利用存储空间地址变换进行图像旋转的方法及装置

摘要

本发明涉及图像处理和计算机图形学领域，为提出一种利用存储空间地址变换实现图像快速旋转的方法，利用动态存储器突发传输的特点，采用可变步长累加的方式计算存储地址，在存储图像的同时完成图像旋转。本发明采用的技术方案是，利用存储空间地址变换进行图像旋转的方法及装置，步骤如下：(1)以一幅图像左上角为旋转中心，计算出原始图像首行首列像素的存储地址；(2)记一次突发长度内传输的像素点的个数为BLP；(3)计算得到每行首列像素的存储地址；(4)其它像素的存储地址在该行首列像素存储地址的基础上得到；(5)产生空洞的地方，采用向左移动像素填充空洞的方式消除空洞。本发明主要应用于图像处理。

说明书

技术领域

本发明涉及图像处理和计算机图形学领域，尤其涉及实时图像旋转、数据存储及实现方式。具体讲,涉及利用存储空间地址变换进行图像旋转的方法。

背景技术

图像旋转是数字图像处理中一个重要组成部分，在机器视觉、医学、航空、遥感等领域具有广泛的应用。传统的图像旋转方法主要分为一步旋转法和多步旋转法。一步旋转法根据公式(1)直接计算每个像素点的映射坐标。

x_i,j＝icosθ-jsinθ

y_i,j＝isinθ+jcosθ>

其中，θ为旋转角度，(i,j)为原始图像中的像素坐标，(x_i,j,y_i,j)为(i,j)在旋转图像中的映射坐标。这种方法计算公式简单、精度高，但是计算量大、效率低，难以满足实时处理需求；同时由于计算得到的映射坐标不一定是整数，可能会产生空洞，因此需要合适的插值技术，如最近邻插值、双线性插值和双三次插值等方法消除空洞。

多步旋转法有两步旋转法和三步旋转法，其中，三步旋转法将二维旋转分解为三次一维平移运算，如公式(2)所示。

三步旋转法减少了浮点乘法运算，但是仍然需要插值方法计算像素值，需要缓存映射坐标和图像数据，即使能够满足实时处理需求，电路也比较复杂。

图像数据常被缓存在存储器中，如果能够实时计算出映射坐标，在存储时将像素值按照旋转后的映射坐标存储，即可在图像存储的同时完成图像旋转。由于数据量庞大，图像数据常被缓存在动态存储器中，动态存储器一般采用突发传输的模式，即指定一个起始地址后，内存就会依次地自动对后面相应数量的存储单元进行读/写操作而不再需要控制器连续地提供列地址。连续传输所涉及的存储单元的数量就是突发长度(Burst Length,BL)，常见的设置为4和8。这种突发传输的方式避免了频繁地发送行列地址及读写命令，从而提高了数据传输的效率，但是这也意味着连续的固定个数的像素需要被存储在一行内的相邻位置。然而传统的图像旋转方法或插值方法计算量大，难以实时计算出存储地址；并且即使实时计算出存储地址，也不一定满足固定数量的像素恰好存储在同一行，因此，一般的映射坐标计算方法难以充分利用动态存储器突发传输的优势，基于地址空间变换实现图像旋转。

发明内容

为克服现有技术的不足，针对目前大部分图像旋转方法难以满足实时处理需求的问题，本发明的目的是提出一种利用存储空间地址变换实现图像快速旋转的方法，利用动态存储器 突发传输的特点，采用可变步长累加的方式计算存储地址，在存储图像的同时完成图像旋转。本发明采用的技术方案是，利用存储空间地址变换进行图像旋转的方法，步骤如下：

(1)以一幅图像左上角为旋转中心，首先由公式(1)计算出原始图像首行首列像素的存储地址(x_1,1,y_1,1)，即(INI0_ROW，INI0_COL)：

x_i,j＝icosθ-jsinθ

y_i,j＝isinθ+jcosθ>

其中，θ为旋转角度，(i,j)为原始图像中的像素坐标，(xi,j,yi,j)为(i,j)在旋转图像中的映射坐标；并根据公式(3)求得N值：

N为地址计算的理论步长值；

(2)记一次突发长度内传输的像素点的个数为BLP，根据公式(6)计算出各个可变的步长值，即step₁，step₂，step₃，……，step_BLP

其中，Na_i为N的累加，Sa_i为步长的累加；

(3)每行首列像素的存储地址，根据其上一行首列像素的存储地址计算得到，对于逆时针，每隔2N行，首列像素的存储位置向右移动一个存储单元，即列地址加1；对于顺时针，每隔2N行，首列像素的存储位置向左移动一个存储单元，即列地址减1；

(4)其它像素的存储地址在该行首列像素存储地址的基础上得到，以第一行像素为例，第1至step₁个像素存储在INI0_ROW行，若逆时针旋转，则第(step₁+1)至(step₁+step₂)个像素存储在(INI0_ROW-1)行，第(step₁+step₂+1)至(step₁+step₂+step₃+1)个像素存储在(INI0_ROW-2)行，以此类推，每隔一个步长，存储位置向上移动一行；同样，若顺时针旋转，则行存储地址依次为(INI0_ROW+1)，(INI0_ROW+2)，……其他行的像素的存储地址与第一行像素存储地址的计算方法一样；

(5)产生空洞的地方，采用向左移动像素填充空洞的方式消除空洞。

利用存储空间地址变换进行图像旋转的装置，由10个部分构成，分别是：旋转角度输入501，数据输入接口502，初始参数计算模块503，写地址产生器504，输入数据缓存接口505，存储器506，存储器控制器507，读地址产生器508，输出数据缓存接口509，显示设备510；其中，旋转角度输入501，提供需要的旋转角度；数据输入接口502提供原始的图像数据信息，即待旋转的原始图像；初始参数计算模块503根据输入的旋转角度计算出包括首行首列存储地址(INI0_ROW，INI0_COL)，理论步长N,及多个可变步长step_i的初始地址参数；写地址产生器504负责产生访问存储的写地址；输入数据缓存接口505用于缓存输入的图像数据；存储器506即为动态存储器，存储图像数据，与此同时，基于地址空间映射实现图像旋转；>

初始参数计算模块503根据输入的旋转角度计算出包括首行首列存储地址(INI0_ROW，INI0_COL)，理论步长N,及多个可变步长step_i的初始地址参数，具体是：

以一幅图像左上角为旋转中心，首先由公式(1)计算出原始图像首行首列像素的存储地址(INI0_ROW，INI0_COL)：

x_i,j＝icosθ-jsinθ

y_i,j＝isinθ+jcosθ>

其中，θ为旋转角度，(i,j)为原始图像中的像素坐标，(xi,j,yi,j)为(i,j)在旋转图像中的映射坐标；并根据公式(3)求得N值：

N为地址计算的理论步长值。

然后，根据公式(6)计算出各个可变的步长值step_i，即step₁，step₂，step₃，……，step_BLP。

其中，N_ai为N的累加，S_ai为步长的累加。

本发明的特点及有益效果是：

1.本发明利用动态存储器(SDRAM或DDR)突发传输的优势，通过控制存储地址实现快速图像旋转，并给出实现旋转方法的装置，处理速度快，且电路简单，能够达到实时处理需求。

2.充分结合动态存储器(SDRAM或DDR)突发传输的特点，提出可变步长累加的方法计算存储地址，在降低计算复杂度的同时，大大提升了图像质量。

附图说明：

图1固定步长累加的方式实现图像旋转。

图2采用可变步长累加的方法和固定步长累加的方法拟合直线(N＝11,BLP＝8)。

图3基于可变步长累加的方法旋转产生空洞。

图4在动态存储器中基于地址空间映射实现图像旋转(BL＝4,BLP＝8)。

图5旋转方法装置示意图。

图6 tanθ＝1/11，BLP＝8，基于可变步长累加的方法实现图像旋转：(a)原始图像；(b)旋转后的图像。

具体实施方式

一幅图像可以看作多行像素，已知旋转角度和首行首列像素的映射坐标，其它像素的映射坐标可按照类似直线光栅化的方式通过累加的方式计算得到，如图1所示。设地址计算的理论步长值为N,N与旋转角度有关，由如下公式得到：

然而由于动态存储器突发传输的特点，对存储器的一次访问涉及BL个存储单元，这意味着被存储在同一行内的相邻位置像素的数量必须是BL的整数倍。因而地址计算的步长只能是某些特殊的值，即(BL×k)(k为整数)。然而根据旋转角度计算出的理论步长N不一定是BL的整数倍，如图1所示，N＝5,这种情况下，难以利用动态存储器突发传输的优势。因此，本发明结合突发传输的特点，提出一种可变步长累加的地址计算方法。

记一次突发长度内传输的像素点的个数为BLP。首先跟据公式(3)计算出理论步长N，然后将(N×BLP)个像素点看做一个整体，记M＝N×BLP。结合整数划分的思想，M可以按照公式(4)的方式划分，也可以按照公式(5)的方式划分。

