Patent Description:
A task of camera based Advanced Driver Assistance Systems (ADAS) applications, e.g., advanced headlight control, is to detect headlights and tail lights of other vehicles at night in order to switch on and off high beam in car or trucks automatically. The control of the high beam depends on whether other vehicles are detected ahead or not.

The traffic ahead of the vehicle is caught by a camera. The images captured by the camera are analyzed in order to detect headlights and tail lights of other vehicles. For complexity reduction and better performance, lights can be grouped together to pairs or clusters, e.g., all lights of one car or lights of a group of cars can be grouped together.

In current state of the art technology handpicked rules are used for the pairing and/or clustering of headlights and tail lights in image data. However, those rules may not be optimal. In addition, these rules are not flexible.

Recent work in this field has been published in the following documents:.

It is an underlying object of the invention to provide a device for clustering light spots, wherein the device generates results with a high accuracy, especially in scenes with a high amount of light spots. It is further an object of the invention to provide a system that comprises the device and a method for clustering light spots.

The object underlying the invention is satisfied by the features of the independent claims. Advantageous further developments and aspects of the invention are set forth in the dependent claims.

In a first aspect of the instant application a device for clustering light spots is provided.

The device is configured to receive one or more images captured by a camera. In particular, the camera may be mounted on a vehicle and captures images of the road scene and, in particular, the traffic in front of the vehicle. The device is further configured to detect light spots in one or more images received from the camera. Pairs can be formed from the light spots detected in one of the images. For each of a plurality of pairs of the detected light spots, the device calculates a distance measure. Afterwards, the device groups the detected light spots to clusters or objects based on the calculated distance measures.

The distance measure quantifies the dissimilarity between light spots and allows a comparison as to which cluster of light spots a respective light spot fits best. The distance measure takes on a large value for dissimilar light spots and a small value for similar light spots. For example, if the distance measure of one of the light spots to a first cluster is smaller than the distance measure of this light spot to a second cluster, then the light spot fits better to the first cluster. A cluster may comprise one light spot or two or more light spots.

The distance measure can be understood as a function of the inverse of a similarity measure. The similarity measure takes on a small value for dissimilar light spots and a large value for similar light spots.

The device generates results with a high accuracy. Especially in scenes with a high amount of light spots, a clustering of the light spots into several clusters of car lights can be desirable since the output of some clusters may be more useful and computationally performant than a huge amount of light pairs. For this task, the distant measure which measures the dissimilarity between the light spots and thus allows to assign a light spot to the most suitable cluster of light spots is far more useful.

With the distance measure, it is possible to evaluate and compare to which cluster of lights a single light source fits best, thus making it possible to shift from a pure pairing process to a more flexible and practical clustering process.

In one embodiment, the device calculates the distance measure for a respective pair of light spots based on at least one feature of the two light spots of the respective pair. The distance measure then quantifies the dissimilarity of the two light spots of the respective pair of light spots with respect to the at least one feature. For example, the distance measure may be calculated based the difference of the blob areas, i.e., the area sizes, of the two light spots. In this example, the distance measure quantifies the dissimilarity of the two light spots with respect to the difference of their blob areas. The distance measure may also be calculated on the basis of two or more features of the light spots.

The at least one feature, on which the calculation of the distance measure is based, may be at least one feature from the following group of features: a difference in blob area of the two light spots of the respective pair of light spots, a difference in angles of the two light spots with the optical axis (sight axis) of the camera, a difference in center of gravity of the two light spots, a difference in color average of the two light spots, a difference in intensity average of the two light spots and/or an Euclidean distance between the two light spots, i.e., an Euclidean distance between the two light spots in a coordinate system with x and y axes. It is to be noted that the aforementioned features are only examples of possible features. It is also possible that the at least one feature, on which the calculation of the distance measure is based, is different from the aforementioned features. Further, additional features may belong to the aforementioned group of features.

The distance measure for a pair of light spots and for a feature i is a function of the term <MAT>, wherein fi is the value of the feature i for the respective two light spots, µi is a mean value of fi for a plurality of pairs of light spots and σi is a standard deviation value of fi for the plurality of pairs of light spots. For example, if the feature i is the difference of the blob areas of the two light spots of a pair of light spots, then fi gives the value of the actual difference in the blob area of the two light spots. Further, the value fi may be calculated for a great number of different pairs of light spots which can be detected in the images captured by the camera. In particular, the value fi may be calculated for all pairs of light spots detected in the images captured by the camera. From these values of fi, the mean value µi and the standard deviation σi can be calculated. In other words, the mean value µi is the value fi for a typical or average pair of light spots.

The distance measure d(fi) for a pair of light spots and for the feature i may also be calculated by the following equation (<NUM>), wherein π is the mathematical constant pi: <MAT>.

In case a plurality of features are considered to determine the similarity/dissimilarity of the light spots, the distance measure for a pair of light spots and for a plurality of features i is a function of the term <MAT>, wherein nf is the number of the plurality of features.

The distance measure d for the nf features may also be calculated by the following equation (<NUM>), wherein the distance measure d is the sum of the distance measures of all single features: <MAT>.

The device may include a Bayes classifier which is used to calculate the distance measure for each of the plurality of pairs of light spots. A Bayes classifier is a probabilistic classifier based on applying the Bayes' theorem.

The Bayes classifier can be trained on labeled training data, in particular with pairs of headlights and tail lights. Thus, for training purposes, images can be input into the Bayes classifier, wherein it is known by the Bayes classifier whether the images show pairs of headlights and tail lights. The features used for the training of the Bayes classifier are selected by a sequential backward selection strategy out of a feature set. First, the Bayes classifier is trained on all of the features of the feature set. The performance of the Bayes classifier using all of the features is then evaluated. Subsequently, each feature is individually removed from the feature set and the Bayes classifier is trained on the remaining features of the feature set. For each of the reduced feature sets, the performance of the Bayes classifier is evaluated. After that the feature, the removal of which improved the performance of the Bayes classifier most, is permanently removed from the feature set. The process of removing a single feature from the feature set as explained is then started anew. This process is repeated until the removal of any other feature from the feature set only worsens the performance of the Bayes classifier. The remaining feature set can be considered as optimal in regard of the initially chosen set of features. The described process for the selection of the optimal features is carried out before the device is used for clustering light spots. During runtime, the calculation of the distance measure is based on the feature set that was selected before during the feature selection process.

The distance measure is calculated based on the trained Bayes classifier and the extracted standard deviation and mean value of the selected feature values. In the Bayes framework, the probability of a feature value fi under the condition that the light spots on which the feature i was calculated belongs to a pair of headlights or tail lights is calculated first. From this probability, which will be explained in more detail below, the distance measure can be calculated as given by equations (<NUM>) and (<NUM>).

In one embodiment, the device receives images captured by the camera in temporally successive frames. In each of the frames, the device may receive a single image. The device calculates a distance measure for each of a plurality of pairs of light spots detected in the image of one of the frames, e.g., the initial frame, and groups the light spots to clusters based on the calculated distance measures. Further, the device determines from the image of the subsequent frame which of the clusters still exist in the subsequent frame.

A cluster may still exist in the subsequent frame if the number of the light spots of the cluster that are detected in the subsequent frame exceeds a predetermined fraction of the number of the light spots of the cluster that were detected in the previous frame. In other words, the cluster still exists in the subsequent frame if a percentage of the light spots of the cluster that are detected in the subsequent frame exceeds a predetermined percentage value. For example, if a cluster contains <NUM> light spots in the previous frame and the predetermined fraction is <NUM>/<NUM>, i.e., <NUM>%, then the cluster still exists in the subsequent frame if the cluster contains <NUM> or more light spots in the subsequent frame.

The device may further be configured to evaluate whether the light spots of one of the clusters in the subsequent frame are still connected to this cluster. For this purpose, the device may determine for each of the light spots of the cluster in the subsequent frame whether the distance measure of a respective light spot to at least one of the other light spots of the cluster is below a first predetermined threshold. If the distance measure of a light spot to at least one of the other light spots of the cluster is below the first predetermined threshold, this light spot is still connected to the cluster. If not, the light spot does not belong to this cluster any more. An iterative breadth-first-search algorithm may be executed for evaluating whether the light spots of a cluster in the subsequent frame are still connected to the cluster.

The device may further be configured to assign a light spot, which is detected in the subsequent frame and has not been assigned to a cluster, to one of the existing clusters or a new cluster if its distance measure to at least one of the light spots of one of the existing clusters or a new cluster is below a second predetermined threshold. The first predetermined threshold may be greater than the second predetermined threshold. This ensures a certain stability of the clusters as a light spot that was assigned to one of the clusters once will be assigned to this cluster as long as possible. An iterative breadth-first-search algorithm may be executed for assigning the light spots, which are detected in the subsequent frame, but have not been assigned to one of the clusters before, to one of the existing clusters or a new cluster.

The device may be further configured to merge clusters together that overlap each other.

In order to reduce the number of clusters to a predetermined number of clusters the device may further be configured to use a k-means clustering algorithm in order to merge clusters together.

In one embodiment, the light spots are spots of headlights and tail lights of vehicles. The camera may be mounted on a vehicle and may capture images of the traffic in front of the vehicle.

According to a further aspect of the invention, a system comprises a camera mounted on a vehicle and configured to capture images, and a device for clustering light spots as explained above.

According to yet a further aspect of the invention, a method for clustering light spots comprises the following steps. An image captured by a camera is received and light spots are detected in the image. Further, a distance measure is calculated for each of a plurality of pairs of light spots detected in the image, and the detected light spots are grouped to clusters based on the calculated distance measures.

The method may comprise the embodiments disclosed above in connection with the device for clustering light spots.

The invention will be described in more detail in the following in an exemplary manner with reference to an embodiment and to the drawings. There are shown in these:.

<FIG> schematically illustrates a system <NUM> including a camera <NUM> and a device <NUM> that allows clustering light spots.

The camera <NUM> is mounted on a vehicle and captures images <NUM> of the area in front of the vehicle and thus the traffic in front of the vehicle. Alternatively, the camera <NUM> may be directed to an area in the rear and/or at a side of the vehicle.

The images <NUM> captured by the camera <NUM> are fed to the device <NUM>. The device <NUM> processes the images <NUM> and generates an output signal <NUM>. The device <NUM> performs a method <NUM> for clustering light spots as schematically illustrated in <FIG>.

In step <NUM> of the method <NUM>, the device <NUM> receives an image <NUM>, which was previously captured by the camera <NUM> and shows a road scene in front of the vehicle.

In step <NUM>, the device <NUM> detects light spots in the image <NUM>, in particular headlight spots and tail light spots of other vehicles.

In step <NUM>, for each pair of light spots detected in the image <NUM>, the device <NUM> calculates a distance measure.

In step <NUM>, the device <NUM> groups the detected light spots to clusters based on the calculated distance measures. The clusters can be output by the device <NUM> as the output signal <NUM>.

The device <NUM>, the system <NUM> and the method <NUM> are exemplary embodiments according to the first, second and third aspect of the invention, respectively.

In the following embodiments and functions of the device <NUM>, the system <NUM> and the method <NUM> are explained in more detail.

In current technology handpicked rules are used for the pairing and/or clustering of headlights and tail lights in image data. However, those rules may not be optimal and are not flexible. In order to overcome these disadvantages of conventional technology, an automatic feature selection algorithm is used to pick the best combination of features out of a large set of features. For example, in tests the best <NUM> features out of a set of <NUM> features were extracted.

The problem of the inflexibility of a hard threshold for every feature is solved by using a distance measure, which is based on a Bayes classifier and the mean as well as the standard deviation of the features.

For the feature selection process, a Bayes classifier is trained on labeled training data. The training data include images showing headlights and tail lights, in particular pairs of headlights and tail lights which are labelled accordingly. These images are input into the Bayes classifier in order to train the Bayes classifier. The features used for the training are selected by a sequential backward selection strategy out of a huge feature set. For example, in tests the initial feature set included <NUM> features.

The features are used to characterize the similarity or dissimilarity of the two light spots of a light spot pair. The set of features can include one or more of the following features: a difference in blob area between the two light spots of the respective pair of light spots, a difference in angles of the two light spots with the optical axis of the camera, a difference in center of gravity of the two light spots, a difference in color average of the two light spots, a difference in intensity average of the two light spots and an Euclidean distance between the two light spots, i.e., an Euclidean distance between the two light spots in a coordinate system with x and y axes. It is to be noted that the aforementioned features are only examples of possible features. The set of features may contain other features and/or additional features.

At the beginning of the feature selection process, the Bayes classifier is trained on all of the features of the feature set. The performance of the Bayes classifier using all of the features is then evaluated. Subsequently, each feature is individually removed from the feature set and the Bayes classifier is trained on the remaining features of the feature set. For each of the reduced feature sets, the performance of the Bayes classifier is evaluated. This allows to determine the removal of which feature improved the performance of the Bayes classifier most. This feature is then permanently removed from the feature set. Afterwards, the process of a removing a single feature from the feature set is repeated as long as the removal of any other feature from the feature set only worsens the performance of the Bayes classifier. The remaining feature set is considered as optimal in regard of the initially chosen set of features.

The trained Bayes classifier is used to calculate the distance measure. The Bayes classifier outputs the probability p of a feature value fi for a feature i under the condition that the two light spots, on which the feature value fi was calculated, are the light spots of the headlights or tail lights of the same vehicle: <MAT> wherein µi is a mean value of fi for a plurality of pairs of light spots and σi is a standard deviation value of fi for the plurality of pairs of light spots.

The distance measure d(fi) for the pair of light spots and for the feature i can be calculated by taking the logarithm of equation (<NUM>) and negating it: <MAT>.

In case nf features (with nf ≥ <NUM>) are considered to determine the similarity or dissimilarity of the light spots, the distance measure d for the nf features can be calculated by the sum of the distance measures of all single features: <MAT>.

Equation (<NUM>) or (<NUM>) can be used to calculate the distance measure d between light spots and clusters of light spots in order to group light spots to clusters and to decide to which cluster a specific light spot fits best.

<FIG> illustrates a method <NUM> as a further exemplary embodiment of a method for clustering light spots. The method <NUM> can be performed by the device <NUM>. The method <NUM> can be divided into three parts: preprocessing <NUM>, clustering <NUM> and postprocessing <NUM>. The preprocessing <NUM> includes steps <NUM> and <NUM>, the clustering includes steps <NUM> and <NUM>, and the postprocessing includes steps <NUM> and <NUM>.

In step <NUM> of the method <NUM>, the device <NUM> receives an image <NUM>, which was previously captured by the camera <NUM> and shows a road scene in front of the vehicle. The device <NUM> receives the images <NUM> captured by the camera <NUM> in temporally successive frames. In each of the frames, the device <NUM> receives a single image <NUM>.

Further, in step <NUM>, the device <NUM> detects light spots in the image <NUM>, which can be headlight spots or tail light spots of other vehicles. A Gaussian curve is applied on every detected light spot with a standard deviation dependent on the radius of the respective light spot and a coloring dependent on whether the respective light spot is a headlight or a tail light. Afterwards, the values of the Gaussian curves are summed up on the position of every detected light spot. The respective light spot is then ultimately classified on the coloring with the highest value, i.e., the respective light spot is classified to be a headlight or a tail light. This ensures that single false detections, for example, a false tail light in a cluster of many headlights, are smoothed out.

In step <NUM>, the distance measure for every pair of light spots detected in the actual image <NUM> is calculated with the help of equation (<NUM>) or (<NUM>). For example, if the image <NUM> shows <NUM> light spots, then <NUM> pairs of light spots can be formed and for each of these pairs the distance measure can be calculated.

In steps <NUM> and <NUM>, the detected light spots are grouped to clusters based on the calculated distance measures.

