基于期望首达时间的形状距离学习算法

郑丹晨; 韩敏

doi:10.3724/SP.J.1004.2014.00092

基于期望首达时间的形状距离学习算法

doi: 10.3724/SP.J.1004.2014.00092 cstr: 32138.14.SP.J.1004.2014.00092

郑丹晨,
韩敏

1.
大连理工大学电子信息与电气工程学部大连 116023

基金项目:

国家自然科学基金（61374154，61074096）资助

计量
- 文章访问数: 2020
- HTML全文浏览量: 73
- PDF下载量: 1288
- 被引次数: 0
出版历程
- 收稿日期: 2012-04-27
- 修回日期: 2012-09-29
- 刊出日期: 2014-01-20

Learning Shape Distance Based on Mean First-passage Time

1.
Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116023

Funds:

Supported by National Natural Science Foundation of China (61374154, 61074096)

摘要

摘要: 由于逐对形状匹配不能很好地反映形状间相似度，因此需要引入后期处理步骤提升检索精度. 为了得到上下文敏感的形状相似度，本文提出了一种基于期望首达时间（Mean first-passage time，MFPT）的形状距离学习方法. 在利用标准形状匹配方法得到距离矩阵的基础上，建立离散时间马尔可夫链对形状流形结构进行分析.将形状样本视作状态，利用不同状态之间完成一次状态转移的平均时间步长，即期望首达时间，表示形状间的距离.期望首达时间能够结合测地距离发掘空间流形结构，并可以通过线性方程进行有效求解.分别对不同数据进行实验分析，本文所提出的方法在相同条件下能够达到更高的形状检索精度.
- 形状匹配 /
- 形状距离学习 /
- 相似度矩阵 /
- 离散时间马尔可夫链 /
- 期望首达时间
Abstract: Since pairwise shape similarity analysis can not measure the shape distance accurately, post-processing steps are introduced into shape matching process for increasing retrieval scores. In this paper, a novel shape distance based on mean first-passage time (MFPT) is proposed for resolving the problem of learning context-sensitive similarity. Given the distance matrix computed by a distance function, discrete-time Markov chains are constructed for analyzing the underlying structure of the manifold formed by shapes. With each shape in the database regarded as a state, the mean number of steps for transition between two states, named mean first-passage time, is used to measure the shape distance. The mean first-passage time induced by geodesic paths can capture the shape manifold structure, and it can be obtained by solving the linear equations. Experimental results on different databases show that shape retrieval results can be effectively achieved by using the proposed method.
- Shape matching /
- learning shape distance /
- affinity matrix /
- discrete-time Markov chain /
- mean first-passage time (MFPT)

HTML全文

参考文献(18)

[1]	Ding Xian-Feng, Wu Hong, Zhang Hong-Jiang, Ma Song-De. Review on shape matching. Acta Automatica Sinica, 2001, 27(5): 678-694(丁险峰, 吴洪, 张宏江, 马颂德. 形状匹配综述. 自动化学报, 2001, 27(5): 678-694)
[2]	Zhou Yu, Liu Jun-Tao, Bai Xiang. Research and perspective on shape matching. Acta Automatica Sinica, 2012, 38(6): 889-910(周瑜, 刘俊涛, 白翔. 形状匹配方法研究与展望. 自动化学报, 2012, 38(6): 889-910)
[3]	Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4): 509-522
[4]	Ling H B, Jacobs D W. Shape classification using the inner-distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2): 286-299
[5]	Bai X, Yang X W, Latecki L J, Liu W Y, Tu Z W. Learning context-sensitive shape similarity by graph transduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(5): 861-874
[6]	Kontschieder P, Donoser M, Bischof H. Beyond pairwise shape similarity analysis. In: Proceedings of the 9th Asian Conference on Computer Vision. Berlin, Heidelberg: Springer-Verlag, 2009. 655-666
[7]	Yang X W, Koknar-Tezel S, Latecki L J. Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval. In: Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 357-364
[8]	Egozi A, Keller Y, Guterman H. Improving shape retrieval by spectral matching and meta similarity. IEEE Transactions on Image Processing, 2010, 19(5): 1319-1327
[9]	Bai X, Wang B, Wang X G, Liu W Y, Tu Z W. Co-transduction for shape retrieval. In: Proceedings of the 11th European Conference on Computer Vision. Heraklion, Greece: Springer, 2010. 328-341
[10]	Render S. A Guide to First-Passage Processes. Cambridge: Cambridge University Press, 2001.
[11]	Condamin S, Bénichou O, Tejedor V, Voituriez R, Klafter J. First-passage times in complex scale-invariant media. Nature, 2007, 450(7166): 77-80
[12]	He Shu-Yuan. Stochastic Process. Beijing: Peking University Press, 2008. 136-166(何书元. 随机过程. 北京: 北京大学出版社, 2008. 136-166)
[13]	Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5): 550-571
[14]	Baseski E, Baseski E, Tari S. Dissimilarity between two skeletal trees in a context. Pattern Recognition, 2009, 42(3): 370-385
[15]	Latecki L J, Lakamper R, Eckhardt T. Shape descriptors for non-rigid shapes with a single closed contour. In: Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head, USA: IEEE, 2000. 424-429
[16]	Daliri M R, Torre V. Robust symbolic representation for shape recognition and retrieval. Pattern Recognition, 2008, 41(5): 1782-1798
[17]	Felzenszwalb P F, Schwartz J D. Hierarchical matching of deformable shapes. In: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition. Minnesota, USA: IEEE, 2007. 1-8
[18]	Xu C J, Liu J Z, Tang X O. 2D shape matching by contour flexibility. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(1): 180-186