Apparatus for lane detection

Abstract

An apparatus for a motor vehicle driver assistance system is provided. The apparatus is configured to optimise object clusters, where each object cluster includes a sequence of position measurements for at least one object in the vicinity of the vehicle. Initially, in a pre-clustering phase, the assignment of the measured object positions to the object clusters may be based on the relative proximity of the measured object positions. The apparatus identifies a rogue object cluster on the basis of a first diagnostic, and a rogue object track from the measurements within the rogue object cluster. The position measurements from the rogue object track are removed from the clusters, and remaining position measurements in the rogue object cluster are reassigned to the other object clusters. The rogue object cluster is removed. Thus the object clusters are optimised.

Claims

1. An apparatus for a motor vehicle driver assistance system for a motor vehicle, the apparatus being operable to initialize and optimise a plurality of object clusters, each of the object clusters including at least one object track, wherein the object track includes a plurality of sequential measurements of a position of a respective object located in the vicinity of the motor vehicle, and the object track has a track length, the apparatus being configured to perform the following steps: a) assign the measurements of the positions of the plurality of object tracks to a collection of object clusters, wherein each of the object clusters include at least one position measurement from at least one of the object tracks; b) calculate a respective value of a first diagnostic for each of the object clusters in the collection; c) based on the values of the first diagnostic, identify a rogue object cluster; d) from the object tracks having the position measurements assigned to the rogue object cluster, identify as a rogue object track the object track having a longest length; e) remove the sequence of position measurements corresponding to the rogue object track from all of the other object clusters; f) reassign any remaining position of the measurements previously assigned to the rogue object cluster to other object clusters in the collection; and g) remove the rogue object cluster from the collection.

2. An apparatus according to claim 1, further configured to repeat the steps b) to g) until no rogue object cluster is identified.

3. An apparatus according to claim 1 further configured to, in the step b), determine whether or not each of the object clusters is confluent with each other of the object clusters.

4. An apparatus according to claim 1 further configured to determine, for each of the object clusters in the collection, whether the object cluster is an inner object cluster or an external object cluster.

5. An apparatus according to claim 4 wherein the value of the first diagnostic for the inner object cluster is the number of other of the inner object clusters with which it is confluent, and; wherein the value of the first diagnostic for the external object cluster is set to zero.

6. An apparatus according to claim 1 wherein the rogue object cluster is the object cluster having a highest unique value of the first diagnostic.

7. An apparatus according to claim 1 further configured to, in the event that two of the object clusters have identical values of the first diagnostic, calculate a value for a second diagnostic for at least the object clusters having the identical value of the first diagnostic, and wherein the identification of the rogue object cluster is further based on the value of the second diagnostic.

8. An apparatus according to claim 7 wherein the value of the second diagnostic for the object cluster is equal to a number of contacts of the object cluster with the other of the object clusters.

9. An apparatus according to claim 8 wherein the rogue object cluster is identified as the object cluster having the highest unique value of the second diagnostic.

10. An apparatus according to claim 9 further configured to, in the event that two of the object clusters have identical values of the second diagnostic, calculate a value for a third diagnostic for at least the object clusters having the identical value of the second diagnostic, and wherein the identification of the rogue object cluster is further based on the value of the third diagnostic.

11. An apparatus according to claim 10 wherein a value of the third diagnostic for the object cluster is equal to the number of parallelisms of it with the other object clusters.

12. An apparatus according to claim 11 wherein the rogue object cluster is identified as the object cluster having the lowest unique value of the third diagnostic.

13. A method for a motor vehicle driver assistance system for a motor vehicle, the method for initialising and optimising a plurality of object clusters, wherein each of the object clusters including at least one object track, wherein each of the object clusters include a plurality of sequential measurements of a position of a respective object located in the vicinity of the motor vehicle, and each of the object tracks has a track length, the method including the following steps: a) assign a position measurements of the plurality of object tracks among a collection of the object clusters, wherein each of the object clusters include at least one position measurement from at least one of the object tracks; b) calculate a respective value of a first diagnostic for each of the object clusters in the collection; c) based on the values of the first diagnostic, identify a rogue object cluster; d) from the object tracks whose position measurements are assigned to the rogue object cluster, identify as a rogue object track the object track having a longest length; e) remove the sequence of position measurements corresponding to the rogue object track from all other of the object clusters; f) reassign any remaining position measurements in the rogue object cluster to the other object clusters in the collection, and; g) remove the rogue object cluster from the collection.

14. A method according to claim 13, further comprising repeating the steps b) to g) until no rogue object cluster is identified.

15. A method according to claim 13, further comprising in the step b), determining whether or not each of the object clusters is confluent with each other of the object clusters.

16. A method according to claim 13, further comprising, determining, for each of the object clusters in the collection, whether the object cluster is an inner object cluster or an external object cluster.

17. A method according to claim 16, wherein: the value of the first diagnostic for the inner object cluster is the number of other of the inner object clusters with which it is confluent, and; wherein the value of the first diagnostic for the external object cluster is set to zero.

18. A method according to claim 13, wherein the rogue object cluster is the object cluster having a highest unique value of the first diagnostic.

19. A method according to claim 13, further comprising, in the event that two of the object clusters have identical values of the first diagnostic, calculating a value for a second diagnostic for at least the object clusters having the identical value of the first diagnostic, and wherein the identification of the rogue object cluster is further based on the value of the second diagnostic.

20. A method according to claim 19, wherein the value of the second diagnostic for the object cluster is equal to a number of contacts of the object cluster with the other of the object clusters.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) So that the invention may be more readily understood, and so that further features thereof may be appreciated, embodiments of the invention will now be described by way of example with reference to the accompanying drawings in which:

(2) FIG. 1 shows a vehicle with a driver assistance system of a type suitable for use with the present invention;

(3) FIG. 2A is a camera-view of a driving scenario;

(4) FIG. 2B is a driving scenario;

(5) FIG. 2C is a driving scenario;

(6) FIG. 3 is a first schematic bird's-eye view of a driving scenario;

(7) FIG. 4 is a second schematic bird's-eye view of a driving scenario;

(8) FIG. 5 is a plot of measured positions for a number of objects in a third driving scenario;

(9) FIG. 6 is a plot of measured positions for a number of objects in the third driving scenario;

(10) FIG. 7 is a plot of measured positions for a number of objects in the third driving scenario;

(11) FIG. 8 is a plot illustrating confluence and contact of object tracks;

(12) FIG. 9 is a plot of measured positions for a number of objects in the third driving scenario;

(13) FIG. 10 is a plot of measured positions for a number of objects in the third driving scenario;

(14) FIG. 11 is a plot of measured positions for a number of objects in the third driving scenario;

(15) FIG. 12 is a plot illustrating the fitting of a spline;

(16) FIG. 13 illustrates the method steps for segmenting measured positions;

(17) FIG. 14 is a plot illustrating calculating the length of an object track, which contains three position points with the corresponding x/y coordinates;

(18) FIG. 15 is a plot illustrating the coordinate transformation in Cartesian coordinate system and;

(19) FIG. 16 is a plot illustrating identifying the section of a spline for calculating the lateral/perpendicular distance;

(20) FIG. 17 is a plot illustrating a calculation of the shortest distance between a spline and a point;

(21) FIG. 18 is a plot illustrating confluence and contact of object tracks, and;

(22) FIG. 19 is a plot illustrating inner and external object clusters.

DETAILED DESCRIPTION

(23) Turning now to consider FIG. 1 in more detail, there is illustrated a schematic representation of an exemplary driver assistance system 1 installed in an ego vehicle 2 (only one side panel of which is denoted in FIG. 1 to indicate the vehicle's orientation). The safety system 1 comprises a number of different types of sensor mounted at appropriate positions on the ego vehicle 2. In particular, the system 1 illustrated includes: a pair of divergent and outwardly directed mid-range radar (“MRR”) sensors 3 mounted at respective front corners of the vehicle 2, a similar pair of divergent and outwardly directed multi-role radar sensors 4 mounted at respective rear corners of the vehicle, a forwardly directed longrange radar (“LRR”) sensor 5 mounted centrally at the front of the vehicle 2, and a pair of generally forwardly directed optical sensors 6 forming part of a stereo vision system (“SVS”) 7 which may be mounted, for example, in the region of the upper edge of the vehicle's windscreen. The various sensors 3-6 are operatively connected to a central electronic control system which is typically provided in the form of an integrated electronic control unit 8 mounted at a convenient location within the vehicle. In the particular arrangement illustrated, the front and rear MRR sensors 3, 4 are connected to the central control unit 8 via a conventional Controller Area Network (“CAN”) bus 9, and the LRR sensor 5 and the sensors of the SVS 7 are connected to the central control unit 8 via a faster FlexRay serial bus 9, also of a type known per se.

(24) Collectively, and under the control of the control unit 8, the various sensors 3-6 can be used to provide a variety of different types of driver assistance functionalities such as, for example: blind spot monitoring; adaptive cruise control; collision prevention assist; lane departure protection; and rear collision mitigation.

(25) FIG. 2A shows a view from a camera mounted to an ego vehicle. Overlaid on the view is an identified lane area 11 located on the central lane 12. The identified lane portion is located between detected portions of line markings 13. A left lane 15 is located on the left of the central lane 12, and a right lane 16 is located on the right of the central lane 12. It will be apparent that the detected portions of the lane markings only extend to a maximum distance from the ego vehicle.

(26) FIG. 2B shows a scenario in which it is difficult or impossible for the system to detect road markings because the road markings are partially or fully obscured from the camera's view by other vehicles. Such a situation may occur, for example, in very heavy traffic or in a traffic jam.

(27) FIG. 2C shows a second example scenario in which it is difficult or impossible to detect road markings because the road markings are obscured from the camera's view by snow. It will be appreciated that there are other reasons why it may not be possible for the camera to detect the road markings as well as those illustrated by FIGS. 2B and 2C.

(28) When it is difficult or impossible to use identify lane markings, and in turn, to identify the lane positions, another method of identifying lane positions is required. The advanced driver assistance system may then make use of those lane positions in a variety of driver assistance or automated driving functionalities.

(29) According to the present invention, clustering historically measured positions of objects is performed. This may permit building a graph of drivable paths from the reconstructed trajectories of vehicles detected by sensors (e.g. Radar, Camera) mounted in an autonomous car. The perceived objects are tracked and for every object a history is calculated by, for example, an Object History module. Each object history (or object track) is an object that stores position information of certain objects over several execution cycles to create a trace of an object's path/trajectory in the current ego coordinate system. Such an object history module is not a part of the present invention described herein.

(30) According to the present invention, the object history points are merged, clustered and labelled with meta-information. A graph of the underlying road infrastructure (including road lanes) can be generated with this information. The generated road infrastructure can be used for different applications, for example:

(31) Updating high precision maps;

(32) generating local temporary maps;

(33) improving lane position estimation in case of insufficient lane information from other sources, for example camera-detected lanes or radar-supported road lane boundaries, and;

(34) object-to-lane assignment in case of insufficient lane information from the camera.

(35) All of these applications of the present invention, and others, may be useful for autonomous driving or Advanced Driver Assistance Systems (ADAS).

(36) FIG. 3 shows a bird's-eye schematic view of a typical driving situation on a road 20. The road 20 has three lanes along which traffic can travel: a central traffic lane 21, a left lane 22 and a right lane 23. The left lane 22 is separated from the central lane 21 by a lane marking; similarly, the right lane 23 is separated from the central lane 21 by another lane marking. The outer limit of the right lane 23 is designated by a solid lane marking; similarly, the outer limit of the left lane 22 is designated by another solid lane marking.

(37) FIG. 3 illustrates an ego vehicle 25 fitted with a driver assistance system including an apparatus according to a first embodiment of the present invention. The ego vehicle 25 is driving along the central lane 21 of the road 20. The direction of travel of the ego vehicle 25 is shown by an arrow 25A. Two other vehicles, 26, 27 are also shown travelling along the road 20. The direction of travel 26A, 27A for each of the other vehicles 26, 27 is also shown in FIG. 3.

(38) Evidently, all of the vehicles shown in FIG. 3 are travelling in generally the same direction (upwards on the page). Accordingly, the road 20 of FIG. 3 corresponds, for example, to half of a highway or motorway. A corresponding second half of the highway or motorway is not shown, but would be located to one side (either to the right or to the left, as seen in FIG. 3) of the road 20 (which side clearly depends on the country in which the road is located). The vehicles on the second half of the highway or motor would travel in generally the opposite direction to the vehicles on the road 20.

(39) The ego vehicle 25 is fitted with at least one sensor. One of the sensors may, for example, be a vehicle RADAR or a LIDAR. The driver assistance system uses the data from the sensor to measure and determine the positions of objects within the field of view of the sensor(s) that are located in the vicinity of the ego vehicle 25. In the scenario shown in FIG. 3, the driver assistance system has detected two objects 26, 27, which are, in fact, the first and second vehicles 26, 27 in this example. For each of the first and second objects 26, 27 the driver assistance system sequentially measures the position of the respective object 26, 27. The measurements are made periodically, although this is not a requirement of the present invention. What is important is that a sequence of position measurements are made.

(40) For each object, an object track is formed. The object track includes the sequence of position measurements 26B, 27B of the object, a fitted mathematical approximation of the measured positions, a length of the sequence or a length of the fitted mathematical approximation.

(41) The object position sequence for the first object 26 is illustrated by the first object position sequence 26B. The object position sequence for the second object 27 is illustrated by the second object position sequence 27B.

(42) If the first object 26 travels within the left lane 22, then it will be appreciated that the first object position sequence generally follows the course of the left lane 22. Equally, if the second object 27 travels within the right lane 23, then it will be appreciated that the second object position sequence 27B generally follows the course of the right lane 23. The first and second objects 26, 27 are each moving relative to the road 20. On the basis that it is likely that the first and second objects are each travelling down the centre of a respective lane most of the time, then movement of the first and second objects generally maps their respective lane path.

(43) FIG. 4 shows a more complex scenario for the ego vehicle 25. In the scenario of FIG. 6, the ego vehicle 25 has detected six objects: the first to sixth objects 30, 31, 32, 33, 34, 35. The driver assistance system has sequentially measured the position of each of the six objects 30, 31, 32, 33, 34, 35 to form six separate object position sequences, illustrated as follows on FIG. 4:

(44) First object 30—object position sequence shown by open pentagons;

(45) Second object 31—object position sequence shown by open squares;

(46) Third object 32—object position sequence shown by filled circles;

(47) Fourth object 33—object position sequence shown by open diamonds;

(48) Fifth object 34—object position sequence shown by open circles, and;

(49) Sixth object 35—object position sequence shown by four-pointed stars.

(50) Each measured position may be transformed into co-ordinates that are in a rest-frame of the ego vehicle 25. Accordingly, compensation for motion of the ego vehicle 25 may be achieved. For the avoidance of doubt the rest-frame of the vehicle means a co-ordinate system in which the ego vehicle is at rest, or not moving. The ego vehicle may be located at the origin of the rest-frame co-ordinate system. The transformation into the rest frame is performed for each sequence of measured object positions for each time step (i.e. each time the functions are evaluated) to compensate for motion of the ego vehicle.

(51) The fourth object 33 has moved from the right lane 23 into the central lane 21. In other words, the measured position sequence for the fourth object (open diamonds in FIG. 4) demonstrate that as the fourth object has travelled along the road it has changed lanes.

(52) Objects that are not moving relative to the road, i.e. static objects such as trees, road signs or other road furniture, may be discarded. A discarded object is not used in any further processing and is not used in the object clusters.

(53) FIG. 5 is a plot showing nine object tracks 1 to 9 (labelled as ObjHist 1 to ObjHist 9) in a further driving scenario. Each object track comprises a position sequence. The length of each object track may be equal to the length of a line passing through each of the points of the position sequence.

(54) Object track 1 is shown as “open circles”, and has a length of 91.66 metres;

(55) Object track 2 is shown as “plus signs”, and has a length of 86.70 metres;

(56) Object track 3 is shown as “asterisks”, and has a length of 33.15 metres;

(57) Object track 4 is shown as “crosses (x)”, and has a length of 83.11 metres;

(58) Object track 5 is shown as “open diamonds”, and has a length of 97.89 metres;

(59) Object track 6 is shown as “open stars”, and has a length of 88.28 metres;

(60) Object track 7 is shown as “open upwards-pointing triangles”, and has a length of 31.45 metres;

(61) Object track 8 is shown as “open leftwards-pointing triangles”, and has a length of 92.91 metres, and;

(62) Object track 9 is shown as “open rightwards-pointing triangles”, and has a length of 75.42 metres.

(63) It is clear from FIG. 5 that some of the object tracks have relatively diverged from one another and some of the object tracks have converged to one another. Such object track behaviour may be due to the corresponding vehicle changing lanes or leaving/entering the road via a slip road, for example.

(64) The distribution of measured positions shown in FIG. 5 constitutes a starting point for a system or method embodiment according to the present invention. The measured positions may be the outputs from a vehicle radar system, for example.

(65) The initial phase of the embodiment is to pre-cluster the object tracks and their corresponding measurement positions into a number of object clusters in an object cluster collection. In other words, initially, in a pre-clustering phase, the assignment of the measured object positions to the object clusters may be based on the relative proximity of the measured object positions. The pre-clustering stage may correspond to step a). Subsequently, the object clusters are optimised. Object clusters may be added to the collection. Object clusters may be removed from the collection.

(66) In the pre-clustering phase, the assignment of the measured object positions to the object clusters may be based on the relative proximity of the measured object positions. In such an example, a first pre-clustering step is to order the object tracks in descending order according to their respective lengths. For example, for the nine object tracks shown in FIG. 5, the object tracks are ordered as follows:

(67) Object track 5, which has a length of 97.89 metres;

(68) Object track 8, which has a length of 92.91 metres;

(69) Object track 1, which has a length of 91.66 metres;

(70) Object track 6, which has a length of 88.28 metres;

(71) Object track 2, which has a length of 86.70 metres;

(72) Object track 4, which has a length of 83.11 metres;

(73) Object track 9, which has a length of 75.42 metres;

(74) Object track 3, which has a length of 33.15 metres;

(75) Object track 7, which has a length of 31.45 metres.

(76) A second pre-clustering step is iterating through all object tracks, starting with the object history ObjHist(i) (a reference object track), where i is an index from 1 to NumObjects, and where NumObjects is equal to the number of object tracks. Where the object tracks have been ordered as above, then when index i=1, the reference object track is the object track having the longest length.

(77) For each object track that has at least a minimum number of unvisited points measured points (MIN_NUMBER_POINTS_FOR_SPLINE), fit a polynomial spline to approximate all the UNVISITED measured object positions in the respective object track. Then, create a first (or next) object cluster within the object cluster collection. Next, copy all unvisited measured positions from the reference object track ObjHist(i) into the created object cluster and mark those measured positions in the reference object track as VISITED.

(78) In a third pre-clustering step, copy each measured position from all of the other object tracks ObjHist(k) [k=1 . . . NumObjects but i≠k] (i.e. the object tracks other than the reference object track) into the same newly-created object cluster and mark those measured points also as VISITED in the corresponding object track, if the measured position is close enough to the fitted polynomial spline derived for the reference object track. In this example, “close enough” means that the perpendicular distance between a given measured position and the fitted spline for the reference object track is within a predetermined threshold, MAX_NEIGHBOURHOOD_DISTANCE. MAX_NEIGHBOURHOOD_DISTANCE may be equal to 1 metre, for example. It will be appreciated that there are other possible for methods for defining the closeness of the measured position and the spline which are equally effective.

(79) Each object track may have a minimum number of measured positions, which may be equal to four, for example. Each object cluster may have a minimum number of measured positions assigned to it, which may be equal to four, for example.

(80) FIG. 6 illustrates the first object cluster generated according to the above methodology. Each measured position within the first object cluster is shown in FIG. 6 as surrounded by a square. The first object cluster contains all the position measurements of object track with the index 5 (ObjHist 5), which corresponds to the reference object track. The first object cluster also contains position measurements from other object tracks to that are “close enough” to the spline fitted to the points of the reference object track. Thus, a plurality of measured positions have been assigned to the first object cluster. The first object cluster is a member of the object cluster collection. The plurality of measured positions corresponding to the first object cluster correspond to a number of different object tracks in the example of FIG. 6. Measured points copied to the first object cluster are marked as VISITED.

(81) After generating the first object cluster as above, the remaining object clusters are generated and added to the object cluster collection in a similar manner. For example, the second object cluster is generated by fitting a polynomial spline to the UNVISITED measured positions in the second longest object track; creating a second object cluster; copying all UNVISITED measured positions from the second object track into the second object cluster, and; copying each UNVISITED measured position from all of the other object tracks into the second object cluster and mark them also as VISITED in the corresponding object track, if the measured position is close enough to the fitted polynomial spline derived for the second object track. The second object cluster is also thereby a member of the object cluster collection.

(82) This process is repeated until all of the UNVISITED measured positions from the object tracks have been assigned to an object cluster and are consequently marked as VISITED.

(83) FIG. 7 illustrates six object clusters generated according to this methodology. The six object clusters are each part of the object cluster collection.

(84) As is evident from FIG. 7, the result of the pre-clustering process may be insufficient for the identification of lane positions on the road using the object clusters. In other words, it is the clusters of FIG. 7 do not follow real-world, plausible, lanes on the road. Consequently the object clustering should be optimised. A system or method according to the present invention achieves such optimisation.

(85) In particular, the real-world plausibility of the relative position of the object clusters to each other can be checked and acted upon to alter the object clusters collection. The criteria for the plausibility of clustering (i.e. the object cluster collection) may include the following:

(86) confluence of individual object clusters in the collection with each other;

(87) inner or outer location of an individual object cluster relative to all object clusters in the collection;

(88) intersections, or contacts, between the object clusters in the collection relative to one another;

(89) parallelism of the object clusters in the collection relative to one another.

(90) Each of these criteria is discussed in more detail below.

(91) In general, the system of the present invention, calculates a first diagnostic for each of the object clusters. The first diagnostic is a descriptive variable that describes some aspect of the object clusters. A value for the first diagnostic for a given object cluster reflects that descriptive variable for the given object cluster.

(92) A calculated value for the first diagnostic potentially (see below) allows the selection of one of the object clusters in the collection as a rogue object cluster. The rogue object cluster is the object cluster that is an outlier relative to the other object clusters in the collection.

(93) In the embodiment described herein, the first diagnostic is confluence. The value for the first diagnostic for a particular object cluster is the number of other object clusters with which the particular object cluster is confluent. Two object clusters are confluent if they converge or intersect each other with an increase in their x-coordinate (using the co-ordinate system of FIGS. 5-12, for example).

(94) If it is not possible to distinguish a rogue object cluster on the basis of the first diagnostic, a second diagnostic may be used to distinguish the rogue objection cluster. In the embodiment described herein, the second diagnostic is contact. Two clusters are in contact if they converge or diverge or intersect each other with an increase of their x-coordinate.

(95) Confluence and contact will be described with reference to FIG. 8. FIG. 8 shows a first object cluster 45, a second object cluster 46, and a third object cluster 47. The “close enough” boundaries 49, 50 of the first object cluster 45 are shown parallel to the first object cluster 45.

(96) In order to check if two object clusters are confluent or in contact, one object cluster is specified as a reference object cluster and another object cluster as a comparative object cluster. The object cluster with the longest length (the length of the imaginary line passing through all points in the object cluster) is defined as the reference object cluster, for example.

(97) In respect of the example situation of FIG. 8, consider that the reference object cluster is the first object cluster 45 and comparative object cluster is the second object cluster 46. Consider also the neighbourhood around the reference object cluster (that is, the space between the two boundaries 49, 50, in FIG. 8) and an extension portion 51 of the comparative object cluster (dashed line in red as an extrapolation up to ‘x’ meters of the comparative cluster to its right side). If the extension portion 51 of the comparative object cluster 46 enters into the neighbourhood of the reference object cluster 45 with increasing X coordinate, then the reference object cluster 45 and comparative object cluster 46 are the to be confluent with each other, otherwise they are not confluent with each other.

(98) In the example of FIG. 8, the first object cluster 45 and the second object cluster 46 are confluent and in contact with each other. Conversely, the first object cluster 45 and the third object cluster 47 are in contact with one another, but they are not confluent. Table 1 (below) shows the confluence relationships between the individual object clusters shown in FIG. 8.

(99) TABLE-US-00001 TABLE 1 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 1 not confluent not not confluent confluent confluent Cluster 2 confluent not not confluent confluent confluent Cluster 3 not not not not confluent confluent confluent confluent Cluster 4 not confluent not not confluent confluent confluent

(100) Table 2 (below) shows the contact relationships between the individual object clusters in FIG. 8:

(101) TABLE-US-00002 TABLE 2 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 1 not in in contact in contact not in contact contact Cluster 2 in contact not in not in in contact contact contact Cluster 3 in contact not in not in not in contact contact contact Cluster 4 not in in contact not in not in contact contact contact

(102) For ensuring object cluster plausibility, a confluence matrix is created. The confluence matrix is a (n+1)-by-(n+1) matrix, where n is the number of object clusters in the collection. An uncompleted confluence matrix is as follows in Table 3:

(103) TABLE-US-00003 TABLE 3 Cluster 1 . . . Cluster n Sums of rows Cluster 1 0 0/1 0/1 Σ . . . 0/1 0 0/1 Σ Cluster n 0/1 0/1 0 Σ Sums of columns Σ Σ Σ

(104) A cell in the matrix represents the relationship between the i-th and j-th (i, j=1, . . . n) object cluster and their relative confluence (or lack of). If two object clusters are confluent with each other AND both clusters are inner clusters, then the value 1 is assigned to the corresponding cell in the confluence matrix, otherwise the integer 0 is assigned. The (n+1)th row and the (n+1)th column represent the sums of the corresponding vertical and horizontal cells, respectively.

(105) In the example, the values for the confluence matrix include an assessment of whether the cluster in question is an “inner” or an “external” object cluster.

(106) An “inner” object cluster is one that is surrounded by at least one object cluster on the left side and at least one object cluster on the right side. An “external” object cluster is an object cluster that is not surrounded by any object clusters on the left side and the right side. See below for more detailed explanation of whether a particular object cluster is an inner or an external cluster.

(107) A particular object cluster is by definition neither confluent nor in contact with itself, and so the diagonal of the confluence matrix has all values equal to zero. Due to the symmetry of the confluence matrix, in further analysis only either the rows or the columns need to be considered. The further following description uses the rows, however, it will be appreciated that the columns could equally be used.

(108) As stated above, the (n+1)th column includes the sums of the corresponding rows. The row with the maximum sum corresponds to an object cluster that is an outlier or rogue object cluster. There are two cases:

(109) In the first confluence case, there is exactly one row having a highest unique value. In the second confluence case, there are two or more rows having the highest value. To break the degeneracy in the second confluence case, the second diagnostic is used. In the embodiment, the second diagnostic is the number of contacts.

(110) In the first confluence case, the object cluster corresponding to the row in the confluence matrix having the highest unique value is identified as the rogue object cluster. It will be noted that the rogue object cluster includes measured positions from a number of object tracks. From those object tracks with measurements included in the rogue object cluster, the object track having the longest length is identified as a rogue object track. All of the measured positions corresponding to the rogue object track are marked as outliers and are removed from every object cluster in the collection in which those measured positions are comprised. Next, all of the other measured points included in the rogue object cluster are marked as being UNVISITED in the corresponding object tracks in which they are included. The rogue object cluster is then removed from the object cluster collection. Finally, the released points (i.e. those marked as UNVISITED) are reassigned to the remaining object clusters in the object cluster collection in an appropriate way, for example based on their distance to those object clusters.

(111) In the second confluence case, there are two (or more) rows in the confluence matrix having the same highest value for the sum of their row. In this second case, an (m×2) contact matrix is generated, where m<n, and m is equal to the number of object clusters in the collection having the same highest value for the sum of their row in the confluence matrix, and n is equal to the number of object clusters in the current object cluster collection. For each of the object clusters having the same highest value for the sum of their row in the confluence matrix, the number of contacts is calculated. Together these calculations form a contact matrix. An example of a contact matrix is shown in Table 3 (below).

(112) TABLE-US-00004 TABLE 4 Cluster number of contacts u N v M . . . . . . w P

(113) The cells in the first column of the contract matrix contain the indexes of the object clusters with the maximum sum of their row in the confluence matrix. The cells in the second column contain values which correspond to the number of other object clusters in the object cluster collection with which the relevant object cluster has a contact. The same procedure is applied to the results of the contact matrix as for the confluence matrix. That is, the maximum value in the second column of the contact matrix can be unique or there can two or more rows with the same highest value (i.e. same number of contacts).

(114) Accordingly, two different contact cases are distinguished. In the first contact case, there is exactly one row having a highest unique value for the number of contacts.

(115) In the second contact case, there are two or more rows having the same highest value for the number of contacts. To break this degeneracy in the second contact case, a third diagnostic is used. In the embodiment described herein, the third diagnostic is parallelism.

(116) In the first contact case, the object cluster corresponding to the row in the contact matrix having the highest unique value is the rogue object cluster. It will be noted that the rogue object cluster includes measured positions from a number of object tracks. From those object tracks with measurements included in the rogue object cluster, the object track having the longest length is identified as a rogue object track. All of the measured positions corresponding to the rogue object track are marked as outliers and are removed from every object cluster in the object cluster collection in which those measured positions are comprised. Next, all of the other measured points included in the rogue object cluster are marked as being UNVISITED in the corresponding object tracks in which they are included. The rogue object cluster is then removed from the object cluster collection. Finally, the released points (i.e. those marked as UNVISITED) are reassigned to the remaining object clusters in the object cluster collection in an appropriate way, for example based on their distance to those object clusters.

(117) In the second contact case, there are two (or more) rows in the contact matrix having the same highest value for the number of contacts. In this second contact case, an (m×2) parallelism matrix is generated, where m<n, and m is equal to the number of object clusters in the collection having the same highest value for the number of contacts. For each of the object clusters having the same highest number of contacts, the number of parallelisms is calculated. Together these calculations form a parallelism matrix. An example of a parallelism matrix is shown in Table 5 (below).

(118) TABLE-US-00005 TABLE 5 Cluster number of parallelisms u N v M . . . . . . w P

(119) The cells in the first column of the parallelism matrix contain the indexes of the object clusters with the highest value for the number of contacts. The cells in the second column of the parallelism matrix contain values which correspond to the number of other object clusters in the cluster collection with which the relevant cluster is parallel.

(120) A similar procedure is applied to the results of the parallelism matrix as for the confluence and contact matrices. The difference for the parallelism matrix is that the object cluster having the lowest value in the second column of the parallelism matrix is identified as being unique or identified as being comprised in two or more rows with the same lowest value.

(121) Again two different parallelism cases are distinguished. In the first parallelism case, there is exactly one row in the parallelism matrix having a lowest unique value. In the second parallelism case, there are two or more rows in the parallelism matrix having the lowest value.

(122) In the first parallelism case, the object cluster corresponding to the row in the parallelism matrix having the lowest unique value is the rogue object cluster. It will be noted that the rogue object cluster includes measured positions from a number of object tracks. From those object tracks with measurements included in the rogue object cluster, the object track having the longest length is identified as a rogue object track. All of the measured positions corresponding to the rogue object track are marked as outliers and are removed from every object cluster in the object cluster collection in which those measured positions are comprised. Next, all of the other measured points included in the rogue object cluster are marked as being UNVISITED in the corresponding object tracks in which they are included. The rogue object cluster is then removed from the cluster collection. Finally, the released points (i.e. those marked as UNVISITED) are reassigned to the remaining object clusters in the collection in an appropriate way, for example based on their distance to those object clusters.

(123) In the second parallelism case, there are two (or more) rows in the parallelism matrix having the same lowest value for the number of parallelisms. In this case, each object cluster corresponding to a row in the parallelism matrix having the lowest value is a rogue object cluster. For each rogue object cluster, from those object tracks with measurements included in the rogue object cluster, the object track having the longest length is identified as a rogue object track. All of the measured positions corresponding to the rogue object track are marked as outliers and are removed from every object cluster in the collection in which those measured positions are comprised. Next, all of the other measured points included in the rogue object cluster are marked as being UNVISITED in the corresponding object tracks in which they are included. The rogue object cluster is then removed from the cluster collection. This is repeated for each rogue object cluster identified by the parallelism matrix. Finally, the released points (i.e. those marked as UNVISITED) are reassigned to the remaining object clusters in the collection in an appropriate way, for example based on their distance to those object clusters.

(124) The creation and evaluation of the confluence matrix, and, if necessary, the contact matrix, and, if necessary, the parallelism matrix continues until the sum of all rows and columns in the confluence matrix are equal to zero. When this condition is met, the remaining object clusters in the collection are verified and correct (i.e. optimised).

(125) As the ego vehicle and surrounding objects move relatively, position measurements of the objects are performed. These newly acquired measurements are designated as UNVISITED. The above-described pre-clustering and optimisation process can be performed to generate a cluster collection that takes account of the newly acquired points, which may be assigned to the object clusters in the object cluster collection. Thus, the object cluster collection is optimised on the basis of the newly acquired points and a number of pre-existing points. The system can thereby be a continuous process with repeating cycles, in which the pre-clustering and optimising of the object clusters in the collection is performed for each processing cycle.

(126) A Worked Example According to the First Embodiment Will Now be Described.

(127) For the example situation shown in FIG. 6, the results of which are shown in FIG. 7, the confluence matrix is calculated as shown Table 6. There are six object clusters in the object cluster collection.

(128) TABLE-US-00006 TABLE 6 Sums of Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 rows Cluster 1 0 1 1 0 1 0 3 Cluster 2 1 0 0 0 0 0 1 Cluster 3 1 0 0 0 1 0 2 Cluster 4 0 0 0 0 0 0 0 Cluster 5 1 0 1 0 0 0 2 Cluster 6 0 0 0 0 0 0 0 Sums of columns 3 1 2 0 2 0

(129) There is exactly one row having the maximum value in the confluence matrix (with a sum equal to 3). Thus, the case is the first confluence case, as described above because there is a unique highest value for cluster 1. Accordingly, cluster 1 is identified as the rogue object cluster.

(130) The rogue object cluster (cluster 1) contains measured positions from each of the following object tracks:

(131) ObjHist 1

(132) ObjHist 2

(133) ObjHist 3

(134) ObjHist 5—rogue object track

(135) ObjHist 6

(136) ObjHist 7

(137) ObjHist 8

(138) ObjHist 9

(139) Of those object tracks, ObjHist5 has the longest length (97.89 metres). As such, ObjHist5 is identified as the rogue object track. All the measured points corresponding to ObjHist5 are labelled as outliers and removed from any and all object clusters to which they had previously been assigned. All the other measured positions that are comprised in the rogue object cluster (i.e. cluster1 minus the positions corresponding to the rogue object track) are labelled as UNIVISTED. The rogue object cluster (cluster 1) is removed from the object cluster collection.

(140) FIG. 9 illustrates the points 55 corresponding to the measured positions of the rogue object cluster (original cluster 1). Those points that correspond to the rogue object track (ObjHist5) are marked as outliers, and are not further used. Those points corresponding to other object tracks comprised in the rogue object cluster are marked as UNVISITED. The rogue object cluster is removed from the object cluster collection.

(141) The measured positions that are marked as UNVISITED are reassigned to the object clusters remaining in the object cluster collection. It is noted that the rogue object cluster (original cluster 1) has been removed from the collection and the remaining object clusters in the collection have been renumbered (see legend on FIG. 9). The resulting object cluster collection after the reassignment and removal of original cluster 1 is shown in FIG. 10.

(142) As will be appreciated from FIG. 10, now the only measured points that are not assigned to any object cluster are those that were comprised in the rogue object track (i.e. ObjHist5). These measured points are the outliers. It will be appreciated that the object clusters in the collection as shown in FIG. 10 have been optimised relative to the object clusters shown in FIG. 7 because the measured positions from object track ObjHist5 has been removed from the object clusters. ObjHist5 corresponds to measurements of a vehicle that has changed lanes, and therefore its movement does not accurately reflect the position of a single road lanes. The removal of the measured points of the rogue object track from the object clusters in the collection therefore permits more accurate lane determination by using the object clusters in the collection, which have been optimised.

(143) Further optimisation is possible however, which is described as follows.

(144) Based on the clusters showed in FIG. 10, a new confluence matrix is generated (see table 7 below).

(145) TABLE-US-00007 TABLE 7 Sums of Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 rows Cluster 1 0 0 0 0 0 0 Cluster 2 0 0 0 1 0 1 Cluster 3 0 0 0 0 0 0 Cluster 4 0 1 0 0 0 1 Cluster 5 0 0 0 0 0 0 Sums of columns 0 1 0 1 0

(146) In this confluence matrix, the maximum of sums of rows is 1. There are two rows with the sum equal to 1: Cluster 2 and Cluster 4. This confluence matrix forms an example of the second confluence case. In other words, there are two rows in the confluence matrix having the same highest value for the sum of their row (equal to 1). In this second confluence case, an (m×2) contact matrix is generated, where m is equal to the number of object clusters in the collection having the same highest value for the sum of their row in the confluence matrix. In this case therefore m=2.

(147) Table 8 shows the contact matrix for the two object clusters having the same highest value in the sum of their respective rows in the confluence matrix.

(148) TABLE-US-00008 TABLE 8 Cluster number of contacts Cluster 2 1 Cluster 4 3

(149) Cluster 2 has only one contact, in particular with Cluster 4; Cluster 4 has contact with three different clusters (Cluster 1, Cluster 2 and Cluster 3). Since the maximum value in the second column in Table 8 is unique (equal to 3), the first contact case occurs. Cluster 4 is therefore identified as the rogue object cluster.

(150) The same process is then applied to cluster 4 as was applied to original cluster 4 above. The longest object track in cluster 4 is object track ObjHist9, which also happens to be the only object track within the cluster 4. Object track ObjHist9 is therefore identified as the rogue object track. In the next step, all the measured positions corresponding to the rogue object track ObjHist9 are labelled as outlier and are then removed from any object cluster to which they are assigned. Rogue object cluster (cluster 4) is then removed from the object cluster collection. Because all of the measured points comprised in the rogue object track happened to correspond to the rogue object track, there are no points from other object tracks to reassign in this example. The result of this second iteration is shown in FIG. 11. The object cluster collection now comprises four object clusters (renumbered after the removal of the rogue object cluster from the object cluster collection).

(151) Further optimisation is possible however, which is described as follows.

(152) Based on the clusters showed in FIG. 11, a new confluence matrix is generated (see Table 9 below) for the four object clusters in the object cluster collection.

(153) TABLE-US-00009 TABLE 9 Cluster Cluster Cluster Cluster Sums of 1 2 3 4 rows Cluster 1 0 0 0 0 0 Cluster 2 0 0 0 0 0 Cluster 3 0 0 0 0 0 Cluster 4 0 0 0 0 0 Sums of columns 0 0 0 0

(154) Each and all of the rows have a sum equal to zero. This means that each of the four object clusters in the object cluster collection have a plausible course. The process of object cluster optimisation is completed.

(155) Subsequently, more position measurements are performed and received by the system for the same or newly recognised object. New measurements may be received during a single processing cycle. The new positions will initially be marked as UNIVISITED. The object cluster collection at the start of each cycle may be empty. A pre-clustering phase is performed to initially create and populate the object cluster collection, which is then optimised according to the methodology described herein. This pre-clustering and optimisation may be performed for each cycle. Each cycle may correspond to a time step in which new position measurements are acquired. This repeated, cyclical, processing may result in a constantly updated and optimised object cluster collection is maintained as object measurements are newly acquired by the vehicle.

(156) Each object cluster generally corresponds to vehicles that are travelling within real world traffic lanes. Accordingly, the mathematical description of the object clusters in the collection can be used to determine the position of those real world lanes, and for advanced driving aids, many of which require knowledge of real world lane positions.

(157) For completeness a number of example auxiliary functions used in the above-described embodiment will now be described.

(158) Curve Fitting

(159) As discussed above, a sequence of measured positions is approximated by a mathematical function across the range of the range of the measured positions. The sequence of measured positions may be those comprised in an object track or those comprised in an object cluster (which may include measured points from a plurality of object tracks). Such mathematical functions describe the relative positions of two object clusters and may permit calculation of confluence, contact, or parallelism of those object clusters.

(160) One such possibility for the mathematical function a single polynomial of nth order. By increasing the order of the polynomial, n, greater changes of curvature may be taken into account and good fitting results achieved. For example, it might be possible either to fit higher order polynomial, or to fit a spline consisting of lower order polynomials, through the given set of points (position measurements).

(161) In polynomial regression models, as the order increases, the X.Math.X.sup.T (where X is the Vandermonde-matrix) matrix becomes ill-conditioned. As a result, (X.Math.X.sup.T).sup.−1 may not be accurate and the parameters of the polynomial may be estimated with considerable error.

(162) Polynomials of the 3rd order are commonly used. However, due to the fact that fitting results based only on one cubic polynomial might be insufficient (see dashed brown curve 60 in FIG. 12), a cubic spline is used in the example embodiment.

(163) FIG. 12 illustrates a cubic spline fit to the points corresponding to each of four segments. The points are shown as asterisk symbols in FIG. 12. The range of x of the points has been divided into four segments, 61, 62, 63, 64. Using the cubic spline method, the range of x is divided into segments and for each segment a polynomial of 3rd order is fitted. Each adjacent pair of the piecewise polynomials 65, 66, 67, 68 have the same continuous function values at their connection point (knot). That is, the first derivatives, as well as the second derivatives, are equal at the knots between the two piecewise polynomials 65, 66, 67, 68 of the spline.

(164) It is evident from FIG. 12 that in this example the spline is a better approximation of the points that the third order polynomial 60 fitted over the full range of x.

(165) The algorithm of spline fitting consists of two steps. In the first step the range of x is divided into several segments and in the second step a polynomial for each segment is fitted.

(166) Dividing of X-Range Into Segments

(167) Depending on the number of data points the whole x range may be divided into a plurality of segments. For example, the number of segments may be equal to four. The prerequisite for creating segments is that the data points are sorted in ascending order according to their x coordinates.

(168) First, an interval is calculated by dividing the entire x-range into four equidistant subranges. Every segment has a left and a right border and every border goes exactly through a data point, the leftmost data point represents the left border of the first segment. Then as much data points are assigned to the segment until the x-distance between the left and the right border point is at least the calculated interval, provided that there are enough data points. The right border of a first subrange also forms the left border of the next subrange (in the sense of increasing x).

(169) After the first subrange is created, an amount of remaining data points are assigned to the next segment in the same way as in the case of the first segment until the x-distance between the left and the right border point is at least the calculated interval, provided that there are enough data points. The minimum number of data points for an interval may be a predetermined variable, MIN_NUMBER_POINTS_PER_INTERVAL. If there are not at least MIN_NUMBER_POINTS_PER_INTERVAL remaining data points, then all the remaining data points may be assigned to the previously created segment. MIN_NUMBER_POINTS_PER_INTERVAL may be equal to 4, for example.

(170) Creation of subsequent segments is continued until the range of x is divided up in to 4 segments, for example. FIG. 13 shows a flow chart illustrating the segment dividing process.

(171) Spline Fitting

(172) This section describes how to perform a curve fitting as a process of constructing a mathematical function, that has best fit to a set of data points as illustrated in FIG. 12. Depending on the number of data points, there can be assigned either one segment or up to four segments. Thus, depending on the number of segments there are two approaches:

(173) Spline Fitting if the Data Points are Grouped in One Segment

(174) The goal is to estimate the parameters of the following mathematical model:
ŷ.sub.i=p(x.sub.i)=a.sub.0+a.sub.1.Math.x.sub.i+a.sub.2.Math.x.sub.i.sup.2+a.sub.3.Math.x.sub.i.sup.3,∀x.sub.L≤x.sub.i≤x.sub.R

(175) Eq. (1) for i=1, . . . , N; N≥M, where N is the number of data points in the data set and M=4 is the number of parameters to be estimated. Equation 1 describes the relationship between the x and y coordinates of the data points. A method of ordinary least squares (OLS) is used with the goal of minimizing the sum of the squares of the differences between the observed y coordinates in the given dataset and those predicted by a linear function of a set of explanatory variables (y is the dependent variable, referred to also as a regressant, whereas x is the independent variable, also known as explanatory variable or as regressor; y is regressed on x). Visually this is seen as the sum of the vertical distances between each data point y.sub.i in the set and the corresponding point ŷ.sub.i on the regression curve—the smaller the differences, the better the model fits the data.

(176) The estimation problem is formulated as follows:

(177) Minimize the objective function

(178) $\begin{array}{cc}f\left(x\right)=\frac{1}{2}\underset{i=1}{\overset{N}{.Math.}}{r}_i^2=\frac{1}{2}\underset{i=1}{\overset{N}{.Math.}}{\left(y_i-{\hat{y}}_i\right)}^2=\frac{1}{2}\underset{i=1}{\overset{N}{.Math.}}{\left(y_i-p\left(x_i\right)\right)}^2& \mathrm{Eq}.\left(2\right)\end{array}$
without any constraints.

(179) In matrix notation, the modeled relationship between x- and y-coordinates of all data points can be written as:

(180) $\begin{array}{cc}\underset{\_}{Y}=\underset{¯}{X}.Math.\underset{¯}{\hat{a}}& \mathrm{Eq}.\left(3\right)\\ \underset{¯}{Y}=\left[\begin{array}{c}{y}_1\\ y_2\\ \mathrm{.Math.}\\ y_N\end{array}\right]& \mathrm{Eq}.\left(4\right)\\ \underset{¯}{X}=\left[\begin{array}{cccc}1& x_1& x_1^2& x_1^3\\ 1& x_2& x_2^2& x_2^3\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 1& x_N& x_N^2& x_N^3\end{array}\right]& \mathrm{Eq}.\left(5\right)\\ \underset{¯}{\hat{a}}=\left[\begin{array}{c}{\hat{a}}_0\\ {\hat{a}}_1\\ {\hat{a}}_2\\ {\hat{a}}_3\end{array}\right]& \mathrm{Eq}.\left(6\right)\end{array}$

(181) The sum of squared residuals in matrix notation is then

(182) $\begin{array}{cc}f\left(\underset{¯}{\hat{a}}\right)=\frac{1}{2}{\underset{¯}{r}}^T.Math.\underset{¯}{r}=\frac{1}{2}.Math.{\left(\underset{\_}{Y}-\underset{¯}{X}.Math.\underset{¯}{\hat{a}}\right)}^T\left(\underset{¯}{Y}-\underset{¯}{X}.Math.\widehat{\underset{¯}{a}}\right)=\frac{1}{2}.Math.\left({\underset{¯}{Y}}^T.Math.\underset{¯}{Y}-2.Math.\underset{¯}{\hat{a}}.Math.{\underset{¯}{X}}^T.Math.\underset{¯}{Y}+{\underset{¯}{\hat{a}}}^T.Math.{\underset{¯}{X}}^T.Math.\underset{¯}{X}.Math.\underset{¯}{\hat{a}}\right)& \mathrm{Eq}.\left(7\right)\end{array}$
where Y is a column vector of y coordinates of all measured data points. In order to find {circumflex over (a)} that minimizes the objective function ƒ({circumflex over (a)}) one needs to take the first derivative of ƒ({circumflex over (a)}) with respect to {circumflex over (a)} and to set it equal to zero, where:

(183) $\begin{array}{cc}\frac{\partial f\left(\underset{¯}{\hat{a}}\right)}{\partial \underset{¯}{\hat{a}}}=\frac{1}{2}.Math.\left(2.Math.{\underset{¯}{X}}^T.Math.\underset{¯}{X}.Math.\underset{¯}{\hat{a}}-2.Math.{\underset{¯}{X}}^T.Math.\underset{¯}{Y}\right)=\underset{¯}{0}& \mathrm{Eq}.\left(8\right)\end{array}$

(184) As an aside, it is noted that when b and a are two n×1 vectors, then

(185) $\frac{\partial \left({\underset{\_}{b}}^T.Math.\underset{\_}{a}\right)}{\partial \underset{\_}{b}}=\frac{\partial \left(a^T.Math.\underset{\_}{b}\right)}{\partial \underset{\_}{b}}=\underset{\_}{b}.$
Let {circumflex over (b)} be a two n×1 vector and  a symmetric n×n matrix, then

(186) $\frac{\partial \left({\underset{\_}{b}}^T.Math.\underset{\_}{A}.Math.\underset{\_}{b}\right)}{\partial \underset{\_}{b}}=2.Math.\underset{\_}{A}.Math.\underset{\_}{b}$

