多分辨率DT模型基图像表示方法

多分辨率DT模型基图像表示方法 多分辨率 模型基图像表示方法 D T 卢 朝 阳,颜 尧 平,吴 成 柯 () 西安电子科技大学 综合业务网国家重点实验室 陕西 西安 710071 () 摘要:提出了一种模型基不规则三角形网格的多分辨率图 D T D e lau n ay T r ian gu la t io n 像表示方法. 在给出了图像表示的灰度误差极小化准则和灰度分布均匀化准则后, 讨论了 网格的分裂与合并方法, 并结合示例对两种准则表示结果的不同特点作了讨论. 多分 D T 辨率模型基图像表示方法可用于静止图像编码及活动图像的运动补偿等图像传输与 D T 处理的应用领域. 关键词: 图像表示; 模型基; 三角形D e lau n ay () 文章编号: 100122400 19990320277204 中图分类号: 39114 文献标识码: T P A - M ult ire so lut ion D e la una y tr ian gula t ion m ode lba sed im a ge repre sen ta t ion schem e 2, 2,2L U Z h a oy a n g YA N Y a op in g W U C h en g k e (). , . , ′710071, N a t io na l Ke y La bo f In te g ra te d Se rv ic e N e tw o rk sXid ia n U n ivXia n C h ina A bstra c t: A m u lt ire so lu t io n rep re sen ta t io n sch em e fo r an im age u sin g a D e lau n ay () 2. t r ian gu la t io n D T m o de lb a sed ir regu la r m e sh e s is in t ro du cedTw o c r ite r ia a re u sed in () , th e sch em e w h en de sc r ib in g th e im agew h ich a re M D m in im ize th e d iffe ren cean d M V (). m in im ize th e va r ian ceT h e sp lit t in g an d m e rg in g a lgo r ithm s o f D T m e sh e s an d th e . d iffe ren t ch a rac te r ist ic s o f th e re su lt s co n ce rn in g tw o c r ite r ia a re a lso d iscu ssedT h e , p ropo sed sch em e is u sab le in st ill im age co d in gm o t io n com p en sa t io n o f ac t ive im age .sequ en ce s an d o th e r im age p ro ce ssin g app lica t io n s ; 2; im age rep re sen ta t io nm o de lb a sedD e lau n ay t r ian gu la t io nKey W ord s: 在图像编码的研究中, 图像的表示方法有重要的地位. 在经典的图像编码方法中, 预测法曾获得广泛应用, 它实际上是把图像看成高阶过程, 从而用线性滤波理论来进行图像的预测编码; 变换 M a rko v 法是将图像看作一个广义平稳的随机场, 用线性变换来去相关. 在现代的图像编码中, 模型基方法 (是基于图像的二维或三维线框图表示; 分形法是基于图像的分数维表示. 其他方法 如子波、神经网络法 ) 等也都无出其右. 1, 2 3 在极低比特率序列图像编码中, 采用三角形或四边形的不规则动态网格来表示灰度图像, 这种模型基的方法近年来受到了重视. 在、I 及? 标准中, 编码的基本结构都是基于具 J P E GM P E GM P E G () 有固定大小的矩形图像方块的离散余弦变换 , 所以, 在压缩比较大时会产生严重的方块效应失 D C T 真. 而随进行动态变形的不规则网格图像编码方法, 在大压缩比时的失真效应比固定方块方法明显 降低. 就运动估计和补偿来说, 用三角形或四边形的变形网格比采用的矩形分块方法在补偿精度 M P E G4 等方面要好. 此外, 采用动态三角形网格进行图像描述为分形、矢量量化及小波在图像编码中的应用 5 打开了新的思路. 基于上述原因, 研究多分辨率的基于不规则变形网格的图像表示方法有重要的意 收稿日期: 1998204213 ( ) 基金项目: 国家自然科学基金资助项目69502004; 综合业务网及关键技术国家重点实验室开放课题资助项目 ( ) 作者简介: 卢朝阳19632, 男, 教授, 博士 1 111 三角形网格 D e la una y 如果二维平面上的数据点集为 {P , P ,, P }, 对每一点 P 定义区域V , 使属于该区域的所有点1 2 n i i ( ) 离数据点 P i 的距离都小于其他数据点 P j j ? i的距离, 则这样定义的区域是覆盖整个平面, 并由凸多 )( 边形构成的图形, 称它为该数据点集的图 简称 氏图. 如果把存在共同边界线段的数据点 V o ro no i V1 () 对用直线连接起来, 就形成该数据点集的三角形网格 即. D e lau n ay D T 在计算几何及图形图像处理中有不少应用, 因为它有一些很好的性质.如对于给定网格节点,D T 网格最大可能地避免出现狭长、尖锐的三角形连接, 并且具有唯一性. 在图像编码中, 前者对提高插 D T 1 值恢复图像的质量非常有利, 而后者有利于提高压缩比. 因此, 笔者采用表数据结构来和构 6 造网格.D T 112 自适应图像表示原理 () () 设原始图像表示为 I = f x , y , x , y ?D , D 为图像所在区域, I 为灰度值. 再设用来表示灰度图N - 1 () () 像的D T 网格共有N 个三角形, 记为 T i , i = 0,, N - 1. 称函数G = g x , y = ? g i x , y (x , y ) ?T| i i= 0 () 为该图像的一个“表示”或“逼近”, 其中函数 g x , y 称作“逼近函数”, 它定义在 T 上, 且满足 C =i i () C T ?C . 这里, 函数 C 表示定义在D 上的一个“准则”, C 是预先设置的一个门限. 采用不同的准则,i 00 可以得到具有不同特性的图像表示. () () 1灰度误差极小化准则 简称准则M D () 这里的“灰度误差”指原始图像与其表示图像之间的误差. 逼近函数 g x , y 可以在每一个三角形i ) ( y 个三角形 3 个顶点 3 个顶点确定的平面上进行构造. 最简单的情形是采用线性插值, 即取g x ,为第 i i 0 ) ( 处的灰度值进行线性插值所得到的平面. 如果线性插值的 C 连续不能满足光滑性的要求, g x ,y 的i 1 构造可采用三角形网格上的光滑曲面插值, 如具有 C 连续性的二次B ezie r 曲面插值. () 得到原始图像的逼近图像后, 准则函数 C 可定义为两者之间绝对误差的最大值, 即 C T i = () () () f x , y - y m ax { }. M D 准则即使 C T 小于等于预先给定的门限值. g i x ,() i 绝对误差的最x , y ?T i ) ( , y ) 即为新一层逼近时应优先考虑的数据点.大值发生的位置 P m = x m , y m (x| ?T m m i ()()2 灰度分布均匀化准则 简称准则 M V 在有些应用中, 对图像的分割希望采用某种“一致性”准则, 即希望在某个区域内, 图像的起伏变化 不大. 在用模型表示图像时, 希望在任意一个三角形范围内, 灰度尽可能均匀分布. 笔者采用网格的 D T 某个三角形上灰度分布的方差来表示这种一致性的度量, 并称这种准则为准则. 这样, 逼近函数M V ) ()() () (y = 1ƒN f , y , 其中N g x , y 可以定义为 T 上的均值, 即 E = g x ,表示 T 上的像x i i i i i ?() x , y ?T i 素点总数. 每一个三角形上灰度分布的方差为 2 22 () () f x , y - N E r V = . [ f x , y - E ]=i i i ??() () x , y ?T x , y ?T ii () () 准则函数 C 可定义为三角形上的灰度方差, 即C T i = V . Mi V 准则即使C T i 小于等于预先给定的门 限值. 与准则不同, 准则没有一个发生最大误差的位置作为新一层逼近时应优先考虑的数据M D M V 点. 通常, 可以用三角形的重心来作为下一层表示优先考虑的数据点, 因为重心必位于三角形内. 重心的 3 3 ( () () ) () 计算方法为 13x k , 13y k , 这里 x k , y k , k = 1, 2, 3 为三角形的 3 个顶点坐标.ƒƒ ? ? k = 1 k = 1 2 分裂与合并方法 在上述图像的表示方法中, 不管是法, 还是法, 实际上都是一个迭代的过程. 这个过程是 M D M V 从一个简单的结构开始, 在或准则指导下, 搜索到某一个“最差的”三角形 T , 再找到该三角形 M D M V b 中“最差的”一点P , 该点将作为新的数据点插入到原来的D T 网格中. 在网格更新后得到新一层更为满 b 意 的图像表示, 直到达到某一个预设的门限为止. 这个门限通常用三角形的数目来表示. 在M D 准则中 也可用插值逼近图像与原始图像之间的最大误差来表示; 在M V 准则中用任意三角形中灰度方差的最大值来表示. 显然, 上述过程建立了一个分辨率由低到高逐渐增加的多分辨率图像表示. 把上述 P 点对 b 网格的插入过程称作D T 网格的分裂. 网格经过充分分裂以后, 有时候也需要进行一些合并. 比如, 希望删掉小于某一面积的三角形, 或者 合并具有接近灰度均值的相邻三角形. 合并是分裂过程的逆步骤, 图像表示的分辨率由高到低下 降.文献6 报道了深度数据描述时的点插入过程;这里用网格节点删除的方法来实现网格合并. D T 7 给出了网格的动态生成与修改方法; 8 中也报道了另一种点删除算法. 下面结合图像表示中存 D T 在的特殊问题, 简述分裂与合并算法.边 建 形 并 树插 11 2网格的分裂 D T 立 进 界 成 简 入 行 特 新 单 网格的分裂算法如图 1 所示.首先, 根据选择的准则找到要D T 搜 别 参点多 三 数 处 边 确 插入的“最差点”P . 图 2 是一个例子, 其中 P 位于?P P P 中. 根据角 bb 1 3 4 计 理 形 形 算 索 定 D T 特性圆规则的要求, ?P P P 的外接圆中不应该有其他节点, 所 1 3 4 以, 由于 P 的插入, 该三角形必须删除. 图 1 中树搜索的目的就是从该分裂算法流程 b 图1P 2 三角形出发, 从列表式数据结构中找到所有的由于 P b 的插入应该被删除的6 三角形. 这一过程可行性由下述定义、定理保证. P 1 定义 1 任意多边形满足下列 3 个条件, 即边界封闭、除顶点外边界互 P b 不相交及内部无孔洞, 则称其为简单多边形. P 3 P 5 定义 2 设A , B 为简单多边形 S 内部两点, 若线段A B? S , 即A B 完全 P 4 位于 S 内, 称A B 是 S 上互为可见的.图2 插入P点 b 引理 1 若 P b ? ?P 1 P 3 P 4 , 则从?P 1 P 3 P 4 的相邻三角形出发做树搜索, 应删三角形集中存在, 其边界包围 P , 为一个简单多边形, 其中可 以不丢失地找到所有的应删三角形.b 无其他网格节点. 引理 2 P 到 S P 的任意顶点均为可见.b 定理 1 连接 P 到 S P 的所有顶点, 即构成新的D T 网格, 三角形的数目增加两个.b 图 2 中S P 为多边形P P P P P . ?P P P , ?P P P 和?P P P 将被删除, 并分裂为 5 个新三角 1 2 3 4 51 2 3 1 3 4 1 4 5 () 形如虚线所示, 比原先多两个. 图 1 的“建立简单多边形”过程将完成这一任务. P 2 值得指出的是, 就图像表示来说, P 完全可能位于矩形的图像边界上,b 这时的处理应稍有不同. 如图 3 所示, P P 右侧为图像边界. 这时, 网格的分 1 5 P 1 P 3裂按定理 2 进行. ?P b 定理 2 如果 P 位于图像边界上, 连接S P 中不与 P 共线的所有顶点,b b P 5 即构成新的D T 网格, 三角形的数目增加一个.P 4插入 P 来分裂网格的最后一步是计算所有新三角形的有关参数, 更新 b 图3 P点位于图像边界上 b 数据结构并保证 S P 内部和外部有正确的相邻关系. 增加新的点来分裂D T 网格, 其步骤与上述过程完全相同.边 形 伞 的 伞删 212 网格的合并 成 D T 沿 界 本 删 除 简 特 地除 网格的合并步骤如图 4 所示, 即去掉某一个网格节点及其周围的 删 别 点单点 D T 多处 的 确 三角形, 再重构本地局部 网格. 为方便起见, 称图 2 中以 P 为公D T b 构 边 理 伞 形 造 除 定 共顶点的所有三角形构成的形状为 P b 的“伞”. 显然, 伞之“沿”为简单 多边形P P P P P . 定理 1, 2 保证了P 的删除或加入都只影响其伞 1 2 3 4 5b 图4 合并算法流程内部的剖分, 所以, 图 4 中合并算法的关键是最后一步伞沿多边形的剖分. D T D T 关于本地伞沿多边形的剖分, 文8 中采用了一个本地辅助窗来重构. 比较起来, 7 的算D T D T 图 5 是两个分别采用和准则来表示图像的结果, 原始图像均为第一帧, 三 M D M V M iss A m e r ica 角形的数目基本相同. 对这两个典型例子作进一步分析, 得出了下述看法. () 1采用模型基图像表示方法得到的图像描述, 在图像变化剧烈的地方三角形网格会密集些, D T 反之, 在平坦的地方, 划分较为粗糙. 在这个意义上, 网格节点可看成是图像的特征点. 这种特性是许多 () 应用 如图像编码、图像识别等所需要的. 图 5 用模型基表示图像的例子 D T () 2当逼近准则不同时, 得到的 网格的形态是不同的. 与准则比较, 准则得到的网格 D T M D M V 在形状上更为“均匀”, 不像准则的结果那么尖锐. 显然, 这与网格分裂的方法有关.M D ( ) 3如果要采用某种方法从网格直接重建恢复图像, 应根据逼近准则做合适选择. 实验表明, 对 () 准则, 宜采用内插方法重建. 当采用由 3 个顶点确定的平面进行线性插值的方法重建图 5 网格的M D a () 恢复图像时, 峰值信噪比 为2716 . 对准则, 采用均值填充的方法比采用线性插值的方法 P SN R dBM V () 能得到更高的如图 5 的网格可达3019 . 从主观视觉质量上看,准则的恢复图像质量要 , P SN R b dBM D 好于准则, 虽然其可能不比后者高.M V P SN R ( )4 由于准则确保原始图像与逼近图像之间的最大绝对误差不超过一定值, 所以这种表示方 M D 1 法可以作为近似模型用来构造静止图像编码方案. 8 中报道的方法就是以此为基础, 结合模型优化 同时达到较好的恢复质量和较高的压缩比. ( )5 () 观察图 5 发现, 由于 准则确保按一致性原则来表示原始图像, 使逼近图像在每一个三b M V 角形上的灰度方差不超过一定值, 其结果显示出三角形的边界与图像的边缘特征拟合较好. 如该图的左下方和右下方呈垂直方向的衣服边界, 以及发际线边界等. 这说明采用准则得到的图像表示, 对图 M V 像中构成物体的各个面的逼近更好. 如果用这种网格进行运动估计和运动补偿, 将比用固定大小的矩形 或规则三角形来分割图像的方法具有优势, 因为这 里的分割与图像内容有关. 上述模型基不规则三角形网格的多分辨率图像表示方法适用于图像编码、运动补偿及特征检 D T 测等研究领域. 参考文献: () 1 卢朝阳, 吴成柯, 陆心如 1 基于表面描述的图像编码方法[]1 通信学报, 1991, 12 3: 17, 22. J () 2 李海波 1 模型基图像编码[]1 通信学报, 1993, 14 2: 69, 77.J 3 , . ——[ .W ang Y L ee OA c t ive M e sh A F ea tu re Seek ing and T rack ing Im age Sequence R ep re sen ta t io n Sch em e J () IE E E T ran s o n Im age P ro ce ssing, 1994, 3 5: 610, 624. () 下转第 285 页 5 结 束 语 在毫米波段, 采用步进频率距离高分辨技术与单脉冲偏轴测角技术相结合的方法对近距离杂波背 景下机动目标进行实时成像是可行的. 该方法不需改变目标视角就可成像, 成像时间短, 并且可以与常 规单脉冲跟踪雷达在功能上兼容, 所成的像能够反映目标的结构特征, 为雷达在强杂波背景中识别目标 提供了一条有效途径. 参考文献: 1 1987. W eh ne r D R. H igh R e so lu t io n R ada r [M . Bo sto n: A r tech H o u se, 2 G ill G S. S tep F requency W avefo rm D e isgn and P ro ce ssing fo r D e tec t io n o f M o v ing T a rge t s in C lu t te r [A . P ro c o f [. : , 1995. 573, 578.IE E E R ada r C N ew Yo rkIE E E () 3 何松华, 郭桂蓉 1毫米波体制的目标高分辨结构图像恢复方法探讨[]1 电子学报, 1993, 21 9: 8, 14.FM CW J 4 Sandy J M . G ro und M o v ing T a rge t R ada r S igna l S im u la t io n [A . P ro c o f N A ECON [C . N ew Yo rk: IE E E , 1980. 725, 732. . [. [. : , 1987. 217,C u r r ie N CM M W L and C lu t te r M o de l U p da te A P ro c o f In te r R ada r Co nf C N ew Yo rkIE E E 5 221. ()编辑: 郭 华 () 上接第 280 页 4 N ak aya Y , H a ra sh im a H. A n Ite ra t ive M o t io n E st im a t io n M e tho d U sing T r iangu la r P a tch e s fo r M o t io n [. , 1991, 1 605: 546, 557.Com p en sa t io n J SP IE , , . 5 D avo ine F A n to n in i M C h a sse ry JF rac ta l Im age Com p re ssio n B a sed o n D e launay T r iangu la t io n and V ec to r () 1996, 5 2: 338, 346.Q uan t iza t io n [J . IE E E T ran s o n Im age P ro ce ssing, ( ) 6 卢朝阳, 吴成柯, 陆心如 1 用三角形化实现的矩形边界表面描述算法[] 1 计算机学报, 1992, 15 3: 161 D e launay J , 170. () 7 唐泽圣, 徐志强 1 二维点集三角剖分的动态生成与修改[]1 计算机辅助设计与图形学学报, 1990, 3: 1, 8. J () 卢朝阳 1 模型优化及其在模型基图像编码中的应用[]1 通信学报, 1997, 8 D T J 18 6: 1, 7. () 编辑: 郭 华