# Motion-Compensated Frame Interpolation Using Cellular Automata-Based Motion Vector Smoothing

Authors: Ran Li; Ying Yin; Fengyuan Sun; Yanling Li; Lei You
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Motion-Compensated Frame Interpolation (MCFI) is one of the common temporal-domain tamper operations, and it is used to produce faked video frames for improving the visual qualities of video sequences. The instability of temporal symmetry results in many incorrect Motion Vectors (MVs) for Bidirectional Motion Estimation (BME) in MCFI. The existing Motion Vector Smoothing (MVS) works often oversmooth or revise correct MVs as wrong ones. To overcome this problem, we propose a Cellular Automata-based MVS (CA-MVS) algorithm to smooth the Motion Vector Field (MVF) output by BME. In our work, a cellular automaton is constructed to deduce MV outliers according to a defined local evolution rule. By performing CA-based evolution in a loop iteration, we gradually expose MV outliers and reduce incorrect MVs resulting from oversmoothing as many as possible. Experimental results show the proposed algorithm can improve the accuracy of BME and provide better objective and subjective interpolation qualities when compared with the traditional MVS algorithms.


---

## Body

## 1. Introduction

Motion-Compensated Frame Interpolation (MCFI) [1] is one of the common temporal-domain tamper operations, and it produces several new video frames between two neighboring video frames along motion trajectories of objects. It can be used to increase the frame rate or temporal resolution of a video sequence, so it is also called Motion-Compensated Frame Rate Upconversion (MC-FRUC) [2, 3]. MCFI is a key step for many video applications, e.g., in the low bit-rate video coding, it is used to remove the temporal redundancy [4]; in the slow replay, it is used to improve movement details in a short time interval [5]; in Liquid Crystal Display (LCD), it is used to reduce the hold-type motion blur [6], etc. Therefore, as a fundamental technique, MCFI has been keeping a high research value since it was born.Motion Estimation (ME) and Motion-Compensated Interpolation (MCI) are the main parts in MCFI. ME is for predicting the Motion Vector Field (MVF) between the neighboring frames, and MCI is for interpolating a new frame by using the MVF output of ME. The performance of MCFI heavily depends on the prediction accuracy of ME, so many works focus on improving ME performance, and they can be classified into two types: Unidirectional ME (UME) [7] and Bidirectional ME (BME) [8]. Block Matching Algorithm (BMA) [9] is the core of UME and BME, and it is performed in order to produce block-based MVF according to the execution mechanisms of UME and BME. UME predicts the motion trajectory of each block from next frame and previous frame, then determines the MVs of blocks on these motion trajectories in the intermediate frame. The MVs produced by UME are close to reality, but for some blocks in the intermediate frame, there could be no MV or multiple MVs, thus introducing holes or overlaps. That is why many works abandon the use of UME and turn to BME. BME directly predicts the MVF of intermediate frame according to the assumption of temporal symmetry of translational motion, so each block has a unique MV, making the estimated MVF free from overlaps and holes. BME has been popular due to its straightforward implementation, though it usually produces inevitable MV outliers because the translational motion cannot describe some complex movements, e.g., rotation and deformation, and the flat region contains many structural-similar patches. To reduce MV outliers produced by BME, Motion Vector Smoothing (MVS) [10] becomes an essential postprocessing step, and in some works, the BME combined with MVS is called a true ME [11–13]. From the above, it can be seen that a high-efficiency MVS is a key to improving the prediction accuracy of BME.A typical MVS method is Median Filter (MF) [14], which replaces the MV of a block with the mean of MVs of its adjacent blocks. When an MV outlier occurs in a flat region, MF is not to adjust this outlier along with the major direction of neighboring MVs but to produce a new MV biased toward the major direction. That keeps MVF output by MF from being a high spatial correction in the flat region. A more popular way is to use Vector-Median Filter (VMF) [15], whose effectiveness is much more evident in the motion field with a high spatial correction when compared with MF. Beyond that, VMF can also reduce impulse noise while preserving contours. In the fields including edges and textures, spatial coherence is limited by the fact that the adjacent MVs do not necessarily align with a direction, so MF and VMF present a poor ability to correct MV outliers. To suppress MV outliers in the nonflat regions, Weighed VMF (WVMF) [16] is a good way. By adaptively controlling weights, WVMF relies not only on spatial coherence but also on the measure of the matching success. Though each MV in MVF can be smoothed by any one of MF, VMF, and WVMF, not all the MVs are outliers, thus introducing computation redundancy, even oversmoothing, i.e., revising the right MV as the wrong one. To prevent oversmoothing, many works add outlier detection before filtering MVF, e.g., Yoon et al. [17] regard an MV as an outlier if its absolute horizontal or vertical component value is larger than the average of those of its neighboring MVs; Kim and Sunwoo [18] detect an MV outlier by comparing the absolute difference of the current MV with the mean MV of its neighboring MVs. However, these methods cannot identify outliers accurately, especially that some obvious outliers are often omitted. Another way of suppressing oversmoothing is to refine MVF by imposing spatial-temporal smoothness constraint upon BMA, e.g., Huang et al. [19] designed a Spatial MVS (S-MVS), which uses Markov Random Field (MRF) to model spatial smoothness constraint of MVF, and refine each MV by performing BMA with MRF-based penalty term; Yoo et al. [20] proposed a Temporal MVS (T-MVS), which selects a reliable MV from the temporal-neighbor MVs along the forward and backward directions. With the spatial-temporal smoothness constraint, these methods make MVF closer to reality but cost lots of computations. So, both correction capability and computational complexity being considered, a more effective MVS can be realized by combining outlier detection and spatial-temporal smoothing. In this work, we try to provide a solution to make better use of the advantages of outlier detection and spatial-temporal smoothing.In this paper, we first perform BME to generate the initial MVF of the intermediate frame; then, a Cellular Automata- (CA-) based MVS (CA-MVS) algorithm is proposed to filter the MVF output by BME. The proposed CA-MVS algorithm is a combination of outlier detection and spatial-temporal smoothing, in which CA is the key to a trade-off between oversmoothing and computational redundancy. Compared with the existing works, the main contributions of our work are summarized as follows:(i)
MV outliers are found in MVF by measuring the angle between each MV and the mean of its neighboring MVs. A harsh threshold on the angle is set in order to pick out the evident outliers(ii)
According to the positions of outliers, the outlier map is generated, and input to CA. By the evolution rule of CA, some hidden outliers are found. After several iterations, the distribution of MV outliers tends to be stable, resulting in a good balance between oversmoothing and computational redundancy(iii)
Spatial-temporal coherence is exploited to correct MV outliers. For any MV outlier, VMF is first performed on its neighboring MVs to obtain the spatially predictive MV. Then, we refine this outlier by using the temporally neighboring MV candidates along the above-mentioned spatially predictive MVExperimental results show that the proposed CA-MVS algorithm can improve the prediction accuracy of BME and provide better objective and subjective interpolation qualities than the traditional MVS methods.


## 2. Background

### 2.1. Motion Vector Smoothing (MVS)

BME suffers from a limitation concerning the fidelity of the predicted MVF: MV outliers are introduced for the instability of temporal symmetry assumption. This drawback can be effectively overcome by performing Motion Vector Smoothing (MVS) in the further stage. As shown in Figure1(a), due to the spatial coherence of MVF, a true MV is similar in value and direction to its adjacent MVs. An example of an MV outlier is illustrated in Figure 1(b), an MV is detected as an outlier once it is different from its adjacent MVs in value or direction. In this case, MF or VMF can be used to correct this outlier. Suppose v0 is an MV outlier, and v1−v8 are its adjacent MVs, MF is performed as follows:
(1)v¯0=18∑i=18vi.Figure 1
Illustrations on the distribution of MV outliers: (a) normal; (b) single outlier; (c) outliers in adjacent MVs; (d) various adjacent MVs.
(a)(b)(c)(d)v¯0 is the corrected MV of v0, at the geometric center of v1−v8. As shown in Figure 1(c), if there are outliers in v1−v8, the mean MV cannot align at the main direction. An alternative solution is VMF, which outputs the median MV v^0 of v1−v8 as the corrected MV, i.e.,
(2)v^0=medv1,h,⋯,vi,h,⋯,v8,hmedv1,v,⋯,vi,v,⋯,v8,v,in which med· produces the median value of input set, vi,h is the horizontal component of the ith adjacent MV vi, and vi,v is the vertical component of the ith adjacent MV vi. The median MV v^0 satisfies the following property:
(3)v^0∈v1,⋯,vi,⋯,v8,∑i=18v^0−vi≤∑i=18vj−vi,j=1,2,⋯,8,in which ∙ is the norm. Equation (3) indicates that the sum of distances between the median MV and adjacent MVs is smaller than the one between any MV in v1−v8 and its adjacent MVs. This property forces v^0 to be biased toward the main direction of v1−v8. A drawback of VMF lies in the lack of turning parameters. As shown in Figure 1(d), if the adjacent MVs vary in value and direction, the median MV is unreliable since we are confident in the validity of any MV. To overcome such a drawback, WVMF has been introduced based on VMF and is defined as
(4)v^0∈v1,⋯,vi,⋯,v8,∑i=18wiv^0−vi≤∑i=18wivj−vi,j=1,2,⋯,8,in which wi is the weight coefficient corresponding to vi. The fixed weights are first considered; then, the definition is extended to the case of adaptively varying weights. The more reliable vi is, the higher the corresponding weight wi is. Therefore, the weighted-median MV is close to the reliable MVs.MF, VMF, and WVMF exploit the spatial coherence of MVF to smooth MV, so their performances degrade when the spatial coherence is limited. In addition to spatial coherence, temporal coherence can also be used to construct the smoothness constraint into BMA. As shown in Figure2, by assuming that MVs remain stable in a local region along time axis, the temporally and spatially neighboring MVs are combined in a candidate set CS. MV outlier can be refined by searching more reliable MV candidates in CS. To measure the reliability of MV candidates, the Sum of Bidirectional Absolute Difference (SBAD) is defined by
(5)SBADBvc=∑x,y∈Bft−1x−vc,h,y−vc,v−ft+1x+vc,h,y+vc,v,in which vc is the MV candidate, B is the pixel position set of the current block in the intermediate frame, vc,h and vc,v are horizontal and vertical components of vc, respectively, and ft−1x,y and ft+1x,y represent the pixel value at the position x,y in the previous frame and next frame, respectively. By the SBAD criterion, the MV outlier v0 can be smoothed as follows:
(6)v~0=argminvc∈CSSBADBvc,in which v~0 is the refined MV of v0. Combined with SBAD, MVS can fully exploit the temporal coherence of MVF. For the above-mentioned MVS algorithms, an inevitable defect is oversmoothing, i.e., revising true MV as a wrong one, which not only reduces the fidelity of MVF but also introduces invalid computations. To overcome oversmoothing which results from the unstable spatial-temporal coherence, we need a proper mechanism of outlier detection to correctly recognize the MV outlier.Figure 2
Illustrations on the spatial-temporal MV candidates.


### 2.2. Cellular Automata (CA)

Cellular Automata (CA) are discrete dynamical systems with a simple structure to investigate self-organization in statistical mechanics, and they were originally introduced by von Neumann and Ulam as a possible idealization of biological systems [21]. It is when a computer game “Life,” an application of a two-dimensional cellular automaton, became successful that CA began to attract researchers’ attention [22]. Then, Stephen Wolfram improved the theory of CA by an in-depth and comprehensive study on the elementary CA [23–25]. It has been widely used in a variety of fields such as sociology, graphics, and physics [26].The construction of a cellular automaton can be represented by the following formula:(7)CA=Ω,S,Λ,d,g,which shows that each point in a d-dimensional lattice Ω, called a cell, can take any one from a finite state set S, and the states of the cells of a lattice are updated according to a local evolution rule g, i.e.,
(8)Sik+1=gSik,Si±rk,r∈Λ,which denotes that the state Sik+1 of a cell at time k+1 depends on its own state Sik at time k, and the states Si±rk of cells in its neighbors set Λ at time k. All cells in the lattice are updated synchronously, and the state of the lattice advances in discrete time steps. An example of the one-dimensional cellular automaton with code 76 is illustrated in Figure 3. All cells are arranged in a line. Each cell has binary states 1 or 0, and its left and right cells construct its neighbors set. The eight possible states of three adjacent cells are given at time k; then, the central cell of the three takes its state at the next time k+1 by a defined rule. The time evolution of the complete cellular automaton is obtained by simultaneous application of the rule at each cell for each time step. In a two-dimensional case, different definitions of neighbors set are possible, among which von Neumann neighborhood and Moore neighborhood are common. As shown in Figure 4(a), four cells, the cells above and below each cell and the two on its right and left, are called von Neumann neighborhood of this cell. Moore neighborhood is illustrated in Figure 4(b), and it is an enlargement of von Neumann neighborhood containing the diagonal cells.Figure 3
One-dimensional cellular automaton with code 76.Figure 4
Examples of neighbors set: (a) von Neumann neighborhood; (b) Moore neighborhood.
(a)(b)By properly modeling objective behaviors as evolution rules, CA can simulate the running of some physical systems. Particularly in two dimensions, CA have been extensively used to exploit the statistics and latent features of images [27, 28]. The MVF of video frame is a two-dimensional lattice, and there exists inherent coherence between adjacent MVs, enabling CA to deduce the statistical mechanics of MV outliers in MVF. Motivated by the rule evaluation of CA, we attempt to construct a two-dimensional cellular automaton to model a universal law analogous to the variation of MV outliers. The cellular automaton controls the evaluation of the outlier map and helps MVS to get a good trade-off between oversmoothing and computational complexity.


## 2.1. Motion Vector Smoothing (MVS)

BME suffers from a limitation concerning the fidelity of the predicted MVF: MV outliers are introduced for the instability of temporal symmetry assumption. This drawback can be effectively overcome by performing Motion Vector Smoothing (MVS) in the further stage. As shown in Figure1(a), due to the spatial coherence of MVF, a true MV is similar in value and direction to its adjacent MVs. An example of an MV outlier is illustrated in Figure 1(b), an MV is detected as an outlier once it is different from its adjacent MVs in value or direction. In this case, MF or VMF can be used to correct this outlier. Suppose v0 is an MV outlier, and v1−v8 are its adjacent MVs, MF is performed as follows:
(1)v¯0=18∑i=18vi.Figure 1
Illustrations on the distribution of MV outliers: (a) normal; (b) single outlier; (c) outliers in adjacent MVs; (d) various adjacent MVs.
(a)(b)(c)(d)v¯0 is the corrected MV of v0, at the geometric center of v1−v8. As shown in Figure 1(c), if there are outliers in v1−v8, the mean MV cannot align at the main direction. An alternative solution is VMF, which outputs the median MV v^0 of v1−v8 as the corrected MV, i.e.,
(2)v^0=medv1,h,⋯,vi,h,⋯,v8,hmedv1,v,⋯,vi,v,⋯,v8,v,in which med· produces the median value of input set, vi,h is the horizontal component of the ith adjacent MV vi, and vi,v is the vertical component of the ith adjacent MV vi. The median MV v^0 satisfies the following property:
(3)v^0∈v1,⋯,vi,⋯,v8,∑i=18v^0−vi≤∑i=18vj−vi,j=1,2,⋯,8,in which ∙ is the norm. Equation (3) indicates that the sum of distances between the median MV and adjacent MVs is smaller than the one between any MV in v1−v8 and its adjacent MVs. This property forces v^0 to be biased toward the main direction of v1−v8. A drawback of VMF lies in the lack of turning parameters. As shown in Figure 1(d), if the adjacent MVs vary in value and direction, the median MV is unreliable since we are confident in the validity of any MV. To overcome such a drawback, WVMF has been introduced based on VMF and is defined as
(4)v^0∈v1,⋯,vi,⋯,v8,∑i=18wiv^0−vi≤∑i=18wivj−vi,j=1,2,⋯,8,in which wi is the weight coefficient corresponding to vi. The fixed weights are first considered; then, the definition is extended to the case of adaptively varying weights. The more reliable vi is, the higher the corresponding weight wi is. Therefore, the weighted-median MV is close to the reliable MVs.MF, VMF, and WVMF exploit the spatial coherence of MVF to smooth MV, so their performances degrade when the spatial coherence is limited. In addition to spatial coherence, temporal coherence can also be used to construct the smoothness constraint into BMA. As shown in Figure2, by assuming that MVs remain stable in a local region along time axis, the temporally and spatially neighboring MVs are combined in a candidate set CS. MV outlier can be refined by searching more reliable MV candidates in CS. To measure the reliability of MV candidates, the Sum of Bidirectional Absolute Difference (SBAD) is defined by
(5)SBADBvc=∑x,y∈Bft−1x−vc,h,y−vc,v−ft+1x+vc,h,y+vc,v,in which vc is the MV candidate, B is the pixel position set of the current block in the intermediate frame, vc,h and vc,v are horizontal and vertical components of vc, respectively, and ft−1x,y and ft+1x,y represent the pixel value at the position x,y in the previous frame and next frame, respectively. By the SBAD criterion, the MV outlier v0 can be smoothed as follows:
(6)v~0=argminvc∈CSSBADBvc,in which v~0 is the refined MV of v0. Combined with SBAD, MVS can fully exploit the temporal coherence of MVF. For the above-mentioned MVS algorithms, an inevitable defect is oversmoothing, i.e., revising true MV as a wrong one, which not only reduces the fidelity of MVF but also introduces invalid computations. To overcome oversmoothing which results from the unstable spatial-temporal coherence, we need a proper mechanism of outlier detection to correctly recognize the MV outlier.Figure 2
Illustrations on the spatial-temporal MV candidates.


## 2.2. Cellular Automata (CA)

Cellular Automata (CA) are discrete dynamical systems with a simple structure to investigate self-organization in statistical mechanics, and they were originally introduced by von Neumann and Ulam as a possible idealization of biological systems [21]. It is when a computer game “Life,” an application of a two-dimensional cellular automaton, became successful that CA began to attract researchers’ attention [22]. Then, Stephen Wolfram improved the theory of CA by an in-depth and comprehensive study on the elementary CA [23–25]. It has been widely used in a variety of fields such as sociology, graphics, and physics [26].The construction of a cellular automaton can be represented by the following formula:(7)CA=Ω,S,Λ,d,g,which shows that each point in a d-dimensional lattice Ω, called a cell, can take any one from a finite state set S, and the states of the cells of a lattice are updated according to a local evolution rule g, i.e.,
(8)Sik+1=gSik,Si±rk,r∈Λ,which denotes that the state Sik+1 of a cell at time k+1 depends on its own state Sik at time k, and the states Si±rk of cells in its neighbors set Λ at time k. All cells in the lattice are updated synchronously, and the state of the lattice advances in discrete time steps. An example of the one-dimensional cellular automaton with code 76 is illustrated in Figure 3. All cells are arranged in a line. Each cell has binary states 1 or 0, and its left and right cells construct its neighbors set. The eight possible states of three adjacent cells are given at time k; then, the central cell of the three takes its state at the next time k+1 by a defined rule. The time evolution of the complete cellular automaton is obtained by simultaneous application of the rule at each cell for each time step. In a two-dimensional case, different definitions of neighbors set are possible, among which von Neumann neighborhood and Moore neighborhood are common. As shown in Figure 4(a), four cells, the cells above and below each cell and the two on its right and left, are called von Neumann neighborhood of this cell. Moore neighborhood is illustrated in Figure 4(b), and it is an enlargement of von Neumann neighborhood containing the diagonal cells.Figure 3
One-dimensional cellular automaton with code 76.Figure 4
Examples of neighbors set: (a) von Neumann neighborhood; (b) Moore neighborhood.
(a)(b)By properly modeling objective behaviors as evolution rules, CA can simulate the running of some physical systems. Particularly in two dimensions, CA have been extensively used to exploit the statistics and latent features of images [27, 28]. The MVF of video frame is a two-dimensional lattice, and there exists inherent coherence between adjacent MVs, enabling CA to deduce the statistical mechanics of MV outliers in MVF. Motivated by the rule evaluation of CA, we attempt to construct a two-dimensional cellular automaton to model a universal law analogous to the variation of MV outliers. The cellular automaton controls the evaluation of the outlier map and helps MVS to get a good trade-off between oversmoothing and computational complexity.


## 3. Proposed CA-Based MVS (CA-MVS) Algorithm

### 3.1. Framework Overview

Figure5 shows the framework of the proposed CA-MVS algorithm. BME is first performed to produce the initial MVF Vt0 from the intermediate frame ft to the previous frame ft−1. According to the assumption of temporal symmetry, we also get the initial MVF −Vt0 from the intermediate frame ft to the next frame ft+1. Then, Vt0 is input into the proposed CA-MVS algorithm, which executes a loop of outlier detection, CA-based evolution, spatial-temporal smoothing, and residual calculation. In the jth iteration, we detect the MV outliers in Vtj, and the binary map Etj is generated to reveal the distribution of outliers. To avoid wrong detection results, outlier detection is limited strictly, so the outlier map Etj only reflects the evident MV outliers. Based on Etj, CA-based evolution is performed to find the hidden outliers. The constructed cellular automaton uses the propagation effect of outliers to model the local evolution rule and deduces E^tj from Etj to expose some hidden outliers. The spatial-temporal smoothing is used to correct any outlier pointed by E^tj in Vtj and outputs the MVF Vtj+1 of ft at the j+1th iteration. We select the less spatial-temporal neighboring MVs to smooth MV outliers in order to suppress oversmoothing. To decide whether to quit the loop, we calculate the residual ɛ between Vtj+1 and Vtj as follows:
(9)ε=1M×N∑m=1M∑n=1N∑l=12Vtj+1m,n,l−Vtjm,n,l,in which M×N denotes the spatial size of Vtj, m,n denotes the spatial position of each MV in Vtj, and l denotes the horizontal or vertical component of MV, i.e., l=1 means the horizontal component, and l=2 means the vertical component. The similarity between Vtj+1 and Vtj is measured by the residual ɛ, and a threshold Thr is set to determine whether to perform the next iteration. Once ɛ is less than or equal to Thr, we make the loop exit and output Vtj+1 as the final MVF Vt of ft. After several iterations, by the evolution of CA, the number of outliers tends to be stable, preventing oversmoothing introduced by redundant computations. According to Vt, the Overlapped Block Motion Compensation (OBMC) [29] is finally performed on ft−1 and ft+1 to interpolate the intermediate frame f^t. Outlier detection, CA-based evolution, and spatial-temporal smoothing are the important parts of the proposed CA-MVS algorithm, and the following describes them in detail.Figure 5
Framework of the proposed CA-MVS algorithm.


### 3.2. Outlier Detection

An evident MV outlier shows its large angle with respect to one of its adjacent MVs, so we use the angle between every two adjacent MVs to detect the outliers in MVF. A3×3 window is used to scan all MVs in MVF from left to right and from top to bottom, and as shown in Figure 6, in the MV window, v0 is the MV to be detected in the red block, and v1−v8 are eight adjacent MVs of v0, which are marked in blue. It costs many computations to compute all angles between v0 and v1−v8. In order to reduce computations, we first get the median MV v^0 of v1−v8 according to Equation (2), then compute the angle θ between v0 and v^0 as follows:
(10)θ=arccosv^0⋅v0v^02v02,θ∈−π,π,in which arccos· is the arc-cosine function. v^0 represents the main direction of v1−v8, so a large θ means that v0 deviates far from its adjacent MVs. Based on this experience, we regard v0 as an evident outlier if ∣θ∣ is larger than π/2. After detecting all MVs in Vtj, the outlier map Etj is generated, in which outlier and nonoutlier are marked with 1 and 0, respectively. This strict criterion makes the exposed outliers more reliable, but it also excludes some real outliers. These hidden outliers lead to the trade-off between oversmoothing and computations: if the hidden outliers are omitted, computations invested to smooth outlier are not many, but they can mislead the correction of exposed outliers, resulting in oversmoothing. Therefore, we add CA-based evolution to keep a good balance between oversmoothing and computations.Figure 6
Illustration on angle computing.


### 3.3. CA-Based Evolution

To ensure the accuracy of detecting outliers, the evident outliers are only marked with 1 inEtj. When we use Etj to decide whether to smooth any MV in Vtj, those hidden outliers cannot be corrected, and the exposed outliers would also be modified incorrectly once some outliers hide in its adjacent MVs. It is necessary to find these hidden outliers in Vtj in order to solve the above problem of oversmoothing. Motivated by the CA theory, we construct a cellular automaton to model the interaction between outliers in Etj and deduce the hidden outliers from the exposed ones according to the defined local evolution rule. Etj is a 2-dimensional lattice, and its element is regarded as a cell. Each cell has two states 0 and 1, denoting nonoutliers and outlier, respectively. Due to the locally stationary statistics of MVF, outliers propagate in its neighborhood. In a 3×3 window, this propagation effect can be enhanced when an outlier is closer to the center or more outliers occur in the window. Based on this experience, as shown in Figure 7, we define a local evolution rule for the constructed cellular automaton. Suppose the state Sik of the current cell is 0, and the states of its adjacent cells are b1−b8, which have two possible values 0 and 1. The state Sik+1 of the current cell at time step k+1 is specified as follows:
(11)Sik+1=gSik,bpp=1,2,⋯,8=1,∑p=18bp≥3,1,b2+b4+b5+b7≠0,0,else.Figure 7
Local evolution rule of the constructed cellular automaton.According to Equation (11), the current MV can be identified as an outlier if outliers occur in its von Neumann neighborhood or more than three outliers occur in its Moore neighborhood. The states at each cell in Etj are updated simultaneously, and these updated states form the new outlier map E^tj. To speed up the CA-based evolution, we summarize the truth table on the above defined local rule, as shown in Table 1. According to Table 1, the state of the cell at a given time is obtained immediately depending on the logical combination of its neighbors’ states at the previous time step. The CA-based evolution propagates the outlier in a local region and deduces the moderate number of hidden outliers. Compared with Etj, E^tj can smooth more outliers, and at the same time, the increased computations can achieve some alleviation of oversmoothing, bringing a good balance between oversmoothing and computational complexity.Table 1
Truth table on CA-based evolution.
Sikb1b2b3b4b5b6b7b8Sik+11××××××××1000000000000000000100000001000000000101000010000000001000010000100100001000000000100000010010000100001010000000Else1


### 3.4. Spatial-Temporal Smoothing

