基于QM算術編碼器的CX序列的反推原理及實現

徐世寅，徐妮妮，楊雪玲，王 靜

（天津工業大學電子與信息工程學院，天津 300387）

基于QM算術編碼器的CX序列的反推原理及實現

徐世寅，徐妮妮，楊雪玲，王 靜

（天津工業大學電子與信息工程學院，天津 300387）

通過對ISO/IEC 10918-1：1993（E）中的QM算術編碼器流程圖和測試序列進行分析，得出CX序列反推原理.利用測試序列中已有的D、MPS、Qe 3列數據，結合QM算術編碼器的概率推斷狀態機和最小化原則，將QM算術編碼器的測試序列中所缺的CX序列補充完整，同時得到MPS、Index的初始值，然后將所得數據輸入QM算術編碼器，驗證所產生CX序列的正確性.

CX序列；QM算術編碼；最小化原則；反推原理

QM算術編碼是一種自適應二進制算術編碼[1-5]，是IBM公司的專利技術.它采用遞歸劃分概率區間的編碼方式，當有足夠多的數據輸入時，QM算術編碼能夠逼近香農熵編碼極限，比霍夫曼編碼擁有更高的編碼效率和靈活性，被廣泛應用于JBIG[1]和JPEG[6]國際標準中.國內算術編碼方面的文獻相當缺乏，僅有的一篇論文原理還不正確，并且算術編碼器方面的測試實例更是難以找到. ISO/IEC10918-1：1993（E）國際標準[6]給使用者設置了相當高的門檻，并且標準中給出的流程圖存在瑕疵，導致使用者無法看懂和正確理解QM算術編碼器.在標準中雖然給出了QM算術編碼器的流程圖和測試序列，但是標準制定者卻故意把測試序列中的CX序列隱去了，讓初學者很難通過流程圖和測試序列看懂和正確使用QM算術編碼器.因此，本文在QM算術編碼器的基礎上，給出CX序列的反推原理、實現及相關分析，編程產生CX序列、MPS的初始值、Index的初始值，使測試序列成為一個完整的實例，并將產生的各序列輸入QM算術編碼程序，驗證其正確性.

1 CX反推原理

1.1CX在QM算術編碼器中的作用

QM算術編碼的編碼器、解碼器如圖1所示.

圖1 QM算術編碼的編碼器與解碼器Fig.1 Encoder and decoder of QM arithmetic

在編碼器中，上下文索引CX和待壓縮二進制數據D構成比特、索引對，例如（1，17），（1，19），（0，36）輸入編碼器編碼產生壓縮數據，壓縮數據以十六進制字節的形式存儲，例如0X65，0X7D，0X46；在解碼器中，與編碼器中相同的上下文索引CX和存儲的壓縮數據共同輸入解碼器，解碼產生原始二進制數據D.上下文索引CX由DCT變換的量化系數所得，具體產生過程請參考ISO/IEC 10918-1：1993（E）國際標準中的相關說明.

1.2 CX反推原理變量說明

反推原理中用到的變量包括：CX、D、MPS（CX）、Index（CX）、NMPS、NLPS、Switch.上下文索引CX為所求的變量，它的取值變化范圍為0～294；待壓縮數據D為二進制，它的取值范圍為0，1；MPS（CX）是對應于每個CX的大小概率判斷標志，MPS（CX）取值范圍為0，1；Index（CX）是對應于每個CX的概率推斷狀態機中的索引值，Index（CX）取值范圍為0~113，在概率推斷狀態機中每個Index（CX）都對應NMPS、NLPS、Switch 3個變量；NMPS為下一個大概率索引值；NLPS為下一個小概率索引值；Switch為大小概率判斷標志的反轉標志.NMPS、NLPS的取值范圍與Index（CX）相同，Switch的取值范圍為0，1.為便于查看，上述變量的取值范圍如表1所示.

表1 變量取值表Tab.1 Variable value table

Qe、Index（CX）、NMPS、NLPS、Switch共同組成概率推斷狀態機，在編解碼中用到的變量Qe值與概率推斷狀態機中的Index（CX）相對應，根據Qe值可在概率推斷狀態機中查到與之對應的Index（CX）、NMPS、NLPS、Switch值，以便確定下一個狀態.

1.3 MPS（CX）與CX的關系

待壓縮數據D輸入算術編碼器后，根據D是0或1，選擇是CODE1還是CODE0流程，如圖2所示.

在進入子程序后，根據MPS（CX）的值選擇是大概率還是小概率子程序.由流程圖可知，當D和MPS（CX）的值相同時進行大概率編碼，不同時進行小概率編碼.MPS（CX）為當前CX大小概率標志，程序初始化時默認MPS（CX）=1為大概率，MPS（CX）=0為小概率；當遇到大小概率判斷標志的反轉標志Switch=1時，MPS（CX）的大小概率判斷標準發生反轉，MPS（CX）=0為大概率，MPS（CX）=1為小概率；當再次遇到Switch=1時，MPS（CX）將反轉回默認值.

圖2 編碼1和0的流程Fig.2 CODE1 and CODE0 procedure

1.4 Qe、Index（CX）與CX的關系

當進入大小概率編碼子程序時，程序根據CX的值查概率推斷狀態機找到相應Index（CX）對應的Qe值進行編解碼，操作相關區間寄存器和編碼寄存器，然后根據CX對應的Index（CX）值查概率推斷狀態機找到對應的下一個遷移狀態的Index（CX），即NMPS、NLPS值，并根據Switch的值完成MPS（CX）的條件性反轉.

1.5 CX反推原理說明

根據以上CX自身及相關量的描述，可以確定基于ISO/IEC 10918-1：1993（E）中測試序列的CX反推原理.在測試序列中，MPS（CX）是測試序列的最終結果，并不是每個CX對應的MPS（CX）初始值，同時在測試序列中，根據Qe值，查找概率推斷狀態機可找到對應的Index（CX）值.將測試序列中的Qe值替換成Index（CX）值，構成新數據表，由于篇幅限制，讀者可自行完成新數據表，此處僅列出部分數據，如表2所示.

表2 數據表Tab.2 Data table

設變量index（CX）（CX為變量，變化范圍為0~ 294），用以記錄當前正在使用的Index（CX）值（Index（CX）代表數據表2中的256個數據中的一個，僅是代表值的符號而已）；設變量mps（CX）（CX為變量，變化范圍為0~294），用以記錄當前正在使用的MPS（CX）值（MPS（CX）代表數據表2中的256個數據中的一個，僅是代表值的符號而已）.初始化第一個index（CX=0）=0，mps（CX=0）=0.

CX反推原理主要分為2部分：①已有值index（CX）的處理；②新賦值index（CX）的處理.反推原理中用到了產生CX的最小化原則，即每次都將原CX加1賦給下一個新CX，這樣產生的CX的數值范圍最小.反推原理通過處理index（CX）值來產生CX值，并通過最小化原則控制產生CX的數值范圍最小.

對于選擇哪一部分產生CX，需要判斷index（CX）所記錄的值中是否有與當前Index（CX）相等的值，即遍歷所有已有值index（CX）查找.如果有，則選擇已有值index（CX）部分處理；如果沒有，則選擇新賦值index（CX）部分處理.

對于已有值index（CX）部分，首先判斷數據表2中與Index（CX）對應的D與MPS（CX）是否相等，以便確定是大概率還是小概率.如果是大概率，將與數據表2中Index（CX）對應的NMPS值賦給index（CX），確定下一個index（CX）的更新值，然后判斷當前mps（CX）值是否與數據表2中當前Index（CX）對應的MPS（CX）值相同.如果相同，則將數據表2中當前MPS（CX）值的下一個值賦給當前mps（CX）；如果不相同，則需要從新賦值的index（CX）處重新開始.如果是小概率，將與數據表2中Index（CX）對應的NLPS值賦給index（CX），重復大概率index（CX）更新值后的過程，最后將出現過的CX記錄下來.

對于新賦值index（CX）部分，即產生新的CX，將數據表2中Index（CX）當前值賦給index（CX），然后判斷D與MPS（CX）是否相等，以便確定是大概率還是小概率.如果是大概率，將與數據表2中Index（CX）對應的NMPS值賦給index（CX），確定下一個index（CX）的更新值，然后將數據表2中當前Index（CX）對應的MPS（CX）值賦給mps（CX）；如果是小概率，將數據表2中與Index（CX）對應的NLPS值賦給index（CX），確定下一個index（CX）的更新值，然后將數據表2中當前Index（CX）對應的MPS（CX）值賦給mps（CX）.將期間使用過的CX記錄下來.

在新賦值index（CX）部分，每次都是產生新的CX，即index（CX）和mps（CX）記錄的都是Index（CX）和MPS（CX）的初始值.因此可以通過以上過程獲得CX值，Index（CX）、MPS（CX）初始值.

2 CX反推原理流程圖

CX反推原理總流程圖如圖3所示.程序通過Initialize程序初始化所需的變量，通過Find index[CX]程序查找與Index[CX]相等的index[CX]，如果找到則執行Old_index[CX]子程序（已有值index（CX）部分），如果沒有找到，則執行New_index[CX]子程序（新賦值index（CX）部分）.

圖3GET_CX流程Fig.3 GET_CX procedure

Initialize程序如圖4所示.初始化各變量，初始化CX=0，變量CX用以記錄當前正在使用的CX的值；初始化y=0，變量y用以記錄新產生CX的值；初始化result=0，變量用以記錄當前Old_index[CX]和New_index[CX]的選擇標志位，即是否找到了匹配的index [CX]，result=0表示未找到，result=1表示已找到；初始化數組index[295]，用以記錄各個CX對應的index [CX]值；初始化數組mps[295]，用以記錄各個CX對應的mps[CX]值；初始化數組cx[256]，用以記錄測試序列中使用過的CX.

Find index[CX]程序如圖5所示，通過遍歷所有已有的index[CX]來查找與Index[CX]匹配的index[CX]，返回已有的CX值和子程序選擇標志位result以確認使用Old_index[CX]和New_index[CX]哪一個子程序來產生CX.

圖4 初始化流程Fig.4 Initialisation procedure

圖5 Find index[CX]流程Fig.5 Find index[CX]procedure

圖6所示為Old_index[CX]子程序流程，在流程中存在無條件跳轉Go to Mark，跳轉到主程序Mark處轉而執行New_index[CX]子程序.圖7所示為New_index [CX]子程序流程.

圖6 Old_index[CX]流程Fig.6 Old_index[CX]procedure

圖7 New_index[CX]流程Fig.7 New_index[CX]procedure

3 實驗結果驗證

實驗是在VC6.0[7]環境下測試通過的，運行程序得到數據CX、MPS初始值、Index初始值，如表3所示.

表3 CX對應MPS和Index初始值Tab.3 Initial value of MPS and Index corresponding to CX

測試序列中共256個CX取值，CX取值如表4所示.

表4 所有CX值Tab.4 All values of CX

為了驗證GET_CX程序的正確性，將程序中所得的數據和待壓縮數據D輸入QM算術編碼器，QM算術編碼器程序仍然在VC6.0環境下運行，程序運行正確，在此僅將測試序列編碼表的部分數據列出，測試序列的解碼表中的CX與編碼表中對應CX值相同，程序結果如表5所示.

表5 測試序列Tab.5 Test sequence

4 結束語

故意缺省CX列的測試序列，給人們學習QM算術編碼器帶來諸多困難.本文設計的CX序列反推程序很好地解決了這個問題，并且提供了完整的測試序列所需的CX、MPS和Index初始值，供人們測試自己編寫的QM算術編碼器；而且在設計CX反推程序的過程中，涉及到一些QM算術編碼器的概念理解，對人們學習QM算術編碼器起到了一定的啟發作用，舉一反三，對理解其他算術編碼器也有一定的幫助.

[1] 小野定康，鈴木純司（日）.JPEG技術[M].葉明，譯.北京：科學出版社,2003.

[2] 小野定康，鈴木純司（日）.JPEG2000技術[M].強增福，譯.北京：科學出版社，2004.

[3] LANGDON G.IBM J Res Develop:An Introduction to Arithmetic Coding[Z].1984.

[4] ONO F,YOSHIDA M，KIMURA T，et al.Subtraction-type arithmetic coding with MPS/LPS conditional exchange[C]//Annual Spring Conference of IECED.Japan:D-288，1990.

[5] LANGDON G.Method for carry-over control in a fifo arithmetic code string[J].IBM Technical Disclosure Bulletin，1980，23（1）：310-312.

[6] CCITT.ISO/IEC 10918-1，T.81(09/92)[Z].FRENCH:CCITT，1992.

[7] HANLY Jeri R，KOFFMAN Elliot B.Problem Solving and Program Design in C[M].萬波，潘蓉，鄭海紅，譯.北京：人民郵電出版社，2007.

Backstepping principle and implementation of CX sequence based on QM arithmetic encoder

XU Shi-yin，XU Ni-ni，YANG Xue-ling，WANG Jing
（School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China）

The backstepping principle of CX sequence is obtained by the analysis of the flow chart and test sequence about QM arithmetic encoder in ISO/IEC 10918-1：1993(E).Using D,MPS,Qe,the three columns of data in test sequence,and combining probability estimation state machine of QM arithmetic encoder and the minimization principle,the test sequence of QM arithmetic encoder is supplemented with its lacking CX sequence,meanwhile,initial values of MPS and Index is gotten.Then,the obtained data are entered into QM arithmetic encoder and the correctness of produced CX sequence is verified.

CX sequence；QM arithmetic encoder；minimization principle；backstepping principle

TN911.7

：A

：1671-024X（2013）01-0061-05

2012-05-16

：國家自然科學基金資助項目（60602036）

徐世寅（1986—），男，碩士研究生.

徐妮妮（1974—），女，博士，副教授，碩士生導師.E-mail:xunini@tjpu.edu.cn