O(n 3logn) Time Complexity for the Optimal Consensus Set Computation for 4-Connected Digital Circles
O(n 3logn) Time Complexity for the Optimal Consensus Set Computation for 4-Connected Digital Circles
复制标题
4连通数字圈最优共识集计算的时间复杂度为O(n 3logn)
DOI：
10.1007/978-3-642-37067-0_21
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Eric Andres
中科院分区：
文献类型：
--
作者：
Gaëlle Largeteau;R. Zrour;Eric Andres
本文提出了一种在噪声存在的情况下，通过最大化内点的数量，即最优一致集，同时固定厚度，将4-连通数字圆拟合到2D图像中的给定点集的方法。我们的方法具有O（n ~ 3logn）的时间复杂度和O（n）的空间复杂度，n为点数，这比以前已知的方法低，同时仍然保证最优解。
This paper presents a method for fitting 4-connected digital circles to a given set of points in 2D images in the presence of noise by maximizing the number of inliers, namely the optimal consensus set, while fixing the thickness. Our approach has aO(n3logn) time complexity andO(n) space complexity,nbeing the number of points, which is lower than previous known methods while still guaranteeing optimal solution(s).