# Mahalanobis Distance-Based Algorithm for Ellipse Growing in Iris Preprocessing

Krzysztof Misztal, Jacek Tabor

► To cite this version:

Krzysztof Misztal, Jacek Tabor. Mahalanobis Distance-Based Algorithm for Ellipse Growing in Iris Preprocessing. 12th International Conference on Information Systems and Industrial Management (CISIM), Sep 2013, Krakow, Poland. pp.158-167, 10.1007/978-3-642-40925-7_16 . hal-01496062

HAL Id: hal-01496062

https://inria.hal.science/hal-01496062

Submitted on 27 Mar 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Mahalanobis distance-based algorithm for ellipse growing in iris preprocessing

Krzysztof Misztal¹ and Jacek Tabor²

¹ AGH University of Science and Technology
Faculty of Physics and Applied Computer Science
al. A. Mickiewicza 30, 30-059 Kraków, Poland

Krzysztof.Misztal@fis.agh.edu.pl

² Jagiellonian University
Faculty of Mathematics and Computer Science
Lojasiewicza 6, 30-348 Kraków, Poland

tabor@ii.uj.edu.pl

**Abstract.** We introduce a new algorithm for ellipse recognition. The approach uses Mahalanobis distance and statistical and analytical properties of circular and elliptical objects. At first stage of the algorithm the starting configuration of initial ellipse is defined. Next we apply a condition which describes how much the shape is ellipse-like on the boundary points.

The algorithm can be easily applied to detection of elliptical objects also on grayscale images. Moreover, we discuss the improvement in iris image preprocessing.

**Keywords:** Mahalanobis distance, ellipse growing, ellipse detection, pattern recognition, feature extraction

## 1 Introduction

Efficient ellipse and circle detection is one of the key tasks in image processing which is widely applied in various computer vision problems, in particular in the computation of the position of 3-D objects in robotic applications [1, 2], in the eye tracking in human-computer interfaces [3], in face detection in biometric identification [4], in character recognition [5]. Consequently the extraction of elliptic shapes from images has captured the interest of researchers for a long time [6]. The methods used for this task can be categorized into several groups. The most widely used is based on Hough transform [7] which takes edge map of an image as an input. Other group is based on the least square methods which mostly cast the ellipse fitting problem into a constrained matrix equation problem [8, 9]. Next category uses neural networks to find fast and approximately sufficient solutions [10]. The last group is focused on hybrid approach which makes it more flexible and efficient in many cases [11–15].

In this paper we introduce a new algorithm based on ellipse-growing idea which may help in iris preprocessing, and consequently in iris pattern recognition. A basic limitation of the current iris recognition methods [16] is that they
<figure><img src="image_2.png" /><figcaption>Fig. 1: Iris image reconstruction. Fig. 1a – original eye image with extracted iris and pupil. After the reconstruction (Fig. 1b) the shape of the iris was changed and it looks like a circle.</figcaption></figure>

require an “on-axis” image of the eye. Clearly in most “real-life” pictures we have only a side-view of the eye, see Fig. 1a, which consequently yields that the eye resembles an ellipse instead of a circle. There are same approaches to deal with this problems which are based on the change in the representation, see [17–19].

We use slightly different approach which allows to use original Daugman’s recognition process – namely we modify the picture by respective affine transformation so that the iris becomes circle-shaped. To do so we fit an optimal ellipse to the pupil of an eye, and apply to the picture the affine operation which transforms this ellipse into a circle, see Fig. 1b, which consequently transforms the iris almost into a circle.

To apply the above mentioned procedure we construct a new ellipse extraction method which is based on the Mahalanobis distance and uses the statistical and analytical properties of circular and elliptical objects. In the first step we use thresholding for finding the starting configuration of cluster - initial ellipse shape<fnref n="3" />. Next we use the specified condition to decide whether to add or not the points from the cluster boundary. Since during the calculation we examine just the boundary points of our cluster the calculation proceeds relatively fast. This condition verifies whether the current boundary element fits (with possible error δ) into the optimal ellipse fitted to the data with the use of Mahalanobis distance. More precisely, we add the boundary point x to the data-cluster C if

