An optimization-based approach for restoring missing structures and textures in images

In this paper, we present a new automated algorithm for image completion, i.e., reconstructing the missing, damaged, or occluded parts in images in a visually non-detectable fashion. Our algorithm is capable of recovering both structural and textural information on the damaged parts, by solving several key subproblems such as determining the connections and shapes of the occluded region boundary curves, synthesizing textures, etc. Our algorithm combines structure-based and texture-based approaches and is hinged on optimization techniques. In particular, we formulate a set of key subproblems as optimization problems in graph theory, and solve them optimally in polynomial time. Previous methods for these problems either cannot ensure the topological correctness of the restored structures or rely only on heuristics.