【文章內(nèi)容簡(jiǎn)介】 ? Quantize Parameter Space ? Create Accumulator Array ? Set ? For each image edge increment: ? If lies on the line: ? Find local maxima in ),( cm),( cmAcmcmA ,0),( ??),( ii yx1),(),( ?? cmAcmA),( cm),( cmAii ymxc ???Image amp。 Vision Lab Better Parameterization NOTE: Large Accumulator More memory and putations Improvement: Line equation: Here Given points find ????? m??? s inc o s yx ???m a x020????????(Finite Accumulator Array Size) ),( ii yx ),( ??),( ii yxyxImage Space ??Hough Space ? Hough Space Sinusoid Image amp。 Vision Lab Image space Votes Horizontal axis is θ, vertical is rho. Image amp。 Vision Lab Image space votes Image amp。 Vision Lab Image amp。 Vision Lab Mechanics of the Hough transform ? Difficulties ? how big should the cells be? (too big, and we merge quite different lines。 too small, and noise causes lines to be missed) ? How many lines? ? Count the peaks in the Hough array ? Treat adjacent peaks as a single peak ? Which points belong to each line? ? Search for points close to the line ? Solve again for line and iterate Image amp。 Vision Lab Fewer votes land in a single bin when noise increases. Image amp。 Vision Lab Adding more clutter increases number of bins with false peaks. Image amp。 Vision Lab Real World Example Original Edge Detection Found Lines Parameter Space Image amp。 Vision Lab Finding Circles by Hough Transform Equation of Circle: 222 )()( rbyax ii ????If radius is known: ),( baAAccumulator Array (2D Hough Space) Image amp。 Vision Lab Finding Circles by Hough Transform Equation of Circle: 222 )()( rbyax ii ????If radius is not known: 3D Hough Space! Use Accumulator array ),( rbaAWhat is the surface in the hough space? Image amp。 Vision Lab Using Gradient Information ? Gradient information can save lot of putation: Edge Location Edge Direction Need to increment only one point in Accumulator!! i?),( ii yxAssume radius is known: ??s inc osrybrxa????Image amp。 Vision Lab Real World Circle Examples Crosshair indicates results of Hough transform, bounding box found via motion differencing. Image amp。 Vision Lab Finding Coins Original Edges (note noise) Image amp。 Vision Lab Finding Coins (Continued) Penny Quarters Image amp。 Vision Lab Finding Coins (Continued) Coin finding sample images from: Vivek Kwatra Note that because the quarters and penny are different sizes, a different Hough transform (with separate accumulators) was used for each circle size. Image amp。 Vision Lab Generalized Hough Transform ? Model Shape NOT described by equation Image amp。 Vision Lab Generalized Hough Transform ? Model Shape NOT described by equation Image amp。 Vision Lab Generalized Hough Transform Find Object Center given edges Create Accumulator Array Initialize: For each edge point For each entry in table, pute: Increment Accumulator: Find Local Maxima in ),( cc yxA),(0),( cccc yxyxA ??),( iii yx ?1),(),( ?? cccc yxAyxA),( cc yxAikikicikikicryyrxx??s inc os????ikr),( cc yx ),( iii yx ?Image amp。 Vision Lab Image amp。 Vision Lab Hough Transform: Comments ? Works on Disconnected Edges ? Relatively insensitive to occlusion ? Effective for simple shapes (lines, circles, etc) ? Tradeoff between work in Image Space and Parameter Space ? Handling inaccurate edge locations: ? Increment Patch in Accumulator rather than a single point Image amp。 Vision Lab Hough變換 ?霍夫變換是圖像處理中一種經(jīng)典的處理 (變換 )方法，目的是從圖像中識(shí)別特定的幾何形狀，如邊界，外形或外輪廓線等能夠用參數(shù)方程表達(dá)的曲線。 ?它的基本思想是：空間曲線與參數(shù)的點(diǎn)－線對(duì)偶性 (duality)：由某一組參數(shù) A描述的曲線在圖像空間中對(duì)應(yīng)了 n個(gè)像素，但所有這 n個(gè)像素在參數(shù)空間中只對(duì)應(yīng)了一個(gè)點(diǎn)（這個(gè)點(diǎn)由 A確定）。反之，參數(shù)空間中的任意一點(diǎn)對(duì)應(yīng)著圖像空間中的一組同類曲線。 Image amp。 Vision Lab 圖像空間與參數(shù)空間 圖像空間 參數(shù)空間 Image amp。 Vision Lab 圖像空間與參數(shù)空間 (續(xù) ) ?對(duì)圖像進(jìn)行某種形式的變換，使得經(jīng)過(guò)變換后原圖上特定形狀的曲線上的點(diǎn)，能夠集中到變換空間（參數(shù)空間）的某些相對(duì)集中的位臵上形成峰。這樣，把對(duì)原圖中特定形狀曲線的檢測(cè)問(wèn)題（確定曲線的參數(shù)），轉(zhuǎn)化為在變換空間中尋找峰值的問(wèn)題（確定峰值點(diǎn)的位臵）。 ?優(yōu)點(diǎn)： ?抗干擾能力強(qiáng)。因?yàn)樗腔诮y(tǒng)計(jì)的方法，所以如果待檢測(cè)曲線上有小的擾動(dòng)，斷裂，甚至是虛線，都能很好地檢測(cè)出來(lái)。 ?利用的是圖象的全局特性。 ?定位比較精確：可以到亞像素級(jí)精度。 ?霍夫變換的應(yīng)用很廣，也有很多改進(jìn)算法。最基本的霍夫變換是從二值圖中檢測(cè)直線和圓等。 Hough變換還可以推廣到更多參數(shù)的曲線檢測(cè)中，甚至可以用來(lái)檢測(cè)任意形狀的曲線。這種被推廣了的 Hough變換稱為廣義 Hough變換。 Image amp。 Vision Lab 檢測(cè)直線 ?直角坐標(biāo)系 XOY 中 , 直線 y=mx+b可以用極坐標(biāo)表示為：r=xcos?+ysin?。因此可以用一個(gè)二維向量 (r,?) (與直線 y=mx+b 垂直 )來(lái)表示這條直線： r 表示向量的長(zhǎng)度， ? 表示向量與軸 X的夾角。 直線在直角坐標(biāo)和極坐標(biāo)之間的關(guān)系 Image amp。 Vision Lab ?在由參數(shù) r和 ?定義的二維參數(shù)空間里， XOY平面上的任意一條直線都可以映射為該空間中的一個(gè)點(diǎn)（該點(diǎn)的位臵由 r和 ?確定）。 ?反過(guò)來(lái)，考察 XOY平面上的一個(gè)點(diǎn) (x,y)，過(guò)該點(diǎn)可以作任意多條直線，每一條直線都對(duì)應(yīng)了參數(shù)