мацію і більш компактний, ніж растровий. Крім того, будь-яке редагування растрових файлів вкрай важко і вимагає великих витрат комп'ютерних ресурсів і часу оператора.
У світі до теперішнього моменту поки не придумали єдиного алгоритму векторизації растрових зображень. Це пояснюється тим, що існує багато умов як на вхідні формати і види растрових зображень, використовуваних в різних галузях життєдіяльності людини, так і на формати вихідних векторних даних. У кожної відомої ГІС є свій набір стандартів і сфер діяльності, для яких і створюються векторизатор.
У разі нашої задачі опису узагальненого алгоритму обмежимося найпростішими зображеннями растрової карти. Зображення складається з безлічі областей різного кольору, ці області виглядають як багатокутники опуклого або неопуклого виду. Шум на зображенні відсутній або ігнорується. Приклад такого зображення наведено на малюнку 2.
Рис. 2. Приклад растрового зображення карти місцевості
У зв'язку з такою інтерпретацією даних про карту можна виділити наступні етапи перетворення растру в його векторне подання:
завантаження растра (дискові або інші операції);
настройка зображення;
виділення контурів і «крайніх» точок областей;
угруповання точок однієї області, формування багатокутника (вектора);
коригування;
формування векторного формату.
Деякі типи зображень вимагають попередньої настройки. Налаштування - це процес обробки вихідного растрового зображення з метою приведення його до такого виду, який передбачає конкретний алгоритм векторизації. Розрізняють такі види налаштувань:
ручне налаштування в растровому графічному редакторі (експертна);
автоматична настройка із застосуванням графічних фільтрів і методів обробки;
комбінована настройка.
Ручна настройка проводиться експертом, знайомим з обмеженнями векторизації. Експерт вручну редагує растр, наприклад він виділяє залишилися після сканування нечіткі лінії і промальовує їх більш чітко. Він також може змінювати співвідношення контрасту і яскравості всього зображення, видаляти шум.
Автоматична настройка - певна заздалегідь послідовність графічних фільтрів, застосовуваних до оброблюваного зображенню. У результаті такої обробки передбачається отримати необхідну растрове зображення.
Комбінована настройка - результат синтезу двох попередніх залежно від специфіки проблеми.
Виділення контурів областей і крайніх точок - наступний етап, необхідний для попереднього виділення точок які описують ці області. Але отриманий результат не дасть інформації про те, яка група точок описують задану область, адже замкнутих областей одного кольору на зображенні може бути скільки завгодно (рис. 3). Для того щоб вирішити цю проблему, потрібно придумати способи щодо упорядкування точок однієї області та визначенню їх приналежності до тієї чи іншої області.
Рис. 3. Приклад виділення контурів областей і крайніх точок
Угрупування точок вирішує проблему упорядкування та приладдя. Алгоритми, які дозволяють це робити, дуже різноманітні і в загальному випадку зводяться до наступних можливих рішень: обхід контуру; побудова опуклої оболонки; кластеризація.
Метод обходу контуру є одним з найпопулярніших алгоритмів. Він простий у реалізації, досить швидкий і ефективний. У результаті обробки алгоритмом растра можуть бути отримані списки «крайніх» точок, а також всіх інших точок контуру; в порядку напрямку обходу контуру. Ці точки формують багатокутники, що описують області карти. Інші методи в цій роботі не розглядаються через їх складності.
Коригування служить для видалення «зайвих» багатокутників. Слово «зайві» говорить про надмірності інформації. Зазвичай в таких завданнях є деякі обмеження на кількість областей, їх лінійні розміри і т.д. Для нас таким критерієм служать лінійні розміри областей.
Формування векторного формату - кінцевий етап, на якому вирішуються додаткові завдання. Сюди відносять знаходження різних статистичних характеристик як всього зображення, так і характеристик деяких областей. Отриману векторну та іншу (додаткову) інформацію заносять в певну структуру даних, яка зберігається на носіях і використовується в подальшому сторонніми додатками. Така структура визначена заздалегідь.
Існує 3 методу векторизації зображення:
. При автоматичної векторизації потрібно тільки задати параметри і запустити процедуру. Програма сама визначить, які ра...
