越來越多的移動(dòng)計(jì)算設(shè)備都開始攜帶照相機(jī)鏡頭，這對(duì)于攝影界來說是一個(gè)好事情，不僅如此攜帶鏡頭也為這些設(shè)備提供了更多的可能性。除了最基本的拍攝功能，結(jié)合合適的軟件這些更為強(qiáng)大的硬件設(shè)備可以像人腦一樣理解它看到了什么。
僅僅具備一點(diǎn)點(diǎn)的理解能力就可以催生一些非常強(qiáng)大的應(yīng)用，比如說條形碼識(shí)別，文檔識(shí)別和成像，手寫文字的轉(zhuǎn)化，實(shí)時(shí)圖像防抖，增強(qiáng)現(xiàn)實(shí)等。隨著處理能力變得更加強(qiáng)大，鏡頭保真程度更高，算法效率更好，機(jī)器視覺 (machine vision) 這個(gè)技術(shù)將會(huì)解決更加重大的問題。
有些人認(rèn)為機(jī)器視覺是個(gè)非常復(fù)雜的領(lǐng)域，是程序員們的日常工作中絕不會(huì)遇到的。我認(rèn)為這種觀點(diǎn)是不正確的。我發(fā)起了一個(gè)開源項(xiàng)目 GPUImage，其實(shí)在很大程度上是因?yàn)槲蚁胩剿饕幌赂咝阅艿臋C(jī)器視覺是怎么樣的，并且讓這種技術(shù)更易于使用。
GPU 是一種理想的處理圖片和視頻的設(shè)備，因?yàn)樗菍ｉT為并行處理大量數(shù)據(jù)而生的，圖片和視頻中的每一幀都包含大量的像素?cái)?shù)據(jù)。在某些情況下 GPU 處理圖片的速度可以是 CPU 的成千上百倍。
在我開發(fā) GPUImage 的過程中我學(xué)到了一件事情，那就是即使是圖片處理這樣看上去很復(fù)雜的工作依然可以分解為一個(gè)個(gè)更小更簡(jiǎn)單的部分。這篇文章里我想將一些機(jī)器視覺中常見的過程分解開來，并且展示如何在現(xiàn)代的 GPU 設(shè)備上讓這些過程運(yùn)行地更快。
以下的每一步在 GPUImage 中都有完整的實(shí)現(xiàn)，你可以下載包含了 OS X 和 iOS 版本的示例工程 FilterShowcase，在其中體驗(yàn)一下各個(gè)功能。此外，這些功能都有基于 CPU (有些使用了 GPU 加速) 的實(shí)現(xiàn)，這些實(shí)現(xiàn)是基于 OpenCV 庫(kù)的，在另一片文章中 Engin Kurutepe 詳細(xì)地講解了這個(gè)庫(kù)。
我將要描述的第一種操作事實(shí)上在濾鏡方面的應(yīng)用比機(jī)器視覺方面更多，但是從這個(gè)操作講起是比較合適的。索貝爾邊界探測(cè)用于探測(cè)一張圖片中邊界的出現(xiàn)位置，邊界是指由明轉(zhuǎn)暗的突然變化或者反過來由暗轉(zhuǎn)明的區(qū)域[1]。在被處理的圖片中一個(gè)像素的亮度反映了這個(gè)像素周圍邊界的強(qiáng)度。
下面是一個(gè)例子，我們來看看同一張圖片在進(jìn)行索貝爾邊界探測(cè)之前和之后：
http://wiki.jikexueyuan.com/project/objc/images/21-31.png" alt="" />
http://wiki.jikexueyuan.com/project/objc/images/21-32.png" alt="" />
正如我上面提到的，這項(xiàng)技術(shù)通常用來實(shí)現(xiàn)一些視覺效果。如果在上面的圖片中將顏色進(jìn)行反轉(zhuǎn)，最明顯的邊界用黑色代表而不是白色，那么我們就得到了一張類似鉛筆素描效果的圖片。
http://wiki.jikexueyuan.com/project/objc/images/21-33.png" alt="" />
那么這些邊界是如何被探測(cè)出來的？第一步這張彩色圖片需要減薄成一張亮度 (灰階) 圖。Janie Clayton 在她的文章中解釋了這一步是如何在一個(gè)片斷著色器 (fragment shader) 中完成的。簡(jiǎn)單地說這個(gè)過程就是將每個(gè)像素的紅綠藍(lán)部分加權(quán)合為一個(gè)代表這個(gè)像素亮度的值。
有的視頻設(shè)備和相機(jī)提供的是 YUV 格式的圖片，而不是 RGB 格式。YUV 這種色彩格式已經(jīng)將亮度信息 (Y) 和色度信息 (UV) 分離，所以如果原圖片是這種格式，顏色轉(zhuǎn)換這個(gè)步驟就可以省略，直接用其中亮度的部分就可以。
圖片一旦減薄到僅剩亮度信息，一個(gè)像素周圍的邊界強(qiáng)度就可以由它周圍 3*3 個(gè)臨近像素計(jì)算而得。在一組像素上進(jìn)行圖片處理的計(jì)算過程涉及到一個(gè)叫做卷積矩陣 (參考：convolution matrix) 的東西。卷積矩陣是一個(gè)由權(quán)重?cái)?shù)據(jù)組成的矩陣，中心像素周圍像素的亮度乘以這些權(quán)重然后再相加就能得到中心像素的轉(zhuǎn)化后數(shù)值。
圖片上的每一個(gè)像素都要與這個(gè)矩陣計(jì)算出一個(gè)數(shù)值。在處理的過程中像素的處理順序是無關(guān)緊要的，所以這種計(jì)算很容易并行運(yùn)行。因此，這個(gè)計(jì)算過程可以通過一個(gè)片斷著色器的方式運(yùn)行在可編程的 GPU 上，來極大地提高處理效率。正如在 Janie 的文章中所提到的，片斷著色器是一些 C 語言風(fēng)格的程序，運(yùn)行在 GPU 上可以進(jìn)行一些非?？焖俚膱D片處理。
下面這個(gè)是索貝爾算子的水平處理矩陣：
| ?1 | 0 | +1 |
| ?2 | 0 | +2 |
| ?1 | 0 | +1 |
為了進(jìn)行某一個(gè)像素的計(jì)算，每一個(gè)臨近像素的亮度信息都要讀取出來。如果要處理的圖片已經(jīng)被轉(zhuǎn)化為灰階圖，亮度可以從紅綠藍(lán)任意顏色通道中抽樣。臨近像素的亮度乘以矩陣中對(duì)應(yīng)的權(quán)重，然后加到最終值里去。
在一個(gè)方向上尋找邊界的過程是這樣的：轉(zhuǎn)化之后對(duì)比一個(gè)像素左右兩邊像素的亮度差。如果當(dāng)前這個(gè)像素左右兩邊的像素亮度相同也就是說在圖片上是一個(gè)柔和的過度，它們的亮度值和正負(fù)權(quán)重會(huì)相互抵消，于是這個(gè)區(qū)域不會(huì)被判定為邊界。如果左邊像素和右邊像素的亮度差別很大也就是說是一個(gè)邊界，用其中一個(gè)亮度減去另一個(gè)，這種差異越大這個(gè)邊界就越強(qiáng) (越明顯)。
索貝爾過程有兩個(gè)步驟，首先是水平矩陣進(jìn)行，同時(shí)一個(gè)垂直矩陣也會(huì)進(jìn)行，這個(gè)垂直矩陣中的權(quán)重如下
| ?1 | ?2 | ?1 |
| 0 | 0 | 0 |
| +1 | +2 | +1 |
兩個(gè)方向轉(zhuǎn)化后的加權(quán)和會(huì)被記錄下來，它們的平方和的平方根也會(huì)被計(jì)算出來。之所以要進(jìn)行平方是因?yàn)橛?jì)算出來的值可能是正值也可能是負(fù)值，但是我們需要的是值的量級(jí)而不關(guān)心它們的正負(fù)。有一個(gè)好用內(nèi)建的 GLSL 函數(shù)能夠幫助我們快速完成這個(gè)過程。
最終計(jì)算出來的這個(gè)值會(huì)用來作為輸出圖片中像素的亮度。因?yàn)樗髫悹査阕訒?huì)突出顯示兩邊像素亮度的不同的地方，所以圖片中由明轉(zhuǎn)暗或者相反的突然轉(zhuǎn)變會(huì)成為結(jié)果中明亮的像素。
索貝爾邊界探測(cè)有一些相似的變體，例如普里維特 (Prewitt) 邊界探測(cè)[2]。普里維特邊界探測(cè)會(huì)在橫向豎向矩陣中使用不同的權(quán)重，但是它們運(yùn)作的基本過程是一樣的。
作為索貝爾邊界探測(cè)如何用代碼實(shí)現(xiàn)的一個(gè)例子，下面是用 OpenGL ES 進(jìn)行索貝爾邊界探測(cè)的片斷著色器：
precision mediump float;
varying vec2 textureCoordinate;
varying vec2 leftTextureCoordinate;
varying vec2 rightTextureCoordinate;
varying vec2 topTextureCoordinate;
varying vec2 topLeftTextureCoordinate;
varying vec2 topRightTextureCoordinate;
varying vec2 bottomTextureCoordinate;
varying vec2 bottomLeftTextureCoordinate;
varying vec2 bottomRightTextureCoordinate;
uniform sampler2D inputImageTexture;
void main()
{
float bottomLeftIntensity = texture2D(inputImageTexture, bottomLeftTextureCoordinate).r;
float topRightIntensity = texture2D(inputImageTexture, topRightTextureCoordinate).r;
float topLeftIntensity = texture2D(inputImageTexture, topLeftTextureCoordinate).r;
float bottomRightIntensity = texture2D(inputImageTexture, bottomRightTextureCoordinate).r;
float leftIntensity = texture2D(inputImageTexture, leftTextureCoordinate).r;
float rightIntensity = texture2D(inputImageTexture, rightTextureCoordinate).r;
float bottomIntensity = texture2D(inputImageTexture, bottomTextureCoordinate).r;
float topIntensity = texture2D(inputImageTexture, topTextureCoordinate).r;
float h = -bottomLeftIntensity - 2.0 * leftIntensity - topLeftIntensity + bottomRightIntensity + 2.0 * rightIntensity + topRightIntensity;
float v = -topLeftIntensity - 2.0 * topIntensity - topRightIntensity + bottomLeftIntensity + 2.0 * bottomIntensity + bottomRightIntensity;
float mag = length(vec2(h, v));
gl_FragColor = vec4(vec3(mag), 1.0);
}上面這段著色器中中心像素周圍的像素都有用戶定義的名稱，是由一個(gè)自定義的頂點(diǎn)著色器提供的，這么做可以優(yōu)化減少對(duì)移動(dòng)設(shè)備環(huán)境的依賴。從 3*3 網(wǎng)格中抽樣出這些命名了的像素，然后用自定義的代碼來進(jìn)行橫向和縱向索貝爾探測(cè)。為簡(jiǎn)化計(jì)算權(quán)重為 0 的部分會(huì)被忽略。GLSL 函數(shù) length() 計(jì)算出水平和垂直矩陣轉(zhuǎn)化后值的平方和的平方根。然后這個(gè)代表量級(jí)的值會(huì)被拷貝進(jìn)輸出像素的紅綠藍(lán)通道中，這樣就可以用來代表邊界的明顯程度。
索貝爾邊界探測(cè)可以給你一張圖片邊界強(qiáng)度的直觀印象，但是并不能明確地說明某一個(gè)像素是否是一個(gè)邊界。如果要判斷一個(gè)像素是否是一個(gè)邊界，你要設(shè)定一個(gè)類似閾值的東西，亮度高于這個(gè)閾值的像素會(huì)被判定為邊界的一部分。然而這樣并不是最理想的，因?yàn)檫@樣的做法判定出的邊界可能會(huì)有好幾個(gè)像素寬，并且不同的圖片適合的閾值不同。
這里你更需要一種叫做坎尼邊界探測(cè)[3]的邊界探測(cè)方法?？材徇吔缣綔y(cè)可以在一張圖片中探測(cè)出連貫的只有一像素寬的邊界：
http://wiki.jikexueyuan.com/project/objc/images/21-34.png" alt="" />
坎尼邊界探測(cè)包含了幾個(gè)步驟。和索貝爾邊界探測(cè)以及其他我們接下來將要討論的方法一樣，在進(jìn)行邊界探測(cè)之前首先圖片需要轉(zhuǎn)化成亮度圖。一旦轉(zhuǎn)化為灰階亮度圖緊接著進(jìn)行一點(diǎn)點(diǎn)的高斯模糊，這么做是為了降低傳感器噪音對(duì)邊界探測(cè)的影響。
一旦圖片已經(jīng)準(zhǔn)備好了，邊界探測(cè)就可以開始進(jìn)行。這里的 GPU 加速過程原本是在 Ensor 和 Hall 的文章 "GPU-based Image Analysis on Mobile Devices" [4]中所描述的。
首先，一個(gè)給定像素的邊界強(qiáng)度和邊界梯度要確定下來。邊界梯度是指亮度發(fā)生變化最大的方向，也是邊界延伸方向的垂直方向。
為了尋找邊界梯度，我們要用到上一章中的索貝爾矩陣。索貝爾轉(zhuǎn)化得到的橫豎值加合后就是邊界梯度的強(qiáng)度，這個(gè)值會(huì)編碼進(jìn)輸出像素的紅色通道。然后橫向豎向索貝爾結(jié)果值會(huì)與八個(gè)方向 (對(duì)應(yīng)一個(gè)中心像素周圍的八個(gè)像素) 中的一個(gè)結(jié)合起來，一個(gè)方向上 X 部分值會(huì)作為輸出像素的綠色通道值，Y 部分則作為藍(lán)色通道值。
這個(gè)方法使用的著色器和索貝爾邊界探測(cè)使用的類似，只是最后一個(gè)計(jì)算步驟用下面這段代碼：
vec2 gradientDirection;
gradientDirection.x = -bottomLeftIntensity - 2.0 * leftIntensity - topLeftIntensity + bottomRightIntensity + 2.0 * rightIntensity + topRightIntensity;
gradientDirection.y = -topLeftIntensity - 2.0 * topIntensity - topRightIntensity + bottomLeftIntensity + 2.0 * bottomIntensity + bottomRightIntensity;
float gradientMagnitude = length(gradientDirection);
vec2 normalizedDirection = normalize(gradientDirection);
normalizedDirection = sign(normalizedDirection) * floor(abs(normalizedDirection) + 0.617316); // Offset by 1-sin(pi/8) to set to 0 if near axis, 1 if away
normalizedDirection = (normalizedDirection + 1.0) * 0.5; // Place -1.0 - 1.0 within 0 - 1.0
gl_FragColor = vec4(gradientMagnitude, normalizedDirection.x, normalizedDirection.y, 1.0);為確?？材徇吔缫幌袼貙挘挥羞吔缰袕?qiáng)度最高的部分會(huì)被保留下來。因此，我們需要在每一個(gè)切面邊界梯度的寬度之內(nèi)尋找最大值。
這就是我們?cè)谏弦徊街兴愠龅奶荻确较蚱鹱饔玫牡胤?。?duì)每一個(gè)像素，我們根據(jù)梯度值向前和向后取出最近的相鄰像素，然后對(duì)比他們的梯度強(qiáng)度 (邊界明顯程度)。如果當(dāng)前像素的梯度強(qiáng)度高于梯度方向前后的像素我們就保留當(dāng)前像素。如果當(dāng)前像素的梯度強(qiáng)度低于任何一個(gè)臨近像素，我們就不再考慮這個(gè)像素并且將他變?yōu)楹谏?/p>
執(zhí)行這個(gè)步驟的著色器如下：
precision mediump float;
varying highp vec2 textureCoordinate;
uniform sampler2D inputImageTexture;
uniform highp float texelWidth;
uniform highp float texelHeight;
uniform mediump float upperThreshold;
uniform mediump float lowerThreshold;
void main()
{
vec3 currentGradientAndDirection = texture2D(inputImageTexture, textureCoordinate).rgb;
vec2 gradientDirection = ((currentGradientAndDirection.gb * 2.0) - 1.0) * vec2(texelWidth, texelHeight);
float firstSampledGradientMagnitude = texture2D(inputImageTexture, textureCoordinate + gradientDirection).r;
float secondSampledGradientMagnitude = texture2D(inputImageTexture, textureCoordinate - gradientDirection).r;
float multiplier = step(firstSampledGradientMagnitude, currentGradientAndDirection.r);
multiplier = multiplier * step(secondSampledGradientMagnitude, currentGradientAndDirection.r);
float thresholdCompliance = smoothstep(lowerThreshold, upperThreshold, currentGradientAndDirection.r);
multiplier = multiplier * thresholdCompliance;
gl_FragColor = vec4(multiplier, multiplier, multiplier, 1.0);
}其中 texelWidth 和 texelHeight 是要處理的圖片中臨近像素之間的距離，lowerThreshold 和 upperThreshold 分別設(shè)定了我們預(yù)期的邊界強(qiáng)度上下限。
在坎尼邊界探測(cè)的最后一步，邊界上出現(xiàn)像素間間隔的地方要被填充，出現(xiàn)間隔是因?yàn)橛幸恍c(diǎn)不在閾值范圍之內(nèi)或者是因?yàn)榉亲畲笾缔D(zhuǎn)化沒有起作用。這一步會(huì)完善邊界使邊界連續(xù)起來。
在最后一步中需要考慮一個(gè)中心像素周圍的所有像素。如果這個(gè)中心像素是最大值，上一步中非最大值轉(zhuǎn)化就不會(huì)影響它，它依然是白色。如果它不是最大值，就會(huì)變成黑色。對(duì)于中間的灰色像素，會(huì)考察它周圍像素的信息。凡是與超過一個(gè)白色像素挨著的都會(huì)變?yōu)榘咨?，相反就?huì)變成黑色。這樣就可以將邊界分離的部分接合起來。
正如你所看到的，坎尼邊界探測(cè)會(huì)比索貝爾邊界探測(cè)更復(fù)雜一些，但是它會(huì)探測(cè)出一條物體邊界的干凈線條。這是線條探測(cè)、輪廓探測(cè)或者其他圖片分析很好的起點(diǎn)。同時(shí)也可以被用來生成一些有趣的美學(xué)效果。
雖然利用上一章中的邊界探測(cè)技術(shù)我們可以獲取關(guān)于圖片邊界的信息，我們會(huì)得到一張可以直觀觀察到邊界所在位置的圖片，但是并沒有更高層面有關(guān)圖片中所展示內(nèi)容的信息。為了得到這些信息，我們需要一個(gè)可以處理場(chǎng)景中的像素然后返回場(chǎng)景中所展示內(nèi)容的描述性信息的算法。
進(jìn)行物體探測(cè)和匹配時(shí)一個(gè)常見的出發(fā)點(diǎn)是特征探測(cè)。特征是指一個(gè)場(chǎng)景中具有特殊意義的點(diǎn)，這些點(diǎn)可以唯一的區(qū)分出一些結(jié)構(gòu)或者物體。由于邊角的出現(xiàn)往往意味著亮度或者顏色的突然變化，所以邊角常常會(huì)作為特征的一種。
在 Harris 和 Stephens 的文章 "A Combined Corner and Edge Detector."[5] 中他們提出一個(gè)邊角探測(cè)的方法。這個(gè)命名為哈里斯邊角探測(cè)的方法采用了一個(gè)多步驟的方法來探測(cè)場(chǎng)景中的邊角。
像我們已經(jīng)討論過的其他方法一樣，圖片首先需要減薄到只剩亮度信息。通過索貝爾矩陣，普里維特矩陣或者其他相關(guān)的矩陣計(jì)算出一個(gè)像素 X 和 Y 方向上的梯度值，計(jì)算出的值并不會(huì)合并為邊界的量級(jí)。而是將 X 梯度傳入紅色部分，Y 梯度傳入綠色部分，X 與 Y 梯度的乘積傳入藍(lán)色部分。
然后對(duì)上述計(jì)算結(jié)果進(jìn)行一個(gè)高斯模糊。從模糊后的照片中取出紅綠藍(lán)部分中的編碼過的值，并將值帶入一個(gè)計(jì)算像素是邊角點(diǎn)可能性的公式：
R = Ix2 × Iy2 ? Ixy × Ixy ? k × (Ix2 + Iy2)2
其中 Ix 是 X 方向梯度值 (模糊后圖片中紅色部分)，Iy 是 Y 梯度值 (綠色部分)，Ixy 是 XY 值的乘積 (藍(lán)色部分)，k 是一個(gè)靈敏性常數(shù)，R 是計(jì)算出來的這個(gè)像素是邊角的確定程度。Shi，Tomasi[6] 和 Noble[7] 提出過這種計(jì)算的另一種實(shí)現(xiàn)方法但是結(jié)果其實(shí)是十分接近的。
在公式中你可以會(huì)覺得頭兩項(xiàng)會(huì)抵消掉。但這就是前面高斯模糊那一步起作用的地方。通過在一些像素上分別模糊 X、Y 和 XY 的乘積，在邊角附近就會(huì)出現(xiàn)可以被探測(cè)到的差異。
我們從 Stack Exchange 信號(hào)處理分站中的一個(gè)問題中取來一張測(cè)試圖片：
http://wiki.jikexueyuan.com/project/objc/images/21-35.png" alt="" />
經(jīng)過前面的計(jì)算過程得到的結(jié)果如下圖：
http://wiki.jikexueyuan.com/project/objc/images/21-36.png" alt="" />
為了找出邊角準(zhǔn)確的位置，我們需要選出極點(diǎn) (一個(gè)區(qū)域內(nèi)亮度最高的地方)。這里需要使用一個(gè)非最大值轉(zhuǎn)化。和我們?cè)诳材徇吔缣綔y(cè)中所做的一樣，我們要考察一個(gè)中心像素周圍的臨近像素 (從一個(gè)像素半徑開始，半徑可以擴(kuò)大)，只有當(dāng)中心像素的亮度高于它所有臨近像素時(shí)才保留他，否則就將這個(gè)像素變?yōu)楹谏＿@樣一來最后留下的就應(yīng)該是一片區(qū)域中亮度最高的像素，也就是最可能是邊角的地方。
通過這個(gè)過程，我們現(xiàn)在可以從圖片中看到任意不是黑色的像素都是一個(gè)邊角所在的位置：
http://wiki.jikexueyuan.com/project/objc/images/21-37.png" alt="" />
目前我是使用 CPU 來進(jìn)行點(diǎn)的提取，這可能會(huì)是邊角探測(cè)的一個(gè)瓶頸，不過在 GPU 上使用柱狀圖金字塔[8]可能會(huì)加速這個(gè)過程。
哈里斯邊角探測(cè)只是在場(chǎng)景中尋找邊角的方法之一。"Machine learning for high-speed corner detection,"[9] 中 Edward Rosten 的 FAST 邊角探測(cè)方法是另一個(gè)性能更好的方法，甚至可能超越基于 GPU 的哈里斯探測(cè)。
筆直的線段是另一種我們會(huì)在一個(gè)場(chǎng)景需要探測(cè)的常見的特征。尋找筆直的線段可以幫助應(yīng)用進(jìn)行文檔掃描和條形碼讀取。然而，傳統(tǒng)的線段探測(cè)方法并不適合在 GPU 上實(shí)現(xiàn)，特別是在移動(dòng)設(shè)備的 GPU 上。
許多線段探測(cè)過程都基于霍夫變換，這是一項(xiàng)將真實(shí)世界笛卡爾直角坐標(biāo)空間中的點(diǎn)轉(zhuǎn)化到另一個(gè)坐標(biāo)空間中去的技術(shù)。轉(zhuǎn)化之后在另一個(gè)坐標(biāo)空間中進(jìn)行計(jì)算，計(jì)算的結(jié)果又轉(zhuǎn)化回正?？臻g代表線段的位置或者其他特征信息。不幸的是，許多已經(jīng)提出的計(jì)算方法都不適合在 GPU 上運(yùn)行，因?yàn)樗鼈冊(cè)谔匦陨暇筒惶赡艹浞值夭⑿袌?zhí)行，并且都需要大量的數(shù)學(xué)計(jì)算，比如在每個(gè)像素上進(jìn)行三角函數(shù)計(jì)算。
2011年，Dubská 等人 [10] [11] 提出了一種更簡(jiǎn)單并更有效的坐標(biāo)空間轉(zhuǎn)換方法和分析方法，這種方法更合適在 GPU 上運(yùn)行。他們的方法依賴與一個(gè)叫做平行坐標(biāo)空間的概念，聽上去很抽象但是我會(huì)展示出它其實(shí)很容易理解。
我們首先選擇一條線段和線段上的三個(gè)點(diǎn)：
http://wiki.jikexueyuan.com/project/objc/images/21-38.png" alt="" />
要將這條線段轉(zhuǎn)化到平行坐標(biāo)空間去，我們需要畫出三個(gè)平行的垂直軸。在中間的軸上，我們選取三個(gè)點(diǎn)在 X 軸上的值，也就是 1，2，3 處畫一個(gè)點(diǎn)。在左邊的軸上，我們選取三個(gè)點(diǎn)在 Y 軸上的值，在 3，5，7 處畫一個(gè)點(diǎn)。在右邊的軸上我們做同樣的事情，但是取 Y 軸的負(fù)值。
接下來我們將代表 Y 軸值的點(diǎn)和它對(duì)應(yīng)的 X 軸值連接起來。連接后的效果像下圖：
http://wiki.jikexueyuan.com/project/objc/images/21-39.png" alt="" />
你會(huì)注意到在右邊的三條線會(huì)相交于一點(diǎn)。這個(gè)點(diǎn)的坐標(biāo)值代表了在真實(shí)空間中線段的斜率和截距。如果我們用一個(gè)向下斜的線段，那么相交會(huì)發(fā)生在圖的左半邊。
如果我們?nèi)〗稽c(diǎn)到中間軸的距離作為 u (在這個(gè)例子中是 2)，取豎直方向到 0 的距離作為 v (這里是 1/3)，將軸之間的距離作為 d (這個(gè)例子中我使用的距離是 6)，我們可以用這樣的公式計(jì)算斜率和截距
斜率 = ?1 + d/u
截距 = d × v/u
斜率是 2，截距是 1，和上面我們所畫的線段一致。
這種簡(jiǎn)單有序的線段繪畫非常適合 GPU 進(jìn)行，所以這種方法是一種利用 GPU 進(jìn)行線段探測(cè)理想的方式。
探測(cè)線段的第一步是尋找可能代表一個(gè)線段的點(diǎn)。我們尋找的是位于邊界位置的點(diǎn)，并且我們希望將需要分析的點(diǎn)的數(shù)量控制在最少，所以之前談?wù)摰目材徇吔缣綔y(cè)是一個(gè)非常好的起點(diǎn)。
進(jìn)行邊界探測(cè)之后，邊界點(diǎn)被用來在平行坐標(biāo)空間進(jìn)行畫線。每一個(gè)邊界點(diǎn)會(huì)畫兩條線，一條在中間軸和左邊軸之間，另一條在中間軸和右邊軸之間。我們使用一種混合添加的方式使線段的交點(diǎn)變得更亮。在一片區(qū)域內(nèi)最亮的點(diǎn)代表了線段。
舉例來說，我們可以從這張測(cè)試圖片開始：
http://wiki.jikexueyuan.com/project/objc/images/21-40.png" alt="" />
下面是我們?cè)谄叫凶鴺?biāo)空間中得到的 (我已經(jīng)將負(fù)值對(duì)稱過來使圖片高度減半)
http://wiki.jikexueyuan.com/project/objc/images/21-41.png" alt="" />
圖中的亮點(diǎn)就是我們探測(cè)到線段的地方。進(jìn)行一個(gè)非最大值轉(zhuǎn)化來找到區(qū)域最值并將其他地方變?yōu)楹谏?。然后，點(diǎn)被轉(zhuǎn)化回線段的斜率和截距，得到下面的結(jié)果：
http://wiki.jikexueyuan.com/project/objc/images/21-42.png" alt="" />
我必須指出在 GPUImage 中這個(gè)非最大值轉(zhuǎn)換過程是一個(gè)薄弱的環(huán)節(jié)。它可能會(huì)導(dǎo)致錯(cuò)誤的探測(cè)出線段，或者在有噪點(diǎn)的地方將一條線段探測(cè)為多條線段。
正如之前所提到的，線段探測(cè)有許多有趣的應(yīng)用。其中一種就是條形碼識(shí)別。有關(guān)平行坐標(biāo)空間轉(zhuǎn)換有趣的一點(diǎn)是，在真實(shí)空間中平行的線段轉(zhuǎn)換到平行坐標(biāo)空間中后是垂直對(duì)齊的一排點(diǎn)。不論平行線段是怎樣的都一樣。這就意味著你可以通過一排有特定順序間距的點(diǎn)來探測(cè)出條形碼無論條形碼是怎樣擺放的。這對(duì)于有視力障礙的手機(jī)用戶進(jìn)行條形碼掃描是有巨大幫助的，畢竟他們無法看到盒子也很難將條形碼對(duì)齊。
對(duì)我而言，這種線段探測(cè)過程中的幾何學(xué)優(yōu)雅是令我感到十分著迷的，我希望將它介紹給更多開發(fā)者。
這些就是在過去幾年中發(fā)展出來的機(jī)器視覺方法中的幾個(gè)，它們僅僅是適合在 GPU 上工作的方法中的一部分。我個(gè)人認(rèn)為在這個(gè)領(lǐng)域還有著令人激動(dòng)的開創(chuàng)性工作要去做，這將會(huì)誕生可以提高許多人生活質(zhì)量的應(yīng)用。希望這篇文章至少為你提供了一個(gè)機(jī)器視覺領(lǐng)域簡(jiǎn)要的總體介紹，并且展示了這個(gè)領(lǐng)域并不像許多開發(fā)者想象的那樣無法進(jìn)入。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多