第一篇：特征选择算法综述20160702

特征选择方法综述

控制与决策 2012.2

     问题的提出 特征选择框架

基于搜索策略划分特征选择方法 基于评价准则划分特征选择方法 结论

一、问题的提出

特征选择是从一组特征中挑选出一些最有效的特征以降低特征空间维数的过程，是模式识别的关键问题之一。对于模式识别系统，一个好的学习样本是训练分类器的关键，样本中是否含有不相关或冗余信息直接影响着分类器的性能。因此研究有效的特征选择方法至关重要。

特征选择算法的目的在于选择全体特征的一个较少特征集合，用以对原始数据进行有效表达按照特征关系度量划分，可分为依赖基尼指数、欧氏距离、信息熵。

二、特征选择框架

由于子集搜索是一个比较费时的步骤，一些学者基于相关和冗余分析，给出了下面一种特征选择框架，避免了子集搜索，可以高效快速地寻找最优子集。

从特征选择的基本框架看出，特征选择方法中有4个基本步骤：候选特征子集的生成（搜索策略）、评价准则、停止准则和验证方法。目前对特征选择方法的研究主要集中于搜索策略和评价准则。因而，本文从搜索策略和评价准则两个角度对特征选择方法进行分类。

三、基于搜索策略划分特征选择方法

基本的搜索策略按照特征子集的形成过程，形成的特征选择方法如下：

图3基于搜索策略划分特征选择方法

其中，全局搜索如分支定界法，存在问题： 1）很难确定优化特征子集的数目； 2）满足单调性的可分性判据难以设计；

3）处理高维多类问题时，算法的时间复杂度较高。

随机搜索法如模拟退火、遗传算法、禁忌搜索算法等，存在问题：

1）具有较高的不确定性，只有当总循环次数较大时，才可能找到较好的结果。

2）在随机搜索策略中，可能需对一些参数进行设置，参数选择的合适与否对最终结果的好坏起着很大的作用。

启发式搜索如SFS、SBS、SFFS、SFBS等，存在问题： 1）虽然效率高，但是它以牺牲全局最优为代价。

每种搜索策略都有各自的优缺点，在实际应用过程中，根据具体环境和准则函数来寻找一个最佳的平衡点。例如，特征数较少，可采用全局最优搜索策略；若不要求全局最优，但要求计算速度快，可采用启发式策略；若需要高性能的子集，而不介意计算时间，则可采用随机搜索策略。

四、基于评价准则划分特征选择方法

图4基于评价准则划分特征选择方法

（一）考虑单个特征对分类的贡献，特征选择方法依据其与分类器的关系分为：Filter方法、Wrapper方法和Embedded方法３类。

封装式算法作为一种经典的特征选择算法类型采用学习算法进行特征选择，其选择过程复杂耗时，目前多与过滤式特征选择算法结合，辅助特征选择；嵌入式算法则分多步骤采用不同选择方式，算法繁琐，其代表算法是基于稀疏多项式逻辑回归模型理论的SBMLR算法等；过滤式算法不需其他学习算法，主要考察特征间计量关系，方法简单，时间复杂度相对较低，代表算法包括：基于特征权重的Relief F、Fisher、SPEC以及基于互信息的MRMR算法等。（1）Filter方法：通过分析特征子集内部的信息来衡量特征子集的好坏，不依赖于分类器。Filter实质上属于一种无导师学习算法。

常用：基于特征权重的Relief F、Fisher、SPEC以及基于互信息的MRMR算法

Filter 特征选择方法一般使用评价准则来增强特征与类的相关性，削减特征之间的相关性。将评价函数分成4类：

1）距离度量。距离度量通常也认为是分离性、差异性或者辨识能力的度量。最为常用的一些重要距离测度：欧氏距离、S阶Minkowski测度、Chebychev 距离、平方距离等。

2）信息度量。信息度量通常采用信息增益(IG)或互信息(MI)衡量。

信息增益：有无这个特征对分类问题的影响的大小。

互信息：描述两个随机变量之间相互依存关系的强弱。

泛化的信息度量函数标准：

其中，C：类别；f：候选特征；S：已选特征；g(C,f,S)：C，f，S之间的信息量； Ɑ：调控系数；δ：惩罚因子

① BIF(best individual feature)是一种最简单最直接的特征选择方法。

评价函数：

I（）：互信息

降序排序

前k个

优缺点：这种方法简单快速，适合于高维数据。没有考虑到所选特征间的相关性，会带来较大的冗余。

② MIFS(mutual information feature selection)：互信息特征选择。使用候选特征f与单个已选特征s相关性对f进行惩罚的方法。

β：调节系数。β在[0.5,1]时，算法性能较好。

③ mRMR(minimal-redundancy and maximal-relevance)方法。思想：最大化特征子集和类别的相关性，最小化特征之间的冗余。

④ FCBF(fast correlation-based filter)。基于相互关系度量给出的一种算法。对于线性随机变量，用相关系数分析特征与类别、特征间的相互关系。对于非线性随机变量，采用对称不确定性(SU)来度量，对于两个非线性随机变量X和Y，它们的相互关系表示为：

H（）：信息熵

基本思想：根据所定义的C-相关（特征与类别的相互关系）和F-相关（特征之间的相互关系），从原始特征集合中去除C-相关值小于给定阈值的特征，再对剩余的特征进行冗余分析。

⑤

CMIM(conditional mutual information maximization)。利用条件互信息来评价特征的重要性程度，即在已知已选特征集S的情况下通过候选特征f与类别C的依赖程度来确定

f的重要性，其中条件互信息I(C;f|S)值越大，f能提供的新信息越多。

3）依赖性度量。有许多统计相关系数被用来表达特征相对于类别可分离性间的重要性程度。如：Pearson相关系数、概率误差、Fisher分数、先行可判定分析、最小平方回归误差、平方关联系数、t-test、F-Statistic等。

Hilbert-Schmidt 依赖性准则(HSIC)可作为一个评价准则度量特征与类别的相关性。核心思想是一个好的特征应该最大化这个相关性。

t:所选特征个数上限；F：特征集合；S：已选特征集合；J(S)：评价准则

从式中可知需要解决两个问题：一是评价准则J(S)的选择；二是算法的选择。

4）一致性度量

给定两个样本,若他们特征值均相同,但所属类别不同,则称它们是不一致的;否则,是一致的。试图保留原始特征的辨识能力,找到与全集有同样区分类别能力的最小子集。典型算法有Focus、LVF等。

Filter方法选择合适的准则函数将会得到较好的分类结果。

优点：可以很快地排除很大数量的非关键性的噪声特征,缩小优化特征子集搜索的规模,计算效率高,通用性好,可用作特征的预筛选器。

缺点：它并不能保证选择出一个优化特征子集,尤其是当特征和分类器息息相关时。因而,即使能找到一个满足条件的优化子集,它的规模也会比较庞大,会包含一些明显的噪声特征。

2）Wrapper法：评价函数是一个分类器，采用特定特征子集对样本集进行分类，根据分类的结果来衡量该特征子集的好坏。Wrapper实质上是一种有导师学习算法。训练集 测试集

优点：准确率高

缺点：1）为选择出性能最好的特征子集，Wrapper算法需要的计算量巨大； 2）该方法所选择的特征子集依赖于具体学习机； 3）容易产生“过适应”问题，推广性能较差

（3）Embedded方法。将特征选择集成在学习机训练过程中，通过优化一个目标函数在训练分类器的过程中实现特征选择。

优点：相对于Wrapper方法，不用将训练数据集分成训练集和测试集两部分，避免了为评估每一个特征子集对学习机所进行的从头开始的训练，可以快速地得到最佳特征子集，是一种高效的特征选择方法。

缺点：构造一个合适的函数优化模型是该方法的难点。

通常，将Filter方法的高效与Wrapper方法的高准确率进行结合，可得到更优的特征子集。混合特征选择过程一般由两个阶段组成：

1）使用Filter方法初步剔除大部分无关或噪声特征,只保留少量特征,从而有效地减小后续搜索过程的规模。

2）将剩余的特征连同样本数据作为输入参数传递给Wrapper选择方法,以进一步优化选择重要的特征。

（二）依据特征之间的联合作用对分类的贡献，分为：CFS（Correltion based Feature Selector）、CFSPabs(CFS based on the absolute of Perons’s correlation coefficient)、DFS(Discernibility of Feature Subsets)。

（1）CFS：基于关联特征的特征选择。CFS计算整个特征子集的类间区分能力实现特征选择，使得被选特征子集中的特征之间尽可能不相关，而与类标高度相关。

Ms：度量了包含ｋ个特征的特征子集S的类别辨识能力。

：特征f（f）与类别C的相关系数的均值 ：特征之间相关系数的均值

分子：特征子集S的类预测能力

分母：特征子集S中特征的冗余程度

适合于二分类

（2）CFSPabs：基于皮尔森相关系数的绝对值的相关特征选择。

（3）DFS：特征子集区分度量。

:当前i个特征的特征子集在整个数据集上的均值向量 :当前i个特征的特征子集在第ｊ类数据集上的均值向量 ：第ｊ类中第k个样本对应当前i 个特征的特征值向量

分子：ｌ个类别中各类别对应包含当前ｉ个特征的特征子集的样本中心向

量与整个样本集对应当前ｉ个特征的中心向量的距离平方和，其值越大，类间越疏。

分母：各个类别对应包含当前ｉ个特征的特征子集的类内方差。方差越小，类内越聚

五、结论

现有特征选择研究主要着眼于选择最优特征子集所需要的两个主要步骤：特征子集搜索 策略和特征子集性能评价准则。将Filter方法和Wrapper方法两者结合，根据特定的环境选择所需要的度量准则和分类器是一个值得研究的方向。

第二篇：基于形状特征的图像检索算法仿真实现研究

本科毕业设计（论文）

工 作 手 册

（理工类专业适用）

学 院

专业班级

姓 名

学 号

指导教师

二○一 年 月 日

基于形状特征的图像检索算法仿真实现研究

摘要:近年来,随着数字多媒体和移动计算机以及互联网信息技术的快速进步发展,数字图像的应用数量正以惊人的增长速度不断增长。面对日益丰富的数字图像媒体信息这个海洋,人们仍然需要有效地从中不断获取所有人期望能够得到的更多媒体信息。因此,在一个大规模的数字图像检索数据库中如何进行快速、准确的图像检索已经成为当前人们图像研究的一个热点。

为了能够实现快速而准确地进行信息检索数字图像,利数字图像的主要视觉信息特征,如图像颜色、纹理、形状等元素，基于形状的数字图像信息检索处理技术应运而生。本文主要深入研究基于图像形状基本特征的边缘图像侦测检索,边缘图像检测检索是基于图像形状基本特征的一种有效检索图像方法,边缘检测是检索图像最基本的形状特性。在图像景物边缘特征检测中,微分这个算子算法可以准确提取和输出景物图像的一些细节分析信息,景物图像边缘特征是图像细节分析信息中最主要具有不可描述性的景物边缘特征的部分,也是进行图像边缘分析过程中的一个不可或缺的部分。本文详细地阐述分析了一种局部边缘厚度检测算子方法,即canny方法算子,用c++编程语言实现各方法算子的局部边缘检测,并根据算子边缘厚度检测的准确有效性和边缘定位的准确可靠性,得出这种canny方法算子已经具备了所有最优化的边缘厚度检测所应必需的各种特性。并通过基于图像轮廓的图形描述表示方法,傅里叶轮廓描述符对一个图像的轮廓形状及其特征特点进行轮廓描述并将其存入图像数据库中。对行业也相应的具有检索查询功能。

关键词:形状特征检索;边缘图像检测;傅里叶描述符

一、前言

随着现代信息化工业社会的到来,几乎任何一个学科研究领域的技术发展都和现代计算机技术密切联系有关,人们所需要处理的图象信息已不仅仅只是一些数字、符号等的信息,而是越来越多地与人接触并得到大量的数字图象内容信息.其中例如:航空卫星信息遥感监测图象、医学遥感图象、地理水文信息监测图象等.而且在实际技术应用中随着时间的不断推移,图象信息数量也在不断扩大,利用各种人力来对这些图象信息进行内容浏览和信息检索，不仅仅需要大量的精力和时间,浪费大量的的人力,而且几乎已是不可能完成的一件事。这样需要利用计算机对这些数字图象内容进行有效内容组织和信息检索便已经成为现代人们科学研究的重要课题.因而传统的数字图象内容表达和信息检索处理方法往往是需要使用图象文件名、标题、关键词数字等.目前,这种检索方法已不能完全满足现代人们的技术要求.因此,人们越来越迫切地认识需要对这些图象的各种可视性和特征图象进行信息提取,并且根据这些可视特征对各种图象内容进行信息检索.基于图象内容的数字图象信息检索处理技术,也正是在这样的一种情况下发展产生的.基于图象内容的数据图象信息检索数据技术就是通过数据分析一个图象的主要内容(例例如:颜色、纹理、形状等),从大量活动视频图象库中查找含有特定物体的图象,它充分克服了现代传统检索方法的不足,融合了数字图象处理、图象识别和网络图象检索数据库等多个领域的最新技术成果,从而完全可以为你提供更有效的图象检索技术手段.它们既充分体现了特征图象的基本信息处理特点,又充分结合了现代传统图象数据库检索技术.其基本检索过程一般是:首先对一个图象特征进行图像预处理,然后根据特征图象的基本内容从特征图象中直接选取所有有需要的特征图象形状特征,存于图象数据库中;然后当对一个图象特征进行勾画检索时,对于一个图象已知的特征图象首先抽取其具有相应的图象特征,然后在整个图象数据库中进行检索与其相似的特征图象,也或者可以根据相对于某一个的查询对象要求直接给出一些图象特征点和值,然后根据所需要给定的图象特征点和值在整个图象数据库中进行检索所要的特征图象.结果例如:对于基本相同形状带有特征的图象检索,你或许可以直接给出一些有关被勾画检索某个对象的基本形状特征描述,可以认为是一些带有特征点的值,也或者可以认为是勾画出的检索对象的形状略图;对于基本相同颜色的图象检过,可以直接给出不同颜色的物体比例或者关系,等等.最后,给出图象检索后的结果.目前,从事这一技术课题相关研究的年轻人越来越多,国外许多著名科研机构和专家学者都在积极进行许多有关这一技术课题的相关研究,例如:公司的数据检索系统.国内的许多专家学者和相关科研机构也在积极进行此技术问题的相关研究.本文首先对基于对象内容实体图象的的检索数据进行了简要的理论概括,然后对基于实体对象动态形状的实体图象内容检索数据理论基础进行了深入的理论研究,包括:基于对象形状的实体图象内容检索计算方法,对象实体形状的综合描述,图象形状配匹检索算法,最后本文给出了一个基于对象形状的实体图象内容检索数据原型管理系统,并在一台微机上加以实现,该原型系统主要功能包括内容图象检索数据库的管理建立,数据库的日常维护,图象的信息查询等几个功能.二、研究介绍

2.1、课题背景及研究意义

随着现代多媒体网络技术、计算机网络技术、通信网络技术及互联网络的迅速进步发展,人们正在快速地发展进入一个现代信息化的新社会。现代信息技术已不可能能够运用各种技术手段大量的进行采集和分析产生各种类型的海量多媒体信息数据,人们对各种多媒体信息的采集需求也越来越大量和频繁。虽然人类信息的数量快速增长直接促进了人类社会的快速发展,但是由于信息快速膨胀也给现代人类社会带来了过多的的信息量以至于远远超过了这类人的整体接受信息能力。因此,除了怎样获取、处理和传输存储各种多媒体信息十分重要,怎样在各类海量的各种多媒体信息中快速有效地准确访问这些人们经常感兴趣的各种多媒体信息也对其显示体现出了同样的巨大重要性。

图像抽象信息采集是传统多媒体信息中最常见的一种,也因其具有传统多媒体信息采集数据量大、抽象应用程度低的基本特点。如何从各种海量的有用图像处理信息中有效地收集获取有用图像信息,即使是图像处理信息数据资源的使用管理和信息检索也就显得日益重要。随着当前人们对文字图像文本信息的巨大检索需求的不断增长,产生了基于图像文本的文字图像信息检索引擎技术,比如著名的中文搜索结果引擎google和百度中对文字图像的文本检索。这种基于人类文本的人工检索标注技术所广泛利用的人工文本标注检索方法虽然存在一些局限性,经常进行检索时会出来大量的一些用户不感兴趣的文本图像,但在没有找到更好文本解决办法的实际情况下,用户通常只能选择继续检索使用。因此如何对一个图像的特征内容自动、客观、全面地对其进行特征提取。真实有效的准确表示数字图像信息内容,帮助用户快速有效地检索访问自己感兴趣的信息图像内容，有着极大的科学研究领域需求和迫切的应用需要,而基于图像形状特征的数字图像信息检索分析技术恰好真正能有效的帮助解决这个现实问题。另外在实际的应用中,图像信息数据库及其信息检索的技术研究对医学多媒体图像数字图书馆、医学临床图像应用管理、卫星图像遥感网络图像和应用计算机图像辅助设计和开发制造、地理位置信息采集系统、犯罪识别系统、商标标识版权的使用管理,生物的形态辨识以及分类等诸多方面可以提供有力的技术支持。

2.2、国内外发展状况

近年来,CBIR已经逐渐发展早熟成为一个非常活跃的医药临床医学研究应用领域,各类我国顶尖临床科研机构与临床研究公司已陆续成功开发推出了一些基于CBIR临床应用管理系统的临床研究应用产品,有的已经成功广泛应用扩大到医药临床医学、商标、专利技术以及检索等诸多研究领域。

IBM的系统QBIC是它是第一个具有商业性的基于CBIR的子系统。它们还提供了基于图像颜色、纹理、形状和其他手绘图像草图的多种图像类型索引使用方法。columbia大学的图库Visual SEEK图库提供了基于自然色彩和立体纹理的多种索引分析方法。PhotoBook 是美国麻省理工学院和多媒体科学实验室自主开发的一套用于检索、浏览人脸图像的交互式检索工具,它其中包含三个图像子系统分别用于提取人脸形状、纹理和各种人脸面部特征,用户甚至可以分别定制做基于上述一种人脸特征的图像检索。MARS(multimedia analysis and retrieval system)这个系统由美国UIUC 大学负责开发,其不同之处主要在于用户学到了很多专业领域的基础知识:例如计算机图像视觉、数据库资源管理和云系统和网络信息资源检索。新加坡国立大学公司开发的一个基于复杂内容的模糊图像信息检索系统,其显著性的技术创新特色主要包括:多种特征提取的新方法、多种基于复杂内容图像检索的新方法、使用自定义组织式的神经网络对复杂内容特征进行度量、建立基于各种内容图像索引的新应用方法以及对各种多媒体信息格式进行模糊图像检索的新应用技术。

清华大学的数字ImgRetr检索结合了多种组织检索方法,就这样能为您提供基于形状主色、纹理、直方结构图、颜色元素分布、框架等多种组织方式的形状检索。

2.3课题研究的主要内容

本文主要依托基于物体形状的网络图像信息检索分析技术,重点深入研究基于物体形状动态特征的网络图像信息检索。形状纹理特征不同于物体颜色、纹理等的特征,形状纹理特征的正确表达必须以对物体图像中每个物体或图像区域的正确划分来作为理论基础。在二维矩形图像中的空间中,形状通常被我们认为为它是由于一条完全封闭的并由轮廓映射曲线所形成包围的特征区域。通常这种情况下.二维形状中的特征区域有两类可以表示它的方法,一类可以是一个区域形状特征,利用的可以是整个二维形状特征区域;另一种分类可以是一条轮廓曲线特征,利用的则可以是二维图像的整个外边和内界。本文主要重点研究的领域就是外界与边界的边缘索引测量方法边缘测量检测,边缘测量检测的常用方法主要有很多,如:roberts矩形交叉曲线微分代数算子、sobelt微分代数算子、priwitt交叉微分代数算子和Laplacian微分代数算子以及canny微分算子。而其中属Canny算子最好。

本文主要深入研究的字符是傅里叶描述符。其主要理论思想观点是用关于物体内部边界的傅立叶变换公式作为其物体形状学的描述。

2.4、相关内容介绍

2.4.1形状分析

2.4.1.1、形状特征

常用的长轴形状运动特征参数有长轴周长、形状特征参数、偏心率、长轴运动方向与弯曲运动能量等矩阵的描述、综合光密度以及三维轮廓的应力矩也同样可以用于表示和用来描述三维图像。

2.4.1.2特征选择

