Field of the invention

This invention concerns a method and system of processing data gathered using a range sensor. The invention has particular, but not exclusive application, to the processing of data gathered using a laser scanner located close to the ground, for example mounted on a vehicle such as a car or van. The invention also concerns a data carrier having instructions thereon and map data generated by the method and system.

Background to the invention It is possible to generate orthrectified views from data gathered by ground based vehicles. Such ground based vehicles comprise laser scanners for measuring the range (distance) of objects from the vehicle. From this data and GPS data, the position of an object can be determined. This may be useful in creating ground control points (GCPs) that can be used to geo- reference image data. Such image data may be used to generate aerial views of the land surface.

A problem with such views is that many of the features of interest, such as features of a road, may be obscured from view by objects located above, such as tree foliage. Preferences for displaying certain features in the aerial image over others may be achieved manually, however for huge sets of data such manual processing of the data is simply not possible and cannot be achieved in real-time. There is a need for a method for removing features not of interest to a viewer that can be computer-implemented such that the images may be created in real-time.

Summary of the invention According to a first aspect of the invention there is provided a method of processing data gathered using a range sensor, the data comprising a plurality of points associated with one or more objects, the method comprising:

determining a reference line extending from the range sensor; and identifying whether each of the plurality of points is a visible or invisible point by:

for each point of the plurality of points, determining a distance from the reference line to the point along a line perpendicular to the reference line and intersecting the point; and, if the distance is greater than a corresponding distance for each of the points of the plurality of points that has a smaller polar angle from the reference line, identifying the point as a visible point, else identifying the point as an invisible point.

In this way, the method systematically identifies points associated with objects to be and not to be displayed on an aerial map of the objects made from the points. In particular, the method may identify points associated with objects overlying lower objects as invisible points such that an aerial map generated from these identifications includes details of the lower objects. Accordingly, the method may act as a "view from bottom" filter prioritising the visibility of objects that would otherwise be obscured by higher overlying objects in an aerial view. A further advantage is that the method does not require human judgement and therefore, can be computer- implemented such that identification of visible and invisible points is automated.

The method may comprise generating a map from the points identified as visible. The method may be carried out in real-time or at least pseudo real- time such that a map of the visible points is generated and displayed to a user as data from the range sensor is received, the map being updated continuously or periodically based on the received data. In particular, the processed data produced by the method may be used to orthorectify images, such as photographic images captured by a camera.

In one embodiment, the reference line passes between the plurality points, ie there is a number of points either side of the reference line. In such an embodiment, identifying whether each of the plurality of points is a visible or invisible point comprises:

for each point of the plurality of points, if the distance is greater than a corresponding distance for each of the points of the plurality of points that has a smaller polar angle from the reference line and is on a same side of the reference line, identifying the point as a visible point, else identifying the point as an invisible point. If the reference line passes through the plurality of points then separate comparisons may have to be carried out for the points located each side of the reference line to ensure that the visible and invisible points are correctly identified.

The reference line may be a line substantially 45 degrees to the horizontal.

The points may be defined in terms of locations of the points relative to the range sensor. For example, the method may be carried out on raw data from the range sensor with the reference line defined by a specified angle from the range sensor. The location of the range sensor may be the pole from which the polar angle is determined. Alternatively, the locations of the points may be defined as absolute locations on a map. This may allow a user to identify a height and viewing angle from which to calculate the visible and invisible points to create bespoke views of the objects. For example, a bottom up view with lower lying objects filtered out so as not to obscure higher lying objects. The data may be data gathered using a laser scanner. According to a second aspect of the invention there is provided a system of processing data gathered using a range sensor, the data comprising a plurality of points associated with one or more obj ects, the system comprising one or more processors arranged to:

determine a reference line extending from the range sensor; and identify whether each of the plurality of points is a visible or invisible point by:

for each point of the plurality of points, determining a distance from the reference line to the point along a line perpendicular to the reference line and intersecting the point and, if the distance is greater than a corresponding distance for each of the points of the plurality of points that has a smaller polar angle from the reference line, identifying the point as a visible point, else identifying the point as an invisible point. According to a third aspect of the invention there is provided a data carrier having instructions stored thereon, wherein the instructions when executed by a processor cause the processor to carry out the method of the first aspect of the invention. According to a fourth aspect of the invention there is provided map data comprising a plurality of points associated with one or more objects and, for each point, an indication of whether the point should be visible or invisible in an aerial view of the map data. The indication of whether the point is visible or invisible may have been determined in accordance with the method of the first aspect of the invention.

According to a fifth aspect of the invention there is provided a method for processing map data according to the fourth aspect of the invention, the method comprising receiving map data and outputting a signal to cause a display of points identified as visible points such that the visible points are not entirely obscured by any display of invisible points. According to a sixth aspect of the invention there is provided a system for processing map data according to the fourth aspect of the invention, the system comprising one or more processors arranged to receive map data and output a signal to cause a display of points identified as visible points such that the visible points are not entirely obscured by any display of invisible points.

According to a seventh aspect of the invention there is provided a data carrier having instructions stored thereon, wherein the instructions when executed by a processor cause the processor to carry out the method of the fifth aspect of the invention.

In one embodiment, the invisible points are not displayed. In another embodiment, the invisible points may be displayed to have a "translucent" appearance such that the visible points can be viewed therethrough.

Short description of the drawings

Embodiments of the invention will be now be described, by example only, with reference to the drawings, in which: -

Figure 1 shows a mobile mapping system (MMS) in accordance with an embodiment of the invention; Figure 2 is a flowchart illustrating a method in accordance with an embodiment of the invention;

Figure 3 is a flowchart of the method of identifying visible and invisible points in accordance with one embodiment of the invention; Figure 4 is a schematic illustration of data gathered by a laser scanner in accordance with an embodiment of the invention;

Figure 5 is a schematic illustration of processing a data point in accordance with an embodiment of the invention;

Figure 6 shows a standard aerial view obtained without "view from bottom" filtering; and Figure 7 shows an aerial view obtained with "view from bottom" filtering in accordance with an embodiment of the invention.

It is known to gather map data using a mobile mapping system (MMS), an example of which is shown in Figure 1. The MMS system comprises a vehicle, in this embodiment a van 21. The van 21 is provided with one or more cameras 29 and one or more, range sensors, in this embodiment laser scanner(s) 23. The looking angle of the one or more cameras 29 and laser scanner(s) 23 can be in any direction of the van 21 and thus can be forward looking, rearward looking, side looking or a combination of these.

The van 21 is further provided with a positioning system for determining a position of the van 21 . In this embodiment, the positioning system comprises a global navigation satellite system, such as GPS, unit connected to an antenna 28 and arranged to communicate with a plurality of satellites SLl , SL2, SL3 and to calculate a position from the received signals. The determined positions are fed into a processing system P.

The positioning system further comprises a DMI (distance measurement instrument). In this embodiment, the DMI is an odometer that measures a distance travelled by the van 221 by sensing the number of rotations of one or more of the wheels 22 of the van 21 . The DMI is connected to the processor P and the signals therefrom may allow the processor P to determine a position with increased accuracy compared to simply obtaining the position from the GPS unit.

The positioning system further comprises an IMU (Inertial Measurement System), which in this embodiment is implemented as three gyro units arranged to measure the rotational accelerations and translational accelerations along three orthogonal directions. The IMU is connected to the processor P and the signals thereform may allow the processor P to determine a position with increased accuracy compared to simply obtaining the position from the GPS unit and/or the DMI. The signals from the gyro units may also be used to determine the looking angle of the laser scanner(s) 23 relative to a reference surface of the Earth. The IMU may also comprise dead reckoning sensors (not shown). It will be noted that one skilled in the art may find many combinations of on board systems that can be used for forming a positioning system for determining an accurate location and orientation of the vehicle and the invention is not limited to the positioning system as described above. The MMS collects geographic data by taking pictures with the cameras 29 mounted on the van 21 and taking laser samples using laser scanner(s) 23. The cameras 29 and laser scanner(s) 23 are connected to processor P for processing of the one of both signals, possibly in "real-time". Processed images may be displayed on display 24 and a user may be able to alter the processing of the images via an input device, in this embodiment keyboard 26.

The laser scanner(s) 23 take laser samples while the van 21 is moving along a route, typically roads, of interest to gather data concerning the location of objects in the environment in which the van 21 is travelling, which may include data associated with a road surface, building blocks, trees, traffic signs, parked cars, people, direction signposts, curbs and vegetation, such as trees or bushes. The locations are positions relative to the corresponding laser scanner 23 that took the sample and may be translated into absolute positions on the Earth using the positional data obtained from the positioning system. Each laser scanner 23 is arranged to take a plurality of samples so as to gather data comprising a plurality of points associated with one or more objects. An example of the data that may be gathered at one instant is shown in Figure 4.

During sampling, the laser scanner(s) 23 gather a cloud of points dense enough to visualise a 3D representation of the objects present along a route travelled by the MMS. In this embodiment, the laser scanners(s) 23 are arranged to produce an output with minimal 35 Hz and 1 deg resolution in order to produce a dense enough cloud of points. A laser scanner such as

MODEL LMS291-S05 produced by SICK is capable of producing such an output. A preferred configuration of the laser scanners 23 is to have one or two scanners 23 scanning the area at the left and right side of the van 21 and one laser looking forward or rearward of the van 21. The scanners 23 may be arranged such that two of the scanners scan the same surface at di ffe r e nt t i m e i n s t ant s . I nt e rn at i o n a l p at e nt ap p l i c at i o n PCT/NL2007/050541 discloses advantages of using such a set-up.

Now referring to Figures 2 , 3, 4 and 5, a method of processing data gathered by the laser scanners 23 will now be described. Such a method may be carried out by processor P and as such may be embodied as instructions of a computer program to be executed by processor P. Alternatively, the raw data from the laser scanners 23 may simply be stored for later processing by a processor external to the MMS . The method comprises receiving data gathered by the laser scanners 102, determining a reference line 202 from the range scanner 23 , in this embodiment, the reference line 202 passing between the plurality of points 104, and identifying whether each of the plurality of points is a visible or invisible point 106. The method for identifying whether each of the plurality of points is a visible or invisible point (illustrated in Figure 3) is carried out separately for the points on each side of the reference line 202 (as illustrated by steps 106a and 106b). In this embodiment, the reference line 202 is a centre ray from the laser scanner 223 that divides the plurality of points 104 roughly in half. Projection line 212 is a line perpendicular to the reference line 202. Now referring to Figure 3, initially a variable, in this embodiment Max Distance, is set to zero 302. Then, for each point of the plurality of points 21 1 , starting from the point having the smallest polar angle (A) from the reference line 202, a distance (CurDist) is determined from the reference line 202 to the point 205 along a line 206 perpendicular to the reference line 202 and intersecting the point 205. If the distance is greater than Max Distance, then in step 306 the point is identified as a visible point and Max Distance is set equal to the determined distance. If the distance is equal to or less than Max Distance, then is step 308 the point is identified as an invisible point and Max Distance remains unchanged. Steps 304 to 308 are repeated for each point moving progressively outward from the point having the smallest polar angel from the reference line 202.

Pseudo code for carrying out the steps of Figure 3 may be written as follows: maxDist=0

For each ray, starting from rays closer to the reference (centre) ray,

curDist= distance from point to centre ray

if (curDist>maxDist)

{

point is visible maxDist=curDist;

}

Else

{

Point is not visible

}

The results of the processing may then be stored in memory as map data and/or output for display, for example on display 24. In one embodiment, the processor P may generate map data of the cloud of points obtained from the laser scanner(s) 23 including an identification of whether each point is a visible and invisible point when viewed in an aerial view.

In Figure 4, the points identified as invisible by this algorithm may be those generally indicated at 214.

Figures 6 illustrates an unfiltered points cloud map before the map has been filtered to remove the invisible points and Figure 7 shows a points cloud map that has been "view from bottom" filtered to only show points identified as visible points. As can be seen much of the undesirable above ground features, such as trees and bushes, have been removed so as surface features, such as the roads, are not obscured to the same degree as in the unfiltered map. In this way, this embodiment systematically identifies points associated with objects to be filtered from an aerial map of surface objects.

Furthermore, the visible points may be points more suitable for use as GCPs for geo-referencing image data, such as that obtained using the cameras 29. The foregoing detailed description of an embodiment of the invention has been presented for the purpose of illustration. It is not intended to be exhaustive or to limit the invention to the precise form disclosed and various modifications and alterations can be made to the described embodiment without departing from the scope of the invention.