# Iris Location Algorithm Based on Union-Find-Set and Block Search

Authors: Long-yang Huang; Li-qiang Zhang; Xiao-li Duan
Journal: Journal of Sensors
 (2021)

---

## Abstract

In view of the problem of unstable recognition effect and low robustness of a traditional iris location algorithm, an iris location algorithm based on union-find-set and block search is proposed. Firstly, the inner circle of the iris is roughly positioned by the method of retrieval, and then, the Hough transform is used to accurately locate the pupil. After that, the convolution operation is used to roughly locate the outer circle, and then, the original image is partitioned to search. And the grayscale change in the gray histogram of the screenshot is observed to accurately locate the outer circle. The obtained iris and the iris obtained by the traditional localization algorithm are processed by the same iris recognition algorithm. The results show that the proposed image is more effective in image recognition and has good robustness.


---

## Body

## 1. Introduction

Due to the uniqueness, noninvasiveness, stability, and natural anticounterfeiting of the iris, the iris has higher accuracy than other biometrics [1]. Therefore, iris recognition technology is one of the most popular biometric recognition technologies.The iris recognition process is divided into iris image acquisition, iris quality evaluation, iris location, iris normalization enhancement, and iris feature expression and matching [2]. Iris location is used to locate the inner and outer boundaries of the iris and segment the iris ring region between the two boundaries, so as to facilitate the expression and recognition of iris features [3]. Traditional iris location algorithms include the calculus circle template method and Hough method based on edge detection [4, 5]. The inner boundary of the iris is roughly located by using the lower edge of the binary image, and the outer boundary of the iris is roughly located by using the one-dimensional gray mean signal on both sides of the inner boundary center [6]. An iris location algorithm based on edge detection and circle fitting is proposed [7]. The iris location algorithm based on a small-scale search is adopted [8]. Although these algorithms can accurately locate the position of the iris, they have poor robustness and high requirements for the image. Moreover, they have poor anti-interference ability to rough eyelids, illumination, and other noise interference, and the recognition effect is unstable. The algorithm processing flow of this paper is shown in Figure 1.Figure 1
Iris inner and outer circle positioning process.Therefore, the iris localization algorithm based on union-find-set and block search is proposed in this paper. For the inner circle positioning of the iris, the method of firstly adopting and collecting the method to realize the coarse positioning of the inner circle can overcome the influence of spot factors, and then, the Hough transform is adopted to improve the speed of accurate positioning of the inner circle. For outer circle positioning, the convolution operation is used to roughly locate the outer circle, and then, the original image is partitioned to search. Then, the grayscale change in the gray histogram of the screenshot is observed to accurately locate the outer circle. Experiments show that the proposed algorithm can effectively enhance the robustness of iris localization, and the iris images acquired by different collectors under different conditions can be used for iris localization, and the recognition effect is stable.


## 2. Algorithm Implementation

### 2.1. The Inner Circle Positioning of the Iris

