随机Hough变换与Tabu搜索算法在基元提取中的比较

Ｈｏｕｇｈ变换（ＨＴ）是目前应用最广的几何基元提取方法，其基本思想在于通过证据积累来提取基元。最近不少人又提出了通过代价函数的全局优化来提取几何基元的思想。随机Ｈｏｕｇｈ变换（ＲＨＴ）和Ｔａｂｕ搜索（ＴＳ）分别是Ｈｏｕｇｈ变换和优化方法中的佼佼者。ＲＨＴ和ＴＳ分别基于不同的策略，两种方法的相互比较在许多文献中已有提及，但目前尚无较完整的理论分析和系统的比较。本文在提取单个基元所需对最小点集的采样次

A COMPARISON BETWEEN THE RANDOMIZED HOUGH TRANSFORMATION AND THE TABU SEARCH ALGORITHM IN GEOMETRIC PRIMITIVE EXTRACTION

The Hough transformation has been a widely used in geometric primitive extraction.It relies basically on an evidence accumulation process.Recently a new family of techniques,namely the optimization based one was proposed which resorts mainly to repeated cost function evaluation process.The randomized Hough transformation and the Tabu search algorithm are the two good representatives of the the Hough family and optimization based family respectively.Although some piecemeal works exist,a systematic comparison between these two families of techniques is unavailable in the literature.In this paper,based on a reasonable criterion,namely the expected number of random samples of minimum subset for a single successful primitive extraction,the performance of between the randomized Hough transform and the Tabu search algorithm is compared.The paper shows that the randomized Hough transformation generally outperforms the Tabu search algorithm.In particular,based on a large number of simulations and experiments with real images,it shows that with a comparable performance,the randomized Hough transformation is about twice as fast as the Tabu search algorithm for both line extraction and circle extraction.