Method, system and apparatus for shelf edge detection

A method of detecting an edge of a support surface in an imaging controller includes: obtaining image data captured by an image sensor and a plurality of depth measurements captured by a depth sensor, the image data and the plurality of depth measurements corresponding to an area containing the support surface; detecting preliminary edges in the image data; applying a Hough transform to the preliminary edges to determine Hough lines representing candidate edges of the support surface; segmenting the plurality of depth measurements to assign classes to each pixel, each class defined by one of a plurality of seed pixels, wherein the plurality of seed pixels are identified from the depth measurements based on the Hough lines; and detecting the edge of the support surface by selecting a class of pixels and applying a line-fitting model to the selected class to obtain an estimated edge of the support surface.

BACKGROUND

Environments in which objects are managed, such as retail facilities, warehousing and distribution facilities, and the like, may be complex and fluid. For example, a retail facility may include objects such as products for purchase, and a distribution facility may include objects such as parcels or pallets. For example, a given environment may contain a wide variety of objects with different sizes, shapes, and other attributes. Such objects may be supported on shelves in a variety of positions and orientations. The variable position and orientation of the objects, as well as variations in lighting and the placement of labels and other indicia on the objects and the shelves, can render detection of structural features, such as the edges of the shelves, difficult.

DETAILED DESCRIPTION

Examples disclosed herein are directed to a method in an imaging controller, including: obtaining image data captured by an image sensor and a plurality of depth measurements captured by a depth sensor, the image data and the plurality of depth measurements corresponding to an area containing the support surface; detecting preliminary edges in the image data; applying a Hough transform to the preliminary edges to determine Hough lines representing candidate edges of the support surface; segmenting the plurality of depth measurements to assign classes to each pixel, each class defined by one of a plurality of seed pixels, wherein the plurality of seed pixels are identified from the depth measurements based on the Hough lines; and selecting a class of pixels and applying a line-fitting model to the selected class to obtain an estimated edge of the support surface.

Additional examples disclosed herein are directed to a mobile automation apparatus, comprising: a locomotive assembly; an image sensor and a depth sensor; and an imaging controller configured to: obtain image data captured by the image sensor and a plurality of depth measurements captured by the depth sensor, the image data and the plurality of depth measurements corresponding to an area containing the support surface; detect preliminary edges in the image data; apply a Hough transform to the preliminary edges to determine Hough lines representing candidate edges of the support surface; segment the plurality of depth measurements to assign classes to each pixel, each class defined by one of a plurality of seed pixels, wherein the plurality of seed pixels are identified from the depth measurements based on the Hough lines; and select a class of pixels and applying a line-fitting model to the selected class to obtain an estimated edge of the support surface.

FIG. 1depicts a mobile automation system100in accordance with the teachings of this disclosure. The system100includes a server101in communication with at least one mobile automation apparatus103(also referred to herein simply as the apparatus103) and at least one client computing device104via communication links105, illustrated in the present example as including wireless links. In the present example, the links105are provided by a wireless local area network (WLAN) deployed via one or more access points (not shown). In other examples, the server101, the client device104, or both, are located remotely (i.e. outside the environment in which the apparatus103is deployed), and the links105therefore include wide-area networks such as the Internet, mobile networks, and the like. The system100also includes a dock106for the apparatus103in the present example. The dock106is in communication with the server101via a link107that in the present example is a wired link. In other examples, however, the link107is a wireless link.

The client computing device104is illustrated inFIG. 1as a mobile computing device, such as a tablet, smart phone or the like. In other examples, the client device104is implemented as another type of computing device, such as a desktop computer, a laptop computer, another server, a kiosk, a monitor, and the like. The system100can include a plurality of client devices104in communication with the server101via respective links105.

The system100is deployed, in the illustrated example, in a retail facility including a plurality of support structures such as shelf modules110-1,110-2,110-3and so on (collectively referred to as shelf modules110or shelves110, and generically referred to as a shelf module110or shelf110—this nomenclature is also employed for other elements discussed herein). Each shelf module110supports a plurality of products112. Each shelf module110includes a shelf back116-1,116-2,116-3and a support surface (e.g. support surface117-3as illustrated inFIG. 1) extending from the shelf back116to a shelf edge118-1,118-2,118-3.

The shelf modules110are typically arranged in a plurality of aisles, each of which includes a plurality of modules110aligned end-to-end. In such arrangements, the shelf edges118face into the aisles, through which customers in the retail facility as well as the apparatus103may travel. As will be apparent fromFIG. 1, the term “shelf edge”118as employed herein, which may also be referred to as the edge of a support surface (e.g., the support surfaces117) refers to a surface bounded by adjacent surfaces having different angles of inclination. In the example illustrated inFIG. 1, the shelf edge118-3is at an angle of about ninety degrees relative to each of the support surface117-3and the underside (not shown) of the support surface117-3. In other examples, the angles between the shelf edge118-3and the adjacent surfaces, such as the support surface117-3, is more or less than ninety degrees.

The apparatus103is equipped with a plurality of navigation and data capture sensors108, such as image sensors (e.g. one or more digital cameras) and depth sensors (e.g. one or more Light Detection and Ranging (LIDAR) sensors, one or more depth cameras employing structured light patterns, such as infrared light, or the like). The apparatus103is deployed within the retail facility and, via communication with the server101and use of the sensors108, navigates autonomously or partially autonomously along a length119of at least a portion of the shelves110. Navigation may be performed according to a frame of reference102established within the retail facility. That is, the apparatus103tracks its location in the frame of reference102. While navigating among the shelves110, the apparatus103can capture images, depth measurements and the like, representing the shelves110(generally referred to as shelf data or captured data).

The server101includes a special purpose controller, such as a processor120, specifically designed to control and/or assist the mobile automation apparatus103to navigate the environment and to capture data. The processor120is interconnected with a non-transitory computer readable storage medium, such as a memory122, having stored thereon computer readable instructions for performing various functionality, including control of the apparatus103to navigate the modules110and capture shelf data, as well as post-processing of the shelf data. The memory122can also store data for use in the above-mentioned control of the apparatus103, such as a repository123containing a map of the retail environment and any other suitable data (e.g. operational constraints for use in controlling the apparatus103, data captured by the apparatus103, and the like).

The memory122includes a combination of volatile memory (e.g. Random Access Memory or RAM) and non-volatile memory (e.g. read only memory or ROM, Electrically Erasable Programmable Read Only Memory or EEPROM, flash memory). The processor120and the memory122each comprise one or more integrated circuits. In some embodiments, the processor120is implemented as one or more central processing units (CPUs) and/or graphics processing units (GPUs).

The server101also includes a communications interface124interconnected with the processor120. The communications interface124includes suitable hardware (e.g. transmitters, receivers, network interface controllers and the like) allowing the server101to communicate with other computing devices—particularly the apparatus103, the client device104and the dock106—via the links105and107. The links105and107may be direct links, or links that traverse one or more networks, including both local and wide-area networks. The specific components of the communications interface124are selected based on the type of network or other links that the server101is required to communicate over. In the present example, as noted earlier, a wireless local-area network is implemented within the retail facility via the deployment of one or more wireless access points. The links105therefore include either or both wireless links between the apparatus103and the mobile device104and the above-mentioned access points, and a wired link (e.g. an Ethernet-based link) between the server101and the access point.

The processor120can therefore obtain data captured by the apparatus103via the communications interface124for storage (e.g. in the repository123) and subsequent processing (e.g. to detect objects such as shelved products in the captured data, and detect status information corresponding to the objects). The server101may also transmit status notifications (e.g. notifications indicating that products are out-of-stock, in low stock or misplaced) to the client device104responsive to the determination of product status data. The client device104includes one or more controllers (e.g. central processing units (CPUs) and/or field-programmable gate arrays (FPGAs) and the like) configured to process (e.g. to display) notifications received from the server101.

Turning now toFIG. 2, the mobile automation apparatus103is shown in greater detail. The apparatus103includes a chassis201containing a locomotive mechanism203(e.g. one or more electrical motors driving wheels, tracks or the like). The apparatus103further includes a sensor mast205supported on the chassis201and, in the present example, extending upwards (e.g., substantially vertically) from the chassis201. The mast205supports the sensors108mentioned earlier. In particular, the sensors108include at least one imaging sensor207, such as a digital camera, as well as at least one depth sensor209, such as a 3D digital camera capable of capturing both depth data and image data. The apparatus103also includes additional depth sensors, such as LIDAR sensors211. As shown inFIG. 2A, the cameras207and the LIDAR sensors211are arranged on one side of the mast205, while the depth sensor209is arranged on a front of the mast205. That is, the depth sensor209is forward-facing (i.e. captures data in the direction of travel of the apparatus103), while the cameras207and LIDAR sensors211are side-facing (i.e. capture data alongside the apparatus103, in a direction perpendicular to the direction of travel). In other examples, the apparatus103includes additional sensors, such as one or more RFID readers, temperature sensors, and the like.

In the present example, the mast205supports seven digital cameras207-1through207-7, and two LIDAR sensors211-1and211-2. The mast205also supports a plurality of illumination assemblies213, configured to illuminate the fields of view of the respective cameras207. That is, the illumination assembly213-1illuminates the field of view of the camera207-1, and so on. The sensors207and211are oriented on the mast205such that the fields of view of each sensor face a shelf110along the length119of which the apparatus103is traveling. The apparatus103is configured to track a location of the apparatus103(e.g. a location of the center of the chassis201) in a common frame of reference previously established in the retail facility, permitting data captured by the mobile automation apparatus to be registered to the common frame of reference.

Referring toFIG. 3, certain components of the mobile automation apparatus103are shown, in addition to the cameras207, depth sensor209, lidars211, and illumination assemblies213mentioned above. The apparatus103includes a special-purpose controller, such as a processor300, interconnected with a non-transitory computer readable storage medium, such as a memory304. The memory304includes a suitable combination of volatile memory (e.g. Random Access Memory or RAM) and non-volatile memory (e.g. read only memory or ROM, Electrically Erasable Programmable Read Only Memory or EEPROM, flash memory). The processor300and the memory304each comprise one or more integrated circuits. The memory304stores computer readable instructions for execution by the processor300. In particular, the memory304stores a control application308which, when executed by the processor300, configures the processor300to perform various functions discussed below in greater detail and related to the detection of shelf edges in data captured by the sensors (e.g. the depth sensors209or the LIDAR sensors211). The control application308may further configure the processor300to perform various functions related to the navigation of the apparatus103(e.g. by controlling the locomotive mechanism203).

The processor300, when so configured by the execution of the application308, may also be referred to as a controller300. Those skilled in the art will appreciate that the functionality implemented by the processor300via the execution of the application308may also be implemented by one or more specially designed hardware and firmware components, such as FPGAs, ASICs and the like in other embodiments.

The memory304may also store a repository312containing, for example, a map of the environment in which the apparatus103operates, for use during the execution of the application308. The apparatus103also includes a communications interface316enabling the apparatus103to communicate with the server101(e.g. via the link105or via the dock106and the link107), for example to receive instructions to navigate to specified locations and initiate data capture operations.

FIG. 3also illustrates example components of the application308. As will be apparent to those skilled in the art, the illustrated components may be implemented as a suite of distinct applications in other embodiments. In the present example, the application308includes a preprocessor320configured to obtain image data and depth measurements and detect preliminary edges in the image data. The application308further includes a Hough line detector324configured to apply a Hough transform to the preliminary edges to detect Hough lines in the image data. The application308further includes a segmentation controller328configured to overlay the Hough lines with the depth measurements to obtain seed pixels and segment the depth measurements based on the seed pixels. The application308further includes a shelf estimator332configured to estimate the shelf edge and the shelf plane based on a class of pixels identified by the segmentation controller328. In particular, by seeding the depth measurement segmentation with Hough lines in the image data, the resultant object classes are likely to represent shelf edges. Further, the depth measurement segmentation is more tolerant of calibration errors between the image sensor and the depth sensor.

The functionality of the application308to detect shelf edges will now be described in greater detail, with reference toFIG. 4.FIG. 4illustrates a method400of detecting a shelf edge, which will be described in conjunction with its performance in the system100, and in particular by the apparatus103, with reference to the components illustrated inFIGS. 2 and 3. As will be apparent in the discussion below, in other examples, some or all of the processing performed by the server101may be performed by the apparatus103, and some or all of the processing performed by the apparatus103may be performed by the server101.

At block405, the processor300, and in particular the preprocessor320, is configured to obtain image data and depth measurements captured, respectively, by an image sensor and a depth sensor and corresponding to an area containing the support surface. In other words, in the present example, the image data and the depth measurements correspond to an area containing at least one shelf support surface117and shelf edge118. The image data and depth measurements obtained at block405are, for example, captured by the apparatus103and stored in the repository132. The preprocessor320is therefore configured, in the above example, to obtain the image data and depth measurements by retrieving the image data and depth measurements from the repository132.

In some examples, the preprocessor320can also be configured to perform one or more filtering operations on the depth measurements. For example, depth measurements greater than a predefined threshold may be discarded from the data captured at block405. Such measurements may be indicative of surfaces beyond the shelf backs116(e.g. a ceiling, or a wall behind a shelf back116). The predefined threshold may be selected, for example, as the sum of the known depth of a shelf110and the known width of an aisle.

At block410, the processor300, and in particular the preprocessor320detects preliminary edges in the image data. For example, referring toFIG. 5A, an image500of an example aisle is depicted. The aisle includes a shelf module510having support surfaces having shelf edges518-1,518-2, and518-3. The support surfaces create shadows, thus providing high contrast at the shelf edges518, and allowing edges to be readily detected from the image data. For example, the preprocessor320may employ Canny edge detection on the image data to detect the preliminary edges. In particular, the preprocessor320may generate a Canny image520, as depicted inFIG. 5B, including the preliminary Canny edges528-1,528-2, and528-3representing the shelf edges518. In other embodiments, the preprocessor320may employ other suitable edge detection models.

The Canny edge detection also detects other Canny edges, including edges of products, ends of the shelf modules, and the like. Accordingly, the processor300may further process the preliminary edges to determine which edges represent shelf edges. Returning toFIG. 4, at block415, the processor300, and in particular the Hough line detector324, applies a Hough transform on the preliminary edges detected at block410to determine Hough lines. In particular, the Hough transform determines, for each pixel position corresponding to a preliminary edge, candidate lines through that pixel position. The candidate lines through the pixel position are mapped as votes for bins in a Hough space, where each bin in the Hough space corresponds to a set of parameters defining a candidate line within the image source. For example, the parameters generally include a distance p defining the distance from the origin (in the image frame of reference) to the point on the candidate line closest to the origin. The parameters generally also include an angle θ defining the angle between the horizontal axis (i.e., the x axis) and the line connecting the candidate line to the origin. The bin having the highest number of votes defines a Hough line based on the parameters of the bin. In the present example, bins having at least a threshold number of votes may define Hough lines.

Turning toFIG. 5C, the image500is overlaid with Hough lines538determined at block415. In particular, the Hough lines538substantially overlay the shelf edges518, as well as some product edges and the vertical edges of the shelf module510. The processor300may expect that substantially vertical Hough lines detected in the image space are unlikely to represent the shelf edges518. Accordingly, the Hough line detector324may further to be configured, at block415, to perform one or more filtering operations to discard Hough lines within a threshold angle of vertical. Specifically, the Hough line detector324may be configured to determine an angle between a given Hough line and a vertical line. Hough lines having an angle below the threshold angle from vertical may be discarded. Thus, for example, the Hough line538-1may be filtered out. The remaining Hough lines538may be assumed to be candidate edges of the shelf.

Returning again toFIG. 4, at block420, the processor300, and in particular the segmentation controller328, segments the depth measurements. Specifically, the segmentation controller328is configured to assign an object class to each depth measurement, wherein each object class corresponds to a distinct object in the image data. For example, the segmentation controller328may segment the image data into a ground class representing the ground or floor of the aisle, and one or more object classes representing distinct objects in the aisle. In particular, some of the object classes may correspond to edges of the support surfaces in the aisle or products on the support surfaces.

FIG. 6depicts a method600of segmenting depth measurements as performed by the segmentation controller328. Generally, the segmentation controller328employs a segmentation algorithm to grow object classes based on a seed pixel depth measurement for each object class. More particularly, the seed pixel depth measurements are derived based on the Hough lines, and thus, the resulting object classes represent objects having linear components, such as shelf edges.

At block605, the segmentation controller328is configured to identify a plurality of seed pixels from the depth measurements. Specifically, the segmentation controller328overlays the Hough lines with the depth measurements, for example, using a predefined correspondence between the image sensor and the depth sensor. The depth measurements corresponding to Hough lines are identified as seed pixels.

In some embodiments, the segmentation controller328may further be configured to filter out the ground class of depth measurements prior to identifying seed pixels. Specifically, the segmentation controller328may select a ground seed pixel at or near the bottom of the image space (e.g. based on predefined criteria). The segmentation controller328may then grow a ground class based on the selected ground seed pixel using the segmentation algorithm as will be described further below. Thus, the seed pixels identified at block605may include depth measurements corresponding to Hough lines and not classified as ground pixels.

For example, referring toFIG. 7A, an image700representing the segmented depth measurements is depicted. The image700includes Hough lines705-1,705-2, and705-3overlaid with the depth measurements. The Hough lines705define seed pixels712-1,712-2and712-3, which define object classes710-1,710-2, and710-3. The Hough lines705also define seed pixels at other depth measurements along the Hough lines705, however, as depicted, these seed pixels are included in the object classes defined by the seed pixels712. The image700further includes a ground class720originating from a ground seed pixel722. The depth measurements in the ground class720may therefore be discarded prior to identifying or selecting seed pixels.

Returning toFIG. 6, at block610, the processor300is configured to select an unclassified object seed pixel. The seed pixel may be, for example, a seed pixel determined at block605, which is not classified as being in the ground class. The segmentation controller328is further configured to define an object class based on the selected seed pixel. In particular, the object class will be grown iteratively using the segmentation algorithm.

Having selected a seed pixel from which to grow an object class, the method600proceeds to block615to grow the object class. At block615, the segmentation controller328selects an unclassified pixel adjacent to a pixel in the object class. For example, in the first iteration, the segmentation controller328selects an unclassified pixel adjacent to the seed pixel selected at block610. The segmentation controller328then determines whether the selected adjacent pixel is part of the object class.

For example, the segmentation controller328may employ an angle segmentation algorithm, as outlined in “Efficient Online Segmentation for Sparse 3D Laser Scans” (Igor Bogoslayskyi & Cyrill Stachniss, Bonn). Specifically, given a first point and a second point in 3D space, the segmentation controller328determines an angle β between an origin in the image frame of reference, the second point, and the first point. That is, the segmentation controller328determines an angle β between a first line from the first point to the second point and a second line from the origin in the image frame of reference to the second point. When the angle β is above a threshold angle, the first point and the second point are determined to be the same object.

For example, referring toFIGS. 7A and 7B, the segmentation controller328may employ the angle segmentation algorithm to determine whether the pixel730is in the object class710defined by the seed pixel712-1. The segmentation controller328determines an angle β between the origin740, the pixel730, and the seed pixel712-1based on the depth measurements of the pixel730and the seed pixel712-1relative to the origin740.FIG. 7Bdepicts an overhead view of the angle β between the origin740, the pixel730, and the seed pixel712-1. When the angle β is above a threshold angle, the pixel730is determined to be the same object as the seed pixel712-1, and is classified as part of the object class710-1and is added to the object class.

Thus, at block615, the segmentation controller328classifies the selected adjacent pixel. Specifically, when the segmentation controller328determines that the selected adjacent pixel is part of the object class, the selected adjacent pixel is added to the object class. If the adjacent pixel is not part of the object class, the segmentation controller328may classify it to indicate that the pixel has been assessed for the current object class. The method600then proceeds to block620.

At block620, the segmentation controller328determines if there are any unclassified pixels adjacent to pixels in the current object class. If there are, the segmentation controller328returns to block615to select an unclassified adjacent pixel. Thus, the segmentation controller328iterates through adjacent pixels to grow the object class. If, at block620, there are no adjacent unclassified pixels, then the current object class is complete, and the segmentation controller328proceeds to block625.

At block625, the segmentation controller328determines if there are any unclassified seed pixels. If there are, the segmentation controller328returns to block610to select an unclassified seed pixel and define a new object class. Thus, the segmentation controller328iterates through the seed pixels to segment the depth measurements into distinct object classes. In particular, as the seed pixels are based on Hough lines, the resulting object classes represent objects having a linear component, and are likely to be shelf edges. Additional constraints may also be applied to select shelf edges, as will be described further below.

Returning toFIG. 4, at block425, the processor300, and in particular the shelf estimator332, is configured to compute an estimated edge of the support surface. Specifically, the shelf estimator332selects a class of pixels as segmented at block420as a predicted shelf edge. For example, the shelf estimator332may select the largest class of pixels satisfying predefined constraints within which a shelf edge is expected to comply. For example, the shelf estimator332may expect that a difference in height between pixels in the class and its seed pixel are within a first threshold distance (e.g. 5 cm). That is, a shelf edge is expected to have a maximum height, and hence classes having heights exceeding the first threshold distance may be discarded as potential shelf edges. Further, the shelf estimator332may expect that a distance between consecutive pixels in the class are within a second threshold distance. That is, a shelf edge is expected to have good point density.

The shelf estimator332may then apply a line-fitting model (e.g. RANSAC) to the selected class to obtain an estimated shelf edge. In some embodiments, the shelf estimator332may further obtain an estimated support surface plane (shelf plane) based on the estimated shelf edge by assuming that the shelf edge is substantially vertical, and may be represented by a vertical plane. Accordingly, the estimated shelf plane is the plane defined by the estimated shelf edge and a vertical line.

At block425, the processor300may further be configured to compute a current distance and a current yaw of the apparatus103to the shelf plane. The current distance and current yaw of the apparatus103to the shelf plane may be used in the navigation of the apparatus103, and in particular, to maintain a constant distance and yaw of the apparatus103while navigating the aisle. In particular, the processor300may add the current distance to a distance buffer including a plurality of previously computed distances, and the current yaw to a yaw buffer including a plurality of previously computed yaws. The processor300may then compute an average distance and an average yaw based, respectively, on the distance buffer and the yaw buffer. Thus, the impact of a bad shelf plane detection may be minimized by the buffer.

In some embodiments, the processor300may further be configured to fuse the output of the present shelf plane detection with one or more additional shelf plane detection methods. For example, the apparatus103may further employ a bottom shelf detector, and a point cloud shelf detector in addition to the present RGBD shelf detector.FIG. 8depicts a method800of fusing the outputs of the three detection methods.

At block805, the processor300obtains estimated support surface (shelf) plane results from the bottom shelf detector and the point cloud shelf detector.

At block810, the processor300is configured to compute an agreement score between the estimated shelf planes from the bottom shelf detector and the point cloud detector. Specifically, the processor300may determine whether distance and yaw measurements from the estimated shelf planes agree. To determine whether the measurements for two detection methods agree, the processor300computes the agreement score given by equation (1), where v and u represent the respective direction vectors reconstructed using the distance and yaw measurements from the two detection methods.

Thus, the agreement score is based on the dot product of the two vectors minus the Frobenius norm of the covariance matrix associated with each detection method.

At block815, the processor300determines which estimated shelf plane to push forwards based on the computed agreement score. Specifically, if the agreement score is above the threshold score, the processor300determines that the estimated shelf plane results from the bottom shelf point cloud detector and the point cloud shelf detector agree, and proceeds to block820. At block820, the processor300selects the estimated shelf plane from the point cloud detector as a comparison plane for the RGBD detector results. The method800then proceeds to block830.

If the agreement score computed at block810is below the threshold score, the processor300determines that the estimated shelf plane results from the bottom shelf point cloud detector and the point cloud shelf detector do not agree and proceeds to block825. At block825, the processor300selects the estimated shelf plane from the bottom shelf detector as the comparison plane for the RGBD detector results. Specifically, the processor300expects that the estimated shelf plane from the bottom shelf detector is more accurate. The method then proceeds to block830.

At block830, the processor300computes a second agreement score between the comparison plane obtained from block820or block825and the estimated shelf plane from the RGBD detector results. Specifically, the processor300computes the second agreement score based on equation (1).

At block835, the processor300determines whether to publish an estimated shelf plane based on the second computed agreement score. If the second agreement score is above the threshold score, the processor300determines that the estimated shelf plane from the RGBD detector and the comparison plane agree and proceeds to block840. At block840, the processor300selects the estimated shelf plane from the RGBD detector, for example, for navigational operations in the apparatus103.

If the second agreement score computed at block830is below the threshold score, the processor300is configured to proceed to block845. At block845, the processor300is configured to discard the results of the frame and wait for the subsequent frame.