ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
words, O.nset is a set of MBRs, each element of which 
represents the possible extension of O around each child 
element in O.subs. See Figure 2. More specifically, 
* 
O.nset = {MBR (c, O.area) | c € O.subs}, 
where MBR' (c, O.area) is a union of all the possible 
extensions of O.area around c. 
For NSR to be an effective representation scheme of ICO, the 
following properties must be satisfied. 
(1) The size of NSR(O) for ICO representation is not so large. 
(2) Computationally efficient ICO search is possible. 
In the following, Theorem 1 assures (1). Theorem 2 and 3 give 
fundamental properties of NSR upon which we can assure (2). 
Proofs are omitted due to page limitation. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
Figure 3. O.area is always identical to the core of O.nset 
(a) Non-ICO ( O.nset is Fig.2: b, c, d); (b) and (c) ICOs having partially 
fixed components ( O.nset is Fig.2: e, f, g); (d), (e), (f) and (g) ICOs 
having no fixed components ( O.nset is Fig.2: h, i, j). 
Theorem 1: The size of O.nset which must be specified in 
order to represent an ICO is O(|O.subs|) where |O.subs| 
denotes the size of O.subs. 
Discussion 1: See Figure 2. It should be noted that, if we resort 
to a relational model (see Figure 1) to represent all the possible 
layouts of ICO, we are forced to prepare O(|O.subs |!) models in 
O.layout. In order to verify this, select an object O 
having O.area.size = (nw,mh) and |O.subs| = nm (each 
element of O.subs has different attribute but are identically 
h, and wzh ). Further 
suppose that r of mn elements are located at fixed positions 
and that the remaining mn —r elements can be placed at any of 
the mn-r positions. Then, the number of possible 
configurations becomes O((| O.subs | r) ), or O(|O.subs |!). 
shaped, ie. width = w, height = 
Theorem 2: Any object O satisfies the following set theoretic 
equation: 
O.area = (\O.nset (= M\eeO.subs MBR° (c, O.area)). 
We refer to the right-hand side of this equation as the core of 
O.nset. 
Discussion 2: Theorem 2 states that O.area is identical to the 
core of O for both non-ICOs and ICOs. See Figure 3 for 
examples. 
Theorem 3: Let MBR (c,O.area) be an expansion of 
MBR' (c, O.area) satisfying 
MBR (c, O.area) c MBR'" (c, O.area), then we obtain 
O.area ©, coups MBR™ (c, O.area)). 
Discussions 3: Theorem 3 states that we can enclose the 
O.area in the core of the enlarged O.nset. See Figure 4 for 
some examples. 
2.3 ICO Recognition using NSR 
In this section we discuss the method of recognizing ICO using 
the above definitions and Theorems. Since real-world ICOs 
have a number of variations, we discuss methods for dealing 
with these variations. 
The Problem: Let / and SEG(/) denote an image and its 
segmented version, respectively. We assume each segment in 
SEG(I) is approximately represented by an MBR. Thus, 
SEG) is a set of 
{(s.attriv, s.area) | se SG}, where SG denotes the set of 
records of the form 
segments in /. s.attriv is the attribute (e.g., water, ground, 
house, etc.) of the segment s, and s.area = (x, y, w, h), where 
(x, y) and (w, ^) denote the base point (e.g., northwest corner) 
and the size (e.g., width and height) of the MBR of s in 7, 
respectively. 
The goal is to find task objects 7O in I. 
The model set (MS) for 7O is assumed to be provided using 
the NSR scheme. Thus, 
MS = {(O.attrib, O.area, O.subs, O.nset) | Oe TO). 
Notice that in MS, the base point parameters (x, y) in O.area 
are undefined, because they can not be determined until the 
model is instantiated (matched to an object) in SEG(/). 
A - 389