Shoeprint evidence is often left at crime scenes, but is not always exploited. There is an increasing amount of research in developing systems to provide more rapid identification of footwear tread patterns. The main problem is that scene of crime shoeprint images can be very significantly degraded. In this paper we identify some of the challenges of this emerging research area. We then review current approaches to this problem, and we present some novel methods and results for two different ways of addressing the problem - namely in the spatial domain and in the transform domain. In the spatial domain, improvements to existing techniques lead to two novel variations which we call the Modified Harris-Laplace (MHL) detector, and the enhanced SIFT descriptor. In the transform domain, we present results of a technique based on Phase-Only Correlation.