WATERSHED SEGMENTATION AND REGION
MERGING WITH APPLICATION TO
REMOTE SENSING
By
TAKASHI KOSHIMIZU
Bachelor of Science
Tamagawa University
Tokyo, Japan
1990
Submitted to the Faculty of the
Graduate College of the
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
December, 1998
WATERSHED SEGMENTATION AND REGION
MERGING WITH APPLICATION TO
REMOTE SENSING
Thesis Approved:
/' Thesis Adviser
K...;;;;;z. CZ 1"7"=
Dean of the Graduate College
ii
ACKNOWLEDGEMENTS
Many people have contributed to this thesis, and 1 would like to specifically
recognize several individuals. Dr. Scott T. Acton, my major professor, has supported me
throughout entire this project. Through his contribution have been many, 1 want to thank
him for his advice, constructive criticism, and gentle guidance. Additionally, I want to
extend him my appreciation for allowing me, at times, selfreliant. I learned many things
during this thesis, about academia, and about myself, and 1 attribute the positive result of
this learning experience to him.
Other individuals within Oklahoma State university have also affected this thesis.
I wish to acknowledge Dr. James West for his constructive advice and honesty. I want to
thank Dr. Keith Teague for his friendship and encouragement, both in and out of the
classroom. I want to express my appreciation to everyone associated with the Oklahoma
Imaging Laboratory, and I with to specifically thank Mr. Andrew Segall, Mr. Joseph
Bosworth, Mr. Anthony Hackner and Miss. Zhongxiu Hu for their many creative
discussion. I have enjoyed interacting with these laboratory members and I also have
been encouraged many times by these wonderful individuals.
Completion of this thesis has required personal sacrifices, and I want to
acknowledge all of my friends and relatives for their understanding. Thanks to my
iii
parents, Mr. and Mrs. Koshimizu, for their neverending love and understanding. I want
to thank Jones' family, especially Paul and Annette Jones. Their friendship, support and
understanding have never come to end during my school work at Oklahoma State
University.
Financial assistance for this thesis has been provided by many sources. Primarily,
I would like to thank the NASA EPSCoR (Experimental Program to Stimulate
Competitive Research) program, who supported this work under grant number NCC5171.
I would like to thank Dr. Ron Elliott of Oklahoma State University Agricultural
Engineering, Dr. David Waits of SiteSpecific Technology Development Group, Inc.
Additionally, I would like to acknowledge the financial support of the Oklahoma State
university Foundation, provided by a Distinguished Graduate Fellowship.
IV
Chapter
TABLE OF CONTENTS
Page
1 Introduction .
1. 1 Overview .
2 Review of Literature 4
2.1 Introduction , 4
2.2 Review of Image Segmentation Techniques 5
2.2.1 Image Segmentation Criteria 5
2.2.2 Image Segmentation Techniques 7
2.2.3 The Edge and Boundary Approach. .. . .. .. 7
Gradient Operators 8
The Laplacian Operator , 10
2.2.4 Regionbased Approach 12
Thresholding 12
Split and merge 13
Advantages and Pitfalls of the Watershed Segmentation 14
2.3 The Watershed Segmentation 16
The Minimum Following Algorithm 16
2.4 The Morphological Pyramid... .. . .. . .. . ... .. . . .. .. . . . .. . . . . .. .. 18
Implementation of the Morphological Pyramid. . . . . .. .. .. 19
2.5 Region Merging Techniques , , 21
The Single Linkage Region Merging Technique 22
Edge Strength Seeking , 23
MarkerBased Segmentation 24
The Variational Technique 24
2.6 Soil Moisture Estimation Techniques 25
Estimation SM using Ts and TM 5/ TM 7 26
Estimation of SM from Tr V.s. NDVI and the Triangle Method 27
2.7 Summary 28
v
Chapter Page
3 The Soil Moisture Estimation Technique from Satellite Imagery..... 30
3.1 Introduction 30
3.2 Satellite Images and Characteristics of Spectral Bands.............. 31
Characteristics of Three Spectral Bands 33
3.3 The Soil Moisture Estimation Process........ .. 37
The Triangle Method 38
3.4 Mesonet Soil Moisture Sensors 40
3.4 Summary........................ .. 42
4 The Watershed Segmentation and Region Merging 43
4.1 Introduction 43
4.2 The Watershed Segmentation Technique... .. .. .. 44
Flow of the WS algorithm.................. .. 44
The Minimum Following Algorithm , 45
4.3 The Multiresolution Pyramid and the Watershed 47
The Multiresolution WS and New Edge Linking Process 48
Computation Cost in the Multi and Fixedresolution Watershed 50
4.4 Region Merging Techniques. .. ... ... .... .... ..... . . .. 51
4.4.1 Single Linkage Region Merging Technique 52
4.4.2 SingleLinkage Region Merging with Recursive Threshold 55
Hierarchy of the Region Merging... . .. . .. .. .. .. . .. 56
4.5 The Variational Technique 58
4.5.1 The Energy Function Formulation 59
4.5.2 Similarity Measurement by the Var.iance versus
Average of Region Graylevel 63
4.6 The Hierarchical Stepwise Merging Algorithm with the
Variational Technique 64
Measurements of the Segmented Images.......... .. ... .. .. .. .. 66
4.7 Application of the Variational Method on Synthetic Images 67
Merging Path and Local Minimum Image Energy 69
Energy Computation for Four Regions '" .. . .. .. .. .. 69
Energy Computation for Three Regions 70
4.8 Summary...... .. ... . .. . . .. . .. ... .. . . .. .. . . . . .. . .. .. 72
vi
Chapter Page
5 Results and Conclusions 74
5.1 Introduction 74
5.2 Image Segmentation Results 75
5.2.1 Application of Region Merging to Test Images 75
Segmentation Results from the Swan Image 76
Segmentation Results from the Leaf Image 77
5.2.2 Soil Moisture Image Segmentation 78
Soil moisture segmentation on SMrl3c07 Image 78
Soil moisture segmentation on SMr04c04 Image 79
Soil moisture segmentation on SMrllc to Image 80
5.3 Conclusion and Discussion 81
The Computation Cost on Watershed Segmentation 80
Region Merging by Variational Model and the Evaluation Criteria 82
Discussion 83
5.4 Future Work . .. .. . .. .. .. . .. . .. .. . ... . . . ... .. .. . . . . .. .. .. . ... . .. .. .. . . . . . . ... 84
Bibliography 99
vii
LIST OF TABLES
Table Page
2.1 WS segmentation  the strengths, weaknesses and the possible solutions 16
3.1 Summary of description of satellite sensors used SM studies 31
4.1 Conventional and New Merging Schemes 52
4.2 The relationship of A.. and ~ E 62
4.3 Initial variance of the test image. .. .. .. . . . ... . ... . .. .. ... .. . .. . . ... ... .. .. .. ... 67
4.4 Calculated MSE and the energy for the thirteen patterns 69
4.5 Calculated MSE and the energy for the possible patterns for four segments. . .. .. 70
4.6 Calculated MSE and the energy for the possible patterns for three segments. 70
5.1 Application oflmage Segmentation 75
5.2 The computation costs of the fixed WS and the multiresolution WS 82
viii
LIST OF FIGURES
Figure Page
2.1 An comparison of a well target identified image and
a target absence image .. ... . ... .. . ... 6
2.2 Two Image Segmentation Approaches....... 7
2.3 An illustration of the basic edge detection mechanism.... .. . 8
2.4 The Prewittoperator kernels............................................................. 10
2.5 The Sobeloperator kernels 10
2.6 Segmentation results by the Sobel edge detection operator. .. . ... .... . .. ... . .. . ... . I I
2.7 The histogram of a SM image............................................................. 12
2.8 Segmentation results from the Watershed segmentation 15
2.9 An illustration of WS 17
2.10 Morphological Image Pyramid. . .. .. .. . . 18
2.11 An illustration of the Single Linkage Region Growing Algorithm 22
3.1 (a) Entire TM Image , .. .. .. 32
3.1 (b) The image region over Oklahoma. . 32
3.2 Three TM band images and NOVI image 34
3.3 Typical spectral reflectance curves for vegetation soil, and water.................. 35
3.4 The ScaUer Plot............................................................................. 37
3.5 The Triangle Method............................................ 38
3.6 A scatter plot and overlapped isopleths 39
3.7 The Soil Moisture Image................................ 40
IX
Figure Page
4.1 The location of minima and the catchment basins in
one dimensional example 45
4.2 Flow of the MRWS 47
4.3 An illustration of our proposed boundary propagation process 49
4.4 SM segmentation results from Single Linkage Region Merging 54
4.5 Flow of the Recursive Thresholding 55
4.6 An illustration of Tree Diagram 56
4.7 SM segmentation examples from Single Linkage Recursive Threshold........... 57
4.8 An illustration of a merging process 61
4.9 An original synthetic test image and the initial partitions............. 67
4.10 Thirteen possible segmentation patterns 68
4.11 The region merging results from variational technique on a synthetic imageA 71
4.12 The region merging results from variational technique on a synthetic imageB 71
5.1 (a) Segmentation results from recursive thresholding on Swan image 86
5.I(b) Segmentation results from variational. technique on Swan image 87
5.2(a) Noisy Leaf image and openclose filtered images....... 88
5.2(b) Segmentation results from recursive thresholding on Leaf image 89
5.2(c) Segmentation results from variational technique on Leaf image 90
5.3(a) SM segmentation results from recursive threshold on SMr13c07 image 91
5.3(b) SM segmentation results from variational technique on SMrl3c07 image 92
5.4(a) SM segmentation results from recursive threshold on SMr04c04 image 93
x
Figure Page
5.4(b) SM segmentation results from variational technique on SMr04c04 image 94
5.5(a) SM segmentation results from recursive threshold on SMrllclO image 95
5.5 (b) SM segmentation results from variational technique on SMr11 c 10 image...... 96
5.6 The Edge Maps. .. 97
XI
Chapterl. Introduction
1.1 Overview
This paper studies an image segmentation technique, which considers the
application and classification of satellitesensed soil moisture images. Image
segmentation is one of the essential and fundamental parts of image processing. The
world of image segmentation is vast and there are various techniques.
As a first step, we start by reviewing the philosophical concept and the
definitions, then clarify them to find a suitable technique for soil moisture image
segmentation. The watershed segmentation is a powerful image segmentation technique.
It is advantageous because it always forms closed and thin boundaries. Therefore, it is the
main focus of this thesis. This image segmentation scheme is widely used by various
types of images, such as medical imaging, texture segmentation, and object extraction. In
this thesis, we apply this segmentation technique in order to classify the satellitesensed
ground soil moisture images. The original images have complex patterns, therefore our
objective is to simplify the soil moisture image as much as preserving the original (soil
moisture) distribution, i.e., minimizing clustering error. However, in the practical
application, there are two disadvantages associate with this algorithm  over segmentation
and large computational costs. Our first goal in this thesis is to find a possible solution to
these problems.
The region merging is a practical remedy for the oversegmentation, and a major
focus of this thesis. Traditionally, region merging techniques are selected for specific
applications and it was implemented in a heuristic manner. Therefore, we attempted to
establish a well motivated region merging technique for the watershed segmentation this
is the second goal in this thesis.
The demand for the application of image processing on satellite sensed imagery is
growing, not only for the scientific research purposes, but also because it is widely
utilized in our daily lives. Our study is initiated from the Earth Observing System, a
project of NASA, which remotely monitors earth and studies its condition form a global
point of view. One of the key topics in this research is the observation of the status and
the transition of ground soil moisture from a global scale. The collected soil moisture
data was processed to study global energy budgets and the water cycles of the globe.
Well organized ground soil moisture estimation techniques have been developed
and applied recently. The soil moisture estimation techniques from the remotely sensed
imagery are essential in mapping the status of the ground soil moisture over the global
area. In this study, we chose an applicable technique and simplified it to draw soil
moisture images from our satellite sensing data. The principle and process are fully
explained in Chapter3.
Unfortunately, the derived soil moisture images are less contrasted and quite
uniform in grayscale distribution. Image segmentation of these images is not a simple
task. When using conventional image segmentation techniques, it is difficult to yield
meaningful segmentation results, due to the complexity of the image. The selection of a
poor technique could cause an inadequate classification of soil moisture distribution.
Therefore, the soil moisture segmentation technique has to be chosen with considerations.
In order to present a possible solution to these problems, a new and sophisticated
region growing technique  the variational technique is introduced. The proposed
2
technique can be a possible solution to the issues of conventional region merging. Using
the variational technique, an equation (energy function) is applied and the region merging
progresses according to the energy function. Additionally, using the energy function, we
have the ability to control the region scalability using a region scaling parameter. Being
able to control the region scalability is essential in the image segmentation of this
research. These details are fully explained in Chapter4.
Once images are segmented, it is important to evaluate and measure the
segmentation quality. If the segmentation results do not represent the original soil
moisture distribution, the segmentation technique is useless. The formulation of the
energy function contributes to the measurement and evaluation of the segmentation
results. The development of a well motivated image evaluation technique is another
important topic and it is our the third goal in this thesis. The segmentation results from
the new approach are evaluated and compared to the conventional approaches according
to the energy level. All of the results are shown in Chapter5.
The importance of the image processing is growing with the development of
digital computers and information technologies. Various image processing technologies
are applied and utilized in our daily life, such as medical imaging, massproduction in
industry, and the internet. This study focuses on just one section of the world of the
image processing. But, proposing a possible solution to the existing issues, we would like
to contribute a progress of the image processing. In the following chapter, Chapter2, we
start to review conventional image segmentation techniques and attempt to clarify the
issues. The chapter also supplies the background of the watershed segmentation
technique and the new image segmentation technique.
3
Chapter 2. Review of Literature
2.1 Introduction
This chapter provides the background for reviewing mainly three topics, which
are the watershed segmentation(WS), morphological pyramid and region merging
techniques. The first part of this chapter discusses philosophical definitions of image
segmentation. The definitions will be a foundation for evaluating the image segmentation
results. Choosing an adequate segmentation technique is an important starting point to
yield meaningful results. In section 2.2, various image segmentation techniques are
reviewed and examined for the applicability.
Another goal of this thesis is to establish a reasonable segmentation technique for
the satellite sensed soil moisture (SM) images. The watershed image segmentation
technique is mainly applied in this thesis. Therefore, the basic idea, the strengths, and the
weak points are reviewed. In section 2.4., we will explain the concept of the image
pyramid and the morphological pyramid which contribute the reduction of the
computational costs. Development of a well established region merging technique is
essential for the WS segmentation of the soil moisture images. In section 2.5, various
region merging techniques are reviewed concerning the application of the SM images.
Lastly, section 2.6 reviews the ground soil moisture estimation techniques from
remotely sensed imagery. Several possible soil moisture estimation techniques are
reviewed and the characteristics are clarified. In the following section, we explain the
basic concept of the image segmentation criteria.
4
2.2 Review of Image Segmentation Techniques
2.2.1 Image Segmentation Criteria
As the first step in finding a suitable segmentation technique for the soil moisture
images, we summarize and clarify the philosophical definition of image segmentation.
Without understanding the fundamental concept of image segmentation, it would be
difficult to evaluate the segmentation results.
There are several viable definitions of image segmentation. Gonzalez (Gonzalez,
1992) defined image segmentation as "subdividing an image into consistent parts or
objects". Castleman mentioned an alternative definition as "decompose an image into
meaningful parts with respect to a particular application" (Castleman, 1996).
If the target object is clearly known, the objective of segmentation is to segment
the target features from the background. Unfortunately, the target objects are not always
clearly identified (our soil moisture images, for example). In order to illustrate the
characteristic of our SM images, we compared two images. In Fig.2.1 (a), the target object
(a swan) is clearly identified. The objective of segmentation of this image will be
segmenting the swan. In contrast to the swan image, a soil moisture image is shown in
Fig.2.1 (b), neither a clear target nor a crisp boundary are observed. Thus, for the
segmentation of the soil moisture image, we have to prepare an adequate image
segmentation technique. Because of the absence of the target image, the segmented
results have to be measured at an appropriate scale. If the swan is segmented, even
visually it is possible to evaluate the segmentation results. But, how should we evaluate
the segmentation results of the soil moisture image? It is much difficult to define
meaningful or sound segmentation results of the soil moisture image, because of the
5
absence of a clear target. This is the reason we want to established a segmentation quality
evaluation technique in this research.
Fig2.1 (a) A Swan Image Fig.2.1 (b) A Soil Moisture Image
Fig.2.t An comparison
of well target identified
image and target
absence image.
Fig 2.1 (a) has a
clear target object a
swan,
Fig 2.1 (b) does not
have a clear object in
the image.
Before exploring the topic, let us I ist the properties of a good segmentation. The
properties below have been used as a guideline to evaluate the segmentation results.
According to Haralick (Haralick, 1992), general segmentation procedures tend to obey
the following properties:
I. Segmented regions of an image should be uniform and homogeneous with
respect to some characteristic, such as gray level or texture condition.
2. Region interiors should be smooth and without holes or spots.
3. Adjacent regions should have significantly different values with respect to the
characteristic on which they are uniform.
4. Boundaries of each segment should be simple, closed, ancl spatially accurate,
Haralick also mentions that it is difficult to achieve all the desired criteria. Therefore,
we need to carefully choose the segmentation technique that is especially suitable for our
soil moisture image segmentation. In the following subsection, we review several
segmentation techniques and evaluate their suitability for the soil moisture image
segmentation.
6
2.2.2 Image Segmentation Techniques
In general, image segmentation algorithms can be categorized by two different
approaches: edgeboundary approach and regionbased approach. In the edgeboundary
approach, one seeks to identify edge pixels and link them together to form the image
boundaries. The edgeboundary approach seeks discontinuity over the image. It directly
seeks edges or boundaries in the image and eventually divides the image based on the
boundaries.
Fig.2.2 Two Image Segmentation Approaches
RegionBased Approach
SEEK SIMILARITY
• Global thresholding
• Adaptive thresholding
• Split and Merge
• Watershed
Edge & Boundary Approach
SEEK DISCONTINUITY
• Robert edge detector
• Prewilt edge detector
• Sobel edge detector
• Laplacian
The second category, the regionbased approach seeks region or pixel similarities.
Using a threshold or other statistical values, it egments an image into homogeneous
regions. There are various image segmentation techniques among this category. In the
following subsection, we will examine the strengths and the weaknesses of each image
segmentation technique to clarify if they are applicable to our particular needs.
2.2.3 The Edge and Boundary Approach
An edge is the boundary between two regions where has significant graylevel
differences occur. This approach seeks the edges by directly examining each image pixel
and its immediate neighbors to determine whether the pixel can be an edge. Pixels
7
exhibiting the required characteristics are labeled edge points and the image that indicates
the presence of edges is called the edge map or the edge image.
The basic idea behind the edgedetection technique is the computations of the
local derivative operation. This concept is shown in Fig.2.3 with a simple example.
Fig.2.3 An illustration of the basic edge detection mechanism
... ~,._ ''''~....;..,. ~~ po ~ • ~ ~.'O'Y ....,
~::,.~...:. ';:";~"i.'i'" ~"),'.' r...i .•~·,.>l<~$." ,'" .' ·t'J.,,",~
if..~'~~@L;=~~A.~t::~ ~~7'j
I r" ~.. •
!.
1_'; , ,
~~3~i~__"~'~~'~~A~:i1
(a) Original Images (b)The Magnitude (c) The First derivative
Zero Crossing
Point
'/
(d) The Second derivative
Fig.2.3(a) is a simple graylevel image, where the dark area is gradually changing to the
bright area and the magnitude intensity is shown in Fig.2.3(b). The first derivative of the
magnitude can be drawn as in Fig.2.3(c). The peaks locate the middle of the graylevel
transition, and is the location of the edges. In the first derivative, Fig2.3(c) the peak
locates the middle of the transition, so it is difficult to detect the exact peak locations
when the image has complex features. This can be simplified by taking the econd
derivative of the magnitude, Fig.2.3(d) and locating the zerocrossing points. The first
derivative is obtained by using the magnitude of the image gradient and the second
derivative is similarly obtained using the Laplacian operator as shown in the following
subsection.
Gradient Operators
Given an image I, with I(x, y) is the intensity at (x, y) in the image I. The gradient
magnitude of an image lex, y) can be shown as
8
VI = [D D.J T = [aI aT JT •
. X,) ax' ay
The gradient magnitude is given by
From the above equations, the gradient magnitude is obtained from partial
derivatives dl / dx and dl/dy. If we take the derivative of two spatial neighbors we can
make a Robert edge operator, such as
g(x,y)={[~l(x, y)/(x + I, y +1)]2 +[~I(x + I,y)l(x,y + 1)]2 }1/2 I
where I(x, y) is the input image with a location of (x, y). This is simply operating a cross
differentiation on two adjacent points. In the practical application of the image
processing, these equations are translated into the kernels or operators. These operators
are convoluted with the original image to detect image edges. Sobel and Prewitt edge
detection operators are one of the practical examples. Shown below is an example of a
formula to show how the Prewitt operator works with a 3x3 kernel.
=IDx I + IDy I I
This operation can be implemented by convoluting the following mask with the original
image.
9
The 3x3 mask is called the Prewittoperator as shown in Fig.2A.
Fig.2.4 The Prewittoperator
kernels. (a) is the layout of the
kernel. (b) and (c) indicates
example of the kernel.
21 22 2J
Zq Zs 4
27 28 ~
(a)
1 I I
0 0 0
1 I I
(b) : D.
1 0 1
1 0 I
1 0 I
(e) : Dy
The Sobel operator uses the same 3x3 area as Prewitt, but with a slight change in
the coefficients. Each mask is shown in Fig.2.5 with the center pixels of the Sobel
operator assigned more weight. The original formula and the convolution kernel are
shown as follows.
Fig.2.5 The Sobel
operator kernels
1 2 1
0 0 0
1 2 1
1 0 1
2 0 2
I 0 I
D.
The Laplacian Operator
The boundary approach attempts to find the edges directly by seeking high
gradient magnitudes in the image. As in the previous example, the boundaries are
detected by running a boundary detection window (kernel) over the gradient magnitude
image. Laplacian edge detection is one of the example and it is a scalar secondderivative
operator. In two dimensions, it is defined as
2 a2 a2
V I(x,y)=ax2 I(x,y)+ay2 I(x,y).
This operation is commonly implemented by a convolution kernel. Since it is a second
derivative operator, the edges are located on the zerocrossing point. The locations of the
zerocrossing points are supposed to correspond to the edge locations in the original
10
Image, 10 Fig.2.3(d). This operation is nOIse sensitive, thus when noise exists III the
image, an additional noise elimination function is usually applied. (Castleman, 1996).
One of the advantages of the edgeboundary approach is the simplicity and the
low computational costs. Yet, this technique has serious disadvantages  these operations
seldom form closed connected boundaries. Eventually, these edge detection approaches
require additional edgelinking steps to form closed contours of the objects. Edgepoint
linking is the process of finding missing edges to form close contours. This process is
very tedious and has the potential to create false edges. Thus, these edge and boundary
detection approaches would not be appropriate in our study, especially for the soil
moisture image segmentation.
Fig.2.6 is the image segmentation results on an Aluminumgrain image by the
Sobel edge detector. In this experiment we used two levels of threshold value, T = 0.0 J
and 0.02. The segmentation results are shown in Fig.2.6(b) and 2.6(c) respectively. These
segmentation results (edge map) show unclosed contours. When the threshold value is
increased, trivial edges emerge, in Fig.2.6(c), yet still the contours are not closed. So, jusl
increasing the threshold value can not be the solution of the edge linking problem.
Fig.2.6 Segmentation results by the Sobel edge detection operator
(a) Original Image (b) The edge map at 1'=0.01 (c) The edge map at 1'=0.02
11
2.2.4 Regionbased Approach
The previous edgeboundary approach sought discontinuity of the image pixels
and detected the edges and/or boundaries to segment the image. In contrast, the regionbased
approach seeks similarity of each of the image elements or regions. In thi.s
subsection, three possible applications are introduced and examined  thresholding, spirit
and merge, and watershed segmentation.
Thresholding
Thresholding is a useful segmentation technique if the image has solid objects and
contrasting background. This approach is simple, requires little computation and
sometimes makes closed regions with connected boundaries. Thresholding works well if
the objects of interest have unifonn gray levels and the rest of the background has a
different but unifonn graylevel. When one threshold value is used to segment an entire
image, it is called a global threshold. Sometimes a single threshold value is not
appropriate to segment a complex image. In the adaptive thresholding, first the entire
image is divided into several subregions, and each threshold value is selected depend on
the subregions. In both cases, the selection of the threshold values depend on the shape
of the histogram. When the histogram IS
bimodal, usually the threshold value IS
Fig.2.7 The histogram of a SM image
4000,,,...,,
3500
chosen at the bottom of the valley 3000
2500
(Castleman, 1996).
Unfortunately, the thresholding
approach has to dependent upon the shape
of the histogram. Fig.2.7 shows the
12
histogram of the soil moisture image in Fig.2.t (b). The shape of the histogram is more
complex than a bimodal distribution. So, the first issue in this approach is the selection of
the threshold value.
Next, if we arbitrarily select multiple thresholds in even intervals, how would the
image be segmented? Let us assume we evenly subdivide (slice) this histogram into 10
subparts to segment the image into to grayscale classes. But how will the segmentation
result look? The worst aspect of this approach is the ignorance of size and spatial
location of the regions. The histogram approach does not consider the spatial location of
the clusters (regions). Consequently, the segmentation scheme forms small scale and/or
large scale regions by chance, and we are not able to control the region scalability (size
of the regions) at all. The major disadvantage of the thresholding approach is the absence
of region scale controllability.
Split and merge
This algorithm creates regions by splitting and/or merging the regions using a
similarity criterion that is sometimes called a predicate. Initially an original image is
subdivided into arbitrary, disjointed subregions and then merge and/or split the regions
to satisfy a given predicate, P. The original image is successively subdivided into smaller
and smaller quadrant regions until each region meets the predicate. Using the same
manner, regions can be merged if the merged region can meet the predicate. Therefore,
this scheme continues merging or splitting regions until each region meets a given
similarity criterion. What is the disadvantage in this scheme and how do the segmentation
results look? First of all, the selection of the predicate is done in a heuristic manner, and
practically it is difficult to select a meaningful value. Second, this scheme also does not
13
consider the region scalability (region size). This algorithm isolates extremely high and
low grayscale small regions in the result image. Noise in an image tends to have the same
characteristics (small but ex.tremely high or low intensity). Therefore, this scheme is
insensitive to the noise and does not effect them! The lack of control over the region
scalability is a pitfall of this algorithm as well. Hence, we need to find a more intelligent
image segmentation approach.
In the following part we will explain the watershed segmentation algorithm. Our
soil moisture segmentation technique is based on the application of the WS algorithm.
First, we will summarize the characteristics, the strengths and the weaknesses. Then we
propose possible solutions for the weak points.
Advantages and Pitfalls of the Watershed Segmentation
The Watershed segmentation is one of the regionbased image segmentation
algorithms which subdivides an entire image into small homogeneous regions. This
algorithm was originally developed end of the 1980' s, then Meyer(Meyer and Beucher,
1992), Vincent(Vincent and Sollie, 1991) and Gauch(Gauch and Pizer, 1992) has
modified the algorithm to more practical use. The watershed algorithm has two main
advantages compared to other segmentation techniques. First, it automatically produces
thin and closed boundaries. Thus, this algorithm never requires additional time
consuming contourtracking or edgeclosing processing. That is a strong incentive when
choosing an image segmentation algorithm. As a second advantage, the watershed
algorithm automatically subdivides an image into small and highly homogeneous regions,
which is called a watershed mosaic image. Additionally, the boundaries are zero
thickness, because the watershed segmentation defines the boundaries as region
14
differences. This is a large advantage of the region based approach. These two properties
are strong motivators as to why we assign this algorithm for the soil moisture image
segmentation. In order to compare the segmentation results, Fig.2.8 demonstrates a
segmentation for the same Aluminumgrain image as in Fig,2.6.
As the boundary image shows in Fig.2.8(c), the contours are all closed and no
trivial edges exist. Compared to Fig.2.6(c) the difference is significant. Nevertheless, the
watershed algorithm is not impeccable  it has a couple of disadvantages. The watershed
segmentation algorithm is highly sensitive to local graylevel variations. thus usually
resulting in a highly oversegmented image. Fig.2.8(c) was originally oversegmented,
and this result was given after a region merging process, which will be explained in
Chapter4. Another drawback of direct application of the watershed segmentation is the
large computational cost.
Fig.2.8 Segmentation results from the Watershed segmentation
(a) Original Image (bl The Mosaic Image (c) The Boundary Image
Historically, vaflous techniques have been studied in order to overcome these
drawbacks, but the best solution has not yet been found. We were challenged in this
thesis to find the best solution for the two issues. These techniques are discussed with a
demonstration in Chapler4. In the following table, the strengths, the weaknesses and our
solutions for the watershed segmentation algorithm are summarized.
15
Up to now, we reviewed several image segmentation techniques clarifying the
strengths and weaknesses. The following subsection briefly reviews the idea of the WS
segmentation algorithm.
Table 2.1 : WS segmentation  the strengths, weaknesses and possible solutions
Strengths
• Closed contours and regions
• Thin boundaries
• Draw mosaic image
• Applicable to complex images
Weaknesses
Oversegmentation
High computational cost
The solutions
Region Merging
Image Pyramid
2.3 The Watershed Segmentation
The concept of watershed is drawn from topographical analogy. Consider the gray
level intensity of an image as a topographic threedimensional relief. Assuming we drop
rain over the geographical area, water would drain from higher points to lower points as
we see in nature. Then we cluster all points that drained to the same local minima. By the
clustering process, we can draw watershed regions and their boundaries. This process is
called the minimum following algorithm. The brief concept of this algorithm is explained
with an illustration in the following subsection.
The Minimum Following Algorithm
The minimum following algorithm, introduced by Gauch and Pizer (Gauch and
Pizer, 1993), is one type of a watershed algorithm. Let us assume a gradient magnitude of
an image is a geographical surface. The first process in this algorithm is finding the local
minima. The local minima can be detected at the lowest points among the 3x3 spatial
neighbors, and they are assigned unique identity numbers. Then, we attempt to drop
water over the gradient magnitude image relief to detect where the rain drops are drained.
The rain drop will seek lower altitude and eventually meet a local minimum. Once the
16
Fig.2.9 An illustration of WS
ALocal minimum
The rain drop will seek lower altitude and eventually meet a local minimum. Once the
rain drains to a local minimum, the unique identity number is returned to the original
starting point. These points are called catchment basins. This process is applied to all of
the points over the image relief. Once all catchment basins have been labeled, watershed
boundaries are drawn by simply detecting the difference of the catchment basins. In other
words, watershed boundaries are borders of the catchment basins. Fig.2.9 illustrates a
local minimum, catchment basin, and the watershed boundaries in a simple image relief.
As we showed segmentation results in Aluminumgrain segmentation in Fig.2.8, the
watershed boundaries can be easily drawn by
detecting the differences of the catchment
basin number.
Historically, there is another variation
of watershed, which is called the immersion
algorithm. According to the immersion
algorithm, the whole gradient magnitude
image relief is immersed into a large water tub
and then the flooding patterns are recorded to draw the pattern of the segmentation. This
algorithm was introduced by Vincent (Vincent and Sollie, 1991) and sometimes applied
by other researches such as Meyer and Beucher (Meyer and Beucher, 1992). But, the
applied images in the research were simple compared to our 8M images. Additionally,
this approach requires complex false edge elimination processing. Dobrin (Dobrin et ai.,
1994) studied the immersion algorithm and reported the possibility of the false boundary
occurring by the algorithm. The minimum following algorithm overcomes the weak point
17
(the creation of false boundaries) of the immersion method. Also, the minimum following
algorithm is simpler to implement. Since the creation of false boundaries is a serious
segmentation issue, we have focused on the minimum following algorithm in this study.
In this subsection we reviewed the mechanism and key characteristics of the
watershed segmentation. In the following section, we will review possible remedies for
the two issues that are mentioned earlier  large computational costs and oversegmentation.
The application of the image pyramid is one possible solution for the
reduction of the computational costs. In the following section, the basic concept of the
image pyramid is explained with an illustration.
2.4 The Morphological Pyramid
Image pyramid is a scale space technique. Sometimes original images contain
extra information, such as insignificant edges or noise. This morphological filtering and
subsampling process leaves only significant information and eliminates noise and trivial
information of the image.
A morphological pyramid is
Fig.2.10 Morphological Image Pyramid
constructed by successIve filtering of the
operators. By repeating this step, the original
image size will be reduced by subsampling
factors. For example, twotoone pixel
sampling along each dimension makes a
quarter of the original image size.
original image with morphological
128x128
18
Recurrence of this process creates a multiresolution image pyramid, shown in Fig.2.t O.
When a morphological filter is used during the sampling process, the image pyramid is
often called a morphological multiresolution pyramid (Hejimans and Toet, 1991).
The reduction of the computational cost is the major incentive for the application
of the image pyramid. Processing a small image takes less computational time.
Remember that over segmentation is another pitfall of watershed segmentation. Region
scalability is also observed from the multiresolution approach, because it creates a scale
space. Thus, using the morphological pyramid, both disadvantages could be minimized.
In the following subsection, further characteristics of morphological pyramid are
reviewed, such as, the filter type, the filter size and the sampling conditions.
Implementation of the Morphological Pyramid
The selection of the morphological filter is important. The size and filter type
directly affect the sampled image. The objective of the morphological filtering is that it
removes trivial edges while eliminating the noise. If the size of filter kernel (structure
element) is too large, it could destroy important contours. Morales and Acharya (Morales
and Acharya, 1995, 1991) intensively studied the relationship of morphological sampling
filter and its effects. According to the study, the sequential openclose filter with the
smaller structure element is the best choice to preserve the edges. From the study, it has
been shown that sequential openclose filtering has less distortion and smoothes the
image better than direct appl.ication of a large structural element. The same sequential
openclose filtering technique has been applied in our multiresolution morphological
pyramid.
19
In the below, the concept of openclose morphological filtering is reviewed. Two
fundamental operators, erosion and dilation make up all morphological filters. When the
original image is given by I and a structural element K, dilating an image 1 with the
structuring element K is defined by
(I ffi KXx) =max{I(y) lye K}.
Dilation performs a moving localmaximum operator, while erosion is a moving localminimum
operator, thus the erosion is defined by
(I e KXx) =min{l(y) lye K}.
By using these fundamental operators, two higher order operators are established.
The opening of an image 1 by structuring element K is defined as
10K = (I e K) ffi K ,i.e., dilation then erosion by K,
and the closing of image 1 by structuring element K is defined as
1 • K =(I liBK) (3K ,i.e., erosion then dilation by K.
An openclose filter is made by cascading open and close operators i.e.,
OpenClose Operation == (I. K) 0 K .
When a morphological pyramid is constructed with an openclose filter, we can
denote the image pyramid levellL by
I L=[(lIL.I). K) oK] J,s'
where L is a pyramid level, K is a structuring element. For example, [.],J,2 represents a
subsampling by a factor of two. If we apply S =2 then the size of the upper layer
pyramid image is onehalf of the sampled image in each dimension. Furthermore, the
20
higher the image layer, the more significant the edges that remain, because of the iterated
openclose filtering (Heijmans et al., 1991).
This subsection has explained the mechanism and objective of the image pyramid.
When the idea of the image pyramid is applied to the watershed segmentation, it is called
the multiresolution watershed segmentation approach. The multiresolution approach
contributes to reduce the computational time and to control the region scalability. Our
application and the detail of the multiresolution watershed pyramid will be explained in
Chapter4.
In the following section, we reviewed several regions merging techniques. By
reviewing these techniques we clarify the weaknesses and the strengths of each region
merging technique for the applicability to soil moisture segmentation.
2.5 Region Merging Techniques
A region merging process is an essential part in the practical watershed image
segmentation process. There are two goals in the region merging. The first goal is to find
an adequate region merging technique for the soil moisture imagery. The second goal is
to establish a suitable quality measurement scale for the segmented results.
Historically, several region growing and merging techniques have been used to
overcome the oversegmentation and to yield a reasonably segmented image.
Unfortunately, these techniques have been applied in a heuristic manner and for
individual applications. Therefore, we attempt to establish a well motivated region
merging technique. The following subsection reviews several region merging techniques.
21
These techniques are the single linkage region growing scheme, edgestrength seeking,
the markerbased segmentation scheme, and the variational method.
The Single Linkage Region Merging Technique
The singlelinkage region merging scheme assumes each region or image pixel is
a node of a graph. Given a similarity criterion, regions are formed by clustering as all of
the connected pixel sets meet the criterion. Sometimes, the similarity is measured by
using region graylevel or other statistical numbers, such as standard deviation or
likelihood ratio(Haralick, 1992).
Fig.2.ll An illustration of the Single
Linkage Region Growing Algorithm.
Fig 2.11 (a) illustrates original pattern
with a clustered region. Fig 2.11 (b)
indicates merged region with new
assigned region value.
Fig.2.11 (a)
103
102
223 220 101 100
226 221 103 103
Fig.2.11 (b)
Fig.2.ll (a) demonstrates this idea with a simple illustration. In the figure, the gray value
of each pixel is shown and the six pixels are already grouped, where each node is
connected by a line. In this example, pixels are connected by lines if their values differ by
less than 10.
One advantage of the singlelinkage region clustering scheme is the simplicity,
which means the region comparison needs only the neighborhood regions. Historically,
sometimes this concept has been used in the watershed region merging process. Vincent
also expanded the idea and applied this scheme to suppress oversegmentation with
recursive merging. The recursive merging varies the threshold (merging criterion) values,
which start from low, then gradually increased to merge additional regions. The recursive
merging can control the merging order according to the region similarity. Because the
22
threshold value is gradually increased, highly similar regions are merged in the early
stage, and dissimilar regions are merged later. The order is sometimes called the merging
hierarchy.
Once regions are merged, the region graylevel and the graphs are updated to the
newly emerged regions, as depicted earlier in Fig.2.11 (b). The termination of merging
occurs when a desired number of regions or objects are obtained. This conventional
merging technique is applied to segment our SM images. The details of the experimental
results are explained in Chapter5.
Edge Strength Seeking
This approach focuses on adjacent edge magnitudes instead of the region
graylevel value. When an edge magnitude value is less than a given edge threshold
(criterion), the connected regions are merged. These edge strengths are detected by
applying an edge detection operator over the segmented image. Beucher and Meyer
extended this idea with a clustering hierarchy. The clustering starts by merging the lowe l
edges. Once all the weak edges are merged, the threshold is gradually increased and the
recursive merging process continues. Thus, the clustering process produces a hierarchy of
region merging (Meyer and Beucher, 1990).
A drawback of this approach is that it has to depend on the edge detection
process. If the image is noisy, this technique has a chance to produce false edges. As we
reviewed in section 2.3, the edge detection process is very sensitive and rarely forms
closed contours. For these reasons, we will not apply this approach for our regi.on
merging scheme.
23
MarkerBased Segmentation
The markerbased segmentation is sometimes used to suppre s watershed oversegmentation.
The marker has two types, an inner marker and an outer marker. The inner
marker is located inside the target object and is used to group the region inside the target
object. The outer marker is located in the background and is used to group the
background regions (Dobrin, Viera et ai., 1994). The marker based clustering is
applicable only if the image is simple in its construction and contains a target object and
background. Unfortunately, our soil moisture images have complicated features. Hence,
the markerbased segmentation does not seem to be suitable for the segmentation of our
soil moisture images.
The Variational Technique
The variational technique 1S quite different from previous region merging
approaches. This method translates an image segmentation into an equation. The method
formulates a mathematical equation and the image segmentation is progressed according
to the equation (Morel and Sohmini, 1994). Generally, the energy equation totally
depends upon the user's interest, so the image energy should measure based on what the
user wants to measure.
Therefore, the first task In this method is to formulate an appropriate energy
equation that represents our region merging process. We focused on two terms, the region
smoothness and the number of regions, because the two tenns represent opposite status.
Using these terms we attempted to formulate our energy equation. The detail is fully
explained in Chapter4. The formulation of the energy equation has another advantage; it
enables us to measure the quality of the segmentation. The segmented images can be
24
evaluated according to the image energy. The new region merging technique is a well
motivated scheme which contrasts most of the historical heuristic region growing
approaches.
This subsection has reviewed and clarified the strengths and weaknesses of the
region merging techniques. Most of the techniques compared the similarity of neighbor
pixels, or regions, using grayleveI similarity or statistical values. Unfortunately, our soil
moisture images are complicated and the graylevel vary graduall y. Thus, we need to
develop a stronger merging algorithm than what exists now. Our new merging scheme,
an application of a variational technique, is fully studied and compared in Chapter4.
From the conventional merging scheme, we applied the single region linkage with
recursive merging techniques for the soil moisture image segmentation.
Up to now, we have reviewed image segmentation techniques and region merging
schemes to find the best approach for the soil moisture images. Continuing in the next
section, we will review the soil moisture estimation techniques.
2.6 Soil Moisture Estimation Techniques
This subsection reviews general concepts of Soil Moisture (SM) estimation
techniques from remotely sensed imagery. Estimation of SM from satellite imagery has
been an important research topic for related researchers. It has been studied extensively
by agricultural, hydrologic, environmental and soil scientists. The estimation techniques
from these studies tend to formulate complicated models. Various local weather
conditions and hydrological parameters have to be considered, such as wind condition,
soil textures, canopy coverage, humidity, amount of rain, and amount of solar radiation.
25
One of the issues of applying these comprehensive models is that it is difficult to obtain
all of the parameters. Thus, we attempted to find relatively simple SM estimation model
without losing significant SM information. Here, we review several SM estimation
techniques and then we introduce the Triangle method.
Estimation 8M using Ts and TM 5/ TM 7
The first approach of SM estimation was simply using the relationship between
satellite measured surface radiant temperature (T.,) and the ground wetness. The Heat
Capacity Mapping Mission (HCMM) satellite was launched in 1978, which was the first
satellite to be devoted to acquiring highresolution thermal data. From the data received,
the relationship between the ground SM content and observed T., (over the baresoil) was
studied. Because, the wet regions tend to have the lower temperature, this study measured
the surface temperature from satellite to estimate the ground water content. The actual
content of the ground soil water (ground truth data) was measured by the gravimetric
manner (the ratio of the mass of water per the mass of the sampled dry soil). A handful of
ground soil samples were collected over the satellite sensed region and the water contents
were measured in the laboratory. This study shows the correlation of Tf( (calibrated
ground temperature) and the soil water contents was ,2 = 0.74 with a nonlinear
relationship (Heilman and Moore, 1982). The research also concluded that the measuring
of SM was affected by local weather conditions and soil texture. The study has been done
only over the bare soil, therefore the SM estimation over vegetated regions will need a
more practical technique.
In the end of the 1980's, estimation of SM from the bandratio approach was
examined. The bandratio analysis uses the combination of spectral bands rather than
26
single band data. Several researchers implied that the ground wetness could correlate to
the TMSffM7 ratio (TM stand for Thematic Mapper, spectral sensors on Landsat).
Musick extended this idea and examined the TMSffM7 and ground soil water contents
under various soil types. From his study, the wetness ratio had weak linear relations to
the water contents of sampled soil with correlation of r 2 = 0.48. The research also
suggested that the TMSffM7 ratio was largeI y affected by the soil texture and soil type
(Musick and Pelletier, 1988). This is one of the disadvantages of the estimation scheme,
because it is difficult to convert the soil texture type to parameters. Next, we focused on
another estimation technique that is called the Triangle method, which was originally
developed by Carlson (Carlson, 1991). This model estimates ground SM levels from the
relationship between surface radiant temperatures(Tf) and the normalized difference
vegetation index (NDVI). This model is simple, yet significant amounts of SM can be
estimated.
Estimation of8M from Ts versus NDVI and The Triangle Method
In the early 1990' s, it was realized that ground surface water content could be
estimated from the relationship of Tf and NDVI. The relationship of NDVI versus Tr has
been studied by several researchers and recently have shown that there is a high
correlation between remotely sensed vegetation levels and surface temperature (Goward
and Hope 1990; Carlson et al., 1990; Price 1989). This approach uses two parameters NDVI
and TM band6, to estimate ground soil moisture level. The NDVI measures the
vegetation level of the ground, and the Landsat TM band6 measures the surface radiant
temperature Ts.
27
The triangle method is a technique that estimates SM levels from the distribution
of the scatter plot. A scatter plot draws the relationship of NDVI versus T.r. Isopleths are
defined as the lines that have the same SM level over the scatterplot. Therefore, if we
draw the isopleths over the scatterplot, we can find SM level. From Carlson's research
(Carlson et al., 1990), the isopleths are drawn by SVAT (soilvegetationatmosphere
transfer) model, which considers local weather and hydrologic parameters. But in our
triangle method, we simplified the concept and attempted to draw linear isopleths over
the scatter plot using a relatively small area. The details of the process will be explained
with illustrations in the following chapter.
2.7 Summary
In this chapter, we attempted to seek appropriate image segmentation techniques
for soil moisture images. Reviewing the possible image segmentation techniques, we
found large advantages in the watershed segmentation technique  it forms closed and
thin segmentation boundaries. Unfortunately, there are two weak point in the algorithm
 large computational costs and over segmentation issues. For a possible remedy for the
computational costs, we use the image pyramid approach. By using the scale space (the
pyramid approach), significant computational cost can be reduced.
The region merging technique is a possible solution to the oversegmentation issue.
Because the structure of the soil moisture image is complex, we attempted to develop a
new region merging technique by applying the variational technique. This merging
technique is advantageous compared to the conventional technique, because of the
formulation of the equation. By forming the equation, the ability to control the region
28
scalability is obtained. The success of the variational technique largely depends on the
formulation of the energy equation. In this research we focused on the region smoothness
and the cardinality (the number of regions) of the image. The second advantage of the
energy function is the ability to measure the segmentation quality. For SM image
segmentation, the evaluation of the segmentation results are extremely important.
Because poor image segmentation techniques could yield incorrect soil moisture
distributions in the segmentation. The details of the process are funy explained in
Chapter4.
Various scientists have studied soil moisture estimation technique from satellite
imageries. In this research, we selected Carlson's soil moisture estimation technique  the
triangle method, because it enables the estimation of surface water contents with high
reliability. For the practical application of the estimation model to our research, we
simplified the model by using smaller regions. The details of the process are explained
with illustrations in Chapter3.
29
Chapter 3.
The Soil Moisture Estimation Technique from Satellite Imagery
3.1 Introduction
This chapter introduces and demonstrates the soil moisture estimation technique
from satellite imagery. The nature of the original satellite imageries, the mechanism of
the soil moisture estimation technique, and our simplified method are fully explained
with examples.
The potential for soil moisture measurement via satellite was realized about two
decades ago. Only recently, have the estimation techniques been developed for
standardizing the translation of satellite measurements to surface soil moisture content
(Price, 1980). The study of soil moisture estimation techniques is still progressing and a
reliable technique has not yet been established. From satellite sensing, it is still difficult
to precisely measure ground water contents, because complex environmental factors have
to be considered. Exploring these topics is beyond the scope of this thesis. Therefore, our
primary goal is developing an image segmentation technique for the acquired images.
The basic idea of our soil moisture estimation technique is based on Carlson's
ground soil water content estimation model with the triangle method. When reviewing
the related literature, we concluded that the triangle method is one of the most
appropriate approaches to estimating ground soil moisture from optical satellite sensing.
The triangle method uses the relationship between the surface radiant temperature and the
vegetation index to estimate the surface soil moisture level. Full application of the theory
requires extensive computation of weather and meteorological data. Thus, we attempted
to simplify the triangle method to obtain rough (crude) soil moisture images.
30
A visiblered, a near infrared and a thennal infrared band are essential for the soil
moisture estimation technique. Section 3.2 explains the spectral characteristics and their
properties. Section 3.3, explains the soil moisture estimation technique, the scatterplot
and the triangle method. Section 3.4 explains the mechanism and limitation of Oklahoma
Mesonet soil moisture sensors.
3.2 Satellite Images and Characteristics of Spectral Bands
There are several sources of remotely sensed imagery that are currently easily
acquired to compute the soil moisture. Table 3.1 summarizes the type of satellite and the
equipped sensors.
Table 3.1: Summary of description of satellite sensors used for SM studies
(Source: LiJlesand and Kiefer, 1996)
Platform: NOAAl1112 Landsat4/5 SPOT ]3
Sensor: AVHRR MSS TM HRV/MS
Orbit: Near Polar
Resolution(m): I,] 00
Near Polar
80
Near Polar
30,(120)
Near Polar
( 10),20
[I ]O.510.73( 10)
[2]0.500.59
[3]0.610.68
[4]0.790.89
[I ]0.450.52
[2]0.520.60
[3]0.630.69
[4]0.760.90
[5] 1.551.75
[7]2.082.35
[6]10.4] 2.5(120)
[J ]0.500.60
[2]0.600.70
[3]0.700.80
[4]0.801.10
[1]0.580.68
[2]0.731.10
[3]3.553.93
Thennal [4]10.311.3
Spectral Region <  wave length (micro meters)  >
Visible
Blue
Green
Red
Near InfraRed
Mid InfraRed
In order to apply the triangle method, we needed three bands: a visiblered, a near
infrared and a thennal infrared. The Landsat thematic mapper (TM) is superior to the
AVHRR (Advanced Very High Resolution Radiometer) and the MSS (MultiSpectacle
Scanner) in terms of the spectral resolution. The TM sensor has all the necessary bands
31
required for the triangle method, so we selected the Landsat TM bands as our source
imagery. Each of the spectral features and the wave lengths are shown in the previous
table.
Fig.3.l(a) Entire TM image Fig.3.1 (b) The image region over Oklahoma
For our experiment, we have selected a 185 x 170 km regIon southwest of
Oklahoma, which includes Little Washita basin. Historically this is one of the most
studied areas for hydrological and meteorological experiments. Therefore, this area
contains various ground truth sensing points, such as ARS Micronet and several
Oklahoma Mesonet sites. Those sites are constantly monitoring local weather and surface
meteorological parameters. The collection of soil moisture data was started in 1996 by the
Mesonet. A total of nine sites are located over our satellite sensed region. We are
expecting to obtain ground truth soil moisture data from the Mesonet sites. Currently the
Mesonet sites are the sole data points for soil moisture ground truth measurement. But,
the selection of this area has the potential to allow access to additional ground truth data
acquired from related studies, such as soil moisture measurement from microwave
sensors.
32
The satellite TM imagery for this study was acquired on a nearly cloud free
summer day, July 25th 1997. The entire original image is shown in Fig. 3.I(a) and the
related location is indicated in Fig.3.1(b) overlapping the area over a map of Oklahoma.
Displaying the TM image using RGB bands, it is easily realized that the summer season
of Oklahoma is teeming with healthy vegetation. We obtained summer season images.
because the distribution of soil moisture tends to be more uniform in the winter season.
These three spectral bands, red, near infrared and thermal infrared TM bands are
essential for this study. NDVI image is derived from the band3 and band4, and the
scatter plot is drawn by the NDVI versus band6. In Fig.3.2, we depicted the three bands
and NOVI image from a 12 km square subregion. The characteristics of each band are
explained as follows.
Characteristics of Three Spectral Bands
This subsection explains spectral characteristics of each of the characteristics of
the three bands. Fig.3.3 shows typical reflectance curves for three types of ground
features: healthy green vegetation, brown bare soil, and clear lake water. The lines in the
figure represent average reflectance curves and the pattern of the reflectance is applied to
detect ground soil moisture.
TM band3, visible red, locates 0.63  0.69 J1m, is designed to sense chlorophyll
absorption. Within the band length, chlorophyll strongly absorbs the radiated energy; this
is the reason that our eyes perceive healthy vegetation as green in color. The band locates
the first valley of the vegetation curve and is also useful in detecting artificial features
over the image (Lillesand, 1994).
33
:1
,I
.,
,I
,I
Fig.3.2 Three TM band images and NDVI image
Fig.3.2(a) TM Band3 Image
Fig.3.2(c) TM Band6Image
Fig.3.2(b) TM Band4 Image
Fig.3.2(d) NDVI Image
.~
i..
34
The man made features, such as roads and buildings give high reflection, which is
shown in Fig.3.2(a). The redband also tends to be affected by atmosphere, since the band
senses water content in the air. As shown in Fig. 3.3, band3 is located near the peak of
the water reflection line.
Fig.3.3 Typical spectral reflectance curves for vegetation,
soil, and water ( Source: Lillesand and Kiefer, 1996 )
Renectance (%)
60
40
20
..b.3...b.4...
,. ,.
''''' Dry bare soil
 Vegetation
