Techniques are described for improving accuracy and speed of video fingerprinting and identification by using video frame color and intensity information. Multiple approaches for generating a novel signature based on video frame color information are described. One is based on spatial distribution of pixel intensities with reference to derived color groups, while another is based on thresholding a joint histogram of pixel intensity, color, and spatial coordinates. These color based signatures can be deployed either as primary video content signatures, or as hash traversal signatures used to improve speed of an initial stage of video data base search procedures. They can also be used as secondary signatures during a video signature data base search with primary video content signatures, to help disambiguate possible false positive matches, and to improve marginal matches which might not be identified otherwise.