Similarity and Clustering of Footwear Prints

Research on footwear impression evidence has been gaining increasing importance in forensic science. Given a footwear impression at a crime scene, a key task is to find the closest match in a local/national database so as to determine footwear brand and model. This process is made faster if database prints are grouped into clusters of similar patterns. We describe a clustering approach based on common primitive patterns. Shape features consisting of lines, circles and ellipses are extracted from database prints using variations of the Hough transform. Then an attributed relational graph (ARG) is constructed for each known print, where each node is a primitive feature and each edge represents a spatial relationship between nodes. A footwear print distance (FPD) between ARGs is used as similarity measure. The FPD is computed between each known print and pre-determined patterns to form clusters. The use of the methodology is demonstrated with a large database of known prints.