HK1083945B - Method for reading a symbol having encoded information - Google Patents

Description

Method for reading symbols with coded information

Technical Field

The present invention relates to a method and apparatus for reading and decoding symbols having encoded information. In particular, the present invention relates to a method and apparatus for reading and decoding signals generated by two-dimensional relief-formed symbols.

Background

The data symbols printed on the object are interpreted by using an optical imaging system in order to identify the object or to obtain information about the object. Bar code symbols are a common one-dimensional representation of symbols, typically comprising a pattern of vertical bars of different widths separated by spaces of different widths. Because the bar and space elements have different light reflecting characteristics, the reader is able to convert the symbol into an electrical signal by analyzing the light reflected by the symbol. The electrical signal is then analyzed and decoded to provide an alphanumeric representation of the symbol, which contains certain information about the object. Bar code symbols of this type are commonly used in a variety of applications such as inventory control, point of sale identification, or logistics tracking systems.

Since conventional one-dimensional symbologies require a large amount of space to express a relatively small amount of data, so-called two-dimensional barcode symbologies have been developed. The two-dimensional symbolic representation consists of a matrix, which occupies the same space as a rectangle or square. Circular or square marks distributed in specific rows and columns of the matrix, instead of bars and spaces, correspond to the information to be expressed. Thus, within a given space, a two-dimensional matrix symbolic representation contains a much larger amount of data than a conventional one-dimensional barcode.

Printing a plurality of bar code symbols on the label, and then applying the label to an article, box, or the like. Alternatively, the bar code may be embossed into the surface of the article. The method of realization is stamping, engraving, etching, milling, embossing or using other known methods. The symbols may be raised from the surface or recessed into the surface. Embossed symbols are more durable, less expensive, and provide other advantages of typical bar code labels. However, it is difficult to read relief-formed symbols using existing non-contact scanning techniques because the contrast between the convex and concave portions of the symbol is generally low. For example, when a laser scanner scans a relief-shaped symbol, high and low portions of the symbol reflect approximately the same scanning beam, and thus it is difficult to distinguish the high and low portions.

One particular application of two-dimensional symbologies utilizes two-dimensional symbologies in the manufacture of electronic devices such as flat panel displays. Typically, the symbol is formed directly on the release display substrate by printing using a suitable ink or by using other suitable techniques. Alternatively, the symbol may be formed directly on the substrate using laser etching or other suitable precision embossing process. Since the two-dimensional symbology can contain a large amount of data within a relatively small dimensional space, the symbology can store a unique identification code for the substrate, including information such as serial number, lot number, model number, and/or customer number. Also, automation of the manufacturing or testing process can be achieved using the symbols, and the manufacturer can prevent theft or counterfeiting of the parts.

Generally, symbols formed on a typical substrate can be read using conventionally known equipment. However, in the manufacture of flat panel displays such as liquid crystal displays, early processing steps had to cover the entire substrate with a thin film coating of a highly reflective metal such as chromium. Since such metal coatings are conformal coatings in nature and are thin, the relief shapes of the symbols formed on the substrate are typically preserved within the thin film coating, thereby forming a buried relief symbol. The main disadvantage of direct-buried relief symbols is that they typically have little or no reflective contrast and are therefore difficult to image. Since the character of the symbol is buried under the metal thin film, an image of the symbol cannot be formed using a color difference existing between the character and the substrate. To solve this problem, the metal thin film usually has a light emitting surface polished to tend to make the symbol characters more blurred.

Summary of The Invention

The present invention overcomes the disadvantages and shortcomings of the prior art by providing methods and apparatus for imaging and decoding symbols, such as two-dimensional relief formed symbols. In particular, the present invention advantageously provides apparatus and methods for reading and decoding symbols in which one or more edges of a number of data units within the symbol are at least partially distinguishable. Meanwhile, edge analysis may be performed using the method and apparatus according to the present invention in order to determine the validity of an edge when decoding a symbol.

According to one aspect of the invention, a symbol image based on a relief pattern may be determined, wherein the relief pattern represents encoded information and includes at least one discernible edge. In general, the symbol image can be determined by determining the edges of the relief pattern and verifying the validity of the determined edges by performing edge analysis on the determined edges. Data cells of the symbol image at least partially representing the encoded information in the relief pattern may be determined to decode the symbol image to provide the encoded information within the relief pattern.

According to another aspect of the invention, there is provided an apparatus for reading a relief pattern, wherein the relief pattern has at least one discernible edge and represents encoded information. Typically, the apparatus comprises means for creating an edge image from the reflected light pattern, and means for verifying the validity of the edges of the edge image. The edge image is preferably created from light reflected from the relief pattern. The validity of the edges of the edge image is preferably determined in order to decode the data cells of the symbol image based on the relief pattern, thereby providing the encoded information within the relief pattern.

Other features and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments, when read in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.

Brief description of the drawings

The accompanying drawings, which are incorporated in and constitute a part of this application, illustrate various aspects of the invention and together with the description of the embodiments, serve to explain the principles of the invention. A brief description of the drawings is as follows:

