Згорткова - магія - або як я сам зробив цифровий фільтр, LightHouse Software
Ішов один із зимових днів, а я сидів на роботі і розмірковував над математичним завданням, яке мені хоч-не-хоч дісталося... Подвійна сума, двовимірний масив, здавалося б, у чому тут може бути проблема?
Але як виявилося, що така тривіальна процедура, як згортка послідовностей, навіть за наявності повного комплекту математичних посібників та книг з мови програмування D, мені просто не по зубах.
Навіть у одновимірному варіанті…
Тоді того ранку 2014 року я думав, що це кінець — я так і не зміг вирішити це завдання і зробити одновимірну згортку, яка визначається досить просто, про що свідчить опис процедури у Вікіпедії та докладний алгоритм на C++. Якщо бути до кінця чесним, то я навіть не вчитувався в математику і вирішив організувати алгоритм, що називається «в лоб», просто провівши звичайну трансляцію в умі з однієї мови програмування на іншу, і ось тут мене (як і завжди, загалом) то) чекав найнеприємніший сюрприз…
Алгоритм просто не спрацював, хоча був повністю ідентичною копією (за винятком, звичайно, прямої роботи з пам'яттю — в D є така чудова штука, як динамічні масиви практично будь-якої мірності, а тому танці з бубном і memset ' ти стають непотрібними) і мені просто довелося винайти свій велосипед (на жаль, не зберігся, та й перший провал з медіанним фільтром був у тому ж файлі, що характерно).
Але, нещодавно, крізь дні та місяці, до мене ніби рикошетом повернулася необхідність зробити пакунок своїми руками, причому вже двовимірну!
Ех, деякі завдання мають тенденцію повертатися…
Двовимірна згортка — це дуже цікава, і як не дивно, операція, що досить часто використовується, іпрактично кожен з нас використовував її хоча б одного разу, коли працював з фотографіями або намагався зробити якийсь цікавий ефект на довільному зображенні.
Але що ж це таке, пакунка?
Якщо не вдаватися в математику, то все виходить досить просто, особливо, якщо згадати статтю про медіанний фільтр, так як згортка двовимірного масиву і за підходом і навіть трохи по духу близька до медіанного фільтра (а скільки загальних елементів коду).
Уявіть, що зображення (початкова картинка) — це деяка таблиця, у комірки якої вписані значення кольору, представленого деякою структурою даних. За цією таблицею, рухається прямокутна рамка (або вікно, термінологія та сама, що і для медіанного фільтра, з застереженнями, звичайно) непарної довжини і непарної ширини.
Кожен осередок рамки, умовно кажучи, має свою «вартість», яка виражена деяким числом, а крім цього, всередині вікна є центральний елемент, який накладатиметься на кожен елемент прямокутної таблиці зображення.
Справа в тому, що наша рамка або вікно плавно рухається по зображенню, щоразу зсуваючись по центральному елементу на один крок і проходячи «зліва-направо, зверху-вниз» (чесно кажучи, мені важко описати напрямок проходу, але сподіваюся, ви мене зрозумієте ). Але рамка не просто рухається, а змінює кожне значення прямокутної матриці зображення за досить простим законом: кожен елемент прямокутної таблиці вікна, накритий вікном, множиться на відповідну вартість, взяту з нашої рамки, після чого всі значення підсумовуються і значенням того елемента зображення, на якому знаходиться центральний елемент вікна, ставати отриманий результат такого віконного підсумовування.
Такого роду «ковзаюче підсумовування»виконуватися доти, доки не буде пройдено все зображення.
На словах, це дуже складно передати, і здається, математика, в цьому випадку, набагато простіше повсякденної мови, але, програмний код краще розуміється (принаймні для мене) в порівнянні з операціями математичного аналізу:
Тут все відбувається саме так, як я описав: у ролі прямокутної матриці зображення виступає абстрактний супертип SuperImage з уже відомої нам бібліотеки роботи із зображеннями, а ось у ролі вікна виступає щось нове та підозріле – якийсь клас Filter, незрозуміло звідки взятий.
Клас Filter відсутній як у стандартній комплектаціїPhobos, так і вdlib, оскільки він був спеціально придуманий мною для легкого і безболісного створення власних обробників зображення: адже насправді пакунок — це і є процедура, за допомогою якої реалізуються лінійні фільтри з кінцевою імпульсною характеристикою (КИХ-фільтри)!
Клас Filter є абстрактним класом — класом, екземпляр якого створити не можна, але головне, що може він надати — це досить високий рівень абстракції (для представлення будь-якого виду лінійного КІХ-фільтра), а також найменший спільний знаменник між різними існуючими типами лінійних фільтрів, працюючих всередині згорткової операції.
При цьому сам клас виглядає приблизно так:
Ідея класу проста: нам потрібна деяка низка методів, які універсальні для всіх типів фільтрів (не забуваємо про те, що цей Filter є абстрактним), а також деякий набір методів, які будуть легко перевизначені і які відіграють роль параметрів фільтра.
У ролі неперевизначуваних універсалій методи getWidth, getHeight, opIndex, які, відповідно до принципівінкапсуляції, одержують значення приватних членів класу: довжину вікна, ширину вікна та індекс відповідно. Крім того, в інтересах збереження структурної цілісності будь-яким похідним від Filter класом, цілий набір членів-даних класу ми оголошуємо захищеними, що передбачає можливість встановлення цих параметрів усередині спадкоємців Filter. Захищеними параметрами, в даному випадку, служать наступні параметри вікна: довжина і ширина вікна,«ядро згортки» (тобто набір «вартостей» вікна або іншими словами, набір коефіцієнтів, що показують силу, з якої впливає оточення на центральний піксель), дільник і зміщення (спеціально підібрані величини, що служать для того, щоб вихідне значення операції згортки входило в допустимий діапазон типу даних, що представляє колір пікселів).
В принципі, проект уже компілюється або збирається за допомогоюdub, але для випробувань не вистачає хоча б одного прикладу робочого фільтра, а ще залишається питання як (виходячи з вже створених нами функції та класу) зробити фільтр і де взяти його параметри (ядро, дільник та усунення).
Визначимо, наприклад, свій фільтр, який виділить найближчі пікселі та поставить їх приблизно на один рівень яскравості із центральним. Для цього необхідно просто зробити спадкування від абстрактного класу Filter і визначити конструктор похідного класу, задавши всередині нього значення для описаних вище параметрів:
Написати свій фільтр для зображень, виявляється не так вже й моторошно: достатньо реалізувати згортку послідовностей і знайти матрицю потрібного ефекту. До речі, про ефект, створений нами фільтр зробить зображення чіткішим, але яскравість може втратити пару півтонів - ось подивіться на стандартне зображення, оброблене отриманим фільтром Area4 за допомогою ось такогокоду:
Файли convolution.d і transformation.d містять, відповідно, реалізації згортки (конволюції) та фільтра Area4. Зображення після впливу згорткової матриці:
Загалом, на цьому на тему згортки ще не закінчено і скоро ми покажемо ще кілька цікавих ефектів, заснованих на пакунку, але це вже будуть зовсім інші статті.