通常一般来说,形状的形态表示特征图型表示法具有两种常用图形表示法的表现方法,一种表示方式主要是用来表示具有轮廓性的形状形态特征,另一种表示方法主要是用来表示具有区域性的形状形态特征的。前者一般来说只用于看到整个部件物体的内部外观和形状边界,而后者则直接把它关系着其应用到整个部件物体外观形状上的各个区域。

2.4.2、一种基于形状的图像检索算法

2.4.2.1、算法分析

基于这种形状的图像检索更多地只是用于了解当前的用户能够粗略地扫描画出一个图形轮廓之后进行图形检索的实际情况。这种图形轮廓绘图可以认为是通过用户凭借自己脑子在空中的第一印象徒手自动画图绘出来的,也甚至可以认为是通过操作系统软件提供的基本图形绘图处理工具“拼凑”的。这两种检索情况都不具有一个基本特点,即它所提供的检索形状只是对所欲检索图象形状的粗略抽象描述,它从它的大小、方向或者其整体形状结构上都很有可能与真正根据要求调查的检索图形形状有较大小的出入。因此,基于面的形状进行检索的主要难点仍然在于需要寻找一种能够准确检索与面的大小、方向及整个扭曲面的伸缩程度无关的检索方法。

不变矩和产品轮廓的应力不变矩的方法产品具有良好的轴向平移、旋转、尺度上的缩小和放不变性及高度抗干扰性。用一个图像的形状不变矩和图像轮廓的应力矩阵来作为矩对图像的两种形状相似特征进行索引,使用适当的形状相似性之间距离进行定义,计算并得出两幅画中图像的形状相似性之间距离,当这个距离的值足够小时,就可以认为两幅画的图像形状是相似的。傅里叶这种算法不仅对图像噪音控制具有很好的鲁棒性,而且对几何变换速度具有不变性,更加十分适合工图像形状分析检索的实际需要。因此，提出了应力不变矩和矩形轮廓的应力不变矩的算法和傅里叶公式描述中的符号相结合的计算方法。

三、图像检索技术的发展过程

目前图像检索的技术最早开始于上个世纪70年代,当时主要研究的是基于文本的检索,即使采用关键词和描述性的文本来对其进行检索,要求使用者对文本中各种特征的描述都必须具备一定的精度准确性和规范性。但是随着各种大规模的数字化图像仓库的诞生,基于文本检索的技术暴露了自身的优势。在我国逐步发展到90年代,基于图像内容的信息化图像检索技术应运而生,其设计思路主要是充分利用信息化图像自身的各种视觉特点,例如:将图像中的颜色、纹理结构、形状、空间之间的关系等信息作为内容来进行匹配、查找。它通过充分地利用了己经拥有的算法,使得所有的特征提取和匹配都完全能够由机器自动地完成,检索的过程也没必要太多的人为干涉和解释,这就克服了传统的手工标签注释方式的低效率和二义性。

四、基于形状特征的图像检索

因为许多的图像检索系统把注意力集中到了基于色彩或者是纹理学的方式上。但对于某些图像形状来说,纹理和颜色的信息不够丰富,如一些商标图像等,这时基于纹理的检索方法便无法完全满足所有的检索要求,而必须从整个图像形状入手。形状特征信息是图像的中心特征之一,图像中的形态和信息不会随着图像中物体颜色的改变而发生任何变化,它是一种稳定的特征。用各种形状的特征来区别物体很加直观,它们是现代社会中人们识别不同形态图像的主要技术特征之一。因此,通过利用各种形状特征来检索图像,可以大大提高检索的精度和效果。基于目标的形状特征的图像检索主要目的是通过检测得到目标轮廓线或分割得到目标轮廓,并针对其所在位置进行形状特征的提取或直接针对图像搜集寻找合适的向量特征。形态描述要求我们在尽量区别各个目标之间的基础上,对于目标平移、转动及尺度的变化并不敏感。目前,虽然我们已经研究提出了许多关于形状的分析技术,但是想要将它们有效运用到图像检索中仍存在的问题还有一些困难和疑惑亟待解决,如算法的工作效率和复杂程度,形状特征的提取与描述等。

五、基于形状特征的图像检索具体实行

5.1对象形状的描述

图象经过边缘的提取、分割后可以获得诸个被分割的区域.对诸个被分割的区域所提取的形状特征,是基于内容的图象检索系统的重要组成部分,所提取的形状特征对于图象的旋转、图像的平移和对图象缩放都是不敏感的.本文主要研究涉及以下几种形状的特征:

(1)基于傅立叶系数的形态和特点.圆角度,细长程,散射性.(2)基于几何形状的特征.区域的面积,区域的周长,体态比.(3)矩描述.共有七个矩常量.(4)以相似多边形为基础的结构和特点.(5)形状直方图.5.2、系统设计与实现

系统主要可以分为三个组成部分:(1)图象数据库建立模块.该建立模块首先对用户输入的各种图象信息进行了预处理,其中包括各种图象信号和噪声的清除,图象尖锐化,边缘检测(对象物的分离),边缘细化,链码追溯,对于边界信息进行了多边形逼近,然后将其提取到对象的各种形状信息,最后把用户需要提取的信息特征值直接存入到图象数据库中;(2)图像数据库维护系统模块.本次维护系统主要负责对图像数据库信息进行维护,主要内容包括图像浏览记录的修改及历史纪念信息的删除;在对图像记录进行修改时,对那些由于计算机自动提取得到的特征值我们都是不可以进行修改的,而且我们只能通过修改这些由人为确定定义的字段,如:一个有关于图象的文字说明部分.(3)图像检索查询模块.该功能首先根据需要对被检索的图像进行提取的形状和特征,然后再根据需要选择按哪些特征值对象来进行检索,设置好图像的检索所达到要求的类型和相似程度,最后与将图像信息与数据库中的其他图像进行匹配,输出查询结果.图象的匹配查询是整个图像信息数据库的主要功能和组成部分,匹配算法的好坏及其优劣直接影响到匹配查询的速度和信息库查询的质量,其根本思路就是通过判断一个经典的已知图象与一个图像数据库中的一个图象之间的距离,如其距离有点足够小,就说明我们可以确定两个已知图象之间是相似的,其结果一般应该是多个已知图象,这些所有的图象都与经典查询的图像在一个给我们认为有点相似.我们其实可以通过运用各种相似性程量测度查询函数过程方法工具来进行分析和控制计算一个查询特征图象与一个特征图像数据库中每一个特征图象的相似度和程度,相似性程度测量中的查询函数过程主要来说是研究建立在对数据特征分析和模式识别相关技术研究基础上的,涉及所遇到的主要技术问题之一就是对于一个数据输入模式如何进行特征描述和模式判别,查询的基本过程就是根据一个新的给定数据模式对一个数据输入中的模式特征进行数据匹配.这个相似度一般来说是通过0~1之间的某个个不同参数特征来进行表现计算出来的,总的相似度也由各种不同特征所测量的相似度通过函数加权运算求和得.传统数据库的准确匹配和查询技术是很简单地了解的,但对于图象型的数据库来说,查询的质量和查询的快慢还是相互矛盾的,要求查询率和准确性好,就需要尽可能多地增加一些描述图象的特征矢量的维数,随之而来就需要尽可能多地增加计算量,所以,要在不降低特征矢量的维数条件下,才能够大幅度地提高查询率,就必须通过调整和完善查询的策略.主要采用以下两种操作方法:

（1）.聚类的基本原理:分类即把一个标准图象按类划分开来成以下几类,每一类都被用户定义成作为一个分类标准图,则在用户查询一个标准图象时,首先根据要求计算出与各种分类标准图之间的物理距离,确定它们之间是否隶属于何一类,然后再与该一类的标准图象之间进行具有相似性的分类匹配.（2）过滤的原理:即通过降低维数,在进行图象匹配之前,首先将一些形状和特征相差甚远的图像从一个被称为图象匹配团队中全部清除掉,然后再将查询到的图象和匹配团队中剩下的其他图象进行对比.5.3、算法步骤

(1)通过计算被检索图像的形状和特征,并从数据库中提取图像形状和特征进行索引;

(2)对特征向量进行归一化;

(3)使用欧式距离法来计算归一化后的图像数据库中各个图像与显示者的图像之间的相似性和距离;

(4)按序输出检索结果。

5.4.边缘检测

其中边缘化的特点通常是直接影响物体图像最为主要的一个基本特点。边缘则主要是在泛指周围各个像素的颜色灰度并没具有较大阶跃性质的变化或者在屋顶上的颜色没有发生较大改变的那一个周围像素。Poggio在文中这样解释说:“或许对应着图像中物体的边界或许并没有对应着图像中物体的边界,但是边缘具有十分令人满意的性质它能大大地减少所要处理的信息但是又保留了图像中物体的形状信息”。

边缘图像检查理论是一种实现图像识别的重要理论知识基础和技术前提,直接意义地说它决定了图像识别检查结果的客观准确性。由于人体边缘图像检测尚不成熟,直接地严重影响了对图像识别的实际研究应用,一直以来都认为是图像识别相关技术应用领域的重要研究发展热点。经过多年的研究探索和应用实践,边缘式质量检测系统技术已经逐渐发展渗透至各个应用领域。在应用生物医学上,边缘提取检测主要作为适用于人体肾脏血小球的边缘提取,在应用生物医学工业和工程科学以及其他工程材料领域的边缘检测,如聚酯纤维或者其他塑料制品。而且在加工喷涂、焊接和机械装配时也被充分地吸收利用。在中国传统的民族文化工艺美术上,用于对传统纺织品和手工艺品的定制设计,服饰的定制设计和手工制作,发型的定制设计,文物收藏材料以及照片的编辑复制和收集整理,运动员的身体动作状态分析和体能评级等等。总之,边缘厚度检测已被广泛应用于各个领域。这仍然是我们必须不容忽视的一个研究发展热点。

5.5、Canny边缘检测

5.5.1 Canny指标

基于微分算子的边缘提取方法存在的一个比较麻烦的问题是如何让我们选择适当的阈值,可以通过这种方法使边缘从每一个细节中被提取出来。阈值的选择方式不同,所需要提取得到的边界信息也不相同。在两个不同的阈值下,采用相同的微分算子均可以从图像边缘提取得出一个点,但两者之间有比较大的差异。这样,在边缘提取中也就存在了对提取良好与否的评估。

针对这一重要问题,根据边缘检测的工作有效性和其定位的安全可靠性, Canny 通过研究最优的边缘检测仪器所必须要求的特点,给出了衡量边缘检测系统性能好坏的三个主要指标:

(1)良好的边缘信噪声对比,即将不是边缘点错误判定为其他边缘点的错误概率相对较高,将其他边缘点错误判定为其他边缘点的错误概率相对较低;

(2)良好的定位特性,即检测出来的边缘点应该要尽量安装在实际边缘的点为中心;

(3)对于单个边缘只能产生唯一的响应,即单个边缘能够同时产生许多个响应,其概率相对较低,并且在虚假的响应中对边界的反馈效果相应得到最佳抑制.用这样一个词来说,就是我们希望能够有效地提高人们对于景物边缘的灵敏度和噪音的同时,这种能够有效地抑制其他人们产生噪音的方式才是良好的边缘提取技术。值得我们十分庆幸的一点其实是,且个二阶线性映射算子仍然能够在有效抵抗图形噪声和对图形边缘的线性检测之间获得最佳结果折中,这个二阶线性映射算子本身其实就是高斯函数的一个二阶取值引用导出函数。高斯函数和用于原图的卷积已经初步达到了一种可以抵抗局部噪声的主要效果,而用于求导的函数,则被普遍认为已经是我们检测一个景物局部边缘的一种重要手段。

设二维高斯函数为

其中,σ为高斯函数的平滑度和分布式的参数,可以被广泛地基于用来衡量控制网络对象或者网络图像平滑的重要程度。

其中，σ是高斯函数的分布参数，可用以控制对图像的平滑程度。

最优阶跃边缘检测算子是以卷积▽G*为基础的，边缘强度为

而边缘方向为

由高斯函数的定义我们得以可知,该高斯函数都可以是无限地从头拖尾的,在实践中,一般的各种情况下都方法是将原来的有限模板尺寸截断为n,至于就达到了有限的模板尺寸。这个新的实验结果证明,当时,能够直接取得较好的边缘化学检查实验结果。

5.5.2 Canny算子的实现

下面是Canny算子的具体实现。

利用高斯函数的双向可分性,将映射▽g的两个一维滤波卷积上的模板可以分解成两个一维的滤波行列式式滤波器:

1

2

3

4

5

6

K为常数将式12分别与图像

则反应出一个在图像上点处的边缘强度,是一个在图像点处的法向力矢量(下一个交于其边缘线方向)。

根据关于canny的卷积定义,中心边缘点梯度作为一个卷积算子和它的图像(x,y)的卷积梯度是在中心边缘点和梯度相同直线方向的同一区域内两个算子梯度中的最高值。这样,就可以能够通过在各个梯度点的最大梯度值和方位上进行判断并得出每个该梯度点的最大强度方位是否为其应用领域最大强度值,从而快速确定各个梯度点的边缘点。例如,当一个矩形像素图象满足以下三个基本条件时,则被我们视作该点是一个像素图像的边界点。

(1)当像素该中一点的平均边缘运动强度方向超过了沿着像素该中一点的边缘梯度方向运动的同方向两个像素相邻点的像素中一点的平均边缘运动强度时;

(2)与该点梯度方向上相邻两点的方向差小于45度;

(3)观测领域核心中的最大边缘变化强度最大边缘阈度数值以所在该观测点位置为领域中心。

此外,如果(1)和(2)同时被边缘的顶点像素满足,那么候选选择梯度最小值相同方向上的两个非相邻顶点像素就从候选选择边缘的顶点中被直接取消,条件(3)阈值相当于由候选边缘区域选择梯度最大的阈值所在点组成的一个阈值,即图像与候选边缘的顶点之间的平均距离可以进行阈值匹配,这一消除过程就等于消除了许多虚假的边缘点。

图像边缘检测的基本步骤:

