(57)【特許請求の範囲】
【請求項１】
対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定手段と、
前記特定手段によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得手段と、
前記探索方向ごとに、前記取得手段によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断手段と、
前記探索窓ごとに、前記判断手段によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定手段と、
前記探索方向ごとに、前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定手段と、
前記決定手段によって前記探索方向ごとに決定された概頂点群を出力する出力手段と、
を備えることを特徴とする抽出装置。
【請求項２】
前記特定手段は、
前記判断手段によって続行しないと判断された特定の探索方向から前記所定角度よりさらに旋回した２つの方向への移動先となる第４および第５の探索窓候補と、を特定し、
前記取得手段は、
前記特定手段によって特定された前記第４および第５の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断手段は、
前記取得手段によって取得された前記第４および第５の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定手段は、
前記判断手段によって続行すると判断された場合、前記第４および第５の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定手段は、
前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする請求項１に記載の抽出装置。
【請求項３】
前記特定手段は、
前記探索窓の前記特定の探索方向への移動先となる第１の探索窓候補と、前記特定の探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、前記設定手段によって設定される前の探索窓から前記設定手段によって設定された前記探索窓への移動方向への移動先となる第６の探索窓候補と、を特定し、
前記取得手段は、
前記特定手段によって特定された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断手段は、
前記取得手段によって取得された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定手段は、
前記判断手段によって続行すると判断された場合、前記第１乃至第３の探索窓候補および前記第６の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定手段は、
前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする請求項２に記載の抽出装置。
【請求項４】
前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備え、
前記出力手段は、前記抽出手段によって抽出された多角形を出力することを特徴とする請求項１乃至３のいずれか一つに記載の抽出装置。
【請求項５】
前記出力手段は、
前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備えるコンピュータに、前記概頂点群を出力することを特徴とする請求項１乃至３のいずれか一つに記載の抽出装置。
【請求項６】
特定手段、取得手段、判断手段、設定手段、決定手段、および出力手段を備えるコンピュータが、
前記特定手段により、対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定工程と、
前記取得手段により、前記特定工程によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得工程と、
前記判断手段により、前記探索方向ごとに、前記取得工程によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断工程と、
前記設定手段により、前記探索窓ごとに、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定工程と、
前記決定手段により、前記探索方向ごとに、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定工程と、
前記出力手段により、前記決定工程によって前記探索方向ごとに決定された概頂点群を出力する出力工程と、
を実行することを特徴とする抽出方法。
【請求項７】
対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定工程と、
前記特定工程によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得工程と、
前記探索方向ごとに、前記取得工程によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断工程と、
前記探索窓ごとに、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定工程と、
前記探索方向ごとに、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定工程と、
前記決定工程によって前記探索方向ごとに決定された概頂点群を出力する出力工程と、
をコンピュータに実行させることを特徴とする抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報を抽出する抽出装置、抽出方法、および抽出プログラムに関する。
【背景技術】
【０００２】
近年、拡張現実（Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ）に代表されるように、実空間を撮像した画像や映像に対して、別の意味を持つ情報をコンピュータグラフィクス（Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）として実際の画像や映像に重畳して表示し、利用者にわかりやすく情報を提示するための装置が提案されている。
【０００３】
特に、無地の四角形（スクリーンと呼ぶ）を空間上に用意し、利用者に応じて異なる広告を、例えば、該装置が、ディスプレイに実空間を撮像した画像を出力する際に重畳して出力することで、広告価値を高めたりしている。この際には、画像から対応する空間上の四角形を抽出することが必要となる。
【０００４】
従来、画像中から四角形を抽出するための技術として、例えば、四角形の４つの頂点をユーザが操作部から指定することにより四角形を抽出する技術がある（例えば、下記特許文献１参照。）。
【０００５】
また、従来、画像中から四角形を自動的に抽出する技術として、例えば、直線を検出する技術であるＨｏｕｇｈ変換が利用されていた。Ｈｏｕｇｈ変換では、撮像した画像から求めたエッジ画像に基づいて直線を検出する。具体的には、Ｈｏｕｇｈ変換では、仮想した一本の直線上に載るエッジの数を数え、数が多ければ仮想した直線が実際の直線であると見なす。
【０００６】
このＨｏｕｇｈ変換により、該装置は、四角形の辺を構成する直線を全て検出することで、四角形を検出する（例えば、下記特許文献２，３参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４―４０３９５号公報
【特許文献２】特開２００８―２０４１２８号公報
【特許文献３】特開２００７―１８０８７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した特許文献２，３に記載の従来技術では、抽出すべき四角形とその背景とにエッジが出現する輝度差が大きなこと、および背景が一様であり抽出する直線よりも長い直線が存在しないことを仮定している。
【０００９】
従って、該装置が実空間を撮像した画像から無地の四角形を抽出する場合、背景が一様ではないため、抽出対象の四角形の辺に相当する直線を検出することができない。具体的には、例えば、スクリーン（抽出対象の四角形）を支える額の部分や、背景にあるスクリーン（抽出対象の四角形）に無関係な直線が四角形の辺に相当する直線より優先して検出されてしまう。
【００１０】
そのため、上述した特許文献１に記載の従来技術のようなユーザからの操作なしに、該装置が、透視投影による歪みを受けた実空間を撮像した画像上での四角形を自動的に抽出することは、困難であった。
【００１１】
従って、該装置が、撮像した画像中のスクリーンに広告を重畳してディスプレイに出力する際、広告を重畳すべきスクリーンの位置を誤認するという問題があった。また、スクリーンが四角形以外の多角形である場合にも同様に、該装置が、多角形の辺に相当する直線を検出できず、スクリーンの位置を誤認するという問題があった。
【００１２】
本発明は、かかる問題点に鑑み、抽出対象の多角形外の背景に影響されずに多角形またはその頂点を抽出する抽出装置、抽出方法、および抽出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決し、目的を達成するため、対象画像内から抽出すべき多角形の頂点の数分設定された対象画像内の開始点からの探索方向ごとに、探索窓の探索方向への移動先となる第１の探索窓候補と、探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定し、特定された第１〜第３の探索窓候補の各々の特徴量を対象画像から取得し、探索方向ごとに、取得された特徴量の各々と探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、探索窓ごとに、続行すると判断された場合、第１〜第３の探索窓候補のうち差分が最小となる探索窓候補を探索窓としてあらたに設定し、探索方向ごとに、続行しないと判断された場合、探索窓内の任意の点を、多角形を構成する概頂点に決定し、探索方向ごとに決定された概頂点群を出力する抽出装置、抽出方法、および抽出プログラムが、一例として提案される。
【発明の効果】
【００１４】
本発明にかかる抽出装置、抽出方法、および抽出プログラムによれば、抽出対象の多角形外の背景に影響されずに多角形またはその頂点を抽出することができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】抽出装置による多角形の抽出の内容を示す説明図である。
【図２】抽出装置のハードウェア構成を示すブロック図である。
【図３】抽出装置の機能ブロック図である。
【図４】積分画像の具体例を示す説明図である。
【図５】探索窓の移動の具体例を示す説明図である。
【図６】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その１）である。
【図７】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その２）である。
【図８】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その３）である。
【図９】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その４）である。
【図１０】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その５）である。
【図１１】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その６）である。
【図１２】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その７）である。
【図１３】実施例１にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その８）である。
【図１４】距離ｒにあるエッジ情報を選択する具体例を示す説明図である。
【図１５】実施例１にかかる抽出装置による四角形の詳細頂点の算出の具体例を示す説明図（その１）である。
【図１６】実施例１にかかる抽出装置による四角形の詳細頂点の算出の具体例を示す説明図（その２）である。
【図１７】実施例１にかかる抽出装置による四角形の詳細頂点の算出の具体例を示す説明図（その３）である。
【図１８】実施例１にかかる抽出処理の詳細を示すフローチャートである。
【図１９】実施例１にかかる概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図２０】実施例１にかかる概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図２１】実施例１にかかる積分画像生成処理の詳細を示すフローチャートである。
【図２２】実施例１にかかる左上概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図２３】実施例１にかかる左上概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図２４】実施例１にかかる右上概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図２５】実施例１にかかる右上概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図２６】実施例１にかかる左下概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図２７】実施例１にかかる左下概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図２８】実施例１にかかる右下概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図２９】実施例１にかかる右下概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図３０】実施例１にかかる詳細頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図３１】実施例１にかかる詳細頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図３２】実施例１にかかる上辺算出処理の詳細を示すフローチャートである。
【図３３】実施例１にかかる右辺算出処理の詳細を示すフローチャートである。
【図３４】実施例１にかかる下辺算出処理の詳細を示すフローチャートである。
【図３５】実施例１にかかる左辺算出処理の詳細を示すフローチャートである。
【図３６】実施例１にかかる辺算出処理の詳細を示すフローチャート（その１）である。
【図３７】実施例１にかかる辺算出処理の詳細を示すフローチャート（その２）である。
【図３８】実施例１にかかる左上頂点算出処理の詳細を示すフローチャートである。
【図３９】実施例１にかかる右上頂点算出処理の詳細を示すフローチャートである。
【図４０】実施例１にかかる右下頂点算出処理の詳細を示すフローチャートである。
【図４１】実施例１にかかる左下頂点算出処理の詳細を示すフローチャートである。
【図４２】実施例２にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その１）である。
【図４３】実施例２にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その２）である。
【図４４】実施例２にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その３）である。
【図４５】実施例２にかかる抽出装置による四角形の概頂点の算出の具体例を示す説明図（その４）である。
【図４６】実施例２にかかる概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図４７】実施例２にかかる概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図４８】実施例２にかかる左上概頂点位置副算出処理の詳細を示すフローチャートである。
【図４９】実施例２にかかる左上概頂点位置第一副算出処理の詳細を示すフローチャート（その１）である。
【図５０】実施例２にかかる左上概頂点位置第一副算出処理の詳細を示すフローチャート（その２）である。
【図５１】実施例２にかかる左上概頂点位置第二副算出処理の詳細を示すフローチャート（その１）である。
【図５２】実施例２にかかる左上概頂点位置第二副算出処理の詳細を示すフローチャート（その２）である。
【図５３】実施例２にかかる右上概頂点位置副算出処理の詳細を示すフローチャートである。
【図５４】実施例２にかかる右上概頂点位置第一副算出処理の詳細を示すフローチャート（その１）である。
【図５５】実施例２にかかる右上概頂点位置第一副算出処理の詳細を示すフローチャート（その２）である。
【図５６】実施例２にかかる右上概頂点位置第二副算出処理の詳細を示すフローチャート（その１）である。
【図５７】実施例２にかかる右上概頂点位置第二副算出処理の詳細を示すフローチャート（その２）である。
【図５８】実施例２にかかる左下概頂点位置副算出処理の詳細を示すフローチャートである。
【図５９】実施例２にかかる左下概頂点位置第一副算出処理の詳細を示すフローチャート（その１）である。
【図６０】実施例２にかかる左下概頂点位置第一副算出処理の詳細を示すフローチャート（その２）である。
【図６１】実施例２にかかる左下概頂点位置第二副算出処理の詳細を示すフローチャート（その１）である。
【図６２】実施例２にかかる左下概頂点位置第二副算出処理の詳細を示すフローチャート（その２）である。
【図６３】実施例２にかかる右下概頂点位置副算出処理の詳細を示すフローチャートである。
【図６４】実施例２にかかる右下概頂点位置第一副算出処理の詳細を示すフローチャート（その１）である。
【図６５】実施例２にかかる右下概頂点位置第一副算出処理の詳細を示すフローチャート（その２）である。
【図６６】実施例２にかかる右下概頂点位置第二副算出処理の詳細を示すフローチャート（その１）である。
【図６７】実施例２にかかる右下概頂点位置第二副算出処理の詳細を示すフローチャート（その２）である。
【図６８】実施例３にかかる抽出装置による多角形の抽出の具体例を示す説明図である。
【図６９】実施例３にかかる概頂点位置算出処理の詳細を示すフローチャートである。
【図７０】実施例３にかかるｍ番目概頂点位置算出処理の詳細を示すフローチャート（その１）である。
【図７１】実施例３にかかるｍ番目概頂点位置算出処理の詳細を示すフローチャート（その２）である。
【図７２】実施例３にかかる詳細頂点算出処理の詳細を示すフローチャート（その１）である。
【図７３】実施例３にかかる詳細頂点算出処理の詳細を示すフローチャート（その２）である。
【図７４】実施例３にかかるｍ番目辺算出処理の詳細を示すフローチャートである。
【図７５】実施例３にかかるｍ番目頂点算出処理の詳細を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して、本発明の実施の形態にかかる抽出装置、抽出方法、および抽出プログラムを詳細に説明する。
【００１７】
（抽出装置による多角形の抽出の内容）
まず、図１を用いて抽出装置による多角形の抽出の内容について説明する。図１は、抽出装置による多角形の抽出の内容を示す説明図である。ここでは、抽出装置は、実空間を撮像し、実空間内にスクリーンとして用意されている四角形の頂点を抽出する。また、スクリーンは無地であることを仮定する。
【００１８】
抽出装置が実空間を撮像した場合、図１の（Ａ）に示すような幅ｄｘ、高さｄｙの画像Ｉが入力される。画像Ｉには抽出対象であるスクリーン１０１が含まれるが、実空間上のスクリーン１０１が矩形であっても、撮像時の透視投影によりスクリーン１０１は歪んだ四角形となっている。また、画像Ｉには抽出対象であるスクリーン（四角形）１０１のほかに、スクリーン１０１の枠材や背景の模様が含まれる。また、画像Ｉでは、太陽光の照射やスクリーン１０１の汚れによって、スクリーン１０１の辺を構成する線分がとぎれている。
【００１９】
この画像Ｉに対して、抽出装置は、抽出対象の四角形１０１を抽出する処理を行う。まず、抽出装置は、（Ａ）に示すように、抽出対象であるスクリーン１０１の内部の点である探索開始点１０２から、四角形１０１の頂点数分の探索方向に向けて、探索窓Ｆを移動させ、四角形１０１のおおよその頂点１０３（以下、「概頂点」という）の位置を算出する。
【００２０】
具体的には、抽出装置は、探索窓Ｆの移動先となる複数の探索窓候補Ｆ１〜Ｆ３を用意し、探索窓候補Ｆ１〜Ｆ３のうち、四角形１０１の辺を越えない移動先となる探索窓候補へ探索窓Ｆを移動させていき、四角形１０１の頂点まで探索窓Ｆを移動させる。ここで、Ｆ１は探索方向への移動先となる探索窓候補であり、Ｆ２およびＦ３は探索方向から４５度旋回した２つの方向への移動先となる探索窓候補である。
【００２１】
（Ｂ）は、右上の概頂点１０３を算出する探索窓Ｆが移動先となる探索窓候補を判断する例を示している。例えば、（１）探索窓Ｆと探索窓候補Ｆ１〜Ｆ３とが四角形１０１内にある場合、抽出対象の四角形１０１が無地であることを仮定しているため、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値とに差は生じない。この場合には、抽出装置は、探索窓Ｆをどの移動先へ移動させても四角形１０１の辺を越えることはないと判断できるため、いずれかの移動先へ探索窓Ｆを移動させる。
【００２２】
また、（２）探索窓Ｆが四角形１０１の辺付近にある場合、探索窓候補Ｆ１およびＦ３が四角形１０１外にあるため、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１およびＦ３内の輝度総和値とに大きく差が生じる。一方で、探索窓候補Ｆ２は四角形１０１内にあるため、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ２内の輝度総和値とには差が生じない。この場合には、抽出装置は、探索窓Ｆを探索窓候補Ｆ２へ移動させれば四角形１０１の辺を越えることはないと判断できるため、探索窓候補Ｆ２へ探索窓Ｆを移動させる。
【００２３】
そして、（３）探索窓Ｆが四角形１０１の頂点付近にある場合、探索窓候補Ｆ１〜Ｆ３がすべて四角形１０１外にあるため、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値とに大きく差が生じる。この場合には、抽出装置は、探索窓Ｆの移動先は存在せず、頂点へ到達したと判断することができる。
【００２４】
従って、抽出装置は、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内のそれぞれの輝度総和値との差に基づいて、探索窓Ｆを四角形１０１の辺を越えないと判断された移動先へ移動させていくことにより、探索窓Ｆを四角形１０１の頂点付近まで移動させることができる。また、抽出装置は、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内のそれぞれの輝度総和値に基づいて、頂点付近まで移動したか否かを判断することができる。
【００２５】
そして、抽出装置は、頂点付近まで移動した探索窓Ｆの頂点のうち探索開始点１０２から最も遠い頂点を概頂点１０３として算出する。このように、抽出装置は、抽出対象である四角形１０１の内部の点から探索窓Ｆを移動させるため、枠材や背景の模様の存在にかかわらず概頂点１０３を算出することができる。
【００２６】
次に、抽出装置は、概頂点１０３からより詳細な頂点１０４（以下、「詳細頂点」という）の位置を算出する。具体的には、抽出装置は、（Ｃ）に示すように、各概頂点１０３を結ぶ線分の周辺部分のみを探索領域として、探索領域内のエッジ情報から四角形１０１の各辺を構成する直線を検出する。そして、抽出装置は、各辺の交点を詳細頂点１０４として算出する。抽出装置は、例えば、ＲＡＮＳＡＣ（ＲＡＮｄｏｍ  ＳＡｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ）法や最小二乗法といった従来技術を用いて、エッジ情報から直線を検出することができる。
【００２７】
なお、ＲＡＮＳＡＣ法については、Ｍ．  Ａ．  Ｆｉｓｃｈｌｅｒ，  Ｒ．  Ｃ．  Ｂｏｌｌｅｓ．らによって、「Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ：  Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｍｏｄｅｌ  Ｆｉｔｔｉｎｇ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｕｔｏｍａｔｅｄ  Ｃａｒｔｏｇｒａｐｈｙ．」（Ｃｏｍｍ．  ｏｆ  ｔｈｅ  ＡＣＭ，  Ｖｏｌ  ２４，  ｐｐ  ３８１―３９５，  １９８１．）に示されている。
【００２８】
このように、抽出装置は、各概頂点１０３を結ぶ線分の周辺部分のみのエッジ情報から四角形１０１の各辺を構成する直線を検出して詳細頂点１０４の座標を算出するため、枠材や背景の模様の存在にかかわらず詳細頂点１０４の座標を算出することができる。
【００２９】
（抽出装置のハードウェア構成）
次に、図２を用いて抽出装置のハードウェア構成について説明する。
【００３０】
図２は、抽出装置のハードウェア構成を示すブロック図である。図２において、抽出装置２００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、記憶装置２０２と、撮像装置２０３と、ディスプレイ２０４と、を備えている。また、各構成部は、バス２０５によってそれぞれ接続されている。
【００３１】
ＣＰＵ２０１は、抽出装置２００全体の制御を司る。記憶装置２０２は、抽出プログラムを記憶している。記憶装置２０２としては、不揮発性メモリやフラッシュメモリ、ハードディスクドライブなどを採用することができる。
【００３２】
撮像装置２０３は、光学的な映像を電気信号に変換し、記憶装置２０２に保持する。この撮像装置２０３は、例えば、ＣＣＤ（Ｃｈａｒｇｅ  Ｃｏｕｐｌｅｄ  Ｄｅｖｉｃｅ）、ＣＭＯＳ（Ｃｏｍｐｌｅｍｅｎｔａｒｙ  Ｍｅｔａｌ―Ｏｘｉｄｅ  Ｓｅｍｉｃｏｎｄｕｃｔｏｒ）センサなどの光学的な映像を電気信号に変換する光電変換素子を有するビデオカメラを採用できる。
【００３３】
ディスプレイ２０４は、カーソル、アイコンあるいはツールボックスをはじめ、文章、画像、機能情報等のデータを表示する。このディスプレイ２０４は、例えば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイ等を採用することができる。
【００３４】
（抽出装置２００の機能的構成）
次に、図３を用いて抽出装置２００の機能的構成について説明する。
【００３５】
図３は、抽出装置の機能ブロック図である。図３に示すように、抽出装置２００は、特定部３０１と、取得部３０２と、判断部３０３と、設定部３０４と、決定部３０５と、出力部３０６と、抽出部３０７と、を備える。
【００３６】
特定部３０１は、対象画像内から抽出すべき多角形の頂点の数分設定された対象画像内の開始点からの探索方向ごとに、探索窓の探索方向への移動先となる第１の探索窓候補と、探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する機能を有する。
【００３７】
ここで、開始点とは、上述した探索窓Ｆの探索開始時の座標を示す点であり、探索対象となる多角形の内部の点である。この開始点の座標は、記憶装置２０２に保持されている。開始点としては、例えば、画像Ｉの中心の点が採用される。探索方向とは、探索対象となる多角形の頂点数分の方向であって、例えば、四角形１０１では、９０度ずつ旋回した４つの方向となる。
【００３８】
また、第１の探索窓候補とは、上述した複数の探索窓候補のうち探索方向に所定のステップ幅進んだ位置における探索窓候補である。すなわち、第１の探索窓候補とは、上述した探索窓候補Ｆ１である。
【００３９】
第２の探索窓候補とは、上述した複数の探索窓候補のうち探索方向から所定角度旋回した方向に所定のステップ幅分進んだ位置における探索窓である。例えば、四角形１０１では、探索方向から＋４５度旋回した方向の探索窓候補である。すなわち、第２の探索窓候補とは、上述した探索窓候補Ｆ２である。第３の探索窓候補とは、上述した複数の探索窓候補のうち探索方向から所定角度旋回した方向に所定のステップ幅分進んだ位置における探索窓候補である。例えば、四角形１０１では、探索方向から−４５度旋回した方向の探索窓候補である。すなわち、第３の探索窓候補とは、上述した探索窓候補Ｆ３である。
【００４０】
具体的には、例えば、特定部３０１は、探索窓Ｆの座標からステップ幅に基づいて、探索窓候補Ｆ１〜Ｆ３の座標を特定する。そして、特定した探索窓候補Ｆ１〜Ｆ３の座標を記憶装置２０２に保持する。これにより、特定部３０１は、探索窓Ｆの移動先とする探索窓候補Ｆ１〜Ｆ３の座標を特定することができる。
【００４１】
特定部３０１は、判断部３０３によって続行しないと判断された特定の探索方向から所定角度よりさらに旋回した２つの方向への移動先となる第４および第５の探索窓候補と、を特定する機能を有する。ここで、特定の探索方向とは、上述した探索方向のうち、後述する判断部３０３によって探索を中断された探索方向である。
【００４２】
第４の探索窓候補とは、第１から第３の探索窓候補に移動先がない場合に、あらたに移動先として検討される探索窓候補である。例えば、四角形１０１では、探索方向から＋９０度旋回した方向の探索窓候補である。すなわち、第４の探索窓候補とは、後述する探索窓候補Ｆ４である。第５の探索窓候補とは、第１から第３の探索窓候補に移動先がない場合に、あらたに移動先として検討される探索窓候補である。例えば、四角形１０１では、探索方向から−９０度旋回した方向の探索窓候補である。すなわち、第５の探索窓候補とは、後述する探索窓候補Ｆ５である。
【００４３】
具体的には、例えば、特定部３０１は、判断部３０３によって探索窓Ｆが頂点付近に到達したと誤認された場合に、探索窓Ｆの座標からステップ幅に基づいて、あらたな探索窓候補Ｆ４およびＦ５内の座標を特定する。そして、特定した探索窓候補Ｆ４およびＦ５の座標を記憶装置２０２に保持する。これにより、特定部３０１は、判断部３０３が四角形１０１の辺を概頂点１０３として誤認した場合に、辺に沿った別の移動先を特定することができる。
【００４４】
また、特定部３０１は、探索窓の特定の探索方向への移動先となる第１の探索窓候補と、特定の探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、設定部３０４によって設定される前の探索窓から設定部３０４によって設定された探索窓への移動方向への移動先となる第６の探索窓候補と、を特定する機能を有する。ここで、特定の探索方向とは、後述する判断部３０３によって探索が中断された探索方向である。第６の探索窓候補とは、上述した第４および第５の探索窓候補のうち後述する設定部３０４によってあらたな移動先候補として設定された探索窓候補である。
【００４５】
具体的には、例えば、特定部３０１は、探索窓候補Ｆ１〜Ｆ３内および探索窓候補Ｆ４またはＦ５の座標を特定する。そして、特定した探索窓候補Ｆ１〜Ｆ３および探索窓候補Ｆ４またはＦ５の座標を記憶装置２０２に保持する。これにより、特定部３０１は、探索窓Ｆの移動先とする探索窓候補Ｆ１〜Ｆ３および探索窓候補Ｆ４またはＦ５の座標を特定することができる。
【００４６】
特定部３０１は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００４７】
取得部３０２は、特定部３０１によって特定された第１〜第６の探索窓候補の各々の特徴量を対象画像から取得する機能を有する。ここで、特徴量とは、上述した輝度総和値である。
【００４８】
具体的には、例えば、取得部３０２は、画像Ｉから積分画像を生成し、積分画像に基づいて探索窓候補Ｆ１〜Ｆ５内の輝度総和値を算出する。そして、取得部３０２は、算出した輝度総和値を記憶装置２０２に保持する。積分画像および積分画像に基づく探索窓内の輝度総和値の算出については従来技術であるため、ここでは詳細な説明を省略する。
【００４９】
なお、この従来技術については、Ｐａｕｌ  Ｖｉｏｌａ，  Ｍｉｃｈａｅｌ  Ｊｏｎｅｓらによって「‘‘Ｒｏｂｕｓｔ  Ｒｅａｌ−ｔｉｍｅ  Ｏｂｊｅｃｔ  Ｄｅｔｅｃｔｉｏｎ，’’」（Ｐｒｏｃ．  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｔａｔｉｓｔｉｃａｌ  ａｎｄ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｔｈｅｏｒｉｅｓ  ｏｆ  Ｖｉｓｉｏｎ  ―  Ｍｏｄｅｌｉｎｇ，  Ｌｅａｒｎｉｎｇ，  Ｃｏｍｐｕｔｉｎｇ，  ａｎｄ  Ｓａｍｐｌｉｎｇ  （２００１）．）に示されている。
【００５０】
これにより、取得部３０２は、探索窓候補Ｆ１〜Ｆ５内の輝度総和値を取得することができ、判断部３０３に探索窓Ｆの移動先となる探索窓候補を判断させることができる。
【００５１】
取得部３０２は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００５２】
判断部３０３は、探索方向ごとに、取得部３０２によって取得された第１〜第３の探索窓候補の特徴量の各々と探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する機能を有する。
【００５３】
具体的には、例えば、判断部３０３は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値のそれぞれとの差が閾値より大きい場合に、探索を続行しないと判断する。これにより、判断部３０３は、探索窓Ｆが多角形の頂点付近に到達したか否かを判断することができ、探索を続行するか否か判断することができる。閾値は、抽出装置２００のユーザや製造者によって予め記憶装置２０２に保持されている。
【００５４】
また、判断部３０３は、取得部３０２によって取得された第４および第５の探索窓候補の特徴量の各々と探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する機能を有する。
【００５５】
具体的には、例えば、判断部３０３は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ４およびＦ５内の輝度総和値のそれぞれとの差が閾値より大きい場合に、探索を続行しないと判断する。これにより、判断部３０３は、探索窓Ｆが多角形の頂点付近に到達したか否かを判断することができ、探索を続行するか否か判断することができる。閾値は、抽出装置２００のユーザや製造者によって予め記憶装置２０２に保持されている。
【００５６】
また、判断部３０３は、取得部３０２によって取得された第１〜第３の探索窓候補および第６の探索窓候補の特徴量の各々と探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する機能を有する。
【００５７】
具体的には、例えば、判断部３０３は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値のそれぞれとの差および探索窓Ｆ内の輝度総和値と後述する設定部３０４によってあらたな移動先候補として設定された探索窓候補内の輝度総和値との差が閾値より大きい場合に、探索を続行しないと判断する。これにより、判断部３０３は、探索窓Ｆが多角形の頂点付近に到達したか否かを判断することができ、探索を続行するか否か判断することができる。閾値は、抽出装置２００のユーザや製造者によって予め記憶装置２０２に保持されている。
【００５８】
判断部３０３は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００５９】
設定部３０４は、探索窓ごとに、判断部３０３によって続行すると判断された場合、第１〜第３の探索窓候補のうち差分が最小となる探索窓候補を探索窓としてあらたに設定する機能を有する。
【００６０】
具体的には、例えば、設定部３０４は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値のそれぞれとの差が最小である探索窓候補をあらたな探索窓Ｆとして設定する。すなわち、探索窓Ｆの座標を、探索窓候補Ｆ１〜Ｆ３のうち、該差が最小である探索窓候補の記憶装置２０２に保持されている座標に書き換える。これにより、設定部３０４は、探索窓Ｆがまだ頂点付近に到達していない場合に、探索窓Ｆを四角形１０１の辺を越えないように移動させることができる。
【００６１】
設定部３０４は、判断部３０３によって続行すると判断された場合、第４および第５の探索窓候補のうち差分が最小となる探索窓候補を探索窓としてあらたに設定する機能を有する。
【００６２】
具体的には、例えば、設定部３０４は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ４およびＦ５内の輝度総和値のそれぞれとの差が閾値以下の探索窓候補のうち、その差が最小である探索窓候補をあらたな探索窓Ｆとして設定する。すなわち、探索窓Ｆの座標を、探索窓候補Ｆ１〜Ｆ３のうち、該差が最小である探索窓候補の記憶装置２０２に保持されている座標に書き換える。これにより、設定部３０４は、探索窓Ｆがまだ頂点付近に到達していない場合に、探索窓Ｆを辺に沿って移動させることができる。
【００６３】
また、設定部３０４は、判断部３０３によって続行すると判断された場合、第１〜第３の探索窓候補および第６の探索窓候補のうち差分が最小となる探索窓候補を探索窓としてあらたに設定する機能を有する。
【００６４】
具体的には、例えば、設定部３０４は、取得部３０２が記憶装置２０２に保持した探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内の輝度総和値のそれぞれとの差および探索窓Ｆ内の輝度総和値と後述する設定部３０４によってあらたな移動先候補として設定された探索窓候補内の輝度総和値との差が最小である探索窓候補をあらたな探索窓として設定する。すなわち、探索窓Ｆの座標を、探索窓候補Ｆ１〜Ｆ３のうち、該差が最小である探索窓候補の記憶装置２０２に保持されている座標に書き換える。これにより、設定部３０４は、探索窓Ｆがまだ頂点付近に到達していない場合に、探索窓Ｆを四角形１０１の辺を越えないように移動させることができる。
【００６５】
設定部３０４は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００６６】
決定部３０５は、探索方向ごとに、判断部３０３によって続行しないと判断された場合、探索窓内の任意の点を、多角形を構成する概頂点１０３に決定する機能を有する。
【００６７】
具体的には、例えば、決定部３０５は、判断部３０３によって移動先となる探索窓候補がないと判断された場合に、探索窓内の任意の点を概頂点１０３として決定する。概頂点１０３としては、例えば、探索窓内の点のうち、探索開始点１０２から最も遠い距離にある点を採用できる。そして、決定部３０５は、決定した概頂点１０３を記憶装置２０２に保持する。これにより、決定部３０５は、探索窓Ｆが頂点付近にたどり着いた場合に概頂点１０３を決定することができる。
【００６８】
決定部３０５は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００６９】
出力部３０６は、決定部３０５によって探索方向ごとに決定された概頂点群を出力する機能を有する。具体的には、例えば、出力部３０６は、決定部３０５が記憶装置２０２に保持した概頂点群を出力する。これにより、出力部３０６は、概頂点の座標を出力することができる。
【００７０】
また、出力部３０６は、抽出部３０７によって抽出された多角形を出力する機能を有する。具体的には、例えば、出力部３０６は、抽出部３０７が記憶装置２０２に保持した詳細頂点１０４から構成される多角形を出力する。これにより、出力部３０６は、詳細頂点１０４を結んでできた多角形を出力することができる。
【００７１】
また、出力部３０６は、概頂点群の中から多角形を構成する辺の両端となる一対の概頂点１０３の間におけるエッジ情報を、一対の概頂点１０３ごとに対象画像から取得することにより、一対の概頂点１０３ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出部３０７を備えるコンピュータに、概頂点群を出力する機能を有する。ここで、エッジ情報とは、画像Ｉのエッジを抽出して二値化した二値画像ＥＢの各座標における情報である。
【００７２】
具体的には、例えば、出力部３０６は、決定部３０５が記憶装置２０２に保持した概頂点１０３を抽出部３０７を備えるコンピュータに出力する。これにより、出力部３０６は、概頂点１０３の座標を抽出部３０７に出力し、抽出部３０７に詳細頂点１０４を抽出させることができる。
【００７３】
出力部３０６は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。これにより、出力部３０６は、算出した概頂点群を出力することができる。
【００７４】
抽出部３０７は、概頂点群の中から多角形を構成する辺の両端となる一対の概頂点１０３の間におけるエッジ情報を、一対の概頂点１０３ごとに対象画像から取得することにより、一対の概頂点１０３ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する機能を有する。
【００７５】
具体的には、例えば、抽出部３０７は、画像Ｉから二値画像ＥＢを生成する。次に、抽出部３０７は、二値画像ＥＢのエッジ情報のうち、記憶装置２０２に保持されている一対の概頂点１０３を結ぶ線分から一定距離にあるエッジ情報のみから、多角形の辺を構成する直線を検出する。そして、抽出部３０７は、それらの辺の交点を、詳細頂点１０４の座標として抽出する。抽出部３０７は、抽出した詳細頂点１０４の座標を記憶装置２０２に保持する。これにより、抽出部３０７は、多角形の詳細頂点１０４の座標を算出することができる。
【００７６】
抽出部３０７は、具体的には、例えば、図２に示した記憶装置２０２に記憶された抽出プログラムをＣＰＵ２０１に実行させることにより、その機能を実現する。
【００７７】
次に、探索窓Ｆ内および探索窓候補Ｆ１〜Ｆ３内の輝度総和値の算出に用いる積分画像の生成と、探索窓Ｆ内および探索窓候補Ｆ１〜Ｆ３内の輝度総和値の算出について説明する。
【００７８】
図４は積分画像の具体例を示す説明図である。ここで、抽出装置２００に、画像Ｉが入力されたとする。（Ａ）は、画像Ｉの各座標（ｘ，ｙ）での輝度値を表している。なお、ここでは、簡単のため、画像Ｉの輝度値は０と１の２種類であるとする。
【００７９】
抽出装置２００は、（Ａ）の画像から、積分画像を生成する。ここで、（Ｂ）に示すように積分画像は各座標における原点から各座標までの輝度値の積分値を表している。例えば、積分画像の座標（１，１）では、画像の原点（０，０）から座標（１，１）までの輝度値の積分値が保持される。すなわち、画像における原点（０，０）の輝度値１と、座標（０，１）の輝度値１と、座標（１，０）の輝度値０と、座標（１，１）の輝度値１との総和３が積分画像の座標（１，１）に保持される。
【００８０】
抽出装置２００は、この積分画像を用いて、左上座標（ｐｘ１，ｐｙ１）と右下座標（ｐｘ２，ｐｙ２）を対角とする探索窓Ｆ内の輝度総和値を算出することができる。具体的には、輝度総和値Ｉｎｔ（ｐｘ１，ｐｙ１，ｐｘ２，ｐｙ２）は下記式１により与えられる。
【００８１】
【数１】
0005569364.tif 000002
【００８２】
ここで、ＩＩ（ｘ，ｙ）は原点（０，０）から画像Ｉの座標（ｘ，ｙ）までの輝度の積分値を示す。ただし、ＩＩ（ｘ，ｙ）のｘ座標またはｙ座標のいずれかが負である場合にはＩＩ（ｘ，ｙ)＝０とする。
【００８３】
例えば、探索窓Ｆの左上座標が（２，２）、右下座標が（４，４）であるとした場合について説明する。抽出装置２００は、右下座標（４，４）での積分値１６に、座標（１，１）での積分値３を加算し、さらに座標（１，４）での積分値６と座標（４，１）での積分値７を減算して、探索窓Ｆ内の輝度総和値を算出することができる。
【００８４】
次に、この輝度総和値を用いて探索窓を移動させる具体例について説明する。図５は探索窓の移動の具体例を示す説明図である。ここでは、Ｍ０は探索窓Ｆ内の輝度総和値を示す。また、Ｍ１、Ｍ２、Ｍ３はそれぞれ探索窓候補Ｆ１〜Ｆ３内の輝度総和値を示す。また、以下では、図中のｘ軸、ｙ軸の矢印の向きを正の方向とする。
【００８５】
ここで、左上の概頂点１０３を算出する探索窓Ｆの移動を例として説明する。探索窓Ｆの座標を（ｄｘ，ｄｙ）とする。また、ｘ軸方向へのステップ幅をｗｘとし、ｙ軸方向へのステップ幅をｗｙとする。そして、探索窓のｘ軸方向のサイズをｆｘとし、ｙ軸方向のサイズをｆｙとする。よって、Ｆ１の座標は（ｄｘ−ｗｘ，ｄｙ−ｗｙ）、Ｆ２の座標は（ｄｘ−ｗｘ，ｄｙ）、Ｆ３の座標は（ｄｘ，ｄｙ−ｗｙ）となる。なお、探索窓Ｆと探索窓候補の座標とはそれぞれの中心の座標をいう。
【００８６】
ここで、例えば、探索窓Ｆ内の輝度総和値を算出する場合、まず、探索窓Ｆの左上座標（ｐｘ１，ｐｙ１）と右下座標（ｐｘ２，ｐｙ２）を算出する。そして、算出した探索窓Ｆの左上座標と右下座標を上述した式１に代入することにより、探索窓Ｆ内の輝度総和値を算出する。
【００８７】
探索窓Ｆの左上座標（ｐｘ１，ｐｙ１）は、探索窓Ｆの中心座標（ｄｘ，ｄｙ）と探索窓Ｆのサイズｄｘ、ｄｙを用いて、（ｄｘ−ｆｘ／２，ｄｙ−ｆｙ／２）で表される。また、探索窓Ｆの右下座標（ｐｘ２，ｐｙ２）は、探索窓Ｆの中心座標（ｄｘ，ｄｙ）と探索窓Ｆのサイズｄｘ、ｄｙを用いて、（ｄｘ＋ｆｘ／２，ｄｙ＋ｆｙ／２）で表される。
【００８８】
従って、探索窓Ｆの輝度総和値は、上記式（１）に探索窓Ｆの左上座標（ｐｘ１，ｐｙ１）＝（ｄｘ−ｆｘ／２，ｄｙ−ｆｙ／２）と右下座標（ｐｘ２，ｐｙ２）＝（ｄｘ＋ｆｘ／２，ｄｙ＋ｆｙ／２）を代入すれば算出できる。すなわち、探索窓Ｆ内の輝度総和値は、ＩＩ（ｄｘ−ｆｘ／２−１，ｄｙ−ｆｙ／２−１）＋ＩＩ（ｄｘ＋ｆｘ／２，ｄｙ＋ｆｙ／２）−ＩＩ（ｄｘ＋ｆｘ／２，ｄｙ−ｆｙ／２−１）−ＩＩ（ｄｘ−ｆｘ／２−１，ｄｙ＋ｆｙ／２）となる。探索窓候補Ｆ１〜Ｆ３についても同様に輝度総和値を算出することができる。
【００８９】
このようにして算出した輝度総和値Ｍ０〜Ｍ３を用いて、抽出装置２００は、探索窓Ｆを移動させていく。例えば、（Ａ）に示す場合では、スクリーン（四角形１０１）が無地であることを仮定しているため、移動先となる探索窓候補Ｆ１〜Ｆ３内の輝度総和値Ｍ１〜Ｍ３のいずれも探索窓Ｆ内の輝度総和値Ｍ０と同等の値となる。この場合には、抽出装置２００は、探索窓Ｆをどの移動先へ移動させても探索窓Ｆは四角形１０１の内部にあると判断できるため、いずれかの移動先へ探索窓Ｆを移動させる。例えば、抽出装置２００は、探索開始点１０２から最も遠い探索窓候補Ｆ１の座標（ｄｘ−ｗｘ，ｄｙ−ｗｙ）をあらたな探索窓Ｆの座標（ｄｘ，ｄｙ）とする。
【００９０】
一方、（Ｂ）に示す場合では、探索窓候補Ｆ１およびＦ３が背景領域を多く含み、探索窓候補Ｆ１およびＦ３内の輝度総和値Ｍ１およびＭ３と探索窓Ｆ内の輝度総和値Ｍ０との間に大きく差が生じる。しかし、探索窓候補Ｆ２内の輝度総和値Ｍ２と探索窓Ｆ内の輝度総和値Ｍ１とが同等の値となる。この場合には、抽出装置２００は、探索窓Ｆを探索窓候補Ｆ２の座標へ移動させれば背景領域とスクリーンの境界（四角形１０１の辺）を越えることはないと判断できる。そのため、探索窓候補Ｆ２の座標（ｄｘ，ｄｙ−ｗｙ）をあらたな探索窓Ｆの座標（ｄｘ，ｄｙ）とする。
【００９１】
そして、（Ｃ）に示す場合では、探索窓候補Ｆ１〜Ｆ３内の輝度総和値Ｍ１〜Ｍ３のいずれも探索窓Ｆ内の輝度総和値Ｍ０と大きく差が生じる。この場合、抽出装置２００は、探索窓Ｆが頂点付近に到達したと判断して探索窓Ｆの移動を終了する。
【００９２】
このように、抽出装置２００は、四角形１０１の辺を越えないように探索窓Ｆを移動させ、探索窓Ｆが頂点付近に到達した場合には探索窓Ｆの移動を終了することができる。また、（Ｂ）に示すように四角形１０１の辺に直線でない部分があっても、抽出装置２００は、探索窓候補内の輝度総和値に基づいて判断を行うため、探索窓Ｆを辺に沿って移動させることができる。
【００９３】
（実施例１）
実施例１は、抽出する多角形として四角形１０１を対象とした場合における抽出装置２００の実施例である。ここで、図６〜１３を用いて、四角形１０１の概頂点１０３の抽出について説明する。
【００９４】
図６〜１３は、実施例１にかかる抽出装置による四角形１０１の概頂点１０３の算出の具体例を示す説明図である。まず、図６の（Ａ）に示すように、抽出装置２００は、左上概頂点１０３を抽出するために、探索開始点１０２から探索窓Ｆを移動させ始める。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ３へ探索窓Ｆを移動する。
【００９５】
次に、図６の（Ｂ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ３へ探索窓Ｆを移動する。
【００９６】
そして、図７の（Ａ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ２へ探索窓Ｆを移動する。
【００９７】
ここで、図７の（Ｂ）に示すように、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち移動できる探索窓候補が存在しないため、探索窓Ｆの左上頂点を抽出対象の四角形１０１の左上概頂点１０３として算出する。
【００９８】
次に、図８の（Ａ）に示すように、抽出装置２００は、右上概頂点１０３を抽出するために、探索開始点１０２から探索窓Ｆを移動させ始める。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ２へ探索窓Ｆを移動する。
【００９９】
そして、図８の（Ｂ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ２へ探索窓Ｆを移動する。
【０１００】
次に、図９の（Ａ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ３へ探索窓Ｆを移動する。
【０１０１】
ここで、図９の（Ｂ）に示すように、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち移動できる探索窓候補が存在しないため、探索窓Ｆの右上頂点を抽出対象の四角形１０１の右上概頂点１０３として算出する。
【０１０２】
次に、図１０の（Ａ）に示すように、抽出装置２００は、左下概頂点１０３を抽出するために、探索開始点１０２から探索窓Ｆを移動させ始める。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ２へ探索窓Ｆを移動する。
【０１０３】
そして、図１０の（Ｂ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ２へ探索窓Ｆを移動する。
【０１０４】
次に、図１１の（Ａ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ３へ探索窓Ｆを移動する。
【０１０５】
ここで、図１１の（Ｂ）に示すように、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち移動できる探索窓候補が存在しないため、探索窓Ｆの左下頂点を抽出対象の四角形１０１の左下概頂点１０３として算出する。
【０１０６】
次に、図１２の（Ａ）に示すように、抽出装置２００は、右下概頂点１０３を抽出するために、探索開始点１０２から探索窓Ｆを移動させ始める。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ３へ探索窓Ｆを移動する。
【０１０７】
そして、図１２の（Ｂ）に示すように、抽出装置２００は、移動後の座標からさらに探索窓Ｆを移動させる。ここでは、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち輝度総和値が最も小さい移動先となる探索窓候補Ｆ１へ探索窓Ｆを移動する。
【０１０８】
次に、図１３に示すように、抽出装置２００は、移動先の探索窓候補Ｆ１〜Ｆ３のうち移動できる探索窓候補が存在しないため、探索窓Ｆの右下頂点を抽出対象の四角形１０１の右下概頂点１０３として算出する。このように、探索窓候補内の輝度総和値に基づいて探索窓Ｆを移動させるため、四角形１０１の辺に途切れがあっても、抽出装置２００は、概頂点１０３を算出することができる。
【０１０９】
このようにして、実施例１にかかる抽出装置２００は抽出対象である四角形１０１の各概頂点１０３を算出することができる。
【０１１０】
次に、抽出装置２００は、概頂点１０３に基づいて、抽出対象の四角形１０１の詳細頂点１０４の座標を算出する。まず、抽出装置２００は、詳細頂点１０４の座標を算出するために、抽出対象の四角形１０１の辺を構成する直線を検出する。ここで、抽出装置２００は、四角形１０１の辺が各概頂点１０３を結んだ線分の周辺に存在するという性質を利用して、四角形１０１外の背景に影響されずに四角形１０１の辺を抽出する。
【０１１１】
具体的には、抽出装置２００は、画像Ｉに対してエッジ抽出を行い画像Ｅを生成し、この画像Ｅに対して二値化を行い特定のエッジ強度の画素のみを２５５、それ以外を０として、二値画像ＥＢを生成する。エッジ抽出の方法としては、例えばＳｏｂｅｌオペレータを利用することができる。
【０１１２】
そして、線分から、距離ｒ以下に存在するエッジ情報のみを対象にして、ＲＡＮＳＡＣ法を適用し、四角形１０１の辺を構成する直線を検出する。ＲＡＮＳＡＣ法は周知技術であるため、ここでは、詳細な説明を省略する。
【０１１３】
なお、ＲＡＮＳＡＣ法については、Ｍ．  Ａ．  Ｆｉｓｃｈｌｅｒ，  Ｒ．  Ｃ．  Ｂｏｌｌｅｓ．らによって、「Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ：  Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｍｏｄｅｌ  Ｆｉｔｔｉｎｇ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｕｔｏｍａｔｅｄ  Ｃａｒｔｏｇｒａｐｈｙ．」（Ｃｏｍｍ．  ｏｆ  ｔｈｅ  ＡＣＭ，  Ｖｏｌ  ２４，  ｐｐ  ３８１―３９５，  １９８１．）に示されている。
【０１１４】
ここで、座標（ｘ１，ｙ１）と座標（ｘ２，ｙ２）の２つの概頂点１０３を結ぶ線分から距離ｒにあるエッジ情報を選択する具体例について説明する。
【０１１５】
図１４は、距離ｒにあるエッジ情報を選択する具体例を示す説明図である。最初に、［ｘ２−ｘ１， ｙ２−ｙ１］Ｔを正規化した大きさが１の単位ベクトルをｖとし、それに直交するベクトルをｕとする。具体的には、ｖ、ｕは下記式（２）で表される。
【０１１６】
【数２】
0005569364.tif 000003
【０１１７】
ここで、Ｔは転置ベクトルまたは転置行列を表し、ｑは下記式（３）で表される規格化定数とする。ただし、ｓｑｒｔは平方根を表す。
【０１１８】
【数３】
0005569364.tif 000004
【０１１９】
また、任意の点（ｘ，ｙ）の直線からの距離ｄと（ｘ１，ｙ１）からの垂線の足までの距離ｌは下記式（４）で表される。
【０１２０】
【数４】
0005569364.tif 000005
【０１２１】
よって、点（ｘ，ｙ）の線分からの距離は、ｌ＞＝０かつｌ＜＝ｑのときはｄで表される。また、点（ｘ，ｙ）の線分からの距離は、ｌ＜０のときはｓｑｒｔ（（ｘ−ｘ１)＊（ｘ−ｘ１）＋（ｙ−ｙ１）＊（ｙ−ｙ１））で表される。そして、点（ｘ，ｙ）の線分からの距離は、ｌ＞ｑのときはｓｑｒｔ（（ｘ−ｘ２)＊（ｘ−ｘ２）＋（ｙ−ｙ２）＊（ｙ−ｙ２））で表される。
【０１２２】
抽出装置２００は、上記距離がｒ以下の点（ｘ，ｙ）のエッジ情報のみを選択して、直線の検出に使用する。この場合にエッジ情報の選択の対象となる領域を図１４に示す。ここでは、概頂点１０３と詳細頂点１０４とのずれに対してすべての方向に対応するために、概頂点１０３の座標（ｘ１，ｙ１）と概頂点１０３の座標（ｘ２，ｙ２）を中心とした半円も領域に含んでいる。
【０１２３】
次に、図１５〜１７を用いて、実施例１にかかる抽出装置による四角形１０１の詳細頂点１０４の算出の具体例について説明する。図１５〜１７は、実施例１にかかる抽出装置による四角形１０１の詳細頂点１０４の算出の具体例を示す説明図である。
【０１２４】
まず、図１５の（Ａ）に示すように、抽出装置２００は、左上概頂点１０３と右上概頂点１０３との座標を結んだ線分の周辺のエッジ情報のみに基づいて上辺を構成する直線を検出する。次に、図１５の（Ｂ）に示すように、抽出装置２００は、右上概頂点１０３と右下概頂点１０３との座標を結んだ線分の周辺のエッジ情報のみに基づいて右辺を構成する直線を検出する。
【０１２５】
そして、図１６の（Ａ）に示すように、抽出装置２００は、左下概頂点１０３と右下概頂点１０３との座標を結んだ線分の周辺のエッジ情報のみに基づいて下辺を構成する直線を検出する。最後に、図１６の（Ｂ）に示すように、抽出装置２００は、左上概頂点１０３と左下概頂点１０３との座標を結んだ線分の周辺のエッジ情報のみに基づいて左辺を構成する直線を検出する。
【０１２６】
次に、図１７に示すように、抽出装置２００は、各辺を構成する直線の交点を詳細頂点１０４の座標として算出する。このようにして、実施例１にかかる抽出装置２００は、抽出対象の四角形１０１の詳細頂点１０４の座標を算出することができる。
【０１２７】
（実施例１にかかる抽出装置２００による抽出処理の詳細）
次に、実施例１にかかる抽出装置２００による抽出処理の詳細について説明する。図１８は、実施例１にかかる抽出処理の詳細を示すフローチャートである。まず、ＣＰＵ２０１は、画像Ｉを撮像し、撮像した画像Ｉを記憶装置２０２に保持する（ステップＳ１８０１）。次に、ＣＰＵ２０１は、図１９，図２０を用いて後述する概頂点位置算出処理を行い、概頂点１０３の座標を算出する（ステップＳ１８０２）。そして、ＣＰＵ２０１は、図３０，図３１を用いて後述する詳細頂点位置算出処理を行い、詳細頂点の座標を算出して（ステップＳ１８０３）、抽出処理を終了する。これにより、抽出対象の四角形１０１を抽出することができる。
【０１２８】
次に、図１８のステップＳ１８０２に示した概頂点位置算出処理について説明する。図１９，図２０は実施例１にかかる概頂点位置算出処理の詳細を示すフローチャートである。ここでは、予め探索開始点１０２の総数Ｎ、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）、探索窓Ｆのｘ軸方向のサイズｆｘとｙ軸方向のサイズｆｙ、探索窓Ｆのｘ軸方向のステップ幅ｗｘとｙ軸方向のステップ幅ｗｙが記憶装置２０２に保持されているとする。
【０１２９】
まず、ＣＰＵ２０１は、図２１を用いて後述する積分画像生成処理を行い、記憶装置２０２に保持されている画像Ｉから積分画像を生成し（ステップＳ１９０１）、生成した積分画像を記憶装置２０２に保持する。そして、ＣＰＵ２０１は、探索開始点番号ｎを０にセットする（ステップＳ１９０２）。
【０１３０】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を左上概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ１９０３）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から左上概頂点位置算出処理を行い（ステップＳ１９０４）、処理後の探索窓Ｆの左上頂点の座標（ｐｘ，ｐｙ）を左上概頂点１０３の座標（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）として算出する（ステップＳ１９０５）。
【０１３１】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を右上概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ１９０６）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から右上概頂点位置算出処理を行い（ステップＳ１９０７）、処理後の探索窓Ｆの右上頂点の座標（ｐｘ，ｐｙ）を右上概頂点１０３の座標（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）として算出し（ステップＳ１９０８）、図２０のステップＳ２００１に進む。
【０１３２】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を左下概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ２００１）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から左下概頂点位置算出処理を行い（ステップＳ２００２）、処理後の探索窓Ｆの左下頂点の座標（ｐｘ，ｐｙ）を左下概頂点１０３の座標（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）として算出する（ステップＳ２００３）。
【０１３３】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を右下概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ２００４）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から右下概頂点位置算出処理を行い（ステップＳ２００５）、処理後の探索窓Ｆの右下頂点の座標（ｐｘ，ｐｙ）を右下概頂点１０３の座標（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）として算出する（ステップＳ２００６）。
【０１３４】
次に、ＣＰＵ２０１は、探索開始点番号ｎをインクリメントする（ステップＳ２００７）。そして、ＣＰＵ２０１は、探索開始点番号ｎが探索開始点１０２の総数Ｎとなっているか否かを判定する（ステップＳ２００８）。探索開始点番号ｎがＮではない場合（ステップＳ２００８：Ｎｏ）、図１９のステップＳ１９０３に戻る。探索開始点番号ｎがＮである場合（ステップＳ２００８：Ｙｅｓ）、概頂点位置算出処理を終了する。これにより、抽出装置２００は、Ｎ個の探索開始点１０２のそれぞれに対する概頂点１０３を算出することができる。
【０１３５】
次に、図１９のステップＳ１９０１に示した積分画像生成処理について説明する。図２１は実施例１にかかる積分画像生成処理の詳細を示すフローチャートである。ここで、Ｉ0（ｘ，ｙ）は画像Ｉの座標（ｘ，ｙ）の画素の輝度を示す。ＩＩ（ｘ，ｙ）は原点（０，０）から画像Ｉの座標（ｘ，ｙ）までの輝度の積分値を示す。
【０１３６】
まず、ＣＰＵ２０１は、ＩＩ（０，０）にＩ0（０，０）を代入する（ステップＳ２１０１）。次に、ＣＰＵ２０１は、ｘ方向ループ変数ｊを１にセットする（ステップＳ２１０２）。そして、ＣＰＵ２０１は、ＩＩ（ｊ，０）にＩ0（ｊ，０）＋ＩＩ（ｊ−１，０）を算出して代入する（ステップＳ２１０３）。ここで、ＣＰＵ２０１は、ｘ方向ループ変数ｊが画像幅ｄｘとなっているか否かを判定する（ステップＳ２１０４）。ｊが画像幅ｄｘとなっていない場合（ステップＳ２１０４：Ｎｏ）、ステップＳ２１０３に戻る。
【０１３７】
ｊが画像幅ｄｘとなっている場合（ステップＳ２１０４：Ｙｅｓ）、ＣＰＵ２０１は、ｙ方向ループ変数ｉを１にセットする（ステップＳ２１０５）。そして、ＣＰＵ２０１は、ＩＩ（０，ｉ）にＩ0（０，ｉ）＋ＩＩ（０，ｉ−１）を算出して代入する（ステップＳ２１０６）。
【０１３８】
次に、ＣＰＵ２０１は、ｘ方向ループ変数ｊを１にセットする（ステップＳ２１０７）。そして、ＣＰＵ２０１は、ＩＩ（ｊ，ｉ）にＩ0（ｊ，ｉ）＋ＩＩ（ｊ，ｉ−１）＋ＩＩ（ｊ−１，ｉ）−ＩＩ（ｊ−１，ｉ−１）を算出して代入する（ステップＳ２１０８）。ここで、ＣＰＵ２０１は、ｊをインクリメントし（ステップＳ２１０９）、ｊが画像幅ｄｘとなったか否かを判定する（ステップＳ２１１０）。
【０１３９】
ｊが画像幅ｄｘとなっていない場合（ステップＳ２１１０：Ｎｏ）、ステップＳ２１０８に戻る。ｊが画像幅ｄｘとなっている場合（ステップＳ２１１０：Ｙｅｓ）、ＣＰＵ２０１は、ｉをインクリメントし（ステップＳ２１１１）、ｉが画像高さｄｙになったか否かを判定する（ステップＳ２１１２）。ｉが画像高さｄｙになっていない場合（ステップＳ２１１２：Ｎｏ）、ステップＳ２１０６に戻る。ｉが画像高さｄｙになっている場合（ステップＳ２１１２：Ｙｅｓ）、積分画像生成処理を終了する。これにより、原点（０，０）から画像Ｉの座標（ｘ，ｙ）までの輝度の積分値から構成される積分画像が生成される。
【０１４０】
次に、図１９のステップＳ１９０４に示した左上概頂点位置算出処理について説明する。図２２，２３は実施例１にかかる左上概頂点位置算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３は探索窓Ｆと探索窓候補Ｆ１，Ｆ２，Ｆ３のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。なお、輝度総和値は、図５を用いて上述した算出手段を用いて算出する。
【０１４１】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ２２０１）。次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ２２０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ２２０３）。さらに、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出し（ステップＳ２２０４）、図２３のステップＳ２３０１に進む。
【０１４２】
ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ２３０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ２３０２）。｜Ｍ０−Ｍ１｜はＭ０とＭ１の差の絶対値を示し、｜Ｍ０−Ｍ２｜は、Ｍ０とＭ２の差の絶対値を示し、｜Ｍ０−Ｍ３｜は、Ｍ０とＭ３の差の絶対値を示す。
【０１４３】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ２３０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さいか否か判定する（ステップＳ２３０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さい場合（ステップＳ２３０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ２３０４）、図２２のステップＳ２２０１に戻る。
【０１４４】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さくない場合（ステップＳ２３０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さいか否か判定する（ステップＳ２３０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さい場合（ステップＳ２３０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ２３０６）、図２２のステップＳ２２０１に戻る。
【０１４５】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さくない場合（ステップＳ２３０５：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ２３０７）、図２２のステップＳ２２０１に戻る。
【０１４６】
Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ２３０２：Ｎｏ）、ＣＰＵ２０１は、探索窓Ｆの中心座標から算出した探索窓Ｆ左上頂点の座標（ｐｘ−ｆｘ／２、ｐｙ−ｆｙ／２）を（ｐｘ、ｐｙ）に代入して出力する（ステップＳ２３０８）。そして、左上概頂点位置算出処理を終了する。
【０１４７】
次に、図１９のステップＳ１９０７に示した右上概頂点位置算出処理について説明する。図２４，図２５は実施例１にかかる右上概頂点位置算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３は探索窓Ｆと探索窓候補Ｆ１，Ｆ２，Ｆ３のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。
【０１４８】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ２４０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ２４０２）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ２４０３）。さらに、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出し（ステップＳ２４０４）、図２５のステップＳ２５０１に進む。
【０１４９】
ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ２５０１）。そして、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ２５０２）。｜Ｍ０−Ｍ１｜はＭ０とＭ１の差の絶対値を示し、｜Ｍ０−Ｍ２｜は、Ｍ０とＭ２の差の絶対値を示し、｜Ｍ０−Ｍ３｜は、Ｍ０とＭ３の差の絶対値を示す。
【０１５０】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ２５０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さいか否か判定する（ステップＳ２５０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さい場合（ステップＳ２５０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ２５０４）、図２４のステップＳ２４０１に戻る。
【０１５１】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さくない場合（ステップＳ２５０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さいか否か判定する（ステップＳ２５０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さい場合（ステップＳ２５０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ２５０６）、図２４のステップＳ２４０１に戻る。
【０１５２】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さくない場合（ステップＳ２５０５：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ２５０７）、図２４のステップＳ２４０１に戻る。
【０１５３】
Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ２５０２：Ｎｏ）、ＣＰＵ２０１は、探索窓Ｆの中心座標から算出した探索窓Ｆ右上頂点の座標（ｐｘ＋ｆｘ／２、ｐｙ−ｆｙ／２）を（ｐｘ、ｐｙ）に代入して出力する（ステップＳ２５０８）。そして、右上概頂点位置算出処理を終了する。
【０１５４】
次に、図２０のステップＳ２００２に示した左下概頂点位置算出処理について説明する。図２６，図２７は実施例１にかかる左下概頂点位置算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３は探索窓Ｆと探索窓候補Ｆ１，Ｆ２，Ｆ３のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。
【０１５５】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ２６０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ２６０２）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ２６０３）。さらに、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出し（ステップＳ２６０４）、図２７のステップＳ２７０１に進む。
【０１５６】
ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ２７０１）。そして、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ２７０２）。｜Ｍ０−Ｍ１｜はＭ０とＭ１の差の絶対値を示し、｜Ｍ０−Ｍ２｜は、Ｍ０とＭ２の差の絶対値を示し、｜Ｍ０−Ｍ３｜は、Ｍ０とＭ３の差の絶対値を示す。
【０１５７】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ２７０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さいか否か判定する（ステップＳ２７０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さい場合（ステップＳ２７０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ２７０４）、図２６のステップＳ２６０１に戻る。
【０１５８】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さくない場合（ステップＳ２７０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さいか否か判定する（ステップＳ２７０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さい場合（ステップＳ２７０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ２７０６）、図２６のステップＳ２６０１に戻る。
【０１５９】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さくない場合（ステップＳ２７０５：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ２７０７）、図２６のステップＳ２６０１に戻る。
【０１６０】
Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ２７０２：Ｎｏ）、ＣＰＵ２０１は、探索窓Ｆの中心座標から算出した探索窓Ｆ左下頂点の座標（ｐｘ−ｆｘ／２、ｐｙ＋ｆｙ／２）を（ｐｘ、ｐｙ）に代入して出力する（ステップＳ２７０８）。そして、左下概頂点位置算出処理を終了する。
【０１６１】
次に、図２０のステップＳ２００５に示した右下概頂点位置算出処理について説明する。図２８，図２９は実施例１にかかる右下概頂点位置算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３は探索窓Ｆと探索窓候補Ｆ１，Ｆ２，Ｆ３のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。
【０１６２】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ２８０１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ２８０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ２８０３）。さらに、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出し（ステップＳ２８０４）、図２９のステップＳ２９０１に進む。
【０１６３】
ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ２９０１）。そして、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ２９０２）。｜Ｍ０−Ｍ１｜はＭ０とＭ１の差の絶対値を示し、｜Ｍ０−Ｍ２｜は、Ｍ０とＭ２の差の絶対値を示し、｜Ｍ０−Ｍ３｜は、Ｍ０とＭ３の差の絶対値を示す。
【０１６４】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ２９０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さいか否か判定する（ステップＳ２９０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さい場合（ステップＳ２９０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ２９０４）、図２８のステップＳ２８０１に戻る。
【０１６５】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さくない場合（ステップＳ２９０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さいか否か判定する（ステップＳ２９０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さい場合（ステップＳ２９０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ２９０６）、図２８のステップＳ２８０１に戻る。
【０１６６】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さくない場合（ステップＳ２９０５：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ２９０７）、図２８のステップＳ２８０１に戻る。
【０１６７】
Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ２９０２：Ｎｏ）、ＣＰＵ２０１は、探索窓Ｆの中心座標から算出した探索窓Ｆ右下頂点の座標（ｐｘ＋ｆｘ／２、ｐｙ＋ｆｙ／２）を（ｐｘ、ｐｙ）に代入して出力する（ステップＳ２９０８）。そして、右下概頂点位置算出処理を終了する。
【０１６８】
次に、図１８のステップＳ１８０３に示した詳細頂点位置算出処理について説明する。図３０，図３１は実施例１にかかる詳細頂点位置算出処理の詳細を示すフローチャートである。
【０１６９】
まず、ＣＰＵ２０１は、画像Ｉからエッジ画像Ｅを作成する（ステップＳ３００１）。次に、ＣＰＵ２０１は、エッジ画像Ｅを二値化して二値画像ＥＢを作成する（ステップＳ３００２）。そして、ＣＰＵ２０１は、探索開始点番号ｎを０にセットする（ステップＳ３００３）。
【０１７０】
次に、ＣＰＵ２０１は、探索開始点番号ｎに対する左上概頂点１０３（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）を（ｕｌｘ，ｕｌｙ）とする。また、右上概頂点１０３（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）を（ｕｒｘ，ｕｒｙ）とする。そして、右下概頂点１０３（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）を（ｌｒｘ，ｌｒｙ）とする。さらに、左下概頂点１０３（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）を（ｌｌｘ，ｌｌｙ）とする（ステップＳ３００４）。
【０１７１】
次に、ＣＰＵ２０１は、図３２を用いて後述する上辺算出処理を行う（ステップＳ３００５）。そして、ＣＰＵ２０１は、図３３を用いて後述する右辺算出処理を行う（ステップＳ３００６）。次に、ＣＰＵ２０１は、図３４を用いて後述する下辺算出処理を行う（ステップＳ３００７）。そして、ＣＰＵ２０１は、図３５を用いて後述する左辺算出処理を行い（ステップＳ３００８）、図３１のステップＳ３１０１に進む。
【０１７２】
次に、ＣＰＵ２０１は、図３８を用いて後述する左上頂点算出処理を行う（ステップＳ３１０１）。そして、ＣＰＵ２０１は、図３９を用いて後述する右上頂点算出処理を行う（ステップＳ３１０２）。次に、ＣＰＵ２０１は、図４０を用いて後述する右下頂点算出処理を行う（ステップＳ３１０３）。そして、ＣＰＵ２０１は、図４１を用いて後述する左下頂点算出処理を行う（ステップＳ３１０４）。
【０１７３】
次に、ＣＰＵ２０１は、ｎをインクリメントする（ステップＳ３１０５）。そして、ＣＰＵ２０１は、算出した左上頂点（ｐｕｌｘ，ｐｕｌｙ）を、探索開始点番号ｎに対する左上頂点（ｐｕｌｘ［ｎ］，ｐｕｌｙ［ｎ］）として記憶装置２０２に保持する。また、ＣＰＵ２０１は、算出した右上頂点（ｐｕｒｘ，ｐｕｒｙ）を、探索開始点番号ｎに対する右上頂点（ｐｕｒｘ［ｎ］，ｐｕｒｙ［ｎ］）として記憶装置２０２に保持する。そして、ＣＰＵ２０１は、算出した右下頂点（ｐｌｒｘ，ｐｌｒｙ）を、探索開始点番号ｎに対する右下頂点（ｐｌｒｘ［ｎ］，ｐｌｒｙ［ｎ］）として記憶装置２０２に保持する。さらに、ＣＰＵ２０１は、算出した左下頂点（ｐｌｌｘ，ｐｌｌｙ）を、探索開始点番号ｎに対する左下頂点（ｐｌｌｘ［ｎ］，ｐｌｌｙ［ｎ］）として記憶装置２０２に保持する（ステップＳ３１０６）。
【０１７４】
次に、ＣＰＵ２０１は、ｎがＮになっているか否かを判定する（ステップＳ３１０７）。ｎがＮになっていない場合（ステップＳ３１０７：Ｎｏ）、図３０のステップＳ３００４に戻る。ｎがＮになっている場合（ステップＳ３１０７：Ｙｅｓ）、詳細頂点位置算出処理を終了する。これにより、抽出装置２００は、抽出対象の四角形１０１の詳細頂点１０４の座標を算出することができる。
【０１７５】
ここで、抽出装置２００は、算出した詳細頂点群の座標の平均座標をあらたな詳細頂点１０４の座標としてもよい。また、抽出装置２００は、算出した詳細頂点群のうち探索開始点から最も遠い詳細頂点１０４をあらたな詳細頂点としてもよい。
【０１７６】
次に、図３０のステップＳ３００５に示した上辺算出処理について説明する。図３２は実施例１にかかる上辺算出処理の詳細を示すフローチャートである。
【０１７７】
まず、ＣＰＵ２０１は、（ｘ１，ｙ１）に（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）を代入し（ステップＳ３２０１）、（ｘ２，ｙ２）に（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）を代入する（ステップＳ３２０２）。次に、ＣＰＵ２０１は、図３６，図３７を用いて後述する辺算出処理を行う（ステップＳ３２０３）。そして、辺算出処理により算出した値ａ、ｂ、ｃをそれぞれ上辺のパラメータｕａ、ｕｂ、ｕｃに代入し（ステップＳ３２０４）、上辺算出処理を終了する。
【０１７８】
次に、図３０のステップＳ３００６に示した右辺算出処理について説明する。図３３は実施例１にかかる右辺算出処理の詳細を示すフローチャートである。
【０１７９】
まず、ＣＰＵ２０１は、（ｘ１，ｙ１）に（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）を代入し（ステップＳ３３０１）、（ｘ２，ｙ２）に（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）を代入する（ステップＳ３３０２）。次に、ＣＰＵ２０１は、図３６，図３７を用いて後述する辺算出処理を行う（ステップＳ３３０３）。そして、辺算出処理により算出した値ａ、ｂ、ｃをそれぞれ右辺のパラメータｒａ、ｒｂ、ｒｃに代入し（ステップＳ３３０４）、右辺算出処理を終了する。
【０１８０】
次に、図３０のステップＳ３００７に示した下辺算出処理について説明する。図３４は実施例１にかかる下辺算出処理の詳細を示すフローチャートである。
【０１８１】
まず、ＣＰＵ２０１は、（ｘ１，ｙ１）に（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）を代入し（ステップＳ３４０１）、（ｘ２，ｙ２）に（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）を代入する（ステップＳ３４０２）。次に、ＣＰＵ２０１は、図３６，図３７を用いて後述する辺算出処理を行う（ステップＳ３４０３）。そして、辺算出処理により算出した値ａ、ｂ、ｃをそれぞれ下辺のパラメータｂａ、ｂｂ、ｂｃに代入し（ステップＳ３４０４）、下辺算出処理を終了する。
【０１８２】
次に、図３０のステップＳ３００８に示した左辺算出処理について説明する。図３５は実施例１にかかる左辺算出処理の詳細を示すフローチャートである。
【０１８３】
まず、ＣＰＵ２０１は、（ｘ１，ｙ１）に（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）を代入し（ステップＳ３５０１）、（ｘ２，ｙ２）に（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）を代入する（ステップＳ３５０２）。次に、ＣＰＵ２０１は、図３６，図３７を用いて後述する辺算出処理を行う（ステップＳ３５０３）。そして、辺算出処理により算出した値ａ、ｂ、ｃをそれぞれ左辺のパラメータｌａ、ｌｂ、ｌｃに代入し（ステップＳ３５０４）、左辺算出処理を終了する。
【０１８４】
次に、図３２〜図３５に示した辺算出処理について説明する。図３６，図３７は実施例１にかかる辺算出処理の詳細を示すフローチャートである。該当特徴点数ｋとは、概頂点１０３を結んだ線分の付近に存在するエッジの数であり、エッジを検出する度にカウントされる値である。ＥＢ（ｘ，ｙ）とは、二値画像ＥＢの座標（ｘ，ｙ）の値を示す。
【０１８５】
まず、ＣＰＵ２０１は、該当特徴点数ｋを０にセットする（ステップＳ３６０１）。次に、ＣＰＵ２０１は、注目画素のｙ座標ｙを０にセットし（ステップＳ３６０２）、注目画素のｘ座標ｘを０にセットする（ステップＳ３６０３）。
【０１８６】
ここで、ＣＰＵ２０１は、ＥＢ（ｘ，ｙ）が０でないか否か判定する（ステップＳ３６０４）。ＥＢ（ｘ，ｙ）が０である場合（ステップＳ３６０４：Ｎｏ）、ステップＳ３７０８に進む。ＥＢ（ｘ，ｙ）が０でない場合（ステップＳ３６０４：Ｙｅｓ）、ＣＰＵ２０１は、規格化定数ｑを算出し（ステップＳ３６０５）、ベクトルｕ，ｖを算出し（ステップＳ３６０６）、ｄ，ｌを算出する（ステップＳ３６０７）。そして、図３７のステップＳ３７０１に進む。
【０１８７】
次に、ＣＰＵ２０１は、ｌが０以上かつｌがｑ以下であるか否かを判定する（ステップＳ３７０１）。ｌが０以上かつｌがｑ以下である場合（ステップＳ３７０１：Ｙｅｓ）、ステップＳ３７０５に進む。
【０１８８】
ｌが０以上かつｌがｑ以下でない場合（ステップＳ３７０１：Ｎｏ）、ＣＰＵ２０１は、ｌが０より小さいか否か判定する（ステップＳ３７０２）。ｌが０より小さくない場合（ステップＳ３７０２：Ｎｏ）、ＣＰＵ２０１は、ｄ＝ｓｑｒｔ（（ｘ−ｘ２）＊（ｘ−ｘ２）＋（ｙ−ｙ２）＊（ｙ−ｙ２））を算出し（ステップＳ３７０４）、ステップＳ３７０５に進む。
【０１８９】
ｌが０より小さい場合（ステップＳ３７０２：Ｙｅｓ）、ＣＰＵ２０１は、ｄ＝ｓｑｒｔ（（ｘ−ｘ１）＊（ｘ−ｘ１）＋（ｙ−ｙ１）＊（ｙ−ｙ１））を算出する（ステップＳ３７０３）。そして、ＣＰＵ２０１は、ｄがｒ以下か否か判定する（ステップＳ３７０５）。ｄがｒ以下でない場合（ステップＳ３７０５：Ｎｏ）、ステップＳ３７０８に進む。
【０１９０】
ｄがｒ以下である場合（ステップＳ３７０５：Ｙｅｓ）、ＣＰＵ２０１は、ｅｘ［ｋ］にｘを代入し、ｅｙ［ｋ］にｙを代入して記憶装置２０２に保持する（ステップＳ３７０６）。そして、ＣＰＵ２０１は、ｋをインクリメントする（ステップＳ３７０７）。
【０１９１】
次に、ＣＰＵ２０１は、ｘをインクリメントする（ステップＳ３７０８）。そして、ＣＰＵ２０１は、ｘがｄｘより小さいか否か判定する（ステップＳ３７０９）。ｘがｄｘより小さい場合（ステップＳ３７０９：Ｙｅｓ）、図３６のステップＳ３６０４に進む。
【０１９２】
ｘがｄｘより小さくない場合（ステップＳ３７０９：Ｎｏ）、ＣＰＵ２０１は、ｙをインクリメントする（ステップＳ３７１０）。そして、ＣＰＵ２０１は、ｙがｄｙより小さいか否か判定する（ステップＳ３７１１）。ｙがｄｙより小さい場合（ステップＳ３７１１：Ｙｅｓ）、図３６のステップＳ３６０３に進む。
【０１９３】
ｙがｄｙより小さくない場合（ステップＳ３７１１：Ｎｏ）、ＣＰＵ２０１は、ＲＡＮＳＡＣ法によりｋサンプルからａｘ＋ｂｙ＋ｃ＝０の直線パラメータａ、ｂ、ｃを算出し（ステップＳ３７１２）、辺算出処理を終了する。なお、ＲＡＮＳＡＣ法は周知技術のため、ここでは、詳細な説明を省略する。
【０１９４】
なお、ＲＡＮＳＡＣ法については、Ｍ．  Ａ．  Ｆｉｓｃｈｌｅｒ，  Ｒ．  Ｃ．  Ｂｏｌｌｅｓ．らによって、「Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ：  Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｍｏｄｅｌ  Ｆｉｔｔｉｎｇ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｕｔｏｍａｔｅｄ  Ｃａｒｔｏｇｒａｐｈｙ．」（Ｃｏｍｍ．  ｏｆ  ｔｈｅ  ＡＣＭ，  Ｖｏｌ  ２４，  ｐｐ  ３８１―３９５，  １９８１．）に示されている。
【０１９５】
次に、図３１のステップＳ３１０１に示した左上頂点算出処理について説明する。図３８は実施例１にかかる左上頂点算出処理の詳細を示すフローチャートである。なお、直線ａ１ｘ＋ｂ１ｙ＋ｃ１＝０と直線ａ２ｘ＋ｂ２ｙ＋ｃ２＝０の交点（ｘ，ｙ）は下記式（５）で求められる。
【０１９６】
【数５】
0005569364.tif 000006
【０１９７】
左上頂点算出処理において、まず、ＣＰＵ２０１は、（ａ１，ｂ１，ｃ１）に（ｕａ，ｕｂ，ｕｃ）を代入し（ステップＳ３８０１）、（ａ２，ｂ２，ｃ２）に（ｌａ，ｌｂ，ｌｃ）を代入する（ステップＳ３８０２）。次に、ＣＰＵ２０１は、上記式（５）を用いて交点（ｘ，ｙ）を算出する（ステップＳ３８０３）。そして、左上頂点（ｐｕｌｘ，ｐｕｌｙ）に（ｘ，ｙ）を代入して記憶装置２０２に保持して（ステップＳ３８０４）、左上頂点算出処理を終了する。
【０１９８】
次に、図３１のステップＳ３１０２に示した右上頂点算出処理について説明する。図３９は実施例１にかかる右上頂点算出処理の詳細を示すフローチャートである。
【０１９９】
まず、ＣＰＵ２０１は、（ａ１，ｂ１，ｃ１）に（ｒａ，ｒｂ，ｒｃ）を代入し（ステップＳ３９０１）、（ａ２，ｂ２，ｃ２）に（ｕａ，ｕｂ，ｕｃ）を代入する（ステップＳ３９０２）。次に、ＣＰＵ２０１は、上記式（５）を用いて交点（ｘ，ｙ）を算出する（ステップＳ３９０３）。そして、右上頂点（ｐｕｒｘ，ｐｕｒｙ）に（ｘ，ｙ）を代入して記憶装置２０２に保持して（ステップＳ３９０４）、右上頂点算出処理を終了する。
【０２００】
次に、図３１のステップＳ３１０３に示した右下頂点算出処理について説明する。図４０は実施例１にかかる右下頂点算出処理の詳細を示すフローチャートである。
【０２０１】
まず、ＣＰＵ２０１は、（ａ１，ｂ１，ｃ１）に（ｂａ，ｂｂ，ｂｃ）を代入し（ステップＳ４００１）、（ａ２，ｂ２，ｃ２）に（ｒａ，ｒｂ，ｒｃ）を代入する（ステップＳ４００２）。次に、ＣＰＵ２０１は、上記式（５）を用いて交点（ｘ，ｙ）を算出する（ステップＳ４００３）。そして、右下頂点（ｐｌｒｘ，ｐｌｒｙ）に（ｘ，ｙ）を代入して記憶装置２０２に保持して（ステップＳ４００４）、右下頂点算出処理を終了する。
【０２０２】
次に、図３１のステップＳ３１０４に示した左下頂点算出処理について説明する。図４１は実施例１にかかる左下頂点算出処理の詳細を示すフローチャートである。
【０２０３】
まず、ＣＰＵ２０１は、（ａ１，ｂ１，ｃ１）に（ｌａ，ｌｂ，ｌｃ）を代入し（ステップＳ４１０１）、（ａ２，ｂ２，ｃ２）に（ｂａ，ｂｂ，ｂｃ）を代入する（ステップＳ４１０２）。次に、ＣＰＵ２０１は、上記式（５）を用いて交点（ｘ，ｙ）を算出する（ステップＳ４１０３）。そして、左下頂点（ｐｌｌｘ，ｐｌｌｙ）に（ｘ，ｙ）を代入して記憶装置２０２に保持して（ステップＳ４１０４）、左下頂点算出処理を終了する。
【０２０４】
このように、上述した実施例１では、抽出対象である四角形１０１の内部を探索開始点１０２とし、四角形１０１の辺を越えないように探索窓Ｆを移動させるため、四角形１０１外の背景に影響されずに概頂点１０３の座標を算出することができる。また、探索窓候補内の輝度総和値に基づき移動先を判断するため、四角形１０１の辺に途切れがあっても、抽出装置２００は、四角形１０１の辺に沿って探索窓Ｆを移動させることができる。
【０２０５】
また、上述した実施例１では、概頂点１０３と概頂点１０３とを結ぶ線分の周辺のエッジ情報のみに基づいて四角形１０１の辺を検出するため、四角形１０１外の背景に影響されずに四角形１０１の辺を構成する直線を検出することができる。そして、それらの直線の交点を詳細頂点１０４の座標として算出することができる。
【０２０６】
ここでは、探索窓Ｆの移動先とする探索窓候補はＦ１〜Ｆ３の３つとしたが、３つに限らず複数の探索窓候補を用いることができる。また、ここでは、移動先とする探索窓候補のステップ幅はｘ軸方向とｙ軸方向で同一の値を用いたが、ｘ軸方向とｙ軸方向で異なる値を用いてもよい。また、ステップ幅を探索状況に応じて変化する可変値としてもよい。例えば、探索開始点１０２の付近ではステップ幅を大きくし、探索開始点１０２から離れるにつれステップ幅を小さくしてもよい。また、移動先とする探索窓候補がなくなった場合に、ステップ幅を小さくして再度移動先とする探索窓候補を探索し、より実際の頂点位置に近い概頂点１０３を算出するようにしてもよい。
【０２０７】
また、ここでは、探索方向は等角に旋回した頂点数分の方向としたが、等角に旋回せず異なる角度ずつ旋回した方向であってもよい。また、探索開始点１０２として、画像Ｉの中心の点を採用したが、ユーザが指定する任意の点であってもよいし、抽出対象の多角形を大まかに検出するアプリケーションによって検出される点であってもよい。また、複数の探索開始点１０２を用いてそれぞれの探索開始点１０２に対する概頂点１０３を算出し、それら概頂点１０３の座標の平均座標を概頂点１０３としてもよい。
【０２０８】
（実施例２）
次に、実施例２にかかる抽出装置２００について説明する。実施例１では、探索窓候補Ｆ１〜Ｆ３により移動先がない場合に頂点を抽出したが、実施例２では、探索窓候補Ｆ１〜Ｆ３により移動先がない場合に、さらに探索窓候補を拡張して探索を継続する。このように探索窓候補を拡張することで、移動先が特定される可能性があるため、実施例１よりも高精度に頂点を抽出することができる。なお、実施例２では、実施例１と同様、抽出する多角形として四角形１０１を対象とした場合について説明する。また、実施例２では、実施例１と同一構成および同一処理については同一符号および同一ステップ番号を付し、その説明を省略する。
【０２０９】
図４２〜４５は、実施例２にかかる抽出装置による四角形１０１の概頂点１０３の算出の具体例を示す説明図である。透視投影による抽出対象の四角形１０１の歪みが非常に大きい場合には、探索方向と四角形の辺とが垂直またはそれに近い角度で交差する関係となってしまう。このとき、図４２の（Ａ）に示すように抽出対象の四角形１０１の辺に探索窓Ｆが到達した場合、探索窓候補Ｆ１〜Ｆ３のみでは、抽出装置２００は探索窓候補Ｆ１〜Ｆ３が移動先でないと判断してしまうため、頂点付近に到達したと誤認することになる。この問題を解決するため、実施例２では、探索窓候補Ｆ１〜Ｆ３とは異なる方向への移動先となる探索窓候補Ｆ４およびＦ５をさらに用いることで、探索窓Ｆが頂点付近に到達したか否かを判断する。
【０２１０】
図４２の（Ａ）に示すように抽出対象の四角形１０１の辺に探索窓Ｆが到達した場合、探索窓候補Ｆ４およびＦ５内のうち少なくともいずれかを移動先にできると判断されるため、探索窓Ｆはまだ頂点付近に到達していないと判断できる。
【０２１１】
一方、図４２の（Ｂ）に示すように、探索窓Ｆが頂点付近に到達していた場合、探索窓候補Ｆ４およびＦ５も同様に移動先ではないと判断されるため、探索窓Ｆは頂点付近に到達したと判断して、概頂点１０３を算出できる。
【０２１２】
ここで、探索窓Ｆが四角形１０１の辺に到達したと判断された場合、抽出装置２００は、辺に沿って探索窓Ｆを移動させるために、探索窓候補Ｆ４およびＦ５のうちいずれかをあらたな移動先として採用する。そして、抽出装置２００は、探索窓候補Ｆ１〜Ｆ３と採用された探索窓候補との４つの探索窓候補を用いて探索窓Ｆを移動させていく。
【０２１３】
具体的には、抽出装置２００は、探索窓候補Ｆ４およびＦ５内の輝度総和値と探索窓Ｆ内の輝度総和値との差を算出し、その差が最小である移動先となる探索窓候補をあらたな移動先として採用する。
【０２１４】
例えば、抽出装置２００は、図４３の（Ａ）に示すような場合では、Ｆ５をあらたな探索窓として採用し、図４３の（Ｂ）に示すような場合では、Ｆ４をあらたな探索窓として採用する。
【０２１５】
次に、図４４，図４５を用いて、あらたな移動先となる探索窓候補を設定した場合の探索窓の移動の具体例について説明する。
【０２１６】
図４４の（Ａ）に示すように、あらたな移動先となる探索窓候補としてＦ５が採用された場合、抽出装置２００は、探索窓Ｆを探索窓候補Ｆ５へ移動させる。次に、抽出装置２００は、探索窓候補Ｆ１〜Ｆ３に探索窓候補Ｆ５を加えた４つの探索窓候補を用いて、概頂点１０３の探索を行う。
【０２１７】
図４４の（Ｂ）に示すように、探索窓候補Ｆ１およびＦ３は辺を越えており移動先とできないが、探索窓候補Ｆ２，Ｆ５は移動先とできる。ここで、抽出装置２００は、より探索開始点１０２から遠い位置にある移動先である探索窓候補Ｆ２へ探索窓Ｆを移動させる。
【０２１８】
図４５に示すように、探索窓候補Ｆ１〜Ｆ５のいずれも移動先とできないため、抽出装置２００は、探索窓Ｆの頂点を概頂点１０３として算出する。これにより、辺付近で頂点を誤認することなく精度よく概頂点１０３を算出できる。
【０２１９】
（実施例２にかかる抽出装置２００による抽出処理の詳細）
次に、実施例２にかかる抽出装置２００による抽出処理の詳細について説明する。ここで、実施例２にかかる抽出処理は実施例１で図１８を用いて説明した処理のうちステップＳ１８０２に示した概頂点位置算出処理を以下に示す実施例２にかかる概頂点位置算出処理に置き換えたものである。なお、他のステップＳ１８０１とステップＳ１８０３は実施例１で説明した処理と同様である。ここで、図４６，図４７を用いて実施例２にかかる概頂点位置算出処理の詳細について説明する。
【０２２０】
図４６，図４７は実施例２にかかる概頂点位置算出処理の詳細を示すフローチャートである。まず、ＣＰＵ２０１は、積分画像生成処理を行い、記憶装置２０２に保持されている撮像した画像Ｉから積分画像を生成する（ステップＳ４６０１）。そして、ＣＰＵ２０１は、探索開始点番号ｎを０にセットする（ステップＳ４６０２）。
【０２２１】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を左上概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ４６０３）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から左上概頂点位置算出処理を行い（ステップＳ４６０４）、さらに、左上概頂点位置副算出処理を行う（ステップＳ４６０５）。そして、ＣＰＵ２０１は、処理後の探索窓Ｆの左上頂点の座標（ｐｘ，ｐｙ）を左上概頂点１０３の座標（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）として算出する（ステップＳ４６０６）。
【０２２２】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を右上概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ４６０７）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から右上概頂点位置算出処理を行い（ステップＳ４６０８）、さらに、右上概頂点位置副算出処理を行う（ステップＳ４６０９）。そして、ＣＰＵ２０１は、処理後の探索窓Ｆの右上頂点の座標（ｐｘ，ｐｙ）を右上概頂点１０３の座標（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）として算出し（ステップＳ４６１０）、図４７のステップＳ４７０１に進む。
【０２２３】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を左下概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ４７０１）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から左下概頂点位置算出処理を行い（ステップＳ４７０２）、さらに、左下概頂点位置副算出処理を行う（ステップＳ４７０３）。そして、ＣＰＵ２０１は、処理後の探索窓Ｆの左下頂点の座標（ｐｘ，ｐｙ）を左下概頂点１０３の座標（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）として算出する（ステップＳ４７０４）。
【０２２４】
次に、ＣＰＵ２０１は、探索開始点１０２の座標（ｓｘ［ｎ］，ｓｙ［ｎ］）を右下概頂点位置算出処理における探索窓Ｆの初期座標（ｐｘ，ｐｙ）として設定する（ステップＳ４７０５）。そして、ＣＰＵ２０１は、初期座標（ｐｘ，ｐｙ）から右下概頂点位置算出処理を行い（ステップＳ４７０６）、さらに、右下概頂点位置副算出処理を行う（ステップＳ４７０７）。そして、ＣＰＵ２０１は、処理後の探索窓Ｆの右下頂点の座標（ｐｘ，ｐｙ）を右下概頂点１０３の座標（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）として算出する（ステップＳ４７０８）。
【０２２５】
次に、ＣＰＵ２０１は、探索開始点番号ｎをインクリメントする（ステップＳ４７０９）。そして、ＣＰＵ２０１は、探索開始点番号ｎが探索開始点１０２の総数Ｎとなっているか否かを判定する（ステップＳ４７１０）。探索開始点番号ｎがＮではない場合（ステップＳ４７１０：Ｎｏ）、図４６のステップＳ４６０３に戻る。探索開始点番号ｎがＮである場合（ステップＳ４７１０：Ｙｅｓ）、概頂点位置算出処理を終了する。
【０２２６】
図４６，図４７の積分画像生成処理、左上概頂点位置算出処理、右上概頂点位置算出処理、左下概頂点位置算出処理、右下概頂点位置算出処理の説明は実施例１で図２１〜図２９を用いて説明したものと同様の処理であるため、ここでは説明を省略する。
【０２２７】
次に、図４６のステップＳ４６０５に示した左上概頂点位置副算出処理について説明する。図４８は実施例２にかかる左上概頂点位置副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。
【０２２８】
まず、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出する（ステップＳ４８０１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出する（ステップＳ４８０２）。
【０２２９】
そして、ＣＰＵ２０１は、｜Ｍ０−Ｍ４｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ４８０３）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ４８０４）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ４８０４：Ｎｏ）、左上概頂点位置副算出処理を終了する。
【０２３０】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ４８０４：Ｙｅｓ）、ＣＰＵ２０１は、Ｍｍｉｎが｜Ｍ０−Ｍ４｜であるか否か判定する（ステップＳ４８０５）。Ｍｍｉｎが｜Ｍ０−Ｍ４｜である場合（ステップＳ４８０５：Ｙｅｓ）、ＣＰＵ２０１は、左上概頂点位置第一副算出処理を行い（ステップＳ４８０６）、左上概頂点１０３（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ４８０７）。そして、左上概頂点位置副算出処理を終了する。
【０２３１】
Ｍｍｉｎが｜Ｍ０−Ｍ４｜でない場合（ステップＳ４８０５：Ｎｏ）、ＣＰＵ２０１は、左上概頂点位置第二副算出処理を行い（ステップＳ４８０８）、左上概頂点１０３（ｕｌｘ［ｎ］，ｕｌｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ４８０９）。そして、左上概頂点位置副算出処理を終了する。
【０２３２】
次に、図４８のステップＳ４８０６に示した左上概頂点位置第一副算出処理について説明する。図４９，図５０は実施例２にかかる左上概頂点位置第一副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ軸方向のステップ幅を示し、ｗｙは探索窓のｙ軸方向のステップ幅を示す。
【０２３３】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ４９０１）。次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ４９０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ４９０３）。
【０２３４】
次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ４９０４）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出し（ステップＳ４９０５）、図５０のステップＳ５００１へ進む。
【０２３５】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５００１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５００２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５００２：Ｎｏ）、左上概頂点位置第一副算出処理を終了する。
【０２３６】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５００２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５００３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５００３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ５００４）、図４９のステップＳ４９０１に戻る。
【０２３７】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５００３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５００５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５００５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５００６）、図４９のステップＳ４９０１に戻る。
【０２３８】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５００５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５００７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５００７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５００８）、図４９のステップＳ４９０１に戻る。
【０２３９】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５００７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ５００９）、図４９のステップＳ４９０１に戻る。
【０２４０】
次に、図４８のステップＳ４８０８に示した左上概頂点位置第二副算出処理について説明する。図５１，図５２は実施例２にかかる左上概頂点位置第二副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２４１】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ５１０１）。次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ５１０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ５１０３）。
【０２４２】
次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ５１０４）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出し（ステップＳ５１０５）、図５２のステップＳ５２０１へ進む。
【０２４３】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５２０１）。そして、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５２０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５２０２：Ｎｏ）、左上概頂点位置第二副算出処理を終了する。
【０２４４】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５２０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５２０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５２０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ５２０４）、図５１のステップＳ５１０１に戻る。
【０２４５】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５２０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５２０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５２０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５２０６）、図５１のステップＳ５１０１に戻る。
【０２４６】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５２０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５２０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５２０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５２０８）、図５１のステップＳ５１０１に戻る。
【０２４７】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５２０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５２０９）、図５１のステップＳ５１０１に戻る。
【０２４８】
次に、図４６のステップＳ４６０９に示した右上概頂点位置副算出処理について説明する。図５３は実施例２にかかる右上概頂点位置副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２４９】
まず、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出する（ステップＳ５３０１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出する（ステップＳ５３０２）。
【０２５０】
そして、ＣＰＵ２０１は、｜Ｍ０−Ｍ４｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５３０３）。そして、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５３０４）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５３０４：Ｎｏ）、右上概頂点位置副算出処理を終了する。
【０２５１】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５３０４：Ｙｅｓ）、ＣＰＵ２０１は、Ｍｍｉｎが｜Ｍ０−Ｍ４｜であるか否か判定する（ステップＳ５３０５）。Ｍｍｉｎが｜Ｍ０−Ｍ４｜である場合（ステップＳ５３０５：Ｙｅｓ）、ＣＰＵ２０１は、右上概頂点位置第一副算出処理を行い（ステップＳ５３０６）、右上概頂点１０３（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ５３０７）。そして、右上概頂点位置副算出処理を終了する。
【０２５２】
Ｍｍｉｎが｜Ｍ０−Ｍ４｜でない場合（ステップＳ５３０５：Ｎｏ）、ＣＰＵ２０１は、右上概頂点位置第二副算出処理を行い（ステップＳ５３０８）、右上概頂点１０３（ｕｒｘ［ｎ］，ｕｒｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ５３０９）。そして、右上概頂点位置副算出処理を終了する。
【０２５３】
次に、図５３のステップＳ５３０６に示した右上概頂点位置第一副算出処理について説明する。図５４，図５５は実施例２にかかる右上概頂点位置第一副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２５４】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ５４０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ５４０２）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ５４０３）。
【０２５５】
次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ５４０４）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出し（ステップＳ５４０５）、図５５のステップＳ５５０１へ進む。
【０２５６】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５５０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５５０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５５０２：Ｎｏ）、右上概頂点位置第一副算出処理を終了する。
【０２５７】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５５０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５５０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５５０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５５０４）、図５４のステップＳ５４０１に戻る。
【０２５８】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５５０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５５０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５５０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ５５０６）、図５４のステップＳ５４０１に戻る。
【０２５９】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５５０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ５５０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ５５０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５５０８）、図５４のステップＳ５４０１に戻る。
【０２６０】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ５５０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５５０９）、図５４のステップＳ５４０１に戻る。
【０２６１】
次に、図５３のステップＳ５３０８に示した右上概頂点位置第二副算出処理について説明する。図５６，図５７は実施例２にかかる右上概頂点位置第二副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２６２】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ５６０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ５６０２）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ５６０３）。
【０２６３】
次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ５６０４）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出し（ステップＳ５６０５）、図５７のステップＳ５７０１へ進む。
【０２６４】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５７０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５７０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５７０２：Ｎｏ）、右上概頂点位置第二副算出処理を終了する。
【０２６５】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５７０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５７０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５７０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５７０４）、図５６のステップＳ５６０１に戻る。
【０２６６】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５７０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５７０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５７０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ５７０６）、図５６のステップＳ５６０１に戻る。
【０２６７】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５７０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ５７０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ５７０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ５７０８）、図５６のステップＳ５６０１に戻る。
【０２６８】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ５７０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ５７０９）、図５６のステップＳ５６０１に戻る。
【０２６９】
次に、図４７のステップＳ４７０３に示した左下概頂点位置副算出処理について説明する。図５８は実施例２にかかる左下概頂点位置副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２７０】
まず、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出する（ステップＳ５８０１）。次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出する（ステップＳ５８０２）。
【０２７１】
そして、ＣＰＵ２０１は、｜Ｍ０−Ｍ４｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ５８０３）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ５８０４）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ５８０４：Ｎｏ）、左下概頂点位置副算出処理を終了する。
【０２７２】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ５８０４：Ｙｅｓ）、ＣＰＵ２０１は、Ｍｍｉｎが｜Ｍ０−Ｍ４｜であるか否か判定する（ステップＳ５８０５）。Ｍｍｉｎが｜Ｍ０−Ｍ４｜である場合（ステップＳ５８０５：Ｙｅｓ）、ＣＰＵ２０１は、左下概頂点位置第一副算出処理を行い（ステップＳ５８０６）、左下概頂点１０３（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ５８０７）。そして、左下概頂点位置副算出処理を終了する。
【０２７３】
Ｍｍｉｎが｜Ｍ０−Ｍ４｜でない場合（ステップＳ５８０５：Ｎｏ）、ＣＰＵ２０１は、左下概頂点位置第二副算出処理を行い（ステップＳ５８０８）、左下概頂点１０３（ｌｌｘ［ｎ］，ｌｌｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ５８０９）。そして、左下概頂点位置副算出処理を終了する。
【０２７４】
次に、図５８のステップＳ５８０６に示した左下概頂点位置第一副算出処理について説明する。図５９，図６０は実施例２にかかる左下概頂点位置第一副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２７５】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ５９０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ５９０２）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ５９０３）。
【０２７６】
次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ５９０４）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出し（ステップＳ５９０５）、図６０のステップＳ６００１へ進む。
【０２７７】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ６００１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ６００２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ６００２：Ｎｏ）、左下概頂点位置第一副算出処理を終了する。
【０２７８】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ６００２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６００３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６００３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６００４）、図５９のステップＳ５９０１に戻る。
【０２７９】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６００３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６００５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６００５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ６００６）、図５９のステップＳ５９０１に戻る。
【０２８０】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６００５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６００７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６００７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６００８）、図５９のステップＳ５９０１に戻る。
【０２８１】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６００７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６００９）、図５９のステップＳ５９０１に戻る。
【０２８２】
次に、図５８のステップＳ５８０８に示した左下概頂点位置第二副算出処理について説明する。図６１，図６２は実施例２にかかる左下概頂点位置第二副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２８３】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ６１０１）。次に、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ６１０２）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ６１０３）。
【０２８４】
次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ６１０４）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出し（ステップＳ６１０５）、図６２のステップＳ６２０１へ進む。
【０２８５】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ６２０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ６２０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ６２０２：Ｎｏ）、左下概頂点位置第二副算出処理を終了する。
【０２８６】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ６２０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６２０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６２０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６２０４）、図６１のステップＳ６１０１に戻る。
【０２８７】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６２０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６２０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６２０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ６２０６）、図６１のステップＳ６１０１に戻る。
【０２８８】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６２０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６２０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６２０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６２０８）、図６１のステップＳ６１０１に戻る。
【０２８９】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６２０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ６２０９）、図６１のステップＳ６１０１に戻る。
【０２９０】
次に、図４７のステップＳ４７０７に示した右下概頂点位置副算出処理について説明する。図６３は実施例２にかかる右下概頂点位置副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２９１】
まず、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出する（ステップＳ６３０１）。次に、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出する（ステップＳ６３０２）。
【０２９２】
そして、ＣＰＵ２０１は、｜Ｍ０−Ｍ４｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ６３０３）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ６３０４）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ６３０４：Ｎｏ）、右下概頂点位置副算出処理を終了する。
【０２９３】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ６３０４：Ｙｅｓ）、ＣＰＵ２０１は、Ｍｍｉｎが｜Ｍ０−Ｍ４｜であるか否か判定する（ステップＳ６３０５）。Ｍｍｉｎが｜Ｍ０−Ｍ４｜である場合（ステップＳ６３０５：Ｙｅｓ）、ＣＰＵ２０１は、右下概頂点位置第一副算出処理を行い（ステップＳ６３０６）、右下概頂点１０３（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ６３０７）。そして、右下概頂点位置副算出処理を終了する。
【０２９４】
Ｍｍｉｎが｜Ｍ０−Ｍ４｜でない場合（ステップＳ６３０５：Ｎｏ）、ＣＰＵ２０１は、右下概頂点位置第二副算出処理を行い（ステップＳ６３０８）、右下概頂点１０３（ｌｒｘ［ｎ］，ｌｒｙ［ｎ］）に（ｐｘ，ｐｙ）を代入する（ステップＳ６３０９）。そして、右下概頂点位置副算出処理を終了する。
【０２９５】
次に、図６３のステップＳ６３０６に示した右下概頂点位置第一副算出処理について説明する。図６４，図６５は実施例２にかかる右下概頂点位置第一副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０２９６】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ６４０１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ６４０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ６４０３）。
【０２９７】
次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ６４０４）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ−ｗｙ）を中心とした探索窓候補Ｆ４に対応する値Ｍ４を算出し（ステップＳ６４０５）、図６５のステップＳ６５０１へ進む。
【０２９８】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ６５０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ６５０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ６５０２：Ｎｏ）、右下概頂点位置第一副算出処理を終了する。
【０２９９】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ６５０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６５０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６５０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ６５０４）、図６４のステップＳ６４０１に戻る。
【０３００】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６５０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６５０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６５０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６５０６）、図６４のステップＳ６４０１に戻る。
【０３０１】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６５０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さいか否か判定する（ステップＳ６５０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さい場合（ステップＳ６５０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６５０８）、図６４のステップＳ６４０１に戻る。
【０３０２】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ４｜より小さくない場合（ステップＳ６５０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ−ｗｙを代入して（ステップＳ６５０９）、図６４のステップＳ６４０１に戻る。
【０３０３】
次に、図６３のステップＳ６３０８に示した右下概頂点位置第二副算出処理について説明する。図６６，図６７は実施例２にかかる右下概頂点位置第二副算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３，Ｍ４，Ｍ５は探索窓Ｆ，探索窓候補Ｆ１と探索窓候補Ｆ２，Ｆ３，Ｆ４，Ｆ５のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０３０４】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ６６０１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ）を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ６６０２）。そして、ＣＰＵ２０１は、（ｐｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ６６０３）。
【０３０５】
次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出する（ステップＳ６６０４）。そして、ＣＰＵ２０１は、（ｐｘ−ｗｘ，ｐｙ＋ｗｙ）を中心とした探索窓候補Ｆ５に対応する値Ｍ５を算出し（ステップＳ６６０５）、図６７のステップＳ６７０１へ進む。
【０３０６】
次に、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ６７０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ６７０２）。Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ６７０２：Ｎｏ）、右下概頂点位置第二副算出処理を終了する。
【０３０７】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ６７０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６７０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６７０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙを代入して（ステップＳ６７０４）、図６６のステップＳ６６０１に戻る。
【０３０８】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６７０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６７０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６７０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６７０６）、図６６のステップＳ６６０１に戻る。
【０３０９】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６７０５：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さいか否か判定する（ステップＳ６７０７）。｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さい場合（ステップＳ６７０７：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６７０８）、図６６のステップＳ６６０１に戻る。
【０３１０】
｜Ｍ０−Ｍ１｜が｜Ｍ０−Ｍ３｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ５｜より小さくない場合（ステップＳ６７０７：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ−ｗｘを代入し、ｐｙにｐｙ＋ｗｙを代入して（ステップＳ６７０９）、図６６のステップＳ６６０１に戻る。
【０３１１】
そして、抽出装置２００は、算出した概頂点１０３から、さらに詳細頂点１０４の座標を算出する。ここで、実施例２にかかる詳細頂点算出処理の詳細は実施例１で図３０〜図４１を用いて説明した処理と同様であるため説明を省略する。
【０３１２】
このように、上述した実施例２では、抽出対象である四角形１０１の内部を探索開始点１０２とし、四角形１０１の辺を越えないように探索窓Ｆを移動させるため、四角形１０１外の背景に影響されずに概頂点１０３の座標を算出することができる。さらに、探索窓Ｆの移動先とする探索窓候補Ｆ１〜Ｆ３に移動先がなくなった場合に、さらに２つの移動先となる探索窓候補Ｆ４およびＦ５を用いるため、四角形１０１の辺を概頂点１０３として誤認することを防止できる。また、探索窓候補内の輝度総和値に基づき移動先を判断するため、四角形１０１の辺に途切れがあっても、抽出装置２００は、四角形１０１の辺に沿って探索窓Ｆを移動させることができる。
【０３１３】
また、上述した実施例２では、概頂点１０３と概頂点１０３とを結ぶ線分の周辺のエッジ情報のみに基づいて四角形１０１の辺を検出するため、四角形１０１外の背景に影響されずに四角形１０１の辺を構成する直線を検出することができる。そして、それらの直線の交点を詳細頂点１０４の座標として算出することができる。
【０３１４】
ここでは、探索窓Ｆの移動先とする探索窓候補はＦ１〜Ｆ３の３つとしたが、３つに限らず複数の探索窓候補を用いることができる。また、ここでは、移動先とする探索窓候補のステップ幅はｘ軸方向とｙ軸方向で同一の値を用いたが、ｘ軸方向とｙ軸方向で異なる値を用いてもよい。また、ステップ幅を探索状況に応じて変化する可変値としてもよい。例えば、探索開始点１０２の付近ではステップ幅を大きくし、探索開始点１０２から離れるにつれステップ幅を小さくしてもよい。また、移動先とする探索窓候補がなくなった場合に、ステップ幅を小さくして再度移動先とする探索窓候補を探索し、より実際の頂点位置に近い概頂点１０３を算出するようにしてもよい。
【０３１５】
また、ここでは、探索方向は等角に旋回した頂点数分の方向としたが、等角に旋回せず異なる角度ずつ旋回した方向であってもよい。また、探索開始点１０２として、画像Ｉの中心の点を採用したが、ユーザが指定する任意の点であってもよいし、抽出対象の四角形を大まかに検出するアプリケーションによって検出される点であってもよい。また、複数の探索開始点１０２を用いてそれぞれの探索開始点１０２に対する概頂点１０３を算出し、それら概頂点１０３の座標の平均座標を概頂点１０３としてもよい。
【０３１６】
（実施例３）
実施例１，２は、抽出対象のスクリーン１０１が四角形である場合の抽出装置２００にかかる実施例であったが、実施例３は、抽出対象のスクリーン１０１が、四角形に限らない多角形である場合の抽出装置２００にかかる実施例である。図６８を用いて、実施例３にかかる抽出装置２００による多角形の抽出の具体例について説明する。
【０３１７】
図６８は、実施例３にかかる抽出装置２００による多角形の抽出の具体例を示す説明図である。ここでは、６角形を例として説明を行う。
【０３１８】
抽出装置２００は、抽出対象のスクリーン１０１（多角形、ここでは、６角形）を抽出する処理を行う。まず、抽出装置２００は、（Ａ）に示すように、抽出対象である多角形１０１の内部の点である探索開始点１０２から、多角形１０１の頂点数分の探索方向に向けて、探索窓Ｆを移動させ、多角形１０１の概頂点１０３の位置を算出する。
【０３１９】
具体的には、抽出装置２００は、（Ｂ）に示すように、探索窓Ｆの移動先となる複数の探索窓候補Ｆ１〜Ｆ３を用意し、探索窓候補Ｆ１〜Ｆ３のうち、多角形１０１の辺を越えない移動先となる探索窓候補へ探索窓Ｆを移動させていく。そして、多角形１０１の頂点まで探索窓Ｆを移動させる。ここで、Ｆ１は探索方向への移動先となる探索窓候補であり、Ｆ２およびＦ３は探索方向から３０度旋回した２つの方向への移動先となる探索窓候補である。
【０３２０】
そして、抽出装置２００は、実施例１と同様に、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内のそれぞれの輝度総和値との差に基づいて、探索窓Ｆを多角形１０１の辺を越えないと判断された移動先へ移動させていく。これにより、探索窓Ｆを多角形１０１の頂点付近まで移動させる。
【０３２１】
また、抽出装置２００は、（Ｃ）に示すような場合には、探索窓Ｆ内の輝度総和値と探索窓候補Ｆ１〜Ｆ３内のそれぞれの輝度総和値に基づいて、頂点付近まで移動したと判断することができる。そして、抽出装置２００は、探索窓Ｆ内の任意の点（以下では、探索窓Ｆの中心とする）を概頂点１０３として算出する。このように、抽出装置２００は、抽出対象である多角形１０１の内部の点から探索窓を移動させるため、枠材や背景の模様の存在にかかわらず概頂点１０３を算出することができる。
【０３２２】
次に、抽出装置２００は、実施例１と同様に、各概頂点１０３を結ぶ線分の周辺部分のみを探索領域として、探索領域内のエッジ情報から多角形１０１の各辺を構成する直線を検出する。そして、抽出装置２００は、各辺の交点を詳細頂点１０４として算出する。抽出装置２００は、例えば、ＲＡＮＳＡＣ法や最小二乗法といった従来技術を用いて、エッジ情報から直線を検出することができる。
【０３２３】
このように、抽出装置２００は、各概頂点１０３を結ぶ線分の周辺部分のみのエッジ情報から多角形１０１の各辺を構成する直線を検出するため、枠材や背景の模様の存在にかかわらず詳細頂点１０４の座標を算出することができる。
【０３２４】
（実施例３にかかる抽出装置２００による抽出処理の詳細）
次に、実施例３にかかる抽出装置２００による抽出処理の詳細について説明する。ここで、実施例３にかかる抽出処理は実施例１で図１８を用いて説明した処理のステップＳ１８０２とステップＳ１８０３に示した概頂点位置算出処理と詳細頂点位置算出処理を以下に示す概頂点位置算出処理と詳細頂点位置算出処理に置き換えたものである。なお、ステップＳ１８０１は実施例１で説明した処理と同様である。
【０３２５】
ここで、実施例３にかかる概頂点位置算出処理について説明する。図６９は実施例３にかかる概頂点位置算出処理の詳細を示すフローチャートである。
【０３２６】
まず、ＣＰＵ２０１は、積分画像生成処理を行い、記憶装置２０２に保持されている撮像した画像Ｉから積分画像を生成する（ステップＳ６９０１）。そして、ＣＰＵ２０１は、抽出対象の多角形１０１の頂点数Ｍが入力されたか否か判定する（ステップＳ６９０２）。頂点数Ｍが入力されていない場合（ステップＳ６９０２：Ｎｏ）、ステップＳ６９０２に戻る。頂点数Ｍが入力された場合（ステップＳ６９０２：Ｙｅｓ）、ステップＳ６９０３に進む。
【０３２７】
次に、ＣＰＵ２０１は、探索開始点番号ｎを０にセットする（ステップＳ６９０３）。そして、ＣＰＵ２０１は、頂点番号ｍを１にセットする（ステップＳ６９０４）。
【０３２８】
次に、ＣＰＵ２０１は、探索開始点１０２の座標を設定する（ステップＳ６９０５）。そして、ＣＰＵ２０１は、探索開始点１０２からｍ番目概頂点位置算出処理を行い（ステップＳ６９０６）、ｍ番目概頂点１０３の座標を算出する（ステップＳ６９０７）。
【０３２９】
次に、ＣＰＵ２０１は、頂点番号ｍをインクリメントする（ステップＳ６９０８）。そして、ＣＰＵ２０１は、頂点番号ｍが頂点数Ｍ＋１となっているか否かを判定する（ステップＳ６９０９）。頂点番号ｍがＭ＋１ではない場合（ステップＳ６９０９：Ｎｏ）、ステップＳ６９０５に戻る。頂点番号ｍがＭ＋１である場合（ステップＳ６９０９：Ｙｅｓ）、ステップＳ６９１０に進む。
【０３３０】
次に、ＣＰＵ２０１は、探索開始点番号ｎをインクリメントする（ステップＳ６９１０）。そして、ＣＰＵ２０１は、探索開始点番号ｎが探索開始点１０２の総数Ｎとなっているか否かを判定する（ステップＳ６９１１）。探索開始点番号ｎがＮではない場合（ステップＳ６９１１：Ｎｏ）、ステップＳ６９０４に戻る。探索開始点番号ｎがＮである場合（ステップＳ６９１１：Ｙｅｓ）、概頂点位置算出処理を終了する。
【０３３１】
ここで、ステップＳ６９０１の積分画像生成処理の詳細は実施例１で図２１を用いて説明した処理と同様であるため説明を省略する。
【０３３２】
次に、図６９のステップＳ６９０６に示したｍ番目概頂点位置算出処理について説明する。図７０，７１は実施例３にかかるｍ番目概頂点位置算出処理の詳細を示すフローチャートである。ここで、Ｍ０，Ｍ１，Ｍ２，Ｍ３は探索窓Ｆと探索窓候補Ｆ１，Ｆ２，Ｆ３のそれぞれの輝度総和値を示す。また、ｆｘは探索窓のｘ軸方向のサイズを示し、ｆｙは探索窓のｙ軸方向のサイズを示し、ｗｘは探索窓のｘ方向のステップ幅を示し、ｗｙは探索窓のｙ方向のステップ幅を示す。
【０３３３】
まず、ＣＰＵ２０１は、（ｐｘ，ｐｙ）を中心とした探索窓Ｆに対応する値Ｍ０を算出する（ステップＳ７００１）。次に、ＣＰＵ２０１は、（ｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ−１８０／ｎ），ｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ−１８０／ｎ））を中心とした探索窓候補Ｆ３に対応する値Ｍ３を算出する（ステップＳ７００２）。そして、ＣＰＵ２０１は、（ｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ＋１８０／ｎ），ｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ＋１８０／ｎ））を中心とした探索窓候補Ｆ２に対応する値Ｍ２を算出する（ステップＳ７００３）。さらに、ＣＰＵ２０１は、（ｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ），ｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ）を中心とした探索窓候補Ｆ１に対応する値Ｍ１を算出し（ステップＳ７００４）、図７１のステップＳ７１０１に進む。
【０３３４】
ＣＰＵ２０１は、｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ３｜を算出し、そのうちの最小値をＭｍｉｎに代入する（ステップＳ７１０１）。そして、ＣＰＵ２０１は、Ｍｍｉｎが閾値ＴｈＭより小さいか否かを判定する（ステップＳ７１０２）。
【０３３５】
Ｍｍｉｎが閾値ＴｈＭより小さい場合（ステップＳ７１０２：Ｙｅｓ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さいか否か判定する（ステップＳ７１０３）。｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さい場合（ステップＳ７１０３：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ−１８０／ｎ）を代入し、ｐｙにｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ−１８０／ｎ）を代入して（ステップＳ７１０４）、図７０のステップＳ７００１に戻る。
【０３３６】
｜Ｍ０−Ｍ３｜が｜Ｍ０−Ｍ２｜と｜Ｍ０−Ｍ１｜より小さくない場合（ステップＳ７１０３：Ｎｏ）、ＣＰＵ２０１は、｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さいか否か判定する（ステップＳ７１０５）。｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さい場合（ステップＳ７１０５：Ｙｅｓ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ＋１８０／ｎ）を代入する。そして、ＣＰＵ２０１は、ｐｙにｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ＋１８０／ｎ）を代入して（ステップＳ７１０６）、図７０のステップＳ７００１に戻る。
【０３３７】
｜Ｍ０−Ｍ２｜が｜Ｍ０−Ｍ１｜と｜Ｍ０−Ｍ３｜より小さくない場合（ステップＳ７１０５：Ｎｏ）、ＣＰＵ２０１は、ｐｘにｐｘ＋ｗｘ＊ｃｏｓ（３６０＊ｍ／ｎ）を代入する。そして、ｐｙにｐｙ＋ｗｙ＊ｓｉｎ（３６０＊ｍ／ｎ）を代入して（ステップＳ７１０７）、図７０のステップＳ７００１に戻る。
【０３３８】
Ｍｍｉｎが閾値ＴｈＭより小さくない場合（ステップＳ７１０２：Ｎｏ）、ＣＰＵ２０１は、中心座標（ｐｘ，ｐｙ）を出力する（ステップＳ７１０８）。そして、ｍ番目概頂点位置算出処理を終了する。
【０３３９】
次に、実施例３にかかる詳細頂点位置算出処理について説明する。図７２，図７３は実施例３にかかる詳細頂点位置算出処理の詳細を示すフローチャートである。まず、ＣＰＵ２０１は、画像Ｉからエッジ画像Ｅを作成する（ステップＳ７２０１）。次に、ＣＰＵ２０１は、エッジ画像Ｅを二値化して二値画像ＥＢを作成する（ステップＳ７２０２）。そして、ＣＰＵ２０１は、探索開始点番号ｎを０にセットし（ステップＳ７２０３）、図７３のステップＳ７３０１に進む。
【０３４０】
次に、ＣＰＵ２０１は、頂点番号ｍを１にセットする（ステップＳ７３０１）。そして、ＣＰＵ２０１は、ｍ番目辺算出処理を行う（ステップＳ７３０２）。そして、ＣＰＵ２０１は、ｍをインクリメントする（ステップＳ７３０３）。
【０３４１】
次に、ＣＰＵ２０１は、ｍがＭ＋１になっているか否かを判定する（ステップＳ７３０４）。ｍがＭ＋１になっていない場合（ステップＳ７３０４：Ｎｏ）、ステップＳ７３０２に戻る。ｍがＭ＋１になっている場合（ステップＳ７３０４：Ｙｅｓ）、ステップＳ７３０５に進む。
【０３４２】
次に、ＣＰＵ２０１は、頂点番号ｍを１にセットする（ステップＳ７３０５）。そして、ＣＰＵ２０１は、ｍ番目頂点算出処理を行う（ステップＳ７３０６）。そして、ＣＰＵ２０１は、ｍをインクリメントする（ステップＳ７３０７）。
【０３４３】
次に、ＣＰＵ２０１は、ｍがＭ＋１になっているか否かを判定する（ステップＳ７３０８）。ｍがＭ＋１になっていない場合（ステップＳ７３０８：Ｎｏ）、ステップＳ７３０６に戻る。ｍがＭ＋１になっている場合（ステップＳ７３０８：Ｙｅｓ）、ステップＳ７３０９に進む。
【０３４４】
次に、ＣＰＵ２０１は、ｎをインクリメントする（ステップＳ７３０９）。そして、ＣＰＵ２０１は、算出したｍ個の頂点を、探索開始点番号ｎに対する頂点として記憶装置２０２に保持する（ステップＳ７３１０）。
【０３４５】
次に、ＣＰＵ２０１は、ｎがＮになっているか否かを判定する（ステップＳ７３１１）。ｎがＮになっていない場合（ステップＳ７３１１：Ｎｏ）、図７３のステップＳ７３０１に戻る。ｎがＮになっている場合（ステップＳ７３１１：Ｙｅｓ）、詳細頂点位置算出処理を終了する。
【０３４６】
次に、図７３のステップＳ７３０２に示したｍ番目辺算出処理について説明する。図７４は実施例３にかかるｍ番目辺算出処理の詳細を示すフローチャートである。
【０３４７】
まず、ＣＰＵ２０１は、（ｘ１，ｙ１）に（ｘ［ｎ］［ｍ］，ｙ［ｎ］［ｍ］）を代入する（ステップＳ７４０１）。次に、ＣＰＵ２０１は、ｍがＭになっているか否かを判定する（ステップＳ７４０２）。ｍがＭになっていない場合（ステップＳ７４０２：Ｎｏ）、ＣＰＵ２０１は、（ｘ２，ｙ２）に（ｘ［ｎ］［ｍ＋１］，ｙ［ｎ］［ｍ＋１］）を代入して（ステップＳ７４０３）ステップＳ７４０５に進む。ｍがＭになっている場合（ステップＳ７４０２：Ｙｅｓ）、ＣＰＵ２０１は、（ｘ２，ｙ２）に（ｘ［ｎ］［１］，ｙ［ｎ］［１］）を代入して（ステップＳ７４０４）ステップＳ７４０５に進む。
【０３４８】
次に、ＣＰＵ２０１は、辺算出処理を行う（ステップＳ７４０５）。そして、辺算出処理により算出した値ａ、ｂ、ｃをそれぞれ上辺のパラメータａ［ｍ］、ｂ［ｍ］、ｃ［ｍ］に代入し（ステップＳ７４０６）、ｍ番目辺算出処理を終了する。
【０３４９】
ここで、ステップＳ７４０５の辺算出処理の詳細は実施例１で図３６，図３７を用いて説明した処理と同様であるため説明を省略する。
【０３５０】
次に、図７３のステップＳ７３０６に示したｍ番目頂点算出処理について説明する。図７５は実施例３にかかるｍ番目頂点算出処理の詳細を示すフローチャートである。
【０３５１】
まず、ＣＰＵ２０１は、（ａ１，ｂ１，ｃ１）に（ａ［ｍ］，ｂ［ｍ］，ｃ［ｍ］）を代入する（ステップＳ７５０１）。次に、ＣＰＵ２０１は、ｍがＭになっているか否かを判定する（ステップＳ７５０２）。ｍがＭになっていない場合（ステップＳ７５０２：Ｎｏ）、ＣＰＵ２０１は、（ａ２，ｂ２，ｃ２）に（ａ［ｍ＋１］，ｂ［ｍ＋１］，ｃ［ｍ＋１］）を代入して（ステップＳ７５０３）、ステップＳ７５０５に進む。ｍがＭになっている場合（ステップＳ７５０２：Ｙｅｓ）、ＣＰＵ２０１は、（ａ２，ｂ２，ｃ２）に（ａ［１］，ｂ［１］，ｃ［１］）を代入して（ステップＳ７５０４）、ステップＳ７５０５に進む。
【０３５２】
次に、ＣＰＵ２０１は、交点（ｘ，ｙ）を算出する（ステップＳ７５０５）。そして、ｍ番目頂点（ｐｘ［ｍ］，ｐｙ［ｍ］）に（ｘ，ｙ）を代入して記憶装置２０２に保持して（ステップＳ７５０６）、ｍ番目頂点算出処理を終了する。
【０３５３】
このように、上述した実施例３では、抽出装置２００は、抽出対象が四角形以外の多角形１０１であっても抽出することができる。また、上述した実施例３では、抽出装置２００は、抽出対象である多角形１０１の内部を探索開始点１０２とし、多角形１０１の辺を越えないように探索窓Ｆを移動させるため、多角形１０１外の背景に影響されずに概頂点１０３の座標を算出することができる。
【０３５４】
そして、上述した実施例３では、抽出装置２００は、概頂点１０３と概頂点１０３とを結ぶ線分の周辺のエッジ情報のみに基づいて多角形１０１の辺を検出するため、多角形１０１外の背景に影響されずに多角形１０１の辺を構成する直線を検出することができる。そして、それらの直線の交点を詳細頂点１０４の座標として算出することができる。
【０３５５】
ここでは、探索窓Ｆの移動先とする探索窓候補はＦ１〜Ｆ３の３つとしたが、３つに限らず複数の探索窓候補を用いることができる。また、ここでは、移動先とする探索窓候補のステップ幅はｘ軸方向とｙ軸方向で同一の値を用いたが、ｘ軸方向とｙ軸方向で異なる値を用いてもよい。また、ステップ幅を探索状況に応じて変化する可変値としてもよい。例えば、探索開始点１０２の付近ではステップ幅を大きくし、探索開始点１０２から離れるにつれステップ幅を小さくしてもよい。また、移動先とする探索窓候補がなくなった場合に、ステップ幅を小さくして再度移動先とする探索窓候補を探索し、より実際の頂点位置に近い概頂点１０３を算出するようにしてもよい。
【０３５６】
また、ここでは、探索方向は等角に旋回した頂点数分の方向としたが、等角に旋回せず異なる角度ずつ旋回した方向であってもよい。また、探索開始点１０２として、画像Ｉの中心の点を採用したが、ユーザが指定する任意の点であってもよいし、抽出対象の多角形１０１を大まかに検出するアプリケーションによって検出される点であってもよい。また、複数の探索開始点１０２を用いてそれぞれの探索開始点１０２に対する概頂点１０３を算出し、それら概頂点１０３の座標の平均座標を概頂点１０３としてもよい。
【０３５７】
このように、上述した実施の形態では、抽出装置２００は、透視投影によって歪んだ抽出対象の多角形１０１を抽出することができる。また、上述した実施の形態では、抽出装置２００は、抽出対象である多角形１０１の内部を探索開始点１０２とし、多角形１０１の辺を越えないように探索窓Ｆを移動させるため、多角形１０１外の背景に影響されずに概頂点１０３の座標を算出することができる。
【０３５８】
また、探索窓候補内の輝度総和値に基づき移動先を判断するため、四角形１０１の辺に途切れがあっても、抽出装置２００は、多角形１０１の辺に沿って探索窓Ｆを移動させることができる。
【０３５９】
そして、上述した実施の形態では、抽出装置２００は、概頂点１０３と概頂点１０３とを結ぶ線分の周辺のエッジ情報のみに基づいて多角形１０１の辺を検出するため、多角形１０１外の背景に影響されずに多角形１０１の辺を構成する直線を検出することができる。そして、それらの直線の交点を詳細頂点１０４の座標として算出することができる。
【０３６０】
また、概頂点１０３と概頂点１０３とを結ぶ線分の周辺のエッジ情報のみに基づいて多角形１０１の辺を検出するため、多角形１０１の辺に途切れがあっても、抽出装置２００は、多角形１０１の辺を構成する直線を検出することができる。
【０３６１】
なお、本実施の形態で説明した抽出方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本抽出プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本抽出プログラムは、インターネット等のネットワークを介して配布することとしてもよい。
【０３６２】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０３６３】
（付記１）対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定手段と、
前記特定手段によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得手段と、
前記探索方向ごとに、前記取得手段によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断手段と、
前記探索窓ごとに、前記判断手段によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定手段と、
前記探索方向ごとに、前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定手段と、
前記決定手段によって前記探索方向ごとに決定された概頂点群を出力する出力手段と、
を備えることを特徴とする抽出装置。
【０３６４】
（付記２）前記特定手段は、前記判断手段によって続行しないと判断された特定の探索方向から前記所定角度よりさらに旋回した２つの方向への移動先となる第４および第５の探索窓候補と、を特定し、
前記取得手段は、前記特定手段によって特定された前記第４および第５の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断手段は、前記取得手段によって取得された前記第４および第５の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定手段は、前記判断手段によって続行すると判断された場合、前記第４および第５の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定手段は、前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記１に記載の抽出装置。
【０３６５】
（付記３）前記特定手段は、前記探索窓の前記特定の探索方向への移動先となる第１の探索窓候補と、前記特定の探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、前記設定手段によって設定される前の探索窓から前記設定手段によって設定された前記探索窓への移動方向への移動先となる第６の探索窓候補と、を特定し、
前記取得手段は、前記特定手段によって特定された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断手段は、前記取得手段によって取得された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定手段は、前記判断手段によって続行すると判断された場合、前記第１乃至第３の探索窓候補および前記第６の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定手段は、前記判断手段によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記２に記載の抽出装置。
【０３６６】
（付記４）前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備え、
前記出力手段は、前記抽出手段によって抽出された多角形を出力することを特徴とする付記１乃至３のいずれか一つに記載の抽出装置。
【０３６７】
（付記５）前記出力手段は、前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備えるコンピュータに、前記概頂点群を出力することを特徴とする付記１乃至３のいずれか一つに記載の抽出装置。
【０３６８】
（付記６）特定手段、取得手段、判断手段、設定手段、決定手段、および出力手段を備えるコンピュータが、
前記特定手段により、対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定工程と、
前記取得手段により、前記特定工程によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得工程と、
前記判断手段により、前記探索方向ごとに、前記取得工程によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断工程と、
前記設定手段により、前記探索窓ごとに、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定工程と、
前記決定手段により、前記探索方向ごとに、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定工程と、
前記出力手段により、前記決定工程によって前記探索方向ごとに決定された概頂点群を出力する出力工程と、
を実行することを特徴とする抽出方法。
【０３６９】
（付記７）前記特定工程は、前記判断工程によって続行しないと判断された特定の探索方向から前記所定角度よりさらに旋回した２つの方向への移動先となる第４および第５の探索窓候補と、を特定し、
前記取得工程は、前記特定工程によって特定された前記第４および第５の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断工程は、前記取得工程によって取得された前記第４および第５の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定工程は、前記判断工程によって続行すると判断された場合、前記第４および第５の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定工程は、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記６に記載の抽出方法。
【０３７０】
（付記８）前記特定工程は、前記探索窓の前記特定の探索方向への移動先となる第１の探索窓候補と、前記特定の探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、前記設定工程によって設定される前の探索窓から前記設定工程によって設定された前記探索窓への移動方向への移動先となる第６の探索窓候補と、を特定し、
前記取得工程は、前記特定工程によって特定された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断工程は、前記取得工程によって取得された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定工程は、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補および前記第６の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定工程は、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記７に記載の抽出方法。
【０３７１】
（付記９）コンピュータが、
前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出工程を実行し、
前記出力工程は、前記抽出工程によって抽出された多角形を出力することを特徴とする付記６乃至８のいずれか一つに記載の抽出方法。
【０３７２】
（付記１０）前記出力工程は、前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備えるコンピュータに、前記概頂点群を出力することを特徴とする付記６乃至８のいずれか一つに記載の抽出方法。
【０３７３】
（付記１１）対象画像内から抽出すべき多角形の頂点の数分設定された前記対象画像内の開始点からの探索方向ごとに、探索窓の前記探索方向への移動先となる第１の探索窓候補と、前記探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、を特定する特定工程と、
前記特定工程によって特定された第１乃至第３の探索窓候補の各々の特徴量を前記対象画像から取得する取得工程と、
前記探索方向ごとに、前記取得工程によって取得された特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断する判断工程と、
前記探索窓ごとに、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定する設定工程と、
前記探索方向ごとに、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を、前記多角形を構成する概頂点に決定する決定工程と、
前記決定工程によって前記探索方向ごとに決定された概頂点群を出力する出力工程と、
をコンピュータに実行させることを特徴とする抽出プログラム。
【０３７４】
（付記１２）前記特定工程は、前記判断工程によって続行しないと判断された特定の探索方向から前記所定角度よりさらに旋回した２つの方向への移動先となる第４および第５の探索窓候補と、を特定し、
前記取得工程は、前記特定工程によって特定された前記第４および第５の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断工程は、前記取得工程によって取得された前記第４および第５の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定工程は、前記判断工程によって続行すると判断された場合、前記第４および第５の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定工程は、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記１１に記載の抽出プログラム。
【０３７５】
（付記１３）前記特定工程は、前記探索窓の前記特定の探索方向への移動先となる第１の探索窓候補と、前記特定の探索方向から所定角度旋回した２つの方向への移動先となる第２および第３の探索窓候補と、前記設定工程によって設定される前の探索窓から前記設定工程によって設定された前記探索窓への移動方向への移動先となる第６の探索窓候補と、を特定し、
前記取得工程は、前記特定工程によって特定された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の各々の特徴量を前記対象画像から取得し、
前記判断工程は、前記取得工程によって取得された前記第１乃至第３の探索窓候補および前記第６の探索窓候補の特徴量の各々と前記探索窓の特徴量との差分に基づいて、探索を続行するか否かを判断し、
前記設定工程は、前記判断工程によって続行すると判断された場合、前記第１乃至第３の探索窓候補および前記第６の探索窓候補のうち前記差分が最小となる探索窓候補を前記探索窓としてあらたに設定し、
前記決定工程は、前記判断工程によって続行しないと判断された場合、前記探索窓内の任意の点を前記概頂点に決定することを特徴とする付記１２に記載の抽出プログラム。
【０３７６】
（付記１４）前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出工程をコンピュータに実行させ、
前記出力工程は、前記抽出工程によって抽出された多角形を出力することを特徴とする付記１１乃至１３のいずれか一つに記載の抽出プログラム。
【０３７７】
（付記１５）前記出力工程は、前記概頂点群の中から前記多角形を構成する辺の両端となる一対の概頂点の間におけるエッジ情報を、前記一対の概頂点ごとに前記対象画像から取得することにより、前記一対の概頂点ごとのエッジ情報が交差した点の集合を詳細頂点群とする多角形を抽出する抽出手段を備えるコンピュータに、前記概頂点群を出力することを特徴とする付記１１乃至１３のいずれか一つに記載の抽出プログラム。
【符号の説明】
【０３７８】
Ｆ  探索窓
Ｆ１  探索窓候補
Ｆ２  探索窓候補
Ｆ３  探索窓候補
１０１  スクリーン（四角形、多角形）
１０２  探索開始点
１０３  概頂点
１０４  詳細頂点
２００  抽出装置
３０１  特定部
３０２  取得部
３０３  判断部
３０４  設定部
３０５  決定部
３０６  出力部
３０７  抽出部
【図１】
0005569364.tif 000007
【図２】
0005569364.tif 000008
【図３】
0005569364.tif 000009
【図４】
0005569364.tif 000010
【図５】
0005569364.tif 000011
【図６】
0005569364.tif 000012
【図７】
0005569364.tif 000013
【図８】
0005569364.tif 000014
【図９】
0005569364.tif 000015
【図１０】
0005569364.tif 000016
【図１１】
0005569364.tif 000017
【図１２】
0005569364.tif 000018
【図１３】
0005569364.tif 000019
【図１４】
0005569364.tif 000020
【図１５】
0005569364.tif 000021
【図１６】
0005569364.tif 000022
【図１７】
0005569364.tif 000023
【図１８】
0005569364.tif 000024
【図１９】
0005569364.tif 000025
【図２０】
0005569364.tif 000026
【図２１】
0005569364.tif 000027
【図２２】
0005569364.tif 000028
【図２３】
0005569364.tif 000029
【図２４】
0005569364.tif 000030
【図２５】
0005569364.tif 000031
【図２６】
0005569364.tif 000032
【図２７】
0005569364.tif 000033
【図２８】
0005569364.tif 000034
【図２９】
0005569364.tif 000035
【図３０】
0005569364.tif 000036
【図３１】
0005569364.tif 000037
【図３２】
0005569364.tif 000038
【図３３】
0005569364.tif 000039
【図３４】
0005569364.tif 000040
【図３５】
0005569364.tif 000041
【図３６】
0005569364.tif 000042
【図３７】
0005569364.tif 000043
【図３８】
0005569364.tif 000044
【図３９】
0005569364.tif 000045
【図４０】
0005569364.tif 000046
【図４１】
0005569364.tif 000047
【図４２】
0005569364.tif 000048
【図４３】
0005569364.tif 000049
【図４４】
0005569364.tif 000050
【図４５】
0005569364.tif 000051
【図４６】
0005569364.tif 000052
【図４７】
0005569364.tif 000053
【図４８】
0005569364.tif 000054
【図４９】
0005569364.tif 000055
【図５０】
0005569364.tif 000056
【図５１】
0005569364.tif 000057
【図５２】
0005569364.tif 000058
【図５３】
0005569364.tif 000059
【図５４】
0005569364.tif 000060
【図５５】
0005569364.tif 000061
【図５６】
0005569364.tif 000062
【図５７】
0005569364.tif 000063
【図５８】
0005569364.tif 000064
【図５９】
0005569364.tif 000065
【図６０】
0005569364.tif 000066
【図６１】
0005569364.tif 000067
【図６２】
0005569364.tif 000068
【図６３】
0005569364.tif 000069
【図６４】
0005569364.tif 000070
【図６５】
0005569364.tif 000071
【図６６】
0005569364.tif 000072
【図６７】
0005569364.tif 000073
【図６８】
0005569364.tif 000074
【図６９】
0005569364.tif 000075
【図７０】
0005569364.tif 000076
【図７１】
0005569364.tif 000077
【図７２】
0005569364.tif 000078
【図７３】
0005569364.tif 000079
【図７４】
0005569364.tif 000080
【図７５】
0005569364.tif 000081