A REVIEW: ANALYSIS OF FOOTWEAR IMPRESSION EVIDENCE COLLECTION & DETECTION

KADAM A.B.¹*, MANZA R.R.², KALE K.V.^3
1Department of Computer Science, Shri. Shivaji Science & Arts College Chickhali, Buldana-411 005, MS, India.
²Department of Computer Science and IT, Dr. Babasaheb Ambedkar Marathwada University, Aurangabad-431 004, MS, India.
³Department of Computer Science and IT, Dr. Babasaheb Ambedkar Marathwada University, Aurangabad-431 004, MS, India.
* Corresponding Author : avinashkadam123@rediffmail.com

Received : 02-07-2012     Accepted : 05-07-2012     Published : 01-08-2012
Volume : 4     Issue : 2       Pages : 410 - 413
Int J Mach Intell 4.2 (2012):410-413
DOI : http://dx.doi.org/10.9735/0975-2927.4.2.410-413

Conflict of Interest : None declared

Impressions of footwear are commonly found in crime scenes. The quality and wide variability of these impressions makes their analysis is very difficult. This research will develop new computational methods to assist the forensic footwear examiner in the U.S. In this research work involves developing a database of representative footwear print images so that appropriate algorithms can be developed and their error rates can be determined. Algorithms for identifying special features such as wear marks and embedded pebbles will be developed. Matching algorithms to be developed will be for both the tasks of verification, where the goal is to determine whether the footwear evidence is from a particular suspect’s shoe, or that of identification, where the goal is to determine the brand of the shoe from a known set of brands. In each case a quantitative measure of the result of matching will be provided. In the identification mode, the tools will allow the narrowing down of possibilities in a database of known prints. Another goal this work is to assist the U.S. footwear examiner is homicides and assaults where there are no known prints to match. For this purpose a classification tool is to be developed, where the objective is to generate from the evidence a set of characteristics, e.g., gender, texture, shape, size and brand. This work will be extended by following guidelines of SWGTREAD and in close consultation with forensic footwear and/or tire tread examiners.

footwear matching, morphology, enhancement, indexing clustering & classification, etc.

Shoe marks- the mark made by the outside surface of the sole of a shoe (the outsole)- are distinctive patterns that are often found at crime scenes. Shoe marks can be broadly broken into two classes:
1. Shoe impressions which contain 3-dimensional information (e.g., shoe impression at the beach) and
2. Shoeprints which contain 2-dimensional information (e.g., shoeprint on a floor).
Shoe marks are common at crime scenes and are believed to be present more frequently than fingerprints [1] . A study of several jurisdictions in Switzerland revealed that 35 percent of crime scenes had shoeprints usable in forensic investigation, while in [2] , Girod found that 30 percent of all burglaries provide usable shoeprints.
More generally, footwear impressions are created when footwear is pressed or stamped against a surface such as a floor or furniture in which process the characteristics of the shoe is transferred to the surface. The tasks for the forensic footwear examiner are:
• verification: where an impression is to be matched against a suspect’s print,
• identification: matching the print evidence against a possibly large set of known prints, and
• classification: determining the generic characteristics of the footwear, such as brand, gender and size.
The variability of prints comes about because of the variety of surfaces on which the impressions are made [Fig-1] . Footwear marks provide valuable forensic evidence. In many instances, shoe marks can be positively identified as having been made by a specific shoe to the exclusion of all other shoes. Identification is based on the physical match of random individual characteristics the shoe has acquired during its life. Evidence provided by a positively identified shoe mark is as strong as the evidence from fingerprints, tool marks and typewritten impressions [1] . In other instances, detail retained in a shoe mark may be insufficient to uniquely identify an individual shoe but is still very valuable. Due to the wide variety of shoes available on the market, with most having distinctive outsole patterns, this implies that any specific model of shoe will be owned by a very small fraction of the general population. If the model of a shoe can be determined from its mark, then this can significantly narrow the search for a particular suspect. An image of a shoe mark can be obtained using photography, gel, or electrostatic lifting or by making a cast when the impression is in soil. Subsequently, in the forensic laboratory, the image of the shoe mark is compared with the shoeprints and shoe impressions of known shoe samples. A process of detection and recovery of footwear impression evidence and of comparison of the impressions with suspect shoes is described in [1] .
The photograph of the impression or of the lifted impression or cast can be subsequently scanned and a digital image produced. Forensic analysis requires comparison of this image against specific databases. These databases include: (i) marks made by shoes currently and previously available on the market and (ii) marks found at other crime scenes. Comparing crime scene shoe mark images to databases is currently a laborious task and it is commonly manually conducted by searching paper catalogues or computer databases. Due to its time consuming nature, shoe mark evidence is not used as frequently as it could be. For example, in 1993, only 500 of 14,000 recovered prints in the Netherlands were identified [3] . Thus, computer-based methods that reduce the operator effort for this task offer great benefit to forensic scientists. Forensic examiners of shoeprints and tire marks are a community of about 200 professionals in the United States. Shoeprints constitute about 80-90% of the case-work of the tread examiner who deals with both footwear and tire-marks. Guidelines for the profession are given on the IAI website dealing with the Scientific Working Group on Shoeprint and Tire Tread Evidence (SWGTREAD). The forensic footwear and/or tire tread examiner collects and preserves footwear and tire tread evidence, makes scientific examinations, comparisons and analyses of footwear and/or tire tread impression evidence in order to:
• include, identify, or eliminate a shoe or tire as the source of an impression;
• determine the brand or manufacturer of a shoe or tire;
• link scenes of crime;
• write reports and provide testimony as needed.
There has been significant research conducted in shoeprint analysis in Europe focusing on the needs of the European forensic community. There are important differences for the task in the US. Homicides and assaults are paid more attention to than burglaries in the U.S. In such cases, shoe prints have a very low likelihood of appearing in other cases. Due to this reason the classification task, i.e., determining brand, style, size, gender etc., is of importance. Through such classification, even if the person could not be identified, the search could be narrowed down to a smaller set of suspects. The goal of this research will be to develop several computational tools to assist the U. S. forensic community in dealing with footwear impressions. Some of the tasks are: rectification of the shoe-prints before they are analyzed, extraction of classificatory features for the purpose of identification or elimination, obtaining the strength of evidence (match score) based on the features extracted from the evidence and known prints and efficient search through a database of prints.

