A Low Complex Selective Block Correlation for Video Frame Interpolation

This paper presents a new frame interpolation technique based on correlation between non overlapping macro blocks. The proposed algorithm generates correlation values and identifies the median value as threshold amongst them. The blocks with correlation less than threshold are linearly interpolated. By linear interpolation between blocks reduces artifacts due to occlusions and holes caused by Motion Vector (MV) processing. Our algorithm decreases the computational complexity to minimum. Experimental results demonstrate that our proposed algorithm performs well in terms of SSIM and computational complexity compared to existing algorithms.


Introduction
Over a decade more, video communication has drawn more attention than image communication. In video communication, video compression, video encoding, video transmission and video decoding are different stages. At each stage, the basic operation is done at video frame level. Frame reconstruction or frame interpolation (FI) is done at receiver/decoder side. The FI process is based on Block Based Motion Estimation (ME) with Motion Compensation (MC) techniques. The FI is also known as Frame Rate Up Conversion (FRUC). There are various FI algorithms. These algorithms tradeoff between computational complexity and interpolated frame quality. The Motion Compensated Frame Interpolation (MCFI) algorithms uses Block Matching Algorithms (BMA) for ME to create Motion Vector (MV), which is used for estimating motion trajectory. This estimation results in translational motion between frames which helps in missing blocks interpolation. Frame Interpolation increases temporal resolution of video frames by interpolating new frames into original sequence. In band limited video temporal down sampling reduces video bit rates. At receiver FI restores the skipped temporal frame. In MCFI process ME, MV Smoothing and MC Interpolation (MCI) are the steps. ME and MV smoothing steps provide MV. By MCI step, the pixels of the frame to be interpolated are estimated from pixels of low frame rate video. Objects in motion are categorized based on (a) Static background (b) Moving object (c) Uncovered background or region and (d) Newly covered background or region [7]. The categories (c) and (d) results in occlusions. In order to get true FI, MVs are classified for reliability and merged using reliability map in [1] with vector median filter. The MVs are correlated in MV Processing (MVP) in the algorithm [2] used for reducing artifacts in occluded areas. The MVs at pixel level, block level and sequence level are exploited to reduce artifacts in [3]. This algorithm increases computational complexity. Using available MVs, estimating true Motion Estimation is proposed in [4] to track the projected object motion. The occlusions are reduced by using four intermediate frames thus increasing computational complexity in FRUC based on Variational Image Fusion (VIF) in [5]. The [6] proposes prediction based vector smoothing, partial average based MC and hole interpolation based on motion outliers. Based on artifacts information, MVP of MV Field (MVF) is proposed in [7] with complexity. In [9] optical flow is a part of complexity [10] and three frames are used to interpolate a single frame. In this paper, we propose the FI method with minimum complexity and can be implemented at the receiver. As in MCFI, block processing stage is used while ME and MC stages are not used. Correlation and a selective block processing with linear interpolation stages are embedded in FI process to reduce complexity. Frame regions or blocks are matched based on correlation. This technique can be used widely because of simplicity in implementation and aptness for large motion regions. Frame is divided into regions of pixels called blocks. The size of block is varied as per technique. The hard motion constraint doesn't reflect real motion perfectly for rigid and non-rigid motion. This parameter defines the size of blocks. If large block size is selected real motion can't be represented while small blocks may not include enough indication for unique identification of motion.

Framework of Proposed Algorithm
In our method, we considered different video sequences. Each video sequence is converted into frames. The frame is divided into non overlapping blocks. The block size is determined by number of pixels. The number of pixels in a block is varied in terms of power of two. The block partitioning is limited by frame resolution. It is obvious that the block size can be increased from a minimum to maximum determined by height or width dimension of a frame. Thus, obtained blocks of same size of different frames are used for further processing. Let current frame be ft, previous frame be ft-1 and next frame be ft+1. The previous and next frames are used to interpolate the current/intermediate frame. The previous and next frames are partitioned into blocks of same size. The corresponding blocks in these frames are correlated. The median of the correlated values is generated and is Threshold value. The group of correlation values, which are less than median value, are grouped as Less Than Threshold (LTT) values group. The correlated blocks which fall into LTT group are linearly interpolated. On the other hand, the correlated values greater than median value are grouped as Greater Than Threshold(GTT) values group. The intermediate frame is interpolated using the blocks, of LTT group, which are linearly interpolated pixel wise and the remaining from GTT group blocks of next frame. Our proposed method is described in the flow chart as in figure 1.

Principles in Proposed Method
In this method, we proposed to interpolate a video frame using previous and next frames of the to be interpolated frame. A video sequence is converted into frame. Each individual frame is divided into blocks of different sizes. The size of a block is determined by number of pixels. The number of pixels considered per block are in power of two i.e., 16, 32, 64, 128, 256 and 512 pixels. The number of blocks per frame is restricted by the intrinsic frame resolution and number of pixels per block. The steps in block generation are (1) If block size is less than or equal to row size, block size is row size (2) if block size is greater than row size, all values from minimum of row/10 and block size/2 to block size are used, so that minimum padding is required. Correlation is used in our proposed method to find similarity measure between the blocks. Corresponding blocks in previous and next frame are correlated. The correlation operation is simple, easy to implement and powerful operation that brings out similarity measure because of linearity and shift-invariance properties. Correlation is applied on every pixel in the corresponding blocks. Correlation will be high when the blocks are perfectly matched and will be low when blocks are mismatched. If the pixel intensity value is high, the correlation will also be high independent of pixel matching nature. This is disadvantage of simple correlation. Hence, we used normalized correlation given by (1) Thus, in our proposed correlation process, the similarity measure ranges between +1 and 0 indicating highly correlated and poorly correlated blocks respectively. All the block correlated values are stored. As a next step in our proposed method, the median amongst the correlated values is generated and is designated as threshold. The quality assessment is done in Full-Reference (FR) mode i.e., interpolated frame is compared with available original frame by metrics Peak Signal to Noise Ratio (PSNR) and Structural Similarity Index (SSIM). Video Quality Metrics Video Quality Measures are of Objective and Subjective types. In this paper we considered objective type criterion which gives the measure of difference between the original and the reconstructed or processed. Mean Squared Error (MSE) is the simple and basic quality measure which is given as Where 'N' is number of pixels per frame 'x' is row dimension of frame, 'y' is column dimension of frame and 't' is time or temporal dimension.
PSNR is one of the benchmarks for performance evaluation of objective video quality metrics. It is dependent on estimation of spatial alignment, temporal alignment, gain and level offset between interpolated frame and original frame.
In human beings, color sensation is attributed by Luminance and Chrominance. Chrominance is attributed by Hue and Saturation. Hue is defined as color tone which is dependent on peak wavelength of the light. Saturation is defined as purity of color which is dependent on bandwidth of light spectrum. The structural information of an image is modeled by SSIM quality metric. The structural information change in SSIM defines the image degradation. Luminance, Contrast and Structure comparison are the steps in similarity measurement. Symmetry, Boundedness and Unique maximum are properties of SSIM. SSIM is defined as where l(x,y) is the luminance at (x,y) location, c(x,y) is the contrast at (x,y) location , s(x,y) is the structural comparison at (x,y) location.

Experimental Results and Discussion
The test sequences are classified into 4 types as tabulated in Table 1.  288 ) format. In generality adapted by researchers, even frames in these sequences were removed and interpolated using neighboring odd frames. In our proposed method, each frame was divided into non-overlapping blocks. For CIF format videos maximum block size is 256 x 256 pixels. In proposed method corresponding blocks in odd frames are considered for interpolating that corresponding block of even frame. The interpolated blocks are augmented in their respective locations .Objective Assessment (OA) of our proposed method was done by using the metric Structural Similarity Index Measurement (SSIM). For each even frame interpolated, original/skipped even frame was used as reference in calculating SSIM. Results of SSIM are tabulated in Table 1.  Table 2, it can be observed that Football, Highway and Tennis sequences had the highest OA at 16 pixel block size. The Highway and News sequences had the highest OA at 32 pixel block size. The 64 pixel size had the best OA for Foreman and Soccer sequences. Garden and Stefan sequences produced best OA with block size of 128 pixels.

Computational Complexity
To maintain generality, the frame dimensions were considered as N×N pixels. Each frame is divided into B sized blocks. The correlation had Sum of Absolute Difference(SAD), as shown in MSE. The number of SAD operations determined the computational complexity of the algorithm. As MVP was not used in our proposed method the search window (W) parameter was discarded. The patch (p) size was included in calculation by [9]. The benchmark FI algorithm complexity is tabulated in table 4.  Table 4, it can be understood that our proposed method has the least computational complexity. The number of computations for the video sequences were graphically represented as in figure3.

C O M P U T A T I O N A L C O M P L E XI T Y Conclusion
In this paper we proposed, correlation of blocks in frames for frame interpolation. Since the motion between frames was linear and correlated highly, interpolating a frame using both end frames had minimum complexity. Our method could interpolate an even ordered frame using neighboring odd ordered frames with minimum complexity. Our experimental results demonstrated that our proposed method performed better in terms of objective assessment SSIM and with minimum computational complexity than other methods.