Symmetry-Based Indexing of Image Databases
Journal of Visual Communication and Image RepresentationPublished 1 December 1998
Daniel Sharvit, Jacky C. P. Chan, Hüseyin Tek, Benjamin B. Kimia
Citations251
SJR quartileQ1
SJR score0.59
SNIP1.06
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.
Abstract
The use of shape as a cue for indexing into pictorial databases has been traditionally based on global invariant statistics and deformable templates, on the one hand, and local edge correlation on the other. This paper proposes an intermediate approach based on a characterization of the symmetry in edge maps. The use of symmetry matching as a joint correlation measure between pairs of edge elements further constrains the comparison of edge maps. In addition, a natural organization of groups of symmetry into a hierarchy leads to a graph-based representation of relational structure of components of shape that allows for deformations by changing attributes of this relational graph. A graduated assignment graph matching algorithm is used to match symmetry structure in images to stored prototypes or sketches. The results of matching sketches and grey-scale images against a small database consisting of a variety of fish, planes, tools, etc., are promising.
Keywords
Computer Science
Operations ResearchBranch-and-Bound Methods: A Survey
1,982 Citations1966Eugene L. Lawler, Derek Wood
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>QBIC project: querying images by content, using color, texture, and shape</title>
1,760 Citations1993Carlton W. Niblack, Ron Barber +7 more
The main algorithms for color texture, shape and sketch query that are presented, show example query results, and discuss future directions are presented.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA graduated assignment algorithm for graph matching
1,098 Citations1996Steven Gold, Anand Rangarajan
A graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise, and not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn the Foundations of Relaxation Labeling Processes
891 Citations1983Robert A. Hummel, Steven W. Zucker
It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality, and a procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting.
International Journal of Computer VisionShock Graphs and Shape Matching
762 Citations1999Kaleem Siddiqi, Ali Shokoufandeh +2 more
A novel tree matching algorithm is introduced which finds the best set of corresponding nodes between two shock trees in polynomial time and is demonstrated under articulation, occlusion, and moderate changes in viewpoint.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn eigendecomposition approach to weighted graph matching problems
718 Citations1988Shinji Umeyama
An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs and an analytic approach is used instead of a combinatorial or iterative approach to the optimum matching problem.
Biological CyberneticsOn the stability of the Travelling Salesman Problem algorithm of Hopfield and Tank
549 Citations1988Greg Wilson, G. S. Pawley
The application of the method of Hopfield and Tank to the Travelling Salesman Problem has been re-examined in an effort to find a procedure for scaling to system sizes of real interest, but no satisfactory refinement was found and the reasons for algorithm failure have been identified.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStructural Descriptions and Inexact Matching
542 Citations1981Linda G. Shapiro, Robert M. Haralick
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.
International Journal of Computer VisionShapes, shocks, and deformations I: The components of two-dimensional shape and the reaction-diffusion space
542 Citations1995Benjamin B. Kimia, Allen Tannenbaum +1 more
The principles are organized around two basic intuitions: first, if a boundary were changed only slightly, then, in general, its shape would change only slightly; and second, that not all contours are shapes, but rather only those that can enclose “physical” material.
IEEE Transactions on Pattern Analysis and Machine IntelligenceModal matching for correspondence and recognition
456 Citations1995Stan Sclaroff, Alex Pentland
Improved formulation of modal matching utilizes a new type of finite element formulation that allows for an object's eigenmodes to be computed directly from available image information, and is applicable to data of any dimensionality.
International Journal of Computer VisionFORMS: A flexible object recognition and modelling system
279 Citations1996Song-Chun Zhu, Alan Yuille
A model for generating the shapes of animate objects which gives a formalism for solving the inverse problem of object recognition and how such a representation scheme can be automatically learnt from examples is described.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA linear programming approach for the weighted graph matching problem
236 Citations1993H.A. Al-Mohamad, Salih O. Duffuaa
Experimental results showed that the LP approach is superior in matching graphs than both other methods.
IEEE Transactions on Systems Man and CyberneticsA graph distance measure for image analysis
186 Citations1984M. A. Eshera, King‐Sun Fu
A new, efficient approach for calculating a global distance measure between attributed relational graphs is proposed, and its applications in computer vision are discussed.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching
174 Citations1986M. A. Eshera, King‐Sun Fu
A shock grammar for recognition
160 Citations1996Kaleem Siddiqi, Benjamin B. Kimia
First, subpixel local detectors for finding and classifying shocks are developed to show that shock patterns are not arbitrary but obey the rules of a grammar, and in addition satisfy specific topological and geometric constraints.
Vision ResearchObject representation by cores: Identifying and representing primitive spatial regions
154 Citations1995Christina A. Burbeck, Stephen M. Pizer
A model of the spatial visual processes underlying the identification and representation of the shape of primitive spatial regions, which proposes that a region's boundaries are sensed at multiple scales by boundariness detectors that give graded responses, is proposed.
Lecture notes in computer scienceToward a computational theory of shape: An overview
148 Citations1990Benjamin B. Kimia, Allen Tannenbaum +1 more
A theory is proposed that unifies the competing elements of shape—parts and protrusions—and a framework for computing them reliably is developed, which has application in areas ranging from robotics to the psychology and physiology of form.
Neural NetworksThe invisible hand algorithm: Solving the assignment problem with statistical physics
147 Citations1994J.J. Kosowsky, Alan Yuille
A novel method is proposed for solving the assignment problem using techniques adapted from statistical physics to derive a convex effective energy function whose unique minimum corresponds to the optimal assignment.
Journal of Mathematical Analysis and ApplicationsOn the evolution of curves via a function of curvature. I. The classical case
146 Citations1992Benjamin B. Kimia, Allen Tannenbaum +1 more
This work considers the general problem of curve evolution as a function of its local geometry and proves an existence theorem for the classical solution and the main theorem rests on lemmas that bound the evolution of length, curvature, and how far the curve can travel.
Shock graphs and shape matching
134 Citations2002Kaleem Siddiqi, Ali Shokoufandeh +2 more
Computer Vision and Image UnderstandingExtraction of Shape Skeletons from Grayscale Images
105 Citations1997Zahir Tari, Jayant Shah +1 more
A new method based on diffusion to smooth out the noise and extract shape skeletons in a robust way and is applicable to shapes which may have junctions such as triple points.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSkeletonization via the realization of the fire front's propagation and extinction in digital binary shapes
100 Citations1989Yu Xia
A sequential method of skeletonization for digital binary images is proposed, realizes in a discrete plane prairie-fire propagation model, and verifies the memorized edge points and those marked only once are removed.
Pattern RecognitionDeformable prototypes for encoding shape categories in image databases
93 Citations1997Stan Sclaroff
The technique of {\em modal matching}, an information-preserving shape decomposition for matching, describing, and comparing shapes despite sensor variations and nonrigid deformations, is employed for shape comparison in 2-D image databases.
Neural ComputationLearning with Preknowledge: Clustering with Point and Graph Matching Distance Measures
69 Citations1996Steven Gold, Anand Rangarajan +1 more
The point-matching distance measure is approximately invariant under affine transformationstranslation, rotation, scale, and shearand permutations, and it operates between noisy images with missing and spurious points.
Neural ComputationConstrained Nets for Graph Matching and Other Quadratic Assignment Problems
69 Citations1991Petar Simić
The main point of the elastic net algorithm is seen to be in the way one deals with the constraints when evaluating the effective cost function (free energy in the thermodynamic analogy), and not in its geometric foundation emphasized originally by Durbin and Willshaw.
Recognition and semi-differential invariants
65 Citations2002Luc Van Gool, P. Kempenaers +1 more
The method for the derivation of such invariants, based on Lie group theory and applicable to a wide spectrum of transformation groups, is described and invariant curve parameterizations are developed for affine and projective transformations.
Determining the similarity of deformable shapes
55 Citations2002Ronen Basri, Luís Augusto Nagasaki Costa +2 more
This paper identifies a number of possibly desirable properties of a shape similarity method, and determines the extent to which these properties can be captured by approaches that compare local properties of the contours of the shapes, through elastic matching.
Visual image retrieval by elastic deformation of object sketches
49 Citations2002Alberto Del Bimbo, Pietro Pala +1 more
In this method, the shape is drawn by the user, and instantiated as an elastic template, and the template is then deformed to match as well as possible the objects in the images.
Image retrieval by elastic matching of shapes and image patterns
33 Citations2002Alberto Del Bimbo, Pietro Pala +1 more
A system for interactive image database retrieval, based on elastic template matching, where the template can be both a 1D template modeling the contour of an object, and a 2D template modeled a part of an image with a significant grey-level pattern.
Shocks from images: propagation of orientation elements
30 Citations2002Hüseyin Tek, P.A. Stoll +1 more
This paper shows that an additional labeling of shocks based on whether the colliding wavefronts carry true orientation information allows a division of shocks into three sets: regular shocks are the partial shocks of partial contours as they remain invariant to the completion of the contour; semi-degenerate and degenerate shocks depict potential parts and gaps.
Content-based image retrieval: color and edges
22 Citations1995Robert S. Gray
A simple content-based system that retrieves color images on the basis of their color distributions and edge characteristics and uses two retrieval techniques that have been described in the literature -- i.e. histogram intersection to compare color distribution and sketch comparison to compare edge characteristics.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Shock-based approach for indexing of image databases using shape</title>
19 Citations1997Benjamin B. Kimia, Jackie Chan +4 more
A symmetry- based and contour-based representation of shape is presented, a propagation-based method to extract partial symmetries from real images, and the generation of user-sketched queries using intuitive shape deformations are presented.
Image and Vision ComputingIndustrial part recognition using a component-index
17 Citations1990R. Mehrotra, F.K. Kung +1 more
A new data-driven technique for part recognition that models an object or a scene as a composition of several components and efficiently identifies a component of the unanalyzed portion of the scene using a k-d tree-based component-index.
A Lagrangian relaxation network for graph matching
13 Citations2002Anand Rangarajan, Eric Mjolsness
A deterministic annealing approach is adopted which is similar to a Lagrangian decomposition approach in that the row and column constraints of the permutation matrix are satisfied separately and Lagrange multipliers are used to equate the two "solutions".
Interactive shape modeling
2 Citations2002Zhibin Lei, David B. Cooper
A family of 2D curves for indexing into an image database, and an algorithm for generating a representation which passes within E of a set of control points specified by the user, are introduced.