Identification of object on interactive display by identifying coded pattern

The present invention generally relates to optically identifying an object using a coded pattern, more specifically such that the object is on or near the surface of an interactive display surface. It involves various coded patterns that can be attached to an object so that it can be identified based on the infrared rays reflected from the pattern when placed.

A visual code, such as a UPC symbol, is typically used to associate a unique identifier (a number or binary bit code) with a given object. This unique identifier is printed on the object. It is detected using an image processing technique that analyzes the sequence of a portion of the visual pattern. When designing such visual coding schemes, the pattern can be easily detected by imaging an object. Or can the identifier be easily restored from the pattern after the pattern has been identified in the image, and of the visual code such as the number of encoded bits, error detection and / or correction, rotation dependence or immutability. It is important to consider various characteristics.

Applications where the visual code must be decrypted often impose constraints on the form of the visual code used to identifier the object. For example, the object to which the visual code is attached is relatively small, so the visual code must be compact. In addition, the pattern used for visual coding must be recognizable by the imaging system used to read the pattern, within its resolution constraints. If a small object has a particular shape, eg, has a round "footprint" on the surface where the visual code is detected, then generally use a circular visual code that matches that round shape of the object. Would be desirable to do. Similarly, if the small object is rectangular or oval, the shape of the object is a shape that makes it easier to determine the orientation of the visual code, facilitates decoding of the patterns used in the code, and allows the object to be identified. Would be desirable.

The visual code used for UPC barcodes on products sold on the market or in other retail stores is typically read by scanning the barcode using a coherent light laser source. Such a laser scanning system has a relatively high resolution and employs a sufficiently high intensity laser beam source capable of scanning barcodes without interference from ambient light. In contrast, decoding the visual code of an object in an image is fairly difficult, especially for images of relatively large surfaces such as the display surface of an interactive display device. The imaging system must first detect the object in the surface image and then decode the pattern of the visual code attached to the object.

Interactive display devices that identify objects using visual codes are known in the art. For example, an interactive display platform was developed at the MIT Media Lab (see, eg, Non-Patent Document 1). The metaDESK contains a near-horizontal geographic surface used to display two-dimensional geographic information. The computer visual system within the desk unit (ie, below the graphical surface) includes an infrared (IR) lamp, an IR camera, a video camera, a video projector, and a mirror. These mirrors reflect the graphic image projected by the projector below the graphic display surface. The IR camera can detect IR light reflected from a "hot mirror" that contains a material backing on the underside of an object called a "phicons" that is placed on the graphic surface. "Great Dome In response to the IR camera's detection of IR reflections from this material that is transparent to visible light applied to the bottom of the phicon), a map of the MIT campus is located where the Great Dome Phicon is located. It will be displayed graphically along with the actual location of the Great Dome in its map. This specification does not provide any teaching or suggestion to use IR patterns, except to show that the software outputs a "list of unidentified'blobs' extracted from the scene" for each visual frame. , Do not teach or explain details about how to be detected and identified.

A similar approach to sensing objects on the display surface is disclosed in several papers published by Jun Rekimoto of Sony Computer Science Laboratory, Inc. in collaboration with other companies. These treatises briefly describe the "HoloWall" and "HoloTable", both of which use IR light to create objects that are close to or in contact with the display surface on which the rear-projected image can be seen. Is detected. The vertical projection panel in the HoloWall and horizontal in the HoloTable is semi-opaque and diffuse, and the object becomes more visible as it approaches and eventually touches the panel. Although it has been mentioned that an IR-detectable pattern on an object is used for identification, again, the IR pattern or how to detect an IR pattern to identify an object is not described in detail.

<nplcit num="1"><text>Brygg Ullmer and Hiroshi Ishii in "The metaDESK: Models and Prototypes for Tangible User Interfaces," Proceedings of UIST 10/1997: 14-17</text></nplcit><nplcit num="2"><text>"Connected Components Analysis" by Andrew Hunter, www.dur.ac.uk/andrewl.hunter/Vision/CV02ConnectedComponents.pdf</text></nplcit>

<p> Various types of visual code are known in the prior art. However, due to the above resolution and other constraints, much of the prior art visual code designed to work with high resolution scanners is attached to relatively small objects in the image. Often not suitable for use with visual systems where the reflected IR light in the image of the entire display surface must be used to read the visual code. Therefore, it would be desirable to employ a visual code that is suitable for the shape and size of the object to be identified and can be identified by a visual detection system with a relatively limited resolution. In order to be able to decode in real time while an object with a coded pattern is moving around on the surface, a suitable coded pattern that can be easily decoded is needed. It is desirable that the pattern gives a relatively high contrast IR in the image of the surface and that the pattern can be decoded through the diffuse surface, but that is because many prior art coded patterns require too much resolution. This is because it cannot be used on such a surface. A more desirable property of a suitable coded pattern is that it has a unique orientation, thus narrowing down the search space needed to find the coded pattern on the surface. For similar reasons, it would be preferable that the coded pattern be recognizable as a single connected component for easy detection and decryption. The prior art has not solved many of these problems, which are relatively specific to diffuse display surfaces and visual detection systems, as described above.</p>

