(57)【要約】【課題】三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を短時間で探索することができる、閉領域同士の隣接面を探索する探索プログラム及び装置を提供する。【解決手段】三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索するプログラムは、閉領域の表面を規定する点群を隣接面毎に分割し、隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する第１ステップと、第１ステップで求めたヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、前記上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する第２ステップと、を含む。【選択図】図１
2015090696.tif 000002
【特許請求の範囲】
【請求項１】
三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索する探索プログラムであって、
閉領域の表面を規定する点群を隣接面毎に分割し、隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する第１ステップと、
前記第１ステップで求めたヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、前記上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する第２ステップと、
を含む、閉領域同士の隣接面を探索する探索プログラム。
【請求項２】
前記第２ステップで決定した隣接面により閉領域同士を接合して、隣接面の周りに在る別の面同士を再構築し、再構築した新たな面を規定する点群についてＤ２を適用して点ペアの距離を求め、再構築した新たな面の点群についてヒストグラムによって特徴量を表して再度データベース化する第３ステップを含み、
前記第２ステップでは、前記第１ステップ及び前記第３ステップで求めたヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、前記上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する、請求項１に記載の閉領域同士の隣接面を探索する探索プログラム。
【請求項３】
三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索する探索装置であって、
閉領域の表面を規定する点群を隣接面毎に分割する分割手段と、
前記分割手段により分割された隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する特徴量算出手段と、
隣接面毎の点群についてヒストグラムで表される特徴量を格納するデータベースと、
前記データベースに格納されている隣接面毎の点群に対して、任意の隣接面とマッチする隣接面候補を求め、上位Ｎ個を探索する上位Ｎ個探索手段と、
前記上位Ｎ個探索手段により探索した上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を、任意の隣接面に対応する隣接面として決定する隣接面決定手段と、
を有する、探索装置。
【請求項４】
さらに、前記隣接面決定手段により求めた隣接面の閉領域と探索対象の隣接面の閉領域とを接合すると共に、隣接面の周りに在る別の面同士を再構築する再構築手段と、
前記再構築手段によって再構築された新たな閉領域の表面を規定する点群についてＤ２を適用して点ペアの距離を求め、表面毎の点群についてヒストグラムによって特徴量を表してデータベース化し直す別の特徴量算出手段と、
を備える、請求項３に記載の探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、閉領域同士の隣接面を探索する探索プログラム及び装置に関する。
【背景技術】
【０００２】
本発明者らは、例えば、同一の石核から製作された石器同士を接合することにより、隣接する石器の位置や姿勢を復元することを鋭意研究している。計算機を用いて石器の剥離面を抽出し、剥離面同士のマッチングにより隣接する石器剥離面を検出してきた（非特許文献１及び２）。
【０００３】
非特許文献１に開示した検出方法では、先ず、対象となる剥離面の幾何形状がどの程度一致するかを、２つの面間の距離に基づいた評価式により算出し、その後、評価値が最小かつ閾値以下となる剥離面間のペアを選択して接合している。
【０００４】
対象となる剥離面を検出する際には、石器の計測により得られた３次元データ上で、剥離面となる閉領域を構成する境界稜線を抽出し、境界線をたどることによって剥離面を検出している。
【０００５】
そこで、非特許文献２では、剥離面の稜線抽出を行わずに、作成されている実測図から剥離面を直接抽出することで剥離面の抽出自動化を図っている。また、非特許文献２では、複数の石器を接合したあとで、分断されてしまった剥離面を検出し、剥離面を再構築し、複数の石器から再構築した剥離面をマッチングしている。
【０００６】
一方、マッチング速度を高速化するために、非特許文献３において、３次元モデルの形状特性を距離のヒストグラムで表現し、一次元情報に単純化することが提案されている。また、特許文献１では、３Ｄモデルから断面を生成し、断面に対して３次元モデルの形状特徴を距離のヒストグラムで表現することにより１次元情報に単純化し、高速に検索する手法であるＤ２を用いて、複数断面の隣接情報とＤ２による類似度を総合評価して形状の類似性を求める技術が提案されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００８−５２７４７３号公報
【非特許文献】
【０００８】
【非特許文献１】山原，今野，千葉，佐藤，" 接合資料作成のための石器剥離面に基づく隣接関係検出法"，日本情報考古学会誌，Vol．17，No.1・2，pp.23-32，(2011)
【非特許文献２】佐藤，松山，千葉，今野，" 石器接合のための複数の隣接剥離面の併合による剥離面再構築手法"，NICOGRAPH 2012，(2012)
【非特許文献３】R.Osada，T.Funkhouser，B.Chazelle，D.Dobkin，" Matching 3d models with shape distributions ", ACM TOG, Vol.21, No.4,pp. 807-832, (2002)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献１に開示した方法では、探索対象となる全ての石器剥離面に総当たりでマッチングを行うため、マッチングには時間がかかり、大量の石器に適用することは困難であるという課題がある。また、複数の石器剥離面が合併し、一つの剥離面を構成するような複雑な剥離面を探索することは難しい。
【００１０】
そこで、本発明では、三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を短時間で探索することができる、閉領域同士の隣接面を探索する探索プログラム及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
前記目的を達成するために、本発明に係る探索プログラムは次の構成を採用する。すなわち、三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索するプログラムであって、
閉領域の表面を規定する点群を隣接面毎に分割し、隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する第１ステップと、
前記第１ステップで求めたヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、前記上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する第２ステップと、
を含む。
【００１２】
前記プログラムにおいて、記第２ステップで決定した隣接面により閉領域同士を接合して、隣接面の周りに在る別の面同士を再構築し、再構築した新たな面を規定する点群についてＤ２を適用して点ペアの距離を求め、再構築した新たな面の点群についてヒストグラムによって特徴量を表して再度データベース化する第３ステップを含み、
前記第２ステップでは、前記第１ステップ及び前記第３ステップで求めたヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、前記上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する。
【００１３】
前記目的を達成するために、本発明に係る装置は次の構成を採用する。すなわち、三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索する探索装置であって、
閉領域の表面を規定する点群を隣接面毎に分割する分割手段と、
前記分割手段により分割された隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する特徴量算出手段と、
隣接面毎の点群についてヒストグラムで表される特徴量を格納するデータベースと、
前記データベースに格納されている隣接面毎の点群に対して、任意の隣接面とマッチする隣接面候補を求め、上位Ｎ個を探索する上位Ｎ個探索手段と、
前記上位Ｎ個探索手段により探索した上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を、任意の隣接面に対応する隣接面として決定する隣接面決定手段と、
を有する。
【００１４】
前記探索装置において、さらに、前記隣接面決定手段により求めた隣接面の閉領域と探索対象の隣接面の閉領域とを接合すると共に、隣接面の周りに在る別の面同士を再構築する再構築手段と、
前記再構築手段によって再構築された新たな閉領域の表面を規定する点群についてＤ２を適用して点ペアの距離を求め、表面毎の点群についてヒストグラムによって特徴量を表してデータベース化し直す別の特徴量算出手段と、
を備える。
【発明の効果】
【００１５】
本発明によれば、ヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する。よって、総当たりでマッチングがとれるかを確認する必要がないので、三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を短時間で探索することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態に係る探索方法の流れ図である。
【図２】図１に示す方法によってデータがどのように処理されるかを示す図である。
【図３】第１ステップを石器に適用した場合の具体的な流れを示す図である。
【図４】Ｄ２の適用を説明する図である。
【図５】Ｄ２の適用による処理について説明する図である。
【図６】図５に示す処理により求まるＤ２のヒストグラムの例を示す図である。
【図７】姿勢最適化を説明するための図である。
【図８】剥離面の再構築の様子を示す図である。
【図９】非特許文献１で示す探索方法の処理の一部を示す図である。
【図１０】本発明の実施形態に係る探索方法の処理の一部を示す図である。
【図１１】本発明の実施形態に係る探索装置の構成図である。
【図１２】ＡＡＤ（Absolute Angle Distance）による処理の流れを示す図である。
【発明を実施するための形態】
【００１７】
（探索プログラム及び探索方法）
以下、図面を参照しながら本発明の実施形態に係る、閉領域同士の隣接面を探索するプログラム（以下、「探索プログラム」と呼び、この「探索プログラム」の実行により為される方法を単に「探索方法」と呼ぶ。）を説明する。以下では、三次元の閉領域として石器を例にとって、石器を構成する多数の石片を接合するために、隣接する隣接面としての剥離面を探索することを前提に説明をする。
【００１８】
図１は、本発明の実施形態に係る探索方法の流れ図である。図２は、図１に示す方法によってデータがどのように処理されるかを示す図である。
対象物たる石器の接合箇所は、打撃により母岩から分離した面同士の形状が一致するか否かを繰り返すことで探索される。打撃により分離した面は剥離面と呼ばれ、剥離面の境界は稜線で構成される。稜線で囲まれた領域が一つの剥離面を表し、剥離面の内側は滑らかで曲率が小さい形状となる。
そこで、本発明の実施形態に係る探索方法の概略は次の通りである。計測点群から隣接面としての剥離面毎に分割し、探索対象となる剥離面と形状が一致する別の対象物（ここでは、別の石器）の隣接面としての剥離面を探索する。その後、形状が一致した２つの隣接面としての剥離面を接合して一つにまとめて再構築する。その際、隣接面としての剥離面が新たな探索対象となる。
【００１９】
第１ステップ：閉領域の表面を規定する点群を隣接面毎に分割し、隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、一次元ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース化する。
第２ステップ：第１ステップ及び第３ステップの何れか一方又は双方で求めた一次元ヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補を上位Ｎ個探索し、上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する。
第３ステップ：第２ステップにより決定した隣接面により閉領域同士を接合して、隣接面の周りに在る別の面同士を再構築し、再構築した新たな面を規定する点群についてＤ２を適用して点ペアの距離を求めて、再構築した新たな面の点群について一次元ヒストグラムによって特徴量を表して再度データベース化する。
【００２０】
石器の場合を例にとって概略説明すると、第１ステップがステップ１−１〜ステップ１−２、第２ステップがステップ２−１〜ステップ２−２、第３ステップがステップ３として次のように分説される。
ステップ１−１：石器を計測し、計測点群を取得しておく。
ステップ１−２：剥離面毎に点群を分割する。
ステップ１−３：剥離面を示す点群にＤ２を適用し、得られた特徴量をデータベースに登録する。
ステップ２−１：探索対象たる剥離面とマッチする剥離面候補をデータベースから選出する。
ステップ２−２：姿勢最適化を行い、正規化距離を計算する。
ステップ２−３：正規化距離が閾値以下かつ最小ものを剥離面とし、正規化距離が閾値より大きい場合にはステップ２−１に戻る。
ステップ３：探索対象の剥離面と探索結果の剥離面とを接合し、隣接した２つの石器とみなし、新たに特徴量を求める。
【００２１】
以下、具体的に石器の場合を例に挙げながら説明する。図３は、第１ステップを石器に適用した場合の具体的な流れを示す図である。
ステップ１−１では、対象物としての石器にレーザー光を照射して対象物の表面を覆う点群を測定し、記憶しておく。
【００２２】
ステップ１−２では、隣接面としての剥離面毎に点群を分割する。その際、ステップ１−１で測定し又は記憶しておいた点群を剥離面毎に分割するために、剥離面の境界となる稜線を抽出した後、稜線で囲まれる閉領域に属する点群を抽出し、同一の色属性を付加する。ただし、剥離面の面積が小さい領域については、マッチングの誤りをもたらすため、剥離面としての抽出は行わない。具体的には次の通りである。
【００２３】
剥離面の境界となる稜線近傍は曲率が大きく、剥離面の内側は曲率が小さい。そのため、計測点群の軽量化処理を適用すると、稜線近傍では点密度が高く、剥離面の内側近傍では点密度が低くなる（図３（ａ）参照）。そこで、各点とその点のＫ近傍点との距離を計算し、或る点と最も近い点との距離が閾値以下の場合にはその或る点を稜線上の点と判断する一方、或る点と最も近い点との距離が閾値以上の場合ではその或る点を剥離面の内側の点と判断する。このようにして、ステップ１−１で求めた点群のうちから剥離面の稜線上の点群だけを抽出する。この状態を示したのが図３（ｂ）である。
【００２４】
次に、稜線上の点群から作成したイラスト図に対し、閉領域毎に異なる色を付し、計測点群をイラスト図へ正射影することにより、イラスト図に描かれている色属性を各点に転写する。転写の具体的な手順は次の通りである。第１手順として、図３（ｃ）に模式的に示すように、閉領域毎に色を付したイラスト図に対してイラスト図と同じ姿勢の計測点群を重ね合わせ、各点をイラスト図に正射影することにより、点とイラスト図の閉領域に対応関係を付ける。第２手順として、図３（ｄ）に示すように、イラスト図上からＲＧＢ情報を取得し、色属性情報を点に付加する。
【００２５】
ステップ１−３では、隣接面としての剥離面を示す点群にＤ２を適用し、得られた特徴量をデータベースに登録する。分散された点群毎に、形状特徴を算出する。Ｄ２を用いて特徴量を算出し、特徴量に基づいてマッチング候補を絞り込む。ここで、Ｄ２を適用するとは、三次元モデルの面上にランダムに点を生成し、その点の中からランダムに選ばれた２点間の距離のヒストグラムを特徴ベクトルとすることである。
【００２６】
以下、Ｄ２の適用について詳細に説明する。図４はＤ２の適用を説明する図であり、図５はＤ２の適用による処理について説明する図である。図４に示すように、或る三角形上に点Ｐを生成するには、モデルの頂点の連続性により構成される三角形の頂点座標Ａ，Ｂ，Ｃから式（１）を用いて行う。
Ｐ＝（１−√ｒ1）Ａ＋√ｒ1（１−ｒ2）Ｂ＋√ｒ1（ｒ2Ｃ）      （１）
なお、ｒ1，ｒ2は、０から１までの値をとり得る準乱数である。
生成された点の中から任意の２点Ｐ1，Ｐ2を選び、次式により距離を求める。
Ｄ２（Ｐ1，Ｐ2）＝｜Ｐ1−Ｐ2｜
生成された点の全ての組み合わせに対しＤ２を適用することにより、１次元の数値群を生成する。
生成された数値群を基にして距離ヒストグラムを生成するために、まず最大値を小数点第一位で切り上げた整数を求める。つぎに、０から切り上げた整数までのＮ＋１区間に対して、距離ヒストグラムを生成する。
例えば、図５（ａ）に示すように石器をモデルにしたとき、図５（ｂ）に示すように点群が表現され、図５（ｃ）のように、特徴量が、全ての頂点のペア間の距離に基づいて算出されて、ヒストグラムにより表される。よって、剥離面を示す点群にＤ２を適用し、得られた特徴量がデータベースに登録される。図６はこのようにして求まるＤ２のヒストグラムの例を示す図である。なお、Ｄ２とは形状分布関数の一種である。
【００２７】
ステップ２−１：探索対象である隣接面（ここでは剥離面）とマッチする隣接面候補（ここでは剥離面候補）をデータベースから選出する。すなわち、データベースに登録した特徴量と検索対象の剥離面上の点群から計算した特徴量とを、マンハッタン距離により比較することで、マッチング候補となる隣接面としての剥離面を探索し、距離の短い上位Ｎ個の剥離面をマッチング候補として算出する。
【００２８】
以下、さらに具体的に説明する。点群の特徴量を示す一次元ヒストグラムは、その形が類似していれば、点群の形状が類似しているとみなされる。よって、分割された点群から生成した特徴量がデータベースに格納されているので、データベース内の特徴量と検索対象の剥離面を示す点群から算出した特徴量を比較すれば、点群形状がどの程度類似しているかを決定することができる。点群形状の類似度は、マンハッタン距離により測ることができる。
【００２９】
いま、特徴量Ｘと特徴量Ｙがあるとき、マンハッタン距離Ｄ（Ｘ，Ｙ）は、式（２）から計算される。
【数１】
2015090696.tif 000003
ここで、ｘi，ｙiはヒストグラムの各区間におけるペア数を示す。
このようにマンハッタン距離は２つのヒストグラムの面積差を表し、ヒストグラムが類似していればマンハッタン距離が短くなり、逆にヒストグラムが類似していなければマンハッタン距離が長くなる。よって、形状が類似していればマンハッタン距離を表す数値は小さくなり、逆に形状が類似していなければマンハッタン距離を示す数値は大きくなる。
【００３０】
そこで、本発明の実施形態では、マンハッタン距離を示す数値が小さい、すなわちマンハッタン距離の短い上位Ｎ個の剥離面をマッチング候補として選出する。このように、マンハッタン距離を示す数値が小さい上位Ｎ個に対してのみ、正規化を行い、マッチングにかかる計算コストの削減を行う。
【００３１】
ステップ２−２：姿勢最適化を行い、正規化距離を計算する。すなわち、マッチング候補から最も適切な剥離面を算出するときには、Ｎ個のマッチング候補となる剥離面に対して姿勢最適化手法を適用し、正規化距離を算出する。そして、正規化距離が最小かつ閾値以下の剥離面を最適な隣接剥離面として算出する。
【００３２】
本発明の実施形態においては、ステップ２−１で選定したマッチング候補は、Ｄ２による類似度の高い形状であるわけである。さらにより高次元の評価を行うために、そのマッチング候補が幾何学的に形状一致するかどうかを評価する。そのため、姿勢最適化と正規化距離の計算を行う。
【００３３】
先ず、姿勢最適化について説明する。図７は、姿勢最適化を説明するための図である。２つの領域が一致しているか否かを定量的に判断するために、初期位置が決定された対象領域の空間姿勢を最適化する。具体的には，領域Ａに含まれる全ての頂点が、領域Ｂ上にのるような空間姿勢を算出する。姿勢の最適化を図るために、領域Ａの頂点が領域Ｂとの距離の二乗和が最小となる姿勢を最適解とする。説明上、領域の面積が小さい領域をＡとし、他方の領域をＢとする。
【００３４】
姿勢最適化は次のように行う。
第１手順：領域Ａ上の頂点Ｖiを領域Ｂ上の各面に射影し、射影した頂点がその面の内側に存在する場合、その面をペア候補とする。全ての候補に対して、領域Ａ上の頂点と、候補面の重心ｇiの距離ｄiが最小となる面をペアとする。
頂点Ｖiと候補面の距離ｄiは次式で算出される。ただし、ｎiは候補面の単位法線ベクトルである。
【数２】
2015090696.tif 000004
第２手順：領域Ａ上の全ての頂点と面ペアに対して算出した距離の合計値Ｄが最小となる条件の下で、最適な姿勢を決定する。
【数３】
2015090696.tif 000005
このようにして合計値Ｄが最小となるように、領域Ａの頂点を座標変換する変換行列を求める。座標変換後の頂点Ｖi’は式（５）で求まる。
【数４】
2015090696.tif 000006
ただし、Ｖi’は、領域Ａの移動後の頂点座標であり、Ｍは４×４の変換行列である。
行列Ｍの要素は、ＸＹＺ各軸の回転角θx，θy，θzと、平行移動量Ｔx，Ｔy，Ｔzから成る多項式である。これらの値を未知数として、最小二乗法を用いて式（４）を解くことにより、誤差が最小となる変換行列を求める。
【００３５】
次に、Ｎ個のマッチング候補となる剥離面に対し、検索対象となる隣接面としての剥離面との正規化距離を算出することについて説明する。
正規化距離は、剥離面同士が幾何学的にどの程度一致するかを示す値である。正規化距離が短かければ剥離面同士の形状が一致し、正規化距離が長ければ剥離面同士の形状は一致しない。正規化距離は、上述の式（４）の合計値Ｄの最小値を領域Ａの面積で割って求める。式（４）によって導出される評価値は、面積が大きい領域ほど大きな値となり、値の大小によって最適な領域を評価することができないからである。
さらに、剥離面同士が一致する場合には、正規化距離は或る一定の値よりも小さくなることが既に本発明者らにより明らかにされている（非特許文献１）。
そこで、本発明の実施形態にあっては、正規化距離が最小かつ閾値以下の剥離面を最適な面として選出する。
正規化距離の算出は、計算コストが高いため、マッチング候補をＮ個に絞り込むことにより大幅に計算コストを削減でき、高速化が実現される。
【００３６】
ステップ２−３：正規化距離が閾値以下かつ最小の隣接面としての剥離面を選び、正規化距離が閾値より大きい場合にはステップ２−１に戻る。このようにして、候補となる剥離面から適切な石器の石片を選択し、実際に接合する。
【００３７】
上述の各ステップを順に行うことにより、検索対象となる隣接面としての剥離面を探索することができる。さらに、求めた探索対象の隣接面（石器の場合には剥離面）と探索結果である隣接面（石器の場合には剥離面）とを接合することができる。よって、検索対象の隣接面と検索結果の隣接面とを合わせ、接合面の周りにある、隣接面同士を併合してひとつの閉領域を再構成し、その新しい閉領域に対する特徴量を求めてデータベース化する（図１のステップ３）。
【００３８】
図１のステップ３について石器に適用した場合を具体的に説明すると、図８は剥離面の再構築の様子を示す図である。剥離面Ａと剥離面Ｂが隣接関係にある三次元モデルとしての石器モデルである。第１モデルと第２モデルにおいて、接合される剥離面を接合面と呼ぶ。二重丸で示す点は剥離面の境界稜線の角となる点を示す。さらに、接合面に隣接する第１モデルの剥離面を剥離面Ａ，Ｃで示す。同様に、第２モデルの剥離面を剥離面Ｂ，Ｄとする。剥離面Ａと剥離面Ｂとが本来一つの剥離面であり分断されたと仮定し、剥離面Ｃと剥離面Ｄとが本来一つの剥離面であり分断されたと仮定する。
【００３９】
このような三次元モデルにおいて、本発明の実施形態に係る再構築の手法を次のように適用する（図１のステップ３）。
第１手順：分断された剥離面の境界線において、接合面を含む３つ以上の剥離面が共有する頂点（図の二重丸の点）の探索を行う。
第２手順：同一剥離面候補の評価及び剥離面の再構築を行う。すなわち、剥離面Ａと剥離面Ｂとが一つの剥離面を構成する場合には、剥離面Ａと剥離面Ｂとが接合される境界線はマッチングした時点で一致する。また、剥離面Ａ及び剥離面Ｂは本来一つの剥離面であったものが分断された形状であるため、剥離面Ａと剥離面Ｂとは滑らかな形状となるはずである。そこで、先ず、剥離面Ａの境界上の頂点と、剥離面Ｂの境界上の頂点との距離が閾値以下となる頂点ペアを求める。次に、各頂点を共有するポリゴンの法線ベクトルの平均を求め、各頂点における平均法線ベクトルの角度が閾値内で一致している場合には、剥離面Ａと剥離面Ｂとは同一剥離面とみなすことにする。剥離面Ａの頂点Ａ１と剥離面Ｂの頂点Ｂ１、剥離面Ａの頂点Ａ２と剥離面Ｂの頂点Ｂ２をそれぞれ端点とする共有境界稜線の両側の剥離面を一つの剥離面となるようにデータを統合することにより、剥離面の再構築を行う。
【００４０】
以上により剥離面が再構築された２つのモデルが１つのモデルに統合され、再構築された剥離面に対して、前述のように、特徴量を算出し直す。すなわち、新たに検出した剥離面から再び剥離面上の点群を抽出し、特徴量の計算を行う。
【００４１】
（計算時間の評価）
発明の実施形態に係る探索方法によりどの程度高速化処理することができるかについて、石器の場合を例にとって説明する。図９は非特許文献１で示す探索方法の処理の一部を示す図であり、図１０は本発明の実施形態に係る探索方法の処理の一部を示す図である。いま、データベースには、ｍ個の剥離面が格納されていると仮定する。
【００４２】
図１０に示す非特許文献１による探索方法では総当りでマッチングを行うため、全ての剥離面と比較し、正規化距離を計算する必要がある。そのため、正規化距離をｍ回計算しなければならない。
【００４３】
一方、本発明の実施形態に係る探索方法では、あらかじめ特徴量を計算し、類似度が高い上位Ｎ個の剥離面に対してのみ正規化距離を計算する。
いま、１回の正規化距離の計算時間をｔ1とし、特徴量の計算時間をｔ2とし、マッチング候補探索時間をｔ3とする。
非特許文献１による探索方法の計算時間はｍｔ1であり、本発明の実施形態に係る探索方法の計算時間はｍ（ｔ2＋ｔ3）＋Ｎｔ1である。
ここで、ｍ≫Ｎと仮定して、計算時間同士を比較する。
ｍｔ1−｛ｍ（ｔ2＋ｔ3）＋Ｎｔ1｝＝（ｍ−Ｎ）ｔ1−ｍ（ｔ2＋ｔ3）
≒ｍ｛ｔ1−（ｔ2＋ｔ3）｝
なお、ｍ−Ｎ≒ｍと近似した。
ｔ1−（ｔ2＋ｔ3）は、ひとつの剥離面に対する計算時間の差分である。この差分の値が正になれば、非特許文献１の方法と比較することにより高速化処理できるか否かが判断される。
次に、マッチング候補の数Ｎの値によりどの程度高速化できるかを検討する。非特許文献１と比較して本発明の実施形態に係る探索方法がｋ倍高速であると仮定すると、次式が導出される。
ｔ1＝ｋ（ｔ2＋ｔ3）
ｋ＞１であれば、次式が導出される。
Ｎ＜ｍ（ｋ−１）／ｋ
以上のことから、この式が成り立つように、Ｎを小さな値に設定すれば、本発明の実施形態に係る探索方法により高速化を実現できる。
【００４４】
（探索装置）
本発明の実施形態に係る、閉領域同士の隣接面を探索する装置（以下、「探索装置」と呼ぶ。）について説明する。探索装置１は、三次元の複数の閉領域のうち隣接する閉領域同士の隣接面を探索するものである。図１１は、本発明の実施形態に係る探索装置の構成図である。探索装置１は、本発明の実施形態に係る探索プログラムを、入力手段２、出力手段３、記憶手段４及び演算制御手段５を有するコンピュータの記憶手段４に格納しておき、探索プログラムを演算制御手段に読み取らせて実行させることにより、実現することができる。このために、演算制御手段５は、分割手段１１と第１特徴量算出手段１２と上位Ｎ個探索手段１３と隣接面決定手段１４と再構築手段１５と第２特徴量算出手段１６とを備える。なお、探索装置１は、データ処理してデータベース化をするので、データベース６を備えている。
【００４５】
分割手段１１は、ステップ１−２において実行され、計測により取得した点群に対して、閉領域の表面を規定する点群を隣接面毎に分割する。
【００４６】
第１特徴量算出手段１２は、ステップ１−３において実行され、分割手段１１により分割された隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、一次元ヒストグラムによって隣接面毎の点群についての特徴量を表し、データベース６に登録してデータベース化する。
【００４７】
上位Ｎ個探索手段１３は、ステップ２において実行され、データベース６に格納されている隣接面毎の点群に対して、任意の隣接面とマッチする隣接面候補を求め、上位Ｎ個を探索する。
【００４８】
隣接面決定手段１４は、ステップ２において実行され、上位Ｎ個探索手段１３により探索した上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を、任意の隣接面に対応する隣接面として決定する。
【００４９】
再構築手段１５は、ステップ３において実行され、隣接面決定手段１４により求めた隣接面の閉領域と探索対象の隣接面の閉領域とを接合すると共に、隣接面の周りに在る別の面同士を再構築する。
【００５０】
第２特徴量算出手段１６は、ステップ３において実行され、再構築手段１５によって再構築された新たな閉領域の表面を規定する点群についてＤ２を適用して点ペアの距離を求め、表面毎の点群について一次元ヒストグラムによって特徴量を表し、データベース６に登録してデータベース化し直す。
【００５１】
データベース６は、第１特徴量算出手段１２及び第２特徴量算出手段１６によって求められる、隣接面毎の点群について一次元ヒストグラムで表される特徴量を格納する。
【００５２】
探索装置１では、前述した探索方法のように、先ず、第１特徴量算出手段１２によって隣接面毎の点群についてＤ２を適用して点ペアの距離を求め、一次元ヒストグラムによって隣接面毎の点群についての特徴量を表してデータベース６に登録しておく。そして、上位Ｎ個探索手段１３によって、一次元ヒストグラムによる類似性により任意の隣接面とマッチングする隣接面候補として上位Ｎ個を探索する。よって、全てを総当たりに探索しないので計算コストが大幅に減少する。
【００５３】
さらに、隣接面決定手段１５によって、上位Ｎ個の隣接面候補のうち幾何学的に一致の度合いが高い隣接面を隣接面として決定する。よって、形状の不一致などの不都合が発生しない。
【００５４】
以上、石器の剥離面にマッチした他の石器の剥離面を探索することを前提としながら、本発明の実施形態を説明したが、石器以外に、金型とそれに対応する製品とのマッチングをとるといったモノづくり作業工程のオートメーション化での各種部品のマッチングなどにおいても適用することができる。
【００５５】
本発明の実施形態は上述に限らず種々変更することができる。例えば、前述したＤ２を適用したあと、面の向きの情報を加えた二次元ヒストグラムとしてデータベース化してもよい。これにより求まるＡＤＤ（Absolute Angle Distance）は内積と距離に基づく形状分布関数である。図１２は、ＡＡＤによる処理の流れを示す図である。
【００５６】
先ず、面の情報を加えるために点群表現の各点に法線ベクトルを付加する。次に、全ての２点間で直線距離と単位法線ベクトルの内積の絶対値を求める。 横軸が距離軸(区間数Ｎｄ)、縦軸が内積軸（区間数Ｎａ）として得られるＮｄ×Ｎａの二次元ヒストグラムがＡＡＤである。検索するモデルには、面の向きについての情報が付されていないモデルや、ポリゴンスープモデルと呼ばれる非連結な多角形の集合から構成されるモデルが含まれる場合が想定される。このようなモデルの場合、内積を用いると検索精度が悪化する場合がありうる。そのため、ＡＡＤでは内積の絶対値をとることで面の裏表を無視することができる。類似度の計算にはユークリッド距離を用いる。モデルＸ、Ｙから求めた特徴量をｘ＝ （ｘi,j），ｙ＝（ｙi,j）とすると、ＸＹのマンハッタン距離として式（６）を用いればよい。
【数５】
2015090696.tif 000007
【符号の説明】
【００５７】
１：探索装置
２：入力手段
３：出力手段
４：記憶手段
５：演算制御手段
６：データベース
１１：分割手段
１２：第１特徴量算出手段
１３：上位Ｎ個探索手段
１４：隣接面決定手段
１５：再構築手段
１６：第２特徴量算出手段
【図１】
2015090696.tif 000008
【図２】
2015090696.tif 000009
【図６】
2015090696.tif 000010
【図７】
2015090696.tif 000011
【図８】
2015090696.tif 000012
【図９】
2015090696.tif 000013
【図１０】
2015090696.tif 000014
【図１１】
2015090696.tif 000015
【図３】
2015090696.tif 000016
【図４】
2015090696.tif 000017
【図５】
2015090696.tif 000018
【図１２】
2015090696.tif 000019