改进的RANSAC匹配点提纯算法

第４５卷第６期　西　安　建　筑　科技　大　学　学　报（自然科学版）　Ｊ．Ｘｉ　ａｉ１　Ｕｎｉｖ．ｏｆ　Ａｒｃｈ．＆Ｔｅｃｈ．（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．４５　Ｎｏ．６　Ｄｅｃ．２Ｏ１３　２０１３年１２月　改进的ＲＡＮＳＡＣ匹配点提纯算法　介　军　，李智杰　，姚　鹏　（１．西安建筑科技大学信息与控制工程学院，陕西西安７１００５５；　２．长庆油田分公司机械制造总厂，陕西西安７１０２０１）　摘　要：针对在图像匹配中，随机抽样一致性（ＲＡＮＳＡＣ）算法对匹配点提纯存在计算量大、效率低的问题，采　用将基本矩阵作为模型参数估计对象的方法，对ＲＡＮＳＡＣ匹配点提纯算法进行了改进．在改进的算法中，运　用Ｂｕｃｋｅｔ分割技术抽取粗匹配点对，进行两幅图像的检测角点和粗匹配，利用视差梯度对匹配点样本预检　验．实验结果表明，此方法在保证较高精度和鲁棒性的情况下，运算量大幅度减少，提高了图像匹配的速度．　关键词：角点检测；图像匹配；视差梯度；ＲＡＮＳＡＣ　中图分类号：ＴＰ　３９１．４ｌ３　文献标志码：Ａ　文章编号：１００６—７９３０（２０１３）０６—０８９６—０６　图像匹配是当前研究的热点问题之一，也是计算机视觉领域中相关理论的基础．在图像匹配的众多　方法中，目前应用最广泛、研究最多的方法是基于特征的匹配［１　方法，它根据原图像中特征趋于稳定、数　量不是太多等具有明显标记的的一些点、线、边缘等进行图像的匹配，使得在处理过程中能尽可能的减　小运算数据量，具有较高的运算速度和效率，且对图像灰度变化具有很强的适应性．美中不足的是，基于　特征的匹配仍需要在不同图像中进行大量的遍历性匹配运算．这样会使得匹配过程中存在计算量很大，　且精度不高的问题．　本文采用Ｈａｒｒｉｓ算法提取不同角度的左右两幅图像的角点，利用灰度归一化互相关对角点进行粗　匹配，然后基于改进的随机抽样一致性（ＲＡＮｄｏｍ　ＳＡｍｐｌｅ　Ｃｏｎｓｅｎｓｕｓ，ＲＡＮＳＡＣ）算法进行精匹配．在　改进的算法中，使用反映两幅图像像素坐标关系的基本矩阵作为模型参数估计对象，采用Ｂｕｃｋｅｔ平面　分割技术分块抽取粗匹配点对避免分布过于集中，利用视差梯度对参与模型计算的粗匹配点样本预检　验以减少不必要的模型验证，在确保精度的前提下，大大减少了计算量，提高了运算速度．　１　角点提取和粗匹配　角点是指在至少两个方向上图像灰度变化均较大的点．在实际的图像中，角点可以是两条直线的交　汇处或者图像轮廓的拐角点、甚至是线段的末端等都可以称之为角点．本文采用Ｈａｒｒｉｓ算法检测角点，　采用使用最多的基于窗口的归一化互相关函数对角点粗匹配．　１．１角点提取　Ｈａｒｒｉｓ算法ｌ＿３　定义的基础是如下定义的图像灰度强度的二阶导数矩阵：　ａ　Ｉ　８ｘ　ａ　Ｉ　８ｘＯｖ　Ｍ：＝　ａ０Ｉ　ＯｘＯｙ　ａ　工　ａ、１　其中：Ｊ为图像灰度强度；５Ｃ与　为图像像素点的横坐标和纵坐标．Ｈａｒｒｉｓ角点的响应函数为：　Ｈ＝＝＝　１　２——ｋ（　ｌ＋　２）　（２）　其中　，　为矩阵为式（１）中Ｍ的两个特征值，根据Ｈａｒｒｉｓ建议，是的取值为０．０４，特征点就是此　收稿日期：２０１３－０１—１４　修改稿日期：２０１３—１卜２５　基金项目：国家自然科学基金资助项目（５０８７８１７６）　作者简介：介军（１９７１一），男，陕西彬县人，工程师，硕士，主要从事计算机应用和教学研究　第６期　介军等：改进的ＲＡＮＳＡＣ匹配点提纯算法　８９７　函数的局部最大值．　１．２粗匹配　角点粗匹配是利用角点附近的灰度信息，采用归一化互相关方法，对于左图像中每一个角点，建立　一个局部匹配的准则．角点粗匹配计算其所有角点的归一化互相关系数．　归一化互相关函数定义如下：　ｋ　Ｚ　∑∑ＥＩ（ｕ＋　，　＋　）一　］×［　（　＋　，　＋　）一了７　］　（３）　公式中，ｋ、ｆ是两个互相关窗口的宽度，一般取ｋ—ｌ，　表示的是灰度平均值（以点（“，　）为中　心）．　计算结果为相关系数Ｃ，Ｃ取值越大，则证明角点　表１　角点互相关匹配矩阵　相关程度越大，这里Ｃ的取值为：一１＜Ｃ＜１．　Ｔａｂ．１　Ｍａｔｃｈｉｎｇ　ｍａｔｒｉｘ　ｏｆ　本文通过计算角点互相关匹配矩阵，来获取匹配　点．查找原则为：遍历矩阵中的每一行数据，找出最大　值，然后再找出该大值所对应的一列，如果此最大值也　是这一列的最大值，那么就可以确定这是一对匹配点．　互相关矩阵如表１所示，其中左侧为左图像中角点　编号，右侧为右图像中角点编号．　２　图像的精匹配　精匹配的目的就是消除粗匹配中的伪匹配点，目前比较有效而且通用的方法就是由Ｆｉｓｃｈｌｅｒ和　Ｂｏｌｌｅｓ提出的ＲＡＮＳＡＣ算法嘲，它对超过５Ｏ％的伪匹配点仍然有效，是一种模型参数估计算法．但是　该算法计算量大并且模型参数不稳定等因素导致了较低的匹配率，基于此问题，本文采取基于视差梯度　和Ｂｕｃｋｅｔ平面分割技术的ＲＡＮＳＡＣ算法来估计基本矩阵，通过基本矩阵剔除伪匹配点，达到图像的　精匹配．　２．１基本矩阵及其估计　极几何的代数形式通常用基本矩阵表示，基本矩阵描述了一幅图像上的像素点与另一幅图像上对　应极线之间关系，以及摄像机的内参数信息［６］，对极关系描述形式如式（４）所示：　，ｒＦ　ｆ一０　（４）　其中，Ｆ是的３×３的基本矩阵，ｍ　和ｍ　是左右两幅图像的一对匹配点，ｍ　一（ｚ　，Ｙ　，１），ｍ　一　（ｚ　，Ｙ　，１）是像素的齐次坐标形式来展示．　基本矩阵的估计方法有多种，典型的也是最常用的有７点法、８点法和基于几何误差的非线性优化　算法等等　引，一般的方法就是以下的８点法，对于　和ｍ　．，按照式（４）可以展开为　７３　ｚ　－厂１ｌ＋ｚ　ｆＹｆｆ１２＋ｚ　厂１３＋ｙ＇ｉｘｌｆ２１＋　｛ｆ２２＋３，ｔ　厂２３＋ｚ　ｆ３１＋Ｙｉ厂３２＋ｆ３３—０　（５）　用矢量，表示由Ｆ的元素组成并按行优先顺序排列的９维矢量，式（５）可以表示为一个矢量的内　积　（ｚ　ｆ　，　Ｙ　，ｚ　，　ｚ　，　ｔ　Ｙ　，Ｙ　ｆ，　，Ｙ　，１）ｆ＝０　（６）　如果有ｎ组点对，可以得到如下的线性方程组：　Ｐｌ１　１；７１１－　ｚ　１Ｙ　ｚ　１　Ｙｌ　１　　Ｙ　ｔ１ｚ１ｚ１　　Ｙ　Ｙａ１Ｙ１　　Ｙ　１１　ｚ１　Ｙｌ　　１］　］　Ａｆ—ｌ　ｉ　ｉ　ｉ　；　；　ｉ　ｉ　！　；Ｉ　ｆ一０　（７）　ｆ　ｚ　ｔ　ｎｚ＂ｔｔｚ　　ｎＸ　ｚ＂ｚ　　Ｙ　ｎＸ　ｎ　Ｙ　Ｙ　Ｙ　ｎ　ｚ　Ｙ　１ｚ”　ｎＹ　　．ｊｆ　根据矩阵描述的数据可以看出，假如矩阵Ａ的秩等于８，那么就可以进行线性求解该方程组，并且　存在惟一的解．然而在实际情况中，点的坐标含有一定的噪声，造成矩阵的秩在有些情况下不等于８．对　８９８　西安建筑科技大学学报（自然科学版）　第４５卷　矩阵Ａ进行最小二乘解，然后再进行分解，即Ａ—ＵＤＶ　，Ｖ的最后一列矢量，在ｌＪ　ｆ『ｌ一１且｛ｌ　ＡＦ　ｌ　ｌ的值最小的条件下，即为最小二乘解．　２．２　ＲＡＮＳＡＣ算法　ＲＡＮＳＡＣ算法是一种简单而巧妙的算法．ＲＡＮＳＡＣ算法的计算量由两部分组成口］：（１）抽样选择　和模型估计需要的时间；（２）模型参数检验需要的时间．　ＲＡＮＳＡＣ算法可总结如下：　（１）求出满足要求的最小抽样数Ｄ：根据计算模型参数需要的最小数据量ｄ、数据错误率￡和置信　概率Ｐ，利用式（８），　１一（１一（１一￡）　）。一Ｐ　（８）　（２）计算参数化模型：从原始数据Ｓ中随机选取一定量的数据点样本，一般采用数据量为ｄ作为标准．　（３）计算当前模型的支撑点集：使用原始数据作为参考，对模型数据进行检验计算，得到模型的支撑　点的数量．　（４）返回第（２）、（３）步，重复进行计算Ｄ次，找出最优模型．　（５）根据第四步得到的最优模型，获得其所对应得支撑点集合，得到最终模型参数．　２．３　改进的ＲＡＮＳＡＣ算法　从上文ＲＡＮＳＡＣ算法描述来看，算法还有可以改进优化之处．可以从抽样选择以及模型参数验证　这两个方面进行优化改进，本文利用平面分割技术和视差梯度分别解决匹配点在空间上分布不均的问　题和减少模型参数验证次数，这样获得的模型参数更具有代表性．　从相关参考文献中视差梯度的定义＿８　得出结论：在一幅图像中，如果Ｐ，ｑ和Ｐ　，ｑ　分别是两幅图像　中两个相邻角点，若角点Ｐ，ｑ分别与角点Ｐ　，ｑ　匹配，并且是相容的，那么通过计算公式得出的视差梯　度Ｇ　应不大于２；否则，两个角点就被认为是不匹配的．视差梯度的公式为：　Ｇ　—ｚ牦每寿　其中，ＩＩ　Ｐ　ｌＩ表示向量Ｐ的模，（　，ｐ）和（ｑ　，ｑ）分别是图像对应角点的坐标向量．　法，从不同方面进行描述可以有效地弥补灰度相关的不足之处，并做出改善．　㈤　视差梯度区别于灰度相关的一般性质，此种方法从另外一个角度来描述角点之间的匹配模式与方　在使用ＲＡＮＳＡＣ方法进行模型参数估计的过程中，如果在空间中使用的随机算法随机抽取点集　有较大的聚合性，经过计算得出的基础矩阵Ｆ将会有很差的稳定性，最后得出的结果也会有较大的误　差．根据经验，可以将图像平面进行网格划分，这里本文采用Ｂｕｃｋｅｔｓ平面分割技术嗍｜１ｏ　形成若干个　Ｂｕｃｋｅｔｓ来减少误差，用归于每个Ｂｕｃｋｅｔ中的所有点的数目占总体点的数目比率的大小作为权值，采　用轮盘赌的方式，不重复的选择点集，能有效的解决点集分布过分集中的问题，并且增强基础矩阵的准　确性和稳定性．　改进的ＲＡＮＳＡＣ算法描述：　（１）根据图像所有角点性质，利用归一化互相关方法建立Ｎ个粗匹配角点对．　（２）根据角点在图像上的位置将匹配点对等大小的划分成ｍ个不同的Ｂｕｃｋｅｔ，计算权值，统计并计　算所有Ｂｕｃｋｅｔ中的角点数Ｎ　，ｉ一１，２，３，…，ｍ，这样每个Ｂｕｃｋｅｔ的权值为Ｐ　：Ｎ　／Ｎ．　（３）根据式（８）计算最小随机抽样数Ｄ．　（４）根据每个Ｂｕｃｋｅｔ的权值Ｐ　，采用轮盘赌的选择方式抽取一个没有重复匹配点对的大小为８的　样本．　（５）设定阈值ｍａｘＴＤ，如果计算所得样本中视差梯度总和，若大于ｍａｘＴＤ，转回第（４）步骤进行重　新抽样；否则，继续执行下一步算法．　（６）计算抽样基础矩阵　，利用８点算法．　（７）将所有的初始匹配点对代入公式（５），使得Ｙ　＝ｍ＇ｉＴＦ　ＩＴｔ　，如果ｙ　的值在区间［口，　中，记录统　计点的数目Ｎ　，以及所对应的角点，重复第（４）～（７）步骤，一直到完成Ｄ次随机抽样为止．　９００　西安建筑科技大学学报（自然科学版）　第４５卷　与原始匹配点集的抽样数量大大减少，匹配的时间减少到１．８１２ｓ．上文中图２显示了使用改进后的算　法所得到的结果，图像中存在的粗匹配点用“ｏ”标出，可以看到在“ｏ”中标“口”符号，表示的是算法剔　除的伪匹配点，将会被处理掉．　表２改进的算法与原算法时间的比较　Ｔａｂ．２　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｉｍｅ　ｃｏｎｓａｍｅｄ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　为了检验本文算法的通用性，选用３组具有代表性的图像，　将本文的算法与原ＲＡＮＳＡＣ算法进行了对比，由表３可以看　出，改进的算法在保持了精度的同时，提高了计算速度．同时，在　最小抽样数一定的前提下，通过不同分辨率，不同场景的图片进　行匹配，得出了在两种算法中粗匹配点数与匹配时间的关系，由　图３可知，随着粗匹配点数的增加，两种算法的匹配时间都在增　加，但是匹配时间差则越来越大，在粗匹配点较多时，改进算法　的优势更为明显．　４结论　三　针对ＲＡＮＳＡＣ方法进行图像角点精匹配时速度慢、实时ｐｏｉｎｔｓ　ａｎｄ　ｔｈｅ　ｍａｔｃｈ　ｔｉｍｅ　性差的问题，本文改进了ＲＡＮＳＡＣ算法．在改进的算法中，以　基本矩阵作为模型参数估计对象，采用Ｂｕｃｋｅｔ图像分割技术分块抽取粗匹配点对，利用视差梯度对抽　取的匹配点对预检验．实验证明，此方法在保证较高精度和鲁棒性的情况下，运算量大幅度减少，提高图　像匹配的速度．　参考文献　Ｒｅｆｅｒｅｎｃｅｓ　［１］ＺＨＵ　Ｑ，ＷＵ　Ｂ，ＸＵ　Ｚ．Ｓｅｅｄ　ｐｏｉｎｔ　ｓｅｌｅｃｔｉｏｎ　ｍｅｔｈｏｄ　ｆｏｒ　ｔｒｉａｎｇｌｅ　ｃｏｎ　ｓｔｒａｉｎｅｄ　ｉｍａｇｅ　ｍａｔｃｈｉｎｇ　ｐｒｏｐａｇａｔｉｏｎ［Ｊ］．　ＩＥＥＥ　Ｇｅｏｓｃｉｅｎｃｅ　ａｎｄ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ　Ｌｅｔｔｅｒｓ，２００６，３（２）：２０７—２１１．　［２］曲天伟，安波，陈桂兰．改进的ＲＡＮＳＡＣ算法在图像配准中的应用ＥＪ］．计算机应用，２０１０，３０（７）：１８４９—１８５１．　ＱＵ　Ｔｉａｎ－ｗｅｉ，ＡＮ　Ｂｏ，ＣＨＥＮ　Ｇｕｉ—ｌａｎ．Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｉｍｐｒｏｖｅｄ　ＲＡＮＳＡＣ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｉｍａｇｅ　ｒｅｇｉｓｔｒａｔｉｏｎ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，３０（７）：１８４９—１８５１．　［３］ＨＡＲＲＩＳ　Ｃ，ＳＴＥＰＨＥＮＳ　Ｍ．Ａ　ｃｏｍｂｉｎｅｄ　ｃｏｒｎｅｒ　ａｎｄ　ｅｄｇｅ　ｄｅｔｅｃｔｉｏｎ［Ｊ］．Ｉｍａｇｅ　Ｖｉｓｉｏｎ　Ｃｏｍｐｕｔｉｎｇ，１９９８，１５（６）：　１２１－１２７．　［４］徐玮．一种基于角点匹配的视图合成方法［Ｊ－Ｉ．系统仿真学报，２００７，１９（１４）：３２６３—３２６５．　ＸＵ　Ｗｅｉ．Ｃｏｒｎｅｒ　Ｍａｔｃｈｉｎｇ—ｂａｓｅｄ　Ａｐｐｒｏａｃｈ　ｏｆ　Ｖｉｅｗ　Ｓｙｎｔｈｅｓｉｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｙｓｔｅｍ　Ｓｉｍｕｌａｔｉｏｎ，２００７，１　９（１４）：　３２６３—３２６５．　［５］ＦＩＳＣＨＬＥＲ　Ｍ　Ａ，ＢＯＬＬＥＳ　Ｒ　Ｃ．Ｒａｎｄｏｍ　ｓａｍｐｌｅ　ｃｏｎｓｅｎｓｕｓ：Ａ　ｐａｒａｄｉｇｍ　ｆｏｒ　ｍｏｄｅｌ　ｆｉｔｔｉｎｇ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ　ｔｏ　ｉｍ—　ａｇｅ　ａｎａｌｙｓｉｓ　ａｎｄ　ａｕｔｏｍａｔｅｄ　ｃａｒｔｏｇｒａｐｈｙ［Ｊ］．ＣＡＣＭ，１９８１，２４（６）：３８１—３９５．　［６３　ＨＡＲＴＬＥＹ　Ｒ，ＺＩＳＳＥＲＭＡＮ　Ａ．Ｍｕｌｔｉｐｌｅ　Ｖｉｅｗ　Ｇｅｏｍｅｔｒｙ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ［Ｍ］．２ｎｄ　ｅｄ．Ｃａｍｂｒｉｄｇｅ　Ｕｎｉｖｅｒｓｉ—　第６期　介　军等：改进的ＲＡＮＳＡＣ匹配点提纯算法　９０１　ｔｙ，２００３．　［７］陈付幸，王润生．基于预检验的快速随机抽样一致性算法［Ｊ］．软件学报，２００５，１６（８）：１４３１—１４３７．　ＣＨＥＮ　Ｆｕ—ｘｉｎｇ，ＷＡＮＧ　Ｒｕｎ－ｓｈｅｎｇ．Ｆａｓｔ　ＲＡＮＳＡＣ　ｗｉｔｈ　Ｐｒｅｖｉｅｗ　Ｍｏｄｅｌ　Ｐａｒａｍｅｔｅｒｓ　Ｅｖａｌｕａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００５，１６（８）：１４３卜１４３７．　［８］马颂德，张正友．计算机视觉ＥＭ］．北京：科学出版社，１９９８：８２—８３．　ＭＡ　Ｓｏｎｇ—ｄｅ，ＺＨＡＮＧ　Ｚｈｅｎｇ－ｙｏｕ．Ｃｏｍｐｕｔｅｒ　ｖｉｓｉｏｎ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ　Ｐｒｅｓｓ，１９９８：８２—８３．　［９］ＣＨＯＵＫＲＯＵＮ　Ａ，ＣＨＡＲＶＩＬＬＡＴ　Ｖ．Ｂｕｃｋｅｔｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｒｏｂｕｓｔ　ｒｅｇｒｅｓｓｉｏｎ　ｆｏｒ　ｃｏｍｐｕｔｅｒ　ｖｉｓｉｏｎ［Ｃ］∥Ｉｎ　Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　ＳＣＩＡ　２００３　Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｈａｌｍｓｔｅｄ　Ｓｗｅｄｅｎ，２００３，２７４９：６０９—６１６．　［１Ｏ］黄以君，刘伟军．基于ＬＱＳ的基本矩阵计算方法［Ｊ］．中国图象图形学报，２００９，１４（１０）：２０６９—２０７３．　ＨＵＡＮＧ　Ｙｉ－ｊｕｎ，ＬＩＵ　Ｗｅｉ－ｊｕｎ．Ａ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｆｕｎｄａｍｅｎｔａｌ　Ｍａｔｒｉｘ　Ｅｓｔｉｍａｔｉｏｎ　Ｕｓｉｎｇ　ＬＱＳ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｉｍａｇｅ　ａｎｄ　Ｇｒａｐｈｉｃｓ，，２００９，１４（１０）：２０６９—２０７３．　Ｉｍｐｒｏｖｅｄ　ＲＡＮＳＡＣ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｍａｔｃｈｅｄ　ｐｏｉｎｔｓ　ｐｕｒｉｆｙｉｎｇ　ＪＩＥＪｕｎ　，ＬＩ　Ｚｈｉ－ｊｉｅ　，ＹＡＯ　Ｐｅｎｇ　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｎｔｒｏｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ　ａｎ　Ｕｎｉｖ．ｏｆ　Ａｒｃｈ．＆Ｔｅｃｈ．，Ｘｉ　ａｎ　７１００５５，Ｃｈｉｎａ；　２．Ｃｈａｎｇｑｉｎｇ　Ｏｉｌｆｉｅｌｄ　Ｃｏｍｐａｎｙ，Ｍａｃｈｉｎｅ　Ｍａｎｕｆａｃｔｕｒｅ　Ｐｌａｎｔ，Ｘｉ　ａｎ　７１０２０１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｍｐｒｏｖｅｍｅｎｔ　ｈａｓ　ｂｅｅｎ　ｍａｄｅ　ｆｏｒ　ＲＡＮＳＡＣ　ａｌｏｇｏｒｉｔｈｍ　ｏｆ　ｍａｔｃｈｅｄ　ｐｏｉｎｔｓ　ｐｕｒｉｆｙｉｎｇ　ｉｎ　ｔｈｅ　ｉｍａｇｅ　ｍａｔｃｈｉｎｇ　ｐｒｏｃｅｓｓ　ｂｙ　ｕｓｉｎｇ　ｆｕｎｄａｍｅｎｔａｌ　ｍａｔｒｉｘ　ａｓ　ｏｂｊｅｃｔ　ｏｆ　ｍｏｄｅｌ　ｐａｒａｍｅｔｅｒ　ｉｎ　ｆｉｎｄｉｎｇ　ａ　ｓｏｌｕｔｉｏｎ　ｔｏ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｔｈｅ　ｌａｒｇｅ　ａｍｏｕｎｔ　ｏｆ　ｃａｌｃｕｌａｔｉｏｎ　ａｎｄ　ｔｈｅ　ｌｏｗ　ｅｆｆｉｃｉｅｎｔｙ　ｔｈａｔ　ｅｏｎｅｒｇｅ．Ｂｙ　ｅｘｔｒａｃｔｉｎｇ　ｒｏｕｇｈ　ｍａｔｃｈｅｄ　ｐｏｉｎｔｓ　ｉｎ　ｓｕｂ—ｂｌｏｃｋ　ｇｅｎｅｒａｔｅ　ｆｒｏｍ　Ｂｕｃｋｅｔｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ，ａｌｇｏｒｉｔｈｍ　ｔｅｓｔ　ｔｗｏ　ｉｍａｇｅｓ　ｗｉｔｈ　ｃｏｒｎｅｒ　ｄｅｔｅｃｔｉｏｎ　ａｎｄ　ｒｏｕｇｈ　ｍａｔｃｈｉｎｇ　ｈａｓ　ａｌｓｏ　ｂｅｅｎ　ｉｍｐｒｏｖｅｄ．Ｍｏｒｅｏｖｅｒ，ｉｔ　ｐｒｅｔｅｓｔｓ　ｔｈｅ　ｓａｍｐｌｅ　ｏｆ　ｍａｔｃｈｉｎｇ　ｐｏｉｎｔｓ　ｕｓｉｎｇ　ｄｉｓｐａｒｉｔｙ　ｃｏｎｓｔｒａｉｎｔ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｒｅｄｕｃｅｓ　ｔｈｅ　ａ—　ｍｏｕｎｔ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎ　ｌａｒｇｅｌｙ，ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｉｍａｇｅ　ｍａｔｃｈｉｎｇ　ａｎｄ　ｋｅｅｐｓ　ｈｉｇｈ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　ｒｏｂｕｓｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｒｎｅｒ　ｄｅｔｅｃｔｉｏｎ；ｉｍａｇｅ　ｍａｔｃｈｉｎｇ；ｄｉｓｐａｒｉｔｙ　ｃｏｎｓｔｒａｉｎｔ；ＲＡＮＳＡＣ　Ｂｉｏｇｒａｐｈｙ：ＪＩＥ　Ｊｕｎ，Ｅｎｇｉｎｅｅｒ，Ｍａｓｔｅｒ，Ｘｉ　ａｎ　７１００５５，Ｐ．Ｒ．Ｃｈｉｎａ，Ｔｅｌ：００８６—２９—８２２０２５３７，Ｅ—ｍａｉｌ：ｍｏｕｚｉ一１９９７＠１６３．ｃｏｒｎ　（上接第８８４页）　Ｐｌａｎｎｉｎｇ　ａｎｄ　ｄｅｓｉｇｎ　ｒｅｓｅａｒｃｈ　ｏｆ　ｖｉｌｌａｇｅ　ｅｍｐｌａｃｅｍｅｎｔ　ｂａｓｅｄ　ｏｎ‘‘ｏｒｉｇｉｎａｌ　ｓｔａｔｅｓ’’ｒｅｓｉｄｅｎｔｉａｌ　ｃｏｎｃｅｐｔｉｏｎ　ＺＨＡＯ　Ｈｏｎｇ—ｂｉｎ　’　（１．Ｓｃｈｏｏｌ　ｏｆ　Ａｒｃｈ．，Ｘｉ　ａｎ　Ｕｎｉｖ．ｏｆ　Ａｒｃｈ．＆Ｔｅｃｈ．，Ｘｉ　ａｎ　７１００５５，Ｃｈｉｎａ；　２．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｔｅｃｈｏｌｏｇｙ　ｉｎ　Ｗｅｓｔ　Ｃｈｉｎａ（ＸＡＵＡＴ），Ｘｉ　ａｎ　７１００５５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐａｐｅｒ　ｓｕｍｍａｒｉｚｅｄ　ａ　ｓｅｒｉｅｓ　ｏｆ　ｐｒｏｂｌｅｍ　ｗｈｉｃｈ　ａｒｉｓｅ　ｉｎ　ｌａｎｄ—ｌｏｓｔ　ｆａｒｍｅｒ　ｖｉｌｌａｇｅ　ｅｍｐｌａｃｅｍｅｎｔ　ｒｅｓｅｔｔｌｅｍｅｎｔ　ａｒｅａ．　Ｔｈｅ　ｒｅｓｅａｒｃｈ　ｓｔａｒｔｓ　ｗｉｔｈ　ｔｈｅ　ｖｉｅｗ　ｏｆ　ｆａｒｍｅｒ　ｗｈｏｓｅ　１ａｎｄ　ｗａｓ　ｃｏｍｍａｎｄｅｅｒｅｄ　ｆｏｒ　ｅｓｔａｂｌｉｓｈｉｎｇ　ｆｌ　ｖｉｌｌａｇｅ　ｅｍｐｌａｃｅｍｅｎｔ　ｐｌａｎｎｉｎｇ　ｉｄｅａ　ｏｆ“Ｏｒｉｇｉｎａｌ　Ｓｔａｔｅｓ”，ａｎｄ　ｅｍｐｈａｓｉｚｅ　ｔｈｅ　ｐｒｏｔｅｃｔｉｏｎ　ｏｆ　ｍａｉｎｔａｎａｎｃｅ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｌｉｆｅｓｔｙｌｅ　ｏｆ　ｔｈｅ　ｐｅｏｐｌｅ．Ｉｎｖｅｓｔｉｇａｔｉｏｎ　ｉｓ　ｍａｄｅ　ｆｏｒ　ｔｈｅ　ｂａｓｉｃ　ｓｅｔｔｌｅｍｅｎｔ　ｓｐａｔｉａｌ　ｆｏｒｍ　ｏｆ　ａ　ｓｕｉｔａｂｌｅ　ｅｍｐｌａｃｅｍｅｎｔ　ｃｏｍｍｕｎｉｔｙ．Ｔｈｅ　ｐａｐｅｒ　ｗｉｌｌ　ｅｘｐｌｏｒｅ　ａ　ｎｅｗ　ｐｌａｎｎｉｎｇ　ｃｏｎｃｅｐｔ　ａｎｄ　ｎｅｗ　ｄｅｓｉｇｎ　ｓｔｒａｔｅｇｙ　ｏｆ　ｅｍｐｌａｃｅｍｅｎｔ　ｃｏｍｍｕｎｉｔｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｎｅｗｌｙ　ｕｒｂａｎｉｚａｔｉｏｎ；ｌａｎｄ－ｌｏｓｔ　ｆａｒｍｅｒ；ｅｍｐｌａｃｅｍｅｎｔ　ｐｌａｎｎｉｎｇ　Ｂｉｏｇｒａｐｈｙ：ＺＨＡＯ　Ｈｏｎｇ—ｂｉｎ，Ｌｅｃｔｕｒｅｒ，Ｃａｎｄｉｄａｔｅ　ｆｏｒ　Ｐｈ．Ｄ．，Ｘｉ　ａｎ　７１００５５，Ｐ．Ｒ．Ｃｈｉｎａ，Ｔｅｌ：００８６—１３９９１１３９１１３，Ｅ－ｍａｉｌ：５５０９９８６５８　＠ｑ　ｑ．ｅｏｍ