.............. Water
o+r''"Trr~r,.rrr'
0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 2.4
Wavelength ( jim )
Band4, is also called the near infrared band and is located over the peak of the
vegetation curve and after the end of water reflection curve. Tn this band, the reflection
from roads and artificial features are not as noticeable as band3, Fig. 3.2(b). Instead, the
overall reflection from agricultural crops show the highest value. In Fig. 3.3, about
0.7 J.Lm, the reflectance of healthy vegetation increases rapidly. Plant leaves typically
reflect about 40  50 % of the energy within the range. Thus, this band is typically used
to analyze type of vegetation and to detect the vegetation level (Lillesand, 1994). The
band is insensitive to water, so it is sometimes used to discriminate bodies of water from
the image. In Fig.3.2(b), the bodies of water are shown at their lowest intensity (black).
35
From this TM band4 image, the river and small lakes are clearly identified, whereas in
the other bands they are not.
TM band6 measures the amount of infrared radiant from the surface and may
also be called a thermal infrared band. This band is typically used to measure the
distribution of surface temperatures. As we can expect, in Fig. 3.2(c) the bodjes of water
(the river) shows the lowest temperature (as black). The spectral resolution of band6 is
120m, whereas the rest of the TM bands are 30m resolution. The coarse resolution makes
the band6 a blocky image, and therefore it has less distinct appearances than the other
band images.
The normalized difference vegetation index (NDVI) is designed to measure global
vegetation levels. This index is made by a simple combination of TM band3 and band4,
the formula is shown as
NDVI = band3band4.
band3 +band4
Generally, the NDVI ranges between 0.8 for completely vegetated areas, 0.05 for
completely bare soil, and near 0.5 for water bodies (Goward et ai., 1993). The index
shows the amount of vegetation by using the characteristics of the two bands. Remember,
band3 is sensitive to artificial objects, but bandA is not, and bandA is sensitive to the
vegetation but band3 is not. Thus, the index can show the vegetation level with more
contrast than the single band (Jensen, 1996). Fig.3.2(d) is an example of the NOVI
image; the brightest regions (white regions) represent highly vegetated area, which are
distributed along the bodies of water and are assumed to be grouped trees with thick
leaves. The light gray area in the image represents cultivated crops. The darkest regions
36
are bodies of water, the manmade objects (such as roads) and bare soil fields. They are
also clearly identified in the NDVI image.
3.3 The Soil Moisture Estimation Process
In the previous section we explained the characteristics of each band and the
NDVI image. The second step for the soil moisture estimation in the triangle method is to
draw the scatter plot. The scatter plot is drawn using NDVI versus band6 and the plot
indicates the relationship between the vegetation level and the radi.ant temperature.
Fig.3.4 shows the typical distribution of a
scatter plot. There are three clusters in the plot,
a cluster of vegetation, a bodies of water and
the bare soil. The vegetation cluster, which is
the largest cluster, tends to distribute diagonally
with a negative slope. This is due to the leaves
having the ability of transpiration. This tends to
preserve their temperature while receiving solar
radiation.
FigJ.4 The Scatter Plot
High
N
D
V
I
Low ....1....... High
Band6
Typically, the distribution of bare soil fOnTIS a horizontal line in the scatter plot
because of a constant NDVI value. During the daytime, the bare soil is heated by solar
radiation and indicates the temperature depending on the amount of moisture content.
Therefore, the radiant temperature of the soil can be a measurement of the surface soil
moisture content. The third cluster in the plot represents bodies of water, which is usually
located at the lowest NDVI with the lowest temperature.
37
The Triangle Method
The triangle method is a soil moisture estimation technique using the scatter plot.
The name of the triangle method is derived from the shape of the scatter plot. The method
assumes that soil moisture is mostly dry, on
with lower temperatures. Thus, for a given
highest vegetation indicating a higher NDVI
left edge, as in Fig.3.5. The triangular shape
Most Dry
~
Most WetL/
Bare soil lin/
isopleths
Fig.3.5 The Triangle Method
~ ii
+ water body
N
D
V
I
relatively high temperatures
the right edge, and mostly saturated, on the
NDVI,
can be interpreted as the areas with the
correspond to low amounts of soil moisture.
Using this relationship, we can map the Radiant Temperature
moisture level.
According to the Carlson's study, the isopLeths are those lines that have the same
soil moisture level and they are derived from the SVAT (SoilVegetationAtmosphere
Transfer) model, which was created by analyzing the extensive relationships of local
weather and meteorological parameters. Once the isopleths are drawn over the scatter
plot, we can interpret the distribution of moisture from the plot. A very similar approach
has been studied by Price (Price, 1990), and both Carlson and Price have shown that the
method has the potential to estimate surface soil moisture level.
If directly applying the triangle method to a large region, we would have to
consider the local weather and meteorological differences. This requires extensive
38
collection of various local hydrological parameters with additional computations. In order
to minimize local weather influences and in order to simplify the soil moisture estimation
model, we focused on relatively small regions of about 12km x 12km. In other words, we
assumed these local climate variations could be minimized using relatively small regions.
Hence, using the fundamental relationship between the isopleths and scatter plot, and
Fig. 3.6 A scatter plot and
overlapped isopleths
The vertical axis shows normalized NOVI and
the horizontal axis shows surface radiant
temperature in centigrade. Once scatter plot is
drawn isopJeths are overlapped on the graph. The
isopleths are derived from the SVAT model. In
the plot, the moisture level is shown as Mo, Mo =
o represents most dry line and Mo = 1.0
represents most wet line.
Source: NASAEOS Report (1995, Carlson2
)
using a relatively small region, we attempted to draw simplified isopleths over our scatter
plot. In theory, the isopleths are drawn with a slight curve as shown in Fig. 3.6. But, we
have assumed the isopleths are linear and equally spaced in slope from the most dry side
to the most wet side as shown in Fig.3.5. Starting from a drawing of a scatter plot, the
major steps of our triangle approach are shown as follow.
Step I: Locate a vertical line, which is the end of the vegetation cluster.
Theoretically, this line can be substituted as an air temperature line. Locate the bare soil
line, which is the horizontal line.
Step 2: Locate the triangle apex, which should be the end of the vegetation cluster
and on the vertical line. In general, the apex of the triangle is chosen at the total
vegetation point and at the temperature that includes the most pixels within the triangle.
39
Step 3: Assume that the dry line has minimum moisture and the wet line has been
saturated by moisture. Swing straight isopleths from the dry side to the wet side, then
translate the moisture level onto a soil moisture
image map. We used 255 isopleths to draw the 255
graylevel moisture map. During this step, the
bodies of water are recorded as the most wet
region. A soil moisture image derived from the
triangle method is shown in Fig.3.7. The wettest
regIOns are shown as bright pixels and the dry
regIOns as darker pixels. The river and the
neighbor areas are adequately indicated as the
most moist region.
3.4 Mesonet Soil Moisture Sensors
Fig.3.7 The Soil Moisture Image
J.,
"~
I,
}
In the last part of this chapter, we would like to brietly describe soil moisture sensors
in the Mesonet sites. The Oklahoma Mesonet started recording the soil moisture data in 1996.
There are two types of soil moisture sensors in the Mesonet. One is called heat dissipation
matric potential sensors, and the other is called the Time Domain ReJlectometry (TDR)
sensors. The TDR sensor's design is based on a manual device, so there is not an automated
stream of data. Therefore, the data from the automated heat dissipation sensors are the only
possible way to collect ground truth data for soil moi'ture measurement from the Mesonet.
Up to now, nine heat dissipation sensors are located within our entire 185x 170 km region,
and the data are recorded at 30 minute intervals. The sensors are equipped with heaters and
40
they measure two points of temperature, before heating and after heating. Then the potential
wetness of the sensing point can be estimated from the temperature difference 6.T.
According to the Mesonet, the heat dissipation sensor is described as follows.
"The sensors are basically a thermocouple and a heater imbedded in a needle encased
in porous porcelain. The ambient temperature is first measured, then the sensor is heated
twenty seconds, then the temperature is measured again. Depending on how much heat is
absorbed by the soil, which will influence the two difference in two temperatures. Due to the
high capacity of water with respect to soil, it will be difference in the temperature change
depending on how much water is in the soil"(Basara, 1997). Obviously, this sensor does not
directly measure the amount of soil moisture, and the 6.T is influenced by the soil type. The
data require a calibration in order to translate the 6.T to correspond to the gravimetric soil
moisture level. This study is ongoing (Basara and Elliott 1997).
As a test, without using calibration, we simply compared each set of 6.T Mesonet
streamed data to the corresponding soil moisture image. Following the basic relationship, we
could find some correlation between the two data: the larger the 6.T, the drier. When we
compared both data (our estimation and the Mesonet data) only a slight correlation was
observed, ? = 0.43. There are possibly two reasons for this. First, each /1T should be
calibrated by considering the soil type, and second, the Mesonet measure pinpointed the
local data, but these satellite records regionaveraged data (spatial resolution). Without using
any calibration or having a fine ground truth measurement, there will be large differences
between the two data. To obtain ground truth data from another source, a microwave
measurement can be a potential approach. The study on microwave sensing is progressing
over the Little Washita area of Oklahoma.
41
3.5 Summary
This chapter described the mechanism and process of a soil moisture estimation
technique following the triangle method. The derived soil moisture image from the triangle
method is shown in Fig.3.7. Visually, the soil moisture image has a reasonable distribution
of soil moisture. The only pitfall in this process is that we do not have reliable ground truth
data to verify the derived soil moisture images. Research on soil moisture over the region is
progressmg.
On the other hand, our main goal for this thesis is to develop an advanced image
segmentation technique. We are going to start the process using the soil moisture images.
The following chapter provides analysis of the image segmentation technique. Starting from
the definition of image segmentation, we will introduce the best segmentation technique for
the soil moisture images.
42
Chapter 4. The Watershed Segmentation and Region Merging
4.1 Introduction
This chapter proposes a possible solution to the two major weak points of the
watershed (WS) algorithm. In the actual image segmentation, large computational cost
and oversegmentation are two common disadvantages of the algorithm. In this thesis, we
first want to show reasonable solutions toward these two issues of the WS.
The first section, section 4.2, explains the mechanism of the WS segmentation
algorithm. In order to reduce the computational cost, we applied the concept of the image
pyramid to fonn a multiresolution watershed pyramid. By applying the multiresolution
image segmentation approach, we were able to attain faster computation and region
scalability.
Finding a reasonable region growing and clustering technique is a key step to
yield sound segmentation results. Conventionally, region merging is implemented in a
heuristic manner. Here, we propose a wellmotivated region clustering technique by
applying a variational technique. The first step of the variational technique is the
formulation of the energy function. Once the equation is formulated, regions are merged
according to their energy levels. This merging scheme is advantageous over the
conventional scheme due to the ability to control region scale. Additionally, the equation
enables us to measure the segmentation results. Measuring segmentation quality is an
essential task, because it is one way to measure the quality of the complex soil moisture
segmentation results. The details of the variational approach and the merging algorithm
are fully explained in section 4.6.
43
4.2 The Watershed Segmentation Technique
The WS segmentation technique is a powerful image segmentation tool, which
always yields thin and closed contours. But, large computational cost has been a major
disadvantage of the algorithm. This section explains the mechanism of the algorithm,
then eventually associated costs are analyzed. In Section 4.3, the multiresolution WS is
introduced as the remedy to the large computational cost. First, we will explain the steps
of the WS segmentation.
Flow of the WS algorithm
The first step of WS is making a gradient magnitude of the original image 1VI II.
Let us consider the I to be a two dimensional grayscale image which has d.igital values
from 0 to 255. Using x and ycoordinates to represent the two dimensional space, we have
I : (x, Y)7 {O, 1,2, ... , 255},
V XE I, yE I.
The gradient magnitude of the original image I, IVII is given by
(1)
IVI(x,y)l= J{l(x,y+l)I(x,y)}2+{l(x,y)I(x+l,y)}2. (2)
Next, the gradient magnitude image is slightly blurred. The blurred image HI is formed
by applying (convoluting) a Gaussian kernel G to the IVI I. This process is necessary,
because the original integer value of IVI I provides poor representation of a smooth
surface, i.e., each point in the image VI ( x, y ) should have a locally unique value. This
process eliminates the plateaus in the image and simplifies the process to identify local
maxima and minima. This second process is shown as
BI =G*IVI I.
44
(3)
In the third step, all local minima should be identified and all catchment basins
are labeled. Each pixel VI (x, y) is compared with its eight spatial neighbors. If the value
of all of the neighbors are greater than the center pixel, the pixel is identified as a local
minimum. Thus, an element M(x, y) is said to be a local minimum
if M(x, y) <p( xo' Yo)'
where N(x, y) represents spatial neighbors of the pixel at row x and column y in eight
connectivity.
I'll I FigA.1 The location of minima and the
catchment basins in one dimensional example
This one dimensional example shows the
location of minima at the black dots and the
catchment basins as WS1  WS4
'+++1~Z
Once all of the local minima In the image are identified, these minima are
assigned a unique identification (ID) number. The ID is used to label the catchment
basins. In our WS, the minimum following a~gorithm is used for the catchment basins
labeling process, which is discussed bellow.
The Minimum Following Algorithm
Remember that watersheds are defined in tenns of the drainage pattern of rainfall.
Regions of terrain that drain to the same local minimum are defilled as the same
watershed (catchment basin). The same analysis can be applied to an image by viewing
the gradient magnitude as height. The gradient magnitude of the image, VI is used to find
the direction of the drainage.
45
In the image BI, each point of BI(x, y) is examined by eeking the lowest valued
neighbor until it merges into one of the local minima M; or an already labeled catchment
basin. This scheme is called the minimumfollowing algorithm, becau e each element
constantly seeks lower altitude in the image terrain. Once the image element drains to the
catchment basin, it is labeled with the same ID number as the local minimum. In Fig.4.I,
there are four local minima, and four catchment basins which have been formed
(grouped) according to the labeling process.
Once all pixels in the image have been associated with their respective minima,
the output image has the watershed patterns (grouped regions). We will define a function
WS that represents the minimum following algorithm. Then the watershed image W can
be defined as
W =WSd (G* IVI I),
WSd = { (x, y) ~ WS(x, y) =d },
(4)
where WS(x, y) is the watershed labeled region and d is the region ID number. The WS
segmented image W yielded a new independent image. In (4), WSd represents all of the
elements in regiond that have the same catchment basin number d.
The WS boundary detection is the last step of the fixed resolution watershed. The
watershed boundaries are detected by searching the difference of the WS region number.
The WS edge map image, E, can be drawn by detecting and recording the region
differences over W. If we assign" I" for the location of boundaries and assign "0" for the
rest of the area, this process can be shown as
E(x, y) = {~ VW(x,y) >0
otherwise
(5)
46
In Fig.4.1, an original one dimensional signal is divided into four regions, and the dotted
lines represent the edge locations. Unfortunately, the above fixedresolution WS requires
large computational costs when it is applied to a more practical image size. Hence, we
introduced the concept of multiresolution WS for the reduction of the computational
costs.
I Original Image
The Multiresolution Pyramid and the Watershed
If the fixedresolution watershed algorithm is directly applied to the original
image size, there will be large computational expenses. The concept of the image
pyramid is the key to solving this issue. A flow of
the multiresolution watershed (MRWS) is shown
4.3
I Root Level Selection I
I WS Edge Propagation I
FigA.2 Flow of the MRWS
Construction of Image Pyramid
WS segmentation at the Root level
in Fig.4.2. The concept behind the multiresolution
pyramid is to create a scale space where only the
most significant features appear at the coarsest
representation. The multiresolution watershed
pyramid is introduced and demonstrated by Gauch
and Pizer (Gauch and Pizer, 1993). In contrast to
their approach, however, we applied the watershed
at a coarse root level and propagated the edges back to finer pyramid layers without
directly perfonning the WS on each layer.
In order to construct a morphological image pyramid, the original image was
sequentially applied with openclose filtering and subsampling. The process can be
denoted as
47
(L=O,l, ... , n.). (6)
When L = 0, 10 represents the original image and [·12 represents down sampling
by a factor of two. IL is referred to as the parent layer and ILI referred to as the child
layer in the pyramid. With oneoftwo downsampling in both dimensions, each
dimension becomes half of the original size.
In (6), (1 0 K) and (I. K) represent a morphological opening and closing operation
by structuring element K, respectively, The openclose operation works as a low pass
filtering, smoothing the image and erasing insignificant features. The openclose filtering
has been assigned because it produces the least graylevel bias compared to the individual
open or close operation. The morphological filters are known to be superior to linear
filters in tenns of edge localization and feature preservation (Morales and Acharya,
1995). The openclose filtering and subsampling steps are applied to all the pyramid
layers until a preselected root level is forrned.
The Multiresolution WS and New Edge Linking Process
Once the watershed algorithm is applied at the root level L, each image element of
WLl has to be linked to an element in WL. All elements on the root level are linked to a
finer image layer. This process is shown as
{
WL(X,y) ijIVWL(X,y)I=O
WL1(XO'YO) = unde.Jh<ned 1if I tv7WL (x,y)1 '# 0
for all (xo' Yo) E C(x, y, L),
where C(x, y, L) represents the children of element (x, y) at level LI.
(7)
In (7), if IVWL(X, y)1 =0, implying that no change in the watershed label exists in
that neighborhood, we can say that the label for the children of WtCx, y) is known to be
48
equal to the label of Wdx, y). But, if IVW'L(X. y)1 # 0 then the label of the children in
question is undefined. Then, to define the label the watershed is applied only for the
undefined elements. The undefined pixels are usually the WS boundaries of the parent
layer. Therefore, the final step in linking level LJ to level L is to apply the watershed
algorithm on the undefined pixels (propagated boundaries) of Wl.J(i,j).
where HI is the same as defined previously.
(8)
Edge proli'~
.
WS is performed
only at the
boundaries
fter the WS,
borders become
thin again
Fig.4.3 An illustration of our
proposed boundary propagation
process. Once boundaries are
propagated from layer Wl.I to WL,
the WS is perfonned only at the
boundaries (gray pixels). Extensive
computational cost can be reduced
through this approach. The darkest
pixels are the new WS boundaries
that emerged by this process.
This linking process continues, level by level, and terminates when the level
corresponding to the original image resolution is accomplished. Since the image pyramid
structure insures the causality of watershed boundaries, no boundaries can appear in level
LI that do not exist in level L. This process is illustrated in FigA.3 and shows whyour
multiresolution approach reduces computational cost. In each edge propagation step, the
WS is applied only on the propagated boundaries. This algorithm dramatically improves
49
the computational expense. The explanation and computational example are shown as
follows.
Computation Costs in the Multi and Fixedresolution Watershed
Generally, the multiresolution algorithm decreases the computational cost of the
watershed segmentation by an order of magnitude (of the root level). Assuming the
computational cost on a comparison between elements is equivalent to an addition
operation, the cost of perfonning the fullresolution watershed on an NxN image is:
3N2 adds and 2N2 multiples for the gradient magnitudeVoperation, 8 (G· N)2 adds and
9 (G· N)2 multiplies for convolution with GxG size of Gaussian kernel, and 1ON2 adds to
perform the WS operation. This means that the fullresolution watershed algorithm
requITes (l3+9G 2 )N2 addition operations and (2+9G 2 )N 2 multiplication operations,
without including the computational cost of prefiltering.
For the multiresolution algorithm, the watershed is applied at a root level R of
SIze (N/2 R) x (N/2 R), then linked to the finer levels of the pyramid. The cost of
constructing the pyramid using an openclose filter with a kernel, size KxK, is
Rl
4K 2 I)N/2L
)2 adds. Now assuming there areERelements in level R which represent
L=O
watershed boundaries, the watershed has to be performed on 4£R elements to link level R
to level Rl. Approximately, this [ink producesER_J ",,2ER elements in level RI because
connectivity has been maintained. The resulting computational cost of linking the multi
RI
resolution watershed is (13 +9G2) . 4L2L ER adds. The computational cost comparison
L=O
50
for the actual image segmentation between the fixedresolution WS and the muJtiresolution
WS is shown as follows.
For more intuitive understanding, we compared the computational expense of the
multi and fixedresolution WS experimentally. In this experiment, a 512x512 original
sized image, a 3x3 Gaussian matrix, and the 3x3 openclose filter were used. Without
using the image pyramid (fixedresolution watershed), on average it took about 19
minutes (using a Unix Workstation) to process the watershed segmentation on a 512x512
soil moisture image. By applying the multiresolution watershed, at root level two (image
size =256), it took about 1.6 minutes and at root level three (image size =128), it took
about 29 second for the watershed segmentation. Further details and comparisons of the
computational cost on the soil moisture images are shown in Chapte5.
4.4 Region Merging Techniques
Region merging is the key to postprocessing the· watershed segmentation,
because the watershed produces an oversegmented image. Usually, it is difficult to
obtain a reasonable segmentation without applying some kind of region merging.
Therefore, the success or failure of the final segmentation depends upon the region
merging technique.
In this section, three region merging techniques are explained, two conventional
and one new merging technique. The first conventional technique is based on a singlelinkage
region growing scheme. The second is the singlelinkage region growing scheme
with recursive region merging. This algorithm improves upon the first algorithm by
utilizing the concept of clustering hierarchy. For the third approach, a new and more
51
sophisticated region merging technique is introduced,  the stepwise merging
optimization approach combined with the variational technique. The following table
summarizes the characteristics among the conventional and new merging techniques. The
mechanisms of each region merging technique are explained in order in the following
section.
Table 4.1 Conventional and New Merging Schemes
Merging Technique Similarity criterion Hierarchy Category
Single Linkage Averaged Region Intensity No Conventional
Single Linkage Recursive Averaged Region Intensity Yes Conventional
Variational Model Weighted Region Variance Yes New
4.4.1 Single Linkage Region Merging Technique: Conventional
In the singlelinkage region merging technique, the region similarity is measured
by a fixed threshold value. Using the threshold value (clustering criterion), adjacent
region similarities are measured. In this scheme, the graylevel of the each WS mo aic
region is compared to the region clustering criteria. Once the WS is applied to the
original image, it segments the original image into small (oversegmented) WS regions.
Then, the WS mosaic image is formed averaging the WS regions that correspond to the
original image. Thus, the value of the mosaic region Md for region d is defined as
(9)
where nd is the size (number of pixels) of the region d, and I is the original image.
According to this merging algorithm, regions are merged if the adjacent mosaic
graylevel is less than the criterion. Once regions are merged, the mosaic value of the
merged region is updated according to (9). This process is applied to all regions over the
52
image and the region merging is terminated when no more regions can be merged at the
given threshold value.
In this scheme, the segmentation is controlled by the threshold value and the root
level selection. Conventionally, the threshold value and root level are chosen to segment
desired target objects and these parameters are obtained in a heuristic manner. There is no
standard to selecting the threshold value and the root level. Additionally, this scheme is
biased in the merging order, because the merging progresses from one corner of the
image to the other.
The application example of this scheme to a soil moisture image is shown in Fig.
4.4, and the original image is shown in Fig.4.4(a). The region includes a river which is
considered a high moisture content area, and is depicted as white in the image. In this
segmentation experiment, three root levels  root level one, two and three are used. Four
levels of threshold values, zero, five, ten, and fifteen are applied to each root level. By
comparing these three images, Fig.4.4(b), 4.4(f), and 4.4(j), the relationship of the region
scalability and the root level selection is clearly understood.
A selection of a low root level (Root= 1) will make fine scale regions, and the fine
features (ex, the river) are still preserved as seen, in Fig.4.4(b). But, in root level two and
three, Fig.4.4(f) and Fig.4.4(j), the river regions have been merged (destroyed) to other
regions even before the start of the region merging process. From the results, it is
understandable that the selection of root level two and three are inappropriate for the
image segmentation. Now, let us look at the results of three segmentations from root level
one. When threshold T=15 is applied at root one, Fig.4.4(e), the river is merged to other
regions.
53
Fig.4.4 SM segmentation results from Single Linkage Region Merging (Fixed Threshold)
Original WS Mosaic Image
(a) Root = 0, Root size = 512
Root =I, Root size =256
(b) T=O, R=2151 (c) T=5, R=475 (d) T= 10 , R=28 I (e)T=15, R=233
Root=2, Root size = 128
(f)T=O, R=329 (g)T=5, R=265 (h) T=IO, R=158 (i) T=15 , R=93
Root=3, Root size = 64
(j)T=O, R=119 (k)T=5, R=73 (I) T= iO, R=39 (m) T=15, R=30
( T denotes the threshold value. and R denotes the number of regions in the image)
54
Yet, the merged results show many small regions (shown as specs), which is an example
of a poor segmentation. Because of lack of the region scalability, the image has (mix)
small regions and large regions. Fig.4.4(e) still has more than 200 regions, and even the
river was merged! We can even visually recognize the weakness of this merging
algorithm, because we want to segment (classify) fewer regions and preserve finer
features, such as the river. And in a latter section, we will measure these segmentation
results using an appropriate measuring scale.
Unfortunately, this merging scheme is too awkward to apply to these complex soil
moisture images. In the following section, we will introduce the modified version of the
merging scheme  the single linkage region merging with recursive threshold algorithm.
4.4.2 SingleLinkage Region Merging with Recursive Threshold: Conventional
As we have seen, the first merging technique
Original WS Segmenlation
was inadequate for the SM image segmentation. The
single linkage region merging with recursive
threshold technique, Fig.4.5, has been developed to
improve the weakness of the previous merging
scheme (Meyer, and Beucher, 1992). This merging
method can be applicable to more complicated and
low contrast images. Here the threshold is not fixed;
~I Threshold I
Region merging Ic:2
~
Merged Segmentation
Fig.4.5 Flow of the Recursive
Thresholding
it is gradually increased. Using the merging mechanism, regions are merged from similar
regions, so distinguished regions are preserved until the last merging stage. The
composite graylevel of each mosaic region is used for the merging criterion just as it was
in the previous merging scheme. But in this algorithm, the most similar pair of regions is
55
selected from the entire WS mosaic regions and merged. When no regions can be merged
at a given threshold value, the threshold value is incremented slightly and the merging
continues until a desired number of regions are obtained.
One advantage of this merging scheme is that it has an. ability to yield the desired
number of segments. Also, merging order has no bias because the merging is progressed
from the most similar regions. This merging order makes a hierarchy of region merging
(merging hierarchy), whose mechanism is explained below.
Hierarchy of the Region Merging
Starting from an oversegmented watershed
mosaic image, a hierarchical merging structure
represents the merging order in the segmentation
structure. In this scheme, the regions are merged one
by one according to the merging criterion. The
merging hierarchy can be visualized using a tree
Fig.4.6 An illustration of
Tree Diagram
diagram, which is shown in FigA.6 (Beaulieu, and Goldberg, 1989). In the diagram, each
node represents a regi.on and the links between the nodes indicate the paths of the
merging. These regions, at the lower level, are clustered in the early merging stages and
form a higher level of segments. The hierarchical levels can be related to the resolution.
Thus the merging hierarchy also represents the region scalability.
This algorithm can be considered as a reasonable merging scheme, but one
disadvantage is that it does not consider the region size in the merging process. Small, but
extremely high or low intensity regions do not merge with neighbors and are left until the
last merging stage. This is an issue in the controlling of region scalability. Using Fig.4.7,
56
we show the results and illustrate the weakness of the merging algorithm. The topleft
image Fig.4.7(a) is an original oversegmented WS image  the same image as the
previous example. Fig.4.7(b) is the segmentation result at the number of regions = 100.
while Fig.4.7(c) is the segmentation result at the number of regions =30.
Fig.4.7 SM segmentation examples from Single Linkage Recursive Threshold
Root level = I, root size =256
(a)Original SM mosaic image (b) Number of regions = 100 (c) Number of regions = 30
(d)Original SM mosaic image (e) Number of regions =50 (f) Number of regions =30
" ,0 ,
~ ... • ...~
••• •
....
..
•
The second row of Fig.4.7 shows the segmentation results from another SM
image. Starting from an oversegmented WS image, Fig.4.7(d), the segmentation rcsulls
are shown in Fig.4.7(e) and Fig.4.7(f) at the number of regions is 50 and 30 respectively.
From the segmentation examples, improvements can be recognized and compared to the
previous merging scheme. But, this segmentation scheme still merges homogeneous
regions too rapidly. Large regions of similar graylevel are merged into one region. while
small scale regions remain unchanged as shown in Fig.4.7(e) and Fig.4.7(f). Therefore,
57
this algorithm also lacks region scale controllability. Our goal is to segment regions by
fonning unifonn scale regions yet minimizing the loss of original SM distribution.
In order to solve this dilemma, a new merging method is introduced  the stepwise
optimized clustering algorithm using the variational technique. This new merging
algorithm resolves the weak points of the conventional (previous) merging algorithms.
One of the major improvements of this algorithm is the weighted regions variance is
used for the similarity measurement. This technique is quite appropriate for the
segmentation of soil moisture images, because the images tend to show lower contrast
and the graylevel varies gradually. Also, this algorithm considers the region size during
the merging process. Additionally, using the concept of image energy, we can evaluate
the segmentation quality. Being able to measure and evaluate the segmentation result is
important. In the following section, a new concept, the variational technique with an
energy equation is introduced.
4.5 The Variational Technique
The variational technique is a new approach compared to the conventional region
merging schemes. Using the variational technique, we formulate an energy equation, then
by solving the equation, we segment images. So, fonnulating the equation is the key step
in the variational model. First, we have to translate the properties of the image
segmentation to form an appropriate function.
In our image segmentation (region merging), we focused on two terms  the
number of segmented regions and region smoothness to form our energy equation. The
smoothness and the number of regions represent opposite segmentation statuses. If a
58
»
segmented image has fine scale(large number of regions), each region will have uniform
(smooth) elements in the region. On the other hand, in a coarse segmentation (a few
number of regions), inhomogeneous (unsmooth) elements are in each region. Therefore,
the region smoothness and the region scale (the number of the regions) are considered in
forming our image segmentation function.
Another advantage of the function is that the segmentation quality can be
measured according to the energy level. Having an appropriate measurement to evaluate
the merging quality is important. In particular, SM images are complex and the regions
tend to have uniform graylevel, which makes it very difficult to compare the
segmentation results visually. Without depending on the image type (simple to complex),
we can measure the quality of segmentation from various region merging schemes. The
process of our energy equation formulation is explained in the following section.
4.5.1 The Energy Function Formulation
As we mentioned previously, we are focusing on the region smoothness and the
number of regions. Our energy function, or cost function, describes the relationship
between the two terms. The first term of the energy function is region variance. We
measure region smoothness using the variance of the region and it is weighted according
to the size of the region. The weighted variance (or sum of variance) of a region i is
defined as,
Weighted Variance (SOV) =S;' Yare OJ)' (II)
Sj represents the size of the region Oi, and Var(·) denotes variance of the region OJ. This
term measures smoothness of the region while also considering the region size, and is
often called the data term in the energy function. The next term is the cardinality of the
59
segmentation. Card(O/) denotes the number of segments in the entire image, I. This tenn
is called the scalability term or cardinality term and represents the energy of the region
scale.
Total energy is gIven by combining the two terms  the variance and the
cardinality tenn. The total energy of an image is given by the summation of the weighted
variance and the cardinality of the image.
E image =LiSj' Var(O) + A(Card(O,)). (12)
Thus, the total energy measures the regions' smoothness and the number of regions at the
given il. In (12), the Ais called a scalability parameter, which controls the scale of the
regions. The physical meaning of Ais the cost for merging. The equation (12) can be
seen in Morel (Morel and Solimini, 1994). But in our merging scheme, Astarts from a
low number, then regions are merged from the most similar regions, and then A is
gradually and monotonically increased until desired number of region is obtained.
The following example explains how the energy function works by providing a
simple illustration, assuming there are only two regions, region i and j. This example is
convenient, because we always merge a pair of regions at once in our merging scheme.
According to the above equation, we compute two energy functions before merging and
after merging according to the equation (12).
E befOl'emerge =Sj' Var(Oj) + Sj' Var(Oj) + 2A.
E aflermerge =S;Uj' Var(Oj uOj ) + il.
The dataenergy increases when the regions merge, Le., dataenergy in two regions before
merging are lower than after the merge. This can be shown by a example via a simple one
dimensional matrix as shown below,
60
MA =[9 8 6 5 4 3 2 2 3 4; 4 3 2 2 1 I I 2 3 4] = [M1 ,M2 ].
Assuming M1 and M2 are independent WS mosaic regions.
Fi.g.4.8(a) Fig.4.8(b)
e _ ltl 12 If ,. l' to
Fig.4.8(c)
[3.;]
Fig. 4.8(a) is a graph that indicates the elements
of M1 and M2 • Fig 4.8(b) shows region M1 and
M2 before merge. Fig 4.8(c) shows the merged
pattern after the two regions are merged.
Fig. 4.8 An illustration of a merging process
In this example, Yare M1 ) =5.82 and Yare M2 ) = 1.34. The weight is 10 pixels,
thus the weighted variance (SOV) is given as SOY J =58.2, and SOY 2 = 13.4. Using
equation (12), the region energy, before and after merging, is given by
Ebeforemerge =SOV1+SOV2 +2A =71.6+2A,
E after merge = SOVlv2 + A = 95.7 + A.
(13)
(14)
By solving the two equations, the scalability parameter Ais found. The energy gap .1 E,
before and after the merge is defined by
.1E =E afler merge  E before merge .
Without considering A, .1 E has a positive number, i.e.,
(15)
E after merge > E before merge or E after merge  E before merge = .1. E > O. ( 16)
Now, if we consider the scalability parameter A, we accept the merge only if .1. E is
negative, i.e., a pair of regions can be merged only if .1.E < O. This means the total image
energy must decrease during the merging process. According to this concept, Ais given
by solving the equations (13) and (14). For .1 E < 0,
61
95.7 + A <71.6+2A,
:.24.1 < A.
Thus, the regions are merged by decreasing the total image energy only if A> 24.1 in this
example. When A= 24.1, it is called the critical merging point and if Ais beyond the
critical merging point, the merging decreases the total image energy. In order to clarify
the energy level, several Avalue are assigned to compute the region energy.
a .e e re a lOns lp 0 an
A E before merge E afler merge liE
10 91.6 105.7 up
20 111.8 115.8 up
24.1 119.8 119.8 0
30 130.7 125.7 down
T bl 42Th 1 ( h' fAd Li E
From this simple example, it is known that the scatability parameter ( A) works as
a cost for merging. Additionally, Acontrols the region scales, because in the equation,
region size is considered. Therefore, A can be also considered as a region scale
parameter. When a small Ais applied, fine segmentations (large number of regions) are
yielded. When a large Ais applied, coarse segmentations (few regions) are yielded. When
the A=0, no regions can be merged, because without considering the A, it always holds
that
Li E = E after merge  E before merge> 0,
which does not meet the merging criterion liE < O.
This section studied the mechanism of the region merging process uSing our
energy function. In the following subsection, we would like to show the advantage of the
weightedvariance for the similarity criterion.
62
4.5.2 Similarity Measurement by the Variance versus Average of Region Graylevel
In the conventional region merging scheme, the average of the region graylevel
was used for the similarity measurements. But, in the new merging scheme the region
variance is used for the similarity criterion. There is a significant difference between the
new and conventional schemes, because the region variance is more sensitive than the
graylevel in comparison. This can be shown using an example. Shown below are the one
dimensional regions (MA ) and (MB). The MB has modified the first and last terms of the
sample region, MA•
MA =[9 8 6 5 4 3 2 2 3 4; 4 3 2 2 2 3 4] = [M) ,M2 ).
MB =@8 6 5 4 3 2 2 300 32 2 2 30 =[M3 , M4 ].
If we compare the average of the two regions, Ave(M)) = Ave(M3) and Ave(M2) =
Ave(M4 ), but in the variance, Var(MI) t:: Var(M3) and Var(M2) t:: Var(M4 ). When we want
to detect the difference between M1 and M3, or M2 and M4, how should we measure the
differences? If we use the region average to measure the similarity, this criterion
(region's average) can not detect the differences. Instead, if the region variance is used to
measure region similarity, it can detect the transition of the region elements. During the
merging process, it is possible that two regions' average are same, even if the large
difference of the components (pixel values). Therefore, this causes merging error in the
conventional merging scheme.
This subsection explained our new merging scheme and the similarity criterion
using a simple example. In the following section, we expand this concept to the entire
image. A hierarchical region clustering and hierarchical stepwise optimization clustering
63

algorithm are introduced. This algorithm merges the regions step by step according to the
merging criterion, therefore this process forms a hierarchical merging structure. The
following subsection shows how the hierarchical structure is effectively applied for t.he
region merging scheme.
4.6 The Hierarchical Stepwise Merging Algorithm with the Variational Technique
In this algorithm, the hierarchical clustering starts from an oversegmented
original watershed segmentation, assuming it has N regions. These regions are considered
as nodes, and the number of the regions is sequentially reduced by merging. At each
iteration, the cost for merging C(Ri . Rj ) is calculated for every pair of regions (Ri , Rj ).
Then the one pair of regions having the minimum merging cost is selected from entire
regions and merged. This merging process is repeated sequentially until the desired
number of regions are obtained.
One of the limitations of the hierarchical merging approach is the large
computational cost for a large data set (large image size), because the merging cost for all
of the possible pairs of regions have to be computed. If there are N regions, this
computation can be N x (NI). In our region merging case, however, only adjacent
regions can be merged. This reduces the number of potential merging combinations per
iteration to N x M, where N is the number of regions, and M is the average number of
neighbors. M is usually a small number, on average around 3~M~8, and is quite
independent of N (Beaulieu and Goldberg, 1989). Additionally, a merge affects only the
surrounding regions, therefore only the adjacent regions need to be updated for the next
evaluation. As a consequence, only a limited number of new segment pairs need to be
64

considered at each merging iteration. This is a major computational advantage obtained
from the concept of the adjacent region clustering.
The algorithm of hierarchical merging with a sequential optimization process is
now explained. The process starts with an initial watershed segmentation, Po ={R I , R2,
R3, .•.. Rn}, and at each iteration, it merges pair of regions that have minimal merging
cost. C,) denotes the cost of the merging a pair of regions. i (R;) and region j (Rj ). The
flow of the merging algorithm is as follow:
I  Initialization process:
1) Po ={Rj , R2• RJ , ... ,Rn } (initial segmentation derived from the watershed).
2) A=0, scalability parameter starts at 0, merging can start somewhere A. >0.
3) Calculate SOVk and NBk (neighbors of region k) 'if Rk E po.
where k is the image cardinality.
4) Calculate the merging cost CS ={C;,j I R) E NB; }.
II  Merge most similar a pair of regions (the lowest cost region):
I) Find a pair of region that meet
CII." = Mm' .lmum(C;'j) flOm the entire region.
C·.lees
2) Region Rm is merged; Rm =(Ru u Rv), which means replacement of the pair
ofregions to a newly merged region  m,
3) Calculate SOVm of the merged region.
4) Update neighborhood information, NBm = (NBu u NB.. ) n {Ru • Rv } I,
which revises the information of the neighborhood
5) If no region can be merged at the given A.. increment it A= A+I.
I Taking the intersection with the complement corresponds to removing those elements from the set.
65
ill  Stopping condition: Stop the merging algorithm if desired number of regions is
obtained.
The initialization process, finding NBk and computing SOV k , are performed only
once for a selected root level WS segmentation image. Thus, this algorithm is also
designed to reduce the computational cost. In the initialization process, the computational
cost is a function of the number of regions, the image size, and the number of neighbors
per region. Instead, if the iteration steps are short, the computational cost is mainly a
function of the number of regions R". The number of iterations depends on the number of
initial regions, because each iteration reduces the number of segments by one.
Measurements of the Segmented Images
Once images have been segmented, the segmentation has to be evaluated to
measure the quality. The quality can be measured by the total image energy according to
(12). Now, assuming we want to compare two segmentation results from different
techniques. If both images have the same cardinality (number of regions), we can
simplify the equation (12) by only considering the varianceterm. Then the segmentation
quality can be evaluate by
IQ image =LiS;' Var(O) =Image variance. ( 17)
The IQ represents image segmentation quality. This equation simply measures the
smoothness at a given cardinality. Just like the image energy. at the given number of
segments, the lower the IQ represents the better segmentation. When we compute image
energy from different segmentation techniques, it is difficult to select a suitable A.
Therefore, if images have the same cardinality, we can compare the segmentation quality
among different segmentation techniques by computing the image variances. This
66
segmentation evaluation technique is used when we compare the conventional and the
new image segmentation results in Chapter5.
Mean squared error (MS£) is often used to measure the differences of the
processed image and the original image. The mean squared error is defined as
( 18)
where I org is the original image and Iseg is the segmented image. If the segmented image is
an adequate representation of the original image, the MSE should yield a lower value.
In this thesis, we evaluated the segmentation results by measuring both image
energy (or image variance) and the MSE. The lower these numbers, the better the
segmentation results. All of the application results are shown in Chapter5.
4.7 Application of the Variational Method on Synthetic Images
The previous section explained the segmentation evaluation techniques and the
process of our image segmentation technique. This subsection explain the relationship
between the segmentation result and the image energy using simple synthetic images.
A synthetic test imageA, which is 8x8 square, is shown in FigA.9. There are five
regions, RI  Rs. and each region has a different graylevel. The initial weighted variance
of each region and the region number is shown in the following table.
Table 4.3 Initial variance of
the test image
Fig.4.9 An original synthetic test image and the
initial partitions
~....
1',', .
t'o ..l,:,.
~,..
i~.j
Fig.4.9(a)
R1
Rz
R5
R4
R3
Fig.4.9(b)
Region Initial SOV
R1 296.1
R2 206.7
R3 139.0
R4 4119.6
Rs 57.3
67
In this experiment, we merged the original image until two regions were formed
from the original five. There are a total of thirteen possible patterns that can be formed
for the two region segmentations.
These patterns are shown in the Fig.4. 10 P2( I )P2( 13). The segmentation result
from the variational technique is shown in Fig.4.l0 P2(l3)vt. The number of possible
pattern is much less than 5C2 (combination of five from two), because regions will merge
with only those connected regions.
Fig.4.10 Thirteen possible segmentation patterns
All of the thirteen patterns are computed using the image energies and the MSE. The
results are summarized in the following Table 4.4. The pattern numbers are shown from
P2(l) through P2(13)vt, and the P2(l3)vt is the segmentation result from our variational
technique. The energy is calculated according to the equation (l2), and the mean squared
error is computed from equation (18).
68
Table 4.4 ea elulated MSE and the energy ~,or the th"Irteen patterns
Pattern P2(1) P2(2) P2(3) P2(4) P2(5) P2(6) P2(7)
MSE 109 89.4 80.5 83.7 74.4 109 79.6
E (KIO
j
) 322 206 89 304 282 317 189
Pattern P2(8) I P2(9) P2(W) P2(1l) P2(12) P2(13)vt
MSE 114 91.2 116 102 101 53.8
E (KI0
3
) 233 178 322 287 284 82
As shown in above table, both the segmentation energy and the MSE, which from
the variational technique indicated lowest value. In other words, our variational algorithm
found the best segmentation in the two region segments. Next we want to show the
segmentation results that form four regions and then three regions and consider the path
of the region merging.
Merging Path and Local Minimum Image Energy
In the previous section, we studied the segmentation energy of only two regions.
Here, we want to examine the image energy for three and four region segmentations to
show the merging path and the energy level. We want to show that the merging technique
consistently produces the lowest image segmentation for each number of segments.
Energy Computation for Four Regions
There are a total of eight segmentation patterns that can be formed from the given
image pattern. We have computed the energy of all the possible segmentation patterns,
and the results are shown in Table 4.5. In the table, P4(8)vt is the segmentation pattern
from our variational algorithm. The error and energy are the lowest among all of the
possible segmentations. Next, we repeated the same computations for three regions.
69
Table 4 5 CaIcuIated MSE and the energy for t·he POSSI'ble patterns or our se ,nentatlon
Pattern P4(1) P4(2) P4(3) P4(4) P4(5) P4(6) P4(7) P4(8)vt
MSE 49.8 41.5 32.1 26.5 35.1 32.9 88.3 15.0
E (llIOJ) 170.1 114.7 61.2 17.9 25.4 44.0 213.2 16.3
Energy Computation for Three Regions
In order to examine the energy level and the errors for three regions, we computed
all possible segmentation patterns which form three regions. There are a total of 20
possible patterns. The segmentation energy and error (MS£) are summarized in the
follow.ng table. Again in this experiment, our variational merging algorithm found the
lowest energy segmentation, which is indicated as P3(20)vt in Table 4.6.
Table 4 6 CalcuIated MSE and the energy for th·e pOSSI'bIe pattems for three segments
Pattern P3(1) P3(2) P3(3) P3(4) P3(5) P3(6) P3(7)
MSE 51.6 50.] 44.4 74.8 48.6 65.2 88.3
E ()(JO"\ I] 6.4 113.6 76.3 284.3 70.9 121.3 211.9
Pattern P3(8) P3(9) P3( 10) P3(ll) P3(12) P3{ 13) P3(l4)
MSE 50.4 99.1 79.9 43.5 72.6 77.7 ]07.1
E (xIO:!) 57.2 233.7 153.9 36.8 269.5 209.4 323.0
Pattern P3( 15) P3(16) P3( J7) P3( 18) P3( 19) P3(20)vt
MSE 76.0 48.6 65.1 66.6 114.9 34.5
,
E (XIO
J
) 190.7 74.3 184.3 173.6 227.8 29.4
Through these experiments, we computed all possible segmentations for two,
three, and four regions. The segmentation results from our algorithm using variational
technique yielded the lowest energy and the lowest error of any segmentation pattern for
each number of segments. Another interesting point is that this algorithm found the path
of the lowest energy in each segmentation. This is a meaningful result.
70
FigA.ll The region merging results from variational technique on a synthetic imageA
(a) 5 regions (b) 4 regions (c) 3 regions (d) 2 regions
The segmented image, FigA.ll (d), is the result of our two region segmentation
from our region merging technique. As we explained earlier, the segmentation pattern has
the lowest energy and MSE of any segmentation pattern(with two regions). Just as for the
two region segmentation, all of the paths (four and three regions) also had the lowest
energy for each number of segments. The merging path is shown in Fig4. 1I.
FigA.12 The region merging results from variational technique on a synthetic imageB
(a)11 regions (b) 9 regions (c) 7 regions (d) 5 regions
We also examined the same experiment on the second synthetic image, Fig.4.12.
The results showed the merging path from the original partition, FigA.12(a) to five
regions (three graylevel classification), FigA.12(d). From the variational technique, the
lowest energy segmentation patterns were found for each number of regions.
In this section, we examined our new region merging technique showing the
merging results on simple synthetic images. The results from the synthetic images show
adequate segmentation results. The results from the variational technique yielded the
lowest MSE and the lowest image energy tn each segmentation. These are encouraging
results and it increase our confidence in applying this merging technique to more
complex images. In the following chapter, we will apply this merging technique to more
71
realistic images  soil moisture images. The segmentation results from the conventional
segmentation technique and our new merging technique are fully compared.
4.8 Summary
This chapter explained our solution to two issues of watershed segmentation large
computational cost and oversegmentation. To reduce the computational cost, we
applied the concept of the image pyramid. Gauch and Pizer introduced the multiresolution
watershed technique(Gauch and Pizer, 1993), but in our multiresolution
watershed pyramid WS is applied at a root level and the WS boundaries are propagated to
the original image size. This approach can reduce the computational cost significantly,
because the WS is applied to each intermediate layer only on the boundaries.
For the application of the WS algorithm to the soil moisture imagery, we
introduced the new merging algorithm by applying the concept of a variational model.
We formulated an energy function, then progressed the merging according to the energy
level. The original energy function can be seen in the Morel's study. But in our merging
scheme, the region scale parameter, Ais increased gradually until desired number of
regions is yielded. We applied this process, because it is a possible way to find a local
minimum energy in the cardinality. From our synthetic image examples, this merging
technique adequately found local minimum energy in each segment. The segmentation
results also showed the lowest energy and the lowest MSE in each segmentation result.
Using the concept of image energy with the energy equation, we obtained a new
image segmentation evaluation criterion. In the following chapter, we wiIJ apply the new
merging algorithm to the actual soil moisture images. The segmentation results are
72
measured by both MSE and image energy (image variance), and these results are
evaluated by comparing the conventional segmentation with the new segmentation
method.
73
Chapter 5. Results and Conclusions
5.1 Introduction
In the previous chapter, we introduced a new region merging technique and a
segmentation evaluation criteria using a variational technique. This chapter demonstrates
the region merging techniques and summarizes the segmentation results. Image
segmentations are implemented by two types of region merging techniques and the
segmentation results are compared. The segmented images are measured by two metrics,
the image energy and mean squared error (MSE) as explained in Chapter4. The smaller
values represent the better segmentation results in both measurements.
Another improvement on the conventional watershed segmentation is the
application of the multiresolution watershed pyramid. Using the multiresolution
watershed (WS), the computational time is significantly reduced. The multiresolution
pyramid creates a scalespace and the WS is applied at a selected root level, which is a
coarse representation of the original image. Once the WS is applied at a root level, the
WS boundaries are propagated to the original image size. During lhe propagation process,
the WS is applied only on the boundaries in each layer. Therefore a significant reduction
in computational cost is expected. We compared the computational cost with and without
applying the multiresolution pyramid on the soil moisture images, and the results are
shown in this chapter. Section 5.3 concludes and discusses all of the research findings
and contributions in this thesis. Finally, section 5.4 mentions some proposals for future
work.
74
5.2 Image Segmentation Results
The objective in this section is to compare and contrast segmentation results from
the new and conventional region merging approaches. In this experiment, a total of five
images are used. For the first two, we selected relatively simple images, which have a
clear target object and are well contrasted. These types of images are often used for the
evaluation of image segmentation techniques.
For the soif moisture image segmentation, we chose three subregions from the
original satellite imagery. Segmentation conditions are summarized in Table 5.1 and the
segmentation results are examined in the following section.
Table 5.1 Application of Image Segmentation
Category Image name: Image size: Root level: Merging method Figure number
Test Image Swan 256 1(128) Recursive Threshold Fig 5.1(a)
Swan 256 1(128) Variational Technique Fig5.I(b)
Leaf 256 2( 64) Recursive Threshold Fig 5.2(b)
Leaf 256 2( 64) Variational Technique Fig 5.2(c)
Soil Moisture SMr13e07(River) 512 1(256) Recursive Threshold Fig 5.3(a)
SMr13e07(River) 512 1(256) Variational Technique Fig 5.3(b)
SMr04e04(Field) 512 1(256) Recursive Threshold Fig 5.4(a)
SMri)4e04(Field) 512 1(256) Variational Technique Fig 5.4(b)
SMrlIe lO(Lake) 512 2(128) Recursive Threshold Fig 5.5(a)
SMrllelO(Lake) 512 2(128) Variational Technique Fig 5.5(b)
5.2.1 Application of Region Merging to Test Images
The purpose of the test images is to show the efficiency of the region merging
methods before applying them to complex soil moisture images. If the segmentation
75
technique shows valid segmentation results from relatively simple images, the
segmentation results from the soil moisture images will be more reliable. A swan image
and a leaf image are chosen for the test images. Each of these images is well contrasted
and has a clearly identified target object. In order to compare the region merging
schemes, the segmentation results are measured by both meansquarederror and the
image variance. The segmentation results are explained below.
Segmentation Results from the Swan Image
The segmentation results from the swan image are shown in FigS I(a) and
Fig.5.I(b). Fig.5.l(a) shows the segmentation results from the conventional merging
scheme using recursive thresholding. Fig. 5. i(b) shows the segmentation results from the
new merging scheme using the variational technique. The topleft image in the figure is
oversegmented at the root level WS mosaic image (region merging starts from this
image) and the rest of the images show the region merged results. In the figures, R stands
for the number of regions in the image, image variance is denoted as V and meansquared
error of the image is denoted as MSE. Starting from the oversegmented original
WS mosaic image, we attempt to merge them to a desired number of regions. In this
experiment, the number of regions is selected from 300 to three regions. Comparing
FigS I (a) and 5.l(b), visually there are few differences. But each image from the new
merging scheme, in Fig.5.1 (b), has superior variance and MSE to those of the
corresponding conventional segmentations, in Fig.5.) (a). In the next test image, we
corrupt an original image by saltandpepper noise, then examine the same sequence for
the Leaf image.
76
Segmentation Results from the Leaf Image
In this experiment, we wanted to demonstrate how noise affects the WS
segmentation and the region merging process. A corrupted image is made by adding 30
percent saltandpepper noise to the original image. During the multiresolution WS
segmentation, each layer of the image is sequentially openclose filtered, then subsampled.
The original image, noisy image, and filtered images are shown in the
Fig.5.2(a). From the images, the filtering effects are easily observed. In root level three,
the noise is eliminated by the sequential filtering, yet the original leaf still can be
recognized. This root level is selected f