WikiDer > O'rtacha siljish

Mean shift

O'rtacha siljish a parametrsiz bo'shliq a maksimal darajalarini aniqlash uchun tahlil texnikasi zichlik funktsiyasi, deb nomlangan rejimi- algoritmni qidirish.^[1] Ilova domenlariga quyidagilar kiradi klaster tahlili yilda kompyuterni ko'rish va tasvirni qayta ishlash.^[2]

Tarix

O'rtacha almashtirish tartibi dastlab 1975 yilda Fukunaga va Hostetler tomonidan taqdim etilgan.^[3]

Umumiy nuqtai

O'rtacha siljish - bu maksimal darajani aniqlash protsedurasi rejimlar- bu funktsiyadan olingan alohida ma'lumotlar berilgan zichlik funktsiyasi.^[1] Bu takroriy usul va biz dastlabki taxmin bilan boshlaymiz ${displaystyle x}$ . Qilsin yadro funktsiyasi ${displaystyle K (x_ {i} -x)}$ berilishi kerak. Ushbu funktsiya o'rtacha qiymatni qayta baholash uchun yaqin nuqtalarning og'irligini aniqlaydi. Odatda a Gauss yadrosi joriy taxmingacha bo'lgan masofada, ${displaystyle K (x_ {i} -x) = e ^ {- c || x_ {i} -x || ^ {2}}}$ . Belgilangan oynadagi zichlikning o'rtacha og'irligi ${displaystyle K}$ bu

{displaystyle m (x) = {frac {sum _ {x_ {i} in N (x)} K (x_ {i} -x) x_ {i}} {sum _ {x_ {i} N (x)) } K (x_ {i} -x)}}}

qayerda ${displaystyle N (x)}$ ning mahallasi ${displaystyle x}$ , buning uchun ochkolar to'plami ${displaystyle K (x_ {i}) eq 0}$ .

Farqi ${displaystyle m (x) -x}$ deyiladi o'rtacha siljish Fukunaga va Hostetlerda.^[3] The o'rtacha siljish algoritmi endi o'rnatadi ${displaystyle xleftarrow m (x)}$ , va qadar baholashni takrorlaydi ${displaystyle m (x)}$ yaqinlashadi.

O'rtacha siljish algoritmi ko'plab dasturlarda keng qo'llanilgan bo'lsa-da, yuqori o'lchovli kosmosda umumiy yadro yordamida algoritm yaqinlashuvining qat'iy isboti hali ham ma'lum emas.^[4] Aliyari G'assabeh o'rtacha siljish algoritmini bir o'lchovli bilan differentsial, qavariq va qat'iy kamayib boruvchi profil funktsiyasi bilan yaqinlashishini ko'rsatdi.^[5] Biroq, bir o'lchovli ishda haqiqiy dunyo dasturlari cheklangan. Bundan tashqari, algoritmning yuqori o'lchamdagi (yoki ajratilgan) statsionar nuqtalarning cheklangan soni bilan yaqinlashuvi isbotlangan.^[4]^[6] Shu bilan birga, umumiy yadro funktsiyasi uchun cheklangan (yoki ajratilgan) statsionar nuqtalarga ega bo'lish uchun etarli shartlar ta'minlanmagan.

Gaussning o'rtacha siljishi - bu Kutish - maksimallashtirish algoritmi.^[7]

Tafsilotlar

Ma'lumotlar cheklangan to'plam bo'lsin ${displaystyle S}$ ichiga o'rnatilgan ${displaystyle n}$ - o'lchovli Evklid fazosi, ${displaystyle X}$ . Ruxsat bering ${displaystyle K}$ ning xarakterli funktsiyasi bo'lgan tekis yadro bo'ling ${displaystyle lambda}$ -bol ${displaystyle X}$ ,

${displaystyle K (x) = {egin {case} 1 & {ext {if}} | x | leq lambda 0 & {ext {if}} | x |> lambda end {case}}}$

Algoritmning har bir takrorlanishida, ${displaystyle sleftarrow m (lar)}$ hamma uchun amalga oshiriladi ${displaystyle sin S}$ bir vaqtning o'zida. Demak, birinchi savol - siyrak namunalar to'plami berilgan zichlik funktsiyasini qanday baholash. Oddiy yondashuvlardan biri bu ma'lumotlarni silliqlashtirishdir, masalan, ularni kenglikning sobit yadrosi bilan yig'ish ${displaystyle h}$ ,

${displaystyle f (x) = sum _ {i} K (x-x_ {i}) = sum _ {i} kleft ({frac {| x-x_ {i} | ^ {2}} {h ^ {2 }}} kun)$

qayerda ${displaystyle x_ {i}}$ kirish namunalari va ${displaystyle k (r)}$ yadro funktsiyasi (yoki Parzen oynasi). ${displaystyle h}$ algoritmdagi yagona parametr bo'lib, tarmoqli kengligi deb ataladi. Ushbu yondashuv sifatida tanilgan yadro zichligini baholash yoki Parzen oynasi texnikasi. Bir marta biz hisoblab chiqdik ${displaystyle f (x)}$ yuqoridagi tenglamadan biz uning lokal maksimumini gradient ko'tarilish yoki boshqa optimallashtirish texnikasi yordamida topishimiz mumkin. Ushbu "qo'pol kuch" yondashuvidagi muammo shundaki, yuqori o'lchovlar uchun uni baholashni hisoblash taqiqlanadi ${displaystyle f (x)}$ to'liq qidiruv maydonida. Buning o'rniga o'rtacha siljish optimallashtirish adabiyotida ma'lum bo'lgan variantni ishlatadi bir necha marta qayta boshlash gradyanli tushish. Mahalliy maksimal miqdorni taxmin qilishdan boshlab, ${displaystyle y_ {k}}$ , bu tasodifiy kirish nuqtasi bo'lishi mumkin ${displaystyle x_ {1}}$ , o'rtacha siljish zichlik bahosining gradyanini hisoblab chiqadi ${displaystyle f (x)}$ da ${displaystyle y_ {k}}$ va shu yo'nalishda tepalikka qadam tashlaydi.^[8]

Yadro turlari

Yadro ta'rifi: Keling ${displaystyle X}$ bo'lishi ${displaystyle n}$ - o'lchovli Evklid fazosi, ${displaystyle mathbb {R} ^ {n}}$ . Ning normasi ${displaystyle x}$ manfiy bo'lmagan raqam, ${displaystyle | x | ^ {2} = x ^ {op} xgeq 0}$ . Funktsiya ${displaystyle K: Xightarrow mathbb {R}}$ agar mavjud bo'lsa yadro deb aytiladi a profil, ${displaystyle k: [0, yaroqsiz [ightarrow mathbb {R}}$ , shu kabi

${displaystyle K (x) = k (| x | ^ {2})}$ va

k manfiy emas.
k o'smaydi: ${displaystyle k (a) geq k (b)}$ agar ${displaystyle a$ .
k qismli uzluksiz va ${displaystyle int _ {0} ^ {infty} k (r), dr$

O'rtacha siljish uchun eng ko'p ishlatiladigan ikkita yadro profillari:

Yassi yadro

${displaystyle k (x) = {egin {case} 1 & {ext {if}} xleq lambda 0 & {ext {if}} x> lambda end {case}}}$

Gauss yadrosi

${displaystyle k (x) = e ^ {- {frac {x ^ {2}} {2sigma ^ {2}}}},}$

bu erda standart og'ish parametri ${displaystyle sigma}$ tarmoqli kengligi parametri sifatida ishlaydi, ${displaystyle h}$ .

Ilovalar

Klasterlash

Ikki o'lchovli kosmosdagi nuqta to'plamini ko'rib chiqing. Markazi C va yadrosi r radiusga ega bo'lgan dumaloq oynani qabul qiling. O'rtacha siljish - bu tepalikka ko'tarilish algoritmi, bu yadroni iterativ ravishda yaqinlashguncha yuqori zichlik mintaqasiga o'tkazishni o'z ichiga oladi. Har bir siljish o'rtacha siljish vektori bilan belgilanadi. O'rtacha siljish vektori har doim zichlikning maksimal o'sish yo'nalishi tomon ishora qiladi. Har bir takrorlashda yadro sentroidga yoki uning ichidagi nuqtalarning o'rtacha qiymatiga o'tkaziladi. Ushbu o'rtacha qiymatni hisoblash usuli yadro tanloviga bog'liq. Agar bu holda yassi yadro o'rniga Gauss yadrosi tanlangan bo'lsa, unda har bir nuqtaga avvaliga yadro markazidan masofa oshgani sayin eksponentsial ravishda yemiriladigan og'irlik beriladi. Yaqinlashishda siljish yadro ichida ko'proq nuqtalarni joylashtiradigan yo'nalish bo'lmaydi.

Kuzatish

O'rtacha siljish algoritmi vizual kuzatuv uchun ishlatilishi mumkin. Bunday sodda algoritm avvalgi rasmdagi ob'ektning rangli gistogrammasi asosida yangi rasmda ishonch xaritasini yaratadi va ob'ektning eski holatiga yaqin joyda ishonch xaritasining eng yuqori nuqtasini topish uchun o'rtacha siljishni ishlatadi. Ishonch xaritasi - bu yangi rasmdagi ehtimollik zichligi funktsiyasi bo'lib, yangi rasmning har bir pikseliga ehtimollik beriladi, bu avvalgi rasmdagi ob'ektda piksel rangining paydo bo'lish ehtimoli. Bir nechta algoritmlar, masalan, yadroga asoslangan ob'ektni kuzatish,^[9] ansamblni kuzatish,^[10] CAMshift ^[11]^[12] ushbu g'oyani kengaytiring.

Yumshoq

Ruxsat bering ${displaystyle x_ {i}}$ va ${displaystyle z_ {i}, i = 1, ..., n,}$ bo'lishi ${displaystyle d}$ - qo'shma kenglik doirasidagi o'lchovli kirish va filtrlangan tasvir piksellari. Har bir piksel uchun

Boshlang ${displaystyle j = 1}$ va ${displaystyle y_ {i, 1} = x_ {i}}$
Hisoblash ${displaystyle y_ {i, j + 1}}$ ga binoan ${displaystyle m (cdot)}$ yaqinlashguncha, ${displaystyle y = y_ {i, c}}$ .
Tayinlang ${displaystyle z_ {i} = (x_ {i} ^ {s}, y_ {i, c} ^ {r})}$ . S va r ustki yozuvlari mos ravishda vektorning fazoviy va intervalli qismlarini bildiradi. Topshiriq shuni ko'rsatadiki, fazoviy joylashish o'qidagi filtrlangan ma'lumotlar konvergentsiya nuqtasining diapazon komponentiga ega bo'ladi. ${displaystyle y_ {i, c} ^ {r}}$ .

Kuchlar

O'rtacha siljish - bu haqiqiy ma'lumotlarni tahlil qilish uchun mos keladigan dasturdan mustaqil vosita.
Ma'lumot klasterlarida oldindan belgilangan shaklni qabul qilmaydi.
U o'zboshimchalik bilan bo'shliqlar bilan ishlashga qodir.
Jarayon bitta parametrni tanlashga bog'liq: tarmoqli kengligi.
O'tkazish qobiliyati / oynaning o'lchamlari 'h' farqli o'laroq jismoniy ma'noga ega k- degani.

Zaif tomonlari

Oynaning o'lchamini tanlash ahamiyatsiz emas.
Oynaning mos bo'lmagan kattaligi rejimlarni birlashishiga yoki qo'shimcha "sayoz" rejimlarni yaratishiga olib kelishi mumkin.
Ko'pincha moslashuvchan oyna o'lchamidan foydalanishni talab qiladi.

Mavjudligi

Algoritmning variantlarini mashinada o'rganish va tasvirni qayta ishlash to'plamlarida topish mumkin:

ELKI. Ko'plab klaster algoritmlari bilan Java ma'lumotlarini qazib olish vositasi.
ImageJ. O'rtacha siljish filtri yordamida tasvirni filtrlash.
mlpack. Ikki daraxtli algoritmga asoslangan samarali dastur.
OpenCV cvMeanShift usuli orqali o'rtacha siljishni amalga oshirishni o'z ichiga oladi
Orfeo asboblar qutisi. C ++ dasturi.
Scikit-o'rganing Numpy / Python dasturi qo'shni nuqtalarni samarali qidirish uchun shar daraxtidan foydalanadi

Shuningdek qarang

Adabiyotlar

^ ^a ^b Cheng, Yizong (1995 yil avgust). "O'rtacha siljish, rejimni qidirish va klasterlash". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 17 (8): 790–799. CiteSeerX 10.1.1.510.1222. doi:10.1109/34.400568.
^ Komaniciu, Dorin; Piter Meer (2002 yil may). "O'rtacha siljish: fazoviy tahlilga nisbatan qat'iy yondashuv". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 24 (5): 603–619. CiteSeerX 10.1.1.160.3832. doi:10.1109/34.1000236.
^ ^a ^b Fukunaga, Keinosuke; Larri D. Hostetler (1975 yil yanvar). "Naqshni tanib olishda qo'llaniladigan zichlik funktsiyasi gradiyentini baholash". Axborot nazariyasi bo'yicha IEEE operatsiyalari. 21 (1): 32–40. doi:10.1109 / TIT.1975.1055330.
^ ^a ^b Aliyari Gassabeh, Youness (2015-03-01). "O'rtacha siljish algoritmini Gauss yadrosi bilan yaqinlashtirish uchun etarli shart". Ko'p o'zgaruvchan tahlillar jurnali. 135: 1–10. doi:10.1016 / j.jmva.2014.11.009.
^ Aliyari Gassabeh, Youness (2013-09-01). "Bir o'lchovli fazoda o'rtacha siljish algoritmining yaqinlashuvi to'g'risida". Pattern Recognition Letters. 34 (12): 1423–1427. arXiv:1407.2961. doi:10.1016 / j.patrec.2013.05.004. S2CID 10233475.
^ Li, Sianru; Xu, Zhanyi; Vu, Fuchao (2007-06-01). "O'rtacha siljishning yaqinlashuvi to'g'risida eslatma". Naqshni aniqlash. 40 (6): 1756–1762. doi:10.1016 / j.patcog.2006.10.016.
^ Karreyra-Perpinan, Migel A. (2007 yil may). "Gaussning o'rtacha siljishi bu EM algoritmi". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 29 (5): 767–776. doi:10.1109 / tpami.2007.1057. ISSN 0162-8828. PMID 17356198. S2CID 6694308.
^ Richard Szeliski, Computer Vision, Algoritmlar va ilovalar, Springer, 2011 y
^ Komaniciu, Dorin; Visvanatan Ramesh; Piter Meer (2003 yil may). "Kernel asosida ob'ektlarni kuzatish". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 25 (5): 564–575. CiteSeerX 10.1.1.8.7474. doi:10.1109 / tpami.2003.1195991.
^ Avidan, Shai (2005). Ansamblni kuzatib borish. 2005 yil IEEE Kompyuter Jamiyatining Kompyuterni ko'rish va naqshni tanib olish bo'yicha konferentsiyasi (CVPR'05). 2. San-Diego, Kaliforniya: IEEE. 494-501 betlar. doi:10.1109 / CVPR.2005.144. ISBN 978-0-7695-2372-9. PMID 17170479. S2CID 1638397.
^ Gari Bradski (1998) Hissiy foydalanuvchi interfeysida foydalanish uchun kompyuterni ko'rishni yuzini kuzatish Arxivlandi 2012-04-17 da Orqaga qaytish mashinasi, Intel Technology Journal, № 2-son.
^ Emami, Ibrohim (2013). "Onlayn xatolarni aniqlash va CAMShift kuzatuv algoritmi uchun tuzatish". 2013 yil Mashinani ko'rish va tasvirni qayta ishlash bo'yicha 8-Eron konferentsiyasi (MVIP). 2013 yil Eronda mashinalarni ko'rish va tasvirlarni qayta ishlash bo'yicha konferentsiya (MVIP). 2. IEEE. 180-183 betlar. doi:10.1109 / IranMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID 15864761.

[PAMI95-1] Cheng, Yizong (1995 yil avgust). "O'rtacha siljish, rejimni qidirish va klasterlash". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 17 (8): 790–799. CiteSeerX 10.1.1.510.1222. doi:10.1109/34.400568.

[PAMI02-2] Komaniciu, Dorin; Piter Meer (2002 yil may). "O'rtacha siljish: fazoviy tahlilga nisbatan qat'iy yondashuv". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 24 (5): 603–619. CiteSeerX 10.1.1.160.3832. doi:10.1109/34.1000236.

[Fukunaga-3] Fukunaga, Keinosuke; Larri D. Hostetler (1975 yil yanvar). "Naqshni tanib olishda qo'llaniladigan zichlik funktsiyasi gradiyentini baholash". Axborot nazariyasi bo'yicha IEEE operatsiyalari. 21 (1): 32–40. doi:10.1109 / TIT.1975.1055330.

[:0-4] Aliyari Gassabeh, Youness (2015-03-01). "O'rtacha siljish algoritmini Gauss yadrosi bilan yaqinlashtirish uchun etarli shart". Ko'p o'zgaruvchan tahlillar jurnali. 135: 1–10. doi:10.1016 / j.jmva.2014.11.009.

[5] Aliyari Gassabeh, Youness (2013-09-01). "Bir o'lchovli fazoda o'rtacha siljish algoritmining yaqinlashuvi to'g'risida". Pattern Recognition Letters. 34 (12): 1423–1427. arXiv:1407.2961. doi:10.1016 / j.patrec.2013.05.004. S2CID 10233475.

[6] Li, Sianru; Xu, Zhanyi; Vu, Fuchao (2007-06-01). "O'rtacha siljishning yaqinlashuvi to'g'risida eslatma". Naqshni aniqlash. 40 (6): 1756–1762. doi:10.1016 / j.patcog.2006.10.016.

[7] Karreyra-Perpinan, Migel A. (2007 yil may). "Gaussning o'rtacha siljishi bu EM algoritmi". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 29 (5): 767–776. doi:10.1109 / tpami.2007.1057. ISSN 0162-8828. PMID 17356198. S2CID 6694308.

[8] Richard Szeliski, Computer Vision, Algoritmlar va ilovalar, Springer, 2011 y

[PAMI03-9] Komaniciu, Dorin; Visvanatan Ramesh; Piter Meer (2003 yil may). "Kernel asosida ob'ektlarni kuzatish". Naqshli tahlil va mashina intellekti bo'yicha IEEE operatsiyalari. 25 (5): 564–575. CiteSeerX 10.1.1.8.7474. doi:10.1109 / tpami.2003.1195991.

[avidan2001-10] Avidan, Shai (2005). Ansamblni kuzatib borish. 2005 yil IEEE Kompyuter Jamiyatining Kompyuterni ko'rish va naqshni tanib olish bo'yicha konferentsiyasi (CVPR'05). 2. San-Diego, Kaliforniya: IEEE. 494-501 betlar. doi:10.1109 / CVPR.2005.144. ISBN 978-0-7695-2372-9. PMID 17170479. S2CID 1638397.

[11] Gari Bradski (1998) Hissiy foydalanuvchi interfeysida foydalanish uchun kompyuterni ko'rishni yuzini kuzatish Arxivlandi 2012-04-17 da Orqaga qaytish mashinasi, Intel Technology Journal, № 2-son.

[Emami2001-12] Emami, Ibrohim (2013). "Onlayn xatolarni aniqlash va CAMShift kuzatuv algoritmi uchun tuzatish". 2013 yil Mashinani ko'rish va tasvirni qayta ishlash bo'yicha 8-Eron konferentsiyasi (MVIP). 2013 yil Eronda mashinalarni ko'rish va tasvirlarni qayta ishlash bo'yicha konferentsiya (MVIP). 2. IEEE. 180-183 betlar. doi:10.1109 / IranMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID 15864761.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Navigation