Conclusion on substructure matching

In this demo, we show an extension of geometric hashing based on frame features and show that it can be successfully applied to very different problems such as substructure matching of proteins and matching of medical images. The use of frames instead of just points allows to decrease the complexity from at least O(n3) for previous approaches to O(n2), and allows the algorithm to discard several false matches that could not be ruled out just with points. Moreover, it makes the algorithm robust with respect to parameter that tune the quality of the matches (which is the uncertainty that we fix on frames on input).

The drawback of this high selectivity of frames is that the uncertainty handling must be very precise. Several points could be modified in this algorithm to improve robustness and efficiency:

We are using an approximate error bound for the error on the invariants. A thorough probabilistic error scheme would enhance robustness but requires that we use the correct metric (and representation) on binary invariants of frames (which is known in this particular case). The problem is then to conceive an efficient indexing method for these objects in presence of measurement errors.
Our clustering algorithm on transformations is too simple and poorly efficient. We could improve here both the robustness and the efficiency.
Last but not least, the nearest neighbor search is done by verifying all frames that have a point distance above a given threshold (research done using kD trees). An algorithm working directly on frames should be more robust and efficient.

[ Back to substructure matching with frames ]

xpennec@sophia.inria.fr