Highlight Article
Feature databases store the identity, location, and characteristics of the natural and man-made features in imagery. To be useful, features must be tied to the ground and measured with both relative and absolute accuracy. The particular end-product dictates the relative importance and needed detail of different types of features.
Feature databases make it possible for cartographers to build maps and GIS databases for urban and regional planners, for civil and military applications, telecommunications, and a host of other applications. Simulation and modeling practitioners use three-dimensional feature databases for visualizing scenes in three dimensions, building virtual worlds (based on real images and features), targeting, and walkthroughs for mission planning and mission rehearsal.
The recent explosive growth of computing power is making it possible to deliver these solutions to the desktop. Photorealistic scenes can now be rendered on workstations. The need for accurate and detailed databases grows with each new application.
Improving Productivity
Extracting features for databases is often the most time-consuming and expensive
step in the production of image-based
products. Depending on the application, it can take days or months to build
feature databases.
The key to improving productivity is introducing automation into the feature extraction process. Several years ago, GDE Systems and Helava embarked on a major effort to re-engineer and redesign the database generation process to significantly reduce the time it takes to extract features and populate feature databases.
Productivity improvement in feature extraction comes not from a single dramatic change, but from incremental improvements in a number of areas. Some of the more important areas are user interfaces, interactive feature editing tools, process improvements, knowledge bases, and image understanding tools.
User Interfaces
Effective user interfaces optimize interactions between the operator and the
feature extraction workstation. Interfaces optimize interactions by minimizing
and making intuitive required inputs, and providing clear feedback on the
progress and status of operations. Subtle factors, such as how feature models
are selected and represented, how many and what kind of feature points need
to be designated by the operator, and how the data are entered, are also
optimized in effective interfaces.
For example, our Single Feature Tool extracts the complicated outlines of bodies of water after the operator invokes the tool, clicks on any interior point in the lake, and on points that form a bounding rectangle. In contrast, a manual tool would require that the operator painstakingly trace around the lake.
The User Interface should permit rapid data entry by permitting some input inaccuracy on the user’s part that is automatically refined. We’ve found that giving the operator a variety of tools works best to improve productivity, especially those that move a floating mark to the image surface, that move line segments towards edges, that square corners, that make adjacent sides of buildings perpendicular, and that make opposite sides parallel. These and similar tools ensure a more powerful interface and reduce the time to accurately produce feature databases.
Interactive Feature Editing Tools
Efficient interactive feature editing tools are used by the operator to correct
inaccuracies in the results of automated
delineations, or from manual feature delineations. Operators need tools to
modify features including but not limited to 1) moving individual points, 2)
rotating, scaling, and translating features, 3) copying feature segments, and
4) deleting extraneous feature elements. It is possible to use inference engines
that direct the selection and parameters of interactive editing tools based
on the confidence levels and probable causes of inaccuracy reported by image
understanding tools to improve operator efficiency and tool acceptance.
"Productivity improvement in feature extraction comes not from a single dramatic change, but from incremental improvements in a number of areas."
Process Improvements
The process of generating a simulation database from raw imagery can be broken
down into eight steps: ingest the imagery, control it, extract terrain, extract
features and feature attributes, convert the terrain matrix to polygons,
reconcile the features with terrain, thin the resultant database, and reformat
the output. While this paper focuses on feature extraction, improvements
in other steps of the simulation database generation process can positively
affect feature extraction: for example, photogrammetric improvements can
increase the accuracy of features extracted from the image.
Knowledge-based Systems
While each image is different, it is possible to capture general feature extraction
expertise in knowledge-based systems. These systems can be used to direct
algorithmic flow and optimize parameter settings for feature extraction tools.
The knowledge base uses the objectives of the operator, the results of previous
operations, and the current state of the system to identify appropriate scenarios
for the current extraction process. Knowledge-based inference engines incorporate
rules that an operator typically follows when extracting features, or performing
other image operations like terrain extraction.
Chains of processing operations can be incorporated into the rule- based inference engine,so that each time the analyst performs an operation, the set of processes performed follow the appropriate decision path. Rules can be built into the system that determine input parameters for the next step in a processing chain based on prior results. Over time, the set of rules included in the knowledge base permits increasing levels of automation. We found that a well-developed set of inferences can result in dramatic speed and accuracy improvements.
To be useful, knowledge bases must be modifiable by the user, flexible, and adaptable to different classes of features, different backgrounds, and different image qualities. Storing parameters for different situations will free the operator from having to track and enter detailed parameter values about which the operator is neither knowledgeable nor concerned. Knowledge bases also have the added value of increasing consistency between operators to ensure the production of a coherent product.
"...a well developed set of inferences can result in dramatic speed and accuracy improvements."
Image Understanding Tools
Image understanding tools automate aspects of the feature extraction process.
We define “image understanding” to include any image processing
or analysis algorithm that facilitates feature extraction. Tools can be applied
singly or in processing chains. Features on this issue’s cover photo
were extracted with image understanding tools currently under development
for production use.
Before introducing new tools, they are validated by comparing operator performance before and after tool inclusion. A representative sample of users and scenarios ensures a realistic assessment. Measures of accuracy, speed, and operator fatigue quantify the tool’s utility. Those tools found to be beneficial are introduced into production software.
When developing new production algorithms, our thesis is to exploit all the information available including photogrammetnc information, camera parameters, and image metrics. The remainder of this paper focuses on image understanding tools for feature extraction.
Manual, Semi-Automated, and Automatic Tools for Feature Extraction
Image understanding tools form a continuum based on the relative influence
of operator and algorithm. Manual tools are entirely driven by the operator
who must lay down discrete points precisely and extract all features without
the benefit of image understanding algorithms. For example, when defining a
flat rooftop using the manual method of extraction, the operator must precisely
mark the vertex at each corner of the rooftop.
Semi-automated feature extraction (SAFE) tools combine operator actions with automatic computations. The premise of this approach is to refine vector data extracted by an operator and to reduce the steps required to collect the vectors that define the extracted features. For the case of the flat rooftop, two of the potential uses of SAFE are 1) the operator approximates each corner, and algorithms adjust the roof boundaries towards the true boundaries, and 2) the operator marks a starting point on the roof, and an algorithm establishes the boundaries of the rooftop. Both manual and fully automated systems have limitations. Operators find it difficult to enter precise points, and automated algorithms need oversight to adjust for suboptimal results, false alarms, or missed detections. Semi-automated tools, however, tend to perform well in these conditions.
Fully automated systems extract features without operator intervention. While there are many powerful and creative image understanding tools, complete automation is not achievable with today’s tools. Fully automated tools are too slow and are not yet capable of dealing with a wide enough variety of image variations to produce accurate results in a majority of cases without operator interaction.
However, the user can combine automatic tools with interactive refinement to produce very powerful solutions. Some are already doing this for automatic terrain extraction. Automatic terrain extraction tools capture 80-99% of the terrain. Interactive terrain extraction tools are then used to refine the results. A similar approach can be applied to automatic feature extraction. For the case of our flat rooftop features, an automated solution could request that an algorithm find all of the roof tops in a scene. A suite of editing tools could then be used to clean up any of the blunders of the algorithm. This process could be improved by introducing the concept of tagging results as accurate or potentially inaccurate, based on the confidence of the extraction algorithm.
Existing Tools
SOCET SET® is a tool kit which includes a wide variety of image understanding
tools.
The Rooftop Tool
This tool simplifies the extraction of flat roofs by accepting points near
the corners of the rooftops, instead of requiring precise x, y, and z placement.
Each of the line segments formed by these points are automatically translated
and rotated to conform to the edge of the feature, and their intersections
form the more precise corners of the rooftop. We provide the operator with
options to make adjacent sides perpendicular or opposite sides parallel.
Operator tests indicate that this tool more than doubles the speed at which rooftops can be extracted, with a significant reduction in operator fatigue, when compared with traditional manual methods.
The Edge and Road Refinement Tool
This tool expands the types of features to which the Rooftop Tool applies.
Any features with well- defined edges, such as paths, trails, roads, or rivers
can be extracted with the linear refinement tool. To use this tool, the operator
designates a few points near the edge of the feature. The algorithm then
iterates to form a multi-segmented edge that closely conforms to the edge
of the feature. Unlike the Rooftop Tool, the Edge and Road Refinement Tool
does not assume a closed polygon.
The Single Feature Tool
Region growing algorithms have long been used in image processing to segment
images into homogeneous areas. An algorithm can start at a point, and grow
to all points that are the same color (or brightness or reflectance) at the
same elevation. Bodies of water including lakes and ponds meet the constant
elevation criteria. To use the Single Feature Tool, the analyst clicks a
floating mark within the feature of interest, and then specifies a bounding
rectangle to speed operation. The region grower fills in the feature and
applies a polygonal border tracker to the grown region to produce the final
boundary of the feature. This process is much faster than a precise and tedious
manual extraction.
Tools Under Development
Some of the methods and image-understanding tools under development are Model-Based
Extraction tools for Buildings and Roads, and Global Least Squares Matching
for Feature Extraction.
Model-Based Extraction Tools for Buildings and Roads
There are many influences on the appearance of an object in an image, including
illumination, object material, and the image acquisition system. Model-based
algorithms seek to exploit not only the knowledge of the imaging process,
but also the constraints and relations that define the object. Simulation
and modeling of the acquisition of the image containing the object of interest
provides the necessary clues to develop model-based feature extraction tools.
This reduces the feature extraction problem to finding an object’s
locations and characterizing its attributes.
Operators can identify objects in imagery more rapidly than fully automated tools. Semi-automated model-based tools rely on the operator to identify the object type and location. The operator lays down a seed, or starting point, for the extraction algorithm, which extracts the detailed attributes of the object. Automated techniques may then be applied to predict and quantify the fit of the model to a large number of local instances. The best instance- is the one that accounts for the largest number of pixels in the object.
"It is now possible to distinguish objects of similar shape based on heir relation to the sources of llumination."
Traditional image understanding algorithms use edge detection or edge following techniques to characterize object geometry. These techniques fail for certain illumination angles, or when the object of interest is the same color as its background. Radiometric modeling overcomes these problems by capturing the underlying physics of the light, object, and image acquisition interactions. Model parameters including sun angles, object composition, and film parameters (the film transfer function) can be combined to create a complete model of an object within its radiometric environment. When these elements are combined with image geometry and edge techniques it is possible to distinguish objects of similar shape based on their relation to the sources of illumination. Combining geometry and radiometry aspects in one coherent model yields powerful image understanding tools.
"Global least squares matching can be used to introduce logical constraints on the data—"
Model-Based Building Extraction Tool
The model-based building extraction tool provides a means to rapidly extract
buildings in a scene. The operator specifies constraints on building size,
shape and material, and places one or two points on the rooftop. The tool
constructs the model of the three-dimensional rooftop, and initiates a search
of the area. The model that best matches the imagery is presented to the
operator for acceptance, rejection, or editing. Upon acceptance, the result
is added to the feature database.
Model-Based Road Following Tool
This tool models road sections. The operator places a starting point on the
road segment. The tool then models the road radiometry and evaluates the
road width and direction. Road sections are then predicted and compared to
the imagery while maintaining limits on the rate of curvature and road material
variations. This process continues until no further sections of road can
be identified, or the boundary of the image is detected.
Global Least Squares Matching for Feature Extraction
Effective three-dimensional feature extraction requires accurate elevation
estimation. A fundamental step to deriving image data is finding conjugate
point pairs in stereo imagery that correspond to points in object space.
The result of searching for conjugate pairs without constraints are unreliable.
Global least squares matching can be used to introduce logical constraints
on the data—for example, elevation changes are assumed to be gradual
at most points in a scene (this is less true at the side of a cliff or an
edge of a building). The problem of finding conjugate pairs can be represented
mathematically as a series of nonlinear simultaneous equations. The equations
are linearized by taking the first terms of the Taylor Series expansion,
and applying array algebra techniques that provide very high- speed solutions
to the conjugate pair finding problem for elevation estimation.
After Global Least Square Matching has been applied to a stereo pair, the operator can enter seed points indicating roof and non-roof areas. The operator can then apply an algorithm that segments the image into roof and non-roof areas using pixel intensity and elevation. The corners of the rooftop blobs are estimated from the segmented image, and rooftop refinement tools are applied to assess the precise locations of the vertices of the rooftop.
Conclusions
Populating feature databases from imagery is a labor-intensive, expensive process.
By incorporating better user interfaces, process improvements, knowledge
bases, and innovative image-understanding tools, industry and academia will
continue to improve the feature database extraction process and speed the
development of feature databases. Manual tools and refinements of the results
of automation will continue to be essential to capture operator knowledge.
Semi-automated feature extraction and automated image understanding tools
(with post-editing and refinement) have already dramatically reduced feature
extraction timelines, and make it possible for us to build the detailed,
accurate feature databases that are essential to cartography, modeling, simulation,
virtual world building, mission planning, and mission rehearsal.
Thus, the true promise of Softcopy Photogrammetry is the reduction of the photogrammetrists time and fatigue during production. This provides more time for the operator to oversee the entire production process. Automated Feature Extraction dramatically reduces production times and, therefore, imagery- derived product costs. SAFE and Automated Feature Extraction (AFE) tools and algorithms are the technologies that promise to make soft- copy-derived products common and affordable industry items.
Acknowledgments
We would like to acknowledge some of the engineers who led the development
of tools featured in this article:
Karen Kaufman (Rooftop, Edge and Road Refinement), Urho Rauhala, PhD (Array
Algebra, and Global Least Squares Matching), Al Bendett (GLSM Extraction Tools),
and Bingcai Zhang, PhD (Inference Engines). Scott Miller initiated and led
much of the development of SOCET SET® tools, and lead much of our user
interface development. Jim Pearson, PhD provided technical leadership in our
research efforts in image understanding tools. Dale Tubig, Bill
Chamberlain,
Jim Olson, and Karen Kaufman are thanked for their work in developing the cover
illustration.
About the Authors
The authors are all employed by GDE Systems, Inc., San Diego, CA.
Dr. Lawrence Firestone is the Manager for Advanced Development in the Advanced Systems Directorate in the Imagery and Information Systems Focused Business Unit.
Suzanne Rupert, MA, is an Advanced Development Systems Engineer leading the engineering effort of the Advanced Feature Extraction R&D development in the Advanced Systems Directorate in the Imagery and Information Systems Focused Business Unit.
James Olson, BS, is a Senior Engineering Specialist in computer vision algorithms leading the R&D Engineering development of the Model- Based Extraction effort within the Advanced systems Directorate in the imagery and Information systems Focused Business Unit.
Walter Mueller, MS. is an Engineering Staff Specialist and Program Manager of the Model-Supported Positioning Program and the Principal Investigator of the Geopositioning Systems Concepts R&D Development within the Advanced Systems Directorate in the imagery and Information Systems Focused Business Unit.
| Top | Home |