(57)【要約】【課題】低い処理負荷で予測符号化を実現する符号化装置を提供する。【解決手段】符号化装置２は、注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成し、注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成し、生成された前記第１の一致情報と、生成された前記第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成し、これらの一致情報に基づいて画像データを符号化する。【選択図】          図６
2005027078.tif 000002
【特許請求の範囲】
【請求項１】
注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報に基づいて画像データを符号化する符号化装置であって、
注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成する第１一致判定手段と、
注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成する第２一致判定手段と、
前記第１一致判定手段により生成された第１の一致情報と、前記第２一致判定手段により生成された第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する第３一致判定手段と
を有する符号化装置。
【請求項２】
前記第１一致判定手段および前記第２一致判定手段は、注目画素を主走査方向に移動させた場合に、参照画素の画素値と注目画素の画素値とが連続して一致する連続数を、前記一致情報として判定し、
前記第３一致判定手段は、前記第１一致判定手段により判定された連続数と、前記第２一致判定手段により判定された連続数とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する
請求項１に記載の符号化装置。
【請求項３】
前記第１一致判定手段により比較される参照画素は、前記第２一致判定手段により比較される参照画素と異なる主走査ライン上にある
請求項１または２に記載の符号化装置。
【請求項４】
前記第１一致判定手段により生成された一致情報、前記第２一致判定手段により生成された一致情報、および、前記第３一致判定手段により生成された一致情報に基づいて、最大の連続数を判定し、判定された最大の連続数を符号化する符号化手段
をさらに有する請求項１〜３のいずれかに記載の符号化装置。
【請求項５】
注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報に基づいて画像データを符号化する符号化方法であって、
注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成し、
注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成し、
生成された前記第１の一致情報と、生成された前記第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する
符号化方法。
【請求項６】
コンピュータを含み、注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報を用いて画像データを符号化する符号化装置において、
注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成するステップと、
注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成するステップと、
生成された前記第１の一致情報と、生成された前記第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値と、この注目画素の画素値との一致情報を生成するステップと
を前記符号化装置のコンピュータに実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の参照位置を参照して画像データを符号化する符号化装置に関する。
【０００２】
【従来の技術】
画像データを符号化する場合に、既定の予測方法により画素値を予測し、それらの予測結果（一致回数、予測値の誤差など）を符号化する方法がある。このように予測結果を符号化する場合には、予測的中率が高いほど符号量を小さくできる。そのため、予測的中率を向上させるため、複数の予測手段が設けられる場合がある。
例えば、特許文献１は、複数の予測部を有し、それぞれの予測部により生成された予測値のヒット回数を計数し符号化する画像符号化装置を開示する。
【０００３】
【特許文献１】
特開２０００−３５０２１５号公報
【０００４】
【発明が解決しようとする課題】
本発明は、上述した背景からなされたものであり、低い処理負荷で予測符号化を実現する符号化装置、符号化方法、およびプログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報に基づいて画像データを符号化する符号化装置であって、注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成する第１一致判定手段と、注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成する第２一致判定手段と、前記第１一致判定手段により生成された第１の一致情報と、前記第２一致判定手段により生成された第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する第３一致判定手段とを有する。
【０００６】
好適には、前記第１一致判定手段および前記第２一致判定手段は、注目画素を主走査方向に移動させた場合に、参照画素の画素値と注目画素の画素値とが連続して一致する連続数を、前記一致情報として判定し、前記第３一致判定手段は、前記第１一致判定手段により判定された連続数と、前記第２一致判定手段により判定された連続数とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する。
【０００７】
好適には、前記第１一致判定手段により比較される参照画素は、前記第２一致判定手段により比較される参照画素と異なる主走査ライン上にある。
【０００８】
好適には、前記第１一致判定手段により生成された一致情報、前記第２一致判定手段により生成された一致情報、および、前記第３一致判定手段により生成された一致情報に基づいて、最大の連続数を判定し、判定された最大の連続数を符号化する符号化手段をさらに有する。
【０００９】
［符号化方法］
また、本発明にかかる符号化方法は、注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報に基づいて画像データを符号化する符号化方法であって、注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成し、注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成し、生成された前記第１の一致情報と、生成された前記第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値とこの注目画素の画素値との一致情報を生成する。
【００１０】
［プログラム］
また、本発明にかかるプログラムは、コンピュータを含み、注目画素の画素値とこの注目画素に対して既定位置にある参照画素の画素値との一致情報を用いて画像データを符号化する符号化装置において、注目画素に対して第１の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第１の一致情報を生成するステップと、注目画素に対して第２の位置にある参照画素の画素値と、この注目画素の画素値とを比較して、第２の一致情報を生成するステップと、生成された前記第１の一致情報と、生成された前記第２の一致情報とに基づいて、注目画素に対して第３の位置にある参照画素の画素値と、この注目画素の画素値との一致情報を生成するステップとを前記符号化装置のコンピュータに実行させる。
【００１１】
【発明の実施の形態】
［背景］
まず、本発明の理解を助けるために、その背景を説明する。
まず、符号化方式の一例として予測符号化方式について説明する。予測符号化方式は、複数の参照位置の画素値を参照し、符号化対象である注目画素の画素値を符号化する。
【００１２】
図１は、符号化装置により実行され、画像データの符号化を実現する第１の符号化プログラム５の構成を示す図である。
図１に示すように、第１の符号化プログラム５は、画像データ取得部５００、予測データ生成部５１０、符号化部５４０および符号出力部５５０を有する。
符号化プログラム５において、画像データ取得部５００は、通信装置または記録装置（後述）などを介して、ラスタライズされた画像データを取得し、予測データ生成部５１０に対して出力する。
予測データ生成部５１０は、画像データ取得部５００から入力された画像データに基づいて、注目画素と参照画素との一致情報（以下、予測データ）を生成し、符号化部５４０に対して出力する。ここで、一致情報とは、注目画素の画素値と参照画素の画素値との相対的な関係を示す情報であり、例えば、注目画素と画素値が一致する参照画素の識別情報（以下、予測部ＩＤ）、注目画素と参照画素とで画素値が連続して一致した回数（以下、連続数）、および、注目画素と参照画素の画素値の差分（以下、予測誤差）などである。
符号化部５４０は、予測データ生成部５１０から入力された予測データを符号化して符号出力部５５０に対して出力する。
符号出力部５５０は、符号化部５４０から入力された符号データを通信装置または記録装置を介して出力する。
【００１３】
図２は、図１に示した第１の予測データ生成部５１０の構成を示す図である。
図２に示すように、予測データ生成部５１０は、複数の予測部５１２、予測誤差算出部５１４、ラン計数部５１６、および選択部５１８を含む。
予測部５１２は、互いに異なる参照位置の画素値を参照して、この画素値を予測値とし、この予測値と注目画素の画素値との比較結果をラン計数部５１６に対して出力する。本例の予測部５１２は、予測値と注目画素の画素値とが一致した場合（すなわち、予測が的中した場合）に、自己を識別する予測部ＩＤをラン計数部５１６に対して出力し、これ以外の場合に、一致しなかった旨をラン計数部５１６に対して出力する。
本例では、４種類の予測部５１２（第１予測部５１２ａ〜第４予測部５１２ｄ）が、注目画素に対して既定位置にある参照画素の画素値を用いて注目画素の予測値を生成し、予測値の注目画素の画素値との比較結果を出力する。なお、予測部５１２は、１種類以上であればよく、例えば、５種類の予測部を設けてもよい。
【００１４】
予測誤差算出部５１４は、予め定められた予測方法で注目画素の画素値を予測し、その予測値を注目画素の実際の画素値から減算し、予測誤差値としてラン計数部５１６に対して出力する。予測誤差算出部５１４の予測方法は、符号データを復号化する復号化装置の予測方法と対応していればよい。本例では、予測誤差算出部５１４は、第１予測部５１２ａと同じ予測方法で予測値を生成し、予測値と実際の画素値との差分を算出する。
【００１５】
ラン計数部５１６は、同一の予測部ＩＤが連続する数をカウントし、予測部ＩＤおよび連続数を選択部５１８に対して出力する。また、ラン計数部５１６は、予測誤差値が入力され場合に、この予測誤差値をそのまま選択部５１８に対して出力する。
【００１６】
選択部５１８は、ラン計数部５１６から入力された予測部ＩＤ、連続数および予測誤差値に基づいて、最も長く連続した予測部ＩＤを選択し、この予測部ＩＤおよびその連続数を予測データとして符号化部５４０（図１）に対して出力する。
例えば、選択部５１８は、予測部ＩＤがいずれかの予測部５１２を指している場合には、この予測部ＩＤに対応する内部カウンタを１だけ増やし、予測誤差値が入力された場合で、かつ、内部カウンタが０でない場合には、それぞれの内部カウンタの値から最大値を選択し、この内部カウンタに対応する予測部ＩＤと対応付けて符号化部５４０に対して出力し、その後に入力された予測誤差値を出力する。
【００１７】
図３は、符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。図３に示すように、ステップ１００（Ｓ１００）において、画像データ取得部５００が画像データを取得すると、符号化プログラム５は、注目画素位置の初期設定，各予測部位置の初期設定，処理済ライン数を０にするなどの内部状態の初期化を行う。
【００１８】
ステップ１０５（Ｓ１０５）において、符号化プログラム５は、符号化処理が終了したライン数をカウントし、処理済ライン数がページのライン数に達したかどうか（ページ終了）を判定する。符号化プログラム５は、処理済ライン数がページのライン数に達したと判定された場合に、Ｓ１８０の処理に移行し、これ以外の場合に、Ｓ１１０の処理に移行する。
【００１９】
ステップ１１０（Ｓ１１０）において、符号化プログラム５は、注目画素の位置がライン終端に達したかどうか（ライン終了）を判定する。符号化プログラム５は、注目画素の位置がライン終端に達したと判定した場合に、Ｓ１７０の処理に移行し、これ以外の場合に、Ｓ１２０の処理に移行する。すなわち、符号化プログラム５は、ライン終了時には次のラインへの移動を行い、ライン終了でなければ次の注目画素の処理へ移る。
【００２０】
ステップ１２０（Ｓ１２０）において、予測データ生成部５１０は、画像データ取得部５００から入力された画像データに基づいて、一組の予測部ＩＤおよびその連続数、または、予測誤差値を生成し、予測データとして符号化部５４０に対して出力する。
ステップ１６０（Ｓ１６０）において、符号化部５４０は、予測データ生成部５１０から入力された予測データ（予測部ＩＤ、連続数および予測誤差値）を符号化し、符号出力部５５０に対して出力する。
【００２１】
ステップ１６５（Ｓ１６５）において、画像データ取得部５００は、注目画素の位置をスキャン方向に移動させ、Ｓ１１０の処理に戻る。画素の移動量は、予測データの連続数に応じて異なる。すなわち、画像データ取得部５００は、予測部ＩＤが連続する場合に、その連続数分だけ注目画素の位置をスキャン方向に移動させ、予測誤差値が予測データ生成部５１０から出力された場合に、１画素分だけ注目画素の位置を移動させる。
このように、符号化プログラム５は、同一スキャンライン（主走査ライン）上で予測データの生成（Ｓ１２０）および符号化処理（Ｓ１６０）をスキャンライン終端まで繰り返す。
【００２２】
ステップ１７０（Ｓ１７０）において、符号化部５４０は、符号化プログラム５がスキャンラインの終端位置を検知すると、未処理の予測データの符号化処理およびライン終端符号化処理を行う。
ステップ１７５（Ｓ１７５）において、符号化プログラム５は、次のラインの処理に移行する。
【００２３】
ステップ１８０（Ｓ１８０）において、符号化プログラム５がページの終了を検知すると、符号化部５４０は、ページの終端符号化処理を行い、処理を終了する。
【００２４】
このように、符号化プログラム５は、ラインおよびページを一区切りとして予測データの生成およびこれの符号化を行う。
【００２５】
図４は、図３に示した第１の予測処理（Ｓ１２０）をより詳細に説明するフローチャートである。
図４に示すように、ステップ１２２（Ｓ１２２）において、予測部５１２の要求に応じて画像データ取得部５００が注目画素の位置を更新すると、各予測部５１２（第１予測部５１２ａ〜第４予測部５１２ｄ）は、注目画素の位置に応じた既定の参照位置を設定し、設定された参照位置の画素値を読み出し、読み出された画素値を予測値とする。なお、予測部５１２には優先順位が設定されおり、この優先順位に従って、参照位置の設定、および、参照位置の画素値の読出しがなされる。
また、予測誤差算出部５１４は、注目画素の画素値と、第１予測部５１２ａによる予測値との差分を算出し、予測誤差値として選択部５１６に対して出力する。
【００２６】
ステップ１２４（Ｓ１２４）において、予測部５１２は、注目画素の画素値と予測値とを比較し、一致しているかどうかを判定する。
予測部５１２は、一致していると判定された場合に、この予測部５１２の予測部ＩＤをラン計数部５１６に対して出力し、Ｓ１２６の処理に移行する。また、予測部５１２は、一致していないと判定された場合に、Ｓ１３０の処理に移行する。
【００２７】
ステップ１２６（Ｓ１２６）において、ラン計数部５１６は、予測部５１２から予測部ＩＤが入力されると、この予測部ＩＤに対応するカウンタに１を加算する。
ステップ１２８（Ｓ１２８）において、予測部５１２は、注目画素をスキャン方向に移動させるよう画像データ取得部５００に指示し、次の注目画素の画素値と、この注目画素に対応する参照位置の画素値とを読み出し、Ｓ１２４の処理に戻る。
このように、いずれかの予測部５１２が連続で的中する場合には、その予測部５１２は、スキャン方向に連続する複数の注目画素について続けて予測処理を行い、ラン計数部５１６は、その連続数をカウントする。
【００２８】
ステップ１３０（Ｓ１３０）において、ラン計数部５１６は、予測部５１２の予測値が的中しない場合に、予測部ＩＤと、これに対応するカウンタの数（連続数）を選択部５１８に対して出力する。
選択部５１８は、ラン計数部５１６からこれまでに入力された最大の連続数を最長予測ラン長として予測部ＩＤに対応付けて記憶し、新たに入力された他の予測部ＩＤの連続数と比較する。
符号化プログラム５は、新たに入力された連続数が選択部５１８内に記憶されている連続数よりも大きいと判定された場合に、Ｓ１３２の処理に移行し、これ以外の場合に、Ｓ１３４の処理に移行する。
ステップ１３２（Ｓ１３２）において、選択部５１８は、最長予測ラン長を、新たに入力された連続数および予測部ＩＤに更新する。
このように、選択部５１８は、ラン計数部５１６から入力される複数の予測部ＩＤの連続数から、最大の予測部ＩＤを選択する。
【００２９】
ステップ１３４（Ｓ１３４）において、予測データ生成部５１０は、全ての予測部５１２について予測処理が終了したか否かを判定し、終了した場合にＳ１３６の処理に移行し、これ以外の場合に、Ｓ１２２の処理に戻り、次の優先順位の予測部５１２についてＳ１２２〜Ｓ１３２の処理を行う。
【００３０】
ステップ１３６（Ｓ１３６）において、選択部５１８は、全予測部５１２の予測が終了すると、最長予測ラン長として記憶されていた連続数および予測部ＩＤを予測データとして符号化部５４０（図１）に対して出力する。また、選択部５１８は、最長予測ラン長として記憶されいる連続数が０の場合（注目画素の画素値と予測部５１２の予測値とがいずれも一致しなかった場合）に、予測誤差算出部５１４から入力された予測誤差値を予測データとして符号化部５４０に対して出力する。
【００３１】
図５は、図４を参照して説明した予測処理（Ｓ１２０）を模式的に説明する図である。
図５（Ａ）に示すように、ラスタライズされた画像データには、主走査方向（スキャン方向）および副走査方向（スキャン方向と直角方向）に並んだ複数の画素が含まれる。
それぞれの画素は画素値を有する。本例の画像データは、白色と黒色とを用いて表現された２値データであるが、これに限定されるものではない。また、本例の画像データは、周縁部（斜線部）にいずれの画素値に属さない値をとるが、上記２値データのいずれかであってもよい。スキャン方向は、図面の左右方向に設定されており、「１」から「８」までの番号が付された画素群からなるラインについて説明する。
【００３２】
図５（Ｂ）は、予測部５１２それぞれの参照位置を例示する。
図５（Ｂ）に例示するように、各予測部５１２の参照位置は、注目画素Ｘとの相対位置として設定されている。具体的には、第１予測部５１２ａは、注目画素Ｘのスキャン方向上流の参照画素Ａを参照し、第２予測部５１２ｂ〜第４予測部５１２ｄは、注目画素Ｘの上方（副走査方向上流）のスキャンライン上に設定されている。本例では、このように同一スキャンライン上に複数の参照画素（参照位置）が設定されている。
【００３３】
図５（Ｃ）は、図５（Ｂ）に例示した各予測部５１２の優先順位および符号を例示する。
予測部５１２の優先順位は、予測値の的中率（参照画素の画素値と注目画素の画素値とが一致する確率）に応じて設定されており、ＭＲＵ（Ｍｏｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムにより動的に更新されてもよい。
また、各予測部５１２に対して割り当てられる符号は、例えば、各予測部５１２の的中率に応じて設定されたエントロピー符号であり、優先順位に対応する符号長となる。
【００３４】
図５（Ｄ）は、図５（Ｃ）に例示された符号による符号データを例示する。
図５（Ｄ）に例示するように、いずれかの予測部５１２の予測が的中した場合には、その予測部５１２（予測部ＩＤ）に対応する符号と、この予測部５１２の連続数とを符号化し、いずれの予測部５１２も予測が的中しなかった場合には、予測誤差値が符号化される。
【００３５】
図６は、図５に例示した画像データに対して予測処理（Ｓ１２０）を行った場合の予測状況の表を示す。
まず、図５（Ａ）に示すように、第１のスキャン位置（例えば、スキャンライン最上流の画素１）が注目画素に設定される。そして、図５（Ｃ）に例示した優先順位に従い、第１予測部５１２ａが参照画素Ａを参照して画素値（Ｐ１）を読み出し、読み出された画素値を予測値（Ｐ１）と、注目画素の画素値（Ｘ１）とを比較する。画素値が一致した場合に、第１予測部５１２ａは、ラン計数部５１６に対して第１予測部５１２の予測部ＩＤを出力する。この場合に、
Ｘ１＝Ｐ１・・・（式１）
の関係が成立していることになる。
また、この第１のスキャン位置で第２予測部５１２ｂが参照画素Ｂの画素値（Ｐ２）を読み出し、注目画素（Ｘ１）と比較し、一致すると判断した場合には、
Ｘ１＝Ｐ２・・・（式２）
の関係が成立していることになる。
【００３６】
次に、第２のスキャン位置（例えば、同一スキャンラインの画素２）が注目画素に設定される。そして、第１予測部５１２ａが参照画素Ａを参照して画素値（Ｘ１）を読み出し、注目画素の画素値（Ｘ２）とを比較する。画素値が一致した場合に、
Ｘ２＝Ｘ１・・・（式３）
の関係が成立していることになる。
同様に、この第２のスキャン位置で第２予測部５１２ｂが参照画素Ｂの画素値（Ｐ３）を読み出し、注目画素（Ｘ２）と比較し、一致すると判断した場合には、
Ｘ２＝Ｐ３・・・（式４）
の関係が成立していることになる。
【００３７】
このような状況において、上記（式１）〜（式４）に基づいて、
Ｘ２＝Ｐ２
の関係が成立していることが分かる。すなわち、第１予測部５１２ａおよび第２予測部５１２ｂの予測データに基づいて、第２のスキャン位置において注目画素の画素値（Ｘ２）と参照画素Ｃの画素値（Ｐ２）とが一致していることが導き出される。
また、同様に、
Ｘ１＝Ｐ３
の関係も成り立つことから、第１予測部５１２ａおよび第２予測部５１２ｂの予測データに基づいて、第１のスキャン位置において注目画素の画素値（Ｘ１）と参照画素Ｄの画素値（Ｐ３）とが一致していることが導き出される。
したがって、参照画素Ｃ（第３予測部５１２ｃ）および参照画素Ｄ（第４予測部５１２ｄ）における予測データの少なくとも一部は、第１予測部５１２ａおよび第２予測部５１２ｂの予測データに基づいて判定可能である。
【００３８】
しかしながら、本符号化プログラム５は、それぞれの予測部５１２についてそれぞれ予測処理を行う。
そこで、本発明にかかる符号化プログラム６（後述）は、上記冗長性を排して、符号化処理の負荷を軽減する。
【００３９】
［実施形態］
以下、本発明の実施の形態を説明する。
図７は、本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図７に示すように、符号化装置２は、ＣＰＵ２１２およびメモリ２１４などを含む制御装置２１、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、および、ＬＣＤ表示装置あるいはＣＲＴ表示装置およびキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２５から構成される。
符号化装置２は、例えば、本発明にかかる符号化プログラム６がプリンタドライバの一部としてインストールされた汎用コンピュータであり、通信装置２２または記録装置２４などを介して画像データを取得し、取得された画像データを符号化してプリンタ装置３に送信する。
【００４０】
図８は、制御装置２１（図７）により実行され、本発明にかかる符号化方法を実現する第２の符号化プログラム６の構成を示す図である。
図８に示すように、第２の符号化プログラム６は、図１に示した第１の符号化プログラム５における第１の予測データ生成部５１０を、第２の予測データ生成部５２０に置換した構成をとる。また、図８に示す符号化プログラム６の各構成のうち、図１に示した各構成と実質的に同一なものには同一の符号が付されている。
符号化プログラム６は、例えば記録媒体２４０（図７）を介して制御装置２１に供給され、メモリ２１４にロードされて実行される。
【００４１】
図９は、第２の予測データ生成部５２０の構成を説明する図である。
図９に示すように、第２の予測データ生成部５２０は、第１の予測データ生成部５１０に、予測制御部５２２を追加し、第１の選択部５１８を第２の選択部５２８に置換した構成をとる。なお、図９に示した予測データ生成部５２０のうち、図２に示した予測データ生成部５１０の構成と実質的に同一なものには同一の符号が付されている。
【００４２】
予測データ生成部５２０において、第２のラン計数部５２６は、第１のラン計数部５１６と同様に、第１予測部５１２ａおよび第２予測部５１２ｂの連続数をカウントする。そして、ラン計数部５２６は、第１予測部５１２ａおよび第２予測部５１２ｂの連続数に基づいて、第３予測部５１２ｃおよび第４予測部５１２ｄの省略ラン長を判定する。省略ラン長とは、第１予測部５１２ａおよび第２予測部５１２ｂの連続数に基づいて、第３予測部５１２ｃまたは第４予測部５１２ｄについて判定される連続数のことである。
【００４３】
また、ラン計数部５２６は、判定された省略ラン長を、第３予測部５１２ｃまたは第４予測部５１２ｄの予測部ＩＤに対応するカウンタに加算し、第３予測部５１２ｃおよび第４予測部５１２ｄに対応する省略ラン長を予測制御部５２２に対して出力する。
【００４４】
予測制御部５２２は、予測制御部５２２から入力された省略ラン長に応じた注目画素を設定し、第３予測部５１２ｃおよび第４予測部５１２ｄに対して出力する。すなわち、第３予測部５１２ｃおよび第４予測部５１２ｄは、省略ラン長に対応する注目画素に対する予測処理を省略し、省略ラン長の数値分スキップした位置から予測処理を開始する。
なお、予測制御部５２２は、第１予測部５１２ａおよび第２予測部５１２ｂに対して、順次注目画素を設定する。
【００４５】
図１０は、第２の予測処理（Ｓ１２０）をより詳細に説明するフローチャートである。なお、図１０に示した各処理のうち、図４に示した処理と実質的に同一なものには同一の符号が付されている。
図１０に示すように、ステップ１３８（Ｓ１３８）において、画像データ取得部５００により１ライン分の画像データが入力されると、予測制御部５２２は、入力された画像データに対して、注目画素を設定する。
第１予測部５１２ａまたは第２予測部５１２ｂは、設定された注目画素について、既定された参照画素（参照画素Ａまたは参照画素Ｂ）を設定する。
【００４６】
ステップ１２４（Ｓ１２４）において、第１予測部５１２ａまたは第２予測部５１２ｂは、参照画素の画素値を読み出し、読み出された画素値を予測値とする。そして、第１予測部５１２ａまたは第２予測部５１２ｂは、注目画素の画素値と、この予測値とを比較し、一致しているかどうかを判定する。
第１予測部５１２ａまたは第２予測部５１２ｂは、一致していると判定された場合に、この予測部５１２の予測部ＩＤをラン計数部５２６に対して出力し、Ｓ１２６の処理に移行する。また、第１予測部５１２ａまたは第２予測部５１２ｂは、一致していないと判定された場合に、一致しなかった旨をラン計数部５２６に対して出力し、Ｓ１４０の処理に移行する。
【００４７】
ステップ１２６（Ｓ１２６）において、ラン計数部５２６は、第１予測部５１２ａまたは第２予測部５１２ｂから入力された予測部ＩＤに対応するカウンタに１を加算する。
また、ラン計数部５２６は、一致した旨を予測制御部５２２に対して出力する。
ステップ１２８（Ｓ１２８）において、予測制御部５２２は、ラン計数部５２６から一致した旨が入力されると、注目画素の位置をスキャン方向に移動させて、次の注目画素を設定する。
【００４８】
ステップ１４０（Ｓ１４０）において、ラン計数部５２６は、第１予測部５１２ａおよび第２予測部５１２ｂ（基準予測部）の予測処理が終了したか否かを判定する。具体的には、ラン計数部５２６は、第１予測部５１２ａおよび第２予測部５１２ｂの両方から、一致しない旨が入力されると、基準予測部の予測処理が終了したと判定する。
ラン計数部５２６は、基準予測部の予測処理が終了したと判定した場合に、Ｓ１４２の処理に移行し、これ以外の場合に、次の優先順位の予測部５１２に対して注目画素を設定するよう予測制御部５２２に対して指示する。
【００４９】
ステップ１４２（Ｓ１４２）において、ラン計数部５２６は、第１予測部５１２ａまたは第２予測部５１２ｂの連続数が最大になるか判定する。具体的には、ラン計数部５２６は、第１予測部５１２ａの連続数（以下、第１ラン長）と、第２予測部５１２ｂの連続数（第２ラン長）とが共に１以上であり、かつ、第２ラン長が第１ラン長よりも大きい場合に、第２ラン長を最大値として確定させる。また、ラン計数部５２６は、第１ラン長と第２ラン長とが共に１以上であり、かつ、第１ラン長が第２ラン長よりも２以上大きい場合に、第１ラン長を最大値として確定させる。
【００５０】
ステップ１４４（Ｓ１４４）において、ラン計数部５２６は、ラン長の最大値を確定した場合に、Ｓ１５０の処理に移行し、これ以外の場合に、Ｓ１４６の処理に移行する。
ステップ１４６（Ｓ１４６）において、ラン計数部５２６は、第３予測部５１２ｃおよび第４予測部５１２ｄの予測処理を行うよう予測制御部５２２に対して指示する。その際に、ラン計数部５２６は、第３予測部５１２ｃまたは第４予測部５１２ｄについて、第１ラン長および第２ラン長に基づいて、一致または不一致が判定できる参照位置をスキップするよう予測制御部５２２に指示する。
予測制御部５２２は、ラン計数部５２６の指示に応じて、注目画素を第３予測部５１２ｃおよび第４予測部５１２ｄに対して設定し、第３予測部５１２ｃおよび第４予測部５１２ｄは、設定された注目画素について、予測値と注目画素の画素値とを比較し、比較結果をラン計数部５２６に対して出力する。
【００５１】
ステップ１４８（Ｓ１４８）において、ラン計数部５２６は、第３予測部５１２ｃまたは第４予測部５１２ｄの連続数が最大になるか判定する。具体的には、ラン計数部５２６は、第１ラン長と第２ラン長とが共に１以上であり、かつ、第１ラン長が第２ラン長よりも２以上大きい場合に、第３予測部５１２ｃの最初の参照位置で一致し、かつ、第２ランの最後尾の画素より後で一致したときに、第３予測部５１２ｃの連続数を最大として確定させる。また、ラン計数部５２６は、第１ラン長と第２ラン長とが共に１以上であり、かつ、第１ラン長が第２ラン長と等しい場合に、第４予測部５１２ｄが第２ランの最後尾の画素より後で２回以上一致したときに、第４予測部５１２ｄの連続数を最大として確定させる。
また、ラン計数部５２６は、上記判定方法により連続数の最大を確定できない場合に、各予測部５１２に対応するカウンタの値を選択部５１８に対して出力し、選択部５１８が、最大の連続数を選択する。
【００５２】
ステップ１５０（Ｓ１５０）において、選択部５１８は、最大の連続数を予測部ＩＤに対応付けて符号化部５４０（図８）に対して出力する。なお、最大数が０の場合に、選択部５１８は、予測誤差算出部５１４から入力された予測誤差値を符号化部５４０に対して出力する。
【００５３】
このように、本実施形態における符号化装置２は、基準となる予測部５１２（本例では第１予測部５１２ａおよび第２予測部５１２ｂ）の予測結果に基づいて、他の予測部５１２の予測結果の少なくとも一部を類推することにより、予測処理の一部を省略し、符号化処理の負荷を軽減する。
【００５４】
［変形例］
なお、上記実施形態では、４つの予測部５１２が設けられた符号化装置２を具体例として説明したが、これに限定されるものではない。例えば、３つの予測部５１２を有する符号化装置や、５つの予測部５１２を有する符号化装置なども上記実施形態と同様に動作可能である。特に、予測部５１２の数を変えると、最大連続数の判定方法が変化するので、以下、最大連続数の判定方法を例示する。
【００５５】
［予測部が３つの場合］
符号化装置２が、第１予測部５１２ａ、第２予測部５１２ｂおよび第３予測部５１２ｃを有する場合、
第１予測部５１２ａの連続数（第１ラン長）および第２予測部５１２ｂの連続数（第２ラン長）が共に１以上であり、第１ラン長よりも第２ラン長が大きい場合に、符号化装置２は、第２ラン長を最大と判定し、第３予測部５１２ｃによる予測処理を省略する。
【００５６】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長よりも２以上大きい場合に、符号化装置２は、第１ラン長を最大と判定し、第３予測部５１２ｃによる予測処理を省略する。
【００５７】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長よりも１だけ大きい場合に、符号化装置２は、第３予測部５１２ｃによる予測処理を行い、第３予測部５１２ｃが最初の参照位置で一致し、かつ、第２ランの最終画素の次の画素から第１ラン最終画素の直上画素までを参照位置として一致した場合に、第３予測部５１２ｃの連続数（第３ラン長）を最大と判定する。
【００５８】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長と等しい場合に、符号化装置２は、第３予測部５１２ｃによる予測処理を行い、第３予測部５１２ｃが最初の参照位置で一致した場合に、第１ラン長と第２ラン長とが等しいと判定する。
【００５９】
［予測部が５つの場合］
次に、第４予測部ｄにより参照される参照画素Ｄのスキャン方向に１画素分下流に位置する参照画素Ｅを考える。つまり、参照画素Ｅを参照して予測処理を行う第５予測部５１２ｅを符号化装置２に追加した場合の最大連続数の判定方法を説明する。
第１ラン長および第２ラン長が共に２以上であり、第１ラン長よりも第２ラン長が大きい場合に、符号化装置２は、第２ラン長を最大と判定し、第３予測部５１２ｃによる予測処理を省略する。
【００６０】
また、第１ラン長が１であり、第１ラン長よりも第２ラン長が大きい場合に、符号化装置２は、第５予測部５１２ｅの連続数（第５ラン長）をカウントし、第２ラン長または第５ラン長の大きい方を最大と判定し、第３予測部５１２ｃおよび第４予測部５１２ｄによる予測処理を省略する。
【００６１】
また、第１ラン長および第２ラン長が共に２以上であり、第１ラン長が第２ラン長よりも２以上大きい場合に、符号化装置２は、第１ラン長を最大と判定し、第３予測部５１２ｃ〜第５予測部５１２ｅの予測処理を省略する。
【００６２】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長よりも１だけ大きい場合に、符号化装置２は、第３予測部５１２ｃによる予測処理を行い、第３予測部５１２ｃが最初の参照位置で一致し、かつ、第２ランの最終画素の次の画素から第１ラン最終画素の直上画素までを参照位置として一致した場合に、第３ラン長を最大と判定し、第４予測部５１２ｄおよび第５予測部５１２ｅの予測処理を省略する。
【００６３】
また、上記いずれにも該当しない場合に、符号化処理２は、第５ラン長をカウントし、第１ラン長または第２ラン長などと比較して、最大も連続数を判定する。
【００６４】
［予測部に優先順位が無い場合］
また、ＬＺ７７符号化のように最大連続数となる予測部５１２同士に優先順位が無い場合に、上記最大連続数の判定方法を簡略化できる。例えば、第１予測部５１２ａ、第２予測部５１２ｂ、第３予測部５１２ｃおよび第４予測部５１２ｄを有する符号化装置２の場合に、第１ラン長と第２ラン長とが等しいときは、第３ラン長が単独で最大となりえないので、この部分を簡略化する。なお、この場合の優先順位は、複数の予測部５１２による連続数が最大値として同一となった場合に、いずれの予測部ＩＤおよび連続数を符号化するかを決定するものである。したがって、予測順序は、上記実施形態と同様に第１予測部５１２ａから順に行われる場合を具体例とする。
【００６５】
具体的には、第１ラン長および第２ラン長が共に１以上であり、第１ラン長よりも第２ラン長が大きい場合に、符号化装置２は、第２ラン長を最大と判定し、第３予測部５１２ｃおよび第４予測部５１２ｄの予測処理を省略する。
【００６６】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長よりも２以上大きい場合に、符号化装置２は、第１ラン長を最大と判定し、第３予測部５１２ｃおよび第４予測部５１２ｄの予測処理を省略する。
【００６７】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長よりも１だけ大きい場合に、符号化装置２は、第３予測部５１２ｃによる予測処理を行い、第３予測部５１２ｃが最初の参照位置で一致し、かつ、第２ランの最終画素の次の画素から第１ラン最終画素の直上画素までを参照位置として一致した場合に、第３予測部５１２ｃの連続数（第３ラン長）を最大と判定し、以下の画素について第３予測部５１２ｃによる予測処理を継続する。
【００６８】
また、第１ラン長および第２ラン長が共に１以上であり、第１ラン長が第２ラン長と等しい場合に、符号化装置２は、第３予測部５１２ｃおよび第４予測部５１２ｄによる予測処理を行い、第４予測部５１２ｄが第１ラン最終画素の直上画素を参照位置として一致した場合に、第４ラン長を最大と判定し、以下の画素について第４予測部５１２ｄによる予測処理を継続する。
【００６９】
以上説明したように、符号化装置２は、第１予測部５１２ａおよび第２予測部５１２ｂの予測結果（連続数）に基づいて、いずれの予測部５１２による連続数が最大となりうるかを判定し、最大となりえない予測部５１２による予測処理を省略することにより、符号化処理の負荷を軽減する。
【００７０】
【発明の効果】
以上説明したように、本発明にかかる符号化装置によれば、低い処理負荷で予測符号化を実現することができる。
【図面の簡単な説明】
【図１】符号化装置により実行され、画像データの符号化を実現する第１の符号化プログラム５の構成を示す図である。
【図２】図１に示した第１の予測データ生成部５１０の構成を示す図である。
【図３】符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。
【図４】図３に示した第１の予測処理（Ｓ１２０）をより詳細に説明するフローチャートである。
【図５】図４を参照して説明した予測処理（Ｓ１２０）を模式的に説明する図であり、（Ａ）は、ラスタライズされた画像データを例示し、（Ｂ）は、予測部５１２それぞれの参照位置を例示し、（Ｃ）は、（Ｂ）に例示した各予測部５１２の優先順位および符号を例示し、（Ｄ）は、（Ｃ）に例示された符号による符号データを例示する。
【図６】図５に例示した画像データに対して予測処理（Ｓ１２０）を行った場合の予測状況の表を示す。
【図７】本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図８】制御装置２１（図７）により実行され、本発明にかかる符号化方法を実現する第２の符号化プログラム６の構成を示す図である。
【図９】第２の予測データ生成部５２０の構成を説明する図である。
【図１０】第２の予測処理（Ｓ１２０）をより詳細に説明するフローチャートである。
【符号の説明】
２・・・符号化装置
２１・・・制御装置
２１２・・・ＣＰＵ
２１４・・・メモリ
２２・・・通信装置
２４・・・記録装置
２４０・・・記録媒体
２５・・・ＵＩ装置
５，６・・・画像形成プログラム
５００・・・画像データ取得部
５１０，５２０・・・予測データ生成部
５１２・・・予測部
５１４・・・予測誤差算出部
５１６，５２６・・・ラン計数部
５１８・・・選択部
５２２・・・予測制御部
５４０・・・符号化部
５５０・・・符号出力部
【図１】
2005027078.tif 000003
【図２】
2005027078.tif 000004
【図３】
2005027078.tif 000005
【図４】
2005027078.tif 000006
【図５】
2005027078.tif 000007
【図６】
2005027078.tif 000008
【図７】
2005027078.tif 000009
【図８】
2005027078.tif 000010
【図９】
2005027078.tif 000011
【図１０】
2005027078.tif 000012