FIG. 1 is a typical two-dimensional symbol displayed on a substrate, detailing the internal data area of the symbol which is made up of a plurality of data cells;

FIG. 2 is a cross-section of the symbol of FIG. 1 taken along line 2-2, showing in detail the portion of the symbol above the substrate surface that forms the relief symbol;

FIG. 3 is a cross-section of the symbol of FIG. 1 taken along line 2-2, further including a coating overlying the symbol;

FIG. 4 is a schematic block diagram of an exemplary imaging system including a light source and a reader in accordance with an aspect of the present invention for imaging and decoding symbols, such as the symbols shown in FIGS. 1, 2, and 3;

FIG. 5 is an edge image of the symbol of FIG. 1 as imaged using the imaging system of FIG. 4 in accordance with an aspect of the present invention, showing in detail the edges of the raised portion of the symbol;

FIG. 6 is a schematic block diagram of a reader usable in accordance with the present invention, the reader having an imaging device and an output in accordance with an aspect of the present invention for processing symbols such as the edge image shown in FIG. 5;

FIG. 7 is a flow chart of an edge analysis algorithm according to the present invention;

FIG. 8 is a view of the edge image of FIG. 5 displayed in a Cartesian coordinate system;

FIG. 9 is a view of the edge image of FIG. 8 further showing the center mark of the data cell of the symbol;

FIG. 10 is a view of the edge image of FIG. 9 detailing the values assigned to certain corners of the data cell in accordance with an aspect of the present invention;

FIG. 11 is a view of the edge image of FIG. 9, further illustrating an exemplary invalid edge that may be determined in accordance with an aspect of the present invention;

FIG. 12 is a view of the edge image of FIG. 9, further illustrating binary values assigned to data cells of the edge image in accordance with another aspect of the present invention;

FIG. 13 is a flow chart of an edge analysis algorithm of the present invention that may be used in steps 322 and/or 324 of the flow chart shown in FIG. 7; and

FIG. 14 is a view of the edge image of FIG. 11, further illustrating binary values assigned to data cells of the edge image in accordance with another aspect of the present invention.

Detailed Description

The present invention is directed to methods and apparatus for efficiently reading and decoding certain images or symbols, such as relief symbols. In particular, the invention aims to analyze images of symbols containing one or more edges of a number of data cells, the data cells comprising geometric shapes contained within the symbol, and the data cells generally providing encoded information readable according to the invention. Edge analysis may be performed using the method and apparatus according to the present invention to determine the validity of an edge when decoding a symbol.

The principles of the present invention may be applied to any symbol, including linear or stacked regions, or other symbolic representations, preferably symbols such as the region relief patterns discussed below. The area symbol representation as used herein is intended to mean, for example, the trademark Vericode^TMOr Data Matrix^TMOr Code One^TMAnd the like, using a matrix of data cells rather than one or more rows of bars and spaces. Stacked symbology, as used herein, refers to any symbology, such as PDF417, that typically uses several adjacent rows of symbols, each row having several characters defined by groups of bars and spaces of various widths.

Zone symbolic representations are well known, as described in U.S. Pat. No. 5,612,524 and U.S. Pat. No. 4,924,078. Fig. 1 shows a typical symbol 10 in such a regional symbol representation. Generally, the symbol 10 includes an internal data region 12 with internal data elements 14 arranged in a matrix fashion, the data region 12 and data elements 14 preferably being rectangular as shown, although any other shape is contemplated. As shown, the internal data area 12 has data cells 14 in an "on" state and data cells 14 in an "off state. As shown, the "on" cells are black (cells referred to by reference numerals 16, 18, 20 and 22), and the "off cells are white (remaining cells of the inner data area 12). The on and off indications are used when decoding a symbol, such as symbol 10. It will be appreciated that any binary indication may be used to distinguish between data cells 14, such as on and off, 0 and 1, and black and white.

As shown, the inner data region 12 is preferably surrounded by directional and/or timing data cell boundaries 24, which are typically used for timing and symbol orientation. As shown, the boundary is typically formed by "opening" a data cell. An external data area 26 may be provided around the border 24, possibly including external data elements (not shown) for providing additional information about orientation, timing and symbol identity. The area surrounding the border 24 or outer data area 26, if any, is preferably one or more concentric straight loops of "closed" data cells around the outermost "open" cells. The number of concentric straight loops of the same area required is determined by the environmental factors of the symbol usage. Alternatively, the outer data zone 26 may be treated as a quiet zone, or surrounded by another quiet zone.

The symbol 10 may be formed directly onto the substrate 28, such as by printing or controlled deposition of a print or other coating, or by providing the symbol on an adhesive-backed label or label by printing or using any other suitable technique, and then adhered or affixed to the substrate. Alternatively, the symbol 10 may be etched, engraved, or otherwise formed in relief on a suitable substrate or article to form the symbol 10. For example, where the substrate 28 is a glass substrate, the symbol 10 may be printed on the substrate 28 using a suitable ink, thereby obtaining a suitable thickness to enable formation of a relief symbol. To be able to form a relief symbol, the thickness of the symbol must be discernable as part of the edge analysis described below. It will be appreciated that the substrate 28 may be any substrate or article upon which a symbol may be formed, the symbol may be formed using a high contrast symbol, a low contrast symbol, an embossed symbol, a non-embossed symbol, or in any other known or expanded format, and may be formed using any technique.

Fig. 2 shows a cross-sectional view of the symbol 10 of fig. 1. In general, if the symbol 10 is formed in relief, the boundary 24 and the data elements 14, such as the data elements 18, are raised regions relative to the surface 30 of the substrate 28. Alternatively, the boundary 24 and the data cell 14 may be recessed regions relative to the surface 30 of the substrate 28. The raised or recessed areas include one or more discernible edges. As shown, the boundary 24 on the left has edges 32 and 34, the data cell 18 has edges 36 and 38, and the boundary 24 on the right has edges 40 and 42. Note that the symbol 10 shown includes additional edges that are not visible in the cross-section of fig. 2. For example, returning to FIG. 1, the data cell 18 includes edges 44 and 46.

For some applications, the entire symbol 10 or portions of the symbol, such as the data cells 14 or the border 24, may be formed so that there is no or little contrast in light reflectance between the symbol 10 and the surface 30 of the substrate 28. For example, a symbol such as symbol 10 may be printed or formed on a substrate, wherein the color of the symbol and the color of the substrate are substantially the same. For relief symbols etched or formed directly on a substrate, there is no or little contrast, because the symbol is formed directly on a bulk substrate and there is no chromatic aberration.

Alternatively, a symbol such as symbol 10 may be covered (at least partially) with a coating, whether intentionally or unintentionally, such that the contrast originally present between the symbol and the substrate is no longer present. Such coatings include inks and/or paints from writing or other marking devices, or other coatings from deposition processes.

The coating may also be formed as part of the manufacturing process. One example is microelectronic device manufacturing technology such as flat panel display manufacturing technology. Referring to fig. 3, a symbol such as the symbol 10 may be formed on the surface 30 of the substrate 28, the symbol 10 containing a unique identification code for the substrate 28 including information regarding serial numbers, lot numbers, and the like. Typically, the substrate 28 of the flat panel display is a glass or ceramic substrate upon which the symbol 10 is formed using a suitable technique, such as photolithography. In the manufacture of certain microelectronic devices, such as liquid crystal displays, part of the process involves covering a substantial portion of the substrate with a coating 48, such as a thin film of a metal, e.g., chromium metal. Since such coatings are conformal coatings in nature and are thin, the relief shape of the symbol formed on the substrate is typically preserved within the thin film coating. The main disadvantage of such relief symbols is that they typically have little or no contrast in retroreflection, and are therefore difficult to image and decode using conventional retroreflection reading processes. In such applications, since the symbol characters are buried under the metal thin film, the color difference existing between the characters and the substrate cannot be used when viewing or reading the symbol. To address this problem, thin films of metal, such as chrome, provide a shiny or highly reflective finish, often making the geometry of the symbols that make up the characters, such as the data cells 14, more ambiguous. Also, the information contained in the symbol is contained in the spatial domain and cannot be read with conventional known readers. Accordingly, the inventive aspects of the present invention provide methods and apparatus for imaging and decoding such symbols.

Reference is now made to fig. 4, which illustrates an imaging system 100 for reading symbols, such as the relief symbols described above. In general, imaging system 100 includes one or more light sources 102 and a reader 104. As shown, light beam 101 from light source 102 impinges on surface 106 of substrate 108, forming reflected light beam 103 which is received by reader 104. The light source 102 is preferably capable of edge illumination of the relief pattern. In particular, the light source 102 is preferably capable of at least partially illuminating at least some edges within the symbol formed on the surface 106 of the substrate 108. Suitable light for illuminating the edges include light used in conventional dark field optical microscopy equipment and illumination sources. In general, light source 102 includes any known or developed device for generating light such as an incandescent light source, a light emitting or laser diode, or the like.

The orientation of the light source 102 may be determined in any manner as long as at least one edge or multiple edges can be identified. For example, when the symbol edge is perpendicular to the substrate, the light source 102 should be at least slightly tilted to reveal the edge. As shown, light source 102 may be offset from reader 104, which is preferably above substrate 108, for analysis by reader 104. For example, a ring light of light emitting diodes may be used. The ring light may be obliquely provided from all sides of the substrate to thereby illuminate all sides. Depending on the type of light reflected, a light sensor may be used within reader 104, and one or more sensors may be mounted to receive the reflected light and provide a signal representative of the detected edge pattern. In addition, light source 102 and/or reader 104 may be moved relative to the substrate or each other to scan all sides.