In some application problems, a set ofn elements needs to be divided into several disjoint subsets according to the relationship between the elements. To solve this kind of problem, first make each element form a separate collection. If there are direct or indirect links between elements in different collections, the two collections are merged until there is no contact in any of the elements in the collection. Since the main concern in such problems is the merge and lookup of sets, such sets are referred to as union-find-set. The mathematical model is as follows.Several mutually disjoint dynamic setsS=A,B,C⋯ are known, which support the following operations:
(i)
initialA,x. Construct a collection named A that contains only one element x(ii)
mergeA,B. Combine the sets A and B, and the result is named A or B(iii)
findx. Find the collection of elements x and return the name of the collectionThe processing steps of the union-find-set are as follows:(i)
Use theinitialA,x operation to create a subset of each element in the collection(ii)
The setsA and B of the x and y elements are obtained by using the findx operation for each associated element pair x,y(iii)
IfA and B are different, then x and y are considered to belong to different sets, and then, the mergeA,B operation is performed(iv)
Go back to step 2 to process the next pair of associated elements until all associated element pairs have been processedIn order to improve the efficiency of union-find-set execution, the tree structure is adopted in this paper to implement and check the set, where the name of the root represents the name of the generated subset and is directly or indirectly associated with any two elements in the tree. There is no direct or indirect association between any two elements in different trees. When the collection tree of two related elements merges, simply find the root of the tree in which each element is located, and then, use one tree as the tree root tree of the other tree.For example, setset=1,2,3,4,5,6,7,8,9,10, and the associated element pair is 5,1,7,4,10,4,4,2,6,3,8,3,9,3. The processing results of the union-find-set are shown in Table 1, where line 2 of Table 1 is the result of the initialA,x processing. The first line is all the elements in the collection, the second line is the collection where each element is located, and the name of the collection is the name of the element. Line 3 of Table 1 is the result of union-find-set execution. The number of sets with the same element and set name in the figure is the final and the result of the collection process.Table 1
The union-find-set set initialization and processing results.
i12345678910Initial set(i)12345678910Result set(i)1232134334The grayscale feature of the iris image is that the grayscale of the pupil region is generally smaller than the grayscale of the iris region. The grayscale of the iris region is generally smaller than the grayscale of the sclera region. And the grayscale change in the same region is relatively small, while that at the boundary of different regions is relatively large. Each pixel in the iris image can be regarded as a set element. If the gray level difference between two adjacent pixelsi and j is less than a certain threshold k, it can be considered that there is an association relationship between the two pixels, denoted as i,j. In this way, the division of different types of regions in the iris can be realized by the union-find-set operation. As the gray level of the pupil area is smaller than that of other regions, the final pupil area can be determined according to the size of the obtained gray level of each region. For a visible iris image, the gray value of the area around the light spot in the inner pupil will show a significant jump. Since the area of the light spot is usually smaller than the area of the pupil, the spot only changes the gray level of a small portion of the pupil area, and the gray level of most of the pupil area is still not affected by the spot. Thus, through the union-find-set operation, a pupil with a partial defect is obtained. This defective pupil can be used as a rough positioning of the pupil, as shown in Figure 2. Figure 2(b) is a result of rough positioning of the pupil region by the union-find-set operation of Figure 2(a).Figure 2
The inner circle positioning of the iris.
(a)(b)(c)On the basis of obtaining the pupil coarse location, the edge tracking method is used to obtain all the edge points of the pupil region. Then, the final inner contour of the iris is obtained by the Hough transform. Because the pupil area is determined before the Hough transform, the search range of the circle center and circle radius is greatly reduced. In addition, because the points used in the Hough transform are edge points obtained by edge tracking, there are no other interference edge points outside the pupil, so the speed of the Hough transform is greatly improved. Figure2(c) is the final inner contour of the iris obtained by the Hough transform.The coarse positioning of the iris inner circle by union-find-set can quickly complete the coarse positioning of the iris pupil, and even in the case of spot interference, most of the pupil can be obtained. Then, the Hough transform is used to determine the precise inner circle contour and improve the positioning efficiency of the inner circle.


### 2.2. The Outer Circle Positioning of the Iris

