Сжатие изображений
Стратегии сжатия двумерных изображений часто основываются на поиске областей с высокой схожестью. В этой задаче мы исследуем конкретный подход, основанный на иерархическом разложении изображения. Для простоты мы рассматриваем только растровые изображения, такие как следующее:
Изображение кодируется в виде дерева, где корень представляет всю область изображения. Если область монохромная, то узел для этой области является листом, хранящим цвет области. В противном случае область делится на четыре части относительно её центра, и подход применяется рекурсивно к каждому квадранту. Для нелистового узла его четыре дочерних узла представляют четыре квадранта, упорядоченные как верхний правый, верхний левый, нижний левый, нижний правый соответственно. В качестве примера, вот дерево, кодирующее изображение выше.
Исходное изображение не монохромное, поэтому мы рассмотрели четыре квадранта. Верхний правый квадрант монохромный белый, поэтому первый дочерний узел корня является листом со значением 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, сверху вниз.