FIG. 5 illustrates an edge image 200 of the symbol 10 shown in FIG. 3 having the coating 48 applied thereto, as formed by illuminating the symbol 10 with one or more suitable light sources, such as the edge-illumination enabled light source 102 described above. As can be seen, the edges of the raised portions of the relief symbol are read.

Fig. 6 illustrates an exemplary embodiment of reader 104 according to the present invention. Reader 104 includes a memory 110, a Central Processing Unit (CPU)112, an imaging device 114, and an output 116. For some applications, the imaging system 100 also includes a gain controller (not shown) for controlling the output level of the signal generated by the imaging device 114, and a photometric detector (not shown).

The entire imaging system 100 may be contained within one component. Alternatively, the elements may be distributed such that a simple lightweight component is used to create the image data and transmit the data to a central component for further processing. The image data is then transferred to a connected computer, stored locally for later transfer, or forwarded to an application program resident within the imaging system.

The CPU112 preferably controls certain operations of the imaging system 100 according to a set of instructions, such as software and firmware, stored in the memory 110. It is contemplated that CPU112 may control operations of decoding image data stored in memory 110, transmitting image data to other systems, activating light source 102, and storing data in memory 110. Note also that various tasks such as decoding may be performed using a plurality of CPUs.

The present invention may use a conventional CPU112 or microprocessor. Memory 110 preferably comprises a semiconductor-based Read Only Memory (ROM) device, as such devices are non-volatile and retain stored instructions in the device's memory even when power is removed. Other storage devices are also contemplated.

It is contemplated that the functions performed by the stored instruction set may be implemented using conventional hardwired circuitry, however, it is preferable to use software or firmware systems because they are simpler, easier to adapt to changes, and less costly. Also, it is contemplated that ROM devices such as memory 110 may be erasable or programmable to modify or revise the software as needed. In addition, a permanent storage medium such as a magnetic disk or an optical disk may be used as the memory 110.

According to one aspect of the present invention, the imaging device 114 preferably converts the received light into a plurality of electrical signals corresponding to the intensity of the received light. The electrical signal is then further amplified and converted to digitized data representing an image on the substrate 108 containing the symbol to be read. The imaging device 114 includes, for example, a Charge Coupled Device (CCD). Further, the imaging device may use Complementary Metal Oxide Semiconductor (CMOS) technology. Typically, a CCD includes a one-or two-dimensional array of adjacent photodiodes, each photodiode defining a different pixel of the array. Note that the array of CCD imaging elements is not limited to any particular pattern. For example, the array may be arranged in generally linear rows and columns; the array may be arranged in a diamond pattern with rows that are straight and columns that are regularly offset; or the array may be arranged in any other pattern in which the photodiodes are ordered with respect to each other.

Each photodiode of the CCD array generates a voltage and/or current that is representative of the intensity of light reflected onto the particular photodiode. The CCD array is electronically scanned by sequentially activating each photodiode, generating an output signal containing the voltage and/or current level of each photodiode. The detected voltage and/or current levels are preferably amplified and converted to binary values. After the imaging device 114 converts the received light into binary values representing the image of the symbol, the binary values are transferred to a memory 110, which may also comprise a conventional semiconductor-based Random Access Memory (RAM).

For some applications, the imaging device 114 may also include a photometric detector (not shown) for detecting the intensity of light reflected onto the imaging device 114. The photometric detector provides a digitized output to the CPU112 that represents the instantaneous intensity of light reflected onto the imaging device 114. Photometric detectors are well known in the art and any suitable detector may be used with the present invention.

A preferred method of efficiently reading embossed symbols in accordance with the present invention generally comprises: an image such as the edge image 200 shown in fig. 5 is subjected to edge analysis. It is desirable to perform a multi-step edge analysis for efficient and reliable reading of relief symbols while eliminating invalid edges and assigning binary values to data cells of the symbols for use in decoding the symbols. There are a number of reasons for the presence of invalid edges in an image. For example, images, particularly images of relief symbols covered with such coatings, are difficult to image and may contain artifacts and/or features that look like edges of the underlying symbol. At the same time, dust and dirt, as well as smudges or other extraneous markings, may also be visible as edges. Thus, the purpose of the principles and concepts of the present invention is to analyze images in determining the validity and invalidity of potential edges, discussed below with reference to the exemplary edge image 200 shown in FIG. 5 and the flow chart shown in FIG. 7.

Referring to fig. 7, a preferred process 300 for decoding symbols in accordance with the present invention is shown. An initial step 302 acquires an image to be analyzed, such as the edge image 200 shown in FIG. 5. The images may be acquired using any known or improved technique, such as using a conventional camera or using the imaging system 100 discussed above. Note that an image contains one symbol or multiple symbols that need to be decoded, where multiple symbols are decoded simultaneously or sequentially in accordance with the present invention.

