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

ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

УДК 004.932.4(043.3)

Автореферат

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

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

Спеціальність 05.13.06 - Інформаційні технології

МЕЛЬНИК ГАННА-ВАЛЕНТИНА ВАЛЕНТИНІВНА

Донецьк - 2009

Дисертацією є рукопис

Робота виконана в Донецькому національному університеті Міністерства освіти й науки України на кафедрі прикладної математики й теорії систем управління.

Науковий керівник:доктор технічних наук, професор Мишко Сергій Васильович Донецький національний університет Міністерства освіти і науки України завідувач кафедри прикладної математики і теорії систем управління (м. Донецьк).

Офіційні опоненти:доктор технічних наук, професор Скобцов Юрій Олександрович Донецький національний технічний університет Міністерства освіти й науки України завідувач кафедри автоматизованих систем управління (м. Донецьк);

доктор технічних наук, професор Антощук Світлана Григорівна Одеський національний політехнічний університет Міністерства освіти й науки України завідувач кафедри інформаційних систем (м. Одеса).

Захист відбудеться «13» листопада 2009 р. о 13:00 на засіданні спеціалізованої вченої ради К 11.051.08 у Донецькому національному університеті Міністерства освіти й науки України за адресою: 83000, м. Донецьк, пр. Театральний, 13, корп. 4, ауд. 416.

З дисертацією можна ознайомитися в бібліотеці Донецького національного університету за адресою: 83000, м. Донецьк, вул. Університетська, 24, головний корпус.

Автореферат розісланий «_____» жовтня 2009 р.

Вчений секретар спеціалізованої вченої ради К 11.051.08______________Д. В. Шевцов

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

скелетизація дискретний математичний

Актуальність теми. На теперішній час автоматизація документообігу визначила перелік актуальних завдань, для рішення яких створено безліч програмних продуктів. Одна із проблем, обумовлена інтенсифікацією інформаційних потоків у системах електронного документообігу (СЕД), припускає при автоматизованому введенні підвищення достовірності перетворення документів до формату, який дозволяє редагування. Це обумовлено тим, що специфіка функціонування підсистеми введення документів визначає спосіб зберігання й ефективність подальшого використання інформації при пошуку й обробці. Рішення завдання підвищення ефективності автоматизованого введення документів припускає розробку, зокрема, нових підходів, що дозволяють здійснювати розпізнавання рукописних текстів, верифікацію підписів, векторизацію креслень та інше.

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

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

Завданням скелетизації зображень різної природи займалися такі закордонні й вітчизняні вчені, як Гонсалес Р., Дуда Р., Лі К., Павлідіс Т., Претт У., Фу К., Хорн Б. К. П., Шлезінгер М. І., Местецький Л. М. та інші, у роботах яких пропонується застосування для генерації скелета, зокрема, морфологічних операцій, перетворень Фур'є, тріангуляції на основі діаграм Вороного. Використання на практиці зазначених підходів характеризує результат скелетизації як зображення, що містить множину артефактів і не відповідає початковому.

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

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

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

Досягнення даної мети обумовлює рішення наступних основних задач:

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

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

– розробити математичну модель утворюючої бінарних зображень на основі моделі об'єкта, що результує скелетизацію на множині атомарних елементів;

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

– провести апробацію та порівняльний аналіз застосування запропонованої інформаційної технології до обробки ЕКД у блоці розпізнавання СЕД з існуючими аналогами.

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

Предмет дослідження - методи й алгоритми скелетизації образів бінарних зображень.

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

Наукова новизна отриманих результатів.

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

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

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

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

Практичне значення роботи.

1. Розроблений спосіб скелетизації дозволив підвищити достовірність векторизації креслень у СЕД за рахунок моделювання початкових зображень GT-об'єктами.

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

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

4. Результати дисертаційної роботи впроваджені в СЕД ЗАТ «ДонецькСталь» - металургійний завод» і страховій компанії «СПІЧ і К», що надало можливості підвищити достовірність приведення електронних копій документів до формату, який дозволяє редагування, а також знизити витрати на зберігання відповідних образів зображень.

