Digital video signature apparatus and methods for use with video program identification systems are disclosed. The example apparatus and methods generate a signature associated with a video program. An example system includes a frame scanner to scan video frames associated with the video program. The frame scanner is to select a video frame based on a number of intra-coded macro blocks within the video frame. The example system also includes an intra-coded macro block extractor to extract intra-coded macro blocks from the video frame and a scaled image extractor to extract a scaled image from the intra-coded macro blocks. A signature generator is also included in the example system to calculate a plurality of centroids associated with video frame based on the scaled image and to form the signature based on the plurality of centroids.