research-article

A Dual-Bound Algorithm for Very Fast and Exact Template Matching

Authors:

Haim Schweitzer,

Rui Deng, and

Robert Finis AndersonAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 33, Issue 3

Pages 459 - 470

https://doi.org/10.1109/TPAMI.2010.105

Published: 01 March 2011 Publication History

Publisher Site

Abstract

Recently proposed fast template matching techniques employ rejection schemes derived from lower bounds on the match measure. This paper generalizes that idea and shows that in addition to lower bounds, upper bounds on the match measure can be used to accelerate the search. An algorithm is proposed that utilizes both lower and upper bounds to detect the k best matches in an image. The performance of this dual-bound algorithm is guaranteed; it always detects the k best matches. Theoretical analysis and experimental results show that its runtime compares favorably with previously proposed real-time exact template-matching schemes.

Cited By

View all

Chan TYiu MHua K(2017)Efficient Sub-Window Nearest Neighbor Search on MatrixIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.263335729:4(784-797)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TKDE.2016.2633357
Shahhosseini SRezaie B(2016)Pattern Matching Using Partial Fourier SpectrumIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2015.243709126:7(1229-1240)Online publication date: 7-Jul-2016
https://dl.acm.org/doi/10.1109/TCSVT.2015.2437091
Kong YDong WMei XZhang XPaul J(2013)SimLocatorThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-013-0847-829:9(861-870)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1007/s00371-013-0847-8

Recommendations

Fast Template Matching With Polynomials

Template matching is widely used for many applications in image and signal processing. This paper proposes a novel template matching algorithm, called algebraic template matching. Given a template and an input image, algebraic template matching ...
Read More
Fixed time template matching
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

The problem of finding a match for an image ('template') within a larger image is known as template matching. It is key to a variety of Computer Vision applications. Currently known template matching algorithms run in fixed time, or are guaranteed to ...
Read More
Efficient Algorithms for Image Template and Dictionary Matching

Given a large text image and a small template image, the Template Matching Problem is that of finding every location within the text which looks like the pattern. This problem, which has received attention for low-level image processing, has been ...
Read More

Comments

Information & Contributors

Information

Published In

cover image IEEE Transactions on Pattern Analysis and Machine Intelligence

IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 33, Issue 3

March 2011

222 pages

ISSN:0162-8828

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 March 2011

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chan TYiu MHua K(2017)Efficient Sub-Window Nearest Neighbor Search on MatrixIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.263335729:4(784-797)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TKDE.2016.2633357
Shahhosseini SRezaie B(2016)Pattern Matching Using Partial Fourier SpectrumIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2015.243709126:7(1229-1240)Online publication date: 7-Jul-2016
https://dl.acm.org/doi/10.1109/TCSVT.2015.2437091
Kong YDong WMei XZhang XPaul J(2013)SimLocatorThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-013-0847-829:9(861-870)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1007/s00371-013-0847-8

Abstract

Cited By

Recommendations

Fast Template Matching With Polynomials

Fixed time template matching

Efficient Algorithms for Image Template and Dictionary Matching

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations