IP Digital Geometry L2

Digital Image:
Geometry in a
discrete grid
Jayanta Mukhopadhyay
Dept. of CSE,
IIT Kharagpur
Discrete Space and Tiling
l Discrete Space
l Integral coordinate space: Zn
l Digital grid
l A finite subset of integral coordinate space: Gn ⊂ Zn
l represented by a n-D rectangular array
l Tessellation or Tiling
l 2D: A bounded region of a specific shape that fills the
plane with no overlaps and no gaps
l Center of the region lies at a grid point
l Regular tiling: All the space filling units are similar and
of the shape of a regular polygon
2
l Generalization to n-D regular hyper-polyhedron
J. Mukhopadhyay, et al (2013), "Digital Geometry
in Image Processing", CRC Press, April.
Regular Archimedean Tiling

l In 2-D: 3
Triangular Hexagonal Rectangular
l In 3-D: 1 (Rectangular)
l In 4-D: 3
l In n-D, n>4: 1 (Rectangular)
Our focus: Digital geometry in rectangular grid ! 3
2-D or 3-D
Why digital geometry?
l Digital Distance Function ( different domain and range)

d: Zn x Zn P (or R)
l Finite neighbourhood.
l Things are different (due to digitization.)
Motivation
l Exact analysis: As they are in the digital space.

l Analysis of approximation: Error bounds from Euclidean
measures, better understanding in correlating corresponding
objects and shapes.
l Efficient computation: Finite neighbourhood and integer
arithmetic.
l Empirical Techniques: Finite enumeration.
Distance Function
l Distance Function:
d: Rn x Rn R
l Digital Distance Function:

d: Zn x Zn P (or R)
l A function of two points in a space measuring their

separation or dissimilarity.
Examples:
u º (u(1), u(2),........, u(n))

v º (v(1), v(2),........, v(n)) 1
æ n p ö
p
L p (u, v) = ç å | u (i ) - v(i ) | ÷
èn i =1 ø
L1 (u , v ) = å | u (i ) - v (i ) |
i =1
n
L2 (u, v) = En (u, v) = å |
i =1
u (i ) - v (i ) | 2
L¥ (u, v) = max{| u(i) - v(i) |}

1£i £ n
Neighbourhood
ε ε-Neighbour:
p a point q is in N(p),
iff d(p,q) ≤ ε.
Desirable: Compact and bounded.

Path
p
q
2 3
1 n
Length of the path ≈n. ε

Desirable feature:
Distance = Length of the shortest Path.
Metric & Conditions:
i. d (u , v) = 0 iff u = v d is defined for

every pair of points
ii. d (u , v) = d (v , u) in the space.
iii. d (u , v) + d (u , w) > d (u , w) ,
" u , v , w Î Rn (Zn)
N(x;d) is a Norm of d if
N(x;d) = d(x, 0) where x = u – v
Why a metric?
l A bounded and compact neighbourhood around a
point in the space.
l There exists an optimal path between two points,
such that the length of this path is given by the
distance function.
Neighbourhood structure:
Examples
L1 norm
Desirable features:
Isotropy and symmetry:
Isotropic in all directions.
Uniformity:
Identical at all points of the
space. L2 norm
Convexity:
In the sense of Euclidean
geometry.
Self-similar:
Similar structure at varying
resolution. L∞ norm
Acknowledgement: Figure taken from http://en.wikipedia.org/wiki/File:Vector_norms.svg
Geometry built on distances
l Shortest Paths in Euclidean Space
l Straight Lines
l Geodesics on Earth
l Parallel Lines
l Equidistant Ever
l Circle
l Trajectory of a point equidistant from Center
l Least Perimeter with Largest Area
l Conics are distance defined.
Neighbors of Pixels in 2-D
l P = (x,y)
l 4–Neighbours
l N4(P) = {(x–1,y), (x+1,y) , (x,y–1), (x,y+1)}
l Diagonal–Neighbours
l ND(P) = {(x–1,y–1), (x–1,y+1) , (x+1,y–1), (x+1,y+1)}
l 8–Neighbours
l N8(P) = N4(P) U ND(P)
o o o o
For a digital
distance:
o o o o o o
A neighbor is at
o o o o distance 1.
14
4-neighbors 8-neighbors
Digital Distances in 2D
For u, vÎZ2 and x = |u – v|=(x1, x2),
Cityblock:
d4(u, v) = x1+x2 ,
Chessboard:
d8(u, v) = max(x1, x2),
Octagonal (uses non-uniform alternating neighborhoods):
doct(u, v) = max(x1, x2, é2(x1 + x2)/3ù) .
Rosenfeld and Pfaltz ’68
Octagonal Distance
b
d(a,b) = 10
Neighborhood sequence {1,2}
doct(u, v) = max(x1, x2, é2(x1 + x2)/3ù)
2 2 2
2 2 1 2 2
2 1 * 1 2
2 2 1 2 2
2 2 2
Weighted Distance
For u, vÎZ2 and x = |u – v|=(x1, x2),
b a b
a p a Metric Conditions:
a ≤ b, and b ≤ 2a
b a b
d<a,b>(u, v) = a.max(x1 , x2 )+ (b-a). min(x1 , x2 )

Weighted Distance: An example
of a path
d<a,b>(p,q)=5b+2a
e.g.,
q(7,5)
For a=1 and b=1.4,
d<1,2>(p,q)=9.
Euclidean distance:
de(p,q)= 8.6
p(0,0)
Circle of a weighted distance
<1, √2>
Neighbors of Voxels in 3-D
l P = (x,y,z)
l 6–Neighbors (Face),
l 18–Neighbors (Edge) &
l 26–Neighbors (Corner)
6–Neighbors 18–Neighbors 26–Neighbors

