(57)【要約】【課題】二値画像上の領域を短時間に抽出するラベリング方法、ラベリング装置、およびラベリングプログラムを提供する。【解決手段】有効画素と非有効画素とで構成されている二値画像の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理段階と、前記第１の処理段階で前記注目画素が選択される度に実行される第２の処理段階であって、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理段階と、を含むラベリング方法。【選択図】図１
2007228139.tif 000002
【特許請求の範囲】
【請求項１】
有効画素と非有効画素とで構成されている二値画像の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理段階と、
前記第１の処理段階で前記注目画素が選択される度に実行される第２の処理段階であって、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理段階と、
を含むラベリング方法。
【請求項２】
前記第１の処理段階において、前記二値画像の上の行の有効画素を全て選択してから下の行の有効画素を選択するとともに、各行においては左から右の順で有効画素を選択し、
前記第２の処理段階において、前記注目画素の右、右下、下および左下にある有効画素のみについて前記設定処理又は前記関連付け処理を実行する請求項１に記載のラベリング方法。
【請求項３】
互いに異なるラベル間の大小関係が規定されており、
前記第１の処理段階において、前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルよりも大きいラベルを前記注目画素に設定し、
前記関連付け処理において、前記有効画素のラベルが前記注目画素のラベルより小さい場合は前記有効画素のラベルを親ラベル、前記注目画素のラベルを子ラベルとして関連付け、前記有効画素のラベルが前記注目画素のラベルより大きい場合は前記注目画素のラベルを親ラベル、前記有効画素のラベルを子ラベルとして関連付ける請求項１又は２に記載のラベリング方法。
【請求項４】
前記関連付け処理において、前記親ラベルが他のラベルに子ラベルとして関連付けられている場合は、前記子ラベルを前記他のラベルに子ラベルとして関連付ける請求項３に記載のラベリング方法。
【請求項５】
前記関連付け処理において、前記子ラベルに他のラベルが子ラベルとして関連付けられている場合は、前記子ラベル及び前記他の子ラベルを前記親ラベルに子ラベルとして関連付ける請求項３又は４に記載のラベリング方法。
【請求項６】
前記関連付け処理において、前記子ラベルが前記親ラベルよりも小さい他のラベルに子ラベルとして関連付けられている場合は、前記親ラベルを前記他のラベルに子ラベルとして関連付ける請求項３、４又は５に記載のラベリング方法。
【請求項７】
有効画素と非有効画素とで構成されている二値画像上の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理手段と、
前記第１の処理手段で前記注目画素が選択されると、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理手段と、
を備えるラベリング装置。
【請求項８】
有効画素と非有効画素とで構成されている二値画像上の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理手段と、
前記第１の処理手段で前記注目画素が選択されると、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理手段としてコンピュータを機能させるラベリングプログラム。
【請求項９】
ディジタル画像から有効画素と非有効画素とで構成されている二値画像を生成する段階と、
前記二値画像に請求項１〜６のいずれか一項に記載のラベリング方法を適用して有効画素にラベルを設定する段階と、
全ての有効画素にラベルを設定した後に実行され、他のラベルと関連付けられていないラベルについては当該ラベルが設定されている有効画素で構成される領域を一つの領域として抽出し、他のラベルと関連付けられているラベルについては関連付けられているラベルが設定されている有効画素で構成される領域を結合した領域を一つの領域として抽出する段階と、
各前記領域の有効画素数を所定の閾値と比較して埃領域を特定する段階と、
前記ディジタル画像の前記埃領域に対応する領域に対して所定の埃除去処理を実行する段階と、
を含むディジタル画像の埃除去方法。
【請求項１０】
前記埃除去処理は、メディアンフィルタを適用する処理である請求項９に記載のディジタル画像の埃除去方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベリング方法、ラベリング装置、ラベリングプログラム、及びディジタル画像の埃除去方法に関する。
【背景技術】
【０００２】
従来、原稿を読み取ってディジタル画像を出力する画像読み取り装置では、読み取りの際に写し込まれた埃をディジタル画像上から除去することができるものが知られている（例えば、特許文献１参照。）。しかしながら、特許文献１の画像読み取り装置によると、作業者が埃を除去する作業を行わなければならいので、作業者にとって負担になるという問題がある。
【０００３】
ところで、従来、ディジタル画像の領域を抽出するラベリング処理が公知である。ラベリング処理を用いて抽出した領域のうち所定の閾値より少ない数の画素で構成されている領域を埃領域とし、埃領域に所定の埃除去処理を実行することにより、作業者の手を煩わすことなく埃を除去することが可能になる。
図１５は、従来のラベリング処理を説明するための模式図である。従来のラベリング処理では、ラベル未設定の有効画素を順に注目画素として選択して他の有効画素のラベルと重複しないラベルを当該注目画素に設定する第１のループと、第１のループで注目画素にラベルが設定される度に実行される第２のループであって当該注目画素の８近傍にあるラベル未設定の有効画素に当該注目画素と同じラベルを設定する第２のループとが実行される。しかしながら、従来のラベリング処理は、第２のループで最初に見つけたラベル未設定の有効画素に注目画素と同じラベルを設定した後、実行中の第２のループを中断し、当該最初に見つけた有効画素を注目画素に設定して新たな第２のループを呼び出している。図１５に示す例では第１のループによってラベルが設定されるのは左上にある有効画素のみであり、他の有効画素は全て第２のループの連鎖によってラベルが設定される。すなわち、従来のラベリング処理は、第２のループから別の第２のループが再帰的に呼び出される多重ループ構造である。一般にループが多重になるほど処理時間が長くなるので、従来のラベリング処理によると処理に長時間を要するという問題がある。
【０００４】
【特許文献１】特開平１１−２９８６６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、上述の問題を解決するために創作されたものであって、二値画像上の領域を短時間に抽出するラベリング方法、ラベリング装置、およびラベリングプログラムを提供することを第１の目的とする。
また、本発明は、ディジタル画像上の埃を短時間に除去する埃除去方法を提供することを第２の目的とする。
【課題を解決するための手段】
【０００６】
（１）上記第１の目的を達成するためのラベリング方法は、有効画素と非有効画素とで構成されている二値画像の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理段階と、前記第１の処理段階で前記注目画素が選択される度に実行される第２の処理段階であって、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理段階と、を含む。
第１の処理段階で注目画素を選択する処理を第１のループ、第２の処理段階で注目画素の８近傍にある有効画素を選択する処理を第２のループというとすると、本発明では第１のループから第２のループが呼び出されるとその第２のループだけが実行されて第１のループに戻る。すなわち本発明では第２のループから第２のループは呼び出されず、ループは最大でも２重までしか多重化されない。従って、ループが３重以上に多重化される場合に比べて処理時間を低減できる。よって本発明によると、二値画像上の領域を短時間に抽出できる。
【０００７】
（２）前記第１の処理段階において、前記二値画像の上の行の有効画素を全て選択してから下の行の有効画素を選択するとともに、各行においては左から右の順で有効画素を選択し、前記第２の処理段階において、前記注目画素の右、右下、下および左下にある有効画素のみについて前記設定処理又は前記関連付け処理を実行してもよい。
本発明によると、第２の処理段階で注目画素の８近傍ではなく４近傍のみについて処理を行えばよいので、第２の処理段階の処理量を低減でき、二値画像上の領域をより短時間に抽出できる。
【０００８】
（３）互いに異なるラベル間の大小関係が規定されており、前記第１の処理段階において、前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルよりも大きいラベルを前記注目画素に設定し、前記関連付け処理において、前記有効画素のラベルが前記注目画素のラベルより小さい場合は前記有効画素のラベルを親ラベル、前記注目画素のラベルを子ラベルとして関連付け、前記有効画素のラベルが前記注目画素のラベルより大きい場合は前記注目画素のラベルを親ラベル、前記有効画素のラベルを子ラベルとして関連付けてもよい。
【０００９】
（４）前記関連付け処理において、前記親ラベルが他のラベルに子ラベルとして関連付けられている場合は、前記子ラベルを前記他のラベルに子ラベルとして関連付けてもよい。
本発明によると、親子関係の階層数を低減できるので、関連付けられているラベルの特定に要する時間を短縮できる。
【００１０】
（５）前記関連付け処理において、前記子ラベルに他のラベルが子ラベルとして関連付けられている場合は、前記子ラベル及び前記他の子ラベルを前記親ラベルに子ラベルとして関連付けてもよい。
本発明によると、親子関係の階層数を低減できるので、関連付けられているラベルの特定に要する時間を短縮できる。
【００１１】
（６）前記関連付け処理において、前記子ラベルが前記親ラベルよりも小さい他のラベルに子ラベルとして関連付けられている場合は、前記親ラベルを前記他のラベルに子ラベルとして関連付けてもよい。
本発明によると、親子関係の階層数を低減できるので、関連付けられているラベルの特定に要する時間を短縮できる。
【００１２】
（７）上記第１の目的を達成するためのラベリング装置は、有効画素と非有効画素とで構成されている二値画像上の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理手段と、前記第１の処理手段で前記注目画素が選択されると、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理手段と、を備える。
本発明によると、二値画像上の領域を短時間に抽出できる。
【００１３】
（８）上記第１の目的を達成するためのラベリングプログラムは、有効画素と非有効画素とで構成されている二値画像上の有効画素を順に注目画素として選択し、選択した前記注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを前記注目画素に設定する第１の処理手段と、前記第１の処理手段で前記注目画素が選択されると、前記注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に前記注目画素と同じラベルを設定する設定処理を実行し、前記注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと前記注目画素のラベルとを関連付ける関連付け処理を実行する第２の処理手段としてコンピュータを機能させる。
本発明によると、二値画像上の領域を短時間に抽出できる。
【００１４】
（９）上記第２の目的を達成するためのディジタル画像の埃除去方法は、ディジタル画像から有効画素と非有効画素とで構成されている二値画像を生成する段階と、前記二値画像に請求項１〜６のいずれか一項に記載のラベリング方法を適用して有効画素にラベルを設定する段階と、全ての有効画素にラベルを設定した後に実行され、他のラベルと関連付けられていないラベルについては当該ラベルが設定されている有効画素で構成される領域を一つの領域として抽出し、他のラベルと関連付けられているラベルについては関連付けられているラベルが設定されている有効画素で構成される領域を結合した領域を一つの領域として抽出する段階と、各前記領域の有効画素数を所定の閾値と比較して埃領域を特定する段階と、前記ディジタル画像の前記埃領域に対応する領域に対して所定の埃除去処理を実行する段階と、を含む。
本発明によると、領域を短時間に抽出できるので、ディジタル画像上の埃を短時間に除去できる。
【００１５】
（１０）前記埃除去処理は、メディアンフィルタを適用する処理であってもよい。
本発明によると、メディアンフィルタを適用するので、埃を目立たなくできる。
【００１６】
尚、本発明に備わる複数の手段の各機能は、構成自体で機能が特定されるハードウェア資源、プログラムにより機能が特定されるハードウェア資源、又はそれらの組み合わせにより実現される。また、これら複数の手段の各機能は、各々が物理的に互いに独立したハードウェア資源で実現されるものに限定されない。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施の形態を実施例に基づいて説明する。
図２は、本発明の一実施例に係るラベリング装置としてのパーソナルコンピュータ（ＰＣ）１０のハードウェア構成を示すブロック図である。ＰＣ１０は、ＣＰＵ１１、ＲＯＭ１２、ＲＡＭ１３、ディスプレイコントローラ１４、インタフェース部１５、リムーバブルメモリコントローラ（ＲＭＣ）１６、外部記憶部１７、および操作部１８を備え、これらはバス１９で相互に接続されている。
【００１８】
ＣＰＵ１１はＲＯＭ１２や外部記憶部１７に記憶されているプログラムを実行してＰＣ１０の全体を制御する。本実施例ではディジタル画像の埃を除去するための埃除去プログラムがスキャナドライバの一部として実装されており、ラベリングプログラムは埃除去プログラムの一部として実装されている。ＣＰＵ１１はスキャナドライバを実行することによって第１の処理手段、および第２の処理手段としても機能する。ＲＯＭ１２は各種のプログラムやデータを予め記憶しているメモリであり、ＲＡＭ１３は各種のプログラムやデータを一時的に記憶するメモリである。これら各種のプログラムやデータは所定のサーバから通信ネットワークを介してダウンロードして入力してもよいし、リムーバブルメモリなどから読み出して入力してもよい。
【００１９】
ディスプレイコントローラ１４は、ＣＰＵ１１に制御され、ＣＲＴ（Cathode Ray Tube）、ＬＣＤ（Liquid Crystal Display）、ＦＰＤ（Flat Panel Display）などのディスプレイ２０にディジタル画像を表示させる。
インタフェース部１５は、イメージスキャナ２２などの外部システムと通信するためのＵＳＢコントローラ、ＵＳＢコネクタなどを備える。通信規格はＵＳＢに限らず、ＩＥＥＥ１３９４、赤外線、イーサネット（登録商標）などのいかなる規格でもよい。
【００２０】
ＲＭＣ１６は、図示しないコネクタを介してリムーバブルメモリに接続され、リムーバブルメモリとＲＡＭ１３との間でデータ転送を制御する。リムーバブルメモリはカード型フラッシュメモリ（所謂メモリカード）でもよいし、その他の繰り返し書き込み可能ないかなる不揮発性記憶媒体であってもよい。
外部記憶部１７は、ハードディスクやハードディスクコントローラなどで構成され、オペレーティングシステム（ＯＳ）、スキャナドライバ、その他各種のプログラムやデータなどが記憶されている。
操作部１８は、キーボード２１が接続されるキーボードコントローラや図示しないマウスが接続されるマウスコントローラなどで構成されている。
【００２１】
次に、ラベリング処理について説明する。
図１は、ラベリング処理を説明するための模式図である。二値画像はディジタル画像の輝度成分に基づいて生成したエッジ画像の各画素値を所定の閾値と比較することにより、画素値が所定の閾値以上である有効画素と画素値が所定の閾値未満である非有効画素とに二値化した画像である。例えば有効画素には画素値として１が設定されており、非有効画素には画素値として０が設定されている。
【００２２】
ラベリング処理では、先ず第１の処理が実行される。第１の処理は、二値画像の有効画素を順に注目画素として選択し、選択した注目画素にラベルが設定されていない場合は他の有効画素に設定されているラベルと重複しないラベルを注目画素に設定する処理である。ここでラベルとは、本実施例では１から昇順に選択される整数のことをいい、例えば１〜５までが既に他の有効画素に設定されている場合は６が次のラベルとして選択される。本実施例の第１の処理では上の行の有効画素を全て選択してから下の行の有効画素を選択するとともに、各行においては左から右の順で有効画素を選択するものとする。
【００２３】
図１の（１）に示すように、最初は有効画素（０，０）が注目画素として選択される。選択された注目画素（０，０）には他の有効画素のラベルと重複しないラベルである「１」が設定されるとともに、図３（Ａ）に示すようにラベル管理テーブルにラベル「１」が登録される。このときラベル管理テーブルの「ラベル数」列にはラベル「１」が設定されている画素の数である１が登録される。
【００２４】
第１の処理で注目画素が選択されると、その度に第２の処理が実行される。第２の処理は、注目画素の８近傍にある有効画素について、ラベルが設定されていない有効画素については当該有効画素に注目画素と同じラベルを設定する設定処理を実行し、注目画素のラベルとは異なるラベルが設定されている有効画素については当該有効画素のラベルと注目画素のラベルとを関連付ける関連付け処理を実行する処理である。ここで本実施例では関連付け処理のことをラベル親子関係登録処理というものとする。
【００２５】
ただし、本実施例では８近傍ではなく注目画素の右、右下、下および左下にある有効画素のみについて設定処理又はラベル親子関係登録処理を実行する。これは前述した第１の処理が上の行の有効画素を全て選択してから下の行の有効画素を選択するとともに、各行においては左から右の順で有効画素を選択するからである。このような順で有効画素が選択される場合、右、右下、下および左下にある有効画素のみに対して設定処理又はラベル親子関係登録処理を実行するだけで、設定処理又はラベル親子関係登録処理が実行されるべき有効画素に対して設定処理又はラベル親子関係登録処理をもれなく実行できる。８近傍ではなく右、右下、下および左下にある４近傍の有効画素のみに対して処理を実行するようにすると、注目画素の４近傍にある画素のみについてその画素が有効画素であるか否かを判定すればよいので、８近傍にある画素についてそれぞれ有効画素であるか否かを判定する場合に比べて判定すべき画素数を半減できる。これにより、従来のラベリング処理に比べて処理速度が大幅に向上する。
【００２６】
図１の（１）に示す例の場合、注目画素（０，０）の下にラベル未設定の有効画素（０，１）があるので、図１の（２）に示すように有効画素（０，１）に注目画素（０，０）と同じラベル「１」が設定され、図３（Ｂ）に示すようにラベル管理テーブルのラベル「１」が登録されている行の「ラベル数」列に１が加算される。
【００２７】
図１の（１）に示す例の場合、注目画素（０，０）の右、右下、下および左下には注目画素（０，０）に設定されているラベル「１」と異なるラベルが設定されている有効画素はないので、ラベル親子関係登録処理は実行されない。
次に、第１の処理に戻り、図１の（３）に示すように有効画素（２，０）が次の注目画素として選択される。選択された注目画素（２，０）にはラベルが設定されていないので、他のいずれの有効画素のラベルとも重複しないラベルである「２」が設定されるとともに、図３（Ｃ）に示すようにラベル管理テーブルにラベル「２」が登録される。
【００２８】
次に、注目画素（２，０）に対する第２の処理が実行される。図１の（３）に示す例の場合、注目画素（２，０）の下にラベルが設定されていない有効画素（２，１）があるので、図１の（４）に示すように有効画素（２，１）に注目画素（２，０）と同じラベル「２」が設定され、図３（Ｄ）に示すようにラベル管理テーブルのラベル「２」が登録されている行の「ラベル数」列に１が加算される。
【００２９】
図１の（３）に示す例の場合、注目画素（２，０）の右、右下、下および左下には注目画素（２，０）に設定されているラベル「２」よりも小さいラベルが設定されている画素はないので、ラベル親子関係登録処理は実行されない。
途中省略して、第１の処理に戻って図１の（５）に示すように有効画素（８，０）が注目画素として選択されると、選択された注目画素（８，０）には他の有効画素のラベルと重複しないラベルである「５」が設定されるとともに、図３（Ｅ）に示すようにラベル管理テーブルにラベル「５」が登録される。
【００３０】
次に、注目画素（８，０）に対する第２の処理が実行される。図１の（５）の場合、注目画素（８，０）の下にラベル未設定の有効画素（８，１）があるので、有効画素（８，１）に注目画素（８，０）と同じラベル「５」が設定され、図３（Ｆ）に示すようにラベル管理テーブルのラベル「５」が登録されている行の「ラベル数」列に１が加算される。
【００３１】
図１の（５）に示す例の場合、注目画素（８，０）の左下には注目画素（８，０）のラベル「５」よりも小さいラベル「４」が設定されている有効画素（７，１）があるので、ラベル「４」にラベル「５」を子として登録するラベル親子関係登録処理が実行される。具体的には、図３（Ｆ）に示すようにラベル管理テーブルのラベル「４」が登録されている行の「子ラベル番号数」列に１が加算されるとともに、当該行の「子ラベル番号」列にラベル「５」が登録される。
【００３２】
途中省略して、第１の処理に戻って図１の（６）に示すようにラベル「２」が設定されている有効画素（２，１）が注目画素として選択されると、注目画素（２，１）に対する第２の処理が実行される。
図１の（６）に示す例の場合、注目画素（２，１）の下にあるラベル未設定の有効画素（２，２）、および右下にあるラベル未設定の有効画素（３，２）に注目画素（２，１）と同じラベル「２」がそれぞれ設定され、図３（Ｇ）に示すようにラベル管理テーブルのラベル「２」が登録されている行の「ラベル数」列に２が加算される。
【００３３】
図１の（６）に示す例の場合、注目画素（２，１）の左下には注目画素（２，１）のラベル「２」よりも小さいラベル「１」が設定されている有効画素（１，２）があるので、ラベル「１」にラベル「２」を子として登録するラベル親子関係登録処理が実行される。具体的には、図３（Ｇ）に示すようにラベル管理テーブルのラベル「１」が登録されている行の「子ラベル番号数」列に１が加算されるとともに、当該行の「子ラベル番号」列にラベル「２」が登録される。
【００３４】
次に、第１の処理に戻って図１の（７）に示すようにラベル「３」が設定されている有効画素（４，１）が注目画素として選択されると、注目画素（４，１）に対する第２の処理が実行される。
図１の（６）に示すように注目画素（４，１）の下にラベル未設定の有効画素（４，２）があるので、図１の（７）に示すように有効画素（４，２）に注目画素（４，１）と同じラベル「３」が設定され、図４（Ｈ）に示すようにラベル管理テーブルのラベル「３」が登録されている行の「ラベル数」列に１が加算される。
【００３５】
また、図１の（７）に示す例の場合、注目画素（４，１）の左下には注目画素（４，１）のラベル「３」よりも小さいラベル「２」が設定されている有効画素（３，２）があるので、ラベル「２」にラベル「３」を子として登録するラベル親子関係登録処理が実行される。ただし、前述したようにラベル「２」はラベル「１」の子として登録されている。この場合、ラベル「３」はラベル「２」の子ではなくラベル「１」の子として登録される。具体的には、図４（Ｈ）に示すようにラベル管理テーブルのラベル「１」が登録されている行の「子ラベル番号数」列に１が加算されるとともに、当該行の「子ラベル番号」列にラベル「３」が登録される。これにより親子関係の階層数を低減できるので、関連付けられているラベルの特定に要する時間を短縮できる。
【００３６】
途中省略して、有効画素（４，２）までが注目画素として選択された結果を図１の（８）および図４（Ｊ）に示す。
次に、第１の処理で図１の（９）に示すようにラベル「４」が設定されている有効画素（６，２）が注目画素として選択されると、注目画素（６，２）に対する第２の処理が実行される。
【００３７】
図１の（８）に示すように注目画素（６，２）の下にはラベル未設定の有効画素（６，３）があるので、図１の（９）に示すように有効画素（６，３）に注目画素（６，２）と同じラベル「４」が設定され、図４（Ｋ）に示すようにラベル管理テーブルのラベル「４」が登録されている行の「ラベル数」列に１が加算される。
【００３８】
また、図１の（９）に示す例の場合、注目画素（６，２）の左下には注目画素（６，２）のラベル「４」よりも小さいラベル「３」が設定されている有効画素（５，３）があるので、ラベル「３」にラベル「４」を子として登録するラベル親子関係登録処理が実行される。ただし、前述したようにラベル「３」はラベル「１」の子として登録されているので、ラベル「４」はラベル「３」ではなくラベル「１」の子として登録される。具体的には、ラベル管理テーブルのラベル「１」が登録されている行の「子ラベル番号数」列に１が加算されるとともに、当該行の「子ラベル番号」列にラベル「４」が登録される。これにより親子関係の階層数を低減できるので、関連付けられているラベルの特定に要する時間を短縮できる。
【００３９】
また、前述したようにラベル「５」はラベル「４」の子として登録されているので、ラベル「５」はラベル「１」の子として登録し直され、ラベル「４」は子ラベルが登録されていない状態に戻される。具体的には、ラベル管理テーブルのラベル「４」が登録されている行の「子ラベル番号数」列に登録されている値、および「子ラベル番号」列に登録されている番号が、図４（Ｋ）に示すようにラベル「１」が登録されている行にそれぞれ移される。これにより親子関係の階層数をより低減できるので、関連付けられているラベルの特定に要する時間をより短縮できる。
【００４０】
次に、第１の処理に戻って図１の（１０）に示すようにラベル「３」が設定されている有効画素（５，３）が注目画素として選択されると、注目画素（５，３）に対する第２の処理が実行される。
図１の（９）に示すように注目画素（５，３）の右下にラベル未設定の有効画素（６，４）があるので、図１の（１０）に示すように有効画素（６，４）に注目画素（５，３）と同じラベル「３」が設定され、図４（Ｌ）に示すようにラベル管理テーブルのラベル「３」が登録されている行の「ラベル数」列に１が加算される。
【００４１】
図１の（１０）に示す例の場合、注目画素（５，３）の右にラベル「４」が設定されている有効画素（６，３）があるが、ラベル「４」は既にラベル「３」の親であるラベル
「１」の子として登録されているので、ラベル親子関係登録処理では何も行われずに処理が終了する。
【００４２】
次に、第１の処理に戻ってラベル「４」が設定されている有効画素（６，３）が注目画素として選択されると、注目画素（６，３）に対する第２の処理が実行される。
図１の（１０）に示す例の場合、注目画素（６，３）の近傍にはラベル未設定の有効画素はないので近傍の画素にラベルを設定する処理は実行されない。
【００４３】
また、ラベル「４」が設定されている有効画素（６，３）の下にラベル「３」が設定されている有効画素（６，４）があるが、ラベル「４」は既にラベル「３」の親であるラベル「１」の子として登録されているので、ラベル親子関係登録処理では何も行われずに処理が終了する。
途中省略して、二値画像に対するラベリング処理が終了した結果を図１の（１１）および図４（Ｍ）に示す。
【００４４】
次に、本発明の一実施例に係るラベリング方法を用いたディジタル画像の埃除去について説明する。
図５および図６は、ＰＣ１０が実行するディジタル画像の埃除去処理の流れを示すフローチャートである。
Ｓ１０５では、ＣＰＵ１１はイメージスキャナ２２からディジタル画像を取得する。
【００４５】
Ｓ１１０では、ＣＰＵ１１はイメージスキャナ２２から取得したディジタル画像のエッジ画像を生成する。
Ｓ１１５では、ＣＰＵ１１はエッジ画像の各画素値を所定の閾値と比較して二値画像を生成する。
Ｓ１２０では、ＣＰＵ１１は二値画像から画素を一つ選択する。
【００４６】
Ｓ１２５では、ＣＰＵ１１は選択した画素が有効画素であるかを判定する。ＣＰＵ１１は選択した画素が有効画素であればその画素を注目画素にしてＳ１３０に進み、有効画素でなければＳ１４５に進む。
Ｓ１３０では、ＣＰＵ１１は注目画素にラベルが設定されているか否かを判定し、ラベルが設定されていない場合はＳ１３５に進み、設定されている場合はＳ１４０に進む。
【００４７】
Ｓ１３５では、ＣＰＵ１１は注目画素に他のいずれの有効画素とも重複しないラベルを設定する。
Ｓ１４０では、ＣＰＵ１１は注目画素に対する第２の処理を実行する。以下、第２の処理について説明する。
【００４８】
図７および図８は、第２の処理の流れを示すフローチャートである。
Ｓ２０５では、ＣＰＵ１１は注目画素の右、左下、下および右下にある画素を一つ選択する。
Ｓ２１０では、ＣＰＵ１１は選択した画素が有効画素であるかを判定し、有効画素であればＳ２１５に進み、有効画素でなければＳ２４５に進む。
Ｓ２１５では、ＣＰＵ１１は選択した有効画素にラベルが設定されているかを判定し、ラベル未設定であればＳ２２０に進み、既にラベルが設定されている場合はＳ２２５に進む。
【００４９】
Ｓ２２０では、ＣＰＵ１１は選択した有効画素に対する設定処理を実行する。具体的には、ＣＰＵ１１は選択した有効画素に注目画素と同じラベルを設定するとともに、ラベル管理テーブルにおいて当該注目画素に設定されているラベルが登録されている行の「ラベル数」列に１を加算する。
Ｓ２２５では、ＣＰＵ１１は選択した有効画素に設定されているラベルが注目画素に設定されているラベルより小さいかを判定し、小さい場合はＳ２３０に進み、それ以外の場合はＳ２３５に進む。
【００５０】
Ｓ２３０では、ＣＰＵは有効画素のラベルを親ラベル、注目画素のラベルを子ラベルとしてラベル親子関係登録処理を実行する。以下、ラベル親子関係登録処理について説明する。
【００５１】
図９および図１０は、ラベル親子関係登録処理の流れを示すフローチャートである。
Ｓ３０５では、ＣＰＵ１１は当該親ラベルと当該子ラベルとの親子関係が既に登録されているかを判定する。具体的には、ＣＰＵ１１はラベル管理テーブルにおいて親ラベルが登録されている行の「子ラベル番号」列に当該子ラベルが既に登録されていれば登録済みと判定する。また、ＣＰＵ１１は、親ラベルが他のラベルの子として登録されており、子ラベルも当該他のラベルの子として登録されていれば登録済みと判定する。ＣＰＵ１１は登録されていなければＳ３１０に進み、登録済みであればラベル親子関係登録処理を終了して戻る。
【００５２】
Ｓ３１０では、ＣＰＵ１１は親ラベルが他のラベルの子として登録されているかを判定する。ＣＰＵ１１は親ラベルが他のラベルの子として登録されていればＳ３１５に進み、親ラベルが他のラベルの子として登録されていなければＳ３３０に進む。
Ｓ３１５では、ＣＰＵ１１は子ラベルを当該他のラベルの子としてラベル管理テーブルに登録する。具体的には、ＣＰＵ１１は当該他のラベルが登録されている行の「子ラベル番号数」列に１を加算するとともに、当該行の「子ラベル番号」列に子ラベルの番号を登録する。
【００５３】
Ｓ３２０では、ＣＰＵ１１は子ラベルに他のラベルが子として登録されているかを判定する。具体的には、ＣＰＵ１１はラベル管理テーブルにおいて子ラベルが登録されている行の「子ラベル番号数」列の値が１以上であれば他のラベルが子として登録されていると判定する。ＣＰＵ１１は子ラベルに他のラベルが子として登録されている場合はＳ３２５に進み、子ラベルに他のラベルが子として登録されていない場合はラベル親子関係登録処理を終了して戻る。
【００５４】
Ｓ３２５では、ＣＰＵ１１は子ラベルに登録されている他の子ラベルを親ラベルの子として再登録する。具体的には、ＣＰＵ１１はラベル管理テーブルにおいて子ラベルが登録されている行の「子ラベル番号数」列に登録されている値、および「子ラベル番号」列に登録されている番号を、親ラベルが登録されている行にそれぞれ移す。
【００５５】
Ｓ３３０では、ＣＰＵ１１は子ラベルが親ラベルより小さい他のラベルの子として登録されているかを判定する。ＣＰＵ１１は子ラベルが親ラベルより小さい他のラベルの子として登録されていればＳ３３５に進み、登録されていなければＳ３４０に進む。
Ｓ３３５では、ＣＰＵは親ラベルを当該他のラベルの子として登録する。ここでＳ３３５が実行されるケースを図１１に示す。図１１において有効画素（１，２）が注目画素として選択された場合、ラベル「２」が親、ラベル「３」が子となってラベル親子関係登録処理が実行される。この場合、子ラベル「３」は親ラベル「２」よりも小さい他のラベル「１」の子として既に登録されているはずなので、Ｓ３３５において親ラベル「２」が他のラベル「１」の子として登録されることになる。これにより親子関係の階層数をより低減できるので、関連付けられているラベルの特定に要する時間をより短縮できる。
Ｓ３４０では、ＣＰＵは子ラベルを親ラベルの子として登録する。
【００５６】
図８に示す第２の処理に戻って、Ｓ２３５では、ＣＰＵ１１は選択した有効画素に設定されているラベルが注目画素に設定されているラベルより大きいかを判定し、大きい場合はＳ２４０に進み、それ以外の場合はＳ２４５に進む。
Ｓ２４０では、ＣＰＵは注目画素のラベルを親、有効画素のラベルを子としてラベル親子関係登録処理を実行する。
Ｓ２４５では、ＣＰＵ１１は右、左下、下および右下にある画素の選択が終了したかを判定し、選択が終了していれば処理を終了し、選択が終了していなければＳ２０５に戻って選択が終了するまで処理を繰り返す。
【００５７】
図５に示す第１の処理に戻って、Ｓ１４５では、ＣＰＵ１１は二値画像の全ての画素の選択が終了したかを判定し、選択が終了していれば図６に示すＳ１５０に進み、選択が終了していなければＳ１２０に戻って選択が終了するまで処理を繰り返す。Ｓ１２０〜Ｓ１４５は特許請求の範囲に記載の「第１の処理段階」に相当する。
【００５８】
Ｓ１５０では、ＣＰＵ１１はラベル管理テーブルを再構築するラベル親子関係再構築処理を実行する。以下、ラベル親子関係再構築処理について説明する。
図１２はラベル親子関係再構築処理の流れを示すフローチャートであり、図１３はラベル親子関係再構築処理を行った後のラベル管理テーブルを示す模式図である。
【００５９】
Ｓ４０５では、ＣＰＵ１１はラベル管理テーブルから「子ラベル番号」列に子ラベル番号が登録されている行を一つ選択する。
Ｓ４１０では、ＣＰＵ１１は選択した行の「ラベル数」列に登録されているラベル数と、選択した行の「子ラベル番号」列に登録されている各子ラベル番号が登録されている行の「ラベル数」列に登録されているラベル数を合計する。
【００６０】
Ｓ４１５では、ＣＰＵ１１は選択した行の「ラベル数」列、および選択した行の「子ラベル番号」列に登録されている各子ラベル番号が登録されている行の「ラベル数」列に、Ｓ４１０で求めた合計をそれぞれ登録する。
Ｓ４２０では、ＣＰＵ１１はラベル管理テーブルから「子ラベル番号」列に子ラベル番号が登録されている全ての行の選択が終了したかを判定し、終了していなければ選択が終了するまで処理を繰り返し、選択が終了していればラベル親子関係再構築処理を終了する。ラベル親子関係再構築処理を行うと、有効領域判定時に毎回ラベル数の加算をしなくてよくなる。
【００６１】
図６に示す第１の処理に戻って、Ｓ１５５では、ＣＰＵ１１は第３の処理を実行する。具体的には、ＣＰＵ１１は他のラベルと関連付けられていないラベルについては当該ラベルが設定されている有効画素で構成される領域を一つの領域として抽出し、他のラベルと関連付けられているラベルについては関連付けられているラベルが設定されている有効画素で構成される領域を結合した領域を一つの領域として抽出する。例えば図１の（１１）に示す例の場合、図１４に示すように３つの領域３１、３２および３３が抽出される。
【００６２】
Ｓ１６０では、ＣＰＵ１１は各領域の有効画素数を所定の閾値と比較して埃領域を特定する。具体的には例えば、ＣＰＵ１１は再構築処理されたラベル管理テーブルでラベル番号を順に選択し、選択したラベル番号の「ラベル数」列に登録されている値が所定の閾値未満であれば当該ラベルが設定されている有効画素で構成される領域は埃領域であると特定する。
【００６３】
Ｓ１６５では、ＣＰＵ１１はディジタル画像において埃領域に対応する領域に対して所定の埃除去処理を実行する。具体的には例えば、ＣＰＵ１１は埃領域に対応する領域に対して公知のメディアンフィルタを適用する。メディアンフィルタは周辺の画素値から突出して大きい画素値または突出して小さい画素値によって生じるノイズの除去能力に優れたフィルタである。
【００６４】
以上説明した本発明の一実施例に係るラベリング方法によると、Ｓ１２０〜Ｓ１４５を第１のループ、Ｓ２０５〜Ｓ２４５を第２のループというとすると、第１のループから第２のループが呼び出されるとその第２のループだけが実行されて第１のループに戻る。すなわち本実施例では第２のループから第２のループが呼び出されず、ループは最大でも２重までしか多重化されない。従って、ループが３重以上に多重化される場合に比べて処理時間を低減できる。よって本発明によると、二値画像上の領域を短時間に抽出できる。
【００６５】
なお、本発明は、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲で種々の実施形態に適用可能である。
【図面の簡単な説明】
【００６６】
【図１】本発明の一実施例に係るラベリング処理を説明するための模式図。
【図２】本発明の一実施例に係るラベリング装置のブロック図。
【図３】本発明の一実施例に係るラベル管理テーブルを示す模式図。
【図４】本発明の一実施例に係るラベル管理テーブルを示す模式図。
【図５】本発明の一実施例に係るフローチャート。
【図６】本発明の一実施例に係るフローチャート。
【図７】本発明の一実施例に係るフローチャート。
【図８】本発明の一実施例に係るフローチャート。
【図９】本発明の一実施例に係るフローチャート。
【図１０】本発明の一実施例に係るフローチャート。
【図１１】本発明の一実施例に係るラベリング処理を説明するための模式図。
【図１２】本発明の一実施例に係るフローチャート。
【図１３】本発明の一実施例に係るラベル管理テーブルを示す模式図。
【図１４】本発明の一実施例に係る二値画像の模式図。
【図１５】従来のラベリング処理を説明するための模式図。
【符号の説明】
【００６７】
１１  ＣＰＵ（第１の処理手段、第２の処理手段）、１０  パーソナルコンピュータ（ラベリング装置）
【図１】
2007228139.tif 000003
【図２】
2007228139.tif 000004
【図３】
2007228139.tif 000005
【図４】
2007228139.tif 000006
【図５】
2007228139.tif 000007
【図６】
2007228139.tif 000008
【図７】
2007228139.tif 000009
【図８】
2007228139.tif 000010
【図９】
2007228139.tif 000011
【図１０】
2007228139.tif 000012
【図１１】
2007228139.tif 000013
【図１２】
2007228139.tif 000014
【図１３】
2007228139.tif 000015
【図１４】
2007228139.tif 000016
【図１５】
2007228139.tif 000017