American University of Armenia
Optimization Project
Spring 2018

Abstract

点模式匹配的问题如下:您有一个点模式数据库(例如，不同的手写字母)，您观察一个新模式，您的任务是从数据库中识别最接近这个新模式的模式。当然，人们过去常常使用神经网络来完成这个任务，但是这个项目将致力于解决方案的转换最小化方法。

关键词:点模式匹配，向量，优化，手写字符，错误，Hession，相似变换，旋转。

1、Introduction

当图像较大，点较少时，点模式匹配比其它图像识别技术更有效。在这种情况下，它的速度和灵活性帮助它成为最优算法。

我们在这个项目中要解决的一个问题叫做点模式匹配问题。在点模式匹配问题中，诸如打印或手写的字符、数字、符号，甚至是制造部件的轮廓都可以用一组点来描述，
$P={p_1,p_2,...,p_n}\quad\quad\quad(1)$P=p1​,p2​,...,pn​(1)
其中
$p_i=\begin{bmatrix}p_{i1}\\ p_{i2}\end{bmatrix}$pi​=[pi1​pi2​​]

是关于第$i$i个采样点的坐标的向量。当$P，n$P，n中的点数足够大时，我们将得到我们期望的结果，并将$P$P视为对象的点模式。在这种情况下，方程(1)将准确地描述对象。我们可以用不同的点模式来表示物体。当我们从不同的距离和/或角度看物体时，这就会发生。在缩放旋转和平移中检查两个给定的模式是否匹配是一个有趣的问题。

我们考虑的模式匹配问题可以这样形成：我们有一个包含$N$N个标准点模式$\{P_1，P_2，…，P_n\}${P1​，P2​，…，Pn​}的数据库，其中每个$P_i$Pi​都具有等式(1)的形式，我们需要从数据库中找到与给定点模式$Q=\{ q_1,q_2,...,q_n \}$Q={q1​,q2​,...,qn​}最匹配的模式。为了解决这个问题，我们需要注意两件事。首先，我们需要理解“最佳匹配”是什么意思。其次，我们需要解出一个解决方案方法，从数据库中找到一个最佳的模式$P^∗$P∗，它将根据所选的度量与模式$Q$Q最佳匹配。

2、Application

点模式匹配广泛应用于航天、文件处理、计算生物学和计算化学等领域。

它被用于航天领域，特别是柏林技术大学航空航天研究所用于确定tubsat卫星的姿态。他们身上有照相机，可以拍摄天空。这些图像用于将星图与星表信息相匹配，并有助于控制卫星的位置和方位。

在生物学和化学中，它被用于放射自显影比对、药物共混鉴定和蛋白质结构比对。

3、Similarity transformation

所以，我们说对于同一个物体，我们可以有两点模式$P和P’$P和P’。如果我们可以通过对另一个应用缩放旋转加平移来获得一个图案，则可以称之为相似图案。如果模式$P$P由式(1)给出，和
$P'=\{ p_1',p_2',...,p_n' \}$P′={p1′​,p2′​,...,pn′​}
其中
$p_i'=[p_{iq}',p_{i,2}']^T$pi′​=[piq′​,pi,2′​]T
$P$P和$P′$P′是相似的，当且仅当存在旋转角$\theta$θ、缩放因子$η$η和平移向量$r=[r_1,r_2]^T$r=[r1​,r2​]T时，使得关系
$p_i'=\begin{bmatrix} cos\theta & -sin\theta\\ sin\theta & \cos\theta \end{bmatrix} p_i+\begin{bmatrix} r_1 \\ r_2 \end{bmatrix}\quad\quad(2)$pi′​=[cosθsinθ​−sinθcosθ​]pi​+[r1​r2​​](2)
对于$i = 1,2，…，n$i=1,2，…，n成立。这种将模式P映射到模式Q的转换称为相似转换。由式(2)可知，相似变换的特征是参数列向量$[\eta,\theta r_1r_2]^T$[η,θr1​r2​]T。

我们可以看出，相似变换是参数$η和θ$η和θ的非线性函数。由于这种非线性，优化过程所需的计算量可能会增加。我们可以通过应用变量替换来解决这个问题。
$a=\eta cos \theta, b=\eta sin \theta$a=ηcosθ,b=ηsinθ
代入式（2）中得到
$p_i'=\begin{bmatrix} a,&-b \\b,&a \end{bmatrix} p_i + \begin{bmatrix}r_1\\r_2 \end{bmatrix}\quad\quad(3)$pi′​=[a,b,​−ba​]pi​+[r1​r2​​](3)
所以参数向量变成了$x=[a,b,r_1,r_2]^T$x=[a,b,r1​,r2​]T。相似变换与参数线性相关。

