Fast geometric trim fitting using partial incremental sorting and accumulation
This work addresses computational bottlenecks in geometric computer vision, offering incremental improvements for specific outlier-affected regression tasks.
The paper tackles the problem of improving efficiency in robust trim-fitting for geometric regression with outliers by introducing a method based on partial incremental sorting and accumulation, achieving highly efficient and reliable results in camera resectioning applications.
We present an algorithmic contribution to improve the efficiency of robust trim-fitting in outlier affected geometric regression problems. The method heavily relies on the quick sort algorithm, and we present two important insights. First, partial sorting is sufficient for the incremental calculation of the x-th percentile value. Second, the normal equations in linear fitting problems may be updated incrementally by logging swap operations across the x-th percentile boundary during sorting. Besides linear fitting problems, we demonstrate how the technique can be additionally applied to closed-form, non-linear energy minimization problems, thus enabling efficient trim fitting under geometrically optimal objectives. We apply our method to two distinct camera resectioning algorithms, and demonstrate highly efficient and reliable, geometric trim fitting.