Measurements and Scoring Procedures 

for Footwear Impression Comparisons

Presented by: 

Martin Herman

Other Team Members: 

John Buckleton, Gunay Dogan, Simone Gittelson, 

Hari Iyer, Yooyoung Lee, Steve Lund

Information Technology Laboratory, NIST

November 8, 2016
Outline

• Motivation and goals

• Description of SHOECALC – a software system 

under development

• Two example scenarios for SHOECALC

– Footwear impression comparison

– Database retrieval

• Summary
Motivation

• Need to improve measurement science 

underpinnings of forensic footwear analysis through 

quantitative analysis of observed characteristics

• Provide software-based approaches for quantitative 

analysis to the forensic footwear community
GOAL:

Develop SHOECALC (a prototype system)

• Inputs:

– Crime scene marks

– Test impressions

• Outputs:

– Similarity scores

– Image quality values

– For objectively 

informing weight of 

evidence assessments 

– For intelligence 

applications
SHOECALC

• For use by footwear examiners

– Gain experience and understanding of use of 

automated methods

– Use feedback from examiners to improve system

– Eventually utilize in casework -- assist examiner by 

providing similarity scores and image quality values

• Workbench for researchers/developers

– Develop new similarity measures and quality metrics

• Develop and test measures for discriminating between 

“mated” and “non-mated” footwear impressions

– Develop approaches and algorithms to “match” 

footwear images

SHOEBASE

Database consisting of

• Crime scene impressions and metadata

• Catalogue of outsole designs and metadata

• Test impressions from shoes of arrestees

• Catalogue of Randomly Acquired Characteristics (RACs) 

along with shape, size, location, brand, outsole design, etc.

• Interfaces and formats for submitting and maintaining 

footwear data

Current status: 

• Obtaining data from various sources, including crime labs, 

academia, and companies
Footwear Data Submission Format
SHOEGULI

Synthetic footwear impressions

• For research and testing, will generate synthetic 

footwear impressions with ground truth known, and 

with user specified characteristics

• Characteristics will include particular subpopulation of 

outsole designs, wear amounts, sizes, and distributions 

of RACs; also different matrix/substrate combinations

• Will generate both synthetic test impressions and 

crime scene impressions (e.g., partial impressions)

Current status:

• As an interim step, generated soft synthetic (crimescene-like) footwear data from actual test impressions
SHOEGULI

Level 1: Outsole features are 

very clear and unambiguous

Level 2: Clarity of outsole 

features is debatable
SHOEMET

Similarity measures

• Will be a workbench for experimentation with different 

similarity measures. Some measures lead to better 

discrimination between mated and non-mated pairs of 

images than others.

• User will input a function for computing a similarity 

score and apply it to any given pair of images; 

numerical score will be reported.

• Also will use SHOEGULI to conduct experiments and 

produce Receiver Operating Characteristic (ROC) plots 

for comparing with a catalog of known, high 

performance similarity measures.
Maximum Clique Algorithm

• Baseline algorithm for similarity

• Finds maximum cliques in a graph

– each node specifies a mapping 

from a feature in the first image in 

the comparison to a like feature in 

the second

– each edge specifies that the 

“relationship” (e.g., distance 

between features) between the 

two nodes connected by the edge 

is similar in the two images

• Image features used – corners, 

circles, straight line segments
Shape Dissimilarity for RAC Boundary Curves

RACs segmented from footwear impressions (courtesy of J. Speir, U of WV).

Similar RAC pairs -- shape distances:

Dissimilar RAC pairs -- shape distances:

Square-Root Velocity Function

(Srinivista et. al. (2011))

Boundary curve:

SRVF representation:

The shape [q] is the set of all 

rotated and reparameterized

SRVF functions:
SHOEQ

Quality measures

• Measuring quality: different characteristics 

that describe the degradation, distortion, 

completeness, and quantity of features in the 

impression

• User will input a footwear image; output will 

be a list of quality scores

• SHOEQ can be used

– To calculate better scores for casework, and

– As a workbench for researchers to develop better 

image quality metrics
SHOEQ

Current status:

• Implemented over 20 different quality metrics

• Demonstrated use of quality to improve 

similarity measures in casework

• Demonstrated use of quality to improve 

database retrieval performance
SHOESHINY

• GUI for user interaction with the other 

modules of SHOECALC

• Will allow user to upload images for 

calculation of similarity and quality scores

• Will allow user to examine various choices of 

similarity metrics and their ROC curves, and 

select choices for reporting the information in 

the evidence 

• Will allow exploratory pattern analysis 
SHOESHINY

Current status: 

Developed user interface to view, compare & analyze patterns and 

dissimilarity scores for pairs of patterns

• Clustering, heat maps, multidimensional scaling, statistics and 

histograms
Two Examples: 

Assisting Footwear Examiner Through 

Similarity and Quality Measures

Two example scenarios of using SHOECALC

1. Comparison of Crime Scene to Test Impressions

2. Database Retrieval

Here we only present initial studies to show 

proof of concept.
Comparison of Crime Scene to Test 

Impressions (1)

• Similarity scores can inform weight of 

evidence assessments

• Algorithmic comparison of questioned to 

known impressions

• Similarity score can provide additional 

information to examiner in evaluating 

observations
Comparison of Crime Scene to Test 

Impressions (2)

• For the given similarity measure, an ROC plot is 

obtained from empirical comparison tests using 

reference data samples (that have ground truth)

• The score obtained for the casework can be plotted on 

the ROC plot to determine identification error rates 

obtained on the reference test samples, using the score 

as a threshold. (see next slide)

• Quality measures can be used to further reduce the set 

of experimental comparisons considered so that they 

are more relevant to this particular case comparison
ROC Plot

Error rates for case 1

(8% FP, 71% FN)

Error rates for case 2

(59% FP, 12% FN)
Comparison of Crime Scene to Test 

Impressions (2)

• For the given similarity measure, an ROC plot is 

obtained from empirical comparison tests using 

reference data samples (that have ground truth)

• The score obtained for the casework can be plotted on 

the ROC plot to determine identification error rates 

obtained on the reference test samples, using the score 

as a threshold. (see next slide)

• Quality measures can be used to further reduce the set 

of experimental comparisons considered so that they 

are more relevant to this particular case comparison
Case 1 Case 2 

Case 3 
Database Retrieval (1)

• Improve efficiency of examiner in finding 

matches in an automated footwear database

• Usually returns rank-ordered list of candidates

– Examiner examines only candidates at the top of 

the list (e.g., top 10, 20, etc.)

• It would be valuable to have a similarity score 

algorithm that places the true match near the 

top of the list, i.e., reduce depth of search

• Quality measures can help place the true 

match higher up in the list
Database Retrieval (2)

• Consider the following situation:

Probe image: crime scene impression

Gallery images: test impressions of known 

offender shoes

• The process first calculates the similarity scores and 

lists the candidates in rank order

• Assume there are two similarity algorithms available. 

Certain quality metrics, when applied to the probe 

image, may be used as predictors to choose the 

better algorithm to reduce depth of search.
Algorithm A

Algorithm B
Summary

• Described SHOECALC prototype system and its current status.

• Described a maximum clique algorithm and shape dissimilarity 

for RAC boundary curves as two components that can be 

incorporated into a similarity algorithm. 

• Demonstrated use of quality values to develop ROC plots that 

are more relevant to particular case comparisons.

• Demonstrated use of quality values to improve database 

retrieval performance in terms of depth of search.

• These methods result in improved information provided to the 

examiner to aid in both forensic and intelligence applications.
Questions?

martin.herman@nist.gov