調色板編碼中2-鄰域聯合轉移概率的索引圖預測

宋傳鳴 何 興 閔 新 王相海

1(遼寧師范大學計算機與信息技術學院 遼寧大連 116081) 2(大連理工大學計算機科學與技術學院 遼寧大連 116024) 3 (計算機軟件新技術國家重點實驗室(南京大學) 南京 210023) (chmsong@lnnu.edu.cn)

高速網絡和云——移動計算模型的發展促使視頻會議、網絡游戲直播、遠程教學、屏幕鏡像、桌面虛擬化等諸多應用生成了大量高清晰度屏幕內容[1-2]，并且這些內容中往往既包含不連續色調的區域(如文本、圖表、圖形、圖標)，又包含連續色調的區域(如自然圖像、視頻).因此，屏幕內容在時間域、空間域和頻率域的數據分布特性與自然視頻存在明顯差異[3]，導致MPEG AVC/H.264、高效率視頻編碼(high efficiency video coding, HEVE)等面向自然圖像/視頻的典型編碼方法無法獲得令人滿意的壓縮效率.為此，國際視頻編碼聯合協作組(Joint Collaborative Team on Video Coding, JCT-VC)自2014年至今致力于面向屏幕內容的HEVC擴展編碼標準——屏幕內容編碼(high efficiency video coding-screen content coding extension，HEVC-SCC)的制定工作，并且目前已采納了幀內塊拷貝(intra-block copy)、調色板、自適應顏色變換、分量間預測(cross component predic-tion)、殘差差分脈沖編碼調制(residual differential pulse code modulation)等作為其推薦編碼方法[4].其中，幀內塊拷貝和調色板是HEVC-SCC的2種最主要的方法，為其貢獻了大部分的性能提升[5].前者類似于發生在同一幀內的運動估計，利用矩形區域的像素集合發掘屏幕內容中蘊含的非局部冗余，但是靈活性不夠，很難用固定形狀的像素集合實現對文本、圖表和圖標等內容的最佳匹配，計算量較大，并且傳統視頻編碼的運動估計為它提供了很好的參考，技術方法較成熟；后者則通過發掘屏幕內容的顏色數量少、重復圖案多的數據特點實現壓縮，其計算量也明顯低于幀內塊拷貝，在壓縮比、實時性和復雜性等多方面可以較好地滿足屏幕內容編碼的需求.

調色板編碼算法是一種適用于屏幕圖像中非連續色調像素內容的一種壓縮算法，其基本思想是首先將屏幕內容中出現次數最多的4種顏色值作為基本顏色(base color)，并為其分別指定索引值建立調色板；其次，將屏幕內容中的各個像素量化成基本顏色或逃逸色(escape color)，并用基本顏色和逃逸色對應的索引值代替像素值，生成索引圖(index map)；最后，對建立的調色板和索引圖進行編碼.目前，調色板的建立和編碼已相對成熟，出現了基于局部調色板的預測編碼算法[6-8]和基于全局調色板的預測編碼算法[9].而相比之下，索引圖的編碼效率，尤其是那些分布在邊緣過渡區或連接區的索引值，則仍有較大的改進空間[5].為解決這個問題，本文提出一種基于2-鄰域聯合轉移概率的索引圖預測方法：首先，利用局部方向預測失敗的索引值組成訓練數據集，計算索引值的2-鄰域轉移概率；其次，在局部預測失敗的情況下，利用與待預測索引相鄰的4個索引計算4組2-鄰域轉移概率及其聯合轉移概率；最后，選擇聯合轉移概率最大的索引值作為待編碼索引的最優預測值.本文算法的主要貢獻包括3個方面：

1) 通過實驗統計發現,較大尺寸的預測模板(如4-鄰域模板)會產生數量眾多的候選模板，而其中的大多數卻為干擾模板，并且大模板不能有效捕獲邊緣反走樣區域的索引值分布特點，進而導致模板的平均匹配概率和非局部預測效率不高；

