Structural Descriptions and Inexact Matching
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 September 1981Open access
Linda G. Shapiro, Robert M. Haralick
Citations542
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The structural description of an object and the concepts of exact and inexact matching of two structural descriptions are formally defined and the formula for the expected number of nodes in the tree for backtracking alone and with a forward checking algorithm is developed.
Abstract
In this paper we formally define the structural description of an object and the concepts of exact and inexact matching of two structural descriptions. We discuss the problems associated with a brute-force backtracking tree search for inexact matching and develop several different algorithms to make the tree search more efficient. We develop the formula for the expected number of nodes in the tree for backtracking alone and with a forward checking algorithm. Finally, we present experimental results showing that forward checking is the most efficient of the algorithms tested.
Keywords
Computer Science
Artificial IntelligenceConsistency in networks of relations
2,430 Citations1977Alan K. Mackworth
The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.
Journal of the ACMAn Algorithm for Subgraph Isomorphism
2,252 Citations1976J. R. Ullmann
A new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search by means of a brute-force tree-search enumeration procedure and a parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is described.
IEEE Transactions on Systems Man and CyberneticsScene Labeling by Relaxation Operations
1,401 Citations1976Azriel Rosenfeld, Robert A. Hummel +1 more
This paper formulates the ambiguity-reduction process in terms of iterated parallel operations (i.e., relaxation operations) performed on an array of object, identification data.
Information SciencesNetworks of constraints: Fundamental properties and applications to picture processing
1,248 Citations1974Ugo Montanari
Constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network, and this solution is proved exact in special cases, e.g., for tree-like and series-parallel networks and for classes of relations for which a distributive property holds.
Artificial IntelligenceIncreasing tree search efficiency for constraint satisfaction problems
1,114 Citations1980Robert M. Haralick, Gordon L. Elliott
Analytically and experimentally show that a lookahead procedure called forward checking which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.
DSpace@MIT (Massachusetts Institute of Technology)Generating Semantic Descriptions From Drawings of Scenes With Shadows
445 Citations1972David L. Waltz
This report reproduces a thesis of the same title submitted to the Department of Electrical Engineering, Massachusetts Institute of Technology, in partial fulfillment of the requirements for the degree of Doctor of Philosophy, September 1972.
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe Consistent Labeling Problem: Part I
287 Citations1979Robert M. Haralick, Linda G. Shapiro
It is shown that Latin square puzzles, finding N-ary relations, graph or auto-mata homomorphisms, graph colorings, as well as determining satisfiability of propositional logic statements and solving scene and edge labeling problems, are all special cases of the general consistent labeling problem.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Structural Model of Shape
103 Citations1980Linda G. Shapiro
Lecture notes in computer scienceComputer Vision Systems
64 Citations2001Schiele, Bernt, Sagerer, Gerhard
Information SciencesReduction operations for constraint satisfaction
51 Citations1978Robert M. Haralick, Larry S. Davis +2 more
The problem of labeling a set of units in such a way as to satisfy an order-N compatibility relation is discussed and shown to be NP-complete.
Elsevier eBooksSOME TECHNIQUES FOR RECOGNISING STRUCTURES IN PICTURES
41 Citations1972Harry G. Barrow, A.P. Ambler +1 more
The chapter discusses the idea of a finite relational structure, that is, a set of elements with given properties and relations among them, as a useful mathematical tool for describing pictures, and to describe general techniques for matching such structures against each other.
IEEE Transactions on Systems Man and CyberneticsArrangements, Homomorphisms, and Discrete Relaxation
33 Citations1978Robert M. Haralick, Jesse S. Kartus
It is shown how homomorphisms between arrangements, which are labeled N-ary relations, are the natural solutions to some problems requiring the integration of low-level and high-level information.