PA170 Digital Geometry
Lecture 09: Content Measurement
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
Motivation: Convergence of Estimators
A real disk D of unit diameter has the area A(D) = π
4 and the perimeter P(D) = π
The area of a digitized disk converges toward the area of the real disk with an
increasing grid resolution h:
lim
h→∞
A(digh(D)) = A(D) =
π
4
The perimeter of a digitized disk does not converge toward the perimeter of the real
disk:
lim
h→∞
P(digh(D)) = 4
h = 1 h = 5 h = 10 h = 17
2/16
Multigrid Convergence
Let F be a family of sets S in Rn, digh(S) be a digitization of S on a grid of resolution
h, and Q be a property (e.g., area, perimeter, or length) defined for all S ∈ F
An estimator EQ is called multigrid convergent for F and for digh iff, for any S ∈ F,
there is a grid resolution hS > 0 such that the estimated value EQ(digh(S)) is defined
for any grid resolution h ≥ hS, and
|EQ(digh(S)) − Q(S)| ≤ κ(h)
where κ is a speed of convergence function that converges toward zero as h → ∞
Examples of theoretical results (for any grid resolution h > 0 and Gauss digitization Gh)
For any planar convex set S, |A(Gh(S)) − A(S)| = O(h−1) [Gauss & Dirichlet]
For any centered disk D, |A(Gh(D)) − A(D)| = Ω(h−1.5) [Hardy 1913]
For any planar convex 3-smooth set S, |A(Gh(S)) − A(S)| = O(h−100
73 · (log h)
315
146 )
[Huxley 1993]
3/16
AREA ESTIMATION
Area Estimators
Let S ⊆ R2 be a planar compact set and A(S) be its true area
The area of the Gauss digitization Gh(S) converges toward A(S)
The area of the inner and outer Jordan digitizations J−
h (S) and J+
h (S), respectively,
converges toward A(S) too
Therefore, the area of any digitization between J−
h (S) and J+
h (S) also converges
toward A(S)
5/16
Discrete Column-Wise Integration
The area A(Π) of an isothetic grid polygon Π can be calculated as
A(Π) =
1
h2
· (α0 −
L
2
− 1)
where h > 0 is grid resolution, α0 is the number of grid points in Π, and L is the total
length of its frontier
Both L and α0 can easily be calculated during border tracing. In particular, α0 can be
calculated using discrete column-wise integration:
1 α0 = 0
2 α0 = α0 + y for all grid points (x, y) at the upper end of a vertical run of object grid points
3 α0 = α0 − y + 1 for all grid points (x, y) at the bottom end of such a run
6/16
LENGTH ESTIMATION
Preliminaries
The frontier of a simply connected, planar compact set S is a simple, rectifiable curve
γ : [0, 1] → R2
Three possible digitizations of γ are as follows:
[A] A cyclic ordered sequence ρh(γ) of grid points derived from the grid-intersection
digitization of γ in Z2
h
[B] A cyclic ordered sequence of grid vertices of 2-cells on the frontier of the Gauss
digitization Gh(S) of S
[C] The closed difference set between the outer and inner Jordan digitizations (i.e.,
M = (J+
h (S) \ J−
h (S))•
)
Set S and its topological frontier γ Cyclic ordered sequence ρh(γ)
8/16
Local Estimators ([A])
The true curve length L(γ) is approximated as a weighted sum of different types of
steps in ρh(γ), which is easy to implement and unique, but not multigrid convergent
Let ni and nd be the number of isothetic and diagonal steps, respectively, and nc be
the number of transitions between these two types of steps in ρh(γ)
The geometric length estimator approximates L(γ) as
LGEOM(ρh(γ)) =
1
h
· (ni +
√
2 · nd )
The best linear unbiased estimator minimizes the mean square error between the
estimated and true curve length:
LBLUE (ρh(γ)) =
1
h
· (0.948 · ni + 1.343 · nd )
The cornercount estimator approximates L(γ) as
LCOC(ρh(γ)) =
1
h
· (0.980 · ni + 1.406 · nd − 0.091 · nc)
9/16
DSS-Based Estimators ([B])
The true curve length L(γ) is approximated by integrating lengths of the
maximum-length digital straight line segments in the digitization of γ, which is easy to
implement and multigrid convergent, but not unique
The basic DSS-based estimator calculates LDSS(digh(γ)) as the length of the
resulting polygon (or of the polygonal arc in case of open curves)
The most probable original length estimator calculates LMPO(digh(γ)) by replacing
the real DSS lengths in LDSS(digh(γ)) with n
h · 1 + a2
h where n is the length of the
binary-word representation of a particular DSS and ah is the estimation of its slope
10/16
Tangent-Based Estimator: Preliminaries
Let γ(t) be a parametrized curve (i.e., γ(t) = (x(t), y(t)), a ≤ t ≤ b)
Apart from uniquely determining the geometric location of all the curve points, a
parametrization provides information about the curve orientation and its speed v(t):
v(t) = ˙γ(t) 2 = ( ˙x(t), ˙y(t)) 2
where
˙x(t) =
dx(t)
dt
and ˙y(t) =
dy(t)
dt
If γ is rectifiable, its length L(γ) is given as
L(γ) =
b
a
v(t)dt =
b
a
( ˙x(t), ˙y(t)) 2dt =
b
a
( ˙x(t))2 + ( ˙y(t))2dt
11/16
Tangent-Based Estimator ([B])
The true curve length L(γ) is approximated by integrating ( ˙x, ˙y) 2 along digh(γ),
which is multigrid convergent and unique, but substantially slower than local and
DSS-based estimators due to the cost associated with the estimation of normals
By tracing the ordered sequence of 0-cells and estimating digitized curve normals at
these locations using a DSS algorithm, the tangent-based estimator approximates
L(γ) as
LTAN(digh(γ)) =
p∈A
n1(p) + n2(p)
2
· n0(p)
where A is the set of all frontier 1-cells of digh(γ), n0(p) is the unit normal to p ∈ A,
and n1(p) and n2(p) are the estimated normals at the endpoints of p
12/16
MLP-Based Estimators ([C])
In case of closed curves, MLP is a minimum-length polygon that circumscribes the
inner frontier of M and is in the interior of its outer frontier
In case of open curves, MLP is a minimum-length polygonal arc that is incident with
all 2-cells in M
The MLP-based estimator calculates LMLP(digh(γ)) as the length of the resulting
polygon (or the polygonal arc in case of open curves), which is multigrid convergent
and unique, but slower than local and DSS-based estimators due to the cost
associated with the MLP construction
13/16
Comparison of Length Estimators: Main Observations
A comparative study of the introduced length estimators conducted in [Coeurjolly &
Klette, 2004]
The analyzed dataset contained convex as well as nonconvex shapes, digitized on
grids of sizes between 30×30 and 1000×1000 grid points
Main Observations
All the evaluated estimators converge, but the local ones toward false values with
relative errors about 2 % at maximum grid resolution
All the evaluated estimators run in linear time, but TAN is roughly three times slower
than its competitors at maximum grid resolution
All the evaluated estimators but the local ones are nearly orientation-independent,
with relative errors up to 2 %. The relative error committed by BLUE is from 4 % to
12 % for a square rotated between 30 and 60 degrees
14/16
Length Estimators: Summary
Method Multigrid Discrete Unique
GEOM No Possibly Yes
BLUE No Possibly Yes
COC No Possibly Yes
DSS Yes Yes No
MPO Yes Yes No
TAN Yes Yes Yes
MLP Yes Yes Yes
Multigrid Is the estimator multigrid convergent at least for convex curves?
Discrete Does the core of the estimation algorithm deal only with integers?
Unique Is the result independent of initialization?
15/16
Take-Home Messages
The area of Gauss as well as inner and outer Jordan digitizations of planar compact
sets converge to true areas of these sets
Local length estimators are fast and unique, but not multigrid convergent
DSS-based and MPO-based estimators are multigrid convergent, but not unique
MLP-based and TAN-based estimators are multigrid convergent and unique at the
expense of their speed
16/16