Computational Efficientcy of Random Sampling Operators in Vision Charles V. Stewart computer vision random sampling robust statistics This paper presents two techniques for improving the computational efficiency of a class of random sampling operators for robust computer vision which fit parametrized surface patches in overlapping regions (windows) throughout an image. The two techniques are: (1) exploiting overlap between adjacent windows to eliminate redundant computation, and (2) determining early in the evaluation of a fit in a window when it can not be better than the best fit tested thus far in the window. Using these techniques, efficiency improvements are seen both in the expected computational complexity and in experimental implementations of the algorithms. The improved algorithms may be used in several ways: (1) to improve the execution time of a given random sampling application, (2) to improve the accuracy of the resulting fits for the same computational cost by increasing the size of the windows, decreasing the spacing between windows, or increasing the number of random samples considered per window, or (3) to improve the chances of avoiding outliers for the same computational cost by considering more samples in each window. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 02/24/1993 cs-93-02
Computational Efficientcy of Random Sampling Operators in Vision
Charles V. Stewart
computer vision
random sampling
robust statistics
This paper presents two techniques for improving the computational efficiency of a class of random sampling operators for robust computer vision which fit parametrized surface patches in overlapping regions (windows) throughout an image. The two techniques are: (1) exploiting overlap between adjacent windows to eliminate redundant computation, and (2) determining early in the evaluation of a fit in a window when it can not be better than the best fit tested thus far in the window. Using these techniques, efficiency improvements are seen both in the expected computational complexity and in experimental implementations of the algorithms. The improved algorithms may be used in several ways: (1) to improve the execution time of a given random sampling application, (2) to improve the accuracy of the resulting fits for the same computational cost by increasing the size of the windows, decreasing the spacing between windows, or increasing the number of random samples considered per window, or (3) to improve the chances of avoiding outliers for the same computational cost by considering more samples in each window.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
02/24/1993
cs-93-02