열림과 닫힘

형태학적 연산(morphological operation)은 영역의 모양을 표현하고 기술하기 위해 영상의 구성 요소를 추출하는 도구이다. 대표적인 두 연산이 열림(opening) 과 닫힘(closing) 이다. 두 연산을 정의하기에 앞서, 먼저 영상을 어떻게 표현하는지 정한다.

$M$개의 행과 $N$개의 열로 이루어진 이진 영상 $A$는 픽셀 값이 $1$인 좌표 $(r, c)$ ($1 \le r \le M$, $1 \le c \le N$)들의 집합으로 나타낸다. 왼쪽 위 모서리의 좌표는 $(1, 1)$이다. 또한 구조 요소(structuring element) 라고 부르는 이진 영상 $B$가 주어지는데, $B$는 $2S+1$개의 행과 $2S+1$개의 열을 가지며 같은 방식으로 집합으로 나타내되 왼쪽 위 픽셀의 좌표가 $(-S, -S)$이다(따라서 중심은 $(0, 0)$이다).

기본이 되는 두 연산은 팽창(dilation) 과 침식(erosion) 이다. $B$에 의한 $A$의 팽창은 다음과 같이 정의한다.

A (+) B = { a + b | a in A, b in B } ∩ Z

여기서 좌표의 덧셈은 성분별로 이루어지고, $Z$는 $1 \le i \le M$, $1 \le j \le N$인 좌표 $(i, j)$들의 집합이다. $B$에 의한 $A$의 침식은 다음과 같이 정의한다.

A (-) B = { w | 모든 b in B 에 대하여 w + b in A }

이를 이용하여 $B$에 의한 $A$의 열림 은

A o B = (A (-) B) (+) B

이고, $B$에 의한 $A$의 닫힘 은

A . B = (A (+) B) (-) B

이다. 대략적으로, 열림은 전체적인 모양을 유지하면서 작은 세부를 제거하고, 닫힘은 전체적인 모양을 유지하면서 작은 틈을 메운다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 공백으로 구분된 세 정수 $M$, $N$, $S$가 있는 줄로 시작한다 ($10 \le M, N \le 256$, $1 \le S \le 4$). 이어지는 $M$개의 줄에는 영상 $A$의 각 행이 주어지며, 각 줄은 .(0) 또는 *(1)인 $N$개의 문자로 이루어진다. 그다음 $2S+1$개의 줄에는 같은 방식으로 구조 요소 $B$가 주어진다. 입력은 0 0 0인 줄로 끝난다.

각 케이스마다 케이스 번호를 한 줄에 Case x 형식으로 출력하고 빈 줄을 하나 출력한다. 이어서 열림 $A \circ B$의 결과 영상을 출력하고, 빈 줄을 하나 출력한 뒤, 닫힘 $A \bullet B$의 결과 영상을 출력한다. 결과 영상의 형식은 입력 영상과 같다. 서로 다른 케이스의 출력 사이에는 등호(=) 75개로 이루어진 줄을 하나 넣어 구분한다(마지막 케이스 뒤에는 이 구분선을 출력하지 않는다).