[컴퓨터비전] 5. 영상 분할

5.1 영상분할의 원리

• 영상 분할: 입력 영상 f(x,y)를 서로 겹치지 않는 영역 R1,R2,…,Rn으로 나누는 것.
• 수학적 조건:
• 좋은 분할 조건:

5.2 전통적 방법

1. 임계화를 이용한 영역 분할

• 영상의 히스토그램을 기준으로 임계값 설정 후 이진화
• 단일 임계값: 오츄 알고리즘
• 다중 임계값: 여러 밝기 구간을 나누어 여러 객체 분리 (이중 임계값 오츄 알고리즘)
• 한계: 복잡한 배경/조명 변화에 취약

2. 군집화를 이용한 영역 분할

• RGB 컬러공간에 화소를 3D 좌표로 매핑 → 군집화로 분할
• 대표적 알고리즘: k-means

3. 분할합병 (Split & Merge)

• 4분 트리(quadtree) 구조로 영상 분할
• 규칙 $Q(r_i)$에 따라 균일하지 않으면 분할, 균일하면 단말 노드로 유지
• 이후 비슷한 영역끼리 다시 합병
• 장점: 구조가 간단하고 이해 쉬움

5.3 그래프 방법

정규화 절단을 이용한 영상 분할

• 영상 → 그래프 $G = (V, E)$ 로 모델링

Wu의 방법

• 유사도 기반 거리 정의:
• 그래프 분할 기준 함수:
• 문제점:

Shi의 방법

• 기존 cut 함수의 한계 인식:
• Normalized Cut (ncut) 함수 정의:

• 장점:

고유벡터 기반 수치적 해법

• 고유값 문제로 변환:
• 해석적 의미:

알고리즘 : 정규화 절단을 이용한 영상 분할

• 입력: 영상 $f(i)$, $0 \leq i \leq M-1$, $0 \leq i \leq N-1$
• 출력: 분할 결과 $S = \{C_1, C_2, ..., C_k\}$ // $C_i$는 연결요소

1. 전체 노드 집합 $V$를 하나의 연결요소 $C$라고 간주
2. $C$의 유사도 행렬 $W$를 계산한다
3. 고유벡터 계산을 위한 행렬 $A$를 구성하고, 고유벡터를 구한다
4. 두 번째 작은 고유값에 해당하는 고유 벡터를 이용하여 $C$를 $C_1, C_2$로 분할
5. $C_1, C_2$ 각각에 대해 추가 분할이 필요한지 판단하고, 그렇다면 2~5를 반복

유사도 정의

• 유사도 함수: 화소 간의 유사도는 특징값과 위치값을 함께 고려해 정의

• 의미:

결과 예시

• 아기 얼굴 영상에 정규화 절단 적용

5.4 민시프트

• 모드 탐색 기반 비모수적 클러스터링
• 커널 밀도 추정 → 확률 밀도 함수의 최대 지점(모드) 탐색
• 핵심: 반복적으로 데이터 중심을 평균 방향으로 이동
• 장점:
• 영상 분할 방식:
• 수렴 조건:
• 응용:

5.5 워터셰드

• 지형 지도를 모델로 한 분할 알고리즘
• 각 픽셀을 고도(=에지 강도)로 생각 → 저지대(지역 최소점)부터 물 채우듯 확장
• 유역(basin): 물이 모이는 영역 → 분할 단위
• 워터셰드(watershed): 서로 다른 유역이 만나는 경계 → 객체 경계
• 기본 알고리즘:
• 장점: 항상 폐곡선(닫힌 경계) 생성

5.6 대화식 물체 분할

• 사용자의 입력을 바탕으로 관심 있는 물체만 정확하게 분할하는 방식
• 기존의 전체 영상 분할과 달리, 관심 대상의 명확한 분할에 초점을 맞춤
• 물체/배경 분할에 활용됨

대표적 알고리즘

1. 스네이크 (Snake, 능동 외곽선)

• 초기 곡선을 설정하고, 외곽선이 물체 경계에 수렴하도록 에너지를 최소화
• 전체 에너지 구성: $E = E_{\text{internal}} + E_{\text{image}} + E_{\text{constraint}}$
• 내부 에너지: 곡선의 매끄러움 유지
• 영상 에너지: 엣지 강도 기반 경계 탐색
• 제약 에너지: 외부 지식 기반 제약 조건 반영
• 수식 기반의 연속적 곡선 표현 → 디지털 영상에선 근사적으로 계산 필요

2. 그래프 컷 (Graph Cut)

• 영상을 그래프로 모델링하고 최소 컷(min-cut)을 통해 분할 수행
• 각 화소를 노드로 표현하고, 이웃 화소 간 유사도(엣지 가중치)로 연결
• t-link: 물체/배경과의 연결 가중치
• n-link: 인접 화소 간의 유사도
• 최적화 방식:
• 다양한 분할 문제에 일반적으로 사용됨

3. 지능 가위 (Intelligent Scissors)

• 사용자가 마우스로 대략적인 경로를 지정하면 최단 경로 기반 실시간 경계 추적
• 경계 강조된 에지 정보를 바탕으로 시각적 피드백 제공
• GIMP 등 오픈 소스 편집기에서 제공되는 기능

4. 레벨 셋 (Level Set)

• 곡선을 명시적으로 표현하지 않고 암시적인 등고선 함수(ϕ)로 표현
• 복잡한 형상의 경계 표현 가능 (예: 분리된 섬 형태, 다공성 구조)
• 곡선의 위상 변화 자동 처리 (구멍, 분할, 병합 등)
• 수학적 정밀도 높지만 계산 비용이 큼

5. GrabCut

• 2004년 SIGGRAPH 논문에서 발표된 강력한 대화식 분할 방식
• 초기 사각형 또는 루프를 입력 → GMM 기반의 그래프 컷 에너지 최적화
• 반복적으로 GMM 업데이트와 최소 컷을 수행하여 경계를 정밀화
• OpenCV에서 함수로 제공되어 활용 쉬움

주요 응용

• 이미지 편집: 배경 제거, 사진 합성
• 의료 영상: 장기 분할, 병변 추출
• 증강 현실(AR): 인물/사물 추출 및 실시간 합성
• 객체 추적: 사용자의 초기 선택 후 자동 추적 기반 물체 인식
• 텍스트 인식, 장면 해석 등 다양한 비전 문제에 활용

5.7 알고리즘 선택

• 영상 성격, 응용 목적, 계산 자원에 따라 적절한 알고리즘 선택 필요