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
- 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 ]