Many-to-Many High Order Matching. Applications to Tracking and Object Segmentation

Abstract

La correspondència de característiques és un problema fonamental de la Visió per Computador, que té múltiples aplicacions com el seguiment, la classificació i recuperació d’imatges, el reconeixement de formes i la visió estereoscòpica. En molts àmbits, és útil per representar l’estructura local de les carácterístiques en correspondència, per augmentar la precissió o per fer les correspondències invariants a certes transformacions (afins, homografies, etc...). No obstant això, la codificació d’aquest coneixement requereix complicar el model mitjançant l’establiment de relacions d’ordre alt entre els elements del model, i per tant l’augment de la complexitat del problema d’optimització. La importància de les correspondències molts-a-molts es de vegades ignorada en la literatura. La majoria dels mètodes es limiten a realizar correspondències un-a-un, generalment validant en conjunts de dades sintètiques, o no realistes. En un entorn real, amb variacions d’escala, il.luminació i orientació de l’objecte d’interés, i amb la presència d’oclusions, desordre, i observacions sorolloses, les relacions molts-a-molts son necessàries per aconseguir resultats satisfactoris. Com a conseqüència, trovar la correspondència molts-a-molts més probable, implica un procés complicat d’optimització combinatòria. En aquest treball dissenyem i demostrem algorismes de correspondència que calculen associacions molts-a-molts, i que poden ser aplicats a diversos problemes difícils de resoldre. El nostre objectiu és fer ús de representacios d’ordre alt per millorar el poder expressiu de la correspondència, alhora que ferm possible el procés d’inferència o l’optimització d’aquests models. Al llarg de la tesi, hem utilitzat eficaçment els models gràfics com la nostra representació preferida, ja que proporcionen un marc probabilístic elegant per abordar problemes de predicció estructurada. Hem introdüit un algorisme de seguiment bassat en correspondències que es porten a terme entre els fotogrames d’una sequència de vídeo, per tal de resoldre el problema de segument de fars de cotxes durant la nit. També generalitzem aquest mateix algorisme per resoldre el problema de l’associació de dades aplicat a different escenaris de seguiment. Hem demostrat l’eficàcia d’aquest enfoc en seqüències de vídeo reals i demostrem que el nostre algorisme de seguiment es pot utilitzar per millorar la precisió d’un sistema de classificació de fars de cotxes. A la segona part d’aquest treball, pasem desde correspondències no denses (punts) cap a correspondèencies denses (regions), i introdüim una nova representació jeràrquica d’imatges. Seguidament, fem ús d’aquest model per desenvolupar correspondències molts-a-molts d’ordre alt entre parelles d’imatges. Demostrem que l’ús de models d’ordre alt en comparació amb altres models més senzills no només millora l’exactitud dels resultats, sinó també la velocitat de convergència de l’algorisme d’inferència. Finalment, seguim explotant la idea de correspondència de regions per dissenyar un algorisme de co-segmentació completament no supervisat, que és capaç de competir amb altres mètodes supervisats de l’estat-de-l’art. El nostre mètode supera inconvenients típics d’alguns treballs passats, com evitar la necesitat d’aparences variades al fons de les imatges. La correspondència de regions en aquest cas s’aplica per explotar eficaçment la informació compartida entre les imatges. També extenem aquest treball per dur a terme co-segmentació de vídeos, sent la primera vegada que s’aborda aquest problema.

Feature matching is a fundamental problem in Computer Vision, having multiple applications such as tracking, image classification and retrieval, shape recognition and stereo fusion. In numerous domains, it is useful to represent the local structure of the matching features to increase the matching accuracy or to make the correspondence invariant to certain transformations (affine, homography, etc…). However, ncoding this knowledge requires complicating the model by establishing high-order relationships between the model elements, and therefore increasing the complexity of the optimization problem. The importance of many-to-many matching is sometimes dismissed in the literature. Most methods are restricted to perform one-to-one matching, and are usually validated on synthetic, or non-realistic datasets. In a real challenging environment, with scale, pose and illumination variations of the object of interest, as well as the presence of occlusions, clutter, and noisy observations, many-to-many matching is necessary to achieve satisfactory results. As a consequence, finding the most likely many-to-many correspondence often involves a challenging combinatorial optimization process. In this work, we design and demonstrate matching algorithms that compute many-to-many correspondences, applied to several challenging problems. Our goal is to make use of high-order representations to improve the expressive power of the matching, at the same time that we make feasible the process of inference or optimization of such models. We effectively use graphical models as our preferred representation because they provide an elegant probabilistic framework to tackle structured prediction problems. We introduce a matching-based tracking algorithm which performs matching between frames of a video sequence in order to solve the difficult problem of headlight tracking at night-time. We also generalize this algorithm to solve the problem of data association applied to various tracking scenarios. We demonstrate the effectiveness of such approach in real video sequences and we show that our tracking algorithm can be used to improve the accuracy of a headlight classification system. In the second part of this work, we move from single (point) matching to dense (region) matching and we introduce a new hierarchical image representation. We make use of such model to develop a high-order many-to-many matching between pairs of images. We show that the use of high-order models in comparison to simpler models improves not only the accuracy of the results, but also the convergence speed of the inference algorithm. Finally, we keep exploiting the idea of region matching to design a fully unsupervised image cosegmentation algorithm that is able to perform competitively with state-of-the-art supervised methods. Our method also overcomes the typical drawbacks of some of the past works, such as avoiding the necessity of variate appearances on the image backgrounds. The region matching in this case is applied to effectively exploit inter-image information. We also extend this work to perform co-segmentation of videos, being the first time that such problem is addressed, as a way to perform video object segmentation.