OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 14 — Jul. 9, 2007
  • pp: 8667–8677

Optics InfoBase > Optics Express > Volume 15 > Issue 14 > Page 8667

« Show journal navigation

A coherent framework for fingerprint analysis: are fingerprints Holograms?

Kieran G. Larkin and Peter A. Fletcher  »View Author Affiliations


Optics Express, Vol. 15, Issue 14, pp. 8667-8677 (2007)
http://dx.doi.org/10.1364/OE.15.008667


View Full Text Article

Acrobat PDF (1489 KB)


Advanced Search

Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We propose a coherent mathematical model for human fingerprint images. Fingerprint structure is represented simply as a hologram – namely a phase modulated fringe pattern. The holographic form unifies analysis, classification, matching, compression, and synthesis of fingerprints in a self-consistent formalism. Hologram phase is at the heart of the method; a phase that uniquely decomposes into two parts via the Helmholtz decomposition theorem. Phase also circumvents the infinite frequency singularities that always occur at minutiae. Reliable analysis is possible using a recently discovered two-dimensional demodulator. The parsimony of this model is demonstrated by the reconstruction of a fingerprint image with an extreme compression factor of 239.

© 2007 Optical Society of America

1. Introduction

Readers may be surprised to learn that the analysis, classification, and recognition of human fingerprint images are still considered by many experts [1–3

D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of fingerprint recognition (Springer, New York, 2003).

] to be unsolved problems. Furthermore, the search for higher compression ratios is still considered by many to be an important research topic [4–6

A. K. Jain and S. Pankanti, “Automated Fingerprint Identification and Imaging Systems,” in Advances in Fingerprint Technology, H. C. Lee and R. E. Gaensslen, eds., (CRC Press, 2001).

] The widely adopted FBI standard for fingerprint data compression [7

C. M. Brislawn, “Fingerprints go digital,” Notices of the AMS 42, 1278–1283 (1995).

] yields typical ratios of 15:1, and extreme ratios measured in the hundreds have appeared quite unattainable. Numerous approaches to fingerprint representation have been tried in the last few decades, but, with hindsight, none have been broadly applicable. In this paper we build on previous developments in fingerprint research and show how a simple model can at last harmonize fingerprint analysis with fingerprint synthesis, and thereby enable unsurpassed fingerprint compression. It is no coincidence that critical matching features such as minutiae appear as uniquely determined components of the representation. At the very heart of the model is the idea of two dimensional phase modulation coupled with a recently proposed analytic method known as vortex demodulation [8

K. G. Larkin, D. Bone, and M. A. Oldfield, “Natural demodulation of two-dimensional fringe patterns: I. General background to the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1862–1870 (2001). http://www.opticsinfobase.org/abstract.cfm?URI=josaa-18-8-1862 [CrossRef]

].

It seems from our perspective that the two essential problems facing fingerprint representation have already been solved by optical physicists.

The first problem is how to reliably model the fingerprint minutiae? More than a century ago Galton [9

F. Galton, Finger Prints (Macmillan, London, 1892). http://galton.org/books/finger-prints/index.htm

] referred to the “minute peculiarities due to branchings of existing ridges, and to the abrupt interpolations of new ones”. Subsequently these features became better known as minutiae. Similarities between optical interferograms and fingerprint patterns have been known for some time by optics researchers. In the seminal 1974 paper by Nye and Berry [10

J. F. Nye and M. V. Berry, “Dislocations in wave trains,” Proc. R. Soc. Lond. A. 336, 165–190 (1974). [CrossRef]

], ridge endings in wave-fronts (namely dislocations) are uniquely associated with spiral structures in the phase representation. Yet fingerprint researchers do not seem to be acquainted with the connection between minutiae and phase spirals [11

A. W. Senior, R. M. Bolle, N. K. Ratha, and S. Pankanti, “Fingerprint Minutiae: A Constructive Definition,” in Workshop on biometrics, IEEE ECCV, (Copenhagen, Denmark, 2002).

, 12

A. Ross, J. Shah, and A. K. Jain, “From Template to Image: reconstructing fingerprints from minutiae points,” IEEE Trans PAMI 29, 544–560 (2007). [CrossRef]

]. Dislocations, or phase vortex spirals, have been found to be ubiquitous in scalar and vector fields, giving rise to an active field of research called singular optics. In a related area known as 2-D phase unwrapping, analogous results have been obtained using the mathematical concept of residues or phase singularities. [13–17

R. M. Goldstein, H. A. Zebker, and C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Science 23, 713–720 (1988). [CrossRef]

]. In parallel with the optics research there have been a few key publications on oriented patterns (such as fingerprints), primarily from point of view of topology [18

R. Penrose, “The topology of ridge systems,” Ann. Hum. Genet.,Lond. 42, 435–444 (1979). [CrossRef]

], image processing [19

M. Kass and A. Witkin, “Analyzing oriented patterns,” Computer vision, graphics, and image processing 37, 362–385 (1987). [CrossRef]

, 20

C. F. Shu and R. C. Jain, “Direct Estimation and Error Analysis For Oriented Patterns,” CVGIP-Image Understanding 58, 383–398 (1993). [CrossRef]

], and chaotic Rayleigh-Bernard convection [21

D. A. Egolf, I. V. Melnikov, and E. Bodenschatz, “Importance of local pattern properties in spiral defect chaos,” Phys. Rev. Lett. 80, 3228–3231 (1998). [CrossRef]

]. Essentially these works have shown that oriented patterns can be uniquely decomposed into a small number of topologically distinct discontinuities and a well defined smooth flow field. Fingerprint research has concentrated on using the ridge orientation and ridge spacing (or its reciprocal, frequency) as the basic representation. Unfortunately the frequency representation fails to work properly because there is an infinite singularity at each dislocation point. The 1993 paper by Sherlock and Monro [22

B. G. Sherlock and D. M. Monro, “A model for interpreting fingerprint topology,” Pattern Recogn. 26, 1047–1055 (1993). [CrossRef]

] introduced the idea of computing a ridge orientation map of a fingerprint and directly identifying the key directional features (known as cores and deltas) therein, but did not extend the insight to a full phase representation. Most recently Ross et al [12

A. Ross, J. Shah, and A. K. Jain, “From Template to Image: reconstructing fingerprints from minutiae points,” IEEE Trans PAMI 29, 544–560 (2007). [CrossRef]

] have demonstrated partial fingerprint reconstruction, but complete reconstruction seems unlikely from oriented minutiae data alone.

