第 1 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin Chapitre 6 Ph¸t hiÖn vμ t¸ch biªn 1. Giíi thiÖu vμ biÓu diÔn biªn ¶nh • Mét sè kh¸i niÖm - Biªn ¶nh (Edge) : lμ c¸c ®−êng biªn giíi gi÷a c¸c vïng ¶nh cho phÐp x¸c ®Þnh h×nh d¹ng c¸c ®èi t−îng trong ¶nh. - Vïng ¶nh (Region) : lμ tËp hîp c¸c ®iÓm ¶nh thuéc vÒ ®èi mét t−îng trong ¶nh. Ranh giíi c¸c vïng ¶nh lμ biªn ¶nh, vμ c¸c ®−êng biªn khÐp kÝn cho phÐp x¸c ®Þnh vïng ¶nh. Biªn ¶nh vμ vïng ¶nh lμ 2 ®Æc tr−ng ®èi ngÉu ¶nh. • BiÓu diÔn biªn ¶nh Biªn ¶nh lμ nh÷ng ®iÓm ¶nh mμ t¹i ®ã hμm ®é s¸ng cña ¶nh liªn tôc cã b−íc nh¶y hoÆc biÕn thiªn nhanh. • C¬ së to¸n häc cña ph¸t hiÖn vμ t¸ch biªn : phÐp to¸n ®¹o hμm • Giíi thiÖu vÒ c¸c ph−¬ng ph¸p ph¸t hiÖn biªn - Ph−¬ng ph¸p trùc tiÕp : ph¸t hiÖn biªn dùa trªn phÐp ®¹o hμm : ®¹o hμm bËc 1, ®¹o hμm bËc 2 - Ph−¬ng ph¸p gi¸n tiÕp : Ph¸t hiÖn biªn dùa trªn ph©n vïng ¶nh Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 2 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin 2. Ph¸t hiÖn biªn dùa trªn ph−¬ng ph¸p ®¹o hμm • C¸c to¸n tö ®¹o hμm ¶nh : Gradient cña ¶nh : G(x,y) , ®¹o hμm bËc 1 Laplace cña ¶nh : L(x,y), ®¹o hμm bËc 2 Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 3 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin • Gradient cña mét ¶nh liªn tôc f(x,y) däc theo r víi gãc θ df ∂f dx ∂f dy θ θ = + = fxCos + fySin dr ∂x dr ∂y dr • Nguyªn t¾c cña ph−¬ng ph¸p ph¸t hiÖn biªn dùa trªn phÐp ®¹o hμm - Ph¸t hiªn biªn dùa trªn ®¹o hμm bËc 1 : t×m cùc trÞ ®Þa ph−¬ng cña gradient - Ph¸t hiªn biªn dùa trªn ®¹o hμm bËc 2 : x¸c ®Þnh ®iÓm ®i qua gi¸ trÞ kh«ng cña laplace Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 4 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin • Bé läc sè (läc tuyÕn tinh) thùc hiÖn gÇn ®óng c¸c phÐp to¸n ®¹o hμm. ∂F(x,y) = ∆F ≈ F(m,n+1)−F(m,n−1) ≈ F(m,n)* (k) 1 ⎡ ⎤ ∂x ∆n 2 Dx , víi DX (k) = ⎢1 0 −1⎥ 2 ⎣ ⎦ ∂F(x,y) ∆F F(m+1,n)−F(m−1,n) ⎡1 ⎤ = ≈ ≈ F(m,n)*D (k) víi D 1 ⎢ ⎥ ∂y ∆m 2 y , = ⎢0 ⎥ y 2 ⎢⎣−1⎥⎦ ∂F(x, y) ≈ (k,l)*X(m,n)= (m,n) vμ ∂F(x, y) ≈ (k,l)*X(m,n)= (m,n) ∂x H x G x ∂y H y G y 3. C¸c ph−¬ng ph¸p hiÖn biªn truyÒn thèng 3.1 Ph¸t hiÖn biÖn dùa trªn gradient cña ¶nh - To¸n tö Prewitt ⎡1 0 −1⎤ ⎡ 1 1 1 ⎤ H = ⎢1 0 −1⎥ H = ⎢ 0 0 0 ⎥ x ⎢ ⎥ y ⎢ ⎥ ⎢⎣1 0 −1⎥⎦ ⎢⎣−1 −1 −1⎥⎦ - To¸n tö Sobel ⎡1 0 −1⎤ ⎡ 1 2 1 ⎤ H = ⎢2 0 − 2⎥ H = ⎢ 0 0 0 ⎥ x ⎢ ⎥ y ⎢ ⎥ ⎢⎣1 0 −1⎥⎦ ⎢⎣−1 − 2 −1⎥⎦ Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 5 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin - To¸n tö Robert G ⎧⎪ X [ ]⎫⎪ - To¸n tö ®¹o hμm h−íng (Compass gradient) : =max⎨Hi(k,l)* (m,n); avec i∈ 0,7⎬ i ⎪⎩ ⎪⎭ 3 2 1 X(m,n) G(m,n) G(m,n) biªn H(k,l)*X(m,n) i max{GIi =0, 7} Ng−ìng 4 0 i i ϕ Gradient 5 6 7 ⎡ 5 5 5 ⎤ H = ⎢−3 0 −3⎥ ⎢ ⎥ ⎢⎣−3 −3 −3⎥⎦ To¸n tö Kirsh - Qu¸ tr×nh t¸ch biªn dùa trªn gradient + TÝnh gradient cña ¶nh theo to¸n tö lùa chän : ⎡Gx(m,n)⎤ G(mn,)=⎢ ⎥, víi G x(m,n)=H (k,l)*X(m,n) vμ G y(m,n)=H (k,l)*X(m,n) G (m,n) x y ⎣ y ⎦ + TÝnh ®é lín cña vect¬ gradient : G(m,n) + X¸c ®Þnh ®iÓm biªn dùa trªn ng−ìng cña gradient hoÆc t×m cùc trÞ ®Þa ph−¬ng cña gradient Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 6 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin 3.2 Ph¸t hiÖn biÖn dùa trªn Laplace cña ¶nh - To¸n tö Laplace ∂2 f ∂2 f ∇ 2 f = + dx 2 dy 2 ∂2 f = 2 f (x, y) − f (x −1, y) − f (x + 1, y) dx 2 ∂ 2 f = 2 f (x, y) − f (x, y − 1) − f (x, y + 1) dy 2 ∇ 2 f = − f (x − 1, y) − f (x, y − 1) + 4 f (x, y) − f (x, y + 1) − f (x + 1, y) ⎡ ⎤ ⎢0 −1 0⎥ - Bé läc Laplace : ⎢ ⎥ TÝnh laplace L(m,n)=H (k,l)*X(m,n) HL(k,l) = ⎢−1 4 −1⎥ . : L - ⎢ ⎥ ⎢0 −1 0⎥ ⎢⎣ ⎥⎦ - Qu¸ tr×nh t¸ch biªn dùa trªn qu¸ tr×nh x¸c ®Þnh sù ®i qua c¸c gi¸ trÞ 0 cña laplace + TÝnh laplace cña ¶nh L(m,n) + X¸c ®Þnh ma trËn ph©n cùc cña laplace X (m,n) P + X¸c ®Þnh ma trËn ®i qua c¸c gi¸ trÞ 0 cña laplace X (m,n) Z + KiÓm tra l¹i c¸c gi¸ trÞ ®é lín cña gradient t¹i c¸c ®iÓm mμ laplace ®i qua gi¸ trÞ 0 Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 7 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin 4. C¸c ph−¬ng ph¸p ph¸t hiÖn vμ t¸ch biªn tiªn tiÕn §Æt vÊn ®Ò - Biªn cña ¶nh tù nhiªn th−êng phøc t¹p, hμm ®é s¸ng cña ¶nh biÕn thiªn ngÉu nhiªn, hμm kh«ng tr¬n. ¶nh sè biÓu diÔn bëi ma trËn sè liÖu, hμm rêi r¹c, vÊn ®Ò tÝnh ®¹o hμm ¶nh ? - ChÊt l−îng ph¸t hiÖn vμ t¸ch biªn cña c¸c ph−¬ng ph¸p truyÒn thèng dùa trªn c¸c to¸n tö Prewitt, Sobel, Robert... bÞ gi¶m nhiÒu khi ¸p dông cho ¶nh tù nhiªn phøc t¹p, nhiÒu tr−êng hîp kh«ng tho¶ m·n yªu cÇu thùc tÕ - Cã nhiÒu ph−¬ng ph¸p ®−îc ®Ò nghÞ, yªu cÇu ph¸t hiÖn vμ t¸ch biªn chÝnh x¸c trong thùc tÕ lu«n ®ßi hái nghiªn cøu c¸c ph−¬ng ph¸p tiªn tiÕn. Giíi thiÖu mét sè ph−¬ng ph¸p ph¸t hiÖn vμ t¸ch biªn tiªn tiÕn • Ph−¬ng ph¸p läc tèi −u - Ph−¬ng ph¸p ®−îc nghiªn cøu bëi Canny (1986) vμ ®−îc ph¸t triÓn bëi Deriche, shen- Castan. - ý t−ëng c¬ b¶n : m« h×nh ho¸ c¸c ®iÓm biªn theo m« h×nh ngÉu nhiªn. T×m bé läc t¸ch biªn thùc hiÖn 2 chøc n¨ng : läc lμm tr¬n hμm vμ läc ®¹o hμm, bé läc ®−îc tèi −u theo 3 tiªu chÝ cña Canny • Ph−¬ng ph¸p dïng hμm néi suy spline • Ph−¬ng ph¸p m« h×nh ho¸ bÒ mÆt ¶nh Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
第 8 页
®¹i häc B¸ch khoa Hμ néi Khoa C«ng nghÖ Th«ng tin 5. KÕt nèi ®iÓm biªn vμ khÐp kÝn ®−êng biªn • VÊn ®Ò: kÕt nèi c¸c ®iÓm biªn sau khi ph¸t hiÖn & t¸ch biªn lu«n lμ cÇn thiÕt trong thùc tÕ • Nguyªn t¾c kÕt nèi ®iÓm biªn : dß biªn ®Ó kÕt nèi ®iÓm biªn tho¶ m·n ®iÒu kiÖn biªn • ThuËt to¸n dß biªn dùa trªn ph−¬ng ph¸p qui ho¹ch ®éng (Dynamic Programming) - Nguyªn t¾c dß biªn theo qui ho¹ch ®éng - D·y c¸c ®iÒm cÇn dß vμ kÕt nèi : {s1, s2, ...., sN} = {sn} - Hμm gi¸ cña qu¸ tr×nh dß biªn theo qui ho¹ch ®éng : n n n f (n)= ∑ G(sk) −α ∑ ϕ(sk)−ϕ(s − ) − β ∑d(sk ,sk −1) k=1 k=2 k 1 k=2 G(sk) et ϕ(sk) lμ m« ®un vμ h−íng cña vector gradient t¹i ®iÓm s trªn ®−êng dß k d(sk ,sk−1) lμ kho¶ng c¸ch h×nh häc giòa 2 ®iÓm s et s , α vμ β lμ c¸c hÖ sè >0, lùa chän k k-1 ⎧∧ ⎫ - Tiªu chuÈn dß t¹i ®iÓm s Φ( )= ⎪⎪ f (snj)⎪⎪ n sn max ⎨ ⎬ j∈1,2,3⎪ ⎪ ⎪⎩ ⎪⎭ s 0 contour pixel arc d'un chemin direction d'elaboration s f Xñ lý ¶nh NguyÔn ThÞ Hoμng Lan
评论 (0)
暂无评论。快来抢沙发吧！