Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from A-E

Digital Inpainting - Image Inpainting, Video Inpainting, Holes Removal on 3-D Surfaces, Summary

inpainted region mechanism information

Timothy K. Shih, Rong-Chi Chang, Su-Mei Chou, Yu-Ping Chen, and
Huan-Chi Huang
Tamkang University, Taiwan

Definition: Digital inpainting is a technique to automatically restore partially damaged photos, repair aged movies, or fill holes on 3D surfaces.

Digital inpainting requires fundamental knowledge in image processing, video coding, and 3D geometric. Certainly, these topics are important issues in multimedia computing. This article summarizes a few challenge issues in digital inpainting and presents some solutions in the literature. We divide the article into three short sections for each problem (i. e., image, video, and 3D surface). Several short articles (included in this book) related to this article further explain additional issues on image and video inpainting.

Image Inpainting

Aged photos and paintings can be damaged either by scratch, dirt, or other reasons. Even though it is not possible to restore a painting to its original, to repair damaged artifacts with a visually pleasant result is useful, especially for examples in digital museum projects. One of the simplest but efficient mechanisms was presented in. The diffusion kernel is able to repair damages of small area with a barrier to deal with high contrast edges. The computation presented in is proved to be very fast. By using a similar interpolation concept, with an extension to allow different thresholds on different interpolated pixels, the mechanism discussed in allows an adaptive computation scheme. Thus, inpainted pixels far away from inpainting boundary can be calculated to achieve a better visual result. Considering inpainting from another perspective, the concept of isophote lines arriving at the boundary of an inpainted area is introduced in By preventing crossed isophote lines, the mechanism can partially preserve structural information in a damaged image. Other works uses concepts on fluid-dynamics and curvature-driven diffusions for image inpainting. Basically, an image with continuous color and intensity levels can be treated as a two dimensional fluid object. The mathematical model derived in achieve a reasonable result of image inpainting.

On the other hand, a multiple resolution approach is used in. The damaged picture is decomposed into several levels, depending on the color variations of the picture. Interpolated pixels are calculated according to its coordination relation with respect to useful surrounding information (see Figure 1). The algorithm is summarized in the article entitled “Multi-Resolution Image Inpainting” in this book.

The algorithm is further extended for painting. A painting can be separated into several layers according to color distributions. Each layer is inpainted separately. The results are merged to obtain a reconstructed image (see Figure 2). The inpainting strategy use in is similar to the algorithm used in. However, to merge inpainted results from different layers, a layer fusion algorithm is necessary. The fusion algorithm follows a strategy. For each damaged pixel to be inpainted, two consecutive layers are compared. A window with pixels in a distance with respect to an inpainted pixel is used. A function computes percentages of useful pixels within the distance is applied to each inpainted pixel. Depending on the percentages, a layer is selected. Useful pixels are non-inpainted pixels from the original image, with respect to a layer. The far ground is firstly placed in a blank paper. The picture is restored with a darker layer step-by-step. In Chinese painting, light far grounds are drawn first, followed by darker grounds. The restoring strategy achieves a similar effect.

The work discussed in and also points out an issue of what type of images that can be restored easily. In general, pixel interpolation is suitable for images with continuous color and intensity, for instance, photos. Images with concrete boundaries, such as cartoon drawing, are hard to appreciate pixel interpolation. To restore cartoon pictures one need to use line detection and heuristics.

The above works are computations on special domain of an image via pixel interpolation or extrapolation. With proper heuristics, structural information can be reconstructed to achieve a reasonable effect. However, sometimes, the resulting image is blurred. One drawback of the spatial domain approach is that textural information is hard to restore. The work discussed in uses a multi-resolution texture synthesis mechanism to combine both spatial and frequency information, which can achieve a better result to restore textures. Another example combining spatial and frequency information for restoration is also found in.

Algorithms discussed above are effective and efficient in restoring damages of small and discontinue areas. To restore damages of larger area, for instance, to remove a person from a picture, it is necessary to take another approach. Simple pixel interpolation or texture synthesis is not able to produce a visually pleasant result. One useful approach is to copy background information from the same picture to replace the selected area (e.g., a person). The exemplar-based synthesis approach computes a priority for each patch to be selected to inpaint the removed area. After a target area is inpainted, a confidence value is assigned or re-computed. The confidence values are them used for computing the next inpainting area. The following briefly summarizes the approach discussed in:

Let be the source region, Let be a manually selected target region and be the contour of ,

Repeat until region is empty
Compute boundary and priorities P
Propagate texture and structure information
Find patch on with highest priority P
Find patch in which minimizes Sum_of_Square_Difference
Copy to
Update confidence values

Essentially, is an area to be inpainted, with its contour Patches on this contour are associated with priorities (representing order to be inpainted). Useful patches from the source region are compared to partial patch on the contour. Best match is selected and copied to the candidate patch. In a few iterations, all candidate patches in the contour are inpainted. This concludes an inpainting step on the contour. The confidence values on inpainted patches are re-computed. And, the same inpainting procedure on the next contour continues, until the target region is empty.

The work discussed in also uses a confidence map (values) and adaptive neighborhood search (finding useful patch of the highest priority). In addition, the picture is refined from coarse level to fine level, which will take several iterations on the same inpainted area. The initial inpainted information relies on a fast estimation scheme known as the push-pull filtering method, to down-sample and up-sample the image in a multi-resolution hierarchically. The algorithm presented in is summarized below:

Let a’ be an inverse matte, with a conference value between 0 and 1 for each pixel For each scale from coarse to fine
Approximate image from color and coarser scale
Compute confidence map from a’ and coarser scale
Compute level set from confidence map
While mean confidence
For next target position
Compute adaptive neighborhood
Search for most similar and frequent source match
Composite and at , updating color and
Compute approximation, confidence map and update level set