Any outlier pointed byE^tj is corrected by the proposed spatial-temporal smoothing. To improve the correction capability, the existing works are trying to construct a large-scale candidate set by exploiting the spatial-temporal coherence of MVF. However, the more candidate MVs there are, the more computations are invested, particularly the higher the probability of outliers occurring in the candidate set is. We combine VMF into the construction of candidate MV set in the spatial-temporal neighborhood, which can simplify the set of candidate MVs while providing a robust capability to correct outliers. The flow of spatial-temporal smoothing is illustrated in Figure 8. Suppose v0 is the MV outlier to be smoothed, and v1−v8 are its adjacent MVs, in which v2 and v5 are MV outliers. First, we input the correct MVs in v1−v8 into VMF and generate their median MV v^0. For the current block B, we find the matching block BM in ft−1 along v^0 and open a search window W centered BM. We set the radius w of W to be 1 and collect the relative displacements from B to all search points in W as the candidate MV set CS. The SBAD value of each MV candidate is computed according to Equation (5) and selects the candidate with the smallest SBAD value as the corrected MV by Equation (6). After scanning all outliers in E^tj, Vtj is updated as Vtj+1. Due to a small radius of the search window, the number of candidates in CS is limited, but these candidates have a strong spatial-temporal coherence with v0, and in that way, a good correction capability can be ensured.Figure 8
Illustration on spatial-temporal smoothing. Gray blocks denote MV outliers, and white blocks denote correct MVs.


## 3.1. Framework Overview

Figure5 shows the framework of the proposed CA-MVS algorithm. BME is first performed to produce the initial MVF Vt0 from the intermediate frame ft to the previous frame ft−1. According to the assumption of temporal symmetry, we also get the initial MVF −Vt0 from the intermediate frame ft to the next frame ft+1. Then, Vt0 is input into the proposed CA-MVS algorithm, which executes a loop of outlier detection, CA-based evolution, spatial-temporal smoothing, and residual calculation. In the jth iteration, we detect the MV outliers in Vtj, and the binary map Etj is generated to reveal the distribution of outliers. To avoid wrong detection results, outlier detection is limited strictly, so the outlier map Etj only reflects the evident MV outliers. Based on Etj, CA-based evolution is performed to find the hidden outliers. The constructed cellular automaton uses the propagation effect of outliers to model the local evolution rule and deduces E^tj from Etj to expose some hidden outliers. The spatial-temporal smoothing is used to correct any outlier pointed by E^tj in Vtj and outputs the MVF Vtj+1 of ft at the j+1th iteration. We select the less spatial-temporal neighboring MVs to smooth MV outliers in order to suppress oversmoothing. To decide whether to quit the loop, we calculate the residual ɛ between Vtj+1 and Vtj as follows:
(9)ε=1M×N∑m=1M∑n=1N∑l=12Vtj+1m,n,l−Vtjm,n,l,in which M×N denotes the spatial size of Vtj, m,n denotes the spatial position of each MV in Vtj, and l denotes the horizontal or vertical component of MV, i.e., l=1 means the horizontal component, and l=2 means the vertical component. The similarity between Vtj+1 and Vtj is measured by the residual ɛ, and a threshold Thr is set to determine whether to perform the next iteration. Once ɛ is less than or equal to Thr, we make the loop exit and output Vtj+1 as the final MVF Vt of ft. After several iterations, by the evolution of CA, the number of outliers tends to be stable, preventing oversmoothing introduced by redundant computations. According to Vt, the Overlapped Block Motion Compensation (OBMC) [29] is finally performed on ft−1 and ft+1 to interpolate the intermediate frame f^t. Outlier detection, CA-based evolution, and spatial-temporal smoothing are the important parts of the proposed CA-MVS algorithm, and the following describes them in detail.Figure 5
Framework of the proposed CA-MVS algorithm.


## 3.2. Outlier Detection

An evident MV outlier shows its large angle with respect to one of its adjacent MVs, so we use the angle between every two adjacent MVs to detect the outliers in MVF. A3×3 window is used to scan all MVs in MVF from left to right and from top to bottom, and as shown in Figure 6, in the MV window, v0 is the MV to be detected in the red block, and v1−v8 are eight adjacent MVs of v0, which are marked in blue. It costs many computations to compute all angles between v0 and v1−v8. In order to reduce computations, we first get the median MV v^0 of v1−v8 according to Equation (2), then compute the angle θ between v0 and v^0 as follows:
(10)θ=arccosv^0⋅v0v^02v02,θ∈−π,π,in which arccos· is the arc-cosine function. v^0 represents the main direction of v1−v8, so a large θ means that v0 deviates far from its adjacent MVs. Based on this experience, we regard v0 as an evident outlier if ∣θ∣ is larger than π/2. After detecting all MVs in Vtj, the outlier map Etj is generated, in which outlier and nonoutlier are marked with 1 and 0, respectively. This strict criterion makes the exposed outliers more reliable, but it also excludes some real outliers. These hidden outliers lead to the trade-off between oversmoothing and computations: if the hidden outliers are omitted, computations invested to smooth outlier are not many, but they can mislead the correction of exposed outliers, resulting in oversmoothing. Therefore, we add CA-based evolution to keep a good balance between oversmoothing and computations.Figure 6
Illustration on angle computing.


## 3.3. CA-Based Evolution

To ensure the accuracy of detecting outliers, the evident outliers are only marked with 1 inEtj. When we use Etj to decide whether to smooth any MV in Vtj, those hidden outliers cannot be corrected, and the exposed outliers would also be modified incorrectly once some outliers hide in its adjacent MVs. It is necessary to find these hidden outliers in Vtj in order to solve the above problem of oversmoothing. Motivated by the CA theory, we construct a cellular automaton to model the interaction between outliers in Etj and deduce the hidden outliers from the exposed ones according to the defined local evolution rule. Etj is a 2-dimensional lattice, and its element is regarded as a cell. Each cell has two states 0 and 1, denoting nonoutliers and outlier, respectively. Due to the locally stationary statistics of MVF, outliers propagate in its neighborhood. In a 3×3 window, this propagation effect can be enhanced when an outlier is closer to the center or more outliers occur in the window. Based on this experience, as shown in Figure 7, we define a local evolution rule for the constructed cellular automaton. Suppose the state Sik of the current cell is 0, and the states of its adjacent cells are b1−b8, which have two possible values 0 and 1. The state Sik+1 of the current cell at time step k+1 is specified as follows:
(11)Sik+1=gSik,bpp=1,2,⋯,8=1,∑p=18bp≥3,1,b2+b4+b5+b7≠0,0,else.Figure 7
Local evolution rule of the constructed cellular automaton.According to Equation (11), the current MV can be identified as an outlier if outliers occur in its von Neumann neighborhood or more than three outliers occur in its Moore neighborhood. The states at each cell in Etj are updated simultaneously, and these updated states form the new outlier map E^tj. To speed up the CA-based evolution, we summarize the truth table on the above defined local rule, as shown in Table 1. According to Table 1, the state of the cell at a given time is obtained immediately depending on the logical combination of its neighbors’ states at the previous time step. The CA-based evolution propagates the outlier in a local region and deduces the moderate number of hidden outliers. Compared with Etj, E^tj can smooth more outliers, and at the same time, the increased computations can achieve some alleviation of oversmoothing, bringing a good balance between oversmoothing and computational complexity.Table 1
Truth table on CA-based evolution.
Sikb1b2b3b4b5b6b7b8Sik+11××××××××1000000000000000000100000001000000000101000010000000001000010000100100001000000000100000010010000100001010000000Else1


## 3.4. Spatial-Temporal Smoothing

Any outlier pointed byE^tj is corrected by the proposed spatial-temporal smoothing. To improve the correction capability, the existing works are trying to construct a large-scale candidate set by exploiting the spatial-temporal coherence of MVF. However, the more candidate MVs there are, the more computations are invested, particularly the higher the probability of outliers occurring in the candidate set is. We combine VMF into the construction of candidate MV set in the spatial-temporal neighborhood, which can simplify the set of candidate MVs while providing a robust capability to correct outliers. The flow of spatial-temporal smoothing is illustrated in Figure 8. Suppose v0 is the MV outlier to be smoothed, and v1−v8 are its adjacent MVs, in which v2 and v5 are MV outliers. First, we input the correct MVs in v1−v8 into VMF and generate their median MV v^0. For the current block B, we find the matching block BM in ft−1 along v^0 and open a search window W centered BM. We set the radius w of W to be 1 and collect the relative displacements from B to all search points in W as the candidate MV set CS. The SBAD value of each MV candidate is computed according to Equation (5) and selects the candidate with the smallest SBAD value as the corrected MV by Equation (6). After scanning all outliers in E^tj, Vtj is updated as Vtj+1. Due to a small radius of the search window, the number of candidates in CS is limited, but these candidates have a strong spatial-temporal coherence with v0, and in that way, a good correction capability can be ensured.Figure 8
Illustration on spatial-temporal smoothing. Gray blocks denote MV outliers, and white blocks denote correct MVs.


## 4. Experimental Results

In this section, the performance of the proposed CA-MVS algorithm is evaluated by testing it on different video sequences and comparing the results with those obtained by the traditional MVS algorithms including MF [14], VMF [15], WVMF [16], S-MVS [19], and T-MVS [20]. An MCFI algorithm is also combined by BME, CA-MVS, and OBMC and compared with the recent state-of-the-art MCFI algorithms [1, 3, 7, 8] from objective perspectives. All test sequences used for experiments are in the standard CIF (352×288) formats and 30 frame/s. To evaluate the quality of the interpolated frames, we remove the first 50 even frames of each test sequence, then use various MCFI algorithms to recover these even frames from the 51 first odd frame. In the proposed CA-MVS algorithm, the block size is set to be 8×8, and how to set the threshold Thr will be discussed in Subsection 4.1. The comparing algorithms keep their original parameter settings. All experiments are conducted on a Windows machine with an Intel Core i7 3.40 GHz CPU and a memory of 8 GB. All algorithms are implemented in MATLAB.


### 4.1. Effect of CA on Performance

We evaluate the effect of CA on the performance improvement by presenting the variations of interpolated frames and outlier maps in the loop iterations as shown in Figure9. In the first iteration, there are many outliers in the outlier map after detection, then by CA-based evolution, many hidden outliers are exposed, and finally, we smooth these outliers and get the corresponding interpolated frame as shown in the left of Figure 9(a), from which it can be seen that obvious mismatches occur around the mouth region. In the second iteration, by outlier detection, the outliers are reduced significantly, but outliers around the mouth cannot be detected. Thanks to the CA-based evolution, these outliers hidden around the mouth are exposed again. The interpolated frame after the second iteration is shown in the second column of Figure 9(a), and we can see that the mismatches around the mouth are suppressed effectively. In the third iteration, after detecting, some outliers disappear as a result of the last spatial-temporal smoothing; then, the CA-based evolution propagates outliers around the detected outliers. After correcting these outliers, the interpolated frame is shown in the third column of Figure 9(a), and it can be seen that mismatches are removed. In the fourth iteration, the distribution of outliers tends to be stable, and the quality of the interpolated frame as shown in the right of Figure 9(a) is a little different from that after the third iteration. Figure 9 indicates that the bad effects from outliers in the interpolated frame are reduced step by step owing to the implementation of CA-based evolution. Figure 10(a) shows the varying PSNR values of the interpolated frame as the number of iteration times increases, and it can be seen that the PSNR value increases gradually at each iteration and tends to stabilize after the third one, indicating that CA-based evolution can effectively improve the interpolated quality. We cannot observe the quality degradation in both objective and subjective results due to oversmoothing, which presents that outlier propagation controlled by CA prevents oversmoothing. From Figure 10(b), we can find that the PSNR value has little change when residual value ɛ is smaller than 0.1 for the 82-rd frame of the Foreman sequence. Limited by space, we cannot present the PSNR and residual curves for other sequences, but these results are similar to Figure 10, i.e., the PSNR value tends to be stable when ɛ is smaller than 0.1. Therefore, in order to remove the invalid iterations, we set the threshold Thr to be 0.1.Figure 9
Interpolated frame and the corresponding outlier map at each iteration in the CA-MVS algorithm for the 82-rd frame ofForeman sequence. In each subfigure, from left to right: results after the first, second, third, and fourth iteration. For the outlier map, the black block denotes outlier, and the white block denotes nonoutlier. (a) Interpolated results; (b) outlier maps after detecting; (c) outlier maps after CA-based evolution.
(a)(b)(c)Figure 10
PSNR and residual values per iteration in the CA-MVS algorithm for the 82-rd frame ofForeman sequence: (a) PSNR curve; (b) residual curve.
(a)(b)


### 4.2. Subjective Evaluation

Figure11 shows the visual results of the 14th interpolated frame of the Foreman sequence with different MVS algorithms. MF and VMF can produce clear background, but serious blocking artifacts occur around the nose. For WVMF, S-MVS, and T-MVS, there are many mismatches on the background, and the faces are deformed severely. The proposed CA-MVS algorithm provides a pleasant result, in which there are no blocking artifacts. Figure 12 shows the visual results on the 58th interpolated frame of the Mobile sequence using different MVS algorithms. MF, VMF, and WVMF make the numbers on the calendar blurry and recover the red ball wrongly. S-MVS and T-MVS produce more serious distortion: numbers on the calendar disappear, and the color distortion occurs around the red ball. The CA-MVS algorithm produces clear numbers, and no deformation is generated. Figure 13 shows the visual results of the 22-rd interpolated frame of the News sequence with different MVS algorithms. WVMF, S-MVS, and T-MVS produce serious blocking effects around the face of anchorwoman. MF and VMF generate a clear face, but some mismatches occur on the background. The CA-MVS algorithm provides a comfortable result. Figure 14 shows the visual results of the 30th interpolated frame of the Stefan sequence with different MVS algorithms. For the traditional MVS algorithms, there are serious ghost effects around the sportsman; however, the CA-MVS algorithm effectively suppresses the blurring and provides a satisfying result.Figure 11
Visual results on the 14th interpolated frame of theForeman sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 12
Visual results on the 58th interpolated frame of theMobile sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 13
Visual results on the 22-rd interpolated frame of theNews sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 14
Visual results on the 30th interpolated frame of theStefan sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)


### 4.3. Objective Evaluation

