算術符号の簡易化・高速化について ～STT-coder の紹介～ 小野 文孝† 上野幾朗‡ †東京工芸大学 (現在 早稲田大学・東京大学) ‡東京工芸大学 (現在 三菱電機(株) ) E-mail: [email protected] あらまし 算術符号は高い圧縮性能と様々な情報源に適用できる汎用性を有する．しかし，その演算負荷が高いため， 如何に効率を保ったまま演算負荷の低減を行うかという検討が長年進められてきた．その結果，最近では，算術符号が多くの画 像／映像符号化標準に採用されるようになっている．しかしながらハフマン符号と比較すると依然としてその負荷は大きく，算 術符号の普及の妨げとなっていると考えられる．そこで，ハフマン符号と同様に状態遷移先と符号とを出力する状態遷移テーブ ルを参照して算術符号化処理を実行させることにより算術符号化の簡易化を図る STT-coder が筆者らにより提案されている．本 報告では STT-coder の狙いとその性能並びに今後の発展の可能性について紹介する． キーワード 算術符号，静止画符号化, ハフマン符号，ROM Simplified and High-Speed Arithmetic coder Introduction of STT-coder Fumitaka ONO† Ikuro UENO†‡ †Tokyo Polytechnic University (now with Waseda Univ. and The Univ. of Tokyo) ‡Tokyo Polytechnic University (now with Mitsubishi Electric Corp.) E-mail: [email protected] Abstract Arithmetic coding has flexible adaptability to various information sources, and provides high coding efficiency. Its disadvantage is the complexity of operations, and the most studies to simplify and speed up arithmetic coding have been tuned for the simplification of the interval calculation for symbols such as in range coder, Q-Coder and MQ-Coder. Thanks to the effort, it is now adopted in many image and video coding standards. However, the simplification is still necessary to be prevailed more widely. Recently, STT-coder has been proposed by us, in which, arithmetic operation is realized by state transition table, just like the case of Huffman coding. In this report, we will introduce the background idea of STT-coder and its performance and future possibility to be developed. Keyword arithmetic coder, still image coding, Huffman coding 1. ま え が き で 行 わ れ て き た ． 初 期 の も の と し て は LR 符 号 1) があ り LPS の 確 率 を (1/2)の べ き 乗 に 限 定 し ，シ フ ト 演 算 で 算術符号は高い圧縮性能と様々な情報源に適用でき LPS の 領 域 幅 を 求 め る も の で あ る ． 続 い て 提 案 さ れ た る 汎 用 性 を 有 す る ．し か し ，そ の 演 算 負 荷 が 高 い た め ， Q-Coder 2) で は LPS の 領 域 幅 を 有 効 領 域 幅 に よ ら ず 固 如何に効率を保ったまま演算負荷の低減を行うかとい 定としていた．有効領域幅は最大で 2 倍の範囲を動く う検討が長年進められてきた．その結果，最近では， ので想定確率としては 2 倍の範囲で変動が生じるが固 算術符号が多くの画像／映像符号化標準に採用される 定 で あ っ て も 確 率 を 限 定 し た LR 符 号 よ り 高 い 性 能 が ようになっている．しかしながらハフマン符号と比較 得 ら れ る ． Q-Coder は 確 率 が 1/2 近 辺 で LPS の 領 域 幅 すると依然としてその負荷は大きく，さらなる普及の が MPS の 領 域 幅 を 上 回 る こ と が あ る の で そ の 補 正 を ためにはより簡易化する必要があると考えられる．こ 行 う 処 理 を 加 え QM-coder 3) や MQ-coder 4) と し て 標 準 に れまでの算術符号の簡易化は主として領域計算の分野 採用されている． 算 術 符 号（ 非 ブ ロ ッ ク 符 号 ）と 通 常 の ハ フ マ ン 符 号（ ブ 領域の下限アドレスと上限アドレスを比較して確定し ロック符号）を比較するとその大きな相違はハフマン た部分が取り出せることになる．最終的にはフラッシ 符号では符号ツリーをたどることで符号化／復号が行 ュ処理を行い領域を特定できる最小限のアドレスを出 えるのに対し，算術符号では一般にそれが困難である 力 す る ．こ の た め 有 効 領 域 の 下 限 を 常 に 記 憶 し て お き ， ことがあげられる．ハフマン符号において符号ツリー 座標確定部を符号として出力する作業が必要になるが， をたどるということは符号ツリーのノード（節）アド この処理は状態遷移による記述では効率よく表現でき レスを遷移先とする状態遷移として符号化／復号を記 ないといえる． 述することであり，符号が確定する場合は出力符号語 一方状態遷移テーブルにより記述する算術符号では を記述し，遷移先はルート（根）に戻る．したがって こ の 14 通 り の 領 域 の ど れ か に 達 す る ま で は 再 正 規 化 算術符号を簡易化する上でハフマン符号と同様に状態 は行わず，再正規化では常にフラッシュ処理を行うも 遷移テーブルによって算術符号の動作を記述できるよ のとして考えることができる．通常の算術符号ではフ うにすることが簡易化につながるといえる．本報告で ラッシュ処理を行う際に有効領域を符号にするうえで はこのような考え方に基づき筆者らによって提案され 無駄な領域が存在してしまうが，これは最後のシンボ た 2 値 の 算 術 符 号 で あ る STT-coder 5) , 6) について紹介す ルである以上避けられないことである．しかし状態遷 移型算術符号ではフラッシュを行うのは最後のシンボ るとともに今後の発展について述べる． ルとは限らないので算術符号として領域の無駄がない 2. 状態遷移による符号化処理の記述 よ う に で き る ． た と え ば 図 2 の a)に 示 す 100 か ら 110 の 領 域 は 大 き さ が (1/2)の べ き 乗 で は な い の で ， 通 常 の 2.1. 3 ビットシステムでの例（方式１） 算術符号でフラッシュを行う場合はこの領域に対応し 算術符号の利点はマルチコンテクスト情報源への対 た 符 号 と し て 10（ 100 と 101 の 共 通 部 分 ） と せ ざ る を 応であり，シングルコンテクスト情報源が対象であれ 得 ず 110 の 部 分 に 無 駄 が 生 じ る ． ま た b)の 001 と 010 ば算術符号を採用する利点はないといってよい．そこ の 領 域 で あ れ ば 大 き さ は (1/2) の べ き 乗 で あ る が 対 応 で算術符号の適用情報源としてマルチコンテクスト情 符 号 は 001 か 010 の い ず れ か と せ ざ る を 得 ず ， 領 域 が 報源を想定する．また多値の算術符号も提案されてい この半分の場合と同じになってしまい，やはり無駄が るが，2 値の算術符号の方が汎用性が高いので符号化 生じる． 対象としては 2 値情報源を考えることとする． 状態遷移型算術符号では次の情報源シンボルが存在 STT-coder で は ま ず 符 号 化 の た め の レ ジ ス タ 長 （ 数 直 す る の で 次 の シ ン ボ ル の 符 号 化 に お い て a)は c)に b) 線アドレスの精度）が 3 ビットの例をとりあげ状態遷 は d) に 分 割 が で き る た め 領 域 の 無 駄 が 生 じ な い ． 移による符号化処理の考え方について考察している． STT-coder で は こ の よ う に 後 続 の シ ン ボ ル を 組 み 合 わ 3 ビ ッ ト シ ス テ ム で は ，ハ フ マ ン 符 号 で あ れ ば 符 号 語 せた情報源の拡大に相当する処理を取り入れており， の種類としては最大で図１のように 1 ビット符号（2 これを「拡大フラッシュ」処理と称している．ただ分 通 り ），2 ビ ッ ト 符 号（ 4 通 り ），3 ビ ッ ト 符 号（ 8 通 り ） 割がシンボル生起確率によらず固定となり情報源のシ の 14 通 り が あ り ，算 術 符 号 の 処 理 過 程 で は 途 中 状 態 と ンボル出現確率の相違（コンテクスト）に基づく領域 してそれらを複数含む連続領域が考えられる．つまり 分割制御が行えないことになる．逆に通常の算術符号 各 状 態 を 遷 移 し 有 効 領 域 が こ の 14 通 り の ど こ か に 達 で あ れ ば a)の 場 合 も b)の 場 合 も 最 終 シ ン ボ ル で な い 限 した時に符号を発生すると考えることでハフマン符号 り再正規化を行うので有効領域を回復することが可能 と全く同様に算術符号の動作を状態遷移により記述で になり，効率低下を防げるがそのためには有効領域の きると考えられる． 下端アドレスを記憶しておく必要があり，状態遷移テ ーブル参照型算術符号とはならないといえる． １１１ １１０ １０１ １００ ０１１ ０１０ ００１ ０００ 図 1 １１ １ 111 111 111 111 110 101 100 011 110 011 010 001 000 110 101 100 011 010 001 000 (c) (d) １０ ０１ ０ ００ 3 ビットシステムでとりうる符号 011 010 001 000 (a) 通常の算術符号においては 3 ビットシステムなら有 効領域幅が 4 以下になれば再正規化を行い有効領域幅 を 5 から 8 の間の値に回復する．また符号出力は有効 000 (b) 図 2 10 有効領域と符号 R8(領域幅=8) 3P 111 L 111 L 11 LM 11 110 L1 LL 101 101 100 M 011 M M 010 M0 001 000 LPS幅 1 2 3 R7(領域幅=7) 111 110 101 100 011 010 001 000 4 LPS幅 R6(領域幅=6) 2P 111 110 101 100 011 010 001 000 3Q L 110 LM 110 LL110 LL101 LM 10 M 1 M M0 2 3 LPS幅 L 101 R5(領域幅=5) L 10 LM 10 3R M M0 LL011 ML010 3M MM 00 1 2 3 111 110 101 100 011 010 001 000 LPS幅 L 100 ML100 3N MM 01 M0 L 00 1 2 (a) 方 式 1 R8(領域幅=8) (b) 111 L111 L 11 L 110 1+R6a 101 100 M 011 M M 010 001 000 LPS幅 1 2 3 111 110 101 100 011 010 001 000 L1 M0 4 LPS幅 R6a(領域幅=6) 111 110 101 100 011 010 M1 111 110 101 100 011 010 1+R6a R5a LL100 3N L010 R6(領域幅=6) 111 110 101 100 011 010 001 000 1+R6 M 1 M M0 2 3 LPS幅 R5a(領域幅=5) M M R7(領域幅=7) (c) (a) L110 L L 1+R4a L 01 LM 01 M1 MM 10 3R L011 ML011 001 001 000 000 2 3 LPS幅 図3 1 3R LL011 M M0 M 0+R6 1 2 3 LPS幅 L100 ML100 3N MM 01 M0 L 00 1 2 111 110 101 MM 10 M 10 100 3R 011 ML011 L 01 010 L010 L11 000 1 L 10 LM 10 R4a(領域幅=4) 001 LPS幅 L101 R5(領域幅=5) 111 110 101 100 011 010 001 000 2 LPS幅 1 2 (b) 方 式 2 3 ビ ッ ト STT-coder の 領 域 分 割 パ タ ー ン さ て ，2 値 の 算 術 符 号 で は MPS／ LPS の 概 念 が 一 般 的 3 ビット算術符号の有効領域幅は通常の算術符号で に 用 い ら れ て い る ． こ の た め STT-coder で も ま ず は あ れ ば 最 大 領 域 の (1/8)の 領 域 を 単 位 と し て 5~8 で あ る MPS／ LPS で の 符 号 化 を 前 提 と す る ． そ こ で 数 直 線 の が，方式１の状態遷移型では 4 以下でも再正規化を行 有 効 領 域 と ，情 報 源 の コ ン テ ク ス ト か ら 定 ま る LPS 幅 わ な い こ と が あ り う る の で 2~8 と な る ． そ こ で MPS とを組み合わせて記載したのが図 3 の方式 1 である． 確 率 が 0.5 か ら 0.99 の 場 合 に つ い て 有 効 領 域 幅 が 2~7 こ こ で MPS と LPS の 領 域 配 置 で あ る が LPS の 上 位 配 の場合における符号化効率と，有効領域幅が 8 の場合 置／下位配置は事前に個別の規則をとりきめておけば の符号化効率との差をとり，効率低下の指標として示 受信側でも正しく判断できるので自由度がある．そこ したのが図 4 である．状態遷移型算術符号ではこのよ で 図 3 に あ る よ う に ，基 本 的 に は LPS を 上 位 配 置 と し うに有効領域の小さな状態を如何に避けるかが課題で て い る が ， 有 効 領 域 幅 が 5 で LPS 幅 が 2 の 場 合 の み あることがわかる． LPS を 下 位 配 置 と し て い る ． こ れ は も し 上 位 配 置 で LPS が 出 現 す る と 有 効 領 域 幅 が 2 で 次 の 符 号 化 で は 2.2. 3 ビ ッ ト シ ス テ ム で の 例 (方 式 2） MPS／ LPS と も 領 域 幅 が 1 で 固 定 と な り 効 率 の 低 下 を さ て ，方 式 1 で は 算 術 符 号 の 動 作 を ブ ロ ッ ク 符 号 と 全 も た ら す た め で あ る ．一 方 MPS が 発 生 す れ ば 有 効 領 域 く同様の条件で考えたわけであるが算術符号の考え方 幅 が 3 で こ れ は 続 く 符 号 化 で は MPS 幅 が 2，LPS 幅 が をとり入れることでより効率を高めることを考える． １ に 固 定 的 に 分 け る こ と に な る が ， こ の 場 合 は MPS が上位配置でも下位配置でも同じであり効率に影響が ない． 通 り の い ず れ か が 考 え ら れ ，た と え ば LPS 幅 が 1 の 場 合 で ，MPS が 発 生 す る と LPS 配 置 が 上 位 で も 下 位 で も さらに新たな状態が発生する（図 3 では下位配置を選 択 ）． LPS 幅 が 2 の 場 合 に は LPS 下 位 配 置 が よ く こ の あ と に は 新 た な 状 態 は 生 じ な い ．ま た LPS 幅 が 3 の 場 合 に MPS が 出 現 す る と 有 効 領 域 幅 が 6（ 符 号 000，001 が領域外）という状態に戻る． (c)の 場 合 は 符 号 1 を 出 力 し 有 効 領 域 幅 が 4(000,001, 110, 111 が 領 域 外 ） と い う 新 た な 状 態 が 発 生 す る ． こ の 次 の 符 号 化 で は LPS 幅 が 1 か 2 か を 選 択 で き る の で この再正規化の効果があるといえる．またこのあとに 図 4 有効領域幅が 2 から 7 の場合の符号化効率低下 （ 横 軸 は MPS 確 率 ； 縦 軸 は 有 効 領 域 幅 が 8 の 場 合 に 対する効率低下量） 新たな状態は発生しない． 以上のように上位ビットが確定した時に再正規化を 許容するという条件を採用すると状態遷移でも符号出 力があるかどうかを示す情報が 1 ビット増えるが有効 通常の算術符号化であれば領域が 4 以下になればそ 領域幅の期待値が大きくなり効率向上につながる．ま の 下 位 座 標 に 関 わ ら ず 有 効 領 域 を 2 倍（ 2 の べ き 乗 倍 ） た (a) の よ う に 状 態 数 の 増 加 を 伴 わ な い も の に 限 定 す する再正規化を行う．このため下位座標を記憶する処 る か (b),(c)の よ う に 状 態 数 の 増 加 を 伴 う も の も 許 容 す 理が必要になる．そこでそれぞれの符号化過程をより るかという判断が必要となる．3 ビットシステムでは 詳 細 に み て い く と (a)[有 効 領 域 幅 が 7 で LPS 領 域 が 3 状態数の増加も少ないので方式２ではいずれをも許容 の 場 合 に LPS が 出 現 し た と き ]に つ い て は 符 号 の 最 上 したがよりビット数の大きいシステムではより系統的 位は 1 と確定するので 1 を符号として出力したうえで な検討が望まれるからである． 精度をあげる（この領域を大きさ 6 に拡大する）こと 方 式 １ と 方 式 ２ の 符 号 化 性 能 は 図 5 の よ う に な り ，方 が可能である．つまりフラッシュではない再正規化を 式２では 3 ビットの通常算術符号と比べた性能低下は 限 定 的 に 許 容 す る わ け で あ る ．こ の と き 次 の 遷 移 先（ 有 平 均 と し て 1％ 程 度 に と ど ま っ て い る ． 効 効 領 域 6） は た と え ば 有 効 領 域 幅 が 8， LPS 幅 が 2 で MPS が 出 現 し た 場 合 の 遷 移 先 と 全 く 同 じ で あ り も 3. STT-coder の 一 般 的 設 計 ともと存在している．つまりこの場合は算術符号の再 3 ビ ッ ト シ ス テ ム で の 個 々 の 例 の 考 察 に 基 づ き ，以 下 正規化にあたる処理をしても下位アドレスの記憶は不 要でありまた全体の状態数も増えない．よって方式 1 ではより一般的な設計法の考察を行う． で は こ の 幅 3 の 領 域 を 次 の 符 号 化 で MPS 幅 が 2， LPS 3.1 幅が 1 と分割してその後領域幅 8 に移るようにしてい コンテクスト（モデル情報源）の設計 3 ビットシステムではすべての有効領域に対し，と たのに対し，方式２では符号 1 を出力して有効領域幅 り う る す べ て の LPS 幅 を 考 え て い た ．し か し 一 般 的 な 6 に移るようにすることにする．遷移テーブルの大き 符号化システムを考える上ではより汎用的な考えが望 さとしては方式１であれば符号が出力されるときは必 ましい．このため各種の算術符号との比較も考慮し， ず 初 期 状 態（ 有 効 領 域 幅 8)に 戻 る の に 対 し こ の 処 理 を 許容すると符号が出力されても初期状態以外に遷移す ターゲットとなる情報源のシンボル出現確率に対し効 率 100%の 符 号 方 式 が 用 意 さ れ た と き に ， 符 号 化 す べ る場合があり，このため遷移時での符号出力の有無を き情報源のシンボル確率がターゲットからずれている 示すための情報として遷移テーブルの出力ビットが 1 としても，その符号化効率が満たすべき最低値を設定 ビット増すことになる． し，その基準が満たされない範囲については新たにタ さ て ，最 上 位 ビ ッ ト が 確 定 し た 時 に は 再 正 規 化 を 許 容 ーゲットとすべき情報源のシンボル確率を設定するよ す る と し た 場 合 に 同 様 の 例 を 個 別 に 調 べ る と (b)[有 効 う に す る ．こ の よ う に し て MPS 確 率 が 0.5 近 辺 か ら 増 領 域 幅 が 8 で LPS 領 域 が 3 の 場 合 に LPS が 出 現 し た と 大する方向にターゲットとなる情報源を順次設定して き ]，(c) [有 効 領 域 幅 が 7 で LPS 領 域 が 2 の 場 合 に LPS いく．このようにして個別の符号とは独立なモデル情 が 出 現 し た と き ]も 考 察 対 象 と な る ．し か し ，両 者 に つ 報源群を考えることができる．これは算術符号ではタ い て は (a)と は 異 な り ，遷 移 先 は 新 た な 状 態 で あ り 状 態 ーゲットとなる情報源に基づき符号化方法（有効領域 数が増加してしまう． に対する各シンボル領域幅の設計）が決定されるとい (b)の 時 は 符 号 1 を 出 力 す れ ば 有 効 領 域 幅 が 6（ 符 号 000，001 が 領 域 外 ）と な る が ，こ れ は も と も と 存 在 す る 有 効 領 域 幅 6（ 符 号 110,111 が 領 域 外 ） と は 異 な る ． ま た こ の 後 の 符 号 化 処 理 で は LPS 幅 と し て 1,2,3 の 3 う考え方ができることによっている． 1.00 0.09 0.96 0.07 Coding Efficiency 0.94 方式1 方式2 フラッシュ無 0.92 0.05 0.90 0.03 0.88 0.86 0.84 0.01 Difference from pure coder_ 0.98 0.82 0.80 -0.01 0.5 図 5 0.6 0.7 0.8 MPS probability 0.9 1 符 号 化 効 率 （ 3 ビ ッ ト STT-coder） 表 1 1.000 8 情 報 源 モ デ ル の 中 心 MPS 確 率 0.999 Coding Efficiency 0.997 S0 S1 S2 S3 S4 S5 S6 S7 0.996 0.995 0.994 0.993 0.992 S1 S0 S2 S3 S4 S5S6S7 0.991 0.990 0.5 0.6 0.7 0.8 0.9 1 MPS probability 図 6 中 心 MPS 情報源 モデル 0.998 確率 0.559 0.671 0.769 0.847 0.904 0.942 0.967 0.982 情報源モデルと理想符号での符号化効率 た と え ば ，最 低 符 号 化 効 率 を 0.99 に 設 定 す る と 図 6 3 ビ ッ ト シ ス テ ム で は 各 有 効 状 態 に 対 す る LPS 幅 を の よ う に MPS 確 率 が 最 も 小 さ い 範 囲 で は MPS 確 率 入力情報と考えていたが，このような考え方に立てば 0.559 の モ デ ル 情 報 源 S0 が 定 ま る ． こ れ は MPS 確 率 コンテクストと有効領域幅を入力情報として必要な 0.559 の 情 報 源 用 の 理 想 符 号 と は MPS で の 符 号 長 を LPS 幅 を 得 て 符 号 化 を 行 う 形 の 方 が 状 態 遷 移 テ ー ブ ル log（ 1/0.559），LPS の 符 号 長 を log（ 1/0.441）と す る 符 サイズをより小さくできる余地がある．また動的符号 号 化 で あ り ，こ の 符 号 化 を MPS 確 率 が 0.5 の 情 報 源 に 化においてはコンテクストの遷移を取り扱うので，こ 適 用 す る と 符 号 化 効 率 が 約 99%と な る こ と を 意 味 し て のモデル情報源の考えを動的符号化にも活用できる． い る ． 図 6 に 符 号 化 効 率 の グ ラ フ を 示 す ． ま た ,S0 か ら S7 の 8 個 の モ デ ル 情 報 源 の 中 心 と な る MPS 確 率 は 表 1 のようになる． STT-coder と し て 6 ビ ッ ト シ ス テ ム を と り あ げ る と 3.2 LPS 幅 の 条 件 と オ フ セ ッ ト の 概 念 の 導 入 上に述べたモデル情報源の考え方では有効領域幅 に 対 す る LPS 幅 は モ デ ル 情 報 源 数 に よ り 制 限 さ れ る ． S7 で の LPS 幅 は 有 効 領 域 幅 が 33 か ら 64 の す べ て で 1 また方式２で示したように上位ビットが確定した時に となるので 6 ビットシステムではこの 8 つの情報源を 再正規化を行うという条件の採用については方式２の (b),(c)の よ う に 状 態 数 の 増 加 を 伴 う も の も 許 容 す る か 想定し，この効率が切り替わるところで符号化方式を という問題が残されている． 切り替えればよいことになる． しかし，上位ビットが確定した時に再正規化を行う かどうかを個別に規定するのは避けるべきであろうし， 再正規化に伴う状態数の上限を設定しなければ方式設 計が現実的にならないので上位ビットが確定した時に は常に再正規化を行うという方針を採用し，状態数の 制 御 は LPS 幅 の 制 限 に よ っ て も た ら さ れ る よ う に す る こととした． た と え ば 3 ビ ッ ト シ ス テ ム の 方 式 ２ の (b)の 場 合 に は 有 効 領 域 幅 が 6 で ，符 号 000，001 が 領 域 外 と な っ て い る．このように下位の幅 2 の領域の符号が領域外とな っている状態のことをオフセット 2 と呼ぶことにする． 方 式 ２ の (a)で 生 じ る 有 効 領 域 6（ 符 号 110，111 が 領 域 外）はもともと存在する状態であり，オフセットゼロ 図 7 にあたる． さて 3 ビット方式２ではオフセット 2 の状態からオ フ セ ッ ト 3 の 状 態 が 生 じ て い る ．こ れ は LPS を 下 位 配 オ フ セ ッ ト を ゼ ロ に 限 定 す る こ と で LPS 幅 を 制 限 し た 場 合 の 有 効 領 域 幅 5～ 7 で の 符 号 化 効 率 の 低 下 （ 横 軸 は MPS 確 率 ， 縦 軸 は 領 域 幅 が 8 の場合と比較した効率低下量） 置 と し た た め で あ る ．こ の 状 態 か ら LPS を 下 位 配 置 と す れ ば 領 域 の 上 限 が 固 定 さ れ MPS の 出 現 に よ り 新 た な オ フ セ ッ ト 値 が 登 場 す る ．一 方 LPS を 上 位 配 置 と す 3.3. 6 ビ ッ ト STT-coder の 設 計 上 記 の 考 え を も と に 6 ビ ッ ト STT-coder を 設 計 す る ． れ ば MPS の 出 現 に よ り オ フ セ ッ ト は 固 定 さ れ 上 限 ア ここでシステムパラメータとして決定する必要がある ドレスが変化することになる．もちろん方式２のよう のはオフセットの種類数である．遷移状態数はオフセ に上位ビットが確定し，確定した分の符号を出力して ットの種類と有効領域の上端アドレスの種類で定まり， 再正規化することによりオフセットが変化する場合も 有 効 領 域 の 上 端 ア ド レ ス は 32 か ら 63 の 32 種 類 な の で 生じる． オ フ セ ッ ト の 種 類 の 32 倍 が 状 態 数 と な る ．オ フ セ ッ ト そこで，3 ビット方式２で考えていた有効領域幅に の種類が 1 種類であればオフセット値はゼロのみであ 対 し と り う る す べ て の LPS 幅 を 考 え る 方 針 は 棄 て ，遷 り ，2 種 類 で あ れ ば ゼ ロ と 1 か ら 31 ま で の ど れ か と の 移状態数はオフセットの種類数により定まることから 組み合わせである．ゼロ以外のオフセット値としては オフセットの種類数を制限し，それに基づいて逆に許 領域の上位ビットが決まり有効領域を拡大する場合に 容 で き る LPS 幅 を 定 め ，そ の 結 果 と し て 状 態 数 の 上 限 新たなオフセット値が生じることも考え合わせると偶 が制限されるようにすることを考える． 数に限定してよいと思われるのですべての偶数値につ たとえば 3 ビットシステムに戻りオフセットを 1 種 い て ，MPS 確 率 が 0.5 か ら 0.98 ま で の 平 均 符 号 化 効 率 類（ オ フ セ ッ ト =0）と す る と ，有 効 領 域 幅 が 8 で は LPS を 計 算 し ，そ の 値 が 最 大 と な る オ フ セ ッ ト 値 を 求 め た ． 幅 は 1,2,4 の 3 種 ， 有 効 領 域 幅 が 7 で は LPS 幅 は 1,3 そ の 結 果 ゼ ロ に 追 加 す べ き オ フ セ ッ ト 値 は ま ず 24 が の 2 種 ， 有 効 領 域 幅 が 6 で は LPS 幅 は 1,2 の 2 種 ， 有 よいことがわかった．さらに許容するオフセット値に 効 領 域 幅 が 5 で は LPS 幅 は 1 の み が 許 容 さ れ る ． つ い て は ゼ ロ と 24 は 含 め る と し て 他 の 偶 数 値 と の 組 この時の遷移状態数は有効領域幅の種類数と等し く，8 から 5 までの 4 種で済む．しかし特に有効領域 み 合 わ せ を す べ て 調 べ た ．そ の 結 果 3 番 目 は 16 で あ り ， 4 番 目 は 28 と な っ た ． 幅 が 5 の と き は LPS 幅 が 1 の み な の で LPS 確 率 が 0.5 さらにオフセット数を増やし 8 個のオフセットを調 に 近 い 情 報 源 で の 効 率 低 下 が 大 き い ．そ こ で MPS 確 率 べ る と 0,8,16,20,24,26,28,30 の 組 み 合 わ せ と な っ た ．こ が 0.5 か ら 0.98 の 範 囲 に つ い て 有 効 領 域 幅 が 5~7 の 場 れらの効率を図 8 に示す． 合における符号化効率と 8 の場合の符号化効率との差 オ フ セ ッ ト 数 を 増 や す と MPS 確 率 が 0.5 付 近 の 効 率 を 調 べ ，効 率 低 下 の 指 標 と し て 示 し た の が 図 7 で あ る ． は上昇する．これは特に有効領域幅の小さい状態で 図 4 と比較するとオフセットをゼロのみとすることで LPS 幅 の 許 容 値 が 増 え る 効 果 が 大 き い た め と 思 わ れ る ． MPS 確 率 が 0.5 付 近 で の 効 率 低 下 が 大 き い と い え る ． しかしオフセットの値自体は大きなものが選択される なお一般的にはオフセットの種類を制限するうえ で，どのオフセット値を許容するのが効果的かを調べ る必要が生じる． ため有効領域幅の期待値は小さくなる． この結果オフセットの種類数が 4 の場合に最も高い 平均符号化効率が得られることがわかる．なお，オフ セ ッ ト 値 が 24 で あ れ ば LPS 幅 8， オ フ セ ッ ト 値 が 28 で あ れ ば LPS 幅 4 の 場 合 が 上 位 ビ ッ ト 確 定 に つ な が る ． 1.000 ideal Coding Efficiency 0.990 N=4 N=3 N=2 0.980 N=8 0.970 N=1 N=1 (D=0) N=2 (D=0,24) N=3 (D=0,16,24) N=4 (D=0,16,24,28) N=8 (D=0,8,16,20,24,26,28,30) 0.960 0.950 0.5 0.6 図 8 0.7 0.8 MPS probability 0.9 1 符 号 化 効 率 （ 6 ビ ッ ト STT-coder） このため符号化効率で最適とされる範囲を超えて 一 般 的 な STT-coder と し て 6 ビ ッ ト シ ス テ ム の 設 計 そ れ ぞ れ LPS 幅 8， LPS 幅 4 を 選 択 す る よ う に す る こ 例 を 紹 介 し た が JPEG2000 や JBIG2 な ど の 画 像 符 号 化 とで平均的な符号化効率が向上することも確認されて に 適 用 す る 検 討 は ま だ 十 分 で は な い ． JBIG2 な ど の 2 いる． 値 情 報 源 に 適 用 す る う え で は MQ-coder と 同 様 に 12 ビ ットシステムが必要と思われる．その設計において 6 3.4. 6 ビ ッ ト STT-coder の 動 的 符 号 化 STT-coder の 静 的 符 号 化 設 計 の 考 え に つ い て は 上 記 で述べたが算術符号では動的符号化も重要であるので 2) 状態遷移型学習方法 についても新たな提案を行って いる．その目的として動的符号化特性を静的符号化特 ビットで示されたオフセットの種類数の最適化結果や オ フ セ ッ ト 値 の 組 み 合 わ せ（ 0，1/4，3/8，7/16 と い う 4 種 ）か ら 類 推 し て 12 ビ ッ ト の シ ス テ ム 設 計 を 行 う こ と も 可 能 で あ り そ の 場 合 に MQ-coder と の 性 能 比 較 を 行うことも興味深い． 性 と 同 様 に MPS の 出 現 確 率 に 対 し フ ラ ッ ト に す る こ ま た JPEG2000 に つ い て は こ れ ま で JBIG2 と 算 術 符 と を 掲 げ て お り ，新 た な 考 え と し て 遷 移 LPS 比 率 の 導 号 を 共 有 す る と い う 前 提 で MQ-coder を 採 用 し て お り 入が重要であることを導いている．状態遷移型学習で 算術符号として何ビットの精度が必要かはあまり明ら の 状 態 に 静 的 符 号 化 で の 効 率 が 99%に 近 い 8 情 報 源 モ か に さ れ て い な い ． 12 ビ ッ ト 版 に 拡 張 し た STT-coder デルを採用した場合の性能の考察から従来並みの動的 が で き た 場 合 ， そ の 共 有 を 図 る ほ か JPEG2000 の 算 術 符号化性能を達成するには 8 情報源（8 状態）では不 符 号 化 に 必 要 な ビ ッ ト 精 度 の STT-coder や JPEG2000 十 分 で あ り ，そ の 倍 の 16 状 態 が 必 要 で あ る こ と が 導 か に 専 用 の 変 形 STT-coder を 検 討 す る 価 値 も あ る と 思 わ れているがそれでも従来の状態遷移型学習よりは少な れる． い 状 態 数 で 済 む こ と ，16 状 態 と は い え 8 状 態 の そ れ ぞ 特に動的符号化については実際の情報源での検討 れの繰り返し（8 情報源）でよいことから静的符号化 が必要であり，それに応じてより実用的なシステムの と動的符号化のシステムの共通化も容易であることが 提案が望まれる． 導かれている． 5. 4. 今後の発展 むすび JPEG2000 の 仕 様 が 固 ま っ て ま も な く 15 年 を 迎 え る ． 算術符号化の簡易化の観点から筆者らが検討を進 その性能については今も色あせていないといえるが民 め て い る 状 態 遷 移 テ ー ブ ル 参 照 型 算 術 符 号 STT-coder 生用途の応用への普及は必ずしも十分でない．そのた の考え方を紹介した． め，算術符号化部分についてもより簡易化することが 必要と思われる．本報告では筆者らがそのような用途 も含めて簡易算術符号化方式として提案している STT-coder の 主 と し て 静 的 符 号 化 部 分 に つ い て 設 計 指 針を紹介した．その結果下限アドレスを記憶しないと いう大きな簡易化の採用によっても十分実用的な性能 が 実 現 で き る こ と が 示 さ れ た ． STT-coder の 考 察 で は 簡易化と同時に算術符号全般の課題についても取り上 げ て お り ， STT-coder の さ ら な る 検 討 が 今 後 の 算 術 符 号化全般への貢献となることを祈っている． 参考文献 1) G.G. Langdon, J. Rissanen: "Compression of Black-White Images with Arithmetic Coding", IEEE Trans., COM-29, 6, pp.858-860 (1981). 2) W.B. Pennebaker. J. L. Mitchell., G.G. Langdon, Jr., R.B. Arps: "An Overview of the Basic Principles of Q-Coder", IBM J. Res. & Develop., Vol.32, No.6 (1988). 3) ISO/IEC 11544 Information Technology -- Coded Representation of Picture and Audio Information -- Progressive Bi-level Image Compression (1993). 4) ISO/IEC 15444-1 Information Technology -- JPEG 2000 Image Coding System: Core Coding System (2000). 5) 上 野 幾 朗 , 小 野 文 孝 ：「 状 態 遷 移 テ ー ブ ル 参 照 型 算 術 符 号 STT-coder の 設 計 」画 像 電 子 学 会 誌 6) Vol.43, No.1, pp.62-70, 2014 年 1 月 上 野 幾 朗 , 小 野 文 孝 ：「 状 態 遷 移 テ ー ブ ル 参 照 型 算 術 符 号 STT-coder に お け る 確 率 推 定 方 式 と 動 的 符 号 化 の 設 計 」画 像 電 子 学 会 誌 No.1, pp.71-78, 2014 年 1 月 Vol.43,
© Copyright 2024 ExpyDoc
