Abstract
This paper reformulates the theory of graph mining on the technical basis of graph matching, and extends its scope of applications to computer vision. Given a set of attributed relational graphs (ARGs), we propose to use a hierarchical And-Or Graph (AoG) to model the pattern of maximal-size common subgraphs embedded in the ARGs, and we develop a general method to mine the AoG model from the unlabeled ARGs. This method provides a general solution to the problem of mining hierarchical models from unannotated visual data without exhaustive search of objects. We apply our method to RGB/RGB-D images and videos to demonstrate its generality and the wide range of applicability. The code will be available at https://sites.google.com/site/quanshizhang/mining-and-or-graphs.
Introduction
Traditional graph mining focuses on identifying frequent subgraphs within databases of labeled graphs, such as molecular structures. However, extending this to computer vision presents significant challenges. Visual data is inherently noisy; objects exhibit variations in pose, texture, and occlusion. Furthermore, unlike chemical atoms, visual primitives (nodes) lack pre-defined labels, making it unclear which features constitute specific object parts.
Existing computer vision approaches often rely on exhaustive searches or extensive manual annotations. This research proposes a general, unsupervised framework to discover the hierarchical "grammar" of objects—their constituent parts and structural variations—directly from unannotated visual data, including RGB, RGB-D, and video.
Methodology: Mining Hierarchical And-Or Graphs
The proposed method represents visual data as Attributed Relational Graphs (ARGs). In an ARG, nodes correspond to local features (e.g., line segments, SIFT points), and edges represent spatial relationships between them. To capture the complex structure of objects, the authors utilize a hierarchical And-Or Graph (AoG) model:
- AND Nodes: Represent the composition of an object from its parts (e.g., a "chair" composed of a "back," "seat," and "legs").
- OR Nodes: Account for structural variability or alternative appearances of a part (e.g., different leg styles).
- Terminal Nodes: Represent the concrete local patterns observed in the images.
The mining process follows a six-step EM-style iterative flowchart:
- Graph Matching: Align the current model to both positive and negative image samples.
- Attribute Estimation: Update node features based on successful matches.
- Node Elimination: Prune nodes that fail to distinguish the object from the background.
- Node Discovery: Automatically identify new parts (OR nodes) consistently present in the data.
- Terminal Determination: Cluster local patterns to define the "OR" branches.
- Parameter Training: Use a linear SVM to weight the importance of various parts and relations.
Experimental Datasets and Applications
The generality of the AoG mining approach was validated across diverse data types:
- Kinect RGB-D Dataset: 5 categories using 3D line segments.
- ETHZ Shape Class Dataset: 5 categories using edge segments in RGB images.
- SIVAL & PASCAL07-6x2: 37 categories using learned middle-level patches.
- Internet Videos: 3 sequences (cheetah, swimming girls, frog) using SIFT points to track deformable objects.
Key Insights
- Mining as Inference: The authors reframe graph mining: while graph matching finds a model in an image, graph mining finds the model that best explains a collection of images.
- Handling Variation with OR Nodes: By explicitly incorporating OR nodes, the model handles intra-category variation, learning multiple valid appearances for object parts rather than relying on a single template.
- Discriminative Mining: The algorithm prioritizes patterns that appear in positive samples but not in negative (background) samples, ensuring the model captures relevant object features rather than common background elements like the sky.
- Efficiency: By "growing" the graph iteratively rather than enumerating all possible subgraphs, the method avoids the computational explosion of exhaustive searches.
Results and Conclusion
The proposed method consistently outperformed state-of-the-art baselines in both graph matching (part localization) and object discovery (clustering purity). In RGB and RGB-D experiments, the mined AoGs achieved significantly lower Error Matching Rates (EMR) compared to methods like "Soft Attributed Patterns" (SAP). The method also demonstrated superior Average Precision (AP) in object detection, particularly as the complexity of the pattern increased.
While highly effective, the authors suggest that performance could be further enhanced by replacing hand-crafted features (SIFT, HOG) with deep CNN features. Additionally, the current process requires an initial "seed" template to initiate the mining cycle. Overall, this work provides a robust foundation for unsupervised object discovery through the lens of hierarchical graph mining.
Summary updated