Feature Extraction Lecture 5 영상 분할

Region Segmentation 영상을 서도 다른 몇 개의 영역 (연결된 영역)으로 나누는 작업 ; 각 영역은 다음과 같은 면에서 동일한 성질을 갖는다 gray value color value(s) textural qualities local gradient motion shape info ..... etc.

Goal of Segmentation 영상을 의미 있는 장면 요소에 대응되는 영역들의 집합으로 나누는 작업 High Level Interpretations Objects Scene Elements Image Elements Raw Images

Primary Goal of Segmentation “Segmenting an image into image elements which may correspond to meaningful scene elements” 의미 있는 장면 요소에 대응되는 영상 요소는 ? 영상의 유형과 복잡도에 따라 답이 달라질 수 있음 : 제약 사항이 적은 장면에 대한 영상을 분할할 때는 좀 더 보수적인 입장에서 진행하여야 함 영상 분할은 잘 정의된 (well defined) 문제가 아님

Region Segmentation Example

Color Image Segmentation ? 명암 영상에 대한 영상 분할 방법과 유사한 방법으로 ? 명암 영상에 대한 영상 분할 방법은 ? 영역 분할을 위해 다음과 같은 영상 사용 가능 : R, G, B 채널의 컬러 영상 텍스쳐 영상 (textural images) 움직임 분석을 통해 얻어진 모션 벡터 영상 (displacement images) 3D 깊이 영상

Problems with Segmentation In general, high level contextual knowledge is required for successful segmentation

Formal Definition of Regions 영상 I 에 대한 영역 분할은 영상 I 에 속한 픽셀들을 K 개의 영역들의 집합 {Rj}, 1≤j≤K, 으로 다음과 같이 분할하는 과정 : K Ç 1. I = Rj Every pixel belongs to a region i=1 No pixel belongs to more than one region 2. Ri Ç Rj = Æ for i ≠ j 3. p connected to p’ for all p, p’ in Rj Spatial coherence 4. For some predicate P Feature coherence P(Ri) is TRUE for I = 1,2,…,K P(Ri Rj) is FALSE for Ri, Rj adjacent and i≠j Ç

Representing Regions 영역 차지 맵 (Region Occupancy Map) 영상에 대응되는 2차원 배열의 각 요소에 할당된 영역 레이블들의 집합 Image Occupancy Map or Label Plane

Contour Representation Image

Chain Code 영역의 경계선을 따라 시계 반대 방향으로 이동하며 생성되는 진행 방향에 대한 코드 : 영역의 경계선을 따라 시계 반대 방향으로 이동하며 생성되는 진행 방향에 대한 코드 : Direction Code

Chain Code CC = (i,j) {5 5 6 6 6 0 0 0 0 0 0 0 1 1 2 2 2 4 4 5 4 3 4 4}

Region Segmentation 기본 방법들 일반화된 이진화 (Generalized thresholding) 영역 확장 (Region growing) 영역 합병 (Region merging) 영역 분리 (Region splitting) 분리와 합병 (Split and Merge) K-평균 군집화 (K-means clustering) 분할 방법들 (Partitioning methods) 그룹화 방법들 (Grouping methods)

Partitioning Methods 분할 (Partitioning): Given : 데이터 집합 Goal : 데이터 간의 연관성에 기초하여 주어진 집합을 몇 개의 그룹으로 나누는 작업 예를 들어, 입력 영상을 균일한 색상 또는 균일한 텍스쳐를 갖는 영역들로 나누는 작업 ; 비디오 영상을 샷(shot – 동일한 시점에서 같은 장면에 대한 영상들) 단위로 나누는 작업 ; 비디오 영상을 균일한 모션 (coherent motion)을 갖는 프레임 단위로 나누는 작업 ;

Grouping Methods 그룹화 (Grouping) : Given : 데이터 집합 Goal : 유사한 성격의 데이터들을 모아 그룹을 형성하는 작업 예를 들어, 관심 물체의 형상이 만들어지도록 픽셀들을 모아서 물체 영역을 형성하는 작업 움직이는 물체에 해당되는 픽셀들을 모아 하나의 이동 물체 영역을 만드는 작업 컬러 또는 텍스쳐가 유사한 픽셀들을 모아 영역을 형성하는 작업

Region Segmentation 기본 기법 영역 합병 (Region Merging) START with many trivial regions (each pixel?) MERGE regions into larger regions based on some similarity criteria CONTINUE merging until no further merging is possible 영역 분리 (Region Splitting) START with a single large region (entire image?) SPLIT into several smaller regions based on a 'splitting' criterion CONTINUE until no further splitting is possible (regions are 'uniform')

Region Segmentation 기본 방법들 일반화된 이진화 (Generalized thresholding) Region growing Region merging Region splitting Split and Merge Extensions to split and merge K-means clustering

Generalized Thresholding RLP(i,j) = k if Tk-1 <= I(i,h) < Tk k = 1,...,m Tk = k번째 임계값 m = 임계값 갯수 RLP (Region Label Plane) = m 개 이상의 연결된 영역을 포함할 수 있음 임계값 Tk 가 적용되는 범위 : 전체 영상 I(I,j), GLOBAL THRESHOLDS 지역 영상 N(I,j) (local neighborhood), LOCAL THRESHOLDS 전체 영상 I(I,j) 와 지역 영상 N(i,j), DYNAMIC THRESHOLDS 이진화 작업을 수행하기 위해 m과 Tk 를 결정하여야 함 m - the number of thresholds, Tk - the threshold values.

Threshold Selection 수동으로 : 임의의 값 선택하여 결과 확인하는 과정 반복 히스토그램 분석에 의해 : 기본 전략 두 피크 P1 과 P2 사이의 최소값 위치 탐색 (search for minima between several peaks - multi-thresholding) 히스토그램에 2차 함수 곡선을 적합 Differentiate to find minimum 영상과 히스토그램에 대한 스무딩 작업 수행 Gray level g p(g) Threshold T P1 P2

Optimal Thresholding 히스토그램을 여러 개의 정규분포의 합으로 표현되는 확률분포 모델 (가우시안 혼합 모델, GMM)에 적합시킴 가우시안 혼합 모델의 지역적 최대값들 사이의 최소 확률값에 해당되는 밝기값을 임계값으로 설정 에러 확률 최소화하는 임계값 설정 방법 가우시안 혼합 모델의 매개변수 값들을 구해야 함 최적화 문제 (optimization problem) Probability distributions of backgrounds and object Corresponding histograms and optimal thresholds

Local or Adaptive Thresholding 밝기값이 조명의 영향을 받아 지역적 변화를 보일 수 있음 (for example)….e.g.: 일반적인 방법으로는 이진화 작업이 매우 어려움

Local or Adaptive Thresholding 각 픽셀이 서로 다른 임계값을 가질 필요가 있음 두 가지 기본 전략 Chow and Kaneka Adaptive Thresholding (1972) 영상을 작은 윈도우들의 집합으로 나누고, 각 작은 윈도우 안에서 히스토그램을 구성하여 임계값 결정 지역적 이진화 (Local Thresholding) 영상을 작은 윈도우들의 집합으로 나누고, 각 작은 윈도우 안에서 픽셀 값들의 통계 정보를 이용하여 임계값 결정 지역적 통계 정보 평균, 분산, 중간값 Mean of 7x7 neighborhood

Improved Results 임계값 = 평균 - C, where C is a constant. 이러한 통계 정보를 이용하면 윈도우 안의 픽셀들이 균일한 값을 갖는 경우, 이들은 모두 배경으로 설정된다 Mean 7x7 neighborhood; C=7 Mean 75x75 neighborhood; C=10 Median 7x7 neighborhood; C=4

Local Histogram Thresholding

Region Segmentation Basic Approaches Generalized thresholding 영역 확장 (Region growing) Region merging Region splitting Split and Merge Extensions to split and merge K-means clustering

Region Growing 목표 : 특정 픽셀을 기본 영역으로 하여 ‘눈사람 만들기’ 처럼 주변의 픽셀이 ‘유사성 기준’을 만족하면 현재 영역에 포함시키는 작업을 반복적으로 수행하여 영상 분할 작업 구현 유사한 특성을 갖는 픽셀들을 하나의 그룹으로 묶는 알고리즘 개략적 개념 다음의 두 조건이 만족되면 픽셀을 현재 영역 그룹에 포함 : 픽셀이 현재 영역에 인접하다 픽셀 값이 현재 영역의 픽셀 값들과 매우 유사하다 더 이상 현재 영역 그룹에 포함되는 픽셀이 없을 때까지 반복 영역 그룹에 포합되지 않은 다른 기본 픽셀을 선택하여 위의 과정 반복

Region Growing 영역 레이블 평면 (RLP)을 사용하여 구현 영상과 같은 크기의 RLP 사용 영상 픽셀이 영역에 포함되면 1, 포함되지 않으면 0 값을 할당 기본 영역을 나타내는 픽셀에 대응되는 RLP 요소 값을 1로 초기화 Image Region Label Plane

Similarity Criteria 픽셀을 현재 영역에 포함시키기 위한 유사성 측정은 어떻게 ? 개략적인 개념 특징값을 비교하여 개략적인 개념 모든 픽셀에 대해 아래 과정을 반복적으로 적용 IF RLP(i,j) = 0 AND RLP(i-n, j-m) = 1 for some n,m = -1 to 1 AND |I(i-n, j-m) - I(i,j)| < T (a predefined threshold) THEN RLP(i,j) = 1

Example: Simple Region Growing Seed Point T=16 T=32 T=64 T=128

Problems 유사성 비교를 위해 어떤 특징을 사용하나 ? 임계값을 어떻게 정하나 ? 알고리즘의 문제점은 ? 영역에 속하는 픽셀들이 점진적으로 또는 임의로 변하는 특징값을 가질 수 있다 영상 전체에 대해 하나의 고정된 임계값을 사용하는 것이 바람직한가 ? pixel sequence: p1,..., pk pj, pj+1neighbors | pj - pj+1| < T but | p1 - pk| > T pk p1

Region Segmentation Basic Approaches Generalized thresholding Region growing 영역 합병 (Region merging) Region splitting Split and Merge Extensions to split and merge K-means clustering

Region Merging 영역간 거리 척도에 대한 정의 일반적으로 : dij = D(Ri, Rj) > 0 D는 특징 공간에서의 거리 척도이며, 영역 Ri 와 Rj 의 특징 벡터들로 구성되는 함수로 표현된다 dij = D(fi, fj) > 0 거리가 최소인 두 영역을 합병 적절한 종료 조건이 필요함

Example Distance Measures 컬러 평균값 간의 거리 척도 영역 중심점 간의 거리 척도 두 척도의 가중 합 Nm 은 영역 Rm 에 속한 픽셀 수 Ni 2 Nj 2 cij = |mi - mnew| + |mj - mnew| Nnew Nnew rij = Ni Nnew Nj |ri - rnew| 2 |rj - rnew| + dij = a cij + b rij

Region Merging Define a distance measure dij = D(f(Ri), f(Rj)) >0 Algorithm: { While termination condition false Determine the minimum distance regions {i*, j*} = arg min dij Merge the minimum distance regions Ri* ¬ Ri* U Rj* Remove merged region from region list L ¬ L-{Rj*} Compute termination condition } Ri, Rj Î L

Merging Hierarchy 알고리즘 진행 과정은 이진 트리 표현 합병 종료는 최소 거리가 임계값을 초과하는 경우 d i*,j* > T stop merging 임계값에 의해 영역 합병 결과가 달라질 수 있음

Fisher’s Criterion 평균과 분산은 병합을 위해 자주 사용되는 특징 특히, 데이터 분포가 가우시안 분포일 때 매우 유용 가우시안 분포의 피크는 평균에서 발생 피크값 = (1 / 2ps2) 분포의 합이 1이 되도록 정규화 영역에 속한 픽셀 값의 히스토그램을 확률 분포로 활용 히스토그램에서 평균 m과 분산 n 를 계산 분산 n 는 분포가 얼마나 편평한가를 나타냄 s = sqrt (n) is the standard deviation 1/2

Histogram Model

Fisher’s Criterion 두 영역이 얼마나 다른가를 나타내는 Fischer’s criterion : m1 - m2 l is a threshold 두 영역이 평균에 있어서 큰 차이를 보이고 분산의 차이가 적으면, 두 영역을 합병하지 않고 분리 m1 - m2 n1 - n2 2 > l

Uniformity 두 인접 영역의 합병을 위한 임계값 l 는 합병된 영역의 균일도 (uniformity)를 계산하여 결정 균일도 낮으면 임계값을 낮추는 전략 평균과 분산값을 이용한 균일도 정의 균일도 = 1 - n / m 균일도에 비례하여 임계값 l 설정 l = (1 - n / m ) l0 User need supply only one threshold l0

Region Segmentation Basic Approaches Generalized thresholding Region growing Region merging 영역 분리 (Region splitting) Split and Merge Extensions to split and merge K-means clustering

Region Splitting 영역 분리 (Region Splitting) : (1) 하나의 큰 영역에서 시작 (initially, entire image) (2) 재귀적으로 작은 영역들로 분리 (3) 각 영역이 균일해질 때까지 분리 (no further splits are possible) A simple approach: Global Thresholding Define a global threshold T Apply to every pixel in the image I: RLP(i,j) = 0 if I(i,j) < T RLP(i,j) = 1 if I(i,j) ≥ T

Region Splitting

Example: Region Splitting

Region Segmentation Basic Approaches Generalized thresholding Region growing Region merging Region splitting 분리 및 합병 (Split and Merge) Extensions to split and merge K-means clustering

Hybrid Technique Split and Merge combination: splits followed by merges (or vice-versa) split and merge decisions can be either local: a pixel and its immediate neighbors a region and its immediate neighbors global: on the basis of a large number of pixels scattered throughout the image

