一种信封图像匹配方法

摘要

本发明公开了一种信封图像匹配方法，将待匹配的两个信封图像分别用图表示出来，则图像之间的相似度计算转化为图匹配问题，采用基于最小权重的二分图匹配算法计算两个图之间的距离。进一步的，首先对信封图像进行分割，基于分割结果构建图像的图表示。其中，图的每个顶点代表信封图像中的一个区域，而图的每一条边用来表示两个区域之间的邻接关系。由于图像在采集过程中易受到噪声等因素的影响，可能会导致对应于同一个信封的多个图像的图表示有所不同，故本发明采用一种非精确图匹配算法。大量实验结果表明，该方法对于光照、倾斜、旋转等具有较强的鲁棒性，能够高效地实现基于信封图像的信函信息查询。

主权项

1.一种信封图像匹配方法，包括对信封图像进行高斯平滑滤波、边缘检测、二值化以及闭运算的预处理步骤，其特征在于，还包括以下步骤：步骤A1，对所述信封图像进行分割，分割结果为Ω={R₁,R₂,...,R_N}，其中N表示区域总数，区域R_i的邻接区域为N(R_i)，基于分割结果Ω构建该信封图像的图G=(V,E,μ,ν)，其中V是顶点集，E是边集，μ:V→L_V为顶点属性函数，ν:E→L_E为边属性函数，其中L_V和L_E可以是任意类型的集合，图G中的顶点v_i对应Ω中的区域R_i，图G中的任两个顶点v_i及v_j，其对应区域分别为R_i∈Ω及R_j∈Ω，v_i和v_j之间存在边e_ij的条件是R_i∈N(R_j)或者R_j∈N(R_i)，图G顶点数目与区域总数相等，也为N，对于图G中的顶点v_i，v_i∈V，根据描述习惯，记v_i∈G，其属性定义为v_i={F_i,T_i,M_i,C_i}，其中，F_i为前景像素比例，即区域R_i中前景像素占整个图像中前景像素的比例；T_i为纹理特征向量，且T_i={Ent_avg,Ent_var,Con_avg,Con_var,Hom_avg,Hom_var}，即计算区域R_i的四方向，包括0度、45度、90度以及180度的灰度共生矩阵P_j(j=1,2,3,4)，其大小为S×S，基于每个P_j提取熵Ent、对比度Con和逆差距Hom三个特征：${\mathrm{Ent}}_j=-\underset{a=0}{\overset{S}{\Sigma }}\underset{b=0}{\overset{S}{\Sigma }}{P}_j(a,b)\times \log P_j(a,b)---\left(1\right)$${\mathrm{Con}}_j=-\underset{a=0}{\overset{S}{\Sigma }}\underset{b=0}{\overset{S}{\Sigma }}{(a-b)}^2\times P_j(a,b)---\left(2\right)$${\mathrm{Hom}}_j=-\underset{a=0}{\overset{S}{\Sigma }}\underset{b=0}{\overset{S}{\Sigma }}\frac{P_j(a,b)}{1+{(a-b)}^2}---\left(3\right)$对每个特征分别求四个方向的均值与方差，则纹理特征最终表示为特征向量T_i={Ent_avg,Ent_var,Con_avg,Con_var,Hom_avg,Hom_var}；M_i为矩特征，假定区域R_i的灰度级范围为[0-L]，则其归一化后灰度直方图表示成H_i={h(0),h(1),...,h(L)}，其中h(k)(k=0,1,...,L)代表灰度级k在区域R_i中所占比例，该区域的直方图二阶矩为：$M_i=\underset{k=0}{\overset{L}{\Sigma }}{(k-m)}^2\times h\left(k\right)---\left(4\right)$其中m为区域R_i的平均灰度值；C_i为上下文特征，令(Cx_i,Cy_i)为R_i的中心，R_j∈N(R_i)的中心为(Cx_j,Cy_j),连接(Cx_i,Cy_i)与(Cx_j,Cy_j)，则形成以(Cx_i,Cy_i)为中心的星形拓扑结构，将整个平面划分为||N(R_i)||份，该拓扑结构较好地描述了N(R_i)之间相对于R_i的位置关系，用θ来表示两条直线间的夹角，则R_i的上下文特征可以描述为特征向量对于图G中连接顶点v_i和v_j的边e_ij，其属性描述所连接两个区域R_i和R_j之间的邻接关系，边e_ij={Cdis_ij,Ang_ij}其中Cdis_ij为归一化的中心连线距离，${\mathrm{Cdis}}_{\mathrm{ij}}=\frac{\sqrt{{({\mathrm{Cx}}_i-{\mathrm{Cx}}_j)}^2+{({\mathrm{Cy}}_i-{\mathrm{Cy}}_j)}^2}}{\sqrt{{\mathrm{ImgH}}^2+\mathrm{Img}{W}^2}}---\left(5\right)$R_i的中心坐标为(Cx_i,Cy_i)，R_j的中心坐标为(Cx_j,Cy_j)，其中ImgH和ImgW分别代表信封图像的高和宽，边e_ij的角度特征Ang指该边与其它所有与顶点v_i或v_j相连的边之间的夹角集合，设E_i={e_im|m=1,2,...,N_i,m≠j,m≠i}表示与顶点v_i相连的边集，E_j={e_jn|n=1,2,...,N_j,n≠i,n≠j}表示与顶点v_j相连的边集，其中N_i和N_j分别表示与顶点v_i及v_j相连的边数，则e_ij的角度特征Ang为：Ang_ij=Ang_i∪Ang_j    （6）其中，${\mathrm{Ang}}_i=\{{\theta }_{e_{\mathrm{ij}}{e}_{i1}},{\theta }_{e_{\mathrm{ij}}{e}_{i2}},····,{\theta }_{e_{\mathrm{ij}}{e}_{\mathrm{im}}}\},e_{\mathrm{im}}\in E_i---\left(7\right)$${\mathrm{Ang}}_j=\{{\theta }_{e_{\mathrm{ij}}{e}_{j1}},{\theta }_{e_{\mathrm{ij}}{e}_{j2}},···,{\theta }_{e_{\mathrm{ij}}{e}_{\mathrm{jn}}}\},e_{\mathrm{jn}}\in E_j---\left(8\right)$${\theta }_{e_{\mathrm{ij}}{e}_{\mathrm{im}}}=\arccos \left(\frac{e_{\mathrm{ij}}·e_{\mathrm{im}}}{\left|e_{\mathrm{ij}}\right|\times \left|e_{\mathrm{im}}\right|}\right)---\left(9\right);$A2，令图库中任一图，表示为G'=(V',E',μ',ν')，计算图G=(V,E,μ,ν)与G'=(V',E',μ',ν')之间的相似度，具体步骤为：B1，计算v_i∈G与v_i'∈G'顶点之间的距离d(v_i,v_i')=d_F+d_T+d_M+d_C    （15）其中，F_i之间的距离d_F：$d_F=\frac{|F_i-F_{i^{\prime }}|}{F_i+F_{i^{\prime }}}---\left(10\right)$T_i之间的距离d_T：$d_T=1-\underset{K=\mathrm{Ent},\mathrm{Con},\mathrm{Hom}}{\Pi }\frac{\min (K_{\mathrm{avgi}},K_{{\mathrm{avgi}}^{\prime }})\min (K_{\mathrm{vari}},K_{\mathrm{var}{i}^{\prime }})}{\max (K_{\mathrm{avgi}},K_{{\mathrm{avgi}}^{\prime }})\max (K_{\mathrm{vari}},K_{{\mathrm{vari}}^{\prime }})}---\left(11\right)$M_i之间的距离d_M：$d_M=\frac{|M_i-M_{i^{\prime }}|}{M_i+M_{i^{\prime }}}$C_i之间的距离d_C采用Hausdorff距离计算d_C，具体方法如下，假定C_i={θ₁,θ₂,...,θ_p}，C_i'={θ'₁,θ'₂,...,θ'_p'}，则$d_C=\frac{\max (h(C_i,C_{i^{\prime }}),h(C_{i^{\prime }},C_i))}{\mathrm{Context}\_\mathrm{MAX}}---\left(12\right)$其中，$h(C_i,C_{i^{\prime }})=\underset{\theta \in C_i}{\max }\underset{{\theta }^{\prime }\in C_{i^{\prime }}}{\max }|\theta -{\theta }^{\prime }|---\left(13\right)$$h(C_{i^{\prime }},C_i)=\underset{{\theta }^{\prime }\in C_{i^{\prime }}}{\max }\underset{\theta \in C_i}{\min }|{\theta }^{\prime }-\theta |---\left(14\right)$Context_MAX是两个顶点属性C之间取到的最大Hausdorff距离，即获得v_i∈G与v_i'∈G'之间的距离d(v_i,v_i')如下，d(v_i,v_i')=d_F+d_T+d_M+d_C    （15）B2，计算对于e_ij∈G和e_i'j'∈G'，边之间的距离为d(e_ij,e_i'j')=d_Cdis+d_Ang    （16）其中d_Cdis表示Cdis属性之间的距离，d_Ang表示Ang属性之间的距离，属性Cdis之间的距离d_Cdis为$d_{\mathrm{Cdis}}=\frac{|{\mathrm{Cdis}}_{\mathrm{ij}}-{\mathrm{Cdis}}_{i^{\prime }{j}^{\prime }}|}{|{\mathrm{Cdis}}_{\mathrm{ij}}+{\mathrm{Cdis}}_{i^{\prime }{j}^{\prime }}|}$属性Ang之间的距离d_Ang采用Hausdorff距离计算，主要步骤如下：假设Ang_ij={θ₁,θ₂,...,θ_p}，Ang_i'j'={θ'₁,θ'₂,...,θ'_p'}，则$d_{\mathrm{Ang}}=\frac{\max \left(h(A{\mathrm{ng}}_{\mathrm{ij}},{\mathrm{Ang}}_{i^{\prime }{j}^{\prime }})\right),h({\mathrm{Ang}}_{i^{\prime }{j}^{\prime }},{\mathrm{Ang}}_{\mathrm{ij}})}{\mathrm{Ang}\_\mathrm{MAX}}$其中，$h({\mathrm{Ang}}_{\mathrm{ij}},{\mathrm{Ang}}_{i^{\prime }{j}^{\prime }})=\underset{\theta \in {\mathrm{Ang}}_{\mathrm{ij}}}{\max }\underset{{\theta }^{\prime }\in {\mathrm{Ang}}_{i^{\prime }{j}^{\prime }}}{\min }|\theta -{\theta }^{\prime }|$$h({\mathrm{Ang}}_{i^{\prime }{j}^{\prime }},{\mathrm{Ang}}_{\mathrm{ij}})=\underset{{\theta }^{\prime }\in {\mathrm{Ang}}_{i^{\prime }{j}^{\prime }}}{\min }\underset{\theta \in {\mathrm{Ang}}_{\mathrm{ij}}}{\min }|{\theta }^{\prime }-\theta |$Ang_MAX是两条边属性Ang之间取到的最大Hausdorff距离；B3，计算图之间的距离Dist(G,G')根据G=(V,E,μ,ν)和G'=(V',E',μ',ν')建立二分图BP，具体为：令$\mathrm{BP}=(\bar{U},\bar{W},\bar{E}),$其中$\bar{U}=V,$$\bar{W}=V^{\prime },$$\bar{E}=\bar{U}\times \bar{W},$若${\bar{e}}_{{\mathrm{ii}}^{\prime }}\in \bar{E},$则令其权重为$w\left({\bar{e}}_{{\mathrm{ii}}^{\prime }}\right)=d(v_i,v_{i^{\prime }}),$基于二分图BP，运用Munkre算法获得具有最小权重的匹配，将该最小权重作为两个图之间的顶点距离Dist_Node，假设图G=(V,E,μ,ν)与G'=(V',E',μ',ν')中顶点数目分别为N和N'，则采用Munkre算法获得min(N,N')对顶点对应关系，定义0-1矩阵Z，大小为N×N'，即基于矩阵Z可以获得两个图之间隐含的边匹配关系，主要分为以下四种情况：假设v_i∈G,v_j∈G及v_i'∈G',v_j'∈G'，Z[i][i']=1并且Z[j][j']=1，对于e_ij∈E∩e_i'j'∈E'，d(e_ij,e_i'j')值不变，对于$e_{\mathrm{ij}}\notin E\cap e_{i^{\prime }{j}^{\prime }}\notin E^{\prime },$令d(e_ij,e_i'j')=0对于令d(e_ij,e_i'j')=σ，其中σ为大于0的常数，对于令d(e_ij,e_i'j')=σ，其中σ为大于0的常数，则G=(V,E,μ,ν)和G'=(V',E',μ',ν')之间的边距离Dist_Edge为：${\mathrm{Dist}}_{\mathrm{Edge}}=\underset{a=0}{\overset{N}{\Sigma }}\underset{b=a+1}{\overset{N}{\Sigma }}\underset{a^{\prime }=0}{\overset{N^{\prime }}{\Sigma }}\underset{b^{\prime }=a^{\prime }+1}{\overset{N^{\prime }}{\Sigma }}Z\left[a\right]\left[a^{\prime }\right]Z\left[b\right]\left[b^{\prime }\right]d(e_{\mathrm{ab}},e_{a^{\prime }{b}^{\prime }})---\left(18\right)$当图G=(V,E,μ,ν)与G'=(V',E',μ',ν')中顶点数目不同时，额外的匹配代价Penal(G,G')为：$\mathrm{Penal}(G,G^{\prime })=\frac{\mathrm{fabs}\left(\right|\left|V\right||-|\left|V^{\prime }\right|\left|\right)}{\left|\right|V\left|\right|+\left|\right|V^{\prime }\left|\right|}---\left(19\right)$其中||·||表示图中顶点数目，fabs(·)为取绝对值操作，图G=(V,E,μ,ν)和G'=(V',E',μ',ν')之间的距离Dist(G,G')为：Dist(G,G')=Dist_Node(G,G')+Dist_Edge(G,G')+Penal(G,G')（20），距离Dist(G,G')即为G=(V,E,μ,ν)和G'=(V',E',μ',ν')之间的相似度。