JP3108479B2

JP3108479B2 - 符号化復号化方法およびその装置

Info

Publication number: JP3108479B2
Application number: JP24028891A
Authority: JP
Inventors: 泰之野水
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1991-08-28
Filing date: 1991-08-28
Publication date: 2000-11-13
Anticipated expiration: 2015-11-13
Also published as: JPH0564007A; US5297220A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、符号化対象の注目画素
に適用したテンプレートに含まれる複数画素の色の組み
合わせに対応した状態番号と、この状態番号に設定され
ている予測画素色とその注目画素の色との一致状態に基
づいて、算術符号化方式の優勢／劣勢シンボルを判定す
る符号化復号化方法およびその装置に関する。

【０００２】

【従来の技術】例えば、原稿をラスタスキャンして得た
画信号の情報量を圧縮するための符号化方式としては、
グループ３ファクシミリ装置の標準符号化方式として採
用されているＭＨ符号、オプション符号化方式として採
用されているＭＲ符号、および、グループ４ファクシミ
リ装置の標準符号化方式として採用されているＭＭＲ符
号などが広く用いられているが、このような標準的な符
号化方式以外でも、符号化効率の良好な符号化方式が提
案されている。

【０００３】その符号化方式の１つに、予測符号化方式
がある。この予測符号化方式では、まず、符号化対象と
なる注目画素に隣接する領域に配置されている複数の参
照画素の色情報に基づいて、注目画素の周囲の画素状態
を判別する（マルコフ情報源分離）。

【０００４】例えば、図１４に示すように、注目画素ｘ
に隣接した領域に配置されている８つの参照画素ａ，
ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈの色の分布状態を調べる。
この場合には、参照画素が８つなので、注目画素ｘに対
して２５６個の状態（マルコフ状態（＝コンテクス
ト））を規定することができる。

【０００５】ここで、注目画素ｘに対し、これらの参照
画素ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈの集合がかたちづ
くる形状、すなわち、注目画素ｘに対する参照画素ａ，
ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈの相対位置情報をあらわす
ひとまとまりのデータをテンプレートとよぶ。すなわ
ち、このテンプレートは、マルコフ情報源分離のために
用いられる。

【０００６】注目画素ｘの色は、例えば、全ての参照画
素ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈの色が白であれば注
目画素ｘが白である確率が高いなど、参照画素ａ，ｂ，
ｃ，ｄ，ｅ，ｆ，ｇ，ｈの色の分布状態、すなわち、マ
ルコフ状態と相関関係があるので、このマルコフ状態に
対して、それぞれある確率で注目画素ｘの色を予測する
ことができる。なお、参照画素ａ，ｂ，ｃ，ｄ，ｅ，
ｆ，ｇ，ｈの色分布状態に対する注目画素ｘの色の予測
確率（推定確率）は、例えば、統計的処理によりあらか
じめ定められる。

【０００７】このようにして、テンプレートを用いて予
測した注目画素ｘの色と、実際の注目画素ｘの色との一
致を調べ、各注目画素ｘについて予測色との一致状態を
あらわす１ビットデータを、マルコフ状態をあらわす状
態番号とともに検出し、それぞれの状態番号について注
目画素順に配列したビット列をランレングス符号化する
ことで、元の画像データを符号化圧縮することができ
る。

【０００８】ところで、この予測符号化方式では、全て
の注目画素ｘについて状態番号を検出完了した状態でラ
ンレングス符号化すると、最も効率よく符号化できる
が、そのためには各状態番号について、予測色との一致
状態をあらわすビットデータ列を注目画素順に保存して
おく必要があり、そのためのデータバッファが必要にな
るために符号化復号化装置の装置規模が大きくなるとと
もに、符号化処理のリアルタイム性が悪いという問題が
ある。

【０００９】そこで、このような問題を解決するため
に、予測符号化方式と算術符号化方式を組み合わせた符
号化方式が提案されている。

【００１０】ここで、算術符号とは、０以上１未満
（［０，１））の数直線上の対応区間（２進小数で
［０．０…０，０．１…１］）を各シンボルの生起確率
に応じて不等長に分割していき、対象シンボル系列を対
応する部分区間に割り当て、再帰的に分割を繰り返して
いくことにより得られた区間内に含まれる点の座標を、
少なくとも他の区間と区別できる２進小数で表現してそ
のまま符号とするものであり、例えば、ＪＰＥＧ（Ｊｏ
ｉｎｔＰｈｏｔｏｇｒａｐｈｉｃＥｘｐｅｒｔｓＧ
ｒｏｕｐ）において国際標化作業が進められているカラ
ー静止画（自然画）符号化方式のエントロピー符号化方
式に採用されたＱＭ−ｃｏｄｅｒの基礎となるものであ
る。

【００１１】例えば、符号化シンボル系列０１００を対
象とした２値算術符号化では、図１５に示すような符号
化が行われる。

【００１２】同図において、例えば、第１シンボルの符
号化時には、全区間が０と１のシンボルの生起確率の比
にしたがってＡ（０）とＡ（１）に分割され、０の発生
により区間Ａ（０）が選択される。次に、第２シンボル
の符号化のさいには、その状態における両シンボルの生
起確率比によってＡ（０）がさらに分割され、発生シン
ボル系列に対応する区間としてＡ（０１）が選択され
る。このような分割と選択の処理のくり返しにより符号
化が進められる。

【００１３】この算術符号はいわゆる非ブロック符号で
あり、とくに、予測符号化方式のように状態番号（コン
テクスト）に応じてシンボルの出現確率が変化する場合
の符号化に適しており、また、ＭＨ符号のようなランレ
ングス符号に比べて、符号器の規模や必要メモリ量など
のハードウェアが小さくて済む、より高い効率が期待で
きる、および、適応符号化が容易であるという利点があ
る。

【００１４】上述したＱＭ−ｃｏｄｅｒは、この算術符
号化をより少ないハードウェア資源を用いて実現し、か
つ、より高速な処理が可能なようにしたものである。

【００１５】さて、算術符号化方式では、２値シンボル
のうち出現確率の高いシンボル、すなわち、優勢シンボ
ルが連続すると、そのシンボルに対応した数直線上の区
間が広くなるため、符号語を表現するために必要なデー
タ量が少なくなり、符号化効率が高くなる。

【００１６】一方、２値シンボルのうち出現確率の低い
シンボル、すなわち、劣勢シンボルが連続すると、その
シンボルに対応した数直線上の区間が狭くなるため、符
号語を表現するために必要なデータ量が多くなり、符号
化効率が悪くなる。

【００１７】このようにして、算術符号化方式における
符号化効率を向上するためには、優勢シンボルが連続す
るように前処理することが必要であり、この場合には、
前処理である予測符号化処理で、注目画素ｘの色の予測
確率をより大きい値にすることが必要となる。

【００１８】さて、注目画素ｘの色の予測確率をより大
きい値にするためには、符号化する画像の特徴をよりよ
く判別できる形状のテンプレートを用いればよい。例え
ば、図１４に示したテンプレートは、活字原稿などの非
中間調画像を処理するときに適しており、また、写真原
稿などの中間調画像を処理するときには、図１６（ａ）
に示したようなテンプレートを用いるとよい。また、非
中間調画像および中間調画像が混在するような原稿の画
像を処理するときには、図１６（ｂ）に示したように、
上述した２つのテンプレートの特徴をあわせもつような
テンプレートが用いられる。

【００１９】

【発明が解決しようとする課題】しかしながら、このよ
うな従来装置には、次のような不都合を生じていた。

【００２０】すなわち、例えば、活字原稿などの非中間
調画像でも、活字などの印字あるいは印刷の具合などに
より画像にかすれが出て、部分的に中間調的な画像があ
らわれたりすることがあり、その中間調的な画像のあら
われる位置、および、中間調の程度などはその画像に特
有なものであるために、局所的な画像の特徴を効率よく
処理できるテンプレートを事前に用意することが困難で
あり、符号化効率を向上することが困難であるという不
都合を生じていた。

【００２１】本発明は、かかる実情に鑑みてなされたも
のであり、符号化効率を向上できる符号化復号化方法お
よびその装置を提供することを目的としている。

【００２２】

【課題を解決するための手段】本発明は、符号化対象の
注目画素に適用したテンプレートに含まれる複数画素の
色の組み合わせに対応した状態番号と、この状態番号に
設定されている予測画素色とその注目画素の色との一致
状態に基づいて、算術符号化方式の優勢／劣勢シンボル
を判定する符号化復号化方法において、符号化時、所定
数の画素の符号化を終了するたびに、注目画素に隣接す
る所定の参照範囲内の画素についてそれぞれ注目画素の
色との一致数を計数し、その一致数の大きいものから参
照画素を所定数検出し、その検出した複数の参照画素を
含む形状のテンプレートを新たに形成してそれ以降はこ
の新たに形成したテンプレートを用いる一方、復号化
時、所定数の画素の復号化を終了するたびに、復号化を
終了した注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数し、その
一致数の大きいものから参照画素を所定数検出し、その
検出した複数の参照画素を含む形状のテンプレートを新
たに形成してそれ以降はこの新たに形成したテンプレー
トを用いるようにしたものである。

【００２３】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化復号
化方法において、符号化時、初期状態では所定のテンプ
レートを用いて符号化処理するとともに、所定数の画素
の符号化を終了するたびに、注目画素に隣接する所定の
参照範囲内の画素についてそれぞれ注目画素の色との一
致数を計数し、その一致数の大きいものから参照画素を
所定数検出し、その検出した複数の参照画素を含む形状
のテンプレートを新たに形成してそれ以降はこの新たに
形成したテンプレートを用いる一方、復号化時、初期状
態では所定のテンプレートを用いて符号化処理するとと
もに、所定数の画素の復号化を終了するたびに、復号化
を終了した注目画素に隣接する所定の参照範囲内の画素
についてそれぞれ注目画素の色との一致数を計数し、そ
の一致数の大きいものから参照画素を所定数検出し、そ
の検出した複数の参照画素を含む形状のテンプレートを
新たに形成してそれ以降はこの新たに形成したテンプレ
ートを用いるようにしたものである。

【００２４】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数してその一致数の大き
いものから参照画素を所定数検出する参照画素検出手段
と、その検出した複数の参照画素を含む形状のテンプレ
ートを形成するテンプレート作成手段と、このテンプレ
ート形成手段により形成したテンプレートを用いて注目
画素を符号化する符号化手段を備えたものである。

【００２５】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数してその一致数の大き
いものから参照画素を所定数検出する参照画素検出手段
と、その検出した複数の参照画素を含む形状のテンプレ
ートを形成するテンプレート作成手段と、初期状態では
所定のテンプレートを用いるとともに上記テンプレート
形成手段により新たなテンプレートが形成されるとその
形成されたテンプレートを用いて注目画素を符号化する
符号化手段を備えたものである。

【００２６】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる既に復号化終了した複数画素の色
の組み合わせに対応した状態番号と、この状態番号に設
定されている予測画素色とその注目画素の色との一致状
態に基づいて、算術符号化方式の優勢／劣勢シンボルを
判定する復号化装置において、所定数の画素の復号化を
終了するたびに復号化を終了した注目画素に隣接する所
定の参照範囲内の画素についてそれぞれ注目画素の色と
の一致数を計数しその一致数の大きいものから参照画素
を所定数検出する参照画素検出手段と、その検出した複
数の参照画素を含む形状のテンプレートを形成するテン
プレート作成手段と、このテンプレート作成手段により
形成されたテンプレートを用いて注目画素を復号化する
復号化手段を備えたものである。

【００２７】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる既に復号化終了した複数画素の色
の組み合わせに対応した状態番号と、この状態番号に設
定されている予測画素色とその注目画素の色との一致状
態に基づいて、算術符号化方式の優勢／劣勢シンボルを
判定する復号化装置において、所定数の画素の復号化を
終了するたびに復号化を終了した注目画素に隣接する所
定の参照範囲内の画素についてそれぞれ注目画素の色と
の一致数を計数しその一致数の大きいものから参照画素
を所定数検出する参照画素検出手段と、その検出した複
数の参照画素を含む形状のテンプレートを形成するテン
プレート作成手段と、初期状態では所定のテンプレート
を用いるとともに上記テンプレート形成手段により新た
なテンプレートが形成されるとその形成されたテンプレ
ートを用いて注目画素を復号化する復号化手段を備えた
ものである。

【００２８】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化復号
化方法において、テンプレートを注目画素に対する相対
位置が固定されている固定参照画素群と注目画素に対す
る相対位置が固定されていない浮動参照画素群から構成
する一方、符号化時、所定数の画素の符号化を終了する
たびに、注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数し、その
一致数の大きいものから浮動参照画素数に一致する参照
画素を検出し、その検出した複数の参照画素と上記固定
参照画素群からなるテンプレートを新たに形成してそれ
以降はこの新たに形成したテンプレートを用いるととも
に、復号化時、所定数の画素の復号化を終了するたび
に、復号化を終了した注目画素に隣接する所定の参照範
囲内の画素についてそれぞれ注目画素の色との一致数を
計数し、その一致数の大きいものから浮動参照画素数に
一致する参照画素を検出し、その検出した複数の参照画
素と上記固定参照画素群からなるテンプレートを新たに
形成してそれ以降はこの新たに形成したテンプレートを
用いるようにしたものである。

【００２９】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化復号
化方法において、テンプレートを注目画素に対する相対
位置が固定されている固定参照画素群と注目画素に対す
る相対位置が固定されていない浮動参照画素群から構成
する一方、符号化時、初期状態では所定のテンプレート
を用いて符号化処理するとともに、所定数の画素の符号
化を終了するたびに、注目画素に隣接する所定の参照範
囲内の画素についてそれぞれ注目画素の色との一致数を
計数し、その一致数の大きいものから浮動参照画素数に
一致する参照画素を検出し、その検出した複数の参照画
素と上記固定参照画素群からなるテンプレートを新たに
形成してそれ以降はこの新たに形成したテンプレートを
用いるとともに、復号化時、初期状態では所定のテンプ
レートを用いて符号化処理するとともに、所定数の画素
の復号化を終了するたびに、復号化を終了した注目画素
に隣接する所定の参照範囲内の画素についてそれぞれ注
目画素の色との一致数を計数し、その一致数の大きいも
のから浮動参照画素数に一致する参照画素を検出し、そ
の検出した複数の参照画素と上記固定参照画素群からな
るテンプレートを新たに形成してそれ以降はこの新たに
形成したテンプレートを用いるようにしたものである。

【００３０】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数しその一致数の大きい
ものから参照画素を所定数検出する参照画素検出手段
と、この参照画素検出手段が検出した複数の参照画素を
注目画素に対する相対位置が固定されていない浮動参照
画素群に設定するとともにこの浮動参照画素群および注
目画素に対する相対位置が固定されている固定参照画素
群からテンプレートを新たに形成するテンプレート作成
手段と、このテンプレート作成手段が形成したテンプレ
ートを用いて注目画素を符号化する符号化手段を備えた
ものである。

【００３１】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数しその一致数の大きい
ものから参照画素を所定数検出する参照画素検出手段
と、この参照画素検出手段が検出した複数の参照画素を
注目画素に対する相対位置が固定されていない浮動参照
画素群に設定するとともにこの浮動参照画素群および注
目画素に対する相対位置が固定されている固定参照画素
群からテンプレートを新たに形成するテンプレート作成
手段と、初期状態では所定のテンプレートを用いるとと
もに上記テンプレート形成手段により新たなテンプレー
トが形成されるとその形成されたテンプレートを用いて
注目画素を符号化する符号化手段を備えたものである。

【００３２】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる既に復号化終了した複数画素の色
の組み合わせに対応した状態番号と、この状態番号に設
定されている予測画素色とその注目画素の色との一致状
態に基づいて、算術符号化方式の優勢／劣勢シンボルを
判定する復号化装置において、所定数の画素の復号化を
終了するたびに注目画素に隣接する所定の参照範囲内の
画素についてそれぞれ注目画素の色との一致数を計数し
その一致数の大きいものから参照画素を所定数検出する
参照画素検出手段と、この参照画素検出手段が検出した
複数の参照画素を注目画素に対する相対位置が固定され
ていない浮動参照画素群に設定するとともにこの浮動参
照画素群および注目画素に対する相対位置が固定されて
いる固定参照画素群からテンプレートを新たに形成する
テンプレート作成手段と、このテンプレート作成手段が
形成したテンプレートを用いて注目画素を復号化する復
号化手段を備えたものである。

【００３３】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる既に復号化終了した複数画素の色
の組み合わせに対応した状態番号と、この状態番号に設
定されている予測画素色とその注目画素の色との一致状
態に基づいて、算術符号化方式の優勢／劣勢シンボルを
判定する復号化装置において、所定数の画素の復号化を
終了するたびに注目画素に隣接する所定の参照範囲内の
画素についてそれぞれ注目画素の色との一致数を計数し
その一致数の大きいものから参照画素を所定数検出する
参照画素検出手段と、この参照画素検出手段が検出した
複数の参照画素を注目画素に対する相対位置が固定され
ていない浮動参照画素群に設定するとともにこの浮動参
照画素群および注目画素に対する相対位置が固定されて
いる固定参照画素群からテンプレートを新たに形成する
テンプレート作成手段と、初期状態では所定のテンプレ
ートを用いるとともに上記テンプレート形成手段により
新たなテンプレートが形成されるとその形成されたテン
プレートを用いて注目画素を復号化する復号化手段を備
えたものである。

【００３４】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化復号
化方法において、テンプレートを注目画素に対する相対
位置が固定されている固定参照画素群と注目画素に対す
る相対位置が固定されていない浮動参照画素群から構成
する一方、符号化時、所定数の画素の符号化を終了する
たびに、注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数し、その
一致数に基づいて新たな浮動参照画素に設定する参照画
素を検出し、その検出した参照画素を上記浮動参照画素
群の任意の画素に置換するとともにその置換後に得られ
た浮動参照画素群と上記固定参照画素群からなるテンプ
レートを新たに形成してそれ以降はこの新たに形成した
テンプレートを用いるとともに、復号化時、所定数の画
素の復号化を終了するたびに、復号化を終了した注目画
素に隣接する所定の参照範囲内の画素についてそれぞれ
注目画素の色との一致数を計数し、その一致数に基づい
て新たな浮動参照画素に設定する参照画素を検出し、そ
の検出した参照画素を上記浮動参照画素群の任意の画素
に置換するとともにその置換後に得られた浮動参照画素
群と上記固定参照画素群からなるテンプレートを新たに
形成してそれ以降はこの新たに形成したテンプレートを
用いるようにしたものである。

【００３５】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化復号
化方法において、テンプレートを注目画素に対する相対
位置が固定されている固定参照画素群と注目画素に対す
る相対位置が固定されていない浮動参照画素群から構成
する一方、符号化時、初期状態では所定のテンプレート
を用いるとともに、所定数の画素の符号化を終了するた
びに、注目画素に隣接する所定の参照範囲内の画素につ
いてそれぞれ注目画素の色との一致数を計数し、その一
致数に基づいて新たな浮動参照画素に設定する参照画素
を検出し、その検出した参照画素を上記浮動参照画素群
の任意の画素に置換するとともにその置換後に得られた
浮動参照画素群と上記固定参照画素群からなるテンプレ
ートを新たに形成してそれ以降はこの新たに形成したテ
ンプレートを用い、復号化時、初期状態では所定のテン
プレートを用いるとともに、所定数の画素の復号化を終
了するたびに、復号化を終了した注目画素に隣接する所
定の参照範囲内の画素についてそれぞれ注目画素の色と
の一致数を計数し、その一致数に基づいて新たな浮動参
照画素に設定する参照画素を検出し、その検出した参照
画素を上記浮動参照画素群の任意の画素に置換するとと
もにその置換後に得られた浮動参照画素群と上記固定参
照画素群からなるテンプレートを新たに形成してそれ以
降はこの新たに形成したテンプレートを用いるようにし
たものである。

【００３６】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数しその一致数の大きい
ものから参照画素を所定数検出する参照画素検出手段
と、この参照画素検出手段が検出した１つ以上の参照画
素により注目画素に対する相対位置が固定されていない
浮動参照画素群のいずれかの位置の画素を更新するとと
もにこの更新後の浮動参照画素群および注目画素に対す
る相対位置が固定されている固定参照画素群からテンプ
レートを新たに形成するテンプレート作成手段と、この
テンプレート作成手段が形成したテンプレートを用いて
注目画素を符号化する符号化手段を備えたものである。

【００３７】また、符号化対象の注目画素に適用したテ
ンプレートに含まれる複数画素の色の組み合わせに対応
した状態番号と、この状態番号に設定されている予測画
素色とその注目画素の色との一致状態に基づいて、算術
符号化方式の優勢／劣勢シンボルを判定する符号化装置
において、所定数の画素の符号化を終了するたびに注目
画素に隣接する所定の参照範囲内の画素についてそれぞ
れ注目画素の色との一致数を計数しその一致数の大きい
ものから参照画素を所定数検出する参照画素検出手段
と、この参照画素検出手段が検出した１つ以上の参照画
素により注目画素に対する相対位置が固定されていない
浮動参照画素群のいずれかの位置の画素を更新するとと
もにこの更新後の浮動参照画素群および注目画素に対す
る相対位置が固定されている固定参照画素群からテンプ
レートを新たに形成するテンプレート作成手段と、初期
状態では所定のテンプレートを用いるとともに上記テン
プレート形成手段により新たなテンプレートが形成され
るとその形成されたテンプレートを用いて注目画素を符
号化する符号化手段を備えたものである。

【００３８】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる復号化終了した複数画素の色の組
み合わせに対応した状態番号と、この状態番号に設定さ
れている予測画素色とその注目画素の色との一致状態に
基づいて、算術符号化方式の優勢／劣勢シンボルを判定
する復号化装置において、所定数の画素の復号化を終了
するたびに注目画素に隣接する所定の参照範囲内の画素
についてそれぞれ注目画素の色との一致数を計数しその
一致数の大きいものから参照画素を所定数検出する参照
画素検出手段と、この参照画素検出手段が検出した１つ
以上の参照画素により注目画素に対する相対位置が固定
されていない浮動参照画素群のいずれかの位置の画素を
更新するとともにこの更新後の浮動参照画素群および注
目画素に対する相対位置が固定されている固定参照画素
群からテンプレートを新たに形成するテンプレート作成
手段と、このテンプレート作成手段が形成したテンプレ
ートを用いて注目画素を復号化する復号化手段を備えた
ものである。

【００３９】また、復号化対象の注目画素に適用したテ
ンプレートに含まれる復号化終了した複数画素の色の組
み合わせに対応した状態番号と、この状態番号に設定さ
れている予測画素色とその注目画素の色との一致状態に
基づいて、算術符号化方式の優勢／劣勢シンボルを判定
する復号化装置において、所定数の画素の復号化を終了
するたびに注目画素に隣接する所定の参照範囲内の画素
についてそれぞれ注目画素の色との一致数を計数しその
一致数の大きいものから参照画素を所定数検出する参照
画素検出手段と、この参照画素検出手段が検出した１つ
以上の参照画素により注目画素に対する相対位置が固定
されていない浮動参照画素群のいずれかの位置の画素を
更新するとともにこの更新後の浮動参照画素群および注
目画素に対する相対位置が固定されている固定参照画素
群からテンプレートを新たに形成するテンプレート作成
手段と、初期状態では所定のテンプレートを用いるとと
もに上記テンプレート形成手段により新たなテンプレー
トが形成されるとその形成されたテンプレートを用いて
注目画素を復号化する復号化手段を備えたものである。

【００４０】

【作用】したがって、符号化対象となる画像の局所的な
特徴に最適なテンプレートを使用することができるの
で、符号化効率が向上する。また、テンプレートを固定
参照画素群と浮動参照画素群に分割して、浮動参照画素
群のみ再構成するようにしているので、テンプレートを
形成するための処理を減少でき、装置規模を縮小できる
とともに、装置コストを低減することができる。

【００４１】

【実施例】以下、添付図面を参照しながら、本発明の実
施例を詳細に説明する。

【００４２】まず、本発明で算術符号化方式として使用
するＱＭ−ｃｏｄｅｒの符号化／復号化アルゴリズムに
ついて説明する。

【００４３】符号化の初めでは、０以上１未満の数直線
を考える。この数直線の間隔をＡ、そのときのマルコフ
状態（初期状態では、状態０）に対応した劣勢シンボル
の発生確率をＱｅとすると、分割後の領域は、次式
（Ｉ）であらわされる。

【００４４】ａ＝Ａ×（１−Ｑｅ）（ａ：優勢シンボルの領域の大
きさ）

【００４５】ｂ＝Ａ×Ｑｅ（ｂ：劣勢シンボルの領域の大きさ）…（Ｉ）

【００４６】ここで、最初のシンボルが０（優勢シンボ
ル）であった場合には、ａを新しいＡとして、１（劣勢
シンボル）であった場合には、ｂを新しいＡとしてさら
に分割を行なう。

【００４７】しかしながら、符号化時に乗算操作が行わ
れることは装置規模の面でも演算速度の面でも不利であ
る。また、無限長のシンボル系列を符号化するさい、小
さくなった領域を演算するためには無限長の演算用レジ
スタが必要となる。

【００４８】そこで、ＱＭ−ｃｏｄｅｒでは、分割後の
新しいＡが常に０．７５以上１．５未満の大きさになる
ように操作して、Ａを１に近似できるようにし、上述し
た式（Ｉ）を次式（ＩＩ）で近似する。

【００４９】ａ＝Ａ−Ｑｅ

【００５０】ｂ＝Ｑｅ …（ＩＩ）

【００５１】この近似に伴い、Ａの値が０．７５未満に
なったときには、Ａが０．７５以上１．５未満の値にな
るまでＡを左にビットシフトして拡大する再正規化処理
を行なう。この再正規化処理により、乗算を必要とする
演算を減算で実現できるとともに、有限長レジスタを用
いて演算を行なうことができる。また、再正規化処理を
行なうと、そのときのマルコフ状態と、処理対象のシン
ボルの優勢／劣勢の区別に応じて、次のマルコフ状態に
推移する。

【００５２】優勢シンボルの符号化処理は、例えば、図
１（ａ）に示すように行われ、また、劣勢シンボルの符
号化処理は、例えば、同図（ｂ）に示すように行われ
る。ここで、Ｃは符号をあらわし、その初期値は０であ
る。

【００５３】すなわち、優勢シンボルを符号化するとき
には、符号Ｃは変更せず（処理１０１）、領域Ａの値を
そのときのマルコフ状態に対応した確率Ｑｅだけ小さい
値に更新する（処理１０２）。このとき、領域Ａの値が
０．７５よりも小さいかどうかを調べて（判断１０
３）、判断１０３の結果がＹＥＳになるときには、領域
Ａの値および符号Ｃを再正規化処理するとともに状態推
移し（処理１０４）、１つの優勢シンボルの処理を終了
する。また、判断１０３の結果がＮＯになるときには、
処理１０４を行なわず、そのときのマルコフ状態を維持
する。

【００５４】また、劣勢シンボルを符号化するときに
は、符号Ｃの値を（Ａ−Ｑｅ）だけ増やして（処理２０
１）、領域Ａの値を確率Ｑｅの値に更新し（処理２０
２）、領域Ａと符号Ｃを再正規化処理するとともに状態
推移する（処理２０３）。