The proposed CA-MVS and traditional MVS algorithms are, respectively, combined with BME and OBMC, and we get some different MCFI algorithms, which are used to interpolate the absent frames of test sequences. Table2 presents the average PSNR values of these interpolated frames when using different MVS algorithms. It can be seen that the CA-MVS algorithm has obvious PSNR gains when compared with any of the other algorithms, e.g., for Football with complex motions, the CA-MVS algorithm is 1.03 dB higher than VMF, and for News with simple motions, the CA-MVS algorithm obtains, respectively, 6.00 dB, 5.42 dB, and 5.36 dB PSNR gains when compared with WVMF, S-MVS, and T-MVS. The last row of Table 2 lists the average PSNR values on all test sequences for various MVS algorithms, and it can be seen that the proposed CA-MVS algorithm obtains obvious PSNR improvements compared with other MVS algorithms. Figure 15 shows the PSNRs of individual interpolated frames on Foreman, Mobile, News, and Stefan. We can see that the proposed CA-MVS algorithm outperforms the traditional MVS algorithms in most cases, and especially for Mobile and Stefan, obvious PSNR improvements of the CA-MVS algorithm can also be obtained. Table 3 lists the average processing time of various MVS algorithms. It can be seen that the CA-MVS algorithm does not excessively introduce computations and only increases by about 0.3 s when compared with MF and VMF. The CA-MVS algorithm requires fewer computations than WVMF, S-MVS, and T-MVS. Table 4 presents the PSNR results of the CA-MVS algorithm and recent state-of-the-art MCFI algorithms [1, 3, 7, 8]. The results of [1, 3, 7, 8] are directly taken from the original researches. From Table 4, we can see that the CA-MVS algorithm obtains PSNR gains for some test sequences, e.g., for Container, the CA-MVS algorithm outperforms [3, 7, 8], and for Football, the CA-MVS algorithm obtains 0.88 dB PSNR gains over [3]. In most cases, the proposed CA-MVS algorithm has comparable PSNR results to those of the state-of-the-art MCFI algorithms. From the above, we can see that the CA-MVS algorithm can provide a good objective interpolation quality.Table 2
Average PSNRs (dB) of the interpolated frames recovered by CA-MVS and traditional MVS algorithms.
Test sequenceMF [14]VMF [15]WVMF [16]S-MVS [19]T-MVS [20]CA-MVSAkiyo40.1546.0939.1637.3237.3446.83Coastguard26.9930.7728.5027.4627.5232.52Container35.7944.4935.5838.9538.9344.91Flower24.8029.5526.3126.2226.2831.68Football21.3521.8321.2021.4221.3222.86Foreman29.8232.1129.8828.1628.1734.73Hall31.1935.2930.5131.7631.7835.48Mobile19.0622.5420.4519.2019.3526.56Mother & daughter37.2141.5636.4838.3338.3442.53News32.3436.3531.2031.7831.8437.20Paris27.8831.9528.6328.1928.2033.52Stefan23.4526.6023.6023.7223.6228.52Tennis25.6228.1726.3826.5226.4330.05Average28.9032.8729.0729.1529.1634.41Figure 15
PSNRs of the interpolated frames constructed by different MVS algorithms: (a)Foreman; (b) Mobile; (c) News; (d) Stefan.
(a)(b)(c)(d)Table 3
Average time (s/frame) comparison of CA-MVS and traditional MVS algorithms.
MethodExecution time (s/frame)MF [14]0.0464VMF [15]0.0548WVMF [16]0.3722S-MVS [19]3.1201T-MVS [20]3.1076CA-MVS0.3717Table 4
Average PSNR (dB) comparison of the CA-MVS and some recent state-of-the-art MCFI algorithms.
Test sequence[1][3][7][8]CA-MVSCoastguard——34.0832.5432.52Container—43.6442.2744.7144.91Flower31.2729.7831.7632.2231.68Football—21.9826.0823.3522.86Foreman33.63—32.8634.9634.73Mobile28.8726.25——26.56News36.19—34.4537.9637.20Stefan29.38—25.4628.9128.52Tennis31.6528.57——30.05


## 4.1. Effect of CA on Performance

We evaluate the effect of CA on the performance improvement by presenting the variations of interpolated frames and outlier maps in the loop iterations as shown in Figure9. In the first iteration, there are many outliers in the outlier map after detection, then by CA-based evolution, many hidden outliers are exposed, and finally, we smooth these outliers and get the corresponding interpolated frame as shown in the left of Figure 9(a), from which it can be seen that obvious mismatches occur around the mouth region. In the second iteration, by outlier detection, the outliers are reduced significantly, but outliers around the mouth cannot be detected. Thanks to the CA-based evolution, these outliers hidden around the mouth are exposed again. The interpolated frame after the second iteration is shown in the second column of Figure 9(a), and we can see that the mismatches around the mouth are suppressed effectively. In the third iteration, after detecting, some outliers disappear as a result of the last spatial-temporal smoothing; then, the CA-based evolution propagates outliers around the detected outliers. After correcting these outliers, the interpolated frame is shown in the third column of Figure 9(a), and it can be seen that mismatches are removed. In the fourth iteration, the distribution of outliers tends to be stable, and the quality of the interpolated frame as shown in the right of Figure 9(a) is a little different from that after the third iteration. Figure 9 indicates that the bad effects from outliers in the interpolated frame are reduced step by step owing to the implementation of CA-based evolution. Figure 10(a) shows the varying PSNR values of the interpolated frame as the number of iteration times increases, and it can be seen that the PSNR value increases gradually at each iteration and tends to stabilize after the third one, indicating that CA-based evolution can effectively improve the interpolated quality. We cannot observe the quality degradation in both objective and subjective results due to oversmoothing, which presents that outlier propagation controlled by CA prevents oversmoothing. From Figure 10(b), we can find that the PSNR value has little change when residual value ɛ is smaller than 0.1 for the 82-rd frame of the Foreman sequence. Limited by space, we cannot present the PSNR and residual curves for other sequences, but these results are similar to Figure 10, i.e., the PSNR value tends to be stable when ɛ is smaller than 0.1. Therefore, in order to remove the invalid iterations, we set the threshold Thr to be 0.1.Figure 9
Interpolated frame and the corresponding outlier map at each iteration in the CA-MVS algorithm for the 82-rd frame ofForeman sequence. In each subfigure, from left to right: results after the first, second, third, and fourth iteration. For the outlier map, the black block denotes outlier, and the white block denotes nonoutlier. (a) Interpolated results; (b) outlier maps after detecting; (c) outlier maps after CA-based evolution.
(a)(b)(c)Figure 10
PSNR and residual values per iteration in the CA-MVS algorithm for the 82-rd frame ofForeman sequence: (a) PSNR curve; (b) residual curve.
(a)(b)


## 4.2. Subjective Evaluation