Split and Merge 개략적인 개념: 영역 인접 그래프 (region adjacency graph) 자료구조를 사용 R 임의의 영역을 4진 트리 (quadtree) 평면으로 분할 Initial decomposition = entire image ? 각 영역이 균일도 조건을 만족하지 못하면 4진 트리 자식을 가짐 인접 영역이 합병을 위한 균일도 조건을 만족하면 재귀적으로 합병 영역 인접 그래프 (region adjacency graph) 자료구조를 사용 R R1 R2 R3 R4 R41 R42 R43 R44 R1 R2 R3 R41 R42 R43 R44

Split and Merge Example

Region Segmentation Basic Approaches Generalized thresholding Region growing Region merging Region splitting Split and Merge Extensions to split and merge K-평균 군집화 (K-means clustering)

Segmentation by k-means clustering 데이터가 K 개의 군집을 갖는다고 가정 (k is known) 각 군집의 중심은 (center) ci 군집의 jth 원소를 특징벡터 xj 로 표현 For scattered points, x would be coordinate(s) For an intensity image, x might be the intensity at a pixel 군집이 얼마나 좋은가를 나타내는 목적함수 (objective function) 를 정의 목적함수를 최대화하는 알고리즘 개발

Objective Function & Algorithm 군집의 요소들은 군집의 중심에 모여있다고 가정 One possible objective function is 다음 과정을 반복하는 알고리즘 설계 군집의 중심을 알고 있다고 가정하고 각 데이터를 군집에 할당 각 데이터가 군집에 할당되었다고 가정하고 군집의 중심 계산

k-means algorithm Choose k data points to act as cluster centers Random selection First k data points Until the cluster centers are unchanged Allocate each data point to cluster whose center is nearest Now ensure that every cluster has at least one data point; possible techniques for doing this include: supplying empty clusters with a point chosen at random from points far from their cluster center. Replace the cluster centers with the mean of the elements in their clusters. end Apply connected components algorithm to generate regions

k-means Clustering

k-means Clustering

k-means Clustering

k-means Clustering

k-means Clustering

k-means Clustering

k-means Clustering

k-means Clustering

Example Assume k=5 각 픽셀 값을 픽셀이 속하는 군집의 평균값으로 표시하였음 연결 요소 찾기 알고리즘 (connected components algorithm)을 적용하여 연결된 영역들을 확인 K=5 Original Image k-means on intensity k-means on color

Other Distance Measures 영역이 조밀한 (compact) 형태를 갖기 원하는 경우 특징 공간 : 5D (2 spatial coordinates, 3 color components) 컬러와 공간 인접성 측면에서 픽셀들이 근접한 가를 평가 유클리디안 거리 (Euclidean distance)의 문제점은 ? 공간 좌표값의 범위가 0-1000 이고 컬러값의 범위는 0-255 인 경우에는 ? 특징값의 크기(scale)가 다른 경우에는 각 특징에 다른 가중치를 할당 가중치가 부여된 유클리디안 거리 : 각 특징의 중요도를 고려하여 가중치 조절 가능 S

Hybrid Edge-Region Approaches 영역 합병과 비슷한 개념 — 과분할 (over-segmented) 영상에서 출발 에지 검출 정보를 함께 사용 두 영역간의 약한 경계 (weak boundaries) 정보에 기초하여 영역 합병 수행 공유하는 경계에 임계값 이하의 약간 에지가 얼마나 있는가를 기준으로 영역 합병 수행 에지에 기초한 영상 분할 방법의 후처리 과정으로 사용되기도 함

Region Features 영역의 특성을 나타내기 위한 특징 물체 인식과 같은 작업을 수행하는데 사용됨 Example features: area, height, and width perimeter, bounding box, area of bounding box centroid orientation compactness moments .....etc.

Region Features Basics Rotation/translation/scale invariant Perimeter Area Orientation Rotation/translation/scale invariant Compactness = perimeter2/area Rectangularity = AreaRect/AreaObject (next slide) Euler number = #regions - #holes

Rectangularity W and L are a function of q Rectangularity = WxL/A Choose q to get WxL minimum Called the ‘minimum bounding rectangle’ Minimized for rectangular objects W L q A

Perimeter P = number of pixels on boundary Region plane P = number of pixels on boundary P = number of horizontal steps + number of vertical steps + 2 x number of diagonal steps or

S S S S S S Moments Centroid: center of mass Higher order moments Note: A = m00 ; r = m10 / m00 ; c = m01 / m00 ; r = r I(r,c) 1 A S S r c c = c I(r,c) 1 A S S r c mpq = r c I(r,c) S S r c p q

S S Central Moments Moments around the center of mass Note that A = u00 ; u01 = 0; u10 = 0 Higher order (2nd order and higher) moments are used heavily in oject recognition upq = (r-r) (c-c) I(r,c) S S r c p q

Orientation Let q be the region orientation with respect to the horizontal axis Can be shown that q tan 2q = 2m11 m20 - m02

Next Topic Next: Stereo Vision