Patent Description:
Multiple sensors can be mapped to a common frame of reference to facilitate fusing information from the multiple sensors. One way to do this is via extrinsic calibration of sensor pairs.

Existing methods survey the position and orientation (also referred to as pose) of each sensor by external means in a controlled environment (also known as a scene). Typically, the survey will use metrological methods to locate each sensor in a common reference frame. These methods can be limited by access (e.g., by using a confined space) and/or line-of-sight constraints to the sensors. In some circumstances, the sensor platform can be disassembled to enable access. Some methods use known calibration targets and other fiducials arranged in meticulously staged scenes. This translates to an expensive and time-consuming process which often cannot be performed in the field. As the actual sensor poses drift over time and the sensor(s) become misaligned, the sensor platform would have to be pulled from service to perform a new calibration.

<CIT> describes, in accordance with a machine translation of its abstract, an external parameter calibration method for a single-shot LIDAR and a panorama camera. The method comprises the following steps: fixing the LIDAR and the panorama camera on a mobile robot; then placing a plurality of chessboards in a common field of view of the LIDAR and the panoramic camera, and shooting and collecting a single frame of panoramic image and point cloud data corresponding to the frame of panoramic image at one time; then, detecting chessboard corner points of the panoramic image by utilizing a grown chessboard corner point detection algorithm; preprocessing the point cloud data, segmenting to remove the point cloud ground, segmenting a point cloud plane, and extracting chessboard point cloud; estimating chessboard corner points of the chessboard point cloud based on the reflection intensity of the point cloud; and finally, establishing a geometric constraint equation of the chessboard corner points of the panoramic image and the chessboard corner points of the point cloud by defining a common counting sequence of the corner points starting from the lower left side of the chessboard, and solving an external calibration parameter. Other related art is given by the paper of <NPL>, as well as by patent document <CIT>.

The invention to which this European patent relates is defined in the appended claims. In a particular implementation, a method includes obtaining, at one or more processors, point cloud data representing locations in three-dimensional (3D) space of points of a point cloud. The method also includes selecting for further processing by the one or more processors one or more subsets of the point cloud data based at least in part on a contour metric. The method also includes grouping, by the one or more processors, sets of points of the one or more subsets of the point cloud into one or more clusters based at least in part on one or more distance metrics, wherein all points of the one or more subsets within a predetermined Euclidean distance from a plane onto which the one or more subsets of the point cloud data have been projected are grouped. The method also includes, for a cluster that satisfies one or more cluster size criteria based on dimensions of a calibration standard, determining, by the one or more processors, whether a distribution of signal intensities of points of the cluster satisfies a distribution criterion. The method further includes, based on a determination that the distribution of signal intensities of points satisfies the distribution criterion, determining, by the one or more processors based on the cluster, boundaries of a region that represents the calibration standard and storing, by the one or more processors, data identifying a set of points of the point cloud that correspond to the calibration standard, the set of points identified based on the boundaries of the region that represents the calibration standard.

In another particular implementation, a system includes a memory configured to store instructions and one or more processors configured to obtain point cloud data representing locations in three-dimensional (3D) space of points of a point cloud. The one or more processors are further configured to select for further processing by the one or more processors one or more subsets of the point cloud data based at least in part on a contour metric. The one or more processors are further configured to group sets of points of the one or more subsets of the point cloud into one or more clusters based at least in part on one or more distance metrics, wherein all points of the one or more subsets within a predetermined Euclidean distance from a plane onto which the one or more subsets of the point cloud data have been projected are grouped. The one or more processors are also configured to, for a cluster that satisfies one or more cluster size criteria based on dimensions of a calibration standard, determine whether a distribution of signal intensities of points of the cluster satisfies a distribution criterion. The one or more processors are further configured to, based on a determination that the distribution of signal intensities of points satisfies the distribution criterion, determine, based on the cluster, boundaries of a region that represents the calibration standard and store data identifying a set of points of the point cloud that correspond to the calibration standard, the set of points identified based on the boundaries of the region that represents the calibration standard.

In another particular implementation, a non-transitory, computer readable medium stores instructions that, when executed by one or more processors, cause the one or more processors to initiate, perform, or control operations including: obtaining point cloud data representing locations in three-dimensional (3D) space of points of a point cloud. The operations also include selecting for further processing by the one or more processors one or more subsets of the point cloud data based at least in part on a contour metric. The operations also include grouping sets of points of the one or more subsets of the point cloud into one or more clusters based at least in part on one or more distance metrics, wherein all points of the one or more subsets within a predetermined Euclidean distance from a plane onto which the one or more subsets of the point cloud data have been projected are grouped. The operations further include, for a cluster that satisfies one or more cluster size criteria based on dimensions of a calibration standard, determining whether a distribution of signal intensities of points of the cluster satisfies a distribution criterion. The operations also include, based on a determination that the distribution of signal intensities of points satisfies the distribution criterion, determining, based on the cluster, boundaries of a region that represents the calibration standard and storing data identifying a set of points of the point cloud that correspond to the calibration standard, the set of points identified based on the boundaries of the region that represents the calibration standard.

The features, functions, and advantages described herein can be achieved independently in various implementations or can be combined in yet other implementations, further details of which can be found with reference to the following description and drawings.

Aspects disclosed herein present systems and methods for establishing an extrinsic relationship between a light detection and ranging (lidar) sensor and a camera. In particular, the systems and methods of the subject disclosure allow for automatic detection of a calibration standard in an unstructured lidar point cloud. To meaningfully fuse the information from multiple sensors, a common frame of reference is established to link the independent frames of reference of the multiple sensors. This can be accomplished through extrinsic calibration of sensor pairs.

The disclosed systems and methods enable mapping two or more complementary sensor systems (e.g., a 3D lidar and a camera) to a common reference frame so that the information provided by each individual sensor can be fused together to provide a more complete and robust perception of the world for autonomous systems. The disclosed system enables automatically detecting a single, simple calibration standard (e.g., a planar chessboard) in an unstructured lidar point cloud (e.g., an unstructured lidar point cloud generated by a lidar scan of a calibration scene). This can translate into a procedure which can be performed both in the field and as necessary. For example, the procedure can be performed as part of pre-flight maintenance for an aircraft.

The figures and the following description illustrate specific examples. It will be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles described herein and are included within the scope of the claims that follow this description. Furthermore, any examples described herein are intended to aid in understanding the principles of the disclosure and are to be construed as being without limitation. As a result, this disclosure is not limited to the specific embodiments or examples described below, but by the claims and their equivalents. Particular implementations are described herein with reference to the drawings. In the description, common features are designated by common reference numbers throughout the drawings.

As used herein, various terminology is used for the purpose of describing particular implementations only and is not intended to be limiting. For example, the singular forms "a," "an," and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. Further, some features described herein are singular in some implementations and plural in other implementations. To illustrate, <FIG> depicts a computing system <NUM> including one or more computing devices <NUM>, which indicates that in some implementations the system <NUM> includes a single computing device <NUM> and in other implementations the system <NUM> includes multiple computing devices <NUM>. For ease of reference herein, such features are generally introduced as "one or more" features and are subsequently referred to in the singular unless aspects related to multiple of the features are being described.

The terms "comprise," "comprises," and "comprising" are used interchangeably with "include," "includes," or "including. " Additionally, the term "wherein" is used interchangeably with the term "where. " As used herein, "exemplary" indicates an example, an implementation, and/or an aspect, and should not be construed as limiting or as indicating a preference or a preferred implementation. As used herein, an ordinal term (e.g., "first," "second," "third," etc.) used to modify an element, such as a structure, a component, an operation, etc., does not by itself indicate any priority or order of the element with respect to another element, but rather merely distinguishes the element from another element having a same name (but for use of the ordinal term). As used herein, the term "set" refers to a grouping of one or more elements, and the term "plurality" refers to multiple elements.

As used herein, "generating," "calculating," "using," "selecting," "accessing," and "determining" are interchangeable unless context indicates otherwise. For example, "generating," "calculating," or "determining" a parameter (or a signal) can refer to actively generating, calculating, or determining the parameter (or the signal) or can refer to using, selecting, or accessing the parameter (or signal) that is already generated, such as by another component or device. As used herein, "coupled" can include "communicatively coupled," "electrically coupled," or "physically coupled," and can also (or alternatively) include any combinations thereof. Two devices (or components) can be coupled (e.g., communicatively coupled, electrically coupled, or physically coupled) directly or indirectly via one or more other devices, components, wires, buses, networks (e.g., a wired network, a wireless network, or a combination thereof), etc. Two devices (or components) that are electrically coupled can be included in the same device or in different devices and can be connected via electronics, one or more connectors, or inductive coupling, as illustrative, non-limiting examples. In some implementations, two devices (or components) that are communicatively coupled, such as in electrical communication, can send and receive electrical signals (digital signals or analog signals) directly or indirectly, such as via one or more wires, buses, networks, etc. As used herein, "directly coupled" is used to describe two devices that are coupled (e.g., communicatively coupled, electrically coupled, or physically coupled) without intervening components.

<FIG> depicts an example system <NUM> for automatically detecting a calibration standard in an unstructured point cloud, in accordance with at least one embodiment of the subject disclosure. In some examples, system <NUM> includes a vehicle <NUM> configured for calibration between a pair of sensors (e.g., lidar system <NUM> and a camera <NUM>) using a calibration standard <NUM> within the sensor ranges of both camera <NUM> and lidar system <NUM>.

In some examples, vehicle <NUM> can be an aircraft, automobile, truck, or other vehicle using sensor pairs. In the same or alternative examples, vehicle <NUM> can be a structure (e.g., house, building, etc.) using sensor pairs. In further same or alternative examples, vehicle <NUM> can be a component of a vehicle, a component of a structure, and/or any combination of a vehicle, structure, component of a vehicle, or a component of a structure.

In some examples, a sensor pair of system <NUM> includes a lidar system <NUM> and a camera <NUM>, as described in more detail below. In some configurations, one or more sensors of the sensor pair (e.g., the lidar system <NUM> and/or the camera <NUM>) can be coupled to the vehicle <NUM>. In some implementations, camera <NUM> can include one or more optics <NUM> and one or more image sensor(s) <NUM> to capture some or all of the image data <NUM> from the calibration standard <NUM>.

