?

在基于深度學(xué)習(xí)的目標(biāo)檢測(cè)算法的綜述?那一節(jié)中我們提到基于區(qū)域提名的目標(biāo)檢測(cè)中廣泛使用的選擇性搜索算法。并且該算法后來(lái)被應(yīng)用到了R-CNN,SPP-Net,Fast R-CNN中。因此我認(rèn)為還是有研究的必要。

傳統(tǒng)的目標(biāo)檢測(cè)算法大多數(shù)以圖像識(shí)別為基礎(chǔ)。一般可以在圖片上使用窮舉法或者滑動(dòng)窗口選出所有物體可能出現(xiàn)的區(qū)域框，對(duì)這些區(qū)域框提取特征并進(jìn)行使用圖像識(shí)別分類方法，得到所有分類成功的區(qū)域后，通過(guò)非極大值抑制輸出結(jié)果。

在圖片上使用窮舉法或者滑動(dòng)窗口選出所有物體可能出現(xiàn)的區(qū)域框，就是在原始圖片上進(jìn)行不同尺度不同大小的滑窗，獲取每個(gè)可能的位置。而這樣做的缺點(diǎn)也顯而易見(jiàn)，復(fù)雜度太高，產(chǎn)生了很多的冗余候選區(qū)域，而且由于不可能每個(gè)尺度都兼顧到，因此得到的目標(biāo)位置也不可能那么準(zhǔn)，在現(xiàn)實(shí)當(dāng)中不可行。而選擇性搜索有效地去除冗余候選區(qū)域，使得計(jì)算量大大的減小。

我們先來(lái)看一組圖片，由于我們事先不知道需要檢測(cè)哪個(gè)類別，因此第一張圖的桌子、瓶子、餐具都是一個(gè)個(gè)候選目標(biāo)，而餐具包含在桌子這個(gè)目標(biāo)內(nèi)，勺子又包含在碗內(nèi)。這張圖展示了目標(biāo)檢測(cè)的層級(jí)關(guān)系以及尺度關(guān)系，那我們?nèi)绾稳カ@得這些可能目標(biāo)的位置呢。我們能不能通過(guò)視覺(jué)特征去減少候選框的數(shù)量并提高精確度呢。

可用的特征有很多，到底什么特征是有用的呢？我們看第二副圖片的兩只貓咪，他們的紋理是一樣的，因此紋理特征肯定不行了。而如果通過(guò)顏色則能很好區(qū)分。但是第三幅圖變色龍可就不行了，這時(shí)候邊緣特征、紋理特征又顯得比較有用。而在最后一幅圖中，我們很容易把車和輪胎看作是一個(gè)整體，但是其實(shí)這兩者的特征差距真的很明顯啊，無(wú)論是顏色還是紋理或是邊緣都差的太遠(yuǎn)了。而這這是幾種情況，自然圖像那么多，我們通過(guò)什么特征去區(qū)分？應(yīng)該區(qū)分到什么尺度？

selective search的策略是，既然是不知道尺度是怎樣的，那我們就盡可能遍歷所有的尺度好了，但是不同于暴力窮舉，我們可以先利用基于圖的圖像分割的方法得到小尺度的區(qū)域，然后一次次合并得到大的尺寸就好了，這樣也符合人類的視覺(jué)認(rèn)知。既然特征很多，那就把我們知道的特征都用上，但是同時(shí)也要照顧下計(jì)算復(fù)雜度，不然和窮舉法也沒(méi)啥區(qū)別了。最后還要做的是能夠?qū)γ總€(gè)區(qū)域進(jìn)行排序，這樣你想要多少個(gè)候選我就產(chǎn)生多少個(gè)，不然總是產(chǎn)生那么多你也用不完不是嗎？

在深入介紹Selective Search之前，先說(shuō)說(shuō)其需要考慮的幾個(gè)問(wèn)題：

• ?適應(yīng)不同尺度（Capture All Scales）：窮舉搜索（Exhaustive Selective）通過(guò)改變窗口大小來(lái)適應(yīng)物體的不同尺度，選擇搜索（Selective Search）同樣無(wú)法避免這個(gè)問(wèn)題。算法采用了圖像分割（Image Segmentation）以及使用一種層次算法（Hierarchical Algorithm）有效地解決了這個(gè)問(wèn)題。
• 多樣化（Diversification）：單一的策略無(wú)法應(yīng)對(duì)多種類別的圖像。使用顏色（color）、紋理（texture）、大小（size）等多種策略對(duì)分割好的區(qū)域（region）進(jìn)行合并。
• 速度快（Fast to Compute）：算法，就像功夫一樣，唯快不破！

回到頂部

一 選擇性搜索的具體算法（區(qū)域合并算法）

輸入: 一張圖片 輸出：候選的目標(biāo)位置集合L算法： 1: 利用切分方法得到候選的區(qū)域集合R = {r1,r2,…,rn} 2: 初始化相似集合S = ? 3: foreach 遍歷鄰居區(qū)域?qū)?ri,rj) do 4: 計(jì)算相似度s(ri,rj) 5: S = S ∪ s(ri,rj) 6: while S not=? do 7: 從S中得到最大的相似度s(ri,rj)=max(S) 8: 合并對(duì)應(yīng)的區(qū)域rt = ri ∪ rj 9: 移除ri對(duì)應(yīng)的所有相似度：S = S\s(ri,r*) 10: 移除rj對(duì)應(yīng)的所有相似度：S = S\s(r*,rj) 11: 計(jì)算rt對(duì)應(yīng)的相似度集合St 12: S = S ∪ St 13: R = R ∪ rt 14: L = R中所有區(qū)域?qū)?yīng)的邊框

首先通過(guò)基于圖的圖像分割方法初始化原始區(qū)域，就是將圖像分割成很多很多的小塊。然后我們使用貪心策略，計(jì)算每?jī)蓚€(gè)相鄰的區(qū)域的相似度，然后每次合并最相似的兩塊，直到最終只剩下一塊完整的圖片。然后這其中每次產(chǎn)生的圖像塊包括合并的圖像塊我們都保存下來(lái)，這樣就得到圖像的分層表示了呢。那我們?nèi)绾斡?jì)算兩個(gè)圖像塊的相似度呢？

?

二 保持多樣性的策略

區(qū)域合并采用了多樣性的策略，如果簡(jiǎn)單采用一種策略很容易錯(cuò)誤合并不相似的區(qū)域，比如只考慮紋理時(shí)，不同顏色的區(qū)域很容易被誤合并。選擇性搜索采用三種多樣性策略來(lái)增加候選區(qū)域以保證召回：

• 多種顏色空間，考慮RGB、灰度、HSV及其變種等
• 多種相似度度量標(biāo)準(zhǔn)，既考慮顏色相似度，又考慮紋理、大小、重疊情況等。
• 通過(guò)改變閾值初始化原始區(qū)域，閾值越大，分割的區(qū)域越少。

1、顏色空間變換

通過(guò)色彩空間變換，將原始色彩空間轉(zhuǎn)換到多達(dá)八中的色彩空間。作者采用了8中不同的顏色方式，主要是為了考慮場(chǎng)景以及光照條件等。這個(gè)策略主要應(yīng)用于中圖像分割算法中原始區(qū)域的生成(兩個(gè)像素點(diǎn)的相似度計(jì)算時(shí)，計(jì)算不同顏色空間下的兩點(diǎn)距離)。主要使用的顏色空間有：（1）RGB，（2）灰度I，（3）Lab，（4）rgI（歸一化的rg通道加上灰度），（5）HSV，（6）rgb（歸一化的RGB），（7）C，（8）H（HSV的H通道）

?

2、區(qū)域相似度計(jì)算

我們?cè)谟?jì)算多種相似度的時(shí)候，都是把單一相似度的值歸一化到[0,1]之間，1表示兩個(gè)區(qū)域之間相似度最大。

• 顏色相似度

使用L1-norm歸一化獲取圖像每個(gè)顏色通道的25 bins的直方圖，這樣每個(gè)區(qū)域都可以得到一個(gè)75維的向量，區(qū)域之間顏色相似度通過(guò)下面的公式計(jì)算：

上面這個(gè)公式可能你第一眼看過(guò)去看不懂，那咱們打個(gè)比方，由于是歸一化后值，每一個(gè)顏色通道的直方圖累加和為1.0，三個(gè)通道的累加和就為3.0，如果區(qū)域ci和區(qū)域cj直方圖完全一樣，則此時(shí)顏色相似度最大為3.0，如果不一樣，由于累加取兩個(gè)區(qū)域bin的最小值進(jìn)行累加，當(dāng)直方圖差距越大，累加的和就會(huì)越小，即顏色相似度越小。

在區(qū)域合并過(guò)程中使用需要對(duì)新的區(qū)域進(jìn)行計(jì)算其直方圖，計(jì)算方法：

• 紋理相似度

這里的紋理采用SIFT-Like特征。具體做法是對(duì)每個(gè)顏色通道的8個(gè)不同方向計(jì)算方差σ=1的高斯微分（Gaussian Derivative），使用L1-norm歸一化獲取圖像每個(gè)顏色通道的每個(gè)方向的10 bins的直方圖，這樣就可以獲取到一個(gè)240（10x8x3）維的向量，區(qū)域之間紋理相似度計(jì)算方式和顏色相似度計(jì)算方式類似，合并之后新區(qū)域的紋理特征計(jì)算方式和顏色特征計(jì)算相同：

?

• 優(yōu)先合并小的區(qū)域

如果僅僅是通過(guò)顏色和紋理特征合并的話，很容易使得合并后的區(qū)域不斷吞并周圍的區(qū)域，后果就是多尺度只應(yīng)用在了那個(gè)局部，而不是全局的多尺度。因此我們給小的區(qū)域更多的權(quán)重，這樣保證在圖像每個(gè)位置都是多尺度的在合并。

上面的公式表示，兩個(gè)區(qū)域越小，其相似度越大，越接近1。

• 區(qū)域的合適度距離

如果區(qū)域ri包含在rj內(nèi)，我們首先應(yīng)該合并，另一方面，如果ri很難與rj相接，他們之間會(huì)形成斷崖，不應(yīng)該合并在一塊。這里定義區(qū)域的合適度距離主要是為了衡量?jī)蓚€(gè)區(qū)域是否更加“吻合”，其指標(biāo)是合并后的區(qū)域的Bounding Box（能夠框住區(qū)域的最小矩形BBij）越小，其吻合度越高，即相似度越接近1。其計(jì)算方式：

• 合并上面四種相似度

其中

?

三 給區(qū)域打分

通過(guò)上述的步驟我們能夠得到很多很多的區(qū)域，但是顯然不是每個(gè)區(qū)域作為目標(biāo)的可能性都是相同的，因此我們需要衡量這個(gè)可能性，這樣就可以根據(jù)我們的需要篩選區(qū)域建議個(gè)數(shù)啦。

這篇文章做法是，給予最先合并的圖片塊較大的權(quán)重，比如最后一塊完整圖像權(quán)重為1，倒數(shù)第二次合并的區(qū)域權(quán)重為2以此類推。但是當(dāng)我們策略很多，多樣性很多的時(shí)候呢，這個(gè)權(quán)重就會(huì)有太多的重合了，排序不好搞啊。文章做法是給他們乘以一個(gè)隨機(jī)數(shù)，畢竟3分看運(yùn)氣嘛，然后對(duì)于相同的區(qū)域多次出現(xiàn)的也疊加下權(quán)重，畢竟多個(gè)方法都說(shuō)你是目標(biāo)，也是有理由的嘛。這樣我就得到了所有區(qū)域的目標(biāo)分?jǐn)?shù)，也就可以根據(jù)自己的需要選擇需要多少個(gè)區(qū)域了。

?

四 選擇性搜索性能評(píng)估

自然地，通過(guò)算法計(jì)算得到的包含物體的Bounding Boxes與真實(shí)情況（ground truth）的窗口重疊越多，那么算法性能就越好。這是使用的指標(biāo)是平均最高重疊率ABO（Average Best Overlap）。對(duì)于每個(gè)固定的類別 c，每個(gè)真實(shí)情況（ground truth）表示為?，令計(jì)算得到的位置假設(shè)L中的每個(gè)值lj，那么 ABO的公式表達(dá)為：

重疊率的計(jì)算方式：

?

上面結(jié)果給出的是一個(gè)類別的ABO，對(duì)于所有類別下的性能評(píng)價(jià)，很自然就是使用所有類別的ABO的平均值MABO（Mean Average Best Overlap）來(lái)評(píng)價(jià)。

?1、單一策略評(píng)估

我們可以通過(guò)改變多樣性策略中的任何一種，評(píng)估選擇性搜索的MABO性能指標(biāo)。論文中采取的策略如下：

• 使用RGB色彩空間(基于圖的圖像分割會(huì)利用不同的色彩進(jìn)行圖像區(qū)域分割)
• 采用四種相似度計(jì)算的組合方式
• 設(shè)置圖像分割的閾值k=50

然后通過(guò)改變其中一個(gè)策略參數(shù)，獲取MABO性能指標(biāo)如下表(第一列為改變的參數(shù)，第二列為MABO值，第三列為獲取的候選區(qū)的個(gè)數(shù))：

表中左側(cè)為不同的相似度組合，單獨(dú)的，我們可以看到紋理相似度表現(xiàn)最差，MABO為0.581，其他的MABO值介于0.63和0.64之間。當(dāng)使用多種相似度組合時(shí)MABO性能優(yōu)于單種相似度。表的右上角表名使用HSV顏色空間，有463個(gè)候選區(qū)域，而且MABO值最大為0.693。表的右下角表名使用較小的閾值，會(huì)得到更多的候選區(qū)和較高的MABO值。

2、多樣性策略組合

我們使用貪婪的搜索算法，把單一策略進(jìn)行組合，會(huì)獲得較高的MABO，但是也會(huì)造成計(jì)算成本的增加。下表給出了三種組合的MABO性能指標(biāo)：

上圖中的綠色邊框?yàn)閷?duì)象的標(biāo)記邊框，紅色邊框?yàn)槲覀兪褂?'Quality' Selective Search算法獲得的Overlap最高的候選框。可以看到我們這個(gè)候選框和真實(shí)標(biāo)記非常接近。

下表為和其它算法在VOC 2007測(cè)試集上的比較結(jié)果：

下圖為各個(gè)算法在選取不同候選區(qū)數(shù)量，Recall和MABO性能的曲線圖，從計(jì)算成本、以及性能考慮，Selective Search Fast算法在2000個(gè)候選區(qū)時(shí)，效果較好。

回到頂部

?五、代碼實(shí)現(xiàn)

?我們可以通過(guò)下面命令直接安裝Selective Search包。

pip install selectivesearch

然后從https://github.com/AlpacaDB/selectivesearch下載源碼，運(yùn)行example\example.py文件。效果如下：

?

# -*- coding: utf-8 -*- from __future__ import (division,print_function, )import skimage.data import matplotlib.pyplot as plt import matplotlib.patches as mpatches import selectivesearch import numpy as npdef main():# 加載圖片數(shù)據(jù)img = skimage.data.astronaut() '''執(zhí)行selective search，regions格式如下[{'rect': (left, top, width, height),'labels': [...],'size': component_size},...]'''img_lbl, regions = selectivesearch.selective_search(img, scale=500, sigma=0.9, min_size=10)#計(jì)算一共分割了多少個(gè)原始候選區(qū)域temp = set()for i in range(img_lbl.shape[0]):for j in range(img_lbl.shape[1]): temp.add(img_lbl[i,j,3]) print(len(temp)) #286#計(jì)算利用Selective Search算法得到了多少個(gè)候選區(qū)域print(len(regions)) #570#創(chuàng)建一個(gè)集合 元素不會(huì)重復(fù)，每一個(gè)元素都是一個(gè)list(左上角x，左上角y,寬,高)，表示一個(gè)候選區(qū)域的邊框candidates = set()for r in regions:#排除重復(fù)的候選區(qū)if r['rect'] in candidates:continue#排除小于 2000 pixels的候選區(qū)域(并不是bounding box中的區(qū)域大小) if r['size'] < 2000:continue#排除扭曲的候選區(qū)域邊框 即只保留近似正方形的x, y, w, h = r['rect']if w / h > 1.2 or h / w > 1.2:continuecandidates.add(r['rect'])#在原始圖像上繪制候選區(qū)域邊框fig, ax = plt.subplots(ncols=1, nrows=1, figsize=(6, 6))ax.imshow(img)for x, y, w, h in candidates:print(x, y, w, h)rect = mpatches.Rectangle((x, y), w, h, fill=False, edgecolor='red', linewidth=1)ax.add_patch(rect)plt.show()if __name__ == "__main__":main()

?

selective_search函數(shù)的定義如下：

def selective_search(im_orig, scale=1.0, sigma=0.8, min_size=50):'''Selective Search首先通過(guò)基于圖的圖像分割方法初始化原始區(qū)域，就是將圖像分割成很多很多的小塊然后我們使用貪心策略，計(jì)算每?jī)蓚€(gè)相鄰的區(qū)域的相似度然后每次合并最相似的兩塊，直到最終只剩下一塊完整的圖片然后這其中每次產(chǎn)生的圖像塊包括合并的圖像塊我們都保存下來(lái)Parameters----------im_orig : ndarrayInput imagescale : intFree parameter. Higher means larger clusters in felzenszwalb segmentation.sigma : floatWidth of Gaussian kernel for felzenszwalb segmentation.min_size : intMinimum component size for felzenszwalb segmentation.Returns-------img : ndarrayimage with region labelregion label is stored in the 4th value of each pixel [r,g,b,(region)]regions : array of dict[{'rect': (left, top, width, height),'labels': [...],'size': component_size 候選區(qū)域大小，并不是邊框的大小},...]'''assert im_orig.shape[2] == 3, "3ch image is expected"# load image and get smallest regions# region label is stored in the 4th value of each pixel [r,g,b,(region)] #圖片分割 把候選區(qū)域標(biāo)簽合并到最后一個(gè)通道上 height x width x 4 每一個(gè)像素的值為[r,g,b,(region)] img = _generate_segments(im_orig, scale, sigma, min_size)if img is None:return None, {}#計(jì)算圖像大小imsize = img.shape[0] * img.shape[1]#dict類型，鍵值為候選區(qū)域的標(biāo)簽 值為候選區(qū)域的信息，包括候選區(qū)域的邊框，以及區(qū)域的大小，顏色直方圖，紋理特征直方圖等信息R = _extract_regions(img)#list類型 每一個(gè)元素都是鄰居候選區(qū)域?qū)?ri,rj) (即兩兩相交的候選區(qū)域)neighbours = _extract_neighbours(R)# calculate initial similarities 初始化相似集合S = ?S = {}#計(jì)算每一個(gè)鄰居候選區(qū)域?qū)Φ南嗨贫萻(ri,rj)for (ai, ar), (bi, br) in neighbours: #S=S∪s(ri,rj) ai表示候選區(qū)域ar的標(biāo)簽 比如當(dāng)ai=1 bi=2 S[(1,2)就表示候選區(qū)域1和候選區(qū)域2的相似度S[(ai, bi)] = _calc_sim(ar, br, imsize)# hierarchal search 層次搜索 直至相似度集合為空while S != {}:# get highest similarity 獲取相似度最高的兩個(gè)候選區(qū)域 i,j表示候選區(qū)域標(biāo)簽i, j = sorted(S.items(), key=lambda i: i[1])[-1][0] #按照相似度排序# merge corresponding regions 合并相似度最高的兩個(gè)鄰居候選區(qū)域 rt = ri∪rj ,R = R∪rtt = max(R.keys()) + 1.0R[t] = _merge_regions(R[i], R[j])# mark similarities for regions to be removed 獲取需要?jiǎng)h除的元素的鍵值 key_to_delete = [] for k, v in S.items(): #k表示鄰居候選區(qū)域?qū)?i,j) v表示候選區(qū)域(i,j)表示相似度if (i in k) or (j in k):key_to_delete.append(k)# remove old similarities of related regions 移除候選區(qū)域ri對(duì)應(yīng)的所有相似度：S = S\s(ri,r*) 移除候選區(qū)域rj對(duì)應(yīng)的所有相似度：S = S\s(r*,rj)for k in key_to_delete:del S[k]# calculate similarity set with the new region 計(jì)算候選區(qū)域rt對(duì)應(yīng)的相似度集合St,S = S∪Stfor k in filter(lambda a: a != (i, j), key_to_delete):n = k[1] if k[0] in (i, j) else k[0]S[(t, n)] = _calc_sim(R[t], R[n], imsize)#獲取每一個(gè)候選區(qū)域的的信息 邊框、以及候選區(qū)域size,標(biāo)簽regions = []for k, r in R.items():regions.append({'rect': (r['min_x'], r['min_y'],r['max_x'] - r['min_x'], r['max_y'] - r['min_y']),'size': r['size'],'labels': r['labels']})#img：基于圖的圖像分割得到的候選區(qū)域 regions：Selective Search算法得到的候選區(qū)域return img, regions

?

該函數(shù)是按照Selective Search算法實(shí)現(xiàn)的，算法的每一步都有相對(duì)應(yīng)的代碼，并且把初始化候選區(qū)域，鄰居候選區(qū)域?qū)Φ谋闅v以及相似度計(jì)算，候選區(qū)域的合并都單獨(dú)封裝成了一個(gè)函數(shù)，由于代碼比較長(zhǎng)，就不一一介紹了，下面我把代碼附上，并且做了詳細(xì)的介紹，有興趣研究的童鞋看一下：

# -*- coding: utf-8 -*- import skimage.io import skimage.feature import skimage.color import skimage.transform import skimage.util import skimage.segmentation import numpy# "Selective Search for Object Recognition" by J.R.R. Uijlings et al. # # - Modified version with LBP extractor for texture vectorizationdef _generate_segments(im_orig, scale, sigma, min_size):"""segment smallest regions by the algorithm of Felzenswalb andHuttenlocher"""# open the Image segment_mask : (width, height) ndarray Integer mask indicating segment labels.im_mask = skimage.segmentation.felzenszwalb(skimage.util.img_as_float(im_orig), scale=scale, sigma=sigma,min_size=min_size)# merge mask channel to the image as a 4th channel 把類別合并到最后一個(gè)通道上 height x width x 4im_orig = numpy.append(im_orig, numpy.zeros(im_orig.shape[:2])[:, :, numpy.newaxis], axis=2)im_orig[:, :, 3] = im_maskreturn im_origdef _sim_colour(r1, r2):"""計(jì)算顏色相似度calculate the sum of histogram intersection of colourargs:r1：候選區(qū)域r1r2：候選區(qū)域r2return：[0,3]之間的數(shù)值"""return sum([min(a, b) for a, b in zip(r1["hist_c"], r2["hist_c"])])def _sim_texture(r1, r2):"""計(jì)算紋理特征相似度calculate the sum of histogram intersection of textureargs:r1：候選區(qū)域r1r2：候選區(qū)域r2return：[0,3]之間的數(shù)值"""return sum([min(a, b) for a, b in zip(r1["hist_t"], r2["hist_t"])])def _sim_size(r1, r2, imsize):"""計(jì)算候選區(qū)域大小相似度calculate the size similarity over the imageargs:r1：候選區(qū)域r1r2：候選區(qū)域r2return：[0,1]之間的數(shù)值"""return 1.0 - (r1["size"] + r2["size"]) / imsizedef _sim_fill(r1, r2, imsize):"""計(jì)算候選區(qū)域的距離合適度相似度calculate the fill similarity over the imageargs:r1：候選區(qū)域r1r2：候選區(qū)域r2imsize：原圖像像素?cái)?shù)return：[0,1]之間的數(shù)值"""bbsize = ((max(r1["max_x"], r2["max_x"]) - min(r1["min_x"], r2["min_x"]))* (max(r1["max_y"], r2["max_y"]) - min(r1["min_y"], r2["min_y"])))return 1.0 - (bbsize - r1["size"] - r2["size"]) / imsizedef _calc_sim(r1, r2, imsize):'''計(jì)算兩個(gè)候選區(qū)域的相似度，權(quán)重系數(shù)默認(rèn)都是1args:r1：候選區(qū)域r1r2：候選區(qū)域r2imsize：原圖片像素?cái)?shù)'''return (_sim_colour(r1, r2) + _sim_texture(r1, r2)+ _sim_size(r1, r2, imsize) + _sim_fill(r1, r2, imsize))def _calc_colour_hist(img):"""使用L1-norm歸一化獲取圖像每個(gè)顏色通道的25 bins的直方圖，這樣每個(gè)區(qū)域都可以得到一個(gè)75維的向量calculate colour histogram for each regionthe size of output histogram will be BINS * COLOUR_CHANNELS(3)number of bins is 25 as same as [uijlings_ijcv2013_draft.pdf]extract HSVargs:img：ndarray類型， 形狀為候選區(qū)域像素?cái)?shù) x 3(h,s,v)return：一維的ndarray類型，長(zhǎng)度為75"""BINS = 25hist = numpy.array([])for colour_channel in (0, 1, 2):# extracting one colour channelc = img[:, colour_channel]# calculate histogram for each colour and join to the result #計(jì)算每一個(gè)顏色通道的25 bins的直方圖 然后合并到一個(gè)一維數(shù)組中hist = numpy.concatenate([hist] + [numpy.histogram(c, BINS, (0.0, 255.0))[0]])# L1 normalize len(img):候選區(qū)域像素?cái)?shù)hist = hist / len(img)return histdef _calc_texture_gradient(img):"""原文：對(duì)每個(gè)顏色通道的8個(gè)不同方向計(jì)算方差σ=1的高斯微分（Gaussian Derivative，這里使用LBP替代calculate texture gradient for entire imageThe original SelectiveSearch algorithm proposed Gaussian derivativefor 8 orientations, but we use LBP instead.output will be [height(*)][width(*)]args：img： ndarray類型，形狀為height x width x 4，每一個(gè)像素的值為 [r,g,b,(region)]return：紋理特征，形狀為height x width x 4"""ret = numpy.zeros((img.shape[0], img.shape[1], img.shape[2]))for colour_channel in (0, 1, 2):ret[:, :, colour_channel] = skimage.feature.local_binary_pattern(img[:, :, colour_channel], 8, 1.0)return retdef _calc_texture_hist(img):"""使用L1-norm歸一化獲取圖像每個(gè)顏色通道的每個(gè)方向的10 bins的直方圖，這樣就可以獲取到一個(gè)240（10x8x3）維的向量calculate texture histogram for each regioncalculate the histogram of gradient for each coloursthe size of output histogram will beBINS * ORIENTATIONS * COLOUR_CHANNELS(3)args:img：候選區(qū)域紋理特征 形狀為候選區(qū)域像素?cái)?shù) x 4(r,g,b,(region))return：一維的ndarray類型，長(zhǎng)度為240"""BINS = 10hist = numpy.array([])for colour_channel in (0, 1, 2):# mask by the colour channelfd = img[:, colour_channel]# calculate histogram for each orientation and concatenate them all# and join to the resulthist = numpy.concatenate([hist] + [numpy.histogram(fd, BINS, (0.0, 1.0))[0]])# L1 Normalize len(img):候選區(qū)域像素?cái)?shù)hist = hist / len(img)return histdef _extract_regions(img):'''提取每一個(gè)候選區(qū)域的信息 比如類別(region)為5的區(qū)域表示的是一只貓的選區(qū)，這里就是提取這只貓的邊界框，左上角后右下角坐標(biāo)args:img: ndarray類型，形狀為height x width x 4，每一個(gè)像素的值為 [r,g,b,(region)]return : R:dict 每一個(gè)元素對(duì)應(yīng)一個(gè)候選區(qū)域， 每個(gè)元素也是一個(gè)dict類型{min_x:邊界框的左上角x坐標(biāo),min_y:邊界框的左上角y坐標(biāo),max_x:邊界框的右下角x坐標(biāo),max_y:邊界框的右下角y坐標(biāo),size:像素個(gè)數(shù),hist_c:顏色的直方圖,hist_t:紋理特征的直方圖,} '''#保存所有候選區(qū)域的bounding box 每一個(gè)元素都是一個(gè)dict {最小x坐標(biāo)值，最小y坐標(biāo)值，最大x坐標(biāo)值，最大y坐標(biāo)值,類別}# 通過(guò)上面四個(gè)參數(shù)確定一個(gè)邊界框R = {}# get hsv image RGB轉(zhuǎn)換為HSV色彩空間 height x width x 3hsv = skimage.color.rgb2hsv(img[:, :, :3])# pass 1: count pixel positions 遍歷每一個(gè)像素for y, i in enumerate(img): #y = 0 -> height - 1for x, (r, g, b, l) in enumerate(i): # x = 0 -> height - 1# initialize a new regionif l not in R:R[l] = {"min_x": 0xffff, "min_y": 0xffff,"max_x": 0, "max_y": 0, "labels": [l]}# bounding boxif R[l]["min_x"] > x:R[l]["min_x"] = xif R[l]["min_y"] > y:R[l]["min_y"] = yif R[l]["max_x"] < x:R[l]["max_x"] = xif R[l]["max_y"] < y:R[l]["max_y"] = y# pass 2: calculate texture gradient 紋理特征提取 利用LBP算子 height x width x 4tex_grad = _calc_texture_gradient(img)# pass 3: calculate colour histogram of each region 計(jì)算每一個(gè)候選區(qū)域(注意不是bounding box圈住的區(qū)域)的直方圖for k, v in R.items():# colour histogram height x width x 3 -> 候選區(qū)域k像素?cái)?shù) x 3（img[:, :, 3] == k返回的是一個(gè)二維坐標(biāo)的集合）masked_pixels = hsv[:, :, :][img[:, :, 3] == k]#print(type(masked_pixels),masked_pixels.shape)R[k]["size"] = len(masked_pixels / 4) #候選區(qū)域k像素?cái)?shù)#在hsv色彩空間下，使用L1-norm歸一化獲取圖像每個(gè)顏色通道的25 bins的直方圖，這樣每個(gè)區(qū)域都可以得到一個(gè)75維的向量R[k]["hist_c"] = _calc_colour_hist(masked_pixels) #在rgb色彩空間下，使用L1-norm歸一化獲取圖像每個(gè)顏色通道的每個(gè)方向的10 bins的直方圖，這樣就可以獲取到一個(gè)240（10x8x3）維的向量R[k]["hist_t"] = _calc_texture_hist(tex_grad[:, :][img[:, :, 3] == k]) #tex_grad[:, :][img[:, :, 3] == k]形狀為候選區(qū)域像素?cái)?shù) x 4return Rdef _extract_neighbours(regions):'''提取 鄰居候選區(qū)域?qū)?ri,rj)(即兩兩相交)args:regions：dict 每一個(gè)元素都對(duì)應(yīng)一個(gè)候選區(qū)域return：返回一個(gè)list，每一個(gè)元素都對(duì)應(yīng)一個(gè)鄰居候選區(qū)域?qū)?#39;''#判斷兩個(gè)候選區(qū)域是否相交def intersect(a, b):if (a["min_x"] < b["min_x"] < a["max_x"]and a["min_y"] < b["min_y"] < a["max_y"]) or (a["min_x"] < b["max_x"] < a["max_x"]and a["min_y"] < b["max_y"] < a["max_y"]) or (a["min_x"] < b["min_x"] < a["max_x"]and a["min_y"] < b["max_y"] < a["max_y"]) or (a["min_x"] < b["max_x"] < a["max_x"]and a["min_y"] < b["min_y"] < a["max_y"]):return Truereturn False#轉(zhuǎn)換為list 每一個(gè)元素 (l,regions[l])R = list(regions.items())#保存兩兩相交候選區(qū)域?qū)eighbours = []#每次抽取兩個(gè)候選區(qū)域 兩兩組合，判斷是否相交for cur, a in enumerate(R[:-1]):for b in R[cur + 1:]:if intersect(a[1], b[1]):neighbours.append((a, b))return neighboursdef _merge_regions(r1, r2):'''合并兩個(gè)候選區(qū)域args:r1：候選區(qū)域1r2：候選區(qū)域2return：返回合并后的候選區(qū)域rt'''new_size = r1["size"] + r2["size"]rt = {"min_x": min(r1["min_x"], r2["min_x"]),"min_y": min(r1["min_y"], r2["min_y"]),"max_x": max(r1["max_x"], r2["max_x"]),"max_y": max(r1["max_y"], r2["max_y"]),"size": new_size,"hist_c": (r1["hist_c"] * r1["size"] + r2["hist_c"] * r2["size"]) / new_size,"hist_t": (r1["hist_t"] * r1["size"] + r2["hist_t"] * r2["size"]) / new_size,"labels": r1["labels"] + r2["labels"]}return rtdef selective_search(im_orig, scale=1.0, sigma=0.8, min_size=50):'''Selective Search首先通過(guò)基于圖的圖像分割方法初始化原始區(qū)域，就是將圖像分割成很多很多的小塊然后我們使用貪心策略，計(jì)算每?jī)蓚€(gè)相鄰的區(qū)域的相似度然后每次合并最相似的兩塊，直到最終只剩下一塊完整的圖片然后這其中每次產(chǎn)生的圖像塊包括合并的圖像塊我們都保存下來(lái)Parameters----------im_orig : ndarrayInput imagescale : intFree parameter. Higher means larger clusters in felzenszwalb segmentation.sigma : floatWidth of Gaussian kernel for felzenszwalb segmentation.min_size : intMinimum component size for felzenszwalb segmentation.Returns-------img : ndarrayimage with region labelregion label is stored in the 4th value of each pixel [r,g,b,(region)]regions : array of dict[{'rect': (left, top, width, height),'labels': [...],'size': component_size 候選區(qū)域大小，并不是邊框的大小},...]'''assert im_orig.shape[2] == 3, "3ch image is expected"# load image and get smallest regions# region label is stored in the 4th value of each pixel [r,g,b,(region)] #圖片分割 把候選區(qū)域標(biāo)簽合并到最后一個(gè)通道上 height x width x 4 每一個(gè)像素的值為[r,g,b,(region)] img = _generate_segments(im_orig, scale, sigma, min_size)if img is None:return None, {}#計(jì)算圖像大小imsize = img.shape[0] * img.shape[1]#dict類型，鍵值為候選區(qū)域的標(biāo)簽 值為候選區(qū)域的信息，包括候選區(qū)域的邊框，以及區(qū)域的大小，顏色直方圖，紋理特征直方圖等信息R = _extract_regions(img)#list類型 每一個(gè)元素都是鄰居候選區(qū)域?qū)?ri,rj) (即兩兩相交的候選區(qū)域)neighbours = _extract_neighbours(R)# calculate initial similarities 初始化相似集合S = ?S = {}#計(jì)算每一個(gè)鄰居候選區(qū)域?qū)Φ南嗨贫萻(ri,rj)for (ai, ar), (bi, br) in neighbours: #S=S∪s(ri,rj) ai表示候選區(qū)域ar的標(biāo)簽 比如當(dāng)ai=1 bi=2 S[(1,2)就表示候選區(qū)域1和候選區(qū)域2的相似度S[(ai, bi)] = _calc_sim(ar, br, imsize)# hierarchal search 層次搜索 直至相似度集合為空while S != {}:# get highest similarity 獲取相似度最高的兩個(gè)候選區(qū)域 i,j表示候選區(qū)域標(biāo)簽i, j = sorted(S.items(), key=lambda i: i[1])[-1][0] #按照相似度排序# merge corresponding regions 合并相似度最高的兩個(gè)鄰居候選區(qū)域 rt = ri∪rj ,R = R∪rtt = max(R.keys()) + 1.0R[t] = _merge_regions(R[i], R[j])# mark similarities for regions to be removed 獲取需要?jiǎng)h除的元素的鍵值 key_to_delete = [] for k, v in S.items(): #k表示鄰居候選區(qū)域?qū)?i,j) v表示候選區(qū)域(i,j)表示相似度if (i in k) or (j in k):key_to_delete.append(k)# remove old similarities of related regions 移除候選區(qū)域ri對(duì)應(yīng)的所有相似度：S = S\s(ri,r*) 移除候選區(qū)域rj對(duì)應(yīng)的所有相似度：S = S\s(r*,rj)for k in key_to_delete:del S[k]# calculate similarity set with the new region 計(jì)算新的候選區(qū)域rt對(duì)應(yīng)的相似度集合St,S = S∪Stfor k in filter(lambda a: a != (i, j), key_to_delete): #過(guò)濾除了(i,j)之外的候選區(qū)域n = k[1] if k[0] in (i, j) else k[0]#計(jì)算新的候選區(qū)域t與候選區(qū)域n之間的相似度S[(t, n)] = _calc_sim(R[t], R[n], imsize)#獲取每一個(gè)候選區(qū)域的的信息 邊框、以及候選區(qū)域size,標(biāo)簽regions = []for k, r in R.items():regions.append({'rect': (r['min_x'], r['min_y'],r['max_x'] - r['min_x'], r['max_y'] - r['min_y']),'size': r['size'],'labels': r['labels']})#img：ndarray 基于圖的圖像分割得到的候選區(qū)域 regions：list Selective Search算法得到的候選區(qū)域return img, regions

?

參考文章：

[1]圖像分割—基于圖的圖像分割（Graph-Based Image Segmentation）(附代碼)

[2]目標(biāo)檢測(cè)（1）-Selective Search

[3]https://github.com/AlpacaDB/selectivesearch(代碼)

[4]Selective Search for Object Recognition(推薦)

[5]J.R. Uijlings, K.E. vandeSande, T. Gevers, and A.W. Smeulders. Selective search for object recognition. IJCV, 2013.

[6]相關(guān)源代碼（matlab）

[7]C++簡(jiǎn)版代碼

總結(jié)

以上是生活随笔為你收集整理的目标检测之选择性搜索-Selective Search的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。