The second problem, given a suitable model (like the hologram model), is how to reliably estimate the model parameters? Crucially, a direct solution of this two-dimensional demodulation problem was proposed in 2001 [8

K. G. Larkin, D. Bone, and M. A. Oldfield, “Natural demodulation of two-dimensional fringe patterns: I. General background to the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1862–1870 (2001). http://www.opticsinfobase.org/abstract.cfm?URI=josaa-18-8-1862 [CrossRef]

].

In the following sections we propose to link the two solutions and thereby establish a unified basis for fingerprint analysis. In one sense this work represents the culmination of our image demodulation research, although the following is merely an outline of the full analysis. A more comprehensive exposition is in preparation and will be presented at a later date.

2. The hologram model

Ideally a fingerprint model would incorporate pattern formation or morphogenesis (as originally described by Turing [23

A. M. Turing, “The chemical basis of morphogenesis, reprinted from Philosophical Transactions of the Royal Society (Part B), 237, 37-72 (1953)," Bull. Math. Biol. 52, 153–197 (1990). [CrossRef] [PubMed]

] and more recently by Witkin [24

A. Witkin and M. Kass, “Reaction-diffusion textures,” Comput. Graphics 25, 299–308 (1991). [CrossRef]

]). However, it is now known that emergent features (such as minutiae) “cannot be explicitly represented in the initial and boundary conditions” of a morphogenic process [25

J. P. Crutchfield, ed., Is Anything Ever New? Considering Emergence, in Complexity: Metaphors, Models, and Reality, (Addison-Wesley, Redwood City, 1994). http://www.santafe.edu/research/publications/wpabstract/199403011

]. In practice it is far more effective to define a model based on the final emerged properties of a pattern (in particular the exact minutiae locations). The thorny question of whether or not the proposed model is the best of all possible models is not considered in this paper. We hope that other researchers may be inspired to use recent developments in model selection criteria [26

J. Myung and M. Pitt, “Model Selection Methods,” in Amsterdam Workshop on Model Selection(Amsterdam, 2004). http://www2.fmg.uva.nl/modelselection/presentation.cfm?presenter=5

] to resolve this difficult question.

We take as our starting point a digital image of a human fingerprint. This may be a scan of a classic ink on paper imprint as shown in Fig. 1, or - more likely - the digital image from a modern fingerprint sensor.

Fig. 1. Digitized fingerprint image from NIST database (262,144 bytes).

Our model represents the intensity of a fingerprint image as amplitude and frequency modulated (AM-FM) function. The canonical equation defining the model is also the general equation for the interference of two coherent beams (wave-fronts):

f xy=a xy+b xy.cos [ψ xy]+n xy.
(1)

The word hologram was first coined in 1949 by Gabor [27

D. Gabor, “Microscopy by reconstructed wave-fronts,” Pro. R. Soc. London 197, 454–487 (1949). [CrossRef]

] to describe precisely the above image model. Actual fingerprint images are often binarized – black and white – and so the cosine in the above equation becomes a square wave. The above formulation is well-posed when the offset a(x, y), the amplitude b(x, y), and the phase ψ(x,y) are suitably smooth real functions. We note that the sign of the phase ψ(x,y) contains a global ambiguity that we also disregard here. A noise term n(x,y) formally completes the model, and may contain finer details, such as pores, as well as noise and other artifacts that do not easily fit the hologram model. It transpires that the AM-FM fingerprint model has been attempted several times before: in 1987 Kass proposed a dominant frequency that is locally distorted by curvilinear co-ordinates [19

M. Kass and A. Witkin, “Analyzing oriented patterns,” Computer vision, graphics, and image processing 37, 362–385 (1987). [CrossRef]

], and more recently Chikkerur used a locally defined surface wave [3

S. Chikkerur, A. N. Cartwright, and V. Govindaraju, “Fingerprint Image Enhancement using STFT Analysis,” in ICAPR, S. Singh, M. Singh, C. Apte, and P. Perner, eds., (Springer-Verlag, Bath, UK, 2005).

]. Furthermore the well known SFRINGE fingerprint synthesis method of Cappelli (see chapter 6 of Ref [1

D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of fingerprint recognition (Springer, New York, 2003).

]) uses Gabor filters to iteratively apply orientation and frequency constraints to a random seed image. What had not been realized before is that such fingerprint models are awkward because frequency is unbounded wherever a minutia occurs. Our approach neatly avoids these singularities by working directly with the phase instead of its unbounded derivative (better known as the instantaneous frequency). It is worth noting that in 1995 Daugman demonstrated a very effective modulation model for what was to become the preeminent biometric, the iris [28

J. G. Daugman and C. J. Downing, “Demodulation, predictive coding, and spatial vision,” J. Opt. Soc. Am. A 12, 641–660 (1995). [CrossRef]

].

Our approach is founded on the crucial observation that the main minutiae – ridge endings and bifurcations – can be simply represented by spiral phases of either positive or negative polarity. It transpires that this observation can be formalized by the Helmholtz Decomposition Theorem (HDT). Usually this is restricted to vector fields, but is equally applicable to the phase representation in which the phase can be interpreted as a potential function. The HDT allows us to uniquely decompose the phase into two parts. The first part is what we call the continuous phase. The second part is what we call the spiral phase:

ψ xy= ψC xy+ ψS xy.
(2)

This much is now well known in two-dimensional phase unwrapping theory, thanks to Ghiglia and Pritt’s classic 1998 textbook [17

D. C. Ghiglia and M. D. Pritt, Two-dimensional phase unwrapping (John Wiley and Sons, New York, 1998).

]. Multiple minutiae are simply generated from spiral phase using the addition of a multitude of spatially shifted, modulo 2π, arctangent functions:

ψS xy= ∑ n=1N pnarctan ( y− yn x− xn).
(3)

What we call the polarity of each minutia is given by pn =±1, and its location by (xn,yn ). We note that the relation between polarity and the incidence of ridge endings or ridge bifurcations is dependent on the direction of the local phase gradient. The spiral phase allows an abrupt change in the local fringe density, either inserting or deleting a ridge. Figure 2 shows an artificial fingerprint pattern generated using Eq. (1) – Eq. (3). The pattern shows a loop and a delta structure [18

R. Penrose, “The topology of ridge systems,” Ann. Hum. Genet.,Lond. 42, 435–444 (1979). [CrossRef]

, 22

B. G. Sherlock and D. M. Monro, “A model for interpreting fingerprint topology,” Pattern Recogn. 26, 1047–1055 (1993). [CrossRef]

] in addition to minutiae. In 1999 Kosz [29

D. Kosz, “New numerical methods of fingerprint recognition based on mathematical description of arrangement of dermatoglyphics and creation of minutiae,” in Biometrics in Human Service User Group Newsletter,Mintie D., ed., (1999). http://www.ct.gov/dss/cwp/view.asp?A=2349&Q=304724

] proposed and demonstrated an effective fingerprint synthesis method based on Eq (3), but was unable to extend the method to analysis. Further details are provided online by Bicz [30

W. Bicz, “The idea of description (reconstruction) of fingerprints with mathematical algorithms and history of the development of this idea at Optel,” (Optel, 2003), http://www.optel.pl/article/english/idea.htm, (Accessed 9 May 2006),

].

Fig.2. Simple synthesized fringe pattern. Note the dominant loop and delta structures as well as the ridge endings and bifurcations.

3. Two-dimensional demodulation

Real progress in fingerprint analysis has been impeded by the absence of a reliable and effective method for determining the offset, amplitude and phase in Eq. (1). Traditionally this task (known as demodulation) has been exceedingly difficult owing to the absence of a truly isotropic and homogeneous two-dimensional analysis technique for such patterns. The main problems of rotation and scale invariance have been solved in a recently proposed technique [8

K. G. Larkin, D. Bone, and M. A. Oldfield, “Natural demodulation of two-dimensional fringe patterns: I. General background to the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1862–1870 (2001). http://www.opticsinfobase.org/abstract.cfm?URI=josaa-18-8-1862 [CrossRef]

]. The method is known as spiral phase or vortex demodulation and effectively generalizes the Hilbert transform from 1-D to 2-D. It has been formally established [31

K. G. Larkin, “Natural demodulation of two-dimensional fringe patterns: II. Stationary phase analysis of the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1871–1881 (2001). [CrossRef]

] that the cosine term Eq. (1) can be converted to a sine (in quadrature to the cosine) by the application of a spiral phase operator. The method requires that the offset (or DC) term be first removed. We have found that a simple offset estimator based on the mid-value of a localized histogram gives good results with fingerprints. The demodulation operator $ takes the offset corrected image and applies a spiral phase Fourier multiplier exp[iϕ(u,v)]:

$ {f xy −a xy}= F −1 {exp [iϕ uv].F {b xy.cos [ψ xy]}} ≅ − iexp [iβ xy].b xy.sin [ψ xy].
(4)

Although the above formulation acts in the Fourier domain (u,v) and requires forward F , and inverse F -1, Fourier transforms, the method can also be implemented in the spatial domain using convolution. Note that the sought after quadrature term sin[ψ(x,y)] is, almost magically, expressed by the transform. But there is a catch: a directional phase multiplier -iexp[iβ(x,y)] has also appeared.

4. Orientation and direction estimation

The demodulation problem has now become one of estimating the ridge direction map for the entire image. It is important to define two closely related, but often confused, parameters: direction and orientation. We follow Jähne’s clear technical distinction [32

B. Jähne, Practical handbook on Image processing for Scientific applications (CRC Press, Boca Raton, Florida, 1997).

] in our work. Direction applies to vectors, and like the gradient in two dimensions the direction β is uniquely defined in the range 0° to 360° (modulo2π). In contrast, ridge orientation is indistinguishable from that of a 180° rotated ridge (modulo π). It is fortunate that orientation can be isotropically estimated by a 2-D mathematical operator known as the 2-D energy operator [33

K. G. Larkin, “Uniform estimation of orientation using local and nonlocal 2-D energy operators,” Optics Express 13, 8097–8121 (2005). [CrossRef] [PubMed]

]. Interestingly the robust formulation of the 2-D energy operator utilizes both first and second order spiral phases in the Fourier domain, and intrinsically outputs the orientation estimate in double-angle formalism. Knutsson’s [34

G. H. Granlund and H. Knutsson, Signal processing for computer vision (Kluwer, Dordrecht, Netherlands, 1995).

] versatile double-angle orientation vector is represented in our complex phasor approach by exp[2iβ], likewise the sought after direction vector by exp[iβ].

