Digi iza ion
D . Rocio Gonzalez-Diaz
ogo[email p o ec ed]
Depa men o Applied Ma h, Uni e si y o Se ille, Spain
D . Pee S elldinge
[email p o ec ed]bu g.de
Compu e Science Depa men , Uni e si y o Hambu g, Ge many
P o esso Longin Jan La ecki
la ec[email p o ec ed]
Depa men o Compu e and In o ma ion Sciences, Temple Uni e si y, USA
1 De ini ion
Digi iza ion is a ma hema ical model o con e ing con inuous subse s o he
plane o space ( ep esen ing eal objec s) o digi al se s in Z2o Z3o simila
g ids ( ep esen ing segmen ed images o hese objec s). This de ini ion can be
gene alized o any dimension n > 3: Digi iza ion con e s ( ans o ms) con in-
uous subse s o Rn o digi al se s in Zno , equi alen ly, o unc ions om Zn
o {0,1}.
2 Backg ound
A undamen al ask o knowledge ep esen a ion and p ocessing is o in e p op-
e ies o eal objec s o si ua ions gi en hei ep esen a ions. In spa ial knowl-
edge ep esen a ion and, in pa icula , in compu e ision and medical imaging,
eal objec s a e ep esen ed in a pic o ial way as ini e and disc e e se s o pix-
els o oxels. The disc e e se s esul by a quan iza ion p ocess, in which eal
objec s a e app oxima ed by disc e e se s. In compu e ision, his p ocess is
called sampling o digi iza ion and is na u ally ealized by echnical de ices like
compu e omog aphy scanne s, CCD came as o documen scanne s. Digi al
images ob ained by digi iza ion a e sui able o es ima e he eal objec p ope -
ies like olume and su ace a ea. The e o e, a undamen al ques ion add essed
in spa ial knowledge ep esen a ion is: Which p ope ies in e ed om disc e e
ep esen a ions o eal objec s co espond o p ope ies o hei o iginals, and
unde wha condi ions his is he case? While his p oblem is well-unde s ood
in he 2D case wi h espec o opology [1, 2, 3, 4, 5], i is no as simple in 3D, as
shown in [7]. Only ecen ly a i s comp ehensi e answe o his ques ion wi h
1
espec o impo an opological and geome ic p ope ies o 3D objec s has been
p esen ed in [8, 9].
Some ecen wo ks done o he gene al case a e shown below. I is p o en in
[10] ha al hough Gauss digi ized bounda ies o subse s o Rn, o n≥3 may
no be mani olds, non-mani oldness may only occu in places whe e he no mal
ec o is almos aligned wi h some digi iza ion axis, showing ha al hough an
objec and i s digi iza ion a e close in he Hausdo sense h ough he p ojec ion
map, hey may no be homemomo phic. Ne e heless, in ha pape , he au ho s
p o e he alidi y o he digi al su ace in eg al as a mul ig id con e gen in eg al
es ima o o subse s o Rn, o n≥3, as long as he digi al no mal es ima o is
also mul ig id con e gen . In addi ion, [11] is a sho su ey on digi al analy ical
geome y whe e he main idea is o analy ically cha ac e ize digi al se s o
desc ibe i s con inuous coun e pa in Rn, o n≥3 and ela ed ans o m.
This way, digi al subse s o Zna e de ined by a lis o inequali ies and no by
an enume a ion o poin s in Zn. Finally, in [12], a modus ope andi is p oposed
o model a digi al subse o Znas a cubical complex p o ing ha he digi al
undamen al g oup o a digi al subse o Znis isomo phic o he undamen al
g oup o i s co esponding cubical complex, ensu ing he opological co ec ness
o he app oach. Thus, p ope ies o digi al subse s o Zncan be compu ed
on hei co esponding cubical complexes using powe ul Algeb aic Topological
ools. Obse e ha his las app oach ‘closes’ a loop: s a ing om a con inuous
subse o Rn, a digi al subse o Znis ob ained and used o compu e a cubical
complex whose embedding in Rnis again a con inuous subse o Rn.
The desc ip ion o geome ic and, in pa icula , opological ea u es in dis-
c e e s uc u es is based on g aph heo y, which is widely accep ed in he com-
pu e science communi y. A g aph is ob ained when a neighbo hood ela ion
is in oduced in o a disc e e se , e.g., a ini e subse o Z2o Z3, whe e Zde-
no es he in ege s. On he one hand, g aph heo y allows in es iga ion in o
connec i i y and sepa abili y o disc e e se s ( o a simple and na u al de ini-
ion o connec i i y see [13, 21], o example). On he o he hand, a ini e g aph
is an elemen a y s uc u e ha can be easily implemen ed on compu e s. Dis-
c e e ep esen a ions a e analyzed by algo i hms based on g aph heo y, and he
p ope ies ex ac ed a e assumed o ep esen p ope ies o he o iginal objec s.
Since p ac ical applica ions, o example in image analysis, show ha his is no
always he case, i is necessa y o ela e p ope ies o disc e e ep esen a ions o
he co esponding p ope ies o he o iginals. Since such ela ions can desc ibe
and jus i y he algo i hms on disc e e g aphs, hei cha ac e iza ion con ibu es
di ec ly o he compu a ional in es iga ion o algo i hms on disc e e s uc u es.
This compu a ional in es iga ion is an impo an pa o he esea ch in com-
pu e science, and in pa icula , in compu e ision (Ma [14]), whe e i can
con ibu e o he de elopmen o mo e sui able and eliable algo i hms o ex-
ac ing equi ed shape p ope ies om disc e e ep esen a ions.
I is clea ha no disc e e ep esen a ion can exhibi all ea u es o he
eal o iginal. Thus one has o accep comp omises. The comp omise chosen
depends on he speci ic applica ion and on he ques ions which a e ypical o
ha applica ion. Real objec s and hei spa ial ela ions can be cha ac e ized
2
using geome ic ea u es. The e o e, any use ul disc e e ep esen a ion should
model he geome y ai h ully in o de o a oid alse conclusions. Topology
deals wi h he in a iance o undamen al geome ic ea u es like connec i i y
and sepa abili y. Topological p ope ies play an impo an ole, since hey a e
he mos p imi i e objec ea u es and human isual sys em seems o be well-
adap ed o cope wi h opological p ope ies.
Howe e , one does no ha e any di ec access o spa ial p ope ies o eal
objec s. The e o e, eal objec s a e ep esen ed as bounded subse s o he Eu-
clidean space R3, and hei 2D iews (p ojec ions) as bounded con inuous sub-
se s o he plane R2. Hence, om he heo e ical poin o iew o knowledge
ep esen a ion, he goal is o ela e wo di e en pic o ial ep esen a ions o
objec s in he eal wo ld: a disc e e and a con inuous ep esen a ion.
Al eady wo o he i s books in compu e ision deal wi h he ela ion
be ween he con inuous objec and i s digi al images ob ained by modeling a
digi iza ion p ocess. Pa lidis [1] and Se a [2] p o ed independen ly in 1982
ha an - egula con inuous 2D se S( he de ini ion ollows below) and he
con inuous analog o he digi al image o Sha e he same shape in a opological
sense. Pa lidis used 2D squa e g ids and Se a used 2D hexagonal sampling
g ids.
In 3D his p oblem is much mo e complica ed. In 2005 i has been shown in
[7] ha he connec i i y p ope ies a e p ese ed when digi izing a 3D - egula
objec wi h a su icien ly dense sampling g id, bu he p ese a ion o connec-
i i y is much weake han opology. S elldinge and K¨o he [7] also ound ou
ha opology p ese a ion can e en no be gua an eed wi h sampling g ids o
a bi a y densi y i one uses he s aigh o wa d oxel econs uc ion, since he
su ace o he con inuous analog o he digi al image may no be a 2D mani old.
The ques ion how o gua an ee opology p ese a ion du ing digi iza ion in 3D
emained unsol ed un il 2007.
The solu ion was p o ided in [8], whe e he same digi iza ion model as
Pa lidis and Se a is used, also - egula se s (bu in R3) a e used o model
he con inuous objec s. As al eady shown in [7] he gene aliza ion o Pa lidis’
s aigh o wa d econs uc ion me hod o 3D ails since he econs uc ed su -
ace may no be a 2D mani old. Fo example, Figu e 1 shows a con inuous objec
and i s digi al econs uc ion whose su ace is no a 2D mani old. Howe e , i
is possible o use se e al o he econs uc ion me hods ha all esul in a 3D
objec wi h a 2D mani old su ace. Mo eo e i is also shown in [8] ha hese
econs uc ions and he o iginal con inuous objec a e homeomo phic and hei
su aces a e close o each o he .
The i s econs uc ion me hod, Majo i y in e pola ion, is a oxel-based
ep esen a ion on a g id wi h doubled esolu ion. I always leads o a well-
composed se in he sense o La ecki [15], which implies ha a lo o p oblems
in 3D digi al geome y become ela i ely simple.
The second me hod is he mos simple one. I jus uses balls wi h a ce -
ain adius ins ead o cubical oxels. When choosing an app op ia e adius he
opology o an - egula objec will no be des oyed du ing digi iza ion.
The hi d me hod is a modi ica ion o he well-known Ma ching Cubes algo-
3
Figu e 1: The digi al econs uc ion (b) o an - egula objec (a) may no be
well-composed, i.e., i s su ace may no be a 2D mani old as can be seen in he
magni ica ion
i hm [16]. The o iginal Ma ching Cubes algo i hm does no always cons uc a
opologically sound su ace due o se e al ambiguous cases [17, 18]. As shown
in [8, 9] mos o he ambiguous cases can no occu in he digi iza ion o an
- egula objec and ha he only emaining ambiguous case always occu s in
an unambiguous way, which can be deal wi h by a sligh modi ica ion o he
o iginal Ma ching Cubes algo i hm. Thus he gene a ed su ace is no only
opologically sound, bu i also has exac ly he same opology as he o iginal
objec be o e digi iza ion. Mo eo e i is shown ha one can use ilinea in e -
pola ion and ha one can e en blend he ilinea pa ches smoo hly in o each
o he such ha one ge s smoo h objec su aces wi h he co ec opology. Each
o hese me hods has i s own ad an ages making he p esen ed esul s applicable
o many di e en image analysis algo i hms.
In he gene al case, well-composed digi al subse s o Zndo no p esen
opological pa adoxes. They also ha e e y in e es ing p ope ies and p ac-
ical applica ions. Di e en “ la o s” o well-composedness (WC) a e p esen in
he li e a u e: WC based on equi alence o connec i i ies (EWC), digi al WC
(DWC), WC in he Alexand o sense (AWC) and WC in he con inuous sense
(CWC). All hese de ini ions a e equi alen in 2D. Fo he 3D case, we ha e:
DWC ⇔AWC ⇔CWC. Fo he nD case, n≥3, we ha e: EWC ⇐DWC.
The es o equi alences o he case n > 3 a e open p oblems nowadays. The
de ini ion o well-composedness has also been ex ended o a bi a y g ids and
mul i alued images (AGWC), see [19].
Me hods o epai ing digi al subse s o Zn, o n > 3, o con e hem in
well-composed ones is a complica ed open p oblem. A i s s ep in his di ec ion
is done in [20] in which a combina o ial me hod is gi en o compu ing a simpli-
cial complex homo opy equi alen o he cubical complex associa ed o a gi en
4
Figu e 2: We s a om I= (Zn, FI) being FIa digi al subse o Zn(in ac ,
FI⊂4Zn). The digi al subse FJo Znencodes he cells o he associa ed
cubical complex Q(I) (blue is used o 0-cells, ed o 1-cells and g een o 2-
cells). Now, we ‘ epai ’ FJ o ob ain he digi al subse FLo Znby ‘ hickening’
he c i ical poin s o FJ. Then, we compu e he simplicial complex PS(I) whose
se o e ices is FL, sa is ying ha he e exis s a ace-connec ed pa h o n-
simplices in PS(I) joining any wo n-simplices inciden o a common e ex in
PS(I), ha is, PS(I) is weakly well-composed, see [20].
digi al subse o Zn. This simplicial complex is con inuously well-composed o
n≤3 and weakly well-composed o n > 3 in he sense ha o any wo n-
simplices inciden o a common e ex , he e always exis s a ace-connec ed
pa h o n-simplices inciden o . A g aphical diag am o he me hod is gi en in
2. Obse e ha cubical and simplicial complexes de i ed om ha me hod a e
also s o ed as digi al subse s o Zn, so ha la e calcula ions on he elemen s
o he complex can be done e icien ly.
3 Theo y
The (Euclidean) dis ance be ween wo poin s xand yin Rnis deno ed by d(x, y),
and he (Hausdo ) dis ance be ween wo subse s o Rnis he maximal dis ance
be ween each poin o one se and he nea es poin o he o he . Le A⊂Rn
and B⊂Rmbe se s. A unc ion :A→Bis called homeomo phism i i is
bijec i e and bo h i and i s in e se a e con inuous. I is a homeomo phism,
hen Aand Ba e homeomo phic. Le A,Bbe wo subse s o Rn(pa icula ly,
n= 2 o 3). Then a homeomo phism :Rn→Rnsuch ha (A) = B
and d(x, (x)) ≤ , o all x∈Rn, is called an -homeomo phism o A o B
and Aand Ba e -homeomo phic. A Jo dan cu e is a se J⊂Rnwhich
is homeomo phic o a ci cle. Le Abe any subse o Rn. The complemen
o Ais deno ed by Ac. All poin s in Aa e o eg ound while he poin s in Ac
a e called backg ound. The open ball in Rno adius and cen e cis he se
5

