此系列的其他文章：
OpenCV算法學習筆記之初識OpenCV
OpenCV算法學習筆記之幾何變換
OpenCV算法學習筆記之對比度增強
OpenCV算法學習筆記之平滑算法
OpenCV算法學習筆記之閾值分割
OpenCV算法學習筆記之形態(tài)學處理
OpenCV算法學習筆記之邊緣檢測（一）
OpenCV算法學習筆記之邊緣處理（二）

更多文章可以訪問我的博客Aengus | Blog

霍夫直線檢測

原理

對于?中的任意一條直線元媚，我們以下圖為例：

xoy平面中的直線

?是直線的正切角罢防，?是直線的截距，?是原點的直線的垂線晰洒，?幔荒；則直線的方程可以用以下方程表示：

所以如果知道平面內(nèi)的一條直線糊闽，那么可以計算出唯一的?和?梳玫，使得此直線與?一一對應，所以我們就完成了?平面中的直線到霍夫空間的映射墓怀。因此如果我們想判斷?平面上一連串的點?是否在一條直線上汽纠，只需判斷他們映射在?平面上的曲線?是否相交于一個點即可，如果相交于一點傀履，則共線。

而對于較為復雜的情況莉炉，可能會出現(xiàn)點?所對應的?平面上的曲線有多個相交點的情況钓账，針對這種問題，我們可以設(shè)置一個投票器絮宁，選擇相交曲線最多的點梆暮，那么這些相交曲線所對應的?即是共線的。

API

OpenCV對二值圖提供霍夫檢測函數(shù)：

void HoughLines(InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn=0, double stn=0)

其中rho代表的步長（分辨率）绍昂，theta代表的步長（分辨率）啦粹，這是因為平面中有無數(shù)個點，而計算機實現(xiàn)時只能取有限個點窘游，所以需要指定步長唠椭，像素為單位，一般取1忍饰；threshold代表投票器的閾值贪嫂，只有大于這個值才會被認為在一條線上；而srn與stn則分別是多通道圖片的rho和theta艾蓝。

標準霍夫直線檢測內(nèi)存消耗較大力崇，執(zhí)行時間也比較短，采用概率霍夫直線檢測可以緩解這一問題赢织，它隨機地從邊緣二值圖中選擇前景像素點亮靴，確定檢測直線的兩個參數(shù)，本質(zhì)上還是標準的霍夫直線檢測于置。其函數(shù)為：

void HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLenght=0, double maxLineGap=0)

其中minLineLenght代表最短直線的長度茧吊；maxLineGap代表同一直線上的兩個點所允許的最大間隙。

霍夫圓形檢測

標準霍夫圓形檢測

原理

標準霍夫圓形檢測的思想與霍夫直線檢測類似俱两。

霍夫圓形檢測的問題可以簡述為：已知平面上的點在多個圓上饱狂，那么哪些點在同一個圓上，并計算出圓心坐標宪彩。

上述問題可以通過此步驟解決：首先固定一個半徑休讳，然后分別以點為圓心，為半徑畫圓尿孔，若在同一個圓上俊柔，那么以它們?yōu)閳A心畫的圓的交點就是所求圓的圓心筹麸，且其半徑就是。具體實現(xiàn)時雏婶，可以首先確定一個的范圍物赶，然后依次畫圓并按照霍夫直線檢測的思想對交點進行投票，票數(shù)最多的即為目標圓圓心坐標留晚，此時的為目標圓半徑酵紫。

平面中的任意一個圓都可以表示為，可以利用圓的極坐標公式對圓心進行計算错维。

Python實現(xiàn)

def hough_circle(image, min_r, max_r, vote_thresh=100):
    """
    :param image 輸入圖像
    :param min_r 最小半徑
    :param max_r 最大半徑
    :param vote_thresh 投票閾值奖地，小于此值則將此目標圓丟棄
    :return 包含目標圓(半徑，橫坐標赋焕，縱坐標)的list
    """
    # 寬参歹，高
    h, w = image.shape
    # 歸為整數(shù)
    minr = round(min_r) + 1
    maxr = round(max_r) + 1
    # 初始化三維計數(shù)器
    r_num = int(maxr - minr + 1)    # 半徑
    a_num = int(w - 1 + maxr + maxr + 1)    # 圓心橫坐標
    b_num = int(h - 1 + maxr + maxr + 1)    # 圓心縱坐標
    accumulator = np.zeros((r_num, b_num, a_num), np.int32)
    # 投票計數(shù)
    for y in range(h):
        for x in range(w):
            if image[y][x] == 255: # 只對邊緣進行霍夫變換
                for k in range(r_num):
                    for theta in np.linspace(0, 360, 180):
                        # 計算對應的a,b
                        a = x - (minr+k)*math.cos(theta/180.0*math.pi)
                        b = y - (minr+k)*math.sin(theta/180.0*math.pi)
                        # 取整
                        a = int(round(a))
                        b = int(round(b))
                        # 投票
                        accumulator[k, b, a] += 1
    # 篩選投票數(shù)大于vote_thresh的圓
    circles = []
    for k in range(r_num):
        for b in range(b_num):
            for a in range(a_num):
                if accumulator[k, b, a] > vote_thresh:
                    circles.append((k+minr, b, a))
    return circles

基于梯度的霍夫圓形檢測

原理

如果已知圓幾條切線的方向，那么對其做垂線隆判，垂線相交的點即是圓的圓心犬庇。通過這種方法，若得到一張圖邊緣二值圖侨嘀，對其中的直線做垂線就可以得到目標圓的圓心臭挽。對于的確認，也可以通過“投票”的思想飒炎，如果條切線距離圓心的距離為埋哟，條切線距離圓心的距離為，有郎汪，就以作為最終的半徑赤赊。

API

OpenCV提供函數(shù):

void HoughCircles(InputArray image, OutputArray circles, int method, double dp, double minDist, double param1=100, double param2=100, int minRadius=0, int maxRadius=0)

其中circles是一個vector<Vec3f>，每一個都代表煞赢；mehod目前只有CV_HOUGH_GRADIENT抛计，代表梯度；dp是計數(shù)器分辨率照筑；minDsit是圓心間的最小距離吹截；param1是Canny邊緣檢測的雙閾值中的高閾值，低閾值默認是高閾值的一半凝危；param2代表最小投票數(shù)波俄；minRadius是需要檢測的圓的最小半徑；maxRadius是需要檢測圓的最大半徑蛾默。

角點檢測

角點可以簡單的認為是兩條線的交點懦铺，也就是一個物體的“角”。角點處的梯度值和梯度變化率都十分明顯支鸡，所以這也是大部分角點檢測算法入手的地方冬念。

Harris角點檢測

原理

Harris角點檢測就是利用角點的梯度值變化較大的這個特點進行檢測趁窃。

其步驟如下：

步驟一：計算分別圖像在水平方向和垂直方向上的梯度與：

步驟二：計算兩個梯度方向上的乘積，注意代表點乘：

步驟三：使用高斯函數(shù)對進行高斯加權(quán)（取急前，ksize=3）醒陆，計算中心點為的窗口對應的協(xié)方差矩陣：

則；

步驟四：計算每個像素點處的Harris響應值（為經(jīng)驗參數(shù)）：

步驟五：過濾大于某一閾值的Harris響應值裆针，得到的結(jié)果就是角點刨摩；

API

OpenCV提供函數(shù)：

void cornerHarris(InputArray src, OutputArray dst, int blockSize, int ksize, double k, int borderType = BORDER_DEFAULT)

實現(xiàn)Harris角點檢測，其中blockSize代表滑塊窗口的尺寸据块，也就是窗口的尺寸码邻；ksize代表Sobel核的大小，所以此API會對圖像進行Sobel邊緣檢測另假；k是Harris中間參數(shù)，經(jīng)驗值0.04~0.06怕犁。

Shi-Tomasi角點檢測

原理

Shi-Tomasi 算法是Harris 算法的改進边篮，主要不同在最后兩個步驟中，Harris 算法最原始的定義是將矩陣 M 的行列式值與 M 的跡相減奏甫，再將差值同預先給定的閾值進行比較戈轿。后來Shi 和Tomasi 提出改進的方法，若兩個特征值中較小的一個大于最小閾值阵子，則會得到強角點思杯。Shi 和Tomasi 的方法比較充分，并且在很多情況下可以得到比使用Harris 算法更好的結(jié)果挠进。

API

OpenCV提供函數(shù)：

void goodFeaturesToTrack(InputArray image, OutputArray corners, int maxCorners, double qualityLevel, double minDistance, InputArray mask=noArray(), int blockSize=3, bool useHarrisDetector=false, double k=0.04);

其中maxCorners代表可以檢測到的最大角點數(shù)量色乾；qualityLevel代表檢測到的角點的質(zhì)量等級，角點特征值小于qualityLevel最大特征值的點將被舍棄领突；minDistance是兩個角點間最小間距暖璧，以像素為單位；mask是指定檢測區(qū)域君旦，若檢測整幅圖像澎办，mask置為空Mat()；blockSize是計算協(xié)方差矩陣時窗口大薪鹂场局蚀；useHarrisDetector是否使用Harris角點檢測，為false恕稠，則使用Shi-Tomasi算子琅绅；k留給Harris角點檢測算子用的中間參數(shù)，一般取經(jīng)驗值0.04~0.06谱俭，useHarrisDetector=false時奉件，該參數(shù)不起作用宵蛀。

參考

《OpenCV算法精解——基于Python和C++》（張平）第九章

角點檢測詳細總結(jié)及代碼示例

第十一節(jié)、Harris角點檢測原理(附源碼)

OpenCV——角點檢測原理分析（Harris县貌，Shi-Tomasi术陶、亞像素級角點檢測）