ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
95 
2.4 EXTRACTION OF STRAIGHT LINES 
The buildings and roads usually presents regular form, and can 
be described by line features. Analyzing and comparing the line 
features in candidate changed regions, the changes of 
man-made objects and other objects, such as trees, can be 
detected. 
The Canny operator was used to detect edges in candidate 
changed areas on both registered epipolar images. In order to 
acquire the vector of line segments, an improved hough 
algorithm was applied to extracted line segments from the 
feature edges. The basic principle of hough transformation is to 
transform straight lines (or curves ) from image domain to 
parameter domain. Then the parameters of the straight lines (or 
curve) can be determined by detecting the point with the 
maximum in the parameter domain. Hough transformation is 
strong resistance of noise, robust and also easy to implement 
but it can’t provide the precise coordinate information of straight 
line, we adopted line tracing algorithm to capture coordinates of 
every edge on line after the traditional hough transformation has 
detected the existence of line. Description information about the 
line could be obtained after edge points had been captured. This 
methods was simply described as follow: 
Suppose a line is made up of P^ P 2 , P3,...P n> : 
(1) for all i,j,k, if i< j<k then Pjis located betweenPiand Pj 
(2) for all 1<i<n, ||Pi-Pi + l|| < Lmax 
Based on its gradient direction 0, we corresponded every edge 
point to a aggregator with gradient angle 0 e(0 b ±0 max ),we can 
calculatepfor every edge, while || p r p 2 || < L max , this two edge 
are thought belonging to one piece of partition of straight line 
with angle of 0 b . Meanwhile, their coordinates will be recorded. 
Figure 4 show extraction result of straight line in the candidate 
changed regions. 
Figure 4 result of extraction of straight line for candidate 
changed regions ( all lines were filtered with length > 10, 
rectangle represent candidate changed regions ) 
2.5 ANALYSIS OF GRADIENT DIRECTION 
As well known objects such as building, trees, which are higher 
than the terrain surface, will be modeled as lumps in DSM. For 
detecting the changed building and reducing the false rate, we 
need distinguish the regions belonging to the building and those 
belonging to other objects, such as trees. The histogram of 
gradient directions can be analyzed. In building’s gradient 
direction histogram, there are usually four peaks representing 
four directions with internal of 0, 90, 180, 270 degree 
respectively, or there are two higher peaks with some lower 
peaks. And there are only two peaks, whose internal is 180 
degree, for the roads. There is no peak for the trees. In our 
algorithm we adopted sober operator to calculate the gradient 
vector. Figure 5 shows the different histograms from the regions 
of building, road and trees. 
(a) Buildings (b) Roads (c) Trees or Nothing 
Figure 5 Gradient Direction Histograms 
In order to make the histogram analysis go smoothly, several 
ways were taken to make the histogram easier to recognize and 
compare. One way is to put statistics and analysis of gradient 
direction limited on the edge points of filtered straight segment to 
refrain noise, another way is to “normalize” the histogram into 
only four directions with interval of 0, 90, 180, 270 degree 
respectively (suitable for rectangle building). In this normalization 
process, a major gradient direction (with the maximum frequency) 
was firstly searched for and was used to derive other 3 
directions. Frequency of gradient direction was recalculated only 
for the four directions according to a tolerance of 15 degree. 
Figure 6 (a) shows the four directions histogram of region 35# 
for new period. Figure 6 (b) for old period. It could been seen out 
from figure 6, on one hand, the four direction histograms reflect 
major gradient direction distribution of every region, on the other 
now, analysis of gradient direction could be done focusing on the 
four directions histogram for every region. Through comparing 
the new and old four directions histogram, the difference of 
frequency of four gradient direction can be acquired. With plenty