|Tese de Doutorado em Computação Gráfica, Visão Computacional e Processamento de Imagens|
UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
DEFESA DE TESE DE DOUTORADO
Aluno: Leandro Augusto Frata Fernandes
Orientador: Manuel Menezes de Oliveira Neto
Título: "On the Generalization of Subspace Detection in Unordered Multidimensional Data"
Linha de Pesquisa: Computação Gráfica, Visão Computacional e Processamento de Imagens
Local: Auditório do Centro de Eventos, Prédio 67 - Instituto de Informática/UFRGS.
Prof. Dr. Jayme Vaz Jr. (IMECC/UNICAMP)
Prof. Dr. Roberto M. Cesar Jr. (IME/USP)
Prof. Dr. Cláudio Rosito Jung (UFRGS)
Prof. Dr. João Luiz Dihl Comba (UFRGS)
Presidente da Banca: Prof. Dr. Manuel Menezes de Oliveira Neto
This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n - p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array.
The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases.
I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.
subspace detection, pattern recognition, subspace parameterization, parameter space, generalization, error propagation, Grassmannian, Hough transform, geometric algebra, Clifford algebra