留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

矢量多边形模式识别的小波方法

范仲鸣 李精忠 张小波

范仲鸣, 李精忠, 张小波. 矢量多边形模式识别的小波方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
引用本文: 范仲鸣, 李精忠, 张小波. 矢量多边形模式识别的小波方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
FAN Zhongming, LI Jingzhong, ZHANG Xiaobo. A Wavelet Method for Vector Polygon Pattern Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
Citation: FAN Zhongming, LI Jingzhong, ZHANG Xiaobo. A Wavelet Method for Vector Polygon Pattern Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688

矢量多边形模式识别的小波方法

doi: 10.13203/j.whugis20150688
基金项目: 

国家自然科学基金 41671448

数字制图与国土信息应用工程国家测绘地理信息局重点实验室资助项目 DM2016SC08

详细信息
    作者简介:

    范仲鸣, 硕士生, 主要从事空间数据库多尺度表达研究.772798560@qq.com

    通讯作者: 李精忠, 博士, 副教授.00009232@whu.edu.cn
  • 中图分类号: P208;TP391.41

A Wavelet Method for Vector Polygon Pattern Recognition

Funds: 

The National Natural Science Foundation of China 41671448

the Open Research Fund Program of Key Laboratory of Digital Mapping and Land Information Application Engineering, NASG DM2016SC08

More Information
    Author Bio:

    FAN Zhongming, master, specializes in the theory and method research of spatial database and multi-scale expression.E-mail:772798560@qq.com

    Corresponding author: LI Jingzhong, PhD, associate professor. E-mail: E-mail:00009232@whu.edu.cn
图(8) / 表(3)
计量
  • 文章访问数:  950
  • HTML全文浏览量:  65
  • PDF下载量:  297
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-10
  • 刊出日期:  2017-10-05

矢量多边形模式识别的小波方法

doi: 10.13203/j.whugis20150688
    基金项目:

    国家自然科学基金 41671448

    数字制图与国土信息应用工程国家测绘地理信息局重点实验室资助项目 DM2016SC08

    作者简介:

    范仲鸣, 硕士生, 主要从事空间数据库多尺度表达研究.772798560@qq.com

    通讯作者: 李精忠, 博士, 副教授.00009232@whu.edu.cn
  • 中图分类号: P208;TP391.41

摘要: 提出了一种基于小波描述子的矢量多边形的模式识别方法,首先分别计算目标多边形与模板多边形的小波系数矩阵,再通过两个矩阵求取两多边形之间的非相似度,最后通过非相似度来确定是否匹配成功。并且,由所选用的小波的性质,可针对性地计算能够体现多边形特征的系数进行比较,从而使识别效果更好。实验结果表明该方法识别效果好,运算效率高,对平移、旋转、缩放等变换不敏感,是一种有效的矢量多边形模式识别方法。

English Abstract

