Semi-automatic extraction of linear features from image data

Method for editing a vector set associated with an extracted linear feature in a remotely sensed image, the vector set defining a path and being tied to a geographical location. The method includes displaying the path in a graphical display. Once the user activates a smart editing tool, the user establishes a region of influence centered around a cursor. The region of influence is configured to respond to cursor movements. The user specifies a point near the path and moves the cursor to it, brining the region of influence along. Any error in the vector set of the path is automatically corrected in real time using image-based logic. The user then previews the correction on the graphical display and implements it, updating the path. The updated path is displayed in real time in the graphical display.

FIELD OF THE INVENTION

This invention relates generally to the field of geospatial analysis and specifically to extracting features of remotely-sensed image data.

BACKGROUND OF THE INVENTION

Geographical information systems (GIS), including remotely-sensed imagery from satellites and aircraft, have revolutionized mapping. To the naked eye, while this imagery may appear to be merely an aerial view of a particular location captured at a particular point in time, there is significant spatial data associated with the imagery.

Spatial data associated with such imagery may be stored, manipulated and displayed in a raster layer. Each GIS image is divided into a grid made up of rows and columns, forming a matrix. Each rectangle defined by the grid is a pixel or cell. Geographical location coordinates and information regarding other attributes, including spectral component bands (e.g., blue, green, red, and near-infrared in the case of multispectral and hyperspectral imagery), may be associated with each cell in the raster layer. Raster data may be stored for each cell in the matrix or may be compressed, particularly in the case of panchromatic images.

Instead of measuring reflected radiation as would be the case for multispectral imagery, radar imagery is the product of bombarding an area with microwaves and recording the strength and travel-time of the return pulses. Radar imagery has particular utility for geographical mapping, monitoring and military applications because the radar imagery may be acquired in any type of weather or at any time, day or night. Since the microwaves used by radar are longer than those associated with optical sensors, radar is not affected by clouds, smoke, pollution, snow, rain or darkness. While radar imagery may appear to be merely a black and white aerial view of a particular geographical location, there is significant spatial data associated with radar imagery. Spatial data associated with such radar imagery may be stored, manipulated and displayed in a raster layer. Each radar image is divided into a grid made up of rows and columns, forming a matrix. Each rectangle defined by the grid is a pixel or cell. Geographical location coordinates and signal strength may be associated with each cell in the raster layer. Raster data may be stored for each cell in the matrix or may be compressed.

Prior art methods have been developed for extracting road locations from raster data to make road maps. However, the prior art methods have been limited to a specific type of imagery such that methods useful for multispectral imagery would not have worked well on radar imagery, panchromatic, or hyperspectral imagery. Indeed, it is not known whether hyperspectral imagery has even been used for linear feature extraction, since its applications have been primarily limited to agricultural ground use, detection and identification of military targets, ocean and forestry observation, and oil, gas, and mineral exploration. Even given a particular type of imagery, the prior art methods have serious drawbacks. With respect to multispectral imagery, automatic methods for extracting road features are unreliable, often locating roads where none exist. Extracting road features manually may be accurate, but manual extraction is inefficient and tiring for cartographers. With respect to radar imagery, prior art methods have largely been limited to manual extraction. While manual extraction may be accurate for those experienced in working with radar imagery, it is tedious, especially when extracting curved roads. However, given the noise, inconsistent brightness and relative low resolution of radar imagery, prior art automatic methods for extracting road features from radar imagery have proved completely unreliable, often veering off the roads or locating roads where none existed.

Thus, there developed a need for an interactive method of extracting linear features from remotely-sensed imagery of all kinds, using spatial data contained in raster layers.

BRIEF SUMMARY OF THE INVENTION

The following summary is provided as a brief overview of the claimed invention. It shall not limit the invention in any respect, with the detailed and fully enabling disclosure being set forth in the Detailed Description of the invention section. Likewise, the invention shall not be limited in any numerical parameters, hardware, software, platform or other variables otherwise stated herein.

An embodiment of the present invention comprises a method for editing a vector set associated with an extracted linear feature in a remotely sensed image, the vector set defining a path and being tied to a geographical location. The method comprises: displaying the path in the remotely sensed image in a graphical display; by user interface, activating a smart editing tool; using a motion sensitive device linked to a cursor on the graphical display, establishing a region of influence operatively associated with the motion sensitive device and the smart editing tool, the region of influence being centered around the cursor, displayed on the graphical display and being configured to change location in the graphical display in response to movement of the cursor as directed by the motion sensitive device; using the motion sensitive device to move the cursor to a user-specified point in the vicinity of the path, thereby changing the location of the region of influence to encompass at least a portion of the path; automatically evaluating the path for an error in the vector set using image-based logic; using image-based logic, automatically suggesting a proposed correction for the error and displaying the proposed correction in real time on the graphical display; by user interface, previewing the proposed correction on the graphical display; using the motion-sensitive device, implementing the proposed correction in a final correction to the vector set resulting in a revised path; and displaying the revised path in real time on the graphical display.

Another embodiment comprises a method for modifying a segment from a path associated with an extracted linear feature in a remotely sensed image, the segment being tied to a geographical location and stored in a file. The method comprises: displaying the path on a graphical display; using a motion sensitive device operatively associated with a cursor to select a first point in the vicinity of path, the first point being associated with a first end point of the segment; by user interface, using the motion sensitive device to move the cursor along the path in a direction away from the first end point to a temporary end point, the temporary end point and the first end point being connected by a temporary segment; using the motion-sensitive device, converting the temporary end point to a second end point, thereby changing the temporary segment to the segment; automatically modifying the segment in real time on the graphical display to a modified segment; and saving the modified segment in the file.

In yet another embodiment, the present invention comprise a method for excising a plurality of vector sets contained within a final polygon, the plurality of vector sets defining paths associated with a plurality of extracted linear features in a remotely sensed image, the vector sets being tied to geographical locations and stored in a file. The method comprises: displaying the paths on a graphical display; using a motion sensitive device operatively associated with a cursor to select a first vertex in the vicinity of the paths by marking the first vertex with the cursor; using the motion sensitive device to move the cursor to select at least a second vertex and a third vertex, the first vertex, second vertex and third vertex being connected in real time in the graphical display to form a polygon encompassing the vector sets; converting the polygon into the final polygon; automatically excising the vector sets contained within the final polygon in real time in the graphical display; and

removing the vector sets contained within the final polygon from the file.

The present invention also comprises a method for attributing a geometry to a path defined by a vector set associated with an extracted linear feature, comprising: displaying the path on a graphical display; using a motion sensitive device to select the path by locating a cursor associated with the motion sensitive device on the path; using the motion sensitive device to continuously change the geometry of the path in real time resulting in a changed geometry; and associating the changed geometry with the vector set in the file.

In another embodiment, the present invention comprises a method for modifying a plurality of vector sets associated with extracted linear features in a remotely sensed image displayed in a graphical display, comprising: activating a paint selection mode; selecting the plurality of vector sets by using a motion-sensitive device operatively associated with a cursor to move the cursor along a trajectory in the remotely sensed image; adding each vector set in the trajectory to a selection ensemble; and performing a universal modification action on the vector sets in the selection ensemble.

The present invention also comprises a method for reviewing the accuracy of extracted linear features in a remotely-sensed image, each extracted linear feature being defined by a vector set. The method comprises: displaying the remotely sensed image on a graphical display; partitioning the remotely sensed image into a plurality of cells, the plurality of cells being displayed in the graphical display; selecting one of the plurality of cells to be a focused cell; reviewing at least one vector set within the focused cell, the at least one vector set being a reviewed vector set and other vector sets being unreviewed vector sets; in real time, designating the reviewed vector set as committed and the unreviewed vector sets as uncommitted; and storing the committed vector set.

The invention further comprises a method for modifying a plurality of vector sets associated with a plurality of extracted linear features in a remotely sensed image, the vector sets being tied to geographical locations and stored in a file. The method comprises: displaying the remotely sensed image on a graphical display; using a motion sensitive device operatively associated with a cursor to select a first vertex in the remotely sensed image, marking the first vertex with the cursor; using the motion sensitive device to move the cursor to select at least a second vertex, the first vertex and the second vertex being connected in real time in the graphical display to form a polyline crossing the vectors sets resulting in selected vector sets; automatically distinguishing the selected vector sets in the graphical display; and modifying the selected vector sets.

An embodiment of the present invention comprises a method for extracting a linear feature in a remotely-sensed image comprising pixels, the linear feature being of a user-selected type and associated with a geographical location. The method comprises: displaying the linear feature on a graphical display; dividing the pixels into a first group and a second group, the first group of pixels being associated with the linear feature and the user-selected type; storing the first group of pixels and second group of pixels in a file; selecting by user-interface a point in the vicinity of the linear feature in the remotely sensed image; using image-based logic and the first group of pixels, automatically snapping the point to the linear feature; and extracting the linear feature, the extracted linear feature being defined by a vector set.

The present invention also comprises a method for extending a first path in a remotely sensed image, the first path being defined by a first vector set associated with an extracted linear feature and a first geographical location. The method comprises: displaying the first path in a graphical display; by user-interface, selecting an additional linear feature oriented substantially in tandem with the path; by user interface, selecting an anchor point for the additional linear feature; using image-based logic and the anchor point, automatically calculating a second vector set, the second vector set being associated with the additional linear feature and a second geographical location and defining a second path; and in real time, automatically connecting the second path to the first path.

DETAILED DESCRIPTION OF THE INVENTION

Broadly described, a method10of the present invention comprises extracting at least one linear feature from remotely-sensed imagery. As used herein, “remotely-sensed imagery” is satellite or aerial imagery of a geographical location that measures reflected or emitted radiation in spectral bands ranging from ultraviolet to infrared on the electromagnetic spectrum, and maintains spatial data in a raster GIS format. A “multispectral image” is an image collected in multiple bands ranging from ultraviolet to infrared. A “panchromatic image” is an image collected in the broad visual wavelength range (plus near-infrared) but rendered in black and white. As used herein, “radar imagery” is imagery produced by illuminating a geographical area with microwaves and measuring and recording the strength and travel time of the received signals or the transmitted and received signals. Radar imagery includes but is not limited to imagery produced from real aperture and synthetic aperture radar (SAR). Generally, radar imagery includes single-band imagery of varying resolutions and dynamic ranges. “Hyperspectral imagery” is an image collected in hundreds of narrow and contiguous spectral bands. Hyperspectral imagery differs from multispectral imagery in the number of bands and the fact that the bands are contiguous. In addition, hyperspectral image data may be viewed in three dimensions of two spatial dimensions and one spectral dimension. A “linear feature” is any feature captured in remotely-sensed imagery such that its pixels lie within a neighborhood distance of a polygonal line, where the neighborhood distance is small by comparison to the total length of the polygonal line. Linear features may include but are not limited to paved roads, unpaved roads, trails, rivers, paths and runways. The linear feature is not limited in any respect to a straight line; thus, the linear feature may be irregular, curved, zigzagged, or meandering, as may be the case of a rural road or a trail. In addition, the linear feature may be characterized by a geometric shape indicative of an aspect of a road, including but not limited to a circle, an oval, loop, or cloverleaf. “Extracting” is a term broadly used to describe a process for locating and identifying the linear feature by reference to at least one data component (e.g., geographical location) associated with the linear feature.

According to an embodiment of a method10of the invention, using a commercially-available geospatial imaging raster-based software, the user may select12a four-band multispectral image14that has previously undergone atmospheric correction according to methods that are well-known in the art, although such atmospheric correction is not required. By way of example, the four bands of the multispectral image14are blue, green, red and near-infrared. However, other spectral bands or additional or fewer bands may be used.FIG. 1shows the selecting12of four-band multispectral image14as used in an embodiment herein. The multispectral image14has a spatial resolution of about 3.28 meters. The commercially-available software is ERDAS IMAGINE® sold by Leica Geosystems Geospatial Imaging, LLC of Norcross, Ga. The four-band multispectral image14was produced by the IKONOS® satellite owned by GeoEye, Dulles, Va.

The method10may further comprise selecting22an output vector file24, as shown inFIGS. 1 and 2. The output vector file24may comprise at least one vector set, a material type56and a geometry46, as explained more fully below. As used herein, a “vector set” comprises a sequence of points (coordinate pairs (x, y)) (e.g., vector) defining a polygonal path30through user-specified anchor points32,34. By virtue of its creation, the polygonal path30may introduce zero to many additional intermediate points38between anchor points32,34.

A preferred embodiment of the method10may comprise inputting16a texture file18, as well. By way of example, the texture file18is generated from a panchromatic image20from the IKONOS® satellite related to the selected multispectral image14. In this example, the panchromatic image20has a spatial resolution of about 0.82 meters.FIG. 2shows the inputting16of texture file18.FIG. 3shows the panchromatic image20associated with the multispectral image14. The texture file18comprises information derived from measuring, at each pixel in the panchromatic image20, the variance over a rectangular area, minimized over angular orientation of the rectangular area about the pixel. As shown inFIG. 4, the image variance is computed over the one-sided rectangular area, rotated by angles separated by 20°. The texture measure is the square root of the minimum variance over these angles. While inputting16the texture file18may be preferred, it is not required as explained more fully below with respect to other embodiments of the method10. Generating223and using texture file18has been described with additional detail in D. Haverkamp and R. Poulsen, “Complementary methods for extracting road centerlines from IKONOS imagery”, Image and Signal Processing for Remote Sensing VIII (Sebastiano B. Serpico; Ed.), Proc. SPIE Vol. 4885, p. 501-511 (2003), which is incorporated herein by reference for all that it discloses.

According to the method10, after inputting16the texture file18, the user may select26a track mode28, as shown inFIG. 5. The track mode28comprises using image-based logic to automatically calculate the appropriate vector sets associated with the anchor points32,34, tracking path30between first anchor point32and second anchor point34selected52by the user to create a near centerline for a road40in multispectral image14, as shown inFIG. 6. As used herein, “path”30may be defined by the vector set.

By way of example, the track mode28image-based logic may comprise a least cost path algorithm incorporated in software, such as Djikstra's algorithm or any other least cost path algorithm known in the art. Least cost path algorithms are well known in the art for constructing a least cost path between two points as a function of “cost.” Assigning costs to different variables represents a way to distinguish between desirable paths and undesirable paths. In the case of the present invention, “cost” may distinguish between image features that are highly correlated, somewhat correlated, or not correlated with the presence of a selected linear feature (e.g., road40), such that high correlation defines low cost. Thus, the least cost path algorithm may assign a cost to moving from one pixel to another (e.g., along path30). By way of example, a preferred cost function may have a lower cost associated with image features related to the middle of road40, with a higher cost associated with image features related to areas away from road40. In an embodiment of the method10, the algorithm may determine the lowest cost path30by assigning a cost to each of several factors and then determining a total combined cost which in turn dictates path30between the user-selected52anchor points32,34. A first factor in assigning cost may be path30length associated with moving from one pixel to another. A second factor in assigning cost may be “spectral roadlikeness,” which may be considered to be the degree to which pixels associated with path30are spectrally similar to typical pixels of a desired class of linear feature (e.g., paved roads). By way of example, spectral roadlikeness is computed by using known Tasseled Cap transformations of the multispectral image14. It has been found that while vegetation is strong in the near infrared band, roads40are weak in the near infrared band. Thus, Tasseled Cap transformations can be used to separate roads40from vegetation. A third factor in assigning cost may be textural roadlikeness, or road40texture. Texture may be derived from the panchromatic image20, as mentioned above, and used as part of image-based logic to identify and locate linear features. A fourth factor in assigning cost may be adjacency to previously extracted roads40. For example, the algorithm adds an increased cost to finding path30that may coincide with or closely parallel portions of previously extracted path30. Another cost factor may be associated with proximity to delimiting edges of road40. Another cost factor may be pixel intensity along axes (bands) of a red, green, blue, infra-red coordinate system or along axes (bands) of a Tasseled Cap coordinate system. Yet another cost factor may be associated with pixel adjacencies along path30. In other embodiments, “image-based logic” may comprise using image data, including spatial relationships and relationships between pixels, to make at least one correlation in data related to a linear feature, possibly to prefer one correlation over another.

Track mode28may be used when panchromatic texture is available. Since panchromatic image20may not always be available, another embodiment may comprise using multispectral image14without the benefit of panchromatic image20and its associated texture. In this embodiment, the user may select a spectral mode. The spectral mode may be used either when panchromatic texture is not available, or when panchromatic texture is available but not a good indicator for road40. Like the track mode28, the spectral mode comprises using image-based logic to track path30between first anchor point32and second anchor point34selected by the user by evaluating spectral similarity to the anchor points32,34and ignoring panchromatic texture. Use of the spectral mode may be beneficial in extracting linear features where the texture is rough, such as in the case of dirt roads, or streets with a lot of overhanging trees, building shadows, or vehicles on the road40surface. The image-based logic of the spectral mode may comprise a least cost path algorithm incorporated in software, such as Djikstra's algorithm or any other least cost path algorithm known in the art. In the spectral mode, the cost factors used to determine the lowest cost path between the user-selected52anchor points32,34may comprise: (1) path30length, (2) spectral similarity to the user-specified anchor points32,34, and (3) adjacency to previously extracted roads. By way of example, adjacency to previously extracted roads adds an additional cost, because road40should not be extracted more than once. For example, the algorithm adds an increased cost to finding path30that may coincide with or closely parallel portions of previously extracted path30. Another cost factor may be associated with proximity to delimiting edges of road40. Another cost factor may be associated with pixel adjacencies along path30. By way of example, the spectral mode may not create least cost path30quite as near the centerline of road40as that created using track mode28. The spectral mode is working with less information than the track mode28; texture is not being used to help guide the path near the road centerline.

It is preferred that the multispectral image14be displayed in a manner known in the art that provides high color contrast, such as using false color bands. It is also preferred that the user zoom in on the multispectral image14to about 150-200% of one image pixel to display pixel.

