Template Matching Technique using Enhanced SAD Technique

Template Matching Technique using Enhanced SAD Technique

Bhavika K. Desai

M. E. Student

B. H. Gardi College Of Engineering. &

Technology-Rajkot Rajkot,Gujarat,India

DR. M. B. Potdar Project Director BISAG,

.

Gandhinagar. Gujarat, India

Manoj Pandya Project Manager BISAG,

Gandhinagar, Gujarat, India

Manish P. Patel

Assistant Professor

1. H. Gardi College Of Engineering. &

   Technology-Rajkot Rajkot,Gujarat,India

   Paru Thakkar Project Manager BISAG,

   Gandhinagar, Gujarat, India

   Abstract Translational template matching addresses the registration problem and has long been a problem of interest in such areas as video compression, robot vision, and biomedical engineering. Fast Fourier transforms (FFTs) have been called one of the ten most important algorithms of the twentieth century. Using some substitutions and complex arithmetic, computation of sum absolute difference derived is to be correlation functions of substituting functions. The former can be computed using the fast Fourier transform (FFT) approach, which is greatly less computationally expensive than the direct computation. The performance of the proposed methods, as well as some illustrative comparisons with other matching algorithms in the literature, is verified through simulations.

   The NCC metric is always suffering to locate the face especially in the images with illumination variations. In this paper we proposed a fast template matching technique based on similarity measurement metrics namely: Enhanced Sum of Absolute Difference (E-SAD) to overcome the drawback of NCC. NCC is affected by illumination and clutter background problems because sometimes there are non-face blocks that have almost the same value of the average face template matrix. This problem can be solved by using Sum of Absolute Differences algorithm (SAD) which is widely used for image compressing and object tracking but still SAD needs more optimization to give more accurate positions for face in the input image. Moreover, SAD can give high localization rate for facial where the image is with high illumination variation but it may be affected by variation in background [4].

   Keywords Convolution, Normalized Cross Correlation, Sum of Absolute Difference, Pattern Matching, Template Matching Fast Fourier Transform.

   INTRODUCTION

   Template matching is a common tool in many applications, including object recognition, video compression, stereo matching, and feature tracking. It has been used for video applications other than sequence coding such as motion compensated spatial temporal interpolation motion compensated enhancement. The SAD (sum of absolute differences) is another commonly used similarity metric. The algorithms which have been developed to speed up the process of sum of absolute difference (SAD) matching are designed

   exclusively in the spatial domain. Although there are many approaches whose objective is to speed up the process of SAD matching, they can only give the position of the SAD minimum. When the distance SAD should be calculated for every location in the image, the direct SAD computation requires more much time. Authors have proposed to expedite this naive approach using the FFT transform while exploiting the Fourier correlation theorem [2].

   1. METHADOLOGY

1. CONVOLUTION METHOD

   Fig. 1 Template convolution process [5].

2. NORMALIZED CROSS CORRELATION (NCC)

Normalized cross correlation (NCC) has been commonly used as a metric to evaluate the degree of similarity (or dissimilarity) between two compared images. The position of a given image pattern in a two dimensional image I. Let I(x, y) denote the intensity value of the image I of the size M x N at the point (x, y), x {0,M-1}, y {0,N-1}. The pattern is represented by a given template T of P x Q. A common way to calculate the position (i, j) of the pattern in the image I is to evaluate the normalized cross correlation value at each point (i, j) for I and the template T, which has

been shifted by I steps in the x direction and by j steps in the y direction. Equation gives a basic definition for the normalized cross correlation coefficient [4].

M N

(i, j)

i1 j1

M N M N

i1 j1

i1 j1

iP1 jQ1

I (x, y)

(1)

(I (x, y))

xi

y j

P Q

(2)

With similar notation µ(T) is the mean value of the template

T. The denominator in Equation (1) is the variance of the zero mean value image function I(x, y) – µ(I(x, y) and the shifted zero mean template function T(x-i, y-j) – µ(T). Due to this normalization, (i, j) is independent to changes in brightness to contrast of the image, which are related t the mean value and the standard deviation.

C. SUM OF ABSOLUTE DIFFERENCE (SAD) METHOD

Sum of absolute differences (SAD) is a widely used as simple algorithm for measuring the similarity between image blocks. It works by taking the absolute difference between each pixel in the original block and the corresponding pixel in the block being used for comparison. These differences are summed to create a simple metric of block similarity. The sum of absolute differences may be used for a variety of purposes, such as object recognition, the generation of disparity maps for stereo images, and motion estimation for video compression [3].

PROPOSED METHOD

The measure used in this paper is the sum of absolute value of differences one: we give a faster algorithm to perform the basic template matching computation for this measure using the frequency domain. In this paper, we propose to expedite this naive approach using the FFT transform while exploiting the Fourier correlation theorem.

Fig. 2 Proposed algorithm of Sum of Absolute Difference (SAD) using FFT

II EXPERIMENTAL RESULT

Fig. 3: Sample for the dataset of Image

TABLE 1 Re.sult of The Original Image Match With The Template Image

TABLE 2 Result of The Original Image Match with the Different Noise level

TABLE 3 Result of Blurring Template Image 1 with Original Image

Fig. 4: Chart of Template Image 1

TABLE 4 Result of Blurring Template Image 2 with Original Image

Fig.5: Chart of Template Image 2

TABLE 5 Result of Blurring Template Image 3 with Original Image

Fig 6: Chart of Template Image 3

TABLE 6 Result of Blurring Template Image 4 with Original Image

Fig 7: Chart of Template Image 4

TABLE 7 Result of Blurring Template Image 5 with Original Image

Fig 8: Chart of Template Image 5

The charts as shown in the above figure represent that by blurring image, the correlation of images reduces. The comparison among NCC, Convolution base and ESAD show that the correlation accuracy drastically reduces with respect to blurred images. Correlation for convolution remains almost constant and correlation for ESAD varies with blurred image. Hence E-SAD works properly for the images having less accuracy.

TABLE 8 Result of Noise Level Template Image 1 with Original Image

Fig. 9: Chart of the Template Image 1 for different noise level

TABLE 9 Result of Noise Level Template Image 2 with Original Image

Fig. 10: Chart of the Template Image 2 for different noise level TABLE 10 Result of Noise Level Template Image 4 with Original Image

Fig. 11: Chart of the Template Image 3 for different noise level

TABLE 11 Result of Noise Level Template Image 4 with Original Image

Fig. 12: Chart of the Template Image 4 for different noise level

TABLE 12 Result of Noise Level Template Image 4 with Original Image

Fig. 13: Chart of the Template Image 2 for different noise level

As shown in the above figure 9, 10, 11, 12 and 13, we can interpret that after adding the different level noise in Normalized Cross Correlation method and Convolution method, correlation value decreases gradually. While there is a drastic change in Enhance sum of absolute difference method while adding different noise levels. Hence variation in image helps to differentiate the objects from the template.

CONCLUSION

In this paper authors have proposed a modified enhanced SAD technique (E-SAD) to improve the performance of SAD. Enhanced SAD proved superiority compared with the other similarity measurements like NCC and Convolution based techniques. Maximum accuracy achieved by E-SAD is 97.5% with noise level 0.02. Template can be restored even from the blurred images. This technique is sensitive to noise.

ACKNOWLEDGMENT

Authors would like to thanks T. P. Singh, Director, Bhaskaracharya Institute for Space Applications & Geo- informatics (Gandhinagar) and B. H. Gardi College of Engineering & Technology-Rajkot for constant encouragement to our research work.

REFERENCES

1. ]. F. Essannouni Æ R. Oulad Haj Thami Æ,D. Aboutajdine Æ A. Salam,

   » Adjustable SAD matching algorithm using frequency domain in J Real-Time Image Proc (2007) 1:257265 DOI 10.1007/s11554-007- 0026-0.

2. Driss Aboutajdine and Fedwa Essannouni, Fast block matching algorithms using frequency Domain in LRIT, Laboratoire associ´e au CNRST, Facult´e des Sciences, Universit´e Mohamed V-Agdal, B.P. 1014 Rabat, Morocco.

3. Nadir Nourain Dawoud , Brahim Belhaouari Samir , Josefina Janier

   ,Fast Template Matching Method Based Optimized Sum of Absolute Difference Algorithm for Face Localization International Journal of Computer Applications (0975 8887) Volume 18 No.8, March 2011

4. C. Saravanan, M. Surender,Algorithm for Face Matching Using Normalized Cross- Correlation in. International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249 8958, Volume- 2, Issue-4, April 2013.

5. Mark Nixon & Alberto Aguado,feature extraction & image processing,second edition.

6. Mikhail J. Atallah, Faster Image Template Matching in the Sum of the Absolute Value of Differences Measure in IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 10, NO. 4, APRIL 2001.