Estimació del moviment de robots mitjançant contorns actius

Estimaci´o del moviment de robots mitjan¸cant contorns actius Guillem Aleny`a Ribas Tesi realitzada al programa de doctorat Control, Visi´o i Rob`otica (ESAII) Directora: Carme Torras Aquesta tesi es presenta per a l’obtenci´o del grau de Doctor Barcelona, 2007 Universitat Polit`ecnica de Catalunya Departament d’Enginyeria de Sistemes, Autom`atica i Inform`atica Industrial Programa de doctorat: Control, Visi´o i Rob`otica Aquesta tesi ha estat realitzada a: Institut de Rob`otica i Inform`atica Industrial, CSIC-UPC Directora de tesi: Carme Torras Tribunal de tesi: Alberto Sanfeliu (Universitat Polit`ecnica de Catalunya) (President) James L. Crowley (INRIA - Rhone-Alpes) R¨udiger Dillmann (Universit¨at Karlsruhe) Norbert Kr¨uger (University of Southern Denmark) Elisa Mart´ınez Marroqu´ın (Universitat Ramon Llull) c Guillem Aleny`a 2007 Voldria que tots els que llegissin la meva novel·la participessin en la meva emoci´o. Em fa contenta pensar que entre tants milers de lectors com ha tingut i continua tenint n’hi ha molts que no havien llegit mai res en catal`a i que ´es llegint-la que han descobert que la nostra era una llengua civilitzada, culta, important. I would like all that read my novel to participate in my emotion. It makes me happy to think that, among the many thousands of readers that it has had and it continues having, there are many who had never read anything in Catalan and it is by reading my novel that they have discovered that ours is a civilized, cultivated, meaningful language. Merc`e Rodoreda. La pla¸ca del diamant (pr`oleg). A la Susanna, per la vida que ens dediquem. No m’ho imagino d’altra manera. I per les dues tesis que tenim a mitges. La seva inquietud per aprendre ´es inspiraci´o. A la Carme. Gr`acies per compartir el cami; i donar-me bones eines. A tots els companys de causa, gr`acies per les discusions i per deixar-me pensar en veu alta. Resum Aquesta tesi versa sobre l’estimaci´o del moviment d’un robot m`obil a partir dels canvis en les imatges captades per una c`amera muntada sobre el robot. El moviment es dedueix amb un algorisme pr`eviament proposat en el marc de la navegaci´o qualitativa. Per tal d’emprar aquest algorisme en casos reals s’ha fet un estudi de la seva precisi´o. Per augmentar-ne l’aplicabilitat, s’ha adaptat l’algorisme al cas d’una c`amera amb moviments d’orientaci´o i de zoom. Quan els efectes perspectius no s´on importants, dues vistes d’una escena captades pel robot es poden relacionar amb una transformaci´o af´ı (o afinitat), que normalment es calcula a partir de correspond`encies de punts. En aquesta tesi es vol seguir un enfoc alternatiu, i alhora complementari, fent servir la silueta d’un objecte modelada mitjan¸cant un contorn actiu. El marc es el seg¨uent: a mesura que el robot es va movent, la projecci´o de l’objecte a la imatge va canviant i el contorn actiu es deforma convenientment per adaptar-s’hi; de les deformacions d’aquest contorn, expressades en espai de forma, se’n pot extreure el moviment del robot fins a un factor d’escala. Els contorns actius es caracteritzen per la rapidesa en la seva extracci´o i la seva robustesa a oclusions parcials. A m´es, un contorn ´es f`acil de trobar fins i tot en escenes poc texturades, on sovint ´es dif´ıcil trobar punts caracter´ıstics i la seva correspond`encia. La primera part d’aquest treball t´e l’objectiu de caracteritzar la precisi´o i la incertesa en l’estimaci´o del moviment. Per avaluar la precisi´o, primer es duen a terme un parell d’experi`encies pr`actiques, que mostren la potencialitat de l’algorisme en entorns reals i amb diferents robots. Estudiant la geometria epipolar que relaciona dues vistes d’un objecte planar es demostra que la direcci´o epipolar af´ı es pot recuperar en el cas que el moviment de la c`amera estigui lliure de ciclorotaci´o. Amb una bateria d’experiments, tant en simulaci´o com reals, es fa servir la direcci´o epipolar per caracteritzar la precisi´o global de l’afinitat en diferents situacions, com ara, davant de diferents formes dels contorns, condicions de visualitzaci´o extremes i soroll al sistema. Pel que fa a la incertesa, gr`acies a que la implementaci´o es basa en el filtre de Kalman, per a cada estimaci´o del moviment tamb´e es t´e una estimaci´o de la incertesa associada, per`o expressada en espai de forma. Per tal propagar la incertesa de l’espai de forma a l’espai de moviment 3D s’han seguit dos camins diferents: un anal´ıtic i l’altre estad´ıstic. Aquest estudi ha perm`es determinar quins graus de llibertat es recuperen amb m´es precisi´o, i quines correlacions existeixen entre les diferents components. Finalv ment, s’ha desenvolupat un algorisme que permet propagar la incertesa del moviment en temps de v´ıdeo. Una de les limitacions m´es importants d’aquesta metodologia ´es que cal que la projecci´o de l’objecte estigui dins de la imatge i en condicions de visualitzaci´o de perspectiva d`ebil durant tota la seq¨u`encia. En la segona part d’aquest treball, s’estudia el seguiment de contorns actius en el marc de la visi´o activa per tal de superar aquesta limitaci´o. ´ Es una relaci´o natural, at`es que el seguiment de contorns actius es pot veure com una t`ecnica per fixar el focus d’atenci´o. En primer lloc, s’han estudiat les propietats de les c`ameres amb zoom i s’ha proposat un nou algorisme per determinar la profunditat de la c`amera respecte a un objecte qualsevol. L’algorisme inclou un senzill calibratge geom`etric que no implica cap coneixement sobre els par`ametres interns de la c`amera. Finalment, per tal d’orientar la c`amera adequadament, compensant en la mesura del possible els moviments del robot, s’ha desenvolupat un algorisme per al control dels mecanismes de zoom, capcineig i guinyada, i s’ha adaptat l’algorisme d’estimaci´o del moviment incorporant-hi els girs coneguts del capcineig i la guinyada. vi Abstract This thesis deals with the motion estimation of a mobile robot from changes in the images acquired by a camera mounted on the robot itself. The motion is deduced with an algorithm previously proposed in the framework of qualitative navigation. In order to employ this algorithm in real situations, a study of its accuracy has been performed. Moreover, relationships with the active vision paradigm have been analyzed, leading to an increase in its applicability. When perspective effects are not significant, two views of a scene are related by an affine transformation (or affinity), that it is usually computed from point correspondences. In this thesis we explore an alternative and at the same time complementary approach, using the contour of an object modeled by means of an active contour. The framework is the following: when the robot moves, the projection of the object in the image changes and the active contour adapts conveniently to it; from the deformation of this contour, expressed in shape space, the robot egomotion can be extracted up to a scale factor. Active contours are characterized by the speed of their extraction and their robustness to partial occlusions. Moreover, a contour is easy to find even in poorly textured scenes, where often it is difficult to find point features and their correspondences. The goal of the first part of this work is to characterize the accuracy and the uncertainty in the motion estimation. Some practical experiences are carried out to evaluate the accuracy, showing the potentiality of the algorithm in real environments and with different robots. We have studied also the epipolar geometry relating two views of a planar object. We prove that the affine epipolar direction between two images can be recovered from a shape vector when the camera motion is free of cyclorotation. With a battery of simulated as well as real experiments, the epipolar direction allows us to analyze the global accuracy of the affinity in a variety of situations: different contour shapes, extreme visualization conditions and presence of noise. Regarding uncertainty, since the implementation is based on a Kalman filter, for each motion estimate we have also its covariance matrix expressed in shape space. In order to propagate the uncertainty from shape space to 3D motion space, two different approaches have been followed: an analytical and a statistical one. This study has allowed us to determine which degrees of freedom are recovered with more accuracy, and what correlations exist between the different motion components. Finally, an vii 1. Introducci´o matem`atics que sovint s´on simplificacions, ja que nom´es modelen una part de la realitat. I finalment, als robots se’ls demana que actu¨ın en temps real. Aix`o fa que el temps disponible per al c`omput estigui limitat i obligui a fer certes aproximacions sacrificant precisi´o per rapidesa. Aquest treball versa sobre l’estimaci´o del moviment d’un robot m`obil a partir dels canvis en les imatges captades per una c`amera muntada sobre el robot.1Fins fa poc, lavisi´o no era un dels sensors preferits en aplicacions de rob`otica m`obil, sobretot industrial, per darrere de l’odometria, dels sensors d’infraroigs, dels ultrasons, dels l`asers i ´ultimament del GPS. Per`o actualment, gr`acies als esfor¸cos fets en el camp de la visi´o artificial, aquesta adquireix m´es import`ancia i esdev´e una eina que cal tenir en compte en rob`otica, i en especial per a l’autolocalitzaci´o i la navegaci´o. Una de les limitacions principals en visi´o artificial quan es vol recuperar el moviment de la c`amera ´es la inherent p`erdua d’informaci´o en el proc´es de formaci´o de la imatge: a partir d’informaci´o parcial 2D es vol recuperar el moviment 3D de la c`amera. ´ Es per aix`o que en general es tendeix a enriquir el sistema de visi´o amb diverses c`ameres, o s’imposen restriccions sobre el moviment o l’escena. ´ Es clar que com m´es informaci´o es t´e sobre l’entorn, m´es i millor informaci´o es pot recuperar, per`o l’enfocament que es vol seguir en aquesta tesi ´es partir del coneixement del menor nombre possible de par`ametres (per exemple, dels par`ametres de calibratge de la c`amera), i donar les claus per aprofitar aquesta informaci´o addicional en el cas que estiguin disponibles. Quan els efectes perspectius no s´on importants, dues vistes d’una escena captades pel robot es poden relacionar amb una transformaci´o af´ı (o afinitat), que normalment es calcula a partir de correspond`encies de punts. Trobar correctament aquestes correspond`encies encara ´es un tema no completament solucionat en visi´o artificial [90,126]. En aquesta tesi es vol seguir un enfocament alternatiu, i alhora complementari, fent servir contorns actius [17]. Un contorn actiu ´es una corba que s’inicialitza al voltant de la projecci´o d’un objecte en la imatge. A mesura que el robot es va movent, la projecci´o de l’objecte en la imatge va canviant i el contorn actiu es deforma convenientment per adaptar-s’hi. De les deformacions d’aquest contorn, expressades en espai de forma [97], se’n pot extreure el moviment del robot fins a un factor d’escala. Els contorns actius es caracteritzen per la rapidesa en la seva extracci´o i la seva robustesa en les oclusions 1Fent un s´ımil biol`ogic, l’objectiu ´es determinar com s’ha “mogut” analitzant els canvis en el que “veu”. 2 1.1 Motivaci´o parcials. A m´es, un contorn ´es f`acil de trobar fins i tot en escenes poc texturades, on sovint ´es dif´ıcil trobar punts caracter´ıstics i la correspond`encia que tenen. El model de c`amera emprat ´es el de perspectiva d`ebil. Perqu`e aquest model sigui aplicable cal que es compleixin dues condicions de visualitzaci´o. Primer, que l’objecte que es mira sigui pla o, si m´es no, que la profunditat (el que a vegades s’anomena relleu) del contorn de l’objecte sigui petita en comparaci´o amb la dist`ancia de la c`amera a l’objecte.2Segon, que la projecci´o del contorn tingui lloc a prop del centre `optic.3En aquest tipus de visi´o monocular apareixen t´ıpicament diverses ambig¨uitats. L’algorisme de seguiment que es presenta fa la suposici´o que el contorn est`a frontoparal·lel en la primera imatge per discernir l’ambig¨uitat que hi ha entre profunditat i gir. Com ´es com´u en visi´o monocular, la translaci´o es recupera fins a un factor d’escala. Aquest factor d’escala dep`en tant de la dist`ancia inicial entre c`amera i objecte com dels par`ametres de calibratge de la c`amera. Hi ha diversos motius per considerar la incertesa en les dades provinents d’un sistema de visi´o. D’una banda, la resoluci´o limitada de les c`ameres i la qualitat del senyal de v´ıdeo provoquen que les dades amb qu`e es treballa siguin imprecises. De l’altra, la qualitat de les imatges tamb´e es veu afectada per les condicions d’il·luminaci´o, els reflexos, les distorsions de les lents emprades i, en general, per un nombre elevat de circumst`ancies no sempre controlables i/o mesurables [92]. Tamb´e cal tenir en compte l’error que s’introdueix identificant la posici´o en la imatge de les caracter´ıstiques que es busquen, en aquest cas el contorn de l’objecte. Un dels objectius que es persegueix ´es caracteritzar la incertesa del moviment obtingut a partir de les deformacions d’un contorn actiu. Cal con`eixer quins factors afecten la recuperaci´o del moviment, la incertesa de cadascuna de les components i trobar les possibles correlacions. Perqu`e sigui ´util en la navegaci´o del robot l’objectiu ´es trobar un algorisme que permeti avaluar i calcular en temps real la incertesa de cada nou moviment que es computa. 2Utilitzar una c`amera de perspectiva d`ebil en escenes on hi ha diversos objectes a diferents profunditats generalment no ´es una bona aproximaci´o. Tanmateix, l’algorisme proposat fixa l’atenci´o en un sol objecte de l’escena, i per tant nom´es cal que l’objecte en q¨uesti´o tingui poc relleu en comparaci´o amb la seva dist`ancia a la c`amera. 3Habitualment si s’utilitza una c`amera amb dist`ancia focal gran s’acompleix aquesta restricci´o. 3 1. Introducci´o Una de les limitacions m´es importants de l’algorisme de recuperaci´o del moviment basat en el seguiment de contorns actius ´es que cal que l’objecte estigui visible durant tota la seq¨u`encia. Dotant el robot d’un sistema de visi´o activa es permet que la c`amera canvi¨ı la seva orientaci´o compensant el moviment del robot. El paradigma de la visi´o activa, amb tot el que implica respecte a l’atenci´o visual, combina perfectament amb la proposta de fer servir contorns actius, que de fet s´on una de les vies per concentrar l’atenci´o del sistema de visi´o. En la mateixa l´ınia, les lents amb zoom afegeixen un grau de llibertat extra al sistema de visi´o, ja que permeten controlar el grau d’obertura de la c`amera. Per segons quina aplicaci´o pot ser interessant prendre una imatge m´es detallada de l’objectiu, o a l’inrev´es, una imatge m´es panor`amica de l’escena. Encara que sembli atractiu afegir un zoom a la c`amera ´es un camp no gaire explorat, segurament a causa de la complexitat que afegeix. Primer, perqu`e quan es fa zoom canvia la resoluci´o i, per tant, l’aparen¸ca dels objectes, i la correspond`encia entre imatges ´es m´es dif´ıcil de solucionar.4 Segon, perqu`e canvien els par`ametres de calibratge de la c` amera i, per tant, canvia la correspond`encia entre les mesures en la imatge i el sistema de coordenades de m´on. Aix`o ´es important si es volen fer mesures m`etriques. I finalment, perqu`e canvien els guanys del sistema de control de l’orientaci´o de la c`amera, cosa que en fa m´es dif´ıcil el control. L’objectiu ´es fer que l’algorisme de c`alcul del moviment sigui m´es ´util encara incorporant una c`amera activa al robot. El cam´ı seguit passa per proposar un algorisme de control que permeti canviar el zoom i orientar la c`amera perqu`e mantingui l’objectiu centrat en la imatge el m`axim de temps possible mentre el robot navega lliurement, cosa que amplia considerablement la zona de treball. Cal proposar un nou algorisme que permeti calcular el moviment del robot tenint en compte tamb´e el moviment d’orientaci´o de la c`amera. 1.2 Compendi de la tesi Aquesta tesi s’estructura com segueix. Al cap´ıtol 2s’introdueixen els principis sobre els quals es desenvolupar`a la resta de la tesi: el seguiment de contorns actius, la pa4El problema pren import`ancia si es considera que sovint caracter´ıstiques que ressalten basades en punts o cantonades, ho fan nom´es a certes resolucions i no s´on, per tant, invariants a zoom. 4 1.2 Compendi de la tesi rametritzaci´o (que anomenarem vector de forma) de la deformaci´o d’aquests contorns en un espai de transformacions del pla de la imatge (que anomenarem espai de forma), i l’algorisme que permet extraure d’aquesta parametritzaci´o l’estimaci´o del moviment del robot. Es presenten dos treballs previs realitzats, encaminats a avaluar la viabilitat del seguiment de contorns actius en rob`otica m`obil. Primer, en el marc del transport de mercaderies, es presenta una comparaci´o amb un sensor de posicionament l`aser. La precisi´o assolida, quan es coneixen els par`ametres de calibratge de la c`amera i s’expressa el moviment en coordenades de c`amera, ´es prometedora. Segon, en el marc d’un vehicle de transport de persones, es presenta la col·laboraci´o del sistema de visi´o amb un sensor inercial. La soluci´o emprada en aquest cas ´es expressar la informaci´o del sensor inercial en l’espai de deformacions que parametritza el moviment de la c`amera. Un cop analitzada la viabilitat del seguiment de contorns, al cap´ıtol 3es fa un estudi m´es en profunditat de la geometria de dues vistes i es presenta un nou algorisme que permet calcular la direcci´o epipolar a partir de dues vistes no calibrades d’un objecte pla. S’observa que la direcci´o epipolar ´es un bon indicador de la qualitat del vector de forma calculat i es du a terme una primera aproximaci´o al problema de determinar la precisi´o de l’algorisme de recuperaci´o del moviment propi fent un bateria d’experiments. En aquests experiments es relaciona la precisi´o obtinguda en la recuperaci´o de la direcci´o epipolar amb diferents situacions de relaxaci´o de les condicions de visualitzaci´o de perspectiva d`ebil, la forma del contorn i el soroll d’adquisici´o. Els experiments reals, amb un bra¸c rob`otic St¨aubli, permeten validar l’algorisme de recuperaci´o de la direcci´o epipolar i comparar-lo amb el m`etode est`andard basat en correspond`encies de punts. Un estudi en profunditat de la precisi´o de l’algorisme de recuperaci´o del moviment requereix considerar les sis components de la posa. Al cap´ıtol 4es desenvolupen les expressions anal´ıtiques per a la propagaci´o de la incertesa suposant que les diferents components s´on independents. A escala qualitativa els resultats s´on correctes, per`o desafortunadament, la incertesa calculada est`a clarament subestimada ateses les aproximacions que cal fer. Al cap´ıtol 5es mostra un segon enfocament de l’an`alisi de la precisi´o, aquest cop estad´ıstic, que es veur`a que ofereix interessants possibilitats de treball futur. Primer es caracteritza la incertesa amb una simulaci´o de Monte Carlo, que permet observar quines components del moviment es recuperen amb m´es precisi´o i les correlacions que hi ha entre les components. Es proposa un algorisme que permet 5 1. Introducci´o fer el c`alcul del moviment del robot i de la seva incertesa en temps real, i se’n prova la correctesa amb experiments reals. Com ja s’ha esmentat, el moviment que es recupera est`a escalat, a causa d’una s`erie de par`ametres que es consideren desconeguts: calibratge de la c`amera i dist`ancia inicial. D’aquests, el par`ametre que sembla m´es dif´ıcil d’obtenir ´es la dist`ancia inicial entre la c`amera i l’objectiu. Al cap´ıtol 6s’introdueix la c`amera amb dist`ancia focal variable, iaprofitant el moviment del zoom es proposa un nou algorisme, basat en calibratge geom`etric, que permet estimar aquesta dist`ancia inicial amb un senzill m`etode, que no requereix el calibratge dels par`ametres interns de la c`amera. En el conjunt del treball fet s’observa que el repertori de moviments que pot fer el robot ´es molt limitat: l’objecte ha de trobar-se al davant del robot i els moviments estan restringits gaireb´e a aproximacions i retrocessos per no perdre’l de vista. Al cap´ıtol 7, en primer lloc es proposa un algorisme per controlar el zoom. D’aquesta manera es pot mantenir constant la mida de la projecci´o del contorn en la imatge, i aix´ı permetre aproximacions i retrocessos m´es llargs. Se’n mostra experimentalment la validesa i tamb´e es mostra l’algorisme per recuperar el moviment de la c`amera. En segon lloc s’explora la possibilitat de canviar l’orientaci´o de la c`amera amb un mecanisme de capcineig i guinyada. Aix`o permet al robot fer traject`ories molt m´es generals, ja que la c`amera ara t´e la capacitat de mantenir l’objecte dins del camp de visi´o per ella mateixa. D’una banda, es proposa un algorisme que permet tancar els diferents lla¸cos de control del sistema de visi´o activa, que permeten mantenir l’objecte dins del camp de visi´o mentre el robot es despla¸ca. De l’altra, es proposa un nou algorisme que permet recuperar el moviment del robot amb una c`amera activa. Els experiments realitzats proven tant la correctesa de l’algorisme de control proposat com la validesa de l’algorisme de c`alcul del moviment. El cap´ıtol 8´es el darrer de la tesi i inclou les conclusions, un resum de les aportacions m´es rellevants portades a terme i una petita discussi´o sobre el treball futur. At`es que les aportacions que es fan inclouen diferents `arees de coneixement, la descripci´o de l’estat de l’art no es concentra en un sol cap´ıtol, com ´es habitual, sin´o que cada cap´ıtol inclou un apartat que exposa la literatura utilitzada sobre cada tema concret. 6 Chapter 1 Introduction It is the scientist duty to raise our abilities by increasing our standards for quality and effectiveness, to show what can be done well by pursuing the just possible, and to clarify ruthlessly, independently of the fact that complexity sells better. Edsger W. Dykstra, april 1986. EDW956-2. 1.1 Motivation A robot can be defined as a mechanical device with the ability of perceiving and manipulating the environment [133]. More and more, robots have to work in unstructured and dynamic environments, where the sensory capacity becomes crucial to help solving the great number of unforeseen situations that can turn up. In this scenario, robotics is no longer just a problem of mechanics and becomes a science, with the goal of developing more sophisticated algorithms to confront directly the different problems that appear in these environments. A great number of factors add noise and uncertainty to this task, and in order to design better algorithms it is necessary to consider this uncertainty. On the one hand, it is necessary to take into account that sensors have limited perception, and also that they are sensitive to external disturbances. On the other hand, the actuators and the robot control system not always fulfil the commands in the expected way. These commands are calculated based on mathematical models that often are simplifications. And, finally, robots are expected to act in real-time. This implies that time for the calculation is limited, which forces to make certain approximations sacrificing accuracy for speed. 7 1. Introduction This work deals with the estimation of the motion of a mobile robot by observing the changes in the images acquired by a camera mounted on the own robot1. Until little ago, vision was not one of the favourite sensors in applications of mobile robotics, especially in industrial robotics, behind odometry, infrafed sensors, ultrasound, laser, and lately GPS. But at present, thanks to the efforts made in the field of artificial vision, it has acquired more importance and has become a tool to take into account in robotics, and specifically in self-localization and navigation problems. One of the main limitations of artificial vision, when the goal is to compute the motion of the camera, is the inherent loss of information in the process of image formation: from 2D partial information we want to retrieve the complete 3D camera motion. For this reason, the general trend is to endow the vision system with several cameras, or to impose restrictions on the motion or the scene. Of course, as more information about the environment is available, more and better motion information can be recovered. However, the path followed in this thesis is to start from the knowledge of the least possible number of parameters (for example, of the calibration parameters of the camera), and to give the clues to be able to use this additional information in the case that it becomes available. When perspective effects are not significant, two views of a scene can be related by an affine transformation (or affinity), which is usually calculated from point correspondences. Finding correctly these correspondences is a subject still not completely solved in artificial vision [90,126]. In this thesis we want to evaluate an alternative, and at the same time complementary, technique that uses active contours [17]. An active contour is a curve that is initialized around the projection of an object in the image. When the robot moves freely, the projection of the object in the image changes and the active contour deforms itself conveniently to adapt to it. From the deformations of this contour, expressed in shape space form [97], the robot motion can be extracted up to a scale factor. Active contours are very easy to track, and are also robust to partial occlusions. Moreover, a contour is easy to find even in poorly textured scenes, where characteristic points and their correspondences are difficult to find. The camera model used is the weak-perspective one. Two visualization conditions should be fulfilled to be able to use this model. First, the target object should be planar or, at least, the depth (sometimes called relief) of the object contour should be small in 1Making a biological comparison, the goal is to determine how it has “moved” analyzing the changes in what it “sees”. 8 1.1 Motivation comparison with the distance from the camera to the object2. Second, the projection of the contour should lie near the optical center3. In this type of monocular vision typically several ambiguities appear. The tracking algorithm presented makes the assumption that the object is frontoparallel in the first image to discern the existing ambiguity between depth and turning. As usual in monocular vision, translations are recovered up to a scale factor. This scale factor depends on the initial distance between the camera and the object as well as on the camera calibration parameters. There are several reasons for considering the uncertainty in the data coming from a vision system. On the one hand, the limited resolution of the cameras and the quality of the video signal lead to lack of precision. On the other hand, the quality of the images is also affected by the lighting conditions, the reflections, the lens distortions, and in general by a high number of circumstances not always controllable and/or measurable [92]. Finally, the errors produced when obtaining the position of the landmarks in the image, in our case the position of the object contour, should be taken into account. One of the thesis objectives is to characterize the uncertainty of the motion obtained from the deformations of an active contour. It is necessary to determine which factors influence motion recovery, to estimate the uncertainty of each motion component, and to find the possible correlations between them. To be useful for robot navigation, the algorithm developed should allow to evaluate and to calculate the uncertainty of each new computed motion in real time. One of the most severe limitations of the motion recovery algorithm based on the tracking of active contours is that the object should keep visible during all the motion sequence. Providing the robot with an active vision system dissociates robot and camera motion, allowing the camera to change its orientation, thus offsetting the robot motion. The active vision paradigm, with all its implications with respect to visual attention, combines perfectly with the proposal of using active contours, which in fact is one of the ways to concentrate the attention of the vision system. 2Using weak-perspective camera models in scenes where there are several objects at different depths is generally not a good approach. However, the proposed algorithm fixes the attention on an object of the scene alone, and therefore it is only necessary that this object has little depth relief in comparison with its distance to the camera. 3This restriction is usually satisfied using a camera with a large focal distance. 9 1. Introduction Along the same line, zoom lenses add an extra degree of freedom to the vision system, allowing to control the field of view of the camera. For some applications it can be interesting to take more detailed images of the target, or conversely, a more panoramic image of the scene. Even if it seems attractive to add a zoom to the camera, it is a field hardly explored, probably because of the added complexity. First, because zoom changes the resolution of the image and, therefore, the appearance of the objects, making the correspondence between images more difficult to solve4. Second, because the camera calibration parameters change, and accordingly, the correspondence between measures in the image and world coordinates also changes. This is important if metric measures are expected. And, finally, because zoom changes the gains of the orientation control system, which becomes more difficult to control. A final goal is to increase the applicability of the motion recovery algorithm by incorporating an active camera to the robot. The path followed is to propose a control algorithm to change the zoom and to turn the camera to keep the target projection centered on the image if possible while the robot moves freely, broadening considerably the robot workspace. It becomes necessary to propose a new algorithm to estimate robot motion taking into account also the change in orientation of the camera. 1.2 Summary of the thesis This thesis is structured as follows. Chapter 2introduces the principles used to develop the rest of the thesis: the tracking of active contours, the parametrization (called shape vector) of the deformation of this contour in a space of transformations of the image plane (called shape space), and the algorithm to extract the motion estimation from this parametrization. Two introductory works are also presented, aimed at estimating the feasibility of the tracking of active contours in mobile robotics. First, within the framework of goods transportation, a comparison with a positioning laser sensor is presented. The accuracy attained, when the parameters of calibration of the camera are known and the motion is expressed in camera coordinates, is promising. Second, within the framework of people transportation, the collaboration of the vision system with an inertial sensor is presented. The solution adopted in this case is to express 4The problem gains importance if one considers that often salient characteristics based on points or corners are salient only for certain resolutions and they are not, therefore, zoom invariant. 10 1.2 Summary of the thesis the inertial information in the space of deformations that parameterizes the camera motion. Once the feasibility of egomotion recovery from contour tracking has been stablished, in Chapter 3two-view geometry is revisited, and a new algorithm to calculate the epipolar direction from two uncalibrated views of a planar object is presented. It is also noticed that the accuracy of the epipolar direction is a good measure of the quality of the shape vector. A first approach to the problem of determining the accuracy of the motion recovery algorithm is conducted by making a series of experiments. In these experiments, the accuracy obtained in the recovery of the epipolar direction is related to different situations of relaxation of the weak-perspective visualization conditions, the form of the contour and the acquisition noise. The real image experiments, using a St¨aubli robotic arm, allow us to validate the algorithm of recovery of the epipolar direction and to compare it with the standard method based on point correspondences. An in-depth study of the accuracy of the algorithm requires to consider the complete set of 6 pose components. Chapter 4presents the analytical expressions derived for the propagation of the uncertainty, assuming independence between the different components. Results are correct at a qualitative level, but unfortunately the calculated uncertainty is clearly underestimated due to the approximations which it is necessary to make. In Chapter 5a statistical approach to the analysis of the accuracy is presented, which will be seen to offer interesting future work possibilities. First, the uncertainty is characterized through a Monte Carlo simulation, that allows to observe which motion components are recovered with more or less accuracy, as well as the correlations between them. An algorithm to calculate robot motion and its uncertainty in real time is also proposed, and its correctness is assessed through real-world experiments. As already mentioned, the recovered motion, in fact the translation components, is scaled due to the fact that some parameters are considered unknown: calibration parameters of the camera and the initial distance. Of these, the parameter that seems more difficult to obtain is the initial distance between the camera and the target. The camera with variable focal distance is introduced in Chapter 6. Using zoom motions, a new algorithm, based on geometric calibration, is proposed to estimate this initial distance with a simple method, which does not require the calibration of the camera internal parameters. 11 2. Punt de partida: vector de forma i posa 3D per x y=f Z0X Y,(2.1) on f´es la dist`ancia focal i Z0´es la dist`ancia mitjana de l’objectiu a la c`amera (´es a dir, el pla RCt´e l’equaci´o Z=Z0). Quan la variaci´o de profunditat de l’objectiu ´es petita, comparada amb Z0, i el punt principal ´es a prop del centroide de la projecci´o de l’objectiu, llavors el model de c`amera de perspectiva d`ebil d´ona una aproximaci´o de la projecci´o perspectiva [67]. Suposem que l’objectiu est`a imm`obil a l’escena i que la c`amera es trasllada segons Ti gira segons Ral voltant de l’objectiu, i possiblement fa un zoom,1cosa que d´ona una segona c`amera de perspectiva d`ebil ψ′. El nou sistema de coordenades af´ı associat amb la segona c`amera est`a definit per les files de Ri el nou origen a −R⊤T, de manera que ψ′respon a l’expressi´o x′ y′=f′ Z′ 0X′ Y′,(2.2) on [X, Y, Z]⊤=R[X′, Y ′, Z′]⊤+T,f′´es la nova dist`ancia focal, i Z′ 0´es la dist`ancia mitjana entre l’objectiu i la segona c`amera. Les dues vistes de l’escena coplan`aria es poden explicar per l’afinitat donada per [99] x′ y′=Mx y+t,(2.3) on M=f′ f Z0 Z0+TzR11 R21 R21 R22 ,(2.4) t=f′ Z0+TzTx Ty+u−u′ v−v′,(2.5) on Rij s´on elements de la matriu de rotaci´o 3D R,Tis´on els elements del vector de translaci´o 3D T,Z0´es la dist`ancia inicial de la c`amera a l’objecte, f´es la dist`ancia focal de la c`amera a la imatge inicial, f′´es la dist`ancia focal en la segona imatge, (u0, v0) ´es el punt principal en la imatge inicial i (u′, v′) ´es la seva posici´o en la segona imatge. Cal fer notar que quan es canvia la dist`ancia focal la posici´o del punt principal tamb´e canvia [83], i aix`o queda clarament expressat a l’equaci´o. Una de les t`ecniques m´es 1L’efecte m´es evident d’una c`amera que fa zoom ´es que la dist`ancia focal i el punt principal canvien [84]. 18 2.2 Antecedents (a) (b) (c) Figura 2.2: Imatges reals amb un contorn actiu inicialitzat. comunes quan els canvis en la posici´o del punt principal s´on petits2´es la de considerarne la mitjana [87] calculada amb posicions diferents del zoom. ´ Es f`acil veure que quan la dist`ancia focal no canvia, per exemple quan es disposa d’una c`amera amb lents fixes com les utilitzades en les seccions 2.3.1 i2.3.2, les equacions (2.4) i (2.5) deriven a les presentades a [17,97]. 2.2.2 L’afinitat que relaciona dues vistes Un contorn actiu ´es una corba que es defineix al pla de la imatge i que s’ajusta a la projecci´o del contorn d’un objecte que es fa servir de caracter´ıstica rellevant a la imatge (figura 2.2). Quan la c`amera es mou, la projecci´o del contorn en la imatge canvia, i el contorn actiu es deforma per ajustar-se a la nova projecci´o. Aquesta deformaci´o es pot codificar amb un vector de forma, tal com s’explicar`a m´es endavant. El contorn es representa com una Spline,3tal com ´es fa comunament en gr`afics per computador [55], d(s) = (dx(s), dy(s))⊤, on ambdues dx(s) i dy(s) s´on corbes B-Spline. Es poden escriure en funci´o dels seus punts de control Q, d(s) = dx(s) dy(s)=B(s)Qx B(s)Qy=B(s)0⊤ 0⊤B(s)Qx Qy=U(s)Q,(2.6) 2Aix`o dep`en de la fabricaci´o de les lents. 3Funci´o polin`omica a trossos que interpola una s`erie de nodes, de manera que cada tros ´es un polinomi de grau ni en cada node els dos polinomis concurrents tenen totes les seves derivades iguals fins a l’ordre n-1. 19 2. Punt de partida: vector de forma i posa 3D on QxiQys´on els vectors columna de les components xiydels punts de control, 0 ´es un vector columna de zeros, i U(s) = I⊗B(s) ´es el producte de Kronecker entre la matriu identitat Ii el vector fila B(s) de la funci´o de base de la B-Spline [17,55]. Quan el contorn s’observa des de dos punts de vista diferents, l’equaci´o (2.3) es pot generalitzar per descriure’n la relaci´o com d′(s) = Md(s) + t,(2.7) on d′(s) i d(s) s´on el contorn en les dues vistes. Combinant l’expressi´o (2.6) amb l’equaci´o (2.7), s’obt´e d′(s) = MU(s)Q+t.(2.8) Ara, definint 1com un vector columna d’uns, es pot observar que B(s)1= 1 per la propietat de l’envolvent convexa de les corbes B-Spline, i altre cop usant l’equaci´o (2.6), la difer`encia entre d′(s) i d(s) es pot escriure com d′(s)−d(s) = txU(s)1 0+tyU(s)0 1+ (M11 −1)U(s)Qx 0 +M12U(s)Qy 0+M21U(s)0 Qx+(M22 −1)U(s)0 Qy.(2.9) D’altra banda, la difer`encia entre d′(s) i d(s) ´es, a partir de l’equaci´o (2.6), d′(s)−d(s)=U(s)(Q′−Q).(2.10) Per tant, comparant aquest resultat amb l’expressi´o (2.9), es pot concloure que la difer`encia en termes de punts de control Q′−Qes pot escriure com la combinaci´o lineal de sis vectors. Fent servir notaci´o matricial, es pot escriure Q′−Q=WS ,(2.11) on W=1 0,0 1,Qx 0,0 Qy,0 Qx,Qy 0 (2.12) ´es la matriu de forma iS´es un vector amb els sis par`ametres de la combinaci´o lineal, el vector de forma S= (tx, ty, M11 −1, M22 −1, M21, M12)⊤,(2.13) 20 2.2 Antecedents Figura 2.3: Representaci´o gr`afica del significat de cada grau de llibertat del vector de forma indu¨ıt pel moviment de la c`amera. que codifica la relaci´o entre dues vistes afins diferents del contorn planar. La figura 2.3 (reprodu¨ıda de [97]) mostra gr`aficament l’efecte de cada par`ametre: dues translacions i quatre escalats. Un cop s’ha obtingut la representaci´o compacta en termes de punts de control, es fa servir un filtre de Kalman per fer el seguiment del contorn durant tota la seq¨u`encia d’imatges [17] i s’obt´e un nou vector de forma per a cada nova imatge. A tall d’exemple, s’ha dut a terme un petit experiment per tal de veure quina forma tenen els diferents vectors de forma que codifiquen diferents moviments de la c`amera. A la figura 2.4 es pot veure el vector de forma corresponent a un despla¸cament del robot cap a un objectiu mentre es pertorba lleugerament la direcci´o. A la figura 2.4(a) es pot observar com la pertorbaci´o de la direcci´o que correspon a translacions TxiTydel robot es codifica en les dues primeres components del vector de forma. La translaci´o Tz, que correspon al moviment d’aproximaci´o que fa el robot cap a l’objectiu, queda codificada en la part vectorial del vector de forma (figura 2.4(b)) i no correspon a una 21 2. Punt de partida: vector de forma i posa 3D 0 20 40 60 80 100 120 140 160 180 200 −0.13 −0.11 −0.09 −0.07 −0.05 −0.03 −0.01 0.01 0.03 tx ty (a) 0 20 40 60 80 100 120 140 160 180 200 −0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 M11 −1 M22 −1 M21 M12 (b) Figura 2.4: Representaci´o dels vectors de forma extrets en una seq¨u`encia real d’un moviment d’un robot. sola component, sin´o a les components M11 iM22 a la vegada. Observant de nou la figura 2.3 es pot veure que aquestes components corresponen a l’escalat horitzontal i vertical. Sembla l`ogic que un moviment d’aproximaci´o, que fa cr´eixer la mida de la projecci´o de l’objecte en la imatge, correspongui a increments iguals en les components que codifiquen l’escalat. Aquests vectors de forma corresponen a un dels experiments que es mostraran m´es endavant (secci´o 2.3.1). 2.2.3 Moviment 3D a partir de l’afinitat Seguidament es presenta com es pot obtenir la rotaci´o i la translaci´o 3D codificades per l’afinitat definida per M= [Mi,j] i t= (tx, ty) [99]. Si es representa la matriu de rotaci´o amb angles d’Euler ZXZ, R=Rz(φ)Rx(θ)Rz(ψ),(2.14) l’equaci´o (2.4) es pot reescriure com M=f′ f Z0 Z0+Tz Rz|2(φ)Rx|2(θ)Rz|2(ψ) = =f′ f Z0 Z0+Tz Rz|2(φ)1 0 0cosθRz|2(ψ) on R|2denota la submatriu 2 ×2 de R. Llavors, MMT=Rz|2(φ)L0 0Lcos2θRz|2−1(φ) (2.15) 22 2.2 Antecedents on L=f′ f Z0 Z0+Tz2 . Aquesta darrera equaci´o mostra que θes pot calcular a partir dels vectors propis de la matriu MMT,4que s’anomenaran (λ1,λ2): cosθ =rλ2 λ1 ,(2.16) on λ1´es el valor propi m´es gran. L’angle φes pot deduir dels vectors propis de MMT; el vector propi v1que correspon al valor propi m´es gran correspon a la primera columna de Rz|2(φ): v1=cosφ sinφ.(2.17) A¨ıllant Rz|2(ψ) de l’equaci´o (2.15), Rz|2(ψ) = f′ f1 + Tz Z01 0 01 cosθ Rz|2(−φ)M,(2.18) i observant, a l’equaci´o (2.15), que f f′1 + Tz Z0=1 √λ1 , es pot trobar, primer, sinψ i, despr´es, ψ. Un cop trobats els angles θ,φiψes pot reconstruir la matriu de rotaci´o Raplicant l’equaci´o (2.14). La translaci´o escalada5en la direcci´o Zes pot calcular com Tz Z0 =f′ f 1 √λ1−1.(2.19) La resta de components de la translaci´o 3D es poden calcular a partir de tfent servir l’equaci´o (2.5): Tx Z0 =tx−(u′−u) f√λ1 ,(2.20) Ty Z0 =ty−(v′−v) f√λ1 .(2.21) 4Es pot aconseguir una derivaci´o semblant si s’expressa la rotaci´o amb angles d’Euler ZYZ, per`o desafortunadament no es pot seguir el mateix gui´o amb altres expressions de la rotaci´o, com per exemple XYZ. 5Com ´es habitual en un sistema monocular, si no es disposa d’informaci´o addicional la translaci´o nom´es es pot recuperar fins a un factor d’escala. M´es endavant, al cap´ıtol 6, es mostra un algorisme per mesurar la dist`ancia inicial de la c`amera a l’objecte i eliminar aquest factor d’escala. 23 2. Punt de partida: vector de forma i posa 3D Les equacions presentades permeten calcular una estimaci´o del moviment 3D de la c`amera a partir de l’afinitat que el parametritza, fins i tot quan la c`amera varia els seus par`ametres interns. Aquestes mateixes expressions es poden derivar quan el sistema de coordenades est`a centrat en la c`amera [97]. En aquest cas, les expressions per trobar les rotacions no varien i les translacions es poden calcular amb: Tx Z0 =tx−(u′−u) f√λ1−R13 , Ty Z0 =ty−(v′−v) f√λ1−R23 , Tz Z0 =f′ f 1 √λ1−R33 . Es pot veure f`acilment que, quan la c`amera no mou el zoom, i per tant la seva dist`ancia focal no varia, llavors f′=f. En aquest cas, el punt principal tampoc varia, i si es considera u′=uiv′=vs’arriba a les expressions ja conegudes [97] per calcular el moviment per a una c`amera passiva. 2.2.4 Detalls de la implementaci´o L’objectiu de l’algorisme de seguiment ´es mantenir la refer`encia d’un contorn objectiu al llarg d’una seq¨u`encia d’imatges i estimar el vector de forma que codifica la deformaci´o del contorn. La implementaci´o de l’algorisme s’ha fet amb un filtre de Kalman. A causa de la seva representaci´o com a B-Spline, el contorn es divideix naturalment en seccions, cadascuna entre dos nodes consecutius. Per al seguiment, es defineixen alguns punts d’inter`es de manera equidistant al llarg de cada secci´o de contorn. Passant a trav´es de cada punt i normal al contorn, es defineix un segment de recta. La recerca del contorn es fa nom´es per als p´ıxels sota aquests segments normals, i el resultat ´es el pas de mesura de l’algorisme del filtre de Kalman. Aix`o provoca que el sistema sigui molt r`apid, ja que el processament d’imatge ´es local, cosa que evita l’´us d’algorismes costosos de segmentaci´o. Una vegada que els elements de la frontera estan situats al llarg de tots els segments de recerca, el filtre Kalman calcula el vector de forma que millor explica la deformaci´o que s’ha mesurat, que ´es sempre una deformaci´o af´ı del contorn inicial. En la implementaci´o que s’ha fet, la llargada dels segments de cerca est`a determinada per la covari`ancia estimada en la iteraci´o anterior del filtre Kalman. Aix`o es fa 24 2.3 Dues experi`encies pr`actiques projectant la matriu de covari`ancies a la recta normal al contorn en el punt donat. Si el seguiment troba bones transformacions afins que expliquen canvis en la imatge, les disminucions de la covari`ancia fan que els segments de cerca encongeixin. D’una banda, aix`o ´es una bona estrat`egia de mesura, ja que quan es t´e confian¸ca que el seguiment es fa correctament les caracter´ıstiques del contorn es busquen m´es localment i el soroll en la imatge afecta menys al sistema. Per`o, d’altra banda, aquesta soluci´o no ´es la millor per seguir canvis grans en la projecci´o de la imatge, com per exemple el que es t´e despr´es d’un moviment r`apid del robot. Un cop estimat el vector de forma que millor aproxima la deformaci´o del contorn actiu, la posa ´es calcula amb l’algorisme 2.1. A efectes pr`actics, aquest algorisme serveix tant per al cas calibrat com per al cas no calibrat. Quan no es disposa de la dist`ancia focal es poden utilitzar les posicions del controlador del zoom (com es veur`a al cap´ıtol 7) per obtenir una aproximaci´o, i si no es coneix la dist`ancia inicial entre l’objecte i la c`amera cal tenir en compte que els valors de les translacions estan escalats per Z0. 2.3 Dues experi`encies pr`actiques 2.3.1 Avaluaci´o de l’error en el moviment estimat Seguidament es presenta un experiment per determinar la viabilitat de l’algorisme de seguiment de contorns en un robot real i un entorn real. Es vol avaluar, a grans trets, si sembla possible que l’algorisme proposat tingui utilitat per a la navegaci´o de robots. Per tal de calcular el moviment prec´ıs del robot es fa servir un goni`ometre l`aser i es compara amb l’estimaci´o del moviment produ¨ıda per l’algorisme presentat anteriorment (algorisme 2.1). Per obtenir informaci´o m`etrica cal con`eixer els par`ametres de calibratge fi estimar la dist`ancia inicial Z0entre c`amera i objectiu. Reducci´o de la matriu de forma Quan el moviment que cal parametritzar est`a restringit possiblement no calen els sis graus de llibertat de la matriu de forma definida a l’equaci´o (2.12). En l’experiment que es presenta a continuaci´o es fa servir un robot planar amb tres graus de llibertat. En aquest cas, l’espai de moviment es pot parametritzar amb dues 25 2. Punt de partida: vector de forma i posa 3D Entrada :S,Z0,fi opcionalment f′,u,u′,v,v′ Sortida : posa 3D = {Tx, Ty, Tz, φ, θ, ψ} si no hi ha par`ametres opcionals aleshores1 es considera una c`amera sense zoom, de manera que s’inicialitza u=u′=v=v′= 0 f′=f fi Recompondre Ma partir de la part vectorial de Scom2 M=S3+ 1 S6 S5S4+ 1 Trobar els vectors propis λ1iλ2i el valor propi v1a partir de la descomposici´o3 en valors singulars de MMT La rotaci´o θes troba a partir dels valors propis:4 θ=acos(qλ2 λ1) La rotaci´o φes calcula a partir de les components del vector propi v1:5 φ=atan2(v12, v11) Per calcular ψprimer cal recompondre les matrius de rotaci´o6 Rpsi =1 λ1Rz|2(−φ)∗1 0 0 1/cos(θ)]∗M iψes calcula amb: ψ=atan2(Rpsi21, Rpsi11) Les translacions es calculen aplicant7 Tx=S1−(u−u′) f√λ1Z0 Ty=S2−(v−v′) f√λ1Z0 Tz=Z0f′ f√λ1−Z0 Algorisme 2.1 : Algorisme per computar la posa a partir del vector de forma. 26 2.3 Dues experi`encies pr`actiques (a) (b) Figura 2.5: Portapalets robotitzat Still EGV-10 emprat en l’experiment real en un magatzem. Un enregistrador recollia informaci´o d’odometria, posicionament l`aser i imatges. (b) Pl`anol detallat de la zona del magatzem on es va dur a terme l’experiment. (a) imatgeinicial (b) imatgemig (c) imatgefinal Figura 2.6: Imatges de l’experiment durant una translaci´o llarga del robot. El contorn actiu es fixa en un panell d’informaci´o que s’utilitza d’objectiu per estimar el moviment de la c`amera. translacions (Tx,Tz) i una rotaci´o (Ry). ` Obviament, la resta de moviments no s´on possibles. Si s’apliquen aquestes restriccions a les equacions (2.4 i2.5) de la deformaci´o 27 2. Punt de partida: vector de forma i posa 3D Seguint el mateix raonament, les components de la informaci´o inercial en forma de vector de forma tamb´e es poden reescalar. Per al primer component es t´e t1max =Z0vθmax +vxmax,(2.34) i l’expressi´o t1=|t1|t1max −t1min t1max +t1min =|t1|ft1+t1min (2.35) La informaci´o inercial es pot afegir a l’algorisme de seguiment reescalant la matriu de covari`ancia amb una matriu que representa la informaci´o inercial de la manera seg¨uent E=qNTHVPVTHTN(2.36) on V´es la matriu escalada de les mesures del sensor inercial definida com V=         t1.. 0 t2 . M11 −1. . M22 −1. M12 0.. M21                 ft1 ft2 fM11 fM22 fM12 fM21         +         t1min t2min M11min M22min M12min M21min         .(2.37) En la propera secci´o d’experiments, els valors m`axims i m´ınims s’han fixat a 1 i 2 respectivament. Experiments combinant visi´o i informaci´o inercial En aquests experiments s’utilitza un robot m`obil RobuCab de Robosoft. Com es pot veure a la figura 2.9, ´es un vehicle m`obil relativament gran amb capacitat per a quatre persones. Es pot utilitzar en dos modes: en mode de conducci´o cotxe (roten les rodes de nom´es un eix) i en mode bidireccional (les quatre rodes giren). Per simplificar el sistema de control, es fa servir el mode de conducci´o de cotxe, per`o es poden obtenir millors resultats, en termes d’angle de gir menor, amb el mode de conducci´o bidireccional, ja que s’incrementa l’angle m`axim de rotaci´o que el vehicle ´es capa¸c de seguir. Per a aquest experiment es munta un sistema de visi´o monocular DragonFly de Point Grey, i les imatges es tracten amb el sistema de seguiment descrit. Per mesurar les rotacions sobre l’eix Yes fa servir un sensor inercial Gyrostar, de Murata. Per mesurar les acceleracions lineals als eixos XiZs’utilitza un doble 34 2.3 Dues experi`encies pr`actiques Figura 2.9: Plataforma m`obil Robucab usada en l’experiment. acceler`ometre ADXL d’Analog Devices. Tots aquests sensors estan connectats a una targeta dissenyada especialment per a aquest experiment que compta amb un processador AVR utilitzat per fer conversions A/D, descodificaci´o de PWM i integraci´o dels senyals d’acceleraci´o. T´e tamb´e un term`ometre per a la correcci´o t`ermica de les dades. Aquest sensor ’intel·ligent’ que s’ha fabricat proporciona l’acceleraci´o i tamb´e en fa la integraci´o per obtenir la velocitat mitjana i la posici´o. El biaix, t´ıpic en aquesta classe de c`alculs d’integraci´o, es restaura peri`odicament amb la informaci´o obtinguda per la fusi´o dels altres sensors. Aquesta targeta comparteix mem`oria amb una targeta basada en un processador PowerPC MPC555, que est`a connectada a trav´es d’un bus CAN al PC de processament de control i visi´o. Tot el sistema s’executa en un nucli de Linux en temps real sobre un ordinador industrial Pentium 233 MHz. S’ha utilitzat nova aproximaci´o a la programaci´o distribu¨ıda [111] per programar el control del robot iper a la intercomunicaci´o del processament de control i de visi´o, aprofitant el sistema operatiu de temps real. Podria semblar que ja que el robot ´es planar es pot fer servir la forma redu¨ıda de l’espai de forma (2.24). Per`o en aquest cas no ´es possible, ja que es tracta principalment d’un robot d’exteriors i per tant no es pot assumir que es mou en un pla. A m´es, disposa de suspensions que fan que, depenent de la c`arrega, la seva distribuci´o i el seu moviment, hi hagi moviment en gaireb´e els sis graus de llibertat. Per tant, cal fer servir la matriu que codifica tot l’espai de forma (2.12). En aquest experiment el robot s’ha programat perqu`e pugui conduir aut`onomament 35 2. Punt de partida: vector de forma i posa 3D 1 3 7 9 11 13 15 17 195 22.0 22.4 23.6 25.6 24.8 22.8 23.2 24.0 24.4 25.2 (a) 22.42 22.38 22.34 22.30 22.26 22.22 22.18 22.14 22.10 22.061 3 5 7 9 11 13 15 17 19 (b) Figura 2.10: Traces de la seq¨u`encia de matrius de covari`ancia resultat de seguir un contorn (a) sense informaci´o inertial i (b) utilitzant la informaci´o inercial. En el segon cas el contorn no es perd i el seguiment pot continuar. seguint un cam´ı filoguiat. D’aquesta manera, la traject`oria es pot repetir f`acilment i es poden fer tots els experiments necessaris en condicions molt similars. El cam´ı seguit en l’experiment que es mostra consta d’un segment de recta, una corba i un altre segment de recta. Primer s’utilitza l’algorisme sense informaci´o inercial. En el primer segment recte el contorn se segueix b´e, per`o quan comen¸ca el gir i la projecci´o del contorn es mou m´es r`apidament al pla de la imatge l’algorisme de seguiment perd l’objectiu. Es fa servir la tra¸ca de la matriu de covari`ancia com a mesura. Com es pot observar en els resultats de la figura 2.10(a), en aquest experiment la tra¸ca de la matriu de covari`ancia augmenta cont´ınuament. Segon, s’utilitza l’algorisme que inclou la informaci´o inertial en el seguiment. En aquest experiment, el seguiment no perd l’objectiu i acaba la seq¨u`encia donant els valors de posa correctament. Com es pot veure en la representaci´o de la tra¸ca de la covari`ancia en la figura 2.10(b), la covari`ancia augmenta al comen¸cament del gir per`o disminueix de pressa, cosa que mostra que l’algorisme de seguiment ha mantingut l’objectiu malgrat la seva translaci´o r`apida d’un costat a l’altre de la imatge. 2.4 Conclusions Aquest cap´ıtol s’ha iniciat presentant els resultats d’uns treballs previs [17,97,99] en qu`e el model de c`amera de perspectiva d`ebil s’ha emprat per definir un espai de forma 36 2.4 Conclusions af´ı amb qu`e es parametritza el moviment realitzat per una c`amera, i posteriorment s’ha mostrat com es pot estimar el moviment 3D a partir d’aquest espai de forma. Fins al moment, aquest algorisme mai no havia estat comparat amb altres algorismes de posicionament, i l’error i la precisi´o no havien estat mesurats abans. La primera estimaci´o de l’error que es comet en la recuperaci´o del moviment s’ha obtingut amb un experiment amb un robot transpaletitzador que s’ha fet en un entorn real, on tamb´e s’ha explorat la possibilitat de combinar la flexibilitat del sistema de visi´o amb la precisi´o d’un sistema de posicionament l`aser. S’ha pogut comprovar num`ericament que l’error m´es gran es comet en la translaci´o Tzi que el seu valor no ´es mai superior al 3%, i s’ha vist que l’algorisme de visi´o presentat pot ser una bona alternativa a la navegaci´o l`aser en fragments de la navegaci´o on no calgui un grau de precisi´o molt elevat. Finalment, s’ha proposat un nou algorisme que aprofita la informaci´o d’un sensor inercial per millorar el seguiment. Ha calgut definir les transformacions inverses d’espai 3D a espai de forma per poder expressar la informaci´o inercial a espai de forma, i s’ha proposat un algorisme per escalar convenientment la zona de cerca. S’ha validat l’algorisme amb un experiment real amb un robot RobuCar de transport de persones. En els treballs realitzats s’ha observat el potencial de l’algorisme d’estimaci´o del moviment mitjan¸cant contorns actius. S’ha constatat que cal fer un estudi m´es en profunditat de la precisi´o que es pot obtenir, i de quins factors influeixen en aquesta precisi´o: dist`ancia inicial, efectes perspectius, soroll en l’adquisici´o... 37 Cap´ıtol 3 Recuperaci´o de la direcci´o epipolar ≪Aix`o, en teoria, tamb´e ser`a veritat; per`o a la pr`actica ´es fals≫. Amb aquest sofisma s’admeten les raons i tanmateix es neguen les conseq¨u`encies. A. Schopenhauer, L’art de tenir sempre la ra´o, (Estratagema 33), Emp´uries, 2005. ≪”That’s all very well in theory, but it won’t do in practice.≫In this sophism you admit the premisses but deny the conclusion. A. Schopenhauer, The Art of Controversy, (stratagem 33), (Translated by T. Bailey Saunders, at Gutenberg project) Extracte Per aprofundir en el coneixement de l’algorisme presentat en el cap´ıtol anterior el primer pas ´es estudiar la geometria que relaciona dues vistes d’un objecte planar en el context de condicions de visualitzaci´o afins. Utilitzant resultats de geometria projectiva, es demostra que la direcci´o epipolar af´ı es pot recobrar a condici´o que el moviment de la c`amera sigui lliure de ciclorrotaci´o (moviment que correspon a la rotaci´o sobre l’eix de projecci´o). Aquest resultat es demostra anal´ıticament, i se sotmet a experimentaci´o. L’experiment consta d’un robot Sta¨ubli que sost´e un objecte planar davant d’una c`amera, i s’utilitza per obtenir seq¨u`encies d’imatges amb moviments ben coneguts, que serveixen per avaluar el rendiment del m`etode i trobar les seves limitacions en la pr`actica. L’algorisme es beneficia dels avantatges 3. Recuperaci´o de la direcci´o epipolar d’utilitzar un contorn actiu per fer el seguiment, que permet fer una aplicaci´o robusta i un processament simple (resolent una equaci´o de segon ordre senzilla), i ´es v`alid fins i tot per a escenes pobrament texturades. La direcci´o epipolar ha resultat ser un bon indicador de la qualitat de l’afinitat que es calcula. Els experiments realitzats han servit per avaluar quines situacions s´on m´es o menys favorables. 3.1 Introducci´o En la darrera d`ecada s’ha dedicat un treball extens a estimar la geometria epipolar que relaciona dues vistes de la mateixa escena. Els m`etodes proposats solucionen el problema de manera diferent depenent del seg¨uent: a) el model de c`ameres que assumeixen, b) els tipus d’escenes a qu`e s’apliquen, i c) com es mesura el moviment visual en el pla de la imatge. El model de c`amera relaciona el moviment mesurat en el pla de la imatge amb el moviment 3D de la c`amera. Habitualment s’han utilitzat diferents models de c`amera depenent de les condicions de visualitzaci´o per emular el proc´es de creaci´o de la imatge [15,101]. S’ha demostrat que el model de perspectiva completa -en versi´o calibrada (c`amera perspectiva) i no calibrada (c`amera projectiva)- ´es massa general quan els efectes de perspectiva disminueixen i no s´on apreciables. En condicions de visualitzaci´o de perspectiva d`ebil (camp de visi´o petit o variaci´o de la profunditat en l’escena petita comparada amb la seva dist`ancia mitjana a la c`amera), els models de c`amera simplificats, com l’ortogr`afic, l’ortogr`afic escalat, o la seva generalitzaci´o per al cas no calibrat, el model de c`amera af´ı, proporcionen una aproximaci´o avantatjosa a la c`amera de perspectiva completa, ja que eviten computar par`ametres que les condicions de visualitzaci´o fan que estiguin mal condicionats. L’estimaci´o de la geometria epipolar en el cas af´ı ha rebut molta atenci´o en la literatura [81,125]. Tanmateix, la majoria dels m`etodes coneguts assumeixen el seg¨uent: 1. l’escena cont´e informaci´o de profunditat, de manera que els algorismes fallen quan la configuraci´o de l’escena s’aproxima a una estructura planar. Per exemple, els experiments amb l’algorisme est`andard d’or1(secci´o 3.3) mostren que per 1Per definici´o, un est`andard d’or ´es el m`etode, procediment o mesura que s’accepta `ampliament i que s’usa com la millor comparaci´o per avaluar m`etodes, procediments o mesures nous. 40 3.1 Introducci´o obtenir resultats acceptables el relleu (difer`encia de profunditats) de l’objecte ha de ser del mateix ordre de magnitud que la llargada/amplada; i 2. l’escena est`a suficientment texturada per permetre l’estimaci´o visual del moviment a partir de correspond`encies de punts. Aqu´ı s’explora un enfocament alternatiu aplicable quan aquestes dues suposicions no s´on aplicables. Els intents previs per superar la suposici´o 1), i per tant calcular la geometria epipolar entre dues imatges a partir d’un pla dominant, han utilitzat una c`amera de perspectiva completa. ´ Es ben sabut que dues vistes d’un pla es relacionen per una colineaci´o segons el model de perspectiva completa [62]. Uns quants autors han utilitzat aquest fet per proposar algorismes per al calibratge de c`ameres [132], autocalibratge [44,93] i extracci´o d’estructura i moviment des de vistes no calibrades de punts sobre plans [14,29] o corbes planars [79]. Tanmateix, quan disminueixen els efectes de perspectiva, la relaci´o entre dues vistes d’una estructura planar es converteix en una afinitat, que invalida els m`etodes basats en colineacions. Que en tinguem coneixement, no hi ha treballs previs que eludeixin la suposici´o 1) en condicions de visualitzaci´o af´ı. Pel que fa a la suposici´o 2), el que es proposa ´es calcular visualment el moviment entre dues vistes utilitzant contorns actius, i aix´ı es poden abordar escenes molt poc texturades. L’afinitat que relaciona dues vistes, que aqu´ı es proposa obtenir seguint un contorn planar, ´es te`oricament equivalent a la que resulta de tres correspond`encies de punts. Tanmateix, com ja s’ha esmentat, l’algorisme que es presenta eludeix la suposici´o 2) i es beneficia d’altres avantatges dels contorns actius, com la seva robustesa a oclusions i soroll, aix´ı com la simplicitat del procediment de seguiment, al mateix temps que evita la correspond`encia de punts. Primer s’explora quina informaci´o de la geometria epipolar af´ı es pot inferir a partir de la deformaci´o af´ı de la projecci´o d’un contorn r´ıgid i planar en dues vistes de perspectiva d`ebil, fent servir l’an`alisi estratificada del moviment per a condicions de visualitzaci´o af´ı introdu¨ıda per Koenderink i Van Doorn [81] i revisitada per Shapiro et al. [125]. Aix`o posa la base per obtenir els par`ametres de moviment en una segona fase. Es mostra que, amb un moviment 3D lliure de ciclorrotaci´o, la direcci´o epipolar es pot recuperar de la relaci´o de les dues vistes afins del contorn. Es realitzen una 41 3. Recuperaci´o de la direcci´o epipolar s`erie d’experiments per provar la sensibilitat del m`etode davant de diferents condicions. Aquests experiments posen de manifest que la direcci´o epipolar, a part de l’inter`es que t´e ja que relaciona dues vistes, serveix per tenir una mesura de la qualitat de l’afinitat que es computa. D’aquesta manera, amb nom´es un nombre es pot avaluar la qualitat de l’afinitat calculada ( per exemple, davant de situacions adverses fora de condicions de perspectiva d`ebil, amb soroll...), cosa que fins ara era molt dif´ıcil d’acomplir, ja que s’havia de manegar tota la posa 6D, introdu¨ıda al cap´ıtol 2. El cap´ıtol s’organitza de la manera seg¨uent. La secci´o 3.2 cont´e l’estudi anal´ıtic de dues vistes de perspectiva d`ebil i proporciona la base per a la recuperaci´o de la direcci´o epipolar. La secci´o 3.3 es dedica a l’experimentaci´o, utilitzant seq¨u`encies d’imatges tant sint`etiques com reals. Es mostren m´ultiples experiments, que inclouen la relaxaci´o de les condicions de visualitzaci´o de perspectiva d`ebil, i es mostra que la direcci´o epipolar serveix tamb´e per mesurar la qualitat de l’afinitat que codifica la deformaci´o del contorn. Finalment, a la secci´o 3.4 es resumeix la contribuci´o feta. 3.2 Estudi anal´ıtic de dues vistes amb perspectiva d`ebil 3.2.1 El model de c`amera El model de c`amera que es fa servir ´es el de perspectiva d`ebil, introdu¨ıt a la secci´o 2.2.1. Seguint el mateix tipus de raonament, si es considera l’equaci´o aX +bY +c=Zd’un pla global S, llavors les dues vistes de l’escena coplan`aria es poden explicar per l’afinitat donada per (2.3) x′ y′=Mx y+t, amb M=sf′ fR11 +aR13 R12 +bR13 R21 +aR23 R22 +bR23,(3.1) t=−f′ Z′R11 R12 R13 R21 R22 R23  Tx Ty Tz +cR13 R23,(3.2) on s=Z0/Z′´es el factor d’escala que explica la variaci´o de profunditat (s > 1 si la segona c`amera s’acosta a l’objecte, i s < 1 si s’allunya), i Ri,j s´on els elements de la matriu de rotaci´o R. 42 3.2 Estudi anal´ıtic de dues vistes amb perspectiva d`ebil Una direcci´o v= [x, y]⊤de la primera imatge Rcorrespon, per l’afinitat citada, amb la direcci´o Mv de la segona imatge R′. Gr`acies al fet que els sistemes de refer`encia afins escollits en les dues c`ameres coincideixen pel despla¸cament, podem superposar les dues imatges i t´e sentit considerar les direccions invariants per M. 3.2.2 Recuperaci´o de la direcci´o epipolar Considerem un sistema de coordenades ortonormal associat a la primera imatge (per exemple, coordenades de p´ıxel normalitzades, quan es coneixen la relaci´o d’aspecte i el biaix de la c`amera). La matriu de rotaci´o sobre l’eix unitari [cos α, sin α, 0]⊤i l’angle ρ t´e la forma R=  (1 −cos ρ) cos2α+ cos ρcos αsin α(1 −cos ρ) sin αsin ρ cos αsin α(1 −cos ρ) (1 −cos ρ) sin2α+ cos ρ−cos αsin ρ −sin αsin ρcos αsin ρcos ρ .(3.3) Per aix`o, la matriu M´es M=sf′ f       (1 −cos ρ) cos2α + cos ρ+asin αsin ρ cos αsin α(1 −cos ρ) +bsin αsin ρ cos αsin α(1 −cos ρ) −acos αsin ρ (1 −cos ρ) sin2α + cos ρ−bcos αsin ρ       ,(3.4) on a= [cos α, sin α]⊤´es la direcci´o de l’eix de rotaci´o i el vector ortogonal e= [−sin α, cos α]⊤=a⊥´es la direcci´o epipolar. Un c`alcul directe mostra que Me =sf′ f(cos ρ+ sin ρ(asin α−bcos α))e,(3.5) la qual cosa d´ona una prova anal´ıtica del resultat seg¨uent: Teorema 3.1. Si el moviment r´ıgid entre dues c`ameres de perspectiva d`ebil se suposa que ´es lliure de ciclorrotaci´o, llavors la direcci´o epipolar epot ser recobrada com un dels dos vectors propis de la part vectorial Mde l’afinitat que explica dues vistes d’una escena planar. Com a conseq¨u`encia, la direcci´o a=e⊥de l’eix de rotaci´o tamb´e es pot recuperar. La figura 3.1 il·lustra el resultat citat. Es mostren dues vistes RiR′d’un objecte planar en forma de “H”, relacionades per una rotaci´o sobre un eix paral·lel al pla de la imatge (per exemple, lliure de ciclorrotaci´o). Per poder-ho il·lustrar m´es f`acilment, 43 3. Recuperaci´o de la direcci´o epipolar 5 10 15 20 25 30 35 40 45 50 −0.08 −0.06 −0.04 −0.02 0 0.02 0.04 0.06 0.08 7.5 15 22.5 30 37.5 45 52.5 60 67.5 75 82.5 rotació (◦) error (◦) (a) Forma quadrada 5 10 15 20 25 30 35 40 45 50 −0.4 −0.3 −0.2 −0.1 0 0.1 7.5 15 22.5 30 37.5 45 52.5 60 67.5 75 82.5 rotació (◦) error (◦) (b) Forma de “H” Figura 3.6: Error en la recuperaci´o de la direcci´o epipolar per a inclinacions de l’eix de rotaci´o diferents quan les rotacions a trav´es d’aquest eix van de 5◦a 50◦. Comen¸cant des d’una vista frontoparal·lela del contorn, la difer`encia en profunditat dels punts es relaciona directament amb la quantitat de rotaci´o que la c`amera realitza sobre un eix situat sobre el contorn. Aix´ı, es fa un experiment per analitzar aquest efecte fixant un eix de rotaci´o en l’objecte a diverses inclinacions ( 7.5◦,15◦,...,82.5◦) i llavors girant la c`amera sobre cadascun d’aquests eixos de 5◦a 50◦, amb la mateixa dist`ancia focal i valors de Z0emprats en l’experiment anterior. La figura 3.6 mostra els resultats obtinguts. Congruent amb la figura 3.4 per a la forma quadrada, l’error en l’estimaci´o de la direcci´o epipolar ´es zero per a qualsevol posicionament de la c`amera resultant d’una rotaci´o sobre un eix que t´e una inclinaci´o de 45◦. Per a la forma de “H”, l’error zero ocorre a valors d’inclinaci´o diferents per a quantitats diferents de rotaci´o. Es pot observar que, per a les dues formes, les rotacions m´es grans indueixen uns errors de recuperaci´o m´es petits. Una explicaci´o geom`etrica d’aquest efecte ´es que, comen¸cant des d’una posici´o de l’objecte frontoparal·lela, com m´es gran ´es la quantitat de rotaci´o m´es propera ´es la configuraci´o dels raigs de projecci´o a una projecci´o paral·lela (figura 3.7). Per aix`o, es pot deduir que els efectes de perspectiva que no es poden modelar produeixen errors m´es grans per a quantitats de rotaci´o petites. En resum, en el cas ideal l’error en la recuperaci´o de la direcci´o epipolar a causa de la difer`encia de profunditat entre els punts ´es insignificant. 50 3.3 Experimentaci´o T R1 R2 α0 R0 α1 α2 Figura 3.7: Comen¸cant amb un objecte frontoparal·lel T, es pren una primera vista R0i llavors dues altres vistes R1iR2;R2despr´es d’una quantitat m´es gran de rotaci´o que R1. El m`axim angle αientre els raigs de projecci´o disminueix (i, aix´ı, la projecci´o es torna m´es propera a una projecci´o paral·lela) a mesura que la quantitat de rotaci´o augmenta. Translaci´o lateral: projecci´o del contorn no centrada Usant el model de c`ameres de perspectiva d`ebil se suposa que les dist`ancies dels punts de control del contorn al raig principal s´on petites, una altra vegada en relaci´o amb la dist`ancia Z0des de la c`amera fins a l’objecte. Aquesta condici´o es pot satisfer amb un camp de visi´o redu¨ıt i mantenint la projecci´o de l’objecte projectat centrada en la imatge (suposant que el centre d’imatge estigui a prop del punt principal). Per avaluar els efectes de relaxar la condici´o que l’objecte estigui centrat, se simulen una s`erie de translacions de la c`amera paral·leles al pla de la imatge que s’estenen des de −175 mm fins a 175 mm, de manera que es cobreix la totalitat de l’`area de la imatge simulada. Es mostren els resultats per a diferents orientacions cada 30◦(0◦,30◦,...,150◦) i els casos especials a 45◦i 135◦. Comparat amb les altres condicions pr`eviament avaluades, les translacions de la c`amera que ocasionen despla¸caments grans de l’objecte en la imatge porten a errors m´es grans en el c`alcul de la direcci´o epipolar. Com es pot veure a la figura 3.8, comparant 3.8(a) i3.8(b), els efectes de forma de contorn s´on insignificants respecte de l’error provocat per no tenir centrada la projecci´o de l’objecte en la imatge. A m´es, els errors de recuperaci´o de la direcci´o epipolar s´on m´es significatius per a translacions al llarg 51 3. Recuperaci´o de la direcci´o epipolar 175 140 105 70 35 0 35 70 105 140 175 −6 −4 −2 0 2 4 6 translació (mm) 0 30 45 60 90 120 135 150 error (◦) (a) Forma quadrada 175 140 105 70 35 0 35 70 105 140 175 −6 −4 −2 0 2 4 6 translació (mm) 0 30 45 60 90 120 135 150 error (◦) (b) Forma de “H” Figura 3.8: Error en la recuperaci´o de la direcci´o epipolar per a una rotaci´o fixa de 40◦sobre un eix inclinat 45◦sobre el pla de l’objecte, i amb una dist`ancia inicial de 5 m, quan despr´es de la rotaci´o es fan translacions laterals de la c`amera al llarg de les direccions llistades a la llegenda. 0 40 80 120 160 200 240 280 320 360 0 2 4 6 8 10 12 14 5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 inclinació (◦) error (◦) (a) Forma quadrada 0 40 80 120 160 200 240 280 320 360 0 2 4 6 8 10 12 14 5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 inclinació (◦) error (◦) (b) Forma de “H” Figura 3.9: Efectes d’introduir ciclorrotaci´o al moviment de la c`amera. Cada l´ınia ´es l’error de recuperaci´o despr´es d’una rotaci´o de la c`amera sobre un eix definit sobre l’objecte, i l’orientaci´o de qui varia de 0◦a 360◦en el pla, i de 0.5◦a 5◦fora del pla (augmentant la quantitat de ciclorrotaci´o). de la direcci´o ortogonal a la direcci´o epipolar (45◦) i insignificants al llarg de la direcci´o epipolar. 52 3.3 Experimentaci´o 3.3.4 Efectes de la ciclorrotaci´o La restricci´o que s’imposa en l’algorisme presentat suposa que no hi ha ciclorrotaci´o en el moviment de la c`amera. Com es pot observar f`acilment a la figura 3.1, si es realitza un moviment de la c`amera que cont´e ciclorrotaci´o no es conserva cap direcci´o en la imatge. El que es pret´en ´es quantificar l’error en la recuperaci´o de la direcci´o epipolar mentre la quantitat de ciclorrotaci´o present en el moviment augmenta. La figura 3.9 mostra els errors resultants de repetir el mateix experiment de la secci´o 3.3.2 per`o introduint graus diferents de ciclorrotaci´o. Per a cada experiment, la rotaci´o ´es de 40◦sobre un eix a trav´es del centre de l’objecte, l’orientaci´o del qual varia de 0◦a 360◦, i on la component de ciclorrotaci´o s’est´en de 0.5◦a 5◦. Com era d’esperar, l’error en la direcci´o epipolar augmenta severament respecte a la quantitat de ciclorrotaci´o, i per tant, cal complir la restricci´o imposada a l’algorisme. 3.3.5 Sensibilitat al soroll L’afinitat Mque explica dues vistes s’aproxima a la identitat per a moviments petits, de manera que el c`alcul de la direcci´o epipolar basada en Mhauria de ser molt sensible davant les pertorbacions en les projeccions dels punts de control. Per avaluar aquesta sensibilitat, es duen a terme una s`erie d’experiments considerant rotacions que s’estenen de 5◦a 50◦sobre un eix orientat a −45◦al pla de l’objecte, per al qual l’error de recuperaci´o s’acosta a zero en condicions lliures de soroll (figura 3.6). S’afegeix soroll gaussi`a amb desviaci´o est`andard igual a m´ultiples de 0.25 p´ıxels a ambdues components xiyde les projeccions en la imatge dels punts de control, i es fa una simulaci´o de Monte Carlo amb 10000 mostres. Els resultats es poden veure en la figura 3.10. Per a cada forma, hi ha deu gr`afiques que corresponen als angles de rotaci´o de 5◦a 50◦i, dins de cada gr`afica, es representen, per a cada nivell de soroll de 0.25 a 1.00 p´ıxels, la direcci´o epipolar mitjana amb una l´ınia horitzontal, i la seva desviaci´o est`andard com un segment vertical. Cal notar que, d’acord amb l’efecte il·lustrat en la figura 3.7, les rotacions m´es grans porten a errors de recuperaci´o m´es petits. A m´es, com era d’esperar, les quantitats m´es altes de soroll produeixen una recuperaci´o m´es pobra, encara que es pot observar que per a rotacions m´es grans que 20◦la recuperaci´o ´es bastant bona fins i tot en pres`encia 53 3. Recuperaci´o de la direcci´o epipolar 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 desviació estàndard del soroll direcció epipolar 5◦10◦15◦20◦25◦35◦45◦ 30◦40◦50◦ (a) Forma quadrada 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 0 0.5 1 55 50 45 40 35 desviació estàndard del soroll direcció epipolar 5◦10◦15◦20◦25◦35◦45◦ 30◦40◦50◦ (b) Forma de “H” Figura 3.10: Mitjana aritm`etica (l´ınia orientada horitzontalment) i desviaci´o est`andard (l´ınia vertical) de les direccions epipolars computades en pres`encia de soroll gaussi`a amb desviacions est`andards de 0.25 a 1.00 p´ıxels. Els deu gr`afics mostrats per a cada forma corresponen a rotacions que s’estenen de 5◦a 50◦sobre un eix orientat a−45◦. d’un soroll considerable. Al contrari, per a rotacions m´es petites que 10◦, l’algorisme proposat no ´es fiable en condicions sorolloses. Observeu que els resultats per a la forma de “H” s´on molt millors, especialment per a petites rotacions, que els obtinguts amb el quadrat, a causa del fet que amb un nombre m´es gran de punts de control l’estimaci´o de l’afinitat ´es molt m´es robusta al soroll. 3.3.6 Comparaci´o amb l’algorisme est`andard d’or Fins a aquest punt, s’han analitzat els efectes de diversos factors (referent a la forma, el model de c`amera emprat...) que influeixen en la precisi´o de l’algorisme proposat. Ara, i encara en una escena simulada, es vol fer una comparaci´o amb l’algorisme est`andard d’or (EdO) per computar la geometria epipolar af´ı [62]. Aquest m`etode, al contrari que el nostre algorisme, necessita que les correspond`encies de punts que utilitza no provinguin de punts coplanars per tal de computar amb la m`axima versemblan¸ca possible l’estimaci´o de la matriu fonamental af´ı. En teoria, nom´es amb quatre punts no coplanars ´es suficient per computar la geometria epipolar af´ı amb l’algorisme EdO. En realitat, el seu rendiment dep`en fortament de la quantitat d’informaci´o no coplan`aria proporcionada, tant pel que fa a la gamma de profunditats com al nombre de punts 54 3.3 Experimentaci´o utilitzats. L’objectiu d’aquesta secci´o ´es establir experimentalment la quantitat d’informaci´o de profunditat exigida per l’EdO per proporcionar resultats de recuperaci´o de direcci´o epipolar equivalents a l’algorisme proposat. Primer es dissenya un experiment en el qual s’afegeix una s`erie de dos a dotze punts suplementaris al contorn en forma de “H”, amb la qual cosa es fa variar la seva dist`ancia respecte al pla de contorn. Els par`ametres de la c`amera es fixen a 500 mm de profunditat entre c`amera i objecte, i a una dist`ancia focal de 767 p´ıxels. Com en l’experiment anterior, el moviment de la c`amera s’aconsegueix mitjan¸cant una rotaci´o de 40◦sobre un eix posat a una orientaci´o de 45◦sobre el pla de l’objecte. Els resultats es mostren a la figura 3.11. Es pot veure que, quan la profunditat d’aquests punts augmenta, l’error en el c`alcul de la direcci´o epipolar disminueix. A m´es, s’ha observat que el nombre i la localitzaci´o xy d’aquests punts tenen poc efecte en el resultat del c`alcul de la direcci´o epipolar. El diagrama cont´e la representaci´o dels errors que resulten en el c`alcul de la direcci´o epipolar af´ı amb l’algorisme EdO per a diferents nombres de punts fora del pla, i un llindar de tall on es mostra l’error en la recuperaci´o de la direcci´o epipolar utilitzant l’algorisme proposat en les mateixes condicions experimentals (evidentment, els punts addicionals fora del pla del contorn no s’utilitzen en l’algorisme proposat). Com es mostra en el diagrama, per a les condicions experimentals donades, els resultats de l’algorisme proposat s´on comparables als resultats de l’algorisme EdO quan els punts extres es posen aproximadament a una dist`ancia igual a la mida de l’objecte (120 mm en aquest cas). Cal observar la import`ancia de la paral·laxi en el c`alcul de la matriu fonamental af´ı en l’algorisme EdO. A mesura que els punts de l’objecte s’acosten a una configuraci´o coplanar, el vector de paral·laxi, que determina la direcci´o epipolar, es redueix monot`onicament en llargada. Conseq¨uentment, la precisi´o de la direcci´o de la recta es redueix de la mateixa manera, i la covari`ancia d’una matriu fonamental af´ı aproximada augmenta. Aquesta situaci´o no ocorre en l’algorisme proposat, ja que s’ha ideat precisament per computar la direcci´o epipolar af´ı des de dues vistes d’un objecte pla. El segon experiment avalua la sensibilitat al soroll de les dues t`ecniques per computar la direcci´o epipolar af´ı, i consisteix a repetir el mateix experiment diverses vegades afegint soroll gaussi`a a les projeccions de pol´ıgon de control. L’experiment es realitza amb l’algorisme proposat utilitzant la forma de “H” planar, i per a l’algorisme d’EdO 55 3. Recuperaci´o de la direcci´o epipolar 0 20 40 60 80 100120140160180200 45.5 45 44.5 44 43.5 43 42.5 42 41.5 profunditat (mm) algorisme proposat direcció epipolar (◦) Figura 3.11: Direcci´o epipolar computada amb l’algorisme EdO en el cas que es posen 2, 4... 12 punts fora del pla (una corba per a cada nombre) situats a profunditats creixents damunt el contorn en forma de “H”. Observeu que el factor m´es important no ´es el nombre de punts, sin´o la profunditat a qu`e es posen. soroll (p´ıxels) cas 0.00 0.25 0.50 0.75 1.00 contorn planar “H” µ-44.97 -44.95 -44.96 -45.04 -45.07 amb l’algorisme proposat σ0 0.193 0.492 0.552 0.876 contorn planar “H” i 2 µ-43.76 -43.77 -43.78 -43.74 -43.85 punts 120mm fora del pla (EdO) σ0 0.143 0.245 0.436 0.486 2 capes del contorn µ-44.91 -44.91 -44.89 -44.92 -44.91 “H” a 0mm i 120mm (EdO) σ0 0.068 0.140 0.210 0.324 Valors de profunditat aleatoris µ-44.81 -45.75 -45.03 -44.51 -44.84 per als punts de pol´ıgon de control (EdO) σ0 0.294 0.486 0.712 0.625 Taula 3.1: Recuperaci´o de direcci´o epipolar utilitzant l’algorisme proposat i l’algorisme EdO per a nivells creixents de soroll gaussi`a aplicats al punts en la imatge. La rotaci´o real de la c`amera ´es de 40◦sobre un eix a 45◦centrat en l’objecte. utilitzant: a) el contorn “H” planar i dos punts fora del pla a una dist`ancia de 120 mm, b) 24 punts dividits en dos estrats, formant dues formes de “H” a dist`ancies diferents, i c) a profunditat aleat`oria dels 12 punts que formen la “H”. La taula 3.1 mostra una comparaci´o dels resultats obtinguts per a una desviaci´o est`andard creixent de 0 a 1 p´ıxel en el soroll expressant en coordenades d’imatge. Es pot observar que els resultats m´es coherents s’obtenen amb l’algorisme proposat 56 3.3 Experimentaci´o i amb l’experiment EdO que utilitza dos estrats de punts de control, mentre que l’EdO amb nom´es dos punts fora del pla produeix una estimaci´o esbiaixada. Tanmateix, no s’observen grans difer`encies en la precisi´o en condicions sorolloses. 3.3.7 Experiments amb imatges reals Presentem ara els resultats obtinguts emprant seq¨u`encies d’imatges en una escena controlada. L’objectiu d’aquest treball no ´es a seguir l’objecte, sin´o a computar l’afinitat i utilitzar-la per calcular la direcci´o epipolar que explica les dues vistes. ´ Es per aix`o que es facilita la fase de seguiment fent avan¸car l’objecte simple de la figura 3.12 (´es clar que en situacions reals no ´es usual trobar objectes tan ben definits!). L’objecte es munta en l’element terminal d’un bra¸c manipulador, de manera que se sap exactament el moviment que es realitza, i el treball es focalitza en avaluar la precisi´o de la direcci´o recobrada en situacions diferents. Es pot veure f`acilment que un moviment de l’objecte amb el bra¸c equival a un moviment de la c`amera. L’escenari de l’experiment consta d’un manipulador RX60 St¨aubli que sost´e el dibuix d’un objecte al seu efector final. Aquest objecte ´es una figura planar artificial en forma de “H” que combina cantonades i l´ınies rectes i corbes, que es poden seguir f`acilment amb el nostre algorisme de seguiment de contorns actius. Les imatges s’adquireixen utilitzant una c`amera firewire Sony DWL500 amb una dist`ancia focal calibrada de 767 p´ıxels. La zona de treball del bra¸c est`a molt limitada (comparada amb un robot m`obil, per exemple), i aix`o restringeix el repertori d’experiments en qu`e podem actuar, per`o conv´e pagar aquest preu a canvi de la precisi´o que s’obt´e en el moviment. La dist`ancia inicial des de la c`amera fins a l’objecte s’ha establert en 500 mm. Aix`o correspon al cas extrem que es descriu a la secci´o 3.3.3, figura 3.5 i, per aix`o, s’est`a provant l’algorisme proposat en condicions relaxades de perspectiva d`ebil, com les estudiades en simulaci´o a la secci´o 3.3.3. Les imatges adquirides tenen evidents efectes de perspectiva, com es pot observar a les figures 3.12 i3.13. El primer experiment inclou el moviment equivalent de la c`amera provocat per una rotaci´o de 40◦sobre un eix en l’objecte en diversos angles d’inclinaci´o mostrejats a intervals de 15◦. D’aquesta manera, es poden comparar amb els resultats de la figura 3.5(b) en cas que la dist`ancia ´es igual a 500mm. Es fan cinc experiments, tots comen¸cant des de la posici´o frontoparal·lela mostrada en la figura 3.12(a). El contorn 57 3. Recuperaci´o de la direcci´o epipolar (a) Inicial (b) 15◦(c) 30◦ (d) 45◦(e) 60◦(f) 75◦ Figura 3.12: El primer experiment amb imatges reals correspon al c`alcul de la direcci´o epipolar entre parells de vistes inclosa la imatge inicial i cadascuna de les altres cinc. Corresponen a rotacions de 40◦de la c`amera sobre un eix en l’objecte amb inclinacions mostrejades a intervals de 15◦. La direcci´o epipolar computada es mostra gr`aficament com la recta que passa a trav´es del centre de l’objecte. se segueix fins a cadascuna de les vistes finals mostrades en les posicions restants de la figura 3.12(a) que generen una seq¨u`encia de direccions epipolars. La direcci´o epipolar computada al final del moviment per l’algorisme proposat es mostra gr`aficament com una l´ınia recta a trav´es del centre de l’objecte. La taula 3.2 presenta els valors num`erics obtinguts en el c`alcul de la direcci´o epipolar. La desviaci´o est`andard es computa adquirint 300 imatges en la posici´o final, 58 3.3 Experimentaci´o direcci´o epipolar -15 -30 -45 -60 -75 ¯ θ-16.63 -31.01 -45.00 -57.63 -72.04 σ0.14 0.09 0.14 0.19 0.13 Taula 3.2: Mitjana aritm`etica i desviaci´o est`andard en graus de la direcci´o epipolar computada per l’algorisme proposat en imatges reals. calculant els corresponents vectors de forma i computant cadascuna de les direccions epipolars. Cal notar que totes les desviacions est`andards s´on molt similars i que els valors mitjans es desvien m´es del valor real a mesura que l’angle se separa de 45◦ d’inclinaci´o. Aix`o s’hauria d’interpretar, considerant tamb´e la figura 3.5, com l’error introdu¨ıt a causa dels efectes de perspectiva que no poden ser modelats per la c`amera de perspectiva d`ebil. De fet, en condicions veritables de perspectiva d`ebil, els errors s´on molt m´es baixos, com es veu amb l’encongiment de les corbes d’error a la figura 3.5, quan la dist`ancia Z0de la c`amera a l’objectiu augmenta. Tamb´e s’analitzen tres seq¨u`encies addicionals relaxant altres condicions de perspectiva d`ebil, de manera similar al cas simulat. La primera seq¨u`encia, etiquetada “no centrada”, comen¸ca en la posici´o inicial frontoparal·lela (figura 3.13(a)) i acaba en una posici´o descentrada, despr´es d’una translaci´o de 100 mm al llarg de l’eix xdel sistema de coordenades del robot, i d’una rotaci´o de 40◦sobre un eix a 45◦d’inclinaci´o (figura 3.13(b)). De manera coherent amb els resultats simulats (vegeu la secci´o 3.3.3), aquesta translaci´o lateral de la c`amera ´es, de bon tros, la violaci´o de les condicions de perspectiva d`ebil que t´e l’efecte m´es important sobre el c`alcul de la direcci´o epipolar. Vegeu els valors num`erics en la Taula 3.3, primera fila. El segon experiment, etiquetat “no frontoparal·lel A”, correspon a la mateixa rotaci´o descrita en l’experiment anterior, per`o la posici´o inicial no ´es frontoparal·lela. La seq¨u`encia comen¸ca amb l’objecte rotat 20◦, com es mostra a la figura 3.13(c) i, despr´es d’una altra rotaci´o de 20◦, acaba a 40◦(figura 3.13(d)). Es pot veure que el resultat ´es una mica pitjor que el de l’experiment anterior, per`o amb una desviaci´o est`andard similar. Finalment, l’´ultim experiment, etiquetat “no frontoparal·lel B”, correspon a una seq¨u`encia amb el contorn inicialment no frontoparal·lel, rotat 40◦(figura 3.13(d)) i 59 4. Estudi anal´ıtic de la propagaci´o de l’error 4.1 Introducci´o Al cap´ıtol 2s’ha vist com es pot obtenir el moviment d’una c`amera a partir de la parametritzaci´o Sde la deformaci´o d’un contorn actiu en l’espai de forma. Tamb´e s’ha observat la necessitat de trobar una manera de calcular la incertesa de cada estimaci´o del moviment. Resulta interessant tant per saber quina confian¸ca es t´e en l’estimaci´o del moviment, com per poder implementar estrat`egies de fusi´o i col·laboraci´o amb altres sensors. Amb el filtre de Kalman es t´e una estimaci´o de la covari`ancia ΣS, per`o tal com s’ha vist aquesta covari`ancia est`a expressada en espai de forma. Cal, doncs, trobar un algorisme per propagar aquesta covari`ancia de l’espai de forma a l’espai 3D. La propagaci´o de la incertesa es pot abordar b`asicament des de dos punts de vista: l’anal´ıtic i l’estad´ıstic. Un m`etode anal´ıtic t´e l’avantatge que troba una expressi´o tancada, amb els beneficis que aix`o comporta. El problema ´es que arribar a la soluci´o a vegades comporta fer aproximacions que introdueixen un biaix en el resultat, per`o s’obt´e un algorisme generalment r`apid. En canvi, els m`etodes estad´ıstics s´on m´es senzills d’implementar, per`o generalment s´on m´es costosos de computar. Un estudi estad´ıstic de la propagaci´o de la incertesa es duu a terme al cap´ıtol 5. El m`etode anal´ıtic considera que entre les dades d’entrada i les de sortida hi ha una funci´o f. En el cas general, aquesta funci´o no t´e perqu`e ser lineal, per`o ha de ser possible estimar-ne el jacobi`a. Aquesta relaci´o es pot aproximar per un desenvolupament en s`erie de Taylor fins a primer ordre. Aquesta aproximaci´o s’ha fet servir, per exemple, per estimar par`ametres [31,37,148], per millorar els resultats en sistemes de cerca guiada [139], i recentment per localitzar robots [60,123]. Aquest m`etode t´e l’avantatge de ser r`apid de computar, per`o cal un esfor¸c previ de derivaci´o m´es gran en comparaci´o amb els m`etodes estad´ıstics. T´e el desavantatge que nom´es s’aproxima l’error, de manera que sempre hi ha un error residual que no es pot eliminar. L’algorisme que cal analitzar, que computa la posa a partir de l’afinitat que parametritza la deformaci´o af´ı d’un contorn, fa servir els valors i vectors propis de la matriu Mde l’afinitat. En la implementaci´o de l’algorisme, els valors propis necessaris per solucionar l’equaci´o 2.15 es troben amb el m`etode de la descomposici´o en valors singulars (SVD). Per estimar la propagaci´o de la incertesa en aquest cas, una possibilitat ´es estimar les derivades parcials de les tres matrius resultat de SVD respecte de cada 66 4.1 Introducci´o element de la matriu original. Es pot computar el jacobi`a de la SVD [100,109], fins i tot quan les matrius estan en casos degenerats. A [109] s’aplica la derivaci´o trobada per propagar l’error en tres problemes comuns de la visi´o artificial: autocalibraci´o, estimaci´o de la geometria epipolar i estimaci´o 3D de moviment r´ıgid. A vegades, per`o, ´es m´es ´util trobar directament l’expressi´o de la propagaci´o de les incerteses en els valors i vectors propis. Hi ha estudis cl`assics basats en la sensibilitat de vectors i valors singulars a pertorbacions en la matriu original [131,146]. En aquesta l´ınia, Weng [144,145], basant-se en aproximacions de primer ordre, estableix la relaci´o que hi ha entre la incertesa de la matriu original i la incertesa en els seus vectors i valors propis, i aplica aquesta derivaci´o a l’estudi de l’error en un algorisme d’estimaci´o del moviment r´ıgid d’una c`amera. En l’algorisme que cal analitzar la posa es calcula a partir dels valors i vectors propis combinats algebraicament amb elements de l’afinitat original. Per tant, nom´es amb aquests m`etodes no ´es suficient per con`eixer la incertesa de la posa. Un altre cam´ı possible ´es emprar `algebres de Lie [116]. Drummond i Cipolla [48] les utilitzen per estimar el jacobi`a de tota la transformaci´o no lineal que passa de l’espai de deformacions afins en la imatge a l’espai de moviments 3D, i ho apliquen al servocontrol visual. Desafortunadament, aquesta aproximaci´o ´es v`alida nom´es en determinades condicions i per a moviments infinitesimals. El jacobi`a obtingut en les condicions m´es generals del nostre algorisme resulta singular i, at`es que no ´es invertible, no es pot aplicar. Es proposa un algorisme que divideix la propagaci´o de la incertesa en dues etapes. En primer lloc, es propaga a trav´es de la SVD per tal de trobar les expressions de la incertesa associades als valors i vectors propis (secci´o 4.2). En segon lloc, es pren l’expressi´o que serveix per trobar cadascun dels par`ametres del moviment 3D i es fa servir l’aproximaci´o de primer ordre per trobar l’expressi´o final de la propagaci´o de la incertesa per a cadascun dels elements de la posa (secci´o 4.3). L’algorisme es formalitza a la secci´o 4.4 i es mostren els resultats d’uns experiments fets amb simulaci´o. Finalment s’exposen les conclusions (secci´o 4.5). 67 4. Estudi anal´ıtic de la propagaci´o de l’error 4.2 Propagaci´o als vectors i valors propis Coneguda la incertesa d’una matriu, el teorema de Weng et. al. [144,145] descrit a continuaci´o mostra com es pot aproximar fins a primer ordre la incertesa dels valors i vectors propis de la matriu. M´es endavant, Earnshaw i Blostein [50] van estendre la derivaci´o del teorema per aproximar la incertesa fins a segon ordre. El resultat ´util del teorema (vegeu l’ap`endix B) ´es el seg¨uent: sigui A= [aij] una matriu diagonalitzable i sim`etrica n×n, i ΣAuna matriu d’incertesa, considerant una aproximaci´o de primer ordre es pot expressar la incertesa al vector propi m´es petit com δ δ δv1=H∆1HTΣAv1(4.1) on H= [v1, .., vn] ´es la matriu de vectors propis i ∆1=diag(0,(λ1−λ2)−1, .., (λ1− λn)−1) ´es la matriu associada al valor propi m´es petit. La incertesa d’aquest valor propi s’expressa com δλ1∼ =vT 1ΣAv1(4.2) La matriu d’incertesa ΣAes pot reescriure en forma vectorial δ δ δAapilant-ne totes les columnes. D’aquesta manera, es pot reescriure (4.1) com δ δ δv1∼ =H∆HTΣAv1=H∆HT[v1Inv2In...vnIn]δ δ δA,Gv1δ δ δA(4.3) on vis´on les components del vector propi, In´es la identitat de dimensi´o n, i δ δ δA´es la versi´o vectorial de la matriu d’incertesa ΣAde la matriu A. De la mateixa manera es pot reescriure (4.2) com δλ1∼ =vT 1ΣAv1=vT 1[v1Inv2In...vnIn]δ δ δA,Pλδ δ δA(4.4) La incertesa del vector propi v2associat al segon valor propi λ2´es δ δ δv2∼ =H∆2HTΣAv2 on ∆2=diag((λ2−λ1)−1,0,(λ2−λ3)−1,···,(λ2−λn)−1) 68 4.2 Propagaci´o als vectors i valors propis De M a MMT El teorema esmentat explica com es propaga la incertesa d’una matriu Mals seus valors i vectors propis. Per`o la matriu que es fa servir en els c`alculs de la recuperaci´o del moviment 3D ´es MMTi la incertesa que es coneix, ΣM, ´es la de la matriu M. Per tant, cal veure com es relacionen ΣMiΣMMT. Es fa un canvi de variable que permet expressar de manera m´es compacta el resultat. Si es defineix N,MT, llavors A=MMT=NTN. El soroll que pertorba aquesta matriu es pot aproximar linealment i s’expressa com ΣA=ΣNTN∼ =NTΣN+ΣT NN En forma matricial aix`o ´es: δA 11 δA 12 δA 21 δA 22=N11 N12 N21 N22TδN 11 δN 12 δN 21 δN 22+δN 11 δN 12 δN 21 δN 22TN11 N12 N21 N22. Posant les matrius en forma vectorial i rearranjant els termes es pot escriure     δA 11 δA 12 δA 21 δA 22     =    N11 0 0N11+N11 0 N12 0 N21 0 0N21+N21 0 N22 0 N12 0 0N12+0N11 0N12 N22 0 0N22+0N21 0N22       δN 11 δN 12 δN 21 δN 22     i tenint en compte que N,MT, resulta     δA 11 δA 12 δA 21 δA 22     =    M11 0 0M11+M11 0 M21 0 M12 0 0M12+M12 0 M22 0 M21 0 0M21+0M11 0M21 M22 0 0M22+0M12 0M22       δM 11 δM 12 δM 21 δM 22     . De forma compacta, cada element del vector de soroll ´es δ δ δA=GAδ δ δM,(4.5) on GApot reescriure’s com: GA= [Fij]+[Gij], essent [Fij]i[Gij] matrius 2×2, on cada element Fij iGij ´es a la vegada una submatriu 2×2. En concret, Fij =MijI2iGij ´es una matriu en qu`e en la columna i-`esima hi ha el vector Mji en la resta de columnes, zeros. Aquestes equacions s´on lleugerament diferents de les trobades per Weng [145] at`es el canvi de variable realitzat. 69 4. Estudi anal´ıtic de la propagaci´o de l’error Ara, observant (4.5) es pot trobar l’expressi´o final de la incertesa als vectors propis de A=MMTrespecte de la incertesa coneguda de la matriu M, si es reescriu (4.3): δ δ δv1=Gv1δ δ δMMT=Gv1GMMTδ δ δM,Dv1δ δ δM.(4.6) De la mateixa manera, (4.4) es reescriu com δλ1=Pλ1δ δ δMMT=Pλ1GMMTδ δ δM,Qλ1δ δ δM.(4.7) 4.3 Aproximaci´o de primer ordre Un cop s’ha trobat l’expressi´o de la incertesa dels valors i vectors propis, el que cal ´es propagar-la pel que resta de l’algorisme d’estimaci´o del moviment, que s´on funcions derivables (2.16 -2.18 i2.19-2.21), per a les quals ´es possible calcular el jacobi`a. El m`etode m´es com´u per trobar una aproximaci´o de la matriu de covari`ancia Σydel resultat d’aplicar la funci´o y=f(x) ´es fer servir [32,51]: Σy=∂f ∂x0Σx ∂f ∂x0 T .(4.8) Per poder aplicar aquest m`etode cal que la funci´o f(x) sigui expl´ıcita i diferenciable, i cal con`eixer la matriu de covari`ancia Σxde les dades. Clarke [32] cita el teorema en qu`e es basa aquesta afirmaci´o i en mostra alguns exemples, i la seva demostraci´o es pot trobar a [24, p. 68]. Aquest m`etode no es pot aplicar a l’algorisme proposat per computar la posa a partir de les deformacions afins, ja que no hi ha una funci´o expl´ıcita, el que es t´e ´es un procediment o algorisme. A m´es ,no ´es diferenciable at`es que el procediment inclou el fet d’escollir el m´es petit dels valors propis obtinguts. Com s’ha vist, per calcular la posa es fan servir els valors i vectors propis de la SVD de la matriu M. A la secci´o anterior s’ha mostrat com es pot propagar la incertesa d’una matriu als valors i vectors propis de la seva descomposici´o en valors singulars. S’observa que cada element de la posa es calcula com a combinaci´o d’aquests valors i vectors propis, i d’elements del vector de forma original. En aquest cas, no es t´e la matriu de covari`ancia de tots aquests par`ametres, i per tant, tampoc no ´es factible fer servir directament (4.8). 70 4.3 Aproximaci´o de primer ordre f(x) x x f(x) y=f(x) incertesa en x incertesa en y Figura 4.1: Interpretaci´o gr`afica de la incertesa Una de les t`ecniques d’aproximaci´o m´es utilitzades es basa en l’expansi´o en s`erie de Taylor d’una funci´o. A vegades, aplicada a la propagaci´o de la incertesa s’anomena m`etode dels moments, ja que es propaga i analitza la incertesa fent servir la mitjana (primer moment), la desviaci´o t´ıpica (segon moment) i a vegades moments d’ordre m´es gran (coeficient d’asimetria, coeficient de curtosi...) de les distribucions de probabilitat. Una de les formes m´es utilitzades s’anomena primer-ordre segon-moment (FOSM1), ja que s’estima fins al segon ordre de la distribuci´o amb una aproximaci´o de primer ordre de la funci´o. Es poden fer aproximacions d’ordre m´es gran, per`o no ´es gaire freq¨uent, ja que els c`alculs s´on bastant m´es complexos i cal con`eixer pr`eviament els moments d’ordre elevat de les dades d’entrada, cosa que no sempre ´es factible. El m`etode dels moments es pot aplicar per trobar la incertesa de cadascun dels par`ametres de la posa 3D un cop coneguda la incertesa dels valors i vectors propis de la SVD de la matriu M. 71 4. Estudi anal´ıtic de la propagaci´o de l’error Una sola variable Si una variable xes mesura amb una incertesa δx, i es fa servir per calcular una funci´o y=f(x), la incertesa δy´es δy≈ ∂f ∂x δx.(4.9) Aquesta equaci´o es pot explicar geom`etricament d’una manera intu¨ıtiva observant la figura 4.1. Si es coneix la funci´o y=f(x)se’n pot fer la representaci´o gr`afica. Es pot aproximar aquesta funci´o amb una recta tangent al punt xi de pendent la derivada parcial.2Sabent la mesura d’entrada i el seu interval de confian¸ca es pot trobar el valor i l’interval del resultat. Com es pot observar, la incertesa dep`en tant de la incertesa del valor d’entrada com del pendent de la funci´o (o de l’aproximaci´o per la l´ınia tangent). Diverses variables En el cas que fdepengui de m´es d’una variable, la incertesa δyes troba combinant les aportacions que fa cadascuna de les diferents variables δy≈v u u t m X j=1 ∂f ∂xj δxj2 + 2 m X j=1 m X k=j+1 rxjxk∂f ∂xj δxj∂f ∂xk δxk,(4.10) on rxjxk´es el coeficient de correlaci´o entre les dues variables. De manera semblant al cas d’una variable, es pot interpretar geom`etricament com l’aproximaci´o de fpel pla tangent m-dimensional avaluat a les mitjanes de totes les m variables de que dep`en, i que t´e pendent de valor les derivades parcials ∂f/∂xi. Diverses variables independents Si les variables s´on independents, els termes de la covari`ancia s´on nuls i l’equaci´o anterior es pot reescriure com δy≈v u u t m X j=1 ∂f ∂xj δxj2 (4.11) 1first-order second-moment. 2Tenint en compte que el pendent de la gr`afica pot ser tant positiu com negatiu, cal emprar el valor absolut de la derivada parcial. 72 4.3 Aproximaci´o de primer ordre 4.3.1 Aplicaci´o a l’estimaci´o del moviment 3D En primer terme es considera que les variables del vector de forma s´on independents, i aix´ı es poden aplicar unes equacions de propagaci´o m´es simples. En el cas que els resultats siguin prometedors, llavors es pot ampliar el raonament tenint en compte les correlacions entre les variables. Translaci´o en Z El valor de la translaci´o en l’eix Z es troba amb (2.19) Tz Z0 =1 √λ1−1 Primer cal trobar-ne la derivada ∂Tz/Z0 ∂λ1 =−1/2 λ1√λ1 i llavors, substituint aquesta derivada a (4.9), s’obt´e δTz/Z0= ∂Tz/Z0 ∂λ1 δλ1=1/2 λ1√λ1 δλ1(4.12) Translaci´o en X L’expressi´o per calcular la translaci´o en l’eix X ´es (2.20) Tx Z0 =tx f√λ1 Les derivades parcials s´on ∂Tx/Z0 ∂tx =1 f√λ1 ∂Tx/Z0 ∂λ1 =−tx 2fλ1√λ1 i substituint a (4.9) s’obt´e δTx/Z0=s1 f√λ1 δtx2 +tx 2fλ1√λ1 δλ12 =1 f√λ1s(δtx)2+−txδλ1 2λ12(4.13) 73 4. Estudi anal´ıtic de la propagaci´o de l’error Translaci´o en Y De manera an`aloga al punt anterior, es troba l’expressi´o de la incertesa a la translaci´o en l’eix Y com δTy/Z0=1 f√λ1sδty2+−tyδλ1 2λ12 (4.14) Rotaci´o θ La rotaci´o θes computa amb (2.16) cosθ =rλ2 λ1 , Les seves derivades parcials s´on ∂θ ∂λ2 =−1 2qλ2 λ1λ1q1−λ2 λ1 ∂θ ∂λ1 =λ2 2qλ2 λ1λ2 1q1−λ2 λ1 i llavors, substituint a (4.9) s’obt´e δθ=v u u u t  1 2qλ2 λ1λ1q1−λ2 λ1 δλ2  2 +  λ2 2qλ2 λ1λ2 1q1−λ2 λ1 δλ1  2 =1 2λ1qλ2 λ1q1−λ2 λ1 sδ2 λ2+λ2δλ1 λ12 (4.15) Rotaci´o φ El valor de φs’obt´e directament de les components del vector propi v1= (vx, vy)T corresponent al valor propi m´es gran (2.17). Si es pren φ= arccos(vx), l’expressi´o que cal utilitzar ´es δφ=1 p1−v2 x δvx(4.16) 74 4.3 Aproximaci´o de primer ordre Amb aquesta expressi´o no es pot recuperar el signe del resultat. Per tal de tenir en compte el signe es pot fer servir la funci´o φ= arctan vy vx. Les derivades parcials s´on ∂φ ∂vx =−vy v2 x+v2 y ∂φ ∂vy =vx v2 x+v2 y La incertesa es troba com δφ=1 v2 x+v2 yrv2 yδ2 vx+v2 xδ2 vy(4.17) Experimentalment es pot comprovar que els valors obtinguts amb les dues equacions (4.16) i (4.17) s´on molt semblants. Rotaci´o ψ Per tal de trobar ψes fa servir l’element R11 de la matriu definida a (2.18). Desenvolupant, es pot trobar l’expressi´o seg¨uent: R11(ψ) = 1 + Tz Z0(cos(φ)M11 + sin(φ)M21) on sabem que 1 + Tz Z0 =1 √λ1 At`es que R´es una matriu de rotaci´o, es pot calcular el valor de la rotaci´o amb ψ= arccos(R11). Per trobar la propagaci´o de la incertesa es calculen les derivades parcials respecte de λ1, φ, M11 iM21: ∂ψ ∂λ1 =1/2(cos(φ)M11 + sin(φ)2M2 21) λ3/2 1s−(−λ1+cos(φ)2M2 11+2 cos(φ)M11 sin(φ)M21 +M2 21−M2 21 cos(φ)2) λ1 ∂ψ ∂φ =(sin(φ)M11 −cos(φ)M21) √λ1s−(−λ1+cos(φ)2M2 11+2 cos(φ)M11 sin(φ)M21 +M2 21−M2 21 cos(φ)2) λ1 ∂ψ ∂M11 =−cos(φ) √λ1s−(−λ1+cos(φ)2M2 11+2 cos(φ)M11 sin(φ)M21 +M2 21−M2 21 cos(φ)2) λ1 75 4. Estudi anal´ıtic de la propagaci´o de l’error de plantejar, i augmenten considerablement la complexitat dels c`alculs. Com es veur`a al proper cap´ıtol, l’aproximaci´o estad´ıstica a la propagaci´o de la incertesa ofereix alguns avantatges, i enceta algunes l´ınies interessants de treball futur. 82 Cap´ıtol 5 Estudi de la precisi´o Most people, including mathematicians, are amateur thinkers in the sense that they have not been taught how to think efectively. They have not been told to throw the crutch away and, as a result, have never learned how to run. Moltes persones, incloent-hi els matem`atics, s´on pensadors afeccionats en el sentit que no se’ls ha ensenyat com han de pensar amb efic`acia. No se’ls ha dit que llencin la crossa i, com a resultat, mai no han apr`es a c´orrer. Edsger W. Dykstra, December 1978. EDW696-1. Extracte En aquest cap´ıtol se segueix un enfocament estad´ıstic per analitzar la precisi´o de l’algorisme d’estimaci´o del moviment. Les simulacions de Monte Carlo mostren que les translacions paral·leles al pla de la imatge i la rotaci´o sobre l’eix `optic es recuperen millor que les translacions al llarg d’aquest eix, que a canvi s´on m´es acurades que les rotacions fora del pla. Pel que fa a les covari`ancies, nom´es els tres graus de llibertat menys precisos semblen estar relacionats. Per obtenir el moviment i la seva covari`ancia associada en un sistema rob`otic real es recorre a un altre m`etode estad´ıstic, la Unscented Transformation (UT), que amb l’espai de forma complet requereix tractar nom´es tretze mostres per cada vista. Se’n valida l’´us mitjan¸cant simulacions de Monte Carlo en experiments simulats, i s’utilitza per calcular la incertesa en experiments reals mostrats en els cap´ıtols anteriors: 5. Estudi de la precisi´o moviments curts amb un bra¸c rob`otic Sta¨ubli en una escena de laboratori controlada i translacions llargues amb un vehicle industrial en un magatzem. En l’´ultim cas, les incerteses obtingudes estan al voltant d’un 3%, que ´es una estimaci´o del moviment prou precisa en operacions de transfer`encia. 5.1 Introducci´o La import`ancia que s’ha donat al soroll en visi´o artificial ha augmentat progressivament al llarg dels anys. Els primers algorismes de geometria visual se centraven en el nombre m´ınim de punts que calia per aplicar un algorisme determinat. M´es endavant, es va incorporar la redund`ancia en les dades per poder tractar amb imatges reals, en qu`e el soroll ´es una component important. Avui dia, la propagaci´o de l’error i les t`ecniques d’estimaci´o de la incertesa s’estan aplicant com a pas necessari per intentar reduir la incertesa d’una manera activa. Els algorismes per recuperar la geometria epipolar i el moviment propi tamb´e han seguit aquesta tend`encia general. Per exemple, encara que se sap que vuit correspond`encies de punts s´on suficients per obtenir la matriu fonamental [63,89], l’algorisme de refer`encia EdO utilitza m´es correspond`encies, redundants, que porten a una estimaci´o m´es robusta a la pr`actica [62,88]. Un primer pas per tractar expl´ıcitament els errors ´es detectar els valors an`omals.1Els dos algorismes m´es populars s´on el Least Mean Squares (LMedS), de qui Zhang [148] d´ona una descripci´o detallada, i el Random Sample Consensus (RANSAC), proposat per Fischler i Bolles [54]. Torr i Murray [137] en proporcionen un estudi comparatiu. El seg¨uent pas ´es modelar el soroll en les dades d’entrada per analitzar com es propaga en el resultat. Una bona introducci´o amb exemples aplicats a casos reals es pot trobar a [32]ia[36]. Si no es t´e informaci´o a priori, sovint se suposa que la incertesa de les dades d’entrada obeeix una distribuci´o gaussiana [62]. La interdepend`encia entre les variables, quan est`a quantificada, normalment es representa per mitj`a d’una matriu de covari`ancies [28,103]. Alguns estudis [22,80] demostren que utilitzar la covari`ancia per caracteritzar la incertesa, per exemple en la localitzaci´o de correspond`encies de punts, ajuda a dissenyar algorismes millors que si no es t´e en compte. Fins i tot, la 1En angl`es outliers. 84 5.1 Introducci´o incertesa en el mateix proc´es d’estimaci´o de la matriu de covari`ancies tamb´e afecta la qualitat del resultat. Una vegada que es modela el soroll a les dades d’entrada, la propagaci´o de la incertesa generalment s’estudia o b´e anal´ıticament o b´e estad´ısticament. Tal com s’ha vist al cap´ıtol anterior, els estudis anal´ıtics sovint requereixen que s’obtingui el jacobi`a de la relaci´o entre les dades d’entrada i el resultat que, per a funcions no lineals, sovint exigeix rec´orrer a aproximacions lineals. Des del punt de vista estad´ıstic, una de les eines m´es potents i simples ´es la simulaci´o de Monte Carlo [46]. Es basa a mostrejar densament l’espai d’entrada i executar l’algorisme per a cada mostra. Un dels problemes ´es que cal determinar el nombre de mostres que s’utilitzaran. Sovint es pren un nombre molt alt per assegurar que es mostreja tot l’espai d’entrada i que el resultat no estar`a esbiaixat i, per tant, s’utilitza quan es necessiten pocs resultats o quan el temps de computaci´o no ´es un problema. Per tal de reduir el temps de c`omput, Julier i Uhlmann han proposat la Unscented Transformation (UT), que intenta trobar determin´ısticament el conjunt de mostres m´es petit que capturi la distribuci´o estad´ıstica de les dades. Aquesta representaci´o ´es particularment interessant, ja que obre la possibilitat d’utilitzar m´es endavant un filtre de Kalman no lineal amb la UT (Unscented Kalman Filter [74], UKF), o un filtre de part´ıcules [57] (PF), tamb´e amb la seva versi´o UT (Unscented Particle Filter [140], UPF). La conveni`encia de la UT per a un problema particular es pot provar amb simulaci´o de Monte Carlo i, si ´es valida, aquesta transformaci´o pot comportar estalvis de temps considerables. L’objectiu d’aquest cap´ıtol ´es analitzar estad´ısticament la precisi´o de l’algorisme de recuperaci´o del moviment de la c`amera mostrat a la secci´o 2.2. Primer, a la secci´o 5.3 es mostra que cal canviar la representaci´o de les rotacions. L’an`alisi de la precisi´o es porta a terme a la secci´o 5.4, on s’analitza la precisi´o utilitzant simulaci´o de Monte Carlo. A la secci´o 5.4.2 s’analitzen les correlacions que han aparegut entre les components de translaci´o i rotaci´o. Un segon prop`osit d’aquest cap´ıtol ´es obtenir un algorisme per estimar la matriu de covari`ancies del sis graus de llibertat del moviment aplicable en temps real per utilitzarlo en aplicacions de rob`otica. Per aix`o, a la secci´o 5.5.1 es presenta la Unscented Transformation, que permet, escollint determin´ısticament un nombre molt limitat de 85 5. Estudi de la precisi´o punts, propagar la covari`ancia a l’espai de moviment. Per demostrar que l’algorisme ´es utilitzable es porten a terme una s`erie d’experiments (secci´o 5.5.2). Finalment, a la secci´o 5.6 es presenten algunes conclusions i perspectives futures. 5.2 Monte Carlo Tot i que ja s’ha fet servir anteriorment, es presenta breument aquest m`etode estad´ıstic. L’estimaci´o per mostreig aleatori ´es un m`etode general i molt f`acil d’implementar, per`o normalment ´es molt cost´os des de punt de vista computacional. A m´es, nom´es proporciona la soluci´o per al vector de dades d’entrada que es fa servir. Si les dades canvien, cal refer tota la simulaci´o. El m`etode ´es bastant simple [46]: s’assumeix que es t´e una funci´o, un vector de dades d’entrada, i que la incertesa Σ es pot modelar a partir d’una distribuci´o de probabilitat coneguda. El vector d’entrada es pertorba repetidament amb el soroll modelat Σ per tal d’obtenir nvectors de dades diferents. Per a cadascun d’aquests vectors es calcula el valor corresponent aplicant la funci´o y=f(x, q, ...). Finalment, es pot examinar la distribuci´o dels valors obtinguts de yi es poden calcular els estad´ıstics (generalment la mitjana i la covari`ancia). Aquest m`etode permet trobar la incertesa encara que la funci´o fsigui complexa o fins i tot desconeguda (per exemple, un proc´es de minimitzaci´o [32]), per`o requereix molt d’esfor¸c de computaci´o, ja que actua per for¸ca bruta. A m´es, no ´es f`acil descriure l’aportaci´o de cada variable a la incertesa global. Usualment, tal com s’ha emprat al cap´ıtol anterior, la simulaci´o de Monte Carlo es fa servir per avaluar la precisi´o dels m`etodes anal´ıtics. 5.3 Representaci´o de les rotacions Tal com es pot veure a l’equaci´o 2.14, fins ara les rotacions s’han codificat mitjan¸cant angles d’Euler R=Rz(φ)Rx(θ)Rz(ψ). ´ Es ben conegut que aquesta representaci´o t´e el problema de la gimbal lock: quan dos eixos estan alineats apareix un problema d’indeterminaci´o. En aquesta representaci´o aix`o passa quan la segona rotaci´o Rx(θ) est`a a prop de la rotaci´o nul·la. El resultat ´es que petites variacions de la posa de la c`amera al voltant de la posici´o inicial no corresponen a valors continus de les components de 86 5.3 Representaci´o de les rotacions −200 0 200 0 100 200 300 400 Rz(φ)0 5 10 15 0 100 200 300 400 500 Rx(θ)−200 0 200 0 100 200 300 400 Rz(ψ) (a) rotaci´o ZXZ 0 5 10 15 0 50 100 150 200 250 300 Rx(φ)0 5 10 15 0 50 100 150 200 250 300 Ry(θ)−1 0 1 2 0 100 200 300 400 500 Rz(ψ) (b) rotaci´o ZYX Figura 5.1: Histogrames de les components de 5000 rotacions calculades afegint soroll σ= 0.5 pixels als punts de control de la projecci´o d’un contorn. A les rotacions ZXZ, petites variacions de la posa corresponen a valors discontinus de les components Rz(φ) i Rz(ψ). En canvi, les mateixes variacions corresponen a valors continus en la representaci´o ZY X. la rotaci´o (vegeu Rz(φ) i Rz(ψ) a la figura 5.1(a)). Aquest problema apareix freq¨uentment, tant a l’inici de la seq¨u`encia d’imatges com tamb´e quan el robot es mou cap a l’objecte fixat. Es proposa convertir la representaci´o en una codificaci´o guinyada-capcineig-balanceig.2 Aquesta representaci´o s’utilitza freq¨uentment en el camp de navegaci´o, i a vegades tamb´e s’anomena rumb-horitz´o-inclinaci´o [122].3Es fa servir la forma R=Rz(ψ)Ry(θ)Rx(φ) =   cψcθ sψcφ +cψsθsφ sψsφ −cψsθcφ −sψcθ cψcφ −sψsθsφ cψsφ +sψsθcφ sθ −cθsφ cθcφ  ,(5.1) 2en angl`es roll, pitch, yaw 3en angl`es heading, attitude, bank 87 5. Estudi de la precisi´o 0 4 8 12 16 20 0 5 10 15 20 φ mitjana MC Real (a) Valors de rotaci´o 0 4 8 12 16 20 −1 0 1 2 3 4 φ error MC Real (b) Error Figura 5.2: Error sistem`atic en la component Rx. La l´ınia cont´ınua representa els valors obtinguts amb Monte Carlo i la l´ınia discont´ınua s´on els valors reals. El mateix es pot aplicar a la component Ry. on sψ icψ representen el sinus i el cosinus respectivament de ψ. La soluci´o inversa ´es φ=atan2(R32, R33) (5.2) θ=atan2(−R31,qR2 32 +R2 33) (5.3) ψ=atan2(R21, R11).(5.4) Generalment, per tal de representar tot l’espai de rotacions possibles, cadascun dels elements de la rotaci´o es restringeix per pert`anyer al rang [0..2π]rad per ψiφ, i a [0..π]rad per θ. De fet, el seguiment d’un objecte planar per una c`amera que rota segons l’eix Xo Ym´es enll`a de π/2 rad no t´e sentit, ja que en aquesta posici´o tots els punts de control de l’objecte s´on colineals i la forma de l’objecte es perd. A m´es, a causa de l’ambig¨uitat Necker reversal [62], no ´es possible determinar el signe de les rotacions entorn d’aquests eixos. Conseq¨uentment, i sense p`erdua de generalitat, es poden restringir els valors de les rotacions Ry(θ) i Rx(φ) per tal que pertanyin al rang [0..π 2)rad i deixar Rz(ψ) al rang de valors [0..2π]rad. Amb aquesta representaci´o s’ha aconseguit despla¸car la gimbal lock fins a cos(θ) = 0, que queda fora del rang de valors possibles. Amb l’eliminaci´o de signe esmentada s’introdueix un biaix per a l’estimaci´o de rotacions Rx(φ) i Ry(θ) petites. En pres`encia de soroll i quan la rotaci´o realitzada per la c`amera ´es petita, les rotacions negatives es computen positives. D’aquesta manera el c`alcul d’una posa mitjana, com la que es presenta en aquest cap´ıtol, est`a esbiaixat. La 88 5.4 Avaluant la precisi´o de les components del moviment −80 −60 −40 −20 0 20 40 60 80 −80 −60 −40 −20 0 20 40 60 80 Figura 5.3: Projecci´o original del contorn (l´ınia discont´ınua), projecci´o de contorn despr´es del moviment combinat detallat a la secci´o 5.4.1 (l´ınia cont´ınua), i projecci´o de contorn despr´es del moviment combinat excepte la translaci´o (l´ınia de punts i guions), per apreciar millor la deformaci´o extrema a la que s’arriba amb les rotacions en els experiments. Es poden observar alguns efectes de perspectiva evidents. figura 5.2(a) mostra els resultats d’un experiment en qu`e la c`amera fa una rotaci´o de 0 a 20◦sobre l’eix Xd’un sistema de coordenades situat en l’objecte. Clarament, els valors Rx(φ) computats per la simulaci´o de Monte Carlo s´on m´es propers als veritables a mesura que l’angle de rotaci´o augmenta. La figura 5.2(b) resumeix els errors que en resulten. La comparaci´o dels dos valors permet avaluar la quantitat d’error sistem`atic introdu¨ıt per la representaci´o de rotaci´o. En resum, l’espai de rotaci´o proposat ´es significativament menor que l’anterior, per`o hem mostrat que ´es prou gran per representar totes les situacions possibles. Tamb´e s’aconsegueix evitar la gimbal lock despla¸cant-la fora del rang. Com es pot veure a la figura 5.1, les variacions petites en la posa resulten en variacions petites en les components de rotaci´o. Conseq¨uentment, el moviment es pot calcular coherentment com una mitjana i la covari`ancia. 5.4 Avaluant la precisi´o de les components del moviment 5.4.1 Propagaci´o de la incertesa a cada component del moviment Els experiments sint`etics estan dissenyats de la manera seg¨uent. Es defineix un objecte planar en l’espai 3D i es projecta al pla de la imatge utilitzant un model de c`amera 89 5. Estudi de la precisi´o de perspectiva completa.4Es trien un conjunt de punts de control que ressegueixen la projecci´o de l’objecte, de manera que es defineix la parametritzaci´o B-Spline del contorn (figura 5.3). Si es forcen les condicions de visualitzaci´o possiblement apareixen efectes de perspectiva en els punts projectats (com en una situaci´o real), per`o l’afinitat emprada no els pot modelar (nom´es pot aproximar el conjunt de punts el millor possible). Si apareixen efectes perspectius, aquests efectes es modelen amb les deformacions afins que es permeten (figura 2.3) i per tant s’introdueix algun error en l’estimaci´o del moviment que cal avaluar. Per a aquests experiments la c`amera es posa a 5000 mm de l’objecte i la dist`ancia focal es fixa a 50 mm. S’han dut a terme diversos experiments amb moviments diferents. Una vegada que la c`amera s’ha mogut, s’afegeix soroll gaussi`a amb mitjana zero i σ= 0.5 als punts de control per simular el soroll d’adquisici´o de la c`amera. Una simulaci´o de Monte Carlo serveix per trobar la mitjana i la covari`ancia del moviment en cada experiment, utilitzant com a transformaci´o l’algorisme presentat a la secci´o 2.2. En cada simulaci´o de Monte Carlo s’utilitzen 5000 mostres. Efecte del soroll en la recuperaci´o d’un moviment simple L’objectiu ´es determinar experimentalment el grau d’exactitud que s’assoleix (error mitj`a i incertesa) amb l’algorisme de recuperaci´o de posa per a cada component del moviment de la c`amera, ´es a dir, les translacions Tx, TyiTz, i les rotacions Rx, RyiRz. Els primers dos experiments impliquen una translaci´o lateral de la c`amera paral·lela als eixos XoY. Amb la configuraci´o escollida de la c`amera, la translaci´o lateral de fins a 300 mm porta la projecci´o de l’objecte des del centre de la imatge fins al l´ımit de la imatge. Els errors en les estimacions del moviment es presenten a les figures 5.4(a) i5.4(c), i com era d’esperar s´on iguals per a les dues translacions. Aix`o ´es perqu`e es considera que els p´ıxels s´on quadrats i que la relaci´o d’aspecte ´es unit`aria. Observeu que mentre la c`amera s’allunya de la posici´o inicial l’error en la translaci´o augmenta, aix´ı com la incertesa corresponent. L’explicaci´o ´es que les condicions del model de perspectiva d`ebil estan menys satisfetes quan l’objecte no est`a centrat. Tanmateix, el m`axim error en la mitjana aritm`etica ´es aproximadament 0.2%, i la pitjor desviaci´o 4Per modelar millor el proc´es de formaci´o de la imatge en la simulaci´o es fa servir un model m´es complet, el de perspectiva completa, que el model que suposa l’algorisme de recuperaci´o del moviment, el de perspectiva d`ebil, per tal d’obtenir imatges sint`etiques m´es reals. 90 5.4 Avaluant la precisi´o de les components del moviment 0 60 120 180 240 300 −4 −3 −2 −1 0 1 2 x error (a) 0 10 20 30 40 50 −10 −5 0 5 10 15 φ error (b) 0 60 120 180 240 300 −4 −3 −2 −1 0 1 2 y error (c) 0 10 20 30 40 50 −10 −5 0 5 10 15 θ error (d) 0 −700 −1400 −2100 −2800 −3500 −80 −60 −40 −20 0 20 40 z error (e) 0 10 20 30 40 50 −1 −0.5 0 0.5 1 ψ error (f) Figura 5.4: Mitjana de l’error (l´ınies cont´ınues) i desviaci´o t´ıpica 2σ(l´ınies discont´ınues) per a moviments purs al llarg i al voltant dels tres eixos de coordenades. Els errors i desviacions en les translacions TxiTys´on equivalents, petits mentre la projecci´o est`a centrada i augmentant a mesura que s’allunya del centre, i pitjors en la translaci´o Tz(encara que milloren si la c`amera s’aproxima a l’objecte). Els errors a RxiRyper a rotacions petites s´on grans, mentre que per a rotacions grans els errors s´on menys significatius. L’error en la rotaci´o Rz´es insignificant. est`andard ´es 0.6%, i per tant es pot considerar que les translacions laterals es recuperen for¸ca correctament. Tal com s’ha mostrat al cap´ıtol 3, el signe de l’error dep`en de la forma de l’objecte i de l’orientaci´o de l’eix de rotaci´o. El tercer experiment implica una translaci´o al llarg de l’eix `optic Z. Des de la 91 5. Estudi de la precisi´o −0.5 0 0.5 2 4 6 8 10 12 14 16 yφ y φ (a) (b) Figura 5.7: (a) Representaci´o gr`afica de la submatriu 2 ×2 de covari`ancia per mitj`a de l’el·lipse d’error que relaciona la rotaci´o φal voltant de l’eix Xi la translaci´o al llarg de l’eix Y. En realitat, el moviment es compon de nom´es una rotaci´o, per`o tamb´e se’n dedueix una petita translaci´o. (b) Efecte de rotar un objecte planar (que ´es equivalent a rotar una c`amera al voltant d’un objecte). El model de perspectiva d`ebil suposa que les projeccions en la imatge haurien de ser on es creuen els raigs puntejats amb el pla de la imatge, per`o realment s´on on es projecten les l´ınies ratllades. Conseg¨uentment, es computa una translaci´o lateral quan en realitat nom´es s’ha fet una rotaci´o. Cal notar que el valor de la translaci´o dep`en de la dist`ancia inicial. Aquestes s´on les ´uniques dues correlacions presents entre les components de moviment recuperades amb l’algorisme proposat. Com ja s’ha esmentat anteriorment, el conjunt complet de resultats experimentals, inclosos tots els moviments al llarg i al voltant dels eixos coordinats i totes les representacions gr`afiques de les submatrius 2 ×2 de covari`ancia, es poden trobar a l’ap`endix C. 5.5 Experiments amb seq¨u`encies reals Les simulacions de Monte Carlo utilitzades anteriorment s´on una eina simple i potent. Tanmateix, sovint nom´es es poden aplicar quan es necessiten pocs resultats o quan el temps de c`alcul no ´es una restricci´o. Ens agradaria trobar un algorisme per propagar la incertesa per a cada estimaci´o del moviment de la c`amera que s’obt´e. En l’actual implementaci´o de l’algorisme proposat es treballa amb vint imatges per segon. L’alternativa que s’ha adoptat, l’anomenada Unscented Transformation, utilitza un nombre petit de mostres que representen la distribuci´o estad´ıstica de les dades, cosa que redueix considerablement el temps de computaci´o exigit per a la propagaci´o d’incertesa. m´es negligibles, com es podr`a observar a la secci´o 5.5.2 d’experiments reals. 98 5.5 Experiments amb seq¨u`encies reals 5.5.1 La Unscented Transformation La Unscented Transformation (UT) va ser proposada per Julier i Uhlmann [73,74]. ´ Es un m`etode per propagar els estad´ıstics a trav´es d’una funci´o general no lineal. La UT no es restringeix a assumir que la distribuci´o d’incertesa de les dades ´es gaussiana. Es defineix de la manera seg¨uent: primer, es trien determin´ısticament un conjunt de punts, anomenats punts sigma (sigma points), que s’espera que capturin els estad´ıstics de la distribuci´o de les dades. Segon, els punts es propaguen fent servir la funci´o no lineal. Finalment, es poden calcular els estad´ıstics amb els punts propagats i aix´ı estimar els estad´ıstics del resultat de la funci´o no lineal. Normalment, aquesta t`ecnica s’utilitza en un paradigma del Filtre Kalman per fer l’estructura de predicci´o i actualitzaci´o recursiva. Aquest ´es l’anomenat Unscented Kalman Filter (UKF) [73]. Cal notar que no ´es necessari calcular les derivades parcials de la transformaci´o. A m´es, la complexitat d’aquest algorisme ´es la mateixa que la de l’EKF. Julier i Uhlmann [74] van demostrar els beneficis de l’UKF en el context de l’estimaci´o de l’estat per a control no lineal, i Wan i Van Der Merwe [143] van mostrarne l’aplicaci´o en problemes d’estimaci´o de par`ametres. Tamb´e van desenvolupar una formulaci´o on es propaga l’arrel quadrada de la matriu de covari`ancies en lloc de la matriu mateixa [141]. Amb aquesta aproximaci´o, els algorismes tenen millors propietats num`eriques (principalment en el marc d’aplicaci´o de l’UKF), i la seva complexitat es redueix per a problemes d’estimaci´o de par`ametres. Tamb´e van desenvolupar una extensi´o del concepte dels filtres de punts sigma per treballar amb filtres de part´ıcules i sumes de gaussianes [140,142]. Lefebvre et al. [85] van proposar una interpretaci´o alternativa de la UT com una regressi´o lineal estad´ıstica, que ´es ´util per justificar els beneficis que s’obtenen amb UKF. S’han proposat diferents algorismes per a la tria determin´ıstica dels punts sigma. Es pot trobar un resum dels diferents m`etodes amb els avantatges i inconvenients que tenen a l’ap`endix D. Aqu´ı es fa servir l’algorisme que originalment es va desenvolupar: la soluci´o sim`etrica [73]. Aquest algorisme requereix de 2Nx+ 1 punts sigma, on Nx ´es la dimensi´o del vector de dades d’entrada. Un punt sigma se situa en la mitjana i els altres se situen sim`etricament al voltant, dos en cada dimensi´o dels eixos principals de la covari`ancia. Es pot representar com un punt sigma al centre de cada cara d’un 99 5. Estudi de la precisi´o hipercub imaginari. A vegades s’anomena UT de segon ordre, ja que la transformaci´o garanteix que es preserven la mitjana i la covari`ancia (els primers dos moments). La variable aleat`oria Nx-dimensional xamb mitjana ¯ xi matriu de covari`ancia Σx es pot aproximar amb el conjunt de punts: x0=¯ x xi=¯ x+ rNx 1−w0Σx!i per i= 1,...,Nx xi+Nx=¯ x− rNx 1−w0Σx!i per i= 1,...,Nx (5.5) amb els pesos w0 wi=1−w0 2Nx per i= 1,...,Nx wi+Nx=1−w0 2Nx per i= 1,...,Nx (5.6) on (√NxΣx)i´es la fila o columna i-`esima7de l’arrel de la matriu NxΣx, i wi´es el pes associat amb el i-`esim punts sigma. Els pesos han de complir la condici´o Pwi= 1. Per convenci´o, el primer punt sigma x0correspon al punt situat en la mitjana. El pes w0assignat a aquest punt controla d’alguna manera la situaci´o dels altres punts. Si el pes ´es positiu, la resta de punts tendeixen a allunyar-se de l’origen i preserven, per tant, el valor de la covari`ancia. Al contrari, si el pes ´es negatiu, els punts es mouen de manera que s’apropen a l’origen [72]. Aquest mecanisme ajusta els moments d’ordre elevat de la distribuci´o. Amb aquest esquema, la mitjana i la covari`ancia de la variable yes poden calcular a partir dels punts sigma transformats, yi=f(xi), segons ¯ y= 2n X i=0 wiyi Σy= 2n X i=0 wiyi−¯ yyi−¯ yT. (5.7) 7Depenent de com est`a formada la matriu Σ, cal fer servir les files o les columnes. Si Σ=AAT, llavors els punts sigma es formen amb les files d’A. En canvi, si Σ=ATA, els punts sigma es formen amb les columnes d’A. 100 5.5 Experiments amb seq¨u`encies reals 5.5.2 Fent servir la UT per estimar la mitjana i la covari`ancia del moviment En l’algorisme d’estimaci´o del moviment propi proposat, l’espai d’entrada ´es l’espai de forma 6-dimensional (2.12), que es transforma a trav´es de les equacions (2.16 -2.21) en les tres components de translaci´o i les tres de rotaci´o que componen el moviment de la c`amera. Per propagar les covari`ancies amb la UT calen 2d+ 1 = 13 punts sigma segons el m`etode de selecci´o sim`etric, essent d= 6 la dimensi´o de l’espai entrada. El procediment per calcular les covari`ancies utilitzant la UT ´es el seg¨uent. Primer, s’inicialitza manualment sobre la imatge un contorn actiu en qu`e s’especifiquen alguns punts de control. Aix`o defineix una matriu de forma Wsegons (2.12). L’algorisme de propagaci´o de la covari`ancia, especificat a l’algorisme 5.1, procedeix de la manera seg¨uent. A cada iteraci´o s’adquireix una nova imatge. Amb un filtre de Kalman es calcula la deformaci´o af´ı del contorn actual respecte al contorn inicial, codificat com un vector de forma, aix´ı com una covari`ancia associada. Basant-se en aquests resultats, l’algorisme UT selecciona 13 punts sigma en l’espai de forma, als quals s’aplica la transformaci´o no lineal per trobar el moviment 3D i la covari`ancia que els correspon. Entrada : Inversa W−1de la matriu de forma, punts de control inicials Q0 Sortida : Posa RT i covari`ancia ΣRT Adquirir una nova imatge1 Amb el filtre de Kalman, predir on es troba el contorn, mesurar on es troben els2 punts de control Qdel contorn projectat, i estimar el vector de forma corresponent usant S=W−1(Q−Q0) Trobar els tretze punts sigma xien espai de forma (5.5) i els seus pesos wi(5.6)3 apartir del vector de forma Si la covari`ancia ΣSestimats pel filtre de Kalman per i=1 fins 13 fer4 Calcular la posa corresponent al punt sigma xi 5 fi6 Calcular la posa RT i la seva covari`ancia ΣRT aplicant (5.7)7 Algorisme 5.1 : Algorisme d’estimaci´o de la posa i la seva covari`ancia amb la UT. Per tal de validar la derivaci´o d’aquest algorisme, s’han realitzat els mateixos experiments sint`etics que els duts a terme amb la simulaci´o de Monte Carlo a la secci´o 5.4.2 i l’ap`endix C, i s’ha calculat la corresponent covari`ancia amb el darrer algorisme utilitzant la UT. Els resultats s’inclouen a les figures 5.6,5.7, i C.1 aC.6. En tots els 101 5. Estudi de la precisi´o (a) imatge0(b) imatge80 Figura 5.8: Imatge inicial i rotaci´o m`axima per a un dels experiments amb el bra¸c rob`otic. experiments la covari`ancia estimada amb la UT ´es molt similar a l’obtinguda amb la simulaci´o de Monte Carlo i, per aix`o, es pot concloure que ´es correcte utilitzar la UT per calcular la covari`ancia del moviment. S’ha realitzat dos conjunts d’experiments amb robots reals. En el primer, un objecte sostingut per un bra¸c rob`otic Sta¨ubli es fa girar davant d’una c`amera imm`obil. En el segon, una c`amera es munta sobre un vehicle portapalets Still EGV-10, que segueix una traject`oria per apropar-se a un objecte mentre oscil·la lleugerament, cosa que ocasiona una translaci´o llarga. Experiments de rotaci´o usant un bra¸c rob`otic En el primer experiment es calcula la incertesa del moviment en un entorn d’experimentaci´o que s’ha presentat anteriorment a la secci´o 3.3: un bra¸c rob`otic Sta¨ubli que sost´e un objecte artificial. En aquest experiment l’objecte es fa girar 40◦(i s’atura cada zero graus) al voltant d’un eix definit sobre l’objecte a 45◦, i despr´es s’hi aplica una segona rotaci´o per retornar-lo a la posici´o inicial. La figura 5.8 mostra l’objecte en la posici´o inicial i en el punt de m`axima rotaci´o. Observeu que aquest moviment ´es equivalent a rotar la c`amera −45◦sobre el mateix eix. A la figura 5.9 es pot observar l’evoluci´o de les sis components del moviment al llarg de tota la seq¨u`encia d’imatges, on es mostra tant l’estimaci´o amb la UT com la transformaci´o del vector de forma (anomenada “directe”). 102 5.5 Experiments amb seq¨u`encies reals 0 50 100 150 200 −5 −4 −3 −2 −1 0 1 frame x UT Directe (a) Tx 0 50 100 150 200 −4 −3 −2 −1 0 frame y UT Directe (b) Ty 0 50 100 150 200 −30 −25 −20 −15 −10 −5 frame z UT Directe (c) Tz 0 50 100 150 200 5 10 15 20 25 30 35 frame φ UT Directe (d) Rx 0 50 100 150 200 0 5 10 15 20 25 30 frame θ UT Directe (e) Ry 0 50 100 150 200 −8 −6 −4 −2 0 frame ψ UT Directe (f) Rz Figura 5.9: Components del moviment que es recupera en l’experiment de la rotaci´o amb imatges reals. El moviment consta d’una rotaci´o de 40◦al voltant d’un eix inclinat 40◦frontoparal·lel a la c`amera i centrat en l’objecte, seguit d’una segona rotaci´o de −45◦al voltant del mateix eix. En vermell hi ha els resultats obtinguts amb l’algorisme original, i en negre els valors del moviment amb l’algorisme que utilitza la UT. De manera congruent amb els resultats sint`etics (vegeu la figura 5.7(b), on es computa una lleugera translaci´o quan es fa nom´es una rotaci´o), es computen petites translacions TxiTy(figures 5.9(a) i5.9(b)) tot i que en realitat no es fan. Gr`acies al calibratge realitzat, aquests resultats es poden expressar en mil·l´ımetres i es pot concloure que els errors de translaci´o computats (de com a m`axim 4 mm) s´on insignificants. Com 103 5. Estudi de la precisi´o 0 50 100 150 200 0 5 10 15 20 25 30 imatge desviació típica Tx Ty Tz Rx Ry Rz (a) desviacions t´ıpiques 0 50 100 150 200 400 500 600 700 800 imatge traça (b) tra¸ca Figura 5.10: (a) Desviacions t´ıpiques computades amb la UT per a l’experiment de rotaci´o, i (b) Tra¸ca de la matriu de covari`ancies que en resulta. era d’esperar, les translacions Tzes recuperen amb m´es error. El proc´es de calibratge determina una dist`ancia inicial des de la c`amera fins a l’objecte de Z0= 500 mm, aix´ı que la precisi´o en la recuperaci´o d’aquesta translaci´o est`a entre l’1% i el 3%, que concorda amb els resultats obtinguts en la simulaci´o. Les rotacions RxiRyno es recuperen correctament per sota de 15◦a causa del soroll en l’adquisici´o i el proc´es de seguiment del contorn. El biaix a causa de la representaci´o de la rotaci´o tamb´e contribueix a afavorir aquest error inicial. Entre les imatges 50 i 100 es poden observar clarament les pauses a cada 10◦, i com coincideixen les rotacions computades amb la UT i directament a partir del vector de forma. Per a la rotaci´o Rz coincideixen al llarg de la seq¨u`encia sencera. A la figura 5.10(a) es mostren les desviacions t´ıpiques aproximades per a la seq¨u`encia de moviment sencera. Les desviacions per a TxiTys´on gaireb´e nul·les. La desviaci´o m´es important s’obt´e per a la component Tz. Es pot observar que la desviaci´o augmenta al mig de la seq¨u`encia, on la rotaci´o ´es m´es gran. Aix`o ´es degut a l’efecte de perspectiva explicat anteriorment a la figura 5.5(f). Es pot observar que les desviacions per a les components RxiRydisminueixen lleugerament quan augmenten els valors de la rotaci´o, i tornen a la seva posici´o inicial quan l’objecte retorna a la posici´o inicial, on s’hauria de recuperar la rotaci´o nul·la. Com era d’esperar, a causa de la correlaci´o entre les rotacions RxiRy, i la translaci´o Tz, la incertesa en Tztamb´e disminueix lleugerament. La figura 5.10(b) mostra la tra¸ca de les matrius de covari`ancies. La tra¸ca es pot 104 5.5 Experiments amb seq¨u`encies reals (a) imatgeinicial (b) imatgemig (c) imatgefinal Figura 5.11: Experiment real en qu`e el robot efectua una translaci´o llarga mentre oscil·la lleugerament. considerar una estimaci´o aproximada de la mida de la covari`ancia [128], i serveix aqu´ı per il·lustrar el comportament global de la incertesa. En la covari`ancia calculada amb l’algorisme proposat, la tra¸ca est`a fortament influ¨ıda per la incertesa a la component Tz. La incertesa global disminueix a la primera part de la seq¨u`encia, un cop es calculen millor les rotacions, per`o al mig de la seq¨u`encia la incertesa global augmenta a causa de la incertesa de Tz. Translaci´o llarga amb un vehicle industrial El segon experiment utilitza les dades que es van recollir en una experi`encia realitzada en el magatzem d’una f`abrica en un ambient real, presentada ja al cap´ıtol 2.3.1. El vehicle portapalets robotitzat que es va emprar disposava d’un l`aser de posicionament i s’han utilitzat els resultats del posicionament l`aser per comparar-los amb els del moviment estimat per l’algorisme de visi´o. Per obtenir resultats m`etrics va ser necessari calibrar la c`amera i calcular la dist`ancia inicial a l’objecte amb el l`aser. Es va seleccionar com a objecte un tauler d’informaci´o, i es va mesurar que la dist`ancia inicial entre la c`amera i el tauler era de 7700 mm. L’experiment consta d’una aproximaci´o de 3500 mm amb una lleugera oscil·laci´o lateral. Tres de les imatges de la seq¨u`encia es poden veure a la figura 5.11 (reprodu¨ıda de la figura 2.6): a la posici´o inicial, a meitat de la seq¨u`encia i a la posici´o final. L’an`alisi dels resultats del moviment ja s’ha presentat a 105 5. Estudi de la precisi´o 0 50 100 150 200 −50 0 50 100 150 200 250 imatge x (a) Tx 0 50 100 150 200 −50 −40 −30 −20 −10 0 10 imatge y (b) Ty 0 50 100 150 200 −4000 −3000 −2000 −1000 0 1000 imatge z (c) Tz 0 50 100 150 200 −40 −20 0 20 40 imatge Rxφ (d) Ry Figura 5.12: Components de moviment recuperades per l’experiment amb un vehicle portapalets. La l´ınia cont´ınua representa el valor del moviment (en mil·l´ımetres per a les translacions i graus per a la rotaci´o) i les l´ınies de punts s´on les fites 2σper a la seq¨u`encia sencera. la secci´o 2.3.1, on tamb´e s’ha utilitzat un espai de forma redu¨ıt de 4 graus de llibertat. Aqu´ı es presenta la covari`ancia per a cada estimaci´o del moviment. La figura 5.12 mostra els resultats obtinguts. Es pot observar que la incertesa a la component Txaugmenta quan la dist`ancia entre el contorn i el centre de la imatge tamb´e augmenta. Aix`o s’ha explicat a la secci´o 5.4.1 i ´es degut a la no-satisfacci´o de les suposicions del model de c`amera af´ı. Tamb´e s’obt´e una translaci´o en la direcci´o Ty. Com ja s’ha explicat anteriorment (secci´o 2.3.1), aix`o ´es causat per desalineacions entre els sistemes de refer`encia de la c`amera i del robot. Com passa per a la component Tx, la incertesa de Tyaugmenta quan augmenta la dist`ancia del contorn al centre de la imatge, per`o en aquest cas els valors s´on m´es petits i aquest efecte no es veu f`acilment. 106 5.5 Experiments amb seq¨u`encies reals 0 50 100 150 200 0 50 100 150 200 250 300 imatge desviació típica Tx Ty Tz Ry (a) Desviacions t´ıpiques 0 50 100 150 200 0 2 4 6 8 10x 104 imatge traça (b) Tra¸ca Figura 5.13: (a) Desviacions t´ıpiques computades amb la UT, i (b) tra¸ca de la matriu de covari`ancia. Com era d’esperar, la incertesa en la translaci´o Tzdisminueix a mesura que el robot s’acosta a l’objecte. Desafortunadament, en aquest experiment les rotacions eren molt petites i l’algorisme no ha estat capa¸c de recuperar-les. Conseq¨uentment, la incertesa aproximada per a aquesta component ´es molt gran (vegeu la figura 5.12(d)). Es representen les desviacions t´ıpiques de les components del moviment i la tra¸ca de la matriu de covari`ancies a la figura 5.13. Com en el cas anterior, la tra¸ca est`a dominada per la incertesa de Tz. Es pot observar com varia la desviaci´o est`andard de la component amb dist`ancia. Comparat amb l’experiment previ, en qu`e la dist`ancia inicial era de 500 mm i la desviaci´o t´ıpica estava entre 20 i 25, la precisi´o en l’estimaci´o de Tzi la seva desviaci´o t´ıpica s´on similars, ja que els valors de desviaci´o estan entre 300 i 100 per a dist`ancies des de 7700 mm fins a 3500 mm. En resum, en aquesta secci´o experimental s’ha mostrat que la incertesa en la recuperaci´o del moviment propi es pot calculat en temps real. Dissenyant un algorisme que explota aquesta capacitat, s’ha analitzat la precisi´o de l’enfocament proposat en la pr`actica, i s’ha arribat a la conclusi´o que s’obt´e al voltant del 3% d’error per a traject`ories llargues. D’aquesta manera, sembla que l’algorisme d’estimaci´o del moviment propi proposat pot ser utilitzat en vehicles portapalets per a operacions de transfer`encia en qu`e no cal una precisi´o elevada, aprofitant que no cal preparar l’entorn amb marques artificials, en combinaci´o amb el posicionament l`aser, m´es prec´ıs en operacions de c`arrega i desc`arrega [2]. 107 6. La visi´o activa: profunditat a partir del zoom utilitzen el model de c`ameres de lent gruixuda, que ´es m´es acurat, ja que imita el proc´es de canvi de dist`ancia focal. ´ Es interessant la correspond`encia que estableixen entre un model de lent gruixuda i una configuraci´o equivalent amb el model estenopeic. Per obtenir bones dades de reconstrucci´o, els cal un proc´es de calibratge molt acurat, que inclou par`ametres intr´ınsecs (amb distorsi´o radial) i extr´ınsecs. Estaven for¸cats a utilitzar una c`amera amb lents de molta qualitat, el que s’anomena una c`amera axial, ja que suposaven que l’eix `optic era estable durant tota la seq¨u`encia en qu`e es feia zoom. Rodin i Ayache [115] van introduir un m`etode de calibratge que no exigeix una c`amera axial f´ısica. Se serveixen d’un m`etode de rectificaci´o geom`etric per posar en correspond`encia totes les imatges d’una seq¨u`encia, per`o el m`etode que proposen no t´e en compte les distorsions, i a m´es la base de triangulaci´o que s’utilitza ´es molt petita (nom´es 50 mm). M´es tard, Lavest et.al. [83] van proposar un m`etode de reconstrucci´o impl´ıcit que utilitza un procediment de calibratge geom`etric basat en dos patrons. Originalment, el m`etode va ser desenvolupat per Martins et.al. [95] per resoldre el problema de retroprojecci´o, i Gremban et.al. [61] en van estendre l’´us per incloure tamb´e una soluci´o al problema de la projecci´o. La idea ´es trobar, sense cap model de c`ameres expl´ıcit, el raig en l’espai que defineix la l´ınia de mira d’un p´ıxel donat. Per calibrar, Lavest et.al. van utilitzar una taula microm`etrica per traslladar el patr´o de calibratge, ja que el m`etode de reconstrucci´o que proposen exigeix un proc´es de calibratge amb un posicionament del patr´o d’alta precisi´o. L’algorisme considera que es pot triangular un nou punt en la imatge,2que cal trobar amb molta precisi´o, amb les dades de calibratge per trobar la localitzaci´o 3D del punt. Aquest m`etode t´e els avantatges de tenir en compte totes les distorsions, el despla¸cament del centre `optic produ¨ıt en fer zoom, i de no exigir l’estimaci´o dels par`ametres intr´ınsecs de la c`amera. Una cr´ıtica que sovint rep [11,106] ´es que no t´e en compte els efectes de desenfocament que apareixen en algunes situacions quan es fa zoom. Precisament, el desenfocament s’ha fet servir tamb´e per estimar la profunditat, tant activament actuant sobre el focus de la c`amera, com aprofitant el mecanisme d’autofocus de la c`amera per deduir la profunditat [59]. El problema d’aquest tipus d’enfocament ´es que per evitar el problema d’haver de calibrar amb totes 2Localitzat manualment a [83] i per mitj`a d’un algorisme iteratiu a [43]. 114 6.2 Encara ´es v`alid el model de c`amera estenopeica? les dist`ancies focals possibles nom´es permet un nombre molt petit de nivells de zoom. El cap´ıtol segueix de la manera seg¨uent. A la secci´o 6.2 es presenten diversos models de c`ameres que s’han fet servir per modelar el zoom. A la secci´o 6.3 es mostren els efectes sobre la imatge de fer zoom i es fa una petita discussi´o sobre les distorsions que apareixen. L’espai de deformacions afins redu¨ıt que es fa servir per modelar el moviment indu¨ıt per zoom es presenta a la secci´o 6.4. A la secci´o 6.5 es presenta l’algorisme proposat de calibratge i el m`etode per inferir la profunditat. La secci´o 6.6 es dedica a presentar alguns experiments realitzats amb imatges reals preses des d’un robot m`obil. Finalment, a la secci´o 6.7 es poden trobar les conclusions i algunes idees sobre l’aplicabilitat de l’algorisme en altres treballs actuals que requereixen el coneixement de la profunditat inicial. 6.2 Encara ´es v`alid el model de c`amera estenopeica? Fins al moment s’ha considerat que el model de lents estenopeic era suficientment adequat per modelar el funcionament de la c`amera. Per`o, quan s’introdueix el zoom al sistema de visi´o, es fan variar els par`ametres interns de la c`amera i cal revisar si el model de lents estenopeic encara ´es adequat per modelar la nova c`amera. Una `optica d’una c`amera generalment ´es un mecanisme que inclou diverses lents amb propietats diferents. En el camp de la visi´o artificial, generalment es consideren quatre models de lents diferents: estenopeic, de lent fina, de lent gruixuda i geom`etric [56]. El model estenopeic ´es el m´es simple i, clarament, tamb´e el m´es utilitzat [51,62,92]. En aquest model s’assumeix que tots els rajos passen per un sol punt, el punt focal. Pel que fa a la c`amera, es pot modelar com una projecci´o perspectiva o b´e af´ı, que en les seves versions calibrades i no calibrades donen lloc a diferents matrius de projecci´o. En general, ´es inadequat per modelar una c`amera amb zoom, tot i que s’han proposat diversos algorismes per calibrar una c`amera amb zoom amb aquest model [42]. ´ Es ben conegut que es pot utilitzar un model de lent estenopeic per modelar una c`amera amb zoom si l’algorisme considera que la dist`ancia entre l’objecte i el pla de projecci´o no ´es un par`ametre fix [83,84]. El segon model ´es el model de lent fina, que assumeix, com el seu nom indica, una lent infinitament fina. Aquesta lent es modela a partir d’un pla. Els rajos que incideixen 115 6. La visi´o activa: profunditat a partir del zoom sobre la lent amb un angle determinat surten amb l’angle canviat. Amb aquest model es tenen en compte efectes com la profunditat de camp, que no es poden modelar amb el model estenopeic, per`o s’ha demostrat que no ´es adequat per modelar c`ameres amb zoom [84]. El tercer model s’anomena de lent gruixuda. En aquest model es representa la lent de la c`amera amb dos plans, els anomenats plans principals [69]. Els rajos de llum incideixen en el primer pla, viatgen paral·lels a l’eix `optic fins al segon pla i surten amb un angle igual al d’incid`encia. Tots els rajos provinents d’un mateix punt incideixen en llocs diferents i amb angles diferents sobre el primer pla, i despr´es de sortir per punts diferents del segon pla i amb angles diferents entre ells es troben en un sol punt. Com es pot veure, depenent d’on es col·loca la retina s’obt´e una imatge m´es o menys enfocada del punt. ´ Es molt interessant la correspond`encia que es pot establir entre configuracions de lents amb el model de lent gruixuda i el seu equivalent amb el model estenopeic [84]. El darrer model ´es el model geom`etric. ´ Es el m´es complet de tots i tamb´e el m´es dif´ıcil d’obtenir, ja que intenta modelar tot el conjunt de lents i mecanismes que formen l’`optica de la c`amera. Quan es fa zoom es produeixen diversos moviments relatius entre les diferents lents que componen l’`optica, i per tant, per poder utilitzar aquest model, cal con`eixer molt acuradament com est`a dissenyada la lent. Actualment hi ha diversos paquets de programari que ajuden tant a dissenyar `optiques com a modelar-les, per`o obtenir informaci´o acurada per generar un model ´util ´es dif´ıcil. ´ Es el model menys utilitzat en visi´o artificial. Un cop presentats els diferents models cal veure m´es detalladament com es comporta el model utilitzat fins ara, l’estenopeic, quan es t´e una c`amera amb zoom.´ Es ben conegut que quan es fa zoom canvia tant la dist`ancia focal com el punt principal (o focus d’expansi´o). El canvi de punt principal segons la dist`ancia focal es pot mesurar f`acilment, i dep`en del proc´es de fabricaci´o i de la qualitat de la lent. A la figura 6.1(a) es pot veure el model estenopeic d’una c`amera amb dues dist`ancies focals diferents si es considera que en canviar la dist`ancia focal de f1af2nom´es canvia la posici´o del pla principal. Naturalment es tracta d’una figura err`onia, per`o sovint ´es la idea que es t´e d’un canvi de dist`ancia focal. Aquest error prov´e de la convenci´o de posar el pla principal davant del centre de projecci´o. Si ´es fa a l’inrev´es i el pla de 116 6.2 Encara ´es v`alid el model de c`amera estenopeica? projecci´o queda fix, el que es mou en realitat ´es la lent que es representa pel punt de projecci´o, i el model estenopeic corresponent ´es el que es pot veure a la figura 6.1(b). Pel que fa al control dels mecanismes d’orientaci´o i zoom de la c`amera, els algorismes que es proposaran m´es endavant (7) utilitzen resultats parcials de l’algorisme de seguiment per generar les noves posicions. Es tracta d’algorismes en lla¸c tancat, i at`es que nom´es es consideren els canvis en la projecci´o per al control, es pot continuar fent servir el model estenopeic. En canvi, l’algorisme de recuperaci´o del moviment propi que s’ha proposat al cap´ıtol 2nom´es t´e en compte el canvi de dist`ancia focal entre dues posicions de zoom diferents, per`o no preveu que el centre `optic tamb´e varia en una c`amera amb zoom. En conseq¨u`encia, cal saber que si no es canvia de model de c`amera s’introdueix un factor d’escalat addicional a la informaci´o del moviment propi. Cal diferenciar clarament entre la component de rotaci´o i la de translaci´o de la posa. Les rotacions no queden afectades en utilitzar aquest model [87], i nom´es les translacions, i sobretot Tz, queden afectades pel despla¸cament no modelat del centre `optic. Ara b´e, aquest escalat t´e molt poca influ`encia en les condicions de visualitzaci´o del model de perspectiva d`ebil. Els experiments realitzats per Tordoff [135] amb dues c`ameres amb zoom diferents mostren que la mida relativa d’un objecte en la imatge a mesura que es canvia la dist`ancia focal ´es gaireb´e id`entica a l’esperada en un model estenopeic per a dist`ancies focals curtes. Per a dist`ancies focals llargues, la difer`encia augmenta a mesura que augmenta la dist`ancia focal. Per`o si la dist`ancia de la c`amera a l’objecte ´es gran, el model estenopeic s’ajusta millor als valors obtinguts, de manera que l’error ´es molt menor. Els errors observats s´on prou petits per permetre, per exemple, calibrar una c`amera amb zoom que nom´es gira [64], on es considera que no hi ha translaci´o. Si calgu´es modelar m´es adequadament la c`amera amb zoom, caldria utilitzar el model de lent gruixuda, que ´es millor que el de lent prima. Per implementar el model geom`etric caldria tenir informaci´o molt precisa de la construcci´o de la lent, i el model resultant seria molt cost´os i v`alid ´unicament per a aquella `optica. En el model de lent gruixuda la dificultat rau a determinar la posici´o correcta dels plans conjugats que representen la lent. Aquesta dist`ancia hauria de poder-se mesurar en un proc´es de calibratge [135]. Un cop trobats es pot calcular el model corresponent de c`amera 117 6. La visi´o activa: profunditat a partir del zoom x1 x2 f1 f2 Tz (a) Model erroni d’una c`amera que canvia la dist`ancia focal f1 f2 x2 x1 Tz1 Tz2 (b) Model estenopeic equivalent a una c`amera que varia la dist`ancia focal Figura 6.1: Model estenopeic erroni i model correcte d’una c`amera en qu`e varia la dist`ancia focal. Com es pot veure, no nom´es canvia la dist`ancia focal, sin´o que tamb´e canvia el centre de projecci´o. En realitat, tamb´e canvia el punt principal (que a vegades s’anomena focus d’expansi´o), per`o aquest efecte no es mostra a la figura. estenopeica i, per tant, no caldria definir un nou algorisme de recuperaci´o del moviment propi, ja que es podrien fer servir les mateixes equacions desenvolupades per al model estenopeic. Malgrat tot, at`es que fins ara no s’ha disposat de cap informaci´o sobre els par`ametres de calibratge de la c`amera i que tampoc es coneix la dist`ancia inicial ni cap caracter´ıstica de l’objecte, les components de translaci´o de la posa computada han estat sempre valors relatius (com ´es t´ıpic en visi´o monocular), escalats per un factor desconegut. No sembla, per tant, un gran inconvenient introduir un factor d’escalat addicional, i encara m´es si se sap que aquest factor t´e molt poca influ`encia. 6.3 Cal considerar el efectes de les distorsions en les lents? Un altre dels efectes `optics que poden apar`eixer en modificar la dist`ancia focal de la c`amera ´es la distorsi´o radial.3Generalment, modelar la distorsi´o radial en lents que fan zoom ´es bastant complicat. La relaci´o entre la dist`ancia focal i la distorsi´o generalment 3No tant pel fet de modificar la dist`ancia focal com pel fet que ara el robot pot aproximar-se molt m´es a l’objecte sense que la projecci´o d’aquest surti de la imatge. 118 6.3 Cal considerar el efectes de les distorsions en les lents? no ´es simple. Tanmateix, hi ha alguns intents de modelar aquesta distorsi´o per a casos particulars [33]. En els sistemes de c`amera-lent comuns la distorsi´o de la projecci´o de l’objecte en el pla de la imatge es produeix quan la dist`ancia es molt curta. Un tractament m´es general dels efectes de distorsi´o, aberraci´o, i les seves causes i conseq¨u`encies es pot trobar a [20]. La distorsi´o generalment s’expressa com el despla¸cament d’un punt de la imatge respecte de la dist`ancia radial al centre de distorsi´o [20], i per aix`o moltes vegades s’anomena distorsi´o radial. Generalment, el centre de distorsi´o i el centre de projecci´o s´on molt propers. Per avaluar els efectes de la distorsi´o s’han pres diverses imatges d’un patr´o de calibratge en diferents configuracions (figura 6.2). Quan la c`amera est`a frontoparal·lela a l’objecte es poden apreciar millor les distorsions radials.4Com es pot veure a la figura 6.2(a), on la dist`ancia entre c`amera i objecte era de tant sols 30 cm, les l´ınies horitzontals que passen prop del centre de la imatge s´on rectes, mentre que les m´es allunyades s´on corbades. El mateix es pot dir de les l´ınies verticals. La figura 6.2(c) es una imatge presa amb la c`amera m´es allunyada. Per tal que la projecci´o sigui molt semblant el zoom de la c`amera s’ha variat, de manera que s’ha augmentat la dist`ancia focal. Com es pot observar, amb la c`amera allunyada (de fet es va col·locar a tant sols 180 cm) els efectes de distorsi´o s´on molt menors, gaireb´e inapreciables. Quan la c`amera no est`a en posici´o frontoparal·lela respecte de l’objecte, els efectes de perspectiva s´on molt m´es importants que no pas els efectes de distorsi´o. Aix`o es pot observar comparant les figures 6.2(b) i6.2(d). Quan la c`amera est`a realment molt aprop (6.2(b)) el que s’observa clarament ´es l’efecte de fuga de la perspectiva. Si la c`amera est`a m´es lluny (en aquest cas, de fet, a nom´es 180 cm) el efectes de perspectiva s´on molt menors. Com s’ha vist, els efectes de la distorsi´o radial s´on menyspreables, sobretot si es tenen en compte les condicions de visualitzaci´o de perspectiva d`ebil. Tanmateix, ´es possible analitzar-ne els efectes potencials sobre l’extracci´o del moviment. Primer de tot, cal tenir en compte que el contorn de l’objecte s’ajusta en cada nova imatge segons 4En una escena general es pot observar f`acilment la distorsi´o radial si es disposa d’un objectiu d’ull de peix (de dist`ancia focal molt curta). Per aix`o cal una lent especial. En una c`amera amb una lent normal per observar l’efecte de la distorsi´o cal acostar molt la c`amera a l’objecte. Com es pot veure, es tracta de reduir la proporci´o entre dist`ancia focal i dist`ancia a l’objecte. 119 6. La visi´o activa: profunditat a partir del zoom (a) dist=30 cm, zoom=64, frontopalal·lel (b) dist=30 cm, zoom=64, no frontoparal·lel (c) dist=180 cm, zoom=1120, frontopalal·lel (d) dist=180 cm, zoom=1120, no frontoparal·lel Figura 6.2: Imatges en qu`e canvia la dist`ancia i el zoom i que permeten observar els efectes perspectius i de distorsi´o radial. Si la dist`ancia ´es curta (a), es poden observar els efectes de la distorsi´o radial, mentre que si l’objecte est`a allunyat (c), aquests efectes s´on menys evidents. Si la c`amera no est`a frontoparal·lela a l’objecte (b) per a dist`ancies curtes, s’observa principalment l’efecte de perspectiva, mentre que si l’objecte est`a una mica m´es allunyat (d), aquest efecte ´es molt m´es subtil. 120 6.4 Reducci´o de l’espai de forma el model definit en la primera imatge. Aix`o fa que el vector de forma que parametritza la deformaci´o del contorn sigui fins a cert punt immune a petits efectes, tant de distorsi´o de la imatge com, fins i tot, de perspectiva. 6.4 Reducci´o de l’espai de forma Coneixent que el moviment que es provoca en la imatge indu¨ıt nom´es per canvis en el zoom ´es restringit, es pot reduir l’espai de forma presentat a la secci´o 2.2.2. Per construir el nou espai de deformaci´o cal tenir en compte dos aspectes. Primer, l’efecte de fer zoom en un factor ρ´es el de traslladar un punt a la imatge xal llarg de la l´ınia que va des del punt principal de la c`amera v0al punt x′=ρu + (1 −ρ)v0. A efectes pr`actics, es pot explicar multiplicant la matriu de calibraci´o de la c`amera que correspon a la primera imatge pel factor ρ. En l’espai de forma redu¨ıt que es vol construir, es pot introduir com un grau de llibertat amb el vector Qx Qy(6.1) que codifica directament l’escala de l’afinitat. Segon, tal com ja s’ha anunciat anteriorment (cap´ıtol 6.2), l’eix `optic en un c`amera que fa zoom no ´es constant [84], i aix`o t´e l’efecte de canviar la posici´o del punt principal cada vegada que es modifica la dist`ancia focal. Per poder modelar aquests moviments cal introduir translacions laterals en l’espai de deformaci´o que es dissenya.5La matriu de forma resultant ´es Wzoom =1 0,0 1,Qx Qy,(6.2) i el vector de forma ´es S= [tx, ty, ρ].(6.3) 6.5 Estimaci´o de la profunditat a partir del moviment indu¨ıt pel zoom Tal com es mostrar`a, l’algorisme que es presenta comparteix els avantatges principals de l’algorisme de calibratge de dos patrons [83,95]: no cal estimar els par`ametres intr´ınsecs 5Es pot derivar matem`aticament de manera semblant a com es fa a [97]. 121 6. La visi´o activa: profunditat a partir del zoom de la c`amera, i no cal fer cap suposici´o sobre l’estabilitat de l’eix `optic entre les diferents dist`ancies focals. Justament, considerar que el punt principal, i per tant l’eix `optic, no ´es estable ´es el que ens permet obtenir l’estimaci´o de profunditat. Cal observar que, en el model estenopeic equivalent a una c`amera que fa zoom, no es conserva ni la direcci´o de projecci´o ni tampoc el centre de projecci´o [87]. Per dur a terme el desenvolupament nom´es se suposa que l’eix `optic varia sempre de la mateixa manera entre dues dist`ancies focals determinades [147]. Tamb´e se suposa que la relaci´o entre dues vistes de la mateixa escena captada per una c`amera est`atica que fa zoom es pot aproximar acuradament per una homot`ecia planar (un canvi d’escala i una translaci´o). Tal com s’ha explicat anteriorment, el factor d’escala (´es a dir, la ra´o de l’homot`ecia) representa el canvi de dist`ancia focal, mentre que la translaci´o explica el despla¸cament del punt principal a causa de la no-estabilitat de l’eix `optic. A m´es, l’algorisme proposat supera una de les dificultats essencials dels algorismes existents: funciona correctament en condicions de visualitzaci´o af´ı. A m´es, des d’un punt de vista computacional, ´es un algorisme de calibratge eficient: evita els sovint costosos c`alculs de minimitzaci´o,6ja que les dades d’entrada s´on les raons de les tres homot`ecies planars. Amb l’algorisme que es presenta, l’estimaci´o d’aquestes raons dep`en de la restricci´o de l’espai de forma af´ı, que parametritza la deformaci´o de l’objecte projectada en la imatge (vegeu la secci´o 6.4), que tant es pot calcular amb les dades provinents d’un m`etode de seguiment d’un contorn actiu [17] com amb les correspond`encies de punts provinents, per exemple, d’un m`etode basat en transfer`encia af´ı [136]. 6.5.1 Algorisme de calibratge L’algorisme de calibratge geom`etric que es proposa es compon dels passos seg¨uents. Primer se situa un objecte planar a certa dist`ancia z1dins del camp de visi´o d’una c`amera amb un zoom A. Llavors, la c`amera canvia el zoom aB. El moviment indu¨ıt pel zoom es pot parametritzar amb un vector de forma (6.3) en qu`e el tercer par`ametre del vector ´es la ra´o ρ1de l’homot`ecia h1que explica aquestes dues vistes (del zoom A al zoom B). Aquest proc´es es repeteix a certa dist`ancia z2de la c`amera: un objecte 6Es pot considerar que el pas previ per trobar el vector de forma ´es una minimitzaci´o, per`o computacionalment el cost ´es molt redu¨ıt ja que nom´es cal trobar la pseudoinversa d’una matriu (nombre de punts de control ×mida de l’espai de forma). 122 6.5 Estimaci´o de la profunditat a partir del moviment indu¨ıt pel zoom planar (pot ser diferent del precedent) ´es captat per la c`amera que fa un zoom, del zoom Aal zoom B, i es calcula un segon vector de forma, que representa l’homot`ecia h2que explica les vistes inicials i finals, i s’obt´e la ra´o ρ2. Si la c`amera veu un objecte planar nou (a una dist`ancia desconeguda z), es pot prendre una imatge en zoom Ai fer zoom fins al zoom B. Llavors, es pot computar un nou vector de forma (i la seva ra´o ρ) que explica la vista inicial i final. El que es demostrar`a m´es endavant ´es que la ra´o entre les profunditats z2−z1 z−z1es pot obtenir a partir de la ra´o entre les homot`ecies anteriors, aplicant ρ(ρ2−ρ1) ρ2(ρ−ρ1)D’aquesta manera s’obt´e una estimaci´o directa de la profunditat desconeguda z, sense necessitat de con`eixer cap par`ametre addicional de la c`amera. A m´es, s’evita l’´us tedi´os d’instruments m`etrics, com ara una taula microm`etrica, en el proc´es de calibratge, ja que l’orientaci´o relativa entre els plans que contenen els dos objectes de calibratge no ´es rellevant. Tampoc no hi ha cap necessitat d’utilitzar patrons de calibraci´o, i ´es per aix`o que els dos objectes utilitzats en el calibratge poden ser objectes familiars en l’escena (com una porta, una finestra, un tauler d’anuncis...). Es proposa superar el problema de computar acuradament la ra´o de l’homot`ecia que explica les vistes inicial i final d’una c`amera que fa un zoom reduint la dimensi´o del vector de forma, que codifica la relaci´o af´ı entre les dues vistes (vegeu la secci´o 6.4). 6.5.2 Com es pot inferir la profunditat Ara es mostra, tal com ja s’ha anunciat anteriorment, com s’utilitza la no-estabilitat de l’eix `optic entre les diferents dist`ancies focals per inferir l’estimaci´o de la profunditat. Suposeu que la direcci´o de l’eix `optic quan la dist`ancia focal ´es Adifereix lleugerament de la direcci´o de l’eix `optic quan la dist`ancia focal ´es B. Llavors, hi ha un raig `optic la la imatge amb zoom Aque passa per un punt de l’imatge xla direcci´o del qual ´es la mateixa que la direcci´o de l’eix `optic aBa la imatge amb zoom B(vegeu la figura 6.3). Aquest raig l´es proper a l’eix `optic en la imatge amb zoom A, i talla els plans de calibratge en els punts X1iX2, i el pla on es troba l’objecte en el punt X. Per tant, la ra´o simple d’aquests punts (X1, X2, X) = d(X1,X2) d(X1,X)(on d(Y1, Y2) ´es la dist`ancia entre dos punts Y1iY2) ´es una estimaci´o de la ra´o de les profunditats z2−z1 z−z1. 123 6. La visi´o activa: profunditat a partir del zoom Taula 6.1: Resultats del segon conjunt d’experiments on s’utilitzen dist`ancies de calibratge diferents i objectes diferents. Exp. ID Cal1 Cal2 Estimat Mesurat 1 240 360 277.6 280 2 321.4 320 3 401.7 400 4 269.8 280 5 240 320 288.2 280 6 357.8 360 7 281.6 280 8 320 400 367.7 360 En aquest experiment es vol mostrar que la codificaci´o del moviment en un espai de forma ´es aplicable tamb´e quan s’utilitzen correspond`encies de punts. Es pot establir una relaci´o entre caracter´ıstiques puntuals extretes d’un objecte i un contorn si es considera la llista de punts com el conjunt de punts de control d’una B-Spline. Com a conseq¨u`encia, el m`etode presentat, que obt´e un parametritzaci´o del moviment, es pot aplicar tamb´e en m`etodes de correspond`encies de punts. Per calibrar s’extreuen manualment quatre punts per a cada imatge dels calaixos, que serveixen per construir el vector de forma corresponent. Per a les imatges del tamboret, en canvi, s’extreuen sis punts, per demostrar que no importa a partir de quants punts s’extreu la parametritzaci´o en vector de forma. Es pot observar que, ja que el m`etode per obtenir el vector de forma multiplicant per la pseudoinversa es pot veure com una minimitzaci´o [17], si es tenen m´es punts es pot obtenir m´es precisi´o. Alguns dels resultats es resumeixen a la taula 6.1. Les columnes etiquetades Cal1 i Cal2 indiquen les dues dist`ancies conegudes amb qu`e s’ha realitzat el calibratge geom`etric, i les altres dues columnes mostren la dist`ancia estimada per l’algorisme presentat i la mesurada manualment. Per als experiments etiquetats 1 i 2, la c`amera est`a situada respectivament a 280 i 320 cm del calaix. Aquestes profunditats estan entre les dues dist`ancies de calibratge (240 i 360 cm), i la profunditat que es computa amb l’algorisme ´es prou correcte en cada experiment. En l’experiment etiquetat 3, la c`amera se situa m´es lluny que la segona dist`ancia de calibratge (fora del rang de calibratge), i la profunditat tamb´e es recobra amb un error petit. Amb aquests par`ametres de cali130 6.7 Conclusions bratge es realitza un quart experiment (numerat 4) utilitzant els sis punts extrets de les imatges dels tamborets. En aquest cas, la profunditat tamb´e es recobra raonablement, encara que pitjor que en els casos previs. En els experiments 5, 6 i 7 el rang de la zona de calibratge s’escur¸ca i s’utilitzen les dist`ancies de calibratge 240 i 320 cm. Quan la dist`ancia est`a dins de la zona de calibratge, com en l’experiment 5, l’error ´es del mateix ordre que en l’experiment previ. En canvi, quan la c`amera est`a situada m´es lluny que la segona dist`ancia de calibratge (experiment 6), la profunditat es recobra correctament, per`o amb m´es error, comparable amb el de l’experiment 3. Aquest ´es un efecte t´ıpic en calibratge geom`etric: la profunditat es recobra correctament dins del rang definit entre la primera i la segona dist`ancia de calibratge, ja que l’algorisme est`a interpolant; fora d’aquesta zona, la profunditat tamb´e es pot inferir, extrapolant la informaci´o, per`o l’error augmenta a mesura que la dist`ancia augmenta. En l’experiment 7 s’utilitzen els punts del tamboret. Finalment, amb l’experiment 8, es prova l’efecte de moure les dues dist`ancies de calibratge m´es lluny. El calibratge es duu a terme amb imatges preses a 320 i 400 cm. Es fa una prova posant la c`amera al mig, i s’obt´e una profunditat correcta. 6.7 Conclusions S’ha presentat un m`etode simple per determinar la dist`ancia d’una c`amera respecte a una fita. La deformaci´o en la imatge provocada quan la c`amera fa zoom es codifica amb un vector de forma de tres graus de llibertat en un espai de forma presentat, on el tercer element correspon a l’escala de l’homot`ecia associada. Aquest simple valor d’escala s’enregistra a cada pas del calibratge. Quan es computa una nova deformaci´o a partir del zoom sobre un objecte, que pot ser diferent, se’n pot comparar l’escala amb les escales de calibratge i, coneixent la profunditat del calibratge, es mostra com es pot deduir la profunditat de l’objecte actual amb una operaci´o simple. Amb els experiments amb imatges reals s’ha demostrat la validesa de l’algorisme. La dist`ancia entre posicions de calibratge determina una zona calibrada on l’algorisme ´es m´es prec´ıs. Fora d’aquesta zona, l’algorisme tamb´e infereix la profunditat, per`o ´es menys prec´ıs a mesura que la dist`ancia augmenta. S’ha mostrat que es pot trobar el 131 6. La visi´o activa: profunditat a partir del zoom vector de forma amb el seguiment de contorns actius, i tamb´e amb algorismes de correspond`encies de punts. En aquest darrer cas, calen un m´ınim de tres correspond`encies de punts per construir l’afinitat, per`o m´es correspond`encies proporcionen una millor estimaci´o del vector de forma. Aqu´ı s’han presentat experiments que utilitzen quatre i sis correspond`encies de punts entre imatges que fan zoom. S’ha demostrat que es pot calcular el vector de forma requerit a partir d’objectes diferents i utilitzant un nombre diferent de correspond`encies de punts. Realitzant els experiments pr`actics s’ha observat que en fer zoom a vegades la projecci´o de l’objecte surt fora de la imatge. Per a prop`osits pr`actics, ´es convenient calibrar amb algunes posicions de zoom diferents per ser capa¸c de trobar un rang de posicions de zoom que contingui l’objecte en les dues imatges i per a la qual es t´e informaci´o de calibratge. El nostre objectiu ha estat principalment eliminar de l’algorisme de moviment propi la incertesa d’escala, com´u en tots els sistemes de visi´o monocular. Per`o aquest m`etode es pot utilitzar tamb´e per a uns altres prop`osits, per exemple, la inicialitzaci´o dels controladors del sistema d’orientaci´o del nostre sistema de visi´o activa (que es mostra al cap´ıtol 7). Els experiments amb el control del dispositiu mostren que la precisi´o obtinguda ´es prou acurada per inicialitzar els controladors en una bona zona de resposta. A [2] es calculava la dist`ancia inicial amb un l`aser, i a [1] amb un patr´o de calibratge. Alguns altres algorismes es podrien beneficiar de l’estimaci´o de la dist`ancia inicial d’una fita donada. Ens permetem enumerar-ne alguns. Davison [39] calcula la profunditat d’una fita en visi´o monocular utilitzant refinaments successius amb un filtre de part´ıcules. Per adquirir l’escala de l’escena en la primera imatge s’utilitza un objecte conegut. L’algorisme presentat es podria utilitzar per canviar l’objecte conegut per qualsevol objecte de l’escena. Recentment, Caballero et. al. [25] han presentat un od`ometre visual monocular per a vehicles aeris. Proposen mesurar la dist`ancia entre la c`amera i els diversos objectes utilitzats en els experiments amb un sonar o un sensor l`aser, per`o finalment en els experiments que presenten ho fan manualment. Sola [130] proposa resoldre el problema de la inicialitzaci´o de la profunditat amb una aproximaci´o del filtre de suma gaussi`a, i Jensfelt et. al. [71] proposen excloure directament del 132 6.7 Conclusions proc´es de SLAM8els trets per als quals la profunditat no ha estat determinada. Tots aquests m`etodes no poden extreure informaci´o significativa quan hi ha poca disparitat entre caracter´ıstiques, per exemple en moviments d’aproximaci´o de robots que veuen objectes distants. ` Obviament, per a mapes tradicionals basats en punts no ´es pr`actic realitzar el reposicionament del zoom cada vegada que cal introduir un nou punt al mapa. Tanmateix, l’algorisme presentat ´es ´util per a les situacions en qu`e cal con`eixer una profunditat de refer`encia, com les esmentades anteriorment. 8SLAM (Simultaneous Localization and Mapping) ´es el procediment pel qual es construeix un mapa i s’hi localitza el robot, tot al mateix temps. 133 Cap´ıtol 7 Estimaci´o del moviment en el context de la visi´o activa Com si fos versemblant que la Natura, tan sol·l´ıcita a vetllar pels mosquits i `adhuc per les herbes i per les floretes, s’hagu´es endormiscat nom´es en el cas de l’home, obligant-lo a refiar-se de les ci`encies, que Theuth, divinitat hostil al g`enere hum`a, invent`a per emmenar-lo a la total perdici´o! Erasme de Rotterdam, Elogi de la follia XXXII. (Jaume Molina, MOLU 10, Edicions 62, 1982.) As if this had the least face of truth, that Nature that was so solicitously watchful in the production of gnats, herbs, and flowers should have so slept when she made man, that he should have need to be helped by sciences, which that old devil Theuth, the evil genius of mankind, first invented for his destruction. Desiderius Erasmus, The Praise of Folly. (Translated by John Wilson, 1668, at Guttenberg project.) Extracte Una de les limitacions m´es importants de l’algorisme de recuperaci´o del moviment propi ´es que cal que el contorn sigui completament visible, en condicions de perspectiva d`ebil, durant tota la seq¨u`encia. Aprofitant els avantatges de la visi´o activa, en aquest cap´ıtol es posen les bases per superar aquesta limitaci´o, d’una banda proveint la c`amera de zoom, que permetr`a compensar la translaci´o del robot al 7. Estimaci´o del moviment en el context de la visi´o activa llarg de l’eix `optic, i de l’altra, controlant la direcci´o de visualitzaci´o amb un dispositiu que permet orientar la c`amera. Els algorismes de control que es proposen, tant per al mecanisme de zoom com per al de capcineig i guinyada, minimitzen un senyal d’error obtingut directament de mesures en la imatge, sense que calgui m´es informaci´o 3D que l’estimaci´o de la dist`ancia inicial (que es pot obtenir amb l’algorisme presentat al cap´ıtol anterior). Un altre avantatge ´es que el senyal d’error s’obt´e com un resultat parcial de l’algorisme d’estimaci´o del moviment, i per tant no afegeix cap c`arrega de c`omput. Els resultats experimentals validen aquesta extensi´o de l’algorisme d’estimaci´o del moviment que possibilita la visi´o activa. 7.1 Introducci´o L’algorisme de recuperaci´o del moviment propi presentat requereix que la projecci´o de l’objecte estigui sempre en la imatge. Amb una c`amera passiva aix`o ´es sovint massa restrictiu, ja que els moviments que pot realitzar el robot es limiten gaireb´e nom´es a aproximacions i recessions de l’objectiu. Una de les solucions m´es prometedores que s’ha considerat ´es proporcionar capacitat d’orientaci´o a la c`amera i dissenyar un algorisme de control per conservar la projecci´o de l’objectiu centrada en la imatge (o com a m´ınim dins de la imatge) en la seq¨u`encia sencera. Un dels problemes principals que presenta l’algorisme de control ´es que caldr`a aplicar guanys diferents depenent de la dist`ancia des de la c`amera fins a l’objectiu. En el camp de la visi´o activa, seguint la inspiraci´o biol`ogica, s’han fet diversos treballs per emular en plataformes artificials dos dels reflexos oculars presents en els organismes vius: el moviment sac`adic i el seguiment suau [114]. El moviment sac`adic implica un moviment r`apid que canvia sobtadament el punt de fixaci´o. El seguiment suau ´es un moviment dels “ulls” que permet fer el seguiment continu d’un objecte mentre es mou, de manera que sempre estigui centrat en la imatge. Els apartats seg¨uents es desevolupen centrant l’inter`es en aquest darrer moviment. Una c`amera activa t´e un grau de llibertat addicional, comparat amb l’ull biol`ogic: el zoom.1Tot i que sembla una capacitat molt interessant en un sistema de visi´o activa els treballs fets fins ara s’ocupen o b´e del zoom o b´e del moviment d’orientaci´o, per`o poques vegades del moviment conjunt. Una de les causes principals ´es que les caracter´ıstiques que ressalten en una imatge obtinguda amb un zoom determinat no tenen perqu`e ser 1L’acomodaci´o, el moviment de l’ull per enfocar objectes a dist`ancies diferents, es pot identificar amb el mecanisme d’enfocament de les lents, per`o el moviment del zoom no t´e referent biol`ogic. 136 7.1 Introducci´o salients en una segona imatge obtinguda amb un valor de zoom diferent. En general, aquestes caracter´ıstiques no s´on invariants a canvis de zoom. Una altra de les causes ´es que el canvi de zoom canvia els par`ametres de calibratge de la c`amera i complica els algorismes de calibrate i autocalibratge. Finalment, el control d’un mecanisme de capcineig i guinyada quan hi interv´e el zoom tamb´e ´es m´es complicat. ´ Es per aix`o que molts dels treballs amb c`amera activa nom´es tenen en compte els moviments d’orientaci´o de la c`amera i no el zoom [40,105,114], o b´e els algorismes proposats s´on estratificats, separant clarament el moviment del zoom i el de l’orientaci´o [129]. Des del punt de vista del control sovint s’ha tractat diferent el moviment sac`adic i el seguiment suau. L’estrat`egia ha estat, en general, generar dos algorismes de control diferents i definir un tercer algorisme per canviar entre aquestes dues estrat`egies de control. Generalment no es considera una altra de les caracter´ıstiques biol`ogiques: la resoluci´o de l’ull biol`ogic no ´es uniforme, mentre que la del sensors comercials s´ı que ho ´es (el que s’anomena visi´o foveal).2Encara que s’ha implementat, impl´ıcitament i expl´ıcitament [82,104], a efectes pr`actics la visi´o foveal ´es convenient nom´es en alguns casos [114]. El cap´ıtol s’estructura de la manera seg¨uent. A la secci´o 7.2 s’introdueix l’´us del zoom per compensar la translaci´o del robot, i preservar aix´ı la mida de la projecci´o de l’objecte en la imatge. La funci´o d’error que permet implementar l’algorisme de control es presenta a la secci´o 7.2.1. A la secci´o 7.2.2 es discuteixen diferentes implementacions de l’algorisme de control i quins canvis cal introduir a l’algorisme d’estimaci´o del moviment. Els resultats experimentals es presenten a la secci´o 7.2.3. Els canvis d’orientaci´o de la c`amera es tracten a la secci´o 7.3. Primer s’exposen els diferents m`etodes i es compara la funci´o d’error que es proposa amb la m´es utilitzada normalment (secci´o 7.3.1). A la secci´o 7.3.2 es mostra com, quan es combina el moviment d’orientaci´o amb el control del zoom, la resoluci´o en el pla de l’objecte no canvia. L’algorisme per controlar el capcineig i la guinyada es presenta a la secci´o 7.3.3, i els experiments, realitzats amb un robot m`obil, es presenten a la secci´o 7.3.4. Finalment, les conclusions i treballs futurs s’exposen a la secci´o 7.4. 2Cal esmentar tamb´e els sistemes purament electr`onics, on es pren una regi´o d’inter`es de la imatge, s’expandeix i se serveix com si fos la imatge presa per la c`amera, de manera que d´ona la sensaci´o (o il·lusi´o) que es disposa d’un sistema mec`anic d’orientaci´o [136]. 137 7. Estimaci´o del moviment en el context de la visi´o activa 7.2 Compensant la translaci´o amb el zoom Si s’imagina la situaci´o d’un robot que ha fixat com a objectiu un objecte que ´es davant seu, ´es f`acil veure que el moviment de translaci´o que pot fer sense perdre de vista l’objecte ´es limitat. La projecci´o de l’objecte a la imatge ha de tenir una mida adequada, ni gaire petita ni gaire gran, per tal que l’algorisme de seguiment pugui funcionar. Aix`o implica que la dist`ancia m`axima entre el robot i l’objectiu dep`en dels par`ametres de l’`optica de la c`amera i de la mida de l’objectiu. L’automatitzaci´o del control del zoom ´es una opci´o molt prometedora per a sistemes de visi´o en aplicacions generals i en aplicacions rob`otiques en particular. Desafortunadament, el control del zoom d’una c`amera no ha rebut l’atenci´o que es podria esperar, tenint en compte com enriqueix les compet`encies d’un sistema de visi´o. La possibilitat de canviar la mida de la projecci´o a la imatge d’un objectiu no nom´es permet analitzar objectes a una resoluci´o m´es alta [68,124], sin´o que tamb´e permet millorar el seguiment [64] i, en conseq¨u`encia, l’estimaci´o del moviment 3D i els resultats de reconstrucci´o [118]. L’inter`es m´es gran per al cas que es presenta ´es que modificar activament el par`ametre de zoom permet moviments del robot molt m´es grans del que seria possible amb una c`amera de dist`ancia focal fixa, ja que es pot controlar la mida de la projecci´o de l’objectiu a la imatge perqu`e sigui favorable per a l’algorisme de seguiment. El m´es natural per acomplir aquest objectiu ´es trobar un algorisme que permeti compensar els moviments de translaci´o del robot amb canvis de zoom. Per tant, mesures de l’estil de l’`area ocupada per la projecci´o de l’objecte en la imatge no s´on adequades. Es pot observar a la figura 7.1 com, utilitzant el model estenopeic i les condicions de visualitzaci´o de perspectiva d`ebil, els canvis en la dist`ancia focal provoquen els efectes desitjats: la imatge d’un objecte es pot conservar si es troba la dist`ancia focal f′que neutralitza l’efecte de la variaci´o de dist`ancia Z0−Z′entre la c`amera i l’objecte. S’han proposat estrat`egies diferents per al control del zoom. Fayman. et. al. [52,53] consideren un objectiu planar i un robot que es pot traslladar nom´es al llarg de l’eix `optic. Per obtenir una projecci´o en la imatge de dimensi´o constant proposen una t`ecnica, que anomenen zoom tracking, dirigida a conservar la proporci´o f/Z entre la dist`ancia focal i la dist`ancia a l’objectiu. Fan servir un model de c`amera de lent gruixuda i suposen coneguts de manera precisa els par`ametres de calibratge de la c`amera. 138 7.2 Compensant la translaci´o amb el zoom Figura 7.1: Quan la dist`ancia entre una c`amera i un objecte frontoparal·lel al pla de la imatge canvia de ZaZ′, es pot trobar una nova dist`ancia focal f′que fa canviar el centre de projecci´o de CaC′de manera que la projecci´o de l’objecte al pla de la imatge Rsigui la mateixa. Els autors sostenen que, en un sistema de visi´o activa, les translacions perpendiculars a l’eix `optic es poden estabilitzar amb t`ecniques de registre d’imatges [23], per`o desafortunadament no es proporciona cap soluci´o pel que fa a les rotacions. Les peticions de zoom es calculen amb els components divergents o convergents del flux `optic (´es a dir, nom´es amb mesures en la imatge), o tamb´e utilitzant la profunditat proporcionada per un sensor d’abast (´es a dir, depenent de la informaci´o de l’escena). Tordoff i Murray [135,136] tamb´e encaren el problema de fixar la mida de l’objectiu en la imatge. Consideren el moviment dels robots en general pel que fa a la c`amera, tant el model perspectiu com el model af´ı. Amb el primer model, el model perspectiu, nom´es tracten el cas de c`ameres que fan rotacions pures (com per exemple les c`ameres de seguretat o vigil`ancia). Aix`o es deu al fet que l’algorisme que proposen necessita fer un autocalibratge continu i aquest autocalibratge es fa utilitzant el m`etode d’Agapito et. al. [42], que nom´es funciona en el cas de c`ameres que roten. L’algorisme per generar demandes al zoom que proposen tamb´e conserva la proporci´o f/Z . Els autors identifiquen problemes de l’algorisme quan l’objectiu ´es planar, lluny`a, o en situacions en qu`e els efectes de perspectiva no s´on presents o s´on discrets (comuns en les c`ameres de seguretat o vigil`ancia). Amb el segon model, el model de c`amera af´ı, no cal el procediment d’autocalibratge. 139