領域成長法によるラベリングの高速化
【課題】領域成長法を用いたラベリング処理を高速化する。
【解決手段】入力画像メモリと、近傍画素から処理対象画素と同一のラベルが付与される条件を満たす画素を探索する同一ラベル画素探索部と、前記同一ラベル画素探索部から出力される連結対象画素の位置情報を記録する連結画素情報保持部と、処理対象画像の全画素について「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新部と、「ラベル付与済み画素フラグ」からプライオリティエンコーダにより次にラベルを付与する画素候補の位置情報を１つ選択して出力するラベル付与画素候補選択部と、前記連結画素情報保持部で保持される連結画素の情報と前記ラベル付与画素候補選択部の出力情報から次にラベルを付与する処理対象の画素と次のラベル番号とを決定するラベル付与制御部と、画素位置とラベル番号を基に各々の画素のラベル番号を書き込む出力ラベルメモリとを有する。
【解決手段】入力画像メモリと、近傍画素から処理対象画素と同一のラベルが付与される条件を満たす画素を探索する同一ラベル画素探索部と、前記同一ラベル画素探索部から出力される連結対象画素の位置情報を記録する連結画素情報保持部と、処理対象画像の全画素について「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新部と、「ラベル付与済み画素フラグ」からプライオリティエンコーダにより次にラベルを付与する画素候補の位置情報を１つ選択して出力するラベル付与画素候補選択部と、前記連結画素情報保持部で保持される連結画素の情報と前記ラベル付与画素候補選択部の出力情報から次にラベルを付与する処理対象の画素と次のラベル番号とを決定するラベル付与制御部と、画素位置とラベル番号を基に各々の画素のラベル番号を書き込む出力ラベルメモリとを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域成長法を用いたラベリング処理装置に関する。
【背景技術】
【０００２】
一般に、ラベリング処理を行う場合に領域成長法又はラスタ走査型の方法を用いることでラベリング処理を実現する。ラスタ走査型では１回目の画像をスキャンする段階で、各画素に対して仮のラベル番号を付与して仮ラベル間の連結情報を生成し格納する。その後２回目のスキャン処理において、１回目のスキャン処理で作成した仮ラベル間の連結情報を基に各画素に対して仮ラベルの書き換えを行い、ここで書き換えたラベルを本ラベルとして扱う。それに対して、領域成長法によるラベリング処理では、現在の処理対象の画素と同一のラベル番号が付与される条件を満たす画素を辿っていく（同一ラベル番号が付与される領域を成長させていく）処理を行うことでラベリング処理を実施する（例えば、特許文献１参照）。
【０００３】
特許文献１の概要は、同一ラベル番号が付与される領域を横方向に限定して行うことで、スタック処理のオーバヘッドを削減している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第０３８４００２５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
領域成長法によるラベリング処理において、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を設けると共に、該フラグからラベル未付与画素を検出するプライオリティエンコーダを設ける。これにより、ラベル付け始点画素を最短１サイクルで選択することが可能となり、ラベリング処理の高速化を図ることができる。
【０００６】
図５は、従来の領域成長法によるラベリング処理の内容を表している。
【０００７】
図５（A）で示すように、これまでの領域成長法によるラベリング処理では、着目する画素に隣接する画素中に同一ラベル番号が付与される条件を満たす画素がない場合は、１画素ずつラスタ走査してラベル付与済みであるか否かを判定し、次のラベル番号を付与する最初の画素を検出しなければならなかった。そのため、領域成長法によるラベリング処理の処理速度の低下を招くという問題があった。
【０００８】
例えば、図５（A）の（6,0）の画素に３のラベルを付与するためには、（0,0）から（0,5）までの画素に対して順にラスタ走査して、ラベルが付与済みであることを判定した後にラベルを付与することが可能となる。さらに、領域を成長させるため、同一ラベルの複数の隣接画素をラベル付与画素候補として、スタック等に保持しておく必要があるが、分岐画素の数が多くなると、ラベル付き付与画素候補の位置情報を保持するためのスタック数が増加することが想定される。このスタック数の増加により、処理性能上のオーバヘッドや、スタックサイズが画像依存になるためスタックサイズの上限値に対して保証ができないという問題があった。
【課題を解決するための手段】
【０００９】
以上に説明した課題を解決するために、本発明の画像ラベリング装置は、画像をラベル番号が付与された複数の領域に分割するラベリング装置であって、ラベリング対象の画像を格納する画像メモリ、前記画像メモリを参照して、処理対象画素と同一ラベルが付与される条件を満たす画素を近傍内画素から探索しその探索結果から該当する画素が存在すればその対象の画素の位置情報を出力する同一ラベル画素探索手段、ラベル未付与の画素の中からラベル付与対象画素候補の位置を１つ選択して出力するラベル付与画素候補選択手段、処理対象画素と同一のラベルが付与される条件を満たす連結画素の位置情報を保持する連結画素情報保持手段、現在処理対象の画素位置とラベル番号とを出力し、前記同一ラベル画素探索手段の出力と連結画素情報保持手段に登録されている画素の位置情報とラベル付与画素候補選択手段の出力に基づいて、次に処理する画素位置情報と次のラベル番号とを決定するラベル付与制御手段、前記ラベル付与制御手段から出力された画素位置情報とラベル番号とを基に、各々の画素のラベル番号を書き込むラベルメモリを備え、前記ラベル付与画素候補選択手段は、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新手段の出力結果からラベル付与対象画素候補を選択する手段を有する。
【発明の効果】
【００１０】
上記構成によれば、ラベリング済み画素及び同一領域の分岐先画素にフラグを立て、次に処理すべき画素を選択する処理時間を削減することで、従来の領域成長法を用いたラベリング処理に対して、処理を高速化することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態における画像処理装置の構成を示すブロック図である。
【図２】本発明の第１の実施形態におけるプライオリティエンコーダを用いたラベル付与画素候補の位置座標を選択するための構成を示す図である。
【図３】本発明の第１及び第２の実施形態におけるラベリング処理のフローチャートである。
【図４】本発明の第２の実施形態における大画像を処理するにあたりプライオリティエンコーダを用いたラベル付与画素候補の位置座標を選択するための構成を示す図である。
【図５】従来の領域成長法によるラベリング処理の内容を説明する図である。
【発明を実施するための形態】
【００１２】
［実施例１］
以下、添付図面を参照して本発明を実施するための最良の形態を説明する。
【００１３】
図１は、本発明の第1の実施形態におけるラベリング装置の構成を示すブロック図である。図１において、１０１は外部から入力されるラベリング処理対象となる画像データを格納する入力画像メモリ、１０２は入力画像メモリ１０１内の画像データを参照して、近傍画素から処理対象画素と同一のラベルが付与される条件を満たす画素を探索し該画素の位置情報を出力する同一ラベル画素探索部、１０３は前記同一ラベル画素探索部１０２から出力される連結画素の位置情報を保持する連結画素情報保持部、１０４は処理対象画像の各画素についてラベル付与済みであるかどうかを示す「ラベル付与済み画素フラグ」を保持し、ラベル付与処理が実施される毎に「ラベル付与済み画素フラグ」の情報を更新するラベリング済みフラグ更新部、１０５は前記「ラベル付与済み画素フラグ」情報からプライオリティエンコーダにより次にラベルを付与する画素候補の位置情報を１つ選択して出力するラベル付与画素候補選択部、１０６は前記連結画素情報保持部１０３で保持される連結画素の情報と前記ラベル付与画素候補選択部１０５の出力情報から次にラベルを付与する処理対象の画素と次のラベル番号とを決定するラベル付与制御部、１０７は前記ラベル付与制御部１０６から出力された画素位置とラベル番号とを基に各々の画素のラベル番号を書き込む出力ラベルメモリである。
【００１４】
本実施例におけるラベリング処理方法については、図３のフローチャートを用いて説明する。
【００１５】
始めに、以下に示す回路内で持つラベル番号を設定するための変数、及び入力画像メモリ１０１に格納した入力画像の処理対象画素の位置座標を示す変数を初期化する（S３０１）。初期化内容は以下のとおりである。
【００１６】
ラベル番号：label_num = ０
位置座標 ：(x,y) = (0,0)
次に、処理対象となる画素の位置座標情報とラベル番号情報を出力ラベルメモリ１０７が持つ出力ラベルバッファへ出力する（S３０２）。
【００１７】
次に、同一ラベル画素探索部１０２において入力画像メモリ１０１と各々の画素が持つ「ラベル付与済み画素フラグ」を参照して、処理対象画素と同一のラベルを付与する条件を満たす近傍画素の有る無しを判定する。このときの近傍画素は縦、横４方向の４近傍である（S３０３）。
【００１８】
次に、ステップS３０３で４近傍比較を行い処理対象画素と同一のラベル条件を持つ画素が存在した場合、その近傍画素の位置座標を１つ選択し次の処理画素として、この画素の位置座標を以下のように設定し、ステップS３０５へ進む（S３０４）。
【００１９】
次の処理対象画素の位置座標：(next_x, next_y)
ステップS３０５はステップS３０４で選択されなかった残りの近傍画素の位置情報を連結画素情報保持部１０３へ出力する（S３０５）。このとき出力された情報から連結画素情報保持部１０３では連結画素情報を更新する。
【００２０】
ステップS３０５の次はステップS３１１へ進む。
【００２１】
ステップS３１１において、ラベル付与制御部１０６は次の処理対象画素として(next_x, next_y)位置座標情報の画素が選択されたことを、ラベリング済みフラグ更新部１０４に通知する。ラベリング済みフラグ更新部１０４では通知された「ラベル付与済み画素フラグ」の情報に基づき、対象画素がラベル付与済みであるかどうかの情報を更新する（S３１１）。
【００２２】
ラベル付与制御部１０６はステップS３１１で通知した位置座標情報を基に、次の処理対象画素の位置情報(x,y)に、通知した(next_x,next_y)情報を設定する（S３１２）。ステップS３１２の処理が終了後、再度ステップS３０２の作業を開始する。
【００２３】
次にステップS３０３で、ラベル未付与の近傍画素が存在しない場合について説明する。この場合、ステップS３０６へ進み、連結画素情報保持部１０３、及びラベル付与画素候補選択部１０５からの出力情報から、近傍画素以外で同一のラベル条件であり、且つラベル未付与の画素候補が処理対象画像内に存在するかを判定する。このとき、処理対象画素の近傍画素以外で同一のラベル条件を持ち且つラベル未付与の画素が存在する場合はステップS３０７へ、そうでない場合はステップS３０９へ進む（S３０６）。
【００２４】
ステップS３０６からステップS３０７へ進んだ場合、ラベル付与制御部１０６はステップS３０６で決定された画素の位置情報を、次の処理対象画素の位置座標である(next_x, next_y)として設定する（S３０７）。
【００２５】
次に、ラベル付与制御部１０６はステップS３０７で設定した次の処理対象の位置座標情報を、連結画素情報保時部１０３へ通知し、その後ステップS３１１へ進む（S３０８）。このとき連結画素情報保持部１０４では、通知された位置座標情報の画素を、ラベリング付与済みとして情報を更新し、次回のステップS３０６で次の処理対象画素候補選択する際に、本画素を処理対象から外す。
【００２６】
一方、ステップS３０６で条件を満たす画素候補がなく、ステップS３０９へ進んだ場合、ラベル付与制御部１０６はラベル付与画素候補選択部１０５の通知結果から、処理対象となっている画像データ全ての画素にラベルが付与済みかどうかを判定する（S３０９）。
【００２７】
このとき処理対象画像の全画素がラベリング済みであるかどうかの判定条件は、次の処理対象画素の位置座標である、(next_x, next_y) == (0, 0)の条件が成立したかどうかで判定する。上記条件が成立した場合にはステップS３１３へ、そうでない場合はステップS３１０へ進む。
【００２８】
ステップS３０９でステップS３１３へ進んだ場合、ラベル付与制御部１０６は処理対象画像全ての画素にラベリングが付与されたことを外部に通知する（S３１３）。
【００２９】
それに対し、ステップS３０９で全画素中においてラベルが未付与の画素が存在する場合、ステップS３１０へ進む。このときラベル付与制御部１０６は、ラベル付与画素候補選択部１０５から出力された位置情報を、処理対象画素の近傍以外の同一ラベル条件画素として判断し、次の処理対象画素の位置情報に登録する（S３１０）。
【００３０】
図２で示す構成図は、各画素のラベル付与済み情報を保持するバッファと該ラベル付与済み情報を入力とするプライオリティエンコーダを示している。このとき、図２に示すようにラベリング済みフラグ更新部で更新された各画素のラベル付与情報を基に、プライオリティエンコーダは次の処理対象となる画素の位置情報を出力する。そして、連結画素情報保持部１０３で持つ連結画素情報と同一の位置情報を持つ画素に対して、次の処理対象画素として決定する。
【００３１】
このように本実施例によれば、連結画素情報保持部１０３が持つ連結画素情報と、ラベル付与画素候補選択部１０５から出力される、ラベル付与画素候補を選択条件とするプライオリティエンコーダを備える。前記プライオリティエンコーダにより次の処理対象画素の位置を選択することが可能となることで、ラベリング処理を高速化することが可能となる。
【００３２】
［実施例２］
本実施例では、第１の実施形態と異なる部分のみを説明する。
【００３３】
第１の実施例では比較的小さい画像を処理する場合を想定していた。本発明においては、処理対象となる画像サイズが大きい場合についても想定しているため、本実施例では２５６×２５６画素の画像を処理する場合の例について図４を用いて説明する。なお、本実施例は基本的には図３のフローチャートに基づいて処理を行う。
【００３４】
図２に示した実施例１では、各画素の「ラベル付与済み画素フラグ」の情報を記録したバッファと、１つのプライオリティエンコーダにより次のラベル付与対象画素の位置座標を生成していた。
【００３５】
しかし、処理対象の画像サイズが大きい場合に、各画素が持つ「ラベル付与済み画素フラグ」の情報を、全画素並列にプライオリティエンコーダへ入力すると膨大な配線となることは自明である。
【００３６】
そのため、本実施例では図４に示す構成で処理を実現する。前記図４の構成では、各画素の「ラベル付与済み画素フラグ」を、ライン単位で高速アクセスが可能なRAMに保持するものとする。そして、画像を構成するライン単位でライン内の全ての画素がラベル付与済みかどうかを表す、「ライン毎のラベル付与済みフラグ」として保持する。なお、この「ライン毎のラベル付与済みフラグ」は初期状態において全てゼロにリセットされている。そして、該「ライン毎のラベル付与済みフラグ」を基に前段のプライオリティエンコーダで、未だラベル付与されていない画素が存在するラインを選択する。そして、選択されたラインの、「ラベル付与済み画素フラグ」を保持するRAMのアドレスを出力する。このRAMには全画素の情報が記録されている。
【００３７】
上記前段のプライオリティエンコーダで出力されたアドレスに従い、RAMから読み出された「ラベル付与済み画素フラグ」を参照して、後段のプライオリティエンコーダが最終的な処理対象画素の位置座標を出力する。このとき出力された処理対象画素に対して、実際にラベルが付与された当該画素の「ラベル付与済み画素フラグ」は、ラベル付与済みとしてフラグ情報が更新される。
【００３８】
このように本実施例によれば、処理対象の画像サイズが大きい場合に、「ライン毎のラベル付与済みフラグ」を選択条件としたプライオリティエンコーダでラベル付与対象画素の絞込を前処理として行う。そして、前段のプライオリティエンコーダで生成された出力結果から、後段のプライオリティエンコーダが最終的なラベル付与対象画素を決定する。これにより、処理対象の画像サイズが大きい場合でも、小規模なプライオリティエンコーダで処理可能であり、第１の実施形態と同等の処理時間で処理が可能となる。
【００３９】
さらに、１部の処理を以下の処理に置き換えることが可能である。
【００４０】
まず、ＲＡＭから逐次各画素のフラグ情報を読み出し、ラベル未付与画素の有無の判定と、処理対象となるラベル未付与画素の特定を同時に行う。このとき、ラベル未付与画素が有りと判定された場合には、当該フラグ情報の格納アドレスを保持すると共に、特定されたラベル未付与画素に対してラベル付与処理を行う。該ラベル付与処理が終了後、前記保持した格納アドレスから、次のラベル未付与画素の特定や有無の判定を再開する。
【符号の説明】
【００４１】
１０１ 入力画像メモリ
１０２ 同一ラベル画素探索部
１０３ 連結画素情報保持部
１０４ ラベル付与画素候補選択部
１０５ ラベリング済みフラグ更新部
１０６ ラベル付与制御部
１０７ 出力ラベルメモリ
【技術分野】
【０００１】
本発明は、領域成長法を用いたラベリング処理装置に関する。
【背景技術】
【０００２】
一般に、ラベリング処理を行う場合に領域成長法又はラスタ走査型の方法を用いることでラベリング処理を実現する。ラスタ走査型では１回目の画像をスキャンする段階で、各画素に対して仮のラベル番号を付与して仮ラベル間の連結情報を生成し格納する。その後２回目のスキャン処理において、１回目のスキャン処理で作成した仮ラベル間の連結情報を基に各画素に対して仮ラベルの書き換えを行い、ここで書き換えたラベルを本ラベルとして扱う。それに対して、領域成長法によるラベリング処理では、現在の処理対象の画素と同一のラベル番号が付与される条件を満たす画素を辿っていく（同一ラベル番号が付与される領域を成長させていく）処理を行うことでラベリング処理を実施する（例えば、特許文献１参照）。
【０００３】
特許文献１の概要は、同一ラベル番号が付与される領域を横方向に限定して行うことで、スタック処理のオーバヘッドを削減している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第０３８４００２５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
領域成長法によるラベリング処理において、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を設けると共に、該フラグからラベル未付与画素を検出するプライオリティエンコーダを設ける。これにより、ラベル付け始点画素を最短１サイクルで選択することが可能となり、ラベリング処理の高速化を図ることができる。
【０００６】
図５は、従来の領域成長法によるラベリング処理の内容を表している。
【０００７】
図５（A）で示すように、これまでの領域成長法によるラベリング処理では、着目する画素に隣接する画素中に同一ラベル番号が付与される条件を満たす画素がない場合は、１画素ずつラスタ走査してラベル付与済みであるか否かを判定し、次のラベル番号を付与する最初の画素を検出しなければならなかった。そのため、領域成長法によるラベリング処理の処理速度の低下を招くという問題があった。
【０００８】
例えば、図５（A）の（6,0）の画素に３のラベルを付与するためには、（0,0）から（0,5）までの画素に対して順にラスタ走査して、ラベルが付与済みであることを判定した後にラベルを付与することが可能となる。さらに、領域を成長させるため、同一ラベルの複数の隣接画素をラベル付与画素候補として、スタック等に保持しておく必要があるが、分岐画素の数が多くなると、ラベル付き付与画素候補の位置情報を保持するためのスタック数が増加することが想定される。このスタック数の増加により、処理性能上のオーバヘッドや、スタックサイズが画像依存になるためスタックサイズの上限値に対して保証ができないという問題があった。
【課題を解決するための手段】
【０００９】
以上に説明した課題を解決するために、本発明の画像ラベリング装置は、画像をラベル番号が付与された複数の領域に分割するラベリング装置であって、ラベリング対象の画像を格納する画像メモリ、前記画像メモリを参照して、処理対象画素と同一ラベルが付与される条件を満たす画素を近傍内画素から探索しその探索結果から該当する画素が存在すればその対象の画素の位置情報を出力する同一ラベル画素探索手段、ラベル未付与の画素の中からラベル付与対象画素候補の位置を１つ選択して出力するラベル付与画素候補選択手段、処理対象画素と同一のラベルが付与される条件を満たす連結画素の位置情報を保持する連結画素情報保持手段、現在処理対象の画素位置とラベル番号とを出力し、前記同一ラベル画素探索手段の出力と連結画素情報保持手段に登録されている画素の位置情報とラベル付与画素候補選択手段の出力に基づいて、次に処理する画素位置情報と次のラベル番号とを決定するラベル付与制御手段、前記ラベル付与制御手段から出力された画素位置情報とラベル番号とを基に、各々の画素のラベル番号を書き込むラベルメモリを備え、前記ラベル付与画素候補選択手段は、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新手段の出力結果からラベル付与対象画素候補を選択する手段を有する。
【発明の効果】
【００１０】
上記構成によれば、ラベリング済み画素及び同一領域の分岐先画素にフラグを立て、次に処理すべき画素を選択する処理時間を削減することで、従来の領域成長法を用いたラベリング処理に対して、処理を高速化することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態における画像処理装置の構成を示すブロック図である。
【図２】本発明の第１の実施形態におけるプライオリティエンコーダを用いたラベル付与画素候補の位置座標を選択するための構成を示す図である。
【図３】本発明の第１及び第２の実施形態におけるラベリング処理のフローチャートである。
【図４】本発明の第２の実施形態における大画像を処理するにあたりプライオリティエンコーダを用いたラベル付与画素候補の位置座標を選択するための構成を示す図である。
【図５】従来の領域成長法によるラベリング処理の内容を説明する図である。
【発明を実施するための形態】
【００１２】
［実施例１］
以下、添付図面を参照して本発明を実施するための最良の形態を説明する。
【００１３】
図１は、本発明の第1の実施形態におけるラベリング装置の構成を示すブロック図である。図１において、１０１は外部から入力されるラベリング処理対象となる画像データを格納する入力画像メモリ、１０２は入力画像メモリ１０１内の画像データを参照して、近傍画素から処理対象画素と同一のラベルが付与される条件を満たす画素を探索し該画素の位置情報を出力する同一ラベル画素探索部、１０３は前記同一ラベル画素探索部１０２から出力される連結画素の位置情報を保持する連結画素情報保持部、１０４は処理対象画像の各画素についてラベル付与済みであるかどうかを示す「ラベル付与済み画素フラグ」を保持し、ラベル付与処理が実施される毎に「ラベル付与済み画素フラグ」の情報を更新するラベリング済みフラグ更新部、１０５は前記「ラベル付与済み画素フラグ」情報からプライオリティエンコーダにより次にラベルを付与する画素候補の位置情報を１つ選択して出力するラベル付与画素候補選択部、１０６は前記連結画素情報保持部１０３で保持される連結画素の情報と前記ラベル付与画素候補選択部１０５の出力情報から次にラベルを付与する処理対象の画素と次のラベル番号とを決定するラベル付与制御部、１０７は前記ラベル付与制御部１０６から出力された画素位置とラベル番号とを基に各々の画素のラベル番号を書き込む出力ラベルメモリである。
【００１４】
本実施例におけるラベリング処理方法については、図３のフローチャートを用いて説明する。
【００１５】
始めに、以下に示す回路内で持つラベル番号を設定するための変数、及び入力画像メモリ１０１に格納した入力画像の処理対象画素の位置座標を示す変数を初期化する（S３０１）。初期化内容は以下のとおりである。
【００１６】
ラベル番号：label_num = ０
位置座標 ：(x,y) = (0,0)
次に、処理対象となる画素の位置座標情報とラベル番号情報を出力ラベルメモリ１０７が持つ出力ラベルバッファへ出力する（S３０２）。
【００１７】
次に、同一ラベル画素探索部１０２において入力画像メモリ１０１と各々の画素が持つ「ラベル付与済み画素フラグ」を参照して、処理対象画素と同一のラベルを付与する条件を満たす近傍画素の有る無しを判定する。このときの近傍画素は縦、横４方向の４近傍である（S３０３）。
【００１８】
次に、ステップS３０３で４近傍比較を行い処理対象画素と同一のラベル条件を持つ画素が存在した場合、その近傍画素の位置座標を１つ選択し次の処理画素として、この画素の位置座標を以下のように設定し、ステップS３０５へ進む（S３０４）。
【００１９】
次の処理対象画素の位置座標：(next_x, next_y)
ステップS３０５はステップS３０４で選択されなかった残りの近傍画素の位置情報を連結画素情報保持部１０３へ出力する（S３０５）。このとき出力された情報から連結画素情報保持部１０３では連結画素情報を更新する。
【００２０】
ステップS３０５の次はステップS３１１へ進む。
【００２１】
ステップS３１１において、ラベル付与制御部１０６は次の処理対象画素として(next_x, next_y)位置座標情報の画素が選択されたことを、ラベリング済みフラグ更新部１０４に通知する。ラベリング済みフラグ更新部１０４では通知された「ラベル付与済み画素フラグ」の情報に基づき、対象画素がラベル付与済みであるかどうかの情報を更新する（S３１１）。
【００２２】
ラベル付与制御部１０６はステップS３１１で通知した位置座標情報を基に、次の処理対象画素の位置情報(x,y)に、通知した(next_x,next_y)情報を設定する（S３１２）。ステップS３１２の処理が終了後、再度ステップS３０２の作業を開始する。
【００２３】
次にステップS３０３で、ラベル未付与の近傍画素が存在しない場合について説明する。この場合、ステップS３０６へ進み、連結画素情報保持部１０３、及びラベル付与画素候補選択部１０５からの出力情報から、近傍画素以外で同一のラベル条件であり、且つラベル未付与の画素候補が処理対象画像内に存在するかを判定する。このとき、処理対象画素の近傍画素以外で同一のラベル条件を持ち且つラベル未付与の画素が存在する場合はステップS３０７へ、そうでない場合はステップS３０９へ進む（S３０６）。
【００２４】
ステップS３０６からステップS３０７へ進んだ場合、ラベル付与制御部１０６はステップS３０６で決定された画素の位置情報を、次の処理対象画素の位置座標である(next_x, next_y)として設定する（S３０７）。
【００２５】
次に、ラベル付与制御部１０６はステップS３０７で設定した次の処理対象の位置座標情報を、連結画素情報保時部１０３へ通知し、その後ステップS３１１へ進む（S３０８）。このとき連結画素情報保持部１０４では、通知された位置座標情報の画素を、ラベリング付与済みとして情報を更新し、次回のステップS３０６で次の処理対象画素候補選択する際に、本画素を処理対象から外す。
【００２６】
一方、ステップS３０６で条件を満たす画素候補がなく、ステップS３０９へ進んだ場合、ラベル付与制御部１０６はラベル付与画素候補選択部１０５の通知結果から、処理対象となっている画像データ全ての画素にラベルが付与済みかどうかを判定する（S３０９）。
【００２７】
このとき処理対象画像の全画素がラベリング済みであるかどうかの判定条件は、次の処理対象画素の位置座標である、(next_x, next_y) == (0, 0)の条件が成立したかどうかで判定する。上記条件が成立した場合にはステップS３１３へ、そうでない場合はステップS３１０へ進む。
【００２８】
ステップS３０９でステップS３１３へ進んだ場合、ラベル付与制御部１０６は処理対象画像全ての画素にラベリングが付与されたことを外部に通知する（S３１３）。
【００２９】
それに対し、ステップS３０９で全画素中においてラベルが未付与の画素が存在する場合、ステップS３１０へ進む。このときラベル付与制御部１０６は、ラベル付与画素候補選択部１０５から出力された位置情報を、処理対象画素の近傍以外の同一ラベル条件画素として判断し、次の処理対象画素の位置情報に登録する（S３１０）。
【００３０】
図２で示す構成図は、各画素のラベル付与済み情報を保持するバッファと該ラベル付与済み情報を入力とするプライオリティエンコーダを示している。このとき、図２に示すようにラベリング済みフラグ更新部で更新された各画素のラベル付与情報を基に、プライオリティエンコーダは次の処理対象となる画素の位置情報を出力する。そして、連結画素情報保持部１０３で持つ連結画素情報と同一の位置情報を持つ画素に対して、次の処理対象画素として決定する。
【００３１】
このように本実施例によれば、連結画素情報保持部１０３が持つ連結画素情報と、ラベル付与画素候補選択部１０５から出力される、ラベル付与画素候補を選択条件とするプライオリティエンコーダを備える。前記プライオリティエンコーダにより次の処理対象画素の位置を選択することが可能となることで、ラベリング処理を高速化することが可能となる。
【００３２】
［実施例２］
本実施例では、第１の実施形態と異なる部分のみを説明する。
【００３３】
第１の実施例では比較的小さい画像を処理する場合を想定していた。本発明においては、処理対象となる画像サイズが大きい場合についても想定しているため、本実施例では２５６×２５６画素の画像を処理する場合の例について図４を用いて説明する。なお、本実施例は基本的には図３のフローチャートに基づいて処理を行う。
【００３４】
図２に示した実施例１では、各画素の「ラベル付与済み画素フラグ」の情報を記録したバッファと、１つのプライオリティエンコーダにより次のラベル付与対象画素の位置座標を生成していた。
【００３５】
しかし、処理対象の画像サイズが大きい場合に、各画素が持つ「ラベル付与済み画素フラグ」の情報を、全画素並列にプライオリティエンコーダへ入力すると膨大な配線となることは自明である。
【００３６】
そのため、本実施例では図４に示す構成で処理を実現する。前記図４の構成では、各画素の「ラベル付与済み画素フラグ」を、ライン単位で高速アクセスが可能なRAMに保持するものとする。そして、画像を構成するライン単位でライン内の全ての画素がラベル付与済みかどうかを表す、「ライン毎のラベル付与済みフラグ」として保持する。なお、この「ライン毎のラベル付与済みフラグ」は初期状態において全てゼロにリセットされている。そして、該「ライン毎のラベル付与済みフラグ」を基に前段のプライオリティエンコーダで、未だラベル付与されていない画素が存在するラインを選択する。そして、選択されたラインの、「ラベル付与済み画素フラグ」を保持するRAMのアドレスを出力する。このRAMには全画素の情報が記録されている。
【００３７】
上記前段のプライオリティエンコーダで出力されたアドレスに従い、RAMから読み出された「ラベル付与済み画素フラグ」を参照して、後段のプライオリティエンコーダが最終的な処理対象画素の位置座標を出力する。このとき出力された処理対象画素に対して、実際にラベルが付与された当該画素の「ラベル付与済み画素フラグ」は、ラベル付与済みとしてフラグ情報が更新される。
【００３８】
このように本実施例によれば、処理対象の画像サイズが大きい場合に、「ライン毎のラベル付与済みフラグ」を選択条件としたプライオリティエンコーダでラベル付与対象画素の絞込を前処理として行う。そして、前段のプライオリティエンコーダで生成された出力結果から、後段のプライオリティエンコーダが最終的なラベル付与対象画素を決定する。これにより、処理対象の画像サイズが大きい場合でも、小規模なプライオリティエンコーダで処理可能であり、第１の実施形態と同等の処理時間で処理が可能となる。
【００３９】
さらに、１部の処理を以下の処理に置き換えることが可能である。
【００４０】
まず、ＲＡＭから逐次各画素のフラグ情報を読み出し、ラベル未付与画素の有無の判定と、処理対象となるラベル未付与画素の特定を同時に行う。このとき、ラベル未付与画素が有りと判定された場合には、当該フラグ情報の格納アドレスを保持すると共に、特定されたラベル未付与画素に対してラベル付与処理を行う。該ラベル付与処理が終了後、前記保持した格納アドレスから、次のラベル未付与画素の特定や有無の判定を再開する。
【符号の説明】
【００４１】
１０１ 入力画像メモリ
１０２ 同一ラベル画素探索部
１０３ 連結画素情報保持部
１０４ ラベル付与画素候補選択部
１０５ ラベリング済みフラグ更新部
１０６ ラベル付与制御部
１０７ 出力ラベルメモリ
【特許請求の範囲】
【請求項１】
画像をラベル番号が付与された複数の領域に分割するラベリング装置であって、ラベリング対象の画像を格納する画像メモリ、前記画像メモリを参照して、処理対象画素と同一ラベルが付与される条件を満たす画素を近傍内画素から探索しその探索結果から該当する画素が存在すればその対象の画素の位置情報を出力する同一ラベル画素探索手段、ラベル未付与の画素の中からラベル付与対象画素候補の位置を１つ選択して出力するラベル付与画素候補選択手段、処理対象画素と同一のラベルが付与される条件を満たす連結画素の位置情報を保持する連結画素情報保持手段、現在処理対象の画素位置とラベル番号とを出力し、前記同一ラベル画素探索手段の出力と連結画素情報保持手段に登録されている画素の位置情報とラベル付与画素候補選択手段の出力に基づいて、次に処理する画素位置情報と次のラベル番号とを決定するラベル付与制御手段、前記ラベル付与制御手段から出力された画素位置情報とラベル番号とを基に、各々の画素のラベル番号を記憶するラベル画像記憶手段を備え、前記ラベル付与画素候補選択手段は、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新手段の出力結果からラベル付与対象画素候補を選択することを特徴とする画像ラベリング装置。
【請求項２】
前記ラベル付与画素候補選択手段は、所定画素数の画素群が全てラベル付与済みであるか否かを表すラベル付与済み画素群フラグを保持する第１の記憶手段と、前記ラベル付与済み画素群フラグに基づいてラベル付与済み画素群を選択する第1のプライオリティエンコーダと、ラベル付与済み画素フラグを保持し、選択されたラベル付与済み画素群に対応するラベル付与済み画素フラグを出力する第２の記憶手段と、前記第２の記憶手段から出力されたラベル付与済み画素フラグを選択する第２のプライオリティエンコーダから構成されることを特徴とする請求項１に記載の画像ラベリング装置。
【請求項３】
前記連結画素情報保持手段は、現在処理対象の画素と同一のラベルが付与される条件を満たし且つラベル未付与の画素であるか否かを表す同一ラベル画素フラグを保持し、該フラグを選択条件とするプライオリティエンコーダにより画素の位置を出力することを特徴とする請求項１に記載の画像ラベリング装置。
【請求項４】
前記画像メモリはキャッシュメモリであり、前記ラベル付け始点画素候補選択手段から出力される画素位置を基に、キャッシュの読み出しアドレスを制御することを特徴とする請求項１に記載の画像ラベリング装置。
【請求項１】
画像をラベル番号が付与された複数の領域に分割するラベリング装置であって、ラベリング対象の画像を格納する画像メモリ、前記画像メモリを参照して、処理対象画素と同一ラベルが付与される条件を満たす画素を近傍内画素から探索しその探索結果から該当する画素が存在すればその対象の画素の位置情報を出力する同一ラベル画素探索手段、ラベル未付与の画素の中からラベル付与対象画素候補の位置を１つ選択して出力するラベル付与画素候補選択手段、処理対象画素と同一のラベルが付与される条件を満たす連結画素の位置情報を保持する連結画素情報保持手段、現在処理対象の画素位置とラベル番号とを出力し、前記同一ラベル画素探索手段の出力と連結画素情報保持手段に登録されている画素の位置情報とラベル付与画素候補選択手段の出力に基づいて、次に処理する画素位置情報と次のラベル番号とを決定するラベル付与制御手段、前記ラベル付与制御手段から出力された画素位置情報とラベル番号とを基に、各々の画素のラベル番号を記憶するラベル画像記憶手段を備え、前記ラベル付与画素候補選択手段は、各々の画素がラベル付与済みであるか否かを表す「ラベル付与済み画素フラグ」を保持するラベリング済みフラグ更新手段の出力結果からラベル付与対象画素候補を選択することを特徴とする画像ラベリング装置。
【請求項２】
前記ラベル付与画素候補選択手段は、所定画素数の画素群が全てラベル付与済みであるか否かを表すラベル付与済み画素群フラグを保持する第１の記憶手段と、前記ラベル付与済み画素群フラグに基づいてラベル付与済み画素群を選択する第1のプライオリティエンコーダと、ラベル付与済み画素フラグを保持し、選択されたラベル付与済み画素群に対応するラベル付与済み画素フラグを出力する第２の記憶手段と、前記第２の記憶手段から出力されたラベル付与済み画素フラグを選択する第２のプライオリティエンコーダから構成されることを特徴とする請求項１に記載の画像ラベリング装置。
【請求項３】
前記連結画素情報保持手段は、現在処理対象の画素と同一のラベルが付与される条件を満たし且つラベル未付与の画素であるか否かを表す同一ラベル画素フラグを保持し、該フラグを選択条件とするプライオリティエンコーダにより画素の位置を出力することを特徴とする請求項１に記載の画像ラベリング装置。
【請求項４】
前記画像メモリはキャッシュメモリであり、前記ラベル付け始点画素候補選択手段から出力される画素位置を基に、キャッシュの読み出しアドレスを制御することを特徴とする請求項１に記載の画像ラベリング装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１３−１０５３１６（Ｐ２０１３−１０５３１６Ａ）
【公開日】平成２５年５月３０日（２０１３．５．３０）
【国際特許分類】
【出願番号】特願２０１１−２４８６５０（Ｐ２０１１−２４８６５０）
【出願日】平成２３年１１月１４日（２０１１．１１．１４）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年５月３０日（２０１３．５．３０）
【国際特許分類】
【出願日】平成２３年１１月１４日（２０１１．１１．１４）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]