Elastic image matching is NP-complete

被引：42

作者：

Keysers, D ^{[1
]}

Unger, W

机构：

[1] Univ Technol Aachen, Rhein Westfal TH Aachen, Dept Comp Sci, Lehrstuhl Informat 6, D-52056 Aachen, Germany

[2] Univ Technol Aachen, Rhein Westfal TH Aachen, Dept Comp Sci, Lehrstuhl Informat 1, D-52056 Aachen, Germany

来源：

PATTERN RECOGNITION LETTERS | 2003年 / 24卷 / 1-3期

关键词：

elastic image matching; two-dimensional warping; NP-completeness;

D O I：

10.1016/S0167-8655(02)00268-4

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

One fundamental problem in image recognition is to establish the resemblance of two images. This can be done by searching the best pixel to pixel mapping taking into account monotonicity and continuity constraints. We show that this problem is NP-complete by reduction from 3-SAT, thus giving evidence that the known exponential time algorithms are justified, but approximation algorithms or simplifications are necessary. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：445 / 453

页数：9

共 18 条

[1] Optimal linguistic decoding is a difficult computational problem [J].