(57)【要約】【課題】  従来において１回の画像走査では、斜めに連結した画素成分の特徴量を計測できない。【解決手段】  特徴量とマージ回数を格納する特徴量テーブルと、特徴量テーブルのインデックスを格納する特徴量ポインタテーブルとを用い、特徴量計測を行う注目画素を含むウインドウ内の画素を参照し、注目画素以外で、ウインドウ内での特徴量ポインタテーブルのデータ格納場所を示すポインタインデックスを付与された画素の有無およびウインドウ内での画素に付与されたポインタインデックスの矛盾の有無により、参照済みの画素と注目画素との特徴量の整合をとりつつ計測を行う。【選択図】図２
2008225739.tif 000002
【特許請求の範囲】
【請求項１】
画像の特徴量を計測する特徴量計測方法において、
前記特徴量と前記特徴量のマージ回数を格納する特徴量テーブルと、
前記特徴量テーブルに格納される特徴量とマージ回数の格納場所を示す特徴量インデックスを格納する特徴量ポインタテーブルと、
を用い、
特徴量計測を行う注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内に前記特徴量ポインタテーブルのデータ格納場所を示すポインタインデックスを付与された画素がない場合は、新規特徴量を作成し前記特徴量テーブルの未使用領域に格納するとともに、前記新規特徴量を指し示す特徴量インデックスを前記特徴量ポインタテーブルに格納する第１の工程と、
前記注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内にポインタインデックスを付与された画素があり、前記ポインタインデックスを付与された画素に矛盾がない場合は、特徴量ポインタテーブルの前記ポインタインデックスに格納された特徴量インデックスが指し示す特徴量をインクリメントする第２の工程と、
前記注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内にポインタインデックスを付与された画素があり、前記ポインタインデックスを付与された画素に矛盾がある場合は、前記特徴量テーブルのうち該当する特徴量のマージ結果である特徴量と修正したマージ回数を格納するとともに、特徴量ポインタテーブルの前記ポインタインデックスに格納された特徴量インデックスのうち、マージされた特徴量インデックスをマージした特徴量インデックスに書き換え、マージ後の特徴量を指し示すようにする第３の工程と、
を有することを特徴とする特徴量計測方法。
【請求項２】
前記ウインドウは、前記注目画素と前記注目画素に対する左、左上、上、右上の画素を含み、前記左、左上、上、右上の画素の少なくとも一つの画素を参照することで、特徴量を計測することを特徴とする請求項１記載の特徴量計測方法。
【請求項３】
画像の特徴量を計測する特徴量計測方法において、
前記特徴量と前記特徴量のマージ回数を格納する特徴量テーブルと、
前記特徴量テーブルに格納される特徴量とマージ回数の格納場所を示す特徴量インデックスを格納する特徴量ポインタテーブルと、
を用い、
前記第１から第３の工程において、前記注目画素の１画素前までの特徴量計測で、前記注目画素に対するウインドウ内の画素の特徴量に矛盾がない場合は前記矛盾のない画素のうちの一つを参照して特徴量計測を行い、前記ウインドウ内に注目画素以外の画素全てに前記ポイントインデックスが付与されていない場合は新規特徴量を作成することを特徴とする請求項１または請求項２記載の特徴量計測方法。
【請求項４】
前記特徴量のマージは、前記特徴量テーブルに格納されているマージ回数のうち、マージ回数が多い方の特徴量にマージ結果を格納することを特徴とする請求項１から請求項３のうちいずれか一項記載の特徴量計測方法。
【請求項５】
前記特徴量は、０／１を示す二値画像のうち１を示す画素の連結成分の面積であることを特徴とする請求項１から請求項４のうちいずれか一項記載の特徴量計測方法。
【請求項６】
前記特徴量は、０／１を示す二値画像のうち１を示す画素の連結成分の重心であることを特徴とする請求項１から請求項４のうちいずれか一項記載の特徴量計測方法。
【請求項７】
前記特徴量テーブルと前記特徴量ポインタテーブルに格納するデータを記憶する記憶素子と、
前記第１の工程から前記第３の工程を実行処理する中央処理装置と、
を備えたことを特徴とする請求項１から請求項６のうちいずれか一項記載の特徴量計測装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置に用いられる二値画像の特徴量計測処理を、一回の走査で計測する特徴量計測方法および特徴量計測装置に関する。
【背景技術】
【０００２】
通常、二値画像の特徴量計測処理は、例えば、１を示す画素が上下左右および斜めに接続している連結成分において、同一の連結成分に自然数の名前を付けるラベリングと、各連結成分の面積等の特徴量を計測する特徴量計測に分けられる。連結成分が複雑な形状をしている場合、一回のラスタ走査では同一の連結成分に複数のラベルが付与され、ラベルが同一となるように整合がとれるまで画像を複数回走査する。
【０００３】
このような課題を解決するために、メモリでポインタ管理をすることにより、一回の走査で特徴量を計測するアルゴリズムが提案されている（例えば、特許文献１参照）。これは２×２の画素を計測しパターンを当てはめ、パターンを基に各ラスタのラベルを３個のメモリを用いてポインタ管理するものである。
【０００４】
【特許文献１】特開平５−１２４４４号公報（第３〜５頁、第１〜１３図）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし上記従来技術においては、斜めに連結した画素成分を計測しないという制限がある。また上記従来技術においては、パターンを適用するために特徴量計測を行う注目画素が０の場合についても、２×２の画素を計測しなければならない。また一般に、ソフトウェアの場合はハードウェアよりも処理速度が遅いため、参照する画素数が多いとメモリへのアクセス数が増え、ソフトウェア処理性能が低下する。
【０００６】
この発明はかかる課題を解決するためになされたもので、画像処理において１回の走査で特徴量を計測するとともに、斜めに連結した画素成分の特徴量も計測可能し、かつ参照する画素数を減らすことでソフトウェアの処理性能を低下させないことを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る特徴量計測方法は、
画像の特徴量を計測する特徴量計測方法において、
前記特徴量と前記特徴量のマージ回数を格納する特徴量テーブルと、
前記特徴量テーブルに格納される特徴量とマージ回数の格納場所を示す特徴量インデックスを格納する特徴量ポインタテーブルと、
を用い、
特徴量計測を行う注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内に前記特徴量ポインタテーブルのデータ格納場所を示すポインタインデックスを付与された画素がない場合は、新規特徴量を作成し前記特徴量テーブルの未使用領域に格納するとともに、前記新規特徴量を指し示す特徴量インデックスを前記特徴量ポインタテーブルに格納する第１の工程と、
前記注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内にポインタインデックスを付与された画素があり、前記ポインタインデックスを付与された画素に矛盾がない場合は、特徴量ポインタテーブルの前記ポインタインデックスに格納された特徴量インデックスが指し示す特徴量をインクリメントする第２の工程と、
前記注目画素を含むウインドウ内の画素を参照し、前記注目画素以外に前記ウインドウ内にポインタインデックスを付与された画素があり、前記ポインタインデックスを付与された画素に矛盾がある場合は、前記特徴量テーブルのうち該当する特徴量のマージ結果である特徴量と修正したマージ回数を格納するとともに、特徴量ポインタテーブルの前記ポインタインデックスに格納された特徴量インデックスのうち、マージされた特徴量インデックスをマージした特徴量インデックスに書き換え、マージ後の特徴量を指し示すようにする第３の工程と、
を有することを特徴とする。
【発明の効果】
【０００８】
本発明のように、注目画素に対して左、左上、上、右上画素を含むウインドウを用いて上記処理を行うことで、注目画素の斜め上の画素との特徴量の整合をとることができるため、斜めに連結した画素成分の特徴量も１回の走査で計測可能となる。
【発明を実施するための最良の形態】
【０００９】
実施の形態１．
図１は、本発明の実施の形態１における特徴量計測方法のデータ構造および画像走査方向を示す図である。図１（ａ）は、実施の形態１における入力画像１１の特徴量計測に用いるデータ構造を示す図である。入力画像１１は０／１の二値画像であり、そのうち斜線がかかった四角枠は１の値を示す画素（以下、１の画素）１２とし、それ以外の点線で囲まれた四角枠は０の値を示す画素（以下、０の画素）１３とする。
【００１０】
入力画像１１は、画像処理を行うにあたり画像データ１４として取り込まれる。従って画像処理の初期状態においては、画像データ１４と入力画像１１は同じである。また画像データ１４におけるドットのかかった四角枠は、特徴量計測を行う注目画素１５であり、特徴量計測においては、後述する特徴量ポインタテーブル１７のポインタインデックスを付与する画素を示している。また注目画素１５を含む太枠は、注目画素１５の特徴量計測を行う際に着目する領域を示すウインドウ１６である。
【００１１】
特徴量ポインタテーブル１７は、後述する特徴量テーブル１８の特徴量インデックスを格納するテーブルである。従って、特徴量ポインタテーブル１７に同じ特徴量インデックスが複数格納されている場合、それらは同じ特徴量インデックスを指していることを意味する。なおポインタインデックスとは、特徴量ポインタテーブル１７におけるデータ（特徴量インデックス）の格納場所を示すものである。
【００１２】
特徴量テーブル１８は、計測した特徴量を格納している特徴量格納領域１９と、過去に特徴量をマージした回数を格納しているマージ回数格納領域２０から成り立つテーブルである。特徴量テーブル１８の各要素は、初期状態を含む有効／無効の状態を持つ。特徴量格納領域１９、マージ回数格納領域２０とも初期状態は「０」である。なお特徴量インデックスとは、特徴量テーブル１８におけるデータ（特徴量およびマージ回数）の格納場所を示すものである。
【００１３】
また図１（ｂ）は、特徴量計測の対象となる画像データ１４の走査方向を矢印で示したものである。
【００１４】
図２は、特徴量計測処理のフローチャートを示したものである。また図２記載のフローチャートのうち、後述するステップＳ１６の処理を図３に、後述するステップＳ１８の処理を図４に、後述するステップＳ１９の処理を図５に、後述するステップＳ１９の処理を図６に示す。
【００１５】
図２から図６のフローチャートに従い、特徴量計測の具体的な処理内容を説明する。また具体的な処理内容については、図２から図６のフローチャートとともに、図７から図１０を適宜参照しつつ説明する。なお本発明の実施の形態にて取り上げる特徴量は面積、つまり１の画素１２の数とし、特徴量のマージ処理は、２つの面積を加算する処理を指す。また、マージ処理で特徴量テーブル１８の格納領域を無効にする場合、特徴量である面積の値を０とすることによって無効にする。
【００１６】
図２のステップＳ１１では、特徴量計測を行う画像データ１４として二値画像である入力画像１１を入力する。従って、画像データ１４の初期状態は入力画像１１と同一であり、特徴量ポインタテーブル１７と特徴量テーブル１８の初期データは「０」にする。
【００１７】
ステップＳ１２で入力画像１１の走査のループ処理を開始し、図２のフローチャートに従って特徴量計測を実施する。このループ処理は、入力画像１１の走査を画素に対して繰り返し、走査終了をもってループ処理を終了する。
【００１８】
ステップＳ１３では、注目画素１５が１の画素１２であるか、０の画素１３であるか判定する。図７はステップＳ１３、ステップＳ１５、ステップＳ１６の一連の処理を示した図である。図７（ａ）は、注目画素１５までに走査を行った走査方向を示す図である。図７（ａ）では、走査方向を矢印で示している。図７（ａ）に示された画像データ１４では、注目画素１５までは０の画素１３が続くため、ステップＳ１３ではＮＯが選択されステップＳ１４へ飛び、入力画像走査のループを繰り返す。
【００１９】
また図７（ａ）に示したように注目画素１５に対して、注目画素１５以外の画素を参照する順序は、例えば、実施の形態１においては、Ａ、Ｂ、Ｃ，Ｄの順番とする。ただし、注目画素１５以外の画素全てを参照するため、参照する順序はこれに限るものではない。
【００２０】
図７（ｂ）は、走査処理において最初に検出する１の画素１２を示す図である。特徴量計測では、まずこの１の画素１２を注目画素１５として計測を行う。この注目画素１５は１の画素１２であるため、ステップＳ１３はＹＥＳとなる。
【００２１】
ステップＳ１５では、注目画素１５以外にウインドウ１６内で０より大きい値が存在するか否かの判定を行う。図７（ｂ）では、注目画素１５を除くウインドウ１６内の全ての画素が０の画素１３であるため、ステップＳ１５ではＮＯとなり、ステップＳ１６へ進む。
【００２２】
ステップＳ１６では、新規特徴量の作成、および注目画素の更新を行う。ステップＳ１６の処理内容を詳述したのが、図３である。ステップＳ１６の処理は、図３に示すようにステップＳ３１とステップＳ３２より構成される。
【００２３】
ステップＳ３１では、特徴量テーブル１８および特徴量ポインタテーブル１７の未使用領域を確保し、確保した特徴量テーブル１８の特徴量インデックスを、確保した特徴量ポインタテーブル１７に格納する。新規に確保した特徴量ポインタテーブル１７は、ステップＳ３２で作成する新規特徴量を指すよう設定される。図７（ｂ）では、ここまでの処理を示している。
【００２４】
ステップＳ３２では、確保した特徴量テーブル１８の領域に新規特徴量を作成し、格納する。具体的には、特徴量テーブル１８の特徴量格納領域１９に、面積として「１」を格納する。また、格納された特徴量格納領域１９に対応するマージ回数格納領域２０は「０」にする（新規特徴量を格納した領域は一度もマージされていないため）。また画像データ１４の注目画素１５に付与するポインタインデックスは、確保した特徴量ポインタテーブル１７のポインタインデックス（図７の場合、ｍ）とする。そしてステップＳ１６へ戻る。上記処理の結果を示したのが、図７（ｃ）である。図２のステップＳ１６へ戻ったらステップＳ１４に進み、特徴量計測のループ処理を繰り返す。
【００２５】
図８は、図７（ｃ）の後に特徴量計測のループ処理を続けた図であり、図２のステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１８の一連の処理を示した図である。
【００２６】
図８（ａ）では、注目画素１５までに走査を行った走査方向を矢印で示している。図８（ａ）に示した走査方向では、図７（ｃ）の後に０の画素１３によるループ処理を行う。その後、１の画素１２があったため、図７で示した処理と同様の処理を行い、この１の画素１２を新規特徴量とするため、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）に、特徴量インデックスの未使用領域を指し示す（ｎ＋１）を格納する。
【００２７】
また特徴量テーブル１８において、特徴量インデックス（ｎ＋１）の特徴量格納領域１９に特徴量である面積「１」を格納する。またマージ回数は０回であるため、特徴量インデックス（ｎ＋１）のマージ回数格納領域２０には「０」を格納する。また対応する画素は、確保した特徴量ポインタテーブル１７のポインタインデックスである（ｍ＋１）を付与する。その後、図８（ａ）に従い走査を繰り返し、次の注目画素の処理を行う状態が図８（ｂ）である。
【００２８】
図８（ｂ）における注目画素１５について考える。ステップＳ１３では、注目画素１５が１の画素１２であるのでＹＥＳと判定し、ステップＳ１５に進む。ステップＳ１５では、注目画素１５の上に、ポインタインデックスがｍとされた１の画素１２があるためＹＥＳと判定し、ステップＳ１７へ進む。
【００２９】
ステップＳ１７では、ウインドウ１６内のポインタインデックスに矛盾があるか否かの判定を行う。例えば図８の場合、注目画素１５を除いたウインドウ１６内には、ポインタインデックスｍの画素以外は全て０の画素１３であるため、矛盾はない（ＮＯ）と判定してステップＳ１８へ進む。
【００３０】
ここで、ウインドウ１６内の１の画素１２は全て同一の連結成分でなくてはならないため、ウインドウ１６内の１の画素１２に付与されているポインタインデックスに格納されている特徴量インデックスは同一の特徴量を指し示していなくてはならない。
【００３１】
従って、「ポインタインデックスに矛盾がある」とは、注目画素１５を除くウインドウ１６内の画素において、付与されたポインタインデックスに格納される特徴量インデックスが異なることをいう。反対に、「ポインタインデックスに矛盾がない」とは、注目画素１５を除くウインドウ１６内の画素において、付与されたポインタインデックスに格納される特徴量インデックスが同一であることをいう。また本明細書で「特徴量の整合をとる」とは、上記矛盾が生じている状態を矛盾のない状態にすることをいう。
【００３２】
ステップＳ１８では、特徴量および注目画素の更新を行う。ステップＳ１８の処理内容を詳述したのが、図４である。ステップＳ１８の処理は、図４に示すようにステップＳ４１より構成される。
【００３３】
ステップＳ４１では、まず特徴量を更新する。図８（ｂ）の場合では、参照順序Ｂの上画素のポインタインデックスがｍであるため、特徴量ポインタテーブル１７のポインタインデックスｍに格納されている特徴量インデックスｎが指している特徴量、つまり特徴量テーブル１８の特徴量インデックスｎに対して、注目画素１５の特徴量（面積）をインクリメントする。従って、特徴量テーブル１８の特徴量インデックスｎにおける特徴量格納領域１９は、「１」＋「１」＝「２」となる。
【００３４】
またステップＳ４１において、注目画素１５のポインタインデックスは、関連付ける画素のポインタインデックスとする。つまり、上画素のポインタインデックスｍを、注目画素１５のポインタインデックスとする。そしてステップＳ１８へ戻る。上記処理の結果を示したのが、図８（ｃ）である。図２のステップＳ１８に戻ったらステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。
【００３５】
図９は、図８（ｃ）の後に特徴量計測のループ処理を続けた図であり、図２のステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１９の一連の処理を示した図である。
【００３６】
図９（ａ）では、注目画素１５までに走査を行った走査方向を矢印で示している。図９（ａ）における注目画素１５について考える。ステップＳ１３では、注目画素１５が１の画素１２であるのでＹＥＳと判定し、ステップＳ１５に進む。
【００３７】
ステップＳ１５では、注目画素１５の左上および左にポインタインデックスｍとされた１の画素１２が、右上にポインタインデックス（ｍ＋１）とされた１の画素１２があるため、０より大きい値が存在する（ＹＥＳ）と判定し、ステップＳ１７へ進む。
【００３８】
ステップＳ１７では、ウインドウ１６内のポインタインデックスに矛盾があるか否かの判定を行う。例えば、注目画素１５を除いたウインドウ１６内において、注目画素１５の左上および左画素のポインタインデックスはｍであり、注目画素１５の右上画素のポインタインデックスは（ｍ＋１）であるため、矛盾がある（ＹＥＳ）と判定し、ステップＳ１９へ進む。
【００３９】
ステップＳ１９では、特徴量マージ処理および特徴量ポインタテーブル１７の整合処理を行う。ステップＳ１９の処理内容を詳述したのが、図５と図６である。このうち、図５は特徴量マージ処理に関する処理を示し、図６は特徴量ポインタテーブル１７の整合処理に関する処理を示している。
【００４０】
特徴量マージ処理は、図５に示すようにステップＳ５１とステップＳ５２より構成される。また特徴量ポインタテーブル１７の整合処理は、図６に示すようにステップＳ６１からステップＳ６７より構成される。なお、特徴量マージ処理と特徴量ポインタテーブル１７の整合処理の順序はどちらを先に行っても良いが、本実施の形態においては、特徴量マージ処理を先に行う例を示す。
【００４１】
図５のうち、ステップＳ５１では、注目画素１５の特徴量を加えた上で特徴量をマージする。ステップＳ５１では、注目画素１５に対して、特徴量ポインタテーブル１７のポインタインデックスｍに格納されている特徴量インデックスｎが指している特徴量、つまり特徴量テーブル１８の特徴量インデックスｎに、注目画素１５の特徴量（面積）をインクリメントする。従って、特徴量テーブル１８の特徴量インデックスｎにおける特徴量格納領域１９は、「２」＋「１」＝「３」となる。
【００４２】
なお、ウインドウ１６内に含まれる注目画素１５以外の画素には、ポインタインデックスがｍと（ｍ＋１）の２種類がある。そのうち、図７（ａ）で示したＡからＤの順序で注目画素１５以外の画素を参照すると、図９（ｂ）においては、注目画素１５の左上の画素（ポインタインデックスｍ）の参照を先に行う（参照順序Ａ）。従って、注目画素１５に付与されるポインタインデックスは参照順序が先のｍとし、上記のように特徴量をインクリメントする。
【００４３】
またステップＳ５１において、注目画素１５のポインタインデックスは、関連付ける画素のポインタインデックスとする。つまり注目画素１５のポインタインデックスは、上記のとおりｍとする。これまでの一連の処理を示したのが図９（ｂ）である。
【００４４】
またステップＳ５１において、ポインタインデックスが矛盾している特徴量をマージする。具体的には、特徴量テーブル１８の特徴量インデックスｎに格納されている特徴量「３」と、特徴量テーブル１８の特徴量インデックス（ｎ＋１）に格納されている特徴量「１」をマージして、「３」＋「１」＝「４」をマージ結果として特徴量テーブル１８の特徴量インデックスｎに格納する。
【００４５】
なお図９の場合は、特徴量をマージする時に特徴量インデックスｎの方にマージさせたが、特徴量インデックス（ｎ＋１）の方にマージさせてもよい。
【００４６】
次にステップＳ５２では、空にした特徴量の領域を無効にする。図９の例では、特徴量のマージに伴い、特徴量テーブル１８の特徴量インデックス（ｎ＋１）において特徴量格納領域１９が空となったため、特徴量テーブル１８の特徴量インデックス（ｎ＋１）を無効にする。ステップＳ５２の処理を終えたら、ステップＳ１９へ戻る。
【００４７】
次に特徴量ポインタテーブル１７の整合処理を行う。特徴量ポインタテーブル１７の整合処理では、図６に記載されているように、まずステップＳ６１において、ウインドウ１６内の画素について、無効にする特徴量を指している特徴量ポインタテーブル１７の値をマージ後の特徴量を指すように書き換える。
【００４８】
例えば図９の例だと、無効にするのは特徴量インデックス（ｎ＋１）である。これを格納している特徴量ポインタテーブル１７のポインタインデックスは（ｍ＋１）であり、このポインタインデックス（ｍ＋１）に対応する画素は、注目画素１５の右上の画素である。特徴量テーブル１８の特徴量インデックス（ｎ＋１）は無効となるため、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）に格納されている値（ｎ＋１）をｎに書き換え、特徴量テーブル１８の特徴量インデックスｎを指し示すようにする。
【００４９】
無効になった特徴量テーブル１８の特徴量インデックス（ｎ＋１）は、過去に特徴量をマージしたことがないため、ウインドウ１６外の特徴量ポインタテーブルの整合に関するループ、つまりステップＳ６２からステップＳ６５は実施せず、ステップＳ６６に進む（ステップＳ６２からステップＳ６５に関する処理は後述する）。
【００５０】
ステップＳ６６では、特徴量テーブル１８のマージ回数を加算し、マージ回数を特徴量テーブル１８のマージ回数格納領域２０に格納する。図９の例では、特徴量テーブル１８の特徴量インデックスｎのマージ回数格納領域２０には初期値「０」に今回のマージ処理分の「１」を加え、「０」＋「１」＝「１」が入る。
【００５１】
ステップＳ６７では、無効になった特徴量テーブル１８のマージ回数を０にする。図９の例では、特徴量テーブル１８の特徴量インデックス（ｎ＋１）が無効となったので、特徴量インデックス（ｎ＋１）のマージ回数格納領域２０に「０」を格納する。上記処理の結果を示したのが、図９（ｃ）である。図２のステップＳ１９に戻ったらステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。
【００５２】
図１０は、図９（ｃ）の後に特徴量計測のループ処理を続けた図であり、図２のステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１９の一連の処理を示した図である。
【００５３】
図１０（ａ）では、注目画素１５までに走査を行った走査方向を矢印で示しており、図９（ｃ）の後の、特徴量計測のループを続けた図を示す。図９（ｃ）から図１０（ａ）に至るまでにおいて、ポインタインデックス（ｍ＋２）を示している１の画素１２は、ウインドウ１６内に１の画素１２がないため新規特徴量としてインデックス（ｍ＋２）を付与されたものである。
【００５４】
またそれ以降の１の画素１２にはインデックスｍが付与されている。これは、図７（ａ）に示した参照順序に従い、対応する画素に対して右上、上、左上、左上の画素にポインタインデックスｍが付与された画素があるからである。
【００５５】
図１０（ｂ）において、特徴量ポインタテーブル１７のポインタインデックスｍは、特徴量インデックスｎを指し示すため、ｎが格納されている。また特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）には、マージ後の特徴量インデックスｎを指し示すため、ｎが格納されている。また特徴量ポインタテーブル１７のポインタインデックス（ｍ＋２）には、新規特徴量が格納されている特徴量インデックス（ｎ＋２）を指し示すため、（ｎ＋２）が格納されている。
【００５６】
また特徴量テーブル１８の特徴量格納領域１９において、特徴量インデックスｎには、特徴量インデックスｎ（面積は「７」）と特徴量インデックス（ｎ＋１）の特徴量（面積は「１」）をマージした「８」が格納されている。また特徴量テーブル１８の特徴量格納領域１９において、特徴量インデックス（ｎ＋１）は無効となっているため、「０」が格納されている。また特徴量テーブル１８の特徴量格納領域１９において、特徴量インデックス（ｎ＋２）には、新規特徴量である「１」が格納されている。
【００５７】
また特徴量テーブル１８のマージ回数格納領域２０において、特徴量インデックスｎにはマージ回数「１」が、特徴量インデックス（ｎ＋１）は無効としたため「０」が、特徴量インデックス（ｎ＋２）はマージしていないためマージ回数「０」が格納されている。
【００５８】
図１０（ｂ）における注目画素１５について考える。ステップＳ１３では、注目画素１５が１の画素１２であるのでＹＥＳと判定し、ステップＳ１５に進む。
【００５９】
ステップＳ１５では、注目画素１５の左に、ポインタインデックスｍとされた１の画素１２が、右上にポインタインデックス（ｍ＋２）とされた１の画素１２があるため、０より大きい値が存在する（ＹＥＳ）と判定し、ステップＳ１７へ進む。
【００６０】
ステップＳ１７では、ウインドウ１６内の特徴量に矛盾があるか否かの判定を行う。例えば図１０では、注目画素１５を除いたウインドウ１６内において、注目画素１５の左のポインタインデックスはｍであり、注目画素１５の右上のポインタインデックスは（ｍ＋２）であり、異なる特徴量インデックスを格納しているため、矛盾がある（ＹＥＳ）と判定し、ステップＳ１９へ進む。
【００６１】
ステップＳ１９では、前述のように特徴量マージ処理および特徴量ポインタテーブル１７の整合処理を行う。
【００６２】
図５に示された特徴量マージ処理において、ステップＳ５１では、注目画素１５の特徴量を加えた上で特徴量をマージする。ステップＳ５１において、注目画素１５には、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋２）に格納されている特徴量インデックス（ｎ＋２）が指している特徴量、つまり特徴量テーブル１８の特徴量インデックス（ｎ＋２）に、注目画素１５の特徴量（面積）をインクリメントする。従って、特徴量テーブル１８の特徴量インデックス（ｎ＋２）における特徴量格納領域１９は、「１」＋「１」＝「２」となる。
【００６３】
なお、ウインドウ１６内に含まれる注目画素１５以外の画素には、ポインタインデックスがｍと（ｍ＋２）の２種類がある。そのうち、図７（ａ）で示したＡからＤの順序で注目画素１５以外の画素を参照すると、図１０（ｂ）においては、注目画素１５の左上、上にはポインタインデックスが付与された画素がなく、右上にポインタインデックス（ｍ＋２）が付与された画素がある。この画素は、ポインタインデックスｍが付与された左の画素より先に参照される。従って、注目画素１５に付与されるポインタインデックスは（ｍ＋２）となる。
【００６４】
またステップＳ５１において、注目画素１５のポインタインデックスは、関連付ける画素のポインタインデックスとする。つまり注目画素１５のポインタインデックスは、上記のとおり（ｍ＋２）とする。これまでの一連の処理を示したのが図１０（ｂ）である。
【００６５】
またステップＳ５１において、ポインタインデックスが矛盾している特徴量をマージする。具体的には、特徴量テーブル１８の特徴量インデックスｎに格納されている特徴量「８」と、特徴量テーブル１８の特徴量インデックス（ｎ＋２）に格納されている特徴量「２」をマージして、「８」＋「２」＝「１０」をマージ結果として特徴量テーブル１８の特徴量インデックス（ｎ＋２）に格納する。
【００６６】
なお上記例の場合は、特徴量をマージする時に特徴量インデックス（ｎ＋２）の方にマージさせたが、特徴量インデックスｎの方にマージさせてもよい。
【００６７】
次にステップＳ５２では、空にした特徴量の領域を無効にする。図１０の例では、特徴量のマージに伴い、特徴量テーブル１８の特徴量インデックスｎにおいて特徴量格納領域１９が空となったため、特徴量テーブル１８の特徴量インデックスｎを無効にする。ステップＳ５２の処理を終えたら、ステップＳ１９へ戻る。
【００６８】
次に特徴量ポインタテーブル１７の整合処理を行う。特徴量ポインタテーブル１７の整合処理では、図６に記載されているように、まずステップＳ６１において、ウインドウ１６内の画素について、無効にする特徴量を指している特徴量ポインタテーブル１７の値をマージ後の特徴量を指すように書き換える。
【００６９】
例えば図１０では、無効にするのは特徴量インデックスｎである。特徴量テーブル１８の特徴量インデックスｎを無効とするため、特徴量ポインタテーブル１７のポインタインデックスｍに格納されている値ｎを（ｎ＋２）に書き換え、特徴量テーブル１８の特徴量インデックス（ｎ＋２）を指し示すようする。
【００７０】
無効になった特徴量テーブル１８の特徴量インデックスｎは、過去に１回特徴量をマージしているため、ウインドウ１６外の特徴量ポインタテーブルの整合に関するループ、つまりステップＳ６２からステップＳ６５を実施する。
【００７１】
上記内容は、以下のことを意味する。ウインドウ１６内の画素にはｍと（ｍ＋２）の２種類のポインタインデックスを付与された画素がある。それらの画素は、異なる特徴量インデックスを指し示しているため、「矛盾した状態」である。そこで矛盾を解消し特徴量の整合をとるため、ポインタインデックスｍとポインタインデックス（ｍ＋２）の指し示す特徴量を同一にした。それが、上記例では特徴量インデックス（ｎ＋２）を指し示すようにすることに相当する。
【００７２】
ここで、ポインタインデックスｍがもともと指し示していた特徴量インデックスはｎであるが、そのマージ回数格納領域２０を参照すると「１」が格納されている。これは、過去に１回マージした結果、特徴量インデックスｎを指し示しているポインタインデックスが、ｍ以外にあと一ついることを示している。そして、上記あと一つのポインタインデックスは、ウインドウ１６外の画素に付与されているものである、ということである。そして、特徴量インデックスｎを指し示しているあと一つのポインタインデックスも同様に特徴量の整合をとるため、ステップＳ６２からステップＳ６５を実施する。
【００７３】
ステップＳ６２では、無効になった特徴量テーブル１８の特徴量インデックスｎは、図１０（ｂ）のマージ回数格納領域２０にもあるように過去に１回特徴量をマージしている。従って、ステップＳ６２で特徴量ポインタテーブル１７を検索する。
【００７４】
ステップＳ６３では、空にした（または空にする）特徴量を指しているか否かの判定を行う。例えば、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）を参照した場合、ポインタインデックス（ｍ＋１）は空にした特徴量テーブル１８の特徴量インデックスｎを指し示している。従ってステップＳ６３はＹＥＳとなり、ステップＳ６４に進む。もし空にした（または空にする）特徴量を指し示していない場合は、ステップＳ６４を飛ばしてステップＳ６５へ進む。
【００７５】
ステップＳ６４では、マージした（マージする）特徴量を指しているポインタに付け替える。例えば図１０（ｂ）の場合、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）は、無効となったｎから特徴量をマージした（ｎ＋２）へ書き換えられる。
【００７６】
１回ポインタを修正したため、あと一つのポインタインデックスはポインタインデックス（ｍ＋１）であり、その特徴量ポインタテーブルの書き換えが終了したため、特徴量の整合がとれ矛盾が解消したので、ステップＳ６２からステップＳ６５のループを抜ける。なお、ウインドウ１６外のポインタインデックスで特徴量の整合を取らなくてはならないものが２つ以上ある場合は、ステップＳ６２からステップＳ６５のループを繰り返す。
【００７７】
ステップＳ６６では、特徴量テーブル１８のマージ回数を加算し、マージ回数を特徴量テーブル１８のマージ回数格納領域２０に格納する。図１０の例では、特徴量テーブル１８の特徴量インデックス（ｎ＋２）のマージ回数格納領域２０には初期値「０」に、特徴量インデックスｎに格納されていた今までのマージ回数「１」と今回のマージ処理分の「１」を加え、「０」＋「１」＋「１」＝「２」が入る。
【００７８】
ステップＳ６７では、無効になった特徴量テーブル１８のマージ回数を「０」にする。図１０の例では、特徴量テーブル１８の特徴量インデックスｎが無効となっているので、特徴量インデックスｎのマージ回数格納領域２０に「０」を格納する。上記処理の結果を示したのが、図１０（ｃ）である。図２のステップＳ１９に戻ったらステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。
【００７９】
走査処理を全て終了し、図２におけるステップＳ１２からステップＳ１４までの間の一連のループ処理が終わったら、ステップＳ２０へ進む。ステップＳ２０では、上記ループ処理によりマージして求めた特徴量である連結成分の面積の合計を出力する。
【００８０】
このように、注目画素１５に対して左、左上、上、右上画素を含むウインドウを用いて上記処理を行うことで、注目画素１５の斜め上の画素との特徴量の整合をとることができるため、図１に示したような斜めに連結した画素成分の特徴量も１回の走査で計測可能となる。
【００８１】
なお特徴量をマージするにあたり、どちらの特徴量インデックスにマージするかの基準には、マージ回数の多い方にマージする、特徴量テーブル１８の特徴量インデックスの小さい方にマージする等が考えられ、いずれの方にマージするかの基準は適宜定めればよい。
【００８２】
例えば図１１にて特徴量をマージする場合、マージ後の特徴量を特徴量テーブル１８の特徴量インデックスｎもしくは特徴量インデックス（ｎ＋１）に格納する。ここで、特徴量テーブル１８の特徴量インデックスｎにマージ後の特徴量を格納した場合、特徴量ポインタテーブル１７のポインタインデックス（ｍ＋１）から（ｍ＋３）に格納されている値を（ｎ＋１）からｎに書き換えなければならない。
【００８３】
一方、特徴量テーブル１８の特徴量インデックス（ｎ＋１）にマージ後の特徴量を格納した場合、特徴量ポインタテーブル１７のポインタインデックスｍに格納されている値をｎから（ｎ＋１）に書き換えるだけでよい。
【００８４】
ゆえに特徴量をマージする際は、特徴量テーブル１８のマージ回数格納領域２０に格納されている過去のマージ回数が多い方にマージ後の特徴量を格納することで、特徴量ポインタテーブル１７を更新する負荷をより低減することができる。
【００８５】
実施の形態２．
図１２は、処理を行う画像データ１４と、注目画素１５に対してウインドウ１６内の参照する画素の順序をＡからＤで示したものである。なお、実施の形態１と実施の形態２における注目画素１５以外の参照画素の順序は異なっている。
【００８６】
図１３は、実施の形態２における特徴量計測のフローチャートを示している。図１３は、実施の形態１に対して画素を参照する手順を追加したフローチャートである。
【００８７】
ステップＳ１１およびステップＳ１２およびステップＳ１３について、注目画素１５が１でない（ＮＯの）場合は、実施の形態１と同様であるため、説明は省略する。
【００８８】
ステップＳ１３において注目画素１５が１の画素１２である場合、ＹＥＳを選択し、ステップＳ１１１に進む。
【００８９】
特徴量計測を行う際、実施の形態１では、ステップＳ１５において、注目画素１５以外にウインドウ１６内で０より大きい値が存在するか否かを判定するにあたり、注目画素１５に対して注目画素１５以外、つまり左と左上と上と右上の画素全てを参照して判定していた。しかし実施の形態２においては、ステップＳ１３以降の処理で、参照する画素の優先順位をつけて判定する。
【００９０】
例えば、注目画素１５の上画素のポインタインデックスが０より大きい場合、ステップＳ１１１ではＹＥＳと判定するため、他の画素を参照する必要はない。それは、左上画素と上画素の特徴量は上画素が注目画素だったときに整合をとっており、上画素と右上画素の特徴量は右上画素が注目画素だったときに整合をとっており、左画素と上画素の特徴量は左画素が注目画素だったときに整合をとっているからである。ステップＳ１１１でＹＥＳと判定した場合、ステップＳ１８へ進む。
【００９１】
ステップＳ１８の処理は実施の形態１の図４、図８と同様であるため、説明は省略する。ステップＳ１８の処理を終了後、ステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。
【００９２】
注目画素１５の上画素が０の画素１３である場合、ステップＳ１１１ではＮＯと判定するため、ステップＳ１１２へ進む。
【００９３】
ステップＳ１１２では、左または左上画素が０より大きいか否かの判定を行う。もしＹＥＳならば、左画素または左上画素と右上画素は、過去に同一ウインドウ内にあったことがない。従って、特徴量の整合がとれておらず異なる特徴量を指している可能性があるため、ステップＳ１１３、ステップＳ１１５で確認する必要がある。またステップＳ１１２において、左および左上が０（ＮＯ）の場合は、ステップＳ１１４へ進む。
【００９４】
ステップＳ１１３では、右上画素が０より大きいか否かの判定を行う。右上画素が０である（ＮＯの）場合はステップＳ１８へ進み、左または左上画素に対して整合がとれるように特徴量／注目画素更新を行う。ステップＳ１８の処理は実施の形態１の図４、図８と同様であるため、説明は省略する。ステップＳ１８の処理を終了後、ステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。ステップＳ１１３において右上画素が０より大きい（ＹＥＳの）場合、ステップＳ１１５へ進む。
【００９５】
ステップＳ１１５では、左または左上画素の特徴量と右上画素の特徴量が同一か否かの判定を行う。ステップＳ１１５においてＹＥＳの場合は、ステップＳ１８へ進み、左または左上画素に対して特徴量／注目画素更新を行う。ステップＳ１８の処理は実施の形態１の図４、図８と同様であるため、説明は省略する。ステップＳ１８の処理を終了後、ステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。ステップＳ１１５において左または左上画素の特徴量と右上画素の特徴量が同一でない（ＮＯの）場合、ステップＳ１９へ進む。これは、実施の形態１のステップＳ１７における矛盾がある（ＹＥＳ）の場合に相当する。
【００９６】
ステップＳ１９では、左または左上画素に対して整合がとれるように特徴量マージ処理および特徴量ポインタテーブル１７の整合処理を行う。ステップＳ１９の処理は実施の形態１の図５、図６、図９、図１０と同様であるため、説明は省略する。ステップＳ１９の処理を終了後、ステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。
【００９７】
ステップＳ１１２において、左および左上が０（ＮＯ）の場合は、ステップＳ１１４へ進む。ステップＳ１１４では、右上画素が０より大きいか否かの判定を行う。もし右上画素が０より大きい（ＹＥＳの）場合、ステップＳ１８へ進み、右上画素に対して整合がとれるように特徴量／注目画素更新を行う。ステップＳ１８の処理は実施の形態１の図４、図８と同様であるため、説明は省略する。ステップＳ１８の処理を終了後、ステップＳ１４へ進み、特徴量計測のループ処理を繰り返す。ステップＳ１１４において右上画素が０（ＮＯ）の場合、ステップＳ１６へ進む。
【００９８】
ステップＳ１６では、新規特徴量作成／注目画素更新を行う。ステップＳ１６の処理は、実施の形態１における図３、図７と同様であるため、説明は省略する。またステップＳ１４、ステップＳ２０の処理も実施の形態１と同様であるため、説明は省略する。
【００９９】
このように、新規特徴量を作成する際は、注目画素１５以外の画素が全て０あることを確認する必要がある。従って、ステップＳ１３にて注目画素１５が１であること、ステップＳ１１１にて注目画素１５の上画素が０であること、ステップＳ１１２にて左および左上画素が０であること、ステップＳ１１４にて右上画素が０であること全ての判定を実施しなくてはならない。
【０１００】
上記フローチャートを用いた処理の例を示したのが図１４である。まず図１４（ａ）に示す例１を考える。注目画素１５に対して上画素ＡはナシであるためＮＯを選択し、ステップＳ１１１からすステップＳ１１２へ遷移する。次に、左画素Ｂと左上画素ＣはナシであるためＮＯを選択し、ステップＳ１１２からステップＳ１１４へ遷移する。次に、右上画素ＤはナシであるためＮＯを選択し、ステップＳ１１４からステップＳ１６へ遷移する。そしてステップＳ１６にて新規特徴量作成／注目画素更新を実施する。従って、画素を４回（Ａ、Ｂ、Ｃ、Ｄ）参照している。
【０１０１】
次に図１４（ｂ）に示す例２を考える。注目画素１５に対して上画素ＡはアリであるためＹＥＳを選択し、ステップＳ１１１からステップＳ１８へ遷移する。そしてステップＳ１８にて特徴量／注目画素更新（上画素）を実施する。従って、画素を１回（Ａ）参照している。
【０１０２】
次に図１４（ｃ）に示す例３を考える。注目画素１５に対して上画素ＡはナシであるためＮＯを選択し、ステップＳ１１１からステップＳ１１２へ遷移する。次に、左画素ＢはアリであるためＹＥＳを選択し、ステップＳ１１２からステップＳ１１３へ遷移する。次に、右上画素ＤはアリであるためＹＥＳを選択し、ステップＳ１１３からステップＳ１１５へ遷移する。次に、左画素と右上画素の特徴量は同一でないため、ステップＳ１１５からステップＳ１９へ遷移する。そしてステップＳ１９にて特徴量マージ／ポインタテーブルの整合を実施する。従って、画素を３回（Ａ、Ｂ、Ｄ）参照している。
【０１０３】
最後に図１４（ｄ）に示す例４を考える。注目画素１５に対して上画素ＡはナシであるためＮＯを選択し、ステップＳ１１１からステップＳ１１２へ遷移する。次に、左画素ＢはアリであるためＹＥＳを選択し、ステップＳ１１２からステップＳ１１３へ遷移する。次に、右上画素ＤはナシであるためＮＯを選択し、ステップＳ１１３からステップＳ１８へ遷移する。そしてステップＳ１８にて特徴量／注目画素更新（左ｏｒ左上画素）を実施する。従って、画素を３回（Ａ、Ｂ、Ｄ）参照している。
【０１０４】
図１５は、図１３のフローチャートに従い図１の入力画像１１について特徴量を計測した際の注目画素を除く参照画素数を示している。なお図１５記載の四角枠内の数値は、図７から図１０記載の付与されたポインタインデックスを表しておらず、上記のように参照画素数を示している点に注意を要する。
【０１０５】
図１２の参照順序および図１３のフローチャートにより、図１５記載のように参照画素数が４個ではなく３個で済む箇所、また参照画素数が１個で済む箇所ができることがわかる。
【０１０６】
実施の形態２のように、注目画素１５に対して、参照する画素の優先順位をつけて判定する処理を実施することにより、参照しなくてもよい画素を参照せずに済むため、処理スピードが向上する。
【０１０７】
なお、本発明の実施の形態を説明するために、計測する特徴量として面積つまり連結成分の画素数を用いた。しかし計測する特徴量は面積に限定する必要はない。例えば、連結成分の重心を計測する特徴量としてもよい。
【０１０８】
その場合は、新規特徴量を作成するステップＳ１６の処理のうち、図３記載のステップＳ３２において、面積に１を加算することに加えて、注目画素１５のＸ座標、Ｙ座標を加算する処理を行う。
【０１０９】
また特徴量／注目画素更新処理を行うステップＳ１８の処理のうち、図４記載のステップＳ４１において、面積をインクリメントする処理に加えて、注目画素１５のＸ座標、Ｙ座標を加算する処理を行う。
【０１１０】
このように処理して、Ｘ座標、Ｙ座標を加算した連結成分の画素数で平均をとることにより、連結成分の画素の重心を特徴量として計測することができる。
【０１１１】
なお実施の形態１、実施の形態２に記載した方法は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置）にて実施される。またデータの格納はＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等の記憶素子を用いてデータを格納させればよい。
【図面の簡単な説明】
【０１１２】
【図１】本発明の実施の形態１における特徴量計測方法のデータ構造および画像走査方向を示す図である。
【図２】本発明の実施の形態１における特徴量計測のフローチャートを示す図である。
【図３】本発明の実施の形態１におけるステップＳ１６（新規特徴量作成および注目画素更新）のフローチャートを示す図である。
【図４】本発明の実施の形態１におけるステップＳ１８（特徴量および注目画素更新）のフローチャートを示す図である。
【図５】本発明の実施の形態１におけるステップＳ１９（特徴量マージ処理）のフローチャートを示す図である。
【図６】本発明の実施の形態１におけるステップＳ１９（特徴量ポインタテーブルの整合処理）のフローチャートを示す図である。
【図７】本発明の実施の形態１における特徴量計測のうち、ステップＳ１３、ステップＳ１５、ステップＳ１６の一連の処理を示した図である。
【図８】本発明の実施の形態１における特徴量計測のうち、ステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１８の一連の処理を示した図である。
【図９】本発明の実施の形態１における特徴量計測のうち、ステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１９を示した図である。
【図１０】本発明の実施の形態１における特徴量計測のうち、ステップＳ１３、ステップＳ１５、ステップＳ１７、ステップＳ１９を示した図である。
【図１１】本発明の実施の形態１における特徴量計測のうち、マージ処理を行う基準の例を示した図である。
【図１２】本発明の実施の形態２における処理を行う画像データと注目画素に対してウインドウ内の参照する画素の順序を示す図である。
【図１３】本発明の実施の形態２における特徴量計測のフローチャートを示す図である。
【図１４】本発明の実施の形態２におけるフローチャートを用いた処理例を示した図である。
【図１５】本発明の実施の形態２における特徴量を計測した際の注目画素を除く参照画素数を示した図である。
【符号の説明】
【０１１３】
１１．入力画像
１２．１の画素
１３．０の画素
１４．画像データ
１５．注目画素
１６．ウインドウ
１７．特徴量ポインタテーブル
１８．特徴量テーブル
１９．特徴量格納領域
２０．マージ回数格納領域
【図１】
2008225739.tif 000003
【図２】
2008225739.tif 000004
【図３】
2008225739.tif 000005
【図４】
2008225739.tif 000006
【図５】
2008225739.tif 000007
【図６】
2008225739.tif 000008
【図７】
2008225739.tif 000009
【図８】
2008225739.tif 000010
【図９】
2008225739.tif 000011
【図１０】
2008225739.tif 000012
【図１１】
2008225739.tif 000013
【図１２】
2008225739.tif 000014
【図１３】
2008225739.tif 000015
【図１４】
2008225739.tif 000016
【図１５】
2008225739.tif 000017