<p> One of the advantages of the present invention is interactive based on the shape and size of the object, the limitations imposed by the resolution of the visual detection system used to image the identifier, and the requirements of the software application in which the object is used. The point is that you can use the appropriate identifier for the object used with the display table. Therefore, one aspect of the invention is a two-dimensional attachment to an object to encode a value so that the value can be determined if the two-dimensional identifier is placed next to the surface detection system of the interactive table. Target identifiers. The two-dimensional identifier includes a cue component with a continuous region of detectable material that the surface detection system responds to. The clue component is approximated by an ellipse when detected by a surface detection system, which has an axis indicating the orientation of the two-dimensional identifier with respect to the coordinate system of the surface detection system. The code portion of the identifier is placed in a predefined location for the clue component. The code part encodes the value with at least one binary element that can be detected by the surface detection system. Also included is a boundary area that surrounds the clue component and the code portion. The boundary area is not detected by the surface detection system as part of the 2D identifier and contains undetectable material that acts as an interference mask surrounding the clue component and code portion to minimize noise. Detectable materials include reflective materials that reflect the infrared rays that the surface detection system responds to.</p><p> Several different types of coding are used in this identifier. In some types of coding, a radial code is used to code the value, and in this type of coding, the clue component contains a continuous radial region of the detectable material. The radial region includes a partial region of undetectable material located at a first defined radius from the center of the radial region. This subregion represents a start bit that indicates the start position where the code portion is read. Also, the code part is configured within the area located at the second defined radius from the center of the radial area, the second defined radius is larger than the first defined radius, and the code part is , Generally extends around the clue component.</p><p> Other coding schemes employ variable length linear code to code the values. In this scheme, the clue components are substantially equal in length and are made of parallel material that is connected to the first end by a defined area of the detectable material used as the starting bit. Includes multiple strips. The parallel strips are separated by an undetectable material at the second end opposite the first end, and the undetectable material at the second end is used as the end bit. The code portion includes a pattern consisting of a detectable area and an undetectable area. Each detectable region and each undetectable region has defined dimensions and is located between parallel strips and between the start and end bits.</p><p> Other coding schemes use variable bit length codes to encode values. In this case, the clue component includes defined dimensions and variable length dimensions. The defined dimension is always smaller than the variable length dimension, and the variable length dimension indicates the range of reference orientation and signing part. The code portion begins with the first binary element at a defined offset from the clue component, and the additional binary element is the range of code portion indicated by variable length dimensions in a direction generally parallel to the reference orientation of the clue component. A matrix of binary elements that forms a line of binary elements ending in, or ends when one line does not contain at least one binary element that can be detected by a surface detection system in the direction generally perpendicular to the variable length dimension. Extend from the first binary element in at least one of three ways to form or form a set of binary elements in a defined position with respect to each other at a defined direction and a defined distance for the immediately preceding binary element. ..</p><p> In other types of coding, the value is coded using a multi-layer variable bit length code, so the clue component is detectable with a binarization threshold and is defined with at least one variable length dimension. Has a shape. At least one variable length dimension indicates the reference orientation and the range of the cord portion. The code part contains at least one binary element that can be detected at the grayscale threshold, but not at the binarization threshold. At least one binary element that can be detected at the grayscale threshold is placed within the clue component, and the clue component is uniform at the binarization threshold, but at least one at the grayscale threshold. Reveal binary elements. Also, the code part is located at a defined offset from the local origin and can start with the first binary element located at the defined position with respect to the clue component, with additional binary elements being the surface detection system. Extends from the first binary element in at least one of the defined directions and the defined distances for the direction generally parallel to one axis used by and for the immediately preceding binary element, and the code portion has a defined shape. Form a series of binary elements at defined positions with respect to each other to include.</p><p> Another aspect of the invention relates to a method of determining a value from a two-dimensional identifier attached to an object when the object is placed near the surface of a surface detection system. This method generally detects the identifier as described above.</p><p> Yet another aspect of the present invention is intended for a system for determining a value from a two-dimensional identifier attached to an object, including an interactive display surface having an interactive side and a contralateral side on which the object can be placed close. To do. The light source in the system directs the IR light to the opposite side of the interactive display surface and to the interactive side through the interactive display surface. Optical sensors are arranged to receive and sense IR light reflected and returned from a patterned object through an interactive display surface to form an image containing a two-dimensional identifier attached to the object. The processor communicating with the optical sensor executes a machine instruction stored in memory, which causes the processor to give an identifier to an object located on or near the interactive display surface. Performs multiple functions that generally match the multiple steps of the method used to determine the value encoded by.</p><p> Many of the above aspects of the invention and the resulting advantages will be apparent as they can be easily understood with reference to the following detailed description of the accompanying drawings.</p>

Example of a computing system that implements the present invention With reference to FIG. 1, examples of systems suitable for implementing various parts of the present invention are shown. The system includes a general purpose computing device in the form of a conventional PC 20 with a processing unit 21, system memory 22, and system bus 23. The system bus combines various system components, including system memory, into processing unit 21, and can be any of several bus structures, including memory buses or memory controllers, peripheral buses, and local buses that use different bus architectures. Good. System memory includes read-only memory (ROM) 24 and random access memory (RAM) 25. The basic input / output system 26 (BIOS), which includes basic routines that help transmit information between elements in the PC 20 at boot time, is usually stored in the ROM 24. The PC20 also includes a hard disk drive 27 for reading and writing to a hard disk (not shown), a magnetic disk drive 28 for reading and writing to a removable magnetic disk 29, and a compact disk read-only memory (CD). -Equipped with an optical disk drive 30 for reading and writing to and from a removable optical disk 31 such as ROM) or other optical medium. The hard disk drive 27, the magnetic disk drive 28, and the optical disk drive 30 are connected to the system bus 23 by the hard disk drive interface 32, the magnetic disk drive interface 33, and the optical disk drive interface 34, respectively. Drives and associated computer-readable media provide non-volatile storage for storing computer-readable machine instructions, data structures, program modules, and other data for the PC20. The environment examples described herein employ a hard disk, a removable magnetic disk 29, and a removable optical disk 31, but those skilled in the art may use magnetic cassettes, flash memory cards, and digital video discs (DVDs). , Bernou

