Iris Recognition Repository: reports/final/content/method.tex@7f671b74a3a8 (annotated)

file
revisions
annotate
diff
raw

reports/final/content/method.tex@7f671b74a3a8 (annotated)

reports/final/content/method.tex

2010-03-19

author: francis
date: Fri Mar 19 09:09:52 2010 +0000
changeset 395: 7f671b74a3a8
parent 392: 0d5b1a284478
child 400: 8ac89faccb3d
permissions: -rw-r--r--

Other stuff

 \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.

Iris Recognition Repository / annotate

reports/final/content/method.tex@7f671b74a3a8 (annotated)

reports/final/content/method.tex