Automatically and accurately conflating road vector data, street maps, and orthoimagery

• US 20070014488A1
• Filed: 06/28/2005
• Published: 01/18/2007
• Est. Priority Date: 07/09/2004
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Shahabi, Cyrus, Chen, Ching-Chien, Chiang, Yao-Yi, Knoblock, Craig
• Granted Patent: US 7,660,441 B2
• Time in Patent Office: Days
• US Class Current: 382/294
• CPC Class Codes: G06T 3/147 using affine transformations
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

Automatic conflation systems and techniques which provide vector-imagery conflation and map-imagery conflation. Vector-imagery conflation is an efficient approach that exploits knowledge from multiple data sources to identify a set of accurate control points. Vector-imagery conflation provides automatic and accurate alignment of various vector datasets and imagery, and is appropriate for GIS applications, for example, requiring alignment of vector data and imagery over large geographical regions. Map-imagery conflation utilizes common vector datasets as “glue” to automatically integrate street maps with imagery. This approach provides automatic, accurate, and intelligent images that combine the visual appeal and accuracy of imagery with the detailed attribution information often contained in such diverse maps. Both conflation approaches are applicable for GIS applications requiring, for example, alignment of vector data, raster maps, and imagery. If desired, the conflated data generated by such systems may be retrieved on-demand.

Claims

1. A method for automatically conflating vector data with geospatial data, said method comprising:

identifying a first set of feature points associated with said vector data;

identifying a second set of feature points associated with said geospatial data;

generating control point pairs, wherein each of said control point pairs includes a distinct one of said first set of feature points and a corresponding distinct one of said second set of feature points; and

deforming at least one of said vector data and said geospatial data to effectively align said control point pairs.

2. The method according to claim 1, wherein said first set of feature points are identified according to a method comprising:

identifying a plurality of line segments defined by said vector data;

identifying a plurality candidate control points, which are each defined by an endpoint of one of said plurality of line segments; and

determining line connectivity of each of said plurality of candidate control points, wherein if said line connectivity for a particular candidate control point exceeds a threshold, then said particular candidate control point is identified as one of said first set of feature points.

3. The method according to claim 2, wherein said threshold is exceeded whenever more than two line segments of said plurality of line segments share common candidate control points of said plurality of candidate control points.

4. The method according to claim 1, wherein said second set of feature points are identified according to a method comprising:

generating a template based upon at least one of said first set of feature points and line characteristics associated with said at least one of said first set of feature points;

identifying geo-coordinates of said first set of feature points;

identifying approximate locations within said geospatial data of each of said first set of feature points;

generating a road-labeled image by identifying on-road regions of said geospatial data; and

comparing said road-labeled image with said template to identify on-road regions in said road-labeled image which have effectively similar dimensions and angles, relative to an orientation of said vector data, as said template, said comparing resulting in said identifying of said second set of feature points.

5. The method according to claim 4, wherein said line characteristics comprise line width of a line segment associated with said at least one of said first set of feature points.

6. The method according to claim 4, wherein said line characteristics comprise line angle of a line segment associated with said at least one of said first set of feature points, wherein said line angle is defined by the angle of said line segment relative to an orientation of said vector data.

7. The method according to claim 4, wherein said identifying said on-road regions of said geospatial data is accomplished by a method comprising:

computing a hue value for a plurality of locations on said geospatial data;

for each of said plurality of locations, comparing said hue value with previously calculated hue values obtained from representative geospatial data, comprising on-road and off-road regions, to generate a probability that a particular location of said plurality of locations is either on-road or off-road; and

wherein

said on-road regions of said geospatial data are defined by said plurality of locations on said geospatial data which meet a certain threshold of said probability.

8. The method according to claim 4, wherein said identifying said on-road regions of said geospatial data is accomplished by a method comprising:

computing a saturation density for a plurality of locations on said geospatial data;

for each of said plurality of locations, comparing said saturation density with previously calculated saturation densities obtained from representative geospatial data, comprising on-road and off-road regions, to generate a probability that a particular location of said plurality of locations is either on-road or off-road; and

wherein

said on-road regions of said geospatial data are defined by said plurality of locations on said geospatial data which meet a certain threshold of said probability.

