Search This Blog

Wednesday, March 7, 2012

Skeleton of Image Region

ပုံရိပ် တစ်ခုရဲ့ တည်ဆောက်ပုံ ပုံသဏ္ဌာန် ကို မျဉ်းကြောင်းများနဲ့ တုတ်ချောင်းပုံ လုပ်ပြီး ကိုယ်စားပြု ဖော်ပြနိုင်ပါတယ်။ အဲဒီလို ဖော်ပြဖို့အတွက် ပုံသဏ္ဌာန် တစ်ခုကို တဖြည်းဖြည်း ပိန်ပါးသွားအောင် လုပ်နည်း တစ်ခုခု ကို သုံးလို့ရပါတယ်။ ရလာတဲ့ မျဉ်းကြောင်းများနဲ့ တုတ်ချောင်းပုံ ကို အဲဒီ ပုံရဲ့ အရိုး (skeleton) လို့ ခေါ်ပါမယ်။ ဒီနည်းဟာ စာလုံးများကို စက်က သိရှိနားလည် မှတ်မိ အောင် လုပ်တဲ့ နေရာ (optical character recognition) တွေမှာ ပဏာမ အဆင့် အနေနဲ့ အသုံးကျကောင်း ကျနိုင်ပါတယ်။ အောက်ကပုံတွေမှာ နမူနာ မူရင်းပုံနဲ့ သူ့ရဲ့ အရိုးကို ဖော်ပြထားပါတယ်.
ပုံရိပ်တစ်ခု ရဲ့ အရိုးကို နည်းအမျိုးမျိုးနဲ့ ရယူနိုင်ပြီး အဲဒီ နည်းတွေထဲက လူသိများတဲ့ နည်းနှစ်နည်းက အလယ်ဝင်ရိုးပြောင်းနည်း Medial Axis Transformation (MAT) နဲ့ နှစ်ဆင့်ပါးနည်း Two Step Thinning တို့ပါ။ MAT မှာ ပုံသဏ္ဌာန် ထဲမှာ ရှိတဲ့ အစက် တစ်စက် ချင်းစီ အတွက် သူတို့ ရဲ့ အနီးဆုံး အနားသတ် ကို လိုက်ရှာပါတယ်။ အဲဒီလို အကွာအဝေးတူ အနီးဆုံး အနားသတ် တစ်ခုမက ရှိတဲ့ အစက်ကို အရိုး လို့သတ်မှတ်ပါတယ်။ MAT ကနားလည်ဖို့ လွယ်ပေမယ့် သူ့ကိုရဖို့ တွက်ချက်မှုတွေ အများကြီး လိုပါတယ်။ သူ့ကို တွက်ဖို့ အကွာအဝေးပုံစံ ပြောင်းခြင်း (distance transform) ကို အရင် လုပ်ပါတယ်။ အကွာအဝေးပုံစံ ပြောင်းတယ်ဆိုတာ ပုံသဏ္ဌာန် ထဲမှာ ရှိတဲ့ အစက် တစ်စက် ချင်းစီ ကို အနီးဆုံး အနားသတ်အထိ အကွာအဝေးနဲ့ အစားထိုးတာပါ။ ရလာတဲ့ ပုံမှာ အနားသတ်နဲ့ နီးတဲ့ အစက်က အကွာအဝေး တန်ဖိုးနည်းတော့ အလင်းအားပျော့ ပြီး၊ အနားသတ်နဲ့ ဝေးတဲ့ အစက်က အကွာအဝေးတန်ဖိုးကြီးတော့ ပိုလင်းပါမယ်။ နောက် အစက်တစ်စက် ခြင်းစီကို ဘေးတိုက် ဒါမှမဟုတ် ဒေါင်လိုက် ကပ်ရပ် အစက်တွေနဲ့ ယှဉ်ကြည့်ပြီး အလယ်မှာ အမြင့်ဆုံး ဖြစ်နေတဲ့ အစက်တွေကို အရိုးလို့ သတ်မှတ်ပါမယ်။ နမူနာ MATLAB ကုဒ် ကို ဒီမှာ (MATeg.m) ကြည့်နိုင်ပါတယ်။ မူရင်း ပုံသဏ္ဌာန်ရယ်၊ အကွာအဝေးပုံစံ ရယ်၊ ရလာတဲ့ အရိုးရယ် ကို အောက်က ပုံတွေမှာ ကြည့်နိုင်ပါတယ်။


နှစ်ဆင့်ပါးနည်း ကတော့ MAT နဲ့ယှဉ်ရင် ပိုမြန်၊ ပိုထိရောက်ပါတယ်။ နှစ်ဆင့်ပါးနည်း က ပုံသဏ္ဌာန် တစ်ခုရဲ့ အနားတွေကို ထပ်တလဲလဲ ဖျက်သွားတာပါ။ အဲဒီလို ဖျက်တဲ့ အခါမှာ အဆုံးမှတ်တွေကို မဖျက်ပါဘူး။ တနေရာနဲ့ တနေရာ ဆက်စပ်နေတဲ့ အမှတ်တွေကို မဖျက်ပါဘူး။ ပုံသဏ္ဌာန် ထဲမှာ ရှိတဲ့ အစက် တွေကို တန်ဖိုး တစ်ရှိတယ်လို့ မှတ်ယူ မှာ ဖြစ်ပြီး နောက်ခံ အစက်တွေကို တော့ တန်ဖိုး သုည ရှိတယ် လို့ မှတ်ယူပါမယ်။ ဒီနည်းမှာ အဆင့် နှစ်ဆင့် ကို ပုံပေါ်မှာ အထပ်ထပ် အဖန်ဖန် နောက်ဆုံး မပြောင်းလဲတဲ့ အရိုး ရတဲ့အထိ သုံးသွားမှာပါ။
အပေါ်ပုံမှာ အလယ် အစက်ရဲ့ ကပ်ရပ် အစက်တွေကို အခေါ်အဝေါ်သတ်မှတ်ပုံကို ပြထားပါတယ်။ ပထမ အဆင့်မှာ အစက် p1 ကို အောက်က အချက်လေးချက်နဲ့ ကိုက်ညီရင် ဖျက်ပစ် ပါမယ်။ (a) 2 ≤ N(p1) ≤ 6 (b) T(p1) = 1 (c) p2.p4.p6 = 0 (d) p4.p6.p8 = 0 အဲဒီမှာ N(p1) ဆိုတာက p1 နဲ့ ကပ်ရပ် အစက်တွေထဲက သုညမဟုတ်တဲ့ အစက် အရေအတွက်ဖြစ်ပြီး၊ T(p1) ဆိုတာက p2, p3, ... , p8, p9, p2 ဆိုတဲ့ အစီအစဉ်အတိုင်း ကြည့်သွားရင် ၀ ကနေ ၁ ကို ပြောင်းသွားတဲ့ အရေ အတွက်ပါ။ ဒုတိယ အဆင့်မှာ (a) နဲ့ (b) ကအတူတူပါပဲ။ ဒါပေမယ့် (c) နဲ့ (d) ကတော့ အောက်မှာ ပြထားတဲ့ အတိုင်း ပြောင်းသွားပါတယ်။ (c') p2.p4.p8= 0 (d') p2.p6.p8= 0 ပထမ အဆင့် ကို ပုံသဏ္ဌာန်တစ်ခုရဲ့ အနားသတ်ပေါ်မှာရှိတဲ့ အစက်တိုင်းအတွက် စဉ်းစားပါမယ်။ အချက် (a) ကနေ (d) ထဲက တစ်ချက်ချက် မကိုက်တာနဲ့ အဲဒီ အစက်ကို မဖျက်တော့ ပါဘူး။ အချက်အားလုံး ကိုက်ညီရင် တော့ ဖျက်ဖို့ အတွက် မှတ်ထားလိုက် ပါမယ်။ ဒါပေမယ့် အဲဒီ အစက် ကို အနားသတ် ပေါ်မှာရှိတဲ့ အစက် အားလုံးကို စဉ်းစားလို့ မပြီးမချင်း တကယ် မဖျက်သေးပါဘူး။ အဲဒီလို နောက်ကျမှ ဖျက်တဲ့ အတွက် တစ်ခြား အစက် တွေကို စဉ်းစား နေတဲ့ အချိန်မှာ ပုံသဏ္ဌာန် ပြောင်းသွားတာကို ကာကွယ်နိုင်ပါတယ်။ ပထမ အဆင့် ကို အနားသတ်ပေါ်မှာရှိတဲ့ အစက် အားလုံးကို စဉ်းစာပြီးပြီဆိုတာနဲ့ ဖျက်ဖို့မှတ်ထားတဲ့ အစက် အားလုံးကို ဖျက်လိုက်ပါမယ်။ (အစက်ရဲ့ တန်ဖိုးကို သုည ပြောင်းလိုက်တာပါ။) ရလာတဲ့ ရလဒ် ပေါ်မှာ ဒုတိယ အဆင့် ကိုလဲ ပထမအဆင့် အတိုင်း ထပ်သုံးပါမယ်။ ဒီ အဆင့်နှစ်ဆင့်ကို အကြိမ်ကြိမ် အဖန်ဖန် ပြန်သုံးမှာ ဖြစ်ပြီး အကြိမ်တစ်ကြိမ်တိုင်းမှာ အောက်က လုပ်ငန်းလေးခုကို လုပ်ပါတယ်။ (၁) ပထမ အဆင့်ကို သုံးပြီး ဖျက်ရမယ့် အစက်တွေကို မှတ်ပါတယ်။ (၂) မှတ်ထားတဲ့ အစက်တွေကို ဖျက်ပါတယ်။ (၃) ဒုတိယ အဆင့်ကို သုံးပြီး ဖျက်ရမယ့် အစက်တွေကို မှတ်ပါတယ်။ (၄) မှတ်ထားတဲ့ အစက်တွေကို ဖျက်ပါတယ်။ ဒီအဆင့်တွေကို သုံးပြီး ပါးပါးသွားရင်း နောက်ဆုံး ဖျက်စရာ အစက် မကျန်တော့ဘူးဆိုရင် ရပ်လိုက်ပါမယ်။ ရလာတဲ့ ပုံက အရိုးဖြစ်ပါတယ်။ အချက် (c) p2.p4.p6 = 0 နဲ့ (d) p4.p6.p8 = 0 ကို တစ်ခါထဲ ပေါင်းပြီး (p4 = 0 or p6= 0) or (p2=0 and p8=0) လို့ တန်းစစ်လို့လဲရပါတယ်။ အဲဒီလိုပဲ (c') နဲ့ (d') ကိုလဲ (p2=0 or p8=0) or (p4=0 and p6=0) လို့ ပေါင်းစစ်လို့ ရပါတယ်။ Two Step Thinning အတွက်နမူနာ MATLAB ကုဒ်ကို ဒီမှာ (TSTeg.m) တွေ့နိုင်ပါတယ်။
ရှေ့မှာ ဖော်ပြခဲ့တဲ့ ကုဒ်တွေက နည်းတွေကိုနားလည်ဖို့ ရယ်၊ တစ်ခြား ပရိုဂရမ် ဘာသာတွေနဲ့ ပြန်ရေးဖို့ရယ် အတွက်တော့ အထောက် အကူ ဖြစ်မယ်ထင်ပါတယ်။ တကယ်တော့ MATLAB မှာ bwmorph ဆိုတဲ့ ဖန်ရှင်ကို သုံးလိုက်တာနဲ့ အရိုးကို တန်းရနိုင်ပါတယ်။ sk=bwmorph(bwImg,'skel',Inf); အဲဒီလိုခိုင်းလိုက်ရင် ထွက်လာတဲ့ ရလဒ် ကို အောက်မှာ ပြထားပါတယ်။
Reference: Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddins, "Digital Image Processing Using MATLAB", Second Edition, Mc Graw Hill (Asia), 2011.