Considering image inpainting form another perspective, inpainting technique can be used to attack visible watermarks . Even the mechanism can not completely remove the watermark, since the visible watermark is half transparent (i.e., watermark pixels are interpolated with underlying pixels), it is possible to extend this mechanism to recover aged photos with pasted Scotch taps (half transparent).

Next, an important issue related to image inpainting should be discussed. Most image inpainting algorithms rely on the user to explicitly select a region for repairing or object removal. This is due to the fact that detection of damaged area is hard to achieve automatically, especially on a single image (i.e., compared to motion picture with several images for cross reference). Damaged areas by ink or scratch are created naturally. It is not easy to separate these areas from a scene taken by a camera, which is created naturally as well. It is almost impossible to precisely distinguish the damages by a mathematical function precisely. However, a naive mechanism developed at Tamkang University is able to detect ink and scratch damages manually created (see Figures 3 and 4). The mechanism uses image processing techniques to find variation of color segments in the picture. With some heuristic rules, the mechanism is able to tell the type of damages (i.e., by ink or by scratch). The black/blue ink traces and scratch in Figures 3 and 4 (as well as other 100 pictures) are created on real photos and scanned for testing. Detected damaged areas are shown in red/yellow. However, there are limitations of the detection mechanism. Extra thin lines and small dots produced from scratch and ink are hard to detect. Ink damages of irregular shape can be mixed with natural objects of dark colors. We are taking a multi-resolution approach to solve the problem. With an improved detection mechanism, a fully automatic system can be implemented for repairing damaged photos in a digital library project.

Video Inpainting

Compared to image inpainting, video inpainting articles are rare to find in the literature. On the detection issue, video inpainting, however, focuses on detection of two types of noises: spikes of brightness and long vertical line of bright or dark intensity. These noises are generated in the process of film development or due to dirt (especially for aged video). The work discussed in estimates movements of small blocks using a reliable displacement map and detect spikes of small regions. Both temporal and spatial strategies are used in inpainting the spike region. Long vertical lines are detected and removed in . The mechanism is an improvement based on the Kokaram’s model.

Video inpainting can also be used to remove logos in a film. The mechanism assumes that video logos are small and in a fixed position in general. The location of logo is detected based on distribution of histogram energy. With logo position allocated, image inpainting mechanism can be used to remove the logo. The algorithm presented in is summarized as the following:

  • Select a logo region, and find the best logo frame using the following 4 steps:

    • Compute the grey-scale histogram of the selected region for all frames
    • Normalize the histogram
    • Calculate the histogram energy of every frame
    • Choose the frame with the maximum energy
  • Enhance and binarize the best logo frame to delineate the extract logo region
  • Inpaint on the logo region for all frames in the video sequence

Another video inpainting project is implemented at Tamkang University. The algorithm detects spikes of brightness based on intensity variation in the temporal domain. Spikes occur randomly with a typical duration of a few frames. Usually, spikes of brightness have color values very close to white color. The detected spikes are removed (inpainted) using information from both spatial and temporal domains. Best results, if any, are used from temporal domains since it is possible to recover the lost using the same object property (assuming that the moving object is inpainted). Otherwise, interpolation of pixels is applied using information in the same frame. Figure 5 show an example of spikes in an aged movie by Jacky Chen. The spikes, detected regions, and a restored frame are all shown in Figure 5. Most spikes are detected. However, the ratio of miss detection is increased if a threshold of spike size is set to very small. But, for incorrect detection, the detected small areas are inpainted as well. In general, the visual result, even with miss detections, is pleasant in the inpainted video as compared to seeing lots of spikes.

Holes Removal on 3-D Surfaces

Three dimensional scanners are important for creating avatars or models in virtual reality and augmented reality. However, due to many reasons, such as occlusions, low reflectance, scanner placement, lack of sufficient coverage, etc, 3-D surfaces produced from scanner may have holes. In most situations, watertight surfaces are required. Algorithms to overcome this problem in most scanners use triangulating boundaries calculation. However, it is possible to produce self-intersecting surfaces. A solution using volumetric diffusion was proposed in The algorithms proposed always produces closed, manifold triangle mesh without self-intersections.

Summary

Digital inpainting is part of multimedia computing research. This article summarizes inpainting techniques used in image, video, and 3D surfaces. Some techniques can be found in image processing literature (i.e., pixel interpolation). Others such as motion estimation algorithms can be found in video coding standard specifications. Digital inpainting techniques are useful and can be used in restoration of aged pictures and films. The approach is different from some signal processing mechanisms which eliminates noises by sacrificing quality of the original multimedia resource.

This interesting research area still has some issues that can be further investigated. For instance, it is possible that different categories of images (e.g., painting, photo, and cartoon drawing) require different inpainting strategies. Also, the assessment strategy needs to be investigated since PSNR values do not always reveal correct visual results. Human evaluation is necessary. For inpainting large blocks on images, it is not possible to inpaint properly unless semantics are considered. Also, exemplar-based technique can consider searching on patches from another picture instead of on the same picture. Thus, an image repository classified according to some semantic criteria is necessary. Most image inpainting tools allow users to select a solid region for inpainting. A fuzzy mask can be added to the region such that partial information from the damaged area can be used. Finally, there is no article of “audio inpainting” found in the literature. It will be interesting if audio inpainting can be used in radio signal transmission.

Digital Media Systems - Video Production, Film Production, Home Video and Audio, Broadcast Television, Digital Radio, Digital Cable, Digital Publishing [next] [back] Digital Image Processing - Introduction, Digital representation of images, Histogram, Arithmetical operations, Geometrical transformations, Neighborhood operations (convolution)

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or