Overhead dimensioning system and method

• US 7,277,187 B2
• Filed: 07/01/2002
• Issued: 10/02/2007
• Est. Priority Date: 06/29/2001
• Status: Expired due to Fees

• Current Assignee: Quantronix Incorporated
• Original Assignee: Quantronix Incorporated
• Inventors: Smith, Lyndon, Carlsruh, Eve, Smith, Melvyn Lionel
• Primary Examiner(s): Nguyen; Sang H.
• Application Number:
  US10/482,063
• Publication Number:
  US 20040240754A1
• Time in Patent Office: 1,919 Days
• Field of Search: 356601-625, 356627-628, 356634-636, 356/640, 356/3.1, 356/4.08, 382/141, 382170-172, 382/190, 382/103, 702/152, 250/559.22, 340/928, 235/384
• US Class Current: 356/601
• CPC Class Codes: G01B 11/00 Measuring arrangements characterised by the use of optical techniques
• CPC Class Codes: G01B 11/024 by means of diode-array scanning
• CPC Class Codes: G01B 11/25 by projecting a pattern, e.g. one or more lines, moiré fringes on the object G01B11/255 takes precedence ; image analysis for depth or shape recovery G06T7/50
• CPC Class Codes: G06T 7/521 from laser ranging, e.g. using interferometry; from the projection of structured light

Abstract

A system and method for dimensioning large or palletized freight of one or more pieces determines the dimensions of a rectangular prism having the smallest volume which would contain the freight. The system is capable of being positioned remotely from the freight. The system is further configured to determine the dimensions in varying levels of ambient light and varying object surface reflectance. The system still further is configured to first rapidly scan an area to determine the general location of the boundaries of the freight and then more precisely scan the determined general boundaries of the freight to determine the precise boundaries of the freight.

Claims

1. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

utilizing a second laser and a second camera to determine an approximate location and a dimension of the at least one item;

acquiring a second set of point cloud data by utilizing the second laser to transmit a second signal over the at least one item and utilizing the second camera to receive a reflection of the second signal;

acquiring a third set of point cloud data by utilizing the second camera to receive the reflection of the first signal;

constructing a three-dimensional image that defines the at least one item by merging the acquired first, second and third sets of point cloud data; and

determining a rectangular prism having a height, length and breadth to contain the constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

2. The method of claim 1, further comprising:

acquiring a fourth set of point cloud data by utilizing the first camera to receive the reflection of the second signal; and

constructing the three-dimensional image that defines the at least one item by merging the acquired first, second, third, and fourth sets of point cloud data.

3. The method of claim 1, further comprising:

transforming the constructed image to a global coordinate system.

4. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data;

compensating for lens distortion of the constructed three-dimensional image comprising utilizing a pixel point correction value in cooperation with the acquired first set of point cloud data to adjust a location of each pixel point affected by radial lens distortion, the pixel point correction value being developed at least in part by;

providing a pixel value for a pixel within the measurement space;

acquiring a scanned pixel value by utilizing the first laser to transmit the first signal over the measurement space and utilizing the first camera to receive a reflection off a pixel of the first signal;

comparing the pixel value with the scanned pixel value; and

generating a pixel correction value in response to the comparison; and

determining a rectangular prism having a height, length, width and breadth and, as compensated for lens distortion, to contain the constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

5. The method of claim 4, further comprising:

storing the pixel correction value in a calibration lookup table, wherein the pixel correction value can be utilized during construction of the three-dimensional image.

6. The method of claim 4, further comprising:

utilizing the pixel correction value to generate an equation for correcting distortions.

7. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data;

reducing noise from the image utilizing image subtraction by;

acquiring a first image that represents the at least one item by utilizing the first laser to transmit the first signal over the measurement space and utilizing the first camera to receive the reflection of the first signal;

acquiring a second image that represents the at least one item by utilizing the first laser to transmit the first signal over the measurement space and utilizing the first camera to receive the reflection of the first signal;

subtracting the second image from the first image to produce a gray-level image; and

utilizing the gray-level image as a threshold value for providing a binary image; and

determining a rectangular prism having a height, length and breadth to contain the constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

8. The method of claim 7, wherein reducing noise comprises:

determining a median pixel value for a predetermined area surrounding a pixel; and

setting each pixel to its respective median pixel value.

9. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data;

reducing noise from the image, comprising;

computing a spatial histogram of the point cloud data in a vertical direction;

computing a spatial histogram of the point cloud data in a horizontal direction;

grouping points having a spatially detached value;

comparing an amount of points in a grouping against a predetermined value;

identifying each grouping having a lesser amount of points than the predetermined value; and

removing each identified grouping; and

determining a rectangular prism having a height, length and breadth to contain the constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

10. The method of claim 9, wherein reducing noise further comprises:

computing the vertical spatial histogram from rotation of the point cloud data in an x-plane; and

computing the horizontal spatial histogram from rotation of the point cloud data in a y-plane.

11. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data;

reducing noise from the image, comprising;

identifying points in a point cloud, each point having a height;

grouping the points by the height of each point;

comparing an amount of points in each grouping against a predetermined value;

identifying each grouping having a lesser amount of points than the predetermined value; and

removing each identified grouping; and

determining a rectangular prism having a height, length and breadth to contain the constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

12. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data;

reducing noise from the image, comprising;

identifying a position of each disjoint point in a measurement array;

comparing a height value of each disjoint point against a height value of a surrounding signal; and

removing each disjoint point not matching the height value of the surrounding signal; and

determining a rectangular prism having a height, length and breadth to contain the constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

13. A method for determining the dimensions of at least one item place within a measurement space, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data including utilizing a point threshold in cooperation with the image during construction of the image; and

determining a rectangular prism having a height, length and breadth to contain the constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

14. The method of claim 13, further comprising:

identifying a gray-scale value for each acquired point;

utilizing each identified point to determine a statistical property of the gray-scale value; and

defining the point threshold in response to the determined statistical property of the gray-scale value.

15. The method of claim 13, further comprising:

providing a group of point threshold values from which to select the point threshold.

16. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data; and

determining a rectangular prism to contain the constructed image, the rectangular prism having a height, length, and breadth, wherein determining comprises;

determining dimensions of the rectangular prism by rotating a coordinate frame about a centroid of the constructed image through a plurality of angular increments;

measuring a distance from the centroid to an edge of the at least one item for each angular increment;

storing each measurement;

identifying a length measurement and a breadth measurement; and

selecting a single length measurement and a single breadth measurement, wherein the selected measurements, in combination with a determined height of the at least one item, comprise dimensions of a rectangular prism having the smallest volume which would contain the at least one item.

17. A method for determining the dimensions of at least one item, the method comprising:

determining an approximate location and extent of at least one item;

acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal, wherein acquiring a first set of point cloud data comprises;

coarsely transmitting the first signal in a first direction at an off-center location within the measurement space;

identifying a first edge of the at least one item;

finely transmitting the first signal in a second direction over the first edge, the second direction being opposite the first direction;

coarsely transmitting the first signal in the second direction at the off-center location within the measurement space;

identifying a second edge of the at least one item; and

finely transmitting the first signal in the first direction over the second edge;

constructing a three-dimensional image that defines the at least one item from the acquired first set of point cloud data; and

determining a rectangular prism having a height, length and breadth to contain the constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

18. A system for determining the dimensions of at least one item set within a measurement space, the system comprising:

a first laser located and oriented for transmitting a first signal through a measurement space within which at least one item may reside, the first laser having a coarse transmission mode and a fine transmission mode;

a first camera located and oriented for receiving the first signal and acquiring a plurality of data points comprising a first set of point cloud data from reflections of the first signal from the at least one item;

an array generator for constructing an image from the acquired first set of point cloud data; and

a rectangular prism generator for constructing a rectangular prism in response to dimensions of the constructed image.

19. The system of claim 18, further comprising:

a lens distortion compensator for compensating for lens distortion of the constructed image.

20. The system of claim 19, wherein the lens distortion compensator is configured to determine an image point correction factor during calibration of the system for use in cooperation with the acquired first set of point cloud data to adjust a location of each image point affected by radial lens distortion.

21. The system of claim 18, further comprising:

a noise filter.

22. The system of claim 21, wherein the noise filter is configured to determine:

a median pixel value by an area surrounding a pixel; and

further comprising a designator for setting each pixel to its respective median pixel value.

23. The system of claim 21, wherein the noise filter is configured to generate:

a vertical spatial histogram of the acquired first set of cloud point data from rotation of the acquired first set of point cloud data in a vertical direction;

a horizontal spatial histogram of the acquired first set of point cloud data from rotation of the acquired first set of point cloud data in a horizontal direction; and

further comprising a grouper for grouping points having a spatially detached value, wherein each group having a lesser amount of points than a predetermined value is removed from the image.

24. The system of claim 21, wherein the noise filter comprises:

an identifier for identifying points in a point cloud, each point having a height;

a grouper for grouping the points by the height of each point; and

a comparator for comparing an amount of points in each group against a predetermined value, wherein each group having a lesser amount of points than a predetermined value is removed.

25. The system of claim 21, wherein the noise filter comprises:

an identifier for identifying a position of each disjoint point in a measurement image; and

a comparator for comparing a height value of each disjoint point against a height value of a surrounding signal;

wherein each disjoint point not matching the height value of the surrounding signal is removed.

26. The system of claim 18, further comprising:

means for determining a point threshold by;

identifying a gray-scale value for each point found in an image;

utilizing each identified point to determine a statistical property of the gray-scale value; and

selecting the point threshold in response to the determined statistical property of the gray-scale value.

27. The system of claim 26, further comprising:

means for generating a group of point threshold values from which to select the point threshold in response to calibration of the system.

28. The system of claim 18, further comprising:

a second laser located and oriented for transmitting a second signal through the measurement space, the second laser having a coarse transmission mode and a fine transmission mode;

a second camera located and oriented for receiving the second signal and acquiring a plurality of data points comprising a second set of point cloud data from reflections of the second signal from the at least one item; and

wherein the array generator is configured to utilize the acquired first and second sets of point cloud data to construct the image.

29. The system of claim 28, wherein the second camera is located and oriented for acquiring a plurality of data points comprising a third set of point cloud data from reflections of the first signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, and third sets of point cloud data to construct the image.

30. The system of claim 29, wherein the first camera is located and oriented for acquiring a plurality of data points comprising a fourth set of point cloud data from reflections of the second signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, and fourth sets of point cloud data to construct the image.

31. The system of claim 30, further comprising:

a third laser located and oriented for transmitting a third signal through the measurement space, the third laser having a coarse transmission mode and a fine transmission mode;

a third camera located and oriented for receiving the third signal and acquiring a plurality of data points comprising a fifth set of point cloud data from reflections of the third signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, fourth, and fifth sets of point cloud data to construct the image.

32. The system of claim 31, wherein the third camera is located and oriented for acquiring a plurality of data points comprising a sixth set of point cloud data from reflections of the first signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, fourth, fifth, and sixth sets of point cloud data to construct the image.

33. The system of claim 32, wherein the third camera is located and oriented for acquiring a plurality of data points comprising a seventh set of point cloud data from reflections of the second signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, fourth, fifth, sixth, and seventh sets of point cloud data to construct the image.

34. The system of claim 33, wherein the first camera is located and oriented for acquiring a plurality of data points comprising an eighth set of point cloud data from reflections of the third signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, fourth, fifth, sixth, seventh, and eighth sets of point cloud data to construct the image.

35. The system of claim 34, wherein the second camera is located and configured for acquiring a plurality of data points comprising a ninth set of point cloud data from reflections of the third signal from the at least one item and wherein the array generator is configured to utilize the acquired first, second, third, fourth, fifth, sixth, seventh, eighth, and ninth sets of point cloud data to construct the image.

36. The system of claim 31, wherein the first, second, and third cameras lie on a first perimeter and the first, second, and third lasers lie on a second perimeter.

37. The system of claim 36, wherein the first, second, and third cameras are spaced 120°

about the center of the first perimeter, and the first, second, and third lasers are spaced 120°

about the center of the second perimeter.

38. The system of claim 37, wherein the first and second perimeters are concentric circles, respectively, the first circle being contained within the second circle.

39. The system of claim 28, wherein the first camera and the first laser lie on a first axis and the second camera and the second laser lie on a second axis.

40. The system of claim 39, wherein the first and second axes are parallel.

41. The system of claim 40, wherein both the first camera and the second camera are located between the first laser and the second laser.

42. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item;

a segment for utilizing a second laser and a second camera to determine the approximate location and a dimension of the at least one item;

a segment for acquiring a second set of point cloud data by utilizing the second laser to transmit a second signal over the at least one item and utilizing the second camera to receive a reflection of the second signal from the at least one item;

a segment for acquiring a third set of point cloud data by utilizing the second camera to receive the reflection of the first signal from the at least one item;

a segment for constructing an image defining the at least one item by merging the acquired first, second, and third sets of point cloud data; and

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

44. The medium of claim 42, further comprising:

a segment for compensating for lens distortion of the constructed image.

45. The medium of claim 44, wherein the segment for compensating for lens distortion comprises:

a segment for utilizing an image point correction factor in cooperation with the acquired first set of point cloud data to adjust a location of each image point affected by radial lens distortion.

46. The medium of claim 45, further comprising:

a segment for storing the image point correction factor in a calibration lookup table, wherein the image point correction factor is associated with an image point location.

47. The medium of claim 42, further comprising:

a segment for utilizing a point threshold during construction of the image.

48. The medium of claim 47, further comprising:

a segment for identifying a gray-scale value for each acquired point;

a segment for utilizing each identified point to determine a statistical property of the gray-scale value; and

a segment for defining the point threshold in response to the determined statistical property of the gray-scale value.

49. The medium of claim 47, further comprising:

a segment for providing a group of point threshold values from which to select the point threshold.

50. The medium of claim 42, further comprising:

a segment for transforming the constructed image to a global coordinate system.

53. The medium of claim 42, further comprising:

a segment for acquiring a fourth set of point cloud data by utilizing the first camera to receive the reflection of the second signal from the at least one item; and

a segment for constructing the image by merging the acquired first, second, third, and fourth sets of point cloud data.

43. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item;

a segment for constructing an image defining the at least one item from the acquired first set of point cloud data;

a segment for reducing noise from the constructed image, comprising;

a segment for identifying points in a point cloud, each point having a height;

a segment for grouping the points by the height of each point;

a segment for comparing an amount of points in each grouping against a predetermined value;

a segment for identifying each grouping having a lesser amount of points than the predetermined value; and

a segment for removing each identified grouping; and

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.

51. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item;

a segment for constructing an image defining the at least one item from the acquired first set of point cloud data;

a segment for reducing noise from the constructed image, comprising;

a segment for computing a spatial histogram of the point cloud data in a vertical direction;

a segment for computing a spatial histogram of the point cloud data in a horizontal direction;

a segment for grouping points having a spatially detached value;

a segment for comparing an amount of points in a grouping against a predetermined value;

a segment for identifying each grouping having a lesser amount of points than the predetermined value; and

a segment for removing each identified grouping; and

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image, after noise reduction therefrom, defining the at least one item to ascertain the rectangular prism within which the at last one item will fit.

52. The medium of claim 51, wherein the segment for reducing noise comprises:

a segment for determining a median pixel value for a predetermined area surrounding a pixel; and

a segment for setting each pixel to its respective median pixel value.

54. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item;

a segment for constructing an image of the at least one item from the acquired first set of point cloud data;

a segment for reducing noise from the constructed image, comprising;

a segment for identifying a position of each disjoint point in a measurement array;

a segment for comparing a height value of each disjoint point against a height value of a surrounding signal; and

a segment for removing each disjoint point not matching the height value of the surrounding signal; and

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image, after noise reduction therefrom, of the at least one item to ascertain the rectangular prism within which the at least one item will fit.

55. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item;

a segment for constructing an image of the at least one item from the acquired first set of point cloud data;

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image;

a segment for determining the dimensions of the rectangular prism by rotating a coordinate frame about the centroid of the constructed image through a plurality of angular increments; and

a segment for measuring a distance from the centroid to an edge of the constructed image for each angular increment;

a segment for storing each measurement;

a segment for identifying a length measurement and a breadth measurement; and

a segment for selecting a single length measurement and a single breadth measurement, wherein the selected measurements, in combination with a determined height of the at least one item, comprise dimensions of a rectangular prism having the smallest volume which would contain the at least one item.

56. A computer-readable medium having an application therein to facilitate dimensioning of at least one item, the medium comprising:

a segment for determining an approximate location and extent of at least one item;

a segment for acquiring a first set of point cloud data by utilizing a first laser to transmit a first signal over the at least one item and utilizing a first camera to receive a reflection of the first signal from the at least one item, wherein the segment for acquiring a first set of point cloud data comprises;

a segment for coarsely transmitting the first signal in a first direction at an off-center location within the measurement space;

a segment for identifying a first edge of the at least one item;

a segment for finely transmitting the first signal in a second direction over the first edge, the second direction being opposite the first direction;

a segment for coarsely transmitting the first signal in the second direction at the off-center location within the measurement space;

a segment for identifying a second edge of the at least one item; and

a segment for finely transmitting the first signal in the first direction over the second edge;

a segment for constructing an image defining the at least one item from the acquired first set of point cloud data; and

a segment for determining a rectangular prism having a height, length and breadth to contain a constructed image defining the at least one item to ascertain the rectangular prism within which the at least one item will fit.