Previously the orientation field has been proposed as a matching feature for fingerprints by many researchers [1

D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of fingerprint recognition (Springer, New York, 2003).

, 35

V. A. Soifer, V. V. Kotlyar, S. N. Khonina, and A. G. Khramov, “The method of the directional field in the interpretation and recognition of images with structure redundancy,” Image Analysis and Signal Processing: Adv. Math. Theory Appl. 6, 710–724 (1996).

]. The direction map β(x,y) can be obtained from the orientation phase map by unwrapping. A relatively sophisticated unwrapping technique, using the topological properties of the ridge flow fields [22

B. G. Sherlock and D. M. Monro, “A model for interpreting fingerprint topology,” Pattern Recogn. 26, 1047–1055 (1993). [CrossRef]

, 36

K. G. Larkin, “Natural demodulation of 2D fringe patterns,” in Fringe´01 - The Fourth International Workshop on Automatic Processing of Fringe Patterns, Juptner W. and Osten W., eds., (Elsevier, Bremen, Germany, 2001). http://citeseer.ist.psu.edu/458598.html

] is necessary for ridge patterns containing the direction singularities known such as loops and deltas (see Fig. 2 and Fig. 3(b)).

Figure 3(a) shows the orientation phase map derived by the 2-D energy operator. Note that the colour encodes the phase and that the brightness represents the reliability of the estimate (a measure derived by the energy operator [33

K. G. Larkin, “Uniform estimation of orientation using local and nonlocal 2-D energy operators,” Optics Express 13, 8097–8121 (2005). [CrossRef] [PubMed]

]). The reliability of the orientation estimate relates to how well the local fingerprint structure corresponds to an a priori fringe model wherein noisy or feint images generally have low reliability, whereas clear, high contrast ridges have high reliability. An algorithm to resolve the inevitable direction ambiguities near loops and deltas must select branch cuts along suitable paths such as ridge contours, as shown in Fig. 3(b). After unwrapping a direction map is obtained, as shown in Fig. 3(c). The direction map is then used to isolate the desired quadrature component:

−exp [ −iβ xy].$ {f xy −a xy}=ib xy.sin [ψ xy].
(5)

The above result can be combined with the original offset-removed image to obtain the raw phase map ψ(x,y):

−exp [ −iβ xy].$ {f xy −a xy} +f xy−a xy=b xy.exp [iψ xy].
(6)
Fig. 3. Steps in the 2-D demodulation using unwrapped direction map

Demodulation thus provides an estimate of the amplitude and phase modulations from the modulus and argument of the complex function in the RHS of Eq. (6). Figure 3(d) shows the raw phase map ψ(x, y) modulo 2π.

5. Helmholtz phase decomposition

The Helmholtz Decomposition Theorem, when applied to 2-D phase, states that phase can be uniquely decomposed into two parts [17

D. C. Ghiglia and M. D. Pritt, Two-dimensional phase unwrapping (John Wiley and Sons, New York, 1998).

]. The first part, variously known as the continuous phase, irrotational, or curl-free component is well-behaved and easily unwrapped. The second part, sometimes known as the spiral phase, rotational, or divergence free component cannot be unwrapped uniquely.

Conventional 2-D phase unwrapping theory can be applied to the raw phase derived from Eq. (6). We prefer to use the classical residue detector of Bone [15

D. J. Bone, “Fourier fringe analysis: the two-dimensional phase unwrapping problem,” Appl. Opt. 30, 3627–3323 (1991). [CrossRef] [PubMed]

] to find the location and polarity of all the spiral phases in the demodulated image. Figure 4 shows the result of applying this detector to the phase in Fig. 3(d). Positive phase spirals are denoted by red, negative by blue.

Alternatively the Helmholtz decomposition theorem can be used directly to separate the phase components (see Ref. [37

Y. Tong, S. Lombey, A. N. Hirani, and M. Desbrun, “Discrete multiscale vector field decomposition,” ACM Transactions on Graphics 22, 445–452 (2003). [CrossRef]

] for an example of a discrete implementation). Subtracting all the spiral phases from the total phase leaves the continuous phase: ψ(x,y)-ψs (x,y) = ψc (x,y). With the spiral phases removed it is trivial to unwrap the continuous phase, as shown in Fig. 5(c).

Fig. 4. Minutiae polarity map

In practice we find that spiral phase pairs (dipoles) appear because of quantization and other noise so that the unwrapping has to be a little more sophisticated, but is well within the bounds of current techniques. Regrettably we do not have space here to describe further the many intricacies of spiral phase.

6. Fingerprint image synthesis

With the analysis complete it is possible to synthesize the original fingerprint f(x, y) from the four elemental sub-images in the canonical equation:

f xy≈a xy+b xy.cos [ ψC xy+ ψS xy].
(7)

Although the fingerprint image itself is a rapidly varying function, the first three elemental images, namely a, b, and ψc are all smooth functions and each can be compressed considerably with little resultant loss in fingerprint detail. Note that the smoothness constraint can be formalized mathematically so that the first and second terms, a and b , do not do all the work of capturing the variations in f(x,y). In our present implementation we have not optimized each of the four component compression algorithms, and there is plenty of scope for improvement using wavelet or other popular compression techniques. In the example presented the images a, b , and ψc were compressed using a fast Fourier transform followed by arithmetic coding of the quantized Fourier coefficients. The last image ψs is represented as a (sparse) polarity map (see Fig. 4) and is compressed directly by run length encoding of the ternary (i.e. -1, 0, +1) image.

Figure 1 shows a representative example of a digitized fingerprint image containing 512×512 pixels, with one byte per pixel (262144 bytes total uncompressed). The fingerprint is taken from the NIST database [38

NIST Image Group´s Fingerprint Research, “Fingerprint Test Data on CD-ROM,” (NIST), http://www.itl.nist.gov/iad/894.03/fing/fing.html.

]. Figure 5 shows the data storage requirements for the four elemental images a(x, y), b(x, y), ψc (x,y), and ψs (x, y).

