Consensus Score Based Outlier Detection Using Extended Hough Transform

In this paper, a novel and efficient outlier detection method is introduced. This method is simple and elegant and it works by calculating a consensus score for each data point to determine the level of consensus of that point with respect to the other data points in a group. A low consensus score means that the corresponding data point has little in common with other data points, and thus is considered to be an outlier. The consensus score is calculated using an algorithm that is derived from an extended version of the basic Hough Transform algorithm. The proposed method is very efficient in that it requires much less computation compared with many other popular ourtlier detection methods. To be specific, the amount of calculation required by the proposed method has a linear relation to the number of data points, whereas most other methods assume an exponential relation in this regard. An analytical and side-by-side comparison in terms of computation complexity and computation time are conducted against a popular RANSAC-based outlier detection algorithm. The effectiveness of the proposed method is first demonstrated for cases where two-dimensional data and linear model are involved; then, extension to data with more complex data type and model is discussed.