As shown inFIG. 7, having selected26the track mode28, the user visually locates road40in multispectral image14. Referring toFIG. 8, the user may select52a plurality of anchor points32,34associated with road40, anchor points32,34being tied to a geographical location in the raster data associated with multispectral image14. The user may then position a cursor on anchor point32, click on it and drag the cursor to anchor point34and double-click on anchor point34.

In a preferred embodiment of the method10, the anchor points32,34may define an ellipse48that has the anchor points32,34as its foci, as shown inFIG. 9. As shown inFIG. 9, the major and minor axes of the ellipse48are 1.4 and 1.0 times the distance between the anchor points32,34. In a preferred embodiment, ellipse48comprises a search region, such that intermediate point38generated for path30connecting anchor points32,34must occur within the area defined by the ellipse. In a preferred embodiment, a purpose of the search region is to manage the tradeoff between search space size and computational speed.

According to the method10, once the user has selected52at least anchor points32,34, image-based logic embedded in software may be employed to automatically create the vector set and connect the anchor points32,34via path30. Path30may include intermediate points38automatically generated in such location and in sufficient quantity to accurately reflect the character of road40. For instance, in the case of a curve in the road, where the user selects52two anchor points32,34by clicking on them, the software may add intermediate points38in between the two anchor points32,34using image-based logic to create additional vectors in the vector set so that the path30can be preferably substantially smooth and located substantially along the near centerline of the road40, as shown inFIG. 10. It may be that path30contains no such intermediate points38. In addition, depending on the character of the road40to be extracted, the user may designate additional anchor points132a,134a, in between anchor points32,34, as explained in more detail below.

For optimal accuracy of road40extraction, a preferred embodiment of method10may comprise a strategy for selecting52the plurality of anchor points32,34. Using the multispectral image14representation of road40, it is preferred that the user select52each anchor point132a(B),134a(C) by locating them in a road intersection42, or road terminal29(cul-de-sac) as shown inFIGS. 10 and 11. In addition, it is preferred that the user click on the road40instead of near the road40as shown on the multispectral image14. It may be beneficial for the user to extract the unambiguous road first, as shown inFIG. 11, by designating anchor points132a(“B” inFIG. 11) and 132(“D” inFIG. 11) first. After the path between anchor points132aand132is determined automatically, the user may select52anchor points134a(“C” inFIG. 11) and 134(“A” inFIG. 11) so path130may be automatically constructed between them. In this example, the least cost path algorithm inhibits path130from being constructed where one already exists. Further, it may be beneficial for the user to extract primary streets first and then move to secondary streets. Additional anchor points132a,134ashould be placed in natural locations, such as bends and junctions. Anchor points32,34should be located at no more than a maximum distance apart, depending on the character of the linear feature to be extracted. For instance, in the case of a straight road40, the maximum distance between anchor points32,34may be greater than in the case of a winding road40while still attaining accuracy in road40extraction. As shown inFIGS. 12 and 13, if only anchor points232(“A” inFIGS. 12 and 13) and234(“C” inFIGS. 12 and 13) are specified, then the generated path230would not properly extract the road40between anchor points232and234. However, when additional anchor point234a(“B” inFIG. 13) is selected52, then the generated path230does properly extract road240.

In the case of a loop in the road40, the number of user-specified anchor points32,34,32a,34arequired for accurate extraction of the road40may be a function of the loop shape. For example, as shown inFIG. 14, in the case of a U-shaped loop, selecting52two anchor points332,334and additional anchor point332amay allow the road40to be properly extracted. However,FIG. 15shows a tight loop with a severe bend. In that case, anchor points332(“A” inFIG. 15) and 334(“E” inFIG. 15), as well as three additional anchor points332a,334a(“B,” “C,” “D” inFIG. 15) may need to be selected52to correctly extract the road40.

In addition, a preferred embodiment of the method10may also comprise use of manual modes (e.g., without image-based logic) for extracting roads40so that the user may have the option of switching between track mode28or spectral mode (e.g., both using image-based logic), or the manual modes—spline mode or digitize mode (e.g., both not using image-based logic). It may be beneficial to use the digitize mode for manually extracting straight roads40. It may be beneficial to use the spline mode to manually extract large roads40with little curvature (e.g., highways).

When path30corresponding to road40is determined, the method10of the present invention further comprises automatically attributing54material type56to the road40. In a preferred embodiment of the method10, the step of automatically attributing54material type56to the road40may be performed while using the track mode28or the spectral mode.

Automatically attributing54material type56to the road40may be performed by using image-based logic comprising a Maximum Likelihood algorithm to attribute material type56from one of six classes: concrete (CO), medium asphalt (MA), dark asphalt (DA), light unpaved (sand or limestone) (SA), gravel (GR), and soil (SO). As shown inFIG. 16, to automatically have the material type56assigned to the least cost path30, the user may designate feature58as “unknown.” The path30may then be automatically attributed54material type56by assigning to path30a particular color associated with the appropriate material type56. Once the material type56has been automatically assigned, this information may be stored in the output vector file24.

By way of example, the material attribution algorithm uses a four-band multispectral vector with spectral components blue, green, red, and near-infrared. According to a preferred embodiment, a raw multispectral measurementMfor multispectral image14may be corrected using atmospheric levelA, such thatM′=M−A. Ensemble statistics may be computed by normalizing for solar elevation effects, such that M″=M′/sin(ε*π/180), where ε is the solar elevation angle, and then computing unweighted averages over all scenes for each class. A Tasseled Cap (TC) transform may be applied to improve class separation, such thatT=TM″, where matrix T is given by the array:

0.3880.3330.3050.316−0.257−0.152−0.2410.706−1.8364.915−2.547−0.533−1.4600.2361.5460.043
Class means {μi}i=, . . . , 6and covariances {Σi}i=1, . . . , 6of the TC values may be recorded for each scene and class. Generally, the four TC components can be described as brightness, greenness (vegetation), green−(blue+red)/2, and red−blue. The Maximum Likelihood algorithm comprises estimated prior probabilities {Pi}i=1, . . . , 6using the Regularized Mahalanobis distance, which is known in the art. The regularization step offsets the limitations of covariances that may be obtained from small samples. For TC vectorT, the class may be chosen that minimizes the expression:
(T−μi)tΣi−1(T−μi)−2 ln(|Σi|).

The prior probabilities may be established empirically, with lower weights given to the asphalt classes in the spectral mode. Using the two-letter abbreviations given to material classes set forth above, the Piestimates may be given by:

Another embodiment of the method10may comprise manually changing58the automatically attributed material type56by specifying the material type56and re-extracting62the affected road40, as shown inFIG. 17.

When path30corresponding to road40is determined, the method10of the present invention may preferably comprise automatically attributing45a geometry46to the road40. Geometry46comprises length64and width66of path30corresponding to road40, as shown inFIG. 18. Road width66may be attributed45automatically using image-based logic, preferably road texture. However, if the width66of given road40is inconsistent or may not be measured reliably, a default road width66may be entered as shown inFIG. 19. In a preferred embodiment, the default road width66was 15 meters. However, road width66may also be indicated manually.

Length64of path30may be attributed45automatically from the corresponding vector set, preferably, after a topology cleaning step, which is described below.

A preferred embodiment of the method10comprises topology cleaning. Topology cleaning may comprise using at least an anchor point snapping algorithm68, a smoothing algorithm70and a vector cleaning algorithm72.

The anchor point snapping algorithm68, or node and line snapping algorithm, may assist in cleaning road topology for a new path30after path30has been extracted. When the user selects52new first and second anchor point,32a,34a, the anchor point snapping algorithm68may determine whether the anchor points32a,34aare within a snap distance74of existing anchor point32,34on path30. The snap distance74may be a predetermined distance, preferably three pixels, as shown inFIG. 20, within which corrections to the road topology may be made. The anchor point snapping algorithm68may be disabled. If the new anchor points132,134are within the snap distance74of an existing anchor point32,34on path30, the anchor point snapping algorithm68moves or “snaps” the new anchor points132,134to coincide with the existing anchor point32,34or path30as shown inFIG. 20.FIG. 20Billustrates the result with respect to intersection42if the user fails to click precisely in the same place for each anchor point32,132.FIG. 20Aillustrates the result when the anchor point snapping algorithm68is employed so that the anchor points32,132are properly joined.

Using76smoothing algorithm70“smoothes” the least cost path30between anchor points32,34to give it a smooth appearance, rather than what might have been a jagged appearance had smoothing not been used. The various smoothing parameters are shown inFIG. 21. The user may choose to adjust a quad window parameter78. Increasing the quad window parameter78may cause extra smoothing to be applied to path30.

The vector cleaning process comprises using image-based reasoning for automatically correcting80or “cleaning” topological errors, and using interactive review and editing of the automatically generated results, including topological errors that were automatically corrected as well as ones that could not be resolved.FIG. 22illustrates two common problems—gap82and dangle84—that may result from the generated path30. Gap82may result from a situation where paths30comprising two vector sets should intersect, but one falls short of reaching the other as illustrated inFIG. 22. The gap82may be corrected by closing it. Dangle84extends beyond the point of intersection42. Dangle84may be corrected by trimming the overhanging portion until the two paths30comprising two vector sets intersect precisely. While different examples of gaps82and dangles84are explained below, the definition of gap82and dangle84should not be limited in any way to the specific examples disclosed herein.

While the anchor point snapping algorithm68may fix some gaps82and dangles84within the snap distance74, as illustrated inFIG. 20, it does not solve the problem for gaps82and dangles84exceeding the snap distance74. For example,FIG. 23shows two gaps82a,82bof equal length (about 20 m). From the image context, it can be seen that gap82ashould logically be closed because the region between the anchor point32and the intersection42comprises the road40. From the image context, it can also be seen that gap82bshould not logically be closed because the region between the vectors is not road40, but rather anchor point34properly terminates indicating a cul-de-sac. The vector cleaning algorithm72uses image-based logic in light of the multispectral image14and the panchromatic image20to determine that gap82ashould automatically be cleaned80(i.e. should logically be closed) while gap82bshould not be closed. By way of example, the vector cleaning algorithm72may determine that gap82should be closed if there is a short path30across the gap82that is spectrally similar to the endpoints of the gap82or shows smooth texture along its trajectory.

A preferred embodiment of the method10comprises automatically cleaning80topological errors. Method10further comprises automatically reviewing the path30for topological errors, such as gaps82and dangles84; automatically using image-based reasoning to clean80or fix the topological errors that can be fixed in that manner; and leaving uncorrected any other topological errors. After the cleaning vectors algorithm72has automatically cleaned80certain gaps82and dangles84, it marks and identifies the fixes85and the topological errors that it could not fix using image-based logic (e.g., problem point) and displays the results as shown inFIG. 24. For each category (fixed dangles, fixed gaps, and problem points) the viewer can be staged to the appropriate location with a marker86placed at the site of the fix85or the problem point.FIG. 24illustrates marker86highlighting fix85to gap82. The user may then review the fixes85to verify that they are proper; if the fixes85are not proper, the user may correct them. In addition, the user may review the problem points and correct them manually.

In one embodiment of the method10, the user may simultaneously put the cleaned vector set on top of the original vector set and make the line width wider for the original vector set as shown inFIG. 25. This is for the sake of comparison of the two vector sets. If the user wants to edit the cleaned vector set, the user may enter the editing mode and make the desired modifications while viewing the results.

FIGS. 26-27illustrate other instances in which the vector cleaning algorithm72may automatically clean80varieties of gaps82and dangles84.FIG. 26Aillustrates parallel gap82. Shown at very high magnification are two nearly parallel lines separated by 0.2 m. Rather than identifying this situation as two gaps, the vector cleaning algorithm72recognized it as parallel gap82and fixed it appropriately with fix85as shown inFIG. 26B.

FIG. 27Ashows what could be gap82or dangle84depending on whether the two paths30actually intersect. In this case, since the paths30do not intersect, it is parallel gap82.FIG. 26Bshows the appropriate fix85as made by the clean vectors algorithm72.

The information regarding anchor points32,34, vector sets, path30, material type56and geometry46may be stored in the output vector file24. Once the output vector file24has been populated and saved, it may be used at any time thereafter to automatically create a map using methods known in the art (e.g., with commercially available GIS software).

Various aspects of the method10of the present invention were tested for speed and accuracy. Three analysts extracted roads from two IKONOS® images both manually (e.g., without image-based logic) and according to method10of the present invention (e.g., using image-based logic).FIG. 28shows the IKONOS-1 and IKONOS-2 multispectral image14scenes with truth vectors. The IKONOS-1 multispectral image14(FIG. 28A) contains 14 km of 2-lane roads, 4 km of highways and 13 km of trails. The IKONOS-2 multispectral image14(FIG. 28B) contains 10 km of 2-lane roads, 5 km of highways and 7 km of trails. Not counting highways, both scenes contain about 50% paved roads. Two of the analysts extracted the road vectors manually or according to method10in opposite order to minimize the effects of learning the road network. The tests were intended to measure extraction and edit time and material attribution accuracy. As shown in Table 1 below, road40extraction according to method10of the present invention (“Tracker” in Table 1) was about 26% faster than manual extraction on average.

With respect to material type56attribution, the analysts in total made11errors out of318road segments for a total material type56attribution accuracy of 96.5%. In addition, when using method10, about 85% fewer mouse clicks were required.

The vector cleaning algorithm72was tested on two datasets. One was a dataset of extracted roads containing 980 vectors totaling 274 km with an associated truth file containing 2520 vectors totaling 524 km. Results of using the vector cleaning algorithm72on this data set were: Probability of dangle detection=100%; False alarm (dangle detection)=0%; Probability of gap detection=100%; False alarm (gap detection)=0%. A second dataset comprised 15 subsets over 5 scenes, each with an associated vector layer. The road extractions were not done very carefully. Nonetheless, the results of using the clean vectors algorithm72on this data set were: Probability of dangle detection=100%; False alarm (dangle detection)=0%; Probability of gap detection=99%; False alarm (gap detection)=0%.

Another embodiment of the present invention comprises a method100for extracting at least one linear feature from radar imagery, such as radar image141. With respect to radar image141, the strength of the reflected energy registers as the brightness of a pixel, such that the stronger the return signal, the brighter the pixel. The strength of the signal, in turn, may depend on a number of factors including surface roughness and moisture content. Whether a surface may be considered rough or smooth may be a function of its height variations in relation to radar wavelength. In general, the rougher the surface, the brighter the pixel associated with that surface. For instance, relatively smooth surfaces, such as road40or still water41, may reflect almost all of the incidence energy away from radar and appear dark in radar image141, as shown inFIG. 29. Rough surfaces, such as vegetation (e.g., field43) and surfaces with a lot of edges and corners (e.g., buildings), scatter incidence energy in many directions and register as brighter areas on radar image141. Electrical properties of a material also may influence how the material appears in radar image141; thus, vegetation containing high moisture content may reflect more incidence energy and appear brighter in radar image141.

Method100of the invention comprises identifying radar image141and smoothing11it, preferably using a two-dimensional isotropic Gaussian filter, although other filters as would be known to those of skill in the art may also be used. Gaussian filters are also well known. By way of example, radar image141comprises single-band radar image141. Additional bands may also be used. The smoothing11may comprise convolving the radar image141with a Gaussian scale sized appropriately for the resolution of radar image141. Whether one size Gaussian may be preferred over another may be a function of the resolution of radar image141. If the Gaussian selected is too small, the disparities in pixel brightness may not be normalized and may prevent road40from being detected. Where an appropriate size Gaussian scale is selected, the convolution process may produce a weighted average of pixel values, normalizing brightness toward the value of central pixels and removing oscillations from frequency response. By way of example, the appropriate Gaussian scale may match the width66of road40. Applying this Gaussian scale for smoothing11radar image141resulted in road40appearing as a thick line, which, as shown inFIG. 30, appears lighter than the surroundings. Another effect of the Gaussian smoothing filter may be to smooth out noise common to many radar images141.

An embodiment of method100may further comprise selecting120radar image141using a commercially-available geospatial imaging raster-based software.FIG. 29shows the selecting12of single-band radar image141as used in an embodiment herein. By way of example,FIG. 29has a spatial resolution of about 1.25 meters with an 8-bit dynamic range (which may comprise about 256 levels of brightness). However, radar images141with other resolutions and dynamic ranges may be used. The commercially-available software is ERDAS IMAGINE® sold by Leica Geosystems Geospatial Imaging, LLC of Norcross, Ga. The radar image141(which was taken of the Golden, CO area) was produced using X-band interferometric SAR from the aerial Star-3i sensor owned by Intermap, Denver, Colo.

A preferred embodiment of the method100may further comprise generating and utilizing pixel statistics associated with radar image141. The statistics preferably comprise first order and second order statistics.

The method100may further comprise selecting22output vector file24, as shown inFIG. 31. The output vector file24may comprise at least one vector set. As used herein, a “vector set” comprises a sequence of points (coordinate pairs (x, y)) defining polygonal path30through user-selected52anchor points32,34. By virtue of its creation, the path30may introduce zero to many additional intermediate points38between anchor points32,34.

According to the method100, after generating statistics and selecting22the output vector file24, the user may select26track mode28, as shown inFIG. 32. The track mode28may comprise using image-based logic to automatically generate a near-centerline path30(e.g., vector set) for road40between first user-selected52anchor point32and second user-selected anchor point34in radar image141, as shown inFIG. 33. As used herein, “path”30may be defined by the vector set. To generate path30, intermediate points38may automatically be added, as shown inFIG. 34.

By way of example, the image-based logic may comprise the least cost path algorithm incorporated in software, such as Djikstra's algorithm or any other least cost algorithm known in the art. Least cost path algorithms are well known in the art for constructing least cost path30between two points as a function of “cost.” Assigning costs to different variables represents a way to distinguish between desirable paths and undesirable paths. In the case of the present invention, “cost” may distinguish between image features that are highly correlated, somewhat correlated, or not correlated with the presence of the selected linear feature (e.g., road40), such that high correlation defines low cost. Thus, the least cost path algorithm may assign a cost to moving from one pixel to another (e.g., along path30). By way of example, there may be a lower cost associated with image features related to the middle of road40, and a higher cost associated with image features related to areas away from road40. In an embodiment of method100, the algorithm may determine the lowest cost path30by assigning a cost to each of several factors and then determining a combined total cost, which in turn may dictate path30between user-selected52anchor points32,34. A first cost factor may be path30length associated with moving from one pixel to another. A second factor in assigning cost may be spectral distance from the user-selected52anchor points32,34. Road40may show consistent brightness (distinct from the surroundings) between well-selected anchor points32,34. Thus, spectral distance from anchor points32,34may be correlated with the presence of road40.

A third factor in assigning cost may be a Laplacian of Gaussian. As is well known, the Laplacian calculates a second spatial derivative of an image (e.g., radar image141), preferably after radar image141has been smoothed using a Gaussian filter. While the Laplacian may conventionally be used to highlight regions of rapid intensity change in pixel brightness for the purpose of extracting edges, according to the method100, the Laplacian may be composed with a suitable Gaussian to transform the topography of the original image into a smoothed topography such that the road40pixels lie in valleys of low brightness (e.g., areas of low intensity) in relation to their immediate surroundings. It is also preferred that the Laplacian of Gaussian contribute to a cost factor when road40in original radar image141appears darker than the surrounding area, as is shown inFIG. 1.

A fourth factor in assigning cost may be adjacency to previously extracted road40. For example, the algorithm adds an increased cost to finding path30that may coincide with or closely parallel a portion of previously extracted path30.

A fifth cost factor may be proximity to edge39. Associating a cost factor with edges39of linear features (e.g., road40) may keep the path30from deviating off the road40. To manifest the presence of edge39, there are various well-known edge mask techniques that may be applied47to radar image141, such as a Nevatia-Babu edge mask and others as would be familiar to one of skill in the art.FIG. 7illustrates applying47edge39mask to radar image141. As shown inFIG. 35, edge39of road40appears white, while road40itself appears black. Field43shows practically no edges39and water41shows only slight edge39contours. Therefore, assigning a high cost to edge39helps to keep path30near the center of road40. Whether applying47the edge39mask to radar image141is preferred may depend on the resolution of the specific radar image141to be used. For lower resolution images where the two edges39of road40may not be distinct, it may not be beneficial to apply47the edge39mask. However, applying47the edge39mask was found to be beneficial in the case of the 1.25 meter resolution of radar image141as shown inFIG. 29.

In other embodiments, image-based logic may comprise using image data, including spatial relationships and relationships between pixels, to make at least one correlation in data related to the linear feature, possibly to prefer one correlation over another.

Depending on the resolution of radar image141, according to one embodiment it may be preferable for efficiency of road40extraction, but not required, to calculate the cost factors associated with the Laplacian of Gaussian, edge39proximities, and other cost factors as a pre-processing218step before beginning image-based road40extraction on radar image141. For example, the running time of algorithms of the method100scale roughly as the resolution squared, so calculations for a 3-meter resolution radar image141may proceed about five times faster than calculations for a 1.25-meter resolution radar image141. Thus, where using a higher resolution radar image141, the speed of extracting roads40may be substantially increased by calculating several of the cost factors in advance. In addition, the user may specify which cost factors to calculate in this pre-processing218step. For example, if it were determined that the edge39proximity cost factor should not be used, for example with a lower resolution radar image141, then the user may indicate that this cost factor is not to be computed as part of the pre-processing218. By way of example, cost factors associated with the Laplacian of Gaussian and edge39proximity were calculated prior to extracting road40from radar image141. The computer program that performed this operation comprises the following variables: input radar image141; an output cost function that assigns a cost to corresponding pixels; fftSize (Fast Fourier Transform size); scale of Laplacian of Gaussian; Gaussian size in meters of Laplacian of Gaussian; highest value of Laplacian of Gaussian; weight of edges39in cost function; and Gaussian size for smoothing11edges39. With the exception of fftSize, the previously-specified variables affect the determination of cost to be used in the least cost path algorithm, and preferably should be changed if any changes are desired in the cost function parameters. For example, if it were desired to eliminate edge39proximity as a cost factor, then the weight of edges cost function should be set to zero. By way of example, the fftSize was set to a default of fftSize=2048, which seemed to work well with computers of more than 1 gigabyte of memory. Reducing fftSize to 1024 or even smaller may be beneficial for computers with less memory. If these cost factors are calculated in advance, then cost file25should be entered27into the user interface after selecting22output vector file24as shown inFIG. 31.

Another embodiment of method100may comprise using the spectral mode for extracting at least one linear feature (e.g., road40) from radar image141. Like the track mode28, the spectral mode comprises using image-based logic to track path30between first anchor point32and second anchor point34selected52by the user. It may be beneficial to use the spectral mode where, in radar image141, the pixels of the road40between anchor points32,34are relatively uniform and similar in brightness to (i.e., spectrally similar to) the pixels associated with anchor points32,34. The image-based logic of the spectral mode may comprise a least cost path algorithm incorporated in software, such as Djikstra's algorithm or any other least cost algorithm known in the art. In the spectral mode, the cost factors used to determine the least cost path30between the user-selected52anchor points32,34may comprise spectral similarity to the user-selected52anchor points32,34; adjacency to previously extracted roads40; and cost of moving from one pixel to another (e.g., along path30).

For example, the least cost path algorithm adds an increased cost to finding path30that may coincide with or closely parallel a portion of a previously extracted path30.

Having selected26the track mode28, the user may now visually locate road40. Referring toFIG. 33, the user may select52a plurality of anchor points32,34associated with road40, anchor points32,34being tied to geographical locations in the raster data associated with radar image141. To designate anchor points32,34, the user may position the cursor on anchor point32, click on it once, drag the cursor to anchor point34, and double-click on anchor point34.

In a preferred embodiment of the method100, the anchor points32,34may define the constrained search region about consecutive anchor points32,34to confine path30connecting them. For example, ellipse48that has the anchor points32,34as its foci, is shown inFIG. 36. In a preferred embodiment, ellipse48comprises the search region, such that any intermediate point38generated for path30connecting anchor points32,34must occur within the area defined by the ellipse48. In a preferred embodiment, a purpose of the search region is to manage the tradeoff between search space size and computational speed.

According to the method100, once the user has selected52anchor points32,34, image-based logic embedded in the software may be employed to automatically create the vector set and connect the anchor points32,34via path30. Path30may include intermediate points38automatically generated in such location and in sufficient quantity to accurately reflect the character of road40. For instance, in the case of a curve in the road40, where the user selects52two anchor points32,34by clicking on them, the software may add intermediate points38in between the two anchor points32,34using image-based logic to create additional vectors in the vector set so that the least cost path30can be preferably substantially smooth and located substantially along near centerline of the road40, as shown inFIG. 33. It may be that path30contains no such intermediate points38. In addition, depending on the character of the road40to be extracted, the user may select52additional anchor points32a,34a, in between anchor points32,34, as explained in more detail below.

For optimal accuracy of road40extraction, a preferred embodiment of method100comprises using a strategy for locating anchor points32,34. Using the radar image141representation of road140, it is preferred that the user select52each anchor point132(A),134(C) by locating them in a road intersection42or a road terminal29(e.g., cul-de-sac), as shown inFIGS. 37 and 38. In addition, it is preferred that the user click on the road140instead of near the road140as shown on radar image141. Further, it may be beneficial for the user to extract primary streets first and then move to secondary streets. Additional anchor points32a,34ashould be placed in natural locations, such as bends and junctions. Anchor points32,34should be located no more than a maximum distance apart, depending on the character of the linear feature to be extracted. For instance, in the case of a straight road40, the maximum distance between anchor points32,34may be greater than in the case of a winding road40while still attaining accuracy in road40extraction. As shown inFIGS. 37 and 38, if only anchor points132(“A” inFIGS. 37 and 38) and134(“C” inFIGS. 37 and 38) were specified, then the generated path130would not properly extract road40between anchor points132and134. However, where additional anchor point132a(“B” inFIG. 28) is selected52, then the generated path130properly extracts road140.

In the case of a loop in the road40, the number of user specified points32,34,38required for accurate extraction of road40via path30may be a function of the loop shape. For example, as shown inFIG. 39, in the case of a U-shaped loop, selecting two anchor points232,234and additional anchor points232a,234amay allow path230to be defined. However,FIG. 40shows a tight loop with a severe bend. In that case, anchor points232(“A” inFIG. 40) and 234(“E” inFIG. 40), as well as three additional anchor points232a,234a(“B,” “C,” “D” inFIG. 40) may need to be specified to correctly determine path230.

In addition, a preferred embodiment of the method100may also comprise use of manual modes (e.g., without image-based logic) for extracting roads40so that the user has the option of switching between track mode28or spectral mode (e.g., both using image-based logic), or the manual modes—spline mode or digitize mode (e.g., neither using image-based logic). It may be beneficial to use the digitize mode to manually extract straight roads40. It may be beneficial to use the spline mode to manually extract large roads40with little curvature (e.g., highways).

A preferred embodiment of the method100comprises topology cleaning using the node and line snapping algorithm, anchor point snapping algorithm68, to snap new anchor points132,134to nearby path30that has already been extracted. The snapping takes place before the path30between new anchor points132,134is generated. When the user selects52new anchor points132,134, the anchor point snapping algorithm68may determine whether the anchor points132,134are within snap distance74of existing anchor point32,34or path30. The snap distance74may be a predetermined distance, preferably three pixels, as shown inFIG. 41, within which corrections to the road topology may be made. The anchor point snapping algorithm68may be disabled. If the new anchor points132,134are within the snap distance74of existing anchor point32,34or path30, the anchor point snapping algorithm68moves or “snaps” the new anchor points132,134to coincide with the existing anchor point32,34or path30as shown inFIG. 41.FIG. 41Aillustrates the result with respect to intersection42if the user fails to click precisely in the same place for each anchor point32,132.FIG. 41Billustrates the result when the anchor point snapping algorithm68is employed so that the anchor points32,132are properly joined.

Using76smoothing algorithm70“smoothes” the least cost path30between consecutive anchor points32,34, revising least cost path30to give it a smooth appearance, rather than what might have been a jagged appearance had smoothing not been used76. The various smoothing parameters are shown inFIG. 42. The user may choose to adjust the quad window parameter78. Increasing the quad window parameter78will cause extra smoothing to be applied to the path30.

The information regarding anchor points32,34, intermediate points38, vector set and path30may be stored in the output vector file24comprising a vector layer.

The user may review path30for other topological errors (e.g., deviations from the linear feature of interest in radar image141(e.g., road40)) and correct them manually to change the vector sets. Such review and correction may take place at any time, either immediately after the extraction or, after the extraction results (e.g., vector set, anchor points32,34, path30) have been stored in the output vector file24. The saved output vector file24may be later loaded into software and the corrections made at that time.

Once the output vector file24has been populated and saved, a map may be created from it automatically at any later time using known methods in the art (e.g., including tools in commercially available GIS software).

Various aspects of the method100of the present invention were tested for speed and accuracy. The method100was tested using Star-3i data associated with radar image141, such as shown inFIG. 29, as well as GeoSAR data associated with radar image314shown inFIG. 43. GeoSAR radar image314is 16-bit single-band (X) data from an aerial sensor with a spatial resolution of about 3 meters and little noise that was provided by the National Geospatial Intelligence Agency. The standard deviation of the data is around 15,000, so the data makes full use of the 16-bit dynamic range (comprising around 65,536 levels of brightness). Other radar image resolutions and dynamic ranges were also tested with good results.

For initial testing, two analysts (only one of whom had previously worked with radar imagery) extracted roads40from six radar images141,314both manually and according to an embodiment of method10(e.g., semi-automatically). Two of the test radar images141,314are shown inFIGS. 29 and 43. The analysts extracted the road40vectors manually or according to method100in opposite order to minimize the effects of learning the road40network. The tests were intended to measure accuracy, as well as extraction and edit time. As shown in Table 2 below, road40extraction according to method100(“Tracker” in Table 2) varied in time, sometimes taking longer than manual extraction. However, method100worked well in areas with many curved roads40which are laborious to extract manually. Method100also worked better on two lane roads40than it did on four-lane roads40.

Subsequent testing was performed by a research scientist with experience in radar imagery and prior art road extraction methods. Radar images141used were from the Star-3i sensor. Three of the radar images141were about 1.25-meter resolution; one of the radar images141had a resolution of about 2.5 meters. The scientist tracked each radar image141twice, once manually and once using a combination of automatic and manual tracking modes according to method100. To reduce bias caused by scene familiarity, the scientist extracted roads40from other scenes between two mappings of a single scene. Table 3 below shows the results. The method100of the present invention reduced tracking time on average, especially in the case of curved roads40.

Method200of the present invention may be used to extract linear features, such as road40, from any remotely sensed image, such as multispectral image14, radar image141, panchromatic image20or hyperspectral image15through a user interface. The user interface is a graphical user interface (GUI), that may be constructed from primitives supplied by commercially-available GIS software package, such as ERDAS IMAGINE® sold by Leica Geosystems Geospatial Imaging, LLC of Norcross, Ga.

Via the interface, the user may select220an input image of image type from among multispectral image14, radar image141, panchromatic image20or hyperspectral image15, which may have been pre-processed218(e.g., atmospherically corrected multispectral image14or hyperspectral image15, or a smoothed version of radar image141). Via the user interface, the selected220input image may be further pre-processed218to generate auxiliary raster images (e.g., texture file18from input panchromatic image20, cost file25from input radar image141) that may also be subsequently employed in practicing method200to enhance the accuracy or speed of subsequent road40extraction. Depending on the type of image selected220, preprocessing18may be preferred but not required.FIG. 45shows, for example, that selection220of input multispectral image14has occurred.

As suggested by the drop-down menu inFIG. 46, the user may now perform, for example, the pre-processing218operation of “Compute221atmospheric correction” against the input multispectral image14. Again, in relation to the drop-down menu inFIG. 46, if the selected input image had been panchromatic image20, then user may have performed the pre-processing218operation of “Compute223texture”, and if the selected input image had been radar image141, then the user may have performed the pre-processing218operation of “Compute225cost function.”

The images from which roads may be satisfactorily extracted by the present invention comprise characteristics described below. For example, multispectral image14may be produced by the IKONOS® satellite owned by GeoEye, Dulles, Va., or by the QuickBird satellite owned by DigitalGlobe®, Longmont, Colo. The multispectral image14produced by the IKONOS® satellite has a resolution of about 3.28 meters; the multispectral image14produced by the QuickBird satellite has a resolution of about 2.4 meters. Panchromatic image20may be from the IKONOS® satellite or the QuickBird satellite. Multispectral image14may be used alone or in conjunction with corresponding panchromatic image20. In the case of the IKONOS® satellite, panchromatic image20has a resolution of about 0.82 meters. In the case of the QuickBird satellite, panchromatic image20has a resolution of about 0.60 meters. Radar image141has a spatial resolution of about 1.25 meters with an 8-bit dynamic range (which may comprise about 256 levels of brightness) and may be produced using X-band interferometric SAR from the aerial Star-3i sensor owned by Intermap, Denver, Colo. Hyperspectral image15is produced by NASA's AVIRIS (Airborne Visible InfraRed Imaging Spectrometer) in224contiguous spectral bands with wavelengths from 400 to 2500 nm. Other remotely-sensed images not specifically described herein may also be used.

Once pre-processing218operations on the selected input image have been performed and the input image is displayed in the GUI, the user may select260the “Extract Roads” feature219, as shown inFIG. 46.

The method200may further comprise selecting22output vector file24. SeeFIG. 45. As set forth above, output vector file24may comprise the vector set, material type56and geometry46. When the output vector file is selected22, it may be empty or may contain information related to previously extracted roads40.

Depending on the image type of the selected220input image, a preferred embodiment of method200may comprise inputting16an additional auxiliary file, cost file25or texture file18, or multiple auxiliary files. The term “auxiliary file” may encompass any supplemental raster file provided as input for the method200of road40extraction. Thus, texture file18and cost file25may be considered auxiliary files. The texture file18may be generated223, or computed, as described above with respect to panchromatic image20. Inputting16texture file18(generated from panchromatic image20that corresponds to multispectral image14) is shown inFIG. 2. In the case of panchromatic image20, the auxiliary file may also be texture file18generated223during preprocessing218step. In the case of radar image141or hyperspectral image15, the auxiliary file may comprise cost file25computed225as a pre-processing step. Cost file25may comprise a radar imagery cost file, hyperspectral imagery cost file or any other cost file that may be associated with application of at least one least cost algorithm to the path30representing a linear feature. With respect to radar image141, entering27cost file25after selecting22output vector file24is shown inFIG. 31.

The method200may further comprise selecting an extraction mode, such as track mode28or spectral mode. Other modes, such as known modes for manual road extraction, may also be selected as part of method200. Manual modes, such as spline mode and digitize mode, are explained above. Thus, method200may comprise selecting26track mode28as shown inFIG. 47. Track mode28comprises using image-based logic to automatically calculate the path30associated with user-selected52anchor points32,34, to create a near centerline for road40. Use of track mode28in this manner with respect to multispectral image14and radar image141is explained above and is shown in FIGS.6and33-34.

By way of example, track mode28image-based logic may comprise a least cost path algorithm incorporated in software, such as Djikstra's algorithm or any other least cost path algorithm known in the art, as explained above. The least cost path algorithm of method200may construct the least cost path30between user-selected52anchor points32,34. The cost factors used in the least cost path algorithm of the present invention have been previously described in some detail. Because many different image types may be the subject of method200, the cost factors used in the method200may vary depending on the type of image selected. The path length factor and the adjacency to previously extracted roads factor may be used for all remotely-sensed images. The spectral road-likeness factor (computed from Tasseled Cap greenness) may be used for multispectral image14. The spectral road likeness cost factor may be used for hyperspectral image15. The textural road likeness factor (specified by the input16texture file18) may be used for panchromatic image20. Cost file25(comprising Laplacian of Gaussian and edge39proximity cost factors) may be used for radar image141.

The spectral mode has been previously described. As explained above, the spectral mode may be well suited for extracting road40from panchromatic image20when that road40exhibits poor image texture (i.e., exhibits high texture within panchromatic image20or its texture file18) as may occur with dirt roads, streets with overhanging vegetation, building shadows, vehicles on the road, and the like. Spectral mode may be well-suited to extracting road40from multispectral image14in conjunction with panchromatic image20when road40exhibits high texture in panchromatic image20or its texture file18. Spectral mode may be used for extracting road40from remotely-sensed imagery of the type discussed herein where it is desired that all points along path30(associated with road40) be spectrally similar to the user-selected52end anchor point32,34of path30,

The method200may further comprise activating262automatic vector revision functions embedded in software. These functions may comprise automatic topology cleaning (including automatic line and node snapping and automatic orthogonal crossroads), automatic corner point installation and automatic smoothing (which may include deep smoothing, as described below), all of which will be explained in more detail below. As previously explained above, topology cleaning removes gap82, dangle,84, as well as realizing the intended coincidence of path30terminals29. The automatic vector revision functions of the present invention comprise functions based on geometric relationships between and within paths30,230. Activating262these automatic vector revision functions may occur at any point in the method200. It may be preferred, although not required, for the user to activate262them early in the method200before actually beginning to select52anchor points32,34in the remotely-sensed image. If the automatic vector revision functions are activated262before selecting52endpoints32,34, automatic point snapping, automatic topology cleaning, automatic corner point installation and automatic smoothing may occur in real time, on the fly, to revise the newly extracted path230(corresponding to the extraction of road40), as well as previously extracted paths30,30ain the vicinity of path30. In another embodiment, all of the automatic vector revision functions may be activated262by default, requiring the user to deactivate any of the functions that are not desired at a particular time for subsequent extraction.

Activating262the automatic vector revision functions may comprise establishing264the snap distance74as shown inFIG. 47. Snap distance74may comprise line snap distance74aand node snap distance74b. As shown inFIG. 48, node snap distance74bmay be a predetermined distance from the end anchor point32of an existing path30, such that if the user specifies new end anchor point232for new path230that is about to be extracted, and that new end anchor point232is within node snap distance74bof end anchor point32of existing path30, then the new anchor point232will be automatically snapped to the end anchor point32of the existing path30by point snapping algorithm268prior to extraction of new path230. As shown inFIG. 49, line snap distance74amay be a predetermined distance from newly extracted path230, such that existing path30which terminates within the line snap distance74aof newly extracted path230is automatically revised (e.g., corrected) by the automatic topology cleaning function to terminate on the newly extracted path230. Additionally, line snap distance74amay be a predetermined distance from existing path30, such that if the user specifies new end anchor point232for new path230that is about to be extracted, and that new end anchor point232is within line snap distance74aof the existing path30, then the new anchor point232will be automatically snapped to the existing path30by point snapping algorithm268prior to extraction of new path230. SeeFIG. 49. In the case of method200, snap distance74(which the user interface may designate in units of image pixels) corresponding to 10 meters, as shown inFIG. 47, may be preferred, as yielding desirable behavior associated with the road40extraction. The user interface may designate snap distance74in units other than image pixels, such as units of meters. While it may be preferred that the line snap distance74aand the node snap distance74bbe set at the same distance, this is not required. Point snapping algorithm268may determine whether anchor points32,34and/or intermediate point38are within the snap distance74of existing anchor point32,34or of path30.

Activating automatic topology cleaning as one of the automatic vector revision functions may automatically resolve gap82, dangle84, as well as snapping anchor point32,232and path30to meet in intersection42, for example. As shown inFIG. 48, if new anchor point232is less than node snap distance74bof existing anchor point32, point snapping algorithm268snaps the new anchor point232to existing anchor point32.FIG. 48(a) shows the results of an extraction (based on mouse clicks at the displayed anchor points32,232) if automatic node snapping were deactivated.FIG. 48(b) shows the results of the extraction based on the same mouse clicks shown inFIG. 48(a) when automatic node snapping is activated—gap82is resolved. Had gap82been dangle84instead, that would have been resolved as well.FIG. 48(a) also shows snap region274displayed as a dotted-line disc, the center of which is anchor point232(in the same location as centerpoint275, in this example) and the radius of which is node snap distance74b. If two anchor points32,232are within snap distance74of one another, that does not necessarily mean that one point lies within disc-shaped snap region274about the other where the radius of snap region274is node snap distance74b; rather, it could mean that one anchor point32lies within snap region274of another shape (e.g., regular polygon) about the other point, where snap region274and its dimensions are determined by node snap distance74b. In another embodiment, the path30associated with existing anchor point32may also be automatically revised, or adjusted, with the addition of new path230inFIG. 48.

Similarly, as shown inFIG. 49, if new anchor point232is less than line snap distance74aof existing path30, then point snapping algorithm268snaps new anchor point232to meet existing path30.FIG. 49(a) shows the results of an extraction (based on mouse clicks at the displayed anchor point232) if automatic line snapping were deactivated.FIG. 49(b) shows the results of the extraction based on the same mouse-clicks as shown inFIG. 48(a) when automatic line snapping is activated—gap82is resolved. Had gap82been dangle84instead, that would have been resolved as well. InFIG. 48(a), centerpoint275of snap region274, whose radius is shown as node snap radius74b, is coincident with anchor point232; inFIG. 49(b) centerpoint275of snap region274, whose radius is line snap radius74a, is coincident with anchor point232. However, this coincidence of locations is not required; snap region274may be centered about other locations as would naturally occur to one of ordinary skill in the art after becoming familiar with the teachings of the present invention.

Activating automatic topology cleaning, one of the automatic vector revision functions, may also comprise establishing266maximum attachment radius73as shown inFIG. 50. The maximum attachment radius73comprises a distance (which may be designated in meters or another unit) that may define a region of influence273centered about centerpoint275, which may coincide with the end anchor point32of existing path30, as shown inFIG. 51. In a preferred embodiment, the region of influence273is a disc centered about centerpoint275, whose radius is maximum attachment radius73, as shown inFIG. 51. The region of influence273may be further described as the area within which a modification, or correction, to path30may be confined.FIG. 51shows the addition of new path230close to existing path30defined in part by anchor point32. Since anchor point32is within the line snap distance74aof new path230, automatic topology cleaning will cause the path30to be automatically rerouted to meet new path230at relocated anchor point32a. If it is desired that the automatic rerouting of path30meet path230at roughly a 90° angle, the path30would be revised as path30ain the manner shown inFIG. 51. Measures of distance other than meters may be used for the maximum attachment radius73. Again, in the embodiment illustrated inFIG. 51, centerpoint275of the region of influence273may coincide with anchor point32. However, this coincidence of locations is not required and may not occur in a different embodiment.

InFIGS. 48-49and51both the snap region274and the region of influence273are visually indicated as dotted-line circles for illustrative purposes. In one embodiment of method200, both the snap region274and region of influence273are mathematical constructs that may not explicitly appear to the user on a graphical display screen. Rather, the user may become familiar with the general confines of the snap region274and the region of influence273after experience gained through use of the method200. In that embodiment, the snap distance74and the maximum attachment radius73may be modified by entering different distances in the GUI text fields shown inFIGS. 47 and 50.

In another embodiment of the method200, the snap region274and/or region of influence273may be displayed graphically on the display screen. For example,FIG. 52shows a graphical representation of region of influence273as a translucent colored disc, although other graphical representations, such as a hollow circle, are possible. In one embodiment, the region of influence273and/or snap region274may be graphically displayed as region(s) centered at a cursor location that is specified manually through a motion-sensitive device comprising switches and means to move the cursor on the display screen, such as a mouse, track ball, or touch pad. In another embodiment, the respective associated maximum attachment radius73and/or the snap distance74may also be changed through the motion-sensitive device comprising switches and means to adjust the value of a numerical parameter, such as a mouse wheel, trackball, or touch pad, without having to manually enter maximum attachment radius73and/or the snap distance74in GUI text fields as shown inFIGS. 50 and 47. Another embodiment may include the ability to maintain continuous, real-time, updated graphical display of the region of influence273or snap region274in response to the user moving the region of influence's273centerpoint275continuously in real-time (e.g., by moving the cursor) over the display screen. Another embodiment may include the ability to maintain continuous, real-time, updated graphical display of an expanding or shrinking region of influence273(or snap region274) whose size may be changing in response to the user continuously adjusting the maximum attachment radius73(or, the snap distance74) via the motion-sensitive device (e.g., mouse wheel, track ball, touch pad). In yet another embodiment, the user may employ any features described in this paragraph when using the smart editing tools281described in more detail below.

Activating262the automatic vector revision functions may further comprise selecting one or more functions, such as automatic topology cleaning (including automatic line and node snapping and automatic orthogonal cross-roads), automatic corner installation, and various smoothing functions, as shown onFIG. 53. In another embodiment, all automatic vector revision functions may be selected (e.g., activated262) as a default, requiring the user in that case to deselect (i.e., deactivate) functionality that may not be desired for subsequent road40extraction. The user may activate262or deactivate some or all of the various automatic vector revision functions at any time.

Proceeding with the description of method200, once the user has selected26track mode28(or any other extraction mode described herein), the user visually locates road40in the remotely-sensed image under consideration, for example, multispectral image14. As described above and shown inFIG. 8, the user may select52anchor points32,34, associated with road40, anchor points32,34being tied to geographical location(s) in the raster data associated with multispectral image14. In one embodiment, when track mode28(or any other extraction mode) is selected26, the cursor shown in multispectral image14assumes a state (e.g., turns into a crosshair) indicating that the user may select52anchor points32,34. The user may then position the crosshair on the road40and single click with the mouse to establish anchor point32. With each successive single click, additional anchor point34is established, with the software automatically connecting anchor points32,34by a negative (e.g., reverse video) “rubber band” line. The user may choose multiple anchor points32,34by single clicking at various locations on road40. When the user desires to end the selecting52, the user may double click on the last selected anchor point34. The user may select52anchor points32,34using the motion-sensitive device or any device that would be obvious to one of ordinary skill in the art.

In the same manner as described above with respect to methods10,100, anchor points32,34may define ellipse48with the anchor points32,34as its foci. SeeFIGS. 9,36. Ellipse48comprises the search region such that intermediate point38generated for path30connecting anchor points32,34, as well as path30, occur within the area defined by the ellipse48.

According to method200, once the user has selected52at least anchor points32,34, image-based logic embedded in software may be employed to automatically create path30connecting anchor points32,34, and display path30on the display screen. Path30may include intermediate points38automatically generated in such locations and in sufficient quantity to accurately reflect the character of road40. Once the image-based logic has automatically created path30, as another step in method200, the image-based logic may also automatically attribute54material type56of road40to corresponding path30, as explained above with reference to methods10,100. Material type56may be indicated by marking the path30associated with road40in a color keyed to the particular material type56attributed54. The step of automatically attributing54material type56to the road40may be performed while using the track mode28or spectral mode, or other extraction mode.

Once the image-based logic embedded in the software has automatically created path30, as another step in method200, the image-based logic may also automatically attribute45geometry46associated with road40to the corresponding path30, as explained above with reference to methods10,100. The software may automatically associate material type56and geometry46with the vector sets associated with path30; material type56and geometry46may be stored as attributes of path30in output vector file24.

Once path30has been automatically created, according to the method200, the user may visually locate new road240in multispectral image14, for example. As described above and shown inFIG. 51the user may select52new anchor points232,234, associated with new road240. Image-based logic embedded in software may be employed to automatically connect anchor points232,234via new path230displayed to the display screen. Again, path230may include intermediate points38(not shown) automatically generated in such locations and in sufficient quantity to accurately reflect the character of road240. Once new path230has been automatically created, as previously described, the image-based logic may also automatically attribute54,45material type56and geometry46of the road240to path230.

In a preferred embodiment, while new path230may have been calculated mathematically, it may not be “drawn” on the display screen until after the automatic vector revision functions have automatically evaluated the geometric relationships between path30and new path230, and revised path30and/or new path230in accordance with application of one or more of the automatic vector revision functions.

In one embodiment, once the software has automatically revised the affected path30according to the automatic vector revision functions, as explained below, the length66of any path30affected by the insertion of new path230may be automatically reattributed245to the revised existing path30. In other embodiments of the method200, material type56or road width66may also be reattributed245to revised path30. Thus, the method200may comprise automatically reattributing245the material type56and geometry46associated with road40to revised path30.

After existing path30(affected by the insertion of new path230) has been revised and had its geometry reattributed245, the visual representation of new revised path30may appear along with that of new path230on the display screen. Once new path230appears on the display screen, the cursor returns to the state (e.g., cross-hairs) indicating that the user may resume selecting52new anchor points232,234.

The discussion of method200now turns to the manner in which the automatic vector revision functions operate and may be used. From the user's perspective, when activated262the software causes these automatic vector revision functions to be applied automatically, seamlessly, on-the-fly and in real time. What is displayed to the display screen may be the final result of the software having applied the activated automatic vector revision function to paths30,230without displaying intermediate results to the screen.

Method200may further comprise using the automatic topology cleaning function to automatically clean the topology of paths30,230based on the geometric relationship between paths30,230. Automatically cleaning the topology of the paths30,230may comprise using 267 an automatic point snapping tool, or point snapping algorithm268embedded in software, to automatically fix topological errors, such as gap82and dangle84.

FIG. 54illustrates functionality associated with using267point snapping algorithm268and automatic topology cleaning.FIG. 54(a) shows the results of a multi-point extraction (indicated in this case by a sequence of three user-selected anchor points232,232a,234(e.g., mouse-clicks left to right)) when this functionality is not activated. Dangle84is left on existing path30, and anchor point232a(associated with the middle mouse click) is not coincident to path30. Thus, three paths30,230,230ameet in the vicinity of the intersection42but are not coincident there.FIG. 54(b) shows the results of the same multi-point extraction using the same user-selected52anchor points232,232a,234(e.g., mouse clicks), but now with point snapping algorithm268and automatic topology cleaning activated. In one embodiment of the invention, the following sequence of processing steps occur: (1) path230is automatically constructed through the three anchor points232,232a,234corresponding to the mouse clicks; (2) if path30exhibits gap82or dangle84in relation to path230(e.g., anchor point32is within line snap distance74aof path230) then anchor point32of path30is automatically relocated to anchor point232aon path230and path30is automatically rerouted to the new anchor point232a; (3) if anchor point232a(corresponding to the middle mouse-click on path230) is within node snap distance74bof intersection42then anchor point232a(corresponding to the middle mouse-click on path230) is snapped to coincide with point232bat intersection42. The result is that the intersection42is resolved cleanly—all paths30,230,230bthat terminate in the vicinity of the intersection42terminate at a common anchor point232b.FIG. 54(c) shows additional capability associated with activation of point snapping algorithm268and automatic topology cleaning. Here a multi-point extraction is shown, consisting in this case of five user-selected52anchor points (e.g., mouse-clicks). The last mouse click in the sequence (e.g., anchor point232a) is automatically detected to be within line snap distance74aof an initially extracted path230passing through all the anchor points232,232b,232c,232d. In this case, anchor point232a(associated with the last mouse-click) is snapped to the self-intersection42point of path230. Other embodiments may exhibit other automatic behaviors that are similar to those described in this paragraph as would naturally occur to one familiar in the art.

Automatically cleaning the topology of existing paths30,30a,30bin relation to new path230may comprise revising paths30,30a,30bso that they not only terminate on new path230, but also meet new path230to form 90-degree “T” intersections42, for example, as shown inFIG. 55. Therefore, using the automatic orthogonal crossroads function may comprise using277orthogonal crossroads algorithm276, described below. Using277orthogonal crossroads algorithm276, together with automatic topology cleaning, establishes revised paths30,30a,30bas paths30,30a,30bthat terminate on path230while maintaining locally orthogonal relationships with new path230. See alsoFIG. 51(also showing establishing orthogonal crossroads).

In method200, the orthogonal crossroads algorithm276may automatically proceed through the following basic steps. SeeFIG. 51. (1) Find the point where the boundary of the region of influence273centered about anchor point32of path30cuts the interior of path30(here, point31); (2) find point32a(to become the new location of anchor point32) on the new path230that is closest to point31; (3) replace the portion of path30that goes from point31to anchor point32with a cubic spline from point31to relocated anchor point32awhere the spline preserves the tangent direction of path30at point31, and assumes a tangent direction orthogonal to path230at anchor point32a. Using277orthogonal crossroads algorithm276results in revising path30so that it terminates orthogonally on new path230.

The automatic vector revision functions of method200may comprise an automatic deep smoothing function, or tool, that may automatically apply at least one extra layer of smoothing to newly extracted path30(before display to the display screen) in addition to smoothing supplied as part of method100. An objective of the automatic deep smoothing tool is to substantially smooth out certain undesirable artifacts in path30that may have been introduced in earlier phases of the extraction process, such as (1) small-wavelength wiggles in the path30that may not reflect a “true” (visual) centerline of road40, and (2) small-amplitude wiggles in near-linear portions of path30. For example, without automatic deep smoothing being activated prior to extraction, the path30displayed to the screen between anchor points32,34may exhibit small-wavelength wiggles, or small-amplitude wiggles in near-linear portions, as shown inFIG. 56(a) and (c). However, with automatic deep smoothing activated prior to extraction, path430displayed to the screen between anchor points32,34is shown inFIG. 56(b) and (d) and appears considerably smoother than that shown inFIG. 56(a) and (c). Method200may comprise automatically deep smoothing path30based on the geometric relationships within an earlier realization of path30during extraction. Automatically deep smoothing path30may comprise using269deep smoothing algorithm270, which may be automatically applied, for example, to the least cost path30, after the path30has been automatically quadratically-smoothed via quad window parameter78in accordance with smoothing algorithm70, resulting in quadratically-smoothed path30. Deep smoothing algorithm270may then proceed through the following steps automatically: (1) Compute a curvature profile for the quadratically-smoothed path, using a sliding nunchuka-like template comprising two fixed length “handles” with a flexible fixed-length “chain” in between. The fixed-length “handles” may represent the least squares line fit to the quadratically-smoothed path, while the flexible fixed-length “chain” may represent a fixed-length arc of the quadratically-smoothed path between the “handles.” (2) Compute critical points (e.g., local curvature inflections, maxima, minima) of the curvature profile. (3) Remove sub-paths of the quadratically-smoothed path that lie between nearby inflection points (while preserving the inflection points themselves), except do not remove sub-paths that correspond to true bends in road40. Deep smoothing algorithm270automatically determines true road bends as follows: If P represents the quadratically-smoothed path and S represents one sub-path of quadratically-smoothed path P between two nearby inflection points of P, the perform least squares line fit to each of the two components of P-S. If the two line fits subtend a sufficiently small angle between them, sub-path S is deemed a true road bend, in which case, S is not removed from the quadratically-smoothed path P. (4) Use cubic spline(s) (with appropriately defined tangents) to interpolate through removed portions of quadratically-smoothed path, resulting in a first revised path, Q. The inserted splines remove small wavelength wiggles in the quadratically-smoothed path, P, by taking a more direct route through the inflection points of quadratically-smoothed path P. (5) Compute the curvature profile for the first revised path, Q. Decompose the first revised path Q into a plurality of sub-paths and classify each sub-path by curvature (high, medium or low). Fit each segment with an active contour, or “snake,” whose bend parameter is specially tuned to that sub-path's curvature class. Concatenate the snakes resulting in a second revised path, R. (6) Perform long least squares line fits to maximal sub-paths of second revised path R, as would be familiar to one of ordinary skill in the art, thereby removing small-amplitude wiggles from near-linear portions of the second revised path R, resulting in a third revised path, W. (7) Fit the third revised path W with the snake of low bend parameter (high flexibility), thus achieving an additional degree of smoothing and resulting in deep smoothed path430.

FIG. 56shows the result of the automatic deep smoothing function, using269deep smoothing algorithm270.FIG. 56(a) and (c) show how the path30actually appears after using267smoothing algorithm70, but prior to using269deep smoothing algorithm270.FIG. 56(b) and (d) show how the deep smoothing algorithm270revises path30, resulting in deep smoothed path430. In one embodiment of method200, if automatic deep smoothing is activated262by the user prior to extraction of path30, the user never sees the visual representation of path30prior to deep smoothing. Rather, in that case, the user only sees the end result—deep smoothed path430.

The automatic vector revision functions of method200may comprise an automatic corner installation278function. The automatic corner installation278function may revise path30by automatically introducing corner points61in path30. In one embodiment, the number and location of corner points61depends on the geometric relationships between or within paths30,230. When activated, using279the automatic corner installation278function may result in the automatic installation of corner point61in new path230that is displayed on the display screen (seeFIGS. 57,58and59). In one embodiment, such as is shown inFIG. 59, the automatic corner installation278function may partition new path230at corner point(s)61, resulting in a plurality of tandem paths230a,230balong path230. The geometry46and material type56are attributed45,54automatically to paths230a,230b. The automatic corner installation278function may comprise point snapping functions, as explained herein.

FIG. 57(a) shows the visual representation of a multi-point extraction (in this case, three user-selected52anchor points32,32a,34) when automatic corner installation278is previously deactivated by the user. Of interest in this example is the user's mouse-click placement of anchor point32anear what should be a corner in the resulting path30at intersection42.FIG. 57(b) shows the visual representation resulting from the same set of user mouse clicks when using279automatic corner installation278function, previously activated262by the user. Corner point61is automatically installed in resulting path230at intersection42. In addition, anchor point32a, because of its proximity to auto-installed corner point61, was automatically relocated by the automatic corner point installation278function to coincide with corner point61. Additionally, the automatic corner installation278function may partition path230at auto-installed corner point61, resulting in two tandem paths230a,230bthat are each automatically attributed45,54their respective geometries46and material type56. Automatic corner installation278would operate in similar fashion in a multi-point extraction that involved multiple corners, instead of one corner as shown inFIG. 57.

FIG. 58illustrates using279automatic corner installation278to automatically install three corner points61, based on two user-identified anchor points32,34. In addition, automatic corner installation278may automatically partition the path30at the automatically installed corner points61, resulting in a plurality of tandem paths30,30a,30b,30cthat are each automatically attributed45,54their respective geometries46and material type56.

FIG. 59shows that using279automatic corner installation278may cause each installed corner point61aon new path230to be snapped to nearby existing corner point61or existing terminal29, should such corner point61be in the vicinity as measured with respect to node snap distance74b.FIG. 59illustrates this snapping for one newly installed corner point61aand one existing corner point61.

The method200may further comprise using281semi-automated, vector-based, real-time smart editing tools280embedded in software, in conjunction with interactive user review, to revise paths30,230. As such, the smart editing tools280revise, or “correct,” paths30,230and their associated anchor points32,34by exploiting geometric relationships between and/or within paths30,230. Therefore, implementation of the smart editing tools280may include aspects of the various algorithms set forth above, separately or in combination. Because the smart editing tools280are vector-based, they may be applied to any path30,230(e.g., vector set) associated with a graphical image or raster image, where path30,230may or may not be associated with road40,240. In an embodiment of the method200acting on such raster imagery, the definition of “linear feature” may be expanded to include any feature captured in raster imagery such that the pixels of the feature lie within a neighborhood distance of a polygonal line, where the neighborhood distance is small by comparison to the total length of the polygonal line. Unlike existing low-level vector based GIS editing tools of the prior art, the smart editing tools280of the present invention do not require the user to relocate individual vectors one at a time. Thus, using281smart editing tools280may comprise applying one or two mouse-clicks to accomplish the same editing function that would have required many individual edit operations under prior art GIS methods.

In method200, the behavior of the smart editing tools280may be influenced by the snap distance74(comprising line snap distance74aand node snap distance74b) and the maximum attachment radius73. Therefore, using281smart editing tools280may comprise establishing264,266snap distance74and maximum attachment radius73.

The smart editing tools280of the present invention may also be used in conjunction with the automatic vector revision tools described above, provided the user has activated262the automatic vector revision tools.

In an embodiment, when at least one path30already exists, the user may identify285an error287in paths30,230, associated with extracted road40,240. Error287may comprise missed corner point61, missed near centerline, misplaced junction (e.g., anchor point32,34) incident to a plurality of paths30,230, undesirable small-wavelength wiggles or small-amplitude wiggles in path30,230, and inaccurate relationships between paths30,230associated with tandem roads40,240. In another embodiment, the user may use the graphically displayed region of influence273and associated motion-sensitive device (e.g., mouse, mouse wheel, track ball) (explained above) to assist with editing paths30,230. In yet another embodiment, the user may use the motion-sensitive device (e.g., mouse) to drag the center of the region of influence273(causing the whole region of influence273to follow continuously) to a desired location, or use the motion-sensitive device (e.g., mouse wheel) to continuously vary the maximum attachment radius73or dimensions of the region of influence273(as explained above), to highlight a region within which a given editorial modification to at least one path30may be confined.

Having identified285the error287, the user may select283the smart editing tool280appropriate to correct the error287. Thus, using281smart editing tools280may comprise selecting283at least one smart editing tool280, as shown inFIG. 50. Smart editing tools280of the present invention may comprise a corner/break installation284tool, a 1-point detour286tool, an N-point detour288tool, a move terminals290tool, a smooth292tool, a fuse294tool and a straighten295tool. In one embodiment of the method200only one smart editing tool280may be selected283at a time. However, in other embodiments combinations of specific smart editing tools280or even all the smart editing tools280may be selected283. In still other embodiments, the individual smart editing tools280may comprise various functional options, enabling the user to select283a desired subset from among the functional options for at least one of the smart editing tools280.

In an embodiment where (1) the automatic corner installation278function was not selected or was deactivated, or (2) the automatic corner installation278function was activated but nevertheless failed to install corner point61, as desired, then, as shown inFIG. 60(a), the automatically-extracted path30skirts intersection42and fails to install corner point61at that location. Visually identifying285this error287, the user may select283corner/break installation284tool as the desired smart editing tool280to effect an edit operation. The user may then click in the intersection42to place anchor point232there. The corner/break installation284tool automatically reroutes the path30through anchor point232, modifying path30within the region of influence273centered about anchor point232to generate new path230, as shown inFIG. 60(b). In one embodiment, the corner/break installation284tool may also automatically partition new path230at anchor point232, thereby dividing new path230into tandem paths230,230a,230b, which are automatically and separately attributed45,54. The paths230,230a,230bmay be automatically attributed45,54the same material type56and width66as original path30. In another example, shown inFIG. 61, if the user-selected52anchor point232lies within node snap distance74bof road terminal29or existing corner, then the installed corner point61may be snapped to the existing road terminal29or existing corner.

Where the automatically generated path30may be deemed by the user to be unacceptably far from the true centerline of the road40, the user may select283the 1-point detour286tool as the desired smart editing tool280to effect the edit operation.FIGS. 62 and 63illustrate operation of the 1-point detour286tool. As shown inFIG. 62, the user may mouse-click in the general vicinity of path30, preferably on the centerline of road40, to place anchor point232at that location. The 1-point detour286tool automatically reroutes the path30through anchor point232, modifying path30within the confines of the region of influence273centered about the new anchor point232. In a preferred embodiment, the region of influence273is a disc whose radius is the maximum attachment radius73. The 1-point detour286tool to then generates smooth new path230, as shown inFIG. 62. New path230preserves the original locations of the end anchor points32,34of the path30. New path230now smoothly approximates the centerline of road40. The length64of path230may be automatically reattributed245. In another embodiment, the width66of path230may also be reattributed245. In a preferred embodiment, where the path30is very curvy, the maximum attachment radius73may be beneficially established266as 15 m prior to the 1-point detour smart edit operation; where the path30is not very curvy, the maximum attachment radius73may be beneficially established266as 30 m prior to the 1-point detour smart edit operation. As shown inFIG. 63, if the user locates anchor point232in the vicinity of two tandem paths30,30asuch that the region of influence273centered about anchor point232overlaps both paths30,30a, then the 1-point detour286tool automatically reroutes the two paths30,30aas if they were fused together as one, to create new path230. New path230may then be automatically partitioned at a point along its trajectory that has a natural relationship to the original point where tandem paths30,30amet each other. This results in two revised tandem paths30,30athat may be reattributed245automatically and separately.

If at intersection42(e.g., a “T” intersection or “+” intersection, such as shown inFIG. 64) two or more paths30,30aare incident to one another, and the user places an anchor point232such that the region of influence273centered at the anchor point232overlaps two or more of these paths30,30a,30b, then there could be potential confusion as to which path30,30ais to be primarily affected by the 1-point detour286tool. This may result in 1-point detour286not being applied to the desired path, or at least not in the desired way. In an embodiment, the issue may be resolved as follows. First, the user selects the desired path30aor desired pair of tandem paths30a,30bto be primarily affected, the selected paths30a,30bbeing involved in the intersection42. The user then applies the 1-point detour286tool, which automatically knows to apply itself to the selected paths30a,30b.

Further, if paths30,30ameet in tandem, then even if paths30,30aare not selected by the user, the combined path30,30amay be edited seamlessly via one or more applications of 1-point detour286tool, under the assumption that other paths230are not in the vicinity to cause confusion as to which path30,30a,230the 1-point detour286tool is to be applied. In another embodiment, if paths30,30bare not selected by the user and meet smoothly in tandem (not creating a sharp angle between them) at intersection42that involves other paths230, the combined path30,30amay still be edited seamlessly through the intersection42via consecutive use of the 1-point detour286tool, as long as the region of influence273associated with the first 1-point detour286tool in the sequence overlaps path30and no other path30a, thereby establishing path30as the first path in the sequence to be edited by 1-point detour286tool. The embodiment may be easily performed because, as successive mouse-clicks associated with successive applications of 1-point detour286tool transition from the vicinity of path30to the vicinity of path30a, the software automatically remembers that path30was the previous path30to which 1-point detour286function was applied, and the software automatically recognizes that path30ais the unique path at intersection42that is smoothly tandem to path30.

In a case where the user deems path30to be unacceptably far from the true centerline of the road40, the user may select283the N-point detour288tool as the desired tool to effect the editing operation. The user may place at least two anchor points (inFIG. 65, shown as three anchor points232,232aand234) by clicking on desired locations. The anchor points232,232a,234should be placed on road40(to obtain desired path230), such that the regions of influence273,273acentered about first and last anchor points232,234both overlap path30. The N-point detour288tool automatically reroutes path30through the anchor points232,232aand234to generate new path230, as shown inFIG. 65. The rerouting of path30does not modify path30outside the regions of influence273,273acentered about the first and last anchor points232,234, except for the portion of path30that spans the two regions of influence273,273a. New path230preserves the original locations of end anchor points32,34of the path30. The length64of path230is automatically reattributed245. In another embodiment, the width of path230may also be reattributed245. If the user selects two anchor points232,234for application of N-point detour288operation, then the portion of new path230that spans the two anchor points232,234may simply be a straight line, and the path230may not be smooth at those two anchor points232,234(in other words, an angle in path230may appear at one or both anchor points232,234). In another embodiment, the N-point detour288tool may be applied to two tandem paths30,30a, where the first user-selected52anchor point32in the N-point detour288operation is in the vicinity of path30and the last user-selected52anchor point32ain the N-point detour288operation is in the vicinity of path30a. In that case, the tandem configuration of path30and30ais treated by the N-point detour288operation as a single path, resulting in a rerouted new path230that is then automatically partitioned at a point along its trajectory that has a natural relationship to the tandem point where path30and path30ahad met. This results in two revised tandem paths30,30athat may be reattributed245automatically and separately.

Where the user concludes that the terminating anchor point(s)32,32a,34,34aof at least one path30need to be moved to a single collective new anchor point location232, the user may use281the move terminals290tool as the desired smart editing tool280to effect the edit operation. As shown inFIG. 66, the user may perform a mouse-click to specify new anchor point232at a desired location (e.g., center of intersection42), such that the region of influence273centered at the new anchor point232contains at least one terminating anchor point32,32a,34,34aof existing paths30,30a,30b,30c. The move terminals290tool automatically reroutes paths30,30a,30b,30cthat terminate within the region of influence273centered about the new anchor point232, smoothly rerouting them so that the resulting new paths230,230a,230b,230cterminate at the new anchor point232. The lengths66of new paths230,230a,230b,230care reattributed245.FIG. 67illustrates application of the move terminals290tool to a T or +intersection42where the valence of the intersection42(3 for T, 4 for +) is one greater than the number of existing paths terminating in the intersection42(e.g., path30involved in the intersection42passes though the intersection42, while paths30a,30bmore or less terminate there). In these cases, if the user places a mouse-click such that the region of influence273centered at the mouse-click contains at least one terminating anchor point32for at least one existing path30a, and additionally the mouse-click is within line snap distance74aof path30, then the mouse-click location is snapped to path30, yielding the location of new anchor point232on path30to which the other paths30a,30binvolved in the intersection42are rerouted. New anchor point232becomes the new terminating anchor point for the rerouted paths30a,30b. As before, paths30a,30bare rerouted within the confines of the region of influence273centered at the user mouse-click, and their geometry46may be reattributed245. If the mouse-click is not within line snap distance74aof path30,30aas has occurred inFIG. 68, then the new anchor point232is placed at the mouse-click location itself, and path30b(not including path30,30a) involved in the intersection42is rerouted to terminate at the new anchor point232. In another embodiment of method200, the user may also select a subset of possible paths30,30a,30bfor application of the move terminals290operation, to restrict the paths that would be rerouted as a result. If multiple paths30,30a,30bmet at common anchor point32, and the user wanted to move the terminal anchor point32aof only one of the involved paths30,30a,30bso that it terminated at a desired mouse-click location, then the user may first select the desired path30a, and then when the move terminals290tool is applied, the software would automatically know to apply it only to path30a.

Using269automatic deep smoothing algorithm270to smooth path30automatically on-the-fly while road40is being extracted has been described above. However, in similar fashion, the deep smoothing algorithm270, or aspects thereof, may also be used281as the smooth292smart editing tool280. If, for example, the user (1) through manual or semi-automatic editing creates undesired small-wavelength or small amplitude wiggles in path30or (2) identifies path30as containing undesired small-wavelength wiggles or small amplitude wiggles, the user may select path30and then select283the smooth292smart editing tool280. This may invoke the vector-based deep smoothing algorithm270or relevant aspects thereof, to automatically smooth path30, generating new path230, as illustrated inFIG. 69. In another embodiment, illustrated inFIG. 70, the user may select283the smooth292smart editing tool280to smooth a plurality of tandem paths30,30a,230. In that embodiment, the user may first select the desired paths30,30a,230in any order and then select283the smooth292smart editing tool280. The smooth292smart editing tool280may automatically (1) explicitly or notionally concatenate paths30,30a, into super path330, (2) smooth super path330, for example, using deep smoothing algorithm270on superpath330in the manner previously described, and (3) explicitly or notionally repartition super path330into a sequence of tandem paths whose number is the same as the number of originally selected paths30,30a,230. The lengths66of the resulting tandem paths comprising super path330are reattributed245. In another embodiment, their widths64may also be reattributed245.

In yet another embodiment of method200, the user may wish to fuse multiple paths30,30a,30b,230,230a,230binto concatenated super path330. The user may select283the fuse294smart editing tool280to effect the edit operation As shown inFIG. 71, the user may select desired tandem paths30,30a,30b,230,230a,230bin any order. Then the user may select283the fuse294tool. Paths30,30a,30b,230,230a,230bare automatically concatenated into super path330, while unnecessary anchor points32a,32b,232a, and232bare removed. Material type56and geometry46are attributed54,45anew. In one embodiment, the width66attributed45to super path330may be a length weighted average of the road widths66of paths30,30a,30b,230,230a,230b. The material type56attributed54may be the material type56of the longest of paths30,30a,30b,230,230a,230b, or may be based on a length-weighted voting scheme among paths30,30a,30b,230,230a,230b, or may be based on such other natural scheme as would occur to one of ordinary skill in the art. The length64attributed45to superpath330may be the sum of the lengths64of paths30,30a,30b,230,230a,230b.

