盒子
盒子
Posts List
  1. Shape matching

地图的匹配问题

在查找文献的过程中,发现地图匹配(map matching)主要是基于GPS信号等获取到的地理坐标信息和实际的地图信息来进行匹配,好像和我们的问题并不是一样的,所以我就没有查找这方面的,而是将其当作一个图像问题。(唐进君, 曹凯. 一种自适应轨迹曲线地图匹配算法J. 測繪學報, 2008, 37(3): 308-315.)(Chen W, Li Z, Yu M, et al. An integrated map-match algorithm with position feedback and shape-based mismatch detection and correctionJ. Journal of Intelligent Transportation Systems, 2008, 12(4): 168-175.)

对于普通的图像问题,有两类相关的问题:图像匹配(image matching)和图像配准(image registration)。图像匹配是寻找与一幅图相似的图像(不对寻找到的图像做矫正);而图像配准是寻找相似图像但是变形后的图像(需要做一些旋转之类的校正变换)。图像配准一般是指针对与同一个传感器在不同的时间、不同的视角或者不同的传感器所获取的图像进行叠加(或者说是融合)的过程,所以其必然会考虑图像的畸变以及对原始图像进行优化。其基本包括四个步骤(Zitova B, Flusser J. Image registration methods: a surveyJ. Image and vision computing, 2003, 21(11): 977-1000.):

  • feature detection
  • feature matching
  • mapping function design
  • image transformation and resampling

对于前两个步骤,这是和图像匹配过程是相近的。由于我们的地图匹配问题,不需要配准的过程,所以下面主要叙述图像匹配方面的内容。

图像匹配一般分为两类:基于灰度的匹配和基于特征的匹配,由于我们的问题中并不存在颜色特征,故只可以使用基于特征的匹配方法。特征方面,在地图匹配中,由于地图只有形状信息,故只考虑基于特征的匹配方法。当不考虑图形的颜色、纹理等问题后,我们相当于可以将一副图形抽象为一个形状(shape),所以这个问题可以近似为形状匹配(Shape matching)

Shape matching

对于该问题可以将其拆分为两个方面,一个是图形的特征值部分(也即shape representation and description),另一个就是根据特征进行匹配的算法。

对于图形的特征部分,传统的分类方法(Zhang D, Lu G. Review of shape representation and description techniquesJ. Pattern recognition, 2004, 37(1): 1-19.)将特征分为基于轮廓(contour-based)和基于区域(region-based)两类,同时每一类中又根据是选取整体还是分段选取而分为structural 和 global 两类,其分类图如下:

(media/14818177325431/14818178326192.jpg)

随着越来越多的形状特征描述方法被提出,并且各种方法之间的融合也被提出,简单的按照获取特征的方法进行分类不再合适(例如对于矩-moments,即包括boundary moments也包括region moments如代数不变矩等)。于是参考文献(Yang M, Kpalma K, Ronsin J. A survey of shape feature extraction techniquesJ. Pattern recognition, 2008: 43-90.)根据过程提出了下面的分类:

(media/14818177325431/14818178491237.jpg)

该文献详细介绍了各种shape 以及 shape feature 的表示方法并在最后总结了各种 feature 针对于不变性(旋转、平移、伸缩、仿射变换)和鲁棒性(噪声、遮挡、畸变)。可以作为一个重要的参考资料。由于,现在无法确定最终的地理轮廓样式,所以无法确定对于 feature 的最终旋转,不过在对基本表达公式分析可以发现应该大部分是可以使用的。

借助上面的特征然后添加较为简单的代价函数就可以进行形状匹配,如(饶芮菱, 金雪峰, 鲁怀伟. 基于链码的二维碎片轮廓匹配算法J. 計算技術與自動化, 2007, 26(2): 34-37.)(赵东保, 贺添, 张卡. 基于复数矩的形状轮廓描述与匹配方法J. 四川大学学报: 工程科学版, 2011, 43(2): 109-115.)(朱延娟, 周来水, 张丽艳, 等. 基于 Hausdorff 距离的多尺度轮廓匹配算法J. 中国机械工程, 2004, 15(17): 1553-1556.)(王琼, 袁建英, 李柏林. 一种融合特征点与轮廓信息的匹配算法J. 计算机应用研究, 2014, 31(10): 3145-3147.)(Wang J, Bai X, You X, et al. Shape matching and classification using height functionsJ. Pattern Recognition Letters, 2012, 33(2): 134-143.)(Hong B W, Soatto S. Shape matching using multiscale integral invariantsJ. IEEE transactions on pattern analysis and machine intelligence, 2015, 37(1): 151-160.)。

对于根据特征点来进行匹配的算法,我并没有找到很好的综述性质的文章,然后找到了两篇相关的文章

Su Z, Wang Y, Shi R, et al. Optimal mass transport for shape matching and comparisonJ. IEEE transactions on pattern analysis and machine intelligence, 2015, 37(11): 2246-2259.

Hasanbelliu E, Giraldo L S, Principe J C. Information theoretic shape matchingJ. IEEE transactions on pattern analysis and machine intelligence, 2014, 36(12): 2436-2451.

对于上面两篇文章,现在还没有太看明白,另外就是感觉对于我们的问题,可能并不需要很复杂的匹配过程。

呼呼呼山(http://code4fun.me)
11 Jan 2018 10:48 PM