画像処理装置および画像処理方法
【課題】画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化されたランの情報を適切に保存する。
【解決手段】初期化処理部３２は、メモリ３１を初期化し、各ランの符号化情報を格納するためのランデータ構造と、符号化情報を格納可能なランの最大値とを設定する。ランデータ構造には、符号化情報を格納するランと同じクラスのランのうちラスタ走査方向の最上流側に位置するランを記憶する帰属元ランフィールドと、上記ランの画像種別を記憶する画像種別フィールドと、上記ランの長さを記憶するランレングスフィールドとを設け、画像種別をデフォルト値に設定しておく。ランレングス符号化処理部３３は、符号化したランの数がメモリ３１に格納可能なランの数の最大値より１つ小さい値に達すると、残りの画素をデフォルト値に対応する画像種別の単一のランとみなして符号化し、符号化処理を終了する。
【解決手段】初期化処理部３２は、メモリ３１を初期化し、各ランの符号化情報を格納するためのランデータ構造と、符号化情報を格納可能なランの最大値とを設定する。ランデータ構造には、符号化情報を格納するランと同じクラスのランのうちラスタ走査方向の最上流側に位置するランを記憶する帰属元ランフィールドと、上記ランの画像種別を記憶する画像種別フィールドと、上記ランの長さを記憶するランレングスフィールドとを設け、画像種別をデフォルト値に設定しておく。ランレングス符号化処理部３３は、符号化したランの数がメモリ３１に格納可能なランの数の最大値より１つ小さい値に達すると、残りの画素をデフォルト値に対応する画像種別の単一のランとみなして符号化し、符号化処理を終了する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画素の連結領域にラベルを付けて各連結領域を分類するラベリング処理を行う画像処理装置および画像処理方法に関するものである。
【背景技術】
【０００２】
従来より、画像データに対する処理を領域毎に区別して行って処理の効率化を図ったり、画像データのデータサイズを小さしたりするために、画像上の画素の集合（連結領域）毎に番号（ラベル）をつけることで画素を分類するラベリング処理が知られている。ラベリング処理によって分類された各領域は、例えば、領域特性を決定するため、領域が属するオブジェクトの分類を識別するため、あるいは領域毎に特定の処理を適用するために、各領域に応じた所定の処理を施される。典型的な処理としては、例えば、領域内の全要素に対して領域固有のフィルタを用いてフィルタリングを行う処理が挙げられる。
【０００３】
連結要素を領域に分類する処理は連結成分ラベリング（connected component labeling）と呼ばれる。また、そのようなアルゴリズムは、連結成分アルゴリズム（connected-component algorithms）と呼ばれる。
【０００４】
例えば、特許文献１には、ＭＨ符号化された画像データを復号することによりランを生成し、先行するランと当該ランとの連結を調べ、連結しているときは先行するランに割り当てられたラベルと同一のラベルを当該ランに割り付け、ラベルの割り付けられた当該ランが異なるラベルの他の複数のランと連結しているとき、それらラベル間にリンクを張ることにより連結している複数のランを統合して１つの連結成分を切り出す技術が開示されている。なお、特許文献１の技術では、各ランの始点座標（ｘ，ｙ）と、各ランの長さと、各ランのラベルとがランテーブルに格納される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−１１１７８２号公報（平成８年４月３０日公開）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１の技術には、符号化されるランの数がメモリに格納可能なランの数を超過する場合に、既に符号化したランの情報が上書きされ、必要な情報が失われてしまうという問題がある。
【０００７】
本発明は、上記の課題に鑑みてなされたものであり、その目的は、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化されたランの情報を適切に保存することができる画像処理装置および画像処理方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の画像処理装置は、上記の課題を解決するために、画像データにおける各画素の画像種別を示す情報であるクラスマップデータから、同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化処理部と、符号化した符号化データを格納する記憶手段とを備えた画像処理装置であって、符号化に先立って上記記憶手段を初期化する初期化処理部を備え、上記初期化処理部は、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定し、上記ランレングス符号化処理部は、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【０００９】
また、本発明の画像処理方法は、画像データにおける各画素の画像種別を示す情報であるクラスマップデータから同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号工程と、符号化したデータを記憶手段に格納する記憶工程とを含む画像処理方法であって、符号化処理工程に先立って上記記憶手段を初期化する初期化処理工程を含み、上記初期化処理工程では、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定し、上記ランレングス符号化処理工程では、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００１０】
上記の構成によれば、初期化処理において、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定する。
【００１１】
また、ランレングス符号化処理において、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行う。
【００１２】
そして、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００１３】
これにより、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【００１４】
また、上記初期化処理部は、上記記憶手段に格納可能な１走査ラインあたりのランの数の最大値であるライン最大値を設定し、上記ランレングス符号化処理部は、各走査ラインについて、符号化情報を生成したランの数が上記ライン最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない当該走査ラインについての残りの画素数に更新し、画像種別については上記デフォルト値のままにすることによって生成し、当該走査ラインについての符号化処理を終了する構成であってもよい。
【００１５】
上記の構成によれば、画像データをランレングス符号化する際、画像データの各ラインに含まれるランの数がメモリに格納可能な１ラインあたりのランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【００１６】
また、上記初期化処理部は、上記ランデータ構造を走査ライン毎に生成し、上記ランレングス符号化処理部は、各ランの符号化情報を当該ランが属する走査ラインに対応する上記ランデータ構造を用いて生成する構成としてもよい。
【００１７】
上記の構成によれば、画像種別情報についてのデフォルト値を走査ライン毎に設定できる。これにより、画像データの末尾のランをデフォルト値に符号化する場合であっても、これら各ランの画像種別を実際の画像データに近づけることができる。
【００１８】
また、上記初期化処理部は、初期化時に上記画像種別情報として設定する上記デフォルト値を、上記画像データにおける背景領域を示す値に設定する構成としてもよい。
【００１９】
上記の構成によれば、一般に画像データにおける末尾部分の画像は背景画像であることが多いので、画像データの末尾のランをデフォルト値に符号化する場合であっても、これら各ランの画像種別を画像データにおける背景領域に設定することにより、実際の画像データにより近づけることができる。
【発明の効果】
【００２０】
以上のように、本発明の画像処理装置および画像処理方法は、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００２１】
これにより、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【図面の簡単な説明】
【００２２】
【図１】クラスマップの一例を示す説明図である。
【図２】図１に示したクラスマップの変形例を示す説明図である。
【図３】ランレングス符号化されたクラスマップの一例を示す説明図である。
【図４】図３に示したクラスマップにおける各ランの連結性を示す連結性グラフである。
【図５】本発明の一実施形態にかかる画像処理装置におけるラベリング処理の流れを示すフローチャートである。
【図６】クラスマップの一例を示す説明図である。
【図７】図７に示したクラスマップの連結性グラフの一例である。
【図８】図６に示したクラスマップの第１ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図９】図６に示したクラスマップの第２ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１０】図６に示したクラスマップの第３ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１１】図６に示したクラスマップの第４ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１２】図６に示したクラスマップの第５ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１３】図６に示したクラスマップの第６ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１４】図６に示したクラスマップの第７ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１５】図５に示したフローチャートの変形例である。
【図１６】図５に示したフローチャートの変形例である。
【図１７】図５に示したフローチャートの変形例である。
【図１８】本発明の一実施形態にかかる画像処理装置におけるラベリング処理の流れを示すフローチャートである。
【図１９】本発明の一実施形態にかかる画像処理装置におけるランレングス符号化処理の流れを示すフローチャートである。
【図２０】図６に示したクラスマップに対する処理を説明するための説明図である。
【図２１】図６に示したクラスマップに対する処理を説明するための説明図である。
【図２２】本発明の一実施形態における初期化処理をコンピュータに実行させるためのコードの一例である。
【図２３】本発明の一実施形態におけるランレングス符号化処理および隣接ラン統合処理をコンピュータに実行させるためのコードの一例である。
【図２４】本発明の一実施形態におけるランレングス符号化処理および隣接ラン統合処理をコンピュータに実行させるためのコードの他の例である。
【図２５】本発明の一実施形態におけるラベリング結果の一例を示す表である。
【図２６】本発明の一実施形態における圧縮処理をコンピュータに実行させるためのコードの例である。
【図２７】本発明の一実施形態におけるラベリング結果の他の例を示す表である。
【図２８】本発明の一実施形態におけるランレングスデータ構造をインデックス化する処理をコンピュータに実行させるためのコードの例である。
【図２９】本発明の一実施形態におけるラベル画像の生成処理をコンピュータに実行させるためのコードの例である。
【図３０】本発明の一実施形態にかかる画像処理装置の概略構成を示すブロック図である。
【図３１】図３０に示した画像処理装置におけるメモリの初期化処理を説明するための説明図である。
【発明を実施するための形態】
【００２３】
本発明の一実施形態について説明する。なお、説明の便宜上、同様の機能を有する部材については同じ符号を付してその説明を省略する場合がある。
【００２４】
図３０は、本実施形態にかかる画像処理装置３０の概略構成を示すブロック図である。なお、この画像処理装置３０は、例えば画像読取装置、画像形成装置、画像送信装置、画像記録装置、あるいは複合機などに備えられるものであってもよく、これらの装置に通信可能に接続されるものであってもよい。
【００２５】
図３０に示したように、画像処理装置３０は、メモリ（記憶手段）３１、初期化処理部３２、ランレングス符号化処理部（ＲＬＥ処理部）３３、連結パス圧縮部３４、ラベル圧縮部３５を備えている。
【００２６】
図５は、画像処理装置３０における処理の流れを概略的に示したフローチャートである。
【００２７】
図５に示すように、まず、初期化処理部３２が、画像処理装置３０に入力されるクラスマップ（クラスマップデータ）のランレングス符号化処理を開始する前に、メモリ３１の初期化処理を行う（Ｓ８０）。
【００２８】
クラスマップとは、画像データに含まれる各要素（典型的には各画素）を当該各要素の画像種別（クラス）毎に分類したデータである。なお、画像処理装置３０に入力されるクラスマップは、各要素の種別（クラス）を判別できるものであればよく、そのデータ形式は特に限定されるものではない。また、クラスマップは、画像処理装置３０が備えられる画像読取装置、画像形成装置、画像送信装置、画像記録装置、あるいは複合機における他の処理ブロックから画像処理装置３０に入力されてもよく、画像処理装置３０に対して通信可能に接続される外部装置から画像処理装置３０に送信されてもよい。また、画像処理装置３０に着脱可能に装着される記録媒体から画像処理装置３０が読み出すようにしてもよい。
【００２９】
図１は、典型的なクラスマップの一例を示す説明図である。図１では、同じ要素タイプに分類される各要素を同様の模様で示している。具体的には、図１に示したクラスマップ２には、６つの領域４、６、８、１０、１２、１４が含まれており、これら６つの領域に属する要素が５つの異なるクラスに分類されている。つまり、領域１０内の要素と領域１２内の要素とは同一のクラスに属する。
【００３０】
クラスマップの一例としては、画像要素を文字領域、写真領域、および網点領域に分類する領域分離システムによる処理結果が挙げられる。また、クラスマップの他の例としては、空（sky）と地表（grass）のように、画像中の被写体等のオブジェクトを分類するシステムの処理結果が挙げられる。当業者であれば、画像処理アプリケーションにおいて多様なタイプのクラスマップが生じ得ることを容易に理解できるであろう。
【００３１】
連結成分ラベリングアルゴリズムは、同じラベルを有する複数の隣接要素を成分としてグループ化する。また、各成分に属する要素同士に同じ処理が適用されるように、各成分に固有のラベルを割り当てる。
【００３２】
図２は、クラスマップの他の例を示す説明図である。この図に示すクラスマップ２０に含まれる領域２２、２４、２６、２８、３０、３２は、それぞれ図１のクラスマップ２における領域４、１０、８、６、１２、１４に対応している。ただし。図１では同じクラスに属する領域１０，１２に対して同じラベルが割付けられていたのに対して、図２では領域２４，３０に別々の固有のラベルが割り当てられている。
【００３３】
初期化処理部３２によって初期化処理が行われた後、ランレングス符号化処理部３３が、ランレングス符号化（ＲＬＥ）／隣接ラン統合処理を行い（Ｓ８２）、処理結果（符号化データ）をメモリ３１に格納する。すなわち、ランレングス符号化処理部３３は、画像処理装置３０に入力されるクラスマップに対してランレングス符号化処理をラスタ方向に沿って順次行うとともに、同じクラスに属し、かつ互いに隣接するラン同士を関連付ける統合処理を行う。なお、ランとは、同じクラスに属し、かつライン（走査ライン）の延伸方向（走査ライン方向）に隣接する画素同士を連結した連結成分である。また、クラスの種類としては、例えば、テキスト、局所背景、ページ背景、絵図、線図などが挙げられる。
【００３４】
なお、ランレングス符号化のアルゴリズムは特に限定されるものではなく、例えば、特定の演算装置に適応するように最適化されたものであってもよい。また、各成分を構成する要素の連結関係を検出してキャッシュに入れる処理を行うための最適な構成になるように連結成分アルゴリズムを構成してもよい。なお、成分の複合的な形状や大面積の成分を考慮することの必要性により、要素同士の連結性を効率的に検出するためのアルゴリズムの設計は複雑になる場合もある。
【００３５】
また、ランレングス符号化の方法には、連結成分に対するラベリングを反復的に行う反復法、連結成分に対するラベリングを再帰的に行う再帰法、および反復法と再帰法という２つの基本的な方法を組み合わせたハイブリッド連結成分ラベリング法（ハイブリッド法）がある。
【００３６】
反復法では、開始画素から追加の画素が当該領域（成分）に加えられなくなるまで、すなわち当該領域の成長が終わるまで、クラスマップ内全体に渡って同じラベル（インデックス）が反復的に付与される。この方法では、データ全体に対する反復回数が連結領域に属する要素の数と等しくなるので、演算の負荷が大きくなる。ただし、反復法では、メモリ使用量およびアクセスパターンを予測可能である。
【００３７】
再帰法では、ラベリングされていない要素からラベリング処理を開始する。この方法では、ラベリング処理対象の要素に隣接する隣接要素、およびこの隣接要素に隣接する要素を再帰的に調べる。上記の再帰を、スタック構成（stack construct）を用いて行ってもよい。連結している隣接要素をスタックから抽出して調べたり、連結している隣接要素をスタックに加えたりする処理をスタックが空になるまで行う。再帰法は、反復法に比べて演算負荷を低減できる。ただし、メモリ使用量が画像データに応じて異なり、アクセスパターンがランダムであるので、メモリ使用量およびアクセスパターンを予測することは困難である。
【００３８】
ハイブリッド法では、メモリアクセスパターンを簡単な処理で概略的に予測することができる。第１の処理では、単純な凸位相（convex topologies）の成分を１つの領域にグループ化するが、より複雑な位相の成分はさらに複数の副成分に分割される。これら各副成分は後に統合される。ハイブリッド法では、分割された副成分を統合するために、これら各副成分の連結性を再帰的に追跡する。ハイブリッド法を用いる場合には有限併合再帰（bounded merge recursion）を行うことがより好ましい。
【００３９】
ハイブリッド法は２つのステップを含む。第１のステップでは、各要素を隣接する連結要素とリンクさせたサブグラフを構築する。第２のステップでは、各サブグラフを識別するためにサブグラフを連結させたグラフの頂点を解析する。なお、連結された各サブグラフは連結成分を構成する。
【００４０】
ハイブリッド法によって生成されるグラフは、各要素（基本要素）に対応する頂点を有しており、同じクラスタイプを有する隣接する頂点同士はリンクされている。上記要素は、典型的には画素（ピクセル）である。このグラフデータ構造は、連結成分にラベリングを行うためのメモリおよび演算処理という観点からは必ずしも最適ではない。なお、グラフ構造を解析する前に同様のクラスタイプを有する複数の要素をグループ化することによって上記処理を簡略化してもよい。ラスタ形式の画像では、ラスタラインに沿って連結された同じクラスに属する複数の画素（ラン）は単一の頂点にグループ化されメモリ内において同一の位置に配置される。このグループ化により、グラフ内の頂点の数およびリンクの数を低減できる。複数のラインの読み出しおよびラインを横断したグループ化を行う構成ではそれによってさらなる利点を得ることができる。
【００４１】
ランレングス符号化（ＲＬＥ）／隣接ラン統合処理において、クラスマップをランレングス符号化（ＲＬＥ）してＲＬＥマップを形成するステップと、同じクラスに属する隣接し合う複数のランを統合した統合ＲＬＥマップを形成し、統合ＲＬＥマップから領域情報を抽出するステップの２つのステップを行うようにしてもよい。この場合、画像中の各クラスに対して固有のラベルを割り当てたクラスマップは、同一ライン内における同じクラスのラベルを有する画素を連結してランレングス符号化される。また、ＲＬＥマップ内においてラインをまたがって連結されたランを抽出することによって領域特性が検出される。
【００４２】
図３はクラスマップの一例を示す説明図である。この図に示すクラスマップ３８は、Ｒ０〜Ｒ１１で示される１２個のランを含む４つのラインを含んでいる。また、クラスマップ３８は２つのクラス、すなわち白いブロックで示されたランＲ０，Ｒ２，Ｒ４，Ｒ６，およびＲ９を含むクラスと、灰色のブロックで示されたランＲ１，Ｒ３，Ｒ５，Ｒ７，Ｒ８，Ｒ１０，およびＲ１１を含むクラスとを有している。
【００４３】
図４は、図３に示したクラスマップ３８における灰色のクラスに属するランの連結性を示すグラフ（連結性グラフ）６０を示している。グラフ６０は、ラン６２，６４，６８，７０，７２，および７４（ランＲ１，Ｒ３，Ｒ５，Ｒ７，Ｒ８，Ｒ１０，およびＲ１１）の各頂点の連結関係と、隣接性を示すリンク６３，６５，６７，６９，７１，および７３を示している。この図に示したように、頂点間の経路長は各要素間で大幅に異なる場合がある。このため、データから算出される経路長によっては、メモリおよび演算処理のアルゴリズムを実際の装置に適用すると必要なメモリ容量が大きくなったり、装置構成が複雑になったりする場合がある。
【００４４】
本実施形態では、ランレングス符号化されたデータを格納するメモリ３１として、固定サイズのメモリ（メモリバッファ）を用いる。なお、このメモリ３１には、後述するように、入力データに依存しない所定の最大実行経路長（maximum execution path lengths）を有するデータが格納される。つまり、本実施形態では、メモリ３１に格納するデータの最大実行経路長およびメモリ３１の設置面積（memory footprint）を固定値とする。したがって、本実施形態は、ＡＳＩＣ（Application Specific Integrated Circuit;特定用途向け集積回路）やＳＩＭＤ（single-instruction multiple-data-pathD）ＤＳＰ（digital signal processing）への実装に特に適している。
【００４５】
なお、メモリ３１に格納されるデータのデータ構造は、クラスマップの列数および行数に関連付けられてもよい。また、上記データ構造は、符号化されたランに関連付けられてもよい。また、このランに関連付けられたデータ構造であるランデータ構造は、各ランに関連付けられたパラメータ、例えば、各ランの帰属元ラン（親ラン）、各ランの属するクラス、各ランのランレングス（ランの長さ）などのパラメータを含んでいてもよい。また、このランデータ構造は、所定の最大ラン数に達するまでは各ランを関連付けて記憶し、各ランにラン番号インデックスを付与することによって各ランを識別するものであってもよい。また、所定の最大ラン数に達した後は残りのランを、デフォルトクラス（例えば背景領域のクラス）に属する単一のランとして記憶させるようにしてもよい。
【００４６】
また、上記ランデータ構造を、クラスマップにおける各ラインのスターティングラン（符号化開始ラン）、すなわちラスタ方向の最上位（最上流側）に位置するランに関連付けてもよい。例えば、上記ランデータ構造における各ラインをスターティングランに関連付けたスターティングランデータ構造において、クラスマップにおける各ラインに対応するランデータ構造内に、当該ラインにおけるスターティングランを示すメモリ参照情報（memory reference）を記憶させてもよい。また、スターティングラン構造は、各ラインに関連付けて記憶されるものであってもよく、ライン番号のインデックスによって識別されるものであってもよい。
【００４７】
また、処理対象のライン（走査線）のクラスマップデータを記憶する入力クラスマップバッファを用いてもよい。また、処理対象のライン（走査線）に対する連結成分ラベルの付与結果を記憶する連結成分ラベル出力バッファを用いてもよい。また、上記データ構造を、演算装置に近接する位置に配置されるローカルバッファ内に格納してもよい。
【００４８】
上記データ構造内の一部のパラメータは、入力データ毎に異なってもよい。また、その他のパラメータは、連結成分アルゴリズムを実現するためのシステムに固有のものであってもよい。また、クラスマップパラメータは、システムアプリケーションに応じて決定されてもよい。
【００４９】
一般に、複合機（multi-function peripheral; MFP）等の典型的なアプリケーションでは、走査解像度は固定値の中から選択される。上記の各パラメータを上記固定値の最大値に対応するように設定することにより、大部分のデータ構造に要求される最低限の要件が決定される。残りのパラメータは、入力クラスマップデータに応じて算出されるランの数によって決定される。
【００５０】
オンチップキャッシュまたは内部バッファの容量は有限であり、メモリ３１に格納可能なランの数は、符号化されるランの数が内部バッファの容量の上限を超えないように制限される。ランの最大数は、例えばシステムのコストと、処理される入力データの複雑さとのバランスを考慮して決定される。
【００５１】
各ランがデフォルトクラスに属するものとして符号化した入力クラスマップのライン数と同数のラン（スターティングラン）をランデータ構造の端部に予め生成しておき、その後それらのランを上書きするようにしてもよい。
【００５２】
ランレングス符号化処理部３３によってランレングス符号化（ＲＬＥ）／隣接ラン統合処理が行われた後、連結パス圧縮部３４が、上記統合処理によって統合された各ランの連結関係を示す連結情報（帰属元ラベル）を圧縮する連結パス圧縮処理を行う（Ｓ８４）。
【００５３】
その後、ラベル圧縮部３５が、上記統合処理によっての統合された各成分（同じクラスに属し、互いに隣接するランの集合）に対して成分毎に共通のラベルを付与しなおすラベル圧縮処理を行う（Ｓ８６）。
【００５４】
次に、画像処理装置３０における初期化処理およびランレングス符号化／隣接ラン統合処理について、図１８を参照しながらより詳細に説明する。図１８は初期化処理およびランレングス符号化／隣接ラン統合処理流れを示すフローチャートである。
【００５５】
上述したように、まず、初期化処理部３２が、画像処理装置３０に入力されるクラスマップ（クラスマップデータ）のランレングス符号化処理を開始する前に、メモリ３１の初期化処理を行う（Ｓ３１０）。
【００５６】
図３１は、初期化処理を説明するための説明図である。なお、図３１は、クラスマップのライン数が１００であり、付与可能なラベル数（格納可能なランの数）が１０００個である場合の例を示している。
【００５７】
初期化処理部３２は、画像処理装置３０に入力されたクラスマップを参照し、メモリ３１内にクラスマップにおける縦方向のライン数（０〜９９）に応じた数のスターティングランデータ（スターティングラン構造）と、メモリに格納可能な最大ラン数に応じたランデータ構造を生成する。各ランデータ構造は、当該ランデータ構造に符号化情報を格納するランである格納対象ランのラン番号（ラベル；ランインデックス、０〜９９９）を格納するための格納対象ランフィールド、上記格納対象ランの帰属元ランを示す帰属元情報（帰属元ラベル）を格納（記憶）するための帰属元ランフィールド、上記格納対象ランが属するクラス（画像種別）を示す画像種別情報を格納するための画像種別フィールド、および上記格納対象ランの長さ（ランレングス）を示すランレングス情報を格納するためのランレングスフィールドを有している。
【００５８】
帰属元ランとは、同じクラスに属する連結された複数のランのうちラスタ方向の最上位（最上流側）に位置するランである。帰属元ランを示すパラメータとしては例えば帰属元ランのラン番号（ランインデックス）を用いることができる。このラン番号は、例えばラスタ方向の位置に応じて各ランに順次付与すればよい。
【００５９】
なお、初期化処理時には、例えば、スターティングランデータの数を画像データのライン数（クラスマップにおける画像領域の縦方向のサイズ）と同数に設定し、各ランデータ構造における帰属元ランのラベルを当該ランデータ構造に対応する格納対象ランのラベルに設定し、格納対象ランが属するクラスをデフォルトクラス（例えば、当該ランデータ構造に対応するラインのスターティングランの属するクラス、あるいはクラスマップにおける背景領域のクラス）に設定し、ランレングスを画像データにおけるラインの延伸方向の画素数（クラスマップにおける画像領域の横方向の画素数）ｍに設定する。
【００６０】
図２２は、初期化処理をコンピュータに実行させるための典型的な中間コードの例を示している。図２２において、StartingRunはスターティングランデータ構造であり、Class、ParentLabel、およびRunLengthはランデータ構造のフィールド（クラス、帰属元ラベル、およびランレングス）であり、NumberRunLimitはメモリに格納可能な最大ラン数であり、default class valueは各ランのクラスを示すパラメータのデフォルト値であるデフォルトクラスを示し、Number of RowsおよびNumber of Columnsは、クラスマップの行数（ライン数）および列数（１ラインの画素数）を示している。
【００６１】
デフォルトクラスの値は、各ランデータ構造に対応するスターティングランのクラスを示す値に設定してもよい。あるいは、画素が背景画像（背景領域）に属しているか否かが入力クラスマップによって示される場合、デフォルトクラスの値は背景画像を示すクラスの値であってもよい。その場合、初期化処理時には、各ランデータ構造は、出力画像全体が背景画像であることを示す状態になる。そして、初期化処理の後、クラスマップの符号化を開始したときには、ランレングス符号化／隣接ラン統合処理の結果に応じてこれら各パラメータの初期値が上書きされることになる。
【００６２】
メモリ３１のデータ構造の初期化処理（Ｓ３１０）の後、ランレングス符号化処理部３３は、まず、クラスマップの第１ラインのランレングス符号化を行う（Ｓ３１２）。
【００６３】
図１９は、第１ラインのランレングス符号化処理の流れを示すフローチャートである。
【００６４】
まず、クラスマップ内の第１ラインを入力バッファ（図示せず）に入力し、注目要素を当該ラインにおける第１要素、すなわちラスタ方向の最上流側の要素に設定する（Ｓ３８０）。
【００６５】
初期化したデータにおける第１ラインの第１ラン（スターティングラン）InitRunを抽出してキャッシュし（Ｓ３８２）、次のラン（上書き後のラン）NextRunのラン番号を設定する（Ｓ３８４）。
【００６６】
次に、上記第１ランInitRunと次のランNextRunとを比較し（Ｓ３８６）、ＲＬＥ／隣接ラン統合処理を終了して連結パス処理を開始するか（３８７）、あるいはＲＬＥ／隣接ラン統合処理を継続するか（３６０）を判断する。
【００６７】
例えば、未符号化処理のランの数が、クラスマップにおける未符号化処理の各ランをデフォルトクラスに設定することしかできない数になった場合に符号化を終了する。より具体的には、例えば図３１に示したデータ構造の場合、ラン番号９９８（格納可能なランのラン番号の最大値−１）に対するＲＬＥ／隣接ラン統合処理が行われようとする段階で次のランに対するラベル付けは不可であると判断し、ラン番号９９８に対してはデフォルトクラスに対応するパラメータを付与し、ラン番号９９８のランレングスをＲＬＥ／隣接ラン統合処理を行っていない残りの要素の数に設定して符号化処理を終了する。
【００６８】
ＲＬＥ／隣接ラン統合処理を継続する場合には、注目要素が属するラン（注目ラン）のパラメータを設定する（Ｓ３９０）。例えば、帰属元ランを注目ラン自身に設定し、クラスを注目要素のクラスに設定し、ランレングスをゼロ（要素数１に対応）に設定する。
【００６９】
その後、上記の注目要素が第１ラインの最終要素であるかを判定する（Ｓ３９２）。そして、最後の要素である場合（３９３）、第１ラインのランレングス符号化を終了する（Ｓ４０４）。
【００７０】
最後の要素ではない場合（３９４）、注目要素をラスタ順に沿った次の要素に変更する（Ｓ３９６）。そして、この新たな注目要素のクラスが処理中のランのクラス（前回の注目要素のクラス）と同一であるかを判断する（Ｓ３９８）。
【００７１】
そして、同一である場合（４００）、処理中のランのランレングスをインクリメントし（Ｓ４０２）、Ｓ３９２の処理に戻る。一方、同一ではない場合（３９９）、Ｓ３８４に戻る。
【００７２】
第１ラインのランレングス符号化（Ｓ３１２）を行った後、ランレングス符号化処理部３３は、クラスマップの最後のラインに対する処理を行ったか否かを判定する（Ｓ３１４）。そして、最後のラインに対する処理を行ったと判断した場合（３１５）、ＲＬＥ／隣接ラン統合処理を終了し、連結パス圧縮処理を開始する（Ｓ３６０）。
【００７３】
一方、最後のラインに対する処理を行っていないと判断した場合（３１６）、ランレングス符号化処理部３３は、クラスマップの次のラインを入力バッファ（図示せず）に入力し、注目要素を当該ラインにおける第１要素、すなわちラスタ方向の最上流側の要素に設定する（Ｓ３１８）。そして、初期化したデータにおける当該ラインの第１ラン（スターティングラン）InitRunを抽出してキャッシュし（Ｓ３２０）、次のラン（上書き後のラン）NextRunのラン番号を設定する（Ｓ３２２）。
【００７４】
次に、ランレングス符号化処理部３３は、上記第１ランInitRunと次のランNextRunとを比較し（Ｓ３２４）、ＲＬＥ／隣接ラン統合処理を終了して連結パス処理を開始するか（３２５）、あるいはＲＬＥ／隣接ラン統合処理を継続するか（３６０）を判断する。例えば、上述したように、未符号化処理のランの数が、クラスマップにおける未符号化処理の各ランをデフォルトクラスに設定することしかできない数になった場合に符号化を終了する。
【００７５】
ＲＬＥ／隣接ラン統合処理を継続する場合（３２６）、注目要素が属するラン（注目ラン）のパラメータを設定する（Ｓ３２８）。例えば、帰属元ラベルを注目ラン自身に設定し、クラスを注目要素のクラスに設定し、ランレングスをゼロ（要素数１に対応）に設定する。
【００７６】
その後、ランレングス符号化処理部３３は、注目要素のクラスと、既に符号化したライン（注目ラインの１つ前のライン）における上記注目要素に隣接する要素である隣接要素のクラスとを比較する（Ｓ３３０）。例えば、４連結の場合（上、下、左、右の隣接要素の連結性を考慮する場合）には真上に隣接する要素のみと比較すればよく、８連結の場合（上、下、左、右、左上、右上、左下、右下の隣接要素の連結性を考慮する場合）には左上、真上、および右上に隣接する各要素と比較すればよい。
【００７７】
図２３は、４連結に基づくＲＬＥ／隣接ラン統合処理をコンピュータに実行させるための中間コードの一例を示している。また、図２４は、８連結に基づくＲＬＥ／隣接ラン統合処理をコンピュータに実行させるための中間コードの一例を示している。
【００７８】
連結している隣接要素がない場合（注目要素のクラスと隣接要素のクラスとが異なる場合）（３３１）、ランレングス符号化処理部３３は、上記注目要素が当該ラインの最後の要素であるかを判定する（Ｓ３３４）。最後の要素である場合（３３５）、Ｓ３１４の処理に戻る。
【００７９】
一方、最後の要素ではない場合（３３６）、ランレングス符号化処理部３３は、注目要素をラスタ順に沿った次の要素にする（Ｓ３３８）。そして、この新たな注目要素のクラスが処理中のランのクラス（前回の注目要素のクラス）と同一であるかを判断する（Ｓ３４０）。
【００８０】
そして、同一である場合（３４２）、処理中のランのランレングスをインクリメントし（Ｓ３４４）、Ｓ３３０の処理に戻る。一方、同一ではない場合（３４１）、Ｓ３２２の処理に戻る。
【００８１】
一方、Ｓ３３０において注目要素のクラスと１つ前のラインにおける隣接要素のクラスとが同じであると判断した場合（３３２）、ランレングス符号化処理部３３は、注目要素の帰属元ラン（Current Parent）と、上記隣接要素の帰属元ラン（Adjacent Parent）とを比較する（Ｓ３４６）。
【００８２】
そして、注目要素の帰属元ラン（Current Parent）の方が隣接要素の帰属元ラン（Adjacent Parent）よりも連結性ツリー（連結性グラフ）の上位にある場合、すなわちラスタ方向の上流側に位置するランである場合（３４８）、隣接要素の帰属元ランの帰属元ランを注目要素の帰属元ランに更新する（Ｓ３５０）。さらに、隣接要素が属するランの帰属元ランを注目要素の帰属元ランに更新し（Ｓ３５２）、Ｓ３３４の処理に戻る。
【００８３】
一方、注目要素の帰属元ラン（Current Parent）の方が隣接要素の帰属元ラン（Adjacent Parent）よりも連結性ツリー（連結性グラフ）の下位にある場合、すなわちラスタ方向の下流側に位置するランである場合（３４７）、注目要素の帰属元ランの帰属元ランを隣接要素の帰属元ランに更新する（Ｓ３５１）。さらに、注目要素が属するランの帰属元ランを隣接要素の帰属元ランに更新し（Ｓ３５２）、Ｓ３３４の処理に戻る。
【００８４】
次に、図６〜図１４を参照しながらＲＬＥ／隣接ラン統合処理についてより詳細に説明する。
【００８５】
図６は、クラスマップの一例およびこのクラスマップに対するＲＬＥ／隣接ラン統合処理の一例を示す説明図である。この図に示すクラスマップ８９は、７つのライン（列とみなすこともできる）９０〜９６と、白と灰色で示した２つのクラスからなるラン１０１〜１３０（Ｒ１〜Ｒ３０）とを含んでいる。
【００８６】
図７は、図６に示したクラスマップ８９における灰色のラン１０１、１０３、１０５、１０７、１０９、１１１、１１２、１１４、１１６、１１８、１１９、１２１、１２３、１２５、１２６、１２８、および１２９の連結性を示す連結性グラフ１４０を示している。連結性グラフ１４０では、ランは頂点１４１〜１５７として示されている。また、連結性グラフ１４０では、隣接するランはリンク１６０〜１７５で連結されている。
【００８７】
なお、図７には図６における灰色のクラスに属するランの連結性を示したが、白色のクラスに属するラン１０２、１０４、１０６、１０８、１１０、１１３、１１５、１１７、１２０、１２２、１２４、１２７、１３０についても同様に連結性グラフを作製することができる。
【００８８】
以下の説明では、ランを、「Ｒ」および参照ラン番号で示す。例えば、第１のラン１０１はＲ１、２２番目のラン１２２はＲ２２と示す。
【００８９】
まず、クラスマップ８９の第１ライン９０をランレングス符号化する。第１ライン９０をランレングス符号化した後、２つのラン１０１（Ｒ１）および１０２（Ｒ２）をライン９０に関連付ける。また、第１のラン１０１（Ｒ１）を第１クラス（灰色）に関連付け、第２のラン１０２（Ｒ２）を第２クラス（白色）に関連付ける。すなわち、第１のラン１０１（Ｒ１）には第１クラスに対応するラベルを割付け、第２のラン１０２（Ｒ２）には第２クラスに対応するラベルを割付ける。ラン１０１（Ｒ１）および１０２（Ｒ２）に、帰属元ラン（親ラン）として自身を指し示す値を付与する。すなわち、第１のラン１０１（Ｒ１）は、図８（ａ）のグラフ１８０に示すように、帰属元ラン（親ラン）として自身を指し示すリンク２５１を有する頂点２０１として示される。また、第２のラン１０２（Ｒ２）は、図８（ｂ）のグラフ１８１に示すように、帰属元ラン（親ラン）として自身を指し示すリンク２５２を有する頂点２０２として示される。
【００９０】
クラスマップ８９の第１ライン９０をランレングス符号化した後、第２ライン９１の各要素を検証し、第２ラインのランレングス符号化および隣接ラン（連結ラン）の統合を行う。
【００９１】
具体的には、第３のラン１０３（Ｒ３）が抽出され、この第３のラン１０３（Ｒ３）の抽出中に前のライン９０における隣接するラン１０１（Ｒ１）が連結性を確認するために検証される。ラン１０３（Ｒ３）はラン１０１（Ｒ１）と同じクラスなので、それぞれの帰属元ラン（親ラン）が検出され、ラン１０１（Ｒ１）がラン１０３（Ｒ３）の帰属元ランとして検出される。
【００９２】
同様に、第４のラン１０４（Ｒ４）が抽出され、その帰属元ランとしてラン１０２（Ｒ２）が検出される。また、第５のラン１０５（Ｒ５）が抽出され、第５のラン１０５（Ｒ５）に隣接する前のライン９０における全てのランは第５のラン１０５（Ｒ５）とは異なるクラスなので、第５のラン１０５（Ｒ５）の帰属元ランはこの時点ではラン１０５（Ｒ５）自身に設定される。また、第６のラン１０６（Ｒ６）が抽出され、その帰属元ランとしてラン１０２（Ｒ２）が検出される。
【００９３】
図９（ａ）および図９（ｂ）は、第２ライン９１に対する処理によって抽出された各ランを示している。第３のラン１０３（Ｒ３）は、図９（ａ）のグラフ１８２では、帰属元ラン（親ラン）としてランＲ１（頂点２０１）を指し示すリンク２５３を有する頂点２０３として示されている。第５のラン１０５（Ｒ５）は、図９（ａ）のグラフ１８２では、帰属元ラン（親ラン）としてランＲ５自身を指し示すリンク２５５を有する頂点２０５として示されている。第４のラン１０４（Ｒ４）および第６のラン１０６（Ｒ６）は、図９（ｂ）のグラフ１８３では、それぞれ帰属元ラン（親ラン）としてランＲ２（頂点２０２）を指し示すリンク２５４，２５６を有する頂点２０４，２０６として示されている。
【００９４】
クラスマップ８９における第２ライン９１のランレングス符号化が終わると、第３ライン９２の要素を検証し、第３ライン９２のランレングス符号化、および隣接ランの統合を行う。第７のラン１０７（Ｒ７）が検出され、この第７のラン１０７（Ｒ７）に隣接するラン１０３（Ｒ３）がこの第７のラン１０７（Ｒ７）と同一クラスに属するので、連結性ツリー（連結性グラフ）における当該クラスの最上位のラン（帰属元ラン）として検出される。本実施形態では、最上位のランは、連結されたランのうちラン番号のもっとも小さいものである。
【００９５】
第７のラン１０７（Ｒ７）に隣接する同一クラスのランはラン１０３（Ｒ３）であるが、図６に示すように、連結された同一クラスのランの中にラン１０３（Ｒ３）よりも上位のラン１０１（Ｒ１）が存在するので、第７のラン１０７（Ｒ７）の帰属元ランはラン１０１（Ｒ１）であると判定される（図１０（ａ）参照）。
【００９６】
同様に、第８のラン１０８（Ｒ８）および第１０のラン１０（Ｒ１０）に隣接する同一クラスのランはラン１０４（Ｒ４）であるが、図６に示すように、連結された同一クラスのランの中にラン１０４（Ｒ４）よりも上位のラン１０２（Ｒ２）が存在するので、第８のラン１０８（Ｒ８）および第１０のラン１０（Ｒ１０）の帰属元ランはラン１０２（Ｒ２）であると判定される（図１０（ｂ）参照）。
【００９７】
第９のラン１０９（Ｒ９）は自身がその帰属元として検出され、ラン１１１（Ｒ１１）の帰属元ランとしてはラン１０５（Ｒ５）が検出される（図１０（ａ）参照）。
【００９８】
図１０（ａ）および図１０（ｂ）に示されているグラフ１８４，１８５は、第３ライン９２に対する処理で検出されるランとそれに連結されるランとの関係を示している。頂点２０１〜２１１は帰属元ランに関連付けられたランを示しており、リンク２５１〜２６１は各ランの連結関係を示している。
【００９９】
図１１（ａ）および図１１（ｂ）に示されているグラフ１８６，１８７は、第４ライン９３に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２１８はラン１０１〜１１８（Ｒ１〜Ｒ１８）に対応しており、リンク２５１〜２６８は上記各ランの連結関係を示している。
【０１００】
図１２（ａ）および図１２（ｂ）に示されているグラフ１８８，１８９は、第５ライン９４に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２２５はラン１０１〜１２５（Ｒ１〜Ｒ２５）に対応しており、リンク２５１〜２７５は上記各ランの連結関係を示している。なお、ラン１２４（Ｒ２４）に対する処理を行う際、初期段階として、このラン１２４（Ｒ２４）内の要素はラン１１５（Ｒ１５）に隣接しており、帰属元ランはラン１０２（Ｒ２）であると判定される。次に、このラン１２４（Ｒ２４）に隣接する第３ライン９２のラン１１７（Ｒ１７）について、第３ライン９２に対する処理を完了した時点ではその帰属元ランはラン１１７（Ｒ１７）自身であるが、このラン１１７（Ｒ１７）に隣接する同一クラスのラン１２４（Ｒ２４）の帰属元ランがラン１１７（Ｒ１７）よりもラン番号が小さいラン１０２（Ｒ２）であることから、その帰属元ランはラン１０２（Ｒ２）に更新される。つまり、第５ライン９４に対する処理の最後に第４ライン９３に属するラン１１７（Ｒ１７）の帰属元ランが第２ラン１０２（Ｒ２）に更新される。なお、この処理対象のライン（注目ライン）よりも前のラインに属するランの帰属元ランを更新する処理は、例えば注目ラインに対する処理が終わる毎に行ってもよく、注目ラインに属する各ランに対する処理が終わる毎に行ってもよい。
【０１０１】
図１３（ａ）および図１３（ｂ）に示されているグラフ１９０，１９１は、第６ライン９５に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２２８はラン１０１〜１２８（Ｒ１〜Ｒ２８）に対応しており、リンク２５１〜２７８は上記各ランの連結関係を示している。第２８ラン１２８（Ｒ２８）の最初の要素に対する処理では帰属元ランはラン１０９（Ｒ９）であると判定されるが、第２８ラン１２８（Ｒ２８）における最後の方の要素に対する処理において帰属元ランは最終的にラン１０５（Ｒ５）に更新される。
【０１０２】
図１４（ａ）および図１４（ｂ）に示されているグラフ１９２，１９３は、第７ライン９６に対する処理によって検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２３０はラン１０１〜１３０（Ｒ１〜Ｒ３０）に対応しており、リンク２５１〜２８０は上記各ランの連結関係を示している。第２９のラン１２９（Ｒ２９）に対する処理により、その帰属元ランは第１のラン１０１（Ｒ１）であると判定される。そして、その結果、第６ライン９５に属するラン１２８（Ｒ２８）およびそれに連結された各ランの帰属元ランはラン１０５（Ｒ５）から第１のラン１０１（Ｒ１）に更新される。
【０１０３】
図２１は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を施す際の帰属元の更新処理を説明するための説明図である。ラン１２８（Ｒ２８）における最後部の要素４１４を処理する際、処理対象の要素４１４に隣接する要素はラン１２５（Ｒ２５）内の要素４１６であると判定される。処理中の要素４１４の帰属元ランはこの時点ではラン１０９（Ｒ９）であり、隣接する要素４１６の帰属元ランはこの時点ではラン１０５（Ｒ５）である。したがって、処理中の要素４１４の帰属元ラン１０９（Ｒ９）は隣接する要素４１６の帰属元ラン１０５（Ｒ５）よりも連結性ツリー（連結性グラフ）の下位であるので、ラン１２８（Ｒ２８）の帰属元ランはラン１０５（Ｒ５）に更新される。これに伴い、ラン１２８（Ｒ２８）に隣接するラン１２３（Ｒ２３）の帰属元ランおよびそれまでラン１２３（Ｒ２３）の帰属元ランであったラン１０９（Ｒ９）の帰属元ランはラン１０５（Ｒ５）に更新される。
【０１０４】
図２０は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を施す際の帰属元の更新処理を説明するための説明図である。
【０１０５】
ラン１２９（Ｒ２９）における最後部の要素４１０を処理する際、処理対象の要素４１０に隣接する要素はラン１２８（Ｒ２８）内の要素４１２であると判定される。処理中の要素４１０の帰属元ランはラン１０１（Ｒ１）であり、隣接する要素４１２の帰属元ランはこの時点ではラン１０５（Ｒ５）である。したがって、処理中の要素４１０の帰属元ラン１０１（Ｒ１）は隣接する要素４１２の帰属元ラン１０５（Ｒ５）よりも連結性ツリー（連結性グラフ）の上位であるので、隣接する要素４１２を含むラン１２８（Ｒ２８）の帰属元ランおよびそれまでラン１２８（Ｒ２８）の帰属元ランであったラン１０５（Ｒ５）の帰属元ランはラン１２９（Ｒ２９）の帰属元ランと同様、ラン１０１（Ｒ１）に更新される。
【０１０６】
図２５は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を行った結果を示す表である。
【０１０７】
なお、ランレングス符号化／隣接ラン統合処理の後、連結パス圧縮部３４が、各ランの連結関係を示す連結情報（帰属元ラン）を圧縮する連結パス圧縮処理を行う。具体的には、連結パス圧縮部３４は、ランＡの帰属元ランＢの帰属元ランがランＣである場合に、ランＡの帰属元ランをランＣに更新することにより、各ランの帰属元ランを最上位のランに圧縮（集約）する。
【０１０８】
図２６は、この連結パス圧縮処理をコンピュータに実行させるための中間コードの一例を示している。また、図２７は、図２５に示したランレングス符号化／隣接ラン統合処理を行った結果に対して連結パス圧縮処理を行った結果を示す表である。
【０１０９】
また、連結パス圧縮部３４が連結パス圧縮処理を行った後、ラベル圧縮部３５が、連結された各成分（同じクラスに属し、かつ互いに隣接する（連結された）ランの集合）に属する各ランに対して成分毎に共通のラベルを付与しなおすラベル圧縮処理を行う。例えば、上述の実施例（図２７に示した例）の場合、帰属元ランがランＲ１である成分は「０」にラベル付けされ、帰属元ランがランＲ２である成分は「１」にラベル付けされ、帰属元ランがランＲ３０である成分は「２」にラベル付けされる。このように、ランインデックスに代えてクラス毎に順次割り付けたラベルを用いることにより、各成分のクラスを識別するための情報に必要とされるビット深度を低減することができる。なお、このラベル圧縮処理は、例えばハッシュテーブルを用いて行うことができる。
【０１１０】
なお、図１５に示すように、ラベル圧縮処理（Ｓ８６）の後に、領域特性（成分特性）の抽出処理（Ｓ３００）を行うようにしてもよい。例えば、図３０に示した構成に加えて、領域特性抽出処理（図示せず）を設け、この領域特性抽出処理が領域特性の抽出処理を行うようにしてもよい。代表的な成分特性としては、領域面積（region area）、成分の境界線（component bounding box）、成分の重心、成分の境界線の中心（component-bounding-box center）、あるいはその他の領域（成分）の特性を示すパラメータが上げられる。領域特性の抽出処理では、例えばランレングスデータを用いてこれらの成分特性を抽出することができる。図２８は、領域特性の抽出処理をコンピュータに実行させるための中間コードの一例を示している。
【０１１１】
また、図１６に示すように、ラベル圧縮処理（Ｓ８６）の後に、ラベル画像生成処理（ラベル画像再構築処理）（Ｓ３０２）を行ってもよい。例えば、図３０に示した構成に加えて、ラベル画像生成部（図示せず）を設け、このラベル画像生成部がラベル画像生成処理を行うようにしてもよい。ラベル画像とは、各ランを当該各ランのクラス（ラベル）と当該各ランのランレングスとに応じて表現した画像である。図２９は、ラベル画像生成処理をコンピュータに実行させるための中間コードの一例を示している。
【０１１２】
また、図１７に示したように、ラベル圧縮処理（Ｓ８６）の後に、領域特性の抽出処理（Ｓ３００）とラベル画像生成処理（Ｓ３０２）とを行うようにしてもよい。また、この場合、領域特性の抽出処理（Ｓ３００）を行った後にラベル画像生成処理（Ｓ３０２）を行うようにしてもよく、ラベル画像生成処理（Ｓ３０２）を行った後に領域特性の抽出処理（Ｓ３００）を行うようにしてもよく、領域特性の抽出処理（Ｓ３００）とラベル画像生成処理（Ｓ３０２）とを並行して行ってもよい。
【０１１３】
以上のように、本実施形態にかかる画像処理装置３０では、初期化処理部３２が符号化処理を行う前にメモリ３１を初期化し、各ランの符号化情報を格納するためのランデータ構造と、符号化情報を格納可能なランの最大値とを設定する。また、ランデータ構造には、このランデータ構造に符号化情報を格納するランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを記憶する帰属元ランフィールドと、上記ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、画像種別情報を予め設定されたデフォルト値に設定する。そして、ランレングス符号化処理部３３は、ラスタ走査方向にそって１画素ずつ走査することで各ランの検出、各ランのランレングスの検出、および各ランの帰属元ランの検出を行い、これらの検出結果に基づいてランデータ構造における上記各フィールドの情報を更新することにより、各ランの符号化情報を生成する。また、ランレングス符号化処理部３３は、符号化したランの数がメモリ３１に格納可能なランの数の最大値より１つ小さい値に達すると、残りの画素をデフォルト値に対応する画像種別の単一のランとみなしてその符号化情報を生成し、メモリ３１に格納して符号化処理を終了する。
【０１１４】
これにより、クラスマップに含まれるランの数がメモリ３１に格納可能なランの最大値を超過している場合であっても、当初に生成した符号化情報が上書きされるなどして失われることを防止できる。
【０１１５】
なお、クラスマップに含まれるランの数がメモリ３１に格納可能なランの最大値を超過している場合、クラスマップにおけるラスタ走査方向の末尾に位置する一部のランはデフォルト値に対応するクラス（例えば背景領域）として符号化されるので、クラスマップ全体に対する符号化処理を行うことはできないものの、クラスマップにおけるラスタ走査方向の先頭から所定数のランについては適切に符号化処理を行ってその結果をメモリ３１に残すことができる。
【０１１６】
これにより、例えば、メモリ３１に格納された符号化結果を参照してクラスマップに対応する原稿の天地判定や原稿種別判定などを適切に行うことができる。上記の天地判定や原稿種別判定の方法は特に限定されるものではないが、例えば、各種原稿のレイアウト例を予め記憶しておき、符号化結果からクラスマップにおける各画像種別に対応する領域のレイアウトを検出し、検出したレイアウトと予め記憶させておいたレイアウト例とを比較することにより、天地判定や原稿種別判定を行うようにしてもよい。上記の原稿種別としては、例えば、複数ページ分の原稿画像を１枚の用紙上に割り付けた割付原稿、テキスト領域を複数のブロックに分けて配置した段組原稿、所定形状の罫線を含む伝票や帳票などが挙げられる。
【０１１７】
また、図３０に示した画像処理装置３０の構成に加えて、上記の天地判定処理を行う天地判定処理部を備えてもよい。また、図３０に示した画像処理装置３０の構成に加えて、上記の原稿種別判定処理を行う原稿種別判定処理部を備えてもよい。
【０１１８】
また、メモリ３１に格納可能な１ラインあたりのランの数の最大値（ライン最大値）を設定し、符号化処理中のラインにおける未符号化処理のランの数がそれら各ランをデフォルトクラスに設定することしかできない数になった場合に、残りの要素をデフォルトクラスに属する単一のランとみなして符号化して当該ラインに対する符号化処理を終了し、次のラインの符号化処理を開始するようにしてもよい。
【０１１９】
また、上記実施形態において、画像処理装置３０に備えられる各部（各ブロック）を、ＣＰＵ等のプロセッサを用いてソフトウェアによって実現してもよい。この場合、画像処理装置３０は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである画像処理装置３０の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、画像処理装置３０に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによって達成される。
【０１２０】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１２１】
また、画像処理装置を通信ネットワークと接続可能に構成し、通信ネットワークを介して上記プログラムコードを供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【０１２２】
また、画像処理装置３０の各ブロックは、ソフトウェアを用いて実現されるものに限らず、ハードウェアロジックによって構成されるものであってもよく、処理の一部を行うハードウェアと当該ハードウェアの制御や残余の処理を行うソフトウェアを実行する演算手段とを組み合わせたものであってもよい。
【０１２３】
本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【産業上の利用可能性】
【０１２４】
本発明は、画像データをランレングス符号化する画像処理装置および画像処理方法に適用することができる。
【符号の説明】
【０１２５】
３０ 画像処理装置
３１ メモリ
３２ 初期化処理部
３３ ランレングス符号化処理部
３４ 連結パス圧縮部
３５ ラベル圧縮部
【技術分野】
【０００１】
本発明は、画素の連結領域にラベルを付けて各連結領域を分類するラベリング処理を行う画像処理装置および画像処理方法に関するものである。
【背景技術】
【０００２】
従来より、画像データに対する処理を領域毎に区別して行って処理の効率化を図ったり、画像データのデータサイズを小さしたりするために、画像上の画素の集合（連結領域）毎に番号（ラベル）をつけることで画素を分類するラベリング処理が知られている。ラベリング処理によって分類された各領域は、例えば、領域特性を決定するため、領域が属するオブジェクトの分類を識別するため、あるいは領域毎に特定の処理を適用するために、各領域に応じた所定の処理を施される。典型的な処理としては、例えば、領域内の全要素に対して領域固有のフィルタを用いてフィルタリングを行う処理が挙げられる。
【０００３】
連結要素を領域に分類する処理は連結成分ラベリング（connected component labeling）と呼ばれる。また、そのようなアルゴリズムは、連結成分アルゴリズム（connected-component algorithms）と呼ばれる。
【０００４】
例えば、特許文献１には、ＭＨ符号化された画像データを復号することによりランを生成し、先行するランと当該ランとの連結を調べ、連結しているときは先行するランに割り当てられたラベルと同一のラベルを当該ランに割り付け、ラベルの割り付けられた当該ランが異なるラベルの他の複数のランと連結しているとき、それらラベル間にリンクを張ることにより連結している複数のランを統合して１つの連結成分を切り出す技術が開示されている。なお、特許文献１の技術では、各ランの始点座標（ｘ，ｙ）と、各ランの長さと、各ランのラベルとがランテーブルに格納される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−１１１７８２号公報（平成８年４月３０日公開）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記特許文献１の技術には、符号化されるランの数がメモリに格納可能なランの数を超過する場合に、既に符号化したランの情報が上書きされ、必要な情報が失われてしまうという問題がある。
【０００７】
本発明は、上記の課題に鑑みてなされたものであり、その目的は、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化されたランの情報を適切に保存することができる画像処理装置および画像処理方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の画像処理装置は、上記の課題を解決するために、画像データにおける各画素の画像種別を示す情報であるクラスマップデータから、同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化処理部と、符号化した符号化データを格納する記憶手段とを備えた画像処理装置であって、符号化に先立って上記記憶手段を初期化する初期化処理部を備え、上記初期化処理部は、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定し、上記ランレングス符号化処理部は、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【０００９】
また、本発明の画像処理方法は、画像データにおける各画素の画像種別を示す情報であるクラスマップデータから同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号工程と、符号化したデータを記憶手段に格納する記憶工程とを含む画像処理方法であって、符号化処理工程に先立って上記記憶手段を初期化する初期化処理工程を含み、上記初期化処理工程では、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定し、上記ランレングス符号化処理工程では、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００１０】
上記の構成によれば、初期化処理において、各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、上記画像種別情報を予め設定されたデフォルト値に設定する。
【００１１】
また、ランレングス符号化処理において、上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行う。
【００１２】
そして、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００１３】
これにより、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【００１４】
また、上記初期化処理部は、上記記憶手段に格納可能な１走査ラインあたりのランの数の最大値であるライン最大値を設定し、上記ランレングス符号化処理部は、各走査ラインについて、符号化情報を生成したランの数が上記ライン最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない当該走査ラインについての残りの画素数に更新し、画像種別については上記デフォルト値のままにすることによって生成し、当該走査ラインについての符号化処理を終了する構成であってもよい。
【００１５】
上記の構成によれば、画像データをランレングス符号化する際、画像データの各ラインに含まれるランの数がメモリに格納可能な１ラインあたりのランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【００１６】
また、上記初期化処理部は、上記ランデータ構造を走査ライン毎に生成し、上記ランレングス符号化処理部は、各ランの符号化情報を当該ランが属する走査ラインに対応する上記ランデータ構造を用いて生成する構成としてもよい。
【００１７】
上記の構成によれば、画像種別情報についてのデフォルト値を走査ライン毎に設定できる。これにより、画像データの末尾のランをデフォルト値に符号化する場合であっても、これら各ランの画像種別を実際の画像データに近づけることができる。
【００１８】
また、上記初期化処理部は、初期化時に上記画像種別情報として設定する上記デフォルト値を、上記画像データにおける背景領域を示す値に設定する構成としてもよい。
【００１９】
上記の構成によれば、一般に画像データにおける末尾部分の画像は背景画像であることが多いので、画像データの末尾のランをデフォルト値に符号化する場合であっても、これら各ランの画像種別を画像データにおける背景領域に設定することにより、実際の画像データにより近づけることができる。
【発明の効果】
【００２０】
以上のように、本発明の画像処理装置および画像処理方法は、符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了する。
【００２１】
これにより、画像データをランレングス符号化する際、画像データに含まれるランの数がメモリに格納可能なランの数を超過する場合であっても符号化済みのランの符号化情報が上書きされるなどして失われることを確実に防止することができる。
【図面の簡単な説明】
【００２２】
【図１】クラスマップの一例を示す説明図である。
【図２】図１に示したクラスマップの変形例を示す説明図である。
【図３】ランレングス符号化されたクラスマップの一例を示す説明図である。
【図４】図３に示したクラスマップにおける各ランの連結性を示す連結性グラフである。
【図５】本発明の一実施形態にかかる画像処理装置におけるラベリング処理の流れを示すフローチャートである。
【図６】クラスマップの一例を示す説明図である。
【図７】図７に示したクラスマップの連結性グラフの一例である。
【図８】図６に示したクラスマップの第１ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図９】図６に示したクラスマップの第２ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１０】図６に示したクラスマップの第３ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１１】図６に示したクラスマップの第４ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１２】図６に示したクラスマップの第５ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１３】図６に示したクラスマップの第６ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１４】図６に示したクラスマップの第７ラインをラベリング処理する際の連結性グラフであり、（ａ）は灰色のクラスに属するラン、（ｂ）は白色のクラスに属するランの連結性を示している。
【図１５】図５に示したフローチャートの変形例である。
【図１６】図５に示したフローチャートの変形例である。
【図１７】図５に示したフローチャートの変形例である。
【図１８】本発明の一実施形態にかかる画像処理装置におけるラベリング処理の流れを示すフローチャートである。
【図１９】本発明の一実施形態にかかる画像処理装置におけるランレングス符号化処理の流れを示すフローチャートである。
【図２０】図６に示したクラスマップに対する処理を説明するための説明図である。
【図２１】図６に示したクラスマップに対する処理を説明するための説明図である。
【図２２】本発明の一実施形態における初期化処理をコンピュータに実行させるためのコードの一例である。
【図２３】本発明の一実施形態におけるランレングス符号化処理および隣接ラン統合処理をコンピュータに実行させるためのコードの一例である。
【図２４】本発明の一実施形態におけるランレングス符号化処理および隣接ラン統合処理をコンピュータに実行させるためのコードの他の例である。
【図２５】本発明の一実施形態におけるラベリング結果の一例を示す表である。
【図２６】本発明の一実施形態における圧縮処理をコンピュータに実行させるためのコードの例である。
【図２７】本発明の一実施形態におけるラベリング結果の他の例を示す表である。
【図２８】本発明の一実施形態におけるランレングスデータ構造をインデックス化する処理をコンピュータに実行させるためのコードの例である。
【図２９】本発明の一実施形態におけるラベル画像の生成処理をコンピュータに実行させるためのコードの例である。
【図３０】本発明の一実施形態にかかる画像処理装置の概略構成を示すブロック図である。
【図３１】図３０に示した画像処理装置におけるメモリの初期化処理を説明するための説明図である。
【発明を実施するための形態】
【００２３】
本発明の一実施形態について説明する。なお、説明の便宜上、同様の機能を有する部材については同じ符号を付してその説明を省略する場合がある。
【００２４】
図３０は、本実施形態にかかる画像処理装置３０の概略構成を示すブロック図である。なお、この画像処理装置３０は、例えば画像読取装置、画像形成装置、画像送信装置、画像記録装置、あるいは複合機などに備えられるものであってもよく、これらの装置に通信可能に接続されるものであってもよい。
【００２５】
図３０に示したように、画像処理装置３０は、メモリ（記憶手段）３１、初期化処理部３２、ランレングス符号化処理部（ＲＬＥ処理部）３３、連結パス圧縮部３４、ラベル圧縮部３５を備えている。
【００２６】
図５は、画像処理装置３０における処理の流れを概略的に示したフローチャートである。
【００２７】
図５に示すように、まず、初期化処理部３２が、画像処理装置３０に入力されるクラスマップ（クラスマップデータ）のランレングス符号化処理を開始する前に、メモリ３１の初期化処理を行う（Ｓ８０）。
【００２８】
クラスマップとは、画像データに含まれる各要素（典型的には各画素）を当該各要素の画像種別（クラス）毎に分類したデータである。なお、画像処理装置３０に入力されるクラスマップは、各要素の種別（クラス）を判別できるものであればよく、そのデータ形式は特に限定されるものではない。また、クラスマップは、画像処理装置３０が備えられる画像読取装置、画像形成装置、画像送信装置、画像記録装置、あるいは複合機における他の処理ブロックから画像処理装置３０に入力されてもよく、画像処理装置３０に対して通信可能に接続される外部装置から画像処理装置３０に送信されてもよい。また、画像処理装置３０に着脱可能に装着される記録媒体から画像処理装置３０が読み出すようにしてもよい。
【００２９】
図１は、典型的なクラスマップの一例を示す説明図である。図１では、同じ要素タイプに分類される各要素を同様の模様で示している。具体的には、図１に示したクラスマップ２には、６つの領域４、６、８、１０、１２、１４が含まれており、これら６つの領域に属する要素が５つの異なるクラスに分類されている。つまり、領域１０内の要素と領域１２内の要素とは同一のクラスに属する。
【００３０】
クラスマップの一例としては、画像要素を文字領域、写真領域、および網点領域に分類する領域分離システムによる処理結果が挙げられる。また、クラスマップの他の例としては、空（sky）と地表（grass）のように、画像中の被写体等のオブジェクトを分類するシステムの処理結果が挙げられる。当業者であれば、画像処理アプリケーションにおいて多様なタイプのクラスマップが生じ得ることを容易に理解できるであろう。
【００３１】
連結成分ラベリングアルゴリズムは、同じラベルを有する複数の隣接要素を成分としてグループ化する。また、各成分に属する要素同士に同じ処理が適用されるように、各成分に固有のラベルを割り当てる。
【００３２】
図２は、クラスマップの他の例を示す説明図である。この図に示すクラスマップ２０に含まれる領域２２、２４、２６、２８、３０、３２は、それぞれ図１のクラスマップ２における領域４、１０、８、６、１２、１４に対応している。ただし。図１では同じクラスに属する領域１０，１２に対して同じラベルが割付けられていたのに対して、図２では領域２４，３０に別々の固有のラベルが割り当てられている。
【００３３】
初期化処理部３２によって初期化処理が行われた後、ランレングス符号化処理部３３が、ランレングス符号化（ＲＬＥ）／隣接ラン統合処理を行い（Ｓ８２）、処理結果（符号化データ）をメモリ３１に格納する。すなわち、ランレングス符号化処理部３３は、画像処理装置３０に入力されるクラスマップに対してランレングス符号化処理をラスタ方向に沿って順次行うとともに、同じクラスに属し、かつ互いに隣接するラン同士を関連付ける統合処理を行う。なお、ランとは、同じクラスに属し、かつライン（走査ライン）の延伸方向（走査ライン方向）に隣接する画素同士を連結した連結成分である。また、クラスの種類としては、例えば、テキスト、局所背景、ページ背景、絵図、線図などが挙げられる。
【００３４】
なお、ランレングス符号化のアルゴリズムは特に限定されるものではなく、例えば、特定の演算装置に適応するように最適化されたものであってもよい。また、各成分を構成する要素の連結関係を検出してキャッシュに入れる処理を行うための最適な構成になるように連結成分アルゴリズムを構成してもよい。なお、成分の複合的な形状や大面積の成分を考慮することの必要性により、要素同士の連結性を効率的に検出するためのアルゴリズムの設計は複雑になる場合もある。
【００３５】
また、ランレングス符号化の方法には、連結成分に対するラベリングを反復的に行う反復法、連結成分に対するラベリングを再帰的に行う再帰法、および反復法と再帰法という２つの基本的な方法を組み合わせたハイブリッド連結成分ラベリング法（ハイブリッド法）がある。
【００３６】
反復法では、開始画素から追加の画素が当該領域（成分）に加えられなくなるまで、すなわち当該領域の成長が終わるまで、クラスマップ内全体に渡って同じラベル（インデックス）が反復的に付与される。この方法では、データ全体に対する反復回数が連結領域に属する要素の数と等しくなるので、演算の負荷が大きくなる。ただし、反復法では、メモリ使用量およびアクセスパターンを予測可能である。
【００３７】
再帰法では、ラベリングされていない要素からラベリング処理を開始する。この方法では、ラベリング処理対象の要素に隣接する隣接要素、およびこの隣接要素に隣接する要素を再帰的に調べる。上記の再帰を、スタック構成（stack construct）を用いて行ってもよい。連結している隣接要素をスタックから抽出して調べたり、連結している隣接要素をスタックに加えたりする処理をスタックが空になるまで行う。再帰法は、反復法に比べて演算負荷を低減できる。ただし、メモリ使用量が画像データに応じて異なり、アクセスパターンがランダムであるので、メモリ使用量およびアクセスパターンを予測することは困難である。
【００３８】
ハイブリッド法では、メモリアクセスパターンを簡単な処理で概略的に予測することができる。第１の処理では、単純な凸位相（convex topologies）の成分を１つの領域にグループ化するが、より複雑な位相の成分はさらに複数の副成分に分割される。これら各副成分は後に統合される。ハイブリッド法では、分割された副成分を統合するために、これら各副成分の連結性を再帰的に追跡する。ハイブリッド法を用いる場合には有限併合再帰（bounded merge recursion）を行うことがより好ましい。
【００３９】
ハイブリッド法は２つのステップを含む。第１のステップでは、各要素を隣接する連結要素とリンクさせたサブグラフを構築する。第２のステップでは、各サブグラフを識別するためにサブグラフを連結させたグラフの頂点を解析する。なお、連結された各サブグラフは連結成分を構成する。
【００４０】
ハイブリッド法によって生成されるグラフは、各要素（基本要素）に対応する頂点を有しており、同じクラスタイプを有する隣接する頂点同士はリンクされている。上記要素は、典型的には画素（ピクセル）である。このグラフデータ構造は、連結成分にラベリングを行うためのメモリおよび演算処理という観点からは必ずしも最適ではない。なお、グラフ構造を解析する前に同様のクラスタイプを有する複数の要素をグループ化することによって上記処理を簡略化してもよい。ラスタ形式の画像では、ラスタラインに沿って連結された同じクラスに属する複数の画素（ラン）は単一の頂点にグループ化されメモリ内において同一の位置に配置される。このグループ化により、グラフ内の頂点の数およびリンクの数を低減できる。複数のラインの読み出しおよびラインを横断したグループ化を行う構成ではそれによってさらなる利点を得ることができる。
【００４１】
ランレングス符号化（ＲＬＥ）／隣接ラン統合処理において、クラスマップをランレングス符号化（ＲＬＥ）してＲＬＥマップを形成するステップと、同じクラスに属する隣接し合う複数のランを統合した統合ＲＬＥマップを形成し、統合ＲＬＥマップから領域情報を抽出するステップの２つのステップを行うようにしてもよい。この場合、画像中の各クラスに対して固有のラベルを割り当てたクラスマップは、同一ライン内における同じクラスのラベルを有する画素を連結してランレングス符号化される。また、ＲＬＥマップ内においてラインをまたがって連結されたランを抽出することによって領域特性が検出される。
【００４２】
図３はクラスマップの一例を示す説明図である。この図に示すクラスマップ３８は、Ｒ０〜Ｒ１１で示される１２個のランを含む４つのラインを含んでいる。また、クラスマップ３８は２つのクラス、すなわち白いブロックで示されたランＲ０，Ｒ２，Ｒ４，Ｒ６，およびＲ９を含むクラスと、灰色のブロックで示されたランＲ１，Ｒ３，Ｒ５，Ｒ７，Ｒ８，Ｒ１０，およびＲ１１を含むクラスとを有している。
【００４３】
図４は、図３に示したクラスマップ３８における灰色のクラスに属するランの連結性を示すグラフ（連結性グラフ）６０を示している。グラフ６０は、ラン６２，６４，６８，７０，７２，および７４（ランＲ１，Ｒ３，Ｒ５，Ｒ７，Ｒ８，Ｒ１０，およびＲ１１）の各頂点の連結関係と、隣接性を示すリンク６３，６５，６７，６９，７１，および７３を示している。この図に示したように、頂点間の経路長は各要素間で大幅に異なる場合がある。このため、データから算出される経路長によっては、メモリおよび演算処理のアルゴリズムを実際の装置に適用すると必要なメモリ容量が大きくなったり、装置構成が複雑になったりする場合がある。
【００４４】
本実施形態では、ランレングス符号化されたデータを格納するメモリ３１として、固定サイズのメモリ（メモリバッファ）を用いる。なお、このメモリ３１には、後述するように、入力データに依存しない所定の最大実行経路長（maximum execution path lengths）を有するデータが格納される。つまり、本実施形態では、メモリ３１に格納するデータの最大実行経路長およびメモリ３１の設置面積（memory footprint）を固定値とする。したがって、本実施形態は、ＡＳＩＣ（Application Specific Integrated Circuit;特定用途向け集積回路）やＳＩＭＤ（single-instruction multiple-data-pathD）ＤＳＰ（digital signal processing）への実装に特に適している。
【００４５】
なお、メモリ３１に格納されるデータのデータ構造は、クラスマップの列数および行数に関連付けられてもよい。また、上記データ構造は、符号化されたランに関連付けられてもよい。また、このランに関連付けられたデータ構造であるランデータ構造は、各ランに関連付けられたパラメータ、例えば、各ランの帰属元ラン（親ラン）、各ランの属するクラス、各ランのランレングス（ランの長さ）などのパラメータを含んでいてもよい。また、このランデータ構造は、所定の最大ラン数に達するまでは各ランを関連付けて記憶し、各ランにラン番号インデックスを付与することによって各ランを識別するものであってもよい。また、所定の最大ラン数に達した後は残りのランを、デフォルトクラス（例えば背景領域のクラス）に属する単一のランとして記憶させるようにしてもよい。
【００４６】
また、上記ランデータ構造を、クラスマップにおける各ラインのスターティングラン（符号化開始ラン）、すなわちラスタ方向の最上位（最上流側）に位置するランに関連付けてもよい。例えば、上記ランデータ構造における各ラインをスターティングランに関連付けたスターティングランデータ構造において、クラスマップにおける各ラインに対応するランデータ構造内に、当該ラインにおけるスターティングランを示すメモリ参照情報（memory reference）を記憶させてもよい。また、スターティングラン構造は、各ラインに関連付けて記憶されるものであってもよく、ライン番号のインデックスによって識別されるものであってもよい。
【００４７】
また、処理対象のライン（走査線）のクラスマップデータを記憶する入力クラスマップバッファを用いてもよい。また、処理対象のライン（走査線）に対する連結成分ラベルの付与結果を記憶する連結成分ラベル出力バッファを用いてもよい。また、上記データ構造を、演算装置に近接する位置に配置されるローカルバッファ内に格納してもよい。
【００４８】
上記データ構造内の一部のパラメータは、入力データ毎に異なってもよい。また、その他のパラメータは、連結成分アルゴリズムを実現するためのシステムに固有のものであってもよい。また、クラスマップパラメータは、システムアプリケーションに応じて決定されてもよい。
【００４９】
一般に、複合機（multi-function peripheral; MFP）等の典型的なアプリケーションでは、走査解像度は固定値の中から選択される。上記の各パラメータを上記固定値の最大値に対応するように設定することにより、大部分のデータ構造に要求される最低限の要件が決定される。残りのパラメータは、入力クラスマップデータに応じて算出されるランの数によって決定される。
【００５０】
オンチップキャッシュまたは内部バッファの容量は有限であり、メモリ３１に格納可能なランの数は、符号化されるランの数が内部バッファの容量の上限を超えないように制限される。ランの最大数は、例えばシステムのコストと、処理される入力データの複雑さとのバランスを考慮して決定される。
【００５１】
各ランがデフォルトクラスに属するものとして符号化した入力クラスマップのライン数と同数のラン（スターティングラン）をランデータ構造の端部に予め生成しておき、その後それらのランを上書きするようにしてもよい。
【００５２】
ランレングス符号化処理部３３によってランレングス符号化（ＲＬＥ）／隣接ラン統合処理が行われた後、連結パス圧縮部３４が、上記統合処理によって統合された各ランの連結関係を示す連結情報（帰属元ラベル）を圧縮する連結パス圧縮処理を行う（Ｓ８４）。
【００５３】
その後、ラベル圧縮部３５が、上記統合処理によっての統合された各成分（同じクラスに属し、互いに隣接するランの集合）に対して成分毎に共通のラベルを付与しなおすラベル圧縮処理を行う（Ｓ８６）。
【００５４】
次に、画像処理装置３０における初期化処理およびランレングス符号化／隣接ラン統合処理について、図１８を参照しながらより詳細に説明する。図１８は初期化処理およびランレングス符号化／隣接ラン統合処理流れを示すフローチャートである。
【００５５】
上述したように、まず、初期化処理部３２が、画像処理装置３０に入力されるクラスマップ（クラスマップデータ）のランレングス符号化処理を開始する前に、メモリ３１の初期化処理を行う（Ｓ３１０）。
【００５６】
図３１は、初期化処理を説明するための説明図である。なお、図３１は、クラスマップのライン数が１００であり、付与可能なラベル数（格納可能なランの数）が１０００個である場合の例を示している。
【００５７】
初期化処理部３２は、画像処理装置３０に入力されたクラスマップを参照し、メモリ３１内にクラスマップにおける縦方向のライン数（０〜９９）に応じた数のスターティングランデータ（スターティングラン構造）と、メモリに格納可能な最大ラン数に応じたランデータ構造を生成する。各ランデータ構造は、当該ランデータ構造に符号化情報を格納するランである格納対象ランのラン番号（ラベル；ランインデックス、０〜９９９）を格納するための格納対象ランフィールド、上記格納対象ランの帰属元ランを示す帰属元情報（帰属元ラベル）を格納（記憶）するための帰属元ランフィールド、上記格納対象ランが属するクラス（画像種別）を示す画像種別情報を格納するための画像種別フィールド、および上記格納対象ランの長さ（ランレングス）を示すランレングス情報を格納するためのランレングスフィールドを有している。
【００５８】
帰属元ランとは、同じクラスに属する連結された複数のランのうちラスタ方向の最上位（最上流側）に位置するランである。帰属元ランを示すパラメータとしては例えば帰属元ランのラン番号（ランインデックス）を用いることができる。このラン番号は、例えばラスタ方向の位置に応じて各ランに順次付与すればよい。
【００５９】
なお、初期化処理時には、例えば、スターティングランデータの数を画像データのライン数（クラスマップにおける画像領域の縦方向のサイズ）と同数に設定し、各ランデータ構造における帰属元ランのラベルを当該ランデータ構造に対応する格納対象ランのラベルに設定し、格納対象ランが属するクラスをデフォルトクラス（例えば、当該ランデータ構造に対応するラインのスターティングランの属するクラス、あるいはクラスマップにおける背景領域のクラス）に設定し、ランレングスを画像データにおけるラインの延伸方向の画素数（クラスマップにおける画像領域の横方向の画素数）ｍに設定する。
【００６０】
図２２は、初期化処理をコンピュータに実行させるための典型的な中間コードの例を示している。図２２において、StartingRunはスターティングランデータ構造であり、Class、ParentLabel、およびRunLengthはランデータ構造のフィールド（クラス、帰属元ラベル、およびランレングス）であり、NumberRunLimitはメモリに格納可能な最大ラン数であり、default class valueは各ランのクラスを示すパラメータのデフォルト値であるデフォルトクラスを示し、Number of RowsおよびNumber of Columnsは、クラスマップの行数（ライン数）および列数（１ラインの画素数）を示している。
【００６１】
デフォルトクラスの値は、各ランデータ構造に対応するスターティングランのクラスを示す値に設定してもよい。あるいは、画素が背景画像（背景領域）に属しているか否かが入力クラスマップによって示される場合、デフォルトクラスの値は背景画像を示すクラスの値であってもよい。その場合、初期化処理時には、各ランデータ構造は、出力画像全体が背景画像であることを示す状態になる。そして、初期化処理の後、クラスマップの符号化を開始したときには、ランレングス符号化／隣接ラン統合処理の結果に応じてこれら各パラメータの初期値が上書きされることになる。
【００６２】
メモリ３１のデータ構造の初期化処理（Ｓ３１０）の後、ランレングス符号化処理部３３は、まず、クラスマップの第１ラインのランレングス符号化を行う（Ｓ３１２）。
【００６３】
図１９は、第１ラインのランレングス符号化処理の流れを示すフローチャートである。
【００６４】
まず、クラスマップ内の第１ラインを入力バッファ（図示せず）に入力し、注目要素を当該ラインにおける第１要素、すなわちラスタ方向の最上流側の要素に設定する（Ｓ３８０）。
【００６５】
初期化したデータにおける第１ラインの第１ラン（スターティングラン）InitRunを抽出してキャッシュし（Ｓ３８２）、次のラン（上書き後のラン）NextRunのラン番号を設定する（Ｓ３８４）。
【００６６】
次に、上記第１ランInitRunと次のランNextRunとを比較し（Ｓ３８６）、ＲＬＥ／隣接ラン統合処理を終了して連結パス処理を開始するか（３８７）、あるいはＲＬＥ／隣接ラン統合処理を継続するか（３６０）を判断する。
【００６７】
例えば、未符号化処理のランの数が、クラスマップにおける未符号化処理の各ランをデフォルトクラスに設定することしかできない数になった場合に符号化を終了する。より具体的には、例えば図３１に示したデータ構造の場合、ラン番号９９８（格納可能なランのラン番号の最大値−１）に対するＲＬＥ／隣接ラン統合処理が行われようとする段階で次のランに対するラベル付けは不可であると判断し、ラン番号９９８に対してはデフォルトクラスに対応するパラメータを付与し、ラン番号９９８のランレングスをＲＬＥ／隣接ラン統合処理を行っていない残りの要素の数に設定して符号化処理を終了する。
【００６８】
ＲＬＥ／隣接ラン統合処理を継続する場合には、注目要素が属するラン（注目ラン）のパラメータを設定する（Ｓ３９０）。例えば、帰属元ランを注目ラン自身に設定し、クラスを注目要素のクラスに設定し、ランレングスをゼロ（要素数１に対応）に設定する。
【００６９】
その後、上記の注目要素が第１ラインの最終要素であるかを判定する（Ｓ３９２）。そして、最後の要素である場合（３９３）、第１ラインのランレングス符号化を終了する（Ｓ４０４）。
【００７０】
最後の要素ではない場合（３９４）、注目要素をラスタ順に沿った次の要素に変更する（Ｓ３９６）。そして、この新たな注目要素のクラスが処理中のランのクラス（前回の注目要素のクラス）と同一であるかを判断する（Ｓ３９８）。
【００７１】
そして、同一である場合（４００）、処理中のランのランレングスをインクリメントし（Ｓ４０２）、Ｓ３９２の処理に戻る。一方、同一ではない場合（３９９）、Ｓ３８４に戻る。
【００７２】
第１ラインのランレングス符号化（Ｓ３１２）を行った後、ランレングス符号化処理部３３は、クラスマップの最後のラインに対する処理を行ったか否かを判定する（Ｓ３１４）。そして、最後のラインに対する処理を行ったと判断した場合（３１５）、ＲＬＥ／隣接ラン統合処理を終了し、連結パス圧縮処理を開始する（Ｓ３６０）。
【００７３】
一方、最後のラインに対する処理を行っていないと判断した場合（３１６）、ランレングス符号化処理部３３は、クラスマップの次のラインを入力バッファ（図示せず）に入力し、注目要素を当該ラインにおける第１要素、すなわちラスタ方向の最上流側の要素に設定する（Ｓ３１８）。そして、初期化したデータにおける当該ラインの第１ラン（スターティングラン）InitRunを抽出してキャッシュし（Ｓ３２０）、次のラン（上書き後のラン）NextRunのラン番号を設定する（Ｓ３２２）。
【００７４】
次に、ランレングス符号化処理部３３は、上記第１ランInitRunと次のランNextRunとを比較し（Ｓ３２４）、ＲＬＥ／隣接ラン統合処理を終了して連結パス処理を開始するか（３２５）、あるいはＲＬＥ／隣接ラン統合処理を継続するか（３６０）を判断する。例えば、上述したように、未符号化処理のランの数が、クラスマップにおける未符号化処理の各ランをデフォルトクラスに設定することしかできない数になった場合に符号化を終了する。
【００７５】
ＲＬＥ／隣接ラン統合処理を継続する場合（３２６）、注目要素が属するラン（注目ラン）のパラメータを設定する（Ｓ３２８）。例えば、帰属元ラベルを注目ラン自身に設定し、クラスを注目要素のクラスに設定し、ランレングスをゼロ（要素数１に対応）に設定する。
【００７６】
その後、ランレングス符号化処理部３３は、注目要素のクラスと、既に符号化したライン（注目ラインの１つ前のライン）における上記注目要素に隣接する要素である隣接要素のクラスとを比較する（Ｓ３３０）。例えば、４連結の場合（上、下、左、右の隣接要素の連結性を考慮する場合）には真上に隣接する要素のみと比較すればよく、８連結の場合（上、下、左、右、左上、右上、左下、右下の隣接要素の連結性を考慮する場合）には左上、真上、および右上に隣接する各要素と比較すればよい。
【００７７】
図２３は、４連結に基づくＲＬＥ／隣接ラン統合処理をコンピュータに実行させるための中間コードの一例を示している。また、図２４は、８連結に基づくＲＬＥ／隣接ラン統合処理をコンピュータに実行させるための中間コードの一例を示している。
【００７８】
連結している隣接要素がない場合（注目要素のクラスと隣接要素のクラスとが異なる場合）（３３１）、ランレングス符号化処理部３３は、上記注目要素が当該ラインの最後の要素であるかを判定する（Ｓ３３４）。最後の要素である場合（３３５）、Ｓ３１４の処理に戻る。
【００７９】
一方、最後の要素ではない場合（３３６）、ランレングス符号化処理部３３は、注目要素をラスタ順に沿った次の要素にする（Ｓ３３８）。そして、この新たな注目要素のクラスが処理中のランのクラス（前回の注目要素のクラス）と同一であるかを判断する（Ｓ３４０）。
【００８０】
そして、同一である場合（３４２）、処理中のランのランレングスをインクリメントし（Ｓ３４４）、Ｓ３３０の処理に戻る。一方、同一ではない場合（３４１）、Ｓ３２２の処理に戻る。
【００８１】
一方、Ｓ３３０において注目要素のクラスと１つ前のラインにおける隣接要素のクラスとが同じであると判断した場合（３３２）、ランレングス符号化処理部３３は、注目要素の帰属元ラン（Current Parent）と、上記隣接要素の帰属元ラン（Adjacent Parent）とを比較する（Ｓ３４６）。
【００８２】
そして、注目要素の帰属元ラン（Current Parent）の方が隣接要素の帰属元ラン（Adjacent Parent）よりも連結性ツリー（連結性グラフ）の上位にある場合、すなわちラスタ方向の上流側に位置するランである場合（３４８）、隣接要素の帰属元ランの帰属元ランを注目要素の帰属元ランに更新する（Ｓ３５０）。さらに、隣接要素が属するランの帰属元ランを注目要素の帰属元ランに更新し（Ｓ３５２）、Ｓ３３４の処理に戻る。
【００８３】
一方、注目要素の帰属元ラン（Current Parent）の方が隣接要素の帰属元ラン（Adjacent Parent）よりも連結性ツリー（連結性グラフ）の下位にある場合、すなわちラスタ方向の下流側に位置するランである場合（３４７）、注目要素の帰属元ランの帰属元ランを隣接要素の帰属元ランに更新する（Ｓ３５１）。さらに、注目要素が属するランの帰属元ランを隣接要素の帰属元ランに更新し（Ｓ３５２）、Ｓ３３４の処理に戻る。
【００８４】
次に、図６〜図１４を参照しながらＲＬＥ／隣接ラン統合処理についてより詳細に説明する。
【００８５】
図６は、クラスマップの一例およびこのクラスマップに対するＲＬＥ／隣接ラン統合処理の一例を示す説明図である。この図に示すクラスマップ８９は、７つのライン（列とみなすこともできる）９０〜９６と、白と灰色で示した２つのクラスからなるラン１０１〜１３０（Ｒ１〜Ｒ３０）とを含んでいる。
【００８６】
図７は、図６に示したクラスマップ８９における灰色のラン１０１、１０３、１０５、１０７、１０９、１１１、１１２、１１４、１１６、１１８、１１９、１２１、１２３、１２５、１２６、１２８、および１２９の連結性を示す連結性グラフ１４０を示している。連結性グラフ１４０では、ランは頂点１４１〜１５７として示されている。また、連結性グラフ１４０では、隣接するランはリンク１６０〜１７５で連結されている。
【００８７】
なお、図７には図６における灰色のクラスに属するランの連結性を示したが、白色のクラスに属するラン１０２、１０４、１０６、１０８、１１０、１１３、１１５、１１７、１２０、１２２、１２４、１２７、１３０についても同様に連結性グラフを作製することができる。
【００８８】
以下の説明では、ランを、「Ｒ」および参照ラン番号で示す。例えば、第１のラン１０１はＲ１、２２番目のラン１２２はＲ２２と示す。
【００８９】
まず、クラスマップ８９の第１ライン９０をランレングス符号化する。第１ライン９０をランレングス符号化した後、２つのラン１０１（Ｒ１）および１０２（Ｒ２）をライン９０に関連付ける。また、第１のラン１０１（Ｒ１）を第１クラス（灰色）に関連付け、第２のラン１０２（Ｒ２）を第２クラス（白色）に関連付ける。すなわち、第１のラン１０１（Ｒ１）には第１クラスに対応するラベルを割付け、第２のラン１０２（Ｒ２）には第２クラスに対応するラベルを割付ける。ラン１０１（Ｒ１）および１０２（Ｒ２）に、帰属元ラン（親ラン）として自身を指し示す値を付与する。すなわち、第１のラン１０１（Ｒ１）は、図８（ａ）のグラフ１８０に示すように、帰属元ラン（親ラン）として自身を指し示すリンク２５１を有する頂点２０１として示される。また、第２のラン１０２（Ｒ２）は、図８（ｂ）のグラフ１８１に示すように、帰属元ラン（親ラン）として自身を指し示すリンク２５２を有する頂点２０２として示される。
【００９０】
クラスマップ８９の第１ライン９０をランレングス符号化した後、第２ライン９１の各要素を検証し、第２ラインのランレングス符号化および隣接ラン（連結ラン）の統合を行う。
【００９１】
具体的には、第３のラン１０３（Ｒ３）が抽出され、この第３のラン１０３（Ｒ３）の抽出中に前のライン９０における隣接するラン１０１（Ｒ１）が連結性を確認するために検証される。ラン１０３（Ｒ３）はラン１０１（Ｒ１）と同じクラスなので、それぞれの帰属元ラン（親ラン）が検出され、ラン１０１（Ｒ１）がラン１０３（Ｒ３）の帰属元ランとして検出される。
【００９２】
同様に、第４のラン１０４（Ｒ４）が抽出され、その帰属元ランとしてラン１０２（Ｒ２）が検出される。また、第５のラン１０５（Ｒ５）が抽出され、第５のラン１０５（Ｒ５）に隣接する前のライン９０における全てのランは第５のラン１０５（Ｒ５）とは異なるクラスなので、第５のラン１０５（Ｒ５）の帰属元ランはこの時点ではラン１０５（Ｒ５）自身に設定される。また、第６のラン１０６（Ｒ６）が抽出され、その帰属元ランとしてラン１０２（Ｒ２）が検出される。
【００９３】
図９（ａ）および図９（ｂ）は、第２ライン９１に対する処理によって抽出された各ランを示している。第３のラン１０３（Ｒ３）は、図９（ａ）のグラフ１８２では、帰属元ラン（親ラン）としてランＲ１（頂点２０１）を指し示すリンク２５３を有する頂点２０３として示されている。第５のラン１０５（Ｒ５）は、図９（ａ）のグラフ１８２では、帰属元ラン（親ラン）としてランＲ５自身を指し示すリンク２５５を有する頂点２０５として示されている。第４のラン１０４（Ｒ４）および第６のラン１０６（Ｒ６）は、図９（ｂ）のグラフ１８３では、それぞれ帰属元ラン（親ラン）としてランＲ２（頂点２０２）を指し示すリンク２５４，２５６を有する頂点２０４，２０６として示されている。
【００９４】
クラスマップ８９における第２ライン９１のランレングス符号化が終わると、第３ライン９２の要素を検証し、第３ライン９２のランレングス符号化、および隣接ランの統合を行う。第７のラン１０７（Ｒ７）が検出され、この第７のラン１０７（Ｒ７）に隣接するラン１０３（Ｒ３）がこの第７のラン１０７（Ｒ７）と同一クラスに属するので、連結性ツリー（連結性グラフ）における当該クラスの最上位のラン（帰属元ラン）として検出される。本実施形態では、最上位のランは、連結されたランのうちラン番号のもっとも小さいものである。
【００９５】
第７のラン１０７（Ｒ７）に隣接する同一クラスのランはラン１０３（Ｒ３）であるが、図６に示すように、連結された同一クラスのランの中にラン１０３（Ｒ３）よりも上位のラン１０１（Ｒ１）が存在するので、第７のラン１０７（Ｒ７）の帰属元ランはラン１０１（Ｒ１）であると判定される（図１０（ａ）参照）。
【００９６】
同様に、第８のラン１０８（Ｒ８）および第１０のラン１０（Ｒ１０）に隣接する同一クラスのランはラン１０４（Ｒ４）であるが、図６に示すように、連結された同一クラスのランの中にラン１０４（Ｒ４）よりも上位のラン１０２（Ｒ２）が存在するので、第８のラン１０８（Ｒ８）および第１０のラン１０（Ｒ１０）の帰属元ランはラン１０２（Ｒ２）であると判定される（図１０（ｂ）参照）。
【００９７】
第９のラン１０９（Ｒ９）は自身がその帰属元として検出され、ラン１１１（Ｒ１１）の帰属元ランとしてはラン１０５（Ｒ５）が検出される（図１０（ａ）参照）。
【００９８】
図１０（ａ）および図１０（ｂ）に示されているグラフ１８４，１８５は、第３ライン９２に対する処理で検出されるランとそれに連結されるランとの関係を示している。頂点２０１〜２１１は帰属元ランに関連付けられたランを示しており、リンク２５１〜２６１は各ランの連結関係を示している。
【００９９】
図１１（ａ）および図１１（ｂ）に示されているグラフ１８６，１８７は、第４ライン９３に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２１８はラン１０１〜１１８（Ｒ１〜Ｒ１８）に対応しており、リンク２５１〜２６８は上記各ランの連結関係を示している。
【０１００】
図１２（ａ）および図１２（ｂ）に示されているグラフ１８８，１８９は、第５ライン９４に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２２５はラン１０１〜１２５（Ｒ１〜Ｒ２５）に対応しており、リンク２５１〜２７５は上記各ランの連結関係を示している。なお、ラン１２４（Ｒ２４）に対する処理を行う際、初期段階として、このラン１２４（Ｒ２４）内の要素はラン１１５（Ｒ１５）に隣接しており、帰属元ランはラン１０２（Ｒ２）であると判定される。次に、このラン１２４（Ｒ２４）に隣接する第３ライン９２のラン１１７（Ｒ１７）について、第３ライン９２に対する処理を完了した時点ではその帰属元ランはラン１１７（Ｒ１７）自身であるが、このラン１１７（Ｒ１７）に隣接する同一クラスのラン１２４（Ｒ２４）の帰属元ランがラン１１７（Ｒ１７）よりもラン番号が小さいラン１０２（Ｒ２）であることから、その帰属元ランはラン１０２（Ｒ２）に更新される。つまり、第５ライン９４に対する処理の最後に第４ライン９３に属するラン１１７（Ｒ１７）の帰属元ランが第２ラン１０２（Ｒ２）に更新される。なお、この処理対象のライン（注目ライン）よりも前のラインに属するランの帰属元ランを更新する処理は、例えば注目ラインに対する処理が終わる毎に行ってもよく、注目ラインに属する各ランに対する処理が終わる毎に行ってもよい。
【０１０１】
図１３（ａ）および図１３（ｂ）に示されているグラフ１９０，１９１は、第６ライン９５に対する処理で検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２２８はラン１０１〜１２８（Ｒ１〜Ｒ２８）に対応しており、リンク２５１〜２７８は上記各ランの連結関係を示している。第２８ラン１２８（Ｒ２８）の最初の要素に対する処理では帰属元ランはラン１０９（Ｒ９）であると判定されるが、第２８ラン１２８（Ｒ２８）における最後の方の要素に対する処理において帰属元ランは最終的にラン１０５（Ｒ５）に更新される。
【０１０２】
図１４（ａ）および図１４（ｂ）に示されているグラフ１９２，１９３は、第７ライン９６に対する処理によって検出されるランとそれに連結されるランとの関係を示している。これら各図における頂点２０１〜２３０はラン１０１〜１３０（Ｒ１〜Ｒ３０）に対応しており、リンク２５１〜２８０は上記各ランの連結関係を示している。第２９のラン１２９（Ｒ２９）に対する処理により、その帰属元ランは第１のラン１０１（Ｒ１）であると判定される。そして、その結果、第６ライン９５に属するラン１２８（Ｒ２８）およびそれに連結された各ランの帰属元ランはラン１０５（Ｒ５）から第１のラン１０１（Ｒ１）に更新される。
【０１０３】
図２１は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を施す際の帰属元の更新処理を説明するための説明図である。ラン１２８（Ｒ２８）における最後部の要素４１４を処理する際、処理対象の要素４１４に隣接する要素はラン１２５（Ｒ２５）内の要素４１６であると判定される。処理中の要素４１４の帰属元ランはこの時点ではラン１０９（Ｒ９）であり、隣接する要素４１６の帰属元ランはこの時点ではラン１０５（Ｒ５）である。したがって、処理中の要素４１４の帰属元ラン１０９（Ｒ９）は隣接する要素４１６の帰属元ラン１０５（Ｒ５）よりも連結性ツリー（連結性グラフ）の下位であるので、ラン１２８（Ｒ２８）の帰属元ランはラン１０５（Ｒ５）に更新される。これに伴い、ラン１２８（Ｒ２８）に隣接するラン１２３（Ｒ２３）の帰属元ランおよびそれまでラン１２３（Ｒ２３）の帰属元ランであったラン１０９（Ｒ９）の帰属元ランはラン１０５（Ｒ５）に更新される。
【０１０４】
図２０は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を施す際の帰属元の更新処理を説明するための説明図である。
【０１０５】
ラン１２９（Ｒ２９）における最後部の要素４１０を処理する際、処理対象の要素４１０に隣接する要素はラン１２８（Ｒ２８）内の要素４１２であると判定される。処理中の要素４１０の帰属元ランはラン１０１（Ｒ１）であり、隣接する要素４１２の帰属元ランはこの時点ではラン１０５（Ｒ５）である。したがって、処理中の要素４１０の帰属元ラン１０１（Ｒ１）は隣接する要素４１２の帰属元ラン１０５（Ｒ５）よりも連結性ツリー（連結性グラフ）の上位であるので、隣接する要素４１２を含むラン１２８（Ｒ２８）の帰属元ランおよびそれまでラン１２８（Ｒ２８）の帰属元ランであったラン１０５（Ｒ５）の帰属元ランはラン１２９（Ｒ２９）の帰属元ランと同様、ラン１０１（Ｒ１）に更新される。
【０１０６】
図２５は、図６に示したクラスマップ８９に対してランレングス符号化／隣接ラン統合処理を行った結果を示す表である。
【０１０７】
なお、ランレングス符号化／隣接ラン統合処理の後、連結パス圧縮部３４が、各ランの連結関係を示す連結情報（帰属元ラン）を圧縮する連結パス圧縮処理を行う。具体的には、連結パス圧縮部３４は、ランＡの帰属元ランＢの帰属元ランがランＣである場合に、ランＡの帰属元ランをランＣに更新することにより、各ランの帰属元ランを最上位のランに圧縮（集約）する。
【０１０８】
図２６は、この連結パス圧縮処理をコンピュータに実行させるための中間コードの一例を示している。また、図２７は、図２５に示したランレングス符号化／隣接ラン統合処理を行った結果に対して連結パス圧縮処理を行った結果を示す表である。
【０１０９】
また、連結パス圧縮部３４が連結パス圧縮処理を行った後、ラベル圧縮部３５が、連結された各成分（同じクラスに属し、かつ互いに隣接する（連結された）ランの集合）に属する各ランに対して成分毎に共通のラベルを付与しなおすラベル圧縮処理を行う。例えば、上述の実施例（図２７に示した例）の場合、帰属元ランがランＲ１である成分は「０」にラベル付けされ、帰属元ランがランＲ２である成分は「１」にラベル付けされ、帰属元ランがランＲ３０である成分は「２」にラベル付けされる。このように、ランインデックスに代えてクラス毎に順次割り付けたラベルを用いることにより、各成分のクラスを識別するための情報に必要とされるビット深度を低減することができる。なお、このラベル圧縮処理は、例えばハッシュテーブルを用いて行うことができる。
【０１１０】
なお、図１５に示すように、ラベル圧縮処理（Ｓ８６）の後に、領域特性（成分特性）の抽出処理（Ｓ３００）を行うようにしてもよい。例えば、図３０に示した構成に加えて、領域特性抽出処理（図示せず）を設け、この領域特性抽出処理が領域特性の抽出処理を行うようにしてもよい。代表的な成分特性としては、領域面積（region area）、成分の境界線（component bounding box）、成分の重心、成分の境界線の中心（component-bounding-box center）、あるいはその他の領域（成分）の特性を示すパラメータが上げられる。領域特性の抽出処理では、例えばランレングスデータを用いてこれらの成分特性を抽出することができる。図２８は、領域特性の抽出処理をコンピュータに実行させるための中間コードの一例を示している。
【０１１１】
また、図１６に示すように、ラベル圧縮処理（Ｓ８６）の後に、ラベル画像生成処理（ラベル画像再構築処理）（Ｓ３０２）を行ってもよい。例えば、図３０に示した構成に加えて、ラベル画像生成部（図示せず）を設け、このラベル画像生成部がラベル画像生成処理を行うようにしてもよい。ラベル画像とは、各ランを当該各ランのクラス（ラベル）と当該各ランのランレングスとに応じて表現した画像である。図２９は、ラベル画像生成処理をコンピュータに実行させるための中間コードの一例を示している。
【０１１２】
また、図１７に示したように、ラベル圧縮処理（Ｓ８６）の後に、領域特性の抽出処理（Ｓ３００）とラベル画像生成処理（Ｓ３０２）とを行うようにしてもよい。また、この場合、領域特性の抽出処理（Ｓ３００）を行った後にラベル画像生成処理（Ｓ３０２）を行うようにしてもよく、ラベル画像生成処理（Ｓ３０２）を行った後に領域特性の抽出処理（Ｓ３００）を行うようにしてもよく、領域特性の抽出処理（Ｓ３００）とラベル画像生成処理（Ｓ３０２）とを並行して行ってもよい。
【０１１３】
以上のように、本実施形態にかかる画像処理装置３０では、初期化処理部３２が符号化処理を行う前にメモリ３１を初期化し、各ランの符号化情報を格納するためのランデータ構造と、符号化情報を格納可能なランの最大値とを設定する。また、ランデータ構造には、このランデータ構造に符号化情報を格納するランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを記憶する帰属元ランフィールドと、上記ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、画像種別情報を予め設定されたデフォルト値に設定する。そして、ランレングス符号化処理部３３は、ラスタ走査方向にそって１画素ずつ走査することで各ランの検出、各ランのランレングスの検出、および各ランの帰属元ランの検出を行い、これらの検出結果に基づいてランデータ構造における上記各フィールドの情報を更新することにより、各ランの符号化情報を生成する。また、ランレングス符号化処理部３３は、符号化したランの数がメモリ３１に格納可能なランの数の最大値より１つ小さい値に達すると、残りの画素をデフォルト値に対応する画像種別の単一のランとみなしてその符号化情報を生成し、メモリ３１に格納して符号化処理を終了する。
【０１１４】
これにより、クラスマップに含まれるランの数がメモリ３１に格納可能なランの最大値を超過している場合であっても、当初に生成した符号化情報が上書きされるなどして失われることを防止できる。
【０１１５】
なお、クラスマップに含まれるランの数がメモリ３１に格納可能なランの最大値を超過している場合、クラスマップにおけるラスタ走査方向の末尾に位置する一部のランはデフォルト値に対応するクラス（例えば背景領域）として符号化されるので、クラスマップ全体に対する符号化処理を行うことはできないものの、クラスマップにおけるラスタ走査方向の先頭から所定数のランについては適切に符号化処理を行ってその結果をメモリ３１に残すことができる。
【０１１６】
これにより、例えば、メモリ３１に格納された符号化結果を参照してクラスマップに対応する原稿の天地判定や原稿種別判定などを適切に行うことができる。上記の天地判定や原稿種別判定の方法は特に限定されるものではないが、例えば、各種原稿のレイアウト例を予め記憶しておき、符号化結果からクラスマップにおける各画像種別に対応する領域のレイアウトを検出し、検出したレイアウトと予め記憶させておいたレイアウト例とを比較することにより、天地判定や原稿種別判定を行うようにしてもよい。上記の原稿種別としては、例えば、複数ページ分の原稿画像を１枚の用紙上に割り付けた割付原稿、テキスト領域を複数のブロックに分けて配置した段組原稿、所定形状の罫線を含む伝票や帳票などが挙げられる。
【０１１７】
また、図３０に示した画像処理装置３０の構成に加えて、上記の天地判定処理を行う天地判定処理部を備えてもよい。また、図３０に示した画像処理装置３０の構成に加えて、上記の原稿種別判定処理を行う原稿種別判定処理部を備えてもよい。
【０１１８】
また、メモリ３１に格納可能な１ラインあたりのランの数の最大値（ライン最大値）を設定し、符号化処理中のラインにおける未符号化処理のランの数がそれら各ランをデフォルトクラスに設定することしかできない数になった場合に、残りの要素をデフォルトクラスに属する単一のランとみなして符号化して当該ラインに対する符号化処理を終了し、次のラインの符号化処理を開始するようにしてもよい。
【０１１９】
また、上記実施形態において、画像処理装置３０に備えられる各部（各ブロック）を、ＣＰＵ等のプロセッサを用いてソフトウェアによって実現してもよい。この場合、画像処理装置３０は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアである画像処理装置３０の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、画像処理装置３０に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによって達成される。
【０１２０】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１２１】
また、画像処理装置を通信ネットワークと接続可能に構成し、通信ネットワークを介して上記プログラムコードを供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【０１２２】
また、画像処理装置３０の各ブロックは、ソフトウェアを用いて実現されるものに限らず、ハードウェアロジックによって構成されるものであってもよく、処理の一部を行うハードウェアと当該ハードウェアの制御や残余の処理を行うソフトウェアを実行する演算手段とを組み合わせたものであってもよい。
【０１２３】
本発明は上述した実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能である。すなわち、請求項に示した範囲で適宜変更した技術的手段を組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【産業上の利用可能性】
【０１２４】
本発明は、画像データをランレングス符号化する画像処理装置および画像処理方法に適用することができる。
【符号の説明】
【０１２５】
３０ 画像処理装置
３１ メモリ
３２ 初期化処理部
３３ ランレングス符号化処理部
３４ 連結パス圧縮部
３５ ラベル圧縮部
【特許請求の範囲】
【請求項１】
画像データにおける各画素の画像種別を示す情報であるクラスマップデータから、同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化処理部と、符号化した符号化データを格納する記憶手段とを備えた画像処理装置であって、
符号化に先立って上記記憶手段を初期化する初期化処理部を備え、
上記初期化処理部は、
各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、
上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、
上記画像種別情報を予め設定されたデフォルト値に設定し、
上記ランレングス符号化処理部は、
上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、
抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、
今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、
上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、
符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了することを特徴とする画像処理装置。
【請求項２】
上記初期化処理部は、
上記記憶手段に格納可能な１走査ラインあたりのランの数の最大値であるライン最大値を設定し、
上記ランレングス符号化処理部は、各走査ラインについて、符号化情報を生成したランの数が上記ライン最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない当該走査ラインについての残りの画素数に更新し、画像種別については上記デフォルト値のままにすることによって生成し、当該走査ラインについての符号化処理を終了することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
上記初期化処理部は、上記ランデータ構造を走査ライン毎に生成し、
上記ランレングス符号化処理部は、各ランの符号化情報を当該ランが属する走査ラインに対応する上記ランデータ構造を用いて生成することを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
上記初期化処理部は、初期化時に上記画像種別情報として設定する上記デフォルト値を、上記画像データにおける背景領域を示す値に設定することを特徴とする請求項１から３のいずれか１項に記載の画像処理装置。
【請求項５】
画像データにおける各画素の画像種別を示す情報であるクラスマップデータから同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化工程と、符号化したデータを記憶手段に格納する記憶工程とを含む画像処理方法であって、
符号化処理工程に先立って上記記憶手段を初期化する初期化処理工程を含み、
上記初期化処理工程では、
各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、
上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、
上記画像種別情報を予め設定されたデフォルト値に設定し、
上記ランレングス符号化工程では、
上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、
抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、
今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、
上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、
符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了することを特徴とする画像処理方法。
【請求項１】
画像データにおける各画素の画像種別を示す情報であるクラスマップデータから、同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化処理部と、符号化した符号化データを格納する記憶手段とを備えた画像処理装置であって、
符号化に先立って上記記憶手段を初期化する初期化処理部を備え、
上記初期化処理部は、
各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、
上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、
上記画像種別情報を予め設定されたデフォルト値に設定し、
上記ランレングス符号化処理部は、
上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、
抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、
今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、
上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、
符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了することを特徴とする画像処理装置。
【請求項２】
上記初期化処理部は、
上記記憶手段に格納可能な１走査ラインあたりのランの数の最大値であるライン最大値を設定し、
上記ランレングス符号化処理部は、各走査ラインについて、符号化情報を生成したランの数が上記ライン最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない当該走査ラインについての残りの画素数に更新し、画像種別については上記デフォルト値のままにすることによって生成し、当該走査ラインについての符号化処理を終了することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
上記初期化処理部は、上記ランデータ構造を走査ライン毎に生成し、
上記ランレングス符号化処理部は、各ランの符号化情報を当該ランが属する走査ラインに対応する上記ランデータ構造を用いて生成することを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
上記初期化処理部は、初期化時に上記画像種別情報として設定する上記デフォルト値を、上記画像データにおける背景領域を示す値に設定することを特徴とする請求項１から３のいずれか１項に記載の画像処理装置。
【請求項５】
画像データにおける各画素の画像種別を示す情報であるクラスマップデータから同じ画像種別に属する画素であって上記画像データの走査ライン方向に隣接する画素の集合であるランを抽出し、各ランのラスタ走査方向に沿った順序と各ランの画素数とに基づいて上記クラスマップデータを符号化するランレングス符号化工程と、符号化したデータを記憶手段に格納する記憶工程とを含む画像処理方法であって、
符号化処理工程に先立って上記記憶手段を初期化する初期化処理工程を含み、
上記初期化処理工程では、
各ランについての符号化結果を示す符号化情報を格納するためのランデータ構造を設定して上記記憶手段に記憶させるとともに、上記記憶手段に符号化結果を格納可能なランの数の最大値を設定し、
上記ランデータ構造に、当該ランデータ構造に符号化情報を格納するランである格納対象ランと同じ画像種別に属するランのうちラスタ走査方向の最上流側に位置するランである帰属元ランを示す帰属元情報を記憶する帰属元ランフィールドと、上記格納対象ランの画像種別を示す画像種別情報を記憶する画像種別フィールドと、上記格納対象ランの長さを示すランレングス情報を記憶するランレングスフィールドとを設け、
上記画像種別情報を予め設定されたデフォルト値に設定し、
上記ランレングス符号化工程では、
上記画像データのラスタ走査方向に沿って注目画素を１画素ずつ順次移動させながら今回の注目画素の画像種別と前回の注目画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別の画素であって走査ライン方向に隣接する画素の集合であるランを抽出し、抽出した上記ランに含まれる各画素の画像種別を示す情報を当該ランの画像種別情報として検出する処理と、
抽出した上記ランの画素数を当該ランのランレングス情報として検出する処理と、
今回の注目画素の画像種別と当該注目画素が属する走査ラインに対してラスタ走査方向の上流側に隣接する走査ラインの画素であって当該注目画素に隣接する画素の画像種別とを比較する処理を各画素について行うことにより、同じ画像種別のランであって異なる走査ライン間で隣接するランの集合からなる連結領域を抽出し、抽出した連結領域に属するランのうちラスタ走査方向の最上流側に位置するランを示す情報を当該連結領域に属する各ランの帰属元情報として検出する処理と、
上記ランデータ構造における帰属元ランフィールド、画像種別フィールド、およびランレングスフィールドに格納されている情報を、各ランについて検出した帰属元情報、画像種別情報、およびランレングス情報に基づいて更新する処理をラン毎に行うことで各ランについての符号化情報を生成する処理とを行い、
符号化情報を生成したランの数が上記最大値よりも１つ少ない数に達した場合、次のランの符号化情報を、上記ランデータ構造に対し、帰属元情報については当該ラン自身を示す情報に更新し、ランレングス情報については符号化処理を行っていない残りの画素数に更新し、画像種別情報については上記デフォルト値のままにすることによって生成し、符号化処理を終了することを特徴とする画像処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【公開番号】特開２０１０−３５１７３（Ｐ２０１０−３５１７３Ａ）
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願番号】特願２００９−１７４６２０（Ｐ２００９−１７４６２０）
【出願日】平成２１年７月２７日（２００９．７．２７）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願日】平成２１年７月２７日（２００９．７．２７）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
[ Back to top ]