ISPRS Commission III, Vol.34, Part 3A Photogrammetric Computer Vision“, Graz, 2002 
  
Error in X Position 
  
0.17 — Shape Based Matching 
= = Least-Squares Adjustment 
— PatMax 
   
   
  
0.05 
Error in X [Pixel] 
© 
-0.05 |- 
-0.17 
  
  
-5 -4 -3 -2 -1 0 
Horizontal Translation [Pixel] 
Error in X Position 
oil = Modified Hough Transform | 
: = = Normalized Cross Correlation | ^ 
  
  
Error in X [Pixel] 
o 
e 
© a 
S 
e 
e 
T 
  
  
  
5 4 3 2 4 0 
Horizontal Translation [Pixel] 
Figure 7: Position accuracy as the difference between the actual 
z coordinate of the IC and the x coordinate returned by the recog- 
nition approach while shifting the chip successively by 1/7 pixel 
to the left. 
Figure 8 shows the corresponding errors in orientation. Here, the 
least-squares adjustment and PatMax® are superior to all other 
candidates reaching maximum errors of 1/50? and 1/100? in this 
example. In comparison, when looking at the result of the shape 
based matching, the improvement of the least-squares adjustment 
is evident: the maximum error is reduced to 1/50? compared to 
the result of the shape-based matching without least-squares ad- 
justment, which was about 1/16?. The error magnitude of the 
other three approaches is higher 1/6° (10°) in this example. 
3.3.3 Computation Time The last criterion that was applied 
is the computation time of the recognition approaches. In Table 1 
the mean recognition times of all approaches using the sequence 
with the shifted IC as well as using the sequence with the rotated 
IC are listed. Additionally, the time increase A from the restricted 
to the unrestricted angle interval is printed in percent. 
First the angle interval was restricted to [-30°;+30°]. In this re- 
spect the shape-based matching approach, the least-squares ad- 
justment, the modified Hough transform and PatMax® are sub- 
stantially faster than existing traditional approaches using the nor- 
malized cross correlation. The results when using an unrestricted 
angle interval are shown in an extra column of table 1. Here, the 
modified Hough transform is slightly faster than the shape-based 
matching approach, which indicates an advantage of the modified 
Hough transform over the shape-based matching if the transfor- 
mation space increases. This assumption is also supported when 
looking at the percental time increase of the modified Hough 
transform: The computation time merely increases by 56%, which 
is the smallest value in this test. Also PatMax® shows only a 
small increase, whereas the computation time of the normalized 
cross correlation increases more dramatically. In this example 
the computation times of our new approaches are only 0.2 to 0.5 
times as high as those of the traditional methods but about 1.0 to 
1.5 times as high as that of PatMax®. 
For the most methods, a similar behavior is obtained when search- 
ing for the rotated IC. What we recognized during evaluation is 
Error in Orientation 
  
Error in Orientation [Deg] 
  
=—= Shape Based Matching 
  
= = Least-Squares Adjustment 
-0.06 | —— PatMax 1 
0 1 2 3 4 5 
Rotation [Deg] 
Error in Orientation 
T 
025r === Modified Hough Transform 
= = Normalized Cross Correlation 
0.2} 
  
Error in Orientation [Deg] 
  
  
  
  
3 
Rotation [Deg] 
Figure 8: Orientation accuracy as the difference between the ac- 
tual object orientation of the IC and the returned angle by the 
recognition approach while rotating the chip successively by ap- 
prox. 1/9° counterclockwise. 
Shifted IC Rotated IC 
RI UR | A R UR | À 
[ms] | [ms] | [%] || [ms] | [ms] | [76] 
SBM 57 126 | 121 50 100 | 100 
LSA 65 133 | 105 60 110 83 
MHT 72 112 56 62 80 29 
PM 55 88 60 80 193 | 141 
NCC 132 | 281 | 113 294 | 373 27 
Table 1: Mean computation times of the shape-based matching 
(SBM), the least-squares adjustment (LSA), the modified Hough 
transform (MHT), PatMax® (PM), and the normalized cross cor- 
relation (NCC) on a 400 MHz Pentium II. Additionally, the time 
increase A from the restricted (R) to the unrestricted (UR) angle 
interval is printed in percent. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
that the more the IC is rotated relatively to the reference orienta- 
tion the longer the computation time of the normalized cross cor- 
relation. Obviously, the implementation of (Matrox, 2001) does 
not scan the whole orientation range at the highest pyramid level 
before the matches are traced through the pyramid but starts with 
a narrow angle range close to the reference orientation. Thus, 
the computation time of the normalized cross correlation is not 
directly comparable to the other approaches, because the orien- 
tation range of [-30°;+30°] or [0°;+360°] is not really scanned, 
i.e., a comparable computation time would be still higher. Also 
the corresponding A-values would be higher. 
Also in the case of the rotated IC, the modified Hough transform 
seems to be the method that is most suitable when dealing with 
large parameter spaces because of its small time increase — in 
this case — of only 29%. To get the effective computation time 
of the least-squares adjustment we have to subtract the computa- 
tion time of the shape-based matching. The difference is in the 
range of 7 to 10 milliseconds and does not depend on the size of 
the parameter space. Therefore, the larger the parameter space 
the less the influence of this constant part, which is the reason for 
the smaller A-values in Table 1 of the least-squares adjustment in 
A - 373