Phân đoạn ảnh màu bằng normalized cut_ncut

PHAÂN ÑOAÏN AÛNH MAØU BAÈNG NORMALIZED CUT_NCUT Taàm quan troïng vaø nhöõng khoù khaên cuûa vieäc gom nhoùm caùc ñoái töôïng mang tính tri giaùc cuûa con ngöôøi töø laâu ñaõ ñöïôc nghieân cöùu nhieàu trong caùc lónh vöïc cuûa thò giaùc maùy tính, ñaëc bieät trong lónh vöïc cuûa xöû lí aûnh. Laøm theá naøo ñeå phaân chia moät aûnh thaønh caùc taäp con. Ñoù laø nhöõng caâu hoûi maø ngöôøi ta ñaõ ñaët ra töø laâu vaø mong muoán tìm ñöôïc caâu traû lôøi. Trong vaøi chuïc naêm gaàn ñaây, coäng ñoàng caùc nhaø khoa hoïc ñaõ ñöa ra caùc phöông phaùp khaùc nhau trong lónh vöïc phaân ñoaïn aûnh nhö: phaân ñoaïn aûnh döïa vaøo caáu truùc gom nhoùm döïa vaøo caây, hay caùc thuaät toaùn taùch vaø troän aûnh döïa vaøo vuøng vaø caùc phöông phaùp thoáng keâ…nhaèm giaûi quyeát toát baøi toaùn. Tröôùc khi thöïc hieän baát kì moät thuaät toaùn naøo chuùng ta phaûi xaùc ñònh ñöôïc tieâu chuaån gì maø chuùng ta muoán toái öu vaø lieäu coù hay khoâng moät thuaät toaùn hieäu quaû cho vieäc thi haønh phöông phaùp ñoù. Trong baøi thöïc haønh phaân ñoaïn aûnh chuùng em söû duïng ôû ñaây”Normalized Cut” laø moät thuaät toaùn söû duïng phöông phaùp gom nhoùm theo lí thuyeát ñoà thò. Moãi aûnh goác seõ ñöïôc theå hieän moät moái quan heä töông öùng baèng vieäc chuyeån taäp aûnh goác ban ñaàu thaønh moät ñoà thò voâ höôùng coù troïng soá G=(E,V) maø moãi node trong G laø moät ñieåm trong khoâng gian ñaëc tröng vaø moãi caïnh ñöôïc hình thaønh giöõa 2 node, troïng löôïng treân moãi caïnh w(i,j) laø haøm ño söï töông ñoàng giöõa 2 node i, j. Trong vieäc gom nhoùm, ta coá gaéng phaân chia taäp ñænh thaønh nhöõng taäp rôøi nhau V1,V2,…,Vm vôùi ñoä ño söï töông töï cuûa nhöõng ñænh trong Vi thì cao coøn khi baêng qua nhöõng taäp Vj khaùc thì thaáp. Ñeå phaân hoaïch 1 ñoà thò, ta caàn ñaët ra nhöõng caâu hoûi sau: Tieâu chuaån chính xaùc naøo cho 1 söï phaân hoaïch toát? Baèng caùch naøo 1 phaân hoaïch nhö theá coù theå ñöôïc tính toaùn 1 caùch hieäu quaû? Vieäc gom nhoùm ñöôïc xem nhö söï phaân chia ñoà thò: Moät ñoà thò G=(V,E) ñöôïc phaân chia thaønh 2 taäp rôøi raïc A, B vôùi , baèng vieäc xoùa boû nhöõng caïnh keát noái 2 phaàn. Ñoä khoâng töông ñoàng giöõa 2 phaàn naøy coù theå ñöôïc tính nhö toång troïng löôïng cuûa nhöõng caïnh ñöôïc xoùa boû. Trong ngoân ngöõ lí thuyeát ñoà thò, noù goïi laø cut : (1) Moät söï phaân ñoâi ñoà thò toái öu laø caùi laøm cöïc tieåu giaù trò cut naøy. Ngöôøi ta ñaõ ñöa moät phöông phaùp gom nhoùm döïa treân tieâu chuaån cut cöïc tieåu naøy. Ñaëc bieät ta muoán phaân hoaïch 1 ñoà thò thaønh k ñoà thò con maø giaù trò cut cöïc ñaïi qua nhöõng taäp con ñöôïc cöïc tieåu. Baøi toaùn naøy coù theå ñöôïc giaûi quyeát baèng vieäc tìm nhöõng giaù trò cut cöïc tieåu. Tieâu chuaån toái öu toaøn cuïc naøy coù theå ñöôïc söû duïng ñeå taïo ra söï phaân ñoaïn toát treân caùc aûnh. Tuy nhieân tieâu chuaån cut cöïc tieåu thieân vò trong vieäc caét nhöõng taäp ñieåm(nhoû) rieâng bieät trong ñoà thò vì cut ñònh nghóa trong (1) taêng vôùi soá caïnh baêng qua 2 phaàn ñöôïc phaân chia. Hình 1 minh hoïa tröôøng hôïp nhö theá. Hình 1 Giaû söû troïng löôïng caùc caïnh tæ leä nghòch vôùi khoaûng caùch giöõa 2 node, ta thaáy cut phaân chia node n1 hoaëc node n2 seõ coù giaù trò raát nhoû. Thaät ra baát kì cut phaân chia nhöõng node rieâng reõ beân nöûa phaûi seõ coù giaù trò cut nhoû hôn cut phaân chia caùc node thaønh nöûa traùi vaø nöûa phaûi. Ñeå traùnh söï thieân vò ñoái vôùi vieäc phaân chia nhöõng taäp ñieåm nhoû naøy, ta ñöa ra 1 ñoä ño cuûa söï khoâng lieân keát giöõa 2 nhoùm. Thay vì xem giaù trò cuûa toång troïng löôïng caùc caïnh keát noái 2 phaân hoaïch, ñoä ño cuûa chuùng ta seõ tính giaù trò cut nhö moät tæ soá cuûa toaøn boä caùc caïnh keát noái ñeán taát caû caùc node cuûa ñoà thò. Ta goïi ñoä ño söï khoâng lieân keát naøy laø normalized cut. (2) vôùi laø toång troïng löôïng töø nhöõng node trong A ñeán taát caû caùc node cuûa ñoà thò. Vôùi söï ñònh nghóa cuûa söï khoâng lieân keát giöõa caùc nhoùm, cut phaân chia nhöõng ñieåm rieâng leû( nhoû) seõ khoâng coøn giaù trò Ncut nhoû, vì giaù trò cut haàu nhö chaéc chaén seõ laø tæ leä phaàn traêm cuûa toång caùc keát noái töø taäp nhoû ñoù ñeán taát caû caùc node khaùc. Trong tröôøng hôïp minh hoïa ôû hình 1, chuùng ta thaáy raèng giaù trò cut1 qua node n1 seõ laø 100% cuûa toaøn boä keát noái töø node ñoù. Treân tinh thaàn ñoù, chuùng ta coù theå ñònh nghóa moät ñoä ño cho toång normalized keát hôïp trong nhieàu nhoùm ñoái vôùi moät phaân hoaïch ñöôïc cho. (3) vôùi assoc(A,A) vaø assoc(B,B) laø toång troïng löôïng cuûa nhöõng caïnh keát noái nhöõng node trong A vaø B töông öùng. Chuùng ta thaáy moät laàn nöõa ñaây laø moät ñoä ño khoâng thieân vò,noù phaûn aùnh 1 caùch chaët cheõ nhö theá naøo nhöõng node trung bình trong nhoùm ñöôïc keát noái vôùi nhau. Moät thuoäc tính quan troïng khaùc cuûa vieäc ñònh nghóa söï lieân keát vaø khoâng lieân keát cuûa 1 söï phaân hoaïch laø chuùng coù lieân quan moät caùch töï nhieân theo coâng thöùc sau: (4) Do ñoù 2 tieâu chuaån phaân hoaïch maø chuùng ta mong muoán trong giaûi thuaät gom nhoùm laø vieäc cöïc tieåu hoùa söï khoâng lieân keát giöõa caùc nhoùm vaø vieäc cöïc ñaïi hoùa söï lieân keát trong noäi boä cuûa caùc nhoùm laø ñoàng nhaát vaø coù theå ñöôïc thoûa maõn ñoàng thôøi. Trong giaûi thuaät phaân ñoaïn aûnh ta seõ söû duïng normalized cut naøy nhö tieâu chuaån phaân hoaïch. Nhöng vieäc cöïc tieåu normalized cut chính xaùc laø baøi toaùn NP ñuû. Ta coù theå cöïc tieåu Ncut(A,B) baèng Phöông trình naøy coù theå ñöôïc giaûi quyeát baèng vieäc giaûi baøi toaùn giaù trò rieâng toång quaùt sau: (D-W)y=Dy Vector rieâng y nhoû nhaát thöù 2 laø lôøi giaûi cuûa baøi toaùn normalized cut Giaûi thuaät: Cho 1 aûnh I . xaây döïng ñoà thò troïng soá G=(V,E) vôùi moãi node cuûa ñoà thò laø moät pixel cuûa aûnh. Ñaët N laø soá node cuûa ñoà thò N=|V| Böôùc 1: Xaây döïng ma traän töông ñoàng ñoái xöùng W kích thöôùc N x N với W(i,j)=wij neáu vôùi X(i) laø vò trí khoâng gian cuûa node i nghóa laø toïa ñoä trong aûnh goác I vaø F(i) laø vector ñaëc tröng ñöïôc ñònh nghóa nhö sau: F(i)=1 ñoái vôùi taäp ñieåm phaân ñoaïn F(i)=I(i) giaù trò cöôøng ñoä cho nhöõng aûnh xaùm F(i)=[ v,u.s.sin(h),v.s.cos(h)](i) vôùi h,s,v laø giaù trò HSV ñoái vôùi phaân ñoaïn aûnh maøu F(i) Ñaët laø toång troïng löôïng töø node i ñeán taát caû caùc node khaùc trong ñoà thò. Xaây döïng ma traän ñöôøng cheùo D kích thước N x N vôùi caùc di treân ñöôøng cheùo cuûa noù Böôùc 2: Giaûi baøi toaùn giaù trò rieâng (D-W)y=Dy vaø laáy vector rieâng öùng vôùi trò rieâng nhoû nhaát thöù 2. Trong Matlab coù haøm eigs ñeå giaûi baøi toaùn giaù trò rieâng. Böôùc 3: Söû duïng vector rieâng ñeå phaân ñoâi ñoà thò. Trong tröôøng hôïp lí töôûng,vector rieâng seõ chæ laáy 2 giaù trò rôøi raïc vaø daáu seõ cho ta bieát chính xaùc phaân hoaïch ñoà thò nhö theá naøo (A={Vi|yi >0}, B= {Vi|yi<=0}). Tuy nhieân y laáy giaù trò thöïc do ñoù ta caàn choïn 1 ñieåm caét. Coù 1 vaøi caùch nhö: Laáy 0 Laáy trung bình Tìm 1 ñieåm caét maø keát quaû Ncut(A,B) ñöôïc cöïc tieåu Ñieåm caét maø cöïc tieåu giaù trò Ncut cöïc tieåu với y=(1+x) – b(1- x) với b= với vôùi x laø moät vector N chieàu, xi=1 neáu node I trong A vaø -1 ngöôïc laïi. Ñeå tìm Ncut cöïc tieåu, ta caàn thöû nhöõng giaù trò ñieåm caét khaùc nhau. Ñieåm caét toái öu gaàn vôùi giaù trò trung bình cuûa nhöõng vector rieâng thu ñöôïc. Matlab coù haøm fminsearch phuø hôïp cho muïc ñích naøy. Böôùc 4: Laëp laïi vieäc chia ñoâi moät caùch ñeä quy. Döøng neáu giaù trò Ncut lôùn hôn giaù trò ngöôõng ñaõ ñöôïc chæ tröôùc(giaù trò Ncut lôùn coù nghóa laø khoâng coù söï phaân hoaïch ñieåm roõ raøng). Hôn nöõa, döøng khi toång soá node trong phaân hoaïch (aera) nhoû hôn moät giaù trò ngöôõng ñöïôc chæ tröôùc