Point Operation Histogram Modification 김성영교수 금오공과대학교 컴퓨터공학과
학습내용 HISTOGRAM HISTOGRAM MODIFICATION DETERMINING THRESHOLD IN THRESHOLDING 2
HISTOGRAM A simple datum that gives the number of pixels that a given value in an image Ex) a 8bit gray-scale image Bin Counts Prob. 0 163 0.005 1 77 0.003... 255 1561 0.051 number of pixels gray level 3
4
in color images 5
true color Color Quantization 256-color 6
HISTOGRAM MODIFICATIONS Improving image contrast and brightness based on histogram Focus on the histogram shape and range 7
fields Histogram Scaling (Histogram Stretching) Histogram Scaling (Histogram Shrinking) Histogram Sliding Histogram Equalization 8
9 50 100 10 210 75 110 55 30 x y 10) 10) :( (210 50) 50) :( 100 ( y x 10) 50)*(210 ( 50) 10)*(100 ( y x 10 50) ( 50) (100 10) (210 10 50) (100 10) 50)*(210 ( x x y min min min max min max ' ) ), ( ( ) ( ) ( ), ( S I y x I I I S S y x I Scaling
O x, y = S max S max I max I min I x, y I min + S min I max I min S max S min : largest gray-level value in the image I(x,y) : smallest gray-level value in I(x,y) : maximum gray-level values possible : minimum gray-level values possible 10
Low-contrast image Histogram of low-contrast image Image after histogram stretching Histogram of image after stretching 11
Histogram of original image Image after shrinking Histogram of shrinked image 12
Sliding O x, y = I x, y + offset offset : amount to slide the histogram 13
Original image Histogram of original image positivevalue histogram sliding Histogram of image after sliding 14
Equalization 높은 contrast 좋은 contrast 15
Aim to change a picture in such a way as to produce a picture with flatter histogram, where all levels are equiprobable 16
CDF Cumulative Distribution Function 17
Deriving Algorithm (1) I l and O l (0 l < L): for the input and output image, the number of pixels per level L 1 l=0 I(l) = L 1 l=0 O(l) for an arbitrarily chosen level p in the input image p l=0 I(l) = q l=0 O(l) 18
Deriving Algorithm (2) Since the output histogram is uniformly flat (T: total number of pixels in the image) O l = T N max N min So the cumulative histogram of the output image q l=0 O(l) = q T N max N min = p l=0 I(l) 19
Deriving Algorithm (3) Output pixels at level q is given by E q, I = q = N max N min T p l=0 I(l) Equalizing function (E) of the level (q) and the image (I) The output image is then O x,y = E I x,y, I 20
algorithm 1 입력영상의히스토그램의값을누적시켜각레벨에서의히스토그램누적합계산 2 히스토그램의누적합을전체픽셀의개수로나누어값을정규화함 3 정규화된값에최대 gray level 값을곱한후반올림을수행 4 입력영상의각 gray level 에대해변환값으로대응 21
10 8 9 2 14 1 5 2 51 49 43 44 27 29 18 10 10 8 11 15 7 0 7 0 7 (1,2,4,4,6,6,7,7) 0 7 히스토그램누적값균일화결과 (10,18,27,29,43,44,49,51) 7 51 (1.37, 2.47,3.71,3.98,5.90, 6.04, 6.73, 7.00) 22
4 5 3 6 7 4 2 2 4 6 0 2 2 5 7 0 0 2 3 5 0 1 2 4 4 LUT 입력레벨 개수 누적값 균일화결과레벨 0 10 10 1.37 1 1 8 18 2.47 2 2 9 27 3.71 4 3 2 29 3.98 4 4 14 43 5.90 6 5 1 44 6.04 6 6 5 49 6.73 7 7 2 51 7.00 7 6 6 4 7 7 6 4 4 6 7 1 4 4 6 7 1 1 4 4 6 1 2 4 6 6 23
Original light image Histogram of original image Histogram of equalized image 24
Histogram normalization vs. equalization equalization normalization 25
DISADVANTAGE Background noise can be increased The image quality in a near-constant region may be degraded 26
THRESHOLD 의결정 background object threshold Bimodal histogram 27
8 26 130 28
OPTIMAL THRESHOLD BY OTSU (1) 1) 히스토그램계산 2) T = k(k 1) 에서클래스분리를위한확률및평균계산 C 1 (k) = k 1 i=0 P i, C 2 k = L 1 i=k P i = N C 1 (k) ω 1 (k) = C 1(k) N, ω 2(k) = C 2(k) N = 1 ω 1(k) k 1 L 1 L 1 μ T1 k = i P i, μ T2 k = i P i, μ T = i P i i=0 i=k i=0 μ 1 k = μ T1 k C 1 k, μ 2 k = μ T2 k C 2 k = μ T μ T1 k N C 1 (k) 29
OPTIMAL THRESHOLD BY OTSU (2) 3) T = k(k 1) 에서클래스분리를위한분산 σ W 2 계산 σ 1 2 k = k 1 n=0 n μ 1 (k) 2 P n C 1 (k), σ 2 2 k = L 1 n=k n μ 2 (k) 2 P n C 2 (k) σ W 2 k = ω 1 k σ 1 2 k + ω 2 (k)σ 2 2 k, k 1, 2,, (L 1) 4) 모든레벨에대해반복하여최적임계값선택 σ W 2 T opt = min 1 k L 1 σ W 2 (k) 30
OPTIMAL THRESHOLD BY OTSU (3) σ 2 = σ B 2 + σ W 2 Within class variance: σ W 2 = ω 1 σ 1 2 + ω 2 σ 2 2 Between class variance: σ B 2 = σ 2 σ W 2 = ω 1 μ 1 μ 2 + ω 2 μ 2 μ 2 = ω 1 ω 2 μ 1 μ 2 2 31
ALGORITHM 1. 히스토그램계산 2. μ T 계산 3. 각 threshold k(1 k < L) 에대해 3-1. C 1 (k), C 2 (k), μ T1 k, μ T2 k, ω 1 (k), ω 2 (k) 계산 3-2. σ 2 B 계산 3-3. 최대 σ 2 B 와비교하여현재 σ 2 B 가더크면 1 현재 σ 2 B 를사용하여최대 σ 2 B 를갱신 2 threshold k를 optimal threshold (T_OPT) 로선택 Coarse to fine approach 사용가능 32
요약 Histogram A simple datum that gives the number of pixels that a given value in an image Histogram modifications Improving image contrast and brightness by changing shape and range of histogram Histogram Normalization (Histogram Stretching and Histogram Shrinking), Histogram Sliding, Histogram Equalization Selecting Threshold Optimal thresholding: Otsu s method 33
REFERENCE R. Gonzalez, R. Woods, Digital Image Processing (2nd Edition), Prentice Hall, 2002 Scott E Umbaugh, Computer Imaging, CRC Press, 2005 Mark Nixon and Alberto Aguado, Feature Extraction & Image Processing, ELSEVIER, 2008 Frank SHIH, Image Processing and Pattern Recognition, IEEE Press, 2010 34