# US 7,412,106 B1 · Methods for locating and decoding distorted two-dimensional matrix symbols

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,412,106 B1
- Document ID: US7412106B1
- Status: Granted
- Kind: B1
- Application number: 11/165,922
- Filed: 2005-06-25
- Granted: 2008-08-12
- Earliest claimed: 2005-06-25
- Assignees: Cognex Technology and Investment Corporation
- Inventors: Sateesha Nadabar; Xiangyun Ye
- Web page: https://patentgrep.com/patent/US7412106B1

## CPC

- G06K 19/06037: {multi-dimensional coding}
- G06V 10/34: Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
- G06K: GRAPHICAL DATA READING (image or video recognition or understanding G06V); PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## 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

### Claim 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:
sharpening 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
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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

The method of claim 1, wherein sharpening includes:
using a Sobel gradient magnitude operator.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

The method of claim 1, wherein smoothing the sharpened image using a moving window includes:
applying a weighted smoothing function within the moving window.

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 1)

The method of claim 1, wherein smoothing the sharpened image using a moving window includes:
applying an average smoothing function within the moving window.

### Claim 10 (depends on 1)

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

### Claim 11 (depends on 1)

The method of claim 1, wherein smoothing the sharpened image using a moving window includes:
morphological dilation, followed by morphological erosion.

### Claim 12 (depends on 1)

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

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 1)

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.

### Claim 15 (depends on 1)

The method of claim 1, further comprising:
prior to sharpening, removing noise so as to improve signal-to-noise-ratio.

### Claim 16 (depends on 15)

The method of claim 15, wherein removing noise includes:
applying a smoothing filter to the image of a 2D matrix code.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 15)

The method of claim 15, wherein removing noise includes at least one of:
Gaussian smoothing, weighted smoothing, average smoothing, and median filtering.

### Claim 19 (depends on 1)

The method of claim 1, further comprising:
amplifying the sharpened image so as to increase contrast in the sharpened image.

### Claim 20 (depends on 19)

The method of claim 19, wherein amplifying the sharpened image includes:
multiplying each gray value of the sharpened image by a constant factor.

### Claim 21 (depends on 19)

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

### Claim 22 (depends on 19)

The method of claim 19, wherein amplifying the sharpened image includes:
non-linear gray level mapping.

### Claim 23 (depends on 1)

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.

### Claim 24 (depends on 20)

The method of claim 20, wherein retrying at different resolutions includes:
sub-sampling the image prior to repeating the method.

### Claim 25 (depends on 1)

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.

### Claim 26 (depends on 1)

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.

### Claim 27 (depends on 26)

The method of claim 26, wherein imperfections in shape include:
donut shape, square ring, crescent, and oval.

### Claim 28

A method for decoding a distorted image of a 2D matrix symbol, comprising:
sharpening 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;
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; and
sampling and decoding the 2D matrix symbol.

### Claim 29 (depends on 28)

The method of claim 28, further comprising:
locating the 2D matrix symbol after preprocessing.

### Claim 30 (depends on 28)

The method of claim 28, further comprising:
locating the 2D matrix symbol before preprocessing.

### Claim 31

A method for verifying a 2D matrix symbol, comprising:
sharpening 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;
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;
sampling and decoding the 2D matrix symbol so as to provide decoded symbol, and a binary pattern of the decoded symbol; and
comparing the binary pattern of the decoded symbol with an ideal pattern of the decoded symbol.