dc.contributor.author Hocking, Laird Robert dc.date.accessioned 2018-09-27T11:54:09Z dc.date.available 2018-09-27T11:54:09Z dc.date.issued 2018-10-20 dc.date.submitted 2017-08-29 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/281805 dc.description.abstract The subject of this thesis is a class of fast inpainting methods (image or video) based on the idea of filling the inpainting domain in successive shells from its boundary inwards. Image pixels (or video voxels) are filled by assigning them a color equal to a weighted average of either their already filled neighbors (the direct'' form of the method) or those neighbors plus additional neighbors within the current shell (the semi-implicit'' form). In the direct form, pixels (voxels) in the current shell may be filled independently, but in the semi-implicit form they are filled simultaneously by solving a linear system. We focus in this thesis mainly on the image inpainting case, where the literature contains several methods corresponding to the {\em direct} form of the method - the semi-implicit form is introduced for the first time here. These methods effectively differ only in the order in which pixels (voxels) are filled, the weights used for averaging, and the neighborhood that is averaged over. All of them are very fast, but at the same time all of them leave undesirable artifacts such as kinking'' (bending) or blurring of extrapolated isophotes. This thesis has two main goals. First, we introduce new algorithms within this class, which are aimed at reducing or eliminating these artifacts, and also target a specific application - the 3D conversion of images and film. The first part of this thesis will be concerned with introducing 3D conversion as well as Guidefill, a method in the above class adapted to the inpainting problems arising in 3D conversion. However, the second and more significant goal of this thesis is to study these algorithms as a class. In particular, we develop a mathematical theory aimed at understanding the origins of artifacts mentioned. Through this, we seek is to understand which artifacts can be eliminated (and how), and which artifacts are inevitable (and why). Most of the thesis is occupied with this second goal. Our theory is based on two separate limits - the first is a {\em continuum} limit, in which the pixel width $h \rightarrow 0$, and in which the algorithm converges to a partial differential equation. The second is an asymptotic limit in which $h$ is very small but non-zero. This latter limit, which is based on a connection to random walks, relates the inpainted solution to a type of discrete convolution. The former is useful for studying kinking artifacts, while the latter is useful for studying blur. Although all the theoretical work has been done in the context of image inpainting, experimental evidence is presented suggesting a simple generalization to video. Finally, in the last part of the thesis we explore shell-based video inpainting. In particular, we introduce spacetime transport, which is a natural generalization of the ideas of Guidefill and its predecessor, coherence transport, to three dimensions (two spatial dimensions plus one time dimension). Spacetime transport is shown to have much in common with shell-based image inpainting methods. In particular, kinking and blur artifacts persist, and the former of these may be alleviated in exactly the same way as in two dimensions. At the same time, spacetime transport is shown to be related to optical flow based video inpainting. In particular, a connection is derived between spacetime transport and a generalized Lucas–Kanade optical flow that does not distinguish between time and space. dc.description.sponsorship Cambridge Overseas Scholarship dc.language.iso en dc.rights All rights reserved dc.rights All Rights Reserved en dc.rights.uri https://www.rioxx.net/licenses/all-rights-reserved/ en dc.subject image processing dc.subject image inpainting dc.subject partial differential equations dc.subject stopped random walks dc.subject numerical analysis dc.subject convergence rates dc.subject 3D conversion dc.subject parallel algorithms dc.title Shell-Based Geometric Image and Video Inpainting dc.type Thesis dc.type.qualificationlevel Doctoral dc.type.qualificationname Doctor of Philosophy (PhD) dc.publisher.institution University of Cambridge dc.publisher.department Applied Mathematics and Theoretical Physics dc.date.updated 2018-09-25T17:54:31Z dc.identifier.doi 10.17863/CAM.29168 dc.publisher.college Sidney Sussex College dc.type.qualificationtitle Doctor of Philosophy (PhD) Applied Mathematics cam.supervisor Schoenlieb, Carola-Bibiane cam.thesis.funding false
﻿