시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 511 | 182 | 135 | 39.017% |
이미지 퀼팅(Image Quilting)이란, 하나의 패턴 이미지를 여러 개 이어붙여서 큰 이미지를 만들어내는 것을 말한다. 하지만 단순히 이미지를 나란히 이어붙이는 것만으로는 자연스러운 이미지를 얻을 수 없다. 이어 붙여질 이미지의 경계가 서로 많이 다를 수 있기 때문이다.
<왼쪽부터 원본 이미지, 단순히 이어붙인 이미지, 최적화하여 이어붙인 이미지>
위와 같은 문제를 해결하고 위의 3번째 이미지같이 더욱 자연스러운 이미지를 얻기 위하여 아래와 같은 방법을 사용한다. 이 문제에서는 편의상 높이가 같은 두 흑백 이미지를 좌우로 합치는 것만 고려한다.
<두 이미지를 포개어 자연스러운 경계를 선택하는 과정>
<포개어진 5X10 영역에서 선택된 경계선 예시>
실제로 포개어진 영역에 존재할 수 있는 경계선은 경우의 수가 많기 때문에 이 중에 가장 자연스럽게 두 이미지를 이어붙일 수 있는 경계를 선택하여야 한다. 경계선의 부자연스러움 정도는 경계선상의 존재하는 각 픽셀 위치에서의 B1 이미지의 픽셀과 B2 이미지의 픽셀의 색상 값의 차를 제곱하여 모두 더한 값으로 정의할 수 있다. 물론 가장 자연스러운 경계선은 이 중 부자연스러운 정도가 가장 낮은 경계선을 의미한다.
<포개어진 영역의 B1 이미지와 B2 이미지, 그리고 최적의 경계선>
이 문제에서는 흑백 영상만을 다루므로 각 픽셀은 0~255의 정수 형태의 색상 값으로 표현할 수 있다. 위의 예시에서 두 이미지는 세 번째 그림과 같이 경계선을 선택하면 최적이라고 할 수 있으며 이때의 부자연스러움 정도는 아래와 같이 계산할 수 있다.
E = (79-62)2 + (10-16)2 + (130-120)2 + (235-240)2 = 450
두 이미지의 포개어질 영역의 색상값들이 주어질 때, 선택할 수 있는 최적의 경계선이 가지는 최소의 부자연스러움 정도를 계산하여 출력하는 프로그램을 작성하시오.
첫 줄에는 포개어진 두 이미지의 높이 H (1 ≤ H ≤ 10) 와 포개어진 영역의 너비 W (1 ≤ W ≤ 10) 가 공백으로 구분된 두 자연수로 주어진다. H는 이미지의 행의 수, W는 포개어진 영역의 열의 수를 나타내는 자연수이다. 이 문제는 포개어질 영역의 색상 값만 주어짐에 유의한다. 입력으로 주어지는 두 이미지는 모두 H행 W열이다.
그 후 H줄에 걸쳐서 B1 이미지의 색상값이 주어진다. 각 줄은 영상의 행이며 W개의 픽셀의 색상 값이 0~255 범위의 자연수로 주어진다. 입력으로 주어지는 행/열의 순서와 실제 영상의 행/열의 순서는 일치한다. 그 후 H줄에 걸쳐서 B2 이미지의 색상값이 주어진다. 입력 형식은 위의 B1 이미지와 같다.
두 이미지에서 선택할 수 있는 경계선이 가지는 최소의 부자연스러운 정도를 한 줄에 출력한다.
4 3 0 79 240 10 110 230 9 130 213 30 70 235 50 62 237 16 58 99 25 120 170 90 120 240
450
University > 아주대학교 > 2017 아주대학교 프로그래밍 경시대회 (APC) > Division 1 C1번