In some examples, the sensor pair (e.g., the lidar system <NUM> and the camera <NUM>) can be calibrated using a calibration standard <NUM> within the sensor ranges of both the camera <NUM> and the lidar system <NUM>. In some configurations, the calibration standard <NUM> can include a predetermined pattern <NUM> and boundaries <NUM>. For example, calibration standard <NUM> can be a chessboard-type standard ("chessboard) comprising alternating black-and-white squares (e.g., the pattern <NUM>) within certain borders (e.g., the boundaries <NUM>). In an exemplary configuration, the dimensions of the pattern <NUM> and the boundaries <NUM> are known prior to calibration (e.g., as dimensions of calibration standard <NUM>).

In some configurations, the lidar system <NUM> includes one or more emitters <NUM> and one or more receivers <NUM>. During an exemplary operation of the example system <NUM>, at least one emitter <NUM> of the lidar system <NUM> transmits one or more transmit signal(s) toward the calibration standard <NUM> (e.g., a chessboard), while the calibration standard <NUM> is in a particular location and/or orientation. In one or more examples, the transmit signal(s) can include optical signals and/or infrared signals. The transmit signal(s) reflects off the calibration standard <NUM> to generate at least one reflection signal(s). During an exemplary operation of the example system <NUM>, the receiver(s) <NUM> of the lidar system <NUM> receive the reflection signal(s). In some configurations, the lidar system <NUM> communicates point cloud data <NUM> to the computing device(s) <NUM>. In some examples, the point cloud data <NUM> is based at least on the reflection signal(s) received by the lidar system <NUM>.

During an exemplary operation of the example system <NUM>, subsequently or simultaneously to the transmit signal(s) reflecting off the calibration standard <NUM>, the camera <NUM> captures an image of the calibration standard <NUM> to obtain the image data <NUM>. In some configurations, the camera <NUM> communicates the image data <NUM> to the computing device(s) <NUM>.

In some examples, the calibration standard <NUM> can be moved to different locations that are further or closer in distance to the lidar system <NUM> and/or the camera <NUM>. The calibration standard <NUM> can also, or alternatively, be rotated about any axis to be oriented in different orientations.

As illustrated in the example system <NUM>, the computing device(s) <NUM> are located within the vehicle <NUM>, remote from the camera <NUM> and/or the lidar system <NUM>. In some examples, the computing device(s) <NUM> can be located within the lidar system <NUM>, within the camera <NUM>, within another sensor used by the vehicle <NUM>, within another vehicle, within another sensor used by another vehicle, or at any other appropriate location. Further, in some configurations, the lidar system <NUM> and the camera <NUM> are housed together and/or mounted together on the vehicle <NUM>. In other examples, the lidar system <NUM> and the camera <NUM> are located at separate locations. Further, components of the computing device(s) <NUM> can be distributed to one or more locations without departing from the scope of the present disclosure. For example, the processor(s) <NUM> can be housed together with or located remotely from the memory <NUM>.

In some examples, the computing device(s) <NUM> receives the point cloud data <NUM> and/or the image data <NUM> one or more via interfaces <NUM>. In some configurations, the interface(s) <NUM> can include one or more input/output interface(s), as described in more detail below with reference to <FIG>.

In some examples, the computing device(s) <NUM> can store the point cloud data <NUM> and/or the image data <NUM> (e.g., in a memory <NUM>) for further processing. As described in more detail below with reference to <FIG>, the computing device(s) <NUM> can process and analyze the point cloud data <NUM> and the image data <NUM> to automatically detect the calibration standard <NUM>. In some examples, the point cloud data <NUM> represents locations in three-dimensional (3D) space of points of a point cloud. Each point of the point cloud corresponds to a location at which a transmit signal from the lidar system <NUM> reflected off various objects in a calibration scene, wherein the object in the calibration scene includes the calibration standard <NUM>).

Processing (e.g., by the processor(s) <NUM>) the point cloud data <NUM> can be resource-intensive due to the potentially large number of points of the point cloud data <NUM>. In some examples, therefore, the processor(s) <NUM> can select one or more subsets of the point cloud data <NUM> for further processing to process the point cloud data <NUM> more efficiently (e.g., to use fewer computing resources). As described in more detail below with reference to <FIG>, selecting one or more subsets of the point cloud data <NUM> can be based at least in part on a contour metric <NUM>, which can be stored in the memory <NUM>. For example, processor(s) <NUM> can select a subset of the point cloud data <NUM> based on a "difference of normals" filter, which is described in more detail below with reference to <FIG>.

<FIG> depicts a non-limiting example of a set of points of a point cloud disposed within a three-dimensional space <NUM>. In <FIG>, the point cloud corresponds to at least a portion of a calibration scene. In the example illustrated in <FIG>, the point cloud includes points representing locations within the calibration scene, including a set of points <NUM> representing a chessboard calibration standard and sets of points <NUM> and <NUM> representing other objects in the calibration scene. To process the point cloud data <NUM>, the processor(s) <NUM> perform multiple operations, as described further herein, to identify the set of points <NUM> that represents the calibration standard <NUM>. The processor(s) <NUM> apply a contour metric (e.g., a difference of normals filter) to select groups of points of the point cloud that satisfy the contour metric. In this example, the contour metric may be satisfied by points that are on a plane. The processor(s) <NUM> can also be configured to, for example, select the largest group of points with a similar contour. In the example illustrated in <FIG>, the largest group of points with a similar contour is represented by the set of points <NUM>, which the processor(s) <NUM> can select for further processing as the group of points of the point cloud that most likely corresponds to the calibration standard <NUM>.

The processor(s) <NUM> also group sets of points of the one or more subsets of the point cloud <NUM> into one or more clusters <NUM> based at least in part on one or more distance metrics <NUM>, which can be stored in the memory <NUM>. The processor(s) <NUM> groups all points of the one or more subsets of the point cloud data <NUM> that are within a predetermined Euclidean distance from a plane onto which the one or more subsets of the point cloud data <NUM> have been projected (e.g., by the processor(s) <NUM>), as described in more detail below with reference to <FIG>.

The processor(s) <NUM> determines whether a distribution of signal intensities of points of the cluster <NUM> satisfies certain distribution criteria <NUM>, which can be stored in the memory <NUM>. The processor(s) <NUM> make this determination only for one or more cluster(s) <NUM> that satisfy one or more cluster size criteria <NUM> based on dimensions of a calibration standard <NUM>. The cluster size criteria <NUM> and/or the dimensions of calibration standard <NUM> can be stored, for example, in the memory <NUM>. As an illustrative example, the processor(s) <NUM> can determine if a cluster <NUM> is larger than the diameter of a circle that would circumscribe the calibration standard <NUM>, as described in more detail below with reference to <FIG>.

The processor(s) <NUM> determines, based on the cluster(s) <NUM>, boundaries <NUM> of a region in the point cloud that represents the calibration standard <NUM>. For example, the processor(s) <NUM> can determine whether the calibration standard <NUM> is oriented in a horizontal/vertical direction or a diamond-shaped direction, as described in more detail below with reference to <FIG>. Depending on the orientation of calibration standard <NUM>, the processor(s) <NUM> can determine a plurality of lines, each line corresponding to a boundary of the boundaries <NUM> of a region in the point cloud that represents the calibration standard <NUM>, as described in more detail below with reference to <FIG>, <FIG>.

The processor(s) <NUM> determine the boundaries <NUM> of a region in the point cloud that represents the calibration standard <NUM> based on a determination that the distribution of signal intensities <NUM> of points satisfies one or more distribution criteria <NUM>. A distribution of signal intensities <NUM> and/or the distribution criteria <NUM> can be stored in the memory <NUM>. As an illustrative example, as described in more detail below with reference to <FIG>, <FIG>, the processor(s) <NUM> can determine which, if any, areas of a region in the point cloud correspond to "black" and "white" regions of a chessboard. The processor(s) <NUM> can use the "black" and "white" regions to further define the boundaries <NUM> of the region in the point cloud that represents the calibration standard <NUM>, as described in more detail below with reference to <FIG>, <FIG>.

The processor(s) <NUM> store data identifying a set of points <NUM> of the point cloud that correspond to the calibration standard <NUM> in one or more locations of the memory <NUM>. The processor(s) <NUM> identify the set of points <NUM> based on the boundaries <NUM> of the region that represents the calibration standard <NUM>.

In some examples, the processor(s) <NUM> can automatically detect the calibration standard <NUM> within an unstructured point cloud based at least on the instructions <NUM> in the memory <NUM>. As described in more detail above, the processor(s) <NUM> can also use data stored in the memory <NUM>, such as the contour metric(s) <NUM>, the distribution criteria <NUM>, the distance metric(s) <NUM>, the distribution of signal intensities <NUM>, the cluster size criteria <NUM>, and/or the dimensions of calibration standard <NUM>. Further, the processor(s) <NUM> can automatically detect the calibration standard <NUM> within an unstructured point cloud using data received from sensors, such as the camera <NUM> and/or the lidar system <NUM>. As described in more detail below with reference to <FIG>, the processor(s) <NUM> can also use other data without departing from the scope of the present disclosure.

<FIG> is a flow chart of an example of a method <NUM> for automatically detecting a calibration standard in an unstructured point cloud, in accordance with at least one example of the subject disclosure. The method <NUM> may be initiated, performed, or controlled by one or more processors executing instructions, such as by the processor(s) <NUM> of <FIG> executing the instructions <NUM> from the memory <NUM>.

In some examples, the method <NUM> includes, at block <NUM>, obtaining point cloud data representing locations in 3D space of points in a point cloud. For example, the processor(s) <NUM> of <FIG> may obtain the point cloud data <NUM> from the lidar system <NUM> or from the memory <NUM>, as described in more detail above with reference to <FIG> and below with reference to <FIG>.

In the example of <FIG>, the method <NUM> also includes, at block <NUM>, selecting for further processing one or more subsets of point cloud data based at least in part on a contour metric. For example, the processor(s) <NUM> can select a subset of the point cloud data <NUM> for further processing based on a contour metric, such as a "difference of normals" filter, as described in more detail below with reference to <FIG>.

In <FIG>, the method <NUM> further includes, at block <NUM>, grouping sets of points of the one or more subsets of the point cloud into one or more clusters based at least in part on one or more distance metrics. For example, the processor(s) <NUM> can group all points of the one or more subsets of the point cloud that are within a particular Euclidean distance from a plane onto which the one or more subsets of the point cloud have been projected, as described in more detail below with reference to <FIG>.

In <FIG>, the method <NUM> also includes, at block <NUM>, for a cluster that satisfies one or more cluster size criteria based on dimensions of a calibration standard, determining whether a distribution of signal intensities of points of the cluster satisfies one or more distribution criteria. For example, the processor(s) <NUM> of <FIG> can determine if a cluster is larger than the diameter of a circle that would circumscribe the calibration standard <NUM>, as described in more detail below and with reference to <FIG>.

For a cluster that is smaller than the diameter of the circle, the processor(s) <NUM> can determine whether a distribution of signal intensities of points of the cluster is similar to a distribution of signal intensities that would be expected to correspond to the calibration standard <NUM> based on the pattern <NUM> of the calibration standard <NUM>. For example, as described in more detail below with reference to <FIG>, <FIG>, the processor(s) <NUM> of <FIG> can determine which, if any, areas of a region in the point cloud correspond to "black" and "white" regions of a chessboard. In this example, the processor(s) <NUM> of <FIG> uses the "black" and "white" regions to further define boundaries of the region in the point cloud that represent the calibration standard <NUM>.

In <FIG>, the method <NUM> further includes, at block <NUM>, based on a determination that the distribution of signal intensities of points satisfies the one or more distribution criteria, determining, based on the cluster, boundaries of a region that represents the calibration standard. For example, the processor(s) <NUM> of <FIG> can determine whether the calibration standard <NUM> is oriented in a horizontal/vertical direction or a diamond-shaped direction, as described in more detail below with reference to <FIG>. Depending on the orientation of the calibration standard, the processor(s) <NUM> of <FIG> can determine a plurality of lines, where each line corresponds to a boundary of a region in the point cloud that represents the calibration standard, as described in more detail below with reference to <FIG>, <FIG>.

