A system for creating a video signature, including a video retrieval module to retrieve a video sequence having a plurality of frames, each of the frames including an image, a region definition module to define a plurality of image regions for the image of each of the frames, such that the image regions occupy the same portions of the image for each of the frames, a motion analysis module to calculate a plurality of motion vectors, such that one of the motion vectors is calculated for each of the image regions of each of the frames by comparison to the image of another one of the frames, each of the motion vectors having a direction of motion and a magnitude of motion, and a signature creation module to create the video signature including data indicative of the direction of motion and the magnitude of motion for each of the image regions of each of the frames. Related apparatus and methods are also described.