Ortho-diffusion decompositions of graph-based representation of images

This paper proposes a new feature representation methodology for graph-based data. Initially, random walks on matrices of pairwise data similarities are considered. A diffusion process is embedded into orthonormal decompositions of such matrices at various scales while enabling a data reduction mechanism as well. At each scale, the QR orthonormal decomposition algorithm, alternating with diffusions and data reduction stages is applied recursively on the given graph-based data representations. The proposed methodology is used in extracting complex feature representations from images, which are then used for image matching and in face recognition. In the face recognition application, both global appearance models and semantic representations of biometric features are considered. Both the correlation and the covariance of images of human faces are considered for the training stage when using global appearance models. The proposed data representation is shown to be robust in face recognition applications, when face images are represented in low resolution and when they are corrupted by noise.