Abstract:
A method for assisted map extrapolation computing establishing a database of geographic images and establishing a database of geospatial datasets extracted from the database of geographic images The method provides an unskilled user interface hosted remotely or self contained within a computing device loaded with imagery and analysis software wherein an unskilled user may select a geographic area The method superimposes any existing data from the geospatial datasets onto the geographic images for a geographic area and displays it to the unskilled user A set of algorithm parameter controls are provided wherein the individual may teach image analysis software how to pick transportation network features such as roads or other objects such as building footprints from the imagery The geospatial datasets are then updated with the features identified by the unskilled user assisted software

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    This invention relates generally to a system and method for extrapolating information from geographic images for the generation of digital maps. More particularly, this invention relates to a system and method for utilizing unskilled user assistance to improve semi automated map extrapolation. 
         [0003]    2. Related Art 
         [0004]    Mapping and navigational devices require complex geospatial map data for operation. With the constantly changing landscape of modern society, it has become increasingly difficult to maintain accurate and up to date map data. The digital maps are obtained by various methods, including high resolution imagery taken from space, as well as ortho-rectified images taken from land-based vehicle. One popular methodology utilizes high resolution multi-spectral images that is available for virtually all of the earth surface. 
         [0005]    There exists a wide variety of systems and methods for automatically or semi-automatically extracting road vectors or spatial objects from this imagery. However, the imagery is typically of varying quality and exposure. Furthermore, the road or other features in the imagery may be obscured by trees, clouds, and other sources. Consequently the quality of automatically extracted objects from imagery is generally poor. Better quality is derived by a semi-automated process where a skilled technician provides seed information that assists a process in distinguishing roads or other objects on the imagery. 
         [0006]    A relatively new approach to improving the map data has been the use of crowd sourcing. Present methodologies utilize passive position sensors such as GPS sensors in a Personal Navigation Device (PND). As a user operates the PND, the device passively records GPS traces along the travel path. This passive data is uploaded to the map developers for use in improving their databases. In many areas, however, the utilization of PND or GPS equipped smart phones is limited and therefore passive approaches to crowd sourcing are not available. In addition, even where such data is available it is only possible to extract the geometry and not detailed attributions such as road names, speed limit. 
         [0007]    Detailed imagery of the entire world is readily available, and roads or other transportation corridors can be readily identified on the images by humans, but in many cases are difficult for a computer to identify. As mentioned above, a skilled operator can teach a computer how to pick roads from imagery. However, with an appropriately designed interface, an unskilled operator is able to perform this function. What is needed is a method and system for positively engaging end users of navigation systems or digital map displays to perform the function of teaching a computer to extract roads and other objects from imagery that was here-to-fore performed by skilled technicians. Furthermore, such a method would allow for accurate modifications of existing geometry and would provide for the addition of detailed attributions that would otherwise be unavailable. It is therefore an object of the present invention to provide a system and method for having end users operate semi-automated road extraction software from high resolution imagery. 
       SUMMARY OF THE INVENTION AND ADVANTAGES 
       [0008]    These and other objects and advantages are achieved according to one aspect of the invention by a method for assisted map extrapolation comprising establishing a database of geographic images and establishing a database of geospatial datasets extracted from the database of geographic images. The method provides an unskilled user interface hosted remotely or self contained within a computing device loaded with imagery and analysis software wherein an unskilled user may select a geographic area. The method superimposes any existing data from the geospatial datasets onto the geographic images for a geographic area and displays it to the unskilled user. A set of algorithm parameter controls are provided wherein the unskilled user may teach image analysis software how to pick transportation network features such as roads or other objects such as building footprints from the imagery. The geospatial datasets are then updated with the features identified by the unskilled user assisted software. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    These and other features and advantages of the present invention will become more readily appreciated when considered in connection with the following detailed description and appended drawings, wherein: 
           [0010]      FIG. 1  is a schematic view of a method and system for assisted map extrapolation  10  in accordance with the present invention; 
           [0011]      FIG. 2  is an illustration of an unskilled user selecting a portion of a geospatial object for use as seed points in accordance with the system described in  FIG. 1 ; 
           [0012]      FIG. 3  is a detailed view of a first pass geography extrapolation superimposed on a geographic image in accordance with the present invention; 
           [0013]      FIG. 4  is a detailed view a unskilled user moving an algorithm parameter control and the results of a multi-pass geography extrapolation superimposed on the geographical image shown in  FIG. 3 ; 
           [0014]      FIG. 5  is a detailed view of an unskilled user accessing a manual cleanup module to erase a geospatial object such as a road; 
           [0015]      FIG. 6  is a detailed view of an unskilled user accessing a manual cleanup module to move a geospatial object such as a road; and 
           [0016]      FIG. 7  is a detailed view of an unskilled user accessing a manual cleanup module to add a geospatial object such as a road; 
           [0017]      FIG. 8  is a detailed illustration of an attribution input module in accordance with the present invention; 
           [0018]      FIG. 9  is an illustration of an alternate embodiment of the present invention, the embodiment utilized selected point parings; and 
           [0019]      FIG. 10  is a schematic view of the alternate method and system for assisted map extrapolation  10  as illustrated in  FIG. 9  and in accordance with the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0020]    Referring to the Figures, wherein like numerals indicate like or corresponding parts throughout the several views, this invention pertains to digital transportation network navigation systems and to the digital maps, databases and devices used by navigation systems. By “digital transportation network”, it is meant to include digital mapping systems for various established transportation networks, including various roadway surfaces for motorized and non-motorized vehicles, walking, biking, skiing and hiking trails, and other established routes along which users of navigations devices travel for business or pleasure. For purposes of this invention, the term “roadway” is intended to be used in a most general way and to be inclusive of all paved and unpaved roads, paths, trails and the like for use by any type of vehicle or a pedestrian. 
         [0021]    Referring now to  FIG. 1 , which is a schematic illustration for a system of assisted map extrapolation  10  in accordance with the present invention. The system utilizes a database of geographic images  12 , at the same scale and using the same map projection so as features on the image are coincident with features displayed from the transportation database. These images  12  may be accumulated through a variety of sources including the use of high-resolution multi-spectral images of the earth surface. The system  10  further includes a geo-spatial map dataset database  14 . In at least one embodiment, the initial geo-spatial map data-set database  14  is comprised of geospatial object data  15  automatically extrapolated from the geographic images database  12  using imaging processing algorithms. The geospatial object data  15  defines a plurality of geospatial objects  17  such as roads, buildings, bodies of water, etc. 
         [0022]    The system  10  contemplates the use of a unskilled user interface  16  wherein an unskilled user  11  may interface with the system for assisted map extrapolation  10 . The term unskilled user  11  is intended to encompass any individual without map extrapolation experience. In one embodiment, it is contemplated that the unskilled user  11  may be a member of the general public. In other embodiments, the unskilled user  11  is one of a select group of individuals with proper motivation but no formal map training. It is contemplated that the unskilled user interface  16  may be web based or contained within a stand-alone computer system loaded with imagery. 
         [0023]    The unskilled user interface  16  includes a first interface element  18  to prompt the unskilled user to select a geographic area  20 . In one embodiment, it is conceived that the unskilled user  11  will utilize the unskilled user interface  16  to identify regions he/she is familiar with in order to review the veracity of the geo-spatial map dataset database  14  as it relates to the geographic images  12 . It is further conceived that the geographic area  20  could be automatically selected to a region near the unskilled user&#39;s location. Once a geographic area  20  has been identified, the system  10  utilizes an extrapolation algorithm module  22  to perform a first pass geography extrapolation  24  wherein the module  22  extrapolates geospatial object data  15  from the geographic image  12  of the selected geographic area  20 . It is contemplated that the first pass geography extrapolation  24  is performed utilizing initial seed points  26  provided to the extrapolation algorithm module  22 . 
         [0024]    It is contemplated that the seed points  26  can be obtained in a variety of fashions. In one embodiment, the unskilled user  11  is prompted to select portions  28  of the geographic image  12  to identify a particular geospatial object  17 , such as a portion of a road or building. ( FIG. 2 ). The visual parameters  30  of the selected portion  28  are utilized by the extrapolation algorithm module  22  to begin the first pass geography extrapolation  24 . In another approach, existing data from the geo-spatial map dataset database  14  may be utilized as the initial seed points  26 . In still another embodiment, where the existing geo-spatial map dataset database  14  information is fairly complete, it is contemplated that the existing geospatial object data  15  for the selected geographic area  20  may be utilized without utilizing a first pass geography extrapolation  24 . 
         [0025]    The interface  16  is then configured to display the first pass geography extrapolation  24  superimposed on the geography image  12  of the selected geography area  20  ( FIG. 3 ). The interface  16  further provides the unskilled user  11  with at least one algorithm parameter control  32  which controls at least one parameter  34  utilized by the extrapolation algorithm module  22  when analyzing a geographic image  12 . An individual control  32  may alter a single parameter  34  or a plurality of parameters. It is contemplated that the control  32  may adjust the aggressiveness of the extrapolation algorithm module  22 . The term aggressiveness is known in the art to refer to the ability of an algorithm to associate portions of an image with an object. For lenticular objects such as roads the algorithm will generally utilize a weighted graph constructed from the line segments identified as roads and the gaps between lines segments where the road is obscured by trees and other impediments. The algorithm will attempt to fill in these gaps. Various parameters can be set to determine how aggressively the algorithm will fill in the gaps. Depending on how these are set, the algorithm may be too aggressive and determine certain linticular features are roads when they are not and/or link road segments together when they should not be. Alternatively, they could not be aggressive enough and miss many roads. 
         [0026]    In addition, although a single control  32  may be utilized, the present invention contemplates the use of multiple controls  32  each controlling a separate algorithm parameter  34 . It is contemplated that these algorithm parameters  34  can include a variety of parameters including, but not limited to, object dimension, intensity, hue, saturation, and object color. Image analysis software used to identify roads or other features from the image relies on finding pixels or groups of pixels with features that are indicative of a road. These features might consist of intensity, huge, saturation, and color of the pixels that make up a road. They may also consist of lenticular groupings of the preceding features—for example, roads may be defined by a group of pixels no more than 4 pixels wide, but as long or longer than 10 pixels. All pixels may, for example, be the same or similar huge of grey. Adjacent imagery may be subtlety different from one image to the next—because of such factors as the sun angle was different when two adjacent images were recorded or the camera used had different characteristics. As the unskilled user  11  adjusts the algorithm parameter control  32 , such as my moving a slider bar  36 , these changes are sent to the extrapolation algorithm module  22  ( FIG. 4 ). An unskilled user  11  does not need to know necessary what parameters  34  affect automated picking of roads from imagery, just that they do affect the accuracy of the picks. A system of controls  32  can be provided consisting of slider bars or virtual dials that adjust factors affecting how the software performs. One slide bar could be color. A unskilled user  11  would move the slide bar  36  to, for example, change the color from grey to more brown. The extrapolation algorithm module  22  would detect the change and recalculate the road picks, based on the change—then redisplay the road picks for the user. This change may have improved the road picks or made them worse. The unskilled user  11  then has the option to further tweek the color or some other parameter to see if the road picks improves or gets worse. The unskilled user  11  does not need to know what parameters  34  the controls affect, he/she simply needs to observe the effect of the change of the control  36 . With practice, the use would develop skill in knowing which controls have what effect. 
         [0027]    The extrapolation algorithm module  22  utilizes that information from the algorithm parameter control  32  to perform a second pass geography extrapolation  38  and display it superimposed on the geographic image  12 . It is contemplated that the second pass geography extrapolation  38  comprises a multi-pass geography extrapolation such that the unskilled user  11  can adjust the controls  32  and visually watch the adjustments until the extrapolation most closely matches the geographic image  12 . This allows an unskilled user  11  to improve the extrapolation without any knowledge of how the extrapolation methodologies actually operate. In an alternate embodiment, it is contemplated that the controls  32  comprise prompts for the unskilled user  11  identify additional portions of a particular geospatial object  17  and this is utilized by the multi-pass extrapolation in a similar fashion. The unskilled user  11  will continue to pick more points on an object, such as a road, until the extrapolation most closely matches the geographic image  12 . 
         [0028]    The system  10  further contemplates the use of a manual cleanup module  40  once the aforementioned extrapolations are satisfactory to the unskilled user  11  ( FIG. 1 ). The manual cleanup module  40  is intended to allow the unskilled user  11  to manually adjust a particular geospatial object  17  not properly addressed by the extrapolations. It is contemplated that this manual adjustment can include, but is not limited to, deleting the particular geospatial object ( FIG. 5 ), moving the particular geospatial object ( FIG. 6 ), or inserting a new geospatial object ( FIG. 7 ). This allows the unskilled user  11  to address issues not dealt with through algorithm adjustment. It is contemplated that this may arise when the view of geospatial objects  17  is impeded by other topography such as trees, shade, buildings, etc. 
         [0029]    Finally, the system  10  further contemplates the use of an attribution input module  42  ( FIG. 8 ). The attribution input module  42  allows the unskilled user  11  to enter non-geographic attributes  44  into the geospatial dataset data base  14 . This can include information such as road names, building names, attraction information, road travel direction, speed limits, etc. This is highly valuable as this information is largely unavailable from the geographic images  12 . Once the unskilled user  11  is satisfied, the adjustments made by way of the controlled extrapolation in addition to the non-geographic attributes  44  can be utilized to improve the geospatial dataset database  14 . 
         [0030]    In an additional embodiment of the present invention, the system  10  contemplates the database of geographic images  12  to comprise a database of ortho-rectified geographic images ( FIGS. 9 and 10 ). The unskilled user  11  is still prompted to identify a geographic area  20  that is familiar. In this embodiment, however, the unskilled user interface  16  displays street information and/or the geospatial database  14  information superimposed onto the ortho-rectified geographic image  12  of the selected geographic area  20 . The unskilled user  11  is prompted to select a plurality of point pairs  48 , each comprising a point from the geospatial map data  14  and a point from the ortho-rectified geographic image  12  that should be in the same location but are not. In this embodiment the extrapolation algorithm module  22  skews/warps the spatial database  14  based on one of a variety of conflation techniques so that the point pairs  48  coincide and intermediate points  50  in between are skewed based on a weighting relative to the nearby point pairs  48 . The technique is applied repeatedly to maximize the correspondence of the point pairs  48  and minimize the distortion of straight lines or curves in the geospatial dataset database  14 . In this embodiment, the unskilled user  11  may continue to pick point pairs  48  until the visual image of the superimposed geospatial dataset database  14  over the ortho-rectified geographical image  12  is satisfactory. It is contemplated that the unskilled user  11  will be then be afforded the opportunity to access the manual cleanup module  40  and the attribution input module  42  to make further improvements. 
         [0031]    It is contemplated that a variety of motivational techniques could be employed to encourage this public interaction. The first is simply a personal motivation. Local businesses in new developments will have an active desire to see their local areas correctly mapped such that patrons can easily find them. Rural individuals may find that correcting local maps may improve deliveries. Contests and give away promotions may be used to elicit public response. Finally, a personal credit may be given to individuals making corrections and reflected within the geo-spatial data-set database  14  such that pride may provide sufficient motivation. 
         [0032]    The foregoing invention has been described in accordance with the relevant legal standards, thus the description is exemplary rather than limiting in nature. Variations and modifications to the disclosed embodiment may become apparent to those skilled in the art and fall within the scope of the invention. Accordingly the scope of legal protection afforded this invention can only be determined by studying the following claims.