【００５５】このときに生成した符号Ｃは、領域のもっ
とも下の部分を示す２進小数値に一致する。また、再正
規化処理では、符号Ｃを領域Ａと同じ桁数左シフトして
拡大し、１を超えた部分の符号Ｃの値が、符号データと
して出力される。

【００５６】また、復号化処理の一例を図１（ｃ）に示
す。

【００５７】まず、符号Ｃが値（Ａ−Ｑｅ）よりも小さ
いかどうかを調べて（判断３０１）、判断３０１の結果
がＹＥＳになるときには、復号化対象となっている注目
画素を優勢シンボルとして判断し（処理３０２）、領域
Ａの値をそのときのマルコフ状態に対応した確率Ｑｅだ
け減じた値に更新する（処理３０３）。そして、更新し
た領域Ａの値が０．７５よりも小さくなったかどうかを
調べて（判断３０４）、判断３０４の結果がＹＥＳにな
るときには、領域Ａと符号Ｃを再正規化するとともにマ
ルコフ状態を推移して（処理３０５）、この１つのシン
ボルの復号化処理を終了する。また、判断３０４の結果
がＮＯになるときには、処理３０５を行なわず、そのと
きのマルコフ状態を維持する。

【００５８】また、判断３０１の結果がＮＯになるとき
には、注目画素を劣勢シンボルとして判断し（処理３０
６）、符号Ｃの値を（Ａ−Ｑｅ）だけ小さい値に更新す
るとともに（処理３０７）、領域Ａを確率Ｑｅの値に更
新し（処理３０８）、領域Ａと符号Ｃを再正規化すると
ともにマルコフ状態を推移して（処理３０９）、この１
つのシンボルの復号化処理を終了する。

【００５９】このようにして、ＱＭ−ｃｏｄｅｒの符号
化時では、優勢シンボルがあらわれたときには符号Ｃが
変化しないとともに、再正規化処理が行われる可能性が
少なく、また、劣勢シンボルがあらわれると即再正規化
処理が行われるとともに符号データが形成される。

【００６０】したがって、劣勢シンボルの出現頻度が小
さくなるように前処理である予測符号化処理を行なう
と、符号化効率が向上するとともに、処理速度も向上す
る。

【００６１】そこで、本実施例では、次のようにして、
予測符号化処理で使用するテンプレートを形成する。

【００６２】まず、図２に示すように、注目画素Ｘより
も過去の時点で注目画素Ｘとなった画素のうち、注目画
素Ｘと同じ主走査ラインを含む３ラインで、注目画素Ｘ
の主走査位置を含み走査開始方向に４画素、かつ、走査
終了方向に３画素の領域に位置する参照画素Ｒ１〜Ｒ１
７の領域を、テンプレートを形成するための参照画素領
域として用いる。

【００６３】そして、１画素の符号化処理を終了する
と、おのおのの参照画素Ｒ１〜Ｒ１７について、そのと
きの注目画素Ｘと同じ色の参照画素Ｒ１〜Ｒ１７を検出
し、色が一致した参照画素Ｒ１〜Ｒ１７について、一致
数を記憶する一致数カウンタの値を１つ増やす。

【００６４】この処理を所定数の画素、例えば、連続す
る３ライン分の画素について行なうと、参照画素Ｒ１〜
Ｒ１７のうち、その時点で一致数カウンタの値が大きい
ものを大きい順に８つ選択し、その大きい順に、参照画
素Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈに割り当て、その参
照画素Ａ〜Ｈと、参照画素Ｒ１〜Ｒ１７の関係を、例え
ば、図３に示すようなテンプレートテーブルに記憶す
る。この場合のテンプレートは、図４に示すようなもの
である。

【００６５】すなわち、この場合、参照画素Ｒ１０の一
致数カウンタの値が最大であり、参照画素Ｒ１１，Ｒ１
７，Ｒ３，Ｒ９，Ｒ１２，Ｒ４，Ｒ１６の順に一致数カ
ウンタの値が小さくなっている。

【００６６】このようにして形成したテンプレートと、
このテンプレートを参照して判断する注目画素Ｘのマル
コフ状態の状態番号との関係は、あらかじめ、例えば、
図５に示すマルコフ状態参照テーブルのように設定され
ている。

【００６７】以上の処理を、連続する３ライン分の画素
について繰り返し行なうことで、画像の局所的な特徴を
捉えたテンプレートを形成することができる。なお、予
測符号化処理の初期状態では、テンプレートがまだ形成
されていないため、テンプレートの初期値として、図４
に示したテンプレートを用いる。すなわち、テンプレー
トテーブルの初期値は、図３に示したものとなる。

【００６８】また、復号化処理するときも、上述した方
法と同じ方法を用いて、３ライン分の画素の復号化を終
了するたびに、テンプレートを形成する。また、復号化
処理を符号化処理と同じ条件で行なえるように、初期状
態では、図４に示したテンプレートを用いる。

【００６９】図６は、本発明の一実施例にかかる符号化
復号化装置を示している。

【００７０】同図において、図示しない画情報発生源か
ら入力される画像データＰＩＸａは、テンプレート作成
部１、状態番号判定部２、および、符号化確率評価部３
に加えられている。また、復号化確率評価部４から出力
される復号データＰＩＸｂは、テンプレート作成部１お
よび状態番号判定部２に加えられている。

【００７１】テンプレート作成部１は、符号化時には画
像データＰＩＸａに基づいて、また、復号化時には復号
データＰＩＸｂに基づいて、上述したテンプレートデー
タの作成処理を行なうものであり、その作成結果で得ら
れたテンプレートテーブルデータは、テンプレート記憶
部５に記憶される。

【００７２】状態番号判定部２は、テンプレート記憶部
５に記憶されているテンプレートテーブルデータに対応
したテンプレートを、符号化時には画像データＰＩＸａ
に、また、復号化時には復号データＰＩＸｂにそれぞれ
適用するとともに、上述したマルコフ状態参照テーブル
を参照して、注目画素Ｘに対するマルコフ状態をあらわ
す状態番号を判別するものであり、その判別結果は、符
号化時には状態番号データＳＣとして符号化確率評価部
３に加えられ、また、復号化時には状態番号データＳＤ
として復号化確率評価部４に加えられる。

【００７３】確率推定テーブル６は、ＱＭ−ｃｏｄｅｒ
に規定されている１１３個の状態についての確率推定テ
ーブルデータを記憶するものであり、その記憶データ
は、符号化確率評価部３および復号化確率評価部４にそ
れぞれ加えられている。なお、確率推定テーブルデータ
は、例えば、「カラー静止画符号化国際標準方式（ＪＰ
ＥＧ）の概説（その２：算術符号）」小野文孝（画像電
子学会誌第２０巻第２号（１９９１）ｐ．１１８）
を参照。

【００７４】符号化確率評価部３は、確率推定テーブル
６の内容を参照し、状態番号判定部２から入力した状態
番号データＳＣと画像データＰＩＸａ、および、算術符
号化部７から再正規化発生時に加えられる再正規化信号
ＲＣに基づき、それぞれの状態番号について、確率推定
テーブル６の状態を判定するとともに、その時点で優勢
シンボルとして判定している色の情報を判定するもので
あり、その判定結果を状態保存テーブル８に記憶すると
ともに、確率推定テーブル６から取り出した推定確率デ
ータＱｅｃと、優勢／劣勢シンボルの区別をあらわすシ
ンボル種別データＳｂｃを算出符号化部７に出力する。

【００７５】状態保存テーブル８は、図７に示すよう
に、おのおのの状態番号について、確率推定テーブル６
の状態をあらわす状態データと、優勢シンボルの色をあ
らわす優勢シンボルデータを記憶するものである。

【００７６】算術符号化部７は、符号化確率評価部３か
ら入力した推定確率データＱｅｃおよびシンボル種別デ
ータＳｂｃに基づき、上述した符号化処理を行なうとと
もに、再正規化処理が発生したときには符号化確率評価
部３に再正規化信号ＲＣを出力するものであり、その符
号化処理により形成した符号データＣＤａを次段装置に
出力する。

【００７７】復号化確率評価部４は、確率推定テーブル
６の内容を参照し、状態番号判定部２から入力した状態
番号データＳＤ、算術復号化部９より入力したシンボル
種別データＳｂｄ、および、算術復号化部９から再正規
化発生時に加えられる再正規化信号ＲＤに基づき、それ
ぞれの状態番号について、確率推定テーブル６の状態を
判定するとともに、その時点で優勢シンボルとして判定
している色の情報を判定するものであり、その判定結果
を状態保存テーブル１０に記憶し、確率推定テーブル６
から取り出した推定確率データＱｅｄを算術復号化部９
に出力し、算術復号化部９が復号化した画素の色をあら
わす復号データＰＩＸｂを次段装置に出力する。また、
状態保存テーブル１０には、状態保存テーブル８と同様
のデータが記憶される。

【００７８】図８は、新たな画素の画像データＰＩＸａ
または復号データＰＩＸｂが入力されたときにテンプレ
ート作成部１が行なう処理例を示している。

【００７９】まず、おのおのの参照画素Ｒ１〜Ｒ１７に
ついて、注目画素Ｘの色と一致するものを判定し、その
一致した参照画素Ｒ１〜Ｒ１７に対応した一致数カウン
タ（図示略）をインクリメントし（処理４０１）、処理
回数を記憶するためのカウンタｉの値をインクリメント
する（処理４０２）。

【００８０】そして、カウンタｉの値が、テンプレート
作成のために必要な画素数ＡＡ以上の値になったかどう
かを調べ（判断４０３）、判断４０３の結果がＹＥＳに
なるときには、一致数カウンタの値が最大の参照画素Ｒ
１〜Ｒ１７を選択し（処理４０４）、そのときのテンプ
レートテーブルの空き領域のうち、一致数カウンタの最
大値に対応した領域にその参照画素Ｒ１〜Ｒ１７の識別
情報を記憶して１画素分のテンプレートを形成する（処
理４０５）。このとき、選択した参照画素Ｒ１〜Ｒ１７
の一致数カウンタの値をクリアする。

【００８１】ここで、テンプレートテーブルの全ての領
域にデータが記憶されているかどうかを調べて（判断４
０６）、判断４０６の結果がＮＯになるときには、処理
４０４に戻り、次の参照画素Ｒ１〜Ｒ１７の選択処理を
行なう。

【００８２】判断４０６の結果がＹＥＳになるときに
は、そのときに形成したテンプレートテーブルデータを
テンプレート記憶部５に保存して（処理４０７）、カウ
ンタｉを０にクリアし（処理４０８）、この処理を終了
する。

【００８３】また、判断４０３の結果がＮＯになるとき
には、即この処理を終了する。

【００８４】以上の構成で、この符号化復号化装置が符
号化動作を行なうとき、まず、初期状態では、テンプレ
ート作成部１は、テンプレート記憶部５に、テンプレー
トテーブルデータの初期値を記憶する。また、状態番号
判定部２は、テンプレートによる状態判定のために必要
な参照データを、全白の状態に初期設定する。また、符
号化確率評価部３は、状態保存テーブル８の全ての状態
番号について、状態データを状態０に初期設定するとと
もに、優勢シンボルデータを０（白）に設定する。

【００８５】この状態で、画像データＰＩＸａが加えら
れると、テンプレート作成部１は、上述した処理を実行
し、１画素分の注目画素Ｘについて、それぞれの参照画
素Ｒ１〜Ｒ１７の一致数カウンタのインクリメント処理
を行なう。

【００８６】また、状態番号判定部２は、そのときに記
憶している参照データのうち、テンプレート記憶部５に
記憶されているテンプレートテーブルデータであらわさ
れる参照画素Ａ〜Ｈに相当する画素のデータを抽出し
て、参照画素Ａ〜Ｈのデータパターンを判定し、そのデ
ータパターンに対応した状態番号を、マルコフ状態参照
テーブルを参照して判断し、その判断結果を状態番号デ
ータＳＣとして符号化確率評価部３に出力する。また、
状態番号判定部２は、そのときに入力した画像データＰ
ＩＸａにより、記憶している参照データを１ビット更新
する。

【００８７】これにより、符号化確率評価部３は、状態
番号判定部２から加えられた状態番号データＳＣに対応
する状態番号について状態保存テーブル８の記憶内容を
取り出し、その取り出した記憶内容に含まれている状態
データによって確率推定テーブル６を参照し、対応した
推定確率を読み込み、その推定確率の値を推定確率デー
タＱｅｃとして算術符号化部７に出力する。それととも
に、符号化確率評価部３は、そのときに入力した画像デ
ータＰＩＸａの色が優勢シンボルであるか劣勢シンボル
であるかを、状態保存テーブル８から取り出した優勢シ
ンボルデータに基づいて判定し、その判定結果をシンボ
ル種別データＳｂｃとして算術符号化部７に出力する。

【００８８】算術符号化部７は、符号化確率評価部３か
ら加えられる推定確率データＱｅｃおよびシンボル種別
データＳｂｃに基づいて、上述した符号化処理を実行
し、その結果、再正規化処理が発生して符号Ｃが１以上
になると、その１以上の部分を符号データＣＤａとして
出力する。

【００８９】また、算術符号化部７は、再正規化処理が
発生すると、再正規化信号ＲＣを符号化確率評価部３に
出力する。これにより、符号化確率評価部３は、シンボ
ル種別および状態データに基づいて確率推定テーブル６
を参照し、そのときの状態番号について、状態データを
更新し、その更新結果を状態保存テーブル８に保存す
る。

【００９０】この動作がくり返し行われて、算術符号化
部７より適宜なタイミングで符号データＣＤａが出力さ
れるとともに、符号化確率評価部３がそれぞれの状態番
号について、確率推定テーブル６における状態推移を監
視し、順次、符号化が進行する。

【００９１】ここで、３ライン分の符号化処理が終了す
ると、テンプレート作成部１は、上述した処理により新
たなテンプレートテーブルデータを作成し、そのテンプ
レートテーブルデータをテンプレート記憶部５に保存す
る。

【００９２】これにより、それ以降は、状態番号判定部
２により判定される状態番号は、新たに形成されたテン
プレートに従ったものとなり、その結果、３ライン毎
に、画像の特徴を最もよく反映した内容にテンプレート
テーブルが更新されるので、符号化効率が大幅に向上す
る。

【００９３】一方、この符号化復号化装置が復号化動作
を行なうとき、まず、初期状態では、テンプレート作成
部１および状態番号判定部２は、符号化時と同じ初期設
定動作を行なう。また、復号化確率評価部４は、状態保
存テーブル１０の全ての状態番号について、状態データ
を状態０に初期設定するとともに、優勢シンボルデータ
を０（白）に設定する。

【００９４】また、状態番号判定部２は、初期状態で
は、状態番号０に対応した状態番号データＳＤを復号化
確率評価部４に出力しており、これにより、復号化確率
評価部４は、状態番号判定部２から加えられた状態番号
データＳＤに対応する状態番号について状態保存テーブ
ル８の記憶内容を取り出し、その取り出した記憶内容に
含まれている状態データによって確率推定テーブル６を
参照し、対応した推定確率を読み込み、その推定確率の
値を推定確率データＱｅｄとして算術符号化部７に出力
する。

【００９５】この状態で、符号データＣＤｂが加えられ
ると、算術復号化部９は、その符号データＣＤｂおよび
推定確率データＱｅｄに基づいて、上述した復号化処理
を実行し、１画素分のシンボルが優勢シンボルであるか
劣勢シンボルを判定して、その判定結果をシンボル種別
データＳｂｄとして復号化確率評価部４に出力する。ま
た、再正規化処理を生じた場合には、再正規化信号ＲＤ
を復号化確率評価部４に出力する。

【００９６】復号化確率評価部４は、算術復号化部９か
ら入力したシンボル種別データＳｂｄ、および、そのと
きに状態保存テーブル１０から取り出して保存している
優勢シンボルデータから、復号化されたシンボルの色を
判別し、その色に対応した復号化データＰＩＸｂを出力
する。また、復号化確率評価部４は、算術復号化部９か
ら再正規化信号ＲＤを入力すると、シンボル種別および
状態データに基づいて確率推定テーブル６を参照し、そ
のときの状態番号について、状態データを更新し、その
更新結果を状態保存テーブル１０に保存する。

【００９７】一方、復号データＰＩＸｂが加えられる
と、テンプレート作成部１および状態番号判定部２は、
符号化時と同様の処理を実行し、１画素分の注目画素Ｘ
について、それぞれの参照画素Ｒ１〜Ｒ１７の一致数カ
ウンタのインクリメント処理、状態番号を判定して状態
番号データＳＤを復号化確率評価部４に出力する処理を
行なう。状態番号判定部２は、そのときに入力した複号
データＰＩＸｂにより、記憶している参照データを１ビ
ット更新する。

【００９８】この動作がくり返し行われて、算術復号化
部９よりシンボル種別データＳｂｄが出力され、それに
対応した色データをもつ復号データＰＩＸｂが復号化確
率評価部４より出力される。それとともに、復号化確率
評価部４がそれぞれの状態番号について、確率推定テー
ブル６における状態推移を監視し、順次、復号化が進行
する。

【００９９】ここで、３ライン分の復号化処理が終了す
ると、符号化処理時と同様に、テンプレート作成部１
は、新たなテンプレートテーブルデータを作成し、その
テンプレートテーブルデータをテンプレート記憶部５に
保存する。

【０１００】これにより、それ以降は、状態番号判定部
２により判定される状態番号は、新たに形成されたテン
プレートに従ったものとなり、その結果、３ライン毎
に、画像の特徴を最もよく反映した内容にテンプレート
テーブルが更新される。

【０１０１】このようにして、復号化時には、テンプレ
ートテーブルの更新動作が符号化時と同じ条件で行われ
るので、適切に復号データＰＩＸｂを出力することがで
きる。

【０１０２】ところで、上述した実施例では、テンプレ
ートを構成する全ての参照画素Ａ〜Ｈについて３ライン
毎に更新しているが、画像の種別によっては、形成され
たテンプレートの全てに共通する部分があらわれること
が多く、その場合、その共通する部分については、あら
かじめテンプレートの構成画素として固定しておき、そ
れ以外の部分について、更新処理を行なうようにするこ
とができる。また、この場合には、更新対象となる画素
数が少なくなるので、テンプレート作成時の処理時間を
短縮でき、より高速なデータ処理を実現することができ
る。

【０１０３】例えば、図９に示すように、参照画素Ａ，
Ｂ，Ｃ，Ｄ，Ｅ，Ｆの６つを、テンプレートの固定的な
要素、すなわち、固定参照画素群として規定し、それ以
外の２つの参照画素Ｇ，Ｈをテンプレートの浮動的な要
素、すなわち、浮動参照画素群として規定する。また、
浮動参照画素群の参照画素Ｇ，Ｈは、参照画素Ｒ１，Ｒ
２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ
１４，Ｒ１５の中から選択される。

【０１０４】この場合、テンプレートの初期値として
は、図１０に示すようなものを用いる。したがって、こ
のテンプレートをあらわすテンプレートテーブルデータ
は、図１１に示すようなものとなり、参照画素Ａ〜Ｆま
では、固定的に使用されるので、更新を受けない更新保
護状態に設定されている。

【０１０５】また、本実施例では、装置構成として図６
のものをそのまま用いることができ、テンプレート作成
部１の処理内容のみが相違する。このテンプレート作成
部１が実行する処理例を図１２に示す。

【０１０６】まず、おのおのの参照画素Ｒ１，Ｒ２，Ｒ
３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，
Ｒ１５について、注目画素Ｘの色と一致するものを判定
し、その一致した参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ
６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５に対応
した一致数カウンタ（図示略）をインクリメントし（処
理５０１）、処理回数を記憶するためのカウンタｉの値
をインクリメントする（処理５０２）。

【０１０７】そして、カウンタｉの値が、テンプレート
作成のために必要な画素数ＡＡ以上の値になったかどう
かを調べ（判断５０３）、判断５０３の結果がＹＥＳに
なるときには、一致数カウンタの値が最大の参照画素Ｒ
１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１
３，Ｒ１４，Ｒ１５を選択し（処理５０４）、そのとき
のテンプレートテーブルの空き領域（浮動参照画素の領
域）のうち、一致数カウンタの最大値に対応した領域に
その参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ
８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５の識別情報を記憶し
て１画素分のテンプレートを形成する（処理５０５）。
このとき、選択した参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，
Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５の一
致数カウンタの値をクリアする。

【０１０８】ここで、テンプレートテーブルの全ての領
域にデータが記憶されているかどうかを調べて（判断５
０６）、判断５０６の結果がＮＯになるときには、処理
５０４に戻り、次の参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，
Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５の選
択処理を行なう。

【０１０９】判断５０６の結果がＹＥＳになるときに
は、そのときに形成したテンプレートテーブルデータを
テンプレート記憶部５に保存して（処理５０７）、カウ
ンタｉを０にクリアし（処理５０８）、この処理を終了
する。

【０１１０】また、判断５０３の結果がＮＯになるとき
には、即この処理を終了する。

【０１１１】ところで、上述した実施例では、浮動参照
画素群の全ての画素について、テンプレートの更新タイ
ミングで更新しているが、画像の局所的な特徴が同じ部
分が広い範囲で続く場合には、浮動参照画素の位置が変
更にならない場合がある。

【０１１２】このような場合では、テンプレートの更新
タイミング毎にテンプレートの更新処理を行なう必要が
なく、ある一定の条件下でテンプレートの更新を行なう
ようにすることができる。この場合には、テンプレート
の更新にかかる時間を短縮できるので、より高速な処理
を実現できる。

【０１１３】また、この場合にも、図６と同じ構成の装
置を用いることができ、テンプレート作成部１の処理内
容のみが相違する。このテンプレート作成部１が実行す
る処理例を図１３に示す。

【０１１４】まず、おのおのの参照画素Ｒ１，Ｒ２，Ｒ
３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，
Ｒ１５について、注目画素Ｘの色と一致するものを判定
し、その一致した参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ
６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５に対応
した一致数カウンタ（図示略）をインクリメントし（処
理６０１）、処理回数を記憶するためのカウンタｉの値
をインクリメントする（処理６０２）。

【０１１５】そして、カウンタｉの値が、テンプレート
作成のために必要な画素数ＡＡ以上の値になったかどう
かを調べ（判断６０３）、判断６０３の結果がＹＥＳに
なるときには、一致数カウンタの値が最大の参照画素Ｒ
１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１
３，Ｒ１４，Ｒ１５を選択し（処理６０４）、その選択
した参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ
８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５が参照画素Ｇ，Ｈの
いずれかに一致するかどうかを調べる（判断６０５）。

【０１１６】判断６０５の結果がＮＯになるときには、
その選択した参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，
Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５の一致数カ
ウンタの係数値が、そのときに参照画素Ｇとして記憶さ
れている参照画素の一致数カウンタの計数値の２倍以上
になっているかどうかを調べる（判断６０６）。

【０１１７】判断６０６の結果がＹＥＳになるときに
は、そのときのテンプレートテーブルの空き領域（浮動
参照画素の領域）にその選択した参照画素Ｒ１，Ｒ２，
Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１
４，Ｒ１５の識別情報を記憶して１画素分のテンプレー
トを形成する（処理６０７）。このとき、選択した参照
画素Ｒ１，Ｒ２，Ｒ３，Ｒ５，Ｒ６，Ｒ７，Ｒ８，Ｒ
９，Ｒ１３，Ｒ１４，Ｒ１５の一致数カウンタの値をク
リアする。

【０１１８】ここで、参照画素Ｒ１，Ｒ２，Ｒ３，Ｒ
５，Ｒ６，Ｒ７，Ｒ８，Ｒ９，Ｒ１３，Ｒ１４，Ｒ１５
のうち、一致数カウンタの値の上位２つまで処理が終了
したかどうかを調べて（判断６０８）、判断６０８の結
果がＮＯになるときには、処理６０４に戻り、次の参照
画素Ｈの選択処理を行なう。

【０１１９】判断６０８の結果がＹＥＳになるときに
は、そのときに形成したテンプレートテーブルデータを
テンプレート記憶部５に保存して（処理６０９）、カウ
ンタｉを０にクリアし（処理６１０）、この処理を終了
する。

【０１２０】また、判断６０３の結果がＮＯになるとき
には、即この処理を終了する。また、判断６０５の結果
がＹＥＳになるとき、および、判断６０６の結果がＮＯ
になるときには、即判断６０８に移行する。

【０１２１】ところで、上述した実施例では、３ライン
分の符号化／復号化処理を終了したタイミングでテンプ
レートを更新するようにしているが、この更新タイミン
グは、これに限ることはない。

【０１２２】また、上述した実施例では、テンプレート
を８画素から構成しているが、この画素数はこれに限る
ことはない。また、固定参照画素群に含まれる画素数を
６つに、浮動参照画素群を２つに設定したが、この画素
数の設定は、これに限ることはない。また、テンプレー
トを形成するために調査する領域を、参照画素Ｒ１〜Ｒ
１７の１７画素領域に設定しているが、この調査領域
は、これに限ることはない。

【０１２３】また、上述した実施例では、浮動参照画素
の更新の条件として、一致数カウンタの計数値が２倍に
なっていることを用いたが、この更新条件は、これに限
ることはない。

【０１２４】

【発明の効果】以上説明したように、本発明によれば、
符号化対象となる画像の局所的な特徴に最適なテンプレ
ートを使用することができるので、符号化効率が向上す
る。また、テンプレートを固定参照画素群と浮動参照画
素群に分割して、浮動参照画素群のみ再構成するように
しているので、テンプレートを形成するための処理を減
少でき、装置規模を縮小できるとともに、装置コストを
低減することができるという効果を得る。

【図面の簡単な説明】

【図１】ＱＭ−ｃｏｄｅｒの符号化／復号化処理の一例
を示すフローチャート。

【図２】テンプレートを作成するための参照画素の調査
領域を例示する概略図。

【図３】テンプレートテーブルデータの一例を示す概略
図。

【図４】作成されたテンプレートの一例を示す概略図。

【図５】マルコフ状態参照テーブルの一例を示す概略
図。

【図６】本発明の一実施例にかかる符号化復号化装置を
示すブロック図。

【図７】状態保存テーブルの記憶内容の一例を示す概略
図。

【図８】テンプレート作成部の処理例を示すフローチャ
ート。

【図９】固定参照画素群と浮動参照画素群を説明するた
めの概略図。

【図１０】テンプレートの他の例を示す概略図。

【図１１】テンプレートテーブルデータの他の例を示す
概略図。

【図１２】テンプレート作成部の他の処理例を示すフロ
ーチャート。

【図１３】テンプレート作成部のさらに他の処理例を示
すフローチャート。

【図１４】テンプレートの従来例を示す概略図。

【図１５】算術符号化方式の原理を説明するための概略
図。

【図１６】テンプレートの他の従来例を示す概略図。

【符号の説明】

１テンプレート作成部２状態番号判定部３符号化確率評価部４復号化確率評価部５テンプレート記憶部８，１０状態保存テーブル

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04N 1/41 - 1/419 G06T 9/00 H03M 7/30

Claims

(57)【特許請求の範囲】

【請求項１】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化復号化方
法において、符号化時、所定数の画素の符号化を終了す
るたびに、注目画素に隣接する所定の参照範囲内の画素
についてそれぞれ注目画素の色との一致数を計数し、そ
の一致数の大きいものから参照画素を所定数検出し、そ
の検出した複数の参照画素を含む形状のテンプレートを
新たに形成してそれ以降はこの新たに形成したテンプレ
ートを用いる一方、復号化時、所定数の画素の復号化を
終了するたびに、復号化を終了した注目画素に隣接する
所定の参照範囲内の画素についてそれぞれ注目画素の色
との一致数を計数し、その一致数の大きいものから参照
画素を所定数検出し、その検出した複数の参照画素を含
む形状のテンプレートを新たに形成してそれ以降はこの
新たに形成したテンプレートを用いることを特徴とする
符号化復号化方法。
【請求項２】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化復号化方
法において、符号化時、初期状態では所定のテンプレー
トを用いて符号化処理するとともに、所定数の画素の符
号化を終了するたびに、注目画素に隣接する所定の参照
範囲内の画素についてそれぞれ注目画素の色との一致数
を計数し、その一致数の大きいものから参照画素を所定
数検出し、その検出した複数の参照画素を含む形状のテ
ンプレートを新たに形成してそれ以降はこの新たに形成
したテンプレートを用いる一方、復号化時、初期状態で
は所定のテンプレートを用いて符号化処理するととも
に、所定数の画素の復号化を終了するたびに、復号化を
終了した注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数し、その
一致数の大きいものから参照画素を所定数検出し、その
検出した複数の参照画素を含む形状のテンプレートを新
たに形成してそれ以降はこの新たに形成したテンプレー
トを用いることを特徴とする符号化復号化方法。
【請求項３】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化装置にお
いて、所定数の画素の符号化を終了するたびに注目画素
に隣接する所定の参照範囲内の画素についてそれぞれ注
目画素の色との一致数を計数してその一致数の大きいも
のから参照画素を所定数検出する参照画素検出手段と、
その検出した複数の参照画素を含む形状のテンプレート
を形成するテンプレート作成手段と、このテンプレート
形成手段により形成したテンプレートを用いて注目画素
を符号化する符号化手段を備えたことを特徴とする符号
化装置。
【請求項４】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化装置にお
いて、所定数の画素の符号化を終了するたびに注目画素
に隣接する所定の参照範囲内の画素についてそれぞれ注
目画素の色との一致数を計数してその一致数の大きいも
のから参照画素を所定数検出する参照画素検出手段と、
その検出した複数の参照画素を含む形状のテンプレート
を形成するテンプレート作成手段と、初期状態では所定
のテンプレートを用いるとともに上記テンプレート形成
手段により新たなテンプレートが形成されるとその形成
されたテンプレートを用いて注目画素を符号化する符号
化手段を備えたことを特徴とする符号化装置。
【請求項５】復号化対象の注目画素に適用したテンプ
レートに含まれる既に復号化終了した複数画素の色の組
み合わせに対応した状態番号と、この状態番号に設定さ
れている予測画素色とその注目画素の色との一致状態に
基づいて、算術符号化方式の優勢／劣勢シンボルを判定
する復号化装置において、所定数の画素の復号化を終了
するたびに復号化を終了した注目画素に隣接する所定の
参照範囲内の画素についてそれぞれ注目画素の色との一
致数を計数しその一致数の大きいものから参照画素を所
定数検出する参照画素検出手段と、その検出した複数の
参照画素を含む形状のテンプレートを形成するテンプレ
ート作成手段と、このテンプレート作成手段により形成
されたテンプレートを用いて注目画素を復号化する復号
化手段を備えたことを特徴とする復号化装置。
【請求項６】復号化対象の注目画素に適用したテンプ
レートに含まれる既に復号化終了した複数画素の色の組
み合わせに対応した状態番号と、この状態番号に設定さ
れている予測画素色とその注目画素の色との一致状態に
基づいて、算術符号化方式の優勢／劣勢シンボルを判定
する復号化装置において、所定数の画素の復号化を終了
するたびに復号化を終了した注目画素に隣接する所定の
参照範囲内の画素についてそれぞれ注目画素の色との一
致数を計数しその一致数の大きいものから参照画素を所
定数検出する参照画素検出手段と、その検出した複数の
参照画素を含む形状のテンプレートを形成するテンプレ
ート作成手段と、初期状態では所定のテンプレートを用
いるとともに上記テンプレート形成手段により新たなテ
ンプレートが形成されるとその形成されたテンプレート
を用いて注目画素を復号化する復号化手段を備えたこと
を特徴とする復号化装置。
【請求項７】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化復号化方
法において、テンプレートを注目画素に対する相対位置
が固定されている固定参照画素群と注目画素に対する相
対位置が固定されていない浮動参照画素群から構成する
一方、符号化時、所定数の画素の符号化を終了するたび
に、注目画素に隣接する所定の参照範囲内の画素につい
てそれぞれ注目画素の色との一致数を計数し、その一致
数の大きいものから浮動参照画素数に一致する参照画素
を検出し、その検出した複数の参照画素と上記固定参照
画素群からなるテンプレートを新たに形成してそれ以降
はこの新たに形成したテンプレートを用いるとともに、
復号化時、所定数の画素の復号化を終了するたびに、復
号化を終了した注目画素に隣接する所定の参照範囲内の
画素についてそれぞれ注目画素の色との一致数を計数
し、その一致数の大きいものから浮動参照画素数に一致
する参照画素を検出し、その検出した複数の参照画素と
上記固定参照画素群からなるテンプレートを新たに形成
してそれ以降はこの新たに形成したテンプレートを用い
ることを特徴とする符号化復号化方法。
【請求項８】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化復号化方
法において、テンプレートを注目画素に対する相対位置
が固定されている固定参照画素群と注目画素に対する相
対位置が固定されていない浮動参照画素群から構成する
一方、符号化時、初期状態では所定のテンプレートを用
いて符号化処理するとともに、所定数の画素の符号化を
終了するたびに、注目画素に隣接する所定の参照範囲内
の画素についてそれぞれ注目画素の色との一致数を計数
し、その一致数の大きいものから浮動参照画素数に一致
する参照画素を検出し、その検出した複数の参照画素と
上記固定参照画素群からなるテンプレートを新たに形成
してそれ以降はこの新たに形成したテンプレートを用い
るとともに、復号化時、初期状態では所定のテンプレー
トを用いて符号化処理するとともに、所定数の画素の復
号化を終了するたびに、復号化を終了した注目画素に隣
接する所定の参照範囲内の画素についてそれぞれ注目画
素の色との一致数を計数し、その一致数の大きいものか
ら浮動参照画素数に一致する参照画素を検出し、その検
出した複数の参照画素と上記固定参照画素群からなるテ
ンプレートを新たに形成してそれ以降はこの新たに形成
したテンプレートを用いることを特徴とする符号化復号
化方法。
【請求項９】符号化対象の注目画素に適用したテンプ
レートに含まれる複数画素の色の組み合わせに対応した
状態番号と、この状態番号に設定されている予測画素色
とその注目画素の色との一致状態に基づいて、算術符号
化方式の優勢／劣勢シンボルを判定する符号化装置にお
いて、所定数の画素の符号化を終了するたびに注目画素
に隣接する所定の参照範囲内の画素についてそれぞれ注
目画素の色との一致数を計数しその一致数の大きいもの
から参照画素を所定数検出する参照画素検出手段と、こ
の参照画素検出手段が検出した複数の参照画素を注目画
素に対する相対位置が固定されていない浮動参照画素群
に設定するとともにこの浮動参照画素群および注目画素
に対する相対位置が固定されている固定参照画素群から
テンプレートを新たに形成するテンプレート作成手段
と、このテンプレート作成手段が形成したテンプレート
を用いて注目画素を符号化する符号化手段を備えたこと
を特徴とする符号化装置。
【請求項１０】符号化対象の注目画素に適用したテン
プレートに含まれる複数画素の色の組み合わせに対応し
た状態番号と、この状態番号に設定されている予測画素
色とその注目画素の色との一致状態に基づいて、算術符
号化方式の優勢／劣勢シンボルを判定する符号化装置に
おいて、所定数の画素の符号化を終了するたびに注目画
素に隣接する所定の参照範囲内の画素についてそれぞれ
注目画素の色との一致数を計数しその一致数の大きいも
のから参照画素を所定数検出する参照画素検出手段と、
この参照画素検出手段が検出した複数の参照画素を注目
画素に対する相対位置が固定されていない浮動参照画素
群に設定するとともにこの浮動参照画素群および注目画
素に対する相対位置が固定されている固定参照画素群か
らテンプレートを新たに形成するテンプレート作成手段
と、初期状態では所定のテンプレートを用いるとともに
上記テンプレート形成手段により新たなテンプレートが
形成されるとその形成されたテンプレートを用いて注目
画素を符号化する符号化手段を備えたことを特徴とする
符号化装置。
【請求項１１】復号化対象の注目画素に適用したテン
プレートに含まれる既に復号化終了した複数画素の色の
組み合わせに対応した状態番号と、この状態番号に設定
されている予測画素色とその注目画素の色との一致状態
に基づいて、算術符号化方式の優勢／劣勢シンボルを判
定する復号化装置において、所定数の画素の復号化を終
了するたびに注目画素に隣接する所定の参照範囲内の画
素についてそれぞれ注目画素の色との一致数を計数しそ
の一致数の大きいものから参照画素を所定数検出する参
照画素検出手段と、この参照画素検出手段が検出した複
数の参照画素を注目画素に対する相対位置が固定されて
いない浮動参照画素群に設定するとともにこの浮動参照
画素群および注目画素に対する相対位置が固定されてい
る固定参照画素群からテンプレートを新たに形成するテ
ンプレート作成手段と、このテンプレート作成手段が形
成したテンプレートを用いて注目画素を復号化する復号
化手段を備えたことを特徴とする復号化装置。
【請求項１２】復号化対象の注目画素に適用したテン
プレートに含まれる既に復号化終了した複数画素の色の
組み合わせに対応した状態番号と、この状態番号に設定
されている予測画素色とその注目画素の色との一致状態
に基づいて、算術符号化方式の優勢／劣勢シンボルを判
定する復号化装置において、所定数の画素の復号化を終
了するたびに注目画素に隣接する所定の参照範囲内の画
素についてそれぞれ注目画素の色との一致数を計数しそ
の一致数の大きいものから参照画素を所定数検出する参
照画素検出手段と、この参照画素検出手段が検出した複
数の参照画素を注目画素に対する相対位置が固定されて
いない浮動参照画素群に設定するとともにこの浮動参照
画素群および注目画素に対する相対位置が固定されてい
る固定参照画素群からテンプレートを新たに形成するテ
ンプレート作成手段と、初期状態では所定のテンプレー
トを用いるとともに上記テンプレート形成手段により新
たなテンプレートが形成されるとその形成されたテンプ
レートを用いて注目画素を復号化する復号化手段を備え
たことを特徴とする復号化装置。
【請求項１３】符号化対象の注目画素に適用したテン
プレートに含まれる複数画素の色の組み合わせに対応し
た状態番号と、この状態番号に設定されている予測画素
色とその注目画素の色との一致状態に基づいて、算術符
号化方式の優勢／劣勢シンボルを判定する符号化復号化
方法において、テンプレートを注目画素に対する相対位
置が固定されている固定参照画素群と注目画素に対する
相対位置が固定されていない浮動参照画素群から構成す
る一方、符号化時、所定数の画素の符号化を終了するた
びに、注目画素に隣接する所定の参照範囲内の画素につ
いてそれぞれ注目画素の色との一致数を計数し、その一
致数に基づいて新たな浮動参照画素に設定する参照画素
を検出し、その検出した参照画素を上記浮動参照画素群
の任意の画素に置換するとともにその置換後に得られた
浮動参照画素群と上記固定参照画素群からなるテンプレ
ートを新たに形成してそれ以降はこの新たに形成したテ
ンプレートを用いるとともに、復号化時、所定数の画素
の復号化を終了するたびに、復号化を終了した注目画素
に隣接する所定の参照範囲内の画素についてそれぞれ注
目画素の色との一致数を計数し、その一致数に基づいて
新たな浮動参照画素に設定する参照画素を検出し、その
検出した参照画素を上記浮動参照画素群の任意の画素に
置換するとともにその置換後に得られた浮動参照画素群
と上記固定参照画素群からなるテンプレートを新たに形
成してそれ以降はこの新たに形成したテンプレートを用
いることを特徴とする符号化復号化方法。
【請求項１４】符号化対象の注目画素に適用したテン
プレートに含まれる複数画素の色の組み合わせに対応し
た状態番号と、この状態番号に設定されている予測画素
色とその注目画素の色との一致状態に基づいて、算術符
号化方式の優勢／劣勢シンボルを判定する符号化復号化
方法において、テンプレートを注目画素に対する相対位
置が固定されている固定参照画素群と注目画素に対する
相対位置が固定されていない浮動参照画素群から構成す
る一方、符号化時、初期状態では所定のテンプレートを
用いるとともに、所定数の画素の符号化を終了するたび
に、注目画素に隣接する所定の参照範囲内の画素につい
てそれぞれ注目画素の色との一致数を計数し、その一致
数に基づいて新たな浮動参照画素に設定する参照画素を
検出し、その検出した参照画素を上記浮動参照画素群の
任意の画素に置換するとともにその置換後に得られた浮
動参照画素群と上記固定参照画素群からなるテンプレー
トを新たに形成してそれ以降はこの新たに形成したテン
プレートを用い、復号化時、初期状態では所定のテンプ
レートを用いるとともに、所定数の画素の復号化を終了
するたびに、復号化を終了した注目画素に隣接する所定
の参照範囲内の画素についてそれぞれ注目画素の色との
一致数を計数し、その一致数に基づいて新たな浮動参照
画素に設定する参照画素を検出し、その検出した参照画
素を上記浮動参照画素群の任意の画素に置換するととも
にその置換後に得られた浮動参照画素群と上記固定参照
画素群からなるテンプレートを新たに形成してそれ以降
はこの新たに形成したテンプレートを用いることを特徴
とする符号化復号化方法。
【請求項１５】符号化対象の注目画素に適用したテン
プレートに含まれる複数画素の色の組み合わせに対応し
た状態番号と、この状態番号に設定されている予測画素
色とその注目画素の色との一致状態に基づいて、算術符
号化方式の優勢／劣勢シンボルを判定する符号化装置に
おいて、所定数の画素の符号化を終了するたびに注目画
素に隣接する所定の参照範囲内の画素についてそれぞれ
注目画素の色との一致数を計数しその一致数の大きいも
のから参照画素を所定数検出する参照画素検出手段と、
この参照画素検出手段が検出した１つ以上の参照画素に
より注目画素に対する相対位置が固定されていない浮動
参照画素群のいずれかの位置の画素を更新するとともに
この更新後の浮動参照画素群および注目画素に対する相
対位置が固定されている固定参照画素群からテンプレー
トを新たに形成するテンプレート作成手段と、このテン
プレート作成手段が形成したテンプレートを用いて注目
画素を符号化する符号化手段を備えたことを特徴とする
符号化装置。
【請求項１６】符号化対象の注目画素に適用したテン
プレートに含まれる複数画素の色の組み合わせに対応し
た状態番号と、この状態番号に設定されている予測画素
色とその注目画素の色との一致状態に基づいて、算術符
号化方式の優勢／劣勢シンボルを判定する符号化装置に
おいて、所定数の画素の符号化を終了するたびに注目画
素に隣接する所定の参照範囲内の画素についてそれぞれ
注目画素の色との一致数を計数しその一致数の大きいも
のから参照画素を所定数検出する参照画素検出手段と、
この参照画素検出手段が検出した１つ以上の参照画素に
より注目画素に対する相対位置が固定されていない浮動
参照画素群のいずれかの位置の画素を更新するとともに
この更新後の浮動参照画素群および注目画素に対する相
対位置が固定されている固定参照画素群からテンプレー
トを新たに形成するテンプレート作成手段と、初期状態
では所定のテンプレートを用いるとともに上記テンプレ
ート形成手段により新たなテンプレートが形成されると
その形成されたテンプレートを用いて注目画素を符号化
する符号化手段を備えたことを特徴とする符号化装置。
【請求項１７】復号化対象の注目画素に適用したテン
プレートに含まれる復号化終了した複数画素の色の組み
合わせに対応した状態番号と、この状態番号に設定され
ている予測画素色とその注目画素の色との一致状態に基
づいて、算術符号化方式の優勢／劣勢シンボルを判定す
る復号化装置において、所定数の画素の復号化を終了す
るたびに注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数しその一
致数の大きいものから参照画素を所定数検出する参照画
素検出手段と、この参照画素検出手段が検出した１つ以
上の参照画素により注目画素に対する相対位置が固定さ
れていない浮動参照画素群のいずれかの位置の画素を更
新するとともにこの更新後の浮動参照画素群および注目
画素に対する相対位置が固定されている固定参照画素群
からテンプレートを新たに形成するテンプレート作成手
段と、このテンプレート作成手段が形成したテンプレー
トを用いて注目画素を復号化する復号化手段を備えたこ
とを特徴とする復号化装置。
【請求項１８】復号化対象の注目画素に適用したテン
プレートに含まれる復号化終了した複数画素の色の組み
合わせに対応した状態番号と、この状態番号に設定され
ている予測画素色とその注目画素の色との一致状態に基
づいて、算術符号化方式の優勢／劣勢シンボルを判定す
る復号化装置において、所定数の画素の復号化を終了す
るたびに注目画素に隣接する所定の参照範囲内の画素に
ついてそれぞれ注目画素の色との一致数を計数しその一
致数の大きいものから参照画素を所定数検出する参照画
素検出手段と、この参照画素検出手段が検出した１つ以
上の参照画素により注目画素に対する相対位置が固定さ
れていない浮動参照画素群のいずれかの位置の画素を更
新するとともにこの更新後の浮動参照画素群および注目
画素に対する相対位置が固定されている固定参照画素群
からテンプレートを新たに形成するテンプレート作成手
段と、初期状態では所定のテンプレートを用いるととも
に上記テンプレート形成手段により新たなテンプレート
が形成されるとその形成されたテンプレートを用いて注
目画素を復号化する復号化手段を備えたことを特徴とす
る復号化装置。