UPDATES ON CLPEX.com

No major updates on the website this week.

_________________________________________
 

we continued a series on U.S. patents related to latent print examination.

we continue this series with a patent involving level 3 detail use by AFIS systems.

_________________________________________
Level III+ use in AFIS systems
Authored by Kasey Wertheim and Jeff Walajtys
Granted October 3, 2006: Patent No. 7,116,806

When specific grayscale or other magnitudes in a fingerprint image are connected, the resulting pathway conforms to specific level III edge and pore ridge features. Using multiple grayscale or other magnitude pathways enhances the recognition and extraction of more, and sometimes substantially all, the level III features in an impression, thereby increasing the likelihood of an AFIS hit.

By connecting pixels which possess the same grayscale or other magnitude, a pathway or contour is formed. This pathway conforms to unique ridge shapes that are present along the edges, pores, and surface morphology of a friction ridge impression. The charted course and, generally, changes in the charted course of the pathway on the x-y axis can be used to recognize and extract level III features.

When a different grayscale value (or other value for the measured magnitude) is chosen, the pathway or contour takes on a new course. Changes in the charted new course will not be the same as changes in any other pathway course. In short, as the magnitudes used to chart the pathway change, the shape, location, prominence, and presence of features along that pathway also changes. If multiple magnitude pathways (multiple pathways within a given measurement indicator, such as grayscale, and/or multiple pathways within or between different magnitude indicators such as grayscale and hue and saturation) are used in an AFIS III+ environment, many, and possibly substantially all, features present in an impression may be
recognized.

Level II AFIS (AFIS II) models mainly take into account major friction ridge path deviations in an impression. These include bifurcations 48 and ridge endings 50, as demonstrated in FIGS. 12a c. FIG. 12a (left) depicts an image of a known impression, FIG. 12b (center) shows an AFIS II system reading ridge paths and major ridge path deviations, then in FIG. 12c (right) recognizing and extracting level II detail with directionality and relationship.

Level III AFIS (AFIS III) additionally takes into account features along the edge of a minor deviation such as a ridge positions 52, 54 and pore positions 56 along the center of a ridge, if available in the impression of the print. FIG. 13a (left) depicts an image of a known impression, FIG. 13b (center) shows an AFIS II system reading ridge paths and major ridge path deviations, then in FIG. 13c (right) recognizing and extracting level II detail with directionality and relationship.

AFIS III+ takes into account this detail and more, at multiple levels or slices of an impression, as
shown in FIG. 14. These slices are defined by the grayscale values that are used to chart the course of
contours or pathways within the slice. Thus, FIG. 14, AFIS III+, utilizes slices comprising multiple
image pathways which conform differently to level III features at different grayscale (or other)
magnitudes.

As shown in FIGS. 15a c and FIGS. 16a c, these AFIS III+ pathways can be isolated and examined
individually to demonstrate the uniqueness of the friction ridge that created the impression. FIGS. 15a c
depict an AFIS III+ analysis the same images as FIGS. 12a c at different grayscale magnitudes; FIGS. 16a
c depict an AFIS III+ analysis the same images but at a different grayscale magnitude from the analysis
in FIGS. 15a c. By examining the course of the pathway and specifically, changes in the course of a
pathway, unique features of that course can be recognized in the different slices (FIGS. 15b and 16b). By
assigning value to changes in the course of a pathway, those unique features can be extracted and used
for searching (FIGS. 15c and 16c). Thus, in FIGS. 15a and 16a, differing individual pathways are seen. In
FIGS. 15b and 16b, features in the filled pathways (or slice) are recognized. In FIGS. 15c and 16c, only
the marked features are shown (relationship, directionality, and prominence can be associated with each
feature).

Thus, if the pathway or level in the print is charted according to a different grayscale or other
magnitude, the position, location, prominence, and presence of features along the pathway changes.

By charting pathways based on a comprehensive set of grayscale values in an image, very large amounts the
detail present can be recognized, extracted, and used in the comparison and identification of a
fingerprint image. AFIS III+ results in a much more accurate and complete latent print feature-based
profile, but that profile can require significantly more processing time and power to search. This is
because the resulting feature set would contain many times more data than traditional level 2 AFIS
systems capture. Further, this increased amount of data would be present on each slice of each image
compared, and each slice would be compared with the multiple slices of known database images, as shown in FIG. 17.

Thus, in some embodiments only selected slices are used, or programs can be provided to compress data or
otherwise facilitate data storage, management, processing, analysis, etc.

Turning to a more general discussion of this aspect of the innovations herein, one feature involves the
use of multiple slices of a single image in an AFIS environment. Another aspect comprises the use of
pathways defined by grayscale or other magnitudes within an image of a friction ridge impression. Once
the pathways in each slice are determined, any extraction or matching algorithm may be used to gather and
compare the data. Additional aspects comprise defining the features for recognition.

There are typically four types of level III features involving directional changes of grayscale magnitude
pathways which can be present and quantified in an AFIS III+ environment. 1) EC: point of maximum offset
on a concave edge feature 2) EV: point of maximum offset on a convex edge feature 3) MC: center of mass
of a concave morphological feature 4) MV: center of mass of a convex morphological feature

A morphological feature is a feature in which a contour line or pathway forms a circuit around a level
III feature. FIG. 18 shows examples of a concave morphological feature that may include a sweat pore, a
depression in the top of a ridge or other morphological feature where detail is a lighter grayscale shade
than the surrounding dark pixels. Examples of a convex morphological feature include an incipient ridge
or a bump on a friction ridge where detail shows up as a darker grayscale shade than the surrounding
light detail. In these Figures, the concave morphological features are of a lighter grayscale value, and
the convex morphological features are of a darker grayscale value than surrounding detail.

