of
-Compute all à such that f(x,a) = 0 and Ix xa) =0
-Increment the corresponding accumulator cell: A(a) = A(a) + 1
step3: After each edge pixel x has been considered, local
maxima in the array A correspond to curves of f in the image.
The advantage of this method is clear if we take into account that
the gradient direction for each edge pixel is already known from
the proceeding edge detection procedure.
For example, the analytical form of the circle is given by:
f(x,y) = (x-a)2+(y-b)2 = 12 (2)
where (a,b) represents the center of the circle and r the radius.
When we follow the edge pixels that lie on the circle the
difference in gray level among the edge pixels is zero. That
means that the magnitude of gradient is zero:
ar
ox
en) eh at =
x? (x-a) +2 (y-b) 5 =0 = (x-a) + (y-b} =0
where 3 tan(®(x) RT
and ®(x) is the gradient direction as indicated from the edge
operator.
Then:
(x-a) + (y-b)* tan(D(x) - £ =0 =>
(x-a)*cos(P(x) - 2 + (y-b)* sin(P(x) - E) =0 (3)
Using the equations (2) and (3), it is obvious that the parameter
locus is reduced from a cone to a line. It can be concluded that
when using the gradient direction information, the number of
free parameters is reduced by one.
The same algorithm can be used for all the analytical curves. For
example an ellipse has 5 parameters. Using the gradient
direction two of the parameters can be solved as a function of
the other three. The computational effort in this case is O(e*d?) ;
where e is the number of edge points and d the distinct values
for each parameter.
Concluding the reference to the Hough Transform it has to be
highlighted that this powerful tool not only detects a predefined
shape, but it also gives its size, orientation, and center.
4. TARGET DETECTION USING HOUGH TRANSFORM
An important task in Digital Photogrammetry is the performance
of highly accurate measurements of target positions on the
digital image in order to perform a transformation between
image coordinate and object coordinate systems. These
measurements can be done either by operator or automatically.
In the latter case there is no need for an operator but the target
must be first detected and its center must be precisely located
using only the computer. Working in this direction [Trinder and
Mikhail, 1982] introduced an algorithm for edge modeling based
on least squares (edges,lines and cross targets), [Zhou, 1986]
utilized an algorithm for locating ellipse centers based on the
moment preserving method, [Trinder, 1988] proposed circles as
targets utilizing again least squares, and [Mikhail, Akey and
Mitchell, 1984] used Fourier descriptors and one dimensional
moments for target location and recognition.
In the present paper the Hough Transform is utilized to detect
and accurately measure the following target:
A white circle in a black background with four equally spaced
diameters intersecting on its center (see figure 3).
Fig. 3: Test target
À circle is the most appropriate shape for a target because the
image of a circle can only be a circle or an ellipse depending on
the observation direction (see figures 4 and 5).
Fig. 4: Digital image of the
test target taken at an angle.
Fig. 5: Gradient (Edge) digital
image of the test target of Fig.4
Hough Transform, as mentioned, cannot only detect circle and
ellipse in an image but it can also directly give their centers
which in the case of target detection is exactly what we are
interested in.
An alternative solution for the target center determination is first
to detect the circle-ellipse image of the target using the Hough
Transform and then to mask the rest of the image outside of the
target, making in this way the detection of the four lines inside
the circle easier using again the Hough Transform. The point of
intersection of these lines is the center of the target. [Harjoko,
1990] proposed the following algorithm for computing the
intersection of lines that are detected using the Hough
Transform:
N lines in the image space form a cluster of lines with a common
point of intersection ( xy). These lines correspond to N
associated clusters in parameter space. It has already been
mentioned that the measurements of the peakness of these
clusters result in a set of N pairs of standard deviations and
means. These quantities are further used to compute the center
of the target ( x.y). The location of the target center is
computed using least squares adjustment. For observations with
different standard deviations each observation must be weighted
properl
where
constan
Then th
where
and the
The stai
where /
the obs
matrix
equatio
Equatic
any iter
iteratior
Experir
approac
conditic
segmen
and qu:
noisy ir
lines wi
quantiz:
The ma
and acc
automa
safely a
the ima,
or as th
circle ta
The me!
No lim
showed
in repe!
illumine
A targe!
utilizing
backgro
safe tar
(noisy,i
accurac:
The pu
photogr
Hough
offer a