In yet another embodiment of method200, the user may wish to straighten extracted path30by using281the straighten295tool to effect the edit operation. SeeFIG. 50. In one embodiment, if road40is roughly straight, but extracted path30contains wiggles, applying the straighten tool will erase existing path30and redraw path30as a straight line between endpoints32,34.

User identification285of error287, user selection283of the smart editing tool280as appropriate for the error287, and application of that selected tool may take place at any time, either immediately after the extraction, after additional extractions or, after the extraction results have been stored in the output vector file24as described herein. The saved output vector file24may be later loaded and the corrections made at that time. After the error287has been addressed using281at least one of the smart editing tools280, the visual changes that appear on the display screen resulting from the last application of the selected smart editing tool280may be fully undone291(e.g., with a single press of an “undo”291pushbutton on the user interface) if the user concludes that the error287was not adequately corrected. If the automatic topology cleaning has been activated during the smart editing operation, the visual changes appearing on the display screen may also be fully undone291at the same time as the last application of the selected smart editing tool280as explained above.

The information regarding path30, such as path30geometry (e.g., the positions of the vectors and vector set(s) comprising the path30), length66, width64and material type56of the path30may be stored in the output vector file24.

Once the output vector file24has been populated and saved, at least one map may be created from it automatically at any later time using known methods in the art (e.g., including tools in commercially available GIS software).

Method200may also comprise preprocessing218remotely-sensed imagery. Preprocessing218may vary as a function of image type, as described herein. To begin preprocessing218as shown inFIG. 45, the user may select the preprocessing218algorithm associated with the remotely-sensed image being used. Preprocessing218may comprise computing221atmospheric correction to multispectral image14or hyperspectral image15, generating223texture file18for panchromatic image20, or computing225cost file25for radar image141. In another embodiment, preprocessing218may comprise computing at least one graphical image file or raster image file based on the image input file(s) such that the computed graphical or raster image files may be subsequently employed to assist in road40extraction. In another embodiment, the user may choose to have the software run the preprocessing218automatically in the background during the course of extracting path30.

Preferably, with respect to multispectral image14, preprocessing218may comprise computing221atmospheric correction, including normalization of solar effects, in accordance with methods that would be familiar to one of ordinary skill in the art. Further, computing221atmospheric correction of multispectral image14may comprise generating a solar elevation level and a mask layer. The solar elevation angle may be used to normalize brightness across pixels. The mask layer contains classification information that may be used to mask input multispectral image14during histogram250generation251. It may be preferable to generate251histogram250of non-water pixels, since road extraction40may be concerned primarily with non-water pixels. Thus, computing221atmospheric correction may comprise removing water pixels, because the atmospheric levels from some spectral bands may be lower over water pixels than non-water pixels. In the method200, the following classification for the mask layer may be used, as may any other classification as would be familiar to one of ordinary skill in the art after becoming familiar with the invention described herein (the numbers merely represent a class indexing):0=good pixel1=water pixel2=raw bright pixel3=water and brightness temperature record (BTR) (inconsistent)4=expanded region near a bright pixel 5=invalid pixel (input values are zero)

In another embodiment, the NUM ANGLES may be set at a value higher than 16, which may better indicate the texture of panchromatic image20, but at the expense of processing time.

Preprocessing218of radar image141may comprise two steps—smoothing11and computing225cost file25. Smoothing11radar image141has been explained above. Smoothing11radar image141may further comprise despeckling radar image141. As explained above, radar image141may be filtered to reduce noise and artifacts. Next, reduced-resolution radar image141may be automatically produced by setting X and Y scale factors to achieve degraded pixel size of about 1-2 m. A Lee-Sigma speckle suppression filter may be applied to radar image141. It may be preferred that the Coefficient of Variation is 0.2 and the Coefficient of Variation Multiplier is 2.0.

As in the case of multispectral image14, generating251histogram250may comprising removing water pixels. Removing water pixels may comprise identifying water pixels by setting as a threshold the band having a value of 124.FIG. 72illustrates the mask (detecting water pixels) obtained by using the band having a value of 100 (which is below the threshold value of 124). Other than the band and threshold values, generating mask layer for hyperspectral image15may follow the same method as that used to generate251histogram250for multispectral image14.

Computing225cost file25for hyperspectral image15may further comprise smoothing histogram250.FIG. 73illustrates the need for smoothing in the case of hyperspectral image15produced by AVIRIS, which may have been subjected to decommutation, interpolation and radiometric scaling for calibration.FIG. 73(a) shows a section of the band with the value of 124, illustrating periodic behavior with a cycle of about 2.5 counts.FIG. 73(b) shows histogram250period versus wavelength index, using a logarithmic scale, with a break at about 97 wavelength index.

In the case of hyperspectral image15, computing225cost file25may comprise computing221atmospheric correction. Atmospheric correction levels may be estimated by analyzing the base of the smoothed histogram250. The atmospheric correction level may be estimated as the smallest data value such that at least five histogram250bins in a row are above 10. This may eliminate spurious artifacts. (e.g., data dropouts, sensor undershoots, etc.). Then, the atmospheric correction level may be removed from the raw data value, ri, to get the corrected value, ci, such that ci=ri−ai.

In a preferred embodiment of the method200, a fixed band-dependent data normalization is performed once the atmospheric correction has been computed221. For convenience the output data type may be maintained as unsigned 16 bit. Statistics are generated over a number of datasets. Using a single data set as an example, after computing

Ai=average atmospheric correct for band i

Mi=data max for band i

Di=data median for band i,

compute band dependent constant gain factor, G, where
G=32767*Min{(Di−Ai)/(Mi−Ai)} over i.
Then, apply band-dependent constant factor, G, to get the new value si, where
si=G*ci/(Mi−Ai), i=1, . . . .n.
This normalization method may be used to maintain comparable data levels over the spectrum of hyperspectral image15.FIG. 74shows a spectral trace of raw hyperspectral image15at one pixel with high albedo after normalization in the manner described herein.FIG. 75shows normalizing quantity: Di−Ai, with bin smoothing applied.

Various aspects of the method200of the present invention were tested for speed and accuracy on multispectral image14, panchromatic image20and radar image141.FIGS. 76-81show the images tested, where for each image in the test, extraction was performed in two different ways (a) semi-automated extraction via method200(using automatic vector revision functions and semi-automated smart editing tools280discussed earlier) versus (b) manual extraction as explained in more detail below.

For the images shown inFIGS. 76-81, the analyst was instructed to extract all roads40in a designated area of interest (AOI) enclosing typical suburban landscape that included curved and straight roads, overhanging trees, and cars on the streets. For each AOI for each image, the analyst kept track of how long it took to extract the roads40manually versus semi-automatically according to method200(shown as “Tracker” in Tables 4 and 5). Manual extraction refers to just the use of the digitize and spline modes (without use of automatic vector revision functions) together with just the vector editing tools available in the ERDAS Imagine commercially-available GIS software. Semi-automatic extraction of method200comprised digitize, spline, track28, and spectral modes, plus the automatic vector revision functions and semi-automatic smart editing tools280of method200. The accuracy standard for near centerline road40extraction was left to the discretion of the analyst who was instructed to keep panchromatic image20path(s)) to within roughly two meters pixels of the and multispectral image14paths to within one meter of the true road40centerline using available editing tools, as necessary. The primary goal of the testing was to quantify for each image type the total extraction time that was achieved by using semi-automatic extraction in accordance with method200as compared to that for manual extraction. The semi-automatic extraction according to method200was always performed first to give a slight bias in favor of manual extraction time, thereby providing a conservative comparison of the two methods. Such bias results from increased familiarity of the image to the analyst. Before any testing began, the analyst practiced using the automatic vector revision functions and the smart editing tools280of method200to become familiar with the operation of the method200.

Table 4 demonstrates that, by using method200, extraction time can be reduced by a factor of about 1.7 for all types of unclassified remotely-sensed image data, as compared to manual extraction time. Table 5 demonstrates that, by using method200, extraction time can be reduced by a factor of about 1.7 for classified panchromatic image20data, and 1.3 for classified radar image141data, as compared to manual extraction time. In addition to speeding extraction time, analysts reported that use of method200also reduced stress and fatigue. Unlike the reporting in Tables 1 and 2 above, the reporting of extraction time in Tables 4 and 5 is no longer divided into initial extraction time and editing time because method200makes it easier for the user to interweave initial road40extraction with path30editing, rather than performing path editing after all the roads40have been initially extracted.

Testing of panchromatic data included original panchromatic image20, as well as its auxiliary derived texture file18. Testing of multispectral data included multispectral image14, as well as the texture file18of the associated panchromatic image20. Testing of radar included radar image141and the associated auxiliary file comprising radar cost file25. Table 4 shows results for unclassified imagery.

Tests were conducted in the same manner on classified panchromatic image20and classified radar image141data provided by NGA. Results are shown in Table 5.

In yet another embodiment of the present invention, method300comprises semi-automated vector-based editing tools and methods embedded in software for correcting errors in vector sets associated with previously extracted linear features of remotely-sensed imagery, regardless of the manner in which those linear features were previously extracted. A number of these editing tools embody in a single edit operation what would normally require multiple edit operations in prior art methods. As in method200, method300may be performed with respect to multispectral image14, hyperspectral image15, panchromatic image20and radar image141. Method300can be used to review and revise vector sets (e.g. path30) associated with linear features previously extracted from remotely-sensed imagery using any known method, whether manual, automatic or semi-automatic. Unlike prior art methods, method300and its associated GUI with real-time, smooth-motion animation graphics affords the user the ability to continuously preview proposed edits to vector sets, including automatic topology cleaning, in real-time and on-the-fly, before the user accepts the edits. Prior art methods, by comparison, experience at least one of the following two weaknesses: (a) multiple edit operations are required to achieve the same effect as a single edit operation in method300; (b) no preview capability is provided for edit operations, so that if the user decides an already-applied edit is unacceptable, the user must either “undo” the edit, or apply additional edit operations as “touch-up” to remedy the deficiencies of the first edit operation. Method300of the present invention may be used to efficiently increase the cartographic accuracy of previously extracted vector sets which may have been developed in accord with a lower standard of cartographic accuracy. In addition, as remotely-sensed landscapes evolve in time under natural and human influences, method300of the present invention may be used to efficiently update previous extractions where, in newer imagery, road40, for example, has been rerouted, extended, or retracted.

Method300will now be described according to the embodiments disclosed herein. Paths30may be rendered in the graphical display as thin lines, or as ribbons, each ribbon having width66corresponding to the actual width of the linear feature (e.g., road40). However, the present invention should not be viewed as being limited in this regard; paths30may be graphically displayed in a variety of colors, line styles and degrees of transparency as would become apparent to one of ordinary skill in the art after becoming familiar with the teachings of the present invention. In addition, method300is described herein as comprising a GUI including smooth animation graphic. The invention should not be viewed as being limited in this respect either, as other types of animation graphics are possible.

In one embodiment, method300comprises using381smart editing tools280. As explained above, using381smart editing tools280comprises establishing266the maximum attachment radius73, as shown inFIG. 50. Maximum attachment radius73comprises the distance (designated in meters or any other unit) that may define the region of influence373centered about centerpoint375, which may be indicated by mouse click or merely the cursor location321associated with the motion-sensitive device. As shown inFIGS. 82-85, region of influence373is graphically displayed as a circle centered about centerpoint375(which may be coincident with cursor location321) and whose radius is the maximum attachment radius73. Region of influence373may be displayed in any other manner as would be obvious to one of ordinary skill in the art after becoming familiar with the teachings of this invention. In connection with method300, the region of influence373may be described as the instantaneous area within which modification(s) or correction(s) are made to vector sets that overlap it.

Smart editing tools280of the present invention comprise corner/break installation284tool, 1-point detour286tool, N-point detour tool288tool, and move terminals290tool. These smart editing tools280have been described above. Because the smart editing tools280are vector-based, they may be applied to any path30,230(e.g., vector set) associated with a graphic image or a raster image (e.g., remotely-sensed imagery), where path30,230may or may not be associated with road40,240. As described above in connection with method200, the definition of “linear feature” may include any feature captured in raster imagery such that the pixels of the feature lie within a neighborhood distance of a polygonal line, where the neighborhood distance is small by comparison to the total length of the polygonal line. Linear features in remotely-sensed imagery may include the centerlines of roads40, trails, rivers44, mountain ridges and ravines, as well as boundaries of lakes, rivers44, snow pack, fields43, buildings, other man-made structures, etc.

Also as explained above, operation of the smart editing tools280depends on establishing the region of influence373that is displayed graphically on the display screen in a portion of the remotely-sensed image that the user has selected. Generally, as used in connection with any of the smart editing tools280, method300comprises selecting283one of the smart editing tools280by pressing an associated icon, for example. While the user could be the entity that first identifies285error287in path30, that is not necessary in method300. In method300, error287may be automatically identified285using automatic image-based logic. Either way, proposed fixes385or corrections for error287in path30will be automatically and continuously suggested in real time based on the movement of the user's cursor (e.g., centerpoint375) and region of influence373, as will be explained in more detail below. All the proposed fixes385are displayed graphically (in a manner that visually distinguishes the proposed fixes385from path30) for the user to preview314prior to committing316to one of them as the desired edit for error287.

Once the smart editing tool280has been selected283, the user uses the motion-sensitive device (e.g. mouse) to drag the centerpoint375(e.g., cursor) of region of influence373(causing the whole region of influence373to follow continuously) to a desired location. The user may also use the motion-sensitive device (e.g., mouse wheel, track ball, slider, touch pad) to vary the maximum attachment radius73or dimensions of the region of influence373to delimit an area within which modifications may be made to path30. As the user drags the cursor and thereby moves the region of influence373(and centerpoint375), certain or all paths30that overlap the region of influence373undergo modification within the region of influence373(in accord with the particular editing tool selected) automatically, continuously, and in real-time. Although method300is described in embodiments in which a mouse is used, the present invention should not be viewed as being limited in that respect. Moreover, method300is described in embodiments in which the cursor and centerpoint375are in the same location within the region of influence373; however, the present invention should not be viewed as being limited in that respect either.

Once the smart editing tool280has been selected283, the user uses the motion-sensitive device (e.g. mouse) to drag the centerpoint375(e.g., cursor) of region of influence373(causing the whole region of influence373to follow continuously) to a desired location. The user may also use the motion-sensitive device (e.g., mouse wheel, track ball, slider, touch pad) to vary the maximum attachment radius73or dimensions of the region of influence373to delimit an area within which modifications may be made to path30. As the user drags the cursor and thereby moves the region of influence373(and centerpoint375), certain or all paths30that overlap the region of influence373undergo modification within the region of influence373(in accord with the particular editing tool selected) automatically, continuously, and in real-time. Although method300is described in embodiments in which the mouse is used, the present invention should not be viewed as being limited in that respect. Moreover, method300is described in embodiments in which the cursor and centerpoint375are in the same location within the region of influence373; however, the present invention should not be viewed as being limited in that respect either.

In addition, method300may also comprise activating262automatic vector revision functions prior to selecting283any of the smart editing tools280. In that case, automatic vector revision functions, including automatic topology cleaning, will be performed on all vector sets that overlap the region of influence373as it is moved around the remotely-sensed image as viewed in the graphical display. Automatic vector revision functions of the present invention have been described above.

As the user moves the region of influence373around the remotely-sensed image in the graphical display, the user can visually preview314the fixes385that are proposed to the vector sets that overlap the instantaneous region of influence373. Once the user is satisfied with the preview visualization of proposed fix385, the user commits316to the proposed fix385, for example, by single mouse-click against it. Proposed fixes385to path30may be graphically displayed in any manner that distinguishes them from the original state of path30. For example, proposed fixes85may be displayed in a color or line style different from that of path30, although other methods can be used. When the user commits316to the proposed fix385of path30as a final correction, the color and line style of new path230returns to that of original path30. New path230is saved off to storage that persists the latest geometry and attribution of the vector sets symbolically—these could be a shape table, output vector file24, or geo-database, among others. In another embodiment, the color and line style of new path230could be changed back to that of original path30during the storage step.

In the embodiments described herein, the proposed fixes385are not saved off to storage that persists the latest geometry46and attribution45of the vector sets symbolically until the user commits316. However, in another embodiment, the proposed fixes385could be saved off to such storage during the preview314and prior to commit316. In such cases, the commit316operation does nothing other than end the preview314session.

Method300will now be described when using the 1-point detour tool286. Embodiments of the 1-point detour286tool have been discussed in detail above. If the user has selected283the 1-point detour286tool as the desired smart editing tool280, then in response to the user's current cursor location321and the associated region of influence373about that location, method300will automatically select path30and apply the 1-point detour286tool to it, so as to correct path30where it deviates unacceptably far from the true centerline of the road40.

FIG. 82illustrates the operation of 1-point detour286tool as part of method300. As shown inFIG. 82(A), the user begins to drag the cursor (in this case, coincident with centerpoint375) and the associated region of influence373in the direction of path30containing error287. The cursor location321(e.g., centerpoint)375is now in the vicinity of error287. As used herein, “in the vicinity” means at, on or near. When the cursor location321is moved closer to road40as shown inFIG. 82(B), proposed fix385(which has automatically re-routed path30through the cursor location321, as well as centerpoint375, within the region of influence373) is suggested and displayed on the graphical display (as a semi-transparent ribbon of different color from that of path30), allowing the user to preview314proposed fix385. Having rejected proposed fix385, the user moves the cursor location321(e.g., centerpoint375) still closer to road40as shown inFIG. 82(C)and now proposed fix385′ is suggested, allowing the user to preview314that proposed fix385′. Having rejected proposed fix385′, the user places the cursor (and, therefore, centerpoint375) at cursor location321on road40as shown inFIG. 82(D), and proposed fix385″ is suggested. In each ofFIG. 82(B, C, D), the 1-point detour286tool has automatically rerouted path30through the current cursor location321, as well as centerpoint375, within the confines of the current region of influence373. No intermediate placement of anchor points332,334or additional anchor points332a,334ais required. The 1-point detour286tool automatically generates the smooth new path230. New path230preserves the original locations of the end anchor points32,34of the path30and now smoothly approximates the centerline of road40. The length64of path230may be automatically reattributed245. In another embodiment, the width66of path230may also be reattributed245. In a preferred embodiment, where the path30is very curvy, the maximum attachment radius73may be beneficially established266as 15 m prior to the 1-point286detour smart edit operation; where the path30is not very curvy, the maximum attachment radius73may be beneficially established266as 30 m prior to the 1-point detour286smart edit operation.

Once the user has previewed314proposed fix385″ as path230and is satisfied with the look of the modifications, the user may commit316to the proposed fix385″, which in the present embodiment is achieved with one mouse-click. The proposed fix385″ realized as path230is thus saved off to storage that persists the latest geometry46and attribution45of the vector sets symbolically which, in the present embodiment, is a shape table. As the proposed fix385″ realized as path230has been committed316, its color and line style revert back to that of path30.

The 1-point detour286tool of the present invention may also be used in conjunction with the automatic topology cleaning, as shown inFIG. 83. In this embodiment, aided by automatic topology cleaning, the 1-point detour286tool handles the T junction (e.g., intersection42) involving two paths30,30awhere path30plays the role of the crossbar of the T and path30aplays the role of the vertical bar of the T. In what follows, the user directly edits path30with 1-point detour286tool, while path30ais affected indirectly by the edit and updated automatically in real-time in accord with automatic topology cleaning so as to maintain the T-like incidence of the two paths30,30a. As shown inFIG. 83(A), the user begins to drag the cursor (in this case, coincident with centerpoint375) and the associated region of influence373in the direction of path30containing error287. The cursor (e.g., centerpoint375) is now in the vicinity of error287. When the cursor, as well as centerpoint375, are moved closer to road40as shown inFIG. 83(B), proposed fix385(which reroutes path30through the current cursor location and centerpoint375and within the region of influence373) is suggested and displayed on the graphical display (as a semi-transparent ribbon of different color from that of path30). In this case, proposed fix385includes both path30and path30asince the region of influence373overlaps both of these paths30,30a. While path30contains error287, the repair of path30ais induced because of its incidence to path30and is handled automatically via automatic topology cleaning. Having rejected proposed fix385, the user moves the cursor, as well as centerpoint375, still closer to road40in the vicinity of intersection42as shown inFIG. 83(C)and now proposed fix385′ is suggested, allowing the user to preview that proposed fix385′. Having rejected proposed fix385′, the user moves the cursor, as well as centerpoint375, to a location directly on road40in the vicinity of intersection42as shown inFIG. 83(D)and now proposed fix385″ is suggested, allowing the user to preview that proposed fix385″. The 1-point detour tool286in conjunction with automatic topology cleaning has now automatically rerouted the two paths30,30aso that they exhibit the correct geometry in relation to intersection42. According to an embodiment of method300, the 1-point detour286tool may accomplish the rerouting of paths30,30a, to paths230,230awithout the user having to specify anchor points232,234, or additional anchor points232a,234a. Revised paths230,230amay be reattributed245automatically and separately.

Once the user has previewed314proposed fix385″ as path230,230aand is satisfied with the look of the modifications, the user may commit316to the proposed fix385″, which in the present embodiment is achieved with one mouse-click. The proposed fix385″ as path230is made permanent and saved off to storage that persists the latest geometry46and attribution45of the vector sets symbolically, which in the present embodiment is a shape table. Once the proposed fix385″ as path230has been committed316, its color and line style revert back to that of path30.

