1 經典橢圓檢測方法
橢圓檢測算法經過多年的研究發展，已經基本形成一個較完整的體系。它們大緻可以分為三類即投票（聚類）、最優化、基于弧段的方法。
投票（聚類）方法
橢圓因為有中心位置坐标、長短軸長度、傾斜角五個參數，标準霍夫變換有較強的魯棒性，但對記憶體要求高，運算效率低，不太現實。霍夫變換類算法以霍夫變換為算法基礎，經過不同國家研究人員多年的不懈努力研究，如今已衍生出很多改進算法，它們各有優劣。随機霍夫變換算法相對标準霍夫變換計算速度有較大提升，但檢測互相遮擋的橢圓時準确度低。
2 随機hough變換橢圓檢測算法
随機橢圓檢測結合使用了了最小二乘法和Hough變換算法。第一步預處理，獲得較理想的邊緣圖。第二步随機選取三個點，取這三點為中心相同大小的鄰域中所有點，用最小二乘法把它們拟合成一個橢圓。如圖2-3所示。第三步從邊緣點中再随機選取第四個點，判斷此點是否在拟合出的圓上。若是，則認為該橢圓是真實橢圓的可能性較大，接着收集證據，驗證該橢圓的真實性。
算法具體過程如下（從第二步開始）：
1.把邊緣檢測得到的點收進集合V中，失敗計數器f初始值設為0。設定5個門檻值，分别是能容忍的失敗次數最大值Tf，檢測進行時對V中邊緣點數量的要求門檻值Tem，随機選取的三點之間兩兩距離最小值Ta，随機選取的第四點到可能橢圓邊界距離的最大值Td，以及橢圓殘缺比率門檻值Tr。
2.np表示集合V中剩餘的點的數量，當np小于Tem時或當失敗次數f大于Tf時停止檢測，算法終止；否則從V中随機取四點，并從V中删除這四點。
3.若用來求解橢圓參數的三個點兩兩之間距離都大于Ta，拟合出橢圓，計算第四個點到該橢圓邊界的距離，若距離小于Td，執行第4步；若不滿足兩者之一，将這四個點傳回到V中，失敗次數加一，回到第2步執行。
4.設E為第3步拟合出來的橢圓，初始化滿足門檻值Td的點的個數num。周遊V中點，計算并判斷它們到橢圓E的邊界的距離是否小于Td，若是則num=num+1，并将該點從V中除去，直到周遊完成。
5.若num>=Tr*K，其中K為橢圓E的周長，那麼跳轉到第6步；否則認為橢圓E不是真實的橢圓，将第4步和第2步中删除的num+4個點傳回V中，并跳轉到第2步。
6.認為橢圓E是一個真實存在的橢圓，f置0，并跳轉到第2步。
3 随機hough變換的優缺點
第一，由于該算法是基于最小二乘法，是以一方面檢測結果往往比真實橢圓小而且對噪聲敏感，但是另一方面當預處理效果較好時檢測精度很高。
第二，由于該算法基于随機采樣，是以一方面可能會有所選點距離較近的情況造成拟合出的橢圓偏差較大，但是另一方面因為随機采樣的靈活性檢測速度提升了。
第三，一方面當參數選取的較好時檢測又快有準确；另一方面，由于該算法嚴格由參數Ta，Td，Tr控制而且這些參數不易取到合适值，是以會出現不合适的參數不僅增加計算量，而且增加誤檢機會的情況。
最優化方法
最優化類方法優點在其精度上，缺點是其一次隻能處理一個圖形，即此前要對圖像資訊進行分類分離。AndrewFitzgibb等人提出了直接最小二乘法橢圓拟合算法。該方法能保證拟合出來的一定是橢圓。但該方法受到孤立點和噪聲點的影響。目前最優化算法多與其他算法一起結合使用。
基于弧段的方法
基于邊界聚類的橢圓檢測方法結合使用了基于弧段的方法和最小二乘法。從邊界圖提取圓弧，再經過過濾、聚類，最終用最小二乘法拟合出橢圓。該方法能有效應對多個橢圓、橢圓互相遮擋和橢圓部分缺損等複雜情況，因而引起了廣泛的注意。
邊界聚類算法流程
邊界聚類算法屬于從下往上結構的算法。算法步驟主要分為三步，分别是預處理，邊界聚類和直接最小二乘法拟合橢圓三個過程。流程圖如下所示：
第四步是二值化。二值化的效果幾乎完全取決于分割門檻值的選取。是以自動尋找最佳分割門檻值的方法就顯得十分關鍵。找到圖檔二值化的一個合适的分割門檻值的一種方法是按圖像的灰階特性,将圖像分成背景和目标兩部分,背景和目标之間的類間方差最大的分割意味着錯分機率最小。MATLAB 的Graythresh函數就是使用該方法來獲得一個自适應門檻值作為二值化的分割依據。
第五步，二值化後，因為橢圓弧附近的非相關像素會嚴重影響檢測結果，是以為了大幅度減少非相關像素，本文用形态學的腐蝕操作來得到細化的邊界。
邊界像素連接配接
采用Kovesi的邊界連接配接算法，以8-鄰域連通準則從上至下，從左至右掃描二值圖像，将邊界像素連接配接為有向邊界列。然後采用邊界列中像素數門檻值條件去除像素數較小的集合。因為若邊界列像素數少于門檻值數，則很有可能是噪聲或背景，應當删除。具體步驟如下：
1.以8-鄰域連通準則從上至下，從左至右掃描二值圖像，按連通區域對圖像中的像素點聚類。
2.尋找每一個連通域中邊界像素中所有的結束點和分叉點（分叉點是三條以上曲線的交點）并存儲。
3.以這些結束點和分叉點為結束标志，讓每一個連通域中的像素點集合分割為遇到結束點和連接配接點就斷開的小集合。
4.删除這些集合中像素數小于某一門檻值的部分。
線段列提取
因為圖像光栅化難以獲得準确的切線，而後續過程需要用到圓弧的切線，是以要進行線段拟合，即用多段折線代替原來的圓弧。具體步驟如下：
1.取邊界像素連接配接成的第i條有向邊界列，判斷是否超過邊界列總數目total，若不是進行步驟2，若是終止算法。
2.判斷該邊界列是否已經完成處理，若為否則進行第3步；若是則i=i+1，重新進行步驟2.
3.從其中第三個點開始，計算第一個點到這個點(記為點j)的連線方程，并依次判斷第一個點和該點之間的所有點到該連線的距離，若所有距離均小于某一門檻值，則j=j+1，重新進行步驟3，否則該有向邊界列從該處斷開，前面部分隻保留第一個點和第j個點，前面j個點構成的連線用第一點和第j點之間的直線連線代替；後面部分仍然記為邊界列i，
4.判斷步驟3中斷開的有向邊界列後面部分像素數是否小于某門檻值，若是則删除掉，否則不處理。最後跳轉到步驟1。
完成這一個過程後一個連通域的的像素點構成的曲線就變成了其中部分像素點構成的一條折線。經過這個過程雖然像素資訊損失了一部分，但是求取圓弧切線的精度從某種意義上說提高了，因為沒有了光栅化效應。而且資料少了處理變得簡單。再采用線段數門檻值條件去除較短的線段列。若線段數數少于門檻值數，則很有可能是噪聲或背景或者進行拟合時誤差過大，是以須删除。
線段列旋轉方向統一
本文将所有線段列旋轉方向統一為逆時針方向。
假設圖3-4中的黑點為線段列中的點，箭頭代表線段列的方向，P1（x1,y1），P2(x2,y2)，P3(x3,y3)為線段列中連續的三個像素，像素都引入z坐标，且令其為0，則P1（x1,y1，0），P2(x2,y2，0)，P3(x3,y3，0)，空間向量
圓弧聚類
圓弧聚類是将屬于同一橢圓但是分開的兩條或多條橢圓弧進行聚類。在進行聚類前，首先要判斷弧段的完整度。一般用弧段的首尾端點P1，P3與中點P2構成的兩向量P2P1，P2P3的夾角的大小來進行判斷。夾角越小，一般該橢圓弧越完整，夾角越大，一般認為橢圓弧缺損越嚴重。設定一個門檻值，當夾角小于該門檻值時認為該弧段已經足夠完整，僅僅靠該弧段上的點就可以較準确地拟合出真實存在的橢圓，是以該弧段不需要參與後面的聚類過程。如果希望該門檻值自适應，在劃分待聚類橢圓弧和不須聚類的弧（較完整弧）之前，先要确定該門檻值。用直接最小二乘法拟合該弧所在的橢圓，若較圓，為了減小的誤差，應使門檻值夾角稍微大一些，如90度；若該弧所在的橢圓較扁，應使門檻值夾角稍微小一些，如60度。接下來才根據該自适應門檻值進行對圓弧判斷。當大于門檻值時認為該弧段上的點過少，不足以拟合出準确的橢圓，需要找到和該弧段屬于同一橢圓的弧段然後用它們所有的點一起拟合出一個橢圓。經過此判斷過程，橢圓弧就被分成兩組。把需要參加聚類的橢圓弧按照含點數的數目由多到少進行排列，下面的過程都按照數目多的弧段優先的順序進行。
對于待聚類的橢圓弧，先要定義其搜尋區域，由于橢圓是封閉圖形，是以整個橢圓可以确定是在其任何一部分弧和弧兩端點的切線所在的射線包圍起來的區域裡面，屬于該橢圓的其他弧以确定是在該弧對應的弦和弧兩端點的切線所在的射線包圍起來的區域裡面。這就是我們搜尋的區域。在圖中a1的搜尋區域也就是射線l1,l2,弦l3和圖像邊緣範圍内的區域，在這個區域裡面找弧，可以縮小搜尋的範圍，提高效率。判斷一條弧是否在待聚類橢圓弧的搜尋區域裡面我們隻需取這條弧的首末端點j3,j4是否在搜尋區域。方法是分别求過這兩點同時平行于待聚類橢圓弧對應弦l3的直線和切線的交點，若交點分别有兩個，交點都在射線上且這兩個端點在對應兩個交點之間則該弧段在搜尋區域内。圖中明顯a2,a3,a4在a1的搜尋區域内而a5不在。
如上圖（a）中的參與拟合的點較多都落在拟合的橢圓上，是以有較大可能滿足限制二條件；（b）中大多數拟合點點離拟合出的橢圓邊界有一定距離，有較大可能不滿足限制條件二。
如果希望這兩個門檻值改為自适應的，方法是先拟合出橢圓，判斷橢圓大小。若橢圓較小，應适當降低限制，即增大距離門檻值，減小比例門檻值；若橢圓較大，應适當提高限制，即減小距離門檻值，增大比例門檻值。本算法中選取的是，若橢圓的短軸小于50則距離門檻值為0.05,比例門檻值設為0.7;否則前者取0.03,後者取0.8。
再配對
聚類後的弧和較完整弧或者兩個較完整弧可能屬于同一橢圓但是在前面的步驟它們隻是被分開了并沒有配對，是以有必要增加再比對過程，增加檢測準确度。比對方法還是限制條件二的方法。因為該方法和原算法的去僞過程相似，是以經過該方法後無需再去僞。
直接最小二乘法橢圓拟合
前面的很多步驟都删除了像素點較少的集合，或者用少數點代替了邊界列中的很多點，或者是分割後再删除點數較少的集合的，這些操作到橢圓拟合這一步實際上基本上去除了所有的背景和噪聲，甚至包括一部分有用資訊。是以即使對噪聲和孤立點敏感的直接最小二乘法也可以用來拟合橢圓，而且因為該方法對橢圓缺損不敏感，是以非常适合。
1 matlab版本
2014a
2 參考文獻
[1] 蔡利梅.MATLAB圖像處理——理論、算法與執行個體分析[M].清華大學出版社，2020.
[2]楊丹,趙海濱,龍哲.MATLAB圖像處理執行個體詳解[M].清華大學出版社，2013.
[3]周品.MATLAB圖像處理與圖形使用者界面設計[M].清華大學出版社，2013.
[4]劉成龍.精通MATLAB圖像處理[M].清華大學出版社，2015.