Within examples, methods and systems for occlusion-robust object fingerprinting using fusion of multiple sub-region signatures are described. An example method includes receiving an indication of an object within a sequence of video frames, selecting from the sequence of video frames a reference image frame indicative of the object and candidate image frames representative of possible portions of the object, dividing the reference image frame and the candidate image frames into multiple cells, defining for the reference image frame and the candidate image frames sub-regions of the multiple cells such that the sub-regions include the same cells for overlapping representations and the sub-regions include multiple sizes, comparing characteristics of sub-regions of the reference image frame to characteristics of sub-regions of the candidate image frames and determining similarity measurements, and based on the similarity measurements, tracking the object within the sequence of video frames.