Міщеряков Юрій Валентинович

УДК 004.896:004932.72

МАТЕМАТИЧНИЙ І ПРОГРАМНИЙ ІНСТРУМЕНТАРІЙ АВТОМАТИЗАЦІЇ ПРОЦЕСУ ПЕРЕТВОРЕННЯ КОНСТРУКТОРСЬКОЇ ДОКУМЕНТАЦІЇ В ЕЛЕКТРОННИЙ ВИГЛЯД

05.13.12 – Системи автоматизації проектувальних робіт

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

Харків – 2003

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

Робота виконана на кафедрі системотехніки Харківського національного університету радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник– | доктор технічних наук, професор Петров Е.Г., Харківський національний університет радіоелектроніки, завідуючий кафедрою системотехніки. | Офіційні опоненти: | доктор технічних наук, професор Путятін Є.П., Харківський національний університет радіоелектроніки, завідуючий кафедрою інформатики.

доктор технічних наук, професор Ходаков В.Є., Херсонський державний технічний університет, завідуючий кафедрою інформаційних технологій.

Провідна установа– | Національний технічний університет “Харківський політехнічний інститут” (кафедра автоматизованих систем управління), Міністерство освіти та науки України.

Захист відбудеться “ 29 04 2003 року о 13.00 годині на засіданні спеціалізованої вченої ради Д .052.02 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись в бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий “ 27 03 2003 року

Вчений секретар

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

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

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

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

Задача перетворення конструкторської документації в електронний вигляд розглядалася багатьма авторами. Значний внесок у розвиток даного напрямку досліджень внесли Путятін Є.П., Шлезингер М.І., Павлідіс Т., Дуда Р., Фолі Дж., Вельтмандер П.В. і ін. Їх роботи присвячені різним аспектам вирішення даної проблеми: усуненню завад на растрових зображеннях, нормалізації растрових зображень, проблемам сегментації, представлення растрової і векторної ін-фор-мації в ЕОМ, розпізнаванню образів.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки в рамках держбюджетної теми № “Розробка математичних методів, алгоритмів і інструментальних засобів надшвидких перетворень зображень” (№ ГР U001948), що входить до складу координаційного плану Міністерства освіти і науки України. Здобувач брав участь у виконанні робіт як виконавець.

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

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

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

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

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

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

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

Предмет дослідження – зашумлені бінарні растрові зображення, що містять, у загальному випадку, зіпсовані примітиви (відрізки прямих, дуги кола).

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

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

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

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

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

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

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

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

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

Практичне значення результатів підтверджується їх впровадженням. У цілому програмний комплекс Vectorizator впроваджений в АТ “Хартрон” для подання існуючої конструкторської документації на паперових носіях у векторному вигляді (довідка від 08.10.02), в АТ ЗТ “Інститут автоматизованих систем” – для автоматизації процесу перетворення конструкторської документації в електронний вигляд (довідка від 09.08.02), ВАТ “Головне спеціалізоване конструкторське бюро по двигунах середньої потужності” при автоматизації перетворення креслень, поданих у растровому вигляді, у векторний вигляд, з метою їх використання в САПР (довідка від 19.09.02).

Розроблені математичний і програмний інструментарій автоматизації перетворення конструкторської документації в електронний векторний вигляд використовуються в навчальному процесі на кафедрі інженерної і комп'ютерної графіки Харківського національного університету радіоелектроніки при викладанні курсів: “Комп'ютерна графіка”, “Інженерна і комп'ютерна графіка”, а також у лабораторному практикумі з цих дисциплін (акт впровадження від 15.10.02).

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

Апробація результатів дисертації. Основні результати роботи доповідалися і обговорювалися:

- на IV – VI Міжнародних конференціях “Теорія і техніка передачі, прийому і обробки інформації” (Харків – Туапсе, 1998, 2000, 2001 р.);

- на V – VI Міжнародному молодіжному форумі “Радіоелектроніка і молодь у XXI столітті” (Харків, 2000, 2001 р.);

- на Міжнародному семінарі “Інформаційні технології в освіті та управлінні” (Херсон, 2002 р.).

Публікації. За темою дисертації опубліковано 10 наукових праць, у тому числі, 4 статті у виданнях, що ввійшли в переліки ВАК України, і 6 публікацій у збірниках праць наукових конференцій.

Структура дисертації. Дисертація складається з вступу, 4 розділів, висновків, списку використаних джерел, 2 додатків. Повний обсяг дисертації містить 175 сторінок, у тому числі 2 додатки, 62 рисунка, 9 таблиць, список використаних джерел з 128 найменувань.

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

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

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

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

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

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

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

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

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

де – площа вікна; – вікно навколо елементу ; – поточна точка.

Якщо визначити вікно у вигляді прямокутника з основою та висотою , то регуляризований варіант буде мати такий вигляд:

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

де – нове значення функції інтенсивності в центральному елементі вікна; – елементи вікна, крім центрального.

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

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

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

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

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

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

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

де  – координати поточної точки зображення, для якої провадиться перерахування; – координати точки, щодо якої провадиться поворот; - кут, на який повертається зображення.

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

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

