07-08-2012, 04:27 PM
Digital image interpolation
Digital image interpolation.docx (Size: 3.43 MB / Downloads: 34)
INTRODUCTION
Digital image interpolation is the recovery of a continuous intensity surface from discrete image data samples. It is a link between the discrete world and the continuous one. In general, almost every geometric transformation requires interpolation to be performed on an image, e.g. translating, rotating, scaling, warping or other applications. Such operations are basic to any commercial digital image processing software. There are several issues which affect the perceived quality of the interpolated images: sharpness of edges, freedom from artifacts and reconstruction of high frequency details. We also seek computational efficiency, both in time and in memory. Classical techniques, such as pixel replication, bilinear or bicubic interpolation have the problem of blurred edges or artifacts around edges. Although these methods preserve the low frequency content of the sample image, they are not able to recover the high frequencies which provide a picture with visual sharpness. Standard interpolation methods are often based on attempts to generate continuous data from a set of discrete data samples through an interpolation function. These methods attempt to improve the ultimate appearance of re-sampled images and minimise the visual defects arising from the inevitable resampling error.
Traditionally, interpolation is accomplished through convolution of the image samples with a single kernel – typically a bilinear, bicubic1, or cubic B-spline2. A number of algorithms have been proposed to improve the magnification results. PDE-based approaches3 apply a nonlinear diffusion process controlled by the local gradient. POCS (Projection- Onto-Convex-Set) schemes4 formulate the interpolation as an ill-posed inverse problem and solve it by regularised iterative projection. Orthogonal transform methods focus on the use of the discrete cosine transform (DCT)5; 6. Directional methods7; 8 examine an image’s local structure around edge areas to direct the interpolation. Variational methods formulate the interpolation as the constrained minimisation of a functional9; 10.
It has been recognised that taking edge information into account will improve the interpolated image’s quality 11; 12; 13; 14 and it is known that the human visual system makes significant use of edges18. Instead of approaching interpolation as simply fitting the interpolation function, these methods consider also the geometry of the image. Li11 asserts that the quality of an interpolated image mainly de pends on the sharpness across the edge and the smoothness along the edge. Li et al.11 attempted to estimate local covariance characteristics at low resolution and used them to direct interpolation at high resolution (NEDI - New Edge Directed Interpolation) while Allebach et al.12 generated a high resolution edge map and used it to direct high-resolution interpolation (EDI - Edge Directed Interpolation). Battiato et al.13 proposed a method by taking into account information about discontinuities or sharp luminance variations while doing the interpolation. Morse et al.14; 15 presented a scheme that uses existing interpolation techniques as an initial approximation and then iteratively reconstructs the isophotes using constrained smoothing. They emphasise the importance of the “smoothness” quality, if the isophotes are not to be visually intrusive. As will shortly become clear, we too accept this need to fit the visual geometry. The above schemes demonstrate improved visual quality (in terms of sharpening edges or suppressing artifacts) by using a model to preserve the edges of the image and to tune the interpolation to fit the source model. However they are complex compared to traditional methods and thus computationally expensive.
Another approach is triangulation modelling. Triangulation has been an active research topic during the past decade. It is popular in geometric modelling. However, image reconstruction using triangles isn’t widely used, probably because of the large number of triangles needed. Yu et al.16 modelled images as data dependent triangulation meshes and reconstructed images from the triangulation mesh. Their approach adapted traditional data-dependent triangulation17
(DDT) with their new cost functions and optimisations. The data dependent triangulation thus matches the edges in the image and improves the reconstructed image. Their method is relatively complex and computationally expensive. We develop a new edge-directed method for image interpolation. We call this an image mesh DDT.We do not assume knowledge of the low-pass filtering kernel or attempt to find a statistical rule about the local geometry. Our approach is related to that of Yu but is simpler and faster because it does not involve any cost function or repeating optimisation process. Our mesh is very simple and completely regular. We avoid the complexity of a full DDT method while keeping the feature of DDT that improves the reconstruction quality. We will demonstrate our algorithm used in arbitrary magnification of still images and other applications.
2. Image Mesh Data-Dependent Triangulation
2.1. Principle of the Algorithm
We first consider the case that there is an edge passing between a square of four pixels. If this edge cuts off one corner, one pixel will have a value substantially different to the other three. We call this pixel the outlier. Imagine that we represent the brightness of the pixel as the height of a terrain. In effect, the three similar pixels define a plateau, relatively flat, while the outlier value is at the bottom of the cliff (if smaller) or the top of a peak (if higher) (Figure 1). This gives us a hint that if we want to interpolate a high resolution pixel within the relatively flat region we should not use the outlier. Classical interpolation methods like bilinear interpolation suffer from edge blurring because they use all four pixels to do interpolation. We only use three. The strength of employing triangles in this way is that we model edges in the image. In effect we tune the interpolator to match edges. In Figure 1, when interpolating the highresolution pixel falling in triangle abc, the interpolator won’t use the value of d which is very different to this plateau. For two pixels falling in different triangles, the height of the vertices will be quite different and thus the sharpness of the edge is kept. It is easy to see that in very smooth regions, the interpolator keeps smoothness as well, even across triangle boundaries.
This simple geometry suggest a way to guide the interpolation so that smoothness within the regions and sharpness between the flat region and cliff region can both be kept. If the diagonal is to correspond to the edge in the image, the diagonal should be the one which does not connect to the outlying pixel value, the one most different to the other three.
Suppose pixels a, b and c are the same height while d is higher than these three. Obviously a, b and c define a flat region while d is the most different pixel to the other three. Thus we connect diagonal ac and get the triangles abc and adc. In general, if b or d is the most different pixel, the edge should be ac, otherwise bd will be the edge. There are other situations if a and d are very different to b and c; or a and b are very different to c and d. In these cases it makes little difference which diagonal is chosen. The edge is roughly either horizontal (ad are different to bc) or vertical (ab are different to cd) and the triangle will always cross the edge.
It is similar to bilinear interpolation in these cases.
Obviously, using the diagonal to triangulate the four-pixel square cannot correspond to edges of arbitrary angle. The diagonal can only roughly represent the orientation of the edge. We could use sub-pixel triangulation to represent arbitrary angles, but that would add more complexity to the algorithm. Our aim is to keep the algorithm as simple as possible. We will demonstrate in this paper that triangulation by diagonal is enough in most situations and can provide excellent
results. It is the direction-selection method that is the key. Our method thus fits the finest triangular mesh to the source pixels. This “image mesh” is completely regular except that the diagonals are locally selected to run in the same general direction as any visible edge. To generate a new image, possibly at higher resolution, the target pixels are located in the source mesh. We then evaluate each target pixel from the triangle in which it sits. It is interpolated using only the information from the three triangle vertices. In edge areas, the interpolator won’t interpolate any two pixels that fall in different triangles. In other words, the new high-resolution image has the edges sharp and the smooth areas smooth.
2.2. Implementation and Optimisation
Suppose the low-resolution image is X and the highresolution image to be generated is Y. Our algorithm can be expressed as two steps. We first scan the sample image X to initialise a 2D array which records the edge direction of all four-pixel squares. In the second step we scan Y. For each yi j we inverse map to the sample image X and use the array to identify the triangle in which the point falls. Then we interpolate within that triangle to get the value of yi j. In the first step, the algorithm has to determine the outlier pixel. This has to be done repeatedly, so speed is important. Instead of finding the outlier directly, we compare the difference ja