그냥 줄이지 않고 폭을 잃는 이미지

모든 픽셀에 비용을 준다

합성 이미지는 폭 240, 높이 150픽셀이다. 완만히 변하는 어두운 배경에 금색 원과 파란 세로 막대가 있다. 스크립트는 세 색 채널의 산술 평균을 구한 뒤 그 스칼라 이미지의 수평 및 수직 기울기 절댓값을 더해 점수를 만든다.

흔히 에너지라고 부르지만 물리적 에너지나 보정된 휘도 측정은 아니다. 국소 대비의 대리값이다. 강한 경계는 비싸고 거의 균일한 곳은 싸다. 이름 때문에 선택이 가려져서는 안 된다. 알고리즘은 이 수치장의 변화를 피하라는 지시를 받았지 물체를 이해하라는 지시를 받은 것이 아니다.

채널 평균에는 특정한 색 구분의 한계가 있다. 순수 빨강 (1, 0, 0)과 순수 초록 (0, 1, 0)은 모두 3분의 1이 된다. 원래 색은 크게 달라도 두 색 사이 경계가 이 스칼라 점수에서는 완전히 사라질 수 있다. 산술이 틀린 것이 아니라 경로 탐색 전에 버린 정보를 보여 주는 예다. 탐색 알고리즘만 바꿔서는 입력 비용에 없는 경계를 되살릴 수 없다.

비용 사이로 연결된 길을 찾는다

수직 심은 행마다 픽셀을 정확히 하나 포함한다. 다음 행으로 갈 때 왼쪽 한 열, 같은 열, 오른쪽 한 열로 움직일 수 있다. 연결을 유지하면서도 딱딱한 열 잘라내기와 달리 비싼 영역을 피해 휠 수 있다.

동적 계획법은 현재 에너지 이미지의 총비용 최소 심을 찾는다. 각 픽셀에서 위 행의 유효한 이전 픽셀 중 최소 누적 비용에 현재 비용을 더한다. 마지막 행의 가장 싼 끝점에서 역추적하면 경로가 나온다. 작은 별도 시험에서는 모든 허용 경로를 열거한 답과 비교한다.

심을 지우면 다음 문제가 달라진다

선택한 픽셀을 지운 뒤 각 행의 남은 픽셀로 틈을 닫는다. 폭은 하나 줄고 높이는 그대로다. 바뀐 이미지에서 기울기를 다시 계산하고 새 심을 찾아 70개를 없앨 때까지 반복한다. 최종 크기는 170 × 150이다.

각 심은 현재 비용장과 규칙에서 최적이다. 하지만 70회 삭제 전체가 모든 가능한 최종 이미지에 대해 전역 최적이라는 증명은 아니다. 앞선 선택은 이후 이웃과 비용을 바꾼다. 단순 구현은 반복되는 국소 결정을 보여 주며 모든 최신 콘텐츠 인식 조정 기법을 재현하지 않는다.

틈을 닫으면 새로운 이웃도 생긴다. 삭제한 접합선 양쪽에 있던 픽셀이 서로 붙으면서 눈에 띄는 새 경계를 만들 수 있다. 여기서 쓰는 후방 에너지 점수는 제거 전 현재 이미지의 대비를 보며, 새로 생기는 모든 관계에 비용을 명시적으로 부과하지 않는다. 나중에 다시 계산하는 것은 유용하지만 이미 손상시킨 선택을 되돌리지는 않는다. 따라서 선택한 경로의 비용이 낮았는지뿐 아니라 편집된 이미지 자체도 확인해야 한다.

유리한 예에서는 원을 지킨다

이 특정 예에서 금색 원에 속하는 2,809개 픽셀은 카빙 후 모두 남는다. 배경이 삭제를 흡수해 원의 픽셀 형태를 유지한다. 같은 출력 크기로 일반 축소하면 원을 가로로 눌러 높이 대비 좁게 만든다.

성공은 의도적으로 구성한 그림에 한정된다. 대상은 강한 경계와 주변의 충분한 저비용 공간이 있다. 얼굴, 글자, 건축, 자연 사진은 시험하지 않았다. 성공한 경우에도 간격과 구성은 변하므로 물체 픽셀 보존이 이미지 전체 의미 보존은 아니다.

평평한 대상이 맹점을 드러낸다

실패 예는 넓은 금색 전경과 미세 반복 줄무늬다. 내부는 시각적으로 주제의 일부여도 기울기 점수에서는 쌀 수 있다. 심 90개를 지우면 전경 픽셀은 21,000에서 14,550으로 줄어 영역이 눈에 띄게 좁아진다.

알고리즘은 지시대로 했다. 매끄러운 얼굴, 단순 표지판, 조용한 그래픽 중심을 지켜야 할 의미적 이유를 모른다. 보호 마스크, 다른 비용, 새 경계를 고려하는 방식은 특정 사례를 개선하지만 추가 판단도 필요하다. 자동 크기 조정에도 관계와 형태 확인이 필요하다.

사용자가 지키려는 픽셀에 추가 벌점을 주어 보호를 표현할 수 있다. 목표에 정보가 더해지지만 완벽해지는 것은 아니다. 유한한 벌점은 다른 비용에 밀릴 수 있고, 완전히 금지된 영역은 연결 경로 자체를 없앨 수 있다. 보호된 대상의 픽셀을 유지하면서도 주변 간격은 달라질 수 있다. 살아남아야 할 대상과 설득력 있게 유지해야 할 시각적 관계를 함께 지정한 뒤, 같은 표시 축척에서 실제 출력을 확인하는 편이 좋다.

목적함수도 편집의 일부다

심을 겹쳐 보여 주면 숨은 선택이 드러난다. 좁아진 그림을 받아들이기 전에 무엇을 지웠고 어떤 선이 휘었으며 익숙한 비율이 바뀌었는지 보자. 작은 수치 비용이 큰 시각적 또는 사실적 결과를 감출 수 있다. 장식보다 증거로 쓰이는 이미지에서는 특히 중요하다.

심 카빙은 편집이 크기 외의 것도 최적화할 수 있음을 보여 줘 매력적이다. 동시에 목표를 신중히 골라야 한다는 점도 보여 준다. 영리하게 작아진 그림이 관찰자가 보존하길 원한 내용에는 덜 충실해질 수 있다.

바로 다음의 가장 싼 픽셀만 고르면 안 되는 이유

추가한 4행 5열 격자는 손으로 확인할 수 있는 작은 비용 지도다. 탐욕적인 이동은 맨 윗줄에서 가장 싼 칸을 고르고, 다음 행의 가능한 이웃 중 가장 싼 칸을 계속 선택한다. 같은 값이면 왼쪽을 고를 때 첫 번째 열에 머물며 1 + 1 + 9 + 9 = 20을 지불한다. 조금 더 비싼 시작점이 나을 수 있다. 2, 3, 3, 3열을 따르면 비용은 2 + 2 + 1 + 1 = 6이다.

동적 계획법은 눈앞의 가장 싼 다음 단계에 확정하지 않고, 각 후보에 도달하는 최저 비용을 유지한다. 누적 비용 패널의 숫자는 그 지점까지 최적 경로의 앞선 모든 행을 포함한다. 마지막 행의 최솟값은 6이며, 역추적하면 더 좋은 경로를 얻는다. 가능한 연결 경로 95개를 모두 조사해 이 격자에서 유일한 최적해임을 확인했다. 현재 접합선 전체의 최적해와 픽셀별 탐욕 선택의 차이가 구체적으로 드러난다.

세 번째 행, 세 번째 열의 칸에 보호 벌점 100을 더하면 최적 경로는 1, 1, 2, 3열로 바뀌며 비용은 12다. 해당 칸을 피하고, 전수 열거로 바뀐 답도 확인할 수 있다. 추가 벌점은 명시적인 선호이지 알고리즘이 그림을 이해해서 배운 것이 아니다. 이 작은 예는 실제 이미지 픽셀을 삭제하지 않는다. 목표를 바꾸면 해가 달라짐을 보여 주며, 전체 이미지 예제는 원래의 보호 없는 대비 점수를 유지한다.