Despite recent advances, face-recognition algorithms are still challenged when applied in the setting of video surveillance systems which inherently introduce variations in the pose of subjects. The present work addresses this problem, and seeks to provide a recognition algorithm that is specifically suited for a frontal-to-side re-identification setting. Deviating from classical biometric approaches, the proposed method considers color- and texture- based soft biometric traits, specifically those taken from patches of hair, skin and clothes. The proposed method and the suitability of these patch-based traits are then validated both analytically and empirically.