Patent Description:
Many different types of sensors sample their surrounding environment sparsely, which means that an object in the environment is only represented by a single or by a few data points that are output from the sensor to represent the entire object. A stretch of road surface may for instance only be seen as a single data point in a cloud of data points, not as a continuous surface. As the sensor moves in relation to the object, the sampled data points associated with the object are likely to change, causing the object to appear as if it is moving even though it is a stationary object. LIDAR sensors often sample the surrounding environment sparsely.

Higher layer systems and control algorithms may have problems interpreting and classifying such sparsely sampled data. For instance, the higher layer algorithms may require significant processing resources in order to classify samples as belonging to a stationary object vs belonging to a non-stationary object due to the apparent motion effects from the sparse sampling.

The documents "<NPL>ET AL) and "<NPL>ET AL) disclose methods for annotating data using a static model of the environment, wherein the static model of the environment comprises a collection of local statistical models.

It is an object of the present disclosure to present methods and devices for annotating a sparsely sampled data set, whereby samples or groups of samples are annotated as stable or stationary despite presence of apparent motion effects due to sparse sampling.

This object is achieved by a method for annotating data points in a data set, where the method comprises obtaining a set of data points associated with an environment sampled by a vehicle sensor and determining a static model of the environment based on the set of data points, wherein the static model of the environment comprises a collection of local statistical models arranged in a hierarchical data structure, where the collection of local statistical models describes local distributions of data points in the environment at different scale levels.

The method further comprises obtaining a new data point associated with the environment, associating the new data point to a corresponding local statistical model comprised in the static model of the environment based on a statistical distance metric from the new data point to the corresponding local statistical model, and annotating the new data point as a stable data point on a given scale level of the hierarchical data structure in case the new data point agrees with the corresponding local statistical model.

This means that samples or groups of samples can be annotated as stable or stationary despite possible presence of apparent motion effects due to sparse sampling. This helps in classifying the nature of movements with respect to previously accumulated data. A label may be a part of sensor output, and can therefore be used as a temporal feature for subsequent sensor fusion systems. A static object, such as a tree, can be labelled as 'stable' on the macro scale, even though it is considered 'unstable' on a smaller scale. This also means that a new data point can be annotated as a stable or unstable data point in dependence of if the new data point is considered close to, or resembling, a current distribution.

According to some aspects, the data points comprise light detection and ranging, LIDAR sensor data and/or radio detection and ranging, RADAR, sensor data.

The present disclosure is thus applicable for data from a broad variety of vehicle sensors.

According to some aspects, a local statistical model comprises a Normal Distribution Transform (NDT) over data points comprised in the associated local area, wherein a covariance of each local area represents a local distribution of the static model of the environment.

A well-known transform, can thus be used.

According to some aspects, the annotating is based on a statistical distance metric from the new data point to the corresponding local statistical model.

This means that a new data point can be annotated as a stable or unstable data point in dependence of if the new data point is considered close to a current distribution.

According to some aspects, the static model of the environment comprises an octree, a quadtree, or an octree map representation.

Well-known and effective representations can thus be used for the present disclosure.

According to some aspects, each cell of the octree, quadtree or octree map is associated with a local statistical model.

According to some aspects, the local distribution is selected from any of; a plane, a sphere, or a cuboid.

According to some aspects, the method comprises extending the static model of the environment based on the new data point in case no corresponding local statistical model is available.

In this way, a new data point that for example corresponds to a region in the static model of the environment in which no previous data points have been obtained, i.e., the region is new ground, can be handled. A new local model based can for example be started on the new data point. This new data point may optionally be annotated as unstable in case no other data is available indicating that the data point is associated with a dynamic object or the like.

According to some aspects, the method comprises updating the static model of the environment based on the new data point in case the new data point does not agree with the corresponding local statistical model.

In this way, a new data point that is the first data point associated with some static structure that is just coming into view by a vehicle sensor can be handled.

According to some aspects, the method comprises excluding the new data point from the static model of the environment in case the new data point is detected as corresponding to a non-stationary object in the environment.

In this manner, a new data point can be annotated as unstable.

This object is also achieved by means of a control unit and a vehicle which are associated with the above advantages.

The present disclosure will now be described in detail with reference to the appended drawings, where:.

<FIG> shows a schematic top view of a vehicle <NUM> equipped with a vehicle sensor system <NUM>. The vehicle moves in a direction with velocity vector vego. The vehicle sensor system <NUM> comprises a vehicle sensor <NUM> and a control unit <NUM>. An optional storage module <NUM> may also be comprised in the control unit <NUM>. The storage module <NUM> will be discussed in more detail below.

The control unit <NUM> is arranged to control operation of the vehicle sensor <NUM>, and to obtain data from the vehicle sensor, such as detections or data points corresponding to objects <NUM>, <NUM> in the vicinity of the vehicle <NUM>.

The vehicle sensor <NUM> may comprise a single sensor unit or a plurality of sensor units, potentially of different type and/or of different configuration. For instance, the vehicle sensor <NUM> may comprise any of a LIDAR sensor, a RADAR sensor, a camera sensor, or an ultrasound sensor. The vehicle sensor <NUM> may also comprise any of a TOF camera system, a structured light system, and a stereo vision system.

The vehicle sensor <NUM> is arranged to generate a number of data points comprising coordinates in a relative coordinate system, i.e., relative to the location and orientation of the sensor. The coordinates may be Cartesian coordinates or they may be polar coordinates.

The data points may also comprise additional information, such as light intensity values, colour data, signal strength values, frequency values, and measures of signal-to-noise ratio (SNR). One or more time-stamps may also be associated with the detections. The time stamps may be assigned per data point or be common to a set of data points. A LIDAR system using a rolling shutter would most likely assign one-time stamp per data point, but it is also plausible to assign a single time stamp per scan or per data set, albeit with loss of accuracy.

A data point, in general, is a value or collection of values representing a configuration of an object or part of an object in an environment, such as in a vicinity of a vehicle. For instance, in case of a LIDAR sensor, a data point may comprise a value indicating a range and an angle from the LIDAR sensor transceiver, or a set of coordinates describing a point in three-dimensional space. A data point may also comprise a velocity estimate obtained from a Doppler shift of a received waveform, and an angle or bearing obtained from an angle of arrival of a reflected sensor signal waveform. The velocity data may in some cases be quantized into moving or stationary, since some aspects of the methods disclosed herein comprises discarding data points related to moving objects.

Herein, a sensor data point is at times referred to as a sample or as a detection. These terms are considered equivalent unless otherwise explicitly stated.

The storage module <NUM> may store map data comprising information about a surrounding environment of the vehicle <NUM>.

New data points are produced more or less continuously by the sensor in cycles or scans. Most sensor systems generate detection data on a regular basis, with a cycle interval of T seconds. For instance, the interval T may correspond to a frame length of a radar signal, or to an image processing duration of a camera-based sensor, or to a scan period of a laser scanner. Detections may be stored by the storage module <NUM> and retrieved for processing as needed.

At least one of the sensors may be arranged to sparsely sample the surrounding environment. Herein, to sparsely sample means that an object having an extension in space will only be represented by a single or a few data points each time update or scan. The data point or points representing an object may move over time (over cycles or scans) due to the effects of the sparse sampling. Sparse sampling will be discussed in more detail below in connection to <FIG>.

The vehicle sensor <NUM> is associated with a field of view <NUM>, which may be a <NUM>-degree field of view, or a more limited field of view as shown in <FIG>. Two objects <NUM>, <NUM> are located in the field of view <NUM>. A first object <NUM> generates a data point marked by a star <NUM>. A second object <NUM> generates a data point marked by a square <NUM>.

The first object <NUM> and the second object <NUM> may be tracked over time by a tracking algorithm which associates obtained data points with the different objects and continuously estimates, e.g., location and heading of the first and second object. Such tracking algorithms may robustly estimate the heading of a tracked object over time even if signal to noise ratio temporarily is reduced, or only a few detections are obtained in some cycles. Examples of such tracking algorithms include Kalman filters, extended Kalman filters, and Particle filters.

The data points <NUM>, <NUM> exhibit motion effects due to the sparse sampling, which means that the data points may move from scan to scan even though the objects <NUM>, <NUM> are stationary objects. This motion may cause problems in higher layer algorithms such as tracking algorithms, which may need to spend significant processing power to classify the objects <NUM>, <NUM> and associate detections <NUM>, <NUM> to different objects.

To aid higher layer algorithms, the techniques proposed herein aim at annotating data points or groups of data points as being associated with a stationary object if this is the case, even though the data points exhibit some motion. This way, the higher layer algorithms can more easily handle apparent motion effects. One of the main ideas behind the present disclosure is to define a feature or region as stable or stationary if its temporal variations correspond to a previously computed model of the region - and to provide this feature as external output from the vehicle sensor <NUM> or from the vehicle control unit <NUM>.

In order to make use of acquired data points, new data sets must often first be aligned with a reference coordinate system or be registered relative to another data set. Such scan matching plays a crucial role in, e.g., simultaneous localization and mapping (SLAM) applications.

<FIG> illustrates an example hierarchical data structure <NUM> which can be used to represent a surrounding environment. The structure in <FIG> is known as an octree. An octree is a hierarchical tree data structure in which each node or cell has eight children. Octrees are often used to partition a three-dimensional space by recursively subdividing it into eight cells 210a, 210b, <NUM>, <NUM>, or octants. The Octree can also be visualized by a tree structure <NUM>, where a trunk node <NUM> has eight branches. Each branch leads to a node or cell <NUM> at a next level which again branches out into eight new branches.

Each cell 210a, 210b, <NUM>, <NUM> is associated with a cell range <NUM>, <NUM>, where the different cell ranges partition a space at different resolutions. A data point <NUM> is associated with a unique cell <NUM> at any given level of the octree based on the data point value and on the cell ranges at the different levels.

A quadtree <NUM>, schematically illustrated in <FIG>, is a two-dimensional version of the octree. Like the octree, a quadtree divides a two-dimensional space into cells <NUM>, <NUM>, <NUM> having cell ranges <NUM> at different resolutions at different levels of the quadtree. Data points <NUM>, <NUM> are again associated with unique cells at each level in the quadtree.

It is appreciated that hierarchical data structures, such as the octree and quadtree data structures, can be efficiently processed by discarding irrelevant cells, e.g., by inserting null pointers at appropriate locations in a memory structure. For instance, cells not associated with any data points, or cells not associated with enough data points to determine a relevant cell feature such as a normal vector, may be discarded to improve processing efficiency. In the example of <FIG>, cell <NUM> does not contain any data points, and could therefore potentially be ignored during further processing. It may also be advantageous to discard cells comprising data points associated with moving objects, since such data points may impact the end result, according to some aspects an end transformation, negatively.

Other examples of hierarchical data structures include VDB trees, i.e., Volumetric Dynamic grid B-trees, and B+trees. The disclosed techniques are particularly suitable for use with Octrees and similar data structures but are not dependent on any particular type of data structure. Rather, the techniques disclosed herein are applicable together with a wide range of different data structures.

The techniques disclosed herein can be used together with an octree-representation of the world model. The octree subdivides the world into cells of different sizes. By, for example, computing a Normal Distribution Transform (NDT) over the octree, the covariance of each cell will represent the local distribution of the 3D world model. If the distribution resembles a plane, any new measurement will be considered 'stable' if its distance to the plane is low. If the distribution resembles a sphere, a new measurement will be considered 'stable' if the new point is statistically likely to be a part of the distribution. The subdivision of the octree into scale levels makes it possible to find regions that are stable on a large-scale level, but unstable on a smaller scale level, which is an advantage associated with the proposed techniques. A new measurement can therefore both be stable and unstable but on different levels.

Each local region in the data structure comprises a statistical representation of the data points corresponding to the particular region. For example, the cells in the octree may comprise information about a centroid value and a covariance matrix. These statistical measures can be used to determine of the data points in a given region corresponds to a planar structure of to a cuboid structure, or perhaps a spherical structure. Given such local statistical models, a new data point can be compared to the local statistical model to which it corresponds.

For instance, a new data point may be obtained and associated to cell 210a. The previous data points associated to this cell may exhibit a statistical distribution with a variance indicating that the data points all lie on or at least close to a planar structure. Now, if also the new data point is close to this planar structure, then it can be annotated as stable or stationary and optionally also as belonging to the planar structure. However, if the new data point is not in agreement with the local statistical distribution, then the data point may not correspond to the planar structure and should therefore not be labelled as stable or stationary.

According to some aspects, oscillating centroids can be annotated as 'stable' if they move according to the model of the underlying surface.

<FIG> illustrate examples showing the effects of sparse sampling of an environment, and the application of the proposed annotation techniques. <FIG> illustrates a scenario where a vehicle <NUM> obtains a new data point <NUM> corresponding to a patch of road surface <NUM>. The patch of road surface is relatively flat, which means that the statistical distribution of data points obtained from this local area can be expected to show a statistical distribution in agreement with a planar structure. <FIG> shows a scenario where the vehicle <NUM> has travelled some distance towards the flat patch of road surface <NUM>. The vehicle <NUM> obtains a new data point <NUM> which agrees with the local statistical model comprised in the static model of the environment. This newly obtained data point <NUM> is therefore annotated as stationary even though it differs from the previously obtained data point <NUM>.

However, as shown in <FIG>, the vehicle <NUM> may also obtain a data point <NUM> which is located some distance away from the patch of road surface. This newly obtained data point <NUM> is not in agreement with the local statistical model, and should therefore not be annotated as stable, at least until more information is available. Perhaps the newly obtained data point <NUM> has been generated by some other stationary object that is just coming into view of the sensor and which has not yet made an impact on the static model of the environment which the vehicle is maintaining.

<FIG> is a flow chart showing methods that summarize the discussions above. There is illustrated a method for annotating data points <NUM>, <NUM> in a data set. The method comprises obtaining S1 a set of data points associated with an environment sampled by a vehicle sensor <NUM>. The obtaining may, e.g., be mostly based on sensing data points by on-board vehicle sensors. However, the obtaining may also optionally comprise downloading data from a remote server or receiving data from other vehicles. The method also comprises determining S2 a static model <NUM>, <NUM> of the environment based on the set of data points, wherein the static model of the environment comprises a collection of local statistical models. The static model of the environment may, e.g., be based on an Octree representation as discussed in connection to <FIG> above. Each cell at each hierarchical level is then associated with a statistical model, which represents a local statistical model.

The method further comprises obtaining S3 a new data point associated with the environment. The new data point may, e.g., be obtained as a recent sample from a vehicle sensor, or it may be obtained as a sensor sample sensed by some other vehicle or downloaded from a remote server.

The method comprises associating S4 the new data point to a corresponding local statistical model comprised in the static model of the environment. For example, the associating may comprise determining a distance metric between the new data point and the local statistical model in the corresponding region of the static model of the environment. One such distance metric is the probability of sensing the new data point given the local statistical model of data points in the region. Another such distance metric is a Gaussian distance metric given as; <MAT> where x is the data point, µ is the mean of an assumed local statistical distribution, and W is an assumed covariance matrix of the assumed local statistical distribution.

As another example, a local statistical model may be based on a Normal Distribution Transform, NDT, over data points comprised in the associated local area, or Octree cell if that representation is used. A covariance of each local area then represents a local distribution of the static model of the environment. The local area may, e.g., be a cell in an Octree structure, in which case the NDT is applied on data points associated with the cell.

In other words, according to some aspects, the annotating is based on a statistical distance metric from the new data point to the corresponding local statistical model. The collection of local statistical models describes local distributions of data points in the environment.

The method also comprises annotating S5 the new data point as a stable data point in case the new data point agrees with the corresponding local statistical model. The 'agreement' can be implemented in many different ways as is realized by the skilled person. For instance, agreement may be taken to mean that the above-mentioned distance metric should be below some predetermined threshold in order to indicate agreement and to not indicate agreement otherwise.

According to aspects, the data points comprise light detection and ranging, LIDAR sensor data S11 and/or radio detection and ranging, RADAR, sensor data S12.

According to aspects, each cell of the octree, quadtree or octree map is associated with a local statistical model.

According to aspects, the local distribution is selected from any of; a plane, a sphere, or a cuboid.

