Оцінка складності алгоритму контурного аналізу

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 10Следующая ⇒

Нехай зображення вже бінарізоване і на ньому виділені контури. Оскільки надалі ми будемо працювати тільки з точками контурів, оцінимо загальну їх кількість на зображенні. Для цього, візьмемо зображення розміром n * n пікселів. Потім покриємо його рівномірної сіткою з кроком s. Сумарна довжина всіх ліній сітки складатиме:

(8.1)

Виходить, що перехід від плоского двовимірного зображення до контурів не зменшує розмірність задачі. Ми як і раніше працюємо в складності О(n²).

Однак тут можна зробити кілька зауважень:

- Наведена оцінка є екстремальною. В реальному зображенні далеко не всі контури мають мінімальний розмір, і вони не покривають всю площу зображення. Отже, число контурів і їх сумарний периметр може бути значно менше . В ідеальному випадку – якщо зображення містить один об'єкт, без перешкод, то контурний аналіз буде працювати тільки з одним контуром, і число його пікселів складатиме вже не квадратичну, а лінійну залежність від n. У випадку роботи із зображенням, як з двовимірним масивом пікселів (наприклад, застосовуючи каскадні фільтри Хаара) – ми завжди працюємо з усіма пікселями зображення, незалежно від того, скільки об'єктів на ньому зображено.

- Оскільки зображення у вигляді контурів вже має природну сегментацію - розбито на контури, то можна здійснювати фільтрацію частин зображення за простимими ознаками. Серед них – площа контуру, периметр, відношення квадрата периметра до площі (коефіцієнт форми). Таким чином, є досить простий і ефективний механізм попередньої фільтрації частин зображення.

- Базові алгоритми двовимірних методів, як правило, не інваріантні до масштабу (SURF, SIFT) або обертанню (Хаар). Тому, фактично, вони працюють в тривимірному просторі, де ще один вимір з'являється через необхідність перебирати масштаби або кути повороту. Оскільки методи контурного аналізу інваріантні до масштабу і обертанню, то тут такої проблеми не існує.

- Контурний аналіз дозволяє обробляти зображення в прогресивному режимі. Це означає, що ми можемо відсортувати контури за якоюсь ознакою (наприклад, по площі або по градієнту кордонів, або по яскравості і т.п.). А потім обробити перший контур, і видати результат. Інші ж контури обробляти у фоновому режимі. Це означає що перший результат (а в багатьох прикладних задачах саме він і потрібний) може бути отриманий за O(n), що є відмінною оцінкою для алгоритмів розпізнавання зображень.

- Оскільки контури незалежні один від одного, то алгоритми розпізнавання легко розпаралелюються. Крім того, алгоритми є дуже простими і можуть виконуватися на графічних процесорах.

- Всі вищенаведені міркування стосуються тільки обробки контурів. Звісно, етап отримання самих контурів нікуди не зникає, і він потребує як мінімум O(n2). Однак, на практиці, цей етап займає не більше 10-20% від загального часу обробки.

Контурний аналіз має дві групи факторів що негативно впливають на результати розпізнавання:

- Перша група факторів пов'язана з проблемою виділення контуру на зображеннях. Контур - це строго визначена дискретна структура. Однак велика кількість реальних зображень мають об'єкти, які слабо виражені на навколишньому фоні. Об'єкт може не мати чіткої межі, він може бути однаковий по яскравості і кольору з фоном, він може бути зашумлен перешкодами і так далі. Всі ці фактори призводять до того, що контур або неможливо виділити взагалі, або він виділяється неправильно, і не відповідає границі об'єкта. Такі випадки дуже важкі для контурного аналізу. Адже контурний аналіз має сенс, тільки в тому випадку, коли контур об'єкта визначений однозначно правильно в усіх своїх точках.

- Друга група факторів, що ускладнюють контурний аналіз, пов'язана з принципами контурного аналізу. Методи контурного аналізу припускають, що контур описує весь об'єкт цілком, і не допускає ніяких перетинів з іншими об'єктами або неповної видимості об'єкта. Таким чином, контурний аналіз має слабку стійкість до перешкод, не допускає перетину або часткової видимості об'єкта.

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности