# Frame Interpolation Based on Visual Correspondence and Coherency Sensitive Hashing

Authors: Lingling Zi; Junping Du; Qian Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The technology of frame interpolation can be applied in intelligent monitoring systems to improve the quality of surveillance video. In this paper, a region-guided frame interpolation algorithm is proposed by introducing two innovative improvements. On the one hand, a detection approach is presented based on visual correspondence for detecting the motion regions that correspond to attracted objects in video sequences, which can narrow the prediction range of interpolated frames. On the other hand, spatial and temporal mapping rules are proposed using coherency sensitive hashing, which can obtain more accurate predicted values of interpolated pixels. Experiments show that the proposed method can achieve encouraging performance in terms of visual quality and quantitative measures.


---

## Body

## 1. Introduction

Frame interpolation plays a very important role in intelligent monitoring systems. This technology can not only increase the frame rate of surveillance video to meet the requirements of monitoring display devices [1] but also forecast the missing frames to obtain smooth surveillance video. The essence of frame interpolation is to predict intermediate frames by using two given frames in video sequences [2], and it can be roughly divided into two categories: the optical flow method and the block matching method. The former uses time-domain variation and correlation of pixel intensity data to determine the location and value of each pixel [3]. However, in practice, because of the existence of a variety of factors such as multiple light levels, transparency, and noise, assumptions of brightness constancy and spatial smoothness in the optical flow basic equations cannot be always satisfied [4, 5]. The latter finds the best match for each block by minimizing the matching difference [6, 7]. Due to its simplicity, this method is easy to implement, but blocking artifacts will occur in the interpolation frames [8]. In brief, these existing methods still suffer from poor quality of video frames. Therefore, it would be beneficial to develop an algorithm to obtain high-quality interpolation frames.In this paper, a novel region-guided frame interpolation algorithm (RGFI) is proposed, the goal of which is to improve the definitions of intermediate frames of the surveillance video. To achieve this, two techniques are introduced for frame interpolation. The first technique is visual correspondence using local descriptor matching [9, 10]. For this purpose, compact real-time descriptors (CARD) [11] are used, an approach which was proposed recently to establish visual correspondence quickly between two images. Moreover, the computation time of each descriptor is approximately 16 times faster than that of the scale-invariant feature transform (SIFT) [12]. The second technique is the latest approximate nearest neighbor (ANN) method [13], called coherency sensitive hashing (CSH) [14], which was proposed to find matching patches quickly. CSH relies on hashing to propagate information through similarity in appearance space and neighborhood in the image plane. Its advantage is the use of special observations to establish candidate block sets, which can avoid many artifacts along edges when reconstructing an original image. Through the advanced techniques described above, the interpolation task for video sequences is achieved satisfactorily from a different perspective.The main contributions of this paper can be summarized as follows:(1) a novel and comprehensive frame interpolation framework based on spatial and temporal correlations in video sequences and (2) a detection approach based on visual correspondence to capture motion regions so as to narrow the prediction range of interpolation frames. The foundation of the detection approach is the frame difference technique and CARD technique, (3) the spatial and temporal block definition and spatial and temporal mapping relationship definition for better implementation of the RGFI algorithm. On this basis, this approach is combined with CSH to construct spatial and temporal mapping rules so as to predict values of interpolated pixels accurately, (4) application of the proposed algorithm to video resizing. Using accurate motion regions obtained in the proposed algorithm, the important content in the surveillance video can be preserved on the premise of ensuring global visual effect and can be displayed on the monitoring display devices with different resolutions.The rest of the paper is structured as follows. Section2 provides an overview of the proposed RGFI algorithm. Section 3 demonstrates the implementation details of RGFI. Section 4 presents experimental work carried out to demonstrate the effectiveness of the algorithm. Section 5 shows another contribution of our algorithm. Section 6 concludes the paper.


## 2. RGFI Overview

In this paper, a novel RGFI algorithm is proposed according to characteristics of video sequences. The RGFI framework is shown in Figure1 and is divided into motion region detection and interpolated pixel computation. First, the detection approach using visual correspondence to capture motion regions is presented. Then the spatial and temporal mapping scheme based on CSH is demonstrated to compute the unknown pixel values in the motion regions obtained. At the same time, for the pixels of other regions of input video frames, only the original values are kept. Through these two steps, high-quality interpolation frames are produced.Figure 1
Architecture of the proposed algorithm.


## 3. Implementation of RGFI

### 3.1. Motion Region Detection Using Visual Correspondence

The motion regions of the surveillance video are very important in the intelligent monitoring system. Therefore, by finding these regions, it is possible to speed up the accomplishment of the interpolation task. Unlike previous methods, the method proposed here takes advantage of visual correspondences based on CARD to obtain motion regions between video frames. The detailed implementation of the detection approach includes three parts: motion region initial estimation, key point correspondence establishment, and motion region determination.Because the frame difference method [15] can quickly find the outline of the moving target in video sequences, it is first used to estimate rough motion regions, as shown in the following:
(1)Ii(x,y)∈Mn′,if|fn+1(x,y)-fn(x,y)|≥Dn×c,
where fn(x,y) and fn+1(x,y) denote the two consecutive frames of the input video sequences, Mn′ is the initial motion region corresponding to fn(x,y), c is a predefined value, and Dn is the difference between the maximum value and the minimum value in two consecutive frames as follows:
(2)Dn=max|fn+1(x,y)-fn(x,y)|-min|fn+1(x,y)-fn(x,y)|.Second, inspired by [11], comparatively accurate key point correspondences are established in the initial motion regions; the establishment process includes the following four steps.Step  1.  Construct an image pyramid [16] for the initial regions as follows:
(3)L(xm,ym,n,σ-1)=L2↓(xm,ym,n,σ),
where L(xm,ym,n,σ) is a scale function, xm and ym are the values of the abscissa and the ordinate, σ is the level of the image pyramid, and 2↓ is the downsampling factor.Step  2.  A corner detector technique [17] is used to find the key points in the image pyramid, and the corresponding point set is denoted as Kn={kn(xk1,yk1)∣(xk1,yk1)∈Mn′}. Similarly, the key point set Kn+1 corresponding to the initial region Mn+1′ of fn+1(x,y) is obtained.Step  3.   For ∀kn′(xi,yi)∈(Kn∪Kn+1), the orientation histogram HG(hkn′) is determined; the corresponding magnitudes and orientations are given in (4). At the same time, log-polar binning is used to achieve good discrimination ability [18], as follows
(4)mHG(xi,yi)=((Mn′(xi+1,yi)-Mn′(xi-1,yi))2+(Mn′(xi,yi+1)-Mn′(xi,yi-1))2)1/2,ωHG(xi,yi)=arctg((Mn′(xi+1,yi)-Mn′(xi-1,yi))(Mn′(xi,yi+1)-Mn′(xi,yi-1))),(5)rk,n′={0,0≤ui2+vi2<φ11+Q8(arctg(uivi)-(2π(lkmodL))L),mmmmmmmmmmlmφ1≤ui2+vi2<φ29+Q8(arctg(uivi)-(2π(lkmodL))L),mmmmmmmmmmlmφ2≤ui2+vi2<φ3,
where rk,n, denotes a rotated binning pattern, L is a predefined value, φ1, φ2, and φ3 are constants, ui and vi denote the coordinate values of kn′(xi,yi) in relative coordinates, QF(θ) represents the quantization function, given in (6), and lk denotes the quantization result of ωHG(xi,yi). On this basis, a spatial binning table [19] is used to extract HG(hkn′) and to obtain the descriptor dkn of kn′(xi,yi), setting the descriptor set Dkn(6)QF(θ)=⌊Fθ+π2π⌋modF.Step  4. For ∀dkn(dkn∈Dkn), compute its corresponding descriptor dmn+1 in the next frame according to the following:
(7)dmn+1=argmindin+1∈Dkn+1disc(din+1-dkn)dmn+1=argmindin+1∈Dkn+1∥din+1-dkn∥1dmn+1=argmini∈Kn(∑j=1C|δin+1(j)-δkn(j)|)δkn=(1+sgn(WTdkn))2,
where δkn is the changed short binary code of any descriptor dkn, C is the length of changed binary code, and W is a weight matrix. In this way, the corresponding set Dmn+1 of descriptor set Dkn and the matching key point Km of Kn can be obtained.Finally, more accurate boundary values for the motion regions can be determined according to the locations of key points and their correspondences between consecutive frames. LetK=Kn∪Km; the boundary values of motion region Mn can then be computed using the following equation:
(8)MLn=minkn(xin,yin)∈Kxin-εL,MRn=maxkn(xin,yin)∈Kxin+εR,MTn=minkn(xin,yin)∈Kyin-εT,MBn=maxkn(xin,yin)∈Kyin+εB,
where MLn, MRn, MTn, and MBn are the left border, right border, top border, and bottom border and εL, εR, εT,  and εB are the predefined minimal deviation values.Figure2 shows one example of motion region detection. Figures 2(a) and 2(b) are the two consecutive frames of the walk video, and the key point correspondences between them are presented. From the results for the motion region shown in Figure 2(c), it is evident that the proposed detection approach can perform well in expressing the motion content of video sequences, which lays the foundation for interpolated pixel computation.One example of motion region detection. The first two figures from the left show the two consecutive images of the walk video; red lines are used to denote key point correspondences. Marked with yellow lines, the obtained motion region in the last figure contains key points denoted by blue dots.
(a)
(b)
(c)


### 3.2. Interpolated Pixel Computation Using Coherency Sensitive Hashing

To facilitate the computation of interpolated pixels, it is necessary to define some concepts in advance.Definition 1.
For obtained motion regions in two consecutive frames, the original motion regionMn and the mapping motion region Mn+1 are defined. Mn or Mn+1 is divided into s×s overlapping image blocks, and each block is defined as a spatial and temporal block, ST for short. Denote the total numbers and sets of ST as TMn,  TMn+1, and Bn={bkn},  Bn+1={bkn+1}, respectively.Definition 2.
Given∀bkn(bkn∈Bn),  assume that bln+1(bln+1∈Bn+1) is the corresponding mapping block of bkn and that it is computed through spatial and temporal mapping rules. Then bkn↦bln+1 is defined as the spatial and temporal mapping relationship between bkn and bln+1.As far as is known, the block matching method generally finds the only match for each original divided block. However, the computation method proposed here can obtain two or more matching blocks for each ST so as to approach more closely the true values of interpolated pixels. This computation method includes four parts: ST projection and conversion, mapping block computation, nearest block determination, and unknown pixel computation.First, the projection of ST is computed on Walsh-Hadamard kernels [20]. Specifically, for each ST bj, bj∈(Bn∪Bn+1), gray-code filter kernels [21] are computed as the transform kernel, as shown in (9) and Figure 3. The results are stored in the temporary set H={WHTj∣1≤j≤TN}, in which TN=TMn+TMn+1:
(9)Vs1(0)=Vs2(0)=1Vs1(k)={[vs1(k-1)αkvs1(k-1)]}Vs2(k)={[vs2(k-1)αkvs2(k-1)]}Vs(k)=Vs1(k)×Vs2(k)s.t.vs1(k-1)∈Vs1(k),Vs(k)=vs2(k-1)∈Vs2(k),αk∈{+1,-1}.Figure 3
Tree scheme for computing projections of a 2D signal onto WH kernels of order 8. In the Walsh-Hadamard kernel array, yellow denotes the value 1 and blue denotes the value −1.To accelerate ST mapping, a hash value is assigned to each transform result, and each hash functionha,b(WHj):Rdim→N maps a dim-dimensional vector WHj onto the set of integers [22]. In this way, the corresponding hash table tm(1≤m≤TN) is constructed, and each ST is saved in the entry tm[gm(bj)], in which gm(bj) is given by the following:
(10)gm(bj)=WHT1·bj+ρ1γ∘WHT2·bj+ρ2γ∘⋯∘WHTj·bj+ρjγ∘⋯∘WHTTN·bj+ρTNγ.
In (10), γ is a fixed integer value which is set in advance and ρj is a random number according to a uniform distribution on the interval [0,γ). At the same time, for the two vectors WHl, WHl′, let c=∥WHl-WHl′∥p; they are hashed to the same value with probability P(c):
(11)P(c)=Pra,b[ha,b(WHl)=ha,b(WHl′)]=∫0r1cfp(tc)(1-tr)dt.Then spatial and temporal mapping rules are established for ST to expand the number of mapping blocks of ST. Here four mapping rules are established, shown as Rules1–4. The first three mapping rules take advantage of a coherency sensitive hashing technique [14] to mine spatial correlations between frames, and Rule 4 makes direct use of temporal correlations of video sequences.Rule 1.
Ifgm(bkn)=gm(bln+1), then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1.Rule 2.
Ifleft(bkn)↦bln+1, then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1, and left(bkn) is the left neighboring block of bkn.Rule 3.
Ifgm(bkn)=gm(bk′n) and  bk′n↦bl′n+1, then bkn↦bl′n+1, where bkn∈Bn, bk′n∈Bn, bl′n+1∈Bn+1.Rule 4.
If the coordinate values of the upper left corner ofbkn are equal to those of bln+1, then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1.The third step is to determine the nearest blocks from the obtained mapping blocks of ST. Here a freedom search technique [8] using the patchmatch method is used to initialize the nearest blocks for each ST as follows:
(12)bnearn+1=bkn+wαiRi.
In (12), Ri∈[-1,1]×[-1,1], α is a constant value, w is a search radius, and bnearn+1 is the best block of any ST bkn. Then for each hash table, (13) is used to compare and update the nearest blocks:
(13)bnearn+1=bmapn+1,ifdisc(bkn,bmapn+1)<disc(bkn,bmapn+1).Finally, the predicted value of the pixels in the ST can be computed through a smoothing operation for the nearest blocks obtained as follows:(14)I′(xi,yi)=(∑j=1|An(bkn)|I(xjn+1,yjn+1))|An(bkn)|,
where I′(xi,yi) denotes the predicted value of an interpolated pixel, An(bkn) is the nearest blocks set of bkn, I(xjn+1,yjn+1)∈bjn+1, and bjn+1∈An(bkn). In addition, to obtain color frame interpolation, the R, G, and B channel values of each pixel can be computed in the same way.


## 3.1. Motion Region Detection Using Visual Correspondence

The motion regions of the surveillance video are very important in the intelligent monitoring system. Therefore, by finding these regions, it is possible to speed up the accomplishment of the interpolation task. Unlike previous methods, the method proposed here takes advantage of visual correspondences based on CARD to obtain motion regions between video frames. The detailed implementation of the detection approach includes three parts: motion region initial estimation, key point correspondence establishment, and motion region determination.Because the frame difference method [15] can quickly find the outline of the moving target in video sequences, it is first used to estimate rough motion regions, as shown in the following:
(1)Ii(x,y)∈Mn′,if|fn+1(x,y)-fn(x,y)|≥Dn×c,
where fn(x,y) and fn+1(x,y) denote the two consecutive frames of the input video sequences, Mn′ is the initial motion region corresponding to fn(x,y), c is a predefined value, and Dn is the difference between the maximum value and the minimum value in two consecutive frames as follows:
(2)Dn=max|fn+1(x,y)-fn(x,y)|-min|fn+1(x,y)-fn(x,y)|.Second, inspired by [11], comparatively accurate key point correspondences are established in the initial motion regions; the establishment process includes the following four steps.Step  1.  Construct an image pyramid [16] for the initial regions as follows:
(3)L(xm,ym,n,σ-1)=L2↓(xm,ym,n,σ),
where L(xm,ym,n,σ) is a scale function, xm and ym are the values of the abscissa and the ordinate, σ is the level of the image pyramid, and 2↓ is the downsampling factor.Step  2.  A corner detector technique [17] is used to find the key points in the image pyramid, and the corresponding point set is denoted as Kn={kn(xk1,yk1)∣(xk1,yk1)∈Mn′}. Similarly, the key point set Kn+1 corresponding to the initial region Mn+1′ of fn+1(x,y) is obtained.Step  3.   For ∀kn′(xi,yi)∈(Kn∪Kn+1), the orientation histogram HG(hkn′) is determined; the corresponding magnitudes and orientations are given in (4). At the same time, log-polar binning is used to achieve good discrimination ability [18], as follows
(4)mHG(xi,yi)=((Mn′(xi+1,yi)-Mn′(xi-1,yi))2+(Mn′(xi,yi+1)-Mn′(xi,yi-1))2)1/2,ωHG(xi,yi)=arctg((Mn′(xi+1,yi)-Mn′(xi-1,yi))(Mn′(xi,yi+1)-Mn′(xi,yi-1))),(5)rk,n′={0,0≤ui2+vi2<φ11+Q8(arctg(uivi)-(2π(lkmodL))L),mmmmmmmmmmlmφ1≤ui2+vi2<φ29+Q8(arctg(uivi)-(2π(lkmodL))L),mmmmmmmmmmlmφ2≤ui2+vi2<φ3,
where rk,n, denotes a rotated binning pattern, L is a predefined value, φ1, φ2, and φ3 are constants, ui and vi denote the coordinate values of kn′(xi,yi) in relative coordinates, QF(θ) represents the quantization function, given in (6), and lk denotes the quantization result of ωHG(xi,yi). On this basis, a spatial binning table [19] is used to extract HG(hkn′) and to obtain the descriptor dkn of kn′(xi,yi), setting the descriptor set Dkn(6)QF(θ)=⌊Fθ+π2π⌋modF.Step  4. For ∀dkn(dkn∈Dkn), compute its corresponding descriptor dmn+1 in the next frame according to the following:
(7)dmn+1=argmindin+1∈Dkn+1disc(din+1-dkn)dmn+1=argmindin+1∈Dkn+1∥din+1-dkn∥1dmn+1=argmini∈Kn(∑j=1C|δin+1(j)-δkn(j)|)δkn=(1+sgn(WTdkn))2,
where δkn is the changed short binary code of any descriptor dkn, C is the length of changed binary code, and W is a weight matrix. In this way, the corresponding set Dmn+1 of descriptor set Dkn and the matching key point Km of Kn can be obtained.Finally, more accurate boundary values for the motion regions can be determined according to the locations of key points and their correspondences between consecutive frames. LetK=Kn∪Km; the boundary values of motion region Mn can then be computed using the following equation:
(8)MLn=minkn(xin,yin)∈Kxin-εL,MRn=maxkn(xin,yin)∈Kxin+εR,MTn=minkn(xin,yin)∈Kyin-εT,MBn=maxkn(xin,yin)∈Kyin+εB,
where MLn, MRn, MTn, and MBn are the left border, right border, top border, and bottom border and εL, εR, εT,  and εB are the predefined minimal deviation values.Figure2 shows one example of motion region detection. Figures 2(a) and 2(b) are the two consecutive frames of the walk video, and the key point correspondences between them are presented. From the results for the motion region shown in Figure 2(c), it is evident that the proposed detection approach can perform well in expressing the motion content of video sequences, which lays the foundation for interpolated pixel computation.One example of motion region detection. The first two figures from the left show the two consecutive images of the walk video; red lines are used to denote key point correspondences. Marked with yellow lines, the obtained motion region in the last figure contains key points denoted by blue dots.
(a)
(b)
(c)


## 3.2. Interpolated Pixel Computation Using Coherency Sensitive Hashing

To facilitate the computation of interpolated pixels, it is necessary to define some concepts in advance.Definition 1.
For obtained motion regions in two consecutive frames, the original motion regionMn and the mapping motion region Mn+1 are defined. Mn or Mn+1 is divided into s×s overlapping image blocks, and each block is defined as a spatial and temporal block, ST for short. Denote the total numbers and sets of ST as TMn,  TMn+1, and Bn={bkn},  Bn+1={bkn+1}, respectively.Definition 2.
Given∀bkn(bkn∈Bn),  assume that bln+1(bln+1∈Bn+1) is the corresponding mapping block of bkn and that it is computed through spatial and temporal mapping rules. Then bkn↦bln+1 is defined as the spatial and temporal mapping relationship between bkn and bln+1.As far as is known, the block matching method generally finds the only match for each original divided block. However, the computation method proposed here can obtain two or more matching blocks for each ST so as to approach more closely the true values of interpolated pixels. This computation method includes four parts: ST projection and conversion, mapping block computation, nearest block determination, and unknown pixel computation.First, the projection of ST is computed on Walsh-Hadamard kernels [20]. Specifically, for each ST bj, bj∈(Bn∪Bn+1), gray-code filter kernels [21] are computed as the transform kernel, as shown in (9) and Figure 3. The results are stored in the temporary set H={WHTj∣1≤j≤TN}, in which TN=TMn+TMn+1:
(9)Vs1(0)=Vs2(0)=1Vs1(k)={[vs1(k-1)αkvs1(k-1)]}Vs2(k)={[vs2(k-1)αkvs2(k-1)]}Vs(k)=Vs1(k)×Vs2(k)s.t.vs1(k-1)∈Vs1(k),Vs(k)=vs2(k-1)∈Vs2(k),αk∈{+1,-1}.Figure 3
Tree scheme for computing projections of a 2D signal onto WH kernels of order 8. In the Walsh-Hadamard kernel array, yellow denotes the value 1 and blue denotes the value −1.To accelerate ST mapping, a hash value is assigned to each transform result, and each hash functionha,b(WHj):Rdim→N maps a dim-dimensional vector WHj onto the set of integers [22]. In this way, the corresponding hash table tm(1≤m≤TN) is constructed, and each ST is saved in the entry tm[gm(bj)], in which gm(bj) is given by the following:
(10)gm(bj)=WHT1·bj+ρ1γ∘WHT2·bj+ρ2γ∘⋯∘WHTj·bj+ρjγ∘⋯∘WHTTN·bj+ρTNγ.
In (10), γ is a fixed integer value which is set in advance and ρj is a random number according to a uniform distribution on the interval [0,γ). At the same time, for the two vectors WHl, WHl′, let c=∥WHl-WHl′∥p; they are hashed to the same value with probability P(c):
(11)P(c)=Pra,b[ha,b(WHl)=ha,b(WHl′)]=∫0r1cfp(tc)(1-tr)dt.Then spatial and temporal mapping rules are established for ST to expand the number of mapping blocks of ST. Here four mapping rules are established, shown as Rules1–4. The first three mapping rules take advantage of a coherency sensitive hashing technique [14] to mine spatial correlations between frames, and Rule 4 makes direct use of temporal correlations of video sequences.Rule 1.
Ifgm(bkn)=gm(bln+1), then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1.Rule 2.
Ifleft(bkn)↦bln+1, then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1, and left(bkn) is the left neighboring block of bkn.Rule 3.
Ifgm(bkn)=gm(bk′n) and  bk′n↦bl′n+1, then bkn↦bl′n+1, where bkn∈Bn, bk′n∈Bn, bl′n+1∈Bn+1.Rule 4.
If the coordinate values of the upper left corner ofbkn are equal to those of bln+1, then bkn↦bln+1, where bkn∈Bn, bln+1∈Bn+1.The third step is to determine the nearest blocks from the obtained mapping blocks of ST. Here a freedom search technique [8] using the patchmatch method is used to initialize the nearest blocks for each ST as follows:
(12)bnearn+1=bkn+wαiRi.
In (12), Ri∈[-1,1]×[-1,1], α is a constant value, w is a search radius, and bnearn+1 is the best block of any ST bkn. Then for each hash table, (13) is used to compare and update the nearest blocks:
(13)bnearn+1=bmapn+1,ifdisc(bkn,bmapn+1)<disc(bkn,bmapn+1).Finally, the predicted value of the pixels in the ST can be computed through a smoothing operation for the nearest blocks obtained as follows:(14)I′(xi,yi)=(∑j=1|An(bkn)|I(xjn+1,yjn+1))|An(bkn)|,
where I′(xi,yi) denotes the predicted value of an interpolated pixel, An(bkn) is the nearest blocks set of bkn, I(xjn+1,yjn+1)∈bjn+1, and bjn+1∈An(bkn). In addition, to obtain color frame interpolation, the R, G, and B channel values of each pixel can be computed in the same way.


## 4. Experimental Results and Discussion

In this section, the proposed RGFI algorithm is compared with other frame interpolation algorithms, including the block matching methods of three-step search (TSS), the adaptive rood pattern search (ARPS) [23], the optical flow method of Horn and Schunck (H&S) [24], Classic+NL-Full [5], and CSH [14]. Each algorithm was run in MATLAB using a PC with Intel(R) Pentium(R) 4 CPU processor, 3.00 GHz, and 3 GB of main memory. To evaluate algorithm performance, one in every two frames of the original video sequences was removed. Then this removed frame was reconstructed using different frame interpolation algorithms, and the reconstructed frame was compared with the removed frame. In all experiments, the detailed parameters were as follows. (1) Since c affects the accuracy of motion region detection, we try several different values and finally determine its value to be 0.2. (2) According to [11], we found that the best choice of parameters {L,ϕ1,ϕ2,ϕ3} is {17,3,10,20}, respectively, and this provides good discrimination ability. (3) Adjustment parameters {εL,εR,εT,εB} are used to complete the conversion from key points to motion regions and by experiments we found that the best choice of each parameter is 8. (4) The value of α is 0.5 and this is the same with [8]. (5) Based on [14], we choose three different values for s, namely, 8, 16, and 32. At the same time, we find that the appropriate value is 16 according to the obtained experiment results. The test video sequences used for these experiments were walk (640 × 480), jump in place (320 × 240), silent (176 × 144), and space (320 × 240). Walk and jump in place were provided by the image sequence evaluation research laboratory in Barcelona [25]. Silent was obtained from the video trace research group at Arizona State University [26]. Space was obtained from Youku Web. The selection of test video sequences covered a variety of different background and object motions, which are frequently found in real video.Figure4 shows the frame interpolation results using the six algorithms. Every row in the figure shows the interpolated frames for the same video using different algorithms, and every column shows the interpolation results for different videos using the same algorithm. From the red-bordered region of each figure, the visual differences among algorithms can be determined. TSS exhibited a poor interpolation effect, ARPS could not reveal the whole motion content, H&S and Classic+NL-Full introduced a suspension effect, and CSH produced disappointing effects, such as vague legs on the walking man. From these figures, it is evident that the proposed algorithm shows comparatively better performance in terms of visual quality.Figure 4
Comparison of interpolation frames obtained using six methods. From top to bottom, every row shows different interpolation results: interpolation frame 44 of walk, interpolation frame 31 of jump in place, interpolation frame 205 of silent, and interpolation frame 3 of space. From left to right, different algorithms are used: TSS, ARPS, H&S, Classic+NL-Full, CSH, and RGFI.To validate the algorithm further, objective measurements are also provided. Peak signal-to-noise ratio (PSNR) and root mean square error (RMSE) are traditional quantitative measures of accuracy. Figures5 and 6 show their values for the interpolation frames of different video sequences using different algorithms. In these figures, the red curves represent the proposed algorithm, and the five black curves using a different format represent comparison algorithms. It can be observed that the PSNR values for the interpolation frames obtained using the proposed algorithm are generally the highest, and the RMSE values are the lowest. However, the proposed method might produce unsatisfactory results, for example, the PSNR value of interpolation frame 58 of walk. Overall, it can be clearly demonstrated that the proposed new method outperforms the other five algorithms.Comparison of PSNR using six algorithms for walk, jump in place, silent, and space, respectively.
(a)
(b)
(c)
(d)Comparison of RMSE using six algorithms for walk, jump in place, silent, and space, respectively.
(a)
(b)
(c)
(d)The MSSIM measure was also used to evaluate the visibility quality of interpolation frames. MSSIM assesses the image visibility quality from an image formation point of view under the assumption of a correlation between human visual perception and image structural information [27, 28]. Figure 7 shows MSSIM comparison results using the six frame interpolation algorithms for the different video sequences. Note that the proposed RGFI algorithm generally achieved a greater MSSIM than the other five algorithms, and the results show that the interpolation frames obtained using the proposed algorithm are closer to the original frames in terms of image structure similarity.Comparison of MSSIM using six algorithms for walk, jump in place, silent, and space, respectively.
(a)
(b)
(c)
(d)Table1 summarizes the average PSNR, RMSE, and MSSIM values for each video sequence using different algorithms. From this table, it can be significantly determined that RGFI always obtains the highest PSNR and MSSIM and the lowest RMSE. In a word, because of its encouraging performance in terms of video visualization and quantitative quality assessment, the proposed algorithm is very competitive in frame interpolation.Table 1
Comparison of average PSNR, RMSE, and MSSIM values.
Method
Evaluation
Walk
Jump-in-place
Silent
Space
TSS
PSNR
33.6385
37.1343
31.8166
34.1798
RMSE
15.8233
11.4544
21.0495
15.3359
MSSIM
0.9351
0.9402
0.9065
0.9647
ARPS
PSNR
34.2260
37.3584
32.0574
33.1645
RMSE
15.8436
11.08734
20.4844
16.7526
MSSIM
0.9393
0.9405
0.9125
0.9616
H&S
PSNR
27.7678
34.7418
29.3596
25.3645
RMSE
31.5615
15.5741
29.3785
40.4711
MSSIM
0.8989
0.9296
0.8757
0.8698
Classic+NL-Full
PSNR
28.3820
35.9997
29.9458
26.3099
RMSE
30.4592
14.1522
27.1623
36.5059
MSSIM
0.9210
0.9456
0.8953
0.8761
CSH
PSNR
29.2065
32.4474
32.9375
22.0820
RMSE
26.4691
21.8114
18.8703
53.6209
MSSIM
0.9325
0.9351
0.9275
0.9141
Proposed algorithm
PSNR
35.4886
38.4762
33.4151
34.8564
RMSE
12.7313
9.7977
17.9540
14.3546
MSSIM
0.9472
0.9518
0.9323
0.9717


## 5. Another Contribution

We combine RGFI with a seam carving approach [29] to achieve video resizing, so as to obtain high-quality resizing results displayed on the monitoring display devices with different resolutions. Figure 8 shows comparative results for frame 10 of the video of “walk with dog” using four methods: scaling method with uniform resizing ratio, the best cropping method directly using cutting, the seam carving method by removing or duplicating seams, and the proposed algorithm using accurate motion regions obtained from RGFI. It can be seen that using the scaling method (see Figure 8(b)), the walking man and his dog all become vaguer than before. Using the best cropping (see Figure 8(c)), the walking man is only partly displayed, resulting in missing original information. Only using seam carving (see Figure 8(d)) does the prominent part of this video sequence change much less than before. From Figure 8(e), it is apparent that the proposed method can protect the prominent object of the original frame when the video sequence resolutions are changed. Table 2 summarizes five evaluation indicators, including average gradient (AG), information entropy (IE), edge intensity (EI), spatial frequency (SF), and image definition (ID) values. These indicators are used to measure the resizing quality of the video frames. From this table, it is clear that the proposed method achieved the highest AG, IE, EI, SF, and ID values, which indicates that the proposed method can effectively improve resizing quality when image sequence resolutions are changed.Table 2
Comparative results for the four resizing methods.
Method
AG
IE
EI
SF
ID
Scaling
10.8870
14.1536
106.7085
7.6176
27.9762
Best cropping
8.5673
9.6485
88.1226
7.5842
20.9809
Seam carving
9.6769
13.5044
96.8119
7.5244
26.1953
Proposed method
11.6518
14.3028
116.5497
7.6478
28.1341Comparative results for a walking man with a dog for the four resizing methods when the resolutions are resized from 180× 144 to 200 × 288.
(a)
The original frame
(b)
Using scaling
(c)
Using best cropping
(d)
Using seam carving
(e)
Using our algorithm


## 6. Conclusions

In this paper, promising RGFI method for intelligent monitoring systems has been presented. The main feature of this method is its ability to obtain relatively high-quality of interpolated frames according to spatial and temporal correlations in video sequences. The implementation process involves two steps: motion region detection and interpolated pixel computation. The former determines the prediction range of interpolation frames through a detection approach based on visual correspondence, and the latter computes interpolated pixels using spatial and temporal mapping rules based on coherency sensitive hashing. Experimental results show that the proposed algorithm outperforms the other five representative frame interpolation algorithms examined on subjective quality and in quantitative measures. At the same time, RGFI combined with a seam-carving approach can achieve video resizing. In a word, a promising frame interpolation method has been proposed for the intelligent monitoring systems. However, as a new frame interpolation algorithm, RGFI also has its disadvantage and the disadvantage is to take comparatively longer time caused by higher complexity. In the future, we will exploit a multicore architecture to do parallel computing, so as to reduce running time of the algorithm.



---

*Source: 453278-2013-07-09.xml*