(57)【要約】【課題】原画像データをより効率良くランレングス符号化する。【解決手段】色コード割当部１３は、原画像データを色コードとランレングスとでコード化し、ランレングスコードを生成し、ランレングスコードを構成する各色コードにつき、各ランのランレングスのヒストグラムを算出し、算出したヒストグラムに基づいて、ある色コードが割り当てられたランの一部を抽出し、未使用の色コードに割り当てる。符号化部１４は、色コード割当部１３による割り当てが終了した後、各色コードにつき、全ランの符号化結果が最小となるビット数を長さ部のビット数として求め、各ランを符号化する。【選択図】図１
2012249061.tif 000002
【特許請求の範囲】
【請求項１】
所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とで各ランを表すランレングスデータに原画像データを符号化するランレングス符号化装置であって、
前記原画像データを色コードとランレングスとでコード化し、ランレングスコードを生成し、前記ランレングスコードを構成する各色コードにつき、各ランのランレングスのヒストグラムを算出し、算出したヒストグラムに基づいて、ある色コードが割り当てられたランの一部を抽出し、未使用の色コードに割り当てる色コード割当部と、
前記色コード割当部による割り当てが終了した後、各色コードにつき、全ランの符号化結果が最小となるビット数を前記長さ部のビット数として求め、各ランを符号化する符号化部とを備えるランレングス符号化装置。
【請求項２】
前記符号化部は、
各色コードにつき、ランレングスの最小値をベース値として算出するベース値算出部と、
各ランにつき、ランレングスから対応する色コードのベース値を差し引き、各ランの差分ランレングスを算出する差分ランレングス算出部と、
各色コードにつき、全ランの差分ランレングスを表すことができる最小のビット数を前記長さ部のビット数として求め、各ランを符号化する差分ランレングス符号化部とを備える請求項１記載のランレングス符号化装置。
【請求項３】
前記符号化部は、各色コードにつき、前記ベース値を、前記長さ部のビット数と対応付けてベース値テーブルを生成するベース値テーブル生成部を更に備える請求項２記載のランレングス符号化装置。
【請求項４】
前記色コード割当部は、前記ヒストグラムからランレングスに複数の偏りがある色コードを特定し、特定した色コードに対し、同じ偏りに属するランを抽出し、前記未使用の色コードを割り当てる請求項１〜３のいずれかに記載のランレングス符号化装置。
【請求項５】
前記色コード割当部は、各色コードにつき、前記長さ部のビット数の分割位置を変えながら符号長の削減量を算出し、前記削減量を最大化する分割位置を持つ色コードを、前記複数の偏りがある色コードとして特定し、特定した色コードにおいて、前記削減量を最大化する分割位置より大きなビット数で表されるランレングスを持つランを抽出し、前記未使用の色コードを割り当てる請求項４記載のランレングス符号化装置。
【請求項６】
所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とを用いて各ランを表すランレングスデータを原画像データに復号化するランレングス復号化装置であって、
前記長さ部は、各ランのランレングスから各ランのベース値を差し引いた差分ランレングスを格納し、
前記ベース値は、各色コードにおけるランレングスの最小値を示し、
各色コードにつき、前記ベース値と前記長さ部のビット数とが対応付けられたベース値テーブルを保持するベース値テーブル保持部と、
各色コードをビットマップ形式で表すための色情報を保持する色情報保持部と、
前記ランレングスデータから色コードを特定し、特定した色コードに対応する前記長さ部のビット数を前記ベース値テーブルから特定し、特定したビット数分の前記色コードに続く前記ランレングスデータを差分ランレングスとして抽出する差分ランレングス抽出部と、
前記差分ランレングス抽出部により抽出された差分ランレングスに対応するベース値を加算し、ランレングスを算出する加算部と、
前記加算部により算出されたランレングス及び前記色情報に基づいて前記ランレングスデータを前記原画像データに復号化する復号化部とを備えるランレングス復号化装置。
【請求項７】
所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とで各ランを表すランレングスデータに原画像データを符号化するランレングス符号化方法であって、
前記ランレングス符号化装置が、前記原画像データを色コードとランレングスとでコード化し、ランレングスコードを生成し、前記原画像データを構成する各色コードにつき、各ランのランレングスのヒストグラムを算出し、算出したヒストグラムに基づいて、ある色コードが割り当てられたランの一部を抽出し、未使用の色コードに割り当てる色コード割当ステップと、
前記ランレングス符号化装置が、前記色コード割当ステップによる割り当てが終了した後、各色コードにつき、全ランの符号化結果が最小となるビット数を前記長さ部のビット数として求め、各ランを符号化する符号化ステップとを備えるランレングス符号化方法。
【請求項８】
所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とを用いて、各ランを表すランレングスデータをランレングス復号化装置が原画像データに復号化するランレングス復号化方法であって、
前記長さ部は、各ランのランレングスから各ランのベース値を差し引いた差分ランレングスを格納し、
前記ベース値は、各色コードにおけるランレングスの最小値を示し、
前記ランレングス復号化装置は、
各色コードにつき、前記ベース値と前記長さ部のビット数とが対応付けられたベース値テーブルを保持するベース値テーブル保持部と、
各色コードを前記原画像データで表すための色情報を保持する色情報保持部とを備え、
前記ランレングス復号化装置が、前記ランレングスデータから色コードを特定し、特定した色コードに対応する前記長さ部のビット数を前記ベース値テーブルから特定し、特定したビット数分の前記色コードに続く前記ランレングスデータを差分ランレングスとして抽出する差分ランレングス抽出ステップと、
前記差分ランレングス抽出ステップにより抽出された差分ランレングスに対応するベース値を加算し、ランレングスを算出する加算ステップと、
前記加算ステップにより算出されたランレングス及び前記色情報に基づいて前記ランレングスデータを前記原画像データに復号化する復号化ステップとを備えるランレングス復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ランレングス符号化に関する技術である。
【背景技術】
【０００２】
ランレングス符号化は、画像の内容にもよるが、適した画像であれば、圧縮率が高い、ロスレス圧縮である、及びハードウェア化した場合の回路規模が小さいといった特徴があり、ＦＡＸ等で広く使用されている。ランレングス符号化の概要に関しては例えば特許文献１、２に記述されている。
【０００３】
カメラにおいても、画像に重畳して出力するＯＳＤ（オンスクリーンディスプレイ）表示パターンをカメラ内に保持するといった用途でランレングス符号化を適用することができる。これは、予め決まったＯＳＤパターンを表示するのであれば、ＯＳＤ表示パターンを予めランレングス符号化してランレングスデータとして保持しておき、そのランレングスデータを表示タイミングに合わせてリアルタイムで復号化する方が、フレームバッファ用のＲＡＭが不要で、低コストになるためである。つまり、ランレングス符号化は、圧縮ロスが小さく、復号化回路の回路構成が簡単、かつ、リアルタイム処理が可能といった特徴を持つため、このような用途に適している。
【０００４】
ＯＳＤ表示パターンをランレングス符号化する場合、符号化するパターンは予め分かっているため、画像全体の特徴から符号化のパラメータを最適化することが可能である。
【０００５】
カラー表示されるＯＳＤ表示パターンは、自然画像とは異なり使用する色数は限定される場合が多い。したがって、ＯＳＤ表示パターンをランレングス符号化する場合、色コードを用いて各色が表され、使用する色数に応じて、色コードのビット数が設定される。そして、各色コードと、各色コードをディスプレイで表示するための色情報とが対応付けられた色コードテーブルを用いて、各色コードが色情報に変換され、ランレングスデータがＯＳＤ表示パターンに復号化される。
【０００６】
図２９（Ａ）は、８×８のＯＳＤ表示パターンをランレングス符号化した一例である。図２９（Ａ）において、各グリッドは画素を表し、各グリッド内の数字は各画素の色コードを示している。図２９（Ｂ）は図２９（Ａ）に示すＯＳＤ表示パターンを色コードとランレングスとでコード化して得られたランレングスコードである。
【０００７】
このランレングスコードは、Ａ、Ｂ等のアルファベットがランの色コード（Ａ：色コード０、Ｂ：色コード１、．．．）を示し、それに続く数字がそのランのランレングスを１０進数で示している。例えば、最初の“Ｂ１８”は色コードが１、ランレングスが１８のランを示している。また、“Ｂ１８”の次の“Ａ５”は色コードが０、ランレングスが５のランを示している。
【０００８】
ランレングス符号化では、水平ラインごとにランを区切って、次の水平ラインは新しいランとする場合もあるが、図２９の例では水平ラインが変わる場合もランは区切らず、連続したランとして符号化している。このようにしても、復号化の際に水平画素数を指定することで正しい復号化が可能である。
【０００９】
ランレングスコードをビットパターンで表したランレングスデータは、色コード部及び長さ部のそれぞれに所定のビット数が割り当てられたビットパターンで表される。色コード部のビット数は使用する色数で決まり、長さ部のビット数はランレングスデータの符号長を最小にすることができる値が採用される。使用する色数が８色の場合、色コード部のビット数は３ｂｉｔとなる。また、長さ部のビット数をｍ、各ランのランレングスを０〜２ｍ−１としたときの、長さ部のビット数と色コード部のビット数との関係は図３０のようになる。
【００１０】
図３０は、図２９のランレングスコードについて、色コード部のビット数を３として、長さ部のビット数を変えたときの色コード毎のランレングスデータの符号長である。
【００１１】
図３０において１行目には、１、８８、１６８が格納されている。これは、ｍ＝１として図２９のランレングスコードをビットパターンで表した場合、色コードが０のランレングスデータは符号長が８８ビットとなり、色コードが１のランレングスデータは符号長が１６８ビットになることを示している。
【００１２】
また、図３０において２行目には、２、４０、７５が格納されている。これは、ｍ＝１として、図２９のランレングスコードをランレングスデータで表した場合、色コードが０のランレングスデータは符号長が４０ビットとなり、色コードが１のランレングスデータは符号長が７５ビットになることを示している。
【００１３】
図３０の表から分かるように、色コード０については、長さ部のビット数を３にすると、図２９のランレングスコードを２４ビットのランレングスデータで表すことができ、色コード１については、長さ部のビット数を５にすると、６４ビットのランレングスデータで表すことができ、それぞれランレングスデータの符号長を最小にすることができる。
【００１４】
図３１は、色コード０の長さ部のビット数を３、色コード１の長さ部のビット数を５にした場合の図２９のランレングスコードのランレングスデータである。
【００１５】
図３１に示すように、Ｂで表される色コード１は長さ部のビット数が５であるため、Ｂ１８は００１１００１０の８ビットで表されている。また、Ａで表される色コード０は長さ部のビット数が３であるため、Ａ５は０００１０１の６ビットで表されている。
【００１６】
このようにして、図２９の“Ｂ１８〜Ｂ１７”のランレングスコードをランレングスデータで表すと、図３１に示す６４ビットのランレングスデータが得られる。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開２０１０−１３１６８１号公報
【特許文献２】特開２００９−０６０３１７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１８】
色コード部のビット数が例えば３の場合、８色の画像を取り扱うことができる。したがって、実際の画像で使用されている色が８色未満の場合、未使用の色コードが発生するが、従来のランレングス符号化においては、この未使用の色コードをどのように取り扱うかに関して全く考慮されていなかった。
【００１９】
また、ＯＳＤ表示パターンのランレングスデータは、ランレングスの分布には偏りがある場合が多い。図３２（Ａ）は、図２９のランレングスコードにおいて、色コード１のランのヒストグラムである。図３２（Ｂ）は、図２９のランレングスコードの色コード１において、色コード部のビット数を３ビットとし、長さ部のビット数を１〜５としたときの符号長である。
【００２０】
図３２（Ｂ）の表から分かるように長さ部のビット数を５にすると符号長を最小にすることができる。しかしながら、ランレングスが２〜３のランは、長さ部のビット数が２であれば十分である。したがって、色コード１について長さ部のビット数を一律に５に設定すると、ランレングスが２〜３のランに対して長さ部のビット数が３ビット余分になり、符号化効率が悪い。これはランレングスの分布に複数の偏りがあることが原因であるが、この複数の偏りに関して、従来のランレングス符号化では全く考慮されていなかった。
【００２１】
本発明の目的は、原画像データをより効率良くランレングス符号化することができる技術を提供することである。
【課題を解決するための手段】
【００２２】
（１）本発明によるランレングス符号化装置は、所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とで各ランを表すランレングスデータに原画像データを符号化するランレングス符号化装置であって、前記原画像データを色コードとランレングスとでコード化し、ランレングスコードを生成し、前記ランレングスコードを構成する各色コードにつき、各ランのランレングスのヒストグラムを算出し、算出したヒストグラムに基づいて、ある色コードが割り当てられたランの一部を抽出し、未使用の色コードに割り当てる色コード割当部と、前記色コード割当部による割り当てが終了した後、各色コードにつき、全ランの符号化結果が最小となるビット数を前記長さ部のビット数として求め、各ランを符号化する符号化部とを備える。
【００２３】
この構成によれば、色コードごとのランレングスのヒストグラムに基づき、いずれかの色コードのランが未使用の色コードに振り分けられる。そのため、原画像データを効率良く符号化することができる。
【００２４】
（２）前記符号化部は、各色コードにつき、ランレングスの最小値をベース値として算出するベース値算出部と、各ランにつき、ランレングスから対応する色コードのベース値を差し引き、各ランの差分ランレングスを算出する差分ランレングス算出部と、各色コードにつき、全ランの差分ランレングスを表すことができる最小のビット数を前記長さ部のビット数として求め、各ランを符号化する差分ランレングス符号化部とを備えることが好ましい。
【００２５】
この構成によれば、各色コードにつき、ランレングスの最小値がベース値として算出される。そして、各ランのランレングスから対応する色コードのベース値が差し引かれて差分ランレングスが算出される。そのため、差分ランレングスはベース値からのオフセットを表し、ランレングスよりも小さくなる。よって、差分ランレングスで各ランを表すことで、各ランの符号長をより短くし、ランレングスデータのビット長を更に短くすることができる。
【００２６】
（３）前記符号化部は、各色コードにつき、前記ベース値を、前記長さ部のビット数と対応付けてベース値テーブルを生成するベース値テーブル生成部を更に備えることが好ましい。
【００２７】
この構成によれば、各色コードにつき、ベース値と長さ部のビット数とが対応付けられたベース値テーブルが生成されるため、このベース値テーブルを参照することで、差分ランレングスからランレングスを算出することができる。
【００２８】
（４）前記色コード割当部は、前記ヒストグラムからランレングスに複数の偏りがある色コードを特定し、特定した色コードに対し、同じ偏りに属するランを抽出し、前記未使用の色コードを割り当てることが好ましい。
【００２９】
この構成によれば、各色コードに複数の偏りがある場合、これらの偏りが分散されるように、各色コードにランが割り当てられる。そのため、符号化効率を改善することができる。
【００３０】
（５）前記色コード割当部は、各色コードにつき、前記長さ部のビット数の分割位置を変えながら符号長の削減量を算出し、前記削減量を最大化する分割位置を持つ色コードを、前記複数の偏りがある色コードとして特定し、特定した色コードにおいて、前記削減量を最大化する分割位置より大きなビット数で表されるランレングスを持つランを抽出し、前記未使用の色コードを割り当てることが好ましい。
【００３１】
この構成によれば、各色コードにおいて長さ部のビット数を分割するための分割位置をより正確に求めることができる。
【００３２】
（６）本発明によるランレングス復号化装置は、所定ビット数で色コードを格納する色コード部と、前記色コード毎にビット数が定められた長さ部とを用いて各ランを表すランレングスデータを原画像データに復号化するランレングス復号化装置であって、前記長さ部は、各ランのランレングスから各ランのベース値を差し引いた差分ランレングスを格納し、前記ベース値は、各色コードにおけるランレングスの最小値を示し、各色コードにつき、前記ベース値と前記長さ部のビット数とが対応付けられたベース値テーブルを保持するベース値テーブル保持部と、各色コードをビットマップ形式で表すための色情報を保持する色情報保持部と、前記ランレングスデータから色コードを特定し、特定した色コードに対応する前記長さ部のビット数を前記ベース値テーブルから特定し、特定したビット数分の前記色コードに続く前記ランレングスデータを差分ランレングスとして抽出する差分ランレングス抽出部と、前記差分ランレングス抽出部により抽出された差分ランレングスに対応するベース値を加算し、ランレングスを算出する加算部と、前記加算部により算出されたランレングス及び前記色情報に基づいて前記ランレングスデータを前記原画像データに復号化する復号化部とを備える。
【００３３】
この構成によれば、差分ランレングスを用いて各ランが表された符号化ランレングスを復号化することができる。
【発明の効果】
【００３４】
本発明によれば、原画像データを効率良くランレングスデータに符号化することができる。
【図面の簡単な説明】
【００３５】
【図１】本発明の実施の形態によるランレングス符号化装置のブロック図である。
【図２】（Ａ）は図２９（Ａ）に対して色コードが１、かつ、ランレングスが２〜３のランに対し、色コード２が割り当てられた原画像データである。（Ｂ）は（Ａ）の原画像データのランレングスコードである。
【図３】図２（Ｂ）のランレングスコードを、長さ部のビット数を変えて符号化したときの色コード別の符号長である。
【図４】ベース値テーブルが生成される処理を示した図である。
【図５】本発明の実施の形態によるランレングス復号化装置のブロック図である。
【図６】図５に示すランレングス符号化装置が適用されていない比較例の車載用カメラの機能ブロック図である。
【図７】図５に示すランレングス復号化装置が適用された車載用カメラの機能ブロック図である。
【図８】図５に示すランレングス復号化装置が適用された車載用カメラのハードウェア構成を示すブロック図である。
【図９】図８に示す車載用カメラにおいて、６種類のＯＳＤ表示パターンを撮像画像データに重畳して出力する場合のＯＳＤ表示制御部８３の機能ブロック図である。
【図１０】ランレングス符号化装置が車載用カメラにランレングスデータを書き込む際の処理を示したブロック図である。
【図１１】（Ａ）は、図１に示すランレングス符号化装置が行うランレングス符号化処理を示したフローチャートである。
【図１２】図１１（Ａ）の色コード分割処理のサブルーチンを示すフローチャートである。
【図１３】図１１に示すベース値算出処理のサブルーチンを示すフローチャートである。
【図１４】図１１のランレングス符号化処理のサブルーチンを示すフローチャートである。
【図１５】図１３、図１４、図１６で示すラン抽出処理のサブルーチンを示すフローチャートである。
【図１６】図１１（Ｂ）に示す長さ部ビット数算出処理のサブルーチンを示すフローチャートである。
【図１７】実施例２でランレングス符号化の対象となるＯＳＤ表示パターンを示した図である。
【図１８】初期のヒストグラムである。
【図１９】初期の色コードテーブルである。
【図２０】初期の符号長テーブルである。
【図２１】符号長削減量テーブルである。
【図２２】初期のヒストグラムを更新することで得られたヒストグラムである。
【図２３】図１９に示す初期の色コードテーブルを更新することで得られた色コードテーブルである。
【図２４】色コード分割処理によって最終的に得られたヒストグラムである。
【図２５】色コード分割処理によって最終的に得られた色コードテーブルである。
【図２６】色コード分割処理によって最終的に得られた符号長テーブルである。
【図２７】色コード分割処理が行われた図１７に示すＯＳＤ表示パターンに対し、差分ランレングスを求めて符号化した場合の効果を示す表である。
【図２８】実施例２の結果をまとめた表である。
【図２９】（Ａ）は８×８のＯＳＤ表示パターンをランレングス符号化した一例である。（Ｂ）は図２９（Ａ）に示すＯＳＤ表示パターンを色コードとランレングスとでコード化することで得られたランレングスコードである。
【図３０】図２９のランレングスコードについて、色コード部のビット数を３として、長さ部のビット数を変えたときの色コード毎のランレングスデータの符号長である。
【図３１】色コード０の長さ部のビット数を３、色コード１の長さ部のビット数を５にして、図２９のランレングスコードのビットパターンである。
【図３２】（Ａ）は、図２９のランレングスコードにおいて、色コード１のランのヒストグラムである。（Ｂ）は、図２９のランレングスコードの色コード１において、色コード部のビット数を３ビットとし、長さ部のビット数を１〜５としたときの符号長である。
【発明を実施するための形態】
【００３６】
図１は、本発明の実施の形態によるランレングス符号化装置のブロック図である。ランレングス符号化装置は、画像取得部１１、テーブル保持部１２、色コード割当部１３、符号化部１４、及びランレングスデータ保持部１６を備えている。
【００３７】
画像取得部１１は、符号化対象となる原画像データを取得する。ここで、原画像データは、例えば、複数の画素がマトリックス状に配列されたデータ構造を持つ。また、各画素は、Ｒ，Ｇ，Ｂ、及び透明度の４成分からなる画素値を持つ。
【００３８】
色コード割当部１３は、画像取得部１１により取得された原画像データの各画素に対して色毎に色コードを付す。そして、色コードを付した原画像データを色コードとランレングスとでコード化し、ランレングスコードを生成する。ここで、ランレングスコードは、複数のランから構成されている。各ランは、色コードとランレングスとで構成されている。色コードはランの色を示す。ランレングスはランの長さを示す。
【００３９】
例えば、図２９（Ａ）の例では、左上の画素からラスタ走査していくと、色コード１の画素が１８個連続している。そのため、これら１８個の画素が１つのランとなる。そして、色コード１に対応する符号Ｂがこのランの色コードとして設定される。なお、図２９（Ｂ）の例では、色コード０，１は、それぞれＡ，Ｂの符号で表されている。
【００４０】
また、この１つのランには１８個の画素が含まれるため、この１つのランのランレングスとして１０進数の１８が設定される。色コード割当部１３は、図２９（Ａ）に示す色コードを付与した原画像データに対してこの処理を繰り返し、図２９（Ｂ）に示すランレングスコードを生成する。
【００４１】
また、色コード割当部１３は、生成したランレングスコードを構成する各色コードにつき、各ランのランレングスのヒストグラムを算出し、算出したヒストグラムに基づいて、ある色コードが割り当てられたランの一部を抽出し、未使用の色コードに割り当てる。
【００４２】
図２９（Ａ）の例では、原画像データには色コード０、色コード１が含まれているため、それぞれの色コード０，１のヒストグラムが算出される。この例において、色コード１に対しては、例えば図３２（Ａ）で示すようなヒストグラムが算出される。つまり、色コード割当部１３は、ランレングスのビット長を複数の階級に分け、各ランのランレングスがどの階級に属するかを特定し、特定した階級に投票することでヒストグラムを算出し、テーブル保持部１２に保持する。
【００４３】
本実施の形態では、最終的に色コードを３ビットのビット列で２進数表示する。そのため、色コードは、最大８つの色コードを表すことができるが、図２９（Ａ）の原画像データでは色コードが２つしか使用されていないため、６つの色コードが未使用となっている。
【００４４】
そこで、色コード割当部１３は、未使用の色コードがある場合、色コードごとのランレングスのヒストグラムに基づき、いずれかの色コードのランを未使用の色コードに振り分けることにより、符号化効率を改善している。
【００４５】
図３２（Ａ）の例では、ランレングスが２〜３と１６〜３１に偏って分布している。そこで、色コード割当部１３は、ランレングスが２〜３のランの色コードに対し、未使用の色コード２を割り当てる。つまり、色コード割当部１３は、ランレングスに複数の偏りがある色コードに対し、同じ偏りに属するランを抽出し、未使用の色コードを割り当てる。
【００４６】
図２（Ａ）は、図２９（Ａ）の例において、色コードが１、かつ、ランレングスが２〜３のランに色コード２を割り当てたときの原画像データである。図２（Ａ）に示すように、図２９（Ａ）で色コード１が付与されていた画素が色コード２に変更されている。図２（Ｂ）は、図２（Ａ）の原画像データのランレングスコードである。この例では、色コード２に対してＣの符号が割り当てられ、ランレングスコードが表されている。
【００４７】
また、色コード割当部１３は、各色コードと長さ部のビット数とが対応付けられた色コードテーブル（図１９参照）を生成し、テーブル保持部１２に保持する。
【００４８】
そして、色コード割当部１３は、色コードの割り当てを変更すると、その割り当ての変更が反映されるように色コードテーブル及びヒストグラムをそれぞれ更新する。具体的には、色コード割当部１３は、あるランにつき色コードの割り当てを変更した場合、そのランの当初の色コードと変更後の色コードとが対応付けられるように色コードテーブルを更新する。
【００４９】
このように、色コードテーブルを更新することで、復号化を行う際、色コードの割り当てが変更されたランについて、そのランが当初持っていた色を再現することができる。
【００５０】
符号化部１４は、色コード割当部１３による割り当てが終了した後、各色コードにつき、全ランの符号化結果が最小となるビット数を長さ部のビット数として求め、各ランを符号化し、ランレングスコードをビットパターンで表したランレングスデータを求める。ここで、ランレングスデータは、各ランを色コード部と長さ部とで表すデータ構造を持っている。色コード部のビット数は３である。
【００５１】
図３は、図２（Ｂ）のランレングスコードを、長さ部のビット数を変えて符号化したときの色コード別の符号長である。色コード０は長さ部のビット数を３、色コード１は長さ部のビット数を５、色コード２は長さ部のビット数を２に設定すると、ランレングスデータの符号長が５５ビットとなり、符号長を最小にすることができる。一方、色コード１の一部のランを色コード２に割り当てる前は、図３０に示すようにランレングスデータの符号長は６４ビットであった。したがって、色コード１のランのうち、ランレングスが２〜３のランを色コード２に割り当てることで、符号号化効率を改善することができる。
【００５２】
具体的には、符号化部１４は、ベース値算出部１４１、差分ランレングス算出部１４２、差分ランレングス符号化部１４３、及びベース値テーブル生成部１４４を備えている。
【００５３】
ベース値算出部１４１は、画像取得部１１により取得された原画像データから、色コード割当部１３と同様にしてランレングスコードを生成し、各色コードにつき、ランレングスの最小値をベース値として算出する。差分ランレングス算出部１４２は、画像取得部１１により取得された原画像データから色コード割当部１３と同様にしてランレングスコードを生成し、各ランにつき、ランレングスから対応する色コードのベース値を差し引き各ランの差分ランレングスを算出する。
【００５４】
差分ランレングス符号化部１４３は、画像取得部１１により取得された原画像データから色コード割当部１３と同様にしてランレングスコードを生成し、各色コードにつき、全ランの差分ランレングスを表すことができる最小のビット数を長さ部のビット数として求め、各ランを符号化する。
【００５５】
ベース値テーブル生成部１４４は、ベース値算出部１４１により各色コードについて算出されたベース値を、差分ランレングス符号化部１４３により各色コードについて算出された長さ部のビット数と対応付けてベース値テーブルを生成し、テーブル保持部１２に保持する。
【００５６】
図４は、ベース値テーブルが生成される処理を示した図である。図４（Ａ）は図２（Ａ）の色コードが付された原画像データであり、（Ｂ）は（Ａ）の原画像データを差分ランレングスを用いて表したときのランレングスコードであり、（Ｃ）はベース値テーブルである。
【００５７】
図４（Ｃ）の例では、色コード０，１，２のベース値はそれぞれ５，１７，２と算出されている。よって、図２（Ｂ）で“Ｂ１８”と表されていたランの差分ランレングスは１８−１７＝１となる。したがって、このＢ１８のランは図４（Ｂ）ではＢ１と表されている。他のランについても同様に差分ランレングスが求められる。そして、各色コードにつき、全差分ランレングスを表すことができるビット数が求められる。すると、図４（Ｃ）に示すように、色コード０，１，２の長さ部のビット数はそれぞれ１と算出される。以上により、図４（Ｃ）に示すように、各色コードにつき、長さ部のビット数とベース値とが対応付けられたベース値テーブルが生成される。
【００５８】
図４（Ｂ）に示すランレングスコードをランレングスデータで表すと、符号長は３６ビットであった。したがって、図２（Ｂ）で色コードを振り分けることで５５ビットに削減された符号長が、更に３６ビットまで削減され、符号化効率が改善されている。
【００５９】
図１に戻り、ランレングスデータ保持部１６は、差分ランレングス符号化部１４３により生成されたランレングスデータを保持する。
【００６０】
このように、ベース値からのランレングスのオフセットを表す差分ランレングスを用いて各ランを表すことで、各ランの符号長をより短くし、ランレングスデータの符号長を更に短くすることができる。
【００６１】
図５は、本発明の実施の形態によるランレングス復号化装置のブロック図である。ランレングス復号化装置は、図１に示すランレングス符号化装置で生成されたランレングスデータを復号する。
【００６２】
具体的には、ランレングス復号装置は、ベース値テーブル保持部５１、色情報保持部５２、差分ランレングス抽出部５３、加算部５４、及び復号化部５５を備えている。
【００６３】
ベース値テーブル保持部５１は、各色コードにつき、ベース値と長さ部のビット数とが対応付けられたベース値テーブルを保持する。つまり、ベース値テーブル保持部５１は、図１に示すランレングス符号化装置により生成されたベース値テーブルを保持する。
【００６４】
図５に示すようにベース値テーブル保持部５１は、図４（Ｃ）に示すベース値テーブルと同じものを記憶している。
【００６５】
色情報保持部５２は、ランレングスデータをビットマップデータに展開する際に必要となる色情報を保持する。図５に示すように色情報保持部５２は、各色コードに対し、Ｒ，Ｇ，Ｂの画素値と透明度αを示す画素値との４つの画素値が対応付けられた色情報テーブルを保持している。
【００６６】
差分ランレングス抽出部５３は、ランレングス符号化装置により生成されたランレングスデータから色コードを特定し、特定した色コードに対応する長さ部のビット数をベース値テーブルから特定し、特定したビット数分の色コードに続くランレングスデータを差分ランレングスとして抽出する。
【００６７】
具体的には、差分ランレングス抽出部５３は、まず、ランレングスデータの最初の３ビットに格納された符号列を抽出する。本実施の形態では、ランレングスデータは、各ランが色コード部と長さ部との順で表され、色コード部のビット数は３ビットである。したがって、ランレングスデータの最初の３ビットは色コードを表すことになる。図５の例では、最初の３ビットに００１の符号列が格納されている。よって、差分ランレングス抽出部５３は、最初のランの色コード１と判定する。
【００６８】
次に、差分ランレングス抽出部５３は、色コード１に対応する長さ部のビット数をベース値テーブルから特定する。この場合、色コード１に対応する長さ部のビット数は１である。よって、差分ランレングス抽出部５３は、最初のランの長さ部のビット数は１と判定する。
【００６９】
次に、差分ランレングス抽出部５３は、最初のランの色コードに続く、１ビットのランレングスデータを差分ランレングスとして抽出する。この場合、差分ランレングスは１である。つまり、最初のランは色コードが００１の符号列で表され、長さ部が１の符号列で表されている。よって、差分ランレングス抽出部５３は、ランレングスデータの５，６，７番目の３ビットを２番目のランの色コード部と判定する。差分ランレングス抽出部５３は、以上の処理を繰り返し、ランレングスデータに含まれる色コードと差分ランレングスとを順次に特定する。
【００７０】
加算部５４は、差分ランレングス抽出部５３により抽出された差分ランレングスに対応するベース値を加算し、ランレングスを算出する。図５の例では、最初のランの差分ランレングスは１である。また、最初のランの色コードは１である。よって、加算部５４は、色コード１に対応する長さ部のベース値である１７をベース値テーブルから読み出す。そして、加算部５４は、読み出したベース値である１７に差分ランレングスである１を加算し、ランレングスを算出する。この場合、ランレングスは１８となり、図２（Ｂ）に示す“Ｂ１８”が再現される。
【００７１】
復号化部５５は、加算部５４により算出されたランレングス及び色情報テーブルに基づいてランレングスデータをビットマップデータに展開する。先の例では、最初のランの色コードは１であり、レングスは１８であった。
【００７２】
したがって、復号化部５５は、色コード１に対応するＲ，Ｇ，Ｂ，αの画素値を色情報テーブルから読み出し、連続する１８個の画素に対して、色コード１に対応するＲ，Ｇ，Ｂ，αの画素値を設定し、各画素を順次に出力することで、ランレングスデータをビットマップデータに展開する。これにより原画像データが得られる。
【００７３】
例えば、復号化部５５は、撮像系で撮像された撮像画像データが展開されたフレームバッファに画素値を書き込むことでビットマップデータに展開する。その結果、ＯＳＤ表示パターン専用のフレームバッファが不要となる。そして、復号化部５５は、各ランに対して上記の処理を繰り返し、ＯＳＤ表示パターンを撮像画像データに重畳表示する。
【００７４】
（実施例１）
次に、図５に示すランレングス復号化装置を車載用カメラに適用した実施例１について説明する。車載用カメラでは、バックビューモニタ用途での車幅線表示など、撮像画像にグラフィックを重畳して出力する機能が求められる。このグラフィックがＯＳＤ表示パターンである。
【００７５】
ＯＳＤ表示パターンを表示する方法として、ＥＣＵなどではＯＳＤ表示パターン専用のフレームバッファを設け、グラフィックコントローラでフレームバッファにＯＳＤパターンを描画する構成が採用される。
【００７６】
図６は、図５に示すランレングス符号化装置が適用されていない比較例の車載用カメラの機能ブロック図である。図６に示す車載用カメラは、撮像系６１、画像処理回路６２、グラフィックコントローラ６３、フレームバッファ６４、及び出力制御部６５を備えている。
【００７７】
撮像系６１は、所定のフレームレートで被写体を撮像するカメラにより構成され、撮像画像データを取得する。画像処理回路６２は、撮像系６１により取得された撮像画像データに対し、ガンマ補正等の所定の画像処理を行う。グラフィックコントローラ６３は、描画回路６３１及び重畳回路６３２を備えている。
【００７８】
描画回路６３１は、ＣＰＵから描画命令を受け、ＯＳＤ表示パターンをフレームバッファ６４に生成する。重畳回路６３２は、フレームバッファ６４に展開されたＯＳＤ表示パターンと、画像処理回路６２から出力された撮像画像データとを重畳し、出力制御部６５に出力する。具体的には、重畳回路６３２は、画像処理回路６２から入力される撮像画像データに同期してフレームバッファ６４からＯＳＤ表示パターンを読み出し、画素演算により重畳結果を生成する。出力制御部６５は、重畳結果画像をＮＴＳＣ信号やデジタル信号として外部に出力する。
【００７９】
このように、比較例の車載用カメラの構成ではフレームバッファ６４として、大容量のＲＡＭが必要となる。また、描画回路６３１を備えるグラフィックコントローラ６３が必要になり、コストが嵩む。
【００８０】
車載用途で必要となるＯＳＤ表示パターンは、車幅線等の予め決められたグラフィック画像が採用される。そのため、必要なＯＳＤ表示パターンを符号化し、データとして保持しておき、表示時にリアルタイムで復号化して表示する構成を採用すると、フレームバッファ６４や描画回路６３１が不要となり、コストダウンが可能である。
【００８１】
図７は、図５に示すランレングス復号化装置が適用された車載用カメラの機能ブロック図である。図７に示す車載用カメラは、撮像系７１、画像処理回路７２、重畳回路７３、符号データＲＡＭ７４、復号化回路７５、及び出力制御部７６を備えている。
【００８２】
撮像系７１、画像処理回路７２、及び出力制御部７６は、図６のものと同じである。符号データＲＡＭ７４は、図１に示すランレングス符号化装置により予め生成されたランレングスデータを保持する。復号化回路７５は、図５に示すランレングス復号化装置により構成されている。重畳回路７３は、画像処理回路７２から出力される撮像画像データと、復号化回路７５から出力されるＯＳＤ表示パターンとを重畳し、重畳結果を出力する。
【００８３】
この構成によれば、ＯＳＤ表示パターンの復号化が、車載用カメラ内部において、表示時にリアルタイムで行われる。そのため、比較例の車載用カメラのように描画回路６３１及びＯＳＤ表示パターン専用のフレームバッファ６４が不要となり、装置構成を簡略化し、コストダウンを図ることができる。
【００８４】
また、符号データＲＡＭ７４が保持するランレングス符号化されたＯＳＤ表示パターンは、車載用カメラの外部で生成されるため、符号化アルゴリズムが複雑化してもコストに対する影響は少ない。また、ランレングスデータの復号化は比較的簡素な処理で実現できるため、表示時においてリアルタイムの復号化が可能となり、車載用カメラにとって好適である。
【００８５】
図８は、図５に示すランレングス復号化装置が適用された車載用カメラのハードウェア構成を示すブロック図である。
【００８６】
図８に示す車載用カメラは、撮像系８１、画像処理回路８２、ＯＳＤ表示制御部８３、出力制御部８４、ＣＰＵ８５、ＲＡＭ８６、ＲＯＭ８７、及びＩ／Ｏ８８を備えている。撮像系８１〜Ｉ／Ｏ８８はそれぞれ、バスライン８９を介して相互に接続されている。
【００８７】
撮像系８１及び画像処理回路８２は、それぞれ図７の撮像系７１及び画像処理回路７２を構成する。ＯＳＤ表示制御部８３は、図７に示す復号化回路７５、符号データＲＡＭ７４、及び重畳回路７３を構成する。出力制御部８４は図７に示す出力制御部７６を構成する。ＣＰＵ８５は、車載用カメラの全体制御を司る。ＲＡＭ８６は、ＣＰＵ８５のワーキングメモリとして使用される。ＲＯＭ８７は予め作成されたランレングスデータを保持している。Ｉ／Ｏ８８は、例えばＥＣＵとの間で各種の制御信号を入出力する。出力制御部８４は、ＯＳＤ表示パターンと撮像画像データとを重畳した画像データをデジタルの画像信号として外部に出力する、或いは、ＮＴＳＣ信号に変換して外部に出力する。
【００８８】
図９は、図８に示す車載用カメラにおいて、６種類のＯＳＤ表示パターンを撮像画像データに重畳して出力する場合のＯＳＤ表示制御部８３の機能ブロック図である。
【００８９】
図９に示すＯＳＤ表示制御部は、６種類のＯＳＤ表示パターンを表示時にリアルタイムに復号化して出力するものである。このＯＳＤ表示制御部は、図７に示す符号データＲＡＭ７４、復号化回路７５、及び重畳回路７３からなる復号化ユニットが６段設けられている。
【００９０】
１段目の重畳回路７３には、図７に示す撮像系７１が画像処理回路７２を介して接続され、撮像系７１により撮像された撮像画像データが入力される。
【００９１】
１段目〜６段目の符号データＲＡＭ７４は、それぞれ、それぞれ、６種類のＯＳＤ表示パターンである第１〜第６のＯＳＤ表示パターンをランレングス符号化することで予め得られたランレングスデータを保持している。そして、１段目〜６段目の符号データＲＡＭ７４は、ＣＰＵ８５からの復号化開始の制御信号を受け付けると、保持するランレングスデータを復号化回路７５に出力し、復号化回路７５に復号化処理を実行させる。
【００９２】
復号化回路７５は、ランレングスデータを復号化して重畳回路７３に出力する。１段目の重畳回路７３は１段目の復号化回路７５から出力された第１のＯＳＤ表示パターンと撮像画像データを重畳して２段目の重畳回路７３に出力する。２段目〜５段目の重畳回路７３は、それぞれ、上段の重畳回路７３から出力された画像データに第２〜第５のＯＳＤ表示パターンを重畳し、下段の重畳回路７３に出力する。
【００９３】
６段目の重畳回路７３は、５段目の重畳回路７３から出力された画像データに第６のＯＳＤ表示パターンを重畳し、出力制御部７６に出力する。これにより撮像画像データに第１〜第６のＯＳＤ表示パターンが重畳された画像データが出力制御部７６に出力される。
【００９４】
図１０は、ランレングス符号化装置が車載用カメラにランレングスデータを書き込む際の処理を示したブロック図である。
【００９５】
コンピュータ１０１は、図１に示すランレングス符号化装置の機能を実現する。まず、コンピュータ１０１はグラフィック作成ツールを起動し、デザイナーからの操作指示にしたがって、ＯＳＤ表示パターンを生成する（工程１）。
【００９６】
次に、コンピュータ１０１は、生成したＯＳＤ表示パターンをランレングス符号化し、ランレングスデータを生成する（工程２）。次に、コンピュータ１０１は、生成したランレングスデータを車載用カメラ１０２のＲＯＭに書き込む（工程３）。これにより、車載用カメラ１０２はランレングスデータを得る。このとき、コンピュータ１０１は、ランレングスデータを復号化するために必要となる色コードテーブル及びベース値テーブルもＲＯＭ８７に書き込む。
【００９７】
なお、コンピュータ１０１は、例えば車載用カメラ１０２が備えるＩ／Ｏ８８とケーブルを介して接続され、ランレングスデータ等を車載用カメラ１０２に出力する。
【００９８】
次に、ＯＳＤ表示制御部８３がＲＯＭ８７からランレングス符号化データを読み出し（工程４）、復号化してＯＳＤ表示パターンを生成し、出力制御部８４を介して外部に出力する。
【００９９】
（実施例２）
次に、実施例１の車載用カメラで使用されるＯＳＤ表示パターンを図１に示すランレングス符号化装置を用いてランレングス符号化する実施例２について説明する。
【０１００】
図１０に示す車載用カメラ１０２の仕様は下記の通りである。
【０１０１】
ＯＳＤ表示パターンの重畳数：６個
同時表示可能色数：８色／面
色コードのビット数：３ｂｉｔ
符号データＲＡＭ７４：色コードが３ｂｉｔなので、３ｂｉｔ／ｗｏｒｄのＲＡＭを使用する。回路を簡単にするため各ランの長さ部は３ｂｉｔの倍数とする。
【０１０２】
符号データＲＡＭ７４のサイズ：２０４９ｂｉｔ／面（３ｂｉｔ／ｗｏｒｄ×６８３ｗｏｒｄ）
表示色：ＲＧＢ２４ｂｉｔ→各面の各色コードに対応した色情報テーブルを設け、３ｂｉｔの色コードをＲＧＢ２４ｂｉｔの画素データに変換する。
【０１０３】
透過表示制御：０（透過率０）〜１（透過率１００％）を１／１６ステップの１７段階で指定する。
【０１０４】
出力される画像データ：３６０×４８０ｐｉｘｅｌ，２４ｂｉｔ／ｐｉｘｅｌ
このように、符号データＲＡＭ７４のサイズが２ＫＢに限定されているため、各ＯＳＤ表示パターンは２ＫＢ以下のサイズに符号化しなければならず、符号化効率のよい符号化アルゴリズムが必要となる。
【０１０５】
＜ランレングス符号化＞
図１１（Ａ）は、図１に示すランレングス符号化装置が行うランレングス符号化処理を示したフローチャートである。図１７は、実施例２でランレングス符号化の対象となるＯＳＤ表示パターンを示した図である。
【０１０６】
このＯＳＤ表示パターンは、３６０×４８０の画素から構成され、３つの色コードを持っている。画面中央に示す傾斜した波線からなるグラフィックには色コード５が付与されている。ＯＳＤ表示パターンの外周を覆う外枠のグラフィックには色コード６が付与されている。ＯＳＤ表示パターンの傾斜した波線からなるグラフィックの背景のグラフィックには色コード０が付与されている。
【０１０７】
まず、色コード割当部１３は、色コード分割処理を行う（Ｓ１）。次に、符号化部１４は、ベース値算出処理を行う（Ｓ２）。次に、符号化部１４は、ランレングス符号化を行い、ランレングスデータを生成する（Ｓ３）。
【０１０８】
＜色コード分割処理＞
図１２は、図１１（Ａ）の色コード分割処理のサブルーチンを示すフローチャートである。まず、色コード割当部１３は、初期化を行う。このとき、色コード割当部１３は、初期の色コードテーブルを生成する（Ｓ１１）。
【０１０９】
図１９は、初期の色コードテーブルである。色コードテーブルは、色コードのフィールドと長さ部ビット数のフィールドとを備えている。色コードテーブルのフィールドには０（Ａ）〜７（Ｈ）の８色の色コードが格納されている。長さ部ビット数のフィールドには、各色コードにおいて、長さ部のビット数毎に割り当てられた色コードが示されている。
【０１１０】
図１９の例では、長さ部ビット数は、０ビット、３ビット、６ビットというように３ビット毎区切られている。これは、符号データＲＡＭを３ｂｉｔ／ｗｏｒｄとしたためである。
【０１１１】
図１９は初期の色コードテーブルであるため、色コード０〜７のそれぞれに対して、長さ部ビット数にかかわらず、色コード０〜７が割り当てられている。
【０１１２】
また、Ｓ１１において、色コード割当部１３は、図２０に示す符号長テーブルを生成する。図２０は、初期の符号長テーブルである。符号長テーブルは、色コードテーブルと同様のデータ構造を持っている。そして、この符号長テーブルは、各色コードにつき、長さ部のビット数を変えたときのランレングスデータの符号長を示している。
【０１１３】
例えば、１行１列目のセルにはｄｄａ９０が格納されている。これは、色コード０につき、長さ部のビット数を０ビットにしたとき、色コード０のグラフィックのランレングスデータの符号長がｄｄａ９０ビットであったからである。
【０１１４】
図２０に示すように、色コード０については、長さ部のビット数を９ビットにしたとき、符号長が１ｅｆ０となり最小となる。そのため、色コード割当部１３は、色コード０の長さ部のビット数を９に設定する。
【０１１５】
同様に色コード５，６については、それぞれ、長さ部のビット数を６ビットに設定したとき、符号長が最小となる。よって、色コード割当部１３は、色コード５，６の長さ部のビット数をそれぞれ６に設定する。
【０１１６】
なお、色コード０，５，６のそれぞれにつき、長さ部のビット数を９，６，６に設定したときのランレングスデータのトータルの符号長は、１ｅｆ０＋０６ｅ４＋１４ｃ７＝４４９ｂ＝１７，５６３ｂｉｔとなる。
【０１１７】
図１２に戻り、色コード割当部１３は、ヒストグラムを作成する（Ｓ１２）。図１８は、初期のヒストグラムである。ヒストグラムは、色コードテーブルと同様のデータ構造を持っている。なお、ヒストグラムの各セルに格納された数値は１６進数である。
【０１１８】
図１７のＯＳＤ表示パターンでは、色コード０のグラフィックにおいて、長さ部のビット数が０ビットより大きく３ビット以下で表すことのできるランの個数が６個であったため、１行２列目のセルには６が格納されている。また、色コード０のグラフィックにおいて、長さ部のビット数が３ビットより大きく６ビット以下で表すことができるランの個数が４８個であったため、１行４列目のセルには４８が格納されている。
【０１１９】
また、図１７に示すＯＳＤ表示パターンは、色コード０のグラフィックの他に、色コード５のグラフィックと色コード６のグラフィックとが存在するため、色コード５、６の該当するセルに数値が格納されている。色コード０，５，６以外の色コードのセルには、数値は格納されていない。
【０１２０】
図１２に戻り、色コード割当部１３は、未使用の色コードが存在するか否かを判定する（Ｓ１３）。未使用の色コードが存在する場合（Ｓ１３でＹＥＳ）、色コード割当部１３は、色コード分割位置を算出する（Ｓ１４）。図１８に示す初期のヒストグラムには、色コード０，５，６以外の色コードのセルには数値が格納されていないため、色コード割当部１３は、未使用の色コードが存在すると判定する。
【０１２１】
一方、未使用の色コードが存在しない場合（Ｓ１３でＮＯ）、処理をリターンさせる。この場合、ヒストグラムにおいて、初期状態で色コードが割り当てられていなかった色コードのいずれかのセルにおいて、数値が格納されていれば、未使用の色コードはないと判定される。
【０１２２】
＜Ｓ１４＞色コード分割位置算出処理
以下、Ｓ１４の色コード分割位置算出処理について詳細に説明する。まず、色コード割当部１３は、各色コードにつき、長さ部のビット数の分割位置を変えながら、現在の長さ部のビット数に対してどれだけ符号長を削減させることができるかを示す符号長削減量テーブルを算出する。そして、符号長削減量テーブルに基づいて、削減量を最大化することができる色コードの分割位置を算出する。図２１は、符号長削減量テーブルである。なお、符号長削減量テーブルは、色コードテーブルと同様のデータ構造を持っている。
【０１２３】
色コード割当部１３は、現在、色コード０，５，６につき、長さ部のビット数を９，６，６に設定している。そのため、図２１に示す符号長削減量テーブルは、この場合と比較したときの符号長の削減量を示している。
【０１２４】
色コード０において、分割位置を３ビットとすると、削減量は３６ビットとなる。ここで、分割位置が３ビットとは、色コード０において、長さ部のビット数が３ビット以下のランは長さ部のビット数を３ビットとしてランレングス符号化を行い、長さ部のビット数が３ビットより大きいランは、分割前の長さ部のビット数（色コード０の場合は９ビット）でランレングス符号化を行った場合を示している。
【０１２５】
同様に、色コード０において、分割位置を６ビットにすると、削減量は２３４ビットとなる。このことから、色コード０については、分割位置を６ビットすると、削減量を最大にすることができる。色コード５，６についても色コード０と同様に長さ部のビット数を変えながら削減量を求める。その結果、色コード５については、分割位置を３ビット、色コード６については分割位置を６ビット又は９ビットにすると削減量を最大にすることができる。
【０１２６】
そして、色コード割当部１３は、図２１に示す符号長削減量テーブルにおいて、全色コードのうち、削減量が最大の色コードを分割対象の色コードとして決定する。この場合、色コード６の６又は９ビットの削減量が１１２２ビットであるため、色コード６が分割対象の色コードとして決定される。
【０１２７】
そして、色コード割当部１３は、色コード６において、削減量が最大である６ビット、又は９ビットを分割位置として決定する。なお、色コード６では、分割位置を６ビット、９ビットとしても削減量は同じである。このような場合、色コード割当部１３は、小さい方の６ビットを分割位置とするが、これに限定されず、大きい方の９ビットを分割位置にしてもよい。
【０１２８】
＜Ｓ１５＞ヒストグラム分割処理
図１２に戻り、Ｓ１５において、色コード割当部１３は、色コード６の分割位置を６ビットとしたため、色コード６において、ランレングスが６ビットより大きなランを抽出し、未使用の色コードに割り当てる。この場合、色コード割当部１３は、例えば、未使用の色コードのうち、番号が最も若い色コードに抽出したランを割り当てればよい。この場合、未使用の色コードのうち、番号が最も若い色コードは色コード１であるため、色コード６において、ランレングスが６ビットより大きなランは色コード１が割り当てられる。
【０１２９】
次に、色コード割当部１３は、抽出したランに対して新たに色コードを割り当てたことを反映させるため、図１８に示す初期のヒストグラムを更新する。図２２は、初期のヒストグラムを更新することで得られたヒストグラムである。
【０１３０】
図２２に示すように、色コード６において長さ部のビット数が９〜２１ビットの各セルに格納された数値が色コード１の長さ部のビット数が９〜２１ビットの各セルに移動され、かつ、色コード６において長さ部のビット数が９〜１２ビットの各セルに格納された数値が０に更新されている。
【０１３１】
＜Ｓ１６＞色コードテーブル更新処理
図１２に戻り、Ｓ１６において、色コード割当部１３は、図１９に示す初期の色コードテーブルを更新する。図２３は、図１９に示す初期の色コードテーブルを更新することで得られた色コードテーブルである。
【０１３２】
図２３に示すように、色コード６において、長さ部のビット数が９〜１２ビットの各セルに格納された数値が６から１に更新されている。これにより、色コード６においてランレングスが６ビットよりも大きいランに対して、色コード１を付与しても、これらのランは、元々は色コード６であったことが分かる。
【０１３３】
次に、色コード割当部１３は、図２０に示す初期の符号長テーブルを生成したときと同様にして、各色コードについての符号長テーブルを生成し、各色コードについて、符号長を最小にする長さ部のビット数を求め、各色コードの長さ部の現在のビット数として設定する。
【０１３４】
以後、色コード割当部１３は、未使用の色コードが残っている間、Ｓ１３〜Ｓ１６の処理を繰り返す。すると、最終的に、図２４に示すヒストグラム、図２５に示す色コードテーブルが得られた。図２４は、色コード分割処理によって最終的に得られたヒストグラムである。図２５は、色コード分割処理によって最終的に得られた色コードテーブルである。
【０１３５】
図２４に示すヒストグラムにおいて、色コード１〜色コード７はそれぞれ、いずれかのセルに数値が格納されており、ランが割り当てられていることが分かる。なお、色コード０において、いずれのセルも０になっているのは、Ｓ１３〜Ｓ１６の最後のループにおいて、色コード０の３ビットのセルの値が未使用の色コード７に移動されたからである。
【０１３６】
図２４に示すヒストグラムでは、色コード１〜７につき、ランレングスが似たような長さを持つランが割り当てられていることが分かる。したがって、各色コードの長さ部は、無駄なくランレングスを格納することができる。
【０１３７】
また、図２５に示すように、例えば、色コード０は、３ビットのセルに色コード７が格納されている。そのため、ランレングスデータにおいて、色コードが７で長さ部のビット数が３ビットのランは、元々の色コードが０であったことが分かる。
【０１３８】
図２６は、色コード分割処理によって最終的に得られた符号長テーブルである。色コード０〜７につき、それぞれ、網掛けで示すセルに対応するビット数で長さ部のビット数を設定すると符号長を最小化することができる。
【０１３９】
図１７に示すＯＳＤ表示パターンの符号長は、色コード分割処理後により、００１ｅ＋１ｂ４８＋０４２６＋０２８８＋０１ｄ４＋１０４７＋００２４＝３４５３＝１３，３９５ｂｉｔとなる。
【０１４０】
＜ベース値処理＞
次に、ベース値処理について説明する。図１１（Ｂ）はベース値処理のフローチャートである。まず、ベース値算出部１４１は、ベース値算出処理を行う（Ｓ２１）。次に、ベース値算出部１４１は、長さ部ビット数算出処理を行う（Ｓ２２）。
【０１４１】
＜ベース値算出処理＞
図１３は、図１１に示すベース値算出処理のサブルーチンを示すフローチャートである。まず、ベース値算出部１４１は、各種パラメータを初期化する（Ｓ３１）。
【０１４２】
次に、ベース値算出部１４１は、処理対象となるＯＳＤ表示パターンの最後のランの抽出が終了したか否かを判定し、終了した場合（Ｓ３２でＹＥＳ）、処理をリターンする。一方、最後のランの抽出が終了していない場合（Ｓ３２でＮＯ）、ベース値算出部１４１はラン抽出処理を行う（Ｓ３３）。
【０１４３】
＜ラン抽出処理＞
図１５は、図１３、図１４、図１６で示すラン抽出処理のサブルーチンを示すフローチャートである。まず、ランレングス変数に０が代入されて初期化され、色コード変数に注目画素の画素値が代入されて色コード変数が初期化される（Ｓ５１）。ここで、注目画素は、ＯＳＤ表示パターンにおいてラスタ走査順に決定される。
【０１４４】
次に、ランレングス変数が１加算され、ランレングス変数が更新される（Ｓ５２）。次に、注目画素の画素位置が更新される（Ｓ５３）。次に、注目画素の画素値が色コード変数と同じ値であれば（Ｓ５４でＹＥＳ）、処理がＳ５２に戻される。一方、注目画素の画素値が色コード変数と異なる値であれば、１つのランが抽出できたと判定され、処理がリターンされる。つまり、ＯＳＤ表示パターンに対して、注目画素が順次ずらされ、注目画素の画素値が前の注目画素の画素値と異なる値になったとき、１つのランが抽出できたと判定する。そして、注目画素をずらす都度、１加算されたランレングス変数の値が抽出したランのランレングスとなる。
【０１４５】
図１３に戻り、Ｓ３４において、ベース値算出部１４１は、図２５に示す色コードテーブルを参照し、Ｓ３３で抽出したランの色コード分割処理後の色コードを算出する。例えば、色コードが０、ランレングスが３ビットより大きく６ビット以下で表すことができるランが抽出された場合、このランの色コードは４と算出される。
【０１４６】
次に、ベース値算出部１４１は、Ｓ３３で抽出したランのランレングスが対応する色コードの現在のベース値未満である場合（Ｓ３５でＹＥＳ）、現在のベース値を抽出したランのランレングスで更新し（Ｓ３６）、処理をＳ３２に戻す。
【０１４７】
一方、Ｓ３３で抽出したランのランレングスが対応する色コードの現在のベース値以上である場合（Ｓ３５でＮＯ）、現在のベース値を更新せず、処理をＳ３２に戻す。
【０１４８】
例えば、Ｓ３４で色コード７と算出されたランのランレングスが色コード７の現在のベース値未満である場合、Ｓ３５でＹＥＳと判定され、色コード７の現在のベース値がこのランレングスで更新される。このような処理が各色コードに対して行われ、各色コードにつき、ランレングスの最小値がベース値として算出される。
【０１４９】
＜長さ部ビット数算出処理＞
次に、図１１（Ｂ）のＳ２２の長さ部ビット数算出処理について説明する。図１６は、図１１（Ｂ）に示す長さ部ビット数算出処理のサブルーチンを示すフローチャートである。まず、差分ランレングス算出部１４２は、各種パラメータを初期化する（Ｓ６１）。次に、差分ランレングス算出部１４２は、処理対象となるＯＳＤ表示パターンの最後のランの抽出が終了したか否かを判定し、終了した場合（Ｓ６２でＹＥＳ）、処理をＳ６８に進める。一方、最後のランの抽出が終了していない場合（Ｓ６２でＮＯ）、差分ランレングス算出部１４２はラン抽出処理を行う（Ｓ６３）。このラン抽出処理は、図１５で示した処理と同じである。
【０１５０】
次に、差分ランレングス算出部１４２は、Ｓ６３で抽出したランの色コードを算出する（Ｓ６４）。この処理は図１３のＳ３４と同じである。
【０１５１】
次に、差分ランレングス算出部１４２は、Ｓ６３で抽出したランレングスから対応する色コードのベース値を差し引き、差分ランレングスを算出する（Ｓ６５）。例えば、Ｓ６３で抽出されたランにおいて、Ｓ６４で算出された色コードが色コード７であった場合、色コード７のベース値を用いて差分ランレングスが算出される。
【０１５２】
次に、差分ランレングス符号化部１４３は、Ｓ６５で求められた差分ランレングスが対応する色コードの最大差分ランレングスより大きい場合（Ｓ６６でＹＥＳ）、対応する色コードの最大差分ランレングスをＳ６５で算出された差分ランレングスで更新し（Ｓ６７）、処理をＳ６２に戻す。
【０１５３】
一方、Ｓ６５で求められた差分ランレングスが対応する色コードの最大差分ランレングス以下の場合（Ｓ６６でＮＯ）、最大差分ランレングスが更新されずに処理がＳ６２に戻される。
【０１５４】
Ｓ６８において、差分ランレングス符号化部１４３は、各色コードにつき、最大差分ランレングスを表すことができる最小のビット数を長さ部のビット数として算出し、処理をリターンする。
【０１５５】
＜ランレングス符号化処理＞
次に、図１１のＳ３のランレングス符号化処理の詳細について説明する。図１４は、図１１のランレングス符号化処理のサブルーチンを示すフローチャートである。まず、差分ランレングス符号化部１４３は、各種パラメータを初期化する（Ｓ４１）。次に、差分ランレングス符号化部１４３は、処理対象となるＯＳＤ表示パターンの最後のランの抽出が終了したか否かを判定し、終了した場合（Ｓ４２でＹＥＳ）、処理をリターンする。一方、最後のランの抽出が終了していない場合（Ｓ４２でＮＯ）、差分ランレングス符号化部１４３はラン抽出処理を行う（Ｓ４３）。このラン抽出処理は、図１５で示した処理と同じである。
【０１５６】
次に、差分ランレングス符号化部１４３は、Ｓ４３で抽出したランの色コードを算出する（Ｓ４４）。この処理は図１３のＳ３４と同じである。
【０１５７】
次に、差分ランレングス符号化部１４３は、Ｓ４４で算出した色コードをランレングスデータ保持部１６に出力する（Ｓ４５）。次に、差分ランレングス符号化部１４３は、Ｓ４３で抽出したランのランレングスから対応する色コードのベース値から差し引き差分ランレングスを求める。そして、差分ランレングスを対応する色コードの長さ部のビット数で符号化することで、差分ランレングスを符号化し、長さ部を算出する（Ｓ４６）。次に、差分ランレングス符号化部１４３は、Ｓ４６で算出した長さ部をランレングスデータ保持部１６に出力する（Ｓ４７）。
【０１５８】
このように、ＯＳＤ表示パターンから順次ランが抽出され、抽出したランの色コードと長さ部とが順次に出力され、ランレングスデータが算出される。
【０１５９】
図２７は、色コード分割処理が行われた図１７に示すＯＳＤ表示パターンに対し、差分ランレングスを求めて符号化した場合の効果を示す表である。
【０１６０】
図２７において、“長さ部ビット数（変更前）”は、差分ランレングスを求める前の長さ部のビット数を示している。“ランレングス”は、差分ランレングスを求める前のランレングスの範囲を示している。“ベース値”は、差分ランレングスを求める際に使用されたランレングスの最小値である。“最大差分ランレングス”は、差分ランレングスの最大値である。“長さ部ビット数（変更後）”は、差分ランレングスを求めた場合の長さ部のビット数を示している。“ラン数”は、各色コードにおけるランの数を示している。“符号長削減量”は、差分ランレングスを採用したことによる符号長の削減量を色コード別に示している。
【０１６１】
例えば、色コード１について、差分ランレングスを求めずに、ランレングスを符号化した場合、長さ部のビット数は１２ビットであった。一方、色コード１について、差分ランレングスを求めて符号化を行うと、長さ部のビット数は０ビットとなった。色コード１のラン数は２であるため、符号長削減量は、２×１２＝２４ビットとなった。
【０１６２】
同様に、色コード６については、符号長削減量は、４６３×６＝２７７８ビットとなった。他の色コードは、符号長削減量は０であった。よって、符号長削減量の合計は２８０２であった。
【０１６３】
一方、差分ランレングスを求めずにランレングス符号化した場合のランレングスデータの符号長は１３３９５ビットであった。よって、差分ランレングスを求めることにより、ランレングスデータの符号長は、１３３９５−２８０２＝１０，５９３ｂｉｔとなる。
【０１６４】
図２８は、実施例２の結果をまとめた表である。色コード分割処理及びベース値処理を適用しない場合、つまり、従来のランレングス符号化を用いた場合、図１７に示すＯＳＤ表示パターンの符号長は１７，５６３ビットであった。一方、色コード分割処理のみ適用した場合、図１７に示すＯＳＤ表示パターンの符号長は、１３，３９５ビットであった。また、色コード分割処理及びベース値処理を適用した場合、図１７に示すＯＳＤ表示パターンの符号長は、１０，５９３ビットであった。
【０１６５】
なお、本実施の形態では、色コード分割処理とベース値処理及びランレングス符号化処理とが組み合わされていたが、これに限定されず、色コード分割処理のみ行ってランレングスデータを生成してもよい。また、ベース値処理及びランレングス符号化処理のみ行ってランレングスデータを生成してもよい。
【０１６６】
また、上記説明では、各色コードにつき、差分ランレングスを表すことができる最小のビット数を長さ部のビット数として採用したが、これに限定されず、各色コードにつき、差分ランレングスで表された全ランの符号化結果が最小となるビット数を長さ部のビット数として採用してもよい。
【符号の説明】
【０１６７】
１１  画像取得部
１２  テーブル保持部
１３  色コード割当部
１４  符号化部
１６  ランレングスデータ保持部
５１  ベース値テーブル保持部
５２  色情報保持部
５３  差分ランレングス抽出部
５４  加算部
５５  復号化部
【図１】
2012249061.tif 000003
【図２】
2012249061.tif 000004
【図３】
2012249061.tif 000005
【図４】
2012249061.tif 000006
【図５】
2012249061.tif 000007
【図６】
2012249061.tif 000008
【図７】
2012249061.tif 000009
【図８】
2012249061.tif 000010
【図９】
2012249061.tif 000011
【図１０】
2012249061.tif 000012
【図１１】
2012249061.tif 000013
【図１２】
2012249061.tif 000014
【図１３】
2012249061.tif 000015
【図１４】
2012249061.tif 000016
【図１５】
2012249061.tif 000017
【図１６】
2012249061.tif 000018
【図１７】
2012249061.tif 000019
【図１８】
2012249061.tif 000020
【図１９】
2012249061.tif 000021
【図２０】
2012249061.tif 000022
【図２１】
2012249061.tif 000023
【図２２】
2012249061.tif 000024
【図２３】
2012249061.tif 000025
【図２４】
2012249061.tif 000026
【図２５】
2012249061.tif 000027
【図２６】
2012249061.tif 000028
【図２７】
2012249061.tif 000029
【図２８】
2012249061.tif 000030
【図２９】
2012249061.tif 000031
【図３０】
2012249061.tif 000032
【図３１】
2012249061.tif 000033
【図３２】
2012249061.tif 000034