Patent Description:
In certain applications it is desirable to move objects from one pallet or platform and place them into another pallet, tote, platform, or conveyance for reassembly and further processing. These objects are typically boxes of varying volumes and weights that must be placed into a receptacle or conveyor line based on a set of rules such as: size of object, size of destination tote or conveyance. Additional rules may be inferred based on printed material on the box, or additionally the kind of box. Box types can vary widely including partial openings in a box top, shape of the box top, whether or not the box is plain cardboard or has been printed. In material handling there are several processes for moving these kinds of objects. In a manual single box pick process, manual operators are presented an assembly of box-like objects and select an individual object to move from a plane or other conveyance to a tote or other conveyance for further processing. In an automated single box pick process the box handling is typically performed by a robot.

A decanting process builds on the single box picking process. Again, typically, manual labor is used to "decant" objects from a plane of objects. These objects are a set of box-like objects, that may or may not be adjacent to each other, that must be moved onto a conveyance or tote, either singly or as a group.

The pose of an object is the position and orientation of the object in space relative to some reference position and orientation. The location of the object can be expressed in terms of X, Y, and Z. The orientation of an object can be expressed in terms of Euler angles describing its rotation about the x-axis (hereinafter RX), rotation about the y-axis (hereinafter RY), and then rotation about the Z-axis (hereinafter RZ) relative to a starting orientation. There are many equivalent mathematic coordinate systems for designating the pose of an object: position coordinates might be expressed in spherical coordinates rather than in Cartesian coordinates of three mutually perpendicular axes; rotational coordinates may be express in terms of quaternions rather than Euler angles; 4x4 homogeneous matrices may be used to combine position and rotation representations; etc. But generally, six variables X, Y, Z, RX, RY, and RZ suffice to describe the pose of a rigid object in 3D space.

Automated single box pick and decanting have some clear issues that humans can easily overcome. For instance, a human might recognize easily that a box position is tipped, rotated, or otherwise not be in a preset location on the plane of boxes. Additionally, a human may easily see that only so many box objects can be moved at a time. Humans also would be able to quickly understand if one object were overlapping another and be able to still move the objects.

Unfortunately, both of the above-noted manual processes are repetitive and prone to burn out and injury for these workers. Manufacturers might also want to move these humans into more appropriate places to supervise automation or other important duties. Ideally, a processing plant would want to automate these processes thus reducing injury, labor shortage and to apply certain rules to the boxes.

In existing art, automated single box picking, or decanting require pre-known information about the arrangement and location of boxes through pre-defined parameters. These parameters must be setup in advance and do not allow for simple changes, or the introduction of new boxes without training or configuration. Other configurations rely on barcoding, or other identification methods that rely on known data about the boxes to determine location and size of boxes.

The automation may include the introduction of robotic systems, sensors, conveyors, or other automated techniques to improve object processing. There is no prior art that handles these kinds of systems without large cost in development and training or significant maintenance in adding new products.

These existing systems rely on either Classical Image Processing or Machine Learning are described hereinbelow.

Classical Image Processing is reliant on a dataset and is dependent on Feature Extraction, Segmentation and Detection to obtain information regarding an item of interest as shown in <FIG>.

Feature extraction attempts to locate and extract features from the image. Segmentation processes use the extracted features to separate the foreground from the background to isolate the portion of an image with desirable data. The processes of feature extraction and segmentation may iterate to extract a final set of features for use in the detection phase. In the final detection phase, a classification, object recognition or measurement is given based on the features in the foreground.

Additionally, existing art requires systems to learn about reading print in a separate process that adds additional time and effort to detection of the desired objects.

Lastly, classical image processing depends on parameters that may be arbitrarily selected such as a percentage of depth and greyscale to determine features - which is error fraught. These kinds of additional parameters add complexity and error to the process.

Alternatively, other systems that automate single box picking or decanting rely on some form of Machine Learning (ML) principles. These are a modern approach to interacting with unknown materials and can learn to classify objects based on a training set of data. Essentially these systems go through a process of identifying objects and asking if the result matches desired result (training). This process requires a large dataset and consumes a significant amount of time.

There are a couple of defects of this process: overtraining and duration of training.

The system must discover features during the training phase and look for things that are important to calculate about the images. Some of these features might include edge or color, or depth or gradients or some other feature that is known only to the training process. Humans gather this information by parallax. An additional downfall of this method is that the more types of input to the ML the longer the training phase.

Too little training on a ML will mean that the system does not have sufficient data for a trained set. Too much and the dataset will be oversized and degrade performance. A balance between the two is required and dependent on a holdout dataset to validate sufficient data.

An additional issue with ML training is accounting for new objects to be added into the process. Anytime a new object is introduced, or an existing object is changed, the system must be retrained for the new data.

The following <CIT>; <CIT>; <CIT>; <CIT>; <CIT>; <CIT>; <CIT>;<CIT>; <CIT>; <CIT>; <CIT>; and <CIT>.

An object of at least one embodiment of the present invention is to provide a machine vision-based method and system which overcome the above-noted shortcomings of Classical Image Processing and/or ML to provide a faster, more reliable process and system.

Other objects of at least one embodiment of the present invention are to provide a machine vision-based method and system which:.

In carrying out the above objects and other objects of at least one embodiment of the present invention, a machine vision-based method to facilitate the unloading of a pile of cartons within a work cell in an automated carton handling system is provided. The method includes the step of providing at least one <NUM>-D or depth sensor having a field of view at the work cell. The at least one sensor has a set of radiation sensing elements which detect reflected, projected radiation to obtain <NUM>-D sensor data. The <NUM>-D sensor data includes a plurality of pixels. For each possible pixel location and each possible carton orientation, the method includes generating a hypothesis that a carton with a known structure appears at that pixel location with that container orientation to obtain a plurality of hypotheses. The method further includes ranking the plurality of hypotheses. The step of ranking includes calculating a surprisal for each of the hypotheses to obtain a plurality of surprisals. The step of ranking is based on the surprisals of the hypotheses. At least one carton of interest is unloaded from the pile based on the ranked hypotheses.

The method may further include utilizing an approximation algorithm to unload a plurality of cartons at a time from the pile in a minimum number of picks.

The sensor may be a hybrid <NUM>-D/<NUM>-D sensor.

The sensor may include a pattern emitter for projecting a known pattern of radiation and a detector for detecting the known pattern of radiation reflected from a surface of the carton.

The pattern emitter may emit a non-visible pattern of radiation and the detector may detect the reflected non-visible pattern of radiation.

The sensor may be a volumetric sensor capable of capturing thousands of individual points in space.

At least one of the hypotheses may be based on print on at least one of the cartons.

Further in carrying out the above objects and other objects of at least one embodiment of the present invention, a machine vision-based system to facilitate the unloading of a pile of cartons within a work cell in an automated carton handling system is provided. The system includes at least one <NUM>-D or depth sensor having a field of view at the work cell. The at least one sensor has a set of radiation sensing elements which detect reflected, projected radiation to obtain <NUM>-D sensor data. The <NUM>-D sensor data including a plurality of pixels. The system also includes at least one processor to process the <NUM>-D sensor data and, for each possible pixel location and each possible carton orientation, generate a hypothesis that a carton with a known structure appears at that pixel location with that container orientation to obtain a plurality of hypotheses. The at least one processor ranks the plurality of hypotheses. Ranking includes calculating a surprisal for each of the hypotheses to obtain a plurality of surprisals. Ranking is based on the surprisals of the hypotheses. The system further includes a vision-guided robot for unloading at least one carton of interest from the pile based on the ranked hypotheses.

The at least one processor may utilize an approximation algorithm so that the vision-guided robot unloads a plurality of cartons at a time from the pile in a minimum number of picks.

Preferably, one or more <NUM>-D or depth sensors <NUM> (<FIG>) of at least one embodiment of the invention measure distance via massively parallel triangulation using a projected pattern (a "multi-point disparity" method). The specific types of active depth sensors which are preferred are called multipoint disparity depth sensors.

"Multipoint" refers to the laser projector which projects thousands of individual beams (aka pencils) onto a scene. Each beam intersects the scene at a point.

"Disparity" refers to the method used to calculate the distance from the sensor to objects in the scene. Specifically, "disparity" refers to the way a laser beam's intersection with a scene shifts when the laser beam projector's distance from the scene changes.

"Depth" refers to the fact that these sensors are able to calculate the X, Y and Z coordinates of the intersection of each laser beam from the laser beam projector with a scene.

"Passive Depth Sensors" determine the distance to objects in a scene without affecting the scene in any way; they are pure receivers.

"Active Depth Sensors" determine the distance to objects in a scene by projecting energy onto the scene and then analyzing the interactions of the projected energy with the scene. Some active sensors project a structured light pattern onto the scene and analyze how long the light pulses take to return, and so on. Active depth sensors are both emitters and receivers.

For clarity, each sensor <NUM> is preferably based on active monocular, multipoint disparity technology as a "multipoint disparity" sensor herein. This terminology, though serviceable, is not standard. A preferred monocular (i.e. a single infrared camera) multipoint disparity sensor is disclosed in <CIT>. A binocular multipoint disparity sensor, which uses two infrared cameras to determine depth information from a scene, is also preferred.

Multiple volumetric sensors <NUM> may be placed in key locations around and above the piles or stacks of cartons <NUM> (<FIG>). Each of these sensors <NUM> typically captures hundreds of thousands of individual points in space. Each of these points has a Cartesian position in space. Before measurement, each of these sensors <NUM> is registered into a common coordinate system. This gives the present system the ability to correlate a location on the image of a sensor with a real world position. When an image is captured from each sensor <NUM>, the pixel information, along with the depth information, is converted by a computer into a collection of points in space, called a "point cloud".

In general, sources of information are unified in the same framework, so that they can be compared as commensurate quantities without using special parameters. This approach to image processing is generally noted as follows: Generate hypotheses. Rank how well each hypothesis matches the evidence, then select the 'best' hypothesis as the answer. This approach is very probabilistic in nature and is shown in the block diagram flow chart of <FIG>.

Boxes or cartons as an example: What are the hypotheses in boxes?.

Focus on intensity in the image and look just for the edge (strength of the edge). What is the probability that there is a pixel that bright? One could focus on the brightest pixels and calculate the probability of a histogram (i.e. probability histogram of <FIG>) and normalize, which is not particularly useful.

One asks if there is a pixel with brightness equal to or greater than this pixel, which is a Cumulative Distribution Function (see the cumulative probability histogram of <FIG>). Cumulative Distribution Functions, which are integrals of histograms, gives one the ability to observe the probability of one pixel. One looks at a histogram of one or more images and assign a probability to one particular pixel.

Then the probability of observing a pixel with intensity greater than or equal to the given value is <NUM>-CDF(g).

If one pick pixels at random (see <FIG>) from a histogram, one cannot get structure and will have just noise.

What is the probability of observing a pixel this bright or brighter? See the cumulative probability formula of <FIG>.

If one takes the multiplication over the box, one can hypothesize where the box is and the orientation and do it for only one box. For each point and rotation of the image one can assign probability of the box being there. It requires a lot of computation to get this number. See the sharp edges of the box of <FIG>.

What is the probability of seeing all the pixels in that box together by chance? Assuming independent probabilities, the probability of observing a whole bunch of independent events together is the multiplication of the probabilities of the individual events. Pi means multiply all these things together. This quantity is the multiplication of a bunch of very small numbers. A low number means this configuration will not occur by random chance.

One does not do all the multiplication computations because they are numerically unstable. One calculates the entropy, (aka the surprisal), which is the negative log probability of the number or observation. Negative log is entropy, which allows for addition instead of multiplication, therefore one works in surprisal which makes probability more accurate and faster. (See <FIG>).

One could just as easily have done this same thing working on the intensity image, volume, or any other feature like print, rather than the edge image. The algorithm does not care what features one is looking at.

The distribution of the random variable, G, is found by observation. The algorithm is good enough that observation of a single image is sufficient, but by continuously updating the CDF as we go, the performance of the algorithm improves.

Using classical methods, if one were looking at the surface points of <FIG>, one might use a morphological structuring element the size of the box and perform some morphology and then threshold to a binary image, then perform connected components to look for something of the correct shape.

If one were to look at <FIG>, one might perform some line segment detections, perhaps using a Hough transform then a threshold, then try to assemble a box from the line segments. Note the threshold parameters. At least one embodiment of the present invention eliminates the parameters in favor of a maximum computation on the entropy image: aside from the structuring model of <FIG>, there are no parameters.

Also, consider what happens if one uses grayscale gradients, but then one wants to add depth gradients as a second source of information. How does one add these quantities together? The classical approach to image processing has no answer for this question. Only the present approach of this application has a ready answer: multiply the probabilities (add the Surprisals). In this approach one could use a whole image, or depth image, or greyscale, or any image.

Decanting: In Multibox Parse, one does not do the select phase, one does not care about the best box. One needs to know where all the boxes are. Visually, the Surprisal hypothesis is represented in <FIG> by size and orientation of the oval.

For Single Box Pick one simply picks the strongest hypothesis from <FIG>.

For Multibox Parse: one must take the same information and find all the boxes.

One solves with an approximation method like Simulated Annealing algorithm but multiple methods for approximating the optimum answer will present themselves.

The algorithm for Pallet Decomposition will ideally partition a layer of boxes such that the number of partitions is minimal - one wants to empty the layer of boxes, by picking multiple boxes at a time, in the minimum number of picks.

A legal pick does not overlap existing boxes. Pick tool does not overlay any box partially.

Illegal picks have tool picking overlapping boxes.

The system includes vision-guided robots <NUM> and one or more cameras <NUM> having a field of view <NUM>. The cameras <NUM> and the robots <NUM> may be mounted on support beams of a support frame structure of the system <NUM> or may rest on a base. One of the cameras <NUM> may be mounted on one of the robots <NUM> to move therewith.

The vision-guided robots <NUM> have the ability to pick up any part within a specified range of allowable cartons using multiple-end-of-arm tooling or grippers. The robots pick up the cartons and orient them at a conveyor or other apparatus. Each robot <NUM> precisely positions self-supporting cartons on a support or stage.

The robots <NUM> are preferably six axis robots. Each robot <NUM> is vision-guided to identify, pick, orient, and present the carton so that they are self-supporting on the stage. The grippers <NUM> accommodate multiple part families.

Benefits of Vision-based Robot Automation include but are not limited to the following:.

A master control station or system controller (<FIG>) determines locations and orientations of the cartons or boxes in the pile or stack of cartons using any suitable machine vision system having at least one camera (i.e. camera <NUM>). Any one or more of various arrangements of vision systems may be used for providing visual information from image processors (<FIG>) to the master controller. In one example, the vision system includes two three-dimensional cameras <NUM> that provides infrared light over fields of vision or view <NUM>. In various embodiments, the light may be infrared.

In some embodiment, multiple cameras such as the cameras <NUM> can be situated at fixed locations on the frame structure at the station, or may be mounted on the arms of the robot <NUM>. Two cameras <NUM> may be spaced apart from one another on the frame structure. The cameras <NUM> are operatively connected to the master controller via their respective image processors. The master controller also controls the robots of the system through their respective robot controllers. Based on the information received from the cameras <NUM>, the master controller then provides control signals to the robot controllers that actuate robotic arm(s) or the one or more robot(s) <NUM> used in the method and system.

The master controller can include a processor and a memory on which is recorded instructions or code for communicating with the robot controllers, the vision systems, the robotic system sensor(s), etc. The master controller is configured to execute the instructions from its memory, via its processor. For example, master controller can be host machine or distributed system, e.g., a computer such as a digital computer or microcomputer, acting as a control module having a processor and, as the memory, tangible, non-transitory computer-readable memory such as read-only memory (ROM) or flash memory. The master controller can also have random access memory (RAM), electrically-erasable, programmable, read only memory (EEPROM), a high-speed clock, analog-to-digital (A/D) and/or digital-to-analog (D/A) circuitry, and any required input/output circuitry and associated devices, as well as any required signal conditioning and/or signal buffering circuitry. Therefore, the master controller can include all software, hardware, memory, algorithms, connections, sensors, etc., necessary to monitor and control the vision subsystem, the robotic subsystem, etc. As such, a control method can be embodied as software or firmware associated with the master controller. It is to be appreciated that the master controller can also include any device capable of analyzing data from various sensors, comparing data, making the necessary decisions required to control and monitor the vision subsystem, the robotic subsystem, sensors, etc..

An end effector on the robot arm may include a series of grippers supported to pick up the cartons. The robotic arm is then actuated by its controller to pick up the cartons with the particular gripper, positioning the gripper <NUM> relative to the cartons using the determined location and orientation from the visual position and orientation data of the particular vision subsystem including its camera and image processor.

In general, the method and system of at least one embodiment of the present invention searches for objects like boxes or cartons which have high variability in shape, size, color, printing, barcodes, etc. There is lots of differences between each object, even of the same type and one needs to determine location of the boxes that may be jammed very close together, without much discernible feature. The method combines both 2D and 3D imaging (grayscale and depth) to get individuation of the objects. The objects may all "look" the same to a human, but have high variability between each assembled box or carton.

Claim 1:
A machine vision-based method to facilitate the unloading of a pile of cartons within a work cell in an automated carton handling system, the method comprising the steps of:
providing at least one <NUM>-D or depth sensor having a field of view at the work cell, the at least one sensor having a set of radiation sensing elements which detect reflected, projected radiation to obtain <NUM>-D sensor data, the <NUM>-D sensor data including a plurality of pixels;
for each possible pixel location and each possible carton orientation, generating a hypothesis that a carton with a known structure appears at that pixel location with that carton orientation to obtain a plurality of hypotheses;
ranking the plurality of hypotheses wherein the step of ranking includes calculating a surprisal for each of the hypotheses to obtain a plurality of surprisals and wherein the step of ranking is based on the surprisals of the hypotheses; and
unloading at least one carton of interest from the pile based on the ranked hypotheses.