Many program modules, including operating system 35, one or more application programs 36, other program modules 37, and program data 38, shall be stored on a hard disk, magnetic disk 29, optical disk 31, ROM 24, or RAM 25. Can be done. Users can enter commands and information into the PC 20 and send control inputs through input devices such as the keyboard 40 and pointing device 42. The pointing device 42 may include a mouse, pen, wireless remote control, or other pointer, as such conventional methods can be used in the present invention because an interactive display device can be employed for input and control on the part of the user. Pointing device can be omitted. As used hereafter, the term "mouse" is intended to include virtually any pointing device used to control the position of a cursor on the screen. Other input devices (not shown) include microphones, joysticks, tactile joysticks, yokes, foot pedals, gamepads, satellite dishes, scanners, and more. These and other input / output (I / O) devices are often connected to the processing unit 21 through the I / O interface 46 coupled to the system bus 23. The term I / O interface is intended to include the respective interfaces specifically used for serial ports, parallel ports, game ports, keyboard ports, and / or universal serial buses (USB). The system bus 23 is also connected to the camera interface 59, which is coupled to the interactive display device 60 and receives signals from the digital video camera mounted on the interactive display device 60, as described below. To do. Instead, use a USB version of the digital camcorder 2. It can also be coupled to an appropriate serial port I / O, such as port 0. Optionally, the monitor 47 can be connected to the system bus 23 via a suitable interface such as a video adapter 48, provided that the interactive display table of the present invention provides a fairly informative display and is by the user. The interactive operation allows input of information and control of software applications, and is therefore preferably coupled to a video adapter. It is understood that PCs are often coupled to other peripheral output devices (not shown), such as speakers (sound cards or other audio interfaces-not shown) and printers. Will be.

Although the present invention can be implemented on a single machine, the PC20 can also operate in a networked environment using a logical connection to one or more remote computers, such as the remote computer 49. The remote computer 49 can be another PC, a server (generally configured exactly like the PC20), a router, a network PC, a peer device, or a satellite or other common network node, typically the PC20. Although many or all of the above elements are included with respect to, only the external memory storage device 50 is illustrated in FIG. The logical connections described in Figure 1 include a local area network (LAN) 51 and a wide area network (WAN) 52. Such networking environments are common in offices, enterprise-wide computer networks, intranets, and the Internet.

When used in a LAN networking environment, the PC 20 is connected to the LAN 51 via a network interface or adapter 53. When used in a WAN networking environment, the PC20 typically has a modem 54, or cable modem, digital subscriber line (DSL) interface, or integrated services digital network (ISDN) to establish communication over WAN 52, such as the Internet. Includes other means such as interfaces. The modem 54, whether internal or external, is connected to the system bus 23 or to the I / O device interface 46, the bus via the serial port. In a networked environment, the program module used by the PC20 or part of it can be stored in a remote memory storage device. It will be appreciated that the network connection shown in the figure is an example and other means can be used to establish communication links between computers such as wireless communication and broadband network links.

Interactive Surface Examples Figure 2 shows an example of an interactive display table 60 that includes a PC 20 in a frame 62 and is used as both an optical input and a video display device for a computer. In this cutout of the interactive display table, the rays used to display text and graphic images are typically shown using dotted lines and rest on the display surface 64a of the interactive display table. , Or the infrared (IR) light used to detect an object directly above it, is shown using a dashed line. The display surface 64a is set in the upper surface 64 of the interactive display table. The perimeter of the table surface is used to support the user's arm or other object, including a graphic image displayed on the display surface 64a or an object that can be used to interact with the virtual environment. To.

The IR light source 66 preferably includes a plurality of IR light emitting diodes (LEDs) and is mounted inside the frame 62. The IR light output by the IR light source 66 is directed upward and below the display surface 64a, as indicated by the dashed lines 78a, 78b, and 78c. The IR light emitted from the IR light source 66 is an object located on or near the display surface after passing through the translucent layer 64b of the table, including a sheet of belam or other suitable translucent material having light diffusing properties. Is reflected from. Although the figure shows only one IR light source 66, such multiple IR light sources should be mounted at intervals around the inside of the frame 62 to evenly illuminate the display surface 64a. It will be understood that it can be done. Infrared rays output by the IR light source either: -pass through the table surface without illuminating the object, as indicated by the dashed line 78a, or illuminate the object on the table surface, as indicated by the dashed line 78b. Or-As shown by the dashed line 78c, it can illuminate an object that is a short distance above the table surface and is not in contact with the table surface.

Objects on the display surface 64a include a "touch" object 76a resting on the display surface and a "hover" object 76b that is close to the display surface but is not in actual contact. As a result of using the translucent layer 64b under the display surface and diffusing the IR light passing through the display surface, the amount of IR light reflected by the object as the object approaches the display surface 64a is actually the object. Increases to the maximum level that can be obtained in contact with the display surface.

The digital video camera 68 is mounted on a frame 62 below the display surface 64a and is in a suitable position to receive IR light reflected from a touch or hover object located above the display surface 64a. .. The digital video camera 68 is equipped with an IR pass filter 86a that transmits only IR light and blocks peripheral visible light that propagates in the display surface 64a along the dotted line 84a. A baffle 79 was placed between the IR light source 66 and the digital video camera to prevent the IR light emitted directly from the IR light source from entering the digital video camera. Objects that are on or above the display surface, reacting only to IR light reflected from objects that are a short distance above or above the display surface 64a or that are in contact with the display surface 64a. This is because the output signal corresponding to the image of the IR light reflected from the light source must be generated. The digital video camera 68 is further included in the peripheral light (for example, the ambient IR light transmitted along the path indicated by the dotted line 84a) that passes through the display surface 64a from above and enters the inside of the interactive display device. It will be understood that it also reacts to light.

IR light reflected from an object on or above the table surface: Reflects back and passes through the translucent layer 64b and the IR path filter 86a, as indicated by the dashed lines 80a and 80b. Through, or into the lens of the digital video camera 68, or Reflected or absorbed by other inner surfaces in the interactive display without entering the lens of the digital video camera 68, as shown by the dashed line 80c. May be done.

The translucent layer 64b diffuses both incident IR light and reflected IR light. Therefore, as explained above, a "hover" object closer to the display surface 64a reflects more IR light than an object of the same reflectance farther from the display surface and returns it to the digital video camera 68. The digital video camera 68 detects IR light reflected from "touch" and "hover" objects in the imaging field, the position of each such object, and optionally the size, orientation, and shape of the object. The digital signal corresponding to the image of the reflected IR light input to the PC 20 is output for the process of determining. Note that while one part of the object (such as the user's finger) is in contact with the display surface, the other part of the object (such as the user's forearm) may be on the table. In addition, the object may include an IR light reflection pattern or coded identifier (eg, barcode) on the bottom surface that is unique to the object, specific to the object or the class of related objects to which the object is a member. it can. Therefore, the imaging signal from the digital video camera 68 further, according to the present invention, not only detects each such unique object, but also determines its orientation, based on the IR light reflected from the reflection pattern. Can also be used for. The logical steps implemented to perform this function are described below.

