A Comparison of Bilinear Interpolation, Cubic Convolution, and
Brownian Interpolation with Least Squares Matching
Jin-Tsong Hwang and Tian-Yuan Shih
Department of Civil Engineering
National Chiao-Tung University
Hsin-Chu, Taiwan,R.O.C.
Abstract
This study compares two fractal interpolation schemes based on fractional Brownian motion (fBm) with two convectional interpolation schemes: bilinear interpolation and cubic convolution. Numerical experiments are performed with a pair of digitized stereo photographs. The original image is reduced to a lower spatial resolution for interpolation. Both the geometric index based on the positioning accuracy of the image matching and the statistic indices such as the root mean square error, average error, maximum deviation, and correlation coefficient derived by comparing interpolated and the reference images indicate that the convectional interpolation schemes are better than the Brownian schemes.
Introduction
This paper examines four interpolation techniques: bilinear interpolation, cubic convolution, weighted Brownian interpolation (Polidori and Chorowicz, 1993), and the modified weighted Brownian interpolation derived in this study. The global statistic and geometric accuracy indices of the interpolated images generated by the four interpolation techniques are computed. The statistical indices include root mean square error (RMSE), average error Bias), correlation coefficient (), and maximum deviation, while the geometric index is the positioning accuracy derived from image matching. Two sampling schemes are also applies to reduce the test image into a lower spatial resolution. The first is decimation which takes the Nth pixel every N pixel. The other is averaging which takes the average of (N+1) x (N+1) window every N pixel. Numerical experiments are also performed with the SUBURB dataset provided by ISPRS Working Group III/3. This dataset includes a pair of digitized stereo photographs, as well as the DTM generated from this pair.
The Interpolation Schemes
Weighted Brownian Interpolation (polidori and chorowizc, 1993)
According to fBm (Mandelbort, 1983), the expected value of the difference in grayscale value over the distance dx is proportional to (dx)H where H is a constant and lies in the range 0<H<1, with a Gaussian distribution (Yokoya et al., 1989; Polidori and Chorowizc, 1993). The relationship between parameter H and fractal dimension D is in Equation (1).
D=3-H (1)
Parameter H can be determined by fitting a straight line with Equation (2):
Log(E[|Z(X+dx)-Z(X)|])=H.Log(dx)+K (2)
Where both H and K are constant. Equation (2) indicates that a plot of (E[|Z(X+dx)-Z(X)|]) as a function of dx on a log-log plot lies on a straight line and its slope is H (Yokaya et al., 1989).
Let
s2 be the variance of grayscale differences over a distance dx that equals one pixel in the input image. If the straight line are extended toward a shorter distance, the variance
s21/2 over a distance dx equal to ½ pixel could be obtained with Equation (3):
s21/2 =( 1/2 )2H s2 (3)
Further, the variance s2b obtained over ½ pixel by a bilinear interpolation is:
s2b=( 1/2 )2 s2 (4)
The weighted Brownian interpolation proposed by Polidori and Chorowicz (1993) adds a random term to the bilinear interpolation. The variance of the subsequent model is the difference between
s2b and
s21/2, as shown in equation (5) (Polidori and Chorowicz, 1993; Saupe, 198):
w2=( 1/2 )2H s2 - s2/4 (5)
Therefore,
For random addition, three parameters, w, G, and R, are expressed in Equation (7):
Z(i,j)=Zb(i,j)+ wGR (7)
Where Z
b(i,j) is the result of bilinear interpolation, G is the Gaussian random variable with a zero mean and unit standard deviation, and R is the correlation coefficient between dx and (E[|Z(X+dx)-Z(X)|])) in the log-log coordinate system. Also, R equals one when the log-log plot yields a straight line. The more the image deviates from the Brownian model implies a smaller R (polidori and Chorowicz, 1993). Because the significance of fractal phenomenon differs from area to area, the purpose of using R is to model the variation of "fractalness".
Term
w, as described in Equation (6), is formulated with
s and H. The two parameters and R are called " fractal factors" in this paper. The image is divided into M*M blocks and each block has N*N pixels. Fractal factors are computed for each block. Then the image is interpolated on the basis of equation (7) block by block with the corresponding
s, H, and R. Considering both the computing effect and local representation using the window is inappropriate. Polidori and Chorowicz (1993) recommended using the window size of 13*13 pixel.
Modified Weighted Brownian Interpolation
The term G in Equation (7) is extended to include a thresholding procedure, and is then denoted as GT, as shown in Equation (8):
Z(i,j)=Zb(i,j)+ wGTR (8)
The random numbers generated are accepted only if they are within the thresholding interval. This thresholding procedure is designed to provide another mechanism to effectively control the added fractal-enhancement components.
