Computational complexity of similarity retrieval in a pictorial database

Three types of similarity are commonly used in similarity retrieval of a pi ctorial database. Only one of them is isometric, hence transitive. We prese nt polynomial time algorithms to find the maximum similar subpicture of two given pictures when the similarity is isometric. For nonisometric types, w e show that finding a maximum similar subpicture in two given pictures is N P-complete, even when all symbols are distinct, by reducing the satisfiabil ity problem to it. (C) 2000 Elsevier Science B.V. All rights reserved.