MindFinder及边缘检测应用与实现.doc

西南交通大学本科毕业设计 论文 第 I 页 西 南 交 通 大 学 毕业设计 论文 MindFinder 及边缘检测应用与实现 题 目 MindFinder 及边缘检测应用与实现 1 本论文的目的 意义 分析及比较经典的图片 Edge 特征提取算法 比较 Canny 算子以及 Berkeley 算法性能的优劣 在大规模购物搜索图片数据集上进行实验 找出适合于购物搜索 应用 的 Edge 特征提取算法 并试图集成进 MindFinder 搜索中 2 学生应完成的任务 1 学习和了解图片 Edges 检测的原理 2 了解 MindFinder 原理 3 比较 Edge 特征提取算法 Canny 算子以及 Berkeley Contour 算法性能 4 实现并改进图片 Edge 算法 5 在大规模图片数据集上进行实验 6 完成毕业论文 西南交通大学本科毕业设计 论文 第 II 页 3 论文各部分内容及时间分配 共 16 周 第一部分绪论 资料收集 2 周 第二部分了解 MindFinder 原理 及经典的 Edge 特征提取算法 3 周 第三部分比较 Canny 算子和 Berkeley 算法性能 4 周 第四部分实验 在大规模数据集上测试数据 比较性能 4 周 第五部分撰写论文 2 周 评阅及答辩 1 周 备 注 指导教师 年 月 日 审 批 人 年 月 日 西南交通大学本科毕业设计 论文 第 III 页 摘 要 基于手绘线条图像检索 SBIR 是计算机视觉领域近年来逐渐兴起的一个研究分 支 作为一个信息检索系统 它只要求用户绘制一些简单的曲线 就能搜索出一系 列相似的图像 这一系统对相似的判定 主要依靠的是图像中物体对象的轮廓与输 入曲线的匹配度 人体视觉的知识告诉我们 人们往往依据轮廓来识别对象的存在 因此 这一类搜索系统很适合用于查找用户感兴趣的物体 另一方面 网上购物已 成为现代人生活中不可缺少的一部分 但使用文字常常难以描述人们的消费需求 在触屏设备快速普及的现在 如果 SBIR 系统能被应用于购物搜索 那么人们只需 根据自己的想法在屏幕上画几笔 就能找到满意的商品 简单有趣的交互方式和视 觉上更加准确的搜索结果 使得 SBIR 系统在电子商务领域的前景十分广阔 本论 文所研究的内容 便是在大规模商品图像数据的基础上 通过对多种底层技术进行 分析 实现和比较 试图构建起适用于购物搜索应用的 SBIR 系统 从本质上说 SBIR 系统的技术难点在于 该如何拉近二值曲线与自然图像轮廓 之间的 语义鸿沟 为了实现这一目标 研究人员已尝试多种不同的匹配思路 并 使用了边缘图 几何拓扑和梯度分布等诸多信息 在本文中 将分别介绍在目前的 研究领域里主流采用的 基于特征点和特征向量的两种匹配方式 尽管使用向量法 构建的系统具有十分突出的搜索效果 但索引机制的缺少使其不具备高扩展性 虽 然通常情况下点匹配法的效率较低 但 MindFinder 系统中提出的特征点索引机制极 大提升了匹配性能 并实现了大规模数据下的实时图像搜索 本文将重点介绍该索 引机制 并在此基础上搭建起最终的 SBIR 系统 尽管本课题采用了基于特征点的匹配手段 但为了检验在购物搜索应用中两种 匹配方式的适用性 本文也实现了 Tensor 向量匹配算法 并在商品图像集合上对二 者的匹配结果进行比较和分析 此外 由于点匹配算法的性能和效果依赖于边缘检 测过程的输出 所以为了分析该过程对于 SBIR 系统的影响 本文分别介绍并实现 了 Canny 算子和 Berkeley 的 Pb 算子 将其集成在系统之中进行测试 并比较搜索 结果 在此基础上 本文对原始自然图像的预处理过程提出了一些改进建议以提升 系统性能 关键词 基于手绘线条图像检索 形状匹配 边缘检测应用 索引机制 西南交通大学本科毕业设计 论文 第 IV 页 Abstract Sketch based Image Retrieval SBIR is a newly proposed research branch in the area of computer vision As an information retrieval system it requires only a simple curve from user to search for a sequence of similar images The definition of similarity in this kind of system mainly depends on the match degree between object contours in image and curves from input Knowledge of human vision system has told us that people always recognize object with the help of its contour That s why SBIR is very suitable for users to search for their interested objects On the other hand online shopping has been a very necessary part in daily life however words are always limited to describe our interests Currently with the wide spread of touch screen equipment if SBIR system is applied to shopping search people would be able to find required products simply using several sketches on screen to describe their thoughts Simple but interesting way to interactive and visually precise search results would make SBIR very useful in the area of e business The research goal of this paper is trying to build a SBIR system which is suitable for shopping search after analyzing implementing and comparing several underlying technologies Essentially the key topic of SBIR system is how to shorten the sematic gap between binary curve and contour of natural image To achieve that task researchers have tried many different matching approaches and also made use of edge map geometric topology gradient distribution and some other cues This paper introduces two matching methods most used currently which are separately based on feature points and feature vector Although several SBIR systems using vector approach have outstanding search results absence of index mechanism makes it hard to scale Point matching is always less efficient however the feature point index mechanism raised by MindFinder system which has achieved real time image search with massive data improves the performance of matching a lot This paper will focus on that mechanism and build the final SBIR system on the base of it Although the matching method used in this paper is based on feature points Tensor vector matching algorithm is also implemented to verify the applicability of two approaches Based on the database of products images these two matching strategies are compared and analyzed Besides performance and results of point matching depend on the output of edge detection therefore in order to analyze the influence upon this system by that process Canny and Pb operators are both introduced realized and integrated in this paper and two kinds of search results are also compared Based on that this paper raises 西南交通大学本科毕业设计 论文 第 V 页 some useful advices for preprocessing original natural image to improve performance of this SBIR system Keywords Sketch based Image Retrieval Edge Detect Application Shape Matching Index Mechanism 西南交通大学本科毕业设计 论文 第 VI 页 目目 录录 摘 要 IV ABSTRACT V 第 1 章 绪 论 1 1 1 课题研究背景和意义 1 1 2 现有边缘检测算法概况 2 1 3 MINDFINDER图像检索系统简介 3 1 4 课题研究内容 3 1 5 本论文的结构安排 4 第 2 章 相关知识概述 5 2 1 CANNY边缘检测原理 5 2 1 1 概述 5 2 2 2 算法流程 5 2 2 BERKELEY边缘检测原理 6 2 2 1 概述 6 2 2 2 算法流程 6 2 3 二值手绘曲线与彩色自然图像的匹配 7 2 3 1 基于向量的匹配 7 2 3 2 基于边界点的匹配 8 2 3 3 总结 9 2 4 MINDFINDER索引机制 9 2 4 1 背景 9 2 4 2 算法流程 9 2 5 开发工具及开发环境简介 11 2 5 1 OpenCV 简介 11 2 5 2 Dev C 简介及 OpenCV 配置 11 第 3 章 算法实现及系统搭建 14 3 1 算法实现 14 3 1 1 Canny 算法及 Berkeley 算法 14 3 1 2 Tensor 向量匹配算法 15 3 2 系统设计 16 3 2 1 功能分析 16 西南交通大学本科毕业设计 论文 第 VII 页 3 2 2 系统结构 17 3 3 后台处理模块实现 17 3 3 1 图像归一化 17 3 3 2 提取边缘图像 18 3 3 3 提取特征文件 18 3 3 4 构建索引 20 3 3 5 查询相似图像 23 3 4 前台搜索模块实现 26 3 4 1 界面设计及实现 27 3 4 2 搜索过程的实现 29 3 4 3 搜索结果 31 第 4 章 实验部分 33 4 1 点匹配与向量匹配 33 4 1 1 实验准备 33 4 1 2 匹配结果对比 33 4 1 3 性能对比 34 4 1 4 总结 36 4 2 CANNY与 BERKELEY算子 36 4 2 1 边缘图像对比 36 4 2 2 搜索结果对比 37 4 2 3 购物搜索应用下的边缘检测 38 结 论 42 致 谢 43 参考文献 44 附 录 TENSOR 实现代码 46 西南交通大学本科毕业设计 论文 第 1 页 第 1 章 绪 论 1 1 课题研究背景和意义 近二十年来 随着互联网的普及 个人拍照设备数量的井喷以及图片分享网站 的流行 人类社会的图像数据呈现爆炸性增长 技术门槛的降低和拍照设备的大幅 降价 使得每个人都成为了图像的创造者和分享者 在这一潮流下 人们开始更多 地在互联网上查看和分享图片 进而更多地去寻找自己需要的素材 然而 人们在 一次次无法满足的搜索需求中逐渐发现 搜索者往往难以准确地用语言描述图片内 容 试图揣摩关键词语义的传统图像搜索 基于文本 自然无法得到满意的结果 正因如此 CBIR Content based Image Retrieval 的理念应运而生 1 2 在这一 新兴但充满活力的领域里 人们试图通过分析图像自身的特征以描述其内容 将模 板 轮廓或是图片作为查询输入 进行基于内容的图像搜索 对应于不同的应用领 域 CBIR 的设计者们采用了不同的技术和方法 但一般来说 常用的图像特征包括 了颜色 纹理 形状 空间分布 局部特征点等等 其中 形状属性最符合人类视 觉系统对物体的感知 因而也引发了一系列关于 SBIR Sketch based Image Retrieval 的研究 5 自上个世纪九十年代中期以来 前人的研究成果颇丰 不仅提出了形状上下文 曲线片段 凹凸段序列等方法来对图像中的形状特征加以描述 而且结合形状段间 的空间分布关系和优化的距离计算方法 使得匹配过程更加高效 结果更加精确 但在早期研究中 形状特征的搜索效果在很大程度上依赖于图像分割的准确度 尽 管陆续有新颖高效的分割不敏感方法提出 但基于数学模型构建的局部形状描述仍 然较多用于剪贴画 卡通或是简单模板对象的匹配 而不太适应于自然图像的搜索 而在另一方面 SBIR 的研究将用户输入的二值曲线段作为查询 词 基本抛 弃颜色和纹理特征 而从形状角度搜索相近图片 在研究早期 SBIR 与 基于形状 的图像匹配 密不可分 事实上 有一段时间内可以认为前者就是后者的子研究 但是 在当前的数据爆发时代 复杂的数据模型已经不适合于大规模的图像搜索 更难以达到实时的处理效果 不仅如此 触摸屏的流行也使得 SBIR 比概念宽泛的 基于形状的图像匹配 有了更加现实的意义 如上所述 SBIR 的早期研究仍以数学模型描述曲线段为主 这一阶段的研究成 果既有曲线尺度空间 拓扑几何特征 也有傅里叶描述子和边界像素邻居信息 但 计算复杂性导致的不可扩展性 使得人们开始设计并提出面向大规模数据的 SBIR 主流的设计思想 是将图像归一化后分块 将其二维形状特征转换为一维向量 图 西南交通大学本科毕业设计 论文 第 2 页 像间的相似度 便可以通过计算向量间的距离加以衡量 这一领域里较为突出的实 践者 有 A Chalechale 所采用的 ARP Angular Rotation Partitioning 3 MPEG 7 标 准中的 EHD Edge Histogram Descriptor 4 以及 M Eitz 所采用的 HOG Histogram of Oriented Gradients Descriptor 和 Tensor Descriptor 6 Eitz 在其所发表的论文中对这四 种向量方法的性能进行了详细的评估 这一思想的优势在于以向量的形式描述了像 素点的梯度方向和空间分布特性 以分块再综合的统计手段减小误差 但不足的是 由于缺少索引机制 提取向量再计算 KNN 的过程在进行数据量扩展时必然面临性 能瓶颈 相对于数学模型构建的曲线段和描述子 由边界像素点组成的轮廓被认为是低 级的形状特征 早在上个世纪八十年代 便出现了利用这一特征进行形状匹配的算 法 CM Chamfer Matching 7 这一思想通过距离转换 将 重合 的像素点个数 作为两个图像的相似度 在此基础上 人们加入梯度方向属性 设计出了 Oriented CM 8 而近年来 微软亚洲研究院所设计的 MindFinder 系统 9 便是采用了此类思 想 设计出了可用于索引的 Indexed OCM 10 从而实现了大规模数据集下的带有索 引机制的 SBIR 从这一系统的演示视频可以看出 其搜索效率和效果都是十分惊人 的 本课题的设计目标是基于边缘像素点和索引机制 面向大规模购物图像的 SBIR 系统 其最初也是最核心的数据处理过程就是提取出自然图像的边缘图 在边界 轮廓 提取领域 最经典的算法是 1986 年 John Canny 提出的 Canny 算子 11 这 一算法依据的是像素点间的亮度差 但近年来的研究表明 颜色 纹理等特征也是 用于检测自然图像边界的重要属性 这其中 较为突出的成果有 UC Berkeley 的学 者提出的 Berkeley Pb 算子 12 等等 下面将对现有的边缘检测算法进行简单介绍 1 2 现有边缘检测算法概况 近年来 加州大学伯克利分校的计算机视觉小组创建了一个名为 BSDS 的基准 测试数据集 16 用于评判边缘提取算法的性能 业界领先的技术成果大多在这一基 准上进行了评测 而该小组则以此为依据对其进行排名 本文依据截至目前的最新 列表 对部分有着突出表现的算法进行简单介绍 1 Canny 算子 这是 1986 年由 John Canny 最先提出的边缘检测算子 11 它依据了亮度差值属性 得到了原始图像的阶跃边界 并在此基础上 通过双阈值过滤和边界连接过程 最 终得到一个唯一的边缘集合 这一算子虽没有在 BSDS 上测试 且检测结果对纹理 特征有很大敏感度 但由于其足够好的性能仍被很多研究人员所采用 2 伯克利 Pb 算子 西南交通大学本科毕业设计 论文 第 3 页 Pb 算子是加州大学伯克利分校的 David R Martin 等人提出的 12 与 Canny 不同 的是 它将亮度 颜色和纹理等局部特征结合在一起 检测出了比前者更精确的边 缘 为了实现这一目标 Martin 等人在一个人为标注的数据集上进行训练 得到了 一个结合了多种特征的分类器 3 伯克利 gPb 算子 在 Pb 算子局部方法的基础上 Michael Maire 等人结合了图像的全局属性 得 到了更高性能的处理过程和更加精确的测试结果 13 4 BEL 算子 与上述的几种通用边缘检测算法不同 Piotr Dollar 等人提出的 Boosted Edge Learning BEL 更适用于特殊类别对象边缘的检测 14 同样是在人为标注图像集的基 础上进行训练 该算法得到可对特殊对象的分类器 从而排除了背景噪声的影响 5 最小覆盖法寻找突出曲线 Pedro Felzenszwalb 等人提出的算法采用了解决最小覆盖问题的思路 15 与尽量 检测出边缘点的方式不同 它试图以最少的曲线表达出图像轮廓 虽然检测结果的 查全度较劣于传统的边缘检测 但噪声大大减小的优势使其适用于很多特殊应用 为了将工作重心集中于系统搭建和性能分析 本课题将在 MindFinder 索引机制 的基础上实现和集成较为简单的 Canny 和 Berkeley Pb 算子 在后文中也将说明 边 缘检测精确度的差别并不是影响搜索结果的关键因素 1 3 MindFinder 图像检索系统简介 微软亚洲研究院的王长虎在分析了当前图像搜索引擎的不足后 提出了一个基 于手绘线条的检索系统 9 只需在画布上寥寥几笔 就可实时搜索出轮廓相似的图片 结果 尽管这类被称为 SBIR 的搜索系统已被研究多年 业界也取得了很多突出的 成果 但 MindFinder 的优势和突出点在于 通过在图像特征点之上建立倒排索引机 制 10 将普通用户的一张手绘图片在 200 万数据集上的查询时间降低至一秒左右 这也是业界在 SBIR 系统研究和设计中首次提出实质意义上的索引机制 通过 MindFinder 的演示视频可以看出 这一系统具有高精确度和位置敏感特性 后者的 存在导致该系统的查全率受限 但通过后文对技术细节进行的剖析可以看到 这是 特征点索引机制的不足之处 也是对性能和效果进行权衡后采取的折中方案 1 4 课题研究内容 本文的研究内容主要包括三个方面 1 依赖 MindFinder 系统的特征点倒排索引机制搭建 SBIR 系统 2 SBIR 系统采用的主流技术 向量和特征点匹配在购物搜索应用下的比较 西南交通大学本科毕业设计 论文 第 4 页 3 Canny 算子和 Berkeley Pb 算子 以下简称 Berkeley 算子 的实现 并将其 集成于 SBIR 系统中进行性能对比 其中 MindFinder 索引机制的实现是本课题的核心内容 在这一模块中 本文 结合购物搜索的特性 对该机制所采取的原始策略进行了些许改变 以作为最终 SBIR 系统的基础 为了实现索引的快速读取 本文采用了性能颇为高效的面向对象 语言 C 并针对查询和构建索引过程分别设计了散列表 倒排列表等读写速度优 秀的数据结构 尽管基于特征点的形状匹配能够很好地应用于 SBIR 系统 倒排索引机制的加 入更使得其对大规模的商品数据有着很好的可扩展性 但本课题仍希望将这一技术 手段与 SBIR 系统主流采用的另一种匹配手段 基于向量的形状匹配 加以对 比 以评判哪一种思路更适合于购物搜索应用 在这一模块中 本文主要采用了 Eitz 等人提出的 Tensor 向量 6 并采用 Matlab 语言加以实现 在实验部分中 本文 采用了 2W 张箱包商品图像 通过匹配结果和搜索性能两个方面来比较两种匹配技 术的优劣 在采用特征点索引机制实现了 SBIR 系统之后 我们发现 该系统的搜索结果 在很大程度上依赖于预处理阶段中边缘检测过程的结果 为了更清晰地了解该过程 对 SBIR 系统的影响 本文中分别实现了 Canny 和 Berkeley 边缘检测算子 在实验 阶段 通过采用两种算子对 2W 张服装商品图像进行边缘检测 并在两个边缘图像 集合上分别建立特征点索引 本文实现了 SBIR 系统对不同边缘检测算法的集成 在比较两种算法的边缘提取结果和两种索引下系统的搜索结果之后 本文推导出了 边缘检测过程对 SBIR 系统搜索结果的影响 并提出了若干改进方案 1 5 本论文的结构安排 本论文共包括为 4 个章节 在第一章中 主要阐述了课题的研究背景及意义 简单介绍了部分边缘检测的 成果以及 MindFinder 图像搜索系统 并概括了课题的研究内容 在第二章中 概述了本课题研究所需要的基础知识 包括几种边缘检测算法的 原理 向量匹配和点匹配算法的原理以及 MindFinder 系统的索引机制 并简单介绍 了系统和算法实现过程中所使用的编程工具及其环境配置 第三章是算法实现和系统的搭建过程 主要包含了 Canny Berkeley 检测算法 和 Tensor 向量算法的实现 以及 SBIR 系统中前后台模块的搭建 第四章是在该系统已完成的基础上进行的实验 包括两种匹配算法的比较和两 种边缘检测算法的测试结果 西南交通大学本科毕业设计 论文 第 5 页 第 2 章 相关知识概述 2 1 Canny 边缘检测原理 2 1 1 概述 Canny 算子是 John Canny 在 1986 年提出的一个多层次边缘检测算法 11 为了更 清晰地对边缘检测问题进行定义 他创立了一种边缘检测计算理论 并将该定义划 分为三个标准 即 好的检测 好的定位和最小响应 其中 好的检测 是指 要降低检测边缘点失败的概率和错误检测非边缘点的 概率 由于这两个概率都随着信噪比的增加而减少 所以这一标准即可表征为求解 信噪比的最大值 而 好的定位 则是指 算子检测出的边缘点应该尽可能地接近 实际边缘 最后 最小响应 的意思是 检测出的边缘只能响应一次 并且不能将 图像噪声当作边缘 为了实现上述目标 Canny 采用了最优解的思想 试图通过变 分法 找出满足特定功能的函数 2 2 2 算法流程 该算法的步骤如下 1 减少噪声 与很多图像处理应用一样 在进行下一步检测之前需要采用高斯 滤波对原始图像进行平滑 这一步骤的目的是为了消除部分噪声点对原始数据的影 响 2 计算图像的亮度梯度 Canny 算子仅考虑了亮度通道 因而只需计算亮度梯 度的幅值和方向 该算法在每一点计算出水平和竖直方向的一阶差分 分别记为 和 再通过式 2 1 和 2 2 分别用和表示梯度大小和指向 为了更好地统 x G y GG 计梯度属性 该算子将计算所得的梯度值置入四个方向域中 2 1 22 yx GGG 2 2 x y G G arctan 3 非极大值抑制 可以认为 边缘点会出现在梯度幅值较大的地方 但为了避 免噪声点的影响 需要将具有局部极大梯度值的点表征地更为突出 这就需要采用 一定的策略对亮度梯度非极大值进行抑制 在这一步骤完成后 即可得到所谓的 瘦图像 4 边缘追踪和连接 在上一步骤的基础上 采用双阈值法过滤掉阈值外的非边 缘点 之后 再结合低阈值过滤得到的结果图像 将高阈值过滤图中的边缘点连接 西南交通大学本科毕业设计 论文 第 6 页 起来 这样重复迭代直至不再变化后 便可得到最终的边缘图像 2 2 Berkeley 边缘检测原理 2 2 1 概述 Berkeley 的计算机视觉研究小组一直致力于边缘检测算法的研究 并结合多人 的工作构建起一个将轮廓进行人为标注的图像集合 BSDS 16 用于边界提取算法的基 准测试和机器学习 本课题所采用的 Pb 算子 12 便是该小组的 Martin 等人在近几年 提出的一个以 BSDS 子集作为训练集合的边缘检测算法 该算法的本质是将边缘检测问题看作分类问题 通过训练一个分类器将边缘像 素点与非边缘像素点区分开来 从而最终得到对边界点可能性的估计 其最大的贡 献在于 将亮度 颜色和纹理等局部特征加以结合 使得最终的检测结果在精确度 查全率评测中有更好的效果 这一特征合并的工作 在边缘检测领域并不多见 而 对纹理特征的详细描述 也使其对自然图片的检测有着相较于其他方法更为突出的 结果 2 2 2 算法流程 该算法的整体思路如下 建立模型对特征 包括亮度 颜色和纹理 加以描述 将已描述的特征局部化 在训练集上对局部特征进行单独优化 将多个特征加以合 并 监督式训练分类器 详细来说 首先 该算法试图用方向能量和光度的方向梯度值来描述亮度 而 用色度的方向梯度来描述颜色 在计算方向梯度时 Martin 提出以像素点为圆心限 定一个圆形区域 以直径为线将其划分成两个半圆后分别计算梯度直方图 通过计 算不同角度的直径划分后两半圆直方图之间的差值 就可以定量描述该点处在不同 方向上的特征属性 而对纹理特征而言 则需要一系列滤波来对原始图像进行预处 理 完成后可以得到一系列量化的向量 在对该向量的直方图进行统计后 即可采 用同样的半圆差值法得到该点处在不同方向上的纹理特性 其次 在定位阶段 该算法需要将位置空间信息 转化为判定边缘点存在的依 据 由于纹理特征的处理出现了两个问题 即无法通过特征值判断边缘方向 以及 在边缘两侧的特征值要高于边缘点上的值 也就是双峰值问题 这两个难题即使在 其他研究中也一直困扰着纹理特征的处理和分析 而该算法中 作者在意识到该现 象的对称性后 提出了一个变换原始特征信号的方法 从而加强了局部极大特征值 并最终消弱了这些异常现象 而亮度和颜色特征 经作者研究后发现 在定位后对 性能的影响并不大 故而没有此项处理过程 再次是特征模型优化阶段 各项特征的描述模型在单独训练之后 将尺度等参 西南交通大学本科毕业设计 论文 第 7 页 数加以调整 得到了最优的描述效果 最后就是训练阶段 该算法为了消除冗余 而将描述亮度特征的性能较差的方 向能量排除 通过采用密度估计 分类树 逻辑回归以及支持向量机等分类器 在 人为标注训练集合的基础上进行监督式训练 并最终获得了可靠的边缘检测算子 2 3 二值手绘曲线与彩色自然图像的匹配 在基于手绘线条的图像搜索系统中 趋待解决的核心问题是 如何拉近二值曲 线与彩色图像间的语义距离 进而评判二者的相似程度 学术界对此难题有很多不 同的解决方案 而其中较为突出的有基于向量和边界点的匹配 前者的设计思路是 对二值曲线和彩色图像单独分块 以不同的策略合并成高维向量 再通过计算欧式 距离来评判二者的相似程度 而后者则是在对彩色图像进行边缘检测的基础上 将 边界像素点作为特征点 通过点与点的匹配来计算二者的符合度 MindFinder 所采 用的索引机制便是在后者基础上进行的性能优化 为了比较两种策略在购物搜索应 用中的性能优劣 本文将分别介绍几种典型算法 并在后文通过实验结果来比较二 者的差别 2 3 1 基于向量的匹配 采用高维向量来描述图像的梯度及其位置分布特性的思路 在学术界已被应用 多年 MPEG 7 标准中的边缘直方图描述子 EHD 4 以及用于人脸检测的梯度直 方图描述子 HOG 都已成为了业界成熟的形状描述方案 而 Chalechale 等人提出 的以角度分块获得向量表达 ARP 的方法 3 在基于手绘线条的图像搜索中也有不 俗的表现 为了评估不同策略的性能 柏林工业大学的 Eitz 等人在近年的一项研究 中 6 将 EHD HOG ARP 等多种形状描述子应用于二值曲线和彩色图像的匹配 而测试结果中最优的方案就是作者自己提出的结构张量 Tensor 描述子 下文将对该 方法进行详细介绍 并在稍后的章节中加以实现 结构张量是一种用于描述图像局部结构的表达方式 这一匹配算法的核心思想 便是试图通过张量来表述图像局部块的梯度主方向 进而反映出图像的梯度分布特 性 并通过对二值曲线和全彩图像采用同样的处理过程 来实现二者相似度的比较 算法的第一个步骤 是将原始图像均等划分为若干小单元 在每个小单元内 计算 的目标是试图找出一个单位向量 使其能够描述该单元内的主要方向 其过程如x 下 首先 将该向量定义为下式中的形式 2 3 ij Cvu uv T x gxx 2 1 maxarg 西南交通大学本科毕业设计 论文 第 8 页 其中 为点 u v 处的梯度向量 uv g 另由等式 2 4 xGxgx ij T Cvu uv T ij 2 可知 计算单位向量的问题即可转换为 在的限制下将中的二次方1 xxT x 程式最大化 而该等式中的矩阵就是之前所提到的结构张量 经过分析可知 只 ij G 需求解的特征向量 就可以得到该单元的主方向 在该算法中 作者将标准 ij G ij G 化后的结果作为第 i j 个单元的梯度分布表述向量 并将所有单元求得的拼接 ij T ij T 成一个高维向量 这样 即可通过计算向量间的欧氏距离来评判图像间的相似度 2 3 2 基于边界点的匹配 与基于向量的思路不同的是 这一类匹配算法不关心空间分布信息 而仅考虑 不同图像上边缘像素点间的对应关系 因此对形状的细微变化更加敏感 上个世纪 出现的槽匹配 Chamfer Matching 算法 7 就是该解决方案中突出的一个 下文将 详细介绍该算法思想以及它的一个变型 经过边缘检测的预处理之后 原始图像被转换为仅含有边界点的二值图像 假 设两幅待比较图像包含的像素点数分别为和 该算法的思路便是通过计算两者 a n b n 重合 点的个数来评判相似度 在这里 重合 的意思是指 两点位置之间的距 离在一定的阈值以内 为了统计 重合 点数 最简单的思路就是遍历两幅图像上 的所有点 从而达到的时间复杂度 这一计算量对于自然图像来说是十分 ba nnO 庞大 也是不可接受的 为了实现性能上的优化 槽匹配算法采用了距离变换 Distance Transformation 过程 其原理是 在边界点图像的基础上构建一个被称 为距离变换图的中间数据结构 并以此为依据判定两幅图的 重合 度 在这一距 离变换图中 每个点的权值可由以下公式确定 4 3 4 3 3 4 3 4min 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k ji k ji k ji k ji k ji k ji k ji k ji k ji k ji pppppppppp 2 5 其中 表示第 k 次迭代时点 i j 的值 若 i j 处为像素点 则 0 否则为 k ji p 0 ji p 无穷大 当某次遍历后权值均没有变化时 迭代即可停止 这样 变换图上的每一个点即可 存储该点与邻接边界点的距离信息 为其中一幅图像建立变换图后 边缘距离的计 算即可由下式完成 2 6 n i i p n d 1 2 1 3 1 西南交通大学本科毕业设计 论文 第 9 页 其中 表示待匹配图像的第 i 个像素点对应的距离变换点的权值 虽然公式 i p 2 5 和 2 6 也可以用不同的赋值和均值公式替代 但经实践证明 此处采用的参数 得到的匹配度 d 能很好地模拟点对点匹配的结果 最初提出的槽匹配仅考虑了边界点的位置 因而丢失了梯度这一描述轮廓方向 的重要信息 为了弥补这一缺陷 使点匹配算法更加健壮 方向槽匹配 Oriented CM 的概念被提了出来 这一思想与以往算法的最大区别在于 边界点根据自身的 梯度方向被划分为多个集合 各子集将单独构建距离变换图 这样一来 轮廓方向 的不同导致边界点具有不同属性 因而排除了互相干扰的可能 同时也提高了匹配 精确度 集合分类的方法可采用角度域的均等划分 即将 360 度的范围切割为 k 个 相同大小的桶 根据 4 个邻接点计算出该边界点的梯度方向后 就能将该点放入唯 一的桶 2 3 3 总结 正如上文中提到的 向量法倾向于关注图像中梯度的分布规律 而点匹配法则 更重视每个独立边界点的位置对匹配结果的影响 这种差别直接导致了前者比后者 具有很强的位置不变性 而通过适当的策略调整甚至可以实现旋转不变性 这一特 性对于通用图像搜索引擎而言是十分突出的优势 但却不太适应于对精确度要求较 高的购物搜索应用 箱包的与众不同 服装的特立独行 很可能就在形状的微量偏 移中得以体现 因此 经过初步分析可以看出 向量法更适合于类别查找 而点匹 配则更擅长于区分同类别的细微差别 从效率的角度来说 虽然点匹配难以与向量 距离的计算过程相比 但下文中提到的索引机制可以极大地优化这一匹配流程 从 而实现大规模数据集下的实时搜索 具体的实验测试结果将在第四章中详细介绍 2 4 MindFinder 索引机制 2 4 1 背景 尽管采用距离转换的方法能将二维点匹配的时间复杂度从大幅降低至 ba nnO 一维的 但每幅图像仍需要二维的空间复杂度以存储距离转换图的数据 以 a nO 空间交换时间 这原本是算法设计中十分有效的优化方案 但却限制了数据集的扩 展 以 300 300 的图像为例 若以一个字节保存距离权值 设置 6 个桶 则一幅图 像的距离变换图至少需要 500KB 而当图像数据集达到十万级别时 内存中至少需 要 54GB 很显然 这样的空间负荷不是一般的服务器能够承受的 当数据规模继 续扩展时 距离变换对点匹配算法的优化在物理上已经无法实现 正是在这样的背 景之下 微软亚洲研究院的王小虎等人在方向槽匹配算法的基础上提出了可索引的 方向槽匹配 Indexable OCM 算法 并提出了 MindFinder 图像搜索系统 9 西南交通大学本科毕业设计 论文 第 10 页 2 4 2 算法流程 该算法的设计思想借鉴了信息检索中经典且高效的倒排索引机制 将图像中的 边界点类比于文档中的字段 实现查询图像在大规模数据集上的实时搜索 该算法 主要实现的是查询图面向数据集合的单向搜索 其构建索引的流程如下 在对图象集合进行预处理的第一步 就是将原始图像缩放为高度为 200 像素的 标准图 由于匹配算法在很大程度上依赖于像素点的绝对位置 所以归一化过程是 十分必要的 接着 采用适当的边缘检测算法提取出边界点集合 接着 计算各边 界点的梯度方向后得到对应的集合 并使用三元组表示该特征点 接下来 yx 的步骤与 CM 的距离变换过程类型 惟一的区别是变换图中的点不再被赋以权值 而是将所有边界点附近 r 范围以内的点置为 1 其他的为 0 如下式所示 2 7 0 其参数说明如下 表 3 1 cvCanny 函数各参数说明 参数说明 image单通道输入图像 edges单通道存储边缘的输出图像 threshold1第一个阈值 threshold2第二个阈值 aperture sizeSobel 算子内核大小 提出 Pb 算子的伯克利计算机视觉小组 在其研究主页提供了该算法的 Matlab 实现代码 并包含了 pbBGTG pbBGCG 和 pbCGTG 等检测算子 在测试各算子在 商品自然图像上的检测结果后 本系统采用了其中速度最快而效果较好的 pbBGTG 算子 两种算法各自提取的边缘图像如图 3 1 所示 a 原始图像 b Canny 边缘 c Berkeley 边缘 图 3 1 边缘图像 西南交通大学本科毕业设计 论文 第 15 页 3 1 2 Tensor 向量匹配算法 值得注意的是 Tensor 算法作为一个基于向量的形状匹配策略 无法集成进本 课题所实现的点匹配索引机制 之所以在此处实现该算法 是为了比较点匹配与向 量匹配在购物搜索应用中的优劣 因此 基于 Tensor 向量的手绘线条搜索可看作是 与前文所实现的系统相独立的过程 由于该算法的实现不仅需要对图像数据的基本操作 更需要强大的矩阵运算工 具 所以本模块主要采用 Matlab 的图像处理和矩阵运算工具完成 而搜索过程中的 对向量间的欧式距离计算需要更高的效率 所以由 C 代码实现 1 向量计算阶段分为以下步骤 将原始彩色图像均分为 8 6 的小块 以 和计算图像中每一个像素点对应的梯度值 然后在每个小块内 1 0 1 hxxhhy 计算 4 维 Tensor 值并在当前区域内归一化 最后将各分块的结果拼接起来 即可得 到描述该图像在各分块内主方向的 Tensor 向量 如图 3 2 所示 详细代码见附录 a 原始图像及其分块 b 第一行 8 个分块的 Tensor 向量 图 3 2 原始图像分块及块内 Tensor 向量 2 在计算出数据库中每张图像的向量值之后 为了搜索出最匹配的相似图像列 表 需要一个高效求解欧氏距离并排序的程序 为了加快匹配效率 该程序将数据 库中所有图像的 Tensor 向量载入内存 由于在后续实验中对该相似列表计算的要求 8 6 分块 每行 8 块 每列 6 块 西南交通大学本科毕业设计 论文 第 16 页 是离线的 所以可以通过空间换时间的方法进行微量优化 这就需要记录任意两对 向量间的欧氏距离 以减少不必要的计算 为了达到该目标 程序中采用了一个一 维的缓存数组 以个向量为例 该数组的容量可为 待计算好向量N 2 1 NN 间的欧氏距离并存入内存后 再进行升序排列即可得到相似图像列表 图 3 2 中原始图像的相似图像列表及各图像对应的欧式距离如下图所示 a 原始图像及前三个最相似商品 b 各相似图像对应的欧式距离 图 3 3 相似图像及其欧式距离 3 2 系统设计 本课题的最终目标是构建一个基于手绘线条的图像检索 SBIR 系统 并实现 其在大规模商品数据集合之上的购物搜索应用 这一系统的实现过程是本文中最为 核心的技术模块 也是后文中对匹配方式和边缘检测算法进行实验比较的必要条件 为了达到该目标 本文借鉴了 MindFinder 系统中的 IOCM 思想 集成了 Berkeley 边 缘检测算法 并开发了一套可进行高效读取和查询的倒排索引机制 从而在实现系 统功能的同时极大地提升了其搜索效率和查询结果 实验表明 通过对 2W 张商品 图像构建索引 该系统对手绘线条输入的平均搜索时间可控制在 5s 以内 在本章接 下来的内容中 将详细介绍该系统的功能分析 结构模块和具体实现 3 2 1 功能分析 该系统主要包括两个部分 即对图像库进行预处理的后台模块和获取手绘线条 并完成搜索过程的前台模块 在后台处理模块 系统需要完成的功能有 将原始彩色自然图像归一化 提取 归一化图像的边缘图 提取边缘图中的特征点并生成距离变换图 即生成特征文件 在特征文件库上构建索引结构 运用该结构完成查询图在图像库上的搜索 获得相 似列表 在前台搜索模块 系统的功能主要包括 提供用于绘制的画板以获取手绘线条 根据后台搜索所得的相似列表展示搜索结果 西南交通大学本科毕业设计 论文 第 17 页 3 2 2 系统结构 索引 结构 原始 图像集 标准 图像集 边缘 图像集 特征 文件集 手绘 线条 特征 文件 相似 列表 获取手绘线条 搜索结果展示 图像归一化 提取边缘图像生成特征文件 构建索引 查询相似图像 后台处理 前台搜索 图 3 4 系统结构图 3 3 后台处理模块实现 作为本系统的核心模块 后台处理的功能对性能和效率有很高要求 因此 该 模块的实现主要采用 C 语言 而遍历文件夹 迭代运行 C 程序等部分文件和数 据处理过程则采用了编程效率更高的 python 语言 3 3 1 图像归一化 在图像归一化阶段 系统采用了 OpenCV 提供的函数库对图像的大小进行重置 如同 MindFinder 系统实现中一样 本系统将原始图像缩放为宽高不超过 200 的标准 图 为了实现对整个图像库的归一化过程 系统将 resize 程序封装为 exe 可执行文 件 并由 python 脚本调用执行 其中 resize 程序采用了 OpenCV 工具库中的 cvResize 函数 void cvResize const CvArr src CvArr dst int interpolation 其参数说明如表 3 2 所示 而 python 程序则采用 os 包中的 os walk 函数完成了对文件夹的遍历 并使用 os system 函数实现了对 resize exe 可执行文件的调用 西南交通大学本科毕业设计 论文 第 18 页 表 3 2 cvResize 函数各参数说明 参数说明 src输入图像 dst输出图像 interpolation 插值方法 CV I