由于我之前一直强调数据结构以及算法学习的重要性，所以就有一些读者经常问我，数据结构与算法应该要学习到哪个程度呢？，说实话，这个问题我不知道要怎么回答你，主要取决于你想学习到哪些程度，不过针对这个问题，我稍微总结一下我学过的算法知识点，以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的，并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构，当然，我也会整理一些看过不错的文章给大家。大家也可以留言区补充。
 
一、算法最最基础
 
1、时间复杂度
 
2、空间复杂度
 
一般最先接触的就是时间复杂度和空间复杂度的学习了，这两个概念以及如何计算，是必须学的，也是必须最先学的，主要有最大复杂度、平均复杂度等，直接通过博客搜索学习即可。
 
文章推荐：
 
算法分析神器—时间复杂度
 
二、基础数据结构
 
1、线性表
 
列表（必学）
链表（必学）
跳跃表（知道原理，应用，最后自己实现一遍）
并查集（建议结合刷题学习）
 
不用说，链表、列表必须，不过重点是链表。
 
三分钟基础数据结构：如何轻松手写链表？
 
以后有面试官问你「跳跃表」，你就把这篇文章扔给他
 
2、栈与队列
 
栈（必学）
队列（必学）
优先队列、堆（必学）
多级反馈队列（原理与应用）
 
特别是优先队列，再刷题的时候，还是经常用到的，队列与栈，是最基本的数据结构，必学。可以通过博客来学习。相关文章：
 
三分钟基础知识：什么是栈？
 
二叉堆是什么鬼？
 
【算法与数据结构】堆排序是什么鬼？
 
3、哈希表（必学）
 
碰撞解决方法：开放定址法、链地址法、再次哈希法、建立公共溢出区（必学）
布隆过滤器（原理与应用）
 
哈希表相关的，推荐通过博客来学习，推荐文章：
 
Hash冲突之开放地址法
 
4、树
 
二叉树：各种遍历（递归与非递归）（必学）
哈夫曼树与编码（原理与应用）
AVL树（必学）
B 树与 B+ 树（原理与应用）
前缀树（原理与应用）
红黑树（原理与应用）
线段树（原理与应用）
 
树相关是知识还是挺多的，建议看书，可以看《算法第四版》。相关文章：
 
高频面试题：什么是B树？为啥文件索引要用B树而不用二叉查找树？
 
【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他。
 
腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？
 
【面试被虐】游戏中的敏感词过滤是如何实现的？
 
5、数组
 
树状数组
矩阵（必学）
 
树状数组其实我也没学过，，，，
 
三、各种常见算法
 
1、十大排序算法
 
简单排序：插入排序、选择排序、冒泡排序（必学）
分治排序：快速排序、归并排序（必学，快速排序还要关注中轴的选取方式）
分配排序：桶排序、基数排序
树状排序：堆排序（必学）
其他：计数排序（必学）、希尔排序
 
对于十大算法的学习，假如你不大懂的话，那么我还是挺推荐你去看书的，因为看了书，你可能不仅仅知道这个算法怎么写，还能知道他是怎么来的。推荐书籍是《算法第四版》，这本书讲的很详细，而且配了很多图演示，还是挺好懂的。
 
推荐文章：
 
必学十大经典排序算法，看这篇就够了(附完整代码/动图/优质文章)(修订版)
 
2、图论算法
 
图的表示：邻接矩阵和邻接表
遍历算法：深度搜索和广度搜索(必学)
最短路径算法：Floyd，Dijkstra（必学）
最小生成树算法：Prim，Kruskal（必学）
实际常用算法：关键路径、拓扑排序（原理与应用）
二分图匹配：配对、匈牙利算法（原理与应用）
拓展：中心性算法、社区发现算法（原理与应用）
 
图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。
 
漫画：什么是 “图”？（修订版）
 
漫画：深度优先遍历 和 广度优先遍历
 
漫画：图的 “最短路径” 问题
 
漫画：Dijkstra 算法的优化
 
漫画：图的 “多源” 最短路径
 
 
 
更多算法的学习，欢迎关注我的公众号『帅地玩编程』
 
 
3、搜索与回溯算法
 
贪心算法（必学）
启发式搜索算法：A*寻路算法（了解）
地图着色算法、N 皇后问题、最优加工顺序
旅行商问题
 
