# Patent

## Title
System and method for package dimensioning

## Abstract

A system and method for package dimensioning is provided. The package-dimensioning system includes an image capturing subsystem for acquiring information about an object within the image-capturing subsystem's field of view. A features-computation module analyzes object information and compiles a feature set describing the object's surface features. A classification module analyzes the feature set and categorizes the object's shape. A shape-estimation module estimates the dimensions of the object.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
The present application claims the benefit of U.S. Patent Application No. 61/872,299 for a System and Method for Package Dimensioning filed Aug. 30, 2013. The foregoing patent application is hereby incorporated by reference in its entirety.


FIELD OF THE INVENTION
The present invention relates to systems and methods for determining the dimensions of packages. More particularly, the present invention relates to a dimensioning system and method for determining package dimensions having reduced cost, better accuracy, and increased speed.
BACKGROUND
In the retail shipping environment, dimensional weight (e.g., volumetric weight) is typically employed to determine the shipping rate for a particular package. Traditionally, measurements of a package's dimensions for purposes of determining dimensional weight are obtained by hand measuring the package with a measuring device such as a tape measure. This approach consumes the time of the shipping company's personnel and is also subject to measurement errors (e.g., incorrectly reading or recording the measurement).
An attractive automated system for package dimensioning has proved elusive. Obtaining an accurate three-dimensional representation of the package has typically required the use of at least two imaging devices to obtain images of the package at different angles. This approach introduces complexities into the process due to the need to assimilate the two images for analysis and, because it requires two imaging devices, it tends to be expensive.
Therefore, a need exists for an inexpensive, but accurate, automated system for determining the dimensions of objects such as packages for shipping.
SUMMARY
Accordingly, in one aspect, the present invention embraces a package-dimensioning system. The package-dimensioning system includes an image-capturing subsystem for acquiring information about an object within the image-capturing subsystem's field of view. The package-dimensioning system also includes a features-computation module for analyzing object information acquired by the image-capturing subsystem and compiling a feature set describing the object's surface features. The package-dimensioning system also includes a classification module for analyzing the feature set describing the object's surface features and for categorizing the object's shape. The package-dimensioning system also includes a shape-estimation module for estimating dimensions of the object. The shape-estimation module includes a plurality of shape-specific submodules adapted for estimating the dimensions of particular shapes.
In one embodiment, the image-capturing subsystem includes a three-dimensional range camera.
In another embodiment, the image-capturing subsystem is configured to generate a point cloud with respect to the object.
In yet another embodiment, the features-computation module is configured to analyze the point cloud.
In yet another embodiment, the features-computation module is configured to compile a relative histogram describing the object's surface features.
In yet another alternative embodiment, the features-computation module is configured to compile a relative histogram describing the object's surface features.
In yet another alternative embodiment, the classification module is configured to select the shape-specific submodule for estimating the dimensions of the object.
In another aspect, the invention embraces a package-dimensioning system that includes an image-capturing subsystem for acquiring information about a plurality of objects within the image-capturing subsystem's field of view. The package-dimensioning system also includes a features-computation module for analyzing object information acquired by the image-capturing subsystem and for compiling a feature set describing each object's surface features. The package-dimensioning system also includes a classification module for analyzing the feature set describing each object's surface features and for categorizing each object's shape. The package-dimensioning system also includes a shape-estimation module for estimating dimensions of each object. The shape-estimation module includes a plurality of shape-specific submodules adapted for estimating the dimensions of particular shapes.
In another embodiment, the features-computation module is configured to differentiate the information about the plurality of objects into discrete object-specific information.
In yet another aspect, the invention embraces a method for estimating the dimensions of a package. An image of an object is acquired. A feature set describing the object's surface features is compiled. The object's shape is categorized based on the feature set. The dimensions of the object are estimated based on the categorization of the object's shape.
The foregoing illustrative summary, as well as other exemplary objectives and/or advantages of the invention, and the manner in which the same are accomplished, are further explained within the following detailed description and its accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram illustrating an exemplary package-dimensioning system according to the present invention.
FIG. 2 is a block diagram illustrating an exemplary alternative embodiment of an exemplary package-dimensioning system according to the present invention.
FIG. 3 is a block diagram illustrating an exemplary package-dimensioning system according to the present invention.