The four elemental images above may be difficult to interpret by the non expert. Figure 5(c) containing the continuous phase term ψc looks the smoothest and most compressible; however it covers a range of about 100 radians and controls the exact fringe spacing, so it requires more dynamic range to encode adequately. Much better compression might be achieved by 2-D polynomial or spline modeling, but is left for future refinements of the technique.

Fig. 5. All four elemental images after decompression (1095 bytes total).

Figure 5(d) containing the spiral phase term ψS looks very complicated because of the (seemingly) arbitrary phase wraps of the cyclic phase, but is really quite compressible in terms of the spiral polarity map (Fig. 4).

Full synthesis from Eq. (7) is shown in Fig. 6 alongside the original for comparison. To give an idea of computational speed, the compression of the example shown took about 6 seconds on a 3 GHz desktop PC. The decompression is much simpler and an order of magnitude faster. The broad similarity of the two images is clear and most of the minutiae are captured by the compressed representation. Although most of the minutiae are captured some visible discrepancies remain, however the fidelity can be traded against the compression and demodulation parameters. In this instance the compression factor is 239 times which illustrates that extreme compression is not necessarily incompatible with effective representation. It is customary to quote a peak signal-to-noise ratio (PSNR) for image compression algorithms. A PSNR of 30dB is generally regarded as a lower limit for visual quality evaluation [5

U. Grasemann and R. Miikkulainen, “Effective image compression using evolved wavelets,” in Genetic And Evolutionary Computation Conference (GECCO-05),(ACM, Washington DC, 2005), pp. 1961–1968.

]. The example shown in Fig. 6 has PSNR of 21.6dB, which, although comparable with JPEG at a 53:1 compression ratio (see Fig. 14 in Ref. [39

S. Kasaei, M. Deriche, and B. Boashash, “A novel fingerprint image compression technique using wavelets packets and pyramid lattice vector quantization,” IEEE Transactions On Image Processing 11, 1365–1378 (2002). [CrossRef]

]), belies the interpretation of our compression as a structure preserving de-noising technique. In particular the ridge endings and bifurcations are robustly encoded as phase spirals which can be selectively maintained as the other elemental images are increasingly smoothed and compressed.

Fig. 6. Decompressed (239×) fingerprint (1095 bytes) on the left, and the original (right).

An important concern of fingerprint researchers is maintaining recognition (or matching) in the presence of print distortions (such as soft tissue deformation whilst rolling fingerprints). Our approach maps the minutiae to a spatial grid, but also maps the continuous phase to the same spatial grid. A deformation invariant representation is then available by mapping corresponding continuous phase values to the minutiae. The mapping is equivalent to the conventional process of ridge-counting between minutiae. The unwrapped continuous phase ψc (x,y), shown in Fig. 5(c), can be interpreted as an absolute ridge index. Trustworthiness of the index is, of course, dependant on identifying the correct topology in section 4. Correct categorization of the deltas is particularly important for reliable indexing, and proper encoding of topology within the continuous phase.

7. Discussion

We have shown that a modulation-based model of fingerprint images allows the image to be split into four elemental sub-images. Each highly redundant sub-image can be compressed drastically using conventional methods. The compressed phase images contain the essential matching and classification features: the phase gradient encodes the orientation and ridge frequency, whilst the spiral phases encode the minutiae. Compression factors greater than 200 times are readily attained. Direct comparisons with the compression of the FBI WSQ standard [7

C. M. Brislawn, “Fingerprints go digital,” Notices of the AMS 42, 1278–1283 (1995).

] are currently not meaningful because of the difference in fidelity, although the potential has been clearly demonstrated. Further research is needed to quantify the reconstructed image fidelity and visual quality as well as to separately optimize compression of each component. At the very least our approach has the potential to unite the currently disparate strands of fingerprint research in one consistent mathematical model. We note that the entire analysis-compression-synthesis process requires no manual intervention and can be fully automated. It seems reasonable to expect that the method has a number of immediate applications in the burgeoning area of biometric based security.

Spiral phase is a recurring theme in this work. Firstly the demodulator uses a spiral phase transform. Secondly the orientation estimator uses two spiral phase transforms. Thirdly, and finally, the phase model is made tractable by uniquely splitting phase into a smooth phase part and a spiral phase part. At a deeper level the spiral phase represents the essential rotation and scaling symmetry properties of both the operators [40

P. A. Fletcher and K. G. Larkin, –Direct embedding and detection of RST invariant Watermarks,” in IH2002, Fifth International Workshop on Information Hiding, Petitcolas F. A. P., ed., (Springer Verlag, Noordwijkerhout, The Netherlands, 2002), pp. 129–144.

] and the model itself.

Are fingerprints holograms? It has been shown that Gabor’s original definition is highly advantageous for the description of level 1 (ridge flow patterns) and level 2 (minutiae) fingerprint features. A hologram encodes the difference between two interfering wave-fronts: the reference and the object. In the case of a fingerprint these wave-fronts could be (arbitrarily) chosen to be the two phases derived from the Helmholtz decomposition. Level 1 features would then correspond with the total wave-front difference and level 2 features with the object wave-front alone.

Acknowledgments

Donald Bone and Michael Oldfield contributed to some early insights into the fingerprint demodulation process. An early version of this work was presented recently at the workshop on information optics [41

K. G. Larkin and P. A. Fletcher, “Extreme compression of fingerprint images: squeezing patterns until the spirals pop out,” in Fifth International Workshop on Information Optics (Toledo, Spain, 2006). http://scitation.aip.org/dbt/dbt.jsp?KEY=APCPCS&Volume=860&Issue=1

].

References and links

1.

D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of fingerprint recognition (Springer, New York, 2003).

2.

N. Ratha and R. Bolle, eds., Automatic Fingerprint Recognition Systems (Springer, New York, 2003).

3.

S. Chikkerur, A. N. Cartwright, and V. Govindaraju, “Fingerprint Image Enhancement using STFT Analysis,” in ICAPR, S. Singh, M. Singh, C. Apte, and P. Perner, eds., (Springer-Verlag, Bath, UK, 2005).

4.

A. K. Jain and S. Pankanti, “Automated Fingerprint Identification and Imaging Systems,” in Advances in Fingerprint Technology, H. C. Lee and R. E. Gaensslen, eds., (CRC Press, 2001).

5.

U. Grasemann and R. Miikkulainen, “Effective image compression using evolved wavelets,” in Genetic And Evolutionary Computation Conference (GECCO-05),(ACM, Washington DC, 2005), pp. 1961–1968.

6.

J. Tharna, K. Nilsson, and J. Bigun, “Orientation scanning to improve lossless compression of fingerprint images.,” in Audio and Video based Person Authentication - AVBPA03, J. Kittler and M. S. Nixon, eds. (Springer, Heidelberg, 2003), pp.343–350.

7.

C. M. Brislawn, “Fingerprints go digital,” Notices of the AMS 42, 1278–1283 (1995).

8.

K. G. Larkin, D. Bone, and M. A. Oldfield, “Natural demodulation of two-dimensional fringe patterns: I. General background to the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1862–1870 (2001). http://www.opticsinfobase.org/abstract.cfm?URI=josaa-18-8-1862 [CrossRef]

9.

F. Galton, Finger Prints (Macmillan, London, 1892). http://galton.org/books/finger-prints/index.htm

10.

J. F. Nye and M. V. Berry, “Dislocations in wave trains,” Proc. R. Soc. Lond. A. 336, 165–190 (1974). [CrossRef]

11.

A. W. Senior, R. M. Bolle, N. K. Ratha, and S. Pankanti, “Fingerprint Minutiae: A Constructive Definition,” in Workshop on biometrics, IEEE ECCV, (Copenhagen, Denmark, 2002).

12.

A. Ross, J. Shah, and A. K. Jain, “From Template to Image: reconstructing fingerprints from minutiae points,” IEEE Trans PAMI 29, 544–560 (2007). [CrossRef]

13.

R. M. Goldstein, H. A. Zebker, and C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Science 23, 713–720 (1988). [CrossRef]

14.

J. M. Huntley, “Noise-immune phase unwrapping algorithm,” Appl. Opt. 28, 3268–3270 (1989). [CrossRef] [PubMed]

15.

D. J. Bone, “Fourier fringe analysis: the two-dimensional phase unwrapping problem,” Appl. Opt. 30, 3627–3323 (1991). [CrossRef] [PubMed]

16.

D. L. Fried and J. L. Vaughn, “Branch cuts in the phase function,” Appl. Opt. 31, 2865–2882 (1992). [CrossRef] [PubMed]

17.

D. C. Ghiglia and M. D. Pritt, Two-dimensional phase unwrapping (John Wiley and Sons, New York, 1998).

18.

R. Penrose, “The topology of ridge systems,” Ann. Hum. Genet.,Lond. 42, 435–444 (1979). [CrossRef]

19.

M. Kass and A. Witkin, “Analyzing oriented patterns,” Computer vision, graphics, and image processing 37, 362–385 (1987). [CrossRef]

20.

C. F. Shu and R. C. Jain, “Direct Estimation and Error Analysis For Oriented Patterns,” CVGIP-Image Understanding 58, 383–398 (1993). [CrossRef]

21.

D. A. Egolf, I. V. Melnikov, and E. Bodenschatz, “Importance of local pattern properties in spiral defect chaos,” Phys. Rev. Lett. 80, 3228–3231 (1998). [CrossRef]

22.

B. G. Sherlock and D. M. Monro, “A model for interpreting fingerprint topology,” Pattern Recogn. 26, 1047–1055 (1993). [CrossRef]

23.

A. M. Turing, “The chemical basis of morphogenesis, reprinted from Philosophical Transactions of the Royal Society (Part B), 237, 37-72 (1953)," Bull. Math. Biol. 52, 153–197 (1990). [CrossRef] [PubMed]

24.

A. Witkin and M. Kass, “Reaction-diffusion textures,” Comput. Graphics 25, 299–308 (1991). [CrossRef]

25.

J. P. Crutchfield, ed., Is Anything Ever New? Considering Emergence, in Complexity: Metaphors, Models, and Reality, (Addison-Wesley, Redwood City, 1994). http://www.santafe.edu/research/publications/wpabstract/199403011

26.

J. Myung and M. Pitt, “Model Selection Methods,” in Amsterdam Workshop on Model Selection(Amsterdam, 2004). http://www2.fmg.uva.nl/modelselection/presentation.cfm?presenter=5

27.

D. Gabor, “Microscopy by reconstructed wave-fronts,” Pro. R. Soc. London 197, 454–487 (1949). [CrossRef]

28.

J. G. Daugman and C. J. Downing, “Demodulation, predictive coding, and spatial vision,” J. Opt. Soc. Am. A 12, 641–660 (1995). [CrossRef]

29.

D. Kosz, “New numerical methods of fingerprint recognition based on mathematical description of arrangement of dermatoglyphics and creation of minutiae,” in Biometrics in Human Service User Group Newsletter,Mintie D., ed., (1999). http://www.ct.gov/dss/cwp/view.asp?A=2349&Q=304724

30.

W. Bicz, “The idea of description (reconstruction) of fingerprints with mathematical algorithms and history of the development of this idea at Optel,” (Optel, 2003), http://www.optel.pl/article/english/idea.htm, (Accessed 9 May 2006),

31.

K. G. Larkin, “Natural demodulation of two-dimensional fringe patterns: II. Stationary phase analysis of the spiral phase quadrature transform.,” J. Opt. Soc. Am. A 18, 1871–1881 (2001). [CrossRef]

32.

