臺灣博碩士論文加值系統

在影像中經常出現線、圓及橢圓。所以在影像處理中，偵測這三種形狀是很重要的。而偵測這些形狀所最常使用的方法為哈克轉換 (HT) 及以 HT變化而來的相關方法。本質上 HT是一個投票程序。票是累積在一個用來代表形狀的參數空間的累積器上。當累積器中的某一單元有足夠的投票數時，我們便可擷取出所要找的形狀。基本上，當要偵測由n個參數所表示的形狀時，使用 HT測該形狀需要 n 維記憶體陣列的累積器。所以哈克轉換的主要缺點是需要花用來表示多維參數空間的大量記憶體空間及執行投票時所需的大量時間。特別地，在 Risse 的研究中指出，當進行哈克轉換時，參數空間中許多地方是多餘不會被使用到的。這種較低的記憶空間使用率也造成了許多記憶空間的浪費。
Xu 等人 曾提出一個隨機式哈克轉換 (RHT) 來改進 HT。當我們要偵測有n個參數的形狀時，RHT每次取出n 個邊點像素並求出通過這 n 個邊點形狀所對應的該 n 個參數的實際值，然後依該值在參數空間中投票。由於 RHT 仍是一種 HT 式的方法，所以施行 RHT 時，仍需花不少記憶空間及計算時間。
本論文首先提出一個新的 affine 轉換為基礎的測線 HT。它將線的斜線-截距參數空間轉換到一個可100％被使用的記憶空間。此外，本論文也提出該方法的三個有效的執行方式。之後，本論文還提出了用來測線、測圓及測橢圓的隨機演算法。這些隨機演算法並不需要在累積器所表示的參數空間上投票，而這也因此可達成於偵測這些形狀時的記憶空間及計算時間上較節省的效果。本論文所進行的一些實驗結果也證實了理論上的分析。

Since lines, circles, and ellipses occur in the image frequently, detecting the three types of shapes is very important in image processing. The commonly used method
for detecting those shapes are the Hough transform (HT) and its variants. The HT is essentially a voting process. These
votes are accumulated in an accumulator which represents the
parameter space for the shape. When one cell in the accumulator
has a satisfactory score, we can retrieve the desired shape.
Basically, to detect a shape of n parameters requires an
n-dimensional array for the accumulator. Therefore, the
principal disadvantage of the HT is that it needs a huge amount of storage to represent the multidimensional parameter space and some amount of executing time to carry out the voting process.
Specifically, Risse points out that there are much redundant memory in the parameter space. The low memory utilization of HT leads to waste much memory space.
In order to reduce the large storage and heavy computation needed
in the HT, Xu et al. proposed a randomized Hough transform (RHT) which randomly selects n edge pixels for detecting the shape of n parameters each time and maps them into one point in the parameter space. But, the
RHT still needs some amount of storage and executing time due to
the disadvantage existing in the HT-based method.
In this thesis, a new affine-transform based HT for detecting
lines is presented first. The proposed method transfers the
slope--intercept parameter space into a fully (100%) utilized
memory space. In addition, three efficient implementations are
presented. Then some efficient randomized algorithms for detecting
lines, circles, and ellipses are presented. These randomized
algorithms do not need to vote in the accumulator and it leads to
memory- and computation-saving effects. Experimental results
confirm the theoretical analysis.

Chapter 1. Introduction 1
1.1. Background 1
1.2. Motivations and purposes2
1.3. Organization of the thesis3
Chapter 2. Memory-Saving Hough Transform for Detecting Lines Based on Affine Transformation5
2.1. The slope-intercept parameter space and
memory utilization5
2.2. The affine transformation to reach 100%
memory utilization9
2.3. Three implementations12
2.4. Experimentations and comparison19
Chapter 3. Fast Randomized Algorithm for Detecting Lines 25
3.1. Background25
3.2. The lines detection randomized algorithm27
3.2.1. The basic idea27
3.2.2. Determining the candidate line28
3.2.3. Determining the true line32
3.2.4. The randomized algorithm33
3.2.5. Two remarks about the algorithm34
3.3. Experimentations and comparison35
Chapter 4. Fast Randomized Algorithm for Detecting Circles 41
4.1. Preliminaries41
4.2. The circles detection randomized algorithm42
4.2.1. The basic idea42
4.2.2. Determining the candidate circle43
4.2.3. Determining the true circle47
4.2.4. The randomized algorithm48
4.3. Experimentations and comparison49
4.4. Discussion59
Chapter 5. Fast Randomized Algorithm for Detecting Ellipses64
5.1. Preliminaries64
5.2. The ellipses detection randomized algorithm66
5.2.1. The basic idea66
5.2.2. Finding the center of the ellipse69
5.2.3. Determining the remaining three parameters of
the ellipse70
5.2.4. Determining the candidate ellipse71
5.2.5. Determining the true ellipse72
5.2.6. The randomized algorithm74
5.3. Experimentations and comparison75
Chapter 6. Conclusions and future works80
References82

