UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
ELIPSOIDES XENERALIZADOS ACTIVOS:
APLICACIÓN Á SEGMENTACIÓN DE
IMAXES MÉDICAS 3D
RAQUEL DOSIL LAGO
NOVEMBRO, 2000
DEPARTAMENTO DE ELECTRÓNICA E COMPUTACIÓN
Ós meus pais
Ag adecemen os
Que o exp esa o meu since o ag adecemen o a ódalas pe soas que con ibuí on á
ealización des a esiña.
En p imei o luga ó di ec o des a memo ia, Xosé Manuel Pa do López, pola súa
colabo ación, pe o sob e odo polo in e ese e a con ianza que deposi ou no meu
aballo.
A Diego Cabello e An onio Mosque a po con a comigo, pois o apoio ecibido
po ambos acili ou eno memen e o meu labo nes e g upo de in es igación.
A Víc o Lebo án e a Fe nando Vila iño po in e e an o empo en axuda me a
poñe es o en ma cha.
A Manolo Penedo pola in o mación acili ada e as suxes ións sob e algúns
aspec os do aballo.
A Paula López pola axuda que me mandou dende I alia a ce ca dos algo i mos
xené icos.
A Víc o B ea, Juanjo e Nando polos consellos e po da me ánimos e, en xe al, a
ódolos compañei os des e depa amen o, que ealmen e conseguen que i a un
ambien e es upendo.

i
ÍNDICE
1 INTRODUCCIÓN..................................................................................................... 1
2 RECONSTRUCCIÓN DE IMAXES 3D................................................................. 5
2.1 P ocesamen o de imaxes médicas........................................................................ 6
2.2 Segmen ación baseada en modelos...................................................................... 7
2.3 Inicialización de supe icies de o mables.......................................................... 11
2.4 Modelo de o ma global: o supe elipsoide......................................................... 12
2.5 Recoñecemen o de baixo ni el .......................................................................... 13
3 MODELOS DE SUPERFICIE............................................................................... 17
3.1 Esquemas de ep esen ación .............................................................................. 17
3.1.1 Dis ibución de pun os de on ei a .......................................................... 17
3.1.2 Ecuacións implíci as................................................................................. 19
3.1.3 Ecuacións explíci as ................................................................................. 20
3.1.4 Rep esen acións “de a ido”................................................................... 21
3.1.5 Técnicas de subdi isión do espacio.......................................................... 22
3.1.6 T ans o mación do eixe medio................................................................. 25
3.1.7 Rep esen acións cuali a i as..................................................................... 26
3.1.8 Xeome ía cons uc i a: CSG................................................................... 27
3.1.9 Esquemas de ep esen ación compa ados................................................. 28
3.2 Mé odos de econs ucción ................................................................................ 30
3.2.1 Pos a en co espondencia median e ans o macións íxidas ................... 30
3.2.2 Mé odos de o mables................................................................................ 32
3.2.3 Técnicas de op imización ......................................................................... 39
4 SUPERCUÁDRICAS.............................................................................................. 45
4.1 Medidas de e o.................................................................................................. 46
4.2 Xene alización pa a posición e o ien ación a bi a ias...................................... 48
4.3 Ambigüidade na ep esen ación median e supe elipsoides ............................... 49
4.4 Inicialización dos pa áme os de ans o mación íxida .................................... 50
4.5 De o macións globais......................................................................................... 53
4.6 Op imización con algo i mos xené icos............................................................. 55
4.6.1 Codi icación.............................................................................................. 56
4.6.2 Rendemen o do AX. ................................................................................. 57
4.6.3 Mecanismos de selección ......................................................................... 58
4.6.4 Función de adap ación.............................................................................. 59
4.7 Pos a en co espondencia con modelos a p io i................................................. 59
5 EXTRACCIÓN DE PARCHES DE SUPERFICIE ............................................. 61
ii
5.1 Fil os mul iescala ecu si os............................................................................. 62
5.1.1 Fil os mul iescala..................................................................................... 62
5.1.2 Implemen ación ecu si a dos il os ....................................................... 64
5.2 De ección de pun os de on ei a ....................................................................... 66
5.3 Cálculo das cu a u as locais............................................................................. 67
5.4 Ex acción de pa ches de supe icie................................................................... 70
5.4.1 Ag upamen o de pun os en pa ches de supe icie .................................... 71
5.4.2 Selección de pa ches de supe icie........................................................... 72
5.5 Obse acións...................................................................................................... 75
6 RESULTADOS........................................................................................................ 79
6.1 Op imización da unción implíci a..................................................................... 79
6.2 P ep ocesado...................................................................................................... 82
6.2.1 De ección de pun os de on ei a.............................................................. 82
6.2.2 De ección de pa ches de supe icie .......................................................... 83
6.2.3 E ique ado e selección de pa ches de supe icie....................................... 83
6.3 Pos a en co espondencia................................................................................... 84
7 CONCLUSIÓNS E PRINCIPAIS APORTACIÓNS........................................... 99
BIBLIOGRAFÍA........................................................................................................ 101
1
1 INTRODUCCIÓN
A impo an e mello a que es án a expe imen a as imaxes médicas idimensionais de
al a esolución, es á de i ando nun maio desen ol emen o das écnicas de
econs ucción de es uc u as ana ómicas, que cada ez poden o ece esul ados de
mello calidade. A ex acción da xeome ía a pa i das imaxes médicas se e de apoio
a ac i idades clínicas dende a diagnose a a a plani icación ci ú xica e simulación do
compo amen o isiolóxico. Pe o a pesa dos ecen es a ances nas ecnoloxías de
adquisición de imaxes, que p opo cionan is as excepcionais da ana omía in e na, o uso
do compu ado pa a cuan i ica e analiza as es uc u as in oluc adas con p ecisión e
e iciencia é aínda limi ada. A di icul ade na análise das imaxes médicas es á en do a ós
sis emas de econs ucción de obxec os 3D da su icien e lexibilidade pa a a a coa
complexidade e a iabilidade das o mas ana ómicas en e dis in os indi iduos.
Ademais, os incon enien es ípicos dos da os mos eados e o uído p o ocan a miúdo
que os con o nos das es uc u as esul en indis inguibles e desconec ados.
Du an e os úl imos anos, os modelos de o mables [28] ixé onse moi popula es en
ecoñecemen o e delineación de obxec os, pa icula men e no campo das imaxes
médicas [37]. O esquema básico dun modelo de o mable consis e nunha cu a, se
aballamos en 2D, ou supe icie, en 3D, que se de o ma localmen e a a axus a se á
on ei a do obxec o máis p óximo. Os modelos de o mables 3D o on inicialmen e
p opos os po Te zopoulos en [56]. Aquel p imei o modelo consis ía nun esquema de
elemen os ini os guiado po écnicas dinámicas. Pos e io es aballos o on
con ibuíndo a da lles lexibilidade. Exemplos da aplicación dos modelos de o mables
poden a opa se en [34, 38, 47, 50, 52, 53].
Cando os modelos de o mables son aplicados a da os 3D exis en dúas modalidades de
segmen ación: 2D (co e a co e) e 3D. En ambos casos o modelo inicial debe es a o
su icien emen e p óximo á on ei a do obxec o que se que e segmen a pa a que o
axus e sexa co ec o. Unha das an axes da segmen ación co e a co e é que se pode
pa i dunha inicialización semiau omá ica ou manual dun co e. Despois de segmen a
ese co e median e un modelo de o mable 2D u ilízase o con o no esul an e como
modelo inicial no co e eciño, epe indo o p oceso pa a ódolos co es da imaxe. Es a
inicialización baséase na p oximidade espacial en e co es adxacen es, que asegu a
con o nos p óximos en o ma e localización. O p incipal incon enien e é que non hai
ou a in e acción en e con o nos de co es eciños no p oceso de de o mación, a pa e
da inicialización, o que pode le a a inconsis encias na supe icie esul an e. Se o
con o no se pe dese nun co e en pa icula , o mé odo alla ía. Ademais, equi e unha
e apa de pos p ocesado pa a conec a-la secuencia da con o nos e ob e a supe icie
con inua.
O uso de e dadei os modelos de supe icie pode ía conduci a mé odos de
segmen ación máis obus os, xa que asegu a ía a cohe encia e a sua idade global nos
8 CAPÍTULO 2. RECONSTRUCCIÓN DE IMAXES 3D
écnica op-down, é dici , baseada en modelos. Pa indo dunha desc ición de al o ni el
ep esen ada po un modelo de inido a p io i, e despois dunha ase de localización do
mesmo na imaxe, aplica íase un p oceso de de o mación local que o ece unha
desc ición de máis baixo ni el. A ou a a e a é a do p ep ocesado da imaxe, necesa ia
pa a a pos a en co espondencia co modelo. O en oque que se lle deu a es e p oblema
oi o dun p oceso bo om-up, como se e á no capí ulo 1. Pa indo dos da os da imaxe,
aise o ganizando a in o mación a a ob e unha ep esen ación que pe mi a decidi que
pun os da imaxe poden pe ence ó obxec o e cales non. A pos a en co espondencia
ealizase en e o modelo a p io i es es e pun os.
Cabe pensa que es a ase de p ep ocesado pode ía ap o ei a se di ec amen e pa a ob e
unha desc ición do modelo de o ma global, en luga de se i se dela simplemen e pa a
a pos a en co espondencia cun modelo de inido de an emán. Sen emba go, imos e
nes a sección que o p ocesado bo om-up non é unha écnica obus a da que se poida
ob e unha desc ición de al o ni el iable. A con inuación imos ace unha compa ación
das ca ac e ís icas que p esen an as écnicas baseadas en imaxes e as baseadas en
modelos, pa a concluí que as p imei as son, polo xe al, as máis adecuadas pa a
calque a ipo de aplicación.
Como se dixo an es, uns dos p oblemas que a on a a análise de imaxes son o
ecoñecemen o de o mas e a econs ucción de imaxes pa a isualización en 3D, onde
os da os cos que se ai aballa ep esen an un ni el de in ensidade de g is ou ben
compoñen es de co . A segmen ación de baixo ni el non baseada en modelos aballa
unicamen e sob e es a in o mación, analizando as p opiedades locais da imaxe pa a
di idi a escena en obxec os. Es o non se pode acada sen ace ningún ipo de
suposición sob e as ca ac e ís icas da imaxe. Po exemplo, se se ai unha segmen ación
baseada en exións, es a ase es ablecendo a hipó ese de que á eas ou olumes de
dis in a co pe encen a obxec os dis in os. Tamén podemos ealiza unha de ección de
bo des, na que se asume que a a iación do ni el de g is se co esponde cunha on ei a
en e di e en es obxec os se supe a un de e minado umb al. O mesmo se pode ace
ope ando no dominio da ecuencia, a ibuíndolle ás baixas ecuencias a in o mación
de bo des ou supe icies on ei izas.
Todas es as ap oximacións son pe ec amen e álidas cando as hipó eses nas que es án
baseadas se cump en. O ei o é que es as case nunca se e i ican de xei o es ic o. Son
moi os os e ec os que se es án ob iando ó es ablece as hipó eses an e io es, como as
a iacións de con as e ou iluminación en dis in as pa es dunha imaxe, a p esencia
dou as es uc u as ademais das de in e ese, as ex u as na supe icie dos obxec os, as
oclusións e, en xe al, calque a ipo de dis o sión ou de deg adación que poida su i
unha imaxe no p oceso de cap u a.
As écnicas non baseadas en modelos non eñen a capacidade de manexa in o mación
de ipo es uc u al. Es o non só ai epe cu i na calidade dos esul ados, senón que
ademais, di icul a a ex acción de p opiedades globais dos obxec os. Po exemplo, se
aplicamos unha de ección de bo des a unha imaxe uidosa ou con ex u as, o esul ado
ai se un conxun o de segmen os de cu a ou de supe icie, segundo aballemos en
dúas ou es dimensións, inconexos e ami icados, e non a on ei a comple a dun
obxec o, e só dese obxec o, di e enciándoo así do es o da imaxe. Polo an o, ampouco
se an pode ex ae p opiedades xeomé icas do obxec o, como posición, á ea ou

2.2 Segmen ación baseada en modelos 9
olume, e c., e menos aínda, i máis alá e p e ende compa a-lo obxec o con ou os
coñecidos e iden i icalo como memb o dunha clase.
Exis en écnicas que, como se mencionou ó p incipio des a in oducción, p e enden
ex ae in o mación da es uc u a global das imaxes, en ando iden i ica-los obxec os
que con én pa indo dos esul ados ob idos no p ocesado de baixo ni el, ás que
chamabamos écnicas guiadas po da os. Hai desen olados mé odos, coma o que se
p esen a no lib o de Balla d e B own [1], que, pa indo dunha de ección de pun os de
on ei a, en an conec a os agmen os de supe icie esul an es pa a o ma
supe icies pechadas que de inan obxec os. O incon enien e que eñen es es mé odos é
que pa en xa de esul ados que poden se e óneos, o que des i úa odo o p oceso
pos e io . Po eso es as écnicas nunca an e-la obus ez e a iabilidade das écnicas
baseadas en modelos.
Tódalas conside acións an e io es son abas que xo den a causa de aballa a ni el
local sen emp ega modelos. Hai ou o aspec o que se pode cues iona nes a clase de
écnicas, e é que non se ai uso de coñecemen o a p io i sob e os obxec os, nin
p ede e minando ce as p opiedades, nin impoñendo limi acións, baseándose en
hipó eses sob e o con ido das imaxes. Ben é ce o que, como se comen ou
an e io men e, semp e que se p ocesa unha imaxe es ase a ealiza algún ipo de
suposición sob e a in o mación que con én. Sen emba go, as p emisas sob e as que se
le a a cabo es a modalidade de segmen ación non eñen en con a ningún ipo de
in o mación especí ica da clase pa icula de imaxe que se es á a analiza , non sendo o
axus e dalgún posible umb al de ni el de g is ou de g adien e de ni el de g is. Se á a o
o dominio de aplicación do a amen o de imaxes no que non se eña ningunha noción
sob e a súa na u eza ou do seu con ido. Podemos descoñece que é ou como é o que a
imaxe ep esen a exac amen e, pe o en moi as ocasións ai se posible in uí ce as
ca ac e ís icas. Po exemplo, se os obxec os eñen con o nos pechados ou abe os, se as
súas supe icies son planas ou cu as. Nalgunhas aplicacións incluso se sabe de
an emán que é o que es amos endo na imaxe.
Tan o a al a de isión de conxun o, como o desap o ei amen o do coñecemen o a
p io i, como a imposibilidade de exe ce ningún ipo de con ol sob e as p opiedades
xeomé icas dos obxec os, poñen os mé odos an e io es en des an axe con espec o ás
écnicas baseadas en modelos, que po de inición son o mé odo axei ado pa a a a con
es e ipo de in o mación. O ei o de pode con ola ou p e ixa de e minados
pa áme os da ep esen ación dunha supe icie, implica pode o za a que os obxec os
se adap en ás ca ac e ís icas desexadas e amén in oduci coñecemen o. A de inición e
o modo de u ilización dun modelo ai depende do ipo de aplicación.
Se o que que emos é ob e a econs ucción dun obxec o, o modelo ai consis i nun
esquema de ep esen ación que ca ac e ice ó obxec o de o ma ap opiada e nun mé odo
de econs ucción pa a ob e-los pa áme os do esquema a pa i da imaxe. Nes es casos,
aínda o modelo non impón ningunha es icción sob e a o ma conc e a do obxec o, si
pode limi a os g aos de libe dade na ep esen ación da o ma. Es o sucede cando, po
exemplo, que emos modela un obxec o median e unha unción implíci a cuad á ica. Os
únicos pa áme os que podemos a ia son adios e os pa áme os de ans o macións
a íns. Un esquema de ep esen ación semp e ai limi a en ce a medida a xeome ía
dun obxec o, pe o amén se poden con ola de e minadas p opiedades no p oceso de
10 CAPÍTULO 2. RECONSTRUCCIÓN DE IMAXES 3D
econs ucción. Un exemplo cla o des a si uación dáse no modelos de snakes ou
con o nos ac i os. O modelo non é an só o esquema de ep esen ación, que non deixa
de se unha simple dis ibución de pun os no espacio, senón que inco po a unha écnica
de econs ucción que pe mi e guia a e olución dos pun os a a que se adap an á
on ei a do obxec o, de inindo o zas en e os pun os, como se osen pa ículas ísicas.
En aplicacións de ecoñecemen o o en oque é dis in o. Pá ese dun modelo a p io i, e
en ón o que hai que implemen a é un mé odo de busca que explo e imaxe pa a a opa
obxec os de ca ac e ís icas simila es á p imi i a dada. Des e xei o soluciónanse as
limi acións do p ocesado de baixo ni el, pois podemos iden i ica-lo obxec o como un
caso pa icula do modelo, ou sexa ealiza unha clasi icación dos obxec os que
apa ecen na escena. Ademais, podemos ob e medidas das súas p opiedades, que eñen
dadas polo modelo de o ma explíci a, na súa pa ame ización, ou de o ma implíci a.
Nes e ipo de a e as é p eciso e un ce o coñecemen o do ipo de obxec os que an
apa ece na imaxe e dispo dun modelo a p io i de cada un deles.
Exis en amén aplicacións nas que, a pesa de e en como obxec i o a desc ición
de allada da o ma dun obxec o, aise p ecisa amén dunha ase de ecoñecemen o
dese obxec o nunha escena, que é o caso que comen abamos an e io men e, sob e o que
e sa es e aballo. A manei a máis común de en oca-lo p oblema é pa i dun modelo a
p io i, que ep esen a un p o o ipo do obxec o. Con el ealiza ase unha p imei a e apa
de ecoñecemen o do obxec o. Logo pe mí ese a de o mación do modelo pa a ob e
inalmen e o modelo pa icula desa imaxe. Es e é o caso do sis ema de segmen ación
2D desen ol o po Al man e B inkley [10], que emp ega un modelo de o ma
p omedio, ob ida a pa i de imaxes de ades amen o. O p oceso de axus e consis e en
ealiza unha es imación dos pun os do con o no da imaxe cada ez máis e inada a
medida que se an in oducindo no os pun os do modelo a p io i. A es imación
ealízase median e un il o de Kalman en unción da in o mación de co elación en e
modelo e imaxe. En ocasións, os modelos a p io i e a pos e io i an i ep esen ados
median e esquemas dis in os. Na me odoloxía que máis adian e p esen amos, es o ai
se ine i able, pos o que o modelo de supe cuád icas o ece unha desc ición de o ma
moi global. Es o aino moi axei ado como modelo a p io i, pe o moi pob e como
desc ición local, polo que se, cando sexa p ecisa unha ase de e inamen o ai habe
que ealiza un cambio de ep esen ación. No caso de u iliza o modelo de
supe cuád icas como inicialización dun modelo de o mable, unha simple mos axe da
supe icie se á su icien e.
Á ho a de exp esa-las es iccións impos as, o ipo de in o mación que hai que manexa
ai se , usualmen e, aínda que non necesa iamen e, de baixo ou al o ni el en
aplicacións de econs ucción ou ecoñecemen o espec i amen e. Podemos, po
exemplo, p e ende limi a a ugosidade dunha supe icie nun p oceso de
econs ucción, e en ón es a emos ope ando a baixo ni el, ou podemos que e encon a
obxec os de o ma ap oximadamen e es é ica en a e as de ecoñecemen o, e aquí
es a emos u ilizando in o mación de máis al o ni el. O esquema de ep esen ación que
escollamos debe se capaz de pa ame iza a in o mación coa que aiamos aballa . En
consecuencia, a ep esen ación escollei a é de e minan e na cons ucción dun bo
mé odo de modelado. Ademais, condiciona á ou limi a á os posibles mé odos de
2.3 Inicialización de supe icies de o mables 11
econs ucción ou de busca. Pa a o obxec i o que nós p opoñemos, a elección de
supe cuád icas pa ece se a máis adecuada.
2.3 Inicialización de supe icies de o mables
Aínda que a nosa p e ensión é que o sis ema sexa aplicable a calque a ipo de imaxes
3D, o dominio de aplicación que o mo i a é o modelado de es uc u as ana ómicas,
conc e amen e de es uc u as óseas. Así, obse a ase que as imaxes coas que
aballamos son odas des e ipo. A idea de ace es e ipo de ap oximación no ámbi o
da imaxe médica, xo de como consecuencia dun p oblema que p esen an os modelos de
de o mación local.
Os modelos de o mables, coñecidos amén como modelos ac i os, o ecen un g an
ni el de de alle nos esul ados, que a penas se en a ec ados polo uído p esen e na
imaxe, pos o que pe mi en con ola a sua idade da o ma do con o no ou supe icie, de
aí que sexa unha das écnicas máis emp egadas nes e campo. A o ma de econs uí o
modelo é median e a e olución da súa o ma guiada pola in o mación de g adien e de
ni el de g is. As ecuacións que exen a e olución dos pun os de on ei a esul an de
esol e-lo p oblema de minimización dunha uncional que ep esen a a ene xía
asociada á on ei a. En e os e mos que con ibúen a esa ene xía, es á o o ixinado
polas o zas que a aen ós pun os ca a ós máximos de g adien e. Es e algo i mo de
econs ucción i e a i o ende a es abiliza se en mínimos locais da ene xía, é dici , os
pun os de on ei a máis p óximos ó pun o de pa ida. Des e xei o, se na imaxe apa ece
máis dun obxec o, o esul ado pode non se o desexado. A supe icie ou con o no debe
es a inicialmen e moi p óxima á do obxec o de in e ese pa a que ou as es uc u as non
in e i an.
A a o de ago a unha das o mas máis sinxelas de soluciona es o é median e a
in e acción co usua io, ó que se lle pe mi e inicializa manualmen e o modelo. Como xa
se comen ou na in oducción, o mé odo de inicialización de cada co e po sepa ado,
deseñando manualmen e o con o no inicial no p imei o co e e p opagando os
esul ados ós co es eciños, non p opo ciona esul ados o almen e sa is ac o ios.
Ou a opción é de ini unha p imi i a simple, como po exemplo unha es e a, e pe mi i
ó usua io elixi a posición do seu cen o e al ez o adio. Tampouco es a é, en xe al,
unha boa solución en imaxe médica, pois a p esencia de g an núme o de ecidos no
olume esixe unha inicialización mello [37].
Es as conside acións sob e os modelos de o mables ob igan a pensa nunha manei a de
inicializa-lo con o no ac i o, que nes e caso se á unha supe icie pois aballa emos en
3D, median e un modelo a p io i. Nalgúns es udios [29] ealizados óp ase po ob e
es es modelos median e a econs ucción manual dun p imei o p o o ipo de obxec o
median e unha ep esen ación de dis ibución espacial de pun os, como unha
iangulación, que ep esen a ía un modelo p omedio dese ipo de obxec o. Nós
conside amos que es o é innecesa io, pos o que a ob ención e almacenamen o des e
modelo a p io i non compensa se despois se ai some e a unha de o mación, que é a
que decide a o ma inal. Pensamos que unha desc ición a g oso modo é su icien e pa a
a inicialización, especialmen e no caso de es uc u as óseas, e que esul a máis sinxela
12 CAPÍTULO 2. RECONSTRUCCIÓN DE IMAXES 3D
de ob e e manexa , ademais de que en unha pa ame ización moi o máis educida.
Es o le ounos á elección dos modelos de elipsoides xene alizados.
2.4 Modelo de o ma global: o supe elipsoide
O esquema de ep esen ación que se escolleu pa a c ea o modelo de o ma global oi o
de supe cuád icas, amén chamadas elipsoides xene alizados ou supe elipsoides. Vén
desc i o po unha unción implíci a non lineal. Os mo i os des a escolla son dous: o bo
comp omiso que o ece en e po encia de ep esen ación e pa ame ización educida e a
in a iancia an e ans o macións íxidas. Es a ep esen ación emp ega un núme o
educido de g aos de libe dade, o que apo a acilidade de manexo e e iciencia no
almacenamen o en memo ia. Es a simplicidade non se ob én a cos a de educi en
exceso a a iedade de o mas que pode adop a , pois o ece unha po encia de
ep esen ación acep able pa a o dominio de aplicación, o que o ai moi a ac i o pa a o
noso p opósi o. Pa a aumen a-la po encia de ep esen ación des as p imi i as, se así
ose necesa io, é posible aplica sob e es e modelo unha se ie de ans o macións de
o ma global de modo moi sinxelo (como se ixo nes e aballo) ob endo así unha
lexibilidade de ep esen ación moi o maio , sen inc emen a en exceso o núme o de
pa áme os do modelo. Po ou o lado, o ec o de pa áme os do modelo, ademais dos
pa áme os de o ma, debe inco po a a iables que den in o mación sob e a posición, a
o ien ación e o amaño con que apa ece na imaxe. No p oceso de ob ención do modelo,
ben sexa pa a ecoñecemen o ou pa a econs ucción, ai habe que de e mina es es
pa áme os. Es o aise ace buscando a ans o mación íxida que aplicada ó modelo
p opo cione a mello ap oximación ó obxec o. Po es e mo i o, o esquema de
ep esen ación debe se in a ian e a es e ipo de ans o macións, que engloban
anslación, o ación e escalado, que amén se chaman ans o macións íxidas po que
non al e an a o ma do modelo. Non ódolos esquemas p esen an in a iancia a es as
ans o macións, un mo i o máis a a o dos supe elipsoides, que si eñen es a
p opiedade.
Dispoñendo dun modelo a p io i pa a un de e minado obxec o podemos localiza di o
obxec o nunha imaxe median e a pos a en co espondencia en ambas ( e igu a 2.1).
Tan o pa a a ob ención do modelo de pa ida ( igu a 2.1, 1º paso), como pa a a súa
pos e io pos a en co espondencia co obxec o na imaxe ( igu a 2.1, 4º paso), o xei o de
calcula os pa áme os do modelo que se axus a adecuadamen e ós pun os de supe icie
é ealizando un p oceso de op imización, no que se en a minimiza unha unción que
depende da dis ancia de cada pun o do obxec o ó pun o máis p óximo da supe icie da
p imi i a. No p imei o caso habe ía que ob e ódolos pa áme os do modelo de
obxec o, an o os que desc iben a súa o ma, coma os de ans o mación íxida. Pa a a
pos a en co espondencia os pa áme os de o ma es án p e ixados e só hai que
de e mina-la ans o mación íxida.
Pa a ex ae os pun os pe encen es á supe icie do obxec o é necesa io ealiza un
p ep ocesado que elimine da imaxe ou os pun os de on ei a que poidan apa ece
(pasos 2º e 3º), aínda que es o pódese e i a emp egando écnicas de c ecemen o de
modelos. Na aplicación que aquí se desc ibe ecó ese á p imei a das dúas opcións. O
c ecemen o de modelos o que ai é inicializa un g an núme o de supe elipsoides po
2.5 Recoñecemen o de baixo ni el 13
odo o olume e, a con inuación, en a nun p oceso i e a i o que ai e oluciona a
algúns deles a a adap a se ás o mas exis en es na imaxe, mes es que os demais an
sendo eliminados. Como esul ado apa ece án segmen ados ódolos obxec os p esen es
na imaxe, e non só o de in e ese. Pa a pode adap a es o ás necesidades da aplicación
se ía necesa io ealiza unha selección do modelo co ec o, emp egando pa a elo
coñecemen o a ce ca da súa xeome ía. Coa ou a es a exia, o coñecemen o aplícase
an es do modelado, na selección dos pun os de on ei a.
Temos en ón que o mé odo de cons ucción dos modelos ai se o cálculo do mínimo
dunha unción non lineal nun espacio mul idimensional. De en e o amplo conxun o de
écnicas que se poden emp ega pa a a op imización, a elixida oi un algo i mo
xené ico. Es a elección en a ias xus i icacións, elacionadas p incipalmen e coa
con e xencia a mínimos globais e coa súa adecuación a uncións complexas. Nes e
caso a complexidade adica na non linea idade e na g an dimensionalidade do
p oblema, que non a ec an en absolu o á codi icación do ec o de pa áme os no
algo i mo xené ico, e amén no manexo de es iccións no ango dos pa áme os, que se
a an dun xei o moi sinxelo. De odos modos ó algo i mo de op imización non ai se
un ac o c í ico no esul ado inal. Lemb emos que o obxec i o non é unha desc ición
de allada do obxec o.
2.5 Recoñecemen o de baixo ni el
O p ocesado da imaxe p e io ó modelado ou á pos a en co espondencia en como
obxec i o a ex acción dun conxun o de pun os que, p esumiblemen e, pe enzan á
supe icie do obxec o. Pa a de e mina es a dis ibución de pun os pódense u iliza
écnicas de p ocesado de baixo ni el non baseado en modelos. O esul ado que ai
o ece , como cabe espe a dese ipo de a amen o da imaxe, se á moi pob e, polos
mo i os que mencionamos no apa ado 2.2, pe o a e apa de modelado se á capaz de
ex ae a in o mación global implíci a nesa nube de pun os.
O p ep ocesado cons a de dúas ases ( e igu a 2.1). En p imei o luga hai que ace
unha de ección de bo des ( igu a 2.1, 2º paso). Pa a es a in pódense aplica il os no
dominio da ecuencia, que ac úan eliminando a in o mación de baixa ecuencia, ou
pódense emp ega il os espaciais, que de ec an a iacións locais do ni el de g is.
Den o des a úl ima modalidade, exis en a ias es a exias. Po un lado es án aquelas
baseadas nunha es imación das p imei as de i adas di eccionais do ni el de g is,
calculadas pa a cada pun o da imaxe nunha ce a eciñanza. Como combinación das
dis in as compoñen es calculadas ob ense unha magni ude que nos in o ma do b usca
que é a a iación da co en cada pun o, que xe almen e se á unha ap oximación ó
g adien e no dominio disc e o. A con inuación hai que de ini un c i e io que, a pa i
des a in o mación, de e mine que pun os pe encen á on ei a dun obxec o. Un c i e io
é de ini un umb al, de o ma que ódolos pun os que eñan alo de g adien e maio ca
el considé ase que pe encen a unha on ei a. A imaxe que esul a de oma es a opción
pode p esen a supe icies de on ei a de g oso maio que a unidade. Unha solución
mello , que oi a emp egada nes e aballo, é de e mina os máximos locais do
g adien e de ni el de g is. Po ou o lado es án as écnicas baseadas no cálculo das
de i adas segundas di eccionais, que pe mi en ealiza unha ap oximación á laplaciana.

14 CAPÍTULO 2. RECONSTRUCCIÓN DE IMAXES 3D
Os pun os de on ei a son nes a ocasión aqueles nos que a unción laplaciana c uza
polo alo ce o.
A segunda ase consis e no e ique ado das supe icies esul an es da de ección de
bo des, median e o cómpu o das p opiedades que as ca ac e izan. Es as e ique as
se i án logo pa a ealiza-la selección de supe icies pe encen es ó obxec o,
baseándonos en coñecemen o ( igu a 2.1, 3º paso). En unción do ipo de obxec o a
segmen a , de ini ase unha unción de a aliación de cada pa che de supe icie que
indica en que medida se pa ece cada pa cela de supe icie ó p o o ipo da clase de
obxec o. Es a unción depende á de p opiedades xeomé icas, como a cu a u a, que
ca ac e iza a o ma dun modelo de e minada, e dos ni eis de g is e de g adien e de
ni el de g is que, en imaxes médicas, poden axuda a de e mina o ipo de ecido do
ó gano. Os pa ches que omen un alo da unción maio son bos candida os a
pe ence á supe icie do obxec o a modela
Á inal des a e apa o que emos é un conxun o de pa ches de supe icie con al a
p obabilidade de pe ence ó obxec o, pe o que non desc iben co ec amen e a súa
o ma, pois apa ece án exións inconexas e ou as ami icadas pola unión con pa ches
pe encen es a ou os obxec os. Sen emba go, es es da os son bos dabondo pa a ealiza-
la pos a en co espondencia co modelo, que se á o que ealmen e u iliza emos como
desc ición da supe icie, e non os pa ches de on ei a, esol endo así o p oblema da
ca encia de in o mación es uc u al.
2.5 Recoñecemen o de baixo ni el 15
Figu a 2.1. Secuencia de p ocesado pa a a inicialización dun modelo de o mable. No paso 1
de ínese un modelo de o ma a p io i a pa i da supe icie p omedio do obxec o ex aída de
imaxes de ades amen o. Os pasos 2 e 3 cons i úen a ase de p ep ocesado de baixo ni el, da que se
ob eñen os pun os de on ei a pa a a pos a en co espondencia co modelo a p io i, no paso 4.
IMAXE
ORIXINAL
2. EXTRACCIÓN DE
PUNTOS DE FRONTEIRA
CONXUNTO DE
PARCHES DE
SUPERFICIE
3. ETIQUETADO E
SELECCIÓN
DE PARCHES
PARCHES DO
OBXECTO A
MODELAR
4. POSTA EN
CORRESPONDENCIA
MODELO A
POSTERIORI
MODELO
A PRIORI
1. MODELADO MEDIANTE
SUPERCUÁDRICAS
PROTOTIPO DE
SUPERFICIE DO
OBXECTO
3 MODELOS DE SUPERFICIE
3.1 Esquemas de ep esen ación
Á ho a de elixi un esquema de ep esen ación de supe icie debemos e en con a
a ios aspec os. En p imei o luga hai que conside a se é ap opiada pa a o ipo de
imaxes que imos a a . Nes e sen ido habe á que es udia-las seguin es p opiedades:
• po encia; qué a iedade de o mas á capaz de adop a e se es as son su icien es
no dominio da aplicación.
• comple i ude; busca ase un mé odo que non p esen e ambigüidades, é dici ,
que dous obxec os di e en es non eñan a mesma ep esen ación.
• unicidade; que a un obxec o só lle co esponda unha única ep esen ación.
A de inición o mal des es concep os pódese encon a no aballo de Flynn e Jain [24].
En segundo luga hai que e en con a ou as cues ións máis p ác icas, elacionadas co
cus e compu acional da ob ención do modelo, cos equi imen os de memo ia e coa
acilidade de implemen ación dos mé odos de econs ucción.
A con inuación p esén ase unha e isión dalgunhas das écnicas de ep esen ación máis
comúns. Pa a cada unha delas indícanse as súas p opiedades, que quedan esumidas na
áboa 3.1 á inal des e apa ado. Tamén se es udia unha ca ac e ís ica moi impo an e en
aplicacións de modelado, que é a in a iancia an e ans o macións íxidas.
3.1.1 Dis ibución de pun os de on ei a
Desc ibi unha supe icie ou un olume po medio dunha nube de pun os en a an axe
de que a súa ob ención a pa i dunha imaxe é bas an e di ec a. Sen emba go, a
in o mación apo ada soamen e polas coo denadas dos pun os é insu icien e á ho a de
isualiza o esul ado ou de aplica un pos p ocesado. Habe á que do a á
ep esen ación de es uc u a, incluíndo in o mación ace ca da conec i idade en e os
pun os. Po es e mo i o, os da os o ganízanse xe almen e en o ma de g a o [24].
Segundo o ipo de aplicación se á in e esan e o ganiza a in o mación dun xei o ou
dou o. Pódese es uc u a de o ma xe á quica, po exemplo nunha á bo e, de al xei o
que os nodos olla sexan os pun os, e capas supe io es da xe a quía empa ella ían
nodos pa a o ma a es as, ag upa ían a es as pa a o ma polígonos, polígonos pa a
cons uí polied os e incluso se pode ía ope a sob e polied os simples pa a ob e
igu as máis complexas.
Habe á ocasións nas que a complexidade des as ep esen acións se á innecesa ia. Pa a
es as si uación hai écnicas máis sinxelas, como é a coñecida como wi e ames ( igu a
24 CAPÍTULO 3. MODELOS DE SUPERFICIE
de e mina-lo plano óp imo. Po ou a pa e, es e mé odo non soluciona o p oblema da
non in a iancia on e a ans o macións íxidas, co ag a an e de que, a di e encia dos
oc ees, a á bo e non é única pa a unha imaxe dada. Es o é moi ácil de e . Se emos
unha imaxe neg a cunha igu a b anca, e emos in ini os planos que co an a imaxe en
dúas exións e que deixan a igu a o almen e con ida nunha delas, quedando a ou a
balei a, men es que na á bo e de oc an es as di isións es án p e ixadas.
Ma ching Cubes
A écnica de Ma ching Cubes, máis que un esquema de ep esen ación, é un mé odo de
econs ucción de supe icies ianguladas, polo que se pode ía incluí es a écnica no
p imei o des a se ie de apa ados, xun o coa iangulación de Delaunay. Sen emba go,
en a pa icula idade de que ai uso dunha oxelización da imaxe pa a di idi o espacio
en exións, a pa i do cal ex ae a iangulación. O mé odo consis e na ex acción
dunha isosupe icie a pa i dunha imaxe olumé ica. A isosupe icie é o análogo a
unha cu a de ni el, pe o es endida a 3D. Nes e caso én de inida po un ni el de g is,
que ma ca a on ei a do obxec o, así que, dalgún xei o es a é unha écnica de de ección
de pun os de on ei a baseada en exións, xa que equi e dunha umb alización. Tamén
a á bo e de oc an es se pode es ende des e xei o, pois as imaxes de inidas en ni eis de
g is hai que ans o malas a bina ias.
O mecanismo é o seguin e. Supoñamos, simpli icando un pouco as cousas, que emos
un olume onde o espacio balei o apa ece colo eado cun ni el de g is en o no a i, e
que ese olume con én un obxec o de co media j. Na zona de ansición habe á unha
a iación do ni el de g is de i a j que se á máis ou menos sua e. En e eses dous
alo es podemos de ini un umb al de ni el de g is que es ablece unha di isión en e
pun os in e nos e ex e nos ó obxec o. Es e é un p oceso de baixo ni el, con ódalas
(a)
(b) (c)
Figu a 3.6. Quad ee

3.1 Esquemas de ep esen ación 25
limi ación que es o supón. Do que se a a ago a e de ob e unha ep esen ación da
isosupe icie en o ma de iangulación a pa i desa clasi icación dos pun os.
A idea é que, se dous pun os adxacen es es án si uados en exións dis in as, é dici , se
un pe ence ó in e io do obxec o e o ou o é ex e no, en ón a isosupe icie debe pasa
po en e os dous. O que ai o algo i mo de Ma ching Cubes é, en p imei o luga ,
ag upa os pun os en cubos ( oxels). Pa a cada cubo es udia ase a que exión pe ence
cada un dos seus 8 é ices. A con inuación habe á que de e mina cal é o plano ou
planos que di iden o cubo de o ma que os pun os in e nos e ex e nos queden si uados
en semiespacios sepa ados. Se po exemplo emos un único é ice pe encen e ó
olume do obxec o, en ón o plano de di isión se á un que co e ás a es as do cubo que
compa en ese é ice. A in e sección des e plano e as a es as do cubo p odúcese po
es pun os, de inindo un iángulo da supe icie do obxec o. Es e é só un dos 15 posible
casos que se poden da , con ando co caso i ial, onde ódolos é ices es án na mesma
exión. A iangulación co esponden e a cada caso pódese e na igu a 3.7.
Ago a só es a decidi po que pun o da a es a ai a c uza cada plano de di isión. A
solución máis sinxela é co a semp e polo pun o medio da a es a. Es a ap oximación
moi poucas posibilidades pa a as o ien acións dos iángulos, polo que a supe icie que
se ob én esul a moi pouco sua e, especialmen e se a imaxe se oma cunha ecuencia
de mos axe baixa. Ou a ap oximación, máis usada que a an e io , é ealiza unha
in e polación lineal dos ni eis de g is sob e os pun os das a es as do cubos. O pun o de
co e se á o que ome o ni el de g is umb al que se de iniu pa a a clasi icación das
exións. Des e xei o ob éñense supe icies máis sua es.
3.1.6 T ans o mación do eixe medio
Como comen abamos, a ep esen ación dun obxec o median e oxelización, indicando
pa a cada pun o da imaxe se pe ence ó olume do obxec o ou non, é moi cus oso no
almacenamen o. Algunhas das écnicas que imos conseguen comp imi-la
ep esen ación, subs i uíndo a oxelización pun o a pun o po ou a máis compac a,
onde os oxels son exións do espacio de amaño a iable. A écnica de ans o mación
do eixe medio (MAT, Medial Axis T ans o m) ,[48 ,49], pe mi e ob e esul ados aínda
mello es, pois un olume ai queda educido ó seu esquele o. O esquele o dunha
supe icie é unha liña,ou conxun o de liñas que ecolle a súa es uc u a. A es a liña é
que se lle chama eixo medio. Se o que emos é un olume, o esquele o se á unha
supe icie, polo que ,en ocasións, a ase e e encia ó obxec o medio (medial objec ), en
luga do eixo medio, pa a engloba ámbalas dúas de inicións.
Pa a de e mina-lo esquele o dun obxec o hai que de ini unha mé ica que p opo cione,
pa a cada pun o do in e io do olume, unha medida da dis ancia ó pun o do con o no
da supe icie ou supe icie do olume máis p óximo. Unha ez de e minado o mapa de
dis ancias, ex áese a liña que une os máximos e ese se á o esquele o. In ui i amen e
ese que es a liña ai equidis a do con o no da supe icie, de aí o nome ans o mada
de eixo medio. A ep esen ación MAT consis e no esquele o e no alo da dis ancia
asociado a cada un dos seus pun os. Po an o, a mé ica emp egada ai se moi
impo an e pa a a pos e io econs ucción da igu a. Algunhas das medidas que se soen
u iliza son a dis ancia euclídea, a dis ancia Manha an, amén chamada ci y block, que
ep esen a a suma das compoñen es do ec o di e encia, e a dis ancia omada como o
26 CAPÍTULO 3. MODELOS DE SUPERFICIE
máximo de en e es as compoñen es. O esquele o calculado a pa i da dis ancia
euclídea pódese in e p e a como o luga xeomé ico dos cen os das ci cun e encias,
no caso 2D, insc i as no con o no, que con adio máximo, pe co en o in e io da
supe icie. En 3D pódese de ini igual só que ago a son es e as. Es o é moi ácil de e
median e un exemplo, coma o da igu a 3.8, que mos a o esquele o an o pa a dúas
como pa a es dimensións. As dúas úl imas mé icas son ap oximacións que, en ce as
aplicacións poden se su icien es. Supoñen un a o o en empo de cálculo.
En calque a dos es casos a elación en e unha igu a e a súa ep esen ación MAT é
semp e álida e biuní oca, ou sexa, que a ep esen ación é comple a e única. Ó mesmo
empo, a po encia de ep esen ación é moi al a, pois pe mi e de ini o mas a bi a ias
con g an esolución, e odo es o nunha ep esen ación compac a que equi e moi pouco
espacio pa a o seu almacenamen o.
3.1.7 Rep esen acións cuali a i as
As ep esen acións cuali a i as manexan un ipo de in o mación o almen e dis in o ó
dos esquemas an e io es. Non se pa ame izan magni udes ca ac e ís icas dunha igu a
xeomé ica, senón que se sobe no ni el de abs acción pa a in en a ace unha
desc ición cuali a i a do aspec o que p esen a. Aínda que o a amen o cuan i a i o é
necesa io en moi as das á eas da isión a i icial, no caso conc e o da ealización de
a e as de análise ou ecoñecemen o pode se su icien e es ablece unha dis inción en e
clases de obxec os emp egando un conxun o de desc ip o es das súas p opiedades,
elacionados coa pe cepción que emos deles. A idea oi p opos a po Biede man, quen
elabo ou unha clasi icación do que el chamou geons (GEome ical iONS),
di e enciándose cada un deles polos alo es dun conxun o de p opiedades cuali a i as.
En a e as de análise es a idea pode se in e esan e, semp e que o núme o de clases de
obxec os de inidos sexa su icien e no campo de aplicación. En caso con a io, a
clasi icación esul a ambigua, pois nunha mesma clase es amos englobando obxec os
dis in os que nos in e esa di e encia . En xe al es e ipo de ep esen ación soe se
incomple a.
Figu a 3.7 As 15 posibles di isións do cubo
3.1 Esquemas de ep esen ación 27
3.1.8 Xeome ía cons uc i a: CSG
CGS son as siglas de Cons uc i e Solid Geome y. Es a ep esen ación ai uso
dalgunhas das que imos an e io men e, a modo de p imi i as de olume. Obxec os
máis complexos con ecciónanse a pa i das p imi i as aplicando sob e elas
ans o macións xeomé icas e/ou combinando a ias igu as median e ope acións de
unión, in e sección ou di e encia. Pa a c ea un obxec o pode se necesa ia oda unha
xe a quía de ope acións sob e as p imi i as, que se es uc u an en o ma de á bo e
bina ia ( igu a 3.9).
As p imi i as de o ma que se emp egan soen i de inidas median e ecuacións
implíci as, incluídos algúns olumes de e olución como cilind os e conos, e amén
polied os, pe o es es úl imos, en luga de ep esen á ense median e unha dis ibución de
é ices, eñen dados polo olume ence ado po un conxun o de planos. Des e xei o,
odas es as p imi i as se poden descompoñe en subá bo es, nos que os nodos olla son
exp esións do ipo
(
)
0,, ≥zyx
ás que se lles chama semiespacios, pois de inen unha supe icie que di ide o espacio en
dúas exións. Se é lineal e emos un polied o, e se é de segundo g ao, e emos as
cuád icas. Subs i uíndo na á bo e CSG a subá bo e co esponden e a cada p imi i a,
pode emos ob e o mas complexas como combinación de semiespacios. Tamén exis en
sis emas des e ipo que, ademais das p imi i as an e io es, emp egan supe icies spline
pechadas e incluso NURBS.
Es e esquema de ep esen ación es á pensado pa a ap o ei a a po encia de
ep esen ación das dis in as p imi i as que emp ega. Nese sen ido a solución é mello
que calque a das an e io es, pe o a cos a dunha se ie de incon enien es moi
impo an es. Un é que o emp ego de semiespacios e de ope acións booleanas an des a
unha ep esen ación moi desc i i a, ol éndose di icul oso o cálculo de p opiedades
xeomé icas. O ou o é que a á bo e CSG non é única pa a un obxec o de e minado.
Es e sis ema é comple o e álido na medida en que o son as p imi i as de supe icie
emp egadas. O ei o de combina es as p imi i as non impón ningún ipo de
ambigüidade adicional nin da luga ep esen acións e óneas.
Figu a 3.8. Obxec o medio en 2D e 3D
28 CAPÍTULO 3. MODELOS DE SUPERFICIE
3.1.9 Esquemas de ep esen ación compa ados
Bo ando unha ollada ás ca ac e ís icas que p esen an os dis in os esquemas de
ep esen ación desc i os nes a e isión podemos cons uí a áboa 3.1, onde se
especi ican pa a cada esquema as p opiedades que se mencionaban ó p incipio des a
sección. A modo de esume p esén ase a con inuación unha compa a i a en e os
dis in os esquemas, acendo e e encia ás p opiedades de po encia de ep esen ación,
comple i ude e unicidade.
Sob e a po encia de ep esen ación, pódese dici que os esquemas baseados en nubes de
pun os eñen unha po encia de ep esen ación an al a como se desexe, en unción da
densidade supe icial de pun os que se elixa. Sen emba go, es a ep esen ación es a á
limi ada a igu as poliéd icas. O mesmo p oblema p esen an os esquemas de
subdi isión do espacio. Dende es e pun o de is a, as ecuacións explíci as son máis
po en es, pois é posible escolle o g ao das uncións polinómicas, o que pe mi e de ini
supe icies con cu a u as an sua es como se c ea con enien e. Tamén a
ep esen ación MAT en unha po encia de ep esen ación al a. No ex emo opos o es án
as ecuacións implíci as, que soen e un núme o moi limi ado de g aos de libe dade.
Respec o ós GEONS, o simple ei o de se unha ep esen ación cuali a i a xa supón
unha o e es icción en can o á capacidade desc i i a, pe o eso depende á de como se
de inan as clases de obxec os. Finalmen e, emos os sis ema CSG que, como he dan as
p opiedades das p imi i as que emp ega pa a cons uí obxec os, é o esquema máis
lexible.
Da comple i ude diciamos que se cump e cando unha de e minada con igu ación dos
pa áme os do esquema de ep esen ación lle co esponde unha única supe icie. Es o
e i ícase en xe al pa a ódolos esquemas que acabamos de e , coa excepción dos
GEONS, que nunha mesma clase poden ag upa a dis in as supe icies.
De en e os esquemas de ep esen ación que acabamos de e isa , só a ans o mación
de eixe medio e os geons cump en a p opiedade de unicidade. Pa a o es o das écnicas
exis i án múl iples ep esen acións dun mesmo obxec o. Os esquemas de dis ibución
Figu a 3.9. Á bo e CSG
3.1 Esquemas de ep esen ación 29
de pun os eñen o p oblema de que exis en innume ables o mas de de e mina-la
conec i idade. Incluso cando se escolle un mé odo sis emá ico de poligonalización, do
ipo da iangulación de Delaunay ou de Ma ching Cubes, a ep esen ación non é única.
Po exemplo, se se que e iangula unha supe icie plana con o ma de cad ado, exis en
dúas posibles con igu acións da conec i idade, segundo a diagonal que se elixa pa a
o ma-los iángulos. Coas ecuacións implíci as, a non unicidade é debida en xe al ás
sime ías de o ación, pe o amén en casos pa icula es exis en ou o ipo de
ambigüidades, como sucede no caso dos supe elipsoides cos pa áme os de cuad a u a.
No caso das ep esen acións median e ecuacións explíci as, sucede que unha mesma
supe icie se pode de ini emp egando dis in os conxun os de pun os de con ol.
Tampouco a cons ucción da á bo e CSG é única pa a unha supe icie de e minada,
pois un obxec o pódese cons uí median e di e sas composicións de p imi i as
simples.
A elección dun ou dou o esquema debe e en con a es es es aspec os, pe o amén
ou o de ipo máis p ác ico, ela i os á e iciencia en empo de cálculo e amén ó
compac a que sexa a ep esen ación. Nes e sen ido, calque a ep esen ación que
in oluc e unha desc ición en o ma de dis ibución de pun os, de elemen os ini os, ou
de oxelización do espacio pe mi e ealiza ce o ipo de a e as, como po exemplo a
isualización, de o ma máis ápida. Nou o ipo de ep esen acións habe á que le a a
cabo unha disc e ización da supe icie. Sen emba go, non odo son an axes. Pa a ob e
unha boa esolución na de inición das supe icies é p eciso dispo dun olume de da os
moi ele ado, co conseguin e uso de espacio en memo ia. Ademais, nalgunhas mé odos
de econs ucción, o ei o de non dispo dunha exp esión analí ica que de ina a
supe icie pode se un p oblema. É o caso das écnicas de exis o, onde o cálculo das
dis ancias en e supe icies e pun os de imaxe non se pode ace de o ma di ec a.
Dado que no p esen e aballo se ai ealiza o modelado p ecisamen e median e un
p oceso de pos a en co espondencia, pensamos que é máis in e esan e emp ega un
modelo desc i o po unha ecuación implíci a. A pe da po encia de ep esen ación que
es o supón, en compa ación cos esquemas de nubes de pun os, non é aquí un p oblema,
senón máis ben unha an axe, pois a in o mación que se manexa é de máis al o ni el, o
que, como e emos, apo a obus ez ó p oceso. O axus e a pequena escala xa se
in oduce pos e io men e na e apa de de o mación local e o cambio de ep esen ación
que debe media en ambas ases e ec úase con apidez po medio dunha simple
disc e ización.

30 CAPÍTULO 3. MODELOS DE SUPERFICIE
3.2 Mé odos de econs ucción
Unha ez seleccionado o esquema de ep esen ación que se ai emp ega pa a de ini-lo
modelo, hai que es udia a es a exia de ob ención dos pa áme os co esponden es a
pa i da imaxe. Pa a a econs ucción dun modelo exis en mul i ude de écnicas. Nes a
sección anse p esen a algunhas das máis comúns, que se clasi ican en dous g upos:
écnicas de pos a en co espondencia con modelos a p io i median e ans o macións
íxidas, e modelos de de o macións. En ealidade, ambas es a exias son
complemen a ias, como xa se comen ou no capí ulo in oduc o io. Pa a ema a es a
e isión p esen a anse unha se ie de algo i mos de op imización que poden se
aplicados pa a implemen a es es mé odos de econs ucción.
3.2.1 Pos a en co espondencia median e ans o macións íxidas
Cando se en un coñecemen o exac o da mo oloxía do obxec o que se desexa modela ,
é posible e i a-la econs ucción do modelo pa a cada imaxe. Pa indo dunha conxun o
de imaxes de ades amen o pódese ob e un modelo a p io i do obxec o, co que a
análise dunha no a imaxe queda educida á busca da ans o mación que supe pón
modelo e obxec o. Es as ans o macións deben man e a o ma o ixinal do modelo a
p io i, polo que se aplican ans o macións íxidas: de anslación, de o ación e de
Esquema de Rep esen ación Po encia Comple i ude Unicidade
Wi e ames al a si non
Poligonalización al a si non
T iangulación de Delaunay al a si non
Cuád icas moi baixa si non
Supe cuád icas baixa si non
Cilind os xene alizados baixa si non
Splines al a si non
B-splines al a si non
NURBS moi al a si non
Á bo es de oc an es al a si non
Ma ching cubes al a si non
MAT al a si si
Geons moi baixa non si
CGS moi al a - non
Táboa 3.1 Ca ac e ís icas de a ios esquemas de ep esen ación
3.2 Mé odos de econs ucción 31
escala. A o ma de de e mina-los pa áme os da ans o mación a ía segundo o ipo de
ep esen ación elixido. Besl e McKey [6] p esen a on unha e isión comple a dos
dis in os mé odos de exis o de imaxes. A con inuación explícanse os mé odos
u ilizados pa a modelos de supe icies pa amé icas, de inidos median e ecuacións
implíci as, e modelos de dis ibucións espaciais de pun os.
Funcións implíci as
Pa a a econs ucción de uncións implíci as sóense aplica écnicas que implican un
p oceso de op imización dunha unción que e lexa a calidade do axus e do modelo ós
da os. Unha das ap oximacións máis usadas consis e en a a de minimiza unha
unción que ep esen e unha medida elacionada coa dis ancia da supe icie ós pun os
da imaxe [6, 9]. En xe al, calcula a dis ancia exac a en e un pun o do espacio e unha
supe icie pode se complexo e cus oso compu acionalmen e, o que le a a u ilización
dou as mé icas. A p opia unción implíci a, dada po (x,y,z), pode se emp egada pa a
es ima en que medida se des ían os pun os da imaxe do modelo, semp e e cando a
unción sexa mono onamen e c ecen e ou dec ecen e coa dis ancia exac a. Na e isión
de Bolle e Vemu i [9], e amén no aballo de Whai e de Fe ie [58] p esén anse
algunhas ap oximacións pa a os casos de cuád icas e supe cuád icas.
Tamén con es e esquema de ep esen ación se pode aplica un mé odo p obabilís ico,
in en ando maximiza-la p obabilidade de que a supe icie sexa a co ec a. Pa a
supe icies simples, como cuád icas é sinxelo de ini unha unción de p obabilidade.
Po exemplo, pa a o caso da es e a, onde habe á que de e mina-los alo es óp imos do
seu cen o c
e do adio
R
, p esén ase en [9] a seguin e unción de p obabilidade:
()





−−−∝ ∑
=
N
i
iRcxp
1
2
2
1
exp
σ
Pa a ou o ipo de uncións implíci as máis complexas, como conos ou supe cuád icas,
é máis complicado de ini unha unción de p obabilidade axei ada.
Nubes de pun os
Cando a modelo non én dado pon unha unción analí ica, senón que se ep esen a po
unha colección de pun os con idos na supe icie, o cálculo das dis ancias en e pun os
do modelo e da imaxe é máis complicado. O máis ecuen e é que a co espondencia
en e pun os de obxec o e imaxe non sexa coñecida, polo que non se pode aplica unha
écnica de minimización de dis ancias de o ma di ec a. Habe á que es ablece un
c i e io pa a empa ella os pun os da supe icie do modelo cos do obxec o. Es o é
impo an e non só na pos a en co espondencia do modelo co obxec o, senón amén na
de inición dos modelos a p io i, que xe almen e se ob eñen a pa i de a ias imaxes de
p oba, que hai que elaciona en e si.
Pa a sal a es e p oblema K ahns ö e [29] e Feldma e Ayache [22] u ilizan unha
écnica baseada en ma cas (landma ks), que son un conxun o educido de pun os
ca ac e ís icos da supe icie. O p imei o dos au o es pe mi e a de inición des as ma cas
po pa e do usua io. De inidas es as ma cas an o no modelo coma no obxec o, emos
unha elación un a un en e elas e podemos calcula dis ancias en e os pa es de pun os.
En ón xa se pode aplica o algo i mo de exis o de ambas imaxes. Se o modelo se ai
32 CAPÍTULO 3. MODELOS DE SUPERFICIE
emp ega como supe icie inicial dun algo i mo do ipo dos an e io es, bas a con
de e mina a ans o mación íxida que hai que aplica ó modelo pa a que as ma cas
queden o máis p óximas posible. Se se desexa un maio axus e dos pun os ó modelo,
pódese pe mi i ans o macións a íns dou o ipo, ademais das íxidas, que supoñen
unha de o mación global do modelo, e incluso ou as ans o macións máis complexas.
Pola súa banda, Feldma p esen a un algo i mo o almen e au omá ico, no que a
co espondencia en e pun os de ambas igu as se ealiza en unción de p opiedades
xeomé icas. Con es e obxec i o p opón unha écnica na que se an aplicando de o ma
sucesi a unha se ie de ans o macións sob e o modelo.
En p imei o luga ealízase unha ans o mación íxida, onde un conxun o de pun os da
supe icie do modelo se empa ellan con aqueles ou os pe encen es ó obxec o que
eñan cu a u as simila es. Es o ai seguido dunha de o mación global do modelo pa a
acada un maio axus e, aplicando unha ans o mación a ín non íxida. Á ho a de
implemen a-la busca da ans o mación a ín global, u iliza un c i e io de
empa ellamen o co máis p óximo, só que a medida da dis ancia que se u iliza es á
omada nun espacio 8D, onde se mide a p oximidade en e as coo denadas espaciais,
pe o amén en e as cu a u as p incipais e as compoñen es do ec o no mal en cada
pun o. Conc e amen e u ilízase unha medida da dis ancia euclídea d, onde os eixes das
8 coo denadas es án escalados con cadanseu ac o αi, de modo que cada e mo eña o
mesmo peso no cálculo da dis ancia. A exp esión é a seguin e.
() ( )
(
)
(
)
(
)
()
()()()
2/1
2
228
2
117
2
6
2
5
2
4
2
3
2
2
2
1
}''''
''''{',
kkkknnnn
nnzzyyxxPPd
zzyy
xx
−+−+−+−
+−+−+−+−=
αααα
αααα
Finalmen e, emos a e apa de de o mación local. A di e encia dos modelos de o ma
global, onde hai que e ec ua un cambio de ep esen ación, disc e izando a supe icie,
na ep esen ación median e dis ibución de pun os xa se pode aplica unha ase de
de o mación local. Es a pode ía se algunha das que máis adian e se expo án nes a
sección. No algo i mo de Feldma óp ase polas ans o macións a íns, pe o es a ez
se án independen es pa a cada pun o da supe icie.
3.2.2 Mé odos de o mables
Os mé odos de o mables, sexan de de o macións locais ou globais, p ecisan da
de inición dun modelo de pa ida, a pa i da cal se de o man pa a axus a se ós da os da
imaxe imaxe. A inicialización da supe icie de o mable pode ealiza se median e a
in e acción co usua io pe o, dependendo do modelo de de o mación emp egado, pode
se necesa ia unha maio ap oximación inicial. Cando es o é así, é habi ual u iliza-lo
modelo de de o mación como un e inamen o dun modelo a p io i, que p e iamen e se
puxo en co espondencia coa imaxe median e ans o macións íxidas. Nes e apa ado
p esén anse algunhas écnicas que u ilizan de o macións pa a a econs ucción
de allada dos obxec os.
Snakes.
A écnica coñecida como modelo de con o nos ac i os -supe icies ac i as no caso 3D-
ou snake é un mé odo de segmen ación moi coñecido pola súa obus ez. En e os
3.2 Mé odos de econs ucción 33
moi os au o es que in es iga on sob e os modelos de snakes, al ez os máis des acados
sexan Te zopoulos e McIne ney [28, 33, 35, 36, 37, 39, 55]. T á ase de simula o
compo amen o da supe icie como un co po some ido ás leis da ísica. Pa a le a es a
idea a cabo hai que de ini un conxun o de o zas de in e acción dos pun os da
supe icie en e eles e cos pun os da imaxe. A cada pa de pun os do mallado da
supe icie asóciaselle unha o za de a acción de inida en unción dunha se ie de
p opiedades dos ma e iais, como elas icidade ou ixidez. Es as in e accións,
comunmen e chamadas o zas ex e nas ou de imaxe, an selas que con olen as
p opiedades xeomé icas in ínsecas da supe icie, egulando a cu a u a e a
con inuidade. As o zas ex e nas, amén chamadas de imaxe, deben p oduci unha
a acción ca a os pun os da imaxe. A supe icie inal se á aquela pa a a que o o al das
o zas es ean en equilib io.
Se en luga de emp ega a o mulación New oniana, aplicamos as ecuacións de Eule -
Lag ange, o p oblema adúcese na minimización da in eg al dunha unción de
densidade de ene xía ou, no dominio disc e o, a suma dunha unción de ene xía local
es endida a ódolos nodos da supe icie. A solución de mínima ene xía co espóndese
coa posición de equilib io. As o zas an es ci adas de i a íanse des a ene xía:
(
)
(
)
(
)
[
]
∫∫ +=
S
ex snake dud E EE ..in
onde
()
u ,= é a supe icie, exp esada en unción dos pa áme os na u ais
[]
1,0, ∈ u .
Expliquemos ago a máis en de alle os e mos que con ibúen á ene xía dun nodo. Po
unha pa e e emos a ene xía esponsable da a acción ca a a on ei a dos obxec os.
Pódense de ini de moi as o mas, en unción das ca ac e ís icas das imaxes en xogo,
pe o habi ualmen e p o ocan a a acción da supe icie ca a ós máximos do g adien e,
onde se supón que debe habe unha on ei a en e dous obxec os, como po exemplo
(
)
(
)
2
. I Eex ∇−=
Pa a egula-la con inuidade ou a cu a u a da supe icie in odúcense e mos de ene xía
in e na elacionados coa elas icidade e a lexibilidade da supe icie, como se se a ase
dunha lámina en ensión ou unha memb ana. Unha posible de inición de ene xía in e na
é a seguin e
()
(
)
(
)
(
)
22222 2 u uu u E ++++=
βα
A a iable
α
con ola a elas icidade, a esis encia ó es i amen o. Cando
α
oma o alo
ce o, unha o za su icien emen e g ande pode p oduci-la o u a da memb ana. A
a iable
β
é a esponsable da ixidez e egula á a acilidade coa que se dob a a lámina
e a a que pun o se pode lexiona . Se
β
é nulo, es amos pe mi indo que haxa
descon inuidades na o ien ación da supe icie, é dici , que se o men esquinas. Os
pa áme os de elas icidade e de ixidez poden se cons an es ou uncións. Os alo es de
α
e de
β
escóllense en unción do ipo de obxec os a econs uí e da calidade das
40 CAPÍTULO 3. MODELOS DE SUPERFICIE
onde o sis ema e oluciona a pasos cons an es ca a ó ex emo. En cada i e ación do
algo i mo de g adien e o ec o de pa áme os a op imiza x
desp ázase unha dis ancia
k, sendo k un alo cons an e, na di ección do ec o de g adien e no malizado, do
seguin e xei o
(
)
()
i
i
ii x
x
kxx
∇
∇
+=
+1
Es a ap oximación p esen a un p oblema que pode se bas an e g a e. Se o alo da
cons an e k é g ande, pódense p oduci oscilacións en o no ó ex emo sen chega a
acadalo nunca con p ecisión su icien e. Pa a eso habe ía que educi-lo alo do paso,
pe o a ía o algo i mo moi len o. Unha posible solución a es e p oblema se ía pe mi i
que k ose diminuíndo nas sucesi as i e acións do algo i mo. En cada i e ación pódese
calcula o alo óp imo de k. O alo de k ai a que conduce ó meno alo posible de
na seguin e i e ación, de e mínase pola condición de mínimo:
()
(
)
()
0
1
=








∇
∇
+
∂
∂
=
∂
∂
+
i
i
iii x
x
kx
k
x
k
Calculado o alo de ki, subs i úese na exp esión de 1+i
x
. Es o diminúe a axa de
con e xencia, pe o o empo de cálculo en cada i e ación inc emén ase.
Máis e icien e é o algo i mo de New on-Raphson, que emp ega o cálculo de de i adas
segundas pa a acada un maio axus e do ex emo. De í ase emp egando unha
ap oximación en se ie de Taylo de p imei a o de
()
(
)
(
)
(
)
iiiii xxx x x
−
∇
+
≈
++ 11
e da condición de ex emo
()
0
0
=
∇x . Se o sis ema es á inicializado nas p oximidades
do ex emo podemos ealiza-la seguin e ap oximación
()
(
)
(
)
(
)
⇒−∇∇+∇==∇ ++ iiiii xxx x x
11 0
(
)
(
)
iiii x xHxx
∇−= −
+
1
1
Es e algo i mo en o incon enien e de que hai que calcula-la ma iz hessiana H en cada
i e ación. De no o podemos eco e á suposición de es a p e o dun ex emo local,o
que nos se e pa a pode ealiza unha ap oximación de segunda o de da unción. co
cal a ma iz hessiana é cons an e e non se á necesa io ecalculala de cada ez. Des e
xei o, a aplicación des e algo i mo esul a moi in e esan e pa a a op imización de
uncións non lineais.
O p incipal p oblema se á conduci as a iables do sis ema ás p oximidades do ex emo
local. Se es o non é posible hai que eco e á écnica de g adien e descenden e, que
pola súa pa e, non o ece unha boa ap oximación do mínimo. O ideal se ía pode
emp ega a écnica de g adien e descenden e nunha e apa inicial do algo i mo e
inalmen e o algo i mo de New on-Raphson pa a un mello axus e do ex emo.

3.2 Mé odos de econs ucción 41
O algo i mo que consegue le a a cabo es e p opósi o é o de Le enbe g-Ma qua d . É
unha a ian e do algo i mo de New on-Raphson que in oduce un pa áme o que egula
o a e olución. O que se ai é subs i uí a ma iz hessiana po ou a
(
)
iiii HA
λ
+
=
1
ijij HA
=
j
i
≠
Inicialmen e o pa áme o
λ
oma un alo ele ado, de o ma que na ma iz A dominan
os elemen os da diagonal, dando luga a un compo amen o simila ó de g adien e
descenden e. Es o conduce ó sis ema ás p oximidades do ex emo máis p óximo. Se o
longo da execución do algo i mo se ai dec ece o pa áme o, A ai ende a H, e en ón
e emos de no o o algo i mo de New on-Raphson, acadando o ex emo con p ecisión.
Tempe ado simulado
O empe ado simulado (Simula ed Annealing, SA) é un bo algo i mo pa a a ob ención
de ex emos globais, especialmen e ú il cando a unción posúe ademais moi os
ex emos locais. É ap opiada an o pa a uncións con inuas de inidas en espacios
mul idimensionais, como é o caso que nos in e esa, como pa a uncións a aliadas sob e
un espacio de con igu acións disc e o pe o ex enso, onde, po un lado, non se poden
aplica algo i mos de g adien e, e po ou o, ealiza unha busca exhaus i a esul a
inabo dable. O p incipio de uncionamen o es á ex aído da e modinámica,
conc e amen e da c is alización das moléculas cando son some idas a un a e iamen o
len o. Dunha o ma moi simpli icada, pódese desc ibi es e enómeno des e xei o: a
pe da de ene xía das moléculas ó descende a empe a u a p oduce unha educción da
mobilidade é mica. Se es o sucede a un i mo su icien emen e len o, es as pa ículas
eñen a opo unidade de “baila ” en e dis in os es ados a a a opa o de mínima ene xía,
es abilizándose e o mando a es uc u a c is alina. Pa a un de e minado alo da
empe a u a, a p obabilidade que en unha pa ícula de es a nun es ado de ene xía E
én dada pola ó mula de dis ibución de p obabilidade de Bol zmann.
()





−
−∝ kT
EE
Ep min
exp
Se T dec ece len amen e a a ce o chégase á si uación en que a p obabilidade de es a no
es ado de mínima ene xía se á a unidade e o es o se án inaccesibles. Pe o pa a
calque a alo de T>0 semp e exis e unha ce a p obabilidade de que a pa ícula
e olucione ca a un es ado ene xe icamen e peo . Vexamos como se aplica es a idea.
Se
()
x E
= é unha unción que que emos op imiza – aise aplica ó caso da busca dun
mínimo global-, o que a emos se á i xe ando alo es de x
alea o iamen e en cada
i e ación do algo i mo. Pa a cada no a con igu ación de e mínase a súa co esponden e
ene xía e a alíase a p obabilidade do sis ema de e oluciona ca a o no o es ado
median e
42 CAPÍTULO 3. MODELOS DE SUPERFICIE
() ( )





>





−
−
≤
=
−
−
−
1
1
1
exp
1
ii
ii
ii
EE
kT
xExE
EE
p
En unción desa p obabilidade esól ese se o sal o se ai e ec i o ou non. En caso
a i ma i o subs i úese o ec o de pa áme os an e io polo no o. Obse ando a unción
emos que e ec i amen e, pa a un alo de T maio que ce o, e a di e encia do que
sucede nun algo i mo de g adien e, a p obabilidade de pasa a un es ado con ene xía
maio non é nula, o que ai pe mi i saí de mínimos locais. Es o é moi ú il nas
p imei as i e acións do algo i mo, onde se equi e unha explo ación do espacio de
con igu acións na p ocu a do mínimo global, pe o a medida que o sis ema e oluciona,
es o supón un incon enien e, pois in oduce imp ecisión á ho a de si ua con exac i ude
o ex emo. Aquí é onde in e én o pa áme o T, que simula o e ec o do descenso da
empe a u a. Inicialmen e ómase un alo al o de T, co cal asegú ase que o sis ema
poida cambia an o pa a mello como pa a peo . Despois dunha explo ación do espacio
onde se es ima en que exión pode es a si uado o mínimo global, a educción paula ina
da empe a u a ai que diminúa a p obabilidade de que a ene xía suba. Finalmen e case
ódalas i e acións se esol e án a a o do descenso, cambiando o compo amen o do
sis ema.
En conclusión, es e mé odo consegue de ec a un es emo global cunha p ecisión boa,
aínda que non se pode asegu a ó cen po cen que o ex emo sexa o óp imo. Can o máis
len o sexa o dec ecemen o da empe a u a maio segu idade se pode á e no esul ado.
Po iso, a pesa de se un sis ema moi e ec i o, é pouco e icien e compu acionalmen e.
Algo i mos xené icos
A aplicación dos p incipios da xené ica á busca adap a i a e a op imización de uncións
deu luga ó desen ol emen o do que se coñece como algo i mos xené icos (AX). Os
undamen os sob e os que se cons úe un algo i mo xené ico, a sabe , os mecanismos de
e olución dos c omosomas e o p incipio de supe i encia do mello adap ado de
Da win, son simulados a i icialmen e sob e unha poboación de posibles solucións a un
p oblema de e minado. Es o da luga a un e icaz sis ema pa a abo da-la busca de
ex emos globais, álido pa a odo ipo de uncións, po complexas que sexan es as.
Algúns es udios in e esan es sob e es e ipo de sis emas ecóllense no aballos de
Goldbe g [25] e Holland [26].
Os AX son, coma o empe ado simulado, écnicas p obabilís icas de explo ación do
espacio de solucións dun p oblema, pe o a di e encia dou as écnicas des a na u eza,
non aballan cunha única solución en cada i e ación, que de aquí en dian e imos
chama xe ación, senón que se xe a oda unha poboación de indi iduos, ep esen ados
median e unha cadea de pa áme os a modo de xenes dun c omosoma. As ope acións
que conducen dunha xe ación á seguin e son p incipalmen e a ep oducción, que é a
ansc ición sen al e acións dun c omosoma, o in e cambio de xenes, chamado
c uzamen o (c osso e ), e a mu ación. O papel que xoga a unción a op imiza na
e olución da poboación, é o de ou o ga a un indi iduo maio ou meno p obabilidade
de in e i na c eación da no a xe ación, a aliando a bondade de cada solución, que se
3.2 Mé odos de econs ucción 43
co esponde ía co g ao de adap ación ó medio. Pos eso á unción a op imiza se lle
chama unción de adap ación ( i ness unc ion).
Polo xe al, pa a a implemen ación das ope acións de a iación xené ica, soe se de g an
u ilidade a codi icación dos ec o es de pa áme os, aínda que es o non é
imp escindible. Habi ualmen e emp éganse codi icación de ipo bina io. Así, unha
ep esen ación moi usual dunha solución da unción é unha cadea de bi s o mada pola
conca enación das codi icacións asociadas a cada un dos pa áme os. Es o acili a an o
a ope ación de mu ación, que consis i ía na selección alea o ia dun dos bi s da cadea e a
negación do seu alo , como o c uzamen o, pa a o que bas a ía selecciona unha ou
máis posicións de uncamen o da cadea e o in e cambio dos anacos esul an es.
Aínda que exis en múl iples a ian es do AX, a liña xe al de uncionamen o é a que
desc ibe o seguin e pseudocódigo.
codi icación.
inicialización alea o ia da poboación a N indi iduos.
a aliación da poboación.
epe i
epe i
selecciona 1 indi iduo e ep oducilo.
selecciona 2 indi iduos e ecombinalos.
selecciona 1 indi iduo e mu alo.
a a xe a N no os indi iduos.
a alia-la no a poboación.
a a que se acade o c i e io de e minación.
A e minación da execución do algo i mo pode ixa se cando se acada un de e minado
g ao de ap oximación da solución, pe o pa a iso hai que dispo dun ce o coñecemen o
sob e a unción que se es á a op imiza . Ou a solución é de e o p oceso de e olución
cando se deixen de obse a a iacións signi ica i as na composición da poboación.
Po se es a si uación ampouco chega a da se, amén se pode limi a o núme o de
xe acións.
O po que do uncionamen o dos AX es á implíci o na o ma de ep esen a e manipula
as a iables. A hipó ese dos bloques cons i uín es (building blocks) xus i ica a
con e xencia do algo i mo baseándose no es udio dos esquemas (schema a) que
compoñen a cadea de xenes. En [5, 25, 27] p esén ase unha in oducción a es a eo ía.
Un esquema é unha secuencia de alo es de e minados dun subconxun o de xenes
pe encen es ó c omosoma –na codi icación bina ia soen ep esen a se polos alo es
co esponden es, ma cando o es o dos bi s como a iables, como po exemplo 10***,
ou 11*0*-. A lonxi ude dun esquema mídese como o núme o de bi s de sepa ación
en e o de maio e o de meno o de. Os esquemas ep esen an exións no espacio de
solucións. Pa a que o AX con e xa, os seus mecanismos de e olución deben consegui
que den o da poboación abonden os indi iduos con esquemas co esponden es a
44 CAPÍTULO 3. MODELOS DE SUPERFICIE
exións p óximas á solución óp ima, ou polo menos a solucións boas. Median e o
p incipio de supe i encia do máis adap ado pe mí ese unha maio pa icipación dos
indi iduos con esquemas bos nas ope acións de c uzamen o, pe mi indo que esquemas
cu os se combinen pa a o ma esquemas longos, é dici máis p e o da solución
óp ima. Son os esquemas cu os os que xogan un papel máis impo an e, pois son os
que maio p obabilidade de sob e i i xe ación as xe ación, dado que can o máis
longo é o esquema maio é a p obabilidade de se agmen ado. Po es e mo i o se
en a á deseña algo i mos que pe mi an ap o ei a ó máximo a in o mación apo ada
po es es esquemas cu os asociados a al os alo es da unción de adap ación, que se
soen chama bloques cons i uín es. Pola súa banda, a mu ación se e pa a in oduci
esquemas no os na poboación. Des e xei o, c uzamen o e mu ación cons i úen un
mé odo de explo ación excelen e na p ocu a do ex emo global da unción.
Tódalas conside acións an e io es ma can unha se ie de di e encias co es o de écnicas
de op imización de p opósi o xe al, que a con inuación se esumen.
O AX aballa con a ias solucións simul aneamen e. Digamos que en un pa alelismo
implíci o. Ademais, pódese dici que as solucións exis en es nunha de e minada
xe ación eñen memo ia das xe acións an e io es, a di e encia de ou as écnicas como
o SA, onde a in o mación de es ados an e io es non se ap o ei a. Es as dúas
ca ac e ís icas pe mi en unha isión máis global do espacio de busca e polo an o maio
p obabilidade de da co esul ado co ec o.
O AX non aballa coas a iables do p oblema, senón que polo miúdo o a á unha
cunha codi icación das mesmas. É dici , as ope acións de e olución xené ica non
p ecisan dispo de ningún ipo de coñecemen o sob e o p oblema en pa icula , nin
sob e a na u eza das uncións a op imiza . Non sucede así cos algo i mos de g adien e,
que a pa e de p ecisa dunha inicialización p óxima á solución desexada, necesi an
ealiza cálculos do g adien e e da ma iz hessiana da unción. Se a unción é
demasiado complexa, es es cálculos se án ap oximados e in oduci án e os.
O a amen o das es iccións nos alo es dos pa áme os é moi sinxelo. Só é necesa io
engadi un e mo de penalización á unción cando se es ea a a alia unha solución non
alida.
Como incon enien e, hai que dici que os AX asegu an a con e xencia ó es emo
global pe o nun empo ilimi ado, o que que e dici que nos podemos cansa de espe a e
que o c i e io de e minación se cump a an es de que se acade unha boa es imación da
solución óp ima. Sen emba go, es e p oblema pódese palia en g an medida ealizando
unha implemen ación pa alela, o que esul a sinxelo dadas as ca ac e ís icas do
algo i mo.
45
4 SUPERCUÁDRICAS
As uncións implíci as chamadas supe cuád icas ou supe elipsoides son unha amilia de
supe icies pa amé icas que se ca ac e izan pola lexibilidade que posúen en
con aposición coa simplicidade da súa ep esen ación. Moi os son os au o es que nos
úl imos anos se es án in e esando polo uso des a ep esen ación, ben sexa de modo
único ou combinada con ou os modelos. P oba des o é a mul i ude de aballos
publicados sob e aplicacións que an uso de supe elipsoides, dos que cabe des aca os
de Te zopoulos e Me axas [39, 55], Solina [30, 51], Ba dine [2, 3, 4], e Chen [15] en e
ou os .
Os supe elipsoides son a ex ensión a 3D das igu as 2D coñecidas como supe elipses,
ou supe cuád icas. Es as ob éñense a súa ez como unha ex ensión das cuád icas,
subs i uíndo o expoñen e 2 das ecuacións dunha cu a cónica po unha a iable eal.
Nunha pa ame ización na u al, a supe elipse en a seguin e exp esión
θ
πθπθ
ε
ε
sen
- ,cos
by
ax
=
<≤=
onde o pa áme o ε é un núme o eal posi i o e a e b son os adios sob e os eixes x e y
espec i amen e. Como as uncións igonomé icas coseno e seno poden oma alo es
nega i os, hai que subs i uí-la ope ación de po enciación, de o ma que en odo o ango
de de inición de θ es ea amén de inida a supe elipse no dominio dos núme os eais.
En ón, na exp esión da supe elipse subs i úese a ope ación de po enciación dunha
a iable u a un núme o eal posi i o ε pola seguin e
(
)
ε
ε
uusignou =:
O pa áme o ε coñécese como pa áme o de cuad a u a, pois é o esponsable da o ma
da cu a. Cando ε ende a ce o, a supe elipse ap oxímase a unha igu a ec angula ,
sendo a e b as dimensións dos lados, pa a ε =1 ense a ecuación dunha elipse e pa a ε
=2, a supe elipse é un ombo con a e b como semidiagonais. Pa a alo es maio es os
lados dos ombo anse cu ando ca a ó in e io , o mando unha igu a cónca a con
apa encia de es ela.
Realizando o p oduc o es é ico da supe elipse consigo mesma, ob éñense as ecuacións
do supe elipsoide.
(
)
(
)
() ()
()
θ
πφπφθ
πθπφθ
ε
εε
εε
1
3
21
2
21
1
sen
- ,sencos
2/2/- ,coscos
az
ay
ax
=
<≤=
<≤=

46 CAPÍTULO 4. SUPERCUÁDRICAS
A supe icie que desc iben es as ecuacións pode oma o mas moi di e sas en unción
dos alo es conc e os dos seus pa áme os. O pa áme o ε1 de e mina a cuad a u a nos
planos que con eñen ó eixo z e ε2 nos planos no mais ó eixo z. Se z, ε1 e ε2 son moi
pequenos a supe icie ap oxima ase a un pa alelepípedo, pa a ε1<<1 e ε2=2 emos un
cilind o e con ε1=ε2=2 as ecuacións an e io es co esponden ás dun elipsoide. Pa a
alo es des es pa áme os maio es que 2 a supe icie p esen a conca idades. En
calque a caso, as supe cuád icas semp e son simé icas espec o ós eixes p incipais. A
ecuación implíci a co esponden e é a seguin e:
()
1,
1/2
3
1/2
2/2
2
2/2
1
=








+
















+








=
ε
εε
εε
a
z
a
y
a
x
q
sendo
()
zyx ,,=
o ec o de posición dun pun o sob e a supe icie e
()
21321 ,,,,
ε
ε
aaaq =
o ec o de pa áme os do supe elipsoide.
4.1 Medidas de e o
Pa a pode emp ega os supe elipsoides como esquema de ep esen ación do modelo de
o ma global, é p eciso de ini unha unción de medida do axus e da supe icie ós
pun os da imaxe. Como se comen ou an e io men e, os dous mé odos máis usados pa a
a op imización de uncións implíci as son o que de ine unha unción que es ima a
p obabilidade de que haxa co espondencia e a que emp ega uncións elacionadas coa
dis ancia en e modelo e imaxe. Es a úl ima é a opción escollei a no p esen e es udio
pa a a op imización dos supe elipsoides. Se se dispón dun conxun o de N pun os da
imaxe pe encen es á on ei a do obxec o, a unción E que mide o e o come ido no
axus e dos pa áme os da supe icie, se á a suma das con ibucións D de cada un dos
pun os.
() ( )
∑
=
=N
i
iq DqE
1
2,
O cálculo exac o da dis ancia dun pun o a unha supe icie pode esul a moi cus oso
compu acionalmen e, polo que se soe u iliza unha ap oximación pa a o cálculo de D.
Pa a o caso conc e o das supe cuád icas a p opia ecuación da supe icie pode o ece
unha medida de e o, pos o que a unción
(
)
q
,, pa a alo es posi i os de qi,, é
mono onamen e c ecen e coa dis ancia adial se o pun o pe ence á exión do espacio
que queda ó a da supe icie, e mono onamen e dec ecen e no in e io .
•
()
q ,=1 o pun o es á sob e a supe icie
•
()
q ,>1 o pun o es á no ex e io da supe icie
•
()
q ,<1 o pun o es á no in e io da supe icie
Po es a azón
(
)
q
, é coñecida como a unción in e io -ex e io . Unha análise en
p o undidade des a unción e de como se pode u iliza pa a ob e medidas da unción de
4.1 Medidas de e o 47
e o pódese e mo aballo de Whai e e Fe ie [58]. A unción de e o que se de i a
di ec amen e des a p opiedade é a seguin e:
(
)
1,
1
−
=
q D
Sen emba go es a non é unha boa unción de e o, pois asigna alo es meno es a
supe elipsoides cun alo de ε1 maio . Po es a azón, as supe icies esul an es dun
axus e con es a unción de e o ende án a e unha sección ans e sal máis edondeada
que a supe icie óp ima. Unha unción moi emp egada que educe es e p oblema é D2,
de ínese a pa i da an e io , de xei o que compensa es e compo amen o.
(
)
1,
1
2−= qx D
ε
En ocasións ai se necesa io ealiza-lo axus e sob e imaxes incomple as, nas que non
se dispón de in o mación sob e a o ma dunha pa e da supe icie. Pode da se o caso de
que, po exemplo, nunha zona da imaxe haxa unha pe da de con as e, o que p o oca
que non se de ec e o bo de do obxec o. Nou os casos é p eciso ace unha
econs ucción de obxec os 3D a pa i dunha única is a 2D, polo que hai unha
oclusión da pa e pos e io do obxec o. En ambas si uacións, a u ilización de
supe elipsoides, soluciona es e p oblema de al a de in o mación baixo a hipó ese de
sime ía axial. A pesa des o, a ambigüidade non queda o almen e esol a, xa que pa a
unha imaxe desc i a pa cialmen e pode habe a ias supe icies igualmen e álidas. A
medida de e o D2, sen emba go, ai a alia es as supe icies de dis in o modo,
asignando alo es meno es ás supe icies que ence an un olume maio . Es o débese a
que pun os con igual dis ancia adial á supe icie con ibúen máis se es án no ex e io
que se es án no in e io , polo que o amaño ende á a aumen a pa a ap oxima se ós
pun os do ex e io e compensa es a di e encia. Dado que o habi ual é ealiza hipó eses
de olume mínimo é ecuen e encon a que a medida de e o D2 se modi ica,
engadindo un ac o g(a1,a2,a3) elacionado coas dimensións do supe elipsoide, que
penaliza ás supe icies que ence an un olume maio . No a igo de Solina e Bajcsy
[51] ealízase un es udio emp egando dis in as exp esións pa a o ac o g, pa a chega a
conclusión de que a unción de e o que pe cep ualmen e mello es esul ados da é
(
)
(
)
{
}
1,
1
2/1
3213 −= qx aaaD
ε
Ningunha das uncións p esen adas a a ago a é in a ian e an e ans o macións de
escala. Pa a que se cump ise es a condición necesi a iamos unha medida de e o que
ose unha mé ica euclídea, pe o, como se dixo an es, o cálculo da dis ancia exac a se ía
moi cus oso, debido á g an non linea idade da unción. Unha ap oximación máis
sinxela de calcula , que si é euclídea, é a dis ancia adial δ do pun o á supe icie ( e
igu a 4.1), es udiada po Whai e e Fe ie [58] e po Ba dine e Col. [2]. Se azamos
unha ec a que una o pun o en cues ión co cen o do supe elipsoide, a dis ancia adial
mídese en e os pun os e 0, no que a ec a in e seca á supe icie. Es a dis ancia
pódese calcula acilmen e coñecendo a elación que ga da coa unción .
Da dis ancia adial sabemos que e i ica 0
+=
δ
. Como non coñecemos a
exp esión de 0
, busca emos unha segunda ecuación que a elacione cos e mos
48 CAPÍTULO 4. SUPERCUÁDRICAS
coñecidos. Na igu a 4.1 pódese e que, dado que os pun os o, e 0 son colinea es,
débese cump i que
µ
=
0, sendo µ >0. É ácil comp oba que a unción
() ()
F 2/1
ε
= é homoxénea de o de 1, polo que se en que F(µx, µy, µz)= µF(x,y,z).
Tendo en con a que F(0
)=1, ob emos µ=1/F(x,y,z). Ope ando con es as exp esións
ense
1/2
0
1
ε
δ







+=
Des a exp esión de í ase unha ecuación pa a δ, da que se pode elimina 0
, endo en
con a que 0
+=
δ
()





−== q
D
,
1
11
4
ε
δ
Hai que ecalca que es a úl ima unción de e o sob ees ima a medida exac a da
dis ancia, excep o naqueles pun os onde a di ección da ec a que une o pun o co cen o
do supe elipsoide coincida coa no mal á supe icie en 0
. Con odo, os au o es es án de
aco do en que es a úl ima é a mello es imación do e o do axus e, a pesa de que en
casos especiais poida se con enien e emp ega algunha das ou as.
Po úl imo, é posible ace unha ap oximación de p imei a o de á dis ancia euclídea
exac a, d, como apun a Ba dine en [2], que co esponde a dis ancia medida sob e unha
ec a no mal a supe icie.
(
)
F FD
∇−= /1)(
5
Es a ap oximación é boa an só pa a pun os p óximos á súa p oxección na supe icie,
ou sexa, pa a alo es pequenos de d. Ademais equi e o cálculo do g adien e de F.
4.2 Xene alización pa a posición e o ien ación a bi a ias
Calque a que sexa a medida de e o que se escolla, ai se semp e p eciso o cálculo da
unción in e io -ex e io
()
q ,. Tal e como a p esen amos, es a unción desc ibe unha
igu a cen ada na o ixe do sis ema de e e encia e cos eixes p incipais ó longo dos
eixes coo denados, men es que o obxec o a modela pode es a si uado en calque a
pa e den o do olume da imaxe e cunha o ien ación calque a. Se unha supe icie
desc i a po unha ecuación implíci a non en o cen o na o ixe de coo denadas, e os
eixes p incipais o ien ados na di ección dos eixes coo denados, na ecuación da
supe icie an apa ece no os pa áme os, que a a ago a non se i e on en con a. A
exp esión xe al dos pun os da supe icie ob ense aplicando as ans o macións de
anslación e o ación necesa ias pa a si uala p imi i a nunha posición e o ien ación
xené icas.
4.3 Ambigüidade na ep esen ación median e supe elipsoides 49
Pa a de e mina-la ans o mación T que hai que aplica ó supe elipsoide pa a que se
supe poña co obxec o na imaxe, ou sexa, pa a pasa o supe elipsoide do sis ema de
e e encia da imaxe a ou o cen ado no obxec o, se á necesa io in oduci os
pa áme os co esponden es no p oceso de op imización, polo que, ós cinco pa áme os
de o ma do supe elipsoide, habe á que engadi os es de anslación, 1, 2, e 3, máis os
es ángulos de Eule , α, β e γ que desc iben a o ación.
()
γ
β
α
ε
ε
,,,,,,,,,,' 32132121 aaaq =
T ans o ma o supe elipsoide espec o á imaxe pa a supe poñe-la co obxec o, equi ale
á ealiza-la ans o mación in e sa sob e a imaxe pa a supe poñe-lo obxec o co
supe elipsoide. Se ’ é o pun o da imaxe dado no sis ema de e e encia cen ado no
obxec o, en ón hai que subs i uí
(
)
q
, na unción de e o seleccionada po es a ou a
exp esión
()
(
)
(
)
(
)
(
)
q q T q q
,',',,
ˆ1=== −
Des e xei o pódense inco po a no as ans o macións á de inición da supe icie, como
e emos máis adian e, cando apliquemos de o macións globais ó supe elipsoide.
4.3 Ambigüidade na ep esen ación median e supe elipsoides
Na sección dedicada ós dis in os esquemas de ep esen ación adian abamos xa que os
supe elipsoides xene alizados non cump en a p opiedade de unicidade. As sime ías de
o ación que ca ac e izan an o a cuád icas como a supe cuád icas, que p o ocan unha
ambigüidade na de e minación dos ángulos de Eule . O caso máis cla o é o da es e a,
pa a a cal os ángulos de Eule es án o almen e inde e minados. Coa igu a do cubo,
calque a o ación de 90º espec o ós eixes p incipais da luga a un no o alo álido do
ángulo de Eule . En xe al, calque a ou a o ma do supe elipsoide p esen a á polo
menos sime ía an e calque a o ación de 180º en o no ós eixes p incipais.
Pe o as sime ías non son as únicas on es de ambigüidade da ep esen ación. Tamén é
posible ob e o mas idén icas a iando os alo es dos pa áme os de cuad a u a. A
o ixe des e compo amen o es á en que os alo es ε<<1 e ε=2 na ecuación da
supe elipse, da que se de i a o supe elipsoide, co espóndense espec i amen e co
Figu a 4.1 Dis ancias adial, δ, e no mal, d, dun pun o a unha supe icie.
56 CAPÍTULO 4. SUPERCUÁDRICAS
(
)
ϕ
θ
γ
β
α
ε
ε
,,,,,,,,,,,,,,, 32121321 kCC aaaq yx
=
Pa a unha imaxe dada, a ob ención do modelo pa icula a ase emp egando algunha
das uncións de e o desc i as nes a sección pa a o axus e ós pun os de on ei a. O
mé odo de axus e da unción elixida que se ai u iliza nes a ocasión é un algo i mo
xené ico que, como se demos a en [31], esul a moi axei ado pa a es e ipo de
uncións.
No capí ulo 3 íxose unha in oducción ós AX, da que se concluíu que é un algo i mo
de op imización global moi obus o, pe o que o seu empo de con e xencia pode se
excesi o. Como a aplicación a desen ol e non es á pensada en p incipio pa a sis emas
dinámicos, a apidez non é aquí unha p io idade. Sen emba go, exis e un se ie de
a iacións sob e o AX básico, que de seguido se an a especi ica , que pe mi en
axiliza o p oceso sen a ec a subs ancialmen e os seus p incipios de uncionamen o,
man endo ódalas p es acións do AX máis sinxelo.
U ilizando algo i mos xené icos emos unha g an libe dade á ho a de especi ica cales e
como an se-los mecanismos e olu i os. Xa só do ope ado de ecombinación pódense
implemen a a ias e sións, que se án máis ou menos axei adas segundo o ipo de
p oblema a a a . Ademais, non exis e unha no ma que nos indique como ixa ce os
pa áme os do algo i mo, como o núme o de indi iduos da poboación, p obabilidades
de c uzamen o e mu ación, po cen axe de indi iduos que se ep oducen, e c., polo que a
elección des as magni udes se a á de o ma empí ica.
O esquema de c eación dunha no a xe ación de indi iduos inclúe a aplicación de
ope ado es de ep oducción, mu ación e c uzamen o. No aballo que aquí se p esen a,
expe imén ase con es a ian es do c uzamen o, que se di e encian no núme o de
pun os polos que se secciona un pa de c omosomas pa a a ecombinación: po un
pun o, po dous pun os e uni o me, onde cada xene do c omosoma se pode in e cambia
independen emen e dos demais. Es e úl imo ope ado en o incon enien e de que non
a o ece a o mación de bloques cons i uín es, dada a ele ada agmen ación dos
c omosomas, o que di icul a a he danza da in o mación con ida nos c omosomas
dunhas xe acións a ou as.
4.6.1 Codi icación
Decididos os ope ado es a emp ega , o p imei o e posiblemen e máis impo an e
aspec o a conside a é como codi ica o ec o de pa áme os do modelo. Pa a da coa
codi icación máis axei ada habe á que e en con a o seguin es ac o es:
• como a ec a o ipo de codi icación, é dici , que sexa bina ia, eal, e c., á
e iciencia dos ope ado es xené icos. Es a e iciencia es a á elacionada coa
capacidade pa a xe a esquemas ú iles;
• como in lúe na e iciencia a o denación dos pa áme os na cadea;
Pos o que os algo i mos xené icos cons i úen un mé odo de op imización moi obus o, o
ipo de codi icación que se manexe, non a ec a á á e ec i idade do algo i mo, pe o si a
e iciencia. Po exemplo, coas codi icacións eal e bina ia os ope ado es xené icos
implemén anse de o ma dis in a. Se unha a iable es á ep esen ada po un núme o

4.6 Op imización con algo i mos xené icos 57
eal, ese núme o cons i ui á po si só un xene do c omosoma, mes es que na
codi icación bina ia, cada un dos bi s equi ale a un xene. Es o ai que a
implemen ación dos ope ado es xené icos pa a a codi icación bina ia sexa máis sinxelo,
pos o que a ep esen ación como unha es a de bi s pe mi e que se modi ique un único
bi ou que se seccione en dous anacos o pa áme o. Es o non é posible coa codi icación
eal, pa a o que hai que de ini ope ado es máis complexos, como os que p opón
Kalyanmoy en [27].
Unha opción mello incluso que a codi icación bina ia é a u ilización do código G ay
[25, 27]. A an axe espec o ó código bina io no mal adica en que dúas cadeas de bi s
que ep esen an núme os consecu i os di e éncianse en un e só un bi . Des a o ma, a
modi icación dun bi da cadea que ep esen a o c omosoma, en semp e a mesma
epe cusión, independen emen e de en que posición da cadea es ea si uado di o bi nin,
dos alo es que nese momen o eñan o es o de bi s. Non sucede así co bina io no mal,
onde pa a pasa do alo 7 ó 8, hai que modi ica os 3 p imei os bi s e sen emba go
pasa de 1000 a 1100 implica a ia o alo da cadea en 8 unidades decimais. Es o
p o oca que haxa in e acción en e os xenes. A in e acción, en ocasións chamada
epis ase, en e os xenes consis e en que a con ibución dun xene á unción de
adap ación depende do alo de ou os xenes.
No que espec a á o denación dos pa áme os na cadea, é impo an e que se aga de
modo que as a iables que es án elacionadas en e si se si úen en localizacións
con iguas, pois es a é a manei a de que os esquemas co esponden es a es es xenes
sob e i an ó c uzamen o. Se se a opasen moi sepa ados na cadea co e ían maio isco
de se en sepa ados. O p oblema é que moi as eces es as elacións en e os pa áme os
non son coñecidas. Ou as eces exis en demasiadas in e elacións en e as a iables
como pa a pode xun alas a odas adecuadamen e. En ón o obxec i o se á busca a
colocación óp ima.
4.6.2 Rendemen o do AX.
Ou o aspec o a e en con a no deseño do algo i mo xené ico é a elección de
pa áme os coma o amaño da poboación, que é o núme o de indi iduos po xe ación,
ou a p obabilidade de que, unha ez seleccionados os indi iduos que an in e i nunha
ope ación de mu ación ou c uzamen o, es a sexa e ec i a. Na escolla des as can idades
habe á que es udia o seu e ec o an o na e icacia como no endemen o do algo i mo,
que, coma semp e, se án obxec i os en con lic o. No caso do amaño da poboación
sucede que, can o maio é es a, maio p obabilidade exis i á de da coa solución
co ec a, pos o que habe á un maio núme o de esquemas en xogo, o que se aduce
nunha explo ación máis ampla do espacio de busca. Pe o, po ou a pa e, a poboación
a da á máis en con e xe ca a a exión de unción de adap ación al a, pois habe á que
i eliminando un g an núme o de esquemas non adap ados. Coa p obabilidade de
mu ación sucede algo pa ecido. Se é moi baixa, ealiza ase unha explo ación p eca ia
do espacio. Lemb emos que a mu ación encá gase de xe a no os esquemas den o da
poboación, e se es o non se p oduce en su icien e medida, a poboación es anca ase, non
habe á e olución. Pola con a, se a mu ación se p oduce con demasiada ecuencia,
pode sucede que esquemas moi adap ados desapa ezan empo almen e ou a den en
domina na poboación, o alen iza ía o p oceso.
58 CAPÍTULO 4. SUPERCUÁDRICAS
No es udio ealizado po De Jong [16], no que se es a on di e sas con igu acións do
AX na op imización dun conxun o de uncións de ca ac e ís icas di e sas, puido
comp oba se que os mello es esul ados se ob eñen pa a amaños da poboación
mode ados, p obabilidade de c uzamen o ele ada e p obabilidade de mu ación baixa,
da o de da in e sa do núme o de indi iduos da poboación, o que co esponde ía a unha
media de unha mu ación po xe ación. Mello es es imacións des es pa áme os se
poden es ablece en base a cálculos es a ís icos pa a p oblemas conc e os, como ixo
Kalyanmoy [27] pa a o cálculo da poboación inicial.
4.6.3 Mecanismos de selección
A con e xencia do AX es á supedi ada á co ec a simulación do p incipio de
supe i encia dos máis adap ados. A manei a máis común de simula es e
compo amen o é a de pe mi i unha maio in e ención dos indi iduos con maio
unción de adap ación nos p ocesos esponsables da c eación das sucesi as xe acións.
O modo máis simple se le a es o a cabo é asigna a cada c omosoma unha
p obabilidade de se seleccionado como pai dun no o c omosoma que sexa
di ec amen e p opo cional ó seu g ao de adap ación, no caso do p oblema da
maximización da unción de e o –un p oblema de minimización pode ans o ma se
acilmen e nun de maximización subs i uíndo a unción pola súa in e sa -. Es e o que
se chama esquema de selección de ule a ( oule e wheel) ou amén mos axe
es ocás ica con eposición. Pe o os AX que u ilizan es e mé odo adoecen dun descenso
p ema u o da a iedade de esquemas na poboación. As causas des e compo amen o
son, po un lado, o ei o de que non se pode medi o alo p omedio da unción de
adap ación pa a un esquema de e minado, e po ou o, que o núme o de eces que un
indi iduo in e én nos p ocesos e olu i os p esen a unha g an des iación espec o ó
núme o que se es ima que é o co ec o, debido a que en cada selección non se en en
con a cales o on as seleccións an e io es.
Exis en múl iples esquemas de selección que en an esol e es es p oblemas. No lib o
de Goldbe g [25] ealízase unha compa ación de a ios des es esquemas. Un mé odo de
selección que en a palia es e úl imo p oblema é o modelo de alo espe ado, amén
chamado mos axe es ocás ica sen eposición, pa a di e encialo do esquema de ule a,
pois ago a, a medida que un indi iduo ai sendo seleccionado pa a o c uzamen o, ai
pe dendo posibilidades de ol e a selo. Es o lé ase a cabo calculando pa a cada
indi iduo o núme o de descenden es que debe e como a súa p obabilidade de
selección pi= i/ media, e cada ez que sae elixido pa a c uza se, és aselle 0.5 se o
c uzamen o é e ec i o e 1.0 se non o é. Es e mé odo educe de conside ablemen e a
pe da p ecoz de esquemas.
Ou o mé odo de selección moi popula é o o neo ( ou namen selec ion). Consis e en
oma oda a poboación e di idila en g upos de n indi iduos. De cada g upo escóllese o
máis adap ado pa a pa icipa nos p ocesos de ecombinación. Habi ualmen e os
indi iduos compi en po pa ellas. Des e xei o asegú ase que o máis adap ado da
poboación pa icipe na o mación da seguin e xe ación. Unha a ian e de es a écnica,
chamada selección de o neo p obabilís ico (p obabilis ic ou namen selec ion),
pe mi e que nas p imei as xe acións exis a unha p obabilidade de que o menos
4.7 Pos a en co espondencia con modelos a p io i 59
adap ado dos dous indi iduos saia elixido. Es a p obabilidade ai descendendo a
medida que e oluciona o sis ema, de o ma simila a como o ai o empe ado simulado.
4.6.4 Función de adap ación
A p obabilidade que se lle asigna a un indi iduo de o ma pa e na c eación dunha
no a xe ación, ai depende unicamen e da súa unción de adap ación. Se emp egamos
unha écnica de selección p opo cional ó alo da unción de adap ación e na poboación
inicial apa ecen indi iduos cunha adap ación moi al a, aínda que non es ean ce ca do
óp imo, de con ado domina án a poboación, con ibuíndo de no o á pe da de esquemas
e polo an o educindo o g ao de explo ación do espacio de busca. Po es a azón é
p ác ica habi ual ealiza un ans o mación das mediadas de e o. A o ma máis sinxela
é ealiza unha o denación po adap ación dos indi iduos, chamada anking. Sendo ’ a
unción de adap ación ans o mada, ’max e ’min as co as do in e alo ó que se mapea ,
e ank(i) a unción que da a posición do indi iduo i nunha o denación descenden e con
, en ón:
()
min
minmax ' ank
1
''
' i
N
−
−
−
=
Tamén se soe ace unha no malización linea
(
)
(
)
iN ank'
−
⋅
=
σ
en unción da des iación es ánda σ dos alo es de , sendo N o núme o de indi iduos
da poboación.
4.7 Pos a en co espondencia con modelos a p io i
O p ocedemen o que se acaba de desc ibi pa a a ob ención dos pa áme os da ecuación
implíci a é igualmen e álido pa a a econs ucción dun modelo e pa a a pos a en
co espondencia en e o obxec o nunha imaxe e un modelo a p io i. A única di e encia
es á en que no segundo caso o núme o de pa áme os a de e mina é meno , pois oda a
in o mación asociada á o ma da supe icie pode se “ eciclada”. En ón a op imización
ese educida ó cálculo dos pa áme os de ans o mación íxida: anslación, o ación e
escalado e un no o pa áme o de escalado, a0, que se in oduce nas ecuacións do
supe elipsoide do seguin e xei o.
(
)
(
)
() ()
()
θ
πφπφθ
πθπφθ
ε
εε
εε
1
30
21
20
21
10
sen
- ,sencos
2/2/- ,coscos
aaz
aay
aax
=
<≤=
<≤=
O obxec i o que nos p opuxemos nes e aballo, a inicialización de supe icies
de o mables, pode abo da se median e a segunda das dúas a e as. Es o equi e da
de inición do modelo a p io i, pe o a econs ucción des e modelo a ase só unha ez.
Pa a que o modelo sexa ep esen a i o da clase de obxec os cos que ai aballa , é
60 CAPÍTULO 4. SUPERCUÁDRICAS
p eciso u iliza algún ipo de écnicas es a ís icas pa a a súa ob ención. É usual u iliza
pa a a op imización da supe icie a p io i unha imaxe p omedio do obxec o, calculada a
pa i dun conxun o de imaxes de p oba. Tamén é in e esan e a u ilización dun modelo
PCA, o que equi i ía, ademais da op imización dos pa áme os de ans o mación
íxida, os pesos da combinación linea de modos de a iación p incipais. Es a écnica
pode se especialmen e ú il cando se conside e que o modelo p omedio non é
su icien emen e ep esen a i o do conxun o de imaxes de p oba, é dici , cando os
di e sos exempla es do obxec o p esen en unha g an a ianza. Ou a opción é emp ega
como modelo a p io i o modelo medio, pe o pe mi indo na pos a en co espondencia a
a iación dos pa áme os de o ma, ou sexa, ans o macións globais non íxidas, aínda
que aquí se a ía de o ma moi limi ada.
En ambos casos, pa a a ex acción da colección de pun os sob e os que se axus a á o
modelo a p io i, é p eciso poñe en co espondencia as imaxes do conxun o de p oba.
Calque a dos mé odos comen ados na sección 3.2.1 pa a pos a en co espondencia en e
dis ibucións espaciais de pun os pode se u ilizada nes a ocasión.
61
5 EXTRACCIÓN DE PARCHES DE SUPERFICIE
A a ago a íxose unha desc ición bas an e de allada da econs ucción dos
supe elipsoides a pa i dos pun os da imaxe, pe o en ningún momen o se ixo mención
a como se e ec úa a selección de pun os que in e eñen na op imización. Nes e capí ulo
explícanse os p ocesos de baixo ni el emp egados, os cales o ece án como esul ado
unha dis ibución de pun os de on ei a, que se án os que se emp eguen pa a o cálculo
das dis ancias á supe icie do modelo.
Unha das solucións máis comunmen e usadas pa a a de ección de pun os de on ei a en
2D é o il ado espacial pa a a es imación das de i adas di eccionais dos ni eis de g is
das imaxes. Nes a ocasión débese abo da-la a e a do il ado en imaxes olumé icas, e
en ón debemos p egun a nos a a que pun o a ap oximación 2D se pode es ende ó ipo
de imaxes 3D que imos manexa ga an indo a calidade dos esul ados. O p oblema que
apa ece é que as imaxes médicas, como po exemplo as p o enien es de CT, non son
e dadei amen e 3D, senón un conxun o apiado de imaxes 2D. A epe cusión que es e
ei o en sob e a calidade dos da os é e iden e. Todo depende á da esolución na
di ección axial que se o eza, pe o xe almen e obse a ase que a ecuencia de
mos axe nesa di ección se á in e io que nas di eccións con idas no plano das imaxes
2D, dando luga a descon inuidades nos alo es de in ensidade ó pasa dun co e ó
seguin e. Cando a dis ancia en e co es non é excesi a pódese e ec ua unha
in e polación que xe e imaxes en planos in e medios, o que da ía maio con inuidade á
secuencia.
A pesa des e incon enien e, o mé odo que se aplica pa a o il ado 3D das imaxes
nes e aballo é unha ex ensión di ec a do il ado 2D. Pa a soluciona o p oblema que
acabamos de ci a , considé ase que un sua izado p e io é su icien e. O mo i o polo
que, a pesa de odo, se elixe es e ipo de de ección, é que a ex ensión de il os 1D a
il os 3D sepa ables poden se implemen ados de o ma ecu si a. Des e xei o, o
empo de compu ación ese educido de o ma impo an e en elación co
co esponden e á con olución cunha másca a no dominio espacial, e dado o olume de
da os manexados en imaxes 3D, es a idea esul a moi a ac i a.
A con inuación a ase unha desc ición dos il os ecu si os. Es es il os son
emp egados pa a o sua izado e a es imación das p imei as e segundas de i adas
di eccionais de cada pun o da imaxe. As de i adas p imei as u ilízanse pa a o cálculo
da posición dos máximos do g adien e, nos que se localiza án os pun os de on ei a.
Unha ez localizados os pun os de on ei a, p ocede ase a ag upalos en pa celas de
supe icie. Como an a exis i múl iples es uc u as na imaxe, e como ademais a
supe icie do obxec o de in e ese pode apa ece agmen ada, ai se necesa ia unha
e apa de selección dos pa ches que in e i án no axus e do modelo. Aquí é onde
in e én o cálculo das de i adas segundas di eccionais, que an se i pa a a
es imación das cu a u as ex emas locais de cada pa che de supe icie. A pa i des es

62 CAPÍTULO 5. EXTRACCIÓN DE PARCHES DE SUPERFICIE
cálculos é posible ex ae algunha medida que poida se i como desc ip o da o ma
dos pa ches. Con es as e ou as ca ac e ís icas que se poden ob e pa a cada pa che,
es ablécese un c i e io de selección. A ex acción e selección de pa ches de supe icie
de állase na sección 5.4.
5.1 Fil os mul iescala ecu si os
Nes a sección desc íbese en de alle a implemen ación u ilizada pa a o il ado
enca gado de es ima as p imei as e segundas de i adas di eccionais das imaxes.
Es udia anse dúas ap oximacións di e en es, pa a as que se le a á a cabo unha
compa ación das p es acións que o ece cada unha no capí ulo de esul ados. Ambas
ap oximacións ep esen an uncións de espos a de impulso dependen es de pa áme os
asociados á escala do il o, de modo que poidan se u ilizados con imaxes de dis in o
ipo e dis in as ca ac e ís icas de uído. En ambos casos a ase unha implemen ación
ecu si a da unción co obxec i o de educi o empo de cálculo das imaxes il adas.
5.1.1 Fil os mul iescala
As ca ac e ís icas que se lle esixen a un il o de de ección de pun os de on ei a
dependen do uso que se lle quei a da . Un il ado axei ado pa a a de ección de
es uc u as nunha imaxe se á con ecuencia pouco ap opiado pa a a boa localización e
de ección de pun os de on ei a a ni el local. No p imei o caso p ecisase un il o que
poida cap a in o mación ele an e na imaxe, men es que no segundo a án al a
ope ado es que p ese en as pequenas es uc u as sen al e a a súa o ma. É dici , que
dis in os ni eis de abs acción equi en il ados a di e en es escalas. Ademais, un
obxec o eal soe mani es a ca ac e ís icas que que se mani es an a escalas di e en es,
polo que a escala ideal pode a ia ó longo do con o no. En calque a caso, nas
aplicacións máis usuais, como a que aquí se p opón, a desc ición median e unha única
escala é su icien e.
Nes e aballo aplicá onse, an o pa a o sua izado das imaxes como pa a o cálculo das
de i adas p imei as e segundas, dúas amilias de il os moi u ilizadas en il ado
mul iescala polas boas p es acións que o ecen pa a es e ipo de a e as. Po unha pa e,
es án o il o de gaussiana e as súas de i adas [20]. O il o de de i ada de gaussiana,
que pa a o caso unidimensional con des iación es ánda σ én dado pola exp esión
seguin e, pe mi e unha al a sup esión de uído ademais da boa localización dos pun os
de on ei a. Se n é unha a iable disc e a
()
22 2/
2
2
1
σ
πσ
n
eng −
=
Po ou a pa e, u ilizá onse ou a amilia de il os que se de i an dun il o de
de ección de pun os de on ei a deseñado u ilizando o c i e io de Canny [11] es endido
a il os in ini os, que o ece unha exp esión analí ica pa a un il o xené ico
unidimensional de inido no dominio con inuo, (x), dadas unha se ie de especi icacións
en elación ós seguin es c i e ios:
5.1 Fil os mul iescala ecu si os 63
• boa de ección, asegu ando unha baixa p obabilidade de de ección dun also
pun o de on ei a e ó mesmo empo unha baixa p obabilidade de allo na
de ección dun pun o de on ei a e dadei o. Dado que ambas p obabilidades
son mono onamen e dec ecen es coa elación sinal- uído, SNR (Signal o Noise
Ra io), o c i e io de boa de ección sa is a ase coa maximización desa
magni ude. Se g(x) é un sinal unidimensional calque a cun pun o de bo de
si uado en x = 0, co ompida po uído gaussiano b anco de ampli ude media
po unidade de lonxi ude n0, a SNR i á dada po :
(
)
(
)
()
()
2/1
2
0∫
∫−
=dxx n
dxx xg
SNR
• boa localización, de xei o que a posición na que se si úe a on ei a de ec ada
do obxec o es ea o máis p óxima posible ó cen o do bo de, median e a
maximización dun ac o de localización, Λ.
(
)
(
)
()
()
2/1
2
0'
''
∫
∫−
=Λ dxx n
dxx xg
onde o após o e indica que se es á omando a de i ada p imei a da a unción
co esponden e espec o da a iable independen e x.
• espos a única, de manei a que a espos a do il o an e un sinal uidoso non
eña demasiados máximos a edo do pun o de bo de. Pa a eso o que se ai é
limi a-la dis ancia media en e dous picos da espos a do il o an e un sinal de
uído gaussiano, ou o que é o mesmo, en e dous pun os de c uce po ce o da
de i ada segunda
()
(
)
()
()
2/1
2
2/1
2
0''
'
∫
∫
=dxx
dxx
x
π
sendo ’’ a de i ada segunda de espec o de x.
Aplicando es es c i e ios pa a a op imización dun il o de de i ada p imei a (x)=h’(x)
de segunda o de, De iche [18, 19] deseñou unha amilia de il os dende o il o de
sua izado, h(x) a a o de de i ada e cei a. As exp esións co esponden es ó il o de
sua izado e ás de i adas p imei a e segunda, nas súas e sións disc e izadas, son as que
seguen.
()
()
(
)
(
)
(
)
nnn enkkxhnekxhenkxh
ααα αα
−−− −==+= 2310 1'' ' 1
onde os pa áme os k0, k1, k2 e k3 son ac o es de no malización. k0 én dado pola
condición
64 CAPÍTULO 5. EXTRACCIÓN DE PARCHES DE SUPERFICIE
()
∑
∞
−∞=
=
n
nh 1
As exp esións de k1, k2 e k3 escóllense de modo que h’ e h’’ eñan espos a nula an e
unha en ada cons an e, esixindo ademais que
()
∑
∞
−∞=
=
n
nh 0''
As exp esións esul an es son:
()
(
)
1
2
1
1
21
1
3
2
2
2
1
2
2
0=
−
=
−
−=
−+
−
=−
−
−
−
−−
−
k
e
e
k
e
e
k
ee
e
k
α
α
α
α
αα
α
αα
Es es il os eñen dados en unción dun pa áme o α elacionado coa escala á que
ope a o il o, polo que a es e il o se lle chama il o al a. Se o il o de sua izado de
gaussiana e o al a se deseñan de modo que eñan a mesma ene xía o al, e i ícase a
elación α·σ=5/2√π. Valo es ípicos de α es án en e 0.5 e 1.5.
5.1.2 Implemen ación ecu si a dos il os
Tan o pa a a amilia de il os gaussianos [20], coma pa a os il os al a [17], ealizouse
unha implemen ación ecu si a con obxec o de educi-lo núme o de ope acións po
pun o da imaxe. A exp esión que elaciona o alo dun elemen o de saída do il o cos
elemen os de en ada, dado pola seguin e con olución,
() ( )( )
∑
−
=
−= 1
0
N
k
kixkhiy
non é ecu si o. N é o núme o de elemen os da secuencia de espos a de impulso. Es e
amaño de másca a do il o pode esul a excesi o se se desexa ob e boas p es acións
en can o a localización e de ección. Pa a a implemen ación, po exemplo, do il o de
gaussiana, débese oma un alo de N que sexa alomenos da o de de 4σ, sendo σ a
des iación es ánda da gaussiana, pa a que o eza bos esul ados. A idea do il ado
ecu si o é deseña un il o que eña un compo amen o equi alen e ó il o de
con olución, ou polo menos que se ap oxime o su icien e, pe o que eña desc i o pola
seguin e ecuación de di e encias
() ( )
)(
1
1
0
kiyakixbiy
n
k
k
m
k
k−⋅−−⋅= ∑∑ =
−
=
Con es a exp esión edúcese o núme o de ope acións necesa ias pa a ob e un alo da
secuencia esul an e de N a n+m, polo que o empo de compu ación dec ece de o ma
impo an e, xa que bas a oma alo es moi pequenos de n e m pa a ob e boas
ap oximacións. Habe á que de e mina os alo es de k
a e k
bda unción de
ans e encia do sis ema ecu si o
5.1 Fil os mul iescala ecu si os 65
()
()
()
∑
∑
∑
=
−
−
=
−−
∞
=
−−
⋅+
⋅
== n
k
k
k
m
k
k
k
n
n
RR
za
zb
znhzH
1
1
0
1
0
1
1
de manei a que o seu compo amen o sexa igual ó do il o non ecu si o, ou, polo
menos, se ap oxime o su icien e de aco do con algunha medida de e o. Aquí aplícase
un c i e io de minimización do e o ó cad ado, onde o e o én dado po :
() ()()
2
0
2∑
∞
=
−=
k
Rkhkh
ε
sendo
()
khR a espos a de impulso do sis ema ecu si o.
Fil os al a
No caso da ap oximación ecu si a dos il os al a, sucede que a unción de
ans e encia asociada pódese implemen a de o ma exac a median e a ecuación de
di e encias an es p esen ada. As ecuacións de di e encias pa a un elemen o de saída
y(n) do il o de sua izado son
()
(
)()
(
)
[
]
(
)
(
)
() ( )( ) ( )
[]
() ( )
() () ()
nynyny
nyenyenxenxekny
nyenyenxenxkny
21
2
2
2
2
12
1
2
101
212211
21211
+=
+−+++−++=
−−−+−−+=
−−−−
−−−
αααα
ααα
α
α
Des a o ma é posible implemen a un il o de sua izado ealizando 8 mul iplicacións
e 7 sumas, independen emen e do alo de α, men es que cun il o non ecu si o se ía
p eciso un núme o de ope acións p opo cional ó amaño do il o. A modo de exemplo,
un il o de 16 bi s de amaño de másca a con α=0.5 necesi a ía 57 ope acións, men es
que con 0.25 se ían 113.
As ecuacións do il o de de i ada p imei a, pola súa pa e, p ecisan an só de 5
ope acións an o de p oduc o como de suma po elemen o de saída.
() ( )
(
)
(
)
()() () ( )
() () ()
[]
nynyekny
nyenyenxny
nyenyenxny
211
2
2
22
1
2
11
2121
2121
−=
+−+++=
−−−+−=
−
−−
−−
α
αα
αα
As ecuacións de di e encias u ilizadas pa a a es imación da de i ada seguin e implican
7 ope acións de suma e 7 de mul iplicación po elemen o de saída, e son as que seguen.
()
(
)( )
(
)
(
)
(
)
() ( )() ( ) () ( )
() () ()
nynyny
nyenyenxenxkeny
nyenyenxkenxny
21
2
2
2
2
2
1
2
11
212211
21211
+=
+−+++−+−=
−−−+−+−=
−−−−
−−−
αααα
ααα
α
α
Fil os de gaussiana
72 CAPÍTULO 5. EXTRACCIÓN DE PARCHES DE SUPERFICIE
A unción ecu si a busca_pun os_adxacen es ai o seguin e:
En ada: úl imo_pun o, supe icie
Pa a cada pun o adxacen e a úl imo_pun o ace
Se pun o oi pe co ido con inua
Ma ca pun o como pe co ido
Se g is(pun o) < g is_umb al_meno con inua
Engade pun o á lis a de pun os de supe icie
Aumen a a á ea da supe icie nunha unidade
úl imo_pun o ← pun o
Busca_pun os_adxacen es(úl imo_pun o, supe icie)
Fin
Fin
Unha ez ema ado es e p oceso dispoñemos xa dunha o ganización da in o mación de
máis al o ni el que a apo ada pola imaxe de ni eis de g adien e de g is. Pe o de
momen o as p opiedades que se desc iben, an o o modulo de g adien e de ni el de g is
como as cu a u as, seguen sendo de ca ác e local, pois an asociadas a pun os
indi iduais da imaxe, polo que non é posible ace unha disc iminación de pa celas de
supe icie. Do que se a a ago a é de ope a sob e a no a desc ición en o ma de
es uc u as de supe icie pa a de e mina p opiedades ela i as, non a cada pun o po
sepa ado, senón ó conxun o de odos eles. Des a o ma seguimos subindo no ni el de
abs acción, chegando a unha desc ición que pe mi i á disc imina os pun os do
obxec o a modela .
5.4.2 Selección de pa ches de supe icie
As e ique as que se asignan a cada pa che de supe icie, eñen dadas como unha
unción das súas ca ac e ís icas. Nes e aballo es udiamos un núme o educido delas
pe o o mé odo é ex ensible a calque a ipo de e ique ado. As ca ac e ís icas que aquí se
manexan son as seguin es:
Á ea. Considé ase que emp egando il os que ope en a escala adecuada, as
pa celas de supe icie máis pequenas co esponden a uído, e poden se desca adas. É
posible que con es e c i e io se es ean eliminando anacos de pequeno amaño da
supe icie do obxec o de in e ese, pe o que non eñen peso no esul ado inal.
Ni el de g adien e de g is p omedio. In o ma da magni ude da a iación do
ni el de g is. Es a a iación pode se baixa cando é moi g adual, pe o amén cando se
p oduce un sal o moi b usco en e exións de ni eis de g is moi p óximos. De manei a
que desca a pa ches con ni el de g is p omedio baixo, podemos es a eliminando as
supe icies de in e ese. Es o, xun o co ei o de que soe habe máis dunha es uc u a
p esen e na imaxe, an que a a medida do g adien e p omedio non sexa su icien e pa a
disc imina pa ches dun de e minado obxec o.
Cu a u as media e gaussiana. Apo an in o mación sob e a o ma local
dunha supe icie. De ínense a pa i das cu a u as p incipais que na sección 5.3 o on
calculadas. Sendo k+ e k- os alo es das cu a u as p incipais nun pun o da supe icie, a
cu a u a media H e a cu a u a gaussiana K eñen dadas po :

5.4 Ex acción de pa ches de supe icie 73
−+
−+ ⋅=
+
=kkK
kk
H
2
Os alo es des es desc ip o es en cada pun o da supe icie dan unha idea ap oximada da
mo oloxía local. A cu a u a gaussiana u ilízase pa a sabe se as cu a u as p incipais
eñen o mesmo signo. Ap oximando a supe icie localmen e a unha unción cuad á ica
pódese es ablece a seguin e clasi icación
• K > 0, elipsoide
• K < 0, hipe boloide
• K = 0 e H ≠ 0, cilind o
• H = K = 0, plano
Pola súa pa e a cu a u a media in o ma sob e a con exidade da supe icie. Asumindo
que as exións de ni el de g is al o co esponden ó in e io dos obxec os e os ni eis de
g is baixos ó ex e io , en ón a cu a u a local nunha di ección de e minada se á
posi i a cando a supe icie sexa cónca a nesa di ección. Tendo es o en con a, o c i e io
pa a de e mina a con exidade da supe icie é o que segue
• H > 0, supe icie cónca a
• H < 0, supe icie con exa
• H = 0 e K ≠ 0, pun o de sela
• H = K = 0, plano
Tan o a cu a u a media como a gaussiana pe mi en dis ingui en e a ias clases de
supe icies, indicando como é a súa cu a u a, pe o non can o. Pa a apo a unha
clasi icación cuali a i a das supe icies debemos in oduci unha no a medida, que a
con inuación se de ine
22
−+ += kkKm
Con es as cinco magni udes que se acaba de de ini xa podemos dispo dunha idea
ap oximada das p opiedades da supe icie en cada pun o. Sen emba go, non son as
p opiedades locais as que in e esan, pois qué ese e ique a-los pa ches de supe icies,
non os pun os de o ma indi idual. As medidas que ealmen e se u ilizan pa a clasi ica
unha supe icie segundo a súa o ma, es a án un p omediadas a ódolos pun os de
on ei a dunha pa cela. A u ilidade das medidas de cu a u a p omediadas es a á
limi ada a pa ches de pequeno amaño ou g andes supe icies moi egula es. Cando,
como esul ado do il ado da imaxe se ob én oda a supe icie dos obxec os, se es es
eñen unha o ma moi complexa, ó p omedia os desc ip o es de o ma pe de án o seu
signi icado. Nes es casos bas a unha clasi icación po á ea e g adien e pa a a selección
dos obxec os.
En unción de odas es as medidas pódese de ini unha e ique a que ep esen e a clase
de pa che que emos. No aballo de Pa do e Cabello [44] suxí ese unha exp esión pa a
o cálculo da e ique a, aplicada o caso 2D, baseada nos alo es do g adien e p omedio e
da lonxi ude dos segmen os de bo de. A exp esión, que asigna alo es maio es a
74 CAPÍTULO 5. EXTRACCIÓN DE PARCHES DE SUPERFICIE
segmen os de cu a S con alo es do p omedio do módulo do g adien e e da lonxi ude l
maio es, é a seguin e:
() ()
2/1
2
1lpI
l
SE
i
Sk
ki 




∇= ∑
∈
sendo pk os pun os de con o no e I o g adien e. A exp esión que se u ilizou nes e
es udio é unha ex ensión da an e io a 3D, á que se lle engaden ac o es que eñen con a
das medidas de cu a u a an e io men e ci adas.
Dependendo do ipo de obxec o que haxa que segmen a habe á que inco po a á
ó mula ac o es elacionados coa cu a u a gaussiana e media dun ou dou o xei o. En
can o a Km pedi áselle usualmen e que sexa o meno posible, pois as supe icies
o ixinadas polo uído soen se moi ugosas. Se se dispón de coñecemen o sob e os
alo es de Km espe ados pódense in oduci na exp esión da e ique a. A exp esión
xené ica da e ique a dun pa che P én dada po :
()
()
caso nou o
,
2/12
max





−
=
=
CK
HK
ag
CKE
PE
m
m
onde a no ación u ilizada ep esen a :
() ()
() ()
() ()
() ()
∑
∑
∑
∑
∈
∈
∈
∈
=
=
=
∇=
Pk
kmm
Pk
k
Pk
k
Pk
k
pK
a
PK
pK
a
PK
pH
a
pH
pI
a
Pg
1
1
1
1
e sendo a a á ea do pa che e C o alo espe ado de Km. Se no se dispón de coñecemen o
a ce ca de C, habe á que subs i uí o seu alo po ce o. Segundo o ipo de supe icie
que se desexe segmen a de ínese o ac o de dis in a manei a. A con inuación
p esén anse algúns exemplos.
Pa a supe icies con ca as planas, in odúcese un ac o que aumen e cando as
cu a u as media como gaussiana enden a ce o en p omedio, como pode se-lo seguin e
(
)
(
)
HKHK ⋅= /1,
Se a supe icie é cilínd ica habe á que dis ingui en e o caso cónca o e o con exo. Po
exemplo, no caso cónca o, en a seguin e exp esión
(
)
(
)
KHsignoHK /, =
5.5 Obse acións 75
Pa a o caso caso con exo, cambia de signo. Cando se desexa segmen a supe icies do
ipo elipsoide ou hipe boloide hai que e en con a o signo an o de
H
como de
K
de
o ma sepa ada. En conc e o, a unción u ilizada pa a a segmen ación da supe icie
ex e na da ibia a pa i das imaxes de CT, debe á e en con a que a súa o ma é
hipe bólica e cónca a, esul ando unha exp esión coma a seguin e.
()
caso nou o
1
0 e 0 ,0 0
2/12
max









−
≠><
=
=
CK
ag
KKH
CKE
PE
m
m
m
Pa a segmen a a supe icie in e na esixi ase que
H
sexa nega i a.
O p oblema con es as magni udes é que son moi suscep ibles de e se a ec adas polo
uído. Se as cu a u as se calculan u ilizando unha eciñanza de pun os de supe icie
moi pequena, a in luencia do uído se á moi g ande, e pode esul a que en luga de
es a medindo a cu a u a da supe icie es eamos medindo a ugosidade ocasionada
polo uído. Aplicando un il o de sua izado a enúase es e e ec o. Tamén é con enien e
u iliza il os de escala g ande pa a o cálculo das de i adas de ni el de g is.
Po ou o lado, é moi ecuen e que apa ezan pa ches duns poucos pun os en zonas de
ni el de g is en p incipio uni o mes debidos ó uído. Es es pa ches poden e cu a u as
nulas, polo que o seu alo da e ique a se ía máximo. Pa a e i a es a si uación
ecó ese a unha ase p e ia de umb alización po á ea, cun ni el umb al moi baixo.
Unha ez calculada a e ique a de cada supe icie, a es a exia a segui pa a a selección
dos pa ches de supe icie, pode se unha simple umb alización do alo da e ique a. A
elección dun umb al semp e supón un p oblema. O habi ual é de e mina un umb al
dis in o pa a cada ipo de imaxes, segundo a écnica de ob ención da imaxe e amén po
con ido, sob e un conxun o de imaxes de p oba.
5.5 Obse acións
A pesa da mello a que supón u ilización de umb alización con his é ese, que a enúa en
ce a medida o e ec o de agmen ación das supe icies, o p oceso de ex acción de
pa ches de supe icie non o ece esul ados o almen e sa is ac o ios. Ben é ce o que o
modelado global ai compensa a pe dida de in o mación p oducida no il ado. Sen
emba go, hai que e en con a que o axus e ai se mello can o máis iables sexan os
da os ex aídos da segmen ación de baixo ni el. Se na umb alización se de ine o meno
dos dous umb ais moi al o, as exións da supe icie de baixo con as e poden se
eliminadas. Dado que a o ma do obxec o én de inida a p io i, a desapa ición dunha
pa e da supe icie no il ado non ai a ec a ós pa áme os da ecuación implíci a nin
das de o macións globais, pe o si á localización, de xei o que o modelo ende á a
desp aza se ca a a zonas onde a densidade de pun os de on ei a sexa maio . Se pola
76 CAPÍTULO 5. EXTRACCIÓN DE PARCHES DE SUPERFICIE
con a o umb al meno é baixo de máis, a supe icie do obxec o pode usiona se con
a e ac os da imaxe, que amén poden con ibuí de o ma impo an e ó e o do axus e.
Pensando sob e odo na segmen ación de imaxes de moi baixa calidade, pode se
in e esan e a u ilización dou as écnicas de il ado, que o ezan mello es p es acións
en can o a sup esión de uído e de ección de es uc u as. Re e ímonos conc e amen e ás
écnicas baseadas en il os de di usión non linea es e anisó opos. T á ase de sua iza
os ni eis de g is dunha imaxe de o ma análoga a un p oceso ísico de di usión, coma o
do calo . Es ablécese en ón un luxo que de e mina a e olución da con igu ación de
ni eis de g is co empo. A imaxe il ada co esponde ó es ado en que se a opa o
sis ema despois di undi se du an e un empo de e minado, elacionado coa escala do
il o. O ope ado de sua izado ob ense como esul ado de esol e a ecuación de
di usión
() ()()
()()





=
∇⋅=
∂
∂
zyxIzyxu
zyxuDdi
zyxu
,,0,,,
,,,
,,,
onde
()
zyxI ,, é o sinal de ni eis de g is e D é unha ma iz simé ica, chamada enso
de di usión.
O il o de sua izado gaussiano é un exemplo de il ado que simula un p oceso de
di usión, pe o nes e caso séguese un modelo linea e iso ópico, é dici , que a di usión
se p oduce ó mesmo i mo en ódolos pun os da imaxe e en ódalas di eccións. Nes e
caso o enso de di usión edúcese a unha cons an e, e a solución u á ecuación da
di usión co espóndese co p oduc o do sinal de ni eis de g is I po unha unción
gaussiana que en po des iación es ánda σ=√2 .
A non linea idade pe mi e de ini luxos a iables segundo a posición na imaxe, de
modo que sexan menos in ensos en exións de on ei a. Es o da luga a il os que
ope an a escala al a en zonas uni o mes, eliminando máis uído, men es que eñen un
e ec o máis local ce ca dos con o nos, p ese ando as es uc u as p esen es na imaxe.
Ou a an axe que o ece a non linea idade é que a enúa o e ec o de deslocalización dos
con o nos que en luga con il ados coma o gaussiano. Un exemplo de il o non linea
iso ópico é o deseñado po Pe ona e Malik [46], onde o enso de di usión é unha
unción escala de inida median e a seguin e exp esión
1
2
2
1
−







∇
+=
λ
u
D
sendo λ>0 un ac o cons an e. In oducindo es e ac o na ecuación da di usión, o luxo
u ∂∂ / diminúe en pun os onde o g adien e aumen a. A maio des an axe des e il o é
que as zonas de on ei a se en máis a ec adas polo uído.
Pola súa pa e a aniso opía do a ó il ado da posibilidade de de ini luxos di e en es
pa a dis in as di eccións. A di usi idade en cada di ección i á de e minada po
ac o es es uc u ais. Un esquema que combine aniso opía e non linea idade pe mi i á
es ablece p ocesos de di usión len os nas di eccións no mais en cada pun o das
5.5 Obse acións 77
supe icies de on ei a, men es que nas di eccións anxen es a es as se á posible le a
a cabo di usións máis ápidas. Po an o, man ense unha boa localización e de ección
das zonas de ansición en e exións men es que se o ece un sua izado maio nas
di eccións anxen es a esas supe icies de on ei a, eliminando uído. Como exemplo
des a écnica éñense os il os de Weicke [57]. Es e úl imo p esen a unha
ap oximación na que se de ine o enso de di usión en unción de desc ip o es de o ma
elacionados con cálculos da cu a u a, análogos ós p esen ados na sección an e io
des e mesmo aballo.
Es a é unha das ías de mello a des a me odoloxía que nes es momen os es amos
conside ando. O pe eccionamen o das écnicas de p ep ocesado pode supoñe unha
mello a impo an e na calidade dos esul ados en imaxes moi uidosas, co que a
aplicación do modelado con supe elipsoides pode es ende se a ou o ipo de imaxes
médicas de máis baixa calidade que as de CT, pa a as que es e p ocesado demos ou
o ece bos esul ados.

79
6 RESULTADOS
Acabamos de p esen a unha me odoloxía o ien ada á esolución dalgúns p oblemas
comúns den o da econs ucción de imaxes en xe al, e especialmen e da imaxe médica,
onde es es p oblemas se an máis pa en es. De iniuse un modelo capaz desc ibi a
es uc u a global dun obxec o, o que pe mi e do a dunha inicialización obus a ós
modelos de de o mación pola súa capacidade pa a e i a ou compensa a pe da de
in o mación que se p oduce nos p ocesos de baixo ni el.
O mé odo deseñado bene íciase an o do coñecemen o dispoñible sob e a o ma global,
po medio do uso de modelos a p io i, como da in o mación a ni el local ex aída da
p opia imaxe, a pa i da cal se e ec úa a iden i icación do obxec o na imaxe. As
p es acións do sis ema desen ol o dependen de es aspec os: a capacidade dos modelos
emp egados pa a ep esen a adecuadamen e os obxec os no ámbi o de aplicación do
sis ema, a e iciencia dos mé odos de op imización, e a e icacia do p ep ocesado na
ex acción dos pun os de on ei a. Nes e capí ulo mos a emos algúns esul ados que
p e enden ilus a-las p es acións que nes es es aspec os p opo ciona a écnica
desen ol a.
6.1 Op imización da unción implíci a
Comeza emos pola de inición dos modelos a p io i. Pa a a elección dunha das medidas
de e o p opos as na sección 4.1 ealizá onse p obas con imaxes de ibia. As unción de
e o que se es udian aquí son as D2, D3, e D4.
(
)
1,
1
2−= qx D
ε
(
)
(
)
{
}
1,
1
2/1
3213 −= qx aaaD
ε
()





−== q
D
,
1
11
4
ε
δ
A con igu ación do algo i mo xené ico emp egado pa a a op imización íxose pa indo
dos alo es dos pa áme os da simulación aconsellados na ob a de Goldbe g [25], que
pos e io men e se some e on a di e sas p obas pa a un maio axus e. Na con igu ación
inal a unción de e o somé ese a un mapeado de anking e emp égase selección de
o neo p obabilís ico, que o ece esul ados conside ablemen e mello es que os de ule a
ou o neo sinxelo. A poboación es á compos a po un o al de 80 indi iduos. O ope ado
de ecombinación é o de c uzamen o po dous pun os, omando a p obabilidade de
c uzamen o como pc=0.8. En can o a mu ación omouse unha p obabilidade bas an e
80 CAPÍTULO 6. RESULTADOS
ele ada, pm=0.1, en is a da p ema u a es abilización da poboación ob ida pa a alo es
máis baixos. Os pa áme os codi icá onse emp egando código G ay de 16 bi s pa a cada
un. Aínda que se ía posible aumen a o núme o de bi s po pa áme o, considé ase que
dado o ipo de aplicación do modelo non se p ecisa de máis esolución. Baixo es as
condicións íxose e oluciona a poboación a a obse a que es a se es abilizaba ou se
chegaba ás 2000 i e acións.
Nunha p imei a p oba aplicouse o algo i mo así con igu ado a unha dis ibución de
pun os de supe icie dunha sección de ibia. As imaxes da igu a 6.1 mos an dis in as
is as desa supe icie, ep esen ados median e un esquema de iangulación pa a a súa
mello isualización. As imaxes das igu as 6.2 e 6.3 ep esen an os esul ados ob idos
pa a as uncións D4 e D3 espec i amen e. Visualmen e pode ap ecia se a di e encia de
aspec o dos co esponden es modelos.
Pe o aínda que pe cep ualmen e a unción D4 o ece mello es esul ados, habe ía que
ealiza unha compa ación cuan i a i a pa a ce ciona se de que e ec i amen e es a é a
medida de e o máis axei ada. Pa a es ima a calidade dos dis in os axus es u ilizouse
unha imaxe sin é ica dun supe elipsoide, que se pode e na igu a 6.4. Es a imaxe
p esen a ódolos ipos de de o mación global que se pe mi e o noso modelo. Os alo es
conc e os dos pa áme os do supe elipsoide pódense e na áboa 6.1. A magni ude que
nos se e pa a compa a nume icamen e os modelos ob idos de ínese pola unción
()
',qqd , que ep esen a a dis ancia en e o ec o q dos pa áme os coñecidos da
supe icie sin é ica e o ec o 'q dos pa áme os calculados u ilizando unha de e minada
unción de e o, dada polo módulo do ec o di e encia q-'q. Pa a que o axus e dun
pa áme o en pa icula non eña máis peso no cálculo da medida de calidade que os
demais, cada compoñen e es á escalada cun ac o ai igual á o de de magni ude de qi,
esul ando a exp esión de d como segue.
() ( )
∑−=
i
iii qqaqqd 22 '',
Os alo es dos ac o es ai apa ecen amén na áboa 6.1 ó lado dos co esponden es
pa áme os. En luga de ealiza unha soa p oba con cada unción de e o, le á onse a
cabo a ios axus es, pa a ob e cadanseu ec o 'q de pa áme os calculados p omedio.
Os alo es de d que se ob i e on son as que se con emplan na áboa 6.2. Pódese obse a
que en xe al, os esul ados son peo es pa a a unción D2 que pa a as ou as dúas. En e D3
e D4 é di ícil de e mina cal das dúas é mello . Se calculamos po sepa ado a unción d
pa a os pa áme os de o ma e os de ans o mación íxida, comp obamos que a en e D3
e D4 pequena di e encia obse ada débese p incipalmen e ó axus e dos pa áme os de
ans o mación íxida.
6.1 P ep ocesado 81
q
i
a
i
q
i’ con
D
2
q
i’ con
D
3
q
i’ con
D
4
ε
1
0,2 0,1 2,174e-01 2,132e-01 2,151e-01
ε
2
0,8 0,1 8,329e-01 8,032e-01 8,054e-01
a
1
20 10 2,003e+01 2,002e+01 2,001e+01
a
2
30 10 3,007e+01 3,002e+01 3,008e+01
a
3
50 10 4,979e+01 4,979e+01 4,978e+01
c
x
0 1 2,151e-04 1,040e-03 2,808e-04
c
y
0,2 0,1 2,092e-01 1,990e-01 1,990e-01
θ
0,003 0,001 2,361e-03 3,026e-03 2,999e-03
k
0,001 0,001 7,735e-04 8,053e-04 1,133e-03
φ
0 1 6,729e-04 -3,097e-02 1,040e-02
α
0 1 -1,846e-03 -3,072e-02 4,473e-02
β
0 1 7,661e-05 8,999e-06 -1,979e-05
γ
0 1 -8,281e-03 3,180e-02 -4,480e-02
1
0 1 1,085e-01 8,941e-02 2,312e-01
2
0 1 -2,959e-03 2,875e-03 -7,610e-03
3
0 1 -2,020e-02 -4,960e-02 -1,781e-02
Táboa 6.1 Valo es dos pa áme os
q
i do supe elipsoide da igu a 6.4 cos co esponden es ac o es de
peso
a
i. Á de ei a, o p omedio dos alo es dos pa áme os
q
i’ calculados pa a as uncións de e o
D
2,
D
3 e
D
4 nun o al de 12 p obas.
Función de e o
d
d
o ma
d
. íxida
D2 0,787 0,779 0,111
D3 0,266 0,242 0,111
D4 0,319 0,210 0,240
Táboa 6.2 Es imación da calidade do axus e coas dis in as medidas de e o.
88 CAPÍTULO 6. RESULTADOS
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.6 Imaxe de p oba con uído gaussiano de des iación es ánda σ = 20.
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.7 Imaxe de p oba con uído gaussiano de des iación es ánda σ = 30.
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.8 Imaxe de p oba con uído gaussiano de des iación es ánda σ = 40.

6.3 Pos a en co espondencia 89
z = 10
z = 20
z = 30
z = 41
z = 50
Figu a 6.9 Imaxe de p oba σ uído = 20 as un il ado gaussiano con σ = 3
z = 10
z = 20
z = 30
z = 41
z = 50
Figu a 6.10 Imaxe de p oba σ uído = 20 as un il ado al a con α = 0.5
z = 10
z = 20
z = 30
z = 41
z = 50
Figu a 6.11 Imaxe de p oba σ uído = 30 as un il ado gaussiano con σ = 3
z = 10
z = 20
z = 30
z = 41
z = 50
Figu a 6.12 Imaxe de p oba σ uído = 40 as un il ado al a con σ = 3
90 CAPÍTULO 6. RESULTADOS
Figu a 6.13 Co es z=50 en nega i o con il ados gaussiano σ=3 (esque da) e al a α=0.5 (de ei a)
Figu a 6.14 Co es z=5 en nega i o con il ados gaussiano σ=3 (esque da) e al a α=0.5 (de ei a)
u1 = u2 = 50
u1 = u2 = 20
u1 = 50, u2 = 20
Figu a 6.15 Ag upamen o de pa celas de supe icie con dis in os alo es dos umb ais maio e meno .
6.3 Pos a en co espondencia 91
z = 20
z = 35
z = 50
Figu a 6.16 Selección de supe icies con K < 0
z = 20
z = 35
z = 50
Figu a 6.17 Selección de supe icies con K > 0
z = 20
z = 35
z = 50
Figu a 6.18 Selección de supe icies con K = 0
z = 20
z = 35
z = 50
Figu a 6.19 Selección de supe icies con H > 0
92 CAPÍTULO 6. RESULTADOS
z = 20
z = 35
z = 50
Figu a 6.20 Selección de supe icies con H < 0
z = 50
x = 50
y = 50
Figu a 6.21 Selección de supe icies cilínd icas na imaxe de p oba con uído σ = 20.
z = 50
x = 50
y = 50
Figu a 6.22 Selección de supe icies cilínd icas na imaxe de p oba con uído σ = 30.
z = 50
x = 50
y = 50
Figu a 6.23 Selección de supe icies cilínd icas na imaxe de p oba con uído σ = 40.
6.3 Pos a en co espondencia 93
z = 10 z = 50 z = 100
z = 140 z = 165
Figu a 6.24 Imaxes CT de pe na de ei a.
z = 10 z = 50 z = 100
z = 140 z = 165
Figu a 6.25 Imaxes CT de pe na de ei a il adas con il o gaussiano.
z = 10 z = 50 z = 100
z = 140 z = 165
Figu a 6.26 Ag upamen o en pa ches de supe icie

94 CAPÍTULO 6. RESULTADOS
z = 1, K > 0
z = 99, K > 0
z = 1, K < 0
z = 99, K < 0
Figu a 6.27 Selección de supe icies po cu a u a gaussiana.
z = 1, H > 0
z = 99, H > 0
z = 1, H < 0
z = 99, H < 0
Figu a 6.28 Selección de supe icies po cu a u a media.
6.3 Pos a en co espondencia 95
z = 10 z = 50 z = 100
z = 140 z = 165
Figu a 6.29 Selección con umb al meno u2=40.
Figu a 6.30 Recons ucción iangulada da supe icie da Figu a 6.29
z = 10 z = 50 z = 100
z = 140 z = 165
Figu a 6.31 Selección con umb al meno u2=30.
Figu a 6.32 Recons ucción iangulada da supe icie da igu a 6.30
96 CAPÍTULO 6. RESULTADOS
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.33 Pos a en co espondencia da imaxe de p oba de uído σ = 20 cun modelo de cilind o.
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.34 Pos a en co espondencia da imaxe de p oba de uído σ = 30 cun modelo de cilind o
z = 30
z = 50
z = 69
x = 50
y = 50
Figu a 6.35 Pos a en co espondencia da imaxe de p oba de uído σ = 40 cun modelo de cilind o
6.3 Pos a en co espondencia 97
z = 20 z = 35 z = 50
z = 165 x = x = 98 x = y = 106
Figu a 6.36 Pos a en co espondencia en e imaxe e modelo calculado coa unción de e o adial
z = 20 z = 35 z = 50
z = 165 x = x = 98 x = y = 106
Figu a 6.37 Pos a en co espondencia en e imaxe e modelo calculado coa unción de e o D3.
104 BIBLIOGRAFÍA
[49]. H. Same . “ The design and analysis o spa ial da a s uc u es”. Addison-Wesley,
Reading, Massachuse s, 1990.
[50]. S. Sando , R. Leahy. “Su ace-based labeling o co ical ana omy using a
de o mable a las”. Medical Image, ol. 16, nº 1, 1997, pp 41-54.
[51]. F. Solina, R. Bajcsy. “Reco e y o pa ame ic models om ange images: he
case o supe qued ics wi h global and local de o ma ions”. T ans. on PAMI, ol.
12, nº 2, Feb ei o 1990, pp 131-146.
[52]. L. S aib, A. Chak abo y, J.S. Duncan. “An in eg a ed app oach o loca ing
neu oana omical s uc u e om MRI”. In e na ional Jou nal o Pa e n
Recogni ion and A i icial In elligence, ol. 11, nº 8, 1997, pp 1247-1269.
[53]. L. S aib, J.S. Duncan. “ Bounda y inding wi h pa ame ically de o mable
models” IEEE T ans. on PAMI, ol. 14, nº 11, 1992, pp 1061-1075.
[54]. G. S o ik. “A bayesian app oach o dynamic con ou s h ough s ochas ic
sampling and simula ed annealing”. IEEE T ans. on PAMI, ol. 16, nº 10,
Ou ub o 1994.
[55]. D. Te zopoulos, D. Me axas. “Dynamic 3D models wi h local an global
de o ma ions: de o mable supe quad ics”. IEEE T ans. on PAMI, ol. 13, nº 7,
Xullo 1991, pp 703-714.
[56]. D. Te zopoulos, A. Wi kin, M. Kass. “Cons ain s on de o mable models:
eco e ing 3D shape and non igid mo ion” A i icial In elligence, ol. 36, 1988,
pp 91-123.
[57]. J. Weicke . “Mul iscale ex u e enhancemen ”. CAIP95, pp 230-237.
[58]. P. Whai e, F.P. Fe ie. “F om unce ain y o isual explo a ion”. IEEE. T ans on
PAMI., ol. 13, nº 10, Ou ub o 1991.