5. Результати дисертаційної роботи використані у навчальному процесі в курсах «Узнавання і розпізнавання при проектуванні інтелектуальних робототехнічних систем», «Моделювання знаків у дискретних множинах», а також при виконанні курсових, дипломних проектів і магістерських робіт студентами спеціальностей «Прикладна математика» й «Інформатика» Донецького національного університету.

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

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися на VIII, IX міжнародних науково-практичних конференціях «Сучасні інформаційні й електронні технології» (м. Одеса, 2007, 2008 р.); наукової конференції Донецького національного університету за підсумками науково-дослідної роботи за період 2007-2008 р. (Донецький національний університет, м. Донецьк, 2009); на розширеному науковому семінарі кафедри прикладної математики й теорії систем управління Донецького національного університету (м. Донецьк, 2009); на XI науково-практичній конференції «Інформаційні технології в освіті й управлінні» (м. Нова Каховка, 2009).

Публікації. По темі дисертації опубліковано 8 наукових праць, з них 5 - у провідних спеціальних виданнях, що входять у перелік ВАК України.

Структура й об'єм дисертації. Дисертація складається із вступу, 4 розділів, висновків, списку використаних джерел з 129 найменувань й 3-х додатків. Робота містить 55 ілюстрацій, 3 таблиці. Загальний об'єм дисертації 195 сторінок, у тому числі 159 сторінок основного тексту.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі «Сучасний стан проблеми скелетизації бінарних зображень у системах електронного документообігу. Постановка задачі дослідження» описані підсистеми, що складають систему електронного документообігу, проаналізовано вплив результатів функціонування підсистем введення й розпізнавання зображень на такі параметри СЕД, як ресурсомісткість зберігання документа; час пошуку необхідної інформації (визначається системою індексації документів); вартість передачі документа від одного робочого місця до іншого. З метою виявлення причин низької достовірності розпізнавання й векторізації розглянуті сучасні системи автоматичного розпізнавання, виявлені їх основні функціональні особливості. На основі аналізу узагальненої функціональної схеми системи автоматичного розпізнавання зображень показано, що результати функціонування блоку попередньої обробки, що містить, зокрема, процедуру скелетизації, значно впливають на якість розпізнавання, тому що класифікація здійснюється на основі обробленого зображення, а не початкового.

Проведено аналіз сучасних підходів до скелетизації; показано, що оцінювати ефективність застосування будь-якого із алгоритмів можливо тільки за результатами розпізнавання зображень. У зв'язку з цим для порівняння алгоритмів скелетизації проведені експерименти, що полягають у розпізнаванні з навчанням системою ABBYY FineReader Professional 8.0 скелетизованих різними алгоритмами зображень, а також векторизації програмою Easy Trace 8.6 Pro результатів різних алгоритмів скелетизації (проріджувальних з пост- і передобробкою; хвильового; заснованих на морфологічних операціях; скелетизації полігональної області). Отримані результати експериментів показали, що кількість вірно розпізнаних нестандартних символів не перевищує 58 % для образів 300 зображень (як початкових, так і результуючих обробку різними алгоритмами скелетизації), а кількість об'єктів, які виявлені при векторизації, значно відрізняється від передбачуваної. Приклад фрагмента тестового зображення наведено на рис. 1, а), а відповідні результати скелетизації - на рис.1, б)-з).

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

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

У другому розділі «Моделі GT-об'єкта й утворюючої знаків бінарних зображень, заданих на множині атомарних елементів» з метою конструктивного визначення результату скелетизації висунута гіпотеза про спосіб формування зображення. Припускається, що при генерації зображення деякого концепту, іменованого як О_i (i=1,2,…), суб'єкт діє відповідно до мотивації, що припускає впізнання результату іншими суб'єктами, які не приймають участі в процесі генерації, як образа однойменного концепту. Для формалізації гіпотетичних положень розроблена узагальнена функціональна схема генерації й реєстрації зображення (рис. 2).

