用于视频编码器中的快速几何模式判定的方法和设备转让专利
申请号 : CN200880019948.4
文献号 : CN101731012A
文献日 : 2010-06-09
发明人 : 简·罗 , 奥斯卡·迪沃拉埃斯科达 , 尹澎 , 陆晓安
申请人 : 汤姆森特许公司
摘要 :
提供了用于视频编码器中的快速几何模式判定的方法和设备。设备包括编码器(100)，用于使用基于几何模型的分区模式来执行非穷尽性几何模式判定。该编码器(100)根据在基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个来跳过基于几何模型的分区模式的测试。
权利要求 :
1.一种设备，包括：
编码器(100)，用于使用基于几何模型的分区模式来执行非穷尽性几何模式判定，其中所述编码器根据在基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个来跳过基于几何模型的分区模式的测试。
2.如权利要求1所述的设备，其中所述非穷尽性几何模式判定使用非几何模式信息、早期停止阈值、相邻信息、残余信息和运动矢量信息中的至少一个。
3.如权利要求2所述的设备，其中所述早期停止阈值对应于量化参数、空间相邻率失真成本和时间相邻率失真成本中的至少一个。
4.一种方法，包括：
使用基于几何模型的分区模式来执行非穷尽性几何模式判定(300，350，500，550，600，650，700，800，1100)，其中所述执行步骤包括：根据在基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，跳过(320，365，515，565，615，665，815，1120)基于几何模型的分区模式的测试。
5.如权利要求4所述的方法，其中所述非穷尽性几何模式判定使用非几何模式信息(315，320，325)、早期停止阈值(920)、相邻信息(415)、残余信息(715)和运动矢量信息(815)中的至少一个。
6.如权利要求5所述的方法，其中所述早期停止阈值对应于量化参数、空间相邻率失真成本和时间相邻率失真成本中的至少一个。
7.一种设备，包括：
编码器(100)，用于使用基于几何模型的分区模式来执行非穷尽性几何参数选择，其中所述编码器通过应用预测性搜索和分级搜索中的至少一个来执行非穷尽性几何参数选择，所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。
8.如权利要求7所述的设备，其中所述初始预测因子选择选择性地使能下列预测因子中的至少一个：基于空间相关性的预测因子、基于时间相关性的预测因子、基于给定编码标准或者给定编码建议书的最佳帧间模式的预测因子、和固定的预测因子网格。
9.一种方法，包括：
使用基于几何模型的分区模式来执行非穷尽性几何参数选择，其中所述执行步骤包括应用预测性搜索和分级搜索(1000)中的至少一个，所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个(900)。
10.如权利要求9所述的方法，其中初始预测因子选择选择性地使能下列预测因子中的至少一个：基于空间相关性的预测因子、基于时间相关性的预测因子、基于给定编码标准或者给定编码建议书的最佳帧间模式的预测因子(915)、和固定的预测因子网格(925)。
11.一种方法，包括：
使用基于几何模型的分区模式，对图像的视频信号数据进行编码，其中所述编码步骤使用用于图像的至少一部分的几何分区参数和预测数据的替换优化来编码所述视频信号数据(1200)。
说明书 :
技术领域
本原理一般涉及视频编码，更具体地，涉及用于视频编码器中的快速几何模式判定(fast geometric mode decision)的方法和设备。
背景技术
在国际标准化组织/国际电工委员会(ISO/IEC)运动图像专家组-4(MPEG-4)第10部分高级视频编码(AVC)标准/国际电信联盟电信标准化部(ITU-T)H.264建议书(下文中称作“MPEG-4 AVC标准”)中，帧间编码(inter-coded)的16×16像素宏块可被拆分为大小为16×8、8×16或8×8的宏块分区(partition)。8×8像素的宏块分区也已知为子宏块。子宏块可被进一步拆分为大小为8×4、4×8和4×4的子宏块分区。编码器可以基于特定宏块的特性来选择如何将宏块划分为分区和子宏块分区，以便最大化压缩效率和主体(subjective)质量。
而且，MPEG-4 AVC标准也支持INTRA(帧内)模式、SKIP(跳跃)模式和DIRECT(直接)模式。帧内模式允许三种类型：INTRA4×4、INTRA16×16和INTRA8×8，该INTRA8×8仅是保真度范围扩展(fidelity rangeextension)模式。INTRA4×4和INTRA8×8支持9种预测模式：垂直预测；水平预测；DC预测，对角向下/向左预测；对焦向下/向右预测；垂直-向左预测；水平-向下预测；垂直-向右预测；和水平向上预测。INTRA16×16支持4种预测模式：垂直预测；水平预测；DC预测；和平面预测。
对于模式判定，帧内画面应当支持帧内模式，而帧间画面应当支持帧间模式和帧内模式。帧内模式包括INTRA4×4和INTRA16×16。对于P画面，帧间模式包括SKIP以及16×16、16×8、8×16和子宏块8×8分区。8×8进一步支持8×8、8×4、4×8和4×4分区。对于B画面，考虑列表0和列表1两者，并且对于宏块和子宏块两者也考虑DIRECT(直接)模式。
现有技术中，率失真优化(RDO，rate-distortion optimization)架构被用于模式判定，即，RDcost J＝D+λR被用来测量编码成本，其中D表示失真，并且R表示比率。对于帧间模式，从模式判定中单独地考虑运动估计。首先对于帧间模式的所有块类型执行运动估计，然后通过比较每个帧间模式和帧内模式的成本来进行模式判定。选择具有最小成本的模式作为最佳模式。
下面概述对P-画面或B-画面中的一个宏块s进行编码的传统过程(下文中称作“传统宏块编码过程”)。
在传统宏块编码过程的第一步骤中，给定最后编码的画面，我们判定拉格朗日乘数λMODE、λMOTION、以及宏块量化器QP。
在传统宏块编码过程的第二步骤中，对于每个参考画面和可能宏块模式的运动矢量，通过最小化
J(REF，m(REF)|λMOTION)＝SA(T)D(s，c(REF，m(REF)))λMOTION+(R(m(REF)-p(REF))+R(REF))
来执行运动估计和参考画面选择。在前面的公式中，J表示率失真成本，REF表示参考画面，m表示正考虑的当前运动矢量，λMOTION表示拉格朗日乘数，c(REF，m(REF))表示使用具有运动矢量m的参考REF的补偿操作，p表示在运动矢量编码期间用于预测的运动矢量，R(m-p)表示用于对运动矢量进行编码的比特，以及R(REF)表示用于对参考画面进行编码的比特。SAD表示原始信号与通过运动矢量预测的参考信号之间的绝对差之和。
在传统宏块编码过程的第三步骤中，当改变MODE(模式)时，给定QP和λMODE，通过最小化
J(s，c，MODE|QP，λMODE)＝SSD(s，c，MODE|QP)+λMODE·R(s，c，MODE|QP)，
来选择宏块预测模式。SSD表示原始信号与重构信号之间的平方差的和。R(s，c，MODE)表示与选择MODE(模式)相关联的比特的数目，包括用于宏块标首、运动和所有DCT系数的比特。MODE(模式)指明来自潜在宏块模式集合的模式，具体如下：
P-帧：
B-帧：
INTRA4×4包括模式：
INTRA16×16/INTRA8×8包括模式：
MODE∈{垂直，水平，DC，平面}
帧分区是有效视频编码中很重要的一个处理。诸如MPEG-4 AVC标准之类的最新视频压缩技术使用基于树的帧分区。这种技术似乎比简单的均匀块分区更有效，该均匀块分区通常用于较老的视频编码标准以及诸如国际标准化组织/国际电工委员会(ISO/IEC)运动图像专家组-2(MPEG-2)标准和国际电信联盟电信部门(ITU-T)H.263建议书(下文中称作“H.263建议书”)之类的标准。然而，基于树的帧分区仍旧无法尽可能有效地编码视频信息，因为它不能有效地捕获二维(2D)数据的几何结构。
使用几何区域分区的帧间和帧内预测在提高视频编码效率方面已经被认为是很有前途的研究方向。先前，对于(例如根据MPEG-4 AVC标准执行的)高级视频编码，已经建议对于帧间和帧内预测引入几何分区，以便提高视频编码效率。为了得到最佳性能，对于编码器来说发现最佳的几何分区是至关重要的。在这些建议中使用了强大的全面搜索策略，但是复杂度非常高。然而，对于模式/分区选择可期望拥有某些快速算法，从而用于几何分区的增加的计算复杂度不会变成实际系统的阻碍。
以前的建议是基于边缘检测开发的快速算法，以便为帧间几何模式预先选择候选分区线。这种快速算法基于以下假设：对于沿着对象边界散落的块，期望用于运动补偿的几何分区更好地工作。达到某种程度，合理地假设基于图像边缘的预选择分区可以实现令人满意的结果。这种方式的主要缺点在于它是通过非常简单的统计和专设(ad hoc)建模来完全驱动的。这导致实际上仅考虑其中几何分区是有用的一部分可能情形，因此在复杂度节省和压缩节省方面实现次佳结果。实际上，这种快速算法的发起人假设分区仅与显性(explicit)图像边缘相关。然而，这不一定为真。例如，对于帧间预测情况，分区反映运动边界而不是图像边缘。在一些情况下，图像边缘可以与运动边界一致，但不是在所有情况中。因此，与完全搜索算法相比，这种快速算法在编码效率上可能导致重大降低。
而且，MPEG-4 AVC标准也支持INTRA(帧内)模式、SKIP(跳跃)模式和DIRECT(直接)模式。帧内模式允许三种类型：INTRA4×4、INTRA16×16和INTRA8×8，该INTRA8×8仅是保真度范围扩展(fidelity rangeextension)模式。INTRA4×4和INTRA8×8支持9种预测模式：垂直预测；水平预测；DC预测，对角向下/向左预测；对焦向下/向右预测；垂直-向左预测；水平-向下预测；垂直-向右预测；和水平向上预测。INTRA16×16支持4种预测模式：垂直预测；水平预测；DC预测；和平面预测。
对于模式判定，帧内画面应当支持帧内模式，而帧间画面应当支持帧间模式和帧内模式。帧内模式包括INTRA4×4和INTRA16×16。对于P画面，帧间模式包括SKIP以及16×16、16×8、8×16和子宏块8×8分区。8×8进一步支持8×8、8×4、4×8和4×4分区。对于B画面，考虑列表0和列表1两者，并且对于宏块和子宏块两者也考虑DIRECT(直接)模式。
现有技术中，率失真优化(RDO，rate-distortion optimization)架构被用于模式判定，即，RDcost J＝D+λR被用来测量编码成本，其中D表示失真，并且R表示比率。对于帧间模式，从模式判定中单独地考虑运动估计。首先对于帧间模式的所有块类型执行运动估计，然后通过比较每个帧间模式和帧内模式的成本来进行模式判定。选择具有最小成本的模式作为最佳模式。
下面概述对P-画面或B-画面中的一个宏块s进行编码的传统过程(下文中称作“传统宏块编码过程”)。
在传统宏块编码过程的第一步骤中，给定最后编码的画面，我们判定拉格朗日乘数λMODE、λMOTION、以及宏块量化器QP。
在传统宏块编码过程的第二步骤中，对于每个参考画面和可能宏块模式的运动矢量，通过最小化
J(REF，m(REF)|λMOTION)＝SA(T)D(s，c(REF，m(REF)))λMOTION+(R(m(REF)-p(REF))+R(REF))
来执行运动估计和参考画面选择。在前面的公式中，J表示率失真成本，REF表示参考画面，m表示正考虑的当前运动矢量，λMOTION表示拉格朗日乘数，c(REF，m(REF))表示使用具有运动矢量m的参考REF的补偿操作，p表示在运动矢量编码期间用于预测的运动矢量，R(m-p)表示用于对运动矢量进行编码的比特，以及R(REF)表示用于对参考画面进行编码的比特。SAD表示原始信号与通过运动矢量预测的参考信号之间的绝对差之和。
在传统宏块编码过程的第三步骤中，当改变MODE(模式)时，给定QP和λMODE，通过最小化
J(s，c，MODE|QP，λMODE)＝SSD(s，c，MODE|QP)+λMODE·R(s，c，MODE|QP)，
来选择宏块预测模式。SSD表示原始信号与重构信号之间的平方差的和。R(s，c，MODE)表示与选择MODE(模式)相关联的比特的数目，包括用于宏块标首、运动和所有DCT系数的比特。MODE(模式)指明来自潜在宏块模式集合的模式，具体如下：
P-帧：
B-帧：
INTRA4×4包括模式：
INTRA16×16/INTRA8×8包括模式：
MODE∈{垂直，水平，DC，平面}
帧分区是有效视频编码中很重要的一个处理。诸如MPEG-4 AVC标准之类的最新视频压缩技术使用基于树的帧分区。这种技术似乎比简单的均匀块分区更有效，该均匀块分区通常用于较老的视频编码标准以及诸如国际标准化组织/国际电工委员会(ISO/IEC)运动图像专家组-2(MPEG-2)标准和国际电信联盟电信部门(ITU-T)H.263建议书(下文中称作“H.263建议书”)之类的标准。然而，基于树的帧分区仍旧无法尽可能有效地编码视频信息，因为它不能有效地捕获二维(2D)数据的几何结构。
使用几何区域分区的帧间和帧内预测在提高视频编码效率方面已经被认为是很有前途的研究方向。先前，对于(例如根据MPEG-4 AVC标准执行的)高级视频编码，已经建议对于帧间和帧内预测引入几何分区，以便提高视频编码效率。为了得到最佳性能，对于编码器来说发现最佳的几何分区是至关重要的。在这些建议中使用了强大的全面搜索策略，但是复杂度非常高。然而，对于模式/分区选择可期望拥有某些快速算法，从而用于几何分区的增加的计算复杂度不会变成实际系统的阻碍。
以前的建议是基于边缘检测开发的快速算法，以便为帧间几何模式预先选择候选分区线。这种快速算法基于以下假设：对于沿着对象边界散落的块，期望用于运动补偿的几何分区更好地工作。达到某种程度，合理地假设基于图像边缘的预选择分区可以实现令人满意的结果。这种方式的主要缺点在于它是通过非常简单的统计和专设(ad hoc)建模来完全驱动的。这导致实际上仅考虑其中几何分区是有用的一部分可能情形，因此在复杂度节省和压缩节省方面实现次佳结果。实际上，这种快速算法的发起人假设分区仅与显性(explicit)图像边缘相关。然而，这不一定为真。例如，对于帧间预测情况，分区反映运动边界而不是图像边缘。在一些情况下，图像边缘可以与运动边界一致，但不是在所有情况中。因此，与完全搜索算法相比，这种快速算法在编码效率上可能导致重大降低。
发明内容
本原理解决了现有技术的这些和其它缺陷和不足，本原理致力于用于视频编码器中的快速几何模式判定的方法和设备。
根据本原理的一方面，提供了一种设备。该设备包括编码器，用于使用基于几何模型的分区模式来执行非穷尽性几何模式判定。根据基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，所述编码器跳过基于几何模型的分区模式的测试。
根据本原理的另一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式来执行非穷尽性几何模式判定。所述执行步骤包括：根据基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，跳过基于几何模型的分区模式的测试。
根据本原理的再一方面，提供了一种设备。所述设备包括编码器，用于使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述编码器通过应用预测性搜索和分级搜索中的至少一个来执行非穷尽性几何参数选择。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化(refinement)中的至少一个。
根据本原理的又一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述执行步骤包括应用预测性搜索和分级搜索中的至少一个。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。
根据本原理的再一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式对图像的视频信号数据进行编码。所述编码步骤使用图像的至少一部分的几何分区参数和预测数据的替换优化来编码所述视频信号数据。
根据结合附图要阅读的示例性实施例的下列详细描述，本原理的这些和其它方面、特征和优点将变得明显。
根据本原理的一方面，提供了一种设备。该设备包括编码器，用于使用基于几何模型的分区模式来执行非穷尽性几何模式判定。根据基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，所述编码器跳过基于几何模型的分区模式的测试。
根据本原理的另一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式来执行非穷尽性几何模式判定。所述执行步骤包括：根据基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，跳过基于几何模型的分区模式的测试。
根据本原理的再一方面，提供了一种设备。所述设备包括编码器，用于使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述编码器通过应用预测性搜索和分级搜索中的至少一个来执行非穷尽性几何参数选择。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化(refinement)中的至少一个。
根据本原理的又一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述执行步骤包括应用预测性搜索和分级搜索中的至少一个。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。
根据本原理的再一方面，提供了一种方法。所述方法包括使用基于几何模型的分区模式对图像的视频信号数据进行编码。所述编码步骤使用图像的至少一部分的几何分区参数和预测数据的替换优化来编码所述视频信号数据。
根据结合附图要阅读的示例性实施例的下列详细描述，本原理的这些和其它方面、特征和优点将变得明显。
附图说明
根据下列示例性附图，可以更好地理解本原理，其中：
图1是根据本原理实施例的、能够根据被扩展用于本原理的MPEG-4 AVC标准来执行视频编码的视频编码器的框图；
图2是根据本原理实施例的、两个分区之间的示例性几何边界的图；
图3A和图3B是根据本原理实施例的、基于MPEG-4 AVC标准模式信息的快速几何模式判定的示例性方法的流程图；
图4是根据本原理实施例的、基于相邻信息的快速几何模式判定的示例性方法的流程图；
图5A是根据本原理实施例的、用于16×16几何模式的模式判定的示例性方法的流程图；
图5B是根据本原理实施例的、用于8×8几何模式的模式判定的示例性方法的流程图；
图6A是根据本原理实施例的、用于16×16几何模式的模式判定的示例性方法的流程图；
图6B是根据本原理实施例的、用于8×8几何模式的模式判定的示例性方法的流程图；
图7是根据本原理实施例的、基于残余信息的快速几何模式判定的示例性方法的流程图；
图8是根据本原理实施例的、基于运动矢量信息的快速模式判定的示例性方法的流程图；
图9是根据本原理实施例的、用于快速预测性几何分区选择的示例性方法的流程图；
图10是根据本原理实施例的、用于使用分级搜索的快速几何分区选择的示例性方法的流程图；
图11是根据本原理实施例的、用于快速几何模式和分区选择的示例性方法的流程图；和
图12是根据本原理实施例的、用于快速替换预测/分区参数优化的示例性方法的流程图。
图1是根据本原理实施例的、能够根据被扩展用于本原理的MPEG-4 AVC标准来执行视频编码的视频编码器的框图；
图2是根据本原理实施例的、两个分区之间的示例性几何边界的图；
图3A和图3B是根据本原理实施例的、基于MPEG-4 AVC标准模式信息的快速几何模式判定的示例性方法的流程图；
图4是根据本原理实施例的、基于相邻信息的快速几何模式判定的示例性方法的流程图；
图5A是根据本原理实施例的、用于16×16几何模式的模式判定的示例性方法的流程图；
图5B是根据本原理实施例的、用于8×8几何模式的模式判定的示例性方法的流程图；
图6A是根据本原理实施例的、用于16×16几何模式的模式判定的示例性方法的流程图；
图6B是根据本原理实施例的、用于8×8几何模式的模式判定的示例性方法的流程图；
图7是根据本原理实施例的、基于残余信息的快速几何模式判定的示例性方法的流程图；
图8是根据本原理实施例的、基于运动矢量信息的快速模式判定的示例性方法的流程图；
图9是根据本原理实施例的、用于快速预测性几何分区选择的示例性方法的流程图；
图10是根据本原理实施例的、用于使用分级搜索的快速几何分区选择的示例性方法的流程图；
图11是根据本原理实施例的、用于快速几何模式和分区选择的示例性方法的流程图；和
图12是根据本原理实施例的、用于快速替换预测/分区参数优化的示例性方法的流程图。
具体实施方式
本发明致力于用于视频编码器中的快速几何模式判定的方法和设备。
本说明书图解说明了本原理。因此将会理解到，本领域的技术人员将能够设计出体现本原理并且被包含在其精神和范畴之内的各种安排，尽管各种安排未在此处明确地描述或示出)。
此处叙述的所有示例和条件性语言是为了教学目的，以辅助读者理解发明人对现有技术进一步贡献的本原理和构思，并且应当被理解为不限于如此具体叙述的示例和条件。
而且，此处叙述原理、方面和本原理的实施例的所有陈述、以及其特定示例意欲涵盖其结构性和功能性的等同物。另外，意欲所述等同物包括当前已知的等同物以及将来研发的等同物，即，被开发用于执行相同功能的任何元件，而不管结构如何。
因此，例如，本领域的普通技术人员将会理解，这里展现的框图代表体现本原理的图解性电路的概念图。类似地，将会理解，任何流程图、流向图、状态转换图、伪代码等代表可以基本在计算机可读媒体上表现并且因此由计算机或处理器执行的各种处理，无论是否明确地地示出了这样的计算机或处理器。
附图中示出的各种元件的功能可以通过使用专用硬件和能够与适当的软件联合执行软件的硬件来提供。当功能被处理器提供时，可以通过单个专用处理器、单个共享处理器或者多个单独的处理器(可以共享其中的一些处理器)来提供所述功能。而且，术语“处理器”或“控制器”的明确使用不应当被曲解为排他地指能够执行软件的硬件，而是可以隐性地包括(而非限制性地)数字信号处理器(“DSP”)硬件、用于存储软件的只读存储器(“ROM”)、随机存取存储器(“RAM”)和非易失性存储器。
还可以包括其它硬件，常规的硬件和/或定制的硬件。类似地，附图中所示的任意开关仅仅是概念性的。它们的功能可以通过程序逻辑的操作、通过专用逻辑、通过编程控制和专用逻辑的交互作用、或者甚至手动来执行，从上下文中可以更具体地理解，实施者可以选择特定的技术。
在于此的权利要求书中，被表述为用于执行具体功能的部件的任意元件意欲涵盖执行该功能的任意方式，包括例如，a)执行该功能的电路元件的组合，或者b)任意形式的软件，因此包括固件、微代码等，它们被与用于执行该软件的适当电路相结合以执行该功能。由所述权利要求限定的本原理蕴含的事实是：各种所记载的手段提供的功能性被组合并且以权利要求请求的方式结合在一起。因此，认为是，可以提供那些功能性的任意手段等同于此处所示的那些手段。
说明书中对本原理的“一个实施例”或者“实施例”的引用是指在本原理的至少一个实施例中包含了结合该实施例描述的特别特征、结构、特性等等。因此，在贯穿说明书的各个位置出现的短语“在一个实施例中”或者“在实施例中”不必都是指向相同的实施例。
将会理解，术语“和/或”的使用(例如，在“A和/或B”的情况下)意欲涵盖第一所列选项的选择(A)、第二所列选项的选择(B)、或者两个选项的选择(A和B)。作为另一个示例，在“A、B和/或C”的情况下，这样的措辞意欲涵盖第一所列选项的选择(A)、第二所列选项的选择(B)、第三所列选项的选择(C)、第一和第二所列选项的选择(A和B)、第一和第三所列选项的选择(A和C)、第二和第三所列选项的选择(B和C)、或者所有三个选项的选择(A、B和C)。如本领域和相关领域中的普通技术人员容易明白的是，对于许多所列的项来说，这可以进行扩展。
而且，将会理解，尽管此处参考MPEG-4 AVC标准描述了本原理的一个或多个实施例，但是本原理并不单单限于该标准，因此本原理可以结合其它视频编码标准、建议书及其扩展来利用，包括MPEG-4 AVC标准的扩展，同时维持本原理的精神。
而且，如此处所使用的，短语“楔形分区(wedge partition)”和“楔形分区(wedge partitioning)”是指图像块被分区为两个区域，这两个区域被任意线或曲线分离。而且，词语“楔形”是指给定边界线或曲线的特定设置和/或选择的分区形状。
而且，如此处所使用的，例如，关于搜索，术语“快速”是指能够找到最佳解决方案或接近最佳的解决方案、但是比密集的(intensive)完全搜索算法具有较低计算复杂度的有效算法。
转向图1，能够根据(被扩展用于本原理的)MPEG-4 AVC标准执行视频编码的视频编码器一般用附图标记100来表示。
视频编码器100包括帧排序缓冲器110，其具有与组合器185的非反相输入进行信号通信的输出。组合器185的输出与具有几何扩展的变换器和量化器125的第一输入进行信号通信连接。具有几何扩展的变换器和量化器125的输出与具有几何扩展的熵编码器145的第一输入以及具有几何扩展的逆变换器和逆量化器150的第一输入进行信号通信连接。具有几何扩展的熵编码器145的输出与组合器190的第一非反相输入进行信号通信连接。组合器190的输出与输出缓冲器135的第一输入进行信号通信连接。
具有几何扩展的编码器控制器105的第一输出与帧排序缓冲器110的第二输入、具有几何扩展的逆变换器和逆量化器150的第二输入、画面类型判定模块115的输入、具有几何扩展的宏块类型(MB类型)判定模块120的输入、具有几何扩展的帧内预测模块160的第二输入、具有几何扩展的解块滤波器165的第二输入、具有几何扩展的运动补偿器170的第一输入、具有几何扩展的快速运动估计器175的第一输入、和参考画面缓冲器180的第二输入进行信号通信连接。
具有几何扩展的编码器控制器105的第二输出与补充增强信息(SEI)插入器130的第一输入、具有几何扩展的变换器和量化器125的第二输入、具有几何扩展的熵编码器145的第二输入、输出缓冲器135的第二输入、以及序列参数集(SPS)和画面参数集(PPS)插入器140的输入进行信号通信连接。
画面类型判定模块115的第一输出与帧排序缓冲器110的第三输入进行信号通信连接。画面类型判定模块115的第二输出与具有几何扩展的宏块类型判定模块120的第二输入进行信号通信连接。
序列参数集(SPS)和画面参数集(PPS)插入器140的输出与组合器190的第三非反相输入进行信号通信连接。
具有几何扩展的逆量化和逆变换器150的输出与组合器127的第一非反相输入进行信号通信连接。组合器127的输出与具有几何扩展的帧内预测模块160的第一输入和具有几何扩展的解块滤波器165的第一输入进行信号通信连接。具有几何扩展的解块滤波器165的输出与参考画面缓冲器180的第一输入进行信号通信连接。参考画面缓冲器180的输出与具有几何扩展175的快速运动估计器的第二输入进行信号通信连接。具有几何扩展的快速运动估计器175的第一输出与具有几何扩展的运动补偿器170的第二输出进行信号通信连接。具有几何扩展的快速运动估计器175的第二输出与具有几何扩展的熵编码器145的第三输出进行信号通信连接。
具有几何扩展的运动补偿器170的输出与开关197的第一输入进行信号通信连接。具有几何扩展的帧内预测模块160的输出与开关197的第二输入进行信号通信连接。具有几何扩展的宏块类型判定模块120的输出与开关197的第三输入进行信号通信连接。开关197的输出与组合器127的第二非反相输入进行信号通信连接。
帧排序缓冲器110和具有几何扩展的编码器控制器105的输入可用作编码器100的输入，用于接收输入画面101。而且，补充增强信息(SEI)插入器130的输入可用作编码器100的输入，用于接收元数据。输出缓冲器135的输出可用作编码器100的输出，用于输出比特流。
使用几何区域分区的帧间预测和帧内预测已经被认为是在提高视频编码效率方面具有前途的研究方向。以前，对于(例如根据MPEG-4 AVC标准执行的)高级视频编码，已经建议引入针对帧间和帧内预测的几何分区，以便提高视频编码效率。为了获得最佳性能，对于编码器来说发现最佳的几何分区是至关重要的。在这些建议中使用了强大的全面搜索策略，但是复杂度非常高。然而，对于模式/分区选择可期望拥有某些快速算法，从而增加的几何分区的计算复杂度不会变成实际系统的阻碍。因此，根据本原理，我们已经构思快速几何算法来节省编码器处的计算性资源。在本原理的一个实施例中，使用基于几何模型的分区模式，对视频编码器使能快速几何模式判定，其中基于标准预测模式与几何分区模式之间的相关性和依赖性中的至少一个来跳过测试几何模式。在本原理的另一个实施例中，使用基于几何模型的分区模式使能对于视频编码器的快速几何参数选择，其中预测性快速搜索算法被应用，包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。在本原理的又一个实施例中，使用基于几何模型的分区模式使能对于视频编码器的快速几何参数选择，其中使用分级搜索。在本原理的又一个实施例中，使能使用基于几何模型的分区模式的视频编码器，其中使用了几何分区和预测数据的交替优化。
如上注意的，最新的视频压缩技术使用帧分区，它比老的视频编码标准中通常使用的简单的均匀块分区更有效，所述老的视频编码标准诸如国际标准化组织/国际电工委员会(ISO/IEC)运动图像专家组-2(MPEG-2)标准。然而，MPEG-4 AVC标准中使用的基于树的帧分区仍旧不能对视频信息足够有效地编码，因为它不能捕获二维(2D)数据的几何结构。为了解决这样的局限，展示了一种通过考虑2D视频数据的2D几何来更好地表示和编码2D视频数据的方法和设备。在一个实施例中，关于针对帧间(INTER16×16GEO、INTER8×8GEO)和帧内预测(INTRA16×16GEO、INTRA8×8GEO)两者的新模式集合，我们使用楔形分区(即，将一个块分区为两个区域，该两个区域由任意线或曲线分离)。
在一个实施例中，可以使用MPEG-4 AVC标准作为基础来合并几何分区模式。块内的几何分区通过线的隐式公式来建模。因此，在一实施例中，分区被定义如下(如图2中所示)：
f(x，y)＝xcosθ+ysinθ-ρ，
其中，ρ、θ分别表示以下：在边界线f(x，y)的正交方向上从原点到边界线f(x，y)的距离；和f(x，y)的正交方向与水平坐标轴x的角度。
转向图2，图像的示例性几何分区一般用附图标记200指明。图像块一般用附图标记220指明。
从它的公式中直接得出：也考虑了具有更高阶几何参数的针对f(x，y)的更相关的模型。
每个块像素(x，y)被分类，从而：
对于编码目的，先验定义了可能分区(或者几何模式)的字典库(dictioanry)。这可用公式定义如下：
和
以及
和
其中，Δρ和Δθ是所选择的量化(参数分辨率)步辐。θ和ρ的量化的索引是所传送的用于对边缘进行编码的信息。然而，如果在编码过程中使用模式16×8和8×16，则对于ρ＝0的情况，可以从可能边缘的集合中去除角度0和90。
在几何自适应运动补偿模式中，执行对每个分区的ρ、θ和运动矢量的搜索，以便发现最佳配置。对于每对ρ和θ，在两个阶段中进行完全搜索策略，其中搜索最佳运动矢量。在几何自适应帧内预测模式内，执行对于每个分区的ρ、θ和最佳预测因子(方向性预测或统计，等等)的搜索，以便发现最佳配置。
在编码器方，如果使用完全搜索，则几何模式的计算性复杂度可能非常高。因此，开发快速算法来减少实际应用中的编码器复杂度是相当重要的。
在一实施例中，我们使用MPEG-4 AVC标准和P画面的帧间几何分区的架构。然而，将会理解，给出此处提供的本原理的示教，本领域和相关领域中的普通技术人员可容易地将本原理的其它实施例应用于帧内几何分区、其它类型的画面和其它视频编码标准和建议书、及其扩展，同时维持本原理的精神。本原理可以与快速运动估计和/或MPEG-4 AVC快速模式判定联合地应用。对于编码成本测量，我们使用RDcost作为一个示例。然而，将会理解，本原理不仅仅限于在前类型的编码成本测量，因此可以应用其它的编码成本测量，包括但不限于仅失真测量(例如均方差等)等等，同时维持本原理的精神。
为了图示和清楚目的，本原理被分类为以下三个类别：(1)基于原始MPEG-4 AVC标准帧间预测模式与几何分区模式之间的相关性的快速模式判定；(2)几何分区模式内的快速几何分区选择；(3)通过几何分区和预测日期的交替优化的快速几何分区选择。将会理解，可以联合地或者独立地应用这些类别。
1.基于原始MPEG-4 AVC标准帧间预测模式与几何分区模式之间的相关性的快速模式判定。
在这个类别中，执行快速算法以便判定我们是否能够完整地跳过测试几何模式。我们将假设MPEG-4 AVC标准帧间预测模式在几何分区模式之前被编码器测试。我们将进一步把第一类别下的我们的算法分类为下列5个子类别：(1)MPEG-4 AVC标准模式判定；(2)早期停止判定；(3)相邻判定；(4)残余判定；和(5)运动矢量判定。可以联合地或者独立地应用这些子类别。
1.1 MPEG-4 AVC标准模式判定
在这个子类别中，我们基于由编码器选择的最佳和/或次佳(如果可得到)的MPEG-4 AVC标准模型来判定是否跳过测试几何模式的压缩性能。在一实施例中，这一类别的判定是基于以下假设：例如，如果编码器选择几何模式作为宏块的最佳模式，则最佳MPEG-4 AVC标准帧间预测模式不可能是SKIP、16×16或者帧内模式。同时，在子8×8级别处，如果最佳子宏块模式是8×8几何模式，则人们可以假设最佳MPEG-4 AVC标准子宏块模式不可能是8×8(或者，如果考虑帧间-B预测，则不可能是Direct 8×8)。在宏块大小级别，这是因为SKIP和/或16×16意味着宏块很可能在相同对象或运动区域内，并且帧内意味着宏块很可能是被阻塞的(occluded)对象。这同样应用于子宏块。在一个实施例中，我们首先检查最佳MPEG-4 AVC标准模式是否是SKIP模式。如果是这种情况，则编码器跳过测试几何模式，从而避免了边缘和运动搜索。如果SKIP不是由编码器选择的最佳模式，则编码器检查最佳MPEG-4 AVC标准模式是否是帧内模式。如果是这种情况，则跳过几何模式。否则，编码器检查最佳MPEG-4 AVC标准模式是否是16×16。如果是这种情况，则编码器检查次佳MPEG-4 AVC标准模式。如果它是SKIP模式，则我们进一步跳过测试几何模式。否则，我们测试几何模式。类似地，对于子宏块，如果最佳MPEG-4 AVC标准子宏块模式是8×8分区大小，则编码器跳过测试几何子宏块模式。
转向图5A，用于16×16几何模式的模式判定的示例性方法一般用附图标记500来指明。
方法500包括开始块505，在开始块505，将控制传递到判定块510。判定块510确定是否J最佳16×16模式＜T最佳16×16模式。如果是，则将控制传递到功能块515。否则，将控制传递到功能块520。
功能块515跳跃到下一宏块，并且将控制传递到结束块549。
功能块520计算J16×16GEO，并且将控制传递到结束块549。
转向图5B，用于8×8几何模式的模式判定的示例性方法一般用附图标记550来指明。
方法550包括开始块555，在开始块555将控制传递到判定块560。判定块560确定是否J最佳8×8模式＜T最佳8×8模式，其中T代表阈值。如果是，则将控制传递到功能块565。否则，将控制传递到功能块570。
功能块516跳跃到下一宏块，并且将控制传递到结束块599。
功能块570计算J8×8GEO，并且将控制传递到结束块599。
将会理解，给出此处提供的本原理的示教，此处提供的示例易于被本领域和相关领域中的普通技术人员扩展到最佳模式的其它组合。而且，将会理解，考虑用来预测的最大数目的条目不限于MPEG-4 AVC标准预测模式当中的最佳和次佳被选的模式，并且因此，也可以利用其它数目的最佳被选的模式，同时维持本原理的精神。
1.2早期停止判定
在这个子类别中，我们建议使用早期停止准则来达到快速模式判定。这些停止准则都基于自适应阈值机制。该阈值可以是量化参数、空间/时间相邻率失真成本(RDcost)等等的函数。基本方案是在测试所有可能的MPEG-4AVC标准宏块/子宏块分区模式之后应用阈值，以便判定是否跳过测试16×16和/或8×8几何分区模式。在一个实施例中，我们在应用16×16/8×8几何分区判定之前仅测试最佳MPEG-4 AVC标准模式。如果最佳MPEG-4 AVC标准模式的RDcost小于某一阈值，则我们跳过测试几何模式。否则，我们测试几何模式。
可以基于一些安全保护或从RDcost收集的统计来选择快速几何模式判定阈值。
转向图3A和图3B，基于MPEG-4 AVC标准模式信息的快速几何模式判定的示例性方法通常分别用附图标记300和350来指明。
方法300包括开始块305，在开始块305将控制传递到功能块310。功能块310检查最佳MPEG-4 AVC标准模式，并且将控制传递到判定块315。判定块315确定最佳MPEG-4 AVC标准模式是否是SKIP(跳过)或帧内。如果是，则将控制传递到判定块320。否则，将控制传递到功能块335。
判定块320确定最佳MPEG-4 AVC标准模式是否是16×16。如果是，则将控制传递到判定块325。否则，将控制传递到功能块330。
判定块325确定次佳MPEG-4 AVC标准模式是否是SKIP(跳过)。如果是，则将控制传递到功能块335。否则，将控制传递到功能块330。
功能块330检查几何模式，并且将控制传递到功能块335。
功能块335选择最佳模式，并且将控制传递到结束块349。
方法350包括开始块355，在开始块355将控制传递到功能块360。功能块360检查最佳MPEG-4 AVC标准子宏块模式，并且将控制传递到判定块365。判定块365确定最佳MPEG-4 AVC标准模式是否为8×8。如果是，则将控制传递到功能块375。否则，将控制传递到功能块370。
功能块370检查子宏块几何模式，并且将控制传递到功能块375。
功能块375选择最佳子宏块模块，并且将控制传递到结束块399。
在另一实施例中，在16×16/8×8几何分区判定之前，我们使用来自最佳和次佳MPEG-4 AVC标准模式的统计数字(如果可得到)。如果最佳MPEG-4 AVC标准模式的RDcost小于某一阈值，并且次佳MPEG-4 AVC标准模式的RDcost小于另一阈值，则我们跳过测试几何模式。否则，我们测试几何模式。
转向图4，基于相邻信息的快速几何模式判定的示例性方法一般用附图标记400来指明。
方法400包括开始块405，开始块405将控制传递到功能块410。功能块410检查上部和左部宏块模式判定，并且将控制传递到判定块415。判定块415确定模式判定是否为SKIP(跳过)或者16×16。如果是，则将控制传递到功能块425。否则，将控制传递到功能块420。
功能块420检查几何模式，并且将控制传递到功能块425。
如果几何模式被检查，则功能块425选择几何模式和来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则，功能块425选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块499。
在另一个实施例中，可以考虑第一类别的第一和第二子类别的途径之间的组合，其中使用关于阈值成本准则和最佳被选的模式准则的组合。另一个可能的途径是使用最佳模式和次佳模式作为阈值适应的条件性环境。根据最佳和次佳MPEG-4 AVC标准模式的组合，可以设置用于跳过或者不测试几何模式的判定阈值。
1.3相邻判定
MPEG-4 AVC标准使用块编码结构。通常，对象趋向于穿过块边界。在这个子类别中，我们将使用相邻信息来使得模式判定更快速。
如果空间和/或时间相邻宏块都不包括对给定的一个或多个宏块(例如16×8，8×16，8×8，8×4)(或者子块)进行分区的模式，则当前宏块(或者子块)的最佳模式成为几何模式的可能性较低。在一个实施例中，编码器检查左部和上部相邻宏块，如果它们都是SKIP(跳过)或16×16，则编码器跳过测试当前宏块中的几何模式。否则，测试几何模式。在另一个实施例中，考虑相邻物和当前最佳MPEG-4 AVC标准模式的组合判定规则被考虑。
转向图6A，用于16×16几何模式的模式判定的示例性方法一般用附图标记600来指明。
方法600包括开始块605，在开始块605将控制传递到判定块610。判定块610确定是否J最佳，次佳16×16模式＜T最佳，次佳16×16模式，其中T是阈值。如果是，则将控制传递到功能块615。否则，将控制传递到功能块620。
功能块615跳跃到下一宏块，并且将控制传递到结束块649。
功能块620计算J16×16GEO，并且将控制传递到结束块649。
转向图6B，用于8×8几何模式的模式判定的示例性方法通常用附图标记650来指明。
方法650包括开始块655，在开始块655将控制传递到判定块660。判定块660确定是否J最佳，次佳8×8模式＜T最佳，次佳16×16模式，其中T是阈值。如果是，则将控制传递到功能块665。否则，将控制传递到功能块670。
功能块665跳跃到下一宏块，并且将控制传递到结束块699。
功能块670计算J8×8GEO，并且将控制传递到结束块699。
1.4.残余判定
残余的能量可以是给定宏块的预测质量的指示符。如果当前宏块的最佳MPEG-4 AVC标准模式的残余的能量足够低，则编码器可以跳过测试几何模式。类似地，如果当前子宏块的最佳MPEG-4 AVC标准子宏块模式的残余的能量低，则我们可以跳过测试子宏块几何模式。在一个实施例中，我们可以使用残余离散余弦变换(DCT)系数的绝对和来计算残余的能量。
转向图7，用于基于残余信息的快速几何模式判定的示例性方法一般用附图标记700来指明。
方法700包括开始块705，在开始块705将控制传递到功能块710。功能块710检查最佳MPEG-4 AVC标准模式的残余，并且将控制传递到判定块715。判定块715确定残余的能量是否小于阈值T。如果是，则将控制传递到功能块725。否则，将控制传递到功能块720。
功能块720检查几何模式，并且将控制传递到功能块725。
如果几何模式被检查，则功能块725选择几何模式和来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块799。
1.5.运动矢量判定
统计上地，由于当存在运动边缘时几何模式最有帮助的事实(即，背景倾向于更静止和/或具有全局运动)，因此前景(foreground)倾向于比背景使用更多的几何模式。通过使用空间和/或时间相邻宏块来分析最佳MPEG-4AVC标准模式的运动字段，编码器可以判定我们是否可以跳过测试几何模式。在一个实施例中，编码器计算最佳MPEG-4 AVC标准运动矢量和相邻运动矢量的差异。如果所述差异小于阈值，则编码器跳过测试几何模式。否则测试几何模式。
转向图8，用于基于运动矢量信息的快速模式判定的示例性方法通常用附图标记800来指明。
方法800包括开始块805，在开始块805将控制传递到功能块810。功能块810计算来自那些最佳MPEG-4 AVC标准模式和相邻宏块的运动的差异，并且将控制传递到判定块815。判定块815确定该差异是否小于阈值T。如果是，则将控制传递到功能块825。否则，将控制传递到功能块820。
功能块820检查几何模式，并且将控制传递到功能块825。
功能块825选择几何模式与来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块899。
2.几何分区模式内的快速楔形选择
在这个分类中，一个目标是减少我们必需用来搜索几何分区模式的可能分区的数目。目标是减少搜索空间、并且最小化最佳编码模式和/或几何分区的优化算法和恢复陷入局部最小值的机会。在该第二类别下的途径可被分离为下列两个子分类：(1)基于预测性的算法；和(2)分级搜索。
2.1.预测性算法
预测性算法可被考虑为主要包括下列三个步骤：(1)初始预测因子选择从一组潜在可能的楔形中选择最佳楔形；(2)如果满足一些规则，则自适应早期终止允许终止在给定阶段的搜索；和(3)预测精化利用最佳楔形预测因子周围的精化图案，以便改善最终预测。可以独立或者联合地执行先前的三个步骤。
2.1.1预测因子选择
其目标是利用预先计算的信息来发现最可能的楔形。我们可以将我们的预测因子划分为下列三组：(1)基于空间和/或时间相关性的预测因子；(2)基于最佳MPEG-4 AVC标准帧间模式的预测因子(如果可得到)；和(3)固定的预测因子网格(predictor grid)。
关于第一组，即基于空间和/或时间相关性的预测因子，我们可以从空间相邻楔形和/或时间相邻楔形扩展楔形分区(或楔形)、和/或那些楔形的一些功能，并且使用它们作为预测因子。
关于第二组，即基于最佳MPEG-4 AVC标准帧间模式的预测因子(如果可得到)，观察到在优化几何模式和最佳MPEG-4 AVC标准帧间模式之间存在强烈的关联性(例如，如果具有重要的水平方向的任意几何分区实际上是最可能的分区模式，则16×8模式很可能是次佳模式)。
关于第三组，即固定的预测因子网格，为了避免其中优化陷入局部最小值的情形，我们也可以测试附加的预测因子。更具体地，我们可以设计一组在预测中心周围相等地或者更密集地隔开的预测因子。在一个实施例中，我们可以使用Δρ′＝2Δρ和Δθ′＝4Δθ来设置固定的搜索预测因子。我们应当注意所有的上述预测因子在所有情况下并不是必需的。我们可以根据是否满足特定条件来自适应地禁用/使能一些预测因子。
2.1.2自适应早期终止
从仿真中我们注意到相邻块的编码成本趋向于高度相关。基于此，可以设置阈值，因此如果当前块的编码成本跨过那个阈值，则搜索算法可以更早地停止。这明显地减低了计算复杂度。我们可以设计两种类型的阈值。一种类型的阈值可被用来从所述预测因子集合中选择最佳或次佳楔形。另一种类型的阈值可被用来判定几何模式是否将被最终选择为最佳模式。所述阈值可以使用空间/时间相邻宏块的RDcost、和/或最佳MPEG-4 AVC标准模式的RDcost来设计(如果可得到)。
一个实施例可以实现如下。在测试所有空间/时间/MPEG-4 AVC标准预测因子之后，我们可以检查RDcost是否少于某一阈值T0。如果是，则我们停止并选择最佳预测因子作为几何模式的最佳楔形。否则，我们测试固定的预测因子。如果RDcost(和/或编码成本)少于T1，则我们将停止并且选择最佳预测因子作为几何模式的最终楔形。否则，我们测试RDcost是否大于T2。如果是，则我们将停止并且设置MPEG-4 AVC标准测试模式作为宏块的最佳模式。否则，我们将精化我们的最佳楔形候选。
2.1.3预测精化
使用被定位在最佳预测因子处的迭代性搜索图案可以进一步精化楔形搜索。我们可以应用来自快速运动估计的所有搜索图案想法。在一个实施例中，例如，我们可以将搜索图案定义为类似于菱形搜索。假设最佳预测因子是(ρ0，θ0)。
步骤1：测试在搜索空间内利用ρ＝ρ0±Δρ和θ＝θ0±Δθ配对的所有楔形。
步骤2：如果具有最小RDcost的楔形是(ρ0，θ0)，则我们停止。否则，通过将(ρ0，θ0)设置为具有最小RDcost的楔形而转到步骤1。
我们还可以在第二或第三最佳预测因子处应用预测精化，以便避免陷入局部最小值。而且，六角形搜索可被应用于更密集和更好覆盖范围的参数空间。当然，本原理不仅限于菱形和六角形搜索，因此可以使用其它类型的搜索，同时维持本原理的精神。
转向图9，用于快速预测性楔形选择的示例性方法一般用附图标记900来指明。
方法900包括开始块905，在开始块905将控制传递到功能块910。功能块910选择一组楔形预测因子，并且将控制传递到功能块915。功能块915从空间/时间预测因子和MPEG-4 AVC标准帧间模式预测因子中选择最佳楔形，并且将控制传递到判定块920。判定块920确定最佳预测因子的RDcost是否小于阈值T0。如果是，则将控制传递到功能块950。否则，将控制传递到功能块925。
功能块925测试固定的预测因子网格，并且将控制传递到判定块930。判定块930确定最佳预测因子的RDcost是否小于阈值T1。如果是，则将控制传递到功能块950。否则，将控制传递到判定块935。
判定块935确定最佳预测因子的RDcost是否大于阈值T2。如果是，则将控制传递到功能块940。否则，将控制传递到功能块945。
功能块945执行预测因子精化，并且将控制传递到功能块950。
功能块950设置几何模式中的最佳楔形，并且将控制传递到功能块955。
功能块955选择几何模式和MPEG-4 AVC模式之间的最佳模式，并且将控制传递到结束块999。
2.2分级搜索
在一实施例中，我们可以应用分级楔形搜索。分级楔形搜索涉及建立楔形参数的分级金字塔(pyramid)。首先在较高级别的金字塔处使用最小图像分辨率执行在2.1.3(预测精化)中的完全搜索或快速搜索图案，以便发现最佳楔形。然后精化该楔形，直到最低级别的金字塔达到原始图像分辨率。在另一实施例中，对分区参数的金字塔式搜索也可应用于原始分辨率图像。这意味着通过在每一级算法处改善(加倍)分区参数的分辨率以分级的方式反复地精化定义分区的参数。
转向图10，使用分级搜索的快速楔形选择的示例性方法通常用附图标记1000来指明。
方法1000包括开始块1005，该开始块将控制传递到功能块1010。功能块1010建立参数的分级金字塔，并且将控制传递到功能块1015。功能块1015对该金字塔的最高级别中的最佳楔形执行完全/快速搜索，并且将控制传递到功能块1020。功能块1020从该金字塔的最高级别到最低级别中精化楔形，并且将控制传递到功能块1025。功能块1025选择几何模式的最佳楔形，并且将控制传递到功能块1030。功能块1030选择几何模式与MPEG-4 AVC标准模式之间的最佳模式，并且将控制传递到结束块1099。
转向图11，快速几何模式和楔形选择的示例性方法通常用附图标记1100来指明。
方法1100包括开始块1105，该开始块将控制传递到功能块1110。功能块1110测试MPEG-4 AVC标准模式，并且将控制传递到判定块1115。判定块1115确定是否应用快速模式判定以便检查我们是否能够跳过检查几何模式。如果能够，则将控制传递到功能块1120。否则，将控制传递到功能块1125。
功能块1120选择MPEG-4 AVC标准模式作为最佳模式，并且将控制传递到结束块1199。
功能块1125应用快速楔形选择以便在几何模式中发现最佳楔形，并且将控制传递到功能块1130。功能块1130选择几何模式与MPEG-4 AVC标准模式之间的最佳模式，并且将控制传递到结束块1199。
3.通过几何分区和预测数据的交替优化进行的快速楔形选择
用于快速联合预测分区参数恢复的另一种途径是使用交替的优化策略。在与交替优化的使用相关的实施例中，编码器对于具有固定的楔形分区参数的分区交替地搜索最佳预测，并且在随后的步骤，编码器对于那个点为止恢复的分区来固定最佳预测因子，并且优化该楔形分区参数，从而在每个步骤，最小化了测量的失真和/或编码成本。根据预先固定(prefixed)的值以及对利用迭代次数进行的优化改进的测量中的至少一个，执行这一处理给定次数。将会理解，用于第一迭代的初始设置可以明显地影响这种途径的最终结果。在另一实施例中，测试用于几何分区和预测数据的交替优化的若干初始条件。该初始条件被应用于几何分区参数和/或预测数据参数。该初始条件可以包括但是不限于下列中的一个或多个：对用于楔形分区的参数空间的预先固定的取样；基于周围相邻物的可用数据的楔形分区参数的预测；用于帧间预测的快速运动搜索；和运动预测因子。
转向图12，快速替换性预测/分区参数优化的示例性方法通常用附图标记1200来指明。将会理解，图12的方法1200可以结合一种或多种先前描述的途径来实现，同时维持本原理的精神。
方法1200包括开始块1205，该开始块将控制传递到功能块1210。功能块1210为几何参数和分区预测设置初始猜测，并且将控制传递到循环限制块1215。循环限制块1215设置N次迭代的循环，并且将控制传递到功能块1220。功能块1220保持分区预测参数，并且将控制传递到功能块1225。功能块1225发现在所有可能性(或者其样本)上循环的最佳几何参数，并且将控制传递到功能块1230。功能块1230设置新的几何分区参数，并且将控制传递到功能块1235。功能块1235保持几何分区参数，并且将控制传递到功能块1240。功能块1240发现在所有可能性(或者其样本)上循环的最佳分区预测参数，并且将控制传递到功能块1245。功能块1245设置新的分区预测参数，并且将控制传递到判定块1250。判定块1250确定是否已经达到稳定的状态优化。如果达到，则将控制传递到功能块1260。否则，将控制传递到循环限制块1255。
循环限制块1255结束N个迭代上的循环，并且将控制传递到功能块1260。
功能块1260保存最佳分区边缘和分区参数，并且将控制传递到结束块1299。
现在将给出本发明的许多伴随优点/特征中的一些的描述，上面已经提到了一些优点/特征。例如，一个优点/特征是一种方法，其包括使用基于几何模型的分区模式来执行非穷尽性几何模式判定。所述执行步骤包括：基于在基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，跳过基于几何模型的分区模式的测试。
另一个优点/特征是如上所述的方法，其中所述非穷尽性几何模式判定使用非几何模式信息、早期停止阈值、相邻信息、残余信息和运动矢量信息中的至少一个。
又一个其它优点/特征是如上所述的方法，其中早期停止阈值对应于量化参数、空间相邻率失真成本和时间相邻率失真成本中的至少一个。
而且，另一个优点/特征是一种方法，其包括使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述执行步骤包括应用预测性搜索和分级搜索中的至少一个。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。
而且，另一个优点/特征是如上所述的方法，其中初始预测因子选择选择性地使能基于空间相关性的预测因子、基于时间相关性的预测因子、基于给定编码标准或者给定编码推荐的最佳帧间模式的预测因子、和固定的预测因子网格中的至少一个。
而且，另一个优点/特征是一种方法，包括使用基于几何模型的分区模式来对图像的视频信号数据进行编码。所述编码步骤使用用于图像的至少一部分的几何分区参数和预测数据的交替优化来编码视频信号数据。
基于此处的示教，相关领域内的普通技术人员可以容易地确定本原理的这些和其它特征和优点。将会理解，本原理的示教能够以硬件、软件、固件、专用处理器、或者它们的组合的各种形式来实现。
更优选地，本原理的示教被实现为硬件和软件的组合。而且，所述软件可被实现为程序存储单元上有形地具化的应用程序。所述应用程序可被上传到包括任意合适架构的机器、并由其执行。优选地，所述机器被实现于计算机平台上，该计算机平台具有诸如一个或多个中央处理单元(“CPU”)、随机存取存储器(“RAM”)、和输入/输出(“I/O”)接口之类的硬件。所述计算机平台也可以包括操作系统和微指令代码。此处描述的各种各样的处理和功能可以是微指令代码的一部分或者应用程序的一部分，或者它们的任意组合，它们可以通过CPU来执行。另外，各种其它外围单元可以连接到计算机平台，例如附加的数据存储单元和打印单元。
进一步理解，因为附图中描绘的一些构成的系统组件和方法优选地以软件来实现，因此系统组件之间的实际连接或者处理功能块可以根据本原理被编程的方式而有所不同。给出此处的示教，相关领域内的普通技术人员将能够预料本原理的这些和类似实现方式或配置。
尽管此处已经参考附图描述了说明性的实施例，但是将会理解，本原理不限于这些精确的实施例，并且相关领域内的普通技术人员可以在其中实现各种变化和修改，而不背离本原理的范畴或精神。所有这些变化和修改意欲包含在如所附权利要求中阐述的本原理的范畴之内。
相关申请的交叉引用
本申请要求于2007年4月12日提交的美国临时申请序列号第60/911,486的权益，在此并入其全部内容作为参考。
本说明书图解说明了本原理。因此将会理解到，本领域的技术人员将能够设计出体现本原理并且被包含在其精神和范畴之内的各种安排，尽管各种安排未在此处明确地描述或示出)。
此处叙述的所有示例和条件性语言是为了教学目的，以辅助读者理解发明人对现有技术进一步贡献的本原理和构思，并且应当被理解为不限于如此具体叙述的示例和条件。
而且，此处叙述原理、方面和本原理的实施例的所有陈述、以及其特定示例意欲涵盖其结构性和功能性的等同物。另外，意欲所述等同物包括当前已知的等同物以及将来研发的等同物，即，被开发用于执行相同功能的任何元件，而不管结构如何。
因此，例如，本领域的普通技术人员将会理解，这里展现的框图代表体现本原理的图解性电路的概念图。类似地，将会理解，任何流程图、流向图、状态转换图、伪代码等代表可以基本在计算机可读媒体上表现并且因此由计算机或处理器执行的各种处理，无论是否明确地地示出了这样的计算机或处理器。
附图中示出的各种元件的功能可以通过使用专用硬件和能够与适当的软件联合执行软件的硬件来提供。当功能被处理器提供时，可以通过单个专用处理器、单个共享处理器或者多个单独的处理器(可以共享其中的一些处理器)来提供所述功能。而且，术语“处理器”或“控制器”的明确使用不应当被曲解为排他地指能够执行软件的硬件，而是可以隐性地包括(而非限制性地)数字信号处理器(“DSP”)硬件、用于存储软件的只读存储器(“ROM”)、随机存取存储器(“RAM”)和非易失性存储器。
还可以包括其它硬件，常规的硬件和/或定制的硬件。类似地，附图中所示的任意开关仅仅是概念性的。它们的功能可以通过程序逻辑的操作、通过专用逻辑、通过编程控制和专用逻辑的交互作用、或者甚至手动来执行，从上下文中可以更具体地理解，实施者可以选择特定的技术。
在于此的权利要求书中，被表述为用于执行具体功能的部件的任意元件意欲涵盖执行该功能的任意方式，包括例如，a)执行该功能的电路元件的组合，或者b)任意形式的软件，因此包括固件、微代码等，它们被与用于执行该软件的适当电路相结合以执行该功能。由所述权利要求限定的本原理蕴含的事实是：各种所记载的手段提供的功能性被组合并且以权利要求请求的方式结合在一起。因此，认为是，可以提供那些功能性的任意手段等同于此处所示的那些手段。
说明书中对本原理的“一个实施例”或者“实施例”的引用是指在本原理的至少一个实施例中包含了结合该实施例描述的特别特征、结构、特性等等。因此，在贯穿说明书的各个位置出现的短语“在一个实施例中”或者“在实施例中”不必都是指向相同的实施例。
将会理解，术语“和/或”的使用(例如，在“A和/或B”的情况下)意欲涵盖第一所列选项的选择(A)、第二所列选项的选择(B)、或者两个选项的选择(A和B)。作为另一个示例，在“A、B和/或C”的情况下，这样的措辞意欲涵盖第一所列选项的选择(A)、第二所列选项的选择(B)、第三所列选项的选择(C)、第一和第二所列选项的选择(A和B)、第一和第三所列选项的选择(A和C)、第二和第三所列选项的选择(B和C)、或者所有三个选项的选择(A、B和C)。如本领域和相关领域中的普通技术人员容易明白的是，对于许多所列的项来说，这可以进行扩展。
而且，将会理解，尽管此处参考MPEG-4 AVC标准描述了本原理的一个或多个实施例，但是本原理并不单单限于该标准，因此本原理可以结合其它视频编码标准、建议书及其扩展来利用，包括MPEG-4 AVC标准的扩展，同时维持本原理的精神。
而且，如此处所使用的，短语“楔形分区(wedge partition)”和“楔形分区(wedge partitioning)”是指图像块被分区为两个区域，这两个区域被任意线或曲线分离。而且，词语“楔形”是指给定边界线或曲线的特定设置和/或选择的分区形状。
而且，如此处所使用的，例如，关于搜索，术语“快速”是指能够找到最佳解决方案或接近最佳的解决方案、但是比密集的(intensive)完全搜索算法具有较低计算复杂度的有效算法。
转向图1，能够根据(被扩展用于本原理的)MPEG-4 AVC标准执行视频编码的视频编码器一般用附图标记100来表示。
视频编码器100包括帧排序缓冲器110，其具有与组合器185的非反相输入进行信号通信的输出。组合器185的输出与具有几何扩展的变换器和量化器125的第一输入进行信号通信连接。具有几何扩展的变换器和量化器125的输出与具有几何扩展的熵编码器145的第一输入以及具有几何扩展的逆变换器和逆量化器150的第一输入进行信号通信连接。具有几何扩展的熵编码器145的输出与组合器190的第一非反相输入进行信号通信连接。组合器190的输出与输出缓冲器135的第一输入进行信号通信连接。
具有几何扩展的编码器控制器105的第一输出与帧排序缓冲器110的第二输入、具有几何扩展的逆变换器和逆量化器150的第二输入、画面类型判定模块115的输入、具有几何扩展的宏块类型(MB类型)判定模块120的输入、具有几何扩展的帧内预测模块160的第二输入、具有几何扩展的解块滤波器165的第二输入、具有几何扩展的运动补偿器170的第一输入、具有几何扩展的快速运动估计器175的第一输入、和参考画面缓冲器180的第二输入进行信号通信连接。
具有几何扩展的编码器控制器105的第二输出与补充增强信息(SEI)插入器130的第一输入、具有几何扩展的变换器和量化器125的第二输入、具有几何扩展的熵编码器145的第二输入、输出缓冲器135的第二输入、以及序列参数集(SPS)和画面参数集(PPS)插入器140的输入进行信号通信连接。
画面类型判定模块115的第一输出与帧排序缓冲器110的第三输入进行信号通信连接。画面类型判定模块115的第二输出与具有几何扩展的宏块类型判定模块120的第二输入进行信号通信连接。
序列参数集(SPS)和画面参数集(PPS)插入器140的输出与组合器190的第三非反相输入进行信号通信连接。
具有几何扩展的逆量化和逆变换器150的输出与组合器127的第一非反相输入进行信号通信连接。组合器127的输出与具有几何扩展的帧内预测模块160的第一输入和具有几何扩展的解块滤波器165的第一输入进行信号通信连接。具有几何扩展的解块滤波器165的输出与参考画面缓冲器180的第一输入进行信号通信连接。参考画面缓冲器180的输出与具有几何扩展175的快速运动估计器的第二输入进行信号通信连接。具有几何扩展的快速运动估计器175的第一输出与具有几何扩展的运动补偿器170的第二输出进行信号通信连接。具有几何扩展的快速运动估计器175的第二输出与具有几何扩展的熵编码器145的第三输出进行信号通信连接。
具有几何扩展的运动补偿器170的输出与开关197的第一输入进行信号通信连接。具有几何扩展的帧内预测模块160的输出与开关197的第二输入进行信号通信连接。具有几何扩展的宏块类型判定模块120的输出与开关197的第三输入进行信号通信连接。开关197的输出与组合器127的第二非反相输入进行信号通信连接。
帧排序缓冲器110和具有几何扩展的编码器控制器105的输入可用作编码器100的输入，用于接收输入画面101。而且，补充增强信息(SEI)插入器130的输入可用作编码器100的输入，用于接收元数据。输出缓冲器135的输出可用作编码器100的输出，用于输出比特流。
使用几何区域分区的帧间预测和帧内预测已经被认为是在提高视频编码效率方面具有前途的研究方向。以前，对于(例如根据MPEG-4 AVC标准执行的)高级视频编码，已经建议引入针对帧间和帧内预测的几何分区，以便提高视频编码效率。为了获得最佳性能，对于编码器来说发现最佳的几何分区是至关重要的。在这些建议中使用了强大的全面搜索策略，但是复杂度非常高。然而，对于模式/分区选择可期望拥有某些快速算法，从而增加的几何分区的计算复杂度不会变成实际系统的阻碍。因此，根据本原理，我们已经构思快速几何算法来节省编码器处的计算性资源。在本原理的一个实施例中，使用基于几何模型的分区模式，对视频编码器使能快速几何模式判定，其中基于标准预测模式与几何分区模式之间的相关性和依赖性中的至少一个来跳过测试几何模式。在本原理的另一个实施例中，使用基于几何模型的分区模式使能对于视频编码器的快速几何参数选择，其中预测性快速搜索算法被应用，包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。在本原理的又一个实施例中，使用基于几何模型的分区模式使能对于视频编码器的快速几何参数选择，其中使用分级搜索。在本原理的又一个实施例中，使能使用基于几何模型的分区模式的视频编码器，其中使用了几何分区和预测数据的交替优化。
如上注意的，最新的视频压缩技术使用帧分区，它比老的视频编码标准中通常使用的简单的均匀块分区更有效，所述老的视频编码标准诸如国际标准化组织/国际电工委员会(ISO/IEC)运动图像专家组-2(MPEG-2)标准。然而，MPEG-4 AVC标准中使用的基于树的帧分区仍旧不能对视频信息足够有效地编码，因为它不能捕获二维(2D)数据的几何结构。为了解决这样的局限，展示了一种通过考虑2D视频数据的2D几何来更好地表示和编码2D视频数据的方法和设备。在一个实施例中，关于针对帧间(INTER16×16GEO、INTER8×8GEO)和帧内预测(INTRA16×16GEO、INTRA8×8GEO)两者的新模式集合，我们使用楔形分区(即，将一个块分区为两个区域，该两个区域由任意线或曲线分离)。
在一个实施例中，可以使用MPEG-4 AVC标准作为基础来合并几何分区模式。块内的几何分区通过线的隐式公式来建模。因此，在一实施例中，分区被定义如下(如图2中所示)：
f(x，y)＝xcosθ+ysinθ-ρ，
其中，ρ、θ分别表示以下：在边界线f(x，y)的正交方向上从原点到边界线f(x，y)的距离；和f(x，y)的正交方向与水平坐标轴x的角度。
转向图2，图像的示例性几何分区一般用附图标记200指明。图像块一般用附图标记220指明。
从它的公式中直接得出：也考虑了具有更高阶几何参数的针对f(x，y)的更相关的模型。
每个块像素(x，y)被分类，从而：
对于编码目的，先验定义了可能分区(或者几何模式)的字典库(dictioanry)。这可用公式定义如下：
和
以及
和
其中，Δρ和Δθ是所选择的量化(参数分辨率)步辐。θ和ρ的量化的索引是所传送的用于对边缘进行编码的信息。然而，如果在编码过程中使用模式16×8和8×16，则对于ρ＝0的情况，可以从可能边缘的集合中去除角度0和90。
在几何自适应运动补偿模式中，执行对每个分区的ρ、θ和运动矢量的搜索，以便发现最佳配置。对于每对ρ和θ，在两个阶段中进行完全搜索策略，其中搜索最佳运动矢量。在几何自适应帧内预测模式内，执行对于每个分区的ρ、θ和最佳预测因子(方向性预测或统计，等等)的搜索，以便发现最佳配置。
在编码器方，如果使用完全搜索，则几何模式的计算性复杂度可能非常高。因此，开发快速算法来减少实际应用中的编码器复杂度是相当重要的。
在一实施例中，我们使用MPEG-4 AVC标准和P画面的帧间几何分区的架构。然而，将会理解，给出此处提供的本原理的示教，本领域和相关领域中的普通技术人员可容易地将本原理的其它实施例应用于帧内几何分区、其它类型的画面和其它视频编码标准和建议书、及其扩展，同时维持本原理的精神。本原理可以与快速运动估计和/或MPEG-4 AVC快速模式判定联合地应用。对于编码成本测量，我们使用RDcost作为一个示例。然而，将会理解，本原理不仅仅限于在前类型的编码成本测量，因此可以应用其它的编码成本测量，包括但不限于仅失真测量(例如均方差等)等等，同时维持本原理的精神。
为了图示和清楚目的，本原理被分类为以下三个类别：(1)基于原始MPEG-4 AVC标准帧间预测模式与几何分区模式之间的相关性的快速模式判定；(2)几何分区模式内的快速几何分区选择；(3)通过几何分区和预测日期的交替优化的快速几何分区选择。将会理解，可以联合地或者独立地应用这些类别。
1.基于原始MPEG-4 AVC标准帧间预测模式与几何分区模式之间的相关性的快速模式判定。
在这个类别中，执行快速算法以便判定我们是否能够完整地跳过测试几何模式。我们将假设MPEG-4 AVC标准帧间预测模式在几何分区模式之前被编码器测试。我们将进一步把第一类别下的我们的算法分类为下列5个子类别：(1)MPEG-4 AVC标准模式判定；(2)早期停止判定；(3)相邻判定；(4)残余判定；和(5)运动矢量判定。可以联合地或者独立地应用这些子类别。
1.1 MPEG-4 AVC标准模式判定
在这个子类别中，我们基于由编码器选择的最佳和/或次佳(如果可得到)的MPEG-4 AVC标准模型来判定是否跳过测试几何模式的压缩性能。在一实施例中，这一类别的判定是基于以下假设：例如，如果编码器选择几何模式作为宏块的最佳模式，则最佳MPEG-4 AVC标准帧间预测模式不可能是SKIP、16×16或者帧内模式。同时，在子8×8级别处，如果最佳子宏块模式是8×8几何模式，则人们可以假设最佳MPEG-4 AVC标准子宏块模式不可能是8×8(或者，如果考虑帧间-B预测，则不可能是Direct 8×8)。在宏块大小级别，这是因为SKIP和/或16×16意味着宏块很可能在相同对象或运动区域内，并且帧内意味着宏块很可能是被阻塞的(occluded)对象。这同样应用于子宏块。在一个实施例中，我们首先检查最佳MPEG-4 AVC标准模式是否是SKIP模式。如果是这种情况，则编码器跳过测试几何模式，从而避免了边缘和运动搜索。如果SKIP不是由编码器选择的最佳模式，则编码器检查最佳MPEG-4 AVC标准模式是否是帧内模式。如果是这种情况，则跳过几何模式。否则，编码器检查最佳MPEG-4 AVC标准模式是否是16×16。如果是这种情况，则编码器检查次佳MPEG-4 AVC标准模式。如果它是SKIP模式，则我们进一步跳过测试几何模式。否则，我们测试几何模式。类似地，对于子宏块，如果最佳MPEG-4 AVC标准子宏块模式是8×8分区大小，则编码器跳过测试几何子宏块模式。
转向图5A，用于16×16几何模式的模式判定的示例性方法一般用附图标记500来指明。
方法500包括开始块505，在开始块505，将控制传递到判定块510。判定块510确定是否J最佳16×16模式＜T最佳16×16模式。如果是，则将控制传递到功能块515。否则，将控制传递到功能块520。
功能块515跳跃到下一宏块，并且将控制传递到结束块549。
功能块520计算J16×16GEO，并且将控制传递到结束块549。
转向图5B，用于8×8几何模式的模式判定的示例性方法一般用附图标记550来指明。
方法550包括开始块555，在开始块555将控制传递到判定块560。判定块560确定是否J最佳8×8模式＜T最佳8×8模式，其中T代表阈值。如果是，则将控制传递到功能块565。否则，将控制传递到功能块570。
功能块516跳跃到下一宏块，并且将控制传递到结束块599。
功能块570计算J8×8GEO，并且将控制传递到结束块599。
将会理解，给出此处提供的本原理的示教，此处提供的示例易于被本领域和相关领域中的普通技术人员扩展到最佳模式的其它组合。而且，将会理解，考虑用来预测的最大数目的条目不限于MPEG-4 AVC标准预测模式当中的最佳和次佳被选的模式，并且因此，也可以利用其它数目的最佳被选的模式，同时维持本原理的精神。
1.2早期停止判定
在这个子类别中，我们建议使用早期停止准则来达到快速模式判定。这些停止准则都基于自适应阈值机制。该阈值可以是量化参数、空间/时间相邻率失真成本(RDcost)等等的函数。基本方案是在测试所有可能的MPEG-4AVC标准宏块/子宏块分区模式之后应用阈值，以便判定是否跳过测试16×16和/或8×8几何分区模式。在一个实施例中，我们在应用16×16/8×8几何分区判定之前仅测试最佳MPEG-4 AVC标准模式。如果最佳MPEG-4 AVC标准模式的RDcost小于某一阈值，则我们跳过测试几何模式。否则，我们测试几何模式。
可以基于一些安全保护或从RDcost收集的统计来选择快速几何模式判定阈值。
转向图3A和图3B，基于MPEG-4 AVC标准模式信息的快速几何模式判定的示例性方法通常分别用附图标记300和350来指明。
方法300包括开始块305，在开始块305将控制传递到功能块310。功能块310检查最佳MPEG-4 AVC标准模式，并且将控制传递到判定块315。判定块315确定最佳MPEG-4 AVC标准模式是否是SKIP(跳过)或帧内。如果是，则将控制传递到判定块320。否则，将控制传递到功能块335。
判定块320确定最佳MPEG-4 AVC标准模式是否是16×16。如果是，则将控制传递到判定块325。否则，将控制传递到功能块330。
判定块325确定次佳MPEG-4 AVC标准模式是否是SKIP(跳过)。如果是，则将控制传递到功能块335。否则，将控制传递到功能块330。
功能块330检查几何模式，并且将控制传递到功能块335。
功能块335选择最佳模式，并且将控制传递到结束块349。
方法350包括开始块355，在开始块355将控制传递到功能块360。功能块360检查最佳MPEG-4 AVC标准子宏块模式，并且将控制传递到判定块365。判定块365确定最佳MPEG-4 AVC标准模式是否为8×8。如果是，则将控制传递到功能块375。否则，将控制传递到功能块370。
功能块370检查子宏块几何模式，并且将控制传递到功能块375。
功能块375选择最佳子宏块模块，并且将控制传递到结束块399。
在另一实施例中，在16×16/8×8几何分区判定之前，我们使用来自最佳和次佳MPEG-4 AVC标准模式的统计数字(如果可得到)。如果最佳MPEG-4 AVC标准模式的RDcost小于某一阈值，并且次佳MPEG-4 AVC标准模式的RDcost小于另一阈值，则我们跳过测试几何模式。否则，我们测试几何模式。
转向图4，基于相邻信息的快速几何模式判定的示例性方法一般用附图标记400来指明。
方法400包括开始块405，开始块405将控制传递到功能块410。功能块410检查上部和左部宏块模式判定，并且将控制传递到判定块415。判定块415确定模式判定是否为SKIP(跳过)或者16×16。如果是，则将控制传递到功能块425。否则，将控制传递到功能块420。
功能块420检查几何模式，并且将控制传递到功能块425。
如果几何模式被检查，则功能块425选择几何模式和来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则，功能块425选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块499。
在另一个实施例中，可以考虑第一类别的第一和第二子类别的途径之间的组合，其中使用关于阈值成本准则和最佳被选的模式准则的组合。另一个可能的途径是使用最佳模式和次佳模式作为阈值适应的条件性环境。根据最佳和次佳MPEG-4 AVC标准模式的组合，可以设置用于跳过或者不测试几何模式的判定阈值。
1.3相邻判定
MPEG-4 AVC标准使用块编码结构。通常，对象趋向于穿过块边界。在这个子类别中，我们将使用相邻信息来使得模式判定更快速。
如果空间和/或时间相邻宏块都不包括对给定的一个或多个宏块(例如16×8，8×16，8×8，8×4)(或者子块)进行分区的模式，则当前宏块(或者子块)的最佳模式成为几何模式的可能性较低。在一个实施例中，编码器检查左部和上部相邻宏块，如果它们都是SKIP(跳过)或16×16，则编码器跳过测试当前宏块中的几何模式。否则，测试几何模式。在另一个实施例中，考虑相邻物和当前最佳MPEG-4 AVC标准模式的组合判定规则被考虑。
转向图6A，用于16×16几何模式的模式判定的示例性方法一般用附图标记600来指明。
方法600包括开始块605，在开始块605将控制传递到判定块610。判定块610确定是否J最佳，次佳16×16模式＜T最佳，次佳16×16模式，其中T是阈值。如果是，则将控制传递到功能块615。否则，将控制传递到功能块620。
功能块615跳跃到下一宏块，并且将控制传递到结束块649。
功能块620计算J16×16GEO，并且将控制传递到结束块649。
转向图6B，用于8×8几何模式的模式判定的示例性方法通常用附图标记650来指明。
方法650包括开始块655，在开始块655将控制传递到判定块660。判定块660确定是否J最佳，次佳8×8模式＜T最佳，次佳16×16模式，其中T是阈值。如果是，则将控制传递到功能块665。否则，将控制传递到功能块670。
功能块665跳跃到下一宏块，并且将控制传递到结束块699。
功能块670计算J8×8GEO，并且将控制传递到结束块699。
1.4.残余判定
残余的能量可以是给定宏块的预测质量的指示符。如果当前宏块的最佳MPEG-4 AVC标准模式的残余的能量足够低，则编码器可以跳过测试几何模式。类似地，如果当前子宏块的最佳MPEG-4 AVC标准子宏块模式的残余的能量低，则我们可以跳过测试子宏块几何模式。在一个实施例中，我们可以使用残余离散余弦变换(DCT)系数的绝对和来计算残余的能量。
转向图7，用于基于残余信息的快速几何模式判定的示例性方法一般用附图标记700来指明。
方法700包括开始块705，在开始块705将控制传递到功能块710。功能块710检查最佳MPEG-4 AVC标准模式的残余，并且将控制传递到判定块715。判定块715确定残余的能量是否小于阈值T。如果是，则将控制传递到功能块725。否则，将控制传递到功能块720。
功能块720检查几何模式，并且将控制传递到功能块725。
如果几何模式被检查，则功能块725选择几何模式和来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块799。
1.5.运动矢量判定
统计上地，由于当存在运动边缘时几何模式最有帮助的事实(即，背景倾向于更静止和/或具有全局运动)，因此前景(foreground)倾向于比背景使用更多的几何模式。通过使用空间和/或时间相邻宏块来分析最佳MPEG-4AVC标准模式的运动字段，编码器可以判定我们是否可以跳过测试几何模式。在一个实施例中，编码器计算最佳MPEG-4 AVC标准运动矢量和相邻运动矢量的差异。如果所述差异小于阈值，则编码器跳过测试几何模式。否则测试几何模式。
转向图8，用于基于运动矢量信息的快速模式判定的示例性方法通常用附图标记800来指明。
方法800包括开始块805，在开始块805将控制传递到功能块810。功能块810计算来自那些最佳MPEG-4 AVC标准模式和相邻宏块的运动的差异，并且将控制传递到判定块815。判定块815确定该差异是否小于阈值T。如果是，则将控制传递到功能块825。否则，将控制传递到功能块820。
功能块820检查几何模式，并且将控制传递到功能块825。
功能块825选择几何模式与来自MPEG-4 AVC标准的最佳模式之间的最佳模式，否则选择来自MPEG-4 AVC标准的最佳模式，并且将控制传递到结束块899。
2.几何分区模式内的快速楔形选择
在这个分类中，一个目标是减少我们必需用来搜索几何分区模式的可能分区的数目。目标是减少搜索空间、并且最小化最佳编码模式和/或几何分区的优化算法和恢复陷入局部最小值的机会。在该第二类别下的途径可被分离为下列两个子分类：(1)基于预测性的算法；和(2)分级搜索。
2.1.预测性算法
预测性算法可被考虑为主要包括下列三个步骤：(1)初始预测因子选择从一组潜在可能的楔形中选择最佳楔形；(2)如果满足一些规则，则自适应早期终止允许终止在给定阶段的搜索；和(3)预测精化利用最佳楔形预测因子周围的精化图案，以便改善最终预测。可以独立或者联合地执行先前的三个步骤。
2.1.1预测因子选择
其目标是利用预先计算的信息来发现最可能的楔形。我们可以将我们的预测因子划分为下列三组：(1)基于空间和/或时间相关性的预测因子；(2)基于最佳MPEG-4 AVC标准帧间模式的预测因子(如果可得到)；和(3)固定的预测因子网格(predictor grid)。
关于第一组，即基于空间和/或时间相关性的预测因子，我们可以从空间相邻楔形和/或时间相邻楔形扩展楔形分区(或楔形)、和/或那些楔形的一些功能，并且使用它们作为预测因子。
关于第二组，即基于最佳MPEG-4 AVC标准帧间模式的预测因子(如果可得到)，观察到在优化几何模式和最佳MPEG-4 AVC标准帧间模式之间存在强烈的关联性(例如，如果具有重要的水平方向的任意几何分区实际上是最可能的分区模式，则16×8模式很可能是次佳模式)。
关于第三组，即固定的预测因子网格，为了避免其中优化陷入局部最小值的情形，我们也可以测试附加的预测因子。更具体地，我们可以设计一组在预测中心周围相等地或者更密集地隔开的预测因子。在一个实施例中，我们可以使用Δρ′＝2Δρ和Δθ′＝4Δθ来设置固定的搜索预测因子。我们应当注意所有的上述预测因子在所有情况下并不是必需的。我们可以根据是否满足特定条件来自适应地禁用/使能一些预测因子。
2.1.2自适应早期终止
从仿真中我们注意到相邻块的编码成本趋向于高度相关。基于此，可以设置阈值，因此如果当前块的编码成本跨过那个阈值，则搜索算法可以更早地停止。这明显地减低了计算复杂度。我们可以设计两种类型的阈值。一种类型的阈值可被用来从所述预测因子集合中选择最佳或次佳楔形。另一种类型的阈值可被用来判定几何模式是否将被最终选择为最佳模式。所述阈值可以使用空间/时间相邻宏块的RDcost、和/或最佳MPEG-4 AVC标准模式的RDcost来设计(如果可得到)。
一个实施例可以实现如下。在测试所有空间/时间/MPEG-4 AVC标准预测因子之后，我们可以检查RDcost是否少于某一阈值T0。如果是，则我们停止并选择最佳预测因子作为几何模式的最佳楔形。否则，我们测试固定的预测因子。如果RDcost(和/或编码成本)少于T1，则我们将停止并且选择最佳预测因子作为几何模式的最终楔形。否则，我们测试RDcost是否大于T2。如果是，则我们将停止并且设置MPEG-4 AVC标准测试模式作为宏块的最佳模式。否则，我们将精化我们的最佳楔形候选。
2.1.3预测精化
使用被定位在最佳预测因子处的迭代性搜索图案可以进一步精化楔形搜索。我们可以应用来自快速运动估计的所有搜索图案想法。在一个实施例中，例如，我们可以将搜索图案定义为类似于菱形搜索。假设最佳预测因子是(ρ0，θ0)。
步骤1：测试在搜索空间内利用ρ＝ρ0±Δρ和θ＝θ0±Δθ配对的所有楔形。
步骤2：如果具有最小RDcost的楔形是(ρ0，θ0)，则我们停止。否则，通过将(ρ0，θ0)设置为具有最小RDcost的楔形而转到步骤1。
我们还可以在第二或第三最佳预测因子处应用预测精化，以便避免陷入局部最小值。而且，六角形搜索可被应用于更密集和更好覆盖范围的参数空间。当然，本原理不仅限于菱形和六角形搜索，因此可以使用其它类型的搜索，同时维持本原理的精神。
转向图9，用于快速预测性楔形选择的示例性方法一般用附图标记900来指明。
方法900包括开始块905，在开始块905将控制传递到功能块910。功能块910选择一组楔形预测因子，并且将控制传递到功能块915。功能块915从空间/时间预测因子和MPEG-4 AVC标准帧间模式预测因子中选择最佳楔形，并且将控制传递到判定块920。判定块920确定最佳预测因子的RDcost是否小于阈值T0。如果是，则将控制传递到功能块950。否则，将控制传递到功能块925。
功能块925测试固定的预测因子网格，并且将控制传递到判定块930。判定块930确定最佳预测因子的RDcost是否小于阈值T1。如果是，则将控制传递到功能块950。否则，将控制传递到判定块935。
判定块935确定最佳预测因子的RDcost是否大于阈值T2。如果是，则将控制传递到功能块940。否则，将控制传递到功能块945。
功能块945执行预测因子精化，并且将控制传递到功能块950。
功能块950设置几何模式中的最佳楔形，并且将控制传递到功能块955。
功能块955选择几何模式和MPEG-4 AVC模式之间的最佳模式，并且将控制传递到结束块999。
2.2分级搜索
在一实施例中，我们可以应用分级楔形搜索。分级楔形搜索涉及建立楔形参数的分级金字塔(pyramid)。首先在较高级别的金字塔处使用最小图像分辨率执行在2.1.3(预测精化)中的完全搜索或快速搜索图案，以便发现最佳楔形。然后精化该楔形，直到最低级别的金字塔达到原始图像分辨率。在另一实施例中，对分区参数的金字塔式搜索也可应用于原始分辨率图像。这意味着通过在每一级算法处改善(加倍)分区参数的分辨率以分级的方式反复地精化定义分区的参数。
转向图10，使用分级搜索的快速楔形选择的示例性方法通常用附图标记1000来指明。
方法1000包括开始块1005，该开始块将控制传递到功能块1010。功能块1010建立参数的分级金字塔，并且将控制传递到功能块1015。功能块1015对该金字塔的最高级别中的最佳楔形执行完全/快速搜索，并且将控制传递到功能块1020。功能块1020从该金字塔的最高级别到最低级别中精化楔形，并且将控制传递到功能块1025。功能块1025选择几何模式的最佳楔形，并且将控制传递到功能块1030。功能块1030选择几何模式与MPEG-4 AVC标准模式之间的最佳模式，并且将控制传递到结束块1099。
转向图11，快速几何模式和楔形选择的示例性方法通常用附图标记1100来指明。
方法1100包括开始块1105，该开始块将控制传递到功能块1110。功能块1110测试MPEG-4 AVC标准模式，并且将控制传递到判定块1115。判定块1115确定是否应用快速模式判定以便检查我们是否能够跳过检查几何模式。如果能够，则将控制传递到功能块1120。否则，将控制传递到功能块1125。
功能块1120选择MPEG-4 AVC标准模式作为最佳模式，并且将控制传递到结束块1199。
功能块1125应用快速楔形选择以便在几何模式中发现最佳楔形，并且将控制传递到功能块1130。功能块1130选择几何模式与MPEG-4 AVC标准模式之间的最佳模式，并且将控制传递到结束块1199。
3.通过几何分区和预测数据的交替优化进行的快速楔形选择
用于快速联合预测分区参数恢复的另一种途径是使用交替的优化策略。在与交替优化的使用相关的实施例中，编码器对于具有固定的楔形分区参数的分区交替地搜索最佳预测，并且在随后的步骤，编码器对于那个点为止恢复的分区来固定最佳预测因子，并且优化该楔形分区参数，从而在每个步骤，最小化了测量的失真和/或编码成本。根据预先固定(prefixed)的值以及对利用迭代次数进行的优化改进的测量中的至少一个，执行这一处理给定次数。将会理解，用于第一迭代的初始设置可以明显地影响这种途径的最终结果。在另一实施例中，测试用于几何分区和预测数据的交替优化的若干初始条件。该初始条件被应用于几何分区参数和/或预测数据参数。该初始条件可以包括但是不限于下列中的一个或多个：对用于楔形分区的参数空间的预先固定的取样；基于周围相邻物的可用数据的楔形分区参数的预测；用于帧间预测的快速运动搜索；和运动预测因子。
转向图12，快速替换性预测/分区参数优化的示例性方法通常用附图标记1200来指明。将会理解，图12的方法1200可以结合一种或多种先前描述的途径来实现，同时维持本原理的精神。
方法1200包括开始块1205，该开始块将控制传递到功能块1210。功能块1210为几何参数和分区预测设置初始猜测，并且将控制传递到循环限制块1215。循环限制块1215设置N次迭代的循环，并且将控制传递到功能块1220。功能块1220保持分区预测参数，并且将控制传递到功能块1225。功能块1225发现在所有可能性(或者其样本)上循环的最佳几何参数，并且将控制传递到功能块1230。功能块1230设置新的几何分区参数，并且将控制传递到功能块1235。功能块1235保持几何分区参数，并且将控制传递到功能块1240。功能块1240发现在所有可能性(或者其样本)上循环的最佳分区预测参数，并且将控制传递到功能块1245。功能块1245设置新的分区预测参数，并且将控制传递到判定块1250。判定块1250确定是否已经达到稳定的状态优化。如果达到，则将控制传递到功能块1260。否则，将控制传递到循环限制块1255。
循环限制块1255结束N个迭代上的循环，并且将控制传递到功能块1260。
功能块1260保存最佳分区边缘和分区参数，并且将控制传递到结束块1299。
现在将给出本发明的许多伴随优点/特征中的一些的描述，上面已经提到了一些优点/特征。例如，一个优点/特征是一种方法，其包括使用基于几何模型的分区模式来执行非穷尽性几何模式判定。所述执行步骤包括：基于在基于几何模型的分区模式与非几何分区模式之间的相关性和依赖性中的至少一个，跳过基于几何模型的分区模式的测试。
另一个优点/特征是如上所述的方法，其中所述非穷尽性几何模式判定使用非几何模式信息、早期停止阈值、相邻信息、残余信息和运动矢量信息中的至少一个。
又一个其它优点/特征是如上所述的方法，其中早期停止阈值对应于量化参数、空间相邻率失真成本和时间相邻率失真成本中的至少一个。
而且，另一个优点/特征是一种方法，其包括使用基于几何模型的分区模式来执行非穷尽性几何参数选择。所述执行步骤包括应用预测性搜索和分级搜索中的至少一个。所述预测性搜索包括初始预测因子选择、自适应早期终止和预测因子精化中的至少一个。
而且，另一个优点/特征是如上所述的方法，其中初始预测因子选择选择性地使能基于空间相关性的预测因子、基于时间相关性的预测因子、基于给定编码标准或者给定编码推荐的最佳帧间模式的预测因子、和固定的预测因子网格中的至少一个。
而且，另一个优点/特征是一种方法，包括使用基于几何模型的分区模式来对图像的视频信号数据进行编码。所述编码步骤使用用于图像的至少一部分的几何分区参数和预测数据的交替优化来编码视频信号数据。
基于此处的示教，相关领域内的普通技术人员可以容易地确定本原理的这些和其它特征和优点。将会理解，本原理的示教能够以硬件、软件、固件、专用处理器、或者它们的组合的各种形式来实现。
更优选地，本原理的示教被实现为硬件和软件的组合。而且，所述软件可被实现为程序存储单元上有形地具化的应用程序。所述应用程序可被上传到包括任意合适架构的机器、并由其执行。优选地，所述机器被实现于计算机平台上，该计算机平台具有诸如一个或多个中央处理单元(“CPU”)、随机存取存储器(“RAM”)、和输入/输出(“I/O”)接口之类的硬件。所述计算机平台也可以包括操作系统和微指令代码。此处描述的各种各样的处理和功能可以是微指令代码的一部分或者应用程序的一部分，或者它们的任意组合，它们可以通过CPU来执行。另外，各种其它外围单元可以连接到计算机平台，例如附加的数据存储单元和打印单元。
进一步理解，因为附图中描绘的一些构成的系统组件和方法优选地以软件来实现，因此系统组件之间的实际连接或者处理功能块可以根据本原理被编程的方式而有所不同。给出此处的示教，相关领域内的普通技术人员将能够预料本原理的这些和类似实现方式或配置。
尽管此处已经参考附图描述了说明性的实施例，但是将会理解，本原理不限于这些精确的实施例，并且相关领域内的普通技术人员可以在其中实现各种变化和修改，而不背离本原理的范畴或精神。所有这些变化和修改意欲包含在如所附权利要求中阐述的本原理的范畴之内。
相关申请的交叉引用
本申请要求于2007年4月12日提交的美国临时申请序列号第60/911,486的权益，在此并入其全部内容作为参考。