(57)【要約】【課題】手書き画像を検索質問とする高精度な三次元形状検索システムを提供すること【解決手段】本発明に係る三次元形状検索システムは、三次元形状データベースに格納されている三次元物体モデルごとに生成するエッジ画像の特徴量に重みが掛け合わされ、該重みが掛け合わされたエッジ画像の特徴量の線形和として近似して構成される画像特徴量を抽出する手段と、三次元物体モデル同士の類似関係が反映されるk-近傍グラフ上で接続がある三次元物体モデルの重みを算出する手段と、過学習を避けるために前記重みに対しL2正規化を行う手段と、前記重みを類似度として該類似度が最小となる重みを算出する手段と、を備え、前記類似度の値に応じて並び替えることで検索を行うことを特徴とする。【選択図】図２
2018147262.tif 000002
【特許請求の範囲】
【請求項１】
三次元形状データベースを検索対象とし、検索質問として用いる手書き画像における画像特徴量であって、
該画像特徴量が、三次元形状データベースに格納されている三次元物体モデルごとに生成するエッジ画像の特徴量に重みが掛け合わされ、該重みが掛け合わされたエッジ画像の特徴量の線形和として近似して構成されることを特徴とする画像特徴量。
【請求項２】
三次元形状データベースを検索対象とし、検索質問として手書き画像を用いる三次元形状検索システムであって、
請求項１に記載の画像特徴量を抽出する手段と、
三次元物体モデル同士の類似関係が反映されるk-近傍グラフ上で接続がある三次元物体モデルの重みを算出する手段と、
過学習を避けるために前記重みに対しL2正規化を行う手段と、
前記重みを類似度として該類似度が最小となる重みを算出する手段と、を備え、
前記類似度の値に応じて並び替えることで検索を行うことを特徴とする三次元形状検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像から特徴量を求め、それを用いて類似した形状の三次元物体モデルを検索するシステムに関する。とくに、スケッチ等の手書き画像から三次元物体モデルを検索するための特徴量を求める方法に関するものである。
【背景技術】
【０００２】
CAD/CAM(Computer-Aided Design / Computer-Aided Manufacturing)において、機械部品モデルのスケッチ等の手書き画像による直感的な検索が求められており、いくつかの従来技術が提案されている。手書き画像からの三次元物体モデルの検索方法に関する従来技術としては、１）立間らの三次元物体モデルの深度バッファを用いる方法（例えば、特許文献１を参照）や、２）Sangらの手法（例えば、非特許文献１を参照）、さらに、３）立間らのOPHOG法（例えば、非特許文献２を参照）がある。
【０００３】
１）に示されている、二次元スケッチ画像を検索質問とする三次元モデルの検索システムでは、三次元物体モデルの深度バッファ画像を処理して、該三次元物体モデルを二次元に投影した画像と比較によりヒストグラムに関する特徴量を算出し、検索結果の順位を得ている。
【０００４】
また、２）Sangらの手法では、スケッチ等の手書き画像と三次元物体モデルから生成した輪郭線画像からHOG-DTF (Histogram of Oriented Gradients - Diffusion Tensor Fields)特徴を抽出し、該特徴量を、輪郭線画像から抽出した別の特徴量で構成される基底を用いてスパースコーディングにより再構成する。その再構成によって求められた重みを類似度として用い、三次元物体モデルの検索を行うものである。Sangらの手法では、手書き画像の特徴量の再構成、つまり、重み付き線形和による近似、にスパースコーディングを用いているため、検索対象や特徴量の次元数が増加すると、スパースコーディングによる重みの計算が負荷となり、実行速度を低下させるという課題がある。
【０００５】
最後に、３）OPHOG法では、まず、三次元物体モデルに対して複数視点からエッジ画像を生成する。その後、手書き画像とエッジ画像を重複したセルと呼ばれる小領域に分割する。次に、作成された小領域ごとにHOG (Histogram of Oriented Gradients)特徴量を抽出する。最後に、手書き画像とエッジ画像間でユークリッド距離を類似度として三次元物体モデルの検索を行うものである。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開2015-201151号公報
【非特許文献】
【０００７】
【非特許文献１】Yoon, Sang Min, Gang-Joon Yoon, and Tobias Schreck. “User-drawn sketch-based 3D object retrievalusing sparse coding.” Multimedia Tools and Applications, 74.13 (2015): 4707-4722.
【非特許文献２】Li, Bo, et al. "A comparison of 3D shape retrieval methods based on a large-scale benchmark supporting multimodal queries." Computer Vision and Image Understanding 131 (2015): 1-27.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来のスケッチ等の手書き画像から三次元物体モデルの検索方法及び三次元形状検索システムでは、三次元物体モデルを二次元に投影した画像との類似度をもとに検索を行うため、三次元物体モデルの三次元構造が考慮されず、該三次元物体モデルの全体的な形状は無視されることになる。したがって、検索者が所望する、検索対象の三次元物体モデルと類似する形状を持つ三次元物体モデルであっても、手書き画像からの従来の特徴抽出では、該画像の特徴を十分に捉えられておらず、検索精度が低くなり、よって、検索結果一覧の上位に現れず、簡便に検索結果が得られないという課題があった。
【０００９】
本発明が解決しようとする課題は、上記の先行技術の課題を鑑みて成されたものであり、スケッチ等の手書き画像（以下、単にスケッチ画像ということがある。）の新たな特徴量を定義し、該特徴量を求めることにより、従来技術と比べて、より高い精度で手書き画像を検索質問（以下、検索クエリということがある。）とする三次元形状検索システムを提供することである。
【課題を解決するための手段】
【００１０】
本発明に係る画像特徴量は、三次元形状データベースを検索対象とし、検索質問として用いる手書き画像における画像特徴量であって、
該画像特徴量が、三次元形状データベースに格納されている三次元物体モデルごとに生成するエッジ画像の特徴量に重みが掛け合わされ、該重みが掛け合わされた特徴量の線形和として近似して構成されることを特徴とする。
【００１１】
本発明に係る三次元形状検索システムは、三次元形状データベースを検索対象とし、検索質問として手書き画像を用いる三次元形状検索システムであって、
請求項１に記載の画像特徴量を抽出する手段と、
三次元物体モデル同士の類似関係が反映されるk-近傍グラフ上で接続がある三次元物体モデルの重みを算出する手段と、
過学習を避けるために前記重みに対しL2正規化を行う手段と、
前記重みを類似度として該類似度が最小となる重みを算出する手段と、を備え、
前記類似度の値に応じて並び替えることで検索を行うことを特徴とする。
【発明の効果】
【００１２】
本発明に係る手書き画像の画像特徴量及びそれを用いる三次元形状検索システムによって、検索対象である三次元物体モデルの形状を考慮して高い精度で、手書き画像から三次元物体モデルの検索を行うことができ、所望の三次元物体モデルを検索結果一覧の上位に提示することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明に係る線形和の近似による画像特徴量の再構成を説明する概念図である。
【図２】本発明に係る三次元形状検索に関する処理フローの概要を示す模式図である。
【図３】本発明に係る画像特徴量及びそれを用いる三次元形状検索システムによる検索結果(Precision-Recall曲線)を示すグラフである。
【発明を実施するための形態】
【００１４】
本発明に係る画像特徴量及び三次元形状検索システムは、演算装置、メモリ、外部記憶装置、表示装置及び入力機器が電気的に接続されている計算機のハードウェアを適宜、制御してなり、C言語などのプログラミング言語を用いて構築され、実行される。
【００１５】
本発明では、検索質問であるスケッチ等の手書き画像から抽出した画像特徴量を、検索対象である三次元物体モデルから生成したエッジ画像の特徴量の重み付き線形和で近似して再構成し、その重みを類似度とすることで前記特徴量の再構成誤差に基づく検索を行う。
【００１６】
スケッチ等の手書き画像から三次元物体モデルを検索するための方法の一つとして、三次元物体モデルから複数視点よりエッジ画像を生成し、該エッジ画像及び手書き画像に対して同様の特徴抽出処理を行い、抽出した特徴量同士の距離を計算して昇順に並び替えることによって検索結果を得る方法がある。
【００１７】
前記方法による検索では、手書き画像に類似した三次元物体モデルが得られるが、三次元物体モデルを二次元に投影した画像をもとに検索を行うため、三次元物体モデルの三次元構造が考慮されず、該モデルの全体的な形状は無視されることになる。
【００１８】
また、前記のスケッチ等の手書き画像から三次元物体モデルを検索する手法として、スパースコーディングの概念を用いて、該手書き画像の特徴量を、三次元物体モデルから生成したエッジ画像の特徴量で再構成することを考え、その際に求められる重みを類似度とすることで検索精度を向上させる手法がある。
【００１９】
本発明では、前記手法と異なり、スケッチ等の手書き画像から抽出した特徴量を、三次元物体モデルから生成したエッジ画像の特徴量に対して重みが掛け合わされた特徴量の線形和（以下、重み付き線形和ということがある）で近似し、その際の重みを類似度とすることで、検索精度の向上を実現する（図１）。その際、三次元物体モデル同士の類似度から近傍グラフを作成し、近傍同士が似た重みを持つように正則化項を追加し、三次元物体モデル同士の類似関係を反映させる。
【００２０】
図２は、本発明に係る三次元形状検索に関する処理フローの概要を示したものである。本発明では、手書き画像から抽出した特徴量を、三次元物体モデルから生成したエッジ画像から抽出した特徴量で重み付き線形和により近似して再構成誤差を算出して検索を行う。
【００２１】
前記重み付き線形和の計算は、前記手書き画像の特徴量と重みを加えた前記エッジ画像との二乗誤差（以下、再構成誤差ということがある）を最小化することで実現される。このとき、前記重みの過学習を防ぐためにL2正則化項を追加する。
【００２２】
さらに、三次元物体モデルの形状特徴量を、生成した前記エッジ画像の特徴量とは別に抽出し、該形状特徴量の類似度から作成した近傍グラフの隣接行列を考慮した正則化項を追加する。
【００２３】
そして、前記正則化項付きの再構成誤差を最小化した時に得られる重みを類似度として検索を行う。
【００２４】
本発明ではまず、前記エッジ画像と、検索質問として与えられた前記手書き画像からOPHOG法によって画像特徴量の抽出を行い、該手書き画像から特徴量q、n個の三次元物体モデル{Mi}ni=1からp枚ずつ生成した画像から特徴量{mij}n,pi=1,j=1を得る。
【００２５】
そして、前記特徴量qと、前記特徴量{mij}n,pi=1,j=1間でユークリッド距離の計算をすることで、三次元物体モデルごとに手書き画像の特徴量qの最近傍となる画像特徴量を割り出し、それらを並べた行列Xを作成する。
【００２６】
【数１】
2018147262.tif 000003
2018147262.tif 000004
【００２７】
次に、各三次元物体モデルから、画像特徴量とは別に、MRLBP法（例えば、真田ら，“多重スケール表現の Local Binary Pattern による 三次元物体の形状類似検索”電子情報 通信学会総合大会講演論文集, vol.2014, No.86, 2014を参照）により形状特徴量Y={y1,・・・,yn}を抽出する。
【００２８】
そして、形状特徴量Yのそれぞれの要素同士のユークリッド距離を計算し、その距離関係からk-近傍グラフを作成する。そこから三次元物体モデル同士の類似関係を表す隣接行列Aを作成する。Aの要素は、三次元物体モデル同士が隣接している場合は1、そうでない場合は0と表す。
【００２９】
【数２】
2018147262.tif 000005
【００３０】
その後、数３に示す正則化項付きの再構成誤差の最小化を行う。そして、その際に得られる重みW={w1,・・・,wn}Tを手書き画像に対する各三次元物体の類似度とする。そのとき、目的関数Ｊは、数３で表される。
【００３１】
【数３】
2018147262.tif 000006
【００３２】
数３において、第一項は、手書き画像から得られた特徴量を三次元物体モデルから得られた特徴量の重み付き線形和で再構成をすることを示す。前記重みの値は、手書き画像の特徴量に類似した特徴量を持つ三次元物体モデルであるほど大きくなる。
【００３３】
第二項は、三次元物体モデル同士の類似関係を重みに反映することを示す。k-近傍グラフ上で接続がある三次元物体モデルの重み同士が、類似した値となる。
【００３４】
第三項は、過学習を避けるために一般的に用いられるL2正規化項である。
【００３５】
数３を最小化する最適な重みWを求めるために、Wで偏微分して0とおき、式をまとめると、数４のようになる。
【００３６】
【数４】
2018147262.tif 000007
2018147262.tif 000008
ここで、L=D-Aであり、Dは対角行列であり、その要素は、
【００３７】
【数５】
2018147262.tif 000009
である。
【００３８】
数４により、それぞれの三次元物体モデルに対応した類似度Wが求まる。最後に、Wの降順に三次元物体モデルを並べることで、検索結果を作成する。
【実施例】
【００３９】
本発明に係る実施例では、手書き画像特徴量の抽出にOPHOG法、三次元物体モデルの特徴量抽出にMRLBP法を用いているが、本発明に係る手書き画像の特徴量は、検索対象となる三次元物体モデルの特徴量が該手書き画像の特徴量と同様にして抽出できれば、前記特徴量の抽出方法に限定されない。
【００４０】
検索対象となる三次元物体モデルのデータに、機械部品の三次元物体モデルから構成されるデータセットであるEngineering Shape Benchmark(ESB)を用いた。ESBは42クラス、867個の三次元物体モデルから構成される。また、検索質問となる手書き画像は、ESBの三次元物体データに合わせて、クラスごとに10枚ずつ、合計420枚の手書き画像を手書きで作成した。
【００４１】
検索性能を評価するための尺度としては、Precision-Recall曲線, Nearest Neighbor(NN), First Tier(FT), Second Tier(ST), E-measure(E), Discounted Cumulative Gain(DCG), Average Precision(AP)を用いた。従来手法には、立間らのユークリッド距離により類似性を評価するOPHOG法、L2正則化のみを加えた重み付き線形和による重みを類似度とする方法を用いた。本発明のパラメータはk=10, α=0.4, β=7.5とした。L2正則化のみの重み計算でのパラメータはβ=9とした。
【００４２】
表１は各手法のNN，FT，ST，E，DCG，APの値をまとめたものである。全ての評価尺度で本発明が最も優れた検索性能を得ているのがわかる。
【００４３】
【表１】
2018147262.tif 000010
【００４４】
一方、図３は各手法のPrecision-Recall曲線である。全てのPrecision-Recallの組合せで、本発明が従来手法を上回っており、最も優れた検索性能であることがわかる。
【図１】
2018147262.tif 000011
【図２】
2018147262.tif 000012
【図３】
2018147262.tif 000013