Method for locating and decoding distorted two-dimensional matrix symbols

• US 8,270,749 B2
• Filed: 06/20/2011
• Issued: 09/18/2012
• Est. Priority Date: 06/25/2005
• Status: Active Grant

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Nadabar, Sateesh, Ye, Xiangyun
• Primary Examiner(s): Cunningham, Gregory F
• Application Number:
  US13/164,216
• Publication Number:
  US 20110268361A1
• Time in Patent Office: 456 Days
• Field of Search: 731/56, 345/611, 345/687, 348/252, 348/405.1, 348/408.1, 348/606, 348/625, 358/3.27, 358/426.03, 358/426.04, 358/405, 358/532, 382/205, 382/254, 382/263, 382/264, 700/73, 708/136
• US Class Current: 382/254
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation

Abstract

A method is presented for processing an image of a two-dimensional (2D) matrix symbol having a plurality of data modules and a discontinuous finder pattern, each distorted by “donut effects”. A resulting processed image contains an image of the 2D matrix symbol having a continuous finder pattern suitable for conventional 2D matrix symbol locating techniques, and having a plurality of data modules, each data module having a center more truly representative of intended data, and suitable for conventional 2D matrix symbol sampling and decoding. The method includes sharpening the distorted image of the 2D matrix symbol to increase a difference between low frequency and high frequency image feature magnitudes, thereby providing a sharpened image, and smoothing the sharpened image using a moving window over the sharpened image so as to provide a smoothed image, the moving window and a module of the 2D matrix code being of substantially similar size.

Claims

1. A method for processing an image of a two-dimensional (2D) matrix symbol having a plurality of data modules and a discontinuous finder pattern, each distorted by “

donut effects”

such that a resulting processed image contains an image of the 2D matrix symbol having a continuous finder pattern suitable for conventional 2D matrix symbol locating techniques, and having a plurality of data modules, each data module having a center more truly representative of intended data, and suitable for conventional 2D matrix symbol sampling and decoding, the method comprising;

at least one processor programmed to;

sharpen the distorted image of the 2D matrix symbol so as to increase a difference between low frequency image feature magnitudes and high frequency image feature magnitudes, thereby providing a sharpened image; and

smooth the sharpened image using a moving window over the sharpened image so as to provide a smoothed image, the moving window and a module of the 2D matrix code being of substantially similar size.

2. The method of claim 1, wherein the moving window visits a plurality of module locations.

3. The method of claim 1, wherein the moving window visits a plurality of pixel locations.

4. The method of claim 1, wherein the moving window visits a plurality of sub-pixel locations.

5. The method of claim 1, wherein sharpening includes:

using a Sobel gradient magnitude operator.

6. The method of claim 1, wherein sharpening includes:

using one of a Laplacian filter;

a Mexican hat filter;

a Roberts gradient magnitude operator;

a Difference-of-Gaussian filter;

a Rank Filter; and

a Top-hat filter.

7. The method of claim 1, wherein smoothing the sharpened image using a moving window includes:

applying a weighted smoothing function within the moving window.

8. The method of claim 7, wherein the weighted smoothing function is a Gaussian function.

9. The method of claim 1, wherein smoothing the sharpened image using a moving window includes:

applying an average smoothing function within the moving window.

10. The method of claim 1, wherein smoothing the sharpened image using a moving window includes:

morphological dilation.

11. The method of claim 1, wherein smoothing the sharpened image using a moving window includes:

morphological dilation, followed by morphological erosion.

12. The method of claim 1, wherein smoothing the sharpened image using a moving window includes:

Median filtering.

13. The method of claim 1, wherein the Gaussian function of the moving window is sized such that the sigma of the Gaussian function is one sixth of one less than a size of a module.

14. The method of claim 1, wherein the moving window is sized such that, at a center of a “

donut effect”

ring that is substantially equal in size to a module size, a magnitude of the smoothed image at the center will be sufficient for correct sampling and decoding.

15. The method of claim 1, further comprising:

prior to sharpening, removing noise so as to improve signal-to-noise-ratio.

16. The method of claim 15, wherein removing noise includes:

applying a smoothing filter to the image of a 2D matrix code.

17. The method of claim 16, wherein the smoothing filter is a kernel of a size that is substantially smaller with respect to a module of the 2D matrix code.

18. The method of claim 15, wherein removing noise includes at least one of:

Gaussian smoothing, weighted smoothing, average smoothing, and median filtering.

19. The method of claim 1, further comprising:

amplifying the sharpened image so as to increase contrast in the sharpened image.

20. The method of claim 19, wherein amplifying the sharpened image includes:

multiplying each gray value of the sharpened image by a constant factor.

21. The method of claim 19, wherein amplifying the sharpened image includes:

histogram equalization.

22. The method of claim 19, wherein amplifying the sharpened image includes:

non-linear gray level mapping.

23. The method of claim 1, further comprising:

repeating the method at different resolutions so as to expand operating range over a variety of module sizes.

24. The method of claim 20, wherein retrying at different resolutions includes:

sub-sampling the image prior to repeating the method.

25. The method of claim 1, wherein the method is repeated so as to repeat smoothing the sharpened image using a moving window by using a moving window of a different size for each repetition of the method, if the module size is unknown.

26. The method of claim 1, wherein the “

donut”

effect refers to any imperfection in shape of a module that would prevent a module from contacting a neighboring module of the same polarity, and would result in module having a pixel value of a wrong polarity at its geometric center or its center-of-mass.

27. The method of claim 26, wherein imperfections in shape include:

donut shape, square ring, crescent, and oval.

28. A method for decoding a distorted image of a 2D matrix symbol, comprising:

At least one processor programmed to;

sharpen the distorted image of the 2D matrix symbol so as to increase a difference between low frequency image feature magnitudes and high frequency image feature magnitudes, thereby providing a sharpened image;

smooth the sharpened image using a moving window over the sharpened image so as to provide a smoothed image, the moving window and a module of the 2D matrix code being of substantially similar size; and

sample and decoding the 2D matrix symbol.

29. The method of claim 28, further comprising:

locating the 2D matrix symbol after preprocessing.

30. The method of claim 28, further comprising:

locating the 2D matrix symbol before preprocessing.

31. A method for verifying a 2D matrix symbol, comprising:

a processor programmed to;

sharpen an image of the 2D matrix symbol so as to increase a difference between low frequency image feature magnitudes and high frequency image feature magnitudes, thereby providing a sharpened image;

smooth the sharpened image using a moving window over the sharpened image so as to provide a smoothed image, the moving window and a module of the 2D matrix code being of substantially similar size;

sample and decode the 2D matrix symbol so as to provide decoded symbol, and a binary pattern of the decoded symbol; and

compare the binary pattern of the decoded symbol with an ideal pattern of the decoded symbol.