Kondensatsiya algoritmi - Condensation algorithm

The kondensatsiya algoritmi (Conikkilamchi Density targ'ib qilingaation) a kompyuterni ko'rish algoritm. Asosiy dastur aniqlash va trek tartibsiz muhitda harakatlanadigan ob'ektlar konturi. Ob'ektlarni kuzatib borish kompyuterni ko'rishning eng asosiy va qiyin jihatlaridan biri bo'lib, odatda bu zaruriy shartdir ob'ektni aniqlash. Ob'ektning konturini rasmdagi qaysi pikselni aniqlay olish unchalik ahamiyatsiz muammo. Kondensatsiya a ehtimollik algoritmi bu muammoni hal qilishga urinishlar.

Algoritmning o'zi Isard va tomonidan batafsil tavsiflangan Bleyk nashrida Xalqaro kompyuter ko'rishi jurnali 1998 yilda.^[1] Algoritmning eng qiziqarli tomonlaridan biri shundaki, u tasvirning har bir pikselida hisoblab chiqmaydi. Aksincha, ishlov berish uchun piksellar tasodifiy tanlanadi va faqat piksellarning bir qismi qayta ishlanadi. Harakatlanayotgan narsa haqidagi bir nechta farazlarni tabiiy ravishda yondashuvning ehtimollik xususiyati qo'llab-quvvatlaydi. Baholash funktsiyalari asosan ushbu sohadagi avvalgi ishlardan kelib chiqadi va ko'plab standart statistik yondashuvlarni o'z ichiga oladi. Ushbu ishning asl qismi zarrachalar filtrini baholash texnikasini qo'llashdir.

Algoritmni yaratishga qodir emasligi ilhom bergan Kalman filtrlash muhim fon tartibsizliklari mavjud bo'lganda ob'ektni kuzatishni yaxshi bajarish. Tartibsizlikning mavjudligi, ob'ekt holati uchun ehtimollik taqsimotini ishlab chiqarishga intiladi ko'p modali va shuning uchun Kalman filtri tomonidan yomon modellashtirilgan. Kondensatsiya algoritmi eng umumiy shaklda ob'ektning o'lchovlari yoki o'lchovlari bo'yicha taxminlarni talab qilmaydi.

Algoritmga umumiy nuqtai

Kondensatsiya algoritmi a tomonidan tasvirlangan ob'ektning konformatsiyasini baholash muammosini hal qilishga intiladi vektor ${ displaystyle mathbf {x_ {t}}}$ vaqtida ${ displaystyle t}$ , berilgan kuzatishlar ${ displaystyle mathbf {z_ {1}, ..., z_ {t}}}$ joriy vaqtni o'z ichiga olgan holda tasvirlardagi aniqlangan xususiyatlarning. Algoritm davlatga baho beradi shartli ehtimollik zichligi ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ faktorli namuna olish asosida chiziqli bo'lmagan filtrni qo'llash orqali va uni rivojlanishi deb hisoblash mumkin Monte-Karlo usuli.^[1] ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ oldingi mosliklar va o'lchovlar asosida ob'ektlar uchun mumkin bo'lgan konformatsiyalar ehtimoli tasviridir. Yoğuşma algoritmi a generativ model^[2] chunki u modellashtiradi qo'shma tarqatish ob'ekt va kuzatuvchi.

Ob'ektning hozirgi vaqtda shartli zichligi ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ vaznli, vaqt bilan indekslangan namuna to'plami sifatida baholanadi ${ displaystyle {s_ {t} ^ {(n)}, n = 1, ..., N }}$ og'irliklar bilan ${ displaystyle pi _ {t} ^ {(n)}}$ . N - tanlangan namuna to'plamlari sonini belgilaydigan parametr. Amalga oshirish ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ to'plamdan almashtirish bilan namuna olish yo'li bilan olinadi ${ displaystyle s_ {t}}$ ning mos keladigan elementiga teng ehtimollik bilan ${ displaystyle pi _ {t}}$ .^[1]

Ob'ekt dinamikasi vaqtinchalik Markov zanjirini tashkil qiladi va kuzatuvlar mavjud degan taxminlar mustaqil bir-birining va dinamikasi kondensatlash algoritmini amalga oshirishni osonlashtiradi. Birinchi taxmin ob'ektning dinamikasini butunlay shartli zichlik bilan aniqlashga imkon beradi ${ displaystyle p ( mathbf {x_ {t}} | mathbf {x_ {t-1}})}$ . Tomonidan belgilanadigan tizim dinamikasi modeli ${ displaystyle p ( mathbf {x_ {t}} | mathbf {x_ {t-1}})}$ algoritm uchun ham tanlanishi kerak va umuman ikkalasini ham o'z ichiga oladi deterministik va stoxastik dinamikasi.

Algoritmni vaqtni boshlash orqali umumlashtirish mumkin ${ displaystyle t = 0}$ va har safar uchta qadam t:

Boshlash

Dastlabki taqsimotga muvofiq namuna olish orqali dastlabki namunalar to'plamini va og'irliklarini hosil qiling. Masalan, sifatida belgilang Gauss va og'irliklarni bir-biriga tenglashtiring.

Takroriy protsedura

O'zgartirish bilan namuna ${ displaystyle N}$ to'plamdan vaqt ${ displaystyle {s_ {0} ^ {(n)}, n = 1, ..., N }}$ ehtimollik bilan ${ displaystyle { pi _ {0} ^ {(n)}, n = 1, ..., N }}$ amalga oshirishni yaratish ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ .
O'rganilgan dinamikani qo'llang ${ displaystyle p ( mathbf {x_ {t}} | mathbf {x_ {t-1}})}$ ushbu yangi to'plamning har bir elementiga, yangi to'plamni yaratish uchun ${ displaystyle {s_ {t} ^ {(n)} }}$ .
Hozirgi kuzatuvni hisobga olish ${ displaystyle mathbf {z_ {t}}}$ , o'rnatilgan ${ displaystyle pi _ {t} ^ {(n)} = { frac {p ( mathbf {z_ {t}} | s ^ {(n)})} { sum _ {j = 1} ^ {N} p ( mathbf {z_ {t}} | s ^ {(j)})}}}$ har bir element uchun ${ displaystyle {s_ {t} ^ {(n)} }}$ .

Ushbu algoritm ehtimollik taqsimotini chiqaradi ${ displaystyle p ( mathbf {x_ {t}} | mathbf {z_ {1}, ..., z_ {t}})}$ to'g'ridan-to'g'ri kuzatiladigan ob'ektning o'rtacha holatini va boshqasini hisoblash uchun ishlatilishi mumkin lahzalar kuzatiladigan ob'ekt.

Jamg'arma og'irliklari o'rniga samaraliroq namuna olish uchun foydalanish mumkin.^[1]

Amalga oshirish masalalari

Ob'ektni kuzatish real vaqtda maqsad bo'lishi mumkinligi sababli, algoritm samaradorligini ko'rib chiqish muhim ahamiyat kasb etadi. Kondensatsiya algoritmi Kalman filtrlash uchun zarur bo'lgan Rikatti tenglamasining hisoblash intensivligi bilan taqqoslaganda nisbatan sodda. Parametr ${ displaystyle N}$ namunalar to'plamidagi namunalar sonini aniqlaydigan, samaradorlik bilan ishlash ko'rsatkichlariga nisbatan aniq kelishuvga olib keladi.

Algoritm samaradorligini oshirish usullaridan biri bu ob'ekt shaklini namoyish etish uchun past darajadagi erkinlik modelini tanlashdir. Isard 1998 tomonidan ishlatilgan model - ning lineer parametrlanishi B-splinalar unda splinelar ma'lum konfiguratsiyalar bilan cheklangan. Tegishli konfiguratsiyalar analitik ravishda bir nechta ko'rinishdagi konturlarning kombinatsiyasini, turli xil pozitsiyalardagi va asosiy tarkibiy qismlarni tahlil qilish (PCA) deformatsiyalanayotgan narsada.

Isard va Bleyk ob'ekt dinamikasini modellashtiradi ${ displaystyle p ( mathbf {x_ {t}} | mathbf {x_ {t-1}})}$ ikkinchi tartib sifatida farq tenglamasi deterministik va stoxastik komponentlar bilan: ${ displaystyle p ( mathbf {x_ {t}} | mathbf {x_ {t-1}}) propto e ^ {- { frac {1} {2}} || B ^ {- 1} ( ( mathbf {x_ {t}} - mathbf { bar {x}}) -A ( mathbf {x_ {t-1}} - mathbf { bar {x}})) || ^ {2 })}}$

qayerda ${ displaystyle mathbf { bar {x}}}$ davlatning o'rtacha qiymati va ${ displaystyle A}$ , ${ displaystyle B}$ dinamik modelning aniqlangan va stoxastik tarkibiy qismlarini ifodalovchi matritsalar. ${ displaystyle A}$ , ${ displaystyle B}$ va ${ displaystyle mathbf { bar {x}}}$ orqali baholanadi Maksimal ehtimollikni baholash ob'ekt odatdagi harakatlarni amalga oshirayotganda.^[1]^[3]

Kuzatish modeli ${ displaystyle p ( mathbf {z} | mathbf {x})}$ ma'lumotlardan to'g'ridan-to'g'ri taxmin qilish mumkin emas, ularni taxmin qilish uchun taxminlarni talab qilish kerak. Isard 1998, ob'ektni ko'rinmas holga keltirishi mumkin bo'lgan tartibsizlik a Poisson tasodifiy jarayoni fazoviy zichlik bilan ${ displaystyle lambda}$ va har qanday haqiqiy maqsad o'lchovi xolis va odatda taqsimlanishi standart og'ish ${ displaystyle sigma}$ .

Kondensatsiyaning asosiy algoritmi bitta ob'ektni o'z vaqtida kuzatib borish uchun ishlatiladi. Bir vaqtning o'zida sahnada bir nechta ob'ektni kuzatib borish uchun bir nechta ob'ektlarning mumkin bo'lgan holatlarini tavsiflash uchun bitta ehtimollik taqsimoti yordamida kondensatlash algoritmini kengaytirish mumkin.^[4]

Tartibsizlik ob'ekt ehtimolini taqsimotini bir nechta tepalikka bo'linishiga olib kelishi mumkinligi sababli, har bir tepalik ob'ekt konfiguratsiyasi haqidagi farazni anglatadi. Tekislashtirish - bu bir necha cho'qqilar ta'sirini kamaytirish uchun kuzatuv tugagandan so'ng, o'tgan va kelajakdagi o'lchovlarga asoslangan taqsimotni konditsionerlashning statistik uslubi.^[5] Yuzalashtirishni to'g'ridan-to'g'ri real vaqtda amalga oshirish mumkin emas, chunki u kelajakdagi o'lchovlar haqida ma'lumot talab qiladi.

Ilovalar

Algoritm ko'rishga asoslangan holda ishlatilishi mumkin robotlarni lokalizatsiya qilish mobil robotlar.^[6] Ob'ektning sahnadagi holatini kuzatish o'rniga, kamera platformasining holati kuzatiladi. Bu atrof-muhitning vizual xaritasini hisobga olgan holda kamera platformasini global miqyosda joylashtirishga imkon beradi.

Yoğuşma algoritmining kengaytmalari ham ishlatilgan inson imo-ishoralarini taniy olish tasvirlar ketma-ketligida. Kondensatsiya algoritmining ushbu qo'llanilishi inson bilan kompyuterning o'zaro ta'sir doirasiga ta'sir qiladi. U taxtada foydalanuvchining oddiy imo-ishoralarini tanib olish, ularni bosib chiqarish yoki saqlash uchun taxtalarning mintaqalarini tanlash kabi harakatlarni boshqarish uchun ishlatilgan.^[7] Xuddi shu sahnada bir nechta avtomashinalarni kuzatishda boshqa kengaytmalar ham ishlatilgan.^[8]

Yoğuşma algoritmi uchun ham ishlatilgan yuzni aniqlash video ketma-ketlikda.^[9]

Resurslar

Kondensatsiya algoritmini amalga oshirish C topishingiz mumkin Maykl Isardning veb-sayti.

Amalga oshirish MATLAB saytida topish mumkin Mathworks File Exchange.

Yordamida amalga oshirishga misol OpenCV kutubxonasini OpenCV forumlari.

Shuningdek qarang

Zarrachalar filtri - Kondensatsiya - bu konturni kuzatishda namuna olishning ahamiyatini qayta aniqlash (SIR) bahosini qo'llashdir

Adabiyotlar

^ ^a ^b ^v ^d ^e Isard, M .; Bleyk, A (1998 yil avgust). "Kondensatsiya - vizual kuzatuvning shartli zichligi". Xalqaro kompyuter ko'rishi jurnali. 29 (1): 5–28. doi:10.1023 / A: 1008078328650.
^ Sminchisesku, C .; Kanaujiya, A .; Metaxas, D.N. (noyabr 2007). "BM3E: Vizual kuzatuv uchun diskriminatsion zichlikni ko'paytirish". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 29 (11): 2030–2044. CiteSeerX 10.1.1.78.1751. doi:10.1109 / tpami.2007.1111. PMID 17848782.
^ Bleyk, Andrea; Isard, Maykl; Reynard, Devid (1995 yil oktyabr). "Konturlarning vizual harakatini kuzatishni o'rganish". Sun'iy intellekt. 78 (1–2): 179–212. doi:10.1016/0004-3702(95)00032-1.
^ Koller-Meier, Ester B.; Ade, Frank (2001 yil 28-fevral). "Kondensatsiya algoritmi yordamida bir nechta ob'ektlarni kuzatish". Robototexnika va avtonom tizimlar. 34 (2–3): 93–105. doi:10.1016 / s0921-8890 (00) 00114-7.
^ Isard, Maykl; Bleyk, Endryu (2006 yil 28-may). Kondensat uchun tekislovchi filtr. Kompyuter fanidan ma'ruza matnlari. 1406. 767-781-betlar. doi:10.1007 / BFb0055703. ISBN 978-3-540-64569-6.
^ Dellaert, F.; Burgard, V .; Tulki, D .; Thrun, S. (1999). "Vizyonga asoslangan mobil robotni lokalizatsiya qilish uchun Kondensatsiya algoritmidan foydalanish". Kompyuterni ko'rish va naqshni aniqlash. 2: 588–594. doi:10.1109 / CVPR.1999.784976. ISBN 0-7695-0149-4.
^ Qora, M.J .; Jepson, AD (14 aprel 1998). "Kondensatsiya algoritmi yordamida vaqtinchalik traektoriyalarni tanib olish". Avtomatik yuz va imo-ishoralarni aniqlash: 16–21. CiteSeerX 10.1.1.154.1402. doi:10.1109 / AFGR.1998.670919. ISBN 0-8186-8344-9.
^ Meier, EB .; Ade, Frank (1999). "Kondensatsiya algoritmidan foydalangan holda avtoulovlarni masofadagi tasvirlarda kuzatib borish". Aqlli transport tizimlari: 129–134. doi:10.1109 / ITSC.1999.821040. ISBN 0-7803-4975-X.
^ Chjou, Shaohua; Krueger, V .; Chellappa, R. (2002 yil 21-may). "Videodan yuzni tanib olish: Kondensatsiya usuli". Avtomatik yuz va imo-ishoralarni aniqlash: 221–226. doi:10.1109 / AFGR.2002.1004158. ISBN 0-7695-1602-5.

[Isard1998-1] v ^d ^e Isard, M .; Bleyk, A (1998 yil avgust). "Kondensatsiya - vizual kuzatuvning shartli zichligi". Xalqaro kompyuter ko'rishi jurnali. 29 (1): 5–28. doi:10.1023 / A: 1008078328650.

[2] Sminchisesku, C .; Kanaujiya, A .; Metaxas, D.N. (noyabr 2007). "BM3E: Vizual kuzatuv uchun diskriminatsion zichlikni ko'paytirish". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 29 (11): 2030–2044. CiteSeerX 10.1.1.78.1751. doi:10.1109 / tpami.2007.1111. PMID 17848782.

[3] Bleyk, Andrea; Isard, Maykl; Reynard, Devid (1995 yil oktyabr). "Konturlarning vizual harakatini kuzatishni o'rganish". Sun'iy intellekt. 78 (1–2): 179–212. doi:10.1016/0004-3702(95)00032-1.

[4] Koller-Meier, Ester B.; Ade, Frank (2001 yil 28-fevral). "Kondensatsiya algoritmi yordamida bir nechta ob'ektlarni kuzatish". Robototexnika va avtonom tizimlar. 34 (2–3): 93–105. doi:10.1016 / s0921-8890 (00) 00114-7.

[5] Isard, Maykl; Bleyk, Endryu (2006 yil 28-may). Kondensat uchun tekislovchi filtr. Kompyuter fanidan ma'ruza matnlari. 1406. 767-781-betlar. doi:10.1007 / BFb0055703. ISBN 978-3-540-64569-6.

[6] Dellaert, F.; Burgard, V .; Tulki, D .; Thrun, S. (1999). "Vizyonga asoslangan mobil robotni lokalizatsiya qilish uchun Kondensatsiya algoritmidan foydalanish". Kompyuterni ko'rish va naqshni aniqlash. 2: 588–594. doi:10.1109 / CVPR.1999.784976. ISBN 0-7695-0149-4.

[7] Qora, M.J .; Jepson, AD (14 aprel 1998). "Kondensatsiya algoritmi yordamida vaqtinchalik traektoriyalarni tanib olish". Avtomatik yuz va imo-ishoralarni aniqlash: 16–21. CiteSeerX 10.1.1.154.1402. doi:10.1109 / AFGR.1998.670919. ISBN 0-8186-8344-9.

[8] Meier, EB .; Ade, Frank (1999). "Kondensatsiya algoritmidan foydalangan holda avtoulovlarni masofadagi tasvirlarda kuzatib borish". Aqlli transport tizimlari: 129–134. doi:10.1109 / ITSC.1999.821040. ISBN 0-7803-4975-X.

[9] Chjou, Shaohua; Krueger, V .; Chellappa, R. (2002 yil 21-may). "Videodan yuzni tanib olish: Kondensatsiya usuli". Avtomatik yuz va imo-ishoralarni aniqlash: 221–226. doi:10.1109 / AFGR.2002.1004158. ISBN 0-7695-1602-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]