One of the major objectives in multimedia technology is to be able to segment objects automatically from a video sequence, for a diverse range of applications from video surveillance and object tracking through to content-based video retrieval, coding and medical imaging. Probabilistic spatio-temporal (PST) video object segmentation has been shown to be of pivotal importance in achieving better segmentation, because it considers space, colour and time features conjointly in a spatio-temporal framework. Existing PST techniques however, incur high computational expense as they normally have to process large dimensional feature vectors. This paper addresses this problem by presenting a computationally efficient PST video object segmentation algorithm that has reduced dimensionality, with experimental results confirming that for various standard video test sequences, a significant reduction in computational complexity is achieved compared with the existing PST technique, without compromising perceptual picture quality.