A difficult problem in digital image and motion picture restoration is the reconstruction of large segments of missing pixels. This problem occurs for instance when subtitles have to be removed from (motion) pictures. Due to the nature of the problem the resotarion has to be done mainly frame by frame.
For this purpose we have developed a Fast Voronoi Tesselation algorithm combined with adaptive filtering. The Voronoi tesselation recovers the texture in the areas with missing samples (the areas where the subtitles are). The adaptive filtering preseves edge-information, to reduce artifacts.
The novelty in our Fast Voronoi Tesselation is that it can be carried out by a sequence of FFT's, which makes the whole restoration algorithm very fast.
Here is one image frame with subtitles (to make the restoration problem even more difficult we have placed an additional subtitle in the center of the image).
And here is the restoration (zoomed in):