⑴ 目標檢測演算法的分步介紹（第 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