Method and apparatus for detecting artifact corners in two-dimensional images

• US 5,418,862 A
• Filed: 08/10/1992
• Issued: 05/23/1995
• Est. Priority Date: 08/10/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service of America (United Parcel Service Incorporated)
• Inventors: Zheng, Joe, Klancnik, Mihael
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/927,909
• Time in Patent Office: 1,016 Days
• Field of Search: 382/22, 235/462
• US Class Current: 382/199
• CPC Class Codes: G06K 7/1092 sensing by means of TV-scanning
• 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/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1469 using sub-pixel interpolation
• CPC Class Codes: G06K 7/1486 Setting the threshold-width for bar codes to be decoded
• CPC Class Codes: G06K 7/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

A system for finding a corner of an artifact in a two-dimensional pixel image selects an original seed pixel and generates a reference vector using the original seed pixel. The system selects a next seed pixel using the original seed pixel and generates a current vector using the next seed pixel. The system compares the current vector to the reference vector and selects a corner based on that comparison. Also a system for finding a corner of a bar code symbol in a two-dimensional pixel image selects a sequence of seed pixels, having a first seed pixel and a plurality of successive seed pixels, where each successive seed pixel is selected in accordance with the previous seed pixel in the sequence. The system generates a reference vector in accordance with the first seed pixel and generates a plurality of successive vectors, each in accordance with a successive seed pixel. The system compares the reference vector to each of the successive vectors and selects a corner in accordance with the comparison.

Claims

1. A method for detecting a corner of an artifact in a two-dimensional pixel image, comprising the steps of:

(a) selecting an original seed pixel;

(b) specifying the original seed pixel to be a current seed pixel;

(c) selecting a next seed pixel in accordance with the current seed pixel;

(d) specifying the next seed pixel to be the current seed pixel;

(e) implementing steps (c) and (d) a plurality of times to select a plurality of seed pixels;

(f) generating a reference vector in accordance with the original seed pixel and a seed pixel of the plurality of seed pixels;

(g) generating a plurality of vectors in accordance with the plurality of seed pixels;

(h) comparing each of the plurality of vectors to said reference vector; and

(i) detecting a corner in accordance with said comparison.

2. The method of claim 1, wherein step (h) comprises the step of determining the magnitude of the vector difference between said reference vector and each of the plurality of vectors and wherein step (i) comprises the step of comparing said magnitude to a threshold magnitude.

3. The method of claim 1, wherein step (h) comprises the step of determining the phase angle between said reference vector and each of the plurality of vectors and wherein step (i) comprises the step of comparing said phase angle to a threshold.

4. An apparatus for detecting a corner of an artifact in a two-dimensional pixel image, comprising:

(a) means for selecting an original seed pixel;

(b) means for specifying the original seed pixel to be a current seed pixel;

(c) seed pixel selecting means for selecting a next seed pixel in accordance with the current seed pixel;

(d) means for specifying the next seed pixel to be the current seed pixel;

(e) means for selecting a plurality of seed pixels using means (c) and (d);

(f) means for generating a reference vector in accordance with the original seed pixel and a seed pixel of the plurality of seed pixels;

(g) means for generating a plurality of vectors in accordance with the plurality of seed pixels;

(h) comparing means for comparing each of the plurality of vectors to said reference vector; and

(i) corner detecting means for detecting a corner in accordance with said comparison.

5. The apparatus of claim 4, wherein said comparing means determines the magnitude of the vector difference between said reference vector and each of the plurality of vectors and wherein said corner detecting means compares said magnitude to a threshold magnitude.

6. The apparatus of claim 4, wherein said comparing means determines the phase angle between said reference vector and each of the plurality of vectors and wherein said corner detecting means compares said phase angle to a threshold.

7. A method for detecting a corner of a bar code symbol in a two-dimensional pixel image, comprising the steps of:

(a) selecting a sequence of seed pixels, said sequence comprising a first seed pixel and a plurality of successive seed pixels, each successive seed pixel being selected in accordance with the previous seed pixel in said sequence;

(b) generating a reference vector in accordance with said first seed pixel and one of the plurality of successive seed pixels;

(c) generating a plurality of successive vectors, each successive vector being in accordance with at least two of the successive seed pixels;

(d) comparing said reference vector to each of said successive vectors;

(e) detecting a corner in accordance with said comparison.

8. The method of claim 7, wherein step (d) comprises the step of determining the magnitude of the vector difference between said reference vector and each of said successive vectors and wherein step (e) comprises the step of comparing said magnitude to a threshold magnitude.

9. The method of claim 7, wherein step (d) comprises the step of determining the phase angle between said reference vector and each of said successive vectors and wherein step (e) comprises the step of comparing said magnitude to a threshold.

10. An apparatus for detecting a corner of a bar code symbol in a two-dimensional pixel image, comprising:

(a) seed pixel selecting means for selecting a sequence of seed pixels, said sequence comprising a first seed pixel and a plurality of successive seed pixels, each successive seed pixel being selected in accordance with the previous seed pixel in said sequence;

(b) means for generating a reference vector in accordance with said first seed pixel and one of the plurality of successive seed pixels;

(c) means for generating a plurality of successive vectors, each successive vector being in accordance with at least two of said successive seed pixels;

(d) comparing means for comparing said reference vector to each of said successive vectors;

(e) corner detecting means for detecting a corner in accordance with said comparison.

11. The apparatus of claim 10, wherein said comparing means determines the magnitude of the vector difference between said reference vector and each of said successive vectors and wherein said corner selecting means compares said magnitude to a threshold magnitude.

12. The apparatus of claim 10, wherein said comparing means determines the phase angle between said reference vector and each of said successive vectors and wherein said corner selecting means compares said magnitude to a threshold.