4 、Problem formulation

在解决实际问题时，用户选择的点模式Q与数据库中的点模式完全相同的概率接近于零。我们所能做的就是在相似变换中找出最接近Q的模式。让
$q=\{ q_1,q_2,...,q_n \}$q={q1​,q2​,...,qn​}
是一个给定的模式
$P'(x)=\{p_1',p_2',...,p_n'\}$P′(x)={p1′​,p2′​,...,pn′​}
模式转换版本
$P=\{p_1,p_2,...,p_n \}$P={p1​,p2​,...,pn​}
让这些模式用矩阵表示
$Q=[q_1,q_2,...,q_n]\\P'=[p_1',p_2',...,p_n']\\和\\P=[p_1,p_2,...,p_n]$Q=[q1​,q2​,...,qn​]P′=[p1′​,p2′​,...,pn′​]和P=[p1​,p2​,...,pn​]，respectively。通过求解无约束优化问题，可以得到匹配$Q$Q的变换后的模式$P’$P’。
$\underset{x}{min}\quad ||P'(x)-Q||^2_F\quad\quad\quad(4)$xmin​∣∣P′(x)−Q∣∣F2​(4)
在||$\cdot$⋅||表示弗洛比尼厄斯范数。上述最小化问题的解对应于找到在frobenius意义下最小化模式$P'和Q$P′和Q之间差异的最佳变换。因为
$||P'(x)-Q||^2_F=\sum_{i=1}^{n} ||p_i'(x)-q_i||^2$∣∣P′(x)−Q∣∣F2​=i=1∑n​∣∣pi′​(x)−qi​∣∣2
得到了最小二乘意义下的最佳变换。现在，如果x是方程(4)中问题的最小化，
$e(P',Q)=||P'(x^*)-Q||_F\quad\quad\quad(5)$e(P′,Q)=∣∣P′(x∗)−Q∣∣F​(5)
那么误差是模式p’和q之间差异的度量。为了得到一个好的结果，$e(P',Q)$e(P′,Q)应该尽可能的小最好的情况是当它是零值的时候，这种情况我们称之为完全匹配。

5 Solution of the problem in Eq.(4)

由式(3)、式(5)可得


式（6b）中的hessian h是正定的，因此式（4）中的目标函数是全局严格凸的，因此具有唯一的全局极小。利用式（6a），目标函数的梯度为
$g(x)=2Hx-2b$g(x)=2Hx−2b
现在，如果我们想找到唯一的全局最小值
$gx=2Hx-2b=0 \\ x^*=H^{-1}b\quad\quad\quad(7)$gx=2Hx−2b=0x∗=H−1b(7)
为了证明矩阵H是可逆的，需要满足两个条件。首先它应该是一个方阵，即它应该有相同的行数和列数。第二，矩阵的行列式不应该等于零。在我们的例子中，$H$H是正定的$2×2$2×2矩阵，我们可以确定$H^{-1}$H−1是存在的。H的逆可以计算如下。设A是2×2的非零行列式矩阵。
$A=\begin{bmatrix}a&b \\ c&d \end{bmatrix}$A=[ac​bd​]
然后
$A^{-1}= \frac{1}{det(A)}\begin{bmatrix}d&-b \\ -c & a\end{bmatrix}$A−1=det(A)1​[d−c​−ba​]
其中$det(A)=ad-bc$det(A)=ad−bc，它是2×2矩阵。

6、Alternative measure of dissimilarity

如式（6a）所示，矩阵的frobenius范数与列向量的$L_2$L2​范数有关。如果我们定义两个新的向量$p’ (x)$p’(x)和$q$q
$p'(x)=\begin{bmatrix}p_1'(x)\\ p_2'(x)\\ \cdot \\ \cdot\\ \cdot \\p_n'(x)\end{bmatrix} and \quad q=\begin{bmatrix}q_1\\ q_2\\ \cdot \\ \cdot\\ \cdot \\q_n\end{bmatrix}$p′(x)=⎣⎢⎢⎢⎢⎢⎢⎡​p1′​(x)p2′​(x)⋅⋅⋅pn′​(x)​⎦⎥⎥⎥⎥⎥⎥⎤​andq=⎣⎢⎢⎢⎢⎢⎢⎡​q1​q2​⋅⋅⋅qn​​⎦⎥⎥⎥⎥⎥⎥⎤​
由式(6)可知