20
J. Mukhopadhyay, et al (2013), "Digital Geometry in
Image Processing", CRC Press, April.
Digital Distances in 3D
For u, v Î Z3 and x = |u – v|,
d6(u, v) = x1 + x2 + x3, (grid distance)

d18(u, v) = max(x1, x2, x3, é(x1 + x2 + x3)/2ù)
d26(u, v) = max(x1, x2, x3) (lattice distance).
Like 2D, in 3D also Octagonal and

Weighted distances are defined.
Yamashita and Ibaraki ‘86
Digital discs
B(O; R ) = {x d (O, x ) £ R}
R R
2D
d4 d8
3D
d6 d18 d26
Vertices of octagonal discs:
{ }
a b
2D : 1 2 : permutation of(± R,±
ab
a+b
R)
{ }
a b c
3D : 1 2 3 : permutation of(± R, ±
b+c
a+b+c
R, ±
c
a+b+c
R)
Octagonal Digital Circles
{1,2} {1,1,2} {1,1,1,2}

Octagonal Digital Spheres
{1,1,2} {1,1,3} {1,2,3}

Binary Image
l f : Gn à {0,1}
l Foreground and background
l p ∈Gn is in foreground, iff f(p)=1, otherwise it is in
background.
l Foreground consists of object points.
§ S : foreground
§ Sc = Gn –S : background
l Adjacent neighbor
l A neighboring foreground pixel
l 2D: 4 / 8 - adjacency
l 3D: 6 /18 / 26 - adjacency
26
Path
l A Sequence of distinct pixels satisfying pair-wise adjacency
l Length of the path
l Number of adjacencies
l One less than the number of points
l Shortest Path between two pixels can be non-unique
l Closed Path: Same Start and End Points
2-D 3-D
27
Connectivity
l Two pixels are Connected if there exists a path
between them.
l Pixels connected to a given pixel form a
Connected Component.
l A Region is a Connected Set of foreground points.
l Foreground & Background
l Foreground: Union of all disjoint Regions in an Image
l Background: Complement of Foreground
l Boundary or Border
l Inner Border: Set of points in R adjacent to complement of R
l Outer Border: Set of points in complement of R adjacent to R 28
4– and 8–Neighbors Dichotomy
l Jordan’s Curve Theorem
l Every simple closed curve divides the
plane into an "interior" region bounded by
the curve and an "exterior" region
containing all far away points
§ Any continuous path connecting a point of one
region to a point of the other intersects that loop
somewhere.
l Digital Jordan’s Curve Theorem
l Deviates from the theorem.
l Use alternate adjacency for interior / exterior
29
J. Mukhopadhyay, et al (2013), "Digital
Geometry in Image Processing", CRC Press,
Limitation of Jordan’s curve
April.
theorem in digital space
(8,4) (4,8)
A single component Three components 30
Foreground points with similar configuration!

Component labeling
l Form a graph with edges between neighboring
foreground pixels.
l Compute connected components.
l Graph traversal algorithms
l Storage inefficient for large components
0 0 1 0
0 0 1 0
1 1 1 0
0 0 0 0
31
Two Scan Labeling

l Use of two masks for
l Forward scanning: Top to bottom and left to right
l Backward Scanning: Bottom to top and right to left
Chamfering!
p p
For 8-adjacent
(a)
connected
component
(b)
l Check the labels (a number) of neighbors at a foreground point p

l If <no label> found, create new unique label
l Else assign the label of a neighbor.
l For multiple labels declare them equivalent and assign the 32
lower numeral id.
Distance Transforms (DT)
l Distance Transform: At every foreground pixel p
(i.e. f(p)=1), it stores the distance of the pixel from
the nearest background (f(.)=0) pixel.
l For all pixels p of an image S, the DT algorithm

computes:
t(p) = mink{d(p, qk): S(qk) = 0, 1 ≤ k ≤ |S|}
l DT(S): Image of t(p)’s, called the DT image.
33
Distance Transforms for
Binary Images (d4)
34
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Distance Transforms for
Binary Images (d8)
35

Distance Transforms Algorithms
l Brute Force Algorithm
For every pixel in foreground F compute the distance to
l
every pixel in background B and find the minima
l Let the image be of size n
l Let f = |F|, b = |B|, f + b = n
l Often f = O(n) and b = O(n)
l Number of distance computations = f.b = O(n2)
We need a better algorithm
36

Chamfering Algorithm for
Distance Transform
l Initialize all DT values to infinity.
l Perform two scans: Raster & Reverse Raster
l In every scan Chamfer with a mask
l At every pixel position, add the mask weight with the pixel
covered and take the minimum
DT(o) = min (DT(Neighboring pixel) + local distance between them)
Computes DT for ‘additive’
a b a
o
b distances
b a b a
b = 1, a = 2: City Block
o
b = 1, a = 1: Chess Board
Forward Scanning Backward Scanning b = 1, a = √2: Weighted
From Left to Right From Right to Left Complexity = O(n) 37
and Top to Bottom and Bottom to Top
Two pass chamfering algorithm
to compute DT with d4
38

Two pass chamfering algorithm
to compute DT with d8
39

Distance Transform: An
example
Input image Output

DT: Properties -1
l [1] t(p) represents the radius of the largest disk
centered at p and totally contained in F
41
DT: Properties -2
l If there is only one q ε B with t(p) = d(p, q):
l (a) an element p’ ε F exists such that the disk centered
at p’ totally contains the disk centered at p (disk B is
totally included in disk A)
l (b) elements p’ ε F and q’ ε B exist such that d(p, q) =
d(p’, q’) and p is adjacent to p’
(a) (b) 42

