使用分群演算法計算HEVC編碼中的動態預測

A Clustering Method for Motion Estimation in HEVC Encoding

陳瀚寬(Han-Kuan Chen)

指導教授 ： 李哲榮

國立清華大學/電機資訊學院/資訊工程學系所/碩士(2018年)

摘要

在視訊編碼裡，動態預測是個不可或缺的過程，該計算的目標是在給定的搜尋區域內找到最相似的區塊，使得視訊編碼能夠得到更好的壓縮率。然而，由於搜尋所有可能的區塊非常花費時間，許多方法使用特別的搜尋形式以便減少搜尋時間。但是隨著影片解析度上升，這些方法會越來越難找到最相似的區塊。
這篇論文中，我們提出一種於HEVC中，利用分群法解決動態預測的演算法。該演算法會建立分群樹以便進行相似搜尋。我們的方法會使用四種搜尋方式，分別是中心搜尋、分群搜尋、樹搜尋以及地理搜尋，以便求出最相似的區塊。實驗結果顯示，我們的位元率失真比TZ搜尋低4%，並且比TZ搜尋少19%～52%的搜尋次數。

關鍵字

高效率視訊編碼 ； 動態預測 ； 分群演算法

並列摘要

Motion estimation is an essential process in video coding. The goal is to find the most similar block within a given search window so that video coding can achieve better compression rate. However, since full search of search window is very time-consuming, many methods that uses fixed sampling patterns have been proposed to reduce the time complexity. But as the video resolution increases, they get harder to identify the optimal solution.
In this thesis, a clustering based method (TC) for motion estimation in HEVC encoding is proposed. The proposal constructs a clustering tree for block similarity search. The algorithm utilizes four search methods: center search, clustering search, tree search, and geography search to find the most similar block. Experiments show that the rate-distortion of our method is 4% smaller than that of the TZ method, and the number of searching blocks of our method is 19% ~ 52% fewer than that of the TZ method.

並列關鍵字

HEVC ； Motion estimation ； Clustering

參考文獻

[1] G. J. Sullivan, J. R. Ohm, W. J. Han, and T. Wiegand. Overview of the high efficiency video coding (hevc) standard. IEEE Transactions on Circuits and Systems for Video Technology, 22(12):1649–1668, 2012.

[2] J. Jain and A. Jain. Displacement measurement and its application in interframe image coding. IEEE Transactions on Communications, 29(12):1799–1808, 1981.

[3] Reoxiang Li, Bing Zeng, and M. L. Liou. A new three-step search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 4(4):438–442, 1994.

[4] Ce Zhu, Xiao Lin, and Lap-Pui Chau. Hexagon-based search pattern for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 12(5):349–355, 2002.

[5] Shan Zhu and Kai-Kuang Ma. A new diamond search algorithm for fast block- matching motion estimation. IEEE Transactions on Image Processing, 9(2):287–290, 2000.