英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
摘 要
图像识别的一个根本问题是建立两个图像的相似性，这个可以通过寻找最后像素到考虑了单调性和约束性的像素映射来完成。我们发现这个问题是NP完全还原3-SAT，从而有证据表明，已知的指数时间算法是合理的，但近似算法和简化是必要的。
关键词：弹性图像匹配；二维变形；NP完全问题。
目 录
第1章 介 绍
在图像识别中，一个共同的问题是匹配给定的两个图像。例如，比较观察图像，给出参考。在这个过程中，弹性图像匹配，二维翘曲或相似类型不变量方法可以运用。为此，我们可以通过在图像匹配中引入的失真定义成本函数，从而对给定成本函数搜索出最佳匹配。在本文中，我们发现决定两个匹配图像间是否存在成本低于某一阀值是一个复杂算法问题。我们还发现这个图像匹配问题是个通过从3-SAT减少的NP完全问题，这是一种常见的表明问题内在困难的方法（加里和约翰逊，1997）。这一结果表明，这种类型的图像比较存在固有的计算困难。而有趣的是，同样的问题在多项式时间算法中是可解的一维序列。例如，语音识别中的时间翘曲问题（参见例如奈伊等人，1992）。这有以下几种含义：对这一问题准确答案感兴趣的研究人员不能希望找到一个多项式时间算法，除非N=NP。此外，人们可以得出这样的结论，被内田和撒克提出并延长的指数时间算法可以认为是有正当理由的一些图像匹配应用。另一方面，这表明，对更快算法如模式识别感兴趣的人在寻找次优解决方案中是正确的。一种方法是限制凯塞斯等人2000年提出的在全球变革中的局部优化和线性近似，另一种可能性是使用启发式方法，如用模拟退火和遗传算法找到一个近似解。此外，束搜索的方法如有希望的候选人。因为这些被成功地用于语言识别，虽然语言解码也是一个NP完全问题（看瑞波特和德拉1999年提出）。
第2章 图像匹配
在各种各样的匹配算法中，我们选择钗达和撒克1998年提出的作为形成图像匹配的一个起点。在不丧失概括性的条件下，在一个有限字母表中让图像和分别为节点标签的灰度值作正方形网络大小的运动。为了定义这个问题，需要两个距离函数，一个相当于灰度值，，测量在灰度值中的匹配性。另一个相当于位移的差异，，测量由匹配引起的失真，对那些距离函数，我们假定它们在常用的平方距离中是可计算多项式时间的单调函数。即：随着的单调增长，且。现在我们称下面的优化问题为图像匹配问题（令）。
实例：大小为的两个图像和的匹配。
结论：A的映射函数:。
方法：
目的：求。换句话说，主要问题是找到从到的映射，从而缩小映射灰度值和由映射引入的衡量失真之间的距离。这儿的失真是通过二维平面内恒等映射的偏离来测量的，恒等映射实现,因此。
相应的判断问题可以通过以下来说明。
问题：给出一个图形匹配的例子和损耗，那么是否存在一个映射使。
在定义一些问题的时候，必须注意采用的距离函数。例如，如果任何一个距离函数是连续函数，那么在映射中问题就会有很明显的连续，最小值用恒等映射给出，连续，最小值可以通过灰度值成本和映射到一个像素中的最小成本在每个像素所有可能匹配到的排序中确定，但是一般而言，这些特殊的情况不是我们在图像匹配中所关注的。
我们选择钗达和撒克的匹配问题去完成问题的定义，这里的映射函数受连续性和单调性的限制：恒等映射中出现的误差最多可以是一个像素（即限制八邻域的平方欧氏距离小于或等于2），用这种方法可以通过选择函数作为例子来形成，即
第3章 降低3-SAT
3-SAT是一个非常著名的NP完全问题（加里和约翰逊，1997），在这一问题里，3-SAT定义如下：
例如：收集变量，一组变量，这样每个由3个常量构成，每个文字是一个变量或一个常量。
问题：是否有一个变量，其每个值都满足？
对应3-SAT例子的图的独立性定义为偶图，它的独立集是由一套条款和设置的变量构成。两定点和相邻，当且仅当涉及或。给定任意3-SAT公式，我们将展示在多项式里如何构建一个相当于图像匹配问题。的这两个图像相似度取决于是否满足相似度条件的公式,当满足时，我们使用一下步骤从3-SAT中实现减少匹配数：
（1）在公式中，我们构建了图D（Ф）的独立性。
（2）将图的独立性绘制在平面上。
（3）绘制的精致取决于对逻辑行为的描绘，产生两个图像。
为此，我们使用三种类型的组成部分：一个部分代表变量，一个部分代表条款，以及组件作为前两个类型的接口。在我们给予正式的减少之前，我们介绍这些组件。
3.1 基本组件
为了从3-SAT中减少，我们需要从我们即将建设的实例图像匹配中拿出五个组件，在3-DNF中给出一个布尔公式。对应各自的图，五组件是在图形描绘中所需要建设的块，随后将被连接，即表示连接器，插口，变量和条款。连接器代表边缘有两种：直连接器和角连接器。每个组件由两部分组成，一个图像和一个图像，在图像中白像素被认为是背景颜色。下面，我们将用指示方向位移的箭头描述可能的映射（如像素的周围位移是唯一被考虑的条件），空白的方块代表各自对应图像的映射。例如，下面相邻像素的位移为零：
（a） （b） （c） （d） （e）
图3.1 零位移
另一方面，以下位移大于零：
（a） （b） （c） （d）
图3-1 正位移
图3-1显示的第一个组成部分，直连接器组件包括一个用两种不同颜色互换表示的直线，这里用◇和□两个符号表示。鉴于外面像素被映射到各自相应的部分及连接器是无限连续的，彩色像素被映射有两种可能途径，即左或右，背景像素的映射有不同的可能性，不影响连接器的主要性能。这个证明连接器名字的性能如下：它不可能找到一个映射，产生零成本相对位移不相等的连接器，例如，引入就很容易观察
到.
（a）图像A （b）图像B
（c）映射1 （d）映射2
图3-2 有两个可能的零成本映射的直连接器组件
也就是说，给定一个初始位移的像素（在本文中可以plusmn;1），如果总成本的映射是零，那么连接器其他的接口就具有相同的位移。鉴于这种性质和方向的连接器，它是我们根据变量和条款定义的，我们可以根据连接器的状态进行真实真理价值的评价，如果在连接器的位移方向上是1像素并且携带假真值，或者如果在连接器的位移方向上是-1像素。此属性确保连接器传输真值不能改变映射是零成本。
绘制任意图形，显然都需要角度，如图3-2所示。考虑所有可能保证总成本为零的位移，任何一个人都能看到角元素也能确保基本连接器的属性。例如，考虑第一个被描述的图，它是属于零成本。另一方面，第二张图说明，用所有脱离组件的连接器构成零成本图是不可能的。在这种情况下，在位置上标记了“*”的像素跟它上面或者它右边的像素发生干涉（也就是由于映射不匹配在准则函数中引入的成本大于零），如果相同颜色相遇，否则在灰度值不匹配术语中将引入更多成本。
（a）图像A （b）图像B
（c）映射1 （d）映射2
图3-3 角落连接器组件和两个例子映射角落
图3-2表明，带有两个阳极（左）和一个阴极输出（右）的可变部分作为连接器，在这里用四分之一的颜色表示。这部分有可能映射为零成本的彩色像素。可变部分带有两个阳极和一个阴极输出还有可能的映射（真假真值）。
左边或右边的原图像的可变部分各自在目标图像之中，（在这两个例子里目标图像中的第二个可变元素不是映射的目标）。这可以确保在连接器的入口处有plusmn;1的像素相对位移，这种属性可以通过两种图像所有可能的映射再次被减少，下述属性（使用可变因素是必要的）是所有零成本映射确保所有的阳极连接器执行相同的真理价值，它执行与阴极连接器相反的真理价值。从这个例子很容易看出关于阳极和阴极输出的任意数字的可变组件是怎样构成的。
图3-3表明最复杂的零件是条款的组成部分。该零件包含两部分。第一部分是相邻右边弯曲的横向连接器，这部分的属性是和的所有真值价值与假值除外的价值可以实现零成本映射。使用左下方的一部分可以使这两个输入端扩展为三个输入端口。如果连接器执行错误的真理价值，那么这部分仅仅可以以零成本映射下面的一个像素。在那
（a）图像A （b）图像B
（c）映射1（lsquo;真rsquo;） （d）映射2（lsquo;假rsquo;）
图3-4 两个正和一个可变部分否定的输出和可能的映射（例如，真假真值）
种情况下，交界处的像素不能以零成本映射到上面或者按上面所述的两输入条款进行映射。另一方面，如果连接器执行真实真理价值，那么这部分仅仅可以以零成本映射到上面一个映射，同时交界处像素可以映射到上面，因此允许和在零成本映射中都执行错误真理价值。因此存在条款组成识别系统的零成本映射至少有一个输入连接器实现真实真理价值。已描述组件已经通过从平面3-SAT（它是在有特殊限制如依赖图形是平面的情况下的3-SAT中的一个NP完全潜在问题）中减少的问题有效的证明了NP完全问题。但是为了从3-SAT中得到减少，我们也需要考虑交叉连接器的可能性。
图3-5表示连接器的交叉，它的基本属性是在真理价值一贯传播的情况下允许零成本映射，这个可以通过垂直连接器和一个复杂中间部分（它可以通过真理价值的分布映射到四个不同的位置）的颜色改变来保证。
（a）图像A
（b）图像B
（c）映射1（真，真，假）
（d）映射2（假，假，真）
图3-5 三个转入连接器组件,,和两种情况下零成本映射（真，真，假）（假，假，真）
3.2 减少问题
通过先前介绍的组件，我们现在可以演示从3-SAT中的减少到图像匹配的过程。
证明图像匹配问题是NP完全问题:
显然，NP完全问题是在NP中，给定一个映射和两个图像和，可以在多项式中得出。为了证明度数，我们从3-SAT问题中构造一个减少问题，给出一个3-SAT的例子，我们构造两个图像和，如果所有的条款都满意零成本映射就存在。
给定附属图表D，我们把图表嵌入构建成二维像素模板，把镜头放在相距彼此足够的距离上（100（K L）sup2;）。这可以由著名的图表方法来完成。通过表D中的图像我们用上述组件构造两个图像和，属于变量的每个镜头可以被可变组件的每个部分所替代，大量剩余连接器与在阴极或阳极应用于各自的条款这种考虑下的大量入射边缘相等。每个镜头属于可以被各个条款部件代替的条款，并且每个边缘的交叉可以被各个交叉部分所替代。最后，所有的边缘被连接器和隐蔽连接器替代，并且在建造的矩形外壳里剩下的像素被用于背景灰度值。很明显，组件的布局可以通过所有的组件
全文共8589字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13580]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