DT: Properties -3
l If there are two (or more) q, q’ ε B such that
t(p) = d(p, q) = d(p, q’), then the disk centered
at p is a maximal disk in F and p is symmetric
43

Medial Axis Transform
A set of maximal blocks contained in the pattern.

Computation of Medial Axis
Transform
• Compute the distance transform.

• Compute local maxima in the
distance transformed image.
Application of MAT in Image
Analysis
• Geometric Transformation (Kumar et al ’96)

• Computation of Normals (Mukherjee et al ’02)
• Thinning of binary pattern (Costa ’00, Pudney ’98)
• Computation of cross-sections of 3D objects
(Mukherjee et al ’00)
• Visualization of 3D objects (Mukherjee et al ’99,
Prevost and Lucas ‘00)
• Image compression (Kumar et al ’95).
• Shape Description (Baja and Svensson ’02)
Thinning from Distance
Transform
Compute the set of Maximal Blocks.

Use them as anchor points while
iteratively deleting boundary points
preserving the topology.
Vincent ’91, Ragnemalm ’93, Svensson-Borgefors-Nystrom ’99

Normal Computation
l Normal at a point p computed by computing

the resultant vector from that point to the
neighboring medial circles.
J. Mukhopadhyay, et al (2013), "Digital Geometry in

Image Processing", CRC Press, April.
Normal Computations:
Examples

Cross-sectioning

Cross-sectioning with different
distance functions.

A set of objects for
experimentation

Cross-sectioning: Voxel data,
MAT & Sphere Approx.
Euclidean Sphere
Voxel Data MAT
Approximation
Shape representation in 2D
l Boundary (Border) Following
l Chain Codes
l Polygonal Approximation using Minimum-
Perimeter Polygons (MPP)
l Polygonal Approximation by Merge/Split
l Signatures
l Boundary Segments
l Skeletons
54
Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Boundary (Contour) Following

l Boundary
l Good representation of an
object shape
l Requires less memory.
l Input:
l Border points
l A foreground (object) point
which is m-adjacent to a
background point in (m, n)
grid.
l Output: A border point An interior
l Ordered sequence of point 55
these points (8,4) Grid
T. Pavlidis. Algorithms for graphics and image processing. Computer
Science Press, Rockville, MD, 1982.
Contour following algorithm

l Start from the leftmost and topmost border point p
with its left neighboring background point q. Mark
p visited.
l Perform clockwise search among 8-neighbors of q
to get the first foreground point except the
preceding border point . For anti-
Assumption:
l If it is already visited Simple clockwise
l stop and output the sequence. contour (non contour,
intersecting)
l Else search in the
l include it in the sequence, anti-clockwise
l mark it visited and
order.
l continue from the recently visited point in the same
manner starting from the previous border point but 56
excluding it from consideration .

Search order and sequence:
An example
The order of
r1 2 r 3 r searching a q 2
p
foreground pixel in q 1 p 1
2
p q ,q q 5
q=r 0 p 4 r the neighborhood of q
0 p 0 p
3 3 4
4
p
a border pixel p with 9, p 5
r7 6 r 5 r
a background q9 p 8 p q 6 6
neighbor at q in an q p8 q 7 7
(a) (8 , 4) digital grid.

(b)
The order follows The sequence of pairs of
clockwise movement border pixels (pi ; qi), where
starting from q pi belongs to foreground, and
qi belongs to background,
in Image Processing", CRC Press, April. respectively, for the point set
Chain Codes
l Representing a boundary of a connected region
l Based on 4 or 8 connectivity of the segments
l For every point code the direction of the next point
1 2
3 1
2 0 4 0
5 7
3 6
4-Directional Code 8-Directional Code 58
Need for resampling
l The chain code of the same length as the
perimeter of the object, in many cases too long
l Hence, re-sample the image to a lower resolution
before calculating the code
l The re-sampling also reduces noise sensitivity
59

Chain codes: Examples
4-connected or
8-connected.
60

Chain codes: various issues
l Starting Point (various options)
l Topmost, Leftmost point
l Context dependent choice
l Normalize by
l Assuming the code to be circular (closed curve) and
l Choose the integer of minimum magnitude
l Rotation Invariance
l Use first difference of the chain code
l Obtained by counting the number of direction changes (in a
counterclockwise direction)
l For example, the first difference of the 4-direction chain code
10103322 is 3133030.
l Use circular shifting for minimal representation
l Size Normalization
l Achieved by adjusting the size of the re-sampling grid. 61
Polygonal approximation
l Polygonal approximations
l Represent a boundary by straight line segments, and
l A closed path becomes a polygon
l Number of straight line segments?
l Accuracy of the approximation
l Larger number of sides add noise
l Small number of side result in coarse shapes
l Optimize for minimum number of sides
l Constraint: Preserve the shape information
62

Polygonal Approximation using
Minimum-Perimeter Polygons
l Optimization involves Iterative Search
l Computationally Expensive
l Use: Approximate Optimization
l MPP: Minimum Perimeter Polygons
63

MPP Algorithm: intuition
Boundary of an object In the discrete grid MPP: Vertices from

inner and outer walls
64

Properties of MPP
l Size of the Cell è
l Accuracy of Polygonal Approximation
l If size of a cell (dXd)= size of a pixel in the
boundary è
l Max error = √2d
l Use largest possible cells è
l Fewest number of vertices in MPP
65

Properties of MPP
l Boundary:
l 4-connected
l straight-line segments
l Mark counterclockwise
l Convex (90 deg turn) Vertices: White
l Concave (270 deg turn) Vertices: Black
l Mirror Vertex for every Concave Vertex
l An MPP vertex is
l Convex Vertex on Inner Wall or
l Mirror of Concave Vertex on Outer Wall
66

MPP Algorithm: Intuition
Concave Convex
Images taken from Gonzalez & Woods, Digital Image Processing (2002)
67

Not a vertex
of MPP
Properties of MPP
l MPP bounded by a simply
connected cellular complex is not
self-intersecting
l Every Convex vertex of MPP is a
W vertex; but not every W vertex
of a boundary is a vertex of MPP
l Every Mirrored Concave vertex of
MPP is a B vertex; but not every B
vertex of a boundary is a vertex of
MPP
68

Properties of MPP
l All B vertices are on or outside
MPP and all W vertices are on or
inside MPP
l The uppermost, leftmost vertex in
a sequence of vertices contained
in a cellular complex is always a
W vertex of MPP
69

Orientation of 3 points
a = ( x1 , y1 ), b = ( x2 , y2 ), c = ( x3 , y3 )
2
é x1 y1 1ù 1
A = ê x2 y2 1ú
ê ú + 3
êë x3 y3 1úû
sgn(a, b, c ) = det( A) =
ì> 0, if (a, b, c ) is a counterclockwise sequence
ï
í = 0, if the points are collinear
ï < 0, if (a, b, c ) is a clockwise sequence
î
70

MPP Algorithm
l Input: Vertices (with W/B Markers)
l In a list in boundary order
l First vertex, V0:

l Uppermost, leftmost, a W vertex of MPP
l Crawler Vertices:
l White crawler: WC and Black crawler: BC
l VL: Last MPP vertex found

l Vk: Current vertex being examined
71

MPP Algorithm
l Let WC = BC = V0
l Repeat over the list
l [A] sgn(VL,WC,Vk)>0
l VL ßWC and WC = BC = VL
l Continue with the next vertex after VL.
l [B] sgn(VL,WC,Vk)≤0 & sgn(VL,BC,Vk)≥0
l WC = Vk, if Vk is convex (W) Move either along W
l BC = Vk , otherwise or B as it appears and
record a MPP vertex if
l Continue with the next vertex after VK. conditions met. Start
again from the new
l [C] sgn(VL,BC,Vk)<0 MPP vertex.
l VL ßBC and WC = BC = VL
l Continue with the next vertex after VL. 72

MPP Algorithm
l Vertices:
l V0 (1,4) W
l V1 (2,3) B
l V2 (3,3) W
l V3 (3,2) B
l V4 (4,1) W
l V5 (7,1) W
l V6 (8,2) B
l V7 (9,2) B
73

MPP Algorithm: Execution
l WC=BC=V0=VL=(1,4)
l V1=(2,4) W
l Condition [B]
l sgn(VL,Wc,V1)=0 &
l sgn(VL,Bc,V1)=0
l WC=V1=(2,4)
l Next vertex: V2= (3,4) B
74

l BC=(1,4), WC=(2,4)
l VL=(1,4)
l V2=(3,4) B
l Condition [B]
l sgn(VL,Wc,V2)=0 &
l sgn(VL,Bc,V2)=0
l BC=V2=(3,4)
l Next vertex V3= (3,3) W
75

l WC=(2,4), BC=(3,4)
l VL=(1,4)
l V3=(3,3) W
l Condition [C]
l sgn(VL,Bc,V3) < 0
l VL = (3,4) BC
l WC= BC =(3,4)
l Next vertex V4=(3,3)
76

l WC= BC =(3,4)
l VL=(3,4)
l V4=(3,3) W
l Condition [B]
l sgn(VL,Wc,V4)=0 &
l sgn(VL,Bc,V4)=0
l WC=V4=(3,3)
l Next vertex V5=(4,3) B
77

l VL=(3,4)
l WC=(3,3)
l BC=(3,4)
l V5=(4,3) B
l Condition [A]
l sgn(VL,Wc,V5) >0
l VL = WC = (3,3)
l WC = BC = VL
l Next vertex:
V6=(4,3) B 78

l WC = BC = VL=(3,3)
l V6=(4,3) B
l Condition [B]
l sgn(VL,Wc,V6)=0
l sgn(VL,Bc,V6)=0
l BC=(4,3)
l Next vertex V7=(4,2) W
79

l WC=(3,3), BC=(4,3)
l VL=(3,3)
l V7=(4,2) W
l Condition [C]
l sgn(VL,Bc,V7) < 0
l VL= BC=(4,3)
l WC = BC = VL
l Next vertex V8= (4,2)
80

l WC=(4,3), BC=(4,3)
l VL=(4,3)
l V8=(4,2) w
l Condition [B]
l sgn(VL,Wc,V8)=0
l sgn(VL,Bc,V8)=0
l WC=(4,2)
81

l WC=(4,2), BC=(4,3)
l VL=(4,3)
l V9=(4,1) W
l Condition [B]
l sgn(VL,Wc,V9)= 0
l sgn(VL,Bc,V9)= 0
l WC= (4,1)
82

l WC=(4,1), BC=(4,3)
l VL=(4,3)
l V9=(5,1) W
l Condition [A]
l sgn(VL,Wc,V10) > 0
l VL = WC= (4,1) W
l WC= BC= (4,1)
l And so on ..
83

MPP : Example
l Image of size
566x566 2
l 8-connected
boundary (1900
points)
3 4 6
l Of different cell size:
2, 3, 4, 6, 8, 16 & 32
l # of Vertices:
l 206, 160, 127,92, 8 16 32
66, 32 & 13.
84

MPP : Example
Input image Output

Fast polygonal approximation of digital curves using relaxed straightness properties
P Bhowmick, BB Bhattacharya - IEEE TPAMI, 2007
Digital curve and straight segments

l Digital Curve (DC): A DC C is an ordered sequence of grid
points (representable by chain codes) such that each point
(excepting the first one) in C is a neighbor of its predecessor
in the sequence.
l Irreducible Digital Curve: A DC C is said to be irreducible
if and only if the removal of any grid point in C makes C
disconnected.
86
An example of DC and irreducible DC.
Chain code representations:

Examples
Chain codes and their enumeration for defining DC. (a) Chain codes in 8-
neighborhood connectivity. (b) (1, 2)10756543.
87
(c) (1, 2)10756543(3, 4)76. (d) (2, 1)0756543121
Digital Straight Line Segments
(DSS)
l Let p, q be points of the digital picture subset S, and let pq
denote the (real) line segment between p and q.
l pq lies near S if, for any (real) point (x,y) of pq, there exists a
(lattice) point (i,j) of S such that max {|i - x |,|j - y|} < 1.
l S has the chord property if, for every p, q in S, the chord pq
lies near S..
q
u 𝚫x
𝚫y
v pq lies near S if for any v there exists u
S
and such that max(𝚫x,𝚫y)<1.
p
AZRIEL ROSENFELD, Digital Straight Line Segments. IEEE TRANSACTIONS 88
ON COMPUTERS, VOL. c-23, NO. 12, DECEMBER 1974, 1264-1268.

Digital Straight Line Segments
(DSS)
l A digital straight line segment (DSS) is the digitization of a
straight line segment.
l A DSS is an irreducible DC.
l A DC is the digitization of a straight line segment if and only
if it has the chord property .

DSS characterization
l R1: The runs have at most two directions, differing by 45 degrees,
and, for one of these directions, the run length must be 1.
l At most two types of elements and they differ only by unity, modulo eight.
l One of the two element values always occurs singly.
l R2: The runs can have only two lengths: consecutive integers.
l Successive occurrences of the element occurring singly are as uniformly
spaced as possible.
l R3: One of the run lengths can occur only once at a time.
l R4: For the run length that occurs in runs, these runs can
themselves have only two lengths p and p+1, which are consecutive
integers, and so on.
l Except run lengths at two extreme ends (l and r, l, r < (p+1) )

An example of a DSS
l Singular element (s) : 1
l Non singular element (n): 0
l Parameters: n, s, l, r, p.
04 1 05 1 04 1 05 1 04 1 05
l=4, r=5, p=4
91
P. Bhowmick and B. B. Bhattacharya, "Fast Polygonal Approximation of Digital Curves Using Relaxed Straightness
Properties," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 9, pp. 1590-1602, Sept. 2007
Digital curve segmented by
DSS’s
l Segments shown with alternate black and grey fragments.
l Of small lengths.
l Too many fragmentation.
92
Approximate DSS (ADSS)
l Used R1
l Modified R2
l Run lengths of non-singly occurred (n) element may vary more than
unity, depending on the minimum length (p).
l But dropped R3 and R4
l To allow longer fragments of DC approximating a straight line
segment.
l DSS is also accepted in the criteria of ADSS
l New Parameters: Run length interval parameters [p,q]
excepting l and r.
Integer computation
l Other hyperparameters: Tolerances
l q-p < d=L (p+1)/2 ⅃ , and l-p, r-p < 𝜖 =L (p+1)/2 ⅃
93
Not DSS but ADSS
l=4, r=5, p=4, q=5
04 1 05 1 05 1 04 1 04 1 05 Run length seq: 455445
Both having non-singular occurrences
l=4, r=4, p=4, q=5

Run length seq: 4545554
04 1 05 1 04 1 05 1 05 1 05 1 04
94
Run lengths of 5 nonconsecutive 1 & 3
Not ADSS
l=4, r=5, p=1, q=8
q-p > L (p+1)/2 ⅃ =1

l-p > L (p+1)/2 ⅃ =1
04 1 05 1 01 1 08 1 04 1 05
r-p > L (p+1)/2 ⅃ =1
l=11, r=1, p=1, q=2
l-p > L (p+1)/2 ⅃ =1

011 1 02 1 02 1 01 1 01 1 01 95
Extraction of a sequence of ADSS

from a DC
l Start from the first point by including it as a vertex of the
first ADSS.
l Extract parameters l, n, and s
l l: leftmost run length of non-singularly occurring element,
l n: non-singularly occurring element, and
l s: non-singularly occurring element.
l Compute runs of n till it breaks conditions of ADSS.
l Include the point before the breaking condition emerges in
the sequence of ADSS in the DC.
l Repeat above steps from the extraction of parameters and
continue till the end of DC.
A linear time algorithm
96
Example
DSS
ADSS
97
Polygonization / Polylineation
l Input: A sequence of ADSS.
l Output: Vertices of polygon.
l Algo:
l Merge consecutive sequences following an error criteria.
l Cumulative (Max) area of triangles formed by end points of the ADSS
and the line segment of the merged segment should remain within a
fraction of maximum iso-thetic distance of the merged line segment.
l Represent merged segments as a straight line segment with start
and end points of the start and end ADSS of the sequence.
l Continue till all the ADSS’s are covered.
p2(x2,y2)
p1(x1,y1) diso(p,q) =max{|xe-xs|,|ye-ys|}
q(xe,ye)
98
p(xs,ys) Cumulative area=∆pp1q+∆pp2q < 𝝉 diso(p,q)

A few results
99
Another example
(a) input set of DC. (b)

ADSS. (c) Ccum : 𝝉= 2.
(d) Cmax : 𝝉 =2. (e) Ccum:
𝝉 =8. (f) Cmax : 𝝉 =8.
100
Polygonal approximation by
merging
1. Merge points along boundary until LSE of line fit
exceeds a threshold. Output a line (side of
polygon) with parameters of LSE
2. Repeat Step 1 as long as there are points on the
boundary
3. Intersections of line segments give vertices
Disadvantage
May not produce vertices at inflection points as ‘long’
consume these ‘outlier’ points within the threshold.
101

splitting
l Boundary into two parts using extreme points.
l Diameter for closed contour providing two points.
l Most distant point from the straight line connecting two end
points of an open contour segment.
l Start with the closed contour and determine two
extreme points.
l Output two open segments in counter-clockwise order.
l Recursively process every open segment and form a
vertex at each stage connecting end points of open
contours
l till the max. dist. less than a threshold. 102
splitting
103

Skeletonization: Medial Axis
Transform (MAT)
l MAT of region R with border B
l For each point p in R, find its closest neighbor in B
l “Closest” use the concept of distance – often Euclidean
l If p has more than one such neighbor, it belongs to the
Medial Axis (Skeleton) of R
l Intuitively MAT is defined by Grassfire analogy
104

Skeletonization: Medial Axis
Transform (MAT)
l Intuitive approach is computationally expensive as
it needs the computation of the distance from
every interior point to every point on the boundary
of a region
l Alternate approach is to remove non-MAT points
l Typical fast (thinning) algorithms iteratively delete
boundary points of a region provided the deletion:
l Does not remove the end points
l Does not break connectivity
l Does not cause excessive erosion of the region
105

Skeletonization: Thinning
Algorithm
l Border / Contour Point: An object (region) point (1) with at
least one background (0) neighbor
l Step 1
l Repeat for all contour points
l Flag contour points for deletion by Condition 1
l Remove all flagged points (change 1 à 0)
l Step 2
l Repeat for all contour points
l Flag contour points for deletion by Condition 2
l Remove all flagged points (change 1 à 0)
l Repeat Steps 1 & 2 till no deletion is possible 106

Algorithm
l Condition 1
a) 2 ≤ N(p1) ≤ 6 N(p1) =Non-zero neighbors of
b) T(p1) = 1 p1= p2+p3+p4+p5+p6+p7+p8+p9
c) p2.p4.p6=0 T(p1) =Number of 0-1
d) p4.p6.p8=0 transitions in the sequence
l Condition 2 p2,p3,p4,p5,p6,p7,p8, p9,p2
A. 2 ≤ N(p1) ≤ 6
B. T(p1) = 1 N(p1)=4
C. p2.p4.p8=0
T(p1)=3
D. p2.p6.p8=0
107

Algorithm
l Condition 1
a) 2 ≤ N(p1) ≤ 6 N(p1) =Non-zero neighbors of
b) T(p1) = 1 p1= p2+p3+p4+p5+p6+p7+p8+p9
c) p2.p4.p6=0 T(p1) =Number of 0-1
d) p4.p6.p8=0 transitions in the sequence
l Condition 2 p2,p3,p4,p5,p6,p7,p8, p9,p2
A. 2 ≤ N(p1) ≤ 6
B. T(p1) = 1 N(p1)=4
C. p2.p4.p8=0
T(p1)=3
D. p2.p6.p8=0
108

Algorithm
o If p1 satisfies [a,b,c,d] (or [A,B,C,D]) it
should be safe to remove it (flag it for
removal) while preserving the structure of
the skeleton intact
n Note: The actual removal is lazy so that the
order of checking for these conditions does not
impact the actual application
109

Algorithm
o Interpretations of conditions
n [a, A]: Guard Condition for
o Protecting end point
o Limiting excessive erosion
n [b, B]: Guard Condition for
o Preserving connectivity
n [c, C] / [d, D]: Candidate Condition for
o Border points
o Corner points
110

Algorithm
o How do the conditions guarantee a
MAT?
n [a, A] 2 ≤ N(p1) ≤ 6 is violated if p1
has
o 1 neighbor à End point of a stroke
o 7 neighbors à Causes excessive
erosion
N(p1)=4
n [b, B] T(p1) = 1 is violated if p1 is
T(p1)=3
o On a 1-pixel thick stroke (bridge) à
Preserve connectivity
111

Algorithm
l [c,d] p2.p4.p6=0 and p4.p6.p8=0 are satisfied
simultaneously by minimal set of values:
l p4=0 (East boundary point) or
l p6=0 (South boundary point) or
l p2=0 and p8=0 (NW corner point)
l [C,D] p2.p4.p8=0 and p2.p6.p8=0 are satisfied
simultaneously by minimal set of values:
l p2=0 (North boundary point) or
l p8=0 (West boundary point) or
l p4=0 and p6=0 (SE corner point)
l NE corner point (p2=0 and p4=0) satisfy [c,d] and [C,D]
l SW corner point (p6=0 and p8=0) satisfy [c,d] and [C,D]112
Skeleton: Example
113

Thinning : Example
Input image Output

Morphological Operations
l Operations on binary images Examples of SE
with a structuring element to
perform morphological
(structural) changes or
extract the features Points conforming
to ‘Fit’ operations
l Structural element (SE):
l a set of points in the digital grid
with a reference integral
coordinate system.
l Performs ‘Hit’ or ‘Fit’ operation
at any point in the digital grid. 115

Reflection and Translation
Bˆ = {w | w = -b, for b Î B}
( A) z = {c | c = a + z, for a Î A}
Reflection
Translation
116
Basic morphological
operations
n Erosion Keep general shape
but smooth with
respect to object /
n Dilation background
n combine to
n Opening object
n Closing background
117
Erosion
n Does the structuring element fit the set?
n erosion of a set A by structuring element B: all z in
A such that B is in A when origin of B=z
A - B = {z|(B)z Í A}
A - B = {z|(B)z Ç A = F} c
n shrink the object
118
Erosion
119
Erosion
120
Erosion Example 1
Original Erosion by 3*3 Erosion by 5*5

image square structuring square structuring
element element
Watch out: In these examples a 1 refers to a black pixel!
121
Erosion: Example
Input image Eroded image

Erosion Example 2
Original After
image erosion
with a
disc of
radius 10
After After
erosion erosion
with a with a
disc of disc of
radius 5 radius 20 123
What Is Erosion For?

Erosion can split apart joined objects
Erosion can strip away extrusions
Watch out: Erosion shrinks objects! 124

Dilation
l Does the structuring element hit the set?

l dilation of a set A by structuring element B: all z in
A such that B hits A when origin of B=z
A Å B = {z|(Bˆ )z Ç A ¹ Φ}
A Å B = {z|[(Bˆ ) Ç A] Í A} z
l grows the object

125
Dilation
126
Dilation
127
Dilation Example
Original image Dilation by 3*3 Dilation by 5*5

square square
structuring structuring
element element
Watch out: In these examples a 1 refers to a black pixel!
128
Dilation: Example
Input image Dilated Image

Dilation : Bridging gaps
130
What Is Dilation For?
Dilation can repair breaks
Dilation can repair intrusions
Watch out: Dilation enlarges objects 131

Useful
n Erosion
n removal of structures of certain shape and size,
given by SE
n Dilation
n filling of holes of certain shape and size, given
by SE
132
Duality
l Erosion and Dilation are duals of each other with

respect to set complementation and reflection
( A - B) = A Å Bˆ
c c
( A Å B) = A - Bˆ
c c
133
5 basic structuring elements
134
Combining erosion and
dilation
n WANTED:
n remove structures / fill holes
n without affecting remaining parts
n SOLUTION:
n combine erosion and dilation
n (using same SE)
135
Erosion followed by dilation:
eliminating irrelevant detail
structuring element B = 13x13 pixels, each set to 1.

136
Opening
erosion followed by dilation, denoted ∘
A  B = ( A - B) Å B
l eliminates protrusions
l breaks necks
l smoothes contour
137
Opening
138
Opening
02-Sep-11 139
Opening Example
Original
Image
Image
After
Opening
140
Closing
dilation followed by erosion, denoted •
A • B = ( A Å B) - B
l smooth contour
l fuse narrow breaks and long thin gulfs
l eliminate small holes
l fill gaps in the contour
141
Closing
142
Closing
143
Closing Example
Original
Image
Image
After
Closing
Image Morphology 144
Properties
Opening
(i) A°B is a subset (subimage) of A
(ii) If C is a subset of D, then C °B is a subset of D °B
(iii) (A °B) °B = A °B
Closing
(i) A is a subset (subimage) of A•B
(ii) If C is a subset of D, then C •B is a subset of D •B
(iii) (A •B) •B = A •B
Note: repeated openings/closings has no effect!

145
Duality
l Opening and Closing are duals of each other with

respect to set complementation and reflection
( A • B) = A  Bˆ
c c
( A  B) = A • Bˆ
c c
146
Hit-or-Miss Transformation ⊛
(HMT)
n find location of one shape among a set of shapes
n ”template matching”
n composite SE: object part (B1) and background

part (B2)
n does B1 fits the object while, simultaneously,
B2 misses the object, i.e., fits the background?
147
Hit-or-Miss Transformation
A * B = ( A - B1 ) Ç [ A - B2 ] c
A * B = ( A - B1 ) - ( A Å Bˆ 2 )
148
Hit-or-Miss transformation
Searching for white pixels, that do not

have 4-connected neighboring pixels.
B1
Original image Erosion with B1

(white pixels)
B2
Complement Erosion with B2
149
Application: Boundary
Extraction
b ( A) = A - ( A - B)
150
Boundary / Contour
Extraction
151
Application: Hole Filling
The key equation for region filling is
X k = ( X k -1 Å B) Ç A c
k = 1,2,3.....
Where X0 contains a starting point inside in each
hole hole, B is a symmetric structuring element and
Ac is the complement of A
This equation is applied repeatedly until Xk is equal
to Xk-1
Finally, union of the result with A is performed.
152
Region Filling
X k = ( X k -1 Å B) Ç A c
k = 1,2,3,...
153
Application: Extraction of
connected components
l Y: A connected component in a set A.
l p: A point in Y.
l For extracting connected component Y perform
the following iteratively with X0=p:
𝑋! = 𝑋!"# ⊕ 𝐵 ⋂𝐴, 𝑘 = 1,2,3
Terminates when Xk=Xk-1 to provide Y.
154
Connected components
155
Application: Convex Hull
l Convex Set
l A set A is said to be convex if the straight
line segment joining any two points in A
lies entirely within A.
l Convex Hull: H = CH(S)
l Minimal convex superset of S
l Continuous Algorithm
l Convex Deficiency: H – S
156
Approximate solution!
Convex Hull
l Bi, i=1,2,3, 4 : Four structuring elements
l Perform the following iterative construction for
each structuring element to provide Di at
convergence.
𝑋!$ = 𝑋!"#
$
⊛ 𝐵$ ⋃𝐴, 𝑖 = 1,2,3, 𝑎𝑛𝑑 4; 𝑘 = 1,2,3, …
&
The convex hull of A: 𝐶 𝐴 = 8 𝐷$

$%#
Constraints: Length of vertical and horizontal to be less than 3.

157
Convex hull

158
Convex Hull

159
Thinning
l The thinning of a set A by a structuring element B.
𝐴⨂𝐵 = 𝐴 − (𝐴 ⊛ 𝐵)
l A more useful expression using an alternate
sequence of structuring elements till convergence.
𝐵 = 𝐵# , 𝐵 ' , … . , 𝐵 (
l Where Bi is a rotated version of Bi-1.
𝐴⨂ 𝐵 = ⋯ 𝐴⨂𝐵# ⨂𝐵' ⋯ ⨂𝐵(
160
Thinning
A Ä B = A - ( A * B)
= A Ç ( A * B) c
161
Thinning
162
Thickening
l Thickening morphological dual of thinning.
𝐴⨀𝐵 = 𝐴⋃(𝐴 ⊛ 𝐵)
l The SE has the same form but 1’s (foreground) and 0’s
(background) interchanged.
l As in thinning, thickening also performed using an
alternate sequence of rotated SEs till convergence.
𝐴⨀ 𝐵 = ⋯ 𝐴⨀𝐵# ⨀𝐵' ⋯ ⨀𝐵(
l Equivalent to thinning background of the thinned
pattern and then taking the complement.
l The thinned background forms the boundary of the
thickened object. 163
Thickening
A • B = A È ( A * B)
164
Skeletons

165
Skeletons &
l Morphological Skeleton: 𝑆 𝐴 = ) 𝑆# (𝐴)
#$%
l Where, 𝑆& 𝐴 = 𝐴 ⊝ 𝑘𝐵 − 𝐴 ⊝ 𝑘𝐵 ∘ 𝐵
k successive erosion.
l k is the last iterative step before A erodes to an empty set.
l The set A can be reconstructed by
&
𝐴=) 𝑆# (𝐴)⨁𝑘𝐵
#$%
k successive dilation.
166
These pixels
wrongly shown
as object points
after the erosion
with radius 1.
Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008 167

Summary
l Binary or Bilevel images: f: Z2 (or Z3 or Zn )à {0/1}
l Background (0) and Foreground or Object Point (1)
l Neighbors, Connectivity, Paths and Distances
l 2D: 4 / 8 –neighbors 3D: 6 / 18 / 26 –neighbors.
l Multiple paths of shortest distances exist.
l Jordan’s Curve Theorem breaks.
l 4-8 or (8-4) Grids for complementary adjacency in
background and foreground.
l Component Labeling: Chamfering (Linear Time)
l Different types of distances
l 4 (/8)-Neighbor in 2D and 6(/18/26)-Neighbor in 3D
l Octagonal distances
l Weighted distances
Summary
l Distance Transform
l Chamfering Algorithm for Additive Distances
l Medial Axis Transform
Applications: Transformation, Cross-sections, Skeleton
l
l Shape representation.
l Contour following, Chain Codes
l Polygonization
l Minimum-perimeter polygon (MPP), ADSS algorithm,
Merging and Splitting
l Skeletonization: Thinning
l Morphological Operations
l Dilation, Erosion, Opening, Closing, Hit-&-Mis Transform
l Applications: Smoothing, Convex Hull, Region Filling,
Thinning, Connected Component Extraction, Thinning
Thank You
170

IP Digital Geometry L2

Uploaded by

Copyright:

Available Formats

IP Digital Geometry L2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

IP Digital Geometry L2

Uploaded by

Copyright:

Available Formats

Digital Image:

Regular Archimedean Tiling

Triangular Hexagonal Rectangular

l Digital Distance Function ( different domain and range)

l Exact analysis: As they are in the digital space.

l Digital Distance Function:

l A function of two points in a space measuring their

u º (u(1), u(2),........, u(n))

L¥ (u, v) = max{| u(i) - v(i) |}

Desirable: Compact and bounded.

Length of the path ≈n. ε

i. d (u , v) = 0 iff u = v d is defined for

For u, vÎZ2 and x = |u – v|=(x1, x2),

d<a,b>(u, v) = a.max(x1 , x2 )+ (b-a). min(x1 , x2 )

6–Neighbors 18–Neighbors 26–Neighbors

For u, v Î Z3 and x = |u – v|,

d6(u, v) = x1 + x2 + x3, (grid distance)

Like 2D, in 3D also Octagonal and

{1,2} {1,1,2} {1,1,1,2}

{1,1,2} {1,1,3} {1,2,3}

theorem in digital space

Foreground points with similar configuration!

Two Scan Labeling

l Check the labels (a number) of neighbors at a foreground point p

l For all pixels p of an image S, the DT algorithm

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

l Let f = |F|, b = |B|, f + b = n

l Often f = O(n) and b = O(n)

l Number of distance computations = f.b = O(n2)

We need a better algorithm

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Input image Output

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

A set of maximal blocks contained in the pattern.

• Compute the distance transform.

• Geometric Transformation (Kumar et al ’96)

Compute the set of Maximal Blocks.

Vincent ’91, Ragnemalm ’93, Svensson-Borgefors-Nystrom ’99

l Normal at a point p computed by computing

J. Mukhopadhyay, et al (2013), "Digital Geometry in

J. Mukhopadhyay, et al (2013), "Digital Geometry

J. Mukhopadhyay, et al (2013), "Digital Geometry

J. Mukhopadhyay, et al (2013), "Digital Geometry

J. Mukhopadhyay, et al (2013), "Digital Geometry

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Boundary (Contour) Following

Contour following algorithm

excluding it from consideration .

(a) (8 , 4) digital grid.

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Boundary of an object In the discrete grid MPP: Vertices from

Courtesy: R.C. Gonzalez and R.E Woods © 1992-2008

Courtesy: P.P. Das, Professor, Dept. of CSE, IIT Kharagpur

Original Erosion by 33 Erosion by 55

Original image Dilation by 33 Dilation by 55