Non-linear image processing and automatic discriminating method and apparatus for images such as images of machine-readable symbols

• US 6,128,414 A
• Filed: 09/29/1997
• Issued: 10/03/2000
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Original Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Inventors: Liu, Lingnan
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US08/939,140
• Time in Patent Office: 1,100 Days
• Field of Search: 235/462-4, 382/182, 382/257, 382/266, 382/267, 382/268
• US Class Current: 382/266
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1452 detecting bar code edges

Abstract

A method and apparatus for locating geometric shapes or edges thereof in data collection symbols initially samples and stores an image of light reflected from the symbol. Thereafter, two routines are performed. A first routine performs low level vision processing by identifying linked points along edges, lines, curves or within shapes. At least one of three distortion compensating subroutines compensate for blocking, breaking, gaps or other severe distortions affecting shapes in the stored image. Under a first subroutine, an edge of a shape is tracked until a stopping condition occurs, at which point the shape is crossed so as to continue tracking on an opposite edge. Under a second subroutine, previously collected linear curve information is used to identify a jump point to continue tracking following a stopping condition. Under a third subroutine, mathematical morphology techniques are employed to close gaps or move blockage in shapes in the stored image. Coordinates of linked points, which represent lines, curves and other geometric shapes, from the first routine are then employed by a second routine which identifies patterns within the identified lines/curves. Based on these identified patterns, types of symbols from various symbologies can be identified and located within the stored image.

Claims

1. In a symbol reading apparatus capable of storing an image of a data collection symbol, the stored image being comprised of a plurality of pixels and the symbol having a predetermined pattern of geometric shapes, a method of locating portions of the shapes within the stored image, the method comprising:

sequentially identifying adjacent pixels along an edge of a shape within the stored image;

performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines if an adjacent pixel cannot be located due to a distortion, wherein the at least one distortion compensating subrouting is selected from a first subroutine that crosses the shape to identify another edge of the shape, a second subroutine that jumps over the distortion, in a direction corresponding to an orientation of the edge, to identify an edge point on the edge following the distortion and without filling in the adjacent pixel, and a third subroutine that morphologically alters the distortion to cross the distortion and identify an edge point on the edge following the distortion;

continuing sequentially identifying adjacent pixels following the distortion;

producing a set of pixels that identify at least a portion of the shape based on the sequentially identifying, performing and continuing;

determining if the set of pixels contains representations of one of several selected patterns of geometric portions for corresponding data collection symbology types, a first selected pattern corresponding to the predetermined pattern of geometric shape of the data collection symbol and which does not represent widths of a plurality of shapes as measured along an intersecting sampling path; and

identifying the data collection symbol in the stored image if the detected geometric portions correspond to the first selected pattern.

2. The method of claim 1 wherein the performing at least one distortion compensating subroutine includes:

determining the orientation of the edge;

crossing the shape in a direction approximately equal to plus or minus 90 degrees from the edge orientation; and

identifying an edge point of the another edge following crossing the shape.

3. The method of claim 1 wherein performing at least one distortion compensating subroutine includes:

determining the orientation of the edge;

jumping a selected amount in a direction approximately equal to the edge orientation; and

identifying an edge point of the edge following jumping the selected amount.

4. The method of claim 1 wherein performing at least one distortion compensating subroutine includes:

determining the orientation of the edge;

sampling a selected number of pixels through the distortion in a direction approximately equal to the edge orientation to produce a one dimensional sampled signal;

morphologically dilating the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying an edge point of the edge following morphologically dilating.

5. The method of claim 1 wherein performing at least one distortion compensating subroutine includes:

determining the orientation of the edge;

sampling a selected number of pixels through the distortion in a direction approximately equal to the edge orientation to produce a one dimensional sampled signal;

morphologically closing the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying an edge point of the edge following morphologically closing.

6. The method of claim 1 wherein performing at least one distortion compensating subroutine includes:

sampling a selected number of pixels through the distortion to produce a two dimensional sampled image;

morphologically dilating the two dimensional sampled image based on a two dimensional structuring image element; and

identifying an edge point of the edge following the step of morphologically dilating.

7. The method of claim 1 wherein performing at least one distortion compensating subroutine includes identifying a second order curve fitting the sequentially identified adjacent pixels along the edge of the shape.

8. The method of claim 1 wherein determining if the set of pixels contains representations includes:

determining if the set of pixels contains at least two parallel lines, and if so, determining that the data collection symbol is a Code One symbol;

determining if the set of pixels contains at least two lines having ends intersecting at approximately 90 degrees, and if so, determining that the data collection symbol is a Data Matrix symbol; and

determining if the set of pixels contains at least a partially enclosed curve, and if so, determining that the data collection symbol is a MaxiCode symbol.

9. A computer implemented method of locating an image of machine-readable visual indicia in a stored image, the stored image being represented by a plurality of points and the machine-readable visual indicia having a predetermined pattern of geometric shapes, the method comprising:

compensating for at least partial breakage for at least one of the geometric shapes in the stored image and compensating for at least partial blockage for at least another of the geometric shapes in the stored image;

detecting a set of curves in the stored image based on groups of points in the plurality of points, wherein each group of points corresponds to one of the curves and wherein at least some of the curves in the set of curves represent at least portions of the geometric shapes of the predetermined pattern;

determining if curves in the set of curves correspond to one of several selected patterns of curves for corresponding data collection symbology types, wherein a first selected pattern corresponds to the predetermined pattern of geometric shapes of the machine-readable visual indicia and does not represent widths of a plurality of shapes as measured along an intersecting sampling path; and

identifying the machine-readable visual indicia in the stored image if curves in the set curves correspond to the first selected pattern.

10. The method of claim 9 wherein detecting a set of curves includes sequentially identifying adjacent points through a middle of at least some of the geometric shapes within the stored image, and wherein at least some of the curves in the set of curves are lines corresponding to identified points through the middle of the geometric shapes of the predetermined pattern.

11. The method of claim 9 wherein compensating includes:

sequentially identifying adjacent points along an edge of at least some of the geometric shapes within the stored image; and

performing at least one distortion compensating subroutine if an adjacent point cannot be located due to the breakage or blockage, wherein the at least one distortion compensating subroutine is selected from a first subroutine that crosses the visual indicia to identify another edge of the geometric shapes, a second subroutine that jumps over the breakage or blockage to identify an edge point following the breakage or blockage, and a third subroutine that morphologically alters the breakage or blockage to cross the breakage or blockage and identify an edge point following the breakage or blockage.

12. The method of claim 9 wherein the machine-readable visual indicia is a Code One symbol, and wherein determining if curves in the set of curves correspond to one of several selected patterns of curves includes the step of determining if the detected set of curves contains the first pattern, wherein the first pattern includes at least two parallel lines.

13. The method of claim 9 wherein the machine-readable visual indicia is a Data Matrix symbol, and wherein determining if curves in the set of curves correspond to one of several selected patterns of curves includes determining if the detected set of curves contains the first pattern, wherein the first pattern includes at least two lines intersecting at approximately 90 degrees.

14. The method of claim 9 wherein the machine-readable visual indicia is a MaxiCode symbol, and wherein determining if curves in the set of curves correspond to one of several selected patterns of curves includes the step of determining if the detected set of curves contains the first pattern, wherein the first pattern includes at least a partially enclosed curve.

15. A computer implemented method of analyzing an image of machine-readable visual indicia in a stored image, the stored image being represented by a plurality of pixels, and the machine-readable visual indicia having an arrangement of geometric shapes representing information, the method comprising:

sequentially identifying adjacent pixels along an edge or within a middle of a shape within the stored image;

recognizing that the shape suffers from a distortion of the shape in the stored image;

determining an orientation of the shape;

crossing the shape in a direction approximately equal to plus or minus 90 degrees from the determined orientation following recognizing that the shape suffers from a distortion, and without filling in missing adjacent pixels in this shape;

identifying an edge point of the another edge following crossing the shape; and

determining if the shape corresponds to one of several selected patterns of shapes for corresponding machine-readable visual indicia types, a first selected pattern corresponding to a predetermined pattern of geometric shapes of the machine-readable visual indicia, and which does not represent widths of a plurality of shapes as measured along an intersecting sampling path.

16. The method of claim 15 wherein the image of machine-readable visual indicia is an image of a bar code symbol, and wherein crossing includes crossing a bar suffering from the distortion.

17. The method of claim 15 wherein recognizing includes identifying a second order curve fitting the sequentially identified adjacent pixels.

18. A computer implemented method of analyzing an image of a data collection symbol in a two-dimensional stored image, the two-dimensional stored image being represented by a plurality of points and the data collection symbol having a pattern of geometric shapes and spaces encoding information, the method comprising:

sequentially identifying adjacent points along an edge of or within a geometric shape in the stored image;

determining an orientation of the edge of the geometric shape;

identifying a distortion with respect to the edge or the geometric shape and jumping a selected amount in a direction approximately equal to the determined orientation, and without filling in adjacent points;

identifying a point of the edge or within the geometric shape following the jumping; and

determining if the geometric shape corresponds to one of several selected patterns of shapes for corresponding data collection symbology types, a first selected pattern that corresponds to a predetermined pattern of geometric shapes for the two-dimensional stored image of the data collection symbol and which does not represent widths of a plurality of geometric shapes as measured along an intersecting sampling path.

19. The method of claim 18 wherein jumping includes;

determining an X dimension of the symbol; and

jumping the selected amount, wherein the selected amount corresponds to the X dimension of the symbol multiplied by a value greater than one.

20. The method of claim 18 wherein determining includes identifying a second order curve fitting the sequentially identified adjacent pixels.

21. The method of claim 18 wherein determining includes determining that the orientation of the shape is curved, and wherein jumping includes jumping a selected arc length.

22. A computer implemented method of analyzing an image of a data collection symbol in a two-dimensional stored image, the two-dimensional stored image being represented by a plurality of points and the data collection symbol having a predetermined pattern of spaces and geometric shapes encoding information, the method comprising:

detecting a distortion in the stored image, the distortion affecting at least one of the shapes of the data collection symbol;

performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines, wherein at least one of the subroutines includes applying at least one morphological technique to alter the distortion;

analyzing the stored image following the applying, and producing a set of points that identify at least a portion of the shape based on the detecting, applying and analyzing; and

determining if the set of points contains representations of one of several selected patterns of geometric portions for corresponding data collection symbology types, a first selected pattern corresponding to a finder pattern of geometric shapes of the data collection symbol and which does not represent widths of a plurality of shapes as measured along an intersecting sampling path.

23. The method of claim 22 wherein applying includes:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the determined orientation to produce a one dimensional sampled signal;

morphologically dilating the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically dilating.

24. The method of claim 22 wherein applying includes:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the detected orientation to produce a one dimensional sampled signal;

morphologically closing the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically closing.

25. The method of claim 22 wherein applying includes:

sampling a selected number of points through the distortion to produce a two dimensional sampled image;

morphologically dilating the two dimensional sampled image based on a two dimensional structuring image element; and

identifying a point of the affected shape following morphologically dilating.

26. The method of claim 22 wherein applying includes:

sequentially identifying adjacent points along an edge of the affected shape within the stored image until the distortion is detected; and

applying the at least one morphological technique to cross the distortion and identify an edge point on the edge following the distortion.

27. The method of claim 22 wherein detecting includes determining whether the at least one shape suffers from a complete breakage formed therethrough.

28. A computer-readable medium storing a computer implementable method for analyzing a stored image comprised of a plurality of points, the method comprising:

detecting a distortion in the stored image, wherein the stored image includes an image of a data collection symbol having a plurality of shapes and spaces encoding information, and wherein the distortion affects at least one of the shapes of the data collection symbol;

performing at least one distortion compensating subroutine selected from a plurality of distortion compensating subroutines, wherein at least one of the distortion compensating subroutines includes applying at least one morphological technique to alter the distortion; and

analyzing the stored image following applying, and producing a set of points that identify at least a portion of the at least one of the shapes based on the detecting, applying and analyzing; and

determining if the set of points contains representations of one of several selected patterns of geometric portions for corresponding data collection symbology types, wherein a first selected pattern corresponds to a finder pattern of geometric shapes of the data collection symbol and does not represent widths of a plurality of shapes as measured along an intersecting sampling path.

29. The computer-readable medium of claim 28 wherein applying includes:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the determined orientation to produce a one dimensional sampled signal;

morphologically dilating the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically dilating.

30. The computer-readable medium of claim 28 wherein applying includes:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the detected orientation to produce a one dimensional sampled signal;

morphologically closing the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically closing.

31. The computer-readable medium of claim 28 wherein applying includes:

sampling a selected number of points through the distortion to produce a two dimensional sampled image;

morphologically dilating the two dimensional sampled image based on a two dimensional structuring image element; and

identifying a point of the affected shape following morphologically dilating.

32. The computer-readable medium of claim 28 wherein applying includes:

sequentially identifying adjacent points along an edge of the affected shape within the stored image until the distortion is detected; and

applying the at least one morphological technique to cross the distortion and identify an edge point on the edge following the distortion.

33. The computer-readable medium of claim 28 wherein detecting includes determining whether the at least one shape suffers from a complete breakage formed therethrough.

34. An apparatus for analyzing machine-readable visual indicia, the apparatus comprising:

an image sensor that receives light reflected form the machine-readable visual indicia and that produces an image signal therefrom that represents the machine-readable visual indicia, the machine-readable visual indicia having a pattern of geometric shapes;

a storage device for storing the image signal as a plurality of points; and

at least one processor, coupled to the image sensor and the storage device, that (a) detects a distortion in the stored image, the distortion affecting at least one of the shapes of the machine-readable visual indicia, (b) selects and performs at least one distortion compensating process selected from a plurality of distortion compensating processes, wherein the selected distortion compensating process applies at least one morphological technique to alter the distortion, (c) analyzes the stored image following applying at least one morphological technique, and producing a set of points that identify at least a portion of the at least one of the shapes based on the detecting, applying and analyzing; and

(d) determines if the set of points contains representations of one of several selected patterns of geometric portions for corresponding machine-readable visual indicia types, a first selected pattern corresponding to a finder pattern of the machine-readable visual indicia and which does not represent widths of a plurality of shapes as measured along an intersecting sampling path.

35. The apparatus of claim 34 wherein the at least one processor sequentially identifies adjacent points along an edge of at least some of the visual indicia within the stored image signal, and wherein at least some of the curves in the set of curves are lines corresponding to detected edges of the geometric shapes.

36. The apparatus of claim 34 wherein the processor is programmed for:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the determined orientation to produce a one dimensional sampled signal;

morphologically dilating the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically dilating.

37. The apparatus of claim 34 wherein the processor is programmed for:

determining an orientation of the affected shape;

sampling a selected number of points through the distortion in a direction approximately equal to the detected orientation to produce a one dimensional sampled signal;

morphologically closing the one dimensional sampled signal based on a one dimensional structuring signal; and

identifying a point of the affected shape following morphologically closing.

38. The apparatus of claim 34 wherein the processor is programmed for:

sampling a selected number of points through the distortion to produce a two dimensional sampled image;

morphologically dilating the two dimensional sampled image based on a two dimensional structuring image element; and

identifying a point of the affected shape following morphologically dilating.

39. The apparatus of claim 34 wherein the processor:

sequentially identifies adjacent points along an edge of the affected shape within the stored image until the distortion is detected; and

applies the at least one morphological technique to cross the distortion and identify an edge point on the edge following the distortion.