A concave optimization algorithm for matching partially overlapping point sets. (July 2020)

• Record Type: Journal Article
• Authors: Lian, Wei; Zhang, Lei
• Is Part Of: Pattern recognition. Volume 103(2020:Jul.)
• Publication Date: 2020-07
• Subjects: Concave optimization -- Point matching -- Branch-and-bound -- Linear assignment -- Global optimization; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107322
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: All the transformation parameters including those of translation are regularized in our CVPR paper, causing the method not able to handle un- known arbitrary translations. To address this issue, we show that under a mild condition, the objective function of RPM is strictly convex quadratic w.r.t. translation. Thus, translation can first be eliminated via minimization. Then, we only need to enforce regularization on the non-translational part of the transformation. This enables our algorithm to handle unknown arbitrary translations and more applicable to practical problems. Our CVPR paper imposes regularization on transformation which causes the transformation solution close to the predefined value. To address this issue, we propose a new formulation targeted at 2D/3D similarity registration problems, where regularization on transformation is abandoned in favor of constraints on transformation. This results in an algorithm capable of handling unknown arbitrary similarity transformations. We conducted extensive experiments on 2D/3D synthetic and real data to test the performance ofthe proposed method. The experimental results demonstrate much better robustness of the proposed method over state-of-the-art methods. Abstract: Matching partially overlapping point sets is a challenging problem in computer vision. To achieve this goal, we model point matching as a mixed linear assignment - least square problem. By eliminating the transformation variable, we reduce the minimization problem to a concave optimization problem with the property that the objective function can be converted into a form with few nonlinear terms. We then use a heuristic variant of the branch-and-bound algorithm for optimization where convergence of the upper bound is used as the stopping criterion. We also propose a new lower bounding scheme which involves solving a k-cardinality linear assignment problem. Two cases of transformations, transformation output being linear with respect to parameters and 2D/3D similarity transformations, are discussed, resulting in ability to handle unknown arbitrary translation and similarity, respectively. Experimental results demonstrate better robustness of the algorithm over state-of-the-art methods.