[CV] Seam Carving for Content-Aware Image Resizing

Date: 2022.10.04 Updated: 2022.10.04

카테고리: Vision

태그: CS

Main Reference:
- CONTENT-AWARE IMAGE RESIZING - TREKHLEB

📹 Seam carving

Original	Content-aware	standard

Seam carving algorithm의 mian idea는 이미지를 resize할 때 단순 비율로 resize하는 것이 아니라 interesting contents 부분을 보존하며 resize하자는 것이다. 위 그림은 636x437 이미지에서 높이 방향 50 픽셀을 제거한 그림이다. 오른쪽 두 그림 중 첫 번째는 seam carving algorithm을 이용한 contetn-aware resize, 두 번째는 standard resize한 것이다. Content-aware resize한 그림을 보면 contents인 산은 변화가 없고 배경 부분만 잘려 나간 것처럼 보인다.

Seam carving algorithm은 간단하게 다음 단계로 구성된다.

Compute energy map of iamge
- image의 energy map 구하기
Find the seam with the lowest energy based on energy map (with dynamic programming)
- energy map을 기반으로 가장 효율적인 경로 구하기
Remove the seam from the image
- image에서 찾은 경로 제거
Repeat until the image width is reduced to the desired value.
- 필요한 만큼 위 과정을 반복

Compute energy map of iamge

energy_map

\[dx = \begin{bmatrix} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \\ \end{bmatrix} \textbf{ , } dy = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \\ \end{bmatrix}\] \[\textbf{Energy}\left ( \textbf{f} \right ) = \sqrt{\left ( \frac{\partial f}{\partial x} \right )^{2} + \left ( \frac{\partial f}{\partial y} \right )^{2}}\]

rgb 이미지를 gray 이미지로 변환
sobel operator를 이용해 dx & dy 계산
energy map 구하기

Find the seam with the lowest energy based on energy map (with dynamic programming)

cumulate_map

\[\textbf{M}\left ( i, j \right ) = \textbf{Energy}\left ( i, j \right ) + min\left ( \textbf{M}\left ( i-1, j-1 \right ), \textbf{M}\left ( i-1, j \right ), \textbf{M}\left ( i-1, j+1 \right ) \right )\]

주어진 Energy map을 기반으로 cumulative minimum energy map 계산
- 세로 픽셀 줄일 때에는 위에서 아래로 cumulate
- 가로 픽셀 줄일 대에는 왼쪽에서 오른쪽으로 cumulate
마지막 row(column)에서 가장 작은 energy 경로 backtracking

seam