WO2012089264A1

WO2012089264A1 - Method and apparatus for determining the position of a building facade

Info

Publication number: WO2012089264A1
Application number: PCT/EP2010/070904
Authority: WO
Inventors: Radoslaw Chmielewski
Original assignee: Tele Atlas Polska Spzoo
Current assignee: Tele Atlas Polska Spzoo
Priority date: 2010-12-30
Filing date: 2010-12-30
Publication date: 2012-07-05
Anticipated expiration: 2013-06-30

Abstract

A method of determining the position of a fagade comprises acquiring measurement data representative of received measurement signals, each received measurement signal representing a reflection of a transmitted measurement signal from a respective, different part of a scene; determining for each of the received measurement signals the lateral position from which that measurement signal was received; determining for each of a plurality of lateral positions a reflection count representative of the number of received measurement signals received from that lateral position; selecting the lateral position that has the maximum reflection count; and determining the position of part of the fagade from the selected lateral position.

Description

METHOD AND APPARATUS FOR DETERMINING THE POSITION OF A BUILDING

FACADE

Field

The present invention relates to a position-determining method and apparatus, for example a method and apparatus for determining automatically the position of a fagade, for instance the fagade of a building.

Background Electronic maps have become widely used, for example in vehicle navigation systems such as those manufactured by TomTom (RTM), handheld devices such as smart phones or other portable electronic devices, or in desktop computer applications. Such devices are able either to display such electronic maps and/or associated images or data to a user, or are able to use such electronic devices in interactive navigation applications.

Many electronic devices now include position-determination technology, for example

Global Positioning System (GPS) technology, that enables the device to determine its own position. Such devices are able to use electronic map data to display to a user a map of a determined location and/or to display images or other data associated with the location. The devices can also provide navigation directions based on the determined location and the electronic map data.

The electronic mapping industry has been putting increasing amounts of data into its electronic maps, for example the accurate representation of the number of lanes within a particular street or road, the positions of lanes and barriers, the identification and location of objects such as street signs and building footprints, and the inclusion of objects within a rich three-dimensional (3D) representation that portrays actual building facades and other features.

The inclusion of accurate 3D representations of building facades within or associated with electronic map data is particularly useful as it enables a user to more quickly and accurately to identify a location, and to determine their orientation with respect to the location, from displayed electronic map data. That can be particularly useful in vehicle navigation and mapping systems as a driver is generally not able to give displayed map data their full attention, as the position of the vehicle may be changing relatively rapidly, and as the driver may have to take driving decisions rapidly based on the displayed data.

The use of accurate 3D representations of real-world facades is not limited to navigation devices, but can be applicable to a wide range of different devices or applications that require the display of a representation of a particular location. Current methods of determining the position of facades, for example building facades, use data obtained from mapping vehicles. Such mapping vehicles are equipped with a variety of detectors, including laser scanners, radar devices, GPS devices and cameras. A computer-generated image of the surroundings of the vehicle can be obtained from the data and images acquired by the mapping vehicle. However, significant operator input is required in order to accurately determine the location or details of particular features. For example, in the case of building facades significant intervention may be required from an operator to review images and associated measurement, to select data points that may represent a building fagade and to extract information concerning details of the fagade, for example the roof line of the fagade. The generation of building fagade data for large regions of a map therefore can become very time consuming, and the accuracy of such fagade data depends on the expertise and subjective input of the operator.

Summary

According to a first aspect of the present invention there is provided a method of determining the position of a fagade, the method comprising:- acquiring measurement data representative of received measurement signals, each received measurement signal obtained from a respective, different part of a scene; determining for each of the received measurement signals the lateral position from which that measurement signal was received; determining for each of a plurality of lateral positions a reception count representative of the number of received measurement signals received from that lateral position; selecting the lateral position that has the maximum reflection count; and determining the position of part of the fagade from the selected lateral position. Each received measurement signal may represent a reflection of a transmitted measurement signal.

Thus, the position of a fagade can be determined automatically, for example without significant or any operator input.

Each received measurement signal may comprise a reflection of a transmitted measurement signal transmitted at a respective, different angle of a plurality of angles. A received measurement signal may be a measurement signal that has been absorbed and retransmitted or a measurement signal that has been scattered, for example backscattered, or a measurement signal that has been reflected substantially without absorption or scattering.

The measurement data may be acquired by a mapping vehicle. The angles may be defined with respect to the mapping vehicle or with respect to the facade. The method may comprise using a mapping vehicle equipped with at least one measurement device to acquire the measurement signals. The method may comprise transmitting at least one measurement signal along each of the plurality of angles and receiving reflections of the measurement signals. The plurality of angles may be angles separated by regular intervals, for example intervals of between 2 degrees and 0.1 degrees, for example intervals of 1 degree, 0.7 degrees, or 0.25 degrees. The plurality of angles may be a range of angles from 0 degrees to 180 degrees.