Although the inner and outer boundaries of the iris are not concentric circles, there is a certain coupling relationship between them. Therefore, the rough location of the center of the pupil circle can be obtained by combining the rough location of the outer ring with the fine location of the inner ring. Firstly, the 5-ary convolution operation is used to process the image. After convolution, the result is binarized. The binary image is shown in Figure3(b).Figure 3
The outer circle positioning of the iris.
(a)(b)(c)(d)In order to calculate the number of white points on the curve of a specified angle range, the number of different radii should be calculated, and the variation range of the radius gradually increases fromr,2×r. Since the upper and lower parts of the iris image are easily interfered by noise such as eyelids, the number of white points under a certain iris angle is only calculated in order to reduce the interference of noise on the positioning of the outer boundary of the iris. It can be seen from Figure 3(b) that the white spot on the lower right side of the iris is more and easy to read. To read as many white points as possible under the condition of less interference, the angle range is selected from the horizontal direction of the pupil center to the right side clockwise 0~60°, which is calculated as the following formula.
(1)maxxc,yc,r∂∂rGσr∗∫r−t/2xc,yc,rr+t/2∮Ix,yπr+t/22−πr−t/22dsdr,where ∗ is the convolution operation. Gσr is the Gaussian smoothing function.
(2)Gσr=12πσer−rc2/2σ2.The pupil centerxc,yc of the inner circle is used as the search point, and the radius is continuously increased. The number of white points of each arc is calculated in turn, and the maximum value is determined to determine the center and radius xc,yc,R. This will roughly establish the position of the outer circle of the iris. The outer circle is roughly positioned as shown in Figure 3(c).There are two problems in the outer circle coarse positioning of the convolution operation. First of all, the outer circle is a concentric circle centered on the pupil. Secondly, the ratio of the iris radius to the pupil radius cannot be accurately predicted due to the different conditions of each image. According to the physiological practice, the iris radius of the human eye is about 1~2 times of the pupil radius, and the maximum radius is set to be 2 times of the pupil radius. Therefore, it is necessary to use the block search method again to perform the precise positioning of the outer ring. The rough location of the outer circle needs two segmentation detection operators of the cylinder center and radius boundary in the horizontal direction.According to the gray histogram of the detection operator, the detection operator is moved left and right, and the gray distribution in the gray histogram of the detection operator is compared with the gray distribution in the gray histogram of the eye image. Then, the gray value distributions on the left and right sides are, respectively, obtained to reach the gray value in the sclera region, and the detection operator moves the distancek to the left and the distance to the right to m. The center of the coarse positioning circle is xc,yc and the radius is R. After moving, the center of the circle x^c,y^c can be calculated as follows.
(3)x^c=xc−k2+m2,y^c=yc.And the radiusR^ can be calculated as follows.
(4)R^=R+k2+m2.The precisely positioned outer circle is shown in Figure3(d).


## 2.1. The Inner Circle Positioning of the Iris

In some application problems, a set ofn elements needs to be divided into several disjoint subsets according to the relationship between the elements. To solve this kind of problem, first make each element form a separate collection. If there are direct or indirect links between elements in different collections, the two collections are merged until there is no contact in any of the elements in the collection. Since the main concern in such problems is the merge and lookup of sets, such sets are referred to as union-find-set. The mathematical model is as follows.Several mutually disjoint dynamic setsS=A,B,C⋯ are known, which support the following operations:
(i)
initialA,x. Construct a collection named A that contains only one element x(ii)
mergeA,B. Combine the sets A and B, and the result is named A or B(iii)
findx. Find the collection of elements x and return the name of the collectionThe processing steps of the union-find-set are as follows:(i)
Use theinitialA,x operation to create a subset of each element in the collection(ii)
The setsA and B of the x and y elements are obtained by using the findx operation for each associated element pair x,y(iii)
IfA and B are different, then x and y are considered to belong to different sets, and then, the mergeA,B operation is performed(iv)
Go back to step 2 to process the next pair of associated elements until all associated element pairs have been processedIn order to improve the efficiency of union-find-set execution, the tree structure is adopted in this paper to implement and check the set, where the name of the root represents the name of the generated subset and is directly or indirectly associated with any two elements in the tree. There is no direct or indirect association between any two elements in different trees. When the collection tree of two related elements merges, simply find the root of the tree in which each element is located, and then, use one tree as the tree root tree of the other tree.For example, setset=1,2,3,4,5,6,7,8,9,10, and the associated element pair is 5,1,7,4,10,4,4,2,6,3,8,3,9,3. The processing results of the union-find-set are shown in Table 1, where line 2 of Table 1 is the result of the initialA,x processing. The first line is all the elements in the collection, the second line is the collection where each element is located, and the name of the collection is the name of the element. Line 3 of Table 1 is the result of union-find-set execution. The number of sets with the same element and set name in the figure is the final and the result of the collection process.Table 1
The union-find-set set initialization and processing results.
i12345678910Initial set(i)12345678910Result set(i)1232134334The grayscale feature of the iris image is that the grayscale of the pupil region is generally smaller than the grayscale of the iris region. The grayscale of the iris region is generally smaller than the grayscale of the sclera region. And the grayscale change in the same region is relatively small, while that at the boundary of different regions is relatively large. Each pixel in the iris image can be regarded as a set element. If the gray level difference between two adjacent pixelsi and j is less than a certain threshold k, it can be considered that there is an association relationship between the two pixels, denoted as i,j. In this way, the division of different types of regions in the iris can be realized by the union-find-set operation. As the gray level of the pupil area is smaller than that of other regions, the final pupil area can be determined according to the size of the obtained gray level of each region. For a visible iris image, the gray value of the area around the light spot in the inner pupil will show a significant jump. Since the area of the light spot is usually smaller than the area of the pupil, the spot only changes the gray level of a small portion of the pupil area, and the gray level of most of the pupil area is still not affected by the spot. Thus, through the union-find-set operation, a pupil with a partial defect is obtained. This defective pupil can be used as a rough positioning of the pupil, as shown in Figure 2. Figure 2(b) is a result of rough positioning of the pupil region by the union-find-set operation of Figure 2(a).Figure 2
The inner circle positioning of the iris.
(a)(b)(c)On the basis of obtaining the pupil coarse location, the edge tracking method is used to obtain all the edge points of the pupil region. Then, the final inner contour of the iris is obtained by the Hough transform. Because the pupil area is determined before the Hough transform, the search range of the circle center and circle radius is greatly reduced. In addition, because the points used in the Hough transform are edge points obtained by edge tracking, there are no other interference edge points outside the pupil, so the speed of the Hough transform is greatly improved. Figure2(c) is the final inner contour of the iris obtained by the Hough transform.The coarse positioning of the iris inner circle by union-find-set can quickly complete the coarse positioning of the iris pupil, and even in the case of spot interference, most of the pupil can be obtained. Then, the Hough transform is used to determine the precise inner circle contour and improve the positioning efficiency of the inner circle.


## 2.2. The Outer Circle Positioning of the Iris

Although the inner and outer boundaries of the iris are not concentric circles, there is a certain coupling relationship between them. Therefore, the rough location of the center of the pupil circle can be obtained by combining the rough location of the outer ring with the fine location of the inner ring. Firstly, the 5-ary convolution operation is used to process the image. After convolution, the result is binarized. The binary image is shown in Figure3(b).Figure 3
The outer circle positioning of the iris.
(a)(b)(c)(d)In order to calculate the number of white points on the curve of a specified angle range, the number of different radii should be calculated, and the variation range of the radius gradually increases fromr,2×r. Since the upper and lower parts of the iris image are easily interfered by noise such as eyelids, the number of white points under a certain iris angle is only calculated in order to reduce the interference of noise on the positioning of the outer boundary of the iris. It can be seen from Figure 3(b) that the white spot on the lower right side of the iris is more and easy to read. To read as many white points as possible under the condition of less interference, the angle range is selected from the horizontal direction of the pupil center to the right side clockwise 0~60°, which is calculated as the following formula.
(1)maxxc,yc,r∂∂rGσr∗∫r−t/2xc,yc,rr+t/2∮Ix,yπr+t/22−πr−t/22dsdr,where ∗ is the convolution operation. Gσr is the Gaussian smoothing function.
(2)Gσr=12πσer−rc2/2σ2.The pupil centerxc,yc of the inner circle is used as the search point, and the radius is continuously increased. The number of white points of each arc is calculated in turn, and the maximum value is determined to determine the center and radius xc,yc,R. This will roughly establish the position of the outer circle of the iris. The outer circle is roughly positioned as shown in Figure 3(c).There are two problems in the outer circle coarse positioning of the convolution operation. First of all, the outer circle is a concentric circle centered on the pupil. Secondly, the ratio of the iris radius to the pupil radius cannot be accurately predicted due to the different conditions of each image. According to the physiological practice, the iris radius of the human eye is about 1~2 times of the pupil radius, and the maximum radius is set to be 2 times of the pupil radius. Therefore, it is necessary to use the block search method again to perform the precise positioning of the outer ring. The rough location of the outer circle needs two segmentation detection operators of the cylinder center and radius boundary in the horizontal direction.According to the gray histogram of the detection operator, the detection operator is moved left and right, and the gray distribution in the gray histogram of the detection operator is compared with the gray distribution in the gray histogram of the eye image. Then, the gray value distributions on the left and right sides are, respectively, obtained to reach the gray value in the sclera region, and the detection operator moves the distancek to the left and the distance to the right to m. The center of the coarse positioning circle is xc,yc and the radius is R. After moving, the center of the circle x^c,y^c can be calculated as follows.
(3)x^c=xc−k2+m2,y^c=yc.And the radiusR^ can be calculated as follows.
(4)R^=R+k2+m2.The precisely positioned outer circle is shown in Figure3(d).


## 3. Experimental Results and Analysis

In the experiments, the CASIA-Iris-Interval iris library [9] of the Chinese Academy of Sciences and the iris library collected by our laboratory were used. In the CASIA-Iris-Interval iris library, 50 of these categories were selected, and 15 images were selected for each category, for a total of 750 images. The visible iris map library collected by our laboratory is mainly from 1200 photos of students and patients, with a resolution of 800×600. The image has passed the quality evaluation and detection in advance, but it contains a variety of types, including images close to the boundary and heavy eye hairs, which are used to detect the robustness of the algorithm.


### 3.1. Image Feature Expression and Matching

In this paper, the rubber ring model is used to uniformly normalize the iris image, and the circular rainbow is expanded into a512rectangle×64. The strongest part of the texture is intercepted and cut into 256×32 fixed rectangular regions to enhance the image texture.In the experiment, the main frequency of CPU is 2.5 GHz, the memory is 8 GB, and the operating system is Windows 10. Before feature extraction, all normalized iris images are translated horizontally to eliminate the problem of iris rotation. Then, two-dimensional Gabor filter is used to extract feature texture information. The attributes of the iris image are determined by comparing the Euclidean distance between samples.


### 3.2. Experimental Judgment Indicators and Experimental Results

The ROC curve is a curve indicating the relationship between False Reject Rate (FRR) and False Accept Rate (FAR) [10]. The ROC curve reflects the matching performance of the iris recognition algorithm [11]. The closer to the horizontal and vertical axes, the better the performance of the system. When the FRR is equal to the value of FAR, which is the best system performance, the value is called Equal Error Rate (EER) [12]. The smaller the EER, the better the performance. In addition, the Correct Recognition Rate (CRR) is also one of the performance evaluation indicators of the commonly used iris recognition system [13].This paper is based on CRR, EER, ROC curve, and algorithm in the average time (pupil time). The outer circle positioning average time (iris time) and the overall average positioning time (time) and the number of irises successfully positioned by the positioning algorithm are compared [14–16].The experimental results of the CASIA-Iris-Interval iris library are shown in Table2. The ROC curve is shown in Figure 4. The experimental results of our laboratory are shown in Table 3, and the ROC curve is shown in Figure 5.Table 2
Results of the CASIA-Iris-Interval iris library.
AlgorithmSuccess numberPupil time (s)Iris time (s)Time (s)CRR (%)EER (%)Literature [4]7280.751.021.7695.81.38Literature [6]7240.670.941.6296.11.03Literature [7]7170.630.761.3897.20.84Proposed7490.600.681.2497.40.65Figure 4
The ROC curve of CASIA-Iris-Interval iris library experiment results.Table 3
Results of our laboratory.
AlgorithmSuccess numberPupil time (s)Iris time (s)Time (s)CRR (%)EER (%)Literature [4]11480.751.021.7695.51.38Literature [6]11570.690.951.6496.81.03Literature [7]11780.630.771.3997.70.84Proposed11880.570.681.2697.90.67Figure 5
The ROC curve of our laboratory experiment results.


## 3.1. Image Feature Expression and Matching

In this paper, the rubber ring model is used to uniformly normalize the iris image, and the circular rainbow is expanded into a512rectangle×64. The strongest part of the texture is intercepted and cut into 256×32 fixed rectangular regions to enhance the image texture.In the experiment, the main frequency of CPU is 2.5 GHz, the memory is 8 GB, and the operating system is Windows 10. Before feature extraction, all normalized iris images are translated horizontally to eliminate the problem of iris rotation. Then, two-dimensional Gabor filter is used to extract feature texture information. The attributes of the iris image are determined by comparing the Euclidean distance between samples.


## 3.2. Experimental Judgment Indicators and Experimental Results

The ROC curve is a curve indicating the relationship between False Reject Rate (FRR) and False Accept Rate (FAR) [10]. The ROC curve reflects the matching performance of the iris recognition algorithm [11]. The closer to the horizontal and vertical axes, the better the performance of the system. When the FRR is equal to the value of FAR, which is the best system performance, the value is called Equal Error Rate (EER) [12]. The smaller the EER, the better the performance. In addition, the Correct Recognition Rate (CRR) is also one of the performance evaluation indicators of the commonly used iris recognition system [13].This paper is based on CRR, EER, ROC curve, and algorithm in the average time (pupil time). The outer circle positioning average time (iris time) and the overall average positioning time (time) and the number of irises successfully positioned by the positioning algorithm are compared [14–16].The experimental results of the CASIA-Iris-Interval iris library are shown in Table2. The ROC curve is shown in Figure 4. The experimental results of our laboratory are shown in Table 3, and the ROC curve is shown in Figure 5.Table 2
Results of the CASIA-Iris-Interval iris library.
AlgorithmSuccess numberPupil time (s)Iris time (s)Time (s)CRR (%)EER (%)Literature [4]7280.751.021.7695.81.38Literature [6]7240.670.941.6296.11.03Literature [7]7170.630.761.3897.20.84Proposed7490.600.681.2497.40.65Figure 4
The ROC curve of CASIA-Iris-Interval iris library experiment results.Table 3
Results of our laboratory.
AlgorithmSuccess numberPupil time (s)Iris time (s)Time (s)CRR (%)EER (%)Literature [4]11480.751.021.7695.51.38Literature [6]11570.690.951.6496.81.03Literature [7]11780.630.771.3997.70.84Proposed11880.570.681.2697.90.67Figure 5
The ROC curve of our laboratory experiment results.


## 4. Conclusion and Future Work

An iris location algorithm based on a joint search set and block search is proposed. The inner circle of the iris is roughly located by the joint search set method, and then, the inner circle of the pupil is accurately located by the Hough transform. Firstly, the convolution operation is used to roughly locate the outer circle of the iris, and then, the block search is used to accurately locate the outer circle of the iris. Under the same feature representation and recognition algorithm, it is compared with other location methods. The experimental results show that the ROC curve of this method is closer to the horizontal and vertical coordinates, and the average time is shortened. This method has high precision and good robustness.The future work of this paper is the combination of theory and practice, so that the proposed algorithm can meet the needs of actual target detection.



---

*Source: 7300864-2021-07-06.xml*