AbstractsComputer Science

Estruturas circulantes em visão por computador; Circulant structures in computer vision

by João Filipe Henriques




Institution: Universidade de Coimbra
Department:
Year: 2016
Keywords: Circulant Matrices; Discrete Fourier Transform; Correlation Filters; Image Transformations; Visual Tracking; Object Detection; Pose Estimation
Posted: 02/05/2017
Record ID: 2063748
Full text PDF: http://hdl.handle.net/10316/29085


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… Advisors/Committee Members: Batista, Jorge (advisor).