Стиснення зображень
Стратегії стиснення двовимірних зображень часто базуються на пошуку областей з високою схожістю. У цій задачі ми розглянемо конкретний підхід, заснований на ієрархічній декомпозиції зображення. Для простоти ми будемо працювати лише з растровими зображеннями, такими як наведене нижче:
Зображення кодується у вигляді дерева, де корінь представляє всю область зображення. Якщо область є монохромною, то вузол для цієї області є листком, що зберігає колір області. В іншому випадку область ділиться на чотири частини відносно її центру, і підхід застосовується рекурсивно до кожного квадранта. Для немонохромного вузла його чотири нащадки представляють чотири квадранти, розташовані у порядку: верхній-правий, верхній-лівий, нижній-лівий, нижній-правий відповідно. Як приклад, ось дерево кодування вищезгаданого зображення.
Оригінальне зображення не є монохромним, тому ми розглянули чотири квадранти. Верхній-правий квадрант є монохромним білим, тому перший нащадок кореневого вузла є листком зі значенням 0. Верхній-лівий квадрант не є монохромним, тому він далі ділиться на чотири підквадранти, кожен з яких є тривіально монохромним. Це призводить до піддерева з листковими значеннями 0, 0, 1, 0. Останні два квадранти є монохромними з відповідними значеннями 0 і 1.
Як більший приклад, ось зображення 8x8 і дерево його кодування.
До цього моменту ми описали схему безвтратного стиснення, але підхід може бути використаний для втратного стиснення з наступним коригуванням. Замість продовження декомпозиції до досягнення монохромної області, використовується поріг, наприклад, 75%, і листок створюється, коли область має принаймні цей відсоток одного з кольорів. Як приклад, ось кодування вищезгаданого зображення 8x8, якщо використовувати 75% як поріг.
Зверніть увагу, що 75% верхнього-лівого квадранта повного зображення є чорними, і тому другий нащадок кореня є 1, і що більше 75% нижнього-лівого квадранта повного зображення є білими, і тому третій нащадок кореня є 0. Однак, ні білий, ні чорний не досягають 75% у верхньому-правому квадранті, тому рекурсивна декомпозиція продовжується, але всі чотири з цих підквадрантів досягають порогу 75% і стають листками. Якщо ми розпакуємо зображення на основі цього нового втратного кодування, ми отримаємо наступний результат.
Ваше завдання — визначити зображення, яке виходить в результаті цієї схеми втратного стиснення, маючи оригінальне растрове зображення і конкретний відсоток порогу.
Вхідні дані
Вхідні дані складатимуться з серії наборів даних, за якими слідує рядок, що містить лише 0. Кожен набір даних починається з рядка, що містить значення W та T, де W — це ширина растрового зображення, а T — відсоток порогу. Зображення завжди будуть квадратними з 1 ≤ W ≤ 64, що є ступенем двійки. Поріг T буде цілим числом з 51 ≤ T ≤ 100. Після специфікації W та T йдуть W додаткових рядків, кожен з яких є рядком ширини W, що містить лише символи 0 та 1, представляючи рядок растрового зображення, з верху до низу.
Вихідні дані
Для кожного набору даних ви повинні надрукувати початковий рядок у формі "Image 1:", нумеруючи зображення, починаючи з 1. Після цього повинні йти W рядків, кожен з яких представляє рядок отриманого растрового зображення у вигляді рядка символів 0 та 1, з верху до низу.