Computer Vision & Pattern Recognition Lab. 제 9 장영상인식 Computer Vision & Pattern Recognition Lab.
영상인식 Computer Vision & Pattern Recognition Lab. 2 /26
영상인식 일반적인영상인식은매우어려운문제임 제한된환경, 여러가지가정하에서수행 영상의종류를알경우 : 얼굴, 문자, 지문, 번호판, 배경이단순하다고가정 실내와같이제한된환경일경우 객체의 texture가단순하다고가정 물체의겹침이없다고가정 Computer Vision & Pattern Recognition Lab. 3 /26
영상인식의과정 Image Low-level processing Intermediate-level processing high-level processing 인식 Low-level processing: 전처리 (eg: Contrast 개선, 잡음제거 ) Intermediate-level processing: 영상분할, 특징추출 High-level processing: 영상인식 (eg: 얼굴인식, 문자인식 ) 전처리 --> 영상분할 --> 특징추출 --> 인식 Computer Vision & Pattern Recognition Lab. 4 /26
[1] 영상분할 (Image Segmentation) 목표 : 영상에존재하는서로다른영역들을구분 ( 예 : 영역별로서로다른번호가할당됨 ) 수행방법 : 이진화 + Connected Component Labeling Computer Vision & Pattern Recognition Lab. 5 /26
이진화 (Thresholding) 영상분할을위한이진화 (Thresholding) 물체와배경을분리 Computer Vision & Pattern Recognition Lab. 6 /26
최적의 Threshold 값의결정방법 T=165 Computer Vision & Pattern Recognition Lab. 7 /26
(1) Global thresholding ( Manual thresholding ) -. 주어진 threshold 값을영상전체에적용 -. 환경의제어가용이한경우에가능 ( 예 : industrial inspection) (2) P-tile thresholding -. 밝기값 0 부터의히스토그램값을더한것이전체화소의 P% 가되는지점을계산 -. Find T such that NxNy * P = 100 T i 0 H(i) -. 전체영상에서물체가차지하는면적이일정한경우 ( 예 : 지문인식 ) Computer Vision & Pattern Recognition Lab. 8 /26
(3) Otsu ( Minimum within-group variance ) 가정 : - 물체와배경이 Bimodal 히스토그램 - 하나의물체는밝기값이거의같음 ( 즉, 밝기값의 variance가작음. 무늬가없음 ) t Computer Vision & Pattern Recognition Lab. 9 /26
Otsu 방법의알고리즘 (1) 영상의히스토그램 H(i) 를계산함. (2) t = 0 부터 255 까지모든 t 값에대해서 (2.1) 왼쪽과오른쪽의평균을각각계산함. 1 (t) = t i H(i) i =0 t H(i) i =0 2 (t) = I i H(i) i = t+1 I H(i) i =t+1 t (2.2) 왼쪽분산값과오른쪽분산값의합을계산함. 2 (t) = t [ i 1 (t) ] 2 H(i) i =0 t H(i) i =0 (3) 2 (t) 값이최소가되는 t 값을구함. + I [ i 2 (t) ] 2 H(i) i=t+1 I H(i) i =t+1 Computer Vision & Pattern Recognition Lab. 10 /26
조명에관계없이배경과물체를정확히분리 Computer Vision & Pattern Recognition Lab. 11 /26
Connected component labeling 목표 : 주어진이진영상에대해서, 연결된영역들에서로다른숫자를할당함. ( 연결성의판별 : 4-connected, 8-connected) Algorithm (4-connected 의경우 ) 1) Scan the image left to right, top to bottom 2) For each non-zero pixel, look at top and left If they are zero, assign a new label to the current pixel If one of them is non-zero, assign that label If both are non-zero, assign any label and write down the equivalence 3) Relabel using equivalence. Computer Vision & Pattern Recognition Lab. 12 /26
Labeling 의과정 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 2 2 0 0 3 1 1 0 2 2 0 0 0 0 0 0 0 0 0 3 = 1 0 0 0 0 0 0 0 0 0 0 1 1 0 2 2 0 0 1 1 1 0 2 2 0 0 0 0 0 0 0 0 0 Computer Vision & Pattern Recognition Lab. 13 /26
Segmentation 의결과 Computer Vision & Pattern Recognition Lab. 14 /26
[2] 특징추출 (Feature Extraction) 목표 : 분할된각영역에대한특징값들을정량적으로추출 결과 : 각영역별로특징값이벡터의형태로표현됨 Issues: 어떠한특징값 ( 면적, 둘레, 평균밝기, 등 ) 을사용할것인가? 특징값의 T, R, S invariance Computer Vision & Pattern Recognition Lab. 15 /26
(1) Boundary-based features -. Boundary length = Number of pixels at bndry -. Diameter = Max [ D(P i, P j ) ], Pi, Pj : boundary pixels -. Major axis = line segment joining 2 pts farthest from each other -. Minor axis = perpendicular to major axis -. Eccentricity = Major axis 길이 / Minor axis 길이 Computer Vision & Pattern Recognition Lab. 16 /26
(2) Region-based features -. Area = f(x,y), f(x,y) is binary image -. Compactness = Perimeter 2 / Area (T, R, S, invariant) -. Mean gray level -. Min. gray level -. Max. gray level -. Number of pixels above mean -. Variance of gray level -. Elongation Computer Vision & Pattern Recognition Lab. 17 /26
(3) Moment-based features Moment of order (p+g): m pq = f(x,y) x p y q Central moment: pq = f(x,y) (x-x) p (y-y) q, x = m 10 / m 00, y = m 01 / m 00 * Central moment is translation invariant! -. Area = m 00 -. Centroid : x = m 10 / m 00, y = m 01 / m 00 -. Orientation : = tan -1 [ 2 11 / ( 20 02 ) ] 1 2 Computer Vision & Pattern Recognition Lab. 18 /26
-. Bounding rectangle l = max min, = x cos + y sin ( : orientation) w = max min, = -x sin + y cos boundary(x,y) -. Best fit ellipse 1/4 1/8 1/4 1/8 I 3 max I min a = 4, b= I max = [ ( x- x ) cos + ( y- y ) sin ] 2 I min = [ - ( x- x ) sin + ( y- y ) cos ] 2 4 I 3 min I max ( 20-02 ) 2 +4 11 -. Eccentricity = m 00 Computer Vision & Pattern Recognition Lab. 19 /26
Normalized Central moment : pq = pq / r 00, r = (p+q)/2 +1, p+q = 2,3,... * Normalized central moment is Translation, Scaling invariant! Invariant moments : Moments which are invariant to T, R, S ==> Useful features for object recognition (1) 1 = 20 + 02 (2) 2 = ( 20-02 ) 2 + 4 2 11 (3) 3 = ( 30-3 12 ) 2 + ( 3 21-03 ) 2 (4) 4 = ( 30 + 12 ) 2 + ( 21 + 03 ) 2 (5) 5 = ( 30-3 12 ) ( 30 + 12 )[ ( 30 + 12 ) 2-3( 21 + 03 ) 2 ] + ( 3 21-03 ) ( 21 + 03 )[3( 30 + 12 ) 2 - ( 21 + 03 ) 2 ] (6) 6 = ( 20-02 )[( 30 + 12 ) 2 - ( 21 + 03 ) 2 ] + 4 11 ( 30 + 12 ) ( 21 + 03 ) (7) 7 = ( 3 21-30 ) ( 30 + 12 )[( 30 + 12 ) 2-3( 21 + 03 ) 2 ] + ( 3 12-30 ) ( 21 + 03 )[( 30 + 12 ) 2 - ( 21 + 03 ) 2 ] Computer Vision & Pattern Recognition Lab. 20 /26
[3] 인식 (Recognition) 목표 : 영역별특징값벡터로부터각영역을인식 1. Pattern classification ( 분류 ): Assignment of objects into one of several pre-specified categories(classes, 예 : 볼트, 너트, 못, 망치 ) 2. Scene understanding ( 이해 ): classification + analysis of relations between objects ==> Solutions are highly problem dependent Computer Vision & Pattern Recognition Lab. 21 /26
인식의과정 Computers should learn (imitate) from human!!! Classification 문제로국한한컴퓨터의인식방법 Training 과정 + Classification 과정 (1) Training - 반복적인학습에의한유아의인지과정을모방 - 주어지는샘플들의특징정보를축적, 기억 - 축적된 training 샘플들의정보로부터 Classifier 를설계 (2) Classification - 반복적인학습에의해인지능력이확보된후 - 설계된 Classifier 를이용하여 unknown input 을분류 Computer Vision & Pattern Recognition Lab. 22 /26
인식문제의예 - 4 종류의물체가존재 : w 1, w 2, w 3, w 4 - 분류를위하여 2 가지의정보를추출 X 1 : average gray level X 2 : boundary length - 2 차원특징벡터 X = [x 1, x 2 ] X 2 300 250 200 150 100 50 0 0 50 100 150 200 250 X 1 Computer Vision & Pattern Recognition Lab. 23 /26
인식 (Classification) 문제에서해결해야할 Issue 들 : -. What kind of features? ==> Problem dependent ( 예 : 사과와배는색상으로는구별가능하지만면적으로는구별하기어려움.) -. How to partition the feature space into regions (one region for each class) to minimize classification error Computer Vision & Pattern Recognition Lab. 24 /26
Classification 알고리즘 [1] Minimum distance classifier (1) Classifier design (Training) 각각의 class j 에대해서, 그 class 에속한 training sample 들의특징벡터 (X) 의평균을계산 m j = X / N j j=1,...,m m j : 평균벡터 x j N j : class j 에속한샘플의수 j : j-th class M : class 의수 (2) Classification 미지의 sample X에대해서, 1) 각 Class 평균까지의거리를계산 d j (X) = X - m j j=1,..,m 2) d i (X) 가최소인 class i 로분류 Computer Vision & Pattern Recognition Lab. 25 /26
[2] K-NN (K Nearest Neighbor) classifier 1. 미지의샘플과모든 training 샘플과의특징벡터의거리를계산 2. 가장가까운 K 개샘플들의 label 중에서다수의 label 로분류 Example: Computer Vision & Pattern Recognition Lab. 26 /26
Clustering ( 군집화 ) 패턴인식 ( 교보문고 ), 전북대학교오일석교수님 Computer Vision & Pattern Recognition Lab. 27 /26
Clustering ( 군집화 ) 군집화의특성 주관성 : 군집화결과의품질은응용이처한상황과요구사항에따라다름 패턴인식 ( 교보문고 ), 전북대학교오일석교수님
순차알고리즘 특성 군집개수를찾아준다. ( 대신임계값을설정해주어야한다.) 순서에민감하다. 빠르다 ( 선형시간 ). 패턴인식 ( 교보문고 ), 전북대학교오일석교수님
k-means 알고리즘 특성 가장널리쓰인다. ( 직관적이해. 구현간편 ) 군집개수를설정해주어야한다. 패턴인식 ( 교보문고 ), 전북대학교오일석교수님
k-means 알고리즘 7 개샘플을 k=3 개의군집으로만드는예제 초기화에의해 ( 그림 (a)), 라인 5 에의해 ( 그림 (b)), 패턴인식 ( 교보문고 ), 전북대학교오일석교수님
k-means 알고리즘 두번째루프를실행하면 ( 그림 (c)), 세번째루프는그이전과결과가같다. 따라서멈춘다. 결국출력은 패턴인식 ( 교보문고 ), 전북대학교오일석교수님
k-means 알고리즘 항상지역최적점으로수렴한다. ( 전역최적점보장못함 ) 초기군집중심에민감 빠르다. outlier 에민감하다. ( 진파랑은 k-medoids, 연파랑은 k-means) 패턴인식 ( 교보문고 ), 전북대학교오일석교수님