2) 將基于模板的索引圖預測建模為一種基于顏色轉移概率的查表操作，可降低模板匹配的計算復雜度；

3) 實驗結果表明,本文算法將索引圖的平均預測準確率提高到97.70%，改善了邊緣反走樣區或過渡區的索引值預測效率.

1 相關工作

典型的索引圖編碼主要有4類：算術編碼、行程編碼、詞典編碼和預測編碼.

算術編碼主要通過減少索引圖數據的統計冗余達到壓縮的目的，如文獻[10]采用自適應算術編碼、文獻[11]采用上下文重映射和算術編碼壓縮索引圖等.但是，算術編碼沒有充分利用索引圖中特有的重復圖案等非局部統計特點，編碼效率不高.

行程編碼則發掘了相鄰索引值出現的重復規則圖案，即局部相關性，如文獻[12]采用1D行程方法將索引值組織成一系列二元、三元組序列進行壓縮；考慮到索引圖中的重復圖案大多是2D的，文獻[13]將一個重復的2D圖案表示成四元組，提出了索引圖的2D行程編碼方法.同時，文獻[14]進一步發現在索引圖的相鄰行(列)之間還存在較強的行(列)局部相關性，并提出若一個圖像塊的某一行(列)與其相鄰的前一行(列)有相同索引值或者僅有1個索引值不同，則用垂直(水平)行程模式編碼該行(列)像素的索引圖，其預測效率更高，所需同步信息更少.雖然行程編碼方法對于規則、平滑區域的索引圖非常有效，可是卻對邊緣、紋理較復雜區域的編碼效率偏低.

針對屏幕圖像中往往包含較多的相同或相似文字和圖形的特點，研究人員提出了一類基于詞典的編碼算法，利用待編碼索引值所在的一個1D或2D連續索引串作為模板，該索引串在空間域上可組織成任意形狀，再在已編碼區域中搜索與其最匹配的索引串，從而去除數據冗余.文獻[15]采用基于Lempel- Ziv字典的gzip算法對復合圖像進行編碼；文獻[16]應用LZMA (Lempel-Ziv-Markov chain algorithm)等提出了面向屏幕內容的字典編碼方法；為加快像素串的匹配速度，文獻[17]提出了Hash表結構的1D字典編碼以及2種字典模式；文獻[18]則進一步提出了屏幕內容的2D字典編碼方法，將待編碼單元的Hash值作為字典索引查找到候選的匹配塊.該類方法利用索引圖包含大量相同字符或者相同紋理結構這種非局部相關性特點，取得了不錯的編碼效率.然而，模板索引串越長，所需要的搜索時間或字典空間等代價就越高，并且，由本文第3節的實驗結果可知，過長的模板索引串對提高邊緣區域的編碼效率反而是不利的.另外，字典編碼方法對索引圖局部相關性的處理效率不高.

為了能同時發掘索引圖的局部和非局部冗余，文獻[19]提出了一種多級預測(multi-stage prediction, MSP)編碼方法，先通過方向預測去除索引值的局部相關性，然后對預測失敗的元素采用模板匹配預測發掘其非局部數據冗余，其索引值被準確預測的概率達到了92%；文獻[20]提出了一種2級層次預測編碼模式，第1級將每個與其左側或上側相鄰索引值相等的索引用特定符號標識出來，再在第2級對每一行符號進行分組，最后對各標識符號進行熵編碼.可見，預測編碼是同時發掘索引圖局部與非局部相關的有效策略，優于典型的算術編碼、行程編碼和詞典編碼.然而，文獻[19-20]提出的2種方法涉及多輪掃描，計算量高.在這種情況下，文獻[7,21]提出略去MSP算法的模板預測.其中，文獻[7]通過簡化方向預測過程，將MSP的計算量降低了80%，可是預測方向較少、預測效率有所降低，適合實時要求較高的應用；文獻[21]則通過實驗統計發現，提出了索引圖的“局部方向相關性”特性，進而利用這個性質在MSP的1級預測基礎上提出了2次方向預測，其預測準確率達到了95%.不過，由于文獻[7,21]僅發掘了索引圖的局部數據相關，尚有部分索引值未借助索引圖的非局部相關性進行處理，其預測準確率仍有一定的提高空間.本文發現，發生預測失敗的索引主要分布在邊緣的過渡或連接區域，并且由于文字、線條往往進行邊緣反走樣處理[5]，這些過渡或連接區域的索引值常呈現特定的組合模式.故此，模板預測仍是充分利用這種模式的有效途徑.與現有方法不同，本文將模板預測建模為轉移概率最大化問題，并進一步縮小模板尺寸，從而以較小的時空復雜度實現了索引值的非局部預測，改善了索引圖的預測準確率.

2 索引圖的局部方向預測和模板預測

本節我們主要對基于局部方向相關性的索引圖預測和基于模板匹配的索引圖預測方法進行簡要介紹.

2.1 基于局部方向相關性的索引圖預測

文獻[21]的實驗結果表明，相鄰索引值之間存在較強的方向相關性，且沿著垂直、水平方向的相關性高于沿著對角線、反對角線方向的相關性.所以，對于待預測索引值x，文獻[21]首先將其水平方向相鄰索引值的預測方向作為初始預測方向.如果該索引值沿著某個方向預測成功，則仍然沿著該方向預測x；若前一索引值預測失敗，則采用MSP的方向預測算法進行初始預測.此時，若仍舊預測失敗，則利用圖1所示的模板分水平、豎直、對角線或反角線4種情況進一步對索引值x完成方向預測，繼續判別沿著45°，60°，90°，120°，135°，150°，180°方向的幾何正則性.

Fig. 1 Template for local directional prediction[21]圖1 局部方向預測模板[21]

當待預測索引值x的初始預測方向為水平時，由于初始預測失敗，表明x處不存在水平方向的邊緣，即Ix≠Ia(Ix和Ia分別表示預測模板中元素x和a處的索引值)，其2次預測過程如下：

1) 若Ia=Ib并且Ia≠Ic，說明x處可能存在豎直邊緣，則令索引x的預測值Px=Ic.

2) 若Ia=Ib并且Ia=Ic，則令Px=Id.

3) 若Ia=Ic并且Ia≠Id，說明x處可能存在45°方向的邊緣，則令Px=Id.

4) 若Ia=Ic并且Ia=Id，則令Px=Ib.

5) 若Ia≠Id,

① 若Ic=Ii，說明x處可能存在90°方向的邊緣，則令Px=Ic；

② 若If=Ib或者Ih=Ib或者Ig=Ib，或者Ic=Ih，說明x處可能存在150°，120°或135°方向的邊緣，則令Px=Ib；

③ 若Ij=Id或者Ij=Ic，說明x處可能存在60°或45°方向的邊緣，則令Px=Id.

6) 若Ia=Id,

① 若Ii=Ic或者Ij=Ic，說明x處可能存在垂直或者60°方向的線，則令Px=Ic；

② 若If=Ib或者Ig=Ib或者Ih=Ib，或者Ic=Ih，說明x處可能存在120°，135°或150°方向的線，則令Px=Ib.

7) 若上述1)～6)條件不滿足，則表明x處不存在明顯的局部幾何正則性，其局部方向預測失敗，默認令Px=Ic，預測結束.

由于篇幅所限，當初始預測為其他方向時，其2次預測過程可詳見文獻[21].

2.2 基于模板匹配的索引圖預測

與文獻[21]的思路不同，MSP算法[19]在初始預測失敗的情況下引入了一種基于模板匹配的第2級預測，其主要思路是利用上下文內容的統計相關性來計算x的最佳預測值.如圖2所示，實線方框內的值“1”是當前待編碼的索引值，陰影方框內的值“0 0 2 0”是與其具有統計相關性的上下文預測模板，以模板“0 0 2 0”作為上文，下文“1”出現的概率為0.75，而下文“2”出現的概率為0.25，所以“1”被作為待編碼索引x的預測值.這樣的模板可以統一地表示成圖3所示的形式，其中x表示待預測的索引值，a，b，c，d表示與x相鄰的已編碼索引值，下文約定稱其為“4-鄰域模板”.

Fig. 2 Diagram of template prediction[19]圖2 模板匹配預測示意圖[19]

Fig. 3 Diagram of 4-neighbor template圖3 4-鄰域模板示意圖

文獻[19]的實驗結果顯示，在初始預測失敗的情況下，4-鄰域模板預測的準確率為53%.從這個意義上講，基于4-鄰域模板匹配的索引圖預測效率還不盡如人意.

3 4-鄰域模板預測效率及轉移概率建模

雖然模板匹配預測能夠發掘屏幕內容的非局部相關性，但是文獻[21]認為模板預測對于那些包含復雜線條(比如漢字)、圖案大多不具有特定全局模式的屏幕圖像，其預測準確率將低于50%.為此，本節深入分析基于4-鄰域模板匹配的預測效率和計算效率偏低的原因，進而提出一種基于聯合轉移概率的索引值預測思路.

3.1 基于模板匹配的預測效率分析

考慮到MSP的初始預測和文獻[21]的2次方向預測已經能夠較好地解決索引值的局部預測問題，本文主要在2種局部預測算法均失敗的情況下，探討基于4-鄰域模板匹配的預測效率.

首先，由于4-鄰域模板采用待編碼索引x周圍的4個相鄰索引值a～d作為模板，并且x和a～d又各有5種可能的取值(包括4種基本顏色和1種逃逸色)，這樣將產生55=3 125種可能的組合，模板數量眾多.但是，其中45的模板卻都屬于干擾模板，也就是2 500種.例如當待預測索引x=0且其鄰域索引值為“2 3 1 2”時，如圖4(a)所示.圖4(b)中的4個模板都會對x的預測過程產生干擾.這表明在干擾模板數量多于正確模板數量的情況下，能夠獲得準確預測值的概率取決于正確的上下文出現的概率.因此，有必要進一步分析各種模板的分布情況.

本文選取JCT-VC公布的19個標準序列的第1幀和3幅文字圖像[21]，并統計其中經過4-鄰域模板匹配預測失敗時所采用的模板集合，從中選取匹配次數最多的模板.表1給出了在這些測試序列和圖像中的失敗索引數量、匹配次數最多的模板數量及對其預測結果構成干擾的模板數量.從表1中能發現，除了“PPT_ Doc_xls”序列，其他18個序列的各項比例相差不大，匹配次數最多的模板平均占預測失敗索引數量的7.017%，對其預測結果構成干擾的模板平均比例為5.901%.若不考慮“PPT_Doc_xls”序列，匹配次數最多的模板平均占比為5.719%，其干擾模板的比例則高達5.710%.這說明即使對于匹配最多的模板來說，干擾模板的影響也是非常明顯的，單一模板所占比例不高；而對于其他的匹配模板，干擾模板的數量甚至會多于正確模板的數量.例如“PCB_Layout”序列，最多匹配的模板占比12.220%，其干擾模板則占比20.847%.在這種情況下，基于模板匹配的索引預測將全部產生錯誤的預測值.可見，干擾模板的大量存在是4-鄰域模板預測效率不高的基本原因之一.

Fig. 4 Example of 4-neighbor interference template圖4 4-鄰域干擾模板示例

SequenceIndex Numberwith PredictionFailure Number ofMost Matched TemplateNumber ofInterferenceTemplate Ratio of MostMatchedTemplate∕%Ratio ofInterferenceTemplate∕%ChinaSpeed16951165911159.7876.578MissionControlClip353807224734854.1766.477CAD_Waveform24700119017964.8187.271Cg_Twist_Tunnel90575937436.5478.204Console23216224315949.6616.866Desktop44087286825576.5055.800FlyingGraphics54514143318092.6293.318Map49550201116874.0593.405PCB_Layout259333169540312.22020.834PPT_Doc_xls5378118431533234.2709.914Programming18013780 7534.3304.180Video_Conferencing180025678523.1504.733Web_Browsing199435939492.9734.759WordEditing31068184310985.9323.534SlideEditing299258487022.8342.346SlideShow110014766124.3275.563Robot50650397515417.8483.042VenueVu96064529246925.5094.884BasketballDrillText19638154111177.8475.688English Text26760153310085.7293.767Simplified Chinese32561177014445.4364.435Traditional Chinese39216148316573.7824.225Average34020257019157.0175.901

另外，本文進一步分析了“PPT_Doc_xls”序列中上下文正確的模板出現比例較高的原因，發現該序列在邊緣位置較少開啟反走樣，基本不受逃逸色和基本顏色的影響，如圖5所示.而對于絕大多數的屏幕內容序列，尤其是那些由顯示適配器生成的圖形元素豐富的序列，反走樣能有效改善其視覺質量.并且，根據文獻[22]的研究發現，屏幕內容中前景物體的邊緣和文字輪廓的反走樣往往出現在2個相鄰的像素之間，形成特定的顏色轉移模式，如圖6所示.故此，邊緣反走樣不僅會導致局部方向預測的失敗，其影響區域、影響方式也與4-鄰域模板不同.本文認為，這是4-鄰域模板預測效率不高的第2個基本原因.

Fig. 5 Enlargement of part of PPT_Doc_xls sequence圖5 PPT_Doc_xls序列的部分區域放大圖

Fig. 6 The color transition pattern in screen content[22]圖6 屏幕內容中的顏色轉移模式[22]

3.2 4-鄰域模板預測的計算效率分析

為分析基于4-鄰域模板的索引值預測的時間復雜度，設模板匹配的搜索窗口為W×H像素，則該搜索窗口中共有W×H個可能的候選模板，且每個候選模板又至多需要4次比較操作，所以采用4-鄰域模板預測1個索引值的時間復雜度為O(W×H)，存儲搜索窗口中已編碼索引的空間復雜度也為O(W×H).從這個意義上講，模板的尺寸越大，其匹配的計算代價越高.

3.3 模板預測的轉移概率模型

通過2.2節的論述可知，模板預測的思路是利用上下文內容的統計相關性來計算待編碼索引的最佳預測值.以4-鄰域模板為例，設Ia，Ib，Ic，Id分別表示圖3中a，b，c，d的索引值，Px表示x的預測值:

(1)

則模板預測在本質上是將使式(1)的聯合條件概率取得極值的I作為x的預測值.本文稱P{I|Ia,Ib,Ic,Id}為“轉移概率”，記為PI←abcd.因此，在預測每個索引值時，沒必要對已編碼索引進行4×W×H次比較操作，而只需仿照Markov過程的轉移概率矩陣建立一張如表2所示的順序表來保存當上文為(Ia,Ib,Ic,Id)時，下文為I∈{0,1,2,3,4}的最大轉移概率.其中，NI←abcd表示由上文(Ia,Ib,Ic,Id)轉移到I的次數.這樣，基于模板匹配的索引值預測就轉化為查表操作，時間復雜度由O(W×H)降到O(1)；同時，由于Ia，Ib，Ic，Id，I各有5種可能的取值，即{0,1,2,3,4}，轉移概率表最多有55=3125行，故此預測1個索引值的空間復雜度就從O(W×H)變成O(3125×7)(7表示每條表項的列數).當然，若搜索窗口較小，這種基于順序表的實現方式反而會增加內存開銷.

Table 2 The Table Structure of Transition Probability表2 轉移概率表的結構

4 基于2-鄰域聯合轉移概率的索引圖預測

鑒于4-鄰域模板所存在的問題，在本節中，我們根據索引值局部預測失敗的情形來討論恰當的預測模板結構，并給出詳細的索引圖非局部預測算法.

4.1 索引圖預測的2-鄰域模板

本文從JCT-VC公布的19個標準測試序列的前90幀和3幅文字圖像中選取了2 000個局部方向預測失敗的索引值，發現這些索引值大多位于逃逸色和基本顏色變化明顯的區域，與文獻[22]所指出的前景物體邊緣和文字輪廓的反走樣區域一致.同時，經過仔細對比分析還發現，這些局部預測失敗的索引主要分布在前景物體邊緣和文字輪廓的左上部、左下部、右上部和右下部，如圖7所示.因為只有在這4種位置時，待預測索引才可能頻繁出現與其相鄰索引不相關的值.

Fig. 7 The color transition pattern in screen content圖7 屏幕內容中的顏色轉移模式

基于圖7分析結果，本文提出了一種2-鄰域模板，如圖8所示，它由4個子模板構成，分別對應前景物體邊緣或文字輪廓的4種拐角位置.下面對該模板的預測效率進行分析.

Fig. 8 The proposed 2-neighbor template圖8 本文提出的2-鄰域模板

首先，每個2-鄰域子模板只有3個索引值，每個索引值有5種可能取值(4種基本顏色和1種逃逸色)，故而每個2-鄰域子模板包含53=125種可能的組合，這個數量僅相當于4-鄰域模板的4%.當然，其中也有4/5的模板屬于干擾模板，該比例與4-鄰域模板相同.

其次，我們統計了19個標準測試序列的第1幀和3幅文字圖像中，匹配次數最多的前10個4-鄰域模板和前10個2-鄰域模板占全部模板的比率，結果如表3所示.從表3可見，約有50%的局部方向預測失敗的索引值能夠利用前10個2-鄰域模板進行預測，而對于前10個4-鄰域模板，該比例僅有30%.一方面，該統計結果驗證了文獻[22]的結論，即邊緣反走樣在相鄰的2個像素之間形成特定的顏色轉移模式，使得2-鄰域最優匹配模板的比例明顯提高；另一方面，由于最佳匹配模板更加集中，其干擾模板所占的平均比例必然降低，基于2-鄰域匹配模板的索引預測準確率將得到有效提高.

Table 3 The Ratio Comparison Between Top10 4-Neighbor Templates and 2-Neighbor Templates表3 匹配最多的前10種4-鄰域模板和2-鄰域模板所占比例的對比情況

Continued (Table 3)

最后，因為每個2-鄰域子模板最多包含125種組合，4個子模板就有500種可能組合，所以若采用3.3節所述的順序表來實現基于模板匹配的索引預測，那么順序表只需500條表項，且每條表項只有5列，其空間復雜度為O(500×5)，這一復雜度低于多數基于搜索的模板匹配所需的空間代價，對目前幾乎所有的計算機系統而言均不構成負擔.

4.2 基于2-鄰域聯合轉移概率的索引值預測

雖然最佳的2-鄰域模板平均占比很高，可是仍然不能避免干擾模板的影響.并且，對于某個局部方向預測失敗的索引值x，我們無法有效判定它處于前景物體或文字輪廓的左上部、左下部、右上部還是右下部.故此，本文采用線性加權法計算4個2-鄰域子模板的聯合轉移概率實現對索引x的預測，進而降低干擾模板造成的影響.具體地講，令PI←ab表示子模板1(如圖8(a)所示)的轉移概率(I∈{0,1,2,3,4})，PI←cd表示子模板2(如圖8(b)所示)的轉移概率，PI←bc表示子模板3(如圖8(c)所示)的轉移概率，PI←ac表示子模板4(如圖8(d)所示)的轉移概率，則4個子模板同時向索引值“0”的聯合轉移概率為

(2)

S0=P0←ab+P0←cd+P0←bc+P0←ac.

(3)

同理，4個子模板同時向索引值“1”，“2”，“3”，“4”的聯合轉移概率分別為

(4)

S1=P1←ab+P1←cd+P1←bc+P1←ac；

(5)

(6)

S2=P2←ab+P2←cd+P2←bc+P2←ac；

(7)

(8)

S3=P3←ab+P3←cd+P3←bc+P3←ac；

(9)

(10)

S4=P4←ab+P4←cd+P4←bc+P4←ac.

(11)

最終，聯合轉移概率最大的值即為待編碼索引x的最佳預測值，即：

(12)

4.3 基于聯合轉移概率的索引值預測步驟

在4.1節和4.2節的基礎上，本節給出基于聯合轉移概率的索引值預測算法的具體預測步驟.

算法1. 基于聯合轉移概率的索引值預測算法.

輸入：待編碼視頻序列、4個2-鄰域子模板對應的轉移概率表PI←ab，PI←cd，PI←bc，PI←ac(PI←ab表結構如表4所示，其余各表與之類似)、序列長度F；

輸出：索引圖的預測誤差.

初始化：將轉移概率表PI←ab，PI←cd，PI←bc，PI←ac的Times，Transition Probability項均清0.

① 令f=1；

② 利用文獻[20]計算得到第f幀的索引圖，若f%L=1，則轉入步驟③；否則，轉入步驟⑦，其中，“%”表示模運算，L為用于調節Markov轉移概率表更新頻率的預設參數(實驗中L=10)；

③ 若f=1，則對關鍵幀進行索引圖預測：

④ 對于某個索引值x，采用文獻[21]的局部方向預測算法對其進行預測，若算法執行至文獻[21]的步驟⑦)(見本文2.1節)，表示局部方向預測失敗，則轉入步驟⑤；否則，轉入步驟⑥；

⑤ 利用索引值x及其鄰域索引值更新轉移概率表PI←ab，PI←cd，PI←bc，PI←ac的相應表項；

⑥ 輸出預測誤差x-Px，若關鍵幀的所有索引值都已處理完畢，則轉入步驟；否則，返回步驟④；

⑦ 對非關鍵幀進行索引圖預測：

⑧ 對于某個索引值x，采用文獻[21]的局部方向預測算法對其進行預測，若算法執行至文獻[21]的步驟⑦)(見本文2.1節)，則轉入步驟⑨；否則，轉入步驟⑩；

⑨ 查詢轉移概率表PI←ab，PI←cd，PI←bc，PI←ac的相應表項，并代入式(2)～(12)中計算Px；

⑩ 輸出預測誤差x-Px，若當前幀的所有索引值都已處理完畢，則轉入步驟；否則，返回步驟⑧；

Table 4 The Table Structure of Transition Probability PI←ab表4 轉移概率表PI←ab的結構

5 實驗與結果

為了驗證本文算法的有效性，選用JCT-VC公布的19個標準測試序列的前90幀和3幅包含英文、簡體中文和繁體中文的圖像進行實驗.

所有實驗均在各視頻幀/圖像的亮度分量進行，首先利用文獻[20]的算法計算得到亮度分量的索引圖，再采用本文算法進行預測并統計預測準確率，同時將結果與MSP[19]算法、局部方向預測算法[21]的預測準確率進行比較.

5.1 預測準確率比較

表5給出了本文算法、MSP算法、局部方向預測算法(local directional prediction， LDP)在各個測試序列上得到的預測準確率.對比發現，本文算法對所有測試序列的預測準確率均高于MSP和方向預測方法，分別比兩者平均提高4.50%和2.27%.

一方面，Map，Robot，BasketballDrillText，China-Speed這4個視頻序列不僅包含字符，還包含由顯示適配器生成的大量幾何圖元，本文算法的預測準確率分別比MSP和方向預測算法提高了9.29%和4.70%.另一方面，對于英文文本、簡體中文和繁體中文的純文本類型圖像，本文算法分別比MSP和局部方向預測算法平均提高了8.51%和4.63%.這2類視頻序列和圖像的共同特點是顯示適配器開啟了邊緣反走樣，可見本文算法的2-鄰域模板能夠比MSP算法的4-鄰域模板更加有效地處理屏幕內容在邊緣漸變區域的索引值非局部預測.然而，對于平滑區域較多、反走樣像素很少甚至未開啟反走樣的序列(如“PCB_Layout”和“CAD_Waveform”等)，局部方向預測已達到很高的準確率，基于2-鄰域模板的非局部預測與4-鄰域模板基本相當，故此性能提升不如上述序列那么明顯.

另外，表5的最后3列分別給出了MSP算法、局部方向預測算法和本文算法在90幀上的預測準確率的平均標準偏差.具體來看，本文算法的預測準確率的平均波動幅度僅是MSP算法的37.5%，是局部方向預測算法的47.37%.所以，本文算法有利于產生更加平穩的預測誤差和輸出碼流.

Table 5 Prediction Accuracy Comparison Among Various Algorithms表5 不同算法的預測準確率比較

5.2 時間復雜度比較

需要指出，本文算法僅對2次方向預測失敗的索引值才進行2-鄰域聯合轉移概率的預測，其數量約占全部待預測索引值的4.57%.由4.2節和4.3節的論述可知，對于非關鍵幀中每個局部方向預測失敗的索引值，本文算法需首先在轉移概率表上進行4次查表操作，取出轉移概率PI←ab，PI←cd，PI←bc和PI←ac；然后，將其代入式(2)～(11)計算聯合轉移概率P(Ix=0)，P(Ix=1)，P(Ix=2)，P(Ix=3)，P(Ix=4)，由式(2)～(11)的定義，該過程需要20次乘法、20次除法和30次加法；最后，將上述5個聯合轉移概率代入式(12)計算最大聯合轉移概率，還需要4次比較運算.故此，本文算法僅用常數次操作即可預測非關鍵幀的1個索引值，其漸近時間復雜度為O(1).而對于關鍵幀中每個局部預測方向失敗的索引值x，本文算法需先根據x及其鄰域索引值a，b，c，d對轉移概率表PI←ab，PI←cd，PI←bc，PI←ac各執行1次查表操作定位到相應的表項，再各用1次加法、1次除法分別更新表項的Times列和Transition Probability列，顯然該過程的時間復雜度也為O(1).綜合上述2種情況，本文算法處理1個索引的時間復雜度為O(1)，與局部方向預測算法的漸近時間復雜度[21]相同.

同時，由3.2節的分析可知，對于W×H像素的搜索窗口，MSP算法在預測1個索引值時需要匹配W×H個4-鄰域模板，且每個模板至多需要4次比較操作，其漸近時間復雜度為O(W×H).從這個意義上講，本文算法的時間復雜度比MSP降低了W×H倍.

6 總 結

本文通過對局部方向預測失敗的索引值的4-鄰域模板預測結果進行分析，發現4-鄰域模板不適合用于刻畫邊緣反走樣區域的顏色轉移模式，進而設計了一種2-鄰域的匹配模板，并將模板匹配建模為一種可借助查表操作實現的轉移概率問題，在此基礎上提出一種2-鄰域聯合轉移概率的非局部索引值預測算法.實驗結果表明，該算法的預測效率分別比MSP方法和局部方向預測算法平均提高了4.50%和2.27%，并且其計算復雜度明顯低于前者，與后者同階.

[22]Gisquet C, Laroche G, Onno P. Non-RCE4: Transition copy mode for palette mode, JCTVC-P0115[R]. Geneva, Switzerland: ITU-T, 2014SongChuanming, born in 1980. Associate professor of the School of Computer and Information Technology of Liaoning Normal University. Received his PhD degree at the Department of Computer Science & Tech-nology of Nanjing University. Member of CCF. His main research interests include image and video coding, and digital water-marking of multimedia.