Problem F
Combining Images
---- The 2003 ACM Programming Contest World Finals ----

As the exchange of images over computer networks becomes more common, the problem of image compression takes on increasing importance. Image compression algorithms are used to represent images using a relatively small number of bits.
 「コンピュータネットワークにおいて、イメージ画像がより多く使われ、その圧縮の重要度が増している。より少ないビット数で画像を表現するにはイメージ圧縮アルゴリズムが使われる。」

One image compression algorithm is based on an encoding called a “Quad Tree.” An image has a Quad Tree encoding if it is a square array of binary pixels (the value of each pixel is 0 or 1, called the “color” of the pixel), and the number of pixels on the side of the square is a power of two.
 「イメージ圧縮アルゴリズムのひとつに4分木(Quad Tree)による表現方法がある。イメージを4分木表現で表現できるのは、イメージが 0か1の値(モノクロ)をもつバイナリピクセルの正方形配列でつくられ、各辺のピクセルの数が2のべき乗になる場合だ。

If an image is homogeneous (all its pixels are of the same color), the Quad Tree encoding of the image is 1 followed by the color of the pixels. For example, the Quad Tree encoding of an image that contains pixels of color 1 only is 11, regardless of the size of the image.
 「イメージが同色の場合、4分木表現は1とそれに続くピクセルの色となる。たとえば、黒一色のイメージの表現は11であり、イメージのサイズと関係ない。」

If an image is heterogeneous (it contains pixels of both colors), the Quad Tree encoding of the image is 0 followed by the Quad Tree encodings of its upper-left quadrant, its upper-right quadrant, its lower-left quadrant, and its lower-right quadrant, in order.
 「イメージが白黒両方をもつ場合、4分木表現は0に続き、左上、右上、左下、右下の四箇所のそのさらなる4分木表現によって表される。」

The Quad Tree encoding of an image is a string of binary digits. For easier printing, a Quad Tree encoding can be converted to a Hex Quad Tree encoding by the following steps:
  a. Prepend a 1 digit as a delimiter on the left of the Quad Tree encoding.
  b. Prepend 0 digits on the left as necessary until the number of digits is a multiple of four.
  c. Convert each sequence of four binary digits into a hexadecimal digit, using the digits 0 to 9 and capital A through F to represent binary patterns from 0000 to 1111.
 「イメージの4分木表現は2進数列になる。見やすくするため、つぎの方法で16進4分木表現に変換できる。
  a. 4分木表現の左側に区切りとしてビット1をつける。
  b. ビット数が4の倍数になるまで、ビット0を左につける。
  c. 4ビットずつ16進数に変換する。ビットパターン0000~1111に0~9と大文字A~Fを使う。」

For example, the Hex Quad Tree encoding of an image that contains pixels of color 1 only is 7, which corresponds to the binary string 0111.
 「たとえば、黒一色だけのイメージの4分木表現は7であり、2進数列 0111に対応する。」

You must write a program that reads the Hex Quad Tree encoding of two images, computes a new image that is the intersection of those two images, and prints its Hex Quad Tree encoding. Assume that both input images are square and contain the same number of pixels (although the lengths of their encodings may differ). If two images A and B have the same size and shape, their intersection (written as A & B) also has the same size and shape. By definition, a pixel of A & B is equal to 1 if and only if the corresponding pixels of image A and image B are both equal to 1.
 「イメージ2つの16進4分木表現を読み取り、イメージの共通部分を取り出し、16進4分木表現で表示するプログラムをつくって欲しい。2つの入力イメージが正方形で、ピクセルの数も同じ(それらの表現の長さが違うかもしれない)と仮定してよい。イメージAとBが同じサイズと形をもつならば、これらの共通部分(A & B と書く)も同じサイズと形をもつ。定義として、ピクセルA & B が1になるのは、イメージAとBの対応するピクセルが両方とも1の場合に限る。」

The following figure illustrates two input images and their intersection, together with the Hex Quad Tree encodings of each image. In the illustration, shaded squares represent pixels of color 1.
 「つぎの図に入力イメージ2つの共通部分と、16進数4分木表現が示されている。影部分は黒を表現している。」

Input
The input data set contains a sequence of test cases, each of which is represented by two lines of input. In each test case, the first input line contains the Hex Quad Tree encoding of the first image and the second line contains the Hex Quad Tree encoding of the second image. For each input image, the number of hexadecimal digits in its Hex Quad Tree encoding will not exceed 100.
 「入力に複数のテストケースが入り、それぞれを2行で説明する。1行目にはイメージ1の16進4分木表現、2行目にはイメージ2のもの。各入力イメージに対し、16進4分木表現の桁数は100以下となる。」

The last test case is followed by two input lines, each containing a single zero.
 「入力の最後の2行に、0が入る。

Output
For each test case, print “Image” followed by its sequence number. On the next line, print the Hex Quad Tree encoding of the intersection of the two images for that test case. Separate the output for consecutive test cases with a blank line.
 「各テストケースに対し、イメージの通し番号を表示すること。つぎの行に、イメージの共通部分を16進4分木表現で表示すること。各ケースの間に空白行を入れること。」

Sample Input
2FA
2BB
2FB
2EF
7
2FA
0
0

Output for the Sample Input
Image 1:
2BA

Image 2:
2EB

Image 3:
2FA

Comments are closed.

Post Navigation