Title Goes Here Correlation Pattern Recognition

Title Goes Here Correlation Pattern Recognition December 10, 2003 Vijayakumar Bhagavatula 1 V ijayakum arBhagavatula

Outline ! ! ! ! Correlation pattern recognition Pattern recognition examples Book Demos 2 V ijayakum arBhagavatula

18-794 Pattern Recognition Theory Objective: To provide the background and techniques needed for pattern classification For advanced UG and starting graduate students Example Applications: ! ! ! ! ! ! Speech recognition Optical character recognition (OCR) Fingerprint recognition Face recognition Automatic target recognition Biomedical image analysis 3 V ijayakum arBhagavatula

Pattern Recognition Methods Input ! ! ! ! Feature Extraction C lassifier C lass Statistical methods (e.g., Bayes decision theory) Machine learning methods Artificial neural networks Correlation filters Most approaches are based in image domain whereas significant advantages exist in spatial frequency domain. 4 V ijayakum arBhagavatula

Example Feature-based Matching Orientation Estimation Orientation Field Ridge Extraction Ridge Ending Extracted Ridges Input Image Ridge Bifurcation Region of Interest Minutiae ! ! ! Features based on intuition & experience Significant preprocessing needed Sensitive to occlusions Fingerprint Locator Thinning f Minutiae Thinned Ridges Minutiae Extraction Minutiae Extraction 6 V ijayakum arBhagavatula

Correlation Pattern Recognition ! ! r(x) test pattern s(x) reference pattern 1 ! ! ! r( x) s( x) dx r( x) dx s( x) 2 2 1 dx Normalized correlation between r(x) and s(x) between -1 and 1; reaches 1 if and only if r(x) s(x). Problem: Reference patterns rarely have same appearance Solution: Find the pattern that is consistent (i.e., yields large correlation) among the observed variations. 7 V ijayakum arBhagavatula

Pattern Variability ! ! Facial appearance may change due to illumination Fingerprint image may change due to plastic deformation 8 V ijayakum arBhagavatula

Pattern Locations ! ! ! Desired Pattern can be anywhere in the input scene. Multiple patterns can appear in the scene. Pattern recognition methods must be shift-invariant. 9 V ijayakum arBhagavatula

Cross-Correlation Function c(τ ) r( x) s( x τ ) dx ! Determine the cross-correlation between the reference and test images for all possible shifts !When the target scene matches the reference image exactly, output is the autocorrelation of the reference image. ! If the input r(x) contains a shifted version s(x-x0) of the reference signal, the correlator will exhibit a peak at x x0. ! If the input does not contain the reference signal s(x), the correlator output will be low ! If the input contains multiple replicas of the reference signal, resulting cross-correlation contains multiple peaks at locations corresponding to input positions. 11 V ijayakum arBhagavatula

Cross-Correlation Via Fourier Transforms Input Scene r(x) FT R (f) IFT H (f) C orrelation Filter Filter D esign ! c(τ) C orrelation O utput R eference Im age s(x) Fourier transforms can be done digitally or optically 12 V ijayakum arBhagavatula

Optical Correlator Inverse Fourier Transform Fourier Transform To InputSLM Fourier Lens To Filter SLM Fourier Lens C C D D etector C orrelation peaks for objects Laser Beam SLM: Spatial Light Modulator CCD: Charge-Coupled Detector 13 V ijayakum arBhagavatula

Correlation Filters Test Image FFT IFFT Analyze Decision Correlation output Training Correlation Filter R ecognition Training Im ages FilterD esign M atch . N o M atch 14 V ijayakum arBhagavatula

Peak to Sidelobe Ratio (PSR) ! PSR invariant to constant illumination changes 1.Locate peak 2.M ask a sm all pixelregion PSR Peak m ean σ 3.C om pute the m ean and σ in a bigger region centered atthe peak ! Match declared when PSR is large, i.e., peak must not only be large, but sidelobes must be small. 15 V ijayakum arBhagavatula

Train on 3,7,16,- Teston 10. 16 V ijayakum arBhagavatula

U sing sam e Filter trained before, Perform cross-correlation on cropped-face show n on left. 18 V ijayakum arBhagavatula

C O R R ELA TIO N FILTER S A R E SH IFT-IN V A R IA N T C orrelation outputis shifted dow n by the sam e am ountofthe shifted face im age,PSR rem ains SA M E! 19 V ijayakum arBhagavatula

U sing SO M EO N E ELSE’S Filter, . Perform cross-correlation on cropped-face show n on left. A s expected very low PSR . 20 V ijayakum arBhagavatula

Automatic Target Recognition Example 21 V ijayakum arBhagavatula

SA IP A TR SD F C orrelation Perform ance for Extended O perating C onditions C ourtesy:N orthrop G rum m an Correlation Plane ContourM ap Correlation Plane ContourM ap M 1A 1 in the open M 1A 1 near tree line A djacenttrees cause som e correlation noise 22 Correlation Plane Surface CorrelationVPl ane Surface ij ayakum arBhagavatula

Biometric Verification Examples 24 V ijayakum arBhagavatula

Facial Expression Database ! Facial Expression Database (AMP Lab, CMU) ! 13 People ! 75 images per person ! Varying Expressions ! 64x64 pixels ! Constant illumination ! 1 filter per person made from 3 training images 25 V ijayakum arBhagavatula

PSRs for the Filter Trained on 3 Images Response to Training Im ages Response to Faces Im ages from Person A PSR M A RG IN O F SEPA RA TIO N Response to 75 face im ages ofthe other12 people 900 PSRs 26 V ijayakum arBhagavatula

PIE Database Illumination Variations ! Simulations using 65 people from the Pose, Illumination and Expression (PIE) Database. ! Each person (with and without background lighting) has 21/22 face images respectively at frontal view. 28 V ijayakum arBhagavatula

49 Faces from PIE D atabase illustrating the variations in illum ination 29 V ijayakum arBhagavatula

Training Image selection ! ! We used three face images to synthesize a correlation filter The three selected training images consisted of 3 extreme cases (dark left half face, normal face illumination, dark right half face). n 3 n 7 n 16 30 V ijayakum arBhagavatula

EER using Filter with Background illumination A uthenticate Threshold R eject 33 V ijayakum arBhagavatula

Iris Verification ! ! ! High-quality iris images yield low error rates Correlation filters yield zero verification errors for the 9 iris images Challenge is to acquire high-quality iris images Source: Dr. J. Daugman’s web site Source: National Geographic Magazine 36 V ijayakum arBhagavatula

Features of Correlation Filters ! ! ! ! Shift-invariant; no need for centering the test image Graceful degradation Can handle multiple appearances of the reference image in the test image Closed-form solutions based on well-defined metrics 37 V ijayakum arBhagavatula

Motivation for the Book ! Most pattern recognition researchers are not able to take advantage of the power of correlation filters because of the diverse background needed ! ! ! ! ! ! ! Signals and system s Probability theory and random variables Linearalgebra O pticalprocessing D igitalsignalprocessing D etection and estim ation theory Goal of the book: To provide the background and techniques for correlation pattern recognition and illustrate with applications. 48 V ijayakum arBhagavatula

Book Chapters ! ! ! ! ! ! ! ! ! Introduction Mathematical background Signals and systems Detection theory Basic correlation filters Advanced correlation filters Optics basics Optical correlators Application examples 49 V ijayakum arBhagavatula

Book Status ! Co-authors ! ! ! ! ! ! D r.A bhijitM ahalanobis,Lockheed M artin D r.Richard Juday,N A SA Johnson Space Center(Retired) All nine chapters written References and final editing being done To be published by Cambridge University Press Should come out in late 2004 50 V ijayakum arBhagavatula

18-794 Pattern Recognition Theory! Speech recognition! Optical character recognition (OCR)! Fingerprint recognition! Face recognition! Automatic target recognition! Biomedical image analysis Objective: To provide the background and techniques needed for pattern classification For advanced UG and starting graduate students Example Applications: