Image segmentation

Digital image segmentation, Digital image processing

1. DIGITAL IMAGE PROCESSING
IMAGE SEGMENTATION

2. Introduction
•Imagesegmentationdividesanimageintoregionsthatare
connectedandhavesomesimilaritywithintheregionand
somedifferencebetweenadjacentregions.
•Thegoalisusuallytofindindividualobjectsinanimage.
•Forthemostparttherearefundamentallytwokindsof
approachestosegmentation:discontinuityandsimilarity.
–Similaritymaybeduetopixelintensity,colorortexture.
–Differencesaresuddenchanges(discontinuities)inanyofthese,but
especiallysuddenchangesinintensityalongaboundaryline,whichis
calledanedge.

3. Detection of Discontinuities
•Therearethreekindsofdiscontinuitiesofintensity:points,
linesandedges.
•Themostcommonwaytolookfordiscontinuitiesistoscana
smallmaskovertheimage.Themaskdetermineswhichkind
ofdiscontinuitytolookfor.


9
1
992211
...
i
ii
zwzwzwzwR

4. Detection of Discontinuities
Point Detection thresholdenonnegativ a: whereT
TR

5. Detection of Discontinuities
Line Detection
•Onlyslightlymorecommonthanpointdetectionistofinda
onepixelwidelineinanimage.
•Fordigitalimagestheonlythreepointstraightlinesareonly
horizontal,vertical,ordiagonal(+or–45).

6. Detection of Discontinuities
Line Detection

7. Detection of Discontinuities
Edge Detection

8. Detection of Discontinuities
Edge Detection

9. Detection of Discontinuities
Edge Detection

10. Detection of Discontinuities
Edge Detection

11. Detection of Discontinuities
Gradient Operators
•First-order derivatives:
–The gradient of an image f(x,y) at location (x,y) is defined
as the vector:
–The magnitudeof this vector:
–The directionof this vector:


















