用Randomized Hough Transform 及 Alpha shape 理論自影像中辨認直線及圓之研究

Abstract

影像分析(Image Analysis) 是從影像中提取資訊的各種技術。這些資訊可能會在往後的處理中扮演重要的角色。例如由2-D影像重建3-D模組時就必須有正確的image analysis的結果。影像分析的第一步工作通常是分割影像(Image Segmentation)。分割(segmentation)是將影像細分成個別的物件。通常，自動化的image segmentation是影像處理中最最困難的工作之一，而往往image segmentation在影像處理中決定image analysis的成敗。 Hough 轉換(Hough Transform)在image segmentation的領域中很重要的一項技術。因為Hough Transform具有強大的邊緣連接(edge linking)的能力。以及不易受雜點干擾的特性。因此Hough Transform演算法在image segmentation的領域中一直都被廣泛應用。 我們將介紹我們將會運用到的計算幾何的理論。包括Alpha shape 和Delaunay triangulation的理論。本文中我們將提出Alpha component base的Hough transform演算法應用於Hough Transformation。

Image Analysis is an important topic in image processing. And Hough transformation is an important technique in Image Analysis. In this paper, we present new Hough transformation algorithm. Different from the tradition Hough transformation, we apply the concept and technique in the computer geometry to Hough transformation. In our algorithm, we improve the “voting” algorithm of the Hough transformation by Alpha shape extraction. We propose this algorithm to detect lines and circles in images.