Daraxtlarga asoslangan minimal segmentatsiya - Minimum spanning tree-based segmentation

Rasm segmentatsiyasi raqamli tasvirni o'xshash xususiyatlarga ega piksellar mintaqalariga bo'lishga intiladi, masalan. bir xillik.[1] Mintaqaning yuqori darajadagi vakili ob'ektlarni hisoblash yoki o'zgarishlarni aniqlash kabi tasvirni tahlil qilish vazifalarini soddalashtiradi, chunki mintaqa atributlari (masalan, o'rtacha intensivlik yoki shakl[2]) xom pikselga qaraganda osonroq taqqoslanishi mumkin.

Grafika asosidagi usullar uchun motivatsiya

Katta hajmdagi rasmlarni segmentatsiyalashni tezlashtirish uchun ishni bir nechta rasmlarga bo'lish mumkin edi CPU. Bunga erishish vositalaridan biri rasmlarni mustaqil ravishda qayta ishlanadigan plitkalarga bo'lishni o'z ichiga oladi. Ammo, agar qismlar segmentatsiya algoritmining minimal o'lchamlari talablariga javob bermasa, plitka chegarasida turgan mintaqalar bo'linishi yoki yo'qolishi mumkin. Arzimas vaqtinchalik echim bir-birining ustiga plitalar qo'yishni o'z ichiga oladi, ya'ni har bir protsessorga o'zining chegarasi atrofida qo'shimcha piksellarni ko'rib chiqishga imkon beradi. Afsuski, bu hisoblash yukini oshiradi, chunki plitka chegarasining ikkala tomonidagi protsessorlar ortiqcha ishlarni bajaradilar. Bundan tashqari, faqat plitka ustidagi bir-biridan kichikroq bo'lgan narsalarning saqlanishiga kafolat beriladi, demak, havo tasviridagi daryolar kabi uzun ob'ektlar hali ham bo'linishi mumkin. Ba'zi hollarda, mustaqil plitalarning natijalari haqiqiy natijalarni taxmin qilish uchun birlashtirilishi mumkin.[3]Muqobil variant grafik asosida segmentatsiya usullari shaklida mavjud. Grafiklarga xos bo'lgan ulanish ma'lumotlari asl tasvirning ayrim qismlari ustida mustaqil ishlarni bajarishga va ularni qayta ulab, aniq natijaga erishish uchun butun dunyo bo'ylab qayta ishlashga imkon beradi.

Tasvirlardan grafikalargacha

Imkoniyati tikish birgalikda mustaqil pastki rasmlar piksellarga ulanish ma'lumotlarini qo'shishga undaydi. Buni grafik sifatida ko'rish mumkin, uning tugunlari pikseldir, qirralari esa piksellar orasidagi bog'lanishni aks ettiradi. Buning oddiy va qiyosan kosmik jihatdan samarali varianti - bu a panjara grafigi, bu orqali har bir piksel to'rttadagi qo'shnilariga ulanadi asosiy yo'nalishlar. Pikselli qo'shnichilik munosabati nosimmetrik bo'lgani uchun, natijada olingan grafik yo'naltirilmagan va uning chekkalarining faqat yarmini (masalan, har bir pikselning sharqiy va janubiy qo'shnisi) saqlash kerak. Oxirgi qadam piksel o'xshashligi haqidagi ma'lumotlarni chekka og'irliklarda kodlashni talab qiladi, shunda asl rasm endi kerak bo'lmaydi. Oddiy holatda chekka og'irliklar piksel intensivligining farqi sifatida hisoblanadi.

Daraxtlarni segmentlarga ajratishning minimal algoritmlari

A minimal daraxt daraxti (MST) minimal vazn, tsikl - barcha tugunlar bog'langan holda grafik qirralarining bepul to'plami. 2004 yilda Felzensvval segmentatsiya usulini joriy qildi[4] asoslangan Kruskalning MST algoritmi. Qirralarning vazni ortib borayotgan tartibda ko'rib chiqiladi; agar bu grafada tsiklni keltirib chiqarmasa va piksellar mavjud mintaqalar piksellariga "o'xshash" bo'lsa, ularning so'nggi nuqta piksellari mintaqaga birlashtiriladi. A yordamida doimiy davrlarda tsikllarni aniqlash mumkin ajratilgan ma'lumotlar tuzilishi.[5] Piksel o'xshashligi evristika tomonidan baholanadi, u vaznni segment boshiga taqqoslaydi. Algoritm bir nechta ajratilgan MSTlarni chiqaradi, ya'ni o'rmon; har bir daraxt segmentga to'g'ri keladi. Algoritmning murakkabligi kvazi chiziqli, chunki chiziqli vaqt ichida qirralarni saralash mumkin hisoblash turi.

2009 yilda Vassenberg va boshq. algoritmini ishlab chiqdi[6] bir nechta mustaqil minimal o'rmonlarni hisoblab chiqadi va keyin ularni birlashtiradi. Bu moslamalarni plitka chegaralariga ajratmasdan parallel ishlov berishga imkon beradi. Belgilangan vazn chegarasi o'rniga, boshlang'ich ulangan komponent yorlig'i ostonaning pastki chegarasini baholash uchun foydalaniladi, bu ortiqcha va past darajali ajratishni kamaytirishi mumkin. O'lchovlar shuni ko'rsatadiki, amalga oshirish Felzenszvalbning ketma-ket algoritmidan kattaligi bo'yicha ustunroq.

2017 yilda Saglam va Baykan Primning minimal uzunlikdagi daraxtning ketma-ket ko'rinishini qo'lladilar va tasvirni segmentatsiyalashning yangi mezonini taklif qildilar.[7] Ular MST-ni Primning MST algoritmi bilan Fibonachchi Heap ma'lumotlar tuzilmasi yordamida quradilar. Uslub tez bajarilish vaqtida sinov tasvirlarida muhim muvaffaqiyatga erishadi.

Adabiyotlar

  1. ^ R. Xaralik, L. Shapiro: Tasvirlarni segmentatsiya qilish usullari. CVGIP 29 (1985 yil yanvar)
  2. ^ J. Iivarinen, M. Peura, J. Sarela, A. Visa: tartibsiz narsalar uchun estrodiol shakl tavsiflovchilarini taqqoslash. In: BMVC (1997) 430-439 betlar
  3. ^ M.-H. Chen, T. Pavlidis: Parallel arxitekturada segmentatsiya uchun rasm seaming. PAMI jildi 12 (6), 1990 yil iyun, 588-594 betlar
  4. ^ P. Felzenszvalb, D. Xuttenloxer: Grafika asosida tasvirni samarali segmentatsiyasi. IJCV 59 (2) (2004 yil sentyabr)
  5. ^ G. Xarfst, E. Rayngold: Union-Find ma'lumotlar tuzilishini potentsial asosli amortizatsiya qilingan tahlili. SIGACT 31 (2000 yil sentyabr) 86-95 betlar
  6. ^ J. Vassenberg, V. Middelmann, P. Sanders: Grafika asosida tasvir segmentatsiyasi uchun samarali parallel algoritm. In: Tasvirlar va naqshlarning kompyuter tahlili, LNCS jild. 5702 (sentyabr 2009) 1003-1010 betlar
  7. ^ A. Saglam, N. Baykan: Minimal uzunlikdagi daraxtlarni namoyish etishga asoslangan navbatdagi rasm segmentatsiyasi. Pattern Recognition Letters 87 (2017), pp 155-162

Tashqi havolalar