Region Merging
(Jain et al., section 3.4.1, 3.4.2)
- Region merging operations eliminate false boundaries and spurious regions by
merging adjacent regions that belong to the same object.
- Merging schemes begin with a partition satisfying condition (4) (e.g., regions pro-
duced using thresholding).
(4) P(R i ) = True
- Then, they proceed to fulfill condition (5) by gradually merging adjacent image
regions.
(5) P(R i ∪ R j )=False
(1) Form initial regions in the image.
(2) Build a regions adjacency graph (RAG).
(3) For each region do:
(3.1) Consider its adjacent region and test to see if they are similar.
(3.2) For regions that are similar (i.e., P(R i ∪ R j )=True), merge them and
modify the RAG.
(4) Repeat step 3 until no regions are merged.
-2-
• How to determine region similarity?
(1) Based on the gray values of the regions.
* Compare their mean intensities.
* Use surface fitting to determine whether the regions may be approxi-
mated by one surface.
* Use hypothesis testing to judge the similarity of adjacent regions
(assumes that the intensity values are drawn from a probability distribu-
tion).
(2) Based on the weakness of boundaries between the regions.
• Region merging using hypothesis testing
- This approach considers whether or not to merge adjacent regions based on the
probability that they will have the same statistical distribution of intensity values.
- Assume that the gray-level values in an image region are drawn from Gaussian dis-
tributions.
(gi − )2
1 −
p(gi ) = e 2 2
√
2
- We can estimate the parameters of the Gaussian using Maximum-Likelihood:
1 n 1 n
ˆ=
n
Σ gi ,
i=1
ˆ =
2
n
Σ (gi −
i=1
ˆ)2
-3-
- Given two regions R 1 and R 2 with m 1 and m 2 pixels respectively, there are two
possible hypotheses:
H0 : Both regions belong to the same object. The intensities are all drawn from
a single Gaussian distribution N ( 0 , 0 ):
H1 : The regions belong to different objects. The intensities of each region are
drawn from separate Gaussian distributions N ( 1 , 1 ) and N ( 2 , 2 ):
- The joint probability density under H 0 , assuming all pixels are independently
drawn, is given by:
m 1 +m 2 (m 1 +m 2 )
1 −
p(g1 , g2 , . . . , g m1 +m2 |H 0 ) = Π p(gi |H 0 ) = e 2
i=1 (√
2 0 )m1 +m2
The joint probability density under H 1 is given by:
m1 m2
1 − 1 −
p(g1 , g2 , . . . , g m1 +m2 |H 1 ) = e 2 e 2
(√
2 1 )m1 (√
2 2 )m2
- The likelihood ratio is defined as the ration of the probability densities under the
two hypotheses:
m 1 +m 2
p(g1 , g2 , . . . , g m1 +m2 |H 1 )
L= = 0
m1 m2
p(g1 , g2 , . . . , g m1 +m2 |H 0 ) 1 2
- If the likelihood ratio is below a threshold value, there is strong evidence that there
is only one region and the two regions may be merged.
-4-
• Region merging by removing weak edges
- The idea is to combine two regions if the boundary between them is weak.
- A weak boundary is one for which the intensities on either side differ by less than
some threshold T 1 .
- The relative lengths between the weak boundary and the region boundaries must be
also considered.
Approach 1
Merge adjacent regions R 1 and R 2 if
W
> T2
S
where W is the length of the weak part of the boundary, and S = min(S 1 , S 2 )
is the minimum of the perimeter of the two regions.
-5-
Approach 2
Merge adjacent regions R 1 and R 2 if
W
> T3
S
where W is the length of the weak part of the boundary, and S is the common
boundary between R 1 and R 2 .
-6-
Region Splitting
(Jain et al., section 3.4.3)
- Region splitting operations add missing boundaries by splitting regions that con-
tain parts of different objects.
- Splitting schemes begin with a partition satisfying condition (5), for example, the
whole image.
(5) P(R i ∪ R j )=False
- Then, they proceed to satisfy condition (4) by gradually splitting image regions.
(4) P(R i ) = True
- Two main difficulties in implementing this approach:
* Deciding when to split a region (e.g., use variance, surface fitting).
* Deciding how to split a region.
Regular Decomposition
(1) If P(R)=False, split R into four quadrants
(2) If P is false on any quadrant, subsplit
-7-
Region splitting and merging
(Jain et al., section 3.4.4)
- Splitting or merging might not produce good results when applied separately.
- Better results can be obtained by interleaving merge and split operations.
- This strategy takes a partition that possibly satisfies neither condition (4) or (5)
with the goal of producing a segmentation that satisfies both conditions.
(1) Split into four disjointed quadrants any region R i where P(R i )=False
(2) Merge any adjacent regions R j and R k for which P(R j ∪ R k )=True;
(3) Stop when no further merging or splitting is possible
-8-
split and merge thresholding
P(Ri ) = True if
|z i − m i | ≤ 2 i for 80% of the pixels in R i
(mi , i are the mean and standard deviation of pixels in R i )