9. The method according to claim 4, wherein said identifying said on-road regions of said geospatial data is accomplished by a method comprising:

computing a hue value for a plurality of locations on said geospatial data;

for each of said plurality of locations, comparing said hue value with previously calculated hue values obtained from representative geospatial data, comprising on-road and off-road regions, to generate a first probability that a particular location of said plurality of locations is either on-road or off-road;

computing a saturation density for a plurality of locations on said geospatial data;

for each of said plurality of locations, comparing said saturation density with previously calculated saturation densities obtained from representative geospatial data, comprising on-road and off-road regions, to generate a second probability that a particular location of said plurality of locations is either on-road or off-road; and

wherein

said on-road regions of said geospatial data are defined by said plurality of locations on said geospatial data which meet a certain threshold of said first probability and said second probability.

10. The method according to claim 1, wherein said generating control point pairs comprises:

filtering inaccurate control point pairs from said control point pairs, each of said inaccurate control point pairs including a feature point of said second set of feature points that is located on said geospatial data that exceeds a threshold distance and angle relative to an actual location on said geospatial data.

11. The method according to claim 1, said method further comprising:

generating a plurality of control point vectors, each of said plurality of control point vectors being defined by a relative position of a distinct one of said first set of feature points and a corresponding distinct one of said second set of feature points;

generating a vector median for said plurality of control point vectors;

associating each of said control point pairs with corresponding control point vectors of said plurality of control point vectors; and

filtering inaccurate control point pairs from said control point pairs, each of said inaccurate control point pairs having a corresponding control point vector which exceeds a threshold difference in direction and magnitude relative to said vector median.

12. The method according to claim 1, said method further comprising:

(a) generating a plurality of control point vectors which are individually associated with a particular one of said control point pairs, wherein each of said plurality of control point vectors comprises a tail point defined by a distinct one of said first set of feature points and a head point defined by a corresponding distinction one of said second set of feature points;

(b) calculating a number of said tail points of said plurality of control point vectors that are located within a predetermined distance relative to a particular head point associated with a particular one of said plurality of control point vectors, wherein if said number falls below a certain threshold, then a control point pair that is associated with said particular one of said plurality of control point vectors is identified as an inaccurate control point pair;

(c) filtering said inaccurate control point pair from said control point pairs; and

(d) repeating said calculating operation (b) and said filtering operation (c) for each tail point of said plurality of control point vectors.

13. The method according to claim 1, wherein said deforming includes rubber sheeting at least one of said vector data and said geospatial data to effectively align said control point pairs.

14. The method according to claim 1, said method further comprising:

obtaining said vector data from a vector data source; and

obtaining said geospatial data from a geospatial data source.

15. The method according to claim 1, wherein said deforming deforms said vector data to effectively align said control point pairs.

16. The method according to claim 1, wherein said deforming deforms said geospatial data to effectively align said control point pairs.

17. The method according to claim 1, wherein said deforming deforms both said vector data and said geospatial data to effectively align said control point pairs.

18. The method according to claim 1, wherein said vector data comprises road network vector data.

19. The method according to claim 1, wherein said geospatial data comprises orthoimagery.

20. The method according to claim 1, said method further comprising:

creating image-aligned vector data based upon said deforming.

21. The method according to claim 20, said method further comprising:

generating a composite image comprising said geospatial data and said image-aligned vector data.

22. The method according to claim 20, said method further comprising:

generating a composite image labeled with attribute data associated with said image-aligned vector data.

23. The method according to claim 1, said method further comprising:

finding geo-coordinates and scale of said vector data.

24. The method according to claim 1, wherein said geospatial data comprises vector data.

25. The method according to claim 1, wherein said geospatial data comprises georeferenced imagery.

26. The method according to claim 1, wherein said geospatial data comprises a raster map.

27. The method according to claim 1, wherein each of said first set of feature points comprises a distinct road intersection, and wherein each of said second set of feature points comprises a distinct road intersection.

28. The method according to claim 1, wherein each of said first set of feature points comprises a distinct railroad intersection, and wherein each of said second set of feature points comprises a distinct railroad intersection.

29. The method according to claim 1, wherein each of said first set of feature points comprises a distinct river intersection, and wherein each of said second set of feature points comprises a distinct river intersection.

30. A method for automatically conflating raster data with geospatial data, said method comprising:

identifying a first set of feature points associated with said raster data;

identifying a second set of feature points associated with said geospatial data;

identifying a set of matched control point pairs comprising feature points of said first set of feature points and corresponding feature points of said second set of feature points; and

deforming at least one of said raster data and said geospatial data to effectively align said set of matched control point pairs.

31. The method according to claim 30, said method further comprising:

generating a binary map representing said raster data, said binary map comprising a foreground and a background, and wherein said foreground comprises a road layer and non-line components;

extracting said road layer from said binary map; and

identifying said first set of feature points associated with said raster data using said extracted road layer.

32. The method according to claim 31, wherein said non-line components comprise data selected from the group consisting of buildings, symbols, text, and characters.

33. The method according to claim 30, said method further comprising:

generating a binary map representing said raster data, said binary map comprising foreground pixels and background pixels, wherein each of said foreground pixels is either a road line pixel or a non-road line pixel;

examining each of said foreground pixels to identify road line pixels, each of said identified road line pixels being defined as a foreground pixel which has neighboring foreground pixels located, within a predetermined distance, vertically parallel and horizontally parallel relative to an associated one of said foreground pixels;

generating a road layer comprising said identified road line pixels; and

identifying said first set of feature points associated with said raster data using said generated road layer.

34. The method according to claim 30, said method further comprising:

(a) generating a binary map representing said raster data, said binary map comprising original foreground pixels and original background pixels, wherein each of said original foreground pixels is either a road line pixel or a non-road line pixel;

(b) examining each of said original foreground pixels to identify road line pixels, each of said identified road line pixels being defined as an original foreground pixel which has neighboring original foreground pixels located, within a predetermined distance, vertically parallel and horizontally parallel relative to an associated one of said original foreground pixels;

(c) calculating a ratio defined by the number of said original foreground pixels relative to the number of said identified road line pixels identified in examining operation (b);

(d) increasing said predetermined distance;

(e) repeating said examining operation (b), said calculating operation (c), and said increasing operation (d) to generate a plurality of ratios; and

(f) if any of said ratios calculated in operation (c) increases relative to a previously calculated one of said ratios, said method further comprises indicating that said raster data includes double-line roads.

35. The method according to claim 31, wherein said extracting said road layer from said binary map comprises:

expanding dimensions of line components in said extracted road layer to reconnect disconnected portions of said line components;

reducing thickness of said line components in said extracted road layer while maintaining relative orientation of said line components and said binary map; and

thinning said line components until said line components have a substantially uniform thickness.

36. The method according to claim 35, wherein said extracted road layer comprises graphics, and said non-line components comprise data selected from the group consisting of buildings, symbols, text, and characters.

37. The method according to claim 30, said method further comprising:

identifying map scale of said raster data;

transforming said first set of feature points based on said map scale to generate a transformed first set of feature points;

transforming said second set of feature points based on resolution to generate a transformed second set of feature points; and

comparing said transformed first set of feature points and said transformed second set of feature points to identify said set of matched control point pairs.

38. The method according to claim 30, said method further comprising:

(a) partitioning said geospatial data into a subspace comprising a subset of said second set of feature points; and

(b) comparing said subset of said second set of feature points and said first set of feature points to identify said set of matched control point pairs; and

wherein

if no matching points are found, an area covered by said subspace is increased and said comparing operation (b) is repeated.

39. The method according to claim 30, said method further comprising:

identifying connectivity of line segments associated with each of said first set of feature points;

identifying connectivity of line segments associated with each of said second set of feature points;

determining which feature points of said first set of feature points and said second set of feature points have associated line segments with corresponding connectivity, said determining generating a subset of said first set of feature points and a subset of said second set of feature points; and

identifying said set of matched control point pairs by matching feature points of said subset of said first set of feature points with feature points of said subset of said second set of feature points.

40. The method according to claim 30, said method further comprising:

identifying direction of line segments associated with each of said first set of feature points;

