Identifying, evaluating and selecting possible pallet board lines in an image scene

• US 8,849,007 B2
• Filed: 10/16/2012
• Issued: 09/30/2014
• Est. Priority Date: 10/19/2011
• Status: Active Grant

• Current Assignee: Crown Equipment Corporation
• Original Assignee: Crown Equipment Corporation
• Inventors: Holeva, Lee F., Elston, Edwin R., Jensen, Eric L., Seelinger, Michael J.
• Primary Examiner(s): Mariam, Daniel
• Application Number:
  US13/652,534
• Publication Number:
  US 20130101202A1
• Time in Patent Office: 714 Days
• Field of Search: None
• US Class Current: 382/141
• CPC Class Codes: B66F 9/122 longitudinally movable
• CPC Class Codes: B66F 9/24 Electrical devices or systems
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A method is provided for determining which of a plurality of possible lines is most likely to be an actual line passing through a possible corner of a pallet. The method may comprise: providing a Ro image comprising pixels valued to generally correspond to an orthogonal distance from an origin point in the Ro image to one or more possible lines in a corresponding grey scale image; providing, using a computer, a location in the Ro image corresponding to a possible pallet corner; defining, using the computer, a plurality of possible lines passing through the possible pallet corner, each of the possible lines being respectively oriented at one angle within a range of angles to an axis of the Ro image; and determining, using the computer, which of the plurality of possible lines is most likely to be the actual line passing through the possible pallet corner.

Claims

1. A method for determining which of a plurality of possible lines is most likely to be an actual line passing through a possible corner of a pallet comprising:

providing a Ro image comprising pixels valued to generally correspond to an orthogonal distance from an origin point in the Ro image to one or more possible lines in a corresponding grey scale image;

providing, using a computer, a location in the Ro image corresponding to a possible pallet corner;

defining, using said computer, a plurality of possible lines passing through the possible pallet corner, each of the possible lines being respectively oriented at one angle within a range of angles to an axis of the Ro image; and

determining, using said computer, which of the plurality of possible lines is most likely to be the actual line passing through the possible pallet corner.

2. The method of claim 1, wherein the range of angles is centered about a horizontal axis in the Ro image.

3. The method of claim 1, wherein said defining comprises calculating an orthogonal distance from the origin point in the Ro image to each of the possible lines being respectively oriented at one angle from the following equation:

ρ

(φ

)=−

x_PalletCorner sin φ

+y_PalletCorner cos φ

wherein;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to a possible line at angle φ

;

φ

=one angle within the range of angles; and

x_PalletCorner, y_PalletCorner=coordinates in the Ro image for the possible pallet corner.

4. The method of claim 3, wherein said defining further comprises identifying points for each possible line using ρ

(φ

) calculated for that line.

5. The method of claim 4, wherein said identifying points for each possible line comprises generating respective first and second end points for a set of sub-lines {L} according to:

{L}={(1,y₁+k) to (M,y₂+k)}, where

k=0, 1, 2, . . . , (N_y−

1),

N_y=the number of sub-lines used to define the possible line; and

where;

6. The method of claim 5, wherein said identifying points for each possible line further comprises generating first and second intermediate points between each set of first and second sub-line end points using Bresenham'"'"'s line algorithm, wherein points for each possible line being defined by end and intermediate points of corresponding first and second sub-lines.

7. The method of claim 6, further comprising evaluating the following expression for each point on each possible line:

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

)

wherein;

(X,Y)=one of the points on a possible line;

ρ

_left(X,Y)=value from the Ro image at a point X,Y on the possible line;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to the possible line at angle φ

;

φ

=the one angle within the range of angles; and

TOL2=an empirically determined value.

8. The method of claim 7, further comprising, for each possible line, incrementing a respective counter each time the following expression is true for a point X, Y on the possible line:

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

)

9. The method of claim 8, further comprising identifying one of the possible lines having the greatest respective counter value as the line most likely to be an actual line passing through the possible pallet corner.

10. A system for determining which of a plurality of possible lines is most likely to be an actual line passing through a possible corner of a pallet comprising:

a computer configured to acquire a Ro image comprising pixels valued to generally correspond to an orthogonal distance from an origin point in the Ro image to one or more possible lines in a corresponding grey scale image;

said computer configured to provide a location in the Ro image corresponding to a possible pallet corner;

said computer further configured to define a plurality of possible lines passing through the possible pallet corner, each of the possible lines being respectively oriented at one angle within a range of angles to an axis of the Ro image; and

said computer further configured to determine which of the plurality of possible lines is most likely to be an actual line passing through the possible pallet corner.

11. The system of claim 10, wherein the range of angles is centered about a horizontal axis in the Ro image.

12. The system of claim 10, wherein to define a plurality of possible lines said computer is further configured to calculate an orthogonal distance from the origin point in the Ro image to each of the possible lines being respectively oriented at one angle from the following equation:

ρ

(φ

)=−

x_PalletCorner sin φ

+y_PalletCorner cos φ

wherein;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to a possible line at angle φ

;

φ

=one angle within the range of angles; and

x_PalletCorner, y_PalletCorner=coordinates in the Ro image for the possible pallet corner.

13. The system of claim 12, wherein to define a plurality of possible lines said computer is further configured to identify points for each possible line using p((p) calculated for that line.

14. The system of claim 13, wherein said computer is further configured to identify points for each possible line by generating respective first and second end points for a set of sub-lines {L} according to:

{L}={(1,y₁+k) to (M,y₂+k)}, where

k=0, 1, 2, . . . , (N_y−

1),

N_y=the number of sub-lines used to define the possible line; and

where;

15. The system of claim 14, wherein to identify points for each possible line said computer is further configured to generate first and second intermediate points between each set of first and second sub-line end points using Bresenham'"'"'s line algorithm, wherein points for each possible line being defined by end and intermediate points of corresponding first and second sub-lines.

16. The system of claim 15, wherein said computer is further configured to evaluate the following expression for each point on each possible line:

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

)

wherein;

(X,Y)=one of the points on a possible line;

ρ

_left(X,Y)=value from the Ro image at a point X,Y on the possible line;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to the possible line at angle φ

;

φ

=the one angle within the range of angles; and

TOL2=an empirically determined value.

17. The system of claim 16, wherein said computer is further configured, for each possible line, to increment a respective counter each time the following expression is true for a point X, Y on the possible line:

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

).

18. The system of claim 17, wherein said computer is further configured to identify one of the possible lines having the greatest respective counter value as the line most likely to be an actual line passing through the possible pallet corner.

19. A computer program product for determining which of a plurality of possible lines is most likely to be an actual line passing through a possible corner of a pallet, comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to acquire a Ro image comprising pixels valued to generally correspond to an orthogonal distance from an origin point in the Ro image to one or more possible lines in a corresponding grey scale image;

computer readable program code configured to provide a location in the Ro image corresponding to a possible pallet corner;

computer readable program code configured to define a plurality of possible lines passing through the possible pallet corner, each of the possible lines being respectively oriented at one angle within a range of angles to an axis of the Ro image; and

computer readable program code configured to determine which of the plurality of possible lines is most likely to be an actual line passing through the possible pallet corner.

20. The computer program product of claim 19, wherein the range of angles is centered about a horizontal axis in the Ro image.

21. The computer program product of claim 19, wherein the computer readable program code configured to define a plurality of possible lines, further comprises:

computer readable program code configured to calculate an orthogonal distance from the origin point in the Ro image to each of the possible lines being respectively oriented at one angle from the following equation;

ρ

(φ

)=−

x_PalletCorner sin φ

+y_PalletCorner cos φ

wherein;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to a possible line at angle φ

;

φ

=one angle within the range of angles; and

x_PalletCorner, y_PalletCorner=coordinates in the Ro image for the possible pallet corner.

22. The computer program product of claim 21, wherein the computer readable program code configured to define a plurality of possible lines, further comprises:

computer readable program code configured to identify points for each possible line using ρ

(φ

) calculated for that line.

23. The computer program product of claim 22, further comprising:

computer readable program code configured to identify points for each possible line by generating respective first and second end points for a set of sub-lines {L} according to;

{L}={(1,y₁+k) to (M,y₂+k)}, where

k=0, 1, 2, . . . , (N_y−

1),

N_y=the number of sub-lines used to define the possible line; and

where;

24. The computer program product of claim 23, wherein the computer readable program code configured to identify points for each possible line, further comprises:

computer readable program code configured to generate first and second intermediate points between each set of first and second sub-line end points using Bresenham'"'"'s line algorithm, wherein points for each possible line being defined by end and intermediate points of corresponding first and second sub-lines.

25. The computer program product of claim 24, further comprising:

computer readable program code configured to evaluate the following expression for each point on each possible line;

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

)

wherein;

(X,Y)=one of the points on a possible line;

ρ

_left(X,Y)=value from the Ro image at a point X,Y on the possible line;

ρ

(φ

)=an orthogonal distance from the origin point in the Ro image to the possible line at angle φ

;

φ

=the one angle within the range of angles; and

TOL2=an empirically determined value.

26. The computer program product of claim 25, further comprising:

computer readable program code configured to, for each possible line, to increment a respective counter each time the following expression is true for a point X, Y on the possible line;

|ρ

_left(X,Y)−

ρ

(φ

)|≦

TOL2*ρ

(φ

)

27. The computer program product of claim 26, further comprising:

computer readable program code configured to identify one of the possible lines having the greatest respective counter value as the line most likely to be an actual line passing through the possible pallet corner.