3D RECONSTRUCTION FROM A
VASCULAR TREE MODEL
Luis ´
Al a ez, Ka ina Ba˜nos, Ca melo Cuenca, Julio Escla ´ın, and Ja ie
S´anchez
Compu e Science Depa men
Las Palmas Uni e si y, Las Palmas 35017 SPAIN
{lal a ez, kba~nos, ccuenca, jescla in, jsanchez}@dis.ulpgc.es,
WWW home page: h p://se dis.dis.ulpgc.es/ lal a ez/ami/index.h ml
Resumen In his pape , we p esen a ascula ee model made wi h
syn he ic ma e ials and which allows us o ob ain images o make a 3D
econs uc ion. We ha e used PVC ubes o se e al diame e s and leng hs
ha will le us e alua e he accu acy o ou 3D econs uc ion. In o de
o calib a e he came a we ha e used a co ne de ec o . Also we ha e
used Op ical Flow echniques o ollow he poin s h ough he images
going and going back. We desc ibe wo gene al echniques o ex ac a
sequence o co esponding poin s om mul iple iews o an objec . The
esul ing sequence o poin s will be used la e o econs uc a se o 3D
poin s ep esen ing he objec su aces on he scene. We ha e made he
3D econs uc ion choosing by chance a couple o images and we ha e
calcula ed he p ojec ion e o . A e se e al epe i ions, we ha e ound
he bes 3D loca ion o he poin .
1. In oduc ion
Gi en he di icul ies o ob ain medical images in good condi ions, due o
hei p i acy and di e se echnical p oblems ha hese can p esen , such as:
a i ac s, occlusions, poo de ini ion o he image, e c; we ha e de eloped a model
o ascula ee using PVC.
This way we can ob ain a se ies o images ollowing he same echnology o
a o a ional angiog aphy, planning an a ch o ixed adius abou he model and
ob aining he images wi h an angula sepa a ion o abou 3 deg ees. Once ob ai-
ned, hey we e manipula ed in o de ha he inal esul is as simila as possible
o he angiog aphies, bu wi hou he p oblems p e iously men ioned. Besides,
by ha ing he 3D model i is possible o es he quali y o he esul s ob ained,
knowing exac alues such as: dis ances be ween bi u ca ions, he diame e s o
he glasses, e c; which will allow us o know he kindness o ou esul s.
2. Ob aining he images
We wan o econs uc images o apply in he Ro a ional Angiog aphy ield
ha i has he nex ea u es:
II
The se ies o images in Ro a ional Angiog aphy is acqui ed while he imaging
assembly o a es in a con inuous a c a ound he pa ien . The whole acquisi ion
is a he as , so ha he comple e se ies can be acqui ed wi h a single injec ion
o con as agen .
The quali y o he indi idual images is gene ally ully adequa e o diagnosis,
wi h he ollowing added ad an ages: wide ange o p ojec ions, op imum iews
o ascula s uc u es.
Fo he 3D econs uc ion, i is essen ial o he images o p ecisely ma ch
each o he . This equi es an ex emely s able and ep oducible image geome y.
The sys em is calib a ed o compensa e o dis o ion in he image in ensi ie
such us pincushion and he a ying dis o ion caused by mo emen h ough he
magne ic ield o he ea h.
The images a e acqui ed in he o a ional angiog aphy mode o e an angle
o 180 deg ees. The un maybe ca ied ou in one o h ee di e en angula ions:
-30 deg ees c anial, 0 deg ees axial, 30 deg ees caudal. Images a e acqui ed a a
ames a e o 12.5 ames by seconds, and a o a ion speed o up o 30 deg ees
pe second, he whole acquisi ion akes 8 seconds esul ing in an a e age o 100
images pe un.
We ha e made he images wi h an angle o 3.6 deg ees and app oxima ely
h ee me e s o dis ance om he model using a o 70 mm ocal dis ance wi h
a digi al came a and because he cha ac e is ics o i s digi ize hen we ha e a
ocal dis ance 105 mm wi h an a c o 270 deg ees ha allows a ound 70 images.
We ha e also ob ained images o a calib a o in o de o ob ain he in insic
pa ame e s o he came a.
3. Mul iscale Analisis and Calib a ion Came a
One o he main concep s o ision heo y and image analysis is mul iscale
analysis. A Mul iscale Analysis T associa es, wi h an o iginal image u(0) = u0a
sequence o smoo hed images u( , x, y) which depend upon an abs ac pa ame e
>0, he scale.
(x, y)−→ u( , x, y)u(0, x, y) = (x, y)
The da um o u0(x, y) is no absolu e in pe cep ion heo y, bu can be con-
side ed as he elemen o an equi alence class. I A is any a ine map o he
plane, u0(x, y) and u0(A(x, y)) can be assumed equi alen om a pe cep ual
poin o iew. Las bu no leas , he obse a ion o u0(x, y) does no gene ally
gi e any eliable in o ma ion abou he numbe o pho ons sen by any isible
place o he op ical senso . The e o e, he equi alence class in conside a ion will
be g(u0(A(x, y))), whe e g s ands o any con as unc ion depending on he
senso . These conside a ions lead us o ocus on he only mul iscale analyses
which sa is ies hese in a iance equi emen s : The A ine Mo phological Sca-
le Space (AMSS). This mul iscale analyses can be de ined by a simple Pa ial
Di e en ial Equa ion:
III
Figu a 1. Acqui ed images.
u = 1
3(u2
yuxx −2uxuyuxy +u2
xuyy)1
3
whe e u( ,x,y) deno es he image analyzed a he scale and he poin (x,y).
In o de o calib a e a came a sys em we need o co ne de ec ion and his
is e y sensi i e o noise. The AMSS mul iscale analysis p esen he ad an age
ha we know, analy ically, he displacemen o he co ne loca ion ac oss he
scales. Then we can sea ch i in a he scale n= 0+n∆ , o n=1,..,N, whe e
U ep esen s he disc e iza ion s ep o he scale and 0 ep esen s he ini ial
scale ha we use o begin o look o co ne s.
We compu e o he scale 0 he loca ion o he ex eme o he cu a u e ha
we deno e by (xi
0, yi
0) , o i=1,.., M, hese poin s ep esen he ini ial candida es
o be co ne s. We ollow ac oss he loca ion (xi
n, yi
n) o he cu a u e ex eme.
Fo each sequence (xi
n, yi
n) n=1,..,N, we compu e in a obus way(using o -
hogonal eg ession and elimina ing ou lie s) he bes line which i he sequence
o poin s, his line co esponds o he bisec o line o he co ne , and we can
ep esen i as a s aigh line which equa ion:
(x( ), y( )) = (X0, Y0) + an(α
2)−1
2 (bx, by)
whe e αis he angle o he co ne and −→
b= (bx, by), is he uni ec o in he
di ec ion o he bisec o line o he co ne , and is he scale. Then we can ind
he co ne doing = 0 in his equa ion.
IV
In o de o calib a e he came as sys em, we ex ac he cha ac e is ics o
he sequence o iews wi h a mo phologic co ne de ec o . This de ec o gi es us
sub pixel in o ma ion. When he iews a e aken om e y close posi ions, he
con en ional me hods o calib a ion can be uns able, o sol e his p oblem we
di ide he sequences o iews in o se e al sub sequences (in his way he op ical
cen e displacemen s a e bigge ). Now, we calib a e e e y subsequence o iew
in an independen way.
In he las s ep, we make he calib a ion be ween he di e en sub sequences
o ob ain only one calib a ion. The me hod we ha e used is e y s able, e en
when he e a e noise and small displacemen s be ween he op ical cen es.
x
wo ld
y
wo ld
z
wo ld
x
2
y
2
x
0
y
0
z
2
z
0
x
1
y
1
z
1
M
j
m
2j
m
0j
m
1j
C
0
C
1
C
2
O
wo ld
O
0
O
1
O
2
Figu a 2. Mo ion pa ame e s de i ed om poin ma ches.
4. Op ical Flow
Once we ha e calib a ed he came a sys em we p opose a me hod o he
eco e ing o dispa i y maps be ween pai o s e eoscopic images. Dispa i y maps
a e ob ained h ough a ma ching p ocess in whe e we ha e o ind o he pixels in
he le image hei co esponden on he igh image. The e a e some me hods,
like co ela ion-based echniques, ha es ima e good ma ching poin s bu do
no gene a e smoo h dispa i y maps o he whole image, so he solu ions in his
case a e no con inuous.
To imp o e he accu acy o he ma ching p ocess we make use o he so-called
epipola geome y. This geome y ep esen s he ela ion ha exis s be ween
s e eoscopic images. Thanks o his geome y, he me hod is able o look o
co espondences in s aigh lines only.
V

0)','(
=
yxR
e
m=(x,y)
m’=(x’,y’)
),( yx
λ
Figu a 3. Displacemen unc ion is pa ame e ized in o de o ake ad- an age o he
in o ma ion gi en by he epipola geome y.
The me hod we p opose o he compu a ion o dispa i y maps is based on
an en-e gy minimiza ion app oach:
E(λ) = Z(I(−→
x)−I0(−→
x+−→
h(λ)))2+Z5λD(5I)5λ
Whe e Iand I0a e he s e eoscopic images,λis a pa ame e ha gi es us
he dis ance be ween he poin ha i is he p ojec ion o m o e he i epipola
s aigh line and he esponsi e poin o m in I0,m0****(see image 3)*****. The
second e m in he equa ion is used o egula ize. Dis a di usion enso ha
di uses in one o ano he way depending whe e he poin is placed. I g adien
o I is high hen he egula iza ion is o e he con ou line and i i is low, we
make egula iza ion.
This ene gy consis s o an a achmen e m ha enables he p ocess o ind
simila pixels in bo h images and a egula iza ion e m ha is necessa y o
cons ain he numbe o possible solu ions and o gene a e smoo h solu ions.
This me hod is a dense me hod in he sense ha o e e y pixel on one image
we ob ain i s co esponden on he o he image.
When we minimize his ene gy, we ob ain he Eule -Lag ange equa ions, whi-
ch a e ep esen ed by means o pa ial di e en ial equa ions. This is a di usion-
eac ion equa ion ha beha es aniso opically a con ou s wi h high alues o
he g adien o he images and iso opically a homogeneous egions whe e he
image g adien is low. The di usion pa is o mula ed in such a way ha he
discon inui ies o he images a e p ese ed. We use a scale-space and py ami-
dal s a egy o allow he me hod o loca e la ge displacemen s. Thanks o his
ene gy minimiza ion app oach he esul ing dispa i y maps ha we may ob ain
a e smoo h by egions.

VI
5. Co esponding Poin s and 3D Recons uc ion.
To sea ch he co esponding poin s in e e y image, we s a wi h a poin in
one image, and using he op ical low echniques, we sea ch he co esponding
poin in he nex image. Once his poin is ob ained, we go back and we sea ch
i he co esponding poin in he i s image is he s a poin . I i is ue, we
con inue sea ching o he poin in he nex image. Once we ha e his new poin
we come back un il he i s image e i ying ha he poin s calcula es a e he
same poin s ha we ha e wi h a small e o . We inish his p ocess when we
sea ch a poin bad placed.
Fi s , we will desc ibe an e icien algo i hm o compu ing sequences o
co esponding poin s wi h maximum leng hs. Second, we will desc ibe a as
algo i hm o compu ing sequences o co esponding poin s, bu in his case wi -
hou maximum leng hs. Expe imen al esul s show he alidi y o his algo i hm.
Bo h algo i hms y o include a candida e o a sequence o nco esponding
poin s o ob ain a sequence o n+ 1 poin s. We will explain di e en quali y
c i e ions, which a e applicable o decide whe he o add a new poin o he
sequence, o no .
In o de o calcula e he sequence o poin s in co espondence, we mus know
he Op ical Flow om e e y iew j o he p eceden iew j−1 (backwa d),
ha we deno e by hj
−(x) = hj
−(x, y)=(ui
−(x, y), j
−(x, y))Tand he Op ical
Flow om he iew j o he nex iew j+ 1 ( o wa d),hj
+(x) = hj
+(x, y) =
(ui
+(x, y), j
+(x, y))T.
The main idea is using he Op ical Flow hj
+(x) o localize he co esponden
poin x0in he iew j+ 1, om he poin x in he iew j, and using he Op ical
Flow hj+1
−(x) in he opposi e di ec ion om he iew j+1 o he iew j o come
back om he poin x0in he iew j+ 1 o a poin xp ime0in he iew j.
Then we ha e, om he Op ical Flow de ini ions,x0=x+hj
+(x) and xp ime0=
x0+hj+1
−(x0) = x+hj
+(x) + hj+1
−(x+hj
+(x)). In ideal condi ions, bo h poin s, x
and x00 mus be he same poin , bu in eal condi ions, his is usually alse, due
o se e al easons as limi a ions o calcula e he Op ical Flow, imp ecision in
he Came a calib a ion, nume ical e o s, e c. In hose cases, we ha e a dis ance
be ween hese poin s d(x, x00) = kx00 −xk. Wi h his idea we can cons uc
sequences o couples o poin s om e e y couple o images. Then he dis ance
d(x, x00) can be used as a c i e ion o quali y.
We can ex end his idea o ob ain sequences wi h mo e han wo poin s. One
poin xj, in he iew j, has i s co esponding poin xj+1 =xj+hj
+(xj), in he
iew j+ 1, and comes back o he poin x0
j=xj+1 +hj+1
−(xj+1) wi h an e o
dj(xj, x0
j)( o wa d and backwa d). To add a new poin o he sequence, we use
he poin xj+1 in he iew j+ 1 and he Op ical Flow hj+1
+(x) o go om he
iew j+ 1 o he iew j+ 2. In his way we ob ain, in his iew, he poin xj+2,
in co espondence wi h he poin xj+1, in he iew j+ 1. The backwa d Op ical
Flow, allows us o es ablish a i s measu e o quali y o he new sequence o h ee
poin s. In his way, in he iew j+ 1, we ha e he e o o wa d and backwa d
VII
Figu a 4. Backwa d and Fo wa d Op ical Flow o a poin in a couple o iews.
dj+1(xj+1, x0
j+1) whe e x0
j+1 =xj+2 +hj+2
−(xj+2), and in he iew j, he e o
o wa d and backwa d is dj(xj, x0
j) wi h x0
j=x0
j+1 +hj+1
−(x0
j+1).
Figu a 5. Backwa d and Fo wa d Op ical Flow o a sequence o se e al poin s.
Gene ally, o add a new poin xj+n o he sequence o n poin s in co espon-
dence xj,xj+1,. . . ,xj+n−1, we use he las poin added o he sequence, xj+n−1,
and he Op ical Flow hj+n−1
+(x) o calcula e he poin xj+nin he iew j+n.
This poin could become a new poin in he sequence o co esponding poin s,
xj+n=xj+n−1+hj+n−1
+(xj+n−1). To do ha , we calcula e he e o s backwa d
di(xi, x0
i)(i=j, j + 1, . . . , j +n−1) whe e we use he Op ical Flow hi+1
−(x) o
calcula e he poin backwa d x0
i, in he iew i, because x0
i=x0
i+1 +hi+1
−(xi+1)0.
This poin will be added o he sequence i hese e o s a e lowe lowe han a
h eshold ha we ha e de ined.
We ha e seen ha he o wa d and backwa d e o is an ini ial quali y mea-
su e o a sequence o co esponding poin s. The o wa d and backwa d e o
also allows us o es ablish a i s es o decide whe he o add a new poin o
he sequence o no . When we ha e a la ge numbe o iews he ini ial poin o
VIII
a sequence will no appea on he iew o he candida e poin and, he e o e,
he o wa d and backwa d e o s will be big. Fo a be e 3D econs uc ion, i
is con enien ha he sequence o poin s would be as la ge as possible in o -
de o u n he algo i hm less sensible o e o s. We may de ine mo e complex
c i e ions o ob ain sequences wi h many poin s. Ins ead o using a cons an
h eshold o he o wa d and backwa d e o s, we may adap his h eshold o
he sequence leng h. This would bene i la ge sequences o poin s wi h bigge
e o a he han sho sequences wi h a smalle e o . Ano he possible c i e ion
ha would be mo e obus is ha o using he candida e poin , he sequence o
co esponding poin s and he calib a ion ma ices o econs uc he 3D poin
and measu e he ep ojec ed e o s on he p ojec ion planes. In case ha he
ep ojec ed e o s would be smalle ha a gi en h eshold we would include he
candida e poin in o he sequence. I is also possible and adap i e scheme o
bene i he la ge sequences.
************************************* *************************************
***************************************
5.1. The Op imal Algo i hm
The Op imal Algo i hm o calcula e sequences o poin s in co espondence
is he ollowing:
1. Fo e e y iew
a) Fo e e y pixel
1) Calcula e he sequence o poin s in co espondence and i s quali y
2) Add he sequence o poin s in co espondence calcula ed in he p e-
ious s ep o an o de ed eposi o y. The i s o de c i e ion is he
numbe o poin s and he second one is he quali y o he sequence
o poin s in co espondence
2. Fo e e y sequence in he sequence eposi o y
a) Check ha he sequence o poin s in co espondence is no included in
ano he sequence o poin s in co espondence wi h a highe numbe o
poin s, o wi h he same numbe o poin s bu wi h a highe quali y
1) I he sequence o poin s in co espondence is no included in any
inal eposi o y o sequences o poin s in co espondence, hen add
he sequence o he inal eposi o y o sequences
2) I he sequence o poin s is included, hen ejec he sequence
In he s ep i e a es h ough all iews building o each pixel on he iew
a sequence o co esponding poin s and assigning a quali y alue. n iews will
p oduce n∗wid h iew ∗heigh iew sequences o co esponding poin s. In he
s ep he sequences o co esponding poin s a e selec ed. No mally some o he
sequences will be included on la ge sequences o hey would be as close o
conside ha hey a e p ac ically he same sequence. Al hough his algo i hm
cons uc s la ge sequences o co esponding poin s, i has he disad an age ha
i is compu a ion cos ly. S ep ... akes in o accoun ha a new sequence will no
IX
be in oduce in o he eposi o y i he sequence al eady exis s. A he beginning
when he eposi o y size is small i is as o es i a sequence is al eady included,
bu when he size is inc eased he numbe o he compa isons will also inc ease
making he p ocess much slowe .
5.2. The Fas Algo i hm
To dec ease he compu a ional cos o he e icien algo i hm p esen ed abo e
we modi y he algo i hm by adding a lag o e e y pixel. This lag indica es i a
pixel is included in a sequence o co esponding poin s. The algo i hm would be
as ollows:
1. Fo e e y iew
a) Fo pixel on he iew no included in a sequence
1) Compu e he sequence o co esponding poin s. Ma k e e y poin in
he sequence as included in a sequence o co esponding poin s
2) The compu ed sequence in he p e ious s ep is added o a eposi o y
Con a y o he e icien algo i hm, he as algo i hm does no gua an ee
ha he sequences o co esponding poin s would con ain he la ge numbe o
poin s.
When we ha e a se o images, hen we ake a couple o came as by chance
and we econs uc he 3D poin . We p ojec his poin o he plane o he whole
came as and we calcula e he p ojec ion e o , he dis ance be ween bo h poin s,
he eal poin and he p ojec ed poin in e e y came a.
La e we ake ano he couple o came as, always by chance, and we epea
he same s eps se e al imes, up o 8 imes i i is possible. We keep wi h he
poin ha minimizes he p ojec ion e o .
6. Resul s
In o de o ob ain he 3D econs uc ion we ha e used wo se o images,
i s se has 16 images, and second se has 25 images. And we ha e used h ee
di e en h eshold o p ojec ion e o : 1.0,1.2 and 1.5. In he nex images, we
can see he di e en 3D econs uc ion:
When we use mo e iews o make he 3D Recons uc ion, we ha e mo e
poin s, bu he ime o do i is bigge . In he o he hand when he p ojec ion
e o inc eases, he numbe o poin s inc eases oo, bu he poin s a e loca ed
wi h less p ecision.
Re e encias
1. L. ´
Al a ez, K. Ba˜nos, C. Cuenca, J. Escla ´ın and J. S´anchez. 3D econs uc ion
om a ascula ee model, EUROCAST, Las Palmas, 2003.