(57)【要約】【課題】  ラベリング処理をブロック画像単位に行う。【解決手段】  画像200を所定サイズの複数のブロック画像に分割し、ブロック画像をラベリング処理したブロックラベル画像を生成する。ブロックラベル画像に割り当てられたラベルのうち、互いに隣接するブロックラベル画像の統合により変更される可能性があるラベルである未確定ラベルに関するブロックラベル情報を生成する。互いに隣接するブロックラベル画像のブロックラベル情報に基づき、隣接するブロックラベル画像に割り当てられたラベルを更新して、隣接するブロックラベル画像を統合したブロックラベル画像と、統合したブロックラベル画像のブロックラベル情報を生成する。ラベル画像の生成、ラベル情報の生成、および、統合を制御して、画像200の全体をラベリング処理する。【選択図】  図2
2014203134.tif 000002
【特許請求の範囲】
【請求項１】
画像を所定サイズの複数のブロック画像に分割する分割手段と、
前記ブロック画像をラベリング処理したブロックラベル画像を生成するラベル画像の生成手段と、
前記ブロックラベル画像に割り当てられたラベルのうち、互いに隣接するブロックラベル画像の統合により変更される可能性があるラベルである未確定ラベルに関するブロックラベル情報を生成するラベル情報の生成手段と、
互いに隣接するブロックラベル画像のブロックラベル情報に基づき、前記隣接するブロックラベル画像に割り当てられたラベルを更新して、前記隣接するブロックラベル画像を統合したブロックラベル画像と、前記統合したブロックラベル画像のブロックラベル情報とを生成する統合手段と、
前記ラベル画像の生成手段、前記ラベル情報の生成手段、および、前記統合手段を制御して、前記画像の全体をラベリング処理する制御手段とを有することを特徴とする画像処理装置。
【請求項２】
前記未確定ラベルは前記ブロック画像の端部の画素に割り当てられたラベルであり、前記ブロックラベル情報は前記未確定ラベルが前記ブロックラベル画像の端部それぞれに出現するか否かを示すことを特徴とする請求項1に記載された画像処理装置。
【請求項３】
前記ラベル情報の生成手段は、前記端部に出現しないラベルを前記ブロックラベル画像において一意のラベルに置き換えることを特徴とする請求項2に記載された画像処理装置。
【請求項４】
前記統合手段は、前記隣接するブロックラベル画像のブロックラベル情報が、前記隣接するブロックラベル画像の接続部における前記未確定ラベルの出現を示す場合、前記隣接するブロックラベル画像の端部を走査して前記ラベルの更新を行うことを特徴とする請求項1から請求項3の何れか一項に記載された画像処理装置。
【請求項５】
前記統合手段は、前記未確定ラベルをもたないブロックラベル画像について、前記ラベルの更新を省略することを特徴とする請求項1から請求項4の何れか一項に記載された画像処理装置。
【請求項６】
前記統合手段は、前記統合したブロックラベル画像の端部に出現しないラベルを前記画像の全体において一意のラベルに置き換えることを特徴とする請求項1から請求項5の何れか一項に記載された画像処理装置。
【請求項７】
前記統合手段は、前記画像の所定の領域に対応するブロックラベル画像から前記統合を開始することを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項８】
前記統合手段は、前記統合の処理時間または前記統合したブロックラベル画像の数が所定の条件を満たした場合、前記統合を終了することを特徴とする請求項7に記載された画像処理装置。
【請求項９】
前記画像は、エッジ検出処理において三値化されたエッジ強度画像であることを特徴とする請求項1から請求項8の何れか一項に記載された画像処理装置。
【請求項１０】
前記エッジ強度画像は、前記エッジ検出処理において、エッジ画素または非エッジ画素として確定された画素、および、前記エッジ画素か否かが未確定の画素を表すことを特徴とする請求項9に記載された画像処理装置。
【請求項１１】
分割手段、ラベル画像の生成手段、ラベル情報の生成手段、統合手段、制御手段を有する画像処理装置の画像処理方法であって、
前記分割手段が、画像を所定サイズの複数のブロック画像に分割し、
前記ラベル画像の生成手段が、前記ブロック画像をラベリング処理したブロックラベル画像を生成し、
前記ラベル情報の生成手段が、前記ブロックラベル画像に割り当てられたラベルのうち、互いに隣接するブロックラベル画像の統合により変更される可能性があるラベルである未確定ラベルに関するブロックラベル情報を生成し、
前記統合手段が、互いに隣接するブロックラベル画像のブロックラベル情報に基づき、前記隣接するブロックラベル画像に割り当てられたラベルを更新して、前記隣接するブロックラベル画像を統合したブロックラベル画像と、前記統合したブロックラベル画像のブロックラベル情報とを生成し、
前記制御手段が、前記ラベル画像の生成手段、前記ラベル情報の生成手段、および、前記統合手段を制御して、前記画像の全体をラベリング処理することを特徴とする画像処理方法。
【請求項１２】
コンピュータを請求項1から請求項10の何れか一項に記載された画像処理装置の各手段として機能させるためのプログラム。
【請求項１３】
請求項12に記載されたプログラムが格納されたコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像をラベリング処理する画像処理に関する。
【背景技術】
【０００２】
画像を構成する画素の値と画素の空間的な関係から、各画素にラベルを付与する画像処理（以後、ラベリング処理）は、画像中から類似または同じ値をもつ画素の連結状態を求める処理である。例えば、二値化画像について、画素値がオンを示す連結した画素の領域ごとに異なったラベルを割り当てる処理がラベリング処理に該当する。
【０００３】
ラベリング処理は領域に基づく画像処理に有用であり、例えば、画像中からある条件を満たす領域を検出し、検出した領域ごとに、例えば色やエッジ量などに関する特徴量が求めることができる。あるいは、認識した物体の領域を検出する処理に用いて、検出した領域を切出マスクの情報として当該領域を画像編集用に切り出したり、領域ごとに異なる画像処理（例えば色変換など）を行うことができる。
【０００４】
ラベリング処理アルゴリズムとしては、領域拡張法（リージョングローイング法）が知られている。この処理は次の手順A、Bを再帰的に実行し、すべての画素にラベルを付与すると終了する。
(A)注目画素が属する領域が未判定の場合、新しい領域として新しいラベルを割り当て、
(b)注目画素に隣接する八画素（または上下左右の四画素）を参照し、連結条件が成立する場合は、隣接画素に注目画素と同じラベルを付与する。つまり、隣接画素を注目画素と同じ領域と判定する。
【０００５】
なお、連結条件は、例えば、隣接画素の値が、注目画素の値と同じまたは近いなどである。
【０００６】
領域拡張法は、アルゴリズムが簡易である一方で再帰処理を必要とする。従って、例えば組込ソフトウェアにおいて領域拡張法を実行しようとすると、ハードウェアなどの資源（メモリ量やCPU処理能力）が限られ、実行が困難な場合がある。
【０００７】
再帰的な処理を必要とせずに、画像を二回読み込むことでラベリング処理を実現する方法が知られている（例えば、非特許文献1、2）。以下、この方式を「2パスラベリング法」と呼ぶことにする。
【０００８】
2パスラベリング法は、画像を一回目に読み込む際に一次ラベリング処理を行い、一次ラベリング処理によって付与したラベル（以下、一次ラベル）の接続情報を保持する。一次ラベルの接続情報は、一次元の配列で実現できることが知られている（非特許文献1）。つまり、2パスラベリング法は、領域拡張法に必要な再帰的な処理が不要になるメリットがある。しかし、画像の解像度が高くなればなるほど、一次ラベルの接続情報の保持に必要なメモリ量が増加する問題がある。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】服部哲郎「パイプライン方式によるリアルタイムの領域ラベリング(I) −基本アルゴリズムと正当性の証明−」TECHNICAL REPORT OF IEICE、PRU93-62、 HC93-36、1993年10月
【非特許文献２】服部哲郎、太田郁義「パイプライン方式によるリアルタイムの領域ラベリング(II) −基本アルゴリズムの拡張方式−」TECHNICAL REPORT OF IEICE、PRU93-63、 HC93-37、1993年10月
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明は、ラベリング処理をブロック画像単位に行うことを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１２】
本発明にかかる画像処理は、画像を所定サイズの複数のブロック画像に分割し、前記ブロック画像をラベリング処理したブロックラベル画像を生成し、前記ブロックラベル画像に割り当てられたラベルのうち、互いに隣接するブロックラベル画像の統合により変更される可能性があるラベルである未確定ラベルに関するブロックラベル情報を生成し、互いに隣接するブロックラベル画像のブロックラベル情報に基づき、前記隣接するブロックラベル画像に割り当てられたラベルを更新して、前記隣接するブロックラベル画像を統合したブロックラベル画像と、前記統合したブロックラベル画像のブロックラベル情報を生成し、前記ラベル画像の生成、前記ラベル情報の生成、および、前記統合を制御して、前記画像の全体をラベリング処理することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、ラベリング処理をブロック画像単位に行うことができる。
【図面の簡単な説明】
【００１４】
【図１】実施例の画像処理装置の構成例を示すブロック図。
【図２】一次ラベルの接続情報の保持に必要なメモリ量の増加の問題を説明する図。
【図３】本実施例のラベリング法の概略を説明する図。
【図４】ブロックラベル付与処理の詳細を説明する図。
【図５】ブロックラベル付与処理を行う画像処理部の構成例を説明するブロック図。
【図６】連結条件判定ウィンドウの一例を示す図。
【図７】処理対象の二値画像のブロック画像例とブロックラベル付与処理の結果例を示す図。
【図８】一次ラベルの接続関係を示す接続関係テーブルと接続情報テーブルの一例を示す図。
【図９】接続関係テーブルと接続情報テーブルの変遷の一例を示す図。
【図１０】接続情報と外接情報の統合を説明するフローチャート。
【図１１】処理後の接続関係テーブルと接続情報テーブルの一例を示す図。
【図１２】ラベルを確定ラベルと未確定ラベルに区分する処理を説明するフローチャート。
【図１３】ブロックラベル付与処理の結果例を示す図。
【図１４】統合処理するブロックラベル画像の一例を示す図。
【図１５】統合処理するブロックラベル画像の接続関係テーブルおよび外接情報テーブルを示す図。
【図１６】ラベル更新処理を説明する図。
【図１７】ブロックラベル統合処理後のブロックラベル画像の一例を示す図。
【図１８】実施例2の画像処理部の構成例を説明するブロック図。
【発明を実施するための形態】
【００１５】
以下、本発明にかかる実施例の画像処理を図面を参照して詳細に説明する。
【実施例１】
【００１６】
［装置の構成］
図1のブロック図により実施例の画像処理装置の構成例を示す。なお、実施例の画像処理装置は、実施例の画像処理を実現するコンピュータ機器などのデータ処理装置によって実現される。
【００１７】
CPU104は、RAM106をワークメモリとして、ROM105やデータ保存部102に格納されたオペレーティングシステム(OS)や各種プログラムを実行し、システムバス110を介して後述する構成を制御する。なお、CPU104は一つのプロセッサに限らず、CPU104としてマルチプロセッサまたはマルチコアプロセッサが利用可能である。
【００１８】
データ入力部101は、例えば画像データを入力するUSBなどのシリアルバスインタフェイスや、CCDやCMOSセンサを用いた撮像部である。データ入力部101は、入力したデータを後述するRAM106やデータ保存部102に格納する。
【００１９】
データ保存部102は、画像データなどを保持する記憶部または記録媒体である。データ保存部102として、例えば、ハードディスクドライブ(HDD)、ソリッドステートドライブ(SSD)、フラッシュメモリ、USBメモリ、あるいは、各種ディスクメディア、メモリカードなどのドライブが利用可能である。データ保存部102は、画像データのほかにも各種プログラムや各種データを保持する。また、後述するRAM106の一部や、後述する通信部107を介した接続先の機器をデータ保存部102として用いることもできる。
【００２０】
表示部103は、画像処理の前後の画像を表示したり、グラフィカルユーザインタフェイス(GUI)を表示する液晶パネル(LCD)などである。勿論、ビデオインタフェイスとケーブルを介して接続された装置外のディスプレイ装置でも構わない。
【００２１】
入力部108は、ユーザ指示やデータを入力するキーボード、マウス、トラックボール、トラックパッド、タブレットなどのポインティングデバイスである。また、実施例のデータ処理装置をディジタルカメラやプリンタなどの機器の一部として構成する場合、入力部108はボタンやダイヤルなどで構成されてもよい。また、表示部103をタッチスクリーンとして、ソフトウェアキーボードやボタンを表示し、それを入力部108としてもよい。
【００２２】
あるいは、公知のジェスチャ認識処理によりユーザ指示を入力する入力部108としてもよい。その場合、入力部108は、可視光線または赤外線による画像を入力する入力部と、入力した画像からユーザ動作を認識してコマンド（ユーザ指示）に変換する変換部から構成される。入力部はデータ入力部101を利用することができ、変換部は専用回路で構成するか、CPU104上で動作するプログラムによって構成すればよい。
【００２３】
通信部107は、ネットワーク111を介して機器間の通信を行うためのインタフェイスである。ネットワーク111は、Ethernet（登録商標）、シリアルバス（USB、IEEE1394）、公衆回線などの有線ネットワークである。あるいは、赤外線(IrDA)、IEEE802.11a/b/g/n、Bluetooth（登録商標）、Ultra Wide Band (UWB)、近距離通信(NFC)などの無線ネットワークでもよい。
【００２４】
画像処理部109は、詳細は後述するが、実施例の画像処理を実行する。
【００２５】
なお、図1には、データ入力部101、データ保存部102、表示部103、入力部108がすべて一つの装置に含まれる構成を示した。しかし、それらの一つまたは複数を含む機器が、上記の有線/無線ネットワークなどによって接続され、所定の通信を行うことで、全体として図1に示す構成が得られる場合も実施例に含まれる。
【００２６】
［ラベリング処理］
●2パスラベリング法
上述したように、リージョングローイング法に比べて2パスラベリング法は、再帰的な処理が不要になるメリットがある一方、画像の解像度が高くなると、一次ラベルの接続情報の保持に必要なメモリ量が増加する問題がある。図2により一次ラベルの接続情報の保持に必要なメモリ量の増加の問題を説明する。なお、図2においては、簡単化のために、二値画像におけるオン画素にラベルを付与する（割り当てる）例を説明する。
【００２７】
図2(a)および(b)は、部分画像における注目画素Dとその近傍画素（斜線を施した画素）を示す。図2(a)は注目画素Dに隣接する計八画素を近傍画素とする例を示し、図2(b)は注目画素601の上下左右に位置する四画素を近傍画素とする例を示す。近傍画素は、処理アルゴリズムなどによって定義されるが、以下では、図2(a)に示す注目画素601の周囲の八画素を隣接画素とする例を説明する。
【００２８】
注目画素Dと隣接画素が何れもオン画素の場合、注目画素Dと当該隣接画素は同一領域に属するとして単一のラベルが付与される。このラベルの数が最大になる場合を説明する。
【００２９】
図2(c)(d)はラベルの数が最大になる場合を示す。なお、図2(c)(d)において、斜線を施した画素がオン画素、白地の画素はオフ画素を示す。また、図2(c)は画像の幅と高さが偶数（8×8画素）の例であり、図2(d)は画像の幅と高さが奇数（9×9画素）の例である。
【００３０】
図2(c)(d)において、周囲八画素を隣接画素とする場合、ラベルの最大数は下式で与えられる。
Lmax = ceil(w/2)×ceil(h/2)      …(1)
ここで、Lmaxはラベルの最大数、
wは画像の幅、
hは画像の高さ、
ceil(x)はx以上になる最小の整数を得る関数。
【００３１】
式(1)から画素数の増加に従いラベルの最大数が増加することがわかる。式(1)によれば、画素数とラベルの最大数は単純な比例関係にあるが、例えばディジタルカメラなどの画素数が、縦横に二次元的に増加することを考慮すると、ラベルの最大数も二次関数的に増加することが容易に予想される。
【００３２】
加えて、Lmaxを表現するために必要なビット長さも増加することになる。Lmaxを表現するために必要なビット長Lは下式で求められる。
L = ceil{log2(Lmax+1)}      …(2)
【００３３】
式(2)において、右端の(Lmax+1)の「+1」は処理対象外の画素、この例ではオフ画素に対応するラベルの分である。従って、一次ラベルに必要なメモリ量ML（単位はビット）は下式で表される。
ML = Lmax×L = Lmax×ceil{log2(Lmax+1)}      …(3)
【００３４】
式(3)からは、二次関数的な増加を示すラベルの最大数Lmaxに対して、必要なメモリ量MLがそれ以上の割合で増加することが示される。次に、具体例を挙げる。
【００３５】
640×480画素の画像（いわゆるVGA画像）の場合：
ラベルの最大数  Lmax0 = ceil(640/2)×ceil(480/2) = 76,800、
ビット長        L00 = ceil{log2(76,800+1)} = 17、
メモリ量        ML0 = 76,800×17 = 1,305,600 ≒ 1.25Mビット。
【００３６】
1920×1080画素の画像（いわゆるフルHD画像）の場合：
ラベルの最大数  Lmax0 = ceil(1920/2)×ceil(1080/2) = 518,400、
ビット長        L0 = ceil{log2(518,400+1)} = 19、
メモリ量        ML0 = 518,400×19 = 9,849,600 ≒ 9.39Mビット。
【００３７】
上記の例を比較すると、フルHD画像の画素数はVGA画像の6.75倍であるが、フルHD画像に必要なメモリ量はVGA画像の約7.5倍になる。このことから、以下の二点が言える。
・画像サイズが大きくなるほど一次ラベルの接続情報の保持に必要なメモリ量が増加する、
・必要メモリ量の増加率は、画素数の増加率より大きい。
【００３８】
一次ラベルの接続情報を保持するメモリ領域をDRAMなどで構成される共有メモリに割り当てることが考えられる。しかし、2パスラベリング法の場合、一次ラベルの作成後、一次ラベルの接続情報に対する統合処理を行う。この統合処理において、メモリのランダムアクセスが発生する（非特許文献1参照）。つまり、DRAMなどに一次ラベルの接続情報を格納した場合、ランダムアクセスを伴うことから、充分なパフォーマンスが得られない可能性が高い。
【００３９】
勿論、一次ラベルの接続情報を保持するメモリとしてSRAMなどの低遅延メモリを利用することも考えられる。しかし、
(1)SRAMは比較的高価、
(2)予め用意されたSRAMの容量が許容する範囲以下の画素数の画像しか処理できない、
(3)画像サイズの増加以上の割合でSRAMのメモリ量が増加する、
【００４０】
などを考慮すると、SRAMでは高解像度画像への対応が困難であることが容易に理解される。言い換えれば、将来を見越したメモリ量を予め搭載すれば装置の高価格化につながる。逆に、その時点時点で必要最小限のメモリ量を搭載すれば、画像サイズの拡大の度に設計変更が発生する。
【００４１】
●実施例のラベリング法
本実施例においては、上記の課題を解決するために、画像をブロック単位にラベリング処理する。図3により本実施例のラベリング法の概略を説明する。
【００４２】
図3において、入力画像200は所定サイズのブロック画像210-221に分割され、各ブロック画像にラベル（以下、ブロックラベル）が付与される。なお、ブロックラベルの付与処理については後述する。ブロックラベルの付与処理により、各ブロック画像に対応するブロックラベル画像230-241とブロックラベル情報250-261が得られる。ブロックラベル情報は、詳細は後述するが、後続するブロックラベルの統合処理において用いる情報である。
【００４３】
図3において、ブロック画像210に対してブロックラベル画像230とブロックラベル情報250が得られる。同様に、ブロック画像211に対してブロックラベル画像231とブロックラベル情報251、…、ブロック画像221に対してブロックラベル画像241とブロックラベル情報261がそれぞれ得られる。
【００４４】
続いて、詳細は後述するが、ブロックラベル画像とブロックラベル情報を統合するブロックラベル統合処理を行う。図3の例においては、ブロックラベル画像230、231、234、235が統合されてブロックラベル画像270が、ブロックラベル画像232、233、236、237が統合されてブロックラベル画像271がそれぞれ得られる。また、ブロックラベル画像238と239が統合されてブロックラベル画像272が、ブロックラベル画像240と241が統合されてブロックラベル画像273が得られる。その際、ブロックラベル画像270、271、272、273にそれぞれ対応するブロックラベル情報280、281、282、283が作成される。
【００４５】
さらに、ブロックラベル画像270-273が統合されて入力画像200に対するラベル画像290が得られ、処理は終了する。なお、最終的なラベル画像290に対してブロックラベル情報を生成する必要はない。ブロックラベル情報は、ラベリング処理の中間状態であるブロックラベル画像に関する情報であり、最終的なラベル画像290には不要である。
【００４６】
●ブロックラベル付与処理
ブロックラベル付与処理は、入力画像から分割されたブロック画像にラベルを付与する処理である。図4によりブロックラベル付与処理の詳細を説明する。
【００４７】
図4(a)はブロック画像にラベルを付与した例を示す。なお、図4(a)は8×8画素のブロック画像例を示している。ブロック画像において、黒ベタまたは斜線を施した画素はオン画素であり、それぞれラベル1からラベル3（矩形内の数字）が付与されている。このラベル付与は、公知の方法で行えばよいが、以下では2パスラベリング法で行うとして説明する。
【００４８】
ブロック画像700が入力画像の一部であることを考慮すると、ラベル1からラベル3には以下のような特徴がある。
ラベル1：ブロック画像の上端に付与画素があり、ブロック画像の上端に接続する他のブロック画像がある場合、当該ブロック画像のラベルと隣接し、統合される可能性がある。
ラベル2：ブロック画像の端に付与画素がなく、他のブロック画像のラベルと統合する必要がない。
ラベル3：ブロック画像の右端と下端に付与画素があり、ブロック画像の右端、下端に接続する他のブロック画像がある場合、それらブロック画像のラベルと隣接し、統合される可能性がある。
【００４９】
言い換えると、図4(a)に示すブロック画像の場合、ラベル2に属す画素の集合（ラベル2をもつ領域の形状）は、他のブロック画像を参照せずに図4(a)に示すブロック画像だけで確定することができる。一方、ラベル1および3は他のブロック画像における他のラベルと隣接する可能性があり、ラベル1および3に属す画素の集合は図4(a)に示すブロック画像だけでは確定することができない。
【００５０】
以後、説明の簡単化のため、ラベル2のように、そのブロックラベル画像単体で確定することができるラベルを「確定ラベル」と呼び、他のブロックラベル画像と統合しないと確定することができないラベル1や3のようなラベルを「未確定ラベル」と呼ぶ。
【００５１】
実施例のラベリング法においては、ブロック画像の外周のどこに未確定ラベルが出現するかを管理する。具体的には、各未確定ラベルについて、当該ラベルに属する画素がブロック画像の外周の四端の何れかに存在するか否かを管理する。例えばブロック画像の右端に付与画素が存在する未確定ラベルは、そのブロックラベル画像と、その右側に位置するブロックラベル画像との統合時にラベル統合の判定対象になる。
【００５２】
この処理を実現するには、各未確定ラベルについて四端の何れかに当該ラベルが付与された画素が存在するか否かを示す情報があればよい。従って、未確定ラベルごとに、各端について1ビットの情報があればよく、四端分の4ビットの情報があればよい。以下、未確定ラベルそれぞれもつこの4ビットの情報を「外接情報」と呼ぶ。
【００５３】
ここで、未確定ラベルの数について説明する。図4(b)(c)のブロック画像例は、未確定ラベルの数が最大になる場合を示し、図4(b)はブロック画像の幅と高さが偶数の例を、図4(c)はブロック画像の幅と高さが奇数の例を示す。
【００５４】
図4(b)(c)において、黒ベタ矩形はオン画素を、白抜き矩形はオフ画素を表し、斜線を施した領域はブロック画像の非外周領域を示す。非外周領域に属する画素は次の何れかである。
・オフ画素、
・確定ラベルに属する画素、
・外周のオン画素と同じラベルが付与された画素。
【００５５】
従って、非外周領域の画素の状態により未確定ラベルが増えることはなく、ブロック画像の外周領域に位置するオン画素すべてに異なるラベルが付与されている場合、そのブロック画像における未確定ラベルの数が最大になる。
【００５６】
ラベリング処理の中間状態で出現するラベルの数は式(1)と同様に下式で表される。
Lbmax = ceil(Bw/2)×ceil(Bh/2)      …(4)
ここで、Lbmaxはブロック画像に出現するラベルの最大数、
Bwはブロック画像の幅、
Bhはブロック画像の高さ。
【００５７】
また、式(2)と同様にLbmaxの表現に必要なビット長さLbは下式で表される。
Lb = ceil{log2(Lbmax+1)}      …(5)
【００５８】
ここで、ブロック画像にラベルを付与した後の未確定ラベルの数を考える。まず、図4(c)の奇数×奇数ブロック画像の例において、未確定ラベルの最大数Lbumaxは下式で表される。
if (Bw = 2N+1 and Bh = 2N+1)
Lbumax = Np/2 = Bw + Bh；      …(6)
ここで、Nは自然数、
Npは外周画素の数。
【００５９】
一方、図4(b)に示す偶数×偶数ブロック画像の場合、図4(c)のようにオン画素とオフ画素を綺麗に配置することはできず、未確定ラベルの最大数Lbumaxは下式で表される。
if (Bw = 2N or Bh = 2N)
Lbumax ＜ Np/2 = Bw + Bh；      …(7)
【００６０】
式(6)(7)から下式が得られる。
Lbumax ≦ Bw + Bh      …(8)
【００６１】
［画像処理部］
図5のブロック図によりブロックラベル付与処理を行う画像処理部109の構成例を説明する。
【００６２】
制御部801は、ブロック処理部802および統合処理部804を制御するとともに、RAM106からメモリ803へのデータ読込、メモリ803からRAM106へのデータ書出を制御する。
【００６３】
メモリ803は、ブロック処理部802のワークメモリとして機能し、また、ブロック処理部802の処理結果が格納される。好ましくは、メモリ803は、SRAMなどの低遅延のメモリで構成される。また、制御部801の制御により、RAM106から読み出されたデータがメモリ803に書き込まれたり、RAM106に転送するためにメモリ803から処理結果のデータが読み出されたりする。
【００６４】
統合処理部804は、制御部801の制御に従い、メモリ803を参照、更新しながらブロック統合処理を実行する。ブロック統合処理において、RAM106から必要なデータが読み込まれ、処理結果はRAM106へ送信される。
【００６５】
図5に示す例において、ブロック処理部802、メモリ803、統合処理部804はシステムバス110と直結されず、これらの処理部はRAM106との間で直接データの送受を行うことができない。しかし、これら処理部とRAM106の間で直接データの送受を可能にする変形は、当業者にとって容易であり、そのような構成も本実施例の一部である。
【００６６】
ブロック処理部802は、制御部801の指示に従い、メモリ803を参照、更新しながらブロックラベリング処理を行う。ブロック処理部802のブロックラベリング処理により生成されるデータは、メモリ803に一旦格納された後、制御部801の制御によりRAM106へ転送される。
【００６７】
仮に、2パスラベリング法を同様な構成で実現する場合、一次ラベルの接続情報はメモリ803に保存されるか、RAM106に保存されることになる。前者の場合、式(3)に示したように、画像サイズに応じたメモリ量が必要になり、画像の高解像度化に伴い必要なメモリ量が増大し、回路規模の増大やそれに伴う装置の高価格化を招く。一方、後者の場合、一次ラベルの接続情報はRAM106に保存されるので、回路規模の増加と装置の高価格化を抑制することができる。
【００６８】
しかし、2パスラベリング法においては、2パス目の処理前にラベル統合処理を行い、一次ラベルの接続情報に対するランダムアクセス、つまり、画像処理部109によるRAM106のランダムアクセスが生じる。ランダムアクセスのため、画像処理部109とRAM106の間で高効率のデータ転送（例えばデータのプリフェッチ）を行うことは困難である。これを緩和するために、画像処理部109にキャッシュ機構を設けることも考えられるが、ランダムアクセスであるためキャッシュ機構の効果が充分に得られない可能性が高い。
【００６９】
これに対して、本実施例のラベリング法においては、画像をブロック単位に処理するため、メモリ803に必要なメモリ量を2パスラベリング法に比べて小さくすることができる。例えば、1920×1080画素のフルHD画像を処理する場合、本実施例のブロックラベル付与処理に必要なメモリ量は次のとおりである。なお、本実施例のブロックラベル付与処理は、ブロックサイズによって必要なメモリ量が変化する。下記の計算例はブロックサイズを16×16画素として例である。
【００７０】
●2パスラベリング法と実施例で共通に必要なメモリ量
ラベル画像メモリとして1920×1080/4×32ビット≒15.8Mビット。なお、式(2)に示すように、フルHD画像の場合、Lmaxを表現するために必要なビット長Lは19ビットだが、メモリアクセスを考慮して32ビットに切り上げて計算した。
【００７１】
●2パスラベリング法に必要なメモリ量
近傍画素の調査用に1ライン遅延するためのラインバッファとして1920×1×19ビット≒35.6Kビット。さらに、一次ラベルの接続情報用に1920×1080/4×19ビット≒9.39Mビット（式(3)参照）。
【００７２】
●実施例のブロックラベル付与処理に必要なメモリ量
ラインバッファとして16×1×7ビット=112ビット。なお、近傍画素の調査に1ライン遅延するが遅延量はブロックサイズでよく、ブロック画像中に出現するラベルの最大数は式(4)によりLmax=16×16/4=64、Lmaxを表現するために必要なビット長は式(5)によりL=7ビットである。
【００７３】
さらに、ブロックラベル情報用に16×16/4×(7+4)=704ビット。なお、メモリ803に格納され、ブロック処理部802が参照するデータ量である。Lmax=16×16/4=64、L=7ビット、さらに外接情報のためのラベルごとの4ビットの総和である。
【００７４】
なお、上記のメモリ量は、ブロックラベル付与処理のために画像を二回参照する際、RAM106から画像を読み込むことを想定する。しかし、RAM106から読み込んだブロック画像のデータをメモリ803に保持してもよい。その場合、メモリ803に、さらに16×16×7ビット=1.75Kビット程度のメモリ量が必要になるが、RAM106と画像処理部109の間のデータ転送量を削減することができる。
【００７５】
●ブロックラベル付与処理
ブロック処理部802は、基本的に2パスラベリング法を用いてブロックラベル付与処理を行うが、本実施例においては、さらに外接情報の処理が加わる。以下の説明では、主に2パスラベリング法と異なる部分を説明し、2パスラベリング法と同じ部分は説明を省略する場合がある。
【００７６】
図6により注目画素と近傍画素の関係例（連結条件判定ウィンドウの一例）を示す。非特許文献1によれば、図6における注目画素Pと近傍画素X、Y、Z、Uの関係から次の処理手順により一次ラベルを付与する。
LRAM(・) = 0；
LC = 初期値；
while (注目画素Pが存在) {
V = max(LX, LU)；
Z* = LRAM(LZ)；
if (P = 0)
LZ = Z*；                          …(9a)
else {
if (Y ≠ 0) {
LP = LY；
LZ = Z*；                      …(9b)
} else {
if (Z = 0 and V= 0) {
LP = LC；
LZ = 0；
LRAM(LC) = LC；
LC++；                                …(9c)
}
if (Z = 0 and V ≠ 0) {
LP = V；
LZ = 0；                    …(9d)
}
if (Z ≠ 0 and V ≠ 0 and Z* ＞ V) {
LP = V；
LRAM(Z*) = V；
LZ = V；                    …(9e)
}
if (Z ≠ 0 and V ≠ 0 and Z* ＜ V) {
LP = Z*；
LRAM(V) = Z*；
LZ = Z*；                    …(9f)
}
if (Z ≠ 0 and V ≠ 0 and Z* = V) {
LP = V；
LZ = Z*；                    …(9g)
}
if (Z ≠ 0 and V = 0) {
LP = Z*；
LZ = Z*；                    …(9h)
}
}
}
}                                                        …(9)
ここで、LRAM(・)はラベル間の結合情報を示すテーブル（一次元配列）、
LCはラベルの識別子、
値1はオン画素、値0はオフ画素を表す、
max()は大きい値をとる関数、
Lxは画素xに付与されたラベルの識別子。
【００７７】
以下では、ラベルの識別子に、数字やアルファベットのような一連の記号を割り当てる例を説明するため、ラベルの識別子を「ラベル番号」と呼ぶことにする。
【００７８】
図7により処理対象の二値画像のブロック画像例とブロックラベル付与処理の結果例を示す。図7において黒画素はオン画素（値1）、白画素はオフ画素（値0）を表し、オン画素中の数字は当該画素に付与された一次ラベルを表す。実施例のブロックラベル付与処理は、2パスラベリング法と同様に、ブロック画像の左上の画素からラスタ順に処理を行う。なお、処理に先立ち、一次ラベルの接続関係を表すテーブルLRAM(・)と、外接情報を表すテーブルはすべてゼロに初期化する。
【００７９】
図8により一次ラベルの接続関係を示す接続関係テーブルと接続情報テーブルの一例を示す。図8においてインデックスはラベル番号に対応する。また、図9により接続関係テーブルと接続情報テーブルの変遷の一例を示す。
【００８０】
図7に示すブロック画像をラスタ順に走査した場合、最初に出現する値1の注目画素Pは画素1001である。値1の注目画素1001の隣接画素X、Y、Z、Uはすべて値0であるから、上記処理手順の(9c)において、LCの初期値（例えばラベル1）が画素1001に付与される。
【００８１】
画素1001に対するラベルの付与に応じて、接続関係テーブルと接続情報テーブルは図9(a)に示すように更新される。つまり、ラベル1に対応する接続関係として「1」が記録され、画素1001がブロック画像の上端に位置するからラベル1に対応する上端ビットに‘1’がセットされる。なお、以下では、図8、9に示す接続情報テーブルの左から右に上端ビット、右端ビット、下端ビット、左端ビットが並ぶとして説明を行うが、この並びは任意である。
【００８２】
以下、図7に示す全画素について説明を行うことは冗長であるから、処理のポイントである画素1002-1012が注目画素Pの場合の処理を説明する。
【００８３】
画素1002、1003、1004、1005には、上記処理手順の(9c)において、それぞれラベル2、3、4、5が付与される。その際、接続関係テーブルは図9(b)、図9(c)、図9(d)、図9(e)に示すように更新される。なお、これら画素1002-1005はブロック画像の端部に位置しないので接続情報テーブルは更新されない。
【００８４】
画素1006が注目画素Pになると、左上画素にはラベル2が付与され、右上画素にはラベル1が付与されている。この場合、V=2、Z*=1、Y=0、Z≠0、Z*＜Vだから処理手順501の(9f)において、画素1006にラベル1が付与される。さらに、図9(f)に示すように、接続情報テーブルのLRAM(V=2)に対応する接続情報の値がZ*の値1に更新される。つまり、ラベル2の合流先としてラベル1が設定される。
【００８５】
次に、画素1007が注目画素Pになると、この場合も二つのラベルが合流する。なお、図7には、画素1007の左上画素にラベル4が付与され、右上画素にラベル1が付与された状態を示しているが、これはブロックラベル付与処理の結果を表し、画素1007の処理時点では、画素1007の右上画素にはラベル2が設定されている。言い換えれば、画素1007の右上画素は、画素1006の処理前に処理されるため、さらにその右上の画素に付与されたラベル2を引き継いだ状態になっている。
【００８６】
つまり、画素1007が注目画素Pになると、左上画素にはラベル4が付与され、右上画素にはラベル2が付与されている。この場合、V=4、Z*=1、Y=0、Z≠0、Z*＜Vだから上記処理手順の(9f)において、画素1006にラベル1が付与される。さらに、図9(g)に示すように、接続関係テーブルのLRAM(V=4)に対応する接続情報の値がZ*の値1に更新される。つまり、ラベル4の合流先としてラベル1が設定される。なお、画素1007が注目画素Pになった場合のZ*の値は、この場合、LZ=2、LRAM(LZ=2)から「1」になる。
【００８７】
画素1008が注目画素Pになると、隣接画素X、Y、Z、Uはすべて値0であるから、上記処理手順の(9c)において、LCの値（この場合はラベル6）が画素1008に付与される。さらに、画素1008はブロック画像の右端に位置するから、図9(h)に示すように、ラベル6に対応する接続情報テーブルの右端ビットに‘1’が設定される。
【００８８】
画素1009が注目画素Pになると、V=0、Z*=6、Y=0、Z≠0、Z*＞Vだから上記処理手順の(9h)において、画素1009にラベル6が付与される。ただし、画素1009のラベルは、画素1012の処理によってラベル1に更新され、図7は更新後の状態を示している。また、図9(i)に示すように、画素1009の処理により接続情報テーブルは更新されず、図9(h)と同じ状態である。
【００８９】
画素1010が注目画素Pになると、V=5、Z*=0、Y=0、Z=0、Z*＜Vだから上記処理手順の(9d)において、画素1010にラベル5が付与される。さらに、画素1010はブロック画像の下端に位置するから、図9(j)に示すように、ラベル5に対応する下端ビットに‘1’が設定される
【００９０】
画素1011が注目画素Pになると、V=1、Z*=0、Y=0、Z=0、Z*＜Vだから上記処理手順の(9d)において、画素1011にラベル1が付与される。さらに、画素1011はブロック画像の下端に位置するから、図9(k)に示すように、ラベル1に対応する下端ビットに‘1’が設定される
【００９１】
画素1012が注目画素Pになると、画素1012の右上画素1009にはラベル6が付与され、画素1012の左側画素にはラベル1が付与されている。この場合、V=1、Z*=6、Y=0、Z≠0、Z*＞Vだから上記処理手順の(9e)において、画素1012にラベル1が付与される。さらに、図9(l)に示すように、接続関係テーブルのLRAM(Z*=6)に対応する接続情報の値がVの値1に更新される。つまり、ラベル6の合流先としてラベル1が設定される。
【００９２】
こうして作成された一次ラベルの接続関係テーブルは、インデックス値がiである場合に「ラベルiはラベルjと同じラベルである（連結している）」旨を表し、i≧jの関係がなり立つ。従って、接続関係テーブルを参照して昇順にラベル番号の再割当を行うことができる。
【００９３】
●接続情報と外接情報の統合
外接情報テーブルの統合は、連結するラベルの上右下左端ビットのビット論理和（ビットOR）を取ることで実現される。図10のフローチャートにより接続情報と外接情報の統合を説明する。なお、図10に示す処理はブロック処理部802によって実行される。
【００９４】
図10において、Label[]は、接続関係テーブルに対応する配列であり、上記LRAM(・)に相当する。Connect[]は、外接情報テーブルに対応する配列であり、Connect[i]は図8、図9に示す4ビットの情報に対応する。例えば、図9(l)の外接情報テーブルのラベル1に対応するビット情報はConnect[1]=‘1010’に相当する。また、maxLabelは、一次ラベルの作成において出現したラベルの最大数である。例えば、図9(l)の場合、maxLabel=6である。
【００９５】
ブロック処理部802は、ループカウンタを初期化（i=1）し(S1201)、カウント値iとmaxLabelの値を比較して(S1202)、カウント値iがmaxLabelを超える（i＞maxLabel）と処理を終了する。また、カウント値iがmaxLabel以下（i≦maxLabl）の場合は処理を継続する。
【００９６】
処理を継続する場合、ブロック処理部802は、Label[i]を変数jに代入し(S1203)、カウント値iと変数jの値が同値（i=j）か否かを判定する(S1204)。同値（i=j）の場合、ラベルiが生成された際の初期の値を接続情報が示しているので、カウント値iをインクリメントして(S1207)、処理をステップS1202に戻す。
【００９７】
一方、カウント値iと変数jの値が異なる（i＞j）場合はラベルiが他のラベルjに連結することを意味し、ブロック処理部802は、Label[i]にLabel[j]の値を代入する(S1205)。図9(l)のタイミングでは、ラベルjが連結するラベルは、さらに他のラベルに連結する可能性があるが、図10に示す処理はラベル1から昇順に実行されるので、ラベル1からラベルjに対するラベルの連結は完了している。従って、ステップS1205においては、単純に、ラベルiをラベルjまたはラベルjが連結するラベルに連結すればよい。
【００９８】
次に、ブロック処理部802は、ラベルLabel[i]に対応するConnect[Label[i]]を更新し(S1206)、カウント値iをインクリメントして(S1207)、処理をステップS1202に戻す。
【００９９】
ステップS1206において、ビット論理和により、ラベルiの連結先のラベルに対応するConnect[]に、ラベルiに対応するConnect[]が統合される。この処理により、図10に示す処理が終了した後、m=Label[m]であるラベルmのConnect[m]に、ラベルmが付与（または連結）された画素の外接情報が集約される。
【０１００】
図11により処理後の接続関係テーブルと接続情報テーブルの一例を示す。図10に示す統合処理により、図11(a)に示すラベル1の上右下左端ビットは、ラベル1、2、4、6の上右下左端ビットがビット論理和された値になる。
【０１０１】
●確定ラベルと未確定ラベルの区分
図12のフローチャートによりラベルを確定ラベルと未確定ラベルに区分する処理を説明する。なお、図12に示す処理はブロック処理部802によって実行される。
【０１０２】
ブロック処理部802は、変数L_label=1、変数G_label=Nに初期化し(S1301)、ループカウンタを初期化（k=1）する(S1302)。変数L_labelは未確定ラベルを更新するための変数であり、変数G_labelは確定ラベルを更新するための変数である。また、Nは画像ブロックのラベルの最大数であり、本実施例においてN=64である。
【０１０３】
次に、ブロック処理部802は、カウント値kとmaxLabelの値を比較する(S1303)。ここで、maxLabelは、図10の処理と同様に、一次ラベルの作成において出現したラベルの最大数である。例えば、図9(l)の場合、maxLabel=6である。そして、カウント値kがmaxLabelを超える（k＞maxLabel）の場合は処理を終了し、カウント値kがmaxLabel以下（k≦maxLabl）の場合は処理を継続する。
【０１０４】
処理を継続する場合、ブロック処理部802は、カウント値kとLabel[k]の値が同値（k=Label[k]）か否かを判定する(S1304)。図10に示す統合処理の結果、最終的に連結すべきラベルの接続情報はk=Lable[k]を満たす。言い換えれば、ステップS1304の判定は、ラベルkが集約されたラベルか否かの判定であり、集約されたラベル（S1304の判定が真）であれば処理をステップS1305に進め、集約されたラベルではない場合は処理をステップS1310に進める。
【０１０５】
ラベルkが集約されたラベルの場合、ブロック処理部802は、Connect[k]の値が0か否かを判定する(S1305)。Connect[k]=0の場合、ラベルkおよびラベルkに連結するラベルが付与された画素はブロック画像の外周部に存在せず、ラベルkは確定ラベルである。他方、Connect[k]≠0の場合、ラベルkまたはラベルkに連結するラベルが付与された画素はブロック画像の外周部に位置し、ラベルkは未確定ラベルである。確定ラベル（Connect[k]=0）の場合、処理はステップS1306に進む。また、未確定ラベル（Connect[k]≠0）の場合、処理はステップS1308に進む。
【０１０６】
ラベルkが確定ラベルの場合、ブロック処理部802は、ラベルkに特殊なラベル番号を付与する。本実施例においては、画像ブロックで発生する可能性がある最大のラベル番号から降順にラベル番号を割り当てる。つまり、Label[k]=G_labelとし(S1306)、変数G_labelをデクリメントして(S1307)、確定ラベルにNから降順にラベル番号を割り当てる。この後、カウント値kをインクリメントし(S1311)、処理をステップS1303に戻す。
【０１０７】
一方、ラベルkが未確定ラベルの場合、ブロック処理部802は、ラベルkに1から昇順にラベル番号を付与する。これは、これまでの処理により離散状態にあるラベル番号を連番にするための処理である。つまり、Label[k]=L_label変数とし(S1308)、変数L_labelをインクリメントして(S1309)、未確定ラベルに1から昇順にラベル番号を割り当てる。この後、カウント値kをインクリメントし(S1311)、処理をステップS1303に戻す。
【０１０８】
また、ラベルkが集約されたラベルではない場合、ラベルkは他のラベルLabel[k]に連結されている。Label[k]＜kであり、ステップS1306またはS1308の処理により、連結先のラベルのラベル番号が更新されている可能性がある。そこで、ブロック処理部802は、Label[k]=Label[Label[k]]としてラベルkの値を更新し(S1310)、その後、カウント値kをインクリメントし(S1311)、処理をステップS1303に戻す。
【０１０９】
図12に示す区分処理により、図11(b)に示すように、未確定ラベルのラベル番号が整理され、確定ラベルにはNから降順にラベル番号が降順に付与される。
【０１１０】
図13によりブロックラベル付与処理の結果例を示す。図13は、図7に示す一次ラベルの付与結果を読み込み、図10と図11に示す処理によって接続情報テーブルを処理した結果を示す。このブロックラベル付与処理の結果はRAM106に格納されるが、その際、下記の二つの処理を行う。
【０１１１】
第一の処理は、未確定ラベルの情報をRAM106に格納する処理である。未確定ラベルの情報は後のブロック統合処理で参照すべき情報、つまり、図2に示すブロックラベル情報である。ブロックラベル情報として必要な情報は、画像ブロック中の未確定ラベルを後に特定するための情報、および、各未確定ラベルに対する外接情報である。未確定ラベルのラベル番号は連番に整理されているから未確定ラベルの最大番号と、未確定ラベルの外接情報である。つまり、ブロック処理部802は、図13の例においては「2」と、ラベル1、2に対する外接情報（図11(b)のConnect[1]、Connect[5]）をRAM106に格納する。
【０１１２】
第二の処理は、確定ラベルのラベル番号を再割り当てする処理である。ブロックラベル付与処理において、画像ブロックで発生する可能性がある最大のラベル番号から降順にラベル番号を確定ラベルに割り当てた。しかし、当該ラベル番号が一意であるのは画像ブロック内だけであり、RAM106に格納する前に、入力画像全体で一意なラベル（以下、最終確定ラベル）を割り当てる。
【０１１３】
第二の処理は、ブロック処理部802により、最終確定ラベルを管理し、確定ラベルに最終確定ラベルを割り当てる。あるいは、CPU104が最終確定ラベルを管理し、制御部801からCPU104に最終確定ラベルの割り当てを要求し、返信されたラベルを確定ラベルに割り当てればよい。最終確定ラベルは、未確定ラベルとの識別が容易であればよく、例えば、画像全体で発生する可能性がある最大のラベル番号から降順に最終確定ラベルとして割り当てればよい。こうすれば、画像処理部109を複数設ける構成の場合も、矛盾することなく、一意の最終確定ラベルを割り当てることができる。
【０１１４】
従って、ブロック処理部802はメモリ803に格納されたブロックラベル付与処理の結果（例えば図13）の確定ラベルを最終確定ラベルに変換し、制御部801は変換結果をRAM106に転送する。さらに、この例において、メモリ803は6ビット/画素で情報を格納する一方、RAM106は例えば32ビット/画素で情報を格納するので、ブロック処理部802または制御部801はビット長の変換を行う。また、ブロック処理部802は、制御部801の制御に従い、上記の変換処理を行いつつ、変換結果を制御部801を介してRAM106に出力する。あるいは、制御部801が変換処理を行ってもよい。
【０１１５】
以上のブロックラベル付与処理を、RAM106に格納された各画像ブロックに施すことで、図3に示す、各画像ブロックのブロックラベル付与結果が得られる。
【０１１６】
●ブロックラベル統合処理
続いて、統合処理部804により、ブロックラベル画像を統合するブロックラベル統合処理が行われる。
【０１１７】
図14により統合処理するブロックラベル画像の一例を示す。図14は、ブロックラベル画像1601と、その下端に接続するブロックラベル画像1602を統合する例を示す。ブロックラベル画像1601と1602には、同じ番号（1、2）のラベルが割り当てられているが、統合前、異なる画像ブロックの同一番号のラベルの間に関連性はなく、たまたま同番号のラベルが割り当てられているだけに過ぎない。また、ブロックラベル画像1601におけるラベルA、および、ブロックラベル画像1602におけるラベルBは最終確定ラベルである。
【０１１８】
図15により統合処理するブロックラベル画像の接続関係テーブルおよび外接情報テーブルを示す。図15(a)はブロックラベル画像1601の接続関係テーブルおよび外接情報テーブルを示し、図15(b)はブロックラベル画像1602の接続関係テーブルおよび外接情報テーブルを示す。
【０１１９】
なお、図15(a)(b)にはテーブル形式の情報を示すが、これらの情報はテーブル形式でメモリ上に存在する必要はなく、これらの情報を復元可能な形でRAM106に格納されていればよい。
【０１２０】
先と同様に、接続関係テーブルの情報をLabel[]で表し、外接情報テーブルの情報をConnect[]で表す。さらに、図15(a)に関する情報をLabel0[]とConnect0[]、図15(b)に関する情報をLabel1[]とConnect1[]で表すことにする。
【０１２１】
統合処理部804は、下記の処理により図15(c)に示すテーブルを作成する。
Label[X] = X；    ただし、1≦X≦6
if (1≦X≦2)
Connect[X] = Connect0[X] ＆ 0xD；
if (3≦X≦6)
Connect[X] = Connect1[X-2] ＆ 0x7；      …(10)
ここで、＆はビット論理積（ビットAND）。
【０１２２】
処理(10)をブロックラベル画像PとQの統合に一般化すると、以下のようになる。
Label[X] = X；  ただし、1≦X≦(LmaxP + LmaxQ)
if (1≦X≦LmaxP)
Connect[X] = ConnectP[X] ＆ Mask(Pの接続端)；
if (LmaxP+1≦X≦LmaxP+LmaxQ）
Connect[X] = (ConnectQ[X-LmaxP] ＆ Mask(Qの接続端)    …(11)
ここで、LabelP[]はPの統合前の接続関係テーブル、
ConnectPはPの統合前の外接情報テーブル、
LmaxPはPの統合前のラベルの最大数、
LabelQ[]はQの統合前の接続関係テーブル、
ConnectQ[]はQの統合前の外接情報テーブル、
LmaxQはQの統合前のラベルの最大数。
【０１２３】
また、マスクMask(C)は、次式の演算によって求める。
Mask(C) = {0x7×f(C, "上端を含む")}
＆ {0xB×f(C, "右端を含む")}
＆ {0xD×f(C, "下端を含む")}
＆ {0xE×f(C, "左端を含む")}；      …(12)
ここで、関数f(C, W)はCが条件Wを満たす場合は‘1’、満たさない場合は‘0’。
【０１２４】
マスクの具体例を説明すると、統合処理によりブロックラベル画像の上端を他のブロックラベル画像と接続する場合、最上位ビットを‘0’にするマスク(0x7)を与える。同様に、右端を接続する場合、上から2ビット目を‘0’にするマスク(0xB)を与える。下端を接続する場合、上から3ビット目を‘0’にするマスク(0xD)を与える。左端を接続する場合、最下位ビットを‘0’にするマスク(0xE)を与える。なお、このマスクの具体例は外接情報テーブルのビット列が上位から順に上端、右端、下端、左端に対応する場合の例であり、ビット列の並びと上下左右端の関係に合わせてマスクを与える。
【０１２５】
次に、統合処理部804は、ブロックラベル画像1601と1602の接続部のラベルの状態を調べ、図15(c)に示すテーブルを更新する。そのために、統合処理部804は、ブロックラベル画像1601の下端の1ライン1611と、ブロックラベル画像1602の上端の1ライン1612をRAM106から読み出す。そして、読み出したラインに対して、ブロックラベル付与処理における一次ラベルの付与処理と同様のラベル更新処理を行う。
【０１２６】
図16によりラベル更新処理を説明する。図16(a)は図14に示すブロックラベル画像1601と1602の2ライン（2×16画素）分のライン画像1611、1612を示す。ライン画像1611、1612に対して、図16(b)に示すように図6と同様の参照画素を適用し、上記処理手順(9)による一次ラベルの付与処理を実行して、図15(c)に示すテーブルを更新する。その際、下記のアルゴリズムに従い、画素に付与されたラベル番号を参照して図15(c)に示すテーブルにアクセスする。
if (Xがライン画像1611のラベル) {
Label'[X] = Label[X]；
Connect'[X] = Connect[X]；
}
if (Xがライン画像1612のラベル) {
Label'[X] = Label[X+2]；
Connect'[X] = Connect[X+2]；
}                                  …(13)
【０１２７】
アルゴリズム(13)をブロックラベル画像PとQを統合する場合に一般化すると、以下のようになる。
if (XがPのラベル) {
Label'[X] = Label[X]；
Connect'[X] = Connect[X]；
}
if (XがQのラベル) {
Label'[X] = Label[X＋LmaxP]；
Connect'[X] = Connect[X+LmaxP]；
}                                  …(14)
【０１２８】
図15(c)のテーブルに対する更新処理において、先述した一次ラベルの付与処理と同様に、ラベル番号の再割り当てと外接情報の統合が行われるが、これは一次ラベルの付与処理と同様の処理であり、説明を省略する。図15(d)は図15(c)のテーブルの更新結果を示す。図15(d)に示すテーブルには番号128のラベルがあるが、これは最終確定ラベルを割り当てるべきラベルである。
【０１２９】
次に、統合処理部804は、図15(d)のテーブルを用いて、ブロックラベル画像1601、1602の更新処理を行う。つまり、ブロックラベル画像1601、1602をRAM106から読み込み、図15(d)のテーブルに従いブロックラベル画像1601、1602を書き換えてRAM106に書き込む。その際、図15(c)のテーブルの更新処理と同様に、Label'[]およびConnect'[]を用いて図15(d)のテーブルを参照し、更新処理を実行する。
【０１３０】
図17によりブロックラベル統合処理後のブロックラベル画像の一例を示す。図17におけるラベルCは、統合処理で新たに割り当てられた最終確定ラベルを表す。統合処理により更新されたブロックラベル画像はRAM106に格納されるが、その際、統合したブロックラベル画像に対するブロックラベル情報が生成される。このブロックラベル情報も所定の書式に従いRAM106に格納される。
【０１３１】
上記では、垂直方向に隣接する二つのブロックラベル画像を統合する例を説明した。水平方向に隣接する二つのブロックラベル画像を統合する場合は、それらブロックラベル画像から2コラム分の画像を取得して、図16(c)に示すようにジグザクに参照画素を適用し、上記の処理を実行すればよい。あるいは、上記処理手順(9)において、行と列を入れ替えて処理を行うことでも可能である。
【０１３２】
そして、ブロック統合処理の結果を新たなブロックラベル画像として、再帰的にブロック統合処理を繰り返し、すべてのブロックラベル画像を統合して最終的に画像全体のラベリング結果を得る。その際、入力画像の端部に位置するブロック画像については、ブロック端が画像全体の端部（上端、下端、左端、右端）の何れに相当するかを調べ、外接情報テーブルの画像全体の端部に対応するビットを‘0’にする。この処置により、上述した処理により、正しいラベリング処理が可能になる。
【０１３３】
すべてブロック画像のブロックラベル付与処理が終了するのを待ってブロックラベル統合処理を行う必要はない。つまり、ブロックラベル統合処理に必要なブロックラベル画像が生成された時点でブロックラベル統合処理を開始すればよい。この場合、先に処理されたブロック画像に対する統合処理と、次に処理するブロック画像に対するブロックラベル付与処理はパイプライン的に動作する。
【０１３４】
このように、ラベリング処理を画像ブロック単位に行うことで、処理に必要なメモリ、とくに作業用のメモリのメモリ量を大幅に削減することができる。従って、実施例のラベリング法を用いるハードウェアの回路規模を大幅に削減することができる。
【０１３５】
また、実施例のラベリング法によれば、最終確定ラベルの割り当て処理以外は並列処理が可能であり、最終確定ラベルの割り当て処理のみ排他的に処理を行うように構成すれば、複数の画像処理部109によりラベリング処理の高速化を図ることができる。この並列性によれば、GPU (graphics processing unit)上で動作するソフトウェアによってラベリング処理を実現する場合の高速化が期待される。
【０１３６】
また、実施例のラベリング法をパーソナルコンピュータ上で動作するソフトウェアで実現する場合、同時に参照すべきデータを少なくして（データアクセスの局所化）、キャッシュなどと組み合わせることで、ラベリング処理を高速化することができる。つまり、ブロックラベル画像の統合処理において、不要なデータ転送を省くことができ、RAM106との間のデータ転送量が削減可能である。
【０１３７】
［変形例］
上記では、一度に二つのブロックラベル画像を統合する例を示したが、統合後のブロックの形状が凸型の矩形であれば、四つのブロックラベル画像を同時に統合する拡張も容易である。
【０１３８】
ブロックラベル画像の統合順序にはとくに制限がないが、例えば、画像の主走査方向に並んだブロックラベル画像を優先して統合してもよいし、逆に、副走査方向に並んだブロックラベル画像を優先して統合してもよい。あるいは、主走査方向に並んだブロックラベル画像と、副走査方向に並んだブロックラベル画像を略同数選択して、空間的に近いブロックラベル画像をブロック状に統合してもよい。
【０１３９】
上記では、すべての画像ブロックについて処理を行うとした。しかし、画像ブロックの内容によっては未確定ラベルが一つも発生しない場合がある。ブロックラベル統合処理において、未確定ラベルをもたないブロックラベル画像はラベルを再割り当てする処理を省略することができる。ブロックラベル画像における未確定ラベルの有無は、対応するブロックラベル情報から容易に判定することが可能である。従って、未確定ラベルをもたないブロックラベル画像は、ブロックラベル統合処理の後、ラベルの再割り当て処理（および、そのためのブロック画像の読み込み）を省略することができる。
【０１４０】
また、画像中の特定領域を中心に、当該領域を拡大するようにブロックラベル画像を統合するとともに、画像全体を処理する前に処理を打ち切ることもできる。このような統合処理によば、画面全体を統合する場合と結果が異なることもあるが、例えば要求処理速度が非常に高く全画像を処理し切れない場合（動画像の各フレームをラベリング処理する場合など）に有効である。
【０１４１】
処理の打切りは、処理時間を計測して所定時間が経過した時点で打ち切る、あるいは、所定数のブロックを統合した時点で打ち切るなどが考えられる。画像中の特定領域としては、例えば、所定領域（画像中央など）、ユーザ指定領域、顔検出処理などの検出領域、画像データの書誌情報（EXIFのSubjectAreaタグ情報やJPEG2000のROIなど）が定める領域、などが考えられる。
【０１４２】
また、実施例のラベリング法をハードウェアで実現する場合、処理の打ち切りにより消費電力を削減することができる。例えば、バッテリ駆動のハードウェアの場合、バッテリ残量などに応じて、画像全体を統合するモードと、処理を打ち切るモードを切り替えることもできる。
【０１４３】
上記では、入力画像として二値画像の例を説明したが、実施例のラベリング法を多値画像に拡張することは容易である。つまり、二値画像の場合は、オン画素の注目画素に隣接する画素がオン画素の場合に注目画素と同一の一次ラベルを付与する。多値画像の場合は、注目画素の信号値と隣接画素の信号値の間の差分を求め、差分の絶対値が所定の閾値未満の場合に注目画素と同一の一次ラベルを付与すればよい。
【０１４４】
さらに、ブロックラベル統合処理においては、端部のライン画像（図16に示す画像1611、1612）に加え、それらに対応する入力画像の信号値を入力し、信号値を参照してラベルを統合するか否かを判定する。判定には、一次ラベルの付与と同様に、信号値の差分に関する閾値を用いる。なお、閾値には所定値を用いればよいが、注目画素の近傍画素や画像ブロック内の他の画素の信号値から統計的かつ動的に閾値を決定してもよい。
【０１４５】
実施例のラベリング法は、1チャネルの多値画像ではなく、例えばRGB画像など多チャネルの多値画像に拡張することも可能である。この場合、各チャネルの信号値を要素とする多次元（RGBの場合は三次元）座標系を規定し、画素の信号値に対応する座標間の距離と所定の閾値を比較する。他チャネルの画像には、RGB画像だけでなく、例えばYCC色空間の画像やCIELab色空間の画像も含まれる。
【０１４６】
このように、2パスラベリング法に基づくラベリング処理を画像ブロック単位に行うことができ、ラベリング処理中に必要になる中間メモリのメモリ量を大幅に削減することができる。また、画像ブロック単位の処理の大部分は、他の画像ブロックの処理から独立し、処理の並列化を容易に実現することができる。
【実施例２】
【０１４７】
以下、本発明にかかる実施例2の画像処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【０１４８】
実施例1においては、図5に示すように、一組の回路構成を有する画像処理部109によってラベリング処理を行う例を説明した。実施例2では、複数の回路構成を有する画像処理部109によってラベリング処理を行う例を説明する。
【０１４９】
図18のブロック図により実施例2の画像処理部109の構成例を説明する。実施例2の画像処理部109は、制御部801、三つのブロック処理部802a、802bおよび802c、二つの統合処理部804aおよび804b、並びに、他の処理を行う処理部805を有し、これら処理部はメモリ803を共有する。制御部801は、ラベリング処理の進み具合に応じて、処理部によるメモリ803の使用を制御して、メモリ803の使用効率を上げる。実施例2において、ブロック処理部802と統合処理部804がそれぞれ複数あれば、ブロック処理部802、統合処理部804、処理部805の数は任意である。
【０１５０】
また、画像処理部109の動作と、ラベリング処理に使用可能なメモリ803の領域に応じて、ブロック処理部802、統合処理部804、処理部805の動作設定を変更することができる。例えば、ブロック処理部802のブロックラベル付与処理における画像ブロックサイズを大きくするほどメモリ803のメモリ使用量が増加するが、統合処理部804のブロックラベル統合処理におけるブロックラベル画像の読出回数を削減することができる。また、ブロックラベル統合処理において同時に統合する画像ブロックの数を増やせば、例えば図15(a)から図15(d)に示すテーブルに必要なメモリ量が増加するが、ブロックラベル統合処理におけるブロックラベル画像の読出回数を削減することができる。
【０１５１】
さらに、ブロック処理部802、統合処理部804（さらに処理部805）を再構成可能な回路で構成することも考えられる。この場合、例えば、互いに他の処理部を実現可能な構成として、システム側の要求に応じて各部の構成を変更し、ラベリング処理を行う。あるいは、再構成可能な回路ではなく、各処理部をCPUとソフトウェアで構成し、CPUによってラベリング処理を行うことも容易である。
【０１５２】
さらに、ブロック処理部802、統合処理部804、処理部805を個別または複数単位に、クロックまたは電源の供給/遮断を設定可能に構成することもできる。この場合、動作モードなどに応じて、高速動作が不要な場合はブロック処理部202、統合処理部804、処理部805の一部のクロック供給や電力供給を停止し、省電力動作に移行させることができる。
【実施例３】
【０１５３】
以下、本発明にかかる実施例3の画像処理を説明する。なお、実施例3において、実施例1、2と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【０１５４】
実施例3では、上記のラベリング法をCannyエッジ検出処理に適用する例を説明する。典型的なCannyエッジ検出処理は以下の処理から構成される。
【０１５５】
まず、入力画像に平滑化フィルタ処理を施し、平滑化画像を得る。
【０１５６】
次に、平滑化画像にエッジ強度算出処理を施し、エッジ強度画像を得る。エッジ検出処理は任意のものでよいが、例えばSobelフィルタなどを用いる。水平方向、垂直方向ごとにエッジを検出した場合は、例えば、水平方向のエッジ強度と垂直方向のエッジ強度の二乗和を算出し、二乗和（またはその平方根）をその画素位置におけるエッジ強度とする。
【０１５７】
次に、エッジの選別処理を行う。これは、エッジ強度画像の各画素値（つまり元の画像のエッジ強度値）に二つの閾値th0とth1 (0≦th0＜th1)を適用して、下記のアルゴリズムにより、当該画素がエッジ画素か否かを判定する。
if (I(x, y) ＜ th0)
非エッジ画素；
if (I(x,y) ＞ th1)
エッジ画素；
if (t0 ≦ I(x,y) ≦ t1) {
if (エッジ画素に隣接する)
エッジ画素；
else
非エッジ画素；
}                                …(15)
ここで、(x, y)は強度画像の座標、
I(x, y)は座標(x, y)の画素の値。
【０１５８】
画素値がt0 ≦ I(x,y) ≦ t1である画素がエッジ画素か否かの決定処理（以下、エッジ画素確定処理）は、エッジ強度画像の画素値を三値化し、上記のラベリング法を応用することで容易に実現される。なお、三値は、非エッジ画素（I(x, y) ＜ th0）、未確定画素（t0 ≦ I(x,y) ≦ t1）、確定エッジ画素（I(x,y) ＞ th1）である。なお、上記のラベリング法をエッジ画素確定処理に適用する場合、ラベル0を非エッジ画素に付与し、ラベル1を確定エッジ画素に付与することが好ましい。
【０１５９】
まず、エッジ画素確定処理における入力画像として、非エッジ画素に画素値「0」を、確定エッジ画素に画素値「1」、未確定画素に画素値「2」を割り当てた三値画像を作成する。
【０１６０】
次に、三値画像を入力として、上記のラベリング法によるブロックラベル付与処理を実行する。つまり、ブロックラベル付与処理により、確定エッジ画素にラベル1を割り当て、未確定画素に新規ラベルを付与する場合はラベル番号が2以上のラベルを割り当てる。
【０１６１】
確定ラベルが出現した場合、ラベル番号が「1」であればそのままとし、そうでない場合は最終確定ラベルとして「0」を割り当てる。上記の処理手順(9)によれば、複数のラベルが合流した場合、よりラベル番号が小さいラベルが残留する（例えば、上記の処理手順(9e)(9f)）。従って、確定ラベルが出現し、かつ、そのラベル番号が確定エッジ画素を意味するラベル番号「1」よりも大きい場合、それは確定エッジ画素に隣接しない未確定画素である。そのような確定ラベルが付与された画素は、アルゴリズム(15)に従い、非エッジ画素とすればよい。
【０１６２】
未確定ラベルについては、他のブロックとの接続状況に依存するので、実施例1と同様に、ブロックラベル情報としてRAM106に保存する。
【０１６３】
また、ブロックラベル統合処理において、ブロックラベル付与処理と同様、確定ラベルが出現した場合は、ラベル番号が「1」であればそのままとし、そうでない場合は最終確定ラベルとして「0」を割り当てる。このようにして、ブロックラベル画像を統合すると、最終的に、非エッジ画素に対応するラベル番号「0」、または、確定エッジ画素に対応するラベル番号「1」が付与されたラベル画像が得られ、Cannyエッジ検出処理が実現される。
【０１６４】
このように、上記のラベリング法を応用することで、Cannyエッジ検出処理の一部（エッジ画素確定処理）を実現することができ、Cannyエッジ検出処理におけるエッジ画素確定処理をブロック単位に実行することが可能になる。Cannyエッジ検出処理における他の処理は容易にブロック処理可能であるから、上記のラベリング法を適用することにより、Cannyエッジ検出処理全体をブロック処理することができる。さらに、エッジ画素確定処理（とくにブロックラベル付与処理の部分）と、その前の処理（平滑化処理、エッジ強度算出処理）をパイプライン状に構成することも容易である。
【０１６５】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【図１】
2014203134.tif 000003
【図２】
2014203134.tif 000004
【図３】
2014203134.tif 000005
【図４】
2014203134.tif 000006
【図５】
2014203134.tif 000007
【図６】
2014203134.tif 000008
【図７】
2014203134.tif 000009
【図８】
2014203134.tif 000010
【図９】
2014203134.tif 000011
【図１０】
2014203134.tif 000012
【図１１】
2014203134.tif 000013
【図１２】
2014203134.tif 000014
【図１３】
2014203134.tif 000015
【図１４】
2014203134.tif 000016
【図１５】
2014203134.tif 000017
【図１６】
2014203134.tif 000018
【図１７】
2014203134.tif 000019
【図１８】
2014203134.tif 000020