Techniques are provided for tracking objects in an encoded video stream based on data directly extracted from the video stream, thus eliminating any need for the stream to be fully or partially decoded. Extracted motion vector and DC coefficient data can be used to provide a rough estimation of which macro-blocks are be associated with a background motion model and which macro-blocks correspond to a foreground object which is moving with respect to the background motion model. Macro-blocks which are associated with a moving foreground object can be grouped based on connectivity and a similarity measure derived from the extracted DC coefficient data. The grouped macro-blocks can be tracked from frame to frame to identify and eliminate groups having only negligible motion. The resulting validated macro-block groups will correspond to a rough object mask associated with a moving region in the analyzed frame.