We are very excited to join forces with MLCommons and OctoML.ai! Contact Grigori Fursin for more details!

Bi-directional Shape Correspondences (BSC): A Novel Technique for 2-d Shape Warping in Quadratic Time?

lib:843cab51a76c9497 (v1.0.0)

Authors: Abdulrahman Oladipupo Ibraheem
ArXiv: 1412.6759
Document:  PDF  DOI 
Abstract URL: http://arxiv.org/abs/1412.6759v1

We propose Bidirectional Shape Correspondence (BSC) as a possible improvement on the famous shape contexts (SC) framework. Our proposals derive from the observation that the SC framework enforces a one-to-one correspondence between sample points, and that this leads to two possible drawbacks. First, this denies the framework the opportunity to effect advantageous many-to-many matching between points on the two shapes being compared. Second, this calls for the Hungarian algorithm which unfortunately usurps cubic time. While the dynamic-space-warping dynamic programming algorithm has provided a standard solution to the first problem above, it demands quintic time for general multi-contour shapes, and w times quadratic time for the special case of single-contour shapes, even after an heuristic search window of width w has been chosen. Therefore, in this work, we propose a simple method for computing "many-to-many" correspondences for the class of all 2-d shapes in quadratic time. Our approach is to explicitly let each point on the first shape choose a best match on the second shape, and vice versa. Along the way, we also propose the use of data-clustering techniques for dealing with the outliers problem, and, from another viewpoint, it turns out that this clustering can be seen as an autonomous, rather than pre-computed, sampling of shape boundary.

Relevant initiatives  

Related knowledge about this paper Reproduced results (crowd-benchmarking and competitions) Artifact and reproducibility checklists Common formats for research projects and shared artifacts Reproducibility initiatives


Please log in to add your comments!
If you notice any inapropriate content that should not be here, please report us as soon as possible and we will try to remove it within 48 hours!