Bounds on he quali y o econs uc ed images
in bina y omog aphy
K. Joos Ba enbu ga,c, Wagne Fo esa,b, Lajos Hajdud,e, Robe Tijdemanb
aCen um Wiskunde &In o ma ica, Science Pa k 123, 1098 XG Ams e dam, The Ne he lands
bMa hema ical Ins i u e, Leiden Uni e si y, The Ne he lands
cVision Lab, Uni e si y o An we p, Belgium
dIns i u e o Ma hema ics, Uni e si y o Deb ecen, Hunga y
eNumbe Theo y Resea ch G oup o he Hunga ian Academy o Sciences, Deb ecen, Hunga y
Abs ac
Bina y omog aphy deals wi h he p oblem o econs uc ing a bina y image om i s p ojec ions.
In pa icula , he e is a ocus on highly unde de e mined econs uc ion p oblems o which many
solu ions may exis . In such cases, i is impo an o ha e a quali y measu e o he econs uc ion
wi h espec o he unknown o iginal image.
In his a icle, we de i e a se ies o uppe bounds ha can be used o gua an ee he quali y
o a econs uc ed bina y image. The bounds limi he numbe o pixels ha can be inco ec
in he econs uc ed image wi h espec o he o iginal image. We p o ide se e al e sions o
hese bounds, anging om bounds on he di e ence be ween any wo bina y solu ions o a
omog aphy p oblem o bounds on he di e ence be ween app oxima e solu ions and he o iginal
objec . The bounds a e e alua ed expe imen ally o a ange o es images, based on simula ed
p ojec ion da a.
Keywo ds: bina y omog aphy, disc e e omog aphy, e o bounds, s abili y
1. In oduc ion
Tomog aphy is a echnique o econs uc ing an image o an objec om a se ies o p o-
jec ions o his objec , acqui ed om a ange o iewing angles. The p ojec ion images a e
ypically eco ded using a scanning de ice, which can employ a ious ypes o beams (e.g., X-
ays, neu ons, elec ons) ha a e se he objec , a e which a de ec o measu es he esul o he
beam-objec in e ac ion. P o ided ha a la ge numbe o high-quali y p ojec ions a e a ailable,
sampled om a ull ange o angles, an accu a e econs uc ion o he objec can be compu ed
using a omog aphic econs uc ion algo i hm [15, 19].
In p ac ice, he se o angles o which p ojec ions a e acqui ed is o en limi ed. Due o
dose cons ain s, i can be desi able o eco d as ew p ojec ions images as possible, while s ill
a aining su icien image quali y. Also, he angula ange can be es ic ed by he pa icula
scanning se up, such as in elec on omog aphy, whe e he shape o he sample holde limi s he
Email add esses: [email p o ec ed] (K. Joos Ba enbu g), [email p o ec ed] (Wagne Fo es),
[email p o ec ed] (Lajos Hajdu), [email p o ec ed] (Robe Tijdeman)
P ep in submi ed o Disc e e Applied Ma hema ics Sep embe 10, 2012
angula ange o he p ojec ions [20]. The esul ing image econs uc ion p oblems, based on
jus a small numbe o p ojec ions, a e known as limi ed da a p oblems.
Fo omog aphic econs uc ion om se e ely limi ed da a, classical algo i hms based on an-
aly ical in e sion o he Radon ans o m, such as he Fil e ed Backp ojec ion algo i hm, o en
yield low quali y econs uc ions ha a e pollu ed by s ong a e ac s. In such cases, i makes
sense o exploi a ailable p io knowledge o he unknown objec . Inco po a ion o his knowl-
edge in he econs uc ion algo i hm can po en ially esul in a educ ion o he equi ed numbe
o p ojec ions, inc eased accu acy o he econs uc ion, o an imp o ed abili y o deal wi h noisy
p ojec ion da a. A p io ha has ecei ed much a en ion ecen ly conce ns he spa si y o he
image, o o i s g adien , which is exploi ed in he ield o Comp essed Sensing [12, 13, 23, 24].
A ela ed, bu mo e s ic ype o p io knowledge is exploi ed in Disc e e Tomog aphy, which
ocuses on he econs uc ion o images ha consis o a small, disc e e se o g ey alues [16, 17].
The ac ual se o g ey le els is ypically assumed o be known in ad ance. He e, we ocus
speci ically on he econs uc ion o bina y images, which consis o jus wo g ey le els, 0
and 1. Se e al econs uc ion algo i hms ha e been p oposed in li e a u e o econs uc ing
bina y images om a small numbe o p ojec ions, o en e en less han 6 [5, 8, 17, 22]. These
algo i hms do no wo k well o all ypes o bina y images, ye hey ha e demons a ed he abili y
o accu a ely econs uc a ious phan om images.
Despi e he s ong cons ain imposed on he g ey alues in disc e e omog aphy, many alid
solu ions o he econs uc ion p oblem can exis , all co esponding o he same se o p ojec-
ions. I he p ojec ions a e ob ained by pe o ming measu emen s on some unknown g ound
u h objec , he econs uc ion can hen de ia e subs an ially om he ue objec . As a con-
sequence, he e is a need o an uppe bound on he di e ence be ween bina y solu ions o he
econs uc ion p oblem. As he g ound u h is a solu ion by i sel , his would also yield a bound
on he econs uc ion e o wi h espec o he g ound u h.
A ela ed p oblem in disc e e omog aphy is he so-called s abili y p oblem, which deals wi h
he ques ion o how he econs uc ion changes i he p ojec ions a e sligh ly pe u bed. Fo
images ep esen ed on a disc e e g id, bo h lowe and uppe bounds ha e been ob ained o he
magni ude o such changes [1, 2, 3, 11, 28]. Fo he case o bina y image econs uc ion om jus
wo p ojec ions, ho izon al and e ical, sha p bounds on he di e ence be ween bina y images
ha ing he same p ojec ions ha e been ob ained by Alpe s and B une i [2] and ex ended by Van
Dalen [26, 27].
In his a icle, we p esen a se ies o bounds which a e highly gene al. Ou bounds can be
compu ed o any se o p ojec ions and in di e en geome ical se ings, o la ice images as
well as disc e ized con inuous images. A key idea in de i ing hese bounds is an obse a ion
i s made by Hajdu and Tijdeman in [14], conce ning he ac ha all bina y solu ions o he
econs uc ion p oblem mus lie on a ce ain hype sphe e, o which bo h he cen e and adius
can be compu ed. The cen e o his hype sphe e, which we call he cen al econs uc ion,
is he sho es eal- alued solu ion o he omog aphy p oblem. This hype sphe e cons uc ion
leads di ec ly o a simple bound on he dis ance be ween any wo bina y solu ions, based on
he iangle inequali y. S onge bounds can be de i ed by ocusing on he dis ance be ween
bina y solu ions o he omog aphy p oblem and he bina y image ha is ob ained by ounding
he cen al econs uc ion. We de i e se e al bounds ha combine p ope ies o he eal- alued
solu ion wi h combina o ial p ope ies ha a e sa is ied by he bina y solu ions. In pa icula , he
ac ha he sum o he pixel alues in he unknown image is ully de e mined by he p ojec ion
da a can be used o imp o e he e o bounds o bina y images.
The s uc u e o his a icle is as ollows. Ou no a ion is in oduced in Sec ion 2, a e which
2
a gene al class o econs uc ion p oblems is in oduced. We hen discuss wo speci ic examples
o such p oblems, based on he g id model and s ip model o compu ing he p ojec ions. In
Sec ion 3, he cen al econs uc ion is in oduced, which plays an impo an ole in all esul s
ha ollow. We discuss wo di e en s a egies o i s compu a ion. Sec ion 4 con ains he main
esul s o his pape : a se ies o quali y bounds o bina y solu ions o he omog aphy p oblem. I
is di ided in h ee pa s: in Sec ion 4.1, a gene al bound is de i ed on he di e ence be ween wo
bina y images ha ing a gi en se o p ojec ions. Sec ion 4.2 deals wi h bounds ha a e based on
p ope ies o he bina y images ha a e ob ained by ounding he cen al econs uc ion. These
bounds a e subsequen ly e ined in Sec ion 4.3 by including he knowledge o he o al numbe
o 1’s in any bina y solu ion, which can be de e mined om he p ojec ion da a.
Sec ion 5 p esen s a se ies o simula ion expe imen s and hei esul s. F om hese esul s,
he p ac ical alue o he p oposed bounds can be e alua ed o di e en ypes o images. The
esul s a e u he discussed in Sec ion 6. Sec ion 7 concludes he pape .
This a icle is an ex ended e sion o he con e ence pape [7]. Compa ed o he con e ence
pape , se e al new bounds ha e been included in he p esen a icle, in pa icula (i) bounds on
he di e ence be ween any bina y image, no necessa ily being a solu ion o he econs uc ion
p oblem, and he unknown o iginal image, and (ii) bounds ha inco po a e knowledge o he
o al numbe o 1’s in he unknown o iginal image. Va ious o he bounds ha e also been e ined.
The expe imen al sec ion has been ex ended wi h an example, depic ing he di e en images and
concep s in ol ed in he a ious bounds. A se ies o expe imen s on bounding he e o o bina y
econs uc ions compu ed by he DART algo i hm, a heu is ic me hod ha is no gua an eed o
yield an exac solu ion [8], bu yields high quali y econs uc ions in p ac ice, is also included.
2. No a ion and model
Th oughou he disc e e omog aphy li e a u e, se e al imaging models ha e been consid-
e ed. In he g id model, an image is o med by assigning a alue o each poin in a egula g id.
In he case o bina y images, each poin is assigned a alue o ei he 0 o 1. He e, we conside
squa e g ids o he o m A={(i,j)∈Z2: 1 ≤i,j≤s} o s∈N,s≥1; see Fig. 1(a). Fo he
g id model, we e e o he poin s in Aas pixels. A bina y image de ined on Acan be ep esen ed
by a map A→ {0,1}. A p ojec ion o an image is o med by conside ing he se o pa allel
lines h ough one o mo e g id poin s in a ce ain di ec ion (a,b)∈Z2, wi h a≥0 and (a,b)
cop ime, and summing he alues o he poin s on each line. Fo a line gi en by he equa ion
ax −by = ( ∈Z), he line p ojec ion p is de ined as
p=X
(x,y)∈A:ax−by=
(x,y).
The g id model can be used o model nanoc ys als, ha consis o disc e e a oms posi ioned in a
egula g id [18, 25].
In many omog aphy applica ions, a con inuous ep esen a ion o he objec is mo e ealis ic,
as he e is no in insic g id s uc u e. In such cases, he unknown image is ypically app oxima ed
by an image de ined on a disc e e pixel g id, using squa e pixels. A common model o compu -
ing he p ojec ions o such a pixelized image is he s ip model [19, sec ion 7.4.1], [30]. In he
s ip model, a p ojec ion is compu ed by conside ing a se o pa allel s ips in a gi en di ec ion
and and o each s ip compu ing he weigh ed sum o all he pixels which in e sec ha s ip
wi h a weigh equal o he in e sec ion a ea o he s ip and he pixel.
3
(a) G id model (b) S ip model
Figu e 1: Two di e en p ojec ion models.
We now de ine some gene al no a ion. An image is ep esen ed by a ec o x=(xi)∈Rn.
We e e o he en ies o xas pixels, which co espond o uni squa es in he s ip model and o
poin s in he g id model. The de i a ion o ou main esul s does no depend on he pa icula
p ojec ion model. Th oughou his pape we assume ha all images a e squa e, consis ing o c
ows and ccolumns, whe e n=c2. A bina y image co esponds wi h a ec o ¯x∈ {0,1}n.
Fo a gi en se o kp ojec ion di ec ions, he p ojec ion map maps an image x o a ec o p∈
Rmo p ojec ion da a, whe e mdeno es he o al numbe o line measu emen s. As he p ojec ion
map is a linea ans o ma ion, i can be ep esen ed by a ma ix W=(wi j)∈Rm×n, called he
p ojec ion ma ix. En y wi j ep esen s he weigh o he con ibu ion o xj o p ojec ed line i.
No e ha o he g id model he p ojec ion ma ix is a bina y ma ix, while o he s ip model i s
en ies a e eal alues in [0,1]. The p ojec ion ma ix Wand ec o pcan be decomposed in o k
blocks as
W=











W1
.
.
.
Wk












,p=











p1
.
.
.
pk












,(1)
whe e each block Wd(d=1,...,k) ep esen s he p ojec ion map o a single di ec ion and each
block pd ep esen s he co esponding p ojec ion da a.
F om his poin on, we assume ha he p ojec ion ma ix has he p ope y ha Pm
i=1wi j =k
o all j=1,...,n. This p ope y is ce ainly sa is ied o he g id model, as e e y xjis coun ed
wi h weigh 1 o exac ly one line in each p ojec ion di ec ion. The p ope y is also sa is ied o
he s ip p ojec ion model, as he o al pixel weigh o each p ojec ion angle is equal o he a ea
o a pixel, which is 1. Fo mos o he p ojec ion models commonly used in omog aphy, such as
he line model, whe e he weigh o a pixel is de e mined by he leng h o i s in e sec ion wi h a
line, his p ope y is app oxima ely sa is ied, bu no always exac ly.
The gene al econs uc ion p oblem consis s o inding a solu ion o he sys em Wx =p
o gi en p ojec ion da a p, i.e., o ind an image ha has he gi en p ojec ions. In bina y o-
mog aphy, one seeks a bina y solu ion o he sys em. Fo a gi en p ojec ion ma ix Wand gi en
p ojec ion da a p, le SW(p)={x∈Rn:Wx =p}, he se o all eal- alued solu ions co espond-
ing wi h he p ojec ion da a, and le ¯
SW(p)=SW(p)∩ {0,1}n, he se o bina y solu ions o he
sys em. As he main goal o inco po a ing p io knowledge o he bina y g ey le els in he econ-
s uc ion is o educe he numbe o equi ed p ojec ions, we ocus on he case whe e mis small
wi h espec o n, such ha he eal- alued econs uc ion p oblem is se e ely unde de e mined.
Despi e he s ong cons ain ha each pixel alue ximus belong o he se {0,1}, he bina y
econs uc ion p oblem o en does no ha e a unique solu ion. Ins ead o posing he uniqueness
4
p oblem as a yes/no ques ion, we ocus in his pape on he numbe o di e en pixels be ween
di e en bina y solu ions. Fo example, i he econs uc ion p oblem has no unique solu ion, bu
all pai s o solu ions ha e a mos 4 di e en pixels, hen one can say ha any such solu ion mus
be close o he o iginal objec om which he p ojec ions ha e been ob ained, e en i he exac
se o di e ences canno be de e mined.
Fo any wo ec o s ¯
u,¯
∈ {0,1}n, de ine he di e ence se D(¯
u,¯
)={i: ¯ui,¯ i}and he
numbe o di e ences d(¯
u,¯
)=#D(¯
u,¯
), whe e he symbol # deno es he ca dinali y ope a o o
a ini e se . No e ha d(¯
u,¯
)=k¯
u−¯
k1.
3. The cen al econs uc ion
As he p ojec ion ma ix is ypically no a squa e ma ix, and also does no ha e ull ank, i
does no ha e an in e se. Recall ha he Moo e-Pen ose pseudo in e se o an m×nma ix Ais
an n×mma ix A†, which can be uniquely cha ac e ized by he wo geome ic condi ions
A†b⊥ N(A) and (I−AA†)b⊥ R(A) o all b∈Rm,
whe e N(A) is he nullspace o Aand R(A) is he ange o A, [10, page 15].
Le x∗=W†p. Then x∗has he p ope y (see Chap e 3 o [9]) ha i is he eal- alued
solu ion o minimal Euclidean no m o he sys em Wx =p, p o ided ha he la e sys em
is sol able. We call x∗ he cen al econs uc ion o p. The cen al econs uc ion plays an
impo an ole in he bounds we de i e o he bina y econs uc ion p oblem. We will show in
he nex sec ion ha all bina y solu ions o he sys em ha e equal dis ance o x∗, so ha one can
conside he cen al econs uc ion as lying “in he middle” o all bina y solu ions.
As all bounds p esen ed in his pape depend on x∗, accu a e compu a ion o x∗is necessa y
o compu e he co esponding di e ence bounds. One app oach o compu ing he cen al econ-
s uc ion o a consis en sys em Wx =pis o use he QR decomposi ion o WT. We will only
ske ch he compu a ion he e and e e o [4] o de ails. Fo cla i y o p esen a ion, we assume
ha Whas ull ow ank. In ac , his assump ion is no sa is ied o omog aphy, and he ex-
ended QR decomposi ion should be used. The QR decomposi ion ac o izes he ma ix WTin o
an o hogonal ma ix Qand an uppe iangula ma ix Ro ull column ank, as
WT=Q R
0!.
The cen al econs uc ion is hen gi en by x∗=Q(RT)−1p, which can be compu ed e icien ly
by i s sol ing he sys em RTy=p o yby back subs i u ion, and hen compu ing x∗=Qy.
Howe e , due o he size o he ma ix W, calcula ion o he QR decomposi ion is usually un-
p ac ical o la ge images. Fo he case m<n, he QR decomposi ion equi es O(n3) ope a ions.
Mo eo e , he n×nma ix Qis ypically dense, equi ing a as amoun o compu e memo y. As
an al e na i e, an i e a i e me hod o sol ing he sys em Wx =p, called CGLS (Conjuga e G a-
dien Leas Squa es), can be used [21]. The CGLS algo i hm can e ec i ely exploi he spa se
s uc u e o he p ojec ion ma ix o educe he equi ed compu a ion ime, and does no equi e
s o age o la ge, dense ma ices. Apa om nume ical e o s, applying CGLS o he sys em
Wx =p esul s, a e con e gence, in he compu a ion o W†p, while no compu ing he ma ix
W†explici ly (see also [29]). Fo all expe imen s in Sec ion 5, he ime equi ed o compu e he
cen al econs uc ion a ied om a ew seconds up o wo minu es on a s anda d PC, depending
on he numbe o p ojec ions and image size.
5

4. Quali y bounds o bina y solu ions
In all he esul s in he ollowing subsec ions, we conside a ixed sys em Wx =pco e-
sponding o a bina y omog aphy p oblem, and e e o he cen al econs uc ion o his sys em
as x∗.
As a subs an ial numbe o bounds will be gi en h oughou his pape , we in oduce he
ollowing no a ion ha will be u he de ined in he emainde o he pape :
•The exp essions a(i) (i=1,2,3,4) will ep esen bounds on he numbe o pixel di e ences
be ween any wo bina y solu ions o he econs uc ion p oblem.
•The exp essions b(i) (i=1,2,3,4) will ep esen bounds on he numbe o pixel di e ence
be ween a ce ain gi en bina y image (no necessa ily a solu ion) and any bina y solu ion
o he econs uc ion p oblem.
•The exp essions c(i) (i=1,2) will ep esen bounds on he numbe o pixel di e ences
be ween he ounded cen al econs uc ion ¯
and any bina y solu ion.
The bounds wi hin each class a,b, and c ep esen uppe bounds o he same dis ance measu e
and can he e o e be compa ed.
4.1. Elemen a y bounds based on he cen al econs uc ion
In his subsec ion, a i s se o bounds a e de i ed. They ollow om he ac ha he Eu-
clidean dis ance be ween he cen al econs uc ion and any bina y solu ion o he econs uc ion
p oblem can be de e mined om he p ojec ions. We s a by no icing ha he Euclidean no m
o any bina y solu ion o he omog aphy p oblem is de e mined by he p ojec ion da a:
Lemma 1. Le ¯
x∈¯
SW(p). Then, k¯
xk2
2=kpk1
k.
P oo . By he de ini ion o he `1-no m, kpk1=Pm
i=1|pi|=Pm
i=1pi, since pi≥0 (i=1,...,n).
Also,
m
X
i=1
pi=
m
X
i=1







n
X
j=1
wi j ¯xj







=
n
X
j=1






m
X
i=1
wi j





¯xj=
n
X
j=1
k¯xj,(2)
and he e o e kpk1=kPn
j=1¯xj.
As ¯
x∈ {0,1}n, we ha e k¯
xk2
2=k¯
xk1=Pn
j=1¯xj=kpk1
k.
The ollowing lemma illus a es he impo ance o he cen al econs uc ion, he sho es
eal- alued solu ion in SW(p), by showing ha he bina y solu ions a e he sho es among all
in ege solu ions o he sys em.
Lemma 2. Le ¯
x∈¯
SW(p)and y∈SW(p)∩Zn. Then k¯
xk2≤ kyk2, wi h equali y i and only i
y∈¯
SW(p).
P oo . No e ha he s a emen is p o ed in [14], see P oblem 2 and he subsequen pa ag aph.
Howe e , o he con enience o he eade we gi e he p oo he e.
We ha e
|| ¯
x||2
2=
n
X
i=1
¯x2
i=
n
X
i=1
¯xi=
n
X
i=1
yi=kpk1
k.(3)
6
Obse ing ha
n
X
i=1
yi≤
n
X
i=1
y2
i=||y||2
2,(4)
wi h equali y i and only i yis bina y, yields he esul .
Lemma 3. Le ¯
x∈¯
SW(p). Then k¯
x−x∗k2=qkpk1
k− kx∗k2
2.
P oo . F om he de ini ion o x∗we ha e (¯
x−x∗)∈ N(W), and x∗⊥(¯
x−x∗). Applying
Py hago as’ Theo em and Lemma 1 yields
k¯
x−x∗k2
2=kpk1
k− kx∗k2
2.(5)
De ine R=qkpk1
k− kx∗k2
2. We will use his cons an h oughou he emainde o his a -
icle, and e e o Ras he cen al adius. Acco ding o Lemma 3, any bina y solu ion o he
econs uc ion p oblem is on he hype sphe e cen e ed in x∗wi h adius R.
Supposing he exis ence o a leas wo di e en bina y solu ions, Lemma 3 allows us o
de i e an uppe bound o he numbe o pixel di e ences be ween hose solu ions.
Theo em 4. Le ¯
x,¯
y∈¯
SW(p)and pu a(1) =4R2. Then d(¯
x,¯
y)≤a(1).
P oo . Acco ding o Lemma 3, we ha e k¯
x−x∗k2=k¯
y−x∗k2=R. The e o e,
k¯
x−¯
yk2≤ k ¯
x−x∗k2+k¯
y−x∗k2=2R.
As ¯
xand ¯
ya e bina y, we ha e d(¯
x,¯
y)=k¯
x−¯
yk1=k¯
x−¯
yk2
2.
Using he iangle inequali y, a simple bound can also be gi en o he dis ance be ween any
bina y image and a solu ion o he econs uc ion p oblem, as ollows:
Co olla y 5. Le ¯
∈ {0,1}nbe a gi en bina y image and pu b(1) =(R+k¯
−x∗k2)2. Then o
any bina y image ¯
x∈¯
SW(p), we ha e d(¯
x,¯
)≤b(1).
4.2. Bounds based on ounding he cen al econs uc ion
The ac ha all elemen s o ¯
SW(p) ha e equal dis ance o he cen al econs uc ion x∗, com-
bined wi h he ac s ha bina y solu ions a e he sho es solu ions among all in ege solu ions
(Lemma 2) and ha x∗is he sho es eal- alued solu ion, sugges s ha bina y solu ions can
o en be ound nea x∗. I is he e o e na u al o conside he image ha is ob ained by ound-
ing each en y o x∗ o he nea es bina y alue. In his sec ion, we will de i e se e al bounds
based on he numbe o di e ences be ween a bina y solu ion o he econs uc ion p oblem and
a bina y image ob ained by ounding x∗.
Fo α∈R, le bin(α)=min(|α|,|1−α|). Pu T=qPn
i=1bin2(x∗
i), i.e., he Euclidean dis ance
om x∗ o he nea es bina y ec o . We will use his cons an h oughou his pape and e e o
Tas he cen al ounding dis ance.
7
Co olla y 6. I R <T, hen ¯
SW(p)=∅.
I R =T, hen all solu ions in ¯
SW(p)can be ob ained by ounding he alues in x∗ o he
nea es bina y alues, and a ia ions a e only possible o he en ies i whe e x∗
i=1
2.
Le T={¯
∈ {0,1}n:k¯
−x∗k2=T}and le ¯
∈ T , i.e., ¯
is among he bina y ec o s ha
a e nea es o x∗in he Euclidean sense.
I R>Tand R−Tis small, i is possible o say ha a ac ion o he ounded alues a e
co ec , i.e., o p o ide an uppe bound on he numbe o pixel di e ences be ween any solu ion
in ¯
SW(p) and ¯
. In mos cases we can no say which ounded alues a e co ec .
Lemma 7. Le ¯
∈ T and le ¯
∈ {0,1}nbe any bina y ec o .
Then k¯
−x∗k2
2=T2+Pi∈D(¯
,¯
)|2x∗
i−1|.
P oo . We ha e he ollowing iden i ies:
k¯
−x∗k2
2=k¯
−¯
+¯
−x∗k2
2
=k¯
−x∗k2
2+2h¯
−x∗,¯
−¯
i+h¯
−¯
,¯
−¯
i
=T2+2h¯
−¯
,x∗i+k¯
k2
2− k¯
k2
2
=T2+2
n
X
i=1
(¯ i−¯ i)x∗
i+
n
X
i=1
¯ i−
n
X
i=1
¯ i
=T2+
n
X
i=1
(¯ i−¯ i)(2x∗
i−1)
=T2+X
i∈D(¯
,¯
)
|2x∗
i−1|.
Lemma 7 can be in e p e ed as ollows: conside he se o en ies whe e ¯
and ¯
a e di e en .
I we ans o m ¯
in o ¯
by pe o ming a sequence o single-en y changes (ei he om 0 o 1, o
om 1 o 0), each ime an en y io ¯
is changed he squa ed Euclidean dis ance om he cu en
ec o o x∗inc eases by si=|2x∗
i−1|.
Le πbe a pe mu a ion o {1,...,n}such ha sπ(1) ≤sπ(2) ≤. . . ≤sπ(n), which can be ob ained
by so ing he en ies siin inc easing o de .
Co olla y 8. Le ¯
∈ T and le ¯
∈ {0,1}nbe any bina y ec o . Then k¯
−x∗k2
2≥T2+P`
i=1sπ(i),
whe e `=d(¯
,¯
).
P oo . Acco ding o Lemma 7 we ha e
k¯
−x∗k2
2=T2+X
i∈D(¯
,¯
)
si≥T2+
`
X
i=1
sπ(i).
As he Euclidean dis ance om x∗ o any ¯
x∈¯
SW(p) is R, a bound can now be de i ed on he
maximal numbe o pixels in ¯
ha mus be changed o mo e om ¯
o ¯
x.
8
Theo em 9. Le ¯
∈ T ,¯
x∈¯
SW(p). Pu
c(1) =max 






0≤`≤n:
`
X
i=1
sπ(i)≤R2−T2






.
Then d(¯
x,¯
)≤c(1).
P oo . As ¯
x∈¯
SW(p), we ha e k¯
x−x∗k2
2=R2.Applying Lemma 7, we ind ha
R2−T2=X
i∈D(¯
x,¯
)
si≥
d(¯
x,¯
)
X
i=1
sπ(i),
which implies ha d(¯
x,¯
)≤c(1).
The p oo o Theo em 9 can be in e p e ed as ollows: conside he se o en ies whe e ¯
and ¯
xa e di e en . I we ans o m ¯
in o ¯
xby pe o ming a sequence o single-en y changes
(ei he om 0 o 1, o om 1 o 0), each ime an en y io ¯
is changed he squa ed Euclidean
dis ance om he cu en ec o o x∗inc eases by si=|2x∗
i−1|. As all bina y solu ions o he
econs uc ion p oblem a e on a hype sphe e cen e ed in x∗wi h adius R, we know ha once we
ha e c ossed he bounda y o his hype sphe e, a bina y solu ion can no longe be ob ained by
changing he alues o addi ional en ies ha ha e no ye been changed. An uppe bound on he
numbe o di e ences be ween ¯
and ¯
xcan be ob ained by coun ing he numbe o s eps equi ed
o c oss he hype sphe e, each ime choosing a pixel which esul s in he minimal inc ease o he
dis ance o x∗. The ollowing wo Co olla ies ollow di ec ly om Theo em 9:
Co olla y 10. Le ¯
∈ T ,¯
x,¯
y∈¯
SW(p)and le a(2) =2c(1) wi h c(1) de ined as in Theo em 9.
Then d(¯
x,¯
y)≤a(2).
Co olla y 11. Le ¯
∈ T and le ¯
∈ {0,1}nbe a gi en bina y image and le b(2) =c(1) +d(¯
,¯
)
wi h c(1) de ined as in Theo em 9. Then d(¯
x,¯
)≤b(2).
In ac , he bound om Co olla y 10 can be sha pened by no ing ha we can assume ha
he se s D(¯
,¯
x) and D(¯
,¯
y) a e disjoin , as en ies ha occu in bo h se s do no con ibu e o he
numbe o di e ences be ween ¯
xand ¯
y. This obse a ion leads o he ollowing Theo em:
Theo em 12. Le ¯
∈ T ,¯
x,¯
y∈¯
SW(p). Pu
a(3) =max 






0≤`≤n:
`
X
i=1
sπ(i)≤2(R2−T2)






.
Then d(¯
x,¯
y)≤a(3).
P oo . De ine ˆ
xby ˆxi=¯ ii ¯xi=¯yi, and ˆxi=¯xio he wise. De ine ˆ
yanalogously. Then
d(ˆ
x,ˆ
y)=d(¯
x,¯
y), kˆ
x−x∗k2
2≤R2, and kˆ
y−y∗k2
2≤R2. Hence, 2R2≥ k ˆ
x−x∗k2
2+kˆ
y−y∗k2
2=2T2+
Pi∈D(¯
,ˆ
x)si+Pi∈D(¯
,ˆ
y)si.As D(¯
,ˆ
x) and D(¯
,ˆ
y) a e disjoin , we ha e 2R2−2T2≥Pd(¯
,ˆ
x)+d(¯
,ˆ
y)
i=1sπ(i).
This implies ha d(¯
x,¯
y)=d(ˆ
x,ˆ
y)≤d(¯
,ˆ
x)+d(¯
,ˆ
y)≤a(3).
A simila bound can be de i ed o he case whe e a pa icula bina y image ¯
, no neces-
sa ily a solu ion o he omog aphy p oblem, is gi en. Fo his, we ans o m ¯
in o ¯
and hen
we pe o m a sequence o single-en y changes in ¯
wi h he exclusion o he pixels ha di e
be ween ¯
and ¯
because hey ha e al eady been coun ed as w ong pixels o ¯
.
9
w ong wi h espec o he unknown phan om image.
6. Discussion o he esul s
Despi e he ac s ha he ou phan oms ha e s ong di e ences in shape and mo phology, and
ha he g id and s ip models a e qui e di e en , he esul s shown in Figs. 6–9 a e su p isingly
consis en h oughou all expe imen s. Mos o he bounds become smalle as he numbe o
p ojec ion di ec ions is inc eased bu mono onici y is no a p ope y o all he bounds p esen ed
in Sec ion 4.
F om he di e ence be ween he bounds p esen ed in Sec ion 4.1 and he bounds based on he
ounded cen al econs uc ion, we see ha in mos cases he phan om ¯
xis subs an ially close o
¯
han o x∗.
In Figs. 6 and 8, i can be obse ed ha he ue ac ion o pixel di e ences be ween he
phan om image ¯
xand he ounded cen al econs uc ion ¯
, deno ed by Ec, is o en app oxima ed
qui e well by he bound c, in pa icula o he g id model. This indica es ha wi h espec o ¯
,
he bounds p esen ed in his a icle can be qui e sha p.
In Fig. 8(a), pa s o he g aphs o he bounds aand c, o mo e han 6 p ojec ions, a e
missing. In ac , in his case all o hem a e ze o, such ha hey canno be displayed in he
loga i hmic scale. This illus a es ha ou heo ems o bounding he dis ance be ween any wo
bina y solu ions can be used o p o e uniqueness o a bina y solu ion, e en when he co espond-
ing eal- alued sys em o equa ions is unde de e mined.
In mos o he expe imen s, he g aphs o a(2) and a(4) a e almos indis inguishable and he
bound a(3) is smalle han a(4) bu i can happen, as in Fig. 9(a), ha his is no he case. In
Fig. 9(a) he bound a(4) p o es uniqueness om 6 p ojec ion di ec ions o mo e while he bound
a(3) does no o 12, 14 and 16 p ojec ions. Al hough a(3) is he sha pes bound in mos o he
expe imen s, his is no ue in gene al and all bounds should be used o ob ain he bes esul .
The bounds a(2), a(3) and a(4) use simila p inciples and hei compu a ion can be pe o med
simul aneously.
7. Ou look and conclusions
In his a icle, we ha e p esen ed a ange o gene al bounds on he accu acy o econs uc-
ions in bina y omog aphy, wi h espec o he unknown o iginal objec . The bounds can be
compu ed wi hin easonable ime and gi e gua an ees on he numbe o pixels ha can be di -
e en be ween any wo bina y solu ions o he omog aphy p oblem, on he di e ence be ween
an image ob ained by ounding he cen al econs uc ion and any bina y solu ion, and on he
di e ence be ween any bina y image and any bina y solu ion. The expe imen al esul s show
ha by using hese bounds, one can p o e ha he numbe o di e ences be ween bina y econ-
s uc ions mus be e y small, e en when he co esponding eal- alued sys em o equa ions is
se e ely unde de e mined. In o de o make hese bound p ac ically use ul, ou esul s will ha e
o be ex ended o deal wi h noisy p ojec ion da a, which we will inco po a e in u u e esea ch.
Acknowledgemen s
L.H. was suppo ed by he OTKA g an s K67580 and K75566, and by he T ´
AMOP 4.2.1./B-
09/1/KONV-2010-0007 p ojec . The p ojec is implemen ed h ough he New Hunga y De el-
16

opmen Plan, co inanced by he Eu opean Social Fund and he Eu opean Regional De elop-
men Fund. W.F. acknowledges suppo om he E asmus Mundus p og am o he Eu opean
Union. K.J.B. was suppo ed by he Ne he lands O ganisa ion o Scien i ic Resea ch (NWO),
p og amme 639.072.005.
[1] Alpe s, A., 2003. Ins abili y and S abili y in Disc e e Tomog aphy. Ph.D. hesis. Technische Uni e si ¨
a M¨
unchen.
Shake Ve lag, ISBN 3-8322-2355-X.
[2] Alpe s, A., B une i, S., 2007. S abili y esul s o he econs uc ion o bina y pic u es om wo p ojec ions. Image
and Vision Compu ing 25, 1599–1608.
[3] Alpe s, A., G i zmann, P., 2006. On s abili y, e o co ec ion, and noise compensa ion in disc e e omog aphy.
SIAM Jou nal on Disc e e Ma hema ics 20, 227–239.
[4] Ba enbu g, K.J., 2003. Analysis and op imiza ion o an algo i hm o disc e e omog aphy. Elec . No es Disc e e
Ma h. 12, 35–46.
[5] Ba enbu g, K.J., 2008. A ne wo k low algo i hm o econs uc ing bina y images om con inuous X- ays. J.
Ma h. Im. Vision 30, 231–248.
[6] Ba enbu g, K.J., Bals, S., Sijbe s, J., K¨
ubel, C., Midgley, P.A., He nandez, J.C., Kaise , U., Encina, E.R., Co onado,
E.A., Van Tendeloo, G., 2009. 3D imaging o nanoma e ials by disc e e omog aphy. Ul amic oscopy 109, 730–
740.
[7] Ba enbu g, K.J., Fo es, W., Hajdu, L., Tijdeman, R., 2011. Bounds on he di e ence be ween econs uc ions in
bina y omog aphy, in: P oceedings o he 16 h IAPR in e na ional con e ence on Disc e e geome y o compu e
image y, Sp inge -Ve lag, Be lin, Heidelbe g. pp. 369–380.
[8] Ba enbu g, K.J., Sijbe s, J., 2011. DART: a p ac ical econs uc ion algo i hm o disc e e omog aphy. IEEE
T ans. Image P ocessing 20, 2542–2553.
[9] Ben-is ael, A., G e ille, T.N.E., 2002. Gene alized in e ses: Theo y and applica ions. Canadian Ma h. Soc.
[10] Bj¨
o ck, Å., 1996. Nume ical me hods o leas squa e p oblems. SIAM, Link¨
oping Uni e si y, Sweden.
[11] B une i, S., Dau a , A., 2005. S abili y in Disc e e Tomog aphy: some posi i e esul s. Disc e e Appl. Ma h. 147,
207–226.
[12] Chen, G.H., Tang, J., Leng, S., 2008. P io image cons ained comp essed sensing (PICCS): A me hod o accu a ely
econs uc dynamic CT images om highly unde sampled p ojec ion da a se s. Medical Physics 35, 660–663.
[13] Donoho, D., 2006. Comp essed sensing. IEEE T ans. In o ma ion Theo y 52, 1289–1306.
[14] Hajdu, L., Tijdeman, R., 2001. Algeb aic aspec s o disc e e omog aphy. J. Reine Angew. Ma h. 534, 119–128.
[15] He man, G.T., 2009. Fundamen als o Compu e ized Tomog aphy: Image econs uc ion om p ojec ions.
Sp inge .
[16] He man, G.T., Kuba, A. (Eds.), 1999. Disc e e Tomog aphy: Founda ions, Algo i hms and Applica ions.
Bi kh¨
ause , Bos on.
[17] He man, G.T., Kuba, A. (Eds.), 2007. Ad ances in Disc e e Tomog aphy and i s Applica ions. Bi kh¨
ause , Bos on.
[18] Jinschek, J.R., Ba enbu g, K.J., Calde on, H.A., Kilaas, R., Radmilo ic, V., Kisielowski, C., 2007. 3-D econ-
s uc ion o he a omic posi ions in a simula ed gold nanoc ys al based on disc e e omog aphy. Ul amic oscopy
108(6), 589–604.
[19] Kak, A.C., Slaney, M., 2001. P inciples o Compu e ized Tomog aphic Imaging. SIAM.
[20] Midgley, P.A., Dunin-Bo kowski, R.E., 2009. Elec on omog aphy and holog aphy in ma e ials science. Na u e
Ma e ials 8, 271–280.
[21] Saad, Y., 2003. I e a i e Me hods o Spa se Linea Sys ems. SIAM, Philadelphia, PA, USA.
[22] Sch¨
ule, T., Schn¨
o , C., Webe , S., Ho negge , J., 2005. Disc e e omog aphy by con ex-conca e egula iza ion
and D.C. p og amming. Disc . Appl. Ma h 151, 229–243.
[23] Sidky, E.Y., Anas asio, M.A., Pan, X., 2010. Image econs uc ion exploi ing objec spa si y in bounda y-enhanced
X- ay phase-con as omog aphy. Op ics Exp ess 18, 10404–10422.
[24] Sidky, E.Y., Kao, C.M., Pan, X., 2006. Accu a e image econs uc ion om ew- iews and limi ed-angle da a in
di e gen -beam CT. J. X- ay Sci. Tech. 14, 119–139.
[25] Van Ae , S., Ba enbu g, K.J., Rossell, M.D., E ni, R., Van Tendeloo, G., 2011. Th ee-dimensional a omic imaging
o c ys alline nanopa icles. Na u e 470, 374–377.
[26] Van Dalen, B., 2009a. On he di e ence be ween solu ions o disc e e omog aphy p oblems. Jou nal o Combina-
o ics and Numbe Theo y 1, 15–29.
[27] Van Dalen, B., 2009b. On he di e ence be ween solu ions o disc e e omog aphy p oblems II. Pu e Ma hema ics
and Applica ions 20, 103–112.
[28] Van Dalen, B., 2009c. S abili y esul s o uniquely de e mined se s om wo di ec ions in disc e e omog aphy.
Disc e e Ma hema ics 309, 3905–3916.
[29] Van de Sluis, A., Van de Vo s , H.A., 1990. SIRT and CG- ype me hods o he i e a i e solu ion o spa se linea
leas -squa es p oblems. Linea Algeb a Appl. 130, 257–302.
17
[30] Zhua, J., Li, X., Ye, Y., Wang, G., 2008. Analysis on he s ip-based p ojec ion model o disc e e omog aphy.
Disc e e Appl. Ma h. 156, 2359–2367.
1234567
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(a) Phan om 1, 32×32
0 5 10 15 20 25 30
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a
c
Ec
(b) Phan om 1, 128×128
0 50 100 150 200
10−6
10−5
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a
c
Ec
(c) Phan om 1, 512×512
0 2 4 6 8 10 12
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(d) Phan om 2, 32×32
0 10 20 30 40 50 60
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(e) Phan om 2, 128×128
0 50 100 150 200
10−5
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a
c
Ec
( ) Phan om 2, 512×512
0 5 10 15
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(g) Phan om 3, 32×32
0 10 20 30 40 50 60
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(h) Phan om 3, 128×128
0 50 100 150 200
10−6
10−4
10−2
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(i) Phan om 3, 512×512
0 5 10 15
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(j) Phan om 4, 32×32
0 20 40 60 80
10−5
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(k) Phan om 4, 128×128
0 50 100 150 200
10−6
10−4
10−2
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(l) Phan om 4, 512×512
Figu e 6: G id model: compu ed bounds as a unc ion o he numbe o p ojec ion di ec ions.
18
0 5 10 15 20
10−3
10−2
10−1
100
101
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(a) Phan om 1, 32×32
0 20 40 60 80
10−5
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(b) Phan om 1, 128×128
0 50 100 150 200
10−5
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(c) Phan om 1, 512×512
0 5 10 15 20
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(d) Phan om 2, 32×32
0 20 40 60 80
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(e) Phan om 2, 128×128
0 50 100 150 200
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
( ) Phan om 2, 512×512
0 5 10 15 20
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(g) Phan om 3, 32×32
0 20 40 60 80
10−5
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(h) Phan om 3, 128×128
0 50 100 150 200
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(i) Phan om 3, 512×512
0 5 10 15 20
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(j) Phan om 4, 32×32
0 20 40 60 80
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(k) Phan om 4, 128×128
0 50 100 150 200
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(l) Phan om 4, 512×512
Figu e 7: G id model: compu ed bounds as a unc ion o he numbe o p ojec ion di ec ions. No e ha he g aphs o
a(2) and a(4) ha e s ong o e lap and can ha dly be dis inguished.
19
0 2 4 6 8
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(a) Phan om 1, 32×32
0 20 40 60 80
10−5
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a
c
Ec
(b) Phan om 1, 128×128
0 50 100 150 200
10−6
10−5
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a
c
Ec
(c) Phan om 1, 512×512
0 5 10 15 20
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(d) Phan om 4, 32×32
0 20 40 60 80
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
(e) Phan om 4, 128×128
0 50 100 150 200
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a
c
Ec
( ) Phan om 4, 512×512
Figu e 8: S ip model: compu ed bounds as a unc ion o he numbe o p ojec ion di ec ions o Phan oms 1 and 4.
0 5 10 15 20
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(a) Phan om 1, 32×32
0 20 40 60 80
10−4
10−3
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(b) Phan om 1, 128×128
0 50 100 150 200
10−4
10−3
10−2
10−1
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(c) Phan om 1, 512×512
0 5 10 15 20
10−0.7
10−0.5
10−0.3
10−0.1
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(d) Phan om 4, 32×32
0 20 40 60 80
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
(e) Phan om 4, 128×128
0 50 100 150 200
10−2
10−1
100
Numbe o angles
F ac ion o pixels
a(1)
a(2)
a(3)
a(4)
( ) Phan om 4, 512×512
Figu e 9: S ip model: compu ed bounds as a unc ion o he numbe o p ojec ion di ec ions o Phan oms 1 and 4. No e
ha he g aphs o a(2) and a(4) ha e s ong o e lap and can ha dly be dis inguished.
20