, 王义11. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110819;
2. 常熟理工学院 计算机科学与工程学院, 江苏 常熟 215500
收稿日期：2015-09-14
基金项目：国家自然科学基金资助项目 (61305025)；江苏省高校自然科学基金资助项目 (15KJB520001)；中央高校基本科研业务费专项资金资助项目 (N120404008)。
作者简介：刘永俊 (1981-)，男，山东青岛人，常熟理工学院副教授，东北大学博士研究生;
王义 (1961-), 男, 内蒙古赤峰人, 东北大学教授，博士生导师。
摘要：提出了一种基于近邻主特征匹配的亚像素级位移测量方法.改进后的近邻主特征提取过程通过修正散度矩阵的构造, 最大化相邻位移图像块投影距离, 提高了算法的精度和稳定性.通过将训练过程离线化, 提出了基于近邻主特征匹配的微纳米位移测量算法, 并通过仿真实验验证了图像块在不同大小和位置情况下算法的精度.在高精度纳米平台、高倍显微镜及标准栅格构成的系统中进行了多角度的实验, 验证了算法的有效性.算法的测量精度比传统的图像块匹配方法提高了近10倍, 特别是算法对于图像块位置和大小的选择鲁棒性更高.
关键词：微纳米图像主成分分析近邻主特征图像块匹配亚像素
A Displacement Measurement Method of Micro/Nano Scale Based on Neighbor Principal Feature Matching
LIU Yong-jun1,2, WEI Yang-jie1
, WANG Yi11. School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Computer Science and Engineering, Changshu Institute of Technology, Changshu 215500, China
Corresponding author: WEI Yang-jie, E-mail: weiyangjie@ise.neu.edu.cn
Abstract: A new sub-pixel displacement measurement method is proposed based on the neighbor principal feature matching. The improved main features extraction process enhances the accuracy and stability of the algorithm by reconstructing divergence correction matrix and maximizing the distance of adjacent image blocks. The overall micro/nano scale measurement method is designed based on the neighbor principal feature matching by off-line training process, and the simulation verifies the accuracy of the method which is used for the image blocks with different sizes and positions. The high-precision nano platform, the high power microscope and the standard grid are used together to validate the measurement. The accuracy of the algorithm is increased by nearly 10 times compared with the conventional blocks matching method. Further, the algorithm has higher robustness in selecting the position and size of the image blocks.
Key Words: micro/nano imageprincipal component analysisneighbor principal featureimage block matchingsub-pixel
微纳米制造技术的迅速发展对测量技术提出了新的挑战, 微纳米测量技术已经成为纳米科学技术的基础之一[1-4].准确、稳定的纳米级尺寸和位移的测量对于设计微纳米驱动与定位技术至关重要，如压电陶瓷作为当今一种较为理想的微位移驱动材料, 如何精确地测量其迟滞、蠕变等现象一直是微纳米领域研究的重点[5-6].
计算机视觉方法使用的设备相对便宜, 测量过程简单、结果直观.但是, 为了使视觉方法能够高精度地测量样品的位移特性, 除了高倍的显微镜系统, 还需要准确的微纳米尺度位移测量算法.最近, Walia等[7]以及本项目组[5-6]针对这些方法的缺点, 均提出了基于亚像素图像块匹配的位移测量的改进方法, 但是该方法仍然是基于原始的图像像素或经过插值后的亚像素图像, 直接对图像块像素值进行比对测量; 测量的效果对搜索区域、模板大小、亚像素拟合程度都有较大的依赖, 降低了算法的稳定性.
近年来, 主成分分析 (principal component analysis, PCA) 方法[8-10]作为模式识别领域最为经典的特征抽取方法之一, 在人脸识别等宏观领域得到了广泛的研究和应用.本文首先在分析了微纳米图像特点的基础上, 对主成分分析中的散度矩阵及准则函数加以改进, 使抽取的“近邻主特征”更加有利于微纳米位移测量中的图像匹配, 然后再将栅格图像精度增加到亚像素级别, 验证了算法的有效性.通过进一步将训练过程离线化, 设计了基于特征匹配的微纳米测量的整体框架, 使测量的实时性得到了保证.
1 图像块匹配算法及问题分析图像块匹配算法 (block matching algorithm, BMA) 简单易行, 是一种经典的测量图像2D运动的方法[5-6].
如图 1所示, 设原图像大小和目标图像大小均为m×n, 图像块模板T大小为a×b, (m≥a, n≥b).将图像块模板T在目标图像中逐行、逐列地移动, 移动范围i∈(1, m－a+1), j∈(1, n－b+1), 其中, i为图像横坐标, j为图像纵坐标.X(i, j) 和Y(i, j) 分别表示模板T在原始图像和目标图像中覆盖的图像块像素.图像块匹配方法的本质就是计算两幅图像样本各像素X(i, j) 和Y(i, j) 间的匹配准则函数, 当匹配函数取极值时获得的坐标与原图像块坐标的差值即为所求位移.
图 1(Fig. 1)
 | 图 1 图像块匹配示意图Fig.1 Schematic of block matching |
由此可见, 图像块匹配过程中选择有效的匹配准则函数和方法是关键.目前主要有最小差异函数和最大相似度函数两大类匹配准则函数[11-13].
图 2为图像块匹配算法中, 沿坐标不断移动模板所得的10幅图像块.
图 2(Fig. 2)
 | 图 2 位移中的图像块Fig.2 Displacing image blocks |
以归一化互相关 (normalized cross correlation, NCC) 为代表的传统图像块匹配方法均是以原始图像的像素值为特征直接进行匹配函数的计算.在传统的模板匹配过程中, 如果位移的数量级为微纳米级, 则各位移图像块本身具有很大的相似性, 加上图像本身又有噪声的影响, 所以很容易使匹配误差增大.文献[5]中为了尽量多地保留位移图像的差异化像素特征, 提高传统模板匹配算法的稳定性, 详细讨论了图像块模板大小的选择, 但算法的通用性受到一定的限制.
2 近邻主特征提取2.1 主特征提取PCA是图像特征抽取中最为经典的方法之一, 其核心是对数据分布的方差进行估计, 以求出各最优投影轴, 即所谓的主方向, 旨在寻找最小均方意义下最能代表原始数据的投影特征, 将其称之为“主特征”; 其抽取的特征具有正交性和统计不相关性的优点[8].基本思想和过程简述如下.
在原始图像中, 将上述图像块模板T(大小为a×b) 由坐标α, β开始沿x, y轴以像素为单位移动mx, my步 (移动大小根据搜索区域大小确定).每次移动后T覆盖的图像块像素矩阵作为训练样本, 设共得到训练样本M=mx×my幅图像矩阵Ai(i=1, …, M), Ai大小为 (a×b).
首先将每幅模板图像的图像矩阵转化为N=a×b维的图像向量Xi(i=1, …, M), 其均值记为X.PCA的基本出发点是希望能找到最优投影方向w, 使样本Xi在其上投影后与样本均值的欧氏距离最大 (即均方误差最小).
 | (1) |
 | (2) |
 | (3) |
 | (4) |
 | (5) |
 | (6) |
 | (7) |
为验证以上结论的正确性, 本文取d=10, 即分别采用式 (3) 和式 (7) 取前10个最大特征值对应的投影方向, 对相邻的10幅位移图像按照式 (4) 进行特征提取，然后将提取的特征进行逆运算:
 | (8) |
图 3(Fig. 3)
 | 图 3 PCA和NPCA的样本特征分布Fig.3 Distribution of samples′ features from PCA and NPCA (a)—PCA; (b)—NPCA. |
分布情况显示, 采用NPCA后, 样本在空间中的分布更加离散化, 对匹配任务更加有利.
3 基于近邻主特征匹配的微纳米位移测量方法将第2节中所述特征抽取训练过程放到实时测量之前, 称之为“离线”处理, 建立一种统一的基于特征提取的亚像素级微纳米位移测量算法.算法如下:
1)?读取位移前原图像, 采用亚像素测量原理, 选择合适的插值方法, 生成新的亚像素图像.(离线)
2)?按本文方法确定坐标原点.(离线)
3)?将T在原亚像素图像中以亚像素为步长沿x, y坐标移动, 生成系列训练样本.(离线)
4)?计算PCA或NPCA准则函数, 求最优投影方向w1, …, wd或φ1, φ2, …, φd.(离线)
5)?将训练样本往最优投影方向上投影, 执行式 (7), 进行特征提取.存取各训练样本坐标位置 (αi, βi) 及对应特征向量
6)?实时采集目标图像, 按照同样的插值方法生成亚像素图像.(实时)
7)?将T在 (α0, β0) 同一坐标位置取得待测量图像块B, 按同样方式转换为N维待测样本向量Y.(实时)
8)?按步骤5) 中同样的方式, 将Y往最优投影方向w1, …, wd或φ1, φ2, …, φd上投影, 得到待测图像块的特征向量?.(实时)
9)?将向量?与
由以上算法可以发现, 真正的实时测量过程只涉及到对目标图像的亚像素化处理、投影和匹配三个步骤.在核心步骤9) 中, 以2.2节说明为例, 向量?与
4 实验结果及分析在传统的图像块匹配算法中, 模板块的大小是影响匹配精度的一个重要因素:太小会降低位置测量的准确性, 太大由于模板内部变形也会影响精度, 而且计算复杂度会急剧增加[5-6].
为验证本文算法的有效性, 在相同实验环境下, 采用如图 2所示的标准5 μm栅格, 采用不同大小的模板对传统匹配方法 (NCC, ZSAD) 和基于主特征的匹配方法 (PCA, NPCA) 进行比较.为进一步考虑x坐标和y坐标的耦合性, 本文计算位移偏差时采用两坐标位移误差之和的平均作为度量标准 (以像素为基本单位).实验的实际位移为每次移动1个像素.
4.1 实验一:亚像素图像位移误差测量在微纳米位移测量中为了提高测量精度, 使用亚像素拟合图像是一种通用的有效方法.本文采用常用的二次线性插值方法得到拟合的亚像素图像并进行实验, 实验结果如表 1所示.
表 1(Table 1)
 表 1 亚像素图像位移误差Table 1 Displacement error based on sub-pixel images
| 表 1 亚像素图像位移误差 Table 1 Displacement error based on sub-pixel images | |||||||||||||||||||||||||||||||||||||||||||||||||
从表 1的实验数据可以看出, 在亚像素图像中, 基于主特征和近邻主特征的图像块匹配方法同样大幅提高了匹配的精度.实验结果表明, 采用特征分析方法起到了去除冗余等干扰噪声的作用, 所以能获得更加稳定、高精度的测量结果.该方法有效地避免了传统亚像素图像块匹配方法中对拟合方法要求苛刻, 以及计算复杂度高的问题.
特别需要指出的是, 传统方法的匹配精度受图像块大小的影响较大, 文献[5]作了详细的讨论, 当图像块远小于或者远大于白色特征块 (见图 2) 时, 识别精度都会大幅下降.在本实验中也验证了这一点, 当图像块小于30×30时位移误差较大.而采用近邻主特征方法进行匹配时, 如第2节所述, 由于特征提取过程中, 其基本思想是使样本的差异化信息最大化, 所以对图像块的大小和位置并不敏感, 图像块最小可以取5×5, 此时图像块均小于白色特征块, 用肉眼已经很难看出图像块的差别了.这是该方法的另一大优点.
4.2 实验二:实际位移误差测量为了进一步在实际应用中验证算法的有效性, 在Physik Instrumente (PI) 公司的纳米平台上进行了如图 2所示的标准栅格位移测量实验, 该平台能够准确给出平台的真实位移, 精度为纳米.实验使用的是HiRox公司的KH-7700显微镜, PI平台的位移为每步50 nm, 栅格图像的像素大小为57.471 3 nm, 因此实际计算的每一步位移的准确值是0.87像素.
实验中同样采用二次线性插值拟合生成亚像素图像, 然后分别采用PCA, NPCA两种方法进行位移测量, 图像块大小取10×10.实验结果见图 4.
图 4(Fig. 4)
 | 图 4 测量位移与实际位移比较Fig.4 Comparison of the actual and measured displacement |
实验表明, 采用基于近邻主特征的图像块匹配方法, 实际匹配误差可以控制在0.05像素以内 (传统图像块匹配方法误差在0.1像素左右[5]), 即在该实验中误差可以控制在5 nm以内, 精度比传统图像块匹配方法有较大提高, 能够满足实际需求.
为进一步测试算法实时性, 采用4种方法测量一步位移的平均时间 (Intel (R) Core (TM) i7 CPU, 8.0 GB内存, 64位操作系统)，见表 2.
表 2(Table 2)
表 2 亚像素图像每步位移的平均时间Table 2 Average time of each step displacement of sub-pixel image
| 表 2 亚像素图像每步位移的平均时间 Table 2 Average time of each step displacement of sub-pixel image | |||||||||||||||||||
由表 2中的实验数据可以看出, 采用第3节中图 4所示的微纳米位移测量方法, 虽然在特征抽取过程中增加了计算复杂度, 但是采用离线特征抽取后, 在实时测量过程中由于匹配的特征数大幅下降 (实验中由亚像素图像的103维降为101), 所以实时匹配的速度反而得到大幅提高.
5 结论1)?微纳米位移测量中传统图像块匹配方法大多直接利用图像原始像素数据进行匹配计算.传统方法一方面, 计算量大; 另一方面, 由于图像噪声等的影响使得匹配精度不高.
2)?从微纳米位移的特点入手, 提出了基于主特征和近邻主特征的图像块匹配位移测量方法.该方法通过对微纳米图像进行离线特征抽取, 使其抽取的主特征更加突出近邻样本的差异化信息, 从而达到对后续在线匹配更加有利的目的.
3)?使用仿真和实验验证了基于近邻主特征的图像块匹配方法的有效性.该方法不仅较大地提高了图像块匹配方法的精度, 而且对图像块大小的选择具有更强的鲁棒性, 是一种更加简单、有效和通用的微纳米位移测量方法.
参考文献
| [1] | Huang C, Wu L Y. State-led technological development:a case of China's nanotechnology development[J].World Development, 2012, 40(5): 970–982.DOI:10.1016/j.worlddev.2011.11.013 |
| [2] | Bykov I V. Automatized methods for optimization of scanning probe microscope operation[J].Strategic Technologies, 2008, 34(1): 179–180. |
| [3] | Yamamoto H, Sano T. Study of micromanipulation using stereoscopic microscope[J].IEEE Transactions on Instrument and Measurement, 2002, 51(2): 182–187.DOI:10.1109/19.997809 |
| [4] | 刘小康, 彭凯, 王先全, 等. 纳米时栅位移传感器的理论模型与误差分析[J].仪器仪表学报, 2014, 35(5): 1136–1142. ( Liu Xiao-kang, Peng Kai, Wang Xian-quan, et al. Theoretical model and error analysis of nanometer time grating displacement sensor[J].Chinese Journal of Scientific Instrument, 2014, 35(5): 1136–1142.) |
| [5] | 魏阳杰, 吴成东, 董再励. 基于亚像素图像块匹配方法的压电陶瓷驱动特性测量[J].机械工程学报, 2010, 46(17): 151–158. ( Wei Yang-jie, Wu Cheng-dong, Dong Zai-li. Sub-pixel image block matching based measurement on driving characteristic of a piezoelectric actuator[J].Chinese Journal of Mechanical Engineering, 2010, 46(17): 151–158.DOI:10.3901/JME.2010.17.151) |
| [6] | 魏阳杰, 吴成东. 微纳米压电陶瓷驱动器的迟滞特性建模[J].东北大学学报 (自然科学版), 2014, 35(2): 166–169. ( Wei Yang-jie, Wu Cheng-dong. Modeling of hysteresis behavior for micro/nano piezoelectric actuator[J].Journal of Northeastern University (Natural Science), 2014, 35(2): 166–169.) |
| [7] | Walia E, Saigal P, Pal A.Enhanced linear block algorithm with improved similarity measure[C]// The 2014 Canadian Conference on Electrical and Computer Engineering.Toronto, 2014:653-659. |
| [8] | 刘永俊, 陈才扣, 王正群. 基于主分量分析的最优鉴别特征抽取[J].计算机应用与软件, 2008, 25(4): 86–88. ( Liu Yong-jun, Chen Cai-kou, Wang Zheng-qun. The extraction of optimal discriminating features based on principal component analysis[J].Journal of Computer Applications and Software, 2008, 25(4): 86–88.) |
| [9] | Grudin M A. On internal representations in face recognition systems[J].Pattern Recognition, 2000, 33(7): 1161–1177.DOI:10.1016/S0031-3203(99)00104-1 |
| [10] | Yang J, Yang J Y. From image vector to matrix:a straightforward image projection IMPCA vs.PCA[J].Pattern Recognition, 2002, 35(9): 1997–1999.DOI:10.1016/S0031-3203(02)00040-7 |
| [11] | Qi T, Michael N H. Algorithms for sub-pixel registration[J].Computer Vision, Graphics, and Image Processing, 1986, 35: 220–233.DOI:10.1016/0734-189X(86)90028-9 |
| [12] | Kim J H, Meng C H. Visually servoes 3-D alignment of multiple objects with sub-nanometer precision[J].IEEE Transactions on Nanotechnology, 2007, 7(3): 321–330. |
| [13] | Robinson D, Milanfar P. Fundamental performance limits in image registration[J].IEEE Transactions on Image Process, 2004, 13(9): 1185–1199.DOI:10.1109/TIP.2004.832923 |