As shown FIG. 19, edge features are features along the pathway proceeding down the edge of a friction
ridge, represented by changes in direction of the pathway. Examples of a concave edge feature include an
inlet of light (furrow) detail into a friction ridge or a sweat pore that is not quite closed in on one
edge. Examples of a convex edge feature include a bump on the side of a ridge or a section of a ridge
that protrudes into the furrow. In FIG. 19, the purple features are examples of concave edge features,
and the green features are examples of convex edge features.

Recognition:

Through simple algebra or otherwise as desired, the location and direction of each feature can be
determined and plotted in relation to the center of the pattern and other features on the x-y axis.

In the case of morphological features, center of mass and feature area can be calculated, and
directionality can be assigned based on pixel grayscale magnitude relative to surrounding values. For
example, convex features would receive a "+" value and convex features would receive a "-" value. Noise
can be reduced by analysis of the prominence of the feature throughout multiple slices (subtle changes
can be disregarded, or a threshold tolerance can be set). Noise can also be reduced by analysis of the
percentage change of grayscale pixel magnitude in surrounding pixels (sharp changes would represent
artificial features that are not friction ridge skin features).

For edge features, the point on a pathway that is furthest from the average path can be calculated, and
directionality can be assigned based on pixel grayscale magnitude relative to the value on either side of
the pathway. Convex features would receive a "+" value and concave features would receive a "-" value.
Noise can be reduced by analysis of the deviation of the point from the average pathway (subtle changes
can be disregarded, or a threshold of tolerance can be set). Noise can also be reduced by analysis of the
frequency of features along a pathway (frequent features would represent artificial features that are not
friction ridge skin features).

Turning to some general issues, the development of the innovations herein have the potential to
significantly increase the accuracy of automated fingerprint identification systems, and/or increase the
identification of more foreign and domestic criminals, thereby contributing to the advancement of law
enforcement, criminal justice systems and homeland security efforts.

Virtually any dimension, or weighted combination of dimensions in an at least 2D digital image (e.g., a
direct digital image, a scanned photograph, a screen capture from a video or other moving image) can be
represented as at least a 3D surface map (i.e., the dimension or intensity of a pixel (or magnitude as
determined by some other mathematical representation or correlation of a pixel, such as an average of a
pixel's intensity and its surrounding pixel's intensities, or an average of just the surrounding pixels)
can be represented as at least one additional dimension; an x,y image can be used to generate an x,y,z
surface where the z axis defines the magnitude chosen to generate the z-axis). For example, the magnitude
can be grayscale or a given color channel.

Other examples include conversion of the default color space for an image into the HLS (hue, lightness,
saturation) color space and then selecting the saturation or hue, or lightness dimensions as the
magnitude. Converting to an RGB color space allows selection of color channels (red channel, green
channel, blue channel, etc.). The selection can also be of single wavelengths or wavelength bands, or of
a plurality of wavelengths or wavelength bands, which wavelengths may or may not be adjacent to each
other. For example, selecting and/or deselecting certain wavelength bands can permit detection of
fluorescence in an image, or detect the relative oxygen content of hemoglobin in an image. The magnitude
can be determined using, e.g., linear or non-linear algorithms, or other mathematical functions as
desired.

Thus, the height of each pixel on the surface may, for example, be calculated from a combination of color
space dimensions (channels) with some weighting factor (e.g., 0.5*red+0.25*green+0.25*blue), or even
combinations of dimensions from different color spaces simultaneously (e.g., the multiplication of the
pixel's intensity (from the HSI color space) with its luminance (from a YUV, YCbCr, Yxy, LAB, etc., color
space)).

The pixel-by-pixel surface projections are in certain embodiments connected through image processing
techniques to create a continuous surface map. The image processing techniques used to connect the
projections and create a surface include mapping 2D pixels to grid points on a 3D mesh (e.g., triangular
or rectilinear), setting the z-axis value of the grid point to the appropriate value (elevating based on
the selected metric, e.g., intensity, red channel, etc.), filling the mesh with standard 3D shading
techniques (gouraud, flat, etc.) and then lighting the 3D scene with ambient and directional lighting.
These techniques can be implemented for such embodiments using modifications in certain 3D surface
creation/visualization software, discussed for example in U.S. Pat. Nos. 6,445,820 and 6,654,490; U.S.
patent application Ser. Nos. 20020114508; 20020176619; 20040096098; 20040109608; and PCT patent
publication No. WO 02/17232.

The present invention can display 3D topographic maps or other 3D displays of color space dimensions in
images that are 1 bit or higher. For example, variations in hue in a 12 bit image can be represented as a
3D surface with 4,096 variations in surface height.

Other examples of magnitude and/or display option include, outside of color space dimensions, the height
of a gridpoint on the z axis can be calculated using any function of the 2D data set. A function to
change information from the 2D data set to a z height takes the form f(x, y, image)=z. All of the color
space dimensions are of this form, but there can be other values as well. For example, a function can be
created in Lumen software that maps z height based on (i) a lookup table to a Hounsfield unit
(f(pixelValue)=Hounsfield value), (ii) just on the 2D coordinates (e.g., f(x,y)=2x+y), (iii) any other
field variable that may be stored external to the image, or (iv) area operators in a 2D image, such as
Gaussian blur values, or Sobel edge detector values.

In all cases, the external function or dataset is related in some meaningful way to the image. The
software herein can contain a function g that maps a pixel in the 2D image to some other external
variable (for example, Hounsfield units) and that value is then used as the value for the z height (with
optional adjustment). The end result is a 3D topographic map of the Hounsfield units contained in the 2D
image; the 3D map would be projected on the 2D image itself.

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=7,116,806.PN.&OS=PN/7,116,806&RS=PN/7,116,806