According to aspects, the method also comprises extending S6 the static model of the environment based on the new data point in case no corresponding local statistical model is available. For instance, a new data point may correspond to a region in the static model of the environment in which no previous data points have been obtained, i.e., the region is new ground. In this case, it may be reasonable to start a new local model based on the new data point. This new data point may optionally be annotated as unstable in case no other data is available indicating that the data point is associated with a dynamic object or the like.

According to aspects, the method also comprises updating S7 the static model of the environment based on the new data point in case the new data point does not agree with the corresponding local statistical model. Perhaps the new data point is the first data point associated with some static structure that is just coming into view by the sensor <NUM>. In this case it makes sense to update the local statistical model to eventually allow more data points from the new structure to be annotated as stable or stationary. According to some aspects, this is done when the updated model has been determined to have a higher certainty than the model before updating. This can according to some aspects be due to the fact that more measurements fit the updated model, and/or that the model before updating has expired time-wise.

According to aspects, the method also comprises excluding S8 the new data point from the static model of the environment in case the new data point is detected as corresponding to a non-stationary object in the environment. Dynamic data points may be indicated by, e.g., Doppler data. These data points are necessarily not comprised in a static object.

According to aspects, the method also comprises providing S9 the annotated data points as an output from a control unit <NUM>.

It is appreciated that objects that are moving in a scene (e.g. other vehicles etc.) may also have 'stable' and 'unstable' regions. Then, the annotation may be done with respect to the local coordinate-system of the vehicle instead of the static world map.

The methods and techniques discussed above can be realized in various forms of hardware. <FIG> schematically illustrates, in terms of a number of functional units, the components of a control unit <NUM> according to an embodiment of the above discussions. Processing circuitry <NUM> is provided using any combination of one or more of a suitable central processing unit CPU, multiprocessor, microcontroller, digital signal processor DSP, etc., capable of executing software instructions stored in a computer program product, e.g. in the form of a storage medium <NUM>. The processing circuitry <NUM> may further be provided as at least one application specific integrated circuit ASIC, or field programmable gate array FPGA.

Particularly, the processing circuitry <NUM> is configured to cause the control unit <NUM> to perform a set of operations, or steps.

The control unit <NUM> may further comprise a communications interface <NUM> for communications with at least one external device, such as a vehicle sensor <NUM>. As such, the communication interface <NUM> may comprise one or more transmitters and receivers, comprising analogue and digital components and a suitable number of ports for wireline or wireless communication.

The processing circuitry <NUM> controls the general operation of the control unit <NUM> e.g. by sending data and control signals to the communication interface <NUM> and the storage medium <NUM>, by receiving data and reports from the communication interface <NUM>, and by retrieving data and instructions from the storage medium <NUM>.

The control unit <NUM> is configured to annotate data points <NUM>, <NUM> in a data set. To achieve this, the control unit <NUM> is adapted to obtain a set of data points associated with an environment sampled by a vehicle sensor <NUM> and to determine a static model <NUM>, <NUM> of the environment based on the set of data points, wherein the static model of the environment comprises a collection of local statistical models. The control unit <NUM> is further adapted to obtain a new data point associated with the environment, to associate the new data point to a corresponding local statistical model comprised in the static model of the environment, and to annotate the new data point as a stable data point in case the new data point agrees with the corresponding local statistical model.

Claim 1:
A method for annotating data points (<NUM>, <NUM>) in a data set, the method comprising;
obtaining (S1) a set of data points associated with an environment sampled by a vehicle sensor (<NUM>);
determining (S2) a static model (<NUM>, <NUM>) of the environment based on the set of data points, wherein the static model of the environment comprises a collection of local statistical models arranged in a hierarchical data structure, where the collection of local statistical models describes local distributions of data points in the environment at different scale levels;
obtaining (S3) a new data point associated with the environment;
associating (S4) the new data point to a corresponding local statistical model comprised in the static model of the environment based on a statistical distance metric from the new data point to the corresponding local statistical model;
annotating (S5) the new data point as a stable data point on a given scale level of the hierarchical data structure in case the new data point agrees with the corresponding local statistical model.