Figu e 3: Fo each bounda y poin o a 2D/3D - egula se exis s an ou side
and an inside oscula ing open -disc/ball
Figu e 4: (a) C i ical con igu a ion (C1). (b) C i ical con igu a ion (C2). Fo
he sake o cla i y, only he oxels o o eg ound o backg ound poin s a e shown
B0
(c) = {x∈Rn|d(x, c)< }, and he closed ball in Rno adius and cen e
cis he se B (c) = {x∈Rn|d(x, c)≤ }. The bounda y o A, deno ed ∂A,
consis s o all poin s x∈Rnwi h he p ope y ha i Bis any open se o Rn
such ha x∈B, hen B∩A6=∅and B∩Ac6=∅.
An open ball B0
(c) is angen o ∂A a a poin x∈∂A i ∂A∩∂B0
(c) = {x}.
An open ball B0
(c) is an oscula ing open ball o adius o ∂A a poin x∈∂A
i B0
(c) is angen o ∂A a xand ei he B0
(c)⊆A0o B0
(c)⊆(Ac)0, whe e
A0is a maximal open subse o A, i.e., Awi hou i s bounda y.
De ini ion 1 A se A⊂Rnis called - egula i , o each poin x∈∂A, he e
exis wo oscula ing open balls o adius o ∂A a xsuch ha one lies en i ely
in Aand he o he lies en i ely in Ac. Examples illus a ing 2D and 3D cases
a e shown in 3.
No e ha he bounda y o a 3D - egula se is a 2D mani old su ace. Any
se Swhich is a ansla ed and o a ed e sion o he se 2· 0
√3Z3is called a cubic
0-g id and i s elemen s a e called sampling poin s. No e ha he dis ance
d(x, p) om each poin x∈R3 o he nea es sampling poin s∈Sis a
mos 0. The oxel VS(s) o a sampling poin s∈Sis i s Vo onoi egion R3:
6
VS(s) = {x∈R3|d(x, s)≤d(x, q),∀q∈S}, i.e., VS(s) is he se o all poin s
o R3which a e a leas as close o sas o any o he poin in S. In pa icula ,
no e ha VS(s) is a cube whose e ices lie on a sphe e o adius 0and cen e
s.
De ini ion 2 Le Sbe a cubic 0-g id, and le Abe any subse o R3. The
union o all oxels wi h sampling poin s lying in Ais he digi al econs uc ion
o Awi h espec o S,ˆ
A=Ss∈(S∩A)VS(s).
This me hod o econs uc ing he objec om he se o included sampling
poin s is he 3D gene aliza ion o he 2D Gauss digi iza ion (see [21]) which has
been used by Gauss o compu e he a ea o discs and which has also been used
by Pa lidis [1] in his sampling heo em.
Fo any wo poin s pand qo S,VS(p)∩VS(q) is ei he emp y o a common
e ex, edge o ace o bo h. I VS(p)∩VS(q) is a common ace, edge, o e -
ex, hen VS(p) and VS(q) a e ace-adjacen ,edge-adjacen , o e ex-adjacen ,
espec i ely. Two oxels VS(p) and VS(q) o ˆ
Aa e connec ed in ˆ
Ai he e exis s
a sequence VS(s1), . . . , VS(sk), wi h k∈Zand k > 1, such ha s1=p,sk=q,
and si∈A(o equi alen ly, VS(si)⊂ˆ
A), o each i∈ {1, . . . , k}, and VS(sj)
and VS(sj+1) a e ace-adjacen , o each j∈ {1, . . . , k −1}. A (connec ed)
componen o ˆ
Ais a maximal se o connec ed oxels in ˆ
A.
De ini ion 3 Le Sbe a cubic 0-g id, and le Tbe any subse o S. Then
S ∈TVS( )is well-composed i ∂(S ∈TVS( )) is a su ace in R3, o equi alen ly,
i o e e y poin x∈∂(S ∈TVS( )), he e exis s a posi i e numbe such ha
he in e sec ion o ∂(S ∈TVS( )) and B0
(x)is homeomo phic o he open uni
disk in R2,D={(x, y)∈R2|x2+y2<1}.
Well-composed digi al econs uc ions can be cha ac e ized by wo local condi-
ions depending only on oxels o poin s o S. Le s1, . . . , s4be any ou poin s
o Ssuch ha T4
i=1 VS(si) is a common edge o VS(s1), . . . , VS(s4). The se
{VS(s1), . . . , VS(s4)}is an ins ance o he c i ical con igu a ion (C1) wi h e-
spec o S ∈TVS( ) i wo o hese oxels a e in S ∈TVS( ) and he o he wo
a e in (S ∈TVS( ))c, and he wo oxels in S ∈TVS( ) ( esp. (S ∈TVS( ))c) a e
edge-adjacen , as shown in Figu e 4a. Now, le s1, . . . , s8be any eigh poin s
o Ssuch ha T8
i=1 VS(si) is a common e ex o VS(s1), . . . , VS(s8). The se
{VS(s1), . . . , VS(s4)}is an ins ance o he c i ical con igu a ion (C2) wi h espec
o S ∈TVS( ) i wo o hese oxels a e in S ∈TVS( ) ( esp. (S ∈TVS( ))c) and
he o he six a e in (S ∈TVS( ))c( esp. S ∈TVS( )), and he wo oxels in
S ∈TVS( ) ( esp. (S ∈TVS( ))c) a e e ex-adjacen , as shown in Figu e 4b.
The ollowing heo em om [15] es ablishes an impo an equi alence be ween
well-composedness and he (non)exis ence o c i ical con igu a ions (C1) and
(C2).
Theo em 1 ([15]) Le Sbe a cubic 0-g id and le Tbe any subse o S. Then,
S ∈TVS( )is well-composed i he se o oxels {V(s)|s∈S}does no con ain
any ins ance o he c i ical con igu a ion (C1) no any ins ance o he c i ical
con igu a ion (C2) wi h espec o S ∈TVS( ).
7
Figu e 5: The su ace o an objec only needs o ha e an a bi a ily small, bu
nonze o cu a u e in o de o make occu ences o he c i ical con igu a ion (C1)
possible in he digi al econs uc ion
A simple consequence o he 2D digi iza ion heo em by Pa lidis [1] is ha
he econs uc ion o an 0- egula se is well-composed. The main di icul y o
3D digi iza ion as compa ed o 2D lies in he ac ha digi al econs uc ion
ˆ
Ao Awi h espec o Sis no gua an eed o be well-composed. An example
is p o ided in 5. The e o e, i is necessa y o epai ˆ
Ain o de o ensu e he
opological equi alence be ween Aand epai ed ˆ
A. The i s opology p ese ing
epai ing me hod has been p oposed in [8], whe e also he ollowing heo em is
p o en. I is an in e es ing obse a ion ha i ook 25 yea s o ob ain his 3D
heo em.
Theo em 2 ([8]) I Ais an - egula objec and Sis a cubic 0-g id wi h 2 0<
, hen he esul o he opology p ese ing epai ing o he econs uc ion ˆ
Ais
-homeomo phic o A.
4 Applica ion
A comple e unde s anding o he loss o in o ma ion due o he digi iza ion
p ocess is undamen al o he jus i ica ion o any compu e ision applica ion.
I he ele an in o ma ion is no con ained in he digi al image, he e is no way
o econs uc i wi hou using con ex knowledge. Thus, whene e one needs
o ha e gua an ees o he co ec beha io o some compu e ision algo i hm
one has o be awa e o wha happens du ing digi iza ion. This a icle gi es an
exempla y insigh o he opic, he ela ed p oblems and he way o sol e hem.
8
5 Open P oblems
The analysis o he e ec o digi iza ion o he in o ma ion being ex ac able
om an image is a challenging esea ch a ea. Newes esul s app oxima e eal
acquisi ion p ocesses and hus gi e di ec implica ions o many compu e ision
algo i hms which ely on p ecise in o ma ion o he s uc u es being app oxi-
ma ed by he digi al image. Howe e , in eali y he digi iza ion p ocess is s ill
mo e complica ed han he models which a e used o opological o geome ic
sampling heo ems. The goal is o de i e gua an ees o digi iza ion models
app oxima ing eal digi iza ion p ocesses.
Fo he case n≥3, he equi alences be ween he di e en de ini ions o
well-composedness (EWC, DWC, AWC, EWC, AGWC) is an open p oblem
oge he wi h a gene al me hod o epai ing non-well-composed digi al se s in
Zn. Besides, he s udy o which p ope ies well-composed images own in Zn
ha e lec he con inuous wo ld is a p omising line o esea ch, such as, he
link be ween c i ical poin s and Mo se heo y [23] o opological pe sis ence [24]
and ee o shapes. A mo e exhaus i e lis can be consul ed in [19, Sec ion 10].
Re e ences
[1] Pa lidis T (1982) Algo i hms o g aphics and image p ocessing. Compu e
Science P ess, Camb idge
[2] Se a J (1982) Image analysis and ma hema ical mo phology. Academic,
San Diego
[3] La ecki LJ, Con ad C, G oss A (1998) P ese ing opology by a digi iza ion
p ocess. J Ma h Imaging Vis 8:131–159
[4] La ecki LJ (1998) Disc e e ep esen a ion o spa ial objec s in compu e i-
sion. Vie ge e M (ed) Se ies on compu a ional imaging and ision. Kluwe ,
Do d ech
[5] Tajine M, Ronse C (2002) Topological p ope ies o hausdo disc e iza-
ion, and compa ison o o he disc e iza ion schemes. Theo Compu Sci
283(1):243–268
[6] S elldinge P, K¨o he U (2003) Shape p ese a ion du ing digi iza ion: igh
bounds based on he mo phing dis ance. In: Pa e n ecogni ion, DAGM
2003, Munich, pp 108–115
[7] S elldinge P, K¨o he U (2005) Towa ds a gene al sampling heo y o shape
p ese a ion. Image Vis Compu J 23(2):237–248
[8] S elldinge P, La ecki LJ, Siquei a M (2007) Topological equi alence be-
ween a 3D objec and he econs uc ion o i s digi al image. IEEE T ans
Pa e n Anal Mach In ell 29(1):126–140
9