Figure11 shows the visual results of the 14th interpolated frame of the Foreman sequence with different MVS algorithms. MF and VMF can produce clear background, but serious blocking artifacts occur around the nose. For WVMF, S-MVS, and T-MVS, there are many mismatches on the background, and the faces are deformed severely. The proposed CA-MVS algorithm provides a pleasant result, in which there are no blocking artifacts. Figure 12 shows the visual results on the 58th interpolated frame of the Mobile sequence using different MVS algorithms. MF, VMF, and WVMF make the numbers on the calendar blurry and recover the red ball wrongly. S-MVS and T-MVS produce more serious distortion: numbers on the calendar disappear, and the color distortion occurs around the red ball. The CA-MVS algorithm produces clear numbers, and no deformation is generated. Figure 13 shows the visual results of the 22-rd interpolated frame of the News sequence with different MVS algorithms. WVMF, S-MVS, and T-MVS produce serious blocking effects around the face of anchorwoman. MF and VMF generate a clear face, but some mismatches occur on the background. The CA-MVS algorithm provides a comfortable result. Figure 14 shows the visual results of the 30th interpolated frame of the Stefan sequence with different MVS algorithms. For the traditional MVS algorithms, there are serious ghost effects around the sportsman; however, the CA-MVS algorithm effectively suppresses the blurring and provides a satisfying result.Figure 11
Visual results on the 14th interpolated frame of theForeman sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 12
Visual results on the 58th interpolated frame of theMobile sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 13
Visual results on the 22-rd interpolated frame of theNews sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)Figure 14
Visual results on the 30th interpolated frame of theStefan sequence with different MVS algorithms: (a) MF; (b) VMF; (c) WVMF; (d) S-MVS; (e) T-MVS; (f) CA-MVS.
(a)(b)(c)(d)(e)(f)


## 4.3. Objective Evaluation

The proposed CA-MVS and traditional MVS algorithms are, respectively, combined with BME and OBMC, and we get some different MCFI algorithms, which are used to interpolate the absent frames of test sequences. Table2 presents the average PSNR values of these interpolated frames when using different MVS algorithms. It can be seen that the CA-MVS algorithm has obvious PSNR gains when compared with any of the other algorithms, e.g., for Football with complex motions, the CA-MVS algorithm is 1.03 dB higher than VMF, and for News with simple motions, the CA-MVS algorithm obtains, respectively, 6.00 dB, 5.42 dB, and 5.36 dB PSNR gains when compared with WVMF, S-MVS, and T-MVS. The last row of Table 2 lists the average PSNR values on all test sequences for various MVS algorithms, and it can be seen that the proposed CA-MVS algorithm obtains obvious PSNR improvements compared with other MVS algorithms. Figure 15 shows the PSNRs of individual interpolated frames on Foreman, Mobile, News, and Stefan. We can see that the proposed CA-MVS algorithm outperforms the traditional MVS algorithms in most cases, and especially for Mobile and Stefan, obvious PSNR improvements of the CA-MVS algorithm can also be obtained. Table 3 lists the average processing time of various MVS algorithms. It can be seen that the CA-MVS algorithm does not excessively introduce computations and only increases by about 0.3 s when compared with MF and VMF. The CA-MVS algorithm requires fewer computations than WVMF, S-MVS, and T-MVS. Table 4 presents the PSNR results of the CA-MVS algorithm and recent state-of-the-art MCFI algorithms [1, 3, 7, 8]. The results of [1, 3, 7, 8] are directly taken from the original researches. From Table 4, we can see that the CA-MVS algorithm obtains PSNR gains for some test sequences, e.g., for Container, the CA-MVS algorithm outperforms [3, 7, 8], and for Football, the CA-MVS algorithm obtains 0.88 dB PSNR gains over [3]. In most cases, the proposed CA-MVS algorithm has comparable PSNR results to those of the state-of-the-art MCFI algorithms. From the above, we can see that the CA-MVS algorithm can provide a good objective interpolation quality.Table 2
Average PSNRs (dB) of the interpolated frames recovered by CA-MVS and traditional MVS algorithms.
Test sequenceMF [14]VMF [15]WVMF [16]S-MVS [19]T-MVS [20]CA-MVSAkiyo40.1546.0939.1637.3237.3446.83Coastguard26.9930.7728.5027.4627.5232.52Container35.7944.4935.5838.9538.9344.91Flower24.8029.5526.3126.2226.2831.68Football21.3521.8321.2021.4221.3222.86Foreman29.8232.1129.8828.1628.1734.73Hall31.1935.2930.5131.7631.7835.48Mobile19.0622.5420.4519.2019.3526.56Mother & daughter37.2141.5636.4838.3338.3442.53News32.3436.3531.2031.7831.8437.20Paris27.8831.9528.6328.1928.2033.52Stefan23.4526.6023.6023.7223.6228.52Tennis25.6228.1726.3826.5226.4330.05Average28.9032.8729.0729.1529.1634.41Figure 15
PSNRs of the interpolated frames constructed by different MVS algorithms: (a)Foreman; (b) Mobile; (c) News; (d) Stefan.
(a)(b)(c)(d)Table 3
Average time (s/frame) comparison of CA-MVS and traditional MVS algorithms.
MethodExecution time (s/frame)MF [14]0.0464VMF [15]0.0548WVMF [16]0.3722S-MVS [19]3.1201T-MVS [20]3.1076CA-MVS0.3717Table 4
Average PSNR (dB) comparison of the CA-MVS and some recent state-of-the-art MCFI algorithms.
Test sequence[1][3][7][8]CA-MVSCoastguard——34.0832.5432.52Container—43.6442.2744.7144.91Flower31.2729.7831.7632.2231.68Football—21.9826.0823.3522.86Foreman33.63—32.8634.9634.73Mobile28.8726.25——26.56News36.19—34.4537.9637.20Stefan29.38—25.4628.9128.52Tennis31.6528.57——30.05


## 5. Conclusion

In this paper, the CA-MVS algorithm is proposed to reduce the incorrect MVs resulting from BME. To overcome oversmoothing, according to the CA theory, we construct a cellular automaton to model the interaction between outliers and define a logical evolution rule to accurately expose outliers step by step. In the CA-MVS algorithm, a loop iteration is executed. First, by the angles between every two adjacent MVs, the evident outliers are detected. Second, through CA-based evolution, we find the hidden outliers based on the information from the exposed outliers. Third, the spatial-temporal smoothing corrects each MV outlier by searching the reliable MV from the spatial-temporal neighboring MVs. Finally, we calculate the residual between the current and the previous MVFs to decide whether to make the loop exit. Experimental results show that, compared with the traditional algorithms, the CA-MVS algorithm can better improve the accuracy of BME and provide better subjective and objective interpolation qualities.As the research in this paper is exploratory, there are many intriguing questions that future work should consider. First, the outlier detection is required to make it more accurate. Second, we will further improve the CA evolution rule to more efficiently find hidden outliers. Finally, the color information will be considered to be mixed into the CA evolution.



---

*Source: 6660869-2021-02-22.xml*