<figure><img src="image_1.png" /></figure>

HAL
open science

# The Retrieval of Shoeprint Images Based on the Integral Histogram of the Gabor Transform Domain

Xiangyang Li, Minhua Wu, Zhiping Shi

► To cite this version:

Xiangyang Li, Minhua Wu, Zhiping Shi. The Retrieval of Shoeprint Images Based on the Integral Histogram of the Gabor Transform Domain. 8th International Conference on Intelligent Information Processing (IIP), Oct 2014, Hangzhou, China. pp.249-258, 10.1007/978-3-662-44980-6_28 . hal-01383339

HAL Id: hal-01383339

https://inria.hal.science/hal-01383339

Submitted on 18 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Retrieval of Shoeprint Images Based on the Integral Histogram of the Gabor Transform Domain

Xiangyang Li, Minhua Wu, Zhiping Shi*

Capital Normal University, College of Information Engineering, Beijing, China
{lixiangyang806, shizhiping}@gmail.com, wumhxxxy@126.com

**Abstract.** Shoeprint images which are extracted at the scene of cases are a kind of important modern forensic clue and evidence. Retrieving the images of the same or the similar shoeprint images from the database quickly and accurately is very important to criminal investigation. To deal with the fragmental shoeprint images, we propose a shoeprint images matching and retrieval algorithm which computing the integral histogram in the Gabor transform domain. First, through the integral histogram find out the most similar position of the fragmental image in the intact image. Then, extract the features of the region found in the first step. At last, compute the similarity of the two components. Experiment results prove that this algorithm leads an increase of 4.82% in the retrieval precision, compared with computing the global features of two images directly.

**Keywords:** fragmental images, Gabor filtering, integral histogram, image retrieval

## 1 Introduction

Shoeprint images are common found at the scene of the crime, which are easy-to-be-left, multiple, specific, relatively stable, continuous. They play a very important role in the criminal investigation and forensic evidence. The traditional methods of managing and retrieving shoeprint images are mainly based on manual coding. For all kinds of shoeprint images, we need to design a coding standard given different coding for different images. Then according to the standard, implement shoeprint images recognition [1]. The manual coding method relies on the operator too much, so the operator's subjective factors have much influence on the identification result. And at the same time, with the rapid increase of shoeprint images, it's very difficult to achieve a satisfactory result. Retrieving the images according to user's requirements quickly and accurately is related to the efficiency of cases in the department of police. Therefore, it is very important to develop a shoeprint images retrieval algorithm with high retrieval accuracy and high speed.

In general, image features mainly include color, texture, shape and spatial location which are extracted from the entire image or from one region [2-3]. How to extract the features efficiently is the key of content based image retrieval (CBIR). Shoeprint
is imprinting of the sole contact with the ground, so color features is meaningless,
only features such as texture, shape and space layout are useful. Guan [4] had pro-
posed a method of recognition for shoeprint images based on outline features, which
find out the outline points at the longest distance according to the truth that the length
of shoe sole was longer than any other parts in a shoe sole, and then calculated the
angle shaped by the two points and horizontal axes. It proofreaded the shoe soles in
terms of calculated angle, extracted 9 features of shoes sole automatically, and then
measured the similarity of shoe soles by Euclidean distance. This method uses the
global contour features of the image, so it is not suitable when there are fragmental
images among the shoeprint images. Jia [5] had proposed a method which classified
the shoeprint images by using the characteristic quantity got from the Laws template
convolution of the image. It can identify the type of grain and point pattern. But to
complex type such as mixed type, edge block type and circle type, it does not have
good recognition efficiency. Xiao [1] had proposed a method based on PSD (power
spectral density) and Zernike moment. But if the segmentation of the shoeprint image
is inaccurate, the Zernike moment features do not performs well. Zhang [6] had pro-
posed a method for retrieving multi-texture images based on counter and texture seg-
mentation. Gabor wavelet transform is applied to extract the features of images. It has
a higher retrieval precision, but it is not suitable to process incomplete images align-
ment, because it uses the global features.

To deal with the fragmental shoeprint images, we propose a shoeprint images
matching and retrieval algorithm based on the integral histogram in the Gabor trans-
form domain. Filter the image with Gabor filter cluster, use the index of the filter
which has the maximum response to replace the gray value of the image in every
pixel, and then, compute the integral histogram of the transformed image. Through
the integral histogram, find out the most similar position of the fragmental image in
the intact image. Then, extract the features of the region found in the former step. At
last, compute the similarity of the two components. Experiment results prove that this
method provides a higher retrieval precision, and it is adaptive to fragmental image
processing.

