Figure 1. Four example images showing the variations caused 
by the printing with two different stamps. The marked windows 
with the white border are enlarged to make the variations clear. 
In this paper, a novel approach is introduced that automatically 
decomposes the object into its rigid parts using several example 
images in which the mutual movements (variations) of the 
object parts are shown. Additionally, the variations of the object 
parts are analyzed and used to build a hierarchical model that 
contains all rigid model parts and a hierarchical search strategy, 
where the parts are searched relatively to each other taking the 
relations between the parts into account. 
This model generation is called offline phase and has to be exe- 
cuted only once and therefore is not time-critical. But in the 
time critical online phase the hierarchical model facilitates a 
very efficient search. 
2. OUTLINE OF THE APPROACH 
In this section a coarse description of the algorithm to create a 
hierarchical model from the input data is presented. The whole 
process is summarized in the flowchart of Figure 2. In section 
3, the single steps are explained in detail. 
The only input data of the algorithm are a sample image of the 
object (model image), in which the object is defined by a region 
of interest (ROI), and some additional example images that, at 
least qualitatively, describe the mutual movements of the single 
object parts. Figure 3 shows an artificial example that is used to 
illustrate the algorithm. 
The first step is to decompose the object, which is defined by 
the ROI within the model image, into small initial components. 
Note that these components need not coincide with the real 
object parts. For instance, if we use the connected components 
of the image edges as criterion for decomposition we would get 
the following components in our example: 1 hat, 1 face, 2 arms, 
2 hands, 2 legs, 2 feet, the outer rectangle of the upper body, the 
inner rectangle of the upper body and at least 1 for each letter 
printed on the upper body. For each initial component a rigid 
model is built using a recognition method that is based on the 
image edges (cf. section 1) and able to find the object under 
rigid transformation (translation and rotation). Since we want to 
fulfill industrial demands we prefer to either use the similarity 
measure described in (Steger, 2001) or the modified Hough 
transform (Ulrich et al., 2001). 
  
  
  
Model Example 
/ Image p ROI Ib Images y 
| Initial Decomposition | 
Y 
Initial Model 
Generation 
| ® 
| Search Initial Models | 
Y 
Analyze Pose Parameters 
z» Clustered Components 
Y 
Final Model 
Generation 
7 ero 
/ 
m 
A. 
| Search Final Models | 
Y 
. | Analyze Pose Parameters 
=> Relations 
Y 
— | Find Optimum Search 
=> Search Tree 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
      
  
  
Hierarchical 
Model 
  
  
  
  
  
  
  
  
Figure 2. Flowchart of the algorithm that is used to create a 
hierarchical model from the input data (Model Image, Region of 
Interest (ROI), and Example Images). 
Each initial model is searched for in all example images. Thus, 
we get the rigid transformation or pose parameters (position and 
orientation) of each initial component in each image. These 
parameters are analyzed and those initial components that form 
a rigid object part are merged together leading to the final 
decomposition. In our example, the hat and the face are 
clustered into one rigid part since they show the same 
movement in each image. The same holds for all initial 
components that form the upper part of the body. They are also 
clustered into one rigid part. Rigid models are built for each of 
the newly generated (clustered) parts and searched in the 
example images. Together with the models of the components 
that have not been clustered they describe the final models. The 
relations (relative movements) between each pair of the rigid 
object parts are computed by analyzing the pose parameters and 
  
Figure 3. Input data: The upper left image represents the model 
image, in which the object is defined by the ROI (white 
rectangle). Additionally, five example images that show the 
mutual movements of the object parts are provided. 
—100— 
store 
repre 
desc 
com] 
ascel 
searc 
Final 
the 1 
optir 
corre 
in the 
Figur 
gener: 
refere 
The s 
the le 
relativ 
The re 
are v 
range 
The h 
object 
image 
image 
part m 
the rei 
space, 
search 
In this 
introdu 
3.1 Ir 
In the 
model 
can be 
The co 
rigid ol