심 조각

Seam carving
더 좁게 만들 원본 이미지
성이 일그러졌기 때문에 스케일링은 바람직하지 않다.
성 일부를 제거하기 때문에 자르는 것은 바람직하지 않다.
심 조각

Sem carving(또는 액상 리스케일링)은 미쓰비시 전기연구소(MERL)의 샤이 아비단(Shai Avidan)과 학제간 센터와 MERL의 아리엘 샤미르(Ariel Shamir)가 개발한 콘텐츠 인식 이미지 크기 조정 알고리즘이다. 이미지에 여러 개의 솔기(중요도가 가장 낮은 경로)를 설정해 기능하며 솔기를 자동으로 제거해 이미지 크기를 줄이거나 솔기를 삽입해 확장한다. 또한 심 조각은 픽셀이 수정되지 않는 영역을 수동으로 정의할 수 있으며 사진에서 전체 물체를 제거하는 기능을 특징으로 한다.

알고리즘의 목적은 이미지 리타겟팅(image retargeting)인데, HTML처럼 문서 표준을 사용하여 다양한 크기의 매체(휴대폰, 투영 화면)에 왜곡 없이 영상을 표시하는 문제로서 이미 페이지 레이아웃과 텍스트의 동적 변경을 지원하지만 이미지는 지원하지 않는 문제가 있다.[1]

이미지 리타겟팅은 2005년 비드야 세틀루르, 사에코 다카게, 라메쉬 라스카르, 마이클 글리처, 브루스 고흐에 의해 발명되었다.[2] 세틀루르 등의 작품은 2015년 10년 임팩트상을 수상했다.

솔즈

솔기는 수직 또는 수평이 될 수 있다. 수직 심은 각 행에 하나의 픽셀이 있는 영상에서 위에서 아래로 연결된 픽셀의 경로다.[1] 수평 심은 연결부가 왼쪽에서 오른쪽으로 있다는 점을 제외하면 유사하다. 중요도/에너지 함수는 픽셀의 인접 픽셀과의 대비를 측정하여 픽셀 값을 매긴다.

과정

다음 예제는 솔기를 조각하는 과정을 설명한다.

스텝 이미지
1) 이미지로 시작한다.
Starting image
2) 각 픽셀의 중량/밀도/에너지를 계산한다. 이것은 그라데이션 크기, 엔트로피, 시각적 편의성, 안구 운동과 같은 다양한 알고리즘에 의해 수행될 수 있다.[1] 여기서는 경사로 크기를 사용한다.
gradient magnitude energy
3) 기운에서 솔기목록을 만든다. 솔기는 에너지에 따라 순위가 매겨지는데, 낮은 에너지 솔기는 이미지의 내용에 가장 중요하지 않다. 심은 아래의 동적 프로그래밍 접근방식을 통해 계산할 수 있다.
seams with energy
4) 필요에 따라 저에너지 솔기를 제거한다.
reduced energy image
5) 최종 이미지.
final image

제거할 솔기는 축소하고자 하는 치수(높이 또는 너비)에 따라서만 달라진다. 낮은 에너지 심을 복사해 주변 픽셀을 평균화함으로써 알고리즘이 한 차원 커지도록 4단계를 반전시키는 것도 가능하다.[1]

컴퓨터 솔기

심을 계산하는 것은 이미지의 한쪽 끝에서 다른 쪽 끝으로 가는 최소 에너지 비용의 경로를 찾는 것으로 구성된다. 이것은 Dijkstra의 알고리즘, 동적 프로그래밍, 탐욕스러운 알고리즘 또는 그래프 컷을 통해 이루어질 수 있다.[1]

동적 프로그래밍

동적 프로그래밍은 보다 복잡한 결과 계산을 단순화하기 위해 하위 계산 결과를 저장하는 프로그래밍 방법이다. 동적 프로그래밍은 심을 계산하는 데 사용될 수 있다. 가장 낮은 에너지의 수직 심(경로)을 계산하려고 하면, 연속된 각 픽셀에 대해 현재 픽셀의 에너지와 그 위의 가능한 픽셀 중 하나의 에너지를 계산한다.