## 2 Retrieval process of shoeprint images

The retrieval process of shoeprint images is shown in Figure 1. Firstly, pre-process
the images obtained on the scene, and then convert them to binary images. Secondly,
index these images based on features extracted from them. Finally, we can implicate
image retrieval. Due to the complex environment on the scene of the crime, the in-
complete contact between the sole and the ground, and the limit of image segmenta-
tion technology, a lot of shoeprint images are incomplete. Therefore, after pre-
processing, the images have inconsistent size and integrity. As shown in Figure 2, the
fragmental image is only part of the full image.
<figure><img src="image_3.png" /><figcaption>Fig. 1. Shoeprint image retrieval process</figcaption></figure>

<caption>Fig. 2. Intact image and fragmental images</caption>

## 2.1 Shoeprint Preprocessing

Useful information of shoeprint images is included in the binary description of the images, so it is important to determine whether the pixel is shoeprint grains or background. Binary image not only reduces the storage capacity, but also can make big contributions to image identification in the later process. There are four main steps in the binarization preprocessing.

- Smooth the original image with a low-pass filter to reduce the noise.

- Divide the images into three parts: the soles, the arch and the heel, the portion rate are 0.45, 0.25 and 0.3. And then every part is divided into 3\*3 blocks. The division of shoeprint is shown in Figure 3.

- To each small block, use the cvAdaptiveThreshold function provided by Opencv 2.4.3 [7] for adaptive threshold binarization., where the first two parameters src and dst are the input and output images, parameter max_val is set to 255, this means the pixel value which is greater than the threshold is set to 255. Parameter adaptive_method is set to ADAPTIVE_THRESHOLD_MEAN_C, block_size is set to the maximum odd value which is not bigger than the width and weight of the small block, the value of the parameter param1 is set to 0. In this way, every pixel is processed by the threshold of the average weighted sum of size b\*b from its neighbours.

- Use morphological operations to process the images to eliminate the noise of the small points, and connect the area broken by binarization.

The binarization results of the images are shown in Figure 4.
## 2.2 Feature extraction

Shoeprint images are binary images after pre-processing, so texture feature and shape feature are mainly considered. Texture is the basic structure of the surface or attribute of an object. It is generally acknowledged that texture is the grayscale change or color change of the image on the space. Comparing the Hu invariant moments [8], co-occurrence matrix [9] and Gabor texture feature, the experimental results show that the last one is the best, so we choose the Gabor texture feature as texture descriptor.

<figure><img src="image_4.png" /><figcaption>Fig. 3. The division of the shoeprint</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5. Integral Histogram</figcaption></figure>

Gabor filter is widely used in image representation, recovery and segmentation, as well as other fields, which is mainly based on the following two points: First, Gabor filter can simulate mammalian visual cortex simple cells receptive field, which is conformed to the characteristics of visual physiology. Second, Gabor filter is able to obtain the best joint resolution in frequency domain and space domain [10]. Texture varies in direction, frequency and extent, and the wavelet transform window can be adaptively adjusted to the change of the window center frequency. Therefore, to extract the texture features of an image, we usually use a cluster of self-similar Gabor wavelets obtained from a mother Gabor wavelet instead of a single one.

The Gabor function is a sine wave modulated by Gaussian function. A two dimensional Gabor function $h(x, y)$ and its Fourier transform $H(u, v)$ can be written as [11]:

$$g(x, y) = \frac{1}{2\pi\sigma_x\sigma_y} \exp\left(-\frac{1}{2}\left(\frac{x^2}{\sigma_x^2} + \frac{y^2}{\sigma_y^2}\right)\right) \quad (1)$$

$$h(x, y) = g(x, y) \exp(2\pi j Wx) \quad (2)$$

$$H(x, y) = \exp\left(-\frac{1}{2}\left(\frac{(u-W)^2}{\sigma_u^2} + \frac{v^2}{\sigma_v^2}\right)\right) \quad (3)$$
where g(x, y) is the Gaussian function, σx and σy are mean square errors in x axis and y axis, which determines the shape of the Gaussian envelope, W is the frequency of the sinusoidal function on the horizontal axis. A cluster of self-similar functions, referred to as Gabor wavelets in the following discussion, is now considered. Let h(x, y) be the mother Gabor wavelet, then self-similar filter dictionary can be obtained by appropriate dilations and rotations of h(x, y) through the generating function [12]:

$$h_{mn}(x, y) = a^{-m} h(x', y'), a > 1, m, n \in \mathbb{Z} \quad (4)$$

$$x' = a^{-m} (x \cos \theta + y \sin \theta), \quad y' = (-x \sin \theta + y \cos \theta), \quad \theta = n\pi / K \quad (5)$$

where α⁻¹ is the scale factor, S is the number of scales and K is the number of orientations, m=0, 1, ..., S-1 and n=0, 1, ..., K-1. Assuming that the class of Gabor wavelets contains S scales and K directions, and the frequency ranges from U₁ to Uₕ, the parameter selection method is as follows:

$$a = (U_h / U_l)^{1/(S-1)}, \quad U_{(n)} = a^n U_l \\ \sigma_{u(n)} = (a-1)U_{(n)} / [(a+1)\sqrt{2\ln2}] \\ \sigma_{v(n)} = \tan(m\pi/(2k)) [U(n) - 2\ln2(2/U(n))] / \sqrt{2\ln2 - (2\sigma_{u(n)}\ln2/U(n))^2} \quad (6)$$

Gabor filter has the characteristics of multi-channel and multi-resolution analysis, through the Gabor filter to extract the features of an image can achieve high resolution in both spatial domain and frequency.

## 2.3 Integral Histogram

Histogram is one of the most widely used features in image recognition and retrieval with high recognition efficiency as it is simple to be calculated. But it cannot be applied to the local alignment of the image because it is the global feature. An improved method is to compute the histogram of the local area we are interested in. Integral Histogram is a method to compute the histograms of all possible target regions in a Cartesian data space with high efficiency [13-14] For the image, H(x, y) is defined as: H(x, y)={Hu, u=1, 2, ..., d}, where d is the scope scale of the gray image. H(x, y) is the histogram of the rectangle formed by the origin point and the point (x, y) of the image.

$$H(x, y) = K(R(0, 0, x, y)) \quad (7)$$

where K is the operation of computing the histogram. The histogram of any rectangular in the image can be quickly computed from its Integral histogram.

In Figure 5, there are four vertices. The histogram of the rectangular shaped by the points A, B, C and D is:

$$K(R(x1, y1, x2, y2)) = H(x2, y2) - H(x2, y1) - H(x1, y2) + H(x1, y1) \quad (8)$$
When the integral histogram of an image is computed, the histogram of target region can be computed easily using simple arithmetic operations.

<figure><img src="image_6.png" /><figcaption>Fig. 4. The original shoeprint images and the images after binarization</figcaption></figure>

## 2.4 The process of the algorithm

To deal with the fragmental shoeprint images, we propose a shoeprint images matching and retrieval algorithm based on the integral histogram in the Gabor transform domain. First, filter the image with the Gabor wavelets. Because the Gabor wavelets are a cluster of self-similar wavelets, so each pixel can get a response value from each filter. In order to transform the image into the characteristics space, use the index of the filter which has the maximum response to replace the gray value of the image in every pixel. Let the original grayscale value of the image is f(x, y), after the transformation, the value f'(x, y) is defined as:

$$f'(x, y) = k, H_k(f(x, y)) = \text{Max}(H_j(f(x, y))(j = 0, 1, 2, \dots, N-1)) \quad (9)$$

where N is the total number of the filters, H_k(f(x, y)) is the result of the point f(x, y) filtered by the filter numbered k. By this, the image is transformed from spatial domain into Gabor transform domain. We can calculate the histogram of one image, so we get the GTH (Gabor Transform Histogram) features. Meanwhile, we can get the features noted as GTIH (Gabor Transform Integral Histogram) by computing the integral histogram of the image.

<figure><img src="image_7.png" /><figcaption>Fig. 6. Flow chart of the algorithm</figcaption></figure>

<caption>Fig. 7. The retrieval result</caption>
The shoeprint images retrieval algorithm is described as shown in Figure 6. The retrieval process is: Filter the image with Gabor filters cluster, use the index of the filter which has the maximum response to replace the gray value of the image in every pixel, and then, compute the integral histogram of the transformed image. To compute the similarity of the fragmental image and the complete image, first, we need to find out the most similar position of the fragmental image in the intact image through the integral histogram. Then, extract the features of the region found in the first step. At last, compute the similarity of the two components. For the image of similar size, compute the similarity directly according to the histogram using the metric method of histogram intersection.

## 3 Experimental Results and Comparisons

In this paper, the shoeprint images retrieval algorithm based on integral histogram is implemented in Visual Studio 2010 and Opencv 2.4.3 platform with c++ language. The experiment environment is: Intel Core i5-3470 3.20GHz, Windows 7, 4.00 GB. There are 2000 binary images which are the processing results of the shoeprint images captured on the scene of the crime. To evaluate the performance of the algorithm, we choose 195 images as a test set. There are 13 categories in the test set, and each category has 15 images. The images are binary images with black background after a series of processing, such as denoising, segmentation, etc. Sometimes, there are large black blocks at the edge of an image. The black edge not only doesn't carry characteristics of the image, but also increases the amount of calculation when filtering it. Hence, to each image, we compute its vertical histogram and horizontal histogram. After this, we can get the effective area of an image. Then, we extract the features of this area. The effective areas of images are shown on Figure 7. As shown in Figure 2, the outside large rectangle is the effective area of the image. The inner small rectangles of the intact image are the most similar position of the fragmental images computed through integral histogram.

Usually the retrieval performance of a CBIR system is measured by precision and recall [3]. Precision (Pr) is defined as the ratio of the number of relevant images retrieved ($N_r$) to the number of total retrieved images $K$. Recall (Re) is defined as the number of retrieved relevant images $N_r$ over the total number of relevant images available in the database $N_t$.

$$ Pr = N_r / K, \quad Re = N_r / N_t \qquad (10) $$

Retrieve each image in the test set, and then compute the average precision. Every time, the system returns 15 images which are most similar to the input images, the former, the more similar, and the most similar 13 images are shown. Figure 7 is the shoeprint retrieval system interface showing the retrieval results. We use Pr to measure the performance of different algorithm. Table 1 is a comparison of several different algorithms. They are described as follows.
- Hu invariant moments features [8]. Calculate the Hu invariant moments features of the image, and use Euclidean distance to measure the similarity (Hu).

- Co-occurrence matrix features [9]. Compute the gray level co-occurrence matrix of the image. The matrix is generated by the parameters: step length is 1 pixel and the orientations are 0, 45, 90, 135 degrees. And then, compute the deficit, energy and entropy of these matrixes and use Euclidean distance to measure the similarity (CoMatrix).

- Extract the GTH feature from the image, and use Euclidean distance to measure the similarity (GTH-E).

- Extract the GTH feature from the image, use histogram intersection to measure the similarity (GTH-I).

- Filter the image with Gabor wavelets. For each filter, we can get a middle image after the filtering, compute the mean and variance of the middle image. Use them as the features of the image (GMV), and use histogram intersection to measure the similarity. GMV are multi-channel features get from the filtered image, so it is not suitable to use Euclidean distance to measure the similarity (GMV-E).

- Extract GTIH features from the image and use histogram intersection to measure the similarity. If the image is fragmental image, find out its most similar position in the intact image, through the integral histogram, compute the feature of the found region (GTIH-I).

- Use the method of GTIH-I to find out the most similar position. Use Gabor cluster filters to filtering the found region to extract the features. Then use histogram intersection to measure the similarity (GTIH-I-R).

In Table 1, Time is the average retrieve time of one image. The experimental results show that the features extracted by Gabor filters are effective to describe the characteristics of the images. Compared with GTH-I, GTH-E proved that the distance measurement histogram intersection is a little better than Euclidean distance, but the difference is small. GTIH-I search for the local features, so its accuracy is better than GTH-I which uses the global features. GTIH-I-R re-extracts the features of the found region, so it increases the retrieval accuracy obviously. GTIH-I-R improves the precision by 4.82% on average compared with the GMV-E.

<table><caption>**Table 1.** The Performance of Different Algorithm</caption><thead><tr><td>Algorithm</td><td>Percision</td><td>Time (second)</td></tr></thead><tbody><tr><td>Hu</td><td>0.228718</td><td>0.002523</td></tr><tr><td>CoMatrix</td><td>0.233504</td><td>0.011149</td></tr><tr><td>GTH-E</td><td>0.396923</td><td>4.688564</td></tr><tr><td>GTH-I</td><td>0.403077</td><td>4.277297</td></tr><tr><td>GMV-E</td><td>0.419487</td><td>4.580621</td></tr><tr><td>GTIH-I</td><td>0.419145</td><td>208.085226</td></tr><tr><td>GTIH-I-R</td><td>0.467692</td><td>317.529205</td></tr></tbody></table>

As shown in Table 2, to measure the similarity of fragmental image and intact image, the result of the method using integral histogram to compute the features of the most
similar region is 0.902385. The result of the method using the cluster of Gabor filters to re-extract the features of the most similar region is 0.938849. The results show that the re-extract features has higher retrieval efficiency. Because the re-extract features of the most similar region have no characteristics of other regions, so they are more localized and more accurate.

<table><caption>**Table 2.** Compute the features of the most similar region</caption><thead><tr><th>Method</th><th colspan="3">Features (12-demensional)</th></tr></thead><tbody><tr><td rowspan="4">The feature of the original fragmental image</td><td>0.205336</td><td>0.083475</td><td>0.139575</td></tr><tr><td>0.107085</td><td>0.063219</td><td>0.031357</td></tr><tr><td>0.054153</td><td>0.038420</td><td>0.075421</td></tr><tr><td>0.006755</td><td>0.059016</td><td>0.007900</td></tr><tr><td rowspan="4">Use the integral histogram to compute the features directly</td><td>0.183289</td><td>0.093500</td><td>0.194598</td></tr><tr><td>0.122024</td><td>0.073280</td><td>0.038685</td></tr><tr><td>0.069721</td><td>0.049539</td><td>0.127830</td></tr><tr><td>0.008835</td><td>0.025142</td><td>0.013555</td></tr><tr><td rowspan="4">Use the cluster of Gabor filters to re-extract the features</td><td>0.194752</td><td>0.076310</td><td>0.151491</td></tr><tr><td>0.096853</td><td>0.063219</td><td>0.033249</td></tr><tr><td>0.092727</td><td>0.041732</td><td>0.062361</td></tr><tr><td>0.007493</td><td>0.042909</td><td>0.008626</td></tr></tbody></table>

# 4 Conclusion

The paper has presented a shoeprint images retrieval algorithm based on Gabor transform domain. The algorithm can provide a higher retrieval precision, especially when the images contain fragmental ones. The innovation of the algorithm is: use the index of the filter which has the maximum response to replace the gray value of the image in every pixel, and then, compute the integral histogram of the transformed image. Use the integral histogram to efficiently find the region in the intact image which the fragmental one is most similar to; avoid comparing the global features directly. Measure the similarity of the features re-extracted from the found region and the features of the fragmental image, to improve the shoeprint images retrieval precision.

# Acknowledgment

This work was supported in part by National Nature Science Found Grants No. 60903141 and No. 61165009. The authors are grateful for the many specific and valuable comments made by the reviewer.
References

1. Xiao, R., Lu, N., Shi, P.: Methods on shoeprint matching. In: the 13th National Conference on Image and Graphics, Nanjing, pp. 256-360(2006)

2. Zhang, D., Islam, M., Lu, G.: A review on automatic image annotation techniques. Pattern Recognition, vol. 45, No. 1, pp. 146-162(2012)

3. Chadha, A., Mallik, S., Johar, R.: Comparative study and optimization of feature extraction techniques for content based image retrieval. International Journal of computer application, vol. 52, No. 20, pp. 25-42(2012)

4. Guan, Y., Li, C., Zhong, M.: Research and realization of recognition for shoe soles based on outline feature. Application Research of computers, Vol. 25 No.8, pp. 2413-2415(2008)

5. Jia, S., Shi, W., Zeng, J., Chen, S.: Shoe prints identification and classification methods based on texture characteristics. Journal of Da Lian Jiao Tong University, Vol. 19 No. 1, pp. 59-62(2008)

6. Zhang, Z., Shi, Z., Shi, Z., Shi, Z.: Image retrieval based on contour. Journal of software, Vol. 19 No. 9, pp. 2461-2470(2008)

7. Bradski, G., Kaehler, A.: Learning Opencv. Tsinghua University Press, Beijing, pp. 155-161(2009)

8. Hu, M.: Visual pattern recognition by moment invariant. IRE Transaction on Information Theory, vol. 8, No. 2, pp. 179-187(1962)

9. Gao, C., Hui, X.: GLCM-Based texture feature extraction. Computer System Application, vol. 19, No. 6, pp. 195-198(2010)

10. Sing, S., Hemachandran, K.: Content-Based image retrieval using Color Moment and Gabor texture feature. International journal of computer science issues, vol. 9, No. 1, pp. 229-309(2012)

11. Roslan, R., Jamil, N.: Texture feature extraction using 2-D Gabor filter. In: Proceedings of IEEE Symposium on Computer Applications and Industrial Electronics, pp. 173-178, Kota Kinabalu(2012)

12. Manjunath, B., Ma, W.: Texture feature for browsing and retrieval if image data. IEEE Transactions on PAMI, vol. 18, No. 8, pp. 837-842(1996)

13. Porikli, F.: Integral histogram: a fast way to extract histograms in Cartesian spaces. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 829-836, San Diego(2005)

14. Park, J., Park, J., Kim, T.: Block-based fast integral histogram. Spring on Engineering and Technology, pp. 1-4, Xi'an(2012)