Missing Data Matrix Factorization Addressing the Structure from Motion Problem

Abstract

Aquest treball es centra en la factorització de matrius per obtenir l'Estructura a partir del Moviment (SFM). La idea és descomposar la matriu de trajectòries en la matriu de moviment, que conté la posició relativa càmera-objecte a cada frame, i la matriu de forma, que conté les coordenades 3D dels punts característics. Aquesta factorització es pot obtenir utilitzant que la matriu de trajectòries té un rang reduït. En particular, si les trajectòries pertanyen a un únic objecte rígid, la matriu té com a molt rang 4. Tot i que s'han proposat diverses tècniques per tractar el problema de les matrius amb forats, aquestes poden no donar resultats correctes quan el percentatge de forats a la matriu és molt gran. Proposem un esquema multiresolució iteratiu per poder tractar aquests casos amb molts elements buits a la matriu de trajectòries. L'esquema proposat consisteix en considerar submatrius amb un percentatge de forats reduït. Seguidament, els forats d'aquestes matrius són emplenats aplicant un mètode de factorització. L'objectiu final és obtenir millors resultats aplicant un mètode de factorització a la matriu emplenada amb l'esquema proposat, enlloc d'aplicar-lo a la matriu inicial, que presenta un elevat percentatge de forats. <br/>En el cas de matrius de trajectòries corresponents a punts característics que pertanyen a diversos objectes, les tècniques de factorització no es poden aplicar directament per<br/>obtenir el moviment i la forma de cada objecte, ja que les trajectòries no estan ordenades per objectes. A més a més, s'ha de tenir en compte un altre problema: l'estimació del rang de la matriu de trajectòries. El problema és que amb forats, el rang de la matriu no pot ser calculat directament. Per altra banda, com que hi ha múltiples objectes, és difícil d'estimar-lo, sense utilitzar informació com ara nombre d'objectes o tipus de moviment d'aquests. Presentem una tècnica per estimar el rang d'una matriu de trajectòries amb forats. La idea és que, si les trajectòries pertanyen a objectes rígids, la freqüència espectral de la matriu de trajectòries inicial no hauria de variar un cop la matriu ha estat emplenada. Els forats de la matriu són emplenats amb un mètode de factorització, considerant diferents valors per al rang de la matriu. Al mateix temps, el rang de la matriu de trajectòries és estimat fent servir una mesura que compara la freqüència espectral de cada matriu emplenada amb la de la matriu inicial. El proper pas consisteix en segmentar les trajectòries segons el seu moviment. Finalment, qualsevol tècnica d'Estructura a partir de Moviment per a un únic objecte pot ser aplicada per trobar el moviment i la forma de cada objecte.<br/>Intentem aplicar la metodologia proposada per al problema de l'Estructura a partir de Moviment a d'altres aplicacions, no només dins el camp de la visió per computador. En particular, l'objectiu és adaptar els mètodes Alternats per poder aplicar-los a diferents problemes de dimensionalitat reduïda. Una de les possibles aplicacions és la fotometria: la idea és recuperar la reflectància i les normals a la superfície i la direcció de la llum en cada imatge, a partir d'imatges obtingudes sota diferents condicions de llum. En una segona aplicació, l'objectiu és adaptar els mètodes Alternats per poder omplir els forats en una matriu de dades provinents d'expressions de gens. Aquestes matrius són generades amb la informació que proporcionen els DNA microarrays. Finalment, els mètodes Alternats són aplicats a matrius de dades de sistemes de recomanació, molt usats en E-commerce. Aquestes matrius contenen puntuacions que els usuaris han donat a certs productes. La idea és predir les puntuacions que un usuari concret donaria a altres productes, utilitzant la informació emmagatzemada en el sistema.

This work is focused on the missing data matrix factorization addressing the Structure from Motion (SFM) problem. The aim is to decompose a matrix of feature point trajectories into the motion and shape matrices, which contain the relative camera-object motion and the 3D positions of tracked feature points, respectively. This decomposition can be found by using the fact that the matrix of trajectories has a reduced rank. Although several techniques have been proposed to tackle this problem, they may give undesirable results when the percentage of missing data is high. An iterative multiresolution scheme is presented to deal with matrices with high percentages of missing data. Experimental results show the viability of the proposed approach.<br/>In the multiple objects case, factorization techniques can not be directly applied to obtain the SFM of every object, since trajectories are not sorted into different objects. Furthermore, another problem should be faced out: the estimation of the rank of the matrix of trajectories. The problem is that, in this case, the rank of the matrix of trajectories is not bounded, since any prior knowledge about the number of objects nor about their motion is used. This problem becomes more difficult with missing data, since singular values can not be computed to estimate the rank. A technique to estimate the rank of a missing data matrix of trajectories is presented. The good performance of the proposed technique is empirically shown considering sequences with both, synthetic and real data. Once the rank is estimated and the matrix of trajectories is full, the motion segmentation of trajectories is computed. Finally, any factorization technique for the single object case gives the shape and motion of every object.<br/>In addition to the SFM problem, this thesis also shows other applications that can be addressed by means of factorization techniques. Concretely, the Alternation technique, which is used through the thesis, is adapted to address each particular problem. The first proposed application is the photometric stereo: the goal is to recover the reflectance and surface normals and the light source direction at each frame, from a set of images taken under different lighting conditions. In a second application, the aim is to fill in missing data in gene expression matrices by using the Alternation technique. Finally, the Alternation technique is adapted to be applied in recommender systems, widely considered in E-commerce. For each application, experimental results are given in order to show the good performance of the proposed Alternation-based strategy.