The lateral positions may be lateral positions defined with respect to a road or mapping vehicle, for example defined with respect to the centreline of a road.

The method may comprise determining for each of the received measurement signals a vertical position from which that measurement signal was received.

The method may comprise determining the lateral position for each of a plurality of different positions of the mapping vehicle, thereby determining the respective position of each of a plurality of parts of the fagade.

The method may comprise joining the determined positions of the plurality of parts of the fagade thereby to produce a line of the facade

The method may comprise, for each of the determined lateral positions, determining the greatest vertical position of the received measurement signals for that lateral position. Thereby a roof line of the fagade may be determined.

The method may comprise joining the positions of the received measurement signals having the greatest vertical positions for the determined lateral positions, thereby to produce a substantially continuous roof line of the facade

The method may comprise determining the vertical positions with respect to a reference position, for example a position of a road surface, and optionally a respective reference position is determined for each of the positions of the mapping vehicle.

The method may comprise discarding received measurement signals having a determined vertical position lower than a threshold height above the reference position, and optionally the threshold height is between 3m and 4m.

The method may comprise identifying received measurement signals that are received from non-building objects and applying a filter to discard or reduce the significance of such received measurement signals from non-building objects.

The method may comprise, for each received measurement signal, assigning an amplitude distribution that comprises a variation of amplitude with lateral position, and optionally summing the resulting amplitudes obtained for each of the lateral positions, wherein the reflection count for each lateral position comprises the summed intensities for that position.

The amplitude may be a probability amplitude representative of the signal from a particular position. The method may comprise defining an array comprising a plurality of cells, each cell having a respective lateral position, wherein the assigning of the amplitude distributions comprises assigning an amplitude distribution to each cell, and optionally the amplitude distribution assigned to each cell is the sum of the amplitude distributions assigned to measurement signals having lateral positions within that cell.

The determination of reflection count for each lateral position may comprise determining a reflection count for each cell.

The method may further comprise applying a non-linear filter or weighting to the amplitude distribution at each cell. The non-linear filter or weighting may be such as to increase the amplitude of the summed amplitude distribution for cells having a larger number of received measurement signals relative to the summed amplitude distribution having a smaller number of received signals.

The applying of the non-linear filter or weighting may comprise applying an alpha blending factor.

The cells of the array may represent lateral positions in two dimensions. The array may represent received measurement signals obtained for a plurality of positions of the mapping vehicle.

The measurement signals may comprise laser signals.

The method may comprise selecting the received measurement signals that have the selected lateral position, identifying those received measurement signals as being measurement signals received from the building fagade, and optionally mapping the fagade using the positions of the fagade-received measurement signals.

The method may comprise storing the positions of the measurement signals identified as being received from the fagade, for example in a fagade buffer.

The method may comprise providing display features, for example points, that have display positions that correspond to the positions of the fagade-received measurement signals thereby to display an image of the fagade.

The method may comprise associating the image of the fagade with electronic map data, and for example, using the image to render a 3D representation of a building for display on a navigation and/or mapping system, such as a vehicle personal navigation system (PND).

In further independent aspect of the invention there is provided a position determining system for determining the position of a fagade comprising:- means for acquiring measurement data representative of received measurement signals, each received measurement signal obtained from a respective, different point of a scene; means for determining for each of the received measurement signals the lateral position from which that measurement signal was received; means for determining for each of a plurality of lateral positions a reception count representative of the number of received measurement signals received from that lateral position; means for selecting the lateral position that has the maximum reception count; and means for determining the position of part of the fagade from the selected lateral position.

The system may comprise means for determining for each of the received measurement signals a vertical position from which that measurement signal was received.

The system may comprise means for determining the lateral position for each of a plurality of different positions of the mapping vehicle, thereby determining the respective position of each of a plurality of parts of the fagade.

The system may comprise means for joining the determined positions of the plurality of parts of the fagade thereby to produce a line of the facade

The system may further comprise means for determining, for each of the determined lateral positions, the greatest vertical position of the received measurement signals for that lateral position.

The system may comprise means for joining the positions of the received measurement signals having the greatest vertical positions for the determined lateral positions, thereby to produce a substantially continuous roof line of the facade

The system may comprise means for determining the vertical positions with respect to a reference position, for example a position of a road surface, and optionally a respective reference position is determined for each of the positions of the mapping vehicle.

The system may comprise means for discarding received measurement signals having a determined vertical position lower than a threshold height above the reference position, and optionally the threshold height is between 3m and 4m.

The system may comprise means for determining received measurement signals that are received from non-building objects and means for applying a filter to discard or reduce the significance of such received measurement signals from non-building objects.