y
f
x
f
y
x
G
G
f  
2
1
22
)(mag
yx
GGf  f 









x
y
G
G
yx
1
tan),(

12. Detection of Discontinuities
Gradient Operators
Roberts cross-gradient operators
Prewitt operators
Sobel operators

13. Detection of Discontinuities
Gradient Operators
Prewitt masks for
detecting diagonal edges
Sobel masks for
detecting diagonal edges

14. yxGGf  Detection of Discontinuities
Gradient Operators: Example

15. Detection of Discontinuities
Gradient Operators: Example

16. Detection of Discontinuities
Gradient Operators: Example

17. Detection of Discontinuities
Gradient Operators
•Second-order derivatives: (The Laplacian)
–The Laplacian of an 2D function f(x,y) is defined as
–Two forms in practice:2
2
2
2
2
y
f
x
f
f







18. Detection of Discontinuities
Gradient Operators
•Consider the function:
•The Laplacian of his
•The Laplacian of a Gaussian sometimes is called the Mexican
hat function. It also can be computed bysmoothing the image
with the Gaussian smoothing mask, followed by application of
the Laplacian mask.deviation standard the: and
where)(
2222
2
2


yxrerh
r

 2
2
2
4
22
2
)(



r
e
r
rh








The Laplacian of a
Gaussian (LoG)
A Gaussian function

19. Detection of Discontinuities
Gradient Operators

20. Detection of Discontinuities
Gradient Operators: Example
Sobel gradient
Laplacian maskGaussian smooth function

21. Detection of Discontinuities
Gradient Operators: Example

22. Edge Linking and Boundary Detection
Local Processing
•Twopropertiesofedgepointsareusefulforedgelinking:
–thestrength(ormagnitude)ofthedetectededgepoints
–theirdirections(determinedfromgradientdirections)
•Thisisusuallydoneinlocalneighborhoods.
•Adjacentedgepointswithsimilarmagnitudeanddirectionare
linked.
•Forexample,anedgepixelwithcoordinates(x
0,y
0)ina
predefinedneighborhoodof(x,y)issimilartothepixelat(x,y)
if thresholdenonnegativ a: ,),(),(
00 EEyxyxf  thresholdangle nonegative a: ,),(),(
00 AAyxyx 

23. Edge Linking and Boundary Detection
Local Processing: Algorithm
1.Computethegradientmagnitudeandanglearrays,M(x,y)andα(x,
y),oftheinputimage,f(x,y).
2.Formabinaryimage,g(x,y),whosevalueatanypairof
coordinates(x,y)isgivenby:
whereT
Misathreshold,Aisaspecificangledirection,and±T
A
definesa“band”ofacceptabledirectionaboutA.
3.Scantherowsofgandfillallgapsineachrowthatdonotexceed
aspecifiedlength,K.
4.Todetectgapsinotherdirection,θ,rotategbythisangleand
applythehorizontalscanningprocedureinstep3.Rotatethe
resultbackby–θ.1, ( , ) AND ( , )
( , )
0, Otherwise
MA
M x y T x y A T
g x y
  



24. Edge Linking and Boundary Detection
Local Processing: Example
In this example,
we can find the
license plate
candidate after
edge linking
process.

25. Edge Linking and Boundary Detection
Global Processing via the Hough Transform

26. Edge Linking and Boundary Detection
Global Processing via the Hough Transform
•Houghtransform:awayoffindingedgepointsinanimage
thatliealongastraightline.
•Example:xy-planev.s.ab-plane(parameterspace)baxy
ii 

27. Edge Linking and Boundary Detection
Global Processing via the Hough Transform
•TheHoughtransformconsistsof
findingallpairsofvaluesof
andwhichsatisfytheequations
thatpassthrough(x,y).
•Theseareaccumulatedinwhatis
basicallya2-dimensional
histogram.
•Whenplottedthesepairsofand
willlooklikeasinewave.The
processisrepeatedforall
appropriate(x,y)locations. sincosyx

28. Edge Linking and Boundary Detection
Hough Transform Example
The intersection of the
curves corresponding
to points 1,3,5
2,3,4
1,4

29. Edge Linking and Boundary Detection
Hough Transform Example

30. Thresholding
•Assumption: the range of intensity levels covered by objects of
interest is different from the background.
Single thresholdMultiple threshold





Tyxf
Tyxf
yxg
),( if 0
),( if 1
),(

31. Thresholding
The Role of Illumination

32. Thresholding
The Role of Illumination
(a)(c)
(e)(d)),(),(),( yxryxiyxf  ),(yxi ),(yxr

33. Thresholding
Basic Global Thresholding

34. Thresholding
Basic Global Thresholding

35. Thresholding
Basic Adaptive Thresholding

36. Thresholding
Basic Adaptive Thresholding
How to solve this problem?

37. Thresholding
Basic Adaptive Thresholding
Answer: subdivision

38. Thresholding
Optimal Global and Adaptive Thresholding
•This method treats pixel values as probability density functions.
•The goal of this method is to minimize the probability of
misclassifying pixelsas either object or background.
•There are two kinds of error:
–mislabeling an object pixel as background, and
–mislabeling a background pixel as object.

39. Thresholding
Use of Boundary Characteristics

40. Thresholding
Thresholds Based on Several Variables
Color image

41. Region-Based Segmentation
•Edgesandthresholdssometimesdonotgivegood
resultsforsegmentation.
•Region-basedsegmentationisbasedonthe
connectivityofsimilarpixelsinaregion.
–Eachregionmustbeuniform.
–Connectivityofthepixelswithintheregionisvery
important.
•Therearetwomainapproachestoregion-based
segmentation:regiongrowingandregionsplitting.

42. Region-Based Segmentation
Basic Formulation
•Let Rrepresent the entire image region.
•Segmentation is a process that partitions Rinto subregions,
R
1,R
2,…,R
n, such that
where P(R
k): a logical predicate defined over the points in set R
k
For example: P(R
k)=TRUE if all pixels in R
k have the same gray
level.RR
i
n
i

1
(a) jijiRR
ji  , and allfor (c)  niR
i ,...,2,1 region, connected a is (b)  niRP
i ,...,2,1for TRUE)( (d)  jiji RRRRP and regionsadjacent any for FALSE)( (e) 

43. Region-Based Segmentation
Region Growing

44. Region-Based Segmentation
Region Growing
•Fig. 10.41 shows the histogram of Fig. 10.40 (a). It is difficult to
segment the defects by thresholding methods. (Applying region
growing methods are better in this case.)
Figure 10.41
Figure 10.40(a)

45. Region-Based Segmentation
Region Splitting and Merging
•Regionsplittingistheoppositeofregiongrowing.
–Firstthereisalargeregion(possibletheentireimage).
–Thenapredicate(measurement)isusedtodetermineifthe
regionisuniform.
–Ifnot,thenthemethodrequiresthattheregionbesplitinto
tworegions.
–Theneachofthesetworegionsisindependentlytestedby
thepredicate(measurement).
–Thisprocedurecontinuesuntilallresultingregionsare
uniform.

46. Region-Based Segmentation
Region Splitting
•Themainproblemwithregionsplittingisdeterminingwhereto
splitaregion.
•Onemethodtodividearegionistouseaquadtreestructure.
•Quadtree:atreeinwhichnodeshaveexactlyfourdescendants.

47. Region-Based Segmentation
Region Splitting and Merging
•Thesplitandmergeprocedure:
–SplitintofourdisjointquadrantsanyregionR
iforwhich
P(R
i)=FALSE.
–MergeanyadjacentregionsR
jandR
kforwhichP(R
jUR
k)=
TRUE.(thequadtreestructuremaynotbepreserved)
–Stopwhennofurthermergingorsplittingispossible.

48. Segmentation by Morphological Watersheds
•Theconceptofwatershedsisbasedonvisualizinganimagein
threedimensions:twospatialcoordinatesversusgraylevels.
•Insuchatopographicinterpretation,weconsiderthreetypesof
points:
–(a)pointsbelongingtoaregionalminimum
–(b)pointsatwhichadropofwaterwouldfallwithcertainty
toasingleminimum
–(c)pointsatwhichwaterwouldbeequallylikelytofallto
morethanonesuchminimum
•Theprincipalobjectiveofsegmentationalgorithmsbasedon
theseconceptsistofindthewatershedlines.

49. Segmentation by Morphological Watersheds
Example

50. Segmentation by Morphological Watersheds
Example

51. Segmentation by Morphological Watersheds
Example

52. The Use of Motion in Segmentation
•ADI: accumulative difference image

53. The Use of Motion in Segmentation