|
Abstract:
|
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%.
|
