- •Дослідження основних проблем предметної області
- •Роль інформаційних технологій у предметній області
- •Загальний опис проблем предметної області.
- •Актуальність даної теми.
- •Аналіз існуючих аналогів
- •Метод Віоли-Джонса
- •Метод surf
- •Метод sift
- •Метод orc
- •Порівняльна характеристика
- •Мета кваліфікаційної роботи
- •Постановка задачі
- •Об’єкт та методи дослідження
- •Програмна підтимка дослідження
- •Інформаційна модель системи
- •Детальний опис реалізації основних процедур та функцій додатку з прикладами.
- •Рекомендації по впровадженню та використанню
- •Порівняльний аналіз методів
- •Оцінка складності алгоритму контурного аналізу
- •Аналіз продуктивності методів
- •Рекомендаціі до використання методів
- •Охорона праці
- •Економічна частина диплому
- •Цивільний захист
- •Наукова новизна та практичне значення одержаних результатів
- •Перелік використаних джерел
- •Додаток a
- •Додаток b
Порівняльний аналіз методів
Оцінка складності алгоритму контурного аналізу
Нехай зображення вже бінарізоване і на ньому виділені контури. Оскільки надалі ми будемо працювати тільки з точками контурів, оцінимо загальну їх кількість на зображенні. Для цього, візьмемо зображення розміром n * n пікселів. Потім покриємо його рівномірної сіткою з кроком s. Сумарна довжина всіх ліній сітки складатиме:
(8.1)
Виходить, що перехід від плоского двовимірного зображення до контурів не зменшує розмірність задачі. Ми як і раніше працюємо в складності О(n2).
Однак тут можна зробити кілька зауважень:
Наведена оцінка є екстремальною. В реальному зображенні далеко не всі контури мають мінімальний розмір, і вони не покривають всю площу зображення. Отже, число контурів і їх сумарний периметр може бути значно менше . В ідеальному випадку – якщо зображення містить один об'єкт, без перешкод, то контурний аналіз буде працювати тільки з одним контуром, і число його пікселів складатиме вже не квадратичну, а лінійну залежність від n. У випадку роботи із зображенням, як з двовимірним масивом пікселів (наприклад, застосовуючи каскадні фільтри Хаара) – ми завжди працюємо з усіма пікселями зображення, незалежно від того, скільки об'єктів на ньому зображено.
Оскільки зображення у вигляді контурів вже має природну сегментацію - розбито на контури, то можна здійснювати фільтрацію частин зображення за простимими ознаками. Серед них – площа контуру, периметр, відношення квадрата периметра до площі (коефіцієнт форми). Таким чином, є досить простий і ефективний механізм попередньої фільтрації частин зображення.
Базові алгоритми двовимірних методів, як правило, не інваріантні до масштабу (SURF, SIFT) або обертанню (Хаар). Тому, фактично, вони працюють в тривимірному просторі, де ще один вимір з'являється через необхідність перебирати масштаби або кути повороту. Оскільки методи контурного аналізу інваріантні до масштабу і обертанню, то тут такої проблеми не існує.
Контурний аналіз дозволяє обробляти зображення в прогресивному режимі. Це означає, що ми можемо відсортувати контури за якоюсь ознакою (наприклад, по площі або по градієнту кордонів, або по яскравості і т.п.). А потім обробити перший контур, і видати результат. Інші ж контури обробляти у фоновому режимі. Це означає що перший результат (а в багатьох прикладних задачах саме він і потрібний) може бути отриманий за O(n), що є відмінною оцінкою для алгоритмів розпізнавання зображень.
Оскільки контури незалежні один від одного, то алгоритми розпізнавання легко розпаралелюються. Крім того, алгоритми є дуже простими і можуть виконуватися на графічних процесорах.
Всі вищенаведені міркування стосуються тільки обробки контурів. Звісно, етап отримання самих контурів нікуди не зникає, і він потребує як мінімум O(n2). Однак, на практиці, цей етап займає не більше 10-20% від загального часу обробки.
Контурний аналіз має дві групи факторів що негативно впливають на результати розпізнавання:
Перша група факторів пов'язана з проблемою виділення контуру на зображеннях. Контур - це строго визначена дискретна структура. Однак велика кількість реальних зображень мають об'єкти, які слабо виражені на навколишньому фоні. Об'єкт може не мати чіткої межі, він може бути однаковий по яскравості і кольору з фоном, він може бути зашумлен перешкодами і так далі. Всі ці фактори призводять до того, що контур або неможливо виділити взагалі, або він виділяється неправильно, і не відповідає границі об'єкта. Такі випадки дуже важкі для контурного аналізу. Адже контурний аналіз має сенс, тільки в тому випадку, коли контур об'єкта визначений однозначно правильно в усіх своїх точках.
Друга група факторів, що ускладнюють контурний аналіз, пов'язана з принципами контурного аналізу. Методи контурного аналізу припускають, що контур описує весь об'єкт цілком, і не допускає ніяких перетинів з іншими об'єктами або неповної видимості об'єкта. Таким чином, контурний аналіз має слабку стійкість до перешкод, не допускає перетину або часткової видимості об'єкта.