Methods and systems for forming images of moving optical codes

• US 20060249581A1
• Filed: 05/03/2005
• Published: 11/09/2006
• Est. Priority Date: 05/03/2005
• Status: Active Grant

• Current Assignee: Datalogic Adc, Inc. (Datalogic S.p.A.)
• Original Assignee: Datalogic Scanning Incorporated (Datalogic S.p.A.)
• Inventors: Smith, Larry J.
• Granted Patent: US 7,383,994 B2
• Time in Patent Office: Days
• US Class Current: 235/454
• 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/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

Methods and systems form a decodable composite image of an optical code that experiences motion. A method according to one embodiment forms a first image of at least a first portion of the optical code at a first time and a second image of at least a second portion of the optical code at a second time, whereby the optical code may undergo relative motion between the first and second times. The method determines one or more of the following parameters of an affine transformation relating the second image to the first image: vertical offset, horizontal offset, horizontal skew factor, vertical skew factor, horizontal scale factor, and vertical scale factor. The method aligns one of the first and second images to the other by utilizing the determined parameters to implement the affine transformation, thereby forming an aligned image. Finally, the method combines elements of the aligned imaged and the other image to form the decodable composite image of the optical code.

Claims

1. A method for forming a decodable composite image of an optical code that experiences motion, the method comprising:

forming a first image of at least a first portion of the optical code at a first time;

forming a second image of at least a second portion of the optical code at a second time, whereby the optical code may undergo relative motion between the first time and the second time;

determining one or more of the following parameters of an affine transformation relating the second image to the first image;

vertical offset, horizontal offset, horizontal skew factor, vertical skew factor, horizontal scale factor, and vertical scale factor;

aligning one of the first and second images to the other of the first and second images by utilizing the determined parameters to implement the affine transformation, thereby forming an aligned image; and

combining elements of the aligned image and the other of the first and second images to form the decodable composite image of the optical code.

2. A method according to claim 1, wherein the optical code is a bar code.

3. A method according to claim 1, further comprising:

determining the orientation of the optical code.

4. A method according to claim 1, wherein forming the first image comprises illuminating the optical code from a first direction.

5. A method according to claim 4, wherein forming the second image comprises illuminating the optical code from a second direction different from the first direction.

6. A method according to claim 1, wherein the determining step comprises:

selecting at least one feature in the first image;

recognizing said at least one feature in the second image; and

determining the one or more parameters of the affine transformation based on the respective locations of said at least one feature in the first and second images.

7. A method according to claim 6, wherein the selecting step comprises:

computing cross correlations between regions of the first image and regions of the second image.

8. A method according to claim 7, wherein the regions are line segments.

9. A method according to claim 8, wherein the line segments lie along virtual scan lines.

10. A method according to claim 8, wherein the line segments are arranged in a rectangular pattern.

11. A method according to claim 8, wherein the optical code is a bar code having bars and spaces, and the line segments cross one or more bars and spaces.

12. A method according to claim 11, wherein the computing step comprises:

decoding the portions of the bar code along the line segments, so as to result in decoded bar code portions; and

computing cross correlations between the decoded bar code portions in the first and second images.

13. A method according to claim 6, wherein the number of features is at least three, and the features are non-colinear.

14. A method according to claim 1, wherein the determining step comprises:

solving for S an equation having substantially the form

$\left[\begin{array}{ccc}{x}_0& y_0& 1\\ x_1& y_1& 1\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}\\ x_p& y_p& 1\end{array}\right]=\left[\begin{array}{ccc}{x}_0^{\mathrm{\prime <br><br>}}& y_0^{\mathrm{\prime <br><br>}}& 1\\ x_1^{\mathrm{\prime <br><br>}}& y_1^{\mathrm{\prime <br><br>}}& 1\\ \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}& \mathrm{⋮<br><br>}\\ x_p^{\mathrm{\prime <br><br>}}& y_p^{\mathrm{\prime <br><br>}}& 1\end{array}\right]<br><br>S.$

where S is an affine transform matrix of a form

$S=\left[\begin{array}{ccc}{s}_3& s_1& s_5\\ s_2& s_4& s_6\\ 0& 0& 1\end{array}\right],$

and (x₀,y₀), (x₁,y₁), . . . , (x_p,y_p) are points in the first image, and (x′

₀,y′

₀), (x′

₁,y′

₁), . . . , (x′

_p,y′

_p) are points in the second image; and

computing one or more of the following;

$h_1=\frac{s_2<br><br>s_5-s_1<br><br>s_6}{s_2<br><br>s_3-s_1<br><br>s_4}$$h_2=\frac{s_3<br><br>s_6-s_4<br><br>s_5}{s_2<br><br>s_3-s_1<br><br>s_4}$$h_3=\frac{s_1}{s_3}$$h_4=\frac{s_3<br><br>s_4-s_1<br><br>s_6}{s_2<br><br>s_3-s_1<br><br>s_4}$$h_5=s_3$$h_6=\frac{s_2<br><br>s_3-s_1<br><br>s_4}{s_3}$

where h₁ represents the horizontal offset, h₂ represents the vertical offset, h₃ represents the horizontal skew factor, h₄ represents the vertical skew factor, h₅ represents the horizontal scale factor, and h₆ represents the vertical scale factor.

15. A method according to claim 1, wherein the horizontal offset is constrained to be zero.

16. A method according to claim 1, wherein the horizontal skew factor is constrained to be zero.

17. A method according to claim 1, wherein the horizontal scale factor is constrained to be one.

18. A method according to claim 1, wherein the vertical skew factor is constrained to be zero.

19. A method according to claim 1, wherein the vertical scale factor is constrained to be one.

20. A method according to claim 1, wherein the aligning step is performed by computing equations substantially of the form:

x=s₁y′

+s₃x′

+s₅
y=s₂y′

+s₄x′

+s₆

where (x,y) is a point in the aligned image, (x′

,y′

) is a point in the other of the first and second images, and S₁, S₂, S₃, S₄, S₅, and S₆ are parameters of the affine transformation.

21. A method according to claim 1, wherein the aligning step comprises:

shifting said one of the first and second images vertically by the vertical offset, so as to result in a vertically offset image;

shifting the vertically offset image horizontally by the horizontal offset and by amounts based on the horizontal skew factor, so as to result in a horizontally shifted image;

shifting the horizontally shifted image by amounts based on the vertical skew factor, so as to result in a vertically skewed image; and

scaling the vertically skewed image horizontally and vertically by the horizontal and vertical scale factors, respectively.

22. A method according to claim 1, wherein the first and second images are formed of pixels indexed horizontally and vertically in a rectangular pattern, and the aligning step comprises:

building a first table in which are stored horizontal pixel indices for use in performing the affine transformation, the first table having a column having entries of the form i+h₁+i*h₃, a column having entries of the form i+i*h₅, and a column having entries of the form i*h4, where i represents a horizontal pixel index;

building a second table in which are stored vertical pixel indices for use in performing the affine transformation, the second table having a column having entries of the form j+h₂, a column having entries of the form j+j*h₄, and a column having entries of the form j*h₆, where j represents a vertical pixel index; and

performing one or more table lookup operations into the first or second tables to implement the transformation.

23. A method according to claim 1, wherein the combining step comprises:

for each element of the composite image choosing the minimum of the corresponding elements from the aligned image and the other of the first and second images.

24. A system for forming a decodable composite image of an optical code that experiences motion, the system comprising:

means for forming a first image of at least a first portion of the optical code at a first time and for forming a second image of at least a second portion of the optical code at a second time after the first time, whereby the optical code may undergo motion between the first time and the second time;

means for determining one or more of the following parameters of an affine transformation relating the second image to the first image;

vertical offset, horizontal offset, horizontal skew factor, vertical skew factor, horizontal scale factor, and vertical scale factor;

means for aligning one of the first and second images to the other of the first and second images by utilizing the determined parameters to implement the affine transformation, thereby forming an aligned image; and

means for combining elements of the aligned image and the other of the first and second images to form the decodable composite image of the optical code.

25. A system for forming a decodable composite image of an optical code that experiences motion, the system comprising:

an imager having a field of view in which an optical code may be present, the imager forming a first image of at least a first portion of the optical code at a first time and a second image of at least a second portion of the optical code at a second time after the first time, whereby the optical code may undergo motion between the first time and the second time;

memory in which are stored the first image and the second image; and

a processor connected to the memory, the processor comprising;

a correlation module that computes one or more cross correlations between the first and second images, and based on the one or more cross correlations determines one or more of the following parameters of an affine transformation relating the second image to the first image;

vertical offset, horizontal offset, horizontal skew factor, vertical skew factor, horizontal scale factor, and vertical scale factor;

a transform module that implements the affine transformation so as to align one of the first and second images to the other of the first and second images thereby resulting in an aligned image; and

a combining module that combines elements of the aligned image and the other of the first and second images to form the decodable composite image of the optical code.

26. A system according to claim 25, further comprising:

a first light source positioned to one side of the imager, whereby the first light source illuminates the optical code for the first image; and

a second light source positioned to a side of the imager opposite said one side, whereby the second light source illuminates the optical code for the second image.

27. A system according to claim 25, wherein the imager is a camera.

28. A system according to claim 25, wherein the optical code is a bar code having a bars and spaces, and the cross correlations are taken over linear segments crossing one or more bars and spaces.

29. A system according to claim 25, wherein the transform module utilizes one or more lookup tables to implement the affine transformation.

30. A system according to claim 25, further comprising:

a lookup table comprising one or more columns indexed relative to a horizontal index i and having substantially the form;

ii + h₁i ·

h₄i ·

(1 + h₅)0h₁0011 + h₁h₄1 + h₅............m −

1m −

1 + h₁(m −

     1) ·

h₄(m −

     1) ·

(1 + h₅)

and a lookup table comprising one or more columns indexed relative to a horizontal index j and having substantially the form;

jj + h₂j ·

h₃j ·

(1 + h₆)0h₂0011 + h₂H₃1 + h₆............n −

1n −

1 + h₂(n −

     1) ·

h₃(n −

     1) ·

(1 + h₆)

where h₁ represents the horizontal offset, h₂ represents the vertical offset, h₃ represents the horizontal skew factor, h₄ represents the vertical skew factor, h₅ represents the horizontal scale factor, and h₆ represents the vertical scale factor.

31. A system according to claim 25, wherein the affine transform is constrained by one or more of the following conditions:

the horizontal offset is constrained to be zero, the horizontal skew factor is constrained to be zero, the horizontal scale factor is constrained to be one, the vertical skew factor is constrained to be zero, or the vertical scale factor is constrained to be one.

32. A method for forming a decodable composite image of an optical code that experiences motion, the method comprising:

forming a first image of at least a first portion of the optical code at a first time;

forming a second image of at least a second portion of the optical code at a second time, whereby the optical code may undergo relative motion between the first time and the second time;

computing one or more cross correlations between the first image and the second image;

determining, based on the one or more cross correlations, one or more parameters of a transformation mapping between the first and second images;

aligning one of the first and second images to the other of the first and second images by utilizing the determined parameters to implement the transformation, thereby forming an aligned image; and

combining elements of the aligned image and the other of the first and second images to form the decodable composite image of the optical code.

33. A method according to claim 32, wherein the transformation is an affine transformation.

34. A method for forming a decodable composite image of an optical code that experiences motion, the method comprising:

forming at least two images of at least portions of the optical code at different times;

determining one or more of the following parameters of an affine transformation relating the second image to the first image;

vertical offset, horizontal offset, horizontal skew factor, vertical skew factor, horizontal scale factor, and vertical scale factor;

predicting, based on the determined parameters, one or both of a location and orientation of the optical code at a future time;

forming an aligned image of at least a portion of the optical code at the future time, the aligned image being aligned to one of said at least two images based on the determined parameters; and

combining elements of the aligned image and the image formed at the future time to form the decodable composite image of the optical code.

35. A method according to claim 34, wherein the images are partial images along virtual scan lines.

36. A method according to claim 34, wherein forming the aligned image comprises:

forming an image of at least a portion of the optical code at the future time; and

aligning the image formed at the future time with one of said at least two images.

37. A method according to claim 34, wherein forming the aligned image comprises:

modifying a virtual scan line path to align with a feature in one of said at least two images; and

collecting image data along the modified virtual scan line path at the future time.