(1)对于滤波,边缘的检测主要是基于引导值进行计算,但是容易受到噪声影响。然而,该滤波器在减少噪声时还会造成边缘强度的损耗。

(2)进行了增强,加强算法把邻域的点的度有明显改变的地方突出表现。一般是靠计算梯度的幅值来实现。

(3)进行检测,但是在有些影像中梯度幅值较大的点并非边缘端。最简单的对边缘性检测就是梯度幅值阈值的判断。

(4)定位,精确确定边缘的位置。

综上所述,Canny算子的具体算法步骤如下:

(1)使用高斯滤波器对图像中的信号进行滤波,去除图像中的干扰和噪声;

(2)分析利用高斯算子的一阶方向偏移滤波函数采用微分的方法对物体图像中各点方向进行滤波,得到每一点的方向梯度和角强度和物体运动时的方向;

(3)针对梯度方向运动进行“非极大抑制”时对其梯度的反向运动及其方向如图可以正确定义为其如下如图所示

标识分别为1,2,3,4的四个区域将其属于四个局部分区之一,各个局部分区用不同的线将相邻四个像素分别排列来对其局部进行高度比较,以此来决定其每个局部的极大像素值。例如,如果我们在相邻中心像素图像获得x的梯度方向上认为属于第4区,则把获得x的极大梯度方向值与其左上和右下两个方向相邻中心像素的极大梯度的数值大小进行向量比较,看获得x的极大梯度的数值大小是否可视为极大梯度值。如果不是,就把每个矩形像素y到x的颜色灰度系数设置为0。这一抑制过程被人们称之为“非极大抑制”。

(4)对一个梯度进行两次阈值,即取一个阈值,两者之间的关系公式为。我们将梯度值小于的每个像素灰度设置为0。然后将梯度值小于的每个像素灰度平均值设定为0。去除了大部分的噪声,但同时也导致损失了有用的边缘和界面结构信息。

5.6基于轮廓的描述方法

基于局部轮廓图对形状进行描述的设计方法又大致可以细分为局部连续型(注意即局部全局式)和局部离散型(即局部结构式)两种。连续型全局轮廓图图描述的方法并没有对称为全局图的轮廓图进行任何分段式的处理,往往目的是从整个称为全局图的轮廓图中抽取并给出一个特征向量。这种属于离散式的分析方法通常首先把它的轮廓特点分解成许多不同片段,然后用传统计算机轮廓提取法找出其片段相应的轮廓特点。简单的物体形状类型描述表示符主要类型包括链码、傅立叶描述符、曲率尺度空间形状描述表示符和小波描述表示符四种基于物体轮廓的形状描述表示方式。

5.7傅立叶形状描述符

傅立叶形状轮廓描述符即它是一种被广泛应用的二维模型形状轮廓描述符,其最基本的设计思想就是用一个直接位于模型物体内部轮廓上没有边界的傅立叶变换函数来对其内部形状轮廓进行精确描述,假设一个二维模型物体的内部轮廓形状是由一系列每个坐标值函数为的物体像素所组合构造的并组成,其中,n函数为在物体轮廓上每个坐标像素的实际参考映射次数。从这些边界点的整体坐标中我们常常可以由此推导出来得出四类不同形状的坐标表达,分别为正弦曲率坐标函数、质心坐标距离、复弦长坐标矢量函数及其余弦长坐标函数。轮廓弧曲线上一个特征点的移动曲率被精确定义是因为该点在轮廓线上切向的移动角度与曲率相当于轮廓弧长之间的角度变动率。曲率密度函数我们通常可以简单地将其表示形式如下:

其中是轮廓线的切向角度,定义为:

质心点的距离函数可以直接定义成其为从一个物体的边界点到另一个给定物体的边界中心之间距离,如下所示:

复坐标函数是用复数表示的像素坐标:

这种复杂的坐标向量函数的傅立叶变换形式可以用来产生一系列关于复数的坐标系数。这些频率系数从微观频率上直接反映表示了各个类型物体的宏观形状,其中较低和高频度的物体分量值就代表了各个类型物体微观形状的具体性和宏观细节属性,高频度的物体分量值则代表了各个类型物体宏观形状的具体微观细节属性特点。形状图的描述符参数可以通过这些图形转换器的参数计算得出。为了使其能够更好保持与参数旋转的速度无关性,我们简单地仅仅保留了每个参数的旋转尺寸位置信息,而且同时省略了参数相位位置信息。缩放参数无关性通常由于在保证把缩放参数值的大小同时减少添加到c和dc中的分量(或第一个不为零的缩放参数)之后缩放才能得到确认。请特别注意图形转换中的无关性就是基于物体轮廓上的形状属性来转换表示固有的转换属性。对于具有曲率向量函数和质心之间距离的曲率函数,我们只不过需要分别考虑正交角频率的两个坐标时间轴,因为这时两个函数的傅立叶变换都必须是对称的,即有。基于点的曲率三角函数的一种形状线性描述符号也可以使其表示形式为:

其中整数代表傅立叶变换每个参数的第一至i个整数分量。类似的,由质心粒子间距所做的推测计算得到的粒子形态可以描述

符为:

对于一个复杂的坐标密度函数,正值的频率密度分量和负值的频率密度分量被同时广泛使用。由于函数dc的地理参数定义是否与某些形态条件所在处或地点的地理位置密切相关而因此得以常被忽略。因此,第一个不是零的微波频率参数分量被广泛应用于后来用于标准化其它的微波变换频率参数。复函数坐标系是函数所有的推导形式得到的坐标形态为其描述符式为其定义方程为:

为了能够保证在整个特征数据库中所有位于物体的各种特征形状和其他特征均可以具有相同的特征直径和特征长度,在第一开始进行实施傅立叶变换前后你需要把所有位于物体边界点的个别特征数目可以统一添加到m。因此算法可以被直接替换为傅立叶变换法的方式使用来大大幅度改善这个算法的执行效率。

5.8图像的相似性度量

在基于特征信息的图像内容检索图像信息检索中,特征的信息相似性和特征度量也被广泛认为已经是一个亟待解决的重大检索技术研究课题之一。只有在根据分析结果得到特点图像的两个特点后后再进行对该两个特点的图像相似性距离进行准确度量,才能有效的根据图像相似性和图像距离情况做出准确判断,实现对该特点图像的准确检索。为了更好地准确达到不同特征数据检索的提取目标,需要针对特征提取后得出的不同特征数据进行相似度的分析计算。相似性系数是以一个特殊数值的表示方式被用来显示表达两个不同物体之间的事物相似性相关程度的一种数学度量式的结果。将一个人类图像的各种特征检索观察点可看作等同是图像位于一个坐标标准空间的一个特征点,两个图像特征观察点的相似度和特征距离即相似度通常用它们之间的特征距离系数来精确表示,不同特征种类的图像特征检索数据所指的需要同时采用的相似度及其度量计算函数都可能是不一样的,相似性和度度量函公式的正确选择的恰当与否往往会对特征检索结果精确度与否产生很大的直接影响,合适点的距离才是度量计算函数的正确选择,将来也会帮助使得人类图像的各个特征向量比较更加容易契合了解的人类对于各种视觉图像感知技术方面图像内容的特征仿真,有助于基于人类视觉图像感知技术方面的人类图像特征检索分析技术的仿真性能和实际应用。

假设我们在一个图像的数据库中,用两个特征向量分别来描述和表示任意一个图像的特征,其中 x 和 y ,分别为是任意两个图像的特征向量,它们之间的接近程度我们可以通过采用距离的度量或者是统计学的方法等等来对这两个图像的相似性做出判断。常见的距离测度度量主要有欧几里德、Manhattan等。下面就我重点介绍一下欧几里德的距离。

欧几里德的线性距离函数是一种在实际上已经使用十分广泛的线性距离函数变量。它的变量计算简单,并且同时也和国际参考动力系统理论中的径向旋转不确定变量计算有密切相互联系。它的英文含义:

例如当我们发生了数据的丢失或者是当所有的特征矢量都不具备相同的权重时,那么就无法利用欧几里德距离计算方法来对其进行类似性的测度。为了避免这类情况,在实践和研究的过程中,我们可以针对欧几里德的距离进行归一化。归一化欧几里德距离的定义公式如下图所示:

6、实验结果分析

图像库中包括简单几何形状,其中星形、心形、圆形、新月形图像10幅。从分析我们不仅可以清楚地明显看出,算法对于检索图像的视觉扭转和图像形变都真的是十分具有非常强的不变性,并对于检索图像的基本主观形态和视觉特性也是非常具有鲁棒性,在就算没有一定的图像形变和扭转干扰等等条件的特殊情况下,仍然完全可以直接得出良好的视觉图像判断检索实验结果;且由于算法检索图像结果所需要排列的持续时间和排列顺序与检索个体的视觉主观性和视觉特征判断检索方式大致相同,检索结果准确率也比较高。

六、以形状为特点的图像检索系统设计

6.1检索基本思想

本文文件检索的基本工作方法主要内容是:在根据设计需要建立矩形图像库时,对不同输入的两个矩形图像子存入进行综合分析,分别选择采用经过改进后的不同可变矩和二维极坐标傅里叶描述子对两个图像的不同形状和状态特征向量进行综合描述;在将两个图像子的存入转换到二维矩形图像库同时,也将其中两个相应的不同可变矩和二维极坐标傅里叶描述子的形状特征向量分别存入二维矩形图像库的特征库.检索时,根据所有用户需要提供的图像查询数据示例检索图像,采用通过线性函数加权方法求和的一种计算结果方式,计算其与二维矩形图像库中各不同类型矩形图像的各种综合相似度,把计算结果对子集中的一个大于一定相似度的图像结果集进行返回发送给所有用户.6.2 Canny算子的程序设计

本文是用C++编程来实现图像的处理,整体流程图如图所示

未打开

N

Y

Canny算子程序流程图如图所示：

6.2.1图像特征数据库设计

基于图像形状和特征的检索系统中的一个图像特征数据库是用来存放和分析图像仓库中不同图像之间的形状和特点。在这里,将计算得到的一组图像的形状和特征(曲率、质心距离、复坐标和弦长)从 Access中存放到一个相应的特征列表中,组成了一个特征数据库。

对于图像的检索,本文特别设计了对图像入库、显示、删除和添加描述四个功能。首先,利用灰度共生矩阵提取的方法得到一个图像的形状特征,并将这些特征数据存储在 access 数据库中;然后,利用基于文本或者简单的缩略图浏览等多种方式从 access 数据库中寻找到一个示例的图像,同时,针对该一个示例图像进行基于其形状和特征的内容检索和匹配,并根据需要给出检索结果的图像。

6.3实验结果

以下是原图与处理后的图片，其中图3-4为原始图片，图3-5为Canny 算子处理后的图片。

从上述处理过的数据和图像中我们可以清楚地看出, canny 算子所处理的数据和图像不但达到了准确地提取边缘信息的主要目的,提高了抵御干扰的能力外,还使得边缘更为连续清晰。

七、基于图像形状学特点的检索方法在系统中的实现

7.1系统框架

一般的图像检索子系统主要有两个大部分共同组成:图像产生子系统和数据库检索子系统,如图4-1所示。图像产生的子系统主要是对于图像输入前进行的预处理、图像中内容的特性提取以及把这些特性和部件描述的信息纳入到数据库中。图像检索子系统主要是完成对图像的检索,其中包含了浏览和查询、图像特点的相似性匹配以及图形使用者接口等几个部分。

在本文的两个实验物理子系统中,图像特征制作与截图生成实验子系统将本文中所需要描述的流体物理学图像特征及其应用对象的局部轮廓特征进行了综合分析并并入库。在这个图像轮廓检索工具子系统中,支持一个用户通过浏览库中现有的一个图像库,手动地绘制一个图像库的轮廓及然后选择一个示例的视图。

7.2编程环境

本次测试实验操作系统的主要程序开发工具平台主要是Window XP,选择使用Visual C++6.0和Access两款软件作为主要的程序开发工具,选择Visual C++6.0和Access是因为它们都能够具有面向对象应用程序设计的基本整体化和性能设计特点以及所需要开发的所有应用程序都能够具有高度的效率地正常运行。同时又是一种微软技术性高度相互集成的企业软件开发实用工具,它为企业用户自己提供了一套功能强大的企业微软软件基础类库。且因我们已经使用了Visual C++6.0来用于开发一个基于视频内容的数字视频流和图像信息检索系统。由于芯片系统内部采用了面向对象的图像设计工作方式,这样也就使得芯片系统的许多图像功能以及处理图像模块都完全可以直接整合应用起来到其它的芯片图像处理系统中,而且需要添加新的图像算法也就不必再因为需要额外复杂地进行修改许多的图像源代码,非常好地有助于整个芯片系统在图像功能上的逐步完善和不断扩展。

7.3程序结果

首先打开一个图像库选择一个图像,然后对该图像进行特征提取。系统通过图像检索相似度的匹配,找到六个与其相似的图像,输出结果。找到六个与其相似的图像,输出结果。

八、总结

本文第一章对基于内容的图像检索方式进行了概述,进而又着重介绍了基于形态的图像检索方式。并且广泛地应用了对图像进行边缘检查的技术,对整个图像进行了检索。它主要是运用 canny 算子的方法。首先,是对边缘的检测主要以导数来计算,但是受到了噪声影响。然而,该滤波器在减少了噪声的作用下,也造成了边缘强度的损耗。其次,增强算法把对邻域的点的度有明显改变的地方以及点凸显性地展现了。一般可以靠计算机梯度的幅值来实现。再次,但是在有些图象中,梯度幅值比较大的地方并非边缘的节点。最简单的对边缘性检测就是梯度幅值阈值的判断。最后,精确地选择了边缘处的位置。

我也希望在今后的将来有更多的人去探导、研究一个边缘检测算子,为使我们能够看到更好的影片效果而努力,为了促进全人类的生活和发展而努力。图像是自古以来人类识别和交流信息的一个主要资料来源,因此,图像处理的应用领域已经涵盖到了人类日常生活、工作等诸多领域。随着现代科学技术的发展和进步,图像的应用领域也在不断拓宽。所以对于边缘性的检测也是需要继续进步。我看到将来,边缘检测技术已经广泛地应用于人们日常生活的各个领域,在当今世界人类的日常生活中,文化艺术、军事技术、生物医疗技术、工业生产和信息工程技术、航天与空间技术等等重要的领域都占有着不可或缺的一部分。同全人类的生活走向风流。

参考文献

[1] 章毓晋．图像处理和分析[M]．北京：清华大学出版社，1999

[2] 章国宝．叶桦．陈维南.基于正交小波变换的多尺度边缘提取[J]．中国图像图形报，1998（3）

[3] 陈武凡．.彩色图像边缘检测新算法−广义模糊算子法[J]．中国科学A辑，1995（2）

[4] 唐立军．段立娟．高文．基于内容的图像检索系统[J]．计算机应用研究，2001，18(7)：41-45

[5] 冯所前．文档内容图像检索[D]．北京大学信息科学技术学院智能科学系硕士学位论文，2005

[6] 谢毓湘．吴玲达．栾悉道．基于内容的图像检索技术研究[J]．计算机工程与应用，2002(1)：35-38

[7] 宋涛．刘刚．一种基于内容的文档图像检索方法．《郑州大学报》，2010年1月

[8] 郭小娟．基于内容的图像检索技术的研究[D]．西安：西北大学，2007

[9] 徐建华．图像处理与分析[M ]．北京:科学出版社，1992

[10] 贾元元．基于形状的图像数据库检索技术研究[学位论文] 2004

[11] Ang Y H．Image Retrieval Based on Multidimensional Feature Properties 1995

[12] 赖志国．余啸海．Matlab 图像处理与应用[M]．北京：国防工业出版社，2004

[13] 唐路路．张启灿．一种自适应阈值的Canny边缘检测算法/光电工程：第38卷第5期，2011．5

第三篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第四篇：算法复习材料

1.假票统计

问题描述：

由于你们团队在国际大学生诗歌大赛上取得的巨大成就，你们学校决定为你们召开一次庆功鸡尾酒会，到来的人数大大超出了预期。然而庆功会的主管却抱怨发现了有人使用假票，实际的门票是从1到N(N <= 10000)，主管怀疑有人采用复印、打印等手段伪造了门票。他把所有收上来的门票拿给你，要求你编写程序，统计所有门票中存在假票的门票数。输入：

输入文件中包含多组测试数据，每组测试数据占两行。第1行包括两个整数N和M，分别表示门票的初始总张数和参加晚会的总人数(1 <= N <= 10000,1 <= M <= 20000)。第2行为M个整数Ti，表示收到的M张门票的号码(1 <= Ti <= N)。输入文件最后一行为0 0，表示输入结束。输出：

对每组输入测试数据，输出一个整数，占一行，表示收上来的门票中共有多少张票被伪造过。输入样例： 5 5 3 3 1 2 4 6 10 6 1 3 6 6 4 2 3 1 2 0 0 输出样例： 1 4

参考代码：

//计算有几个号码被复制过 #include #include #define N 10010 #define M 20010 intcnt[N];//cnt[i],i出现的次数 int main(){ int n, m,t;while(scanf(“%d%d”, &n, &m), n + m){ memset(cnt, 0, sizeof(cnt));int i, j, res = 0;for(i = 0;i < m;i++){ scanf(“%d”, &t);cnt[t]++;} for(i = 1;i <= n;i++){ if(cnt[i] > 1){ res ++;} } printf(“%dn”, res);} return 0;}

2.看和说

问题描述：

看和说的顺序定义如下：任何一个字符串都是以数字开头，每个随后的元素都是被前一个元素重新定义。例如，字符串“122344111”可以被描述为“1个1，两个2，1个3，2个4和3个1”。因此，122344111以序列的形式表示出来就是1122132431。同理，101就表示1111111111。输入：

输入包括测试数据的组数，然后依次为相应的测试数据，每个数据占一行，不会超过1000位。输出： 对于每个测试数据，输出对应的字符串。

输入样例： 3 122344111 1111111111 12345 输出样例： 1122132431 101 1112131415 参考代码：

#include #include int main(){ char s[1001];intn,i,num,len;scanf(“%dn”,&n);while(n--){

num=1;

gets(s);

len=strlen(s);

for(i=0;i

{

if(s[i]!=s[i+1])

{

printf(“%d%c”,num,s[i]);

num=1;

}

else

num++;

}

printf(“n”);} return 0;}

3．二进制转化为十六进制

问题描述：

输入一个2进制的数，要求输出该2进制数的16进制表示。在16进制的表示中，A-F表示10-15 输入：

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000。输出：

n行，每行输出对应一个输入。输入样例： 100000 111 输出样例： 7

参考代码1：

#include #include int main(){

inti,n,dec,len;

char bin[10001];

scanf(“%d”,&n);

while(n--)

{

scanf(“%s”,bin);

len=strlen(bin);//求二进制数的长度

dec=4-len%4;

if(len%4)//处理头几位，后移dec位，使得变成4的整数倍，前面补0

{

for(i=len;i>=0;i--)

bin[i+dec]=bin[i];

for(i=0;i

bin[i]='0';

len+=dec;

}

for(i=0;i

printf(“%X”,(bin[i+3]-'0')+(bin[i+2]-'0')*2+(bin[i+1]-'0')*4+(bin[i]-'0')*8);

printf(“n”);

}

return 0;}

//参考代码2：

#include #include #define maxn 10006

int main(){ int i, j, t, tp, p;charstr[maxn], str_rev[maxn];char res[maxn/4], tmp[6], tmp_rev[6];while(scanf(“%d”, &t)!=EOF){ while(t--){ p = 0;scanf(“%s”, &str);intlen = strlen(str);for(i = lenii;strncpy(tmp, str_rev + i, k);for(j = kj-1] = tmp[j];sscanf(tmp_rev, “%d”, &tp);//printf(“k = %d tp = %d tmp = %s tmp_rev = %sn”, k, tp, tmp, tmp_rev);switch(tp){ case 0: res[p++] = '0';break;case 1: res[p++] = '1';break;case 10: res[p++] = '2';break;case 11: res[p++] = '3';break;case 100: res[p++] = '4';break;case 101: res[p++] = '5';break;case 110: res[p++] = '6';break;case 111: res[p++] = '7';break;case 1000: res[p++] = '8';break;case 1001: res[p++] = '9';break;case 1010: res[p++] = 'A';break;case 1011: res[p++] = 'B';break;case 1100: res[p++] = 'C';break;case 1101: res[p++] = 'D';break;case 1110: res[p++] = 'E';break;case 1111: res[p++] = 'F';break;default: break;} i += 4;

} for(i = p-1;i >= 0;i--)printf(“%c”, res[i]);printf(“n”);} } return 0;}

第五篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广