a) | b) | Рис. . Поворот зображення на кут
a) вихідне зображення; b) зображення після повороту.

У тому випадку, коли існує перекіс креслення, в роботі передбачено відновлення його нормального стану. Оператори, що відповідають даному перетворенню, мають такий вигляд:

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

Слід відзначити, що послідовне застосування перетворень і приводить до повороту вихідного зображення на 180.

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

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

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

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

Первинне зображення являє собою матрицю точок. Білі точки належать фону, чорні – об'єкту (лінії). Відповідно до обраної послідовності розв'язуваних задач () необхідно виділити точки, з яких складається об'єкт. Для цього зображення проглядається по рядках, із рядка виділяються безупинні послідовності пікселів (точок растра), що належать об'єктам. Виділені послідовності пікселів позначимо як “діапазони” d. Таким чином, по закінченню перегляду початкове зображення буде представлено у вигляді відрізків горизонтальних ліній – діапазонів.

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

де ,– - координати знайденого діапазону; , – - координати діапазону, обраного з множини.

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

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

З метою пошуку ліній креслення здійснюється апроксимація по центрах діапазонів. Для цих цілей використовується метод найменших квадратів. Для запобігання ситуації ділення на 0 при обчисленні коефіцієнтів і , передбачено поворот системи координат (осі 0Х и 0Y змінюються місцями). Надалі необхідно враховувати, у якій системі координат розраховані коефіцієнти.

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

Обчислення товщини ліній, у даному випадку, може бути здійснене таким способом. На кожній ліній вибирається кілька точок (від трьох до 10), їх кількість залежить від довжини лінії. Потім визначається товщина в кожній обраній точці лінії у пікселях. Отримані дані усереднюються. В залежності від дозволу зображення, зі списку ДСТУ вибирається товщина, найбільш відповідна знайденому значенню і присвоюється лінії. У результаті вище описаних дій отримано набір ліній, апроксимуючих креслення. Однак кінці цих ліній не будуть стикуватися.

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

де , – коефіцієнти першої лінії; , – коефіцієнти другої лінії.

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

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

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

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

На практиці растрове зображення, як правило, має шуми. Після відділення об'єкта від фону і розподілу знайдених діапазонів по множинах, шуми будуть подані у вигляді ок-ре-мих множин. Такі множини будуть містити 1-3 діапазони (параметр, що настроюється, та задається до початку векторизації) і довжина цих діапазонів, менше ніж 5-20 пікселів (параметр, що настроюється). Діапазони, які є шумами, обведені овалом (). Усі множини, які відповідають шумам (у залежності від параметрів, що настроюються), виключаються з розгляду.

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

де , , , – - координати діапазонів;  – кількість діапазонів.

До обраних діапазонів додається наступний діапазон з множини та для діапазонів перераховується зміна їхніх довжин . Якщо виконується умова

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

Після розподілу діапазонів по множинах, у залежності від зміни їх довжини, отримані множини маркіруються певним чином ().

Визначення типу множини здійснюється в такий спосіб:

Рис. . Маркірування списків
а) – сильне збільшення довжин діапазонів; б) – сильне зменшення довжин діапазонів;
в) – слабке збільшення довжин діапазонів; г) – слабке зменшення довжин діапазонів;
д) – немає зміни довжин діапазонів. | - якщо зміна довжин діапазонів у множині (параметр, що настроюється, рекомендується вибрати рівним 5), то вважається, що ця множина із діапазонами, що сильно збільшуються;

- якщо (параметр, що настроюється, рекомендується вибрати рівним 0,2) і , то вважається, що ця множина із діапазонами, що слабко збільшуються;

- якщо , то вважається, що ця множина із діапазонами, що сильно зменшуються;

- якщо і , то вважається, що ця множина із діапазонами, що слабко зменшуються;

- якщо і , то вважається, що довжина діапазонів у множині не змінюється.

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

де - множина типу а); - множина типу д); - множина типу б).

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

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

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

,

де , – початкові значення коефіцієнтів a і b; , – поточні значення коефіцієнтів і ;  – припустима помилка зміни коефіцієнтів і .

Якщо умова виконується, то додається ще k діапазонів і перевірка умови повторюється. У протилежному випадку поточна множина переривається і наступні діапазони переносяться в нову множину. Описана процедура здійснюється для усіх початкових множин.

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

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

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

- множини повинні мати однакові чи близькі типи;

- середня довжина діапазонів обох множин повинна бути однаковою;

- різниця коефіцієнтів і обох множин не повинна перевищувати , крім того, коефіцієнти і повинні бути розраховані в одній системі координат (обидва в XOY або YOX);

- діапазони повинні мати перекриття , що обчислюється за формулами -;

- множини також поєднуються, якщо в одній з них перебуває усього один діапазон.

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

Серед діапазонів, кінці яких потрапляють в околи і , шукаються координати і ().

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

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

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

а)б)

Рис. . Немає сполучення і стикування кінців ліній

У деяких випадках через погану якість початкового креслення виникають розриви ліній (а).

У цьому випадку необхідно знаходити розірвані лінії і об'єднувати їх. Для об'єднання повинен виконатися ряд умов:

- найближчі кінці різних ліній повинні бути на відстані не більше, ніж D (параметр, що настроюється);

- коефіцієнти і обох ліній не повинні відрізнятися більш ніж на (припустима помилка зміни коефіцієнтів і ), а також і мають бути розраховані в одній системі координат (обидва в XOY або YOX);

- обидві лінії мають бути однієї товщини.

Значення параметру D обумовлює максимальну довжину розриву, через яку може пройти лінія. Якщо обидві умови виконуються, то дві лінії заміняються однією (б). Слід зазначити необхідність акуратного вибору параметру D. Це пов'язано з тим, що на кресленні можуть бути присутні штрихпунктирні лінії, і вони можуть бути замінені однією безперервною лінією, замість того, щоб бути розпізнаними як одна штрихпунктирна лінія.

а) | б)

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

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

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

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

Розроблений програмний засіб має модульну структуру, наведену на .

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

Рис. . Структура програмного засобу | Модуль читання/запису зображень призначений для читання з файлу і запису у файл растрових, векторних зображень, проекту (растрова і векторна графіка), а також для експортування векторної графіки у формат DXF (AutoCAD).

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

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

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

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

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

Таблиця

Часові витрати на обробку зображення |

Час обробки, сек. | Розмір зображення, точки | Медіанна фільтрація | Анізотропна фільтрація | Виділення границь | Поворот
зображення | Косий зсув зображення | Дзеркальне відображення | 450x650 | <1 | 2 | <1 | <1 | <1 | <1 | 900x1300 | <1 | 7 | <1 | 1 | 1 | <1 | 1800x2600 | 3 | 26 | 3 | 7 | 7 | 1 |

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

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

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

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

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

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

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

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

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

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

Отримані результати використані в АТ “Хартрон” (м. Харків) для перетворення графічної документації на паперових носіях в електронний вигляд, а також при розвитку системи автоматизованого проектування, в АТ ЗТ “Інститут автоматизованих систем” (м. Харків) - для автоматизації процесу перетворення конструкторської документації в електронний вигляд при створенні електронних архівів креслень, у ВАТ “Головне спеціалізоване конструкторське бюро по двигунах середньої потужності” - при автоматизації перетворення креслень, представлених у растровому вигляді, у векторний вигляд з метою їхнього використання в САПР.

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

1. Мищеряков Ю.В. Алгоритмы распознавания отрезков прямых на чертежах //Вестник Херсонского государственного технического университета. –2002. –№ 8. – С. 380-384.

2. Мищеряков Ю.В. Методы распознавания прямолинейных отрезков
на чертежах //АСУ и приборы автоматики. –2002. –Вып. 140. – С. 77-84.

3. Овезгельдыев А.О., Мищеряков Ю.В., Евсеева И.В., Об одном подходе к автоматизации изготовления рекламной продукции //Вестник Херсонского государственного технического университета. –1999. –№ 1(5). – С. 140-142.

4. Плехова А.А., Мищеряков Ю.В., Шубин И.Ю. Модель и метод решения базовой задачи о построении гладкой трассы //АСУ и приборы автоматики. –1999. –Вып. . – С. 65-71.

5. Мищеряков Ю.В. Бредихин В.М. Автоматизация перевода конструкторской документации в электронный вид //Сб. науч. тр. по материалам 4-го Междунар. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. –Харьков: ХТУРЭ, 2000. – С. 245–246.

6. Мищеряков Ю.В. Бредихин В.М. Предварительная обработка конструкторской документации в электронный вид пригодный для редактирования //Сб. науч. тр. 6-й Междунар. конф. “Теория и техника приема, передачи и обработки информации”. –Харьков: ХТУРЭ, 2000. – С. 303-304.

7. Мищеряков Ю.В., Костин Д.В., Перетятько Ю.В. Разработка программных средств автоматизации процессов распознавания конструкторской документации //Сб. науч. тр. 8-й Междунар. конф. “Теория и техника приема, передачи и обработки информации”. –Харьков: ХТУРЭ, 2002. – С. 275-277.

8. Мищеряков Ю.В., Костин Д.В., Перетятько Ю.В. Разработка программного обеспечения для перевода конструкторской документации в электронный вид //Сб. науч. тр. 7-й Междунар. конф. “Теория и техника приема, передачи и обработки информации”. –Харьков: ХТУРЭ, 2001. – С. 289-290.

9. Петров Э.Г., Мищеряков Ю.В. Автоматическое распознавание образов //Сб. науч. тр. по материалам 3-го Международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. –Харьков: ХТУРЭ, 1999. – С. 372-373.

10. Борячок М.Д., Мищеряков Ю.В. Бредихин В.М. Об обработке графических изображений //Сб. науч. тр. 4-Междунар. конф. “Теория и техника приема, передачи и обработки информации”. –Харьков: ХТУРЭ, 1998. – С. 332.

АНОТАЦІЯ

Міщеряков Ю.В. Математичний і програмний інструментарій автоматизації процесу перетворення конструкторської документації в електронний вигляд. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 – системи автоматизації проектувальних робіт – Харківський національний університет радіоелектроніки, Харків, 2003.

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