一种基于改进地貌形状上下文的形状匹配方法

刘望舒; 郑丹晨; 韩敏

doi:10.16383/j.aas.2017.c160302

一种基于改进地貌形状上下文的形状匹配方法

doi: 10.16383/j.aas.2017.c160302

刘望舒^1,,
郑丹晨^1,,
韩敏^1, ,

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

基金项目:

国家自然科学基金 61374154

中央高校基本科研业务费专项资金 DUT16RC(4)18

详细信息

作者简介:
刘望舒大连理工大学电子信息与电气工程学部硕士研究生.主要研究方向为模式识别.E-mail:liuwangshu@mail.dlut.edu.cn

郑丹晨大连理工大学电子信息与电气工程学部讲师.主要研究方向为计算机视觉和模式识别.E-mail:dcjeong@dlut.edu.cn

通讯作者:
韩敏大连理工大学电子信息与电气工程学部教授.主要研究方向为模式识别, 复杂系统建模与分析及时间序列预测.本文通信作者.E-mail:minhan@dlut.edu.cn

计量
- 文章访问数: 1470
- HTML全文浏览量: 177
- PDF下载量: 543
- 被引次数: 0
出版历程
- 收稿日期: 2016-04-01
- 录用日期: 2016-08-23
- 刊出日期: 2017-10-20

Shape Matching Method Based on Improved Aspect Shape Context

LIU Wang-Shu^1
,,
ZHENG Dan-Chen^1
,,
HAN Min^{1
, ,}

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

Funds:

National Natural Science Foundation of Chin 61374154

Fundamental Research Funds for the Central Universities DUT16RC(4)18

More Information

Author Bio:
Master student at the Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology. Her main research interest is pattern recognition

Lecturer at the Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology. He received his Ph. D. degree from Dalian University of Technology in 2014. His research interest covers computer vision and pattern recognition

Corresponding author: HAN Min Professor at the Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology. Her research interest covers pattern recognition, modeling and analysis of complex system, and time series prediction. Corresponding author of this paper.E-mail:minhan@dlut.edu.cn

摘要

摘要: 在基于地貌形状上下文的形状匹配方法中，计算地貌空间测地距离消耗时间较高，对应形状特征提取过程的效率较低.针对这一问题，本文提出了一种基于地貌模糊形状上下文的快速形状匹配方法.在形状特征提取过程中，通过引入最短路径算法对轮廓采样点间的测地距离进行快速计算.在此基础上结合对数极坐标模糊直方图构造地貌模糊形状上下文，其能够更好地描述轮廓点分布情况进而有效提升形状描述符的表达能力.考虑到轮廓点集顺序已知，进一步引入动态规划分析不同地貌空间下形状片段间的对应关系，以获取准确的形状匹配结果.通过对不同的数据集进行实验仿真分析，验证了本文方法能够有效地提升运算效率并取得较好形状检索精度.
- 形状匹配 /
- 地貌空间 /
- 最短路径 /
- 模糊直方图 /
- 地貌模糊形状上下文
Abstract: In shape matching method based on aspect shape context, it is time consuming to calculate the geodesic distances on the aspect spaces, and the process of shape feature extraction is inefficient. To solve this problem, this paper proposes a fast shape method based on aspect fuzzy shape context. During the process of shape feature extraction, the geodesic distances between sample points on the shape contour can be effectively obtained by using the shortest path algorithm, and log-polar fuzzy histogram is further introduced to construct aspect fuzzy shape context, and the description ability is improved with the sample point distributions represented precisely. With the orders of sample points, the dynamic programming method is employed to analyze the correspondence between shape segments in different aspect spaces, and the shape matching result can be obtained accurately. With the proposed method tested on different shape databases, the computation efficiency can be effectively improved and desirable shape retrieval results can be achieved.
- Shape matching /
- aspect space /
- shortest path /
- fuzzy histogram /
- aspect fuzzy shape context(AFSC)
注释:

1) 本文责任编委胡清华

HTML全文

图 1 以不同距离度量分析相似形状对应采样点关系的示例

Fig. 1 An example of analyzing the distances between corresponding points from two similar shapes with different measures

下载: 全尺寸图片幻灯片

图 2 一个二值图像对应生成的地貌空间示例

Fig. 2 An example of the aspect space obtained from a binary image

下载: 全尺寸图片幻灯片

图 3 地貌空间中测地线路径示例

Fig. 3 An example of geodesic in the aspect space

下载: 全尺寸图片幻灯片

图 4 分析不同方法计算测地距离效率

Fig. 4 Efficiency comparison of computing geodesic distances by using different methods

下载: 全尺寸图片幻灯片

图 5 Kimia-99数据集中形状样本示例

Fig. 5 Examples of shapes in Kimia-99 database

下载: 全尺寸图片幻灯片

图 6 参数τ变化对应的PR曲线

Fig. 6 Precision-recall curves for different τ

下载: 全尺寸图片幻灯片

图 7 Kimia-216数据集中形状样本示例

Fig. 7 Examples of shapes in Kimia-216 database

下载: 全尺寸图片幻灯片

图 8 Tari-1000形状样本示例

Fig. 8 Examples of shapes in Tari-1000 database

下载: 全尺寸图片幻灯片

表 1 Kimia-99数据形状特征提取时间比较(s)

Table 1 Comparison of the time used for shape feature extraction on Kimia-99 database (s)

方法	特征提取时间(s)
Fast marching^[11]	208.56
本文方法	11.77

下载: 导出CSV

表 2 Kimia-99数据在不同方法下检索结果比较

Table 2 Comparison of retrieval rates for different algorithms tested on Kimia-99 database

方法	1st	2nd	3rd	4th	5th	6th	7th	8th	9th	10th	全部
SC^[6]	97	91	88	85	84	77	75	66	56	37	756
Hierarchical parts^[16]	99	99	98	98	98	97	96	94	93	82	954
IDSC + DP^[10]	99	99	99	98	98	97	97	98	94	79	958
MDS + SC + DP^[10]	99	98	98	98	97	99	97	96	97	85	964
GM + SC^[17]	99	99	99	99	99	99	99	97	93	86	969
Height functions^[18]	99	99	99	99	98	99	99	96	95	88	971
FSC + SCS^[13]	99	99	99	99	98	99	98	95	94	91	972
Symbolic representation^[19]	99	99	99	98	99	98	98	95	96	94	975
AFSC	99	99	99	99	99	99	99	99	98	92	982

下载: 导出CSV

表 3 Kimia-216数据在不同方法下检索结果比较

Table 3 Comparison of retrieval rates for different algorithms tested on Kimia-216 database

方法	1st	2nd	3rd	4th	5th	6th	7th	8th	9th	10th	全部
Generative model^[20]	216	216	214	212	212	207	203	190	179	175	2024
Shock edit^[21]	216	216	216	215	210	210	207	204	200	187	2081
SC + DP^[10]	216	216	215	210	210	209	208	204	200	191	2079
FSC + SCS^[13]	216	216	215	214	213	214	210	201	193	188	2080
Path similarity^[22]	216	216	215	216	213	210	210	207	205	191	2099
IDSC + DP^[10]	216	216	215	211	211	210	211	207	203	198	2098
AFSC	216	216	216	214	214	215	209	207	209	199	2115

下载: 导出CSV

表 4 Tari-1000数据在不同方法下的结果比较

Table 4 Comparison of results for different algorithms tested on Tari-1000 database

方法	Bull's eye score
Tree edit + Context^[23]	86.42
Similar and discriminative parts^[24]	91.37
COP^[25]	92.18
SC + DP^[4]	94.17
Group-wised^[26]	94.58
IDSC + DP^[10]	95.33
ASC + DP^[11]	95.44
AFSC	97.21

下载: 导出CSV

参考文献(26)

