（电路与系统专业论文）图形反走样算法及其硬件模型研究.pdf

南京航空航天大学硕士学位论文 摘要 本文研究的主要内容是图形的反走样算法及其硬件模型研究。本文从理论分析了 图形、图像走样的原因，对反走样算法进行了研究和比较，提出了一种基于边缘提取 和模板匹配的图形反走样算法。 本文首先从理论上阐述了引起走样的原因、常用的反走样算法和本文采用的基于 边缘提取和模板匹配的反走样算法；其次简单地阐述了数字系统的设计方法，并结合 在设计过程中的体会，提出一些数字系统设计的思想；最后主要用v h d l 语言描述 了硬件系统的模型并进行了时序仿真。 通过本文对算法的研究和m a t l a b 仿真，证实了算法的可行性和有效性，本 算法适合所有的图形和大字符的反走样。 关键词反走样边缘提取模板匹配v h d lf p g a 一一一 图形反走样算法及其硬件模型研究 a b s t r a c t t h i sp a p e ri n t r o d u c e sak i n do fg r a p ha n t i a l i a s i n ga l g o r i t h ma n dj t s i m p l e m e n tb yh a r d w a r e t h ep a p e ra n a l y s ist h ea l i a s i n gr e a s o n o f - g r a p ha n d i m a g ei nt h e o r y ，r e s e a r c ha 1 1k i n do fa n t i a l i a s i n ga l g o r i t h m a n da d v a n c e d a na n t i a 1i a i n ga l g o r i t h mb a s e do nt h ee d g ep i c k i n g u pa n dt e m p l a t e m a t c h i n g f i r s t ，t h ep a p e re x p a t i a t et h er e a s o no fa l i a s i n g i n t h e o r y ， 8 “t 1 一a 1 1 a s i n ga l g o r i t h m1 nc o m m o nu s ea n da ng r a p ha n t i a l i a s i n ga l g o r i t h m b a s ee d g ep l c k i n g u pa n d t e m p l a t em a t c h i n g ：s e c o n d l y ，t h ep a p e rd i s c u s st h e d e s l g nm e a n so fd i g l t a ls y s t e m ，a n dp u tf o r w a r ds o m ei d e ao fd i g i t a l s y s t e m d e s i g nw h i c hie x p e r i e n c e di nt h ec o u r eo fm yd e s i g n i n gt h es y s t e m ：a t l a s t t h ep a p e rc o n s t r u c tt h e s y s t e mm o d e lo ft h eh a r d w a r eb yv h d l i tv a l i d a t e dt h ef e a s i b i l i t ya n dv a l i d i t yo ft h ea l g o r i t h mt h r o u g ht h e r e s e a r c h i n ga ns i m u l a t i o no ft h ea l g o r i t h m t h ea l g o r i t h mi ss u i tf o ra l l t h e g r a p ha n db i gc h a r a c t e r a f t e rt h i s ，1d e s i g n e dt h eh a r d w a r es y s t e mo f a n t i a l i a s i n ga l g o r i t h mb yv h d la c c o r d i n gt h er e q u i r e m e n to fa l g o r i t h ma n d d a t as t r u c t u r eo f g r a p h k e yw o r d ： a n t i a i a s i n g a l i a s i n ge d g ep i c k u p t e m p l a t em a t c h i n g v h d lf p g a 概论 0 1 课题来源 飞机技术和飞机性能的迅速发展，大屏幕综合显示是必然的趋势，即在任意状态 飞行中，飞行员可以在有限的视域内依靠一个或几个显示器，及时地获得所必须而充 分的信息。在整个显示系统中，图形显示占据重要地位，其中显示速度和图形质量又 是关键问题。显示画面的实时、清晰，是飞行员及时准确操作的保证。 面目前国内军用座舱显示系统，由于图形生成系统的硬件性能和在图形处理算法 软件上的落后，使其性能和质量远远落后于西方发达国家。只有从图形显示系统的硬 件结构和图形生成算法同时入手，重点研究实时图形生成系统的硬件结构，将现代电 子领域技术的最新发展，各种成熟软、硬件i p 等应用到座舱综合显示系统中，结合 优化图形处理算法，从根本上大幅度提高座舱图形显示系统的性能，实现国产飞机座 舱的现代化目标。 在军用座舱显示系统中，采用液晶显示器来显示各种图形和字符。液晶显示器是 由一系列离散的显示像素点组成，当用这些离散的像素点来显示连续的图形和图象 时，必然会引起失真，尤其在显示线条图形时这种失真更加明显，通常我们把这种失 真称为走样。为了减小或者消除这种失真所采用的方法就称为反走样。本文研究的内 容就是图形的反走样算法。 o 2 反走样算法的现状 现代对于反走样算法的研究还没有达到个很成熟的阶段，国内外这方面的论文 也不是很多。目前还没有一套成熟的理论来解决各种图形或图象的走样问题。对于反 走样算法大致可以分为三类，一是对于面状图象的反走样；二是字符的反走样，字符 的反走样又可分为大字符和小字符的反走样；三是图形的反走样，主要是针对线条形 图形的反走样。要对不同类型的图象或图形进行反走样，采用的算法往往不同。即使 是同种类型的图形或图象，为了达到不同的反走样效果，也有不同的反走样算法。 最常用的反走样方法就是增加采样点，也就是减小显示器像素的尺寸，但是这是 增加数据处理量为代价的，同时显示器像素的大小都已经固定，用这种方法不太现实。 另外一种方法就是对像素矩阵进行滤波，因为走样主要是由图形或图象的突变引起， 这种突变引起图象频谱的高频成分，用低通滤波器可以将这些高频成分滤除，以达到 反走样的目的，但是这种方法很难控制反走样以后的图形线条的宽度，所以这种算法 对于图形的反走样不太适合。要用滤波的方法对图形、图象进行反走样，滤波器参数 的设置是关键，对于不同的参数，得到的图象反走样效果有明显的不同。还有一种算 法是通过曲线拟合和模板匹配的的反走样算法，虽然它比较适合图形的反走样，但是 这种算法计算比较复杂，不太适合用硬件来实现。 从理论上讲，适合于图形反走样的反走样算法都适合大字符的反建样；然而对于 3 蚓彤反止弹饽 ：及其埂什模田研究 小字符要考虑反走样以后字符发生模糊，小字符的反走样算法可以作为一个新的课题 去研究。 o 3 可编程器件概述 可编程器件经过几年的发展，芯片的规模、密度、性能都有了惊人的变化。可编 程逻辑器件成为计算机应用、通信技术、自动控制技术、仪表仪器等领域广受欢迎的 器件，它是科学实验、样机研制、小批量生产的最佳选择。p l d 技术有三大发展方 向：一、向密度更高、速度更快、频带更宽的百万门系统级方向发展。二、向嵌入标 准或通用功能方向发展。三、向低电压、低功耗的绿色元件方向发展。可编程逻辑器 件主要是指c p l d 和f p g a ，能应用在不同的高科技领域，如数字电路设计、微处理 器系统、d s p 、电信、可重构计算机及a s i c 设计。 复杂的可编程器件( c p l d ) 规模大、结构复杂，属于大规模集成电路的范围。 c p l d 主要是可编程逻辑宏单元( l m c ) 围绕中心的可编程互连矩阵单元组成。其中 l m c 结构较复杂，并具有复杂的v o 单元互连结构，可由用户根据需要生成特定的 电路结构，完成一定的功能。由于c p l d 内部采用固定长度的金属线进行各逻辑块的 互连，所以设计逻辑电路是具有可预测性，避免了分段互连结构时序不完全预测的缺 点。2 0 世纪9 0 年代，c p l d 的发展迅速，不仅具有点擦除特性，而且出现了边界扫 描及在线可编程等高级特性。同时除了以l m c 为基础加上内部a n d 、o r 阵列外， 外围的i o 模块扩大了其在线系统中的应用范围和扩展性。较常用的有x i l i n x 公司 的e p l d 、a l t e r a 公司及l a t t i c e 公司的c p l d 。1 9 9 2 年l a t t i c e 公司率先推出 了i s p ( i n s y a e m p r o g r a m m a b i l i t y , 在线系统编程) 技术，但是对于多数c p l d 来说， 修改后的逻辑不能完全符合原有的引脚输出，或者是修改了关键的定时路径。这样， 为了修改逻辑，不得不重新进行电路布线，对于高密度的c p l d 尤其是这样。许多厂 家的c p l d 在进行层次互连以后，性能降低，延迟不稳定。而c y p r e s s 公司使5 1 2 个 宏单元的器件也具有了“引脚锁定”和“速度锁定”功能。 现场可编程逻辑门阵列( f i e l dp r o g a m m a b l eg a t ea r r a y ) f p g a ，它的优点是可以实 时地对外加的或者内置的r a m 或e p r o m 编程，实时地改变器件的功能，实现现场 可编程( 基于e p r o m ) 或在线重配置( 基于r a m ) ，是科学实验、样机研制、小批 量产品生产的最佳选择器件。 f f g a 通常包括三类可编程资源：可编程逻辑功能块，可编程i o 和可编程互连。 可编程逻辑块是实现用户功能的基本单元，它们通常排列成一个阵列，散布于整个芯 片；可编程v o 块完成芯片上逻辑与外部封装脚的接口，常围绕着整个阵列于芯片四 周，可编程内部互连包括各种长度的线段和编程连接开关，它们将各个可编程逻辑块 或【o 块连接起来，构成特定功能的电路。不同厂家的f p g a 在线可编程的规模，内 部互连线的结构和采用的可编程的元件上存在较大的差异。较常用的是x i l i n x 和 a i t e r a 公司的f p g a 器件。 南京航空航天大学硕士学位论文 0 4 本文研究的图形反走样算法及其硬件模型研究 对图形进行反走样，首先要确定反走样算法。因为算法的不同，直接影响反走样 处理的性能。本文提出了种适合硬件实现并能够控制线条宽度的反走样算法，这种 算法是利用边缘检测的方法，找出图形中最容易引起失真的边缘部分，然后沿着找出 的边缘做一定的平滑或者增加一定的随机噪声，这样可以使得失真现象得到良好的控 制，同时也控制了反走样以后的图形线条的宽度在一定的范围之内。边缘检测般要 对整幅图形数据进行搜索，对每个像素都要进行一定的运算，再加上平滑工作，这种 算法工作量比较大，但是这种算法比较简单，没有涉及到复杂的积分、微分运算( 仅 仅用到累加，比较运算) ，即使是乘法运算，其两个操作数仅仅是0 或1 ，所以比较 适合于用硬件( f p g a 或c p l d ) 来实现。 本文第三章到第八章详细阐述了反走样算法硬件实现。硬件设计的思路是首先设 计黑白二值图形的反走样模块，在本文中称为黑白核一心处理模块。黑自核心处理模块 主要由轮廓( 边缘) 提取单元和模板匹配单元构成，其主要功能是将没有灰度级别的 黑白二值图形通过运算得到具有1 6 级( 4 位二进制数表示) 灰度的反走样图形。然 后，在黑白核心处理单元的基础上设计彩色图形的反走样模块，彩色图形的反走样模 块与黑白核心处理模块相比增加了彩色预处理单元、彩色后处理单元、像素缓冲单元。 彩色预处理单元是将彩色图形数据通过一定的算法处理成适合黑白核心处理单元处 理的数据，彩色后处理单元接收黑白核心处理单元的数据和像素缓冲单元的数据，以 恢复原先输入图形的色彩。像素缓冲单元主要是对输入的彩色像素进行缓存，以供恢 复色彩时用，为了适应硬件的流水线结构，像素缓冲单元设计成三级缓冲的形式。 当然，用硬件实现图形的反走样，也可以使用d s p 来实现，但是考虑到图形显示 的实时性，用c p l d 或者f p g a 可编程器件更加能够满足实时性的要求。 幽彤反走样算法及其娅仆模j 似 f 亢 1 1 二维图象分析 1 1 1 采样和量化 第一章走样的理论分析 尽管f ( x ，y ) 这个二维函数所对应的图像，可以在某个范围内对所有的置y 均定义， 但是在实际处理的时候，我们只可能取某些离散点上的值，并以此为基础来进行讨论。 在进行显示时，首先对二维信号肛，力进行采样，如果服，力定义在一个矩形区域d 上，即当o sx 量x ，o y y 时有定义，令厶和匆分别为两个充分小的数，且满足m o a x = x ，n 0 4 y = y 。当我们用 f ( i ，) ，即 f ( i a x ，j a y ) 来表示f ( x ，叫时，称这种采样 为等间隔采样，其中出和匆分别为x 和y 方向上的采样间隔，它们的倒数称为相 应方向上的采样频率，在没有特别说明时，我们所采用的都是这种采样。 1 1 2 二维采样定理 一个使人普遍关心的问题是，当净，力用其采样值 f ( i ，j ) ) 来表示时，原来包含 在 f ( i ，j ) ) 中的信息是否会丢失。换句话说，我们是否能用f ( i ，j ) 来完全恢复f ( x ，川。 放到图像显示这个环境中来说，这个问题就是像素矩阵所代表的图像能否完全真实地 反映客观存在的图像，也就是图像在显示屏幕上显示是否会引起失真的问题。下面对 二维采样进行分析：假设是兀( r ，f ：) 是一个二维连续波形，对它进行矩形抽样而得到 的离散信号f ( n 。，n 2j 由下列公式给出：f ( n 1 ，n 2 ) = 厶( n 。互，n 2 t 2 ) ，其中t 1 t 2 是正整数， 分别表示水平抽样间隔和垂直抽样间隔( 或抽样周期) 。对于这种形成的序列，我们 要明确的是f 。( f ，f ：) 能否由f ( n l ，n 2 ) 恢复出来。 下面定义二维傅立叶变换： f a ( c 2 f 2j = f 。( q , t 2 ) e x p ( j r 2 l f i j 0 2 t 2 ) d r l 础2 肿：) = 专- i 协e x p ( j 0 1 f 1 棚：f 2 ) 蛾蛾 由于m ，列铆洱幔j ，则可以用以下的式子表示： f ( n l , j = 三了r z z o r a , ，0 2 ) e x p ( j - c 2 1 月l 五+ j - ( 2 2 n 2 t 2 ) d ( 2 1 d ( - 2 2 ，引入q ：乌，：r 正 妣f ( n l , n 2 j = 专e ”去吒r 等，鲁2 ) e x p ( j 叩川蚴：脚加： 在整个，m t 。：j 平面内的双重积分可以分解成很多积分的无穷级数， s q ( k ， ：j 下 南京航空航犬人学硕| 。￥：似论文 方彤一丌十2 丌女l5 似1 ，+ 2 z k l ，一丌+ 2 z k ：! 丌+ 2 , z k ! ，贝i jl 二式i l j 以1 弓如竞 八 2 嘉等等趔。圾：，去cc 鲁，“- ：) e x p ( j c o l n i + 鲰州： 用l 一2 础2 2 z k 2 代替m 2 ，则可以去掉积分对k ，k 2 的依赖关系，于是 肌刚2 专甄志k i k z 蹦与等与 刚叩一蚴：刚m ： 瓢f ( c o t , c 0 2 ，。去荨丢cc 半，等， 或者瓢胭五) 2 去善丢脚一孚，呼孕) 上式给出了连续信号的傅立叶变换和离散信号的傅立叶变换之间的关系，这个 表达式的右边可以解释为r 力，力：j 的周期延拓。 当连续信号f o ( t f ：是带限信号时，则式1 5 可以进步简化，在r 力。力，j 的某 个有限区域之外，带限信号的傅立叶变换为零，为了方便起见，我们假定采样周期 足够小，使下式成立： r 力l ，口2 ，= 0 ，当| 力l | 彳7 1 口2 当 l j2 则简化为fr 力，五，氆咒j ；嘉r q ，口：，；l q l 争到力：1s 争。在这个区域外 i 21 1 2 的，( q 。正，q ，疋) 由其周期性给出，如下图1 1 ( a ) ( b ) 图11 ( a ) 连续带限信号的傅立叶变换( b ) 连续带限信号的傅立叶变换的周期延拓 从上面的分析可以得到二维抽样定理：一个带限的连续信号，可以由它的抽样值完全恢 复出来，这就必须保证抽样周期足够小，或者说周样频率足够大以保证条件： 幽彤反走样算法及其艘什睽m j f 尤 r q 。，f 2 1j = 0 当1 n l l 1 7 4 - j 力! j2 7 ”- 成立 。i2 1 1 3 二维滤波 假设我们已知二维函数f ( x ，y j 所代表的图象是由有用信号s ( x y j 和噪声信号 n ( x ，y j 两部分组成，对f ( x ，y ，进行滤波，就是要在对它规定一定的运算后，使运算 的结果和有用信号s ( x y ，充分接近，而噪声信号n ( x y j 在结果中基本上被抑制掉，为 了说明这个目标应当如何才能达到，我们需要先在频域中进行讨论。 设f ( x ，y ，s ( x y ，n ( x ，yj 的频谱分别为f ( u ，v j ，s ( u v ) 瓤l n ( j ，那么由 “y ，= s ( x ，川+ 月似y j ，我们可以知道吖j = s 似v j + _ v 似v j 也同样成立。 如果我们知道s ( u ，v ) - 与u ( j 是分离的话，也就是说假定存在某个区域d ，使得 下面的关系成立 rn ( u ，v j = 0 当r “，v j d 时 l s ( “，v j ：0 当( “，v j 萑d 时 那么，我们只要规定这样的一个函数h ( j ，令它满足： h 阻，v 户r 1 当r “，v j d 时 lo 当( “，v ) d 时 并令y ( u ，v ，= r ，f ( u ，v j ，于是有斤，= 吖j ，这也就是说，即j 的逆 傅立叶变换7 r y ，应当和s 一，v j 的逆傅立叶变换s 似，川也是一样的，这样就实现的所 需要的目标。 当然，这里是在很理想的( 例如频谱可分离) 假定下来讨论的。但是，这个假定 可以在采样定理成立时得到满足。这是因为，我们希望g m v j ( 采样以后的频谱) 在作 了定的运算后能和f ( u ，v j 一样。根据g ( u v ，频谱图( 图1 2 ) ，我们可以看出，只要 规定 h ( u ，v j = l1 一v ，西= 似v ) l l “1 i 2 b ：) 的缘故。于篡藉 图形反走样算法及其崾什模型 l j f 究 j k 山p i j b ： 乍飞 1 2v - r l 。 一u b l a ，一一、jl ，一、 ，r 、：， 装 少i 出t l b 图1 3 频谱的混叠现象 g ( u ，v ) 与h ( u ，v ) 相乘时，在d 一石这些位置a f r of ( u ，v ) 将丢失，不仅如此，如图1 3 所不的a ，b 两个小区域上分别叠加f ( u + i a x ，v l 4 y j 和f ( u 1 血，y i 却j 这两个 函数中的某些值。因此，这里不仅有f ( u ，v ) 应有的值，而且有了实际上不是它的频率 成分。这就是在采样间隔不够小，即采样频率不够高的情况下，在频率域中形成的频 谱混叠现象。这样，我们如果还用与血，如相应的低通滤波器h ( “，。) 来恢复厂( z ，y ) 时，所得到的结果不会是要求的f ( x ，y ) ，而是有相当大失真的图象了。由此可见， 将采样信号通过低通滤波器所得到的恢复后的信号，只要采样间隔不是足够小，那么 就会失真。失真的根本原因是某些高频成分的丢失以及另外一些高频成分折回来当作 低频成分被使用而引起的。这就是通常所说的混叠现象。 通过上面的介绍，可以知道，设备的限制或者要显示的图象有丰富的高频成分， 常常导致对实际图象采样不足的像素矩阵。这种采样不足的情况引起采样信号的频谱 在频域上的混叠现象，从而反映在时间、空间上是采样信号经过低通滤波后的信号或 者图象与实际的图象有差异，即图象会失真。由于人眼在观察时固有的低通滤波功能， 使得像素矩阵所代表的显示在屏幕上的采样信号，在被我们看到后( 实现了低通滤波) 可能发生上述分析所引起的失真。 1 3 消除图形失真( 反走样) 的一些方法 从上面的讨论我们可以知道，由于图形频谱的混叠引起了图形的失真。那么了消 除或营说是减少这种失真的方法我们称之为反混叠，也称为反走样。 在这一章中，我们要介绍减少图形失真即反走样的一些常用的方法。一般来说， 由于图形频谱常常不是带宽有限的，所以要在显示中完全消除失真现象是不可能的。 因此我们只能采取措施，使得失真尽可能地减少，当失真降低到人的眼睛无法分辨的 时候，我们就认为消除了图形的失真。 在众多的方法中，最直观最容易想到的办法就是增加采样频率。例如，我们可以 在一个像素中采多个而不是一个采样点，例如采四个、九个或者更多，然后在将这些 采样值进行平均加权作为该像素的实际值。这个方法相当于采样前对原图象先作低通 南_ ：航空航夫人、j 硕r ：f 沦文 滤波。这种方法实现起柬也非常地方便，但是这种疗法化费的代价是比较高的。 另外一种方法是所谓的后处理法。假定我 f j 已经按照通常的方法得到了要 t & 爪帆 实际图形的采样，但是在将它显示之前，对采样后的图j 髟做进步的处胖，最后阿将 处理后的采样点在屏幕上显示出来。这里所说的处理，并无专f 1 的规定。例如种可 供选择的处理就是利用标准的取阀值的方法( 或其他更加有效的方法) ，找出图形巾 最容易失真的部分边缘。然后沿着找出的边缘作一定的平滑或者增加一定的随机 噪声，这样可以使得失真现象得到良好的控制。这种方法所需要的工作量一般是比较 大的，这是因为边缘检测一般要对整个图形进行搜索，每个像素要与其邻近的像素进 行比较，所以工作量与屏幕分辨率的平方成正比，再加上平滑的时间，因此也相当费 时，然而这种方法对改变边缘的外观很有效。 第三种方法就是面积采样法。这种方法的思想非常的直观。那就是如果将一个像 素理解成为对应的一个小的矩形区域的话，那么这个像素的采样应当是在这个小区域 上所有可见强度的平均值。为了说明方法，请参阅图l4 ：图( a ) 表示一个像素实际 上为两个可见面所覆盖。其中光强度为a 的覆盖了像素的1 2 ，b 对应像素的l i 3 ， 而未被覆盖的c ( 即背景) 为1 6 。于是这个像素显示为( a 2 + b 3 + c 6 ) 。 面积采样法实际上是前面介绍的滤波方法的一个具体的实现。这里w x ，yj 一个像 素所占的区域为1 ，其外为0 。所以，经过滤波( 这种平均值对应的滤波器) 后的采 样与常规点的采样有本质的区别。例如黑白间隔的条纹图形的显示，在采用面积采 图1 4 覆盖同一像素的两个面 c a b 样方法后，绝对不会出现全黑或者金白这种严重失真的图形。另方面，既然我们将 面积采样法理解为滤波的结果，那么在具体实现时，选择不同的滤波方法就会得到 不同的滤波结果。但是这是量的差异，而不是质的差异。 尽管这种方法很简单，但是具体实现的时候仍然有许多实际的问题要认真对待。 最早提出这个方法的是f c r o w ，由于面积采样法等价于采样前先进行低通滤波，这 样图形中不能被重建的高频分量在采样前被滤去，重建时，频率混叠得到良好的控制， 因而使得采样后图形的失真大大减少。但是这种运算的工作量很大，因而要寻找快速 幽彤反走样谇7 去及其硬件跌掣蚜究 的能等效于直接做褶积滤波的方法。除了要解决这个问题，c r o w 还提出了要使这个 方法有自调节功能，也就是晚要尽可能在十分必要的时候才施行上述的滤波运算。 c r o w 对于上述的两个问题，部提出了解决的办法，对于前一个问题，他在对滤 波器作了可分离的假设下，认为如果要进行滤波的图形是分片的常数的话，就可以建 立查表的方法来减少来运算的次数。对于后个问题，他所提出的方法是对可能出现 光强度有较大变化的地方做定的标记，例如曲面的侧影轮廓就是这样的。如果用多 面体来逼近曲面，那么在确定了观察位置和观察方向后，侧影轮廓线必是这样的两个 多边形的公共边，其中一个多边形是可见的，另一侧为自隐面。所以如果我们在多面 体表示中对多边形的公共边，公共顶点作适当的标记，那么比较容易确定侧影轮廓线， 从而可以在其附近施行必要的滤波以消除图形的失真。当然，不光是它们，其它的地 方，例如曲面的边界( 一边是背景，一边是曲面内部) 也可能有剧烈变化的光强度， 同样需要适当的注意。 1 4 图形反走样算法 现实世界是连续模拟的，而机器视觉是离散数字的，这两者之间的差别如果超过 人体视觉所允许的范围就称为走样。走样，也就是由0 和1 表示数字图形在其色彩的 过度区域，在视觉可见范围内引起的鲜明的锯齿和不一致。走样使得图形变形，造成 视觉上的不适感，甚至会引起误解。工程上常常采用措施，用于减少或者消除这种走 样的技术，称之为反走样。 1 4 1 、基于边缘提取和模板匹配的反走样算法 1 4 1 1 反走样算法的有关定义及基本概念 图集定义：g 、t k 、d 都是按照某种规则定义的集合，n 为集合的元素，g 、 d 的定义分别如下：d = f d k ，jg = f t k l 乃n t i = 西f 爿) 凡其中n 为二维空间中以d t 为边界的区域，称g 为参数图形，d 为g 的边界。 及走棒翼子定义：g r ) = f g ( r ) i j ) j = r f gr ) = r p ) ( g ) ：g 。( r ? c ) 一fg ( r ) i i j ，= r ar gr c ，= r ar ，c j 倒i 其中rr ，r j 为对的非反走样变换，r 。r ，r ，c ) 为对的反走样扫描变换，为空间分辨率，c 为灰度级，m r 和胁是二值图像的 行数和列数，我们称grr ) 为g 在r 分辨率下的二值参数数字图像，g c trr ，c ) 为g 在，分辨率、c 灰度级条件下的反走样参数数字图像。 连通区域二值定义：v i r d ，m r 一 ，i 徊，n r u j f = 泄，= ，；如果g “ j ) 2 iag ( i 。j j ) 鸯带g t j ) 一g ( i ，j 1 ) 或氆g ( i 。| ) = g ( i j j ) g ( r ) 中备连通区竣 的边界称之为轮廓，边界像素为轮廓像素，并称gr rj r f ：，为8 连通区域。 轮南提淑真子定义：g cfr ) = cf g ( r ) ) = r ( r ) ( d ) = ( g c ( r ) ( i ? j ) j ，其中c ( ) 是从中提取轮廓像素的运算， 即当且仅当gr ，r i ，为轮廓像素时，使得g c r r j r i ，= 1 ，称g c f r ) 为gr rj 的轮廓像素。 1 4 i 2 反走样算法 本宵讨论的反走样算法的实质是假定原图为二值图形，按照一定的规则给图彤的 轮廓像素赋予不同的扶度值，以达到平滑整个图形的目的。因此，这种算法应该分为 两个步骤：一是提取图形的轮廓，二是通过运算给每个轮廓像素赋予不同的灰度值。 第一步通过轮廓提取算法实现，第二步通过模板匹配算法实现。 ( a ) 轮廓提取算法 假设输入的二维数字图形为r 一，一，i = ，2 m r ? = ，2 n r ；按照行顺序或 者按照列的顺序，逐个地以每个像素为中心取一个3 3 的区域，并判断这个区域是 否为个8 连通区域，如果是一个8 连通区域，那么连通区域值为0 的像素就是 图形的轮廓，轮廓提取的结果如图15 所示( 黑色为图形像素，灰色为轮廓像素1 图1 5 轮廓提取示意图 轮廓提取的数学表示如下：假设p ，o f ( i ，j ) ji = ，2 ，m r ij = ，2 n r 为轮 廓素，s “州为计算的中间值，崩，矽，i = ，2 ，m r ；j = ，2 n r 为输入的图形矩阵。 f + i ，+ l s z i d l 笠厂( f ，n( 1 6 ) p 1 ，一1 、 p r o f o ，) = c ( g ( ，) ) fl 一厂( f ，) ；厂( f ) = l 且5 “2 i nr d - 。口： b sr d o ： s y n t r d 。a 。： i ff d _ e p t 。1 a n di n _ r d p - n e x t _ s t a r e 一s 1 ： e l s e n e x ts t a t e i nr d 1 ： b 5r d 一a ： s ，n t r d t nr d o ： h sr d 一1 ： s y n t r d 。o ： i ffdr d v 。1 a n db s e p t n e x ts t a t e s 3 ： e 1 ；e m e x ts t a t e i nr d 一a ： b sr d 一1 ： s y n t r d 0 ： n e x ts t a t e 一s 4 ： w h e ns 4 ，) i nr d ，口： b sr d - 0 ： s y n t r d 0 。； i f ( s y n t _ e p t = 1 a n d n e x ts t a t e - s 5 ： e 1 5 e n e x ts t a t e i nr d ( ，0 ： b sr d ，a ： s g n t r d 。1 ； r e x ts t a t e i nr d - 。8 ： b sr d - 8 ： s g n tr d i nr d - 。0 ： b sr d - 0 ： s p n t _ r d ( 。n 。： n e x ts t a t e - s 0 ： e n dc a s e ： e n dp r o t e s s s t a r e _ c o m b ： s t a t e _ c l o c k e d ：p r o c e s s c l k ) b e g i n i f c l k e u e n ta n dc l k - 1 t h e n p r e s e n ts t a t e ( 。f l e x t _ s t a t e ： e n di f ： e n dp r o c e s ss t a t e _ c l o c k e d ：l e 帅c o n t o r la t - c h i t e c t u v e ： 哲求航2 虢人人学唧! 一 伊沦父 第四章轮廓提取单元 4 0 轮廓提取单元原理框架 轮廓提取单元完成的任务主要是对输入的数据进行运算，以计算出输入的像素 是否为轮廓像素。轮廓提取单元的总体框图如图4 1 所示，各单元的描述见下面各 小节： 图4 1 轮廓提取单元的总体框图 4 1 输入缓冲单元( f i r s tb u f ) 输入缓冲单元对输入的数据进行缓冲，采用缓冲可以减少系统模块间的等待， 提高数据的处理速度，但是这是以牺牲系统的资源为代价的，在设计时，要充分考 虑，因为在c p l d 或者f p g a 中，存储单元特别占用资源。输入缓冲单元如图4 1 所不d a t a _ i n a 6 3 o 】、d a t a _ i n b 6 3 0 】、d a t a i n c 6 3 0 、d a t a _ i n d 6 3 0 】、d a t a i n e 6 30 】 分别是输入的5 个6 4 位数据：d a t a o u t a 6 3 o l 、d a t a _ o u t b ( 6 3 o l 、d a t a、_ o u t c 6 3o l d a t a o u t d 6 3 0 】、d a t a _ o u t e 6 3 0 】为输出的5 个6 4 位数据：信号f f i r s t b u ff u l l 来自系 统控制器，m r s t b u ff u l l = 1 1 表示输入缓冲已经将新的数据输入到输入缓冲单元；信 号f p r o t r d 来自系统控制器，f p r o f j 扣1 1 通知输入缓冲单元从外界读入数据： d o u r r d y 为本系统的输出信号，当d o u tr d y = 1 时，表示缓冲器中的数据已经准备 好，后续相应的单元可以从本单元中将数据读走。 圈形反走样算法及其硬件模型研究 4 2 轮廓提取单元( p r o f i | e o p ) 本单元是边缘提取算法的具体实现，在本单元中，为了提高运算的速度，采用 了并行运算结构，用三个单元同时进行运算，最终通过逻辑判断，来决定单元的状 态。在本单元中，对轮廓提取算法进行的改进，使得本算法更加适合于用硬件来实 现。具体的算法如下描述： 假设d i n _ a 6 3 0 、d i nb 6 3 0 、d i nc 6 3 o 、d i nd 6 3 0 、d i ne 6 3 o 为输八 数据，如何判断d i nc 6 3 一0 1 这6 3 个位哪些位是轮廓像素呢? 首先，以d i n b 6 3 0 中的每个像素为中心，选取一个3 x 3 的区域，如果中心像素不为0 ，这个3 x 3 区域 保持其原来的值不变；如果为1 ，这个3 x 3 区域中的中像素的值取反，将处理后的 第3 列值保存在一个变量b 6 3 0 1 中。以同样的方法分别对d i nc 6 3 。o 进行处理， 处理后的值保存在c 6 3 0 中。再以同样的方法对d i nc 6 3 o 进行处理，处理后的 结果存放在d 6 3 0 中。最终对将b 6 3 0 】、c 6 3 一o 、d 6 3 0 j 对应的为相或，存放在 变量d a t ao u t 6 3 0 1 中。从上面的运算中可以看出，每计算一行，都要对三次轮廓提 取，一次相或运算，但是三次轮廓提取运算是相同的算法，只不过是输入的数据不 同而己，所以可以采用相同的模块进行处理。算法处理的结果如下图4 2 所示( 图 中的黑色像素点表示图形像素，而灰色像素点表示轮廓像素，在本图中仅仅画出了 5 行数据中中间一行的轮廓数据) 图4 2一行数据轮廓提取示意图 算法的实现框图如下图4 3 所示：p r o f i l e o p l 、p r o f i | e o p 2 、p r o f i l eo p 3 完成的功 能类似，主要是完成三次轮廓提取，分别得到三个在中间行像素上引起的轮廓。在这 几个模块中d i na 6 3 0 】、d i n b 6 3 0 】、d i n c 6 3 0 、d i n d 6 3 0 、d i n _ e 1 6 3 o 是5 个 6 4 位输入数据；c l k 为输入时钟信号；f r r o fr d 为系统控制器送来的读信号，当 f p r o f l 时，从外部将数据读入到这三个模块中； 一1 为处理完后输出的_ r d = d a t ao u t 6 30 结果：p r o f i l eo 、一、1 表示一次数据处理完，当f p r o f1fl当时钟的上升沿来到时，_rd= 将p r o f i l eo 、，复位，p r o f i l eo 、一l 。 p r o f i l eo p l 的仿真结粱如图4 4 所示： 南京航空航人人。；颁十学f i 沦殳 图4 3算法的实现框图 1 0 l | 1 0 1 1 4 8 由l 砷l 删1 1 1 4 l m 巾0 1 l i i | 期l 胁胁碾i i l o l l 删8 m l 胁删1 4 胁i 删l i l i j | i 删l 期| 1 f | i l 劬l i | i | l l l 4 i i j 丌丌广广l it ii i i rl 丌l t i 可丌丌厂广i t i 可t 丌丌 t 【可丌阿 1 竹广r r 广i w t l 竹汁广r 。广i 丁1 竹什r 广i 1 _ l ”竹广r 广广下t 1 n 矿 1 1 - p i p h 1 一f f 1 1 h 些吐吐i 划出些吐吐l 刳翼辫丛i l l 丛吐 划“些四 il fq 0 0 9 唧唧t 即啤il ii 【j1 l i h n 姗e i i 1 雨斤f f l 节一ii 词丽断词彳= i 嗣斤斤厅i 诵司行丽嗣雨嗣一i1 斤 1 叶t 十r 中l h 1 1 叶f 叶一p 中1 1 叶f 十p 十j 州悱i 十叶p 十 辛寺片阡 卡i 爿辛牛恃片；辛；爿什忖阡 哨h h 忖卜卜十；h h 怍 图4 4算法实现仿真图 从上面的仿真结果中可以看出，输入数据进行处理的时间为6 4 个时钟周期如 果不采用并行结构，那么整个的处理时间为1 9 2 个时钟周期，通过这种平行结构， 使得处理时间减少到原来的三分之一。f i n a l _ o p 的单元完成对输入的两个6 4 位数据 的对应位相或，在这个模块中，只有当f p r o f i l eo v l 、f p r o f i l e o v 2 、f p r o f i l eo v 3 都 等于1 时，在时钟的上升沿到来时才将数据读入进行运算，同时d r o f i l eo v ： p r o f i l e o vl & f p r o f i l e o v 2 & f p r o f i t e _ o v 3 。 4 3 轮廓输出缓冲单元( p l a c e ) 轮廓输出缓冲单元主要是对轮廓像素进行缓冲，p r o f i l ei n 6 3 0 1 为输入的轮 南京航空航人人。；颁十学f i 沦殳 图4 3算法的实现框图 1 0 l | 1 0 1 1 4 8 由l 砷l 删1 1 1 4 l m 巾0 1 l i i | 期l 胁胁碾i i l o l l 删8 m l 胁删1 4 胁i 删l i l i j | i 删l 期| 1 f | i l 劬l i | i | l l l 4 i i j 丌丌广广l it ii i i rl 丌l t i 可丌丌厂广i t i 可t 丌丌 t 【可丌阿 1 竹广r r 广i w t l 竹汁广r 。广i 丁1 竹什r 广i 1 _ l ”竹广r 广广下t 1 n 矿 1 1 - p i p h 1 一f f 1 1 h 些吐吐i 划出些吐吐l 刳翼辫丛i iiil i l 丛吐 划“些四 iiiiliil fiiiii iiiliq 0 0 9 唧唧t 即啤iiiil iiiiiii 【jii1 li i iii i ii ii i ifijill i h n 姗e iiiij ii ii liii lij i il i 1 雨斤f f l 节一ii 词丽断词彳= i 嗣斤斤厅i 诵司行丽嗣雨嗣一i1 斤 1 叶t 十r 中l h 1 1 叶f 叶一p 中1 1 叶f 十p 十j 州悱i 十叶p 十 辛寺片阡 卡i 爿辛牛恃片；辛；爿什忖阡 哨h h 忖卜卜十；h h 怍 图4 4算法实现仿真图 从上面的仿真结果中可以看出，输入数据进行处理的时间为6 4 个时钟周期如 果不采用并行结构，那么整个的处理时间为1 9 2 个时钟周期，通过这种平行结构， 使得处理时间减少到原来的三分之