ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

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

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

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

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

1.1 Актуальність теми

Завдання автоматизованої обробки даних стояло перед людством ще з часів появи самих даних. Але тільки з появою цифрових форматів збереження цей процес значно просунувся вперед. Ще в 60-х роках XX століття [7] Хаф запропонував перетворення, що дозволяє переводити координати точок двомірного простору в дані акумуляторного масиву з подальшим застосуванням процедури голосування. І хоча в той час цифровий формат зберігання був не особливо поширений, проте, дане перетворення дуже зацікавило наукове співтовариство. У подальшому різними вченими були запропоновані варіанти даного алгоритму для знаходження не тільки лінії, але й кіл, еліпсів і навіть об'єктів довільної форми [12].

З часом розповсюдження цифрових форматів зображень дало ще більший поштовх до освоєння області автоматичної обробки зображень. І до перетворення Хафа стали звертатися все частіше. Виникло безліч його модифікацій, які прискорювали алгоритм і робили його досить швидким. Це дозволяло застосовувати його в реальних системах виявлення об'єктів [14] і навіть в системах реального часу. Так само позитивним моментом у розвитку цього напряму став грати той факт, що з кожним роком обчислювальна потужність сучасних ЕОМ зростає, що так само допомагає прискорити процес пошуку об'єктів на зображенні.

Вже зараз перетворення Хафа може застосовуватися в таких областях як розпізнавання контурів будівель на зображеннях [11], визначення лінії горизонту [9], знаходження ліній дорожньої розмітки, визначення кількості осей у рухомого транспорту та інших сферах.

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

1.2 Мета і задачі дослідження

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

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

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

В процесі роботи необхідно вирішити наступні задачі:

1) дослідження існуючих методів пошуку об'єктів на зображенні і виділення з них найбільш продуктивних і популярних;

2) детальний розгляд окремих випадків цих методів для виявлення різних типів об'єктів;

3) розробка оптимізованих методів, що дозволяють прискорити базовий алгоритм пошуку об'єкта;

4) програмна реалізація базових і оптимізованих методів з метою порівняння їх швидкості виконання та ефективності розпізнавання.

1.3 Наукова новизна

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

1.4 Практична значимість

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

2 Сучасний стан проблеми

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

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

У джерелі [2] обговорюється рандомізоване перетворення Хафа для пошуку еліпсів на зображенні. Пояснюються рівняння для знаходження еліпсів та їх реалізація. Алгоритм показав хороші результати при знаходженні еліпсів з кутом нахилу 0 і 90 градусів до осі координат на зображенні. Також наведені приклади пошуку і знаходження еліпсів на реальних зображеннях після передобробки даних зображення.

У джерелі [6] описується перетворення Хафа для пошуку ліній і кіл на монохромному цифровому зображенні. Описана основна ідея методу, приклад виділення прямих і кіл на зображенні. Описано загальний випадок алгоритму пошуку прямих на зображенні за допомогою перетворення Хафа. Також описані деякі модифікації цього перетворення.

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

У джерелі [8] описується перетворення Хафа для пошуку ліній і кіл на зображенні з використанням бібліотеки OpenCV. Детально описано перетворення Хафа для ліній і наведений початковий код алгоритму на мові С++, також описані функції бібліотеки OpenCV, що реалізують це перетворення. Описано алгоритм для пошуку кіл і відповідні функції бібліотеки OpenCV, представлений приклад відповідної програми. Наведені результати роботи написаних програм з описом отриманого результату.

У джерелі [9] описується пошук на зображенні кута його відхилення від лінії горизонту і відповідне його коригування. Алгоритм пошуку лінії горизонту проводиться за допомогою перетворення Хафа. Описана суть перетворення, параметричне рівняння та особливості його реалізації для даного завдання. Наведена наочна покрокова ілюстрація пошуку лінії горизонту і коректування зображення після її знаходження.

У джерелі [10] описується перетворення Хафа для пошуку кіл і ліній. Описано різновиди цього перетворення для пошуку ліній і деталі реалізації в бібліотеці OpenCV. Зокрема описані функції цієї бібліотеки, передані їй параметри і значення які повертаються. Наведено ілюстрації роботи функцій з різними переданими їй параметрами.