这方便的只是都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。
 
4、动态规划
 
树形DP：01背包问题
线性DP：最长公共子序列、最长公共子串
区间DP：矩阵最大值（和以及积）
数位DP：数字游戏
状态压缩DP：旅行商
 
我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，再leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的真他妈多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。后面有时间，我也写一下我学到的套路，有点类似于我之前写的递归那样，算是一种经验。也就是我做题时的模板，不过感觉得写七八个小时，，，，，有时间就写。之前写的递归文章：为什么你学不会递归？告别递归，谈谈我的一些经验
 
5、字符匹配算法
 
正则表达式
模式匹配：KMP、Boyer-Moore
 
我写过两篇字符串匹配的文章，感觉还不错，看了这两篇文章，我觉得你就差不多懂 kmp 和 Boyer-Moore 了。
 
字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？
 
 
 
更多算法的学习，欢迎关注我的公众号『苦逼的码农』
 
 
6、流相关算法
 
最大流：最短增广路、Dinic 算法
最大流最小割：最大收益问题、方格取数问题
最小费用最大流：最小费用路、消遣
 
这方面的一些算法，我也只了解过一些，感兴趣的可以学习下。
 
总结
 
对于上面设计到的算法，我都提供了感觉还不错的文章，建议大家收藏，然后可以利用零碎的时间进行阅读，有些人可能会觉得上面的算法太多，说实话，我觉得不多，特别是对于在校生的，上面涉及到的算法可以不用很懂，但至少得了解。至于书籍的话，如果你连基本数据结构都还不懂的，建议看《数据结构与算法》相关书籍，例如《大话数据结构》、《数据结构与算法分析》。如果你有一定的基础，例如知道链表，栈，队列，那么可以看《算法第四版》，不过这本书是用 Java 实现的，不过我觉得你只要学过 C，那么可以看的懂。
 
这些算法的学习，虽然你觉得学了没有什么用，但还是那些话，它对你的影响是潜意识的，它可以给你打下很深厚的基础内功，如果你想走的更远，那么我推荐学习，标注必学的，那么我觉得，你是真的需要抽时间来学习下，标注原理与应用的，代表你可以不知道怎么用代码实现，但是必得知道它的实现原理以及应用，更多算法的学习，可以持续关注我的微信公众号勒。
 
作为一个非常注重计算机基础以及算法学习的程序员，一路自学走来，看过挺多不错的优质书籍，在这里推荐给大家，全都是自己看过滴。
 
最后，很多人问我都是怎么学习的，那我干脆就把我看过的优质书籍贡献出来：
 
计算机基础入门推荐：《程序是怎样跑起来的》、《网络是怎样连接的》、《计算机是怎样工作的》
 
进一步认识计算机网络：《计算机网络:自顶向下》、《图解http》
 
数据结构+算法入门：《数据结构与算法分析：C语言描述版》，《大话数据结构》、《阿哈算法》
 
算法进阶：《算法第四版》、《编程之美》、《编程珠玑》
 
由于我是Java技术栈的，顺便推荐基本Java的书籍，从左到由的顺序看到
 
Java：《Java核心技术卷1》、《编程思想》、《深入理解Java虚拟机》、《Java编程艺术》
 
数据库：《mysql必知必会》、《MySQL技术内幕：InnoDB存储引擎》
 
就先介绍这么多，这些都是最基础最核心滴，希望对那些不知道看什书的同学有所帮助
 
 
 
对了，我介绍的这些书籍，我顺便帮你整理好了，你可以在我的原创微信公众号『帅地玩编程』回复『书籍』获取哦
 
 
另外，帅地把公众号的精华文章整理成了一本电子书，共 630页！目录如下
 
 现在免费送给大家，在我的公众号帅地玩编程回复程序员内功修炼即可获取。
 
有收获？希望老铁们来个三连击，给更多的人看到这篇文章
 
1、老铁们，关注我的原创微信公众号「帅地玩编程」，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux），保存让你看完有所收获，不信你打我。
 
2、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。
 
作者info
 
 
 
作者：帅地，一位热爱写作的小伙
 原创公众号：『帅地玩编程』，已写了150多篇文章，专注于写 算法、计算机基础知识等提升你内功的文章，期待你的关注。
 转载说明：务必注明来源（注明：来源于公众号：苦逼的码农， 作者：帅地）
 

目录
 
一、遗传算法概述
 
二、遗传算法的特点和应用
 
三、遗传算法的基本流程及实现技术
 
3.1 遗传算法的基本流程
 
3.2 遗传算法的实现技术
 
1.编码
 
2.适应度函数
 
3.选择算子
 
4.交叉算子
 
5.变异算子
 
6.运行参数
 
四、遗传算法的基本原理
 
4.1 模式定理
 
4.2 积木块假设
 
五、遗传算法编程实例（MATLAB）
 

一、遗传算法概述
 
        遗传算法（Genetic Algorithm，GA）是进化计算的一部分，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通用，鲁棒性强，适于并行处理。
 
二、遗传算法的特点和应用
 
   遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，具有以下特点：
 
1. 以决策变量的编码作为运算对象。
 
    传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法是使用决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式，使得我们在优化计算中可借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化激励，也可以很方便地应用遗传操作算子。
 
2. 直接以适应度作为搜索信息。
 
    传统的优化算法不仅需要利用目标函数值，而且搜索过程往往受目标函数的连续性约束，有可能还需要满足“目标函数的导数必须存在”的要求以确定搜索方向。
 
    遗传算法仅使用由目标函数值变换来的适应度函数值就可确定进一步的搜索范围，无需目标函数的导数值等其他辅助信息。直接利用目标函数值或个体适应度值也可以将搜索范围集中到适应度较高部分的搜索空间中，从而提高搜索效率。
 
3. 使用多个点的搜索信息，具有隐含并行性。
 
    传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程。单个点所提供的搜索信息不多，所以搜索效率不高，还有可能陷入局部最优解而停滞；
 
    遗传算法从由很多个体组成的初始种群开始最优解的搜索过程，而不是从单个个体开始搜索。对初始群体进行的、选择、交叉、变异等运算，产生出新一代群体，其中包括了许多群体信息。这些信息可以避免搜索一些不必要的点，从而避免陷入局部最优，逐步逼近全局最优解。
 
4. 使用概率搜索而非确定性规则。
 
   传统的优化算法往往使用确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系，这种确定性可能使得搜索达不到最优店，限制了算法的应用范围。
 
   遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式进行的，增加了搜索过程的灵活性，而且能以较大概率收敛于最优解，具有较好的全局优化求解能力。但，交叉概率、变异概率等参数也会影响算法的搜索结果和搜索效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。
 
综上，由于遗传算法的整体搜索策略和优化搜索方式在计算时不依赖于梯度信息或其他辅助知识，只需要求解影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于各种领域，包括：
 
函数优化
组合优化生产调度问题
自动控制
机器人学
图像处理（图像恢复、图像边缘特征提取......)
人工生命
遗传编程
机器学习
三、遗传算法的基本流程及实现技术
 
   基本遗传算法（Simple Genetic Algorithms,SGA）只使用选择算子、交叉算子和变异算子这三种遗传算子，进化过程简单，是其他遗传算法的基础。
 
3.1 遗传算法的基本流程
 
 通过随机方式产生若干由确定长度（长度与待求解问题的精度有关）编码的初始群体；
通过适应度函数对每个个体进行评价，选择适应度值高的个体参与遗传操作，适应度低的个体被淘汰；
经遗传操作（复制、交叉、变异）的个体集合形成新一代种群，直到满足停止准则（进化代数GEN>=?）；
将后代中变现最好的个体作为遗传算法的执行结果。
                                                   
 
其中，GEN是当前代数；M是种群规模，i代表种群数量。
 
3.2 遗传算法的实现技术
 
基本遗传算法（SGA）由编码、适应度函数、遗传算子（选择、交叉、变异）及运行参数组成。
 
1.编码
 
（1）二进制编码
 
二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。
 
优点：编、解码操作简单，遗传、交叉便于实现
 
缺点：长度大
 
（2）其他编码方法
 
格雷码、浮点数编码、符号编码、多参数编码等
 
2.适应度函数
 
适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。
 
3.选择算子
 
通过选择算子模拟“优胜劣汰”，适应度高的个体被遗传到下一代的概率较大，适应度低的算子被遗传到下一代的概率较小。
 