$$ \|x - \mu_C\|_{\Sigma_C} = \sqrt{(x - \mu_C)^T \Sigma_C^{-1} (x - \mu_C)} \le 2 + \delta, $$

where μ_C and Σ_C denote the mean and covariance of C. The procedure is repeated until no boundary point belonging to the set satisfies the condition. The main advantage of the proposed method is that no complicated mathematical computation is involved in the implementation. Moreover, it is suitable for ellipse growing and ellipse extraction even on grayscale digital images and can be used for higher dimensional data.

<footnote n="3">³ This step can be omitted or replaced by other procedure which ends with proper initial configuration of the cluster.</footnote>
The remainder of the paper is organized as follows: in the next section we present basics of the Mahalanobis distance. Moreover we provide a natural and intrinsic characterization of elliptical shapes, which is proper even in higher dimensions. In the third section we look more closely at the outcome information from the growing cluster. We use its characterization to correct the image. In section 4 we provide the results of experiments to illustrate the performance of our method. Finally, the last section contains some concluding remarks and possible directions of future investigations.

## 2 Theoretical background

In this section for the convenience of the reader we present a brief exposition of the Mahalanobis distance and indicate how these information can be used to construct ellipse growing algorithm.

It is well-known that the Euclidean distance between two points $x$ and $y$ in real space is given by

$$ \|x - y\| = \sqrt{(x - y)^T \mathbf{I} (x - y)}, \text{ for } x, y \in \mathbb{R}^N. $$

where $T$ denotes the transpose operation and $\mathbf{I}$ is an identity matrix.

It follows immediately that all points with the same distance from the origin $\|x - 0\| = c$ satisfy $x_1^2 + \dots + x_n^2 = c^2$, which means that all components of an observation $x$ contribute equally to the Euclidean distance of $x$ from the center. But this situation in same cases is not optimal as we often prefer a distance such that components with high variability should have different weight than components with low variability. This can be obtained by using the Mahalanobis distance [20] defined for a positive definite matrix $\Sigma$ by

$$ \|x - y\|_{\Sigma} = \sqrt{(x - y)^T \Sigma^{-1} (x - y)}. \quad (1) $$

In this case the set of all points with the same distance $c$ from a given point $x_0$

$$ \{x \in \mathbb{R}^N | (x - x_0)^T \Sigma (x - x_0) = c^2\}, \quad (2) $$

describes and ellipsoid with center at $x_0$. If $x_0 = 0$ then (2) is the general equation of ellipsoid centered at the origin.

One can easily see that instead of calculating the Mahalanobis distance $\|x - y\|_{\Sigma}$ we can equivalently transform the points by the matrix $\Sigma^{-1/2}$ and compute the Euclidean distance of transformed points:

$$ \|x - y\|_{\Sigma} = \|\Sigma^{-1/2} x - \Sigma^{-1/2} y\|, $$

see Fig. 2.

Let $C$ denote the given subset of $\mathbb{R}^N$. By $\mu_C$ we denote the mean value of $C$, and by $\Sigma_C$ we mean covariance matrix of $C$. If we want to fit the Mahalanobis distance to our data set $C$, as $\Sigma$ we take the covariance matrix $\Sigma_C$ of $C$.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Mahalanobis distance vs. Euclidean distance. Fig. (a) – Mahalanobis distance in the original space on the data C, Fig. (b) – Euclidean distance in space transformed by the operation $x \to \Sigma_C^{-1/2}(x - \mu_C)$.</figcaption></figure>

**Remark 1.** It is worth noting that Mahalanobis distance can be treated as a Euclidean distance in a transformed space, where the mean of the data C is transformed into zero:

$$C \ni x \to \Sigma_C^{-1/2}(x - \mu_C) \in \mathbb{R}^N.$$

Fig. 2 presents the modification of origin given by this operation.

We are going to present some important observations crucial in the construction of our algorithm with the use of Mahalanobis distance. Consider the data uniformly distributed over the circle $^4\mathbb{B}(0, R) := \{x \in \mathbb{R}^2: \|x\| \le R\}$ of radius $R \ge 0$.

**Remark 2.** Consider the circle $\mathbb{B}(x_0, R)$ with radius $R$ on the plane. Then the covariance matrix $\Sigma$ of the uniform probability distribution on $\mathbb{B}(x_0, R)$ is given by

$$\Sigma = \frac{R^2}{4} \mathbb{I}. \qquad (3)$$

Proof of this remark is quite simple and based on the change into polar coordinates (the N-dimensional version can be obtained by spherical representation of N-ball [21, Chap. 8, Thm. 4]).

Next theorem is essential for algorithm construction.

**Theorem 3.** Consider the uniform probability density on the ellipse $E \subset \mathbb{R}^2$ with covariance $\Sigma_E$. Then

$$E = \mathbb{B}_{\Sigma_E}(\mu_E, 2). \qquad (4)$$

<footnote n="4">⁴ We consider Euclidean norm in this paper.</footnote>
*Proof.* By applying the transformation described in Remark 1 we can reduce our reasoning to the case when $E = \mathbb{B}(0, R)$. Then by (3)

$$ 
\begin{aligned}
\mathbb{B}_{\Sigma_E}(0,2) &= \{x : \|x\|_{\Sigma_E} \le 2\} \\
&= \{x : \|x\|_{\Sigma_E}^2 \le 4\} = \{x : x^T(\frac{R^2}{4}\mathbb{I})^{-1}x \le 4\} \\
&= \{x : x^T x \le R^2\} = \mathbb{B}(0, R) = E.
\end{aligned}
$$

Fig. 3 presents the given data-sets $C$ (or more precisely the uniform density on the data) with fitted ellipses given by formula (4) in the presented objects.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Different data-sets with ellipse constructed by equation (4).</figcaption></figure>

Observe that on the true ellipse $E$, by Theorem 3 the set $E$ will coincide with $\mathbb{B}_{\Sigma_E}(\mu_E, 2)$. Thus two allow the increase, or more precisely, the grow, of the ellipse we allow error level $\delta > 0$. In other words we allow to add a point to our data-cluster $C$ if it satisfies the condition

$$ x \in \mathbb{B}_{\Sigma_C}(\mu_C, 2 + \delta). $$

With different values of $\delta$ we will control how close to an ellipse we want to remain. Consequently, the complete version of the authors' algorithm can be described as follows:

**initial conditions**

choose $\delta > 0$

choose initial configuration of initial ellipse $C$

compute mean value $\mu_C$ and covariance matrix $\Sigma_C$ of $C$

**repeat**

added ← False

**for each** $x$ in $\partial C$ **do**

**if** $x \in \mathbb{B}_{\Sigma_C}(\mu_C, 2 + \delta)$ **then**

$C := C \cup \{x\}$

compute mean value $\mu_C$ and covariance matrix $\Sigma_C$ of $C$

added ← True

**end if**

**end for**

**until** added
The algorithm finds the maximal “almost” ellipse (with given error $\delta$) fitting in the input image by growing set $C$ (Fig. 4).

<figure><img src="image_5.png" /><figcaption>(a) initial configuration (b) 9th iteration (c) 25th iteration (d) 54th iteration</figcaption></figure>

<caption>Fig. 4: Fitting ellipse – authors’ algorithm iterations.</caption>

As we know the role of $\delta$ is how close to an ellipse we want to stay. However, to start the algorithm we need an explicit construction of the initial configuration of $C$ – we usually select sufficiently large ellipse which fits into our data. To do so we apply the thresholding and some morphological operations (see Fig. 8).

Another important thing is the meaning of the boundary of the cluster $\partial C$ – we understand by this the nearest point which are not the members of the cluster $C$. In case of digital image we have natural discretization of our space, so we can easily determine the boundary using von Neumann neighborhoods (see Fig. 5).

<figure><img src="image_6.png" /><figcaption>Fig. 5: The boundary points of the black pixel used in our algorithm.</figcaption></figure>

Finally, we can optimize the calculation of the mean value and covariance matrix of cluster $C$. Following well-known remark shows the formula for on-line calculation of the mean and covariance of the modified data.

*Remark 4.* Let $U, V$ be subsets of $\mathbb{R}^2$, $U \cap V = \emptyset$. We put

$$w_{U \cup V} = w_U + w_V, \quad p_U = \frac{w_U}{w_{U \cup V}}, \quad p_V = \frac{w_V}{w_{U \cup V}}.$$

where $w_U$ and $w_V$ denote the weights (cardinalities) of the sets $U$ and $V$ respectively. Then mean value and covariance matrix of set $U \cup V$ are given by

$$\mu_{U \cup V} = p_U \mu_U + p_V \mu_V,$$
$$ \Sigma_{U \cup V} = p_U \Sigma_U + p_V \Sigma_V + p_U p_V (\mu_U - \mu_V)(\mu_U - \mu_V)^T $$

The algorithm presented above has the ability to fit the maximal elliptical object in the image. It uses calculated value of Mahalanobis distance with the given error-level $\delta$. Clearly, the error level can change the performance of the algorithm. Fig. 6 presents the output of the algorithm for different values of $\delta$.

<figure><img src="image_7.png" /><figcaption>Fig. 6: Different level of $\delta$ for the same image may give different results. Fig. 6a – input image. Fig. 6b initial configuration. Points added to cluster at the earlier stage of the algorithm change the result.</figcaption></figure>

Let now look at the starting configuration of the cluster. Fig. 7 presents the output of the algorithm for different initial configuration of cluster (the initial choice of set $C$). In most cases we obtain almost the same results. However there is a possibility to damage the algorithm effect as is presented at Fig. 7d and 7h, where we start with initial set $C$ given by an interval. Then the algorithm changes just the horizontal size of the cluster while the vertical stay unchanged.

## 3 Experimental results

In this section we present the two connected examples of the algorithm outcome for binary and grayscale iris image formats.

**Binary image.** In this case we apply our algorithm for thresholded image<fnref n="5" /> – see first row at Fig. 8. The fitted ellipse contain the foreground of the image (marked on black with weight equals 1), since we use just the information obtained after thresholding. Fig. 8a and Fig. 8b presents the initial and outcome

<footnote n="5">⁵ We use same morphological operations for remove out-layers and reduce noise.</footnote>
<figure><img src="image_8.png" /><figcaption>Fig. 7: Different initial configuration of the algorithm may give different outcome. The first row present the initial configuration, while the second row – the algorithm outcome.</figcaption></figure>

ellipse respectively. Fig. 8 shows the outcome of the algorithm (boundary of the fitted ellipse) at the original image.

**Grayscale image.** In this case we also use the thresholded image for finding the initial ellipse. However in the next steps of the algorithm we use information about the color in each pixel added to the ellipse. This approach is better because we use full information we have and obtained result is more natural.

More advanced example is presented at Fig. 1. As an outcome of the authors’ algorithm we obtain the fitted ellipse, which statistical description can be used to define the transformation operation (compare Remark 1). Thus we can transform the iris image to make it more convenient for further processing by iris pattern recognition algorithms.

## 4 Conclusions

We presented a new method for ellipse growing based on properties of Mahalanobis distance, which can be used in detection of ellipses in: both binary and grayscale images. The numerical experiments have demonstrated that the algorithm works sufficiently well in both cases. We can apply the algorithm for iris preprocessing in real-life pictures where eyes are photographed sideways. Moreover, we can easily adapt the approach to higher dimensional data (for example in 3D medical images).

In the future work we plan to focus on the automation of the algorithm, in particular in the automatic detection of the necessary parameters (e.g. δ level) and image preprocessing methods (e.g. morphological operations). Furthermore we plan a more complete analysis of the behavior of the algorithm performance.
<figure><img src="image_9.png" /><figcaption>Fig. 8: Application of the authors' algorithm for detection of the pupil and iris at the grayscale images [22] for binary images (first row) and grayscale images: (a), (d) – initial configuration of a cluster, (b), (e) – final size of the cluster, (c), (f) – fitted ellipse at original image.</figcaption></figure>

## Acknowledgments

This work was supported by the Polish National Centre of Science Grant No. 2012/07/N/ST6/02192.

## References

1. Nguyen, T.M., Ahuja, S., Wu, Q.J.: A real-time ellipse detection based on edge grouping. In: Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on, IEEE, 3280–3286, 2009.

