connected through a straight line. The point of greatest departure

from the straight line is examined. If the departure is too large,

the point becomes an anchor point for two straight line-segments.

The procedure then repeats until all points are fitted by line

segments.

However, the seemingly simple algorithm is complicated by the

necessity to determine anchor points. Any new anchor point may

generate a need for two additional anchor points, each within two

separated segments. We use a “first-in-last-out” stack algorithm

to handle the anchor point selection. The algorithm is described

as follows.

Define a minimum departure which determines an anchor

point, say A,

Set a first-in-last-out stack (STK1), then sequentially push

all the points from the first end point (marked as A) to the

second end point (marked as B), set two more first-in-last-

out stacks (STK2 and STK3), and mark STK2 as -,

Push point B into STK3, and then push point A into STK3,

Pop two end points A and B from STK3. If STK3 is NULL,

go to step h),

Pop end point (marked as C) from STK1. If C==B go to

step g),

Calculate the distance d from point C to the line AB. If d

>A, push point B into STK3, and then push point C into

STK3, mark STK2 as +; pop point from STK2, and push the

point into STK1 until STK2 is NULL, go to step c).

Otherwise, push point C into STK2, continue with step e),

If STK2 marked as - , record point A and point C, iterative

pop point from STK2 until STK2 is NULL, go to step d);

else push point B into STK1, let B==C, pop point from

STK2, and push the point into STK1 until STK2 is NULL,

go to step e), and

Discard STK1, STK2 and STK3, then End.

image. The iterative line detection proceeds with the deletion of

recognized lines. It ends when the ratio of global maximum to

medium values in the accumulative array is less than the ratio of

the array size to the image size. Figures 8(a) to (d) are line

extraction results through Hough transformation.

c)

d)

Figure 8 Line extraction through Hough transformation.

4.6 Line Grouping through Perspective Geometry

In theory, a set of parallel lines in 3-D object space converges at

a single point known as the vanishing point when projected into

the image space. Consider a unit sphere centered at one of the

exposure centers, called a Gaussian sphere. A vanishing point

can also be represented as a point on the Gaussian sphere, that is,

a unit vector placed at the perspective center. So, given a vector

Q in the object space, its vanishing point V on the Gaussian

sphere can be computed as

4.5 Hough Transformation for Global Edge Linking

Hough transformation is mainly used here for linking edge pixels

of straight lines. It involves transformation of a line from a

Cartesian coordinate space to a polar coordinate space, in which,

the transformed line is simply a point at coordinates (p,0). A

family of lines passing through a common point maps into the

connected set of points. The main advantage of Hough

transformation is that it is relatively unaffected by gaps in curves

and by noise. For the problem of straight-line detection, Hough

technique organizes points into straight lines by considering all

possible straight lines.

In practice, there are two key points in an algorithm about Hough

transformation. One is in choosing the size of the array; the other

is in determining a threshold to form or exclude corresponding

lines. In our study, we base the size of the array on the image

size. Our experiments show that in order to achieve good

localized line detection, the size should be two'to three times

larger than the size of image. In order to exclude pseudo lines, a

global maximum criterion (rather than local maximum) is

selected to form a line. The longest line segment sharing two end

points with detected edge pixels is recognized as a line in the

where M is rotation matrix from the object to image coordinate

system. In particular, suppose the solar azimuth is represented by

0. We have two vectors Q and Q on the sphere