一种求解二次图匹配模型的方法

摘要

一种求解二次图匹配模型的方法，该方法在给定图匹配模型和容忍满足所有约束条件的图像匹配矩阵时，首先在容忍满足等式约束的条件计算图匹配目标函数的上升方向，然后在至少有一个等式约束和不等式约束的违反超过容忍度时，计算回拉梯度矩阵增量并执行回拉操作，以保证整个迭代计算上升方向的过程在容忍满足所有约束的条件下进行。其中，当对某个不等式约束的违反超过容忍度时，意味着该不等式约束此时能够提供可行域的部分边界信息，故将被暂时当作等式约束处理用于上升方向的计算。本方法的创新之处在于提供一种求解图匹配问题的非线性规划方法，可广泛应用于解决计算机视觉领域的对象检测、特征跟踪、图片分类、形状匹配和图片检索等问题。

主权项

一种求解二次图匹配模型的方法，在给出具体的算法内容之前，这里先给出图匹配模型的问题描述；在图匹配模型中，定义一组图像匹配对pair(G,G′)，其中G为第一幅图像特征点组成的图，G′为第二幅图像特征点所组成的图；其特征在于：G_i(G′_i′)表示图G(G′)中的第i个顶点，G_ij∈{0,1}(G′_i′j′∈{0,1})表示图中由G_i(G′)及G_j(G′_j′)所组成的边，若G_ij＝1(G′_i′j′＝1)则边G_ij(G′_i′j′)存在，否则不存在；定义图像匹配矩阵x(x_ii′∈{0,1})，如果x_ii′＝1表明图G中的顶点G_i与图G′中顶点G′_i′存在一致性对应关系，x_ii′＝0则相反；定义c为点配对矩阵，其中c_ii′为点匹配对pair(G_i,G′_i′)的权重，同理，定义d为边配对矩阵，其中d_ii′jj′为边配对pair(G_ij,G′_i′j′)的权重；那么图匹配问题就转化为求解最优图像匹配矩阵x^*，以使二次规划目标函数达到最大化：$x^{*}=\underset{x}{\mathrm{argmax}}[\underset{{\mathrm{ii}}^{\prime }}{\Sigma }{c}_{{\mathrm{ii}}^{\prime }}{x}_{{\mathrm{ii}}^{\prime }}+\underset{{\mathrm{ii}}^{\prime }{\mathrm{jj}}^{\prime }}{\Sigma }{d}_{{\mathrm{ii}}^{\prime }{\mathrm{jj}}^{\prime }}{x}_{{\mathrm{ii}}^{\prime }}{x}_{{\mathrm{jj}}^{\prime }}]$$subjectto:{\Sigma }_i{x}_{{\mathrm{ii}}^{\prime }}=1,\forall i^{\prime },{\Sigma }_{i^{\prime }}{x}_{{\mathrm{ii}}^{\prime }}=1,\forall i$其中1≤i,j,i′,j′≤m，m表示图G和G′中的顶点个数，即要求图像匹配矩阵的每一行元素之和为1、列元素之和为1；图像匹配矩阵x(x_ii′∈{0,1})为0‑1矩阵，而为了计算方便，该矩阵首先定义为连续变量，并增加约束条件x_ii′≥0,只在最后一步做相应整数处理就得到真实的0‑1匹配矩阵；为便于后续描述，将上述的图匹配问题转化为标准的非线性规划模型：max f(vec(x))＝vec(x)^Tvec(c)+vec(x)^Tdvec(x)$s.t\left\{\begin{array}{c}{g}_1\left(x\right):{\Sigma }_1{x}_{1i^{\prime }}-1=0\\ \mathrm{...}\\ g_m\left(x\right):{\Sigma }_l{x}_{{\mathrm{li}}^{\prime }}-1=0\\ g_{m+1}\left(x\right):{\Sigma }_1{x}_{i1}-1=0\\ \mathrm{...}\\ g_{2m}\left(x\right):{\Sigma }_m{x}_{im}-1=0\\ h_1\left(x\right):x_{11}\ge 0\\ \mathrm{...}\\ h_{m^2}\left(x\right):x_{m^2}\ge 0\end{array}\right.$其中vec(x)、vec(c)分别为图像匹配矩阵x和点配对矩阵c的列展开向量，vec(x)^T为的vec(x)转置，g_k(x)、h_p(x)(1≤k≤2m,1≤p≤m²)分别表示匹配矩阵的每一行向量元素之和为1，每一列向量元素之和为1以及匹配矩阵的元素大于等于0的等式和不等式约束；m表示图G和G′中的顶点个数；2m为等式约束的个数；m²为不等式约束的个数。