У джерелі [11] описуються метод відновлення 3D-моделей будівель зі знімків двомірних зображень. Метод заснований на визначенні рівнів деталізації. Розглядаються кожен з трьох рівнів деталізації. Також у роботі описується як може бути застосоване перетворення Хафа для виявлення кордону будівель.

У статті [12] описано перетворення Хафа як метод для виявлення кривих, використовуючи два параметри точки на кривій і параметри самої кривої. На початку роботи показано як виявляти як аналітичні так і не аналітичні криві, які обмежені кордонами бінарної картинки. В результаті робота була узагальнена для виявлення деяких аналітичних кривих у чорно-білих зображеннях, зокрема ліній, кіл і парабол.

У джерелі [13] розглянуто перетворення Радону, його властивості та основні типи. Розглянуто задачу розпізнавання простих геометричних об'єктів на монохромному зображенні на підставі інтегрального перетворення простору зображення в простір параметрів об'єкта. Наведено алгоритми пошуку найпростіших геометричних об'єктів на зображенні.

У джерелі [14] розглядаються особливості алгоритмів пошуку відбитка печатки на зображенні документа на основі перетворення Хафа. Наводяться результати досліджень для базового алгоритму Хафа і модифікованого, в якому додатково використовується градієнт яскравості для більш швидкого знаходження радіуса печатки і прискорення її пошуку.

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

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

3 Аналіз перетворення Хафа для задачі пошуку двовимірних геометричних примітивів на зображенні

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

Класичний алгоритм перетворення Хафа був призначений для знаходження прямих на зображенні, але пізніше алгоритм був розширений і тепер його можна застосовувати для виявлення як інших параметризуємих об'єктів (наприклад, еліпсів [2], кіл [14], парабол), так і не параметризуємих об'єктів довільної форми [12].

Як було сказано раніше класичне перетворення Хафа є лінійним і застосовується для виявлення прямих. Пряма задається рівнянням y=mx+b і може обчислюватися для будь-якої пари активних точок на зображенні (x,y). Головна ідея перетворення Хафа – враховувати характеристики прямих у термінах її параметрів, тобто параметрів m та b. Таким чином, простір параметрів для ліній буде двомірним і складатиметься з двох параметрів – кута нахилу m і точки перетину прямої з віссю OY, b. Але для даного типу рівняння існує проблема задавання вертикальних прямих, тому що в цьому випадку отримуємо нескінченні значення параметрів m та b. Якщо ж представити пряму через параметри вектора, перпендикулярного цій прямій, який проходить через початок координат, то ця проблема зникне. Задамо пряму через два параметри R і θ. R представляє собою довжину зазначеного вектора, а θ – кут вектора до осі координат.

У цьому випадку рівняння прямої буде представлено в такому вигляді:

Або ж воно може бути змінено до наступного вигляду: r = x*cos θ + y*sin θ.

Таким чином, кожна пряма на зображенні може бути представлена двома параметрами свого вектора нормалі – r та θ. Ці параметри будуть унікальними за умови що θЄ[0,PI] і rЄR, або якщо θЄ[0,2PI] і r>=0. Створивши акумуляторний масив з певним кроком, зможемо заносити в нього значення заданих параметрів. Цей масив також називають простором Хафа для прямих на площині або просто накопичувальним простором.

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

Де r та θ можуть мати довільні значення з вищевказаного діапазону.

Це відповідає синусоїдальній кривій в накопичувальному просторі (r,θ), яка унікальна для кожної окремої точки. Синусоїди декількох точок накладаються одна на одну. Точки їх перетину в просторі параметрів задають параметри прямих – (r,θ), які проходять через точки котрі задають синусоїди. Таким чином точки, які формують пряму лінію, визначають синусоїди, які перетинаються в одній точці, яка задає параметри шуканої лінії. Задача пошуку прямої лінії, врешті решт, зводиться до задачі пошуку максимума в накопичувальному просторі параметрів.

3.1 Перетворення Хафа для пошуку ліній

Нехай задано N активних точок на зображенні (точок за якими потрібно знайти пряму лінію).

Нехай є безліч плоских ліній L(R,θ), котрі задаються в параметричному вигляді параметрами R, θ. Перший параметр це довжина перпендикуляра від прямої до точки початку координат, другий – кут між перпендикуляром прямої і віссю координат (нехай це буде вісь OX). Таким чином, підставивши ці параметри в параметричне рівняння, зможемо відновити початкове рівняння прямої.

Параметри прямих утворюють двомірний простір Хафа, по одній осі якого буде змінюватись параметр R, по іншій осі параметр θ. Цей простір нам необхідно зробити дискретним, для цього нам потрібно знати мінімальне і максимальне можливе значення радіуса (R) і кута (θ). Мінімальний радіус буде дорівнює нулю (пряма проходить через початок координат), максимальний – відстані від найвіддаленішої активної точки зображення до початку координат. Мінімальний кут дорівнює 0 градусів, максимальний – 2*PI (або 360 градусів). Також визначимо розмірність нашої таблиці – нехай по осі R вона дорівнює k, а по осі θ дорівнює m. Тоді масив прямих можна зобразити як L[k][m]. Значення радіуса в клітинці L[i][j] дорівнює:

R(L[i][j]) = Rmin + dR*i,

де Rmin – мінімальний радіус (дорівнює нулю);
            dR = (Rmax-Rmin)/k.

Значення кута в клітинці L[i][j] дорівнює:

θ(L[i][j]) = j*dθ,

де dθ = 2*PI/m.

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

У загальному вигляді алгоритм Хафа для пошуку прямої лінії на зображенні буде виглядати так:

  1. Обчислити максимальне значення віддаленості активних точок від початку координат – Rmax.
  2. Задати розмірність простору Хафа для кута (θ) і для радіуса (R).
  3. Обчислити параметри dR и dθ.
  4. Створити матрицю, в яку заносяться дані про кількість активних точок, що лежать на прямій з заданими параметрами – L(R,θ), її розмір дорівнює – L[k][m].
  5. Обнулити усі значення матриці L(R, θ).
  6. Цикл по всім активним точкам зображення – Ti(Xi,Yi):
        Цикл по j від 0 до 2*PI з кроком dθ:
            θ = j * dθ;
            R = Xi*cos(θ) + Yi*sin(θ);
            Rтек = Rmin;
            k = 0;
            Поки |Rтек-R|>dR/2:
                Rтек = Rтек + dR;
                k = k + 1;
            Кінець Поки;
            L[k][j] = L[k][j] + 1;
        Кінець циклу по j;
    Кінець циклу по всім точкам.
  7. Знайти клітинку L[i][j] з максимальним значенням лічильника.
  8. Відновити параметри прямої по клітинці L[i][j] відповідно до формул:
        R(L[i][j]) = dR*i;
        θ(L[i][j] = j*dθ;
  9. Вивести знайдені параметри R і θ.

3.2 Перетворення Хафа для пошуку кола

Перетворення Хафа успішно застосовується для пошуку кіл на растровому зображенні.

Геометрично коло становить собою безліч точок, рівновіддалених від однієї точки – центру кола. Рівняння кола має вигляд: (x-a)^2+(y-b)^2=R^2, де (x,y) – координати будь-якої точки кола, (a,b) – координати центру кола, R – радіус кола.

Таким чином, будь-яке коло можна задати трьома параметрами: радіус (R) і координати центру кола (a,b). Отже накопичувальний простір Хафа буде тривимірним (R,a,b). Якщо при пошуку кола відомий його радіус, тоді накопичувальний простір буде двовимірним (невідомі параметри шуканої окружності – координати її центру (a,b)).

Нижче у загальному вигляді описаний алгоритм Хафа для пошуку кіл.

  1. Задати максимальний радіус кола – Rmax.
  2. Задати кордони розміщення центру кола – Xmin, Xmax, Ymin, Ymax.
  3. Створити масив, в якому зберігаються дані про кола і кількість точок, через які вони проходять:
    C[Xmax-Xmin][Ymax-Ymin][Rmax].
  4. Обнулити масив C[a][b][R].
  5. Цикл по всіх активних точках (Xi, Yi) зображення:
        Цикл по а від Xmin до Xmax з кроком dX=1:
            Цикл по b від Ymin до Ymax з кроком dY=1:
                R := SQRT((Xi – a)^2 + (Yi – b)^2);
                C[a][b][R] := C[a][b][R] + 1;
            Кінець циклу по b;
        Кінець циклу по а;
    Кінець циклу по всім точкам.
  6. У масиві C[a][b][R] знайти клітинку з максимальним значенням.
  7. Знайти параметри рівняння кола по знайденій клітинці C[i][j][k]:
        a := i;
        b := j;
        R := k.
  8. Вивести знайдені параметри.

3.3 Застосовуваність перетворення Хафа

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

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

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

Висновки

У роботі були проаналізовані методи пошуку двовимірних геометричних примітивів на зображенні. В результаті виконання були вивчені літературні та Інтернет джерела, в яких описувалися подібні методи. Найбільш простим, але досить ефективним методом виявився метод перетворення Хафа. Цей метод може успішно застосовуватися для розпізнавання таких геометричних об'єктів на зображенні – лінії, кола, еліпси, а також непараметричні об'єкти. У проаналізованих джерелах були вивчені випадки цього перетворення для всіх зазначених типів геометричних об'єктів.

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

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

Список джерел

  1. The Hough Transform [Електронний ресурс]. – Режим доступу : http://homepages.inf.ed.ac.uk/rbf/CVonline....
  2. Samuel A. Inverso. Computer Vision: Ellipse Detection Using Randomized Hough Transform [Електронний ресурс]. – Режим доступу : http://www.saminverso.com/res/vision/.
  3. James Matthews. Hough Transforms [Електронний ресурс]. – Режим доступу : http://www.generation5.org/content/2008....
  4. Алгоритм Хафа для обнаружения произвольных кривых на изображениях [Електронний ресурс]. – Режим доступу : http://habrahabr.ru/blogs/algorithm/102948/.
  5. Использование преобразований Хафа (Hough transform) для выделения прямых на изображении [Електронний ресурс]. – Режим доступу : http://eddy-em.livejournal.com/932.html.
  6. Дегтярева A. Преобразование Хафа [Електронний ресурс]. – Режим доступу : http://www.cgm.computergraphics.ru/content/view/36.
  7. Преобразование Хафа [Електронний ресурс]. – Режим доступу : http://ru.wikipedia.org/wiki....
  8. OpenCV шаг за шагом. Преобразование Хафа [Електронний ресурс]. – Режим доступу : http://robocraft.ru/blog/computervision....
  9. Коррекция наклона (skew correction) [Електронний ресурс]. – Режим доступу : http://bik-top.livejournal.com/37060.html.
  10. Преобразования Хафа [Електронний ресурс]. – Режим доступу : http://locv.ru/wiki....
  11. Arefi H. Levels of detail in 3D building reconstruction from lidar data / [H. Arefi, J. Engels, M. Hahn, H. Mayer.]. – Stuttgart : Stuttgart University of Applied Sciences; Munich : Bundeswehr University Munich, 2008. – 490с.
  12. Ballard D. H. Generalizing the Hough transform to detect arbitrary shapes / Ballard D. H. – New York : Computer Science Department, University of Rochester, 1980 – 122с.
  13. Запрягаев С. А. Программная оболочка для поиска примитивов на изображении / С. А. Запрягаев, А. И. Сорокин // Вестник ВГУ, серия: системный анализ и информационные технологии. – Воронеж, 2008. – № 2. – С. 37-47.
  14. Сай И. С. Эффективность алгоритмов поиска оттиска печати в изображении документа / Сай И. С. // Вестник ТОГУ. – 2009. – № 4. – C. 53-60.
  15. Семенов А.Б. Обработка и анализ изображений с использованием языка JAVA, курс лекций / Семенов А.Б. – Тверь : Тверской государственный университет, 2007. – 10 c.

Важливе зауваження

При написанні даного автореферату магістерська робота ще не завершена. Приблизна дата завершення – 1 грудня 2012 р. Повний текст роботи, а також матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.