形状再現装置及びプログラム
【課題】 現実的なしわの形を再現することのできる形状再現装置及びプログラムを提供する。
【解決手段】 与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置１であって、前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部１１と、隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部１２と、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部１３と、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部１４と、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部１５とを備えた平面形状再現装置である。
【解決手段】 与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置１であって、前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部１１と、隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部１２と、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部１３と、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部１４と、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部１５とを備えた平面形状再現装置である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は三次元形状のモデル化技術に関する。
【背景技術】
【０００２】
紙葉類の汚損を自動で検査する技術を開発する場合、汚損した紙葉類のサンプルを取得することが必要となる。しかし、例えば、検査対象が未発行の紙幣の場合には、汚損したサンプルを大量に収集することが困難である。そこで、画像処理によって汚損した紙幣の画像を生成して利用することが考えられる。しかし、紙幣は流通して使用されることによってしわが発生する。従って、画像処理を利用する場合には、しわを再現して画像処理に組み込むことのできる技術が必要である。
【０００３】
紙など平面のしわを再現する手法として、数値シミュレーションがある。これには、有限要素法や、分子動力学などの手法があり、平面の物理的特性や、それに加わる外力を忠実にシミュレートすることができる。
一方、図形などのパターンを捕らえて統計的に再現する手法として、マルコフ確率場が用いられている。マルコフ確率場については、種々の技法が提案され（非特許文献１乃至５参照）、例えば、文様（texture）の合成に利用されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J.Besag. Spatial interaction and the statistical analysis of lattice systems (with discussion). Journal of the Royal Statistical Society, B, VoL36, PP. 192-236, 1974.
【非特許文献２】Michael S. Brown and W. Brent Seales. Image restoration of arbitrarily warped documents. IEEE TRANS-ACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, Vol. 26, No. 10, pp. 1295-1306, October 2004.
【非特許文献３】Maurizio Pilu. Undoing page curl distortion using applicable surfaces. In IEEE Computer Vision and Pattern Recognition Conference, Vol. 1, pp. 67-72, December 2001. Kauai,HI.
【非特許文献４】Gerhard Winkler. Image Analysis, Random Fields and Markov Chain Monte Carlo Methods. A Mathematical Introduction. Application of Mathematics 27. Stochastic Modeling and Applied Probability. Springer, 2nd edition, 2003.
【非特許文献５】Li Zhang, Yu Zhang, and Chew Lim Tan. An improved physically-based method for geometric restoration of distorted documents images. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 30, No. 4, pp. 728-734, April 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、数値シミュレーションを用いようとしても、現実のしわの物理的状況を完全に再現するのは困難であり、必ずしも、実際の形状をシミュレートしたものが得られるとは限らない。また数値シミュレーションでは、一般に計算に要する時間が大きくなるという問題も指摘されている。
【０００６】
一方、マルコフ確率場を用いてしわを再現する技術は開示されていない。三次元形状に対してマルコフ確率場を作る最も簡単な方法は、三次元形状の高さデータ（標高データ）を取得してその標高データをそのまま用いることである。しかしながら、しわはもともと平らな平面が折れ曲がって出来たものである。例え、標高値が同じしわ同士であったとしても、しわの特徴も同じであるとはいえない。標高値そのものはしわの特徴を表しているとはいえないため、標高値を用いたマルコフ確率場では現実的なしわの形を再現することができない。
【０００７】
本発明は、かかる事情に鑑みてなされたものであって、現実的なしわの形を再現することのできる形状再現装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するための本発明は、与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置であって、前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部と、隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部と、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部と、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部と、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部とを備えた。
【０００９】
また本発明は、与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成するプログラムであって、前記平面形状を三角形の格子によって複数の領域である面素に分割するステップ、隣接する二つの面素の成す角度である面素間角度を求めるステップ、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成するステップ、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするステップ、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現するステップをコンピュータに実行させる。
【発明の効果】
【００１０】
この発明の形状再現装置及びプログラムによれば、現実的なしわの形を再現することができる。
【図面の簡単な説明】
【００１１】
【図１】本実施の形態の形状再現装置の構成を示す図。
【図２】本実施の形態の形状再現装置の形状再現動作を示す概略のフロー図。
【図３】形状再現動作に関連した各部とデータベースのつながりを示す図。
【図４】実測形状を示す図。
【図５】格子形状を例示する図。
【図６】平面面素分割部が分割した格子点を例示する図。
【図７】面素と面素間角度との関係を表す図。
【図８】算出した面素間角度を示す図。
【図９】近傍データベースに登録されている近傍パターンの例を示す図。
【図１０】採用する近傍パターンの指定方法を説明する図。
【図１１】面素配置部が位置決めした結果を示す図。
【図１２】面素配置部の構成を示す図。
【図１３】総合ずれコスト最小化部の処理手順を示すフロー図。
【図１４】出力形状のフォーマット例を示す図。
【発明を実施するための形態】
【００１２】
[第１の実施の形態]
図１は、本実施の形態の形状再現装置１の構成を示す図である。
形状再現装置１には、入出力装置２、形状計３が適宜接続される。入出力装置２は、形状再現装置１にユーザの操作指示を入力し、また形状再現装置１からの出力を表示する。形状計３は、レーザ等を用いて対象とする物体表面の三次元形状を測定する。
【００１３】
形状再現装置１は、入出力制御部１０、平面面素分割部１１、面素間角度取得部１２、確率場形成部１３、サンプル部１４、面素配置部１５及びデータベース部２０を備えている。
【００１４】
入出力制御部１０は、形状再現装置１が入出力装置２、形状計３との間でデータを授受するためのインターフェースである。平面面素分割部１１は、形状計３が測定した測定値に基づいて物体表面の形状を格子形状に変換する。面素間角度取得部１２は、格子で囲まれる面同士の角度（面素間角度）を計算する。確率場形成部１３は、面素間角度を変数とする確率場を形成する。サンプル部１４は、形成された確率場から値をサンプリングする。面素配置部１５は、サンプリングした値を用いて形状を再現する。この再現した形状は形状再現装置１の出力形状である。
【００１５】
そして、データベース部２０には、実測形状データベース２１、格子形状データベース２２、近傍データベース２３及び出力形状データベース２４が設けられている。
【００１６】
実測形状データベース２１には、形状計３で測定した実測値が記憶されている。格子形状データベース２２には、種々の格子形状が記憶されている。近傍データベース２３には、様々な近傍パターン（後述）が記憶されている。出力形状データベース２４には、再現した形状のデータが記憶されている。
【００１７】
図２は、本実施の形態の形状再現装置１の形状再現動作を示す概略のフロー図である。図３は、この形状再現動作に関連した各部とデータベースのつながりを示す図である。なお、図３には、各部の処理に用いられる入力データ及び各部の処理結果である出力データなどを表している。
以下、図２、図３を参照しつつ形状再現装置１の形状再現動作を説明する。
【００１８】
図２のステップＳ０１において、入出力制御部１０は、形状計３が測定した実測形状を読込み実測形状データベース２１に記憶する。実測形状は、例えばレーザー計測により得られ、図４に示すようにＸＹ座標とその点での高さを記録したものである。
【００１９】
ステップＳ０２において、平面面素分割部１１は、読込み実測形状データベース２１に記録されている実測形状を格子形状に変換する。より詳細には、次の二つの制約を（できるだけ）充たすように、実測形状を三角格子に分割する。
（制約１）格子点は実測形状上にある。（制約２）隣接する格子点間の距離は等しい。
なお、この分割においては、非特許文献２，３，５に記載された技術を適用することができる。
【００２０】
本実施の形態では、平面を複数の三角形に分割する格子を用いる。格子の形や大きさには様々なものが考え得る。図５は、格子形状を例示する図である。格子形状データベース２２にはこれらの格子形状がデータベースとして記録されている。
【００２１】
以下の説明では、格子点（格子を形成するための複数の直線の交点）を特定して示すための指数（格子点指数）として、ｉ，ｊ，ｋ，ｌなどの記号を用いる。格子は二次元平面上の点であるため、格子点指数は二つの整数の組で表すことができる。例えばｉ＝（２，４）などと表す。
図６は、平面面素分割部１１が分割した格子点を例示する図である。このように、それぞれの格子点は、空間的な座標位置と対応付けられる。
【００２２】
また格子の辺はその両端の格子点の組で表す。例えば、格子点ｉと格子点ｊとを結ぶ辺は［ｉ，ｊ］と表記する。
なお、格子によって分割された一つの領域を面素と呼ぶ。図５に示す格子形状では一つ一つの三角形で表される面の領域が面素となる。
【００２３】
ステップＳ０３において、面素間角度取得部１２は、一つの面素と隣接する面素との間の角度（以下、面素間角度と呼ぶ）を計算する。
図７は、面素と面素間角度との関係を表す図である。格子点指数ｉで指定される格子点の空間での位置をベクトルｒｉ＝（ｘｉ、ｙｉ、ｚｉ）とする。いまベクトルｒｉ、ｒｊ、ｒｋが互いに隣接する格子点を表すとすると、この三つの格子点で作られる面素｛ｉ，ｊ，ｋ｝の法線方向を表すベクトルｎｉｊｋは次の式（１）で与えられる。
【数１】
【００２４】
この面素｛ｉ，ｊ，ｋ｝と格子点ｊ、格子点ｋを共有し、もう一つの格子点ｚを持つ隣接する面素｛ｊ，ｋ，ｌ｝の法線方向ベクトルｎｊｋｌも同様に与えられる。したがって、この二つの面素間の面素間角度θｊｋは次の式（２）で与えられる。
【数２】
【００２５】
図８は、算出した面素間角度を示す図である。格子点指数１と格子点指数２とで表される２つの格子点を結ぶ直線を辺として共有する二つの三角形のなす角度を面素間角度として表している。
【００２６】
ここで、隣接する二つの面素間の面素間角度θｊｋを求めるのは、この面素間角度がしわの特性を表していると考えるからである。いま、素材として伸縮のほとんど無い紙を例とすると、しわの無い平らな紙の上に設けた２点間の距離は、しわが発生したとしても変化しない。一方、しわが発生することによって、そのそれぞれの点を含む平面と元の平らな平面とのなす角度が変化する。従って、この角度に紙の変形情報が含まれていると考えられる。本実施の形態では、この技術思想に基づいて、角度を変数とする確率場を生成する。
【００２７】
ステップＳ０４において、確率場形成部１３は、一つ一つの面素間角度を変数とする確率場を作成する。
確率場とは、複数の変数（面素間角度）が相互に関係しながら作られる多変量統計分布のことである。各変数が二次元またはそれ以上の空間に規則正しく配置させていることを念頭において「場」という言葉が使われている。このため、「場」は、画像や空間統計などのモデルとして良く用いられる。
【００２８】
確率場を指定するには、場を形成する一つの変数が他のどの変数と相互作用するかを指定する必要がある。この一つの変数と相互作用のある変数の関係を「近傍」と呼ぶ。また相互作用の形とその強さも決める必要がある。本実施例では相互作用の形としてガウス分布型のもののみを考える。したがって確率場を作ることは次の二つのステップからなる。
（第１ステップ）近傍を定義する。（第２ステップ）相互作用の強さ、つまり結合定数の大きさを決める。
以下、これら２つのステップの内容について具体的に説明する。
【００２９】
第１ステップ：近傍の定義
近傍データベース２３には様々な近傍パターンが記憶されている。図９は、近傍データベース２３に登録されている近傍パターンの例を示す図である。図の黒丸は、格子点と格子点の中間の位置を表現している。即ち、黒丸は、図８に示す２つの格子点に対応する面素間角度を表している。
【００３０】
また、図９のそれぞれの近傍パターンに示す、二つの黒丸を結ぶ実線は、その二つの面素間角度間に相互作用があることを表現している。従って、実線で結ばれた隣接する黒丸同士は相互に作用を及ぼす。ａ＝０の場合の近傍パターンには、実線がなく各黒丸は二重丸で囲まれている。この二重丸は自己相互作用を表すが、その統計分布としての意味は後ほどエネルギー関数を導入するところで説明する。
【００３１】
確率場では、それぞれの変数（面素間角度）に「位置」が付随している。したがって近傍を定義する場合も、位置的に近いものを考えるのが自然である。図９においても、近い位置にある黒丸と実線で結ばれている。しかしながら、近傍は必ずしも空間的に近いものに限定される訳ではない。遠くはなれた面素間角度間に相互作用がある近傍パターンを考えることができる。従って、図９に示す近傍パターンに限られず、近傍データベース２３により多くの近傍パターンを登録することも可能である。またここでは二つの面素間角度間の相互作用しか示していないが、三つ以上の面素間角度間の相互作用を考えることも可能である。
【００３２】
このようにして、近傍を決めることにより、確率密度分布の形を定義する方法を説明する。今、格子点ｉと格子点ｊとを結ぶ辺［ｉ，ｊ］に対応する面素間角度の値をθｉｊと表す。また全ての面素間角度の集合をΘと表す。すなわち、Θは式（３）で表される。
【数３】
【００３３】
ここで、ユーザーはどの近傍パターンを使うかを指定する。図１０は、採用する近傍パターンの指定方法を説明する図である。図１０では、近傍パターンのタイプａが、０，３，４の３つのパターンが採用されている。この近傍パターンの指定は、入出力装置２を介して行うことができる。ここで、採用された近傍パターンは、以下に示す確率密度関数の定式化で用いられる。
【００３４】
そして、Θについてエネルギーを式（４）で定義する。
【数４】
【００３５】
なお、Σａにおいて、図１０の採否が１であったパターンが和の対象となる。ρａは近傍ａの結合定数と呼ぶ。また、[ｉ，ｊ]〜[ｋ、ｌ]は、辺[ｉ，ｊ]と辺[ｋ、ｌ]とが隣接していること、即ち、近傍パターンにおいて、辺[ｉ，ｊ]上の黒丸と辺[ｋ，ｌ]上の黒丸とが実線で結ばれていることを表している。
【００３６】
次に、Θの確率密度分布ｐ（Θ）を式（５）で与える。
【数５】
【００３７】
ここで近傍パターンａ＝０場合は、式（４）のエネルギー関数にΣθ２ｉｊの項を導入する。従ってこのときの確率密度分布ｐ（Θ）は式（６）で表される。
【数６】
【００３８】
式（６）は、これはθｉｊが正規分布に従うことを表している。従って結合定数ρ０は分散を規定する量になっていることがわかる。
【００３９】
ここで、式（４）におけるエネルギーを導入したことについて説明する。
エネルギーは、確率に対応させる概念として導入したものである。例えば、統計力学では、エネルギーが高い状態は確率的に実現しにくく、エネルギーが低い状態は確率的に実現しやすいとされることのアナロジーとして捉えることができる。
【００４０】
この考えを式（４）に当てはめてみると、エネルギーの小さい、隣接する面素間角度の差が小さい事象（しわの折り目の影響が少ない部分）が発生する確率は大きく、エネルギーの大きい、隣接する面素間角度の差が大きい事象（しわの折り目の近傍に位置する部分）が発生する確率は小さいことを前提としている。この前提は、現実のしわの発生状況として妥当なものである。
【００４１】
なお、式（４）では、近傍ａの結合定数ρａの値の大小あるいは正負によって得られるエネルギー値が変更される。即ち、結合定数ρａをどのように選定するかによって、近傍パターン毎にエネルギー値、即ちその近傍パターンの発生確率が決定される。
【００４２】
そこで、結合定数ρａを実測形状に基づいて決定する。そのため、式（７）に示す最尤推定法（Maximum Likelihood Method）を用いる。
【数７】
【００４３】
ここでΘ０は面素間角度取得部１２により与えられる、実測形状による入力面素間角度値の値である。
【００４４】
式（７）に示す最尤推定法により、結合定数ρａを求めることが可能である。なお、最尤推定法を適用する際の規格化定数Ｚの計算方法については、例えば、非特許文献１、４などに開示された手法を用いることができる。
【００４５】
以上の処理によって、実測形状に基づいてしわの面素間角度を変数とする確率密度分布を得ることができる。従って、この確率密度分布を母集団としてサンプリングした面素間角度の集合は、しわの一形態を再現していることになる。
【００４６】
図２のステップＳ０５において、サンプル部１４は、確率場形成部１３が求めた結合定数の組｛ｐａ｝によって決まる確率場から面素間角度値をサンプリングによって取り出す。なお、このときの確率密度分布は式（５）で与えられる。確率場のように多変量の確率分布からサンプルを取り出す技術としてはマルコフ連鎖モンテカルロ法を用いることが出来る（例えば、非特許文献４参照）。
【００４７】
ステップＳ０６において、面素配置部１５は、サンプリングにより取り出した面素間角度の集合Θを用いて面素の位置決めを行う。
図１１は、面素配置部１５が位置決めした結果を示す図である。サンプリングで抽出した面素間角度が、格子点指数１と格子点指数２とで表される２つの格子点を結ぶ直線を辺として共有する二つの三角形のなす角度として位置決めされている。
【００４８】
以下、面素配置部１５の動作について説明する。
面素配置部１５は、次の二つの制約を（出来るだけ）充たすように出力形状の格子点の位置を決める。
【００４９】
（制約１）面素間角度はサンプル部１４が出力した面素間角度値に等しい。（制約２）隣接する格子点間の距離は等しい。
【００５０】
図１２は、面素配置部１５の構成を示す図である。
面素配置部１５は、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８を備えている。
【００５１】
面素配置部１５は、ある格子点の位置を初期値として、上記２つの制約を充足するように格子点位置を変更しながら繰返し計算を実行する。この際、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８が、面素間角度のずれ、格子点間の距離のずれ、総合的なずれを評価する。面素配置部１５は、これらの評価において、ずれが所定範囲内に収まったときに、繰返し計算を終了し、そのときの格子点の位置を出力形状の格子点の位置とする。
【００５２】
ここで、面素配置部１５が、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８を用いて繰返し計算を行うことの必要性について説明する。
【００５３】
上述のように、マルコフ確率場から得られる情報は面素間角度値である。そこで、この面素間角度値がどの位置にあるものか、即ち、高さの情報を対応付ける必要がある。しかし、得られた面素間角度値をそのまま採用して高さを決めることは、必ずしも可能ではない。これは、例えば、紙のように伸縮性が低い素材を対象とした場合は、実現できない形状となり、現実の形状と乖離したデータとなるからである。
【００５４】
従って、マルコフ確率場からの角度は尊重しつつ、できるだけ伸縮が生じないように位置を決定することが必要である。本実施の形態では、少しの角度のずれと、少しの長さのずれを許容し、その代わり、角度と長さがそれぞれずれることによるデメリットをコストとして評価する。そして、これらのコストができるだけ小さくなるように位置を決定する。
【００５５】
まず、面素間角度ずれコストについて説明する。
格子点の位置が与えられた場合の面素間角度は、上述の式（１）、式（２）を用いて求めることができる。そこで、マルコフ確率場から求めた面素間角度をθ０ｊｋとすると、面素間角度ずれコスト計算部１６は、面素間角度ずれコストＣＡを式（８）で求める。
【数８】
【００５６】
続いて、長さずれコストについて説明する。
二つの格子点ｊ，ｋ間の距離ｌｊｋは式（９）で与えられる。
【数９】
【００５７】
ところで、格子点間の距離は元々は所定の長さｌ０であった。そこで、長さずれコスト計算部１７は、長さずれコストＣＬを式（１０）で求める。
【数１０】
【００５８】
次に、総合ずれコスト最小化部１８について説明する。
総合ずれコスト最小化部１８は、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７を用いて面素の位置を決定する。
図１３は、総合ずれコスト最小化部１８の処理手順を示すフロー図である。
【００５９】
ステップＳ１１において、総合ずれコスト最小化部１８は、各格子点の初期値ｒ０ｉをｒｉに代入する。ステップＳ１２において、初期値に対応した面素間角度ずれコストＣ０Ａと当該面素間角度ずれコストＣ０Ａのｒｉでの微分値を求める。
【００６０】
ここで、微分値を求めるのは、総合ずれコスト最小化部１８が総合コストを最小化する際に必要となるからである。微分値は、式（８）の関数を直接微分して計算することもできるし、数値的に処理して微分することも可能である。数値的に処理する場合は、ｒｉを微小量δｒｉ変化させたときのＣＡの変化δＣＡを求めて、その商を計算すれば良い。
【００６１】
ステップＳ１３において、初期値に対応した長さずれコストＣ０Ｌと当該長さずれコストＣ０Ｌのｒｉでの微分値を求める。ここで、微分値を求めるのは、面素間角度ずれコストの場合と同様に、総合ずれコスト最小化部１８が総合コストを最小化する際に必要となるからである。なお、微分値は、上述と同様に、関数の微分あるいは数値処理いずれの方法でも計算できる。
【００６２】
ステップＳ１４において、総合ずれコストＣ０Ｔとその微分値を求める。これらは、ステップＳ１２及びステップＳ１３で求めたコスト及び微分値を加算して得られる。
以上の準備処理に続いて、総合ずれコストＣ０Ｔを評価値とする繰返し計算を実行する。
【００６３】
ステップＳ１５において、総合ずれコストＣ０Ｔを減少させるようなｒｉの変化分δｒｉを計算する。具体的には、微小量ｋ（＞０）を設定して、その符号を反転させた値（−ｋ）とステップＳ１４で求めた微分値とを積算した値を変化分δｒｉとする。そして、ステップＳ１６において、その変化分δｒｉを各格子点座標値ｒｉと加算した値を新たな格子点座標値ｒｉとする。
【００６４】
ステップＳ１７〜Ｓ１９において、新たな格子点座標値ｒｉを用いて、上述のステップＳ１２〜Ｓ１４と同様の手順で、新たな面素間角度ずれコスト、長さずれコスト、総合ずれコストとそれらの微分値とを求める。
【００６５】
ステップＳ２０において、計算が収束したかどうか判定する。具体的には総合ずれコストの変化Ｃ１Ｔ−Ｃ０Ｔを計算し、それが所定の閾値εよりも小さいか確かめる。もし小さければ、計算が収束したものとみなし、このときのｒ０ｉの値を最終的な格子点の座標値とする。
小さくない場合は、ステップＳ２１において、このときの格子点の座標値、総合ずれコスト、微分値を新たな初期値としてステップＳ１５からの処理を実行する。
【００６６】
以上の処理によって、最終的に出力形状として格子点の座標を得ることができる。
図１４は、出力形状のフォーマット例を示す図である。この出力形状は、出力形状データベース２４に格納され、あるいは入出力装置２に表示される。
【００６７】
なお、マルコフ確率場からはサンプリングにより面素間角度値の集合Θを一つまたは複数得ることができる。上述の実施の形態では、一組のサンプル値を用いたが、応用によっては複数組のサンプル値が必要になることもある。その場合はおのおのの組のサンプルに対して、面素配置部１５を用いて出力形状を作り出せば良い。
【００６８】
また、サンプルの格子サイズは、必ずしも実測形状を平面面素分割部１１で分割したときの格子サイズと同じでなくても良く、用途に対して適した格子サイズを指定することもできる。
【００６９】
[実施の形態の効果]
以上説明した実施の形態によれば、紙のしわなどのように、平面が折れ曲がってできる形状に関する統計的な分布モデルを得ることができる。この分布モデルを用いることにより、上述の形状を定量的に取り扱うことができる。これにより、上述の形状を画像処理に組み込むことが可能となる。例えば、分布モデルからサンプリングされた結果に基づいて生成された形状に関するデータを、公知の技術を利用して紙幣の画像に適用する。そして、得られたしわのある画像と基準となる画像とを比較することで紙幣の汚損の程度を評価することが可能となる。
【００７０】
このように、本実施の形態では一般に折れ曲がった平面の状態を定量的に取り扱うことができるため、折れ曲がった平面上に記録されている情報の劣化度の評価、あるいは情報の復元が可能となる。また、折れ曲がった平面による音、光、電磁波等の反射の効果の評価が可能になる。
【００７１】
なお、上述の実施の形態ではマルコフ確率場を用いているが、マルコフ確率場に限定されるものではない。
【００７２】
なお、上述の各実施の形態で説明した機能は、ハードウエアを用いて構成するに留まらず、ソフトウエアを用いて各機能を記載したプログラムをコンピュータに読み込ませて実現することもできる。また、各機能は、適宜ソフトウエア、ハードウエアのいずれかを選択して構成するものであっても良い。
【００７３】
尚、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００７４】
１…形状再現装置、２…入出力装置、１０…入出力制御部、１１…平面面素分割部、１２…面素間角度取得部、１３…確率場形成部、１４…サンプル部、１５…面素配置部、１６…面素間角度ずれコスト計算部、１７…長さずれコスト計算部、１８…総合ずれコスト最小化部、２０…データベース部、２１…実測形状データベース、２１…読込み実測形状データベース、２２…格子形状データベース、２３…近傍データベース、２４…出力形状データベース。
【技術分野】
【０００１】
本発明は三次元形状のモデル化技術に関する。
【背景技術】
【０００２】
紙葉類の汚損を自動で検査する技術を開発する場合、汚損した紙葉類のサンプルを取得することが必要となる。しかし、例えば、検査対象が未発行の紙幣の場合には、汚損したサンプルを大量に収集することが困難である。そこで、画像処理によって汚損した紙幣の画像を生成して利用することが考えられる。しかし、紙幣は流通して使用されることによってしわが発生する。従って、画像処理を利用する場合には、しわを再現して画像処理に組み込むことのできる技術が必要である。
【０００３】
紙など平面のしわを再現する手法として、数値シミュレーションがある。これには、有限要素法や、分子動力学などの手法があり、平面の物理的特性や、それに加わる外力を忠実にシミュレートすることができる。
一方、図形などのパターンを捕らえて統計的に再現する手法として、マルコフ確率場が用いられている。マルコフ確率場については、種々の技法が提案され（非特許文献１乃至５参照）、例えば、文様（texture）の合成に利用されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J.Besag. Spatial interaction and the statistical analysis of lattice systems (with discussion). Journal of the Royal Statistical Society, B, VoL36, PP. 192-236, 1974.
【非特許文献２】Michael S. Brown and W. Brent Seales. Image restoration of arbitrarily warped documents. IEEE TRANS-ACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, Vol. 26, No. 10, pp. 1295-1306, October 2004.
【非特許文献３】Maurizio Pilu. Undoing page curl distortion using applicable surfaces. In IEEE Computer Vision and Pattern Recognition Conference, Vol. 1, pp. 67-72, December 2001. Kauai,HI.
【非特許文献４】Gerhard Winkler. Image Analysis, Random Fields and Markov Chain Monte Carlo Methods. A Mathematical Introduction. Application of Mathematics 27. Stochastic Modeling and Applied Probability. Springer, 2nd edition, 2003.
【非特許文献５】Li Zhang, Yu Zhang, and Chew Lim Tan. An improved physically-based method for geometric restoration of distorted documents images. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 30, No. 4, pp. 728-734, April 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、数値シミュレーションを用いようとしても、現実のしわの物理的状況を完全に再現するのは困難であり、必ずしも、実際の形状をシミュレートしたものが得られるとは限らない。また数値シミュレーションでは、一般に計算に要する時間が大きくなるという問題も指摘されている。
【０００６】
一方、マルコフ確率場を用いてしわを再現する技術は開示されていない。三次元形状に対してマルコフ確率場を作る最も簡単な方法は、三次元形状の高さデータ（標高データ）を取得してその標高データをそのまま用いることである。しかしながら、しわはもともと平らな平面が折れ曲がって出来たものである。例え、標高値が同じしわ同士であったとしても、しわの特徴も同じであるとはいえない。標高値そのものはしわの特徴を表しているとはいえないため、標高値を用いたマルコフ確率場では現実的なしわの形を再現することができない。
【０００７】
本発明は、かかる事情に鑑みてなされたものであって、現実的なしわの形を再現することのできる形状再現装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するための本発明は、与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置であって、前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部と、隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部と、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部と、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部と、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部とを備えた。
【０００９】
また本発明は、与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成するプログラムであって、前記平面形状を三角形の格子によって複数の領域である面素に分割するステップ、隣接する二つの面素の成す角度である面素間角度を求めるステップ、面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成するステップ、この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするステップ、サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現するステップをコンピュータに実行させる。
【発明の効果】
【００１０】
この発明の形状再現装置及びプログラムによれば、現実的なしわの形を再現することができる。
【図面の簡単な説明】
【００１１】
【図１】本実施の形態の形状再現装置の構成を示す図。
【図２】本実施の形態の形状再現装置の形状再現動作を示す概略のフロー図。
【図３】形状再現動作に関連した各部とデータベースのつながりを示す図。
【図４】実測形状を示す図。
【図５】格子形状を例示する図。
【図６】平面面素分割部が分割した格子点を例示する図。
【図７】面素と面素間角度との関係を表す図。
【図８】算出した面素間角度を示す図。
【図９】近傍データベースに登録されている近傍パターンの例を示す図。
【図１０】採用する近傍パターンの指定方法を説明する図。
【図１１】面素配置部が位置決めした結果を示す図。
【図１２】面素配置部の構成を示す図。
【図１３】総合ずれコスト最小化部の処理手順を示すフロー図。
【図１４】出力形状のフォーマット例を示す図。
【発明を実施するための形態】
【００１２】
[第１の実施の形態]
図１は、本実施の形態の形状再現装置１の構成を示す図である。
形状再現装置１には、入出力装置２、形状計３が適宜接続される。入出力装置２は、形状再現装置１にユーザの操作指示を入力し、また形状再現装置１からの出力を表示する。形状計３は、レーザ等を用いて対象とする物体表面の三次元形状を測定する。
【００１３】
形状再現装置１は、入出力制御部１０、平面面素分割部１１、面素間角度取得部１２、確率場形成部１３、サンプル部１４、面素配置部１５及びデータベース部２０を備えている。
【００１４】
入出力制御部１０は、形状再現装置１が入出力装置２、形状計３との間でデータを授受するためのインターフェースである。平面面素分割部１１は、形状計３が測定した測定値に基づいて物体表面の形状を格子形状に変換する。面素間角度取得部１２は、格子で囲まれる面同士の角度（面素間角度）を計算する。確率場形成部１３は、面素間角度を変数とする確率場を形成する。サンプル部１４は、形成された確率場から値をサンプリングする。面素配置部１５は、サンプリングした値を用いて形状を再現する。この再現した形状は形状再現装置１の出力形状である。
【００１５】
そして、データベース部２０には、実測形状データベース２１、格子形状データベース２２、近傍データベース２３及び出力形状データベース２４が設けられている。
【００１６】
実測形状データベース２１には、形状計３で測定した実測値が記憶されている。格子形状データベース２２には、種々の格子形状が記憶されている。近傍データベース２３には、様々な近傍パターン（後述）が記憶されている。出力形状データベース２４には、再現した形状のデータが記憶されている。
【００１７】
図２は、本実施の形態の形状再現装置１の形状再現動作を示す概略のフロー図である。図３は、この形状再現動作に関連した各部とデータベースのつながりを示す図である。なお、図３には、各部の処理に用いられる入力データ及び各部の処理結果である出力データなどを表している。
以下、図２、図３を参照しつつ形状再現装置１の形状再現動作を説明する。
【００１８】
図２のステップＳ０１において、入出力制御部１０は、形状計３が測定した実測形状を読込み実測形状データベース２１に記憶する。実測形状は、例えばレーザー計測により得られ、図４に示すようにＸＹ座標とその点での高さを記録したものである。
【００１９】
ステップＳ０２において、平面面素分割部１１は、読込み実測形状データベース２１に記録されている実測形状を格子形状に変換する。より詳細には、次の二つの制約を（できるだけ）充たすように、実測形状を三角格子に分割する。
（制約１）格子点は実測形状上にある。（制約２）隣接する格子点間の距離は等しい。
なお、この分割においては、非特許文献２，３，５に記載された技術を適用することができる。
【００２０】
本実施の形態では、平面を複数の三角形に分割する格子を用いる。格子の形や大きさには様々なものが考え得る。図５は、格子形状を例示する図である。格子形状データベース２２にはこれらの格子形状がデータベースとして記録されている。
【００２１】
以下の説明では、格子点（格子を形成するための複数の直線の交点）を特定して示すための指数（格子点指数）として、ｉ，ｊ，ｋ，ｌなどの記号を用いる。格子は二次元平面上の点であるため、格子点指数は二つの整数の組で表すことができる。例えばｉ＝（２，４）などと表す。
図６は、平面面素分割部１１が分割した格子点を例示する図である。このように、それぞれの格子点は、空間的な座標位置と対応付けられる。
【００２２】
また格子の辺はその両端の格子点の組で表す。例えば、格子点ｉと格子点ｊとを結ぶ辺は［ｉ，ｊ］と表記する。
なお、格子によって分割された一つの領域を面素と呼ぶ。図５に示す格子形状では一つ一つの三角形で表される面の領域が面素となる。
【００２３】
ステップＳ０３において、面素間角度取得部１２は、一つの面素と隣接する面素との間の角度（以下、面素間角度と呼ぶ）を計算する。
図７は、面素と面素間角度との関係を表す図である。格子点指数ｉで指定される格子点の空間での位置をベクトルｒｉ＝（ｘｉ、ｙｉ、ｚｉ）とする。いまベクトルｒｉ、ｒｊ、ｒｋが互いに隣接する格子点を表すとすると、この三つの格子点で作られる面素｛ｉ，ｊ，ｋ｝の法線方向を表すベクトルｎｉｊｋは次の式（１）で与えられる。
【数１】
【００２４】
この面素｛ｉ，ｊ，ｋ｝と格子点ｊ、格子点ｋを共有し、もう一つの格子点ｚを持つ隣接する面素｛ｊ，ｋ，ｌ｝の法線方向ベクトルｎｊｋｌも同様に与えられる。したがって、この二つの面素間の面素間角度θｊｋは次の式（２）で与えられる。
【数２】
【００２５】
図８は、算出した面素間角度を示す図である。格子点指数１と格子点指数２とで表される２つの格子点を結ぶ直線を辺として共有する二つの三角形のなす角度を面素間角度として表している。
【００２６】
ここで、隣接する二つの面素間の面素間角度θｊｋを求めるのは、この面素間角度がしわの特性を表していると考えるからである。いま、素材として伸縮のほとんど無い紙を例とすると、しわの無い平らな紙の上に設けた２点間の距離は、しわが発生したとしても変化しない。一方、しわが発生することによって、そのそれぞれの点を含む平面と元の平らな平面とのなす角度が変化する。従って、この角度に紙の変形情報が含まれていると考えられる。本実施の形態では、この技術思想に基づいて、角度を変数とする確率場を生成する。
【００２７】
ステップＳ０４において、確率場形成部１３は、一つ一つの面素間角度を変数とする確率場を作成する。
確率場とは、複数の変数（面素間角度）が相互に関係しながら作られる多変量統計分布のことである。各変数が二次元またはそれ以上の空間に規則正しく配置させていることを念頭において「場」という言葉が使われている。このため、「場」は、画像や空間統計などのモデルとして良く用いられる。
【００２８】
確率場を指定するには、場を形成する一つの変数が他のどの変数と相互作用するかを指定する必要がある。この一つの変数と相互作用のある変数の関係を「近傍」と呼ぶ。また相互作用の形とその強さも決める必要がある。本実施例では相互作用の形としてガウス分布型のもののみを考える。したがって確率場を作ることは次の二つのステップからなる。
（第１ステップ）近傍を定義する。（第２ステップ）相互作用の強さ、つまり結合定数の大きさを決める。
以下、これら２つのステップの内容について具体的に説明する。
【００２９】
第１ステップ：近傍の定義
近傍データベース２３には様々な近傍パターンが記憶されている。図９は、近傍データベース２３に登録されている近傍パターンの例を示す図である。図の黒丸は、格子点と格子点の中間の位置を表現している。即ち、黒丸は、図８に示す２つの格子点に対応する面素間角度を表している。
【００３０】
また、図９のそれぞれの近傍パターンに示す、二つの黒丸を結ぶ実線は、その二つの面素間角度間に相互作用があることを表現している。従って、実線で結ばれた隣接する黒丸同士は相互に作用を及ぼす。ａ＝０の場合の近傍パターンには、実線がなく各黒丸は二重丸で囲まれている。この二重丸は自己相互作用を表すが、その統計分布としての意味は後ほどエネルギー関数を導入するところで説明する。
【００３１】
確率場では、それぞれの変数（面素間角度）に「位置」が付随している。したがって近傍を定義する場合も、位置的に近いものを考えるのが自然である。図９においても、近い位置にある黒丸と実線で結ばれている。しかしながら、近傍は必ずしも空間的に近いものに限定される訳ではない。遠くはなれた面素間角度間に相互作用がある近傍パターンを考えることができる。従って、図９に示す近傍パターンに限られず、近傍データベース２３により多くの近傍パターンを登録することも可能である。またここでは二つの面素間角度間の相互作用しか示していないが、三つ以上の面素間角度間の相互作用を考えることも可能である。
【００３２】
このようにして、近傍を決めることにより、確率密度分布の形を定義する方法を説明する。今、格子点ｉと格子点ｊとを結ぶ辺［ｉ，ｊ］に対応する面素間角度の値をθｉｊと表す。また全ての面素間角度の集合をΘと表す。すなわち、Θは式（３）で表される。
【数３】
【００３３】
ここで、ユーザーはどの近傍パターンを使うかを指定する。図１０は、採用する近傍パターンの指定方法を説明する図である。図１０では、近傍パターンのタイプａが、０，３，４の３つのパターンが採用されている。この近傍パターンの指定は、入出力装置２を介して行うことができる。ここで、採用された近傍パターンは、以下に示す確率密度関数の定式化で用いられる。
【００３４】
そして、Θについてエネルギーを式（４）で定義する。
【数４】
【００３５】
なお、Σａにおいて、図１０の採否が１であったパターンが和の対象となる。ρａは近傍ａの結合定数と呼ぶ。また、[ｉ，ｊ]〜[ｋ、ｌ]は、辺[ｉ，ｊ]と辺[ｋ、ｌ]とが隣接していること、即ち、近傍パターンにおいて、辺[ｉ，ｊ]上の黒丸と辺[ｋ，ｌ]上の黒丸とが実線で結ばれていることを表している。
【００３６】
次に、Θの確率密度分布ｐ（Θ）を式（５）で与える。
【数５】
【００３７】
ここで近傍パターンａ＝０場合は、式（４）のエネルギー関数にΣθ２ｉｊの項を導入する。従ってこのときの確率密度分布ｐ（Θ）は式（６）で表される。
【数６】
【００３８】
式（６）は、これはθｉｊが正規分布に従うことを表している。従って結合定数ρ０は分散を規定する量になっていることがわかる。
【００３９】
ここで、式（４）におけるエネルギーを導入したことについて説明する。
エネルギーは、確率に対応させる概念として導入したものである。例えば、統計力学では、エネルギーが高い状態は確率的に実現しにくく、エネルギーが低い状態は確率的に実現しやすいとされることのアナロジーとして捉えることができる。
【００４０】
この考えを式（４）に当てはめてみると、エネルギーの小さい、隣接する面素間角度の差が小さい事象（しわの折り目の影響が少ない部分）が発生する確率は大きく、エネルギーの大きい、隣接する面素間角度の差が大きい事象（しわの折り目の近傍に位置する部分）が発生する確率は小さいことを前提としている。この前提は、現実のしわの発生状況として妥当なものである。
【００４１】
なお、式（４）では、近傍ａの結合定数ρａの値の大小あるいは正負によって得られるエネルギー値が変更される。即ち、結合定数ρａをどのように選定するかによって、近傍パターン毎にエネルギー値、即ちその近傍パターンの発生確率が決定される。
【００４２】
そこで、結合定数ρａを実測形状に基づいて決定する。そのため、式（７）に示す最尤推定法（Maximum Likelihood Method）を用いる。
【数７】
【００４３】
ここでΘ０は面素間角度取得部１２により与えられる、実測形状による入力面素間角度値の値である。
【００４４】
式（７）に示す最尤推定法により、結合定数ρａを求めることが可能である。なお、最尤推定法を適用する際の規格化定数Ｚの計算方法については、例えば、非特許文献１、４などに開示された手法を用いることができる。
【００４５】
以上の処理によって、実測形状に基づいてしわの面素間角度を変数とする確率密度分布を得ることができる。従って、この確率密度分布を母集団としてサンプリングした面素間角度の集合は、しわの一形態を再現していることになる。
【００４６】
図２のステップＳ０５において、サンプル部１４は、確率場形成部１３が求めた結合定数の組｛ｐａ｝によって決まる確率場から面素間角度値をサンプリングによって取り出す。なお、このときの確率密度分布は式（５）で与えられる。確率場のように多変量の確率分布からサンプルを取り出す技術としてはマルコフ連鎖モンテカルロ法を用いることが出来る（例えば、非特許文献４参照）。
【００４７】
ステップＳ０６において、面素配置部１５は、サンプリングにより取り出した面素間角度の集合Θを用いて面素の位置決めを行う。
図１１は、面素配置部１５が位置決めした結果を示す図である。サンプリングで抽出した面素間角度が、格子点指数１と格子点指数２とで表される２つの格子点を結ぶ直線を辺として共有する二つの三角形のなす角度として位置決めされている。
【００４８】
以下、面素配置部１５の動作について説明する。
面素配置部１５は、次の二つの制約を（出来るだけ）充たすように出力形状の格子点の位置を決める。
【００４９】
（制約１）面素間角度はサンプル部１４が出力した面素間角度値に等しい。（制約２）隣接する格子点間の距離は等しい。
【００５０】
図１２は、面素配置部１５の構成を示す図である。
面素配置部１５は、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８を備えている。
【００５１】
面素配置部１５は、ある格子点の位置を初期値として、上記２つの制約を充足するように格子点位置を変更しながら繰返し計算を実行する。この際、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８が、面素間角度のずれ、格子点間の距離のずれ、総合的なずれを評価する。面素配置部１５は、これらの評価において、ずれが所定範囲内に収まったときに、繰返し計算を終了し、そのときの格子点の位置を出力形状の格子点の位置とする。
【００５２】
ここで、面素配置部１５が、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７及び総合ずれコスト最小化部１８を用いて繰返し計算を行うことの必要性について説明する。
【００５３】
上述のように、マルコフ確率場から得られる情報は面素間角度値である。そこで、この面素間角度値がどの位置にあるものか、即ち、高さの情報を対応付ける必要がある。しかし、得られた面素間角度値をそのまま採用して高さを決めることは、必ずしも可能ではない。これは、例えば、紙のように伸縮性が低い素材を対象とした場合は、実現できない形状となり、現実の形状と乖離したデータとなるからである。
【００５４】
従って、マルコフ確率場からの角度は尊重しつつ、できるだけ伸縮が生じないように位置を決定することが必要である。本実施の形態では、少しの角度のずれと、少しの長さのずれを許容し、その代わり、角度と長さがそれぞれずれることによるデメリットをコストとして評価する。そして、これらのコストができるだけ小さくなるように位置を決定する。
【００５５】
まず、面素間角度ずれコストについて説明する。
格子点の位置が与えられた場合の面素間角度は、上述の式（１）、式（２）を用いて求めることができる。そこで、マルコフ確率場から求めた面素間角度をθ０ｊｋとすると、面素間角度ずれコスト計算部１６は、面素間角度ずれコストＣＡを式（８）で求める。
【数８】
【００５６】
続いて、長さずれコストについて説明する。
二つの格子点ｊ，ｋ間の距離ｌｊｋは式（９）で与えられる。
【数９】
【００５７】
ところで、格子点間の距離は元々は所定の長さｌ０であった。そこで、長さずれコスト計算部１７は、長さずれコストＣＬを式（１０）で求める。
【数１０】
【００５８】
次に、総合ずれコスト最小化部１８について説明する。
総合ずれコスト最小化部１８は、面素間角度ずれコスト計算部１６、長さずれコスト計算部１７を用いて面素の位置を決定する。
図１３は、総合ずれコスト最小化部１８の処理手順を示すフロー図である。
【００５９】
ステップＳ１１において、総合ずれコスト最小化部１８は、各格子点の初期値ｒ０ｉをｒｉに代入する。ステップＳ１２において、初期値に対応した面素間角度ずれコストＣ０Ａと当該面素間角度ずれコストＣ０Ａのｒｉでの微分値を求める。
【００６０】
ここで、微分値を求めるのは、総合ずれコスト最小化部１８が総合コストを最小化する際に必要となるからである。微分値は、式（８）の関数を直接微分して計算することもできるし、数値的に処理して微分することも可能である。数値的に処理する場合は、ｒｉを微小量δｒｉ変化させたときのＣＡの変化δＣＡを求めて、その商を計算すれば良い。
【００６１】
ステップＳ１３において、初期値に対応した長さずれコストＣ０Ｌと当該長さずれコストＣ０Ｌのｒｉでの微分値を求める。ここで、微分値を求めるのは、面素間角度ずれコストの場合と同様に、総合ずれコスト最小化部１８が総合コストを最小化する際に必要となるからである。なお、微分値は、上述と同様に、関数の微分あるいは数値処理いずれの方法でも計算できる。
【００６２】
ステップＳ１４において、総合ずれコストＣ０Ｔとその微分値を求める。これらは、ステップＳ１２及びステップＳ１３で求めたコスト及び微分値を加算して得られる。
以上の準備処理に続いて、総合ずれコストＣ０Ｔを評価値とする繰返し計算を実行する。
【００６３】
ステップＳ１５において、総合ずれコストＣ０Ｔを減少させるようなｒｉの変化分δｒｉを計算する。具体的には、微小量ｋ（＞０）を設定して、その符号を反転させた値（−ｋ）とステップＳ１４で求めた微分値とを積算した値を変化分δｒｉとする。そして、ステップＳ１６において、その変化分δｒｉを各格子点座標値ｒｉと加算した値を新たな格子点座標値ｒｉとする。
【００６４】
ステップＳ１７〜Ｓ１９において、新たな格子点座標値ｒｉを用いて、上述のステップＳ１２〜Ｓ１４と同様の手順で、新たな面素間角度ずれコスト、長さずれコスト、総合ずれコストとそれらの微分値とを求める。
【００６５】
ステップＳ２０において、計算が収束したかどうか判定する。具体的には総合ずれコストの変化Ｃ１Ｔ−Ｃ０Ｔを計算し、それが所定の閾値εよりも小さいか確かめる。もし小さければ、計算が収束したものとみなし、このときのｒ０ｉの値を最終的な格子点の座標値とする。
小さくない場合は、ステップＳ２１において、このときの格子点の座標値、総合ずれコスト、微分値を新たな初期値としてステップＳ１５からの処理を実行する。
【００６６】
以上の処理によって、最終的に出力形状として格子点の座標を得ることができる。
図１４は、出力形状のフォーマット例を示す図である。この出力形状は、出力形状データベース２４に格納され、あるいは入出力装置２に表示される。
【００６７】
なお、マルコフ確率場からはサンプリングにより面素間角度値の集合Θを一つまたは複数得ることができる。上述の実施の形態では、一組のサンプル値を用いたが、応用によっては複数組のサンプル値が必要になることもある。その場合はおのおのの組のサンプルに対して、面素配置部１５を用いて出力形状を作り出せば良い。
【００６８】
また、サンプルの格子サイズは、必ずしも実測形状を平面面素分割部１１で分割したときの格子サイズと同じでなくても良く、用途に対して適した格子サイズを指定することもできる。
【００６９】
[実施の形態の効果]
以上説明した実施の形態によれば、紙のしわなどのように、平面が折れ曲がってできる形状に関する統計的な分布モデルを得ることができる。この分布モデルを用いることにより、上述の形状を定量的に取り扱うことができる。これにより、上述の形状を画像処理に組み込むことが可能となる。例えば、分布モデルからサンプリングされた結果に基づいて生成された形状に関するデータを、公知の技術を利用して紙幣の画像に適用する。そして、得られたしわのある画像と基準となる画像とを比較することで紙幣の汚損の程度を評価することが可能となる。
【００７０】
このように、本実施の形態では一般に折れ曲がった平面の状態を定量的に取り扱うことができるため、折れ曲がった平面上に記録されている情報の劣化度の評価、あるいは情報の復元が可能となる。また、折れ曲がった平面による音、光、電磁波等の反射の効果の評価が可能になる。
【００７１】
なお、上述の実施の形態ではマルコフ確率場を用いているが、マルコフ確率場に限定されるものではない。
【００７２】
なお、上述の各実施の形態で説明した機能は、ハードウエアを用いて構成するに留まらず、ソフトウエアを用いて各機能を記載したプログラムをコンピュータに読み込ませて実現することもできる。また、各機能は、適宜ソフトウエア、ハードウエアのいずれかを選択して構成するものであっても良い。
【００７３】
尚、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。
上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００７４】
１…形状再現装置、２…入出力装置、１０…入出力制御部、１１…平面面素分割部、１２…面素間角度取得部、１３…確率場形成部、１４…サンプル部、１５…面素配置部、１６…面素間角度ずれコスト計算部、１７…長さずれコスト計算部、１８…総合ずれコスト最小化部、２０…データベース部、２１…実測形状データベース、２１…読込み実測形状データベース、２２…格子形状データベース、２３…近傍データベース、２４…出力形状データベース。
【特許請求の範囲】
【請求項１】
与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置であって、
前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部と、
隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部と、
面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部と、
この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部と、
サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部と
を備えたことを特徴とする平面形状再現装置。
【請求項２】
前記面素配置部は、
再現される平面形状の面素間角度とサンプリングにより得られた面素間角度とのずれを表す指数を計算する面素間角度ずれコスト計算部と、
再現される平面形状の面素の各辺の長さと所与の値とのずれを表す指数を計算する長さずれコスト計算部と、
この両指数の和が略最小となるように、再現される平面形状の面素の格子点を決定する総合ずれコスト最小化部と
を備えたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項３】
形状とサイズとで分類される格子の種類を保存する格子形状データベースを有し、
この格子形状データベースから、前記平面画素分割部が平面形状を画素に分割する際の格子の種類を指定できるようになされたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項４】
一つの面素間角度と相互作用を有する自己及び他の面素間角度とを対応付けて分類した近傍パターンを保存する近傍データベースを備え、
この近傍データベースより、前記確率場形成部が確率場を形成する際の近傍パターンを少なくとも一つ指定できるようになされたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項５】
与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成するプログラムであって、
前記平面形状を三角形の格子によって複数の領域である面素に分割するステップ、
隣接する二つの面素の成す角度である面素間角度を求めるステップ、
面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成するステップ、
この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするステップ、
サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現するステップ
をコンピュータに実行させるためのプログラム。
【請求項６】
面素で構成される平面形状を再現するステップは、
再現される平面形状の面素間角度とサンプリングにより得られた面素間角度とのずれを表す指数を計算するステップ、
再現される平面形状の面素の各辺の長さと所与の値とのずれを表す指数を計算するステップ、
この両指数の和が略最小となるように、再現される平面形状の面素の格子点を決定するステップ
を備えたことを特徴とする請求項５に記載のプログラム。
【請求項７】
形状とサイズとで分類される格子の種類を保存する格子形状データベースを検索して平面形状を画素に分割する際の格子の種類を指定するステップを更に備えたことを特徴とする請求項５に記載のプログラム。
【請求項８】
一つの面素間角度と相互作用を有する自己及び他の面素間角度とを対応付けて分類した近傍パターンを保存する近傍データベースを検索して、確率場を形成する際の近傍パターンを少なくとも一つ指定するステップを更に備えたことを特徴とする請求項５に記載のプログラム。
【請求項１】
与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成する平面形状再現装置であって、
前記平面形状を三角形の格子によって複数の領域である面素に分割する平面面素分割部と、
隣接する二つの面素の成す角度である面素間角度を求める面素間角度取得部と、
面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成する確率場形成部と、
この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするサンプル部と、
サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現する面素配置部と
を備えたことを特徴とする平面形状再現装置。
【請求項２】
前記面素配置部は、
再現される平面形状の面素間角度とサンプリングにより得られた面素間角度とのずれを表す指数を計算する面素間角度ずれコスト計算部と、
再現される平面形状の面素の各辺の長さと所与の値とのずれを表す指数を計算する長さずれコスト計算部と、
この両指数の和が略最小となるように、再現される平面形状の面素の格子点を決定する総合ずれコスト最小化部と
を備えたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項３】
形状とサイズとで分類される格子の種類を保存する格子形状データベースを有し、
この格子形状データベースから、前記平面画素分割部が平面形状を画素に分割する際の格子の種類を指定できるようになされたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項４】
一つの面素間角度と相互作用を有する自己及び他の面素間角度とを対応付けて分類した近傍パターンを保存する近傍データベースを備え、
この近傍データベースより、前記確率場形成部が確率場を形成する際の近傍パターンを少なくとも一つ指定できるようになされたことを特徴とする請求項１に記載の平面形状再現装置。
【請求項５】
与えられた平面形状を表すデータに基づいて当該平面形状の再現データを生成するプログラムであって、
前記平面形状を三角形の格子によって複数の領域である面素に分割するステップ、
隣接する二つの面素の成す角度である面素間角度を求めるステップ、
面素間角度の間の相互作用を定義して、面素間角度を変数とする確率場を形成するステップ、
この確率場において定義された確率分布を母集団として面素間角度の集合をサンプリングするステップ、
サンプリングにより得られた面素間角度に基づいて、面素で構成される平面形状を再現するステップ
をコンピュータに実行させるためのプログラム。
【請求項６】
面素で構成される平面形状を再現するステップは、
再現される平面形状の面素間角度とサンプリングにより得られた面素間角度とのずれを表す指数を計算するステップ、
再現される平面形状の面素の各辺の長さと所与の値とのずれを表す指数を計算するステップ、
この両指数の和が略最小となるように、再現される平面形状の面素の格子点を決定するステップ
を備えたことを特徴とする請求項５に記載のプログラム。
【請求項７】
形状とサイズとで分類される格子の種類を保存する格子形状データベースを検索して平面形状を画素に分割する際の格子の種類を指定するステップを更に備えたことを特徴とする請求項５に記載のプログラム。
【請求項８】
一つの面素間角度と相互作用を有する自己及び他の面素間角度とを対応付けて分類した近傍パターンを保存する近傍データベースを検索して、確率場を形成する際の近傍パターンを少なくとも一つ指定するステップを更に備えたことを特徴とする請求項５に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１２−４３３０１（Ｐ２０１２−４３３０１Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８５４８２（Ｐ２０１０−１８５４８２）
【出願日】平成２２年８月２０日（２０１０．８．２０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月２０日（２０１０．８．２０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]