Online Program Home
My Program

Abstract Details

Activity Number: 254 - Contributed Poster Presentations: Section on Statistical Learning and Data Science
Type: Contributed
Date/Time: Monday, July 30, 2018 : 2:00 PM to 3:50 PM
Sponsor: Section on Statistical Learning and Data Science
Abstract #329917
Title: An Algorithm to Compare Patterns and Its Application on Shoe Out-Sole Impressions
Author(s): Soyoung Park* and Alicia Carriquiry
Companies: Iowa State University / CSAFE and Iowa State University
Keywords: Graph theory; Maximum-clique; Random forest; Image analysis; Shoe out-sole comparison; Graph matching

We develop an algorithm to compare graphs in shoe out-sole impressions using the property of geometrical congruence in patterns. The resulting similarity score can be used to compare a full or partial shoe out-sole impression (Q) from an unknown source to an impression (K) from a known reference shoe. The algorithm relies on graph theory and a maximum clique (MC) approach, and takes advantage of the MC's invariance to rotation and translation to align two impressions and quantify the degree of correspondence. First, the coordinates of 500 well defined corners are used to roughly align K and Q using MC. Second, all the coordinates of edges in Q and K are realigned using an alignment metric from the first step. Finally, we focus on local circular areas in Q and the corresponding regions in K and extract multiple features from their overlap, which we can combine into a single score using a random forest. Using our own developed R packages `Shoeprintr' and 2D images collected at CSAFE that so far include 444 pairs of known matches and 438 pairs of known non-matches, the positive predictive probability (indeed a match) was 96%, whereas the negative predictive probability was 92%.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2018 program