In an automatic footwear identification system, firstly, known shoeprints are scanned, processed and indexed into a database [Fig-2] . An automatic footwear identification system accepts as input shoeprint evidence and retrieves the most likely matching prints. Automatic matching of footwear patterns has been little explored. Early work [2,4-7] involves semi-automatic methods of manually annotated footwear print descriptions using a codebook of shape primitives, e.g., wavy patterns, geometric shapes and logos. The process is laborious and the source of poor performance due to inconsistent user encoding [17] .
In known footwear prints are scanned in different angles, like +30, -30, +60, -60, +90, -90, are scanned & indexed into a database [Fig-3] .
The approach of [3] employs shapes generated from footwear prints using image morphology operators. Spatial positioning and frequencies of shapes are used for classification with a neural network. No performance measures are reported [8,9] uses fractals to represent prints and mean square noise error classification.
Fourier Transforms (FT) have been used for classification of full and partial prints [10,11] .
Most recently [13] invariant local feature descriptors and spectral matching has been used previous techniques of automatic footwear matching can be characterized along four dimensions as follows.
1. Features Used
• fractal patterns [8,9] ,
• 2-D Discrete Fourier Transforms (DFT) [10,11] and
• local invariant descriptors [12,13]

2. Feature Similarity/Matching Algorithms Used
• Mean Square Noise Error method [8,9] ,
• DFT coefficients [10,11] and
• spectral correspondence matching method [13] for local invariant descriptor matching

3. Databases Tested are
• Database I [8,9] : 145 full-print images with no spatial or rotational variations,
• Database II [10] : 503 shoeprint images belonging to 139 pattern groups with each group containing 2 or more examples,
• Database III [11] : 476 complete images belonging to 140 pattern groups with each group containing two or more examples. and
• Database IV [13] : a subset of 368 different patterns [14]

4. Footwear Prints Used in Experiments are
• real footwear prints and
• generated partials [11] (Fig. 2.1).

There is a significant-sized literature on content-based image retrieval (CBIR). This is due to the fact that large volumes of images are being produced, e.g., by NASA and DoD and it is expensive or impossible to annotate each of them by type. Thus it is a challenge to find images similar to the one at hand.

Interactive image enhancement operations are available in Photoshop and other image processing software that are available to the footwear examiner. This effort will be to perform such operations automatically so that searching can be done efficiently.

Debris and shadows and other artifacts in the crime scene impressions will interfere with true shoe prints. So, the proposed task of “shoe print detection” is to automatically label a print to be a shoe print or not. For this task, not only shoe print images are needed, but also other types of prints encountered in crime scenes.

Debris and shadows and other artifacts in the crime scene impressions are difficult to filter out from footwear impressions. They have interfered with attempts to store and search in the database. Therefore, after digital image enhancement, some algorithms are desired to be able to classify different regions of footwear impression to be one of two types: useful regions (impressed by footwear) and discardable regions (impressed by other artifacts (noise) such as debris).

To cope with poor image quality robust matching algorithms, that possibly emulate human expert comparisons, should be designed to make accurate and fast decisions. A comprehensive system needs to integrate three levels of analysis: (i) Global shoe properties: heavily worn or brand new, shape, size etc., (ii) Shoe classification: brand, style, belongs to male or female (iii) Shoe recognition: Detailed and distinctive local features should be utilized to increase the discriminative power in order to confirm a match between a shoeprint recovered from the scene of crime and a suspect’s property.

In some crime scenes, only partial shoeprints (termed as “half prints” and “quarter prints”) are available, e.g., the right column of Fig. 2.1. When information available in partial prints is limited, effective utilization of the little information available is a challenge.

In a large shoeprint database, the efficiency (speed) of retrieving a query print may also be important. Effective indexing techniques should be designed for such requirement. Indexing method to enter standard shoeprint prototypes should also be developed.

Clustering of footwear prints into those of similar type can yield not only faster retrieval but also provide taxonomy of footwear print types. Clustering will involve extracting discriminating features from footwear prints and determining their proximity in feature space.

The system should be flexible to allow for possibly different types of retrieval. For instance, the task can be that to retrieve all shoeprints in the database that match a particular region of the shoeprint.

There are several potential classification tasks, e.g., determining brand or manufacturer, determining gender, etc. Even if a perfect match does not exist in the template database, a variety of classification algorithms could be relied upon to provide useful information such as gender, age and shoe size.

It is proposed to create a data set of foot-wear outer sole impression samples. They are necessary for developing algorithms for this research as well as for testing. At present such databases are not publicly available.

This project has commonalities with other projects in the analysis of impression evidence, specifically questioned document examination and friction ridge analysis. However there are also major differences. [17,18] .

A critical step in shoe-print identification is shoe-print extraction- which is the task of extracting the foreground from the background surface. The problem is formulated as a machine learning task which is approached using a probabilistic model, i.e. Conditional Random Fields (CRFs). Since the model exploits the inherent long range dependencies that exist in the shoe-print it is more robust than other approaches, i.e. neural networks & adaptive thresholding of grayscale images into binary [18] .

In this paper we observe & studied various techniques for identification, classification & verification for shoe-print evidence collection and detection. Most of researchers are used enhancement, morphological & segmentation techniques, bust the given results are not satisfied.
In future we used the various image processing techniques such as segmentation is very useful to extracting the foreground from the background. Specifically mathematical morphology & another edge based algorithms is very better to extract the shapes of various types of shoe-patterns such as noise, robust, full-prints, & partial prints, etc. datasets.

[1] Bodziak W. (2000) Footwear Impression Evidence Detection, Recovery and Examination.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Girod A. (1996) Forensic Science Int., 82, 59-65.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Geradts Z., Keijzer J. (1996) Forensic Science Int., 82, 21-31.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Sawyer N. (1995) Proc. European Convention on Security and Detection.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Ashley W. (1996) Forensic Science Int., 82(1), 7-20.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Mikkonen S., Astikainenn T. (1994) Journal of Forensic Science, 39(5), 1227-1236.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Mikkonen S., Suominen V., Heinonen P. (1996) Forensic Science Int., 82(1), 67-79.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Alexander A., Bouridane A., Crookes D. (1999) Seventh Internationl Conference Image Processing and Its Applications, 2, 638-641.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Bouridane A., Alexander A., Nibouche M., Crookes D. (2000) International Conference Image Processing, 1, 474-477.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] Huynh C., de Chazal P., McErlean D., Reilly R., Hannigan T. and Fleud L. (2003) International Conference Image Processing, 3, 569-572.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] de Chazal P., Flynn J., Reilly R.B. (2005) Pattern Analysis and Machine Intelligence, IEEE Transactions, 27, 341-350.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Zhang L., Allinson N. (2005) UK Workshop On Computational Intelligence (UKCI).  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Pavlou M., Allinson N.M. (2006) Intelligent Data Engineering and Automated Learning, Burgos, Spain, 721-728.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Service F.S. (1999) UK National Shoewear Database.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[15] Aitken C., Taroni F. (2004) Statistics and the Evaluation of Evidence for Forensic Scientists.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[16] Hand D., Mannilla H., Smyth P. (2001) Principles of Data Mining.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[17] Sargur Srihari (2007) Analysis of Footwear Impression Evidence, CEDAR, University of Buffalo State University of New York, Amherst, NY 14228.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[18] Veshnu Ramakrishanan and Sargur Shrihari (2008)International Conference on Pattern Recognition, IEEE Computer Society, FL.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1- Example of five shoeprint pattern categories. The left two columns show examples of images of full-prints and the right column shows examples of images of partial-prints.
	Fig. 2- Indexing: Known footwear prints are scanned, processed and indexed into a database.
	Fig. 3- Indexing: Known footwear prints are scanned in different angles.