 |
 |
 |
 |
 |
 |
 |
|
Project: Crew Research Project Student Researchers: Jennifer Davison, Kelly Hasler Advisors: Karen T. Sutherland Ph.D Institution: University of Wisconsin--La Crosse |
||
|
|
Humans are very good at picking out composite features to use as landmarks in unstructured environments and to use those landmarks to navigate or identify objects around themselves. The goal of this work was to decide what features in a typical unstructured environment an automated navigation system could use as landmarks and how properties of those features could be combined to provide localization superior to that obtained by using beacons or point features.
Account of the process used in completing the research
Most of the previous research using landmarks in outdoor environments has used point features, such as mountain peaks, as opposed to composite features. Point features are easier to identify but produce more error when used for localization than do composite features. To identify a composite land feature, a precise definition must be known. Since no clear, formal definitions existed for any of these features, they had to be formulated. By interpreting previous work and consulting with researchers in the area, the terms for such features, such as ridge line, saddle, circ and bowl, and their definitions were developed. The features were separated into two categories: Primitives and Formations. The Primitives are themselves composite while the Formations are groupings of Primitive composite features. It was decided to focus this work on ridge lines since the La Crosse area provided numerous examples with which to work.
Digital images of the bluffs surrounding La Crosse were taken. An image library was created consisting of images taken at multiple locations and from different viewpoints at each location in order to clearly capture distinguishable land features within the bluffs.
USGS (United States Geological Survey) elevation data for the La Crosse area was obtained and used to render a terrain map of the area. The data used was 7.5 minute DEM (Digital Elevation Model) with readings taken every 30 meters. This allowed for simulated terrainsto be rendered covering the same areas as the images in the library and for the elevation at any given point to be electronically available.
The digital images were then converted into a form that allowed for easy access to the actual pixel values. They were cropped so that extraneous features in the image were eliminated and ridge lines were featured. The cropped images were then converted from color to grey scale, then into a matrix of numerical values with each value ranging from 0, representing black, to 255, representing white. These pixel values were then written into a text file. Visual patterns of pixel values were visible in this text file. An algorithm was developed to color different ranges of pixel values different colors. It was found that there was a unique number pattern that represented the ridge line. The unique pattern consisted of a contrasting pattern of lighter number values located in close proximity to darker number values. Although ridge lines along the sky line were easy to find, these patterns were also apparent along ridge lines that did not border the sky.
Finally, pattern recognition algorithms were developed in an attempt to identify this unique pattern that represented the ridge line. The goal was to produce from the pixel intensity values a single entity which could be labeled ``Ridge line''. Although ridge lines on the map as well as on the scene rendered from the map data are shown as lines, they appear as blobs in the actual images. Once the blobs are identified, they must be compared in some way to the linear map data in order to match the view to the map.
The first algorithm pulled out pixels with values exceeding a given threshold. There were two problems with this approach:
1. When images are taken in an outdoor setting, there is no control over the light intensity. Images existed in the library with ridge lines visible to the human eye which had no pixel values over the threshold.
2. It was then necessary to add another level of processing to the algorithm in order to decide which of these thresholded pixels were part of the ridge line and which were outliers and to connect the legitimate pixels into a single entity.
At this point, it was decided that, to deal with the light intensity problem, instead of an absolute threshold, a difference measure should be used, pulling out pixels which differed from their surroundings by a percentage of the total range of pixel values. The second problem was dealt with by grouping pixels into a blob, using a standard region growing algorithm. A ``Ridge line signature'' was then developed for each connected blob for matching with the map ridge lines.
Conclusions and results achieved
A set of rigorous definitions for composite features in outdoor environments was developed.
It was found that there is a unique pixel value pattern when a ridge line appears in a digital picture and this pattern can be extracted using a pattern recognition algorithm.
After examining the U.S. Geological Survey data available, it was clear that the data is smoothed to the point that many land features commonly recognized by a human observer, such as cliffs and outcroppings of rock are lost in the smoothing. Although the U.S. Geological Survey data might be of more value if it included more data using smaller intervals than 30 meters, the additional data would then add to any required processing time.
It should therefore be noted that using the USGS data for localization on a map will require that large scale features be utilized rather than some of the smaller distinguishable features so often used by humans.
Weather conditions can change the view significantly. For example, when the sky is overcast, the image is dark, leading to a smaller range of pixel values and less likelihood of picking up differences that signify ridge lines. A scaling of the pixel values can often widen the spread, but only if there are not too many outliers to skew the distribution. As an example, an image taken with an overcast sky might contain pixels in the range of 0 to 150. By scaling the pixel values, the range can be changed to 0 to 255, providing a larger difference in values along the ridge lines. However, a patch of white in the image, such as a piece of pavement in the foreground, produces outliers and will skew the distribution and mitigate the effect of the scaling. Vegetative growth can also change the look of the surroundings. A tree line may be mistaken as a ridge line when analyzing the digital image. However, it should be noted that human navigators also occasionally mistake tree lines for ridge lines.
Department of Computer Science
University of Wisconsin--La Crosse
La Crosse, WI 54601