아래 이미지는 하나의 최적의 심을 계산하기 위한 DP 과정을 묘사한다.[1] 각 사각형은 픽셀을 나타내며, 왼쪽 위 값은 해당 픽셀의 에너지 값을 나타내는 빨간색이다. 검은색으로 표시된 값은 픽셀까지 이어지는 에너지의 누적 합계를 나타낸다.

  • 맨 위 행은 그 위에 아무것도 없으므로 에너지는 소스 이미지와 동일하다.

  • 나머지 행의 각 픽셀에 대해 에너지는 자체 에너지와 위의 세 에너지 중 최소 에너지다. 바닥에 닿을 때까지 반복한다.

  • 마지막에 가지고 있는 가장 낮은 에너지의 경우 최소의 에너지를 최소의 에너지로 심을 복구하기 위해 최소의 에너지를 백업하십시오.

에너지 계산은 간단한 기능에 대해 사소한 유사점이다. 또한 DP 어레이의 계산은 일부 프로세스 간 통신과 병행될 수 있다. 그러나 동시에 여러 개의 솔기를 만드는 문제는 두 가지 이유로 더 어렵다. 즉, 정확하게 하기 위해서는 제거될 때마다 에너지를 재생해야 하고 단순히 여러 솔기를 추적하면 중복이 생길 수 있다는 것이다. Avidan 2007은 각 솔기를 반복적으로 제거하고 생성된 솔기를 기록하기 위한 "인덱스 맵"을 저장함으로써 모든 솔기를 계산한다. 지도에는 영상의 각 픽셀에 대해 "nth seam" 번호가 표시되며, 나중에 크기 조절에 사용할 수 있다.[1]

그러나 두 가지 문제를 모두 무시할 경우 평행심 조각에 대한 탐욕스러운 근사치가 가능하다. 이를 위해 한 쪽 끝에는 최소 에너지 픽셀이 있고 다른 쪽 끝에는 최소 에너지 경로를 계속 선택한다. 사용한 픽셀은 다시 고르지 않도록 표시한다.[3] 국소 심도 좋은 근사치를 위해 영상의 작은 부분에 대해 병렬로 계산할 수 있다.[4]

문제들

  1. 알고리즘은 오류를 줄이기 위해 사용자가 제공한 정보를 필요로 할 수 있다. 이것은 보존할 지역에 페인팅을 하는 것으로 구성될 수 있다. 사람의 얼굴을 사용하면 얼굴 탐지가 가능하다.
  2. 때때로 알고리즘은 낮은 에너지 심을 제거함으로써 실수로 더 높은 에너지의 심을 만들기도 한다. 이에 대한 해결책은 솔기 제거를 시뮬레이션한 다음 에너지 델타를 점검하여 에너지가 증가하는지(전방에너지) 확인하는 것이다. 만약 그렇다면, 대신 다른 솔기를 선호해라.[5]

구현

ImageMagick의 리퀴드 스케일 기능을 사용하여 심판을 시연하는 대화형 SVG SVG 파일에서 백분율 위로 마우스를 올려서 원본 이미지를 비교하고(상단), 그 너비를 심 이동(중간)을 사용하여 백분율로 재조정하고 보간(하단)을 사용하여 동일한 크기로 재조정하십시오.
ImageMagick의 리퀴드 스케일 기능을 사용하여 심판을 시연하는 대화형 SVG SVG 파일에서 위와 같이 백분율 위로 마우스를 이동하십시오. 얼굴이 주변보다 덜 영향을 받는다는 점에 유의하십시오.

어도비 시스템즈는 MERL로부터 솔기 조각 기술에 대한 비독점적 라이센스를 취득하여 포토샵 CS4의 기능으로 구현하였는데,[6] 이를 콘텐츠 인식 스케일링이라고 한다.[7] 라이선스가 비독점적이기 때문에, 다른 인기 있는 컴퓨터 그래픽 어플리케이션들, 그중에는 KIMP, digiKam, ImageMagick, 그리고 일부 독립형 프로그램들, 그 중에는 iResizer도 이 기법의 구현을 가지고 있으며,[8] 그 중 일부는 무료 및 오픈 소스 소프트웨어로 출시된다.[9][10][11]

개선 및 확장

  • 2D(time+1D) 솔기를 도입하여 에너지 기능과 비디오 활용도를 개선하십시오.[5]
    • GPU에서 더 빠른 구현.[4]
    • 정적 영상에 이 정방향 에너지 기능의 적용.[12]
  • 다중 연산자: 자르기 및 스케일링과 결합하십시오.[13]
  • 여러 솔기를[14] 훨씬 더 빠르게 제거

2010년 8가지 이미지 리타겟팅 방법을 검토한 결과, 심 조각이 테스트한 알고리즘 중 가장 나쁜 알고리즘에 속하는 출력을 생성하는 것으로 나타났다. 그러나, 그것은 위에서 언급한 다중 연산자 확장(자르기 및 스케일링과 결합)의 일부였다.[15]

참고 항목

참조

  1. ^ Jump up to: a b c d e f g Avidan, Shai; Shamir, Ariel (July 2007). "Seam carving for content-aware image resizing ACM SIGGRAPH 2007 papers". SIGGRAPH 2007: 10. doi:10.1145/1275808.1276390.
  2. ^ Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher and Bruce Gooch (December 2005). "Automatic image retargeting". MUM '05: Proceedings of the 4th International Conference on Mobile and Ubiquitous Multimedia: 59–68. doi:10.1145/1149488.1149499. ISBN 0473106582.CS1 maint: 작성자 매개변수 사용(링크)
  3. ^ Bist; Palakkode (2016). "Parallel Seam Carving". www.andrew.cmu.edu.
  4. ^ Jump up to: a b Chen-Kuo Chiang; Shu-Fan Wang; Yi-Ling Chen; Shang-Hong Lai (November 2009). "Fast JND-Based Video Carving With GPU Acceleration for Real-Time Video Retargeting". IEEE Transactions on Circuits and Systems for Video Technology. 19 (11): 1588–1597. doi:10.1109/TCSVT.2009.2031462.
  5. ^ Jump up to: a b 비디오 리타깃을 위한 심 조각 개선. 마이클 루빈스타인, 아리엘 샤미르, 샤이 아비단. 시그그래프 2008.
  6. ^ 2008년 12월 16일 미쓰비시 전기 보도 자료, 비즈니스 와이어.
  7. ^ Adobe Photoshop CS4의 새로운 기능 목록.
  8. ^ Teorex에서 소프트웨어 크기를 조정하는 iResizer 컨텐츠 인식 이미지
  9. ^ Liquid Rescale, KIMP용 심 조각 플러그인
  10. ^ digiKam 포함 발표
  11. ^ ImageMagick에 포함된 심기 조각 기능
  12. ^ https://avikdas.com/2019/07/29/improved-seam-carving-with-forward-energy.html
  13. ^ 멀티 오퍼레이터 미디어 대상 변경. 마이클 루빈스타인, 아리엘 샤미르, 샤이 아비단. SIGGRAPH 2009.
  14. ^ Science in China Series F: Information Sciences, 2009 Science IN China PRESS의 크기를 조정하는 실시간 콘텐츠 인식 이미지. 2011년 7월 7일 웨이백 머신에 보관
  15. ^ Rubinstein, Michael; Gutierrez, Diego; Sorkine, Olga; Shamir, Ariel (2010). "A Comparative Study of Image Retargeting" (PDF). ACM Transactions on Graphics. 29 (5): 1–10. doi:10.1145/1882261.1866186. RetargetMe 벤치마크를 참조하십시오.

외부 링크