Source-linked AI summary
Video Inpainting of Complex Scenes
Alasdair Newson, Andrés Almansa, Matthieu Fradet, Yann Gousseau, Patrick Pérez
TL;DR
Video inpainting remains less extensively studied than image inpainting because its temporal dimension makes high-quality processing computationally difficult, despite applications in restoration and post-production. The paper optimises a global, non-local patch-based functional with extensions for complex motion and textures, yielding automatic results across varied scenes with substantially lower execution time than prior methods. High-resolution videos can still require several hours to process, and long-occluded moving objects remain difficult.
Problem
Video inpainting has seen less research than image inpainting because the added temporal dimension creates high time complexity, while high-quality results on high-definition videos have only recently become possible semi-automatically.
Method
The algorithm optimises a global non-local patch-based functional, adding spatio-temporal PatchMatch, texture features, moving-background handling, specialised initialisation, and multi-resolution details.
Results
The method handles dynamic textures, multiple moving objects, moving backgrounds, and other complex situations automatically without pre-segmentation, while achieving results at least an order of magnitude faster than previous algorithms.
Takeaways & Limitations
The resulting algorithm addresses video textures and varied complex scenes in a single framework without manual input or segmentation beyond defining the inpainting mask.
Takeaways & Limitations
Long-occluded moving objects remain difficult, and high-resolution videos can take up to several hours to process.
Abstract
from arXiv · showhide
We propose an automatic video inpainting algorithm which relies on the optimisation of a global, patch-based functional. Our algorithm is able to deal with a variety of challenging situations which naturally arise in video inpainting, such as the correct reconstruction of dynamic textures, multiple moving objects and moving background. Furthermore, we achieve this in an order of magnitude less execution time with respect to the state-of-the-art. We are also able to achieve good quality results on high definition videos. Finally, we provide specific algorithmic details to make implementation of our algorithm as easy as possible. The resulting algorithm requires no segmentation or manual input other than the definition of the inpainting mask, and can deal with a wider variety of situations than is handled by previous work. 1. Introduction. Advanced image and video editing techniques are increasingly common in the image processing and computer vision world, and are also starting to be used in media entertainment. One common and difficult task closely linked to the world of video editing is image and video " inpainting ". Generally speaking, this is the task of replacing the content of an image or video with some other content which is visually pleasing. This subject has been extensively studied in the case of images, to such an extent that commercial image inpainting products destined for the general public are available, such as Photoshop's " Content Aware fill " [1]. However, while some impressive results have been obtained in the case of videos, the subject has been studied far less extensively than image inpainting. This relative lack of research can largely be attributed to high time complexity due to the added temporal dimension. Indeed, it has only very recently become possible to produce good quality inpainting results on high definition videos, and this only in a semi-automatic manner. Nevertheless, high-quality video inpainting has many important and useful applications such as film restoration, professional post-production in cinema and video editing for personal use. For this reason, we believe that an automatic, generic video inpainting algorithm would be extremely useful for both academic and professional communities.
1. Introduction.
Video inpainting research includes object-based and patch-based approaches, but prior methods face restrictive scene assumptions, segmentation requirements, or high computational cost. The paper builds on non-local patch-based optimisation to address complex situations automatically and provides implementation details.
- Object-based methods segment moving foreground and background, then use separate inpainting procedures with restrictive motion assumptions.
- Patch-based methods copy spatio-temporal cuboids that encode local texture, structure, and motion, but greedy strategies provide no guarantee of global coherence.
- Non-local patch-based methods ensure global coherence automatically, but their high-dimensional nearest-neighbour searches can require several days for a few seconds of VGA video.
- The proposed work uses the non-local patch-based approach as its core and targets complex video-inpainting situations through solutions to key algorithmic challenges.
- Its contributions include spatio-temporal PatchMatch acceleration, texture features, moving-background handling, initialisation, and precise multi-resolution implementation details.
- The algorithm is intended to provide automatic video inpainting without manual segmentation, supported by an implementation made available by the authors.
2. Variational framework and notation.
The framework represents video inpainting as global patch-based optimisation over video content and patch correspondences. Iterative nearest-neighbour matching and reconstruction are embedded in a multi-resolution scheme.
- The global functional is optimised by alternating nearest-neighbour matching for occluded patches with reconstruction from the resulting correspondences.
- The video is represented over a spatio-temporal volume, with colour content defined at positions p = (x, y, t).
- The occlusion H and data region D partition the spatio-temporal volume into unknown and unoccluded positions.
- Video patches are rectangular spatio-temporal cuboids whose ordered colour values form the patch representation.
- Only patches from fully unoccluded neighbourhoods are used as source patches, while the occlusion is dilated for neighbourhood-based processing.
- A shift map φ associates each position with a corresponding source position q = p + φ(p) constrained to lie in the usable unoccluded region.
- The iterative optimisation uses a multi-resolution pyramid to improve results, avoid local minima, and reconstruct structures and moving objects in large occlusions.
3. Proposed algorithm.
The proposed algorithm accelerates global patch-based video inpainting while addressing textured video, moving backgrounds, and initialization challenges. It combines spatio-temporal PatchMatch, texture features, affine realignment, and a specified multi-resolution initialization scheme.
- Approximate Nearest Neighbour search: The algorithm extends PatchMatch to spatio-temporal approximate nearest-neighbour search through initialization, propagation, and random search.Propagation spreads good shifts, while random search explores progressively smaller neighborhoods; the procedure uses 10 iterations.
- Video reconstruction: The final reconstruction can use only the best patch, producing results similar to mean shift while avoiding weighted-averaging blur at lower computational cost.The weighted mean-based reconstruction accelerates convergence, whereas the best-patch method is used for the final reconstruction.
- Video texture pyramid: Texture features are added to the patch distance to help identify correct patches for video-texture inpainting.The texture feature pyramid reflects the video’s textural nature, addressing ambiguities caused by multi-resolution comparisons and standard ℓ2 patch distances.
- Inpainting with mobile background: The framework performs foreground and background inpainting simultaneously without segmenting the video into foreground and background.This avoids the segmentation requirement of earlier approaches, while the paper notes that repeated patches with identical motion are not guaranteed for some sequences.
end
The implementation uses careful initialization and multi-resolution design choices to improve reconstruction quality, while retaining practical stopping and search parameters. Temporal subsampling is generally avoided because long occlusions make object motion difficult to determine.
- Initialization: Careful initialization joins occluded structures where random initialization and zero-Laplacian interpolation fail to improve the reconstruction.The proposed onion-peel initialization produces a satisfactory cardboard-tube result.
- Multi-resolution scheme: Temporal subsampling is avoided because motion is difficult to represent at coarser pyramid levels.It is used only when objects remain behind the occlusion for a long time, as in the “Jumping girl” sequence.
- Multi-resolution scheme: Long occlusions remain difficult because the motion of an occluded object becomes increasingly ambiguous unless it is strictly periodic.The authors leave this problem open for further work.
- Multi-resolution scheme: Pyramid levels should keep occlusion size from becoming too large relative to patch size.The passage reports that experiments support this level-selection principle.
- Texture reconstruction: Texture features are necessary for correctly reconstructing complex video textures such as waves.Without the features, the waves are reconstructed incorrectly.
- Multi-resolution scheme: The implementation uses nearest-neighbour upsampling for the shift map when moving between pyramid levels.This choice was made after experimentation as a simpler alternative to a more intricate scheme.
4. Experimental results.
Experiments show that the unified algorithm handles diverse video-inpainting situations with high visual quality, without segmentation or manual intervention, while substantially reducing computation time.
- Visual evaluations: The method produces similarly high-quality results to Wexler et al. and Granados et al. on challenging video-inpainting examples.The comparisons include moving backgrounds and multiple moving objects.
- Visual evaluations: The algorithm reconstructs several moving objects without the manual segmentation required by Granados et al.The reported visual quality is similar to that of previous algorithms.
- Visual evaluations: Texture features improve inpainting results for dynamic textures, whereas omitting them produces an unsatisfactory reconstruction.The paper notes that some competing approaches using plain colour distance or direct pixel copying would encounter similar problems.
- Visual evaluations: Moving backgrounds are handled within the same unified framework, without requiring a separate algorithm or foreground/background segmentation.This capability is demonstrated against Granados et al.’s background-specific method.
- Execution times: 20-50 times speedup is obtained over Wexler et al.’s ANN search, while total execution times are around an order of magnitude faster than Granados et al.’s semi-automatic methods.ANN search represents the majority of the computational load; the comparison uses ANN times because Wexler et al.’s total-time parameters are incompletely specified.
- Execution times: High-resolution examples can still require several hours to process.The authors identify further acceleration as an open improvement area.
5. Further work.
The authors identify unresolved difficulties with long-term object occlusion and high-resolution processing, while suggesting richer patch features and dimensionality reduction as future directions.
- Further work: Long-term occlusion of a moving object remains difficult and is not handled in a unified manner.Temporal subsampling performs poorly when complex motion is present.
- Further work: The patch space could be enriched with features such as spatio-temporal gradients.This suggestion follows the observed usefulness of a multi-resolution texture-feature pyramid.
6. Conclusion.
The proposed automatic algorithm performs well across varied video-inpainting situations, including dynamic textures and high-definition videos, without manual input or segmentation.
- Conclusion: The algorithm performs well in varied situations and on high-definition videos in a completely automatic manner.
- Conclusion: The method requires no manual input or segmentation beyond defining the inpainting mask.
- Conclusion: Dynamic video textures are addressed with more realistic results than other inpainting algorithms.
- Conclusion: The authors aim for the method to make video inpainting more accessible for post-production, restoration, and personal video enhancement.
Appendix A. On the link between the non-local patch-based and shift map-based formulations.
The appendix relates non-local patch-based and shift-map formulations by showing that the latter is a constrained special case, while emphasizing that the formulations are not fully equivalent.
- Non-local patch-based formulation: Non-local patch-based inpainting uses a probability distribution of correspondence weights and minimizes a global energy with a soft-assignment term and entropy regularizer.The formulation uses a positive weight function normalized for each point, with γ controlling selectivity.
- Non-local patch-based formulation: The framework uses Gaussian-weighted patch distances and can be optimized by alternating minimization over the video and correspondence weights.The paper specializes the patch distance to the ℓ2 norm for its subsequent derivation.
- Relation to shift maps: The shift-map formulation becomes a special case when weights collapse to a single match, intra-patch weighting is uniform, and reconstruction follows one shift map.The appendix also considers γ approaching zero in relating the energies.
- Relation to shift maps: Under these constraints, the inpainted value is reconstructed from the correspondence selected for its patch.The appendix describes this reconstruction as an aggregated average in the general formulation and as a single correspondence in the shift-map case.
- Caveat: The two formulations are not equivalent because they differ in optimization methodology and because the shift-map formulation includes a gradient term.The appendix also notes that the single-shift-map reconstruction choice was not considered by Arias et al., so results may differ.
Appendix B. Comparing textured patches.
Texture comparison can fail because multi-resolution subsampling loses detail, making textured patches resemble smooth ones. Numerical simulations quantify this difficulty for image and video patches.
- The appendix notes that reconstructing Equation A.7 creates problems at the occlusion border, which are ignored for simplicity.
- Table 2 reports simulated probabilities for random 2D and 3D patches, using ten-run averages and centered normal components with variance 25.
- Multi-resolution subsampling loses detail and can make textured patches match smooth ones at every pyramid level.
B.1. Comparing patches with the classical ℓ2 distance.
The classical ℓ2 patch distance can favor constant patches over textured patches, especially when many candidate patches are searched. This issue is particularly important in video, where useful matches may occur anywhere in the volume.
- For white-noise and constant patches with the same mean, SSD comparisons favor the constant patch on average over another random patch.
- The relevant probability is whether any candidate random patch beats the constant patch, rather than the average distance between three patches.
- The SSD distances follow chi-square distributions, allowing the probability of a random patch beating a constant one to be computed numerically or by simulation.
- 2 × 10^-7 is the probability that a random 5 × 5 × 5 video patch beats a constant patch, requiring a 170 × 170 × 170 volume for one expected match.
- Local ANN search restrictions used in image inpainting do not hold for video when complex movement may place relevant information anywhere in the video volume.
- PatchMatch exacerbates the distance problem because texture-producing shifts are not piecewise constant and therefore are not propagated, unlike smooth-patch shifts.
B.2. ANN search with PatchMatch.
A texture-feature pyramid addresses the failure of classical patch comparison by guiding inpainting toward appropriate patches. A white-noise toy example illustrates the resulting ability to reconstruct texture naturally.
- The texture-feature pyramid is inpainted simultaneously with the colour-video pyramid to guide patch selection.
- In the white-noise toy example, texture features make it possible to inpaint noise in a way that appears natural to human observers.