（通信与信息系统专业论文）镜像层叠滤波器优化理论及算法研究.pdf

哈尔滨 警大学硕十学位论文 摘要 为了满足人们对信号处理更高的要求，非线性信号处理逐渐发展起来， 作为非线性信号处理主要手段的非线性滤波器得到了广泛研究。层叠滤波器 是一种具有层叠性和闽值分解性的非线性滤波器。根据阈值分解方式的不同， 层叠滤波器分为传统阈值分解层叠滤波器( 简称为传统层叠滤波器) 和镜像阈 值分解层叠滤波器( 简称为镜像层叠滤波器) 。与传统层叠滤波器相比，镜像 层叠滤波器不仅具有低通特性，而且具有带通和高通特性。本文重点研究了 镜像层叠滤波器的优化理论及算法，主要内容包括： 首先，对层叠滤波理论进行了研究，包括：正布尔函数的定义、性质及 生成算法，镜像层叠滤波器的定义及输出信号的快速重建，镜像层叠滤波器 的优化模型，并对现有优化算法进行了简要介绍。 其次，为了降低镜像层叠约束的计算量，引入一种二级小窗口级联递归 滤波结构。级联窗口的滤波效果相对同样大小的单级窗口的效果得到了扩展； 递归结构节省了运算空间，提高了滤波效果。本文通过实验仿真确定了最佳 二级级联窗口的形状及尺寸。 然后，针对离散粒子群算法寻优能力较差的缺点，提出了一种改进离散 粒子群算法。该算法中引入精英集团和粒子自适应变异策略以提高算法的寻 优能力，精英集团由适应度较好的若干粒子组成；粒子自适应变异策略根据 粒子浓度自适应确定变异概率。仿真实验表明：与简单遗传算法和离散粒子 群算法相比，应用改进的离散粒子群算法优化的镜像层叠滤波器较好地保持 了原始图像的细节。 接着，考虑到初始种群对算法搜索能力的影响，对初始种群要求不高的 遗传算法进行了研究，改进了影响算法寻优能力的主要算子一交叉算子：将 优秀个体与与其相似性差别较大、适应度较差的若干个体交叉，相似性根据 个体间的汉明距离来衡量。仿真实验表明：与改进的离散粒子群算法相比， 应用改进的遗传算法优化的镜像层叠滤波器的去除噪声性能有所提高。 哈尔滨t 程大学硕十学何论文 最后，为增加种群多样性，更有效地提高算法的全局寻优性能，对克隆 选择算法进行了研究，并对其进行了如下改进：记忆群体采用多克隆算子， 多克隆算子中的重组操作采用了改进遗传算法中交叉算子的思想；保留群体 采用单克隆算子，单克隆算子中的变异操作采用改进离散粒子群算法中的自 适应变异策略，此外群体问还进行信息交流，避免后期进化停滞。仿真实验 表明：与改进粒子群算法和改进的遗传算法相比，应用改进克隆选择算法优 化的镜像层叠滤波器的去噪和保持图像细节性能得到了平衡。 关键词：镜像阈值分解；层叠滤波；粒子群算法；遗传算法；克隆选择算法 哈尔滨t 程大学硕十学何论文 a b s t r a c t i no r d e rt os a t i s f yt h ed e m a n do fp e o p l er e q u i r i n gh i g h e ra b i l i t yo fs i g n a l p r o c e s s i n g ，n o n l i n e a rs i g n a lp r o c e s s i n gi sg r a d u a l l yd e v e l o p i n g ，n o n l i n e a rf i l t e r s a r ew i d e l ys t u d i e dw h i c ha r et h em a i nm e a n so fn o n l i n e a rs i g n a lp r o c e s s i n g s t a c kf i l t e r sa r eac l a s so fn o n l i n e a rd i g i t a lf i l t e r sw h i c hp o s e s st h r e s h o l d d e c o m p o s i t i o na n ds t a c k i n gp r o p e r t i e s a c c o r d i n gt h ed i f f e r e n tw a y so ft h r e s h o l d d e c o m p o s i t i o ns t a c kf i l t e r si n c l u d et r a d i t i o n a lt h r e s h o l dd e c o m p o s i t i o ns t a c k f i l t e r s ( r e f e r r e d t oa st r a d i t i o n a ls t a c k f i l t e r s ) a n d m i r r o r e dt h r e s h o l d d e c o m p o s i t i o ns t a c kf i l t e r s ( r e f e r r e dt oa sm i r r o r e ds t a c kf i l t e r s ) c o m p a r e dw i t h t r a d i t i o n a ls t a c kf i l t e r s ，m i r r o r e ds t a c kf i l t e r sn o to n l ya r ep r o v i d e dw i t hl o w - p a s s c h a r a c t e r i s t i c ，b u ta l s ob a n d - p a s sa n dh i g h - p a s sc h a r a c t e r i s t i c s t h i sp a p e rf o c u s e s o nt h eo p t i m i z a t i o nt h e o r ya n da l g o r i t h m so fm i r r o r e ds t a c kf i l t e r s ，t h es t u d y i n c l u d e st h ef o l l o w i n ga s p e c t s ： f i r s t l y , s t a c kf i l t e r i n gt h e o r yi ss t u d i e dw h i c hi n c l u d e sd e f i n i t i o n ，p r o p e r t i e s a n d g e n e r a t i n ga l g o r i t h mo fp o s i t i v e b o o l e a nf u n c t i o n , d e f i n i t i o na n df a s t r e c o n s t r u c t i o no ft h eo u t p u ts i g n a l so fm i r r o r e ds t a c kf i l t e r , o p t i m i z a t i o nm o d e lo f m i r r o r e ds t a c kf i l t e r s ，r e l a t i v eo p t i m i z a t i o na l g o r i t h m sa r ei n t r o d u c e d s e c o n d l y , i no r d e rt o r e d u c et h ec a l c u l a t i o no fc o n s t r a i n t so fm i r r o r e d t h r e s h o l d d e c o m p o s i t i o n ，at w os m a l lw i n d o w sc a s c a d er e c u r s i v ef i l t e r i n g s t r u c t u r ei si n t r o d u c e d ，t h ef i l t e r i n ge f f e c to fc a s c a d ew i n d o w si se x t e n d e d c o m p a r i n gw i t hs i n g l e w i n d o wo fs a n l es i z e ；r e c u r s i v es t r u c t u r es a v e st h e c o m p u t i n gs p a c ea n di m p r o v e sf i l t e r i n ge f f e c t t h eo p t i m u ms h a p ea n ds i z e so f t h et w os m a l lw i n d o w sa r ee n s u r e dt h r o u g he x p e r i m e n t s t h i r d l y , f o rp o o ro p t i m i z i n gs h o r t c o m i n g s o fd i s c r e t ep a r t i c l es w a r m a l g o r i t h m ，a ni m p r o v e dd i s c r e t ep a r t i c l es w a r ma l g o r i t h mi sp r o p o s e d t h ee l i t e g r o u pa n da d a p t i v em u t a t i o ns t r a t e g i e sa r ei n t r o d u c e dt oe n h a n c et h eo p t i m i z i n g 哈尔滨f ：释大学硕十学位论文 c a p a b i l i t yo ft h ea l g o r i t h m ，t h ee l i t eg r o u pi sm a d eu po fs e v e r a lh i g h f i t n e s s p a r t i c l e s ；m u t a t i o np r o b a b i l i t i e s a r ea d a p t i v ea n de n s u r e d b yt h ep a r t i c l e s c o n c e n t r a t i o n e x p e r i m e n t ss h o wt h a tc o m p a r i n gw i t hs i n g l eg e n e t i ca l g o r i t h m a n dd i s c r e t ep a r t i c l es w a r ma l g o r i t h mt h em i r r o r e ds t a c kf i l t e r so p t i m i z i n gb yt h e i m p r o v e dd i g i t a lp a r t i c l es w a r ma l g o r i t h md ow e l li nk e e p i n gt h ed e t a i l so ft h e o r i g i n a li m a g e s f o u r t h l y , c o n s i d e r i n g t h ee f f e c to ft h ei n i t i a ls w a r mt ot h e s e a r c h i n g c a p a b i l i t yo fa l g o r i t h m ，g e n e t i ca l g o r i t h mw h i c hd e m a n d sl e s so fi n i t i a ls w a r mi s e x p l o r e d ，t h ec r o s s o v e ro p e r a t i o nw h i c hi st h em a i ne f f e c t i v ef a c t o ro ft h e a l g o r i t h mi si m p r o v e d ：n e wp a r t i c l e sa r eg e n e r a t e db yc r o s s i n gf i n ep a r t i c l e sa n d p o o rp a r t i c l e sw h i c ha r ew i t hl a r g e rs i m i l a r i t ya n dw i t hl o w e rf i t n e s sc o m p a r e d w i t ht h ef i n ep a r t i c l e s ，t h es i m i l a r i t i e so fp a r t i c l e sa r em e a s u r e db yh a m m i n g d i s t a n c e s e x p e r i m e n t ss h o wt h a tc o m p a r i n gw i t hi m p r o v e dd i s c r e t ep a r t i c l e s w a r ma l g o r i t h mt h em i r r o r e ds t a c kf i l t e r so p t i m i z i n gb yt h ei m p r o v e dg e n e t i c a l g o r i t h mp o s eh i g h e rc a p a b i l i t yo fe r e a s i n gt h en o i s eo ft h eo r i g i n a li m a g e s f i n a l l y , i no r d e rt oi n c r e a s ed i v e r s i t yo fs w a l t na n de f f e c t i v e l ye n h a n c et h e g l o b a lo p t i m i z a t i o np e r f o r m a n c e ，c l o n a ls e l e c t i o na l g o r i t h mi s s t u d i e d t h e i m p r o v e m e n ti sa sf o l l o w ：p o l y c l o n a lo p e r a t o ri si n t r o d u c e dt om e m o r yg r o u p ，t h e r e o r g a n i z a t i o no ft h ep o l y c l o n a lo p e r a t o ra d o p t st h et h o u g h to f c r o s s o v e ro p e r a t o r i ni m p r o v e dg e n e t i ca l g o r i t h m ；m o n o c l o n a lo p e r a t o ri si n t r o d u c e dt or e s e r v a t i o n g r o u pa n dt h em u t a t i o no ft h em o n o c l o n a lo p e r a t o ra d o p t st h ea d a p t i v em u t a t i o n s t r a t e g yi nt h ei m p r o v e dd i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，i n a d d i t i o nt h e r ea r ee x c h a n g e so fi n f o r m a t i o nb e t w e e nt h et w og r o u p st oa v o i dl a t e e v o l u t i o n a r ys t a g n a t i o n e x p e r i m e n t ss h o wt h a tc o m p a r i n gw i t hi m p r o v e dg e n e t i c a l g o r i t h ma n di m p r o v e dd i s c r e t ep a r t i c l es w a r ma l g o r i t h mc a p a b i l i t i e so fe r e a s i n g n o i s ea n dk e e p i n gd e t a i l so fo r i g i n a l i m a g e so fs t a c kf i l t e r so p t i m i z i n gb y i m p r o v e dc l o n a ls e l e c t i o na l g o r i t h ma r eb a l a n c e d 哈尔滨t 程人学硕十学位论文 k e yw o r d s ：m i r r o r e dt h r e s h o l dd e c o m p o s i t i o n ；s t a c kf i l t e r i n g ；p a r t i c l es w a r m a l g o r i t h m ；g e n e t i ca l g o r i t h m ；c l o n a ls e l e c t i o na l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用已在文中指出，并与参考文献相对应。除文中 己经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者( 签字) ：题华 日期：硼彦年弓月fz 日 哈尔滨。i ：程大学硕十学何论文 第1 章绪论 1 1 镜像层叠滤波器的研究目的和意义 作为数字信号处理技术的主要代表，线性滤波器由于其数学表达形式简 单，具有某些理想特性，并且容易设计和实现，在数字信号和数字图像处理 的早期研究中被用作主要的处理手段。然而，自然现象和社会现象中涌现出 来的大量信号处理问题都是非线性的，例如在信号获取和传输过程中引入的 系统非线性，线性信号处理技术已经逐渐无法满足人们对信号处理的精度、 实时性和灵活性的要求。 为了满足更多、更高的信号处理需要，自2 0 世纪7 0 年代起非线性信号 处理便逐渐发展起来，成为研究学者共同关注的基础研究之一。2 0 世纪8 0 年代中期出现的层叠滤波器极大地促进了非线性滤波器的发展。层叠滤波器 是一类重要的非线性数字滤波器，优点主要体现在两个方面：1 ) 在理论上概 括了许多非线性数字滤波器，其中包括一大类排序统计滤波器和形态滤波器， 层叠滤波理论也已成为研究非线性数字滤波器的一种重要理论工具；2 ) 采用 阈值分解结构，通过阈值分解理论将对多值信号的研究转化为对相对简单的 二值信号的研究，这不仅解决了传统非线性滤波研究中的一些难点问题，例 如滤波器的输出统计分布，滤波器优化等，而且有利于并行处理和通过v l s i 技术实现。 基于传统阈值分解的层叠滤波器( 以下简称为传统层叠滤波器) 只是综合 了低通滤波的特性，只能应用于需要低通滤波特性的操作中。基于此原因， 国外学者又提出一种基于镜像阈值分解的新型层叠滤波器一镜像阈值分解层 叠滤波器( 以下简称为镜像层叠滤波器) 。与传统层叠滤波器相比，采用镜像 阈值分解技术的层叠滤波器是定义在镜像闽值分解二值域中，它不仅具有低 通滤波的特性，还具有带通和高通特性，使得层叠滤波技术不再局限于低通 哈尔滨r 程大学硕十学位论文 滤波领域，而是扩展到了许多要求带通和高通滤波性能的领域，例如均衡、 波束形成和系统识别等对带通滤波器要求严格的领域。传统层叠滤波器和镜 像层叠滤波器都是基于正布尔函数定义的一类非线性数字滤波器，由于滤波 结构元的多样性、正布尔函数的数目庞大，尤其是镜像阈值分解后正布尔函 数长度的显著增加，选择何种优化策略和算法高效地优化镜像层叠滤波器已 成为该领域的研究热点和难点。 基于上述分析可见，寻求高效快速的全局算法优化基于镜像阈值分解的 层叠滤波器是一个具有挑战性的课题。本课题的开展对层叠滤波器的发展起 到了促进作用，对跟踪国内外层叠滤波器的研究热点具有一定的学术价值， 对信号与图像处理、模式识别和计算机视觉等学科的发展产生积极的影响。 1 2 镜像层叠滤波器的国内外发展现状 层叠滤波器最早源于人们对中值滤波器的研究，j p a t r i c kf i t c h 等人川首 先于1 9 8 4 年提出并证明了中值滤波器具有层叠性和阈值分解性。随后，学者 们基于阈值分解和二值滤波函数，对多维信号阈值分解、递归和非递归中值 滤波器等进行研究聆一i 。1 9 8 6 年，p e t e rd w e n d t 等人h 1 对以上研究结果进行了 总结和概括，初步形成了以阈值分解性和层叠性为核心的层叠滤波器理论体 系，该理论以阈值分解性和层叠性为核心，定义了一大类包括排序统计滤波 器和形态结构滤波器在内的滤波器。层叠滤波器是由正布尔函数定义的，因 此对于层叠滤波器的根特性研究、最优化问题等都是围绕正布尔函数展开的。 8 0 年代末，p t y u 和k c h e n 分别通过图论对正布尔函数进行了研究d 刊。 通过研究不仅发现了正布尔函数的性质，而且说明层叠滤波器的种类是以指 数形式增长的，概括了类型十分广泛的非线性滤波器。j h l i n 等人还定义 了一类更加广泛的层叠滤波器，称之为广义层叠滤波器【7 】，广义层叠滤波器 的二值滤波函数也要求满足层叠性，但并一定为正布尔函数。a k i r at a g u c h i 于1 9 9 9 年将层叠滤波器概念进一步扩展，提出了含盖广义层叠滤波器和f i r 滤波器在内的模糊层叠滤波器概念及其设计方法【l 】。在过去的十几年中，传 2 哈尔滨f ：稃大学硕十学何论文 统层叠滤波器在信号处理领域中得到了相当大的关注p j ，但由于它只综合了 低通滤波的操作，在需要带通和高通滤波操作的应用中受到了很大的限制0 1 。 此后阈值分解的概念进一步扩展，延伸为镜像阈值分解，文献 1 0 】对镜像阈 值分解理论和镜像阈值分解基础上的层叠滤波器作了系统的介绍，p a r e d e s j l ，a r c eg r 等人对镜像层叠滤波器的统计特性和优化做出一定研究。 随着层叠滤波器理论的发展，关于层叠滤波器硬件实现的研究也成为人 们关注的热点。1 9 8 9 年k c h e n 首先研究了基于正布尔函数的层叠滤波器并 行实现问题，l e l u c k e 于1 9 9 2 年提出了层叠滤波器的v l s i 实现方案，1 9 9 5 年d a k o p i a n 设计了广义层叠滤波处理器钔。 2 0 世纪8 0 年代后期和9 0 年代初，借助于统计估计理论、自适应理论和 随机噪声理论，越来越多的人开始研究层叠滤波器的最优化问题。e d w a r dj c o y l e 、j e a n h s a n gl i n 、g a b b o u j m 和w i n l o n gl e e 等人先后基于m a e 准 则进行了层叠滤波器的优化研究5 。9 i ，也有一些学者提出基于m s e 等准则口蚴1 进行层叠滤波器的优化设计。在实现最优化算法上，u n d r i l l ，p e 和d e l i b a s s i s k 于1 9 9 6 年首先提出采用遗传算法对层叠滤波器进行优化设训2 4 1 ，常用的全 局优化算法还有模拟退火算法、遗传算法、禁忌搜索算法和粒子群算法等 1 2 5 - 2 6 ) 。目前，应用自适应算法和遗传算法设计最优层叠滤波器的研究正在兴 起，同时，层叠滤波器最优化实现的其它算法，如图搜索算法、目标函数法、 模糊集合法等也开始出现。解决最优化问题的另一个重要方法是采用结构元 约束最优层叠滤波器，由样本点组成的集合称之为结构元，结构元也称作 滤波子窗，是对原有滤波窗内元素的一种划分。m o n c e fg a b b o u j 、p k u o s m a n e n 、j a s t o l a 等人旺8 训在这方面取得了重要进展。 在实际应用领域，除了从噪声信号中恢复原始信号以外，层叠滤波器还 被应用于图象边缘提取，产品缺陷检测等方面，p e u n d r i l l l 3 2 - 3 5 1 还将其成功 地应用于医学诊断处理中。 国内对层叠滤波器( 最初被称为堆栈滤波器) 的研究起步相对较晚，目前 哈尔滨一1 j 稃人学硕十学位论文 国内对层叠滤波器的研究仅限于基于传统阈值分解的层叠滤波器方面。1 9 9 7 年出版的非线性滤波器与数字图象处理一书中，陈贺新教授第一次引入 国外层叠滤波器的研究成果( 该书中称之为级叠滤波器) 。南京大学的周性伟， 叶万洲的等人【3 7 1 研究了连续层叠滤波器的基本理论及其广义化和判决准 则，兰州大学的马义德等学者p 8 1 提出了结构元约束的最优层叠滤波器和混合 滤波器的设计，王伟对层叠滤波器理论和算法进行了一定的研究，在层叠加 权中值滤波器p 9 i ，基于层叠处理的多级自适应w o s 滤波器，结构元约束算 法越1 等方面取得了一定的研究成果。王伟、孙圣和h 3 舶1 等对二维结构元约束 层叠滤波器进行了优化设计。张文成、孙莉、崔颖等人对传统层叠滤波器的 实现、优化理论及算法做出了一定的研究h 5 枷1 。在层叠滤波器应用和实现方 面，吴东等人讨论了如何用f p g a 实现传统层叠滤波器h ，黎明等人p 0 1 则研 究了基于传统层叠滤波的边界检测方法。 1 3 课题内容介绍 作为国家自然科学基金资助项目( 6 0 6 7 2 0 3 4 ) ，本文在深入研究现有传统 层叠滤波器优化理论和算法的基础上，主要围绕镜像层叠滤波器的优化理论 和算法开展研究工作，对新兴的仿生群体智能优化算法在镜像层叠滤波器中 的应用和改进进行了研究，主要内容如下： 第l 章为绪论，介绍了镜像层叠滤波器研究的目的和意义，简要阐述和 总结了国内外层叠滤波技术的发展状况，同时给出了本文的主要工作内容。 第2 章介绍了镜像层叠滤波器的基础理论，首先从j 下布尔函数的层叠性 和阈值分解性以及与传统层叠滤波器的区别入手，然后给出定义镜像层叠滤 波器的正布尔函数的随机生成算法以及滤波图像的快速重建，随后介绍了评 价图像处理效果的标准，本文镜像层叠滤波器的优化模型建立于平均绝对值 误差准则之下，最后介绍了传统层叠滤波器优化中采用的相关优化算法。 第3 章介绍了离散粒子群算法对镜像层叠滤波器的优化设计，其中包括： 标准粒子群算法及本文改进的离散粒子群算法的介绍：本文改进的离散粒子 4 哈尔滨1 祥人学硕十学俜论文 群算法如何优化镜像层叠滤波器。为了降低镜像层叠约束的计算量，文中引 入了一种二级小窗口级联递归滤波方式。最后通过仿真实验验证了算法的性 能，其中包括：两级小窗口的形状与尺寸的设计选取，改进离散粒子群算法 中各个参数的选取，以及不同算法设计的镜像层叠滤波器的性能比较。 第4 章介绍了遗传算法及其改进算法对镜像层叠滤波器进行的优化设 计，其中包括：简单遗传算法的介绍，遗传算法的重要因子，遗传算法早熟 原因的分析及常用改进措施。针对定义镜像层叠滤波器的正布尔函数的特点， 提出本文的改进遗传算法。最后，通过实验比较了改进离散粒子群算法与改 进遗传算法优化的镜像层叠滤波器的性能。 第5 章介绍了镜像层叠滤波器的另一种快速仿生优化算法一克隆选择算 法，其中包括：标准克隆选择算法及改进克隆选择算法的介绍，改进克隆算 法如何优化镜像层叠滤波器。最后通过仿真实验对比和分析了不同算法优化 的镜像层叠滤波器的性能。 最后给出本课题的总结，归纳了一年多来在对镜像层叠滤波器优化算法 研究上所作的工作，并对可进一步开展研究的方向提出个人看法。 哈尔滨r 稃大学硕十学待论文 第2 章镜像层叠滤波器的基本理论 2 1 引言 层叠滤波是基于信号阈值分解发展起来的一种新型数字滤波技术，它的 出现使人们可以从另一角度来重新认识许多非线性滤波器。每一个层叠滤波 器对应于一个正布尔函数，层叠滤波器的优化设计、性能分析等都是围绕正 布尔函数展丌的。基于传统阈值分解的层叠滤波器称为传统阈值分解层叠滤 波器，基于镜像阈值分解的层叠滤波器称为镜像阈值分解层叠滤波器，镜像 层叠滤波器定义了一类更广泛的数字滤波器，突破了传统闽值分解的概念， 在频率选择和滤波性能等方面都有提高。因此，本章首先对镜像层叠滤波器 的正布尔函数的相关性质进行了介绍，然后结合正布尔函数的定义给出镜像 层叠滤波器的数学表达式，接着简单介绍了镜像层叠滤波器的层叠性约束方 法和输出信号产生算法，最后介绍了层叠滤波器的相关优化算法。 2 2 镜像层叠滤波器的基本理论 2 2 1 阈值分解性和层叠性 镜像阈值分解不同于传统阈值分解，基于镜像阈值分解的层叠滤波器不 仅具有低通特性，还具有带通和高通性能，增强了滤波器的频率选择能力。 镜像阈值分解定义如下： 假设x = 防。，x ：，x 】是一个长度为n 的多值信号向量，这里的 z q ，并且q = 一m ，0 ，m ) ，向量x 的镜像阈值分解信号由两部分 组成，每部分由2 m 个二进制向量组成。第一部分与传统阈值分解的定义相 关，即： x m ，x 0 ，x 彳 这里x ”的第f 个元素的定义如下： 6 哈尔溟i ：祥入学硕十学伉论文 和兀五) = 二1乞? ，历q ( 2 ) 第二部分由镜像向量s 的阈值分解信号构成，x 的镜像向量s 定义为： s = 【s i ，s 2 ，s 】= 卜x l ，一x 2 ，一x 】 s 的阈值分解产生了分解信号s 一肘+ 1 ，s o ，s 肘，这里s m 的第i 个元素的定 义如下： 牡邢) = 二，乞翟，m q ( 2 - 2 ) 由上可知，一个整数值信号x 由唯一的镜像阂值信号表示，反之亦然。 x ，盟- 融i ，j ；，) ) 这里卜丝鲨一表示的是镜像阈值分解操作的一对一的映射。因此，初始 整数信号x 能够从它们的二值信号中准确地恢复出来。 置= 去z ， ( 2 3 ) 定义2 - l ：长度为的矢量x 和y ，如果对于任意的i 1 , 2 ，n ) ，x ，z ， 则称x y 。对于矢量序列x ，x 2 ，x m ，若x j x 2 x ，称矢量 序列具有层叠性。 根据信号阈值分解及层叠性定义，显然经过镜像阈值分解的二进制信号 向量中的每一组二进制向量序列都服从层叠性，即 【x ；s 】【x7 ；s7 】，力，f j ( 2 - 4 ) 其中f ，表示两个不同的镜像闽值， x 。；s 1 i x ，；s ，】 一1 ，1 ) 2 表示该镜像阈 值分解下的向量。 此外，如果陋。；s 1 和 x j ；s 7 】这两个二值向量之间的汉明距离为1 ，即 ( 【x ；s 】，【x ，s 切= l ，那么这两个二进制向量就满足镜像局部层叠性，即： x ：x ：，j ：j k = l ，2 ，n 且h ( x 。；s ，】 x 。，s 。】) = l( 2 - 5 ) 层叠性是层叠滤波器定义的核心，无论对于层叠滤波器的理论分析还是 硬件实现都具有重要作用。 7 哈尔滨1 ：程大学硕十学倚论文 2 2 2 镜像阈值分解的输出信号 镜像阈值分解输出长度为2 n 的二值向量( 为滤波窗口长度，2 n 为镜像 阈值分解输入信号向量长度) ，但不是所有2 2 种可能的二值向量都会出现在 阈值分解的输出端。由于向量x 和镜像向量s 之间的相关性，二值分解向量 k ；s 】的某些分量被限制，例如【x ；s = 【五，x 2 ，x 3 ；s l ，s 2 , j 3 】= - i ，- 1 ，1 ；- 1 ，一l ，1 】， 这个二值分解向量就不会出现在镜像阈值分解的输出端，因为这个二值分解 向量表示对于一个给定的镜像分解阈值m ，存在x ， m ，s i m ，x 2 0 ，那么这个二值向量不会出现在镜像阈值分解的输 出端。可以通过反证法来证明定理2 1 的j 下确性。证明见参考文献 4 8 】。 定理2 1 给出了满足何种条件的二值向量不会出现在镜像阈值分解的输 出端，下面的定理2 2 给出了镜像阈值分解端输出二值向量的数目。 定理2 2 ：对于一个滤波窗口尺寸为的镜像阈值层叠滤波器，镜像阈值分 解输出端输出长度为2 n 的二值向量的个数为n = 2 ( 3 ) 一2 。 证明：首先证明不能由镜像阈值分解产生的二值向量的数目f 4 8 1 。 k ；s 】= k ，x 2 ，x ；& ，s 2 ，s ，】是包含2 个分量的二值向量，根据定理 2 1 可知，那些不出现在镜像阂值分解输出端的向量应满足：w ( x 人s ) 0 且 雌 i ) 0 。设k 为集合 x 1 , x 2 ，x ) 中元素为一1 的个数。 8 哈尔滨i i j 掣大学硕+ 学位论文 当k 2 1 时，对于栗个i l ，2 ，n ) ，存在x f = 一1 ，那么对于所有的二值 向量而言，满足下述条件的不会出现在输出端，即量= - i 且至少存在一个 j 0 , 2 ， ，使得s ，= + l ( 其中f ) ，共有2 一1 个。 因为f 为 l ，2 ， 中的任意值，所以有f ? 1 ( 2 - i 1 ) 个二值向量不会出 现在镜像阈值分解的输出端，这些二值向量前面的n 个分量中含有一个一1 。 当k = 2 时，对于某个i ，z 1 , 2 ，n 且i l ，存在x ，= - 1 和x t = - 1 。如 果分量【s i , s ，】为 一1 , - 1 】， 1 ，- 1 】， - 1 ，1 】，且至少存在一个j 1 , 2 ，n ) 使得 j j = + 1 ，其中歹i ，歹，满足上述条件的二值向量不会由镜像闽值分解 产生，共有( 2 一1 x 2 2 1 ) 个。因为i 和，是 1 ，2 ，) 中的任意值，且f ，。 所以有f ? 1 ( 2 肛2 1 x 2 2 1 ) 个二值向量不会出现在镜像阈值分解的输出端， - ， 这些二值向量前面的n 个分量中含有两个一1 。 类似方法可推导出，当3 七一1 ，有( ：) ( 2 n - k _ 1 x 2 七一1 ) 个二值向量 不出现在镜像阈值分解的输出端，这些二值向量前面的n 个分量中含有k 个 一1 。将k = 1 ，2 ，n 一1 所有二值向量的数目相加，可以得出不能由镜像阈 值分解产生的二值向量的数目； n 烈- i f n 七尸 、一1 ) ( 2 n - 七- 1 ) 那么可以出现在镜像阈值分解输出端的二值向量的数目为 = 2 2 一善( ：) ( 2 一) ( 2 一t 一) ( 2 6 ) 根据二项式理论可以得到 = 荟n ( 七 2 2 “一一备n - 1 ( n 后) ( 2 一) ( 2 一 一) = 2 ( 2 ) + 2 薯( ：) 2 一蕃( ：) 因为n - 1 n ) 2 纠_ 2 _ 1 ，n 备- i ( n 七) 纠_ 2 ，代入上面的表达式中，可以 得到n ：2 ( 3 u ) 一2 n 。 9 哈尔滨f r 平人学硕十学位论文 2 2 3 正布尔函数及镜像层叠滤波器的定义 定义2 - 2 ：一个具有输入的布尔函数厂： 一1 ，1 ) j 一l ，1 ，当且仅当其任意 两个包含n 个分量的二值输入向量x = i x 。，x ：，x 】和y = 陟。，y ：，y 】满 足任意分量一y ，f l ，2 ，) ，其输出一定为厂( x ) 厂( y ) 时，称此布尔 函数为正布尔函数( p b f ) ，或者称此布尔函数具有层叠性。 与传统层叠滤波器相比较，镜像阈值分解定义了更广泛的非线性滤波器 体系一镜像层叠滤波器。 定义2 - 3 ：已知向量x = 皿，x ：，x p 】，其中的元素x ， - m ，o ，m ， 所对应的镜像阈值分解信号为i xs 】肌1 ，k s 】o ，k ；s r ，则镜像层叠滤波 器的输出定义如下： 1m q ( x ) = 去厂( z ，x 多，x 多；s ，j ? ，s 多) ( 2 7 ) 厶坍= 一 彳+ l 由定义2 - 2 和2 3 可得，镜像阈值分解的层叠滤波器可通过查找表来定 义，即当滤波窗长为时，镜像层叠滤波器可定义为有n = 2 ( 3 ) 一2 个输 入的真值表，每一个输入对应着一个可能的输出。在这种情况下，正布尔函 数厂( ) 可以表示成一个长度为+ 的向量d d = 【d i ，d 2 ，d 】= f ( x i ) ，f ( x 2 ) ，f ( x ) 】 ( 2 - 8 ) 这里的d ，= f ( x ，) 一l ，+ 1 ) 满足局部层叠特性，x ， 一l ，+ 1 ) 2 是那些出现在 镜像阈值分解输出端的长度为2 n 的二值分解向量。 2 3 镜像层叠滤波器输出信号的快速重建 由镜像层叠滤波后输出信号的层叠性可知，滤波器输出的滤波器信号正 是二值信号从1 变成一1 或者由一1 变成l 跃变时的阈值，因此与传统阈值分 解层叠滤波器相似，在正布尔函数真值表已知的情况下，滤波器输出信号的 重建方法仍采用判断是否发生由1 到一l 或者一1 到1 的跃变，即首先对噪声 图像取滤波向量，取得滤波向量后对信号值在一m + l 到m 之间进行镜像阈 l o 哈尔滨下程大学硕十学位论文 值分解，该分解以串行方式丌展，然后就分解后的二值信号求出正布尔函数 真值表对应的二值输出，求出镜像层叠滤波输出后的二值信号后，判断其是 否发生由l 到一1 或者一l 到l 的跃变，如果跃变则停止分解并认为此时的镜 像阈值为滤波器输出的像素值。该快速算法可以最大程度上减少阈值分解次 数，重建输出图像。算法具体的实现如下所述： 1 ) 对于变化范围是卜m ，mi 的信号，初始化阈值分解的上边界值 u p p e r b o u n d = m 和阈值分解的下边界值l o w e r b o u n d = 一m + l ，设置中间值 t = ( u p p e r b o u n d + l o w e r b o u n d ) 2 j ，在，处对所截取信号向量镜像阈值分解， 得到一个二值分解向量口，由j 下布尔函数真值表查找出对应的输出值厂( 口) ； 2 ) 如果厂【口) = l ，令，d w e r b o u n d = ，新，的值由上述计算公式重新计算 得到；若厂【口) = - 1 ，则u p p e r b o u n d = t ，同样公式重新计算，然后计算新， 处阂值分解向量口，求出此时输出厂( 口) ； 3 ) 若u p p e r b o u n d - l o w e r b o u n d 1 ，则重复( 2 ) ；若等于1 ，则l o w e r b o u n d 为镜像层叠滤波器输出的滤波信号。 显然，与传统的叠加重建法即对噪声图像取窗口像素值，然后对窗口元 素值在一m + l 到m 之间进行阈值分解，接着求出分解后的二值信号对应的 正布尔函数真值表的二值输出，最后将所求得的结果相加后再与输出的像素 值相比较，本文的快速重建方法由于进行较少的镜像阈值分解，且无需叠加 从而提高图像重建的速度。 2 4 正布尔函数的随机生成算法 镜像层叠滤波器是由f 布尔函数定义的，因此只要能确定定义镜像层叠 滤波器的正布尔函数，便确定了镜像层叠滤波器。实际上，对于镜像层叠滤 波器的最优化，是在众多正布尔函数中搜索能使误差标准达到最小的j 下布尔 函数，要利用诸如遗传算法、模拟退火算法等全局化优化算法对镜像层叠滤 波器进行优化，因此首先面临的问题就是如何随机生成初始种群或者个体以 用于优化。由于正布尔函数可以用一个二值向量表示，如果我们能随机生成 正布尔函数的真值表向量，便可随机生成满足需要的正布尔函数。 由上文可知，布尔函数可由向量d 表示，因此随机选取l 或者一1 ，便 可得到随机布尔函数，但这样得到的布尔函数不一定是正布尔函数，需要做 两方面的调整：1 ) 镜像阈值分解输出端不存在的二值向量对应的布尔位置为 0 ；2 ) 需要对向量d 进行层叠性判断和约束，并且1 ) 中提到的布尔位置无需 进行层叠约束，算法阐述如下： 对于输入变量为2 n 的布尔函数，将随机生成的布尔函数向量d 进行2 n 次层叠性判断和约束后，得到的布尔函数向量即表示一个正布尔函数。假设 第七次约束后得到的向量为d 2 = ( d ? ，d ；，d ：) ，式中部分= f ( v ，) ，其 中v ，为镜像阈值分解端的输出信号，部分d ；= 0 ，其位置对应镜像阈值分解 端不存在的输出信号。层叠性判断和约束规则如下： 如果f ，满足一扛2 扣1 ，且f ，均对应镜像阈值分解端的输出信号，对 于输入向量v ，v ，满足“( v ，) = l 有 d ；，则 体譬 如果f ，_ ，其一对应镜像阈值分解端不存在的输出信号，则，d ；