Though being a vital part of video indexing and retrieval systems, key-frame extraction algorithms have been based mainly on the analysis of various frame similarities and their later clustering. This work broadens the spectra of the analysis by focusing on the spatio-temporal region relations present in the scene to determine the most representative frame in the shot. It applies efficient video segmentation to a low-resolution sequence representative utilising a novel iterative unsupervised segmentation algorithm based on the anisotropic diffusion paradigm and k-means clustering. Key-frames are determined by applying a set of heuristic rules to the behaviour and features of extracted spatio-temporal regions. Experimental results are given.