liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Maximum Entropy Matching: An Approach to Fast Template Matching
Linköping University, Department of Electrical Engineering, Computer Vision. Linköping University, The Institute of Technology.
2000 (English)Report (Other academic)
Abstract [en]

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 [2] 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.

  1. One application is tracking of cars in video sequences from a  helicopter.
  2. 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
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-53370ISRN: LiTH-ISY-R-2313OAI: diva2:288327
Available from: 2010-01-20 Created: 2010-01-20 Last updated: 2014-09-15Bibliographically approved

Open Access in DiVA

fulltext(415 kB)337 downloads
File information
File name FULLTEXT01.pdfFile size 415 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Computer VisionThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 337 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 200 hits
ReferencesLink to record
Permanent link

Direct link