A method and systems of enhancing a video using a related image are provided. One or more patches are identified in the video, with each patch identifying a region that is present in one of the frames of the video that can be mapped to a similar region in at least one other frame of the video. For each identified patch in the video, a best matching patch in the related image is found. The video is enhanced using the best matching patch in the related image for each identified patch in the video.