Математика/5. Математичне моделювання

Сердюк М.Є.

Національна металургійна академія України

Каркасна інтерполяція статичних зображень з використанням 6-точкових сепарабельних сплайнів.

Вступ. Просторова інтерполяція цифрових зображень пов’язана зі здійсненням зміни щільності пікселів на одиницю площі малюнка. На сьогодні, до найбільш відомих методів просторової інтерполяції можна віднести наступні (див. [1, 2]): метод найближчого сусідства, білінійну, біквадратичну, бікубічну інтерполяції, В-сплайн інтерполяцію, інтерполяцію Lanczos’а. Загальною рисою цих підходів є побудова так званих сепарабельних інтерполяційних фільтрів. Це означає, що зміна щільності пікселів для будь-якого зображення спочатку реалізується за x-координатою (горизонтальний zooming), і лише потім за y-координатою (вертикальний zooming). Власне ця обставина і приводить до появи небажаних візуальних ефектів в маcштабованих зображеннях (розмитість контурних ліній, “сходинковий” ефект в похилих контурах (aliazing-ефект), дублюючі контури (ефект Gibbs’а) і т.п.).

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

Постановка задачі. Нехай - довільна непуста підмножина R², - масив опорних точок (пікселів) на Δ. Нехай I - зображення в шкалі сірих відтінків, для якого , і при цьому для всіх , де - породжуюча функція I така, що . Нехай є образом означеного зображення на піксельну сітку .

Відомо (див. [4]), що для класу функцій з обмеженою варіацією їх топографічні карти можна описати в термінах кривих Jordan’а. Будемо вважати, що при кожному значенні множини рівнів зображення I мають скінченний периметр . Надалі такі зображення будемо утотожнювати з породжуючими їх функціями .

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

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

Означення 2. Нехай - довільний допустимий каркас для . Тоді зображення будемо називати каркасною інтерполяцією для , якщо: 1) його образ на піксельну сітку співпадає з ; 2) ; 3) знайдуться функція і диз’юнктивне розбиття множини такі, що:

для всіх ;

(1)

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

Означення 3. 6-точковим сплайном, побудованим на ланцюгу вхідних даних будемо називати функцію , якщо

, (2)

де включення рівносильне виконанню умов

(3)

(4)

. (5)

У відповідності до результатів, наведених в [5], задача про інтерполяційний сплайн (2)-(5) має єдиний розв’язок . Вирішення цієї задачи за допомогою системи Maple 10 дає наступний результат:

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

Конструювання каркасу зображення. Нехай для кожного із пікселів є відомим деякий його направлений окіл . Позначимо зону впливу обраного піксела – замкнену кулю радіуса 1/2 з центром в точці , а - сукупність всіх пікселів, сусідніх з . Введемо до розгляду множини . Покладемо

. (6)

Ясно, що умова приналежності точок до каркасу забезпечує включення (див. означення 1).

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

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

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

.

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

Алгоритм побудови функції Ĩ*. Функцію будемо вважати відтвореною в задачі каркасної інтерполяції (1), якщо правило, за яким визначається її значення в кожній точці каркасу , забезпечує виконання властивостей .

Введемо наступні поняття.

Означення 4. Решіткою для множини будемо називати ті точки з , які лежать на прямих та , де , .

Означення 5. Вектором решітчатого зсуву будемо називати довільний вектор , координати якого задовольняють умовам:

Для відтворення функції в довільній точці направленого околу піксела виконаємо наступні дії. Оберемо вектор решітчатого зсуву мінімально можливої довжини такий, що , при цьому , де та - центральні ланки ланцюга . Введемо вектор , де найближчий піксел до . Позначимо і розглянемо систему точок де . Ясно, що . Через цю систему точок і через залучення 6-точкових сплайнів відтворимо значення функції в точках , . В залежності від орієнтації вектора , правило апроксимації буде різним. Так, якщо є -орієнтованим, то , , де є відстанню від до точки , а 6-точковий сплайн будується за системою точок . Якщо є -орієнтованим, то , де 6-точковий сплайн будується за системою точок . Аналогічно відтворюється значення функції у випадку, коли є -орієнтованим або -орієнтованим. При цьому сплайни будуються за вертикальними системами точок.

Тоді правило для відтворення значення функції в довільній точці з -направленого околу набуває наступного вигляду: якщо є відстанню від точки до центрального з’єднання ланцюга , то

(7)

де позначено: - 6-точковий сплайн за системою точок , а - такий же сплайн за системою .

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

Література:

1. Carlson B. Image interpolation and filtering // IEEE Trans on ASSP.-March 2000.-Vol. ASSP-26, no. 4.

2. Keys R. Cubic convolution interpolation for digital image processing // IEEE Trans on ASSP.-Dec 2002.-Vol. ASSP-29, no. 6.

3. Serra J. Image Analysis and Mathematical Morphology. New York: Academic Press, 1982.

4. Ambrosio L., Caselles V., Masnou S., Morel J.M. The connected components of sets of finite perimeter // European Journal of Mathematics, - 2001. - Vol. 3. - Pp. 39-92.

5. Треногин В.А. Функциональный анализ. - Москва: Физматлит, 2002.