Part-in-whole 3D shape matching and docking

A new algorithmic framework is proposed to efficiently recognize instances of template shapes within target 3D models or scenes. The new framework provides an efficient solution of the part-in-whole matching problem and, with simple adaptations, it can also be exploited to quickly select sites in the target which properly fit with the template. Therefore, the method proposed potentially offers a new approach to all applications where complementarity has to be analysed quickly such as, for instance, docking. By assuming that the template is small when compared to the target, the proposed approach distinguishes from the previous literature because the part-in-whole matching is obtained by extracting offline only the shape descriptor of the template, while the description of the target is dynamically and adaptively extracted during the matching process. This novel framework, called the Fast Reject schema, exploits the incremental nature of a class of local shape descriptors to significantly reduce the part-in-whole matching time, without any expensive processing of the models for the extraction of the shape descriptors. The schema has been tested on three different descriptors and results are discussed in detail. Experiments show that the gain in computational performances does not compromise the accuracy of the matching results. An additional descriptor is introduced to compute parts of the target having a complementary shape with respect to the template. Results of such a shape complementarity detection are shown in domains such as cultural heritage and drug design.