A next step 304 finds objects within the image acquired in step 302. For example, the contrast region may be considered as an object to be analyzed. Typically, an image may contain invalid symbols as well as objects that look like symbols, such as smudges or foreign marks, handwriting, and other symbols that do not contain encoded information. Step 304 preferably identifies all objects within the image of interest that are likely to be symbols or portions of symbols. This is accomplished by using known or improved image processing or graphical analysis techniques to determine and evaluate areas of contrast, color, shape, etc. The image analysis techniques described above are well known and commercially available. Numerous objects within a symbol may be prioritized or ordered for analysis in a particular order. For example, the objects may be ordered according to size or shape such that objects that may be valid symbols are analyzed first, and objects that may not be valid symbols are analyzed later.

Step 306 begins analyzing the first object identified in step 304. However, all of the objects identified in step 304 may be analyzed simultaneously, such as by using multiple image analysis systems or other similar methods. Step 308 finds the edge or outer boundary of the object being analyzed, such as the edge image 200 shown in FIG. 5. Any technique for determining edges of an object may be used. The preferred technique is to use a Hough transform that determines straight lines.

For example, referring to FIG. 8, an edge image 200 is represented in a Cartesian coordinate system having coordinate axes 202 and 204. A coordinate system may be used to determine the relative positions of certain shapes of the edge image 200, and in particular, the image analysis software used may use the coordinate system. It is noted, however, that any other coordinate system may be used besides the cartesian coordinate system. Step 308 preferably identifies edges 206, 208, 210, and 212 of edge image 200. Edges 206, 208, 210, and 212 define the outer boundaries of the symbols of edge image 200. A next step 310 determines the corners of the edge image 200 by considering the intersection of the edges determined in step 308. As seen in fig. 8, edges 206, 208, 210, and 212 occur at points (1, 1), (1, 9), (9, 9), and (9, 1), thereby defining corners of edge image 200.

Step 312 determines the center position of the data cells of the edge image 200. In some aspects of the invention, the center of the data cell may be determined when the size of the edge image 200 is known. For example, as shown, the edge image 200 may be determined to be comprised of an 8x8 matrix of data cells, where the data cells have edges 206, 208, 210, and 212. Thus, the matrix includes 64 data cells (1 x1 for each data cell). Within the coordinate system, each of the 64 data cells has a midpoint that can be easily determined. That is, the midpoint of each cell is half the length between each coordinate axis of the cell. Referring to fig. 9, a data cell 214 having a midpoint (1.5 ) is shown. While another data cell 216 is shown with a midpoint (5.5, 4.5). Therefore, in fig. 9, the midpoint of each of the 64 data cells of the edge image 200 is represented by a cross. The midpoint of the cell can be determined in any manner and does not need to know the size of the edge image or symbol of interest to be decoded. That is, the process 300, or a portion thereof, is iteratively repeated by attempting different matrix configurations until a solution is found. Generally, in some form of the invention, the process is repeated until the symbol is decoded. In addition, the above-described techniques may be applied to any edge image or symbol, and are not limited to a square matrix.

Similar to step 314, the relative position of the corners of the data cells within the coordinate system is determined. Furthermore, as well as determining the midpoint of a data cell, the corners of the data cell can be easily determined within the coordinate system. For example, the corners of the data cells 214 are located at (1, 1), (1, 2), (2, 2), and (2, 1). Likewise, the corners of data cell 216 are located at (5, 4), (5, 5), (6, 5) and (6, 4).

Next, step 316 determines whether the particular data unit contains an edge, including a valid edge or an invalid edge. Determining the validity of the identified edge is described in detail below. The purpose of step 316 is to identify objects that may be edges. Referring to fig. 9, a typical data unit is identified by reference numeral 218. The midpoint of data cell 218 is located at (3.5, 5.5) and its neighbors are 220, 222, 224 and 226, with the midpoints being (2.5, 5.5), (3.5, 6.5), (4.5, 5.5) and (3.5, 4.5), respectively. In the best mode of step 316, points between the midpoint of the data cell of interest and the midpoints of adjacent data cells are evaluated to determine whether an edge exists. For example, by looking at points (3, 5.5), (3.5, 6), (4, 5.5) and (3.5, 5), the edges of the data cell 218 are determined. Thus, the edges 228, 230, 232, and 234 of the data cell 218 may be identified. The above process is preferably repeated for each data unit of the edge image 200 to identify all edges of all data units of the edge image. The above evaluation can be done visually or graphically, preferably using well-known image analysis software. In other words, the edge image 200 is preferably in a digital format that can be analyzed using well-known computerized image analysis techniques.

Next, step 318 assigns a numerical value to each corner of the data cells of the edge image, which can be used to eliminate invalid edges. Preferably, each corner of each data cell is assigned a value based on the number of edges emanating from that particular corner. In accordance with the present invention, a set of values may be determined that may identify a particular corner from which to issue an invalid edge. Note that the corners of data cells with no outgoing edges are assigned a value of 0 or ignored altogether for analysis. For example, an edge that leaves a corner in a first direction is assigned a value of 1. The edge that leaves the corner in the second direction is assigned a value of 2. An edge leaving a corner in the third direction is assigned a value of 4. And assigning a value of 8 to an edge that leaves a corner in the fourth direction. A particular corner is assigned a value that is the sum of the values of the edges leaving the particular corner. For the purposes of this application and for purposes of illustration, the foregoing directions will be referred to as the up, left, down, and right directions, respectively, of the drawings associated with this application. Thus, referring to fig. 10, each corner of the data cell from which an edge emanates is marked with a numerical value assigned using the techniques described above. For example, the corners of data cells 218 are located at (3, 5), (3, 6), (4, 6), and (4, 5). The corner at (3, 5) includes an edge that leaves in the upward direction (assigned a value of 1) and an edge that leaves in the rightward direction (assigned a value of 8), and thus the corner is assigned a value of 9. The corner at (3, 6) includes an edge that leaves in a downward direction (assigned a value of 4) and an edge that leaves in a rightward direction (assigned a value of 8), and thus the corner is assigned a value of 12. The corner at (4, 6) includes an edge that leaves in the downward direction (assigned a value of 4) and an edge that leaves in the leftward direction (assigned a value of 2), and thus the corner is assigned a value of 6. Finally, the corner at (4, 5) includes an edge that leaves in the downward direction (assigned a value of 4), an edge that leaves in the leftward direction (assigned a value of 2), an edge that leaves in the upward direction (assigned a value of 1), and an edge that leaves in the rightward direction (assigned a value of 8), thus assigning a value of 15 to the corner. As shown, since the edge image 200 contains all valid edges, each value assigned to a corner of a data unit of the edge image 200 may be used to indicate the valid corner from which the valid edge emanates. That is, in one aspect of the present invention, the values of the corners from which the effective edges are issued include at least 3, 5,6, 9, 10, 12, and 15.

Fig. 11 shows an edge image 400 that contains several invalid edges and is used to explain the method of eliminating the invalid edges using step 318 of process 300. It can be seen that the first invalid edge 402 leaves the cell corner at (5, 7) at the same time as it leaves the cell corner at (6, 7). Since the edge is not visible in the relief or topographical pattern, edge 402 is determined to be invalid. In addition, since this type of edge is not allowed in a particular encoding scheme, the edge 402 is referred to as an invalid edge. Thus, the cell angle is assigned a value of 8 and 2, respectively. Likewise, the values 8 and 2 identify the corners from which the invalid edge emanates. In order to determine whether a particular edge is invalid, adjacent corners need to be considered together, and if both corners are assigned invalid values, a common edge of both corners is determined to be an invalid edge.

Fig. 11 illustrates another exemplary invalid edge 404. As discussed with reference to edge 402, edge 404 is not visible in the relief pattern. The edge 404 is a common edge located at the corner of (5, 5) and at the corner of (5, 4). Thus, the angle at (5, 5) is assigned a value 14 and the angle at (5, 4) is assigned a value 11. Additionally, edges 406, 408, and 410, which are invalid edges, respectively, are illustrated. The edges 406, 408, and 410 determine additional values 1, 4, 7, and 13 that may be used to identify invalid edges. Thus, in one aspect of the invention, the values of the corners from which the invalid edge emanates include at least 1, 2, 4, 7, 8, 11, 13, and 14.

In addition to the above method, another test may be used to eliminate invalid edges in step 320, i.e., identify corners from which odd edges are issued. That is, according to the present invention, a corner from which an odd number of sides are emitted indicates an error. Referring to fig. 11, the corners located at (2, 4), (3, 4), (5, 4), (5, 5), (5, 7), (6, 7), (7, 6), (7, 7) emit odd number of sides. Specifically, the corners at (5, 4), (5, 5) and (2, 4) respectively emit three edges, and the corners of the remaining other invalid edges emit one edge. Thus, if an edge is a common edge that emits corners of an odd number of edges, the edge is determined to be invalid. For example, the angles at (5, 4) and (5, 5) each emit three edges and have a common edge 404. Thus, edge 404 is determined to be invalid. Likewise, by the same analysis, edges 402, 406, and 408 are determined to be invalid edges.

Each data unit is assigned a logical value or code before decoding the information contained in the symbol or edge image (e.g., edge image 400). Preferably binary values representing on or off, black or white, etc., such as binary values 0 and 1, are used. Also, another step 322 of scanning a row to assign a binary value to each data cell may be performed, followed by step 324 of scanning a column to assign a binary value to each data cell. Referring to FIG. 13, steps 322 and 324 include scanning in the opposite direction to provide even further error correction capability. Note that scanning the rows and columns simultaneously may be included in any order. Note that the decoding step 326 may be performed at any time after the binary value is assigned to the cell. For example, after scanning a row and/or a column, a decoding step 326 is performed (see line 323 in FIG. 7). Further, the decoding step may be performed in the process of assigning binary values to one or more data cells.

In step 322, the rows are first scanned in a left-to-right direction for each row of the edge image 400. Each data cell is preferably assigned a binary value, such as 0 or 1, to create a symbol image 400 with the correctly identified data cell, which is then decoded. The values are assigned by first assigning an initial value, e.g. 1, to the first data element of a row (the leftmost data element). Next, values are assigned to the adjacent data cells based on whether there is an edge between the adjacent data cells. If there is an edge, the neighboring cell is assigned a value opposite to the value of the previous data cell. If there are no edges, the neighboring data cells are assigned the same value as the previous cell. For example, fig. 12 shows the binary values assigned by such a scan. In step 322, to perform a right-to-left scan, a binary value is placed in the lower right quadrant of the cross used to mark the midpoint of each data cell. It is also possible to perform the scanning in the opposite direction, i.e. right to left per row, and place the value in the upper right quadrant of the cross marking the middle point of each data cell. As described below, in step 324, the values obtained by scanning the columns in the top-to-bottom direction are placed in the top-left quadrant and the values obtained by scanning the columns in the bottom-to-top direction are placed in the bottom-left quadrant.

For example, a certain row of the edge symbol 400 shown in fig. 12, which includes data cells whose midpoints are (5.5, 1.5), (5.5, 2.5), (5.5, 3.5), (5.5, 4.5), (5.5 ), (5.5, 6.5), (5.5, 7.5), and (5.5, 8.5), is described below. The data units are labeled a, B, C, D, E, F, G, and H, respectively, for reference. First, the initial data unit (i.e., the data unit labeled a) is assigned a value of 1. Next, since there is an edge between the data cells a and B, the data cell B is assigned a binary value opposite to the value of the previous data cell, i.e., 0. In addition, there is an edge between the data cells B and C, so a binary value of 1 is assigned to the data cell C. For the same reason, the data cell D is assigned a binary value of 0. Since there is no edge between data cells D and E, E and F, and F and G, binary values of 0 are assigned to data cells E, F and G. Finally, data cell H is assigned a binary value of 1 because there is an edge between data cells G and H.

Preferably, binary values are assigned to all cells by scanning the rows in both directions in the manner described above. Thus, for right-to-left scanning and left-to-right scanning, the generated binary values are placed in the upper right quadrant and the lower right quadrant of the cross used to mark the midpoint of each data cell, and fig. 12 represents the binary values of the edge image 400. Meanwhile, each column of the edge image is scanned and a binary value is assigned, just like the line scan of the edge image 400. Thus, for both top-to-bottom scanning and bottom-to-top scanning, the resulting binary values for the columns are placed in the upper left quadrant and the lower left quadrant of the cross that marks the midpoint of each data cell.

Next, step 336 determines the binary value of each data cell by analyzing the binary values assigned by the four scans of steps 322 and 324. The analysis includes considering the net value of four scans. For example, referring to the data cell a of fig. 12, the net value of the binary value assigned to the cell a is 4(1+1+1+ 1). Each scan assigns a value of 1 to the cell. In other words, the binary values of cell a are all 1, since all scans are consistent. Thus, a net value of 4 for the four scans using steps 322 and 324 indicates that a binary value of 1 may be assigned to the data cell. Likewise, each of the four scans assigns a binary value of 0 to data cell B. Thus, for the same reason, a net value of 0 using four scans indicates that the data cell can be assigned a binary value of 0. After determining the binary values of all the data cells in step 336, step 326 is performed, and step 326 decodes the edge image according to the binary values assigned in step 336. If the edge image is successfully decoded, a decision is made in step 328 to save the information, and then proceeding to step 330, step 330 considers whether more objects were identified in step 304. If there are more objects to consider, the process 300 moves to step 332 to begin analyzing the next object in accordance with the present invention. If no other objects need to be analyzed, the process ends at step 334. Note that if the edge image cannot be decoded, the process proceeds to step 330 to consider other objects or retry decoding. For example, the decoding is retried using a different threshold in order to decode the information.

As for the binary values assigned to all the cells of the edge image 400 shown in fig. 12 by the four scans, it is noted that the edge image 400 of fig. 12 does not contain invalid edges. Similarly, the edge image 400 of FIG. 12 is represented by FIG. 14 with several invalid edges (edges 402, 404, 406, 408, and 410) to explain the method of assigning binary values to the cells of the edge image using the scans of steps 322 and 324, wherein the edge image is decoded using the binary values. Several data units are labeled I, J, K, L, and M for reference. Meanwhile, fig. 14 shows binary values assigned by the four scans of steps 322 and 324. First, a data cell having a net value of 4 of the binary values assigned for the four scans of steps 322 and 324 (see cell I) is assigned a binary value of 1. Meanwhile, assigning a cell with a net value of 0 to a binary value of 0 (see cell L) a net value of 1 or 3 for a cell indicates that three of the four scans know the correct binary value for the cell. In other words, the correct binary value of two scans (forward and reverse) of one of the row or column, but not both, is known. For example, referring to the cell labeled M in FIG. 14, a net value of 1 is assigned to cell M. A binary value of 0 is assigned in the column scan from top to bottom, and a binary value of 1 is assigned in the scan from bottom to top, which is not coincident therewith. However, scanning from right to left and from left to right coincide, assigning a binary value of 0. Therefore, since the binary value 0 is assigned to three scans out of the four scans, the cell is assigned the binary value 0 for decoding the edge image 400. The same analysis is performed for cells with a net value of 3. For example, the cell labeled J has a net value of 3, and a binary value of 1 may be assigned because three of the four scans assign a binary value of 1. Finally, a net value of 2 for a cell indicates that the scans in opposite directions along the rows and columns are not uniform. Therefore, such cells cannot be assigned binary values and can be marked as unknown. For example, a cell labeled K has a net value of 2 and can be labeled as unknown.

Note that if only the column scanning from top to bottom and the row scanning from left to right are performed, a binary value of 0 may be erroneously assigned to the cell K (a binary value of 1 should be assigned to the cell K). In general, since it is preferable to mark cells as unknown over incorrectly marked cells, performing four scans provides information sufficient to assign the correct binary values to some cells, especially if invalid edges are present, sufficient to mark other cells as unknown. Thus, assigning erroneous binary values to cells can be minimized or eliminated.

The detailed description sets forth the numerous features and advantages of the present invention described herein. It should be understood, however, that while particular forms or embodiments of the invention have been illustrated and described herein, various modifications, including shape modifications and arrangement of parts, may be made without departing from the spirit and scope of the invention.

Claims (17)

1. A method of characterizing a symbol in terms of a relief pattern having a two-dimensional matrix of data elements representing encoded information, the method comprising the steps of:

determining the presence of a discernible edge of the relief pattern and compiling information representing an edge image, the edge image at least partially representing a two-dimensional matrix data element and containing the discernible edge;

verifying the effectiveness of the edge image by performing edge analysis on at least one identifiable edge; and

a data cell of the symbol is determined from the edge image for decoding the symbol to provide information encoded within the relief pattern of the symbol.

2. The method of claim 1, wherein the step of determining the presence of a discernible edge of the relief pattern comprises imaging the relief pattern of the symbol with an imaging device.

3. The method according to claim 1, wherein the step of validating comprises assigning a symbolic value representing the validity of the discernible edge to the intersection of the plurality of discernible edges.

4. A method according to claim 3, wherein the symbol values comprise numerical values.

5. The method according to claim 4, wherein the value assigned to the intersection of the plurality of discernible edges that represents the validity of the discernible edge is based on the number of discernible edges that form the intersection of the plurality of discernible edges.

6. The method according to claim 4, wherein the step of verifying comprises verifying the validity of the discernible edge based on a value assigned to a first intersection of discernible edges that includes the discernible edge to be verified.

7. The method according to claim 6, wherein the step of verifying further comprises verifying the validity of the distinguishable edges on the basis of a value assigned to a second intersection of distinguishable edges, the second intersection comprising the distinguishable edge to be verified.

8. The method according to claim 1, wherein the step of verifying comprises verifying the validity of the discernible edge by determining the number of discernible edges emanating from a first intersection of a plurality of discernible edges, the first intersection comprising the discernible edge to be verified.

9. The method according to claim 8, wherein the step of verifying further comprises verifying the validity of the discernible edges by determining the number of discernible edges that emanate from a second intersection of the plurality of discernible edges, the second intersection comprising the discernible edge to be verified and the second intersection being adjacent to the first intersection of the discernible edges.

10. A method according to claim 1, wherein the step of determining the data cells of the symbol from the edge image comprises assigning a binary value to at least one of the data cells to enable decoding of the symbol.

11. The method of claim 10, wherein the step of determining the data cells of the symbol from the edge image comprises scanning the edge image in a first direction to assign a binary value to at least one of the data cells.

12. The method of claim 11, wherein the step of determining the data cells of the symbol from the edge image further comprises scanning the edge image in a second direction to assign a binary value to at least one data cell scanned in the first direction.

13. The method of claim 12, wherein the columns are scanned in a top-to-bottom direction to assign a binary value to at least one data cell and scanned in a bottom-to-top direction to assign a binary value to at least one data cell.

14. The method of claim 13, wherein the plurality of binary values assigned to the at least one data cell are analyzed to determine a single binary value for the at least one data cell.

15. The method of claim 10 further comprising the step of decoding the edge image according to the assigned binary values to provide information encoded within the symbol.

16. An apparatus for reading a feature of a symbol in accordance with a relief pattern having a two-dimensional matrix of data elements representing encoded information, the apparatus comprising:

means for detecting the reflected light pattern and creating an edge image from the reflected light from the relief pattern, the edge image at least partially representing a two-dimensional matrix data element; and

means for verifying the validity of the discernible edge of the edge image and determining the data cell of the symbol from the relief pattern for decoding the symbol to provide the information encoded within the relief pattern.

17. The apparatus of claim 16, as part of a system comprising a light source capable of at least partially illuminating the relief pattern so that the at least one discernible edge can be read.