- 學位論文
隨機橢圓偵測法的比較
A Comparison of Randomized Sampling Ellipse Detection Algorithm
摘要
影像處理和圖形識別常常需要處理曲線偵測的問題，而霍夫轉換 (Hough Transform )被認為是目前標準的處理法。但是橢圓偵測上霍夫轉換所需要的空間複雜度是O(n5)，因此在記憶體受限制的應用中，隨機曲線偵測法是一種可行的替代方案。在目前文獻中已存在許多隨機曲線偵測法，但是對於這些隨機曲線偵測法一直缺乏一個有系統化的比較，以作為不同的應用中選擇適當偵測器的參考。本論文提出了一個橢圓偵測器的架構，在這個架構下橢圓偵測器被分為六個元件，分別負責取樣、排除錯誤的取樣、計算橢圓方程式、延遲驗證橢圓是否存在、驗證橢圓是否存在於圖片和將點自圖片中移除。在該架構下我們將實作並比較RANSAC、隨機霍夫轉換 (Randomized Hough Transform)、Pascal RANSAC、Pencil of Ellipse RANSAC四種隨機橢圓偵測法。此外我們也將圖片依照noise rate、drop rate和橢圓的數目加以分成三類，並設計了三種公平的實驗測試這些圖片。這三種實驗中第一種是給予充分的次數、第二種是給予比較在至少取樣成功一次的機率相同的次數，第三種是給予固定的時間，然後分別對執行時間、假警報跟遺失橢圓數做比較。
並列摘要
Curve detection is a common problem in many computer vision and image processing applications. A standard algorithm for detection is the Hough transform. However, in ellipse detection the Hough transform has space complexity of O(n^5). In applications with limited memory resource, randomized detection algorithms become attractive alternatives. Since there are a number of randomized methods to choose from, a framework for systematically comparing can be valuable in helping to decide the algorithms to use. In this thesis, we propose an architecture model for ellipse detection algorithms. The architecture consists of six components, including sampling strategy, sampling constraint, curve computation, delay strategy, testing and removal. We have successfully implemented four algorithms under the architecture, including standard RANSAC, Pascal RANSAC, RHT, and pencil of ellipses. Comparison results are reported in this thesis.