Растрове зображення зображення як двовимірний масив даних. Растрове зображення зображення як двовимірний масив даних Алгоритми розпізнавання образів на зображеннях
УДК 004932: 621.396
Т.М. ВЛАСОВА, В.Г. КАЛМИКОВ
АЛГОРИТМ І ПРОГРАМА РОЗПІЗНАВАННЯ КОНТУРІВ ЗОБРАЖЕНЬ ЯК ПОСЛІДОВНОСТІ відрізків ЦИФРОВИХ ПРЯМИХ
Abstract: In the given work the algorithm of the recognition of the digital direct line segment in contours of the binary images and the software implementation of the algorithm is considered. Utilization of this algorithm to process the images will result to more natural and economical description in comparison with known ways of the description of the images. The considered algorithm and the software implementation can be used also for the description of contours when processing the half-tone and colour images.
Key words: image, contour, digital straight segments, algorithm, program.
Анотація: У даній работе наводитися алгоритм розпізнавання відрізків цифрових прямих у контурах бінарніх збережений, а такоже програмна реалізація алгоритму. Використання цього алгоритму для оброблення зображення прізведе до того, что описание збережений буде більш натуральним та економного порівняно з відомімі засоби кодування зображення. Запропоновані алгоритм и програмна реалізація могут застосовуватісь для кодування контурів при обробленні напівтоновіх та кольорових збережений. Ключові слова: зображення, контур, відрізкі цифрових прямих, алгоритм, програма.
Анотація: У даній роботі розглядаються алгоритм розпізнавання відрізків цифрових прямих у контурах бінарних зображень і програмна реалізація алгоритму. Використання цього алгоритму при обробці зображень призведе до більш природного і економного порівняно з відомими способами опису зображень. Розглянутий алгоритм і програмна реалізація можуть бути використані також і для опису контурів при обробці напівтонових і кольорових зображень. Ключові слова: зображення, контур, відрізки цифрових прямих, алгоритм, програма.
1. Введення
Структурний аналіз контурів зображень як послідовностей відрізків прямих і дуг кривих є однією з основних задач при обробці зображень з метою їх інтерпретації в системах штучного інтелекту.
У більшості випадків зображення можна розглядати як частину площини, розділену на області з постійними або змінними по деякому закону параметрами, наприклад, оптичною щільністю, кольором, текстурою, що визначають фон і об'єкти зображення. Невід'ємною властивістю кожної з цих областей є її межа, тобто контур -односвязная послідовність, що складається з відрізків прямих і дуг кривих. При обробці растрових зображень зазвичай виділяються контури об'єктів. Однак контури об'єктів, представлені у вигляді сукупності окремих, граничних пікселів мало придатні для подальшої обробки, оскільки недостатньо висловлюють його геометричну сутність.
Розпізнавання контурів зображень у вигляді послідовності відрізків прямих можна вважати однією з основних задач в процесі обробки растрового зображення. Рішення завдання уявлення контуру у вигляді послідовності відрізків прямих дозволяє отримати опис зображення в компактному вигляді, природному для людського сприйняття, інваріантному щодо афінних перетворень, зручному, зокрема, для обробки нейросетями. Відрізки прямих є основними елементами контуру. Дуга кривої також часто замінюється вписаною в неї ламаною лінією як в основних положеннях математичного аналізу, так і у великій кількості практичних застосувань.
Відомі методи і алгоритми, зокрема, запропоновані в роботі, дозволяють отримати наближене рішення, що прийнятно не для всіх додатків.
У даній роботі розглядається розпізнавання контуру бінарного зображення як послідовності відрізків цифрових прямих без втрати інформації.
2. Контур як послідовність відрізків цифрових прямих
В даному розділі розглядається структурний аналіз контурів зображень як послідовності відрізків цифрових прямих, які є вихідними даними для сегментації контуру на дуги цифрових кривих і відрізки цифрових прямих.
Обмежимося розглядом бінарних зображень, об'єкти яких повністю визначаються обмежують їх контурами. Дуги цифрових кривих, як і відрізки цифрових прямих, утворюються при дискретизації зображень, що містять контури, утворені відрізками прямих і дугами кривих.
Характерні ознаки відрізків прямих і дуг кривих в процесі перетворення втрачаються. Розглядаючи дискретизованного зображення при достатньому збільшенні, часто важко буває дізнатися окремі відрізки прямих і дуги кривих в послідовності
вертикальних і горизонтальних відрізків. Додаткові труднощі виникають при обробці через те, що лінії контурів - математичні лінії без товщини - відображаються на екрані монітора зв'язковими послідовностями пікселів, тобто візуальними лініями, які мають товщину.
Щоб виключити виникають через це проблеми, будемо розглядати зображення, отримане з початкового в результаті дискретизації, як двовимірний клітинний комплекс. В такому випадку
пікселі є двовимірними елементами цього клітинного комплексу. Крім пікселів, є крек і точки. Крек - це
боку пікселів, що є одновимірними елементами. Точки є кінцевими точками креків і кутовими точками пікселів. Точки є нольмернимі елементами. Таким
чином, в даному випадку контур об'єкта - це зв'язкова замкнута послідовність контурних креків, граничних між пікселями об'єкта і фоном. Контур може бути описаний як послідовність цілочисельних координат точок,
обмежують контурні крек. Як показано в, уявлення площині зображення як
клітинного комплексу дає багато переваг. Зокрема, межа області стає тонкою кривої з нульовою площею.
На рис. 1 наведені приклад вихідного контуру об'єкта, утвореного дугою кривої і відрізком прямої, а також його цифровий еквівалент як послідовність креків. Пронумеровані точки, що належать крек різних напрямків. Як і в роботах, під Ь -елементом будемо розуміти зв'язну послідовність креків одного і того ж напрямку, що виходить з деякої точки і закінчується креком того ж або перпендикулярного напрямку. На рис. 1 приведено одне з можливих розбиттів контуру на Ь -елементи, які утворені крек між точками: (0-2), (2-4), (4-6), (6-8), (8-9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25), (25-27 ), (27-0). Кожен Ь -Елемент характеризується такими параметрами: напрямом щодо початкової його точки g (прийнято g = 0 - для направлення вгору, 1 - вправо, 2 - вниз, 3 - вліво); l - кількістю креків напрямки g (! = 1,2, ...); напрямком останнього крека q щодо направлення g попередніх креків (q = -1 - останній крек спрямований вліво щодо направлення g, +1 - вправо, 0 - збігається з напрямком g). Кількість креків l умовно будемо називати "довжиною" Ь -елементом Для Ь -елементом (0-2) g = 0,! = 3, q = + 1. Для Ь -елементом (27-0) g = 3, = 1, q = 0.
Метод виділення відрізків цифрових прямих у контурі використовує наступне властивість послідовності Ь-елементів, що утворюють відрізок. Така послідовність включає Ь -елементи з однаковими значеннями g, q; їх довжини приймають значення !, +1. причому
чергування Ь-елементів довжин !, +1 визначається ланцюгової дробом, одержуваної при розподілі цілих чисел п = Ах = | х1 - х2 | і т = Ау = | у1 - у2 \, де (х1зу1), (х2, у2) - координати початкової
і кінцевої точок відрізка: або
Покладемо для визначеності, що п> т. Як випливає з формули (1), l - ціла частина від ділення п на т - відповідає в відрізку цифровий прямий кількості з l поспіль креків одного напрямку. Разом з прилеглим перпендикулярним креком вони утворюють Ь -Елемент довжини !. к1 поспіль Ь-елементів довжини l і один Ь -Елемент довжини! +1 (або к1 поспіль Ь-елементів довжини +1 і один Ь -Елемент довжини!) утворюють К1 -Елемент "довжини" к1 (за аналогією з "довжиною "Ь-елементів). Ь -Елемент, що відрізняється по довжині на 1 від поспіль Ь-елементів, будемо називати зміненим Ь -елементом даного К1 -елементом. Аналогічно, к2 поспіль К1 -елементів "довжини" к1 і один К1-елемент "довжини" к1 +1 (або к2 поспіль К1 -елементів "довжини" к1 +1 і один К1 -Елемент "довжини" к1) утворюють К2 елемент "довжини" к1. І так
до + до 2 + к з + ... + кг
далі до вичерпання членів ланцюгового дробу. К1 -Елемент (взагалі К1 -Елемент), що відрізняється по довжині на 1 від поспіль К1 -елементів (Кг-1 -Елемент), будемо називати зміненим К1 -елементом (Кг-1 -елементом) даного К2 -елементом (Кг -елементом). Таким чином, кожному
цифровому відрізку прямої відповідає ланцюговий дріб, елементи якої визначають структуру цього відрізка.
У контурі на рис. 1 можуть бути виділені наступні відрізки цифрових прямих: 0-3, 3-9, 910, 10-17, 17-0.
3. Виділення відрізків цифровий прямий в контурі
При обробці контурів зображень, зокрема, бінарних зображень, в послідовності креків, що утворює контур, необхідно виділити частини послідовності, що утворюють відрізки прямих. Це завдання можна розглядати як задачу визначення елементів ланцюгового дробу по послідовності Ь-елементів контуру. Дане завдання є зворотною по відношенню до задачі визначення структури відрізка прямої по послідовності членів ланцюгового дробу, одержуваної як відношення різниць координат початку і кінця відрізка.
Метод виділення відрізків цифровий прямий складається в послідовному виконанні наступних дій.
1. Виділення послідовності Ь-елементів в послідовності креків. Ця дія відповідає визначенню цілої частини! ланцюгового дробу (1).
2. Виділення послідовності Кг-елементів при г = 1 в послідовності Ь-елементів, причому один з Ь-елементів кожного К1 -елементом повинен містити на 1 крек більше або менше за інших. Ця дія відповідає визначенню к1 -го елемента ланцюгового дробу (1). Після його виконання значення г повинно бути збільшено на 1.
3. Виділення послідовності Кг-елементів в послідовності Кг-1-елементів,
причому один з Кг-1-елементів кожного Кг -елементом повинен містити на один К-2 -Елемент більше або менше за інших. Ця дія відповідає визначенню до (-го елемента ланцюгового дробу (1). Після його виконання значення г повинно бути збільшено на 1.
4. Пункт 3 повторюється до тих пір, поки з йдуть підряд Кг -елементів ще можливо
утворити км -Елемент.
5. Визначають граничні точки між двома сусідніми Ь -елементом, які не входять в один і той же Кг -Елемент. Ці точки є кінцевими точками відрізків цифрових прямих, що утворюють контур.
Розглянемо алгоритм виділення відрізків прямих в послідовності Ь-елементів
Нехай [Ь5 (/ 5, gs, qs)); 5 = 0.1, ..., £ - послідовність Ь-елементів, що утворюють контур; х5, у5- координати початку е-го Ь-елемента; [Ху, у у); у =; г = 0,1, ...,!; !< £ - множество
точок зламу контура. Точки зламу визначають кінцеві точки відрізків прямих, які утворюють контур. Знайти точки зламу - значить, визначити відрізки прямої, що утворюють контур.
Кожен розглянутий відрізок характеризується Кг -елементом, а також ланцюгової
дробом. У початковий момент розпізнавання відрізка прямої елементи відповідної ланцюгового дробу рівні 0. Відрізок можна вважати розпізнаним, якщо розпізнані параметри Кг -елементом, включаючи його порядок г і значення елементів відповідної ланцюгового дробу.
1. Початкові умови.
Задані послідовності [Ь5 (/ 5, gs, qs)) і (х5, У5).
Необхідно знайти координати точок зламу | х;., У,).
к0р: = 0, к1р: = 0, К2Р: = 0, ..., кр: = 0 - робочі значення елементів ланцюгового дробу.
Приймемо в якості початкової точки першого відрізка точку 5 = 0; і = 0; і = 0.
2. Приймають перший Ь -Елемент в послідовності початком першого відрізка прямої. Початкова його точка х5, у. Довжина / = / 0 є також значенням першого елемента ланцюгового дробу.
5: = 5 + 1; к1р: = к1р + 1.
3. Виконують перевірку для наступного Ь -елементом, утворюють вони разом з попередніми К0-елемент.
3.1. Якщо ((Д3 == д3-1) && (Д3 == 73-1) && (4 == / 3-1)), то продовження Кг -елементом к0р: = к0р +1; 5: = 5 + 1; і продовження відрізка прямої. Перехід до п.3.
3.2. Якщо ((Д3 ф д3-1) || (Д3 ф 73-1) 11 (| / е - / є-1!> 1)), то кінець відрізка прямої. Перехід до п.5.
3.3. Якщо ((& == 9з + 1) && (% == 7з + 1) && ((/ з + 1 == / з + 1) 1! (/ З - 1 == / 3 + 1))), то завершення К0 -елементом; Ї = Ї + 1.
4. Перевірка продовження / завершення К (-елементом.
4.1. Якщо (до == 0), то до ^ = до ^; кр: = 0; до ^ 1р: = к1 + 1р + 1; 5: = 5 +1; початок км -елементом.
Перехід до п.3.
4.2. Якщо ((до ІФ 0) && (до == до ^)), то до ^ 1р: = до ^ 1р + 1; 5: = 5 + 1; продовження Кі + 1 -елементом. Перехід до п.3.
4.3. Якщо ((до (Ф 0) && ((до + 1 == к1р) 11 (К1-1 == до ^))), то Ї: = +1; кінець км -елементом.
Перехід до п.4.
4.4. Якщо ((^ ф0) && (| до - к1р |> 1)), то кінець відрізка прямий перехід до п.5.
5. Кінець відрізка.
X] = Хз; у = Уз; к1р: = 0, К2Р: = 0,., кір: = 0; до: = 0, к2: = 0,., до: = 0.
Якщо (s< S), то s:= s +1; переход к п. 2.
Інакше - кінець послідовності L-елементів. Кінець роботи алгоритму.
По суті, пропонований алгоритм знаходить елементи ланцюгового дробу і для кожного отриманого Kt -елементом і перевіряє, чи є ланцюговий дріб новозбудованого Kt -елементом підходящої до вже побудованої.
4. Програма виділення відрізків цифровий прямий
Як видно з опису алгоритму, в ньому міститься значна кількість умовних переходів, застосування яких суперечить рекомендаціям структурного програмування через труднощі, що виникають при налагодженні програм. Крім того, кількість параметрів Kt заздалегідь
визначити неможливо, оскільки змінна t заздалегідь не обмежена. Обмежити величину t
Значить заздалегідь обмежити розміри зображення. Програмна реалізація, особливо налагодження запропонованого алгоритму тривіальними засобами із зазначених причин істотно ускладнена. Зменшити труднощі розробки та налагодження програмної реалізації можна, якщо використовувати сучасні засоби об'єктно-орієнтованого програмування.
Запропонований алгоритм реалізований у вигляді програми LINESEGM, яка входить до складу лабораторного програмного комплексу по обробці зображень в середовищі Visual C ++.
В якості вихідної інформації програма LINESEGM використовує послідовності L-елементів, побудовані для кожного з контурів оброблюваного зображення.
Результатом роботи програми є побудована для кожного контуру зв'язкова послідовність відрізків цифрових прямих, представлена координатами кінцевих точок відрізків.
Як видно з алгоритму, операції побудови Kt-елементів з Kt-l-елементів
однакові для всіх значень t. Відзначимо, що початкове значення t = 0 і в процесі роботи алгоритму збільшується кожного разу на 1. Спеціальний клас CKForLn включає методи, відповідні операціям алгоритму. У процесі роботи програми, що реалізує алгоритм при кожному збільшенні t на 1, створюється новий об'єкт, що містить функції, які виконують операції алгоритму для кожного значення t.
З огляду на, що на нульовому рівні К0 -елементи утворюються не з До-елементів, а з L -
елементів, для реалізації алгоритму на нульовому рівні створена спеціальна модифікація класу CKForLn - клас Cmini.
Принцип роботи програми полягає в тому, що для кожного значення t в програмі реалізується об'єкт класу CKForLn t-того рівня, який містить функції, що визначають параметри Kt -елементом. Вихідними параметрами Kt -елементом є параметри вже
завершеного Kt-l-елементів, параметри якого були визначені об'єктом класу CKForLn t-1
Ого рівня.
Об'єкти класу CKForLn реалізуються в міру виникнення умов, а саме: необхідність побудови До -елементом чергового рівня, - і накопичуються в спеціальному динамічному масиві. Об'єкт нульового рівня створюється відразу ж на початку роботи програми.
Реалізація об'єктів в динамічному масиві в міру збільшення t дозволяє не накладати обмежень на розміри зображення. Обмеження на розмір зображення визначаються тільки ресурсами використовуваного комп'ютера.
При описі роботи програми буде використано поняття завершеного Kt -
елемента. Кожен завершений Kt -Елемент містить kt Kt-l-елементів та один змінений Kt-l -Елемент, який містить kt-l ± 1 Kt-2-елементів, на відміну від незавершеного Kt -елементом, який не містить незавершеного Kt -елементом.
Клас CKForLn включає наступні методи.
1. Метод DK (), (define K-element) - визначити До -Елемент.
Визначити Kt -Елемент - значить, визначити кількість Kt-1-елементів, що утворюють даний Kt -Елемент.
2. Метод VK§, (verify K-element) - перевірити ідентичність розглядається До -елементом з К-елементом того ж рівня, певним попередньо функцією методу DK ().
3. Метод DEO, (define the end of K-element) - визначити завершення До -елементом, тобто при визначенні Kt -елементом знайти його змінений Kt-1 -Елемент. Функція методу DE () рівня t-1 викликається функцією методу DK () рівня t.
4. Метод VE (), (verify the end of До -element) - перевірити ідентичність завершення даного До -елементом зміненим До -елементом, певним попередньо функцією методу DE ().
Клас Cmini включає такі ж методи, що відрізняються від методів класу CKForLn тим, що методи класу Cmini працюють з L-елементів та визначають або перевіряють К0 -елементи.
Методи класу Cmini
Методи класу Cmini використовують в якості вихідних даних послідовності L-елементів, побудовані для кожного з контурів оброблюваного зображення, починаючи з поточного номера L-елементів в момент виклику функції методу.
Функція методу DK () класу Cmini порівнює параметри кожного наступного L-елементів з параметрами початкового L-елементів до тих пір, поки вони збігаються. Що стосується розбіжності параметрів функція DK () перевіряє, завершено чи К0 -Елемент і закінчує
роботу. Завершеним вважається К0 -Елемент, що закінчується зміненим L -елементом, таким, довжина якого відрізняється від інших L-елементів К0 -елементом на 1 (операція 3.1 для початку відрізка - t = 0).
Функція методу VK () перевіряє, чи збігаються параметри наступних k0 L-елементів з параметрами L-елементів К0 -елементом, попередньо визначеного функцією методу DK ()
того ж рівня. У разі збігу параметрів поточного К0 -елементом з попередньо
певним функція VK () формує ознака продовження відрізка і завершує роботу (операція 3.1 для продовження відрізка - t> 0).
В іншому випадку функція VK () формує ознака завершення відрізка і завершує
Функція методу DE () порівнює параметри поточного Kci-елемента з параметрами К0 -елементом, попередньо визначеного функцією DK (), щоб визначити, чи є поточний К0 -Елемент зміненим. У разі рівного розподілу інших параметрів кількість L-елементів до0
зміненого К0 -елементом порівняно з К0 -елементом, попередньо визначеним
функцією DK (), має відрізнятися на 1 (операція 3.2, 3.3 для визначення завершення
початкового К0 -елементом відрізка - t = 0). Результат - параметри зміненого К0 -елементом
використовуються в методі VE () класу Cmini.
Функція методу VE () порівнює параметри поточного К0 -елементом з параметрами попередньо визначеного функцією DE () зміненого К0 -елементом, щоб визначити,
чи збігаються вони (операція 3.2, 3.3 для продовження відрізка - t> 0). Результат - ознака збігу або розбіжності - використовується в методі VК () класу CKForLn.
Методи класу CKForLn
Методи використовують в якості вихідних даних параметри К-елементів, побудовані для нижчого рівня. Тобто, для визначення параметрів Kt -елементом використовуються параметри
вже побудованих Kt-l-елементів.
Функція методу DK () рівня t класу CKForLn при визначенні параметрів ^ -елементом викликає функцію VK () рівня t-1 класу CKForLn, яка перевіряє, чи слід за вже визначеним Kt-l -елементом Kt-l -Елемент з такими ж параметрами. Якщо так, виклик функції VK () повторюється. При цьому відбувається підрахунок кількості повторень, тобто визначається параметр kt.
В іншому випадку функція DK () рівня t викликає функцію DE () рівня t-1 для визначення зміненого Kt-l-елементів та закінчує роботу. Після закінчення роботи функція DK () рівня t класу CKForLn визначає параметри і формує ознаки завершеного або незавершеного Kt -елементом (операція 4.1, 4.2 при поточному максимальному значенні t).
Функція методу VK () рівня t класу CKForLn перевіряє, чи збігаються параметри наступних kt Kt-елементів з параметрами Kt -елементом, попередньо визначеного
функцією методу DK () того ж рівня. У разі збігу параметрів поточного Kt -елементом з
попередньо визначеним функцією DK () Kt -елементом того ж рівня, функція VK ()
формує ознака продовження відрізка і завершує роботу.
В іншому випадку функція VK () формує ознака завершення відрізка і завершує роботу (операція 4.1,4.2 при поточному значенні t, меншому максимального).
Kt -елементФункція методу DE0уровня t класу CKForLn при визначенні параметрів Kt -елементом порівнює параметри поточного Kt -елементом з параметрами Kt -елементом, попередньо визначеного функцією DK (), щоб визначити, чи є поточний Kt -Елемент зміненим. У разі рівного розподілу інших параметрів їх значення kt-1 повинні відрізнятися на 1. У разі виконання цієї умови функція DE () формує ознака зміненого Kt -елементом і
завершує роботу (операція 4.3, 4.4 при поточному максимальному значенні t).
Функція методу VE () рівня t класу CKForLn порівнює параметри поточного Kt -елементом з параметрами попередньо виділеного функцією DE () зміненого Kt -елементом, щоб визначити, чи збігаються значення їх параметрів.
У разі збігу значень параметрів поточного Kt -елементом з попередньо
певним функцією DK () того ж рівня, функція VK () формує ознака збігу значень параметрів і завершує роботу (операція 4.3,4.4 при поточному значенні t, меншому максимального).
Тимчасова діаграма (рис. 2) ілюструє роботу програми LINESEGM на прикладі розпізнавання відрізка прямої. У нижній частині малюнка зображена частина цифрової лінії, що складається з L-елементів одних і тих же основного і допоміжного напрямків і різних довжин.
На кроці 0 створений об'єкт класу Стіпі, який визначає параметри К0 -елементом.
На кроці 10 завершено визначення параметрів К0-елемента і створюється об'єкт 1 класу СКРогЬп, який використовує функції раніше створеного об'єкта для визначення параметрів К1-елемента. На кроці 19 завершено визначення параметрів К1 -елементом і створюється об'єкт 2 класу СКРогЬп, який використовує функції раніше створених об'єктів для визначення параметрів К2 -елементом. На кроці 49 завершено визначення параметрів К2 -елементом і створюється об'єкт 3 класу СКРогЬп, який використовує функції раніше створених об'єктів для визначення параметрів К3-елемента. На кроці 79 виконується
умова завершення відрізка. Детально робота програми описана в додатку.
На ділянці 0-6 два Ь -елементом утворюють незавершений К0 -Елемент. Очевидно, що Ь -
елемент 3-6 довжини 3 завершує відрізок прямої, так як Ь -Елемент 6-7 довжини 1 не може бути його продовженням. Таким чином, Ь -Елемент 6-7 є початком відрізка цифрової прямої.
На рис. 3 представлений приклад роботи програми. Контур бінарного зображення фігурної стрілки розділений квадратиками на відрізки прямих. Результат роботи програми -послідовність відрізків прямих - був використаний для виділення дуг цифрових кривих. Великі квадратики показують межі дуг цифрових кривих.
Робота програми перевірена на значній кількості (понад 2000) прикладів і використовується при дослідженні структурного аналізу напівтонових зображень.
5. Робота програми розпізнавання відрізків прямих
Розглянемо роботу програми іИЕБЕСМ на прикладі рис. 4. У нижній частині малюнка зображена частина цифрової лінії, що складається з Ь-елементів одних і тих же основного і допоміжного напрямків і різних довжин. На ділянці 0-6 два Ь -елементом утворюють незавершений К0-
Мал. 3. Приклад роботи програми структурного аналізу контуру - сегментація контуру відрізками цифрових прямих
елемент. Очевидно, що Ь -Елемент 3-6 довжини 3 завершує відрізок прямої, так як Ь -Елемент 6-7 довжини 1 не може бути його продовженням. Таким чином, Ь -Елемент 6-7 є початком відрізка цифрової прямої.
Роботу програми по визначенню чергового відрізка прямої починає функція ОК () нульового рівня, яка визначає завершений К0 -Елемент 6-10, що складається з Ь-елементів
довжин 1,1,2; до0 = 2. Цей К0 -Елемент є початковим для К1-елемента. Програма утворює об'єкт першого рівня і передає управління функції ОК () цього об'єкта. Функція ОК () рівня 1 викликає функцію VKQ рівня 0. Функція VKQ порівнює параметри Ь-елементів К0-елемента 6-10 з наступними Ь-елементами і підтверджує наявність К0 -елементом 10-14,
ідентичного К0 -елементом 6-10. Продовжуючи роботу, функція VKQ виявляє, що такі Ь -елементи не утворюють такого ж К0 -елементом, завершує роботу і передає управління функції ОК () рівня 1. Функція ОК () рівня 1 викликає функцію ОЕ () рівня 0. Ця остання, починаючи з Ь -елементом 6-7, визначає наявність зміненого К0 -елементом 14-19, що складається з Ь-елементів довжин 1,1,1,2; до0 = 3, завершує роботу і передає управління функції ОК () рівня 1. Ця функція визначає наявність завершеного К1-елемента 6-19, що складається з двох К0 -
елементів 1,1,2, (к1 = 2) і одного зміненого 1,1,1,2 (К0 = 3). Програма утворює об'єкт другого рівня і передає управління функції ОК () цього об'єкта. Функція ОК () рівня 2 викликає функцію VKQ рівня 1, яка, в свою чергу, викликає функцію VKQ рівня 0. Функція VKQ порівнює параметри Ь-елементів К0 -елементом 6-10 з наступними Ь -
елементами і підтверджує наявність К0 -елементів 19-23, 23-27, ідентичних К0-елементу 6-10, тобто стільки ж, скільки таких К0-елементів міститься в К1-елементі 6-19. Далі функція VKQ рівня 0 повертає управління з ознакою продовження відрізка функції VKQ рівня 1. Функція VKQ викликає функцію VE0 рівня 0, яка визначає наявність зміненого К0 -
елемента 27-32, ідентичного К0 -елементом 14-19. Таким чином, визначено К1-елемент 19-32,
ідентичний К1-елементу 6-19. Далі функція VKQ рівня 1 не визначає черговий К1-елемент, ідентичний К1-елементу 6-19, через те, що функція VE0 рівня 0 не визначає змінений К1-елемент, ідентичний К1-елементу 6-19, починаючи з Ь -елементом 40-41, і повертає управління функції ОК () рівня 2. Функція ОК () рівня 2 викликає функцію ОЕ () рівня 1, яка визначає наявність зміненого К1-елемента 32-49, що складається з К0 -елементів 32-36, 36- 40,
40-44, 44-49. Далі визначається К2-елемент 6-49, утворюється об'єкт рівня 3, визначається змінений К2-елемент 49-79. Ці два К2-елемента утворюють К3-елемент 6-79. Цим побудова відрізка завершується, оскільки такі Ь -елементи 79-81 і 81-83 не утворюють К0 -Елемент,
ідентичний К0 -елементом 6-10, і функція VKQ рівня 0 не формує ознака продовження
відрізка. У послідовності Ь-елементів виділено відрізок цифровий прямий 6-79. Програма починає визначення наступного відрізка, починаючи з Ь -елементом 80-82.
б. висновки
1. Запропоновано новий алгоритм виділення відрізків прямої в контурах зображень і нетривіальна програмна реалізація алгоритму, які дозволяють отримати точне рішення задачі розпізнавання контурів зображень як послідовностей відрізків прямих.
2. Програмна реалізація алгоритму виділення відрізків прямої в контурах зображень виконана із застосуванням сучасних засобів об'єктно-орієнтованого програмування, що дозволило не накладати явних обмежень на розміри оброблюваного зображення при максимальному використанні ресурсів застосовуваного комп'ютера.
3. На основі запропонованого алгоритму і його програмної реалізації отримано теоретичне рішення і проведені експерименти з розпізнавання дуг цифрових кривих і сегментації контуру бінарних зображень на відрізку цифрових прямих і дуги цифрових кривих.
СПИСОК ЛІТЕРАТУРИ
1. Kovalevsky V.A. Applications of Digital Straight Segments to Economical Image Encoding, In Proceedings of the 7th International Workshop, DGCI "97, Montpellier. - France, 1997. - December 3-5. - P. 51-62.
2. Калмиков В.Г. Структурний метод опису та розпізнавання відрізків цифрових прямих у контурах бінарних зображень // Штучний інтелект. - 2002. - № 4. - C. 450-457.
3. Калмиков В.Г., Вишневський В.В. Аналіз контурів об'єктів в бінарних зображеннях // Інститут проблем математичних машин і систем. - 1997. - № 2. - С. 68 - 71.
4. Калмиков В.Г. Дуга цифрової крівої - визначення и! Застосування // Оброблення сігналів и збережений та розпізнавання образів. Праці сьомої ВСЕУКРАЇНСЬКОЇ міжнародної конференции. - Київ. - 2004. - 11 - 15 жовтень.
Постановка задачівизначається метою і можливостями її реалізації.
Мета.Розробити програму класифікації деталей прямокутної форми на якісні і браковані.
Можливості для реалізації завданнявизначаються можливостями комп'ютера. Комп'ютер здатний обробляти числову інформацію в алгоритмічної послідовності. Щоб реалізувати можливості комп'ютера необхідно змоделювати решаемую завдання.
Моделювання із застосуванням комп'ютера має на увазі перехід від реального об'єкта (світу) до кодованому опису його властивостей за допомогою даних і операцій над ними. Такий перехід, як правило, виконується в кілька етапів:
абстракція- вибір найбільш істотних ознак об'єкта з точки зору поставленої задачі.
Необхідно провести дослідження, які дозволяють від об'єкта моделювання перейти до суб'єкта моделювання відкинувши все зайве відповідно до мети в поставленому завданню
Чим відрізняється прямокутник від інших чотирикутників?
- Рівність протилежних сторін.
- Паралельність протилежних сторін.
- Рівність діагоналей.
- Всі кути прямі.
Який мінімум ознак потрібен для однозначного вирішення завдання?
- Рівність 2-х протилежних сторін + рівність діагоналей.
- Паралельність 2-х протилежних сторін + рівність діагоналей.
- Три кута прямі.
Отже, завдяки абстракції ми отримали словесну інформаційну модель. Але, вона ще поки незрозуміла для комп'ютера. Він розуміє математичну модель, яка представлена у вигляді алгоритму і реалізовану програмно.
Методика реалізації завдання.
Креслення якісної деталі (прямокутника) або бракованої деталі (чотирикутника) виконується з відрізків (команда LINE) в графічній системі AutoCAD і експортується в. Програма kntrs.lsp () зчитує з DXF-файлу дані про відрізки (координати вершин) і записує їх в текстовий файл vrtks.txt в круговому порядку обходу вершин.
Текстовий файл vrtks.txt можна створити вручну, знімаючи координати вершин безпосередньо з креслення.
Розроблена програма rct.lsp повинна зчитувати дані з файлу vrtks.txt, аналізувати їх і виводити в файл result.txt запис про відповідність деталі вимогам (прямокутник чи ні).
формалізація ознак
Рівність довжин відрізків (сторін або діагоналей): Довжина кожного відрізка визначається як гіпотенуза прямокутного прямокутника (по теоремі Піфагора) через різницю координат відрізків:
(Setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
Паралельність прямих: K2 = K1, де До- кутовий коефіцієнт прямої К = (Y2-Y1) / (X2-X1)
Як формалізувати поняття «Прямий кут»? В рамках поставленої задачі наявність «Прямого кута» можна визначити за ознакою перпендикулярності відрізків: K2 = -1 / K1, де До- кутовий коефіцієнт прямої. К = (Y-Y0) / (X-X0).
Відображення моделі в комп'ютері
Будь-яка інформація в кінцевому підсумку відображається в комп'ютері за допомогою двійкових чисел (кодів) у Внутримашинное модель. Раніше кодування здійснювалося програмістом. Зараз основна частина програм створюється на алгоритмічних мовах.
Давно хотів написати спільну статтю, яка містить в собі самі основи Image Recognition, якийсь гайд по базовим методам, що розповідає, коли їх застосовувати, які завдання вони вирішують, що можливо зробити ввечері на коліні, а про що краще й не думати, не маючи команди людина в 20.
Якісь статті по Optical Recognition я пишу давненько, так що пару раз на місяць мені пишуть різні люди з питаннями по цій тематиці. Іноді створюється відчуття, що живеш з ними в різних світах. З одного боку розумієш, що людина швидше за все професіонал в суміжній темі, але в методах оптичного розпізнавання знає дуже мало. І найприкріше, що він намагається застосувати метод з блізрасположенних області знань, який логічний, але в Image Recognition повністю не працює, але не розуміє цього і сильно ображається, якщо йому почати розповідати що-небудь з самих основ. А враховуючи, що розповідати з основ - багато часу, якого часто немає, стає все ще сумніше.
Ця стаття задумана для того, щоб людина, яка ніколи не займалася методами розпізнавання зображень, зміг протягом 10-15 хвилин створити у себе в голові якусь базову картину світу, відповідну тематиці, і зрозуміти в який бік йому копати. Багато методів, які тут описані, застосовні до радіолокації і аудіо-обробці.
Почну з пари принципів, які ми завжди починаємо розповідати потенційному замовнику, або людині, яка хоче почати займатися Optical Recognition:
- При вирішенні задачі завжди йти від найпростішого. Набагато простіше повісити на персону мітку оранжевого кольору, ніж стежити за людиною, виділяючи його каскадами. Набагато простіше взяти камеру з великою роздільною здатністю, ніж розробляти сверхразрешающій алгоритм.
- Сувора постановка задачі в методах оптичного розпізнавання на порядки важливіше, ніж в задачах системного програмування: одне зайве слово в ТЗ може додати 50% роботи.
- У завданнях розпізнавання немає універсальних рішень. Не можна зробити алгоритм, який буде просто «розпізнавати будь-який напис». Табличка на вулиці і лист тексту - це принципово різні об'єкти. Напевно, можна зробити загальний алгоритм (ось хороший приклад від гугла), але це вимагатиме великих складнощів великої команди і складатися з десятків різних підпрограм.
- OpenCV - це біблія, в якій є безліч методів, і за допомогою якої можна вирішити 50% від обсягу майже будь-якого завдання, але OpenCV - це лише мала частина того, що в реальності можна зробити. В одному дослідженні у висновках було написано: «Завдання не вирішується методами OpenCV, отже, вона нерозв'язна». Намагайтеся уникати такого, не лінуватися і тверезо оцінювати поточну задачу кожен раз з нуля, без використання OpenCV-шаблони.
Список наведених тут методів не повний. Пропоную в коментарях додавати критичні методи, які я не написав і приписувати кожному по 2-3 супровідних слова.
Частина 1. Фільтрація
У цю групу я помістив методи, які дозволяють виділити на зображеннях цікавлять області, без їх аналізу. Велика частина цих методів застосовує якесь єдине перетворення на всі точки зображення. На рівні фільтрації аналіз зображення не проводиться, але точки, які проходять фільтрацію, можна розглядати як області з особливими характеристиками.Бінаризація по порогу, вибір області гістограми
Саме просто перетворення - це бінаризація зображення по порогу. Для RGB зображення і зображення в градаціях сірого порогом є значення кольору. Зустрічаються ідеальні завдання, в яких такого перетворення досить. Припустимо, потрібно автоматично виділити предмети на білому аркуші паперу:
Вибір порога, за яким відбувається бінаризація, багато в чому визначає процес самої бинаризации. В даному випадку, зображення було бінаризованими за середнім кольором. Зазвичай бінаризація здійснюється за допомогою алгоритму, який адаптивно вибирає поріг. Таким алгоритмом може бути вибір матожіданія або моди. А можна вибрати найбільший пік гістограми.
Бінаризація може дати дуже цікаві результати при роботі з гістограмами, в тому числі в ситуації, якщо ми розглядаємо зображення не в RGB, а в HSV. Наприклад, сегментувати цікавлять кольори. На цьому принципі можна побудувати як детектор мітки так і детектор шкіри людини.
Класична фільтрація: Фур'є, ФНЧ, ФВЧ
Класичні методи фільтрації з радіолокації і обробки сигналів можна з успіхом застосовувати в безлічі завдань Pattern Recognition. Традиційним методом в радіолокації, який майже не використовується в зображеннях в чистому вигляді, є перетворення Фур'є (конкретніше - БПФ). Одне з небагатьох виняток, при яких використовується одновимірний перетворення Фур'є, - компресія зображень. Для аналізу зображень одновимірного перетворення зазвичай не вистачає, потрібно використовувати куди більш ресурсоємних двовимірне перетворення.
Мало хто його насправді розраховує, зазвичай, куди швидше і простіше використовувати згортку, що цікавить з уже готовим фільтром, заточеним на високі (ФВЧ) або низькі (ФНЧ) частоти. Такий метод, звичайно, не дозволяє зробити аналіз спектра, але в конкретному завданні видеонаблюдения зазвичай потрібен не аналіз, а результат.
Найпростіші приклади фільтрів, що реалізують підкреслення низьких частот (фільтр Гаусса) і високих частот (Фільтр Габора).
Для кожної точки зображення вибирається вікно і перемножується з фільтром того ж розміру. Результатом такої згортки є нове значення точки. При реалізації ФНЧ і ФВЧ виходять зображення такого типу:
вейвлети
Але що якщо використовувати для згортки з сигналом якусь довільну характеристическую функцію? Тоді це буде називатися "Вейвлет-перетворення". Це визначення вейвлетов не є коректним, але традиційно склалося, що в багатьох командах вейвлет-аналізом називається пошук довільного патерну на зображенні за допомогою згортки з моделлю цього патерну. Існує набір класичних функцій, використовуваних в вейвлет-аналізі. До них відносяться вейвлет Хаара, вейвлет Морлі, вейвлет мексиканський капелюх, і.т.д. Примітиви Хаара, про які було кілька моїх минулих статей (,), відносяться до таких функцій для двовимірного простору.
Вище наведено 4 приклади класичних вейвлетов. 3х-мірний вейвлет Хаара, 2х-мірні вейвлет Мейєра, вейвлет Мексиканська Капелюх, вейвлет Добеши. Хорошим прикладом використання розширеної трактування вейвлетов є завдання пошуку відблиску в оці, для якої вейвлетом є сам відблиск:
Класичні вейвлети зазвичай використовуються для стиснення зображень, або для їх класифікації (буде описано нижче).
кореляція
Після такої вільного трактування вейвлетов з мого боку варто згадати власне кореляцію, що лежить в їх основі. При фільтрації зображень це незамінний інструмент. Класичне застосування - кореляція відеопотоку для знаходження зрушень або оптичних потоків. Найпростіший детектор зсуву - теж в якомусь сенсі різницевий коррелятор. Там де зображення не корелюють - був рух.
фільтрації функцій
Цікавим класом фільтрів є фільтрація функцій. Це чисто математичні фільтри, які дозволяють виявити просту математичну функцію на зображенні (пряму, параболу, коло). Будується акумулює зображення, в якому для кожної точки вихідного зображення промальовується безліч функцій, її породжують. Найбільш класичним перетворенням є перетворення Хафа для прямих. У цьому перетворенні для кожної точки (x; y) отрісовивается безліч точок (a; b) прямий y = ax + b, для яких вірно рівність. Виходять красиві картинки:
(Перший плюсег того, хто перший знайде підступ в зображенні і такому визначенні і пояснить його, другий плюсег того, хто перший скаже що тут зображено)
Перетворення Хафа дозволяє знаходити будь-які параметрізуемих функції. Наприклад окружності. Є модифіковане перетворення, яке дозволяє шукати будь-які фігури. Це перетворення страшенно люблять математики. Але ось при обробці зображень, воно, на жаль, працює далеко не завжди. Дуже повільна швидкість роботи, дуже висока чутливість до якості бинаризации. Навіть в ідеальних ситуаціях я вважав за краще обходитися іншими методами.
Аналогом перетворення Хафа для прямих є перетворення Радону. Воно обчислюється через БПФ, що дає виграш продуктивності в ситуації, коли точок дуже багато. До того ж його можна використовувати до НЕ бінаризованими зображенню.
фільтрації контурів
Окремий клас фільтрів - фільтрація кордонів і контурів. Контури дуже корисні, коли ми хочемо перейти від роботи з зображенням до роботи з об'єктами на цьому зображенні. Коли об'єкт досить складний, але добре виділяється, то часто єдиним способом роботи з ним є виділення його контурів. Існує цілий ряд алгоритмів, які вирішують задачу фільтрації контурів:Найчастіше використовується саме Кенні, який добре працює і реалізація якого є в OpenCV (Собель там теж є, але він гірше іщёт контури).
Інші фільтри
Зверху наведені фільтри, модифікації яких допомагають вирішити 80-90% завдань. Але крім них є більш рідкісні фільтри, які використовуються в локальних завданнях. Таких фільтрів десятки, я не буду приводити їх все. Цікавими є ітераційні фільтри (наприклад активна модель зовнішнього вигляду), а так само ріджлет і курвлет перетворення, є сплавом класичної вейвлет фільтрації і аналізом в поле радон-перетворення. Бімлет-перетворення красиво працює на кордоні вейвлет перетворення і логічного аналізу, дозволяючи виділити контури:
Але ці перетворення дуже специфічні і заточені під рідкісні завдання.
Частина 2. Логічна обробка результатів фільтрації
Фільтрація дає набір придатних для обробки даних. Але найчастіше можна просто взяти і використовувати ці дані без їх обробки. У цьому розділі буде кілька класичних методів, що дозволяють перейти від зображення до властивостей об'єктів, або до самих об'єктів.Морфологія
Переходом від фільтрації до логіки, на мій погляд, є методи математичної морфології (,,). По суті, це найпростіші операції нарощування і ерозії бінарних зображень. Ці методи дозволяють прибрати шуми з бінарного зображення, збільшивши або зменшивши наявні елементи. На базі математичної морфології існують алгоритми оконтуривания, але зазвичай користуються якимись гібридними алгоритмами або алгоритмами в зв'язці.
контурний аналіз
У розділі по фільтрації вже згадувалися алгоритми отримання кордонів. Отримані кордону досить просто перетворюються в контури. Для алгоритму Кенні це відбувається автоматично, для інших алгоритмів потрібна додаткова бінаризація. Отримати контур для бінарного алгоритму можна наприклад алгоритмом жука.Контур є унікальною характеристикою об'єкта. Часто це дозволяє ідентифікувати об'єкт по контуру. Існує потужний математичний апарат, що дозволяє це зробити. Апарат називається контурним аналізом (,).
Якщо чесно, то у мене жодного разу ні вийшло застосувати контурний аналіз в реальних задачах. Аж надто ідеальні умови потрібні. Те кордон не знайдеться, то шумів занадто багато. Але, якщо потрібно щось розпізнавати в ідеальних умовах - то контурний аналіз чудовий варіант. Дуже швидко працює, гарна математика і зрозуміла логіка.
особливі точки
Особливі точки це унікальні характеристики об'єкта, які дозволяють зіставляти об'єкт сам з собою або зі схожими класами об'єктів. Існує кілька десятків способів дозволяють виділити такі точки. Деякі способи виділяють особливі точки в сусідніх кадрах, деякі через великий проміжок часу і при зміні освітлення, деякі дозволяють знайти особливі точки, які залишаються такими навіть при поворотах об'єкта. Почнемо з методів, що дозволяють знайти особливі точки, що не такі стабільні, зате швидко розраховуються, а потім підемо по зростанню складності:Перший клас. Особливі точки, які є стабільними протягом секунд.Такі точки служать для того, щоб вести об'єкт між сусідніми кадрами відео, або для відомості зображення з сусідніх камер. До таких точок можна віднести локальні максимуми зображення, кути на зображенні (кращий з детекторів, мабуть, детектор Харіса), точки в яких досягається максимуми дисперсії, певні градієнти і.т.д.
Другий клас. Особливі точки, які є стабільними при зміні освітлення і невеликих рухах об'єкта.Такі точки служать в першу чергу для навчання і подальшої класифікації типів об'єктів. Наприклад, класифікатор пішохода або класифікатор особи - це продукт системи, побудованої саме на таких точках. Деякі з раніше згаданих вейвлетов можуть є базою для таких точок. Наприклад, примітиви Хаара, пошук відблисків, пошук інших специфічних функцій. До таких точок відносяться точки, знайдені методом гістограм спрямованих градієнтів (HOG).
Третій клас. Стабільні точки.Мені відомо лише про два методи, які дають повну стабільність і про їх модифікації. Це SURF і SIFT. Вони дозволяють знаходити особливі точки навіть при повороті зображення. Розрахунок таких точок здійснюється довше в порівнянні з іншими методами, але досить обмежений час. На жаль ці методи запатентовані. Хоча, в Росії патентувати алгоритми низя, так що для внутрішнього ринку користуйтеся.
Частина 3. Навчання
ретья частина розповіді буде присвячена методам, які не працюють безпосередньо з зображенням, але які дозволяють приймати рішення. В основному це різні методи машинного навчання і прийняття рішень. Нещодавно Яндикс виклав на Хабре курс з цієї тематики, там дуже хороша підбірка. Ось воно є в текстовій версії. Для серйозного заняття тематикою настійно рекомендую подивитися саме їх. Тут я спробую окреслити кілька основних методів використовуваних саме в розпізнаванні образів.У 80% ситуацій суть навчання в задачі розпізнавання в наступному:
Є тестова вибірка, на якій є кілька класів об'єктів. Нехай це буде наявність / відсутність людини на фотографії. Для кожного зображення є набір ознак, які були виділені яким-небудь ознакою, будь то Хара, HOG, SURF або який-небудь вейвлет. Алгоритм навчання повинен побудувати таку модель, за якою він зможе проаналізувати нове зображення і прийняти рішення, який з об'єктів є на зображенні.
Як це робиться? Кожне з тестових зображень - це точка в просторі ознак. Її координати це вага кожного з ознак на зображенні. Нехай нашими ознаками будуть: «Наявність очей», «Наявність носа», «Наявність двох рук», «Наявність вух», і.т.д ... Всі ці ознаки ми виділимо існуючими у нас детекторами, які навчені на частини тіла, схожі на людські. Для людини в такому просторі буде коректною точка. Для мавпи точка для коня. Класифікатор навчається за вибіркою прикладів. Але не на всіх фотографіях виділилися руки, на інших немає очей, а на третій у мавпи через помилку класифікатора з'явився людський ніс. Той, якого навчають класифікатор людини автоматично розбиває простір ознак таким чином, щоб сказати: якщо перша ознака лежить в діапазоні 0.5
Існує дуже багато класифікаторів. Кожен з них краще працює в якійсь своїй завданню. Завдання підбору класифікатора до конкретного завдання це багато в чому мистецтво. Ось трошки красивих картинок на тему.
Простий випадок, одномірне поділ
Розберемо на прикладі найпростіший випадок класифікації, коли простір ознаки одномірне, а нам потрібно розділити 2 класу. Ситуація зустрічається частіше, ніж може представитися: наприклад, коли потрібно відрізнити два сигнали, або порівняти патерн зі зразком. Нехай у нас є навчальна вибірка. При цьому виходить зображення, де по осі X буде міра схожості, а по осі Y-кількість подій з таким заходом. Коли шуканий об'єкт схожий на себе - виходить ліва гауссіана. Коли не схожий - права. Значення X = 0.4 розділяє вибірки так, що помилкове рішення мінімізує ймовірність прийняття будь-якого неправильного рішення. Саме пошуком такого роздільника і є завдання класифікації.
Маленька ремарка. Далеко не завжди оптимальним буде той критерій, який мінімізує помилку. Наступний графік - це графік реальної системи розпізнавання по райдужній оболонці. Для такої системи критерій вибирається такий, щоб мінімізувати ймовірність помилкового пропуску сторонньої людини на об'єкт. Така ймовірність називається «помилка першого роду», «ймовірність помилкової тривоги», «помилкове спрацьовування». В англомовній літературі «False Access Rate».
) АдаБуста - один з найпоширеніших класифікаторів. Наприклад каскад Хаара побудований саме на ньому. Зазвичай використовують коли потрібна бінарна класифікація, але нічого не заважає навчити на більшу кількість класів.
SVM (,,,) Один з найпотужніших класифікаторів, що має безліч реалізацій. В принципі, на завданнях навчання, з якими я стикався, він працював аналогічно адабусте. Вважається досить швидким, але його навчання складніше, ніж у Адабусти і потрібно вибір правильного ядра.
Ще є нейронні мережі і регресія. Але щоб коротко їх класифікувати і показати, чим вони відрізняються, потрібна стаття куди більше, ніж ця.
________________________________________________
Сподіваюся, у мене вийшло зробити побіжний огляд використовуваних методів без занурення в математику і опис. Може, комусь це допоможе. Хоча, звичайно, стаття неповна і немає ні слова ні про роботу зі стереозображення, ні про МНК з фільтром Калмана, ні про адаптивне Байесови підході.
Якщо стаття сподобається, то спробую зробити другу частину з підбіркою прикладів того, як вирішуються існуючі завдання ImageRecognition.
І на останок
Що почитати?1) Колись мені дуже сподобалася книга «Цифрова обробка зображень» Б. Яні, яка написана просто і зрозуміло, але в той же час наведена майже вся математика. Хороша для того, щоб ознайомитися з існуючими методами.
2) Класикою жанру є Р Гонсалес, Р. Вудс "Цифрова обробка зображень". Чомусь вона мені далася складніше, ніж перша. Сильно менше математики, зате більше методів і картинок.
3) «Обробка та аналіз зображень в задачах машинного зору» - написана на базі курсу, читаного на одній з кафедр фізтеху. Дуже багато методів і їх докладного опису. Але на мій погляд в книзі є два великих мінуса: книга сильно орієнтована на пакет софта, який до неї додається, в книзі занадто часто опис простого методу перетворюється в математичні нетрі, з яких складно винести структурну схему методу. Зате автори зробили зручний сайт, де представлено майже весь зміст - wiki.technicalvision.ru
4) Чомусь мені здається, що хороша книжка, яка структурує і пов'язує картину світу, що виникає при занятті Image Recognition і Machine Learning - це «Про інтелекті» Джеффа Хокінса. Прямих методів там немає, але є багато думок на подумати, звідки прямі методи обробки зображень відбуваються. Коли вчитуватися, розумієш, що методи роботи людського мозку ти вже бачив, але в задачах обробки відео.
Коли ми дивимося на двовимірне зображення будь-якої тривимірної сцени (на картині, фотографії, екрані монітора), нам здається, що там безпосередньо присутні всі ті предмети, які ми могли б побачити, якби на власні очі спостерігали ту ж сцену в життя. Тим часом, все, що нам насправді дано в двовимірному зображенні, це видиме поле, Що представляє собою лише деяку функцію розподілу яскравостіабо кольоруна двовимірної площині: f(x, y) , де xі y- декартові координати, що описують площину зображення.
Більш того, якщо наблизитися впритул до екрану комп'ютерного монітора, можна побачити, що зображення на екрані насправді не гладке і безперервне, а являє собою дискретну «мозаїку», що складається з окремих кольорових прямокутників, розташованих у вигляді регулярної прямокутної матриці. Це і є цифрове зображення. З математичної точки зору цифрове зображенняявляє собою двовимірну матріцуIm розміру (DimXDimY), гдеx- ціле число від 0 доDimX- 1, яке описує номер елемента в рядку матриці, y- ціле число від 0 доDimY- 1, яке описує номер рядка матриці, в якій розташований даний елемент. При цьому сам елемент цифрового зображення (осередок прямокутної матриці) носить назву піксель(Pixel, pictureelement). У найпростішому випадку кожен піксельIm має скалярний цілочисельне значення, пропорційне значенню функції розподілу яскравості f(x, y) в даній точці площини.
На рис. 1.1.1 зліва показано зображення жіночого обличчя, представлене як зображення, а справа показаний збільшений фрагмент зображення того ж особи (праве око), де для кожного елемента зображення вказано відповідне числове значення пікселя. Світлим елементів зображення відповідають б прольшие значення матриці, темним - менші значення. Ніякої іншої інформації цифрове зображення не містить.
@Мал. 1.1.1 Цифрове зображення як двовимірна матриця інтенсивностей
Починаючи вивчати машинне зір, необхідно чітко уявляти собі, що в комп'ютері в якості цифрового зображення зберігається тільки і виключно двовимірний масив чисел того чи іншого формату. Будь-які інші дані, які ми хотіли б з зображення витягти (фігури, лінії, об'єкти, розміри, зміст зображеного тексту і т.д. і т.п.) - можуть бути отримані лише в результаті застосування ряду процедур обробки та аналізу зображення, які ми повинні або самі запрограмувати, або використовувати готові процедури, наявні в відомих пакетах програм для аналізу зображень. При цьому для вирішення простих завдань комп'ютерного зору готові засоби напевно знайдуться в стандартних бібліотеках процедур обробки зображень, для вирішення завдань складніше необхідно буде скомбінувати ті чи інші готові процедури, а для багатьох цілком «звичайних» завдань, які «біологічне» зір людини, здавалося б , вирішує легко і граючи, комп'ютерне машинне зір досі рішень не має і все ще продовжує їх шукати. Адже використовуючи своє природне зір, людина легко орієнтується в будь-якій обстановці, дізнається предмети, вибирає шлях, управляє автомобілем і багато, багато іншого. Чому ж комп'ютер, який отримує зображення від відеокамери, всього цього не може? Може бути, справа в будову людського ока?
Насправді людське око, як і відеокамера, всього лише формує «видиме поле», аналогічне до цифрового зображення. При цьому оптична система, що складається з зіниці і кришталика, проектує двовимірне зображення на сітківку ока, де фоточутливі клітини ( «палички» і «колбочки») перетворять отримане зображення в нервові імпульси. І тільки після цього складний механізм обробки отриманої інформації, що функціонує у відповідному відділі нашого мозку, інтерпретує ці імпульси як зрозуміле нам зображення видимої сцени. Таким чином, і у людини функцію «бачення» виконує не один тільки очей, але система «очей + мозок» ( «сенсор + комп'ютер»). Саме вбудовані в мозок алгоритми обробки інформації дозволяють людині розуміти те, що він бачить. Роль цих вбудованих алгоритмів можна пояснити на наступному прикладі.
Коли в середині XXвека хірурги-офтальмологи навчилися робити операції на кришталику ока, у багатьох сліпих від народження людей з'явилася технічна можливість прозріти. Тобто після такої операції у людини, досі сліпого (світло просто не проходив через кришталик), зображення на сітківці починало формуватися і відповідні сигнали починали надходити в мозок абсолютно так само, як це відбувається у здорових людей. На жаль, в даному випадку «побачити світ» не означало «почати бачити». Як показала подальша історія, більшість «технічно прозріли» дорослих пацієнтів так ніколи і не змогли досягти в області зору більш істотних результатів, ніж розпізнавання простих геометричних фігур - і навіть це вимагало від них серйозних свідомих зусиль. Впізнавання же людей по обличчях і орієнтування в просторі так і залишилися для них непосильними завданнями. Справа в тому, що ті вбудовані механізми «автоматичного» зорового аналізу, які розвиваються у людей в ранньому дитинстві, у цих пацієнтів не були своєчасно розвинені, і вони виявилися в положенні комп'ютера, що має пристрій для введення зображення, але не має необхідного програмного забезпечення для його аналізу.
Для того щоб остаточно переконатися в складності стоїть перед нами завдання аналізу зображення, що представляє собою двовимірний масив числових даних, спробуємо поставити себе на місце комп'ютерної програми, що має справу з абстрактними числами. Для цього подумки змінимо модальність сприйняття зображення - переведемо його з візуальної області в тактильну. Уявімо двовимірний масив значень інтенсивності як шахову дошку, розмір якої дорівнює розміру зображення (DimXDimY), а в центр кожної клітини застромлять стовпчик, висота якого пропорційна значенню відповідного пікселя зображення. Іншими словами, розглянемо двовимірне зображення як якусь умовну тривимірну поверхню. На рис. 1.1.2 зліва фрагмент жіночого обличчя показаний як зображення, а справа зображений як псевдотривимірного рельєф.
@Мал. 1.1.2. Цифрове зображення як псевдо-тривимірний рельєф
Тепер уявіть собі, що ви повинні, що не дивлячись на зображення, обмацати відповідний йому «рельєф» і постаратися визначити, що саме цей «рельєф» зображує - будинок, собаку або людське око? Як показують експерименти, середня людина не в змозі впоратися з подібним завданням. Навіть розпізнавання простих геометричних фігур в подібному «рельєфному» поданні буде пов'язано зі значними зусиллями і зажадає свідомої вироблення спеціального навички, стратегії і алгоритмів обмацування. Така, незважаючи на уявну простоту об'єкта «цифрове зображення», справжня складність завдань комп'ютерного і машинного зору.