公式(4)即是固定步长累加的方法，即将M拆分为多个N值相加。公式(5)即本发明提出的可变步长累加的方法，将M拆分成多个不固定的整数，即step₁，step₂，step₃，……，step_BLP,但是这些整数都是BLP的整数倍，然后将这写整数作为计算存储地址的步长。以BLP＝8,N＝11为例，如图2所示，黑色虚线代表固定步长累加的方式，红色实线代表可变步长累加的方式。由于11不是8的倍数，如果采用固定步长的方式，只能将其近似为8或16。从图2中共可以看出无论被近似为8还是16，固定步长的方式都不能很好地拟合原直线，导致旋转角度与真实旋转角度不一致；而可变步长累加的方法则取得很好的拟合效果。因此在存储地址计算时，采用可变步长累加的方式计算。

按照公式(5)的拆分方式可以有多种拆分结果，为了与直线的拟合结果更佳，本发明采用如下公式计算步长，各步长值如表1所示。

其中，Na_i为N的累加，Sa_i为步长的累加。

表1步长分配结果

下面给出整个图像旋转方法的流程：

(1)以一幅图像左上角为旋转中心，首先由公式(1)计算出原始图像首行首列像素的存储地址(INI0_ROW，INI0_COL)，并根据公式(3)求得N值。

(2)然后根据公式(6)计算出各个可变的步长值step_i，即step₁，step₂，step₃，……，step_BLP，步长结果如表1所示。

(3)每行首列像素的存储地址，根据其上一行首列像素的存储地址计算得到。对于逆时针，每隔2N行，首列像素的存储位置向右移动一个存储单元，即列地址加1；对于顺时针，每隔2N行，首列像素的存储位置向左移动一个存储单元，即列地址减1；

(4)其它像素的存储地址在该行首列像素存储地址的基础上得到。以第一行像素为例，第1至step₁个像素存储在INI0_ROW行。若逆时针旋转，则第(step₁+1)至(step₁+step₂)个像素存储在(INI0_ROW-1)行，第(step₁+step₂+1)至(step₁+step₂+step₃+1)个像素存储在(INI0_ROW-2)行，以此类推，每隔一个步长，存储位置向上移动一行。同样，若顺时针旋转，则行存储地址依次为(INI0_ROW+1)，(INI0_ROW+2)，……其他行的像素的存储地址与第一行像素存储地址的计算方法一样。

(5)如果只按照前面的步骤存储，旋转后的图像会产生空洞，如图3所示。产生空洞的地方，采用向左移动像素填充空洞的方式消除空洞。

按照以上步骤，即可依次求出每个像素点的存储位置。如图4所示，为图像在动态存储器中的存储示意图。图5给出实现该旋转方法的装置示意图。该装置共有10个部分构成，分别是旋转角度输入501，数据输入接口502，初始参数计算模块503，写地址产生器504，输入数据缓存接口505，存储器506，存储器控制器507，读地址产生器508，输出数据缓存接口509，显示设备510。其中，旋转角度输入501，提供需要的旋转角度。数据输入接口502提供原始的图像数据信息，即待旋转的原始图像。初始参数计算模块503根据输入的旋转角度计算出首行首列存储地址(INI0_ROW，INI0_COL)，理论步长N,及多个可变步长step_i等初始地址参数。写地址产生器504负责产生访问存储的写地址。输入数据缓存接口505用于缓存输入的图像数据，由于摄像头输入像素的时钟频率与存储器存储数据的时钟频率不同，因此需要缓存设备解决异步时钟域问题。存储器506即为动态存储器，存储图像数据，与此同时，基于地址空间映射实现图像旋转。存储器控制器507为访问存储器的接口，通过控制器根据读写地址及读写命令访问存储器。读地址产生器508用于产生读地址。输出数据缓存接口509缓存输出数据，解决存储器与显示设备之间的异步时钟域问题。显示设备510用于显示最终的旋转图像。

如图5所示，以720×576的分辨率的图像，tanθ＝1/11，即顺时针旋转5.194°为例给出本发明的一种实施方式。采用DDR存储图像数据，BL设置为4，存储时每个存储单元存储两个像素值，则一次突发传输内传输的像素点的个数为8。此时N＝11，BLP＝8，则M＝88。88个像素会被存储在存储器中的8行，因此88需要被拆分成8个整数相加。根据公式(6)求得step₁＝8，step₂＝16，step₃＝8，step₄＝16，step₅＝8，step₆＝8，step₇＝16，step₈＝8。图6(a)为>