基於N個皇后像素篩選法之快速動態預測演算法

Abstract

由於視訊串列需要的儲存空間非常龐大，所以對於空間有限的儲存設備或傳輸頻寬而言，都必須將視訊串列加以壓縮。而動態預測法便是藉由去除視訊串列中時間軸上的多餘性而達到視訊壓縮目的的一個方法。而由於動態預測法的完整搜尋方式的計算複雜度非常龐大，因此在即時運用上必須必須設計快速演算法降低動態預測法的龐大計算複雜度。相關文獻中所提出的方法大致可以分為減少搜尋點數以及像素篩選兩大類。本論文將著墨於像素篩選的方式以降低動態預測法的計算複雜度。 像素篩選法的優劣，可以藉由所選擇的像素在區域上的代表性以及方向上的代表性加以分析。本論文中，N-queens pattern所選擇的像素不論在區域性或是方向性都具有一定的代表性。由本論文的實驗結果得知，採用N-queens像素篩選法除了能將計算複雜度降低為原本的 外，並且採用N-queens像素篩選法的視訊壓縮品質會維持與原本搜尋方式相當近似的視訊壓縮品質。

Due to the storage size of video sequences are huge, it needs compression technique to reduce the storage size of video sequences. Motion estimation is this kind of technique to remove the temporal redundancy between video frames. Since the complexity of motion estimation is extremely huge, it needs some kind of fast algorithms to reduce the complexity of motion estimation for real-time application. Many approaches in reference papers can be classified into two categories: search points reduction and pixel decimation. In this paper, we will focus on the pixel decimation approach. Pixel decimation can be analyzed by the regional representation and directional representation of selected pixels. The selected pixels of N-queens approach we proposed in this paper have enough representation of both. By the experimental results, N-queens approach can reduce the complexity to of the original one. And the visual quality and bit rate are almost the same as the original search algorithms.