Centro de Investigación y Estudios Avanzados. Departam ento de Ingeniería Eléctrica. *

ce t m de investísacisn y i i

ESTUDIOS AVANZADOS BEL

I. P. N. B I B L I O T E C A

Sección de Computación

'n g e n ie r ia

Una solución al problema do la correspondencia en un par estéreo utilizando descriptores de curvas.

Tesis que presenta Joaquín SALAS1 p ara obtener el grado de M aestro en Ciencias eu la especialidad de Ingeniería Eléctrica. Trabajo dirigido por el Dr. Sergio CHAPA.

México, D .F .. A gosto 1991.

b e c a r i o d e CONACYT.

e l e c t r ic a

GÍIITM DE INVESTIGACION Y fet ESTUDIOS AVAN?t ()os S í l

I. P . N. ■

I B L I O T E C A

IN G E N IE R IA E L E C T R IC #

AGRADECIM IENTOS:

E ste tra b a jo es fru to d e un ac u erd o de colaboración científica e n tre las escuelas E .N . S . T . d e B r e t a g n e en F ran c ia y C I N V E S T A V d e l I .P .N . en M éxico. F ra n cia . Q u iero agrad ec er a los profesores M . A lia n H I L L I O N , Jefe del D e p a rta m e n to de M atém a tic as y S istem as d e C om unicación, y M . J e a n -M a r c B O U C H E R , re sp o n sab le de mi estan c ia, p o r h a b e rm e recibido ta n a m a b le m en te en su d e p a rta m e n to . A sí ta m b ié n , a los profesores M . C h r is tia n R O U X . Jefe del G ru p o de T ra ta m ie n to de Im ágenes, y M . G u y C A Z U G E L . quienes siem pre tu v ie ro n una p a la b ra d e apoyo p ara este proyecto. Igua lm e n te , a M . J e a n - J o s é J A C Q y M . J e a n -P a u l L A U R E N T . sin cuyo equipo y co n o c im ie n ­ tos técnicos, el proyecto no h u b ie ra pro g resad o com o lo hizo. F in a l­ m en te. q u iero agrace d er los alum nos y p ersonal de la E .N .S .T . de B re ­ tag n e . cuya am istad a lo largo de estos m eses ha sido u n a d e las e x p e ­ riencias m ás enriquecedoras que he tenido. M é x ic o . E sta e s tan c ia y en general m is estu d io s de M ae stría han sido fu e rte ­ m en te apo y a d o s en C I N V E S T A V ..Q u iero ag rad ec er al profesor D r . D a v id M U Ñ O Z . Jefe del D e p a rta m e n to d e Ingeniería E lé c tric a , y a los señores D r . G u ille r m o M O R A L E S . Jefe de la Sección de C o m p u ta c ió n , D r . J o s é L u is G O R D I L L O y D r . J u a n M a n u e l I B A R R A . Jefe de la Sección d e C ontrol A u to m ático , p o r to d o su apoyo p a r a la realización de e s te in terc am b io q u e m e h a p e rm itid o t r a ­ b a ja r en un lab o ra to rio del m ás a lto nivel. T am bién, a los profesores D r a . A n a M a r ía M A R T I N E Z y D r . S e r g io C H A P A , m is a s ­ esores académ icos en M éxico, p o r to d a s sus conversaciones y consejos. P or ú ltim o , a los alum nos de las Secciones de C o m p u ta ció n y C o n tro l A u to m á tic o , quienes han p ro p icia d o un am b ie n te científico y h u m a n o m uy rico, del cual m e siento orgulloso de form ar p arte .

DEDICATORIA:

,4 R a m ó n y Socorro, quienes hace m ucho tiem po m e en señaron que pocas cosas son m á s valiosas que un poco de conocim iento.

A L en is y D aniel, qu ien e s m e han proporcionado un a m b ie n te fa m ilia r pleno.

In tro d u cció n .

Las im ágenes son proyecciones tridim ensionales d e escenas trid im e n sio n a­ les. La re cu p erac ió n d e la inform ación d e p ro fu n d id a d es un p ro b lem a fu n ­ d a m e n ta l en ap licacio n es ta le s com o la navegación a u to m á tic a , la c a rto g ra fía y la ro b ó tica . El o b je tiv o d e este tra b a jo es desc rib ir un m éto d o p a ra en c o n ­ tr a r la co rresp o n d e n cia e n tre los segm entos d e cu rv a de dos im ágenes u sando téc n ic as de estereoscopia. D adas dos im ágenes y el m odelo geo m é tric o d e las c á m a ra s , la ta re a de la estereo sco p ia es e n c o n tra r los p u n to s , q u e c o rresp o n d e n en u n a y en o tr a im agen, y señ alan u n p u n to único en la escena; d esp u és, to m a n d o en c u e n ta la diferencia de los d e s p laz am ien to s de los p u n to s en las im ágenes ( disparidad) y la posición de las cá m a ra s , la inform ación de p ro fu n d id a d p u ed e ser c a lcu lad a m e d ian te u n a tran sfo rm ac ió n g eo m étrica. En el L a b o ra to rio d e T ra ta m ie n to d e Im ágenes de la E .N .S .T . de B reta g n e se t r a b a j a sobre p ro b lem a s relacionados con el an á lisis y p ro c esam ien to d e im ágenes, en o casio n es d e sa rro llan d o investigación b ásica y en o tra s en co­ lab o ra ció n con e m p re sas d e la región con el fin d e ap lic a r e s ta tec n o lo g ía a la solución de p ro b lem a s. E s te tra b a jo se u b ic a d e n tro de un gra n pro y e cto d e an á lisis o cu la r que tien e com o fin el d ia g n ó stico a u to m á tic o de en ferm e d ad es. En p a rtic u la r los desarrollos de n u e s tro tr a b a jo serán utilizad o s p a r a la d e te rm in a ció n de la c u rv a tu ra d e la su p erficie d e los ojos y o b serv ar si se pu ed e n o b te n e r p a rá m e tro s re la tiv o s a defectos tales com o m io p ía o astig m atism o . N u e stro p ro p ó sito es el diseño y co n stru c ció n d e un m odelo p a r a resolver el p ro b le m a d e la c o rre sp o n d e n c ia b asa d o en té c n ic as d e estereo c o p ía . P ro ­ p o nem os u n alg o ritm o q u e u tiliz a d e sc rip to res de segm entos d e cu rv a com o base p a r a re c u p e ra r la inform ación de p ro fu n d id a d . C reem os q u e la re p re ­ sentación de e s tru c tu ra s trid im e n sio n ales p re su p o n e la con stru c ció n de proce­ sos de in terp o lac ió n d e superficies, lo cual re q u ie re u n a solución al p ro b lem a de la seg m en ta ció n d e o b je to s en la escena; p en sa m o s q u e é s te es un p ro b ­ lem a q u e m erece ate n ció n p o r derecho pro p io y p o r ello no hem os p ro p u e sto u n a solución al p ro b le m a d e la re co n stru cc ió n trid im e n sio n al en este escrito. El re p o rte se o rg a n iz a en c u a tro ca p ítu lo s y un apéndice: C a p ítu lo

1.

Se p ro p o rc io n a un p a n o ra m a general d e la estereoscopia; se

cam r# 1 1

i n v e s t i d a c i ©n y

it

E ST U D I O S A V A N Z A 8 0 S S E L

i. P. N. i l S L I O T E C A

’N G E N IE R 1A E L E C T R IC #

incluyen tem as y tra b a jo s previos im p o rtan tes. C a p í t u l o 2. D esarrollam os los algoritm os necesarios p a ra la realización del m odelo de propuesto. C a p í t u l o 3. Se p re sen tan los re su lta d o s que obtuvim os al ex p e rim en tar con el m odelo construido. C a p í t u l o 4 . Señalam os algunas conclusiones y proponem os posibles m ejo­ ras al proyecto. A p é n d ic e . E l tra b a jo com p u tac io n al es p re sen tad o y descrito.

Contenido 1

L a e s te re o v is ió n . 1.1 Definición del p ro b le m a ............................................................................ 1.2 G e o m e tría e ste re o ........................................................................................ 1.2.1 G e o m e tr ía s i m p l i f i c a d a .............................................................. 1.3 D e te c c ió n d e c o n t o r n o s ........................................................................................ 1.4 1 .5

2

E l m o d e lo d e e s t e r e o s c o p i a p r o p u e s to . 2.1 2.2 2.3 2.4 2.5

3

T ra b ajo s p re v io s........................................................................................... Inform alm ente: n u e stro a lg o ritm o .........................................................

* 1 3 ? 9 ^ 16 17

In tro d u c c ió n .................................................................................................... ^ F iltro G ra d ie n te ............................................................................................ ^ A d e lgazam iento de lín eas.......................................................................... 20 E x tra cció n de co n to rn o s............................................................................. 22 2.4.1 D e te rm in ació n d e los segm entos de r e c ta ............................ 27 A lgoritm o de c o rre sp o n d e n c ia .................................................................. 28 2.5.1 P rim e ra e ta p a ................................................................................. 29 2.5.2 S eg u n d a e ta p a ................................................................................ 30

R e s u lta d o s e x p e rim e n ta le s .

33

3.1

La ta s a ............................................................................................................... 33 3.1.1 Im ágenes o rig in ales....................................................................... 33 3.1.2 Im ag en g ra d ie n te ........................................................................... 34 3.1.3 A d e lg a za m ien to de lín eas ........................................................... 35 3.1.4 E x tr a c c ió n d e c o n t o r n o s .............................................................. 35 3.1.5 A p a r e a m ie n to ................................................................................ 36 3.2 Las ra q u e ta s d e p in g -p o n g ......................................................................... 38 3.2.1 Im ágenes o rig in ales....................................................................... 38 iii

SMíTEfC' BE INVESTISACieN Y Pf ESTUDIOS AVANZAB9S BU

!. P. N. B I B L I O T E C A I N G E N I E R I A E L E C T R I C '1

iv

C O N T E N ID O

3.3

4

3.2.2

Im agen g ra d ie n te ........................................................................... 38

3.2.3

A delgazam iento de lín eas........................................................... 3 9

3.2.4

E x tra cció n d e co n to rn o s............................................................. 41

3.2.5

A p a rea m ie n to .................................................................................. 42

El lab o ra to rio ................................................................................................ 45 3.3.1

Im ágenes originales. .....................................................................45

3.3.2

Im agen g ra d ie n te ............................................................................45

3.3.3

A delgazam iento d e lín eas............................................................47

3.3.4

E x tra cció n de co n to rn o s..............................................................47

3.3.5

A p a rea m ie n to .................................................................................. 51

C o n c lu s io n e s .

A L a p r o g r a m a c ió n d e l m o d e lo . A .l

A lm acena im ag en .........................................................................................57

A .2 R ecu p e ra im ag en ..........................................................................................59 A .3 G ra d ie n te ........................................................................................................ 62 A .4 A delgazam iento de lín eas..........................................................................65 A .5 E xtracción de co n to rn o s............................................................................76 A . 6 C orre sp o n d en cia........................................................................................... 97

53

55

Capitulo 1

INGENIERIA ELECTRICA

La estereovisión. 1.1 D efin ición del p ro b lem a . N u e stro s o jo s son el m odelo m ás pró x im o q u e ten e m o s p a ra explicar el p rin ­ cipio d e la estereoscopia. Sim plifiquem os e n o rm e m en te el m odelo y olvidé­ m onos p o r u n m o m ento de la en o rm e com p lejid ad d e funcionam iento d e los ojos; tom ém oslos sim p le m e n te com o dos c a p to re s visuales con la ú n ica m isión de tra n s fe rir im ágenes del m undo físico a n u e s tro cerebro. U n ojo es, en el caso id ea l, fu n c io n a lm e n te d ep e n d ien te con re sp ecto al o tro p o r las siguientes causas: • A m bos ojos funcionan d u ra n te el m ism o p erío d o de tiem po; es decir, n o rm a lm e n te se ab ren y cie rra n sim u ltá n e a m e n te , lo cual oca sio n a que c a p te n los m ism os eventos. • Los ejes focales de los ojos convergen en el p u n to d e interés; pero en g en e ral, el p u n to de Ínteres se e n c u e n tra de ta l m a n e ra re tira d o que p o d em o s co n sid erar a los ejes focales com o p rá c tic a m e n te paralelos. • F ísic a m e n te , los ojos se e n c u e n tra n o rie n ta d o s en la m ism a dirección y a la m ism a a ltu ra en su posición n o rm al. • El e n fo q u e es el m ism o, id ea lm e n te , p a r a c a d a ojo. C a d a o jo c a p ta u n a escena bidim ensional. El ce reb ro , m e d ian te un m ecanis­ m o que no hem os co m prendido del to d o , p ro c e sa am bas im ágenes y nos hace 1

2

C A P ÍT U L O 1. L A E S T E R E O V IS IÓ N .

p ercib ir la p ro fu n d id a d 1. A h o ra b ien, u n siste m a de visión artificial cuyo fin fuera la inferencia de pro fu n d id a d en u n a escena, d eb e ría c o n ta r con los siguientes com ponentes: • Dos o m ás im ágenes, to m ad as p o r dos o m ás cám aras fijas o p o r u n a cá m a ra d esplazada. • U n proceso, llam ad o calibración, que dete rm in e : — La posición d e las cám aras en el m o m ento de to m a r las im ágenes; — La p ro fu n d id a d de un p u n to que nos sirva de referencia p a ra re la­ cionar n u e stra s m edidas con el m undo físico. • U n s iste m a de inferencia que dad a s com o e n tra d a s el co n ju n to de im á­ genes y el m odelo geom étrico de las cá m ara s al m o m ento de to m a r las im ágenes d ete rm in e la pro fu n d id a d de los p u n to s en la escena. V arias técnicas del tip o cooperativo (v e r §1.4) h an sido estu d iad a s. E stas in te n ta n re la cio n ar conocim iento referente al m ovim iento, la te x tu ra o el flujo ó ptico con la estereoscopia. La integración de ta l ca n tid a d de d ato s co n sti­ tu y e un p ro b lem a m uy com plejo desde los p u n to s de v is ta de la a rq u ite c tu ra co m p u tac io n al y los algoritm os requeridos. P o r m edio d e la estereo c o p ía se in te n ta re p ro d u c ir el fun cio n am ien to del s iste m a visual h u m an o en el sentido de que, d ad o un c o n ju n to de im ágenes de u n a escena y el m odelo geom étrico d e las cá m ara s en el m om en to de to m a r las im ágenes, el p ro p ó sito de la estereoscopia es e x tra e r la inform ación de p ro ­ fu n d id ad de la escena. E n la estereoscopia clásica, el p ro b lem a fu n d a m e n tal consiste en en c o n tra r las proyecciones de u n a c a ra c te rís tic a en la esc en a en las dos im ágenes (problem a de la correspondencia). El arreglo g eom étrico m ás sim p le p a ra expe rim en tac ió n estereoscópica se p re sen ta en la F ig. 1.3. Los planos im ágenes son coplanares y los ejes focales se en c u en tra n a la m ism a a ltu ra . Los algoritm os de estereo visión d eben id entificar p u n to s d e co rresp o n d e n cia e n tre las dos im ágenes con el fin de en c o n trar la p ro fu n d id a d . U n p u n to en u n a im agen e s ta r á d esplazado en la o tra im agen u n a d is ta n c ia que es d e p e n d ien te del d esp lazam ien to relativo d e las cá m ara s y d e la pro fu n d id a d del p u n to en la escena. U n a vez que 1 Podemos inferir profundidad con u n solo ojo, pero esto se debe a conocimiento previo, interpretación de movim iento ó inferencia a partir de la iluminación y las sombras.

1.2.

G E O M E T R ÍA E S T E R E O .

3

la co rresp o n d e n cia h a sido efectu a d a, la p ro fu n d id a d p u ed e ser ca lcu lad a u san d o u n a tran sfo rm ac ió n g eo m é tric a o trian g u lac ió n (ver § 1 . 2 ). El p roceso d e b ú sq u e d a d e los p u n to s de co rresp o n d e n cia pu ed e ser sim ­ plificado en v irtu d del m odelo geom étrico d e sc rito en el p árrafo an te rio r. Dos consideraciones p u ed e n ser p o stu la d as: • Los p u n to s q u e en u n a im agen ap a rez ca n en la lín ea i(lín e a epipolar), a p a re c e rá n en la m ism a línea i en la o t r a im agen (propiedad de epipolaridad). E l p lan o que se define e n tre la lín ea i y el p u n to en la escena se le lla m a plano epipolar. • D efinam os el arreglo de la F ig. 1.3 en térm in o s de im agen d erecha D e im agen iz q u ierd a / . Si un p u n to ap a re c e en la m ita d d e la d erecha de D en to n c es, si a p a rec e en la im agen / , a p a re c e rá en su m ita d derecha. Ig u a lm e n te , si un p u n to a p a rec e en la m ita d de la izq u ie rd a d e I e n ­ to n ce s, si a p a rec e en la im agen Z), a p a re c e rá en la m ita d izquierda. E sto re d u ce el espacio d e b ú sq u ed a de un p u n to .

1.2

G eo m etría este r eo .

C on el fin d e ap lic a r la inform ación de p ro fu n d id a d a la resolución de pro b le­ m as, n ec esitam o s referenciar ca d a p u n to que observam os en la im agen con re sp ecto al m u n d o físico. C on ta l efecto definim os dos s iste m as coordenados: el s iste m a coordenado de la im agen q u e nos s e rv irá p a ra lo ca liz ar p u n to s en la im agen y el sis te m a coordenado global en d o nde localizarem os cu a lq u ie r o tr a cosa. L a F ig. 1.1 ilu s tr a la idea. M ed ian te el sis te m a co o rd en ad o global, localizam os el p u n to v y la cá m a ra , que se e n c u e n tra tra s la d a d a del origen, ro ta d a h o riz o n ta lm e n te un ángulo 0 , y con u n a dirección d e en foque a lz ad a un ángulo . L a proyección del p u n to v en la im ag en , es m ed id o con re sp ecto al s is te m a co o rd en ad o de la im agen. N u e stro p ro b le m a es e n c o n tra r u n a tran sfo rm ac ió n g e o m é tric a que nos ex p rese las co o rd en ad a s de un p u n to en la im agen en té rm in o s del siste m a co o rd en ad o global. D efinim os en to n ces, el plan o d e la im agen con resp ecto al sis te m a co o rd en ad o global m e d ian te los siguientes tre s pasos: 1. T ra sla d am o s el c e n tro del p lan o im agen al c e n tro de la c á m a ra m e d ian te

4

C A P ÍT U L O 1. L A E S T E R E O V IS IÓ N .

F ig u ra 1.1: T r a n s fo r m a c ió n d e p e r s p e c tiv a . Dos sistem as co o rd en ad o s son utilizados. La c á m a ra y el p u n to v son referenciados p o r el sis te m a coordenado global. El sis te m a co ordenado de la im agen, q u e co n tien e al p u n to im agen v ', es referen ciad o con resp ecto a la cám ara. Sea t>o la posición del centro de rotación de la cá m ara . La cá m a ra tie n e un giro h o rizo n ta l de u n ángulo 0 y su dirección d e enfoque e s tá alz a d a un ángulo .

1.2.

G E O M E T R ÍA E S T E R E O .

5

u n a m a triz hom ogenea d e tra sla c ió n G e x p resad a com o:

2. G ira m o s h o riz o n ta lm e n te la c á m a ra un ángulo 6 y b aja m o s su dirección d e en fo q u e un ángulo , d e ta l m a n e ra que el eje Y (el eje d e p ro fu n ­ d id a d ) del s is te m a co o rd en ad o global quede p aralelo con el eje focal de la cá m ara ; lo cual se p u e d e re p re s e n ta r p o r la m a triz ho m o g en ea de ro tac ió n S , e x p re s a d a com o:

( 1.2)

3. T ra sla d am o s el c e n tro de ro tac ió n de la c á m a ra v 0 al c e n tro del sis te m a g lobal. E sto se logra ap lica n d o el o p erad o r / / , definido com o u n a m a triz h om ogenea por: 1

0

0

-x 0

0 1 0

-y o

0 0 1

- ¿o

0

0

0

(1.3)

i

L a tran sfo rm ac ió n a n te rio r, q u e nos e x p re s a p u n to s de la im agen en el sis te m a co o rd en ad o global, es lla m a d a tran sfo rm ac ió n in v ersa de p ers p e c tiv a y se ex p re s a com o: v = H x S x G x v ' (1-4) D espués de algunos cálculos R ic h ard O. DU D A en [9], o b tien e la localiza­ ción del c e n tro del le n te de u n a c á m a ra con re sp ecto al sis te m a c o o rd en ad o global i>o; xo v0 =

yo . z0 .

+

l\ eos 9

—

l¡s\n6

+

¡2 eos sin 0 /3 sin 4>eos 0

+

l3 eos 2, tal que r x = p y r ^+1 = q y hay proxim idad inm ediata entre n y r ¿+ 1 VI=]....*. E jem plos ilu strativ o s de los conceptos de proxim idad m e d ia ta e in m e d ia ta se p re sen tan en la F ig. 2.7. U na im agen puede e s ta r co m p u e sta d e varias

2.5.

A L G O R I T M O D E C O R R E S P O N D E N C IA .

31

F ig u ra 2.7: P r o x im id a d m e d ia ta e in m e d ia t a . E n (a) r y s tien en p ro x i­ m idad in m e d ia ta . E n (b) r y s tien en pro x im id ad m e d ia ta , y a que no tien en p ro x im id ad in m e d ia ta p ero ex iste un q ta l q u e tie n e p ro x im id ad in m e d ia ta con s y ofrece p ro x im id ad m e d ia ta p o r in term ed io d e q' con r. E n la figura se cu m p le q u e V, 7 , < 7 ; donde 7 es u n valor real. decenas de c ircu ito s; id ea lm e n te , los circuitos re p re s e n ta n e s tru c tu ra s in d e­ p e n d ie n te s y es p o sib le d esc rib ir la escena en base a la relación d e los circuitos q ue la fo rm a n . A l g o r i t m o : C álculo d e la co rresp o n d e n cia e n tre g ru p o s de segm entos de curva. E n t r a d a s : Los co n ju n to s T \ y T2, el conjunto d e circuitos de la im agen 1 y 2 con ele m e n to s y ¿2 ,« re spectivam ente.. S a lid a s : El co n ju n to M de correspondencias e n tre g ru p o s d e curvas. P R O C E D U R E P o sE m p a te ; V A R i, j , m , n :IN T E G E R ; B E G IN F O R i: = 1 T O n um ero de circuitos en Ti S elecciona el circuito-i de 7 j, = ” y seg u irá u n a porción de código q u e re em p la z a rá su llam ada. En el caso de u n a sección no nom b rad a , solo se p re s e n ta rá el código de lenguaje C. En ocasiones, u n a sección n o m b ra d a es dividida; es el caso d e las variables, co n stan te s, y e s tru c tu ra s d e d ato s, las cuales son p re se n ta d a s en el m om ento que creem os m ás o p o rtu n o . D espués d e la p rim era, estas secciones a p a rec erán con la form a: “< N o m b re d e la s e c c ió n > + = ” , lo cual in d ica que su contenido debe ser pegado a la p rim e ra sección. P a ra facilitar la le c tu r a del código, se han to m ad o alg u n a s convenciones. Las p alab ras reservadas com o fo r , w h ile , así com o los pro c ed im ie n to s in ­ cluidos en la lib rería e s ta n d a r com o fp r in tf, fc lo s e , ap a re c e rá n en negritas; los identificadores a p a rec erán en itálicas y los nom bres d e p rocedim ientos en le tra norm al. Ig u a lm e n te , algunos sím bolos han sido reem plazados: sím bolo:

s u stitu y e a:

< >

= |

=

* A V

=

kk ii

j

Igualm ente, algunas funciones com o la raíz cu a d rad a , h a sido s u s titu id a p o r el sím bolo m a te m á tic o el sím bolo * h a sido s u s titu id o p o r x cu a n d o se refiere a u n a m u ltiplicación y algunas operaciones del le n g u a je C e s ta n d a r com o i + + , h an sido su s titu id a s p o r i *— i + 1 .

A .l.

A .l

A L M A C E N A IM A G E N .

57

A lm a c e n a im a g e n .

El p ro g ra m a A l m a c e n a l m a g e n p e r m ite alm ac en ar la porción de m em o ria p rin c ip a l, que co rresp o n d e a la im ag en d ig ita l, en la m em oria s e c u n d a ria de la co m p u ta d o ra . C on el fin d e ap ro v ech a r el equipo co m p u tacio n al ex iste n te , la im agen se alm ac en a en la m em o ria in c o rp o ra d a a la c a rta de adquisición de im ágenes; é sto vuelve al p ro g ra m a d e p e n d ie n te del equipo, p ero las im ágenes son lo suficientem ente g ra n d es (768 colum nas p o r 512 hileras) com o p a r a ju s tific a r la decisión. C om o a te n u a n te , podem os ag reg ar que si la m em o ria del o rd e n a d o r es lo su ficien tem en te g ra n d e com o p a ra reservar un espacio de m em o ria de 384k p a la b ra s , sin p ro b lem a , los cam bios al p ro g ra m a son m ínim os. 1. La descripción co m ien z a m o s tra n d o las porciones principales d e u n p ro ­ g ra m a en len g u a je C , cu y a s co m p o n e n te s serán llenadas después. P o r eje m p lo , la porción del p ro g ra m a lla m a d a < L a s co n stan te s 3 > será re e m p la z a d a p o r u n a sec u en cia d e d eclaración de c o n sta n te s q u e co­ m ie n z a en §3. < L o s archivos que se p re p ro ce san

2>

< L a s c o n sta n te s 3 > < L a s variables globales 4 > < R u t i n a “S aveM em ory” 5 > < R u t i n a “m a in ”

6

>

2. Las ru tin a s p a ra el m an e jo d e la c a r ta de adquisición de im ágenes se e n c u e n tra n en la lib re ría “ig selib .h ” . R u tin a s tales com o inicializar la c a r ta de ad quisición, d ig ita liz a r u n a im agen, escrib ir u n p u n to en la m em o ria, leer un p u n to de la m em o ria, etc . En e s ta serie d e p ro g ram as solo se u tiliz a la r u tin a que nos in d ica la dirección de m em oria en d o nde se e n c u e n tra la c a r ta de adq u isició n de im ágenes. T odas las ru tin a s q u e p u d ie ra n e s ta r re la cio n ad a s con la t a r je ta se hicieron siguiendo el m an e jo e s ta n d a r d e a p u n ta d o re s q u e p e rm ite el len g u a je C. El archivo “s td io .h ” con tien e las ru tin a s de e n tra d a y salid a e s ta n d a r en el le n g u a je C. P a r a m ayor inform ación c o n su ltar la d o cu m e n ta ció n del len g u a je .

58

A P É N D IC E A . L A P R O G R A M A C IÓ N D E L M O D E L O . < L os archivos que se p reprocesan

2>

=

# i n c l u d e “igselib.h” # i n c l u d e “std io .h ” 3. La im agen dig ital que m a n e ja la c a rta de adquisición tie n e dim ensiones de 768 colum nas x 512 h ileras. C a d a pixel e s tá re p rese n ta d o p o r 8 b its, es decir tenem os 256 diferentes niveles de gris. < L a s c o n stan te s 3 > = # d e f i n e n um C olum nas (768) # d e f i n e num H ileras (512) 4. La variable screen es la dirección de m em o ria en do n d e com ienza el alm acenam iento de la im agen. < L a s variables globales 4 > = B y t e screen; 5. E s ta ru tin a re cu p era los d ato s de la m em o ria principal y los alm ac en a en u n archivo. < R u tin a “S aveM em ory” 5 > = v o id savelm age( ñam e) c h a r *name\ { B y t e *s,*r; in t j; F IL E *f, / # i n c l u d e “ig selib .h ” # i n c l u d e “s td io .h ” 3. L a im agen d ig ita l q u e m a n e ja la c a r t a d e adquisición tie n e dim ensiones de 768 co lu m n as x 5 1 2 h ileras. E s ta es la p rim e ra d e varias secciones en d o n d e las c o n s ta n te s e s tá n definidas. < L a s c o n sta n te s 3 > = ^ d e f i n e n u m C o lu m n a s (768) ^ d e f i n e num H ileras (512) Ver también 4.

4. El valor p a r a um bral es función de la im agen q u e se e s te p ro c esan d o , h a s ta d o n d e n o so tro s sab e m o s no h ay m a n e ra de d e te rm in a r su valor p o r m edios a u to m á tic o s . El valor d e um bral nos sirve p a r a e tiq u e ta r a un p u n to p (x , y) de la im a ­ gen de ac u erd o a dos clases, C O N T O R N O y F O N D O , d e la siguiente m anera: CONTORNO FO N D O

si p ( x ,y ) > um bral en o tro caso.

(A .l)

< L a s co n s ta n te s 3 > + = # d e f i n e um bral (15) ^¿define contorno (255) ^ d e f i n e fo n d o (0) 5. L a varia b le screen in d ic a la dirección de m em o ria en d o n d e co m ien z a la im agen.

64

A P É N D IC E A . L A P R O G R A M A C IÓ N D E L M O D E LO . < L a s variables globales 5 > = B y t e screen; 6.

El valor del g ra d ie n te / ( x , y ) , p a ra un p u n to p ( x t y ), se d e te rm in a de ac u erd o al filtro “R o b e rts ” por: f ( x ) = | p {x, y ) — p (x + 1, y + 1) I + \ p ( x , y + 1) - p (x + l , y ) | (A .2) < R u tin a “g ra d ie n t”

6>

=

v o id g ra d ie n t() { in t i j,n iv e l, , a¿, as , ; fo r (j um bral) { densidad 2) A ( densidad < 6 )) { p atrones *—propiedadB Q ,*); i f (patrones = 1 ) { i f ((p ro p ie d a d C (j,t)= 0 )A (p ro p ie d a d D (>;,t)= 0 )) { *(screen + n u m C o lu m n a s x i + j ) um bral)) next [9] < um bral) A («[2] > um bral)) n ext

< R u tin a s auxiliares 3 > < R u tin a P rin cip al 40 > 2. El archivo “s td io .h ” contiene las ru tin a s de e n tra d a y salid a e s ta n d a r en el len g u a je C. P a r a m ayor inform ación c o n s u lta r la docu m e n ta ció n del lenguaje. < Archivos “in clu d e” que se preprocesan 2 > = # i n c l u d e “s td io .h ”

A.6.

99

C O R R E S P O N D E N C IA .

3. Las ru tin a s que co n stitu y en el cu e rp o del p ro g ra m a están d ivididas en las siguientes p arte s: < R u tin a s au x iliares 3 > = < R ecu p eració n de inform ación 7 > < E s tu d io de la e s tru c tu ra

8

>

< C o rre sp o n d en cia 16 > < C álculo d e p ro fu n d id a d 38 > < R esu ltad o s 39 > 4. L a e s tru c tu ra “n o d e ” posee d a to s ac e rc a d e los d escriptores de los seg­ m entos de cu rv a, ay u d a s p a r a el proceso de co rresp o n d e n cia y re s u lta ­ dos: D e s c rip to re s : • n. L o n g itu d de la curva. C a d a u n id a d re p re s e n ta cinco pixeles. • m edia. D irección pro m ed io de la cu rv a, ex p resad o en radianes. • (x, y). C o o rd en a d as de la posición del ce n tro id e. E l origen del sis­ te m a de co o rd en ad as se e n c u e n tra en el m arg e n su p erio r izquierdo; el d esp laz am ien to p ositivo en las direcciones X y Y es h ac ia la d e re c h a y h ac ia a b a jo re sp ectiv am en te . • ( 2^05 í/o), (xj-, *//)• C o o rd en a d as d e los p u n to s inicial y final del seg m en to d e curva. A yu d as: • label. N úm ero de curva. • A x , A y . Valor ab so lu to del d e sp laz am ien to en los ejes X y Y , de la cu rv a con re sp ecto a su cu rv a co rresp o n d ien te . • longG rupo. Se u tiliz a cu a n d o la cu rv a h a en c o n trad o co rresp o n ­ d e n c ia ju n to a un g ru p o de curvas, re p re s e n ta la lo n g itu d del g ru p o . C a d a u n id ad re p re s e n ta cinco pixeles.

100

A P É N D IC E A . L A P R O G R A M A C IÓ N D E L M O D E L O . • circuito. Las curvas de los o b jeto s son a g ru p ad as de ac uerdo a si algún ex tre m o de u n a c u rv a e s tá “ce rca” de u n extrem o de o tra cu rv a diferente a ella m ism a. Id e alm en te, estos ag ru p am ien to s d e curvas re p rese n ta n e s tru c tu ra s ind ep e n d ie n tes de los o b jeto s. E stas e s tru c tu ra s son b a u tiz a d a s com o circuitos y son u tiliz ad as d u ra n te el proceso de c o rresp o n d e n cia d e g ru p o s de curvas. R e s u lta d o s : • z. C o o rd en a d a de p ro fu n d id a d del ce n tro id e calculada. • matched. C u rv a con la que se h a e n c o n trad o correspondencia. • group. Se u tiliz a cuando la cu rv a h a en c o n trad o correspondencia . com o u n g ru p o de curvas, re p re s e n ta el identificador del gru p o . E s ta es la p rim e ra de varias secciones, en d o nde se definen e s tru c tu ra s d e datos. < E s tru c tu ra s de datos 4 > = s t r u c t node{ f l o a t m edia; f l o a t x,y,r, f lo a t A x ,A y ; f lo a t longGrupo; i n t label,n,matched,group; in t x 0, y 0, x j , y j \ in t circuito; }; Ver también 5, 12, 13 y 14.

5. U n a im agen e s tá fo rm ad a p o r un c o n ju n to de curvas y el n ú m e ro d e circuitos que estas curvas form an. < E s tru c tu ra s de d ato s 4 > + = s t r u c t im age{ s t r u c t n ode *nodo; i n t inder, };

A .6.

C O R R E S P O N D E N C IA .

101

6. Las im ágenes e s tá n re p re s e n ta d a s p o r los d esc rip to res de sus curvas. Las variables imagen[0] e im agen[ 1] g u a rd a n inform ación de las curvas de la p rim e ra y seg u n d a im ag en re sp ectiv am en te . E s ta es la p rim e ra de varias secciones, en d o n d e se definen variables globales. < V ariables globales 6 > = s t r u c t im age im agen[2]; Ver también 28 y 35.

7. Los d e sc rip to res d e las cu rv as son a lm ac en ad a s en el archivo “o u tp u t2 ” p o r el p roceso d e extra cc ió n d e contornos. El n ú m e ro de curvas que se e x tra je ro n en c a d a im agen e s tá alm ac en ad o en el arch iv o wo u tp u t3 ” . El espacio p a r a a lm ac en ar e s ta inform ación en m em o ria p rin cip a l es reservado al m om en to de ejecución del p ro g ram a. < R ecu p e ra ció n de inform ación 7 > = v o id lo a d In fo rm atio n (){ i n t i; F I L E * f* g ; s t r u c t n o d e m sr; / < A p a rea m ie n to e n tre e s tru c tu ra s 23 > < A p a rea m ie n to p o s te rio r 25 > 17. L a e s tru c tu ra m a tch es fo rm a lm e n te u n grafo relacional. E n la v aria b le m a tc h .ite m [i\ se alm a c e n a rá el g rupo de curvas que c o rresp o n d e rán con la cu rv a i. < Inicializacion de la e s tru c tu ra de co rresp o n d e n cia 17 > = v o id in itM a tc h S tru c tu re () { s t r u c t h ilera rour, in t i ; m a tch .in d e x -f = ^ ¿ d e fin e cocienteL ong (0.8)

108 22.

A P É N D IC E A . L A P R O G R A M A C IÓ N D E L M O D E L O . C a d a cu rv a de la p rim e ra im agen es co m p a ra d a con ca d a cu rv a de la segunda. C u an d o los d escriptores de am bas son sim ilares conside­ ram os que h a h a b id o co rrespondencia y la reg istra m o s p a ra fu tu ra s referencias. D espués analizam os el co m p o rta m ie n to general de los d e­ splazam ientos d e los centroides de las curvas que correspondieron; con ésto obtenem os inform ación ú til p a ra resolver am bigüedades. Los d e ­ scrip to res utilizados en la com paración son: L o n g i t u d . El co cien te d e la curva de m en o r long itu d con el d e m ayor d e b e rá ser m ay o r d e cocienteLong. D i r e c c i ó n . L a d iferen cia e n tre el prom edio de las direcciones d e b e rá ser m en o r d e 02o grados. D e s p l a z a m i e n t o ,d e l C e n t r o i d e . L a d iferencia e n tre la c o o rd en ad a X d e b e rá ser m en o r de separaciónlm agenes pixeles.
=

v o id m atchS ingleL ine(){ i n t » J ,in d e r, i n t histogram a[num H ileras],m áxim o,m ínim o; flo a t A l , A x , A y , A m e d ia , m j , m¿; f o r (t = m a in () { num ero grupo «— 1; lo ad In fo rm atio n (); c re a te S tru c tu re (& imagen[0\ ); create S tru c tu re(& w ia < 7en[l]); in itM a tc h S tru c tu re (); m atchS ingleL ineQ ; m atch C o m p letG ra p h Q ; p o stM atch in g (); ca lcu leD e p th (); sav elnform ationQ ;

■

} calculeDepth:procedimiento, §38 matchCompletGraphrprocedimiento, §23 imayenivariable, §6 n«meroGr«po:variable, §35 s&velnform&tion:procedimiento, §39

cre«teStructurc:procediniiento, §8 matchSingleLine:procediiniento, §22 initMatchStructure:procedim iento, §17 postM atching:procediiniento, §25

Lista de Figuras 1.1 1.2 1.3 1.4 1.5 1.6 1.7 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9

T r a n s f o r m a c i ó n d e p e r s p e c t i v a ..................................................... G e o m e t r í a e s t e r e o .................................................................................. G e o m e t r í a s i m p l i f i c a d a ...................................................................... G e o m e t r í a e s t e r e o s im p l i f i c a d a ..................................................... D e te c c ió n d e c a m b io s e n u n a i m a g e n u n i d i m e n s io n a l . . F a c t o r e s e s p a c i a l e s y d ir e c c io n a le s e n la a p lic a c ió n d e l a s e g u n d a d e r i v a d a ............................................................................... R e s t r i c c ió n d e c o n t i n u i d a d .................................................................

4 6 8

9 10 12

15

D i a g r a m a a b lo q u e s d e l m o d e lo p r o p u e s t o ............................... 18 C á lc u lo d e l f i l t r o g r a d i e n t e ................................................................ 20 V e c in o s d e l p u n t o P\ e n u n a v e n t a n a d e 3 x 3 .................... 21 A p r o x im a c i ó n d e u n o b j e t o p o r s e g m e n t o s d e r e c t a s . . 24 E j e m p l o d e u n a v e n t a n a ................................................................. 26 R e p r e s e n t a c ió n d e u n a e s t r u c t u r a r e la c i o n a l p o r u n g r a f o ............................................................................................................. 29 P r o x i m i d a d m e d i a t a e i n m e d i a t a .............................................. 31 Im á g e n e s o r i g i n a l e s d e l a t a s a .................................34 Im á g e n e s g r a d i e n t e d e la t a s a ................................. 34 A d e lg a z a m i e n t o d e lín e a s d e la t a s a ......................................... 35 E x t r a c c i ó n d e c o n t o r n o s d e la t a s a ..........................................35 E t i q u e t a c i ó n d e la s c u r v a s e x t r a í d a s a la s i m á g e n e s d e l a t a s a ............................................................................................................ 36 Im á g e n e s o r i g i n a l e s d e la s r a q u e t a s .................... 38 Im á g e n e s g r a d i e n t e d e la s r a q u e t a s .................... 39 A d e l g a z a m i e n t o d e l í n e a s a la s i m á g e n e s d e la s r a q u e t a s . 40 E x t r a c c i ó n d e c o n t o r n o s a la s im á g e n e s d e la s r a q u e t a s . 41 125

126

L IS T A D E F IG U R A S 3.10 E t i q u e t a c i ó n d e la s c u r v a s e x t r a í d a s a la s i m á g e n e s d e la s r a q u e t a s ................................................................................................ 42 3.11 I m á g e n e s o r i g i n a l e s d e l l a b o r a t o r i o .......................................... 45 3.12 I m á g e n e s g r a d i e n t e d e l l a b o r a t o r i o ( 1 ) .................................. 46 3.13 A d e lg a z a m i e n t o d e l ín e a s a la s im á g e n e s del 3.14 E x t r a c c i ó n d e c o n t o r n o s a la s i m á g e n e s del 3.15 E t i q u e t a c i ó n d e la s c u r v a s e x t r a í d a s d e la s i m á g e n e s d e l l a b o r a t o r i o ..........................................................................................49

l a b o r a t o r i o . 47 l a b o r a t o r i o . 48

Lista de Tablas 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8

D e s c r i p t o r e s d e lo s s e g m e n t o s d e c u r v a e x t r a í d o s d e l a t a s a ................................................................ ........................................... 37 R e s u l t a d o s d e l a p a r e a m i e n t o d e la s c u r v a s e n la s i m á g e n e s d e l a t a s a . P r i m e r a e t a p a ................... ........................................... 37 R e s u l t a d o s d e l a p a r e a m i e n t o d e la s c u r v a s e n la s i m á g e n e s d e l a t a s a . S e g u n d a e t a p a .................. ........................................... 37 D e s c r i p t o r e s d e lo s s e g m e n t o s d e c u r v a e x t r a í d o s d e la s r a q u e t a s ................................................... ........................................... 43 R e s u l t a d o s d e l a c o r r e s p o n d e n c i a e n la s r a q u e t a s . P r i m e r a e t a p a .................................................................. ........................................... 44 R e s u l t a d o s d e l a c o r r e s p o n d e n c i a e n la s r a q u e t a s . S e g u n d a e t a p a .................................................. ........................................... 44 D e s c r i p t o r e s d e lo s s e g m e n t o s d e