A video fingerprinting algorithm extracts characteristic features from regions of interest in a media object, such as a video signal. The regions of interest contain the perceptually important parts of the video signal. A fingerprint may be extracted from a target media object, and the fingerprint the target media content may then be matched against multiple regions of interest of known reference fingerprints. This matching may allow identification of complex scenes, inserts, and different versions of the same content presented in different formats of the media object.