Olaf Hellwich
2. The geometrical parameters of a segment derived out of merged segments can be determined from the parameters of
the original segments. Thus, applied to region growing by merging, the computational effort is independent of the
shape, size and girth of the regions and therefore constant. This enables shape-controlled region growing with the
same order of computational effort as without shape control.
3. The same set of parameters also enables the compensation of the lateral ratio of rectangular objects. This can be
carried out independently of the orientation compensation.
To be independent of user interaction the region-growing-by-merging algorithm starts with all pixels as competing seed
points. Initially, every pixel builds a region with four boarders to its neighbouring pixels. With every step the one boarder
that is minimizing a given criterion is removed.
This quality criterion of a region is defined on the basis of radiometric and shape characteristics as well as computational
requirements. A region should be homogeneous and have a rectangular, not a fractal, shape. The merging criterion
therefore must measure boarder smoothness. One easy to calculate parameter is the enclosed area divided by the boarder
length. The problem is that, if applied on grid data, this gives preference to squares with boarders parallel to the grid.
In contrary to this, for grid data given the number of pixels P within the region, the number of edges FE and corners C
forming the boarder the new parameter describes the shape of the area by:
; 2E? -16— C? D
TPEC — 32P (
It can easily be shown that every square with parallel or diagonal boarders derives to 7 pc: = 1 (cf. Fig. 5). Other shapes
get higher values. For any other orientation of the square (Giinzl and Hellwich, 2000) show that deviations can easily be
compensated for by a simple extension to equation 1. The same is valid for the ratio of the side lengths of rectangles such
that any rectangle with arbitrary orientation with respect to the grid is provided with the optimum parameter value.
Figure 5: Segment shape parameter for grid data. In case of the left strictly squared region rprc — 1, whereas in case of
the equally large right region which is not squared rpc = 1.2.
To implement the criterion of equation 1 it is necessary to continuously keep track of the boarder length and the number
of corners within each boarder. Therefore, the boarders were implemented as cyclic doubly-linked lists. Every boarder
is part of both lists of two neighbouring regions. The algorithm keeps track of the number of edges E, the number of
corners C and the angle with which it is connected to the following boarder sections within both chains. The boarders are
organized within a binary heap data structure (Cormen et al., 1990, page 140) enabling a merging to be performed with
an effort of order O(m In b) where m is the mean number of neighbours a region has, and b is the number of boarders
surrounding and separating from each other the original pixels of the image.
Summarizing, the parameter describes the deviation of the shape of a segment from a rectangle. It is “1” whenever the
segment is rectangular — independent of the location and orientation of the segment with respect to the grid, as well as
of the ratio of the side lengths of the rectangle. When the segment increasingly deviates from the rectangular shape, the
parameter increases continuously. As a result this computationally efficient shape parameter is very well suited to segment
areas of agricultural landuse usually consisting of rectangles.
4 RESULTS
In this section, two examples of scene interpretation based on multisensor fusion are shown. The theoretical framework
described in the previous sections has not yet been fully applied for the processing of these examples. Nevertheless, the
preliminary results already show promising results.
392 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