The PC 20 is integrated with the interactive display table 60 as shown in FIG. 2, or instead, is external to the interactive display table as shown in the embodiment of FIG. You can also do it. In FIG. 3, the interactive display table 60'is connected to an external PC 20 (including the optional monitor 47, as described above) through the data cable 63. Further, as shown in this figure, a set of orthogonal axes X and Y is associated with the display surface 64a, and also the origin indicated by "0". Although not shown individually, it will be appreciated that multiple coordinate positions along each orthogonal axis can be used to specify a position on the display surface 64a.

The interactive display table is connected to an external PC20 (as shown in Figure 3), or other types such as set-top boxes, video game consoles, laptop computers, or media computers (not shown). When connected to an external computing device, the interactive display table has input / output devices. The power sent to the interactive display table is supplied through a power lead 61 coupled to a conventional alternating current (AC) power source (not shown). The data cable 63 connected to the interactive display table 60'is a USB 2.0 port on the PC20, Institute of Electrical and Electronics. It can be coupled to an Engineers (IEEE) 1394 (or Firewire) port, or an Ethernet® port. Also, as the speed of wireless connections continues to increase, interactive display tables are also connected to computing devices such as the PC20 via such high speed wireless connections, or some other suitable wired or wireless data communication link. It is possible that this may happen. Whether built or external as an integral part of the interactive display, the PC 20 runs algorithms to process digital images from the digital video camera 68, highlighting the good points and interactive. Runs software applications designed to use the more intuitive user interface features of Display Table 60, and is not specifically designed to take advantage of such features, but still of interactive display tables. Also run other software applications that can properly use the input and output functions.

An important and powerful feature of the interactive display table (ie, any of the embodiments described above) is that it displays a graphic image or virtual environment for a game or other software application, and the interaction between the graphic image or virtual environment. It is a function that enables the operation to be displayed on the display surface 64a and identifies an object on the display surface such as the object 76a or an object hovering directly above the object such as the object 76b.

Again, referring to FIG. 2, the interactive display table 60 comprises a video projector 70 used to display graphic images, virtual environments, or text information on display surface 64a. The video projector is preferably of the liquid crystal display (LCD) or digital light processor (DLP) type with a resolution of at least 640 x 480 pixels. The IR cut filter 86b is mounted on the front of the projector lens of the video projector 70 so that the IR light emitted by the video projector enters the interior of the interactive display table and the IR light rests on the display surface 64a. Or prevent it from interfering with the IR light reflected from the object above it. The first mirror assembly 72a passes the projected light transmitted from the projector lens along the dotted line 82a through the transparent opening 90a in the frame 62 so that the projected light is incident on the second mirror assembly 72b. The second mirror assembly 72b reflects the projected light onto the translucent layer 64b at the focal point of the projector lens so that the projected image is visible and focused on the display surface 64a for display. ..

Alignment devices 74a and 74b are provided to adjust the angle of the first and second mirror assemblies to ensure that the image projected onto the display surface is aligned with the display surface, with screw rods and rotatable adjustment nuts 74c. Including. In addition to directing the projected image in the desired direction, these two mirror assemblies can be used to lengthen the path between the projector 70 and the translucidum layer 64b, resulting in a longer focal length (and therefore a lower cost). Projector lenses can be used with projectors.

Object Code Recognition Figure 4 shows a flow diagram exemplifying the entire logic for recognizing a coded object's two-dimensional identifier code. In step 100, an application program, such as a game, specifies the type of code that the application expects to detect attached to an object on the table. Code types that can be used in the present invention include circular, linear, matrix, variable bit length matrix, multi-layer matrix, black and white (binary), and grayscale. Possible ways to specify the code type are to load code pattern characteristics, set thresholds, and / or enable templates for pattern recognition. Template activation can also include generating several rotated versions of the template that facilitate object recognition.

The remaining logic in FIG. 4 is preferably executed by an image processing module that communicates with the currently running software application. In this way, the software application can interface with the image processing module in a standard way. As described in detail below, image processing modules perform various functions related to detecting objects through shape, pixel intensity, code type, and corresponding code values. An example is template matching or threshold setting that attempts to find a coded object if the object can appear on the table in any orientation.

At step 102, the image processing module outputs the current input from the IR video camera in response to the reflected IR light arriving from the display surface of the table from one or more objects on or near the display surface. Detects connecting components in the binary image of the image. In this example of an IR visual system, the connecting component contains a set of adjacent "on" pixels in a binary image. These pixels contain a portion of a two-dimensional identifier code that contains an IR reflective material that returns the reflected IR light towards the IR camcorder. The connection component can correspond to the entire identifier code attached to the object placed on the interactive table, or a subcomponent that is separated from the code part of the identifier attachment. In some cases described below, separate subcomponents serve as clues components that help determine the location and orientation of the identifier code. In other cases, the entire identifier code is used as its own clue component, thereby identifying the location and orientation of the identifier code. The binary image is formed by determining which pixels of the normalized input image exceed a predetermined binarization threshold. Connection component detection is performed using standard algorithms, such as the algorithm described by BKPHorn (see "Robot Vision").

In step 104, the image processing module represents the connecting component as an ellipse and calculates the centers and lengths of the major and minor axes of the ellipse. The image processing module then finds the mean and covariance values for the pixels of the connection component, and based on the statistical mean and covariance of the pixels along the elliptical axis, the position of the connection component and the coordinates of the interactive display table. Determine the orientation. For details of this method, refer to, for example, Non-Patent Document 2.

