|
|
|
КЛАСТЕРІЗАЦІЯ ЗОБРАЖЕНЬ АЛГОРИТМОМ РОЗБИТТЯ З УРАХУВАННЯМ ЩІЛЬНОСТІ РОЗПОДІЛЕННЯ
| |
| 24.09.2023 17:46 |
|
Автор: Богучарський Сергій Іванович, кандидат технічних наук, Харківський національний університет імені В. Н. Каразіна;
Хруслов Максим Михайлович, кандидат фізико-математичних наук, Харківський національний університет імені В. Н. Каразіна
|
|
[26. Технічні науки;] |
Обробка мультимедійної інформації один із напрямів досліджень штучного інтелекту. З удосконаленням засобів обробки та збільшенням обчислювальних потужностей за останнє десятиліття з’явилося багато нових методів, що дозволяють ефективно обробляти відео. Однак, як і раніше. кластеризація залишається одним із лідируючих підходів до аналізу багатовимірних даних, у тому числі відео. Незважаючи на значний прогрес у цій галузі, все ще існує ряд невирішених проблем, серед яких домінуючими є: швидкість обробки великих обсягів мультимедіа, зашумленість даних, неоднозначність при віднесенні окремих спостережень до того чи іншого кластера, необхідність наявності апріорної інформації про кластери або додаткове інтерактивне налаштування параметрів кластеризації [1–3]. У зв’язку з цим останнім часом спостерігаються тенденції модифікації раніше розроблених методів з орієнтацією на більш високий рівень інтелектуальної обробки за умови усунення зазначених вище проблем.
Серед відомих підходів до кластеризації прийнято виділяти насамперед алгоритми, засновані на розбиттях. Як спостереження тут виступають об’єкти відеокадрів (наприклад, окремі пікселі зі своїми характеристиками, параметрами, властивостями або ознаками) і розглядається відстань між ними. При цьому зазвичай враховується відстань у ознаковому просторі. Таким чином, всі об’єкти «розносяться» по кластерам, що не перетинаються, причому відстань між об’єктами одного кластера в ідеалі повинна прагнути до мінімуму, а відстань між об’єктами різних кластерів – до максимуму. Дуже часто кожен кластер характеризується та задається центроїдом. До недоліків даного підходу, крім необхідності завдання початкового числа кластерів, слід віднести формування кластерів строго опуклої форми, тоді як значні сегменти відеокадрів можуть характеризуватись і складнішими формами [4, 5].
У процесі так званого ієрархічного підходу до кластеризації формується дерево, яке, на відміну від попереднього підходу до кластеризації, є не єдиним набором кластерів, а скоріше багаторівневим набором можливих варіантів розбиття простору на кластери [6]. Тут кілька кластерів нижчого рівня об’єднані в один кластер на вищому рівні ієрархії, що дозволяє встановити, який рівень розбиття на кластери даного конкретного додатка.
Однак, звідси випливає інше питання: скільки кластерів вважати оптимальним для даного додатка і яким чином його визначати. Крім того, подібні алгоритми мало прийнятні для аналізу великих обсягів відеоданих через складні обчислювальні процедури.
Альтернативним підходом, що дозволяє отримати кластери різної форми, є методи щільності кластеризації [2]. З назви, дана група методів аналізує щільність розподілу даних, враховуючи можливі шуми. Як кластери відбираються області високої концентрації в певному ознаковому просторі, розділені областями нижчої щільності. Спостереження, не віднесені до жодного кластера, вважаються випадковими обуреннями. Одним з найбільш поширених алгоритмів даної категорії є густинний алгоритм кластеризації просторових даних з присутністю шуму DBSCAN (англ. Density-Based Spatial Clustering of Applications with Noise) [6]. В його основі лежать концепції досяжності (англ. reachability) та зв’язності (англ. connectivity), які виражаються через два параметри відповідно: радіусом аналізованої околиці точки (є) та мінімальним числом точок у цій околиці (MinPts).
Точка x(k) є досяжною за густиною з точки x(q), при виконанні наступних двох умов: відстань між точками менше або дорівнює є, і в околиці точки x(k) знаходиться не менше MinPts точок. Точка x(k) вважається пов’язаною за густиною з точкою x(q), якщо існує третя точка, така що обидві ці точки досяжні з неї за густиною. Кластер формується із набору пов’язаних за щільністю точок. Чим більший радіус околиці є, тим менше буде знайдено кластерів, аж до одного єдиного всеосяжного кластера. Інша справа з кількістю точок MinPts: чим вище буде це значення, тим менше кластерів буде знайдено, аж до повної їх відсутності. Експерименти показали, що алгоритм працює значно повільніше при кількості точок, що перевищує 1000. Тому має сенс зробити модифікацію алгоритму, до того ж у реальних завданнях обробки відео часто спостерігається перетин сегментів. Іншими словами, одне спостереження може належати одночасно кільком кластерам [7, 8].
В рамках запропонованого методу обробки відео на основі нечіткої щільності кластеризації розподіл об’єктів за кластерами виконується аналогічно звичайному алгоритму DBSCAN, але загальна кількість даних, що обробляються, сильно скорочується. Коли відстань між об’єктами сусідніх кластерів буде меншою за певне значення, виконується процедура об’єднання цих кластерів. На останньому етапі здійснюється розрахунок рівнів належності об’єктів кластерам. Приклад сегментації відеокадра за допомогою запропонованого методу щільності нечіткої кластеризації показаний на рис. 1. Якщо пікселі в правій нижній частині кадру виявилися більш чітко розмежованими за кластерами, то пікселі в області дерев, у лівій верхній частині відеокадра, мають рівні приналежності кільком кластерам, ця область вийшла менш чіткою.
Рисунок 1 – Сегментація відеокадра
за допомогою щільної нечіткої кластеризації
Як переваги запропонованого методу слід виділити стійкість до шуму, можливість обробки кластерів різної форми і розміру, високу швидкість обробки багатовимірних даних. До недоліків можна віднести чутливість результатів кластеризації до обраних і підлягають аналізу параметрів, а також відсутність механізму регулювання щільності розподілу і зв’язності, що змінюється в окремих областях, що є предметом майбутніх досліджень. Експерименти, проведені на штучно згенерованих та реальних відеоколекціях відкритого доступу, показали, що запропонований метод перевершує за ефективністю традиційні DBSCAN та CLARANS, які зазвичай використовуються для кластеризації великих обсягів даних.
Джерела інформації
1. Chu, S.-C. Improved clustering and soft computing algorithms : Doctoral Thesis ... Doctor of Philosophy / S.-C. Chu. - Adelaide, 2004. - 238 p.
2. Gan, Y. Data Clustering: Theory, Algorithms and Applications / Y. Gan, Ch. Ma, J. Wu. - Philadelphia: SIAM, 2007. - 455 p.
3. Szeliski, R. Computer Vision. Algorithms and Applications / R. Szeliski. - London: Springer, 2011. - 813 p.
4. Xu, R. Clustering / R. Xu, D.C. Wunsch. - Hoboken: Wiley, 2009. - 341 p.
5. Feature extraction and clustering for dynamic video summarization / H. Zhou, A.H. Sadka, M.R. Swash et al. // Neurocomputing. - 2010. - Vol. 73, No. 10-12. - P. 1718-1729.
6. Kaufman, L. Finding Groups in Data: An Introduction to Cluster Analysis / L. Kaufman, P.J. Rousseeuw. - Hoboken: Wiley, 2005. - 368 p.
7. Ali, M.A. Review on fuzzy clustering algorithms / M.A. Ali, G.C. Karmakar, L.S. Dooley // IETECH Journal of Advanced Computations. - 2008. - Vol. 2, No. 3. - P. 169-181.
8. Bezdek, J.C. Fuzzy Models and Algorithms for Pattern Recognition and Image Processing / J.C. Bezdek, J. Keller, R. Krisnapuram, N.R. Pal. - N.Y.: Springer, 2005. - 776 p.
|
|
 Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
|
|
|
Голосування 
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter