GPU-Based Computation of 2D Least Median of Squares with Applications to Fast and Robust Line Detection
This work addresses the efficiency bottleneck in robust regression and computer vision for applications like image processing, though it is incremental as it adapts existing methods to GPU acceleration.
The authors tackled the high computational complexity of 2D Least Median of Squares (LMS) estimation by developing a fast, parallel GPU-based algorithm, which significantly outperformed the optimal single-threaded CPU algorithm and improved line detection in noisy images compared to standard Hough Transform methods.
The 2D Least Median of Squares (LMS) is a popular tool in robust regression because of its high breakdown point: up to half of the input data can be contaminated with outliers without affecting the accuracy of the LMS estimator. The complexity of 2D LMS estimation has been shown to be $Ω(n^2)$ where $n$ is the total number of points. This high theoretical complexity along with the availability of graphics processing units (GPU) motivates the development of a fast, parallel, GPU-based algorithm for LMS computation. We present a CUDA based algorithm for LMS computation and show it to be much faster than the optimal state of the art single threaded CPU algorithm. We begin by describing the proposed method and analyzing its performance. We then demonstrate how it can be used to modify the well-known Hough Transform (HT) in order to efficiently detect image lines in noisy images. Our method is compared with standard HT-based line detection methods and shown to overcome their shortcomings in terms of both efficiency and accuracy.