In <FIG>, the method <NUM> also includes, at block <NUM>, storing data identifying a set of points of the point cloud that correspond to the calibration standard, the set of points identified based on the boundaries of the region that represents the calibration standard, as described in more detail above with reference to <FIG>.

Although the method <NUM> is illustrated as including a certain number of steps, more, fewer, and/or different steps can be included in the method <NUM> without departing from the scope of the present disclosure. For example, the method <NUM> can begin at block <NUM> with point cloud data representing locations in 3D space of points of a point cloud already stored in memory. As an additional example, as detailed below with reference to <FIG>, operations to select subsets of points of the point cloud for further processing (as in block <NUM>) can, in certain examples, include additional steps that generally correspond to selecting for further processing one or more subsets of the point cloud data based at least in part on a contour metric. As a still further example, as detailed below with reference to <FIG>, the process of determining, based on the cluster, boundaries of a region that represents the calibration standard (as in block <NUM>) can be different depending on a variety of factors (e.g., a known orientation of the calibration standard).

<FIG> is a flow chart of another example of a method <NUM> for automatically detecting a calibration standard in an unstructured point cloud, in accordance with at least one example of the subject disclosure. The method <NUM> may be initiated, performed, or controlled by one or more processors executing instructions, such as by the processor(s) <NUM> of <FIG> executing the instructions <NUM> from the memory <NUM>.

In some examples, the method <NUM> includes, at block <NUM>, locating the calibration standard in image data. For example, the processor(s) <NUM> of <FIG> can locate the calibration standard <NUM> in the image data <NUM>. For example, image processing techniques can be used to detect pixels in the image data that correspond to the pattern <NUM> of the calibration standard <NUM>.

In the example of <FIG>, the method <NUM> also includes, at block <NUM>, projecting the point cloud onto the camera image. For example, processor(s) <NUM> of <FIG> can use a pinhole camera model to project 3D points onto an image plane using a perspective transformation. The pinhole camera model can be augmented with the camera matrix and distortion vector if available.

In <FIG>, the method <NUM> also includes, at block <NUM>, selecting all points within the point cloud corresponding to the camera image region containing the calibration standard. For example, the processor(s) <NUM> of <FIG> can select all points within the point cloud corresponding to the camera image region containing the calibration standard <NUM> to create a buffer for further processing to process the point cloud data <NUM> more efficiently.

In <FIG>, the method <NUM> also includes, at block <NUM>, clustering the selected points by range, and at block <NUM>, selecting the largest cluster in the image foreground. For example, the processor(s) <NUM> of <FIG> can generate clusters among the points selected as corresponding to the camera image region that contains the calibration standard <NUM>. In this example, some of the selected points are likely to correspond to returns from the calibration standard <NUM> and others of the selected points may correspond to foreground or background objects (e.g., the ground, a stand on which the calibration standard <NUM> rests, etc.). Grouping the selected points into clusters by range helps to distinguish returns from other objects from returns form the calibration standard <NUM>. The largest foreground cluster may be selected by computing the mean range and size of each cluster and then ranking the clusters by ascending distance and descending size. From the ranking, the processor(s) <NUM> of <FIG> can select the largest foreground cluster as an initial estimate of the portion of the point cloud most likely to contain the calibration standard.

In <FIG>, the method <NUM> also includes, at block <NUM>, accepting all points within a predetermined threshold distance of the selected cluster. For example, the processor(s) <NUM> of <FIG> can accept all points within a particular Euclidian distance from the selected cluster. Accepting all the points within a predetermined threshold distance of the selected cluster provides a set of data points representative of a portion of the point cloud, where the set of data points corresponds to an initial estimate of the location of the calibration standard <NUM> within the point cloud. The processor(s) <NUM> of <FIG> can use this initial estimate as a search space to be searched for points corresponding to the calibration standard <NUM> to increase the speed and efficiency of automatically detecting the calibration standard <NUM>.

In <FIG>, the method <NUM> also includes, at block <NUM>, applying a contour metric. For example, the processor(s) <NUM> of <FIG> can filter the selected points (e.g., the largest foreground cluster, including all points within a particular Euclidean threshold) using a contour metric such as a difference of normals operator. As illustrated below with reference to <FIG>, the processor(s) <NUM> of <FIG> can apply the contour metric(s) <NUM> to identify regions in the point cloud with a common contour. As regions of a planar calibration standard should present as a surface with a substantially similar contour (e.g., substantially flat), the application of the contour metric(s) <NUM> allows for an efficient assessment of areas within the point cloud that have a consistent contour.

In <FIG>, the method <NUM> also includes, at block <NUM>, selecting the largest set of points with a consistent contour. For example, the processor(s) <NUM> of <FIG> can select the largest set of points of consistent surface normals, as described in more detail below and with reference to <FIG>.

<FIG> is a flow chart of an example of a method <NUM> for applying a contour metric and selecting the largest set of points with consistent contour, in accordance with at least one example of the subject disclosure. In some implementations, the method <NUM> generally corresponds to blocks <NUM>-<NUM> of <FIG>. One example of applying a contour metric is applying a "difference of normals" filter, as described in more detail below. One example of selecting the largest set of points with consistent contour is selecting the largest set of consistent surface normals, as described in more detail below.

In the example of <FIG>, the method <NUM> includes, at block <NUM> computing the difference of normals for all points in the point cloud. In the same or alternative examples, applying a difference of normals filter includes computing the difference of normals for all points in a subset of the point cloud (e.g., the points in the selected largest foreground cluster and all points within a particular Euclidean threshold of the largest foreground cluster, as described in more detail above with reference to <FIG>).

In some configurations, the difference of normals operator ("Δn̂(p, r<NUM>, r<NUM>)") is defined as <MAT>, where <MAT>. In the preceding, Δn̂ is the difference of normals operator, "p" is a point in the point cloud, and "r<NUM>" and "r<NUM>" are support radii.

As an illustrative example, the processor(s) <NUM> of <FIG> can use the difference of normals operator to average the surface normals for a point (p) in the point cloud at two radii (r<NUM>, r<NUM>) from the point. For a given r<NUM> and r<NUM>, the result of applying the difference of normals ("DoN") operator to all the points in a point cloud is a vector map where a DoN vector is assigned to each point. Since each DoN is the normalized sum of two unit normal vectors, the magnitude of the DoN vectors is within [<NUM>, <NUM>]. Calculating the two normal maps estimated with support radii r<NUM> and r<NUM> for a calibration scene is a process that is highly parallelizable and thus benefits optimization of the processor(s) <NUM>.

Referring again to <FIG>, the method <NUM> also includes, at block <NUM>, accepting all points that are below a particular contour threshold. For example, the processor(s) <NUM> of <FIG> can establish one or more thresholds for the contour metric(s) <NUM> based on the magnitude and/or the component values of the contour metric(s) <NUM>. As illustrated in <FIG>, applying the difference of normals filter results in a three-dimensional point cloud smaller than the initial three-dimensional point cloud (e.g., an output Mx3 point cloud from an input Nx3 point cloud, where M <=N).

In <FIG>, the method <NUM> further includes, at block <NUM>, selecting the largest set of points with consistent contour <NUM>. In some examples, selecting the largest set of points with consistent contour <NUM> includes selecting the largest set of consistent surface normals.

In <FIG>, the method <NUM> further includes, at block <NUM>, computing the mean of the surface normals (µsn) that have not previously been identified as part of a largest set of points with consistent contour.

In <FIG>, the method <NUM> further includes, at block <NUM>, determining a set of consistent surface normals ("D"). For example, the processor(s) <NUM> of <FIG> can calculate D as <MAT> where v̂sn is the unit vector of the surface normal. The method <NUM> further includes, at block <NUM>, computing the mean ("µD") and standard deviation ("σD") for the set D. The method <NUM> further includes, at block <NUM>, accepting all points in D where the points' difference of normals are within one standard deviation of the mean (e.g., µD - σD ≤ D ≤ µD + σD). As illustrated in <FIG>, selecting the largest set of consistent surface normals results in a three-dimensional point cloud smaller than either the initial three-dimensional point cloud or the point cloud resulting from applying the difference of normals filter (e.g., an output Lx3 point cloud from an input Mx3 point cloud, where L <= M).

In <FIG>, the method <NUM> further includes, at block <NUM>, marking all accepted points as used. For example, the processor(s) <NUM> of <FIG> can indicate when a set of points has been processed to aid in the iterative processing in the entire point cloud by removing repeated processing of the same points. In <FIG>, the method <NUM> can continue to other steps in other methods that can further process and/or analyze the data output from method <NUM> (e.g., the Lx3 point cloud). For example, the processor(s) <NUM> of <FIG> can output a subset of the point cloud data <NUM>, as described in more detail below.

<FIG> is an illustrative three-dimensional graph <NUM> showing a set of points of a point cloud disposed within a three-dimensional space <NUM>, in accordance with at least one example of the subject disclosure. <FIG> is provided as an illustrative example to aid in understanding and should not be understood to limit the scope of the subject disclosure. As described above with reference to <FIG>, the point cloud includes points representing locations within the calibration scene, including a set of points <NUM> representing a chessboard calibration standard and a set of points <NUM>, <NUM> representing other objects in the calibration scene. <FIG> also illustrates a set of points <NUM> representing a part of the calibration scene itself. In <FIG>, the sets of points <NUM>, <NUM>, <NUM>, <NUM> are plotted along three-dimensional axes <NUM>, <NUM>, <NUM>.

As an illustrative example, the processor(s) <NUM> of <FIG> can be configured to select for further processing one or more subsets of the point cloud data <NUM> based at least in part on a contour metric <NUM> such as a DoN filter, as described in more detail above. Applying a contour metric <NUM> to data representative of the sets of points <NUM>, <NUM>, <NUM>, and <NUM> can aid the processor(s) <NUM> of <FIG> in selecting the appropriate subset of the point cloud data <NUM>.

For example, applying the contour metric <NUM> to set of points <NUM> indicates a single horizontal line, most of the points of which are reflective from flat surfaces (and thus of a consistent contour). Applying the contour metric <NUM> to set of points <NUM> indicates multiple horizontal lines, most of which are reflective from flat surfaces (and thus of a consistent contour). Applying the contour metric <NUM> to sets of points <NUM>, <NUM> indicates multiple horizontal lines, many of which are reflective from curved, rather than flat, surfaces (and thus of inconsistent contour). In the illustrative example, the processor(s) <NUM> can select set of points <NUM> for further processing as the largest set of points with consistent contour.

As detailed above, selecting the largest set of points with a consistent contour can increase the efficiency of analyzing an unstructured point cloud. Referring again to <FIG>, the method <NUM> can further include, at block <NUM>, fitting the selected points from the point cloud to a plane. For example, the processor(s) <NUM> of <FIG> can fit the selected points to a plane using the "Random Sample Consensus" or "RANSAC" method. In <FIG>, the method <NUM> also includes, at block <NUM>, clustering any points close to the resultant fitted plane. For example, the processor(s) <NUM> of <FIG> can determine closeness to the fitted plane based at least on one or more distance metric(s) <NUM>, including a particular Euclidean distance threshold.

In <FIG>, the method <NUM> further includes, at block <NUM>, computing a minimum spanning tree of a graph of the clusters. In some configurations, the processor(s) <NUM> of <FIG> can generate the spanning tree on a cluster basis to improve the overall efficiency of the system <NUM>. For example, generating a minimum spanning tree on a per-cluster basis (rather than a per-point basis) requires substantially fewer computing resources. A minimum spanning tree of a graph of the subset of the point cloud data <NUM> is illustrated in more detail below with reference to <FIG>.

In <FIG>, the method <NUM> further includes, at block <NUM>, selecting as a seed cluster the node from the minimum spanning tree that corresponds to the largest cluster. In some configurations, the processor(s) <NUM> of <FIG> can select the node corresponding to the largest cluster as an estimate of the cluster best representing the center of the calibration standard <NUM>.

In <FIG>, the method <NUM> further includes, at block <NUM>, growing a cluster from the seed cluster until the grown cluster is within one or more dimension(s) of the calibration standard. For example, the processor(s) <NUM> of <FIG> can be configured to grow a seed cluster along a minimum spanning tree until a first cluster size threshold of cluster size criteria <NUM> is met. In some configurations, the first cluster size threshold of cluster size criteria <NUM> can be based on a first dimension of the calibration standard (of dimensions of calibration standard <NUM>). For example, the first cluster size threshold can be based on a known diameter of a circle that would circumscribe the calibration standard <NUM>. The seed cluster can grow so long as the cluster is within the predetermined diameter, as described in more detail below with reference to <FIG>.

Growing along both directions of the minimum spanning tree identifies one or more node(s) as candidates for adding to the seed cluster. A candidate node in the minimum spanning tree is added to the seed cluster if the candidate node passes certain thresholds. In some implementations, a candidate node is added to the seed cluster if the candidate node meets certain requirements for both the size of the candidate node and the number of points in the candidate node.

For example, the processor(s) <NUM> of <FIG> can add a candidate node to the seed node only if the candidate note meets a line gate threshold and is not larger than the known diameter of a circle that circumscribes the calibration standard <NUM>. The line gate can be used to filter a candidate note that does not include sufficient points in the node. For example, the line gate can be calculated as follows: <MAT>.

The processor(s) <NUM> of <FIG> can, using the above equation, calculate the line gate ("LGate") based on the maximum expected range ("d"), the smaller dimension of the calibration standard ("W") and the azimuthal resolution of the lidar scan ("θ"). In some configurations, a threshold value for the line gate can be experimentally determined. The maximum expected range, the smaller dimension of the calibration standard, the azimuthal resolution of the lidar scan, and/or the threshold value for the line gate can be stored in memory <NUM>, e.g., as one or more dimensions of calibration standard <NUM>.

In addition to passing the line gate threshold, in some configurations a candidate node cannot exceed a particular size threshold (e.g., the known diameter of a circle circumscribing the calibration standard) to be added to the seed cluster. This can be used to filter a candidate node that is too large to correspond to the calibration standard. For example, if part of the lidar point cloud includes points corresponding to the front of a vehicle, a candidate node of points corresponding to the front of the vehicle can pass the line gate threshold but violate the size threshold. If the candidate node violates one or more thresholds (e.g., either the line gate threshold or the size threshold), then the candidate note is not added to the seed cluster. Growing along both directions of the minimum spanning tree using exemplary thresholds (e.g., a line gate threshold and a diameter threshold) is described in more detail below with reference to <FIG>.

<FIG> illustrates an exemplary minimum spanning tree <NUM> generated from a selected subset of the point cloud data <NUM>, in accordance with at least one example of the subject disclosure. <FIG> is provided as an illustrative example to aid in understanding and should not be understood to limit the scope of the subject disclosure. <FIG> illustrates certain advantages of generating a minimum spanning tree on a per-cluster basis, as detailed above with reference to <FIG>. The exemplary minimum spanning tree <NUM> includes five nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, with each node <NUM>, <NUM>, <NUM>, <NUM>, <NUM> corresponding to a cluster of points from the point cloud. The exemplary tree <NUM> also illustrates an edge <NUM> between the nodes <NUM>, <NUM>; an edge <NUM> between the nodes <NUM>, <NUM>; an edge <NUM> between the nodes <NUM>, <NUM>; and an edge <NUM> between the nodes <NUM>, <NUM>. Generating the exemplary minimum spanning tree <NUM> can include identifying the shortest path between all the nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of the tree <NUM>. By generating the exemplary minimum spanning tree <NUM> on a per-node basis rather than a per-point basis (e.g., by using a cluster of points as a node in the tree), exemplary systems and methods (e.g., system <NUM> of <FIG> and/or method <NUM> of <FIG>) can more efficiently detect a calibration standard in an unstructured point cloud.

For example, the processor(s) <NUM> of <FIG> can select the node <NUM> corresponding to the largest cluster as the seed cluster. The processor(s) <NUM> of <FIG> can then grow the seed cluster in both directions along the minimum spanning tree <NUM>, identifying the node <NUM> (along the edge <NUM>) and the node <NUM> (along the edge <NUM>) as candidate nodes to add to the seed cluster.

As described in more detail above with reference to <FIG>, to be added to the seed cluster, a candidate node should pass one or more thresholds. For example, the candidate nodes <NUM>, <NUM> would need to pass a line gate threshold and a size threshold before being added to the seed cluster. In some configurations, a size threshold can include testing whether the candidate node would grow the cluster beyond a particular size. Diagram <NUM> illustrates a plurality of potential size thresholds. Diagram <NUM> illustrates an exemplary calibration standard chessboard <NUM> of known width <NUM> and length <NUM>. One or more of width <NUM> and/or length <NUM> can be used as a size threshold. However, width <NUM> and/or length <NUM> alone can be insufficient for a two-dimensional candidate node. In some configurations, therefore, diameter <NUM> of a circle <NUM> circumscribing exemplary calibration standard chessboard <NUM> can be used (e.g., by processor(s) <NUM> of <FIG>) as a size threshold (e.g., in the method <NUM> of <FIG>).

Referring again to the exemplary candidate nodes <NUM>, <NUM>, the exemplary candidate node <NUM> can fail an exemplary size threshold, e.g., diameter <NUM>. For example, if the processor(s) <NUM> of <FIG> added the candidate node <NUM> to the node <NUM>, the resultant cluster <NUM> could be larger than the diameter <NUM> of the circle <NUM> circumscribing the calibration standard <NUM>. If the processor(s) <NUM> of <FIG> added the candidate node <NUM> to the node <NUM>, the resultant cluster <NUM> could be smaller than the diameter <NUM> of the circle <NUM> circumscribing the calibration standard <NUM>. Thus, the processors(s) <NUM> could add the candidate node <NUM> to the seed node <NUM> while rejecting the candidate node <NUM>.

In some implementations, the processor(s) <NUM> of <FIG> could continue growing the exemplary minimum spanning tree <NUM>, identifying the node <NUM> (along the edge <NUM>) as a candidate node. As described in more detail above with reference to <FIG>, a candidate node can also be subject to a line gate threshold. In <FIG>, the candidate node contains only three points. The processor(s) <NUM> of <FIG> can, therefore, reject the candidate node <NUM> for failing an exemplary line gate threshold. In some implementations, the processor(s) <NUM> of <FIG> can continue growing the exemplary minimum spanning tree <NUM> in the direction of the node <NUM>, identifying the node <NUM> (along the edge <NUM>) as a candidate node. Growth in both directions from the seed node <NUM> can continue until all the nodes <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> have been considered as candidates.

Using exemplary minimum spanning tree <NUM>, the processor(s) <NUM> of <FIG> can grow a cluster <NUM> until a first cluster size threshold of the cluster size criteria <NUM> (e.g., diameter <NUM>) is no longer violated and/or no more candidate nodes remain.

Referring again to <FIG>, the method <NUM> further includes, at block <NUM>, determining whether the cluster <NUM> meets a second cluster size threshold of the cluster size criteria <NUM>. In some configurations, the second cluster size threshold of the cluster size criteria <NUM> can be based on a second dimension of the calibration standard of the dimensions of calibration standard <NUM>. For example, the processor(s) <NUM> of <FIG> can determine whether the cluster <NUM> includes sufficient points to indicate that the cluster <NUM> corresponds to the calibration standard <NUM>. In a particular implementation, the processor(s) <NUM> of <FIG> can determine whether the cluster <NUM> includes sufficient points by applying a coarse gate.

The coarse gate can be used to filter clusters that do not include sufficient points to be considered part of the calibration standard. For example, the physical ground can manifest as a cluster of points from the lidar point cloud. However, the ground tends to manifest as long lines rather than a dense cluster. In a particular configuration, the coarse gate can be calculated as follows: <MAT>.

For example, the processor(s) <NUM> of <FIG> can calculate the coarse gate ("CGate") using the above formula, using the expected number of beams from the lidar scan ("b"), the largest dimension of the calibration standard ("L"), and the azimuthal resolution of the lidar scan ("θ"). In some configurations, the threshold value of the coarse gate can be experimentally determined. In some implementations, the expected number of beams from the lidar scan, the largest dimension of the calibration standard, the azimuthal resolution of the lidar scan, and/or the threshold value of the coarse gate can be stored at memory <NUM> and/or lidar system <NUM>.

In <FIG>, if the cluster does not meet the second cluster size threshold, the method <NUM> can return to, at block <NUM>, select the next largest set of points with consistent contour. If the cluster does meet the second cluster size threshold, the method <NUM> can continue to, at block <NUM>, apply distribution criteria to a distribution of signal intensities of points of the clusters. For example, a lidar scan from lidar system <NUM> of <FIG> can return reflectivity values for each of the points in the point cloud. The reflectivity values for the entire point cloud can form a distribution of reflectivity values (an example of signal intensity). The processor(s) <NUM> of <FIG> can apply one or more distribution criteria to classify each of the points as "black," "white," or "neither.

In some implementations, the method <NUM> can include more, fewer, and/or different processes than those illustrated in <FIG>. For example, the process described above with reference to blocks <NUM>-<NUM> can be omitted. Obtaining all points within a particular Euclidean distance of the largest foreground cluster allows for an initial estimate of the region of the point cloud in which the calibration standard <NUM> of <FIG> resides. Such an initial estimate can increase the speed and efficiency of the overall calibration process. Specifically, selecting the largest, foreground cluster of points in the point cloud for further processing can allow the processor(s) <NUM> of <FIG> to process the most likely set of points rather than the entire point cloud.

Omitting some of all of the process described with reference to blocks <NUM>-<NUM> can slow the calibration process by, for example, requiring the processor(s) <NUM> of <FIG> to analyze more of the point cloud data <NUM>. Although the processor(s) <NUM> of <FIG> can use the portions of the method <NUM> included at one or more of blocks <NUM>-<NUM> to increase efficiency, in some implementations, the processor(s) <NUM> of <FIG> can automatically detect the calibration standard within an unstructured point cloud without departing from the scope of the subject disclosure.

<FIG> is a flow chart of an example of a method <NUM> for applying distribution criteria to a distribution of signal intensities, in accordance with at least one example of the subject disclosure. In some implementations, the method <NUM> generally corresponds to block <NUM> of the method <NUM>, as described in more detail above with reference to <FIG>. In the example of <FIG>, the method <NUM> receives as input data representative of a cluster of points selected from sensor output. For example, the processor(s) <NUM> of <FIG> receive a distribution of signal intensities <NUM> corresponding to reflectivity values associated with one or more clusters <NUM>.

In <FIG>, the method <NUM> includes, at block <NUM>, computing a midpoint of the input values. In some implementations, reflectivity values from a lidar scan (e.g., by lidar system <NUM> of <FIG>) range in value from zero to <NUM>, with zero representing the lowest reflectivity and <NUM> representing the highest reflectivity. Each end of the reflectivity value range can be assigned a label. For example, values closer to zero can be designated as "black," while values closer to <NUM> can be designated as "white. " In real-world applications, reflectivity values can be closer to arbitrary values within the reflectivity value range. One approach to accounting for this difference is to compute the midpoint of the actual reflectivity values. Values on one side of the midpoint can be designated as "white," and values on the other side of the midpoint can be designated as "black. " If the classification of lidar point cloud reflectivity values is applied to points corresponding to a high-contrast calibration standard (e.g., a black-and-white chessboard), there should also be a distinct separation between the groups of points on either side of the calculated midpoint value. In some configurations, there can be a group of reflectivity values that do not belong to the designated "black" and "white" groups (e.g., points that lie within the separation region between the "black" and "white" regions). Points that correspond to reflectivity values that do not belong to the designated "black" and "white" groups can be designated as "neither.

In <FIG>, the method <NUM> also includes, at block <NUM>, selecting all the values that are less than or equal to the midpoint. For example, the processor(s) <NUM> of <FIG> can select all values in the distribution of signal intensities <NUM> that are less than or equal to the midpoint of the values in the distribution of signal intensities <NUM>. In <FIG>, the method <NUM> further includes, at block <NUM>, computing the mean and standard deviation of the values that are less than or equal to the midpoint. For example, the processor(s) <NUM> of <FIG> can compute the mean and standard deviation of the values of the distribution of signal intensities <NUM> that are less than or equal to the midpoint.

In <FIG>, the method <NUM> includes, at block <NUM>, determining if all the values are within three standard deviations ("3σ") of the calculated mean. If all the values are not within 3σ of the mean, the method <NUM> includes, at block <NUM>, removing the outliers and classifying the outliers as "neither. " If all the values are within 3σ of the mean, the method <NUM> includes, at block <NUM>, classifying the points as "black.

In <FIG>, the method <NUM> includes, at block <NUM>, selecting all values that are greater than the midpoint. In <FIG>, the method <NUM> further includes, at block <NUM>, computing the mean and standard deviation of the values that are greater than the midpoint.

In <FIG>, the method <NUM> also includes, at block <NUM>, determining whether all the values are within 3σ of the calculated mean. If all the values are not within 3σ of the mean, the method <NUM> includes, at block <NUM>, removing the outliers and classifying the outliers as "neither. " If all the values are within 3σ of the mean, the method <NUM> includes, at block <NUM>, classifying the points as "white.

In some implementations, once all the points in the cluster have been classified as "white," "black," or "neither," the method <NUM> can output the classification values for further analysis and/or processing. For example, the processor(s) <NUM> of <FIG> can refit the plane only to the "white" and "black" points, while ignoring the "neither" points. " An example of a distribution of reflectivity values is illustrated below with reference to <FIG>.

<FIG> illustrates an exemplary distribution of signal intensities <NUM>, in accordance with at least one example of the subject disclosure. <FIG> is provided as an illustrative example to aid in understanding and should not be understood to limit the scope of the subject disclosure. <FIG> illustrates a distribution of signal intensities <NUM> in a layout that generally corresponds to the exemplary minimum spanning tree <NUM> of <FIG>. However, the distribution of signal intensities <NUM> can be analyzed in any appropriate form without departing from the scope of the subject disclosure.

The exemplary distribution of signal intensities <NUM> illustrates a group <NUM> of points that returned generally similar reflectivity values. Likewise, the distribution of signal intensities <NUM> illustrates a group <NUM> of points that returned generally similar reflectivity values. As described in more detail below with reference to <FIG> and <FIG>, applying distribution criteria to the groups <NUM>, <NUM> indicates that the groups <NUM>, <NUM> return reflectivity values that fall on different ends of a reflectivity value spectrum. According to the distribution criteria, the groups <NUM>, <NUM> can be classified differently. For example, the processor(s) <NUM> of <FIG> can classify the group <NUM> as "white" and the group <NUM> as "black. " In some implementations, the computing device(s) <NUM> of <FIG> can store the distribution of signal intensities <NUM> and/or the distribution criteria <NUM> in memory <NUM>.

Although the method <NUM> and the exemplary distribution of signal intensities <NUM> use the terms "white," "black," and "neither" to describe exemplary distribution criteria, other terms can be used to denote and/or describe the distribution criteria <NUM> of <FIG> without departing from the scope of the present disclosure.

Referring again to <FIG>, the method <NUM> further includes, at block <NUM>, determining whether there is sufficient separation in the distribution of signal intensities. If there is not sufficient separation in the distribution of signal intensities, the method <NUM> includes, at block <NUM>, selecting the next largest set of points with a consistent contour, as described in more detail above. This can occur when the initial largest foreground cluster is associated with an object that does not return sensor data with sufficient contrast. For example, if another large, flat surface (e.g., a billboard, a sign, the side of a panel van, etc.) is present in a calibration scene using a black-and-white chessboard as the calibration standard <NUM> of <FIG>, the processor(s) <NUM> can select as the set of points corresponding to the other large, flat surface rather than the set of points corresponding to the calibration standard <NUM>.

If there is sufficient separation between the signal intensity values, the method <NUM> includes, at block <NUM>, refitting the plane of the points in the analyzed cluster. In some examples, the processor(s) <NUM> of <FIG> can refit the plane by re-applying the RANSAC method to the points in the analyzed cluster <NUM>. This can be done to refine the plane to which the points had previously been fitted. When the plane was previously fitted, the method <NUM> applied the fitting to the largest set of points with consistent contour (and before clustering). The earlier fit can include points that most likely do not correspond to the calibration standard. Re-applying the fit at this point can allow for a better estimate of the plane to which the appropriate points belong.

In <FIG>, the method <NUM> further includes, at block <NUM>, accepting points within a particular threshold distance to the fitted plane. The method <NUM> further includes, at block <NUM>, projecting the accepted points onto a two-dimensional plane. In some configurations, projecting the points into a two-dimensional plane can aid efficiency, both by increasing the processing speed of the processor(s) <NUM> of <FIG> (two-dimensional analysis is easier and faster than three-dimensional analysis) and helping to remove some of the noise from the sensor scan from the lidar system <NUM>.

In <FIG>, the method further includes, at block <NUM>, fitting the dimensions of the calibration standard to the accepted points. As detailed below with reference to <FIG>, in some implementations, the processor(s) <NUM> of <FIG> can apply one or more algorithm(s) to fit the dimensions of the calibration standard <NUM> to a subset of the point cloud data <NUM>. For example, the steps for fitting points from the point cloud to a vertical/horizontal-oriented chessboard can differ from the steps for fitting points from the point cloud to a diamond-oriented chessboard. As illustrative examples, <FIG> illustrates an example of a method <NUM> of fitting the points to a vertical/horizontal-oriented chessboard, while <FIG> illustrates an example of a method <NUM> of fitting the points to a diamond-oriented chessboard.

In <FIG>, the method <NUM> can include, at block <NUM>, determining whether the final fit was successful. If the fit is not successful, the method <NUM> further includes, at block <NUM>, selecting the next largest set of points with consistent contour, as described in more detail above. If the fit is successful, the method <NUM> further includes, at block <NUM>, storing data identifying a set of points that correspond to the calibration standard. For example, the computing device(s) <NUM> of <FIG> can store the set of points <NUM> in memory <NUM>. The method <NUM> can repeat some or all of the method <NUM> to identify a new calibration standard and/or the same calibration standard at a different time.

<FIG> is a flow chart of an example of a method <NUM> for fitting one or more boundaries of a calibration standard to a set of points, in accordance with at least one example of the subject disclosure. For example, the processor(s) <NUM> of <FIG> can fit one or more of the boundaries <NUM> to the set of points <NUM>. As detailed above with reference to <FIG>, the particular fitting algorithm chosen can depend on, among other things, the orientation of the calibration standard. For example, whether the standard is oriented in a substantially vertical/horizontal manner (as opposed to a substantially diamond-shaped manner) can determine which fitting algorithm applies. The method <NUM> can be used in some implementations to fit boundaries of a calibration standard for a standard in a substantially horizontal/vertical orientation. The method <NUM> can be used to fit boundaries of a calibration standard for a standard in a substantially diamond-shaped orientation.

Both of the methods <NUM>, <NUM> include substantially similar preliminary steps. Specifically, the methods <NUM>, <NUM> include substantially similar steps for determining a beam direction and fitting lines to beams. Generally, the preliminary steps include establishing an appropriate reference frame for analyzing the identified points from the lidar point cloud. For example, the methods <NUM>, <NUM> first establish the "parallel" and "perpendicular" beam directions for the lidar scan. In some configurations, the parallel beam direction is based on the azimuthal-direction scan of the lidar. Certain <NUM>-degree scanning lidars consider the <NUM>-degree scanning direction to be the azimuth scan regardless of the physical orientation of the lidar. The elevation direction corresponds to the "perpendicular" beam direction. Elevation scan data can be added in multiple ways. For example, the lidar can include a laser that scans in a random vertical pattern. In other examples, the lidar can include multiple lasers in a fixed orientation. In real-world application, lidar can have any orientation with respect to the physical world (e.g., mounted at an angle or upside down). By establishing the analysis reference frame with respect to the parallel and perpendicular beam directions, the methods <NUM>, <NUM> can ignore the physical orientation of the sensor with respect to the physical world.

In <FIG>, the method <NUM> includes, at block <NUM>, finding all pairs of points that are within a particular Euclidean distance threshold from one another. The method <NUM> also includes, at block <NUM>, creating commonly-oriented unit vectors between the pairs of close points. For the purposes of the methods <NUM>, <NUM>, "commonly oriented" means that vectors with direction θ and θ + π should be considered the same.

In some configurations, the densest concentration of vector directions should correspond to the parallel beam direction. In <FIG>, the method <NUM> includes, at block <NUM>, computing the histogram of the vector directions and, at block <NUM>, selecting the mean of the largest bin. In some implementations, computing the histogram of the vector directions and selecting the mean of the largest bin can enable the processor(s) <NUM> of <FIG> to identify the densest concentration of vector directions and thus the parallel beam direction. For example, due to the scanning nature of the lidar system <NUM> of <FIG>, the azimuthal point spacing can be much denser than the elevation point spacing. Further, lidar beams from the lidar system <NUM> can generally manifest across the surface of certain calibration standards <NUM> (e.g., chessboards) as approximately straight lines. This can allow the processor(s) <NUM> to establish the parallel beam direction ("v̂para =< px, py >"), where px, py represent points between which are a unit vector direction at the mean of the largest bin of the histogram.

Once the parallel beam direction is established, the processor(s) <NUM> of <FIG> can determine the perpendicular beam direction by solving the system of equations: v̂perp = < vx, vy >; v̂parav̂para = <NUM>; |v̂perp| = <NUM>. The solution is illustrated in the equation below: <MAT>.

In <FIG>, the method <NUM> also includes, at block <NUM>, fitting a line to each lidar beam crossing the point cluster. The method <NUM> can include, at block <NUM>, selecting all the pairs of points close to the beam direction. In some configurations, the processor(s) <NUM> of <FIG> can use the histogram bin that was chosen as the parallel beam direction ("b[<NUM>]") to select an additional number of candidate bins on either side of the selected bin. For example, the processor(s) <NUM> of <FIG> can select eight additional candidate bins (four on each side of b[<NUM>]). The processor(s) <NUM> of <FIG> can further use the candidate bins from each side until the drop-off between consecutive bins on a side is beyond a particular threshold. For example, the processor(s) <NUM> of <FIG> can establish a threshold ("Tdrop") such that <MAT>. The processor(s) <NUM> can accept candidate bins until the drop-off violates the threshold (e.g., when <MAT> Tdrop, i < j). The processor(s) <NUM> can cluster all the points from the accepted bin to remove any isolated points. The processor(s) <NUM> can then generate a set of points to which to fit lines ("Sfit").

In <FIG>, the method <NUM> includes, at block <NUM>, clustering the points in Sfit. For example, the processor(s) <NUM> of <FIG> can generate a single linkage, hierarchical clustering of the points in Sfit. The method <NUM> further includes, at block <NUM>, determining an appropriate cut distance. For example, the processor(s) <NUM> of <FIG> can find the first cluster that exceeds the line gate threshold in size, and then cut midway between this cluster and the next. Generating a cut line in this manner can better allow for non-uniform beam spacing of the relevant sensor. In the same or alternative implementations, cut lines can be generated through alternative methods that would be apparent to one of ordinary skill in the art.

In <FIG>, the method <NUM> also includes, at block <NUM>, fitting lines to the points of the cluster. In some implementations, the processor(s) <NUM> of <FIG> can use the RANSAC method to fit a line to a cluster when three or more points are available. In the same or alternative implementations, the processor(s) <NUM> of <FIG> can use a first order polynomial fit when fewer than three points are available. In some configurations, a refined line is fit in the same way to the points close to the cluster, resulting in a candidate line pci and v̂ci with associated metadata [E<NUM> M E<NUM>], where pci is a point on the ith candidate line, v̂ci is the unit vector giving the direction of the line, Ei are the edge points of the line (taken from Sfit) and M is the midpoint of the line.

<FIG> illustrates an exemplary line-to-beam fitting <NUM> for lines fitted to points clustered hierarchically along the beam direction, in accordance with at least one example of the subject disclosure. Exemplary fitting <NUM> is provided as an illustrative example to aid in understanding and is not intended to limit the scope of the subject disclosure. <FIG> illustrates a plurality of fitted lines <NUM>, <NUM> that have been fitted to the clustered points. As illustrated in <FIG>, the fitted lines <NUM> are substantially parallel, while the fitted line <NUM> is not. As described in more detail below with reference to <FIG>, the line <NUM> can, in some implementations, be rejected due to lack of appropriate orientation.

Referring again to <FIG>, the method <NUM> includes, at block <NUM>, ensuring that each line is unique. In some implementations, the test for uniqueness can include two parts. For example, the processor(s) <NUM> of <FIG> first checks whether pci falls near a line in a unique set ("Slines"). If it does, the processor(s) <NUM> can eliminate pci because the candidate line is either too similar to the unique set or a cross beam line. In some configurations, the processors(s) perform this proximity test by computing Tline = (pci - puj) × v̂uj, ∀ i ∈ candidate set, ∀ j ∈ unique set. If Tline < Tthresh, where Tthresh is a particular threshold value, then the candidate line falls too near a line in the unique set and the processor(s) <NUM> can reject the candidate line. The processor(s) <NUM> can also perform a second check of whether v̂ci is parallel with a line in the unique set. In some configurations, the processor(s) <NUM> can perform this parallel test by computing Tpara = v̂ci × v̂uj, ∀ i ∈ candidate set, ∀ j ∈ unique set. If Tpara < Tthresh, then the candidate line is insufficiently parallel to a line in the unique set and the processor(s) <NUM> can reject the candidate line.

Although each beam can appear visually parallel, there can be sufficient variation in direction to reject lines as insufficiently parallel. For example, referring again to <FIG>, any of the lines <NUM> can generate Tpara < Tthresh, while line <NUM> can generate Tpara > Tthresh. Thus, for example, the processor(s) <NUM> of <FIG> would pass lines <NUM> under the second uniqueness check and reject line <NUM> under the second uniqueness check.

Referring again to <FIG>, if a candidate line is considered unique, the processor(s) <NUM> of <FIG> can add the candidate line to the unique set, Slines. Additionally, in some implementations, the processors(s) <NUM> can mark all points close to the candidate line as used. In some configurations, the processor(s) can use one or more threshold(s) to determine whether a point is close to a candidate line. As an illustrative example, determining whether a point should be included in Sused can include two separate thresholds. Multiple thresholds can be used depending on real-world considerations of the particular sensor pair being calibrated. For example, the VLP32-C lidar has non-uniform beam spacing. The VLP32-C is manufactured by Velodyne™ LiDAR (Velodyne is a registered trademark of Velodyne LiDAR, Inc. of San Jose California, USA).

In areas where the beam density is very high, the method <NUM> can fit lines that span multiple lidar beams but are still close enough to the parallel direction to be accepted. In such a configuration, the method <NUM> can choose between using a "loose" threshold or a "tight" threshold to prevent large gaps between segments of points used to fit the line. To determine which threshold to use, the method <NUM> can first project all the points passing the loose threshold onto the line, noting that Ptight ⊂ Ploose, and determine which points also pass the tight threshold. The method <NUM> can (e.g., by processor(s) <NUM> of <FIG>) also determine an exemplary threshold, Tσ = max (std(Ptight),std(Ploose)) and sum all gaps that are greater than Tσ for both Ploose and Ptight. In a particular implementation, the method <NUM> can use the tight threshold whenever Gtight < <NUM> * Gloose, where Gtight = ∑ Ptight ∀ Ptight > Tσ and Gloose = ∑ Ploose ∀ Ploose > Tσ. Otherwise, the method <NUM> can use the loose threshold.

In <FIG>, the method <NUM> can include, at block <NUM>, determining whether all pairs of points have been used. If not all the pairs have been used, the method <NUM> can include, at block <NUM>, re-clustering the pairs close to the beam direction. If all the pairs of points have been used, the method <NUM> includes, at block <NUM>, filtering lines that are too far from the parallel beam direction and too short for membership in the calibration standard region. For example, the processor(s) <NUM> of <FIG> can, for each line, calculate coordinates in a new measurement space. For example, the processor(s) <NUM> can, for each line "uj" in a set of lines "u," calculate coordinates comprising (<NUM>) a difference ("Δθ") between the orientation of the beam direction ("v̂beam") and the line's orientation ("v̂uj"); and (<NUM>) a difference ("ΔL") between the line's length ("Luj") and the median of all line lengths ("Lu"). In a particular configuration, the processor(s) <NUM> can calculate the coordinates according to the following equations: <MAT> <MAT>.

In some configurations, the processor(s) <NUM> of <FIG> can calculate line lengths (e.g., Lu, Luj) based on the endpoints of the lines "uj" in the set of lines "u. " As described in more detail above, metadata associated with each line can include the line's endpoints and midpoint. In some implementations, the metadata can be stored at memory <NUM>.

In the new measurement space, the origin point (i.e., (<NUM>,<NUM>)) can represent an ideal value. In some examples, the method <NUM> can include, at block <NUM>, rejecting any line(s) whose distance from the ideal is beyond a predetermined threshold. For example, the processor(s) <NUM> of <FIG> can reject any line whose distance from the origin is greater than one. <FIG> below illustrates an exemplary plotting of fitted lines (e.g., lines <NUM>, <NUM> of <FIG>) within this measurement space.

<FIG> illustrates an exemplary plotting <NUM> of coordinates associated with fitted lines, in accordance with at least one example of the subject disclosure. Exemplary plotting <NUM> is provided as an illustrative example to aid in understanding and is not intended to limit the scope of the subject disclosure. Exemplary plotting <NUM> includes a plurality of points <NUM> and <NUM> plotted according to the coordinates described in more detail above with reference to <FIG>. For example, the plurality of points <NUM> and <NUM> generally correspond to the lines <NUM> and <NUM> of <FIG>, respectively. Each of the lines <NUM> and <NUM> can have coordinates corresponding to each line's respective Δθ and ΔL values. <FIG> illustrates each of the plurality of points <NUM> and <NUM> plotted according to its Δθ and ΔL coordinates, where the axis <NUM> corresponds to a range of Δθ values and the axis <NUM> corresponds to a range of ΔL values. As both the Δθ and ΔL values are normalized, the range of Δθ and ΔL values fall between zero and one. After plotting, each of the points <NUM> and <NUM> has a respective Euclidean distance from the origin of exemplary plotting <NUM>.

In <FIG>, the plurality of points <NUM> are generally associated with the lines <NUM> of <FIG>, and the point <NUM> is generally associated with the line <NUM> of <FIG>. As described in more detail above with reference to <FIG>, the lines <NUM> pass a direction and/or length filter, while the line <NUM> fails a direction and/or length filter. In <FIG>, the point <NUM> is notably farther from the origin point of the plotting <NUM> than the points <NUM>. As noted above, if one or more of the points <NUM> and <NUM> are at a distance from the origin that is greater than a particular threshold (e.g., one), then the line corresponding to the points <NUM> and <NUM> can be filtered out.

Referring again to <FIG>, the method <NUM> also includes, at block <NUM>, sorting the lines that are perpendicular to the beam direction. In some implementations, the processor(s) <NUM> of <FIG> can sort all the lines in Slines along the perpendicular beam direction by projecting the midpoint of each line onto v̂perp. This can enable the processor(s) <NUM> to sort the lines by distance to generate a defined top and bottom. In <FIG>, the method <NUM> also includes, at block <NUM>, selecting a midpoint line as a seed line for growing the region corresponding to the calibration standard. In some implementations, this selection can include selecting the line corresponding to the median of the projected lines. Generally, selecting the seed line in this manner allows for growth of the region corresponding to the calibration standard to begin approximately in the middle of the region.

<FIG> illustrates an exemplary cluster <NUM> with lines fitted to the points of the cluster, in accordance with at least one example of the subject disclosure. Exemplary cluster <NUM> is provided as an illustrative example to aid in understanding and is not intended to limit the scope of the subject disclosure. Exemplary cluster <NUM> illustrates the identified standard region corresponding to the selected set of points as described in more detail above with reference to <FIG>, as well as the standard region described in more detail below with reference to <FIG>.

Exemplary cluster <NUM> illustrates a number of candidate line endpoints <NUM>. Each of the candidate line endpoints <NUM> corresponds to an endpoint of a candidate line, as described in more detail above with reference to <FIG>. Additionally, exemplary cluster1200 illustrates seed line endpoints <NUM>. Seed line endpoints correspond to the endpoints of the candidate line that was selected as the midpoint line, as described in more detail above with reference to block <NUM> of <FIG>. Further, exemplary cluster <NUM> illustrates seed line midpoint <NUM>. Seed line midpoint <NUM> generally corresponds to the midpoint of the candidate line that was selected as the midpoint line, as described in more detail above with reference to block <NUM> of <FIG>.

Exemplary cluster <NUM> illustrates a candidate line (e.g., the line defined by endpoints <NUM> and midpoint <NUM>) that has been selected as the seed line for growing the identified standard region. As illustrated, the seed line is approximately in the middle of the standard region. Referring again to <FIG>, the method <NUM> includes, at block <NUM>, growing from the seed line until all candidate lines have been used or the expected dimensions of the standard have been filled. In some implementations, the processor(s) <NUM> of <FIG> can iteratively grow from the seed line in both directions along v̂perp, the perpendicular beam direction. For example, at each iteration, the processor(s) <NUM> of <FIG> can select the growth direction by determining the next candidate line whose length is closest to the current mean length of all lines in the standard region. If the next lines in both directions are significantly different from the mean line length, the processor(s) <NUM> can skip the line and continue with the next line (if available) as the candidate growth direction.

After determining the growth direction, the processor(s) <NUM> of <FIG> can determine whether including a candidate line grows the standard region beyond the known boundaries of the standard. For example, the processor(s) <NUM> can determine whether including a candidate line grows beyond the known diameter of the circle that circumscribes the calibration standard (e.g., diameter <NUM> of <FIG>) as well as the standard's known length and/or width (e.g., length <NUM> and/or width <NUM> of <FIG>). If the candidate line fits within the dimensional constraints, the processor(s) <NUM> of <FIG> can ensure that all points in the cluster are accounted for. For example, the processor(s) <NUM> can determine if all points in the cluster are contained in Sused. If there are no missing points, the processor(s) <NUM> can include the candidate line and can incorporate the candidate line's length into the mean line length.

Referring again to <FIG>, the method <NUM> includes, at block <NUM>, establishing the top and bottom boundaries of the cluster. In some implementations, the processor(s) <NUM> of <FIG> can establish the top and bottom boundaries <NUM> of a cluster <NUM> by identifying the two accepted candidate lines that are the farthest from the seed line in each direction along the perpendicular beam direction (v̂perp). In <FIG>, the method <NUM> further includes, at block <NUM>, fitting lines for perpendicular bounds. For example, to fully identify the cluster <NUM> as corresponding to the calibration standard <NUM>, the processor(s) <NUM> can also identify the boundary lines of boundaries <NUM> along the parallel beam direction (v̂para).

In some implementations, identifying the boundary lines along the parallel beam direction includes dividing all the accepted edge points (e.g., all the points along the top and bottom boundary lines) into "left half" and "right half" edges with respect to the parallel beam direction. In some examples, it can be sufficient to determine the separate groupings rather than identifying the left and right halves. In some configurations, the processor(s) <NUM> of <FIG> can determine the left half and right half groupings by selecting a random edge ("Erand") and computing the distance to all other edges, as shown in the equations below: <MAT> <MAT>.

In the above equations, "E<NUM>" and "E<NUM>" correspond to the endpoints of a candidate line, and "Side <NUM>" and "Side <NUM>" correspond to a first vertical side and a second vertical side, respectively. For example, in some configurations, "Side <NUM>" can correspond to a "left" vertical side, while in other configurations, "Side <NUM>" can correspond to a "right" vertical side.

The processor(s) <NUM> of <FIG> can fit a series of lines to the left half edges using a strategy similar to that described in more detail above with reference to blocks <NUM>-<NUM> of <FIG>. This strategy can include selecting the line within the cluster <NUM> with the best combination of (<NUM>) matching the perpendicular beam direction and (<NUM>) fitting the most edge points of the bottom boundary line. The processor(s) <NUM> of <FIG> can accept the line best meeting these two criteria as a third boundary line. A similar procedure performed on the right half can yield the final boundary line. Collectively, these four boundary lines can define a region in the point cloud in which the calibration standard <NUM> resides.

Referring again to <FIG>, exemplary cluster <NUM> illustrates the lines <NUM>, <NUM>, <NUM>, <NUM> that have been accepted as the boundaries for the standard region. In <FIG>, the cluster <NUM> has a top (or first) boundary line <NUM>, a bottom (or second) boundary line <NUM>, a left (or third) boundary line <NUM>, and a right (or fourth) boundary line <NUM>. The combination of the boundary lines <NUM>, <NUM>, <NUM>, <NUM> provide a bounding quadrilateral for the region in the point cloud in which the calibration standard resides.

Referring again to <FIG>, the method <NUM> further includes, at block <NUM>, accepting all points near or inside the boundaries defined by the boundary lines. For example, the processor(s) <NUM> of <FIG> can accept all points near or inside the bounding quadrilateral provided by the boundary lines <NUM>, <NUM>, <NUM>, <NUM> of <FIG>. In some configurations, the processor(s) <NUM> of <FIG> can identify points as near the boundary lines <NUM>, <NUM>, <NUM>, <NUM> of <FIG> by identifying points that are within a predetermined Euclidian distance from each of the boundary lines <NUM>, <NUM>, <NUM>, <NUM>. In some configurations the processor(s) <NUM> of <FIG> can also identify the set of points <NUM> that are near or inside the bounding quadrilateral. In some implementations, the boundary lines <NUM>, <NUM>, <NUM>, <NUM> and/or the set of points <NUM> can be stored at memory <NUM> of <FIG>.

Although the method <NUM>, the exemplary line-to-beam fitting <NUM>, the exemplary plotting <NUM>, and the exemplary cluster <NUM> use the terms "left" and "right" to describe grouping of points, other terms can be used to denote and/or describe the groupings of points, clusters, lines, endpoints, edges, boundary lines, etc. without departing from the scope of the present disclosure.

<FIG> is a flow chart of an example of another method <NUM> for fitting one or more boundaries of a calibration standard to a set of points, in accordance with at least one example of the subject disclosure. As detailed above with reference to <FIG>, the particular fitting algorithm chosen can depend on, among other things, the orientation of the calibration standard. For example, whether the standard is oriented in a substantially vertical/horizontal manner (as opposed to a substantially diamond-shaped manner) can determine which fitting algorithm applies. The method <NUM> can be used to fit boundaries of a calibration standard in a substantially horizontal/vertical orientation. The method <NUM> can be used to fit boundaries of a calibration standard in a substantially diamond-shaped orientation.

Both the methods <NUM>, <NUM> include substantially similar preliminary steps. Generally, the preliminary steps include establishing an appropriate reference frame for analyzing the identified points from the lidar point cloud. For example, the method <NUM> includes, at blocks <NUM>-<NUM>, a process substantially similar to the process described in more detail above with reference to <FIG>.

In <FIG>, the method <NUM> also includes, at block <NUM>, sorting the lines that are perpendicular to the beam direction. For example, the processor(s) <NUM> of <FIG> can sort all the lines in Slines along the perpendicular beam direction by projecting the midpoint of each line onto v̂perp. This can enable dividing the edges into "left half" and "right half" clusters with respect to the parallel beam direction. In <FIG>, the method <NUM> includes, at block <NUM>, dividing the edges into left and right in the parallel direction. In some implementations, the processor(s) <NUM> of <FIG> can divide the edges into left and right halves by first establishing left and right edges. In a particular implementation, the processor(s) <NUM> can identify the "left half" edges ("Eleft") and the "right half" edges ("Eright") using the formulas below: <MAT> <MAT>.

In <FIG>, the method <NUM> also includes, at block <NUM>, selecting left and right inflection points. In a particular implementation, the processor(s) <NUM> of <FIG> can find the left inflection point (Ileft) by calculating Ileft = min (ProjEleft) ∀E ∈ {Eleft}. Similarly, the processor(s) <NUM> can find the right inflection point (Iright) by calculating Iright = min (ProjEright) ∀E ∈ {Eright}. The method <NUM> further includes, at block <NUM>, dividing the "left half" edges of the cluster into a first group on one side of the left inflection point and a second group on the other side of the left inflection point. The method <NUM> also includes, at block <NUM>, dividing the "right half" edge of the cluster into a first group on one side of the right inflection point and a second group on the other side of the right inflection point.

In <FIG>, the method <NUM> also includes, at block <NUM>, fitting lines to four sets of edges. In some implementations, the processor(s) <NUM> of <FIG> can fit lines to four sets of edges according to the left and right inflection points. For example, the processor(s) <NUM> can calculate the sets of endpoints corresponding to each of the four sides ("S<NUM>", "S<NUM>", "S<NUM>", "S<NUM>") according to the following formulas: <MAT> <MAT> <MAT> <MAT>.

Identifying the sets of endpoints corresponding to each of the four sides can allow the processor(s) <NUM> to fit lines to each set of endpoints, therefore identifying the sides of a bounding quadrilateral for the cluster <NUM>, as described in more detail below with reference to block <NUM>.

<FIG> illustrates another exemplary cluster <NUM> with lines fitted to the points of the cluster, in accordance with at least one example of the subject disclosure. Exemplary cluster <NUM> is provided as an illustrative example to aid in understanding and is not intended to limit the scope of the subject disclosure. The exemplary cluster <NUM> illustrates a left inflection point <NUM> and a right inflection point <NUM>. The left inflection point <NUM> and right inflection point <NUM> generally correspond to the inflection points identified by method <NUM>, as described in more detail above with reference to <FIG>.

The exemplary cluster <NUM> also depicts a plurality of points that can potentially correspond to one or more of the four sides that provide a bounding quadrilateral of the cluster <NUM>. For example, the exemplary cluster <NUM> illustrates a set of points that includes a point <NUM> on one side of the left inflection point <NUM>, where the point <NUM> corresponds to a first side (e.g., S<NUM>). Cluster <NUM> also illustrates a set of points that includes the points <NUM>-<NUM> on the other side of the left inflection point <NUM>, where the points <NUM>-<NUM> correspond to a second side (e.g., S<NUM>). Cluster <NUM> also illustrates a set of points <NUM>-<NUM> on one side of the right inflection point <NUM>, where the points <NUM>-<NUM> correspond to a third side (e.g., S<NUM>). Cluster <NUM> also illustrates a set of points <NUM>-<NUM> on the other side of the right inflection point <NUM>, where the points <NUM>-<NUM> correspond to a fourth side (e.g., S<NUM>).

