一种图像去抖动设备及其方法

摘要

本发明公开了一种图像去抖动设备及其方法。该设备包括：特征点选取单元，用于从连续的F帧图像中的一帧图像中选取N个特征点；矩阵生成单元，用于跟踪所述N个特征点在所述F帧图像中的其它帧图像中的坐标，并从中选取m个特征点，利用所述m个特征点的在F帧图像中的坐标生成矩阵M；矩阵分解单元，用于对所述矩阵M进行分解；去抖动单元，用于对分解所得矩阵去抖动，得到去抖的特征点坐标；重建单元，用于基于去抖的特征点坐标进行图像重建。通过本发明能够获得高清晰度和低抖动性的视频图像。

权利要求

1.一种图像去抖动设备，包括：

特征点选取单元，用于从连续的F帧图像中的一帧图像中选取N个特征点；

矩阵生成单元，用于跟踪所述N个特征点在所述F帧图像中的其它帧图像中的坐标，并从中选取m个特征点，利用所述m个特征点的在F帧图像中的坐标生成矩阵M；

矩阵分解单元，用于对所述矩阵M进行分解，将所述矩阵M分解为矩阵C和矩阵E：M≈W⊙(C2m×rEr×k)，对M进行分解，得到：其中W是二进制掩码矩阵，其中的0指示消失的数据，而1指示存在的数据，符号⊙表示按元素的乘法,所述矩阵E为所述m个特征点中的多个代表点的轨迹矩阵，所述矩阵C为所述m个特征点与所述多个代表点之间的几何关系， 当已处理所述F帧图像中的δ帧之后，移除所述矩阵M中的γδ个点，引进后续的δ帧，添加后面帧中γδ个皆出现的特征点，所述矩阵M变为矩阵M1,矩阵M1如下：

其中

去抖动单元，用于对分解所得矩阵E去抖动，得到去抖的特征点坐标；

重建单元，用于基于去抖的特征点坐标进行图像重建。

2.如权利要求1所述的设备，其特征在于，所述特征点选取单元确定待取特征点的位置和最小特征值，并选取最小特征值最大、且两两距离大于预先设定的特定值的前N个像素点作为特征点。

3.如权利要求1所述的设备，其特征在于，矩阵生成单元通过连续分层处理确定各帧图像之间的位移矢量。

4.如权利要求1所述的设备，其特征在于，所述m个特征点为在F帧图像中皆出现的特征点。

5.如权利要求1所述的设备，其特征在于，所述重建单元通过平移和/或旋转和/或缩放方式使每帧图像从其原始位置校正到光滑的运动轨迹上的位置。

6.如权利要求1所述的设备，其特征在于，所述重建单元基于去抖的特征点坐标进行保持图像内容的扭转重建。

7.如权利要求6所述的设备，其特征在于，所述重建单元还包括：划块单元，用于将图像划成网格；

坐标计算单元，用于计算去抖后的网格顶点坐标和网格内各点的坐标；以及插值单元，用于将各点坐标插值成为整数点。

8.如权利要求7所述的设备，其特征在于，所述坐标计算单元对去抖后网格进行如下限制：去抖后网格尽可能保持原来直角三角形网格的刚性；去抖后网格要与控制点尽可能的一致。

9.如权利要求1所述的设备，其特征在于，在对图像进行重建的过程中，如果当前图像边缘像素丢失，使用当前图像之前和/或之后的图像中的像素进行回填，并将这些图像无缝地融合以生成新的图像。

10.一种图像去抖动方法，包括：

从连续的F帧图像中的一帧图像中选取N个特征点；

跟踪所述N个特征点在所述F帧图像中的其它帧图像中的坐标，并从中选取m个特征点，利用所述m个特征点的在F帧图像中的坐标生成矩阵M；

将所述矩阵M分解为矩阵C和矩阵E：M≈W⊙(C2m×rEr×k)，对M进行分解，得到：其中W是二进制掩码矩阵，其中的0指示消失的数据，而1指示存在的数据，符号⊙表示按元素的乘法,所述矩阵E为所述m个特征点中的多个代表点的轨迹矩阵，所述矩阵C为所述m个特征点与所述多个代表点之间的几何关系， 当已处理所述F帧图像中的δ帧之后，移除所述矩阵M中的γδ个点，引进后续的δ帧，添加后面帧中γδ个皆出现的特征点，所述矩阵M变为矩阵M1,1

