ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
ILL-CONFIGURED OBJECT REPRESENTATION BY NEIGHBOUR SET 
WITH APPLICATIONS TO AERIAL IMAGE ANALYSES 
T. Watanabe * *, K. Sugawara? 
* Graduate School of Information Systems, University of Electro-Communications, 
1-5-1 Chofu-ga-oka, Chofu-shi, Tokyo, 182-8585 Japan — (watanabe, sugawara)@sd.is.uec.ac.jp 
KEY WORDS: Object, Configuration, Model, Theory, Algorithm, Recognition, Registration, Image 
ABSTRACT: 
We introduce herein the concept of the ill-configured object (ICO). An ICO is a geometrical object having a stable (unique) name but 
varying configurations (shape, size, components, and component layout). In addition, we introduce the concept of the neighbour set 
representation (NSR) of an object, and show that the NSR is well-fitted to the ICO. Moreover, we show that any object, either non- 
ICO or ICO, can be characterized as a solution of a set theoretic equation defined on its NSR. An algorithm is thus designed to detect 
ICOs in images. Two applications of the proposed theory are then presented. The first is ICO recognition in aerial images, and the 
second is automatic matching of highly deviated landmark-less images. The latter provides a foundation for automatic land cover 
change analysis using satellite/aerial images obtained under different conditions (time, height, and direction). 
1. INTRODUCTION 
Although number of objects of concern to us may have specific 
names, their configurations may vary. The shape, the 
components, and component layout may change depending on 
the case. For example, an aerial image of school is usually 
composed of a number of components, such as a school building, 
a playground, and a pool. However, the overall size, shape, 
components, and their layout vary, as shown in Figure 1. In this 
paper, this type of object is referred to as an ill-configured 
object (ICO). In contrast, an object that has a very stable 
configuration, such as a human face, is an example of a non- 
ICO. The problem of ICO recognition in segmented images is 
examined herein. We will skip discussions on aerial image 
segmentation and refer the reader to our recent paper (Watanabe, 
2002). The solution of this problem will contribute to various 
image analysis tasks that require object recognition, especially 
tasks that require inexact matching (Shapiro, 1981). 
In order to solve this problem, we should prepare an appropriate 
computational representation of ICO. A typical representation is 
a graph model (equivalently, a relational model) in which nodes 
represent component regions and arcs represent region 
adjacency relations (Shapiro, 1981; Vosselman, 1992; Kim, 
1991). Object recognition then becomes the problem of finding 
a sub-graph (of the larger graph representing the whole image) 
that exactly matches the model graph. In order to cope with 
ICOs in this setting, we must prepare various graph models 
corresponding to the topological variants of the ICOs. Using the 
inexact matching method, which finds a sub-graph that is similar 
to a given model, we can reduce the model set size at the 
expense of high computation cost (Shapiro, 1981; Shapiro, 
1982; Shapiro, 1985; Vosselman, 1992). 
A powerful algorithm for inexact matching of trees has recently 
been developed, however, this algorithm is as of yet 
inapplicable for general graphs (Oommen, 2001). In addition, 
non-graphical representations of objects, such as MRF (Markov 
random field) (Geman, 1984), attribute grammar (Young, 1986), 
logical rules (Ohta, 1985), and 2D string (Chang, 1987), also 
exist. However, in order to deal with ICOs, these representations 
  
* Corresponding author. 
also have high cost, with respect to either model preparation 
and/or in computation. Therefore, a new representation and a 
new matching method are required in order to solve the ICO 
recognition problem. Recently, a new method ACC (adaptive 
combination of classifiers) is proposed to deal with a kind of 
ICO having a non-fixed but stable component layout (Mohan, 
2001). It's typical target is the articulated human body 
composed of components including, head, right/left arums, 
body, and foots. ACC is composed of several low level 
component classifiers and a high level combination classifier. 
Using the fact that both the place and the extent of each 
component is stable, each component classifier monitors the 
existence of a relevant component in a relevant window and 
the combination classifier decides the existence of a human 
body using the outputs of these component classifiers. In both 
layers, classifiers are realized using SVM (support vector 
machine) (Vapnik, 1998). Although superior performance 
than the traditional non component-based complete person 
detector is reported, very high SVM training cost of nearly 
O(10?) positive and O(10*) negative examples are required 
p g p q 
for each classifier. So, ACC looses its power for ICOs that 
have unstable components configuration and/or permits only 
small training examples as seen in aerial image. 
So, to solve the ICO recognition problem, we are required to 
go back to the basics and investigate the possibility of a new 
representation scheme for ICO. We introduce herein the 
concept of neighbor set representation (NSR) of objects as a 
possible solution and investigate its properties. We show that 
the number of models required for ICO representation is far 
fewer than for the graph models. We show that NSR is a 
unified representation for both non-ICOs and ICOs by proving 
that both objects can be characterized as a solution, i.e., a fixed 
point, of a set theoretic formula defined on the NSR of the 
object. Fortunately, this formula permits an iterative solution 
on which we can build an ICO search algorithm. 
We present two applications of aerial image analysis in order 
to demonstrate the usefulness of the proposed concepts: ICO 
recognition in artificial and real images (Suto, 2000), and 
A - 387