図形形状認識装置、図形形状認識方法、およびプログラム
【課題】高速な図形の形状認識を行い、さらに並列処理に最適な領域単位で処理することでより高速な図形の形状認識を行う図形形状認識方法および図形形状認識装置を提供することを目的とする。
【解決手段】図形形状認識装置１０は、画像データ取り込み部１０１と、二値化処理部１０２と、エッジ処理部１０３と、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と、特徴点集合記憶部１１７と、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と、頂点候補集合記憶部１２７と、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）と、頂点集合記憶部１３７と、画像出力部１４０とから構成されている。また、図形形状認識装置１０には、カメラ１１と、画像表示装置１３が接続されている。
【解決手段】図形形状認識装置１０は、画像データ取り込み部１０１と、二値化処理部１０２と、エッジ処理部１０３と、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と、特徴点集合記憶部１１７と、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と、頂点候補集合記憶部１２７と、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）と、頂点集合記憶部１３７と、画像出力部１４０とから構成されている。また、図形形状認識装置１０には、カメラ１１と、画像表示装置１３が接続されている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、図形形状認識装置、図形形状認識方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、現実環境にコンピューターを用いて情報を付加提供するＡＲ（Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ；拡張現実）の技術が注目されている。ＡＲの実現方法としては各種の方法が提案されているが、その１つとしてマーカーを使う方法（マーカー型ＡＲ）が提案されている。マーカーを使う方法においては、予めマーカーとして定められている二次元バーコード等の画像を用い、このマーカーを対象となる空間である画像内に設置する。図２４は、マーカーの一例を示す図である。また、図２５は、二値化されたマーカーを含む入力画像の一例を示す図である。図２５のように、画像中に図２４のマーカーが配置されている。このように、図形形状認識装置が、マーカーを含む画像を取得し、取得した画像中からマーカーを検出し、検出したマーカーに予めリンクされているプログラム等が起動する。具体的な例として、名刺にマーカーを埋め込んで生成した場合、このマーカーを含む名刺の画像をカメラで撮像して、図形形状認識装置で処理を行うと、マーカーにリンクした人物の写真や動画が再生される。
【０００３】
このような撮像された画像からの図形形状認識装置における図形形状認識手法としては、以下のような手法がある。まず、撮像された画像を取得し、取得した画像（濃淡画像）にエッジ処理を行うか、もしくは取得した画像を二値化し、二値化した画像に対してエッジ処理を行う。そして、図形形状認識装置が、エッジ処理した情報に基づいてラベリング処理を行うことで、検出物体の輪郭を抽出して、抽出した輪郭情報に基づいて検出物体の形状認識を行うといった手法がある（例えば、特許文献１参照）。
【０００４】
ここで、ラベリング処理とは、エッジ処理した画像情報を用いて、同じ連結成分に属する全ての画素に同じラベルを割り当て、異なった連結成分には異なったラベルを割り当てる処理である。図２６は、ラベリング処理を説明する図である。図２６において、探索開始点から同じ連結成分を境界追跡法（例えば８近傍）のアルゴリズムによる探索を行い、ラベル１を割り当てる。同様に異なる連結成分にはラベル２、ラベル３が割り当てられる。このようにして、同じ連結部分を検出することで、取得された画像の中から輪郭を抽出する。図２６は、ラベリング処理された画像の一例を示す図である。図２７は、図２５の画像をラベリングした例であり、抽出された輪郭の一部を示している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平５−１６５９６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
例えば、このようなＡＲをインターネット等のＷｅｂアプリケーション等で実現する場合、図形形状認識装置として一般のコンピューター等が利用可能である。近年のコンピューターはマルチコア化が進んでおり、このようなマルチコアを有効に利用するためには、図形形状認識方法において、取得した画像を一定の領域単位に分割して並列処理する必要がある。
しかしながら、特許文献１の手法において、取得された画像を一定の領域単位に分割しようとしても、ラベリングの探索範囲が取得された画像によって変化するため、単純に処理領域を分割することは困難であるという課題があった。また、仮に予め定めておいた領域ごとに分割して並列処理を行った場合、ラベリングを行った対象が分割により分断されてしまうこともある。この場合、分断された各ラベル領域が同一の領域であるのかを別途判定する必要が生じてしまい、並列処理と単一処理との演算コストが変わらないか、演算量が増加してしまう場合もあるという課題があった。
【０００７】
本発明は、上記の課題に鑑みてなされたものであって、高速な図形の形状認識を行い、さらに並列処理に最適な領域単位で処理することでより高速な図形の形状認識を行う図形形状認装置、図形形状認識方法、およびプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明は、図形形状認識装置において、エッジ処理した入力画像の全ての画素を１画素ずつ参照し、線分の交点である特徴点を全て検出する特徴点判定処理部と、前記特徴点判定部が検出した全ての前記特徴点を１つずつ参照し、全ての頂点候補を検出する頂点候補判定処理部と、前記頂点候補判定処理部が検出した頂点候補を１つずつ参照し、参照した前記頂点候補に基づき当該頂点候補を含み図形を構成する他の頂点候補を検出し、検出した前記頂点候補に基づいて図形形状を認識する図形形状認識処理部とを備えることを特徴としている。
【０００９】
また、本発明は、図形形状認識装置において、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理部と、前記特徴点判定部が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判定処理部と、前記頂点候補判定部が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理部とを備えることを特徴としている。
【００１０】
また、本発明は、図形形状認識装置において、前記特徴点判定処理部は、参照した前記画素の八近傍における隣接画素同士の接続および接触、あるいは、接続または接触の構成に基づいて構成パターンを検出し、検出した構成パターンに基づいて前記画素が特徴点か否かを判定することを特徴としている。
【００１１】
また、本発明は、図形形状認識装置において、前記頂点候補判定処理部は、参照した特徴点を特徴付ける情報を用いて前記特徴点に隣接している画素を順次探索し、探索した結果に基づき前記特徴点を始点とし探索終了点を終了点とする２本のベクトルを生成し、生成した前記２本のベクトルのなす角を算出し、生成した前記２本のベクトルの各距離と前記なす角を用いて頂点候補か否かを判定することを特徴としている。
【００１２】
また、本発明は、図形形状認識装置において、前記特徴点判定処理部、前記頂点候補判定処理部、前記図形形状認識処理部のうち少なくとも１つの処理部を複数備え、複数の前記特徴点判定処理部が並列処理、または複数の前記頂点候補判定処理部が並列処理、または複数の前記図形形状認識処理部が並列処理することを特徴としている。
【００１３】
また、本発明は、図形形状認識方法において、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程とを含むことを特徴としている。
【００１４】
また、本発明は、図形形状認識装置のプログラムにおいて、コンピューターに、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程とを実行させることを特徴としている。
【発明の効果】
【００１５】
本発明によれば、取得した画像から、画素単位で線分の交点である特徴点の抽出を行い、抽出した特徴点に関する情報を特徴点集合として生成し、生成した特徴点集合から頂点候補を抽出し、抽出した特徴点候補に関する情報を頂点候補集合として生成し、さらに生成した頂点候補集合から図形の頂点の抽出と他の頂点の推定を行うことが可能となる。さらにまた、各処理を並列演算に最適な画素単位にしたため、並列演算による高速な図形形状の認識を行うことが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態に係る図形形状認識装置の構成の一例を示すブロック図である。
【図２】同実施形態に係る図２４の二値化画像をエッジ処理した後の画像データの一例を示す図である。
【図３】同実施形態に係る検出した特徴点の一例を示す図である。
【図４】同実施形態に係る頂点候補を説明する図である。
【図５】同実施形態に係る特徴点集合の構成の一例を示す図である。
【図６】同実施形態に係る頂点候補集合の構成の一例を示す図である。
【図７】同実施形態に係る頂点集合の構成の一例を示す図である。
【図８】同実施形態に係る図形形状認識方法のフローチャートである。
【図９】同実施形態に係る特徴点処理手順のフローチャートである。
【図１０】同実施形態に係る頂点候補処理手順のフローチャートである。
【図１１】同実施形態に係る頂点処理手順のフローチャートである。
【図１２】同実施形態に係る連結点と分岐点の例を説明する図である。
【図１３】同実施形態に係る注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成がノイズと判定される例を説明する図である。
【図１４】同実施形態に係る注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成が特徴点ではないと判定される例を説明する図である。
【図１５】同実施形態に係る特徴点が連結点の場合の探索を説明する図である。
【図１６】同実施形態に係る特徴点が分岐点の場合の探索を説明する図である。
【図１７】同実施形態に係る探索結果およびベクトル生成手法を説明する図である。
【図１８】同実施形態に係る正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点抽出手法を説明する図である。
【図１９】同実施形態に係る正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点推定手法を説明する図である。
【図２０】同実施形態に係る正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点抽出手法を説明する図である。
【図２１】同実施形態に係る正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点推定手法を説明する図である。
【図２２】同実施形態に係る正三角形の場合の頂点抽出手法および頂点推定手法を説明する図である。
【図２３】同実施形態に係る正方形の場合の頂点抽出手法および頂点推定手法を説明する図である。
【図２４】マーカーの一例を示す図である。
【図２５】二値化されたマーカーを含む入力画像の一例を示す図である。
【図２６】ラベリング処理を説明する図である。
【図２７】ラベリング処理された画像の一例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、図１〜図２５を用いて説明する。なお、本発明は係る実施形態の構成に限定されず、本発明の技術思想の範囲内で種々の変更が可能である。
【００１８】
図１は、図形形状認識装置の構成の一例を示すブロック図である。図１のように、図形形状認識装置１０は、画像データ取り込み部１０１と、二値化処理部１０２と、エッジ処理部１０３と、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と、特徴点集合記憶部１１７と、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と、頂点候補集合記憶部１２７と、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）と、頂点集合記憶部１３７と、画像出力部１４０とを備える。また、図形形状認識装置１０には、カメラ１１と、画像表示装置１３が接続されている。
また、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、それぞれ連結点・分岐点判断部１１１と、ノイズ除去部１１２と、特徴点判定部１１３と、特徴点集合生成部１１４とを備える。
また、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、それぞれ探索部１２１と、ベクトル生成部１２２と、頂点角度判定部１２３と、頂点候補判定部１２４と、頂点候補集合生成部１２５とを備える。
また、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、それぞれ頂点抽出部１３１と、頂点推定部１３２と、図形形状認識部１３３とを備える。
【００１９】
カメラ１１は、例えば受光レンズとＣＣＤカメラ等で構成され、検出図形を含む入力画像を撮影し、撮影された画像データを図形形状認識装置１０に送信する。画像表示装置１３は、図形形状認識装置１０から図形形状認識結果の表示用の画像を受信し、受信した画像を表示する。
【００２０】
画像データ取り込み部１０１は、カメラ１１により撮影された検出図形を含む入力画像を取り込み、取り込んだ画像データを二値化処理部１０２に出力する。
【００２１】
二値化処理部１０２は、画像データ取り込み部１０１が出力する画像データを取り込む。また、二値化部１０２は、取り込んだ画像データに対して、閾値を用いて二値化し、二値化した画像情報をエッジ処理部１０３に出力する。なお、二値化における閾値の設定方法は、例えば１９７９年に大津展之によって提案された方法（以下、大津の方法）を用いて行う。図２５は、二値化されたマーカーを含む入力画像の一例を示す図である。
【００２２】
エッジ処理部１０３は、二値化処理部１０２が出力する画像データを取り込む。また、エッジ処理部１０３は、取り込んだ二値化された画像データに対して、ラプラシアンフィルタを用いた一般的な手法を用いたエッジ処理を行う。また、エッジ処理部１０３は、エッジ処理した画像データをエッジ集合としてエッジ処理部１０３に書き込んで記憶させる。図２は、図２５の二値化画像をエッジ処理した後の画像データの一例を示す図である。また、エッジ集合は、エッジ処理部１０３がエッジ処理により生成した各画素の座標（ｘ，ｙ）の各データを有している。また、エッジ処理は、ラプラシアンフィルタ以外の一般的な手法を用いても良い。
【００２３】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理部１０３に記憶されているエッジ集合の中から未参照の画素を未参照の画素がなくなるまで参照する。また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、参照した画素の特徴点判定を行い、線分の交点である特徴点と判定した画素および特徴点を特徴付ける情報を特徴点集合として生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる。なお、参照するとは、エッジ処理部１０３に記憶されているエッジ集合の中から画素を読み出す処理のことであり、また未参照の画素を未参照の画素がなくなるまで参照するとは、まだ読み出していない画素を未参照の画素がなくなるまで読み出す処理のことである。
また、各特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、特徴点判定処理を並列に処理する。例えば、取得した画像が６４０×４８０画素（＝３０７２００画素）の場合、特徴点判定処理部１１０ａが１番目の画素の特徴点判定処理を行い、並列して特徴点判定処理部１１０ｂが４番目の画素の特徴点判定処理を行い、並列して特徴点判定処理部１１０ｃが７番目の画素の特徴点判定処理を行う。特徴点判定処理を終了した特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、未参照の画素を未参照の画素がなくなるまで参照して、参照した画素の特徴点判定処理を順次行い、取得した画像全ての画素について特徴点判定処理を行う。また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に対して特徴点判定が終了した後、特徴点集合の生成が終了した情報を頂点候補判定処理１２０（ａ，ｂ，ｃ・・・）に出力する。また、各特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が、取得した画素を参照する順番は、例えばエッジ集合の中から順番に読み出しても良く、あるいはランダムに読み出しても良く、さらには、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）ごとに予め定めた領域を読み出すようにしても良い。
【００２４】
以下に、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
連結点・分岐点判定部１１１は、エッジ処理部１０３が記憶するエッジ集合の中から未参照の画素の中から１画素を参照する。次に、連結点・分岐点判定部１１１は、参照した画素を注目点とし、エッジ集合を参照して注目点の８近傍に２点以上の黒画素が存在しているか否かを判定する。注目点の８近傍に２点以上の黒画素が存在していると判定した場合、連結点・分岐点判定部１１１は、注目点と８近傍に存在する黒画素との接続および接触、あるいは、接続または接触の構成パターンが連結点であるか、分岐点であるかを判定する。
連結点と分岐点の具体的な例を、図１２を用いて説明する。図１２（ａ）において、画素ｍ５が注目点であり、ｍ１〜ｍ９（ｍ５を除く）の画素が８近傍の画素である。図１２（ａ）のように、注目点ｍ５に画素ｍ８と画素ｍ３が接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「連結点」と定義する。連結点の他の例は、（ｍ１，ｍ５，ｍ８），（ｍ２，ｍ５，ｍ７），（ｍ２，ｍ５，ｍ９），（ｍ４，ｍ５，ｍ３），（ｍ４，ｍ５，ｍ９），（ｍ１，ｍ５，ｍ６），（ｍ７，ｍ５，ｍ６）の３画素が接続および接触、あるいは、接続または接触している状態である。
図１２（ｂ）のように、注目点ｍ５に画素ｍ２と画素ｍ６および画素ｍ８が接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「分岐点」と定義する。連結点の他の例は、（ｍ２，ｍ４，ｍ５，ｍ８），（ｍ２，ｍ４，ｍ５，ｍ６），（ｍ４，ｍ５，ｍ６，ｍ８）の４画素が接続および接触、あるいは、接続または接触している状態である。
【００２５】
ノイズ除去部１１２は、連結点・分岐点判定部１１１が参照した注目点、および注目点の８近傍に存在する２つの黒画素の接続および接触、あるいは、接続または接触の構成パターンのうち、ノイズの構成パターンを除去する。特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が抽出したい特徴点は、図形を特徴付けている線分の交点であり、辺である線分ではない。すなわち、特徴点とは、複数の線分をつなぎ合わせた交点（線分の終点同士をつなぎ合わせた点も含む）であり、多角形の１８０度以内の頂点、多角形の１８０度以上の頂点、閉じていない線分の交点などを備えている。このため、直線は特徴点ではないため、参照した注目点、および注目点の８近傍の２つの黒画素が直線的に接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「ノイズ」と定義する。具体例として、注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成パターンを、ノイズと判定する例を、図１３を用いて説明する。図１３のように、注目点と８近傍にある黒画素が、縦または横、または斜めに直線的に接続および接触、あるいは、接続または接触している構成パターンがノイズである。
【００２６】
特徴点判定部１１３は、連結点・分岐点判断部１１１の判定結果とノイズ除去部１１２の判定結果に基づき、特徴点を判定する。特徴点と判定する条件は、連結点・分岐点判断部１１１が連結点または分岐点と判定した画素、かつノイズ除去部１１２がノイズと判定しなかった画素である。また、特徴点ではないと判定する条件は、連結点・分岐点判断部１１１が連結点または分岐点と判定しなかった画素、またはノイズ除去部１１２がノイズと判定した画素、または８近傍に黒画素が２画素以上ない画素である。図１４は、注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成パターンが特徴点ではないと判定される例を説明する図である。図１４（ａ）のように、参照した画素（注目点）の８近傍に１つの黒画素しか接続あるいは接触していない構成パターンを、特徴点判定部１１３は特徴点ではないと判定する。また、図１４（ｂ）のように、参照した画素（注目点）の８近傍に４つの黒画素が接続および接触、あるいは、接続または接触している構成パターンを、特徴点判定部１１３は特徴点ではないと判定する。
すなわち構成パターンとは、連結点・分岐点判断部１１１が参照した画素とその画素の８近傍の画素の接続および接触、あるいは、接続または接触の構成によるものである。また、構成パターンの種類は、連結点であるパターンと、分岐点であるパターンと、ノイズであるパターンと、８近傍に黒画素が２画素以上ないパターンなどである。図３は、検出した特徴点の一例を示す図である。図３において、白抜き丸〇は、特徴点判定部１１３が検出した特徴点の一例である。
【００２７】
特徴点集合生成部１１４は、特徴点判定部１１３が特徴点であると判定した画素を特徴点として特徴付ける情報として、連結点・分岐点判断部１１１が参照した画素とその８近傍に接続および接触、あるいは、接続または接触している２つ以上の黒画素の座標と、構成パターンの種類（連結点または分岐点）を関連付けて特徴点集合を生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる。また、特徴点集合生成部１１４は、特徴点集合の生成が終了したことを頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）に出力する。図５は、特徴点集合の構成の一例を示す図である。図５のように特徴点集合は、表形式のデータとして実現されており、特徴点の座標と、特徴点の構成パターン（連結点か分岐点か）と、特徴点に接続および接触、あるいは、接続または接触されている画素の座標の各データを有している。
【００２８】
頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に対して特徴点判定が終了した後、特徴点集合の生成が終了した情報を特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から取り込んだ後、特徴点集合記憶部１１７が記憶している特徴点集合の中から未参照の特徴点を未参照の特徴点がなくなるまで参照する。頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）が特徴点を参照する順番は、特徴点集合記憶部１１７が記憶している順番に参照しても良く、あるいはランダムに参照しても良い。また、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、参照した特徴点について 頂点候補判定を行い、頂点候補と判定した特徴点および頂点候補を特徴付ける情報を頂点候補集合として頂点候補記憶部１２７に記憶する。
また、各頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理を並列に処理する。例えば、取得した特徴点集合が１００組合せの場合、頂点候補判定処理部１２０ａが１番目の特徴点集合の組合せについて頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｂが２番目の特徴点集合の組合せについて頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｃが３番目の特徴点集合の組合せについて頂点候補判定処理を行う。頂点候補判定処理を終了した頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、未参照の特徴点集合の組合せについて順次参照して、参照した特徴点集合の組合せについて頂点候補判定処理を順次行い、参照した全ての特徴点集合について頂点候補判定処理を行う。また、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全ての特徴点集合の特徴点に対して頂点候補判定が終了した後、頂点候補集合の生成が終了した情報を図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）に出力する。
【００２９】
以下に、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
探索部１２１は、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から特徴点集合の生成が終了した情報を取り込んだ後、特徴点集合記憶部１１７が記憶している特徴点集合の中から未参照の１つの特徴点集合を参照する。また、探索部１２１は、参照した特徴点集合から特徴点の座標と、参照した特徴点に接続および接触、あるいは、接続または接触している画素の座標と構成パターン（連結点、分岐点）を読み出す。また、探索部１２１は、読み出した特徴点の８近傍に接続および接触、あるいは、接続または接触している２つの黒画素を起点として選択して、後述する探索手順に基づき接続および接触、あるいは、接続または接触している画素を、所定の回数、順次探索する。また、探索部１２１は、参照した特徴点の座標と探索結果の２つの探索終点の座標を、ベクトル生成部１２２に出力する。図１７は、探索結果およびベクトル生成手法を説明する図であり、図１７（ａ）は、特徴点の８近傍に接続および接触、あるいは、接続または接触している画素から順次探索した結果の例である。図１７（ａ）の例では、探索部１２１が特徴点の８近傍に接続および接触、あるいは、接続または接触している黒画素を起点に、接続および接触、あるいは、接続または接触している黒画素ｍ１３とｍ３２から順次探索した結果、探索終点Ａ（ｍ９１（ｘ９，ｙ１））と探索終点Ｂ（ｍ３９（ｘ３，ｙ９））に到達する。
【００３０】
ベクトル生成部１２２は、探索部１２１が探索した結果である特徴点の座標と、探索した終点の座標を取り込む。また、ベクトル生成部１２２は、取り込んだ特徴点の座標と、探索した終点の座標を用いて、２本のベクトル（特徴点と探索終点Ａ、特徴点と探索終点Ｂ）を生成し、特徴点の座標と生成した２本のベクトルを頂点角度判定部１２３に出力する。図１７（ｂ）は、特徴点と探索終点からベクトルを生成した例である。図１７（ｂ）の例では、ベクトル生成部１２２は、特徴点ｍ２２（ｘ２，ｙ２）から探索終点Ａ（ｍ９１（ｘ９，ｙ１））に向かうベクトルＡと、特徴点ｍ２２（ｘ２，ｙ２）から探索終点Ｂ（ｍ３９（ｘ３，ｙ９））に向かうベクトルを生成する。
【００３１】
頂点角度判定部１２３は、ベクトル生成部１２２が出力する特徴点の座標と２本のベクトルを取り込む。また、頂点角度判定部１２３は、取り込んだ２本のベクトルのなす角θを算出する。また、頂点角度判定部１２３は、算出したなす角θについて、次式（１）を満たすＮを算出する。
【００３２】
θ＝（（（Ｎ−２）×π）／Ｎ）±α・・・（１）
【００３３】
式（１）において、Ｎは正Ｎ角形を構成する頂点の数、αは図形形状を認識する上での予め定められた誤差角度である。また、誤差角度αは、例えば５度などの一定の角度でも良く、あるいはＮに応じて設定しても良い。また、頂点角度判定部１２３は、算出したＮが３以下（なす角θが６０度以下）、さらに１８０度以上の場合は、式（１）を満たさないと判定する。また、頂点角度判定部１２３は、頂点角度判定の判定結果と、特徴点の座標、２本のベクトルおよびなす角θを頂点候補判定部１２４に出力する。
【００３４】
頂点候補判定部１２４は、頂点角度判定部１２３が出力する判定結果と、特徴点の座標と、２本のベクトルおよびなす角θを取り込む。頂点候補判定部１２４は、取り込んだ頂点角度判定の判定結果と、特徴点の座標と、２本のベクトルおよびなす角θに基づいて、探索部１２１が参照した特徴点を頂点候補か否か判定する。頂点候補判定部１２４は、特徴点に対して２本のベクトルが存在ない場合、特徴点に接続および接触、あるいは、接続または接触している画素が連続していないため、すなわち図形のコーナーではないため頂点候補ではないと判定する。また、頂点候補判定部１２４は、頂点候補と判定した特徴点の座標、２本のベクトル、なす角θ、および式（１）との比較により算出したＮを頂点候補集合生成部１２５に出力する。図４は、頂点候補を説明する図である。図４の白抜き丸〇は、頂点候補判定部１２４が頂点候補として判定した特徴点の一例である。
【００３５】
頂点候補集合生成部１２５は、頂点候補判定部１２４が出力する特徴点の座標、２本のベクトル、なす角θ、およびＮを取り込む。また、頂点候補集合生成部１２５は、特徴点を頂点候補として特徴付ける情報として、取り込んだ特徴点の座標、２本のベクトル、なす角θ、およびＮを関連付けて頂点候補集合を生成し、生成した頂点候補集合を頂点候補集合記憶部１２７に記憶する。図６は、頂点候補集合の構成の一例を示す図である。図６のように、頂点候補集合は、表形式のデータとして実現されており、特徴点の座標と、２本のベクトル（ａ、ｂ）と、Ｎと、なす角θの各データを有している。
【００３６】
図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）から頂点候補集合の生成が終了した情報を取り込んだ後、頂点候補集合記憶部１２７が記憶している頂点候補集合の中から未参照の頂点候補を未参照の頂点候補がなくなるまで参照する。図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）が頂点候補を参照する順番は、頂点候補集合記憶部１２７が記憶している順番に参照しても良く、あるいはランダムに参照しても良い。また、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、参照した頂点候補について、参照した頂点候補を含む図形を構成する他の頂点抽出と推定を行い、参照した頂点候補と抽出および推定した頂点に基づき図形形状の認識を行い、図形形状の認識結果を画像出力部１４０に出力する。
また、各図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、図形形状認識処理を並列に処理する。例えば、取得した頂点候補集合が２０組合せの場合、図形形状認識処理部１３０ａが１番目の頂点候補集合の組合せについて図形形状認識処理を行い、並列して図形形状認識処理部１３０ｂが２番目の頂点候補集合の組合せについて図形形状認識処理を行い、並列して図形形状認識処理部１３０ｃが３番目の頂点候補集合の組合せについて図形形状認識処理を行う。図形形状認識処理を終了した図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、未参照の頂点候補集合の組合せについて順次参照して、参照した頂点候補集合の組合せについて図形形状認識処理を順次行い、取得した全ての頂点候補集合について図形形状認識処理を行う。
【００３７】
以下に、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
頂点抽出部１３１は、頂点候補集合記憶部１２７が記憶している頂点候補集合の中から未参照の頂点候補集合を順次参照して、参照した頂点候補集合から頂点候補（以後、参照頂点候補）の座標、ベクトル、Ｎおよびなす角θを読み出す。また、頂点抽出部１３１は、Ｎ（正Ｎ角形）に基づき、参照頂点候補を含む図形の他の頂点を、頂点候補集合の中から抽出し、抽出した頂点候補（以下、抽出頂点候補という）と参照頂点候補の各頂点候補集合を頂点推定部１３２に出力する。
【００３８】
頂点推定部１３２は、頂点抽出部１３１から参照頂点候補と抽出頂点候補の頂点集合を取り込む。また、頂点推定部１３２は、取り込んだ参照頂点候補と抽出頂点候補の頂点候補集合を用いて、それらの頂点候補を含む図形の他の頂点候補の座標を、後述する頂点推定手法を用いて演算により推定する。また、頂点推定部１３２は、参照頂点候補と抽出頂点候補の各頂点候補集合、および推定した頂点を関連づけ、頂点集合として頂点集合記憶部１３７に記憶する。
図７は、頂点集合記憶部１３７が記憶する頂点集合の構成の一例を示す図である。図７のように、頂点集合は、表形式のデータとして実現されており、図形ごとに頂点の座標と各頂点のベクトルの各データを有している。
【００３９】
図形形状認識部１３３は、頂点集合記憶部１３７に記憶されている頂点集合を読み出す。また、図形形状認識部１３３は、読み出した頂点集合に基づき、その頂点が構成する図形形状を認識し、認識した図形形状およびその図形を構成している各頂点の座標等を画像出力部１４０に出力する。
【００４０】
画像出力部１４０は、図形形状認識部１３３が認識した図形形状およびその図形を構成している各頂点の座標等が認識結果を取り込み、取り込んだ認識結果を画像表示装置１３に出力する。
【００４１】
[探索手順の説明]
次に、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）内の探索部１２１の探索手順について、図１５〜図１７を用いて詳細に説明する。図１５は、特徴点が連結点の場合の探索を説明する図である。図１６は、特徴点が分岐点の場合の探索を説明する図である。図１７は、探索結果およびベクトル生成手法を説明する図である。
【００４２】
まず、特徴点が連結点の場合の探索手順について図１５を用いて説明する。説明を簡略化するために、５×５（＝２５画素）内での探索を例に説明する。便宜的に、図１５（ａ）のように各画素についてｍ１１〜ｍ５５の位置番号をつけ説明を行う。特徴点集合記憶部１１７から読み出した特徴点集合が（特徴点ｍ２２（ｘ２，ｙ２）；連結点；接続および接触、あるいは、接続または接触されている画素ｍ２３（ｘ２，ｙ３），ｍ３１（ｘ３，ｙ１））の場合、探索部１２１は、図１５（ｂ）のように、特徴点ｍ２２に接続および接触、あるいは、接続または接触されている画素ｍ２３とｍ３１をそれぞれ起点Ａ、起点Ｂに設定し、まず、起点Ａから探索を開始する。
【００４３】
次に、探索部１２１は、起点Ａ（ｍ２３）の８近傍に接続および接触、あるいは、接続または接触している特徴点以外の黒画素をエッジ処理部１０３内に記憶されているエッジ集合から抽出する。図１５（ｃ）のように起点Ａ（ｍ２３）の８近傍に接続および接触、あるいは、接続または接触している画素はｍ１４とｍ２４である。このように起点に接続および接触、あるいは、接続または接触している画素が複数ある場合、探索部１２１は次の探索画素をランダムに選択する。また、図１５（ｄ）のように、探索途中で探索先に２つ以上の接続および接触、あるいは、接続または接触している黒画素がある場合、１つ前の画素からの距離が長い方を選択する。具体的には、探索部１２１は、起点Ａとしてｍ２３から探索開始し、次にランダムに選択したｍ２４に進む。次に、探索部１２１は、ｍ２４に接続および接触、あるいは、接続または接触している黒画素ｍ２５とｍ３５の内、ｍ２４の１つ前の画素ｍ２３から距離の長い方の画素であるｍ３５に進む。
【００４４】
このように、探索部１２１は、起点Ａ（ｍ２３）から、ｍ２４、次にｍ３５のように探索を続け、所定回数の探索、例えば７回探索を行う。７回の探索途中で接続および接触、あるいは、接続または接触している画素が存在しなくなった場合、そのルートの探索は打ち切り、途中で次の探索画素をランダムに選択した画素に戻り探索を行う。
同様に、図１５（ｅ）のように、探索部１２１は、起点Ｂ（ｍ３１）からの探索を行う。なお、探索の順番は、起点Ａまたは起点Ｂのどちらを先に行っても良い。
【００４５】
次に、特徴点が分岐点の場合の探索手順について図１６を用いて説明する。なお、図１６の各画素については、図１５（ａ）と同一のｍ１１〜ｍ５５の位置番号を用いて説明を行う。連結点の探索手順との違いは、特徴点の８近傍に３つの黒画素が存在していることである。探索部１２１は、特徴点の８近傍にある３つの黒画素の中からランダムに２つの画素を選択して、起点Ａ、起点Ｂとする。図１６（ａ）の例では、ｍ２３を起点Ａに、ｍ３１を起点Ｂに選択する。以下、図１６（ｂ）のように、起点Ａおよび起点Ｂからの探索は、連結点の場合と同様に行う。
【００４６】
図１７（ａ）は、特徴点が連結点の探索結果の一例を示す図である。図１７（ａ）のように、特徴点（ｍ２２）の８近傍にある黒画素のｍ１３を起点Ａとして探索を行った結果、探索終点Ａ（ｍ１９（ｘ１，ｙ９））に到達し、他方、特徴点（ｍ２２）の８近傍にある黒画素のｍ３２を起点Ｂとして探索を行った結果、探索終点Ｂ（ｍ９３（ｘ９，ｙ３））に到達する。
探索部１２１は、特徴点の８近傍にある黒画素を起点に探索を行った結果、予め定めた回数の探索を行い２つの起点に対する探索終点に到達した場合、参照した特徴点の座標と２つの探索終点の座標をベクトル生成部１２２に出力する。
また、特徴点の８近傍にある黒画素を起点に探索を行った結果、予め定めた回数の探索を行わないうちに探索終了点が探索できない場合、すなわち、その先に画素がない場合、探索部１２１は、参照した特徴点の座標と、探索した結果、探索終点が存在しなかった情報を頂点候補判定部１２４に出力する。
以上のようにして、探索部１２１は、特徴点の８近傍にある黒画素に接続および接触、あるいは、接続または接触している黒画素の探索を行う。
【００４７】
[頂点抽出手法および頂点推定手法の説明]
次に、図形形状認識部（ａ，ｂ，ｃ・・・）内の頂点抽出部１３１が行う頂点抽出手法と、頂点推定部１３２が行う頂点推定手法について、図１８〜図２３を用いて説明する。
【００４８】
まず、頂点抽出部１３１は、頂点候補集合記憶部１２７から未参照の１つの頂点候補集合（Ａ（ｘ０，ｙ０））を参照する。次に、頂点抽出部１３１は、参照した頂点候補集合のなす角θと、２本のベクトルと、頂点候補の座標、およびＮを読み出す。頂点抽出部１３１と頂点推定部１３２は、読み出したＮの値に応じて以下のように頂点抽出と頂点推定を行う。
【００４９】
[正Ｎ角形：Ｎが５以上の奇数]
Ｎが５以上の奇数の場合について、図１８と図１９を用いて説明する。図１８は、正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点抽出手法を説明する図である。図１９は、正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点推定手法を説明する図である。説明を簡略化にするために、Ｎ＝５の例について説明する。
頂点抽出部１３１は、Ｎ＝５、すなわち正五角形のため、正五角形の内角θ＝１０８度を算出する。または、頂点抽出部１３１が頂点候補集合記憶部１２７から参照した頂点候補のなす角θを用いる。
次に、頂点抽出部１３１は、以下の２本のベクトルを読み出す。
【００５０】
【数１】
【００５１】
【数２】
【００５２】
そして、頂点抽出部１３１は、読み出した２本のベクトルと、算出した内角θまたは参照したなす角θ＝１０８度を用いて、次式（２）と式（３）を用いて各ベクトルａ２、ｂ２、ａ３、ｂ３を算出する。
【００５３】
【数３】
【００５４】
【数４】
【００５５】
式（２）と式（３）においてｉ＝２，３であり、θ２＝（θ＋π）／２、θ３＝―（θ＋π）／２である。
次に、頂点抽出部１３１は、式（２）と式（３）により求めた以下に示す各ベクトルの組合せが、参照した頂点候補の特徴点Ａからの距離ｄｉが次式（４）を満たす頂点候補を頂点候補集合記憶部１２７から読み出して抽出する。
【００５６】
【数５】
【００５７】
【数６】
【００５８】
ｄ−α≦ｄｉ≦ｄ＋α・・・式（４）
【００５９】
なお、式（４）において、αは頂点候補集合における各２本のベクトルのなす角の誤差角度であり、また、ｄは正五角形の対角線の距離である。
すなわち、図１８において、頂点抽出部１３１は、参照した頂点候補Ａのベクトルａとベクトルｂ、なす角θ＝１０８と対になる２つの頂点候補Ｃと頂点候補Ｄを頂点候補集合記憶部１２７から抽出する。
まず、頂点抽出部１３１は、頂点候補Ｃ（ｘ２，ｙ２）、距離ｄ２、および以下の２本のベクトルを頂点候補集合記憶部１２７から読み出して抽出する。
【００６０】
【数７】
【００６１】
次に、頂点抽出部１３１は、頂点候補Ｄ（ｘ３，ｙ３）、距離ｄ３、および以下の２本のベクトルを頂点候補集合記憶部１２７から読み出して抽出する。
【００６２】
【数８】
【００６３】
上記の条件を満たす２つの頂点候補ＣとＤが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａを頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した２つの頂点候補集合（頂点ＣとＤ）を頂点推定部１３２に出力する。
上記の条件を満たす２つの頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点ではないと判定する。
【００６４】
なお、正五角形について説明したが、Ｎが５以上の奇数の正Ｎ角形の場合についても同様に、前述した頂点抽出手法を用いて２つの頂点候補を抽出する。その場合、正Ｎ角形の場合、内角θ＝３６０度／Ｎ、ｉ＝２，３を用いて式（２）と式（３）により同様にベクトルを算出する。また、式（４）において、ｄは正Ｎ角形の対角線のうち一番長い対角線の距離である。
【００６５】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｃと頂点Ｄの頂点候補集合を取り込む。また、頂点推定部１３２は、取り込んだ頂点Ａと頂点Ｃと頂点Ｄの頂点候補集合を用いて、残りの頂点（ＢとＥ）を推定する。正五角形の場合について、図１９を用いて頂点推定手法を説明する。
まず、頂点推定部１３２は、頂点Ａ（ｘ０，ｙ０）と頂点Ｃ（ｘ２，ｙ２）または頂点Ｄ（ｘ３，ｙ３）の各座標を用いて、頂点Ａと頂点Ｃと頂点Ｄを含む正五角形の外接円の半径ｒを算出する。図１９において、線分ＡＣの長さをｓとし、正五角形の中点をＯ（ｘｃ，ｙｃ）、角度∠ＯＡＣをβ、角度∠ＡＯＥとγとした場合、γ＝∠ＡＯＥ＝２π／Ｎより、∠ＡＯＣ＝π−π／Ｎであるため、β＝∠ＯＡＣ＝π／２Ｎとなる。したがって外接円の半径ｒは、次式（５）により算出できる。
【００６６】
ｒ＝ｓ／（２×ｃｏｓβ）・・・（５）
【００６７】
次に、頂点Ａのベクトルａの単位ベクトルを以下のように置くと、正五角形の中点Ｏ（ｘｃ，ｙｃ）は、次式（６）により算出できる。
【００６８】
【数９】
【００６９】
【数１０】
【００７０】
次に、頂点推定部１３２は、算出した正五角形の中点Ｏ（ｘｃ，ｙｃ）から頂点ＡのベクトルＯＡを回転角度γずつ回転することで、図形の残りの頂点Ｂと頂点Ｅを次式（７）および次式（８）を用いて推定する。
【００７１】
【数１１】
【００７２】
【数１２】
【００７３】
式（８）において、ｉは１以上でＮ−１以下の整数（ｉ＝（Ｎ−１）／２とｉ＝（（Ｎ−１）／２）＋１は除く）である。
【００７４】
また、頂点抽出部１３１が参照した頂点候補と抽出した２つの頂点候補と、頂点推定部１３２が推定した頂点とを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００７５】
[正Ｎ角形：Ｎが６以上の偶数]
次に、Ｎが６以上の偶数の場合について、図２０と図２１を用いて説明する。図２０は、正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点抽出手法を説明する図である。図２１は、正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点推定手法を説明する図である。説明を簡単にするために、Ｎ＝６の例について説明する。
頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００７６】
【数１３】
【００７７】
【数１４】
【００７８】
次に、図２０のように、読み出した頂点候補Ａの２本のベクトルとそれぞれ符号が逆の以下の２本のベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｄを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００７９】
【数１５】
【００８０】
【数１６】
【００８１】
上記の条件を満たす頂点候補Ｄが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｄ）の頂点候補集合を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【００８２】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｄの頂点候補集合を取り込む。また、頂点推定部１３２は、取り込んだ頂点Ａと頂点Ｄにより構成される正六角形の中点Ｏ（ｘｃ，ｙｃ）を、次式（９）を用いて算出する。
【００８３】
【数１７】
【００８４】
次に、頂点推定部１３２は、算出した中点Ｏ（ｘｃ，ｙｃ）から頂点Ａ（ｘ０，ｙ０）へのベクトルＯＡを回転した値を、次式（１０）で算出し、残りの頂点Ｂ，Ｃ，Ｅ，Ｆを抽出する。すなわち、正六角形なので、２π／Ｎ＝２π／６＝６０度ずつベクトルＯＡを回転することで順次、残りの頂点Ｂ，Ｃ，Ｅ，Ｆを抽出する。
【００８５】
【数１８】
【００８６】
式（１０）において、ｉは１以上でＮ−１以下の整数（ｉ＝Ｎ／２は除く）である。
以上のように、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｄと、頂点推定部１３２が推定した頂点Ｂ，Ｃ，Ｅ，Ｆを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００８７】
[正Ｎ角形：Ｎが３の場合]
正三角形の場合について、図２２を用いて説明する。図２２は、正三角形の場合の頂点抽出手法および頂点推定手法を説明する図である。頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００８８】
【数１９】
【００８９】
【数２０】
【００９０】
次に、図２２（ａ）と図２２（ｂ）のように、頂点抽出部１３１は、読み出した頂点候補Ａの２本のベクトルと、次式（１１）と次式（１２）を用いて頂点Ｂのベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｂを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００９１】
【数２１】
【００９２】
【数２２】
【００９３】
上記の条件を満たす頂点候補Ｂが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｂ）を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【００９４】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｂの各頂点候補集合を受け取る。また、頂点推定部１３２は、受け取った頂点Ａと頂点Ｂの頂点候補集合から各ベクトルを読み出す。また、頂点推定部１３２は、読み出したベクトルを用いて、頂点Ａと頂点Ｂの互いに向かい合わないベクトル、すなわちベクトルｂとベクトルａ１の交点を算出して、算出した頂点を残りの頂点Ｃ（ｘ２，ｙ２）として推定する。
また、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｂと、頂点推定部１３２が推定した頂点Ｃを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００９５】
[正Ｎ角形：Ｎが４の場合]
正方形の場合について、図２３を用いて説明する。図２３は、正方形の場合の頂点抽出手法および頂点推定手法を説明する図である。頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００９６】
【数２３】
【００９７】
【数２４】
【００９８】
次に、図２２（ａ）と図２２（ｂ）のように、頂点抽出部１３１は、読み出した頂点候補Ａの２本のベクトルとそれぞれ符号が逆のベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｂを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００９９】
【数２５】
【０１００】
【数２６】
【０１０１】
上記の条件を満たす頂点候補Ｂが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｂ）を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【０１０２】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｂの各頂点候補集合を受け取る。また、頂点推定部１３２は、受け取った頂点Ａと頂点Ｂの頂点候補集合から各ベクトルを読み出す。また、頂点推定部１３２は、読み出したベクトルを用いて、頂点Ａと頂点Ｂの互いに向かい合わないベクトル、すなわちベクトルｂとベクトル−aの交点を算出して、算出した頂点を残りの頂点Ｃ（ｘ２，ｙ２）として推定し、同様に、ベクトルａとベクトル−bの交点を算出して、算出した頂点を残りの頂点Ｄ（ｘ４，ｙ４）として推定する。
また、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｂと、頂点推定部１３２が推定した頂点Ｃと頂点Ｄを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に記憶する。
【０１０３】
[図形形状認識処理の手順]
次に、図形形状認識手順について、図８〜図１１のフローチャート、図１の構成図を用いて説明する。図８は、図形形状認識装置１０全体の図形形状認識手順を示すフローチャートである。以下、このフローチャートに沿って説明する。
【０１０４】
まず、カメラ１１が撮像した画像（濃淡画像）を画像データ取り込み部１０１が取得する（ステップＳ１）。画像データ取り込み部１０１は、取得した画像データを二値化処理部１０２に出力する。
【０１０５】
二値化処理部１０２は、画像データ取り込み部１０１が出力する画像データを取り込む。また、二値化部１０２は、取り込んだ画像データを、閾値を用いて二値化する（ステップＳ２）。また、二値化処理部１０２は、二値化した画像データをエッジ処理部１０３に出力する。なお、二値化における閾値の設定方法は、例えば大津の方法を用いて行う。
【０１０６】
エッジ処理部１０３は、二値化処理部１０２が出力する画像データを取り込む。また、エッジ処理部１０３は、取り込んだ画像データに対して、ラプラシアンフィルタ等を用いた一般的な手法によりエッジ処理を行う（ステップＳ３）。また、エッジ処理部１０３は、エッジ処理した画像情報（各黒画素の座標）をエッジ集合としてエッジ処理部１０３に書き込んで記憶させる。
【０１０７】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理終了後、エッジ処理部１０３が記憶するエッジ集合の中から未参照の画素を順次参照して、参照した画素を特徴点か否かの判定を行う（ステップＳ４）。
【０１０８】
次に、特徴点判定処理手順について、図９のフローチャートを用いて説明する。特徴点判定処理部１１０ａ内の連結点・分岐点判定部１１１は、エッジ処理部１０３内に記憶されているエッジ集合の中から未参照の１画素を参照する（ステップＳ１０１）。
【０１０９】
次に、連結点・分岐点判定部１１１は、参照した画素を注目点とし、エッジ処理部１０３に記憶されているエッジ集合を参照して注目点の８近傍の画素に２点以上の黒画素が存在しているか否かを判定する。次に、注目点の８近傍に２点以上の黒画素が存在していると判定した場合、連結点・分岐点判定部１１１は、注目点と８近傍に存在する黒画素との接続および接触、あるいは、接続または接触の構成パターンが連結点であるか、分岐点であるかを判定する。また、ノイズ除去部１１２は、連結点・分岐点判定部１１１が参照した注目点、および注目点の８近傍に存在する２つの黒画素の接続および接触、あるいは、接続または接触の構成パターンのうち、ノイズの構成パターンを除去する。また、特徴点判定部１１３は、連結点・分岐点判定部１１１の判定結果と、ノイズ除去部１１２の判定結果を用いて、参照した画素が線分の交点である特徴点であるか否かを判定する（ステップＳ１０２）。
ステップＳ１０２で参照した画素が特徴点であると判定した場合（ステップＳ１０２；Ｙｅｓ）、特徴点集合生成部１１４は参照した画素（注目点）とその画素を特徴点として特徴付ける情報（画素の座標と、その画素の８近傍にある黒画素の座標と、その画素と８近傍にある黒画素との構成パターン）を特徴点集合として生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる（ステップＳ１０３）。
ステップＳ１０２で参照した画素が特徴点でない判定した場合（ステップＳ１０２；Ｎｏ）、参照した画素についての特徴点判定処理を終了する。
【０１１０】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理部１０３に記憶されている全てのエッジ集合に含まれる画素に対してステップＳ４の特徴点判定処理を行う。また、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、特徴点判定処理を並列に処理する。すなわち、特徴点判定処理部１１０ａが、エッジ集合から画素１を参照して特徴点判定処理を行い、並列して特徴点判定処理部１１０ｂは、特徴点判定処理部１１０ａが参照していない画素を参照して特徴点判定処理を行う。また、特徴点判定処理が先に終了した特徴点判定処理部１１０ａまたは特徴点判定処理部１１０ｂは、未参照の画素を順次参照して特徴点判定を行う。
以上の処理により、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に特徴点判定処処理が終了した後、特徴点集合の生成が終了したことを頂点候補判定処理に出力する（ステップＳ５）。
【０１１１】
図８に戻り、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から全ての画素についての特徴点集合の生成が終了した情報を取り込んだ後、特徴点記憶部１１７が記憶している特徴点集合の中から未参照の１つの特徴点を順次参照して、参照した特徴点に対して頂点候補判定処理を行う（ステップＳ６）。
【０１１２】
次に、頂点候補判定処理手順について、図１０のフローチャートを用いて説明する。頂点候補判定処理部１２０ａ内の探索部１２１は、特徴点集合記憶部１１７が記憶している特徴点集合から未参照の１つの特徴点集合を参照する（ステップＳ２０１）。
【０１１３】
次に、探索部１２１は、参照した特徴点集合に基づいて、前述した探索手順により、特徴点に接続および接触、あるいは、接続または接触している画素の探索を行う（ステップＳ２０２）。
探索部１２１は、特徴点の８近傍にある黒画素を起点に探索を行った結果、所定回数の探索を行い２つの起点に対する探索終点に到達した場合（ステップＳ２０２；Ｙｅｓ）、参照した特徴点の座標と２つの探索終点の座標をベクトル生成部１２２に出力する。
また、特徴点の８近傍にある黒画素を起点に探索を行った結果、所定回数の探索を行わないうちに探索終点に到達した場合、すなわち、その先に画素がない場合、探索部１２１は、参照した特徴点の座標と、探索した結果、探索終点が存在しなかった情報を頂点候補判定部１２４に出力する。頂点候補判定部１２４は、参照した特徴点は探索終了点が存在しないと判定し（ステップＳ２０２；Ｎｏ）、参照した特徴点集合の頂点候補判定処理を終了する。
【０１１４】
次に、ベクトル生成部１２２は、探索部１２１から特徴点の座標と２つの探索終点の座標を取り込む。ベクトル生成部１２２は、取り込んだ特徴点の座標と２つの探索終点の座標を用いて、前述したベクトル生成手法により２本のベクトルを生成する（ステップＳ２０３）。また、ベクトル生成部１２２は、特徴点の座標と生成した２本のベクトルを頂点角度判定部１２３に出力する。
【０１１５】
次に、頂点角度判定部１２３は、ベクトル生成部１２２が生成した２本のベクトルと特徴点の座標とを取り込む。また、頂点角度判定部１２３は、ベクトル生成部１２２が生成した２本のベクトルのなす角θを算出する。また、頂点角度判定部１２３は、算出したなす角θについて、次式（１）を満たすＮ（Ｎは正の整数）を算出する。
【０１１６】
θ＝（（（Ｎ−２）×π）／Ｎ）±α・・・（１）
【０１１７】
また、頂点角度判定部１２３は、なす角θが６０度以下または１８０度以上の場合は、（１）式を満たさないのでＮＧと判定し、判定結果を頂点候補判定部１２４に出力する。また、頂点角度判定部１２３は、２本のベクトルのなす角θについて式（１）を満たすＮが算出できた場合、ＯＫと判定し、特徴点の座標と、２本のベクトルと、２本のベクトルのなす角θ、および頂点角度判定を頂点候補判定部１２４に出力する。
また、頂点候補判定部１２４は、頂点角度判定部１２３から特徴点の座標と、２本のベクトルと、２本のベクトルのなす角、および頂点角度判定を取り込み、取り込んだ頂点角度判定がＯＫの場合（ステップＳ２０４；Ｙｅｓ）、その特徴点を頂点候補として判定し、特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを頂点候補集合生成部１２５に出力する。
また、頂点候補判定部１２４は、受け取った頂点角度判定がＮＧの場合、頂点候補ではないと判定し（ステップＳ２０４；Ｎｏ）、参照した特徴点集合の頂点候補判定処理を終了する。
【０１１８】
次に、頂点候補集合生成部１２５は、頂点候補判定部１２４から、特徴点を頂点候補として特徴付ける情報として、特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを取り込む。また、頂点候補集合生成部１２５は、取り込んだ特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを関連付けて頂点候補集合を生成して、頂点候補集合記憶部１２７に書き込んで記憶させる（ステップＳ２０５）。
【０１１９】
頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、特徴点集合記憶部１１７が記憶する全ての特徴点集合に含まれる特徴点に対してステップＳ６の頂点候補判定処理を行う。また、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理を並列に処理する。すなわち、頂点候補判定処理部１２０ａが、特徴点集合から特徴点１を参照して頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｂは、頂点候補判定処理部１２０ａが参照していない特徴点２を参照して頂点候補判定処理を行う。また、頂点候補判定処理が先に終了した頂点候補判定処理部１２０ａまたは頂点候補判定処理部１２０ｂは、未参照の特徴点を順次参照して頂点候補判定を行う。
以上の処理により、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全ての特徴点集合の頂点候補判定処処理が終了した後、頂点候補集合の生成が終了した情報を図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）に出力する（ステップＳ７）。
【０１２０】
次に、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）から全ての特徴点についての頂点集合の生成が終了した情報を取り込んだ後、頂点候補集合記憶部１２７から未参照の１つの頂点候補集合を順次参照して頂点処理を行う（ステップＳ８）。
【０１２１】
次に、頂点処理手順について、図１１のフローチャートを用いて説明する。図形形状認識処理部１３０ａ内の頂点抽出部１３１は、頂点候補集合記憶部１２７が記憶している頂点候補集合から未参照の１つの頂点候補集合を参照する（ステップＳ３０１）。
【０１２２】
次に、頂点抽出部１３１は、参照した頂点候補集合を用いて、その頂点候補を含む図形の他の頂点候補を、前述した頂点抽出手法により頂点候補集合記憶部１２７が記憶している頂点候補集合から抽出する（ステップＳ３０２）。抽出する頂点候補数は、参照した頂点候補集合のＮに基づき、Ｎ＝３または４以上の偶数の場合は１つの頂点候補を抽出し、Ｎ＝５以上の奇数の場合は２つの頂点候補を算出する。また、頂点候補集合記憶部１２７から前述した各条件に合致する頂点候補が抽出できた場合、頂点抽出部１３１は、参照頂点候補を頂点であると判定する（ステップＳ３０２；Ｙｅｓ）。参照頂点候補を頂点と判定した場合、頂点抽出部１３１は、参照頂点候補集合と、抽出した頂点候補集合を頂点推定部１３２に出力する。
前述した各条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は参照した頂点候補を頂点ではないと判定し（ステップＳ３０２；Ｎｏ）、参照した頂点候補集合についての図形形状認識処理を終了する。
【０１２３】
次に、頂点推定部１３２は、頂点抽出部１３１が参照した頂点候補集合（以下、参照頂点候補集合）と抽出した頂点候補集合（以下、抽出頂点候補集合）を取り込む。また、頂点推定部１３２は、取り込んだ参照頂点候補集合と抽出頂点候補集合を用いて、これらの頂点候補を頂点として含む図形の他の頂点を前述した頂点推定手法により算出し、算出した頂点を残りの頂点として推定する。頂点の推定は、Ｎ＝３の場合は１点、Ｎ＝４，５の場合は２点、Ｎ＝６の場合は４点について行う。
また、頂点推定部１３２は、参照頂点候補集合と抽出頂点候補集合と、頂点推定部１３２が推定した頂点の座標とベクトルとを、頂点集合として頂点集合記憶部１３７に書き込んで記憶させる（ステップＳ３０４）。また、頂点推定部１３２は、頂点処理が終了した情報を図形形状認識部１３３に出力する。
【０１２４】
図８に戻り、図形形状認識部１３３は、頂点推定部１３２から頂点処理が終了した情報を取り込んだ後、頂点集合記憶部１３７に記憶されている未参照の頂点集合を順次参照する。また、図形形状認識部１３３は、参照した頂点集合に基づき、その頂点が構成する図形形状を認識し、認識した図形形状、およびその図形を構成している各頂点の座標等を画像出力部１４０に出力する（ステップＳ９）。
【０１２５】
図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補集合記憶部１２７が記憶する全ての頂点候補集合に含まれる頂点候補に対してステップＳ８の頂点処理を行う。また、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点処理を並列に処理する。すなわち、図形形状認識処理部１３０ａが、頂点候補集合から頂点候補１を参照して頂点処理を行い、並列して図形形状認識処理部１３０ｂは、頂点候補判定処理部１２０ａが参照していない頂点候補２を参照して頂点処理を行う。また、頂点処理が先に終了した図形形状認識処理部１２０ａまたは図形形状認識処理部１３０ｂは、未参照の頂点候補を順次参照して頂点判定処理を行う。
【０１２６】
画像出力部１４０は、図形形状認識部１３３が認識した図形形状およびその図形を構成している各頂点の座標等の図形形状認識結果を取り込み、取り込んだ図形形状認識結果を画像表示装置１３に出力する（ステップＳ１０）。また、画像表示装置１３は、画像出力部１４０が出力した図形形状認識結果を表示する。
以上により、図形形状認識処理を終了する。
【０１２７】
以上のように、本実施形態によれば、撮像した画像における線分の交点である特徴点の検出を、特徴点判定処理の並列処理が行いやすい画素ごとに行うようにしたので、図形形状認識処理を並列処理することで高速化を実現することができる。また、図形形状認識において、従来技術のようにラベリング処理に替えて、図形を構成している頂点を抽出し、抽出した頂点を用いて図形の他の頂点や図形の形状を推定するようにしたので、さらに図形形状における認識処理の高速化を実現することができる。また、本実施形態の図形認識処理は、ラベリング処理のように取得した画面全体に処理を行う場合と比較し、各処理を並列して行いやすい単位に設定してあるので、複数の特徴点判定処理、または複数の頂点候補判定処理、または複数の図形形状認識処理において、各処理の計算量の均一化が容易なため、並列処理を容易にすることができる。
【０１２８】
また、本実施形態では、エッジ処理部１０３は、二値化処理部１０２で二値化された入力画像を用いてエッジ処理を行う例について説明したが、画像データ取り込み部１０１が取り込んだ画像データである濃淡画像に直接エッジ処理を行うようにしても良い。
【０１２９】
また、本実施形態では、頂点角度判定部１２３で全てのＮについて式（１）を満たすか判定する例について説明したが、認識したい図形の形状が予め分かっている場合等、用途に応じて、一定の範囲のＮ、例えば３≦Ｎ≦１０のみを頂点候補として判定しても良い。
【０１３０】
また、本実施形態では、図形の形状を、まず頂点候補判定処理部が１つの頂点候補を抽出し、次に図形形状認識処理部が残りの頂点を抽出し、次にこれらの抽出した頂点候補を用いて残りの頂点を推定して図形形状を認識する例について説明したが、残りの頂点を推定で算出するのではなく、図形形状認識処理部が残りの頂点を抽出するようにしても良い。この場合においても、図形形状の認識において図形の頂点のみを抽出しているので、ラベリングを行う手法と比較して高速に図形形状を認識することができる。
【０１３１】
また、本実施形態では、図形の形状を、まず頂点候補判定処理部が１つの頂点候補を抽出し、次に図形形状認識処理部が残りの頂点を抽出し、次にこれらの抽出した頂点候補を用いて残りの頂点を推定して図形形状を認識する例について説明したが、残りの頂点を推定により算出した後、頂点推定部１３２は推定した頂点と、頂点候補集合記憶部１２７が記憶している頂点候補集合を比較して、が頂点候補集合に実在しているか否かを判定する用ようにしても良い。これにより、さらに図形形状の認識精度を向上することができる。
【０１３２】
また、本実施形態では、カメラ１１が撮像した画像データから図形形状を認識する例を説明したが、予め取得した画像データから図形形状認識を行っても良い。また、本実施形態では、画像データ取り込み部１０１が取り込んだ画像を二値化処理部１０２で二値化処理した後にエッジ処理する例を説明したが、取り込んだ画像データに直接エッジ処理を行っても良い。
【０１３３】
なお、実施形態の図１の各部の機能を実現するためのプログラムをコンピューター読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピューターシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピューターシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピューターシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピューター読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピューターシステムに内蔵されるハードディスク等、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ） Ｉ／Ｆを介して接続されるＵＳＢメモリー等の記憶装置のことをいう。さらに「コンピューター読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピューターシステム内部の揮発性メモリーのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピューターシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１３４】
また、本実施形態では、特徴点判定処理と、頂点候補判定処理と、頂点処理（図形認識処理）とを、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）で並列処理する例について説明したが、並列処理は図示しない複数のＣＰＵで行うことも可能である。この場合、例えば、ＣＰＵ１が特徴点判定処理部１１０ａの処理を行い、ＣＰＵ２が特徴点判定処理部１１０ｂの処理を行う。または、１つのＣＰＵで特徴点判定処理部１１０ａと特徴点判定処理部１１０ｂとを並列処理するようにしても良い。
また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）の少なくとも１つが複数の処理部を備えていて、複数の特徴点判定処理部を並列処理、または複数の頂点候補判定処理部を並列処理、または複数の図形形状認識処理部を並列処理するようにしても良い。
【０１３５】
さらにまた、本実施形態では、特徴点判定処理と、頂点候補判定処理と、頂点処理（図形認識処理）とを、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）で並列処理する例について説明したが、各処理部（特徴点判定処理部１１０と頂点候補判定処理部１２０と複数の図形形状認識処理部１３０）はそれぞれ１つずつで並列処理を行わなくても良い。この場合においても、本実施形態で説明した特徴点判定処理や頂点候補判定処理、および頂点処理（図形認識処理）を用いれば、従来のラベリングを用いた図形形状認識装置より高速な図形形状の認識を行うことができる。
【符号の説明】
【０１３６】
１０・・・図形形状認識装置
１０１・・・画像データ取り込み部
１０２・・・二値化処理部
１０３・・・エッジ処理部
１１０（ａ，ｂ，ｃ・・・）・・・特徴点判定処理部
１１７・・・特徴点集合記憶部
１２０（ａ，ｂ，ｃ・・・）・・・頂点候補判定処理部
１２７・・・頂点候補記憶部
１３０（ａ，ｂ，ｃ・・・）・・・図形形状認識処理部
１３７・・・頂点集合記憶部
１４０・・・画像出力部
１１・・・カメラ
１３・・・画像表示部
【技術分野】
【０００１】
本発明は、図形形状認識装置、図形形状認識方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、現実環境にコンピューターを用いて情報を付加提供するＡＲ（Ａｕｇｍｅｎｔｅｄ Ｒｅａｌｉｔｙ；拡張現実）の技術が注目されている。ＡＲの実現方法としては各種の方法が提案されているが、その１つとしてマーカーを使う方法（マーカー型ＡＲ）が提案されている。マーカーを使う方法においては、予めマーカーとして定められている二次元バーコード等の画像を用い、このマーカーを対象となる空間である画像内に設置する。図２４は、マーカーの一例を示す図である。また、図２５は、二値化されたマーカーを含む入力画像の一例を示す図である。図２５のように、画像中に図２４のマーカーが配置されている。このように、図形形状認識装置が、マーカーを含む画像を取得し、取得した画像中からマーカーを検出し、検出したマーカーに予めリンクされているプログラム等が起動する。具体的な例として、名刺にマーカーを埋め込んで生成した場合、このマーカーを含む名刺の画像をカメラで撮像して、図形形状認識装置で処理を行うと、マーカーにリンクした人物の写真や動画が再生される。
【０００３】
このような撮像された画像からの図形形状認識装置における図形形状認識手法としては、以下のような手法がある。まず、撮像された画像を取得し、取得した画像（濃淡画像）にエッジ処理を行うか、もしくは取得した画像を二値化し、二値化した画像に対してエッジ処理を行う。そして、図形形状認識装置が、エッジ処理した情報に基づいてラベリング処理を行うことで、検出物体の輪郭を抽出して、抽出した輪郭情報に基づいて検出物体の形状認識を行うといった手法がある（例えば、特許文献１参照）。
【０００４】
ここで、ラベリング処理とは、エッジ処理した画像情報を用いて、同じ連結成分に属する全ての画素に同じラベルを割り当て、異なった連結成分には異なったラベルを割り当てる処理である。図２６は、ラベリング処理を説明する図である。図２６において、探索開始点から同じ連結成分を境界追跡法（例えば８近傍）のアルゴリズムによる探索を行い、ラベル１を割り当てる。同様に異なる連結成分にはラベル２、ラベル３が割り当てられる。このようにして、同じ連結部分を検出することで、取得された画像の中から輪郭を抽出する。図２６は、ラベリング処理された画像の一例を示す図である。図２７は、図２５の画像をラベリングした例であり、抽出された輪郭の一部を示している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平５−１６５９６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
例えば、このようなＡＲをインターネット等のＷｅｂアプリケーション等で実現する場合、図形形状認識装置として一般のコンピューター等が利用可能である。近年のコンピューターはマルチコア化が進んでおり、このようなマルチコアを有効に利用するためには、図形形状認識方法において、取得した画像を一定の領域単位に分割して並列処理する必要がある。
しかしながら、特許文献１の手法において、取得された画像を一定の領域単位に分割しようとしても、ラベリングの探索範囲が取得された画像によって変化するため、単純に処理領域を分割することは困難であるという課題があった。また、仮に予め定めておいた領域ごとに分割して並列処理を行った場合、ラベリングを行った対象が分割により分断されてしまうこともある。この場合、分断された各ラベル領域が同一の領域であるのかを別途判定する必要が生じてしまい、並列処理と単一処理との演算コストが変わらないか、演算量が増加してしまう場合もあるという課題があった。
【０００７】
本発明は、上記の課題に鑑みてなされたものであって、高速な図形の形状認識を行い、さらに並列処理に最適な領域単位で処理することでより高速な図形の形状認識を行う図形形状認装置、図形形状認識方法、およびプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明は、図形形状認識装置において、エッジ処理した入力画像の全ての画素を１画素ずつ参照し、線分の交点である特徴点を全て検出する特徴点判定処理部と、前記特徴点判定部が検出した全ての前記特徴点を１つずつ参照し、全ての頂点候補を検出する頂点候補判定処理部と、前記頂点候補判定処理部が検出した頂点候補を１つずつ参照し、参照した前記頂点候補に基づき当該頂点候補を含み図形を構成する他の頂点候補を検出し、検出した前記頂点候補に基づいて図形形状を認識する図形形状認識処理部とを備えることを特徴としている。
【０００９】
また、本発明は、図形形状認識装置において、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理部と、前記特徴点判定部が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判定処理部と、前記頂点候補判定部が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理部とを備えることを特徴としている。
【００１０】
また、本発明は、図形形状認識装置において、前記特徴点判定処理部は、参照した前記画素の八近傍における隣接画素同士の接続および接触、あるいは、接続または接触の構成に基づいて構成パターンを検出し、検出した構成パターンに基づいて前記画素が特徴点か否かを判定することを特徴としている。
【００１１】
また、本発明は、図形形状認識装置において、前記頂点候補判定処理部は、参照した特徴点を特徴付ける情報を用いて前記特徴点に隣接している画素を順次探索し、探索した結果に基づき前記特徴点を始点とし探索終了点を終了点とする２本のベクトルを生成し、生成した前記２本のベクトルのなす角を算出し、生成した前記２本のベクトルの各距離と前記なす角を用いて頂点候補か否かを判定することを特徴としている。
【００１２】
また、本発明は、図形形状認識装置において、前記特徴点判定処理部、前記頂点候補判定処理部、前記図形形状認識処理部のうち少なくとも１つの処理部を複数備え、複数の前記特徴点判定処理部が並列処理、または複数の前記頂点候補判定処理部が並列処理、または複数の前記図形形状認識処理部が並列処理することを特徴としている。
【００１３】
また、本発明は、図形形状認識方法において、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程とを含むことを特徴としている。
【００１４】
また、本発明は、図形形状認識装置のプログラムにおいて、コンピューターに、エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程とを実行させることを特徴としている。
【発明の効果】
【００１５】
本発明によれば、取得した画像から、画素単位で線分の交点である特徴点の抽出を行い、抽出した特徴点に関する情報を特徴点集合として生成し、生成した特徴点集合から頂点候補を抽出し、抽出した特徴点候補に関する情報を頂点候補集合として生成し、さらに生成した頂点候補集合から図形の頂点の抽出と他の頂点の推定を行うことが可能となる。さらにまた、各処理を並列演算に最適な画素単位にしたため、並列演算による高速な図形形状の認識を行うことが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態に係る図形形状認識装置の構成の一例を示すブロック図である。
【図２】同実施形態に係る図２４の二値化画像をエッジ処理した後の画像データの一例を示す図である。
【図３】同実施形態に係る検出した特徴点の一例を示す図である。
【図４】同実施形態に係る頂点候補を説明する図である。
【図５】同実施形態に係る特徴点集合の構成の一例を示す図である。
【図６】同実施形態に係る頂点候補集合の構成の一例を示す図である。
【図７】同実施形態に係る頂点集合の構成の一例を示す図である。
【図８】同実施形態に係る図形形状認識方法のフローチャートである。
【図９】同実施形態に係る特徴点処理手順のフローチャートである。
【図１０】同実施形態に係る頂点候補処理手順のフローチャートである。
【図１１】同実施形態に係る頂点処理手順のフローチャートである。
【図１２】同実施形態に係る連結点と分岐点の例を説明する図である。
【図１３】同実施形態に係る注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成がノイズと判定される例を説明する図である。
【図１４】同実施形態に係る注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成が特徴点ではないと判定される例を説明する図である。
【図１５】同実施形態に係る特徴点が連結点の場合の探索を説明する図である。
【図１６】同実施形態に係る特徴点が分岐点の場合の探索を説明する図である。
【図１７】同実施形態に係る探索結果およびベクトル生成手法を説明する図である。
【図１８】同実施形態に係る正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点抽出手法を説明する図である。
【図１９】同実施形態に係る正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点推定手法を説明する図である。
【図２０】同実施形態に係る正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点抽出手法を説明する図である。
【図２１】同実施形態に係る正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点推定手法を説明する図である。
【図２２】同実施形態に係る正三角形の場合の頂点抽出手法および頂点推定手法を説明する図である。
【図２３】同実施形態に係る正方形の場合の頂点抽出手法および頂点推定手法を説明する図である。
【図２４】マーカーの一例を示す図である。
【図２５】二値化されたマーカーを含む入力画像の一例を示す図である。
【図２６】ラベリング処理を説明する図である。
【図２７】ラベリング処理された画像の一例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、図１〜図２５を用いて説明する。なお、本発明は係る実施形態の構成に限定されず、本発明の技術思想の範囲内で種々の変更が可能である。
【００１８】
図１は、図形形状認識装置の構成の一例を示すブロック図である。図１のように、図形形状認識装置１０は、画像データ取り込み部１０１と、二値化処理部１０２と、エッジ処理部１０３と、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と、特徴点集合記憶部１１７と、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と、頂点候補集合記憶部１２７と、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）と、頂点集合記憶部１３７と、画像出力部１４０とを備える。また、図形形状認識装置１０には、カメラ１１と、画像表示装置１３が接続されている。
また、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、それぞれ連結点・分岐点判断部１１１と、ノイズ除去部１１２と、特徴点判定部１１３と、特徴点集合生成部１１４とを備える。
また、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、それぞれ探索部１２１と、ベクトル生成部１２２と、頂点角度判定部１２３と、頂点候補判定部１２４と、頂点候補集合生成部１２５とを備える。
また、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、それぞれ頂点抽出部１３１と、頂点推定部１３２と、図形形状認識部１３３とを備える。
【００１９】
カメラ１１は、例えば受光レンズとＣＣＤカメラ等で構成され、検出図形を含む入力画像を撮影し、撮影された画像データを図形形状認識装置１０に送信する。画像表示装置１３は、図形形状認識装置１０から図形形状認識結果の表示用の画像を受信し、受信した画像を表示する。
【００２０】
画像データ取り込み部１０１は、カメラ１１により撮影された検出図形を含む入力画像を取り込み、取り込んだ画像データを二値化処理部１０２に出力する。
【００２１】
二値化処理部１０２は、画像データ取り込み部１０１が出力する画像データを取り込む。また、二値化部１０２は、取り込んだ画像データに対して、閾値を用いて二値化し、二値化した画像情報をエッジ処理部１０３に出力する。なお、二値化における閾値の設定方法は、例えば１９７９年に大津展之によって提案された方法（以下、大津の方法）を用いて行う。図２５は、二値化されたマーカーを含む入力画像の一例を示す図である。
【００２２】
エッジ処理部１０３は、二値化処理部１０２が出力する画像データを取り込む。また、エッジ処理部１０３は、取り込んだ二値化された画像データに対して、ラプラシアンフィルタを用いた一般的な手法を用いたエッジ処理を行う。また、エッジ処理部１０３は、エッジ処理した画像データをエッジ集合としてエッジ処理部１０３に書き込んで記憶させる。図２は、図２５の二値化画像をエッジ処理した後の画像データの一例を示す図である。また、エッジ集合は、エッジ処理部１０３がエッジ処理により生成した各画素の座標（ｘ，ｙ）の各データを有している。また、エッジ処理は、ラプラシアンフィルタ以外の一般的な手法を用いても良い。
【００２３】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理部１０３に記憶されているエッジ集合の中から未参照の画素を未参照の画素がなくなるまで参照する。また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、参照した画素の特徴点判定を行い、線分の交点である特徴点と判定した画素および特徴点を特徴付ける情報を特徴点集合として生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる。なお、参照するとは、エッジ処理部１０３に記憶されているエッジ集合の中から画素を読み出す処理のことであり、また未参照の画素を未参照の画素がなくなるまで参照するとは、まだ読み出していない画素を未参照の画素がなくなるまで読み出す処理のことである。
また、各特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、特徴点判定処理を並列に処理する。例えば、取得した画像が６４０×４８０画素（＝３０７２００画素）の場合、特徴点判定処理部１１０ａが１番目の画素の特徴点判定処理を行い、並列して特徴点判定処理部１１０ｂが４番目の画素の特徴点判定処理を行い、並列して特徴点判定処理部１１０ｃが７番目の画素の特徴点判定処理を行う。特徴点判定処理を終了した特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、未参照の画素を未参照の画素がなくなるまで参照して、参照した画素の特徴点判定処理を順次行い、取得した画像全ての画素について特徴点判定処理を行う。また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に対して特徴点判定が終了した後、特徴点集合の生成が終了した情報を頂点候補判定処理１２０（ａ，ｂ，ｃ・・・）に出力する。また、各特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が、取得した画素を参照する順番は、例えばエッジ集合の中から順番に読み出しても良く、あるいはランダムに読み出しても良く、さらには、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）ごとに予め定めた領域を読み出すようにしても良い。
【００２４】
以下に、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
連結点・分岐点判定部１１１は、エッジ処理部１０３が記憶するエッジ集合の中から未参照の画素の中から１画素を参照する。次に、連結点・分岐点判定部１１１は、参照した画素を注目点とし、エッジ集合を参照して注目点の８近傍に２点以上の黒画素が存在しているか否かを判定する。注目点の８近傍に２点以上の黒画素が存在していると判定した場合、連結点・分岐点判定部１１１は、注目点と８近傍に存在する黒画素との接続および接触、あるいは、接続または接触の構成パターンが連結点であるか、分岐点であるかを判定する。
連結点と分岐点の具体的な例を、図１２を用いて説明する。図１２（ａ）において、画素ｍ５が注目点であり、ｍ１〜ｍ９（ｍ５を除く）の画素が８近傍の画素である。図１２（ａ）のように、注目点ｍ５に画素ｍ８と画素ｍ３が接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「連結点」と定義する。連結点の他の例は、（ｍ１，ｍ５，ｍ８），（ｍ２，ｍ５，ｍ７），（ｍ２，ｍ５，ｍ９），（ｍ４，ｍ５，ｍ３），（ｍ４，ｍ５，ｍ９），（ｍ１，ｍ５，ｍ６），（ｍ７，ｍ５，ｍ６）の３画素が接続および接触、あるいは、接続または接触している状態である。
図１２（ｂ）のように、注目点ｍ５に画素ｍ２と画素ｍ６および画素ｍ８が接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「分岐点」と定義する。連結点の他の例は、（ｍ２，ｍ４，ｍ５，ｍ８），（ｍ２，ｍ４，ｍ５，ｍ６），（ｍ４，ｍ５，ｍ６，ｍ８）の４画素が接続および接触、あるいは、接続または接触している状態である。
【００２５】
ノイズ除去部１１２は、連結点・分岐点判定部１１１が参照した注目点、および注目点の８近傍に存在する２つの黒画素の接続および接触、あるいは、接続または接触の構成パターンのうち、ノイズの構成パターンを除去する。特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）が抽出したい特徴点は、図形を特徴付けている線分の交点であり、辺である線分ではない。すなわち、特徴点とは、複数の線分をつなぎ合わせた交点（線分の終点同士をつなぎ合わせた点も含む）であり、多角形の１８０度以内の頂点、多角形の１８０度以上の頂点、閉じていない線分の交点などを備えている。このため、直線は特徴点ではないため、参照した注目点、および注目点の８近傍の２つの黒画素が直線的に接続および接触、あるいは、接続または接触している状態を、構成パターンの１つとして「ノイズ」と定義する。具体例として、注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成パターンを、ノイズと判定する例を、図１３を用いて説明する。図１３のように、注目点と８近傍にある黒画素が、縦または横、または斜めに直線的に接続および接触、あるいは、接続または接触している構成パターンがノイズである。
【００２６】
特徴点判定部１１３は、連結点・分岐点判断部１１１の判定結果とノイズ除去部１１２の判定結果に基づき、特徴点を判定する。特徴点と判定する条件は、連結点・分岐点判断部１１１が連結点または分岐点と判定した画素、かつノイズ除去部１１２がノイズと判定しなかった画素である。また、特徴点ではないと判定する条件は、連結点・分岐点判断部１１１が連結点または分岐点と判定しなかった画素、またはノイズ除去部１１２がノイズと判定した画素、または８近傍に黒画素が２画素以上ない画素である。図１４は、注目点と８近傍にある画素の接続および接触、あるいは、接続または接触の構成パターンが特徴点ではないと判定される例を説明する図である。図１４（ａ）のように、参照した画素（注目点）の８近傍に１つの黒画素しか接続あるいは接触していない構成パターンを、特徴点判定部１１３は特徴点ではないと判定する。また、図１４（ｂ）のように、参照した画素（注目点）の８近傍に４つの黒画素が接続および接触、あるいは、接続または接触している構成パターンを、特徴点判定部１１３は特徴点ではないと判定する。
すなわち構成パターンとは、連結点・分岐点判断部１１１が参照した画素とその画素の８近傍の画素の接続および接触、あるいは、接続または接触の構成によるものである。また、構成パターンの種類は、連結点であるパターンと、分岐点であるパターンと、ノイズであるパターンと、８近傍に黒画素が２画素以上ないパターンなどである。図３は、検出した特徴点の一例を示す図である。図３において、白抜き丸〇は、特徴点判定部１１３が検出した特徴点の一例である。
【００２７】
特徴点集合生成部１１４は、特徴点判定部１１３が特徴点であると判定した画素を特徴点として特徴付ける情報として、連結点・分岐点判断部１１１が参照した画素とその８近傍に接続および接触、あるいは、接続または接触している２つ以上の黒画素の座標と、構成パターンの種類（連結点または分岐点）を関連付けて特徴点集合を生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる。また、特徴点集合生成部１１４は、特徴点集合の生成が終了したことを頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）に出力する。図５は、特徴点集合の構成の一例を示す図である。図５のように特徴点集合は、表形式のデータとして実現されており、特徴点の座標と、特徴点の構成パターン（連結点か分岐点か）と、特徴点に接続および接触、あるいは、接続または接触されている画素の座標の各データを有している。
【００２８】
頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に対して特徴点判定が終了した後、特徴点集合の生成が終了した情報を特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から取り込んだ後、特徴点集合記憶部１１７が記憶している特徴点集合の中から未参照の特徴点を未参照の特徴点がなくなるまで参照する。頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）が特徴点を参照する順番は、特徴点集合記憶部１１７が記憶している順番に参照しても良く、あるいはランダムに参照しても良い。また、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、参照した特徴点について 頂点候補判定を行い、頂点候補と判定した特徴点および頂点候補を特徴付ける情報を頂点候補集合として頂点候補記憶部１２７に記憶する。
また、各頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理を並列に処理する。例えば、取得した特徴点集合が１００組合せの場合、頂点候補判定処理部１２０ａが１番目の特徴点集合の組合せについて頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｂが２番目の特徴点集合の組合せについて頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｃが３番目の特徴点集合の組合せについて頂点候補判定処理を行う。頂点候補判定処理を終了した頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、未参照の特徴点集合の組合せについて順次参照して、参照した特徴点集合の組合せについて頂点候補判定処理を順次行い、参照した全ての特徴点集合について頂点候補判定処理を行う。また、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全ての特徴点集合の特徴点に対して頂点候補判定が終了した後、頂点候補集合の生成が終了した情報を図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）に出力する。
【００２９】
以下に、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
探索部１２１は、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から特徴点集合の生成が終了した情報を取り込んだ後、特徴点集合記憶部１１７が記憶している特徴点集合の中から未参照の１つの特徴点集合を参照する。また、探索部１２１は、参照した特徴点集合から特徴点の座標と、参照した特徴点に接続および接触、あるいは、接続または接触している画素の座標と構成パターン（連結点、分岐点）を読み出す。また、探索部１２１は、読み出した特徴点の８近傍に接続および接触、あるいは、接続または接触している２つの黒画素を起点として選択して、後述する探索手順に基づき接続および接触、あるいは、接続または接触している画素を、所定の回数、順次探索する。また、探索部１２１は、参照した特徴点の座標と探索結果の２つの探索終点の座標を、ベクトル生成部１２２に出力する。図１７は、探索結果およびベクトル生成手法を説明する図であり、図１７（ａ）は、特徴点の８近傍に接続および接触、あるいは、接続または接触している画素から順次探索した結果の例である。図１７（ａ）の例では、探索部１２１が特徴点の８近傍に接続および接触、あるいは、接続または接触している黒画素を起点に、接続および接触、あるいは、接続または接触している黒画素ｍ１３とｍ３２から順次探索した結果、探索終点Ａ（ｍ９１（ｘ９，ｙ１））と探索終点Ｂ（ｍ３９（ｘ３，ｙ９））に到達する。
【００３０】
ベクトル生成部１２２は、探索部１２１が探索した結果である特徴点の座標と、探索した終点の座標を取り込む。また、ベクトル生成部１２２は、取り込んだ特徴点の座標と、探索した終点の座標を用いて、２本のベクトル（特徴点と探索終点Ａ、特徴点と探索終点Ｂ）を生成し、特徴点の座標と生成した２本のベクトルを頂点角度判定部１２３に出力する。図１７（ｂ）は、特徴点と探索終点からベクトルを生成した例である。図１７（ｂ）の例では、ベクトル生成部１２２は、特徴点ｍ２２（ｘ２，ｙ２）から探索終点Ａ（ｍ９１（ｘ９，ｙ１））に向かうベクトルＡと、特徴点ｍ２２（ｘ２，ｙ２）から探索終点Ｂ（ｍ３９（ｘ３，ｙ９））に向かうベクトルを生成する。
【００３１】
頂点角度判定部１２３は、ベクトル生成部１２２が出力する特徴点の座標と２本のベクトルを取り込む。また、頂点角度判定部１２３は、取り込んだ２本のベクトルのなす角θを算出する。また、頂点角度判定部１２３は、算出したなす角θについて、次式（１）を満たすＮを算出する。
【００３２】
θ＝（（（Ｎ−２）×π）／Ｎ）±α・・・（１）
【００３３】
式（１）において、Ｎは正Ｎ角形を構成する頂点の数、αは図形形状を認識する上での予め定められた誤差角度である。また、誤差角度αは、例えば５度などの一定の角度でも良く、あるいはＮに応じて設定しても良い。また、頂点角度判定部１２３は、算出したＮが３以下（なす角θが６０度以下）、さらに１８０度以上の場合は、式（１）を満たさないと判定する。また、頂点角度判定部１２３は、頂点角度判定の判定結果と、特徴点の座標、２本のベクトルおよびなす角θを頂点候補判定部１２４に出力する。
【００３４】
頂点候補判定部１２４は、頂点角度判定部１２３が出力する判定結果と、特徴点の座標と、２本のベクトルおよびなす角θを取り込む。頂点候補判定部１２４は、取り込んだ頂点角度判定の判定結果と、特徴点の座標と、２本のベクトルおよびなす角θに基づいて、探索部１２１が参照した特徴点を頂点候補か否か判定する。頂点候補判定部１２４は、特徴点に対して２本のベクトルが存在ない場合、特徴点に接続および接触、あるいは、接続または接触している画素が連続していないため、すなわち図形のコーナーではないため頂点候補ではないと判定する。また、頂点候補判定部１２４は、頂点候補と判定した特徴点の座標、２本のベクトル、なす角θ、および式（１）との比較により算出したＮを頂点候補集合生成部１２５に出力する。図４は、頂点候補を説明する図である。図４の白抜き丸〇は、頂点候補判定部１２４が頂点候補として判定した特徴点の一例である。
【００３５】
頂点候補集合生成部１２５は、頂点候補判定部１２４が出力する特徴点の座標、２本のベクトル、なす角θ、およびＮを取り込む。また、頂点候補集合生成部１２５は、特徴点を頂点候補として特徴付ける情報として、取り込んだ特徴点の座標、２本のベクトル、なす角θ、およびＮを関連付けて頂点候補集合を生成し、生成した頂点候補集合を頂点候補集合記憶部１２７に記憶する。図６は、頂点候補集合の構成の一例を示す図である。図６のように、頂点候補集合は、表形式のデータとして実現されており、特徴点の座標と、２本のベクトル（ａ、ｂ）と、Ｎと、なす角θの各データを有している。
【００３６】
図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）から頂点候補集合の生成が終了した情報を取り込んだ後、頂点候補集合記憶部１２７が記憶している頂点候補集合の中から未参照の頂点候補を未参照の頂点候補がなくなるまで参照する。図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）が頂点候補を参照する順番は、頂点候補集合記憶部１２７が記憶している順番に参照しても良く、あるいはランダムに参照しても良い。また、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、参照した頂点候補について、参照した頂点候補を含む図形を構成する他の頂点抽出と推定を行い、参照した頂点候補と抽出および推定した頂点に基づき図形形状の認識を行い、図形形状の認識結果を画像出力部１４０に出力する。
また、各図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、図形形状認識処理を並列に処理する。例えば、取得した頂点候補集合が２０組合せの場合、図形形状認識処理部１３０ａが１番目の頂点候補集合の組合せについて図形形状認識処理を行い、並列して図形形状認識処理部１３０ｂが２番目の頂点候補集合の組合せについて図形形状認識処理を行い、並列して図形形状認識処理部１３０ｃが３番目の頂点候補集合の組合せについて図形形状認識処理を行う。図形形状認識処理を終了した図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、未参照の頂点候補集合の組合せについて順次参照して、参照した頂点候補集合の組合せについて図形形状認識処理を順次行い、取得した全ての頂点候補集合について図形形状認識処理を行う。
【００３７】
以下に、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）が備える各機能部について、説明する。
頂点抽出部１３１は、頂点候補集合記憶部１２７が記憶している頂点候補集合の中から未参照の頂点候補集合を順次参照して、参照した頂点候補集合から頂点候補（以後、参照頂点候補）の座標、ベクトル、Ｎおよびなす角θを読み出す。また、頂点抽出部１３１は、Ｎ（正Ｎ角形）に基づき、参照頂点候補を含む図形の他の頂点を、頂点候補集合の中から抽出し、抽出した頂点候補（以下、抽出頂点候補という）と参照頂点候補の各頂点候補集合を頂点推定部１３２に出力する。
【００３８】
頂点推定部１３２は、頂点抽出部１３１から参照頂点候補と抽出頂点候補の頂点集合を取り込む。また、頂点推定部１３２は、取り込んだ参照頂点候補と抽出頂点候補の頂点候補集合を用いて、それらの頂点候補を含む図形の他の頂点候補の座標を、後述する頂点推定手法を用いて演算により推定する。また、頂点推定部１３２は、参照頂点候補と抽出頂点候補の各頂点候補集合、および推定した頂点を関連づけ、頂点集合として頂点集合記憶部１３７に記憶する。
図７は、頂点集合記憶部１３７が記憶する頂点集合の構成の一例を示す図である。図７のように、頂点集合は、表形式のデータとして実現されており、図形ごとに頂点の座標と各頂点のベクトルの各データを有している。
【００３９】
図形形状認識部１３３は、頂点集合記憶部１３７に記憶されている頂点集合を読み出す。また、図形形状認識部１３３は、読み出した頂点集合に基づき、その頂点が構成する図形形状を認識し、認識した図形形状およびその図形を構成している各頂点の座標等を画像出力部１４０に出力する。
【００４０】
画像出力部１４０は、図形形状認識部１３３が認識した図形形状およびその図形を構成している各頂点の座標等が認識結果を取り込み、取り込んだ認識結果を画像表示装置１３に出力する。
【００４１】
[探索手順の説明]
次に、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）内の探索部１２１の探索手順について、図１５〜図１７を用いて詳細に説明する。図１５は、特徴点が連結点の場合の探索を説明する図である。図１６は、特徴点が分岐点の場合の探索を説明する図である。図１７は、探索結果およびベクトル生成手法を説明する図である。
【００４２】
まず、特徴点が連結点の場合の探索手順について図１５を用いて説明する。説明を簡略化するために、５×５（＝２５画素）内での探索を例に説明する。便宜的に、図１５（ａ）のように各画素についてｍ１１〜ｍ５５の位置番号をつけ説明を行う。特徴点集合記憶部１１７から読み出した特徴点集合が（特徴点ｍ２２（ｘ２，ｙ２）；連結点；接続および接触、あるいは、接続または接触されている画素ｍ２３（ｘ２，ｙ３），ｍ３１（ｘ３，ｙ１））の場合、探索部１２１は、図１５（ｂ）のように、特徴点ｍ２２に接続および接触、あるいは、接続または接触されている画素ｍ２３とｍ３１をそれぞれ起点Ａ、起点Ｂに設定し、まず、起点Ａから探索を開始する。
【００４３】
次に、探索部１２１は、起点Ａ（ｍ２３）の８近傍に接続および接触、あるいは、接続または接触している特徴点以外の黒画素をエッジ処理部１０３内に記憶されているエッジ集合から抽出する。図１５（ｃ）のように起点Ａ（ｍ２３）の８近傍に接続および接触、あるいは、接続または接触している画素はｍ１４とｍ２４である。このように起点に接続および接触、あるいは、接続または接触している画素が複数ある場合、探索部１２１は次の探索画素をランダムに選択する。また、図１５（ｄ）のように、探索途中で探索先に２つ以上の接続および接触、あるいは、接続または接触している黒画素がある場合、１つ前の画素からの距離が長い方を選択する。具体的には、探索部１２１は、起点Ａとしてｍ２３から探索開始し、次にランダムに選択したｍ２４に進む。次に、探索部１２１は、ｍ２４に接続および接触、あるいは、接続または接触している黒画素ｍ２５とｍ３５の内、ｍ２４の１つ前の画素ｍ２３から距離の長い方の画素であるｍ３５に進む。
【００４４】
このように、探索部１２１は、起点Ａ（ｍ２３）から、ｍ２４、次にｍ３５のように探索を続け、所定回数の探索、例えば７回探索を行う。７回の探索途中で接続および接触、あるいは、接続または接触している画素が存在しなくなった場合、そのルートの探索は打ち切り、途中で次の探索画素をランダムに選択した画素に戻り探索を行う。
同様に、図１５（ｅ）のように、探索部１２１は、起点Ｂ（ｍ３１）からの探索を行う。なお、探索の順番は、起点Ａまたは起点Ｂのどちらを先に行っても良い。
【００４５】
次に、特徴点が分岐点の場合の探索手順について図１６を用いて説明する。なお、図１６の各画素については、図１５（ａ）と同一のｍ１１〜ｍ５５の位置番号を用いて説明を行う。連結点の探索手順との違いは、特徴点の８近傍に３つの黒画素が存在していることである。探索部１２１は、特徴点の８近傍にある３つの黒画素の中からランダムに２つの画素を選択して、起点Ａ、起点Ｂとする。図１６（ａ）の例では、ｍ２３を起点Ａに、ｍ３１を起点Ｂに選択する。以下、図１６（ｂ）のように、起点Ａおよび起点Ｂからの探索は、連結点の場合と同様に行う。
【００４６】
図１７（ａ）は、特徴点が連結点の探索結果の一例を示す図である。図１７（ａ）のように、特徴点（ｍ２２）の８近傍にある黒画素のｍ１３を起点Ａとして探索を行った結果、探索終点Ａ（ｍ１９（ｘ１，ｙ９））に到達し、他方、特徴点（ｍ２２）の８近傍にある黒画素のｍ３２を起点Ｂとして探索を行った結果、探索終点Ｂ（ｍ９３（ｘ９，ｙ３））に到達する。
探索部１２１は、特徴点の８近傍にある黒画素を起点に探索を行った結果、予め定めた回数の探索を行い２つの起点に対する探索終点に到達した場合、参照した特徴点の座標と２つの探索終点の座標をベクトル生成部１２２に出力する。
また、特徴点の８近傍にある黒画素を起点に探索を行った結果、予め定めた回数の探索を行わないうちに探索終了点が探索できない場合、すなわち、その先に画素がない場合、探索部１２１は、参照した特徴点の座標と、探索した結果、探索終点が存在しなかった情報を頂点候補判定部１２４に出力する。
以上のようにして、探索部１２１は、特徴点の８近傍にある黒画素に接続および接触、あるいは、接続または接触している黒画素の探索を行う。
【００４７】
[頂点抽出手法および頂点推定手法の説明]
次に、図形形状認識部（ａ，ｂ，ｃ・・・）内の頂点抽出部１３１が行う頂点抽出手法と、頂点推定部１３２が行う頂点推定手法について、図１８〜図２３を用いて説明する。
【００４８】
まず、頂点抽出部１３１は、頂点候補集合記憶部１２７から未参照の１つの頂点候補集合（Ａ（ｘ０，ｙ０））を参照する。次に、頂点抽出部１３１は、参照した頂点候補集合のなす角θと、２本のベクトルと、頂点候補の座標、およびＮを読み出す。頂点抽出部１３１と頂点推定部１３２は、読み出したＮの値に応じて以下のように頂点抽出と頂点推定を行う。
【００４９】
[正Ｎ角形：Ｎが５以上の奇数]
Ｎが５以上の奇数の場合について、図１８と図１９を用いて説明する。図１８は、正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点抽出手法を説明する図である。図１９は、正Ｎ（Ｎは５以上の奇数の整数）角形の場合の頂点推定手法を説明する図である。説明を簡略化にするために、Ｎ＝５の例について説明する。
頂点抽出部１３１は、Ｎ＝５、すなわち正五角形のため、正五角形の内角θ＝１０８度を算出する。または、頂点抽出部１３１が頂点候補集合記憶部１２７から参照した頂点候補のなす角θを用いる。
次に、頂点抽出部１３１は、以下の２本のベクトルを読み出す。
【００５０】
【数１】
【００５１】
【数２】
【００５２】
そして、頂点抽出部１３１は、読み出した２本のベクトルと、算出した内角θまたは参照したなす角θ＝１０８度を用いて、次式（２）と式（３）を用いて各ベクトルａ２、ｂ２、ａ３、ｂ３を算出する。
【００５３】
【数３】
【００５４】
【数４】
【００５５】
式（２）と式（３）においてｉ＝２，３であり、θ２＝（θ＋π）／２、θ３＝―（θ＋π）／２である。
次に、頂点抽出部１３１は、式（２）と式（３）により求めた以下に示す各ベクトルの組合せが、参照した頂点候補の特徴点Ａからの距離ｄｉが次式（４）を満たす頂点候補を頂点候補集合記憶部１２７から読み出して抽出する。
【００５６】
【数５】
【００５７】
【数６】
【００５８】
ｄ−α≦ｄｉ≦ｄ＋α・・・式（４）
【００５９】
なお、式（４）において、αは頂点候補集合における各２本のベクトルのなす角の誤差角度であり、また、ｄは正五角形の対角線の距離である。
すなわち、図１８において、頂点抽出部１３１は、参照した頂点候補Ａのベクトルａとベクトルｂ、なす角θ＝１０８と対になる２つの頂点候補Ｃと頂点候補Ｄを頂点候補集合記憶部１２７から抽出する。
まず、頂点抽出部１３１は、頂点候補Ｃ（ｘ２，ｙ２）、距離ｄ２、および以下の２本のベクトルを頂点候補集合記憶部１２７から読み出して抽出する。
【００６０】
【数７】
【００６１】
次に、頂点抽出部１３１は、頂点候補Ｄ（ｘ３，ｙ３）、距離ｄ３、および以下の２本のベクトルを頂点候補集合記憶部１２７から読み出して抽出する。
【００６２】
【数８】
【００６３】
上記の条件を満たす２つの頂点候補ＣとＤが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａを頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した２つの頂点候補集合（頂点ＣとＤ）を頂点推定部１３２に出力する。
上記の条件を満たす２つの頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点ではないと判定する。
【００６４】
なお、正五角形について説明したが、Ｎが５以上の奇数の正Ｎ角形の場合についても同様に、前述した頂点抽出手法を用いて２つの頂点候補を抽出する。その場合、正Ｎ角形の場合、内角θ＝３６０度／Ｎ、ｉ＝２，３を用いて式（２）と式（３）により同様にベクトルを算出する。また、式（４）において、ｄは正Ｎ角形の対角線のうち一番長い対角線の距離である。
【００６５】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｃと頂点Ｄの頂点候補集合を取り込む。また、頂点推定部１３２は、取り込んだ頂点Ａと頂点Ｃと頂点Ｄの頂点候補集合を用いて、残りの頂点（ＢとＥ）を推定する。正五角形の場合について、図１９を用いて頂点推定手法を説明する。
まず、頂点推定部１３２は、頂点Ａ（ｘ０，ｙ０）と頂点Ｃ（ｘ２，ｙ２）または頂点Ｄ（ｘ３，ｙ３）の各座標を用いて、頂点Ａと頂点Ｃと頂点Ｄを含む正五角形の外接円の半径ｒを算出する。図１９において、線分ＡＣの長さをｓとし、正五角形の中点をＯ（ｘｃ，ｙｃ）、角度∠ＯＡＣをβ、角度∠ＡＯＥとγとした場合、γ＝∠ＡＯＥ＝２π／Ｎより、∠ＡＯＣ＝π−π／Ｎであるため、β＝∠ＯＡＣ＝π／２Ｎとなる。したがって外接円の半径ｒは、次式（５）により算出できる。
【００６６】
ｒ＝ｓ／（２×ｃｏｓβ）・・・（５）
【００６７】
次に、頂点Ａのベクトルａの単位ベクトルを以下のように置くと、正五角形の中点Ｏ（ｘｃ，ｙｃ）は、次式（６）により算出できる。
【００６８】
【数９】
【００６９】
【数１０】
【００７０】
次に、頂点推定部１３２は、算出した正五角形の中点Ｏ（ｘｃ，ｙｃ）から頂点ＡのベクトルＯＡを回転角度γずつ回転することで、図形の残りの頂点Ｂと頂点Ｅを次式（７）および次式（８）を用いて推定する。
【００７１】
【数１１】
【００７２】
【数１２】
【００７３】
式（８）において、ｉは１以上でＮ−１以下の整数（ｉ＝（Ｎ−１）／２とｉ＝（（Ｎ−１）／２）＋１は除く）である。
【００７４】
また、頂点抽出部１３１が参照した頂点候補と抽出した２つの頂点候補と、頂点推定部１３２が推定した頂点とを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００７５】
[正Ｎ角形：Ｎが６以上の偶数]
次に、Ｎが６以上の偶数の場合について、図２０と図２１を用いて説明する。図２０は、正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点抽出手法を説明する図である。図２１は、正Ｎ（Ｎは６以上の偶数の整数）角形の場合の頂点推定手法を説明する図である。説明を簡単にするために、Ｎ＝６の例について説明する。
頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００７６】
【数１３】
【００７７】
【数１４】
【００７８】
次に、図２０のように、読み出した頂点候補Ａの２本のベクトルとそれぞれ符号が逆の以下の２本のベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｄを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００７９】
【数１５】
【００８０】
【数１６】
【００８１】
上記の条件を満たす頂点候補Ｄが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｄ）の頂点候補集合を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【００８２】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｄの頂点候補集合を取り込む。また、頂点推定部１３２は、取り込んだ頂点Ａと頂点Ｄにより構成される正六角形の中点Ｏ（ｘｃ，ｙｃ）を、次式（９）を用いて算出する。
【００８３】
【数１７】
【００８４】
次に、頂点推定部１３２は、算出した中点Ｏ（ｘｃ，ｙｃ）から頂点Ａ（ｘ０，ｙ０）へのベクトルＯＡを回転した値を、次式（１０）で算出し、残りの頂点Ｂ，Ｃ，Ｅ，Ｆを抽出する。すなわち、正六角形なので、２π／Ｎ＝２π／６＝６０度ずつベクトルＯＡを回転することで順次、残りの頂点Ｂ，Ｃ，Ｅ，Ｆを抽出する。
【００８５】
【数１８】
【００８６】
式（１０）において、ｉは１以上でＮ−１以下の整数（ｉ＝Ｎ／２は除く）である。
以上のように、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｄと、頂点推定部１３２が推定した頂点Ｂ，Ｃ，Ｅ，Ｆを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００８７】
[正Ｎ角形：Ｎが３の場合]
正三角形の場合について、図２２を用いて説明する。図２２は、正三角形の場合の頂点抽出手法および頂点推定手法を説明する図である。頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００８８】
【数１９】
【００８９】
【数２０】
【００９０】
次に、図２２（ａ）と図２２（ｂ）のように、頂点抽出部１３１は、読み出した頂点候補Ａの２本のベクトルと、次式（１１）と次式（１２）を用いて頂点Ｂのベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｂを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００９１】
【数２１】
【００９２】
【数２２】
【００９３】
上記の条件を満たす頂点候補Ｂが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｂ）を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【００９４】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｂの各頂点候補集合を受け取る。また、頂点推定部１３２は、受け取った頂点Ａと頂点Ｂの頂点候補集合から各ベクトルを読み出す。また、頂点推定部１３２は、読み出したベクトルを用いて、頂点Ａと頂点Ｂの互いに向かい合わないベクトル、すなわちベクトルｂとベクトルａ１の交点を算出して、算出した頂点を残りの頂点Ｃ（ｘ２，ｙ２）として推定する。
また、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｂと、頂点推定部１３２が推定した頂点Ｃを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に書き込んで記憶させる。
【００９５】
[正Ｎ角形：Ｎが４の場合]
正方形の場合について、図２３を用いて説明する。図２３は、正方形の場合の頂点抽出手法および頂点推定手法を説明する図である。頂点抽出部１３１は、頂点候補Ａの以下の２本のベクトルを読み出す。
【００９６】
【数２３】
【００９７】
【数２４】
【００９８】
次に、図２２（ａ）と図２２（ｂ）のように、頂点抽出部１３１は、読み出した頂点候補Ａの２本のベクトルとそれぞれ符号が逆のベクトルを有し、かつ参照した頂点候補Ａから予め定められた一定以上の距離ｄにある頂点候補Ｂを頂点候補集合記憶部１２７から読み出して抽出する。予め定められた一定以上の距離ｄは、例えば、検出したい図形が図２４のようなマーカーで、図形の対角線の大きさが予め分かっている場合、マーカーの大きさに応じて設定する。
【００９９】
【数２５】
【０１００】
【数２６】
【０１０１】
上記の条件を満たす頂点候補Ｂが頂点候補集合記憶部１２７から抽出できた場合、頂点抽出部１３１は、参照した頂点候補Ａは頂点であると判定する。また、頂点抽出部１３１は、参照した頂点候補集合（頂点Ａ）と、抽出した頂点候補集合（頂点Ｂ）を頂点推定部１３２に出力する。
上記の条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は、参照した頂点候補は頂点ではないと判定する。
【０１０２】
次に、頂点推定部１３２は、頂点抽出部１３１から頂点Ａと頂点Ｂの各頂点候補集合を受け取る。また、頂点推定部１３２は、受け取った頂点Ａと頂点Ｂの頂点候補集合から各ベクトルを読み出す。また、頂点推定部１３２は、読み出したベクトルを用いて、頂点Ａと頂点Ｂの互いに向かい合わないベクトル、すなわちベクトルｂとベクトル−aの交点を算出して、算出した頂点を残りの頂点Ｃ（ｘ２，ｙ２）として推定し、同様に、ベクトルａとベクトル−bの交点を算出して、算出した頂点を残りの頂点Ｄ（ｘ４，ｙ４）として推定する。
また、頂点抽出部１３１が参照した頂点候補Ａと抽出した頂点候補Ｂと、頂点推定部１３２が推定した頂点Ｃと頂点Ｄを頂点集合として、頂点推定部１３２が頂点集合記憶部１３７に記憶する。
【０１０３】
[図形形状認識処理の手順]
次に、図形形状認識手順について、図８〜図１１のフローチャート、図１の構成図を用いて説明する。図８は、図形形状認識装置１０全体の図形形状認識手順を示すフローチャートである。以下、このフローチャートに沿って説明する。
【０１０４】
まず、カメラ１１が撮像した画像（濃淡画像）を画像データ取り込み部１０１が取得する（ステップＳ１）。画像データ取り込み部１０１は、取得した画像データを二値化処理部１０２に出力する。
【０１０５】
二値化処理部１０２は、画像データ取り込み部１０１が出力する画像データを取り込む。また、二値化部１０２は、取り込んだ画像データを、閾値を用いて二値化する（ステップＳ２）。また、二値化処理部１０２は、二値化した画像データをエッジ処理部１０３に出力する。なお、二値化における閾値の設定方法は、例えば大津の方法を用いて行う。
【０１０６】
エッジ処理部１０３は、二値化処理部１０２が出力する画像データを取り込む。また、エッジ処理部１０３は、取り込んだ画像データに対して、ラプラシアンフィルタ等を用いた一般的な手法によりエッジ処理を行う（ステップＳ３）。また、エッジ処理部１０３は、エッジ処理した画像情報（各黒画素の座標）をエッジ集合としてエッジ処理部１０３に書き込んで記憶させる。
【０１０７】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理終了後、エッジ処理部１０３が記憶するエッジ集合の中から未参照の画素を順次参照して、参照した画素を特徴点か否かの判定を行う（ステップＳ４）。
【０１０８】
次に、特徴点判定処理手順について、図９のフローチャートを用いて説明する。特徴点判定処理部１１０ａ内の連結点・分岐点判定部１１１は、エッジ処理部１０３内に記憶されているエッジ集合の中から未参照の１画素を参照する（ステップＳ１０１）。
【０１０９】
次に、連結点・分岐点判定部１１１は、参照した画素を注目点とし、エッジ処理部１０３に記憶されているエッジ集合を参照して注目点の８近傍の画素に２点以上の黒画素が存在しているか否かを判定する。次に、注目点の８近傍に２点以上の黒画素が存在していると判定した場合、連結点・分岐点判定部１１１は、注目点と８近傍に存在する黒画素との接続および接触、あるいは、接続または接触の構成パターンが連結点であるか、分岐点であるかを判定する。また、ノイズ除去部１１２は、連結点・分岐点判定部１１１が参照した注目点、および注目点の８近傍に存在する２つの黒画素の接続および接触、あるいは、接続または接触の構成パターンのうち、ノイズの構成パターンを除去する。また、特徴点判定部１１３は、連結点・分岐点判定部１１１の判定結果と、ノイズ除去部１１２の判定結果を用いて、参照した画素が線分の交点である特徴点であるか否かを判定する（ステップＳ１０２）。
ステップＳ１０２で参照した画素が特徴点であると判定した場合（ステップＳ１０２；Ｙｅｓ）、特徴点集合生成部１１４は参照した画素（注目点）とその画素を特徴点として特徴付ける情報（画素の座標と、その画素の８近傍にある黒画素の座標と、その画素と８近傍にある黒画素との構成パターン）を特徴点集合として生成し、生成した特徴点集合を特徴点集合記憶部１１７に書き込んで記憶させる（ステップＳ１０３）。
ステップＳ１０２で参照した画素が特徴点でない判定した場合（ステップＳ１０２；Ｎｏ）、参照した画素についての特徴点判定処理を終了する。
【０１１０】
特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、エッジ処理部１０３に記憶されている全てのエッジ集合に含まれる画素に対してステップＳ４の特徴点判定処理を行う。また、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、特徴点判定処理を並列に処理する。すなわち、特徴点判定処理部１１０ａが、エッジ集合から画素１を参照して特徴点判定処理を行い、並列して特徴点判定処理部１１０ｂは、特徴点判定処理部１１０ａが参照していない画素を参照して特徴点判定処理を行う。また、特徴点判定処理が先に終了した特徴点判定処理部１１０ａまたは特徴点判定処理部１１０ｂは、未参照の画素を順次参照して特徴点判定を行う。
以上の処理により、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）は、全てのエッジ集合の画素に特徴点判定処処理が終了した後、特徴点集合の生成が終了したことを頂点候補判定処理に出力する（ステップＳ５）。
【０１１１】
図８に戻り、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）から全ての画素についての特徴点集合の生成が終了した情報を取り込んだ後、特徴点記憶部１１７が記憶している特徴点集合の中から未参照の１つの特徴点を順次参照して、参照した特徴点に対して頂点候補判定処理を行う（ステップＳ６）。
【０１１２】
次に、頂点候補判定処理手順について、図１０のフローチャートを用いて説明する。頂点候補判定処理部１２０ａ内の探索部１２１は、特徴点集合記憶部１１７が記憶している特徴点集合から未参照の１つの特徴点集合を参照する（ステップＳ２０１）。
【０１１３】
次に、探索部１２１は、参照した特徴点集合に基づいて、前述した探索手順により、特徴点に接続および接触、あるいは、接続または接触している画素の探索を行う（ステップＳ２０２）。
探索部１２１は、特徴点の８近傍にある黒画素を起点に探索を行った結果、所定回数の探索を行い２つの起点に対する探索終点に到達した場合（ステップＳ２０２；Ｙｅｓ）、参照した特徴点の座標と２つの探索終点の座標をベクトル生成部１２２に出力する。
また、特徴点の８近傍にある黒画素を起点に探索を行った結果、所定回数の探索を行わないうちに探索終点に到達した場合、すなわち、その先に画素がない場合、探索部１２１は、参照した特徴点の座標と、探索した結果、探索終点が存在しなかった情報を頂点候補判定部１２４に出力する。頂点候補判定部１２４は、参照した特徴点は探索終了点が存在しないと判定し（ステップＳ２０２；Ｎｏ）、参照した特徴点集合の頂点候補判定処理を終了する。
【０１１４】
次に、ベクトル生成部１２２は、探索部１２１から特徴点の座標と２つの探索終点の座標を取り込む。ベクトル生成部１２２は、取り込んだ特徴点の座標と２つの探索終点の座標を用いて、前述したベクトル生成手法により２本のベクトルを生成する（ステップＳ２０３）。また、ベクトル生成部１２２は、特徴点の座標と生成した２本のベクトルを頂点角度判定部１２３に出力する。
【０１１５】
次に、頂点角度判定部１２３は、ベクトル生成部１２２が生成した２本のベクトルと特徴点の座標とを取り込む。また、頂点角度判定部１２３は、ベクトル生成部１２２が生成した２本のベクトルのなす角θを算出する。また、頂点角度判定部１２３は、算出したなす角θについて、次式（１）を満たすＮ（Ｎは正の整数）を算出する。
【０１１６】
θ＝（（（Ｎ−２）×π）／Ｎ）±α・・・（１）
【０１１７】
また、頂点角度判定部１２３は、なす角θが６０度以下または１８０度以上の場合は、（１）式を満たさないのでＮＧと判定し、判定結果を頂点候補判定部１２４に出力する。また、頂点角度判定部１２３は、２本のベクトルのなす角θについて式（１）を満たすＮが算出できた場合、ＯＫと判定し、特徴点の座標と、２本のベクトルと、２本のベクトルのなす角θ、および頂点角度判定を頂点候補判定部１２４に出力する。
また、頂点候補判定部１２４は、頂点角度判定部１２３から特徴点の座標と、２本のベクトルと、２本のベクトルのなす角、および頂点角度判定を取り込み、取り込んだ頂点角度判定がＯＫの場合（ステップＳ２０４；Ｙｅｓ）、その特徴点を頂点候補として判定し、特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを頂点候補集合生成部１２５に出力する。
また、頂点候補判定部１２４は、受け取った頂点角度判定がＮＧの場合、頂点候補ではないと判定し（ステップＳ２０４；Ｎｏ）、参照した特徴点集合の頂点候補判定処理を終了する。
【０１１８】
次に、頂点候補集合生成部１２５は、頂点候補判定部１２４から、特徴点を頂点候補として特徴付ける情報として、特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを取り込む。また、頂点候補集合生成部１２５は、取り込んだ特徴点の座標、２本のベクトルおよび２本のベクトルのなす角θを関連付けて頂点候補集合を生成して、頂点候補集合記憶部１２７に書き込んで記憶させる（ステップＳ２０５）。
【０１１９】
頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、特徴点集合記憶部１１７が記憶する全ての特徴点集合に含まれる特徴点に対してステップＳ６の頂点候補判定処理を行う。また、複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理を並列に処理する。すなわち、頂点候補判定処理部１２０ａが、特徴点集合から特徴点１を参照して頂点候補判定処理を行い、並列して頂点候補判定処理部１２０ｂは、頂点候補判定処理部１２０ａが参照していない特徴点２を参照して頂点候補判定処理を行う。また、頂点候補判定処理が先に終了した頂点候補判定処理部１２０ａまたは頂点候補判定処理部１２０ｂは、未参照の特徴点を順次参照して頂点候補判定を行う。
以上の処理により、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）は、全ての特徴点集合の頂点候補判定処処理が終了した後、頂点候補集合の生成が終了した情報を図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）に出力する（ステップＳ７）。
【０１２０】
次に、図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）から全ての特徴点についての頂点集合の生成が終了した情報を取り込んだ後、頂点候補集合記憶部１２７から未参照の１つの頂点候補集合を順次参照して頂点処理を行う（ステップＳ８）。
【０１２１】
次に、頂点処理手順について、図１１のフローチャートを用いて説明する。図形形状認識処理部１３０ａ内の頂点抽出部１３１は、頂点候補集合記憶部１２７が記憶している頂点候補集合から未参照の１つの頂点候補集合を参照する（ステップＳ３０１）。
【０１２２】
次に、頂点抽出部１３１は、参照した頂点候補集合を用いて、その頂点候補を含む図形の他の頂点候補を、前述した頂点抽出手法により頂点候補集合記憶部１２７が記憶している頂点候補集合から抽出する（ステップＳ３０２）。抽出する頂点候補数は、参照した頂点候補集合のＮに基づき、Ｎ＝３または４以上の偶数の場合は１つの頂点候補を抽出し、Ｎ＝５以上の奇数の場合は２つの頂点候補を算出する。また、頂点候補集合記憶部１２７から前述した各条件に合致する頂点候補が抽出できた場合、頂点抽出部１３１は、参照頂点候補を頂点であると判定する（ステップＳ３０２；Ｙｅｓ）。参照頂点候補を頂点と判定した場合、頂点抽出部１３１は、参照頂点候補集合と、抽出した頂点候補集合を頂点推定部１３２に出力する。
前述した各条件を満たす頂点候補が頂点候補集合記憶部１２７から抽出できない場合、頂点抽出部１３１は参照した頂点候補を頂点ではないと判定し（ステップＳ３０２；Ｎｏ）、参照した頂点候補集合についての図形形状認識処理を終了する。
【０１２３】
次に、頂点推定部１３２は、頂点抽出部１３１が参照した頂点候補集合（以下、参照頂点候補集合）と抽出した頂点候補集合（以下、抽出頂点候補集合）を取り込む。また、頂点推定部１３２は、取り込んだ参照頂点候補集合と抽出頂点候補集合を用いて、これらの頂点候補を頂点として含む図形の他の頂点を前述した頂点推定手法により算出し、算出した頂点を残りの頂点として推定する。頂点の推定は、Ｎ＝３の場合は１点、Ｎ＝４，５の場合は２点、Ｎ＝６の場合は４点について行う。
また、頂点推定部１３２は、参照頂点候補集合と抽出頂点候補集合と、頂点推定部１３２が推定した頂点の座標とベクトルとを、頂点集合として頂点集合記憶部１３７に書き込んで記憶させる（ステップＳ３０４）。また、頂点推定部１３２は、頂点処理が終了した情報を図形形状認識部１３３に出力する。
【０１２４】
図８に戻り、図形形状認識部１３３は、頂点推定部１３２から頂点処理が終了した情報を取り込んだ後、頂点集合記憶部１３７に記憶されている未参照の頂点集合を順次参照する。また、図形形状認識部１３３は、参照した頂点集合に基づき、その頂点が構成する図形形状を認識し、認識した図形形状、およびその図形を構成している各頂点の座標等を画像出力部１４０に出力する（ステップＳ９）。
【０１２５】
図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点候補集合記憶部１２７が記憶する全ての頂点候補集合に含まれる頂点候補に対してステップＳ８の頂点処理を行う。また、複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）は、頂点処理を並列に処理する。すなわち、図形形状認識処理部１３０ａが、頂点候補集合から頂点候補１を参照して頂点処理を行い、並列して図形形状認識処理部１３０ｂは、頂点候補判定処理部１２０ａが参照していない頂点候補２を参照して頂点処理を行う。また、頂点処理が先に終了した図形形状認識処理部１２０ａまたは図形形状認識処理部１３０ｂは、未参照の頂点候補を順次参照して頂点判定処理を行う。
【０１２６】
画像出力部１４０は、図形形状認識部１３３が認識した図形形状およびその図形を構成している各頂点の座標等の図形形状認識結果を取り込み、取り込んだ図形形状認識結果を画像表示装置１３に出力する（ステップＳ１０）。また、画像表示装置１３は、画像出力部１４０が出力した図形形状認識結果を表示する。
以上により、図形形状認識処理を終了する。
【０１２７】
以上のように、本実施形態によれば、撮像した画像における線分の交点である特徴点の検出を、特徴点判定処理の並列処理が行いやすい画素ごとに行うようにしたので、図形形状認識処理を並列処理することで高速化を実現することができる。また、図形形状認識において、従来技術のようにラベリング処理に替えて、図形を構成している頂点を抽出し、抽出した頂点を用いて図形の他の頂点や図形の形状を推定するようにしたので、さらに図形形状における認識処理の高速化を実現することができる。また、本実施形態の図形認識処理は、ラベリング処理のように取得した画面全体に処理を行う場合と比較し、各処理を並列して行いやすい単位に設定してあるので、複数の特徴点判定処理、または複数の頂点候補判定処理、または複数の図形形状認識処理において、各処理の計算量の均一化が容易なため、並列処理を容易にすることができる。
【０１２８】
また、本実施形態では、エッジ処理部１０３は、二値化処理部１０２で二値化された入力画像を用いてエッジ処理を行う例について説明したが、画像データ取り込み部１０１が取り込んだ画像データである濃淡画像に直接エッジ処理を行うようにしても良い。
【０１２９】
また、本実施形態では、頂点角度判定部１２３で全てのＮについて式（１）を満たすか判定する例について説明したが、認識したい図形の形状が予め分かっている場合等、用途に応じて、一定の範囲のＮ、例えば３≦Ｎ≦１０のみを頂点候補として判定しても良い。
【０１３０】
また、本実施形態では、図形の形状を、まず頂点候補判定処理部が１つの頂点候補を抽出し、次に図形形状認識処理部が残りの頂点を抽出し、次にこれらの抽出した頂点候補を用いて残りの頂点を推定して図形形状を認識する例について説明したが、残りの頂点を推定で算出するのではなく、図形形状認識処理部が残りの頂点を抽出するようにしても良い。この場合においても、図形形状の認識において図形の頂点のみを抽出しているので、ラベリングを行う手法と比較して高速に図形形状を認識することができる。
【０１３１】
また、本実施形態では、図形の形状を、まず頂点候補判定処理部が１つの頂点候補を抽出し、次に図形形状認識処理部が残りの頂点を抽出し、次にこれらの抽出した頂点候補を用いて残りの頂点を推定して図形形状を認識する例について説明したが、残りの頂点を推定により算出した後、頂点推定部１３２は推定した頂点と、頂点候補集合記憶部１２７が記憶している頂点候補集合を比較して、が頂点候補集合に実在しているか否かを判定する用ようにしても良い。これにより、さらに図形形状の認識精度を向上することができる。
【０１３２】
また、本実施形態では、カメラ１１が撮像した画像データから図形形状を認識する例を説明したが、予め取得した画像データから図形形状認識を行っても良い。また、本実施形態では、画像データ取り込み部１０１が取り込んだ画像を二値化処理部１０２で二値化処理した後にエッジ処理する例を説明したが、取り込んだ画像データに直接エッジ処理を行っても良い。
【０１３３】
なお、実施形態の図１の各部の機能を実現するためのプログラムをコンピューター読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピューターシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピューターシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピューターシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピューター読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピューターシステムに内蔵されるハードディスク等、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ） Ｉ／Ｆを介して接続されるＵＳＢメモリー等の記憶装置のことをいう。さらに「コンピューター読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピューターシステム内部の揮発性メモリーのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピューターシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１３４】
また、本実施形態では、特徴点判定処理と、頂点候補判定処理と、頂点処理（図形認識処理）とを、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）で並列処理する例について説明したが、並列処理は図示しない複数のＣＰＵで行うことも可能である。この場合、例えば、ＣＰＵ１が特徴点判定処理部１１０ａの処理を行い、ＣＰＵ２が特徴点判定処理部１１０ｂの処理を行う。または、１つのＣＰＵで特徴点判定処理部１１０ａと特徴点判定処理部１１０ｂとを並列処理するようにしても良い。
また、特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）の少なくとも１つが複数の処理部を備えていて、複数の特徴点判定処理部を並列処理、または複数の頂点候補判定処理部を並列処理、または複数の図形形状認識処理部を並列処理するようにしても良い。
【０１３５】
さらにまた、本実施形態では、特徴点判定処理と、頂点候補判定処理と、頂点処理（図形認識処理）とを、複数の特徴点判定処理部１１０（ａ，ｂ，ｃ・・・）と複数の頂点候補判定処理部１２０（ａ，ｂ，ｃ・・・）と複数の図形形状認識処理部１３０（ａ，ｂ，ｃ・・・）で並列処理する例について説明したが、各処理部（特徴点判定処理部１１０と頂点候補判定処理部１２０と複数の図形形状認識処理部１３０）はそれぞれ１つずつで並列処理を行わなくても良い。この場合においても、本実施形態で説明した特徴点判定処理や頂点候補判定処理、および頂点処理（図形認識処理）を用いれば、従来のラベリングを用いた図形形状認識装置より高速な図形形状の認識を行うことができる。
【符号の説明】
【０１３６】
１０・・・図形形状認識装置
１０１・・・画像データ取り込み部
１０２・・・二値化処理部
１０３・・・エッジ処理部
１１０（ａ，ｂ，ｃ・・・）・・・特徴点判定処理部
１１７・・・特徴点集合記憶部
１２０（ａ，ｂ，ｃ・・・）・・・頂点候補判定処理部
１２７・・・頂点候補記憶部
１３０（ａ，ｂ，ｃ・・・）・・・図形形状認識処理部
１３７・・・頂点集合記憶部
１４０・・・画像出力部
１１・・・カメラ
１３・・・画像表示部
【特許請求の範囲】
【請求項１】
エッジ処理した入力画像の全ての画素を１画素ずつ参照し、線分の交点である特徴点を全て検出する特徴点判定処理部と、
前記特徴点判定部が検出した全ての前記特徴点を１つずつ参照し、全ての頂点候補を検出する頂点候補判定処理部と、
前記頂点候補判定処理部が検出した頂点候補を１つずつ参照し、参照した前記頂点候補に基づき当該頂点候補を含み図形を構成する他の頂点候補を検出し、検出した前記頂点候補に基づいて図形形状を認識する図形形状認識処理部と、
を備えることを特徴とする図形形状認識装置。
【請求項２】
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理部と、
前記特徴点判定部が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判定処理部と、
前記頂点候補判定部が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理部と、
を備えることを特徴とする図形形状認識装置。
【請求項３】
前記特徴点判定処理部は、
参照した前記画素の八近傍における隣接画素同士の接続および接触、あるいは、接続または接触の構成に基づいて構成パターンを検出し、検出した構成パターンに基づいて前記画素が特徴点か否かを判定する
ことを特徴とする請求項１または請求項２に記載の図形形状認識装置。
【請求項４】
前記頂点候補判定処理部は、
参照した特徴点を特徴付ける情報を用いて前記特徴点に隣接している画素を順次探索し、探索した結果に基づき前記特徴点を始点とし探索終了点を終了点とする２本のベクトルを生成し、生成した前記２本のベクトルのなす角を算出し、生成した前記２本のベクトルの各距離と前記なす角を用いて頂点候補か否かを判定する
ことを特徴とする請求項１から請求項３のいずれか１項に記載の図形形状認識装置。
【請求項５】
前記特徴点判定処理部、前記頂点候補判定処理部、前記図形形状認識処理部のうち少なくとも１つの処理部を複数備え、複数の前記特徴点判定処理部が並列処理、または複数の前記頂点候補判定処理部が並列処理、または複数の前記図形形状認識処理部が並列処理する
ことを特徴とする請求項１から請求項４のいずれか１項に図形形状認識装置。
【請求項６】
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、
前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、
前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程と、
を含むことを特徴とする図形形状認識方法。
【請求項７】
コンピューターに、
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、
前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、
前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程と、
を実行させるためのプログラム。
【請求項１】
エッジ処理した入力画像の全ての画素を１画素ずつ参照し、線分の交点である特徴点を全て検出する特徴点判定処理部と、
前記特徴点判定部が検出した全ての前記特徴点を１つずつ参照し、全ての頂点候補を検出する頂点候補判定処理部と、
前記頂点候補判定処理部が検出した頂点候補を１つずつ参照し、参照した前記頂点候補に基づき当該頂点候補を含み図形を構成する他の頂点候補を検出し、検出した前記頂点候補に基づいて図形形状を認識する図形形状認識処理部と、
を備えることを特徴とする図形形状認識装置。
【請求項２】
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理部と、
前記特徴点判定部が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判定処理部と、
前記頂点候補判定部が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理部と、
を備えることを特徴とする図形形状認識装置。
【請求項３】
前記特徴点判定処理部は、
参照した前記画素の八近傍における隣接画素同士の接続および接触、あるいは、接続または接触の構成に基づいて構成パターンを検出し、検出した構成パターンに基づいて前記画素が特徴点か否かを判定する
ことを特徴とする請求項１または請求項２に記載の図形形状認識装置。
【請求項４】
前記頂点候補判定処理部は、
参照した特徴点を特徴付ける情報を用いて前記特徴点に隣接している画素を順次探索し、探索した結果に基づき前記特徴点を始点とし探索終了点を終了点とする２本のベクトルを生成し、生成した前記２本のベクトルのなす角を算出し、生成した前記２本のベクトルの各距離と前記なす角を用いて頂点候補か否かを判定する
ことを特徴とする請求項１から請求項３のいずれか１項に記載の図形形状認識装置。
【請求項５】
前記特徴点判定処理部、前記頂点候補判定処理部、前記図形形状認識処理部のうち少なくとも１つの処理部を複数備え、複数の前記特徴点判定処理部が並列処理、または複数の前記頂点候補判定処理部が並列処理、または複数の前記図形形状認識処理部が並列処理する
ことを特徴とする請求項１から請求項４のいずれか１項に図形形状認識装置。
【請求項６】
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、
前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、
前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程と、
を含むことを特徴とする図形形状認識方法。
【請求項７】
コンピューターに、
エッジ処理した入力画像に含まれる未参照の画素を未参照の画素がなくなるまで参照して、参照した前記画素が線分の交点である特徴点か否かを判定し、特徴点と判定した前記画素を特徴点として特徴付ける情報に基づいて特徴点集合を生成する特徴点判定処理工程と、
前記特徴点判定処理工程が生成した前記特徴点集合から、未参照の前記特徴点を未参照の特徴点がなくなるまで参照して、参照した特徴点が頂点候補か否かを判定し、頂点候補と判定した前記特徴点を頂点候補として特徴付ける情報に基づいて頂点候補集合を生成する頂点候補判処理工程と、
前記頂点候補判定処理工程が生成した前記頂点候補集合の中から、未参照の前記頂点候補を未参照の頂点候補がなくなるまで参照し、参照した前記頂点候補が頂点か否かを判定し、頂点と判定した前記頂点候補とともに図形を構成する他の頂点候補を前記頂点候補集合の中から抽出し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補を用いて、図形を構成する他の頂点を推定し、頂点と判定した前記頂点候補且つ抽出した前記頂点候補且つ推定した前記頂点に基づいて図形形状を認識する図形形状認識処理工程と、
を実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【公開番号】特開２０１１−７６３７４（Ｐ２０１１−７６３７４Ａ）
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願番号】特願２００９−２２７２５１（Ｐ２００９−２２７２５１）
【出願日】平成２１年９月３０日（２００９．９．３０）
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【Ｆターム（参考）】
【公開日】平成２３年４月１４日（２０１１．４．１４）
【国際特許分類】
【出願日】平成２１年９月３０日（２００９．９．３０）
【出願人】（３９７０６５４８０）エヌ・ティ・ティ・コムウェア株式会社 (187)
【Ｆターム（参考）】
[ Back to top ]