运用可变模板进行并行图像处理的一种快速算法.pdf

第 26卷 第 3 期 2003年 3 月 计 算 机 学 报 CHINESE JOURNAL OF COMPUTERS Vol 26 No 3 Mar 2003 运用可变模板进行并行图像处理的一种快速算法 董育宁 南京邮电学院信息工程系 南京 210003 收稿日期 2001 10 10 修改稿收到日期 2002 12 15 本课题得到江苏省教育厅 医学图像三维重建与分析系统 项目资助 董育宁 男 1955 年生 博士 教授 主要研究兴趣是图像处理与分析 三维重建 网络视频流传输和图像数据库技术 E mail dongyn njupt edu cn 摘 要 提出了一种在并行机上有效地计算 空间 可变模板的方法 论证了利用一个在图像网格点处计算多项式 的优化算法 可以大大减少可变模板的运算量 对于包含非多项式函数的可变模板 可以用函数的泰勒级数展开实 现在像素点上的递推运算 详细分析了可变模板中若干常用函数的泰勒展开用于实现模板运算的合理性 准确性 和有效性 关于硬件的影响以及该方法的适用范围 也做了讨论 关键词 图像处理抽象 可变模板 快速算法 中图法分类号 TP391 An Efficient Algorithm for Parallel Image Processing with Variant Templates DONG Yu Ning Department of Information Engineering Nanjing University of Posts and Telecommunications Nanjing 210003 Abstract A fast algorithm for parallel image processing with variant templates is presented in this paper This algorithm is based on a key observation that we have a priori knowledge of the changing patterns of the ar guments i j and k and can take full advantage of this It is shown that the point wise updating of the variant templates can be greatly simplified by use of an optimized algorithm for evaluating polynomials at the image grid points While the efficient computation of polynomials plays a central role in this approach the technique is extended to include transcendental functions with the help of the Taylor expansion Examples of typical tran scendental functions show that reasonably high precision for common low level image processing applications and efficiency using only very few initial terms of the Taylor series can be achieved when the series form of the function is used for executing the variant template operations The influence of hardware and the limitations of the proposed algorithm are discussed at the end of the paper Keywords image processing abstractions variant templates fast computation 1 引 言 图像处理正在越来越多的领域中得到应用 包 括工业流水线检测 目标追踪 自动汽车驾驶 数字 电视图像传输以及医疗成像等方面 1 在许多实际 应用中 图像处理系统必须能够进行海量图像数据 的实时操作 并可通过监视器进行人机交互处理 2 这些处理功能的质量在很大程度上影响着研究工作 的效率及研究的成果 低级图像处理包含图像的抽样 滤波 旋转及其 它有关图像像素级和邻域级的运算 这些运算一般 都很简单 但由于需要处理的数据量巨大 所以要求 处理机具有强大的处理能力 典型的图像处理算法 要在图像的每一个像素上进行成百上千次的运算 为了实现这样巨大的计算能力 人们提出了并行处 理的方式 3 4 高级图像处理抽象中最有力的工具是图像模板 运算 尤其是可变模板管道或序列 可变模板管道能 较好地表达许多图像操作 如自适应滤波和图像变 换 5 8 尽管近年来许多学者对有效地执行图像模 板运算这个问题进行了研究 但很少有人提及如何 有效地执行通用可变模板 9 18 因此 关于如何有效 地计算通用可变模板或可变模板管道这个问题 尚 无定论 本文将探讨在中等或粗颗粒的MIMD 分布式多 处理器系统中 如何有效地计算 局部 平移可变模 板管道这个问题 在这样的并行机中 每个处理器在 本地内存中至少存有若干整行或整列的图像数据 并且独立地处理本地的子图像 在英国贝尔法斯特 女皇大学和乌尔斯特大学研制的 EPIC 可扩展并行 图像协处理器 便是这样一个系统 14 15 本文第 2 节指出了可变模板的计算效率问题 根据我们最新的文献资料检索 该问题尚未很好地 解决 为了对付这个问题 第 3节中探讨了对某些特 殊类型可变模板的解决方案 在第 4 节 根据图像中 规则像素网格点的性质 我们提出了一种解决更一 般可变模板算子的方法 它可以大大简化这些模板 的逐点更新过程 文章的最后讨论了硬件的影响及 所提方法的适用范围 2 问题陈述 本节将指出可变模板管道的计算效率问题 一个模板 T 可用一个三元组集的通用表达式 来定义 8 T row offset1 col off set1 weight1 row offset2 col off set2 weight2 row offsetN col off setN weightN 1 其中 每个三元组表示相对于中心像素的位置及该 点的权值 N 为模板中三元组的数目 每个可变模 板的权值和 或形状可随图像位置 i j 和 或管道阶 数 k 而变化 实际上 模板的权值和形状可以是 i j k 及其它参数的任意函数 设为ft 图 1 列出了一 些可变模板的例子 最直接的执行方法是通过调用 函数 ft在图像的每个像点上更新模板 不过 这种方 法效率不会高 其中 a 为 Hadamard 行变换 b 为类拉普拉斯算 子 它的中心权值与它到图像中心 Cx Cy 的距离成 正比 c 为可变形状的模板 d 为通过反向地址映 射的空间变换模板 如几何变形的校正 输入 IM0 p q 输出 IM1 i j p a0 a1i a2j a3i 2 a4ij a5j 2 q b0 b1i b2j b3i 2 b4ij b5j 2 3 提高效率的提示 通过观察图 1 的例子 我们有若干种途径来改 善直接法 1 如果 ft最多只依赖于i j k 三个变量中的 两个变量 则可以先处理其它的变量 放在循环的最 内层 在那里模板将保持不变 2 如果ft包含一些条件性测试 则可将图像分 为几个子区域 每个子区域符合一个条件测试 并可 用分段静态模板逐个地对每个子区域执行运算 例 如 对于Hadamard 行变换算子 图 1 a 按照 even j div 2 k 这个条件测试 每一行数据可分为两个子 区域 真 假 并将两个静态模板 T1和 T2分别用于 这两个子区域 其中 T1 0 0 1 0 2 k 1 真区域 T2 0 0 1 0 2 k 1 假区域 具体地说 在第 k 阶 用于优化运算的 C 伪代 码可写为 333 3 期董育宁 运用可变模板进行并行图像处理的一种快速算法 for m 0 m N 2k 1 m 2k 1 m1 m 2k for j 0 j 0 x h 0 y y 0 由图 2 a 可见收敛条件为 式 9 y 0 a0 0 a1 0 15 如果式 15 成立 则另一个条件自动满足 情况 2 a1 0 对 y 0 16a 且 a1 a1x a0 对 y y x N 16b a1 1 N a0 0 a1 0 17 因此 式 15 和 17 指出了该例中的收敛条件 对同一函数 泰勒展开有不同的形式 也就对应 不同的收敛域 例如 对数函数也可展开为 log y y logy y y y 2 2y 2 y 3 3y 3 y y y 18 如仍用式 13 和 14 的条件 收敛域可以是 a1 0 20 可见 Rn依赖于x 的值 当 x 增加时 Rn减小 设 x 1 则 Rn i n 2 2i 13 2i 1 i n 2 2i 1e a 2i 1 x 0 21 其中 a loge3 若令 f t 2 2t 1e a 2t 1 22 根据柯西 麦克劳林积分公式 21 n f t dt i nf i n f t dt f n 23 将 u a 2t 1 du 2adt 代入上式 积分式变为 z u 1e udu E 1 z 24 其中 z a 2n 1 E1 z 为非完全 Gamma 函数的 指数积分 21 根据式 21 24 Rn E1 z 2 2n 1e z 25 由数学表查得 22 a loge3 1 10 E1 5 5 n 2 0 00064 26 因此 R2 m 则当 0 时 x m n最 大 所以 Rn m n x m n x 1 35 设 m 1 2 当 x 2 时 有 R2 1 2 1 2 1 2 2 1 2 2 2 4 5 4 42 10 2 36a R4 3 5 16 24 2 3 2 3 45 10 3 36b 同样 当 x 增加时 Rn减小 若 x 5 则 R2 2 3 5 1 2 2 1 12 10 2 37a R4 3 5 16 24 5 3 5 1 40 10 4 37b 4 收敛速度 我们可以用前面所讲的方法来提高式 32 的收 敛速度 将式 32 中的 x h m乘上 1 a 1 h x 得 1 a1 h x x h m x m n 0 m n h x n a1 n 0 m n h x n 1 x m 1 n 1 m n h x n a1 n 1 m n 1 h x n x m 1 n 1 m n 1 h x n m n 1 a1n n x m 1 n 1 m n 1 h x n m 1 a1 1 n n 38a 若令 a1 1 则上式变为 x m n 1 m n 1 x m nhnm 1 n 38b 337 3 期董育宁 运用可变模板进行并行图像处理的一种快速算法 原先分子中的 m n 1被 m 1 代替 而 m 1 是一个常数 与 n 无关 这样将收敛速度提高了 n 1级 5 讨 论 5 1 误差分析的进一步讨论 1 另一种途径 前面已通过例子论述了如何控制近似误差 这 种方法也可用来处理更复杂的情况 只是要用到更 多的数学计算 由于在非实时情况下 真实值通常总 是可得的 所以可考虑另一种替代方法 让 z 和z 分 别表示真实值和估计值 则误差 E 可表示为 E z z 39 因此 可用另一种方法来估算精度 这种误差控 制方法可与前面提及的解析方法结合使用 并且 如 果解析公式不够精确或很难得到 这种方法也许就 更好 2 误差累积 前文的误差分析方法 只考虑了当前位置产生 的近似误差 但是 由于递归计算包含了前一位置的 馈入 所以上一步产生的误差可能会累积到下一步 比如 从位置 0前进到位置 1 z 1 z 0 z 由式 39 z0 E0 z E1 z0 z E0 E1 z1 E1c 40a 其中 E1c E0 E1 40b 是包括从位置 0 扩散到位置 1 的累计误差 通常 在 位置 t Etc t i 0 Ei 41 可能我们已注意到 在许多情况下 近似误差或 泰勒级数的余项 Rn与x 的位置有关 当 x 增大时 它就减小 就如式 20 35 和 40 所示的那样 这 就给了我们一个提示 即沿着 x 轴倒序循环 就可 能减小总体误差 这样 由前面迭代产生的很小的误 差 在后面的迭代中可忽略不计 因此 总体误差就 可由在 x 的最后一点 最小值 处产生的误差粗略 地估算得到 5 2 性能的硬件相关性 就多项式的计算而言 本文所讲的方法在绝大 多数机器上都能高效地运行 而对于超越函数 则与 硬件有关 如果计算机配置了算术协处理器 则内置 函数 如 log sqt exp 等 就执行得相对快 所以也许 不必对这些函数进行泰勒展开 直接法可能更有效 不过 要是能对任一种计算机都提供一个优化方案 而不需借助于特殊的硬件 不是更好吗 5 3 算法的局限 这里没有考虑嵌套超越函数的情况 尽管本文 讲的基本理论也许适用于这种复杂的情况 但诸如 收敛性 误差分析和级数展开的有效性等问题还有 待验证 不过所幸的是 在低级图像处理中 很少见 到这种复杂的表达式 6 结 论 本文提出的快速计算可变模板管道的方法 是 基于这样一种观察 即我们知道自变量 i j k 的变 化模式 并能充分利用这些条件 文中证明了 可以 利用在图像网格点处计算多项式的优化算法 来有 效地减少计算可变模板算子的运算量 尽管在这种方法中 多项式的高效计算起了重 要作用 借助于泰勒展开 这种方法已可扩展到超越 函数 在几乎任何系统配置中 这种方法对多项式而 言 在计算上的优势是显而易见的 而对超越函数而 言 则依赖于其它一些因素 包括硬件的配置 但是 通过前述典型的超越函数的例子可知 当用函数的 级数形式来执行可变模板算子时 能够得到较高的 精度 对一般的低级图像处理而言 和较高的效率 仅使用泰勒级数的前几项 致谢 感谢英国贝尔法斯特女皇大学的 D Crookes 教授对本文工作的宝贵建议 参考文献 1Pratt W K Digital Image Processing 2nd Ed NY John Wiley Sons 1991 2Choudhary A N Patel J H Parallel Architectures and Parallel Algo rithms for Integrated Vision Systems Kluwer Academic Publishers 1990 3Hull M E C Crookes D Sweeney P J eds Parallel Processing The Transputer and Its Applications Addison Wesley 1994 4Zomaya A Y ed Parallel Computing Paradigms and Applications In ternational Thomson Computer Press 1996 5Ritter G X et al Image algebra An overview CVGIP 1990 49 297 331 6BrownT J Crookes D A high level language for image processing 338 计 算 机 学 报2003 年 Image and Vision Computing 1994 12 2 67 79 7Crookes D Morrow P J McParland P J IAL A parallel image pro cessing programming language IEE Proceedings Part I 1990 137 3 176 182 8Crookes D Spence I T A Brown T J Efficient parallel image trans forms A very high level approach In Proceedings of the 1995 World Transputer Congress 1995 135 143 9Wilson J N Fischer G R Ritter G X Implementation and use of an image processing algebra for programming massively parallel computers In Proceedings of the 2nd Symposium on the Frontiers of Massively Parallel Computation Fairfax VA 1988 587 594 10Coffield P C Scudiere M B A prototype coprocessor for image algebra operations In Proceedings of the SPIE 1993 2030 327 333 11Shi H Ritter G X Wilson J N An efficient algorithm for image tem plate product on SIMD mesh connected computers In Proceedings of the 1993 International Conference on Application Specific Array Proces sors Venice Italy 1993 12Shi H Ritter G X A special class of nonlocal image template opera tions In Proceedings of the SPIE 1994 2300 204 212 13Shi Hong Chi Two image template operations for binary image process ing Journal of Mathematical Imaging and Vision 1997 7 3 269 274 14Crookes D Brown T J Dong Y McAleese G Morrow P J Roantree D K Spence I T A A self optimising coprocessor model for portable parallel image processing In LNCS 1124 Berlin Springer Verlag 1996 213 216 15Morrow P Crookes D Brown J Dong Y McAleese G Roantree D Spence I Achieving scalability portability and efficiency in a high level programming model for parallel architectures In Proceedings of UK PAR 96 1996 29 39 16Wilson J N Forsman RH Using templates and neighborhoods Practi cal considerations and formal observations In Proceedings of the SPIE 1994 2300 192 203 17Li D Recursive operations in image algebra 18Sussner P Ritter G X Rank based decompositions of morphological templates IEEE Transactions on Image Processing 2000 9 8 1420 1430 19Crandall R E Topics in Advanced Scientific Computation Springer Te los 1996 20Beyer W H CRC Handbook of Mathematical Sciences 5th ed FL CRC Press Inc 1975 21Arfken G Mathematical Methods for Physicists 3rd ed