Identifying and evaluating multiple rectangles that may correspond to a pallet in an image scene

• US 8,977,032 B2
• Filed: 10/16/2012
• Issued: 03/10/2015
• 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., Seelinger, Michael J., Yoder, John-David S.
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US13/652,563
• Publication Number:
  US 20130101203A1
• Time in Patent Office: 875 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 evaluating a possible pallet structure. The method comprises: providing a gray scale image comprising one or more possible lines; providing respective pixel locations in the gray scale image for an estimated upper left corner and an estimated upper right corner; calculating, using a computer, a value h based on the estimated upper left corner location and the estimated upper right corner location; estimating, using the computer, a first hole with a first rectangle having a height h; estimating, using the computer, a second hole with a second rectangle having the height h; and estimating, using the computer, the possible center stringer with a third rectangle having the height h.

Claims

1. A method for evaluating a possible pallet structure comprising:

providing a gray scale image comprising one or more possible lines;

providing respective pixel locations in the gray scale image for an estimated upper left corner of the possible pallet structure and an estimated upper right corner of the possible pallet structure;

calculating, using a computer, a value h based on the estimated upper left corner location and the estimated upper right corner location;

estimating, using the computer, a first hole with a first rectangle having a height h, the first hole corresponding to a left opening located to the left of a possible center stringer of the possible pallet structure;

estimating, using the computer, a second hole with a second rectangle having the height h, the second hole corresponding to a right opening located to the right of the possible center stringer; and

estimating, using the computer, the possible center stringer with a third rectangle having the height h.

2. The method of claim 1, wherein calculating the value h comprises calculating:

3. The method of claim 2,

wherein the first rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_11r and a y-coordinate y_11r, and a respective second endpoint, with an x-coordinate x_12r and a y-coordinate y_12r,

wherein the second rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_21r and a y-coordinate y_21r, and a respective second endpoint, with an x-coordinate x_22r and a y-coordinate y_22r,

wherein the third rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_31r and a y-coordinate y_31r, and a respective second endpoint, with an x-coordinate x_32r and a y-coordinate y_32r;

and

wherein r=an index value uniquely referring to one of the respective h lines in each of the first, second and third rectangles, the value of which ranges from 0 to (h−

1) with r=0 referring to a bottom-most of the h lines.

4. The method according to claim 3, further comprising:

for each pixel location in the h lines of the first rectangle, identifying a corresponding pixel value at that pixel location in the gray scale image in order to generate a first set of corresponding pixel values;

for each pixel location in the h lines of the second rectangle, identifying a corresponding pixel value at that pixel location in the gray scale image in order to generate a second set of corresponding pixel values;

for each pixel location in the h lines of the third rectangle, identifying a corresponding pixel value at that pixel location in the gray scale image in order to generate a third set of corresponding pixel values;

generating a first vertical projection of the first and second rectangles based on the first and second sets of corresponding pixel values;

generating a second vertical projection of the third rectangle based on the third set of corresponding pixel values; and

calculating a score value, Score_hole, based on the first and second vertical projections, which represents a likelihood that the third rectangle corresponds to an actual center stringer in the gray scale image, that the first rectangle corresponds to a first actual opening positioned to the left of the actual center stringer, and the second rectangle corresponds to a second actual opening positioned to the right of the actual center stringer.

5. The method of claim 4, wherein only negative pixel values in the first and second corresponding sets of pixel values are used to generate the first vertical projection.

6. The method of claim 4, wherein only negative pixel values in the third corresponding set of pixel values are used to generate the second vertical projection.

7. The method of claim 3, wherein the respective first and second endpoint coordinates for each of the h lines of the first rectangle are calculated according to:

x_11r=round(X_LLC−

leftWidth*cos(φ

_BPBL));

x_12r=X_LLC−

1;

