分块技术实现图像快速_高精度旋转
- 格式：pdf
- 大小：1.31 MB
- 文档页数：5
第38卷第4期 光电工程V ol.38, No.4 2011年4月Opto-Electronic Engineering April, 2011 文章编号：1003-501X(2011)04-0103-05分块技术实现图像快速-高精度旋转李兵1，王云宽1，黄为1，吴少泓1，刘海龙2( 1. 中国科学院自动化研究所，北京 100190;2. 森佩富莱公司，上海 201417 )摘要：本文提出了一种分块技术，在保障图像旋转精度的前提下，实现图像的快速旋转。
该算法只需对图像的一小块区域进行旋转，然后通过简单的坐标变换即可获得整幅旋转后的图像。
同时为了便于硬件实现，提出了一种用于事先存储仿射变换信息的Dart模型，将该模型与图像分块技术相结合可以消除图像旋转算法中的浮点运算，使得算法适用于一些无法处理浮点运算的处理器。
经测试，本文提出的算法具有高精度、高速度等特点。
关键词：快速图像旋转；高精度；嵌入式系统；分块技术；Dart模型中图分类号：TP391.41 文献标志码：A doi：10.3969/j.issn.1003-501X.2011.04.018Realization of Fast-high-quality Image Rotation Using Block Division LI Bing1，WANG Yun-kuan1，HUANG Wei1，WU Shao-hong1，LIU Hai-long2( 1. Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;2. Semperflex Shanghai Ltd. Shanghai 201417, China )Abstract: A novel algorithm called block division for fast image rotation with accuracy guarantee was proposed. In our algorithm, we only rotate a small region of rotated image and get entire rotated image by simple coordinate transformations. For convenient hardware implementation, we propose Dart model to store the information of affine transformations in advance, and combine this model with the technology of block division to eliminate float calculation.Tests shows that the proposed algorithm can realize high-accuracy and high-speed image rotation.Key words: fast image rotation; high-quality; embedded system; block division; Dart model0 引 言在数字图像处理和模式识别领域，图像旋转是一项基础但极其重要的部分。
传统的图像旋转算法一般可分为两类：One-pass[1]和Multi-pass，其中Multi-pass算法主要包括Two-pass[2-4]和Three-pass[5]，与Multi-pass 相比，One-pass方法可以获得更高的旋转精度，但One-pass算法的计算复杂度较高，图像旋转速度较慢。
Multi-pass算法通过对仿射变换矩阵进行分解，获得了更高旋转速度，但同时降低了图像的旋转精度。
为了便于图像旋转算法的硬件实现，需要考虑到算法的浮点运算量和内存的使用量两个方面，文献[6]根据旋转角度直接对像素点操作，消除了算法中的浮点运算。
文献[7]提出了基于图像块的图像旋转算法，降低了算法的内存使用量。
本文提出了一种算法可同时实现图像的高精度和高速度旋转。
首先，提出了一种分块技术实现图像的快速旋转，已知旋转后图像的大小(如640×480)，算法一般仅需要对该图像的一小块区域(如640×1)进行旋转仿射变换，然后通过简单的坐标变换获得旋转后图像像素点与原图像像素点之间的映射关系。
其次，提出了一种Dart模型消除分块算法中的浮点运算，满足一些无法处理浮点运算的处理器(如多数的嵌入式系统)。
Dart模型将所有图像像素点的仿射变换信息以较小的内存消耗存入指定内存，在对图像进行旋转时实收稿日期：2010-12-02；收到修改稿日期：2011-01-10作者简介：李兵(1982-)，男(汉族)，黑龙江佳木斯人。
博士研究生，主要研究工作是机器视觉与智能控制。
E-mail: libing1982828@。
光电工程 2011年4月 104 图1 小块区域与旋转后图像之间的像素点映射Fig.1 Pixel map between block and rotated image时提取。
1 分块技术利用基本仿射变换矩阵进行坐标旋转变换具有精度高的优点，但其计算复杂度高。
为了降低旋转算法的计算复杂度，本文提出分块技术实现图像的快速旋转，分块技术包括图像分块和映射关系两个部分，图像分块根据旋转角度获得小块区域中心点及该区域内的点的仿射变换结果，映射关系获得旋转后图像像素点与原图像像素点的对应关系。
1.1 图像分块图像分块的目的是将一幅较大的图像分成若干具有相同尺寸的小块区域，将这些小块区域的长度和宽度设定为奇数，这样方便获得这些小块区域的中心点。
具体图像分块步骤如下：1) 根据旋转角度获得原图像旋转后的大小，即完全包围旋转后图像的区域大小。
2) 将旋转后的图像分成若干具有相同尺寸的小块区域。
3) 计算每个小块区域中心点旋转一定角度(相对与旋转后图像的中心点)后的坐标值，分别提取这些坐标值的整数部分和小数部分，将小数部分扩大一定的倍数表示成整数(本文倍数取1 000)，小数部分的存在是为了提高图像的旋转精度(具体见实验部分)。
4) 计算某小块区域所有像素点旋转一定角度(相对于该区域的中心点)后的坐标值，这些坐标值采用步骤3)相同的表示方法，此步骤中的区域内像素点坐标值仿射变换只需进行一次。
1.2 映射关系图像分块获得了小块区域中心点及区域内的点的坐标值，通过建立二者与以w 为原点坐标系之间的映射关系，可获得旋转后图像像素点与原图像像素点的对应关系。
如图1所示，定义以w 为原点的坐标系为C 0，以o 为原点的坐标系为C 1，以o 1为原点的坐标系为C 2，这三个坐标系均为水平轴正方向指向右方，垂直轴正方向指向上方。
A 1为旋转后图像上的某区域，o 为A 1的中心，p 为A 1上的某点。
A 2为以点o 为中心点的A 1平移至o 1所获得的区域。
A 3为A 1以w 为圆心旋转r 2度后所获得的区域。
由直线p 1o 1与直线po 相平行和三角形opw 与o 1p 2w 全等，得r 5=r 2。
r 2角度值及p 1在C 2坐标值已知，可获得p 2在C 2的坐标值。
o 1在C 0的坐标值可通过旋转直线wo 获得。
这样就可以通过式(1)和式(2)获得点p 2在C 0中的坐标值。
012202C o C p Cp x x x += (1)012202C o C p Cp y y y += (2) 其中：02Cp x ，02C p y 为点p 2在C 0上的水平及垂直方向上的坐标值；22C p x ，22C p y 为点p 2在C 2上的坐标值；01C o x ，01C o y 为区域中心点o 1在C 0上的坐标值。
可以看出已知旋转角度、区域中心点坐标值(相对与图像的中心点) 和区域上点的坐标值(相对与该区域的中心)即可获得图像上像素点旋转后的位置坐标。
由于区域内的像素点只需进行一次仿射变换，因此对于一幅图像(如1 000×1 000)的浮点运算量由4 000 000次(Basic matrix R 算法)降低到8 000次(分块算法)。
2 Dart 模型对于一些具有浮点运算能力的处理器(如PC 机)，分块算法单独即可实现图像的快速旋转。
但分块算法中仍然存在一定量的浮点运算，对于一些没有浮点运算能力的处理器(如定点DSP 、ARM 等)，需进行特殊的处理(如浮点数转定点数)，为了便于硬件实现，提出了Dart 模型用于消除分块算法中的浮点运算。
Dart 模型分为Dart 信息模型(DIM)和Dart 计算模型(DCM)。
第38卷第4期 李 兵 等：分块技术实现图像快速-高精度旋转 105图2 Dart 信息模型Fig.2 Dart information model图3 Dart 计算模型 Fig.3 Dart calculation model 2.1 创建Dart 信息模型DIM 用于存储图像(小块区域)像素点的位置信息，DIM 只需要创建一次并存入指定内存，即可以通过简单的改变DIM 内存的首地址快速获得该图像旋转任意角度后的像素点位置信息。
DIM 创建步骤如下：1) 创建原点为o 的二维坐标系，水平轴(x 轴)正方向指向右方，垂直轴(y 轴)正方向指向上方，坐标点的间距为1d (d 为图像两像素点之间的水平距离)。
2) 在此坐标系上创建一个矩形M ，矩形的四个角点分别为(-m , m )，(-m , -m )，(m , m )，(m , -m )。
3) 在矩形M 内创建内切圆C 。
4) 创建圆C 的同心圆，同心圆的半径由1d 到md 。
5) 以圆点o 为参考点，对直线om 做逆时针旋转，旋转角度范围为0~360°，旋转角度步长为α，每旋转一次可获得当前角度下om 与所有同心圆的一组交点的集合z n ，定义这些点为DIM 的信息点。
DIM 的几何结构如图2所示。
在DIM 内存中，集合n z 对应相应信息点在该坐标系中的位置信息，通过式(3)和式(4)可获得这些位置信息。
αtan ⋅=r i x (3)αcot ⋅=r i y (4)其中：x i 和y i 分别为信息点对应x 方向和y 方向的坐标值，r 为圆点o 与信息点之间的距离，α为信息点所在半径与x 正方向的夹角。
获得这些信息点的具体位置信息后，以序列) (1210−⋅⋅⋅n z z z z 的顺序存入内存，其中1)0,1,2(−⋅⋅⋅=n i i z 具有相同数量的信息点，这些信息点的存储顺序为) (1210−⋅⋅⋅im i i i z z z z 。