After determining the position and orientation of the connecting components, the image processing module can easily determine the type and value of the code by performing one or more optional determination steps. In one embodiment, the optional decision steps 106, 110, 114, 118, and 120 are not used and the process sequentially goes from step 104 through code decision steps 108, 112, 116, 122, 124, step 126. The results of the code determination are ranked there, and the closest code type is selected based on statistical analysis. In the second embodiment, these optional decision steps are used to select the code decision step to be performed. For example, optional decision step 106 indicates whether code decision step 108 should be performed. Therefore, this embodiment functions as a filter that reduces the amount of calculation required for code detection.

A combination of the above techniques can be used to prevent the code type from being inadvertently discarded. In the combined approach, multiple optional decision steps can be used to assign a "reliability" factor to each code type to be determined. For example, in an image processing system, a confidence factor can be assigned based on a statistical analysis of connected components that fall within a specified radius, as determined in determination step 106. Similarly, the image processing module can assign other confidence factors if the same connection component fits within the specified square area according to the decision in decision step 110. Other confidence factors are also whether the minor axis of the connecting component is equal to the specified length (for decision step 114), the match between the connecting component and the specified shape (for decision step 118), Alternatively, the bit proximity to the connection component (for decision step 120) can be determined. In general, the confidence factor can be determined for each code type and can be used in determining the code type that best fits the currently detected component. For example, the confidence factor is how well a pixel is "read", that is, how clearly it is divided into black and white intensity levels, and even a valid bitcode from a codebook with valid pixel values. It can also be determined from how well it is "read" as one of them. Also, the confidence level can be determined by whether the maximum and minimum pixel intensity levels differ by at least some predetermined value, which means that if the difference between their intensities is too small, the pixels will be noisy. Because there is a possibility of becoming.

As an example, in Figure 4, the connection component is used to determine code values for each code type that meets at least the minimum criteria, while removing code types that do not meet the minimum criteria for each code type. The combination of the first and second embodiments is shown. These optional decision steps can be performed alone or in combination to first screen the connection components for potentially matching code types. For the code types that the connection components may match, the image processing module preferably determines the distribution of the connection components from the respective code types that may match. The image processing module then ranks the decisions by best fit and selects the most consistent code type and corresponding code value as the code attached to the object.

As shown above, in the optional determination step 106, the image processing module tests the connection component to see if it fits within a particular radius or radial mask. If the sum of the lengths and / or pixel values of the connecting component axes is within the defined range (that is, the connecting components fall within the radial mask), the image processing module proceeds to step 108 to determine the radial code. .. Details of the radial code determination are described below with respect to FIGS. 5 and 6. After determining the radial code, or if the connecting component does not fall within the defined radius or radial mask, the process proceeds to optional determination step 110.

In the optional determination step 110, the image processing module tests the connection component to see if it fits within the specified square area corresponding to the dimensions of the die. If the connecting component matches the rotated white square template, or if the spindle and subaxis are of equal length and correspond to a defined die dimension (that is, the connecting component fits within the die dimension). The image processing module proceeds to step 112 to determine the die spot pattern. Details of determining the spot pattern of the die are described below with respect to FIGS. 7 and 8. After determining the die spot pattern, or if the connecting component does not fit within the specified square area corresponding to the known die dimensions, the process proceeds to optional determination step 114.

In the optional determination step 114, the image processing module tests the connection component for equality to a predetermined length corresponding to the linear code height. If the length of the minor axis of the connecting component is equal to a given length (that is, the second axis of the connecting component is equal to the linear code height), the image processing module proceeds to step 116 to determine its linear code. .. Details of the linear code determination are described below with respect to FIGS. 9 and 10. After determining the linear code, or if the sub-axis of the connecting component is not equal to the predetermined length, the process proceeds to the optional determination step 118.

In the optional determination step 118, the image processing module tests the connection component for matching with a given shape or clue component. If the connecting component is not in the shape of a straight line with one known dimension (that is, the connecting component does not match the clue component), the image processing module goes to step 126 and if it is in the shape of such a straight line. , The image processing module proceeds to the optional determination step 120.

In the optional decision step 120, the image processing module tests the connection component for neighboring code bits. If there are unconnected bits within a predetermined distance and orientation of the connecting component (ie, the connecting component has neighboring code bits), the image processing module proceeds to step 122 to determine the matrix code. Details of the matrix code determination are described below with respect to FIGS. 11 and 12. After determining the matrix code, or if there are no unconnected bits within a given distance and orientation of the connecting component (that is, the connecting component does not have neighboring code bits), the image processing module proceeds to step 124 and is grayscaled. Determine the scale code. Details of the grayscale code determination are described below with respect to FIGS. 13, 14, and 15 (the logic flow from step 122 to step 124 shows the sequential logic flow of the first embodiment).

At step 126, the image processing module ranks the results of the code determination (s) and then performs a statistical analysis to select the code type that the connection component is most likely to match. If the connecting component is not detected as code, the image processing module can evaluate the connecting component as an unidentified, other type of object, such as a user's finger or an uncoded object.

Radial Code Recognition Figure 5 shows an example of radial code 130 that is particularly useful in assigning identifiers to round objects, that is, objects with a round footprint. Radial code 130 includes a light-reflecting internal circular region 132 with a dark "start bit" 134. The start bit 134 is preferably located at a defined first radius from the center of the coding region, taking the shape of a keystone, pie slice, or any other shape that makes it easy to identify the start bit. Can be done. The start bit within the light reflection internal circular region defines a start reference point from which the code value can be determined. The start bit further defines the orientation of the object to be coded with respect to the light reflection internal circular region.

The radial cord 130 further includes an outer evenly divided concentric ring 136 with "data bits" of light and dark keystone shapes. The annulus 136 is located at a second radius from a center that is greater than the first radius. Note that the dashed line is included only in this figure to more clearly indicate the placement of the data bits. However, the actual radial cord does not include such lines and the entire light reflection area contains a single connecting component. In this case, the entire identifier code acts as its own clue component. The outer, evenly divided, concentric annulus contains the values of the code as a series of bright and dark keystone-shaped bits. The code value is read starting by placing the start bit in the defined clockwise (or instead, preferred counterclockwise) direction.

The dark background 138 surrounds the radial cord 130 so that the radial cord can be easily detected as a connecting component. On dark backgrounds, minimize the risk that "noise" pixels will be considered part of the connecting component.

