Transcript black white pictures

Two dimensional thining
Let P =(V, m, n, B) and P ' = (V, m, n, B - D) be digital pictures, where
D  B. Then we say that P' is obtained from P by deleting the points in D.
Alternatively, we may say that P is obtained from P' by adding the points in
D.
Image thinning is a common pre-processing operation in pattern recognition.
Its goal is to reduce the set of black points to a "skeleton" in a "topologypreserving" way.
Effect of a thinning
algorithm on the (8, 4)
digital picture
1
Maximal ball
Let denote by Br(x) the ball of radius r (strictly positive integer) centred on
x є Z2, defined by Br(x) = {y є Z2, d(x, y) ≤ r}, where function
d:Z2→R+∪ {0} is a metric.
Let assume a digital image (Z2, m, n, B). A ball Br(x)  B is maximal for B if
it is not strictly included in any other ball included in B.
The medial axis of B, denoted by MA(B), is the set of the centres of all the
maximal balls for B.
Examples of balls of radiuses 1, 2, 3 respectively (city distance)
2
Example of medial axis
2 2 2 2 2 2 2
3 2 2 2 2 2 2 2 2
1 1 1
1 1 1
2
2
[Malina 02] p. 83
3
Medial axis vs thining and shrinking
A non-topological requirement of a thinning algorithm is that each elongated part of
the input black point set should be represented by a black digital arc in the output
skeleton.
An algorithm which does not meet this condition, but merely deletes black points
while preserving the topology of the image, is called a shrinking algorithm.
Input object
One iteration of
thining
Shrinking result
Medial axis
Thining result
[Coup 07]
4
Topology preservation criterion
Let P = (Z2, m, n, B) P' = (Z2, m, n, B - D) be a two-dimensional digital
pictures. Then deletion of the points in a subset D of B preserves
topology if and only if
•
each black component of P contains exactly one black component of P',
and
• each white component of P' contains exactly one white component of P,
Example 1: (8,4) dig. pic.
P
Example 2: (8,4) dig. pic.
P’
P
P’
5
Topology preservation criterion
Let P = (Z2, m, n, B) be a two-dimensional digital picture. Then deletion of
the points in a subset D of B preserves topology if and only if
•
each black component of P contains exactly one black component of P',
and
• each white component of P' contains exactly one white component of P,
where P' is the digital picture (Z2, m, n, B - D).
Example 3: (8,4) dig. pic.
P
P’
6
Simple point
A black point p in a two-dimensional digital picture is called a simple point
if its deletion preserves topology in the sense of Criterion from the previous
slide.
a


c
b

[Coup 10]
7
Theorem on simple points in 2D
Let pp be
be aanon-isolated
non-isolatedborder
borderpoint
pointininanan
(8,(8,
4) 4)
or (4,
or (4,
8) digital
8) digital
picture.
picture.
Let
B be the
Then
p isblack
a simple
pointpoint
set of
iffthe
T(p)
digital
= 1 and
picture
Tb(p)
and
= 1let B' = B — { p}. Then
p is a simple point iff:
•
p is adjacent to just one component of N8(p) ∩ B'.
•
p is adjacent to just one component of N8(p) ∩ B*, where B* = Z2 \ B
Where N8(p) is a 8-neighbourhood of p. (def. in slide 7). Proof in ()
Let introduce:
a

T(p) – number of components of N8(p) ∩ B'.
Tb(p) – number of components of N8(p) ∩ B*

So: T(a) = Tb(a) = 1; T() = Tb() = 2; T()=0,
Tb()=1
8
Sequential deletion of simple points
Let P0, P1,..., Pn be a sequence of digital pictures. If for each 1 < i < n the
picture Pi+1 is obtained by deleting a simple point of Pi, from Pi then we
say that Pn is obtainable from P0 (or that P0 can be transformed into Pn)
by sequential deletion of simple points.
Important!
• A simple point of Pi, need not be a simple point of P0;
• A black point of Pi that is a simple point of P0 need not be a simple point
of Pi
9
Example of sequential deletion of simple points
P0
P1
P2
P3
P4
P5
P6
P7
P8
P9
10
Problem with parallel deletion of simple points
p
P0
q
s
P1
P2
P3
P6
P7
t
P4
P5
P8
P9
11
Theorems about sequential deletion of simple points
• Any finite (4, 8) or (8, 4) digital picture whose black point set is non-empty and
connected and has no holes can be transformed by sequential deletion of simple
points to a digital picture with just one black point. [Rose 70]
• Finite (4, 8) digital picture whose black point set is connected and has just one
hole can be transformed by sequential deletion of simple points to a digital
picture whose black point set is a simple closed black curve. [Rose 73]
• Finite (4, 8) and (8, 4) digital picture topology preservation in the sense of the
criterion from slide 28 is equivalent to the condition that P' be obtainable from P
by sequential deletion of simple points. [Rose 98]
• In any finite (4, 8) digital picture sequential deletion of simple points will
eventually produce a digital picture whose black point set does not contain any 2
by 3 arrays of black points. [Alex 71]
• Given two finite (4, 8) digital pictures whose black point sets are connected, and
which have the same number of holes, it is possible to transform one to the other
by sequential addition and deletion of simple points. [Mylo 71]
12
2D parallel thinning algorithms
It is generally quite tricky to prove that a proposed parallel thinning
algorithm satisfies the criterion from slide 28. For an example of such a
proof see [Stef 71].
Unfortunately such proofs often have to be done from first principles.
13
Theorem on border parallel deletion of points
A black point with coordinates (x, y) is said to be a north border point if the
point (*, y + 1) is a white point.
An end point of a two-dimensional digital picture is a black point that is
adjacent to just one other black point.
Theorem 2. Let P be an (8, 4) or a (4, 8) digital picture. Then (parallel)
deletion of any number of simple north border non-end points of P
preserves topology in the sense of criterion from slide 27.
Simple north-border non-end
points in an (8, 4) digital picture
14
Border sequential
Theorem 2 obviously remains valid if "east," "south," or "west" is
substituted for "north." However, the restriction that border points are
deleted from just one side (north) is necessary.
q
p
Simple non-end points in an (8, 4) digital
picture whose parallel deletion will merge
two white components
Theorem 2 is applicable to algorithms which delete points in parallel from
each side in turn (e.g., in the order N, S, E, W). Such algorithms have been
called border sequential [Hild 83].
15
Topological characteristic of points in 2D
A latice point p is:
Simple point: T(p) = 1 Tb(p) = 1 (see slide 30)
Interior point: Tb(p) = 0
Isolated point T(p) = 0
Curve point T(p) = 2 and Tb(p) = 2
Curve junction point T(p)=3 or Tb(p)=3
border point
Interior point
Isolated point
curve point
junction point
between curves
17
Theorem about simple points in 3D
Let X ⊆ Z3 and x ∊ X.
K6(x, X) –number of components of N18(x) ∩ X \ {x} adjacent to x.
K26(x, X) –number of components of N26(p) ∩ X \{x} adjacent to x.
Let p be u non-isolated border point in an (m, n) digital picture. Let B be the
black point set of the digital picture.
Then p is a simple point iff Km(p, B) = 1 and Kn(p, B*) = 1,
where B* = Z3 - B
18
Topological numbers T, Tb in 3D
In 3D we similarly calculate T(p) and Tb(p), for a black point p and
(Z3, 26, 6, B) digital image.
T(p) = K26(p, B) and Tb(p) = K6(p, B*)
T(p) is calculated as a number of black 26-components in N26(p) - {p}
N26(p)-{p}
T(p) = 1
p
19
Topological numbers T, Tb in 3D
Tb(p) is calculated as a number of white 6-components in N18(p) 6-adjacent
to p.
N18(p)
Tb(p) = 3
p
20
Topological characteristic of points in 3D
For a 3D (26, 6) digital image a point p is:
An interior point
A isolated point
A border point
A curve point
A curves junction
A surface point
A surface-curve(s) junction
A surfaces junction
A surfaces-curve(s) junction
Tb(p) = 0
T(p) = 0
T(p) = 1
T(p) = 2
T(p) > 2
T(p) = 1
T(p) ≥ 2
T(p) = 1
T(p) ≥ 2
and
and
and
and
and
and
and
Tb(p) = 1
Tb(p) = 1
Tb(p) = 1
Tb(p) = 2
Tb(p) = 1
Tb(p) > 2
Tb(p) > 2
Border
points
Junction between
curves
Junction between
surfaces
curve
Junction
curve-surface
surface
[Malan 10]
21
Example
Fragment of (26, 6) image. Junction between surfaces: T(p) = 1 and Tb(p) > 2
Calculation of T(p)
N26(p)-{p}
T(p) = 1
p
Calculation of Tb(p)
N18(p)
Tb(p) = 4
p
22