DIP_14_54_boundary extraction in dip .ppt

Boundary extraction in dip

1. Some practical uses
of morphology

2. It is possible to segment an image into regions
of common attribute by detecting the boundary
of each region for which there is a significant
change in attribute across the boundary
2

3. 3
Boundary of an
object
Consists of pixels that
belong to the object(s) itself
Consists of pixels that
belong to the background
Relation??
They are same

4. 4
Boundary of set A
β(A)
1.Erode A by B
2.Perform set difference between A & its
erosion

5. Example
Input image
Output Image
Structure element used is a 3X3 all 1s matrix
5

6. 6

7. 7

8. 8
Let A be a set. It contains a subset whose
elements are 8-connected boundary
points of a region.
All non-boundary points are labelled 0.
Set A

9. 9
Beginning with a point pinside the
boundary, the objective is to fill the
entire region with 1s.
A value 1 is assigned to the point p(p is an
arbitrarily selected point inside the boundary)
p

10. 10
Set A
c
The region is filled with 1s by the
following procedure.
X
k= (X
k-1
B) ∩ A
c
for k = 1, 2, …
where X
0= p
Structuring element
B
origin

11. 11
Structuring element
B
origin
X
0

12. 12
∩
Set A
c
X
1

13. 13
The algorithm terminates at iteration
step k if X
k= X
k-1.
The set union of X
kand A contains the
filled set & its boundary.
Thedilationprocesswouldfilltheentireareaifleft
unchecked.
TheintersectionwithA
c
ateachsteplimitstheresultto
insidetheregionofinterest.

14. 14

15. 15

16. 16
Extraction of connected components
in a binary image is central to many
automated image analysis
applications

17. 17
Let A be a set and Y be a connected component in it.
Point pof Y is known.
The following iterative expression yields all the elements
of Y.
Set A
p
Y
X
0= p
X
Structuring
element B

18. 18

19. 19
Set A is said to be convex, if
the straight line segment
joining any two points in A lies
entirely within A

20. 20
The convex hull Hof an arbitrary set
S is the smallest convex set
containing S
The set difference H –S is called the
convex deficiencyof S
Convex hull & Convex
deficiency
useful for object description

21. 21
Algorithm for obtaining Convex
Hull, C(A), of a set A
Therearefourconvexhullmasks,where1
representsblack,0representswhiteandX
representsapixelthatdoesn’tmatter,either
0or1.
1xx
10x
1xx
111
x0x
xxx
xx1
x01
xx1
xxx
x0x
111
B
1
B
2
B
3 B
4

22. 22
Theprocedureconsistsofimplementingthe
followingequation
Note: converged means when
•Where A represents iteratively applying the hit-or-miss
transform with the 4 masks.
•When the masks produce no more changes, the union is
performed between all 4 masks and the result becomes D
i
+1
+1

23. 23
Convex Hull Masks
Convex hull uses the hit or miss
function
If any of these masks are found in the
image, then that middle pixel on the
image is replaced with a 1 or black
respectively.
 To achieve the complete convex hull
image, these masks must be applied
repeatedly until no further changes
occur.

24. 24

25. 25
1 x x
1 0 x
1 x x
B
1

26. 26
1 1 1
x 0 x
x x x
B
2

27. 27
x x 1
x 0 1
x x 1
B
3

28. 28
x x x
x 0 x
1 1 1
B
4

29. 29

30. 30
Toreducethiseffectlimitgrowthsothatit
doesnotextendpastthevertical&
horizontaldimensionsoftheoriginalset
ofpoints

31. 31

32. 32
Boundaries of greater complexity can be
used to limit growth even further in
images with more detail.
e.g. the maximum dimensions of the original
set of points along vertical, horizontal &
diagonal directions can be used.
Price paid for such refinements ??
Additional complexity

33. 33

34. 34
Thinning: from many pixels width to
just one
•Much work has been done on the thinning
of ``thick''binary images,
•where attempts are made to reduce shape
outlineswhich are many pixels thick to
outlines which are only one pixel thick.
Thinning of thick binary images

35. 35
Erase black pixels such that
Anobjectwithoutholeserodestoa
minimally connected strokelocated
equidistantfromitsnearestouter
boundaries
Anobjectwithholeserodestoa
minimallyconnectedringmidwaybetween
eachhole&itsnearestouterboundary.
Thinning is used to remove selected
foreground pixels from binary images

36. 36
Thinning
Original
image
Thinned
image

37. 37
Applying thinning to
fault detection in PCB
All lines are thinned to one pixel width
Now you can check connectivity

38. 38
Thinning is basically a search & delete process.
It removes only those boundary pixels from the
image whose deletion
Doesnotchangeconnectivityoftheir
neighbourslocallyand
Doesnotreducethelengthofanalready
thinnedcurve
Critical pixel
Its deletion changes the
connectivity of its
neighbourhoodlocally
End pixel
Its deletion reduces the length
of an already thinned curve.
The no. of neighbouringpixels
of an end pixel are ??

39. 39
Some boundary pixels
011
011
010
011
011
100
010
010
010
010
010
001
010
011
000
000
011
000
000
010
001
(a) (b) (c) (d)
(e) (f) (g)
The image A is
8-connected
The centre pixel of which windows is a
critical pixel ?
(b), (c), (d)

40. 40
011
011
010
011
011
100
010
010
010
010
010
001
010
011
000
000
011
000
000
010
001
(a) (b) (c) (d)
(e) (f) (g)
The centre pixel of which windows is a
end pixel ?
(f), (g)

41. 41
011
011
010
011
011
100
010
010
010
010
010
001
010
011
000
000
011
000
000
010
001
(a) (b) (c) (d)
(e) (f) (g)
The centre pixel of which windows can be
deleted without affecting local connectivity
of the neighbourhood or reducing the length
of the arc?
(a), (e)

42. 42
011
011
010
011
011
100
(a) (b)
What happens to the centre pixels when we
consider the image A to be 4-connected?
In (a) the centre pixel becomes critical,
while in (b) it is not

43. 43

44. 44

45. 45

46. 46

47. 47
Thinning removes only those boundary pixels from the image
whose deletion
Doesnotchangeconnectivityoftheirneighbourslocallyand
Doesnotreducethelengthofanalreadythinnedcurve
Thedeletionofallboundarypixelsthatsatisfythe
abovecriteriashouldbedonesimultaneouslyto
ensuresymmetryintheresultantskeleton.
However,suchstrategymaydeletecompletelya
curvesegmentsuchastheonegivenbelowsinceall
thepixelssatisfytheabovecriteria.
111111
111111

48. 48
Solutio
n to the
proble
m
Applythedeletionprocess
simultaneouslytoallboundary
pixelsofaparticularside(N,S,
EorW)
How to find out the pixels
of the north boundary?
Pixel (x,y) is in the north boundary
if pixel (x, y+1) is in A
c
When is pixel (x, y) in the S, E or W boundary?
111
11
11
111
X

49. 49

50. 50
The thinning of a set A by a
structuring element B can be defined
in terms of the
hit-or-miss transform

51. 51
A more useful expression for
thinning A symmetrically
Use a sequence of structuring elements
{B} = {B
1
, B
2
, ..., B
n
}
where B
i
is the rotated version of B
i-1

52. 52
Thinning
Thinning is often accomplished
using a sequence of rotated
structuring elements (a). Given
a set A (b), results of thinning
with first element is shown in
(c), and the next 7 elements (d)
–(i). There is no change
between 7
th
and 8
th
elements,
and no change after first 3
elements. Then it converges to
a m-connectivity. 
 
    
n
n
BBBABA
BBBB
BAhitnmissABA





21
21
,,
,

53. 53
Thickening is the morphological dual of thinning
Thickening can also be defined as
a sequential operation

54. 54
A separate algorithm is rarely
used for thickening
The usual procedure??
Thin the background of the set in
question & then take the complement
of the result
To thicken A
Let C = A
c
Thin C
Take C
c