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