413 
В3b. Beijing 2008 
flow is shown in 
:d Region Grow 
n_ 
3oundary Fitting 
RITHM 
ne the region of 
f the building in 
;eds to define a 
ig region, 
points. Calculate 
nation (7 of the 
pixels. Compare 
neighbour pixel, 
itisfy one of the 
than 95% of the 
:vel of the pixels 
eshold. 
than or equal to 
id the grey level 
>r equal to one 
gion mean. 
, which is added 
K.els have been 
annot be grown 
MA 
the building has 
ise and regular 
f o schemas are 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
4.1 Boundary formation 
In high resolution remotely sensed image, the shape of a certain 
number of buildings is rectangular. For this kind of building, 
the boundary can be represented as a convex hull. The convex 
hull of a finite point set S = {P} is the smallest 2D polygon Q 
(or polyhedron in 3D) that contains S. That is, there is no other 
polygon (or polyhedron) A with S (Z A Cl Q . Also, this 
convex hull has the smallest area and the smallest perimeter of 
all polygons containing the set S. This idea is explained in the 
following Figure.2. The black pixels are collected via previous 
growing approach and the red boundary is the convex polygon 
of the black pixels. With these pixels, the approximate shape of 
the building is obvious. The exact boundary of the building can 
be represented by the convex hull of these pixels. 
Figure.2 Convex hull of the building pixels 
There are various algorithms to compute the convex of point set. 
Andrew's Monotone Chain Algorithm (A. M. Andrew, 1979) is 
one of the fast 2D hull algorithms, which is implemented as a 
stack. We choose it for that it runs in О (n log n) time due to the 
sort time. First the algorithm sorts the point set S = {P 0 , Pi... 
P„_i} by increasing x and then у coordinate values. Let the 
minimum and maximum x-coordinates are x mi „ and 
x max . Clearly, P 0 .x = x min , but there may be other points with this 
minimum x-coordinate. Let P__ be the point in S with P.x = 
x min first and then min у among all such points. Also, let P_ + be 
the point with P.x = x min first and then max у second. Note that 
P— = P_ + when there is a unique x-minimum point. Similarly 
define P+_ and P ++ as the points with P.x =x max first, and then у 
min or max second. Again note that P + _ = P ++ when there is a 
unique x-maximum point. Next, join the lower two points, P__ 
and P + _ to define a lower line L min . Also, join the upper two 
points, P_+ and P ++ to define an upper line L max . These points 
and lines are shown in the following example diagram. 
The algorithm now proceeds to construct a lower convex vertex 
chain Wmin below L min and joining the two lower points P— 
and P+-; and also an upper convex vertex chain Wmax above 
h max and joining the two upper points P++ and P-+ . Then the 
convex hull W of S is constructed by joining Wmin and Wmax 
together. 
The lower or upper convex chain is constructed using a stack 
algorithm almost identical to the one used for the Graham 
scan. For the lower chain, start with P— on the stack. Then 
process the points of S in sequence. Only consider points 
strictly below the lower line LSuppose that at any stage, 
the points on the stack are the convex hull of points below L„„„ 
that have already been processed. Now consider the next point 
Pi that is below L mi „. If the stack contains only the one point P_ 
_ then put P* onto the stack and proceed to the next 
stage. Otherwise, determine whether P* is strictly left of the 
line between the top two points on the stack. If it is, put P* onto 
the stack and proceed. If it is not, pop the top point off the 
stack, and test ? k against the stack again. Continue until P* gets 
pushed onto the stack. After this stage, the stack again contains 
the vertices of the lower hull for the points already 
considered. The geometric rationale is exactly the same as for 
the Graham scan. After all points have been processed, push 
P+- onto the stack to complete the lower convex chain. 
The upper convex chain Cl max is constructed in an analogous 
manner, but processes S in decreasing order {P„_i, P, ; - 2 ... Pol, 
starts at P++, and considers only points above L max . Once the 
two hull chains have been found, it is easy to join them together 
Figure.3 Convex computation algorithm 
This idea is only applicable when the building shape can be 
represented by a convex hull and the grow result is well enough. 
If the building shape is not a convex polygon, the boundary of 
the building can be calculated by active contour model from the 
region derived by grown algorithm. Details of ACM algorithm 
have been demonstrated in the book by Sonka. M (2003). The 
following figure shows the precise boundary (with blue colour) 
calculated by ACM algorithm. 
Figure.4 Building boundary calculated by ACM 
4.2 Building shape representation 
In real world, the building boundary is comprised of some 
straight lines and right angels. The comers whose constructing 
edges are parallel to the axis in planar coordinate system can be 
classified into four types which can be labelled ABCD