The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis
We define the Pascal triangle of a discrete (gray scale) image as a pyramidal arrangement of complex-valued moments and we explore its geometric significance. In particular, we show that the entries of row k of this triangle correspond to the Fourier series coefficients of the moment of order k of t...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут математики НАН України
2013
|
| Schriftenreihe: | Symmetry, Integrability and Geometry: Methods and Applications |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/149235 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis / M. Boutin, S. Huang // Symmetry, Integrability and Geometry: Methods and Applications. — 2013. — Т. 9. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-149235 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1492352019-02-20T01:24:05Z The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis Boutin, M. Huang, S. We define the Pascal triangle of a discrete (gray scale) image as a pyramidal arrangement of complex-valued moments and we explore its geometric significance. In particular, we show that the entries of row k of this triangle correspond to the Fourier series coefficients of the moment of order k of the Radon transform of the image. Group actions on the plane can be naturally prolonged onto the entries of the Pascal triangle. We study the prolongation of some common group actions, such as rotations and reflections, and we propose simple tests for detecting equivalences and self-equivalences under these group actions. The motivating application of this work is the problem of characterizing the geometry of objects on images, for example by detecting approximate symmetries. 2013 Article The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis / M. Boutin, S. Huang // Symmetry, Integrability and Geometry: Methods and Applications. — 2013. — Т. 9. — Бібліогр.: 8 назв. — англ. 1815-0659 2010 Mathematics Subject Classification: 30E05; 57S25; 68T10 DOI: http://dx.doi.org/10.3842/SIGMA.2013.031 http://dspace.nbuv.gov.ua/handle/123456789/149235 en Symmetry, Integrability and Geometry: Methods and Applications Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We define the Pascal triangle of a discrete (gray scale) image as a pyramidal arrangement of complex-valued moments and we explore its geometric significance. In particular, we show that the entries of row k of this triangle correspond to the Fourier series coefficients of the moment of order k of the Radon transform of the image. Group actions on the plane can be naturally prolonged onto the entries of the Pascal triangle. We study the prolongation of some common group actions, such as rotations and reflections, and we propose simple tests for detecting equivalences and self-equivalences under these group actions. The motivating application of this work is the problem of characterizing the geometry of objects on images, for example by detecting approximate symmetries. |
| format |
Article |
| author |
Boutin, M. Huang, S. |
| spellingShingle |
Boutin, M. Huang, S. The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis Symmetry, Integrability and Geometry: Methods and Applications |
| author_facet |
Boutin, M. Huang, S. |
| author_sort |
Boutin, M. |
| title |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis |
| title_short |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis |
| title_full |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis |
| title_fullStr |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis |
| title_full_unstemmed |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis |
| title_sort |
pascal triangle of a discrete image: definition, properties and application to shape analysis |
| publisher |
Інститут математики НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/149235 |
| citation_txt |
The Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis / M. Boutin, S. Huang // Symmetry, Integrability and Geometry: Methods and Applications. — 2013. — Т. 9. — Бібліогр.: 8 назв. — англ. |
| series |
Symmetry, Integrability and Geometry: Methods and Applications |
| work_keys_str_mv |
AT boutinm thepascaltriangleofadiscreteimagedefinitionpropertiesandapplicationtoshapeanalysis AT huangs thepascaltriangleofadiscreteimagedefinitionpropertiesandapplicationtoshapeanalysis AT boutinm pascaltriangleofadiscreteimagedefinitionpropertiesandapplicationtoshapeanalysis AT huangs pascaltriangleofadiscreteimagedefinitionpropertiesandapplicationtoshapeanalysis |
| first_indexed |
2025-07-12T21:10:08Z |
| last_indexed |
2025-07-12T21:10:08Z |
| _version_ |
1837476994566062080 |
| fulltext |
Symmetry, Integrability and Geometry: Methods and Applications SIGMA 9 (2013), 031, 25 pages
The Pascal Triangle of a Discrete Image: Definition,
Properties and Application to Shape Analysis?
Mireille BOUTIN † and Shanshan HUANG ‡
† School of Electrical and Computer Engineering, Purdue University, USA
E-mail: mboutin@purdue.edu
‡ Department of Mathematics, Purdue University, USA
E-mail: huang94@purdue.edu
Received September 24, 2012, in final form April 03, 2013; Published online April 11, 2013
http://dx.doi.org/10.3842/SIGMA.2013.031
Abstract. We define the Pascal triangle of a discrete (gray scale) image as a pyramidal
arrangement of complex-valued moments and we explore its geometric significance. In par-
ticular, we show that the entries of row k of this triangle correspond to the Fourier series
coefficients of the moment of order k of the Radon transform of the image. Group actions
on the plane can be naturally prolonged onto the entries of the Pascal triangle. We study
the prolongation of some common group actions, such as rotations and reflections, and we
propose simple tests for detecting equivalences and self-equivalences under these group ac-
tions. The motivating application of this work is the problem of characterizing the geometry
of objects on images, for example by detecting approximate symmetries.
Key words: moments; symmetry detection; moving frame; shape recognition
2010 Mathematics Subject Classification: 30E05; 57S25; 68T10
1 Definition and reconstruction properties
Let {(xk, yk)}Nk=1 with xk, yk ∈ R represent the pixel locations of a digital image. For simplicity,
we use complex coordinates zk = xk + iyk. Consider a gray scale image defined on {zk}Nk=1.
More specifically, we have a mapping ρ : {zk}Nk=1 → R≥0, where ρ(zk) represents the intensity
of pixel zk.
1 Denote the discrete gray scale image by I = {(zk, ρ(zk))}Nk=1.
Consider the following moment matrix:
τN (I) =
µ0,0 µ1,0 µ2,0 µ3,0 · · · µN−1,0
µ0,1 µ1,1 µ2,1 · · · · · · µN−1,1
µ0,2 µ1,2 · · · · · · · · · µN−1,2
µ0,3 · · · · · · · · · · · · µN−1,3
...
...
µ0,N−1 µ1,N−1 · · · · · · · · · µN−1,N−1
N×N
,
where µj,l =
N∑
k=1
zjkz̄
l
kρ(zk), j, l ∈ Z≥0 is the complex moment of order (j, l) for the discrete
image I. Observe the conjugate symmetry property of the moments µj,l = µ̄l,j . In particular,
µj,j ∈ R, ∀ j ∈ Z≥0.
?This paper is a contribution to the Special Issue “Symmetries of Differential Equations: Frames, Invariants
and Applications”. The full collection is available at http://www.emis.de/journals/SIGMA/SDE2012.html
1We use R≥0 instead of a specific discrete domain such as {0, 1, . . . , 255} for more generality.
mailto: mboutin@purdue.edu
mailto: huang94@purdue.edu
http://dx.doi.org/10.3842/SIGMA.2013.031
http://www.emis.de/journals/SIGMA/SDE2012.html
2 M. Boutin and S. Huang
We can express the relationship between the moments and the image I in matrix form:
τN (I) = Z†WZ, (1)
where
Z =
1 z1 z21 · · · zN−11
1 z2 z22 · · · zN−12
...
... · · ·
...
1 zN z2N · · · zN−1N
, W =
ρ(z1) 0 · · · 0
0 ρ(z2) · · · 0
...
...
. . .
...
0 · · · 0 ρ(zN )
,
and Z† is the conjugate transpose of Z. Observe that Z is a Vandermonde matrix and therefore
is invertible when the pixel locations zk are pairwise distinct. Therefore, if the pixel coordinates
are known and pairwise distinct, one can reconstruct the image I by matrix inversion: W =
(Z−1)†τN (I)Z−1.
Definition 1. Let r be a nonnegative integer and let I be a discrete gray scale image. The
Pascal triangle T r(I) of order r of I is the following pyramid:
µ0,0
µ0,1 µ1,0
µ0,2 2µ1,1 µ2,0
µ0,3 3µ1,2 3µ2,1 µ3,0
µ0,4 4µ1,3 6µ2,2 4µ3,1 µ4,0
...
µ0,r (r1)µ1,r−1 · · · (rl)µl,r−l · · · ( r
r−1)µr−1,1 µr,0
Lemma 1 (pixel intensity reconstruction property). If the grid point locations {zk}Nk=1 are
known and pairwise distinct, then the image I can be reconstructed from the Pascal triangle
TN−1(I) of order N − 1. More specifically, knowledge of the entries of the right diagonal row of
TN−1(I), i.e. {µj,0}N−1j=0 , is sufficient for image reconstruction2.
Proof. Recall the definition of the moments
µj,l =
N∑
k=1
zjkz̄
l
kρ(zk).
We consider the vector formed by the moments {µj,0}N−1j=0 , which can be written in matrix
form as
µ0,0
µ1,0
µ2,0
...
µN−1,0
=
1 1 · · · 1
z1 z2 · · · zN
z21 z22 · · · z2N
...
...
...
...
zN−11 zN−12 · · · zN−1N
ρ(z1)
ρ(z2)
...
ρ(zN )
. (2)
Observe that the coefficient matrix in (2) is a Vandermonde matrix. The Vandermonde
matrix has full rank when zj 6= zk for all distinct j, k = 1, 2, . . . , N . Thus, since the pixel
locations are assumed to be distinct, we can reconstruct the pixel intensities {ρ(zk)}Nk=1 by
inverting the coefficient matrix and multiplying by the moment vector on the left-hand-side. �
2The fact that the pixel intensities can be reconstructed from a finite number of moments was stated in [3].
Our lemma provides a clear statement of the conditions under which this reconstruction is theoretically possible.
The Pascal Triangle of a Discrete Image 3
Notice that if we consider the Pascal triangle TN (I) of order N , then knowledge of the second
right diagonal row of TN (I), i.e. {µj,1}N−1j=0 , is also sufficient for image reconstruction as long as
the zk’s are pairwise distinct and nonzero. This is because the vector formed by the moments
{µj,1}N−1j=0 can be written in matrix form as
µ0,1
µ1,1
µ2,1
...
µN−1,1
=
z̄1 z̄2 · · · z̄N
z1z̄1 z2z̄2 · · · zN z̄N
z21 z̄1 z22 z̄2 · · · z2N z̄N
...
...
...
...
zN−11 z̄1 zN−12 z̄2 · · · zN−1N z̄N
ρ(z1)
ρ(z2)
...
ρ(zN )
=
1 1 · · · 1
z1 z2 · · · zN
z21 z22 · · · z2N
...
...
...
...
zN−11 zN−12 · · · zN−1N
z̄1 0 · · · 0
0 z̄2 · · · 0
...
...
. . .
...
0 0 · · · z̄N
ρ(z1)
ρ(z2)
...
ρ(zN )
. (3)
The coefficient matrix in (3) is a Vandermonde matrix multiplied by a diagonal matrix. As-
suming that the pixel locations are pairwise distinct insures that the Vandermonde matrix
is invertible, and further assuming that they are nonzero insures invertibility of the diagonal
matrix. Hence the coefficient matrix in (3) is nonsingular and we can reconstruct the pixel
intensities {ρ(zk)}Nk=1 from TN (I) by inverting this coefficient matrix and multiplying by the
moment vector on the left-hand-side.
A similar argument can be used to show that, for any fixed l, the pixel intensities can be
reconstructed from the moment vector {µj,l}N−1j=0 , which can be obtained from the Pascal triangle
TN+l−1(I) of order N + l − 1.
Remark 1. In practice, when reconstructing the pixel intensities of an image I, floating point
errors in the matrix inversion can result in inaccuracies in the reconstructed image. In fact,
the recovered pixel intensities may be complex valued. While the imaginary part of the result
tends to be quite small, it is advantageous to first reformulate the problem to guarantee a real
solution. One way to force the solution to be real is to separate equation (2) into two sets of
equations with real coefficients. More specifically, we can separate the equation system into its
real part and its imaginary part, and combine these two real equation systems into one. After
this, a real solution for the new equation system can be found, for example, by singular value
decomposition (SVD).
Lemma 2. Given the moments matrix τN (I) of a discrete image I and an upper bound on the
number N of pixels, one can reconstruct the pixel location zk and the intensity ρ(zk) for all zk
such that ρ(zk) 6= 0.3
Proof. If the number of pixels in the image I is strictly less than N , we can extend I to an
image with N pixels by adding zero intensity pixels. Without loss of generality, we assume that
ρ(zk) 6= 0 for k = 1, . . . , s and ρ(zk) = 0 for k = s+ 1, . . . , N . Consider the polynomial
P (t) =
s∏
k=1
(t− zk) = ts +
s∑
j=1
cjt
s−j ,
where the coefficients cj are polynomials in the zk’s.
3This result generalizes Proposition 1 in [6], which states that the vertices of a polygon are uniquely determined
by a finite number of moments.
4 M. Boutin and S. Huang
Observe that P (zk) = 0, ∀ k = 1, 2, . . . , s. Therefore, we also have ρ(zk)z̄
l
kP (zk) = 0, for any
l = 0, . . . , s− 1. Summing all these equations over k’s, we get
s∑
k=1
ρ(zk)z̄
l
kP (zk) = 0 =⇒
s∑
k=1
ρ(zk)z̄
l
k
zsk +
s∑
j=1
cjz
s−j
k
= 0
=⇒
s∑
k=1
ρ(zk)z̄
l
kz
s
k +
s∑
j=1
cj
s∑
k=1
ρ(zk)z̄
l
kz
s−j
k = 0
=⇒ µs,l +
s∑
j=1
cjµs−j,l = 0
=⇒
s∑
j=1
cjµs−j,l = −µs,l, l = 0, 1, . . . , s− 1.
We write these last equations in matrix form:
µ0,0 µ1,0 µ2,0 µ3,0 · · · µs−1,0
µ0,1 µ1,1 µ2,1 · · · · · · µs−1,1
µ0,2 µ1,2 · · · · · · · · · µs−1,2
µ0,3 · · · · · · · · · · · · µs−1,3
...
...
µ0,s−1 µ1,s−1 · · · · · · · · · µs−1,s−1
︸ ︷︷ ︸
cs
cs−1
cs−2
...
c1
= −
µs,0
µs,1
µs,2
...
µs,s−1
. (4)
τs(I)
From equation (1) we know that
τs(I) =
1 1 · · · 1
z̄1 z̄2 · · · z̄s
... · · ·
...
z̄s−11 z̄s−12 · · · z̄s−1s
ρ(z1) 0 · · · 0
0 ρ(z2) · · · 0
...
...
. . .
...
0 · · · 0 ρ(zs)
1 z1 z21 · · · zs−11
1 z2 z22 · · · zs−12
...
... · · ·
...
1 zs z2s · · · zs−1s
.
Thus τs(I) is invertible, since the locations zk are pairwise distinct and the pixel intensities ρ(zk)
are nonzero. Hence we can solve the above equation system for (cs, cs−1, . . . , c1) by inverting τs(I)
and multiplying by the vector on the right-hand-side of equation (4).
Since the ck’s determine the polynomial P (t), we can solve for the roots of P (t) = 0, which are
actually {zk}sk=1. By Lemma 1, we can subsequently obtain the pixel intensities {ρ(zk)}sk=1. �
Remark 2. To determine the number of nonzero pixels, we can look at the rank of τN (I). Since
τN (I) = Z†WZ by equation (1) and rank(Z†) = rank(Z) = N , rank(W ) = s, we can conclude
that rank(τN (I)) = s.
Since the Pascal triangle T 2N−2(I) of the image I contains all the information needed to
recover τN (I), we have the following corollary:
Corollary 1 (image reconstruction property). Given the Pascal triangle T 2N−2(I) of a dis-
crete image I, one can reconstruct both the grid point locations {zk}Nk=1 and the corresponding
intensities {ρ(zk)}Nk=1 for all those zk such that ρ(zk) 6= 0.
The Pascal Triangle of a Discrete Image 5
2 Relationship with the Radon transform
The Radon transform fθ(r) is the projection of the image I = {(zk, ρ(zk))}Nk=1 onto the straight
line through the origin with direction vector
(
cos(θ) sin(θ)
)T
, i.e.
fθ(r) =
∑
k∈S
ρ(zk),
where S = {k |xk cos(θ) + yk sin(θ) = r, k = 1, 2, . . . , N}. Since fθ(r) is a periodic function of θ
with period 2π, any of its n-th order moment mn(θ) is also periodic with period 2π. It turns
out that, for any n = 0, 1, 2, . . ., the coefficients of the Fourier series of mn(θ) are given by the
entries of row (n+ 1) of T r(I) with r ≥ n.
Lemma 3. The n-th order moment mn(θ) of the Radon transform fθ(r) is given by the following
linear combination of the (n+ 1)-th row entries of the Pascal triangle T r(I) with r ≥ n:
mn(θ) =
1
2n
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)θ. (5)
Proof. For n = 0, we have
m0(θ) =
N∑
k=1
ρ(zk) =
N∑
k=1
ρ(zk)z
0
k z̄
0
k = µ0,0.
For n > 0, we have
mn(θ) =
∑
r
rnfθ(r) =
N∑
k=1
(
rk(θ)
)n
ρ(zk),
where rk(θ) is the projection of the vector (xk, yk)
T onto the axis with angle θ ∈ (−π, π] with
respect to x-axis. More precisely,
rk(θ) = xk cos θ + yk sin θ =
1
2
(
zke
−iθ + z̄ke
iθ
)
, ∀ k = 1, 2, . . . , N,
and therefore
mn(θ) =
N∑
k=1
(
rk(θ)
)n
ρ(zk) =
N∑
k=1
(
1
2
(
zke
−iθ + z̄ke
iθ
))n
ρ(zk)
=
1
2n
N∑
k=1
(
zke
−iθ + z̄ke
iθ
)n
ρ(zk) =
1
2n
N∑
k=1
(
n∑
l=0
(
n
l
)
zlke
−ilθz̄n−lk ei(n−l)θ
)
ρ(zk)
=
1
2n
n∑
l=0
(
n
l
)( N∑
k=1
zlkz̄
n−l
k ρ(zk)
)
e−ilθei(n−l)θ =
1
2n
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)θ. �
Figs. 1 and 2 summarize the relationship between the Pascal triangle and the Radon transform
of an image when the pixel locations are known and unknown, respectively. Observe that
a smaller number of rows of the Pascal triangle are needed in order to reconstruct the image if
the pixel locations were known.
6 M. Boutin and S. Huang
{(
zk, ρ(zk)
)}N
k=1
fθ(r)
T 2N−2(I)
{
mn(θ)
}2N−2
n=0
Radon transform
nth order
moment
triangle of the
complex moments
Lemma 3
Corollary 1
Figure 1. Relationship between the Pascal triangle and the Radon transform of an image under the
assumption that the pixel locations are unknown a priori.
{
ρ(zk)
}N
k=1
with zk fixed fθ(r)
TN−1(I)
{
mn(θ)
}N−1
n=0
Radon transform
nth order
moment
triangle of the
complex moments
Lemma 3
Lemma 1
Figure 2. Relationship between the Pascal triangle and the Radon transform of an image under the
assumption that the pixel locations are fixed and known a priori.
3 Image reconstruction from samples
Lemma 4. The last row of Tn(I) can be reconstructed from n + 1 generic moment samples
mn(θ1),mn(θ2), . . . ,mn(θn+1).
Proof. We first write equation (5) in matrix form:
mn(θ1)
mn(θ2)
...
mn(θn+1)
=
1
2n
einθ1 · · · ei(n−2l)θ1 · · · e−inθ1
einθ2 · · · ei(n−2l)θ2 · · · e−inθ2
... · · ·
... · · ·
...
einθn+1 · · · ei(n−2l)θn+1 · · · e−inθn+1
µ0,n
...
( nl )µl,n−l
...
µn,0
.
There is a unique solution for
(
µ0,n, . . . , (
n
l )µl,n−l, . . . , µn,0
)
if and only if
det
einθ1 · · · ei(n−2l)θ1 · · · e−inθ1
einθ2 · · · ei(n−2l)θ2 · · · e−inθ2
... · · ·
... · · ·
...
einθn+1 · · · ei(n−2l)θn+1 · · · e−inθn+1
6= 0
⇐⇒ det
e−inθ1 0 0 . . . 0
0 e−inθ2 0 . . . 0
...
...
. . .
...
0 . . . 0 . . . e−inθn+1
ei2nθ1 · · · ei4θ1 ei2θ1 1
ei2nθ2 · · · ei4θ2 ei2θ2 1
... · · ·
...
...
...
ei2nθn+1 · · · ei4θn+1 ei2θn+1 1
6= 0
The Pascal Triangle of a Discrete Image 7
⇐⇒ det
ei2nθ1 · · · ei4θ1 ei2θ1 1
ei2nθ2 · · · ei4θ2 ei2θ2 1
... · · ·
...
...
...
ei2nθn+1 · · · ei4θn+1 ei2θn+1 1
6= 0,
since e−inθj 6= 0, ∀ j = 1, . . . , n+ 1.
Observe that the above determinant is a Vandermonde determinant. It is nonzero if ei2θj 6=
ei2θk for all distinct j, k = 1, . . . , n+ 1. Therefore, if the θj ’s are such that ei2θj 6= ei2θk (thus the
need to pick a generic sample set), we will get a unique solution for
(
µ0,n, . . . , (
n
l )µl,n−l, . . . , µn,0
)
.
Hence we can reconstruct the last row of Tn(I). �
Corollary 2. Given the grid point locations {zk}Nk=1, we can reconstruct the discrete image I =
{(zk, ρ(zk))}Nk=1 from the Radon transform fθ1(r), fθ2(r), . . . , fθN (r) at N fixed generic angles
θ1, . . . , θN .4
Proof. From the given radon transform of the image at different angles, we can calculate the
moments
{
mn(θk) |n = 0, . . . , N − 1, k = 1, . . . , n+ 1
}
. The conclusion followed by combining
Lemmas 1 and 4. �
The diagram of Fig. 3 thus commutes. Note that, one could use a similar argument along
with Corollary 1 to show that (2N − 1) generic observations of {mn(θj), j = 1, . . . , n+ 1}2N−2n=0
would be needed to fully reconstruct the image {(zk, ρ(zk))}Nk=1 with pixel positions zk unknown.
{( )}
ρ(zk) with fixed zk, k = 1, 2, . . . , N fθ1(r), fθ2(r), . . . , fθN (r)
TN−1(I)
{
mn(θ1), mn(θ2), . . . , mn(θn+1)
}N−1
n=0
Radon transform
nth order
moment
triangle of the
complex moments
Lemma 3
Lemma 1
Lemma 4
Corollary 2
Figure 3. Relationship between the Pascal triangle TN−1(I) and the Radon transform.
4 Prolongation of group actions on the moments
and invariantization
Let (G, ·) be a group acting on the complex plane:
· : G× C −→ C,
(g, z) 7−→ g · z, ∀ g ∈ G, z ∈ C.
This induces a group transformation (G, ◦) of the discrete image I = {(zk, ρ(zk))}Nk=1, namely
g ◦ {(zk, ρ(zk))}Nk=1 = {(g · zk, ρ(zk))}Nk=1, ∀ g ∈ G.
4This result generalizes Theorem 5.1 in [4], which states that a quadrature domain can be uniquely recon-
structed by the line integral projections at finite angles.
8 M. Boutin and S. Huang
Then the induced transformation (G, ∗) on moments {µj,l}j,l∈Z≥0 is
g ∗ {µj,l}j,l∈Z≥0 = g ∗
{
N∑
k=1
zjkz̄
l
kρ(zk)
}
j,l∈Z≥0
=
{
N∑
k=1
(g · zk)j(g · zk)lρ(zk)
}
j,l∈Z≥0
.
In other words, the transformed moments are the moments of the transformed image.
Example 1. Consider the action of G = C on C by translation
(z0, z) 7→ z + z0, ∀ z0 ∈ G, ∀ z ∈ C.
Then the induced transformation on the image I = {(zk, ρ(zk))}Nk=1 is
z0 ◦ {(zk, ρ(zk))}Nk=1 = {(zk + z0, ρ(zk))}Nk=1, ∀ z0 ∈ G. (6)
In other words, the image is translated horizontally with distance x0 = Re(z0) and vertically
with y0 = Im(z0). The transformed complex moments are
µ̃j,l =
N∑
k=1
z̃jk
¯̃zlkρ(z̃k) =
N∑
k=1
(zk + z0)
j(z̄k + z̄0)
lρ(zk)
=
N∑
k=1
(
j∑
s=0
(
j
s
)
zskz
j−s
0
)(
l∑
t=0
(
l
t
)
z̄tkz̄
l−t
0
)
ρ(zk)
=
j∑
s=0
l∑
t=0
(
N∑
k=1
zskz̄
t
kρ(zk)
)(
j
s
)(
l
t
)
zj−s0 z̄l−t0
=
j∑
s=0
l∑
t=0
µs,t
(
j
s
)(
l
t
)
zj−s0 z̄l−t0 , ∀ j, l ∈ Z≥0. (7)
Written in matrix form, the transformation of the moment matrix τN (I) is τN (Ĩ) = A†τN (I)A,
where A = (aj,l)N×N is an upper-triangular matrix with aj,l =
(
l−1
j−1
)
zl−j0 , and A† is the
conjugate transpose of A.
Having obtained an explicit formula for the action of G on the moments, we follow Fels and
Olver’s moving frame method [1, 2, 7] to obtain a set of invariant functions of the moments.
More specifically, we consider the cross-section defined by µ̃1,0 = 0. The group transforma-
tion that maps τN (I) to the cross-section is the moving frame z0 = −µ1,0
µ0,0
. By applying the
moving frame to the moment matrix, we obtain the matrix τ̃N (I) = A†0τN (I)A0, where A0 =((
l−1
j−1
)
(−µ1,0
µ0,0
)l−j
)
N×N
. By equivariance of the moving frame, all the entries of τ̃N (I) are invari-
ant under translation. One can check that theses entries µ̃j,l are actually the centralized moments
µ̃j,l =
N∑
k=1
(
zk −
µ1,0
µ0,0
)j (
z̄k −
µ̄1,0
µ0,0
)l
ρ(zk), j, l ∈ Z≥0. (8)
By normalizing (i.e. applying the moving frame transformation to) the coordinates of T r(I),
we obtain the translation invariant Pascal triangle T rtrans(I) for a discrete image I:
µ̃0,0
µ̃0,1 µ̃1,0
µ̃0,2 2µ̃1,1 µ̃2,0
µ̃0,3 3µ̃1,2 3µ̃2,1 µ̃3,0
µ̃0,4 4µ̃1,3 6µ̃2,2 4µ̃3,1 µ̃4,0
...
µ̃0,r ( r1 ) µ̃1,r−1 · · · ( rl ) µ̃l,r−l · · · ( r
r−1 ) µ̃r−1,1 µ̃r,0
The Pascal Triangle of a Discrete Image 9
Observe that the corresponding n-th order central moment m̃n(θ) of the image,
m̃n(θ) =
N∑
k=1
(
rk(θ)− r0(θ)
)n
ρ(xk, yk),
where r0(θ) = x0 cos θ+ y0 sin θ is the projection of the centroid, is invariant under translations.
Lemma 5 (orbit separation property of T 2N−2
trans (I)). Let I1, I2 be two discrete gray scale images
with the same number N of pixels. There exists a translation g ∈ C such that g ◦ I1 = I2, where
◦ is defined as in (6) ⇐⇒ T rtrans(I1) = T rtrans(I2) for r ≥ 2N − 2.
Proof. ⇒ If ∃ g ∈ G such that g ◦ I1 = I2, we have z
(2)
k = z
(1)
k + z0 and ρ2
(
z
(2)
k
)
= ρ1
(
z
(1)
k
)
, for
some z0 ∈ C, k = 1, . . . , N . From equation (7) we know that
µ
(2)
0,0 = µ
(1)
0,0, µ
(2)
1,0 = µ
(1)
0,0z0 + µ
(1)
1,0, hence
µ
(2)
1,0
µ
(2)
0,0
=
µ
(1)
1,0
µ
(1)
0,0
+ z0.
Then applying equation (8), we can get for any j, l ∈ Z≥0
µ̃
(1)
j,l =
N∑
k=1
(
z
(1)
k −
µ
(1)
1,0
µ
(1)
0,0
)j (
z̄
(1)
k −
µ̄
(1)
1,0
µ
(1)
0,0
)l
ρ1
(
z
(1)
k
)
=
N∑
k=1
(z
(2)
k −
µ
(1)
1,0
µ
(1)
0,0
− z0)j
(
z̄
(2)
k −
µ̄
(1)
1,0
µ
(1)
0,0
− z̄0
)l
ρ2
(
z
(2)
k
)
= µ̃
(2)
j,l .
Therefore T rtrans(I1) = T rtrans(I2) for any r ∈ Z≥0.
⇐ If T rtrans(I1) = T rtrans(I2) for r ≥ 2N −2, from Corollary 1, we conclude that Itrans1 = Itrans2 ,
i.e.
{(
z
(1)
k,trans, ρ1
(
z
(1)
k,trans
))}N
k=1
=
{(
z
(2)
k,trans, ρ2
(
z
(2)
k,trans
))}N
k=1
.
Hence ∃ z0, z′0 ∈ C s.t. z
(1)
k,trans = z
(1)
k + z0, z
(2)
k,trans = z
(2)
k + z′0 with ρ1
(
z
(1)
k,trans
)
= ρ1
(
z
(1)
k
)
and
ρ2
(
z
(2)
k,trans
)
= ρ2
(
z
(2)
k
)
for any k = 1, 2, . . . , N . Without loss of generality, we assume that
z
(1)
k,trans = z
(2)
k,trans and ρ1
(
z
(1)
k,trans
)
= ρ2
(
z
(2)
k,trans
)
. Therefore ∃ z0 − z′0 ∈ C = G satisfying
z
(1)
k + z0 − z′0 = z
(2)
k , ρ1
(
z
(1)
k + (z0 − z′0)
)
= ρ1
(
z
(1)
k
)
= ρ2
(
z
(2)
k
)
,
i.e. ∃ g = z′0 − z0 ∈ G = C such that g ◦ I1 = I2. �
Remark 3. Without loss of generality, we can assume that the two images have the same
number of pixels by simply adding zero valued pixels to the smaller image.
Example 2. Consider the action of G = R+ on C by scaling
(λ, z) 7→ λz, ∀λ ∈ G, ∀ z ∈ C.
Then the induced transformation on the image I = {(zk, ρ(zk))}Nk=1 is
λ ◦ {(zk, ρ(zk))}Nk=1 = {(λzk, ρ(zk))}Nk=1, ∀λ ∈ G. (9)
10 M. Boutin and S. Huang
In other words, the image is scaled by a factor λ both horizontally and vertically. Then the
transformed complex moments are
µ̂j,l =
N∑
k=1
ẑjk
¯̂zlkρ(ẑk) =
N∑
k=1
(λzk)
j(λz̄k)
lρ(zk)
=
N∑
k=1
λj+lzjkz̄
l
kρ(zk) = λj+l
N∑
k=1
zjkz̄
l
kρ(zk) = µj,lλ
j+l, ∀ j, l ∈ Z≥0.
Written in matrix form, the moment matrix for the new image Î after scaling is
τN (Î) =
1 0 0 · · · 0
0 λ 0 · · · 0
0 0 λ2 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 λN−1
τN (I)
1 0 0 · · · 0
0 λ 0 · · · 0
0 0 λ2 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 λN−1
.
Again, we use the moving frame method of Fels and Olver to obtain a set of invariant functions
of the moments. Notice that µ̂1,1 =
N∑
k=1
ẑk ¯̂zkρ(ẑk) =
N∑
k=1
(
x̂2k + ŷ2k
)
ρ(ẑk) 6= 0 unless all ρ(zk) are
zero. We consider the cross-section defined by µ̂1,1 = 1. The group transformation that maps
τN (I) to the cross-section is the moving frame λ = (µ1,1)
− 1
2 . By applying the moving frame to
the moment matrix, we obtain the matrix
τ̂N (I) =
1 0 · · · 0
0 (µ1,1)
− 1
2 · · · 0
...
...
. . .
...
0 · · · 0 (µ1,1)
−N−1
2
τN (I)
1 0 · · · 0
0 (µ1,1)
− 1
2 · · · 0
...
...
. . .
...
0 · · · 0 (µ1,1)
−N−1
2
.
By equivariance of the moving frame, all the entries of τ̂N (I) are invariant under scaling.
By normalizing the coordinates of T r(I), we obtain the scaling invariant Pascal triangle
T rscale(I) for a discrete image I:
µ0,0
µ0,1√
µ1,1
µ1,0√
µ1,1
µ0,2
µ1,1
2
µ2,0
µ1,1
µ0,3
µ
3/2
1,1
3
µ1,2
µ
3/2
1,1
3
µ2,1
µ
3/2
1,1
µ3,0
µ
3/2
1,1
µ0,4
µ21,1
4
µ1,3
µ21,1
6
µ2,2
µ21,1
4
µ3,1
µ21,1
µ4,0
µ21,1
...
µ0,r
µ
r/2
1,1
( r1 )
µ1,r−1
µ
r/2
1,1
· · · ( rl )
µl,r−l
µ
r/2
1,1
· · · ( r
r−1 )
µr−1,1
µ
r/2
1,1
µr,0
µ
r/2
1,1
Observe that the corresponding n-th order normalized moment m̂n(θ) = mn(θ)/µ
n
2
1,1 is in-
variant under scaling.
Lemma 6 (orbit separation property of T 2N−2
scale (I)). Let I1, I2 be two discrete gray scale images
with the same number N of pixels. There exists a scaling g ∈ R+ such that g ◦ I1 = I2, where ◦
is defined as in (9) ⇐⇒ T rscale(I1) = T rscale(I2) for r ≥ 2N − 2.
The Pascal Triangle of a Discrete Image 11
Proof. ⇒ If ∃ g ∈ G such that g◦I1 = I2, we have z
(2)
k = λz
(1)
k and ρ1
(
z
(1)
k
)
= ρ2
(
z
(2)
k
)
for some
λ ∈ R+, k = 1, . . . , N . Since for I1 and I2, the corresponding scaling invariant moments are
µ̂
(1)
j,l =
µ
(1)
j,l
(
µ
(1)
1,1
) j+l
2
=
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
(
N∑
k=1
z
(1)
k z̄
(1)
k ρ1
(
z
(1)
k
))
j+l
2
,
µ̂
(2)
j,l =
µ
(2)
j,l
(
µ
(2)
1,1
) j+l
2
=
N∑
k=1
(
z
(2)
k
)j(
z̄
(2)
k
)l
ρ2
(
z
(2)
k
)
(
N∑
k=1
z
(2)
k z̄
(2)
k ρ2
(
z
(2)
k
))
j+l
2
=
N∑
k=1
(
λz
(1)
k
)j(
λz̄
(1)
k
)l
ρ1
(
z
(1)
k
)
(
N∑
k=1
(
λz
(1)
k
)(
λz̄
(1)
k
)
ρ1
(
z
(1)
k
))
j+l
2
=
N∑
k=1
λj+l
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
(
N∑
k=1
λ2z
(1)
k z̄
(1)
k ρ1
(
z
(1)
k
))
j+l
2
=
λj+l
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
λj+l
(
N∑
k=1
z
(1)
k z̄
(1)
k ρ1
(
z
(1)
k
))
j+l
2
=
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
(
N∑
k=1
z
(1)
k z̄
(1)
k ρ1
(
z
(1)
k
))
j+l
2
= µ̂
(1)
j,l .
Therefore T rscale(I1) = T rscale(I2) for any r ∈ Z≥0.
⇐ If T rscale(I1) = T rscale(I2) for r ≥ 2N − 2, from Corollary 1, we conclude that Iscale1 = Iscale2 ,
i.e.
{(
z
(1)
k,scale, ρ1
(
z
(1)
k,scale
))}N
k=1
=
{(
z
(2)
k,scale, ρ2
(
z
(2)
k,scale
))}N
k=1
.
Hence ∃λ1, λ2 ∈ R+ s.t. z
(1)
k,scale = λ1z
(1)
k , z
(2)
k,scale = λ2z
(2)
k with ρ1
(
z
(1)
k,scale
)
= ρ1
(
z
(1)
k
)
and
ρ2
(
z
(2)
k,scale
)
= ρ2
(
z
(2)
k
)
for any k = 1, 2, . . . , N . After relabeling, we have z
(1)
k,scale = z
(2)
k,scale and
ρ1
(
z
(1)
k,scale
)
= ρ2
(
z
(2)
k,scale
)
. Then ∃ λ1λ2 ∈ R+ = G satisfying
z
(1)
k
λ1
λ2
= z
(2)
k , ρ1
(
z
(1)
k
λ2
λ1
)
= ρ1
(
z
(1)
k
)
= ρ2
(
z
(2)
k
)
,
i.e. ∃ g = λ2
λ1
∈ G = R+ such that g ◦ I1 = I2. �
More generally, consider the action of group G of diagonal matrices on R2
+ by scaling
((
λ1 0
0 λ2
)
,
(
x
y
))
7→
(
λ1 0
0 λ2
)(
x
y
)
=
(
λ1x
λ2y
)
,
∀
(
λ1 0
0 λ2
)
∈ G, ∀
(
x
y
)
∈ R2.
Then the induced transformation on the image I = {(zk, ρ(zk))}Nk=1 is
(
λ1 0
0 λ2
)
◦
{(
zk, ρ(zk)
)}N
k=1
=
{(
λ1xk + iλ2yk, ρ(zk)
)}N
k=1
,
∀
(
λ1 0
0 λ2
)
∈ G, zk = xk + iyk.
In other words, the image is scaled by a factor λ1 horizontally and scaled by λ2 vertically.
12 M. Boutin and S. Huang
Notice that after the transformation, the pixel coordinates become
ẑk = λ1xk + iλ2yk = λ1
zk + z̄k
2
+ iλ2
zk − z̄k
2i
=
λ1 + λ2
2
zk +
λ1 − λ2
2
z̄k,
¯̂zk = λ1xk − iλ2yk = λ1
zk + z̄k
2
− iλ2
zk − z̄k
2i
=
λ1 − λ2
2
zk +
λ1 + λ2
2
z̄k.
Then we have the transformed complex moments
µ̂j,l =
N∑
k=1
ẑjk
¯̂zlkρ(ẑk) =
N∑
k=1
(
λ1 + λ2
2
zk +
λ1 − λ2
2
z̄k
)j (λ1 − λ2
2
zk +
λ1 + λ2
2
z̄k
)l
ρ(zk)
=
N∑
k=1
ρ(zk)
[
j∑
s=0
(
j
s
)(
λ1 + λ2
2
)s
zsk
(
λ1 − λ2
2
)j−s
z̄j−sk
]
×
[
l∑
t=0
(
l
t
)(
λ1 − λ2
2
)t
ztk
(
λ1 + λ2
2
)l−t
z̄l−tk
]
=
N∑
k=1
ρ(zk)
[
j∑
s=0
l∑
t=0
(
j
s
)(
l
t
)(
λ1 + λ2
2
)l−t+s(λ1 − λ2
2
)j−s+t
zs+tk z̄j+l−s−tk
]
=
j∑
s=0
l∑
t=0
(
j
s
)(
l
t
)(
λ1 + λ2
2
)l−t+s(λ1 − λ2
2
)j−s+t [ N∑
k=1
ρ(zk)z
s+t
k z̄j+l−s−tk
]
=
1
2j+l
j∑
s=0
l∑
t=0
(
j
s
)(
l
t
)
(λ1 + λ2)
l−t+s(λ1 − λ2)j−s+tµs+t,j+l−s−t, ∀ j, l ∈ Z≥0,
which is a linear combination of the last row of the Pascal triangle T j+l(I).
Example 3. Consider the action of G = {z ∈ C||z| = 1} on C by rotation
(
eiθ0 , z
)
7→ zeiθ0 , ∀ eiθ0 ∈ G, ∀ z ∈ C.
Then the induced transformation on the image I = {(zk, ρ(zk))}Nk=1 is
eiθ0 ◦ {(zk, ρ(zk))}Nk=1 =
{(
eiθ0zk, ρ(zk)
)}N
k=1
, ∀ eiθ0 ∈ G. (10)
In other words, the image is rotated counterclockwise with an angle θ0. The transformed complex
moments are
µ′j,l =
N∑
k=1
z′jkz̄′
l
kρ(z′k) =
N∑
k=1
(
zke
iθ0
)j(
z̄ke
−iθ0)lρ(zk) =
N∑
k=1
ei(j−l)θ0zjkz̄
l
kρ(zk)
= ei(j−l)θ0
N∑
k=1
zjkz̄
l
kρ(zk) = µj,le
i(j−l)θ0 , ∀ j, l ∈ Z≥0.
Written in matrix form, the moment matrix for the new image I ′ after rotation is
τN (I ′) =
1 0 0 · · · 0
0 e−iθ0 0 · · · 0
0 0 e−i2θ0 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 e−i(N−1)θ0
τN (I)
1 0 0 · · · 0
0 eiθ0 0 · · · 0
0 0 ei2θ0 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 ei(N−1)θ0
.
The Pascal Triangle of a Discrete Image 13
Now we will use the moving frame method of Fels and Olver to obtain a set of invariant functions
of the moments. If µ0,2 6= 0, we normalize the imaginary part of µ′0,2 to zero by specifying the
rotation angle θ0. Since µ′0,2 = µ0,2e
−i2θ0 , looking at ~µ0,2 as a vector in R2 representing the
complex number µ0,2, we set
2θ0 = ^(~µ0,2, ~e1) + 2kπ, k ∈ Z.
Here ^(~x, ~y) = tan−1
(y2
y1
)
− tan−1
(
x2
x1
)
∈ (−π, π] denotes the angle from ~x to ~y, ~e1 = (1, 0)T is
one of the standard basis of R2. The real part of µ′0,2 then reduces to its magnitude |µ0,2|.
Since θ0 ∈ (−π, π], 2θ0 ∈ (−2π, 2π]. To uniquely determine the value of θ0, we consider
µ′1,2 = µ1,2e
−iθ0 . We choose θ0 such that Re(µ′1,2) ≥ 0, which leads to the moving frame
formulae
θ0 =
1
2^(~µ0,2, ~e1) if ^(~µ1,2, ~e1)− 1
2^(~µ0,2, ~e1) ∈
[
−π
2 ,
π
2
]
,
1
2^(~µ0,2, ~e1) + π if ^(~µ1,2, ~e1)− 1
2^(~µ0,2, ~e1) ∈
(
π
2 ,
3π
2
]
,
1
2^(~µ0,2, ~e1)− π if ^(~µ1,2, ~e1)− 1
2^(~µ0,2, ~e1) ∈
[
−3π
2 ,−
π
2
)
.
(11)
By applying the moving frame to the moment matrix, we obtain the matrix
τ ′N (I) =
1 0 0 · · · 0
0 e−iθ0 0 · · · 0
0 0 e−i2θ0 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 e−i(N−1)θ0
τN (I)
1 0 0 · · · 0
0 eiθ0 0 · · · 0
0 0 ei2θ0 · · · 0
...
...
...
. . .
...
0 · · · · · · 0 ei(N−1)θ0
,
with θ0 satisfying (11). By equivariance of the moving frame, all the entries of τ ′N (I) are invariant
under rotation.
By normalizing the coordinates of T r(I), we obtain the rotational invariant Pascal triangle
T rrotate(I) for a discrete image I:
µ0,0
µ0,1
eiθ0
µ1,0
e−iθ0
|µ0,2| 2µ1,1 |µ2,0|
µ0,3
ei3θ0
3
µ1,2
eiθ0
3
µ2,1
e−iθ0
µ3,0
e−i3θ0µ0,4
ei4θ0
4
µ1,3
ei2θ0
µ2,2 4
µ3,1
e−i2θ0
µ4,0
e−i4θ0
...
µ0,r
eirθ0
· · · ( rl )
µl,r−l
ei(r−2l)θ0
· · · µr,0
e−irθ0
Observe that the corresponding n-th order moment m′n(θ) = mn(θ − θ0), with θ0 defined as
in (11), is invariant under rotations.
Lemma 7 (orbit separation property of T 2N−2
rotate (I) ). Let I1, I2 be two discrete gray scale images
with the same number N of pixels. There exists a rotation g ∈ {z ∈ C||z| = 1} such that
g ◦ I1 = I2, where ◦ is defined as in (10) ⇐⇒ T rrotate(I1) = T rrotate(I2) for r ≥ 2N − 2.
Proof. ⇒ If ∃ g ∈ G such that g ◦ I1 = I2, we have z
(2)
k = z
(1)
k eiθ0 and ρ1(z
(1)
k ) = ρ2(z
(2)
k ), for
some eiθ0 ∈ {z ∈ C | |z| = 1}, k = 1, . . . , N . For I1 and I2, the corresponding scaling invariant
moments are
µ̂
(1)
j,l = µ
(1)
j,l e
−i(l−j)θ1 =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ1 ,
14 M. Boutin and S. Huang
µ̂
(2)
j,l = µ
(2)
j,l e
−i(l−j)θ2 =
N∑
k=1
(
z
(2)
k
)j(
z̄
(2)
k
)l
ρ2
(
z
(2)
k
)
ei(j−l)θ2
=
N∑
k=1
(
z
(1)
k eiθ0
)j(
z̄
(1)
k e−iθ0
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ2 =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)(θ0+θ2).
Since µ
(2)
0,2 = µ
(1)
0,2e
−i2θ0 , µ
(2)
1,2 = µ
(1)
1,2e
−iθ0 , we have
^
(
~µ
(2)
0,2, ~e1
)
= ^
(
~µ
(1)
0,2, ~e1
)
− 2θ0 + 2k1π,
^
(
~µ
(2)
1,2, ~e1
)
= ^
(
~µ
(1)
1,2, ~e1
)
− θ0 + 2k2π, k1, k2 ∈ Z. (12)
Notice that ^
(
~µ
(l)
0,2, ~e1
)
, ^
(
~µ
(l)
1,2, ~e1
)
, θ0 ∈ (−π, π], for l = 1, 2. Hence k1, k2 = 0,±1. To decide θ1
and θ2, we consider
^
(
~µ
(2)
1,2, ~e1
)
− 1
2
^
(
~µ
(2)
0,2, ~e1
)
= ^
(
~µ
(1)
1,2, ~e1
)
− 1
2
^
(
~µ
(1)
0,2, ~e1
)
+ (2k2 − k1)π (13)
by using (12).
If ^
(
~µ
(2)
1,2, ~e1
)
− 1
2^
(
~µ
(2)
0,2, ~e1
)
∈
[
−π
2 ,
π
2
]
, from (11) we know that θ2 = 1
2^
(
~µ
(2)
0,2, ~e1
)
. Since
^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−3π
2 ,
3π
2
]
, then 2k2 − k1 is either 0 or ±1 in (13). If k1 = 0, k2 = 0,
there is ^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−π
2 ,
π
2
]
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
. Then from (12) we have
θ2 = θ1 − θ0. Thus µ̂
(2)
j,l =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ1 = µ̂
(1)
j,l . If k1 = 1, k2 = 0, there
is ^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
(
π
2 ,
3π
2
]
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
+ π. Then from (12) we still
have θ2 = θ1 − θ0. Thus µ̂
(2)
j,l = µ̂
(1)
j,l . If k1 = 1, k2 = 1, there is ^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−3π
2 ,−
π
2
)
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
− π. Then from (12) we have θ2 = θ1 − θ0 + 2π. Thus
µ̂
(2)
j,l =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ1 = µ̂
(1)
j,l .
If ^
(
~µ
(2)
1,2, ~e1
)
− 1
2^
(
~µ
(2)
0,2, ~e1
)
∈
(
π
2 ,
3π
2
]
, from (11) we know that θ2 = 1
2^
(
~µ
(2)
0,2, ~e1
)
+ π. Since
^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−3π
2 ,
3π
2
]
, then 2k2 − k1 = 0, 1, 2 in (13). If k1 = 1, k2 = 1,
there is ^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−π
2 ,
π
2
]
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
. Then from (12) we
have θ2 − π = θ1 − θ0 + π. Thus µ̂
(2)
j,l =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ1 = µ̂
(1)
j,l . If k1 = 0,
k2 = 0, there is ^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
(
π
2 ,
3π
2
]
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
+ π. Then
from (12) we have θ2 − π = θ1 − θ0 − π. Thus µ̂
(2)
j,l = µ̂
(1)
j,l . If k1 = 0, k2 = 1, there is
^
(
~µ
(1)
1,2, ~e1
)
− 1
2^
(
~µ
(1)
0,2, ~e1
)
∈
[
−3π
2 ,−
π
2
)
. Hence θ1 = 1
2^
(
~µ
(1)
0,2, ~e1
)
− π. Then from (12) we have
θ2 − π = θ1 − θ0 + π. Thus µ̂
(2)
j,l =
N∑
k=1
(
z
(1)
k
)j(
z̄
(1)
k
)l
ρ1
(
z
(1)
k
)
ei(j−l)θ1 = µ̂
(1)
j,l .
If ^
(
~µ
(2)
1,2, ~e1
)
− 1
2^
(
~µ
(2)
0,2, ~e1
)
∈
[
−3π
2 ,−
π
2
)
, through the similar discussion, we can still conclude
that µ̂
(2)
j,l = µ̂
(1)
j,l . Therefore T rscale(I1) = T rscale(I2) for any r ∈ Z≥0.
⇐ If T rrotate(I1) = T rrotate(I2) for r ≥ 2N − 2, from Corollary 1, we conclude that Irotate1 =
Irotate2 , i.e.
{(
z
(1)
k,rotate, ρ1
(
z
(1)
k,rotate
))}N
k=1
=
{(
z
(2)
k,rotate, ρ2
(
z
(2)
k,rotate
))}N
k=1
.
Hence ∃ eiθ1 , eiθ2 ∈ {z ∈ C | |z| = 1} s.t. z
(1)
k,rotate = z
(1)
k eiθ1 , z
(2)
k,rotate = z
(2)
k eiθ2 with ρ1
(
z
(1)
k,rotate
)
=
ρ1
(
z
(1)
k
)
and ρ2
(
z
(2)
k,rotate
)
= ρ2
(
z
(2)
k
)
for any k = 1, 2, . . . , N . Without loss of generality, we
The Pascal Triangle of a Discrete Image 15
assume z
(1)
k,rotate = z
(2)
k,rotate and ρ1
(
z
(1)
k,rotate
)
= ρ2
(
z
(2)
k,rotate
)
. Then ∃ ei(θ1−θ2) ∈ {z ∈ C | |z| = 1} =
G satisfying
z
(1)
k ei(θ1−θ2) = z
(2)
k , ρ1
(
z
(1)
k ei(θ1−θ2)
)
= ρ1
(
z
(1)
k
)
= ρ2
(
z
(2)
k
)
,
i.e. ∃ g = ei(θ1−θ2) ∈ G = {z ∈ C | |z| = 1} such that g ◦ I1 = I2. �
In conclusion, we have the translation, scaling and rotation invariant Pascal triangle T rint(I):
µ̃0,0
µ̃0,1e−iθ0√
µ̃1,1
µ̃1,0eiθ0√
µ̃1,1
|µ̃0,2|
µ̃1,1
2
|µ̃2,0|
µ̃1,1
µ̃0,3e−i3θ0
µ̃
3/2
1,1
3
µ̃1,2e−iθ0
µ̃
3/2
1,1
3
µ̃2,1eiθ0
µ̃
3/2
1,1
µ̃3,0ei3θ0
µ̃
3/2
1,1
...
µ̃0,re−irθ0
µ̃
r/2
1,1
· · · ( rl )µ̃l,r−l
µ̃
r/2
1,1 e
i(r−2l)θ0
· · · µ̃r,0eirθ0
µ̃
r/2
1,1
5 Geometric interpretation of the moments
5.1 Shape elongation
Intuitively, the elongation of a shape is described by the relationship between its length and
its width. It is thus a property that is invariant under translation, scaling and rotation of the
image. To characterize the shape elongation, we therefore consider the invariantization ˆ̃m′2(θ) of
the second order moment m2(θ) with respect to translation, scaling and rotation. By combining
the results of Examples 1, 2 and 3, we have
ˆ̃m′2(θ) =
1
4
(
|µ̃0,2|
µ̃1,1
ei2θ + 2 +
|µ̃2,0|
µ̃1,1
e−i2θ
)
=
1
4
(
|µ̃0,2|
µ̃1,1
(
cos(2θ) + i sin(2θ)
)
+ 2 +
|µ̃2,0|
µ̃1,1
(
cos(2θ)− i sin(2θ)
))
=
1
4
(
2
|µ̃0,2|
µ̃1,1
cos(2θ) + 2
)
=
1
2
(
|µ̃0,2|
µ̃1,1
cos(2θ) + 1
)
, (14)
where
µ̃1,1 =
N∑
k=1
(zk − z0)(z̄k − z̄0)ρ(zk) =
N∑
k=1
(
(xk − x0)2 + (yk − y0)2
)
ρ(zk) > 0.
Recall that when making the moments scaling invariant, we normalized ˆ̃µ1,1 to 1 by dividing
each µ̃j,l by the corresponding power of
√
µ̃1,1. Hence
√
µ̃1,1 represents the scale of the image.
Equation (14) indicates that the quantity
|µ̃0,2|
µ̃1,1
prescribes the relationship between the maxi-
mum and the minimum values of the standard deviation of the random transform. It thus gives
us a quantification of the elongation of the shape illustrated by the image5.
Lemma 8. If not all ρ(zk) are zero, then 0 ≤ |µ̃0,2|µ̃1,1
≤ 1.
5A.R. Rostampour et al. [8] previously introduced the n04
n2
02
as a measure of elongation of the projections of
an image. We observe that our measure of elongation has a lower order, and that it can be obtained without
normalizing the angle of the image.
16 M. Boutin and S. Huang
Proof. By definition, |µ̃0,2| ≥ 0 and µ̃1,1 > 0, hence
|µ̃0,2|
µ̃1,1
≥ 0. If
|µ̃0,2|
µ̃1,1
> 1, since ˆ̃m′2(θ) =
1
2
( |µ̃0,2|
µ̃1,1
cos(2θ) + 1
)
, and ˆ̃m′2(θ) ≥ 0 by definition, if we choose θ = π
2 , then
|µ̃0,2|
µ̃1,1
cos(2θ) + 1 < 0,
which is a contradiction. Therefore
|µ̃0,2|
µ̃1,1
≤ 1. �
The case
|µ̃0,2|
µ̃1,1
= 1 corresponds to the most extreme elongation, namely the straight lines.
Lemma 9. The pixel coordinates zk lie on a single straight line if and only if
|µ̃0,2|
µ̃1,1
= 1.
Proof. ⇒ Suppose we have a straight line. As the line is put vertically, the projection of the
line is a dot. Hence the second moment of the Radon transform is zero at that angle θ∗, i.e.
ˆ̃m′2(θ
∗) =
1
2
(
|µ̃0,2|
µ̃1,1
cos(2θ∗) + 1
)
= 0. (15)
Since −1 ≤ cos(2θ∗) ≤ 1 and from Lemma 8 we know that 0 ≤ |µ̃0,2|µ̃1,1
≤ 1 for any image, we can
conclude that (15) is true only when
|µ̃0,2|
µ̃1,1
= 1 and cos(2θ∗) = −1. Hence
|µ̃0,2|
µ̃1,1
= 1 is true.
⇐ Now suppose
|µ̃0,2|
µ̃1,1
= 1. Combine the results in Examples 1, 2 and 3, we conclude that
ˆ̃m′2(θ) = m̃2(θ − θ0)/µ̃1,1 =
1
2
(
|µ̃0,2|
µ̃1,1
cos(2θ) + 1
)
, ∀ θ ∈
(
−π
2
,
π
2
]
,
where θ0 satisfies (11). Since ˆ̃m′n(π2 ) = 0, then there is θ̃ = π
2 − θ0 such that at this angle the
centralized second order moment m̃2(θ̃) of the image is zero.
Let the Radon transform fθ̃(r) at angle θ̃ be a discrete function. Without loss of generality,
we assume that
N∑
k=1
fθ̃(rk(θ)) = 1 and fθ̃(rk(θ)) ≥ 0. Since
m̃2(θ̃) =
N∑
k=1
(
rk(θ̃)− r0(θ̃)
)2
fθ̃(rk(θ)) = 0,
where r0(θ̃) is the projection of the centroid of the image, we observe that fθ̃(r) = δ(r− r0(θ̃)).
Then we conclude that the image lies on a line through r0(θ̃) with angle θ̃+ π
2 to the x-axis. �
The other extreme case is when
|µ̃0,2|
µ̃1,1
= 0. This corresponds to ˆ̃m′2(θ) = const. So the
standard deviation of the projection is the same for all directions. There are many ways for this
to happen. One interesting case is the discrete analogue of rotation symmetries.
Definition 2. An object is said to have Ñ -fold rotation symmetry (Ñ -FRS) if it is unchanged
by a rotation around its centroid by 2kπ
Ñ
, for all k = 1, . . . , Ñ .
Lemma 10. If the image I has an Ñ -FRS with Ñ > 2, then
|µ̃0,2|
µ̃1,1
= 0.
Proof. Suppose the data have Ñ -FRS. For a certain point with distance rk, k = 1, 2, . . . ,M ,
from the centroid, angle θk with x-axis and weight ρ(zk), there are Ñk − 1 more points with
the same distance from the centroid and the same weight ρ(zk) but having angle θk + 2jπ
Ñk
,
j = 1, . . . , Ñk − 1 with x-axis respectively. Then the moment µ̃0,2 can be written as
µ̃0,2 =
M∑
k=1
ρ(zk)
Ñk−1∑
j=0
(
rk cos
(
θk +
2jπ
Ñk
)
− irk sin
(
θk +
2jπ
Ñk
))2
The Pascal Triangle of a Discrete Image 17
=
M∑
k=1
ρ(zk)
Ñk−1∑
j=0
r2k cos
(
2θk +
4jπ
Ñk
)
− i
M∑
k=1
ρ(zk)
Ñk−1∑
j=0
r2k sin
(
2θk +
4jπ
Ñk
)
=
M∑
k=1
ρ(zk)
Ñk−1∑
j=0
r2k cos(2θk) cos
(
4jπ
Ñk
)
− r2k sin(2θk) sin
(
4jπ
Ñk
)
− i
M∑
k=1
ρ(zk)
Ñk−1∑
j=0
r2k sin(2θk) cos
(
4jπ
Ñk
)
+ r2k cos(2θk) sin
(
4jπ
Ñk
)
=
M∑
k=1
ρ(zk)
r2k cos(2θk)
( Ñk−1∑
j=0
cos
(
4jπ
Ñk
))
− r2k sin(2θk)
Ñk−1∑
j=0
sin
(
4jπ
Ñk
)
− i
M∑
k=1
ρ(zk)
r2k sin(2θk)
Ñk−1∑
j=0
cos
(
4jπ
Ñk
)
+ r2k cos(2θk)
Ñk−1∑
j=0
sin
(
4jπ
Ñk
)
.
It can be shown that
Ñk−1∑
j=0
cos
(
4jπ
Ñk
)
= 0,
Ñk−1∑
j=0
sin
(
4jπ
Ñk
)
= 0, ∀ Ñk > 2.
Then µ̃0,2 = 0, hence
|µ̃0,2|
µ̃1,1
= 0. �
One can give a statistical interpretation of our proposed shape elongation measure
|µ̃0,2|
µ̃1,1
. In-
deed after renormalizing the total ink µ0,0 =
N∑
k=1
ρ(zk) to one, one can view the pixel intensities as
describing a discrete probability distribution. The standard deviation matrix of that distribution
is then determined by the third row of the Pascal triangle, as stated in the following lemma:
Lemma 11. Consider the discrete image I as a bivariate distribution with the joint probability
mass function P (X = xk − x0, Y = yk − y0) = ρ(zk)
µ0,0
, k = 1, 2, . . . , N . The covariance matrix Σ
of that distribution is given by
Σ =
µ̃1,1 + Re(µ̃0,2)
2µ0,0
− Im(µ̃0,2)
2µ0,0
− Im(µ̃0,2)
2µ0,0
µ̃1,1 − Re(µ̃0,2)
2µ0,0
.
Proof. Observe that
µ̃1,1
µ0,0
=
N∑
k=1
(zk − z0)(z̄k − z̄0)
ρ(zk)
µ0,0
=
N∑
k=1
(
(xk − x0)2 + (yk − y0)2
)ρ(zk)
µ0,0
,
µ̃0,2
µ0,0
=
N∑
k=1
(z̄k − z̄0)2
ρ(zk)
µ0,0
=
N∑
k=1
(
(xk − x0)2 − (yk − y0)2
)ρ(zk)
µ0,0
− 2i
N∑
k=1
(xk − x0)(yk − y0)
ρ(zk)
µ0,0
.
18 M. Boutin and S. Huang
Write Σ =
(
σ2x ρXY σxσy
ρXY σxσy σ2y
)
. Since the random variables X, Y both have zero mean, we
have
σ2x =
N∑
k=1
(xk − x0)2
ρ(zk)
µ0,0
, σ2y =
N∑
k=1
(yk − y0)2
ρ(zk)
µ0,0
,
ρXY σxσy =
N∑
k=1
(xk − x0)(yk − y0)
ρ(zk)
µ0,0
.
Then one can check that
µ̃1,1
2µ0,0
+
Re(µ̃0,2)
2µ0,0
= σ2x, − Im(µ̃0,2)
2µ0,0
= ρXY σxσy,
µ̃1,1
2µ0,0
− Re(µ̃0,2)
2µ0,0
= σ2y . �
Recall that, in order to obtain the standard deviation m2(θ) of the projection of a bivariate
distribution onto the line with direction vector (x, y) = r(cos θ, sin θ), one can simply project
the standard deviation matrix Σ onto (x, y) :
(
cos θ sin θ
)
Σ
(
cos θ
sin θ
)
= m2(θ).
It is easy to check that the relationship between the shape elongation
|µ̃0,2|
µ̃1,1
and the eigenva-
lues λmax, λmin of the standard deviation matrix Σ is
|µ̃0,2|
µ̃1,1
= |λmax−λmin
λmax+λmin
|.
5.2 Rotational symmetry
We have seen in the last section that an image I having an Ñ -FRS has µ̃0,2 = 0. More generally,
we have the following lemmas, which was used in [5] as the basis for a HAZMAT sign recognition
method.
Lemma 12. Let Ñ be a (finite) integer. If an image I has an Ñ -fold rotation symmetry and if
l−j
Ñ
is not an integer, then µ̃j,l = 0. Conversely, if µ̃j,l = 0 for all l−j
Ñ
that are not an integer,
then the image I has an Ñ -fold rotation symmetry6.
Proof. ⇒ Let us rotate I clockwise around the origin by 2π
Ñ
. Due to its symmetry, the rotated
image I ′ must be the same as the original one. In particular, it must hold
µ̃′j,l = e2πi(l−j)/Ñ µ̃j,l = µ̃j,l.
Since l−j
Ñ
is not an integer, this equation can be fulfilled only if µ̃j,l = 0.
⇐ Suppose µ̃j,0 = 0 for any j
Ñ
not an integer of some finite integer Ñ . Let us rotate I
clockwise around the origin by 2kπ
Ñ
for each k = 1, 2, . . . , Ñ − 1, then µ̃′j,0 = e−2πijk/Ñ µ̃j,0 for
each k and all j = 0, 1, . . . , N − 1. For jk
Ñ
∈ Z, it is easy to check that e−2πijk/Ñ = 1, hence
µ̃′j,0 = µ̃j,0. For jk
Ñ
/∈ Z, j
Ñ
is not an integer either. Then µ̃j,0 = 0 = µ̃′j,0. In this way we have
µ̃′j,0 = µ̃j,0 for all j = 0, 1, . . . , N − 1. Since in the proof of Lemma 1, we showed that {µ̃j,0}N−1j=0
uniquely determine I, then we can conclude that I and I ′ are the same for any rotation with
angle 2kπ
Ñ
, k = 1, 2, . . . , Ñ − 1. Therefore the image I has an Ñ -fold rotation symmetry. �
Remark 4. As N increases, more and more columns of the Pascal triangle T r(I) become zero,
so that in the limit case, as N →∞, all entries µj,l with j 6= l of T r(I), for any order r, vanish.
This limit case corresponds to ∞-fold rotation symmetry (e.g. circles), which however does not
occur among discrete images.
6An analogue for the “if” part of this lemma for the case of a continuous image can be found in [3].
The Pascal Triangle of a Discrete Image 19
5.3 Reflection symmetry
Consider the reflection of an image about the line through the origin with direction vector(
cos(θ) sin(θ)
)T
, θ ∈ (−π
2 ,
π
2 ]. The point zk = xk+iyk is mapped to zk = z̄ke
i2θ = (xk cos(2θ)+
yk sin(2θ)) + i(xk sin(2θ)− yk cos(2θ)) under the reflection with its pixel intensity ρ(zk) staying
the same. Then the new complex moment is
µ
j,l
=
N∑
k=1
zjkz̄
l
kρ(zk) =
N∑
k=1
(
z̄ke
i2θ
)j(
zke
−i2θ)lρ(zk)
=
N∑
k=1
ei2(j−l)θz̄jkz
l
kρ(zk) = ei2(j−l)θ
N∑
k=1
z̄jkz
l
kρ(zk) = µl,je
i2(j−l)θ, ∀ j, l ∈ Z≥0.
Therefore the moment matrix for the new image I after reflection is
τN (I) =
1 0 0 · · · 0
0 e−i2θ 0 · · · 0
0 0 e−i4θ · · · 0
...
...
...
. . .
...
0 · · · · · · 0 e−i2(N−1)θ
τN (I)T
1 0 0 · · · 0
0 ei2θ 0 · · · 0
0 0 ei4θ · · · 0
...
...
...
. . .
...
0 · · · · · · 0 ei2(N−1)θ
.
We can conclude from the above relation that if an image is symmetric with respect to the
x-axis (i.e. θ = 0), then we will have τN (I) = τN (I)T , i.e. µj,l = µl,j for all j, l ∈ Z≥0. Since
µj,l = µ̄l,j by definition, this means that all the µj,l’s are real7.
Similarly, if an image is symmetric with respect to the y-axis (i.e. θ = π
2 ), we can conclude
that µj,l’s are real for j, l of the same parity and µj,l’s are imaginary for j, l of opposite parity.
More generally, we have the following result:
Lemma 13. A discrete image is symmetric with respect to reflections about a line through the
origin with direction
(
cos θ0 sin θ0
)T
⇐⇒ tan(l − j)θ0 = −
Im(µj,l)
Re(µj,l)
, j, l = 0, 1, . . . .
Proof. Notice that with reflection symmetry, we have
mn(θ0 − θ) =
1
2n
N∑
k=1
(
zke
−i(θ0−θ) + z̄ke
i(θ0−θ))nρ(zk)
=
1
2n
N∑
k=1
(
z̄ke
i2θ0e−i(θ0+θ) + zke
−i2θ0ei(θ0+θ)
)n
ρ(zk)
=
1
2n
N∑
k=1
(
z′ke
−i(θ0+θ) + z̄′ke
i(θ0+θ)
)n
ρ
(
z̄′ke
i2θ0
) (
denote z′k = z̄ke
i2θ0
)
=
1
2n
N∑
k=1
(
z′ke
−i(θ0+θ) + z̄′ke
i(θ0+θ)
)n
ρ(z′k) = mn(θ0 + θ).
Conversely, if mn(θ0 − θ) = mn(θ0 + θ) for an image I = {(zk, ρ(zk))}Nk=1, then for its
reflection image Ir = {(z̄kei2θ0 , ρ(zk))}Nk=1, there is mr
n(θ0 + θ) = mn(θ0 − θ) = mn(θ0 + θ) for
7For the continuous analogue, the fact that reflecting an object horizontally transforms complex moments into
their conjugate was previously noted in [3].
20 M. Boutin and S. Huang
any θ ∈ (−π, π]. From Lemmas 1 and 4 we can conclude that the image reconstructed from{
mr
n(θj), j = 1, . . . , n+ 1
}N−1
n=0
and
{
mn(θj), j = 1, . . . , n+ 1
}N−1
n=0
will be the same, i.e. Ir = I.
Hence the image has reflection symmetry.
By equation (5), we know
mn(θ0 + θ) =
1
2n
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)(θ0+θ),
mn(θ0 − θ) =
1
2n
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)(θ0−θ).
Then mn(θ0 + θ) = mn(θ0 − θ), i.e. mn(θ0 + θ)−mn(θ0 − θ) = 0 can be written as
1
2n
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)θ0(ei(n−2l)θ − e−i(n−2l)θ
)
= 0
⇔
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)θ0(2i sin(n− 2l)θ
)
= 0
⇔
n∑
l=0
(
n
l
)
µl,n−le
i(n−2l)θ0 sin(n− 2l)θ = 0
⇔
bn−1
2
c∑
l=0
(
n
l
)
sin(n− 2l)θ
(
µl,n−le
i(n−2l)θ0 − µn−l,lei(2l−n)θ0
)
= 0
⇔
bn−1
2
c∑
l=0
(
n
l
)
sin(n− 2l)θ2i Im
(
µl,n−le
i(n−2l)θ0) = 0
⇔
bn−1
2
c∑
l=0
(
n
l
)
sin(n− 2l)θ
(
Re(µl,n−l) sin(n− 2l)θ0 + Im(µl,n−l) cos(n− 2l)θ0
)
= 0.
The above equation is true for any θ ∈
(
−π
2 ,
π
2
]
, so it is true if and only if
Re(µl,n−l) sin(n− 2l)θ0 + Im(µl,n−l) cos(n− 2l)θ0 = 0, l = 0, 1, . . . ,
⌊
n− 1
2
⌋
,
i.e.
tan(n− 2l)θ0 = −
Im(µl,n−l)
Re(µl,n−l)
, l = 0, 1, . . . ,
⌊
n− 1
2
⌋
. (16)
Since µn−l,l = µ̄l,n−l, (16) can be written as
tan(l − j)θ0 = −
Im(µj,l)
Re(µj,l)
, ∀ j = 0, 1, . . . , l = 0, 1, . . . . � (17)
In this way, for a given discrete image, we can check (17) to decide whether it is symmetric
with respect to a certain line or not. If it is, then the line is at an angle θ given by
θ =
arctan
(
− Im(µj,j+1)
Re(µj,j+1)
)
if Re(µj,j+1) 6= 0, ∀ j = 0, 1, . . . ,
π
2
otherwise.
The Pascal Triangle of a Discrete Image 21
6 Experiments and results
To illustrate the application of the Pascal triangle to symmetry detection, we used our results
to design a simple reflection symmetry detection method8. We tested this method on images
from the MPEG-7 CE Shape-1 Part-B data set9. The data set includes 1400 binary images.
The images are divided into 70 object classes, each object class containing 20 images. All our
ground truth data and classification results can be downloaded from https://engineering.
purdue.edu/~mboutin/symmetric_shapes.
6.1 Horizontally symmetric object detection experiment
In this experiment, we identified images that have a horizontal axis of reflection symmetry us-
ing only the first four rows of the Pascal triangle. Our data set consists of 320 shapes from
the MPEG-7 shape database. Specifically, we included all 20 images contained in each of the
following 16 classes: Bird, Device1-Device5, Device7-Device9, Watch, Cup, Dog, Flatfish, Glas,
Hat, Tree.
We first manually divided the data into two sets. One set, called Set 1a, was assigned all
objects that appeared to have a clear horizontal symmetry axis, up to some minor details. The
remaining set, called Set 2a, was assigned the remaining images. Set 1a and Set 2a contain 113
and 207 images respectively. As one can see by inspecting Set 2a (see for example the images
in Fig. 5(c) and (d)), our classification was quite strict. Indeed, we excluded many objects
that could be declared symmetric under a greater tolerance for error. We thus created a second
grouping allowing for more errors: Set 1b and Set 2b, which are the data sets resulting from
this more lenient definition of symmetry.
Recall that, by Lemma 13, an image has a horizontal axis of symmetry if and only if all
the entries of its Pascal triangle are real. Since we are focusing on the symmetry of the object
contained in the image, as opposed to the image itself, we need to consider the translation
invariant Pascal triangle consisting of the centralized moments µ̃j,l. Thus horizontally symmetric
objects should be recognizable by considering the magnitude of the imaginary part of each of its
centralized moments. Note that µ̃0,0 and µ̃0,1 are always real and that µ̃2,0 = ¯̃µ0,2. Thus, if we
restrict ourselves to the first four rows of the Pascal triangle, for simplicity, then horizontally
symmetric objects are characterized by the fact that µ̃0,2, µ̃0,3 and µ̃1,2 are real. In other words,
objects that are approximately symmetric should have µ̃0,2, µ̃0,3 and µ̃1,2 with an imaginary
part close to zero. In order to remove the scale ambiguity resulting from the arbitrary scale used
to describe the pixel coordinates, we followed the approach described in Section 4, Example 2
to invariantize our coordinates with respect to scaling. Our specific classification criteria were:
if Im
(
µ̃0,2
µ̃1,1
)2
+ Im
(
µ̃0,3
µ̃
3/2
1,1
)2
+ Im
(
µ̃1,2
µ̃
3/2
1,1
)2
< r2,
then object is symmetric,
else
object is not symmetric,
where r is a variable threshold.
In our experiments, we varied the threshold r from 0.005 to 0.15. For each value of r,
we classified every image as either “symmetric” or not symmetric using the above mentioned
8The reader interested in the application of the Pascal triangle to the detection of rotational symmetries is
invited to read [5].
9Shape data for the MPEG-7 core experiment CE-Shape-1, http://www.cis.temple.edu/~latecki/
TestData/mpeg7shapeB.tar.gz.
https://engineering.purdue.edu/~mboutin/symmetric_shapes
https://engineering.purdue.edu/~mboutin/symmetric_shapes
http://www.cis.temple.edu/~latecki/TestData/mpeg7shapeB.tar.gz
http://www.cis.temple.edu/~latecki/TestData/mpeg7shapeB.tar.gz
22 M. Boutin and S. Huang
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1.1
Symmetry Classification
Threshold, r
prec
rec
acc
(a) Detection of horizontally symmetric objects using Set 1a and Set 2a data
set and the first four rows of the Pascal triangle. The max accuracy is 83.75%.
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1.1
Symmetry Classification
Threshold, r
prec
rec
acc
(b) Detection of horizontally symmetric objects using Set 1b and Set 2b data
set and the first four rows of the Pascal triangle. The max accuracy is 96.25%.
Figure 4. Precision, recall and accuracy for r from 0.005 to 0.15 at increments of 0.005.
criteria. We also computed the precision, recall, and accuracy for each value of r, where
precision =
number of true positives
number of true positives + false positives
,
recall =
number of true positives
number of true positives + false negatives
,
accuracy =
number of true positives + true negatives
number of true positives + true negatives + false positives + false negatives
.
The results obtained when using the data sets Set 1a and Set 2a are plotted in Fig. 4(a), and
those obtained using Set 1b and Set 2b are plotted in Fig. 4(b). Observe that the maximum
accuracy for the first data set, 83.75% (obtained around r = 0.07), goes up to 96.25% (obtained
around r = 0.11) for the second data set. This is consistent with the fact that the second data
set was constructed using a greater tolerance for error: after all, we are only using the first
four rows of the triangle to classify the shape. Indeed, the shapes that were moved from Set 2a
to Set 1b caused the number of false positive to decrease and thus the precision to increase
correspondingly. Fig. 5 illustrates some of our results.
6.2 Symmetric objects (any axis) detection experiment
In this experiment we identified images that have an axis of reflection symmetry. Our data set
consists of 200 shapes from the following 10 classes of the MPEG-7 shape database: Beetle, Bell,
Bird, Butterfly, Camel, Cattle, Classic, Crown, Horseshoe, Lizzard.
The Pascal Triangle of a Discrete Image 23
(a) Set 1a shapes classified as symmetric. (b) Set 1a shapes classified as not symmetric.
(c) Set 2a shapes (not in Set 1a) classified as
symmetric.
(d) Set 2a shapes (not in Set 1a) classified as
not symmetric.
Figure 5. Small selection of shapes chosen from the MPEG-7 shape database, r = 0.07.
We first manually divided the data set into two sets. One set, called Set 1, was assigned all
objects in the classes of Beetle, Bell, Butterfly, Crown and Horseshoe. Because these objects
all represent shapes that have a natural axis of symmetry. The remaining set, called Set 2, was
assigned the images in the classes of Bird, Camel, Cattle, Classic and Lizzard. Set 1 and Set 2
each contains 100 images.
Recall that, by Lemma 13, an image is symmetric with respect to reflections about a line
through the origin with direction
(
cos θ0 sin θ0
)T
if and only if tan(l − j)θ0 = − Im(µj,l)
Re(µj,l)
, for
all j, l ∈ Z+. Since we are focusing on the symmetry of the object contained in the image,
as opposed to the image itself, we need to consider the translation invariant Pascal triangle
consisting of the centralized moments µ̃j,l. Thus the symmetry axis of symmetric objects should
be recognizable by considering the arc tangent of the negative ratio of the imaginary part and
the real part of each of its centralized moments. Note that the arc tangent of an angle are always
between −π
2 and π
2 , hence there will be some ambiguity when deciding θ0 from arctan(kθ0) with
|k| > 1. Also note that µ̃0,1 is always zero and µ̃j,l = ¯̃µl,j . Thus for simplicity, we characterized
the symmetry axis of symmetric objects by the fact that
θ0 = arctan
(
− Im(µ̃1,2)
Re(µ̃1,2)
)
= arctan
(
− Im(µ̃2,3)
Re(µ̃2,3)
)
= arctan
(
− Im(µ̃3,4)
Re(µ̃3,4)
)
.
In other words, objects that are approximately symmetric with respect to an axis of angle θ0
should have arctan
(
− Im(µ̃1,2)
Re(µ̃1,2)
)
, arctan
(
− Im(µ̃2,3)
Re(µ̃2,3)
)
and arctan
(
− Im(µ̃3,4)
Re(µ̃3,4)
)
close to each other.
Since we consider the ratio of the imaginary part and real part of each moment, it is not
necessary to remove the scale ambiguity resulting from the arbitrary scale used to describe the
pixel coordinates in this experiment, as the quantities we consider are already invariant under
scaling. Also note that, if the symmetry axis of an image is of angle θ0 = π
2 , then θ0 = −π
2 also
defines the same symmetry axis, although the arc tangent of the angles near these two values
are quite different. Taking these into account, our specific classification criteria were:
if
∣∣∣|θ1| −
π
2
∣∣∣ < T,
∣∣∣|θ2| −
π
2
∣∣∣ < T,
∣∣∣|θ3| −
π
2
∣∣∣ < T,
then object is symmetric vertically,
24 M. Boutin and S. Huang
0 5 10 15
0.4
0.5
0.6
0.7
0.8
0.9
1
Symmetry Axis Detection
Threshold, T
prec
rec
acc
Figure 6. Symmetric objects detection using µ̃2,2, µ̃2,3 and µ̃3,4. The max accuracy is 79.5%.
else if |θ1 − θ2| < T, |θ2 − θ3| < T, |θ3 − θ1| < T,
then object is symmetric with symmetry axis θ0 =
θ1 + θ2 + θ3
3
,
else
object is not symmetric,
where θ1 = arctan
(
− Im(µ̃1,2)
Re(µ̃1,2)
)
, θ2 = arctan
(
− Im(µ̃2,3)
Re(µ̃2,3)
)
, θ3 = arctan
(
− Im(µ̃3,4)
Re(µ̃3,4)
)
and T is a vari-
able threshold.
In our experiments, we varied the threshold T from 1◦ to 15◦. For each value of T , we classified
every image as either “symmetric” or not symmetric using the above mentioned criteria. And
for each symmetric image, we found its symmetry axis. We also computed the precision, recall,
and accuracy for each value of T .
The classification results obtained when using the data sets Set 1 and Set 2 are plotted in
Fig. 6. Observe that the maximum accuracy for the data set is 79.5% at T = 4◦. The accuracy
of the experiment could be improved by using more moments: after all, we are only using three
moments to classify the shapes. Indeed, using more moments would yield a more selective
criterion, which should decrease the number of false positives and increase the number of true
negatives. Fig. 7 illustrates some of our results.
7 Conclusion and future work
We have introduced the Pascal triangle of a discrete image, which is constructed using complex-
valued moments. We obtained the relationship between the triangle and the Fourier series
coefficients of the moment of the Radon transform of the image, that is, each row n of the Pascal
triangle contains the coefficients of the Fourier series of the n-th order moment of the Radon
transform of the image. This relationship gives the moments a clear geometric interpretation.
For example,
µ0,3
8 of an image is the coefficient of ei3θ in the third order moment m3(θ) of the
Radon transform of the image, and thus when |µ0,3| is large, then the order three variation of
the skewness of the projection is proportionally large.
We showed that the image can be fully reconstructed using a finite number of rows of the
triangle. This fact, which is specific to discrete (finite) images, allows us to be able to derive
necessary and sufficient conditions for the presence of various symmetries. It also allows us
to conclude that the invariantized Pascal triangle separates the orbits of certain group actions.
Indeed, by using the moving frame method we were able to invariantize the Pascal triangle with
respect to translation, rotation and scaling, and by using the reconstruction property of the
invariantized Pascal triangle, we were able to show the uniqueness of the reconstruction modulo
these transformations.
The Pascal Triangle of a Discrete Image 25
(a) Set 1 shapes classified as symmetric with
axis 53.0◦ and 94.5◦ respectively.
(b) Set 1 shapes classified as not symmetric.
(c) Set 2 shapes classified as symmetric with
axis 99.2◦ and 136.1◦ respectively.
(d) Set 2 shapes classified as not symmetric.
Figure 7. Small selection of symmetric objects detection results for images in Set 1 and Set 2 with
threshold T = 5.
We tested the application of the Pascal triangle to the recognition of symmetric shapes from
the MPEG-7 shape database. More specifically, we derived a simple method to detect horizontal
symmetries using the first four rows of the triangle. We then tested this method using 16 object
classes. We also derived a simple method to detect symmetry axes in objects using entries within
only the first eight rows of the triangle. We then tested this method using 10 object classes.
Extension of our method to other group actions such as affine transforms should be doable
using the moving frame method. Observe that our definition for µj,l naturally extends to vector
valued pixel intensities. Therefore, it should be straightforward to extend our framework to the
case of color images. We are looking forward to also extending this work to the case of 3D objects.
Acknowledgments
This research was supported in parts by NSF grant CCF-0728929.
References
[1] Fels M., Olver P.J., Moving coframes. I. A practical algorithm, Acta Appl. Math. 51 (1998), 161–213.
[2] Fels M., Olver P.J., Moving coframes. II. Regularization and theoretical foundations, Acta Appl. Math. 55
(1999), 127–208.
[3] Flusser J., Zitova B., Suk T., Moments and moment invariants in pattern recognition, John Wiley & Sons
Ltd., Chichester, 2009.
[4] Gustafsson B., He C., Milanfar P., Putinar M., Reconstructing planar domains from their moments, Inverse
Problems 16 (2000), 1053–1070.
[5] Haddad A.W., Huang S., Boutin M., Delp E.J., Detection of symmetric shapes on a mobile device with
applications to automatic sign interpretation, Proc. SPIE 8304 (2012), 83040G, 13 pages.
[6] Milanfar P., Verghese G.C., Karl W., Willsky A.S., Reconstruction polygons from moments with connections
to array processing, IEEE Trans. Signal Process. 43 (1995), 432–443.
[7] Olver P.J., Classical invariant theory, London Mathematical Society Student Texts, Vol. 44, Cambridge
University Press, Cambridge, 1999.
[8] Rostampour A.R., Madhvapathy P.R., Shape recognition using simple measures of projections, in Procee-
dings of Seventh Annual International Phoenix Conference on Computers and Communications (Scottsdale,
AZ, 1988), IEEE, Arizona State University, 1988, 474–479.
http://dx.doi.org/10.1023/A:1005878210297
http://dx.doi.org/10.1023/A:1006195823000
http://dx.doi.org/10.1088/0266-5611/16/4/312
http://dx.doi.org/10.1088/0266-5611/16/4/312
http://dx.doi.org/10.1117/12.908815
http://dx.doi.org/10.1109/78.348126
http://dx.doi.org/10.1017/CBO9780511623660
http://dx.doi.org/10.1109/PCCC.1988.10124
http://dx.doi.org/10.1109/PCCC.1988.10124
1 Definition and reconstruction properties
2 Relationship with the Radon transform
3 Image reconstruction from samples
4 Prolongation of group actions on the moments and invariantization
5 Geometric interpretation of the moments
5.1 Shape elongation
5.2 Rotational symmetry
5.3 Reflection symmetry
6 Experiments and results
6.1 Horizontally symmetric object detection experiment
6.2 Symmetric objects (any axis) detection experiment
7 Conclusion and future work
References
|