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

## OVERVIEW

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.

Soyoung Park
Alicia Carriquiry

###### Journal

Statistical Analysis and Data Mining

21 Feb. 2020

IN 104 FW

## The Goals

### 1

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.

### 2

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.

## APPROACH AND METHODOLOGY

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

#### Clique

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

## KEY TAKEAWAYS FOR PRACTITIONERS

### 3

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

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

### SEE THE ALGORITHM IN ACTION

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.