Relaxing the triangle inequality in pattern matching

被引:60
作者
Fagin, R [1 ]
Stockmeyer, L [1 ]
机构
[1] IBM Corp, Almaden Res Ctr, San Jose, CA 95120 USA
关键词
pattern matching; shape matching; triangle inequality; distance measure; image database;
D O I
10.1023/A:1008023416823
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Any notion of "closeness" in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality (d(A, C) less than or equal to d(A, B) + d(B, C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a "relaxed triangle inequality" suffices, of the form d(A, C) less than or equal to c(d(A, B) + d(B, C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in (an experimental version of) IBM's QBIC(1) ("Query by Image Content") system (Niblack et al., 1993) satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.
引用
收藏
页码:219 / 231
页数:13
相关论文
共 12 条
[1]  
ARKIN EM, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P129
[2]   TRADEMARK SHAPES DESCRIPTION BY STRING-MATCHING TECHNIQUES [J].
CORTELAZZO, G ;
MIAN, GA ;
VEZZI, G ;
ZAMPERONI, P .
PATTERN RECOGNITION, 1994, 27 (08) :1005-1018
[3]  
Huttenlocher D. P., 1992, Proceedings. 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.92CH3168-2), P654, DOI 10.1109/CVPR.1992.223209
[4]  
Jain AK., 1989, FUNDAMENTALS DIGITAL
[5]  
Kim YS, 1997, PROC CVPR IEEE, P307
[6]   PSI-S CORRELATION AND DYNAMIC TIME WARPING - 2 METHODS FOR TRACKING ICE FLOES IN SAR IMAGES [J].
MCCONNELL, R ;
KWOK, R ;
CURLANDER, JC ;
KOBER, W ;
PANG, SS .
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING, 1991, 29 (06) :1004-1012
[7]   Shape measures for content based image retrieval: A comparison [J].
Mehtre, BM ;
Kankanhalli, MS ;
Lee, WF .
INFORMATION PROCESSING & MANAGEMENT, 1997, 33 (03) :319-337
[8]  
NIBLACK W, 1993, SPIE, V1908, P173
[9]  
NIBLACK W, 1995, P IEEE INT C IM PROC
[10]  
SCASSELLATI B, 1994, P SOC PHOTO-OPT INS, V2185, P2, DOI 10.1117/12.171777