개요
이 기사에서는 "Seam Carving"으로 알려진 흥미로운 알고리즘에 대해 자세히 알아 봅니다. 이미지를 자르거나 내용을 왜곡하지 않고 이미지 크기를 조정하는 것은 불가능 해 보이는 작업을 수행합니다. 우리는 이음새 조각 알고리즘을 처음부터 구현하는 방법을 구축하고 그 뒤에 숨겨진 몇 가지 흥미로운 수학을 엿볼 것입니다.
미적분에 대한 약간의 지식은 따라하는 데 도움이되지만 필수는 아닙니다. 그럼 시작합시다.
(이 기사는 MIT의 Grant Sanderson의 강의에서 영감을 받았습니다.)
문제 :
이 이미지를 살펴 보겠습니다.
살바도르 달리가 그린이 그림은“기억의 지속성”이라고 불립니다. 예술적 가치보다는 그림의 내용에 더 관심이 있습니다. 너비를 줄여 그림 크기를 조정하려고합니다. 우리가 생각할 수있는 두 가지 유효한 프로세스는 그림을 자르거나 너비를 줄이는 것입니다.
그러나 우리가 볼 수 있듯이 자르기는 많은 물체를 제거하고 압착하면 사진이 왜곡됩니다. 우리는 두 가지 장점을 모두 원합니다. 즉, 개체를 자르거나 왜곡하지 않고 너비를 줄입니다.
보시다시피, 물체와 함께 그림에 많은 빈 공간이 있습니다. 여기서 우리가 원하는 것은 물체 사이의 빈 공간을 제거하여 불필요한 공간을 버리고 그림의 흥미로운 부분을 유지하는 것입니다.
이것은 참으로 어려운 문제이며 길을 잃기 쉽습니다. 따라서 문제를보다 관리하기 쉬운 작은 부분으로 나누는 것이 항상 좋은 생각입니다. 이 문제를 두 부분으로 나눌 수 있습니다.
- 그림에서 흥미로운 부분 (즉, 물체)을 식별합니다.
- 그림을 왜곡하지 않고 제거 할 수있는 픽셀 경로 식별.
개체 식별 :
계속 진행하기 전에 그림을 그레이 스케일로 변환하고 싶습니다. 나중에 수행 할 작업에 도움이 될 것입니다. 다음은 RGB 픽셀을 그레이 스케일 값으로 변환하는 간단한 공식입니다.
def rgbToGrey (arr) : greyVal = np.dot (arr [..., : 3], [0.2989, 0.5870, 0.1140]) return np.round (greyVal) .astype (np.int32)
사물을 식별하기 위해 전략을 세울 수 있습니다. 그림의 모든 가장자리를 어떻게 든 식별 할 수 있다면 어떨까요? 그런 다음 이음새 조각 알고리즘에 가장자리를 통과하지 않는 픽셀 경로를 가져 오도록 요청할 수 있으므로 확장하면 가장자리로 닫힌 영역은 건드리지 않습니다.
그렇다면 우리는 어떻게 가장자리를 식별할까요? 우리가 할 수있는 한 가지 관찰은 인접한 두 픽셀 사이에 색상이 급격히 변할 때마다 물체의 가장자리가 될 가능성이 높습니다. 이 즉각적인 색상 변화를 해당 픽셀에서 새 개체의 시작으로 합리화 할 수 있습니다.
다음으로 해결해야 할 문제는 픽셀 값의 급격한 변화를 식별하는 방법입니다. 지금은 한 줄의 픽셀이라는 간단한 경우를 생각해 봅시다. 이 값 배열을 다음과 같이 표시한다고 가정하십시오. x.
우리는 픽셀의 차이를 취할 수 있습니다 x [i + 1], x [i]. 현재 픽셀이 오른쪽에서 얼마나 달라지는 지 보여줍니다. 또는 우리는 또한 차이를 취할 수 있습니다 x [i] 과 x [i-1] 왼쪽에 변화를 줄 것입니다. 총 변화를 표시하기 위해 두 가지의 평균을 구할 수 있습니다.
미적분학에 익숙한 사람은이 표현을 미분의 정의로 빠르게 식별 할 수 있습니다. 맞습니다. 급격한 변화를 계산해야합니다. x 그래서 우리는 그것의 미분을 계산하고 있습니다. 우리가 가질 수있는 또 하나의 열망하는 관찰은 필터를 정의한다면 [-0.5,0,0.5] 그리고 배열 [x [i-1], x [i], x [i + 1]] 및 그 합계를 취하면 x [i]에서 미분을 얻을 수 있습니다. 사진이 2d이므로 2d 필터가 필요합니다. 자세한 내용은 다루지 않겠습니다. 필터의 2D 버전은 다음과 같습니다.
필터가 x 축을 따라 각 픽셀에 대한 미분을 계산하므로 수직 가장자리를 제공합니다. 마찬가지로 y 축을 따라 미분을 계산하면 수평 가장자리가 생깁니다. 이에 대한 필터는 다음과 같습니다. (전치시 x 축 필터와 동일합니다.)
이러한 필터는 Sobel 필터.
따라서 사진을 가로 질러 이동해야하는 두 개의 필터가 있습니다. 각 픽셀에 대해 주변의 (3X3) 부분 행렬로 요소 별 곱셈을 수행 한 다음 그 합계를 취합니다. 이 작업을 Convolution이라고합니다.
회선:
수학적으로 컨볼 루션 연산은 다음과 같습니다.
두 함수의 점적 곱셈을 수행하는 방법을 확인한 다음 통합하십시오. 수치 적으로는 우리가 이전에했던 것, 즉 필터와 이미지를 요소별로 곱한 다음 그 합계를 가져 오는 것과 일치합니다.
알림, 방법 k 그것은 다음과 같이 쓰여진 기능 k (t-τ). 컨볼 루션 연산을 위해서는 신호 중 하나를 뒤집어 야하기 때문입니다. 이런 식으로 직관적으로 상상할 수 있습니다. 직선 수평 선로에있는 두 개의 기차가 불가피한 충돌을 위해 서로를 향해 달리고 있다고 상상해보십시오 (중첩 때문에 기차에 아무 일도 일어나지 않을 것이라고 걱정하지 마십시오). 그래서 기차의 머리는 서로 마주보고있을 것입니다. 이제 트랙을 왼쪽에서 오른쪽으로 스캔한다고 상상해보십시오. 그런 다음 왼쪽 열차의 경우 뒤에서 머리로 스캔합니다.
마찬가지로 컴퓨터는 왼쪽 상단에서 오른쪽 하단으로가는 대신 오른쪽 하단 (2,2) 모서리에서 왼쪽 상단 (0,0)까지 필터를 읽어야합니다. 따라서 실제 Sobel 필터는 다음과 같습니다.
컨볼 루션 작업 전에 180도 회전을합니다.
우리는 계속해서 간단한 소박한 컨볼 루션 작업을 수행하는 구현. 다음과 같을 것입니다.
def naiveConvolve (img, ker) : res = np.zeros (img.shape) r, c = img.shape rK, cK = ker.shape halfHeight, halfWidth = rK // 2, cK // 2 ker = np.rot90 (ker, 2) img = np.pad (img, ((1,1), (1,1)), mode = 'constant') for i in range (1, r + 1) : for j in range ( 1, c + 1) : res [i-1, j-1] = np.sum (np.multiply (ker, img [i-halfHeight : i + halfHeight + 1, j-halfWidth : j + halfWidth + 1]) )) 반환 해상도
이것은 잘 작동하지만 결과에 도달하기 위해 거의 9 * r * c 곱셈과 덧셈을 수행하므로 실행하는 데 엄청난 시간이 걸립니다. 그러나 우리는 똑똑하고 수학에서 더 많은 개념을 사용하여 시간 복잡성을 크게 줄일 수 있습니다.
빠른 컨볼 루션 :
컨볼 루션에는 흥미로운 속성이 있습니다. 시간 도메인의 컨볼 루션은 주파수 도메인에서의 곱셈에 해당합니다. 즉
어디로 F (w) 주파수 영역의 기능을 나타냅니다.
푸리에 변환이 시간 영역의 신호를 주파수 영역으로 변환한다는 것을 알고 있습니다. 따라서 우리가 할 수있는 것은 이미지와 필터의 푸리에 변환을 계산하고 곱한 다음 역 푸리에 변환을 수행하여 컨볼 루션 결과를 얻는 것입니다. 이를 위해 NumPy 라이브러리를 사용할 수 있습니다.
def fastConvolve (img, ker) : imgF = np.fft.rfft2 (img) kerF = np.fft.rfft2 (ker, img.shape) return np.fft.irfft2 (imgF * kerF)
(참고 : fastConvolve 함수가 원형 컨볼 루션을 계산하기 때문에 일부 경우 값이 순진한 방법과 약간 다를 수 있습니다. 그러나 실제로는 이러한 작은 값 차이에 대해 걱정하지 않고 고속 컨볼 루션을 편안하게 사용할 수 있습니다.)
멋있는! 이제 수평 모서리와 수직 모서리, 즉 x 및 y 구성 요소를 계산하는 효율적인 방법이 있습니다. 따라서 다음을 사용하여 이미지의 가장자리를 계산합니다.
def getEdge (greyImg) : sX = np.array ([[0.25,0.5,0.25], [0,0,0], [-0.25, -0.5, -0.25]]) sY = np.array ([[0.25,0 , 0.25, -0.5,0], [0.5, -0.25,0], [0.25, -XNUMX]]) #edgeH = naiveConvolve (greyImg, sX) #edgeV = naiveConvolve (greyImg, sY) edgeH = fastConvolve (greyImg, sX) edgeV = fastConvolve (greyImg, sY) return np.sqrt (np.square (edgeH) + np.square (edgeV))
대박. 우리는 첫 번째 부분을 완료했습니다. 가장자리는 그림의 흥미로운 부분이고 검은 색 부분은 걱정없이 제거 할 수 있습니다.
픽셀 경로 식별 :
연속 경로의 경우 각 픽셀이 그 아래에있는 가장 가까운 3 개의 픽셀에만 연결되는 규칙을 정의 할 수 있습니다. 이것은 위에서 아래로 픽셀의 연속적인 경로를 갖는 것입니다. 따라서 우리의 하위 문제는 비용을 최소화해야하는 기본적인 길 찾기 문제가됩니다. 가장자리의 크기가 더 크기 때문에 가장 낮은 비용으로 픽셀 경로를 계속 제거하면 가장자리를 피할 수 있습니다.
함수를 정의합시다“비용" 픽셀을 가져와 거기에서 그림 끝까지 도달하는 최소 비용 픽셀 경로를 계산합니다. 다음과 같은 관찰이 있습니다.
- 맨 아래 행 (예 : i = r-1)
2. 중간 픽셀의 경우
암호:
def findCostArr (edgeImg) : r, c = edgeImg.shape cost = np.zeros (edgeImg.shape) cost [r-1 ,:] = edgeImg [r-1 ,:] for i in range (r-2,- 1, -1) : j 범위 (c) : c1, c2 = max (j-1,0), min (c, j + 2) cost [i] [j] = edgeImg [i] [j] + cost [i + 1, c1 : c2] .min () 반환 비용
음모:
플롯에서 삼각형 모양을 볼 수 있습니다. 즉, 해당 픽셀에 도달하면 가장자리를 통과하지 않는 바닥으로가는 경로가 없습니다. 그리고 그것이 우리가 피하려고하는 것입니다.
비용 매트릭스에서 픽셀 경로를 찾는 것은 탐욕스러운 알고리즘으로 쉽게 수행 할 수 있습니다. 맨 위 행에서 최소 비용 픽셀을 찾은 다음 연결된 모든 픽셀 중에서 비용이 가장 적은 픽셀을 선택하여 아래쪽으로 이동합니다.
def findSeam (cost) : r, c = cost.shape path = [] j = cost [0] .argmin () path.append (j) for i in range (r-1) : c1, c2 = max (j -1,0), min (c, j + 2) j = max (j-1,0) + cost [i + 1, c1 : c2] .argmin () path.append (j) 반환 경로
경로로 정의 된 이음새를 제거하려면 각 행을 통과하여 경로 배열에서 언급 한 열을 삭제하면됩니다.
def removeSeam (img, path) : r, c, _ = img.shape newImg = np.zeros ((r, c, 3)) for i, j in enumerate (path) : newImg [i, 0 : j ,: ] = img [i, 0 : j ,:] newImg [i, j : c-1 ,:] = img [i, j + 1 : c ,:] return newImg [:, :-1, :]. astype (np.int32)
그리고 그게 다입니다. 여기에서는 100 개의 솔기 조각 작업을 미리 계산했습니다.
우리는 그림 속의 물체들이 어떻게 서로 정말 가까워 졌는지 볼 수 있습니다. 우리는 물체에 왜곡을 일으키지 않고 솔기 조각 알고리즘을 사용하여 이미지의 크기를 성공적으로 줄였습니다. 전체 코드가 포함 된 노트북 링크를 첨부했습니다. 관심있는 독자는 살펴볼 수 있습니다 여기에서 지금 확인해 보세요..
전반적으로 Seam Carving은 재미있는 알고리즘입니다. 제공된 이미지에 세부 사항이 너무 많거나 가장자리가 너무 많으면 실패하므로주의해야합니다. 최종 결과가 무엇인지 확인하기 위해 알고리즘을 사용하여 다른 그림을 땜질하는 것은 항상 재미 있습니다. 의심이나 제안이 있으면 친절하게 답변에 남겨주세요. 끝까지 읽어 주셔서 감사합니다.
저자에 관하여
저는 컴퓨터 과학을 졸업하고 현재 소프트웨어 개발자로 일하고 있습니다. 나는 수학에 대한 깊은 사랑을 가지고 있습니다. 저는 수학의 새로운 개념과 컴퓨터 과학 및 기계 학습 분야의 응용 프로그램을 읽고 배우는 것을 좋아합니다.
모바일 APP에서이 기사를 읽을 수도 있습니다. 
