이미지 퀼팅 (라지)

이미지 퀼팅(image quilting)은 패턴 이미지 한 장을 여러 번 이어 붙여 큰 이미지를 만드는 기법이다. 그런데 이미지를 그냥 나란히 붙이면 자연스러운 결과가 나오지 않는다. 맞닿는 두 이미지의 경계 부분이 서로 크게 다를 수 있기 때문이다.

왼쪽부터 원본 이미지, 단순히 이어 붙인 이미지, 최적화해서 이어 붙인 이미지

세 번째 그림처럼 더 자연스러운 결과를 얻으려고 아래 방법을 쓴다. 이 문제에서는 편의상 높이가 같은 흑백 이미지 두 장을 좌우로 합치는 경우만 다룬다.

두 이미지를 포개어 자연스러운 경계를 고르는 과정

이어 붙일 두 이미지를 B1과 B2라고 하자. B1이 왼쪽, B2가 오른쪽이다.
두 이미지의 경계를 조금 포갠다. 포갠 영역의 너비는 최소 2픽셀이다.
포개진 영역에서 B2와 B1의 차이가 가장 작아지도록 경계선을 정한다. 그리고 경계선과 그 오른쪽 부분에 B2의 픽셀을 덮어써서 새 이미지를 만든다.
- 경계선은 포개진 영역의 각 행마다 픽셀을 하나씩 골라서 만든다.
- 경계선의 각 행에서 고른 픽셀은 바로 위나 아래 행에서 고른 픽셀과 두 칸 이상 떨어질 수 없다. 다시 말해 위아래로 인접한 두 경계선 픽셀의 열 번호 차이는 -1, 0, 1 중 하나여야 한다.
- 각 행은 경계선으로 고른 픽셀을 기준으로, 그 왼쪽은 B1의 픽셀을 그대로 쓰고 그 픽셀과 오른쪽 픽셀은 B2의 픽셀로 덮어쓴다.

포개진 5행 10열 영역에서 고른 경계선의 예

포개진 영역에 존재할 수 있는 경계선은 경우의 수가 많으므로, 그중 두 이미지를 가장 자연스럽게 이어 붙이는 경계선을 골라야 한다. 경계선의 부자연스러운 정도는 경계선 위에 있는 각 픽셀 위치에서 B1의 색상 값과 B2의 색상 값의 차를 제곱해 모두 더한 값으로 정의한다. 가장 자연스러운 경계선은 이 값이 가장 작은 경계선이다.

포개진 영역의 B1 이미지와 B2 이미지, 그리고 최적의 경계선

이 문제는 흑백 영상만 다루므로 각 픽셀의 색상 값은 0 이상 255 이하의 정수로 나타낸다. 위 예시에서 두 이미지는 세 번째 그림과 같이 경계선을 고르면 최적이고, 이때 부자연스러운 정도는 다음과 같이 계산한다.

$E = (79-62)^2 + (10-16)^2 + (130-120)^2 + (235-240)^2 = 450$

두 이미지에서 포개질 영역의 색상 값이 주어질 때, 고를 수 있는 경계선 중 부자연스러운 정도가 가장 작은 값을 계산해 출력하는 프로그램을 작성하시오.

첫 줄에 포개진 두 이미지의 높이 $H$ ( $1 \le H \le 100$ )와 포개진 영역의 너비 $W$ ( $1 \le W \le 100$ )가 공백으로 구분된 두 자연수로 주어진다. $H$ 는 이미지의 행 수, $W$ 는 포개진 영역의 열 수다. 이 문제는 포개질 영역의 색상 값만 주어진다는 점에 유의한다. 입력으로 주어지는 두 이미지는 모두 $H$ 행 $W$ 열이다.

그 다음 $H$ 개 줄에 걸쳐 B1 이미지의 색상 값이 주어진다. 각 줄은 영상의 한 행이며, 픽셀 $W$ 개의 색상 값이 0 이상 255 이하의 정수로 주어진다. 입력으로 주어지는 행과 열의 순서는 실제 영상의 행과 열의 순서와 같다. 그 다음 $H$ 개 줄에 걸쳐 B2 이미지의 색상 값이 같은 형식으로 주어진다.