Maximum Entropy Matching: An Approach to Fast Template Matching
2000 (English)Report (Other academic)
One important problem in image analysis is the localization of a template in a larger image. Applications where the solution of this problem can be used include: tracking, optical flow, and stereo vision. The matching method studied here solve this problem by defining a new similarity measurement between a template and an image neighborhood. This similarity is computed for all possible integer positions of the template within the image. The position for which we get the highest similarity is considered to be the match. The similarity is not necessarily computed using the original pixel values directly, but can of course be derived from higher level image features.
The similarity measurement can be computed in differentways and the simplest approach are correlation-type algorithms. Aschwanden and Guggenb¨uhl  have done a comparison between such algorithms. One of best and simplest algorithms they tested is normalized cross-correlation (NCC). Therefore this algorithm has been used to compare with the PAIRS algorithm that is developed by the author and described in this text. It uses a completely different similarity measurement based on sets of bits extracted from the template and the image.
This work is done withinWITAS which is a project dealing with UAV’s (unmanned aerial vehicles). Two specific applications of the developed template matching algorithm have been studied.
- One application is tracking of cars in video sequences from a helicopter.
- The other one is computing optical flow in such video sequences in order to detect moving objects, especially vehicles on roads.
The video from the helicopter is in color (RGB) and this fact is used in the presented tracking algorithm. The PAIRS algorithm have been applied to these two applications and the results are reported.
A part of this text will concern a general approach to template matching called Maximum Entropy Matching (MEM) that is developed here. The main idea of MEM is that the more data we compare on a computer the longer it takes and therefore the data that we compare should have maximum average information, that is, maximum entropy. We will see that this approach can be useful to create template matching algorithms which are in the order of 10 times faster then correlation (NCC) without decreasing the performance.
Place, publisher, year, edition, pages
Linköping, Sweden: Linköping University, Department of Electrical Engineering , 2000. , 24 p.
LiTH-ISY-R, ISSN 1400-3902 ; 2313
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-53370ISRN: LiTH-ISY-R-2313OAI: oai:DiVA.org:liu-53370DiVA: diva2:288327