(57)【要約】【課題】ラベリング処理を効率的に実行する画像処理装置を実現する。【解決手段】仮ラベルデータ生成部は、入力画像において所定の順番に従って画素に着目して現画素が前記有効画素であり、かつ、直前画素が現画素に隣接する有効画素でない場合には新たに発行した識別子を現画素の仮ラベルとして現画素に割り当てた仮ラベルデータを生成し、現画素が有効画素であり、かつ、直前画素が現画素に隣接する有効画素である場合には直前画素の仮ラベルを現画素の仮ラベルとして現画素に割り当てた仮ラベルデータを生成する。連結情報生成部は、現画素が有効画素である場合には直前画素に該当せず、かつ、現画素に隣接する有効画素の仮ラベルと現画素の仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する。【選択図】図２
2013114278.tif 000002
【特許請求の範囲】
【請求項１】
所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成部と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成部と
を具備する画像処理装置。
【請求項２】
いずれかの前記仮ラベルから当該仮ラベルと前記連結関係にある前記仮ラベルを辿っていくことにより相互に前記連結関係にある前記仮ラベルからなる集合を生成して当該集合の各々を識別するための識別子である本ラベルと前記仮ラベルとを対応付けたラベル変換テーブルを生成するラベル変換テーブル生成部と、
前記仮ラベルデータにおける前記画素に前記所定の順番に従って着目して前記ラベル変換テーブルにおいて前記着目した画素の前記仮ラベルに対応付けられた前記本ラベルを前記仮ラベルの代わりに前記画素に割り当てた本ラベルデータを生成する本ラベルデータ生成部と
をさらに具備する請求項１記載の画像処理装置。
【請求項３】
前記ラベル変換テーブルは、エントリ番号を有する複数のエントリを備え、
前記ラベル変換テーブル生成部は、前記複数のエントリの各々の前記エントリ番号を前記仮ラベルの値として当該仮ラベルに対応する前記本ラベルを前記エントリに記録する
請求項２記載の画像処理装置。
【請求項４】
前記ラベル変換テーブル生成部は、
前記連結情報における前記仮ラベルから当該仮ラベルと前記連結関係にある前記仮ラベルを辿って前記連結関係のある他の前記仮ラベルを辿れなくなった前記仮ラベルを起点仮ラベルとして決定する起点仮ラベル決定部と、
前記決定された起点仮ラベルについて前記本ラベルを発行する本ラベル発行部と、
前記起点仮ラベルの決定において辿った前記仮ラベルからなる前記集合において当該集合内の前記仮ラベルに対して前記起点仮ラベルについて発行された前記本ラベルを対応付けたテーブルを前記ラベル変換テーブルとして生成するラベル対応関係決定部と
を備える請求項２記載の画像処理装置。
【請求項５】
検出対象画像において所定の物体を検出して当該検出された物体の領域内の画素との間において座標が一致する前記有効画素を含む画像を前記入力画像として生成する物体検出部をさらに具備する
請求項１記載の画像処理装置。
【請求項６】
所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成手順と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成手順と
を具備する画像処理装置の制御方法。
【請求項７】
所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成手順と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成手順と
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、画像処理装置および画像処理装置の制御方法ならびに当該方法をコンピュータに実行させるためのプログラムに関する。詳しくは、物体にラベルを付与する画像処理像装置および画像処理装置の制御方法ならびに当該方法をコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
従来、画像処理装置において、画像内の物体を識別するために物体ごとに一意な識別子をラベルとして付与するラベリング処理が実行されることがあった。例えば、動画に含まれる各画像から移動する物体を検出して追跡する処理においてラベリング処理が用いられる。
【０００３】
このラベリング処理においては、まず、画像処理装置は、所定の順番に従って画素に着目（スキャン）し、着目した着目画素が移動体の領域内の画素であるか否かを判別する。このスキャンにおいては、例えば、画像において上から下へ行の各々が順に着目され、行の各々においては左から右の方向へ順に画素が着目される。このように１ラインごとにスキャンを行うスキャニングはラスタスキャンと呼ばれる。そして、画像処理装置は、様々な手法を用いて移動体の領域内の画素に仮ラベルを付与する。
【０００４】
ここで、仮ラベリングの手法として、例えば、着目した着目画素の左隣の画素と真上の画素との仮ラベル値を参照し、小さい方の仮ラベル値を着目画素に付与する手法が提案されている（例えば、特許文献１参照。）。この手法を用いて、例えば、座標が（０，０）、（１，０）、（０，１）、（１，１）の４つの画素を含む画像に仮ラベルを付与する場合を考える。ここで、１行目において（０，０）、（１，０）の順に、２行目において（０，１）、（１，１）の順に画素が着目され、１および２行目において（１，０）、（０，１）、（１，１）の画素のみが有効画素であったものとする。画像処理装置は、着目した順に従って、（１，０）の画素に仮ラベル値１、（０，１）の画素に仮ラベル値２を付与する。（１，１）の画素に対しては、画像処理装置は、真上の（１，０）の仮ラベル値１と左隣の（０，１）の仮ラベル２とのうちの小さい方の仮ラベル値１を付与する。
【０００５】
仮ラベルの付与後において、画像処理装置は、互いの座標間の距離が一定値以内の画素群ごとに、一意な本ラベルを発行し、その画素群の仮ラベルと本ラベルとを対応付けたラベル変換テーブルを作成する。例えば、前述の例においては、仮ラベルが付与された（１，０）、（０，１）、（１，１）の画素は互いに隣接しているため、これらの画素の集合に対して本ラベル値１が発行される。そして、この本ラベル値１に、これらの画素の仮ラベル値１および２が対応付けられる。本ラベル発行後に、画像処理装置は、仮ラベリングの際と同一の順番に従って画素に着目する。そして、画像処理装置は、着目した画素に仮ラベルが付与されていれば、ラベル変換テーブルを参照して、仮ラベルを本ラベルに変換する本ラベリング処理を実行する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平７−１０５３６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述の従来技術では、本ラベリング処理の高速化が困難であった。上述の仮ラベリング処理においては、画像処理装置が着目した画素の真上の画素の仮ラベルを参照するため、着目する順（すなわち、ラスタスキャンの順）と異なる順番に仮ラベルが画素に付与されるおそれがある。この結果、本ラベリング処理において、ラベル変換テーブルが、着目した順と異なる順に不規則に参照されるおそれがあった。例えば、この仮ラベリング手法を使用した場合、前述のように（１，０）、（０，１）、（１，１）の画素にそれぞれ仮ラベル値１、２、１が付与される。この場合、ラスタスキャンの順、すなわち（１，０）、（０，１）、（１，１）の順とは無関係に不規則にラベル変換テーブルが参照されてしまう。有効画素数が多いほど、ラベル変換テーブルが不規則に参照される影響が大きくなり、ラベル変換テーブルへのアクセス効率が低下してしまう。この結果、本ラベリング処理の効率が低下し、ラベリング処理の高速化が困難になるという問題があった。
【０００８】
本技術はこのような状況に鑑みて生み出されたものであり、ラベリング処理を効率的に実行する画像処理装置を実現することを目的とする。
【課題を解決するための手段】
【０００９】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って上記画素に着目して当該着目された画素である現画素が上記有効画素であり、かつ、上記現画素の１つ前に着目された画素である直前画素が上記現画素に隣接する上記有効画素でない場合には新たに発行した識別子を上記現画素の仮ラベルとして上記現画素に割り当てた仮ラベルデータを生成し、上記現画素が上記有効画素であり、かつ、上記直前画素が上記現画素に隣接する上記有効画素である場合には上記直前画素の上記仮ラベルを上記現画素の仮ラベルとして上記現画素に割り当てた上記仮ラベルデータを生成する仮ラベルデータ生成部と、上記現画素が上記有効画素である場合には上記現画素に隣接する上記有効画素の上記仮ラベルと上記現画素の上記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成部とを具備する画像処理装置、および、その制御方法ならびに当該方法をコンピュータに実行させるためのプログラムである。これにより、現画素が有効画素であり、かつ、直前画素が現画素に隣接する有効画素でない場合には新たな仮ラベルが現画素に割り当てられ、現画素が有効画素であり、かつ、直前画素が現画素に隣接する有効画素である場合には直前画素の仮ラベルが現画素に割り当てられるという作用をもたらす。
【００１０】
また、この第１の側面において、いずれかの上記仮ラベルから当該仮ラベルと上記連結関係にある上記仮ラベルを辿っていくことにより相互に上記連結関係にある上記仮ラベルからなる集合を生成して当該集合の各々を識別するための識別子である本ラベルと上記仮ラベルとを対応付けたラベル変換テーブルを生成するラベル変換テーブル生成部と、上記仮ラベルデータにおける上記画素に上記所定の順番に従って着目して上記ラベル変換テーブルにおいて上記着目した画素の上記仮ラベルに対応付けられた上記本ラベルを上記仮ラベルの代わりに上記画素に割り当てた本ラベルデータを生成する本ラベルデータ生成部とをさらに具備してもよい。これにより、本ラベルと仮ラベルとを割り当てたラベル変換テーブルが生成され、そのラベル変換テーブルにおいて仮ラベルに対応する本ラベルが仮ラベルの代わりに割り当てられるという作用をもたらす。
【００１１】
また、この第１の側面において、上記ラベル変換テーブルは、エントリ番号を有する複数のエントリを備え、上記ラベル変換テーブル生成部は、上記複数のエントリの各々の上記エントリ番号を上記仮ラベルの値として当該仮ラベルに対応する上記本ラベルを上記エントリに記録してもよい。これにより、エントリ番号が仮ラベルの値として仮ラベルに対応する本ラベルがエントリに記録されるという作用をもたらす。
【００１２】
また、この第１の側面において、上記ラベル変換テーブル生成部は、上記連結情報における上記仮ラベルから当該仮ラベルと上記連結関係にある上記仮ラベルを辿って上記連結関係のある他の上記仮ラベルを辿れなくなった上記仮ラベルを起点仮ラベルとして決定する起点仮ラベル決定部と、上記決定された起点仮ラベルについて上記本ラベルを発行する本ラベル発行部と、上記起点仮ラベルの決定において辿った上記仮ラベルからなる上記集合において当該集合内の上記仮ラベルに対して上記起点仮ラベルについて発行された上記本ラベルを対応付けたテーブルを上記ラベル変換テーブルとして生成するラベル対応関係決定部とを備えてもよい。これにより、起点仮ラベルが決定され、その起点仮ラベルについて本ラベルが発行され、集合内の仮ラベルに対して起点仮ラベルについて発行された本ラベルが対応付けられるという作用をもたらす。
【００１３】
また、この第１の側面において、検出対象画像において所定の物体を検出して当該検出された物体の領域内の画素との間において座標が一致する上記有効画素を含む画像を上記入力画像として生成する物体検出部をさらに具備してもよい。これにより、検出対象画像において検出された物体の領域内の画素との間において座標が一致する有効画素を含む画像が入力画像として生成されるという作用をもたらす。
【発明の効果】
【００１４】
本技術によれば、画像処理装置がラベリング処理を効率的に実行することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１５】
【図１】実施の形態における画像処理装置の一構成例を示すブロック図である。
【図２】実施の形態におけるラベル付与部の一構成例を示すブロック図である。
【図３】実施の形態における仮ラベルデータ生成部の動作の一例を示す表である。
【図４】実施の形態における連結情報テーブル生成部の動作の一例を示す表である。
【図５】実施の形態における２値画像の一例を示す図である。
【図６】実施の形態における仮ラベルデータの一例を示す図である。
【図７】（ａ）実施の形態における連結情報テーブルの一例である。（ｂ）実施の形態におけるラベル変換テーブルの一例である。
【図８】実施の形態における本ラベルデータの一例を示す図である。
【図９】実施の形態における画像処理装置の動作の一例を示すフローチャートである。
【図１０】実施の形態における仮ラベルデータ生成処理の一例を示すフローチャートである。
【図１１】実施の形態における連結情報テーブルエントリ追加処理の一例を示すフローチャートである。
【図１２】実施の形態におけるラベル変換テーブル生成処理の一例を示すフローチャートである。
【図１３】実施の形態における起点仮ラベル決定処理の一例を示すフローチャートである。
【図１４】実施の形態における本ラベル発行処理の一例を示すフローチャートである。
【図１５】実施の形態におけるラベル対応関係決定処理の一例を示すフローチャートである。
【図１６】実施の形態における本ラベルデータ生成処理の一例を示すフローチャートである。
【図１７】実施の形態における起点仮ラベルを探索中のラベル変換テーブルの一例である。
【図１８】実施の形態における起点本ラベル配列の一例を示す図である。
【図１９】実施の形態における本ラベルを付与中のラベル変換テーブルの一例である。
【図２０】実施の形態における１行目のラベルの変換処理を説明するための図である。
【図２１】実施の形態における２行目のラベルの変換処理を説明するための図である。
【図２２】変形例におけるラベル変換テーブルの一例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（ラベリング処理：直前画素の仮ラベルを現画素に割り当てる例）
２．変形例
【００１７】
＜１．第１の実施の形態＞
［画像処理装置の構成例］
図１は、実施の形態における画像処理装置１００の一構成例を示すブロック図である。この画像処理装置１００は、入力された検出対象画像に対して所定の画像処理を実行するものであり、前処理部１１０、移動体検出部１２０、ラベル付与部２００、移動体追跡処理部１３０、および、後処理部１４０を備える。ここで、検出対象画像は、例えば、動画を構成するフレームのそれぞれであり、２次元格子上に配列された画素からなる画像である。
【００１８】
前処理部１１０は、移動体検出部１２０以降における処理の実行を容易にするための画像処理を前処理として実行するものである。例えば、手ブレを検出して、そのブレを補正する処理などが前処理として実行される。手ブレの検出方式はとしては、動画におけるフレームの各々に基づいてカメラの動きのベクトルを求めるベクトル検出方式などが用いられる。前処理部１１０は、前処理を施した検出対象画像を移動体検出部１２０に信号線１１９を介して出力する。
【００１９】
移動体検出部１２０は、移動する物体を移動体として検出するものである。この移動体検出部１２０は、例えば、動画における今回の検出対象画像（フレーム）と前回の検出対象画像（フレーム）とを比較することにより、移動体を検出する。そして、移動体検出部１２０は、検出した移動体の領域内の画素の画素値を２値のうちの一方の値（例えば、１）とし、それ以外の画素の画素値を他方の値（例えば、０）とした画像（以下、「２値画像」と称する。）を検出対象画像から生成する。以下、移動体として検出された物体の領域内の画素を「有効画素」と称し、それ以外の画素を「無効画素」と称する。移動体検出部１２０は、生成した２値画像をラベル付与部２００に信号線１２９を介して出力する。
【００２０】
なお、移動体検出部１２０は、パターンマッチングなどを行うことにより人物の顔等の物体を認識して、その物体の領域内の画素を有効画素、それ以外の画素を無効画素として２値画像を生成してもよい。また、移動体は、特許請求の範囲に記載の物体の一例である。また、２値画像は、特許請求の範囲に記載の入力画像の一例である。
【００２１】
ラベル付与部２００は、移動体の領域ごとに、その領域を識別するための識別子を本ラベルとして付与する（割り当てる）ものである。ラベル付与部２００は、移動体の領域内の画素のそれぞれの座標と、その領域に割り当てた本ラベルとを含む本ラベルデータを生成して移動体追跡処理部１３０に信号線２０９を介して出力する。
【００２２】
移動体追跡処理部１３０は、移動体を追跡する処理を実行するものである。具体的には、移動体追跡処理部１３０は、前回の本ラベルデータと今回の本ラベルデータとを比較して、サイズや位置が近い本ラベル同士を対応付ける。前回の本ラベルと対応付けられた今回の本ラベルは、前回検出された移動体と同一の移動体の本ラベルであるとして扱われる。移動体追跡処理部１３０は、本ラベル同士を対応付けたデータを後処理部１４０へ信号線１３９を介して出力する。
【００２３】
後処理部１４０は、本ラベルの対応関係から、移動体の追跡結果を生成するものである。例えば、後処理部１４０は、今回の本ラベルデータにおいて前回と対応するものが見つからなかった本ラベルに対応する移動体を新たに出現した移動体であると判断する。また、後処理部１４０は、前回の本ラベルデータにおいて今回と対応するものが見つからなかった本ラベルに対応する移動体を消失した移動体であると判断する。後処理部１４０は、移動体ごとに、判断結果と、移動体の領域内の画素の座標および本ラベルとを含む追跡結果を生成して出力する。この判断結果は、その移動体が前回にも検出されたか否か、および、新たに出現した移動体であるか否か、ならびに、消失した移動体であるか否かについて判断された結果を含む。
【００２４】
［ラベル付与部の構成例］
図２は、実施の形態におけるラベル付与部２００の一構成例を示すブロック図である。このラベル付与部２００は、仮ラベル付与部２１０、仮ラベルデータ保持部２２０、連結情報テーブル保持部２３０、ラベル変換テーブル生成部２４０、起点本ラベル配列保持部２５０、および、ラベル変換テーブル保持部２６０を備える。また、ラベル付与部２００は、本ラベルデータ生成部２７０および本ラベルデータ保持部２８０を備える。
【００２５】
仮ラベル付与部２１０は、２値画像において画素に仮ラベルを割り当てて、仮ラベルデータおよび連結情報テーブルを生成するものである。この仮ラベル付与部２１０は、仮ラベルデータ生成部２１１および連結情報テーブル生成部２１２を備える。
【００２６】
仮ラベルデータ生成部２１１は、２値画像において順に画素に着目して、着目した画素が有効画素である場合に、その画素に仮ラベルを割り当てた仮ラベルデータを生成するものである。詳細には、仮ラベルデータ生成部２１１は、次の手順に従って仮ラベルデータを生成する。まず、仮ラベルデータ生成部２１１は、２値画像においてラスタスキャンを行う。このラスタスキャンにおいては、例えば、画像において上から下へ行の各々が順に着目され、行の各々においては左から右の方向へ順に画素が着目される。以下、仮ラベルデータ生成部２１１が着目した画素を「現画素」と称し、現画素の１つ前に着目された画素を「直前画素」と称する。例えば、現画素の座標を（ｍ，ｎ）とした場合、直前画素の座標は、（ｍ−１，ｎ）とされる。
【００２７】
なお、一定の順に従って画像が着目されるのであれば、画素に着目する順は任意である。仮ラベルデータ生成部２１１は、例えば、画像の左から右へ列の各々に順に着目し、列の各々においては上から下へ順に画素に着目してもよい。
【００２８】
そして、仮ラベルデータ生成部２１１は、現画素が有効画素であるか否かを判断する。現画素が無効画素である場合には、ラスタスキャンの順における次の画素が着目される。現画素が有効画素である場合には、仮ラベルデータ生成部２１１は、直前画素が現画素に隣接する有効画素であるか否かを判断する。直前画素が現画素に隣接する有効画素でないとき（言い換えれば、直前画素が無効画素であるとき、または、直前画素が現画素に隣接していないとき）、仮ラベルデータ生成部２１１は、新たに発行した識別子を現画素の仮ラベルとして現画素に割り当てる。直前画素が現画素に隣接する有効画素であるとき、仮ラベルデータ生成部２１１は、直前画素の仮ラベルを現画素の仮ラベルとして現画素に割り当てる。仮ラベルデータ生成部２１１は、画素ごとに、その画素の座標と画素に割り当てた仮ラベルとを対応付けたデータを仮ラベルデータとして生成して仮ラベルデータ保持部２２０に保持する。また、仮ラベルデータ生成部２１１は、ラスタスキャンにおいて着目した画素の画素値および座標を連結情報テーブル生成部２１２に出力する。
【００２９】
連結情報テーブル生成部２１２は、互いに連結関係にある仮ラベル同士を対応付けた連結情報テーブルを生成するものである。この連結情報テーブルは、連結情報テーブル保持部２３０に保持される。
【００３０】
ここで、画素間に連結関係があるか否かは、２次元座標系における画素間の距離が一定の値（例えば、２1/2）以下であるか否かにより判断される。互いに連結関係にある仮ラベルが付与された画素は、同一の移動体の領域内の画素として扱われる。ここで、連結情報テーブル生成部２１２は、現画素の仮ラベルと直前画素の仮ラベルとを対応付けたエントリについては連結情報テーブルに追加しない。前述したように直前画素および現画素の仮ラベルは同一であり、このエントリはラベル変換テーブルの生成に必要でないためである。また、連結情報テーブル生成部２１２は、連結情報テーブルに同じエントリを２つ以上、追加しない。連結情報テーブルの無駄を省くためである。なお、現画素および直前画素の仮ラベルからなるエントリや、重複するエントリを連結情報テーブル生成部２１２が追加し、これらのエントリの処理をラベル変換テーブル生成部２４０がスキップする構成とすることもできる。
【００３１】
例えば、距離が２1/2以下の画素間に連結関係があると定義した場合を考える。この場合、現画素（ｍ，ｎ）と連結する画素の座標は、（ｍ−１，ｎ−１）、（ｍ，ｎ−１）、（ｍ＋１，ｎ−１）、（ｍ−１，ｎ）、（ｍ＋１，ｎ）、（ｍ−１，ｎ＋１）、（ｍ，ｎ＋１）、および、（ｍ＋１，ｎ＋１）の８つである。このうち、（ｍ−１，ｎ）は直前画素であるから、連結情報テーブルに追加する対象から除かれる。また、ラスタスキャンにおいて、（ｍ＋１，ｎ）、（ｍ−１，ｎ＋１）、（ｍ，ｎ＋１）、および、（ｍ＋１，ｎ＋１）は、現画素より後に着目されるため、未だ仮ラベルが付与されていない。このため、現画素に着目した時点においては、これらの画素が連結情報テーブルに追加されることはない。したがって、連結情報テーブル生成部２１２は、（ｍ−１，ｎ−１）、（ｍ，ｎ−１）、および、（ｍ＋１，ｎ−１）の３つの画素について有効画素であるか否かを判断すればよい。
【００３２】
現画素と、（ｍ−１，ｎ−１）、（ｍ，ｎ−１）、および、（ｍ＋１，ｎ−１）のうちのいずれかと、が有効画素である場合について考える。この場合、連結情報テーブル生成部２１２は、現画素の仮ラベルと、有効画素（Ｍ、ｎ−１）の仮ラベルとを対応付けたエントリを、新規に追加するエントリを生成する。ここで、Ｍは、ｍ−１、ｍ、または、ｍ＋１である。このエントリが直前エントリと重複しない場合、連結情報テーブル生成部２１２は、その候補を連結情報テーブルに追加する。ここで、直前エントリは、追加するエントリの候補の直前に追加されたエントリ、言い換えれば、現画素に着目した時点における最後のエントリである。
【００３３】
なお、連結情報テーブル生成部２１２は、画素間の距離が２1/2以下であるか否か以外の条件に従って連結関係を判断することもできる。例えば、距離が１以下の画素間に連結関係があると定義した場合、連結情報テーブル生成部２１２は、（ｍ，ｎ−１）の画素についてのみ、有効画素であるか否かを判断すればよい。また、距離が２以下の画素間に連結関係があると定義した場合、連結情報テーブル生成部２１２は、（ｍ−１、ｎ−１）、（ｍ，ｎ−１）、（ｍ＋１，ｎ−１）、および、（ｍ，ｎ−２）の画素について有効画素であるか否かを判断すればよい。また、連結情報テーブル生成部２１２は、特許請求の範囲に記載の連結情報生成部の一例である。
【００３４】
ラベル変換テーブル生成部２４０は、仮ラベルと本ラベルとを対応付けたラベル変換テーブルを連結情報テーブルから生成するものである。ラベル変換テーブル生成部２４０は、例えば、次の手順に従ってラベル変換テーブルを生成する。
【００３５】
まず、ラベル変換テーブル生成部２４０は、連結情報テーブルにおいて連結元仮ラベルＬｐｆから連結先仮ラベルＬｐｔへと連結関係にある仮ラベルを辿ってゆき、他に連結関係のある仮ラベルを辿れなくなった仮ラベルを求める。求められた仮ラベルは、互いに連結関係にある仮ラベルの集合において、最初に発行された仮ラベルである。この仮ラベルを以下、「起点仮ラベル」と称する。ラベル変換テーブル生成部２４０は、互いに連結関係のある仮ラベルからなる集合（言い換えれば、同じ移動体の領域内の画素群）ごとに起点仮ラベルを求める。
【００３６】
次に、ラベル変換テーブル生成部２４０は、起点仮ラベルの各々について本ラベルを発行する。ラベル変換テーブル生成部２４０は、それらの起点仮ラベルに対し、発行した本ラベルを対応付けた起点本ラベル配列を、起点本ラベル配列保持部２５０に保持する。
【００３７】
そして、ラベル変換テーブル生成部２４０は、起点仮ラベルの探索において辿った全ての仮ラベルに対して、その起点仮ラベルについて発行された本ラベルを対応付けたテーブルをラベル変換テーブルとして生成する。生成されたラベル変換テーブルは、ラベル変換テーブル保持部２６０に保持される。
【００３８】
本ラベルデータ生成部２７０は、ラベル変換テーブルおよび仮ラベルデータから本ラベルデータを生成するものである。具体的には、本ラベルデータ生成部２７０は、仮ラベルデータにおいてラスタスキャンを行う。このラスタスキャンの順は、仮ラベルを割り当てた際のラスタスキャンの順と同じものである。そして、本ラベルデータ生成部２７０は、ラスタスキャンにおいて着目した現画素の仮ラベルに対応する本ラベルをラベル変換テーブルから読み出し、読み出した本ラベルを仮ラベルの代わりに現画素に割り当てる。本ラベルデータ生成部２７０は、画素ごとに、その画素の座標と画素に割り当てた本ラベルとを対応付けたデータを本ラベルデータとして生成して本ラベルデータ保持部２８０に保持する。
【００３９】
図３は、実施の形態における仮ラベルデータ生成部２１１の動作の一例を示す表である。仮ラベルデータ生成部２１１は、ラスタスキャンにおいて着目した現画素の画素値Ｐ（ｍ，ｎ）が１である（すなわち、有効画素である）か否かを判断する。Ｐ（ｍ，ｎ）が０である場合、仮ラベルデータ生成部２１１は、その座標について無効な値（例えば、０）の仮ラベルを割り当てる。Ｐ（ｍ，ｎ）が１である場合、仮ラベルデータ生成部２１１は、現画素に隣接する直前画素の仮ラベル値Ｌｐ（ｍ−１，ｎ）が０以外の値である（すなわち、その直前画素が有効画素である）か否かを判断する。Ｌｐ（ｍ−１，ｎ）が０以外の値である場合、仮ラベルデータ生成部２１１は、Ｌｐ（ｍ−１，ｎ）の値の仮ラベルを現画素に割り当てる。Ｌｐ（ｍ−１，ｎ）が０である場合、仮ラベルデータ生成部２１１は、新たに発行した値の仮ラベルを現画素に割り当てる。
【００４０】
図４は、実施の形態における連結情報テーブル生成部２１２の動作の一例を示す表である。連結情報テーブル生成部２１２は、現画素の画素値Ｐ（ｍ，ｎ）が１であるか否かを判断する。Ｐ（ｍ，ｎ）が１である場合、連結情報テーブル生成部２１２は、現画素と連結関係にある画素の仮ラベル値Ｌｐ（Ｍ，ｎ−１）のうちのいずれかが０以外の値（有効な値）であるか否かを判断する。ここで、Ｍは、ｍ−１、ｍ、または、ｍ＋１である。Ｌｐ（Ｍ，ｎ−１）のうちのいずれかが有効な値である場合、連結情報テーブル生成部２１２は、Ｌｐ（ｍ，ｎ）と、有効な仮ラベル値Ｌｐ（Ｍ，ｎ−１）とを対応付けたエントリが直前エントリと重複するか否かを判断する。Ｌｐ（ｍ，ｎ）およびＬｐ（Ｍ，ｎ−１）からなるエントリが直前エントリと重複しなければ、連結情報テーブル生成部２１２は、そのエントリを連結情報テーブルに新たに追加する。
【００４１】
図５は、実施の形態における２値画像の一例を示す図である。２値画像において、網掛けの画素は検出対象画像において検出された移動体の領域内の画素（すなわち、有効画素）であり、それ以外の画素は移動体の領域外の画素（すなわち、無効画素）である。有効画素の画素値は、例えば１であり、無効画素の画素値は、例えば０である。なお、有効画素および無効画素のそれぞれの画素値は１および０に限定されない。例えば、有効画素の画素値を０とし、無効画素の画素値を２５５としてもよい。
【００４２】
図６は、実施の形態における仮ラベルデータ保持部２２０に保持された仮ラベルデータの一例を示す図である。この仮ラベルデータにおいて、網掛けの画素は有効画素であり、そうでない画素は無効画素である。有効画素には有効な値（例えば、０以外の値）の仮ラベルが割り当てられ、無効画素には無効な値（例えば、０）の仮ラベルが割り当てられる。そして、この仮ラベルは、画素に着目した順に沿って規則的に発行される。例えば、２値画像において（０，０）乃至（４，０）が無効画素であり、（５，０）が有効画素であった場合について考える。この場合、着目された無効画素（０，０）乃至（４，０）には無効な値（例えば、０）の仮ラベルが割り当てられる。そして、次に着目された現画素（５，０）は有効画素であり、その直前画素（４，０）は無効画素であるから、現画素（５，０）には新たに発行した１の値の仮ラベルが割り当てられる。続いて着目された（６，０）および（７，０）が無効画素であり、（８，０）が有効画素であった場合、同様に、（６，０）および（７，０）に０が割り当てられ、（８，０）には新たに発行した２の値が割り当てられる。そして、次に着目された現画素（９，０）が有効画素であった場合、直前画素（８，０）が有効画素であるため、その直前画素の仮ラベル値である２が、現画素（９，０）に割り当てられる。
【００４３】
図７は、実施の形態における連結情報テーブルＬおよびラベル変換テーブルＨの一例である。図７（ａ）は連結情報テーブル保持部２３０に保持された連結情報テーブルＬの一例である。この連結情報テーブルＬは、結合元仮ラベル値Ｌｐｆと結合先仮ラベル値Ｌｐｔとを対応付けたエントリを１つ以上有する。結合元仮ラベル値Ｌｐｆの配列には、現画素の仮ラベル値が保持され、結合先仮ラベル値Ｌｐｔの配列には、現画素と連結関係にある有効画素の仮ラベル値が保持される。例えば、仮ラベルデータにおいて現画素（４，１）の仮ラベル値が４であり、その現画素と連結関係にある有効画素（５，０）の仮ラベル値が１であり、この連結関係が最初に見つかった場合を考える。この場合、４が最初の結合元仮ラベル値Ｌｐｆ［０］に保持され、１が最初の結合先仮ラベル値Ｌｐｔ［０］に保持される。
【００４４】
図７（ｂ）は、ラベル変換テーブル保持部２６０に保持されたラベル変換テーブルＨの一例である。このラベル変換テーブルＨは、各々にエントリ番号が割り当てられた複数のエントリを有する。このエントリ番号は、例えば、先頭からのメモリオフセット値である。エントリの各々には、そのエントリのメモリオフセット値と同じ値の仮ラベルに対応する本ラベルが保持される。例えば、仮ラベル値１乃至９に対して、本ラベル値１が対応付けられた場合、ラベル変換テーブルＨにおいてメモリオフセット値１乃至９のエントリに本ラベル値１が保持される。なお、メモリオフセット値０の領域は、有効な本ラベル値を保持する領域として用いられない。
【００４５】
図８は、実施の形態における本ラベルデータの一例を示す図である。この本ラベルデータにおいては、画素の各々について仮ラベルに代えて本ラベルが割り当てられる。例えば、仮ラベルデータにおいて（４，１）に４の仮ラベル値が割り当てられ、ラベル変換テーブルにおいて仮ラベル値４に本ラベル値１が対応付けられた場合について考える。この場合、（４，１）に対して、仮ラベル値４の代わりに本ラベル値１が割り当てられる。この結果、２値画像において互いに連結関係にある有効画素からなる領域の各々に対して異なる本ラベルが割り当てられる。例えば、有効画素（２，４）と有効画素（２，５）との間の距離は２１／２以下であるから互いに連結関係にあり、これらには同じ値の本ラベル値１が割り当てられる。一方、無効画素（２，６）を挟む有効画素（２，７）と有効画素（２，５）との間の距離は、２１／２より大きく連結関係にないため、（２，７）には（２，５）とは異なる本ラベル値３が割り当てられる。
【００４６】
［画像処理装置の動作例］
次に、図９を参照して、上述の実施の形態における画像処理装置１００の動作の一例について説明する。この動作は、例えば、動画に含まれる検出対象画像が画像処理装置１００に入力されたときに開始する。画像処理装置１００は、検出対象画像に対し、カメラのブレ補正などの前処理を実行する（ステップＳ９１０）。そして、画像処理装置１００は、前回の検出対象画像と今回の検出対象画像とから移動体を検出して、移動体の領域内の画素を有効画素とし、移動体の領域外の画素を無効画素とした２値画像を生成する（ステップＳ９１１）。
【００４７】
画像処理装置１００は、２値画像から仮ラベルデータおよび連結情報テーブルを生成するための仮ラベルデータ生成処理を実行する（ステップＳ９２０）。画像処理装置１００は、連結情報テーブルからラベル変換テーブルを生成するためのラベル変換テーブル生成処理を実行する（ステップＳ９４０）。画像処理装置１００は、仮ラベルデータおよびラベル変換テーブルから本ラベルデータを生成するための本ラベルデータ生成処理を実行する（ステップＳ９８０）。
【００４８】
画像処理装置１００は、前回および今回の本ラベルデータを比較して、サイズや位置が近い領域の本ラベル同士を対応付ける（ステップＳ９９１）。画像処理装置１００は、本ラベルの対応関係から、移動体ごとに出現および消失を判定し、追跡結果を出力する（ステップＳ９９２）。ステップＳ９９２の後、画像処理装置１００は、今回の検証対象画像に対する画像処理を終了する。
【００４９】
［ラベル付与部の動作例］
次に、図１０乃至１５を参照して、実施の形態におけるラベル付与部２００の動作の一例について説明する。図１０は、実施の形態における仮ラベルデータ生成処理の一例を示すフローチャートである。画像処理装置１００におけるラベル付与部２００は、仮ラベル値の計数値である仮ラベルカウンタＣｐを０に初期化する（ステップＳ９２１）。ラベル付与部２００は、２値画像においてラスタスキャンを行う。ここで、２値画像における画素の水平座標は０乃至Ｗ−１であり、垂直座標は０乃至Ｈ−１とする。ラスタスキャンにおいては、（０，０）から（Ｗ−１，Ｈ−１）へ順に画素が着目される。ラベル付与部２００は、着目した画素を現画素として次のステップＳ９２３乃至Ｓ９３０を実行する（ステップＳ９２２）。ステップＳ９２２の後、ラベル付与部２００は、仮ラベルデータ生成処理を終了する。
【００５０】
ラベル付与部２００は、現画素が有効画素である（すなわち、現画素の画素値Ｐ（ｍ，ｎ）が１である）か否かを判断する（ステップＳ９２３）。現画素が有効画素である場合（ステップＳ９２３：Ｙｅｓ）、ラベル付与部２００は、直前画素が現画素に隣接する（言い換えれば、ｍ≠０である）か否かを判断する（ステップＳ９２４）。直前画素が現画素に隣接する場合（ステップＳ９２４：Ｙｅｓ）、ラベル付与部２００は、直前画素が有効画素である（すなわち、直前画素の仮ラベル値Ｌｐ（ｍ，ｎ−１）≠０）か否かを判断する（ステップＳ９２５）。直前画素が有効画素である場合（ステップＳ９２５：Ｙｅｓ）、ラベル付与部２００は、直前画素の仮ラベル値Ｌｐ（ｍ，ｎ−１）を現画素の仮ラベル値Ｌ（ｍ，ｎ）として現画素に割り当てる（ステップＳ９２６）。
【００５１】
直前画素が現画素に隣接しない場合（ステップＳ９２４：Ｎｏ）、または、直前画素が有効画素でない場合（ステップＳ９２５：Ｎｏ）、ラベル付与部２００は、現画素に新規に仮ラベルを割り当てる。具体的には、仮ラベルカウンタＣｐをインクリメントし、インクリメント後の仮ラベルカウンタＣｐの値を現画素の仮ラベル値Ｌｐ（ｍ，ｎ）として現画素に割り当てる（ステップＳ９２８）。ステップＳ９２６またはＳ９２８の後、ラベル付与部２００は、連結情報テーブルにエントリを追加するための連結情報テーブルエントリ追加処理を実行する（ステップＳ９３０）。
【００５２】
現画素が有効画素でない場合（ステップＳ９２３：Ｎｏ）、ラベル付与部２００は、無効な値（例えば、０）の仮ラベルを現画素の仮ラベル値Ｌｐ（ｍ，ｎ）として現画素に割り当てる（ステップＳ９２７）。ステップＳ９２７またはステップＳ９３０の後、ラベル付与部２００は、ステップＳ９２２に戻る。
【００５３】
図１１は、連結情報テーブルエントリ追加処理の一例を示すフローチャートである。ラベル付与部２００は、現画素が２値画像における１行目の画素であるか否かを判断する（ステップＳ９３１）。
【００５４】
現画素が２行目以降の画素である場合（ステップＳ９３１：Ｎｏ）、ラベル付与部２００は、水平座標Ｍ（Ｍは、ｍ−１乃至ｍ＋１）について次のステップＳ９３３乃至Ｓ９３５の処理を実行する（ステップＳ９３２）。
【００５５】
ラベル付与部２００は、現画素に連結する画素の仮ラベル値Ｌｐ（Ｍ，ｎ−１）が０より大きいか否かを判断する（ステップＳ９３３）。Ｌｐ（Ｍ，ｎ−１）が０より大きい場合（ステップＳ９３３：Ｙｅｓ）、ラベル付与部２００は、Ｌｐ（ｍ，ｎ）およびＬｐ（Ｍ，ｎ−１）からなるエントリが連結情報テーブルにおける直前エントリと重複するか否かを判断する（ステップＳ９３４）。Ｌｐ（ｍ，ｎ）およびＬｐ（Ｍ，ｎ−１）のエントリが直前エントリと重複しない場合（ステップＳ９３４：Ｎｏ）、ラベル付与部２００は、そのエントリを連結情報テーブルに追加する（ステップＳ９３５）。
【００５６】
Ｌｐ（Ｍ，ｎ−１）が０である場合（ステップＳ９３３：Ｎｏ）、または、直前エントリと重複する場合（ステップＳ９３４：Ｙｅｓ）、もしくは、ステップＳ９３５の後、ラベル付与部２００は、ステップＳ９３２に戻る。
【００５７】
現画素が１行目の画素である場合（ステップＳ９３１：Ｙｅｓ）、または、ステップＳ９３２の後、ラベル付与部２００は、連結情報テーブルエントリ追加処理を終了する。
【００５８】
図１２は、実施の形態におけるラベル変換テーブル生成処理の一例を示すフローチャートである。ラベル変換テーブル生成処理においてラベル付与部２００は、起点仮ラベルを決定するための起点仮ラベル決定処理を実行し（ステップＳ９４５）、本ラベルを発行するための本ラベル発行処理を実行する（ステップ９６０）。そして、ラベル付与部２００は、仮ラベルと本ラベルとの対応関係を決定するためのラベル対応関係決定処理を実行する（ステップＳ９７０）。ラベル対応関係決定処理の後、ラベル付与部２００は、ラベル変換テーブル生成処理を終了する。
【００５９】
図１３は、実施の形態における起点仮ラベル決定処理の一例を示すフローチャートである。ラベル付与部２００は、連結情報テーブルＬのエントリの数をＮＬとして保持する。また、ラベル付与部２００は、仮ラベルの各々に対する本ラベルの値を全て０に初期化したラベル変換テーブルＨを生成する（ステップＳ９４６）。
【００６０】
ラベル付与部２００は、０乃至ＮＬ−１の変数ｉについて次のステップＳ９４８乃至Ｓ９５５を実行する（ステップＳ９４７）。ステップＳ９４７の後、ラベル付与部２００は、起点仮ラベル決定処理を終了する。
【００６１】
ラベル付与部２００は、連結情報テーブルＬを参照し、ｉ番目の連結元仮ラベル値Ｌｐｆ［ｉ］を変数ａに保持し、ｉ番目の連結先仮ラベル値Ｌｐｔ［ｉ］を変数ｂに保持する（ステップＳ９４８）。ラベル付与部２００は、ラベル変換テーブルＨにおいて、ａ番目のエントリＨ［ａ］が０であるか否かを判断する（ステップＳ９４９）。Ｈ［ａ］が０でない場合（ステップＳ９４９：Ｎｏ）、ラベル付与部２００は、変数ａをＨ［ａ］により更新する（ステップＳ９５０）。ステップＳ９５０の後、ラベル付与部２００は、ステップＳ９４９に戻る。
【００６２】
Ｈ［ａ］が０である場合（ステップＳ９４９：Ｙｅｓ）、ラベル付与部２００は、ラベル変換テーブルＨにおいて、ｂ番目のエントリＨ［ｂ］が０であるか否かを判断する（ステップＳ９５１）。Ｈ［ｂ］が０でない場合（ステップＳ９５１：Ｎｏ）、ラベル付与部２００は、変数ｂをＨ［ｂ］により更新する（ステップＳ９５２）。ステップＳ９５２の後、ラベル付与部２００は、ステップＳ９５１に戻る。
【００６３】
Ｈ［ｂ］が０である場合（ステップＳ９５１：Ｙｅｓ）、ラベル付与部２００は、ａがｂより大きいか否かを判断する（ステップＳ９５３）。なお、仮ラベルデータ生成処理において同じ値のＬｐｆおよびＬｐｔが、連結情報テーブルＬに保持されることはないため、ａおよびｂが同じ値となることはない。
【００６４】
ａがｂより大きい場合（ステップＳ９５３：Ｙｅｓ）、ラベル付与部２００は、Ｈ［ａ］をｂにより更新する（ステップＳ９５４）。ａがｂより小さい場合（ステップＳ９５３：Ｎｏ）、ラベル付与部２００は、Ｈ［ｂ］をａにより更新する（ステップＳ９５５）。ステップＳ９５４またはＳ９５５の後、ラベル付与部２００は、ステップＳ９４７に戻る。
【００６５】
起点仮ラベル決定処理により、ラベル変換テーブルＨにおいて起点仮ラベルに対応するエントリに０が保持される。また、起点仮ラベル以外の仮ラベルに対応するエントリには、起点仮ラベルを辿るための値（例えば、起点仮ラベルのエントリを示すポインタやポインタのポインタ）が保持される。
【００６６】
図１４は、実施の形態における本ラベル発行処理の一例を示すフローチャートである。ラベル付与部２００は、仮ラベルの各々に対応するエントリを有し、それらのエントリの値を全て０に初期化した起点本ラベル配列Ｔを生成する。また、ラベル付与部２００は、仮ラベルの個数をＮｐとして保持し、本ラベル値の計数値である本ラベルカウンタＣｎｐを０に初期化する（ステップＳ９６１）。
【００６７】
ラベル付与部２００は、０乃至Ｎｐ−１の変数ｊについて次のステップＳ９６３およびＳ９６４を実行する（ステップＳ９６２）。ステップＳ９６２の後、ラベル付与部２００は、起点仮ラベル決定処理を終了する。
【００６８】
ラベル付与部２００は、変数ｊの値が起点仮ラベルの値である（すなわち、ｊ番目のエントリＨ［ｊ］＝０）か否かを判断する（ステップＳ９６３）。Ｈ［ｊ］＝０である場合（ステップＳ９６３：Ｙｅｓ）、ラベル付与部２００は、起点本ラベル配列におけるｊ番目のエントリＴ［ｊ］を本ラベルカウンタＣｎｐの値により更新し、Ｃｎｐをインクリメントして本ラベルを発行する（ステップＳ９６４）。Ｈ［ｊ］≠０である場合（ステップＳ９６３：Ｎｏ）、または、ステップＳ９６４の後、ラベル付与部２００は、ステップＳ９６２に戻る。
【００６９】
本ラベル発行処理により、起点本ラベル配列において、起点仮ラベルと同じ値のエントリに本ラベルが保持され、他のエントリには０の値が保持される。
【００７０】
図１５は、実施の形態におけるラベル対応関係決定処理の一例を示すフローチャートである。ラベル付与部２００は、Ｎｐ−１乃至０の変数ｋについて次のステップＳ９７２乃至Ｓ９７７を実行する（ステップＳ９７１）。ステップＳ９７１の後、ラベル付与部２００は、ラベル対応関係決定処理を終了する。
【００７１】
ラベル付与部２００は、ラベル変換テーブルＨにおいてｋ番目のエントリＨ［ｋ］が０であるか否かを判断する（ステップＳ９７２）。Ｈ［ｋ］が０でない場合（ステップＳ９７２：Ｎｏ）、ラベル付与部２００は、変数ｋの値を変数ｔに保持する（ステップＳ９７３）。そして、ラベル付与部２００は、ラベル変換テーブルＨにおいてＨ［ｔ］が０であるか否かを判断する（ステップＳ９７４）。Ｈ［ｔ］が０でない場合（ステップＳ９７４：Ｎｏ）、ラベル付与部２００は、変数ｔの値をＨ［ｔ］により更新する（ステップＳ９７５）。ステップＳ９７５の後、ラベル付与部２００は、ステップＳ９７４に戻る。
【００７２】
Ｈ［ｔ］が０である場合（ステップＳ９７４：Ｙｅｓ）、ラベル付与部２００は、仮ラベル値ｋに対し、本ラベル値Ｔ［ｔ］を対応付ける。具体的には、ラベル付与部２００は、ラベル変換テーブルＨにおいてＨ［ｋ］をＴ［ｔ］により更新する（ステップＳ９７６）。
【００７３】
Ｈ［ｋ］が０である場合（ステップＳ９７２：Ｙｅｓ）、ラベル付与部２００は、仮ラベル値ｋに対し、本ラベル値Ｔ［ｋ］を対応付ける。具体的には、ラベル付与部２００は、ラベル変換テーブルＨにおいてＨ［ｋ］をＴ［ｋ］により更新する（ステップＳ９７７）。ステップＳ９７６またはＳ９７７の後、ラベル付与部２００は、ステップ９７１に戻る。
【００７４】
ラベル対応関係決定処理により、ラベル変換テーブルにおいて起点仮ラベルと連結関係にある仮ラベルの各々に対し、その起点仮ラベルについて発行された本ラベルが対応付けられる。
【００７５】
図１６は、実施の形態における本ラベルデータ生成処理の一例を示すフローチャートである。ラベル付与部２００は、仮ラベルデータにおいてラスタスキャンを行う。このラスタスキャンにおいて着目した画素を現画素としてラベル付与部２００は、次のステップＳ９８２およびＳ９８３を実行する（ステップＳ９８１）。ステップＳ９８１の後、ラベル付与部２００は、本ラベルデータ生成処理を終了する。
【００７６】
ラベル付与部２００は、現画素の仮ラベル値Ｌｐ（ｍ，ｎ）が無効な値（例えば、０）であるか否かを判断する（ステップＳ９８２）。Ｌｐ（ｍ，ｎ）≠０である場合（ステップＳ９８２：Ｎｏ）、ラベル付与部２００は、仮ラベルデータにおいて仮ラベル値Ｌｐ（ｍ，ｎ）を、その仮ラベル値に対応する本ラベル値Ｈ［Ｌｐ（ｍ，ｎ）］に置き換える（ステップＳ９８３）。ステップＳ９８３の後、ラベル付与部２００は、ステップＳ９８１に戻る。
【００７７】
本ラベルデータ生成処理により、仮ラベルデータにおいて仮ラベルが本ラベルに置き換えられる。仮ラベルが本ラベルに置き換えられた仮ラベルデータは、本ラベルデータとして出力される。
【００７８】
なお、ラベル付与部２００は、仮ラベルデータにおいて仮ラベルを本ラベルに更新したものを本ラベルデータとして生成しているが、仮ラベルデータと別途に本ラベルデータを生成してもよい。この場合、ラベル付与部２００は、仮ラベルデータから現画素の仮ラベルを読み出し、別途に生成した本ラベルデータにおいて、その現画素の座標と同じ座標の画素に対し、仮ラベルと対応する本ラベルを対応付ける。
【００７９】
続いて、図１７乃至図１９を参照して、連結情報テーブルＬからラベル変換テーブルＨを生成する処理について説明する。図１７は、実施の形態における起点仮ラベルを探索中のラベル変換テーブルＨの一例である。
【００８０】
２値画像の画素について、１乃至１７の値の仮ラベルが付与された場合について考える。また、仮ラベルデータは図６に例示した構成であり、連結情報テーブルＬは図７（ａ）に例示した構成であるものとする。この場合、メモリオフセット値が１乃至１７のエントリを有するラベル変換テーブルＨが生成される。初期状態においては、エントリの各々には０の値が保持される。
【００８１】
ｉ＝０の場合、連結情報テーブルにおいてＬｐｆ［０］＝４であり、Ｌｐｔ［０］＝１である。つまり、４の仮ラベルと１の仮ラベルとが連結関係にある。また、初期状態のラベル変換テーブルＨにおいてＨ［４］およびＨ［１］はいずれも０である。この場合、Ｈ［４］の値が、４と連結関係にある１の値により更新される。
【００８２】
ｉ＝１の場合、連結情報テーブルにおいてＬｐｆ［１］＝５であり、Ｌｐｔ［１］＝２である。この場合、Ｈ［５］の値が、５と連結関係にある２の値により更新される。ｉ＝２の場合、連結情報テーブルにおいてＬｐｆ［２］＝６であり、Ｌｐｔ［２］＝３である。この場合、Ｈ［６］の値が、６と連結関係にある３の値により更新される。
【００８３】
ｉ＝３の場合、連結情報テーブルにおいてＬｐｆ［３］＝６であり、Ｌｐｔ［３］＝４である。また、i＝２の状態のラベル変換テーブルＨにおいてＨ［６］およびＨ［４］は０でない。この状態のラベル変換テーブルＨにおいて、メモリオフセット値６に対応付けられた仮ラベルＨ［６］（＝３）を辿り、その仮ラベル値３に対応付けられた仮ラベル値Ｈ［３］を辿ると、Ｈ［３］は無効な値０である。一方、メモリオフセット値４に対応付けられた仮ラベルＨ［４］（＝１）を辿り、その仮ラベル値１に対応付けられた仮ラベル値Ｈ［１］を辿ると、Ｈ［１］は無効な値０である。連結関係のある他の仮ラベルを辿れなくなったときの仮ラベルはそれぞれ３と１とであるため、Ｈ［３］の値が、３と連結関係にある１の値により更新される。
【００８４】
このようにしてｉが０から１３となるまでラベル変換テーブルＨを更新してゆくと、互いに連結関係にある仮ラベルの集合において最初に発行された仮ラベル（起点仮ラベル）をメモリオフセット値とするエントリに０の値が保持される。それ以外のエントリには、起点仮ラベルを辿るための値が保持される。例えば、仮ラベル１乃至９および１１が互いに連結関係にある場合、この集合において最初に発行された仮ラベルの値は１である。したがって、メモリオフセット値が１のエントリに０の値が保持される。メモリオフセット値２乃至４のエントリには、起点仮ラベルの値を示すポインタの値である１が保持される。メモリオフセット値５のエントリには、起点仮ラベルを示すポインタのポインタ値である２が保持されている。
【００８５】
図１８は、実施の形態における起点本ラベル配列Ｔの一例を示す図である。この起点本ラベル配列Ｔは、メモリオフセット値が仮ラベル値と同じ値のエントリを有し、初期状態においては、それらのエントリには０の値が保持される。なお、メモリオフセット値０の領域は、有効な値を保持する領域として用いられない。ここで、ラベル変換テーブルＨにおいて、起点仮ラベルの値である１、１０、および、１６をメモリオフセット値とするエントリに０が保持され、それ以外のエントリには０以外の値が保持されたものとする。この場合、それらの起点仮ラベル１、１０、および、１６について、本ラベル値１、２、および、３が発行される。そして、起点本ラベル配列Ｔにおけるオフセット値１、１０、および、１６のエントリに本ラベルの値である１、２、および、３が保持される。
【００８６】
図１９は、実施の形態における本ラベルを付与中のラベル変換テーブルＨの一例である。ｋ＝１７の場合、Ｈ［１７］が０でないことから１７は起点仮ラベル値ではない。Ｈ［１７］は１０であり、１０から辿ったＨ［１０］が０であることから１０が起点仮ラベル値である。この起点仮ラベル値１０に対し、起点本ラベル配列Ｔにおいて本ラベル値２が対応付けられている。このため、Ｈ［１７］は２に更新される。
【００８７】
ｋ＝１６の場合、Ｈ［１６］が０であるから１６は起点仮ラベル値である。この起点仮ラベル値１６に対し、起点本ラベル配列Ｔにおいて本ラベル値３が対応付けられている。このため、Ｈ［１６］は３に更新される。
【００８８】
このようにして、ｋが１７から０になるまでラベル変換テーブルＨを更新してゆくと、起点仮ラベルに至るまで辿った仮ラベルの各々に対し、その起点仮ラベルについて発行された本ラベルが対応付けられた状態となる。
【００８９】
図２０および図２１を参照して、本ラベリングにおけるラベル変換テーブルＨへのアクセス効率について説明する。図２０は、実施の形態における１行目のラベルの変換処理を説明するための図である。図２０の上段に示すように、初期状態における仮ラベルデータの１行目の（５，０）、（８，０）、（９，０）の画素について、それぞれ１、２、２の値の仮ラベルが割り当てられている。このため、ラスタスキャンにおいて、１、２、２の仮ラベル値が順に仮ラベルデータから読み出される。
【００９０】
ラベル付与部２００は、仮ラベル値が１である（５，０）に着目時に、ラベル変換テーブルＨにおいてメモリオフセット値が１のエントリを参照する。このエントリには１の値の本ラベルが保持されているため、（５，０）に対して１の値の本ラベルが割り当てられる。
【００９１】
続いて、ラベル付与部２００は、仮ラベル値が２である（８，０）および（９，０）に着目時に、ラベル変換テーブルＨにおいてメモリオフセット値が２のエントリを参照する。このエントリには１の値の本ラベルが保持されているため、（８，０）および（９，０）に対し、２の値の仮ラベルの代わりに１の値の本ラベルが割り当てられる。この結果、図２０の下段に示すように、仮ラベルデータの１行目において仮ラベルが本ラベルに変換された状態となる。仮ラベルデータにおける網掛けは、ラベルが変換された画素である。
【００９２】
図２１は、実施の形態における２行目のラベルの変換処理を説明するための図である。図２１の上段に示すように、１行目を変換後の仮ラベルデータ２２０の２行目の（１，１）、（２，１）、（４，１）、（７，１）の画素について、それぞれ３、３、４、５の値の仮ラベルが割り当てられている。このため、ラスタスキャンにおいて、３、３、４、５の仮ラベル値が順に仮ラベルデータ２２０から読み出される。
【００９３】
ラベル付与部２００は、仮ラベル値が３である（１，１）および（２，１）の着目時に、ラベル変換テーブルＨにおいてオフセット値が３のエントリを参照する。このエントリには１の値の本ラベルが保持されているため、（１，１）および（２，１）に対し、３の値の仮ラベルの代わりに１の値の本ラベルが割り当てられる。同様に、（４，１）、（７，１）の画素に対し、４、５の値の仮ラベルの代わりに１の値の本ラベルが割り当てられる。この結果、図２１の下段に示すように、仮ラベルデータの２行目において仮ラベルが本ラベルに変換された状態となる。仮ラベルデータにおける網掛けは、ラベルが変換された画素である。
【００９４】
図２０および図２１に例示したように、ラスタスキャンを行って本ラベリングを行った場合、その順に沿ってラベル変換テーブルＨがアクセスされる。このため、ラベル変換テーブルＨのアクセス効率が向上する。
【００９５】
このように本技術の実施の形態によれば、画像処理装置１００は、画素に順に着目して、着目した現画素が有効画素であり、かつ、直前画素が現画素に隣接する前記有効画素でない場合には新規の仮ラベルを現画素に割り当てる。一方、画像処理装置１００は、現画素が有効画素であり、かつ、直前画素が現画素に隣接する有効画素である場合に、その直前画素の仮ラベルを現画素の仮ラベルとして現画素に割り当てる。これにより、着目した順番に沿って発行された仮ラベルが画素に割り当てられる。したがって、本ラベリングにおいて、その順番に沿ってラベル変換テーブルがアクセスされる。この結果、ラベル変換テーブルのアクセス効率が向上してラベリング処理を高速に実行することができる。
【００９６】
また、本ラベリングにおいてラベル変換テーブルへのアクセスの遅延を抑制する目的でラベル変化テーブル内のある程度の数のエントリをキャッシュに保持しておく手法があるが、この手法を用いる場合、キャッシュの制御が簡易なもので済む。これは、ラスタスキャンの順に沿って仮ラベルが発行されており、キャッシュに必要なエントリ数を予測することが容易であるためである。
【００９７】
さらに、本技術の実施の形態によれば、簡易な構成でラベリング処理を高速化することができるため、単位時間当たりの画像の処理数（フレームレート）を増加することができる。フレームレートの増加により、ビデオカメラや監視カメラシステムなどにおいて顔等の物体認識を実行する際に認識精度を容易に向上させることができる。
【００９８】
＜１．変形例＞
図２２を参照して、上述の実施の形態における変形例について説明する。図２２は、
実施の形態における変形例のラベル変換テーブルの一例である。図７（ｂ）に例示したラベル変換テーブルにおいては本ラベルのみが保持され、メモリオフセット値が仮ラベルの値を表わしていたのに対し、図２２に例示したラベル変換テーブルには、本ラベルに加えて、仮ラベルの値が保持される。これにより、画像処理装置１００は、メモリオフセット値と異なる値の仮ラベル値を画素に割り当てることができる。
【００９９】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１００】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【０１０１】
なお、本技術は以下のような構成もとることができる。
（１）所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成部と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成部と
を具備する画像処理装置。
（２）いずれかの前記仮ラベルから当該仮ラベルと前記連結関係にある前記仮ラベルを辿っていくことにより相互に前記連結関係にある前記仮ラベルからなる集合を生成して当該集合の各々を識別するための識別子である本ラベルと前記仮ラベルとを対応付けたラベル変換テーブルを生成するラベル変換テーブル生成部と、
前記仮ラベルデータにおける前記画素に前記所定の順番に従って着目して前記ラベル変換テーブルにおいて前記着目した画素の前記仮ラベルに対応付けられた前記本ラベルを前記仮ラベルの代わりに前記画素に割り当てた本ラベルデータを生成する本ラベルデータ生成部と
をさらに具備する前記（１）記載の画像処理装置。
（３）前記ラベル変換テーブルは、エントリ番号を有する複数のエントリを備え、
前記ラベル変換テーブル生成部は、前記複数のエントリの各々の前記エントリ番号を前記仮ラベルの値として当該仮ラベルに対応する前記本ラベルを前記エントリに記録する
前記（２）記載の画像処理装置。
（４）前記ラベル変換テーブル生成部は、
前記連結情報における前記仮ラベルから当該仮ラベルと前記連結関係にある前記仮ラベルを辿って前記連結関係のある他の前記仮ラベルを辿れなくなった前記仮ラベルを起点仮ラベルとして決定する起点仮ラベル決定部と、
前記決定された起点仮ラベルについて前記本ラベルを発行する本ラベル発行部と、
前記起点仮ラベルの決定において辿った前記仮ラベルからなる前記集合において当該集合内の前記仮ラベルに対して前記起点仮ラベルについて発行された前記本ラベルを対応付けたテーブルを前記ラベル変換テーブルとして生成するラベル対応関係決定部と
を備える前記（２）または（３）記載の画像処理装置。
（５）検出対象画像において所定の物体を検出して当該検出された物体の領域内の画素との間において座標が一致する前記有効画素を含む画像を前記入力画像として生成する物体検出部をさらに具備する
前記（１）乃至（４）のいずれかに記載の画像処理装置。
（６）所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成手順と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成手順と
を具備する画像処理装置の制御方法。
（７）所定値の画素値を有する画素である有効画素を含む入力画像において所定の順番に従って前記画素に着目して当該着目された画素である現画素が前記有効画素であり、かつ、前記現画素の１つ前に着目された画素である直前画素が前記現画素に隣接する前記有効画素でない場合には新たに発行した識別子を前記現画素の仮ラベルとして前記現画素に割り当てた仮ラベルデータを生成し、前記現画素が前記有効画素であり、かつ、前記直前画素が前記現画素に隣接する前記有効画素である場合には前記直前画素の前記仮ラベルを前記現画素の仮ラベルとして前記現画素に割り当てた前記仮ラベルデータを生成する仮ラベルデータ生成手順と、
前記現画素が前記有効画素である場合には前記現画素に隣接する前記有効画素の前記仮ラベルと前記現画素の前記仮ラベルとを連結関係にある仮ラベルとして対応付けた連結情報を生成する連結情報生成手順と
をコンピュータに実行させるためのプログラム。
【符号の説明】
【０１０２】
１００  画像処理装置
１１０  前処理部
１２０  移動体検出部
１３０  移動体追跡処理部
１４０  後処理部
２００  ラベル付与部
２１０  仮ラベル付与部
２１１  仮ラベルデータ生成部
２１２  連結情報テーブル生成部
２２０  仮ラベルデータ保持部
２３０  連結情報テーブル保持部
２４０  ラベル変換テーブル生成部
２５０  起点本ラベル配列保持部
２６０  ラベル変換テーブル保持部
２７０  本ラベルデータ生成部
２８０  本ラベルデータ保持部
【図１】
2013114278.tif 000003
【図２】
2013114278.tif 000004
【図３】
2013114278.tif 000005
【図４】
2013114278.tif 000006
【図５】
2013114278.tif 000007
【図６】
2013114278.tif 000008
【図７】
2013114278.tif 000009
【図８】
2013114278.tif 000010
【図９】
2013114278.tif 000011
【図１０】
2013114278.tif 000012
【図１１】
2013114278.tif 000013
【図１２】
2013114278.tif 000014
【図１３】
2013114278.tif 000015
【図１４】
2013114278.tif 000016
【図１５】
2013114278.tif 000017
【図１６】
2013114278.tif 000018
【図１７】
2013114278.tif 000019
【図１８】
2013114278.tif 000020
【図１９】
2013114278.tif 000021
【図２０】
2013114278.tif 000022
【図２１】
2013114278.tif 000023
【図２２】
2013114278.tif 000024