Referring again to <FIG>, the method <NUM> also includes, at block <NUM>, fitting lines to each set of points. In some implementations, the processor(s) <NUM> of <FIG> can fit lines to each side using the RANSAC method, a first order polynomial fit, and/or other fitting technique as appropriate. For example, referring against to <FIG>, fitting a line corresponding to the point <NUM> can use a first order polynomial fit, as there is only one point in the set of points corresponding to the first side (e.g., one point on one side of the left inflection point <NUM>). Fitting a line corresponding to the set of points <NUM>-<NUM> can use the RANSAC method, as there are eight points corresponding to the second side (e.g., eight points one the other side of the left inflection point <NUM>). In some configurations, fitting lines to each side can be an iterative process to ensure at least a minimum number of points match the fit. This minimum number of points can be determined by reference to a particular threshold.

Referring again to <FIG>, the exemplary cluster <NUM> depicts the lines <NUM>, <NUM>, <NUM>, and <NUM> that have been fitted to various points on either side of the inflection points <NUM> and <NUM>. In some implementations, the fitted lines can include a first line boundary <NUM> fitted to the point <NUM>, a second boundary line <NUM> fitted to the set of points <NUM>-<NUM>, a third boundary line <NUM> fitted to the set of points <NUM>-<NUM>, and a fourth boundary line <NUM> fitted to the set of points <NUM>-<NUM>. The combination of the boundary lines <NUM>, <NUM>, <NUM>, and 1412provide a bounding quadrilateral for the region in the point cloud in which the calibration standard resides.

Referring again to <FIG>, the method <NUM> further includes, at block <NUM> accepting all points near or inside the boundaries defined by the boundary lines. For example, the processor(s) <NUM> of <FIG> can accept all points near or inside the bounding quadrilateral provided by the boundary lines <NUM>, <NUM>, <NUM>, and 1412of <FIG>. In some configurations, the processor(s) <NUM> of <FIG> can identify points near the boundary lines <NUM>, <NUM>, <NUM>, and <NUM> by identifying points that are within a predetermined Euclidian distance from each of the boundary lines <NUM>, <NUM>, <NUM>, and <NUM>. In some configurations the processor(s) <NUM> of <FIG> can also identify the set of points <NUM> of <FIG> that are near or inside the bounding quadrilateral. In some implementations, the boundary lines <NUM>, <NUM>, <NUM>, and <NUM> of <FIG>and/or the set of points <NUM> of <FIG> can be stored at the memory <NUM> of <FIG>.

Although the method <NUM> and the exemplary cluster <NUM> use the terms "left" and "right" to describe grouping of points, other terms can be used to denote and/or describe the groupings of points, clusters, lines, endpoints, edges, boundary lines, inflection points, etc. without departing from the scope of the present disclosure.

<FIG> is a block diagram of a computing environment <NUM> including a computing device <NUM> configured to support aspects of computer-implemented methods and computer-executable program instructions (or code) according to the present disclosure. For example, the computing device <NUM>, or portions thereof, is configured to execute instructions to initiate, perform, or control one or more operations described in more detail above with reference to <FIG>. In a particular aspect, the computing device <NUM> can include the computing device(s) <NUM>, the camera <NUM>, and/or the lidar system <NUM> of <FIG>, one or more servers, one or more virtual devices, or a combination thereof.

The computing device <NUM> includes one or more processors <NUM>. In a particular aspect, the processor(s) <NUM> correspond to the processor(s) <NUM> of <FIG>. The processor(s) <NUM> is configured to communicate with system memory <NUM>, one or more storage devices <NUM>, one or more input/output interfaces <NUM>, one or more communications interfaces <NUM>, or any combination thereof. The system memory <NUM> includes volatile memory devices (e.g., random access memory (RAM) devices), nonvolatile memory devices (e.g., read-only memory (ROM) devices, programmable read-only memory, and flash memory), or both. The system memory <NUM> stores an operating system <NUM>, which can include a basic input/output system for booting the computing device <NUM> as well as a full operating system to enable the computing device <NUM> to interact with users, other programs, and other devices. The system memory <NUM> stores system (program) data <NUM>, such as the instructions <NUM>, the contour metric(s) <NUM>, the distribution criteria <NUM>, the distance metric(s) <NUM>, the distribution of signal intensities <NUM>, the cluster size criteria <NUM>, the dimensions of calibration standard <NUM>, the set of points <NUM>, the subsets of the point cloud data <NUM>, the clusters <NUM>, the boundaries <NUM>, the image data <NUM>, the point cloud data <NUM> of <FIG>, or a combination thereof.

The system memory <NUM> includes one or more applications <NUM> (e.g., sets of instructions) executable by the processor(s) <NUM>. As an example, the one or more applications <NUM> include the instructions <NUM> executable by the processor(s) <NUM> to initiate, control, or perform one or more operations described with reference to <FIG>. To illustrate, the one or more applications <NUM> include the instructions <NUM> executable by the processor(s) <NUM> to initiate, control, or perform one or more operations described with reference to the set of points <NUM>, the subsets of the point cloud data <NUM>, the clusters <NUM>, the boundaries <NUM>, or a combination thereof.

In a particular implementation, the system memory <NUM> includes a non-transitory, computer readable medium (e.g., a computer-readable storage device) storing the instructions <NUM> that, when executed by the processor(s) <NUM>, cause the processor(s) <NUM> to initiate, perform, or control operations to automatically detect a calibration standard in an unstructured lidar point cloud.

The operations include obtaining point cloud data representing locations in three-dimensional (3D) space of points of a point cloud. The operations also include selecting for further processing by the one or more processors one or more subsets of the point cloud data based at least in part on a contour metric. The operations also include grouping sets of points of the one or more subsets of the point cloud into one or more clusters based at least in part on one or more distance metrics. The operations further include, for a cluster that satisfies one or more cluster size criteria based on dimensions of a calibration standard, determining whether a distribution of signal intensities of points of the cluster satisfies a distribution criterion. The operations also include, based on a determination that the distribution of signal intensities of points satisfies the distribution criterion, determining, based on the cluster, boundaries of a region that represents the calibration standard and storing data identifying a set of points of the point cloud that correspond to the calibration standard, the set of points identified based on the boundaries of the region that represents the calibration standard.

The one or more storage devices <NUM> include nonvolatile storage devices, such as magnetic disks, optical disks, or flash memory devices. In a particular example, the storage devices <NUM> include both removable and non-removable memory devices. The storage devices <NUM> are configured to store an operating system, images of operating systems, applications (e.g., one or more of the applications <NUM>), and program data (e.g., the program data <NUM>). In a particular aspect, the system memory <NUM>, the storage devices <NUM>, or both, include tangible computer-readable media. In a particular aspect, one or more of the storage devices <NUM> are external to the computing device <NUM>.

The one or more input/output interfaces <NUM> enable the computing device <NUM> to communicate with one or more input/output devices <NUM> to facilitate user interaction. For example, the one or more input/output interfaces <NUM> can include a display interface, an input interface, or both. For example, the input/output interface <NUM> is adapted to receive input from a user, to receive input from another computing device, or a combination thereof. In some implementations, the input/output interface <NUM> conforms to one or more standard interface protocols, including serial interfaces (e.g., universal serial bus (USB) interfaces or Institute of Electrical and Electronics Engineers (IEEE) interface standards), parallel interfaces, display adapters, audio adapters, or custom interfaces ("IEEE" is a registered trademark of The Institute of Electrical and Electronics Engineers, Inc. of Piscataway, New Jersey). In some implementations, the input/output device(s) <NUM> include one or more user interface devices and displays, including some combination of buttons, keyboards, pointing devices, displays, speakers, microphones, touch screens, and other devices. In a particular aspect, the input/output device(s) <NUM> include the interface(s) <NUM> of <FIG>.

The processor(s) <NUM> are configured to communicate with devices or controllers <NUM> via the one or more communications interfaces <NUM>. For example, the one or more communications interfaces <NUM> can include a network interface. The devices or controllers <NUM> can include, for example, the camera <NUM>, the lidar system <NUM> of <FIG>, one or more other devices, or any combination thereof.

In some implementations, a non-transitory, computer readable medium (e.g., a computer-readable storage device) stores instructions that, when executed by one or more processors, cause the one or more processors to initiate, perform, or control operations to perform part of or all the functionality described above. For example, the instructions can be executable to implement one or more of the operations or methods of <FIG>. In some implementations, part or all of one or more of the operations or methods of <FIG> can be implemented by one or more processors (e.g., one or more central processing units (CPUs), one or more graphics processing units (GPUs), one or more digital signal processors (DSPs)) executing instructions, by dedicated hardware circuitry, or any combination thereof.

The illustrations of the examples described herein are intended to provide a general understanding of the structure of the various implementations. Many other implementations can be apparent to those of skill in the art upon reviewing the disclosure. Other implementations can be utilized and derived from the disclosure, such that structural and logical substitutions and changes can be made without departing from the scope of the disclosure. For example, method operations can be performed in a different order than shown in the figures or one or more method operations can be omitted.

Moreover, although specific examples have been illustrated and described herein, it should be appreciated that any subsequent arrangement designed to achieve the same or similar results can be substituted for the specific implementations shown. This disclosure is intended to cover any and all subsequent adaptations or variations of various implementations. Combinations of the above implementations, and other implementations not specifically described herein, will be apparent to those of skill in the art upon reviewing the description, provided that they remain within the scope of the appended claims.

Claim 1:
A method (<NUM>) comprising:
obtaining (<NUM>), at one or more processors (<NUM>), point cloud data (<NUM>) representing locations in three-dimensional (3D) space of points of a point cloud;
selecting (<NUM>) for further processing by the one or more processors one or more subsets of the point cloud data (<NUM>) based at least in part on a contour metric (<NUM>);
grouping (<NUM>), by the one or more processors, sets of points of the one or more subsets of the point cloud data (<NUM>) into one or more clusters (<NUM>) based at least in part on one or more distance metrics (<NUM>), wherein all points of the one or more subsets within a predetermined Euclidean distance from a plane onto which the one or more subsets of the point cloud data have been projected are grouped;
for a cluster (<NUM>) that satisfies one or more cluster size criteria (<NUM>) based on dimensions (<NUM>) of a calibration standard (<NUM>), determining (<NUM>), by the one or more processors (<NUM>), whether a distribution of signal intensities (<NUM>) of points of the cluster (<NUM>) satisfies a distribution criterion (<NUM>);
based on a determination that the distribution of signal intensities (<NUM>) of points satisfies the distribution criterion (<NUM>), determining (<NUM>), by the one or more processors (<NUM>) based on the cluster (<NUM>), boundaries (<NUM>) of a region that represents the calibration standard (<NUM>); and
storing (<NUM>), by the one or more processors (<NUM>), data identifying a set of points (<NUM>) of the point cloud that correspond to the calibration standard (<NUM>), the set of points (<NUM>) identified based on the boundaries (<NUM>) of the region that represents the calibration standard (<NUM>).