Video indexing and similarity retrieval by largest common subgraph detection using decision trees
✍ Scribed by Kim Shearer; Horst Bunke; Svetha Venkatesh
- Book ID
- 104161367
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 349 KB
- Volume
- 34
- Category
- Article
- ISSN
- 0031-3203
No coin nor oath required. For personal study only.
✦ Synopsis
While the largest common subgraph (LCSG) between a query and a database of models can provide an elegant and intuitive measure of similarity for many applications, it is computationally expensive to compute. Recently developed algorithms for subgraph isomorphism detection take advantage of prior knowledge of a database of models to improve the speed of on-line matching. This paper presents a new algorithm based on similar principles to solve the largest common subgraph problem. The new algorithm signi"cantly reduces the computational complexity of detection of the LCSG between a known database of models, and a query given on-line.