MODEL-BASED OPTIMIZATION: 
ACCURATE AND CONSISTENT SITE MODELING 
P. Fua 
Artificial Intelligence Center 
SRI International 
333 Ravenswood Avenue 
Menlo Park, CA 94025 
fua@ai.sri.com 
Commision Ill, Working Group 2 
KEY WORDS: Vision Sciences, Cartography, Modeling, Aerial, Three-dimensional 
ABSTRACT 
Model-Based Optimization (MBO) is a paradigm in which an objective function is used to express both geometric and 
photometric constraints on features of interest. A parametric model of a feature, such as a road, a building, a river or the 
underlying terrain, is extracted from one or more images by adjusting the model's state variables until a minimum value of the 
objective function is obtained. The optimization procedure yields a description that simultaneously satisfies (or nearly satisfies) 
all constraints, and, as a result, is likely to be a good model of the feature. 
Furthermore, because objects are all modeled in the same fashion, we can refine the models simultaneously and enforce 
geometric and semantic constraints between objects, thus increasing not only the accuracy but also the consistency of the 
reconstruction. 
We believe that these capabilities will prove indispensable to automating the generation of complex object databases from 
imagery, such as the ones required for realistic simulations or intelligence analysis. 
1 INTRODUCTION 
Model-Based Optimization (MBO) is a paradigm in which 
an objective function is used to express both geometric and 
photometric constraints on features of interest. A parametric 
model of a feature (such as a road, a building, or coast- 
line) is extracted from one or more images by adjusting the 
model's state variables until a minimum value of the objec- 
tive function is obtained. The optimization procedure yields 
a description that simultaneously satisfies (or nearly satisfies) 
all constraints, and, as a result, is likely to be a good model 
of the feature. 
The deformable models we use here are extensions of tra- 
ditional snakes [Terzopoulos, et al., 1987, Kass et al., 1988, 
Fua and Leclerc, 1990]. They are polygonal curves or face- 
tized surfaces to which is associated an objective function 
that combines an “image term” that measures the fit to the 
image data and a regularization term that enforces geometric 
constraints. 
Because features and surfaces are all modeled in a uniform 
fashion, we can refine several models simultaneously and en- 
force geometric and semantic constraints between objects, 
thus increasing not only the accuracy but also the consis- 
tency of the reconstruction. The ability to apply such con- 
straints is essential for the accurate modeling of complex sites 
in which objects obey known geometric and semantic con- 
straints. In particular, when dealing with multiple objects, 
it is crucial that the models be both accurate and consis- 
tent with each other. For example, individual components 
of a building can be modeled independently, but to ensure 
realism, one must guarantee that they touch each other in 
an architecturally feasible way. Similarly, when modeling a 
cartographic site from aerial imagery, one must ensure that 
the roads lie on the terrain—and not above or below it—and 
that rivers flow downhill. To that end, we have developed 
a constrained-optimization scheme that allows us to impose 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
hard constraints on our snakes at a very low computational 
cost while preserving their convergence properties. 
We first introduce our generalized snakes. We then present 
our constrained-optimization scheme. Finally, we demon- 
strate its ability to enforce geometric constraints upon individ- 
ual snakes and consistency constraints upon multiple snakes 
to produce complex and consistent site models. 
2 GENERALIZED SNAKES 
We model linear features as polygonal curves that may be 
described either as a sequential list of vertices, or, for more 
complex objects such as a road network or a 3-D extruded 
object, described by the network topology. In the latter case, 
to describe the object completely, one must supply not only 
the list of vertices but also a list of “edges” that defines the 
connectivity of those vertices. In addition, with some of these 
complex objects, one can also define "faces," that is, circular 
lists of vertices that must be constrained to remain planar. 
Similarly, we model the terrain on which these features rest 
as triangulated surface meshes whose shape is defined by the 
position of vertices and can be refined by minimizing an ob- 
jective function. 
Our ultimate goal is to accommodate the full taxonomy of 
those "generalized snakes" described by Table 1. The al- 
gorithms described here are implemented within the Radius 
Common Development Environment (RCDE) [Mundy et al., 
1992]. 
2.1 Polygonal Snakes 
A simple polygonal snake, C, can be modeled as a sequential 
list of vertices, that is, in two dimensions, a list of 2-D vertices 
$2 of the form 
Soi d(m, gi); dm M Uns (1) 
      
    
  
  
  
  
  
  
  
     
    
  
  
  
  
  
   
    
     
    
    
    
     
   
    
    
      
     
     
    
   
   
   
    
    
    
   
    
   
      
   
    
Ta 
and, in tt 
In this pa 
dinates o 
model's « 
In the 2- 
term we 
is taken 
where / 
of C, f(: 
points (: 
practice, 
IVZ(f(s 
segment: 
In the 3- 
compute 
computil 
these en 
2.2 Sn 
These si 
such as | 
2-D cut 
vertices 
the imag 
Ep(C 
tu: 
and defi 
The firs 
the secc 
curvatur 
tant. li 
spaced \ 
ularity. 
or conju 
large nu 
effective 
the equ: