（计算机软件与理论专业论文）基于内容的商标图像分层检索算法研究与实现.pdf

基于内容的商标图像分层检索算法 研究与实现 计算机软件与理论 硕士生：严芬 指导教师：李才伟副教授 摘要 商标图像检索是商标注册过程中商标查重的重要手段之一。本文对基于内容 的商标图像检索技术和主流算法进行广泛深入的研究，继而提出了一种自适应的 商标图像分层检索算法。针对商标图像的特殊性，本文首先定义了六个对旋转、 缩放、平移和反色变换具有不变性的全局特征，给出其提取算法；通过特征组合 提供了4 种备选的粗分算法；对用户提交的查询示例，算法首先利用自适应的分 支选择子算法对图像进行特征显著性分析，然后自动调用最佳的租分算法进行第 一层检索，滤除图片库中那些明显不相似的图像；对余下的图像，再利用距离分 布直方图进行第二层的精确匹配。 该算法的主要创新点在于：基于形状特征的自适应的分层检索方法；针对商 标图像的六个显著视觉特征的定义与提取；提出算法对反色变换的鲁棒性。 作为算法的测试平台，本文用v c + + 编程实现了一个基于示例查询的商标图 像检索系统，图片库中收集了1 4 0 0 余张标准商标图案。算法测试部分通过四组 实验，并与h u 不变矩方法和距离分布直方图方法进行对比，证明本文算法合理、 有效，同时对图像旋转、缩放、平移和反色变换具有很好的不变性。 关键词：基于内容的商标图像检索，分层检索，自适应，距离分布直方图 r e s e a r c ha n di m p l e m e n t a t i o no fh i e r a r c h i c a lm e t h o df o r c o n t e n t - b a s e dt r a d e m a r ki m a g er e t r i e v a l c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ；y a n f e n s u p e r v i s o r ：l ic a i w e i a b s t r a c t i nt h i sp a p e r , ah i e r a r c h i c a lm e t h o dw a sp r o p o s e df o rc o n t e n t - b a s e db i n a r y t r a d e m a r ki m a g er e t r i e v a l f i r s t ，s i xg l o b a lf e a t u r e s ，w h i c hr o b u s tt or o t a t i o n ，z o o m , t r a n s l a t i o na n dc o l o rr e v e r s i o n ，w e r ed e f i n e da n da b s t r a e t e d t h e nf e a t u r e sw e r e e n m b i n e da sf o u rc a n d i d a t e so ft h ef i r s t s t a g ec l a s s i n ga l g o r i t h m w h e na ni m a g e e x m n p l ei ss u b m i t t e d t h es d f - a d a p t i v e - b r a n c h c h o o s ea l g o r i t h mw i l lb ec a l l e dt o 曲 f e a t u r ea n a l y s i sa n dc h o o s et h eo p t i m a lc l a s s i n ga l g o r i t h mf l o r at h ef o u rc a n d i d a t e s a c c o r d i n gt ot h es a l i e n c eo ft h ef e a t u r e s t h i si st h ef i r s tr e t r i e v a lh i e r a r c h y , m o s t u n l i k ei m a g e si nd a t a b a s ew i l lb ee x c l u d e di l lt h i ss t a g e , a n dt h el e f to n e sw i l lb e r e f i n e db yt h es e c o n d h i e r a r c h y r e t r i e v a l ，w h i c h w i l lb e d o n eb y d i s t a n c e - d i s t r i b u t i o n - h i s t o g r a mm e t l l o d i n n o v a t i o n so ft h ep r o p o s e dm e t h o da r ef o l l o w s ：f i r s t , as e l f - a d a p t i v eh i e r a r c h i c a l r e t r i e v a lm e t h o db a s e do ns h a p ef e a t u r e s s e c o n d ，t h ed e f i n i t i o na n da b s n a c t i o no f s m n o t a b l ef e a t u r e s a c c o r d i n gt ot h ep a r t i c u l a r i t yo ft r a d e m a r ki m a g e s t h i r d ，t h e d e c l a r a t i o na n di m p l e m e n to f a l g o r i t h m sr o b u s tt oi m a g ec o l o rr e v e r s i o n a q b es y s t e mw a sb u i l t 鹪t h ea l g o r i t h mt e s t i n gp l a t f o r m i n c l u d i n ga l li m a g e d a t a b a s ec o m p o s e do f1 , 4 0 0s t a n d a r dt r a d e m a r ki m a g e s f o u re x p e r i m e n t sw e r e d e s i g n e da n di m p l e m e n t e dt op r o v et h ev a l i d i t ya n dm t m n a l i t yo ft h em e t h o d p r o p o s e di nt h i sp a p e r k e y w o r d s ：c o n t e n t - b a s e dt r a d e m a r ki m a g er e t r i e v a l 、h i e r a r c h i c a lr e t r i e v a l 、s e l f - a d a p t i v e 、 d i s t a n c e - d i s t r i b u t i o n - h i s t o g r a m “i 第1 章引言 在商标申请过程中，审查待注册商标与己注册商标的重复性、相似性是鉴定 一个商标是否具有注册资格的前提。商标图像检索是实现商标查重的重要手段之 _ ，其目的是找出相近似或者相同的商标，为商标排查工作提供判断依据。近年 来，商标申请数量的激增为商标排查工作带来了难度，也提出了更高的要求。 商标的鉴别主要针对商标显著特征进行，主要体现在商标图案设计上。商 标图像检索主要有类目检索、文本检索和基于内容的检索等三种技术。目前的商 标图像查重主要通过类目浏览查询和文字查询方式实现，适用于纯字符商标和 那些具有完备说明的商标，而对于一些纯图形、缺少完整注释的商标而言，要检 索这类商标变得困难，目前般采用图像要素编码法，或者是集成基于内容的 图像检索技术来实现 ”。随着商标数目的不断增长，类目检索和文本检索的弊端 逐渐显露，一方面手工分类的人工消耗比较大，而且分类、标引的一致性不易保 证。另一方面，一些抽象商标图像既不易归类，也不易通过文本方式来描述。针 对这些不足，人们考虑将基于内容的图像检索技术应用于商标图像的检索中， 以实现更直观、客观的商标检索。 本文对基于内容的商标图像检索技术和主流算法进行广泛深入的研究，继而 提出了一种新的自适应的商标图像分层检索算法。针对商标图像的特殊性，首先 定义了六个对旋转、缩放、平移和反色变换具有不变性的全局特征，给出其提取 算法；通过特征组合提供了4 种备选的粗分算法；对用户提交的查询示例，算法 首先利用自适应的分支选择子算法对图像进行特征显著性分析，然后自动调用最 佳的粗分算法进行第一层检索，滤除图片库中那些明显不相似的图像；对余下的 图像，再利用距离分布直方图进行第二层的精确匹配。 本文算法的主要创新点在于： ( 1 ) 基于图像形状特征的自适应的分层检索方法，在粗分和细分两个层次 上对图像进行深度不一的匹配，自适应的分支选择算法根据查询示例的特征显著 性，自动调用最佳的粗分算法，无需用户干预； 中山人学坝i 学位论立第1 章0 i ； ( 2 ) 针对二值商标图像的特殊性，定义了背景色、最小约束矩长宽比、实 一t b 度、紧密度、复杂度、圆形性等六个显著视觉特征并给出有效的提取方法； ( 3 ) 提出算法对反色变换的鲁棒性。在图像检索中检索算法对变换的鲁棒 性是度量算法性能的一个重要指标。目前的二值商标图像检索算法只考虑了算法 对旋转、缩放、平移等变换的不变性，而忽视了对图像反色变换的不变性，在处 理时假定图像为白色背景黑色目标物体，对于黑色背景白色目标的图像无法处 理，本文对此进行改进。 作为算法的测试平台，本文用v c + + 编程实现了一个基于示例查询的商标图 像检索系统，图片数据库采用s q ls e r v e r2 0 0 3 实现，图片库中收集了1 4 0 0 余 张标准商标图案。系统功能包括用户查询示例的提交、5 种图像预处理方法、分 别针对示例图像和图片库的8 种特征的提取算法、2 种特征向量归一化方法、2 种相似距离计算方法、自适应的分支选择子算法、基于样本统计的特征显著性值 域划分方法、4 种粗分算法、基于距离分布直方图的细分算法以及集成的自适应 分层检索算法。此外还留有测试项，可以直接对数据库表中的图片记录进行编辑， 也可以方便的添加其他的检索算法。作为本文算法的对比实验，系统也实现了基 于h u 不变矩的检索算法和单层的距离分布直方图检索方法。系统功能较完备， 实验证明已经具备一定的实用价值。 算法测试部分设计了四组实验，选用命中率、查全率、相对查全率和基于排 序的查准率作为检索性能的评价指标，并与h u 不变矩方法和单层的距离分布直 方图方法进行对比。实验证明本文算法合理、有效，同时对图像旋转、缩放、平 移和反色变换具有很好的不变性。 2 第2 章基于内容的商标图像检索 本章对基于内容的商标图像检索( c o n t e n t b a s e dt r a d e m a r ki m a g e r e t r i e v a l ，以下简称c b t i r ) 的研究现状做一个综合性的整理和描述。着重归结 相关算法中几种基于形状特征检索的研究思路。最后针对当前c b t i r 的研究障 碍，对几种解决方法作了一个分析和比较。 2 1 商标检索技术综述 商标检索技术根据其检索机理可以分为类目检索、文本检索和基于内容检 索。 2 1 1 基于类目检索商标 目前，类目检索是实践中使用最为普遍的方式之一，通过等级式分类目录 对不同行业不同领域的产品和服务进行分类和组织，并提供基于类目的浏览查 找。著名的商标国际分类通用标准有有关商标注册用商品和服务国际分类的尼 斯协定( 简称尼斯协定，n i c ec l a s s i f i c a t i o n ) ，我国在1 9 8 8 年以前采用 的是国内分类法，自1 9 8 8 年1 1 月开始采用尼斯国际分类。尼斯分类包括4 5 个 大类，其中商品3 4 类，服务项目1 1 类，共包含一万多个商品和服务项目。同 时为了对包括图形要素的商标建立分类，另有建立商标图形要素国际分类的维 也纳协定( 简称维也纳协定，v i e n n ac l a s s i f i c a t i o n ) 2 1 ，用于对图形要素 进行编码分类显示，该分类由商标图形要素按大类、小类及组分类的一览表组成， 并根据情况加以注释。所有分类包括2 9 个大类，下面设有子类，如“3 1 1 4 a ” 表示动物类中的熊猫图像，“2 9 1 5 ”表示颜色类中的紫色。基于类目检索商标 是目前商标申请过程中主流的检索方式。 2 1 2 基于文本检索商标 采用自由词、关键词检索的方式，根据商标被标识的特征字段进行查找，并 中山人学坝i + 学位论文第2 章皋十内容的商标幽像柃索 可使用简单的布尔操作符连接查询词，构造查询表达式。如美国联邦政府注册商 标库( t r a d e m a r ks c a nf e d e r a l ) 通过d i a l o g 提供检索，检索功能包括特征字 段检索、布尔逻辑检索、截词检索、号码检索 3 】o 又如中国商标数据库网站【4 】提 供的检索功能，结合类目和文本查找，查找字段包括注册号、中文、拼音英文、 商品n 务名称、日文片假名、商标所有人、图形要素。图形要素根据维也纳协 定中的号码规则书写。文本检索的实质是字符串匹配原理，通过对商标特征的文 本描述，建立索引，实现提问与特征标识的匹配。文本检索方式比类目浏览能够 更快速地定位所需要查找的对象，使用方便。不过类目检索与文本检索般是相 互结合和促进的，类目的组织为自由词、关键词检索提供了数据组织的基础。 2 1 3 基于内容检索商标 随着商标数目的不断增长，前两种检索的弊端逐渐显露，一方面手工分类 的人工消耗比较大，而且分类、标引的一致性不易保证。另一方面，一些抽象商 标图像既不易归类，也不易通过文本方式来描述。针对这些不足，人们考虑将基 于内容的图像检索技术应用于商标图像的检索中，以实现更直观、客观的商标检 索。基于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ，以下简称c b i r ) 始于二十世纪九十年代，因此，以基于内容检索方式查询商标图像也属于较晚 兴起的研究，该领域的早期研究之一是1 9 9 2 年同本的t k a t o 建立的商标形状 检索系统。c b t i r 根据商标图像的内容特征来匹配，如商标图案的色彩、图像中 某个对象的形状等。目j ；i 主要实现的是对低层可视化特征的提取和表示上。目的 是更好地满足对图形商标、组合商标，以及那些因为各种原因缺失了完备说明的 商标的检索需求，这类商标难以通过文本形式得到很合适的描述。采用基于内容 的方式检索商标，需要提取并标出商标图像显著的可视化特征，通常采用形状、 颜色特征，然后与已有商标图像的特征库匹配，根据两个商标图像的可视化相 似程度判断它们是否具有雷同嫌疑，检索原理如图2 - 1 所示。基于内容检索一般 采用q b e ( q u e r yb ye x a m p l e ) ，用户可提交图像示例，根据示例的特征查找与 之相似的其它图像。基于内容的商标检索同样可以实现基于示例的检索。 4 中山人学顾 ：学位论文 第2 章基f 内容的商标图像榆索 l 待注册商标 _ - + 特 征 提 取 和 表 i 已注册商标r _ + 一 不 2 2c b t i r 研究现状 相 超过闻值i 似 。l 距7 i 离 的 低于阙值i 计 。l 算 7 i 图2 一l 基于内容的商标检索原理 基于内容的图像检索始于二十世纪九十年代，因此，以基于内容检索方式 查询商标图像也属于较晚兴起的研究。目前成熟的系统尚不多见，引用率比较高 的有a r t i s a np r o j e c t l 5 1 以及卡内基梅隆大学开发的t r a d e m a r k 系统【6 】。e a k i n s 等 开发的a r t i s a n 系统抽取和分析商标组成部分的边缘特征，计算整体图像的形 状特征向量与查询示例对应特征向量之间的距离，对象对应的判断依据是形状、 大小和位置信息。1 9 9 8 年e a k n s 等又继续完善a r t i s a n ，并以英国国家商标注 册库的1 0 ，0 0 0 个商标图像为试验集合加以检验和效果评价【刀。t r a d e m a r k 系统 是2 0 0 2 年由卡内基梅隆大学开发的，采用局部匹配，强调对商标图像内部对象 的个体特征分析。将商标图像中的对象划分为圆、多边形、线条，对这些对象分 别匹配。 关于c b t i r 算法，早期的研究大多是基于图像的颜色和形状特征的，本文认 为，形状是商标图像的最显著特征，所以研究范围也仅限于基于形状特征的匹配。 基于形状检索的研究有两种思路，一种是全局匹配，另一种是局部匹配。 全局匹配强调对整体图像的形状、轮廓特征分析。通常的形状表示法有傅立 叶描绘子、形状无关矩。c o r t e l a z z o e t a l 【8 】采用串匹配技术描述商标图像的 形状特征。l a i n1 9 1 使用无关矩、傅立叶描述子描述图像形状特征。e a k i n s 等 开发的a r t i s a n 系统抽耿和分析商标组成部分的边缘特征，计算整体图像的 形状特征向量与查询示例对应特征向量之白j 的距离，对象对应的判断依据是形 团困团口 中山人学硕i ：学位论文第2 章攮十内容的商标图像榆索 状、大小和位置信息。马跃先等【l o l 基于七个h u 不变矩和街访距离计算二值商 标图像的相似度，没有对变形问题更多考虑。j a i n 和v a i l a y a 【1 1 】则不仅利 用了七个h u 不变矩和边沿方向特征，还使用变形模板匹配对商标实行分级检索。 俞勇等【1 2 采用字符串分类法、最小约束矩筛选法和点匹配法，从三个层次实 现对商标图像相似度的综合判断。k i m 和k i m 【1 3 】利用的是z m m s 矩描绘图像。 z h a n g 【1 4 1 提出动态形状匹配，使用8 维链码来描述二值图形。j a ul i n gs h i h 和 l i n gh w e ic h e n 【1 5 1 利用两种变形参数、形状无关矩和边缘直方图四类特征柬 刻画商标图像，并对这四类分别加权计算整体相似度。 另一种思路是局部匹配，强调对商标图像内部对象的个体特征分析。a l w i s 【1 6 1 将商标图像中的对象划分为线条、角、封闭圆，对这些对象分别匹配，与 之相似的做法是卡内基梅隆大学开发的t r a d e m a r k 系统 6 1 ，不过后者采用了不 同的分类，分为圆、多边形、线条。周丽华等【1 7 根据信息论中熵的概念，提 出商标图像的单元信息熵，基于单元熵矢量的欧氏距离计算相似度，避免图像 整体熵对位置信息的欠缺。黄元元等【1 8 1 利用形状与空b j 位置特征来检索二值 商标图像，检索也是以图像中对象为单元，根据形状判断两个图像日j 的对应对 象。然后根据对应对象的空间位置的距离计算两者的相似度，侧重于对商标图像 内部对象的捕捉。孙兴华等【1 9 1 研究并提出在商标检索中局部特征比全局特 征可能起到更好的检索效果，因此对如何结合各类特征的融合准则进行了探索 研究。 近年来基于形状检索的研究又出现了一种新的思路：结合全局和局部的匹 配。国内学者郭丽，黄元元，孙兴华等对此做了大量的研究，如 2 0 1 用分块图 像特征进行商标图像检索，提出一种使用全局和局部图像特征检索商标图像的方 法，首先确定图像的形状主方向，根据形状主方向对图像进行旋转，然后对旋转 后的图像提取目标区域，对目标区域用四叉树分解的方法划分多缴分块，最后抽 驳分块图像特征进行图像相似性度量；文1 2 1 】提出一种基于单元子图像形状和 空矧结构的多级商标图像检索算法，极据单元予图像特征相似性对商标图像进行 粗检索，然后对结果图像的空问结构用位置字符串匹配的方法进行分析。 6 中山人学硕七学位论文 第2 章基于内容的商标l 堇j 像柃索 2 3c b t i r 的障碍及解决 在现实的应用中，商标检索总会面临各种问题，其障碍不仅包括技术性因 素，也存在许多非技术的人为因烈”。 ( 1 ) 非技术因素是指人主观的认识和实际的操作中带来的困难。商标检索的 目的是为了找出相近似、或者相同的商标，为商标排查工作提供判断依据，近年 来商标注册问题引发的争执非常多。虽然技术手段上对于更为客观地反映商标特 征可起到硬性指标的作用，减少一定的争议，然而视觉相似是个较主观的概念， 符合人们认知的可视化相似又属于图像内容的高级语义部分，分析难度大，同 时受到一些背景知识的影响和作用，也可能产生不同的事物却给人相似的感觉， 这也就是导致目前图像检索中的一大难点“语义鸿沟”( s e m a n t i cg a p ) 的本 质问题。在基于内容检索中一般采用相关反馈技术获取在图像检索中与用户的交 互信息，更新系统知识库，以提高对图像特征分析和相似度判断的准确性。 在非技术层次上还有待对相似度衡量标准的进一步明确，只有在有限范围 内对商标的相近相同判断标准更准确的量化和具体化，才能够为技术实现提供 一个更可靠的保障，也为实际工作的操作提供更有力的依据。本文对非技术因素 不作更深入的研究。 ( 2 ) 技术性因素是指在技术实现手段和方法上的困难，主要体现在特征提取 表示和相似度大小判断上。一方面，商标图像特征需要得到更明确的分类和标识， 从而与大量的同类商标相互区分。图像分割和特征提取也是一个不断精益求精的 过程，基于内容检索本身还没有一个效果较好的通用技术，因此要无歧意地直 观体现商标图像的显著特征，同时满足特征的颜色、比例不变性和旋转不变性， 还存在难度。另一方面，如何在特征表示的基础上，采取合适的策略来衡量两个 商标图像之间的相似度大小也是难题之一。而技术性因素的根本难点还在于一些 非技术因素的存在，因为视觉感知的相似和相近是一个较主观的问题。 在技术层次上还有待于对商标图像的特征分析、特征提取方面进行更深入探 索，商标图像属于一类特殊的图像，尽管诸多的图像检索算法都可以应用于商 标图像的检索实现中，不过针对商标的形状显著特征，以及商标图像的自身特 点，还有很大的发展余地。同时，考虑分层次、分不同水平来实现商标检索，以 中山人学坳 ：学位论文 第2 章皋十内容的商标图像榆索 结合类目检索，文本检索、内容检索共同实现对商标的查询，这也不失为个便 捷的方法，可以在这些不同层次和级别上进行深度不一的匹配【1 1 1 【1 2 1 。 目f i i j c b i r 是研究热点，各种特征提取和相似匹配算法层出不穷。其中的一些 算法也被用于c b t i r 。c b t i r 主要用于注册商标的查重，由于其应用的特殊性，对 检索的查准率和查全率要求更高。近年来商标图像剧增，而且商标图案设计同趋 多样化，图像千差力别，目前还没有任何一种算法具有普适性，大多算法对一种 类型的商标图像能得到较好的检索效果，对其他类别的商标图像不一定适用。因 此有必要针对每个图像的显著视觉特征，选择最合适最有效的检索算法。这是本 文提出自适应算法的出发点。 2 4 分层检索 从前面两节的分析可见，c b t i r 目前的解决方法及研究趋势可以归结为三类： ( 1 ) 基于相关反馈：检索以人机交互式进行，用户对检索结果给出评判， 系统接收用户对当l i 检索结果的反馈意见，分析用户的关注点，自动地调整查询， 重新计算检索结果，使之更加接近用户的信息需求l 。 ( 2 ) 多特征融合：对图像提取多个显著特征，按一定的组合原则( 如加权) 进行特征组合。 ( 3 ) 分层检索：分层次、分不同水平来实现商标检索，以结合类目检索、 文本检索、内容检索共同实现对商标的查询，可以在这些不同层次和级别上进行 深度不一的匹配。这是本文分层检索算法的出发点。 2 4 1 分层检索的理论 分层检索的思想源自j a i n 和v a i l a y a 的论文【l l 】，文中提出一个两层捡 索的系统：第一层采用边缘方向直方图结合七个h u 不变矩的方法对数据库中图 像进行一次过滤，排除那些与查询图像明显不相似的图像，缩小下一层检索的搜 索范围；第二层采用可变模板方法进行精细匹配。论文1 6 1 介绍了卡纳基悔隆 大学开发的t r a d e m a r k 系统，此系统中也采用了分层的检索思想。系统提取商标 8 中山人学顾 ：学位论文第2 章基于内容的商标图像榆索 图像的轮廓和骨架作为特征向量。对用户提交的商标图像，首先根据其整体形状 作出判定，确定适合于提取轮廓还是骨架特征，然后再执行后续。 另外，国内学者俞勇等在文【1 2 1 中也提出一种商标图像检索的多层次方法， 分三个层次由粗逐细地实现图像检索，动态减少图像搜索范围。第一层采用字符 串匹配方法准确定位商标在商品分类表中的位置；第二层利用最小约束矩方法， 排除多数不相似商标，并保证空间变换下的检索不变性；第三层利用点匹配方法 计算商标的相似程度。该方法综合了文本和图像多种特征，符合现行的人工商标 注册和审核过程。郭丽、黄元元1 2 1 】提出一种基于单元子图像形状和空间结构 的多级商标图像检索算法，该方法实际上也是一个两层检索的框架，综合利用图 像的局部形状特征和图像内部的结构特征。首先根据单元子图像形状特征相似性 对商标图像进行粗检索，然后对结果图像的空间结构用位置字符串匹配的方法进 行分析。只有同时满足形状相似和空间结构相似的待检图像才能作为检索结果输 出。 z 4 2 分层检索的优势分析 较相关反馈和多特征融合方法，本文认为分层检索有其优势，分析如下： ( 1 ) 与相关反馈相比 相关反馈一般要求用户具有相关背景知识，给用户操作带来不便，而基于分 层检索无需用户参与反馈；由于不同用户对图像的相似性有不同的见解，相似性 的判定存在极大的主观性，利用相关反馈能在一定程度上减小“语义鸿沟”，极 大地改善检索效果，这正是在c b i r 中引入相关反馈的意义所在；但是由于商标 图像本身的特征以及商标检索应用的特殊性，c b t i r 中的相似性较一般的c b i r 要客观得多，主要表现在： 从商标图像本身的特征来看。商标图像属于人工图像，没有自然图像的复杂 背景和目标，一般由一些抽象的几何图形或艺术字组成，图像的各个部分具有相 对明显的分界，形状和空间结构特征显著。而且许多是单色无纹理的二值图像 2 3 1 2 4 l 。因此用户对商标图像视觉特征的关注点也相对较集中。 从应用方面来看，c b t i r 主要用于注册商标的查重。即判断待注册商标是否 9 中山人学碘i j 学位论文第2 帝筚f 内各的商标幽像榆索 与商标库中已注册的商标存在相同或相似。我国商标法中指出，商标相同或相似 的依据是“以普通消费者的一般注意力为评判的主观标准”，不至于让普通消费 者混淆的商标就被认为是不相似的【2 5 1 。对此大多人的评判标准趋于一致。 ( 2 ) 与多特征融合相比 首先，多特征的融合较单一特征匹配，检索效果确实有一定的改善，但是也 不具备普适性。对一些单一特征显著的图像，其效果反倒不佳，本文在算法实验 中也验证了这一点。 其次，多特征融合的检索方法计算量大，耗时。考虑到一般的做法是将图片 库中图像特征向量作为索引，静态存储。用户提交检索示例后，检索时间的丌销 体现在两方面：一是对检索示例的特征提取及特征向量的归一化；二是检索示例 特征向量与数据库中所有图像的特征向量逐一比较，计算相似距离。前者耗时小， 在大规模搜索时可以忽略，后者是主要的时问丌销。而相似匹配的时间丌销与搜 索范围( 即与检索示例进行相似比较的图像数目) 成正比。所以，如果在相似比 较之6 订先对检索示例进行过滤，滤除数据库中那些明显不相似的图像，而只与剩 余的较相似图像进行比较，则检索范围大大缩小，检索时间将显著减少。这证是 本论文分层检索的思想。 鉴于分层检索的以上优势，本文算法将采用分层检索的思想，以期在不增加 算法时间复杂度的基础上，从检索结果的视觉一致性以及对变换的鲁棒性等方面 加以改善，同时考虑算法的自适应特性以及对图像反色变换的不变性。 0 第3 章自适应的商标图像分层检索算法 本章提出了一种自适应的商标图像分层检索算法。详细描述了算法的处理流 程和实现过程。算法性能的测试与分析将在第四章中给出。 3 1 算法研究范围 商标图像属于一类特殊的图像，尽管诸多的图像检索算法都可以应用于商 标图像的检索实现中，不过针对商标形状的显著特征，以及商标图像自身的特 点，还有很大的发展余地。 商标图像按其组成结构可以划分为三种类型：字符商标( w o r d - i n - m a r k ) 、图 形商标( d e v i c e i n - m a r k ) 和组合商标( c o m p o s i t em a r k ) ，如图3 - 1 所示。其中 图形商标主要由纯图形、图像组成，如几何形状或者一般的图像，目前c b t i r 的研究主要针对图形商标【”。 g o o g l ea u 6 l ( a ) 字符商标 ( b ) 图形商标( c ) 组合商标 图3 - 1 商标示例 商标图像特征一般包括颜色( c o l o r ) 、轮廓( s k e l e t o n ) 、形状( s h a p e ) 以及版 面( l a y o u t ) 等特征。商标图像属于人工图像，没有自然图像的复杂背景和目标， 一般由一些抽象的几何图形或艺术字组成，图像的各个部分具有相对明显的分 界，形状特征显著。而且许多是单色无纹理的二值图像瞄 1 2 4 1 。 本文的研究主要针对图形型的二值商标，在特征提取上主要考虑基于形状的 全局统计特征。原因如下： 中山人学坝i 学位论史第3 章白适j 引1 勺商标【川像分层f ：索算法 1 ) 和颜色、纹理相比，形状特征更为直观，能更好地表征二值商标图像的特点。 2 ) 便于交互描述。目前的c b t i r 系统一般采用示例检索模式，更突出了形状特 征的重要性，用户可以通过勾勒图像的形状或轮廓，从图像库中检索出形状 类似的图像。 3 2 算法预备知识 本节介绍本文算法中用到的一些基本方法、相关原理及公式。其中涉及图像 处理、图形学、形状匹配和c b i r 的基本方法。具体包括中值滤波、彩色图像灰 度化、灰度图像的阈值二值化和根据梯度的二值化、边缘检测、轮廓提取和轮廓 跟踪、k l 变换求图像主轴方向公式、平面坐标系中图像绕点旋转公式、扫描线 多边形填充算法、圆形拟合函数、七个h u 不变矩、距离分布直方图、特征向量 的高斯归一化和线性缩放归一化、相似匹配的欧氏距离和最小绝对差距离。 下面按照其在算法中应用到的先后顺序逐一说明。 3 2 1 空间域平滑去噪 在c b i r 中，图像噪声的存在将会直接影响特征提取的准确度，因此需要预 先进行去噪处理。图像去噪又称为图像平滑或滤波，可以在空间域进行，也可以 在频率域进行。常采用的空自j 域滤波方法有均值滤波和中值滤波。 ( 1 ) 均值滤波 均值滤波是一种常用的基于邻域的平滑方法，即对每个像素选取一定尺寸的 邻域( 模板) ，用邻域中像素的平均灰度值束替换此像素值。 ( 2 ) 中值滤波 中值滤波也是种常用的基于邻域的平滑方法，即对每个像素选取一定尺寸 的邻域( 如n n ，n = 3 , 5 7 ) 对邻域内像素按大小重新排序，取位于中间的像素 值替代当前像素值。 本文在实验中发现，两者都起到了平滑去噪的作用，同时模糊了图像的边缘 中山人学硕l 学位论文第3 章自适戍的商标图像分层检索算法 和细节。在取相同窗口大小的情况下，实际处理效果中值滤波要优于均值滤波， 能够较多的保留图像细节。 本文选用3 x 3 的中值滤波进行灰度图像去噪，主要目的是消除孤立的黑白噪 声点，同时对图像边缘的模糊效应最小化。实际处理中，对图像边界上伽一1 ) 2 ( 即1 ) 个像素宽度区域不进行处理，以避免模板超出图像边界。 3 2 2 彩色图像灰度化 由彩色转化为灰度的过程叫灰度化处理，即使r g b 模型中的r = g = b 。灰度化 处理是把含有亮度和色彩的彩色图像变换成厌度图像的过程【2 6 1 。 一般彩色图像每个像素用3 个字节表示，每个字节分别对应r 、g 、b 分量， 转换后的黑白图像的一个像素用一个字节表示该点的灰度值，其值在0 - 2 5 5 之 问。转换关系为 o r a y ( i ，_ ，) = 0 11r ( i ，_ ，) d - o 5 9g ( i ，) d - 0 3b c i ，d ( 3 1 ) 其中g r a y ( i ，力为转换后的灰度图像在( f ，) 点处的灰度值，由于上式中 绿色的比重最大，所以很多处理中也直接取g 值作为转化后的灰度。 其他灰度化处理方法还有取三个分量的最大值，最小值，算术平均值等，目 的都是使r ，g ，b 分量值相等。 本文选用变换公式( 3 1 ) 对彩色图像进行灰度化。事实上由上式求出的灰 度值即为1 u v 颜色模式中的亮度分量y 值，根据人眼的感知特性，相对于颜色信 息，人眼对图像的亮度信息更敏感，所以基于亮度信息的灰度映射能达到最佳的 视觉效果。 3 2 3 灰度图像二值化 图像包括目标物体和背景，在商标图像的检索中，我们的关注点只是目标物 体，因此有必要首先将目标和背景分离。 二值化处理就是通过颜色的差异把图像的目标物体和背景区分丌来。最常用 中山人学倾i + 学位论义 第3 章白适麻的商标幽像分层伶索算泣 的是阈值二值化，即设定某一阈值t ，用t 将图像的数据分成两部分：大于t 的 像素群和小于t 的像素群。阈值二值化中具体又包括非零取一，固定阂值、双 固定闽值等变换方法。目的都是使一幅灰度图变成黑白二值图，将我们所需的目 标部分从复杂的图像背景中分离出来【2 6 】。 还有一些其他的方法可以实现二值化，如一些常用的边缘检测算子，其处理 效果实质上是对图像进行边界二值化。本文实践了其中的几种算法，按照处理效 果将二值化归结为两类： 1 ) 区域二值化：处理效果是目标区域与背景的分离，可以通过阈值二值化实现； 2 ) 边界二值化：处理效果是目标边界与背景的分离，可以通过一些梯度边缘检 测算子实现。 本文对商标图像形状特征的提取有些是针对目标区域的，有些只是针对目标 边界，所以实际处理中用到固定阈值二值化( 取t = 1 2 8 ) 以及根据梯度二值化 图像( 原理详见下一节) 。 3 2 4 边缘检测 本文针对商标图像的特征提取主要是基于目标物体的形状特征和空间像素 分布的，而边缘检测、轮廓提取和轮廓跟踪是形状匹配的基础。 边缘检测算子是一组用于亮度函数中定位变化的重要局部图像预处理方法。 经典的边缘算法认为，边缘主要表现为图像局部特征的不连续性，从而关于边缘 算子的研究也主要集中于狄度图像梯度的研科卸。 由于我们常常无法事先确定轮廓的取向，选择用于轮廓增强的微分算子时， 必须选择那些不具备空间方向性和具有旋转不变的线性微分算子。最基本的一类 边缘检测算子是微分算子类。 r o b e r t s 算子就是一种简单易行的微分算子，它基于一阶方向导数在边缘处 取最大值这一变化规律。r o b e r t s 采用的是对角方向相邻的两个像素之差。从图 像处理的实际效果来看，r o b e r t s 算子定位比较精确，但由于仪使用了很少几个 像素来近似梯度，算子本身没有平滑作用，对图像中的噪声高度敏感。s o b e l 算子 1 4 中山天学硕士学位论文第3 章自适应的商标图像分层榆索算法 有一定的噪声抑制能力，在检测阶跃边缘时，得到的边缘宽度至少为2 像素，它 不依赖于边缘方向的二阶微分算子，是一个标准量而不是向量，具有旋转不变即 各向同性的性质，在图像处理中经常用来提取图像的边缘。这两者对灰度渐变低 噪声的图像有较好的检测效果，但是对于混合多复杂噪声的图像，处理效果就不 理想。它们的主要缺点为：依赖于物体的大小且对噪声敏感，抗干扰性能差，边缘 不够精细。 c a n n y 算子则以一阶导数为基础判断边缘点，它是一阶传统微分中检测受白 噪声影响的阶跃边缘中最优的，比r o b e r t s 算子和s o b e l 算子在降噪能力上都 要强。但是，传统c a n n y 算子的计算量大、实时性较差，并且检测边缘的精度仍 没有达到单像素级，在实际处理中受各种干扰因素的影响，仍然存在部分虚假边 缘。 总的说来，各有优缺点，在应用中应该根据实际情况选择适合的算子。 本文实验中发现，梯度算子o r 向一次微分公式) 和r o b e r t s 算子的处理效 果更合适，为本文算法所采纳。 r o b e r t s 算子： g f ( i ，力】= ( f ，) 一八f + 1 ，j + n 2 + 【f ( i + l ，- ，) 一f q ，+ 1 ) 】2 ( 3 2 ) 梯度算子( 双向一次微分公式) ： g f ( i ，朋：知瓦f 而i 开雨鬲万丽丽 ( 3 3 ) 3 。2 5 轮廓提取和轮廓跟踪 外轮廓的提取，是本文对目标物体进行形状特征分析的基础。 轮廓提取是边界分割中非常重要的一种处理，同时也是图像处理的经典难 题，轮廓提取和轮廓跟踪的目的都是获得图像的外部轮廓特征。在必要的情况下， 应用一定的方法表达轮廓特征，为图像的形状分析作准备，对特征描述、识别和 理解等高层次的处理有着重大的影响【2 6 1 。 边界跟踪效果的好坏主要取决于两个因素：一是跟踪的起始点的选取，起始 点的选取直接影响到跟踪的精确度，同时如果起始点选得不好，还给算法的设计 中山人学坝i 学位论立第3 章白适戍的商标图像分层榆索算法 增加难度；二是跟踪准则的选取，准则既要便于理解和分析，又要便于程序的设 计。 边界跟踪的基本方法是：先根据某些严格的“探测准则”找出目标物体轮廓 上的像素，再根据这些像素的某些特征用一定的“跟踪准则”找出目标物体上的 其他像素。一般的跟踪准则是：边缘跟踪从图像左上角开始逐个像点扫描，当遇 到边缘点时丌始顺序跟踪，直至跟踪的后续点回到起始点( 对于闭合曲线) 或者 其后续点再没有新的后续点( 对于非闭合曲线) 为止。如果为非闭合曲线，则跟 踪- - n 后需从起始点丌始朝相反的方向跟踪到另一尾点。如果不止一个后续点， 则按上述连接准则选择加权平均最大的点为后续点，另一次要的后续点作为新的 边缘跟踪起点另行跟踪。一条线跟踪完后，接着扫描下一个未跟踪点，直至图像 内的所有边缘都跟踪完毕。 这种边界跟踪在图像处理时，执行先后是有次序的，后面的处理要用到前面 的处理结果。因此算法的处理速度慢，但是对于边界点的判断精确。而且整个边 界连续无中断，跟踪后产生的轮廓边缘宽度只有一个像素。 3 2 6k - l 变换求形状主方向 k - l 变换又叫主分量变换或霍特林变换。是把原来多个变量化为少数几个综 合指标的一种统计分析方法，是一种降维处理技术。其理论依据是通过j 下交变换 将协方差矩阵( 实对称矩阵) 对角化，从而消除图像的相关性【2 8 1 。 k - l 变换的优点是去相关性，应用在数据压缩和图像旋转等方面。 在图像检索中，为了使图像特征具有旋转不变性，可以选定一个固定的参考 方向，形状主方向就是一个很好的参考量，对一幅图像其形状主方向是唯一的而 且具有旋转不变性【2 0 1 。 形状主方向( 记为n ) 决定于图像的主轴方向与水平方向的央角( 记为8 ) ， 其中图像的主轴方向就是图像目标像素区域的最佳拟合椭圆的长轴方向。由图像 的k l 变换可知，0 是具有最大特征值的特征矢量方向，可以根据图像的中心矩 进行计算，即 1 6 中山人学硕士学位论文第3 章臼适庸的商标图像分层检索算法 其中 ：a r c t a n ( u 0 2 _ u 2 。+ ( u o z _ u 2 0 ) 2 + 4 u j l 2 ) ( 3 4 ) z u l l = ( 工一i ) 9 0 一7 0 ) 9 r ( x ，y ) ( 3 5 ) j ， 甜。为图像的p + g 阶中心矩，( x o ，y 。) 为t ( x ，y ) 的重心坐标。根据夹角进 行形状主方向口的确定存在两种可能：( 1 ) 直接选取作为口；( 2 ) 选取其反方 向+ 万作为口。较为简单实用的方法是将图像旋转一角度，然后根据图像的 三阶中心矩进行确定，其计算公式为 i8 口2 i + 石 3 2 7 平面坐标系中图像绕点旋转公式 图像旋转是数字图像处理中图像的基本几何变换之一。在本文中主要用于最 小约束矩提取的预处理，即将图像绕重心旋转使其主轴方向水平向右。 图像的旋转必须指明其旋转中心。一般取图像重心为圆点，旋转一定的角度。 旋转后图像的大小一般会改变。可以把转出显示区域的图像截去，也可以扩大图 像范围以显示所有的图像 2 6 1 2 9 1 。 在如图3 2 所示的坐标系中，点( x o ，儿) 经过旋转口度后坐标变成( 五，j ，) ， d 图3 - 2 图像旋转示意图 1 7 缶3( o o 中山人学颂i + 学位论史第3 章白适戊的商标幽像分层榆索算法 旋转前： 旋转后： f x o = y c o s f l 1 y 。= y s i n i x l2 y c o s ( p g ) = y e o s f l c o s a + i y - = y s i n ( f l g ) = y s i n , b c o s g 一 ( 3 7 ) y s i n f l s i n a = x 0cosg+yo s i n a y c o s , b s i n g = - - x 0s i n g + y o