identifying direction of line segments associated with each of said second set of feature points;

determining which feature points of said first set of feature points and said second set of feature points have associated line segments with differences in direction which fall within an identified threshold, said determining generating a subset of said first set of feature points and a subset of said second set of feature points; and

identifying said set of matched control point pairs by matching feature points of said subset of said first set of feature points with feature points of said subset of said second set of feature points.

41. The method according to claim 30, said method further comprising:

identifying feature point density of said first set of features points;

partitioning said geospatial data into a plurality of subspaces;

identifying feature point density of said second set of feature points in each of said plurality of subspaces;

determining which subspaces of said plurality of subspaces have a feature point density that falls within a particular range of point densities relative to said feature point density of said first set of feature points, said determining generating a set of potentially matching subspaces from said plurality of subspaces; and

identifying said set of matched control point pairs by matching feature points of said first set of feature points with feature points of said second set of feature points which are located in said set of potentially matching subspaces.

42. The method according to claim 30, said method further comprising:

identifying a localized distribution of said first set of feature points;

partitioning said geospatial data into a plurality of subspaces;

identifying a localized distribution of said second set of feature points in each of said plurality of subspaces;

determining which subspaces of said plurality of subspaces have a localized distribution that falls within a particular distribution range relative to said localized distribution of said first set of feature points, said determining generating a set of potentially matching subspaces from said plurality of subspaces; and

identifying said set of matched control point pairs by matching feature points of said first set of feature points with feature points of said second set of feature points which are located in said set of potentially matching subspaces.

43. The method according to claim 30, said method further comprising:

identifying connectivity and direction of line segments associated with each of said first set of feature points;

identifying connectivity and direction of line segments associated with each of said second set of feature points;

determining which feature points of said first set of feature points and said second set of feature points have associated line segments with corresponding connectivity and line direction, said determining generating a subset of said first set of feature points and a subset of said second set of feature points; and

identifying said set of matched control point pairs by matching feature points of said subset of said first set of feature points with feature points of said subset of said second set of feature points.

44. The method according to claim 30, said method further comprising:

identifying feature point density of said first set of feature points;

identifying feature point density of said second set of feature points in each of said plurality of subspaces;

identifying a localized distribution of said first set of feature points;

identifying a localized distribution of said second set of feature points in each of said plurality of subspaces;

partitioning said geospatial data into a plurality of subspaces;

determining which subspaces of said plurality of subspaces have a feature point density that falls within a particular range of point densities relative to said feature point density of said first set of feature points and which additionally have a localized distribution that falls within a particular distribution range relative to said localized distribution of said first set of feature points, said determining generating a set of potentially matching subspaces from said plurality of subspaces; and

identifying said set of matched control point pairs by matching feature points of said first set of feature points with feature points of said second set of feature points which are located in said set of potentially matching subspaces.

45. The method according to claim 30, said method further comprising:

partitioning said raster data into a first plurality of subspaces; and

partitioning said geospatial data into a second plurality of subspaces, wherein said deforming is performed by deforming each of said first plurality of subspaces with a corresponding subspace of said second plurality of subspaces to effectively align said set of matched control point pairs.

46. The method according to claim 30, wherein said second set of feature points are identified according to a method comprising:

generating a template based upon at least one of said first set of feature points and line characteristics associated with said at least one of said first set of feature points;

identifying geo-coordinates of said first set of feature points;

identifying approximate locations within said geospatial data of each of said first set of feature points;

generating a road-labeled image by identifying on-road regions portions of said geospatial data; and

comparing said road-labeled image with said template to identify on-road regions in said road-labeled image which have effectively similar dimensions and angles, relative to an orientation of said raster data, as said template, said comparing resulting in said identifying of said second set of feature points.

47. The method according to claim 46, wherein said line characteristics comprise line width of a line segment associated with said at least one of said first set of feature points.

48. The method according to claim 46, wherein said line characteristics comprise line angle of a line segment associated with said at least one of said first set of feature points, wherein said line angle is defined by the angle of said line segment relative to an orientation of said raster data.

49. The method according to claim 30, said method further comprising:

obtaining said raster data from a raster data source; and

obtaining said geospatial data from a geospatial data source.

50. The method according to claim 30, wherein said deforming deforms said raster data to effectively align said control point pairs.

51. The method according to claim 30, wherein said deforming deforms said geospatial data to effectively align said control point pairs.

52. The method according to claim 30, wherein said deforming deforms both said raster data and said geospatial data to effectively align said control point pairs.

53. The method according to claim 30, wherein said raster data comprises road network data.

54. The method according to claim 30, wherein said geospatial data comprises orthoimagery.

55. The method according to claim 30, said method further comprising:

creating georeferenced raster data based upon said deforming.

56. The method according to claim 55, wherein said georeferenced raster data comprises an image-aligned raster map.

57. The method according to claim 55, said method further comprising:

generating a composite image comprising said geospatial data and said georeferenced raster data.

58. The method according to claim 55, said method further comprising:

generating a composite image labeled with attribute data associated with said georeferenced raster data.

59. The method according to claim 30, said method further comprising:

finding geo-coordinates and scale of said raster data.

60. The method according to claim 30, wherein said raster data comprises georeferenced imagery, and said geospatial data comprises georeferenced imagery.

61. The method according to claim 30, wherein said raster data comprises a street map.

62. The method according to claim 30, said method further comprising:

identifying connectivity of line segments associated with each of said first set of feature points; and

identifying connectivity of line segments associated with each of said second set of feature points.

63. The method according to claim 30, said method further comprising:

identifying orientation of line segments associated with each of said first set of feature points, relative to said raster data; and

identifying orientation of line segments associated with each of said second set of feature points, relative to said geospatial data.

64. The method according to claim 30, wherein each of said first set of feature points comprises a distinct road intersection, and wherein each of said second set of feature points comprises a distinct road intersection.

65. The method according to claim 30, wherein each of said first set of feature points comprises a distinct railroad intersection, and wherein each of said second set of feature points comprises a distinct railroad intersection.

66. The method according to claim 30, wherein each of said first set of feature points comprises a distinct river intersection, and wherein each of said second set of feature points comprises a distinct river intersection.

67. The method according to claim 30, said method further comprising:

creating georeferenced raster data based upon said deforming; and

generating a composite image comprising said geospatial data and said georeferenced raster data, wherein said geospatial data is semi-transparent.

68. The method according to claim 30, said method further comprising:

creating georeferenced raster data based upon said deforming; and

generating a composite image comprising said geospatial data and said georeferenced raster data, wherein said georeferenced raster data is semi-transparent.

69. A computer-readable medium containing instructions for controlling a computer for conflating vector data with geospatial data according to a method comprising:

identifying a first set of feature points associated with said vector data;

identifying a second set of feature points associated with said geospatial data;

generating control point pairs, wherein each of said control point pairs includes a distinct one of said first set of feature points and a corresponding distinct one of said second set of feature points; and

deforming at least one of said vector data and said geospatial data to effectively align said control point pairs.

70. A computer-readable medium containing instructions for controlling a computer for conflating raster data with geospatial data according to a method comprising:

identifying a first set of feature points associated with said raster data;

identifying a second set of feature points associated with said geospatial data;

identifying a set of matched control point pairs comprising feature points of said first set of feature points and corresponding feature points of said second set of feature points; and

deforming at least one of said raster data and said geospatial data to effectively align said set of matched control point pairs.

71. A system for conflating vector data with geospatial data, said system comprising:

means for identifying a first set of feature points associated with said vector data;

means for identifying a second set of feature points associated with said geospatial data;

means for generating control point pairs, wherein each of said control point pairs includes a distinct one of said first set of feature points and a corresponding distinct one of said second set of feature points; and

means for deforming at least one of said vector data and said geospatial data to effectively align said control point pairs.

72. A system for conflating raster data with geospatial data, said system comprising:

means for identifying a first set of feature points associated with raster data;

means for identifying a second set of feature points associated with geospatial data;

means for identifying a set of matched control point pairs comprising feature points of said first set of feature points and corresponding feature points of said second set of feature points; and

means for deforming at least one of said raster data and said geospatial data to effectively align said set of matched control point pairs.