[1]	Kendall D G. Shape manifolds, procrustean metrics, and complex projective spaces. Bulletin of the London Mathematical Society, 1984, 16(2):81-121 doi: 10.1112/blms.1984.16.issue-2
[2]	Su Y Q, Liu Y H, Cuan B N, Zheng N N. Contour guided hierarchical model for shape matching. In:Proceedings of the 15th IEEE International Conference on Computer Vision. Santiago, Chile:IEEE, 2015. 1609-1617
[3]	Janan F, Brady M. Shape description and matching using integral invariants on eccentricity transformed images. International Journal of Computer Vision, 2015, 113(2):92-112 doi: 10.1007/s11263-014-0773-x
[4]	Roman-Rangel E, Pallan C, Odobez J M, Gatica-Perez D. Analyzing ancient maya glyph collections with contextual shape descriptors. International Journal of Computer Vision, 2011, 94(1):101-117 doi: 10.1007/s11263-010-0387-x
[5]	周瑜, 刘俊涛, 白翔.形状匹配方法研究与展望.自动化学报, 2012, 38(6):889-910 http://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201206002.htm Zhou Yu, Liu Jun-Tao, Bai Xiang. Research and perspective on shape matching. Acta Automatica Sinica, 2012, 38(6):889-910 http://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201206002.htm
[6]	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 doi: 10.1109/34.993558
[7]	Mori G, Belongie S, Malik J. Efficient shape matching using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11):1832-1837 doi: 10.1109/TPAMI.2005.220
[8]	Xie J, Heng P A, Shah M. Shape matching and modeling using skeletal context. Pattern Recognition, 2008, 41(5):1756-1767 doi: 10.1016/j.patcog.2007.11.005
[9]	Premachandran V, Kakarala R. Perceptually motivated shape context which uses shape interiors. Pattern Recognition, 2013, 46(8):2092-2102 doi: 10.1016/j.patcog.2013.01.030
[10]	Ling H B, Jacobs D W. Shape classification using the innerdistance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2):286-299 doi: 10.1109/TPAMI.2007.41
[11]	Ling H B, Yang X W, Latecki L J. Balancing deformability and discriminability for shape matching. In:Proceedings of the 11th European Conference on Computer Vision. Crete, Greece:Springer, 2010. 411-424
[12]	Ling H B, Jacobs D W. Deformation invariant image matching. In:Proceedings of the 10th IEEE International Conference on Computer Vision. Beijing, China:IEEE, 2005. 1466-1473
[13]	韩敏, 郑丹晨.基于模糊形状上下文特征的形状识别算法.自动化学报, 2012, 38(1):68-75 http://www.aas.net.cn/CN/abstract/abstract17656.shtml Han Min, Zheng Dan-Chen. Shape recognition based on fuzzy shape context. Acta Automatica Sinica, 2012, 38(1):68-75 http://www.aas.net.cn/CN/abstract/abstract17656.shtml
[14]	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 doi: 10.1109/TPAMI.2004.1273924
[15]	Sebastian T B, Klein P N, Kimia B B. On aligning curves. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(1):116-125 doi: 10.1109/TPAMI.2003.1159951
[16]	Donoser M, Riemenschneider H, Bischof H. Efficient partial shape matching of outer contours. In:Proceedings of the 9th Asian Conference on Computer Vision. Xi'an China:Springer, 2010. 281-292
[17]	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 doi: 10.1109/TIP.2010.2040448
[18]	Wang J W, Bai X, You X G, Liu W Y, Latecki L J. Shape matching and classification using height functions. Pattern Recognition Letters, 2012, 33(2):134-143 doi: 10.1016/j.patrec.2011.09.042
[19]	Daliri M R, Torre V. Robust symbolic representation for shape recognition and retrieval. Pattern Recognition, 2008, 41(5):1782-1798 doi: 10.1016/j.patcog.2007.10.020
[20]	Tu Z W, Yuille A L. Shape matching and recognition-using generative models and informative features. In:Proceedings of the 8th European Conference on Computer Vision. Prague, Czech Republic:Springer, 2004. 195-209
[21]	Siddiqi K, Shokoufandeh A, Dickinson S J, Zucker S W. Shock graphs and shape matching. International Journal of Computer Vision, 1999, 35(1):13-32 doi: 10.1023/A:1008102926703
[22]	Bai X, Latecki L J. Path similarity skeleton graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7):1282-1292 doi: 10.1109/TPAMI.2007.70769
[23]	Baseski E, Erdem A, Tari S. Dissimilarity between two skeletal trees in a context. Pattern Recognition, 2009, 42(3):370-385 doi: 10.1016/j.patcog.2008.05.022
[24]	Wang Z, Ouyang J. Shape classes registration and retrieval based on shape parts matching. Journal of Computational Information Systems, 2013, 9(4):1493-1499 http://or.nsfc.gov.cn/handle/00001903-5/326740
[25]	Zhou Y, Wang J W, Zhou Q, Bai X, Liu W Y. Shape matching using points co-occurrence pattern. In:Proceedings of the 6th International Conference on Image and Graphics. Hefei, China:IEEE, 2011. 344-349
[26]	Wang J W, Zhou Y, Bai X, Liu W Y. Shape matching and recognition using group-wised points. In:Proceedings of the 5th Pacific Rim Symposium on Image and Video Technology. Gwangju, Korea:Springer, 2012. 393-404