The Halftone Screen Algorithm of Error Diffusion Research Based on Edge Detection ZHAO Lianqing, CHEN Yuhang School of Electric and Electronic engineering, North China Electric Power University, Beijing, China e-mail: zhaolianqing@163.com, cc_chenyuhang@163.com Abstract: Based on the experiments, this paper combines the edge detection method with the dynamic error diffusion algorithm to optimize the shortcomings of traditional error diffusion. The image is divided into two parts, the edge regions and the non-edge regions. The former will be processed directly without error diffusing in order to reduce the loss of contour while the latter is processed by the dynamic error diffusing, whose diffusion weight is changed dynamically. During the process of edge detection, a method for extending Laplace template is introduced to improve the quality of edge detection. Through the simulation results, the image quality is optimized by the improved algorithm. Keywords: digital halftone screen; error diffusion; edge detection; dynamic error diffusion 基于边缘检测的误差扩散半色调算法研究 赵莲清, 陈宇航华北电力大学电气与电子工程学院, 北京, 中国,102206 e-mail: zhaolianqing@163.com, cc_chenyuhang@163.com 摘要 本文以实验为基础, 融合边缘检测算法和动态误差扩散算法, 研究传统误差扩散算法的优化方案 对原图形进行边缘检测, 边缘区域与非边缘分别进行处理, 前者不进行误差扩散, 以减少轮廓损失 ; 后者通过动态误差扩散, 使得误差扩散的扩散权值动态改变 在边缘检测过程中引用了扩展的 Laplace 算子, 提高边缘检测质量 通过仿真结果分析, 证明改进算法对图像质量的优化 关键词 数字半色调 ; 误差扩散 ; 边缘检测 ; 动态误差扩散 1 概述数字半色调技术是利用数学 计算机等工具, 将具有连续色调图像转化为二值图像阵列的一门技术, 使输出的二值图像阵列给人造成一种视觉上的连续色 [1] 调效果, 半色调算法的选择直接影响到打印效果的优劣 目前, 在半色调技术中, 使用最为广泛也是效果最好的算法是误差扩散算法 通过对这种算法进行结构分析和频域分析, 可知误差扩散算法在处理图像细节和图像边缘过程中存在缺陷 由于误差扩散滤波器在对图像进行二值化过程中, 对图像误差频谱进行了调整, 同时也衰减了图像的低频部分使图像质量降低 [2] 针对这些缺点, 本文在已有的半色调算法基础上 项目基金 : 国际科技合作计划项目资助课题 ( 批准号 2007DFA71250) 进行了改进 在图像边缘检测过程中, 引进了一种扩展的 Laplace 算子 [3], 提高了图像边缘检测的灵敏度 在图像的非边缘区域, 引用了动态的误差扩散算法 [4], 减小了由于误差扩散过程中权值固定而引起的图像质量降低 将这两种算法同时引用到半色调过程中, 来提高处理后图像的效果, 使图像边缘轮廓更加突出, 非边缘区域图像色调过度更加平滑 2 改进的半色调算法 2.1 边缘检测算法首先对图像进行边缘检测, 增强图像的边缘效果 定义图像中灰度发生急剧变化的区域为边缘区域, 则图像灰度变化可用图像灰度梯度来反映 : df df G dx dy (1) 406
G 表示图像 f ( xy, ) 在 ( x, y ) 处的梯度 梯度的模值 G 可以作为边缘检测的算子 : G f f 2 2 1/2 [ x y ] (2) 本文中引用的 Laplace 算子由二阶偏导数定义 : f x f y 2 2 2 G 2 2 (3) 从实验结果可以看出扩展的 Laplace 算子模型考虑了更多方向, 在进行边缘检测的过程中对图像灰度阶凋变化更敏感, 伪轮廓的产生有所减少, 提高了图像边缘提取的质量 如图 3 所示改进后的检测图轮廓更加清晰, 在色调平缓区域不必要的边缘轮廓有所减少 实际检测过程中,Laplace 算子利用差分来实现 常见的算子模型如表 1: Table 1. Laplace operator template 表 1. Laplace 算子模板 -1-1 -1-1 8-1 -1-1 -1 但表 1 所示的模板只考虑了当前像素点周围 8 个方向上, 文献 [3] 中提出了扩展的 Laplace 算子模型, 如表 2 所示 : Figure 2. Result of Laplace operator 图 2. Laplace 算子检测图 Table 2. Extending Laplace operator template 表 2. 扩展的 Laplace 算子模板 0 1/8 0 1/8 0 1/8 1/2 1 1/2 1/8 0 1-7 1 0 1/8 1/2 1 1/2 1/8 0 1/8 0 1/8 0 本文, 将这种改进的边缘检测模板引入到误差扩散半色调过程中 对原图像进行边缘像素信息提取, 提取结果如图 3 所示 Figure 1. Original image 图 1. 原始图像 Figure 3. Result of extending operator 图 3. 改进 Laplace 算子检测图 2.2 动态误差扩散算法传统的误差扩散算法都采用固定的误差扩散系数, 在经典的误差扩散之后, 又提出了很多改进算法 但这些算法大都改变了误差扩散的滤波器, 即改变扩散权值和扩散方向, 提高了在误差扩散过程中噪声在频域搬移的质量 而动态的误差扩散则是根据扩散误差的不同来改变扩散权值 [4] 通常的误差扩散是通过发送误差, 为了方便处理, 从接受误差的角度来考虑 其扩散的方向和权值分配如图 4 407
p( j1, i 1) p( j 1, i) p( j1, i 1) h2 h3 h 4 h 1 p( j, i 1) p( ji, ) 统的误差扩散来说, 动态的误差扩散权值选择提高了误差扩散与图像的联系 减少了因为扩散权值固定而引起的半色调图像中出现的伪轮廓和图像边缘区域信息的损失 在确定了图像的误差扩散权值后, 便可以对图像进行误差扩散 如图 5 所示, 为传统的误差扩散结果 ; 图 6 为动态的误差扩散结果 : Figure 4. Traditional error diffusion 图 4. 传统误差扩散示意图 其中 p( j, i) 表示当前像素点 ; p( j1, i1) p( j1, i) p( j1, i1) p( j, i1) 表示以处理像素点 ;h 1 2 3 4 表示扩散权值, 分别为 7/16 1/16 5/16 3/16 可见传统的误差扩散中扩散权值是固定不变的, 与原图像的灰度特征无关, 没有考虑到图像本身的特点 且在水平和竖直方向上扩散权值 ( h1 3 ) 最大, 在扩散过程中会造成水平和竖直方向上的误差叠加, 产生伪轮廓 由于权值固定的传统误差扩散存在的缺陷, 所以本文使用了动态误差扩散, 即误差扩散权值根据图像 [5] 像素特征而动态变化 扩散权值的选择算法如下 : 用 e1 e2 e3 e 4 表示当前像素 p( j, i) 和其周围四个已处理像素的差值, 如公式 (4) 所示 : e1 P( j1, i) P( j, i) e2 P( j1, i1) P( j, i) e3 P( j1, i) P( j, i) e4 P( j1, i1) P( j, i) 其中 P( ji, ) 表示 p( j, i) 点的像素值 根据这些差值就可以确定误差扩散系数 对 e1 e2 e3 e4 进行排序, 根据排序的结果, 差值最大的方向选择的误差扩散权值最小 ; 同样, 差值最小的方向选择的误差扩 散权值最大 例如, 这些边缘差值排列后的结果是 e1 e2 e3 e4, 那么误差扩散权值的选择为 : 7 5 3 1 H1, H 2, H 3, H 4 16 16 16 16 这种根据当前像素点与周围像素差值来动态的选择误差扩散权值的方法考虑到了图像的特征, 相对传 (4) Figure 5. The result of traditional error diffusion 图 5. 传统误差扩散结果 Figure 6. The result of dynamic error diffusion 图 6. 动态误差扩散结果 从实验结果可以看出, 传统的误差扩散在轮廓处比较模糊, 部分区域有失真 ; 由于误差扩散系数是固定的, 处理后的图像对灰度的把握不好 动态的误差扩散减少了由于轮廓信息损失所引起的伪轮廓, 且误差扩散的过程与图像特征联系起来, 对色调的把握更好, 表现细节更多, 如图 6 中荷叶的部分, 叶脉表现的更为清晰 但动态的误差扩散并不是完美的, 在灰度变化剧烈的区域, 图像细节表示的并不明显 从图 6 可以看出, 图中花蕊部分的细节几乎没有表现出来 针对这一缺点, 本文把改进的边缘检测引入到动态误 408
差扩散中, 来增强图像半色调过程中对细节的表现, 提高图像的视觉效果 2.3 改进的动态误差扩散算法 通过前面的实验, 分析出动态误差扩散存在的缺点, 进而引入了边缘检测算法 把图像分为两部分来处理 : 边缘轮廓部分和非边缘轮廓部分 由于通常在进行误差扩散的过程中, 把边缘轮廓和非边缘区域共同进行处理, 边缘像素点同样要进行误差的叠加, 削弱了边缘点强度, 轮廓看起来相对模糊 改进的误差扩散算法首先对原始图像进行边缘检测, 检测出的边缘像素点并不进行误差扩散, 直接对其进行阈值判断 在非边缘区域引用本文中提到的动态误差扩散算法, 加强原始图像与半色调过程的联系 如图 7 所示, 为改进后的算法流程 改进的算法流程中, 边缘点的检测即采用本文 2.1 节所提到的改进的边缘检测算法, 在非边缘区域采用的动态误差扩散算法流程如图 8 所示 2.4 实验结果及分析 在 Matlab7.0 环境下, 对图 4 进行仿真实验, 实验 Figure 8. Flowchart for dynamic error diffusion 结果如图 9 所示 : 图 8. 动态误差扩散流程图 Figure 9. The result of improved algorithm 图 9. 改进动态误差扩散结果 改进算法的结果, 在非边缘区域没有太大的变化 而对于边缘区域有所加强, 从图 9 可以看出, 相对于原始的误差扩散图像视觉效果更好 在避免了图像细节丢失的基础上, 加强了图像轮廓区域信息 3 结束语 Figure 7. Flowchart for the improved algorithm 图 7. 改进算法流程图 由以上讨论可知, 相对于传统误差扩散半色调算法, 改进的算法加强了对图像细节和边缘轮廓的处理 图像进行误差扩散前先进行边缘检测, 使用扩展的 Laplace 算子以提高边缘提取的精确度, 对于图像边缘点不进行误差扩散, 使图像轮廓信息得以更好的保留 409
而动态误差扩散算法使误差扩散权值根据图像特征动态改变, 减少由于扩散权值固定而引起的图像细节信息损失, 提高图像的质量 References ( 参考文献 ) [1] 任小玲, 张二虎, 数字半色调技术发展研究 [J], 西安工业学院学报,2003,23(2),P108-P113. [2] Ren Xiaoling, Zhang Erhu, Review of Progress of Digital Halftoning Techniques [J], Journal Of Xi an Institute Of Technology, 1999, 23(2), P108-P113 (Ch). [3] K. E. Spaulding, R. L. Miler, J. Schidkraut, Methods for generating blue-noise dither matrices for digital halftoning [J], J. Electron. Imaging, 1997, 6(2), 208-230. 黄剑玲, 邹辉, 基于高斯 Laplace 算子图像边缘检测的改进 [J], 微电子学与计算机,2007,24(9),P155-161. [4] Huang Jianling, Zou Hui, The Improvement of Image Edge Detection Based on Gauss-Laplace Operator [J], Microelectronics & Computer, 2007, 24(9), P155-161 (Ch). 刘祖军, 刘纯亮, 等离子体显示中基于边缘检测的动态误差扩散方法 [J], 西安交通大学学报,2004,38(6),P627-631. [5] Liu Zujun, Liu Chunliang, Dynamic Error Diffusion Method Based on Edge Detection in Alternating Current Plasma Display Panel [J], Journal Of Xi an Jiaotong University, 2004, 38(6), P627-631. [6] Chung J. Kuo, Ching Liao, Ching C. Lin, Adaptive Interpolation Technique for Scanning Rate Conversion [J], IEEE Transaction on Circuits and Systems for Video Technology, 1996.6(3), P317-321. 410