D. H. Ballard, ``Generalizing the Hough transform to detect arbitrary
shapes,'' Pattern Recognition, 13(2), pp. 111-122, 1981.
D. Ben--Tzvi and M. B. Sandler, ``A combinatorial Hough transform,''
Pattern Recognition Letters, 11(3), pp. 167--174, 1990.
J. R. Bergen and H. Shvaytser, ``A probabilistic algorithm for
computing Hough transforms,'' Journal of Algorithms, 12(4), pp.
639--656, 1991.
H. P. Biland, ``The recognition and volumetric description of
three--dimensional polyhedral scenes in analysis of Hough--space
structures,'' Ph.D. thesis. Swiss Federal Institute of Technology,
Zurich, ETH Zurich, 1987.
C. M. Brown, ``Inherent bias and noise in the Hough transform,'' IEEE
Transactions on Pattern Analysis and Machine Intelligence, 5(5), pp.
493--505, 1983.
T. C. Chen and K. L. Chung, ``A new randomized algorithm for
detecting lines,''
to appear in Real--Time Imaging.
T. C. Chen and K. L. Chung, ``A randomized algorithm for detecting
circles,'' The 13th IPPR Conference on Computer Vision, Graphics and
Image Processing, R. O. C., August 20--22, Vol. 2, pp. 118--124,
2000.
T. C. Chen and K. L. Chung, ``An efficient randomized algorithm for
detecting circles,'' to appear in Computer Vision and Image
Understanding.
T. C. Chen and K. L. Chung, ``A novel and efficient randomized
algorithm for detecting ellipses,'' submitted.
K. L. Chung, W. M. Yan, and T. C. Chen, ``Affine
transformation--based Hough transform for detecting lines,''
submitted.
M. Cohen and G. T. Toussaint, ``On the detection of structures in
noisy pictures,'' Pattern Recognition 9, pp. 95--98, 1977.
P. E. Danielsson and O. Seger, ``Generalized and separable Sobel
operators,'' Machine Vision for Three--Dimensional Scenes, edited by
H. Freeman, Academic Press, Boston, pp. 347--379, 1990.
E. R. Davies, ``Finding ellipses using the generalized Hough
transform,'' Pattern Recognition Letters, 9, pp. 87--96, 1989.
E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities,
Academic Press, London, 1990.
R. O. Duda and P. E. Hart, ``Use of the Hough transformation to
detect lines and curves in pictures,'' Commun. ACM, 15(1), pp.
11--15, 1972.
M. A. Fischler and R. C. Bolles, ``Random sample consensus: A
paradigm for model fitting with applications to image analysis and
automated cartography,'' Commun. ACM, 24(6), pp. 381--395, 1981.
M. A. Fischler and O. Firschein, Intelligence: The Eye, the Brain,
and the Computer, Addison Wesley, pp. 279--280, 1987.
M. A. Fischler and R. Firschen,``Parallel guessing: A strategy for
high-speed computation,'' Pattern Recognition, 20(2), pp. 257--263,
1987.
G. Gerig and F. Klein, ``Fast contour identification through
efficient Hough transform and simplified interpretation strategy,''
Proceedings of the International Joint Conference on Pattern
Recognition, pp. 498--500, 1986.
G. Gerig, ``Linking image--space and accumulator space: A new
approach for object--recognition,'' Proceedings of the International
Joint Conference on Computer Vision, pp. 112--117, 1987.
R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison
Wesley, New York, 1992. pp. 414--423,
W. E. L. Grimson and D. P. Huttenlocher, ``On the sensitivity of the
Hough transform for object recognition,'' IEEE Transactions on
Pattern Analysis and Machine Intelligence, 12(3), pp. 255--274,
1990.
C. T. Ho and L. H. Chen, ``A fast ellipse/circle detector using
geometric symmetry,'' Pattern Recognition, 28(1), pp. 117--124,
1995.
C. T. Ho and L. H. Chen, ``A high-speed algorithm for elliptical
object detection,'' IEEE Transactions on Image Processing, 5(3), pp.
547--550, 1996.
P. V. C. Hough, ``Method and means for recognizing complex patterns,''
U.S. Patent 3,069,654, Dec. 18, 1962.
D. J. Hunt, L. W. Nolte, A. R. Reibman, and W. H. Ruedger, ``Hough
transform and signal detection theory performance for images with
additive noise,'' Computer Vision Graphics Image Processing, 52, pp.
386--401, 1990.
J. Illingworth and J. Kittler, ``The adaptive Hough transform,'' IEEE
Transactions on Pattern Analysis and Machine Intelligence, 9(5),
pp.690--698, 1987.
J. Illingworth and J. Kittler, ``Survey: A survey of the Hough
Transform,'' Computer Vision, Graphics, and Image Processing, 44,
pp. 87--116, 1988.
D. Ioannou, W. Huda, and A. F. Laine, ``Circle recognition through a
2D Hough transform and radius histogramming,'' Image and Vision
Computing, 17, pp. 15-26, 1999
H. Kalviainen and P. Hirvonen, ``An extension to the randomized Hough
transform exploiting connectivity,'' Pattern Recognition Letters,
18(1), pp. 77-85, 1997.
H. Kalviainen, P. Hirvonen, L. Xu, and E. Oja, ``Probabilistic and
nonprobabilistic Hough transforms: Overview and comparison,'' Image
and Vision Computing, 13(4), pp. 239-252, 1995.
A. A. Kassim, T. Tan, and K. H. Tan, ``A comparative study of
efficient generalised Hough transform techniques,'' Image and
Vision Computing, 17, pp. 737--748, 1999.
C. Kimme, D. Ballard, and J. Sklansky , ``Finding circles by an array
of accumulators,'' Communication of the ACM, 18( 2), pp. 120--122,
1975.
N. Kiryati and A. M. Bruckstein, ``Antialiasing the Hough
transform,'' CVGIP: Graphical models Image Processing, 53(3), pp.
213--222, 1991.
N. Kiryati, Y. Eldar, and A. M. Bruckstein, ``A probabilistic Hough
Transform,'' Pattern Recognition 24(4), pp. 303--316, 1991.
Z. Kulpa, ``On the properties of discrete circles, rings, and
disks,'' Computer Graphics and Image Processing, 10, pp. 348--365,
1979.
V. Kyrki and H. Kalviainen, ``Combination of local and global line
extraction,'' Real--Time Imaging, 6, pp. 79-91, 2000.
V. F. Leavers, ``The dynamic generalized Hough transform: Its
relationship to the propabilistic Hough transforms and an application
to the concurrent detection of circles and ellipses,'' CVGIP: Image
Understanding, 56(3), pp. 381--398, 1992.
V. F. Leavers, ``Survey: Which Hough Transform,'' CVGIP: Image
Understanding, 58(2), pp. 250--264, 1993.
H. Li, M.A. Lavin, and R. J. Le Master, ``Fast Hough transform: A
hierarchical approach,'' Computer Vision, Graphics, and Image
Processing, 36, pp. 139--161, 1986.
P. Liang, ``A new and efficient transform for curve detection,''
Journal of Robotic Systems, 8(6), pp. 841--847, 1991.
R. A. McLaughlin, ``Randomized Hough transform: Better ellipse
detection,'' IEEE TENCON. Digital Signal Processing Applications,
1, pp. 409--414, 1996.
R. A. McLaughlin, ``Randomized Hough transform: Improved ellipse
detection with comparision,'' Pattern Recognition Letters, 19, pp.
299--305, 1998.
C. F. Olson, ``Constrained Hough transforms for curve detection,''
Computer Vision and Image Understanding, 58(3), pp.
329--345, 1999.
P. L. Palmer, M. Petrou, and J. Kittler, ``A Hough transform
algorithm with a 2d hypothesis testing kernel,'' CVGIP: Image
Understanding, 58, pp. 221--234, 1993
J. Princen, J. Illingworth, and J. Kittler, ``A Hierarchical approach
to line extraction based on the Hough transform,'' Computer Vision,
Graphics and Image Processing, 52(1), pp. 57--77, 1990.
J. Princen, J. Illingworth, and J. Kittler, ``A formal definition of
the Hough transform: Properties and relationships,'' Journal of
Mathematical Imaging and Vision, 1, pp. 153--168, 1992.
J. Princen, J. Illingworth, and J. Kittler, ``Hypothesis testing: A
framework for analyzing and optimizing Hough transform Preformance,''
IEEE Transactions on Pattern Analysis and Machine Intelligence
16(4), pp. 329--341, 1994.
T. Risse, ``Hough transform for line recognition: Complexity of
evidence accumulation and cluster detection,'' Computer Vision
Graphics Image Processing, 46, pp. 327--345, 1989.
A. Rosenfeld, Picture Processing by Computer, Academic Press, San
Diego, 1969.
G. Roth and M. D. Levine, ``Extracting geometric primitives,'' CVGIP:
Image Understanding, 58(1), pp. 1--22, 1993.
G. G. Roussas, A first course in mathematical statistics, Addison
Wesley, New York, 1983.
S. D. Shapiro, ``Transformations for the computer detection of curves
in noisy pictures,'' Computer Graphics Image Processing, 4, pp.
328--338, 1975.
S. D. Shapiro, ``Feature space transforms for curve detection,''
Pattern Recognition, 10, pp. 129--143, 1978.
S. D. Shapiro, ``Properties of transforms for the detection of curves
in noisy pictures,'' Computer Graphics Image Processing, 8, pp.
219--236, 1978.
S. D. Shapiro, ``Generalization of the Hough transform for curve
detection in noisy digital images,'' Proceedings of the
International Joint Conference on Pattern Recognition, pp. 710--714,
1978.
S. D. Shapiro and A. Iannino, ``Geometric constructions for
predicting Hough transform performance,'' IEEE Transactions on
Pattern Analysis and Machine Intelligence, 1(3), pp. 310--317, 1979.
J. Sklansky, ``On the Hough technique for curve detection,'' IEEE
Transactions on Computers, 27(10), pp. 923--926, 1978.
M. Soffer and N. Kiryati, ``Guaranteed convergence of the Hough
transform,'' Vision Geometry III, Proc. SPIE 2356, pp. 90--100,
1994.
R. S. Stephens, ``Probabilistic approach to the Hough transform,''
Image and Vision Computing, 9(1), pp. 66--71, 1991.
P. R. Thrift and S. M. Dunn, ``Approximating point--sets image by
line segments using a variation of the Hough transform,'' Computer
Vision Graphics Image Processing, 21, pp. 383--394, 1983.
S. Tsuji and F. Matsumoto ``Detection of ellipses by a modified Hough
transformation,'' IEEE Transaction on Computers, 27(8), pp.
777--781, 1978.
T. M. van Veen and F. C. A. Groen, ``Discretization errors in the
Hough transform,'' Pattern Recognition, 14(1), pp. 137--145, 1981.
F. M. Wahl and H. P. Biland, ``Decomposition of polyhedral scenes in
Hough space,'' in 18th International Conference on Pattern
Recognition, pp. 78--84, IEEE, New York, 1986.
W. Wernick, Analytic Geometry, Silver Burdett, New York, 1968.
L. Xu, E. Oja, and P. Kultanan, ``A new curve detection method:
randomized Hough transform (RHT),'' Pattern Recognition Letters,
11(5), pp. 331--338, 1990.
L. Xu and E. Oja, ``Randomized Hough transform (RHT): Basic
mechanisms, algorithms, and computational complexities,'' CVGIP:
Image Understanding, 57(2), pp. 131--154, 1993.
R. K. K. Yip, P. K. S. Tam, and D. N. K. Leung, ``Modification of
Hough transform for circles and ellipses detection using a
2-Dimensional Array,'' Pattern Recognition, 25(9), pp. 1007-1022,
1992.
H. K. Yuen, J. Illingworth, and J. Kittler, ``Detection partially
occluded ellipses using the Hough transform,'' Image and Vision
Computing, 7, pp. 31--37, 1989.
H. K. Yuen, J. Princen, J. Illingworth, and J. Kittler, ``Comparative
study of Hough transform methods for circle finding,'' Image and
Vision Computing, 8(1), pp. 71--77, 1990. change added
S. Y. K. Yuen, T. S. L. Lam, and N. K. D. Leung, ``Connective Hough
transform,'' Image and Vision Computing, 11(5), pp. 295--301, 1993.