FIG. 6 is a flow diagram illustrating the logical steps performed by the image processing module to process the radial code. At step 140, the image processing module searches for the start bit at a defined radius from the center of the circular region. The search area is located within the radius of the data bits. In general, image processing modules can use a defined fixed threshold to determine the value of any bit. However, in order to improve reliability, the image processing module preferably calculates the threshold value as the average value of the minimum pixel value and the maximum pixel value of the code pattern. As mentioned above, the difference between the minimum pixel value and the maximum pixel value may be too small due to an attempt to decode the noise.

In determination step 142, the image processing module determines if the start bit is found at the defined radius. If the start bit is not found, the process of determining the radial code ends. However, if the start bit is found, the image processing module proceeds to step 144 to read the data bits in the defined clockwise (or counterclockwise) direction from the center of the circular region at the defined radius. These bits have a radial width known for the deformed table coordinates from the input image.

In the optional decision step 146, test for valid radial code. To test the validity of the radial code, the image processing module can attempt to verify that the detected bits represent a code value that exists in a table of possible valid code values. Instead, the image processing module can compare the connecting component with a valid radial code template. This pattern matching method will be described in detail with reference to FIG. If the detected code is not a valid code, the process of determining the radial code ends. If the detected code is valid, or if no optional validation is performed, the image processing module goes to step 148 and is detected in the code using table lookup or other such method. The object ID is determined from the bits.

Die Matrix Code Recognition FIG. 7 shows an example of a matrix code 150 used when recognizing a square object such as a die surface. Matrix code 150 is a square area 152 of the connecting component (shown in white) in which 1 to 6 data bits 154 (die spots) are arranged in a 3x3 grid 158 in 6 predetermined patterns. including. Note that the dashed lines are only included in the figure to illustrate the data bits, and the actual die matrix code does not include the lines.

Die pixels are read from a 3x3 grid within a square area. After this, the 3x3 grid pattern is compared to each of the six acceptable die face patterns and is further rotated 90 degrees for a "2", "3", or "6" spot die face. It is also compared with other versions of the die face pattern. Alternatively, a grid of arbitrary size and associated dieface bit patterns can be read. After the die face facing the display surface is identified, the opposite die face always has a defined relationship, that is, the die face facing the known die face is known as 7. A die face facing upward is known because it has a number of spots equal to the difference between.

The dark background 156 surrounds the matrix code 150 so that the matrix code can be easily detected as a connecting component. On dark backgrounds, minimize the risk that "noise" pixels will be considered part of the connecting component.

FIG. 8 is a flow diagram illustrating the logical steps performed by the image processing module to determine the die matrix code. At step 160, the image processing module rotates the white square template by a predetermined angle up to 90 degrees and determines the orientation of the square connecting component by matching the template with the connecting component. The image processing module then proceeds to step 162 to read the pixel pattern of the binarized image of the connecting component from within the 3x3 grid.

In step 164a, each known die face pattern (and a 90 degree rotated version of the die face pattern for a die face with "2", "3", or "6" spots). Start the process of repeatedly examining. In decision step 166, the pixel pattern read from the connection component is compared with a known die face pattern. If the pixel pattern matches a known die face pattern, the image processing module proceeds to step 168 to determine the value of the top surface of the die. As mentioned above, the total face-to-face on the die is equal to 7, and the value on the top surface is equal to the number of spots in the detection pattern minus 7. After determining the value of the top surface, the image processing module ends. However, if the known die face pattern does not match the pixel pattern of the connecting component, the iterative process ends at step 164b.

Linear Code Recognition Figure 9 shows an example of a linear code 170 used in object recognition. The linear code 172 includes two bright parallel bars 174a and 174b, a bright start bit 176, a dark stop bit 178, and a plurality of bright or dark code bits 180. It will be clear that the terms "bright" and "dark" mean the IR reflectance of a material applied to create a coding pattern on the material of the object or the object itself. A bright bit corresponds to a part of the identifier that is a good reflector of IR light, and a dark bit or area corresponds to a part of the identifier or the surrounding part of an object that absorbs IR light or does not reflect very well. .. These terms are somewhat arbitrary because the image on the display surface can be easily flipped electronically.

The dark background 182 surrounds the linear cord so that it can be easily detected as a connecting component. On dark backgrounds, minimize the risk that "noise" pixels will be considered part of the connecting component. Again, note that the lines that delineate the data bits are included in the figure for illustration purposes only. The actual linear code usually does not contain identifiable lines.

The linear code is a connecting component and is symmetric with respect to the spindle or major axis. The orientation, as calculated from the connection component process, can deviate 180 degrees from the true orientation of the object displaying the code. By examining the positions of the start bit and the stop bit, the decoding algorithm can correct the orientation. The number of bits in the linear code is variable. Given the size of the bits (eg, width), the number of bits in the linear code can be determined directly from the length of the bright parallel bars. Examples 172a-172h of the linear code show all eight instances of the 3-bit code.

FIG. 10 is a flow diagram illustrating the logical steps of the logical steps performed by the image processing module to determine the linear code. At step 190, the image processing module identifies the end edge of the connecting component by starting at the corner of the main axis (major axis) and summing the pixel values in each line perpendicular to the main axis of the connecting component. Linear component termination is checked when the sum is 0 or less than or equal to a given low threshold. At the end of the start bit, it will have a larger sum than at the end of the end bit. In decision step 192, the image processing module tests for the presence of the start bit. If the start bit is not found, the process of determining the linear code ends, and if found, the process continues to step 194 and determines the length of the code from the end of the connection component found in step 190.

In the optional decision step 196, the image processing module tests for a valid code length. Based on the software application in which the object is detected, if the length of the code is not as expected, the process of determining the linear code ends. If the software application does not perform an optional decision to test for a valid code length, or if the code length is as expected, the process proceeds to step 198 to determine the number of bits in the code. The number of bits in the code is calculated by the following formula. Code bit = (connection component length / bit width) -2

