Estruturas circulantes em visão por computador

Abstract

Visual recognition systems are extremely data-hungry. To accurately recognize a new kind of object, a learning algorithm requires a massive dataset of example images, often augmented artificially by cropping different image regions. More examples seem to invariably raise the computational burden of learning. Is this an inescapable fact? In this thesis, we show that it is not true -- that the structure of these datasets hides important shortcuts. The key observation is that samples are not independent, since samples cropped from the same image share most pixels. Using an analytical model of image translation, the cyclic shift, we show that the resulting dataset contains circulant matrices. As a result, we can diagonalize it with the Discrete Fourier Transform (DFT), which reduces both storage and computation by orders of magnitude. The use of the DFT further reveals an interesting link to correlation filters from classical signal processing. We accelerate learning algorithms such as Ridge Regression and Support Vector Regression, addressing linear and non-linear kernel methods. We propose two trackers, the Dual and Kernelized Correlation Filters, which run at hundreds of frames-per-second, and yet perform better than more complex trackers on a 50 videos benchmark. For detection, we propose a decomposition that is several times faster than hard-negative mining, a staple of detector learning. We also generalize these results for other kinds of datasets, such as rotated images or non-rigidly deformed images, which accelerates the learning of pose estimators. The proposed solutions require only a few lines of code to implement, relying on the Fast Fourier Transform and optional off-the-shelf solvers for the bulk of the computations, which easily run in parallel. The software produced during this thesis is open-source.

Os sistemas de reconhecimento visual necessitam de vastas quantidades de dados. Para reconhecer um novo tipo de objecto, um algoritmo de aprendizagem requer uma grande base de dados de imagens-exemplo, muitas vezes aumentada artificialmente através da extracção de diferentes regiões dessas imagens. Intuitivamente, processar mais exemplos implica aumentar invariavelmente o custo computacional do processo de aprendizagem. Será que esta intuição corresponde à realidade? Esta tese demonstra que tal não é verdade -- que a estrutura destas bases de dados contém atalhos ainda inexplorados. A principal observação é que as amostras não são independentes, já que amostras extraídas da mesma imagem vão ter vários píxeis em comum. Com base num modelo analítico da translação de imagem, chamado "deslocação cíclica", é demonstrado que a base de dados resultante contém matrizes circulantes. Consequentemente, podemos diagonalizá-la com a Transformada de Fourier Discreta (TFD), o que reduz significativamente os requisitos de armazenamento e de computação. O uso da TFD revela uma ligação importante aos filtros de correlação estudados em processamento de sinal. Demonstra-se que é possível acelerar algoritmos de aprendizagem tais como o método dos mínimos quadrados com regularização, e regressão de vectores de suporte, abordando tanto métodos lineares como de kernel (núcleo). São propostos dois métodos de seguimento visual, o Filtro de Correlação Dual e o de Kernel, capazes de processar vídeo a centenas de imagens por segundo, e que demonstram maior precisão que outros métodos mais complexos numa base de dados de 50 vídeos. Para detecção de objectos, é proposta uma decomposição várias vezes mais rápida que a procura sistemática de exemplos negativos, o método mais comum de aprendizagem de detectores. Estes resultados são também generalizados para outros tipos de bases de dados, tais como imagens que sofreram rotação ou deformações não rígidas, o que permite ainda acelerar detectores de pose. As soluções propostas podem ser implementadas com poucas linhas de código, usando apenas a Transformada de Fourier Rápida, e opcionalmente algoritmos de aprendizagem externos, que podem ser executados em paralelo. O código-fonte relativo a esta tese é de acesso livre.