Insights: An Algorithm to Compare Two-Dimensional Footwear Outsole Images Using Maximum Cliques and Speeded Up Robust Features


An Algorithm to Compare Two-Dimensional Footwear Outsole Images Using Maximum Cliques and Speeded Up Robust Features


Footwear impression researchers sought to increase the accuracy and reliability of impression image matching. They developed and tested a statistical algorithm to quantify and score the degree of similarity between a questioned outsole impression and a reference impression obtained from either a suspect or a known database. The resulting algorithm proved to work well, even with partial and partial-quality images.

Lead Researchers

Soyoung Park 
Alicia Carriquiry


Statistical Analysis and Data Mining

Publication Date

21 Feb. 2020

The Goals


Develop a semi-automated approach that:

  • Compares impression evidence imagery with putative suspect or database images.
  • Calculates a score to quantify the degree of similarity (or correspondence) between the images.
  • Lowers human error and bias in current practice.


Create a method to obtain a similarity score for a pair of impressions which can be used to assess the probative value of the evidence.


This algorithm focuses on the similarity between two outsole images and relies on the concept of maximum clique. Local maximum cliques can be used to find corresponding positions in the two images so that they can be aligned.

Rotation and translation don’t affect a maximum clique –– it depends on the pairwise distances between nodes on the graph.

So –– although outsole pattern images may be translated, rotated and subjected to noise and other loss of information –– the geometrical
relationships between the points that constitute the pattern will not change much.

In this study, researchers developed a publicly available and usable database of 2D outsole impressions. Then the researchers used data from a KNM™ (knowledge navigator model) database.

Key Definitions

Graph Theory

Study of graphs made up of vertices connected by edges


A subset of vertices with edges linking symmetrically, where every two disinct vertices are adjacent

Maximum Clique

Clique that includes the larges possible number of vertices



With this new comparison learning algorithm, practitioners can align images using features chosen as areas of interest and calculate a similarity score more objectively.


The proposed pattern-matching algorithm can work with partial images or images of variable quality by partially aligning patterns to quantify degrees of similarity between two impressions.


While this study focuses on footwear evidence, this algorithm has potential
applications for other situations of pattern comparison, like:

  •  latent prints
  • surveillance photos
  • handwriting
  • tire treads and more.


The algorithm can distinguish impressions made by different shoes –– even when shoes share class characteristics including degree of wear.


Researcher Dr. Soyoung Park demonstrates the team’s novel algorithm in a CSAFE webinar. The method is promising, because it appears to correctly determine, with high probability, whether two images have a common or a different source, at least for the shoes on which they have experimented.


Explore and try the algorithm by downloading it.

NIST Releases New Report on Human Factors’ Role in Handwriting Evaluation

pen and handwritten text

All human activities carry a risk of error, and handwriting examination is no exception. To reduce errors in this field, NIST convened the Expert Working Group for Human Factors in Handwriting Examination. This expert panel sponsored by NIJ and NIST examined strategies to improve handwriting evaluation methods and outline best practices.

The Group produced a new report, Forensic Handwriting Examination and Human Factors: Improving the Practice Through a Systems Approach. The document takes a closer look at how human factors impact all aspects of handwriting examination, from documenting discriminating features, reporting results and testifying in court. 

In the report, you’ll also find a discussion of education, training, certification, and the role of quality assurance, quality control, and management in reducing errors.

CSAFE Resources for Improving Handwriting Evaluation 

CSAFE researchers are also working to improve objectivity and reduce errors in handwriting analysis. Our work aims to rigorously assess the role of complexity in signature analysis and relate complexity to examiner performance. We are also developing open-source software and publicly available statistical algorithms for writing comparison to help handwriting examiners integrate quantitative approaches in their work.

Handwriting Database

The CSAFE Handwriting Database is an interactive, public database designed for the development of statistical approaches to forensic handwriting evaluations.  


CSAFE automatic matching algorithms provide objective and reproducible scores as a foundation for a fair judicial process. This R package utilizes a variety of functions to identify letters and features from handwritten documents.


Tips for Students Pursuing Careers in Forensic Science

The exciting role of forensic scientist combines the power of observation, inference and research-based analysis to fight crime. From identifying the time of death to taking a closer look at fingerprints found at the scene, these scientists play an essential role in forensic examinations and linking suspects to specific evidence. 

The expert training and education of different types of forensic scientists is key to the investigation process and trial proceedings. Are you interested in joining the field? The U.S. Bureau of Labor Statistics anticipates jobs for forensic scientists will grow at twice the anticipated rate for other occupations, with a 17 percent increase between 2016 and 2026.  

Tips on Preparing to Become a Forensic Scientist

A forensic science job requires a minimum of a four-year bachelor’s degree in a field such as biology, chemistry or forensic science. Professionals recommend students seek out the following educational experiences to prepare for futures as a forensic investigator. 

  •     Search for a program with a strong academic core in natural sciences and math like biochemistry, toxicology, analytical chemistry and instrumental analysis. 
  • Obtain a thorough grounding in laboratory procedures and the use of scientific instruments. 
  • Build technical skills by taking courses in criminal justice, evidence handling and ethics.
  • Get acquainted with the criminal justice system and its processes through courses in criminology.
  • Develop strong written and oral communication skills to improve dialogue with law enforcement or explain findings to a judge and jury.
  • Seek out opportunities to gain additional hands-on experience through forensic science-related internships.

A Sneak Peek at an Advanced Degree

Students interested in jobs such as laboratory directors, professors or a specialist role can pursue advanced degrees. During a graduate program, you can choose a specialty such as ballistics, digital evidence or toxicology. In addition to classwork, master’s and Ph.D. students develop advanced skills in the laboratory. 

A Look at Continuing Education and Certifications

Education for the forensic scientist continues after the job begins with additional employer training. Certifications in various specialties such as blood pattern analysis, forensic photography and latent print analysis are available from organizations such as the International Association for Identification.

Impacting Society With A Career In Forensics

CSAFE offers students interested in pursuing forensic science careers the opportunity to discover how statistics apply to forensic evidence analysis. Learn more about our hands-on experiences for graduate and undergraduate students on our Forensic Education page and see how one student’s CSAFE research is preparing him for his dream job of DNA analyst.

Forensic science is a rigorous and demanding subject, but students committed to academic work and practical experience can stand out amongst other job applicants. Students can look forward to a gratifying career that contributes to the fair administration of justice.


First Interdisciplinary Training Standard Approved by OSAC

OSAC Registry Ribbon

The Organization of Scientific Area Committees (OSAC) for Forensic Science registry of approved standards now includes its first interdisciplinary training standard. This new standard provides guidelines to help laboratories ensure their team stays up-to-date on the latest forensic science methods and best practices. 


According to OSAC, ASTM E2917-19a Standard Practice for Forensic Science Practitioner Training, Continuing Education, and Professional Development Programs outlines what essential knowledge, skills and abilities laboratory training programs should address. Previously, these types of standards existed only in DNA and seized drug analysis disciplines. The standard also specifies continuing education requirements for forensic science professionals. 


OSAC Registry standards define minimum requirements, best practices, scientific protocols and other guidance to help ensure that the results of forensic analysis are reliable and reproducible.


Access Details:

OSAC, through the National Institute of Standards and Technology (NIST), has entered into a contract with ASTM International that gives 30,000 public criminal justice agencies free access to standards published under ASTM Technical Committee E30 on Forensic Science. To access these standards, click the green “ASTM Standards Access” button on OSAC’s Access to Standards webpage to enter the ASTM Compass website.