The process proceeds to step 200 to determine the value of each code bit along the major or principal axis. The code bit value is: -based on the value of the pixel in the center of the code bit, or-comparing the mean of all the values in the area of the code bit with a given threshold and the mean is given If it is greater than the threshold of, the code bit value can be determined by assuming that it is "1", or by pattern matching, or by using some other judicial use.

The process proceeds to step 202 to determine the object ID from the value of the code bits via table lookup or other such method.

Variable Bit Length Matrix Code Recognition FIG. 11 shows an example of a variable bit length matrix code 210 used in object recognition. The variable bit length matrix code 212 includes a bright rectangular connection "clue" component 214. The sub-axis or minor axis of the clue component has a fixed length, but the spindle or major axis can be of any length (longer than the minor axis). The estimation of the orientation of the variable bit length matrix code is derived in much the same way as the linear code. The orientation of the clue component is correct up to a rotation of 180 degrees, which can be further corrected by determining the side of the clue component where the bitfield is located. The shape of the clue component preferably enhances the orientation reliability of the corresponding elliptical model.

The variable bit length matrix code also includes a matrix field 216, which is located at a distance from the main axis of the clue component on one or both sides of the clue component. Note that the lines that delineate the data bits are included in the figure only to illustrate the data bits, and the actual die matrix code does not include visible lines. The width of the matrix field is equal to the length of the main axis of the clue component. A matrix field contains one or more rows of data bits. Each row of the matrix field contains at least one bright or white bit, so the decoding algorithm reads the bits outward from the clue component until no white bits are found in the row. The number of lines can be determined. Instead, the number of rows in the matrix field can be encoded in the first row of the matrix field. By using a variable number of rows, along with a variable length spindle of the clue component, the code can be shaped appropriately for different object sizes. Since the matrix field can contain one or more checksum bits, it is possible to detect a decoding error after the bit sequence has been decoded by image analysis. Checksum bits can also be used to determine if the decryption process has read the bit sequence from the correct side of the clue component if there is no other step to determine the problem. Such an algorithm simply attempts to decode from both sides of the clue component and uses a valid sequence as the correct bit pattern. Instead, the shape of the clue component can indicate the sides of the matrix in which the code is located.

The variable bit length matrix code is surrounded by a dark background 218. The dark background allows the clue component to be easily detected as a connecting component, minimizing the risk of considering the "noise" pixel as part of the clue component and matrix field.

FIG. 12 is a flow diagram illustrating the logical steps performed by the image processing module to determine the variable bit length matrix code. At step 230, the image processing module determines the length of the clue component. The image processing module represents the clue component as an ellipse and calculates the centers and lengths of the major and minor axes of the ellipse. The image processing module then determines the position and orientation of the clue component with respect to table coordinates from the statistical mean and covariance of the elliptical axes.

The process proceeds to step 232 to determine the number of bits per row in the matrix field. Since the width of the code bits is fixed and known, the number of bits per line is equal to the length of the clue component divided by the known width of the code bits.

In step 234 of the preferred option, the image processing module accesses the normalized image instead of the binarized image to further facilitate processing. Binarizing a normalized image often contains noise pixels, but reading bits from a normalized image yields relatively reliable pixel values and reads smaller bit patterns. Can be done.

The process in block 236a checks the value of the variable bit length matrix code on one side of the clue component. Step 238a begins the process of repeatedly addressing each row of the matrix field on one side of the clue component. Since each row of the matrix field is located at a predetermined offset distance continuous from the clue component, the repetition of reading the code bits is performed in discrete steps. At step 240a, the process reads the data bits in one row of the matrix field. Reading the data bits is preferably performed using a defined fixed or relative threshold, in which case the relative threshold is the difference between the maximum and minimum pixel intensities. Determined as a function of. Pattern matching is possible, but the degree of freedom in detecting variable length rows and variable rows is limited.

In decision step 242a, test for missing code bits, which marks the end of the code. If the line does not contain a code bit, the iterative process ends, and if it does, the process proceeds to step 244a, storing the line code for later processing. The iterative process proceeds to step 246a.

The optional process in block 236b then checks the value of the variable bit length matrix code on the opposite side of the clue component. This step can be done if the application program expects a variable bit length matrix field to be included on both sides of the clue component, or the application program attempts to read from both sides of the clue component and uses an algorithm to checksum or It is performed when the code is validated using other validation processes, because the orientation of the matrix code is determined by ± 180 degrees.

Optional step 238b initiates the process of repeatedly addressing each row of the matrix field on the opposite side of the clue component. From now on, optional steps 240b, 242b, 244b, and 246b perform the same functions as steps 240a, 242a, 244a, and 246a, respectively, but for the bits on the opposite side of the clue component. The coding process proceeds to step 248, where the object ID is determined from the code bits stored in step 244 using a look-up table or other suitable method.

Recognizing Grayscale Codes and Arbitrary Shape Codes Figure 13 shows an example of grayscale code 252 used in object recognition. The grayscale code uses multiple thresholds to detect not only black-and-white images but also grayscale images. Grayscale code 252a includes a connection "clue" component 254a. The dark background 252a surrounds the grayscale code so that it can be easily detected as a connecting component. The dark background makes it easy to detect the clue component and minimizes the risk of considering the "noise" pixel as part of the clue component. Binarization of the input image sets the threshold to a predetermined level at which the input image is rendered in black and white. Therefore, the binarized clue component is white and is therefore easily identifiable as a clue component (the gray bit is white in the binarized image).

If a clue component is detected, a second predetermined threshold is applied to the normalized image, revealing the gray and white code bits within the clue component. This predetermined second threshold may further be a relative threshold as determined as described above. Thus, the binarized clue components 254a, 254c, 254e, and 254g include a pair of half-split grayscale components 254b, 254d, 254f, and 254h, respectively. The gray and white data bits are placed in the defined positions for the clue component. Note that the lines that delineate the data bits are included in the figure for illustration purposes only. However, the actual grayscale code usually does not include such visible lines.

The clue component for the grayscale code does not have to be rectangular, as shown by the clue component examples 254c and 254g. After the connection component is recognized, a second predetermined threshold can represent the grayscale code bits within the connection component. Alternatively, grayscale code can also use pattern recognition to identify clue components.

The embedded nature of the grayscale code allows the use of two connecting components with a common center. Such an array of connecting components is very unlikely to happen by accident and is easily detected. The clue component example 252e includes a connection component 255e centered within another connection component 254e. The orientation of the grayscale code can be defined by defining that some code bits in the clue component are white, gray, or a unique combination thereof. For example, the orientation of grayscale components 254b and 254f is easily confirmed when all but one corner bit needs to be gray. The shape of asymmetric clue components such as 254c and 254g can clearly indicate the orientation of the grayscale cord. Since the grayscale code can include a plurality of checksum bits, it is possible to detect a decoding error after the bit sequence is decoded by image analysis.

FIG. 14 shows an example of arbitrary shape code 260 used when recognizing an object, especially an object having a strange shape. Arbitrary shape code 260 includes a connection "clue" component 262 and one or more data bits 264. The arbitrary shape code is surrounded by a dark background 268. The dark background makes it easy to detect clue component data bits and minimizes the risk of considering "noise" pixels as part of the code. The data bits of the arbitrary shape code are placed in the defined positions for the clue component. Alternatively, the data bits can be placed in a predefined position with respect to the previous data bit so that the position of each data bit is predefined.

The arbitrary shape code can further include one or more empty areas 266. Such empty areas may be inherent in the shape of the object to which the code is attached. Empty areas can affect the placement of data bits. For example, the data bit 264b is separated from the data bit 264a by an empty area 266. Instead, the empty area is one or more bits in the cord when the suspension spring 304 is pushed with a constant force, for example by moving the IR reflective area 306 into contact with the display surface. It can be associated with a mechanism that can affect the code, such as an object that contains a button 302 that changes its value. Instead, the button can also change the reflectance of the regular bits with any of the codes mentioned above.

FIG. 15 is a flow diagram illustrating the logical steps performed by the image processing module to determine the grayscale or arbitrary shape code after identifying the connecting components. At step 270, the image processing module accesses the current normalized image, which contains gray shading. At step 272, the image processing module determines the minimum gray intensity within the connecting component. In this step, the dark background of the grayscale or arbitrary shape code is distinguished from the code in the grayscale or arbitrary shape code. Step 274 indicates that the image processing module sets a second threshold T defined by the following equation. T = (maximum white intensity-minimum gray intensity) / 2

By applying this threshold to the normalized image, it is possible to distinguish between gray bits and white bits. Steps 270, 272, and 274 are not required to read the bits of the arbitrary shape code. However, when you access the normalized image, even small bits can be read accurately.

At step 276, the image processing module accesses a defined pattern of expected bit positions. These predefined positions are applicable to the bits within the clue component and / or to the defined bit positions outside the clue component, but with respect to it. In step 278, the image processing module reads the data bits in the pattern predefined in step 276 with respect to the shape and orientation of the connecting components. These data bits are read using the second threshold.

In the optional decision step 280, the image processing module tests for valid code values. If the code value is not valid, the process terminates, and if it is valid, the process proceeds to step 282, where it determines the object ID from the code bits via table lookup or other such method.

In another approach used in connection with the present invention, the coded pattern attached to the object is recognized for any shape. In this case, all image pixels outside the area (but within a defined larger area) must be black, but the image pixels on the coded pattern are black or white (or gray). Is stipulated. This process works well in conjunction with the above techniques, which validate the read code against a codebook known to ensure that the code is really valid.

Although the present invention has been described for preferred embodiments of the present invention, one of ordinary skill in the art will appreciate that numerous modifications can be made within the scope of the claims. Therefore, the scope of the present invention is not intended to be limited by the above description in any respect, but is defined in its entirety by reference to the claims instead.

The invention for which the exclusive right is claimed is claimed.

<figref num="1">It is a functional block diagram of a generally conventional computing device or personal computer (PC) suitable for image processing of an interactive display table as used in carrying out the present invention.</figref><figref num="2">In the diagram of the inside of an interactive display table showing the included hardware components, the path the light follows in the interactive display table, and the surface of the interactive display table and examples of objects located above it. is there.</figref><figref num="3">It is an isometric view of an interactive display table to which a PC is externally attached.</figref><figref num="4">It is a flow diagram which illustrates the whole logic circuit which recognizes the 2D identifier code attached to the object placed on or near the display surface.</figref><figref num="5">It is a figure of the Example of the radial cord by this invention.</figref><figref num="6">FIG. 5 is a flow diagram illustrating the logical steps performed by an image processing module when determining a radial code attached to an object on a display surface.</figref><figref num="7">It is a figure of the Example of the matrix code by this invention.</figref><figref num="8">It is a flow diagram which shows the logical step of the logical step executed by an image processing module for determining a die matrix code.</figref><figref num="9">It is a figure of the example of the linear code by this invention.</figref><figref num="10">It is a flow diagram which illustrates the logical step of the logical step executed by the image processing module to determine a linear code.</figref><figref num="11">It is a figure of the Example of the variable bit length matrix code by this invention.</figref><figref num="12">It is a flow chart which shows the logical step for determining the variable bit length matrix code attached to an object.</figref><figref num="13">It is a figure of the Example of the grayscale code by this invention.</figref><figref num="14">It is a figure of the Example of the arbitrary shape code by this invention.</figref><figref num="14A">FIG. 5 is a diagram of an embodiment of an object having an arbitrary shape code of FIG. 14 and having a button pressed by a user to correct the shape code.</figref><figref num="15">FIG. 5 is a flow diagram illustrating the logical steps performed by an image processing module to determine a grayscale or arbitrary shape code.</figref>

Code description

20 System memory 35 Operating system 36 Application program 37 Other program modules 38 Program data 21 Processing unit 48 Video adapter 23 System bus 32 Hard disk drive interface 33 Magnetic disk drive interface 34 Optical disk drive interface 46 I / O device interface (for example, serial) 53 Network Interface 47 Monitor 49 Remote Computer 54 Modem 36 Application Program 40 Keyboard