B. Jähne, Practical handbook on Image processing for Scientific applications (CRC Press, Boca Raton, Florida, 1997).

33.

K. G. Larkin, “Uniform estimation of orientation using local and nonlocal 2-D energy operators,” Optics Express 13, 8097–8121 (2005). [CrossRef] [PubMed]

34.

G. H. Granlund and H. Knutsson, Signal processing for computer vision (Kluwer, Dordrecht, Netherlands, 1995).

35.

V. A. Soifer, V. V. Kotlyar, S. N. Khonina, and A. G. Khramov, “The method of the directional field in the interpretation and recognition of images with structure redundancy,” Image Analysis and Signal Processing: Adv. Math. Theory Appl. 6, 710–724 (1996).

36.

K. G. Larkin, “Natural demodulation of 2D fringe patterns,” in Fringe´01 - The Fourth International Workshop on Automatic Processing of Fringe Patterns, Juptner W. and Osten W., eds., (Elsevier, Bremen, Germany, 2001). http://citeseer.ist.psu.edu/458598.html

37.

Y. Tong, S. Lombey, A. N. Hirani, and M. Desbrun, “Discrete multiscale vector field decomposition,” ACM Transactions on Graphics 22, 445–452 (2003). [CrossRef]

38.

NIST Image Group´s Fingerprint Research, “Fingerprint Test Data on CD-ROM,” (NIST), http://www.itl.nist.gov/iad/894.03/fing/fing.html.

39.

S. Kasaei, M. Deriche, and B. Boashash, “A novel fingerprint image compression technique using wavelets packets and pyramid lattice vector quantization,” IEEE Transactions On Image Processing 11, 1365–1378 (2002). [CrossRef]

40.

P. A. Fletcher and K. G. Larkin, –Direct embedding and detection of RST invariant Watermarks,” in IH2002, Fifth International Workshop on Information Hiding, Petitcolas F. A. P., ed., (Springer Verlag, Noordwijkerhout, The Netherlands, 2002), pp. 129–144.

41.

K. G. Larkin and P. A. Fletcher, “Extreme compression of fingerprint images: squeezing patterns until the spirals pop out,” in Fifth International Workshop on Information Optics (Toledo, Spain, 2006). http://scitation.aip.org/dbt/dbt.jsp?KEY=APCPCS&Volume=860&Issue=1

OCIS Codes
(070.5010) Fourier optics and signal processing : Pattern recognition
(090.2880) Holography : Holographic interferometry
(100.2650) Image processing : Fringe analysis
(100.5070) Image processing : Phase retrieval
(110.2960) Imaging systems : Image analysis
(350.5030) Other areas of optics : Phase

ToC Category:
Fourier optics and signal processing

History
Original Manuscript: May 24, 2007
Revised Manuscript: June 22, 2007
Manuscript Accepted: June 22, 2007
Published: June 26, 2007

Virtual Issues
Vol. 2, Iss. 8 Virtual Journal for Biomedical Optics

