Аналіз алгоритмів розпізнавання образів для оптимізації рішення задачі пошуку об’єкта у відеоряді

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аналіз алгоритмів розпізнавання образів для оптимізації рішення задачі пошуку об'єкта у відеоряді

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

В останні роки розпізнавання образів знаходить все більше застосування. Розпізнавання мови, друкарського і рукописного тексту, різних зображень значно спрощує взаємодію людини з комп'ютером, створює передумови для застосування різних систем штучного інтелекту.

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

На сьогодні розроблено досить багато різноманітних алгоритмів розпізнавання образів. Кожен з них створювався для роботи з певним типом зображень, а для подальшого застосування у прикладному програмуванні необхідно обирати найбільш оптимальний з точки зору конкретного завдання та удосконалювати його у конкретних реаліях.

Аналіз останніх досліджень і публікацій. Перші дослідження зі застосуванням обчислювальної техніки переважно йшли класичною схемою математичного моделювання - математична модель, алгоритм і розрахунок. Такими були завдання моделювання процесів що відбуваються під час вибухів атомних бомб, розрахунку балістичних траєкторій, економічних пріоритетів і інших застосувань. Заснована Норбертом Ві - нером на початку XX століття нова наука, що отримала назву кібернетика (наука про загальні закономірності процесів управління і передачі інформації в машинах, живих організмах і суспільстві), дозволила в дослідження питання розпізнавання образів ввести кількісні методи [1; 2]. Іншими словами, представити процес розпізнавання образів (по суті - природне явище) математичними методами. Однак окрім класичних ідей побудови математичних моделей виникали і методи засновані на зовсім інший природі - дослідження та навчання групи відомих об'єктів. Як показала практика розв'язання окремих виділених завдань, вони часто давали кращий результат ніж рішення, засновані на переускладнених математичних моделях. Їх ідея полягала у відмові від прагнення створити вичерпну математичну модель досліджуваного об'єкта (а досить часто адекватні моделі неможливо побудувати), а натомість задовольнятись відповіддю тільки на конкретні питання, що досліджуються на даний час, причому ці відповіді переносити на широкий клас досліджуваних питань подібного характеру. До досліджень, що ставилися таким чином для розпізнавання зорових образів: прогнозування врожайності, рівня річок, завдання розрізнення нафтоносних і водоносних пластів по непрямим геофізичним даним тощо, конкретна відповідь потрібна у досить простій формі, як, наприклад, належність об'єкта одному зі заздалегідь фіксованих класів. Натомість же вихідні дані з завдань, зазвичай, задавалися як уривкові відомості про досліджувані об'єкти, наприклад, у вигляді набору заздалегідь розкласифікованих об'єктів. З математичного погляду таке розпізнавання образів є далеким від узагальнення ідеї екстраполяції функції [3; 4; 5].

В Україні зазначену проблему почали досліджувати з середини 60-х років ХХ століття. Тоді ж було створено перші програми та пристрої, що розпізнавали кілька десятків окремо вимовлених слів. Згодом сформувались окремі школи, що займались теоретичним вивченням та впровадженням розробок у дію: Інститут кібернетики (під керівництвом Т.К. Вінцюка), Львівський університет (М.П. Деркач), Харківський національний інститут радіоелектроніки (М.Ф. Бондаренко), Дніпропетровський університет (О.М. Карпов), Одеський університет (Т.О. Бровченко та Е.О. Нушікян).

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

Для досягнення поставленої мети, були виділені такі завдання:

• проаналізувати існуючі методи розпізнавання образів;

• виділити переваги та недоліки цих методів;

• розробити алгоритм співставлення об'єктів на відеоряді.

Виклад основного матеріалу. Розпізнавання образів - завдання ідентифікації об'єкта або визначення будь-яких його властивостей за його зображенням (оптичне розпізнавання) або аудіо - записом (акустичне розпізнавання) та іншим характеристикам.

Образом є угрупування в системі класифікації, що об'єднує (виділяє) певну групу об'єктів за деякою ознакою.

Методи розпізнавання образів можна умовно поділити на дві групи інтенціальні та екстенціальні. Відмінною особливістю інтенціальних методів є те, що в якості елементів операцій при побудові та застосуванні алгоритмів розпізнавання образів вони використовують різні характеристики ознак та їх зв'язків. Такими елементами можуть бути окремі значення або інтервали значень ознак, середні величини і дисперсії, матриці зв'язків ознак і т. п., над якими здійснюються дії, що виражаються в аналітичній або конструктивній формі. При цьому об'єкти в даних методах не розглядаються як цілісні інформаційні одиниці, а виступають у ролі індикаторів для оцінки взаємодії і поведінки своїх атрибутів. До таких методів відносяться [2; 5]:

• Методи, засновані на оцінках густин розподілу значень ознак (або подібності та відмінності об'єктів). За їх допомогою вирішуються завдання з відомим розподілом, як правило, нормальним, але виникає необхідність набору та перебору великої статистики. Відповідно перебір всієї навчальної вибірки при розпізнаванні може бути досить великим, а тому ростиме експоненціально швидко. Недоліком є висока чутливість до непредставницької навчальної вибірки і артефактів.

• Логічні методи можуть застосовуватися лише для завдань невеликої розмірності простору ознак, що продиктовано високою евристичністю таких методів. При відборі логічних вирішальних правил (кон'юнкція) необхідний повний перебір, що веде за собою високу обчислювальна трудомісткість.

• Лінгвістичні (структурні) методи. Вирішуються завдання відновлення (визначення) граматики за деякою множиною висловлювань (описів об'єктів). Такі завдання важко формалізувати, тому вони важко піддаються математичному представленню.

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

Основними операціями в розпізнаванні образів за допомогою обговорюваних методів є операції визначення подібності та відмінності об'єктів. Об'єкти у зазначеній групі методів відіграють роль діагностичних прецедентів. При цьому залежно від умов конкретного завдання роль окремого прецеденту може змінюватися в най - ширших межах: від головної і визначальної до вельми непрямої участі в процесі розпізнавання. У свою чергу умови задачі можуть вимагати для успішного вирішення участі різної кількості діагностичних прецедентів: від одного об'єкту в кожному класі, що розпізнається, до повного об'єму вибірки, а також різних способів обчислення властивостей подібності та відмінності об'єктів [5]. Цими вимогами пояснюється подальший поділ екстенціональних методів на підкласи.

• Метод порівняння з прототипом. Його недоліком є висока залежність результатів класифікації від міри відстані (метрики) та неможливість створення заздалегідь визначеної оптимальної метрики.

• Метод к найближчих сусідів. Застосовується на завданнях невеликої розмірності за кількістю класів і ознак. Має високу залежність результатів класифікації від міри відстані (метрики). В завданнях такого типу виникає необхідність повного перебору навчальної вибірки при розпізнаванні, що веде до значної обчислювальної трудомісткості.

• Колективи вирішальних правил (КВП). Відзначається дуже висока технічна складність методу, невирішеність низки теоретичних проблем, як при визначенні областей компетенції приватних методів, так і в самих приватних методах.

В нашій роботі увага приділяється задачам та відповідним алгоритмам розпізнавання відео - потоків. Розпізнавання відеопотоку має ряд особливостей, тому у впроваджені даних методів є ряд проблем:

• швидкість розпізнавання образу на зображенні є недостатньою для розпізнання 25 кадрів за секунду;

• процес розпізнавання потребує значних затрат ресурсів оперативної пам'яті;

• більшість алгоритмів потребує великої навчальної вибірки позитивних і/або негативних зображень.

Таким чином, розглянемо існуючі методи виявлення об'єкта на цифровому відеоряді.

Методи розпізнавання об'єкта на цифровому зображенні, за способом віднесення ділянки зображення до області інтересів, можна розділити на дві великі групи: узагальнюючі і розрізняючі.

Узагальнюючі методи складають абстрактне, ідеалізоване уявлення про структуру об'єкта на основі позитивних навчальних зображень.

Підхід цього методу полягає у використанні умовної моделі, яка здатна вчитися розрізняти частини об'єкта. Зображення розбивається на невеликі ділянки, кожній з яких надається мітка, що представляє собою смислове значення цієї ділянки.

Метод Карпура-Вінна. Наприклад, маємо мітки: «Ліс», «Небо», «Трава», «Ціль». Знаючи розташування і класифікацію однієї частини, пошук місця розташування інших частин обмежується. Наприклад, якщо знати розташування дерева, то інші дерева можуть бути легко виявлені. У методі для виявлення об'єкта використовується дальній радіус просторових обмежень на ділянках [5].

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

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

Блок-схема роботи алгоритму пошуку співпадіння об'єкту-цілі з міткою-прицілом

Розрізняючі методи використовують спеціальну функцію-класифікатор для виявлення об'єкта на цифровому зображенні. У процесі навчання вони виділяють відмінності між позитивними і негативними навчальними зображеннями.

Метод Віоли-Джонса. Ґрунтується на інтегральному уявленні зображення за ознаками Ха - ара. На основі алгоритму адаптивного бустінгу відбувається побудова класифікатора, який видає логічні відповіді. Метод використовує каскад з декількох класифікаторів, послідовно застосовуваних до зображення. Кожен класифікатор включає набір характерних ознак Хаара, що мають фіксоване взаємне розташування.

В основі методу Папагеоргіу лежить використання вейвлет Хаара. Вейвлет - це математична функція, що дозволяє аналізувати різні частотні компоненти даних. У методі Папагеоргіу обчислюються проміжні представлення, які інкапсу - люють важливу інформацію в класі об'єкта, такі представлення обчислюється для всіх об'єктів, що надійшли в якості вхідних даних зображень, що в результаті дає набір позитивних і негативних векторних ознак. Ці векторні ознаки використовуються для навчання класифікаторів за шаблоном розрізняти об'єкти у своєму класі [4].

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

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

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

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

Наведена на рисунку 1 блок-схема демонструє принцип роботи описаного алгоритму пошуку співпадіння об'єкту-цілі з міткою-прицілом. Пошук об'єкту здійснюється на основі заданого масиву характеристик навчальної вибірки.

Висновки і пропозиції. Отже, були проаналізовані різні методи виявлення об'єктів у відеопотоці.

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

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

На основі представленого алгоритму було розроблено програму розпізнавання цілей та влучень на відеозображенні, яку експериментально перевірено шляхом впровадження її в центрі тактико-спеціальної підготовки «Булат».

Список літератури

образ зображення інформатика алгоритм

1. Авалиани Г.В. Эвристические методы в распознавании образов / Г.В. Авалиани. - Тбилиси: Мецниереба, 1988. - 78 с.

2. Горелик А.Л. Методы распознавания / А.Л. Горелик, В.А. Скрипкин. - М.: Высшая школа, 1984, 2004. - 262 с.

3. Стокман Дж. Компьютерное зрение = Computer Vision / Джордж Стокман, Линда Шапиро. - М.: Бином. Лаборатория знаний, 2006. - 752 с.

4. Фомин Я.А. Распознавание образов: теория и применения / Я.А. Фомин. - М.: ФАЗИС, 2012. - 429 с.

5. Szeliski R. Computer Vision: Algorithms and Applications [Електронний ресурс]. - Режим доступу: http://szeliski.org/Book/

Размещено на Allbest.ru