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