范仲鸣, 李精忠, 张小波. 矢量多边形模式识别的小波方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
引用本文: 范仲鸣, 李精忠, 张小波. 矢量多边形模式识别的小波方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
FAN Zhongming, LI Jingzhong, ZHANG Xiaobo. A Wavelet Method for Vector Polygon Pattern Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
Citation: FAN Zhongming, LI Jingzhong, ZHANG Xiaobo. A Wavelet Method for Vector Polygon Pattern Recognition[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1400-1405, 1416. doi: 10.13203/j.whugis20150688
  • 模式识别是指对表征事物或是现象的数值的、文字的或是逻辑关系层面的信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分[1]。在测绘学中,模式识别被用来进行地理信息提取[2]、特定地理要素的识别[3, 4]、自动制图综合[5, 6]、遥感图像分类[7]等工作。模板匹配法是模式识别中最简单实用的一种方法,最基本的模板匹配法通过对目标图像与模板图像进行逐像素地对比计算非相似度来进行匹配,这种方法虽然准确性高,但是效率很低,因此一直以来都有学者致力于寻找改良的模板匹配。改良方法的基本思路一般是通过一些方法生成数值的描述子来描述目标的形状,描述子应尽可能区别不同目标并且对目标的一些细微变化不敏感[8]。一些常用的描述子包括链码[9]、样条[10]、矩[11]、傅里叶描述子[12]等。

    采用链码和矩作为描述子的方法通常适用于像素图形,若将矢量多边形转化为像素图形再使用上述方法会降低效率,样条方法多用于描述由复杂曲线构成的图形,用傅里叶方法处理矢量多边形已经有了一定的成果,如帅赟等[13]使用傅里叶描述子为基础进行模板匹配,艾廷华等[14]的以傅里叶变换为基础定义的相似度的计算方法,但傅里叶方法对于规则的多边形而言一般会展开到很高的阶次,因此这些方法对于由顶点以及直线段构成的矢量多边形而言效果并不是最好。

    在模式识别领域中,由于Mallat快速算法的存在,小波在等间隔采样的数据(像素图、均匀采样的音频或电信号等)的处理上具有天然的优势。利用小波方法对像素图或栅格数据进行识别的研究已经有了理论成果[15, 16]。由于矢量多边形数据并非等间隔采样数据,因此应用小波分析的方法时不能直接套用对像素图进行处理时采用的算法。本文将探讨以小波系数作为描述子对矢量多边形模式识别在可靠性与效率上的可行性,并以一种多贝西小波(DB2) 为例对结合了小波方法的模板匹配法进行论述。

    • 小波(wavelet)函数是由一个函数为原型,通过一定的形变和平移得到的一族函数的统称,其中作为原型的函数被称为母小波,记做ψ(t)。母小波一般需要满足以下条件:

      $$ \left\{ {\begin{array}{*{20}{l}} \begin{array}{l} \int_{ - \infty }^{ + \infty } {\psi \left( t \right){\rm{d}}t = 0} \\ \int_{ - \infty }^{ + \infty } {|\psi \left( t \right){{\rm{|}}^2}{\rm{d}}t = 1} \end{array} \end{array}} \right. $$ (1)

      其他函数由母小波通过形变和平移得到,记做ψa, b(t),且有:

      $$ {\psi _{a, b}}(t) = {\left| a \right|^{-\frac{1}{2}}}\psi \left( {\frac{{t-b}}{a}} \right) $$ (2)

      式中,参数a控制形变尺度,称为尺度系数; 参数b控制图形在坐标轴上的左右位移,称为平移系数。

      做函数f(t)与ψa, b(t)的内积,得到:

      $$ ({T^{{\rm{WAV}}}}f)(a, b) = {\left| a \right|^{-\frac{1}{2}}}\int_{_{-\infty }}^{^{ + \infty }} {f(t)} \psi \left( {\frac{{t-b}}{a}} \right){\rm{d}}t $$ (3)

      ab可在R上任意取值,称TWAVf的连续小波变换(continuous wavelet transform,CWT),计算结果称为f的小波系数。若将式(3) 中的尺度系数a离散化,则得到:

      $$ T_{_{m, n}}^{^{{\rm{WAV}}}}\left( f \right) = {a_0}^{-\frac{m}{2}}\smallint _{_{-\infty }}^{^{ + \infty }}f(t)\psi (a_{_0}^{^{-m}}t - n{b_0}){\rm{d}}t $$ (4)

      其中:

      $$ \left\{ \begin{array}{l} a = a_0^m\\ b = n{b_0}a_0^m \end{array} \right.,m \in Z $$ (5)

      使得尺度系数无法在R上任意取值,称式(5) 为函数f的二进小波变换。若式(5) 中有nZ,即将平移系数b也离散化,称式(5) 为函数f的离散小波变换(discrete wavelet transform,DWT)。本文将利用由多贝西小波DB2为基础的二进小波变换得到的小波系数。多贝西小波DB2具有如下性质:若f为一次函数,则有TWAV(f)=0。

      多边形的边为一条线段,其表达式为一次函数,多贝西小波的该性质会使得多边形的某条边的一部分所对应的小波系数为零,通常而言这样的一部分边是不重要的,从而通过小波系数是否为0即可判断该系数是否重要。

      DB2小波是通过上述性质构造而来,因此无法求出确切的表达式,但通过数值方法可以得到该函数各点任意精度的近似值。图 1是用数值方法求得的DB2母小波的一个近似函数的图像,其于[0, 3]以外的点上的函数值皆为零。

      图  1  DB2小波的函数图像

      Figure 1.  Function Image of DB2 Wavelet

    • 矢量多边形可用其顶点的坐标序列描述,用直线段顺次连接顶点即得到完整的多边形。将多边形看做一个做匀速运动的点的位置随时间t的变化而形成的轨迹,并对其轨迹的表达式做周期延拓,则多边形可写为参数方程:

      $$ \left\{ \begin{array}{l} x = x\left( t \right)\\ y = y\left( t \right) \end{array} \right., t \in \left( {-\infty, + \infty } \right) $$

      分别对x(t)与y(t)做二进小波变换即可得到相应的小波系数。

      DB2小波的紧支性,使得参数方程与小波函数的内积函数也具有紧支性,每个mn值确定的小波系数均可以通过对内积函数在有限区间内做数值积分的方法得到。mn皆可有无穷多取值,为了得到尽可能精简的特征,必须知道哪些系数是最值得计算的。

      对多边形进行特征提取得到的系数称为多边形的一个特征系数,求取特征系数时所用的的小波函数的非零区间的中点ti所对应的位于多边形上的点(x(ti), y(ti))为多边形的一个特征点,多边形的同一个特征点上的特征系数按其小波函数的m取值从大到小排列构成的向量为多边形的一个特征向量,多边形的特征向量构成的矩阵为一个特征矩阵。

      首先考虑尺度系数中m的取值范围。显然,m值越小,则需要求取的特征系数越多,识别的效果越好,但计算量也越大,因此需要确定一个能够达到足够精度的尽可能大的m。为达到此目的,采用离散小波变换得到的系数对多边形进行重构。粗略观察重构的图形(见图 2),可以观察到无论多边形规则与否,取m值为-5时重构多边形的形状已经非常接近原始多边形。由此猜想实际应用时可令m的最小值为-5,应已足够对多边形进行识别。

      图  2  用小波系数重构的3个多边形

      Figure 2.  Three Polygons Reconstructed with Wavelet Coefficient Original Graphics

      为验证m的最小值取-5时即可满足精度要求的猜想,本文采用计算重构图形与原始图形的面积重叠度的方法。记原始多边形为P,重构多边形为P′, 定义P′对P的面积重叠度UP′为:

      $$ {U_{P\prime }} = \left[{S\left( {P \cap P\prime } \right)/S\left( P \right)} \right] \times 100\% $$ (6)

      式中,S(P)为P的面积。将图 2的几个重构多边形从上到下编号为a、b、c,分别计算其对相应的原始多边形的面积重叠度得到表 1

      表 1  重构图形与相应原图形的面积重叠度

      Table 1.  Overlap Percentage between Reconstructed Graphics and Corresponding

      m Ua/% Ub/% Uc/%
      0 59.907 63.241 49.276
      -1 81.271 81.155 69.751
      -2 92.368 93.209 85.550
      -3 98.027 97.046 94.341
      -4 99.489 98.939 97.833
      -5 99.809 99.466 99.362
      -6 99.891 99.643 99.770
      -7 99.904 99.683 99.870
      -8 99.905 99.697 99.888

      表 1可知,在m最小值取-5时,面积重叠度已经达到了99%以上,从而能够满足需要的精度要求。

      再考虑平移系数中n的取值。由于DB2小波的良好性质,对于每个确定的m,取一系列等间隔的n值可使得与原函数做内积运算的小波函数构成内积空间的一组基,从而能对原多边形进行重构。因此,采用离散小波变换的方法取闭区间上等间隔的有限个n值即可符合要求。

      一次函数与DB2小波的内积总是零,而等间隔取n值同时使得多边形的特征点对于参数t而言也变得等间隔,因此不可避免地会计算连接两个相邻顶点的边的参数方程与DB2小波的内积,会使得计算的结果中存在大量的零值,这对于计算效率以及体现多边形的特征而言效果并不好。由于矢量多边形最重要的信息在于其顶点位置,因此用顶点而不是等间隔的取多边形上的点作为特征点更能够体现多边形的特征,对于每一个m,选取多边形的顶点作为特征点进行运算会使得计算结果更好。

    • 对模板多边形与目标多边形均用上述特征提取的方法计算特征系数,用特征系数构成的特征矩阵作为提取的多边形的特征,通过计算两个特征矩阵的非相似度来确定目标多边形是否与模板多边形同类。

      记目标有k个顶点的多边形为P,顶点分别为p0(x0, y0), p1(x1, y1), …, pk(xk, yk),nm, i是使得函数ψm, n(t)的非零区间中点位于顶点pi上的n的取值,本文特征矩阵MP为:

      $$ {\mathit{\boldsymbol{M}}_P} = \left[{\begin{array}{*{20}{c}} {{T_{0, {n_{0, 0}}}}}&{{T_{1, {n_{1, 0}}}}}& \cdots &{{T_{m, {n_{m, 0}}}}}\\ {{T_{0, {n_{0, 1}}}}}& \ddots &{}&{{T_{m, {n_{m, 1}}}}}\\ \vdots &{}& \ddots & \vdots \\ {{T_{0, {n_{0, k}}}}}&{{T_{1, {n_{1, k}}}}}& \cdots &{{T_{m, {n_{m, k}}}}} \end{array}} \right] $$

      其中:

      $$ \begin{array}{l} T_{{{_{i, n}}_{_{i, j}}}}^{^2} = {\left[{{2^{-\frac{i}{2}}}\int_{_{-\infty }}^{^{ + \infty }} {x(t)} \psi ({2^{-i}}t - {n_{i, j}}){\rm{d}}t} \right]^2} + \\ \;\;\;\;\;\;\;\;\;\;{\left[{{2^{-\frac{i}{2}}}\int_{_{-\infty }}^{^{ + \infty }} {y(t)} \psi ({2^{-i}}t - {n_{i, j}}){\rm{d}}t} \right]^2} \end{array} $$ (7)

      若对多边形P做平移和旋转的变化得到多边形$ \tilde P $, 则其顶点$\widetilde {{p_i}} $满足如下关系:

      $$ \left( \begin{array}{l} \widetilde {{x_i}}\ \widetilde {{y_i}} \end{array} \right) = \left( {\begin{array}{*{20}{c}} {\cos \theta }&{-\sin \theta }\\ {\sin \theta }&{\cos \theta } \end{array}} \right)\left( \begin{array}{l} {x_i}\\ {y_i} \end{array} \right) + \left( \begin{array}{l} c\\ d \end{array} \right) $$ (8)

      从而可知:

      $$ {\mathit{\boldsymbol{M}}_P} = {\mathit{\boldsymbol{M}}_{\widetilde P}} $$ (9)

      即特征矩阵不会随多边形的平移和旋转而改变。本文采用将多边形的周长缩放为定值后再计算其特征矩阵的方法,因而对仿射变换具有稳定性。

      对模板多边形与目标多边形分别求算特征矩阵后,由于两者的顶点数一般不同,因此得到的矩阵行数一般不同。因此,先计算两矩阵的行向量之间的非相似度矩阵N,记模板多边形的特征矩阵Mo=[A0 A1At]T,目标多边形的特征矩阵Mp=[B0 B1Bk]T,则:

      $$ \mathit{\boldsymbol{N = }}\left( {\begin{array}{*{20}{c}} {\left\langle {{\mathit{\boldsymbol{A}}_0}, {\mathit{\boldsymbol{B}}_0}} \right\rangle }&{\left\langle {{\mathit{\boldsymbol{A}}_1}, {\mathit{\boldsymbol{B}}_0}} \right\rangle }& \cdots &{\left\langle {{\mathit{\boldsymbol{A}}_l}, {\mathit{\boldsymbol{B}}_0}} \right\rangle }\\ {\left\langle {{\mathit{\boldsymbol{A}}_0}, {\mathit{\boldsymbol{B}}_1}} \right\rangle }& \ddots &{}& \vdots \\ \vdots &{}& \ddots & \vdots \\ {\left\langle {{\mathit{\boldsymbol{A}}_0}, {\mathit{\boldsymbol{B}}_k}} \right\rangle }& \cdots & \cdots &{\left\langle {{\mathit{\boldsymbol{A}}_l}, {\mathit{\boldsymbol{B}}_k}} \right\rangle } \end{array}} \right) $$ (10)

      其中,

      $$ \left\langle {{\mathit{\boldsymbol{A}}_m}, {\mathit{\boldsymbol{B}}_n}} \right\rangle = 1-\frac{{{\rm{max}}({\mathit{\boldsymbol{B}}_{{m_i}}})}}{{{\rm{max}}({\mathit{\boldsymbol{B}}_{{m_i}}}) + D({\mathit{\boldsymbol{A}}_m}, {\mathit{\boldsymbol{B}}_n})}} $$ (11)

      式中,0 < i < kD(Am, Bn)指两向量AmBn的欧氏距离。若得到的N的行数小于列数,则将N转置。

      计算得到矩阵N后,依次从N的每一行中取出一个数,且规定后取出的数所在列必须比先取出的数所在列更靠右,依此规则取出的数的总和的最小值除以向量的行数即为所求非相似度。

      最后,根据非相似度的大小来判断目标多边形是否匹配成功,非相似度越大,则两个多边形的形状越不相似。

    • 判断是否匹配成功需要判断目标与模板多边形的非相似度是否过大,在实际使用之前,有必要通过实验确定使用的模板多边形所对应的非相似度的阈值。若求取的非相似度大于阈值,则认为匹配失败,反之亦然。

      实验使用的模板多边形的形状如图 3所示,实验内容为用形状各异的目标多边形分别与模板多边形求非相似度,通过观察结果确定一个较合理的阈值。

      图  3  选取的模板多边形

      Figure 3.  Template Polygon Selected

      实验使用的目标多边形的形状如图 4,通过观察即可知这些多边形中,图 4(e)是由模板多边形增加一个顶点得到,而图 4(f)是模板多边形沿水平方向拉伸得到,从而图 4(e)图 4(f)理论上应该匹配成功。

      图  4  选取的目标多边形

      Figure 4.  Target Polygons Selected

      本文程序用Python编写,在Windows 7运行,处理器主频为2.4 GHz。

      实验结果如表 2所示。从表 2结果看,对于该模板多边形,可以认为将阈值取为20%左右较为合理。

      表 2  目标多边形的识别结果

      Table 2.  Identification Results of Target Polygons

      目标编号 非相似度/% 平均用时/ms
      (a) 23.058 248.0
      (b) 23.729 209.0
      (c) 26.509 573.0
      (d) 27.834 490.0
      (e) 7.091 960.0
      (f) 19.742 893.0
    • 图 5是武汉大学某家属区建筑物平面图,设定阈值为20%,仍以图 3中的多边形为模板多边形对该小区的建筑物进行识别,并将成功识别出来的建筑物用网格标记出来,得到的结果如图 5(b)所示。

      图  5  武汉大学家属区建筑物模式识别平面图

      Figure 5.  Part of Plan of Relational Area of WHU

      从实际效果来看,与模板多边形相似的建筑物全部被识别出来,而且没有出现误匹配的情况,说明对于此模板多边形而言此阈值的设置是合理的。

    • 定义几个指标:运行时间为从数据输入到结果输出所需的时间;识别率为实际正确识别出来的多边形占应被识别的多边形的百分比;误识别率为不应被识别而实际被识别的多边形占不应被识别的多边形总数的百分比。

      本文选择的深圳市某区1:10 000的平面图(图 8)进行对比实验。采用传统的模板多边形匹配法:将两个多边形的周长缩放至相同,再对起点进行重叠,对模板多边形中每个顶点在参数方程中对应的t值,求取目标多边形中相同t值的点作为其对应点,计算对应点之间的欧氏距离作为非相似度。

      图  8  实验结果

      Figure 8.  Results of Experiment

      实验采用的模板多边形为“L”型多边形,如图 6所示。

      图  6  “L”形模板多边形

      Figure 6.  L-Shape Template Polygon

      实验使用的平面图如图 7所示,假定应被识别的多边形已用深色标出,结果如图 8所示。可以看出,对于稍复杂的图形,传统方法很难进行有效识别。

      图  7  深圳市某区图

      Figure 7.  Part of the Street Map of Shenzhen

      表 3  实验中两种方法的指标对比

      Table 3.  Index Comparison of the Two Methods in Experiment

      指标 本文方法 传统方法
      总多边形数x 37 37
      运行时间t 23.888s 1.389s
      t/x 0.646s 0.038s
      识别率 100% 0
      误识别率 2.9% 41.2%

      通过对比实验可以看出,本文提出的方法相对传统的识别方法在精度上有很大的提升,而识别多边形所用的时间在可接受范围内,说明该方法有效可行。

    • 本文提出一种以小波系数为基础的特征矩阵之间的非相似度计算进行模板匹配的方法,对矢量多边形进行模式识别,得到了较好的结果,说明该方法是一种行之有效的方法。

      进一步的探究发现,该方法存在两方面缺陷:一是每个模板多边形适用的阈值并不相同,因此每次使用一个新的模板多边形时首先需要确定阈值;二是该方法如何在准确度与效率之间做出平衡尚需进一步的探究。

参考文献 (16)

目录

    /

    返回文章
    返回