1

直線檢測問題

在紙上畫一條直線，用手機拍下照片，把照片交給計算機識別。

計算機是如何知道這張照片中的這條直線的？

存在直線嗎？

直線在哪里？

點、線、面是基本的幾何元素。

歐幾里得在《幾何原本》中寫道：

直線是點朝一個方向以及反方向的無限平鋪。

一條直線在圖像中，每個人一眼就能看出來。

我們不僅能夠說出圖像中存在一條直線，還可以說出直線經過哪個點，以及直線的方向。

如果有多條直線，我們還能說出直線之間的關系，相交還是(近似)平行，交點在哪里……

計算機怎么識別圖像中的直線？

計算機的常規方法是提取邊緣點，之后檢測直線。

2

灰度矩陣與直線的灰度特征

計算機接收到一張照片，獲得一個對應圖像的灰度矩陣。

矩陣是一格一格的，一格稱為一個像素(pixel)。

矩陣的橫、縱坐標是離散化的。

矩陣中的元素是量化的值，從0到255，該值稱為灰度。

灰度，也稱亮度，是該點受到光照亮度的對應數字。

如果是彩色的照片，對于計算機來說就是3張灰度圖，即3個灰度矩陣。

按順序分別是紅的、綠的和藍的灰度圖。

因為在攝像機成像元件(CCD或CMOS)前面嵌有拜爾濾鏡(如下圖所示)，使得三種顏色(即波長)的光進入到不同的灰度圖中。

顯示時，三種顏色同時顯示，由于紅、綠、藍挨得很近，遠處看就是彩色的。

1975年柯達美國分公司申請了拜爾濾鏡發明專利(US3971065)，1976年獲得授權。

下面是一張灰度圖：

計算機的數據用Matlab軟件顯示出來：

白色直線——灰度呈山峰形貌(黑色直線——灰度呈裂縫形貌)。

下面是兩塊鋼板拼在一起的灰度圖，中間有條直線(接縫)，如何進行識別直線？

3

邊緣檢測原理

首先對灰度矩陣進行邊緣提取。

邊緣就是圖像中灰度值變化大的點，凡是差值大于一定程度就當作邊緣點。

在灰度矩陣中沿著水平方向從左到右移動當前位置，

從第二個像素開始，將該位置左右兩個像素作差分，后者減去前者的灰度差存在另一個結果矩陣中對應當前位置處，直到倒數第二個像素為止，這樣就獲得了水平方向的邊緣點差分結果矩陣。

沿著垂直方向也如此，獲得垂直方向的邊緣點差分結果矩陣。

有人覺得這樣還不能精準找到邊緣點，所以在上述思想上進行了修正，給出了索貝爾(Sobel)方法。

Sobel方法是將如下的左邊小矩陣扣到灰度矩陣上，將上下對應項相乘再相加，得數就是這個中間位置處的水平差分結果，放入到水平差分結果矩陣中存儲，然后移動該小矩陣向右，直到一行都完成這樣的運算，再下移一行進行……直到全部算完，獲得水平結果矩陣。

下方的右邊小矩陣如法炮制，可以獲得垂直結果矩陣。

這是在圖像上進行計算的典型做法——鄰域計算，鄰域計算所用到的上述小矩陣被稱為“算子”。

上面給出的是Sobel算子，分為x方向和y方向兩種算子。

算子不同，得到的處理不同。

下面是Sobel算子與Prewitt算子對比：

在邊緣檢測領域，有roberts算子、canny算子、log算子、laplacian算子……

用不同的算子會得到不同的結果。

如果邊緣點的方向是傾斜的(既不水平也不垂直)，在上述兩個矩陣中就容易不明顯，為了找到這些邊緣點，還需要將上述兩個矩陣進行一個整合。

整合辦法是：

將上述兩個矩陣的對應元素平方和、相加，再開根號，

這樣就得到了全方向的邊緣點差分結果矩陣。

整合公式：

包括了任意方向的灰度差分結果矩陣。

該差分結果矩陣將邊緣點凸顯出來。

接著進行二值化：

將上述邊緣點差分結果矩陣進行二值化：

凡是邊緣點差分大于某個事先預定的值(稱為閾值)就當作邊緣點，設其值為1，非邊緣點設值為0。

從而獲得一個元素值只有1或0的黑白圖像。

下圖為采用Sobel方法進行邊緣提取得到的黑白圖像。

閾值的取值需要慎重：

如果閾值取得過小，會將大量不是邊緣的點當作邊緣點。

如果閾值取得過大，會將大量是邊緣的點忽略掉。

閾值取得過小的結果：

4

最小二乘法

接下來的任務是：

在上述邊緣點黑白圖像中識別出直線。

有一種方法是用于找到多個點的擬合直線的，叫做最小二乘法。

最小二乘法就是找到一條直線，該直線到各點的距離之和最短。

但是這種方法不適用于邊緣點黑白圖中識別直線，

原因是邊緣點有不少存在錯誤，即存在噪點，

一個偏離直線很遠的點可能被錯認為是邊緣點，

而且在直線兩側的點的數量也不一樣多，

都會導致最小二乘法找不出正確的直線。

噪點存在的原因是多方面的，很難沒有一個噪點：

1)光線總是或多或少的照進攝像機；

2)鏡頭畸變，弧面精度有限，玻璃材質均勻程度偏差導致折射率有變化；

3)攝像機電路干擾、電磁影響；

4)邊緣點提取時閾值選擇不當會帶來大量噪點……

因此最小二乘法無法在存在大量錯誤點的情況下找到直線。

5

哈夫變換

大量采用的直線檢測的方法是哈夫變換。

哈夫變換(Hough Transform, 簡稱HT，又譯作霍夫變換)可以找到經過點最多的直線。

在計算機視覺和圖像處理領域，哈夫變換作為一種形狀分析技術被廣泛應用。

哈夫變換是1959年由Paul Hough申請的美國發明專利技術，1962年獲得授權。

Hough發明專利的名稱為：

Method and Means for Recognizing Complex Patterns(用于識別復雜圖案的方法和手段)

拿穿羊肉串打個比方，就是要找到羊肉穿得最多的竹簽。

經過邊緣點最多的直線就是要找的直線。

這個方法可以有效克服噪點的影響，

因為噪點往往不在直線上，噪點的數量一般是少于經過直線上的點的。

如果噪點的數量多于經過直線上的點，是什么情況？

就是人眼也分辨不出該直線了，

這種情況出現在前面的邊緣點提取環節，灰度跳變的閾值選小了。

哈夫變換方法怎么做的呢？

哈夫變換方法是：

利用直線參數方程：

建立一個對應的哈夫空間。

哈夫空間的橫坐標是直線相對于坐標橫軸的角度，

而縱坐標是坐標原點到直線的垂足長度。

這樣一來，每個直角坐標空間的點都對應哈夫空間中的一條正弦曲線，

反之，每個哈夫空間中的點都對應直角坐標空間中的一條直線。

這個變換稱為哈夫變換。

哈夫變換就是直角坐標空間(也稱為笛卡爾空間)與極坐標空間的變換。

哈夫變換將每個邊緣點換算成為哈夫空間的正弦曲線，

多個邊緣點就有多條正弦曲線，

哈夫空間中的這些正弦曲線的交點，

對應于經過了最多點的一條直線。

下圖為哈夫變換得到的哈夫空間結果：

存在一個高聳的塔尖，塔尖這一點的高度就是投票數，說明有最多的點在對應該點的直線上，塔尖這一點在哈夫空間中的角度值、垂足距離值可以首先得到，用參數方程就得到了對應的直線。

在原來邊緣點圖像中找直線的任務，就轉換成在對應的哈夫空間中找最多正弦曲線的交點的任務。

計算機善于找最大值或最小值，

模模糊糊、大約多少的事情計算機不擅長。

如何找最多曲線的交點？

計算機采用投票的方式，

哈夫空間中，正弦曲線經過的每個小格子里都會投上一票，

當所有的邊緣點對應的正弦曲線都畫完，則投票結束，

數數得票數，就找到了得票最多的那個點。

有了這個點，其對應的直線參數也就找到了，

直線也就識別出來了。

直線識別的結果(白線)疊加在原圖上：

之所以劃分很多格子，

是因為計算機只能做量化計算。

每個格子的邊長稱為步長(或周期)。

一個是直線角度的步長，

另一個是垂足距離的步長。

步長越小，計算得越精確，

但是耗時間就越長。

不僅直線可以通過哈夫變換來檢測，圓也可以通過哈夫變換來識別。

凡是能夠有確定的解析式的曲線，也都可以使用哈夫變換的方法來檢測。

哈夫變換還可以識別多條直線、多個圓弧。

哈夫變換是圖像處理中從圖像中識別幾何形狀的基本方法之一。

哈夫變換的基本原理在于利用點與線的對偶性，將原始圖像空間的給定的曲線通過曲線表達形式變為參數空間的一個點，從而把原始圖像中給定曲線的檢測問題轉化為尋找參數空間中的峰值問題。可以適用于直線、橢圓、圓等。

6

哈夫變換教程視頻

來看看哈夫變換的教程視頻：

7

哈夫變換的不足

哈夫變換方法存在一個問題：效率低。

因為哈夫變換方法需要將每個點對應的正弦曲線畫在哈夫空間中，

一個點就要畫出179根線(如果是步長為1度的話)，

每個點都這樣做一遍，

計算量比較大，程序運行耗時長。

因此哈夫變換方法也被人取了一個綽號：咖啡方法。

一杯咖啡慢悠悠地喝完了，

哈夫變換的計算結果才姍姍來遲。

8

哈夫變換改進方法

人們針對哈夫變換方法提出了多種改進措施，

于是產生了隨機哈夫變換、快速哈夫變換、隨機快速哈夫變換等。

在產生了這些改進的哈夫變換后，

原來的哈夫變換就被定義為：

標準哈夫變換。

隨機哈夫變換方法是隨機找邊緣點來進行哈夫變換，

在不斷運行的過程中，就會找到交于一點的直線數量逐漸上升，

當直線數量達到預設的一個數值時，就終止程序，

認為此時已經找到了該直線。

這個方法有一定的風險性，

只要交于一點的直線數量足夠的大就好，

風險雖然仍然存在，但是已經很小。

快速哈夫變換方法是將兩個點一同拿來做哈夫變換。

因為兩點有且僅有一條直線，

因此用該直線在哈夫空間去繪制一個點，

這樣計算量就大大降低了。

原來標準哈夫變換方法需要畫出整條正弦曲線，

兩個點就是兩條正弦曲線，

現在只用在哈夫空間畫出兩個點所在直線的一個點即可。

8

哈夫變換Matlab程序

事先拍攝一張照片，存為灰度圖像，名為a1.bmp，將其放在下面的程序同一個文件夾中。打開Matlab，將下面的程序新建一個腳本文件，運行該文件。

%Hough detection

clear;? ? ? ? ? %清除上次運行的所有變量

close all;? ? ?%關閉上次運行的子窗口

%=====下面讀取原圖并顯示

I1 = imread('a1.bmp');? ? ?%事先有張灰度圖，名為a1.bmp

figure(1),imshow(I1)? ? ? ? ?%將圖像顯示出來

I2 = im2double(I1);? ? ? ? ? %將圖片的數據類型從unit8變為double型，只有這樣回敘才能進行處理

%=====下面進行Sobel方法的邊緣提取并顯示

I_edge = edge(I2,'sobel');? %邊緣提取，采用Sobel方法

figure(2),imshow(I_edge)? ?%將結果圖像顯示出來

%=====輸入源圖像大小

image_y_max=570;

image_x_max = 760;

%=====輸入搜索初始角度

alpha_initial = 100;

%=====輸入搜索步長角度

thelta_step = 1;

%=====輸入搜索總角度范圍

total_angle_for_search = 180;

m = round(total_angle_for_search/thelta_step+1);

%=====初始化hough投票矩陣，未防止計算的lamda距離超出矩陣，設置一個大的矩陣

n=2000;

M_hough=zeros(n,m);

%=====防止距離為負

lamda_initial =round(n/2);

%=====對每個像素操作

for x = 1 : image_x_max - 1

? ? for y = 1 : image_y_max - 1?

%=====轉換為矩陣下標的坐標系

? ? ? ? u = -y + image_y_max;

? ? ? ? v=x;

%=====如果有點，就投票

? ? ? ? if I_edge(u,v) == 1

? ? ? ? %======循環m次，直線旋轉投票

? ? ? ? ? ? for k = 1 : m-1

%=====計算角度

? ? ? ? ? ? ? ? alpha1 = alpha_initial + k*thelta_step;

? ? ? ? ? ? ? ? alpha1 = round(alpha1);

%=====計算距離

? ? ? ? ? ? ? ? lamda1 = x*cos(alpha1*pi/180)+y*sin(alpha1*pi/180);

? ? ? ? ? ? ? ? lamda1 = round(lamda1);? ? ?

? ? ? ? ? ? ?M_hough(lamda_initial + lamda1,k) = M_hough(lamda_initial + lamda1,k) + 1;

? ? ? ? ? ? end

? ? ? ? end

? ? end

end

%=====顯示M_hough矩陣

figure(5),mesh(M_hough);

%======取出最大值所在的行、列

[rm,km]=find(M_hough == max(max(M_hough)))

%=====計算該點原距離

rm = rm - lamda_initial;

%draw the line

%=====計算該點原角度

alpha_line = alpha_initial + km*thelta_step

alpha_line_rad = alpha_line*pi/180;

lamda_line = rm/sin(alpha_line_rad);

%=====在原圖像上重疊畫出該直線

for x=1:image_x_max-1

?%=====直線方程式

? ? y = -x*(1/tan(alpha_line_rad))+lamda_line;

?%=====只畫在圖像中的直線

? ? if y <= image_y_max - 1

? ? ? ? if y >= 1

? ? ? ? ? ? v = x;

? ? ? ? ? ? u = -y + image_y_max;

? ? ? ? ? ? u = round(u);

? ? ? ? ? ? I2(u,v) = 255;

? ? ? ? end

? ? end

end

%=====顯示檢測結果

figure(6),imshow(I2);

關于圖像上的直線檢測，你是否還有更好的辦法呢？

總結

以上是生活随笔為你收集整理的echarts怎么控制一个点沿着折线移动_计算机怎么识别图像中的直线？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。