倾斜图像矫正算法的研究

Research on Tilted Image Correction Algorithm

摘要: 为提高倾斜图像矫正效果、降低计算复杂度，本文深入分析了TILT (Transform invariant low-rank textures)算法并对其进行优化改进，包括凸优化算法、拉格朗日乘子法、多分辨策略优化方法等。为了验证算法有效性，本文对车牌、建筑、文字以及人脸等不同类型的倾斜图像进行矫正实验。仿真结果表明，TILT及其改进算法对多种角度甚至是较大角度倾斜图像的矫正都可获得较为理想结果，且改进算法可有效降低计算复杂度，因而该算法在图像的后续处理、识别等领域具有广泛的应用前景。

Abstract: In order to improve the tilt image correction effect and reduce the computational complexity, this paper analyzes and optimizes the TILL (Transform invariant low-rank textures) algorithm, including the convex optimization algorithm, the Lagrange multiplier algorithm, the multi-resolution strategy optimization algorithm, etc. In order to verify the validity of the algorithm, this paper corrects different types of tilt images, such as license plate, building, text and face. The simulation results show that TILT and its improved algorithm can obtain more ideal results for the correction of tilt images from various angles even larger angles, and the improved algorithm can effectively reduce the computational complexity, so the algorithm has a wide range of applications in the fields of image follow-up processing and recognition.

1. 引言

随着信息技术的不断发展，计算机视觉技术被广泛应用于人们的生活情境中，如图像识别及处理技术已广泛应用于医学、交通、金融等领域，为各领域数字化发展打下基础，进一步推动城市信息化建设，由于图像获取时受到环境条件、采集方法等影响，易出现倾斜问题，从而影响了识别的精度。为了有效解决这一问题，倾斜图像矫正技术引起了众多专家学者的关注，也成为了近年来的研究热点。Bindhu A等提出retinex算法来恢复朦胧和彩色投射的水下图像 [1]，陈斌等也提出了对采样照片通过主成分稀疏表示和低秩分解算法进行分割的处理方法 [2]。目前广泛使用的主要是不变特征描述法，即尺度不变特征转换(SIFT: Scale-invariant feature transform)，该算法是一种机器视觉的算法，用来侦测与描述影像中的局部性特征。该算法在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变数 [3]，曾峦等提出基于改进的SIFT特征提取算法的自动图像匹配策略 [4]，丁国绅等提出基于高光谱图像的SIFT特征提取算法 [5]。陈彪等将图像矫正算法应用于自闭症儿童语言和交流培训工具ACC中 [6]，缪新等提出针对MEMS振镜扫描引起的图像畸变的矫正方法 [7]，对于人脸图像方面，魏振婷等解决了传统门禁存在错误的安全问题，提出基于人脸识别和图像矫正的算法 [8]，在智能交通领域，孟祥成等提出针对线阵相机拍摄路面图像灰度不均的矫正方法 [9]，汪乐意提出了FPGA对图像进行畸变矫正 [10]。本文讨论TILT (Transform invariant low-rank textures，即基于变换不变低秩纹理算法)及其改进算法在倾斜图像矫正中的应用，以期获得理想的效果。

2. TILT算法

变换不变低秩纹理(TILT)算法，主要利用图像中的代表结构信息，区别于传统算法只能分析稀有且难以准确测量的量。该算法使用了稀疏低秩逼近的优化函数，使其可有效恢复原图像的仿射变换或投影变化，解决了识别图像中具有特定特征的点或较为奇异区域的难题，是解决三维重构、物体识别等问题的重要基石。

纹理一般指具有一定静态随机特性的图像区域，本文中低秩纹理即为图像中有相当确定性规律或周期性结构的区域，其主要选取图像中具有几何意义的结构，也包括一些常规的局部特征，例如边、角以及具规律性和对称性的图案。当低秩纹理以矩阵表示时，其为低秩矩阵，对应于图像中低秩纹理表现的特性为规律性、对称性和周期性。

可以将二维纹理用二元函数 $I^0\left(x,y\right)$ 表示。若对于任意常数 $y_0$， $I^0\left(x,y_0\right)$ 可以由一组一元函数有限线性表示，定义 $I^0$ 的秩为：

$r=\dim \left(\text{span}\left\{I^0\left(x,y_0\right)|y_0\in ℝ\right\}\right)$ (1)

具有规则对称图案的图像通常为低秩纹理。低秩纹理的概念不仅仅是角落的边缘，还包含更宽范围的特征或区域。但在图像纹理特征提取的过程中，经常会对图像进行平移、旋转、尺度缩放、仿射和投影等处理，而且纹理函数采样值还有可能会遭到许多类型的破坏，如量化、噪声和遮挡等，此时计算机无法将变化后图像与原始图像相对应，同时图像的对称性、规律性等特征也会受到破坏，图像的秩可能会增加，图像并不一定仍具有低秩纹理。

假设低秩纹理 $I^0\left(x,y\right)$ 位于场景中的平面上，从某个视角观察到的图像函数 $I\left(x,y\right)$ 是原低秩纹理函数 $I^0\left(x,y\right)$ 的变形：

$I\left(x,y\right)=I^0\circ {\tau }^{-1}\left(x,y\right)=I^0\left({\tau }^{-1}\left(x,y\right)\right)$ (2)

其中 $\tau$ 表示旋转变形、仿射变形或投影变形， $I\left(x,y\right)$ 表示变形后的纹理。在实际生活中，原始照片会存在倾斜、阴影、模糊、部分损坏等情况，即产生初始变形。在一般情况下，变形后的纹理 $I\left(x,y\right)$，作为一个矩阵不再是低秩。低秩纹理除了视角变化之外，还可能被噪声和遮挡所破坏，或者包含来自周围背景的一些像素。可以通过误差矩阵 对这种偏差进行建模，如下所示：

$I=I^0+E$ (3)

此时图像I不再是一个低秩纹理。在本文中，都假设只有一小部分的图像像素被损坏，因此E是一个稀疏矩阵。为从包含变形和损坏的图像中恢复确切的低秩纹理 $I^0$，给定一个变形和损坏的图像纹理： $I=\left(I^0+E\right)\circ {\tau }^{-1}$，恢复低秩纹理 $I^0$ 和域变换 $\tau$。从而可得以下的优化问题：

$\underset{I^0,E,\tau }{\min }\text{rank}\left(I^0\right)+\gamma {\Vert E\Vert }_0\text{s}\text{.t}\text{.}I\circ \tau =I^0+E$ (4)

其中 ${\Vert E\Vert }_0$ 表示E中非零项的数量，用以寻找尽可能最低秩的纹理 $I_0$，得到域变换 $\tau$ 的误差矩阵E。 $\gamma >0$ 是一个加权参数，该参数权衡纹理的秩与误差的稀疏性。解决 $I^0$ 这个问题就称为变换不可变的低秩纹理(TILT)。

虽然秩函数和l₀-范数在原问题(4)是非常难以优化的，它是一般的NP问题。但是在相当广泛的条件下，可以用矩阵核范数 ${\Vert I^0\Vert }_{*}$ 代替低秩纹理 $I^0$ 的秩，以l₁-范数 ${\Vert E\Vert }_1$ 代替 ${\Vert E\Vert }_0$。因此，最终的优化问题，如下：

$\underset{I^0,E,\tau }{\min }{\Vert I^0\Vert }_{*}+\gamma {\Vert E\Vert }_1\text{s}\text{.t}\text{.}I\circ \tau =I^0+E$ (5)

虽然上述问题的目标函数是凸的，但是约束条件 $I\circ \tau =I^0+E$ 在域变换 $\tau$ 上是非线性的。因此该问题是非凸的。为解决这一问题，一般方法是在当前的估计和迭代中线性化约束，线性化形式的约束可表示为：

$I\circ \tau +\nabla I\Delta \tau =I^0+E$ (6)

其中 $\nabla I$ 是图像变换参数的倒数。在(5)中的优化问题会减化到：

