4.2 MINDTCT The algorithms used in MINDTCT were inspired by the Home OfficeS^s Automatic Fingerprint Recognition System; specifically the suite of algorithms commonly referred to as "HO39."[55] The NIST software is an entirely original implementation exceeding the capabilities of HO39. It incorporates new algorithms, a modular design, dynamic allocation, and flexible parameter control, which provide a framework for supporting future enhancement and adaptation of the technology. It should be noted that the algorithms and software parameters have been designed and set to optimally process images scanned at 19.69 pixels per millimeter(ppmm) (500 pixels per inch) and quantized to 256 levels of gray. Figure 18. Minutiae detection process. Once the software is successfully installed and compiled, the program, mindtct, is available for detecting minutiae in a finger print image. This section describes each of the major steps in the minutiae detection process. It should be noted that two generations of minutiae detection have been developed prior to the public release of this software. Thus, mindtct calls second 1. Input ANSI/NIST File 2. Generate Image Maps 3. Binarize Image 4. Detect Minutiae 5. Remove False Minutiae 6. Count Neighbor Ridges 7. Assess Minutiae Quality 8. Output ANSI/NIST File generation(or Version2) routines. Version1 routines are included in the libraries for comparison, but in general, they will perform less satisfactorily. Figure18 lists the functional steps executed. The software has been designed in a modular fashion so that each of the steps listed in Figure18 is primarily executed by a single subroutine. This permits other alternative approaches to be implemented and substituted into the process, and the overall impact on performance can be evaluated. To support the many required operating parameters, a single global control structure is used to record sizes, tolerances, and thresholds. This structure, lfsparm_V2, is automatically constructed and initialized in the file src/lib/lfs/globals.c and the values of its members are defined in src/include/lfs.h. Many of the principal control parameters are discussed in this section. 4.2.1 Input ANSI/NIST File [src/lib/an2k/fmtstd.c; read_ANSI_NIST_file()] Mindtct inputs a fingerprint image and automatically detects minutiae on the fingerprint. The algorithms and parameters have been developed and set for images scanned at 19.69 ppmm and quantized to 256 levels of gray. The application reads in an ANSI/NIST formatted file and searches the file structure for a gray scale fingerprint record. Once found, the fingerprint image in this record is processed. The application is capable of processing ANSI/NIST Type-4, Type-13, and Type-14 fingerprint image records.[30] Currently, only the first grayscale fingerprint record in the ANSI/NIST file is processed, but the application could be changed to process all grayscale fingerprints in the file. 4.2.2 Generate Image Quality Maps [src/lib/lfs/maps.c; gen_image_maps()] Because the image quality of a fingerprint may vary, especially in the case of latent fingerprints, it is critical to be able to analyze the image and determine areas that are degraded and likely to cause problems. Several characteristics can be measured that are designed to convey information regarding the quality of localized regions in the image. These include determining the directional flow of ridges in the image and detecting regions of low contrast, low ridge flow, and high curvature. These last three conditions represent unstable areas in the image where minutiae detection is unreliable, and together they can be used to represent levels of quality in the image. Each of these characteristics is discussed below. 4.2.2.1DirectionMap [src/lib/lfs/dft.c; dft_dir_powers()] One of the fundamental steps in this minutiae detection process is deriving a directional ridge flow map, or direction map . The purpose of this map is to represent areas of the image with sufficient ridge structure. Well-formed and clearly visible ridges are essential to reliably detecting points of ridge ending and bifurcation. In addition, the direction map records the general orientation of the ridges as they flow across the image. To locally analyze the fingerprint, the image is divided in to a grid of blocks. All the pixels within a block are assigned the same results. Therefore, in the case of the direction map, all the pixels in a block will be assigned the same ridge flow direction. Several considerations must be made when using a block-based approach. First, it must be determined how much local information is required to reliably derive the desired characteristic. This area is referred to as the window. The characteristic measured within the window is then assigned to each pixel in the block. It is typically desirable to share data used to compute the results assigned to neighboring blocks. This way some of the image that contributed to one blockS^s results is included in the neighboring blockS^s results as well. This helps minimize the discontinuity in block values as you cross the boundary from one block to its neighbor. This S,smoothingT^ can be implemented using a system where a block is smaller than its surrounding window, and windows overlap from one block to the next. This is illustrated in Figure19. Figure 19. Adjacent blocks with overlapping windows. The large frame at the top of the figure depicts a window(in white) surrounding a smaller block(in gray). Assuming that neighboring blocks are adjacent and non-overlapping, this scenario is defined by three parameters: the window size S,L,T^the blocksizeS,MT^ and the offset of the block from the windowS^s originS,N.T^In the global control structure, lfsparms_V2, these parameters are defined as MAP_WINDOWSIZE_V2=24, MAP_BLOCKSIZE_V2=8,and MAP_WINDOWOFFSET_V2=8 respectively. As a result, the image is divided up into a grid of 8 *8 pixel blocks with each block being assigned a result from a larger surrounding 24 *24 pixel window, and the area for windows of neighboring blocks overlap by upto 2/3. The bottom row of framesin the Figure 19 illustrates how this works in practice. Designating the address of a block by its(row index,column index),the left frame shows the first block(1,1) being computed. The next frame advances to the next adjacent block to the right, block(1,2). Correspondingly, its window is shifted 8pixels, and the new block receives its results. Note that there are two copies of the image being used. Each window operates on the original imagedata, N LM N L M L=24 M=8 N=8 1,1 1,2 2,1 2,2 1,1 1,1 1,2 1,1 1,2 2,1 while block results are written to a separate output image. The third frame in the illustration depicts the window configuration for block(2,1), and the fourth frame shows its right neighbor being computed. One additional consideration must be made when using blocks. It must be determined how to handle the edges of the image. The dimensions of the image will likely not be an even multiple of blocks, and the windows surrounding blocks along the perimeter of the image may extend off the image. In this software, the image is padded by a margin of medium gray pixels(set to intensity 128). This margin is sufficiently large to contain the perimeter windows in the image. The processing of partial blocks is also accounted for at the right and bottom of the image. This blocking scheme is implemented in src/lib/lfs/block.c; block_offsets(). Given the above approach for computing block results with an overlapping window, the technique used for determining ridge flow direction in the image can be described. Foreach block in the image, the surrounding window is rotated incrementally and a Discrete Fourier Transform(DFT) analysis is conducted at each orientation. Figure20 illustrates the incremental rotation of the window. The top left box in the figure depicts a window with its rows rotated 90 o counterclockwise so that they are aligned vertically. This is considered orientationS,0T^in the software. The parameter NUM_DIRECTIONS in the global control structure, lfspars_V2, specifies the number of orientations to be analyzed in a semicircle. This parameter is set to 16, creating an increment in angle of 11.25 o between each orientation. These orientations are depicted on the circle in the figure. The bottom row in the figure illustrates the incremental rotation of the windowS^s rows at each defined orientation. Figure 20. Window rotation at incremental orientations. When determining the direction of ridge flow for a block, each of its window orientations is analyzed. With in an orientation, the pixels along each rotated row of the window are summed together, forming a vector of 24 pixel row sums. The 16 orientations produce 16 vectors of row sums. Each vector of row sums is convolved with 4 waveforms of increasing frequency. These are illustrated in Figure21. The topwave form in the figure has a single period extending across the length of the entire vector. The second waveformS^s frequency is doubled from the first; the third is doubled from the second, and so forth. Discrete values for the sine and cosine functions at the 4 different frequencies are computed for each unit along the vector. The row sums in a vector are then multiplied to their corresponding discrete sine values, and the results are E^ 1.11.25r^ 2.22.5r^ 3.33.75r^ 8.90r^ 15.168.75r^ E^ 24 24 0.0r^ 0 1 2 3 4 5 67 8 910 1112 131415 !=11.25r^ accumulated and squared. The same computation is done between the row sums in the vector and their corresponding discrete cosine values. The squared sine component is then added to the squared cosine component, producing a resonance coefficient that represents how well the vector fits the specific waveform frequency. Figure 21. DFT waveform frequencies. The spatial frequency of the top wave form in Figure21 discretely represents ridges and valleys with a width of approximately 12pixels. The second waveform represents 6pixel wide ridges and valleys. The third waveform represents 3pixel wide ridges and valleys. Finally, the fourth wave form represents 1.5 pixel wide ridges and valleys. Given an image scanned at 19.69ppmm, these waveforms cover ridges and valleys ranging in width from 0.6mm down to 0.075mm. The resonance coefficients produced from convolving each of the 16 orientationS^s row sum vectors with the 4 different discrete waveforms are stored and then analyzed. Generally, the dominant ridge flow direction for the block is determined by the orientation with maximum wave form resonance. The details are in the sourcecode. In Figure22, an original fingerprint image is shown on the left. The image on the right, is the same fingerprint image annotated with the ridge flow directions recorded in the resulting direction map. Each direction in the map is represented as a rotated line segment centered within its corresponding 8*8 pixel image block. Figure 22. Direction map results. 4.2.2.2 LowContrastMap[src/lib/lfs/block.c; low_contrast_block()] It is difficult, if not impossible, to accurately determine a dominant ridge flow in certain portions of a fingerprint image. This is true of low contrast areas that contain image back ground and smudges. It is desirable to detect these areas and prevent artificially assigning ridge flow directions where there really are no clearly defined ridges. To derive an arbitrary ridge flow strictly from the data within these areas is problematic. An image map called the low contrast map is computed where blocks of sufficiently low contrast are flagged. This map separates the background of the image from the fingerprint, and it maps out smudges and lightly-inked areas of the fingerprint. Minutiae are not detected within lowcontrast blocks in the image. One way to distinguish a lowcontrast block from a block containing well-defined ridges, is to compare their pixel intensity distributions. By definition, there is little dynamic range in pixel intensity in a lowcontrast area, so the distribution of pixel intensities will be very narrow. A block containing well-defined ridges will, on the other hand, have a considerably broader range of pixel intensities as there will be pixels ranging from very light in the middle of valleys to very dark in the middle of ridges. In order to determine if a block is low contrast, this software computes the pixel intensity distribution within the block's surrounding window. A specified percent of the distributionS^s high and low tails are trimmed, and the width of the remaining distribution is measured. If the measured width is sufficiently small, then the block is flagged in the map as having low contrast. In the global control structure, lfsparms_V2, the parameter PERCENTILE_MIN_MAX=10 causing the lowest and highest 10% of pixel intensities in the distribution to be trimmed. By trimming the tails, the subsequent width measurement is made in a much more stable portion of the distribution. The parameter MIN_CONTRAST_DELTA=5 is the pixel intensity threshold less than which indicates a low contrast block. This threshold was derived empirically from a training sample of low and high contrast blocks extracted from real fingerprint images. The image maps are actually computed in this software on a 6-bit pixel intensity image with 64 levels of gray. The threshold here of 5 actually corresponds to a threshold of 10 shades of gray in the original 8-bit pixel intensity image with 256 levels of gray. In other words, if the dynamic range of the center 80% of a blockS^s pixel intensity distribution is not larger than 10 shades of gray, it is determined to below contrast. The white crossmarks in the corner of the fingerprint image in Figure23 label blocks with sufficiently low contrast. Figure 23. Low contrast map results. 4.2.2.3 LowFlowMap[src/lib/lfs/maps.c; gen_initial_maps()] It is possible, when deriving the initial direction map, for some blocks to have no dominant ridge flow. These blocks typically correspond to low-quality areas in the image. Initially these blocks are not assigned an orientation in the direction map, but subsequently some of these blocks may be assigned an orientation by interpolating the ridge flow of neighboring blocks. The low flow map marks the blocks that could not initially be assigned a dominant ridge flow. In the event that minutiae are detected in these blocks, their assigned quality is reduced because they have been detected within a less reliable part of the image. The white crossmarks in the fingerprint image in Figure24 label blocks with no dominant ridge flow. Figure 24. Low flow map results. 4.2.2.4 HighCurveMap[src/lib/lfs/maps.c; gen_high_curve_map()] Another part of fingerprint image that is problematic when it comes to detecting minutiae reliably is in areas of high curvature. This is especially true of the core and delta regions of a fingerprint. [36] The high curve map marks blocks that are in high-curvature areas of the fingerprint. Two different measures are used. The first called, vorticity, measures the cumulative change in ridge flow direction around all the neighbors of a block. The second called, curvature, measures the largest change in direction between a blockS^s ridge flow and the ridge flow of each of its neighbors. The details are in the sourcecode. In the event that minutiae are detected in these blocks, their assigned quality is reduced because they have been detected within a less reliable part of the image. The white crossmarks in the fingerprint image in Figure25 label blocks with high-curvature ridges. Figure 25. High curve map results. 4.2.2.5QualityMap [src/lib/lfs/quality.c; gen_quality_map()] The final image map produced by this package is a quality map.As discussed, the low contrast map, low flow map, and the high curve map all point to different low quality regions of the image. The information in these maps is integrated into one general map, as shown in Figure26, and contains 5 levels of quality. The quality assigned to a specific block is determined based on its proximity to blocks flagged in these various maps. The details are in the sourcecode. Figure 26. Quality map results. 4.2.3 Binarize Image [src/lib/lfs/binar.c; binarize_V2()] The minutiae detection algorithm in this system is designed to operate on a bi-level(orbinary)image where black pixels represent ridges and white pixels represent valleys in a finger's friction skin. To create this binary image, every pixel in the grayscale input image must be analyzed to determine if it should be assigned a black or white pixel. This process is referred to as image binarization. A pixel is assigned a binary value based on the ridge flow direction associated with the block the pixel is within. If there was no detectable ridge flow for the current pixel's block, then the pixel is set to white. If there is detected ridge flow, then the pixel intensities surrounding the current pixel are analyzed within a rotated grid as illustrated in Figure27. Figure 27. Rotated grid used to binarize the fingerprint image. This grid is defined in the global control structure, lfsparms_V2, with column width( DIRBIN_GRID_W) set to 7 pixels and row height( DIRBIN_GRID_H) set to 9 pixels. With the pixel of interest in the center, the grid is rotated so that its rows are parallel to the local ridge flow direction. Gray scale pixel intensities are accumulated along each rotated row in the grid, forming a vector of row sums. The binary value to be assigned to the center pixel is determined by multiplying the center row sum by the number of rows in the grid and comparing this value to the accumulated grayscale intensities within the entire grid. If the multiplied center row sum is less than the grid's total intensity, then the center pixel is set to black; otherwise, it is set to white. Figure 28. Binarization results. RidgeFlowDirectionC The results of binarization are shown in the Figure28. The original grayscale image is on the left, and its binarization results are on the right. It should be noted that the binarization step is critical to the successful detection of minutiae in this approach. The binarization results need to be robust in terms of effectively dealing with varying degrees of image quality and reliable in terms of rendering ridge and valley structures accurately. These are challenging, and at times conflicting goals. It is desirable to preserve as much image information and ridge/valley structure as possible so that minutiae are not missed, and yet it is undesirable to accentuate degraded areas in the image to the point of introducing false minutiae. Significant effort has been invested to promote both robust and reliable binary images, and yet the current system tends to produce a considerable number of false minutiae. This is particularly troublesome when processing latent fingerprint images. 4.2.4 Detect Minutiae [src/lib/lfs/minutia.c; detect_minutiae_V2()] This step methodically scans the binary image of a fingerprint, identifying localized pixel patterns that indicate the ending or splitting of a ridge. The patterns searched for are very compact as illustrated in Figure29. The left-most pattern contains six binary pixels in a 2*3 configuration. This pattern may represent the end of a black ridge protruding into the pattern from the right. The same is true for the next 2*4 pattern. The only difference between this pattern and the first one is that the middle pixel pair is repeated. In fact, this is true for all the patterns depicted. This "family" of ridge ending pattern scan be represented by the right-most pattern, where the middle pair of pixels(signified by S, *T^)may repeat one or more times. Figure 29. Pixel pattern used to detect ridge endings. Candidate ridge endings are detected in the binary image by scanningconsecutivepairsofpixelsintheimagelookingfor sequencesthatmatchthispattern.Patternscanningisconducted both verticallyandhorizontally. Thepatternasillustratedisconfiguredforvertical scanningasthepixelpairsarestackedontopofeachother.To conductthehorizontalscan,thepixelpairsare unstacked, rotated90oclockwise,andplacedbackinsequencelefttoright. Usingtherepresentationabove,aseriesofminutiaepatternsare usedtodetectcandidateminutiapointsinthebinary fingerprintimage.Thesepatternsare illustratedinFigure30.Therearetwo patternsrepresentingcandidateridgeendings,therest representvariousridgebifurcations.Asecondaryattributeof appearing/disappearingisassignedtoeachpattern.This designatesthe directionfromwhicharidgeorvalleyis protrudingintothepattern.Allpixelpairsequencesmatching thesepatterns,astheimageisscannedbothvertically andhorizontally,formalistof candidateminutiapoints. * 2*3 2*4 2*5 ... 2*N Pattern Figure 30. Pixel patterns used to detect minutiae. 4.2.5 Remove False Minutiae [src/lib/lfs/remove.c; remove_false_minutia_V2()] UsingthepatternsinFigure30,candidateminutiaepointsare detectedwithasfewassixpixels.Thisfacilitatesa particularlygreedydetectionscheme thatminimizesthechanceofmissingtrue minutiae;however,manyfalseminutiaeareincludedinthe candidatelist.Becauseofthis,mucheffortisspentonremoving thefalseminutiae.Thesestepsincluderemovingislands,lakes, holes,minutiaeinregionsofpoorimagequality,sideminutiae, hooks,overlaps,minutiaethataretoowide,andminutiaethatare toonarrow(pores).Ashortdescriptionofeachofthesesteps isprovidedintheorderinwhichtheyareexecuted. 4.2.5.1 RemoveIslandsandLakes[src/lib/lfs/remove.c; remove_islands_and_lakes()] Figure 31. Removal of islands and lakes. Inthisstep,ridgeendingfragmentsandspurious inkmarks(islands)alongwithinteriorvoidsinridges(lakes)are identifiedandremoved.Thesefeaturesaresomewhatlargerthan thesizeof poresinthefrictionskinandtheyareoften ellipticalinshape;therefore,theytypicallywillhaveapairof candidateminutiapointsdetectedatoppositeends. Anillustratrionofthesetypesof featuresisshowninFigure31. ** * * * * * * * * 1.RidgeEnding(appearing) 4.Bifurcation(appearing) 2.RidgeEnding(disappearing) 3.Bifurcation(disappearing) 5.Bifurcation(disappearing) 6.Bifurcation(disappearing) 7.Bifurcation(appearing) 8.Bifurcation(appearing) 9.Bifurcation(disappearing) 10.Bifurcation(appearing) ISLAND BA LAKE A B 1. If(distance(A,B)!=16pixels)Then2. If(direction.angle(A,B)?=123.75o)Then 3. If(on.loop(A)&&on.loop(B))Then4. If(loop.length!=60pixels)Then 5.remove(A,B)6.fill.loop() Includedatthebottomofthefigurearethecriteriausedtodetect islandsandlakes.Apairofminutiamustbewithin16pixels( MAX_RMTEST_DIST_V2)ofeachother.Ifso,thenthedirectionsof thetwominutiaemustbenearlyopposite( >= 123.75o)eachother.Next,bothminutiaemustlieontheedgeof thesameloop,andtheperimeteroftheloopmustbe <=60pixels (MAX_HALF_LOOP_V2 * 2).Ifallthesecriteriaaretrue,thenthe pairofcandidateminutiaeareremovedforthelistandthebinary imageisalteredsothattheisland/lakeisfilled.Notethatthis istheonlyremovalstepthatmodifiesthebinaryfingerprintimage. 4.2.5.2RemoveHoles [src/lib/lfs/remove.c; remove_holes()] Figure 32. Removal of holes. Hereaholeisdefinedsimilarlytoanislandorlake,onlysmaller, andtheloopneedonlyhaveone minutia point on it. The criteria for removing a hole are illustrated in Figure 32. If a candidateminutiapointliesontheedgeofaloopwithperimeterlength <=15pixels( SMALL_LOOP_LEN),thenthepointisremovedfromthecandidatelist. 4.2.5.3 RemovePointingtoInvalidBlock [src/lib/lfs/remove.c; remove_pointing_invblock_V2()] Thisstepandthenextidentifyandremovecandidateminutiaethat arelocatednearblocksthatcontainnodetectableridge flow.Theseblocksarereferredtoascontaining invalidridgeflow directionandrepresentlow-qualityareasinthefingerprintimage. Figure 33. Removal of minutia pointing to an invalid block. HOLE A 1. If(on.loop(A))Then2. If(loop.length!=15pixels)Then 3.remove(A) 1. B=translate(A,4pixels,direction(A)) 2.D=direction(block(B)) 3. If(D==Invalid)Then4.remove(A) CurrentBlock NeighborBlock A B Direction = 7 Direction = Invalid ThisstepisillustratedinFigure33.Aminutiapoint istranslated4pixels( TRANS_DIR_PIX_V2)inthedirectiontheminutiaispointing.If thetranslatedpointlieswithinablockwithinvalidridgeflow direction,thentheoriginalminutiapointisremovefromthelist. 4.2.5.4 RemoveNearInvalidBlocks [src/lib/lfs/remove.c; remove_near_invblocks_V2()] Figure 34. Removal of minutia near invalid blocks. Here,theproximityofacandidateminutiatoanumberof surroundingblockswithinvalidridgeflowdirectionis evaluated.Givenaminutiapoint,theblockssufficientlyclose totheminutia (detailslefttothesourcecode ),andimmediately neighboringtheblockinwhichtheminutiaresides,aretestedin turn.Ifoneoftheseneighboringblockshasinvalid ridgeflowdirection, thenitssurrounding8neighborsare tested.Thenumberofsurroundingblockswithvalid ridgeflowdirectionarecounted,andifthenumberofvalidblocksis!7( RM_VALID_NBR_MIN),thentheoriginalminutiapoint isremovedfromthecandidatelist.Figure34illustratedthisstep. 1.Nbrs=block.neighbors(A) 2. InvNbrs=invalid.directions(Nbrs) 3. ForeachNiinInvNbrs4.Ni.Nbrs=neighbors(Ni) 5.Ci=count.valid.directions(Ni.Nbrs) 6. If(Ci!7)Then 7.remove(A) CurrentBlock NeighborBlock 1 NeighborBlock 2 NeighborBlock 3 Direction = 9 Direction = 9 Direction =Invalid A NeighborBlock 2 4.2.5.5 RemoveorAdjustSideMinutiae [src/lib/lfs/remove.c; remove_or_adjust_side_minutiae_V2()] Figure 35. Removal or adjustment of minutiae on the side of a ridge or valley. Thisstepaccomplishestwopurposes.Thefirstistofine-tunethe positionofaminutiapointsothatitismoresymmetricallyplaced onaridgeorvalleyending.Intheprocess,itmaybe determined thatthereisnoclearsymmetricalshapetothecontouronwhich thecandidateminutialies.Thisisoftenthecasewithpoints detectedalongthe sideofaridgeorvalleyinstead oftheridgeor valley'sending.Inthiscase,themisplacedminutiapointis removed.InFigure35,theillustration ontheleftdepictstheadjustmentofaminutiapointfrompointA 1toA2.Theillustrationontherightdepictstheremovalofasidepoint,B. Toaccomplishthis,startingatthecandidateminutiapoint, theedgeofeithertheridgeorvalleyis tracedtotherightandtotheleft7pixels( SIDE_HALF_CONTOUR),producingalistof 15contourpoints.Thecoordinatesofthesecontour pointsarerotatedsothatthedirectionofthe candidate minutia is pointing vertical. The rotated coordinates are then analyzed to determinethenumberand sequenceofrelativemaximaandminimaintherotatedy-coordinates. Ifthereis onlyoney-coordinateminima,thenthepointofthe minimumisassumedtolieatthebottomofabowl-shape drotatedcontour,andthecandidateminutiaismovedtocorrespond tothisposition intheoriginalimage.Iftherearemore thanoney-coordinateminima,thenaspecificsequence ofminima-maxima-minimamustexist,inwhichcasethecandidate minutiaismovedtothepoint intheoriginalimagecorresponding tothelowesty-coordinateminima.Again,thisisassumedtobethe bottomofarelativelybowl-shapedrotatedcontour.Ifthereis morethanoney- coordinateminimaandthereisnotanexact minima-maxima-minimasequencealongtherotatedcontour,then theminutiapointisdeterminedtoliealongthesideofaridgeor valley,anditis removedfromthecandidatelist. 1. Pts=trace.contours(A,7pixels) 2. R.Pts=rotate.points.vertical(Pts,direction(A)) 3.-Min.Ys,Max.Ys""=min.and.max.Ys(R.Pts) 4. If(#Min.Ys==1)Then Adjust(A,Pts[Min.Y1]) 5. ElseIf(-Min.Ys,Max.Ys""== -Min.Y1,Max.Y1,Min.Y2"")ThenMin.Y=point.at.min.Y(R.Pts,Min.Ys) Adjust(A,Pts[Min.Y]) 6.Elserevove(A) Removed B Adjusted A1A 2 4.2.5.6RemoveHooks [src/lib/lfs/remove.c; remove_hooks()] Figure 36. Removal of hooks. Ahookisaspikeorspurthatprotrudesoffthesideofaridgeor valley.AnexampleisillustratedinFigure36.Thisfeature typicallyhastwominutiaeofoppositetype,oneonasmall pieceofridgeandtheotherinasmallvalley,thatarerelatively closetoeachother.Thetwopointsmustbewithin16pixels( MAX_RMTEST_DIST_V2)ofeachother,theirdirectionsmustbe nearlyopposite( >= 123.75o),theymustbeofoppositetype,and theymustlieonthesameridge/valleyedgewithin30contourpixels( MAX_HOOK_LEN_V2)fromeachother.Ifallthesearetrue,thenthe twominutiapointsareremovedfromthecandidatelist. 4.2.5.7RemoveOverlaps [src/lib/lfs/remove.c; remove_overlaps()] Inthisstep,anoverlapisadiscontinuityinaridgeorvalley. Theseartifactsaretypicallyintroducedbythefingerprint impressionprocess.Abreakinaridgecauses2falseridgeendings tobedetected,whileabreakinavalleycauses2false bifurcations.Thecriteriafordetectinganoverlapare illustratedinFigure37.Twominutiapointsmustbe within8pixels (MAX_OVERLAP_DIST)ofeachother, andtheirdirectionsmustbenearlyopposite( >= 123.75o).If so,thenthedirectionofthelinejoiningthetwominutiapointsis calculated.Ifthedifference betweenthedirectionoffirst minutiaandthejoininglineis( <= 90o),thenthetwominutiaea reremovedfromthecadidatelist.Otherwise,iftheminutiaeare within6pixels (MAX_OVERLAP_JOIN_DIST)ofeachother,and therearenopixelvaluetransitionsalongthejoining line,thenthepointsareremovedfromthecandidatelist. 1. If(distance(A,B)!=16pixels)Then 2. If(direction.angle(A,B)?=123.75o)Then 3. If(type(A)!=type(B))Then 4. Pts=trace.contours(A,30pixels) 5. If(in.points(Pts,B))Then6.remove(A,B) HOOK B A Figure 37. Removal of overlaps. 4.2.5.8 RemoveTooWideMinutiae[src/lib/lfs/remove.c; remove_malformations()] Thenexttwostepsidentifyfalseminutiaethatlieonmalformed ridgeandvalleystructures.Ageneralizedridgeending iscomprisedofaY-shapedvalleyenvelopingablackrod.Theinverse istrueforageneralizedbifurcation.Simpletestsareapplied toevaluatethequalityofthisY-shape. Figure 38. Removal of too wide minutiae. Thisstepevaluateswhetherthestructureenvelopingaridgeor valleyendingisrelativelyY-shapedandnottoowide. Figure38illustratesthecriteriaapplied.Theedgeoftheridgeor valleyistracedtotheleftandtothe right20pixels( MALFORMATION_STEPS_2),producing2 1. If(distance(A,B)!=8pixels)Then 2. If(direction.angle(A,B)?=123.75o)Then 3. If(type(A)==type(B))Then 4. J=join.direction(A,B) 5.If(direction.angle(180 o-A,J)!=90oThen 6.remove(A,B) 7. ElseIf(distance(A,B)!=6pixels&&free.path(A,B))Then 8.remove(A,B) OVERLAP A B 1. Pts1=trace.contour(A,20pixels) 2. Pts2=trace.contour(A,-20pixels) 3. B=Pts1[10];C=Pts1[20] 4. E=Pts2[10];F=Pts2[20] 5.D10=distance(B,E) 6.D20=distance(C,F) 7. If((D20/D10)?2.0)Then 8.remove(A) TOO WIDE? A D10 D20 B C E F listsofcontourpoints.Oneachcontour,coordinatesatpixel index10( B&E)andatpixelindex20( C&F)arestored. Thedistancebetweenpixelsatindex10( MALFORMATION_STEPS_1)iscomputedasisthedistance betweenpixelsatindex20.Theratioofthesetwodistancesisthen calculated(D20/D10),andiftheratioislarger than2.0( MIN_MALFORMATION_RATIO),thentheminutiapointis removedfromthecandidatelist.Itshouldbenotedthatbasedon thesecriteria thebifurcationintheillustrationwouldnotberemoved. 4.2.5.9 RemoveTooNarrowMinutiae[src/lib/lfs/remove.c; remove_pores_V2()] Figure 39. Removal of too narrow minutiae. Theprevioussteptestsforcandidateminutiaethataretoowide. Thissteptestsforpointsthatareonstructuresthataretoonarrow. Thisistypical,forexample,ofporesinthefrictionskin. Figure39illustratesthistest.Startingwiththe candidateminutiapoint, F,itscoordinatesaretranslated3pixels( PORES_TRANS_R)oppositetheminutia'sdirection.Thetopedge andbottomedgesoftheenvelopingstructurearethen locatedat( Q&P).Fromthesetwopoints,theedgeis tracedtotheleft10pixels( PORES_STEP_FWD) and to the right 8 pixels (PORES_STEP_BWD).Thepointsattheendof the10pixelcontoursarestored( A&B),andthepointsattheendof the 8-pixelcontoursarestored( C&D).Next,distances arecomputedbetweenthesepairsofpoints, 1. T=180o-direction(F) 2. R=translate(F,3pixels,T) 3. Q=find.edge(R,Up,12pixels) 4. P=find.edge(R,Down,12pixels) 5. Pts=trace.contour(Q,10pixels) 6. A=Pts[10] 7. Pts=trace.contour(Q,-8pixels) 8.C=Pts[8] 9. Pts=trace.contour(P,10pixels) 10. B=Pts[10] 11. Pts=trace.contour(P,-8pixels) 12.D=Pts[8] 13. D1=distance(A,B) 14. D2=distance(C,D) 15. If((D1/D2)!=2.25)Then 16.remove(F) TOO NARROW? FD1 10 A B C D R Q P10 8 8 D2 andtheratio( D1/D2)iscomputed.Iftheratio is <=2.25(PORES_MAX_RATIO),thentheminutiapointisremoved fromthecandidatelist.Infact,iftheprocessfailstofindanyof thepointsin theillustration,thenthecandidateminutiais removed.Itshouldbenotedthat, mindtct,onlysearchesfor minutiaethataretoonarrowwithin high-curvatureregionsorregionswhereridge flowdirectionis non-determinable. 4.2.6 Count Neighbor Ridges [src/lib/lfs/ridges.c; count_minutiae_ridges()] Fingerprint minutiae matchers often use information in addition to just the points themselves.Ancillary informationusuallyincludestheminutia'sdirection,itstype,anditmayinclude informationpertainingtominutiaeneighbors.Beyondaminutia's position,direction,andtype,therearenostandardneighbor schemes.DifferentAFISsystemsusedifferentneighbor topologiesandattributes.Onecommonattributeisthenumberof interveningridges(calledridgecrossings)betweenaminutia andeachofitsneighbors.Forexample,theFBI'sIAFISuses ridgecrossingsbetweenaminutiaandits8nearest neighbors,whereeachneighboristhe closestwithinaspecifiedoctant.[37] Theneighborschemedistributedwiththissystemhas beendirectlyinheritedfromHO39.[55]Upto5nearestneighbors( MAX_NBRS)arereported.Givenaminutiapoint,theclosest neighborsbelow(inthesamepixelcolumn), andtotheright(withinentirepixelcolumns)inthe imageareselected.Thesenearestneighborsaresortedinorderof theirdirection,startingwithverticalandworkingclockwise. Usingthistopology,ridgecountsarecomputedandrecorded betweenaminutiapointandeachofitsnearestneighbors. 4.2.7 Assess Minutia Quality [src/lib/lfs/quality.c; combined_minutia_quality()] Oneof the goalsofdevelopingthissoftwarepackagewasto computeaquality/reliabilitytobeassociatedwith eachdetectedminutiapoint.Evenwiththelengthylistofremovalstepsabove, falseminutiaepotentiallyremaininthecandidatelist.Arobust qualitymeasurecanhelpmanagethisinthatfalseminutiaeshould beassignedalowerqualitythantrueminutiae. Throughdynamic thresholding,atradeoffbetweenretainingfalseminutiaeand throwingawaytrueminutiaemaybedetermined.Tothisend, mindtct,computesandreportsminutiaequalities. Twofactorsarecombinedtoproduceaqualitymeasureforeach detectedminutiapoint.Thefirstfactor, L,istakendirectly fromthelocationoftheminutiapointwithinthequalitymap described in Section 4.2.2.5. One of five quality levels is initially assigned, with 4 being thehighestqualityand0beingthelowest. Thesecondfactorisbasedonsimplepixelintensity statistics(meanandstandarddeviation)withintheimmediate neighborhoodoftheminutiapoint.Thesizeoftheneighborhood issetto 11pixels( RADIUS_MM).Thisissufficientlylargeto containgenerousportionsofanaverageridgeandvalley.Ahigh qualityregionwithinafingerprintimagewillhavesignificant contrast thatwillcoverthefullgrayscalespectrum. Consequently,themeanpixelintensityofthe neighborhoodwillbeverycloseto127.Forsimilarreasons, thepixelintensitiesofanideal neighborhoodwillhaveastandarddeviation>=64. Usingthislogic,thefollowingreliabilitymeasure, R,iscalculatedgivenneighborhoodmean, u,andstandarddeviation,ffi: ( )ffiu ffi u ffi ffi u FFR otherwise ifF F ,min 64 640.1 127 1270.1 = \Delta \Theta \Delta \Lambda \Xi >= --= Minutiaquality,Q,iscalculatedusingqualitymaplevel,L,andreliability,R,as: \Delta \Delta \Delta \Theta \Delta \Delta \Delta \Lambda \Xi = =*+ =*+ =*+ =*+ = 001. 1)04(.05. 2)14(.10. 3)24(.25. 4)49(.50. Lif LifR LifR LifR LifR Q Thisresultsinaqualityvalueontherange.01to.99.Alowquality valuerepresentsaminutiadetectedinalowerqualityregionof theimage,whereasahighqualityvaluerepresentsaminutia detectedinahigherqualityregion. 4.2.8 Output ANSI/NIST file [src/lib/an2k/fmtstd.c; write_ANSI_NIST_file()] Uponcompletion, mindtct,takesthecontentsoftheinput ANSI/NISTformattedfileandinsertstwonewrecords. AType-9record,holdingthedetectedminutiae,isconstructedand insertedalongwithaType-13orType-14record,holdingtheimage binarizationresults.Iftheinputimageisofalatent fingerprint,thenthebinarizationresultsarestoredina Type-13record; otherwise,theimageresultsarestoredina Type-14record.ItshouldbenotedthattheminutiaeintheType-9 recordareformattedintheNIST-assignedfields5-12according totheANSI/NIST standard.[30]Theutilities, an2k2iafand iaf2an2k,asdescribedintheReferenceManualofthisdocument maybeusedtoconvertbetweenthesefieldsand theFBI/IAFIS-assignedfields 13-23.[37] Anumber ofotherfilesareproducedinadditiontothe outputANSI/NISTfile.Theseincludeafileforeachof theimagemapsdescribedin Section4.2.2andalogfilelistingallthedetected minutiaeandtheirassociatedattributes.Alloftheseare textfilesandarecreatedby mindtctinthecurrent workingdirectorywithfixedfilenames.Thedirectionmapisstoredin dmap.txt;thelowcontrastmapisstoredin lcmap.txt;thelowflowmapisstoredin lfmap.txt;thehighcurvemapisstoredin hcmap.txt;andthequalitymapisstoredin qmap.txt.Themapsarerepresentedbyagridofnumbers,eachcorrespondingtoablockinthefingerprintimage. Thelasttextoutputfile, min.txt,containsaformattedlisting ofattributesassociatedwitheachdetectedminutiaeinthe fingerprintimage.Amongtheseattributesaretheminutia's pixel coordinatelocation,itsdirection,andtype. Theformatandalltheattributesreportedinthisfilearedescribedwithinthe mindtctmanualpageintheReferenceManual.Outputfiles generatedfrom mindtctareprovidedin test/mindtct/execs/mindtct. Figure40displaysthedetectedminutiaefortheexamplefingerprint. Figure 40. Minutiae results.