(57)【要約】【課題】  符号化パラメータの変動を抑制するだけでなく、その符号化パラメータがランに適した値になる確率を高くなし、高い圧縮効率の符号化データを得る。【解決手段】  着目画素Ｘｉをランレングス符号化する場合、着目画素Ｘｉより１ライン前の画素のランを配列変数から取得し、着目画素が含まれるランの符号化パラメータＪ，Ｋを決定する（ステップＳ９０３）。そして、着目画素からのランＲＬを計数する（Ｓ９０５乃至Ｓ９０８）。そして、取得した符号化パラメータを着目画素が含まれるランＲＬを符号化する際の初期パラメータとし、その符号化パラメータを更新しつつ着目画素を含むランをランレングス符号化する（ステップＳ９１１）。そして、着目画素を含むランで配列変数を更新する（ステップＳ９１２）。【選択図】  図８
2009076992.tif 000002
【特許請求の範囲】
【請求項１】
ラスタースキャン順に画素データを入力し、動的に更新される符号化パラメータに従ってランレングス符号化する画像符号化装置であって、
ランレングス符号化を行なうことで更新された前記符号化パラメータを特定する符号化履歴情報を、画素位置毎に記憶するための記憶手段と、
着目画素の位置からのランをランレングス符号化する際、前記着目画素の水平方向の位置と同じであって、１ライン前の画素位置の符号化履歴情報を前記記憶手段から取得する取得手段と、
前記取得手段で取得した符号化履歴情報で特定される前記符号化パラメータを前記ランの符号化の初期の符号化パラメータとし、当該初期の符号化パラメータを前記ランに応じて更新しながら、前記ランをランレングス符号化する符号化手段と、
前記符号化手段による前記ランの符号化を行なった後の前記符号化パラメータを特定する情報を、前記ランを構成する各画素の符号化履歴情報として前記記憶手段に格納する格納手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記記憶手段は、各画素位置毎に、それぞれの画素が属するランを前記符号化履歴情報として記憶することを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記記憶手段は、各画素位置毎に、ランレングス符号化した際の更新後の符号化パラメータを前記符号化履歴情報として記憶することを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
ラスタースキャン順に画素データを入力し、動的に更新される符号化パラメータに従ってランレングス符号化する画像符号化装置の制御方法であって、
ランレングス符号化を行なうことで更新された前記符号化パラメータを特定する符号化履歴情報を、画素位置毎に記憶するための記憶領域をメモリ内に確保する工程と、
着目画素の位置からのランをランレングス符号化する際、前記着目画素の水平方向の位置と同じであって、１ライン前の画素位置の符号化履歴情報を前記記憶領域から取得する取得工程と、
前記取得工程で取得した符号化履歴情報で特定される前記符号化パラメータを前記ランの符号化の初期の符号化パラメータとし、当該初期の符号化パラメータを前記ランに応じて更新しながら、前記ランをランレングス符号化する符号化工程と、
前記符号化工程による前記ランの符号化を行なった後の前記符号化パラメータを特定する情報を、前記ランを構成する各画素の符号化履歴情報として前記記憶領域に格納する格納工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項５】
コンピュータが読み込み実行することで、前記コンピュータを、請求項１乃至３のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項６】
ラスタースキャン順に画素データを入力し、動的に更新される符号化パラメータに従ってランレングス符号化又は予測符号化する画像符号化装置であって、
ランレングス符号化、予測符号化のいずれで符号化したのかを示す識別情報と、ランレングス符号化を行なうことで更新された前記符号化パラメータを特定する特定情報とで表わされる符号化履歴情報を、画素位置毎に記憶するための記憶手段と、
着目画素の近傍に位置し、既に符号化された複数の画素で表わされる色数が、予め設定された閾値以下であるか否かを判定する判定手段と、
前記判定手段で前記色数が前記閾値以下であると判定した場合、着目画素からのランを検出し、検出したランをランレングス符号化するランレングス符号化手段と、
前記判定手段で前記色数が前記閾値を超えると判定した場合、着目画素を予測符号化すると共に、前記着目画素が予測符号化されたことを示す識別情報を含む符号化履歴情報を前記記憶手段に格納する予測符号化手段とを備え、
前記ランレングス符号化手段は、
前記着目画素の位置からのランをランレングス符号化する際、前記着目画素の水平方向の位置と同じであって、１ライン前の画素位置の符号化履歴情報を前記記憶手段から取得する取得手段と、
前記取得手段で取得した符号化履歴情報に含まれる前記識別情報がランレングス符号化を示す場合には、取得した符号化履歴情報に含まれるの前記パラメータ特定情報で特定される符号化パラメータを初期の符号化パラメータとして決定し、
前記取得手段で取得した符号化履歴情報に含まれる前記識別情報が予測符号化を示す場合には、デフォルトの符号化パラメータを初期のパラメータとして決定する決定手段と、
前記決定手段で決定された初期の符号化パラメータを前記ランに応じて更新しながら、前記ランをランレングス符号化する符号化手段と、
前記符号化手段による符号化を行なった際、ランレングス符号化されたことを示す識別情報、及び、前記ランの符号化を行なった後の前記符号化パラメータを特定する情報を、前記ランを構成する各画素位の前記符号化履歴情報として、前記記憶手段に格納する格納手段と
を備えることを特徴とする画像符号化装置。
【請求項７】
前記記憶手段に記憶される前記パラメータ特定情報は、ランであることを特徴とする請求項６に記載の画像符号化装置。
【請求項８】
前記記憶手段に記憶される前記パラメータ特定情報は、ランレングス符号化した際の更新後の符号化パラメータとすることを特徴とする請求項６に記載の画像符号化装置。
【請求項９】
前記デフォルトの符号化パラメータは、着目画素の位置より前であって、最後にランレングス符号化した際の更新後の符号化パラメータとすることを特徴とする請求項６乃至８いずれか１項に記載の画像符号化装置。
【請求項１０】
ラスタースキャン順に画素データを入力し、動的に更新される符号化パラメータに従ってランレングス符号化又は予測符号化する画像符号化装置の制御方法であって、
ランレングス符号化、予測符号化のいずれで符号化したのかを示す識別情報と、ランレングス符号化を行なうことで更新された前記符号化パラメータを特定する特定情報とで表わされる符号化履歴情報を、画素位置毎に記憶するための記憶領域をメモリに確保する工程と、
着目画素の近傍に位置し、既に符号化された複数の画素で表わされる色数が、予め設定された閾値以下であるか否かを判定する判定工程と、
前記判定工程で前記色数が前記閾値以下であると判定した場合、着目画素からのランを検出し、検出したランをランレングス符号化するランレングス符号化工程と、
前記判定工程で前記色数が前記閾値を超えると判定した場合、着目画素を予測符号化すると共に、前記着目画素が予測符号化されたことを示す識別情報を前記記憶領域に格納する予測符号化工程とを備え、
前記ランレングス符号化工程は、
前記着目画素の位置からのランをランレングス符号化する際、前記着目画素の水平方向の位置と同じであって、１ライン前の画素位置の符号化履歴情報を前記記憶領域から取得する取得工程と、
前記取得工程で取得した符号化履歴情報に含まれる前記識別情報がランレングス符号化を示す場合には、取得した符号化履歴情報に含まれるの前記パラメータ特定情報で特定される符号化パラメータを初期の符号化パラメータとして決定し、
前記取得工程で取得した符号化履歴情報に含まれる前記識別情報が予測符号化を示す場合には、デフォルトの符号化パラメータを初期のパラメータとして決定する決定工程と、
前記決定工程で決定された初期の符号化パラメータを前記ランに応じて更新しながら、前記ランをランレングス符号化する符号化工程と、
前記符号化工程による符号化を行なった際、ランレングス符号化されたことを示す識別情報、及び、前記ランの符号化を行なった後の前記符号化パラメータを特定する情報を、前記ランを構成する各画素の前記符号化履歴情報として、前記記憶領域に格納する格納工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１１】
コンピュータが読み込み実行することで、前記コンピュータを、請求項６乃至９のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項１２】
請求項５又は１１に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの符号化技術に関するものである。
【背景技術】
【０００２】
従来、同じ値が連続している画素について、その連続数を符号化するランレングス符号化方式が広く一般的に知られている。
【０００３】
例えば、上記ランレングス符号化を用いる方式としては、国際標準方式であるＪＰＥＧ−ＬＳ（非特許文献１）が知られている。
【０００４】
図１はＪＰＥＧ−ＬＳにおけるランレングス符号化モードでの処理の流れを示すフローチャートである。
【０００５】
以下、同図に従ってＪＰＥＧ−ＬＳにおけるランレングス符号化の処理の流れについて説明をする。符号化時の画素のスキャン順はラスタースキャン順である。
【０００６】
ランレングス符号化モードに入る前に、ランの長さｎと、符号化対象であるランが画像端にかかっているかどうかを表すフラグｆは決まっているものとする。そして、ランインデックスの値Ｊとランインデックスによって変更する値Ｋとの関係を図２に示す。ランインデックスＪの初期値を“０”とするとＫの値は“０”となる。なお、フラグｆが“１”は、着目ランが画像の右端まで到達していることを示し、フラグｆが“０”の場合には、着目ランの終端位置が画像の右端に至っていないことを示す。
【０００７】
長さｎのランを符号化するとき、まずステップ１０１にて、ｎと２kを比較する（ステップＳ１０１）。ここで、ｎ＞２k（ＹＥＳ）ならば、ステップ１０２に進んで“１”（１ビット）を出力する。そして、ステップＳにて、ｎから２Ｋを減じた結果を新たなｎとする。つまり、ｎを更新する。この後、ステップＳ１０４にて、ランインデックスＪに１を足して、ランインデックスＪを更新し、ステップＳ１０１へと処理を戻す。
【０００８】
一方、ステップＳ１０１にて、ｎ≦２kであると判定した場合、処理はステップＳ１０５に進む。ステップＳ１０５では、着目しているランが画像端に掛かっているかどうかを示すフラグｆをチェックする。フラグｆが“０”であると判定した場合には、ステップＳ１０６にて、“０”（１ビット）を出力する。そして、ステップＳ１０７にて、ランの残りの長さをＫビットを使って符号化し出力する。そして、ステップＳ１０８にて、ランインデックスＪから１を引き更新する。
【０００９】
また、ステップＳ１０５にて、フラグｆが“０”以外（フラグｆが“１”）であると判定した場合、ステップＳ１０９に進み、ｎと“０”とを比較する。ｎ＞０であると判定した場合には、“１”を出力し、ｎ＝０であれば何もしないで処理を終了する。
【００１０】
次のランを符号化する際には、更新されているランインデックスの値を初期値として符号化を行うことで、動的にランインデックスが変化し、徐々にランの長さに適した値が割り当てられるようになる。
【特許文献１】ＩＴＵ−Ｔ  Ｔ．８７  ｜  ＩＳＯ／ＩＥＣ１４４９５−１
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記の如く、ＪＰＥＧ−ＬＳの符号化モードの一つにランレングス符号化モードがある。このランレングス符号化では、ランの長さに対して最適な符号が割り当てられるように、ランインデックス等の符号化パラメータを動的に変化させる方式を取っている。この方式の場合、同じような長さのランが連続していれば、次第に最適な符号が割り当てられ、符号量を最小限に抑えることができる。しかしながら、短いランと長いランが交互に発生するような画像の場合、ランインデックスが適当な値に収束せず、多くの符号を発生させてしまう場合がある。
【００１２】
本発明は係る課題に鑑みなされたものであり、符号化パラメータの変動を抑制するだけでなく、その符号化パラメータがランに適した値になる確率を高くすることで、高い圧縮率の符号化データを生成する符号化技術を提供しようとするものである。
【課題を解決するための手段】
【００１３】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
ラスタースキャン順に画素データを入力し、動的に更新される符号化パラメータに従ってランレングス符号化する画像符号化装置であって、
ランレングス符号化を行なうことで更新された前記符号化パラメータを特定する符号化履歴情報を、画素位置毎に記憶するための記憶手段と、
着目画素の位置からのランをランレングス符号化する際、前記着目画素の水平方向の位置と同じであって、１ライン前の画素位置の符号化履歴情報を前記記憶手段から取得する取得手段と、
前記取得手段で取得した符号化履歴情報で特定される前記符号化パラメータを前記ランの符号化の初期の符号化パラメータとし、当該初期の符号化パラメータを前記ランに応じて更新しながら、前記ランをランレングス符号化する符号化手段と、
前記符号化手段による前記ランの符号化を行なった後の前記符号化パラメータを特定する情報を、前記ランを構成する各画素の符号化履歴情報として前記記憶手段に格納する格納手段とを備える。
【発明の効果】
【００１４】
本発明によれば、符号化パラメータの変動を抑制するだけでなく、その符号化パラメータがランに適した値になる確率を高くし、高い圧縮率の符号化データを得ることが可能となる。
【発明を実施するための最良の形態】
【００１５】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１６】
［第１の実施形態］
図８は本実施形態に係る画像符号化装置の基本構成を示す図である。
【００１７】
１４０１は装置全体の制御を司る制御部として機能するＣＰＵである。１４０２はＣＰＵ１４０１が実行するプログラムを格納したり、ワークエリアとして使用するＲＡＭである。１４０３は、ＢＩＯＳやブートプログラムを格納しているＲＯＭである。１４０４はキーボード、１４０５はポインティングデバイスであるマウスである。１４０６は表示装置であり、ＣＲＴやＬＣＤ等の表示デバイスで構成される。１４０７はハードディスク装置等に代表される大容量の外部記憶装置であり、ここにＯＳや実施形態に係る符号化／復号処理のプログラムが格納されている。また、この外部記憶装置１４０７は、各種データファイルを格納するためにも利用される。１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化処理の為のプログラム、符号化対象画像データをファイルとして記録しても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、そのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【００１８】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えはＩ／Ｆ１４０９を介して符号化対象となる画像データを本装置の本装置のＲＡＭ１４０２や外部記憶装置１４０７に入力することや、逆に、本装置のＲＡＭ１４０２や外部記憶装置１４０７から生成した画像符号化データを装置外部に出力することができる。１４１０は上述の各部を繋ぐバスである。
【００１９】
上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードし、実行する。この結果、本装置は情報処理装置として機能する。更に、ユーザがマウス１４０５を操作して、画像符号化／復号の開始指示を行なうと、ＣＰＵ１４０１は該当するアプリケーションプログラムを外部記憶装置１４０７からＲＡＭ１４０２にロードし、実行する。この結果、本装置が画像符号化装置、或いは、画像復号装置として機能することになる。
【００２０】
以下は、画像符号化アプリケーションを実行し、本装置が画像データを可逆符号化する画像符号化装置として機能する場合の説明である。
【００２１】
説明を簡単なものとするため、符号化対象の画像データのサイズは水平方向Ｗ画素、垂直方向Ｈ画素であるものとする。また画素は、Ｒ、Ｇ、Ｂの３つの輝度成分で表わされ、それぞれは８ビット（２５６階調）であるのとする。また、符号化対象の画像データを入力する順序は点順次、即ち、ラスタースキャン順であって、その各画素を構成するデータがＲ，Ｇ，Ｂの順番に並べられているものとする。なお、色空間の種類はＲＧＢに限らず、ＹＭＣＫでも構わないし、その色空間の種類でも良いし、成分の数は問わない。モノクロ画像であれば１成分（濃度、又は輝度）となる。
【００２２】
また、符号化対象の画像データの発生源は、外部記憶装置１４０７（画像データファイル）、インタフェース１４０９に接続されたイメージスキャナ、或いは、印刷データ等のデータをレンダリング処理した結果でも構わず、その種類も問わない。また、符号化されたデータは、外部記憶装置１４０７に圧縮ファイルとして格納（出力）するものとするが、その出力対象の種類も問わない。
【００２３】
さて、本実施形態では、符号化処理を開始にするに先立ち、画像の１ライン分、すなわち、水平方向の画素の数Ｗに相当する配列変数Ｄ（ｘ，Ｃ）をＲＡＭ１４０２の予め設定された記憶領域に確保する。なお、ここでは配列変数Ｄ（，）はＲＡＭ１４０２に確保する例を示しているが、ハードディスク等の書き換え可能なメモリ内であればその種類は問わない。
【００２４】
ここで変数ｘは、水平方向の画素位置を特定するものであり、変数ｘの取り得る範囲は０≦ｘ≦Ｗ−１である。つまり、この配列変数は座標ｘで示される画素位置毎に情報を保持する変数と言える。引数Ｃは、０、１のいずれかの値である。Ｄ（ｘ，０）には、符号化の種類を識別する識別情報を格納する。実施形態における符号化の種類はパラメータＪ，Ｋを用いるランレングス符号化と、予測符号化の２種類である。また、Ｄ（ｘ，１）には、ランレングス符号化された際のラン（連続する画素数）を格納する。
【００２５】
例えば、Ｄ（ｘ、０）が“０”の場合、水平方向の座標ｘの画素は、ランレングス符号化されていることを示す。Ｄ（ｘ，１）で示される値は、そのランを示す。また、Ｄ（ｘ，０）が“１”の場合、水平方向の座標ｘの画素は、予測符号化されていることを示す。
【００２６】
以下の説明において、符号化しようとする座標（ｘ，ｙ）の着目画素をＸｉと表現する。上記配列変数Ｄ（，）を、着目画素Ｘｉの１ライン前の座標（ｘ，ｙ−１）の画素の符号化履歴を判定するために用いる。すなわち、着目画素Ｘｉの１ライン前の座標（ｘ，ｙ−１）の符号化種別を、Ｄ（ｘ，０）に従って判定する。また、着目画素Ｘｉの１ライン前の座標（ｘ，ｙ−１）の符号化種別がランレングス符号化されている場合には、Ｄ（ｘ，１）の値を調べることで、そのランが幾つであったのか判定する。
【００２７】
本実施形態では、着目画素Ｘｉがランレングス符号化対象の画素であった場合、１ライン前の画素の符号化履歴から、着目画素Ｘｉを含むランを符号化する際のパラメータＪ、Ｋを決定し、符号化するものである。
【００２８】
以下、図３のフローチャートに従って、実施形態における符号化処理手順を説明する。なお、符号化を開始にするに先立ち、外部記憶装置１４０７には出力ファイルのヘッダを格納する。このヘッダには、画像データの水平、垂直方向の画素数（サイズ情報）、色空間の種類、色成分のビット数等、復号に必要なデータを格納する。以下の説明で生成される符号化データは、このヘッダに後続するデータとして格納されるものである。
【００２９】
まず、ステップＳ３０１にて、ＲＡＭ１４０２に配列変数Ｄ（，）を確保し、その配列変数の値を初期化する。初期化処理では、Ｄ（，０）＝０、Ｄ（，１）＝０とする。つまり、全てがランレングス符号化され、ランが“０”であるものとして設定する。但し、この初期値は、復号装置と同じようにすれば良く、上記の初期値でもって本発明が限定されるものではない。
【００３０】
次いで、ステップＳ３０２にて、垂直方向の座標を示す変数ｙを“０”で初期化し、ステップＳ３０３にて、水平方向の座標を示す変数ｘを“０”で初期化する。
【００３１】
この後、処理はステップＳ３０４に進み、座標（ｘ，ｙ）で示される着目画素Ｘｉの近傍に位置する４つの近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄが互いに同じ色であるかを判定する。言い替えれば、ステップＳ３０４では、近傍画素｛Ｘａ，Ｘｂ，Ｘｃ，Ｘｄ｝の色数が“１”であるか否かを判定している、とも言える。
【００３２】
着目画素Ｘｉと近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄとの相対位置関係は図４に示す通りである。すなわち、近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄは、着目画素の近傍の符号済みの画素である。なお、着目画素Ｘｉが画像の境界位置にあるとき、近傍画素Ｘａ、Ｘｂ、Ｘｃ、Ｘｄの全て、若しくはその幾つかが画像外に位置することになる。このように画像外に位置する近傍画素は、その成分Ｒ、Ｇ、Ｂは“０”と見なす。ただし、この値は、復号装置と共通にすれば良いので、これによって本発明が限定されるものではない。
【００３３】
４つの近傍画素が互いに等しい場合（色数が“１”である場合）、着目画素Ｘｉが近傍画素Ｘａと等しくなる確率が非常に高い。そこで、処理はステップＳ３０５に進み、ランレングス符号化処理を行なう（詳細は後述）。この後、処理はステップＳ３０９に進む。
【００３４】
一方、ステップＳ３０４にて、４つの近傍画素が表わす色数が２以上であると判定した場合、処理はステップＳ３０６に進み、着目画素Ｘｉを構成する各色成分毎に予測符号化し、その符号化データを出力する。この予測符号化処理は、本実施形態では、ＪＰＥＧ−ＬＳに規定されている手順に従うものとする。一例を示すのであれば、次の通りである。
【００３５】
以下は着目画素Ｘｉの色成分Ｒを符号化する場合について説明する。Ｇ成分については、符号化対象がＲ成分からＧ成分に代わるだけである。Ｂ成分も同様である。
【００３６】
着目画素ＸｉのＲ成分、近傍画素Ｘａ，Ｘｂ，ＸｃのＲ成分を仮に、Ｘｉ（Ｒ）、Ｘａ（Ｒ），Ｘｂ（Ｒ），Ｘｃ（Ｒ）と表現する。先ず、着目画素のＲ成分の予測値Ｐを求める。ＪＰＥＧ−ＬＳでは、予測値Ｐを求めるために、幾つかの式が定義されている。ここでは、簡単のため、予測値Ｐを以下のようにしても求めるものとする。
Ｐ＝Ｘａ（Ｒ）＋Ｘｂ（Ｒ）−Ｘｃ（Ｒ）
【００３７】
次に、着目画素のＲ成分であるＸｉ（Ｒ）と予測値Ｐとの予測誤差ｅを算出する。
ｅ＝Ｘｉ（Ｒ）−Ｐ
【００３８】
この後、この予測誤差ｅをエントロピー符号化（例えば、ハフマン符号化、Ｇｏｌｏｍｂ符号化、算術符号化等）し、その符号語（符号化データ）を出力する。
【００３９】
上記のようにして、着目画素ＸｉのＲ成分の符号化データを生成し、出力すると、着目画素ＸｉのＧ成分、Ｂ成分についても同様に処理することにより、着目画素Ｘｉの全色成分の符号化処理を行なう。
【００４０】
この後、着目画素Ｘｉが予測符号化されたことを示すため、ステップＳ３０７にて、着目画素のｘ座標で特定される配列変数Ｄ（ｘ，０）に“１”を格納する。
【００４１】
また、予測符号化は、１画素単位に符号化することになるので、ステップＳ３０８では、変数ｘを“１”だけ増加させ、ステップＳ３０９に処理を進める。
【００４２】
ステップＳ３０９では、変数ｘと変数Ｗとを比較する。ｘ＜Ｗであると判定した場合、着目画素Ｘｉの位置は右端位置に到達していないことになるので、ステップＳ３０４に処理を戻す。
【００４３】
また、ステップＳ３０９にて、ｘ＝Ｗと判定された場合、処理はステップＳ３１０に進み、変数ｙを“１”だけ増加させ、処理をステップＳ３１１に進める。
【００４４】
ステップＳ３１１では、変数ｙと変数Ｈとを比較する。ｙ＜Ｈであると判定した場合、着目画素は最終ライン上にないことになるので、ステップＳ３０３以降の処理を行なう。また。ｙ＝Ｈであると判断した場合には、画像データの全画素について符号化が完了したことになるので、本処理を終える。
【００４５】
次に、上記のステップＳ３０５のランレングス符号化処理の詳細を、図９のフローチャートに従って説明する。なお、以下の説明において、着目画素Ｘｉの座標は、図３の処理で利用される変数ｘ、ｙによって特定されることに注意されたい。
【００４６】
先ず、ステップＳ９０１にて、ランを計数するための変数ＲＬ、及び、フラグｆをそれぞれ“０”で初期化する。
【００４７】
次いで、ステップＳ９０２に進み、変数Ｄ（ｘ、０）を調べ、着目画素Ｘｉの１ライン前の画素、すなわち、座標（ｘ，ｙ−１）の画素がランレングス符号化されているのか、予測誤差符号化されているのかを判定する。
【００４８】
着目画素Ｘｉの１ライン前の画素がランレングス符号化されていると判定した場合には、ステップＳ９０３に進む。ステップＳ９０３では、着目画素Ｘｉの１ライン前の画素のランを変数Ｄ（ｘ，１）を読出すことで取得する。そして、このＤ（ｘ，１）の値に従って、着目画素のランレングス符号化を行なうための初期のパラメータＪ，Ｋを決定する。これらパラメータＪ，Ｋを求め方は、以下の通りである。
【００４９】
説明を簡単なものとするため、今、着目画素Ｘｉが図５の“＊”位置にあるものとする。なお、図５は白地に黒色の垂直線が存在する例を示している。着目画素Ｘｉが存在するライン上の着目画素Ｘｉよりも左側、及び、着目画素Ｘｉより上のラインは符号化済みの領域である点に注意されたい。
【００５０】
この符号化済み領域において、符号化種類が予測符号化（Ｄ（，０）＝１）であった画素を“Ｒ”、ランレングス符号化（Ｄ（，０）＝０）であれば、そのランを示す数値（Ｄ（，１））で表現すると、図５の画像は図６のように表現できる。図６において“−”の画素は、着目ライン上の着目画素Ｘｉよりも左側にある画素の符号化処理によって、Ｄ（，）が上書きされたことを示している。
【００５１】
図６から、着目画素Ｘｉの１ライン前の画素（座標（ｘ，ｙ−１））の符号化の種別はランレングス符号化であって、ランが“４”であることがわかる。本実施形態では、このラン“４”を２q＋ｍで表わした際の指数ｑを求める。数値“４”は２2＋０であるから、指数ｑは“２”となる。実際は、このような複雑な演算は不要である。すなわち、ランを二進表現した際、ＭＳＢからＬＳＢに向かって最初に“１”に現れるビット位置をｑとして求めればよい。そして、求めたｑをパラメータＫとして決定する。
【００５２】
また、パラメータＪの求め方は次の通りである。
【００５３】
先ず、図２のテーブルを左から右側に調べ、決定したパラメータＫと同じ値が最初に見つかった位置のランインデックス値を、パラメータＪとして決定する。図２の場合、最初にＫ＝２となるのは、ランインデックス値が“８”であるので、パラメータＪは“８”として決定する。
【００５４】
以上が、ステップＳ９０３におけるパラメータＪ，Ｋの決定手順である。
【００５５】
一方、ステップＳ９０２にて、着目画素Ｘｉの１ライン前の画素、すなわち、座標（ｘ，ｙ−１）の画素が予測符号化されている場合（Ｄ（ｘ，０）＝１の場合）には、ステップＳ９０４に進む。この棄て追う９０４で、配列変数Ｄ（，）を参酌せず、デフォルトの値をパラメータＫ，Ｊに設定する。デフォルトの値は、復号装置との間で同一の値であれば良い。本実施形態では、パラメータＫ，Ｊは共に“０”であるものとして決定する。
【００５６】
上記のようにしてパラメータＪ，Ｋが求まると、処理はステップＳ９０５に進み、ランの検出と符号化処理を行なうことになる。
【００５７】
先ず、このステップＳ９０５では、着目画素Ｘｉと、その直前の画素Ｘａとが同じ色であるか否かを判定する（ここで、画素Ｘａの座標は（ｘ−１，ｙ）である）。また、２つの画素が同じ色であるというのは、それら２つの各成分の値が互いに等しい場合である。
【００５８】
着目画素Ｘｉと画素Ｘａが等しいと判定した場合には、ステップＳ９０６に進み、変数ＲＬを“１”だけ増加させる。そして、着目画素Ｘｉの位置を更新するため、ステップＳ９０７にて、変数ｘを“１”だけ増加させる。この後、ステップＳ９０８に進み、変数ｘと変数Ｗとを比較する。ｘ＜Ｗである場合、着目画素は画像の右端に到達していないことを示すので、ステップＳ９０５の処理に戻る。一方、変数ｘと変数Ｗが等しいと判断した場合、着目画素は画像の右端に位置することを示すので、フラグｆに“１”をセットし、ステップＳ９１０に処理を進める。
【００５９】
上記のステップＳ９０５乃至ステップＳ９０８のループは、同じ色の画素の連続数、すなわち、ランを求めていることに他ならない。
【００６０】
さて、ステップＳ９０５にて、着目画素Ｘｉとその直前の画素Ｘａとが異なる色であると判定された場合、又は、ステップＳ９０８にて、同じ色が連続したまま着目画素が画像の右端位置まで到達したと判断した場合、処理はステップＳ９１０に進む。
【００６１】
この後、ステップＳ９１０にて、変数ｎに変数ＲＬの値を代入し、ステップＳ９１１にて変数ｎのランレングス符号化を行なう。このステップＳ９１１におけるランレングス符号化処理の内容は、図１のフローチャートで示した通りであるので、その説明は省略する。なお、図１では符号化対象のランを変数ｎで表わしている。この理由で、ステップＳ９１０では便宜的に変数ｎに変数ＲＬの値を格納している。
【００６２】
ステップＳ９１２では、着目画素Ｘｉが存在するラインの次のラインの符号化処理に備えて、ランの最初の画素位置から、ＲＬ個分の配列変数Ｄ（，）を更新する処理を行なう。符号化したランの先頭のｘ座標をｘｓで表わすと、
Ｄ（ｘｓ，０）、Ｄ（ｘｓ＋１，０）、…、Ｄ（ｘｓ＋ＲＬ−１、０）それぞれを“０”を格納する。言い替えれば、水平方向の座標ｘｓの画素位置からＲＬ個の範囲の画素群がランレングス符号化されたことを示す履歴情報を配列変数Ｄ（，）に格納し、更新する。また、同様に、Ｄ（Ｘｓ，１）、Ｄ（Ｘｓ＋１，１）、…、Ｄ（Ｘｓ＋ＲＬ−１、１）には、変数ＲＬの値（着目画素を含むラン）を格納する。
【００６３】
なお、図３のフローチャートにおいて、ステップＳ３０４にてＹｅｓと判断され、図９のフローチャートに従った処理を開始した最初のステップＳ９０５にて、着目Ｘｉと直前画素Ｘａが等しくない、と判定されることも起こりえる。この場合、ラン“０”を符号化して出力することになる。ラン“０”の場合、着目画素Ｘｉは、図９の処理では符号化対象とはならず、図３の処理にて予測符号化されることになる。
【００６４】
以上説明した様に本実施形態に従えば、着目画素Ｘｉを含むランを符号化する際の初期パラメータＪ，Ｋを、着目画素Ｘｉの１つ前のラインの画素の符号化履歴に従って決定する。これにより、パラメータの変動を抑制すると共に、ランに最適なパラメータを維持する確率を高め、圧縮効率を向上させることが可能となる。
【００６５】
なお、実施形態では、画像の符号化を開始した際の最初のラインでは、初期値で初期化した配列変数Ｄ（，）を用いて符号化するものとして説明した。しかしながら、これによって本発明が限定されるものではない。すなわち、画像の最初のラインについては従来の同様の処理を行ない、パラメータＪ、Ｋを更新しても良い。但し、この場合にも、符号化済みとなった画素位置に対応する配列変数Ｄ（，）を、その際に用いた符号化種別を示す情報、ランレングス符号化したのであればそのランを示す情報の符号化履歴情報で更新することになる。
【００６６】
また、上記実施形態では、着目画素Ｘｉを含むランを符号化する際に、着目画素Ｘｉの１ライン前の画素の符号化種類が予測誤差符号化であった場合、デフォルトの値を用いるものとして説明した（図９のステップＳ９０４）。しかし、このデフォルトの値を用いる代わりに、直前のランの符号化処理で更新されたパラメータＪを用いても構わない。
【００６７】
さらにまた、実施形態では、ランレングス符号化と予測誤差符号化を用いる例を説明したが、ランレングス符号化のみを用いるようにしても構わない。この場合、符号化の種類は１種類だけとなるので、配列変数Ｄはランのみを格納すればよい。
【００６８】
また、実施形態では、ランレングス符号化を開始する条件が、着目画素Ｘｉの近傍の４つの画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄが互いに等しい、すなわち、近傍４画素が示す色数が“１”である例を説明した。しかしながら、近傍画素が表わす最大色数よりも十分に小さい値の候補、例えば｛１，２｝の中からユーザが閾値を１つ選択できるようにしても構わない。この場合、近傍画素の色数が閾値以下の場合に、ランレングス符号化を行なうように、閾値を超える場合には予測符号化を行なう。ただし、閾値はユーザが選択することになるので、生成される符号化データファイルのヘッダに、その閾値を特定する情報を格納することが必要である。
【００６９】
また、上記実施形態の画像符号化装置で生成された符号化画像データを復号する場合には、上記と逆の処理を行なえばよい。着目画素が、符号化対象の画像データの最初の画素（画像の左上隅の位置の画素）である場合、着目画素がランレングス符号化される。なぜなら、その画像外の近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄが共に同じ色であるものとして判定されるからである。しかしながら、この最初の画素を除けば、基本的に、１つのランレングス符号化データの前には予測符号化データが位置する。それ故、予測符号化データを復号して得られた画素データを仮にＸｐとしたとき、ランレングス符号化データを復号したランで示される数分の画素データＸｐを出力すればよい。
【００７０】
また、上記実施形態では、配列変数Ｄ（，）の引数を２つの例で示したが、ＱビットのＭＳＢを符号化種別を示す情報を格納し、残りのＱ−１ビットをランを格納する領域として用いてもかまわない。
【００７１】
また、実施形態では、ランレングス符号化処理を図１に示した手順に従い行なうものとしたが、符号化の種類はこれに限定されるものではない。すなわち、動的にパラメータを変更もしくは更新して符号化するものであれば良い。例えば、ランＲＬを、動的パラメータＫを用いてＧｏｌｏｍｂ符号化する場合にも適用しても良いであろう。
【００７２】
［第２の実施形態］
上記第１の実施形態では、着目画素Ｘｉの１ライン前の画素の履歴情報のパラメータ特定情報（第１の実施形態ではラン）を参照してパラメータＪ，Ｋを決定した。しかしながら、着目画素Ｘｉの１ライン前の画素のランインデックス値そのものを着目画素をランレングス符号化する際にランインデックス値として適用しても構わない。
【００７３】
この場合、図９のステップＳ９１２では、配列変数Ｄ（ｘ，１）には、ランではなく、ランレングス符号化した際の更新後のラインインデックス値である変数Ｊを格納するようにすればよい。
【００７４】
また、図９のステップＳ９０３では、Ｄ（ｘ，１）からランインデックス値を取得し、それがパラメータＪの値であるとして決定すればよい。パラメータＪが決定されると、図２のテーブルからパラメータＫを一義的に決定できる。
【００７５】
［第３の実施形態］
本第３の実施形態では、複数画像を合成して作成されたような画像に対して、領域情報を用いて、参照するランインデックスの値を変更する例を説明する。
【００７６】
例えば、前景と背景の領域情報が与えられているような２種類の属性を持つ画像の場合には、前景と背景を別々に符号化する。ランインデックスの値も画像領域によってそれぞれ違う値をとるので、動的に追従させていった場合、最適なランインデックス値を割り当てることができる。
【００７７】
具体的には、図７のような画像の場合、グレーの部分が前景画像、その他が背景画像の属性を持つ。背景画像は真っ白のベタ画像となり、ランレングス符号化方式による符号化効率の向上が見込まれる。前景画像に関しても、ランの長さが極端に変動することがなくなるので、符号化効率を改善することが可能となる。
【００７８】
これを実現するには、画像をラスタースキャンして符号化する際に、各画素の属性（２つの属性にて切り替えるあれば１ビットで良い）を入力し、その入力した属性を示す情報に基づき、参照する履歴情報を切り替えればよい。具体的には、配列変数Ｄ（ｘ，Ｃ，Ａｔｒ）のように３つの引数で表わし、変数Ａｔｒを属性とみなし、これによって２種類の履歴情報を利用すればよいであろう。
【００７９】
この結果、図７に示される１つの自然画ブロック中の最後のラインの次のラインを符号化する場合には、その自然画ブロックの最初のラインよりも１つ前のラインの符号化履歴情報を参照することも可能になる。
【００８０】
なお、符号化対象の画像データとしては、ＰＤＬ形式の印刷データを受信してレンダリングした画像が好適である。レンダリング処理を行なうレンダリング部は、印刷データに基づいて文字パターンや線画の描画をページメモリに行ない、印刷データ中に含まれる自然画もページメモリに展開することになる。従って、レンダリング部は、ページメモリに対応する属性メモリを備えるようにする。１ページのレンダリングを開始する際には属性メモリに対して全ての画素が文字線画の属性を持つものとして初期化する。そして、その後で、自然画をページメモリに展開した際には、属性メモリの該当する領域の属性を自然画を示すように書き換えればよい。そして、レンダリング部が１ページのレンダリングを終えたところで、ページメモリの画像データと、属性メモリのデータとを本装置に出力すればよい。この結果、画素単位に属性を判別することができ、属性毎に符号化パラメータを切り替えることが可能になる。
【００８１】
また、上記実施形態では、符号化対象の画像データのサイズは水平方向画素数Ｗ、垂直方向の画素数Ｈとし、その画像データをラスタースキャンして符号化する例を説明した。しかしながら、この画像データからユーザが不図示の操作部で設定したｍ×ｎ（ｍ，ｎは２以上の値）画素のブロックを単位に入力し、符号化しても構わない。この場合、Ｗをｍ、Ｈをｎと読み代えて、各ブロック単位に符号化するだけで良い。
【００８２】
［他の実施形態］
第１や第２の実施形態では、着目画素の１ライン前の画素のランの長さや、ランインデックス値を参照して、ランレングス符号化を行ったが、参照する画素は、着目画素の１ライン前の画素でなくてもよい。
【００８３】
例えば、図１０のような画像の場合は、白い画素をランレングス符号化する際に第１の実施形態のように１ライン前の画素のラン長やランインデックス値を参照してランインデックスの値を決定すると、最適なランインデックス値は割り当てられず符号量が増加してしまう可能性がある。このような画像の場合には、１回目に出てくるランの長さ又はランインデックスと、２回目に出てくるランの長さ又はランインデックスを保存しておき、ランインデックス値の変動を見て、参照するランの長さ又はランインデックスの値を、着目画素の上のランから参照するか、別のランから参照するかどうかを判定し、適用する。こうすることで、符号量の抑制ができる。
【００８４】
以上、本発明に係る実施形態を説明した。上記実施形態では、パーソナルコンピュータ等の汎用情報処理装置上で実行するアプリケーションで実現する例を説明したが、同様の処理をハードウェアにて行なっても構わない。
【００８５】
また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それを読取り装置（ＣＤ−ＲＯＭドライブ）にセットし、そのプログラムをシステムにコピーもしくはインストールすることで実行可能になる。それ故、かかるコンピュータ可読記憶媒体も本発明の範疇に入ることは明らかである。
【図面の簡単な説明】
【００８６】
【図１】従来のランレングス符号化処理の流れを示すフローチャートである。
【図２】ランインデックス値とパラメータＫの対応テーブルを示す図である。
【図３】第１の実施形態の符号化処理のメイン処理を示すフローチャートである。
【図４】着目画素Ｘｉとその近傍画素Ｘａ，Ｘｂ，Ｘｃ，Ｘｄの相対位置関係を示す図である。
【図５】実施形態のける符号化対象の画像の一例を示す図である。
【図６】図５の画像中の着目画素の近傍に位置する符号化履歴情報の例を示す図である。
【図７】第３の実施形態が適用する画像の例を示す図である。
【図８】実施形態の画像符号化装置のブロック構成図である。
【図９】図３のステップＳ３０５の詳細を示すフローチャートである。
【図１０】変形例の符号化対象の画像の一例を示す図である。
【図１】
2009076992.tif 000003
【図２】
2009076992.tif 000004
【図３】
2009076992.tif 000005
【図４】
2009076992.tif 000006
【図５】
2009076992.tif 000007
【図６】
2009076992.tif 000008
【図７】
2009076992.tif 000009
【図８】
2009076992.tif 000010
【図９】
2009076992.tif 000011
【図１０】
2009076992.tif 000012