• Ingen resultater fundet

Template Matching

In document -OA 6H=?EC (Sider 85-90)



y(x) Higher threshold Lower Threshold Accepted by Lower Accepted by higher

Figure 13.1: The 1D function y(x) is seen to have multiple local maxima. Searching for the object which contain the global maximum, it is seen that neither the high nor low threshold (red or green) seems to be suitable. However, by combining these in a way such that only survivors of both thresholds are accepted as object, the resulting object will be appropriate. The high threshold can be interpreted as a lter regarding the low threshold.

handle the high-intensity corneal reections seen as white blobs. This phe-nomenon is explained intuitively by approximating the eye with a convex mirror, which reects the illumination in one direction. As a consequence, the estimate may be biased dependent on the light conditions. Using knowl-edge about the iris shape, the estimate can be further improved by weighting the center of gravity estimate or by incorporation of white blobs inside the iris.

13.2 Template Matching

Template matching is a technique for comparing data, in this an case image, with a stored reference template and subsequently assigning a score based on the level of similarity. In its simplest form it is equivalent with cross correlation, which is dened in the spatial domain as,

C(s, t) =X




I(x, y)T(x−s, y−t), (13.1)


Figure 13.2: The pupil is approximately black and assumed to be darker than the background.(Top left) Input image. (Top right) The high threshold (green) captures the object but unfortunately some of the background too, while the low threshold captures a small part of the object (blue). (bottom) Survivors of both thresholds are accepted as object. The center of pupil is estimated by calculating the center of mass of the object.

13.2. TEMPLATE MATCHING 87 where IM×N is an image, T is a template, (x, y) the pixels corresponding to the template, s = 0,1, . . . , M 1 and t = 0,1, . . . , N 1. It is usually assumed that the object of interest do not change appearance very much.

The template may be an intensity/binary image or a parameterization.

The method is very popular due to the relative simple implementation and ne results in applications such as pattern recognition, tracking etc.

However, the sensitivity to typical problems as noise, partial occlusions and varying illumination may be a huge drawback. Furthermore, the computation time may be slow dependent on the size of the template. There are several fast optimized algorithms that can be used to speed up the matching process [70][99].

13.2.1 Iris Tracking

The iris detector proposed by T. Ishikawa et al. [43] consists of two parts.

Initially, two dierent templates are applied to approximately locate the iris.

The rst template is a black disk template which is matched against the intensity image. The second is a ring template which is matched against the vertical edge image. The radius of both templates can be determined manually or by more sophisticated methods such as from the t of an AAM.

The template matching condence is then determined by summing the two sets of matching scores. The position with maximum condence is chosen as the initial estimate of the center of the iris.

This estimate is then rened using an ellipse tting algorithm[86] to detect the pupil contour. Initially, the edges are detected by scanning radially from the center and outward as seen in gure 13.3. The maximum gradient on each line is dened as an edge. The estimate is improved by tting an ellipse to the detected edges. The general form of an ellipse is dened as,

a1x2+a2xy+a3y2 +a4x+a5y = 1, (13.2) where the parametersa1, . . . , a5 are t using least squares. The center, shape and orientation of the ellipse are obtained by converting the general equation to standard form[69]. The standard form, with major axis parallel to the x-axis, is formulated as the coordinates(x, y)satisfying the following equation,


λ21 + (y−cy)2

λ22 = 1, (13.3)

where(cx, cy)is the center,λ1 andλ2are the length of major and minor axes.

The angle between major and vertical axis θ is applied by the rotation, µ x



µ cos(θ) sin(θ)

sin(θ) cos(θ)

¶ µ x y

. (13.4)


Figure 13.3: The initial estimate of the center of the iris is rened by tting an ellipse to the radial edges of the pupil, which is found by scanning radially from the center and outward towards thekpoints on a circle. The position with maximum gradient is chosen as edge. The yellow line shows one of the k lines, while the green line is the relative intensity level and the red line the relative gradient on this line.

The renement procedure is repeated until convergence, which should in general be no more than 2-3 iterations[43]. The template matching condence for a given image and the improved estimate of the center of iris is depicted in gure 13.4.

13.2.2 Outlier Detection

Improving the iris location by radial edge detection is unfortunately not trivial. This is caused by the relative weak edges in the image and high-intensity corneal reections.

Ishikawa et al. [43] propose to increase the robustness by ltering out edges, which are long away from the initial estimate. Nevertheless, this seems to be a poor solution.

If the estimate of the center of iris is acceptable, the Euclidian distance should be approximately equal. Therefore, we propose to constrain on the common distances. The algorithm is shown below, where c2×1xy is the


Figure 13.4: Note that warm colors should be interpreted as high values. (Top left) Black disk template matched against the intensity image. (Top right) Ring (annulus) template matched against the vertical edge image. (Bottom left) The template matching condence is determined by summing the two sets of matching scores (top left) and (top right). (Bottom right) The position with best condence is chosen as the initial estimate of the center of the iris, which is rened using an ellipse tting algorithm. Note that the algorithm is applied on graytone intensity images.

90 CHAPTER 13. SEGMENTATION-BASED TRACKING mated center of iris, X2×k the estimated edge points on the linesL spanned by c2×1xy and the points P2×k on the circle with a given radius. k represents the dimension and is typed as upper case, while lower case indexes represents one specic line.

Initially, the domain of lines are ranging from the center to the points lying on a circle (13.5). The Euclidian distance between center and the estimated edgesX2×k are calculated (13.6). The dierence gk−1 between the distances are obtained by dierentiating (13.7). If the dierence is greater (13.8) or less (13.9) than some tolerance, the domain of L is adjusted and the edge estimate is recalculated. The algorithms runs until convergence or a given stopping criteria is reached. The outlier detection step is depicted in gure 13.5.


c2×1xy ;P2×k¤

; (13.5)

while (not Converged)

dk = dist(cxy,X2×k); (13.6)

gk−1 = diff(dk); (13.7)

for i= 1 : k−1

if (gi > tol) (Too far away...) (13.8) Li [cxy;Xi] ;

Xi = edge(Li);

elseif (gi < tol) (Too near centroid...) (13.9) Li [Xi;Pi] ;

Xi = edge(Li);


if Xi = (If no edge, discard point)

Xi = [ ] ; end

end end

In document -OA 6H=?EC (Sider 85-90)