圖劃分演算法

Ⅰ 什麼是圖像分割

1 數字圖像處理技術是一個跨學科的領域。隨著計算機科學技術的不斷發展，圖像處理和分析逐漸形成了自己的科學體系，新的處理方法層出不窮，盡管其發展歷史不長，但卻引起各方面人士的廣泛關注。首先，視覺是人類最重要的感知手段，圖像又是視覺的基礎，因此，數字圖像成為心理學、生理學、計算機科學等諸多領域內的學者們研究視覺感知的有效工具。其次，圖像處理在軍事、遙感、氣象等大型應用中有不斷增長的需求。

基於圖論的圖像分割技術是近年來國際上圖像分割領域的一個新的研究熱點。該方法將圖像映射為帶權無向圖，把像素視作節點。利用最小剪切准則得到圖像的最佳分割 該方法本質上將圖像分割問題轉化為最優化問題。是一種點對聚類方法。對數據聚類也具有很好的應用前景。但由於其涉及的理論知識較多，應用也還處在初級階段。因此國內這方面的研究報道並不多見，本文將對圖論方法用於圖像分割的基本理論進行簡要介紹，並對當前圖論方法用於圖像分割的最新研究進展進行綜述，並著重介紹基於等周圖割的圖像分割的方法。

2 圖像目標分割與提取技術綜述

圖像分割是一種重要的圖像技術，在理論研究和實際應用中都得到了人們的廣泛重視。圖像分割的方法和種類有很多，有些分割運算可直接應用於任何圖像，而另一些只能適用於特殊類別的圖像。有些演算法需要先對圖像進行粗分割，因為他們需要從圖像中提取出來的信息。例如，可以對圖像的灰度級設置門限的方法分割。值得提出的是，沒有唯一的標準的分割方法。許多不同種類的圖像或景物都可作為待分割的圖像數據，不同類型的圖像，已經有相對應的分割方法對其分割，同時，某些分割方法也只是適合於某些特殊類型的圖像分割。分割結果的好壞需要根據具體的場合及要求衡量。圖像分割是從圖像處理到圖像分析的關鍵步驟，可以說，圖像分割結果的好壞直接影響對圖像的理解。

3 定義及分割方法
為後續工作有效進行而將圖像劃分為若干個有意義的區域的技術稱為圖像分割(Image Segmentation)
目前,有許多的圖像分割方法,從分割操作策略上講,可以分為基於區域生成的分割方法,基於邊界檢測的分割方法和區域生成與邊界檢測的混合方法.

Ⅱ 如何在matlab中進行圖像的網格劃分。

可以使用meshgrid函數

meshgrid是MATLAB中用於生成網格采樣點的函數。在使用MATLAB進行3-D圖形繪制方面有著廣泛的應用，函數效果如下圖所示：

函數功能：

生成繪制3-D圖形所需的網格數據。在計算機中進行繪圖操作時， 往往需要一些采樣點，然後根據這些采樣點來繪制出整個圖形。在進行3-D繪圖操作時，涉及到x、y、z三組數據，而x、y這兩組數據可以看做是在Oxy平面內對坐標進行采樣得到的坐標對(x, y)

例如， 要在「3<=x<=5，6<=y<=9，z不限制區間」 這個區域內繪制一個3-D圖形，如果只需要整數坐標為采樣點的話。可能需要下面這樣一個坐標構成的矩陣：

(3,9),(4,9),(5,9);

(3,8),(4,8),(5,8);

(3,7),(4,7),(5,7);

(3,6),(4,6),(5,6);

在matlab中可以這樣描述這個坐標矩陣：

把各個點的x坐標獨立出來，得：

3,4,5;

3,4,5;

3,4,5;

3,4,5;

再把各個點的y坐標也獨立出來：

9,9,9;

8,8,8;

7,7,7;

6,6,6;

這樣對應的x、y結合，便表示了上面的坐標矩陣。meshgrid就是產生這樣兩個矩陣，來簡化我們的操作。然後根據(x, y)計算獲得z，並繪制出三維圖形。

在Matlab命令窗口中鍵入type meshgrid可以查看該函數的源代碼（由此可以理解meshgrid的演算法思想）， 鍵入doc meshgrid或者help meshgrid可以獲得幫助文檔。

語法

[X,Y] =meshgrid(x,y)

meshgrid返回的兩個矩陣X、Y必定是行數、列數相等的，且X、Y的行數都等於輸入參數y中元素的總個數，X、Y的列數都等於輸入參數x中元素總個數（這個結論可以通過查看meshgrid的源代碼得到，可以通過示常式序得到驗證）。

[X,Y]=meshgrid(x)與[X,Y]=meshgrid(x,x)是等同的

[X,Y,Z]=meshgrid(x,y,z)生成三維數組，可用來計算三變數的函數和繪制三維立體圖

相關函數： plot3、mesh、surf、automesh、ndgrid

Ⅲ 選擇性搜索演算法 （Selective Search)

計算機視覺領域有幾個基本的任務：

object detection 的基礎是 object recognition，只不過要先將圖片進行分割，對每個分割之後的子圖區域 region （也稱為 patch） 進行 object recognition.

由於事先並不知道物體在圖片的哪個位置，為了避免漏檢，我們應該對圖片中盡量多的 region 進行搜索。理論上來說，可以有無窮多個 region。這里就需要一種 region proposal 的演算法，以比較高效的方式提出圖片劃分 region 的方式，從而加速整個 object detection 的過程並且提高准確率。

本文將要介紹的 selective search 演算法 ，是比較經典的，也是 R-CNN 中使用的 region proposal 演算法。

參考文獻：

為了避免蠻力搜索，selective search 演算法首先需要一個基於像素的圖像分割。這里用的是 Felzenszwalb and Huttenlocher 演算法 （因為是當時速度最快的演算法，而且是公開的），得到一個 oversegmented 的圖像分割。例如：

這里之所以用 oversegmented 圖像，是為了得到盡可能細分的區域，再以此為基礎逐步合並，形成更大的區域。

image segmentation 可以用作 region proposal 的基礎，每個分割的區域都可以看作一個潛在的 region，但是一個 object 往往包含了多個分割的區域，例如盛有咖啡的杯子，咖啡和杯子應該作為一個整體來看待。因此，還要根據某種相似性原則進行分割區域的合並，得到更大范圍的 region。

Selective search 演算法考慮了 4 種相似性度量，取值都在 [0,1] 之間，越大越相似。

最終的相似性度量是上述四個度量的組合：

其中 取 0 或 1.

總結起來，selective search 的演算法步驟非常簡單：

環境配置：

具體程序：

最後效果如下：

顯示的 100 個 region 已經包含了我們感興趣的待檢測區域，說明了 selective search 演算法的高效。