In step <NUM>, it is evaluated which light clusters detected in the previous frame still exist in the image <NUM> of the actual frame. This is done by evaluating which light spots of the previous frame are still detected and matched in the actual frame, i.e., the frame subsequent to the previous frame. A cluster that was detected in the previous frame still exists in the actual frame if the number of the light spots of the cluster that are detected in the actual frame exceeds a predetermined fraction of the number of the light spots of the cluster that were detected in the previous frame. Thus, the cluster still exists if a percentage of the light spots of the cluster that are detected in the actual frame exceeds a predetermined percentage value.

As an example, <FIG> schematically shows an image <NUM> captured in the previous frame and <FIG> schematically shows an image <NUM> captured in the actual frame. In the image <NUM>, light spots L<NUM> to L<NUM> are detected. Further, light spots L<NUM> to L<NUM> are grouped to a cluster C<NUM> and light spots L<NUM> to L<NUM> are grouped to a cluster C<NUM>. In the image <NUM>, the light spots L<NUM>, L<NUM>, L<NUM> and L<NUM> to L<NUM> are detected, however the light spot L<NUM> detected in the previous frame is no longer detected in the actual frame. Further, a new light spot L<NUM> is detected in image <NUM>.

The cluster C<NUM> in the image <NUM> thus contains <NUM>% of the light spots of the cluster C<NUM> in the image <NUM>. If the predetermined percentage value is <NUM>%, the cluster C<NUM> in the image <NUM> exceeds this value so that it can be stated that the cluster C<NUM> still exists in the actual frame. The cluster C<NUM> also still exists in the actual frame since the cluster C<NUM> has the same number of light spots in both images <NUM> and <NUM>.

In step <NUM>, it is also evaluated if the light spots of a cluster are still connected in the actual frame, for example, by using an iterative breadth-first-search algorithm. A light spot is considered to be connected to the cluster if its distance measure to at least one of the other light spots of this cluster is below a first predetermined threshold T<NUM>. In the example of <FIG>, an iterative breadth-first-search algorithm can be executed for evaluating whether the light spots L<NUM>, L<NUM>, L<NUM> detected in the actual frame are connected to the cluster C<NUM> and the light spots L<NUM> to L<NUM> are connected to the cluster C<NUM>.

In step <NUM>, the remaining light spots are clustered and, if possible, clusters are merged. For this purpose, an iterative breadth-first-search algorithm can be performed running over all light spots light spots L<NUM>, L<NUM>, L<NUM> and L<NUM> to L<NUM> that are detected in the image <NUM>. In particular, it is evaluated if the distance measure of a remaining light spot, i.e., the light spot L<NUM>, to at least one of the light spots of one of the existing clusters or a new cluster is below a second predetermined threshold T<NUM>, wherein the second predetermined threshold T<NUM> is smaller than the first predetermined threshold T<NUM>. There are the following options for the result of step <NUM>:.

It is to be noted that for the initial frame when clusters have not been formed yet, two light spots form a new cluster if their distance measure is below the second predetermined threshold. Another light spot may be assigned to this cluster if its distance measure to at least one of the light spots of this cluster is also below the second predetermined threshold.

In step <NUM>, overlapping clusters are merged together in the actual frame.

Claim 1:
A device (<NUM>) for clustering light spots,
wherein the light spots are spots of headlights and tail lights of vehicles, the device (<NUM>) is configured to
receive more than one image (<NUM>) captured by a camera (<NUM>),
detect light spots in the images (<NUM>),
calculate a distance measure for each of a plurality of pairs of light spots detected in the images (<NUM>),
wherein the distance measure for each pair of light spots is calculated on the basis of two or more features of the two light spots of the respective pair, and
group the detected light spots to clusters based on the calculated distance measures,
characterized by
the distance measure for a respective pair of light spots and for a feature i being a function of <MAT>, wherein fi is the value of the feature i for the two light spots of the respective pair, µi is a mean value of fi for a plurality of pairs of light spots and σi is a standard deviation value of fi for the plurality of pairs of light spots,
two light spots forming a new cluster in an initial frame when clusters have not been formed yet if their distance measure is below a predetermined threshold T<NUM>, and
a third light spot being assigned to the cluster if its distance measure to at least one of the two light spots of the cluster is below the predetermined threshold T<NUM>.