Iris Recognition Repository / file revision

 \chapter{Methodology}

 To achieve automated iris recognition, there are three main tasks: first we must locate the iris in a given image. Secondly, it is necessary to encode the iris information into a format which is amenable to calculation and computation, for example a binary string. Finally, the data must be storable, to load and compare these encodings.

 \section{Iris Location}

 When locating the iris there are two potential options. The software could

 require the user to select points on the image, which is both reliable and

 fairly accurate, however it is also time consuming and implausible for any

 real-world application. The other option is for the software to auto-detect the

 iris within the image. This process is computationally complex and introduces a source of error due to the inherent complexities of computer vision. However, as the software will then require less user interaction it is a major step towards producing a system which is suitable for real-world deployment, and thus became a priority for extending the program specification.

 Locating the iris is not a trivial task since its intensity is close to that of

 the sclera\footnote{The white part of the eye.} and is often obscured by

 eyelashes and eyelids. However the pupil, due to its regular size and uniform

 dark shade, is relatively easy to locate. The pupil and iris can be approximated as concentric and this provides a reliable entry point for autodetection.

 \subsection{Pupil}

 The pupil's intensity and location are fairly consistent in most images and

 so it lends itself well to auto-detection. Detection of the pupil can be

 carried out by: removing noise by applying a median blur, thresholding the image

 to obtain the pupil, performing edge detection to obtain the pupil boundary and

 then identifying circles.

 A median filter is an kernel based, convolution filter which blurs an image by setting a pixel value to the median of itself with its neighbours. A na\"ive approach to applying a median filter would be to simply find the median for a given area around each

 pixel by sorting an array and finding the median to replace the current pixel

 with. This could be implemented with a sorting algorithm which would have runtime

 $\mathcal{O}(n \log n)$ on average. However, since the software requires

 several median blurs on different images we require a more efficient solution.

 For an improved algorithm we consult Perreault's paper \cite{median2007}, which

 describes an algorithm to create a median filter in linear time. The process

 (see algorithm \ref{medianfilteralgor}) involves constructing individual column

 histograms and combining them to form histograms centred around a pixel, known

 as a kernel histogram.

 The significant speed increase comes from the way in which the column

 histograms are updated and combined. For each pixel we remove an old column

 histogram from the kernel, shift a new column histogram down one pixel so it is

 centred on the required row and then add this new histogram to the kernel

 histogram. While this radically reduces the number of operations which need to

 be performed for each pixel, there is an initialisation step for each row which

 has runtime linear in the size of the kernel histogram $ \mathcal{O}(r)$. This

 enabled the entire median filter to be applied in a matter of milliseconds.

 \begin{algorithm}

 \caption{Median filtering algorithm as proposed in \cite{median2007}}

 \label{medianfilteralgor}

 \begin{algorithmic}

 \STATE \textbf{Input:} Image X of size $m \times n$, kernel radius $r$.

 \STATE \textbf{Output:} Image Y of size $m \times n$.

 \STATE Initalize each column histogram $h_0, \ldots, h_{n-1}$ as if centred on row $-1$.

 \FOR{$i=1$ to $m$}

 \STATE Shift the first $r$ column histograms $h_0, \ldots, h_{r-1}$ down 1 pixel.

 \STATE Combine these $r$ column histograms to form the kernel histogram $H$.

 \FOR{$j=1$ to $n$}

 \STATE Set pixel $Y_{i,j}$ equal to the median of $H$.

 \STATE Shift column histogram $h_{j+r}$ down 1 pixel.

 \STATE Remove column histogram $h_{j-r-1}$.

 \STATE Add column histogram $h_{j+r}$.

 \ENDFOR

 \ENDFOR

 \end{algorithmic}

 \end{algorithm}

 \begin{figure}

   \centering

 	\includegraphics[width=0.35\textwidth]{pupil_step_1_start}

 	\label{pupil_step_1_start}

 	\hspace{1cm}

 	\includegraphics[width=0.35\textwidth]{pupil_step_2_median}

 	\caption{Image before and after a median filter.}

 		\label{pupil_step_2_median}

 \end{figure}

 The overall effect of the median blur is to reduce the noise and pixel

 intensity complexity of the iris image without perturbing the edge fidelity of

 the original image. This results in a stronger clustering of pixel values in

 the resultant pixel data histogram; this permits a largely noise-free, dynamic

 analysis of features which occupy discrete pixel ranges, such as the pupil (see

 figure \ref{example_histogram}).

 \begin{figure}

 	\centering

 	\includegraphics[width=0.35\textwidth]{example_histogram}

 	\caption{Histogram generated in the application following a median blur of a database image.  Note the distinct, left-most (darkest pixel values) peak as a typical pupil's pixel signature on the image.}

 	\label{example_histogram}

 \end{figure}

 Upon application of a dynamic threshold to our median blurred image the

 leftmost image in figure \ref{pupil_step_3_thresh} is obtained. The location of

 the pupil is well defined, and edge detection can extract this information to

 form a single bit depth image which can be searched for circles.

 The Sobel filter is an edge detection technique which calculates the gradients

 (in both the $x$ and $y$ direction) of the image intensity for each pixel and

 then combines them to give a gradient magnitude. This indicates how sharp the

 boundary is, which is itself an indication of whether an edge is present.

 \begin{figure}

   \centering

 	\includegraphics[width=0.35\textwidth]{pupil_step_3_thresh}

 	\label{pupil_step_3_thresh}

 	\hspace{1cm}

 	\includegraphics[width=0.35\textwidth]{pupil_step_4_sobel}

 	\caption{Thresholded image before and after edge detection with a 2D Sobel convolution filter.}

 	\label{pupil_step_4_sobel}

 \end{figure}

 As can be seen in \ref{pupil_step_4_sobel} the result of this process of

 filtering is a circular artifact denoting the extremeties of the pupil in the

 image. This data requires further analysis for the presence of circular

 artifacts to acquire a "best-fit" representation of the potentially elliptical

 pupil.

 %TODO: make this not logbook styleeee

 %TODO: make this focused towards pupils

 The Hough Transform is implemented to locate the pupil (and subsequently the

 iris).  Given a regular curve -- in this case a circle -- and a suitable range

 of parameters -- $x$ centre, $y$ centre and radius -- the generalised Hough

 transform can query individual pixels in an image for their contribution to a

 globally consistent solution for any parameters within the valid range.

 Due to the high computational complexity of the Hough transform technique (the

 parameter space for a simple circle is in three dimensions and depending on

 valid ranges this can quickly grow to millions of computations) and previous

 considerations for application performance, a number of elements were

 streamlined to accelerate the computation.

 Thresholding the input image has the inherent benefit of changing the virtual

 bit-depth of the image to 1 (black or white). Furthermore, the implemented algorithm saves

 time by only operating on black pixels -- a greyscale implementation would

 significantly add to the processing time.  Additionally a search on the

 threshold result (figure \ref{pupil_step_3_thresh}) gives confident parameter

 estimations for centre and radius which can be used to constrain and guide the

 Hough algorithm.

 \begin{figure}

   \centering

 	\includegraphics[width=0.35\textwidth]{pupil_step_5_hough}

 %	\label{pupil_step_5_hough}

 	\hspace{1cm}

 	\includegraphics[width=0.35\textwidth]{pupil_step_6_finish}

 	\caption{Hough transform solution for a circle (red), given edge detected pupil image.}

 	\label{pupil_step_6_finish}

 \end{figure}

 As can be seen in figure \ref{pupil_step_6_finish}, this process gives fast,

 accurate and reliable solutions for circular artefacts in the thresholded and

 edge detected pupil image.  The basis of iris auto-detection relies on this

 process.

 \subsection{Iris}

 Once we have the location of the pupil clearly defined, the complexity of

 locating the iris is somewhat reduced due to the relative concentricity of the

 pupil and iris. 

 In contrast to pupil detection, efficiently locating the iris is somewhat more

 complicated due to (i) the obstruction of the iris by the eyelids for most

 eyes, (ii) its irregular pattern and (iii) because of the relative similarity with the iris

 boundary and the sclera.

 Nevertheless, following a similar method to that of locating the pupil generally provides good results.

 Again, a median filter is applied to the original image in order to remove noise from the image and to

 strengthen the clustering in the pixel histogram. The resultant histogram is used to identify a point

 that can be used to threshold the image to produce an image similar to figure \ref{iris-threshold}.

 The method involves finding the peaks of the histogram (excluding the left-most peak that represents the pupil)

 and choosing a treshold value between these points. Although not always optimum, this method generally creates

 an image that the Hough Transform can use to find an approximate match for the iris; other, potentially better,

 methods for achieving this threshold are discussed in the future work section (\ref{furtherwork}).

 \begin{figure}

   \centering

 	\includegraphics[width=0.4\textwidth]{iris-threshold}

   \caption{	An example of an image that is obtained by intelligently thresholding the original input image and then using Sobel to edge detect.

 						This image represents the data that is used to locate the iris; the data is used by the Hough Transform to decide

 						on a best-fit circle to represent the location of the iris. A rough semi-circle can be made out by the human eye; this is what

 						allows the Hough Transform to accurately locate the iris. }

     \label{iris-threshold}

 \end{figure}

 The Hough transform is very efficient for the task of finding the iris from an image such

 as this because it is resilient to noise

 and performs well even when a large amount of the circle is hidden. For

 example, when two eyelids are covering a large portion of the iris, such

 as in figure \ref{hough-eyelids}. This provides us with a circle that defines the iris, although

 portions of this are still obscured by the eyelids, meaning that these also need to be defined.

 \begin{figure}

   \centering

 	\includegraphics[width=0.5\textwidth]{hough-eyelids}

   \caption{	A demonstration of the results obtained by applying the Hough Transform to an image such as that in figure

 						\ref{iris-threshold}. The chosen circle is shown in red, which is an average of all of the circles with the 

 						maximum number of votes (in green). The blue circles represent those with the second most votes.}

     \label{hough-eyelids}

 \end{figure}

 \subsection{Eyelids}

 We note that an image of an eye roughly has three intensities, from darkest to

 lightest: pupil, iris and sclera, and eyelids. Hence a suitable thresholding

 method should be able to separate the eyelids from the rest of the image. Otsu

 gives a method in \cite{otsu1975} for appropriately thresholding grey level

 images; the algorithm works as follows. 

 Assume we have an image with $L$ possible intensities for each pixel and $n_i$

 is the number of pixels of intensity $i$. We first normalize the histogram into

 a probability distribution, that is $p_i = n_i / \sum_{i=1}^{L} n_i$. We assume

 that we threshold the image at level $k$ into two classes, $C_0$ containing

 levels less than or equal to $k$ and $C_1$ containing the rest. We then define

 $$\omega(k) := \sum_{i=1}^{k} p_i \text{ and } \mu(k) := \sum_{i=1}^{k} ip_i,$$

 which are the probability of a pixel picked at random being in $C_0$ and the expected (mean) intensity for $C_0$ respectively.

 It is clear to see that that $1-\omega(k)$ is the probability of a pixel being in $C_1$ and $\mu(L)$ is the mean intensity of the entire image. We then calculate

 $$\sigma^2 = \frac{\left[\mu(L)\omega(k) - \mu(k)\right]^2}{\omega(k)[1 - \omega(k)},$$

 which is shown to be measure of the variance between the two classes $C_0$ and $C_1$ by Otsu in \cite{otsu1975}. We calculate this between-class variance for each $k$ and finally threshold on the $k$ where $\sigma^2$ maximized.

 To get any useful information from Otsu thresholding we must first ignore the

 pupil to ensure that the result does not only consist of two classes (the pupil

 and then everything else).

 Once we have ignored the pupil in class calculations we find that Otsu thresholding

 gives us two classes: one containing the iris, sclera and the pupil (since it

 has lowest intensity), and the other class containing the eyelids, see figure

 \ref{otsu-eyelids}.

 With the iris located within the image we must now begin the task of extracting information from it.

 \begin{figure}

   \centering

 	\includegraphics[width=0.35\textwidth]{anothereye}

 		\hspace{1cm}

 	\includegraphics[width=0.35\textwidth]{otsue}

 	\caption{Image before and after a median blur and Otsu threshold.}

 	\label{otsu-eyelids}

 \end{figure}

 \section{Encoding the Iris}

 %TODO: Reasons for unwrapping the iris for the filters. Polar coords.

 The iris is encoded to a unique set of 2048 bits which serve as the fundamental

 identification of that person's particular iris. These iris bit codes can be

 stored in a database and then compared to uniquely identify a person. The size

 of 2048 is sufficiently large to store the data of several particular filters

 on most angles of the iris, while also being sufficiently small to be easily

 stored in a database and manipulated quickly. We wish to extract phase

 information from the iris as opposed to amplitude information since phase

 information is not skewed by pupil deformation. We use Gabor filters to extract

 this phase information as suggested by Daugman \cite{daugman2004}.

 %One of the main problems with this kind of approach is the way in which we 

 %target the iris boundary in order for it to be 

 The Gabor filter is an application of the Gabor wavelet (see equation

 \ref{gaborEquation}) \cite{daugman2004}. This will return two bits depending on

 which quadrant (see figure \ref{quadrants}) the normalised resulting imaginary

 number from this lies in. This equation can be simplified for computation by

 considering it as a combination of two filters: one filter representing the

 real part of the integral and the other representing the imaginary part. Each

 of these filters consist of a combination of a Gaussian and a sinusoidal

 filter (see figure \ref{gabor-combo}). The parameters $\alpha$, $\beta$ and

 $\omega$ are then tuned by constraining the Gaussian filter to range over one

 standard deviation and the sinusoidal filter to range from $-\pi$ to $\pi$.

 \begin{equation}

 \label{gaborEquation}

 h_{\{Re,Im\}} = sgn_{\{Re,Im\}}\int _{\rho} \int _{\phi} I(\rho, \phi) e^{-i\omega(\theta _{0} - \phi)} e^{-(r_{0}-\rho)^{2}/\alpha^{2}} e^{-(\theta_{0}-\phi)^{2}/\beta^{2}} \rho d\rho d\phi

 \end{equation}

 \begin{figure}

 	\centering

 		\includegraphics[width=0.35\textwidth]{quadrants}

 	\caption{The four phase quadrants and the corresponding bit sequences they represent}

 	\label{quadrants}

 \end{figure}

 \begin{figure}

   \centering

 	\includegraphics[width=0.8\textwidth]{gabor-combo}

   \caption{The real (left) and imaginary (right) parts of the Gabor wavelets}

   \label{gabor-combo}

 \end{figure}

 %\subsection{Heatmaps}

 %A heatmap is created by applying a fixed size Gabor filter to every pixel in an

 %unwrapped iris. Then the 2 bit code for each pixel is represented as a colour

 %on the heatmap. By doing this we were able to see clearly which size filters

 %would give us the most informative data when doing comparisons. As shown by

 %figure \ref{heatmaps}, smaller filters produce a largely varying heatmap, and

 %much larger filters give significantly less useful information for comparisons.

 %We will therefore try to use small filters across the area closest to the pupil

 %to capture the large amount of detail seen here. We will then increase the

 %sizes of filters further out in the iris to make sure that we cover a

 %sufficient proportion of the iris in our comparisons, but will try to balance

 %this so that we don't use uninformative filters as in figure \ref{heatmaps}

 \subsection{Filter Placement and Size}

 The Gabor filters need to be placed so that they take account for a large

 enough range of data without missing out the fine detail within the iris. As we

 require 2 bits to uniquely identify each quadrature, we have the additional

 constraint that 1024 filters must be used, allowing a manageable bit code

 length of 256B for each iris which can be split into sections of 4B. To

 simplify the calculations involved in applying the filters to the unwrapped iris they

 can also be considered to all be placed at a uniform rotation of 0. Since it

 can be observed that there is consistent amounts of information at points

 varying in the angular direction in the iris, it is also a good idea to place

 the filters uniformly in this direction. In this implementation 256 angular

 directions were considered because it divides our

 required number of filters evenly and includes a large spread of data across

 the iris. However, in many cases, in the radial direction there is more

 distinct information observed closer to the pupil.

 To include the more important data close to the pupil the filters can be

 positioned so that a larger proportion of them have their centres in this

 range. With the 256 angular directions there are 4 radial filter locations left

 to position. These can be placed uniformly between the bottom of the iris and

 half-way across the iris to allow the data around the pupil to be explored.

 Finally, to make sure that filters are always large enough to represent enough

 data, the constraint that a filter centre cannot be placed on the 3 pixels

 nearest the top and bottom of the image is added. This means that useless

 filters of sizes 1 and 3 will never be included when encoding the iris, and we

 avoid including additional pupil debris that may have been incorporated into

 the iris section. The final set of filter locations across an unwrapped iris is

 represented in figure \ref{filterpos}.

 \begin{figure}[h!]

   \centering

 	\includegraphics[width=0.8\textwidth]{filterpos}

   \caption{Filter positions for an iris of radius 40 between $\theta$=0 and $\theta$=45  }

   \label{filterpos}

 \end{figure}

 The final consideration with the filters is their size. Two schemes for doing

 this are demonstrated in figure \ref{filter-size}. The first (left) aims to

 position the largest possible filter at every filter location. This means that

 the filters fulfil one of the original requirements; that the filters should

 capture as much information as they can. The issue which this scheme suffers

 from is that the filters with their centres in the middle of the iris can be so

 large that they aren't really able to represent some of the finer detail in the

 image. The second scheme (right) tackles this problem

 by capping all filters in the image at a maximum size. This maximum size can be

 tuned in the implementation to get more distinct bitcodes, which is why it is

 favourable and consequently the one we use.

 \begin{figure}

 	\centering

 		\includegraphics[width=0.9\textwidth]{filter-size}

 	\caption{Two schemes for filter sizes and placements at a fixed point in the angular direction in an iris of radius 40. Left: maximum size filter placed. Right: filter sizes capped at 25}

 	\label{filter-size}

 \end{figure}

 \section{Comparisons}

 Iris encodings can be compared by computing a Hamming distance between them. 

 The Hamming distance between two iris codes is calculated as given in \cite{daugman2004}. 

 Assume we have two iris codes, $codeA$ and $codeB$, with corresponding bit masks, 

 $maskA$ and $maskB$ (where a 0 in the bit mask corresponds to a bad bit in that position 

 in the iris code). Then we calculate the hamming distance $H$ as:

 $$H = \frac{\|(codeA \otimes codeB) \cap maskA \cap maskB\|}{\|maskA \cap maskB\|}. $$

 Where $\otimes$ is the bitwise XOR operator and $\cap$ is the bitwise AND operator.

 We can see that the numerator will be the number of differences between the

 mutually non-bad bits of $codeA$ and $codeB$ and that the denominator will be

 the number of mutually non-bad bits. However an astute reader may observe that

 this measure can fail if there is an exceedingly low number of mutually non-bad bits

 causing the numerator to be zero even though there may actually be large differences

 between $codeA$ and $codeB$. However, this is a simple case to handle and will rarely

 occur when comparing iris images.

 This comparison is performed for various shifts in the codes to check for

 rotation of the image, as it is very possible that a subject's eye in the image

 is rotated if the camera or their head is tilted slightly.

 This statistical independence test is the key to iris recognition. It provides

 sufficiently many degrees-of-freedom to fail in every case where the iris

 bitcodes of two different eyes are compared, but uniquely passed when the same

 iris is compared with itself.

 \subsection{Iris Database}

 Since we are able to generate the code and the iris mask directly, these are

 the only two items that are required to be stored in a database, the image

 bitmaps themselves are no longer required.

 We are currently using a basic text file as our database as this was simple to

 implement and for the small number of eyes we have as test subjects this is

 perfectly adequate and proves to be able to compare iris bitcodes extremely

 fast.

 \section{Graphical User Interface}

 Since the software was built in Qt, a cross-platform toolkit, the final product

 runs on Linux, Windows, and Mac desktops, adopting the operating system's

 native toolkit and giving it an integrated feel on all platforms.

 \begin{figure}

   \centering

 	\includegraphics[width=0.8\textwidth]{kde}

   \caption{Linux with Open File view.}

 \end{figure}

 \begin{figure}

   \centering

 	\includegraphics[width=0.45\textwidth]{windows}

 	\includegraphics[width=0.45\textwidth]{mac}

 	\caption{Windows and Mac OS X.}

 \end{figure}

 Usability is an important consideration when creating an application, and

 throughout development the aim was to provide a clean and intuitive interface

 whilst still providing full usability and advanced features. The key

 intellectual challenges for the user interface have been primarily to provide a

 straight-forward and informative access point for the user, but also to provide

 relevant extra data when required with a fall-back mechanism for difficulties

 in auto-detection.

 \begin{figure}

   \centering

 	\includegraphics[width=0.5\textwidth]{heatmapapp}

   \caption{Application with heatmap tab.}

 \end{figure}

 The final product includes relevant data and feedback behaviour such as

 histogram information from the image to allow the advanced user to track-down

 and diagnose auto-detection failures. This information is placed into a tabbed

 interface below the primary image so that it is easily accessible without

 encroaching on our clean interface which allows the average user

 point-and-click refinement (if necessary) of the iris parameters with real-time

 visual feedback without overloading them with this more advanced information.