The system may comprise means for assigning, for each received measurement signal, an amplitude distribution that comprises a variation of amplitude with lateral position, and optionally summing the resulting amplitudes obtained for each of the lateral positions, wherein the reflection count for each lateral position comprises the summed intensities for that position.

The system may comprise means for defining an array comprising a plurality of cells, each cell having a respective lateral position, wherein the means for assigning of the amplitude distributions may be configured to assign an amplitude distribution to each cell, and optionally the amplitude distribution assigned to each cell is the sum of the amplitude distributions assigned to measurement signals having lateral positions within that cell. The system may comprise means for applying a non-linear filter or weighting to the amplitude distribution at each cell, the non-linear filter or weighting being such as to increase the amplitude of the summed amplitude distribution for cells having a larger number of received measurement signals relative to the summed amplitude distribution having a smaller number of received signals.

The system may comprise means for transmitting the measurement signals and/or means for receiving the received measurement signals, for example a transmitter device and/or a detector device. The transmitter device and detector device may comprise a laser scanner.

The system may comprise means for selecting the received measurement signals that have the selected lateral position, identifying those received measurement signals as being measurement signals received from the building fagade, and optionally means for mapping the fagade using the positions of the fagade-received measurement signals.

In another independent aspect of the invention there is provided a position determination system for determining the position of a fagade comprising a processing resource that is configured to:- acquire measurement data representative of received measurement signals, each received measurement signal representing a reflection of a transmitted measurement signal from a respective, different point of a scene; determine for each of the received measurement signals the lateral position from which that measurement signal was received; determine for each of a plurality of lateral positions a reflection count representative of the number of received measurement signals received from that lateral position; select the lateral position that has the maximum reflection count; and determine the position of part of the fagade from the selected lateral position.

In another independent aspect of the invention there is provided a computer program product comprising computer-readable instructions that are executable to perform a method as claimed or described herein.

It will be appreciated that features described in relation to any of the above aspects of invention may also optionally be applicable to any other aspect of invention. Furthermore, it will also be appreciated that method features analogous to any described apparatus features are intended to fall within the scope of the disclosure and vice versa.

Brief Description of the Drawings

At least one embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

Figure 1 is a schematic illustration of a mapping vehicle in accordance with an embodiment; Figure 2 is a schematic illustration of a processing system according to an embodiment, for determining the position of a fagade;

Figure 3 is a flow chart illustrating a process for determining the position of a fagade according to an embodiment;

Figure 4 is a plot of laser points having different lateral positions obtained from measurements by the mapping vehicle;

Figure 5 is a plot of the laser points of Figure 4 after removal of laser points from heights below a predetermined threshold;

Figure 6 is a plot of the laser points of Figure 5, after a filtering process has been performed;

Figure 7 is a histogram of laser point count for different lateral positions;

Figure 8 is a plot of the laser points of Figure 6 in which identified positions of parts of a fagade have been connected together;

Figure 9 is a plot in which identified positions of the identified highest points of a fagade have been joined together;

Figure 10 is a representation of an array of cells in a lateral plane;

Figure 11 is a plot of a cosine function used to broaden each laser point;

Figure 12 is a histogram that shows individual and combined amplitude contributions from different laser points;

Figure 13 is an illustration of a non-linear filter according to an embodiment; and

Figure 14 is a schematic illustration of the position of laser points in a scene.

Detailed Description of Embodiments Figure 1 is an illustration of a mapping vehicle 2 that includes a vehicle navigation system 4 and associated laser sensors in the form of laser scanners 6, 8. The laser sensors are arranged symmetrically on each side of the vehicle, with one of the scanners 6 arranged on one side of the vehicle 2 and the other of the scanners 8 arranged on the other side of the vehicle 2. Each of the scanners comprises a laser transmitter for transmitting a pulsed or continuous beam of laser radiation to different points in a scene, a laser detector for detecting received laser radiation, and a processor for controlling the scanning of a laser beam by the scanners and for processing the results of measurements. The laser sensor processor is operable to determine the distance of a surface of a building 19, 20, object or other surroundings with which the laser sensor is aligned and from which the laser radiation is received using, for example, time-of-flight measurements or other known ranging techniques. Each laser scanner is configured to scan the laser beam across a laser scanned area 3, 5 of a scene and to perform range measurements along different directions within the laser scanned area. Any suitable laser scanners 6, 8 can be used, for example Sick (RTM) LMS291 -S05 scanners.

The navigation and position determination system 4 comprises a digital map or map database and satellite receivers (for example GPS or Galileo receivers) that are operable to determine the position of the mapping vehicle. A vehicle position determination module uses input from the satellite receivers to calculate an accurate position (and bearing if desired) for the vehicle, relative to the digital map. Any suitable navigation and position determination system 4 can be used. The mapping vehicle will usually also include various other transmitters and sensors, for example radar transmitters and sensors, and one or more cameras, in accordance with known mapping vehicle configurations.

In operation the mapping vehicle travels along a predetermined route comprising a plurality of road segments, and gathers measurement data as it travels. Subsequently the gathered data is sent to a processing apparatus 30 for further processing or analysis. In alternative embodiments the processing apparatus 30 is incorporated in the mapping vehicle 2.

The processing apparatus 30 is illustrated schematically in Figure 2 and comprises a personal computer (PC) or workstation that is connected to a display device 34, a data store 36 and a user input device or devices 38, in this case a computer keyboard and mouse.

The processing apparatus 30 comprises a central processing unit (CPU) 40 that is operable to load and execute a variety of software modules or other software components. In the embodiment of Figure 1 , the software modules include a data selection module 42 for selecting laser measurement data for use in subsequent processing and discarding some of the laser measurement data. The software modules also include a filtering/weighting module 44 for filtering or weighting the laser measurement data and a fagade calculation module 46 for determining the position of the fagade from the filtered/weighted laser measurement data. The processing apparatus also includes a hard drive. In the embodiment of Figure 1 the hard drive stores the laser measurement data received from the mapping vehicle.

The processing apparatus 30 also includes other standard components of a PC including RAM, ROM, a data bus, an operating system including various device drivers, and hardware devices (for example a graphics card) for interfacing with various peripheral devices. Such standard components are not shown in Figure 1 for clarity.

The data store 36 in the embodiment of Figure 1 includes a database that stores large number of different datasets, including digital map data. In operation the processing apparatus 30 is operable to update the digital map data stored in the data store 36 with the calculated fagade positions and/or other fagade features. In operation the laser sensors 6, 8 transmit laser signals that are received by surfaces (for example surfaces of buildings, walls, signs, trees or other features) present in a scene and received by the laser sensors. The laser sensors determine the distance of the surfaces from which the laser signals are received along the measurement directions using known techniques, and output sensor measurement signals representative of the determined distances and thus represent the surroundings of the vehicle on the road. As the vehicle travels, the measurement signal obtained from each of the sensors 6, 8 varies as the distance from the vehicle to roadside features varies.

In the embodiment of Figure 1 , each of the scanners 6, 8 is configured to repeatedly perform measurements at 1 degree increments, from 0 degrees to 180 degrees, in rapid succession. Any other suitable increment or range can be used in alternative embodiments, for example increments of 0.7 degrees or 0.25 degrees, and a range of 60 degrees to 120 degrees, or 90 degrees to 135 degrees, for example depending on the application and the expected position and size of buildings that may be present. The measurement signals are each transmitted in a direction perpendicular to the long axis of the mapping vehicle, and thus in a direction substantially perpendicular to the road. The angles can be defined with respect to the mapping vehicle so that, for example, an angle of 0 degrees corresponds to the laser scanner pointing directly down towards the road. That measurement at 0 degrees can be used as a reference measurement as described in more detail below.

Thus, for each position of the mapping vehicle, a set of 180 laser reflection measurements can be obtained from each scanner 6, 8 for angles from 0 degrees to 180 degrees. Each of the laser reflection measurements represents the reflection of the laser signal from a particular point on a building or other object. In practice some of the 180 laser reflection measurements obtained by each sensor for each mapping vehicle position will be null measurement signals, for example if there is no building or other object in the path of the transmitted signal for some angles. There may be null measurements for around 30% or less of the 180 laser reflection measurements in a city or town environment, or for around 50% of the measurements in a rural environment. The laser reflections are also referred to as laser points. Each set of laser reflection measurements is stored together with the position of the mapping vehicle, determined from GPS or other location-determination measurements, at the time the set of laser reflection measurements were taken.

It is feature of the described embodiment that the sets of received laser signals obtained for a particular road segment are processed to determine automatically the position of building facades present at either side of the mapping vehicle for that road segment. The roof line of the building fagade can also be determined automatically as will be described in more detail below. The process is illustrated in overview in the flow chart of Figure 3. At the first stage 50 of the process the laser point measurement data is acquired by the mapping vehicle. At the next stage 52 the lateral and vertical position of each laser point is determined, using known techniques, based on the known orientation (an angle between 0 degrees and 180 degrees) of the scanner at the time of measurement and the time between transmission of the laser signal and reception of the received signal.

The vertical positions are determined with respect to a reference height. In the embodiment of Figure 1 , the reference height is the height of the mapping vehicle above the road, which is determined from the laser point measurement data for a scanner angle of 0 degrees (when the laser scanner is pointing directly downwards towards the road).

The laser point measurement data obtained for a particular road segment, including the determined lateral and vertical positions of the laser points are then provided to the processing apparatus 30 for further processing.

In the embodiment of Figure 1 , an array or matrix comprising a plurality of cells is defined by the fagade calculation module 46. Each cell of the array or matrix represents a respective range of lateral positions for example defined by orthogonal x and y directions that are in the same plane as the road surface or mapping vehicle, with the vertical position then being the position in a z direction (although any suitable co-ordinate system can be used). The size of each cell can be set based on the expected accuracy of the determination of position of each laser point. Each of the laser points is assigned to a respective cell of the array or matrix based on the determined lateral position of the laser point. Often a single cell will have assigned to it many different laser points each of which has been received from points having substantially the same lateral positions but different heights.

Figure 4 is a plot of laser points having different lateral positions, obtained from measurements by the mapping vehicle for a particular road segment. The brighter areas of the plot show are areas from which a larger number of laser points are received. The location of the road surface 70 and the approximate location 72 of a fagade can be identified but it can also be seen that there is a significant amount of noise, and contributions from other features (which may be for example trees or streetlamps) that in practice prevent identification of the precise position of the building fagade without further processing of the data.

At the next stage 54, all of those laser points that have a vertical position below a predetermined threshold (for example less than 3m, or less than 4m) are discarded by the data selection module 42. That removes laser points that have been received from the road, for example. Figure 5 is a plot of the data of Figure 4 after the laser points having a vertical position below the threshold have been removed. It can be seen that the whole road surface has been removed from the analysis. However, some of the noise and contributions from other objects, such as trees and lamps, is still present.

Next, filtering and/or weighting processes are performed by the filtering/weighting module 44 at stage 56, in order to remove laser point data that is judged not to relate to building facades and/or to provide greater weight to laser point data that is likely to have been obtained from reflection from a building. The filtering and/or weighting processes that are performed by the embodiment of Figure 1 are described in more detail below. Figure 6 is a plot of the data of Figure 5 after the filtering and weighting processes have been performed and the building fagade can now be seen clearly, without significant additional contributions from other objects.

At the next stage 58, a laser point count for each of the different lateral positions is performed by the fagade calculation module 46 on the laser point data that has been subject to the data selection and filtering/weighting processes. Figure 7 is a histogram of the laser point count that is obtained for different lateral positions (different cells) in one direction perpendicular to the road (to the left or right of the road). It can be seen from Figure 7 that there is a strong peak in the laser point count for the cell that is located at 11 m from the centreline of the road, which indicates that the object at the distance 11 m from the centreline has the greatest vertical extent of any of the objects from

At the next stage, 60 the lateral position of a building fagade in a direction perpendicular to the road is determined automatically as being the lateral position in that direction for which the greatest number of laser points are obtained, after the filtering and weighting processes have been performed. In the example of Figure 7 it is clear that the lateral position of the fagade will be automatically determined as being at 11 m from the centreline of the road, for that position along the road.

The processes of stages 58 and 60 are usually repeated for different positions along the road to determine the lateral distance of the fagade from the road at those different positions along the road.

At the next stage 62, the height of the building fagade at a given position along the road can be determined, if desired, by determining the greatest vertical position of any of the laser points having the lateral position that was selected at stage 60 as being the lateral position of the fagade. In the embodiment of Figure 1 , the laser point data which has been determined as having a lateral position corresponding to the fagade is stored in a fagade buffer and the greatest vertical position for any of the laser point data stored in the fagade buffer is selected as being the height of the building fagade. In the example of Figure 7, the laser points assigned to the cell at 11 m from the centreline of the road are stored in the fagade buffer, the laser point stored in the fagade buffer having the greatest vertical position is identified, and that vertical position is identified as being the height of the fagade. At the next stage 64, the lateral positions of the fagade, and/or the determined vertical position of the top of the fagade, determined for different positions along the road can be joined if desired, thereby to map the building fagade. Figure 8 is a plot of the data of Figure 6 in which the identified lateral positions of the fagade have been joined to map the line of the fagade. In this case the fagade line extends from the bottom left to the top right of the figure.

Figure 9 is a plot in which the identified position (in both lateral and vertical directions) of the identified highest points of the fagade have been connected by a line 74 thereby to map, for example, a roof line of the fagade. A further line 76 is included in Figure 9 to indicate the street surface. The points plotted in Figure 9 represent the positions of each of the laser points identified as being obtained from the fagade (thus, each of the laser points stored in the fagade buffer). It can be seen that by plotting those laser points the fagade can be mapped.

The method illustrated in Figure 3 provides for rapid, automated determination of building or other facades.

As mentioned above, filtering and or weighting processes are performed at stage 56 of the process in order to remove laser point data that is judged not to relate to building facades and/or to provide greater weight to laser point data that is likely to have been obtained from reflection from a building fagade. It has been found that in many practical circumstances filtering and/or weighting of the laser point data can provide significant improvement in the accuracy of the automatic determination of the position of a fagade. The filtering and weighting processes performed by the embodiment of Figure 1 are now described in more detail.

Figure 10 shows a representation of the array in the x-y plane used by the fagade calculation module 46 to represent the laser points. The array comprises an array of cells 80, which in this case have dimensions of 0.25 metres by 0.25 metres. In this embodiment the accuracy of the determination of the position laser point in a lateral direction (thus, in the x-y plane) is around 1 metre. Therefore, although each laser point will be attributed to a particular cell, there is a significant probability that in reality the laser point was located in a different cell to that to which it was attributed.

The filtering/weighting module 44 modifies the laser point data of the array by assigning an amplitude distribution, otherwise referred to as a radial gradient, to each laser point location. The amplitude distribution comprises a variation of amplitude with lateral position. The amplitude distribution can be considered to be representative of a probability of the laser point being at that lateral position. In the embodiment of Figure 10 the amplitude distribution is represented by a cosine function centred around the centre point of the cell to which the laser point was originally attributed, as illustrated in Figure 11 . The function in this case is amplitude = Cos ((d-d₀)n+1 )/2, where d₀ is the position of the centre of the cell, and d is the distance from the centre of the cell. Any other suitable distribution can be used in other embodiments, for example a Gaussian distribution.

If a cell contains more than one laser point then the amplitude of the distribution for that cell is scaled accordingly. For example, Figure 11 illustrates the variation in amplitude with lateral position for the case of a cell containing a single laser point. It can be seen that the distribution has a maximum value of 1 at the centre of the cell (distance = 0). In the case where a cell contained five laser points, the distribution would have a maximum value of 5 at the centre of the cell.

It can be understood that the amplitude for a particular cell will include contributions from neighbouring or more distant cells, and the filtering/weighting module is able to sum the amplitude contributions to obtain a total amplitude for each cell. In the simplified example of Figure 10, originally two laser points were detected and attributed to cells 82, 84. An amplitude distribution is assigned to each laser point as described in the preceding paragraph. The lateral extent of the distribution arising from each cell 82, 84 is indicated in Figure 10 by respective circles 86, 88. By way of example, the amplitude arising from the laser point in cell 84 is 1 .0 in cell 84 itself, 0.5 in cells 90, 92 and zero in cells 94, 96. It can be understood that cells in the shaded region 98 where the two circles 86, 88 overlap will include amplitude contributions from both cells 82, 84.

Figure 12 is a histogram that shows, in another example, the individual amplitude contributions (blue and red columns respectively) from each of two laser points originally attributed to positions 0.0 and 1 .0, as a function of position for lateral positions from -0.6 to +1.4. The histogram also shows the sum of the amplitude contributions (as the yellow column).

The amplitude assigned to a particular cell or lateral position is representative of a laser point count that is used by the fagade calculation module to determine the position of the fagade at stage 60 as described above. In the embodiment of Figure 1 , a further filtering process is performed before the laser point count procedure is performed at stage 60, and before the amplitude contributions for different cells are summed.

The further filtering process comprises applying a non-linear filter to the amplitude distributions assigned to different cells, so as to increase the amplitude distributions assigned to cells that have a larger number of laser points attributed to them in comparison to the amplitude distributions assigned to cells that have a smaller number of laser points attributed to them.

An illustration of the non-linear filter that is applied is provided in Figure 13. The filter applies a weighting, also referred to as an alpha blending factor, to the amplitude distribution attributed to a particular cell in dependence on the number of laser points originally attributed to that cell. In the embodiment of Figure 13, by way of example, a relative weighting of around 0.1 would be applied to the amplitude distribution arising from a cell having 30 laser points attributed to it. In contrast, a weighting of 1.0 would be applied to the amplitude distribution arising from a cell having 100 laser points attributed to it.

In the absence of the non-linear filtering process, the maximum of the amplitude distribution arising from a cell having 100 laser points attributed to it would be 100, and the maximum of the amplitude distribution arising from a cell having 30 points attributed to it would be 30. Following the non-linear filtering process, the maximum of the amplitude distribution arising from a cell having 100 laser points attributed to it would still be 100, but the maximum of the amplitude distribution arising from a cell having 30 points attributed to it would now be around 3. Thus, greater weight is given to those cells that have a larger number of laser points assigned to them. It should be understood that the values of the amplitudes discussed in this paragraph are by way of example only, and that the amplitude values can be normalised to any suitable scale.

In many embodiments, the non-linear filter that is applied is more non-linear in nature than illustrated in Figure 13 and even greater weight is attributed to cells having larger numbers of laser points attributed to them (effectively for such embodiments the slope of the graph of Figure 13 is steeper for higher numbers of laser points and shallower for smaller number of points than is shown in Figure 13).

The effect of the non-linear filtering process is to attribute greater weight to laser points that are likely to have been obtained from building facades and to attribute less weight to laser points that are likely to have been obtained from other objects, as now explained with reference to Figure 14. As illustrated schematically in Figure 14, the number of laser points obtained from different lateral positions will depend on objects that are present at those lateral positions. In Figure 4, the dots 100 indicate the positions from which laser points have been obtained. In this case, laser points have been obtained from a tree 102 and a building 104. The number of laser points for a particular lateral position, or range of lateral positions, will depend on the nature of the object from which the laser points were received. For the range of lateral positions indicated schematically by the lines 106, 108 (and corresponding to one cell of the array) six laser points were received from the tree 102. It can clearly be seen a much greater number of laser points would be obtained from the building 104 for the same-sized range of lateral positions (corresponding to another cell of the array) than for the tree, other object or source of noise due for example, to the greater vertical extent of the building 104 and the often substantially planar nature of a building fagade which can lead to a greater concentration of laser points being successfully detected from a building fagade than from other, irregular objects such as trees. By applying the nonlinear filter process greater weight can be given to laser points that are likely to have been obtained from buildings than to laser points that are likely to have been obtained from other objects or that may represent noise.

After the non-linear filtering process has been applied, the amplitude for each cell is calculated from the sum of all of the weighted amplitude distributions. The resulting amplitude value for each cell is taken to be the laser point count for that cell at stage 58 of the process as described above.

It will be understood that in alternative embodiments other filtering or weighting processes are used instead of the processes described in relation to Figures 10 to 14, or indeed that no such filtering or weighting process is used. Nevertheless, a non-linear filtering process has been found to be particularly useful in practice for removing or reducing the effects of objects other than the fagade of interest and the effects of noise. Similarly the use of a radial gradient approach in which an amplitude distribution is assigned to each laser point effectively to broaden each laser point has been found to be particularly effective in fagade detection, particularly when a limited number of laser point measurements are obtained for each position of the mapping vehicle.

The method described in relation to the embodiment of Figure 3 is able to provide a rapid, accurate automatic determination of the position and other properties of building or other facades in many practical circumstances. The method has been described in relation to the determination of a fagade on one side of the road for a single road segment. However, it will be understood that facades will usually be detected for both sides of a road and over an entire road network or for large portions of a road network.

The results of the fagade detection process can subsequently be used in other processes, and can be combined with other measurements. For example, the results can be used in a subsequent process for the rendering of an image of the fagade using image data or other measurements that may also have been obtained by the mapping vehicle. Such a rendering process can be based on the location of the fagade and/or the line of maximum height of the fagade determined using the method.

The embodiment of Figure 1 determines the position of the fagade from analysis of received laser signals. Laser signals are particularly useful given the large range and low dispersion of laser signals, which enables accurate position determination of a fagade even over long distances. However, in other embodiments further measurement signals of any suitable type may be used. For example, maser or other microwave signals may be used, or other visible light or infrared signals may be used.

In a further embodiment, the received measurement signals comprise light that is used to form an image of a scene. Two images from different perspectives are obtained and photogrammetric techniques are used to determine the locations of different points on the fagade and other objects or points of the scene from which the light was obtained. Then, as for other embodiments, for each of a plurality of lateral positions a reception count representative of the number of received measurement signals received from that lateral position is determined, the lateral position that has the maximum reception count is selected, and the position of part of the fagade is determined from the selected lateral position.

It will also be appreciated that whilst various aspects and embodiments of the present invention have heretofore been described, the scope of the present invention is not limited to the particular arrangements set out herein and instead extends to encompass all arrangements, and modifications and alterations thereto, which fall within the scope of the appended claims.

Whilst embodiments described in the foregoing detailed description refer to GPS, it should be noted that any kind of position sensing technology can be used as an alternative to (or indeed in addition to) GPS. For example the navigation device may utilise using other global navigation satellite systems such as the European Galileo system. Equally, it is not limited to satellite based but could readily function using ground based beacons or any other kind of system that enables the device to determine its geographic location, such as location determination systems based on image recognition, laser based systems and/or user input.

Alternative embodiments of the invention can be implemented as a computer program product for use with a computer system, the computer program product being, for example, a series of computer instructions stored on a tangible data recording medium, such as a diskette, CD-ROM, ROM, or fixed disk, or embodied in a computer data signal, the signal being transmitted over a tangible medium or a wireless medium, for example, microwave or infrared. The series of computer instructions can constitute all or part of the functionality described above, and can also be stored in any memory device, volatile or nonvolatile, such as semiconductor, magnetic, optical or other memory device.

It will also be well understood by persons of ordinary skill in the art that whilst the described embodiments implement certain functionality by means of software, that functionality could equally be implemented solely in hardware (for example by means of one or more ASICs (application specific integrated circuit)) or indeed by a mix of hardware and software. As such, the scope of the present invention should not be interpreted as being limited only to being implemented in software.

Lastly, it should also be noted that whilst the accompanying claims set out particular combinations of features described herein, the scope of the present invention is not limited to the particular combinations hereafter claimed, but instead extends to encompass any combination of features or embodiments herein disclosed irrespective of whether or not that particular combination has been specifically enumerated in the accompanying claims at this time.

Claims

1 . A method of determining the position of a fagade, the method comprising:- acquiring measurement data representative of received measurement signals, each received measurement signal obtained from a respective, different part of a scene;

determining for each of the received measurement signals the lateral position from which that measurement signal was obtained;

determining for each of a plurality of lateral positions a reception count representative of the number of received measurement signals obtained from that lateral position;

selecting the lateral position that has the maximum reception count; and

determining the position of part of the fagade from the selected lateral position.

2. A method according to Claim 1 , wherein each received measurement signal comprises a reflection of a transmitted measurement signal transmitted at a respective, different angle of a plurality of angles.

3. A method according to any preceding claim, wherein the method comprises determining for each of the received measurement signals a vertical position from which that measurement signal was obtained.

4. A method according to any preceding claim, comprising determining the lateral position for each of a plurality of different positions of the mapping vehicle, thereby determining the respective position of each of a plurality of parts of the fagade.

5. A method according to Claim 4, comprising joining the determined positions of the plurality of parts of the fagade thereby to produce a line of the facade

6. A method according to Claim 4 or 5, further comprising for each of the determined lateral positions, determining the greatest vertical position for the received measurement signals for that lateral position.

7. A method according to Claim 6, comprising joining the positions of the received measurement signals having the greatest vertical positions for the determined lateral positions, thereby to produce a substantially continuous roof line of the facade

8. A method according to any preceding claim, comprising determining the vertical positions with respect to a reference position, for example a position of a road surface, and optionally a respective reference position is determined for each of the positions of the mapping vehicle.

9. A method according to Claim 8, comprising discarding received measurement signals having a determined vertical position lower than a threshold height above the reference position, and optionally the threshold height is between 3m and 4m.

10. A method according to any preceding claim, comprising determining received measurement signals that are received from non-building objects and applying a filter to discard or reduce the significance of such measurement signals received from non-building objects.

11. A method according to any preceding claim, comprising for each received measurement signal, assigning an amplitude distribution that comprises a variation of amplitude with lateral position, and optionally summing the resulting amplitudes obtained for each of the lateral positions, wherein the reception count for each lateral position comprises the summed intensities for that position.

12. A method according to Claim 11 , comprising defining an array comprising a plurality of cells, each cell having a respective lateral position, wherein the assigning of the amplitude distributions comprises assigning an amplitude distribution to each cell, and optionally the amplitude distribution assigned to each cell is the sum of the amplitude distributions assigned to measurement signals having lateral positions within that cell.

13. A method according to Claim 12, wherein the determination of reception count for each lateral position comprises determining a reception count for each cell.

14. A method according to Claim 12 or 13, further comprising applying a non-linear filter or weighting to the amplitude distribution at each cell, the non-linear filter or weighting being such as to increase the amplitude of the summed amplitude distribution for cells having a larger number of received measurement signals relative to the summed amplitude distribution having a smaller number of received signals.

15. A method according to Claim 14, wherein the applying of the non-linear filter or weighting comprises applying an alpha blending factor.

16. A method according to any of Claims 12 to 15, wherein the cells of the array have lateral positions in two dimensions, and the array represents received measurement signals obtained for a plurality of positions of the mapping vehicle.

17. A method according to any preceding claim, wherein the measurement signals comprise laser signals.

18. A method according to any preceding claim, wherein the method comprises selecting the received measurement signals that have the selected lateral position, identifying those received measurement signals as being measurement signals received from the building fagade, and optionally mapping the fagade using the positions of the fagade-received measurement signals.

19. A position determining system for determining the position of a fagade comprising:- means for acquiring measurement data representative of received measurement signals, each received measurement signal obtained from a respective, different point of a scene;

means for determining for each of the received measurement signals the lateral position from which that measurement signal was obtained;

means for determining for each of a plurality of lateral positions a reception count representative of the number of received measurement signals obtained from that lateral position;

means for selecting the lateral position that has the maximum reception count; and means for determining the position of part of the fagade from the selected lateral position.

20. A computer program product comprising computer-readable instructions that are executable to perform a method according to any of Claims 1 to 18.