Відповідно до наведеної функціональної схеми, зображення трактується як множина слідів, які візуалізовані на ПРЗ внаслідок реєстрації рухів ЧР ПФС, здійснених під впливом керуючих дій, що згенеровані відповідно до траєкторій, які задаються пристроєм управління за моделлю. Тоді результатом попередньої обробки є формування за початковим зображенням множини образів траєкторій, що допускають генерацію однойменного зображення. Оскільки за образом зображення може бути відновлена, в загальному випадку, множина траєкторій, сформульовано й обґрунтовано гіпотезу про спосіб формування зображення, відповідно до якої шукана множина траєкторій мінімальна за потужністю, причому реєстрація сліду по кожному з елементів множини здійснюється ЧР (рис.2) максимально можливого розміру для кожного з відповідних слідів. Таким чином, метою скелетизації є виявлення GT-об'єкта (від англ. «generative trajectory» - траєкторія, що породжує) - множини образів кривих, відновлених за образом зображення, кожний з яких відповідає єдиному елементу моделі концепту. Обґрунтовано, що GT-об'єкт відповідає «геометричному центру» зображення у випадку, якщо базовий елемент (частина зображення, що відповідає результату реєстрації ЧР ПФС однієї точки траєкторії) є планіметричною фігурою, для якої виконуються наступні вимоги:

- утворює опуклу множину;

- базові елементи, які відповідають різним по «товщині» ЧР ПФС, подібні;

- є симетричною щодо вертикальної й горизонтальної осей, а також повороту навколо центра.

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

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

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

(АЕ) A= ,

де б_h=б(i_h,j_h), i_h{1,…,I},j_h{1,…,J},Н=IJ. При цьому атомарні елементи множини А, які формують образ зображення, називаються активними (ААЕ). Отже, для побудови моделі GT-об'єкта, що використовується в системі автоматизованого введення й розпізнавання, необхідно обґрунтувати вибір елементу, який відповідає образу траєкторії, а також визначити образ базового елемента в термінах властивостей АЕ.

Відповідно до теоретичних положень, розроблених для моделювання образів зображень на множині АЕ, обґрунтовано, що образом траєкторії на множині А є шлях з _a в _b - L(_a,_b) - скінченна, цілком упорядкована множина зв'язних зв'язок L(_a,_b)={(_h,_h+1)_m } , m_h{1,2,3,4}, де ₁=_a, _n+1=_b; - зв'язка типу m_h{1,2,3,4}, ; r{2,3,…,n},_r має рівно два зв'язних АЕ із множини {_k} , а ₁ й _n+1 - не більше двох. Доведено, що відновлення GT-об'єкта можливо ізольовано для кожного D-знаку - максимальної по потужності зв'язної множини активних атомарних елементів. Тоді для формування GT-об'єкта на множині АЕ необхідно по образу зображення визначити множину шляхів, кожний з яких відповідає траєкторії руху пристрою фіксації сліду при генерації зображення.

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

Таким чином, для формування GT-об'єкта на множині АЕ необхідно за образом зображення визначити множину шляхів, які є образами траєкторій руху ПФС при генерації зображення, й мають максимально можливу довжину по кількості складових АЕ. Дане трактування GT-об'єкта конструктивно обґрунтовує мету попередньої обробки образів зображень, заданих на множині АЕ.

Для завдання шляхів, що складають GT-об'єкт, виявляються такі ААЕ, які відповідають «локальному геометричному центру» (ЛГЦ) D-знака Z (рис. 3), що припускає визначення необхідного числа «максимальних кіл», центри яких гіпотетично відповідають ЛГЦ образа зображення.

а)б)в)г)д)

Рис. 3. Образи зображень на множині АЕ

Оскільки «максимальні кола» відповідають образу базового елемента, що моделює ЧР ПФС, то для формування GT-об'єкта необхідно визначити зазначений об'єкт на множині АЕ, для чого сформульовані вимоги до образу базового елемента (опуклість, симетрія й подібність) у термінах властивостей множини АЕ, які для деякої множини SА мають такий вигляд:

1) множина АЕ SА називається опуклою, якщо _a,_bS виконується: Л(₂(_a,_b))S, де Л(₂(_a,_b)) - множина АЕ, що складають всілякі найкоротші шляхи (НШ) з АЕ _a в _b;

2) опукла множина АЕ SА називається ₀-центрованою, ₀S, якщо _a=(i_a,j_a)S існує АЕ _b=(i_b,j_b)S такий, що i_b=2i₀-i_a й j_b=2j₀-j_a.

3) послідовність ₀-центрованих множин S_iА, i{1,2,…,n_S},є послідовністю подібних множин, якщо i{1,2,…,n_S-1},виконано: ?S_i?S_i+1= і S_i=S_i+1\?S_i+1, де ?S - множина АЕ, зв'язних з АЕ «фона» вертикальною або горизонтальною зв'язкою, тобто:

?S={б_k=б(i_k,j_k)S|б_p=б(i_p,j_p)A\ : (i_p-i_k) (j_p-j_k)=0, max{|i_p-i_k|, |j_p-j_k|}=1}.

Обґрунтовано, що кола, приклади границь яких наведені на рис. 4, а), б), згенеровані різними засобами комп'ютерної графіки, не задовільняють властивостям ₀-центрованості й подібності.

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

а)б)в)

Рис.4. Приклади образів базових елементів - окружностей на множині АЕ, згенерованих стандартними алгоритмами (а, б); множина (в)

У відповідності із властивостями кола, заданого в усюди щільній множині, визначений елемент представлення (ЕП) розміру r c центром в АЕ - (образ базового елемента на множині АЕ) як множина АЕ, відстань від кожного з яких до центра не перевищує r, тобто множина = ={б_kА|(,_k)?r}, rN, де ( ,_k)=|-i_k|+|-j_k|. Приклад множини, що обмежує ЕП розміром r=5, наведений на рис. 4, в).

Доведено, що введений елемент представлення задовольняє всім вимогам, висунутим до образа базового елемента:

– елемент представлення , для будь-якого rN, такого, що А є опуклою множиною АЕ;

– множина АЕ , для будь-якого rN такого, що А, є ₀-центрованою множиною;

– послідовність ЕП , r=1,2,…, таких, що А, є послідовністю подібних множин.

Визначення ЕП на множині АЕ допускає розробку способу генерації GT-об'єкта для заданого D-знака Z= шляхом формування повного покриття з метою визначення ААЕ, що моделюють його ЛГЦ.

Очевидно, що в загальному випадку будь-який ААЕ є центром кількох ЕП, всі АЕ яких належать образу зображення, але тільки ЕП найбільшого розміру, що повністю складається з ААЕ, може відповідати образу базового елемента. Для виявлення таких АЕ на множині активних атомарних елементів введена функція, яка кожному АЕ D-знаку Z ставить у відповідність величину, що характеризує розмір максимального ЕП, який повністю складається з ААЕ: . Областю визначення функції F(_h) є множина ААЕ D-знака Z, причому F(_h)=0 тільки тоді, коли ААЕ утворює горизонтальну або вертикальну зв'язку з АЕ множини А\Z. Приклади образа зображення та значень функції F(_h) наведені на рис. 5.

а)б)

Рис. 5. Образ зображення (а) і множина значень функції F(_h) (б)

Тоді ЛГЦ моделюють АЕ, що складають, зокрема, локальні максимуми функції F(_h), розрахованої для досліджуваного D-знака. Аналіз образів зображень і відповідних таблиць значень функцій дозволив виявити наступні множини ААЕ, що формують ЛГЦ знака:

М - множина локальних максимумів, яка складається з АЕ б_hZ, що доставляють найбільше в околі U(б_h)={б_pZ|max{|i_h-i_p|,|j_h-j_p|}=1} значення функції

F(_h): M=

де M_k={ й , Z й F(_k) }, k{1,…,Q_M};

P - множина АЕ, що зберігають локальну товщину, тобто тих АЕ, які не містять в околі АЕ з більшим значенням функції

F(_h): P= ,

де P_k={ , , Z};

S - множина зв'язних підмножин S_k, k{1,…,Q_S}, максимальних по потужності, які утворені АЕ, що зберігають значення функції F(б), і зв'язують в сукупності незв'язні підмножини M й P з мінімально можливою зміною значення функції F(_h).

Приклади множин M, P, S наведені на рис. 6.

а)б)

Рис. 6. Образ початкового зображення (а) і відповідні значення функції F(_h), на яких виділені множини M, P, S (б)

Відповідно до викладеного, для формування GT-об'єкта єдиного сліду без самоперетинань необхідно на кожній зі зв'язних підмножин множин М, P, S виявити найкоротші шляхи, які є образами траєкторій, що в загальному випадку не завжди можливо зробити однозначно. Тоді генерація GT-об'єкта здійснюється відповідно до гіпотези про спосіб формування зображення, тобто на основі атомарних елементів множин M, P, S виявляються множини шляхів з мінімально можливим значенням міри, що породять повне покриття знака множиною елементів представлення, центри яких установлені в АЕ виявлених шляхів.

У випадку, якщо образ зображення було отримано в результаті здійснення руху ПФС по декількох траєкторіях, які мають загальні точки, ЧР, яка використовувалася при фіксуванні кожного зі слідів, не характеризує фрагмент образу зображення відповідного перетинання (рис. 7). Тоді для виявлення GT-об'єкта необхідно виділити фрагменти образу зображення, що є образами перетинань слідів, і виключити їх із множини АЕ, які однозначно формують шукані шляхи. Для множин АЕ, які залишилися і є фрагментами слідів без перетинань, аналіз проводиться аналогічно випадку реєстрації сліду без самоперетинань і розглянутий раніше. Множина АЕ, що характеризує фрагменти, утворені перетинанням двох і більше слідів, образи яких на множині А мають загальні АЕ, визначена як d-множина - підмножина MP загальних АЕ образів різних слідів. Обґрунтовано, що АЕ є елементом d- множини тоді й тільки тоді, коли встановлений у нього ЕП має непусте перетинання із двома й більше ЕП із центрами в АЕ з незв'язних підмножин множини MPS.

Рис. 7. Множина значень функції F(): d-множини виділені темно-сірим, границі ЕП із центрами в АЕ d-множин - світло-сірим

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

Формування GT-об'єкта припускає можливість відновлення образу зображення з метою прийняття рішення про адекватність проведеної попередньої обробки. При цьому для відновлення необхідно задати тільки АЕ, що складають шляхи GT-об'єкта, а також розмір ЕП, що моделює ЧР ПФС при реєстрації кожного фрагмента траєкторії. Таким чином, якщо GT-об'єкт заданий як множина шляхів , кожний з яких може бути представлений у вигляді об'єднання НШ, і для кожного АЕ _h обчислене значення функції F(_h), тоді утворюючою GT-об'єкта називається множина АЕ, отримана в результаті об'єднання множин ЕП, установлених у кожний АЕ множини (GT)= , тобто множина . Отримана множина АЕ (утворююча) підлягає порівнянню з початковим зображенням. Приклад двох GT-об'єктів, а також відновлені утворюючі представлені на рис. 8.

а)б)

Рис. 8. GT-об'єкти (позначені темно-сірим кольором) і відповідні утворюючі (позначені світло-сірим), накладені на образ початкового зображення (позначено чорним)

Сформульовані в розділі 2 результати складають основу для розробки інформаційної технології формування GT-об'єкта.

У третьому розділі «Інформаційна технологія генерації GT-об'єктів й утворюючих знаків бінарних зображень на множині атомарних елементів» описані розроблена архітектура й алгоритми автоматизованої системи скелетизації знаків бінарних зображень. Функціональна схема вказаної інформаційної технології представлена на рис. 9.

Блок обчислення значень функції F() (рис. 9, блок 1) здійснює обробку образа зображення, що моделюється в підсистемі введення й розпізнавання у вигляді підмножини АЕ, причому образ зображення може складатися як з одного, так і з декількох D-знаків, кожен з яких обробляється окремо. Після побудови таблиці значень F() у блоці 2 (рис. 9) формуються множини M, P, S, причому передбачається, що значення функції в АЕ, які не складають D-знак, менше, ніж в ААЕ.

Виявлені множини M, P, S аналізуються в блоці 3 (рис. 9) з метою формування d-множин оцінкою відстані від АЕ, можливо формуючих d-множини, до відповідних центрів ЕП.

Після побудови d-множин здійснюється формування шляхів, що відповідають фрагментам слідів без перетинань, тобто на множинах M, P, S за винятком тих АЕ, які є центрами ЕП, що мають загальні АЕ з елементами представлення, установленими в АЕ d-множин, генеруються шляхи, котрі складають фрагменти GT-об'єктів. Очевидно, що таких шляхів у загальному випадку багато, єдиним критерієм переваги може служити однотипність побудови шляхів на кожному із фрагментів образу сліду, для того, щоб при сполученні шляхів у блоці 5 (рис. 9) їх можна було віднести до одного типу.

Відповідно до виділених шляхів і НШ у блоці 5 (рис. 9) проводиться аналіз НШ із метою виявлення таких пар, які при сполученні за допомогою АЕ d-множин забезпечують виконання гіпотези про спосіб формування зображення. Якщо можливих сполучень декілька, то в якості шуканих виступають множини, що моделюють всі можливі сполучення для кожної d-множини. При цьому всі з'єднання проводяться як можна «ближче» до відрізка прямої, який генерується засобами комп'ютерної графіки, та з'єднує відповідні АЕ НШ, тому що показано, що для АЕ кожної d-множини можна в загальному випадку сформувати множину сполучень, які складаються з фіксованої кількості АЕ.

Отримані в блоці 5 (рис. 9) множини множин НШ є GT-об'єктами, якщо адекватно відображають властивості початкового зображення, і при цьому дозволяють однозначно робити класифікацію. Те, що отриманий GT-об'єкт допускає однозначне виявлення, наприклад, непохідних елементів, забезпечується способом побудови. Перевірка відповідності побудованих моделей деякому класу зображень здійснюється на етапі розпізнавання, але при відновленні утворюючої оцінку адекватності моделі (блок 6, рис. 9) можна провести за допомогою порівняння таблиць значень функції F() початкового й відновленого зображень, які, як обґрунтовано в дисертаційній роботі, чисельно повинні відрізнятися не більше ніж на два для АЕ із множин M, P, S, виділених на початковому зображенні.

Запропонований спосіб формування GT-об'єкта дозволяє якісно підвищити ефективність роботи блоку введення й розпізнавання документів СЕД, тому що із множини отриманих моделей можна вибрати ту, котра найбільше достовірно відповідає класу об'єкта, який розпізнається.

У четвертому розділі «Розробка програмного забезпечення й експериментальні дослідження системи генерації GT-об'єкта» описана програма, що реалізує генерацію й обробку бінарного зображення. У програмному забезпеченні, розробленому в дослідницьких цілях, реалізовані функції, які відображають всі проміжні етапи обробки, зокрема, формування dг-множини; множини АЕ, щодо яких можна розглядати локальну товщину; таблиці значень функції F(б) і відповідного графіку. Програмна реалізація дозволяє вибрати для кожної dг-множини найкраще сполучення, не розглядаючи всі можливі варіанти, і зберегти результати у вигляді зображення або множини шляхів. Здійснюється перевірка адекватності GT-об'єкта оцінкою зміни розміру ЕП для початкового й відновленого зображень, для чого генерується утворююча, котру також можна зберегти. Приклади GT-об'єктів й утворюючих для тестових образів зображень наведені на рис. 10.

а)б)в)

г)д)е)

Рис. 10. Приклади зображень (а-в), GT-об'єктів (г-е) і утворюючої (е)

Показано, що згенерована множина GT-об'єктів відповідає схематичному представленню, а повторна обробка утворюючої з метою виявлення GT-об'єкта приводить до генерації зображень, які збігаються з початковими. Експериментальні дослідження підтверджують висновок про те, що GT-об'єкт адекватно моделює зображення, оскільки результат скелетизації прогнозований, що не виконується для інших алгоритмів скелетизації. У ході експерименту встановлено, що вірно розпізнаних GT-об'єктів на 27% більше, ніж при розпізнаванні скелетів і початкових зображень, що свідчить про значне підвищення достовірності розпізнавання програмою ABBYY FineReader Professional 8.0 при використанні GT-об'єктів. Інший експеримент, який полягає у векторизації креслень, показав, що кількість об'єктів, виявлених стандартними засобами обробки растрових зображень (Easy Trace 8.6 Pro, Corel Trace 11.0), на 11,4% менше, ніж для початкових зображень і скелетів, отриманих за допомогою інших алгоритмів.

Для зберігання електронних копій документів, введених у СЕД без розпізнавання, на основі інформаційної технології формування GT-об'єкта розроблений спосіб зберігання зображень, який дозволяє зменшити розміри файлів з ЕКД на 8-25% (залежно від типу зображення) без втрати якості в порівнянні зі стандартними алгоритмами. Спосіб стиску зображення заснований на записі кожного зі шляхів, що складає GT-об'єкт, у структурі: розмір елемента представлення; кількість АЕ, що складають шлях; початковий АЕ шляху; послідовність типів зв'язок, що формують шлях.

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

ВИСНОВКИ

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

При виконанні роботи отримані наступні основні результати.

1. Виявлено недоліки підходів до скелетизації, основні з яких - відсутність визначення терміна «скелет», а також застосування понять, однозначно визначених в усюди щільних множинах, до зображень, заданих у дискретних представленнях, що дозволило обґрунтувати актуальність моделювання зображень, які результують скелетизацію, на множині атомарних елементів.

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

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

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

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

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

7. Розроблено програмне забезпечення, що реалізує автоматизовану генерацію множини GT-об'єктів по заданому на множині атомарних елементів образу зображення. Перевірка адекватності згенерованого GT-об'єкта здійснювалася відновленням утворюючої по виявленій множині образів траєкторій й аналізом однойменності отриманого й початкового зображень. Використання даного програмного забезпечення на стадії попередньої обробки дозволило зменшити кількість виявлених об'єктів для образів креслень при автоматичній векторизації на 11,4 %.

8. Розроблено інформаційну технологію стиску образів бінарних зображень ЕКД, яка дозволяє зменшити розмір відповідних файлів до 25% шляхом зберігання GT-об'єктів, що згенеровані на стадії попередньої обробки зображень.

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

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

1. Мельник А.-В.В. Определение остова изображений, подлежащих автоматическому распознаванию / А.-В.В. Мельник, С.В. Мышко // Труды 8 международной научно-практической конференции «Современные информационные и электронные технологии».- Одесса, ОНПУ.- 2007. - С.55.

2. Мельник А.-В.В. Остов образа изображения, заданного на множестве атомарных элементов, как множество кратчайших путей / А.-В.В. Мельник, С.В. Мышко // Труды 9 международной научно-практической конференции «Современные информационные и электронные технологии» в 2 т.- Одесса, ОНПУ.- 2008. - Т.1. - С.29.

3. Мельник А.-В.В. Проблема скелетизации при проектировании систем распознавания цифровых изображений / А.-В.В. Мельник, С.В. Мышко, Д.В. Шевцов // Вісник Донецького національного університету (Серія А, Природничі науки). - Донецьк: ДонНУ. - 2008. - № 2. - С. 502-509.

4. Мельник А.-В.В. Моделируемость GT-объекта на дискретном множестве атомарных элементов / А.-В.В. Мельник, С.В. Мышко, Д.В. Шевцов // Вісник ХНТУ. - Xерсон: ХНТУ. - 2008. - № 3. - С. 223-300.

5. Мельник А.-В.В. Способ формирования GT-объектов образов изображений на множестве атомарных элементов // А.-В.В. Мельник, С.В. Мышко, Д.В. Шевцов // Зб. наук. праць Східноукраїнського національного університету ім. В. Даля. - Луганськ: СНУ ім. В. Даля. - 2009. - Вип. 2 - С.117-124.

6. Вайсруб Н.В. Применение способа формирования GT-объектов и способа автоматического моделирования изображений при проектировании систем технического зрения / Н.В. Вайсруб, А.-В.В. Мельник, С.В. Мышко, Д.В. Шевцов // Інформаційно-керуючі системи на залізничному транспорті.- Харьков: УкрДАЗТ. - 2009. - № 2 (75). - С. 55-59.

7. Мельник А.-В.В. Проблемы скелетизации при проектировании систем автоматического распознавания бинарных изображений / А.-В.В. Мельник, Д.В. Шевцов // Матеріали наукової конференції професорсько-викладацького складу, наукових співробітників і аспірантів Донецького національного університету за підсумками науково-дослідної роботи за період 2007-2008 рр. (Том 1. Природничі науки). - Донецьк, ДонНУ.- 2009. - С. 55.

8. Мельник А.-В.В. Разработка системы автоматической скелетизации бинарных изображений // Вісник ХНТУ. - Xерсон: ХНТУ. - 2009. - № 1(34). - С. 225-230.

АНОТАЦІЯ

Мельник Г.-В.В. Моделі та інформаційні технології скелетизації при попередній обробці бінарних зображень в системах електронного документообігу. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - інформаційні технології. - ДонНУ, Донецьк, 2009.

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

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

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

Ключові слова: системи електронного документообігу, скелетизація, множина атомарних елементів, шлях, GT-об'єкт, елемент представлення, утворююча.

АННОТАЦИЯ

Мельник А.-В.В. Модели и информационные технологии скелетизации при предварительной обработке бинарных изображений в системах электронного документооборота. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - информационные технологии. - ДонНУ, Донецк, 2009.

В диссертации рассматривается важная научно-практическая задача скелетизации бинарных изображений электронных копий документов.

Для того, чтобы по заданному изображению можно было построить модель, которую затем сверить с одной из заданных с целью распознавания, необходимо осуществить предобработку, называемую скелетизацией, основной задачей которой является получение такого изображения, которое соответствует исходному, но допускает построение модели. Показано, что целью данной обработки является построение GT-объекта как образа множества траекторий, реализация которых некоторым средством регистрации приведет к генерации изображения, одноименного исходному. В виду того, что изображение, обрабатываемое с помощью цифровой электронно-вычислительной машины, целесообразно моделировать на множестве атомарных элементов, предложена постановка задачи, которая предполагает формирование GT-объекта как множества кратчайших путей, каждый из которых сохраняет локально-глобальное направление. Обосновано, что множество кратчайших путей является GT-объектом только в том случае, если образующая формирует полное покрытие образа исходного изображения.

Для формирования по образу изображения искомого множества путей необходимо сформировать множество атомарных элементов, которые характеризуют локальную толщину фрагментов образа изображения. С этой целью введена функция, значения которой соответствуют расстоянию до ближайшего атомарного элемента изображения, связного с фоном. Тогда множество атомарных элементов, для которых можно определить локальную толщину, составляют множество М локальных максимумов; множество атомарных элементов P, для которых сохраняется локальная толщина; и S - множество атомарных элементов, которые связывают с минимальным изменением толщины множества P и (или) M. Обосновано, что не всегда АЭ множеств M, P, S являются образами траекторий, и, следовательно, формирование GT-объекта осуществляется на основе путей, выявленных на фрагментах следов без пересечений, которые затем объединяются в соответствии с гипотезой, т.е. с целью получения минимального количества кратчайших путей, каждый из которых регистрировался устройством фиксации следа наибольшего размера.

Введено понятие образующей - восстановленного по GT-объекту образа изображения, доказано, что образу изображения соответствует в общем случае множество GT-объектов.

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

Проведена апробация программного обеспечения на ЗАО «ДонецкСталь» - металлургический завод» и в страховой компании «Спич и К», позволившая повысить эффективность функционирования подсистемы распознавания в составе систем электронного документооборота.

Ключевые слова: системы электронного документооборота, скелетизация, множество атомарных элементов, путь, GT-объект, элемент представления, образующая.

THE SUMMARY

Melnik A.-V.V. The models and informational technology of skeletization under prior processing of images in the systems of electronic circulation of documents. - Manuscript.

The dissertation for obtaining the academic degree of candidate of technical sciences. Speciality 05.13.06 - Information Technologies - Donetsk National University, Donetsk, 2009.

Am important scientific and practical problem skeletization binary images of documents' electronic copies is considered in the dissertation.

On set by the image it was possible to construct model with the purpose of recognition, it is necessary to carry out preliminary processing - skeletization which primary goal is reception of such image which corresponds initial, but supposes construction of model. It is shown, that the purpose of the given processing is construction GT-objects as image of trajectories' set which realization by means of registration will result in generation image, same initial. The offered statement of a task on set of atomic elements that supposes formation of GT-object as sets of the shortest paths (each keeps a local-global direction). Formation of GT-object is carried out on the basis of the paths revealed for set atomic elements which correspond to the local geometrical center traces without crossings which are then united with the purpose of reception of a minimum quantity of the shortest paths, each of which was registered by the greatest size of the device of fixing of a trace. It is entered concepts forming - an image of the image restored on GT-object. It is proved, that an image of the image the set of GT-objects answers generally.

Efficiency of the offered path realized as the software, is proved to parameters of reliability of recognition, and also amount of objects which vectorings of skeletization's images grow out. Approbation of the software on Joint-Stock Company «DonetskStal» - a metal works» and in the insurance company «Spich and C» is lead with the purpose of increase of efficiency of functioning of a subsystem of recognition in structure of system of electronic document circulation.

Key words: electronic workflow systems, skeletization, set of atomic elements, path, GT-object, element of the representation, forming.

...