Citation
Kieran G. Larkin and Peter A. Fletcher, "A coherent framework for fingerprint analysis: are fingerprints Holograms?," Opt. Express 15, 8667-8677 (2007)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-14-8667


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of fingerprint recognition (Springer, New York, 2003).
  2. N. Ratha and R. Bolle, eds., Automatic Fingerprint Recognition Systems (Springer, New York, 2003).
  3. S. Chikkerur, A. N. Cartwright, and V. Govindaraju, "Fingerprint image enhancement using STFT analysis," in ICAPR, S. Singh, M. Singh, C. Apte, and P. Perner, eds., (Springer-Verlag, Bath, UK, 2005).
  4. A. K. Jain and S. Pankanti, "Automated fingerprint identification and imaging systems," in Advances in Fingerprint Technology, H. C. Lee, and R. E. Gaensslen, eds., (CRC Press, 2001).
  5. U. Grasemann, and R. Miikkulainen, "Effective image compression using evolved wavelets," in Genetic and Evolutionary Computation Conference (GECCO-05),(ACM, Washington DC, 2005), pp. 1961 - 1968.
  6. J. Tharna, K. Nilsson, and J. Bigun, "Orientation scanning to improve lossless compression of fingerprint images," in Audio and Video based Person Authentication - AVBPA03, J. Kittler, and M. S. Nixon, eds., (Springer, Heidelberg, 2003), pp. 343-350.
  7. C. M. Brislawn, "Fingerprints go digital," Not. Am. Math. Soc. 42, 1278-1283 (1995).
  8. K. G. Larkin, D. Bone, and M. A. Oldfield, "Natural demodulation of two-dimensional fringe patterns: I. General background to the spiral phase quadrature transform.," J. Opt. Soc. Am. A 18, 1862-1870 (2001). http://www.opticsinfobase.org/abstract.cfm?URI=josaa-18-8-1862 [CrossRef]
  9. F. Galton, Finger Prints (Macmillan, London, 1892). http://galton.org/books/finger-prints/index.htm
  10. J. F. Nye and M. V. Berry, "Dislocations in wave trains," Proc. R. Soc. Lond. A. 336, 165-190 (1974). [CrossRef]
  11. A. W. Senior, R. M. Bolle, N. K. Ratha, and S. Pankanti, "Fingerprint Minutiae: A Constructive Definition," in Workshop on biometrics, IEEE ECCV, (Copenhagen, Denmark, 2002).
  12. A. Ross, J. Shah, and A. K. Jain, "From template to image: reconstructing fingerprints from minutiae points," IEEE Trans PAMI 29, 544-560 (2007). [CrossRef]
  13. R. M. Goldstein, H. A. Zebker, and C. L. Werner, "Satellite radar interferometry: two-dimensional phase unwrapping," Radio Science 23, 713-720 (1988). [CrossRef]
  14. J. M. Huntley, "Noise-immune phase unwrapping algorithm," Appl. Opt. 28, 3268-3270 (1989). [CrossRef] [PubMed]
  15. D. J. Bone, "Fourier fringe analysis: the two-dimensional phase unwrapping problem," Appl. Opt. 30, 3627-3632 (1991). [CrossRef] [PubMed]
  16. D. L. Fried and J. L. Vaughn, "Branch cuts in the phase function," Appl. Opt. 31, 2865-2882 (1992). [CrossRef] [PubMed]
  17. D. C. Ghiglia, and M. D. Pritt, Two-dimensional phase unwrapping (John Wiley and Sons, New York, 1998).
  18. R. Penrose, "The topology of ridge systems," Ann. Hum. Genet. 42, 435-444 (1979). [CrossRef]
  19. M. Kass and A. Witkin, "Analyzing oriented patterns," Computer vision, graphics, and image processing 37, 362-385 (1987). [CrossRef]
  20. C. F. Shu and R. C. Jain, "Direct Estimation and Error Analysis for Oriented Patterns," CVGIP-Image Understanding 58, 383-398 (1993). [CrossRef]
  21. D. A. Egolf, I. V. Melnikov, and E. Bodenschatz, "Importance of local pattern properties in spiral defect chaos," Phys. Rev. Lett. 80, 3228-3231 (1998). [CrossRef]
  22. B. G. Sherlock and D. M. Monro, "A model for interpreting fingerprint topology," Pattern Recogn. 26, 1047-1055 (1993). [CrossRef]
  23. A. M. Turing, "The chemical basis of morphogenesis, reprinted from Philosophical Transactions of the Royal Society (Part B), 237, 37-72 (1953)," Bull. Math. Biol. 52, 153-197 (1990). [CrossRef] [PubMed]
  24. A. Witkin and M. Kass, "Reaction-diffusion textures," Comput. Graphics 25, 299-308 (1991). [CrossRef]
  25. J. P. Crutchfield, ed., Is Anything Ever New? Considering Emergence, in Complexity: Metaphors, Models, and Reality, (Addison-Wesley, Redwood City, 1994). http://www.santafe.edu/research/publications/wpabstract/199403011
  26. J. Myung and M. Pitt, "Model Selection Methods," in Amsterdam Workshop on Model Selection(Amsterdam, 2004). http://www2.fmg.uva.nl/modelselection/presentation.cfm?presenter=5
  27. D. Gabor, "Microscopy by reconstructed wave-fronts," Proc. R. Soc., London 197, 454-487 (1949). [CrossRef]
  28. J. G. Daugman and C. J. Downing, "Demodulation, predictive coding, and spatial vision," J. Opt. Soc. Am. A 12, 641-660 (1995). [CrossRef]
  29. D. Kosz, "New numerical methods of fingerprint recognition based on mathematical description of arrangement of dermatoglyphics and creation of minutiae," in Biometrics in Human Service User Group Newsletter, D. Mintie, ed., (1999). http://www.ct.gov/dss/cwp/view.asp?A=2349&Q=304724
  30. W. Bicz, "The idea of description (reconstruction) of fingerprints with mathematical algorithms and history of the development of this idea at Optel," (Optel, 2003), http://www.optel.pl/article/english/idea.htm, (Accessed 9 May 2006),
  31. K. G. Larkin, "Natural demodulation of two-dimensional fringe patterns: II. Stationary phase analysis of the spiral phase quadrature transform.," J. Opt. Soc. Am. A 18, 1871-1881 (2001). [CrossRef]
  32. B. Jähne, Practical handbook on Image processing for Scientific applications (CRC Press, Boca Raton, Florida, 1997).
  33. K. G. Larkin, "Uniform estimation of orientation using local and nonlocal 2-D energy operators," Opt. Express 13, 8097 - 8121 (2005). [CrossRef] [PubMed]
  34. G. H. Granlund, and H. Knutsson, Signal processing for computer vision (Kluwer, Dordrecht, Netherlands, 1995).
  35. V. A. Soifer, V. V. Kotlyar, S. N. Khonina, and A. G. Khramov, "The method of the directional field in the interpretation and recognition of images with structure redundancy," Image Analysis and Signal Processing: Adv. Math. Theory Appl. 6, 710-724 (1996).
  36. K. G. Larkin, "Natural demodulation of 2D fringe patterns," in Fringe'01 - The Fourth International Workshop on Automatic Processing of Fringe Patterns, W. Juptner, and W. Osten, eds., (Elsevier, Bremen, Germany, 2001). http://citeseer.ist.psu.edu/458598.html
  37. Y. Tong, S. Lombey, A. N. Hirani, and M. Desbrun, "Discrete multiscale vector field decomposition," ACM Transactions on Graphics 22, 445 - 452 (2003). [CrossRef]
  38. NIST Image Group's Fingerprint Research, "Fingerprint Test Data on CD-ROM," (NIST), http://www.itl.nist.gov/iad/894.03/fing/fing.html.
  39. S. Kasaei, M. Deriche, and B. Boashash, "A novel fingerprint image compression technique using wavelets packets and pyramid lattice vector quantization," IEEE Trans. Image Process. 11, 1365-1378 (2002). [CrossRef]
  40. P. A. Fletcher and K. G. Larkin, "Direct embedding and detection of RST invariant Watermarks," in IH2002, Fifth International Workshop on Information Hiding, F. A. P. Petitcolas, ed., (Springer Verlag, Noordwijkerhout, The Netherlands, 2002), pp. 129-144.
  41. K. G. Larkin, and P. A. Fletcher, "Extreme compression of fingerprint images: squeezing patterns until the spirals pop out," in Fifth International Workshop on Information Optics (Toledo, Spain, 2006). http://scitation.aip.org/dbt/dbt.jsp?KEY=APCPCS&Volume=860&Issue=1

Cited By

 Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited