寫(xiě)在最前面：

本文只會(huì)講思路，不會(huì)放代碼，不會(huì)放代碼，不會(huì)放代碼，重要的事情說(shuō)三遍。

因?yàn)檫@個(gè)事情還是比較敏感的，頂象在驗(yàn)證碼方向做的也算是比較大的了，國(guó)內(nèi)很多公司在用的驗(yàn)證碼都是頂象的，代碼就不放了，避免被人拿去做壞事了。

另外，也是為頂象的驗(yàn)證碼做個(gè)簡(jiǎn)單的測(cè)試。如果有頂象的大佬看到，可以考慮把這個(gè)驗(yàn)證碼更新一下啦~

純一時(shí)手癢，僅為技術(shù)交流，請(qǐng)勿用于任何商業(yè)活動(dòng)，也請(qǐng)勿對(duì)頂象的驗(yàn)證碼進(jìn)行攻擊，感謝~

請(qǐng)不要進(jìn)行任何違法行為，否則后果自負(fù)！

以下正文。

前兩天有位大佬丟過(guò)來(lái)一張驗(yàn)證碼圖片，問(wèn)我該如何處理。驗(yàn)證碼它長(zhǎng)這樣，要求是點(diǎn)擊圖片中被分割出來(lái)的最大的區(qū)域：

喲吼，這驗(yàn)證碼，有點(diǎn)東西啊~

但是大佬問(wèn)的問(wèn)題，說(shuō)什么也得給搞定嘛~

于是，我思索了一下，一個(gè)想法慢慢成形，我覺(jué)得可以把任務(wù)拆解成幾個(gè)小問(wèn)題：

• 1.檢測(cè)出圖片中被標(biāo)記出來(lái)的點(diǎn)
• 2.將檢測(cè)出來(lái)的點(diǎn)連成一條線
• 3.根據(jù)線將圖像切割成幾個(gè)不連通的區(qū)域
• 4.計(jì)算各個(gè)區(qū)域的面積，獲取面積最大的區(qū)域的一個(gè)點(diǎn)的坐標(biāo)，即為結(jié)果

略微推敲了幾遍，覺(jué)得想法可行，于是，開(kāi)搞~

轉(zhuǎn)載請(qǐng)注明來(lái)源：https://blog.csdn.net/aaronjny/article/details/110245896

一、檢測(cè)出圖片中被標(biāo)記出來(lái)的點(diǎn)

先來(lái)解決第一個(gè)問(wèn)題，怎么檢測(cè)出圖片中被標(biāo)記出來(lái)的點(diǎn)。

我最直接的想法是使用目標(biāo)檢測(cè)算法，因?yàn)檫@些點(diǎn)還是挺明顯的，目標(biāo)檢測(cè)模型（比如yolo）應(yīng)該是可以奏效的。但是一張圖片上的點(diǎn)比較多，標(biāo)注數(shù)據(jù)集感覺(jué)很麻煩，雖然覺(jué)得可行，但真心不想費(fèi)那么大功夫。

又看到標(biāo)記點(diǎn)的顏色和正常圖片的顏色還是有一定差別的，于是，我決定先嘗試直接在圖片的像素和色值上下些功夫。

1、BGR圖像上的、基于離群值篩選的檢測(cè)方法

考慮到標(biāo)記點(diǎn)和正常圖片的顏色上的差別，可以初步判斷一個(gè)標(biāo)記點(diǎn)和周圍的其他像素點(diǎn)在色值上是有一定偏離的，我們可以考慮把色值與相鄰局部區(qū)域整體色值有一定大小偏離的點(diǎn)，認(rèn)為是標(biāo)記點(diǎn)。

emmm，話比較繞是吧？感覺(jué)不太好理解？那我來(lái)舉個(gè)例子：

有一只哈士奇混在了一群狼里面，雖然都是犬科，但是長(zhǎng)得還是不太一樣的，我們需要把二哈揪出來(lái)~

我們以前面的示例圖片為例，解釋一下這個(gè)問(wèn)題，請(qǐng)看：

以藍(lán)色框圈起來(lái)的綠色點(diǎn)群（實(shí)際上是很多綠色點(diǎn)聚在一起了，不只是一個(gè)點(diǎn)）為例，在藍(lán)色框選中的圖片區(qū)域里可以看到，雖然已經(jīng)有不少綠色點(diǎn)了，但這個(gè)點(diǎn)的數(shù)量占藍(lán)色框里的全部點(diǎn)的比例還是偏少的，更多的是正常的點(diǎn)。

假如說(shuō)把藍(lán)色框擴(kuò)大，變成紅色框，會(huì)發(fā)現(xiàn)，雖然綠色點(diǎn)數(shù)量增加了，但正常點(diǎn)的數(shù)量增加的更多，綠色點(diǎn)的比例進(jìn)一步降低了。

那么，相對(duì)于正常點(diǎn)來(lái)說(shuō)，標(biāo)記點(diǎn)的色值就是離群值了（偏離了周圍正常點(diǎn)的色值范圍）。那么，我們就可以先設(shè)定一個(gè)框框，然后滑動(dòng)這個(gè)窗口，遍歷整張圖片，計(jì)算窗口在每個(gè)位置檢測(cè)出離群值的點(diǎn)，這些點(diǎn)就可以作為標(biāo)記點(diǎn)。

那么，具體該怎么做呢？

其實(shí)檢測(cè)離群點(diǎn)的算法有很多，我這里介紹一種，絕對(duì)中位差法。

①對(duì)于一個(gè)h*w的矩陣M，先統(tǒng)計(jì)其中位數(shù)，即為median。

②對(duì)于矩陣M中的每一個(gè)值，都是用它減去 median，并取絕對(duì)值，獲得新的矩陣N。

③對(duì)N求中位數(shù)，即中位差，我們記為mad。

④我們認(rèn)為在區(qū)間 [median-x*mad,median+x*mad] 內(nèi)的點(diǎn)屬于正常點(diǎn)，超出則為離群點(diǎn)，x看情況設(shè)置，我們這里取3。

如果使用 numpy 來(lái)描述這個(gè)過(guò)程的話，如果要檢測(cè)點(diǎn)(row,col)是否為離群值，可以表示如下：

median = np.median(M)
mad = np.median(np.abs(M - median))
lower_limit = median - 3 * mad
upper_limit = median + 3 * mad
if lower_limit <= im[row][col] <= upper_limit:
  print('正常值')
else:
  print('離群值')

• 1
•  
•  
•  
•  
•  
•  
•  

有幾點(diǎn)要注意的是：

• 1.這里的矩陣M實(shí)際上并不是整張圖片，按前面的描述應(yīng)該也能看出來(lái)，M指的實(shí)際上是要檢測(cè)點(diǎn)(row,col)向周圍等距離擴(kuò)散出來(lái)的一個(gè)小矩陣。
• 2.我這里也只是針對(duì)矩陣舉例的，實(shí)際上BGR圖片是(h,w,3)的，而不是（h,w）的，所以這里實(shí)際處理的時(shí)候是分別對(duì)3個(gè)圖像信道做了絕對(duì)中位差法篩選（即調(diào)用3次，每次處理一個(gè)信道，均在正常范圍內(nèi)才認(rèn)為是正常點(diǎn)）。

如果還不明白的話，我再舉個(gè)具體的例子，我隨便編了一個(gè)小矩陣，5*9的，如下圖藍(lán)色框所示：

假設(shè)我們?nèi)∮绊懢嚯xk為1（表示只關(guān)注距離待檢測(cè)點(diǎn)不超過(guò)1個(gè)格子的點(diǎn)），那么滑動(dòng)窗口（感受野）的大小就是1*2+1=3。假設(shè)我們要檢測(cè)的點(diǎn)時(shí)第3行第3列的點(diǎn)，則窗口可以用紅色框表示：

還記得中位數(shù)是什么嗎？把一組數(shù)按照從小到大的順序排列，最中間的數(shù)就是中位數(shù)。對(duì)于這個(gè)紅色框來(lái)說(shuō)，從小到大排列為：

[1,2,2,2,2,3,4,4,5]

• 1

一共9個(gè)數(shù)，最中間的數(shù)是第5個(gè)，數(shù)值是2，即 median = 2。

然后計(jì)算出矩陣N，即讓矩陣M（紅色框）中的每個(gè)數(shù)都減去 median ，并取絕對(duì)值 ：

[
	[3,1,2],
	[0,1,0],
	[2,0,0]
]

•  

2

3

4

5

然后計(jì)算N的中位數(shù)，[0,0,0,0,1,1,2,2,3]，得到 mad=1。

根據(jù) [median-x*mad,median+x*mad]，當(dāng)x取3時(shí)，可以計(jì)算出正常區(qū)間為[2-3*1,2+3*1]，即[-1,5]。第3行第3列的數(shù)字剛好為3，在這個(gè)區(qū)間里，不是離群值。

接著我們判斷第3行第4列的數(shù)字是否為離群值：

簡(jiǎn)單計(jì)算一下:

median=3
N=array([[ 2.,  1.,  0.],
       [ 0.,  1., 17.],
       [ 1.,  1.,  3.]])
mad=1
區(qū)間為[3-1*3,3+1*3]=[0,6]

 

第3行第4列的數(shù)字2在這個(gè)區(qū)間里，是正常值。

再將窗口右移一格：

計(jì)算一下：

median=5
N=array([[ 1.,  2.,  1.],
       [ 3., 15.,  2.],
       [ 3.,  1.,  0.]])
mad=2
區(qū)間為[5-2*3,5+2*3]=[-1,11]

1

2

3

4

5

6

第3行第5列數(shù)值為20，不在這個(gè)區(qū)間里，為異常值。這個(gè)和我們的直觀判斷也是一致的，因?yàn)?0確實(shí)比旁邊的數(shù)都大很多，屬于異常值。

這樣應(yīng)該明白了吧？

OK，我們使用絕對(duì)中位差法測(cè)試一下，檢測(cè)效果一般，如下圖所示：

可以看到，雖然標(biāo)記點(diǎn)被檢測(cè)出來(lái)了（事實(shí)證明是這一張相對(duì)容易檢測(cè)，在其他的樣本上還會(huì)存在部分標(biāo)記點(diǎn)沒(méi)有被檢測(cè)出來(lái)的情況），但也誤將一些正常的點(diǎn)識(shí)別為了標(biāo)記點(diǎn)，我們把這些誤識(shí)別的點(diǎn)稱為噪聲，因?yàn)樗鼈兿鄬?duì)于我們要檢測(cè)的標(biāo)記點(diǎn)來(lái)說(shuō)，就是一種干擾。

那么，我們需要進(jìn)行降噪。

降噪的方法也很簡(jiǎn)單，跟上面的方法類似。我也是取一個(gè)局部的窗口，統(tǒng)計(jì)窗口內(nèi)被認(rèn)為是標(biāo)記點(diǎn)的個(gè)數(shù)，以及窗口內(nèi)全部點(diǎn)的個(gè)數(shù)（即被認(rèn)為是正常的點(diǎn)+被認(rèn)為是標(biāo)記點(diǎn)的點(diǎn)），計(jì)算占比。從圖片上可以看出，噪聲一般是比較零散的，所以可以通過(guò)占比閾值的設(shè)置過(guò)濾掉大部分噪聲點(diǎn)。

降噪后的結(jié)果如下:

結(jié)果確實(shí)好了很多，可以看到大部分噪點(diǎn)被過(guò)濾掉了，只剩下小部分比較密集的還在負(fù)隅頑抗。但同時(shí)也能看到，這種降噪方法也會(huì)對(duì)識(shí)別正確的標(biāo)記點(diǎn)產(chǎn)生負(fù)面影響（即把正確的標(biāo)記點(diǎn)也認(rèn)為是噪點(diǎn)了，雖然很少，但在上圖還是能看到的），所以關(guān)于閾值的設(shè)置需要好好權(quán)衡。

還有一點(diǎn)需要注意的是，對(duì)于每個(gè)點(diǎn)都做絕對(duì)中位差法檢測(cè)的話，計(jì)算量還是太大了，消耗的時(shí)間比較高。

多給幾個(gè)示例，就能夠看出檢測(cè)結(jié)果不夠好了：

2、灰度圖像上、基于離群值篩選的檢測(cè)方法

我們已經(jīng)在BGR圖像上進(jìn)行了離群值篩選，那么可以考慮一下，我能否直接在灰度圖像上這么做？

畢竟一來(lái)，BGR有3個(gè)信道，灰度圖片只有1個(gè)信道，所以本來(lái)需要做3次的運(yùn)算現(xiàn)在只用做1次了，計(jì)算量能有較大幅度的降低；二來(lái)，說(shuō)不定只從灰度明暗的角度處理，效果會(huì)更好？

于是，我將圖片轉(zhuǎn)灰度，再做測(cè)試。圖片轉(zhuǎn)灰度：

使用絕對(duì)中位差法檢測(cè)標(biāo)記點(diǎn)：

過(guò)濾噪聲點(diǎn)：

可以看到，速度和效果均略微提升，但提升有限。

再多給幾個(gè)示例對(duì)比：

另外，轉(zhuǎn)灰度之后能夠看到，標(biāo)記點(diǎn)整體是比正常點(diǎn)偏亮一點(diǎn)的。所以也可以嘗試直接設(shè)置色值的閾值，來(lái)檢測(cè)標(biāo)記點(diǎn)。經(jīng)測(cè)試，速度會(huì)更快，但效果比絕對(duì)中位差法要差一些，所以我就不再展開(kāi)了。

3、哈里斯角點(diǎn)檢測(cè)

如果覺(jué)得絕對(duì)中位差在處理這個(gè)任務(wù)時(shí)還是不夠好的話，有什么更好的方法嗎？

有的！從朋友那里得知哈里斯角點(diǎn)檢測(cè)算法時(shí)，我整個(gè)人都驚呆了——竟然還有這么牛X的算法？

這是什么神仙算法？

處理驗(yàn)證碼簡(jiǎn)直不要太好用好不好？

為自己狹窄的知識(shí)面默哀……在線卑微……

那么，什么是哈里斯角點(diǎn)檢測(cè)呢？

要說(shuō)哈里斯角點(diǎn)檢測(cè)，得先說(shuō)一下角點(diǎn)。

那么，什么是角點(diǎn)呢？

角點(diǎn)可以簡(jiǎn)單理解為是兩條邊的交點(diǎn)?？梢灶惐任覀兊淖澜?、筆尖等，如果將桌子和筆拍下來(lái)，桌角和筆尖都會(huì)是角點(diǎn)。

上面的定義是為了方便我們理解的，如果嚴(yán)格一點(diǎn)來(lái)說(shuō)的話，角點(diǎn)指的是在鄰域內(nèi)具有兩個(gè)（及以上）主方向的特征點(diǎn)。它在圖像中有具體的坐標(biāo)和某些數(shù)學(xué)特征，通常表現(xiàn)為：

• 輪廓之間的交點(diǎn)

• 對(duì)于同一場(chǎng)景，即使視角發(fā)生變化，通常具備穩(wěn)定性質(zhì)的特征

• 該點(diǎn)附近區(qū)域的像素點(diǎn)無(wú)論在梯度方向上還是其梯度幅值上有著較大變化

  如下圖所示，在各個(gè)方向上移動(dòng)小窗口，如果在所有方向上移動(dòng)，窗口內(nèi)灰度都發(fā)生變化，則認(rèn)為是角點(diǎn)；如果任何方向都不變化，則是均勻區(qū)域；如果灰度只在一個(gè)方向上變化，則可能是圖像邊緣。

  

哈里斯角點(diǎn)檢測(cè)的基本思想是什么呢？

算法基本思想是使用一個(gè)固定窗口在圖像上進(jìn)行任意方向上的滑動(dòng)，比較滑動(dòng)前與滑動(dòng)后兩種情況，窗口中的像素灰度變化程度，如果存在任意方向上的滑動(dòng)，都有著較大灰度變化，那么我們可以認(rèn)為該窗口中存在角點(diǎn)。

以上關(guān)于哈里斯角點(diǎn)檢測(cè)的內(nèi)容，主要整理、參考于下面兩篇文章，感興趣的話可以閱讀一下：

• Harris角點(diǎn)檢測(cè)原理詳解 (https://blog.csdn.net/lwzkiller/article/details/54633670)
• 圖像特征之Harris角點(diǎn)檢測(cè) (https://senitco.github.io/2017/06/18/image-feature-harris/)

好了，問(wèn)題又來(lái)了——哈里斯角點(diǎn)檢測(cè)算法實(shí)現(xiàn)困難嗎？

不用擔(dān)心，opencv 已經(jīng)幫你實(shí)現(xiàn)好啦~ 調(diào)用cv2.cornerHarris 即可。

那哈里斯角點(diǎn)檢測(cè)的效果如何呢？仍然選取初次測(cè)試的圖片，看下效果：

喲呵，效果很不錯(cuò)哦~雖然有小部分標(biāo)記點(diǎn)沒(méi)檢測(cè)出來(lái)，但大體輪廓已經(jīng)在了，而且關(guān)鍵是，幾乎沒(méi)有噪點(diǎn)，這對(duì)我們后面的處理提供了極大的便利。

還有一個(gè)明顯的優(yōu)點(diǎn)是，哈里斯角點(diǎn)檢測(cè)的速度很快，再加上檢測(cè)效果不錯(cuò)，降噪部分的代碼也可以去掉了，計(jì)算速度有了明顯的提升。

多給幾個(gè)示例對(duì)比：

我覺(jué)得效果已經(jīng)很不錯(cuò)了，那標(biāo)記點(diǎn)的檢測(cè)就到這里吧？可以開(kāi)始下一步了。

二、將檢測(cè)出來(lái)的點(diǎn)連成一條線

關(guān)于如何將點(diǎn)連成一條線這件事上，我也想了兩種方法：

• 使用圖搜索，將標(biāo)記點(diǎn)組成連通域，再搜索域和域之間的最短路徑，當(dāng)距離不超過(guò)一定值時(shí)進(jìn)行連接。反復(fù)迭代這個(gè)過(guò)程，直到所有的域都不能再連通或者只剩下了一個(gè)域
• 直接將每一個(gè)原始被標(biāo)記點(diǎn)周圍一定范圍內(nèi)的點(diǎn)，都也變成被標(biāo)記點(diǎn)，我把這個(gè)過(guò)程稱為“浸染”。其中，只有原始的被標(biāo)記點(diǎn)有浸染能力，被浸染出來(lái)的被標(biāo)記點(diǎn)不具備二次浸染周圍點(diǎn)的能力。這樣相當(dāng)于把每個(gè)標(biāo)記點(diǎn)都放大了，只要點(diǎn)足夠大，點(diǎn)與點(diǎn)之間的縫隙也就被點(diǎn)本身給覆蓋掉了，也就連成了線。

第一種方法的效果確實(shí)不錯(cuò)，我覺(jué)得主要有兩個(gè)缺點(diǎn)：

• 算法寫(xiě)起來(lái)麻煩
• 時(shí)間復(fù)雜度特別特別特別高

第一個(gè)缺點(diǎn)對(duì)我來(lái)說(shuō)問(wèn)題不算大，我已經(jīng)寫(xiě)好了。但第二個(gè)缺點(diǎn)就嚴(yán)重影響實(shí)用了，沒(méi)法在工程里面用起來(lái)，遂放棄。

第二種方法雖然簡(jiǎn)單粗暴，但快速有效啊。可能有的同學(xué)會(huì)疑惑，如果我對(duì)被標(biāo)記點(diǎn)進(jìn)行浸染的話，最終被標(biāo)記點(diǎn)的數(shù)量會(huì)變多，會(huì)占用原來(lái)的正常點(diǎn)，這樣是不是會(huì)對(duì)我最后計(jì)算面積產(chǎn)生影響??？

影響肯定是有點(diǎn)，這樣連線分割之后的區(qū)域，面積算起來(lái)肯定比正常的要小。但我只需要判斷哪個(gè)區(qū)域更大就行了，并不需要我精準(zhǔn)返回面積（不說(shuō)算法了，人也沒(méi)法判斷出來(lái)?。?，我這么做并不會(huì)改變各區(qū)域的面積大小順序，所以并無(wú)大礙。

浸染的時(shí)候，還要考慮浸染多大范圍。當(dāng)浸染的范圍是0時(shí)（即不浸染周圍的元素），就和第一步的檢測(cè)結(jié)果一致：

當(dāng)浸染范圍是1時(shí)（即影響周圍距離不超過(guò)1的格子，實(shí)際表現(xiàn)就是以當(dāng)前點(diǎn)為中心的一個(gè)3*3的窗口），連線結(jié)果為：

浸染范圍為2時(shí)（5*5的窗口）：

需要注意的是，浸染也是有一定計(jì)算量的。當(dāng)浸染范圍越大（但也不能太大，不然可能會(huì)把線都糊在一起）時(shí)，對(duì)區(qū)域的劃分就越精確，越不容易出現(xiàn)連線里有斷點(diǎn)的情況，但耗時(shí)也會(huì)越大。

我最終將閾值設(shè)在了7，能夠在保證精度的同時(shí)兼顧性能：

再多看兩個(gè)例子：

連線做到這一步也就可以了，開(kāi)始下一步。

三、根據(jù)線將圖像切割成幾個(gè)不連通的區(qū)域

我們以這張圖片為例：

我們要做的是，讓程序能將圖片里面的五個(gè)區(qū)域給識(shí)別區(qū)分出來(lái)：

具體該怎么做呢——兄dei，你聽(tīng)說(shuō)過(guò)深度優(yōu)先搜索嗎？

其實(shí)這就是一個(gè)簡(jiǎn)單的圖搜索問(wèn)題，搜索出圖中所有連通的像素，每一個(gè)連通域就是一個(gè)切割出來(lái)的區(qū)域。

如果你還不理解的話，我們可以這么看：

首先，你有一張圖：

然后，從左上角出發(fā)，也就是坐標(biāo)(0,0)的位置。如果它不是黑色的被標(biāo)記點(diǎn)，就將它涂成紅色。

然后從這個(gè)點(diǎn)開(kāi)始向外擴(kuò)散，把遇到的所有不是黑色的標(biāo)記點(diǎn)都涂成紅色。

注意，在涂的過(guò)程中，你還需要記錄下你涂過(guò)的點(diǎn)的坐標(biāo)?，F(xiàn)在這個(gè)區(qū)域被涂滿了，無(wú)法再繼續(xù)了，而你也已獲得了一個(gè)連通域（包括這個(gè)域里的點(diǎn)的坐標(biāo)集），也就是一個(gè)分割出來(lái)的子圖。

接下來(lái)，我們?cè)僦鹦袙呙柽@張圖，找到第一個(gè)不是紅色、也不是黑色的點(diǎn)，我們就找到了下面這個(gè)紫色的點(diǎn)：

然后跟上面的步驟相同，逐步擴(kuò)散，直到不能再擴(kuò)散為止：

這樣，我們又獲得了第二個(gè)連通域，也就是第二個(gè)切割出來(lái)的子圖。

使用同樣的方式，我們能夠獲得剩下的三個(gè)連通域，也就是如下的黃、綠、藍(lán)三個(gè)區(qū)域：

你看，這不是很輕松就完成了子圖的分割嗎？

編碼上也并不困難，只要會(huì)寫(xiě)遞歸，再簡(jiǎn)單學(xué)習(xí)一下圖搜索相關(guān)的算法，就能夠?qū)懗鰜?lái)，很簡(jiǎn)單的。而且流程我已經(jīng)說(shuō)的很細(xì)了，按照我說(shuō)的流程直接實(shí)現(xiàn)也是沒(méi)問(wèn)題的。我剛才已經(jīng)對(duì)連通域搜索算法做了詳細(xì)的舉例，這要是還搞不明白的話我也沒(méi)辦法啦~

當(dāng)然了，上面是為了理解起來(lái)方便一點(diǎn)，講的比較細(xì)致繁瑣，實(shí)際開(kāi)發(fā)中某些流程是可以被優(yōu)化的。

四、計(jì)算各個(gè)區(qū)域的面積，獲取面積最大的區(qū)域的一個(gè)點(diǎn)的坐標(biāo)，即為結(jié)果

在上一步，我們已經(jīng)獲得了所有連通子圖，以及它們對(duì)應(yīng)的點(diǎn)集。

再來(lái)回顧一下驗(yàn)證碼需要我們做的——點(diǎn)擊面積最大的子圖。

把問(wèn)題拆的細(xì)一點(diǎn)，如下：

• 計(jì)算各個(gè)子圖的面積
• 找出面積最大的子圖
• 獲取該子圖中的隨機(jī)一個(gè)點(diǎn)的坐標(biāo)

①怎么計(jì)算面積？

最簡(jiǎn)單的方法，統(tǒng)計(jì)子圖里面點(diǎn)的數(shù)量不就可以嗎？類似于積分的思想。我們已經(jīng)獲得了每個(gè)子圖對(duì)應(yīng)的點(diǎn)集，所以這一步就只是簡(jiǎn)單的統(tǒng)計(jì)，很容易做到。

②怎么找出面積最大的子圖？

這個(gè)就不用說(shuō)了吧？排個(gè)序就行了嘛。

③怎么獲取該子圖中隨機(jī)的一個(gè)點(diǎn)的坐標(biāo)？

emmm，愛(ài)怎么獲取怎么獲取唄，用 python 的 random 標(biāo)準(zhǔn)庫(kù)隨機(jī)選一個(gè)也行，嫌麻煩的話，直接去點(diǎn)集里面的第一個(gè)點(diǎn)也行，只要保證屬于面積最大的子圖的點(diǎn)集就行。

五、結(jié)果展示

所有的流程都走完了，不妨選幾張圖片做個(gè)測(cè)試。我手里總共有10張樣例圖片（藍(lán)色點(diǎn)是要點(diǎn)擊的地方）。

對(duì)于上面這張圖片，可以發(fā)現(xiàn)，藍(lán)色點(diǎn)竟然和黑色點(diǎn)重疊了？

其實(shí)是沒(méi)有問(wèn)題的。為了展示的清楚，我把藍(lán)色點(diǎn)也放大了很多倍，原始的點(diǎn)（要點(diǎn)擊的坐標(biāo)）實(shí)際上是和黑色點(diǎn)無(wú)重疊的。

另外，我將黑色點(diǎn)浸染得很粗，本身就也相當(dāng)于做了一定的冗余，也能保證不會(huì)出現(xiàn)點(diǎn)擊在標(biāo)記點(diǎn)上的情況。

繼續(xù)看：

可以看到效果還不錯(cuò)哈~我們下面來(lái)做結(jié)果分析。

六、結(jié)果分析

從剛開(kāi)始開(kāi)發(fā)，到最后完成，我經(jīng)歷了幾個(gè)版本的迭代優(yōu)化。

①第一個(gè)版本，是研究可行性的代碼。

實(shí)現(xiàn)思路：

BGR圖像上的絕對(duì)中位差法 + 降噪 + 標(biāo)記點(diǎn)浸染連線 + 圖連通搜索

這個(gè)版本只是為了驗(yàn)證思路是否可行，各方面沒(méi)做什么優(yōu)化，所以執(zhí)行效率比較低，工程階段基本沒(méi)法用。

執(zhí)行時(shí)間：

1分鐘

通過(guò)率：

一般

②第二個(gè)版本是對(duì)第一個(gè)版本的改進(jìn)，主要使用了numpy和各種提速技巧對(duì)算法做了性能優(yōu)化。

實(shí)現(xiàn)思路：

• BGR圖像上的絕對(duì)中位差法 + 降噪 + 標(biāo)記點(diǎn)浸染連線 + 圖連通搜索
• numpy + 各種提速技巧

執(zhí)行時(shí)間：

11秒

通過(guò)率：

一般

③因?yàn)楹臅r(shí)還是比較長(zhǎng)，所以第三個(gè)版本主要還是對(duì)第二個(gè)版本的性能改進(jìn)，主要是使用多進(jìn)程分?jǐn)傆?jì)算量，以達(dá)到加速計(jì)算的目的。

實(shí)現(xiàn)思路：

• BGR圖像上的絕對(duì)中位差法 + 降噪 + 標(biāo)記點(diǎn)浸染連線 + 圖連通搜索
• numpy + 各種提速技巧
• 多進(jìn)程并發(fā)計(jì)算

執(zhí)行時(shí)間：

4.3秒

通過(guò)率：

一般

④第四個(gè)版本，我決定在第三個(gè)版本的基礎(chǔ)上，將要檢測(cè)的圖像由BGR圖像轉(zhuǎn)為灰度圖像，一方面可以減少計(jì)算量，另一方面也看能否獲得更好地結(jié)果。

實(shí)現(xiàn)思路：

• BGR圖像轉(zhuǎn)灰度圖像
• 灰度圖像上的絕對(duì)中位差法 + 降噪 + 標(biāo)記點(diǎn)浸染連線 + 圖連通搜索
• numpy + 各種提速技巧
• 多進(jìn)程并發(fā)計(jì)算

執(zhí)行時(shí)間：

3.5秒

通過(guò)率：

略有提升

⑤第五個(gè)版本使用哈里斯角點(diǎn)檢測(cè)算法，替換掉了絕對(duì)中位差法，在標(biāo)記點(diǎn)的檢測(cè)上效果良好，所以降噪的部分也不再需要了。借助于哈里斯角點(diǎn)檢測(cè)算法的優(yōu)異效果，方案的通過(guò)率有了顯著提升。

實(shí)現(xiàn)思路：

• BGR圖像轉(zhuǎn)灰度圖像
• 哈里斯角點(diǎn)檢測(cè) + 標(biāo)記點(diǎn)浸染連線 + 圖連通搜索

檢測(cè)效果和耗時(shí)成正相關(guān)，通過(guò)閾值的調(diào)節(jié)，找一個(gè)比較合適的選擇。

執(zhí)行時(shí)間：

0.9秒

通過(guò)率：

100% (低樣本數(shù))

最終版本的方案我讓朋友幫我測(cè)試過(guò)，共提交了100次，均成功通過(guò)，所以成功率100%？

這個(gè)樣本數(shù)還是偏少了，不確定在1000次、10000次下是不是也能達(dá)到100%，但即便有偏差，應(yīng)該也不會(huì)偏差太多。

來(lái)源：CSDN: https://blog.csdn.net/aaronjny/article/details/110245896