x
x x
0
1
1
1
1
3
=
+
(
)
+
=
=
∑∑
A
A
kr kr
k r
k
K
r
R
r
,
(45)
with
x
kr
= [
X
″
kr
,
Y
″
kr
]
= [
x
kr
,
y
kr
]
being the
k
th
vertex of the ring
r
with
K
r
vertices and edges, and the matrix
M
of normalized
second moments contains the elements:
µ
xx
kr kr
kr k r
k r
k
K
r
R
A
A x x x
x
r
=
+
+
(
)
+
+
=
=
∑∑
1
6
2
1
1
2
1
1
,
,
(46)
µ
yy
kr kr
kr k r
k r
K
r
R
A
A y y y
y
r
=
+
+
(
)
+
+
=
∑∑
1
6
2
1
1
2
1
k
=
1
,
,
(47)
and
µ
xy
kr kr k r
kr k r
k r k r
k r kr
k
A
A x y
x y
x y
x y
=
+
+
+
(
)
+
+
+
+
=
1
12
2
2
1
1
1
1
1
,
,
,
,
,
K
r
R
r
∑∑
=
1
(48)
The matrix of centralized second moments reads:
M
″
=
G
–
x
0
x
0
(49)
and its eigendecomposition
M
″
=
U
Λ
U
yields the eigenvec-
tors
U
= [
u
1
,
u
2
] and the two eigenvalues [
λ
1
,
λ
2
] = diag(
Λ
).
Observe, the eigenvalues
λ
1
and
λ
2
of the 2×2 matrix
M
″
in
Equation 49, derived by integration, correspond to the eigen-
values
λ
1
and
λ
2
of the 3×3 matrix
M
in Equation 7, derived by
summation over all points.
The polygon’s centroid
x
0
on the plane
A
″
= [0,0,1,–
Z
]
represented in 3D space can then be backtransformed using:
X
x
0
0
=
Q
Z
(50)
to obtain the polygon’s centroid
0
in the 3D space. And even-
tually, the eigenvectors
u
1
and
u
2
in the plane
A
″
are rotated
according to
R Q U Q
=
( )
=
,
Diag 1
0
0 0 1
1 2
u u
(51)
to determine the rotation matrix
R
as part of the plane’s repre-
sentation (Equation 1).
For the determination of the plane’s uncertainty we consid-
er a virtual scanning process yielding equally spaced points
on the plane. Given the area
A
of a polygon and a sampling
distance
Δ
in two orthogonal directions, the number of sam-
pling points in the polygon is
S = A
/
Δ
2
. Assuming a known,
representative weight
w
= 1/
σ
2
for all coordinates in Equation
15, we get
N
11
=
wS
, and therefore, using the eigenvalues of
M
″
in Equation 49:
( )
σ
σ
∆
q
A
2
2
=
(52)
( )
σ
σ
∆
λ
α
2
2
2
=
A
(53)
( )
σ
σ
∆
λ
β
2
2
1
=
A
(54)
Obviously, just the product
σ
∆
of the assumed uncertainty
σ
of the virtual sampling points and the spacing
∆
has to
be specified to compute the complete representation of the
uncertain plane
A
corresponding to a given polygon
P
. The
uncertain plane in centroid representation (Equation 1) is
completely specified by Equations 50 through 54. Figure 1
summarizes the computations.
Input
: coordinates
X
k
of the polygon vertices, product
σ
Δ
of virtual sampling distance and standard deviation
Output
: plane parameters and their covariance matrix
in homogeneous representation {
A
,
Σ
AA
}
1. Compute plane parameters
A
in homogeneous repre-
sentation (39, 41) and transform polygon into plane
with
Z
=const (42, 43)
2. Compute normalized and centralized second mo-
ments (45, 48), perform eigendecomposition of
moment matrix
3. Transform centroid (50) into 3D space (51)
4. Compute variances of the centroid form (52, 53, 54)
5. Compute covariance matrix
Σ
AA
for plane parameters
in homogeneous representation (20, 23)
Figure 1. Computation of plane parameters and their
covariance matrix given a planar polygon in 3D.
Testing Geometric Relations
For boundary representations, we assume that each vertex is
defined by at least three planes intersecting in one point. Adja-
cent faces lying in the same plane will therefore lead to unde-
fined points. Thus, in a preprocessing step we check the faces’
binary relations encoded in the given boundary representation
for identical planes and merge faces corresponding to the
same plane. Additionally, we restrict ourselves to the relation
orthogonality
as the most dominant geometric constraint.
The assumptions that the geometric relations hold, con-
stitute the null hypotheses to be checked and the space of
hypotheses is given by all pairs of adjacent faces represented
by polygons. The relations are formulated as constraints for
two planes
A
and
B
in homogeneous representation
A
and
B
, respectively, and the computation of the test statistics
requires the joint 8×8 covariance matrix
Σ
= Diag(
Σ
AA
,
Σ
BB
) of
the two parameter groups.
Two planes
A
and
B
are identical if:
d
A B
B A
≡
=
×
−
=
h h
h
h
A B
0
0
0
(55)
holds. The singular covariance matrix of the distances
d
º
is
deduced by variance-covariance propagation
Σ
º
=
J
Σ
J
with
the 6×8 Jacobian:
J
S
S
A I
A I
h
h
h
h
=
−
−
( )
( )
A
A
A
A
0
0
0 3
0 3
(56)
using
A
=
B
because of the assumed identity. The rank of the
matrix
J
is three and, thus, the corresponding
χ
2
3
-distributed
test statistic reads:
T
≡ ≡ ≡
+
≡
=
d d
Σ
(57)
with the Moore-Penrose pseudoinverse
Σ
+
º
.
Two planes
A
and
B
are orthogonal if:
d
h h
⊥
=
=
A B
0
(58)
holds, where
A
h
and
B
h
are the normals. The variance of the
distance
d
^
is deduced by variance-covariance propagation
σ
2
^
=
J
Σ
J
with the Jacobian:
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2018
397
