# Presentation: 069630

## Development of a Blunder Detection Approach for Automated Point Matching During Vector-to-Image Data Integration

- Lawrence V. Stanislawski
- Michael P. Finn
- E. Lynn Usery
- Paul M. Robinette

**U.S. Department of the Interior**
**U.S. Geological Survey**

- lstan@usgs.gov, mfinn@usgs.gov, usery@usgs.gov, probinette@usgs.gov
- http://carto-research.er.usgs.gov/

## Outline

**Goals and Objectives**
**Approach**
**Test Data and Methods**
**Preliminary Results**
**Conclusions**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

## Goals and Objectives

***The National Map***** will consist of integrated datasets**
**Current, complete, consistent, accurate**
**True geographic position**
**Various data sources**
**Consortium of data stewards**
**Project objective is to develop and test automated systems and algorithms to shift features from one dataset into alignment with another to achieve integration**
**Focus: Automate integration of vector roads to orthoimage data**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
During recent years, the U.S. Geological Survey (USGS) has been remodeling the way it provides geospatial data to the nation through The National Map program (USGS, 2006). The vision of The National Map is to ensure that “current, complete, consistent, and accurate” geographic base information is readily available through a system of web-based interfaces (USGS, 2006). To the extent possible, geospatial data will be aligned to its true geographic position, thereby eliminating any cartographic offsets inherent with some source products. The National Map data will be derived from various sources by a consortium of data stewards. 

Thus far, our integration research has included 
	empirical exploratory analysis to qualitatively and quantitatively assess the extent of the data integration problem, 
	development of a hypothesis for data integration based on resolution and accuracy, and 
	development and testing of automated systems and algorithms to shift features from one dataset into alignment with another to achieve integration 
This presentation focuses on the last topic for specific data types. That is, we are developing and testing automated processes to horizontally integrate vector road data to orthoimage data

## ApproachAutomate integration of vector roads to orthoimage data

**Emulate USC method to auto-match image intersection points to corresponding vector intersection points ****(**Chen, C.-C., C. Shahabi, and C.A. Knoblock 2003. _Automatically conflating road vector data with high resolution orthoimagery_. Report to U. S. Geological Survey on Grant No. 03CRSA0631. University of Southern California, Los Angeles.)
**Process includes a vector median filtering approach to exclude inappropriate match pairs**
**Test another approach to filter undesired point matches: localized affine transformation**
**K-means clustering technique with weighted affine transformation**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Through a cooperative agreement with USC, we have emulated an automated approach that matches image intersection points to corresponding vector intersection points in a subset of a road layer.
The process includes a vector median filter to remove undesirable matching pairs. However, for this subproject, we have been testing another filtering process that employs local affine transformations to the matching point pairs. A k-means clustering technique is used to build local clusters of match pairs, and then a weighted affine transformation is computed for each cluster.

## Test Data

**High-resolution datasets**
**1.5 km x 1.5 km 0.33-meter resolution color orthoimage (133 cities of HSIP, 2004)**
**MDOT vector roads (magenta).**
**98 road intersections (green)**
**Urban residential area near Ballwin MO (west of St. Louis).**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Thus far, our test data includes:
High-resolution datasets
1.5 km x 1.5 km 0.33-meter resolution color orthoimage (collected for 133 priority cities of Homeland Security Infrastructure Program in 2004)
Vector roads from Missouri Department of Transportation (magenta), which is the most accurate source for this area.
98 road intersections (green)
Urban residential area near Ballwin MO (just west of St. Louis).

## Lower resolution datasets
Nine 5 km x 5 km 1-meter resolution CIR orthoimages (collected for NAIP, 2004) during “leaf on” season.
Vector DLG roads which were collected years before images (green)
776 road intersections
Urban and rural area around Foristell, MO

