ibul 2004 
eview of 
utline of 
erator to 
loreover, 
ly texture 
the real- 
tation is 
nentation 
ating the 
lgorithms 
algorithm 
tual pixel 
are four 
following 
elow the 
there are 
situation 
ark pixel, 
'cognized 
extraction 
s. If there 
(A), the 
becomes 
he object 
lored as a 
ht. If this 
"it 1s part 
the white 
ght. Else, 
does not 
action on 
luded the 
n, using a 
  
  
  
  
  
  
  
  
  
  
  
>xtraction. 
ion of the 
jeted are 
tracted is 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
2.1.3 Leak detection: Even when using an optimal grey 
value interval, the region growing algorithm can leak out if 
contrast at the object boundary is not sufficient. In case of the 
liver, especially the regions next to stomach and kidney are 
susceptible to leaking, since these organs have similar grey 
values as the liver itself. Often, the origin of the leak is only a 
narrow connection between neighbouring tissues. Since the 
time region growing algorithms are employed in segmentation, 
solutions that are both fast and easy to control have been 
searched to solve this problem. Often, the segmentation 
software allows the user to draw a line which blocks the region 
growing and thus prevents leakage. However, the most user- 
friendly approach would require just one mouse click in the 
leak area to remove it. The only proposed solution with this 
interaction scheme (Sekiguchi and Sano, 1994) has a major 
draw-back: it only works with very narrow connections. 
We propose a new method using distance transformation to 
identify leak regions and remove the additional area. The basic 
idea is as follows: From an arbitrary point within the erroneous 
area, we calculate the path to the seed point which always 
maintains the maximum possible distance to the surrounding 
edges. The point on this path which after a local maximum has 
the shortest distance to the contour marks the narrowest 
bottleneck to the chosen region and thus the origin of the leak. 
The constraint that a local maximum has to be passed first 
prevents that the starting point of the path is marked as origin if 
the user clicked at a position too close near the edge. 
A direct implementation of this idea uses the skeletonization or 
medial axis transformation (Lee, 1982) of the object of interest. 
There are several different definitions for the MAT of a shape, 
one being the following: assuming the shape is of a burnable 
material and is set on fire simultaneously on all sides, it will 
burn down towards the center. Where several fronts of fire 
meet, they extinguish themselves and the resulting line graph is 
the skeleton of the shape. 
  
Figure 2. Skeletonization of a leaked liver shape by 
thresholding the gradient magnitudes of the distance 
image. All pixels with a gradient magnitude lower 
than 0.95 are marked black. 
When the path follows this skeleton as much as possible, the 
maximum distance to the object border is maintained 
automatically. A fast implementation to test if points belong to 
the skeleton or not is based on the gradient magnitudes of the 
distance image of the shape, which can efficiently be calculated 
using the algorithm presented in (Arya, 1998). All points where 
this magnitude is zero belong to the skeleton. Due to 
inaccuracies in the distance transformation of quantized images, 
it is better in practice to test if the gradient magnitude lies 
below a specific threshold. For an example of this method see 
figure 2. 
Being able to determine if a pixel is part of the skeleton or not, 
the next step consists of finding the shortest path over this 
skeleton. An extensive graph search on the entire skeleton is the 
most obvious solution to this problem, but to save the inherent 
costs of computation, we opted for a different method. Our 
algorithm makes use of the fact that the path always leads from 
the periphery towards the seed-point. During the region 
growing phase we count at which step each pixel is added to the 
region, defining a geodetic distance function. During the path 
search, we only consider pixels with a geodetic distance lower 
or equal to the distance at the current position and chose among 
those the one with the lowest gradient magnitude. In case the 
lowest magnitude is lower than 0.5 (i.e. the path has not 
reached the skeleton yet), we alternatively chose the pixel with 
the largest distance to the contour. 
For every pixel in the path, we check its distance to the contour 
for a local minimum to find bottlenecks of the shape. The 
smallest local minimum is marked as the origin of the leak. 
Subsequently, we search the two nearest, opposing points on 
the contour at the acquired position and separate the segmented 
area along a line between these two points. The part of the area 
where the user clicked is then removed from the segmentation. 
An example of this operation is shown in figure 3. 
  
Figure 3. The region grower with seed point in the liver 
(white circle) has leaked out into the stomach. The 
path calculated by the heuristic from the point of 
correction is displayed yellow-green. The blue line 
shows where the contour will be separated at the 
leak origin. 
2.2 The new contour correction tool 
The presented leak detection for the region growing tool works 
in cases with a bottleneck between leaked area and origin. If 
this bottleneck is not present or the deviation is too small the 
method will not work. Additionally, as we found out in the user 
survey of our segmentation software, demand for an efficient 
correction tool is very high. The basic freehand segmentation, 
i.c. adding or subtracting an enclosed area, is not sufficient: 
Changing between the two modes is time-consuming and error- 
prone, moreover, it is cumbersome to revolve the entire 
correction area.