Istanbul 2004
subdivision
the advantage
rlobal features:
ild and Shiren
is selected as
| triangles are
e an equilateral
ary subdivision
distortion when
decisions will
pe and size of
las on the ease
| is selected, in
dpoints of each
y.
ry subdivision
promise. It is
on the plane: a
our equilateral
ivided into four
sion based on
lows in Figure 4
1 octahedron
ed on manifold
ause every point
set in Euclidean.
r every point in
tered with many
is a 2-dimension
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
If the spherical surface is divided by quaternary subdivision
based on octahedron, the spherical surface digital space is
8x4 (N 19.5... Rn N ) regular mesh based on finite
,
discrete space, expressed as 7 ^. In the first level. spherical
surface has the 8 base triangles, which are local coordinates
systems of manifold. The relationship between $8 local
coordinate systems can be described by spherical surface
spacefilling curves (shown as Figure 5), which is a continuous
mapping from a one-dimensional interval, to the points on the
spherical surface. Continuous ordering based on spacefilling
curves have been proven useful in heuristics related to a number
of spatial, combinatorial, and logistical problems (Bartholdi and
Goldsman 2001)
A
NU
Figure S. Spherical spacefilling curves based on
octahedron with quaternary subdivision
To every base triangle, quaternary spherical surface spacefilling
curve still can be used to express the relationship between every
sub-triangle. In quaternary subdivision, the relationship
between sub-triangles can be depicted with quaternary spherical
surface spacefilling curve (shown as Figure 6). In given
resolution, spherical surface digital space can be continuously
indexed by quaternary spherical spacefilling curve (Details in
Bartholdi 2001). Comparing with the other modal (Dutton
1991), spherical surface digital space has the advantage of
continuous ordering. It makes us to index the sphere digital
space continuously to allow quick and efficient search at
multi-scale. At the same time, spherical surface digital space has
the intrinsic disadvantage that the triangle is equivalent but not
equal with each other.
aster mimes
(a) level 1
(b) level2 (c) level 3
Figure 6. The quaternary spherical surface spacefilling curve
Planar digital space is a simple Euclidean space, but spherical
surface digital space is a more complex manifold. So spherical
surface digital space is not the simple copy of planar digital
space. It has some special properties just as follows. Spherical
surface digital spacc is not a Euclidean space, that is to say, it is
no homomorphous to planar and no single coordinates system
can be sct up to express every point in spherical surfacc.
Although cells of spherical surface digital space are
approximately equivalent, it still has a multi-scale and
continuous ordering advantages (Bartholdi and Goodsman
2001).
3j. THEBASIC TOPOLOGY MODEL OF SPHERICAL
SURFACE DIGITAL SPACE
From the definition of spherical surface digital space, y is
the result of partitioning the connected spherical surface into
small triangular pieces that cover the whole spherical surface
space. Each triangle is viewed as an element, called “spel”
(short for spatial element). All the spels in the spherical surface
^
can form a new set, which can be named as grid set 7^ . The
2
set 1° can then be regarded as the hardware of the spherical
surface digital space. The transitive closure Ó of the
2
adjacency relation between the two spels in 7” can be
considered as software. This system can be expressed as
(T^,8) , where Ó is the binary relations. This binary
>
relation determines the connectedness between the spels in 7
9 ~
(T 6) is also referred to as "spherical surface digital
2 2v.
topology". S is a connected space, but the 7^ is not
connected space. In 7 ^ , this implicit assumption of
2
connectedness in S no longer works.
3.1 General definitions and notations
2
Points of 7. associated with triangles that have value 1 are
called black points, and those associated with triangles with
value 0 are called white points. The set of black points normally
corresponds to an object in the digital image. First, we consider
?
objects as subsets of the spherical surface digital space y
m2
Elements of. 7 are called “spels” (short for spatial element).
The set of spels which do not belong to an object O is
2
included in. 7 constitute the complement of the object and is
denoted by O . Any spel can be seen as a unit triangle centered
at a point with integer coordinates. Now, we can define some
binary symmetric antireflexive relations between spels. Two
spels are considered as 3-adjacency if they share an edge and
12-adjacent if they share a vertex. For topological
considerations, we must always use two different adjacency
relations for an object and its complement (shown as Figure 7).
(m, n
We sum this up by the use of a couple with
(n, n ) = 4312) n - adjacency
the
n' - adjacency far
being used for the
object and the its complement. By
transitive closure of these adjacency relations, we can define
another one: connectivity between spels. We define an
n-path 7
O included
voxels (1) i
with a length k from spel € to spel b in
>
in T as a sequence of
ovis ‚such that for 0 1 sk , the
0
spel "V, is n - adjacent or equal to V., , with
Vg 78 and V, — b. Now we define connectivity: two
voxels à and. Dare called n - connected in an object O
if there exists an N - path 77 from à to bin O. This is an
relation
equivalence between spels of O . and the