(187) Eq. (8) leads to the set of simultaneous equations known as the normal equations:
X.sup.T.Math.X.Math.â=X.sup.T.Math.Y  Eq. (9)
where:

(188) Y is a (n×1) vector of observations on the dependent variable;

(189) â is a (4×1) vector of unknown polynomial parameters that is to be estimated;

(190) X is a (n×4) matrix which contains the observation on 4 independent variables for n observations, and;

(191) N is the number of data points.

(192) X.sup.T.Math.X and X.sup.T.Math.Y are known from the set of data points but â is unknown. To check that the solution of Eq. (9) is a minimum, the second derivative of ƒ(â) is taken, which is the same as the first derivative of Eq. (8), with respect to â. This yields to X.sup.T.Math.X. It is clear that, as long as X has full rank, this is a positive definite matrix and hence â as a solution of Eq. (9) is a minimum. There are two things to note about the (X.sup.T.Math.X) matrix. First, it is always square since it is n×n. Second, it is always symmetric.

(193) Spline Fitting if the Data Points are Divided Into Several Segments

(194) As shown in the example of FIG. 12, the data points are divided into four segments. In this example a spline consisting of four polynomials is fitted which are defined piecewise for each and every segment:

(195) $\begin{array}{cc}{\hat{y}}_i=s\left(\underset{\_}{\hat{a}},x_i\right)=\{\begin{array}{cc}{p}_1\left(\widehat{\underset{\_}{a}},x_i\right)={\hat{a}}_{10}+{\hat{a}}_{11}.Math.x_i+{\hat{a}}_{12}.Math.x_i^2+{\hat{a}}_{13}.Math.x_i^3,& \forall x_L\le x_i\le x_I\\ p_2\left(\widehat{\underset{\_}{a}},x_i\right)={\hat{a}}_{20}+{\hat{a}}_{21}.Math.x_i+{\hat{a}}_{22}.Math.x_i^2+{\hat{a}}_{23}.Math.x_i^3,& \forall x_I\le x_i\le x_{\mathrm{II}}\\ p_3\left(\widehat{\underset{\_}{a}},x_i\right)={\hat{a}}_{30}+{\hat{a}}_{31}.Math.x_i+{\hat{a}}_{32}.Math.x_i^2+{\hat{a}}_{33}.Math.x_i^3,& \forall x_{\mathrm{II}}\le x_i\le x_{\mathrm{III}}\\ p_4\left(\widehat{\underset{\_}{a}},x_i\right)={\hat{a}}_{40}+{\hat{a}}_{41}.Math.x_i+{\hat{a}}_{42}.Math.x_i^2+{\hat{a}}_{43}.Math.x_i^3,& \forall x_{\mathrm{III}}\le x_i\le x_R\end{array}& \mathrm{Eq}.\left(10\right)\end{array}$
where i=1, . . . , N and N is the number of data points.

(196) Unlike the above case where all data points are grouped in one segment, here fitting of a spline to data points must satisfy the so called equality constraints between adjacent segments, in addition to minimizing the sum-of-squares-of-errors. In the example of four segments, there are following constraints:

(197) the values of adjacent polynomials within a spline must be continuous at the boundary points (knots)
p.sub.i(a,x.sub.i=x.sub.I)−p.sub.2(a,x.sub.i=x.sub.I)=0
p.sub.2(a,x.sub.i=x.sub.II)−p.sub.3(a,x.sub.i=x.sub.II)=0
p.sub.3(a,x.sub.i=x.sub.III)−p.sub.4(a,x.sub.i=x.sub.III)=0

(198) the derivatives of adjacent polynomials within a spline must be continuous at the boundary points (knots)

(199) $\frac{\partial p_1\left(\widehat{\underset{\_}{a}},x_i=x_I\right)}{\partial x_i}-\frac{\partial p_2\left(\widehat{\underset{\_}{a}},x_i=x_I\right)}{\partial x_i}=0$$\frac{\partial p_2\left(\widehat{\underset{\_}{a}},x_i=x_{\mathrm{II}}\right)}{\partial x_i}-\frac{\partial p_3\left(\widehat{\underset{\_}{a}},x_i=x_{\mathrm{II}}\right)}{\partial x_i}=0$$\frac{\partial p_3\left(\widehat{\underset{\_}{a}},x_i=x_{\mathrm{III}}\right)}{\partial x_i}-\frac{\partial p_4\left(\widehat{\underset{\_}{a}},x_i=x_{\mathrm{III}}\right)}{\partial x_i}=0$

(200) The fitting problem can be summarized mathematically as follows:

(201) $\begin{array}{cc}\underset{\underset{\_}{\hat{a}}}{\min \arg }f\left(\underset{\_}{a},x_i\right)& \mathrm{Eq}.\left(11\right)\end{array}$
subject to C.Math.â=d
where

(202) 0$\begin{array}{c}\mathrm{Eq}.\left(12\right)\\ f\left(\widehat{\underset{\_}{a}},x_i\right)=\frac{1}{2}.Math.{\left(\underset{\_}{Y}-\underset{\_}{X}.Math.\widehat{\underset{\_}{a}}\right)}^T.Math.\left(\underset{\_}{Y}-\underset{\_}{X}.Math.\widehat{\underset{\_}{a}}\right)=\frac{1}{2}.Math.\left({\underset{\_}{Y}}^T.Math.\underset{\_}{Y}-2.Math.\widehat{\underset{\_}{a}}.Math.{\underset{\_}{X}}^T.Math.\underset{\_}{Y}+{\widehat{\underset{\_}{a}}}^T.Math.{\underset{\_}{X}}^T.Math.\underset{\_}{X}.Math.\widehat{\underset{\_}{a}}\right)\\ \underset{\_}{Y}=\{\begin{array}{c}{\left[\begin{array}{cccccc}{y}_L& \mathrm{.Math.}& y_I& y_I& \mathrm{.Math.}& y_R\end{array}\right]}^T,.fwdarw.2\mathrm{segments}\\ {\left[\begin{array}{ccccccccc}{y}_L& \mathrm{.Math.}& y_I& y_I& \mathrm{.Math.}& y_{\mathrm{II}}& y_{\mathrm{II}}& \mathrm{.Math.}& y_R\end{array}\right]}^T,.fwdarw.3\mathrm{segments}\\ {\left[\begin{array}{cccccccccccc}{y}_L& \mathrm{.Math.}& y_I& y_I& \mathrm{.Math.}& y_{\mathrm{II}}& y_{\mathrm{II}}& \mathrm{.Math.}& y_{\mathrm{III}}& y_{\mathrm{III}}& \mathrm{.Math.}& y_R\end{array}\right]}^T,.fwdarw.4\mathrm{segments}\end{array}\\ \widehat{\underset{\_}{a}}=\{\begin{array}{c}{\left[\begin{array}{cccccccc}{\hat{a}}_{10}& {\hat{a}}_{11}& {\hat{a}}_{12}& {\hat{a}}_{13}& {\hat{a}}_{20}& {\hat{a}}_{21}& {\hat{a}}_{22}& {\hat{a}}_{23}\end{array}\right]}^T,.fwdarw.2\mathrm{segments}\\ {\left[\begin{array}{cccccccccccc}{\hat{a}}_{10}& {\hat{a}}_{11}& {\hat{a}}_{12}& {\hat{a}}_{13}& {\hat{a}}_{20}& {\hat{a}}_{21}& {\hat{a}}_{22}& {\hat{a}}_{23}& {\hat{a}}_{30}& {\hat{a}}_{31}& {\hat{a}}_{32}& {\hat{a}}_{33}\end{array}\right]}^T,.fwdarw.3\mathrm{segments}\\ {\left[\begin{array}{cccccccccccccccc}{\hat{a}}_{10}& {\hat{a}}_{11}& {\hat{a}}_{12}& {\hat{a}}_{13}& {\hat{a}}_{20}& {\hat{a}}_{21}& {\hat{a}}_{22}& {\hat{a}}_{23}& {\hat{a}}_{30}& {\hat{a}}_{31}& {\hat{a}}_{32}& {\hat{a}}_{33}& {\hat{a}}_{40}& {\hat{a}}_{41}& {\hat{a}}_{42}& {\hat{a}}_{43}\end{array}\right]}^T,.fwdarw.4\mathrm{segments}\end{array}\\ \underset{\_}{X}=\{\begin{array}{c}\left[\begin{array}{cccccccc}1& x_L& x_L^2& x_L^3& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 1& x_I& x_I^2& x_I^3& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& x_I& x_I^2& x_I^3\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 1& x_R& x_R^2& x_R^3\end{array}\right],.fwdarw.2\mathrm{segments}\\ \left[\begin{array}{cccccccccccc}1& x_L& x_L^2& x_L^3& 0& 0& 0& 0& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 1& x_I& x_I^2& x_I^3& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& x_I& x_I^2& x_I^3& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& x_R& x_R^2& x_R^3\end{array}\right],.fwdarw.3\mathrm{segments}\\ \left[\begin{array}{cccccccccccccccc}1& x_L& x_L^2& x_L^3& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 1& x_I& x_I^2& x_I^3& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& x_I& x_I^2& x_I^3& 0& 0& 0& 0& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3& 0& 0& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& x_{\mathrm{III}}& x_{\mathrm{III}}^2& x_{\mathrm{III}}^3& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& x_{\mathrm{III}}& x_{\mathrm{III}}^2& x_{\mathrm{III}}^3\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& x_R& x_R^2& x_R^3\end{array}\right],.fwdarw.4\mathrm{segments}\end{array}\\ \mathrm{Eq}.\left(16\right)\\ \underset{\_}{C}=\{\begin{array}{c}\left[\begin{array}{cccccccc}1& x_I& x_I^2& x_I^3& -1& -x_I& -x_I^2& -x_I^3\\ 0& 1& 2x_I& 3x_I^2& 0& -1& -2x_I& -3x_I^2\end{array}\right],.fwdarw.2\mathrm{segments}\\ \left[\begin{array}{cccccccccccc}1& x_I& x_I^2& x_I^3& -1& -x_I& -x_I^2& -x_I^3& 0& 0& 0& 0\\ 0& 1& 2x_I& 3x_I^2& 0& -1& -2x_I& -3x_I^2& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3& -1& -x_{\mathrm{II}}& -x_{\mathrm{II}}^2& -x_{\mathrm{II}}^3\\ 0& 0& 0& 0& 0& 1& 2x_{\mathrm{II}}& 3x_{\mathrm{II}}^2& 0& -1& -2x_{\mathrm{II}}& -3x_{\mathrm{II}}^2\end{array}\right],.fwdarw.3\mathrm{segments}\\ \left[\begin{array}{cccccccccccccccc}1& x_I& x_I^2& x_I^3& -1& -x_I& -x_I^2& -x_I^3& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 2x_I& 3x_I^2& 0& -1& -2x_I& -3x_I^2& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& x_{\mathrm{II}}& x_{\mathrm{II}}^2& x_{\mathrm{II}}^3& -1& -x_{\mathrm{II}}& -x_{\mathrm{II}}^2& -x_{\mathrm{II}}^3& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 2x_{\mathrm{II}}& 3x_{\mathrm{II}}^2& 0& -1& -2x_{\mathrm{II}}& -3x_{\mathrm{II}}^2& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& x_{\mathrm{III}}& x_{\mathrm{III}}^2& x_{\mathrm{III}}^3& -1& -x_{\mathrm{III}}& -x_{\mathrm{III}}^2& -x_{\mathrm{III}}^3\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 2x_{\mathrm{III}}& 3x_{\mathrm{III}}^2& 0& -1& -2x_{\mathrm{III}}& -3x_{\mathrm{III}}^2\end{array}\right],.fwdarw.4\mathrm{segments}\end{array}\\ \mathrm{Eq}.\left(17\right)\\ \underset{\_}{d}=\{\begin{array}{c}{\left[\begin{array}{cc}0& 0\end{array}\right]}^T,.fwdarw.2\mathrm{segments}\\ {\left[\begin{array}{cccc}0& 0& 0& 0\end{array}\right]}^T,.fwdarw.3\mathrm{segments}\\ {\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\end{array}\right]}^T,.fwdarw.4\mathrm{segments}\end{array}\end{array}$

(203) In order to solve the minimization problem in Eq. (11), the approach of Lagrange function with only equality constraint may be used. The Lagrange function is as follow:
L(â,λ)=ƒ(â)+λ.sup.T.Math.(C.Math.â−d)  Eq. (18)

(204) Eq. (18) is an equivalent representation of the problem given in Eq. (11) whose solution is the minimum of the Lagrange function. Since the Lagrange function is a convex quadratic function of â, the solution can be found from the optimality condition:

(205) $\begin{array}{cc}\frac{\partial L\left(\widehat{\underset{\_}{a}},\underset{\_}{\lambda }\right)}{\partial \widehat{\underset{\_}{a}}}=0& \mathrm{Eq}.\left(19\right)\\ \frac{\partial L\left(\widehat{\underset{\_}{a}},\underset{\_}{\lambda }\right)}{\partial \underset{\_}{\lambda }}=0& \mathrm{Eq}.\left(20\right)\end{array}$

(206) For the partial derivative of the Lagrange function with respect to the coefficients the following applies:

(207) $\begin{array}{cc}\frac{\partial L\left(\widehat{\underset{\_}{a}},\underset{\_}{\lambda }\right)}{\partial \widehat{\underset{\_}{a}}}=\frac{\partial f\left(\widehat{\underset{\_}{a}},\right)}{\partial \widehat{\underset{\_}{a}}}+\frac{\partial }{\partial \widehat{\underset{\_}{a}}}{\underset{\_}{\lambda }}^T.Math.\left(\underset{\_}{C}.Math.\widehat{\underset{\_}{a}}-\underset{\_}{d}\right)={\underset{\_}{X}}^T.Math.\underset{\_}{X}.Math.\widehat{\underset{\_}{a}}-{\underset{\_}{X}}^T.Math.\underset{\_}{Y}+{\underset{\_}{C}}^T.Math.\underset{\_}{\lambda }& \mathrm{Eq}.\left(21\right)\end{array}$

(208) For the partial derivative of the Lagrange function with respect to the coefficients the following applies:

(209) $\begin{array}{cc}\frac{\partial L\left(\widehat{\underset{\_}{a}},\underset{\_}{\lambda }\right)}{\partial \underset{\_}{\lambda }}=\frac{\partial f\left(\widehat{\underset{\_}{a}},\right)}{\partial \underset{\_}{\lambda }}+\frac{\partial }{\partial \underset{\_}{\lambda }}{\underset{\_}{\lambda }}^T.Math.\left(\underset{\_}{C}.Math.\widehat{\underset{\_}{a}}-\underset{\_}{d}\right)=\underset{\_}{C}.Math.\widehat{\underset{\_}{a}}-\underset{\_}{d}& \mathrm{Eq}.\left(22\right)\end{array}$

(210) Putting Eq. (19) and Eq. (20) together yields a square set of n+number of segments−1+p linear equations in variables â, λ:

(211) $\begin{array}{cc}\left[\begin{array}{cc}{\underset{\_}{X}}^T.Math.\underset{\_}{X}& {\underset{\_}{C}}^T\\ \underset{\_}{C}& \underset{\_}{0}\end{array}\right].Math.\left[\begin{array}{c}\widehat{\underset{\_}{a}}\\ \underset{\_}{\lambda }\end{array}\right]=\left[\begin{array}{c}{\underset{\_}{X}}^T.Math.\underset{\_}{Y}\\ \underset{\_}{d}\end{array}\right]& \mathrm{Eq}.\left(23\right)\end{array}$
where:

(212) Y is a ([n+m−1]×1) vector of observations on the dependent variable,

(213) â is a ([4.Math.m]×1) vector of unknown spline parameters that is to be estimated,

(214) X is a ([n+m−1]×[4.Math.m]) design matrix which contains the observation on 4.Math.m independent variables for n observations,

(215) C is a (p×[4.Math.m]) equality matrix,

(216) d is a (p×1) equality vector,

(217) n is the number of data points,

(218) m is the number of segments,

(219) p=is the number of equality constraints.

(220) The solution of Eq. (23) provides the desired solution of Eq. (11).

(221) Calculation of the Curve Length Where the Curve is Represented by Discrete Points

(222) To sort the object tracks or the object clusters according to their respective lengths it is necessary to calculate those lengths. The calculation of the length depends on the number of points (measured positions). As such, three cases are defined, for example:

(223) Case A: 0≤Number of Points≤1

(224) The length of a set of points which contains maximum one point is by definition equal to zero.

(225) Case B: 2≤Number of Points≤3

(226) If the number of points is two or three, then the length is calculated by summing of the polygonal chain segment lengths, 70, 71, as illustrated in FIG. 14. The length of the data set (consisting of three points) is the sum of L.sub.1 and L.sub.2, as shown in FIG. 14.

(227) Case C: Number of Points>3

(228) In case of more than three points, first a polynomial spline is fitted (as above), potentially to each of a plurality of segments. Then for every segment which is modelled as a polynomial
p.sub.i(x)=a.sub.0+a.sub.1.Math.x+a.sub.2.Math.x.sup.2+a.sub.3.Math.x.sup.3∀x.sub.L≤x≤x.sub.R  Eq. (24)
the segment length is calculated as follows:

(229) $\begin{array}{cc}{L}_i\left(p_i\right)={\int }_{x_L}^{x_R}\sqrt{1+{\left(\frac{{\mathrm{dp}}_i\left(x\right)}{\mathrm{dx}}\right)}^2}.Math.\mathrm{dx}={\int }_{x_L}^{x_R}\sqrt{1+{\left(a_1+2.Math.a_2.Math.x+3.Math.a_3.Math.x^2\right)}^2}.Math.\mathrm{dx}& \mathrm{Eq}.\left(25\right)\end{array}$

(230) Finally, the length of all points is determined by summing of the individual segment lengths.

(231) $\begin{array}{cc}L=\underset{i=1}{\overset{m}{.Math.}}{L}_i\left(p_i\right),\mathrm{where}m\mathrm{is}\mathrm{number}\mathrm{of}\mathrm{segments}& \mathrm{Eq}.\left(26\right)\end{array}$

(232) Coordinate Transformation

(233) An example to demonstrate coordinate transformation is showed in FIG. 15. The coordinate transformation of the point P from xy-coordinate system into x″y″-coordinate system is derived as follows:
x′.sub.P=x.sub.P−Δx
y′.sub.P=y.sub.P−Δy
x″.sub.P=a+b y″.sub.P=c−d
a=x′.sub.P.Math.cos γ c=y′.sub.P.Math.cos γ
b=y′.sub.P.Math.sin γ d=x′.sub.P.Math.sin γ
x″.sub.P=x′.sub.P.Math.cos γ+y′.sub.P.Math.sin γ=cos γ.Math.(x.sub.P−dx)+sin γ.Math.(y.sub.P−dy)  Eq. (27)
y″.sub.P=−x′.sub.P.Math.sin γ+y′.sub.P.Math.cos γ=−sin γ.Math.(x.sub.P−dx)+cos γ.Math.(y.sub.P−dy)  Eq. (28)
Eq. (27) and Eq. (28) can also be expressed in matrix notation:

(234) $\begin{array}{cc}\left[\begin{array}{c}{x}_P^{″}\\ y_P^{″}\end{array}\right]=\left[\begin{array}{cc}\cos \gamma & \sin \gamma \\ -\sin \gamma & \cos \gamma \end{array}\right].Math.\left[\begin{array}{c}\left(x_P-\mathrm{dx}\right)\\ \left(y_P-\mathrm{dy}\right)\end{array}\right]& \mathrm{Eq}.\left(29\right)\end{array}$

(235) Calculation of the Distance Between a Point and a Spline

(236) In order to calculate the distance between a point and a spline it is necessary to determine those segments (or segment) of the spline against which the distance must be calculated. Hence, for each segment, two coordinate systems are created:

(237) x.sub.1/y.sub.1: a coordinate system at the beginning of the segment where the x.sub.1-axis is the tangent of the polynomial segment at its beginning.

(238) x.sub.2/y.sub.2: a coordinate system at the end of the segment where the x.sub.2-axis is the tangent of the polynomial segment at its end.

(239) These coordinate systems are illustrated in FIG. 16. First, second, third and fourth segments 72, 73, 74, 75 of the spline are shown. The point in question, point P, is shown.

(240) The coordinates of the point P in question are transformed once into x.sub.1/y.sub.1-coordinate system and once into x.sub.2/y.sub.2-coordinate-system. If the x-coordinate of the point in x.sub.1/y.sub.1-coordinate-system is greater than or equal to zero and in x.sub.2/y.sub.2-coordinate-system the x-coordinate is smaller than zero, then the corresponding segment represents those polynomial against which the distance will be calculated. In the example of FIG. 16, this is the third segment 74.

(241) The situation is illustrated in FIG. 17, in which the distance between a segment 76 of the spline and the point P is calculated. Consider that the segment 76 is represented by a cubic polynomial and a point as depicted in FIG. 17. The goal is to calculate the shortest distance δ between the cubic polynomial and the point P.

(242) The distance δ can be expressed as a function depending on x as follows:
δ.sup.2(x)=(x−x.sub.P).sup.2+(y−y.sub.P).sup.2=(x−x.sub.p).sup.2+(p(x)−y.sub.P).sup.2  Eq. (30)

(243) To find the minimum δ, the derivative of Eq. (30) is set to zero:

(244) $\begin{array}{cc}\frac{d}{\mathrm{dx}}{\delta }^2\left(x\right)=0\mathrm{where}& \mathrm{Eq}.\left(31\right)\\ \frac{d}{\mathrm{dx}}{\delta \left(x\right)}^{2}2.Math.\left(x-x_P\right)+2.Math.\left(p\left(x\right)-y_P\right).Math.\frac{d}{\mathrm{dx}}p\left(x\right)=6.Math.a_3^2.Math.x^5+10.Math.a_2.Math.a_3.Math.x^4+\left(4.Math.a_2^2+8.Math.a_1.Math.a_3\right).Math.x^3+\left(6.Math.a_0.Math.a_3+6.Math.a_1.Math.a_2-6.Math.a_3.Math.y_P\right).Math.x^2+\left(4.Math.a_0.Math.a_2+2.Math.a_1^2+2-4.Math.a_2.Math.y_P\right).Math.x+\left(2.Math.a_0.Math.a_1-2.Math.a_1.Math.y_P-2.Math.x_P\right)& \mathrm{Eq}.\left(32\right)\end{array}$
Solving Eq. (31) yields a set of complex and real roots r=(x.sub.1 x.sub.2 x.sub.3 x.sub.4 x.sub.5).sup.T. Now we consider only those roots which are real and lie in the interval between x.sub.min and x.sub.max.
r.sub.reduced=r where x.sub.i.Math. Λ x.sub.min≤x.sub.i≤x.sub.max∀i=1, . . . ,5

(245) Now, we seek for those roots x.sub.0 within reduced roots r.sub.reduced so that it yields a minimum when inserted into Eq. (30). Therefore, the distance between the point P(x.sub.P/y.sub.P) and the polynomial p(x) is
δ(x.sub.0)=√{square root over ((x.sub.0−x.sub.P).sup.2+(p(x.sub.0)−y.sub.P).sup.2)}  Eq. (33)

(246) Checking Confluence and Contact of Two Clusters

(247) Given two object clusters, the following naming convention is used: Cluster 1 (also called as reference cluster) is the object cluster with the longest length and the other cluster is Cluster 2.

(248) FIG. 18 illustrates the process of calculating confluence and contact of two object clusters.

(249) First, two splines 77, 78 are fitted based on Cluster 1 and Cluster 2, respectively. The second spline 78 of Cluster 2 is extended on the right side by linear extrapolation (as shown in FIG. 18). The extrapolation of the second spline 78 is necessary in cases where Cluster 2 has not yet reached the neighbourhood of Cluster 1 but according to its tendency it will reach the neighbourhood of Cluster 1 in the near future. For example, the length of the extrapolation may correspond to 5 metres. Second, the whole range of the second spline 78 including the extension is equidistantly discretized into a series of sample points. Then, the distance between every sample point of Cluster 2 and the first spline 77 of Cluster 1 is calculated and entered in a table as in Table 10 (see below). Next, based on the results in Table 10 a distance spline is fitted. The distance spline is a spline fitted to the distances to Cluster 1 as a function of the x-coordinate of Cluster 2 (as exemplified in Table 10).

(250) TABLE-US-00010 TABLE 10 x-coordinate of distance to Cluster 2 Cluster 1 x.sub.1 δ.sub.1 x.sub.2 δ.sub.2 . . . . . . x.sub.N δ.sub.N

(251) The two splines may be said to be in contact with one another if the distance between them is smaller than or equal to a threshold ε. Two splines may be the to be confluent if they are in contact and the first derivative of the distance spline at x.sub.C is not positive where x.sub.C is the x-coordinate where distance spline is equal to the threshold ε. This can be expressed mathematically as follows:

(252) At the real roots r=[x.sub.C1 . . . x.sub.Cm].sup.T of the equation
δ(x)=ε  Eq. (34)
the object clusters are in contact. If there are no real roots, the object clusters are not in contact with each other.

(253) If the solution of Eq. (34) contains real roots and the inequality

(254) $\begin{array}{cc}\frac{d}{\mathrm{dx}}\delta \left(x\right){|}_{x=x_{\mathrm{Ci}}}<0,\mathrm{where}i=1,\mathrm{.Math.},m& \mathrm{Eq}.\left(35\right)\end{array}$
is satisfied at least for one real root, then the clusters are confluent.

(255) Parallelism of Two Clusters

(256) In geometry, two lines are the to be parallel if they are in a plane and do not intersect or touch each other at any point. Since the object clusters include the points (corresponding to measured positions), the geometric approach used for lines is not simply applied to the parallelism of the object clusters. Accordingly, the following example methodology may be used for the parallelism of a pair of object clusters.

(257) First, for each of two object clusters a spline is fitted. Next, the shortest spline is resampled at equidistant x-coordinates, forming a series of sample points along the shortest spline. Then, for every sample point of the shortest spline the shortest distance to the longest spline is calculated. The maximum and minimum of those shortest distances are calculated. The difference between the maximum and minimum of all those distances is calculated. If the value of the difference is smaller than or equal to a predetermined threshold, then the two object clusters in question may be parallel with each other, otherwise they may not be parallel with each other.

(258) Determine if a Cluster is Inner or External Cluster

(259) An object cluster C.sub.R that has at least one other object cluster C.sub.i on its left side and at least one other object cluster on its right side may be defined to be an inner cluster. An external object cluster has at least one side (i.e. left or ride side) on which no other object clusters are located. The below methodology provides an example for determining whether a particular object cluster is inner cluster or an external cluster.

(260) First, fit a cubic spline based on cluster C.sub.R, where C.sub.R is the particular object cluster that is to be checked if it is inner or external cluster. Second, iterate over all other clusters C.sub.i where i≠R in the cluster object collection. For each other cluster C.sub.i, transform its coordinates into the coordinate system of C.sub.R. The coordinate system of C.sub.R slides over the spline of C.sub.R and has the same orientation as the tangent of the spline at the point where the origin of C.sub.R-coordinate system is located (see FIG. 19). Finally, check the sign of transformed y-coordinates of points of every cluster C.sub.i where i≠R and x.sub.Transformed≤h. If the values of the transformed y-coordinates of all other object clusters include both positive and negative values, then the Cluster C.sub.R is an inner cluster, otherwise the cluster C.sub.R is an external cluster.

(261) Five object clusters as exemplarily depicted in FIG. 19. Considering Cluster 3 as the object cluster in question, the y-coordinate of every point P.sub.k(x≤h, y) ∈ C.sub.i, where i=1, 2, 4, 5 which is transformed into the x.sub.3/y.sub.3-coordinate system, is negative. Thus, Cluster 3 is identified as an external cluster.

(262) Considering Cluster 5 as the object cluster in question, and applying the same transformation on P.sub.k(x≤h, y) ∈ C.sub.i, where i=1, 2, 3, 4 into x.sub.5/y.sub.5-coordinate system, yields that the y-coordinate of every point P.sub.k ∈ C.sub.i is positive for i=1, 2, 3 and is negative at the same time for i=4. Thus, Cluster 5 is identified as an inner cluster.

(263) When used in this specification and claims, the terms “comprises” and “comprising” and variations thereof mean that the specified features, steps or integers are included. The terms are not to be interpreted to exclude the presence of other features, steps or integers.

(264) The features disclosed in the foregoing description, or in the following claims, or in the accompanying drawings, expressed in their specific forms or in terms of a means for performing the disclosed function, or a method or process for obtaining the disclosed results, as appropriate, may, separately, or in any combination of such features, be utilised for realising the invention in diverse forms thereof.

(265) While the invention has been described in conjunction with the exemplary embodiments described above, many equivalent modifications and variations will be apparent to those skilled in the art when given this disclosure. Accordingly, the exemplary embodiments of the invention set forth above are considered to be illustrative and not limiting. Various changes to the described embodiments may be made without departing from the spirit and scope of the invention.

(266) While the above description constitutes the preferred embodiment of the present invention, it will be appreciated that the invention is susceptible to modification, variation and change without departing from the proper scope and fair meaning of the accompanying claims.