新しいパターンマッチング原理-解析的DPマッチング-の理論展開と評価

新模式匹配原理的理论发展和评估——解析式DP匹配

基本信息

批准号：
19650042
负责人：
内田誠一
金额：
$ 1.92万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Exploratory Research
财政年份：
2007
资助国家：
日本
起止时间：
2007 至 2008
项目状态：
已结题

项目摘要

本研究は、理論的興味深さだけでなく応用上も非常に重要な「2次元パターンの弾性マッチング問題」について、全く新しい原理に基づくDPマッチング-解析的DPマッチング-を持って取り組む。2008年度は、解析的DPマッチングの原理について、その定量的・定性的評価を、実画像を用いた物体追跡実験を通して徹底的に行なった。2007年度の開発・検討結果により明らかになったように、従来の離散的なDPマッチング法に対する解析的DPマッチングの計算量的有意性は、画像を扱うような高次元空間での最適化問題において非常に顕著になる。例えば、従来のDPマッチングのアプローチでは、2次元パターンのマッチング問題はNP-hard問題であり、事実上解けない。これに対し、解析的DPマッチングでは十分高速に解きうる。その知見を踏まえ、2008年度は、解析的DPマッチングの原理を動画像中の移動物体追跡に適用し、実験を通してその定量的・定性的な評価を行った。計算速度、解法の妥当性と拡張性、ならびにマッチングの精度(追跡精度)について様々な検討を加えた。特に、解析的DPマッチングで必要となる初期値(二次関数の近似中心)の与え方については、粗密戦略、双方向戦略という二つの手法を案出し、その優劣について比較を行った。また弾性体を追跡するための拡張も行った。それらの基礎的検討を踏まえた上で、実際の映像を用いた実験の結果、従来の離散的なDPマッチング法では数日を要する処理を、わずか100msで終了できることを確認した。これはすなわち、実に7桁以上の効率化が図られたことを意味している。比較対象について計算量低減の工夫を図った場合でも、依然2桁以上の効率化を維持していた。以上より、一定の成果が得られたものと考える。

这项研究将基于一个全新的原则，解决了“二维模式的弹性匹配问题”，不仅具有理论上的兴趣，而且还具有应用于DP匹配的DP匹配 - 分析DP匹配。 2008年，通过使用真实图像进行对象跟踪实验，对分析DP匹配原理进行定量和定性评估。正如2007年开发和检查结果所揭示的那样，在传统离散DP匹配方法上匹配的分析DP的计算意义在高维空间（例如与图像的较高空间）的优化问题中非常明显。例如，在常规的DP匹配方法中，2D模式匹配问题是NP硬性问题，几乎是难以理解的。相反，可以高速求解分析DP匹配。基于这一发现，在2008年，分析DP匹配的原理应用于移动图像中的移动对象跟踪，并通过实验进行了定量和定性评估。关于解决方案的计算速度，有效性和可扩展性以及匹配精度（跟踪精度）已经提出了各种考虑。特别地，关于分析DP匹配所需的初始值（近似函数近似的中心）的方法，提出了两种方法：一种粗糙的策略和双向策略，并就其优越性和自卑感进行了比较。它也扩展以跟踪弹性体。考虑到这些基本研究，我们确认使用实际图像的实验只能在100毫秒内完成，这需要几天使用常规的离散DP匹配方法。这意味着效率已提高了七个数字以上。即使努力减少比较目标的计算量，效率仍然可以通过两个以上的数量级来维持。从以上，我们认为已经取得了某些结果。

项目成果

期刊论文数量（54）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

並列Fast Level Set Methodによる移動体の高速な3次元形状復元

使用并行快速水平集方法快速恢复移动物体的 3D 形状

DOI：
发表时间：
2007
期刊：
電子情報通信学会論文誌 vol. J90-D(印刷中)
影响因子：
0
作者：
K. Hara;et. al.;原ら;岩下ら
通讯作者：
岩下ら

Real Time Estimation of Deforming Organs By Neural Network for Endoscopic Surgery Simulator

内窥镜手术模拟器神经网络实时估计变形器官

DOI：
发表时间：
2007
期刊：
The First International Symposium on Information and Computer Elements
影响因子：
0
作者：
Ken'ichi Morooka;H. Masuda;R. Kurazume;X. Chen;S. Uchida;K. Hara;M. Hashizume
通讯作者：
M. Hashizume