$\underset{I^0,E,\tau }{\min }{\Vert I^0\Vert }_{*}+\lambda {\Vert E\Vert }_1\text{s}\text{.t}\text{.}I\circ \tau +\nabla I\Delta \tau =I^0+E$ (7)

虽然该线性化只是对原非线性问题的局部逼近，但是通过迭代，可收敛得到一个原非凸问题(5)的局部最小值。

综上所述，总结算法如下：

算法1：

输入：输入图像I，初试变形 $\tau$，权系数 $\lambda >0$。

输出：问题(5)的最优解 $I^{0*}$， $E^{*}$， $\Delta {\tau }^{*}$。

当未收敛到最小值时进入以下循环：

步骤1：归一化和计算 $\nabla I$ ：

$I\circ \tau \leftarrow \frac{I\circ \tau }{{\Vert I\circ \tau \Vert }_F};\nabla I\leftarrow \frac{\partial }{\partial \zeta }{\left({\frac{\text{vec}\left(I\circ \zeta \right)}{\Vert \text{vec}\left(I\circ \zeta \right)\Vert }}_F\right)|}_{\zeta =\tau };$

步骤2 (内循环)：解决线性化问题：

$\begin{array}{l}\left(I^{0*},E^{*},\Delta {\tau }^{*}\right)\leftarrow \arg {\min }_{I^0,E,\Delta \tau }{\Vert I^0\Vert }_{*}+\lambda {\Vert E\Vert }_1\\ \text{s}\text{.t}\text{.}I\circ \tau +\nabla I\nabla \tau =I^0+E;\end{array}$

步骤3：更新变形：

$\tau \leftarrow \tau +\Delta {\tau }^{*};$

3. 算法优化

3.1. 基于增广拉格朗日乘子优化

观察算法1可以发现，算法中计算量最大最耗时的部分为迭代循环过程的第二步内循环，这一步中主要进行的是凸优化操作。对于这种优化问题可使用传统内点法进行优化。虽然内点法在解决优化问题时能够得到较准确的收敛结果，但它在处理数据量较大的问题时，精确度和效率都会有明显降低，因此当输入图像较大时，算法1所需处理时间更长。

针对这一问题，林宙成等人提出的增广拉格朗日乘子法 [11] 在处理类似核范数的最小化问题时能取得高效且相对准求的效果。

根据拉格朗日乘子法的定义，设定如下凸优化问题：

${\min }_{x}f\left(x\right)\text{s}\text{.t}\text{.}\psi \left(x\right)=b$ (8)

式中目标函数f为凸优化方程，约束条件 $\psi$ 为线性方程。包含约束条件的凸优化问题，可依据基本拉格朗日乘子法可将其转化为近似无约束条件的优化问题，即可将上式(8)转化为以下增广拉格朗日方程式：

$L_{\mu }\left(X,Y\right)=f\left(x\right)+\langle Y,b-\psi \left(x\right)\rangle +\frac{\mu }{2}{\Vert b-\psi \left(x\right)\Vert }_2^2$ (9)

式中Y为拉格朗日乘子向量， ${\Vert \cdot \Vert }_2$ 表示欧几里得范数，即矩阵， $\mu >0$ 表示附加在不可行点上的惩罚量。按照上面的定义，应用ALM算法求解，可将上式转化为以下增广拉格朗日方程的凸优化问题：

$L_{\mu }\left(I^0,E,\Delta \tau ,Y\right)=f\left(I^0,E\right)+\langle Y,R\left(I^0,E,\Delta \tau \right)\rangle +\frac{\mu }{2}{\Vert R\left(I^0,E,\Delta \tau \right)\Vert }_F^2$ (10)

其中， 为拉格朗日乘子矩阵， $\langle \cdot ,\cdot \rangle$ 表示矩阵内积。同时对多个未知量优化求解相对而言较为复杂，为解决该问题可用交替方向法来依次求取最优值，因此可将式(9)转化为利用交替方向法得到的迭代计算式即式(10)。在式(10)中最复杂的运算是在第一步，求 $I^0,E$ 和 $\Delta \tau$ 这三者的最优值。对这三者同时求解最小值将会有较大的计算量，可用同样的处理方法，对这三者逐个求最优解，如下所示：

$\{\begin{array}{l}{I}_{k+1}^0\leftarrow {\min }_{I^0}L\left(I^0,E,\Delta \tau ,Y_k,{\mu }_k\right)\\ E_{k+1}\leftarrow {\min }_{E}L\left(I_{k+1}^0,E,\Delta \tau ,Y_k,{\mu }_k\right)\\ \Delta {\tau }_{k+1}\leftarrow {\min }_{\Delta \tau }L\left(I_{k+1}^0,E_{k+1},\Delta \tau ,Y_k,{\mu }_k\right)\end{array}$ (11)

为方便求解，式(11)可以用收缩算子的方法进行转化，如下式：

$\{\begin{array}{l}{I}_{k+1}^0\leftarrow U_k{S}_{{\mu }_k^{-1}}\left[{\text{Σ}}_k\right]V_k^{\text{T}}\\ E_{k+1}\leftarrow S_{\lambda {\mu }_k^{-1}}\left(I\circ \tau +\nabla I\Delta {\tau }_k-I_{k+1}^0-{\mu }_k^{-1}{Y}_k\right)\\ \Delta {\tau }_{k+1}\leftarrow {\left(\nabla I^{\text{T}}\nabla I\right)}^{-1}\nabla I^{\text{T}}\left(-I\circ \tau +I_{k+1}^0+E_{k+1}-{\mu }_k^{-1}{Y}_k\right)\end{array}$ (12)

综合以上分析过程，再结合交替方向法可将算法1中第二步内循环过程优化为算法2。

算法2 (解决算法1的内循环)：

输入：当前变形和归一化后的图像 $I\circ \tau$ 及其对于变形 $\tau$ 的 $\nabla I$，和 $\lambda >0$。

输出：对问题(10)的解( $I^0$，E， $\nabla \tau$ )。

初始值： $k=0$， $Y_0=0$， $E_0=0$， $\nabla {\tau }_0=0$， ${\mu }_0>0$， $\rho >1$ ；

当未收敛到最小值时进入以下循环：

$\left(U_k,{\displaystyle \sum k},V_k\right)=\text{svd}\left(I\circ \tau +\nabla I\Delta {\tau }_k-E_k+{\mu }_k^{-1}{Y}_k\right);$

$I_{k+1}^0=U_k{S}_{{\mu }_k^{-1}}\left[{\displaystyle \sum k}\right]V_k^{\text{T}};$

$E_{k+1}=S_{\lambda {\mu }_k{}^{-1}}\left[I\circ \tau +\nabla I\Delta {\tau }_k-I_{k+1}^0+E_{k+1}-{\mu }_k^{-1}{Y}_k\right];$

$\Delta {\tau }_{k+1}=\left(\nabla I\right)\left(-I\circ \tau +I_{k+1}^0+E_{k+1}-{\mu }_k^{-1}{Y}_k\right);$

$Y_{k+1}=Y_k+{\mu }_k\left(I\circ \tau +\nabla I{\Delta }_{\tau }{}_{k+1}-I_{k+1}^0-E_{k+1}\right);$

${\mu }_{k+1}=\rho {\mu }_k;$

从算法2中可以观察到，可用求奇异值分解的方法减少算法中较为复杂的部分，使得该算法的计算效率得到有效提高。将这种数学的优化方法运用到上文提出的算法中，即将算法2加入到算法1的第二步中，便可得出经优化后的特征提取算法，算法1和算法2共同组成了基于矩阵低秩性提取旋转不变纹理特征的完整算法。

3.2. 多分辨策略优化方法

在降低计算矩阵秩的运算量方面，本文在算法的实现过程中使用了多分辨策略，通过降低图像的分辨率，减少每次计算图像秩的时间，以达到算法提速的目的。多分辨策略在图像处理算法研究中是降低矩阵运算量的一种常用方法 [12]。当降低图像分辨率时，图像本身的信息会有所丢失，从而导致图像秩的大小也会发生改变。但对于同一分辨率下的图像来说，它们秩的大小关系并不会因为信息丢失而发生改变。由于TILT算法是将图像进行旋转，并比较秩的大小来获得最小秩的图像。因此降低图像分辨率的同时，噪声也会随之被弱化，可有效地减少噪声对算法计算时间的影响。

纹理图像在矩阵中表现为一定的周期性，要保证图像中纹理模型的结构不发生变化，就必须使图像分辨率降低的量小于该周期量。对于不同的纹理模型的图像可对其分辨率进行不同程度的降低。在本文试验中初始设定为对图像进行两次下采样操作。一次为先转换为低分辨率图像，再求取纹理矩阵秩达到最小时的空间变换τ，再对τ进行空间变换，最后得到地址纹理图像；还有为直接按τ进行空间变换，得到低秩纹理图像。

4. 实验方案测试与分析

4.1. 实验方案介绍

Affine方案的第一步为先对图像进行平面旋转，再通过秩大小比较得到平面低秩图像。第二步则图像调整左右两边，如同以中心水平线为轴进行定幅度的旋转来实现垂直方向上的图像形变，同理再通过秩比较得到竖直的图像。第三步调整上下两边，如同以中心垂直线为轴进行旋转来实现水平方向上的形变，同理最后比较秩的大小得到最后的矫正图像。

Homography方案与Affine方案有较为相近的处理过程，尤其是在平面旋转矫正、垂直方向倾斜矫正和水平方向倾斜矫正这三步上。而不同的是Homography方案有着与Affine方案不同的工作空间，其可工作于三维空间。

4.2. 不同方案倾斜车牌图像矫正

在大多数现实场景中，得到的车牌图像往往不仅仅只有一种倾斜方向，混合多种倾斜的矫正对于日常应用更具参考性。如图1~图6为不同程度的混合倾斜图像，采用不同的矫正方案得到的实验结果，并对比Affine方案与Homography方案的优劣。

(a)(b)

Figure 1. The two schemes deal with minor mixed tilt correction. (a) Affine scheme; (b) Homography scheme

图1. 两种方案处理较小混合倾斜矫正。(a) Affine方案；(b) Homography方案

(a)(b)

Figure 2. The two schemes deal with large mixed tilt correction. (a) Affine scheme; (b) Homography scheme

图2. 两种方案处理较大混合倾斜矫正。(a) Affine方案；(b) Homography方案

(a)(b)

Figure 3. The two schemes deal with great mixed tilt correction. (a) Affine scheme; (b) Homography scheme

图3. 两种方案处理极大混合倾斜矫正。(a) Affine方案；(b) Homography方案

如图1~图3为不同程度的混合倾斜矫正得到的实验结果。图1为混合倾斜程度较小的倾斜矫正，该结果显示图1(a)的Affine方案能实现理想的矫正效果，但带有略微的混合倾斜；而图1(b) Homography方案对程度较小的倾斜图像有非常理想的矫正效果，结果无论是在矫正幅度还是边界的分割上都十分理想。在图2(a)较大的混合倾斜矫正图像中Affine方案仍有一定的矫正效果，但含有较严重的混合倾斜情况；与此同时，图2(b) Homography方案对于较大倾斜幅度的混合倾斜有一定的矫正能力，但是输出车牌图像的边界并非十分理想，图2的两种方案初始化工作都有一定的困难。最后当混合倾斜程度极大时，两种方案结果如图3(a)所示，Affine方案有一定矫正效果，但已无法实现理想完全正向的矫正，输出结果仍带有较明显的倾斜；如图3(b)所示的Homography方案可较好矫正过大倾斜幅度的混合倾斜，输出结果在矫正幅度和边界分割上都可达到理想要求，但图3的初始化过程已十分困难。比较以上Affine方案和Homography方案对混合倾斜车牌的处理结果，可知Affine和Homography方案对混合倾斜车牌图像都有较好的矫正效果，随着倾斜幅度的增大，Homography方案的倾斜矫正能力强于Affine方案。

4.3. 不同场景图像倾斜矫正

由上节实验结果可知，Homography方案相对于Affine方案有更好的矫正效果，故本节主要采用Homography方案进行倾斜图像矫正。以下为日常生活中的一些常见的场景，图4和图5为大楼代表建筑场景，图6和图7为路牌代表中文文字场景，图8和图9为人脸代表人脸识别，图10和图11为英文代表英文文字场景，图12和图13为灯具代表较复杂生活场景。对于各矫正图像，红色方框为原图选取场景即输入图像，绿色方框为矫正图框即输出的图像。

Figure 4. Building image initial marquee

图4. 建筑图像初始选取框

Figure 5. Building image tilt correction

图5. 建筑图像倾斜矫正结果

首先对大楼的建筑场景进行倾斜矫正，如图4大楼总体结构复杂程度适中，无明显对称结构，且窗户数量较多，增加一定矫正难度，但其所含物体等较少，且倾斜程度也为适中，作为建筑场景的图像代表而言，选取该图像较为合适。如图5从矫正结果来说，矫正效果较好，畸变程度较低，保持原有图像特征，可充分将图像原有噪声等取出，将原本倾斜的图像矫正为基本呈水平状态。

图6中路牌倾斜角度较大，图像中文字信息较为丰富，为图像后续的倾斜矫正提供一定难度，且对于图像倾斜矫正有较明显的效果呈现。图7为其矫正结果，原本倾斜的图像得到较好的矫正，倾斜的文字也得到较好的矫正，文字清晰几乎无明显变形，但边框选取仍有一点问题，但已可为后续的文字识别提供较好的基础。

Figure 6. Road sign image initial marquee

图6. 路牌图像初始选取框

Figure 7. Road sign image tilt correction

图7. 路牌图像倾斜矫正

图8为对于人脸的图像矫正，在日常的生活中，人脸识别可应用于多种场景，人脸为基本对称图像，该图像倾斜程度适中。该图像的矫正结果如图9虽然人脸图像额头处有较小失真被拉长，但总体而言矫正结果较好，也说明了该算法可用于人脸图像处理以及人脸识别等方面的应用。

Figure 8. Face image initial marquee

图8. 人脸图像初始选取框

Figure 9. Face image tilt correction

图9. 人脸图像倾斜矫正

图10为对英文图像的矫正，该英文处于倾斜圆柱体上，倾斜程度较为复杂，且相对于整体图像而言该部分较小。从矫正结果如图11来说，英文图像得到了较好的倾斜矫正，字母清晰程度比较高，体现该算法对只占图像较小部分的英文也有较好的矫正能力。

Figure 10. English image initial marquee

图10. 英文图像初始选取框

Figure 11. English image tilt correction

图11. 英文图像倾斜矫正

最后为对倾斜的灯具图像的矫正，如图12该灯具整体外形较为复杂，也存在较大的倾斜角度，对此倾斜图像矫正有一定的难度。从矫正结果如图13而言，图像矫正结果较好，该灯具顶部和底部切割较好，虽灯具底座仍有较小程度的倾斜，但影响不大，整体结果而言符合预期。

Figure 12. Lamp image initial marquee

图12. 灯具图像初始选取框

Figure 13. Lamp image tilt correction

图13. 灯具图像倾斜矫正

5. 总结

大量基于低秩矩阵的倾斜图像矫正技术应用的实验表明，该算法对于多种角度的车牌倾斜情况，甚至是一些大角度的车牌倾斜情况都有理想的矫正效果，且对于各种类型的复杂图像也都有一定的矫正效果，为后续识别等提供较好基础。因此，基于低秩矩阵的倾斜图像矫正技术在图像识别领域具有较好的应用前景，同时，对于推动人脸识别技术、文字识别技术和智能交通技术等的发展也有重要的意义。

基金项目

浙江省自然科学基金资助项目(No.LY17F010003)。

NOTES

^*通讯作者。