一种基于四面体网格的视频矢量化方法
一种基于四面体网格的视频矢量化方法
【技术领域】
[0001] 本发明属于计算机图形学、多媒体信息技术、视频处理等领域，涉及一种基于四面 体网格的视频矢量化方法。
【背景技术】
[0002] 基于矢量的图形内容越来越多的呈现于智能手机、电脑与网络上。而在人们随时 随地获取信息的推动下，各种各样的电子设备层出不穷，例如手机、平板电脑、笔记本电脑 等。这些设备的显示分辨率大小不一，传统视频有着既定的分辨率，在这些设备上显示往往 需要进行有损的缩放操作。而矢量图形则有着分辨率无关的特性，无论如何缩放都是无损 的，很好的解决了这样的问题。
[0003] 另一方面，随着科学技术的高速发展以及信息量的急速膨胀，个人电子设备的存 储越发不能满足人们的需求，人们需要通过不断从网络上获取信息的方式来满足自身的需 求，而矢量图形所具有的数据紧凑性能够很好的满足高效网络通信这一需求。
[0004] 网络素材的广泛需求推动着网络素材的制作，传统的美工制作过程会消耗大量的 人力成本与时间成本，而矢量图形的可编辑性更高，可以节省许多人力成本。
[0005] 在矢量图形的众多优点基础下，其发展趋势不言而喻，网络上已经有大量的由手 工创作的矢量图形，同时图像矢量化方法也得到了一定的发展，出现了基于三角形网格的 图像矢量化方法、基于梯度网格的图像矢量化方法、基于扩散曲线的图像矢量化方法等一 系列方法。
[0006] 然而对于传统的视频来说，单纯依靠手工设计将它们转化为矢量图形并不现实， 并且视频对时空一致性的需求使得图像矢量化的方法并不能很好的应用于视频。因此需要 一种能够自动将视频转化为矢量图形的方法，专利200810102127. 9,彩色光栅图像或视频 的矢量化方法可以对卡通视频进行矢量化，也是一种视频矢量化的方法，但是不能应用于 一般的自然视频。
【发明内容】
[0007] 发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种视频矢 量化方法，从而能够将传统的点阵视频转化为矢量视频。
[0008] 技术方案：本发明公开了一种基于四面体网格的视频矢量化方法，其核心在于计 算出原始输入视频的四面体网格模型并进行简化与优化，包括以下步骤：
[0009] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0010] 步骤2,建立初始四面体网格：将视频的每一个像素作为顶点，建立一个初始四面 体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0011] 步骤3,分割初始四面体网格：对初始四面体网格中四面体进行分割，使得每一个 四面体的四个顶点都具有同样的标号；
[0012] 步骤4,简化初始四面体网格：使用基于边坍缩的四面体简化方法，对初始四面体 网格进行简化细分，得到细分后的控制网格；
[0013] 步骤5,对控制网格进行颜色优化：对原始输入视频进行采样，用采样得到的结果 对控制网格进行颜色优化；
[0014] 步骤6,渲染控制网格：把颜色优化后的控制网格细分至1至3次以适合目标分辨 率，然后进行渲染。
[0015] 其中，步骤1包括以下步骤：
[0016] 步骤1-1，使用视频过分割方法，将原始输入视频分割为若干块（任意自然数）超 像素，原始输入视频的每个超像素都得到一个唯一的标号，将此标号赋予所有属于该超像 素的像素，分割后的超像素包含的每一个像素都拥有原始输入视频的红、绿、蓝颜色属性 (r，g，b)以及新的标号属性L。
[0017] 步骤2包括以下步骤：
[0018] 步骤2-1，根据原始输入视频每一个像素建立一个顶点，顶点属性包括像素的位置 信息（x，y，z)，颜色属性（r，g，b)以及标号属性L;
[0019] 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay(德劳内）四面体化方法（参 考文章DeWall:AfastdivideandconquerDelaunaytriangulationalgorithminEd) 在8个顶点组成的正方体之间建立6个四面体，得到一个初始四面体网格。
[0020] 步骤3包括以下步骤：
[0021] 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则 在该边中心新增一个顶点，该顶点的标号为该边两个顶点标号的并集；
[0022] 步骤3-2，检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标 号均不相同，则在三角形中心新增一个顶点，该顶点的标号为该三角形三个顶点标号的并 集；
[0023] 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号 均不相同，则在该四面体的体中心新增一个顶点，该顶点标号为该四面体四个顶点标号的 并集；
[0024] 步骤3-4，使用LatticeCleaving(晶格切割）算法（参考文章Lattice Cleaving:ConformingTetrahedralMeshesofMultimaterialDomainswithBounded Quality)，根据新增的顶点对四面体网格进行切割产生四面体内部网格边界，得到一个新 的四面体网格。
[0025] 步骤4包括以下步骤：
[0026] 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具 体过程如下：
[0027] 对于四面体网格中的每一个顶点点V，其坐标表示为四维向量[x，y，z，c]T，其中X、 y、z为该顶点v在原始输入视频中的坐标，c为其颜色值。令四面体的四个顶点分别为四维 向里Vi、V。、V3、V4，四会隹向里V^2V2Vi'VigV3Vi、Vi4V^ ?nCiTOSS(V12，V13，V14) '
[0028] 其中Cross(v12,v13,v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于 V12、V13、V14的四维向量，令n1、n2、n3、n4表示n的四个元素，即n=[n1，n2,n3,nJ。
[0029] 令d=-Dot(n,Vi)，其中Dot(n,v)表示n与乂丨的点积。
[0030] 则四面体T的超平面方程系数向量h= [ni，n2,n3,n4,d]，即四面体T所在超平面 n1x+n2y+n3z+n4c+d=0〇
[0031] 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式v= [X，y,z,c, 1]T，计算其Q矩阵及其二次误差A(v):
[0032] Q=heH(v)hh，
[0033] A(v) =EhGH(v) (hTv)2=vtQv,
[0034] 其中H(v)为顶点v所连接的所有四面体的集合；
[0035] 步骤4-3，计算四面体网格中每一条边eij的坍缩最优位置v#与坍缩代价 Cost(\)，坍缩最优位置/通过求解以下优化方程得出：
[0037] 其中％与Q」分别为边eu两个顶点v占v」的Q矩阵，令：
[0039] 其中qn~q55均为Qu的元素，令：
[0042] 则坍缩最优位置/=A^
[0043] i丹缩代价Cost(ey计算如下：
[0044] Cost(eiJ) =v*T (Qj+Qj)v*；
[0045] 步骤4-4,为保持因步骤3-4中对四面体进行切割而产生的内部网格边界，将一端 在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所有的边依照其坍缩代 价Cost进行排序，对坍缩代价Cost最小的边进行坍缩操作，将坍缩成的顶点设置到其最 优位置上/，合并的两个顶点的拓扑连接，重复进行本步骤，直至剩余顶点数达到预先 设定数量（任意自然数）或者没有符合条件的边可供坍缩为止，从而得到坍缩后的控制网 格；
[0046] 步骤4-5,对i丹缩后的控制网格进行细分（参考文章Anewsolidsubdivision schemebasedonboxsplines)，然后通过求解以下优化方程，对控制网格进行优化：
[0047]minvE(v) =EF (v) + 入EL (v)，
[0050] 其中EF(v)与分别为误差能量项与拉普拉斯能量项，参数A(任意实数）用 以调节它们之间的权重，在EF (v)的定义中，vk为控制网格细分后的顶点，4为vk在初始网 格上的投影，4在初始网格上，vk在细分后的控制网格上4是vk的优化目标。这里是使用 控制网格的细分网格把控制网格优化得更相似于初始网格，被优化的是控制网格。Ns为控 制网格细分后的顶点数目，k取值1~Ns，ak表示控制网格中的顶点与细分网格中的顶点 的线性组合关系，在Ejv)的定义中，Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。为 控制网格的顶点数目，
表示求解使得E(v)最小的V，该优化问题可以通过最小二 乘法求解。。
[0051] 步骤5包括：使用细分后的控制网格对原始输入视频进行采样，求解以下优化方 程以优化控制网格的顶点颜色：
[0052] 其中，
：表示求解使得E(c)最小的颜色值c，ck为控制网格细分后的顶点 颜色，|| * ||i:表示2范数的平方，即欧氏距离的平方，为Ck在原始输入视频上采样的颜 色，该优化问题可以通过最小二乘法求解。
[0053] 步骤6包括：将颜色优化后的控制 网格细分至适应于目标分辨率的密度，然后将 其缩放至目标分辨率后渲染成视频，视频中每个像素点的颜色值通过对其所属四面体的四 个顶点的颜色值进行三线性插值（参考书籍：GraphicsGemsIV)得到。
[0054] 有益效果：本发明的显著优点是：
[0055] (1)本发明提出的视频矢量化的方法具有高度的自动性，整个矢量化过程中无需 用户进行手动交互。
[0056] (2)本发明使用的四面体矢量模型在几何处理中具有一般性，由本发明所得到的 矢量视频模型可以使用一般的四面体处理方法进行编辑。
[0057] (3)本发明得到的四面体矢量模型具有保真性，将其重新渲染成视频后与原始输 入视频误差较小。
【附图说明】
[0058] 图1为本发明方法的基本流程图。
[0059] 图2为均匀切割立方体示意图。
[0060] 图3为多标号的四面体示意图。
[0061] 图4为Cleaver算法切割模板示意图。
[0062] 图5为原始输入视频的若干帧。
[0063] 图6为矢量视频植染出的若干帧。
【具体实施方式】
[0064] 下面结合附图和【具体实施方式】对本发明做更进一步的具体说明。
[0065] 本方法的流程图如图1所示，分为六大过程：首先是使用视频过分割方法对视频 进行过分割；然后是依照视频过分割的结果建立初始四面体网格；然后是使用Cleaver算 法对初始四面体网格进行切割；然后是使用基于边坍缩的四面体简化方法对四面体网格进 行简化；然后是通过求解优化方程对四面体网格进行颜色优化；最后是对四面体网格进行 渲染。
[0066] 具体地说，如图1所示，本发明公开了一种视频矢量化方法，主要包括以下几个步 骤：
[0067] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0068] 步骤2,建立初始四面体网格：将视频的每一个像素点作为顶点，建立一个稠密的 初始四面体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0069] 步骤3,分割初始四面体网格：对网格中四面体进行分割，使得每一个四面体的四 个顶点都具有同样的标号。
[0070] 步骤4,四面体网格的简化：使用基于边坍缩的四面体简化方法，对稠密的四面体 网格进行简化，在尽量不影响其形状的前提下减少四面体的个数，得到稀疏的控制网格。
[0071] 步骤5,四面体网格的颜色优化：将简化后的稀疏的控制网格细分，然后原始输入 视频中进行采样，用采样得到的结果对稀疏的控制网格进行颜色优化。
[0072] 步骤6,四面体网格的渲染：把颜色优化后的控制网格细分1至3次以适合目标分 辨率，然后进行渲染。
[0073] 对于步骤1，视频过分割的具体实施细节如下步骤：
[0074] 步骤1-1，使用视频过分割方法，将视频分割为若干块超像素。视频的每个超像素 都将得到一个唯一的标号，并将此标号赋予所有属于该超像素的像素，从而视频的每一个 像素都拥有原本的红、绿、蓝颜色属性（r，g，b)以及新的标号属性L。
[0075] 对于步骤2,建立初始四面体网格的具体实施细节如下步骤：
[0076] 步骤2-1，根据视频每一个像素点建立一个顶点，其属性有包括位置信息（x，y， z)，颜色属性（r，g，b)以及标号属性L。
[0077] 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay(德劳内）四面体化方法（参 考文章DeWall:AfastdivideandconquerDelaunaytriangulationalgorithminEd) 在其间建立起6个四面体，如图2所示，从而得到一个稠密的初始四面体网格。
[0078] 对于步骤3,切割四面体网格的具体实施细节如下步骤：
[0079] 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则 在该边中心新增一个顶点，其标号为该边两个顶点标号的并集，如图3中（a)和图3中（b) 所示。
[0080] 步骤3-2,检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标号 均不相同，则在三角形中心新增一个顶点，其标号为该三角形三个顶点标号的并集，如图3 中（c)所示。
[0081] 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号 均不相同，则在该边中间新增一个顶点，其标号为该四面体四个顶点标号的并集，如图3中 (d)所示。
[0082] 步骤3-4，使用LatticeCleaving(晶格切割）算法（参考文章Lattice Cleaving:ConformingTetrahedralMeshesofMultimaterialDomainswithBounded Quality)，根据新增的顶点对四面体网格进行切割产生四面体内部网格边界，切割模板如 图4所示，从而得到一个新的更为稠密的四面体网格。
[0083] 对于步骤4,四面体网格简化的具体实施细节如下步骤：
[0084] 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具 体过程如下：
[0085] 对于顶点V，其坐标表示为四维向量[X，y,z,c]T，其中x、y、z为该顶点v在原始输 入视频中的坐标，c为其颜色值。
[0086] 令四面体的四个顶点分别为四维向量v2、v3、v4，令四维向量v12=v2、、v13 = v3_Vi、v14=v「Vpn=Cross(v12,v13,v14),
[0087] 其中Cross(v12,v13,v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于 V12、V13、V14的四维向量，令n 1、n2、n3、n4表示n的四个元素，即n=[n 1，n2, ％，nJ。
[0088] 令d=-Dot(n,v)，其中Dot(n,v)表示n与乂丨的点积。
[0089] 则四面体T的超平面方程系数向量h= [ni，n2,n3,n4,d]，即四面体T所在超平面 n1x+n2y+n3z+n4c+d= 0〇
[0090] 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式v= [X，y,z,c, 1]T，计算其Q矩阵及其二次误差A(v):
[0091] Q=SheH(v)hThj
[0092] A(v) =EhGH(v) (hTv)2=vtQv,
[0093] 其中H(v)为顶点v所连接的所有四面体的集合；
[0094] 步骤4-3,计算四面体网格中每一条边\的坍缩最优位置^与坍缩代价 Cost(\)，坍缩最优位置/通过求解以下优化方程得出：
[0095] minvvT (Qi+Qj)V，
[0096] 其中％与Q」分别为边eu两个顶点v占v」的Q矩阵，令：
[0098] 其中qn~q55均为Qu的元素，令：
[0101] 则坍缩最优位置v*=A
[0102] i丹缩代价Cost(eij)计算如下：
[0103] Cost(eij) =v*T(Qi+Qj)v*；
[0104]步骤4-4,为需要保持因步骤3-4中对四面体进行切割而产生的内部网格边界， 将一端在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所有的边依照其Cost进行排序，对Cost最小的边进行坍缩操作，将坍缩成的顶点设置到其最优位置/上， 合并\的两个顶点的拓扑连接。重复进行此步骤，直至剩余顶点数达到用户预先设定数量 (任意自然数）或者没有符合条件的边可供坍缩为止，从而得到控制网格。
[0105] 步骤4-5,对i丹缩后的控制网格进行细分（参考文章Anewsolidsubdivision schemebasedonboxsplines)，然后通过求解以下优化方程，对控制网格进行优化，使得 其形状更接近于初始网格：
[0106]minvE(v) =EF (v) + 入EL (v)，
[0109] 其中EF(v)与分别为误差能量项与拉普拉斯能量项，参数A(取值任意实 数，A由用户调节以便得到其理想的结果）用以调节它们之间的权重。在EF(v)的定义中， vk为控制网格细分后的顶点，4为vk在初始网格上的投影，Ns为控制网格细分后的顶点数 目，ak表达了控制网格中的顶点与细分网格中的顶点的线性组合关系。在Ejv)的定义中， Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。为控制网格的顶点数目，mjWO)表示求 解使得E(v)最小的V，该优化问题可以通过最小二乘法求解。
[0110] 对于步骤5,四面体网格颜色优化的具体实施细节如下：
[0111] 对控制网格进行细分，使用细分网格对原始输入视频进行采样，随后求解以下优 化方程以优化控制网格的顶点颜色：
[0113] ck为控制网格细分后的顶点颜色，C〖为Ck在原始输入视频上采样的颜色，Ns为控 制网格细分后的顶点数目，ak表达了控制网格中的顶点与细分网格中的顶点的线性组合 关系，该优化问题可以通过最小二乘法求解。
[0114] 对于步骤6,四面体网格渲染的具体实施细节如下：
[0115] 将四面体控制网格细分至适应于目标分辨率的密度，然后将其缩放至目标分辨率 后渲染成视频，视频中每个像素点的颜色值通 过对其所属四面体的四个顶点的颜色值进行 三线性插值（参考书籍：GraphicsGemsIV)得到。
[0116] 实施例
[0117] 本实施例的实验硬件环境是：Intel(R)Xero(R)CPUE5-2620 2.0GHz，144G内存， 软件环境是MicrosoftVisualStudio2010、MicrosoftWindows7Professional和Matlab 2012a。测试视频来自于网络上公开的视频。
[0118] 本发明公开了一种基于四面体网格的视频矢量化方法，其核心在于计算出原始输 入视频的四面体网格模型并进行简化与优化，包括以下步骤：
[0119] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0120]步骤2,建立初始四面体网格：将视频的每一个像素点作为顶点，建立一个初始四 面体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0121] 步骤3,分割初始四面体网格：对网格中四面体进行分割，使得每一个四面体的四 个顶点都具有同样的标号；
[0122] 步骤4,简化四面体网格：使用基于边坍缩的四面体简化方法，对四面体网格进行 简化，得到控制网格；
[0123] 步骤5,对控制网格进行颜色优化：将控制网格细分，然后对原始输入视频进行采 样，用采样得到的结果对控制网格进行颜色优化；
[0124] 步骤6,渲染控制网格：把颜色优化后的控制网格细分1至3次以适合目标分辨 率，然后进行渲染。
[0125] 输入的测试视频如图5所示，在使用对视频进行过分割时将超像素数目控制在 100~200之间，在四面体网格简化过程中拉普拉斯项的权重X取值在〇. 1~〇. 〇1之间， 简化后的控制网格顶点数设置为该视频像素数的〇. 5%，四面体网格的渲染结果如图6所 示，可以看出矢量化后的视频基本保持了原始输入视频中物体的形状等显著特征。
[0126] 本发明提供了一种基于四面体网格的视频矢量化方法，具体实现该技术方案的方 法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技 术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰 也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。
【主权项】
1. 一种基于四面体网格的视频矢量化方法，其特征在于，包括以下步骤： 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并为每 一个超像素标记标号，并将此标号赋予所有属于该超像素的像素； 步骤2,建立初始四面体网格：将视频的每一个像素作为顶点，建立一个初始四面体网 格，将每个像素的对应颜色以及标号赋予其对应的顶点； 步骤3,分割初始四面体网格：对初始四面体网格中四面体进行分割，使得每一个四面 体的四个顶点都具有同样的标号； 步骤4,简化初始四面体网格：使用基于边坍缩的四面体简化方法，对初始四面体网格 进行简化细分，得到细分后的控制网格； 步骤5,对控制网格进行颜色优化：对原始输入视频进行采样，用采样得到的结果对控 制网格进行颜色优化； 步骤6,渲染控制网格：把颜色优化后的控制网格细分1至3次以适合目标分辨率，然 后进行渲染。2. 如权利要求1所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤1包 括以下步骤： 步骤1-1，使用视频过分割方法，将原始输入视频分割为若干块超像素，原始输入视频 的每个超像素都得到一个唯一的标号，将此标号赋予所有属于该超像素的像素，分割后的 超像素包含的每一个像素都拥有原始输入视频的红、绿、蓝颜色属性（r，g，b)以及新的标 号属性L。3. 如权利要求2所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤2包 括以下步骤： 步骤2-1，根据原始输入视频每一个像素建立一个顶点，顶点属性包括像素的位置信息 (X，y，z)，颜色属性（r，g，b)以及标号属性L ; 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay四面体化方法在8个顶点组成的 正方体之间建立6个四面体，得到一个初始四面体网格。4. 如权利要求3所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤3包 括以下步骤： 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则在该 边中心新增一个顶点，该顶点的标号为该边两个顶点标号的并集； 步骤3-2,检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标号均不 相同，则在三角形中心新增一个顶点，该顶点的标号为该三角形三个顶点标号的并集； 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号均 不相同，则在该四面体的体中心新增一个顶点，该顶点标号为该四面体四个顶点标号的并 集； 步骤3-4,使用Lattice Cleaving算法，根据新增的顶点对四面体网格进行切割产生 四面体内部网格边界，得到一个新的四面体网格。5. 如权利要求4所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤4包 括以下步骤： 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具体过 程如下： 对于四面体网格中的每一个顶点V，其坐标表示为四维向量[X，y，z，c]T，其中X、y、Z 为该顶点v在原始输入视频中的坐标，c为其颜色值， 令四面体T的四个顶点分别为四维向量Vp V2、V3、V4，令四维向量V12= V fVp V13 = V3-V0 V14= V n = Cross (v12, v13, v14), 其中Cross (v12, v13, v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于v 12、 v13、Vi4的四维向量，令η p n2、n3、n4表示η的四个元素，即η = [η p n2, n3, n4]。， 令参数d = -Dot (n，V1)，其中Dot (n，V1)表示n与￥丨的点积， 则四面体T的超平面方程系数向量h = [ni，n2, n3, n4, d]，即四面体T所在超平面方程 % n1x+n2y+n3z+n4c+d = 0 ； 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式V = [X，y，z， c，l]T，计算其Q矩阵及其二次误差Λ(ν): Q - Σ h e H(v)h h， Δ (ν) =Σ heH(v) (hTv)2= VtQv, 其中H(v)为顶点V所连接的所有四面体的集合； 步骤4-3,计算四面体网格中每一条边\的坍缩最优位置ν#与坍缩代价Cost (e y，坍 缩最优位置/通过求解以下优化方程得出： minvvT (Q^Qi) ν, 其中仏与L分别为边e ^两个顶点ν占 的Q矩阵，令：其中qn~q 55均为Q u的元素，令：则坍缩最优位置/=A，Bq， 缩代价CosUeij)计算如下： Cost(Gij) = v*T( Q ^QjOv*; 步骤4-4,将一端在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所 有的边依照其坍缩代价进行排序，对坍缩代价最小的边进行坍缩操作，将坍缩成的顶点设 置到其最优位置/上，合并边e u的两个顶点的拓扑连接，重复进行本步骤，直至剩余顶点 数达到预先设定数量或者没有符合条件的边可供坍缩为止，从而得到坍缩后的控制网格； 步骤4-5,对坍缩后的控制网格进行细分，通过求解以下优化方程，对控制网格进行优 化：其中Ef(V)与EJv)分别为误差能量项与拉普拉斯能量项，参数λ用以调节它们之间 的权重，在Ef(V)的定义中，Vk为控制网格细分后的顶点，#为Vk在初始网格上的投影，N s为控制网格细分后的顶点数目，k取值1~Ns，a k表示控制网格中的顶点与细分网格中的 顶点的线性组合关系，在EJv)的定义中，Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。 为控制网格的顶点数目，mvin表示求解使得E(V)最小的V。6. 如权利要求5所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤5包 括：使用细分后的控制网格对原始输入视频进行采样，求解以下优化方程以优化控制网格 的顶点颜色：其中，mjnEO)表示求解使得E(c)最小的颜色值c，Ck为控制网格细分后的顶点颜色， 4为Ck在原始输入视频上采样的颜色。7. 如权利要求6所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤6包 括：将颜色优化后的控制网格细分至适应于目标分辨率的密度，然后将其缩放至目标分辨 率后渲染成视频，视频中每个像素点的颜色值通过对其所属四面体的四个顶点的颜色值进 行三线性插值得到。
【专利摘要】本发明公开了一种基于四面体网格的视频矢量化方法，包括使用视频过分割方法对视频进行过分割；依照视频过分割的结果建立初始四面体网格；使用Lattice Cleaving算法对初始四面体网格进行切割；使用基于边坍缩的四面体简化方法对四面体网格进行简化；通过求解优化方程对四面体网格进行颜色优化；最后是对四面体网格进行渲染。本发明在将视频矢量化为四面体网格模型的同时尽量保持了视频中物体的几何形状等特征，并且处理过程中无需用户进行交互操作。
【IPC分类】G06T7/00, G06T7/40
【公开号】CN104899889
【申请号】CN201510349260
【发明人】郭延文, 朱捷, 王氚, 王文平
【申请人】南京大学
【公开日】2015年9月9日
【申请日】2015年6月23日
【技术领域】
[0001] 本发明属于计算机图形学、多媒体信息技术、视频处理等领域，涉及一种基于四面 体网格的视频矢量化方法。
【背景技术】
[0002] 基于矢量的图形内容越来越多的呈现于智能手机、电脑与网络上。而在人们随时 随地获取信息的推动下，各种各样的电子设备层出不穷，例如手机、平板电脑、笔记本电脑 等。这些设备的显示分辨率大小不一，传统视频有着既定的分辨率，在这些设备上显示往往 需要进行有损的缩放操作。而矢量图形则有着分辨率无关的特性，无论如何缩放都是无损 的，很好的解决了这样的问题。
[0003] 另一方面，随着科学技术的高速发展以及信息量的急速膨胀，个人电子设备的存 储越发不能满足人们的需求，人们需要通过不断从网络上获取信息的方式来满足自身的需 求，而矢量图形所具有的数据紧凑性能够很好的满足高效网络通信这一需求。
[0004] 网络素材的广泛需求推动着网络素材的制作，传统的美工制作过程会消耗大量的 人力成本与时间成本，而矢量图形的可编辑性更高，可以节省许多人力成本。
[0005] 在矢量图形的众多优点基础下，其发展趋势不言而喻，网络上已经有大量的由手 工创作的矢量图形，同时图像矢量化方法也得到了一定的发展，出现了基于三角形网格的 图像矢量化方法、基于梯度网格的图像矢量化方法、基于扩散曲线的图像矢量化方法等一 系列方法。
[0006] 然而对于传统的视频来说，单纯依靠手工设计将它们转化为矢量图形并不现实， 并且视频对时空一致性的需求使得图像矢量化的方法并不能很好的应用于视频。因此需要 一种能够自动将视频转化为矢量图形的方法，专利200810102127. 9,彩色光栅图像或视频 的矢量化方法可以对卡通视频进行矢量化，也是一种视频矢量化的方法，但是不能应用于 一般的自然视频。
【发明内容】
[0007] 发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种视频矢 量化方法，从而能够将传统的点阵视频转化为矢量视频。
[0008] 技术方案：本发明公开了一种基于四面体网格的视频矢量化方法，其核心在于计 算出原始输入视频的四面体网格模型并进行简化与优化，包括以下步骤：
[0009] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0010] 步骤2,建立初始四面体网格：将视频的每一个像素作为顶点，建立一个初始四面 体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0011] 步骤3,分割初始四面体网格：对初始四面体网格中四面体进行分割，使得每一个 四面体的四个顶点都具有同样的标号；
[0012] 步骤4,简化初始四面体网格：使用基于边坍缩的四面体简化方法，对初始四面体 网格进行简化细分，得到细分后的控制网格；
[0013] 步骤5,对控制网格进行颜色优化：对原始输入视频进行采样，用采样得到的结果 对控制网格进行颜色优化；
[0014] 步骤6,渲染控制网格：把颜色优化后的控制网格细分至1至3次以适合目标分辨 率，然后进行渲染。
[0015] 其中，步骤1包括以下步骤：
[0016] 步骤1-1，使用视频过分割方法，将原始输入视频分割为若干块（任意自然数）超 像素，原始输入视频的每个超像素都得到一个唯一的标号，将此标号赋予所有属于该超像 素的像素，分割后的超像素包含的每一个像素都拥有原始输入视频的红、绿、蓝颜色属性 (r，g，b)以及新的标号属性L。
[0017] 步骤2包括以下步骤：
[0018] 步骤2-1，根据原始输入视频每一个像素建立一个顶点，顶点属性包括像素的位置 信息（x，y，z)，颜色属性（r，g，b)以及标号属性L;
[0019] 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay(德劳内）四面体化方法（参 考文章DeWall:AfastdivideandconquerDelaunaytriangulationalgorithminEd) 在8个顶点组成的正方体之间建立6个四面体，得到一个初始四面体网格。
[0020] 步骤3包括以下步骤：
[0021] 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则 在该边中心新增一个顶点，该顶点的标号为该边两个顶点标号的并集；
[0022] 步骤3-2，检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标 号均不相同，则在三角形中心新增一个顶点，该顶点的标号为该三角形三个顶点标号的并 集；
[0023] 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号 均不相同，则在该四面体的体中心新增一个顶点，该顶点标号为该四面体四个顶点标号的 并集；
[0024] 步骤3-4，使用LatticeCleaving(晶格切割）算法（参考文章Lattice Cleaving:ConformingTetrahedralMeshesofMultimaterialDomainswithBounded Quality)，根据新增的顶点对四面体网格进行切割产生四面体内部网格边界，得到一个新 的四面体网格。
[0025] 步骤4包括以下步骤：
[0026] 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具 体过程如下：
[0027] 对于四面体网格中的每一个顶点点V，其坐标表示为四维向量[x，y，z，c]T，其中X、 y、z为该顶点v在原始输入视频中的坐标，c为其颜色值。令四面体的四个顶点分别为四维 向里Vi、V。、V3、V4，四会隹向里V^2V2Vi'VigV3Vi、Vi4V^ ?nCiTOSS(V12，V13，V14) '
[0028] 其中Cross(v12,v13,v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于 V12、V13、V14的四维向量，令n1、n2、n3、n4表示n的四个元素，即n=[n1，n2,n3,nJ。
[0029] 令d=-Dot(n,Vi)，其中Dot(n,v)表示n与乂丨的点积。
[0030] 则四面体T的超平面方程系数向量h= [ni，n2,n3,n4,d]，即四面体T所在超平面 n1x+n2y+n3z+n4c+d=0〇
[0031] 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式v= [X，y,z,c, 1]T，计算其Q矩阵及其二次误差A(v):
[0032] Q=heH(v)hh，
[0033] A(v) =EhGH(v) (hTv)2=vtQv,
[0034] 其中H(v)为顶点v所连接的所有四面体的集合；
[0035] 步骤4-3，计算四面体网格中每一条边eij的坍缩最优位置v#与坍缩代价 Cost(\)，坍缩最优位置/通过求解以下优化方程得出：
[0037] 其中％与Q」分别为边eu两个顶点v占v」的Q矩阵，令：
[0039] 其中qn~q55均为Qu的元素，令：
[0042] 则坍缩最优位置/=A^
[0043] i丹缩代价Cost(ey计算如下：
[0044] Cost(eiJ) =v*T (Qj+Qj)v*；
[0045] 步骤4-4,为保持因步骤3-4中对四面体进行切割而产生的内部网格边界，将一端 在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所有的边依照其坍缩代 价Cost进行排序，对坍缩代价Cost最小的边进行坍缩操作，将坍缩成的顶点设置到其最 优位置上/，合并的两个顶点的拓扑连接，重复进行本步骤，直至剩余顶点数达到预先 设定数量（任意自然数）或者没有符合条件的边可供坍缩为止，从而得到坍缩后的控制网 格；
[0046] 步骤4-5,对i丹缩后的控制网格进行细分（参考文章Anewsolidsubdivision schemebasedonboxsplines)，然后通过求解以下优化方程，对控制网格进行优化：
[0047]minvE(v) =EF (v) + 入EL (v)，
[0050] 其中EF(v)与分别为误差能量项与拉普拉斯能量项，参数A(任意实数）用 以调节它们之间的权重，在EF (v)的定义中，vk为控制网格细分后的顶点，4为vk在初始网 格上的投影，4在初始网格上，vk在细分后的控制网格上4是vk的优化目标。这里是使用 控制网格的细分网格把控制网格优化得更相似于初始网格，被优化的是控制网格。Ns为控 制网格细分后的顶点数目，k取值1~Ns，ak表示控制网格中的顶点与细分网格中的顶点 的线性组合关系，在Ejv)的定义中，Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。为 控制网格的顶点数目，
表示求解使得E(v)最小的V，该优化问题可以通过最小二 乘法求解。。
[0051] 步骤5包括：使用细分后的控制网格对原始输入视频进行采样，求解以下优化方 程以优化控制网格的顶点颜色：
[0052] 其中，
：表示求解使得E(c)最小的颜色值c，ck为控制网格细分后的顶点 颜色，|| * ||i:表示2范数的平方，即欧氏距离的平方，为Ck在原始输入视频上采样的颜 色，该优化问题可以通过最小二乘法求解。
[0053] 步骤6包括：将颜色优化后的控制 网格细分至适应于目标分辨率的密度，然后将 其缩放至目标分辨率后渲染成视频，视频中每个像素点的颜色值通过对其所属四面体的四 个顶点的颜色值进行三线性插值（参考书籍：GraphicsGemsIV)得到。
[0054] 有益效果：本发明的显著优点是：
[0055] (1)本发明提出的视频矢量化的方法具有高度的自动性，整个矢量化过程中无需 用户进行手动交互。
[0056] (2)本发明使用的四面体矢量模型在几何处理中具有一般性，由本发明所得到的 矢量视频模型可以使用一般的四面体处理方法进行编辑。
[0057] (3)本发明得到的四面体矢量模型具有保真性，将其重新渲染成视频后与原始输 入视频误差较小。
【附图说明】
[0058] 图1为本发明方法的基本流程图。
[0059] 图2为均匀切割立方体示意图。
[0060] 图3为多标号的四面体示意图。
[0061] 图4为Cleaver算法切割模板示意图。
[0062] 图5为原始输入视频的若干帧。
[0063] 图6为矢量视频植染出的若干帧。
【具体实施方式】
[0064] 下面结合附图和【具体实施方式】对本发明做更进一步的具体说明。
[0065] 本方法的流程图如图1所示，分为六大过程：首先是使用视频过分割方法对视频 进行过分割；然后是依照视频过分割的结果建立初始四面体网格；然后是使用Cleaver算 法对初始四面体网格进行切割；然后是使用基于边坍缩的四面体简化方法对四面体网格进 行简化；然后是通过求解优化方程对四面体网格进行颜色优化；最后是对四面体网格进行 渲染。
[0066] 具体地说，如图1所示，本发明公开了一种视频矢量化方法，主要包括以下几个步 骤：
[0067] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0068] 步骤2,建立初始四面体网格：将视频的每一个像素点作为顶点，建立一个稠密的 初始四面体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0069] 步骤3,分割初始四面体网格：对网格中四面体进行分割，使得每一个四面体的四 个顶点都具有同样的标号。
[0070] 步骤4,四面体网格的简化：使用基于边坍缩的四面体简化方法，对稠密的四面体 网格进行简化，在尽量不影响其形状的前提下减少四面体的个数，得到稀疏的控制网格。
[0071] 步骤5,四面体网格的颜色优化：将简化后的稀疏的控制网格细分，然后原始输入 视频中进行采样，用采样得到的结果对稀疏的控制网格进行颜色优化。
[0072] 步骤6,四面体网格的渲染：把颜色优化后的控制网格细分1至3次以适合目标分 辨率，然后进行渲染。
[0073] 对于步骤1，视频过分割的具体实施细节如下步骤：
[0074] 步骤1-1，使用视频过分割方法，将视频分割为若干块超像素。视频的每个超像素 都将得到一个唯一的标号，并将此标号赋予所有属于该超像素的像素，从而视频的每一个 像素都拥有原本的红、绿、蓝颜色属性（r，g，b)以及新的标号属性L。
[0075] 对于步骤2,建立初始四面体网格的具体实施细节如下步骤：
[0076] 步骤2-1，根据视频每一个像素点建立一个顶点，其属性有包括位置信息（x，y， z)，颜色属性（r，g，b)以及标号属性L。
[0077] 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay(德劳内）四面体化方法（参 考文章DeWall:AfastdivideandconquerDelaunaytriangulationalgorithminEd) 在其间建立起6个四面体，如图2所示，从而得到一个稠密的初始四面体网格。
[0078] 对于步骤3,切割四面体网格的具体实施细节如下步骤：
[0079] 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则 在该边中心新增一个顶点，其标号为该边两个顶点标号的并集，如图3中（a)和图3中（b) 所示。
[0080] 步骤3-2,检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标号 均不相同，则在三角形中心新增一个顶点，其标号为该三角形三个顶点标号的并集，如图3 中（c)所示。
[0081] 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号 均不相同，则在该边中间新增一个顶点，其标号为该四面体四个顶点标号的并集，如图3中 (d)所示。
[0082] 步骤3-4，使用LatticeCleaving(晶格切割）算法（参考文章Lattice Cleaving:ConformingTetrahedralMeshesofMultimaterialDomainswithBounded Quality)，根据新增的顶点对四面体网格进行切割产生四面体内部网格边界，切割模板如 图4所示，从而得到一个新的更为稠密的四面体网格。
[0083] 对于步骤4,四面体网格简化的具体实施细节如下步骤：
[0084] 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具 体过程如下：
[0085] 对于顶点V，其坐标表示为四维向量[X，y,z,c]T，其中x、y、z为该顶点v在原始输 入视频中的坐标，c为其颜色值。
[0086] 令四面体的四个顶点分别为四维向量v2、v3、v4，令四维向量v12=v2、、v13 = v3_Vi、v14=v「Vpn=Cross(v12,v13,v14),
[0087] 其中Cross(v12,v13,v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于 V12、V13、V14的四维向量，令n 1、n2、n3、n4表示n的四个元素，即n=[n 1，n2, ％，nJ。
[0088] 令d=-Dot(n,v)，其中Dot(n,v)表示n与乂丨的点积。
[0089] 则四面体T的超平面方程系数向量h= [ni，n2,n3,n4,d]，即四面体T所在超平面 n1x+n2y+n3z+n4c+d= 0〇
[0090] 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式v= [X，y,z,c, 1]T，计算其Q矩阵及其二次误差A(v):
[0091] Q=SheH(v)hThj
[0092] A(v) =EhGH(v) (hTv)2=vtQv,
[0093] 其中H(v)为顶点v所连接的所有四面体的集合；
[0094] 步骤4-3,计算四面体网格中每一条边\的坍缩最优位置^与坍缩代价 Cost(\)，坍缩最优位置/通过求解以下优化方程得出：
[0095] minvvT (Qi+Qj)V，
[0096] 其中％与Q」分别为边eu两个顶点v占v」的Q矩阵，令：
[0098] 其中qn~q55均为Qu的元素，令：
[0101] 则坍缩最优位置v*=A
[0102] i丹缩代价Cost(eij)计算如下：
[0103] Cost(eij) =v*T(Qi+Qj)v*；
[0104]步骤4-4,为需要保持因步骤3-4中对四面体进行切割而产生的内部网格边界， 将一端在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所有的边依照其Cost进行排序，对Cost最小的边进行坍缩操作，将坍缩成的顶点设置到其最优位置/上， 合并\的两个顶点的拓扑连接。重复进行此步骤，直至剩余顶点数达到用户预先设定数量 (任意自然数）或者没有符合条件的边可供坍缩为止，从而得到控制网格。
[0105] 步骤4-5,对i丹缩后的控制网格进行细分（参考文章Anewsolidsubdivision schemebasedonboxsplines)，然后通过求解以下优化方程，对控制网格进行优化，使得 其形状更接近于初始网格：
[0106]minvE(v) =EF (v) + 入EL (v)，
[0109] 其中EF(v)与分别为误差能量项与拉普拉斯能量项，参数A(取值任意实 数，A由用户调节以便得到其理想的结果）用以调节它们之间的权重。在EF(v)的定义中， vk为控制网格细分后的顶点，4为vk在初始网格上的投影，Ns为控制网格细分后的顶点数 目，ak表达了控制网格中的顶点与细分网格中的顶点的线性组合关系。在Ejv)的定义中， Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。为控制网格的顶点数目，mjWO)表示求 解使得E(v)最小的V，该优化问题可以通过最小二乘法求解。
[0110] 对于步骤5,四面体网格颜色优化的具体实施细节如下：
[0111] 对控制网格进行细分，使用细分网格对原始输入视频进行采样，随后求解以下优 化方程以优化控制网格的顶点颜色：
[0113] ck为控制网格细分后的顶点颜色，C〖为Ck在原始输入视频上采样的颜色，Ns为控 制网格细分后的顶点数目，ak表达了控制网格中的顶点与细分网格中的顶点的线性组合 关系，该优化问题可以通过最小二乘法求解。
[0114] 对于步骤6,四面体网格渲染的具体实施细节如下：
[0115] 将四面体控制网格细分至适应于目标分辨率的密度，然后将其缩放至目标分辨率 后渲染成视频，视频中每个像素点的颜色值通 过对其所属四面体的四个顶点的颜色值进行 三线性插值（参考书籍：GraphicsGemsIV)得到。
[0116] 实施例
[0117] 本实施例的实验硬件环境是：Intel(R)Xero(R)CPUE5-2620 2.0GHz，144G内存， 软件环境是MicrosoftVisualStudio2010、MicrosoftWindows7Professional和Matlab 2012a。测试视频来自于网络上公开的视频。
[0118] 本发明公开了一种基于四面体网格的视频矢量化方法，其核心在于计算出原始输 入视频的四面体网格模型并进行简化与优化，包括以下步骤：
[0119] 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并 为每一个超像素标记标号，并将此标号赋予所有属于该超像素的像素；
[0120]步骤2,建立初始四面体网格：将视频的每一个像素点作为顶点，建立一个初始四 面体网格，将每个像素的对应颜色以及标号赋予其对应的顶点；
[0121] 步骤3,分割初始四面体网格：对网格中四面体进行分割，使得每一个四面体的四 个顶点都具有同样的标号；
[0122] 步骤4,简化四面体网格：使用基于边坍缩的四面体简化方法，对四面体网格进行 简化，得到控制网格；
[0123] 步骤5,对控制网格进行颜色优化：将控制网格细分，然后对原始输入视频进行采 样，用采样得到的结果对控制网格进行颜色优化；
[0124] 步骤6,渲染控制网格：把颜色优化后的控制网格细分1至3次以适合目标分辨 率，然后进行渲染。
[0125] 输入的测试视频如图5所示，在使用对视频进行过分割时将超像素数目控制在 100~200之间，在四面体网格简化过程中拉普拉斯项的权重X取值在〇. 1~〇. 〇1之间， 简化后的控制网格顶点数设置为该视频像素数的〇. 5%，四面体网格的渲染结果如图6所 示，可以看出矢量化后的视频基本保持了原始输入视频中物体的形状等显著特征。
[0126] 本发明提供了一种基于四面体网格的视频矢量化方法，具体实现该技术方案的方 法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技 术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰 也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。
【主权项】
1. 一种基于四面体网格的视频矢量化方法，其特征在于，包括以下步骤： 步骤1，视频过分割：使用视频过分割方法将原始输入视频过分割成为超像素，并为每 一个超像素标记标号，并将此标号赋予所有属于该超像素的像素； 步骤2,建立初始四面体网格：将视频的每一个像素作为顶点，建立一个初始四面体网 格，将每个像素的对应颜色以及标号赋予其对应的顶点； 步骤3,分割初始四面体网格：对初始四面体网格中四面体进行分割，使得每一个四面 体的四个顶点都具有同样的标号； 步骤4,简化初始四面体网格：使用基于边坍缩的四面体简化方法，对初始四面体网格 进行简化细分，得到细分后的控制网格； 步骤5,对控制网格进行颜色优化：对原始输入视频进行采样，用采样得到的结果对控 制网格进行颜色优化； 步骤6,渲染控制网格：把颜色优化后的控制网格细分1至3次以适合目标分辨率，然 后进行渲染。2. 如权利要求1所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤1包 括以下步骤： 步骤1-1，使用视频过分割方法，将原始输入视频分割为若干块超像素，原始输入视频 的每个超像素都得到一个唯一的标号，将此标号赋予所有属于该超像素的像素，分割后的 超像素包含的每一个像素都拥有原始输入视频的红、绿、蓝颜色属性（r，g，b)以及新的标 号属性L。3. 如权利要求2所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤2包 括以下步骤： 步骤2-1，根据原始输入视频每一个像素建立一个顶点，顶点属性包括像素的位置信息 (X，y，z)，颜色属性（r，g，b)以及标号属性L ; 步骤2-2,对于每8个直接相邻的顶点，使用Delaunay四面体化方法在8个顶点组成的 正方体之间建立6个四面体，得到一个初始四面体网格。4. 如权利要求3所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤3包 括以下步骤： 步骤3-1，检查初始四面体网格中的所有边，如果一条边的两个顶点标号不同，则在该 边中心新增一个顶点，该顶点的标号为该边两个顶点标号的并集； 步骤3-2,检查初始四面体网格中的所有三角形，如果一个三角形的三个顶点标号均不 相同，则在三角形中心新增一个顶点，该顶点的标号为该三角形三个顶点标号的并集； 步骤3-3,检查初始四面体网格中的所有四面体，如果一个四面体的四个顶点标号均 不相同，则在该四面体的体中心新增一个顶点，该顶点标号为该四面体四个顶点标号的并 集； 步骤3-4,使用Lattice Cleaving算法，根据新增的顶点对四面体网格进行切割产生 四面体内部网格边界，得到一个新的四面体网格。5. 如权利要求4所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤4包 括以下步骤： 步骤4-1，对于四面体网格中的每一个四面体T，计算其超平面方程系数向量h，具体过 程如下： 对于四面体网格中的每一个顶点V，其坐标表示为四维向量[X，y，z，c]T，其中X、y、Z 为该顶点v在原始输入视频中的坐标，c为其颜色值， 令四面体T的四个顶点分别为四维向量Vp V2、V3、V4，令四维向量V12= V fVp V13 = V3-V0 V14= V n = Cross (v12, v13, v14), 其中Cross (v12, v13, v14)表示四维向量v12、v13、v14的叉积，其结果n是一个垂直于v 12、 v13、Vi4的四维向量，令η p n2、n3、n4表示η的四个元素，即η = [η p n2, n3, n4]。， 令参数d = -Dot (n，V1)，其中Dot (n，V1)表示n与￥丨的点积， 则四面体T的超平面方程系数向量h = [ni，n2, n3, n4, d]，即四面体T所在超平面方程 % n1x+n2y+n3z+n4c+d = 0 ； 步骤4-2,对于四面体网格中的每一个顶点v，将其表示为齐次坐标形式V = [X，y，z， c，l]T，计算其Q矩阵及其二次误差Λ(ν): Q - Σ h e H(v)h h， Δ (ν) =Σ heH(v) (hTv)2= VtQv, 其中H(v)为顶点V所连接的所有四面体的集合； 步骤4-3,计算四面体网格中每一条边\的坍缩最优位置ν#与坍缩代价Cost (e y，坍 缩最优位置/通过求解以下优化方程得出： minvvT (Q^Qi) ν, 其中仏与L分别为边e ^两个顶点ν占 的Q矩阵，令：其中qn~q 55均为Q u的元素，令：则坍缩最优位置/=A，Bq， 缩代价CosUeij)计算如下： Cost(Gij) = v*T( Q ^QjOv*; 步骤4-4,将一端在内部网格边界另一端不在内部网格边界上的边排除在外，对剩余所 有的边依照其坍缩代价进行排序，对坍缩代价最小的边进行坍缩操作，将坍缩成的顶点设 置到其最优位置/上，合并边e u的两个顶点的拓扑连接，重复进行本步骤，直至剩余顶点 数达到预先设定数量或者没有符合条件的边可供坍缩为止，从而得到坍缩后的控制网格； 步骤4-5,对坍缩后的控制网格进行细分，通过求解以下优化方程，对控制网格进行优 化：其中Ef(V)与EJv)分别为误差能量项与拉普拉斯能量项，参数λ用以调节它们之间 的权重，在Ef(V)的定义中，Vk为控制网格细分后的顶点，#为Vk在初始网格上的投影，N s为控制网格细分后的顶点数目，k取值1~Ns，a k表示控制网格中的顶点与细分网格中的 顶点的线性组合关系，在EJv)的定义中，Vi为控制网格的顶点，巧为Vi的拉普拉斯坐标，N。 为控制网格的顶点数目，mvin表示求解使得E(V)最小的V。6. 如权利要求5所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤5包 括：使用细分后的控制网格对原始输入视频进行采样，求解以下优化方程以优化控制网格 的顶点颜色：其中，mjnEO)表示求解使得E(c)最小的颜色值c，Ck为控制网格细分后的顶点颜色， 4为Ck在原始输入视频上采样的颜色。7. 如权利要求6所述的一种基于四面体网格的视频矢量化方法，其特征在于，步骤6包 括：将颜色优化后的控制网格细分至适应于目标分辨率的密度，然后将其缩放至目标分辨 率后渲染成视频，视频中每个像素点的颜色值通过对其所属四面体的四个顶点的颜色值进 行三线性插值得到。
【专利摘要】本发明公开了一种基于四面体网格的视频矢量化方法，包括使用视频过分割方法对视频进行过分割；依照视频过分割的结果建立初始四面体网格；使用Lattice Cleaving算法对初始四面体网格进行切割；使用基于边坍缩的四面体简化方法对四面体网格进行简化；通过求解优化方程对四面体网格进行颜色优化；最后是对四面体网格进行渲染。本发明在将视频矢量化为四面体网格模型的同时尽量保持了视频中物体的几何形状等特征，并且处理过程中无需用户进行交互操作。
【IPC分类】G06T7/00, G06T7/40
【公开号】CN104899889
【申请号】CN201510349260
【发明人】郭延文, 朱捷, 王氚, 王文平
【申请人】南京大学
【公开日】2015年9月9日
【申请日】2015年6月23日
最新回复(0)