# A Spatial Prediction-Based Motion-Compensated Frame Rate Up-Conversion
## 2 Proposed SP-MCFI Algorithm
### BME for Basic Block  
The MV of an absent block is predicted by the MVs of its neighboring basic blocks. A better ME algorithm is needed to guarantee that any basic block has an accurate MV. Therefore, a full search ME is introduced to perform BME algorithm on the basic blocks. As Figure 3 shows, the advantage of a full search ME is that it can match the optimal motion trajectory within the search window, but meanwhile, the disadvantage is obvious. Assuming that the search radius is 8 and the standard block is 16 \(\times\) 16 in size, we can find that 289 blocks need to be searched in order to find the best matching block. Taking the CIF format as an example, a single video frame of 396 such matching blocks can mean a huge  
Figure 1: A flowchart of the proposed SP-MCFI algorithm.  
Figure 2: The block classification model.  
amount of computation for the full search ME algorithm. Therefore, this paper introduces an advanced SEA to reduce the computational complexity.  
Assuming that the resolution of the interpolated frame \(\mathbf{f}_{t+0.5}\) is \(M\times N\) and the block size is \(s\times s\), each frame would include \(M\times N/s^{2}\) standard blocks, and \(M\) and \(N\) must be divisible by \(s\). The pixel coordinate \((i,j)\) of the upper left corner of each block is used as a reference, and the luminance accumulation sum \(P\) of the block \((i,j)\) is calculated respectively in the \(t\)th frame and the \((t+1)\)th frame as follows:  
\[P_{t}(i,j)=\sum_{m=0}^{s}\sum_{n=0}^{s}f_{t}(i+m,j+n) \tag{1}\]  
\[P_{t+1}(i,j)=\sum_{m=0}^{s}\sum_{n=0}^{s}f_{t+1}(i+m,j+n) \tag{2}\]  
where \(f_{t}(i+m,j+n)\) and \(f_{t+1}(i+m,j+n)\) denote the luminance at the coordinate of \((i+m,j+n)\) respectively in \(f_{t}\) and \(f_{t+1}\) and \((m,n)\) is the coordinate of pixel in the block.  
The top-left pixel of the current basic block is set to \(\mathbf{p}\) (\(\mathbf{p}=(i,j)\)), then, the candidate blocks in the search window are traversed symmetrically in two reference frames. For reference frame \(\mathbf{f}_{t+1}\), the offset of the \(n\)th candidate block is \(\mathbf{v}_{n}^{\prime}=(x,y)\), and the offset of \(n\)th candidate block in the reference frame \(\mathbf{f}_{t}\) is \(-\mathbf{v}_{n}^{\prime}\). When the search window radius is \(r\), \(x\), \(y\in[-r,r]\), the initial offset is set to \((r,r)\), then the initial difference \(D_{0}\) of the current basic block is calculated in the following formula:  
\[D_{0}=\left\|\mathbf{B}_{t}(\mathbf{p}-\mathbf{v}_{0}^{\prime})-\mathbf{B}_{t+1}(\mathbf{p}+\mathbf{v} _{0}^{\prime})\right\|_{1} \tag{3}\]  
where \(\mathbf{B}_{t}(i-r,j-r)\) is the vector in which all the pixels of block \((i-r,j-r)\) in \(\mathbf{f}_{t}\) are arranged in rows and \(|\mid\bullet\mid\mid_{1}\) is the \(l_{1}\)-norm of the vector. After calculating \(D_{0}\), the \(\mathbf{v}_{n}^{\prime}\) is updated to the next candidate block in the search window; if the following inequality is satisfied,  
\[|P_{t}(i-x,j-y)-P_{t+1}(i+x,j+y)|<D_{0} \tag{4}\]  
then the difference \(D_{n}\) of the \(n\)th candidate block is calculated as follows:  
\[D_{n}=\left\|\mathbf{B}_{t}(\mathbf{p}-\mathbf{v}_{n}^{\prime})-\mathbf{B}_{t+1}(\mathbf{p}+\mathbf{v }_{n}^{\prime})\right\|_{1} \tag{5}\]  
Update the motion vector \(\mathbf{v}_{s}\) of the current basic block as follows:  
\[\mathbf{v}_{s}=\mathbf{v}_{n}^{\prime}=(x,y) \tag{6}\]  
Then, the updated \(D_{0}=\min\{D_{n},D_{0}\}\); otherwise, \(\mathbf{v}_{s}\) remains unchanged. All the candidate blocks in the search window should be traversed symmetrically according to the above process.  
Figure 3: An illustration of a full search ME.