⑴ 目标检测算法的分步介绍（第 1 部分）
英文原文： https://www.analyticsvidhya.com/blog/2018/10/a-step-by-step-introction-to-the-basic-object-detection-algorithms-part-1/
对原文的表达有部分改动
在本文中，我们将更深入地研究可用于目标检测的各种算法。我们将从 RCNN 家族的算法开始，即 RCNN、Fast RCNN 和 Faster RCNN。在本系列即将发布的文章中，我们将介绍更高级的算法，如 YOLO、SSD 等。
下图是说明目标检测算法如何工作的一个流行示例。图像中的每个物体，从一个人到一只风筝，都以一定的精度被定位和识别。
让我们从最简单的深度学习方法开始，也是一种广泛使用的方法，用于检测图像中的目标——卷积神经网络（ CNN）。CNN 的内部工作原理如下：
我们将图像传递给网络，然后通过各种卷积和池化层处理，发送给全连接层。最后，我们以目标类别的形式获得输出。这相当简单，不是吗？对于每个输入图像，我们得到一个相应的类作为输出。我们可以使用这种技术来检测图像中的各种目标吗？让我们看看如何使用 CNN 解决一般的目标检测问题。
使用这种方法的问题在于图像中的目标可能具有不同的纵横比和空间位置。例如，在某些情况下，目标可能覆盖图像的大部分，而在某些情况下，目标可能仅覆盖图像的一小部分。目标的形状也可能不同（在现实生活中经常发生）。由于这些因素，我们将需要大量的区域，从而导致大量的计算时间。因此，为了解决这个问题并减少区域数量，我们可以使用基于区域的 CNN，它使用提案法选择区域。让我们了解这个基于区域的 CNN 可以为我们做什么。
与在大量区域上工作不同的是，RCNN 算法是在图像中选取一堆框并检查这些框中是否有任何一个包含任何目标。 RCNN 使用 selective search 从图像中提取这些框（这些框称为 regions）。
让我们首先了解什么是 selective search 以及它如何识别不同的 regions。基本上四个模式可以构成一个物体：不同的尺度、颜色、纹理和外壳。selective search 识别图像中的这些模式，并在此基础上提出各种regions。以下是selective search 工作原理的简要概述：
举个例子：
到目前为止，我们已经看到了 RCNN 如何实现目标检测。但是这种技术有其自身的局限性。由于以下步骤，训练 RCNN 模型既昂贵又缓慢：
所有这些过程结合起来使 RCNN 非常慢。对每张新图像进行预测大约需要 40-50 秒，这实质上使得模型在面对庞大的数据集时变得笨重且几乎无法构建。
好消息是——我们有另一种目标检测技术，它修复了我们在 RCNN 中看到的大部分问题。
我们还能做些什么来减少 RCNN 算法通常需要的计算时间？我们是否可以每张图像只运行一次并获取所有感兴趣的区域（包含某个目标的区域）。
RCNN 的作者 Ross Girshick 提出了这个想法，即每张图像只运行一次 CNN，然后找到一种方法在 2,000 个区域之间共享该计算。在 Fast RCNN 中，我们将输入图像提供给 CNN，后者反过来生成卷积特征图。使用这些地图，提取提议的区域。然后我们使用 RoI 池化层将所有提议的区域重塑为固定大小，以便可以将其馈入全连接网络。
让我们将其分解为简化概念的步骤：
因此，Fast RCNN 不是使用三个不同的模型（如 RCNN），而是使用单个模型从区域中提取特征，将它们分成不同的类，并同时返回识别类的边界框。
为了进一步分解，我将对每个步骤进行可视化。
这就是 Fast RCNN 如何解决 RCNN 的两个主要问题，1. 将每个图像的一个而不是 2,000 个区域传递给 ConvNet。2. 使用一个而不是三个不同的模型来提取特征、分类和生成边界框。
但即使是 Fast RCNN 也存在某些问题。它还使用 selective search 作为寻找感兴趣区域的建议方法，这是一个缓慢且耗时的过程。每张图像检测目标大约需要 2 秒，这与 RCNN 相比要好得多。但是当我们考虑大型现实生活数据集时，即使是 Fast RCNN 看起来也不那么快了。
Faster RCNN 是 Fast RCNN 的修改版本。它们之间的主要区别在于 Fast RCNN 使用 selective search 来生成感兴趣的区域，而 Faster RCNN 使用 Region Proposal Network ，又名 RPN。 RPN 将图像特征图作为输入并生成一组目标提议，每个提议的目标以分数作为输出。
Faster RCNN 方法通常遵循以下步骤：
让我简要解释一下这个区域提议网络（RPN）实际上是如何工作的。
首先，Faster RCNN 从 CNN 获取特征图并将它们传递给区域提议网络。 RPN 在这些特征图上使用一个滑动窗口，在每个窗口，它生成 k 个不同形状和大小的 Anchor 框：
Anchor 框是固定大小的边界框，它们放置在整个图像中，具有不同的形状和大小。对于每个 Anchor，RPN 预测两件事：
我们现在有不同形状和大小的边界框，它们被传递到 RoI 池化层。在 RPN 步骤之后，有可能存在没有分配给它们的类别提议。我们可以获取每个建议并对其进行裁剪，以便每个建议都包含一个目标。这就是 RoI 池化层所做的。它为每个锚点提取固定大小的特征图：
然后将这些特征图传递到具有 softmax 和线性回归层的全连接层。它最终对目标进行分类并预测已识别目标的边界框。
到目前为止，我们讨论的所有目标检测算法都使用区域来识别目标。网络不会一次性查看完整图像，而是依次关注图像的各个部分。这会造成两个并发症：
⑵ 什么是字符串多模式匹配和字符串多模式匹配算法又如何
你问两个多模式匹配有什么区别吗..
多模式就是说查找的子串不止一个.
你可以当做是单一模式匹配的叠加版,那样直接套KMP也行.
至于字典树(trie),一般用于英文单词匹配.
trie是一棵树,树上的每一条边都是一个字母,除了根节点之外的每一个节点都代表一个单词.
对于每一个节点,都有26个指针:指针A - 指针Z,分别对应26个字母
一开始时,字典树只有一个根节点,当加入一个单词时,先向根节点插入一个元素,连接根节点的一个指针,这个指针编号是单词的第一个字母,然后再在这个新的节点上增加一个元素,指针编号是第二个字母...以此类推.
检索过程很简单,自己想想就懂了,这个结构已经十分好理解了.
⑶ 那些经典算法：AC自动机
第一次看到这个名字的时候觉得非常高级，深入学习就发现，AC就是一种多模式字符串匹配算法。前面介绍的BF算法，RK算法，BM算法，KMP算法都属于单模式匹配算法，而Trie树是多模式匹配算法，多模式匹配算法就是在一个主串中查找多个模式串，举个最常用的例子，比如我们在论坛发表评论或发帖的时候，一般论坛后台会检测我们发的内容是否有敏感词，如果有敏感词要么是用***替换，要么是不让你发送，我们评论是通常是一段话，这些敏感词可能成千上万，如果用每个敏感词都在评论的内容中查找，效率会非常低，AC自动机中，主串会与所有的模式串同时匹配，这时候就可以利用AC自动机这种多模式匹配算法来完成高效的匹配，
AC自动机算法是构造一个Trie树，然后再添加额外的失配指针。这些额外的适配指针准许在查找字符串失败的时候进行回退（例如在Trie树种查找单词bef失败后，但是在Trie树种存中bea这个单词，失配指针会指向前缀be），转向某些前缀分支，免于重复匹配前缀，提高算法效率。
常见于IDS软件或病毒检测软件中病毒特征字符串，可以构建AC自动机，在这种情况下，算法的时间复杂度为输入字符串的长度和匹配数量之和。
假设现有模式字符串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 构建AC自动机如下：
说明：
1）当前指针curr指向AC自动机的根节点：curr=root。
2）从文本串中读取（下）一个字符。
3）从当前节点的所有孩子节点中寻找与该字符匹配的节点：
4）若fail == null，则说明没有任何子串为输入字符串的前缀，这时设置curr = root，执行步骤2.
若fail != null,则将curr指向 fail节点，指向步骤3。
理解起来比较复杂，找网上的一个例子，假设文本串text = “abchnijabdfk”。
查找过程如下：
说明如下：
1）按照字符串顺序依次遍历到：a-->b-->c-->h ,这时候发现文本串中下一个节点n和Trie树中下一个节点i不匹配，且h的fail指针非空，跳转到Trie树中ch位置。
注意c-->h的时候判断h不为结束节点，且c的fail指针也不是结束节点。
2）再接着遍历n-->i,发现i节点在Trie树中的下一个节点找不到j，且有fail指针，则继续遍历，
遍历到d的时候要注意，d的下一个匹配节点f是结束字符，所以得到匹配字符串：ijabdf，且d的fail节点也是d，且也是结束字符，所以得到匹配字符串abd，不过不是失败的匹配，所以curr不跳转。
先将目标字符串插入到Trie树种，然后通过广度有限遍历为每个节点的所有孩子节点找到正确的fail指针。
具体步骤如下：
1）将根节点的所有孩子节点的fail指针指向根节点，然后将根节点的所有孩子节点依次入队列。
2）若队列不为空：
2.1）出列一个字符，将出列的节点记为curr，failTo表示curr的
fail指针，即failTo = curr.fail 。
2.2) 判断curr.child[i] == failTo.child[i]是不是成立：
成立：curr.child[i].fail = failTo.child[i]
因为当前字符串的后缀和Tire树的前缀最长部分是到fail，
且子字符和failTo的下一个字符相同，则fail指针就是
failTo.child[i]。
不成立： 判断failTo是不是为null是否成立：
成立： curr.child[i].fail = root = null。
不成立： failTo = failTo.fail 继续2.2
curr.child[i]入列，再次执行步骤2）。
3）队列为空结束。
每个结点的fail指向的解决顺序是按照广度有限遍历的顺序完成的，或者说层序遍历的顺序进行，我们根据父结点的fail指针来求当前节点的fail指针。
上图为例，我们要解决y节点的fail指针问题，已经知道y节点的父节点x1的fail是指向x2的，根据fail指针的定义，我们知道红色椭圆中的字符串序列肯定相等，而且是最长的公共部分。依据y.fail的含义，如果x2的某个孩子节点和节点y表示的表示的字符相等，y的fail就指向它。
如果x2的孩子节点中不存在节点y表示的字符。由于x2.fail指向x3，根据x2.fail的含义，我们知道绿色框中的字符序列是相同的。显然如果x3的某个孩子和节点y表示字符相等，则y.fail就指向它。
如果x3的孩子节点不存在节点y表示的字符，我们重复这个步骤，直到xi的fail节点指向null，说明我们达到顶层，只要y.fail= root就可以了。
构造过程就是知道当前节点的最长公共前缀的情况下，去确定孩子节点的最长公共前缀。
下图中，每个节点都有fail虚线，指向根节点的虚线没画出，求图中c的孩子节点h的fail指向：
原图中，深蓝色的框出来的是已经确定fail指针的，求红色框中h节点的fail指针。
这时候，我们看下h的父亲节点c的fail指针指向，为ch中的c（这表示abc字符串的所有后缀bc和c和Trie树的所有前缀中最长公共部分为c），且这个c节点的孩子节点中有字符为h的字符，所以图中红色框中框出的h节点的fail指针指向 ch字符串中的h。
求红色框中i的fail指针指向，上图中，我们可以看到i的父亲节点h的指向为ch中的h，（也就是说我们的目标字符串结合中所有前缀和字符序列abch的所有后缀在Trie树中最长前缀为ch。）我们比较i节点和ch中的h的所有子节点，发现h只有一个n的子节点，所以没办法匹配，那就继续找ch中h的fail指针，图中没画出，那么就是它的fail指针就是root，然后去看root所有子节点中有没有和i相等的，发现最右边的i是和我们要找的i相等的，所以我们就把i的fail指针指向i，如后面的图。
⑷ 目标检测算法图解：一文看懂RCNN系列算法
姓名：王咫毅
学号：19021211150
【嵌牛导读】CNN如此风靡，其衍生算法也是层出不穷，各种衍生算法也可以应用于各种应用场景，各类场合。本文则是了解每个衍生算法的各个使用场景、原理及方法。
【嵌牛鼻子】RCNN 目标检测
【嵌牛提问】RCNN系列算法有何区别和联系？
【嵌牛正文】
在生活中，经常会遇到这样的一种情况，上班要出门的时候，突然找不到一件东西了，比如钥匙、手机或者手表等。这个时候一般在房间翻一遍各个角落来寻找不见的物品，最后突然一拍大脑，想到在某一个地方，在整个过程中有时候是很着急的，并且越着急越找不到，真是令人沮丧。但是，如果一个简单的计算机算法可以在几毫秒内就找到你要找的物品，你的感受如何？是不是很惊奇！这就是对象检测算法（object detection）的力量。虽然上述举的生活例子只是一个很简单的例子，但对象检测的应用范围很广，跨越多个不同的行业，从全天候监控到智能城市的实时车辆检qian测等。简而言之，物体检测是强大的深度学习算法中的一个分支。
在本文中，我们将深入探讨可以用于对象检测的各种算法。首先从属于RCNN系列算法开始，即RCNN、 Fast RCNN和 Faster RCNN。在之后的文章中，将介绍更多高级算法，如YOLO、SSD等。
1.解决对象检测任务的简单方法（使用深度学习）
下图说明了对象检测算法是如何工作。图像中的每个对象，从人到风筝都以一定的精度进行了定位和识别。
下面从最简单的深度学习方法开始，一种广泛用于检测图像中的方法——卷积神经网络（CNN）。如果读者对CNN算法有点生疏，建议 阅读此文 。
这里仅简要总结一下CNN的内部运作方式：
首先将图像作为输入传递到网络，然后通过各种卷积和池化层处理，最后以对象类别的形式获得输出。
对于每个输入图像，会得到一个相应的类别作为输出。因此可以使用这种技术来检测图像中的各种对象。
1.首先，将图像作为输入；
2.然后，将图像分成不同的区域；
3.然后，将每个区域视为单独的图像；
4.将所有这些区域传递给CNN并将它们分类为各种类别；
5.一旦将每个区域划分为相应的类后，就可以组合所有这些区域来获取具有检测到的对象的原始图像：
使用这种方法会面临的问题在于，图像中的对象可以具有不同的宽高比和空间位置。例如，在某些情况下，对象可能覆盖了大部分图像，而在其他情况下，对象可能只覆盖图像的一小部分，并且对象的形状也可能不同。
基于此，需要划分大量的区域，这会花费大量的计算时间。因此，为了解决这个问题并减少区域数量，可以使用基于区域的CNN，它使用提议方法选择区域。
2.基于区域的卷积神经网络
2.1 RCNN的思想
RCNN算法不是在大量区域上工作，而是在图像中提出了一堆方框，并检查这些方框中是否包含任何对象。RCNN 使用选择性搜索从图像中提取这些框。
下面介绍选择性搜索以及它如何识别不同的区域。基本上四个区域形成一个对象：不同的比例、颜色、纹理和形状。选择性搜索在图像中识别这些模式，并基于此提出各种区域。以下是选择性搜索如何工作的简要概述：
首先， 将图像作为输入：
然后，它生成初始子分段，以便获得多个区域：
之后，该技术组合相似区域以形成更大的区域（基于颜色相似性、纹理相似性、尺寸相似性和形状兼容性）：
最后，这些区域产生最终的对象位置（感兴趣的区域）；
下面是RCNN检测对象所遵循的步骤的简要总结：
1.首先采用预先训练的卷积神经网络；
2.重新训练该模型模型——根据需要检测的类别数量来训练网络的最后一层（迁移学习）；
3.第三步是获取每个图像的感兴趣区域。然后，对这些区域调整尺寸，以便其可以匹配CNN输入大小；
4.获取区域后，使用SVM算法对对象和背景进行分类。对于每个类，都训练一个二分类SVM；
最后，训练线性回归模型，为图像中每个识别出的对象生成更严格的边界框；
[对上述步骤进行图解分析]（ http://www.robots.ox.ac.uk/~tvg/publications/talks/Fast-rcnn-slides.pdf ）：
首先，将图像作为输入：
然后，使用一些提议方法获得感兴趣区域（ROI）（例如，选择性搜索）：
之后，对所有这些区域调整尺寸，并将每个区域传递给卷积神经网络：
然后，CNN为每个区域提取特征，SVM用于将这些区域划分为不同的类别：
最后，边界框回归（Bbox reg）用于预测每个已识别区域的边界框：
以上就是RCNN检测物体的全部流程。
2.2 RCNN的问题
从上节内容可以了解到RCNN是如何进行对象检测的，但这种技术有其自身的局限性。以下原因使得训练RCNN模型既昂贵又缓慢：
基于选择性搜索算法为每个图像提取2,000个候选区域；
使用CNN为每个图像区域提取特征；
RCNN整个物体检测过程用到三种模型：
CNN模型用于特征提取；
线性svm分类器用于识别对象的的类别；
回归模型用于收紧边界框；
这些过程相结合使得RCNN非常慢，对每个新图像进行预测需要大约40-50秒，这实际上使得模型在面对巨大的数据集时变得复杂且几乎不可能应用。
好消息是存在另一种物体检测技术，它解决了RCNN中大部分问题。
3.了解Fast RCNN
3.1Fast RCNN的思想
RCNN的提出者Ross Girshick提出了这样的想法，即每个图像只运行一次CNN，然后找到一种在2,000个区域内共享该计算的方法。在Fast RCNN中，将输入图像馈送到CNN，CNN生成卷积特征映射。使用这些特征图提取候选区域。然后，使用RoI池化层将所有建议的区域重新整形为固定大小，以便将其馈送到全连接网络中。
下面将其分解为简化概念的步骤：
1.首先将图像作为输入；
2.将图像传递给卷积神经网络，生成感兴趣的区域；
3.在所有的感兴趣的区域上应用RoI池化层，并调整区域的尺寸。然后，每个区域被传递到全连接层的网络中；
4.softmax层用于全连接网以输出类别。与softmax层一起，也并行使用线性回归层，以输出预测类的边界框坐标。
因此，Fast RCNN算法中没有使用三个不同的模型，而使用单个模型从区域中提取特征，将它们分成不同的类，并同时返回所标识类的边界框。
对上述过程进行可视化讲解：
将图像作为输入：
将图像传递给卷积神经网络t，后者相应地返回感兴趣的区域：
然后，在提取的感兴趣区域上应用RoI池层，以确保所有区域具有相同的大小：
最后，这些区域被传递到一个全连接网络，对其进行分类，并同时使用softmax和线性回归层返回边界框：
上述过程说明了Fast RCNN是如何解决RCNN的两个主要问题，即将每个图像中的1个而不是2,000个区域传递给卷积神经网络，并使用一个模型来实现提取特征、分类和生成边界框。
3.2Fast RCNN的问题
Fast RCNN也存在一定的问题，它仍然使用选择性搜索作为查找感兴趣区域的提议方法，这是一个缓慢且耗时的过程，每个图像检测对象大约需要2秒钟。
因此，又开发了另一种物体检测算法——Faster RCNN。
4.了解Faster RCNN
4.1. Faster RCNN的思想
Faster RCNN是Fast RCNN的修改版本，二者之间的主要区别在于，Fast RCNN使用选择性搜索来生成感兴趣区域，而Faster RCNN使用“区域提议网络”，即RPN。RPN将图像特征映射作为输入，并生成一组提议对象，每个对象提议都以对象分数作为输出。
以下步骤通常采用Faster RCNN方法：
1.将图像作为输入并将其传递给卷积神经网络，后者返回该图像的特征图；
2.在这些特征图上应用RPN，返回提议对象及其分数；
3.在这些提议对象上应用RoI池层，以将所有提案降低到相同的大小；
4.最后，将提议传递到全连接层，该层在其顶部具有softmax层和线性回归层，以对对象的边界框进行分类和输出；
这里简要解释一下RPN是如何运作的：
首先，Faster RCNN从CNN获取特征图并将它们传递到区域提议网络。RPN在这些特征图上使用滑动窗口，每个窗口生成不同形状和大小的k个方框（ Anchor boxe）：
方框是固定尺寸的边界箱，具有不同的形状和尺寸。对于每个方框，RPN预测两件事：
预测锚是对象的概率；
用于边界框回归器调整锚点以更好地适合物体的形状；
在有了不同形状和大小的边界框后，将其传递到RoI池层。对每个提案并对其进行裁剪，以便每个提案都包含一个对象。这就是RoI池层所做的事情，它为每个方框提取固定大小的特征图：
然后将这些特征图传递到全连接层，该层具有softmax和线性回归层，最终对对象进行分类并预测已识别对象的边界框。
4.2Faster RCNN的问题
上述讨论过的所有对象检测算法都使用区域来识别对象，且网络不会一次查看完整图像，而是按顺序关注图像的某些部分，这样会带来两个复杂性的问题：
该算法需要多次通过单个图像来提取到所有对象；
由于不是端到端的算法，不同的系统一个接一个地工作，整体系统的性能进一步取决于先前系统的表现效果。
链接： https://www.jianshu.com/p/51fc039ae7a4