Yanushkevich S.N., Wang P.S.P., Gavrilova M.L., Srihari S.N. (eds.) Image Pattern Recognition. Synthesis and Analysis in Biometrics
Подождите немного. Документ загружается.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
128 Synthesis and Analysis in Biometrics
detection methods can be classified into the following three categories:
first-order differential operators, zero-crossing detection of second-order
derivatives and more complex heuristic algorithms (such as Canny
operator). As the feature lines are not uniform in all directions, all
the results extracted by first-order derivatives operators (Sobel, Prewitt,
Roberts) are not of sufficient quality. Many detailed feature lines might be
lost. Compared with first-order derivatives, the results of LoG and Canny
are much better: LoG covers all the possible features, including minor
features such as curved lines and dots; Canny connects some adjacent
feature lines, so the resulting edges are smoother. In order to keep the
continuity of feature lines and cover all the possible detail features, we
combined the results of LoG and Canny for edge detection.
After the binary edge results are obtained, the morphological thinning
algorithm is applied to get a unitary image, where the maximal width
of the edge is one pixel. By thinning edges into skeletal pixels, which is
an accurate representation of feature edges, we can also easily record the
position of those feature lines.
After the tracking process is performed for all starting points,
information on the total number of feature lines extracted, the number of
points in each feature line, and x,y coordinates of every point, is recorded
for subsequent use in mapping and rendering.
4.5.4. Topology-Based Approach for Generation and Synthesis
of New Biometric Information
Finally, one of the most challenging areas is a recently emerged problem
of generating biometric information, or so-called inverse problem in
biometrics. In order to verify the validity of algorithms being developed,
and to ensure that the methods work efficiently and with low error rates
in real-life applications, a number of biometric data can be artificially
created, resembling samples taken from live subjects. In order to perform
this procedure, a variety of methods should be used, but the idea that we
explore is based on the extraction of important topological information from
the relatively small set of samples (such as boundary, skeleton, important
features etc.), applying variety of computational geometry methods, and
then using these geometric samples to generate the adequate set of test
data.
One example of such technique can be the generation of synthetic iris
patterns for testing of the iris identification algorithms and for medical
purposes. A multiresolution technique known as reverse subdivision is used
to capture the necessary characteristics from existing irises, which are then
combined to form a new iris image. In order to improve the results, a
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 129
set of heuristics to classify iris images is developed in collaboration with
Prof. Faramarz Samavati, University of Calgary. We propose to generate
iris images as unique combinations of existing irises, and we also introduce
heuristics used to classify iris images. The flowchart of the iris synthesis
system is given in Fig. 4.17.
Input Iris Images
Polar Transform
Iris Scaling Algorithm
Multiresolution Engine
Iris Deformation
Output Iris Image
Reverse Polar
Transform
Fig. 4.17. Iris generation system flowchart.
A more detailed description of the algorithm is now provided. First,
all of the images are pre-processed in such a way that the center of the
image corresponds to the center of the pupil, which significantly reduced the
complexity of the following algorithms. Then we transform the iris into an
alternate coordinate system which unwraps the circular iris information into
columns and rows which is better suited to computer processing. Next we
remove the pupil to guarantee that we are working with the iris information
needed for the synthesis components. Finally, once an image has been
synthesized, we reinsert the pupil information and return the iris to its
natural coordinate system.
At the iris synthesis stage, we first irises are classified according to their
patterns (number of concentric rings) and their frequency characteristics.
Then low and high level details from the selected irises are combined
according to a specific algorithm (for more information, consult
[
39
]
). The
resulting set of synthetic irises is shown in Fig. 4.18.
The methodology has high potential for applications in other areas of
biometric synthesis.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
130 Synthesis and Analysis in Biometrics
Fig. 4.18. Set of synthetic irises.
4.6. Conclusions
Geometric data structures and methodology based on proximity and
topology prove to be useful for emerging field of biometric technologies. The
chapter presents a detailed overview of existing computational geometry
methods, their recently developed applications in biometrics and their
implementation, and suggests a number of new approaches for investigation
of specific biometric problems.
Acknowledgments
Author would like to thank Prof. Vlad P. Shmerko for his encouragement,
advice and expertise that he generously shared during the process of
preparation of this Chapter. Author also would like to acknowledge Prof.
Jon Rokne and Prof. Jim Parker for their valuable suggestions, support
and contributions to this Chapter. Last, but not the least, author would
like to thank all graduate students and research associates of the Biometric
Technologies Laboratory at the University of Calgary for their dedicated
work on the project and enthusiasm for research.
Bibliography
1. Wayman, J.L. (1999). Technical testing and evaluation of biometric
identification devices, in Biometrics: Personal Identification in Networked
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 131
Society (A.Jain, R.Bolle, S.Pankanti,eds), Kluwer, Dordrecht, pp. 345–352.
2. Burge, M. and Burger, W. (2000). Ear Biometrics in Computer Vision,
Intern. Conf. on Pattern Recognition Proceeding Vol.02, (Barcelona, Spain,
2000), pp. 826–831.
3. Gavrilova, M. L. (2001). Robust algorithm for finding nearest-neighbors
under L-1, L-inf and power metrics in the plane, LNCS 2073, 1, Springer-
Verlag, pp. 663–672.
4. Gavrilova, M.L. and Alsuwaiyel,M. (2001). Two Algorithms for Computing
the Euclidean Distance Transform, Intern. J. of Image ϕ Graphics,World
Scientific, 1, 4, pp. 635–646.
5. Karasick, D.L., Nackman, L.R, Rajan,V.T., Mitchell,J.B.A. (1997).
Visualization of Three-Dimensional Delaunay Meshes, Algorithmica, 19(1-
2), pp. 114–128.
6. Luchnikov, V.A., Gavrilova,M.L., Medvedev,N.N., Voloshin,V.P. (2002). The
Voronoi-Delaunay Approach for the Free Volume Analysis of a Packing of
Balls in a Cylindrical Container, J. Future Generation Computer Systems, 8,
pp. 673–679.
7. Medvedev, N.N. (2000). Voronoi-Delaunay method for non-crystalline
structures, SB Russian Academy of Science, Novosibirsk.
8. Mucke, E, Saias, I. and Zhu, B. (1996). Fast Randomized Point
Location Without Preprocessing in Two- and Three-dimensional Delaunay
Triangulations, 12th Annual Symposium on Computational Geometry,
pp. 274–283.
9. Agarwal, P., Guibas, L., Murali, T. and Vitter,J. (1997). Cylindrical
static and kinetic binary space partitions, 13th Annual Symposium on
Computational Geometry, pp. 39–48.
10. Maltoni, D., Maio, D. and Jain, A.K. (2003). Handbook of Fingerprint
Recognition, Springer-Verlag, 2003.
11. Jain, A.K., Hong, L. and Bolle, R. (1997). On-line Fingerprint Verification,
IEEE Transaction on Pattern Analysis and Machine Intelligence, 19,
(April,1997), pp. 302–314.
12. Abellanas, M., Hurtado, F. and Palop, B. (2004). Transportation networks
and Voronoi Diagrams, Proc. 1st Intern. Symposium on Voronoi Diagrams
in Science and Engineering, Tokyo, Japan.
13. Lee, D.T., Chung-Shou Liao and Wei-Bung Wang (2004). Time-Based
Voronoi Diagram, Proc.1stIntern.SymposiumonVoronoiDiagrams,Tokyo,
Japan, pp. 229–243.
14. Bebis, G., Deaconu, T. and Georiopoulous, M. (1999). Fingerprint
identification using Delaunay triangulation, ICIIS 99, Maryland, pp. 452–
459.
15. Cappelli R., Maio D. and Maltoni D., (2001). Modelling Plastic Distortion
in Fingerprint Images, ICAPR, LNCS 2013, pp. 369–376.
16. Jiang, X. and Yau, W.-Y, (2000). Fingerprint minutiae matching based on
the local and global structures. Proc. 15th Intern. Conf. Pattern Recognition
(ICPR, 2000) 2 pp. 1042-1045.
17. Kovacs-Vajna, Zs. and Miklos A. (2000). Fingerprint Verification System
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
132 Synthesis and Analysis in Biometrics
Based on Triangular Matching and Dynamic Time Warping, IEEE Trans.
on PAMI, 22, 11, pp. 1266–1276.
18. Liang, X. and Asano, T. (2006). A Linear Time Algorithm for
Binary Fingerprint Image Denoising Using Distance Transform, IEICE
TRANSACTIONS on Information and Systems, E89-D, 4, pp. 1534–1542.
19. Gavrilova, M. (2004). Computational Geometry and Biometrics: on the Path
to Convergence, Proceedings of the International Workshop on Biometric
Technologies 2004, Calgary, AB, Canada, pp. 131–138.
20. Wang, C. and Gavrilova, M. (2004). A Multi-Resolution Approach to Singular
Point Detection in Fingerprint Images, Intern. Conf. of Artificial Intelligence,
I, pp. 506–511.
21. Wang, C. and Gavrilova, M. (2005). A Novel Topology-based Matching
Algorithm for Fingerprint Recognition in the Presence of Elastic Distortions,
Intern. Conf. on Computational Science and its Applications,LNCS,
Springer-Verlag, 1, pp. 748–757.
22. Wayman, J, Jain. A, Maltoni, D. and Maio, D. (2006). Biometric Systems:
Technology, Design and Performance Evaluation, Book, Springer.
23. Yanushkevich, S. N., Stoica, A., Shmerko, V. P. and Popel, D. V. (2005).
Biometric Inverse Problems. CRC Press/Taylor & Francis Group, Boca
Raton, FL.
24. Xiao, Y. and Yan, H. (2002). Facial Feature Location with Delaunay
Triangulation/Voronoi Diagram Calculation, Conferences in Research and
Practice in Information Technology, Feng, D. D., Jin, J., Eades, P. and Yan,
H., Eds., ACS. 11 pp. 103–108.
25. Yanushkevich, S., Gavrilova, M. and Shmerko, V. (2004). Editors,
Proceedings of the International Workshop on Biometric Technologies 2004,
Special Forum on Modeling and Simulation in Biometric Technologies,
University of Calgary, Calgary, AB, Canada, 120p.
26. Tse, R, Dakowicz, M, Gold, C.M. and Kidner,D.B. (2005). Building
Reconstruction Using LIDAR Data, In Proc. 4th ISPRS Workshop on
Dynamic & Multi-dimensional GIS, pp. 156–161.
27. Cohen-Or, Daniel and Levanoni Yishay. (1996). Temporal continuity of levels
of detail in Delaunay triangulated terrain, Visualization96, IEEE. Press,
pp. 37–42.
28. Apu, R. and Gavrilova, M. (2005). Adaptive Spatial Memory Representation
for Real-Time Motion Planning, 3IA 2005 Intern. Conf. on Computer
Graphics and Artificial Intelligence, France, pp. 21 32.
29. Yamada, H. (1984). Complete Euclidean distance transformation by parallel
operation, Proc. 7th International Conference on Patter Recognition, pp. 69–
71.
30. Danielsson, P. (1980). Euclidean distance mapping, Computer Graphics and
Image Processing, 14, pp. 227–248.
31. Rosenfeld, A. and Pfalz, J.L. (1966). Sequential operations in digital picture
processing, J. of ACM, 13, pp. 471–494.
32. Okabe, A., Boots, B., Sugihara, K. and Sung Nok Chiu. (2000). Spatial
tessellations: concepts and applications of Voronoi diagrams, 2nd Ed., John
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 133
Wiley and Sons, Chichester, West Sussex, England.
33. Li, S. and Jain ,A. (2004). Handbook of Face Recognition, Springer, 2004.
34. Apu, R. and Gavrilova, M. (2006). An Efficient Swarm Neighborhood
Management for a 3D Tactical Simulator, IEEE-CS Proceedings, ISVD 2006,
Banff, AB, Canada.
35. Bhattachariya, P. and Gavrilova, M. (2006). CRYSTAL - A new density-
based fast and efficient clustering algorithm, IEEE-CS Proceedings, ISVD
2006, Banff, AB, Canada.
36. Luo, Y., Gavrilova, M. L. and Costa-Sousa, M. (2006). NPAR by Example:
line drawing facial animation from photographs, IEEE CS Proceedings of
CGIV06, Australia, August 2006 (upcoming).
37. Wang, H. and Gavrilova, M. (2006). An Efficient Algorithm for Fingerprint
matching, International Conference on Pattern Recognition, 20 - 24 August
2006, Hong Kong, IEEE-CS publishers, 2006 (upcoming).
38. Parke, F.I. (1974). A Parameterized Model for Human Faces, PhD Thesis,
University of Utah, Salt Lake City, UT, December 1974.
39. Wecker, L., Samavati, F. and Gavrilova M. (2005). Iris Synthesis: A Multi-
Resolution Approach, GRAPHITE 2005, New Zealand, pp. 121–125.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
This page intentionally left blankThis page intentionally left blank
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
PART 2
ANALYSIS IN BIOMETRICS
135
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
136
This page intentionally left blankThis page intentionally left blank
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
PART 2
BIOMETRIC VERIFICATION: STATISTICAL
MODEL
Discriminating elements and similarity
Strength of evidence
Applications
SIGNATURE RECOGNITION: COMPOSITE
MODEL
Distances between signatures
Experimental protocols
Composite classifiers
Signature synthesis
EAR RECOGNITION: FORCE FIELD MODEL
Ear topology
Force field transform
Feature extraction
FACIAL RECOGNITION: NONTENSOR-
PRODUCT WAVELET MODEL
Formal design
Filter banks
Design examples
PALMPRINT RECOGNITION: FUSED
WAVELET MODEL
Palprint images preprocessing
Wavelet-based feature extraction
Palmprint feature matching
KEYSTROKE AND MOUSE DYNAMICS
ANALYSIS
Keystroke and free text detection
Mouse analysis movement
137