Template Matching Using Sum And Differences Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Robot vision provides the robot controller with information about objects in the environment. Robot vision systems supply valuable information that can be used to automate the manipulation of objects. With the use of robotic vision, the position, orientation, identity, and condition of each part in the scene can be obtained .This high level information can then be used to plan robot motion such as determining how to grasp a part and how to avoid collisions with obstacles [6].The robot vision system consists of a mounted camera which takes images to be matched with the template images stored in the image directory. The template matching algorithm is used in order to find a match for the search image. This system is used in the industry mainly for picking objects from the conveyer belt. The camera is mounted on the robotic arm and a library of templates is stored in its memory. The template of the desired object is then compared with the image of each object that is moving on the conveyor and if a match is found, that object is picked up and separated from the rest. The scope of this work is to develop the template matching algorithm. This technique can also be used to distinguish faulty parts from the factory output. Rest of the paper is organized as ….

Template Matching

Template matching is one of the most common techniques used in signal and image processing. Template matching applications include image retrieval, image recognition, image registration, object detection, and stereo matching. Given an input and a template image, the matching algorithm finds the partial image that most closely matches the template image in terms of specific criterion, such as the Euclidean distance or cross correlation [1]. However, conventional template matching methods using a template image consume a large amount of computational time. A number of techniques have been investigated with the intent of speeding up the template matching.

The template matching process involves:

moving the template within the scene image at each position,

evaluating the similarity between the template and the image region over the template's position,

determining the positions based on similarity measure.

The correlation between the template and the image window has been used as a measure of similarity in template matching and image registration [9].The basic template matching algorithms includes pixel based matching of the template image with the target image. Generally, the template images are stored in the memory or image directory and then compared with the image taken by the mounted camera. A successful implementation is said to be done when the image searched is found. The coarse-to-fine strategy, proposed by Rosenfeld and Vander Brug [2] is a well-known approach to reduce the computational cost of template matching. This strategy uses a low-resolution template and an input image for initial coarse matching. Matching between high-resolution template and input images is applied for fine matching only when there is high similarity in the coarse matching. Tanimoto proposed a hierarchical search algorithm and introduced pyramid data structures [8]. However, this strategy cannot always find the most similar part in the fine matching since the other part may be detected in coarse matching. This strategy can be easily combined with other speed-up techniques.

Contextual template matching [4] refers to situations where the feature sets of the two templates under consideration may not be identical, but are rather contingent on the context within which these templates are observed. This paper addresses context-dependent template matching where the relevancy of certain features to a given object is contingent on the value of higher level features. It uses contextual matching where the image context space is matched. Relevant features of the object are taken together in a set. This set is then used as a reference for finding matches in the subordinate image. This approach uses relevant features, but these features may not be the compared features in the image and can be very difficult to program and thus doesn't give accurate results.

Considering the ease of processing [3], this method is based on a template matching process that targets route numbers of vehicles. However, with this method, the correlation values fluctuate greatly due to the changes in the external environment, which poses the problem of greatly reducing the judgment precision if simple threshold values are used. This paper describes the identification method using the above-mentioned template matching process and its problems, and proposes an identification method that uses anew recognition algorithm for solving those problems. This method uses correlation between template image and search area of the search image. It converts the template and search image in algebraic form for comparison. The algebraic polynomials are then correlated using the correlation theorem.

S. Omachi [7]et. al propose a novel template matching algorithm, called algebraic template matching. Given a template and an input image, algebraic template matching efficiently calculates similarities between the template and the partial images of the input image, for various widths and heights. The partial image most similar to the template image is detected from the input image for any location, width, and height. In the proposed algorithm, a polynomial that approximates the template image is used to match the input image instead of the template image. The proposed algorithm is effective especially when the width and height of the template image differ from the partial image to be matched. An algorithm using the Legendre polynomial is proposed for efficient approximation of the template image. This algorithm not only reduces computational costs, but also improves the quality of the approximated image. It is shown theoretically and experimentally that the computational cost of the proposed algorithm is much smaller than the existing methods. In this algorithm the image to be matched is first converted to a polynomial. The image polynomial is approximated using the least square method. The template image to be compared is then compared with the approximated image for matching.

R. Anderson and H. Schweiter [5] present a novel algorithm which in many cases can guarantee that the best match is found. In other cases it finds a good approximation to the best match. This algorithm runs in fixed time (a.k.a. hard real time). It finds an optimal match very quickly when a good match exists. This algorithm finds the distance between the image subwindow and template using an Early Termination. The distance is then decreased using the image subwindow and template. The pixels are then matched after every step. The algorithm compares the distance before matching, in this case the distance is maximum when the template and image sub window are very far from the start

Template matching has many applications including object tracking, stereo vision, machine vision and image coding.

Sum and Difference Algorithm

Acquire target image and template image.

FOR TARGET IMAGE : Since it represents a 2 dimensional image, we initialize 2 variables, one for the vertical scan line i change and one along the horizontal pixel line j.

Increment j for the entire horizontal scan line and keep variable i constant for each turn. Then increment i to change the scan line.

While incrementing j and i, compare the current pixel to the associated target image pixel. The pixels are compared by calculating the sum and difference between the intensities the two.

In step iv, if difference =0, then go to step iii and continue matching for further pixels.

In step iv, if difference > 0, then break loop and terminate program.

In step v, the difference between the pixels is 0, i.e. the pixels are same and if all the pixels of these are matched in this way, the target image and template image are the same.

In step vi, there is a difference between the intensities, i.e. the pixels are not same so the image cannot be matched resulting in an undesired result.

Template Matching

The experimental results and conclusions are based on results obtained by applying the proposed method to 20 images stored in the image directory. The following experiment conducted was performed by selecting the template image from the image directory and comparing it with the search image provided to the program as target. A suitable output to the program will be obtaining a match for the target image and obtaining a subplot of the target image. If in case a match is not found, the program will give a negative feedback. As the given images show, there is a target image, a template image and a generated result image. Since the required result is found, the resultant image shows a indication box at the co-ordinates where the image is found. As soon as the result is found, the program is terminated and the output image is produced (figures 2,3,4).

The main advantages of this method are that there is a comparison of pixels instead of comparing the entire region gives a more accurate result, as the intensities of each pixel is compared. Compared to region based matching the proposed algorithm is more accurate as the average intensities of the region is not manipulated according to the template.

Conclusion and Futurework

The proposed algorithm is very effective as shown in the experimental results and can serve as a basis for further research on robot vision systems. There is scope of improvement in the algorithm as the current algorithm is slow and requires considerable amount of processing since it compares each pixel to the template image pixels. Also the method of calculating exact difference, i.e. 0 differences between 2 pixels can in some cases not hold true, because of minute differences in the images.

Flowchart of Sum and Difference Algorithm