(57)【要約】【課題】  画像の輪郭を正しい曲線形状で表現する。【解決手段】  本発明は、輪郭を入力し、非線形平滑化を行い、折れ線近似を行い、曲線区間を作成する。全ての曲線区間について割り当て候補を生成し、全ての割り当て候補の要素について曲線パラメータを推定し、その結果に基づいて全ての割り当て候補の適応度を計算し、全ての曲線区間について隣接区間と重複のない割り当て候補を選択し、図形情報として出力する。【選択図】  図１
2006318397.tif 000002
【特許請求の範囲】
【請求項１】
ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識方法において、
入力された輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を記憶手段に格納する非線形平滑化ステップと、
前記記憶手段から前記平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段に格納する折れ線近似ステップと、
前記記憶手段から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段に格納する曲線区間生成ステップと、
前記記憶手段から前記曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段に格納する割り当て候補生成ステップと、
前記記憶手段から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段に格納する曲線パラメータ推定ステップと、
前記各割り当て候補に対して、前記記憶手段から読み出した前記曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段に格納する適応度計算ステップと、
前記記憶手段に格納されている各曲線区間の割り当て候補の中から、適応度が最大で、かつ、隣接曲線区間との重複のない割り当て候補を選択し、出力する割り当て候補選択ステップと、
を行うことを特徴とする図形認識方法。
【請求項２】
ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識装置であって、
前記輪郭を入力し、記憶手段に格納する輪郭入力手段と、
前記記憶手段に格納されている前記輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を記憶手段に格納する非線形平滑化手段と、
前記記憶手段から前記平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段に格納する折れ線近似手段と、
前記記憶手段から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段に格納する曲線区間生成手段と、
前記記憶手段から前記曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段に格納する割り当て候補生成手段と、
前記記憶手段から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段に格納する曲線パラメータ推定手段と、
前記各割り当て候補に対して、前記記憶手段から読み出した前記曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段に格納する適応度計算手段と、
前記記憶手段に格納されている各曲線区間の割り当て候補の中から、適応度が最大で、かつ、隣接曲線区間との重複のない割り当て候補を選択する割り当て候補選択手段と、
前記記憶手段から隣接曲線区間との重複のない割り当て候補を読み出して、図形情報として出力する図形情報出力手段と、
を有することを特徴とする図形認識装置。
【請求項３】
ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識プログラムであって、
入力された輪郭及び、各処理結果を格納する記憶手段を有するコンピュータに、
前記記憶手段に格納されている輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を該記憶手段に格納する非線形平滑化ステップと、
前記記憶手段から前記平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段に格納する折れ線近似ステップと、
前記記憶手段から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段に格納する曲線区間生成ステップと、
前記記憶手段から前記曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段に格納する割り当て候補生成ステップと、
前記記憶手段から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段に格納する曲線パラメータ推定ステップと、
前記各割り当て候補に対して、前記記憶手段から読み出した前記曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段に格納する適応度計算ステップと、
前記記憶手段に格納されている各曲線区間の割り当て候補の中から、適応度が最大で、かつ、隣接曲線区間との重複のない割り当て候補を選択し、出力する割り当て候補選択ステップと、
を実行させることを特徴とする図形認識プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、図形認識方法及び装置及びプログラムに係り、特に、画像から輪郭を取り出して直線及び楕円弧等の曲線として表現する図形認識方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
従来、画像中の物体の輪郭を直線や曲線として表現するには、輪郭をコーナー（直線と直線、または、直線と曲線との交点）等で分割し、直線上に並んだ区間を直線として検出し、それ以外の区間を曲線として円弧等の当てはめを行っている。
【０００３】
例えば、夾角が極小となる点、即ち、点Ａと点Ｃの間の全てのＢ’，Ｂ”に対して、
【０００４】
【数１】
2006318397.tif 000003
となるような点Ｂをコーナーとして検出する(図２１（ａ）)。さらに、輪郭を一定距離Ｌで分割する(図２１（ｂ）)。コーナーや一定間隔の分割点のうち、夾角がほぼ１８０度の部分を直線区間とする。また、残りの部分でほぼ同間隔、同角度の区間を円弧とする。
【０００５】
上記の例では、直線と円弧のみの検出であるが、直線以外の連続した部分を個別に楕円弧の当てはめを行うことで、直線と楕円弧の検出を行うことができる（例えば、特許文献１参照）。
【特許文献１】特開２００４−１３９２７７
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の方法では、変曲点（楕円の曲がる方向の時計回りから反時計回り、あるいは、反時計回りから時計回りに変わる点）の検出を行っていないため、Ｓ字の曲線を楕円と誤認識する問題がある（図２２（ａ））。
【０００７】
変曲点を検出するためには、夾角の符合が変わる点を検出する必要があるが、ノイズにより輪郭に細かな凹凸があると変曲点を誤検出してしまう。また、細かな凹凸を取り除くために輪郭の平滑化を行うと、コーナーが消失し、角度の小さい折れ線の円弧等と誤認識するという問題がおきる（図２２（ｂ））。
【０００８】
さらに、曲線と直線が滑らかに接する部分は、局所的には曲線の一部と区別がつかないため、滑らかに接続した楕円と線分を一つの楕円と誤認識するという問題がある（図２２（ｃ）)。
【０００９】
本発明は、上記の点に鑑みなされたもので、画像の輪郭を正しい曲線形状で表現するための図形認識方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
図１は、本発明の原理を説明するための図である。
【００１１】
本発明は、ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識方法において、
入力された輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を記憶手段に格納する非線形平滑化ステップ（ステップ１）と、
記憶手段から平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段に格納する折れ線近似ステップ（ステップ２）と、
記憶手段から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段に格納する曲線区間生成ステップ（ステップ３）と、
記憶手段から曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段に格納する割り当て候補生成ステップ（ステップ４）と、
記憶手段から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段に格納する曲線パラメータ推定ステップ（ステップ５）と、
各割り当て候補に対して、記憶手段から読み出した曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段に格納する適応度計算ステップ（ステップ６）と、
記憶手段に格納されている各曲線区間の割り当て候補の中から、適応度が最大で、かつ、隣接曲線区間との重複のない割り当て候補を選択し、出力する割り当て候補選択ステップ（ステップ７）と、を行う。
【００１２】
図２は、本発明の原理構成図である。
【００１３】
本発明は、ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識装置であって、
輪郭を入力し、記憶手段１００に格納する輪郭入力手段１０と、
記憶手段１００に格納されている輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を記憶手段１００に格納する非線形平滑化手段２０と、
記憶手段１００から平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段１００に格納する折れ線近似手段３０と、
記憶手段００から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段１００に格納する曲線区間生成手段４０と、
記憶手段１００から曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段１００に格納する割り当て候補生成手段５０と、
記憶手段００から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段１００に格納する曲線パラメータ推定手段６０と、
各割り当て候補に対して、記憶手段１００から読み出した曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段１００に格納する適応度計算手段７０と、
記憶手段１００に格納されている各曲線区間の割り当て候補の中から、適応度が高く、かつ、隣接曲線区間との重複のない割り当て候補を選択し、記憶手段１００に格納する割り当て候補選択手段８０と、
記憶手段１００から隣接曲線区間との重複のない割り当て候補を読み出して、図形情報として出力する図形情報出力手段９０と、を有する。
【００１４】
本発明は、ファイルやネットワークから入力された輪郭から線分・楕円弧を含む形状特徴を推定するための図形認識プログラムであって、
入力された輪郭及び、各処理結果を格納する記憶手段を有するコンピュータに、
記憶手段に格納されている輪郭のコーナーを残しながら細かな凹凸を取り除くことにより平滑化を行い平滑化された輪郭を該記憶手段に格納する非線形平滑化ステップと、
記憶手段から平滑化された輪郭を読み出して、接線方向が一定の範囲に収まる線素に分割し、該線素を該記憶手段に格納する折れ線近似ステップと、
記憶手段から線素を読み出して、該線素に基づいてコーナーや変曲点を検出し、曲線の可能性のある区間を生成し、生成された曲線区間を該記憶手段に格納する曲線区間生成ステップと、
記憶手段から曲線区間を読み出して、該曲線区間内の線素の数に応じて割り当て候補を生成し、該記憶手段に格納する割り当て候補生成ステップと、
記憶手段から割り当て候補を読み出して、各割り当て候補に対して曲線パラメータの推定と誤差の計算を行い、その結果を該記憶手段に格納する曲線パラメータ推定ステップと、
各割り当て候補に対して、記憶手段から読み出した曲線パラメータの数と誤差から曲線区間に対する当てはまりの度合いである適応度を計算し、該記憶手段に格納する適応度計算ステップと、
記憶手段に格納されている各曲線区間の割り当て候補の中から、適応度が最大で、かつ、隣接曲線区間との重複のない割り当て候補を選択し、出力する割り当て候補選択ステップと、を実行させる。
【発明の効果】
【００１５】
輪郭に細かな凹凸があると、本来一つの線分、あるいは、楕円弧として認識すべき区間を不必要に分割し、正しく図形が認識できない。さらに、区間が細かく分割されてしまうと、パラメータ推定の際に、誤差の影響が大きくなり、元の図形と異なる図形として認識してしまうことがある。
【００１６】
これに対し、本発明では、平滑化処理により凹凸を取り除くので、次段の折れ線近似処理において不必要な区間が生成されるのを防ぎ、さらに、曲線区間生成処理において同一の曲線として割り当てるべき区間を正しく検出できる。このため、パラメータ推定の誤差を少なくすることができる。
【００１７】
また、非線形平滑化処理を行うことで、コーナーを残すので、折れ線を認識できる。
【００１８】
また、曲線区間生成処理において、コーナーと変曲点を区別して検出する、及び、コーナーを検出することにより、折れ線と円弧等との誤認識を防ぐことができる。また、変曲点を検出することにより、Ｓ字の曲線を分割することができる。
【００１９】
さらに、割り当て候補選択処理において、複数の割り当ての中から適応度が高い候補を選ぶことにより、局所的には判断できなかった曲線と直線が滑らかに接する部分を正しく認識できる。
【００２０】
上記から、本発明によれば、ノイズによって輪郭点に凹凸が生じている場合でも、
・角度の小さい折れ線を円弧等と誤認識；
・滑らかに接続した楕円弧と線分を一つの楕円弧と誤認識；
・Ｓ字の曲線を楕円弧と誤認識；
することなく、輪郭を正しい曲線形状で表現することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図３は、本発明の一実施の形態における図形認識装置の構成を示す。
【００２３】
同図に示す図形認識装置は、輪郭入力部１０、非線形平滑化部２０、折れ線近似部３０、曲線区間生成部４０、割り当て候補生成部５０、曲線パラメータ推定部６０、適応度計算部７０、割り当て候補選択部８０、図形情報出力部９０、及び記憶部１００から構成される。
【００２４】
輪郭入力部１０は、ファイルやネットワーク等から輪郭情報ｚｔ＝（ｘｔ，ｙｔ）Ｔ，ｔ＝１，…，Ｌを入力し、入力された順に記憶部１００に格納する。
【００２５】
非線形平滑化部２０は、記憶部１００から輪郭情報を時系列的に読み出して、輪郭のコーナーを残しながら、輪郭の座標から細かな凹凸(ノイズ)を取り除き、平滑化された輪郭を記憶部１００に格納する。
【００２６】
詳しくは、Sequential Monte Carlo法（Filtering and Smoothing for Motion Trajectory of Feature Point Using Non-Gaussian State Space Model, IEICE transaction on Information and Systems, Vol.E84-D, No.6, June 2001, pp.755-759）を用いて、輪郭の座標ｚｔ＝（ｘｔ，ｙｔ）Ｔから、平滑化された座標とその方向成分からなる状態ベクトルｓｔ=(ｘｔ，ｙｔ，ｄｘｔ，ｄｙｔ) Ｔを下記のように推定する。
【００２７】
状態遷移モデル：
ｓｔ＝Ｆｓｔ−１＋ｖｔ                    （２）
ｚｔ＝Ｈｓｔ＋ｗｔ                       （３）
状態遷移行列Ｆ：
【００２８】
【数２】
2006318397.tif 000004
観測行列Ｈ：
【００２９】
【数３】
2006318397.tif 000005
また、ｖｔはシステムノイズ、ｗｔは観測ノイズである。
【００３０】
以下に、非線形平滑化部２０の具体的な動作を示す。
【００３１】
ステップ１０１）  初期化：
ｔ←１
σａとσｂの値を設定する。なお、σａとσｂは、それぞれ座標点データへの忠実度・画像モデルとの一致度を表す閾値である。
【００３２】
状態の候補とその重みｓ０ｉ，ｗ０ｉ，ｉ＝１，…，Ｎを初期化する。
【００３３】
ｓ０ｉ＝（２ｘ１−ｘ２，２ｙ１−ｙ２，ｘ２−ｘ１＋ε，ｙ２−ｙ１＋ε）Ｔ    （６）
【００３４】
【数４】
2006318397.tif 000006
ここで、εは平均０、分散σａ２のガウス乱数である。
【００３５】
ステップ１０２）  サンプリング：
ｓt-1ｉがｗt-1ｉの確率で選択されるように復元抽出し、ｓ’ｔi，ｉ＝１，…，Ｎとする。
【００３６】
ステップ１０３）  状態予測：
ｓｔi＝Ｆｓ’ ｔi＋（０，０，ε，ε）Ｔ        （８）
ここで、εは平均０、分散σａ２のガウス乱数である。
【００３７】
ステップ１０４）  重みの設定：
【００３８】
【数５】
2006318397.tif 000007
ここで、‖・‖は、ベクトルのノルムである。
【００３９】
ステップ１０５）  状態推定：
【００４０】
【数６】
2006318397.tif 000008
ステップ１０６）  終了判定：
ｔ＜Ｎならばｔ←ｔ＋１としてステップ１０２に戻る。
【００４１】
ｔ＝Ｎならば終了し、状態ベクトルｓｔ，ｔ＝１，…，Ｌを取得し、記憶部１００に格納する。
【００４２】
折れ線近似部３０は、記憶部１００から平滑化された輪郭を時系列的に読み出して、接線方向が一定の範囲に収まる線素に分割し、記憶部１００に格納する。
【００４３】
以下に、折れ線近似部３０の詳細な動作を説明する。
【００４４】
入力として、非線形平滑化部２０により記憶部１００に格納された状態ベクトルｓｔ，ｔ＝１，…，Ｌが読み込まれる。
【００４５】
出力は、以下の処理で求められた線素Polyｊ，ｊ＝１，…，Ｍであり、記憶部１００に格納される。
【００４６】
ステップ２０１）  初期化：
ｉ←０、ｊ←１、ｔ←１、Ｄ←φとする。
【００４７】
各線分が同じ方向かどうかを決める閾値△tanの値を設定する。
【００４８】
ステップ２０２）  方向集合Ｄの更新：
【００４９】
【数７】
2006318397.tif 000009
ステップ２０３）  同じ方向かどうかの判定：
【００５０】
【数８】
2006318397.tif 000010
ここで、diamは集合の直径である。
【００５１】
ステップ２０４）  終了判定：
ｔ＜Lならば、t←ｔ＋１として、ステップ２０２に戻る。
【００５２】
ｔ＝ＬならばＭ←ｊとして処理を終了し、線素Polyij,ｉ＝１，…，Ｉｊ，ｊ＝１，…，Ｍが記憶部１００に格納される。
【００５３】
曲線区間生成部４０は、記憶部１００から線素Polyjを読み出して、コーナーや変曲点を検出し、曲線の可能性のある区間を生成する。このとき、変曲点の前後で線素を重複させる。生成された曲線区間を記憶部１００に格納する。
【００５４】
以下に詳細に曲線区間生成部４０の動作を説明する。
【００５５】
入力として、折れ線近似部３０により記憶部１００に格納されている線素Polyj、j＝１，…，Mが読み込まれる。
【００５６】
出力は、以下の処理で求められた曲線区間Ｃｋ，ｋ＝１，…，Ｎが記憶部１００に格納される。
【００５７】
ステップ３０１）  初期化：
ｊ←２，ｋ←１，Ｃ１←Poly１とし、隣り合う線素がコーナーを形成するかどうかを決める閾値△dirの値を設定する。
【００５８】
ステップ３０２）  終了判定：
ｊ＞Ｍならば、Ｎ←ｋとして終了する。曲線区間Ｃｋ，ｋ＝１，…，Ｎを取得し、記憶部１００に格納する。
【００５９】
ステップ３０３）  コーナー検出：
線素Polyｊ−１の終点の接線の方向とPolyｊの始点の接線の方向のずれがθのとき、θ＜△dirならばコーナーとし、コーナーであれば、ｋ←ｋ＋１、Ｃｋ←Polyjｊ←ｊ＋１としてステップ３０２に移行する。コーナーでなければ、Ｃｋ←Polyｊとして、ステップ３０４に移行する。
【００６０】
ここで、始点Poly１ｊ−１と
【００６１】
【数９】
2006318397.tif 000011
との中点（図４（ａ）の黒三角）と
【００６２】
【数１０】
2006318397.tif 000012
（図４（ａ）の黒丸の点）を１：１に外分する点ｐとして、点ｐから
【００６３】
【数１１】
2006318397.tif 000013
への直線をPolyj-1の終点の接線とする。同様に、点ｑから
【００６４】
【数１２】
2006318397.tif 000014
への直線を
【００６５】
【数１３】
2006318397.tif 000015
の始点の接線とする。曲線の一部であればθは小さく（図４（ａ））、コーナーであればθは大きくなる（図４（ｂ））。
【００６６】
ステップ３０４）  変曲点検出：
ｊ＝Ｍならばステップ３０５に移行する。そうでなければ、図５に示すように、曲線が曲がる方向が時計回りか反時計回りかを調べ、異なる方向になった部分を検出する。
【００６７】
すなわち、
【００６８】
【数１４】
2006318397.tif 000016
ここで、“×”は外積である。
【００６９】
ＴｊとＴｊ−１の符合が異なれば変曲点として、ｋ←ｋ＋１、Ｃｋ←Ｃｋ∪Polyj(Polyjは２つの区間で重複する)。
【００７０】
ステップ３０５）  ｊ←ｊ＋１としてステップ３０２へ移行する。
【００７１】
次に、割り当て候補生成部５０について説明する。
【００７２】
割り当て候補生成部５０は、記憶部１００から曲線区間を読み出して、当該曲線区間内の線素の数に応じて割り当て候補を生成し、記憶部１００に格納する。
【００７３】
本実施の形態では、割り当てる対象の曲線を線分と楕円とする。変曲点における前後の区間との重複や、曲線や直線の滑らかな接合を考慮するため、両端の線素を楕円割り当てに含めるか否かで４つの候補を作成する。但し、図６に示すように、線素が１の場合は線分のみ、２の場合は“楕円”か“線分＋線分”とする。ここで、各候補の“＋”で区切られた部分を割り当て要素とする。曲線パラメータの推定と誤差の計算は割り当て要素毎に、適応度の計算は候補毎に行う。
【００７４】
次に、曲線パラメータ推定部６０について説明する。
【００７５】
曲線パラメータ推定部６０は、記憶部１００から割り当て候補を読み出して、各割り当て候補に対して、曲線パラメータの推定と誤差の計算を行い、計算結果を記憶部１００に格納する。
【００７６】
曲線パラメータ推定部６０は、与えられた割り当て要素のモデルパラメータの推定、及び、割り当て誤差の計算を行う。割り当て要素の座標列を｛（ｘｉ，ｙｉ）│ｉ＝１，…，ｎ｝とする。
【００７７】
線分モデル：線分は、
ｙcosθｇ＝ｘsinθｇ＋ρ                            （１３）
の２つのパラメータθｇ，ρで表される、θｇ，ρは次のように計算される。
【００７８】
【数１５】
2006318397.tif 000017
ここで、
【００７９】
【数１６】
2006318397.tif 000018
また、誤差は次のように計算される。
【００８０】
【数１７】
2006318397.tif 000019
楕円モデル：楕円は、図７に示すように、｛ｒａ，ｒｂ，θε，ｐ，ｑ｝の５つのパラメータで表される。まず、座標列から次の連立方程式の解α、β、γ、ζ、ηを求める。
【００８１】
【数１８】
2006318397.tif 000020
ここで、
【００８２】
【数１９】
2006318397.tif 000021
楕円の中心（ｐ，ｑ）は、
【００８３】
【数２０】
2006318397.tif 000022
長径ｒａ、短径ｒｂ，傾きθεは：
【００８４】
【数２１】
2006318397.tif 000023
ここで、
【００８５】
【数２２】
2006318397.tif 000024
また、誤差を以下のように近似計算する。
【００８６】
【数２３】
2006318397.tif 000025
ここで、
【００８７】
【数２４】
2006318397.tif 000026
Ｒｅ（・）は、複素数の実部、Ｉｍ（・）は複素数の虚部、ｉは虚数単位である。
【００８８】
【数２５】
2006318397.tif 000027
上記のように求められた誤差を記憶部１００に格納する。
【００８９】
次に、適応度計算部７０について説明する。
【００９０】
適応度計算部７０は、記憶部１００から各曲線区間の割り当て候補と曲線パラメータの推定結果、及び誤差を読み出して、各割り当て候補に対して、曲線パラメータ数と誤差から曲線区間に対する当てはまり具合（適応度）を計算し、各割り当て候補毎に適応度を記憶部１００に格納する。
【００９１】
適応度計算部７０は、各割り当て候補の小区間の誤差とモデルのパラメータ数から適応度を以下のように計算する。
【００９２】
【数２６】
2006318397.tif 000028
（ここで、線分のパラメータ数は２、楕円パラメータは５）
上記で求められた適応度を記憶部１００に格納する。
【００９３】
次に、割り当て候補選択部８０について説明する。
【００９４】
割り当て候補選択部８０は、記憶部１００から割り当て候補と適応度を読み込み、各曲線の区間割り当て候補の中から適応度が高く、かつ、隣接曲線区間との重複の少ない割り当て候補を選択し、記憶部１００に格納する。
【００９５】
割り当て候補選択部８０は、図８に示すように、現在の曲線区間ｉと手前の曲線区間ｉ−１とを比較し、重複があるかどうか調べる。重複があれば、図９に示す重複解消ルールに従って重複を解消し、区間候補のリストを更新する。なお、重複解消ルールは、メモリ等の記憶手段に格納されているものとする。
【００９６】
図形情報出力部９０は、記憶部１００から候補を読み出して、当該候補を図形情報としてファイル，ネットワーク等に出力する。
【００９７】
記憶部１００は、入力された輪郭情報や、上記の各構成要素の中間結果（状態ベクトル、折れ線情報、曲線区間情報、割り当て候補、割り当て要素、曲線パラメータ、誤差、適応度）及び後述する重複解消ルール等を記憶する。
【００９８】
次に、上記の構成における動作を説明する。
【００９９】
図１０は、本発明の一実施の形態における動作のフローチャートである。
【０１００】
ステップ５０１）  初期値設定：
非線形平滑化部２０の座標点データへの忠実度を表す閾値σａ，直線モデルとの一致度を表す閾値σｂ、折れ線近似部３０の各線分が同じ方向かどうかを決める閾値△ｔａｎ、曲線区間生成部４０の隣り合う線素がコーナーを形成するかどうかを決める閾値△ｄｉｒの値を設定する。
【０１０１】
ステップ５０２）  輪郭の入力：
輪郭入力部１０は、輪郭情報ｚｔ＝（ｘｔ，ｙｔ）Ｔ，ｔ＝１，…，Ｌを記憶部１００に読み込む。読み込まれた輪郭情報の例を図１１に示す。
【０１０２】
ステップ５０３）  輪郭の平滑化：
非線形平滑化部２０は、記憶部１００の輪郭情報を読み出して、平滑化し、状態ベクトルを生成して、記憶部１００に保存する。状態ベクトルの位置座標を図１２に示す。
【０１０３】
ステップ５０４）  輪郭の折れ線近似：
折れ線近似部３０は、記憶部１００の状態ベクトルを読み出して、図１３に示すように状態ベクトルを折れ線近似して、記憶部１００に保存する。
【０１０４】
ステップ５０５）  曲線区間生成：
曲線区間生成部４０は、記憶部１００から折れ線情報を読み出し、折れ線のコーナーと変曲点を検出し、図１４に示すように区間に分割して記憶部１００に保存する。図１４において、「区間１」と「区間２」はコーナーで分割されるので重複はない。一方、「区間２」と「区間３」は、変曲点で分割されるので、図１５に示すように、変曲点の手前の線素「６」と「７」の区間は「区間２」と「区間３」で重複する。
【０１０５】
ステップ５０６）  割り当て候補生成：
割り当て候補生成部５０は、記憶部１００から曲線区間情報を読み出し、線素の数に応じて割り当て候補を生成する。「区間１」は線素が１なので、候補を一つ姿勢する。「区間２」、「区間３」は、線素が３以上なので、候補を４つ生成する。このようにして生成された候補を図１６に示すような割り当て候補リストとして記憶部１００に格納する。
【０１０６】
ステップ５０７）  曲線パラメータ推定：
曲線パラメータ推定部６０は、記憶部１００から割り当て要素を読み込み、曲線パラメータと誤差を計算して記憶部１００に格納する。
【０１０７】
ステップ５０８）  適応度計算：
適応度計算部７０は、記憶部１００の曲線パラメータ数と誤差から適応度を計算し、記憶部１００に保存する。記憶部１００に格納される適応度のリストの例を図１７に示す。
【０１０８】
ステップ５０９）  割り当て候補選択：
割り当て候補選択部８０は、記憶部１００から図１６に示す割り当て候補リストを読み出して、まず、「区間１」を調べ、次の区間との重複がないので、線分１−２を選択する。次に、「区間２」を調べ、「区間３」と線分６−７が重複しているので、重複の解消を図る。「区間２」の“線分２−３＋楕円３−７”と、「区間３」の“楕円６−１０”の両方が曲線なので、どちらかが線分となる割り当てを調べる。その結果、図１８に示すような重複解消の組み合わせが得られる。
【０１０９】
ここでは、Ｆ１２＋Ｆ２３＞Ｆ２２＋Ｆ１３であるとする。線分６−７は「区間２」に属することになり、線素６−７に関する部分を「区間３」から削除する。その結果、図１９に示すような適応度のリストが記憶部１００に格納される。
【０１１０】
ステップ５１０）  図形情報出力：
割り当て候補選択部８０が全ての区間の重複を解消した後、図形情報出力部９０は、記憶部１００から読み出した各区間の先頭候補を図２０に示すような図形に変換し、ファイル、ネットワーク等に出力する。
【０１１１】
以上述べたように、本発明によれば、ノイズによって輪郭点に凹凸が生じている場合でも、輪郭を正しく線分と楕円弧の区間に分けて認識できる。さらに、割り当て候補生成において楕円以外の曲線、すなわち、放物線やベジェ曲線等を利用してより複雑な図形を認識することも可能である。
【０１１２】
上記の図１０に示す動作をプログラムとして構築し、記憶部１００を有するコンピュータに実行させる、または、ネットワークを介して流通させることも可能である。
【０１１３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１１４】
本発明は、画像から輪郭を抽出して曲線を表現するための図形認識技術に適用可能である。
【図面の簡単な説明】
【０１１５】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における図形認識装置の構成図である。
【図４】本発明の一実施の形態における曲線区間生成部におけるコーナー検出を説明するための図である。
【図５】本発明の一実施の形態における曲線区間生成部の変曲点検出を説明するための図である。
【図６】本発明の一実施の形態における割り当て候補生成を説明するための図である。
【図７】本発明の一実施の形態における楕円パラメータを説明するための図である。
【図８】本発明の一実施の形態における重複部分を示す図である。
【図９】本発明の一実施の形態における重複解消ルールである。
【図１０】本発明の一実施の形態における動作のフローチャートである。
【図１１】本発明の一実施の形態における入力された輪郭の例である。
【図１２】本発明の一実施の形態における平滑化された輪郭の例である。
【図１３】本発明の一実施の形態における折れ線近似の例である。
【図１４】本発明の一実施の形態における区間分割の例である。
【図１５】本発明の一実施の形態における区間候補の例である。
【図１６】本発明の一実施の形態における割り当て候補リストの例である。
【図１７】本発明の一実施の形態における適応度のリストである。
【図１８】本発明の一実施の形態における重複階層の組み合わせである。
【図１９】本発明の一実施の形態における更新後の「区間３」の適応度のリストである。
【図２０】本発明の一実施の形態における図形情報の例である。
【図２１】従来の輪郭分割を示す図である。
【図２２】従来の問題点を説明するための図である。
【符号の説明】
【０１１６】
１０  輪郭入力手段、輪郭入力部
２０  非線形平滑化手段、非線形平滑化部
３０  折れ線近似手段、折れ線近似部
４０  曲線区間生成手段、曲線区間生成部
５０  割り当て候補生成手段、割り当て候補生成部
６０  曲線パラメータ推定手段、曲線パラメータ推定部
７０  適応度計算手段、適応度計算部
８０  割り当て候補選択手段、割り当て候補選択部
９０  図形情報出力手段、図形情報出力部
１００  記憶手段、記憶部
【図１】
2006318397.tif 000029
【図２】
2006318397.tif 000030
【図３】
2006318397.tif 000031
【図４】
2006318397.tif 000032
【図５】
2006318397.tif 000033
【図６】
2006318397.tif 000034
【図７】
2006318397.tif 000035
【図８】
2006318397.tif 000036
【図９】
2006318397.tif 000037
【図１０】
2006318397.tif 000038
【図１１】
2006318397.tif 000039
【図１２】
2006318397.tif 000040
【図１３】
2006318397.tif 000041
【図１４】
2006318397.tif 000042
【図１５】
2006318397.tif 000043
【図１６】
2006318397.tif 000044
【図１７】
2006318397.tif 000045
【図１８】
2006318397.tif 000046
【図１９】
2006318397.tif 000047
【図２０】
2006318397.tif 000048
【図２１】
2006318397.tif 000049
【図２２】
2006318397.tif 000050