2. Greggio, N., Manfredi, L., Laschi, C., Dario, P., Carrozza, M.C.: Robotcub implementation of real-time least-square fitting of ellipses. In: Humanoid Robots, 2008. Humanoids 2008. 8th IEEE-RAS International Conference on, IEEE, 174–181, 2008.

3. Takegami, T., Gotoh, T., Ohyama, G.: An algorithm for model-based stable pupil detection for eye tracking system. Systems and Computers in Japan **35**, 21–31, 2004.

4. Jain, V., Learned-Miller, E.: Fddb: A benchmark for face detection in unconstrained settings. University of Massachusetts, Amherst, Tech. Rep. UM-CS-2010-009, 2010.

5. Jin, Y., Qiu, K., Dai, Y., Xiao, G., Deng, H.: An improved handwritten chinese character recognition based on localized ellipse model. In: Image and Signal Pro-
cessing (CISP), 2010 3rd International Congress on. Volume 4., IEEE, 1803–1807, 2010.

6. Wong, C., Lin, S., Ren, T., Kwok, N.: A survey on ellipse detection methods. In: Industrial Electronics (ISIE), 2012 IEEE International Symposium on, IEEE, 1105–1110, 2012.

7. Illingworth, J., Kittler, J.: A survey of the hough transform. Computer vision, graphics, and image processing **44**, 87–116, 1988.

8. Fitzgibbon, A., Pilu, M., Fisher, R.B.: Direct least square fitting of ellipses. Pattern Analysis and Machine Intelligence, IEEE Transactions on **21**, 476–480, 1999.

9. Prasad, D.K., Leung, M.K.: Methods for ellipse detection from edge maps of real images. Machine Vision-Applications and Systems, 135–162, 2012.

10. Chiang, C.C., Ho, M.C., Liao, H.S., Pratama, A., Syu, W.C.: Detecting and recognizing traffic lights by genetic approximate ellipse detection and spatial texture layouts. International Journal of Innovative Computing, Information and Control **7**, 6919–6934, 2011.

11. Dufrenois, F.: Ellipse fitting with uncertainty and fuzzy decision stage for detection. application in videomicroscopy. In: Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Springer, 432–443, 2001.

12. Prasad, D.K., Leung, M.K.: A hybrid approach for ellipse detection in real images. In: Second International Conference on Digital Image Processing, International Society for Optics and Photonics, 75460I–75460I, 2010.

13. Chia, A.S., Rahardja, S., Rajan, D., Leung, M.K.: A split and merge based ellipse detector with self-correcting capability. Image Processing, IEEE Transactions on **20**, 1991–2006, 2011.

14. Mai, F., Hung, Y., Zhong, H., Sze, W.: A hierarchical approach for fast and robust ellipse extraction. Pattern Recognition **41**, 2512–2524, 2008.

15. Tabor, J., Misztal, K.: Detection of elliptical shapes via cross-entropy clustering. Pattern Recognition and Image Analysis, LNCS, 7887, 656–663, 2013.

16. Daugman, J.G.: High confidence visual recognition of persons by a test of statistical independence. Pattern Analysis and Machine Intelligence, IEEE Transactions on **15**, 1148–1161, 1993.

17. Daugman, J.: New methods in iris recognition. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on **37**, 1167–1175, 2007.

18. Chun, C.N., Chung, R.: Iris recognition for iris tilted in depth. In: Computer Analysis of Images and Patterns, Springer, 530–539, 2003.

19. Dorairaj, V., Schmid, N.A., Fahmy, G.: Performance evaluation of non-ideal iris based recognition system implementing global ica encoding. In: Image Processing, 2005. ICIP 2005. IEEE International Conference on. Volume 3., IEEE, III–285, 2005.

20. Mahalanobis, P.C.: On the generalized distance in statistics. In: Proceedings of the national institute of sciences of India. Volume 2., New Delhi, 49–55, 1936.

21. Königsberger, K.: Analysis 2. Springer (2004)

22. Institute of Automation, Chinese Academy of Science: CASIA iris image database (http://www.cbsr.ia.ac.cn/IrisDatabase.htm), 2013.