International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
Figure 3. The stereo pair of package scaled model 
The second approach is based on an assumption that all cuts 
(circles) lie approximately in one plane. Then image 
orthotransformation to this reference plane gives metric scaled 
map of the front side of package with known scale factor. So it 
is possible to perform plane measurements to have adequate 
results. 
  
Figure 4. The orthophoto of the package scaled model 
Fig.4. presents the orthophoto of the package produced basing 
on the reference plane and left image. In the orthophoto the cuts 
look like circles. 
The algorithm for automated circles recognition in the images 
was developed. It was used for cut detection and subsequent 
measurements. Below the description of image analysis 
algorithm is presented. 
3.2 Image analysis algorithm 
The image analysis algorithm based on the original circle 
detection technique (Knyaz V., 2000). The complete procedure 
of image analysis for one frame includes the following steps: 
|. Forming of intensity gradient field 
2. Testing hypotheses from discrete space of circle 
parameters (2x2D-accumulator) 
3. 2x2D-accumulator analysis: determination of circles" 
locations 
4. Constructing a minimal convex covering for a set of 
extracted circles 
5. Reconstruction of non-detected circles 
6. Computation of required area parameters 
These steps are briefly described bellow. 
3.2.1 Forming an intensity gradient field: The intensity 
gradient field is implemented as two 2D arrays: array of 
gradients in x-direction and array of gradients in y-direction. It 
1s formed as follows: 
e Evaluation of gradients by Sobel operator; 
e Elimination of weak gradients; 
e Thinning of gradient field. 
The Sobel operator is a well-known image processing 
procedure. It allows the determination of both magnitude and 
orientation of image intensity gradients at the each pixel of 
image. Elimination of weak gradients means that the elements 
of gradient field with gradient magnitude less than some 
threshold to be set to zero. 
    
Thinning of gradient field is a procedure that eliminates all 
points of gradient field those are not the local maxima in their 
directions. This procedure makes the contours of objects as 
sharp as possible. Practically, at this stage, the gradient field 
may be considered as a contour image supported with gradient 
values at each contour point. 
3.2. Testing hypotheses from discrete space of circle 
parameters (2x2D-accumulator): At this step, the each point 
of area of interest is tested as a possible center of circle. This 
testing presumes the following operations: 
e Collecting a number of appropriate contour points for each 
value of possible circle radius in some given range; 
e Normalizing this numbers as percents of circle length for 
corresponding radii; 
e Finding the best radius that corresponds to the maximum 
percentage value. 
The “appropriate contour point” means here that the angle 
between the radius vector from this point to center point and the 
gradient vector in this point is small enough. Normalizing of 
numbers is performed, because the possible number of points on 
discrete circle depends on its length. 
The best hypothesis for tested point is stored in a special 2x2D- 
accumulator. The accumulator of hypotheses is implemented as 
two 2D-arrays those geometry corresponds to the geometry of 
source image. One accumulator array R(x,y) contains the radius 
of probable circle for this center point (x,y) and the other array 
N(x,y) contains the corresponding number of points on the 
circle contour. 
  
  
  
  
  
Figure. 5. Example of function of a number of appropriate 
contour points for each value of possible circle radius 
3.2.5  2x2D-accumulator analysis: determination of 
circles’ locations: The procedure of 2x2D-accumulator analysis 
performs the iterative search of local maxima according to the 
following algorithm: 
Step 1. Find the global maximum of N(x.y) array 
Step 2. Put the circle with (x,y) center and R(x,y) radius into the 
list of circles. 
Step 3. If (N(x, y R(x,y)«Percentage, Ratio) 
then 
stop the search. 
else 
clear the accumulator in the round neighborhood of 
(x,y) with R(x,y) radius and go to step |. 
   
International 
This procedur 
circles until al 
be put in a list. 
  
Figure.6. Th 
3.2.4 Const 
extracted circ 
geometry. The 
connected wit. 
points. Due to 
arcs of circle: 
However, we 
allows repres: 
polygon witho 
in three steps: 
e Find the m 
e Find the m 
e Expand th 
vector from m: 
Our experimer 
approximation 
  
Figure. 7. Mi 
minim