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