Digital Signal Processing Reference
In-Depth Information
y
C
k
KL
x
C
d
KL
(8)
r
C
x
K
x
C
y
K
y
C
(9)
It concludes that three points which are not in the same line map to a point
x
C
,y
C
,r
C
in the parameter space. In this paper, it is supposed that three points make up a
point-group in image space and a vector
Px,y,r
represents the point in parameter
space. So a point-group in a circle in image space maps to a vector P
i
in parameter
space. In image space, n point-groups are selected and mapped to n vectors
P
P
…P
in parameter space. If the point-groups are selected from the same circle, they will be
mapped to the same vector in parameter. In all the vectors, the one which has the max
count number is the parameter of the circle.
3
Gradient Hough Transform Algorithm
Randomized Hough Transform is multi-to-one mapping and the parameters are saved
and accumulated in the memory units. Lots of invalid parameters are produced when
doing randomized sampling, and these invalid parameters occupy lots of memory units
and make invalid accumulation[6]. For example, there have N circles whose size is q,
and have n points which are not on the circles, the probability that 3 points are selected
at the same circle by random sampling is expressed as follow:
p
NC
N
NNN
(10)
C
N
n
=
0
If
, Eq.(10) can be simplified,
P
NC
N
N
N
N
C
N
N
(11)
It is obvious that the probability P is in inverse proportion to the mounts of circles N,
when N increases, invalid accumulations are more and more. So it is impractical for our
concentric circles detections.
For this, it brings out Gradient Hough Transform. As we all know, the line along the
gradient direction[7, 8] in the circle edge of image passes the center of circle. Because
of concentric circles, there has only one center, if we select the two random points in the
circle edge, the two lines along the gradient directions cross at the center. We suppose
two points, C
a
and C
b
, and their gradient directions are expressed by
dy
dx
|C
and
dy
dx
|
C
, their coordinates are (X
Ca
,Y
Ca
) and (X
Cb
,Y
Cb
), so we can figure out the
center which is expressed (X
o
,Y
o
) by using Eq.(12) and Eq.(13).
C
Y
Y
C
X
X
C
(12)
C
Y
Y
C
X
X
C
(13)