**Nine 5 km x 5 km 1-meter resolution CIR orthoimages (collected for NAIP, 2004) during “leaf on” season.**
**Vector DLG roads which were collected years before images (green)**
**776 road intersections**
**Urban and rural area around Foristell, MO**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Lower resolution datasets
Nine 5 km x 5 km 1-meter resolution CIR orthoimages (collected for National Agriculture Imagery Program, 2004), during leafy season. (IrRG bands vs. RGB regular color)
	(Horizontal accuracy of the images is purported to be within+/- 3 m of reference orthoimages (USGS-NDOP DOQ) for 90% of points measured. Meets 	NMAS.)
Vector roads overlaying these images is derived from USGS Digital Line Graph (DLG) data (green). Collection dates vary. Therefore, vectors are missing many subdivision roads and other road improvements.
776 road intersections.
Urban and rural area around Foristell, MO

## Lower resolution datasets
Roads out of date with images

**Roads out of date with images**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Test Data**

**Notes:**

This example shows where vector DLG roads are not up to date with road improvements depicted in the image data.

## MethodsRoad Vectors to Image Integration

**Classify image pixels as road or non-road based on hue, saturation, and value.**
**Locate road intersection points in the vector data.**
**Buffer vector intersection points and create a vector image template (VIT) of road segments within each point buffer that reflects road widths as defined by the vector feature type or associated attributes.**
**For each VIT, find the image pattern within a local area of the classified image that best matches the VIT. If a match is found, store the matching image pattern centroid coordinates and the associated vector intersection coordinates.**
**Using the k-means approach, cluster image match points into groups that are larger than 30 and less than or equal to 40.**
**Check if any blunders are detected in each cluster by using the weighted affine transformation to fit the vector intersection points to the matching image points.**

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide lists the main processes in the vector-to-image integration strategy that implements a local affine transformation (LAT) to filter undesireable vector-to-image intersection matches.
Classify image pixels as road or non-road based on hue, saturation, and value. (Bayesian classifier)
Locate road intersection points in the vector data.
Buffer vector intersection points and create a vector image template (VIT) of road segments within each point buffer that reflects road widths as defined by the vector feature type or associated attributes.
For each VIT, find the image pattern within a local area of the classified image that best matches the VIT. If a match is found, store the matching image pattern centroid coordinates and the associated vector intersection coordinates (Also stores a correlation value indicating the number of road pixels falling into the ‘match’ template.
Using the k-means approach, cluster image match points into groups that are larger than 30 and less than or equal to 40.
Check if any blunders are detected in each cluster by using the weighted affine transformation to fit the vector intersection points to the matching image points.

## MethodsAutomated Process to Identify Image Road Intersections

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide graphically depicts the automated process for identifying road intersections. 
Intersections are identified on the vector road layer and a supervised image classification process identifies road pixels on the image. For each vector intersection, a template is generated based on feature attributes, and localized template matching process identifies a best match from which an image intersection is extracted. Window size and search distance depend on image characteristics and how well the datasets are integrated before processing.
The number of overlapping road pixels falling within the template is used to determine the best match.  This ‘vector template to image correlation’ value is recorded for each intersection, along with the pattern centroid coordinates.

## MethodsExample of Localized Template Matching

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This figure shows an example of a vector image template, which is then shifted around a local area of the road image to select a best intersection pattern match.

## MethodsAffine transformation on cluster of intersections to detect blunders

- The method being used to modify the weights of suspected outlying observations in the weighted affine transformation was developed by the Geodetic Institute of Denmark and is "especially designed to eliminate gross errors“. The local affine transformation fits the vector intersections to corresponding auto-interpreted image intersections in a cluster.
- If
-     then the coordinate is a flagged and it’s weight is modified,
- where *r* is the residual of a vector intersection coordinate, *w* is the weight assigned to the coordinate, *c* is a
- 	constant of 2.5, and *    *is the* a posteriori* estimate of the reference standard deviation.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Once we have all the matching pairs identified, we generate local clusters of intersections using k-means clusters.  Then, a weighted affine transformation is computed for each cluster to detect blunders. The method being used to modify the weights of suspected outlying observations was developed by the Geodetic Institute of Denmark and is "especially designed to eliminate gross errors“.  The affine transformation fits the vector intersections to corresponding auto-interpreted image intersections.  During this process,

During the transformation process of a cluster, if the ABSOLUTE VALUE OF A VECTOR COORDINATE RESIDUAL TIMES THE SQUARE ROOT OF THE COORDINATES WEIGHT DIVIDED BY THE STANDARD DEVIATION OF UNIT WEIGHT IS LESS THAN THE CONSTANT OF 2.5, THEN THE COORDINATE IS FLAGGED AND IT’S WEIGHT IS MODIFIED.

In essense, the weight of a flagged coordinate is reduced to eliminate the coordinates affect on the transformation.

If a vector intersection coordinate is flagged, then the intersection match pair is considered undesirable, and filtered out.

## ResultsHigh Resolution Data near Ballwin

- All correct image intersections manually identified (MI) (cyan triangle)
- Radial discrepancies between MI and auto-interpreted (AI) image intersections (green square) computed and averaged.
- Radial discrepancies between MI and vector intersection (VI) points (blue square) computed and averaged.
- Largest MI to VI discrepancy shown.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
All correct image intersections were manually identified (MI) (cyan triangle).
Radial discrepancies between MI and auto-interpreted (AI) image intersections (green square) were computed and averaged.
Radial discrepancies between MI and vector intersection (VI) points (blue square) were also computed and averaged.
This image shows the Largest MI to VI discrepancy.

## ResultsHigh Resolution Data near Ballwin

- K-Means Clusters
- Three clusters with 35, 30, and 38 points.
- Green triangle cluster had 7 flagged points (yellow) from the weighted affine transformation.
- Flagged points did not include the points with the largest MI to AI discrepancies.
- The flagged points had MI-AI discrepancies of 11.4, 17.6, 21.4, 23.2, 23.9, 28.3, and 29.8 meters

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Here we see the K-Means Clusters
Clustering generated three clusters with 35, 30, and 38 points.
Green triangle cluster had 7 flagged points (yellow) from the weighted affine transformation.
Flagged points did not include the points with the largest MI to AI discrepancies, which was about 45 m. The flagged points had MI-AI discrepancies of 11.4, 17.6, 21.4, 23.2, 23.9, 28.3, and 29.8 meters, which are some of the larger discrepancies but not among the largest.

## ResultsHigh Resolution Data near Ballwin

- Manually Identified – Auto Interpreted Discrepancy Distribution

- Manually Identified – Auto Interpreted Discrepancy Distribution, without LAT flagged intersections

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide shows the frequency distributions of discrepancies between manually identified and auto-interpreted image intersections. All discrepancies are shown in the top distribution, and the lower distribution does not include the flagged intersections.

## ResultsHigh Resolution Data near Ballwin

- Removing pairs flagged with LAT slightly reduces the average discrepancies of the AI points to the correct intersections (12.4 m (blue) to 11.6 m (red)).
- Rubbersheeting the vector data to AI points with or without flags degrades positional accuracy (average MI – VI 5.8 m (cyan))

- Discrepancy Summary

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This chart shows the minimum, maximum, average, and standard deviations of discrepancies. Removing match pairs that were flagged with LAT (with values shown in red) slightly reduces the average discrepancy of the auto-interpreted intersections to the correctly identified intersections. It reduces from 12.4 meters as shown in blue to 11.6 m, as shown in red). 
On average, performing the rubbersheeting process through the piecewise linear transformation to fit the vector roads to the auto-interpreted points degrades the integration of the vector road intersections with the manually identified image intersections. Without fitting the roads to the image, the average discrepancy of the road intersections to correctly identified intersections is is 5.8 m, as shown in cyan.

Intersection that were flagged with the local affine transformations have an average discrepancy between the auto-interpreted intersections to the manually identified intersections of 22.2 meters, as shown in beige. This average is nearly twice the size of the average discrepancy for all intersections.

## ResultsHigh Resolution Data near Ballwin

- Piecewise linear fit of vector roads to auto-interpreted intersections with improper matches (yellow).
- Original roads in pink.
- Auto-interpreted points off in same direction, therefore not flagged with LAT

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Piecewise linear fit of vector roads to auto-interpreted intersections with poor matches (yellow).
Original roads in pink.
Auto-interpreted points off in same direction, therefore not flagged with LAT

## ResultsHigh Resolution Data near Ballwin

- Piecewise linear fit (yellow) of vector roads to auto-interpreted intersections in area where LAT flagged intersections (cyan).
- Original roads in pink.
- Eliminating flagged points would improve fit.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide shows the fitted roads in the area where the local affine transformation flagged intersections in cyan. Eliminating these flagged intersection would improve the fit in this area.

## ResultsHigh Resolution Data near Ballwin: 50% VMF filter

- K-Means Clusters
- Two clusters each with 30 and 30 points.
- Green triangle cluster had one flagged points (bright cyan) from the weighted affine transformation.
- Flagged points did not include the points with the largest MI to AI discrepancies.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Also did the same analysis using only the intersections remaining after the 50 percent vector median filter. The vector median filter was used to used to filter 50 percent of the auto-interpreted intersections having discrepancy vectors that were the most different in direction and magnitude from the median discrepancy vector. This filter left 49 intersections. K-Means Clustering generated 2 clusters, as shown, both having 30 points. Notice that some points were used in both clusters.
Weighted affine transformations flagged one intersection in one cluster, which is shown in cyan. The flagged intersection has a discrepancy of 6 meters from the correctly identified intersection.

## ResultsHigh Resolution Data near Ballwin: 50% VMF filter

- Manually Identified – Auto Interpreted Discrepancy Distribution

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide shows the frequency distributions of discrepancies between manually identified and auto-interpreted image intersections. Notice that the filter reduced the average discrepancy from 12.4 m to 4.7 meters. However, some auto-interpreted intersections that were furthest from the manually interpreted intersections still remain ( some with more that 40 m)

## ResultsHigh Resolution Data near Ballwin 50% VMF filter

- Removing pairs flagged with LAT does not affect average discrepancy of the AI points to the correct intersections (4.7  m) (blue and red).
- Transforming data to AI points with or without flags slightly improves positional accuracy (average MI – VI 5.8 m (cyan))

- Discrepancy Summary

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This chart shows the minimum, maximum, average, and standard deviations of discrepancies from the 50% VMF. Removing match pairs that were flagged with LAT does not affect the average discrepancy of the auto-interpreted intersections to the correctly identified intersections, which are shown in blue. 
On average, performing a piecewise linear transformation to fit the vector roads to the auto-interpreted points that were not filtered improves the integration of the vector road intersections with the manually identified image intersections. Integration improves average discrepancy from 5.8 to 4.7 meters at the intersections that were included in the match.

Again the intersection flagged by the local affine transformations has a discrepancy of 6 meters, which is larger than the average of all discrepancies.

## ResultsHigh Resolution Data near Ballwin 50% filter

- After the fit, discrepancies between all  vector intersections to manually identified intersections average 5.5 m (blue).
- Before fit, discrepancies between all  vector intersections to manually identified intersections average 5.8 m (red).

- Discrepancy Summary

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
However, what happened at the intersections that were not included in the piecewise linear transformation?

Overall all intersections, the automated piecewise linear transformation using the 50% vector median filter has an average discrepancy of 5.46 meters between the 98 fitted vector road intersections and the manually identified image intersections. Which is a slight improvement over the average discrepancy of 5.77 meters before the fit. However, the fitted intersections have a maximum discrepancy that is about 10 meters larger than the maximum from the non-fitted data. This happens at a location where the a road improvement is evident in the image  where it does not exist in the vectors.

## ResultsHigh Resolution Data near Ballwin: 50% filter

- Piecewise linear fit of vector roads to auto-interpreted intersections (yellow).
- Original roads in pink.
- Problem matches were removed from this area by 50% VMF.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Piecewise linear fit of vector roads to auto-interpreted intersections (yellow).
Original roads in pink.
Problem matches were removed from this area by 50% VMF.

## ResultsHigh Resolution Data near Ballwin: 50% filter

- Piecewise linear fit (yellow) of vector roads to auto-interpreted intersections in area LAT flagged intersection (cyan).
- Original roads in pink.
- Eliminating flagged point degrades the fit at this intersection.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
This slide shows the fitted roads in the area of the local affine transformation flagged intersection. Eliminating this flagged intersection degrades the fit at this intersection.

## Results: 1-m resolution CIR image data near Foristell, MO: 50% filter

- K-means clusters with flagged intersections highlighted with orange.

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Looking quickly at the Foristell MO data where we are integrating DLG roads with 1-m Color infrared images. 390 total intersections remaining after the 50% filter. This slide shows the 15 K-means clusters that were generated, which range from 30 to 38 points. The 12 intersections flagged by the weighted affine are highlighted with orange.

## Results: 1-m resolution CIR image data near Foristell, MO: 50% filter

- Flagged point (orange)
- Auto-interpreted points (cyan)

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Many points are confused with buildings and other intersections within search window.

## Concluding Remarks

- Auto-interpreted intersection location algorithm needs refinements to eliminate inappropriate matches:
- Incorporate an inverse distance weight value to classified road image that identifies road center pixels, and give road center pixels higher weight when computing correlation match values,
- Do not include intersections where it is too congested with road pixels,
- Do not include matches where the vector template ‘correlation’ value is less than a constant.
- K-means clustering algorithm successfully generated localized clusters of road intersection points.
- When no other filter was applied, a localized weighted affine transformation on k-means clusters of 30 to 40 points, flagged some inappropriate intersection matches.
- Further research on the use of k-means clusters with the weighted affine transformation to filter out inadequate vector to image match points is needed.  (Vary cluster size and blunder detection constant.)

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Based on these data concerning our automated processes to integrate vector road with orthophoto images, we can make some concluding statements:
1.Auto-interpreted intersection location algorithm needs refinements to eliminate inappropriate matches:
Incorporate an inverse distance weight value to classified road image that identifies road center pixels,
Do not include intersections where it is too congested with road pixels,
Do not include matches where the vector template ‘correlation’ value is less than a constant.
2. K-means clustering algorithm successfully generated localized clusters of road intersection points.
3. When no other filter was applied, a localized weighted affine transformation on k-means clusters of 30 to 40 points, flagged some inappropriate intersection matches.
4. Further research on the use of k-means clusters with the weighted affine transformation to filter out inadequate vector to image match points is needed.  (Vary cluster size and blunder detection constant.) 

## GA DOT on Ortho (12K)

- GA DOT on Ortho (12K)

## ResultsHigh Resolution Data near Ballwin

- Vector template ‘match’ values (X-axis) to radial discrepancy between manually-identified and auto-interpreted intersections (Y-axis)
- Correlation -0.48
- Intersections flagged by weighted affine highlighted (pink)

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Vector template ‘match’ values (X-axis) to radial discrepancy between manually-identified and auto-interpreted intersections (Y-axis)
Correlation -0.48
Intersections flagged by weighted affine highlighted (pink)

## Results1-m resolution CIR images near Foristell

- Vector template ‘match’ values (X-axis) to radial discrepancy between manually-identified and auto-interpreted intersections (Y-axis)
- Correlation 0.007

*ASPRS 2007 Annual Conference, May 7-11, Tampa, FL*

**Notes:**
Vector template ‘match’ values (X-axis) to radial discrepancy between manually-identified and auto-interpreted intersections (Y-axis)
Correlation 0.007

## Development of a Blunder Detection Approach for Automated Point Matching During Vector-to-Image Data Integration

- Lawrence V. Stanislawski
- Michael P. Finn
- E. Lynn Usery
- Paul M. Robinette

**U.S. Department of the Interior**
**U.S. Geological Survey**

- lstan@usgs.gov, mfinn@usgs.gov, usery@usgs.gov, probinette@usgs.gov
- http://carto-research.er.usgs.gov/