WO2020074326A1

WO2020074326A1 - Method, apparatus and computer program for generating map data

Info

Publication number: WO2020074326A1
Application number: PCT/EP2019/076604
Authority: WO
Inventors: Swapnil Dipak UDAR; Ravi Kantilal PANCHANI
Original assignee: Tomtom Global Content B.V.
Priority date: 2018-10-09
Filing date: 2019-10-01
Publication date: 2020-04-16

Abstract

Certain examples of the present disclosure relate to a method, apparatus and computer program for generating map data (701, 801, 901, 1001, 1101, 1301). Various examples comprise causing, at least in part, actions that result in: receiving a first map data element (g₁) and a second map data element (g₂), each map data element defining a shape and a location of a map object; expanding the shape of at least the first map data element; in response to determining that the expanded shape (g₁') of at least the first map data element overlaps with the shape (g₂') of the second map data element, merging the first and second overlapping shapes to form a unified shape (u₁'); and generating map data using the unified shape.

Description

METHOD, APPARATUS AND COMPUTER PROGRAM FOR GENERATING MAP

DATA

TECHNOLOGICAL FIELD

Examples of the present disclosure relate to a method, apparatus and computer program for generating map data. Some examples, though without prejudice to the foregoing, relate to a method, apparatus and computer program for generating map data indicative of areas/regions, such as Built-Up Areas (BUA’s) .

BACKGROUND

Conventional methods for generating map data, such as electronic map data indicating a zone, an area or a region feature (such as a Built-up Area, “BUA”, which groups concentration of buildings and provides an indication of an urbanised area and/or an area corresponding to a named settlement/region) are not always optimal.

Currently, methods of generating/capturing map data relating to regions, such as BUA map data, are performed by using satellite imagery as a source reference and then carrying out a time consuming and manual labour intensive process of identifying BUA regions therefrom.

It is useful to provide a method, apparatus and computer program to improve the generation of map data.

The listing or discussion of any prior-published document or any background in this specification should not necessarily be taken as an acknowledgement that the document or background is part of the state of the art or is common general knowledge. One or more aspects/examples of the present disclosure may or may not address one or more of the background issues.

BRIEF SUMMARY According†o one or more examples of the disclosure there is provided a method for generating map data, the method comprising causing, at least in part, actions that result in:

receiving a first map data element and a second map data element, each map data element defining a shape and a location of a map object; expanding the shape of at least the first map data element;

in response to determining that the expanded shape of at least the first map data element overlaps with the shape of the second map data element, merging the first and second overlapping shapes to form a unified shape; and

generating map data using the unified shape.

According to one or more examples of the disclosure there is provided an apparatus comprising means for performing the above method.

According to one or more examples of the disclosure there is provided a computer program that, when executed by at least one processor, performs the above method.

According to one or more examples of the disclosure there are provided examples as claimed in the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

For a better understanding of various examples of the present disclosure that are useful for understanding the detailed description and certain embodiments of the invention, reference will now be made by way of example only to the accompanying drawings in which:

Figure 1 illustrates a method according to the present disclosure;

Figures 2A and 2B illustrate a further method according to the present disclosure;

Figure 3 schematically illustrates an apparatus according to the present disclosure; Figure 4 illustrates a satellite image overlaid with map data elements; Figure 5 illustrates the map data elements of Figure 4;

Figure 6 illustrates an enlargement of the shapes of the map data elements of Figure 5;

Figure 7 illustrates a coalescing of the shapes of the map data elements of Figure 6;

Figure 8 illustrates a shrinking of the shapes of the map data elements of Figure 7;

Figure 9 illustrates a removal of holes from the shapes of the map data elements of Figure 8;

Figure 10 illustrates a grouping of the map data elements of Figure 9; Figure 1 1 illustrates sub-groups of the map data elements of Figure 10 following further: enlargement, coalescence, shrinking and removal of holes of a sub-group of the map data elements of Figure 10;

Figure 12 illustrates the sub-groups of the map data elements of Figure 1 1 along with an overlay of the original map data elements of Figure 5; Figure 13 illustrates a simplification of the shapes of the map data elements of Figure 12;

Figure 14 is a schematic illustration of an exemplary part of a Global Positioning System (GPS) usable by a navigation device;

Figure 15 is a schematic diagram of a communications system for communication between a navigation device and a server;

Figure 1 6 is a schematic illustration of electronic components of the navigation device of Figure 15 or any other suitable navigation device; and

Figure 1 7 is a schematic diagram of an arrangement of mounting and/or docking a navigation device.

The Figures are no† necessarily to scale. Certain features and views of the figures may be shown schematically or exaggerated in scale in the interest of clarity and conciseness. For example, the dimensions of some elements in the figures may be exaggerated relative †o other elements†o aid explication. Similar reference numerals are used in the Figures†o designate similar features where appropriate. For clarity, all reference numerals are no† necessarily displayed in all figures.

DETAILED DESCRIPTION

The Figures schematically illustrate method for generating map data (701 , 801 , 901 , 1001 , 1 101 , 1301 ), the method comprising causing, a† leas† in part, actions that result in:

receiving a firs† map data element (gi ) and a second map data element (g2), each map data element defining a shape and a location of a map object;

expanding the shape of a† leas† the firs† map data element;

in response†o determining that the expanded shape (gh) of a† leas† the firs† map data element overlaps with the shape (g2 ) of the second map data element, merging the firs† and second overlapping shapes to form a unified shape (ui’ ) ; and

generating map data using the unified shape.

Advantageously, various examples of the disclosure may provide an improved method of automatically generating map data, e.g. indicative of a region/area (no† leas† for example a BUA), by consolidating/coalescing firs† and second separate/discrete map data elements, each defining a shape and associated location of a map object, into a single unified shape which is used †o generate map data. Examples may enable a reduction in the number of, and complexity of, map data elements representative of a region, thereby providing a simplification of map data representing a region.

For the purposes of illustration and no† limitation, in some examples of the present disclosure, an improved method of generating BUA map data may be provided. The map data elements may relate†o a shape and location of a map object that is indicative of the presence of one or more buildings, the spatial concentration of which may be indicative of a BUA. Such map data elements may comprise: a 2D shape (e.g. area) and location of a map object, e.g. a building footprint and/or a car park;

a I D shape (e.g. line segment) and location of a map object, e.g. a† leas† a portion of a navigable element such as a road segment; and a 0D shape (e.g. point) and location of a map object, e.g. an address, address point location, an address point hookline, and a postal point.

Rather than storing, processing and rending a plurality of such individual, separate and discrete map data elements†o represent a BUA, examples of the present disclosure provide a method of merging such map data elements, i.e. coalescing/unifying their shapes and associated locations into a unified whole. Advantageously, this may reduce the number of individual map data elements, i.e. such that there are fewer separate, disparate and individual shapes and associated locations representing the BUA. For example, instead of having two or more proximal map data elements (related †o a map object suggestive of the presence of buildings/urbanisation) each defining its own shape and location (such that there are two or more shapes and two or more locations), the shapes may be expanded and then, if the shapes are overlapping, the shapes are merged so as†o provide a single unified shape associated with a single location for use in providing/generating BUA map data. Examples may thus consolidate/coalesce map data elements of a firs† set†o generate a second set of map data elements comprising fewer map data elements than the firs† set, thereby comprising fewer shapes and fewer associated locations.

Such a consolidation/coalescence of plural map data elements†o fewer or a single coherent unified whole map data element representative of a BUA may reduce storage and processing requirements for BUA map data. Moreover the rendering of such simplified BUA map data may be significantly less computationally intensive (such as when rendering zooming in/ou† of a displayed BUA region) as compared †o the rendering of a plurality of source/raw map data elements indicative of a BUA each having its own shape and associated location. The method may be implemented by one or more computers and may be automated so as to avoid/reduce user input and user effort as compared†o previous manual processes of generating BUA map data, and may also increase accuracy and precision of the generated map data.

Furthermore, examples may enable differing types of input map data elements may be utilised (e.g. differing dimensionality of the shapes of the map data elements, such as input: areas, lines and points). Examples may thus enable utilisation of a wider range of, and differing sources of, reference data for the input map data elements as compared†o prior techniques. For instance, examples of the present disclosure are no† limited †o using 2D area/region input map data elements and/or satellite imagery as source reference data, but may additionally make use of alternate data sets and differing sources of data that may be suggestive buildings, such as 0D point like map data elements e.g. postal addresses, address points, and postal points. The ability†o make use of varied sources of reference data may assist in the confidence in the resultant generated BUA map data. Moreover, since such alternate data sources may be more readily available and more frequently updated (c.f. the frequency of availability of updates†o satellite imagery), more current and up-to-date BUA map data may be generated.

Although examples of the present disclosure are discussed with regards†o generating BUA map data, it is†o be appreciate that other types of map data indicative of other types of areas/regions may be generated in accordance with other examples of the present disclosure. For example, in other examples, the generated map data may be representative of a region indicative of land mass of an archipelago of islands (i.e. the input map data elements may be a shape and location of each island/isle†/ou†crop of the archipelago). Figure 1 schematically illustrates a flow chart of a method 100 according to an example of the present disclosure. Figures 5†o 8 also help illustrate certain of the blocks of the method.

In block 101 , a firs† map data element and a second map data element are received (examples of such firs† and second map data elements, gi and g are illustrated in Figure 5). The map data elements each define a shape of a map object and an associated location of the same.

In examples where map data indicative of a BUA is†o be generated, the map object may be an object of an electronic map that may be indicative of a building and/or an urbanised area. For example, a map object may be, for example:

a building footprint (BFP) (an area feature representing a part or an entire footprint of a building),

a car park (an area feature representing a part or an entire footprint of a car park),

a portion of a navigable element (a line features representing a part of a navigable element such as a road),

a postal address, address point (APT)

an address point hookline, or

a postal point (an address feature, such as a post code, that provides postal information from an address, a group of addresses or a postal area).

The shape of the map object may be: a vector feature (such as a point, a line and a polygon) or any geometric shape. The location may be an anchor point associated with the shape. In some examples, data representative of the shape and its associated location may be stored as shapefile forma†. Shapefiles are a digital vector storage forma† for storing geometric location and associated attribute information. The shape may be OD, 1 D or 2D (or even 3D, such as a 3D representation of a building). For instance, in certain examples, the received map data elements, defining a shape and associated location, may define:

a 2 dimensional shape (e.g. circle, triangle, quadrilateral, closed loop, area, region, polygon or polyline);

a 1 dimensional shape (e.g. a line, a line segment); or

a 0 dimensional shape (e.g. a point)

each associated with a location.

In block 102, the shape of at least the first map data element is expanded. In certain examples, the shape of the second map data element may also be expanded (an example of expanded first and second map data elements, gi‘ and g₂‘ is illustrated in Figure 6). Any appropriate algorithm may be applied to effect such an expansion of the shapes.

Expanding the shape of a map data element may comprise increasing one or more dimensions of the shape and/or increasing the dimensionality of the shape.

For example, where shape is a 2D shape (such as a 2D geometric shape, closed loop, polygon or area) expanding the shape may comprise increasing one or more of: a widthwise dimension, a lengthwise dimension, and a size/area of the shape by a first scaling factor.

Where the shape is a 1 D shape, such as a line/line segment; expanding the shape may comprise increasing the length of the line. Alternatively, or in addition, expanding the shape may comprise increasing the dimensionality of the I D shape, e.g. adding a width dimension; thereby converting the I D shape/line to a 2D shape/area.

Similarly, where the shape is a 0D point, expanding the shape may comprise increasing the dimensionality of 0D shape, e.g. adding a width and/or length dimension, thereby converting 0D point to a I D shape/line or a 2D shape/area (for example expanding a point like do† †o a circle of a predetermined radius).

Following the expansion of the shape of the firs† map data element, a determination is made as†o whether the expanded shape overlaps with the shape of the second map data element. Responsive to a determination of such an overlap, the first and second overlapping shapes are merged in block 103 to form a unified shape. Such a merging of the two shapes amalgamates/coalesces/consolidate the two shapes to form single unitary whole shape (an example of a merged/unionised shape u i ¹ of the expanded first and second map data elements, gi‘ and g₂‘ is illustrated in Figure 7). Any appropriate algorithm may be applied to effect such a merging/union of the shapes.

Likewise, the previous locations associated with the former shapes may likewise be consolidated and associated with the unionised shape ui‘. For example, an anchor point location for the unionised shape ui‘ may be defined as a newly generated location, such as a midway point location between the two previous locations of the two former shapes. Alternatively, an anchor point location for the unionised shape u i ¹ may be simply be defined as one or the other of the previous locations of the former shapes.

In optional block 104, the merged/unitary shape is reduced in size (an example of a reduced sized shape ui of the merged/unionised shape uL is illustrated in Figure 8). Any appropriate algorithm may be applied to effect such a size reduction/shrinking, preferably whilst maintaining fidelity to the shape of the unitary shape.

In block 105, the consolidated/merged/unitary shape (e.g. uL of Figure 6), or the reduced size merged/unitary shape ui, is used to generate map data.

In some examples the map data may be the consolidated map data element itself, i.e. the merged/unitary shape u (or the reduced size merged/ unitary shape ui) and it associated location. In some examples, the merged/ unitary shape undergoes further processing, as discussed below with respect to Figures 2A and 2B, prior†o generating map data.

Figures 2A and 2B schematically illustrate a flow char† of a further method 200 according†o an example of the present disclosure. Figures 5 to 1 1 and 13 also help illustrate certain of the blocks of the method.

In block 201 (and with reference to Figure 5), a first set 501 , G of a first plurality of map data elements g: is received.

In block 202 (and with reference to Figure 6), the shapes of the map data elements g: are expanded to form a set 601 , G’ of map data elements having expanded shapes gi’.

In block 203 (and with reference to Figure 7), any expanded map data elements g/ that are overlapping with one another are merged together†o form a set 701 , U’ of merged/unionised map data elements Ui’ . Since various map data elements are merged, the unionised set U’ comprises fewer map data elements than the initial set G’ (and hence comprises fewer shapes and few associated locations and hence such a unionised set U’ of map data elements requires less storage space moreover the processing and rendering of such simplified data is also facilitated).

In block 204, (and with reference to Figure 8), the size of the unified map data elements u/ of the set U’ are reduced to form a set 801 , U of one or more reduced sized unified map data elements Ui.

In block 205 (and with reference to Figure 9), the one or more reduced sized unified map data elements Ui of the set U are modified so as to remove any holes in the shapes to form a set 901 , V of unified map data elements Vi devoid of holes. By way of example, the removal (or“filling in”) of any holes in the shape of a map data element may comprise: determining whether a shape of the map data element u: comprises a multi-polygon, i.e. a polygon with one or more infernal polygons (defining“holes”), wherein the outermost polygon defines the actual extremity of the overarching shape and the internal polygons define holes or void regions. Removing such “holes” comprises removing such internal polygons from the map data element’s shape, i.e. deleting any such internal polygons from the shape file of the (“holey”) map data element u: to generate a (“hole-less”) map data element Vi.

Following block 205, (and with reference to Figure 10), the set 901 , V of (“hole less”) map data elements Vi, is subdivided into two groups 1001 , Vi and 1002, V2. The first group/subset Vi comprises larger map data elements vn (e.g. of a size above a threshold size) and the second group/subset V2 comprises smaller map data elements va (e.g. of a size below a threshold size). In more detail, in block 206, map data elements Vi having a size greater than a pre determined threshold size are identified to define a first subset Vi of the set V having larger sized map data elements vii. In block 207, map data elements Vi having a size less than a pre-determined threshold size are identified to define a second subset V2 of the set V having smaller sized map data elements V2i.

In block 208, (and with reference to Figure 1 1 ), the set 1002, V2 of smaller sized map data elements V21 effectively undergoes a further round of processing similar to that of blocks 202, 203, 204 and 205. In more detail, in block 208, the shapes of the map data elements va of the second set V2 are expanded to form an expanded set of map data elements W (not shown). The scaling factor used in expanding the shape of the map data elements in block 208 may be a different scaling factor to that used in the expansion of block 202. For examples, the second scaling factor used in block 208 may be larger than the first scaling factor used in block 202. In block 209, any overlapping expanded shapes of the map data elements of the set are merged†o form a set W₂’ (no† shown). In block 210, the size of each of the merged shapes in set W₂ ^’are reduced†o form set W₂ (no† shown). In block 21 1 , any holes in the reduced sized merged map data elements of set W₂ are removed†o form a set X₂ of map data elements x_2i (illustrated in Figure 1 1 ).

If required, the resultant set X₂ may itself be subdivided info groups of larger and smaller sized map data elements and undergo a further round of processing similar†o that of blocks 208 - 21 1 , i.e. expansion (e.g. by a third scaling factor greater than the second scaling factor), merging, shrinking and hole removal of the smaller sized map data elements.

In block 212, a filtering step may be performed †o remove map data elements having a size less than a predetermined threshold size/area (no† shown). If is†o be appreciated that this step could be formed after block 213.

In block 213, the initial subset Vi (of larger map data elements) is combined with the subset X₂ (derived from the initial subset V₂ of smaller map data elements) to generate a new set of map data elements.

In block 214, map data is generated from the sets of map data elements Vi and X₂. In some examples, the generated map data may comprise the consolidation of the map data elements into a single shapefile. In some examples, the consolidated map data elements may undergo yet further processing prior to the generation of map data, e.g. as discussed below with respect to Figure 13.

The flowchart of Figures 2A and 2B represents one possible scenario among others. The order of the blocks shown is not absolutely required, so in principle, the various blocks can be performed out of order. Not all the blocks are essential. In certain examples one or more blocks may be performed in a different order or overlapping in time, in series or in parallel. One or more blocks may be omitted or added or changed in some combination of ways.

The methods discussed above and the blocks of Figures 1 , 2A and 2B are functional and the functions described may or may not be performed by a single physical entity, such as is described with reference to Figure 3, so as to provide a computer implemented method.

Examples of the present disclosure may take the form of a computer implemented method, an apparatus or a computer program. Accordingly, examples may be implemented in hardware, software or a combination of hardware and software.

Examples of the present disclosure are described using flowchart illustrations and schematic block diagrams. It will be understood that each block (of the flowchart illustrations and block diagrams), and combinations of blocks, can be implemented by computer program instructions of a computer program. These program instructions may be provided to one or more processor(s), processing circuitry or controller(s) such that the instructions which execute on the same create means for causing implementing the functions specified in the block or blocks, i.e. such that the method may be computer implemented. The computer program instructions may be executed by the processor(s) to cause a series of operational steps/actions to be performed by the processor(s) to produce a computer implemented process such that the instructions which execute on the processor(s) provide steps for implementing the functions specified in the block or blocks.

Accordingly, the blocks support: combinations of means for performing the specified functions; combinations of actions for performing the specified functions; and computer program instructions/algorithm for performing the specified functions. It will also be understood that each block, and combinations of blocks, can be implemented by special purpose hardware- based systems which perform the specified functions or actions, or combinations of special purpose hardware and computer program instructions.

Figure 3 schematically illustrates a block diagram of an apparatus 300 comprising means for performing methods according to the present disclosure, no† leas† the methods of Figures 1 and 2A-2b discussed below, as well as the methods illustrated in Figures 5†o 13 and the algorithm discussed below.

The apparatus 300 comprises a controller 301 which, in the illustrated example, is provided by a processor 302 and memory 303.

The memory 303 stores a computer program 304 comprising computer readable program code/instructions 305 that, when executed by the processor 302, controls the apparatus 300†o perform the methods according †o the present disclosure. The controller 301 is configured†o receive: input map data elements 308 and is configured†o provide output generated map data 309 (e.g. for storage, transmission or rendering on a local or remote device). The processor 302 may comprise an input interface 306 via which data (no† leas† such as the input map data elements) and/or commands are input†o the processor 302, and an output interface 307 via which data (such as the generated map data) and/or commands are output by the processor 302.

The computer program may be stored on a non-†ransi†ory computer- readable storage medium.

The apparatus may be one or more of: a wireless communications device, a hand-portable electronic device, and a portable navigation device. The apparatus may be embodied by a computing device, no† leas† such as those mentioned above. The apparatus 300 may, for example, be a server device (such as server 2150 of Figure 15) or a client device (such as navigation device 2200 of Figure 15). In some examples, the apparatus may be embodied as a chip, chip set or module, i.e. for use in any of the foregoing. As used here ‘module’ refers†o a unit or apparatus that excludes certain parfs/componenfs that would be added by an end manufacturer or a user.

Reference will now be made†o a specific implementation of methods of the present disclosure†o generate map date indicative of BUA. Whilst a specific example implementation and algorithm is descripted, it is to be appreciated that the teaching and scope of the present disclosure is not limited merely to this specific implementation.

Figure 4 illustrates a satellite image 401 , overlaid with a set 501 , G of a plurality of map data elements g: (G and g: are more clearly separately illustrated in Figure 5). Each map data element g: represents a geometry (i.e. a shape, size and location) of a building footprint. Such geometries of building foot prints may be derived from the satellite image 401 via appropriate image processing/object recognition.

Each of the plurality of map data elements/geometries of building foot prints g: is defined by a shapefile“S”. The plurality of separate, independent and discrete shapefiles S may be merged into a single shape file“s”. The first step of an algorithm for generating map data is:

1 . Merge all shapefiles: (s <— merge(S))

All the geometries of the single shape file s are read into G, which comprises a set of the plurality map data elements/geometries g:. The second step of the algorithm is:

2. Read all geometries: (G <— read_geome†ries(s))

For all geometries in G, every geometry is “buffered”, i.e. expanded/enlarged, by a parameter X (which is illustrated in figure 6 to create set G’). The third step of the algorithm is:

3. Expand geometries: (vg e {G}. g <— buffer (g, X)) A cascaded union of G is taken (which is illustrated in Figure 7 to create set IT) such that overlapping geometries are considered as a single geometry. The fourth step of the algorithm is:

4. Consolidate geometries (G <— union (G))

The union is then shrunk back to its original size by same parameter value X, i.e. buffered by -X (which is illustrated in Figure 8 to set create U). The fifth step of the algorithm is:

5. Shrink Geometries (vg e {G}. g <— buffer (g, -X))

After shrinking the union to original size any small holes/donuts formed in previous step are removed (which is illustrated in Figure 9 to create set V). The sixth step of the algorithm is:

6. Remove Floles if any (vg e {G}. g <— remove_donu†s (g))

The resultant geometries are then filtered to separate smaller geometries into separate Gsmaiier and larger geometries into Giarger, so that Gsmaiier is set of smaller geometries, e.g. having a size less than a predetermined size parameter value Y, and Giarger contains bigger geometries, e.g. having a size greater than a predetermined size parameter value Y, (which is illustrated in Figure 10 to create sets Vi and V2). The seventh step of the algorithm is:

7. Separate out smaller geometries (Gsmaiier, Giarger ·*— fil†er_by_area(G, Y)

For the separated smaller geometries Gsmaiier, the steps 3 through 6 (expand -> unite -> shrink -> remove holes) are repeated. Flowever, this time, the (smaller) geometries are expanded by double the value than that used for the first expansion, i.e. they are expanded by 2X (this is illustrated in Figure 1 1 with the creation of Vi and X2). The eighth step of the algorithm is:

8. Repeat for smaller geometries (Gsmaiier <— (REPEAT steps from 3 to 6 Where G <— Gsmaiier, X=2*X, Y=Y) )

Figure 12 illustrate a combination of:

the Giarger geometries - set V comprising vn. the Gsmaiier geometries (after a further expansion, uniting, shrinking and hole removal) - set X comprising X2i,

along with an overlap of the original BFP geometries (of Figure 5) - set G comprising gi

to show how the Giarger and Gsmaiier geometries provide an representation of a BUA.

Following the process of algorithm step 8, and its additional processing of the smaller geometries, the processed Gsmaiier is unioned with the Giarger. This union is then filtered by a threshold parameter value Y†o remove any still remaining smaller areas below a threshold size. The ninth step of the algorithm is:

9. Unite smaller and larger into one (G <— Gsmaiier U Giarger) and

Gsmaiier, Giarger ^ fil†er_by_orea (G, Y)

In order to obtain a simpler boundary for the BUA, the boundaries (i.e. polyline defining the shape of the BUA) of the result of step 9 are simplified and the output is written into a shape file (as illustrated in Figure 13). The tenth step of the algorithm is:

10. Simplify boundary G <— smoofhjooundaries (Giarger)

and

rite output into a final output shapefile s <— wri†e_geome†ries (G) representing the BUA

Examples of the present disclosure include an apparatus comprising various modules, means or circuitry that provide the functionality for performing the above methods and algorithm steps. The modules, means or circuitry may be implemented as hardware, or may be implemented as software or firmware †o be performed by a computer processor. In the case of firmware or software, examples of the present disclosure can be provided as a computer program product including a computer readable storage structure embodying computer program instructions (i.e. the software or firmware) thereon for performing by the computer processor. Figures 14 - 17 illustrate a Global Positioning System (GPS) as well as a communication system (including a server and navigation device) for use with the same. Examples of the present disclosure may generate map data that can be used by such a server and navigation device.

Figure 14 illustrates a GPS. The GPS of Figure 14 and the like are used for a variety of purposes. In general, the GPS is a safellife-radio based navigation system capable of determining continuous position, velocity, time, and in some instances direction information for an unlimited number of users. Formerly known as NAVSTAR, the GPS incorporates a plurality of satellites which orbit the earth in extremely precise orbits. Based on these precise orbits, GPS satellites can relay their location, as GPS data,†o any number of receiving units. Plowever, it will be understood that Global Positioning systems could be used, such as GLOSNASS, the European Galileo positioning system, COMPASS positioning system or IRNSS (Indian Regional Navigational Satellite System).

The GPS system is implemented when a device, specially equipped †o receive GPS data, begins scanning radio frequencies for GPS satellite signals. Upon receiving a radio signal from a GPS satellite, the device determines the precise location of that satellite via one of a plurality of different conventional methods. The device will continue scanning, in most instances, for signals until if has acquired a† leas† three different satellite signals (noting that position is no† normally, but can be determined, with only two signals using other triangulation techniques). Implementing geometric triangulation, the receiver utilizes the three known positions †o determine its own two-dimensional position relative †o the satellites. This can be done in a known manner. Additionally, acquiring a fourth satellite signal allows the receiving device†o calculate its three dimensional position by the same geometrical calculation in a known manner. The position and velocity data can be updated in real time on a continuous basis by an unlimited number of users. As shown in Figure 14, the GPS system 2100 comprises a plurality of satellites 2102 orbiting about the earth 2104. A GPS receiver 2106 receives GPS data as spread spectrum GPS satellite data signals 2108 from a number of the plurality of satellites 2102. The spread spectrum data signals 2108 are continuously transmitted from each satellite 2102, the spread spectrum data signals 2108 transmitted each comprise a data stream including information identifying a particular satellite 2102 from which the data stream originates. The GPS receiver 2106 generally requires spread spectrum data signals 2108 from at least three satellites 2102 in order†o be able to calculate a two-dimensional position. Receipt of a fourth spread spectrum data signal enables the GPS receiver 2106 to calculate, using a known technique, a three-dimensional position.

Turning†o Figure 15, a navigation device 2200 (i.e. a Portable Navigation Device - PND) comprising or coupled to the GPS receiver device 2106, is capable of establishing a data session, if required, with network hardware of a“mobile” or telecommunications network via a mobile device (not shown), for example a mobile telephone, PDA, and/or any device with mobile telephone technology, in order†o establish a digital connection, for example a digital connection via known Bluetooth technology. Thereafter, through its network service provider, the mobile device can establish a network connection (through the Internet for example) with a server 2150. As such, a “mobile” network connection can be established between the navigation device 2200 (which can be, and often times is, mobile as it travels alone and/or in a vehicle) and the server 2150 to provide a“real-time” or at least very“up to date” gateway for information.

The establishing of the network connection between the mobile device (via a service provider) and another device such as the server 2150, using the Internet for example, can be done in a known manner. In this respect, any number of appropriate data communications protocols can be employed, for example the TCP/IP layered protocol. Furthermore, the mobile device can utilize any number of communication standards such as CDMA2000, GSM, IEEE 802.1 1 a/b/c/g/n, etc.

Hence, if can be seen that the Interne† connection may be utilised, which can be achieved via data connection, via a mobile phone or mobile phone technology within the navigation device 2200 for example.

Although no† shown, the navigation device 2200 may, of course, include its own mobile telephone technology within the navigation device 2200 itself (including an antenna for example, or optionally using the internal antenna of the navigation device 2200). The mobile phone technology within the navigation device 2200 can include internal components, and/or can include an insertable card (e.g. Subscriber Identity Module (SIM) card), complete with necessary mobile phone technology and/or an antenna for example. As such, mobile phone technology within the navigation device 2200 can similarly establish a network connection between the navigation device 2200 and the server 2150, via the Interne† for example, in a manner similar to that of any mobile device.

For telephone settings, a Bluetooth enabled navigation device may be used to work correctly with the ever changing spectrum of mobile phone models, manufacturers, etc., model/manufacturer specific settings may be stored on the navigation device 2200 for example. The data stored for this information can be updated.

In Figure 15, the navigation device 2200 is depicted as being in communication with the server 2150 via a generic communications channel 2152 that can be implemented by any of a number of different arrangements. The communication channel 2152 generically represents the propagating medium or path that connects the navigation device 2200 and the server 2150. The server 2150 and the navigation device 2200 can communicate when a connection via the communications channel 2152 is established between the server 2150 and the navigation device 2200 (noting that such a connection can be a data connection via mobile device, a direct connection via personal computer via the Internet, etc.).

The communication channel 2152 is not limited to a particular communication technology. Additionally, the communication channel 2152 is not limited to a single communication technology; that is, the channel 2152 may include several communication links that use a variety of technology. For example, the communication channel 2152 can be adapted†o provide a path for electrical, optical, and/or electromagnetic communications, etc. As such, the communication channel 2152 includes, but is no† limited to, one or a combination of the following: electric circuits, electrical conductors such as wires and coaxial cables, fibre optic cables, converters, radio-frequency (RF) waves, the atmosphere, free space, etc. Furthermore, the communication channel 2152 can include intermediate devices such as routers, repeaters, buffers, transmitters, and receivers, for example.

In one illustrative arrangement, the communication channel 2152 includes telephone and computer networks. Furthermore, the communication channel 2152 may be capable of accommodating wireless communication, for example, infrared communications, radio frequency communications, such as microwave frequency communications, etc. Additionally, the communication channel 2152 can accommodate satellite communication.

The communication signals transmitted through the communication channel 2152 include, but are no† limited to, signals as may be required or desired for given communication technology. For example, the signals may be adapted †o be used in cellular communication technology such as Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA), Global System for Mobile Communications (GSM), General Packet Radio Service (GPRS), etc. Both digital and analogue signals can be transmitted through the communication channel 2152. These signals may be modulated, encrypted and/or compressed signals as may be desirable for the communication technology. The server 2150 includes, in addition to other components which may not be illustrated, a processor 2154 operatively connected to a memory 2156 and further operatively connected, via a wired or wireless connection 2158,†o a mass data storage device 2160. The mass storage device 2160 contains a store of navigation data and map information, and can again be a separate device from the server 2150 or can be incorporated into the server 2150. The processor 2154 is further operatively connected †o transmitter 2162 and receiver 2164, to transmit and receive information to and from navigation device 2200 via communications channel 2152. The signals sent and received may include data, communication, and/or other propagated signals. The transmitter 2162 and receiver 2164 may be selected or designed according to the communications requirement and communication technology used in the communication design for the navigation system 2200. Further, it should be noted that the functions of transmitter 2162 and receiver 2164 may be combined into a single transceiver.

As mentioned above, the navigation device 2200 can be arranged †o communicate with the server 2150 through communications channel 2152, using transmitter 2166 and receiver 2168†o send and receive signals and/or data through the communications channel 2152, noting that these devices can further be used†o communicate with devices other than server 2150. Further, the transmitter 2166 and receiver 2168 are selected or designed according to communication requirements and communication technology used in the communication design for the navigation device 2200 and the functions of the transmitter 2166 and receiver 2168 may be combined into a single transceiver as described above in relation to Figure 15. Of course, the navigation device 2200 comprises other hardware and/or functional parts, which will be described later herein in further detail.

Software stored in server memory 2156 provides instructions for the processor 2154 and allows the server 2150†o provide services†o the navigation device 2200. One service provided by the server 2150 involves processing requests from the navigation device 2200 and transmitting navigation data from the mass data storage 2160 to the navigation device 2200. Another service that can be provided by the server 2150 includes processing the navigation data using various algorithms for a desired application and sending the results of these calculations to the navigation device 2200.

The server 2150 constitutes a remote source of data accessible by the navigation device 2200 via a wireless channel. The server 2150 may include a network server located on a local area network (LAN), wide area network (WAN), virtual private network (VPN), etc.

The server 2150 may include a personal computer such as a desktop or laptop computer, and the communication channel 2152 may be a cable connected between the personal computer and the navigation device 2200. Alternatively, a personal computer may be connected between the navigation device 2200 and the server 2150 to establish an Internet connection between the server 2150 and the navigation device 2200.

The navigation device 2200 may be provided with information from the server 2150 via information downloads (not least such a map data generated in accordance with the present disclosure) which may be updated automatically, from time to time, or upon a user connecting the navigation device 2200 to the server 2150 and/or may be more dynamic upon a more constant or frequent connection being made between the server 2150 and navigation device 2200 via a wireless mobile connection device and TCP/IP connection for example. For many dynamic calculations, the processor 2154 in the server 2150 may be used to handle the bulk of processing needs, however, a processor (not shown in Figure 15) of the navigation device 2200 can also handle much processing and calculation, oftentimes independent of a connection to a server 2150.

Referring to Figure 16, it should be noted that the block diagram of the navigation device 2200 is not inclusive of all components of the navigation device, but is only representative of many example components. The navigation device 2200 is located within a housing (not shown). The navigation device 2200 includes processing circuitry comprising, for example, the processor 2202 mentioned above, the processor 2202 being coupled to an input device 2204 and a display device, for example a display screen 2206. Although reference is made here to the input device 2204 in the singular, the skilled person should appreciate that the input device 2204 represents any number of input devices, including a keyboard device, voice input device, touch panel and/or any other known input device utilised to input information. Likewise, the display screen 2206 can include any type of display screen such as a Liquid Crystal Display (LCD), for example.

In one arrangement, one aspect of the input device 2204, the touch panel, and the display screen 2206 are integrated so as to provide an integrated input and display device, including a touchpad or touchscreen input 2250 (Figure 17) †o enable both input of information (via direct input, menu selection, etc.) and display of information through the touch panel screen so that a user need only touch a portion of the display screen 2206 to select one of a plurality of display choices or†o activate one of a plurality of virtual or “soft” buttons. In this respect, the processor 2202 supports a Graphical User Interface (GUI) that operates in conjunction with the touchscreen.

In the navigation device 2200, the processor 2202 is operatively connected to and capable of receiving input information from input device 2204 via a connection 2210, and operatively connected to at least one of the display screen 2206 and the output device 2208, via respective output connections 2212,†o output information thereto. The navigation device 2200 may include an output device 2208, for example an audible output device (e.g. a loudspeaker). As the output device 2208 can produce audible information for a user of the navigation device 2200, it should equally be understood that input device 2204 can include a microphone and software for receiving input voice commands as well. Further, the navigation device 2200 can also include any additional input device2 204 and/or any additional output device, such as audio input/output devices for example.

The processor 2202 is operatively connected†o memory 2214 via connection 2216 and is further adapted†o receive/send information from/to inpuf/oufpuf (I/O) ports 2218 via connection 2220, wherein the I/O port 2218 is connectible †o an I/O device 2222 external†o the navigation device 2200. The external I/O device 2222 may include, but is no† limited†o an external listening device, such as an earpiece for example. The connection to I/O device 2222 can further be a wired or wireless connection to any other external device such as a car stereo unit for hands-free operation and/or for voice activated operation for example, for connection to an earpiece or headphones, and/or for connection to a mobile telephone for example, wherein the mobile telephone connection can be used†o establish a data connection between the navigation device 2200 and the Interne† or any other network for example, and/or to establish a connection to a server via the Interne† or some other network for example.

The memory 2214 of the navigation device 2200 comprises a portion of non volatile memory (for example †o store program code) and a portion of volatile memory (for example †o store data as the program code is executed). The navigation device also comprises a port 2228, which communicates with the processor 2202 via connection 2230, †o allow a removable memory card (commonly referred†o as a card)†o be added†o the device 2200. In the embodiment being described the port is arranged†o allow an SD (Secure Digital) card†o be added. In other embodiments, the port may allow other formats of memory to be connected (such as Compact Flash (CF) cards, Memory Sticks, xD memory cards, USB (Universal Serial Bus) Flash drives, MMC (MultiMedia) cards, SmartMedia cards, Microdrives, or the like).

Figure 16 further illustrates an operative connection between the processor 2202 and an antenna/receiver 2224 via connection 2226, wherein the antenna/receiver 2224 can be a GPS antenna/receiver for example and as such would function as the GPS receiver 2106 of Figure 14. If should be understood that the antenna and receiver designated by reference numeral 2224 are combined schematically for illustration, but that the antenna and receiver may be separately located components, and that the antenna may be a GPS patch antenna or helical antenna for example.

It will, of course, be understood by one of ordinary skill in the art that the electronic components shown in Figure 16 are powered by one or more power sources (not shown) in a conventional manner. Such power sources may include an internal battery and/or a input for a low voltage DC supply or any other suitable arrangement. As will be understood by one of ordinary skill in the art, different configurations of the components shown in Figure 16 are contemplated. For example, the components shown in Figure 16 may be in communication with one another via wired and/or wireless connections and the like. Thus, the navigation device 2200 described herein can be a portable or handheld navigation device 2200.

In addition, the portable or handheld navigation device 2200 of Figure 16 can be connected or “docked” in a known manner to a vehicle such as a bicycle, a motorbike, a car or a boat for example. Such a navigation device 2200 is then removable from the docked location for portable or handheld navigation use. Indeed, in other embodiments, the device 2200 may be arranged to be handheld to allow for navigation of a user.

Referring to Figure 17, the navigation device 2200 may be a unit that includes the integrated input and display device 2206 and the other components of Figure 15 (including, but not limited to, the internal GPS receiver 2224, the processor 2202, a power supply (not shown), memory systems 2214, etc.).

The navigation device 2200 may sit on an arm 2252, which itself may be secured to a vehicle dashboard/window/etc. using a suction cup 2254. This arm 2252 is one example of a docking station to which the navigation device 2200 can be docked. The navigation device 2200 can be docked or otherwise connected to the arm 2252 of the docking station by snap connecting the navigation device 2200†o the arm 2252 for example. The navigation device 2200 may then be rotatable on the arm 2252. To release the connection between the navigation device 2200 and the docking station, a button (no† shown) on the navigation device 2200 may be pressed, for example. Other equally suitable arrangements for coupling and decoupling the navigation device 2200†o a docking station are well known †o persons of ordinary skill in the art.

In the embodiment being described, the processor 2202 of the navigation device is programmed†o receive GPS data received by the antenna 2224 and, from time†o time,†o store that GPS data, together with a time stamp of when the GPS data was received, within the memory 2214 to build up a record of the location of the navigation device. Each data record so-stored may be thought of as a GPS fix; i.e. it is a fix of the location of the navigation device and comprises a latitude, a longitude, a time stamp and an accuracy report.

In one embodiment the data is stored substantially on a periodic basis which is for example every 5 seconds. The skilled person will appreciate that other periods would be possible and that there is a balance between data resolution and memory capacity; i.e. as the resolution of the data is increased by taking more samples, more memory is required†o hold the data. However, in other embodiments, the resolution might be substantially every: 1 second, 10 seconds, 15 seconds, 20 seconds, 30 seconds, 45 seconds, 1 minute, 2.5 minutes (or indeed, any period in between these periods). Thus, within the memory of the device there is built up a record of the whereabouts of the device 2200 a† points in time.

In some embodiments, it may be found that the quality of the captured data reduces as the period increases and whilst the degree of degradation will a† leas† in part be dependent upon the speed a† which the navigation device 2200 was moving a period of roughly 15 seconds may provide a suitable upper limit.

Whilst the navigation device 2200 is generally arranged to build up a record of its whereabouts, some embodiments, do not record data for a predetermined period and/or distance at the start or end of a journey. Such an arrangement helps to protect the privacy of the user of the navigation device 2200 since it is likely to protect the location of his/her home and other frequented destinations. For example, the navigation device 2200 may be arranged not to store data for roughly the first 5 minutes of a journey and/or for roughly the first mile of a journey.

In other embodiments, the GPS may not be stored on a periodic basis but may be stored within the memory when a predetermined event occurs. For example, the processor 2202 may be programmed to store the GPS data when the device passes a road junction, a change of road segment, or other such event.

Further, the processor 2202 is arranged, from time to time, to upload the record of the whereabouts of the device 2200 (i.e. the GPS data and the time stamp) to the server 2150. In some embodiments in which the navigation device 2200 has a permanent, or at least generally present, communication channel 2152 connecting it to the server 2150 the uploading of the data occurs on a periodic basis which may for example be once every 24 hours. The skilled person will appreciate that other periods are possible and may be substantially any of the following periods: 15 minutes, 30 minutes, hourly, every 2 hours, every 5 hours, every 12 hours, every 2 days, weekly, or any time in between these. Indeed, in such embodiments the processor 2202 may be arranged to upload the record of the whereabouts on a substantially real time basis, although this may inevitably mean that data is in fact transmitted from time to time with a relatively short period between the transmissions and as such may be more correctly thought of as being pseudo real time. In such pseudo real time embodiments, the navigation device may be arranged to buffer the GPS fixes within the memory 2214 and/or on a card inserted in the port 2228 and†o transmit these when a predetermined number have been stored. This predetermined number may be on the order of 20, 36, 100, 200 or any number in between. The skilled person will appreciate that the predetermined number is in part governed by the size of the memory 2214 or card within the port 2228.

In other embodiments, which do not have a generally present communication channel 2152 the processor 2202 may be arranged to upload the record to the server 2152 when a communication channel 2152 is created. This may for example, be when the navigation device 2200 is connected to a user’s computer. Again, in such embodiments, the navigation device may be arranged to buffer the GPS fixes within the memory 2214 or on a card inserted in the port 2228. Should the memory 2214 or card inserted in the port 2228 become full of GPS fixes the navigation device may be arranged to delete the oldest GPS fixes and as such it may be thought of as a First in First Out (FIFO) buffer.

In the embodiment being described, the record of the whereabouts comprises one or more traces with each trace representing the movement of that navigation device 2200 within a 24 hour period. Each 24 is arranged to coincide with a calendar day but in other embodiments, this need not be the case.

Generally, a user of a navigation device 2200 gives his/her consent for the record of the devices whereabouts to be uploaded to the server 2150. If no consent is given then no record is uploaded to the server 2150. The navigation device itself, and/or a computer to which the navigation device is connected may be arranged to ask the user for his/her consent to such use of the record of whereabouts.

The server 2150 is arranged to receive the record of the whereabouts of the device and to store this within the mass data storage 2160 for processing. Thus, as time passes the mass data storage 2160 accumulates a plurality of records of the whereabouts of navigation devices 2200 which have uploaded data.

As discussed above, the mass data storage 2160 also contains map data. Such map data provides information about the location of road segments, points of interest and other such information that is generally found on map, including map data generated in accordance with examples of the present disclosure, such map date which may be indicative of regions/zones/areas such as BUA.

Although specific terms are employed herein, they are used in a generic and descriptive sense only and no† for purposes of limitation.

Features described in the preceding description may be used in combinations other than the combinations explicitly described.

Although functions have been described with reference†o certain features, those functions may be performable by other features whether described or no†.

Although features have been described with reference†o certain examples, those features may also be present in other examples whether described or no†. Accordingly, features described in relation to one example/aspec† of the disclosure may include any or all of the features described in relation to another example/aspec† of the disclosure, and vice versa,†o the extent that they are no† mutually inconsistent.

Although various examples of the present disclosure have been described in the preceding paragraphs, it should be appreciated that modifications†o the examples given can be made without departing from the scope of the invention as set out in the claims. As used herein, the "determining" (and grammatical variants thereof) can include, not least: calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, "determining" can include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, "determining" can include resolving, selecting, choosing, establishing, and the like.

Whilst endeavouring in the foregoing specification†o draw attention†o those features of examples of the present disclosure believed to be of particular importance it should be understood that the applicant claims protection in respect of any patentable feature or combination of features hereinbefore referred to and/or shown in the drawings whether or not particular emphasis has been placed thereon.

The examples of the present disclosure and the accompanying claims may be suitably combined in any manner apparent†o one of ordinary skill in the art.

Each and every claim is incorporated as further disclosure info the specification and the claims are embodimenf(s) of the present invention. Further, while the claims herein are provided as comprising specific dependencies, it is contemplated that any claims may depend from any other claims and that to the extent that any alternative embodiments may result from combining, integrating, and/or omitting features of the various claims and/or changing dependencies of claims, any such alternative embodiments and their equivalents are also within the scope of the disclosure.

Claims

We claim: 1. A method for generating map data, the method comprising causing, a† leas† in part, actions that result in:

receiving a firs† map data element and a second map data element, each map data element defining a shape and a location of a map object; expanding the shape of a† leas† the firs† map data element;

in response†o determining that the expanded shape of a† leas† the firs† map data element overlaps with the shape of the second map data element, merging the firs† and second overlapping shapes†o form a unified shape; and

generating map data using the unified shape.

2. The method of any one or more of the previous claims, wherein expanding the shape comprises increasing the dimensions of the shape.

3. The method of any one or more of the previous claims, further comprising reducing the size of the unified shape.

4. The method of any one or more of the previous claims further comprising causing, a† leas† in part, actions that result in:

receiving a firs† set of map data elements;

expanding the shapes of each of the map data elements;

merging overlapping expanded shapes†o form one or more unified shapes;

using the one or more unified shapes†o generate a second set of map data elements comprising fewer map data elements than the firs† set of map data elements.

5. The method of claim 4, further comprising reducing the size of the one or more unified shapes.

6. The method of claim 4 or 5, further comprising removing any holes in the one or more unified shapes.

7. The method of any one or more of the previous claim 4†o 7, further comprising causing, at least in par†, actions that result in:

identifying map data elements of the second set of map data elements having a size greater than a pre-de†ermined threshold†o define a firs† subset of the second set of map data elements; and

identifying map data elements of the second set of map data elements having a size less than a pre-de†ermined threshold †o define a second subset of the second set of map data elements.

8. The method of claim 7, further comprising causing, a† leas† in part, actions that result in:

expanding the shape of each of the map data elements of the second subset;

in response†o determining that one or more expanded shapes of the second subset overlaps with another expanded shape of the second subset, merging the overlapping expanded shapes of the second subset†o form one or more unified shapes of the second subset.

9. The method of claim 8, further comprising reducing the size of the one or more unified shapes of the second subset.

10. The method of claim 8 or 9, further comprising removing any holes in the unified shapes of the second subset.

1 1 . The method of any of claims 7 to 10, wherein:

expanding the shape of each of the plurality of map data elements comprises expanding the shape of each of the plurality of map data elements by a firs† scaling factor; and expanding the shape of each of the map data elements of the second subset comprises expanding the shape of each of the map data elements of the second subset by a second scaling factor different to the firs† scaling factor.

12. The method of any one or more of the previous claims, further comprising removing map data elements having shapes determined†o be less than a pre-defermined threshold size.

13. The method of any one or more of the previous claims when dependent†o claim 7, further comprising generating a third data set of map data elements by combining:

the first subset of the second set of map data elements, and

the one or more unified shapes of the second subset of the second set of map data elements.

14. The method of any one or more of the previous claims, wherein the map data elements comprises one or more of:

a shape and location of a building footprint,

a shape and location of a car park,

a shape and location of at least a portion of a navigable element, an address point location,

an address point hookline, and

a postal point.

15. The method of any one or more of the previous claims, wherein the generated map data is configured to be representative of a built up area.

16. An apparatus comprising means configured to cause the apparatus at least to perform the method as claimed in one or more of claims 1 to 15.

17. A computer program that, when performed by at least one processor, causes the method as claimed in any one or more of claims 1 to 15.

18. A computer readable storage medium encoded with instructions that, when performed by a processor, performs the method of any one or more of claims 1 to 15, preferably wherein the computer readable storage medium is non-†ransi†ory