矩阵M如下：

其中

对所述矩阵E去抖动，得到去抖的特征

点坐标；

用于基于去抖的特征点坐标进行图像重建。

11.如权利要求10所述的方法，还包括确定待取特征点的位置和最小特征值，并选取最小特征值最大、且两两距离大于预先设定的特定值的前N个像素点作为特征点；所述m个特征点为在F帧图像中皆出现的特征点。

12.如权利要求11所述的方法，其特征在于，通过连续分层处理确定各帧图像之间的位移矢量。

13.如权利要求10所述的方法，其特征在于，通过平移和/或旋转和/或缩放方式使每帧图像从其原始位置校正到光滑的运动轨迹上的位置。

14.如权利要求10所述的方法，其特征在于，基于去抖的特征点坐标进行保持图像内容的扭转重建。

15.如权利要求14所述的方法，其特征在于，进行保持图像内容的扭转重建还包括：将图像划成网格；计算去抖后的网格顶点坐标和网格内各点的坐标；以及将各点坐标插值成为整数点。

说明书

一种图像去抖动设备及其方法

技术领域

[0001] 本发明涉及图像处理领域，尤其涉及一种图像去抖动设备及其方法。

背景技术

[0002] 图像去抖动技术指的是从摄像机的实际运动中去除不期望的无意运动，这样处理后的视频在视觉上将变得平滑，减轻了由于无意运动引起的画面之间的跳动感。

[0003] 现有的去抖动方法主要分为两大类：光学去抖动和电子去抖动。光学防抖是通过镜头内置的仪器感应相机的抖动，再通过调整镜头内透镜的位置而达到去抖动效果。电子去抖动，是通过电子手段来对图像进行处理，以减轻抖动对图像的影响。电子防抖的方法很多，一种方式是通过陀螺仪等传感器来感知当前相机的抖动情况，从而实现去抖动功能。还有一种方式是通过后期对抖动模糊图像进行图像处理来对图像进行抖动补偿。

[0004] 采用了加速度计等传感器的方法需要增加一定硬件成本。而通过后期对抖动模糊图像进行图像处理的方法一般计算量很大、且耗时长，无法实现在便携式设备上。

[0005] 因此，需要一种新颖的去抖动技术，能够至少部分地解决上述现有技术中存在的问题。

发明内容

[0006] 本发明的目的是提供一种图像去抖动设备及其方法。通过本发明的图像去抖动设备及其方法，可大幅度减少计算量，降低了硬件设备的配置需求，使得能够在低配置的移动端设备上使用，最后得到的视频图像具有高清晰度和低抖动性的优点。

[0007] 根据本发明的一个方面，提供一种图像去抖动设备，包括：特征点选取单元，用于从连续的F帧图像中的一帧图像中选取N个特征点；矩阵生成单元，用于跟踪所述N个特征点在所述F帧图像中的其它帧图像中的坐标，并从中选取m个特征点，利用所述m个特征点的在F帧图像中的坐标生成矩阵M；矩阵分解单元，用于对所述矩阵M进行分解；去抖动单元，用于对分解所得矩阵去抖动，得到去抖的特征点坐标；重建单元，用于基于去抖的特征点坐标进行图像重建。

[0008] 进一步地，所述特征点选取单元确定待取特征点的位置和最小特征值，并选取最小特征值最大、且两两距离大于预先设定的特定值的前N个像素点作为特征点。

[0009] 进一步地，矩阵生成单元通过连续分层处理确定各帧图像之间的位移矢量。

[0010] 进一步地，所述m个特征点为在F帧图像中皆出现的特征点。

[0011] 进一步地，矩阵分解单元将所述矩阵M分解为矩阵C和矩阵E，所述矩阵E为所述m个特征点中的多个代表点的轨迹矩阵，所述矩阵C为所述m个特征点与所述多个代表点之间的几何关系。

[0012] 进一步地，所述去抖动单元对所述矩阵E的行向量进行光滑化处理。

[0013] 进一步地，所述重建单元通过平移和/或旋转和/或缩放方式使每帧图像从其原始位置校正到光滑的运动轨迹上的位置。

[0014] 进一步地，所述重建单元基于去抖的特征点坐标进行保持图像内容的扭转重建。

[0015] 进一步地，所述重建单元还包括：划块单元，用于将图像划成网格；坐标计算单元，用于计算去抖后的网格顶点坐标和网格内各点的坐标；以及插值单元，用于将各点坐标插值成为整数点。

[0016] 进一步地，所述坐标计算单元对去抖后网格进行如下限制：去抖后网格尽可能保持原来直角三角形网格的刚性；去抖后网格要与控制点尽可能的一致。

[0017] 进一步地，在对图像进行重建的过程中，如果当前图像边缘像素丢失，使用当前图像之前和/或之后的图像中的像素进行回填，并将这些图像无缝地融合以生成新的图像。

[0018] 根据本发明的一个方面，提供一种图像去抖动方法，包括：从连续的F帧图像中的一帧图像中选取N个特征点；跟踪所述N个特征点在所述F帧图像中的其它帧图像中的坐标，并从中选取m个特征点，利用所述m个特征点的在F帧图像中的坐标生成矩阵M；将所述矩阵M分解为矩阵C和矩阵E，所述矩阵E为所述m个特征点中的多个代表点的轨迹矩阵，所述矩阵C为所述m个特征点与所述多个代表点之间的几何关系；对所述矩阵E去抖动，得到去抖的特征点坐标；用于基于去抖的特征点坐标进行图像重建。

[0019] 与现有技术相比，本发明的所提供的方案计算量小、对硬件设备的配置要求不高、并且能够获得高清晰度和低抖动性的视频图像。

附图说明

[0020] 为了进一步阐明本发明的各实施例的以上和其它优点和特征，将参考附图来呈现本发明的各实施例的更具体的描述。可以理解，这些附图只描绘本发明的典型实施例，因此将不被认为是对其范围的限制。在附图中，相同或相应的部件将用相同或类似的标记表示。

[0021] 图1示出根据本发明的一个实施例的视频去抖动设备100。

[0022] 图2示出根据本发明的一个实施例的运动分析的离散结果按时间的累积。

[0023] 图3示出了根据本发明的一个实施例的矩阵分解图。

[0024] 图4示出根据本发明的一个实施例的重建单元105的结构示意图。

[0025] 图5示出根据本发明的一个实施例将图像划分成网格的示意图。

[0026] 图6示出根据本发明的一个实施例的相对坐标的示意图。

[0027] 图7示出根据本发明的一个实施例方程组系数A的记法的示意图。

[0028] 图8示出根据本发明的一个实施例的三角形变形保持内部的比例关系的示意图。

[0029] 图9示出根据本发明的一个实施例的视频去抖动方法的流程图900。

具体实施方式

[0030] 在以下的描述中，参考各实施例对本发明进行描述。然而，本领域的技术人员将认识到可在没有一个或多个特定细节的情况下或者与其它替换和/或附加方法、材料或组件一起实施各实施例。在其它情形中，未示出或未详细描述公知的方法或操作以免造成本发明的各实施例的诸方面晦涩。类似地，为了解释的目的，阐述了特定数量和配置，以便提供对本发明的实施例的全面理解。然而，本发明可在没有特定细节的情况下实施。

[0031] 本发明提供了一种视频去抖动的设备和方法。首先从待处理视频取F帧图像，从这些帧中提取特征点，实时计算这些特征点的位置；然后运用统计学方法拟合特征点的光滑运动轨迹，将每帧图像从其原始位置校正到光滑运动轨迹位置。

[0032] 图1示出根据本发明的一个实施例的视频去抖动设备100。如图1所示，视频去抖动设备100包括特征点选取单元101、矩阵生成单元102、矩阵分解单元103、去抖动单元104和重建单元105。

[0033] 视频去抖动设备100将待处理视频取连续的F帧图像作为处理对象。特征点选取单元101从F帧图像中的一帧中选取N个特征点。矩阵生成单元102在其它帧图像中跟踪这N个特征点，从N个特征点中选取F帧图像中都出现的m个点存到矩阵M。矩阵分解单元103对矩阵M进行分解M≈W⊙CE。去抖动单元104对矩阵E去抖，由此利用M≈W⊙CE,得到m个去抖的特征点坐标。然后，重建单元105基于去抖的特征点坐标进行图像重建。

[0034] 下面结合各个单元详细描述视频去抖动设备100的具体细节和工作过程。

[0035] 特征点选取单元101从F帧图像中的一帧中选取N个特征点。特征点要求具有显著的纹理特征，即图像中具有代表性以及健壮性的点。

[0036] 可通过各种方法来确定特征点。例如，可使用FAST特征点检测算法或SIFT(Scale-invariant feature transform)局部特征点检测算法。

[0037] 在本发明的一个实施例中，特征点选取单元101可采用如下方法从第一帧中选取N个特征点，设第一帧为图像I(x,y)，定义以下矩阵[1]：

[0038]

[0039] 其中W为几个像素的像素块,Ix表示图像I(x,y)在x方向上的梯度Ix(x,y)＝[I(x+1,y)–I(x–1,y)]/2，Iy表示图像I(x,y)在y方向上的梯度Iy(x,y)＝[I(x,y+1)–I(x,y–1)]/
2。

[0040] 该矩阵[1]的两个特征值为：

[0041]

[0042] 取公式[2]中的最小特征值λ＝min{λ1,λ2}。

[0043] 记录各个待取特征点的位置(x,y)和最小特征值λ。

[0044] 特征点要求具有显著的纹理特征，即图像中具有代表性以及健壮性的点，这就要求两个特征值皆为充分大的正值。故取其最小特征值λ最大、且两两距离大于预先设定的特定值的前N个点。

[0045] 矩阵生成单元102跟踪N个特征点在F帧图像中的其余帧中的坐标，从N个特征点中选取F帧图像中都出现的m个点存到矩阵M。在本发明的实施例中，可采用各种匹配算法确定N个特征点在其余帧中的坐标。

[0046] 例如，可采用SAD(绝对差之和)图像匹配算法确定N个特征点在各个帧中的坐标。

[0047] 首先，考虑特征点在各个帧之间的位移足够小的情况。

[0048] 在第t+1帧中，构造由若干像素组成的像素块w(例如，10×10像素块)，特征点(x，y)位于像素块w内。设J(x)＝I(x,y,t+1)，并且I(x-d)＝I(x-u,y-v,t)，为了简化省略时间变量t，可得：

[0049] J(x)＝I(x-d)+n(x)  [3]

[0050] 其中n表示噪声，I(x,y,t+1)表示在第t+1帧中像素点(x，y)的像素值，I(x-u,y-v,t)表示在第t帧中像素点(x-u,y-v)的像素值，d＝(u,v)表示位移矢量。

[0051] 像素块w区域内像素点(x，y)与(x-u,y-v)的差的平方和为∫w[I(x-d)-J(x)]2dx。对于不同的位移矢量d，将得到不同的平方和。当t+1帧与t帧的像素块最相似时，该平方和最小，因此在搜索范围内针对位移矢量d的所有可能取值，计算平方和，并且将这些平方和中的最小值所对应的位移矢量d确定为第t+1帧中像素点(x，y)与第t帧中的对应像素点(x-u,y-v)之间的位移矢量。

[0052] 当位移矢量d较小时，可作出以下近似：

[0053]

[0054] 并且令：

[0055]

[0056] 因此，

[0057] 对u，v求导，即得最优解为：

[0058]

[0059] 然而，当各个帧之间的位移较大时，需要对上述计算方法进行改进。在本实施例中，经由连续的分层处理查找正确的位移矢量。首先，分别在各下采样图像，如I＝I↓8,I↓4,I↓2,求得位移矢量，然后以所得的(u,v)放大作为新的初值，获得较精确的位移矢量。

[0060] 假设已经获得比较粗糙的解(u(n),v(n))，则：

[0061] J(n)(x)＝I(x-u(n)-du，y-v(n)-dv，t+1)  [8]

[0062] 因此，公式[7]化为：

[0063]

[0064] 该方程还可记为：

[0065]

[0066] 直接得到

[0067]

[0068] 上述过程可归纳为以下步骤：

[0069] 1.初始化(u,v)为0或上一帧的解或分层处理中粗糙层所得解的上采样；

[0070] 2.在获得u(n),v(n)的情况下，利用公式[11]得到du,dv,u(n+1)＝u(n)-du，v(n+1)＝v(n)-dv；

[0071] 3.更新E、F，重复步骤2，直至du,dv趋向为零。

[0072] 根据获得的位移矢量，可计算出N个特征点在各个帧中的坐标。

[0073] 基于本发明公开的特征点检测和图像匹配算法运算效率非常高，在嵌入式设备如手机、平板电脑等有限的内存空间存储以及计算资源的产品中拥有很好的应用前景。

[0074] 第i个特征点在F个帧图像中的坐标形成第i特征点轨迹 对于在某一帧图像中消失的点，可记为最后一次跟踪到的位置

[0075] 将n个特征点轨迹排列为矩阵：

[0076]

[0077] 在上面n个点中，取m个在k(k＝F)个帧中皆出现的特征点。在特殊情况下，有可能最初不能取得m个这样的特征点，此时需要将k值减小。另外，不能确保在接下来的帧中这些特征点不会消失。

[0078] 将在k帧中皆出现的m个特征点排列为矩阵M2m×k：

[0079]

[0080] 图2示出根据本发明的一个实施例的运动分析的离散结果按时间的累积。

[0081] 如图2所示，曲线201是特征点坐标的真实轨迹，曲线202是假设另一不抖动相机拍摄的无抖动特征点的轨迹。因此，本发明通过数值拟合合成光滑的运动轨迹，使真实轨迹201无限接近轨迹202。通过平移、旋转和/或缩放等方式使每帧图像从其原始位置校正到光滑的运动轨迹上的位置。

[0082] 如果对于上面的轨迹矩阵直接进行独立的光滑化处理，由于点数太多，可能会造成图像的几何结构受到严重破坏，弄巧成拙。

[0083] 因此提取轨迹矩阵的几个(r/2)代表点(其矩阵为E)做光滑化，保持原来的点与这几个点的几何关系C。

[0084] 即，矩阵分解单元103对矩阵M进行分解：

[0085] M＝M0≈W⊙(C2m×rEr×k)  [14]

[0086] 其中W是二进制掩码矩阵，其中的0指示消失的数据，而1指示存在的数据，符号⊙表示按元素的乘法，即，R＝P⊙Q，表示ri,j＝pi,j·qi,j。

[0087] 对M0进行分解，得到：

[0088]

[0089] 其中

[0090] 当处理了δ帧之后，移除上面矩阵的γδ个点，引进后续的δ帧，添加后面帧中γδ个皆出现的特征点。此时轨迹矩阵由M0变为M1，但是这两个矩阵具有相同的部分。参见图3，图3示出了根据本发明的一个实施例的矩阵分解图。

[0091] 矩阵M1如下：

[0092]

[0093] 显然，只有E2和C2是未知的，近似求解这两个矩阵，得到：

[0094]

[0095]

[0096] 其中 为r×r矩阵。

[0097] 对于新的场景切换，初始矩阵M0的化简无法通过上面的方法求解。为了求解矩阵C和E，利用以下方程[19]:

[0098]

[0099] 即

[0100]

[0101] 可通过列文伯格-马夸尔特非线性最小二程法(Levenberg-Marquardt nonlinear least squares algorithms)来求解方程[19]。

[0102] 然后，对分解所得的矩阵E的行向量做光滑化处理。在本发明的实施例中，可通过各种光滑方法进行处理。例如，可通过高斯滤波进行光滑处理，对行向量进行加权平均，每一个像素点的值都由其本身和邻域内的其他像素值经过加权平均后得到。还可以通过多项式拟合进行光滑处理。

[0103] 最终可获得得到m个特征点的下列信息：

[0104] 1.未经光滑化的各帧的坐标、所属三角网格，

[0105] 2.光滑化的各帧的坐标，

[0106] 3.特征点开始出现的时刻tin，特征点丢失的时刻tout(如果特征点尚未丢失的话，则记为当前的时刻，如t＝50)。

[0107] 在获得光滑化的各帧的特征点坐标之后，重建单元105进行图像重建。可通过各种方法基于去抖后的特征点坐标进行图像重建。

[0108] 下面结合图4描述根据本发明的一个实施例的保持图像内容的扭转重建。图4示出根据本发明的一个实施例的重建单元105的结构示意图。重建单元105包括划块单元401、坐标计算单元402以及插值单元403。

[0109] 划块单元401将图像划成方形网格。在本发明的一个实施例中，每个小的方形为10×10像素块,再将方形网格划成两个三角网格，如图5所示。图5示出根据本发明的一个实施例将图像划分成网格的示意图。

[0110] 坐标计算单元402利用去抖后的m个特征点求得去抖后的网格顶点{Vi,j}，再利用去抖后的网格顶点{Vi,j}求得这些顶点所构成的三角网内各点的坐标。

[0111] 插值单元403进行插值使得各个坐标为整数。

[0112] 下面结合各个单元详细描述重建图像的具体细节和工作过程。

[0113] 首先划块单元401将图像区域均匀划成n×m,每个网格约为10×10像素块，bVi,j代表网格上的顶点,m个特征点坐标{bPk}。符号bVi,j、bPk代表去抖前的数据，而符号的Vi,j、Pk代表去抖后的数据。经过前面的去抖处理，去抖后的特征点坐标Pk已经确定，但去抖后的网格顶点E＝{Vi,j}未知。

[0114] 每个特征点未必在这些网格的顶点上，现在需要计算出{Pk}所在的网格对应的顶点集合C＝Constraints＝{Vi,j}。一旦集合C上的点都计算出来了，就可以利用五十岚健夫(Takeo Igarashi)方法求出其他的网格顶点的坐标D＝E|C。在得到所有三角网格的坐标以后，利用仿射变换就可以将三角形内所有点的坐标都求出来了。

[0115] 在选取特征点的过程中，可以限定两个特征点间最短的距离，保证每个四边形网格里至多有一个特征点。一旦确定特征点的坐标，即可确定相应的网格的四个顶点坐标，设这些顶点的集合为CV。

[0116] 在本发明的一个实施例中，将N1×N2图片划成n×m像素块,则对于点P＝(x,y),若xN1/n,yN2/m皆为整数，那么点P就是网格上的顶点。

[0117] 设变换后网格的顶点为{Vi,j}，现在我们要对变换后网格做两个限制：1.新网格尽可能保持原来直角三角形网格的刚性——相似性变换项Es；2.新的网格要与控制点尽可能的一致——数据项Ed。

[0118] 因此可归纳为：

[0119]

[0120] 对于图5所示的三角形网格，存在两种三角形：△i,j和△i,j,2，二者两两间隔。

[0121] 保持三角网格的刚性含义如下：

[0122] 在图5所示的三角形ABC中， 逆时针旋转90度后与 同向：

[0123]

[0124] 即，

[0125]

[0126] 故对三角形ABC所引入的刚性限制为：

[0127] min||Vi，j-Vi+1，j+βR(Vi+1，j+1-Vi+1，j)||2  [23]

[0128] 但考虑到每个点(i,j)为6个三角形的公共点，对这几个三角形的刚性限制累加，并引入权值ωi,j、ωi,j,2,则对点Vi,j的刚性限制为：

[0129]

[0130] 强调三个点变化比较明显的三角形，尽可能的保持原来的形状。ωi，j为三角形Vi，jVi+1，jVi+1，j+1所有点的颜色变化，设Vi，j＝(xi，yj)，将三角形Vi，jVi+1，jVi+1，j+1定义为：

[0131] ΔVi，jVi+1，jVi+1，j+1＝：{(xi+I，yj+J)|0≤I≤GridLength，0≤J≤width，J≤βI}  [25][0132] 关于RGB求方差，得到

[0133]

[0134] ωi，j，2为三角形Vi，jVi，j+1Vi+1，j+1所有点的颜色变化。

[0135] ωi，j，2对应的三角形为：

[0136] ΔVi，jVi，j+1Vi+1，j+1＝：{(xi+I，yj+J)|0≤I≤GridLength，0≤J≤GridWidth，J≥βI}  [27][0137] 对Es关于Vi，j＝(ui，j，vi，j)求导得到：

[0138]

[0139]

[0140] 其中

[0141]

[0142] 得到关于ui,j,vi,j的线性方程组：

[0143]

[0144]

[0145] 考虑特征点位置的移动对整个网格的影响，使得特征点周围的点尽可能的与之保持一致的移动，即满足以下方程式：

[0146]

[0147] 其中：

[0148] ·Vk1,Vk2,Vk3为特征点Pk所在的三角网格的顶点；

[0149] ·φk1,φk2,φk3为Pk由上面三个顶点的系数。

[0150] 由图5的网格划分可知，对应的特征点P＝(x,y)可能落于网格ACBD的两个三角形的边上或内部，利用平面向量共面的知识，P可由ABC或ADC的点唯一表出。对任意特征点P，必存在一个三角网格，如ABC满足：P＝φAA+φBB+φCC,其中φA+φB+φC＝1。

[0151] 现在求出这些系数φ。

[0152] 现在对所有网格的顶点(如A＝(Ax,Ay))，设有n×m个网格顶点，开一个二维系数数组φ[n][m]，

[0153] ·初始化皆为0

[0154] ·对包含特征点的网格顶点，则φA可能不为0。

[0155] 下面是对特征点Pk逐点分析，依据图6，Pk＝(pkx,pky)(pkx,pky＝0,1,2,…)若在选取特征点的时候就保证了每个网格至多有一个特征点，那么取

[0156] i＝int pkx/栅格长度,j＝int pky/栅格宽度  [32]

[0157] 则立即可求出图中ABCD四个顶点的坐标，以及其所对应的网格顶点分别为

[0158] A→Vi,j,B→Vi+1,j+1,C→Vi,j+1,D→Vi+1,j

[0159] 下面根据图6，讨论这些系数的求法：

[0160] 取x＝px/栅格长度,y＝py/栅格宽度  [33]

[0161] 设

[0162] 由于在特征点的跟踪阶段返回了每个特征点所在的三角网格，因此存在两种情况：

[0163] 1.参见图6，如果点P∈△ABC，

[0164] 因为

[0165] 并且

[0166] 结果P＝(1-b)A+aB+(b-a)C，

[0167] 即φA＝1-b，φB＝a，φC＝b-a，

[0168] 即

[0169] 由于网络顶点可能被共用，上面的变量带定义为特征点P的局部变量，只与P有关：其中i和j的初值为0，则

[0170]

[0171] 2.参见图6，如果点P∈△ABD，

[0172] 因为

[0173] 并且

[0174] 结果P＝(1-a)A+bB+(a-b)D，

[0175] 即

[0176] 即

[0177] 求解公式[20]的最优解，上面的Es方程仅仅为一部分，考虑到Ed部分项比较少，因此直接在公式[30]的基础上，对其系数进行更新。为了获得更新数据不会产生冲突，对逐个的Pk，依次更新A→B→C→D。

[0178] 为简明起见，设Pk由A,B,C,D四点表出，则对于第t帧，

[0179]

[0180] 其中T＝50，设tin、tout分别为特征点Pk出现与丢失的时刻，如果tout-tin<2T，则[0181]

[0182] 否则

[0183]

[0184] 对Ed关于ui,j,vi,j求导得到：

[0185]

[0186] 因此在公式[30]的基础上，引入图7中的系数，则

[0187]

[0188] 初值皆取为0,对每个特征点并行的更新下面数据：

[0189] 1.另 则

[0190]

[0191]

[0192] 2.另 则

[0193]

[0194]

[0195] 3.另 则

[0196]

[0197]

[0198] 4.另 则

[0199]

[0200]

[0201] 上面的4个hk是独立的。

[0202] 更新了以上系数后，公式[30]可化为：

[0203]

[0204] 利用改进的Jacobi迭代(0≤θ<1),可解上面方程:

[0205]

[0206] 有了各个网格顶点的坐标，下面可以求解网格内点的坐标。

[0207] 图8示出根据本发明的一个实施例的三角形变形保持内部的比例关系的示意图。

[0208] 如图8所示，ABCD的顶点的位置都已经确定了，现在要确定三角形内部以及边界点的位置。由于三角形边界有重合，因此可设：

[0209] ·

[0210] ·

[0211] ·而整个图像的右，上两个边界则另外算。

[0212] 设A(xA，yA)→A′，B(xB，yB)→B′，C(xC，yC)→C′，这些点为已知网格顶点。

[0213] 1.对于Q∈△ABC，设Q(xB+i，yB-j)，则通过以下伪代码计算三角形ABC内所有点：

[0214]

[0215] 其中，Q′，A′，B′，C′代表坐标。

[0216] 2.对于Q∈△ACD，设Q(xD-i，yD+j)，则通过以下伪代码计算三角形ACD内所有点：

[0217]

[0218] 3.对于边界上的点，

[0219] (1)像素点在上边界，如Q∈线BC，设Q(xB+i，yB)

[0220] for(i＝0；i＜xC-xB；i++){

[0221] Q′＝B′+i/GridLength·(C′-B′)

[0222] }

[0223] (2)像素点在在右边界，如Q∈线CD，设Q(xD，yD+j)

[0224] for(j＝0；j＜yC-yD；j++){

[0225] Q′＝D′+j/GridWidth·(C′-D′)

[0226] }

[0227] 完成上面操作后，所得到的点并非整数点，需要进行插值成为整数点，即为所求网格内各点坐标。

[0228] 在本发明的实施例中，在对图像进行重建的过程中，可能会导致图像边缘像素丢失。对于丢失的像素区域，可使用当前图像之前和/或之后的图像中的像素进行回填。在回填丢失的像素区域时，需要将当前图像和用于回填的图像校正到正确的位置，然后将这些图像无缝地融合来生成新的图像。

[0229] 图9示出根据本发明的一个实施例的视频去抖动方法的流程图900。将待处理视频中的F帧图像作为处理对象。在步骤910，从F帧图像中的一帧中选取N个特征点。在步骤920，在其它帧图像中跟踪这N个特征点，从中选取其中m个点存到矩阵M。在步骤930，对矩阵M进行分解M≈W⊙CE。在步骤940，对矩阵E去抖，由此利用M≈W⊙CE,得到m个去抖的特征点。然后，在步骤950，基于去抖的特征点，进行保持图像重建。

[0230] 可以把各实施例提供为可包括其上存储有机器可执行指令的一个或多个机器可读介质的计算机程序产品，这些指令在由诸如计算机、计算机网络或其他电子设备等的一个或多个机器执行时，可以引起一个或多个机器执行根据本发明的各实施例的操作。机器可读介质可以包括但不限于软盘、光盘、CD-ROM(紧致盘只读存储器)和磁光盘、ROM(只读存储器)、RAM(随机存取存储器)、EPROM(可擦除可编程只读存储器)、EEPROM(电可擦除可编程只读存储器)、磁或光卡、闪速存储器或适用于存储机器可执行指令的其他类型的介质/机器可读介质。

[0231] 此外，可以作为计算机程序产品下载各实施例，其中，可以经由通信链路(例如，调制解调器和/或网络连接)由载波或其他传播介质实现和/或调制的一种或多种数据信号把程序从远程计算机(例如，服务器)传输给请求计算机(例如，客户机)。因此，在此所使用的机器可读介质可以包括这样的载波，但对此不作要求。

[0232] 附图和前面的描述给出了各实施例的示例。本领域中的技术人员将明白，所描述的元素中的一种或多个可以很好地组合成单个功能元素。备选地，可以把些元素拆分成多个功能元素。可以把来自一种实施例的元素添加到另一实施例。例如，可以改变在此描述的处理的顺序，且不限于在此描述的方式。此外，不必按所显示的次序实现任何流程图的动作；也不必然需要执行所有动作。而且，不依赖于其他动作的那些动作可以与其他动作并行执行。各实施例的范围决不限于这些特定的示例。无论是否在说明书中明确地给出，诸如材料的结构、尺寸和使用的差异等的众多变更都是可能的。各实施例的范围至少是下列的权利要求所指定的那样宽广。