IEEE Robotics & Automation Magazine - September 2014 - 68

Algorithm 1. Helmert blocking.
1) Given a partitioning scheme, establish the normal
equations for each partial subnet separately.
2) Eliminate the unknowns for all nodes that do not have
constraints with neighboring partial subnets.
3) Establish the main system after eliminating all the inner nodes containing only intrasubnet measurements.
4) Solve the main system of equations containing only
separator nodes.

(a)

5) Solve for inner nodes given the value of separator nodes.

graph partitioning and submapping have been frequently
used in robotics, to the best of our knowledge, Helmert's
method has not been referenced in the robot mapping
community-only Triggs et al. [53] mention it as an optimization procedure in their bundle adjustment survey.
Helmert observed that by partitioning the triangle net in a
particular way, one can solve the overall system of equations
in parallel. He outlined that the whole triangle net can be
broken into multiple smaller subnets. All nodes that have
constraints only within
the same subnet are called
inner nodes and can be
There might still be more
eliminated. All separator
nodes, i.e., those that conmethods in geodetic
nect multiple subnets, are
mapping that are unknown then optimized. The previously eliminated inner
nodes can be computed
outside their community
independently given the
values of the separator
but could inspire other
nodes. Most importantly,
the formed subnets can
fields.
be solved in parallel.
He l m e r t's b l o c k i n g
method is outlined in Algorithm 1 and is explained more
precisely as a mathematical algorithm by Wolf in [54]. Consider a simple triangle net shown in Figure 4. In Figure 4(a),
each line segment is a constraint and the end of segments
represents a physical observation tower. Helmert observed
that if he divides the triangle net into two halves, for example, as shown in Figure 4(b), the top half of the towers will be
independent of the bottom half given the values of the separators, as shown in Figure 4(c). Such a system can be solved
using reduced normal equations [5], [54].
Let us represent the whole system of equations from the
triangle net in Figure 4(a) as
Ax = b.

(7)

This equation can be subdivided into three parts in the following manner:
xs
6A s A 1 A 2@ >x 1H = b.
x2
68

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

september 2014

(8)

(b)

(c)

(d)

(e)
Figure 4. (a)-(e) The Helmert blocking in action. The left column
shows a toy example of triangle net. The right column shows the
corresponding stacked coefficient matrix for each net.

Here, A s and x s represent the coefficients and unknowns,
respectively, arising from the central separator. A 1 and A 2
are coefficients of the top and bottom subnets. The coefficient matrix 6A s A 1 A 2@ in (8) is shown on the right-hand
side of Figure 4(c). The corresponding system of normal
equations is
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2014