常用的选择算法：轮盘赌选择法，即令表示群体的适应度函数值的总和，表示群体中第i个染色体的适应度值，则它产生后代的能力刚好为其适应度值所占的份额
 
4.交叉算子
 
交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体；
交叉运算是遗传算法区别于其他进化算法的重要特征，是产生新个体的主要方法。
在交叉之前需要将群体中的个体进行配对，一般采取随机配对原则。
 
常用的交叉方式：
 
单点交叉
双点交叉（多点交叉，交叉点数越多，个体的结构被破坏的可能性越大，一般不采用多点交叉的方式）
均匀交叉
算术交叉
5.变异算子
 
遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。
 
就遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但也是必不可少的一个运算步骤，它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索，从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。
 
6.运行参数
 
编码长度。编码长度取决于问题解的精度，精度越高，编码越长；
种群规模。规模小，收敛快但降低了种群的多样性，；
交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构，使搜索具有太大随机性；较小的交叉概率发现新个体的速度太慢，一般取值为
变异概率。变异概率太小，则变异操作产生新个体的能力和抑制早熟现象的能力会较差；变异概率过高随机性过大，一般建议取值范围为0.005～0.01
终止进化代数。算法运行结束的条件之一，一般取100～1000
四、遗传算法的基本原理
 
4.1 模式定理
 
定义1:模式H是由{0,1,*}中的元素组成的一个编码串，其中“*”表示通配符，既能被当作0，也能被当作1。e.g. H=10**1
 
定义2:模式的阶，是指模式中所含有0，1的数量，记作O(H)  e.g. O(11*00**)=4
 
定义3:模式的矩，即模式的长度，是指模式中从左到右第一个非*位和最后一个非*位之间的距离，记作
 
          e.g. 
 
定义4:模式的适应度值，是群体中所包含的全部个体的适应度值的平均值。
 
定义5:在选择、交叉、变异遗传算子的作用下，低阶、长度短、超过群体平均适应值的模式的生存数量，将随迭代次数以指数规律增长。
 
模式定理不仅说明基因块的样本呈指数增长，也说明用遗传算法寻求最优样本的可能性，但它并未指出遗传算法一定能够寻求到最优解，积木块假设说明了遗传算法的寻找最优解的能力。
 
4.2 积木块假设
 
具有低阶、定义长度短，且适应度值高于群体平均适应度值的模式称为基因块或积木块。
 
积木块假设：个体的基因块通过选择、交叉、变异等遗传算子的作用，能够相互拼接在一起，形成适应度更高的个体编码串。
 
积木块假设说明了用遗传算法求解各类问题的基本思想，即通过积木块直接相互拼接在一起能够产生更好的解。
 
五、遗传算法编程实例（MATLAB）
 
https://github.com/strawberry-magic-pocket/Genetic-Algorithm.git
 
 

为什么会有这么多基于群智能的算法，蚁群、粒子群、鱼群、烟花、炮竹、猪群、牛群、马群、羊群、猴群、鸡群。。。算法。？？？？？？
 黑人问号.jpg
 
 蝙蝠算法( BA) 是 Yang 教授于 2010 年基于群体智能提出的启发式搜索算法,是一种搜索全局最优解的有效方法。该算法是一种基于迭代的优化技术,初始化为一组随机解,然后 通过迭代搜寻最优解,且在最优解周围通过随机飞行产生局部新解,加强了局部搜索。与其他算法相比,BA 在准确性和有效性方面远优于其他算法,且没有许多参数要进行调整。
 
BA算法是模拟自然界中蝙蝠利用一种声呐来探测猎物、避免障碍物的随机搜索算法即模拟蝙蝠利用超声波对障碍物或猎物进行最基本的探测、定位能力并将其和优化目标功能相联系。BA算法的仿生原理将种群数量为的蝙蝠个体映射为D维问题空间中的NP个可行解,将优化过程和搜索模拟成种群蝙蝠个体移动过程和搜寻猎物利用求解问题的适应度函数值来衡量蝙蝠所处位置的优劣，将个体的优胜劣汰过程类比为优化和搜索过程中用好的可行解替代较差可行解的迭代过程。在蝙蝠搜索算法中,为了模拟蝙蝠探测猎物、避免障碍物,需假设如下三个近似的或理想化的规则：
 
1）所有蝙蝠利用回声定位的方法感知距离,并且它们采用一种巧妙的方式来区别猎物和背景障碍物之间的不同。
 2）蝙蝠在位置xi以速度vi随机飞行,以固定的频率fmin、可变的波长λ和音量A0来搜索猎物。蝙蝠根据自身与目标的邻近程度来自动调整发射的脉冲波长（或频率）和调整脉冲发射率r属于[0,1]
 3）虽然音量的变化方式有多种但在蝙蝠算法中, 假定音量A是从一个最大值A0(整数)变化到固定最小值Amin
 伪代码：
 
 Maltab实现：
 主函数代码：
 
function [bestMin, bestID] = MYBA()
%A new modification approach on bat algorithm for solving optimization problems
 
%omegaxyz.com 2019年2月12日
 
clc
%% BA参数设置
 
t = 1; 
maxT = 500; %最大迭代次数
dim = 30; %问题的维度
sizep = 50; %种群大小
xmin = -100;
xmax = 100; %位置向量的范围
 
A = 0.6.*ones(sizep,1);    % 响度 (不变或者减小)
r = zeros(sizep,1);      % 脉冲率 (不变或增加))
r0 = 0.7;
Af = 0.9;
Rf = 0.9;
Qmin = 0;         % 最小频率
Qmax = 1;         % 最大频率
 
%% 初始化
 
Lb = xmin*ones(1,dim);
Ub = xmax*ones(1,dim);
pop = Lb+(Ub-Lb).*rand(sizep,dim); %种群初始化
popv = zeros(sizep,dim);   % 速度
Q = zeros(sizep,1);   % 频率
 
pfitness = zeros(dim,1);
for i = 1:sizep
    pfitness(i) = evaluate(pop(i,:)); %评价
end
[bestMin, bestID]=min(pfitness);
bestS = pop(bestID, :);
bestArchive = zeros(maxT,1);
%% 具体迭代过程
 
while t <= maxT
    for i = 1:sizep
        Q(i)=Qmin+(Qmax-Qmin)*rand();
        popv(i,:)=popv(i,:)+(pop(i,:)-bestS)*Q(i);
        Stemp = pop(i,:)+popv(i,:);
        % 脉冲率
         if rand>r(i)
             Stemp=bestS-1+2*rand(1,dim);
         end
         fitTemp = evaluate(Stemp);
         if (fitTemp<=pfitness(i))&&(rand()<A(i))
            pop(i,:) = Stemp;
            pfitness(i) = fitTemp;
            A(i) = Af*A(i);
            r(i) = r0*(1-exp(-Rf*t));
         end
         if fitTemp <= bestMin
            bestMin = fitTemp;
         	bestS = Stemp;
         end
    end
    bestArchive(t) = bestMin;
    fprintf('GEN: %d  min: %.4f\n', t, bestMin);
    t = t +1;
end
 
 
end
 
评价函数：
 可以自己改
 
function z=evaluate(u)
    %Axis parallel hyperellipoid
    dim=size(u,2);
    z=sum((2:dim).*((u(2:dim)).^2));
end
 
更多内容访问 omegaxyz.com
 网站所有代码采用Apache 2.0授权
 网站文章采用知识共享许可协议BY-NC-SA4.0授权
 © 2019 • OmegaXYZ-版权所有 转载请注明出处

图像特征包括颜色特征、纹理特征、形状特征以及局部特征点等。
 
局部特点具有很好的稳定性，不容易受外界环境的干扰。
 
1. 局部特征点
 
图像特征提取是图像分析与图像识别的前提，它是将高维的图像数据进行简化表达最有效的方式，从一幅图像的的数据矩阵中，我们看不出任何信息，所以我们必须根据这些数据提取出图像中的关键信息，一些基本元件以及它们的关系。
 
局部特征点是图像特征的局部表达，它只能反正图像上具有的局部特殊性，所以它只适合于对图像进行匹配，检索等应用。对于图像理解则不太适合。而后者更关心一些全局特征，如颜色分布，纹理特征，主要物体的形状等。全局特征容易受到环境的干扰，光照，旋转，噪声等不利因素都会影响全局特征。相比而言，局部特征点，往往对应着图像中的一些线条交叉，明暗变化的结构中，受到的干扰也少。
 
而斑点与角点是两类局部特征点。斑点通常是指与周围有着颜色和灰度差别的区域，如草原上的一棵树或一栋房子。它是一个区域，所以它比角点的噪能力要强，稳定性要好。而角点则是图像中一边物体的拐角或者线条之间的交叉部分。
 
2. 斑点检测原理与举例
 
2.1 LoG与DoH
 
斑点检测的方法主要包括利用高斯拉普拉斯算子检测的方法（LOG）,以及利用像素点Hessian矩阵（二阶微分）及其行列式值的方法（DOH）。
 
LoG的方法已经在斑点检测这入篇文章里作了详细的描述。因为二维高斯函数的拉普拉斯核很像一个斑点，所以可以利用卷积来求出图像中的斑点状的结构。
 
DoH方法就是利用图像点二阶微分Hessian矩阵：
 
 
 
 
 
以及它的行列式的值DoH(Determinant of Hessian):
 
 
 
 
 
Hessian矩阵行列式的值，同样也反映了图像局部的结构信息。与LoG相比，DoH对图像中的细长结构的斑点有较好的抑制作用。
 
无论是LoG还是DoH，它们对图像中的斑点进行检测，其步骤都可以分为以下两步：
 
1）使用不同的生成或模板，并对图像进行卷积运算；
 
2）在图像的位置空间与尺度空间中搜索LoG与DoH响应的峰值。
 
2.2 SIFT
 
详细的算法描述参考：SIFT定位算法关键步骤的说明
 
2004年，Lowe提高了高效的尺度不变特征变换算法（SIFT）,利用原始图像与高斯核的卷积来建立尺度空间，并在高斯差分空间金字塔上提取出尺度不变性的特征点。该算法具有一定的仿射不变性，视角不变性，旋转不变性和光照不变性，所以在图像特征提高方面得到了最广泛的应用。
 
该算法大概可以归纳为三步：1）高斯差分金字塔的构建；2）特征点的搜索；3）特征描述。
 
在第一步中，它用组与层的结构构建了一个具有线性关系的金字塔结构，让我们可以在连续的高斯核尺度上查找特征点。它比LoG高明的地方在于，它用一阶高斯差分来近似高斯的拉普拉斯核，大大减少了运算量。
 
在第二步的特征点搜索中，主要的关键步骤是极值点的插值，因为在离散的空间中，局部极值点可能并不是真正意义上的极值点，真正的极植点可以落在了离散点的缝隙中。所以要对这些缝隙位置进行插值，然后再求极值点的坐标位置。
 
第二步中另一关键环节是删除边缘效应的点，因为只忽略那些DoG响应不够的点是不够的，DoG的值会受到边缘的影响，那些边缘上的点，虽然不是斑点，但是它的DoG响应也很强。所以我们要把这部分点删除。我们利用横跨边缘的地方，在沿边缘方向与垂直边缘方向表现出极大与极小的主曲率这一特性。所以通过计算特征点处主曲率的比值即可以区分其是否在边缘上。这一点在理解上可以参见Harris角点的求法。
 
最后一步，即为特征点的特征描述。特征点的方向的求法是需要对特征点邻域内的点的梯度方向进行直方图统计，选取直方图中比重最大的方向为特征点的主方向，还可以选择一个辅方向。在计算特征矢量时，需要对局部图像进行沿主方向旋转，然后再进邻域内的梯度直方图统计（4x4x8）。
 
2.3 SURF
 
详细的算法描述参考：1. SURF算法与源码分析、上  2. SURF算法与源码分析、下
 
2006年，Bay和Ess等人基于SIFT算法的思路，提出了加速鲁棒特征（SURF）,该算法主要针对于SIFT算法速度太慢，计算量大的缺点，使用了近似Harr小波方法来提取特征点，这种方法就是基于Hessian行列式（DoH）的斑点特征检测方法。通过在不同的尺度上利用积分图像可以有效地计算出近似Harr小波值，简化了二阶微分模板的构建，搞高了尺度空间的特征检测的效率。
 
SURF算法在积分图像上使用了盒子滤波器对二阶微分模板进行了简化，从而构建了Hessian矩阵元素值，进而缩短了特征提取的时间，提高了效率。其中SURF算法在每个尺度上对每个像素点进行检测，其近似构建的Hessian矩阵及其行列式的值分另为：
 
 
 
 
 
 
 
 
 
其中和为利用盒子滤波器获得的近似卷积值。如果大于设置的门限值，则判定该像素点为关键字。然后与SIFT算法近似，在以关键点为中心的像素邻域内进行非极大值抑制，最后通过对斑点特征进行插值运算，完成了SURF特征点的精确定位。
 
而SURF特征点的描述，则也是充分利用了积分图，用两个方向上的Harr小波模板来计算梯度，然后用一个扇形对邻域内点的梯度方向进行统计，求得特征点的主方向。
 
3. 角点检测的原理与举例
 
角点检测的方法也是极多的，其中具有代表性的算法是Harris算法与FAST算法。
 
这两个算法我都有专门写过博文来描述其算法原理。Harris角点和FAST特征点检测。
 
3.1 Harris角点特征提取
 
Harris角点检测是一种基于图像灰度的一阶导数矩阵检测方法。检测器的主要思想是局部自相似性/自相关性，即在某个局部窗口内图像块与在各个方向微小移动后的窗口内图像块的相似性。
 
在像素点的邻域内，导数矩阵描述了数据信号的变化情况。假设在像素点邻域内任意方向上移动块区域，若强度发生了剧烈变化，则变化处的像素点为角点。定义的Harris矩阵为：
 
 
 
 
 
其中，和分别为点在和方向上的强度信息的一阶导数，为对应位置的权重。通过计算Harris矩阵的角点响应值D来判断是否为角点。其计算公式为：
 
 
 
 
 
其中，det和trace为行列式和迹的操作符，是取值为0.04~0.06的常数。当角点响应值大于设置的门限，且为该点邻域内的局部最大值时，则把该点当作角点。
 
3.2 FAST角点特征提取
 
基于加速分割测试的FAST算法可以快速地提取出角点特征。该算法判断一个候选点是否为角点，依据的是在一个像素点为圆心，半径为3个像素的离散化Bresenllam圆周上，在给定阈值的条件下，如果在圆周上有个连续的像素灰度值大于或小于。
 
针对于上面的定义，我们可以用快速的方法来完成检测，而不用把圆周上的所有点都比较一遍。首先比较上下左右四个点的像素值关系，至少要有3个点的像素灰度值大于或小于，则为候选点，然后再进一步进行完整的判断。
 
为了加快算法的检测速度，可以使用机器学习ID3贪心算法来构建决策树。这里需要说明的是，在2010年Elmar和Gregory等人提出了自适应通用加速分割检测（AGAST）算法，通过把FAST算法中ID3决策树改造为二叉树，并能够根据当前处理的图像信息动态且高效地分配决策树，提高了算法的运算速度。
 
4. 二进制字符串特征描述子
 
可以注意到在两种角点检测算法里，我们并没有像SIFT或SURF那样提到特征点的描述问题。事实上，特征点一旦检测出来，无论是斑点还是角点描述方法都是一样的，可以选用你认为最有效的特征描述子。
 
特征描述是实现图像匹配与图像搜索必不可少的步骤。到目前为止，人们研究了各种各样的特征描述子，比较有代表性的就是浮点型特征描述子和二进帽字符串特征描述子。
 
像SIFT与SURF算法里的，用梯度统计直方图来描述的描述子都属于浮点型特征描述子。但它们计算起来，算法复杂，效率较低，所以后来就出现了许多新型的特征描述算法，如BRIEF。后来很多二进制串描述子ORB，BRISK，FREAK等都是在它上面的基础上的改进。
 
4.1 BRIEF算法
 
BRJEF算法的主要思想是：在特征点周围邻域内选取若干个像素点对，通过对这些点对的灰度值比较，将比较的结果组合成一个二进制串字符串用来描述特征点。最后，使用汉明距离来计算在特征描述子是否匹配。
 
BRIEF算法的详细描述可以参考：BRIEF特征描述子
 
4.2 BRISK算法
 
BRISK算法在特征点检测部分没有选用FAST特征点检测，而是选用了稳定性更强的AGAST算法。在特征描述子的构建中，BRISK算法通过利用简单的像素灰度值比较，进而得到一个级联的二进制比特串来描述每个特征点，这一点上原理与BRIEF是一致的。BRISK算法里采用了邻域采样模式，即以特征点为圆心，构建多个不同半径的离散化Bresenham同心圆，然后再每一个同心圆上获得具有相同间距的N个采样点。
 
 
由于这种邻域采样模式在采样时会产生图像灰度混叠的影响，所以BRISK算法首先对图像进行了高斯平滑图像。并且使用的高斯函数标准差与各自同心圆上点间距成正比。
 
假设在个采样点中任意选取一对采样点，其平滑后的灰度值分别为和，则两点间的局部梯度为：
 
 
 
 
 
假设把所有采样点对构成的集合记为，则
 
 
 
 
 
那么短距离采样点对构成的集合S以及长距离采样点构成的集合L分别为：
 
 
 
 
 
 
 
 
 
其中，通常设置距离阈值为，其中为特征点的尺度。
 
由于长距离采样点对含有更多的特征点角度信息，且局部梯度相互抵消，所以可以在集合L中计算出特征点的特征模式方向为：
 
 
 
 
 
然后将采样模式围绕特征点旋转角度，进而特征描述子具有了旋转不变性。
 
最后，在旋转后的短距离采样点集合S内，对所有的特征点对行像素灰度值比较，最终形成512比特的二进制字符串描述子。
 
4.3 ORB算法
 
ORB算法使用FAST进行特征点检测，然后用BREIF进行特征点的特征描述，但是我们知道BRIEF并没有特征点方向的概念，所以ORB在BRIEF基础上引入了方向的计算方法，并在点对的挑选上使用贪婪搜索算法，挑出了一些区分性强的点对用来描述二进制串。ORB算法的详细描述可以参考：ORB特征点检测。
 
4.4 FREAK算法
 
Fast Retina KeyPoint，即快速视网膜关键点。
 
根据视网膜原理进行点对采样，中间密集一些，离中心越远越稀疏。并且由粗到精构建描述子，穷举贪婪搜索找相关性小的。42个感受野，一千对点的组合，找前512个即可。这512个分成4组，前128对相关性更小，可以代表粗的信息，后面越来越精。匹配的时候可以先看前16bytes，即代表精信息的部分，如果距离小于某个阈值，再继续，否则就不用往下看了。
 
5. 应用之图像匹配
 
图像匹配的研究目标是精确判断两幅图像之间的相似性。图像之间的相似性的定义又随着不同的应用需求而改变。例如，在物体检索系统中（找出含有亚伯拉罕·林肯的脸的图像），我们认为同一物体的不同图像是相近的。而在物体类别检索系统中（找出含有人脸的图像），我们则认为相同类的物体之间是相近的。
 
这里局部特征点的应用主要表现在第一种相似性上，也就是说我们需要设计某种图像匹配算法来判断两幅图像是否是对同一物体或场景所成的图像。理想的图像匹配算法应该认为两幅同一物体的图像之间相似度很高，而两幅不同物体的图像之间相似度很低，如下图所示。
 
 
由于成像时光照，环境，角度的不一致，我们获取的同一物体的图像是存在差异的，如同上图中的两辆小车的图像一样，角度不同，成像就不同。我们直接利用图像进行比较是无法进行判断小车是否为同一类的。必须进行特征点的提取，再对特征点进行匹配。
 
图像会存在哪些变换呢？一般来说包括了光照变化与几何变化，光照变化表现是图像上是全局或局部颜色的变化，而几何变化种类就比较多了，可以是平移、旋转、尺度、仿射、投影变换等等。所以我们在研究局部特征点时才要求特征点对这些变化具有稳定性，同时要有很强的独特性，可以让图像与其他类的图像区分性强，即类内距离小而类间距离大。
 
6. 参考文献
 
[1] 基于角点的图像特征提取与匹配算法研究，薛金龙，2014.
 
[2] 基于局部特征的图像匹配与识别，宫明明，2014.
 
[3] 基于视觉信息的图像特征提取算法研究，戴金波，2014.
 
[4] 图像局部不变性特征与描述，王永明，王贵锦编著。