搜尋樣型之區塊移動估計研究：模型、演算法設計與視訊編碼應用

Abstract

基於搜尋樣型之區塊移動估計 (Pattern-based Block Motion Estimation, PBME) 演算法是現今視訊編碼系統最常採用的壓縮工具之一。儘管許多研究者已經探討過PBME，卻甚少研究是關於「解釋PBME的工作原理與機制」之理論模型。 在這篇論文中，我們提出一個PBME的統計模型。這個模型包含兩個元件：1)移動向量 (Motion Vector) 的統計分布機率函數，2)一個搜尋演算法可以達到的最小搜尋點數函數，我們稱為「權重函數 (Weighting Function, WF)」。藉由檢視實驗資料，我們驗證此統計模型的正確性。然後我們展示兩個此模型的應用範例。由建立理想的WF中，我們設計基因式稜型搜尋演算法 (Genetic Rhombus Pattern Search, GRPS)。模擬結果顯示，與其他著名的搜尋演算法相比，GRPS減少20%的搜尋點數同時維持類似的壓縮影像PSNR (Peak Signal-to-Noise Ratio) 品質。更進一步，我們提出的模型能可靠預測一個PBME演算法應用在一新影像序列上的運算複雜度。 我們將此模型應用在PBME的設計上，檢視一個典型PBME演算法中每個元件，然後系統化調整主要元件，來達成最佳或接近最佳的結果。首先我們使用解析模型來分析並設計基因式樣型搜尋 (Genetic Pattern Searches)。然後我們提出一個適應性搜尋樣型切換策略 (Adaptive Pattern Switching Strategy)，此一樣型切換策略會動態的在兩個樣型搜尋中切換。第三，我們延伸提出的PBME模型來評估起始搜尋點的效率，並漸進式建立一個接近最佳的起始搜尋點集合 (Starting Point Set)。第四，我們檢視早期終止方法 (Early Termination)，並建議一個選取有效門檻值的量度值。藉此，我們建立一個有精確門檻值的早期終止機制。結合上述的技術，我們發展出一個完整的PBME演算，其效能超過許多現存的演算法。 儘管WF相當符合「確定性樣型搜尋方法 (Deterministic Pattern Search Scheme) 」，然而，WF不能精確的預測「機率性樣型搜尋方法 (Probabilistic Pattern Search Scheme) 」 (如基因式樣型演算法 (Genetic Pattern Search) )的效能。因此，我們提出「改良權重函數 (Refined Weighting Function, RWF) 」。在「單調象限函數與平滑象限邊界 (Quadrant Monotonic function with Smooth quadrant Border, QMSB) 的比對誤差表面 (Matching Error Surface) 」假設下，RWF可以更精確描述基因式與非基因式樣型搜尋演算法。RWF代表一個搜尋演算法在QMSB比對誤差平面中可以達到的平均搜尋點數函數。在建立RWF的過程中，我們學習如何更進一步加速樣型搜尋演算法，並設計兩個動量指引 (Momentum-directed) 基因式樣型搜尋演算法。此演算法給予每個可能的移動向量變異 (MV Mutation) 不同的優先權 (Priority) ，平均而言加速之前提出的基因式樣型搜尋演算法5%到7%。其中，不同移動向量變異的優先權是按照之前成功的搜尋來給定。 此外，我們檢視整個「可以預測樣型搜尋方法之平均搜尋點數」的改良模型。配合RWF，改良模型的預測精確度隨之提升。因此，我們重新檢視適應性樣型搜尋演算法中的編碼工具。我們特別專注在兩個編碼工具的影響：樣型切換策略與起始點選擇。我們研究這些工具中的最佳參數選擇，以及其對整體效能的影響。實驗結果顯示，我們改良的搜尋樣型切換策略可以再加速搜尋流程，並且將視覺品質保持到跟其構成的樣型搜尋方法相同。 總體而言，這篇論文建立一個PBME的分析模型，並且示範如何使用此一模型來建立樣型搜尋演算法與適應性樣型搜尋方法。我們並改良此模型，增加其精確性，也依此設計更好的快速搜尋演算法。

Pattern-based block motion estimation (PBME) is one of the most widely adopted compression tools in the contemporary video coding systems. However, despite that many researchers have studied PBME, few have attempted to construct an analytical model that can explain the underneath principle and mechanism of various PBME algorithms. In this dissertation, we propose a statistical PBME model that consists of two components: 1) the statistical probability distribution of the motion vectors, and 2) the minimal number of search points (called weighting function, WF) achieved by a search algorithm. We verify the accuracy of the proposed model by checking the experimental data. Then, two application examples using this model are proposed. Starting from an ideal weighting function, we devise a novel genetic rhombus pattern search (GRPS) to match the design target. Simulations show that comparing to the other popular search algorithms, GRPS reduces the average search points for more than 20% and, in the meanwhile, it maintains a similar level of coded image peak signal-to-noise ratio (PSNR) quality. Furthermore, the proposed model can reliably predict the performance of a PBME algorithm applied to a new video sequence. With the aid of the proposed model, we design new PBMEs by looking into every component of a typical PBME algorithm and fine-tuning the major components systematically to achieve the optimal or nearly optimal results. First, we use the aforementioned analytic model in analyzing and designing effective genetic-algorithm-based pattern searches. Then, we propose an adaptive switching strategy that dynamically switches between two pattern searches. Third, we extend our PBME model to evaluate the efficiency of starting (initial search) points. A near optimal set of starting points is identified through iterative steps. Fourth, we study the early termination threshold technique and suggest a metric in selecting an effective threshold. An early termination mechanism with accurate threshold is thus constructed. Combining all these techniques, we develop a PBME algorithm that outperforms many existing algorithms. Although the WF matches the deterministic search schemes quite well, however, the WF fails to give a precise search point prediction when a probabilistic search method such as a genetic pattern search is involved. Therefore, we propose a refined weighting function (RWF) that describes both genetic and non-genetic pattern searches more accurately under the assumption that the matching error surface is a quadrant monotonic function with smooth quadrant border (QMSB). In the process of constructing RWF, we further accelerate the pattern searches and two momentum-directed genetic pattern search algorithms are devised. These new algorithms assign priorities to the candidate mutations based on the information provided by the preceding successful searches and this can further reduce the computational complexity of the previously proposed genetic pattern searches by 5% to 7% in average. With refined RWF, the prediction accuracy of the refined model is significantly improved. Consequently, we re-examine the coding tools in the adaptive pattern search scheme. We focus on two components, the pattern switching strategy and the starting point selection. We investigate the optimal parameter selection issue in these tools and their impacts on the overall coding performance. Experimental results show that our refined pattern switching schemes can further accelerate the search process and in the meanwhile keep the visual quality comparable to the best of their constituent pattern searches. In summary, we propose an analytical model for PBME and demonstrate a methodology for developing new pattern-based search algorithms and the adaptive pattern search schemes by using our proposed model. One step further, we refine the original model, improve its accuracy and then design better fast search algorithms accordingly.