In yet another embodiment of method300, 1-point detour286tool may be used to repair two tandem paths30,30a. Given two tandem paths30,30a(e.g., end-to-end), 1-point detour tool286handles the two paths30,30ain seamless fashion as if they constituted single super path330. Then, the 1-point detour286tool automatically breaks the super path330into two new paths30b,30cthat are incident end-to-end. The incidence location of the two new paths30b,30chas a natural relationship to the incidence location of the original two paths30,30a. (The 1-point detour286tool's handling of tandem paths30,30awas discussed above in connection withFIG. 63to illustrate an embodiment of method200.)

Method300may also comprise using381the N-point detour288tool as the desired smart editing tool280. If the user has selected283the N-point detour288tool as the desired smart editing tool280, then in response to the user's current cursor location321and the associated region of influence373about that cursor location321, method300will automatically select path30and apply the N-point detour288tool to it, so as to correct path30where it deviates unacceptably far from the true centerline of the road40.

As shown inFIG. 84(A), once the N-point detour288tool has been selected283, the user begins to drag the cursor (coincident with centerpoint375) and the associated region of influence373in the direction of path30containing error287. The cursor location321(e.g., centerpoint375) is now in the vicinity of error287. When the user moves the cursor location321, as well as centerpoint375, to the location shown inFIG. 84(B), the N-point detour288tool automatically reroutes path30through this cursor location321(and centerpoint375) within the region of influence373as shown. The user now clicks with the mouse at this cursor location321to establish anchor point232on the rerouted path30a. The rerouted path30ais visually displayed as a semi-transparent ribbon of color or line style different from that of original path30shown inFIG. 84(A). Next, the user moves the cursor location321, as well as centerpoint375, and the associated region of influence373to the location shown inFIG. 84(C). The N-point detour288tool takes rerouted path30aofFIG. 84(B)that goes through anchor point232, and automatically reroutes it through the new cursor location321(e.g., centerpoint375) inFIG. 84(C)within the region of influence373. The user now clicks at this cursor location321to establish anchor point232aon the latest rerouted path30b. The latest rerouted path30bnow passes through both anchor points232,232a. Next, the user moves the cursor location321, as well as centerpoint375, and the associated region of influence373to the location shown inFIG. 84(D)inducing the reroute of path30bshown there. The user now double clicks at this cursor location321to establish anchor point234on this latest rerouted path230and to designate anchor point234as the final anchor point234in the sequence. The latest rerouted path230now passes through all three anchor points232,232a, and234. Upon the double click, the new path230is saved off to storage that persists the latest geometry46and attribution45of the vector sets symbolically which, in the present embodiment, is a shape table. As the path230has been committed316, its color and line style revert back to that of path30.

The rerouting of path30does not modify path30outside the areas which variously overlap the region of influence373centered about the anchor points232,232a,234. New path230preserves the original locations of end anchor points32,34of the path30. The length64of path230is automatically reattributed245. In another embodiment, the width66of path230may also be automatically reattributed245.

If the user selects just two anchor points232,234during application of N-point detour288operation, then the portion of new path230that spans the two anchor points232,234may simply be a straight line, and the path230may not be smooth at those two anchor points232,234(in other words, an angle in path230may appear at one or both anchor points232,234). In another embodiment, the N-point detour288tool may be applied to two tandem paths30,30a, where the first user-selected52anchor point32in the N-point detour288operation is in the vicinity of path30and the last user-selected52anchor point32ain the N-point detour288operation is in the vicinity of path30a. In that case, the tandem configuration of path30and30ais treated by the N-point detour288operation as a single path, resulting in a rerouted new path230that is then automatically partitioned at a point along its trajectory that has a natural relationship to the tandem point where path30and path30ahad met. This results in two revised tandem paths30,30athat may be reattributed245automatically and separately.

In another embodiment, method300may comprise using381the move terminals290tool as the desired smart editing tool280to move the terminating anchor points32,32a,34,34aof paths30,30a,30b,30cto the single new collective anchor point232. The user may select283the move terminals290tool after identifying285error287. If the user has selected283the move terminals290tool as the desired smart editing tool280, then in response to the user's current cursor location321and the associated region of influence373about that location, method300will automatically select path30and apply the move terminals290tool so as to correct path30where it deviates unacceptably far from intersection42.

As shown inFIG. 85(A), once the move terminals290tool has been selected283, the user begins to drag the cursor (coincident with centerpoint375) and its associated region of influence373in the direction of path30containing error287where paths30,30a,30b, and30cdo not meet properly at intersection42. The cursor location321(e.g., centerpoint375) is now in the vicinity of error287. When the user moves the cursor location321(e.g., centerpoint375) to the location shown inFIG. 85(B), the region of influence373contains at least one terminating anchor point32,32a,34,34aof existing paths30,30a,30b,30c. The move terminals tool290automatically proposes to relocate these terminating anchor points32,32a,34,34ato a common terminal at the cursor location321(e.g., centerpoint375), and reroutes the paths30,30a,30b,30caccordingly within the region of influence373, resulting in proposed fix385. Having rejected proposed fix385, the user moves cursor location321(as well as centerpoint375) and the region of influence373closer to intersection42, as shown inFIG. 85(C). The move terminals290tool automatically proposes the common terminal at the cursor location321(e.g., centerpoint375) and reroutes the paths30,30a,30b,30caccordingly within the region of influence373, resulting in proposed fix385′. Having rejected proposed fix385′, the user moves cursor location321(e.g., centerpoint375) to coincide with intersection42, as shown inFIG. 85(D). Again, the move terminals290tool automatically proposes the common terminal at the cursor location321(e.g., centerpoint375) and reroutes the paths30,30a,30b,30caccordingly within the region of influence373, resulting in proposed fix385″. Assuming the user is satisfied with the preview314of proposed fix385″, the user clicks at the current cursor location321(e.g., centerpoint375) to establish anchor point232as the common terminal for paths230,230a,230b,230c. The proposed fix385″ is committed316and saved off to storage that persists the latest geometry46and attribution45of the vector sets symbolically which, in the present embodiment, is a shape table. Once the proposed fix385″ is committed316, the color and line style of paths230,230a,230b,230crevert back to those of paths30,30a,30b,30c.

In another embodiment of method300, the move terminals290tool may also be applied to a T or +intersection42where the valence of the intersection42(3 for T, 4 for +) is one greater than the number of paths terminating at the intersection42(e.g., path30involved in the intersection42passes though the intersection42, while paths30a,30bmore or less terminate there), in similar manner to that explained above to propose the common terminal for paths30a,30bon path30at intersection42. SeeFIG. 67. This can be done by setting the line snap distance74asufficiently large and then moving the cursor location321(e.g., centerpoint375(which takes along the region of influence373)) in the vicinity of intersection42. The move terminals290tool will automatically propose fix385, comprising the common terminal (snapped to path30as allowed by the line snap distance74a) for paths30a,30b. Assuming the user is satisfied with the preview314of proposed fix385, the user clicks at the cursor location321(e.g., centerpoint375) to establish anchor point232as the common terminal on path30for paths30a,30b. As before, paths30a,30bare rerouted within the region of influence273,373. In the embodiment described, the region of influence373is centered about the current cursor location321(e.g., centerpoint375). In another embodiment the region of influence373may be centered about the point31on path30that is close or closest to the current cursor location321.

While steps for using381the smart editing tools280as part of method300has been variously described, it is important to remember that the various operations and algorithms enable real-time, automatic, on-the-fly updates to the vector sets (e.g., paths30) in the graphical display. To the user, the proposed fixes385adjust smoothly and continuously in the graphical display in response to the current cursor location321and associated region of influence373. Thus, advantageously, in response to movement of the cursor, paths30appear to be continuously redrawn without the need to add additional anchor points232a,234a, and without the need for mouse-clicks, except to commit to the proposed fix385″ after previewing314other proposed fixes385,385′. Prior art methods, by comparison, experience at least one of the following two weaknesses: (a) multiple edit operations are required to achieve the same effect as a single edit operation in method300; (b) no preview capability is provided against edit operations, so that if the user decides an already-applied edit is unacceptable, he must either “undo” the edit, or apply additional edit operations as “touch-up” to remedy the deficiencies of the first edit operation. Thus, method300minimizes user effort and tedium in relation to the activity of editing extracted vector sets (e.g. path30) toward the goal of making cartographically-accurate maps.

Method300may further comprise editing path30by attributing345or reattributing the feature width (“width”, for short)366to path30. In prior art methods, when no acceptable image-independent default width is available for path30, and when no automatic image-based logic is available to accurately assess the width of path30, the user typically computes the width of the linear feature represented by path30via manual measuring tools, for example, a tool that allows the user to stretch a graphical rubber band across the short axis of the linear feature and return the length of the rubber band in appropriate units. However, using the present invention, attributing345width366is easier and in some cases more accurate than explicit manual measurement, particularly when there is local variability in the width of the feature along its centerline, so that an average or representative width is truly what is desired. The present invention allows the user to adjust the proposed width366′,366″ of path30(taken as the centerline of the linear feature) continuously via the motion-sensitive device (e.g., mouse wheel, slider bar) and to preview314the results of that action in real time in the graphical display. For each proposed width366′,366″ for path30, the user can see how well that width366′,366″ agrees with the actual width366of the corresponding linear feature in the image.

InFIG. 86(A), path30is depicted by a narrow centerline of road40. Once the tool is activated, attributing345width366may begin by rendering path30as a semi-transparent or opaque ribbon of uniform width66, such as a default or currently-assigned width, on the remotely-sensed image in the graphical display, as shown inFIG. 86(B). The ribbon may be displayed with the centerline designated, but this is not required. The ribbon width is tied to and may be continuously varied by operation of the motion-sensitive device (e.g., mouse wheel, slider bar). As shown inFIGS. 86(C)and (D), width366′,366″ is continuously varied, automatically, on-the-fly and in real time until the user is satisfied that the final width366fills all or nearly all of the space occupied by road40. Again, the user has the ability to visually preview314proposed widths366′,366″ before committing316. Committing316to final width366for path230means saving off the final width366for path230to the storage that persists the latest geometry46and attribution45of the vector sets symbolically which, in the present embodiment, is a shape table. This is assuming that saving off to such storage was not occurring during the previews314. Otherwise, the commit316step simply means terminating the current width-preview session.

In another embodiment of method300, path30may be smoothed in a manner similar to that which was just described for attributing345width366. Methods for smoothing path30have previously been described. According to method300, path30may be globally smoothed318by using the motion-sensitive device (e.g., mouse wheel, slider bar) to vary the level of global smoothing318applied to the path30. The result is displayed visually in the graphical display. Once the continuous global smoothing318tool has been activated, the user can preview314the effects of different levels of global smoothing318on the path30shown in the graphical display.

InFIG. 87(A), irregular and uneven path30is shown. Once the global smoothing318tool is activated and the user designates path30for global smoothing318(e.g., by clicking on path30with the mouse), global smoothing318may begin by rendering path30as a semi-transparent or opaque ribbon on road40in the graphical display.FIG. 87(B). The ribbon may be displayed with the centerline designated, but this is not required. The smoothing level of the ribbon is tied to and may be continuously varied by operation of the motion-sensitive device (e.g., mouse wheel). As shown inFIGS. 87(C)and (D), the path30is smoothed automatically, continuously, on-the-fly and in real time as a function of the global smoothing318level conveyed through the motion-sensitive device. The previewing314would generally continue until the user is satisfied that path30is sufficiently smooth. The global smoothing318algorithm itself (behind the user interface) may work by varying at least one parameter within the deep smoothing algorithm270or by varying at least one parameter within another known prior art global smoothing algorithm. Either way, the parameter is varied via the motion-sensitive device. As in other embodiments of method300, the user may visually preview314proposed fixes385,385′ before committing316. Committing316to the desired level of smoothing such as shown in path230ofFIG. 87(D)means saving off the newly-smoothed path230to the storage that persists the latest geometry and attribution of the vector sets symbolically which, in the present embodiment, is a shape table. This is assuming that saving off to such storage was not occurring during the previews314. Otherwise, the commit step316simply means terminating the current global smoothing318preview314session.

In another embodiment, the automatic vector revision functions may be at work during global smoothing318. In that case, not only is the path30directly affected by global smoothing318, but other paths30may be indirectly affected (due to their incidence with the path30that is being globally smoothed318) and will be updated by the automatic vector revision functions, redrawn and displayed in real time, automatically continuously, and on-the fly.

Method300may also comprise local smoothing320path30or portion thereof.FIG. 88(A)illustrates path30(path30displayed as a semi-transparent ribbon) with a portion that is irregular, uneven and in need of smoothing. However, this portion of path must first be delimited so that the local smoothing320operation is performed only on delimited segment324. The user moves the cursor in the vicinity of one end of the irregular, uneven portion of path30to cursor location321A, then clicks, which automatically places delimiting point322A on path30. As shown inFIG. 88(B), the user now moves the cursor location to321B, then clicks, which automatically places a second delimiting point322B on path30at the other end of the irregular, uneven portion of path30, thus forming delimited segment324. Delimited segment324may be rendered differently from the rest of path30in the graphical display.FIG. 88(B). A graphical rubber band may connect cursor locations321A,321B, but this is not required. The smoothing level of delimited segment324is tied to and may be continuously varied by operation of the motion-sensitive device (e.g., mouse wheel). As shown inFIGS. 88(C)and (D), the delimited segment324is locally smoothed320automatically, continuously, on-the-fly and in real time as a function of the local smoothing level conveyed through the motion-sensitive device. The previewing314would generally continue until the user is satisfied that the delimited segment324is sufficiently smooth. The local smoothing320algorithm itself (behind the user interface) may work by varying at least one parameter within the deep smoothing algorithm270or by varying at least one parameter within some other known prior art global smoothing algorithm. Either way, the parameter is varied via the motion-sensitive device. As in other embodiments of method300, the user may visually314preview proposed fixes385before committing316. Committing316to the desired level of smoothing against delimited segment324ofFIG. 88(D)means saving off the newly-modified path230(that was locally smoothed320on delimited segment324) to the storage that persists the latest geometry46and attribution45of the vector sets symbolically which, in the present embodiment, is a shape table. This is assuming that saving off to such storage was not occurring during the previews. Otherwise, the commit316step simply means terminating the current local smoothing320preview314session.

In another embodiment, the automatic vector revision functions may be at work during local smoothing320. In that case, not only is the path30directly affected by local smoothing320against delimited segment324, but other paths30may be indirectly affected (due to their incidence with path30that is being locally smoothed) and will be updated by the automatic vector revision functions, redrawn and displayed in real time, automatically continuously, and in real-time.

Like local smoothing320, the excise functions304of the present invention comprise delimiting a segment in path30, (e.g. delimited segment324) but now for the purpose of excising delimited segment324. Excise functions304of method300comprise the two-point (2-point) excise326tool and the polygon excise328mode.

Two-point excise326tool will now be described with reference toFIG. 89. InFIG. 89(A), the user has already activated the 2-point excise326tool and is moving the cursor from cursor location321toward path30. The user moves the cursor to cursor location321A within the vicinity of path30, then clicks, which automatically establishes delimiting point322A directly on path30as shown inFIG. 89(B). The user then begins to move the cursor in a direction away from delimiting point322A generally following the trajectory of path30. As the user begins the move, the cursor may be connected to cursor location321A by a graphical rubber band, although this is not required. The user moves the cursor to cursor location321B in the vicinity of path30. Without clicking, proposed delimiting point322B′ is automatically placed directly on path30as shown inFIG. 89(B), forming proposed delimited segment324′. The delimited segment324′ may be rendered invisible or otherwise differently from the remainder of path30. As shown inFIGS. 89(C)and (D), as the cursor location321B changes in relation to cursor location322A, the location of proposed delimiting point322B″,322B also changes instantaneously and continuously, causing delimited segment324,324′,324″ to shrink or grow, along path30automatically, on-the-fly, continuously, and in real time as a function of cursor location321B which is linked to delimiting point322B.

Once again, the excise functions304of the present invention, including the 2-point excise326tool, provide the user with an opportunity to preview314the proposed excisions by rendering delimited segments324′,324″ invisible or otherwise distinct from the portions of paths30that are not being excised. The display of the proposed excision is updated automatically, continuously, on-the-fly and in real time as a function of the current cursor location and earlier points established via the cursor. Once the user has previewed314the proposed excision as shown inFIG. 89(D), the user commits316to that excision by double-clicking, for example. Committing316to the excision of delimited segment324from path30ofFIG. 89(D)means saving off the net result of the excision to storage that persists the latest geometry and attribution of the vector sets symbolically which, in the present embodiment, is a shape table. This is assuming that saving off to such storage was not occurring during the previews314. Otherwise the commit316step simply means terminating the current excision preview314session.

The excise functions304of the present invention may also comprise polygon excise328mode, for excising portions of one or more paths30(e.g., vector sets) simultaneously by enclosing those portions to be excised in a final polygon333. In reference toFIG. 90, the user has already activated polygon excise328mode. In this embodiment, method300comprises selecting the polygon excise328mode for excising paths30, or portions thereof, that result from previously extracting linear features in remotely-sensed imagery. As shown inFIG. 90(A), the user places the cursor at cursor location321, then clicks there, establishing the first vertex329of the polygon331being formed. As the user drags the cursor to cursor location321A, a graphical rubber band automatically connects vertex329to cursor location321A, as shown inFIG. 90(B). The user clicks at cursor location321A to establish the second vertex329A of the polygon331being formed. As the user continues to drag the cursor to cursor location321B, polygon331is automatically and continuously updated in the display, connecting established vertices329,329A, with the cursor location321B via the graphical rubber band. The user clicks at cursor location321B to establish the third vertex329B of the polygon331being formed. As shown inFIG. 90(C), polygon331may be rendered by the closed graphical rubber band boundary through vertices329,329A and cursor location321B. The interior of polygon331may be rendered transparent or semi-transparent or in any other manner. Paths30a, or portions thereof, within polygon331may be rendered transparent or differently from the portions of paths30that lie outside of polygon331as shown inFIG. 90(C), (D). Polygon331(or final polygon333) may be of any shape and can include protrusions and intrusions. Paths30that cross the boundary of polygon331may also be highlighted in the manner shown inFIG. 90(B), (C), (D). The shape of polygon331changes automatically, continuously, smoothly, on-the-fly and in real-time as a function of the current cursor location321and vertices329,329A,329B,329C established via the cursor. As the shape of polygon331changes, so do the visual renditions of those portions of paths30athat lie within the interior of the polygon331, as well as the paths30themselves that cross the boundary of polygon331.

The user may preview314polygon331and the associated excision against paths30that overlap its interior. Once the user commits316to the polygon331(e.g., by double-clicking at the last cursor location321C), it becomes final polygon333, as shown inFIG. 90(D). Committing316to the final polygon333means saving off the net result of the excision to storage that persists the latest geometry and attribution of the vector sets symbolically which, in the present embodiment, is a shape table. This is assuming that saving off to such storage was not occurring during the previews314. Otherwise, the commit316step simply means terminating the current polygon excise328preview314session.

In another embodiment, instead of excising portions of paths30awithin the interior of final polygon333, paths30amay be modified using any other universal action, such as smoothing or straightening.

Similarly, other embodiments of method300comprise selecting312an ensemble of vector sets (e.g. paths30) against which to apply the universal action. Methods for selecting312the ensemble of vector sets (e.g., selection ensemble342) on which to apply the universal action comprise paint selection336mode, polyline-thru-selection338mode and partitioning340.

Paint selection336mode will now be described with reference toFIG. 91.FIG. 91(A)shows previously extracted vector sets (e.g., paths30) overlaid on a remotely-sensed image within the graphical display. After the user enters paint selection336mode, using the motion-sensitive device, the user drags the cursor to cursor location321(shown inFIG. 91as circle with a “+” at the center) along a desired trajectory. Each path30(e.g., vector set) encountered or crossed by the cursor as it moves along the desired trajectory is added to selection ensemble342. The moment that the cursor location321crosses or comes in contact with path30, a visual change automatically and instantaneously occurs in path30indicating that path30is now included in selection ensemble342, as shown inFIG. 91(C), (D).

In another embodiment of paint selection336mode, cursor location321may be coincident with centerpoint375of the region of influence373. When the user drags the cursor, centerpoint375and the region of influence373follow. When the region of influence373comes in contact with path30(e.g., vector set), path30is added to the selection ensemble342.

Once the desired selection ensemble342has been formed, the user exits paint selection336mode (e.g., by double-clicking with the mouse) while the vector sets in the selection ensemble342remained selected. At this point, the user may now apply the universal action across all the vector sets in the selection ensemble342. The universal action may comprise deletion (e.g., excision), smoothing, straightening, setting a common attribute value (e.g., width66, material type56), or any other function that takes a vector set as input argument.

Methods for selecting312the ensemble of vector sets (e.g., selection ensemble342) against which to apply the universal action further comprise polyline-thru-selection338mode, which will now be described with reference toFIG. 92.FIG. 92(A)shows previously extracted vector sets (paths30) overlaid on the remotely-sensed image within the graphical display. After the user enters polyline-thru-selection338mode, the user creates graphical polyline344in the graphical display, using the cursor associated with a motion-sensitive device to establish the vertices329of polyline344. As the user moves the cursor and clicks, as shown in FIG.92(A)-(C), vertices329of polyline344are created coincident with cursor locations321. The last vertex329added to the polyline344is designated by the user with a double click at the corresponding cursor location321. At this time, any path30crossed by polyline344is automatically placed in selection ensemble342and undergoes visual change resulting in path30a, as shown inFIG. 92(D).

Once the desired selection ensemble342has been formed via polyline-thru-selection338mode, the user may now apply the universal action across all the vector sets in the selection ensemble342. The universal action may comprise deletion (e.g., excision), smoothing, straightening, setting a common attribute value (e.g., width66, material type56), or any other function that takes a vector set as input argument.

Partitioning340the remotely-sensed image into cells346in the graphical display will now be described with reference toFIG. 93. Partitioning340the remotely-sensed image into cells346may be used as part of methods for systematic quality assurance and quality control (QA/QC) of linear feature extraction. During the QA/QC activity, extracted vector sets (e.g., paths30) fall into two categories: those that are approved and committed316, and those that are uncommitted and which may required modification prior to approval. Similarly, entire cell346can be viewed as uncommitted or committed316, depending on whether its interior overlaps path30that is uncommitted, for example. Partitioning340enables the user at any moment in time to concentrate attention on a particular uncommitted focus cell348that overlaps at least one uncommitted path30and is therefore in need of QA/QC resolution. Partitioning340also enables the user to keep track of which cells346have already been committed316following QA/QC review and which have not.

After the user selects the remotely-sensed image, displays it on the graphical display, and has overlaid vector sets (e.g., paths30) on it, the user partitions340the remotely-sensed image into cells346,346A, where cells346,346A overlap paths30(which may or may not be committed316) and are rendered visible or differently in the graphical display from those that do not overlap paths30. Additionally, uncommitted focus cell348(which overlaps at least one path30that is uncommitted) may be rendered differently in the graphical display from other cells346(which overlap paths30that may or may not be committed). Paths30that are uncommitted may be rendered differently in the graphical display than paths30that are committed316. InFIG. 93(A), for example, all paths30are in the uncommitted stated as evidenced by the fact that they are not of the color used to designate the committed316state. InFIG. 93(B), the user has selected path30a(highlighted) that overlaps the lower right cell346A. Where the user wishes to delete path30as part of the QA/QC review, for example,FIG. 93(C)shows that path30ahas been deleted and cell346A has been rendered invisible in the graphical display because it no longer overlaps any paths30. Although any path30in any cell346can be edited for QA/QC review at any time, in a preferred embodiment, the user may edit paths30within focus cell348. After some or all of the paths30in focus cell348have passed QA/QC review, and have been committed316, the user can instantaneously advance the focus cell348to the next cell346that overlaps uncommitted paths30. Establishing focus cell348facilitates systematic QA/QC review of uncommitted paths30. As in the other embodiments of method300, changes in path30, including status changes from uncommitted to committed316, are made automatically, continuously, on-the-fly and in real time. Partitioning340comprises previewing314the various edit operations described above since this supports the QA/QC process. As previously discussed, changes in path30are saved off to storage that persists the latest geometry46and attribution45of vector sets, which, in the present embodiment, is a shape table.

In addition, partitioning340can be used in conjunction with other embodiments of method300, such as global smoothing318, straightening, automatic vector revision functions, and excision. The user can confine any of these operations within focus cell348after partitioning the remotely-sensed image in the graphical display; however, any cell346could also be employed. In addition, the QA/QC process of changing the status of paths30from uncommitted to committed316may be performed collectively on all vector sets (e.g., paths30) in selection ensemble342, as well. In addition, the QA/QC process of changing the status of paths30from uncommitted to committed316may be performed collectively on all paths30that overlap or lie entirely within focus cell348or any other cell346.

For various reasons, it is often necessary to extend a previously-extracted vector set (path30) representing a linear feature in remotely-sensed imagery so as to create a longer vector set (super path330) that contains the first. If it is desired that this extension be performed using automatic image-based logic, the extension would logically take place in two parts. The first part involves extracting, in image-based fashion, a new portion of the relevant linear feature that terminates at an endpoint (e.g., anchor point32) of the existing vector set (e.g., path30). The second part involves fusing the newly-extracted vector set (e.g., path30a) and the previously-extracted vector set (e.g., path30) together into a single vector set (e.g., super path330). From a user interface perspective, it is desirable that these two distinct operations be invoked together within the context of a single operation. The primary drivers for vector set extension capability are: (a) present-day remotely-sensed raster images are sometimes so huge that it is not practical with a single extraction operation to extract the entirety of a very long linear feature; (b) previously extracted vector sets corresponding to linear features (e.g., paths30) may terminate on the boundary of a given raster image and might later require extension when an adjacent raster image in a mosaic comes into play; (c) remotely-sensed landscapes are often ever-changing as a result of human and natural forces—thus vector sets (e.g., paths30) extracted from an older raster image representing roads40, for example, may need to be extended in a newer raster image covering the same landscape, as the roads40themselves may have been extended in the interim between the time the two images were captured. As described below, method300enables the user to perform image-based vector set extension under the guise of a single operation that invokes both the extraction step and the fusion step mentioned above.

Extending306existing path30in image-based fashion will now be described with reference toFIG. 94. As shown inFIG. 94(A), the vector extension308mode for extending306existing path30combines, in a single operation, the activities of first extracting a new linear feature (using the image-based-logic extraction methods described herein) from remotely-sensed imagery where the new linear feature (e.g., road40) is geometrically tandem to path30, and second, fusing the new extraction with existing path30. After the user enters the vector extension308mode, the user extracts path30ausing the image-based methods for linear feature extraction previously described herein. As the user places anchor points32,32aon road40in the vicinity of anchor point34on previously extracted path30, new path30awill be automatically extracted and automatically fused to path30to form super path330that follows the trajectory of paths30,30a. The geometry46of super path330is attributed45automatically. Super path330then effectively replaces path30within the storage that persists the latest geometry and attribution of vector sets which, in the present embodiment, is a shape table.

Vector extension308mode can also be used to extend two paths30,30′ in image-based fashion where road40has not been extracted between them. The extension essentially bridges the two paths30,30′ together to form super path330that contains them. As shown inFIG. 94(B), after the user enters vector extension308mode, the user extracts path30ausing the image-based methods for extraction previously described herein. The user places anchor point32on road40in the vicinity of anchor point34on previously extracted path30and places anchor point32ain the vicinity of anchor point34aof path30′. New path30awill be automatically extracted and automatically fused with paths30,30′ to form super path330that follows the trajectory of paths30,30a,30′. The geometry46of super path330is attributed45automatically. Super path330then effectively replaces paths30and30′ within the storage that persists the latest geometry46and attribution of vector sets which, in the present embodiment, is a shape table.

To help relieve effort and tedium in extracting linear features from remotely-sensed imagery, method300embodies snapping310the cursor to “raw feature signal”350, which can be thought of as snapping the cursor to a nearby pixel (in the remotely-sensed imagery) that locally manifests the characteristics of a desired type of linear feature (e.g., road40, trail, river44, etc.) that the user wishes to extract. This capability enables the user, prior to extracting a linear feature with automatic image-based logic, to preview314which linear feature (e.g., road40, river44) is about to be extracted (based on the current cursor location321) before it actually is extracted. It also allows the user to use the image-based-logic extraction methods described herein to extract the desired linear feature without having to place the cursor precisely on that linear feature (e.g., road40, river44) in order to extract it. It also allows the user to perform linear feature extractions without having to zoom in on as small a portion of the remotely-sensed image as would otherwise be necessary.

Snapping310to raw feature signal350comprises initially selecting a remotely—sensed image and forming from it a derived raster sub-image352. Examples of derived raster sub-image352are the gradient or the Laplacian of the original raster image, but much more sophisticated derived images are possible. Derived raster sub-image352comprises a sub-image of the selected remotely-sensed image in which the pixels in derived raster sub-image352have been classified into groups. Each group corresponds to a particular kind of linear feature of interest (e.g., road40centerline pixels, trail centerline pixels, river44centerline pixels, etc.), except one group contains pixels that do not manifest as belonging to any linear feature of interest. Alternatively, the classification of pixels may be into just two groups: those that lie on linear features of interest, and those that do not. Either way, pixels that lie on linear features of interest (as dictated by the derived raster sub-image352) are highlighted in the display relative to the remaining pixels of the original (selected) raster image. More than one type of linear feature may be so highlighted at a time with, for instance, different colors used for pixels that belong to different types of linear features. For example, as shown inFIG. 95, the desired linear features are road40centerline and river44centerline; road40centerline pixels appear as one shade of dark gray, and river44centerline pixels appear as a different shade of dark gray. The remaining pixels of the original (selected) raster image are not highlighted at all. The derived raster sub-image352may be created through pre-processing218or may be created in real time, on-the-fly as a function of the current cursor location321.

Snapping310to raw feature signal350comprises aligning derived raster sub-image352with the selected remotely-sensed image, so that corresponding pixels (in the geo-spatial sense) line up. Derived raster sub-image352may be visually displayed as an overlay to the selected remotely-sensed image in the graphical display. However, this is not required, and in fact, derived raster sub-image352may not be displayed at all (though the capability of snapping310to raw feature signal350nevertheless understands the alignment.)

Once the derived raster sub-image352(which was created either at the outset of the extraction session during pre-processing218or created on the fly as a function of the cursor location321) is aligned with the selected remotely-sensed image, the user's current cursor location321is snapped to the nearest pixel (or a nearby pixel) that lies on the linear feature of interest (e.g., road40). In the case ofFIG. 95, for example, if the user has designated at the outset that all road40centerline pixels are of interest (and thus represent raw feature signal350) then placing the cursor in the vicinity of road40would cause the cursor to be automatically and instantaneously “snapped” to that the location of the nearest road40centerline pixel within the derived raster sub-image352.

Similarly, inFIG. 96, the user has designated at the outset that all road40centerline pixels are of interest (and thus constitute raw feature signal350). What appear as dark lines through the center of roads40are classified as road40centerline pixels in the derived raster sub-image352, which is overlaying the selected remotely-sensed image in the graphical display. As the user places the cursor near road40at cursor location321, the cursor location321automatically and instantaneously snaps310the cursor to raw feature signal350, which in this case is the nearest road centerline pixel (in the derived raster sub-image352) for road40. The new cursor location321′ is indicated onFIG. 96(A)at the crosshair. The user now clicks to establish a terminating anchor point32at location321′ for path30that is about to be extracted using image-based logic. Next, the user moves the cursor to location321A which is similarly snapped to road40centerline pixel. The user now clicks to establish terminating anchor point34at location321A′ for path30athat is about to be extracted using image-based logic. The fact that both cursor locations321,321A were snapped to centerline pixels of road40indicates to the user that road40is in fact the linear feature that is about to be extracted (versus another nearby linear feature). Now when the user double clicks, the road40will be extracted with image-based logic as was described earlier herein, creating path30automatically.

Having herein set forth various and preferred embodiments of the present invention, it is anticipated that suitable modifications can be made thereto which will nonetheless remain within the scope of the invention. The invention shall therefore be construed in accordance with the following claims: