Bài giảng Xử lý ảnh: Chương 7 - Nguyễn Thị Hoàng Lan

®¹i häc B¸ch khoa Hµ néi<br /> <br /> Khoa C«ng nghÖ th«ng tin<br /> <br /> Ch−¬ng 7<br /> <br /> Ph©n vïng ¶nh<br /> 1. Kh¸i qu¸t chung<br /> • Mét vµi kh¸i niÖm<br /> - Mét vïng ¶nh R (Region) : lµ tËp hîp cña c¸c ®iÓm ¶nh cã cïng chung c¸c thuéc tÝnh<br /> thuéc vÒ mét ®èi t−îng trong ¶nh.<br /> - Ph©n vïng ¶nh (segmentation): lµ qu¸ tr×nh ph©n ho¹ch tËp hîp c¸c ®iÓm ¶nh X thµnh c¸c<br /> tËp con cña c¸c vïng ¶nh Ri tho¶ m·n c¸c ®iÒu kiÖn sau :<br /> ∀i Ri ≠ ∅ , ∀i, j i ≠ j, Ri ∩ R j = ∅ et X = ∪ Ri , Ri bao gåm c¸c pixel cã thuéc tÝnh chung.<br /> i<br /> <br /> • C¸c h−íng tiÕp cËn cña ph©n vïng ¶nh<br /> - Ph©n vïng dùa trªn ®é ®ång ®Òu, ®é t−¬ng tù vÒ møc x¸m vµ vÒ c¸c thuéc tÝnh cña c¸c<br /> pixel trong mçi vïng.<br /> - Ph©n vïng dùa trªn t¸ch biªn dùa trªn sù biÕn thiªn cña hµm ®é s¸ng hay møc x¸m<br /> • C¸c c«ng ®o¹n chñ yÕu cña ph©n vïng ¶nh : - TiÒn xö lý<br /> - Qu¸ tr×nh ph©n vïng (thuËt to¸n)<br /> - ®¸nh nh·n ph©n t¸ch c¸c vïng vµ hiÖu chØnh<br /> <br /> Xö lý ¶nh<br /> <br /> NguyÔn ThÞ Hoµng Lan<br /> <br /> ®¹i häc B¸ch khoa Hµ néi<br /> <br /> Khoa C«ng nghÖ th«ng tin<br /> <br /> • Mét sè ph−¬ng ph¸p ph©n vïng<br /> <br /> - Ph©n vïng dùa trªn sù ph©n líp c¸c ®iÓm ¶nh trong kh«ng gian thuéc tÝnh mét chiÒu<br /> hoÆc kh«ng gian thuéc tÝnh nhiÒu chiÒu,<br /> - Ph©n vïng theo ph−¬ng ph¸p cÊu tróc,<br /> - Ph©n vïng dùa trªn biÓu diÔn vµ xö lý ®a ph©n gi¶i,<br /> - Ph©n vïng dùa trªn ph©n tÝch kÕt cÊu (texture).<br /> <br /> 2. C¸c thuéc tÝnh cña ®iÓm ¶nh vµ cña vïng ¶nh<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> Thuéc tÝnh biªn ®é<br /> ®é ®ång ®Òu vÒ møc x¸m, ®é t−¬ng ph¶n<br /> Thuéc tÝnh tÇn sè<br /> Thuéc tÝnh thèng kª, tham sè th«ng kª<br /> Thuéc tÝnh h×nh häc, tham sè h×nh häc<br /> Thuéc tÝnh cÊu tróc (texture) ...<br /> <br /> 3. Ph−¬ng ph¸p ph©n líp<br /> • Sù ph©n líp<br /> - Kh¸i niÖm vÒ líp c¸c c¸ thÓ (c¸c phÇn tö) : tËp hîp c¸c phÇn tö cã chung thuéc tÝnh<br /> - Sù ph©n líp : ph©n lo¹i c¸c phÇn tö vÒ c¸c líp theo c¸c tiªu chuÈn vÒ thuéc tÝnh<br /> - Mét vïng ¶nh Rk ®−îc x¸c ®Þnh bëi c¸c pixel thuéc vÒ mét líp Ck<br /> Xö lý ¶nh<br /> <br /> NguyÔn ThÞ Hoµng Lan<br /> <br /> ®¹i häc B¸ch khoa Hµ néi<br /> <br /> Khoa C«ng nghÖ th«ng tin<br /> <br /> • Ph−¬ng ph¸p ph©n líp c¸c ®iÓm ¶nh trong kh«ng gian thuéc tÝnh ®a chiÒu<br /> <br /> Tiªu chuÈn ph©n líp : kho¶ng c¸ch gi÷a c¸c vect¬ thuéc tÝnh<br /> • Ph©n líp c¸c ®iÓm ¶nh trong kh«ng gian thuéc tÝnh 1 chiÒu : thuéc tÝnh biªn ®é<br /> - Tiªu chuÈn ph©n líp dùa trªn c¸c ng−ìng gi¸ trÞ møc x¸m gi÷a c¸c vïng<br /> - ThuËt to¸n ISODATA (Iterative Self Organization DATa Analysis)<br /> B−íc ®Çu (t = 0)<br /> + ®o¸n nhËn sè líp M<br /> + Lùa chän c¸c gi¸ trÞ ng−ìng ban ®Çu gi÷a c¸c líp Tj(0)<br /> B−íc lÆp (t = 1, 2 ...) :<br /> + Thùc hiÖn ph©n líp theo c¸c ng−ìng Tj(t-1)<br /> + TÝnh gi¸ trÞ trung b×nh trong mçi líp mk(t)<br /> + TÝnh c¸c gi¸ trÞ ng−ìng míi Tj(t) theo c¸c gi¸ trÞ mk(t)<br /> + KiÓm tra ®iÒu kiÖn lÆp<br /> B−íc cuèi: + Ph©n líp c¸c ®iÓm ¶nh theo c¸c gi¸ trÞ ng−ìng ®¹t ®−îc khi thuËt to¸n héi tô,<br /> + ®¸nh nh·n thuéc tÝnh, ph©n t¸ch c¸c vïng vµ hiÖu chØnh sè líp nÕu cÇn,<br /> + Ph©n t¸ch c¸c vïng<br /> <br /> 4. Ph−¬ng ph¸p cÊu tróc<br /> • ThuËt to¸n lan to¶ vïng<br /> • ThuËt to¸n ph©n vïng dùa trªn sù ph©n chia vµ kÕt hîp c¸c miÒn kÒ<br /> Nguyªn t¾c chia ¶nh dùa trªn cÊu tróc c©y tø ph©n<br /> Rx<br /> <br /> Ri1<br /> <br /> Ri2<br /> <br /> Ri3<br /> <br /> Ri4<br /> <br /> R11<br /> <br /> R12<br /> <br /> R13<br /> <br /> R14<br /> <br /> Ri<br /> <br /> Xö lý ¶nh<br /> <br /> R121 R122 R123 R124 R131 R132 R133 R134<br /> <br /> NguyÔn ThÞ Hoµng Lan<br /> <br /> ®¹i häc B¸ch khoa Hµ néi<br /> <br /> Khoa C«ng nghÖ th«ng tin<br /> <br /> ThuËt to¸n ph©n chia miÒn kÒ d−¹ trªn cÊu tróc c©y tø ph©n<br /> •<br /> <br /> ChØ tiªu ph©n chia<br /> Sè ®o ®é ®ång ®Òu thuéc tÝnh cu¶ miÒn R:<br /> <br /> σ ( R) =<br /> <br /> NÕu<br /> <br /> 1<br /> 2<br /> ∑ ( A( s) − m( R)) vµ<br /> card ( R) s∈R<br /> <br /> σ(R) > θ<br /> <br /> th×<br /> <br /> Pred(R) = 0,<br /> <br /> Hµm vÞ tõ : Pred(R)<br /> <br /> nghÜa lµ ®é kh«ng ®ång ®Òu<br /> <br /> •<br /> <br /> Nguyªn t¾c thuËt to¸n<br /> - Ph©n chia liªn tiÕp c¸c miÒn kÒ theo cÊu tróc c©y tø ph©n cho ®Õn khi ®¹t ®−îc tÊt c¶ c¸c miÒn ®ång ®Òu<br /> - X©y dùng c©y tø ph©n cña ¶nh<br /> - TÝnh sai sè b×nh ph−¬ng cña ¶nh sau qu¸ tr×nh chia<br /> VÝ dô<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> Xö lý ¶nh<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 2<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 1<br /> 2<br /> 1<br /> 1<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 1<br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 1<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> <br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> <br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> <br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> <br /> 0<br /> 0<br /> .8<br /> .2<br /> .9<br /> .9<br /> .1<br /> .1<br /> <br /> 0<br /> 0<br /> .2<br /> .2<br /> .1<br /> .1<br /> .1<br /> .1<br /> <br /> 3<br /> 3<br /> 0<br /> 0<br /> 1<br /> 1<br /> 1<br /> 1<br /> <br /> .3<br /> .3<br /> 0<br /> 0<br /> .1<br /> .1<br /> ,1<br /> .1<br /> <br /> NguyÔn ThÞ Hoµng Lan<br /> <br /> ®¹i häc B¸ch khoa Hµ néi<br /> <br /> Khoa C«ng nghÖ th«ng tin<br /> <br /> ThuËt to¸n kÕt hîp<br /> •<br /> <br /> ®å thÞ c¸c miÒn kÒ G(V, E)<br /> V : TËp c¸c nót t−¬ng øng víi c¸c miÒn kÒ. E : TËp c¸c cung, c¸c liªn kÕt<br /> Hai miÒn kÒ Ri vµ Rj ®−îc nèi bëi mét cung trªn ®ã mang gi¸ trÞ vÒ ®é ®o sù kh«ng ®ång ®Òu thuéc tÝnh gi÷a 2 miÒn E(Ri, Rj).<br /> <br /> •<br /> <br /> ChØ tiªu kÕt hîp<br /> Hai miÒn kÒ Ri vµ Rj sÏ ®−îc kÕt hîp thµnh mét miÒn R :<br /> <br /> R = Ri ∪ R j<br /> <br /> nÕu gi¸ trÞ ®é ®o vÒ sù kh«ng ®ång ®Òu thuéc tÝnh<br /> <br /> gi÷a 2 miÒn lµ nhá nhÊt. Qu¸ tr×nh kÕt hîp ®−îc dùa trªn sù kiÓm tra ®iÒu kiÖn vÒ sai sè b×nh ph−¬ng nh− sau :<br /> N<br /> E ( N ) = ∑ ∑ A( s) − m( R k ) 2<br /> k =1 s∈R k<br /> <br /> (<br /> <br /> •<br /> <br /> )<br /> <br /> Néi dung thuËt to¸n kÕt hîp<br /> -<br /> <br /> B−íc ®Çu :<br /> B−íc lÆp :<br /> <br /> -<br /> <br /> B−íc cuèi :<br /> <br /> X©y dùng ®å thÞ c¸c miÒn kÒ cña ¶nh sau qu¸ tr×nh ph©n chia : G(V, E), vµ chän ng−ìng<br /> KÕt hîp c¸c miÒn kÒ Ri et Rj t−¬ng øng víi c¸c cung cã gi¸ trÞ nhá nhÊt.<br /> CËp nhËt ®å thÞ c¸c miÒn kÒ G(V, E) vµ tÝnh sai sè E(N) sau mçi lÇn kÕt hîp<br /> KiÓm tra ®iÒu kiÖn lÆp dùa trªn E(N)<br /> KÕt qu¶ ph©n vïng dùa trªn ®å thÞ c¸c miÒn kÒ sau qu¸ tr×nh lÆp, t¸ch c¸c vïng vµ hiÖu chØnh (nÕu c©n)<br /> <br /> m= 1,0 m= 1,3<br /> <br /> 0,9<br /> <br /> 0<br /> <br /> m= 1,8 m= 2,0<br /> <br /> a)<br /> <br /> 0<br /> 2,6<br /> 4,2<br /> <br /> 0<br /> m= 1,9<br /> <br /> m= 2,0 m= 2,0<br /> <br /> 0,9<br /> <br /> 2,6<br /> <br /> 0<br /> <br /> m= 1,0 m= 1,0<br /> <br /> Xö lý ¶nh<br /> <br /> 0,9<br /> <br /> 1,43<br /> <br /> m= 1,0<br /> <br /> 2<br /> <br /> 2<br /> 0<br /> <br /> 1,8<br /> <br /> 1,8<br /> <br /> b)<br /> <br /> NguyÔn ThÞ Hoµng Lan<br /> <br />