DETAILED DESCRIPTION
The present invention embraces a package-dimensioning system. The package-dimensioning system is typically used in measuring an object's dimensions for the purpose of determining the appropriate shipping rate to charge in shipping transactions. In retail shipping operations, in particular, the dimensions of an object (e.g., package, box, container, shipping tube, etc.) are often used to determine the shipping fare where the shipping fare is based on the dimensional weight of an object.
Traditionally, the dimensional weight is calculated by hand-measuring the dimensions of the object to be shipped (e.g., with a tape measure). Hand-measuring tends to be slow, personnel-intensive, and subject to human error. Automation of the dimensioning process would alleviate these shortcomings of the hand-measuring approach. Because the estimated dimensions are used for a commercial transaction, most countries require certification of the system's accuracy under typical operating conditions (e.g., the intended-use case). Consequently, the automation must provide reliable, accurate dimensioning of objects.
Three-dimensional cameras (e.g., 3D cameras), such as range cameras, can be utilized effectively in dimensioning applications. The high cost of these range cameras, however, has precluded their widespread use. The recent advent of relatively low-cost range cameras has afforded greater opportunity for implementing automated dimensioning on a wider scale. Consequently, the package-dimensioning system according to the present invention uses an image capturing subsystem (e.g., a range camera) to acquire a two-dimensional image showing the distance to points within the field of view. The acquired image (e.g., range image) typically has pixel values which correspond to the distance from the range camera. For example, brighter pixels indicate the point is a shorter distance away than points represented by darker pixels. In this way, the range image is a two-dimensional image that provides depth information regarding a three-dimensional scene.
The image acquired by the image capturing subsystem is analyzed to identify the object within the image and to identify certain surface features of the object. The package-dimensioning system analyzes the surface features to categorize the shape of the object (e.g., cuboid, cylinder, or prism) and to estimate its dimensions. Typically, the processing of the image that is acquired by the image capturing subsystem is performed by a computer, which typically has a central processing unit (CPU) and a memory.
Referring now to FIGS. 1 and 2, the package-dimensioning system 100 according to the present invention includes an image-capturing subsystem 110. The image-capturing subsystem 110 acquires information about an object within the image-capturing subsystem's 110 field of view. Typically, the image-capturing subsystem includes an imaging device (e.g., camera, stereo camera, range camera 110A, lidar). The imaging device may be any sensor that provides information from which a computer can build an organized 3D point cloud. An organized point cloud has 3D points arranged in a 2D matrix, which corresponds to the rasterization of the range image. Typically, the image-capturing system is configured to generate a point cloud with respect to the object within its field of view. The point cloud usually contains information regarding the positioning of points in a three-dimensional space (e.g., X, Y, Z coordinates) within the field of view of the image-capturing subsystem 110 when the range image is acquired, including points on the surface of the object 112. The information regarding the positioning of points on the surface of the object is referred to as object information.
A features-computation module 120 analyzes object information acquired by the image-capturing subsystem 110. Based upon the analysis of the object information, the features-computation module 120 compiles a feature set describing the object's 112 features. Compiling a feature set typically involves consideration of two features of points on the object 112: curvature c and orientation θ relative to the ground plane. The orientation of each point relative to the ground plane is typically measured by the angle, θ, between the local surface normal and the ground's normal. In other words, the feature set for each object 112 includes computations of two features, curvature c and orientation θ, for each point in the point cloud representing the surface of the object 112.
Object information relating to an image of a regular box, for instance, will be dominated by points with zero curvature (c=0) and with orientations parallel or orthogonal to the ground (θ=π/2 radians or θ=0 radians). By way of further example, object information relating to an image of a cylinder lying flat will have non-zero curvature (c>0) and a continuous range of orientation with respect to the ground (e.g., θ=[0 radians, π radians]). The feature set as a whole, therefore, describes an object's surface features (e.g., planar surfaces, curved surfaces). Typically, the feature set takes the form of a relative histogram (e.g., 2D relative histogram). By way of example, a typical histogram might use (i) ten uniform bins for curvature c, ranging from 0 to 0.08 and (ii) 20 uniform bins for orientation θ, varying from 0 to π radians.
The package-dimensioning system 100 according to the present invention also includes a classification module 130. The classification module 130 analyzes the feature set (e.g., relative histogram) describing the object's surface features. Based on the analysis of the feature set, the classification module 130 categorizes the object's shape. Typically, the system 100 takes advantage of the fact that the domain of shipped objects 112 is generally limited, with the vast majority of shipped objects 112 being cuboids, cylinders, or prisms. Given this, the classification module 130 is typically limited to a relatively small (e.g., between about 4 and 8) number of shape categories. By way of example, and without intending to limit the disclosure, the classification module 130 may be configured to categorize an object's shape as a rectangular box, a right circular cylinder lying flat, a right circular cylinder standing vertically, a right regular prism with triangular bases lying flat, or a right regular prism with triangular bases standing vertically. Providing a limited number of potential shape categories increases the likelihood that the classification module 130 will be able to successfully categorize the object's 112 shape because the differences between the feature sets associated with each shape category are sufficiently distinct to avoid shape confusion (e.g., tendency to associate more than one shape with a given feature set). This approach of limiting the number of shapes categories therefore increases system accuracy while increasing system speed through decreased computational complexity (e.g., by limiting the number of shape categories under consideration when attempting to match a feature set with a shape category).
The package-dimensioning system 100 also includes a shape-estimation module 140. The shape-estimation module 140 estimates the dimensions of the object 112. Typically, the shape-estimation module includes a plurality of shape-specific submodules 145 adapted for estimating the dimensions of particular shapes. For example, and without intending to limit the disclosure to any particular embodiment, upon the classification module's 130 categorization of the object's 112 shape as a rectangular box (e.g., by analysis of the feature set derived from the point cloud associated with the object's surface), the shape-estimation module 140 would utilize the shape-specific submodule 145 adapted for estimating the dimensions of rectangular boxes. In this example, the rectangular box version of the shape-specific submodule 145 would analyze the object information and output an estimate of the dimensions (e.g., length, width, and height) of the rectangular box object. Typically, the shape-estimation module 140 utilizes object information relating to the distance of various points on the object from the range camera's 110A to estimate the object's dimensions.
Referring now to FIG. 3, the package-dimensioning system 100 embraced by the present invention may be adapted to estimate the dimensions of a plurality of objects 112 within the field of view of the image-capturing subsystem 110. To accomplish this, the system 100 typically must segment the objects 112 that are above the ground plane (e.g., supporting surface) within the field of view of the image-capturing subsystem 110. Typically, Euclidian clustering is employed to segment the objects 112 in an organized point cloud, whereupon the system 100 processes each segmented portion of the point cloud associated with a distinct object in the manner described above.
To supplement the present disclosure, this application incorporates entirely by reference the following patents, patent application publications, and patent applications: U.S. Pat. No. 6,832,725; U.S. Pat. No. 7,159,783; U.S. Pat. No. 7,128,266; U.S. Pat. No. 7,413,127; U.S. Pat. No. 7,726,575; U.S. Pat. No. 8,390,909; U.S. Pat. No. 8,294,969; U.S. Pat. No. 8,408,469; U.S. Pat. No. 8,408,468; U.S. Pat. No. 8,381,979; U.S. Pat. No. 8,408,464; U.S. Pat. No. 8,317,105; U.S. Pat. No. 8,366,005; U.S. Pat. No. 8,424,768; U.S. Pat. No. 8,322,622; U.S. Pat. No. 8,371,507; U.S. Pat. No. 8,376,233; U.S. Pat. No. 8,457,013; U.S. Pat. No. 8,448,863; U.S. Pat. No. 8,459,557; U.S. Pat. No. 8,469,272; U.S. Pat. No. 8,474,712; U.S. Pat. No. 8,479,992; U.S. Pat. No. 8,490,877; U.S. Pat. No. 8,517,271; U.S. Pat. No. 8,523,076; U.S. Pat. No. 8,528,819; U.S. Patent Application Publication No. 2012/0111946; U.S. Patent Application Publication No. 2012/0223141; U.S. Patent Application Publication No. 2012/0193423; U.S. Patent Application Publication No. 2012/0203647; U.S. Patent Application Publication No. 2012/0248188; U.S. Patent Application Publication No. 2012/0228382; U.S. Patent Application Publication No. 2012/0193407; U.S. Patent Application Publication No. 2012/0168511; U.S. Patent Application Publication No. 2012/0168512; U.S. Patent Application Publication No. 2010/0177749; U.S. Patent Application Publication No. 2010/0177080; U.S. Patent Application Publication No. 2010/0177707; U.S. Patent Application Publication No. 2010/0177076; U.S. Patent Application Publication No. 2009/0134221; U.S. Patent Application Publication No. 2012/0318869; U.S. Patent Application Publication No. 2013/0043312; U.S. Patent Application Publication No. 2013/0068840; U.S. Patent Application Publication No. 2013/0070322; U.S. Patent Application Publication No. 2013/0075168; U.S. Patent Application Publication No. 2013/0056285; U.S. Patent Application Publication No. 2013/0075464; U.S. Patent Application Publication No. 2013/0082104; U.S. Patent Application Publication No. 2010/0225757; U.S. Patent Application Publication No. 2013/0175343; U.S. patent application Ser. No. 13/347,193 for a HYBRID-TYPE BIOPTICAL LASER SCANNING AND DIGITAL IMAGING SYSTEM EMPLOYING DIGITAL IMAGER WITH FIELD OF VIEW OVERLAPPING FIELD OF FIELD OF LASER SCANNING SUBSYSTEM, filed Jan. 10, 2012 (Kearney et al.); U.S. patent application Ser. No. 13/367,047 for LASER SCANNING MODULES EMBODYING SILICONE SCAN ELEMENT WITH TORSIONAL HINGES, filed Feb. 6, 2012 (Feng et al.); U.S. patent application Ser. No. 13/400,748 for a LASER SCANNING BAR CODE SYMBOL READING SYSTEM HAVING INTELLIGENT SCAN SWEEP ANGLE ADJUSTMENT CAPABILITIES OVER THE WORKING RANGE OF THE SYSTEM FOR OPTIMIZED BAR CODE SYMBOL READING PERFORMANCE, filed Feb. 21, 2012 (Wilz); U.S. patent application Ser. No. 13/432,197 for a LASER SCANNING SYSTEM USING LASER BEAM SOURCES FOR PRODUCING LONG AND SHORT WAVELENGTHS IN COMBINATION WITH BEAM-WAIST EXTENDING OPTICS TO EXTEND THE DEPTH OF FIELD THEREOF WHILE RESOLVING HIGH RESOLUTION BAR CODE SYMBOLS HAVING MINIMUM CODE ELEMENT WIDTHS, filed Mar. 28, 2012 (Havens et al.); U.S. patent application Ser. No. 13/492,883 for a LASER SCANNING MODULE WITH ROTATABLY ADJUSTABLE LASER SCANNING ASSEMBLY, filed Jun. 10, 2012 (Hennick et al.); U.S. patent application Ser. No. 13/367,978 for a LASER SCANNING MODULE EMPLOYING AN ELASTOMERIC U-HINGE BASED LASER SCANNING ASSEMBLY, filed Feb. 7, 2012 (Feng et al.); U.S. patent application Ser. No. 13/852,097 for a System and Method for Capturing and Preserving Vehicle Event Data, filed Mar. 28, 2013 (Barker et al.); U.S. patent application Ser. No. 13/780,356 for a Mobile Device Having Object-Identification Interface, filed Feb. 28, 2013 (Samek et al.); U.S. patent application Ser. No. 13/780,158 for a Distraction Avoidance System, filed Feb. 28, 2013 (Sauerwein); U.S. patent application Ser. No. 13/784,933 for an Integrated Dimensioning and Weighing System, filed Mar. 5, 2013 (McCloskey et al.); U.S. patent application Ser. No. 13/785,177 for a Dimensioning System, filed Mar. 5, 2013 (McCloskey et al.); U.S. patent application Ser. No. 13/780,196 for Android Bound Service Camera Initialization, filed Feb. 28, 2013 (Todeschini et al.); U.S. patent application Ser. No. 13/792,322 for a Replaceable Connector, filed Mar. 11, 2013 (Skvoretz); U.S. patent application Ser. No. 13/780,271 for a Vehicle Computer System with Transparent Display, filed Feb. 28, 2013 (Fitch et al.); U.S. patent application Ser. No. 13/736,139 for an Electronic Device Enclosure, filed Jan. 8, 2013 (Chaney); U.S. patent application Ser. No. 13/771,508 for an Optical Redirection Adapter, filed Feb. 20, 2013 (Anderson); U.S. patent application Ser. No. 13/750,304 for Measuring Object Dimensions Using Mobile Computer, filed Jan. 25, 2013; U.S. patent application Ser. No. 13/471,973 for Terminals and Methods for Dimensioning Objects, filed May 15, 2012; U.S. patent application Ser. No. 13/895,846 for a Method of Programming a Symbol Reading System, filed Apr. 10, 2013 (Corcoran); U.S. patent application Ser. No. 13/867,386 for a Point of Sale (POS) Based Checkout System Supporting a Customer-Transparent Two-Factor Authentication Process During Product Checkout Operations, filed Apr. 22, 2013 (Cunningham et al.); U.S. patent application Ser. No. 13/888,884 for an Indicia Reading System Employing Digital Gain Control, filed May 7, 2013 (Xian et al.); U.S. patent application Ser. No. 13/895,616 for a Laser Scanning Code Symbol Reading System Employing Multi-Channel Scan Data Signal Processing with Synchronized Digital Gain Control (SDGC) for Full Range Scanning, filed May 16, 2013 (Xian et al.); U.S. patent application Ser. No. 13/897,512 for a Laser Scanning Code Symbol Reading System Providing Improved Control over the Length and Intensity Characteristics of a Laser Scan Line Projected Therefrom Using Laser Source Blanking Control, filed May 20, 2013 (Brady et al.); U.S. patent application Ser. No. 13/897,634 for a Laser Scanning Code Symbol Reading System Employing Programmable Decode Time-Window Filtering, filed May 20, 2013 (Wilz, Sr. et al.); U.S. patent application Ser. No. 13/902,242 for a System For Providing A Continuous Communication Link With A Symbol Reading Device, filed May 24, 2013 (Smith et al.); U.S. patent application Ser. No. 13/902,144, for a System and Method for Display of Information Using a Vehicle-Mount Computer, filed May 24, 2013 (Chamberlin); U.S. patent application Ser. No. 13/902,110 for a System and Method for Display of Information Using a Vehicle-Mount Computer, filed May 24, 2013 (Hollifield); U.S. patent application Ser. No. 13/912,262 for a Method of Error Correction for 3D Imaging Device, filed Jun. 7, 2013 (Jovanovski et al.); U.S. patent application Ser. No. 13/912,702 for a System and Method for Reading Code Symbols at Long Range Using Source Power Control, filed Jun. 7, 2013 (Xian et al.); U.S. patent application Ser. No. 13/922,339 for a System and Method for Reading Code Symbols Using a Variable Field of View, filed Jun. 20, 2013 (Xian et al.); U.S. patent application Ser. No. 13/927,398 for a Code Symbol Reading System Having Adaptive Autofocus, filed Jun. 26, 2013 (Todeschini); U.S. patent application Ser. No. 13/930,913 for a Mobile Device Having an Improved User Interface for Reading Code Symbols, filed Jun. 28, 2013 (Gelay et al.); U.S. patent application Ser. No. 13/933,415 for an Electronic Device Case, filed Jul. 2, 2013 (London et al.); U.S. patent application Ser. No. 13/947,296 for a System and Method for Selectively Reading Code Symbols, filed Jul. 22, 2013 (Rueblinger et al.); U.S. patent application Ser. No. 13/950,544 for a Code Symbol Reading System Having Adjustable Object Detection, filed Jul. 25, 2013 (Jiang); U.S. patent application Ser. No. 13/961,408 for a Method for Manufacturing Laser Scanners, filed Aug. 7, 2013 (Saber et al.); U.S. patent application Ser. No. 13/973,315 for a Symbol Reading System Having Predictive Diagnostics, filed Aug. 22, 2013 (Nahill et al.); U.S. patent application Ser. No. 13/973,354 for a Pairing Method for Wireless Scanner via RFID, filed Aug. 22, 2013 (Wu et al.); and U.S. patent application Ser. No. 13/974,374 for Authenticating Parcel Consignees with Indicia Decoding Devices, filed Aug. 23, 2013 (Ye et al.).
* * *
In the specification and/or figures, typical embodiments of the invention have been disclosed. The present invention is not limited to such exemplary embodiments. The use of the term “and/or” includes any and all combinations of one or more of the associated listed items. The figures are schematic representations and so are not necessarily drawn to scale. Unless otherwise noted, specific terms have been used in a generic and descriptive sense and not for purposes of limitation.

## Claims

1. A package-dimensioning system, comprising:
an imager for acquiring information about an object within the imager field of view;
a features-computation module for analyzing object information acquired by the imager and compiling a feature set describing the object's surface features;
a classification module for analyzing the feature set describing the object's surface features and for categorizing the object's shape; and
a shape-estimation module for estimating dimensions of the object, the shape-estimation module comprising a plurality of shape-specific submodules adapted for estimating the dimensions of particular shapes.

2. The package-dimensioning system according to claim 1, wherein the imager comprises a range camera.

3. The package-dimensioning system according to claim 1, wherein the imager is configured to generate a range image with respect to the object.

4. The package-dimensioning system according to claim 3, wherein the features-computation module is configured to analyze the range image.

5. The package-dimensioning system according to claim 1, wherein the features-computation module is configured to compile a relative histogram describing the object's surface features.

6. The package-dimensioning system according to claim 1, wherein the classification module is configured to select the shape-specific submodule for estimating the dimensions of the object.

7. A package-dimensioning system, comprising:
an imager for acquiring information about a plurality of objects within the imager field of view;
a features-computation module for analyzing object information acquired by the imager and for compiling a feature set describing each object's surface features;
a classification module for analyzing the feature set describing each object's surface features and for categorizing each object's shape; and
a shape-estimation module for estimating dimensions of each object, the shape-estimation module comprising a plurality of shape-specific submodules adapted for estimating the dimensions of particular shapes.

8. The package-dimensioning system according to claim 7, wherein the imager comprises a range camera.

9. The package-dimensioning system according to claim 7, wherein the imager is configured to generate a range image with respect to each object.

10. The package-dimensioning system according to claim 9, wherein the features-computation module is configured to analyze the range image associated with each object.

11. The package-dimensioning system according to claim 7, wherein the features-computation module is configured to compile a relative histogram describing each object's surface features.

12. The package-dimensioning system according to claim 7, wherein the classification module is configured to select the shape-specific submodule for estimating the dimensions of each object.

13. The package-dimensioning system according to claim 7, wherein the features-computation module is configured to differentiate the information about the plurality of objects into discrete object-specific information.

14. A method for estimating the dimensions of a package, comprising:
acquiring an image of an object with an imager;
compiling a feature set describing the object's surface features with a features-computation module;
categorizing the object's shape based on the feature set with a classification module; and
estimating the dimensions of the object based on the categorization of the object's shape using a shape-estimation module comprising a plurality of shape-specific submodules adapted for estimating the dimensions of particular shapes.

15. The method according to claim 14, wherein the image of an object is acquired using a range camera.

16. The method according to claim 14, wherein the feature set comprises a relative histogram describing the object's surface features.