Valia Guerra-Ones

Victoria Hernández-Mederos, Dimas Martínez, Jorge Estrada-Sarlabous et al.

In this paper we introduce Farthest Sampling Segmentation (FSS), a new method for segmentation of triangulated surfaces, which consists of two fundamental steps: the computation of a submatrix $W^k$ of the affinity matrix $W$ and the application of the k-means clustering algorithm to the rows of $W^k$. The submatrix $W^k$ is obtained computing the affinity between all triangles and only a few special triangles: those which are farthest in the defined metric. This is equivalent to select a sample of columns of $W$ without constructing it completely. The proposed method is computationally cheaper than other segmentation algorithms, since it only calculates few columns of $W$ and it does not require the eigendecomposition of $W$ or of any submatrix of $W$. We prove that the orthogonal projection of $W$ on the space generated by the columns of $W^k$ coincides with the orthogonal projection of $W$ on the space generated by the $k$ eigenvectors computed by Nyström's method using the columns of $W^k$ as a sample of $W$. Further, it is shown that for increasing size $k$, the proximity relationship among the rows of $W^k$ tends to faithfully reflect the proximity among the corresponding rows of $W$. The FSS method does not depend on parameters that must be tuned by hand and it is very flexible, since it can handle any metric to define the distance between triangles. Numerical experiments with several metrics and a large variety of 3D triangular meshes show that the segmentations obtained computing less than the 10% of columns $W$ are as good as those obtained from clustering the rows of the full matrix $W$.

Salehe Erfanian Ebadi, Valia Guerra Ones, Ebroul Izquierdo

The research reported in this paper addresses the fundamental task of separation of locally moving or deforming image areas from a static or globally moving background. It builds on the latest developments in the field of robust principal component analysis, specifically, the recently reported practical solutions for the long-standing problem of recovering the low-rank and sparse parts of a large matrix made up of the sum of these two components. This article addresses a few critical issues including: embedding global motion parameters in the matrix decomposition model, i.e., estimation of global motion parameters simultaneously with the foreground/background separation task, considering matrix block-sparsity rather than generic matrix sparsity as natural feature in video processing applications, attenuating background ghosting effects when foreground is subtracted, and more critically providing an extremely efficient algorithm to solve the low-rank/sparse matrix decomposition task. The first aspect is important for background/foreground separation in generic video sequences where the background usually obeys global displacements originated by the camera motion in the capturing process. The second aspect exploits the fact that in video processing applications the sparse matrix has a very particular structure, where the non-zero matrix entries are not randomly distributed but they build small blocks within the sparse matrix. The next feature of the proposed approach addresses removal of ghosting effects originated from foreground silhouettes and the lack of information in the occluded background regions of the image. Finally, the proposed model also tackles algorithmic complexity by introducing an extremely efficient "SVD-free" technique that can be applied in most background/foreground separation tasks for conventional video processing.