Rotation and lighting invariant template matching

Kimmo Fredriksson, Veli Mäkinen, Gonzalo Navarro

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and it is brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost optimal both in the worst and the average cases simultaneously. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach. (c) 2007 Elsevier Inc. All rights reserved.
Original languageEnglish
JournalInformation and Computation
Volume205
Issue number7
Pages (from-to)1096-1113
Number of pages18
ISSN0890-5401
DOIs
Publication statusPublished - 2007
MoE publication typeA1 Journal article-refereed

Cite this

Fredriksson, Kimmo ; Mäkinen, Veli ; Navarro, Gonzalo. / Rotation and lighting invariant template matching. In: Information and Computation. 2007 ; Vol. 205, No. 7. pp. 1096-1113.
@article{75a3e4c53f014f05a5adc772ef64a5fd,
title = "Rotation and lighting invariant template matching",
abstract = "We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and it is brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost optimal both in the worst and the average cases simultaneously. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach. (c) 2007 Elsevier Inc. All rights reserved.",
author = "Kimmo Fredriksson and Veli M{\"a}kinen and Gonzalo Navarro",
year = "2007",
doi = "10.1016/j.ic.2007.03.002",
language = "English",
volume = "205",
pages = "1096--1113",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",
number = "7",

}

Rotation and lighting invariant template matching. / Fredriksson, Kimmo; Mäkinen, Veli; Navarro, Gonzalo.

In: Information and Computation, Vol. 205, No. 7, 2007, p. 1096-1113.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Rotation and lighting invariant template matching

AU - Fredriksson, Kimmo

AU - Mäkinen, Veli

AU - Navarro, Gonzalo

PY - 2007

Y1 - 2007

N2 - We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and it is brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost optimal both in the worst and the average cases simultaneously. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach. (c) 2007 Elsevier Inc. All rights reserved.

AB - We address the problem of searching for a two-dimensional pattern in a two-dimensional text (or image), such that the pattern can be found even if it appears rotated and it is brighter or darker than its occurrence. Furthermore, we consider approximate matching under several tolerance models. We obtain algorithms that are almost optimal both in the worst and the average cases simultaneously. The complexities we obtain are very close to the best current results for the case where only rotations, but not lighting invariance, are supported. These are the first results for this problem under a combinatorial approach. (c) 2007 Elsevier Inc. All rights reserved.

U2 - 10.1016/j.ic.2007.03.002

DO - 10.1016/j.ic.2007.03.002

M3 - Article

VL - 205

SP - 1096

EP - 1113

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 7

ER -