The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B7. Beijing 2008 
homogeneous regions. 
to have the same distribution contribute to this value: 
var(n) 
w(n, n ) 
d S pec(v2(n'),Vi(n))w(n, n')(13) 
n'Gdes(n) 
w(n, n') ■ a{n') 
Y2, w(n,n*) ■ a(n*) 
n* £des(n) 
(14) 
The weight w(n, n) between a node n and its descendent n' have 
to be normalized, so that Yln'edes(n) w ( n i n ') = 1 holds. The 
variability var(n) of a node n becomes therefore the weighted 
average of the spectral distances d spe c to its descendents des(n). 
The area a{n) of node n will be explained in more detail in the 
next section. 
3.3 Node value recalculation 
V2 (n) 
ô(w(n, n )) 
z 
\ yz v 2 (n) • ö(w(n,ri)) (19) 
n'€<ies(n) 
f 1, if w(n, n') > 9 
I 0, else 
S(w(n,n)) 
n' Edes(n) 
(20) 
(21) 
3.4 Iterative processing 
All calculations, in particular adjustments of link strengths and 
recalculations of the values of each node are done iteratively. The 
following gives an overview of the algorithm: 
After the weights of each connection have been adjusted, the val 
ues of every parent have to be recalculated. Starting at the level 
1=1 of the pyramid the values of all nodes in all levels have to 
be recomputed. The weights used have to depend on the link 
strength between the two nodes. However, they should also de 
pend on the size of the image area a(n') represented by the de 
scended n': Consider a node at a particular level of the pyramid, 
that has only one strong connection down the pyramid to only one 
image pixel. This node should have less influence than another 
node, that covers a large area within the image. 
a ( n ) = 
n' £des(n) 
w(n, n') ■ a(n') 
Y2 w(n'* ,n') 
n'* Epar(n') 
(15) 
As the sum in the denominator is computed over the parents of 
n', the area of a node is distributed among its parents in a nor 
malized way. This ensures that the total area of all nodes at each 
level is the same as the area of the original image. 
Every node in the pyramid plays two roles. On the one hand 
it is the sample covariance matrix of its descendents estimated by 
weighted averaging. On the other hand it is the descendent of a 
node on the next level. In order to apply the distance measure 
(11) it has to be Wishart distributed and the number of looks has 
to be known. One can show, that the sum of Wishart distributed 
random variables Xi is again Wishart distributed: 
Xi ~ W(m, X), * = 1,..., k => Xi ~ W m, X j (16) 
However, this holds only if all Xi have the same covariance ma 
trix X and are independent. This assumption should be strongly 
violated at higher levels of the pyramid, because their nodes cover 
large regions of the image. Furthermore, a multiplication with a 
scalar changes the distribution: 
X~W(n,Z) a-X ~W(n,a-Z) (17) 
The weighted average can therefore not be assumed to be Wishart 
distributed. That is why each node holds two values. The first one 
is simply the weighted average of the values of its descendents 
and therefore an estimation of the true covariance matrix: 
Ui(n) = ^2 V2 (n')-w(n,n) (18) 
n' Gdes(n) 
where w(n,n') is defined by (14). The second one is the (un 
weighted) average of the descendents with the strongest connec 
tions. This ensures, that only descendents which are very likely 
0: INIT: Construct pyramid 
1: While: levels not converged 
1.1: FOR 1=1 TOL 
1.1.1: Adjust weights w{n\n l ~ l ) 
1.1.2: Recalculate area a(n l ) 
1.1.3: Recalculate values v\(n l ) and V2(n l ) 
1.1.4: Recalculate variability var{n l ) 
2: Construct tree => Extract segments 
After a few iterations the link strengths will stabilise and not 
change anymore. At first the level Z = 1 of the pyramid con 
verges. At this time each node at this level will have strong links 
only to that subset of pixels in the set of descendents, which are 
very likely to have the same distribution governed by covariance 
matrix X of which the node value is an estimation. The sec 
ond value of a node at level l = 1 will now be an (unweighted) 
average of Wishart distributed random variables of the same dis 
tribution. That is why its own distribution can be assumed to be 
Wishart, too. However, the averaged variables cannot be assumed 
to be independent, because of the possible overlap of their areas 
in the image. Therefore the number of looks is estimated by the 
area the node covers in the original image and not by the number 
of looks of its descendents. All levels will converge in ascending 
order after a few iterations. 
3.5 Tree construction 
If the whole pyramid has converged, meaning that link strengths 
and, therefore, values of all nodes do not change anymore, there 
are two general types of nodes in the pyramid. On the one hand, 
nodes that have strong connections to one or more parents and, on 
the other hand, nodes which have no strong connection to any par 
ent at all. Latter ones define roots of independent subtrees within 
the pyramid and represent homogeneous regions in the image. 
All nodes at the top level of the pyramid or nodes whose link 
strengths to all their parents are below a certain threshold are con 
sidered as such roots. However, because of the different statistics 
at each level, e.g. the mean number of looks decreases with de 
creasing height, one cannot use a global threshold. But there is in 
each level an abrupt rise in the number of roots for a certain 
value t r ■ This value is used as threshold to define the roots in 
each level. Figure 1 shows an example of the relationship be 
tween the number of roots at a certain level and the threshold to 
define them.