Source file: | compress.{c, cpp, java} |
Input file: | compress.in |
Strategies for compressing two-dimensional images are often based on finding regions with high similarity. In this problem, we explore a particular approach based on a hierarchical decomposition of the image. For simplicity, we consider only bitmapped images such as the following:
The image is encoded as a tree, with the root representing the entire image region. If a region is monochromatic, then the node for that region is a leaf storing the color of the region. Otherwise, the region is divided into four parts about its center, and the approach is applied recursively to each quadrant. For a non-leaf node, its four children represent the four quadrants ordered as upper-right, upper-left, lower-left, lower-right respectively. As an example, here is the tree encoding of the above image.
As a larger example, here is an 8x8 image and the tree encoding of it.
Thus far we have described a lossless compression scheme, but the approach can be used for lossy compression with the following adjustment. Instead of continuing the decomposition until reaching a monochromatic region, a threshold such as 75% is used, and a leaf is created whenever a region has at least that percentage of either color. As an example, here is the encoding of the above 8x8 image if using 75% as the threshold.
Your goal is to determine the image that results from this lossy compression scheme, given an original bitmap image and a specific threshold percentage.
Input:
The input will consist of a series of data sets, followed by a line
containing only 0. Each data set begins with a line containing values
W and T, where W is the width of the bitmap and T is the threshold
percentage. Images will always be square with
Output: For each data set, you should print an initial line of the form "Image 1:" numbering the images starting with 1. Following that should be W lines, with each line representing a row of the resulting bitmap as a string of characters 0 and 1, from top to bottom.
Example Input: | Example Output: |
4 80 0000 1000 0011 0011 8 75 11111000 11110000 11000011 11000011 11000100 00000100 00010011 00010011 4 75 1101 1111 0111 0011 0 |
Image 1: 0000 1000 0011 0011 Image 2: 11110000 11110000 11110011 11110011 00000100 00000100 00000011 00000011 Image 3: 1111 1111 1111 1111 |