'1+004. 021 Математичне та програмне забезпечення комп’ютерної системи ідентифікації елементів української жестової мови

Національний університет «Львівська політехніка»

Давидов Максим Володимирович

УДК 004.93'1+004.021

Математичне та програмне забезпечення комп’ютерної системи ідентифікації елементів української жестової мови

01.05.03 - Математичне та програмне забезпечення обчислювальних машин і систем

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Львів - 2009

Дисертацією є рукопис
Робота виконана в Національному університеті “Львівська політехніка”, кафедра “Інформаційні системи та мережі”
Науковий керівник:

доктор технічних наук, професор

Пасічник Володимир Володимирович

Національний університет “Львівська політехніка”,

завідувач кафедри “Інформаційні системи та мережі”
Офіційні опоненти:

доктор технічних наук, професор

Воробель Роман Антонович

Фізико-механічний інститут ім. Г.В.Карпенка НАН України (м. Львів),

завідувач відділу обчислювальних методів і систем перетворення інформації
доктор технічних наук, доцент

Камінський Роман Миколайович

Буковинський університет (м. Чернівці),

професор кафедри комп’ютерних систем і технологій

Захист відбудеться 29 жовтня 2009 р. о 14⁰⁰ годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С. Бандери, 12)
З дисертацією можна ознайомитись у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1).

Автореферат розісланий 28 вересня 2009 р.

Вчений секретар спеціалізованої вченої ради

доктор технічних наук, професор Р.А. Бунь

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Згідно з резолюцією ООН 48/96 від 20 грудня 1993 року кожна держава повинна забезпечити використання жестової мови для навчання нечуючих дітей та забезпечити послуги сурдоперекладу для сприяння спілкуванню нечуючих з людьми, які не володіють мовою жестів. Згідно наказу Міністерства освіти і науки України навчальний предмет «Українська жестова мова» введено з 2009/2010 навчального року у спеціальних загальноосвітніх навчальних закладах для дітей глухих та зі зниженим слухом. Актуальною задачею є розроблення програмних засобів, які допомагають у вивченні та перекладі української жестової мови.

В Інституті кібернетики ім. В. М. Глушкова НАН України та Київському національному університеті ім. Т. Г. Шевченка під керівництвом професора Ю.В. Крака ведуться дослідження з метою створення системи спілкування людей з вадами слуху. Розроблена технологія передбачає створення віртуальної тривимірної моделі, яка розмовляє жестовою мовою, та розроблення технології читання з губ.

У світі ведуться наукові дослідження з метою створення комп’ютеризованих систем розпізнавання жестової мови. Значний внесок у розроблення математичних моделей таких систем зробили Т. Старнер, Г. Ней, Дж. Цірен, А. Фітцгіббон, Г. Стерн, Т. Куган, Ц. Воглер, Р. Боуден, А. Фархаді, Р.-Х. Ліанг. Перші роботи, які розпочалися в 80-х роках ХХ століття, стосувалися розпізнавання пальцевої абетки – дактилю. Із пришвидшенням процесорної техніки, розпочалися роботи із розпізнавання жестів повної жестової мови. За опублікованими даними, в університеті м. Аахен (Німеччина) на базі обсягом 152 жести досягнуто якість розпізнавання 97,6% для одного користувача та 78% для двох користувачів при розпізнаванні з відеокамери. В університеті м. Даліан (Китай) на базі з 5113 жестів досягнуто якість розпізнавання 92% для одного користувача та 84% для шести користувачів із використанням рукавиць для введення даних.

Жестові мови різних країн розвивалися незалежно, а тому значно відрізняються одна від одної. Для розпізнавання жестів української жестової мови важливо якісно ідентифікувати форму долоні людини, яка жестикулює. Актуальною науковою задачею є задача покращення якості ідентифікації форми долоні у русі для розпізнавання жестів української жестової мови.

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

Результати дослідження мають важливе значення для вирішення проблеми інтеграції нечуючих у суспільство. Розроблені у процесі дослідження методи та програмні засоби опрацювання відео реального часу можна використати для розв’язування широкого кола задач комп’ютерного зору.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась відповідно до напрямків наукової діяльності кафедри інформаційних систем та мереж Національного університету «Львівська політехніка» за темою Міністерства освіти і науки України «Дактиль», 2006–2009 рр. (номер державної реєстрації 0107U001116) – автором розроблені алгоритми ідентифікації форми долоні та алгоритми знаходження кінців пальців долоні.

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

Для досягнення цієї мети необхідно вирішити такі завдання:

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

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

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

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

Наукова новизна одержаних результатів. У дисертаційній роботі вирішено актуальну наукову задачу ідентифікації елементів української жестової мови з відео реального часу. При цьому:

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

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

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

Розроблена комп’ютеризована система ідентифікації жестів складається з камери, дисплею або плазмової панелі та системного блоку з одноядерним процесором Celeron 2 ГГц. Програмне забезпечення системи складається з програми опрацювання відео реального часу «IMPROC», програми ідентифікації жестів «Жест», комп’ютеризованого тренажера жестової мови «Тренажер української жестової мови». Програмне забезпечення ідентифікації жестів та опрацювання відео реального часу розроблене автором самостійно у середовищі Microsoft Visual C++ 6.0 із використанням об’єктно-орієнтованого та шаблонного програмування.

Здійснено впровадження результатів дисертаційної роботи при розробленні комп’ютеризованого тренажера жестової мови для Львівського дитячого дистанційного навчально-консультаційного центру дітей з особливими потребами на базі НВК "Школа-гімназія "Сихівська" та Львівської спеціальної загальноосвітньої школи-інтернату Марії Покрови для глухих дітей, при виконанні робіт за бюджетною науково-дослідною темою Міністерства освіти і науки України ДБ/Дактиль “Математичне моделювання та програмна реалізація системи перекладу з жестової мови” (номер державного реєстру 0107U001116).

Особистий внесок здобувача. Всі положення й результати дисертаційної роботи отримані автором самостійно. У роботах, опублікованих у співавторстві, здобувачеві належать: розроблення методу створення навчальних прикладів, методу виділення характеристик зображення, модифікованого методу градієнтного навчання нейронної мережі [1], розроблення методу розбиття даних на групи для підвищення якості навчання нейронної мережі [2], теоретичне обґрунтування та розроблення алгоритму псевдодвовимірної деформації зображення для порівняння зображення з еталоном та розроблення функції порівняння пікселів для покращення ідентифікації зображення за еталоном [3], розроблення методики тестування та порівняння методів ідентифікації форми долоні за еталоном [4], розроблення алгоритмів порівняння з еталоном для тренажеру жестової мови [5], розроблення методики тестування та проведення порівняння методів ідентифікації кінців пальців долоні [6], розроблення алгоритмів порівняння з еталоном для тренажеру жестової мови [7], розроблення методів пошуку кінців пальців [8], програмна реалізація елементів тренажеру жестової мови [9], розроблення методу пошуку долоней та обличчя на зображенні [10].

Апробація результатів дисертації. Наукові й практичні результати роботи доповідалися та обговорювалися на: Першій центральноєвропейській студентській конференції з лінгвістики (м. Будапешт, Угорщина, 2006), Міжнародних виставках інформаційних технологій та телекомунікацій ЦеБІТ-2006, ЦеБІТ-2007, ЦеБІТ-2008 (м. Ганновер, Німеччина, 2006, 2007, 2008), сьомій міжнародній конференції «Інтелектуальний аналіз інформації ІАІ-2007» (м. Київ, 2007), міжнародній науковій конференції «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту (ISDMCI’2009)» (м. Євпаторія, 2009).

Публікації. Результати дисертації опубліковано у 10 наукових працях, у тому числі в 6 статтях у фахових наукових виданнях, 4 статтях у матеріалах і тезах конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, 4 розділів, двох додатків та списку використаних джерел. Загальний обсяг дисертації 134 сторінки, з яких основний зміст викладено на 117 сторінках друкованого тексту, містить 36 рисунків, 23 таблиці. Список використаних джерел складається з 114 найменувань. Додатки містять опис наборів тестових даних, акти впровадження.
ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі до дисертації обґрунтовано актуальність проблеми досліджень, сформульовано мету роботи та задачі досліджень. Наведено характеристику наукової новизни та практичної цінності отриманих результатів. Показано зв'язок роботи з науковими програмами, планами, темами.

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

Проведено огляд сучасних досліджень, які виконують з метою розпізнавання елементів іноземних жестових мов. Керівниками досліджень є проф. Л. Акарун (університет Богазічі, Туреччина), проф. Г. Ней, проф. Дж. Цірен (університет м. Аахен, Німеччина), проф. А. Фітцгіббон (університет м. Оксфорд, Великобританія), проф. Ц. Омлін (університет Вестерн Кейп), проф. Дж. Лоу (університет PETRONAS, Малазія), Дж. Уоч (університет Бен Гуріон, Ізраїль), Г. Стерн (Каліфорнійський університет, США), Л. Гуі (політехнічний університет м. Лозан, Швейцарія), проф. Т. Куган (університет м. Дублін, Ірландія), Г. Бірк (університет м. Аальборг), проф. Ф. Ле-Жен (лабораторія комп’ютерного зору CvLav, Швейцарія), проф. Н. Ліу (університет Квінсланд, Австралія) та інші.

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

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

У другому розділі проведено декомпозицію задачі розпізнавання та перекладу жестової мови, як задачі комп’ютерного зору. На основі результатів аналізу існуючих систем ідентифікації елементів жестових мов, розроблено структуру системи перекладу жестової мови у текст та визначено місце вирішених у роботі задач у загальній системі. У розробленій структурі введено зворотні зв’язки для автоматизованого налаштування до умов зйомки та особливостей доповідача. Розроблена структура розбита на модулі, зв’язок між якими зображено структурною схемою (Рис. ).

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

Рис. . Структурна схема системи перекладу жестової мови у текст

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

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

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

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

Досліджено функції, які обирають характеристики зображення з хрестоподібного (рис. 2а) та квадратного (рис. 2б) околу. Для визначення характеристик окремого піксела зображення використовуються функції виділення яскравості, функції виділення компонент кольору Y, Cb, Cr у представленні YCbCr, компонент H, S, V у представлені HSV, компонент R,G, B у представленні RGB, функція виділення країв.
Рис. . Хрестоподібний (а) та квадратний (б) окіл для вибору характеристик зображення для r=2. Чорним кольором позначено піксел зображення, окіл якого розглядається.

Для формування множини навчальних прикладів , де – навчальне значення входу, а – еталонне значення виходу, розроблено метод інтерактивного вибору навчальних прикладів з відеозображення. Оператор вказує на зображенні точку , яка відповідає об’єкту, та задає радіус області зображення, яку він займає. До множини позитивних навчальних прикладів додаються навчальні приклади за наступним правилом: для всіх цілих таких, що додати до множини навчальних прикладів новий навчальний приклад за формулою

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

Повторне виконання вищенаведених дій для розширення навчаючої вибірки дозволяє покращити якість навчання класифікатора.

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

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

Дістав подальший розвиток метод відбору навчальних прикладів для навчання нейромережевого класифікатора у якому:

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

Для навчання нейромережевого класифікатора удосконалено метод зворотного поширення похибки, у якому, порівняно з класичним методом, внесено такі зміни:

при перерахунку ваг нейромережевих зв’язків, додається додаткове випадкове значення з діапазону , параметр зменшується під час навчання від початкового значення до нуля;
при погіршенні результату на протязі трьох циклів алгоритму, алгоритм повертається до попередніх значень нейромережевих зв’язків;
введений додатковий параметр, який пришвидшує зміну ваг нейромережевих зв’язків початкових шарів мережі.

Розроблену модифікацію методу порівняно із класичною реалізацією на прикладі розв’язання задачі ідентифікації кінців пальців на відео. На тестовій задачі прийнятний результат розпізнавання отримано за 50 циклів навчання нейромережі (час виконання 0,5 с на процесорі із частотою 2GHz). Для досягнення такого самого результату із застосуванням класичного алгоритму необхідно 500 циклів навчання (час виконання 5 с). Таким чином, застосування розробленого методу дозволило скоротити час навчання у 10 разів порівняно із класичним алгоритмом, що є суттєвим для розроблення інтерактивних програм та програм, які навчаються в процесі використання. Розроблений метод покладений в основу технології «покажи, що потрібно розпізнати». Ця технологія дає можливість користувачеві показати, які об’єкти на відео його цікавлять, а програма навчається їх розпізнавати.

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

Для розв’язання задачі виділення ділянок зображення із кольором шкіри використано два методи: метод моделі освітлення та метод нейронних мереж.

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

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

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

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

Задача пошуку оптимальної монотонної деформації одного зображення в інше є NP-повною. Під оптимальністю розуміємо мінімізацію величини деформації та мінімізацію відмінності елементів зображень. Відомий алгоритм розв’язання цієї задачі, який розроблено Сеічі Учіда (Seiichi Uchida) та Хіроакі Сакое (Hiroaki Sakoe), має обчислювальну складність для зображень розміру NxN. Також існує модифікація алгоритму, яка розглядає обмежені деформації зображень, а алгоритм її вирішення має обчислювальну складність .

Розроблений у дисертаційній роботі алгоритм порівняння зображення з еталоном із врахуванням псевдодвовимірної моделі деформації зображення має обчислювальну складність , де N та M – ширина та висота зображень, вимірювана в елементах зображень, які порівнюють, – параметр алгоритму. Підвищення швидкодії досягнуто за рахунок обмеження максимального зсуву та за рахунок використання псевдодвовимірних алгоритмів. Розроблений алгоритм має меншу обчислювальну складність ніж методи порівняння зображень на основі псевдодвовимірних прихованих марковських моделей (P2DHMM) та псевдодвовимірних прихованих марковських моделей з моделлю деформації (P2HMMDM) та може бути застосований коли доступний лише один навчальний приклад.

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

Для порівняння пікселів зображення з еталоном введена штрафна функція . Ця функція побудована таким чином, щоб елементи зображення, близькі за кольором до межі об’єкта, не були віднесені до тла, а елементи зображення, значно відмінні від об’єкта не були віднесені до об’єкта. Розглянуто два випадки: перший – порівняння елемента зображення з прозорим пікселем еталона із віднесенням елемента зображення до тла, та другий – порівняння елемента зображення з непрозорим пікселем еталона із віднесенням елемента зображення до об’єкта.

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

Із використанням методу еталону розроблено програмно-алгоритмічні засоби ідентифікації форми долоні. Задачу визначення конфігурації долоні вирішено як задачу знаходження відомої конфігурації долоні найбільш схожої до зображеної на кадрі, та обчислення числової оцінки схожості. Розроблені алгоритми увійшли в систему опрацювання відео «IMPROC» у вигляді методів Etalon Image Match, Masked Etalon Image Match, Masked Etalon Image Select. Ці методи реалізовано на мові програмування С++ у вигляді класів.

При використанні 100 еталонів розміру 24х26 час опрацювання на комп’ютері з процесором Celeron 1,2 GHz складає 70 мс, що є достатнім для виконання обчислень у реальному часі.

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

Робота алгоритму розпізнавання розпочинається, коли одна або дві долоні переміщуються у зону розпізнавання, яка задається при налаштуванні системи. Система формує послідовність SL та SR форми та напрямку руху лівої та правої долоні, відповідно. Коли отримані послідовності повністю відповідають прихованій марковській моделі жесту, вважається, що жест розпізнано та виводиться опис жесту на екран (рис. 3).

Рис. . Блок-схема алгоритму ідентифікації жестів
Розроблені алгоритми покладені в основу програми ідентифікації жестів «Жест». За результатами тестування на наборі з 85 жестів правильно ідентифіковано 78 (91,7%). Отриманий результат близький за порядком до результатів, які отримані іноземними вченими. Для точного порівняння розробленого методу з іноземними необхідно провести тестування на одних і тих самих тестових наборах. Це виявилося неможливим, через те, що відкриті для вільного використання відомі іноземні тестові набори створені у градації сірого, що не дозволяє використати алгоритми опрацювання, розроблені у цій роботі.

У четвертому розділі наведено структуру та результати тестування комп’ютеризованої системи ідентифікації жестів української жестової мови. Система складається з камери, дисплею та системного блоку. На сьогодні для керування системою використовуються стандартні засоби (миша та клавіатура). У подальшому планується керування системою здійснювати жестами. Експерименти проведено із використанням системного блоку з одноядерним процесором Celeron 2 ГГц та оперативною пам’яттю об’ємом 1 Гб.

Програмне забезпечення системи складається з програми опрацювання відео реального часу «IMPROC», програми ідентифікації жестів «Жест», комп’ютеризованого тренажера жестової мови «Тренажер української жестової мови». Програмне забезпечення ідентифікації жестів та опрацювання відео реального часу розроблене автором самостійно у середовищі Microsoft Visual C++ 6.0. із використанням об’єктно-орієнтованого та шаблонного програмування.

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

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

Розв’язання задачі визначення положення обличчя та долоней користувача складається з двох етапів: визначення зон зображення із кольором шкіри та сегментація отриманих зон для виділення обличчя та долоней. Більша область вважається обличчям, дві менші — долонями. Найкращі результати отримані при застосуванні нейромережевого підходу для визначення ділянок із кольором шкіри та кластеризації за зв’язністю. На трьох тестових наборах правильно розпізнано положення обличчя та долоней на 96%, 98,9% та 96,8% кадрах, відповідно.

Задачу розпізнавання кінців пальців руки розв’язано як задачу класифікації елементів зображення на такі, що вважають кінцями пальців, та на такі, що відмінні від них. Для класифікації елементів зображення використано нейромережевий класифікатор. Результати опрацювання зображень нейромережами, які навчені за допомогою модифікованого методу зворотного поширення похибки та методу спряжених градієнтів, порівняно на чотирьох групах тестових зображень. Модифікований метод дозволив у середньому на 27% зменшити кількість помилок розпізнавання та на 44% зменшити час навчання, порівняно з методом спряжених градієнтів. При використанні класичного методу зворотного поширення похибки для вирішення поставленої задачі розпізнавання, задовільного результату не отримано.

Для порівняння якості роботи різних методів ідентифікації форми долоні за еталоном створено тестовий набір, який складається з 240 зображень доповідача української жестової мови, відзнятих в однакових умовах. На кожному із зображень доповідач показує один з 12 жестів. Приклади еталонів долоні наведено на рис. 4.

1 2 3 4 5 6

Рис. . Приклади еталонів долоні: 1 – „чому?, 2 – „нагорода”, 3 – „навіщо?”

(фігура 1), 4 – „навіщо?” (фігура 2), 5 – „скільки?”, 6 – „юрист”

Завдяки застосуванню розробленого алгоритму порівняння зображень та функції штрафного множника (ФШМ) підвищено відсоток правильно класифікованих основних конфігурацій долоні з 87% до 94% (табл. 1).
Таблиця 1

Відсоток правильно ідентифікації форм долоні різними методами (%)

Метод порівняння зображень	Функція порівняння пікселів	Відсоток правильно класифікованих прикладів, %
Із врахуванням псевдодвовимірної моделі деформації зображення	ФШМ	94
	Евклідова віддаль	92
Із спотворенням зображення, хрестоподібний окіл	ФШМ	84
Із спотворенням зображення, хрестоподібний окіл	Евклідова віддаль	84
Із спотворенням зображення, квадратний окіл	ФШМ	65
Із спотворенням зображення, квадратний окіл	Евклідова віддаль	74
Попіксельний	ФШМ	88
Попіксельний	Евклідова віддаль	87

Програмний модуль ідентифікації жестів увійшов до інтерактивного «Тренажера української жестової мови». Інтерактивна частина тренажера призначена для контролю за навчанням мові жестів. Алгоритми розпізнавання жесту дозволяють встановлювати правильність виконання жесту та сигналізувати про це учневі.

Тренажер жестової мови впроваджено у Львівському дитячому дистанційному навчально-консультаційному центрі дітей з особливими потребами на базі НВК "Школа-гімназія "Сихівська" та Львівській спеціальній загальноосвітній школі-інтернаті Марії Покрови для глухих дітей. Для системи використано комп’ютери із процесорами Celeron 1,7 ГГц та Celeron 2 ГГц, відповідно. Для отримання відеоданих використано веб-камери Labtec Webcam 5500 та Creative Live! Cam Optia AF, відповідно.

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

Розроблено структуру програмного комплексу розпізнавання жестів, який містить додатковий модуль визначення положення кінців пальців долоні та модуль розпізнавання форми долоні. Це дало можливість врахувати специфіку української жестової мови у системі ідентифікації жестів.
Розроблено метод створення навчальних прикладів з відео, який використовує поняття нечіткого околу точки зображення. Завдяки цьому розроблено концепцію інтерактивного навчання класифікатора «покажи, що потрібно розпізнати».
Дістав подальший розвиток метод відбору навчальних прикладів для навчання нейромережевого класифікатора за рахунок розбиття навчальних прикладів на групи, що дало можливість зменшити кількість помилок розпізнавання для різних умов освітлення та неоднорідного тла.
Удосконалено метод навчання нейромережевого класифікатора зворотним поширенням похибки за рахунок введення додаткової випадкової величини зміни ваг нейромережі та коефіцієнта зворотного поширення похибки. Кількість помилок розпізнавання кінців пальців зменшено в середньому на 27%, а час навчання на 44% порівняно з нейромережевим класифікатором з бібліотеки LTI-lib.
Розроблено новий метод порівняння зображення з еталоном із використанням псевдодвовимірної моделі монотонної деформації зображення та нової штрафної функції встановлення міри подібності пікселів зображення та еталону. На тестовій базі з 240 зображень підвищено відсоток правильної класифікованих конфігурацій долоні з 87% до 94%, порівняно з відомими методами порівняння зображень у реальному часі.
Із застосуванням розроблених методів реалізовано комп’ютеризовану систему ідентифікації жестів, за допомогою якої правильно розпізнано 78 з 85 жестів (91,7%) української жестової мови.
Розроблений програмний модуль ідентифікації жестів для інтерактивного «Тренажера української жестової мови» впроваджено у Львівському дитячому дистанційному навчально-консультаційному центрі для дітей з особливими потребами на базі НВК "Школа-гімназія "Сихівська" та Львівській спеціальній загальноосвітній школі-інтернаті Марії Покрови для глухих дітей.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Давидов М. В. Класифікація елементів відеозображень реального часу з допомогою нейромережі / М. В. Давидов, Ю. В. Нікольський // Вісник Національного університету “Львівська політехніка”, Інформаційні системи та мережі. — Львів, 2005. — №549. — С. 82—92.
Давидов М. В. Нейромережний класифікатор елементів відеозображень реального часу / М. В. Давидов, Ю. В. Нікольський // Вісник Національного університету “Львівська політехніка”, Комп’ютерні системи проектування. Теорія і практика. — Львів, 2006. — №564. — С. 18—25.
Давидов М. В. Автоматична ідентифікація елементів жестової мови за методом еталону / М. В. Давидов, Ю. В. Нікольський // Вісник Національного університету “Львівська політехніка”, Інформаційні системи та мережі. — Львів, 2007. — №589. — С. 174—198.
Давидов М. В. Вибір ефективного методу опрацювання зображень на основі еталону для ідентифікації елементів жестової мови / М. В. Давидов, В. В. Пасічник, Ю. В. Нікольський // Автоматизированные системы управления и приборы автоматики, Всеукраинский межведомственный научно-технический сборник. —2008. — №139. — С. 59—68.
Давидов М. В. Методи та засоби опрацювання зображень реального часу для ідентифікації елементів жестової мови / М. В. Давидов, Ю. В. Нікольський // Штучний інтелект, науково-технічний журнал, Державний університет інформатики і штучного інтелекту. — Донецьк, 2008. — №1. — С. 131—138.
Давидов М. В. Аналіз методів розпізнавання у моделях жестової мови / М. В. Давидов, О. В. Пасічник, Ю. В. Нікольський // Східно-Європейський журнал передових технологій. — Харків, 2008. — №4/2 (34). — С. 57—61.
Пасічник В. В. Програмний тренажер для навчання мові жестів / В. В. Пасічник, Ю. В. Нікольський, М. В. Давидов // Спеціалізований тематичний додаток до загальногалузевого науково-виробничого журналу „Зв’язок”. Праці міжнародної наукової конференції „Розвиток інформаційно-комунікаційних технологій та розбудова інформаційного суспільства в Україні”: м.Ганновер, Німеччина, СеВІТ-2007, 15-21 бер. 2007 р. – К., 2007. – С. 98—106.
Pasichnyk O. System of finger movement identification for sign language recognition / Oksana Pasichnyk, Iouriy Nikolskiy, Maksym Davydov // Abstracts of First Central European Student Conference in Linguistics: 29-31 May 2006. — Budapest, 2006. — Р. 23—25.
Пасічник В. В. Математичне моделювання та програмна реалізація елементів тренажеру для навчання жестовій мові людей, що втратили слух / В. В. Пасічник, Ю. В. Нікольський, М. В. Давидов // Сборник трудов седьмой международной конференции «Интеллектуальный анализ информации ИАИ-2007»: 15-18 мая 2007 г. — К., 2007. — С. 56—66.
Давидов М. В. Дослідження методів розпізнавання елементів жестової мови на основі пошуку та опрацювання зображення руки / М. В. Давидов, Ю.В.Нікольський, О.В.Пасічник // Матеріали конференції «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту (ISDMCI’2009)», 18-22 травня 2009. — Євпаторія, 2009. — Т. 2. — С. 298—300.

АНОТАЦІЇ

Давидов М.В. Математичне та програмне забезпечення комп’ютерної системи ідентифікації елементів української жестової мови. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – Математичне та програмне забезпечення обчислювальних машин і систем. – Національний університет «Львівська політехніка», Львів, 2009.

Дисертація присвячена розробленню математичного та програмного забезпечення комп’ютеризованої системи ідентифікації жестів української жестової мови у реальному часі.

Розроблено нову модифікацію методу навчання нейронних мереж зворотним поширенням похибки, яка дозволила на 27% зменшити кількість помилок розпізнавання кінців пальців долоні та на 44% зменшити час навчання, порівняно з методом спряжених градієнтів. Розроблено новий метод вибору навчальних прикладів для навчання нейромережевого класифікатора, який дозволив застосувати технологію інтерактивного навчання з відео. Розроблену модель псевдодвовимірної неперервної деформації зображення використано для порівняння форми долоні з еталоном, що дало змогу підвищити відсоток правильного розпізнавання форми долоні з 87% до 94%. Розроблена комп’ютеризована система ідентифікації жестів української жестової мови на тестовому наборі з 85 жестів правильно розпізнає 92% жестів.

Ключові слова: жестова мова, нейронні мережі, псевдодвовимірна неперервна деформація зображення, ідентифікація форми долоні, розпізнавання жестів.
Давыдов М.В. Математическое и программное обеспечение компьютерной системы идентификации элементов украинского жестового языка. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 – Математическое и программное обеспечение вычислительных машин и систем. – Национальный университет «Львовская политехника», Львов, 2009.

Диссертация посвящена разработке математического и программного обеспечения компьютеризированной системы идентификации жестов украинского жестового языка в реальном времени.

Разработана новая модификация метода обучения нейронных сетей обратным распространением ошибки, которая позволила на 27% уменьшить количество ошибок распознавания концов пальцев ладони и на 44% уменьшить время обучения, по сравнению с методом сопряженных градиентов. Разработан новый метод выбора обучающих примеров для обучения нейронных сетей, который позволил использовать технологию интерактивного обучения нейронных сетей с видео. Разработанная модель псевдодвумерной непрерывной деформации изображения использована для сравнения формы ладони с эталоном, что позволило увеличить процент правильно распознанных форм ладони с 87% до 94%. Разработанная компьютеризированная система идентификации жестов украинского жестового языка на тестовом наборе их 85 жестов правильно распознает 92% жестов.

Ключевые слова: жестовый язык, нейронные сети, псевдодвумерная непрерывная деформация изображений, идентификация формы ладони, распознавание жестов.
Davydov M.V. Mathematical support and software of the computerized Ukrainian sign language identification system. – Manuscript.

Thesis for a candidate’s degree in technical sciences by speciality 01.05.03 –

Mathematical support and software of computational machines and systems. – Lviv Polytechnic National University, Lviv, 2009.

The thesis is dedicated to development of computational methods and software of the computerized real-time Ukrainian sign language identification system. The problem of sign language to text translation is not solved not only in Ukraine but all over the world. A valuable contribution to development of foreign languages sign recognition models was made by T. Starner, H. Ney, J. Zieren, A. Fitzgibbon, H. Stern, T. Coogan, C. Vogler, R. Bowden, A. Farhadi, R.-H. Liang. The proposed recognition model differs from existing foreign language recognition models by hand shape recognition in motion.

The system utilizes one video camera as a sensor. The software of the system consists of real-time video processing application “IMPROC”, gesture identification application “Sign”, computerized “Ukrainian sign language trainer”.

New algorithms and methods are proposed for the purpose of the system development. The task of Ukrainian gesture language recognition and translation to written language was analyzed. The advantages and disadvantages of known foreign sign language recognition systems were studied. The most difficult task in real-time sign language recognition is hand shape identification. Most of the systems do not consider signs that differ by hand shape only. The structure of software solution for this task was proposed. The proposed system structure utilizes fingertip position information and pseudo 2-dimentional continuous image deformation model for hand shape recognition.

Two skin segmentation methods for hands tracking were developed. The first method is based on neural network classifier. The second is based on diffusion light equation.

Fingertip recognition is done by means of the neural network classifier. New modification of back propagation neural network training algorithm was developed. Via the modification the fingertip recognition error rate was reduced by 27% and the teaching time was reduced by 44% comparing with conjugate gradient method. New method for sample selection for neural networks teaching was developed. The method allows use of new technology for interactive neural networks teaching from video.

The fast pseudo 2-dimensional continuous image deformation model was developed for hand shape recognition. The proposed model is faster than pseudo 2-dimentional hidden Markov models (P2HMM) and pseudo 2-dimentional hidden Markov models with deformation model (P2HMMDM) and could be used even if one sample for every hand shape is available. For better hand shape extraction the new penalty function is proposed to compare image pixels and hand shape sample pixels. The proposed function utilizes two penalty functions – function of fuzzy penalty for pixel difference between image pixel and opaque sample pixel and function of fuzzy penalty for resemblance of image pixel and the nearest opaque sample pixel in case of pixel comparison to transparent sample pixel. By the means of proposed methods the percent of properly recognized hand shapes increased from 87% up to 94%.

The sign identification method is based on hidden Markov models. The one-dimensional hidden Markov model with 8 states is used. Such number of states is enough to describe complex gestures with several hand shapes. For every sign a model for left and right hand is created. The Baum-Welch algorithm is used for HMM training and forward algorithm is used for gesture verification for model fitness. The developed sign identification software utilizes proposed algorithms. The best achieved result of separate signs recognition is 92% of test set that contains 85 signs.

The result achieved is close to sign language recognition results achieved by foreign scientists. For the precise comparison of results testing on common test set is required, but it is impossible because open foreign sign language test sets are captured by monochrome camera and are unsuitable for processing by methods proposed in this thesis.

The sign identification module is implemented in interactive “Ukrainian sign language trainer”. The proposed trainer version consists of sign language dictionary with gesture video records. The trainer has means for video rendering with different speed and frame-by-frame review. The interactive part of the trainer is developed for sign language gesture verification. Special functions allows student to see his own image from camera. Is helps to synchronize student signs and signs form vocabulary. The gesture recognition algorithm identifies proper and improper gesture execution and signalizes about it to user.

The interactive “Ukrainian sign language trainer” is inculcated in Lviv consulting center for special need children based on “School-gymnasium “Syhivska” and Lviv specialized secondary boarding school for hearing impaired children.

Key words: sign language, neural networks, two-dimensional image deform model, hand shape recognition, gesture identification.