Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Оцінка складності алгоритму контурного аналізу
Нехай зображення вже бінарізоване і на ньому виділені контури. Оскільки надалі ми будемо працювати тільки з точками контурів, оцінимо загальну їх кількість на зображенні. Для цього, візьмемо зображення розміром n * n пікселів. Потім покриємо його рівномірної сіткою з кроком s. Сумарна довжина всіх ліній сітки складатиме: (8.1) Виходить, що перехід від плоского двовимірного зображення до контурів не зменшує розмірність задачі. Ми як і раніше працюємо в складності О(n2). Однак тут можна зробити кілька зауважень: - Наведена оцінка є екстремальною. В реальному зображенні далеко не всі контури мають мінімальний розмір, і вони не покривають всю площу зображення. Отже, число контурів і їх сумарний периметр може бути значно менше . В ідеальному випадку – якщо зображення містить один об'єкт, без перешкод, то контурний аналіз буде працювати тільки з одним контуром, і число його пікселів складатиме вже не квадратичну, а лінійну залежність від n. У випадку роботи із зображенням, як з двовимірним масивом пікселів (наприклад, застосовуючи каскадні фільтри Хаара) – ми завжди працюємо з усіма пікселями зображення, незалежно від того, скільки об'єктів на ньому зображено. - Оскільки зображення у вигляді контурів вже має природну сегментацію - розбито на контури, то можна здійснювати фільтрацію частин зображення за простимими ознаками. Серед них – площа контуру, периметр, відношення квадрата периметра до площі (коефіцієнт форми). Таким чином, є досить простий і ефективний механізм попередньої фільтрації частин зображення. - Базові алгоритми двовимірних методів, як правило, не інваріантні до масштабу (SURF, SIFT) або обертанню (Хаар). Тому, фактично, вони працюють в тривимірному просторі, де ще один вимір з'являється через необхідність перебирати масштаби або кути повороту. Оскільки методи контурного аналізу інваріантні до масштабу і обертанню, то тут такої проблеми не існує. - Контурний аналіз дозволяє обробляти зображення в прогресивному режимі. Це означає, що ми можемо відсортувати контури за якоюсь ознакою (наприклад, по площі або по градієнту кордонів, або по яскравості і т.п.). А потім обробити перший контур, і видати результат. Інші ж контури обробляти у фоновому режимі. Це означає що перший результат (а в багатьох прикладних задачах саме він і потрібний) може бути отриманий за O(n), що є відмінною оцінкою для алгоритмів розпізнавання зображень.
- Оскільки контури незалежні один від одного, то алгоритми розпізнавання легко розпаралелюються. Крім того, алгоритми є дуже простими і можуть виконуватися на графічних процесорах. - Всі вищенаведені міркування стосуються тільки обробки контурів. Звісно, етап отримання самих контурів нікуди не зникає, і він потребує як мінімум O(n2). Однак, на практиці, цей етап займає не більше 10-20% від загального часу обробки.
Контурний аналіз має дві групи факторів що негативно впливають на результати розпізнавання: - Перша група факторів пов'язана з проблемою виділення контуру на зображеннях. Контур - це строго визначена дискретна структура. Однак велика кількість реальних зображень мають об'єкти, які слабо виражені на навколишньому фоні. Об'єкт може не мати чіткої межі, він може бути однаковий по яскравості і кольору з фоном, він може бути зашумлен перешкодами і так далі. Всі ці фактори призводять до того, що контур або неможливо виділити взагалі, або він виділяється неправильно, і не відповідає границі об'єкта. Такі випадки дуже важкі для контурного аналізу. Адже контурний аналіз має сенс, тільки в тому випадку, коли контур об'єкта визначений однозначно правильно в усіх своїх точках. - Друга група факторів, що ускладнюють контурний аналіз, пов'язана з принципами контурного аналізу. Методи контурного аналізу припускають, що контур описує весь об'єкт цілком, і не допускає ніяких перетинів з іншими об'єктами або неповної видимості об'єкта. Таким чином, контурний аналіз має слабку стійкість до перешкод, не допускає перетину або часткової видимості об'єкта.
|
|||||
Последнее изменение этой страницы: 2017-02-05; просмотров: 131; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.219.7 (0.007 с.) |