Fast Bernstein function interpolation algorithm for image manipulation
This study examines the application of Bernstein function interpolation to image data, and specifically examines techniques for accelerating the interpolation process. Bernstein interpolation requires inverting a full n x n matrix, where n is the size of a row or column in the image, and this must be done for each row and column in the image in the case of one-dimensional interpolation. In the dissertation, a block decomposition algorithm is examined which can substantially accelerate the inversion process while keeping the quality of the scaled image high. In this algorithm each row and column of the image is broken into multiple blocks. Instead of interpolating a row or column, multiple small blocks are interpolated, significantly accelerating the process. Because of the equal size of the most blocks in both rows and columns, a Bernstein basis has been constructed. Then, each block, except for trailing blocks, of each row and column, is the linear combination of a Bernstein basis. Therefore, only a few unit vectors are interpolated to construct a Bernstein basis instead of interpolating all image data. This reduces the computational time due to interpolation by more than tens. While blocking and Bernstein Bases accelerate the interpolation process, they cause problems associated with discontinuities between neighboring blocks. The issue of discontinuities and techniques to solving this problem are addressed in depth in the dissertation. Preserving edge is a very important issue for any image operation algorithm. This study gives a preliminary investigation on this issue. Edge detection is done by traditional partial derivatives and edge preservation is done by tuning values of the diffusion number of the Bernstein function interpolation. Two dimensional Bernstein function interpolation is also addressed, which is meant to be extended to other applications.