y_11r=round((ρ

_BPBL−

r+x_11r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_11r=round((ρ

_BPBL−

r+x_12r*sin φ

_BPBL)/cos φ

_BPBL))

wherein;

X_LLC=an x-coordinate for the possible lower left corner through which the bottom pallet board line, L_BPB, passes;

8. The method according to claim 7, wherein the respective set of pixel locations for each of the h lines of the first rectangle is comprised of leftCount pixel locations, where leftCount=round(leftWidth*cos(φ

_BPBL)), the method further comprising;

calculating a first vertical projection of the first rectangle by;

providing a respective accumulator Y_ifor each of the leftCount pixel locations, where i is an index value uniquely referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the first rectangle, the value of i ranges from 1 to leftCount with i=1 referring to a left-most pixel location in the one of the h lines of the first rectangle; and

accumulating in each respective accumulator Y_ia sum according to;

9. The method of claim 8, wherein the respective first and second endpoint coordinates for each of the h lines in the second rectangle are calculated according to:

x_21r=X_LRC+1;

x_22r=round(X_LRC+rightWidth*cos(φ

_BPBL));

y_21r=round((ρ

_BPBL−

r+x_21r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_22r=round((ρ

_BPBL−

r+x_22r*sin φ

_BPBL)/cos φ

_BPBL))

wherein;

X_LRC=an x-coordinate for a possible lower right corner of the possible center stringer

10. The method according to claim 9, wherein the respective set of pixel locations for each of the h lines of the second rectangle is comprised of rightCount pixel locations, where rightCount=round(rightWidth*cos(φ

_BPBL)), the method further comprising;

calculating a second vertical projection of the second rectangle by;

providing a respective accumulator Y_i for each of the rightCount pixel locations, where i is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the second rectangle, the value of i ranges from (leftCount +1) to (leftCount +rightCount) with i=(leftCount +1) referring to a left-most pixel location in the one of the h lines of the second rectangle; and

accumulating in each respective accumulator Y_i a sum according to;

11. The method of claim 10, wherein the respective first and second endpoint coordinates for each of the h lines of the third rectangle are calculated according to:

x_31r=X_LLC;

x_32r=X_LRC;

y_31r=round((ρ

_BPBL−

r+x_31r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_32r=round((ρ

_BPBL−

r+x_32r*sin φ

_BPBL)/cos φ

_BPBL)).

12. The method according to claim 11, wherein the respective set of pixel locations for each of the h lines of the third rectangle is comprised of s pixel locations, wherein s=((X_LRC−

X_LLC)+1), the method further comprising;

calculating a third vertical projection of the third rectangle by;

providing a respective accumulator Z_j for each of the s pixel locations, where j is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the third rectangle, the value of j ranges from 1 to s with j=1 referring to a left-most pixel location in the one of the h lines of the third rectangle;

accumulating in each respective accumulator Z_j a sum according to;

13. The method according to claim 12, wherein:

14. A system for evaluating a possible pallet structure comprising:

an imaging camera configured to acquire a gray scale image comprising one or more possible lines;

a computer configured to execute instructions stored in an accessible memory;

the computer when executing instructions stored in the accessible memory;

identifies respective pixel locations in the gray scale image for an estimated upper left corner of the possible pallet structure and an estimated upper right corner of the possible pallet structure;

calculates a value h based on the estimated upper left corner location and the estimated upper right corner location;

estimates a first hole with a first rectangle having a height h, the first hole corresponding to a left opening located to the left of a possible center stringer of the possible pallet structure;

estimates a second hole with a second rectangle having the height h, the second hole corresponding to a right opening located to the right of the possible center stringer; and

estimates the possible center stringer with a third rectangle having the height h.

15. The system of claim 14, wherein the computer when executing instructions stored in the accessible memory calculates:

16. The system of claim 15,

wherein the first rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_11r and a y-coordinate y_11r, and a respective second endpoint, with an x-coordinate x_12r and a y-coordinate y_l2r,

wherein the second rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_21r and a y-coordinate y_21r, and a respective second endpoint, with an x-coordinate x_22r and a y-coordinate y_22r,

wherein the third rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_31r and a y-coordinate y_31r, and a respective second endpoint, with an x-coordinate x_32r and a y-coordinate y_32r;

and

wherein r=an index value uniquely referring to one of the respective h lines in each of the first, second and third rectangles, the value of which ranges from 0 to (h−

1) with r=0 referring to a bottom-most of the h lines.

17. The system according to claim 16, wherein the computer when executing instructions stored in the accessible memory:

identifies, for each pixel location in the h lines of the first rectangle, a corresponding pixel value at that pixel location in the gray scale image in order to generate a first set of corresponding pixel values;

identifies, for each pixel location in the h lines of the second rectangle, a corresponding pixel value at that pixel location in the gray scale image in order to generate a second set of corresponding pixel values;

identifies, for each pixel location in the h lines of the third rectangle, a corresponding pixel value at that pixel location in the gray scale image in order to generate a third set of corresponding pixel values;

generates a first vertical projection of the first and second rectangles based on the first and second sets of corresponding pixel values;

generates a second vertical projection of the third rectangle based on the third set of corresponding pixel values; and

calculates a score value, Score_hole, based on the first and second vertical projections, which represents a likelihood that the third rectangle corresponds to an actual center stringer in the gray scale image, that the first rectangle corresponds to a first actual opening positioned to the left of the actual center stringer, and the second rectangle corresponds to a second actual opening positioned to the right of the actual center stringer.

18. The system of claim 17, wherein only negative pixel values in the first and second corresponding sets of pixel values are used to generate the first vertical projection.

19. The system of claim 17, wherein only negative pixel values in the third corresponding set of pixel values are used to generate the second vertical projection.

20. The system of claim 16, wherein the respective first and second endpoint coordinates for each of the h lines of the first rectangle are calculated according to:

x_11r=round(X_LLC−

leftWidth*cos(φ

_BPBL));

x_12r=X_LLC−

1;

y_11r=round((ρ

_BPBL−

r+x_11r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_12r=round((ρ

_BPBL−

r+x_12r*sin φ

_BPBL)/cos φ

_BPBL))

wherein;

X_LLC=an x-coordinate for the possible lower left corner through which the bottom pallet board line, L_BPB, passes;

21. The system according to claim 20, wherein the respective set of pixel locations for each of the h lines of the first rectangle is comprised of leftCount pixel locations, where leftCount=round(leftWidth*cos(φ

_BPBL)), and the computer when executing instructions stored in the accessible memory;

calculates a first vertical projection of the first rectangle by;

providing a respective accumulator Y_i, for each of the leftCount pixel locations, where i is an index value uniquely referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the first rectangle, the value of i ranges from 1 to leftCount with i=1 referring to a left-most pixel location in the one of the h lines of the first rectangle; and

accumulating in each respective accumulator Y_i, a sum according to;

22. The system of claim 21, wherein the respective first and second endpoint coordinates for each of the h lines in the second rectangle are calculated according to:

x_21r=X_LRC+1;

x_22r=round(X_LRC+rightWidth*cos(φ

_BPBL));

y_21r=round((ρ

_BPBL−

r+x_21r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_22r=round((ρ

_BPBL−

r+x_22r*sin φ

_BPBL)/cos φ

_BPBL))

wherein;

X_LRC=an x-coordinate for a possible lower right corner of the possible center stringer

23. The system according to claim 22, wherein the respective set of pixel locations for each of the h lines of the second rectangle is comprised of rightCount pixel locations, where rightCount=round(rightWidth*cos(φ

BPBL)), and the computer when executing instructions stored in the accessible memory;

calculates a second vertical projection of the second rectangle by;

providing a respective accumulator Y_i for each of the rightCount pixel locations, where i is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the second rectangle, the value of i ranges from (leftCount +1) to (leftCount +rightCount) with i=(leftCount +1) referring to a left-most pixel location in the one of the h lines of the second rectangle; and

accumulating in each respective accumulator Y_ia sum according to;

24. The system of claim 23, wherein the respective first and second endpoint coordinates for each of the h lines of the third rectangle are calculated according to:

x_31r=X_LLC;

x_32r−

X_LRC;

y_31r=round((ρ

_BPBL−

r+x_31r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_32r=round((ρ

_BPBL−

r+x_32r*sin φ

_BPBL)/cos φ

_BPBL)).

25. The system according to claim 24, wherein the respective set of pixel locations for each of the h lines of the third rectangle is comprised of s pixel locations, wherein s=((X_LRC −

X_LLC)+1), and the computer when executing instructions stored in the accessible memory;

calculates a third vertical projection of the third rectangle by;

providing a respective accumulator Z_j for each of the s pixel locations, where j is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the third rectangle, the value of j ranges from 1 to s with j=1 referring to a left-most pixel location in the one of the h lines of the third rectangle;

accumulating in each respective accumulator Z_j a sum according to;

26. The system according to claim 25, wherein:

27. A computer program product for evaluating a possible pallet structure in a gray scale image comprising one or more possible lines, 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 identify respective pixel locations in the gray scale image for an estimated upper left corner of the possible pallet structure and an estimated upper right corner of the possible pallet structure;

computer readable program code configured to calculate a value h based on the estimated upper left corner location and the estimated upper right corner location;

computer readable program code configured to estimate a first hole with a first rectangle having a height h, the first hole corresponding to a left opening located to the left of a possible center stringer of the possible pallet structure;

computer readable program code configured to estimate a second hole with a second rectangle having the height h, the second hole corresponding to a right opening located to the right of the possible center stringer; and

computer readable program code configured to estimate the possible center stringer with a third rectangle having the height h.

28. The computer program product of claim 27, wherein the computer readable program code configured to calculate the value h is further configured to calculate:

29. The computer program product of claim 28,

wherein the first rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_11r and a y-coordinate y_11r, and a respective second endpoint, with an x-coordinate x_12r and a y-coordinate y_l2r,

wherein the second rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_21r and a y-coordinate y_21r, and a respective second endpoint, with an x-coordinate x_22r and a y-coordinate y_22r,

wherein the third rectangle comprises h lines, each line comprised of a respective set of pixel locations between, and including, a respective first endpoint, with an x-coordinate x_31r and a y-coordinate y_31r, and a respective second endpoint, with an x-coordinate x_32r and a y-coordinate y_32r;

and

wherein r=an index value uniquely referring to one of the respective h lines in each of the first, second and third rectangles, the value of which ranges from 0 to (h−

1) with r=0 referring to a bottom-most of the h lines.

30. The computer program product according to claim 29, further comprising:

computer readable program code configured to, for each pixel location in the h lines of the first rectangle, identify a corresponding pixel value at that pixel location in the gray scale image in order to generate a first set of corresponding pixel values;

computer readable program code t configured to, for each pixel location in the h lines of the second rectangle, identify a corresponding pixel value at that pixel location in the gray scale image in order to generate a second set of corresponding pixel values;

computer readable program code configured to, for each pixel location in the h lines of the third rectangle, identify a corresponding pixel value at that pixel location in the gray scale image in order to generate a third set of corresponding pixel values;

computer readable program code configured to generate a first vertical projection of the first and second rectangles based on the first and second sets of corresponding pixel values;

computer readable program code configured to generate a second vertical projection of the third rectangle based on the third set of corresponding pixel values; and

computer readable program code configured to calculate a score value, Score_hole, based on the first and second vertical projections, which represents a likelihood that the third rectangle corresponds to an actual center stringer in the gray scale image, that the first rectangle corresponds to a first actual opening positioned to the left of the actual center stringer, and the second rectangle corresponds to a second actual opening positioned to the right of the actual center stringer.

31. The computer program product of claim 30, wherein only negative pixel values in the first and second corresponding sets of pixel values are used to generate the first vertical projection.

32. The computer program product of claim 30, wherein only negative pixel values in the third corresponding set of pixel values are used to generate the second vertical projection.

33. The computer program product of claim 29, wherein the respective first and second endpoint coordinates for each of the h lines of the first rectangle are calculated according to:

x_11r=round(X_LLC−

leftWidth*cos φ

_BPBL));

x_12r=X_LLC−

1;

y_11r=round((ρ

_BPBL−

r+x_11r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_12r=round((ρ

_BPBL−

r+x_12r*sin φ

_BPBL)/cos φ

_BPBL))

wherein;

X_LLC=an x-coordinate for the possible lower left corner through which the bottom pallet board line, L_BPB, passes;

34. The computer program product according to claim 33, wherein the respective set of pixel locations for each of the h lines of the first rectangle is comprised of leftCount pixel locations, where leftCount=round(leftWidth*cos(φ

_BPBL)), the computer program product further comprising;

computer readable program code configured to calculate a first vertical projection of the first rectangle by;

providing a respective accumulator Y_i for each of the leftCount pixel locations, where i is an index value uniquely referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the first rectangle, the value of i ranges from 1 to leftCount with i=1 referring to a left-most pixel location in the one of the h lines of the first rectangle; and

accumulating in each respective accumulator Y_i a sum according to;

35. The computer program product of claim 34, wherein the respective first and second endpoint coordinates for each of the h lines in the second rectangle are calculated according to:

x_21r=X_LRC+1;

x_22r=round(X_LRC+rightWidth*cos(φ

_BPBL));

y_21r=round((ρ

_BPBL−

r+x_21r*sin φ

_BPBL/cos φ

_BPBL)), and

y_22r=round((ρ

_BPBL−

r+x_22r*sin φ

_BPBL/cos φ

_BPBL))

wherein;

X_LRC=an x-coordinate for a possible lower right corner of the possible center stringer

36. The computer program product according to claim 35, wherein the respective set of pixel locations for each of the h lines of the second rectangle is comprised of rightCount pixel locations, where rightCount=round(rightWidth*cos(φ

_BPBL)), the computer program product further comprising;

computer readable program code configured to calculate a second vertical projection of the second rectangle by;

providing a respective accumulator Y_i for each of the rightCount pixel locations, where i is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the second rectangle, the value of i ranges from (leftCount +1) to (leftCount +rightCount) with i=(leftCount +1) referring to a left-most pixel location in the one of the h lines of the second rectangle; and

accumulating in each respective accumulator Y_i a sum according to;

37. The computer program product of claim 36, wherein the respective first and second endpoint coordinates for each of the h lines of the third rectangle are calculated according to:

x_31r=X_LLC;

x_32r=X_LRC;

y_31r=round((ρ

_BPBL−

r+x_31r*sin φ

_BPBL)/cos φ

_BPBL)), and

y_32r=round((ρ

_BPBL−

r+x_32r*sin φ

_BPBL)/cos φ

_BPBL)).

38. The computer program product according to claim 37, wherein the respective set of pixel locations for each of the h lines of the third rectangle is comprised of s pixel locations, wherein s=((X_LRC−

X_LLC)+1), the computer program product further comprising;

computer readable program code configured to calculate a third vertical projection of the third rectangle by;

providing a respective accumulator Z_j for each of the s pixel locations, where j is an index value unique referring to a particular pixel location in the set of pixel locations that comprise one of the h lines of the third rectangle, the value of j ranges from 1 to s with j=1 referring to a left-most pixel location in the one of the h lines of the third rectangle;

accumulating in each respective accumulator Z_j a sum according to;

39. The computer program product according to claim 38, wherein: