›
›

Bài giảng Xử lý ảnh số - Chương 9: Phân đoạn ảnh - Ngô Quốc Việt

pdf 53 trang cucquyet12 6960
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý ảnh số - Chương 9: Phân đoạn ảnh - Ngô Quốc Việt", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_xu_ly_anh_so_chuong_0_phan_doan_anh_ngo_quoc_viet.pdf

Nội dung text: Bài giảng Xử lý ảnh số - Chương 9: Phân đoạn ảnh - Ngô Quốc Việt

  1. PHÂN ĐOẠN ẢNH NGÔ QUỐC VIỆT TPHCM-2014
  2. Bài giảng giúp Người học hiểu về mục tiêu và ứng dụng của bài toán phân đoạn ảnh Người học hiểu về lý thuyết và các phương pháp phân đoạn ảnh Người học hiểu và cài đặt được phân đoạn ảnh tĩnh hay động với thư viện OpenCV Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 2
  3. 1. Giới thiệu bài toán phân đoạn 2. Phân đoạn ảnh dựa trên các phương pháp phân ngưỡng sắc xám . Phân ngưỡng toàn cục . Phân ngưỡng thích nghi, và dựa trên phương pháp Otsu. 3. Phân đoạn ảnh dựa trên các phương pháp tương tự Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 3
  4. Phân đoạn nhằm chia ảnh thành các vùng hoặc đối tượng có thể xử lý được Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 4
  5. Nếu phân đoạn tốt, các contours của objects sẽ xuất hiện và có thể trích để sử dụng. Có thể xác định hình dáng đối tượng. Dựa trên màu sắc, hình dáng, texture, có thể xác định rõ đối tượng. Phân đoạn ảnh được sử dụng nhiều trong ‘tìm kiếm tương tự (similarity searches) Phân đoạn ảnh là bài toán khó trong Xử lý ảnh. Vẫn là một chủ đề trong các hội thảo/hội nghị liên quan đến thị giác máy tính, xử lý ảnh. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 6
  6. Phân đoạn cho phép trích đối tượng trong ảnh. Các thuật giải phân đoạn dựa trên các tính chất cơ bản như màu sắc, giá trị xám, hay texture: discontinuity và similarity. Phân chia ảnh dựa trên các thay đổi độ sáng đột ngột, nhằm phát hiện biên trong ảnh. Tuy nhiên, không luôn xác định được biên để tạo vùng. Phân chia ảnh thành các vùng tương tự theo tiêu chuẩn xác định (mức xám, texture, color, motion). Dựa trên sự tương tự giữa các pixel kề nhau nhằm xây dựng các đối tượng. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 7
  7. Kiểu phân đoạn phụ thuộc vào ứng dụng Có nhiều thuật giải phân đoạn . Phân đoạn dựa trên đường viền vùng (edge detection) . Phân đoạn dựa trên clustering (hoặc grouping) . Phân đoạn dựa trên phân hoạch (partition) đồ thị Các ứng dụng như finding people, summarizing video, annotation figures, background subtraction, finding buildings/rivers in trong ảnh vệ tinh. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 8
  8. Edges dựa trên KHÁC NHAU (DIFFERENCES hay DISCONTINUITY) giữa các pixel kề nhau. Regions dựa trên sự TƯƠNG TỰ (SIMILARITIES) giữa các pixel kề nhau. Discontinuity Similarity Point Detection (dựa trên Thresholding (phân sắc xám) ngưỡng) Line Detection (dò đường Region Growing & Merging thẳng có trong ảnh) Edge Detection (đạo hàm Watershed bậc 1, 2) Active Countouring Clustering Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 9
  9. Ảnh R được phân hoạch thành các vùng con R1, R2, R3, , Rn sao cho R R a. Hội các Ri bằng với R  i i 1, ,n b. Các Ri không giao nhau Ri  Rj 0,i j c. Q(Ri)=TRUE d. Q(Ri  Rj) =FALSE, với hai vùng Ri, Rj kề nhau (vì nếu có thì đã tạo thành một vùng) Với Q(Rk) là vị từ logic xác định trên pixel thuộc Rk (ví dụ: tất cả pixel trên ngưỡng T) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 10
  10. Phân đoạn bằng mắt thường Old man và các thứ khác Hai người và con chó Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 11
  11. Tạo thành ảnh nhị phân từ ảnh xám đầu vào. Nhằm tách được foreground và forground. Thực hiện bằng cách chọn ngưỡng T, và tạo ảnh ouput theo công thức 1 f (x, y) T g(x, y) 0 f (x, y) T Chỉ làm việc tốt với ảnh có bi-model histogram, ít nhiễu. Có thể dùng nhiều ngưỡng Ti. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 12
  12. 1. Chọn ngưỡng ban đầu T (vd: chọn mean của mọi pixels) 2. Phân đoạn thành hai nhóm G1, G2, với mean tương ứng m1, m2. 3. Tính toán ngưỡng mới theo cách T = ½ (m1+m2) 4. Lặp lại bước 2 và 3 cho đến khi sự thay đổi của T mới so với T ở lần trước đó nhỏ hơn giá trị cho trước Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13
  13. Tự động thực hiện phân ngưỡng ảnh dựa trên hình dáng histogram Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 14
  14. Cho ảnh và L mức sáng q = 0, 1, 2, , L – 1 Histogram chuẩn hóa: 푖 = 푛푖/ . , với 푖 = 0, 1, 2, , 퐿 – 1, ni là số pixel cường độ sáng i. Ngưỡng k chia ảnh thành hai tập: . 0: các pixel mức sáng trong ,0, 1, , - . 1: các pixel mức sáng trong , + 1, , 퐿 − 1- 퐿−1 푃1 = 푖=0 푖 , 푃2 = 푖= +1 푖 = 1 − 푃1( ). là tổng tích lũy các p của 0 và 1. 퐿−1 1 1 휇1 = 푖. 푖, 휇2 = 푖. 푖 푃1 푃2 푖=0 푖= +1 퐿−1 휇 = 푖=0 푖. 푖, là global mean Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15
  15. Variance của mỗi nhóm 2 2 푖=0 푖 − 휇1 . 푖 휎1 = 푃1 퐿−1 2 2 푖= +1 푖 − 휇2 . 푖 휎2 = 푃2( ) 2 퐿−1 2 Variance của toàn bộ ảnh: 휎 = 푖=0 푖 − 휇 푖 . 푖 2 2 2 2 휎 = 푃1 휎1 + 푃2 휎2 + 푃1 휇1 − 휇 2 + 푃2 휇2 − 휇 2 2 2 Trong đó:휎푤 = 푃1 휎1 + 푃2 휎2 : within-class variance; 2 2 2 휎 = 푃1 휇1 − 휇 + 푃2 휇2 − 휇 : inter-class variance Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16
  16. Xác định k sao cho: 2 m푖푛 휎푤 , = 0,1, . . , 퐿 − 1 Tương đương tìm k sao cho max variance giữa hai lớp 2 휎 , = 0,1, . . , 퐿 − 1 2 2 휎 = 푃1 휇1 − 휇 2 + 푃2 휇2 − 휇 2 2 휎 = 푃1 푃2 휇1 − 휇2 2 휇 − 휇 푃1 = , 휇 = 푖. 푖, 푃1 푃2 푖=0 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 17
  17. Phân đoạn ≥ 3 ngưỡng 2 2 휎 = 푃1 휇1 − 휇 2 + 푃2 휇2 − 휇 2 + 푃3 휇3 − 휇 Cần xác định 2 ∗ ∗ 2 휎 1, 2 = *휎 1, 2 , 0 3. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 18
  18. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 19
  19. Chia ảnh thành các vùng Thực hiện phân ngưỡng thích nghi trên từng vùng Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 20
  20. Tham khảo mã nguồn openCV_AdaptiveThresHold Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 21
  21. Mean shift là thuật giải lặp nonparametric hoặc còn gọi là nonparametric density gradient estimation dựa trên cách tiếp cận kernel tổng quát. Mục tiêu: tìm cực đại của hàm mật độ xác suất (density modes) theo mẫu. Thực hiện bằng cách với mỗi điểm dữ liệu, chọn một window có kích thước cho trước, sau đó xác định mean point. Dời cửa sổ này đến điểm đó, lại tiếp tục tính mean point. Lặp liên tục cho đến khi mean point “không thay đổi" (hội tụ) cho cửa sổ đó. Mean-shift được dùng trong segmentation, clustering, visual tracking, etc. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 22
  22. Mean Shift Algorithm 1. Xác định kích thước cửa sổ tìm kiếm (search window). 2. Xác định vị trí ban đầu của search window cho mỗi điểm data. 3. Tính toán vị trí mean (centroid của dữ liệu) trong search window. 4. Xác định tâm của search window tại vị trí mean location có được ở bước 3. 5. Lặp lại bước 3 và 4 đến khi hội tụ Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23
  23. Đặt {xi}i=1 n ,là ảnh, {zi}i=1 n là các điểm hội tụ, và {Li}i=1 n là các nhãn Mean-shift segmentation Lặp i = 1 n, tìm mean shift cho xi và lưu điểm hội tụ vào zi. Tìm m clusters {Cp}p=1 m các điểm hội tụ bằng cách gom các điểm khoảng cách gần nhau vào một nhóm (khoảng cách nhỏ hơn ngưỡng cho trước – ví dụ 0.5) Lặp i= 1 n , gán Li= {p | zi ϵCp}. Rõ ràng cần xác định cách di chuyển của search window Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 24
  24. Nguồn: Dorin Comaniciu and Peter Meer, Distribution Free Decomposition of Multivariate Data, Pattern Analysis & Applications (1999)2:22–30 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 25
  25. Mục tiêu của mean shift algorithm là tìm cực trị cục bộ của density theo phân phối xác định. Nghĩa là, xác định cách di chuyển search window trong mỗi bước lặp Xác định thông qua mean shift vector để di chuyển search window. Sử dụng khái niệm kernel density estimation để xác định mean shift vector Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 26
  26. Kernel density estimation là phương pháp non parametric để ước lượng density function của biến ngẫu nhiên. Được dùng để ước lượng probability density Tìm Mean shift mode Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 27
  27. d Cho n điểm {xi}i=1, ,n thuộc R , cửa sổ bán kính h. Đặt kernel density với kernel K(x) là: n 1 x xi f (x) d K nh k 1 h Kernel K(x) có thể xác định bởi 2 K(x) c k x ck,d là hằng chuẩn hóa k,d Hàm k được gọi là profile của K. Có nhiều dạng hàm k. Đơn giản nhất là flat kernel. 1 x 1 f (x) 0 x 1 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 28
  28. Estimate của density gradient được xác định bởi gradient của kernel density estimate. Modes của density function định vị tại các zeros của gradient function. Nghĩa là f(x) = 0. n 2 1 x x 2C n x x f (x) K i f (x) k,d x x g i nhd  h d 2  i i 1 nh i 1 h 2 n x x x g i 2 i 1 i 2C n x x h f (x) k,d g i x d 2  2 nh i 1 h n x x g i i 1 h g(s) k'(s) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 29
  29. Thành phần 2 n x x g i x i 1 i h m (x) x h 2 n x x g i i 1 h Được gọi là mean shift vector. Chính là vector di chuyển của search window sau mỗi bước lặp. Thủ tục di chuyển search window như sau t Tính toán ở bước t, mh(x ). t+1 t Translate window: x = xt+mh(x ). Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30
  30. Flat kernel 1 x 1 f (x) 0 x 1 Gaussian kernel: 2 K(x) exp x Epanechikov kernel 3/ 4(1 x2 ) x 1 E(x) 0 x 1 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 31
  31. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 32
  32. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
  33. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 34
  34. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
  35. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 36
  36. Search window Center of mass Mean Shift vector Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
  37. Search window Center of mass Nguồn: Y. Ukrainitz & B. Sarel Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
  38. Tham khảo openCV_MeanShiftSegmentation Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39
  39. count pixel input image intensity • Now how to determine the three main intensities that define our groups? • We need to cluster. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 40
  40. With this objective, it is a “chicken and egg” problem: . If we knew the cluster centers, we could allocate points to groups by assigning each to its closest center. . If we knew the group memberships, we could get the centers by computing the mean per group. 42
  41. Phân hoạch tập các ‘pattern’ thành những clusters Xác định subsets các điểm ‘gần nhau’ Các tiêu chuẩn “gần nhau” : Dựa trên giá trị cường độ; Các độ đo Texture, etc. Input – tập các giá trị x1, x2, , xn (các điểm ảnh). Output – tập các clusters và tâm của chúng. K-mean Clustering phân hoạch n input thành K tập (K ≤ n) S = {S1, S2, , Sk} sao cho cực tiểu within-cluster sum of squares (WCSS) k 2 argmin   x j i S i 1 x j Si Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 43
  42. 1. Khởi động ngẫu nhiên các tâm cluster c1, , cK 2. Với mỗi tâm cluster, xác định các điểm thuộc cluster • Với mỗi điểm p, tìm gần nhất ci. Gán p vào cluster i 3. Với các điểm thuộc cluster, tìm tâm ci • Chọn ci là mean của points trong cluster i 4. Nếu ci thay đổi, lặp lại bước 2 Tính chất • Luôn hội tụ some solution • Có thể bị “local minimum”: ie, không luôn tìm được global minimum của hàm mục tiêu Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 44
  43. Chọn K mean (hay là tâm) ngẫu nhiên từ dữ (1) (1) liệu: m1 , ,mk Bước gán: xác định điểm xp thuộc cluster nào theo công thức (t) (t) (t) Si xp : xp mi xp m j 1 j k Cập nhận mean của các cluster theo 1 m(t 1) x i (t)  j S (t ) i x j Si Câu hỏi: chọn ngẫu nhiên như thế nào? Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 45
  44. Chọn không gian màu (trong phân đoạn ảnh màu). Cách chọn vector biểu diễn điểm ảnh . Ảnh xám: (grey_level, x, y). . Ảnh màu: (la, lb, lc, x, y). Với la, lb, lc là giá trị màu trong không gian màu. Không gian CIE Lab thích hợp để phân đoạn với thuật giải K-Mean Cách tính khoảng cách giữa 2 điểm dữ liệu trong biểu thức so sánh . Sử dụng khoảng cách Euclidean. Cách chọn K tâm khởi động ứng với K cluster Cách xách định giá trị K tự động ? Phân đoạn ảnh texture như thế nào? Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
  45. Việc gán cluster label cho từng pixel có thể phát sinh Original (nhiều Gán nhãn theo cluster điểm trắng xen kẽ) center’s intensity ? Cần bảo đảm phân đoạn 3 trơn. Cách nào? 1 2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 47
  46. P(foreground | image) Xem xét sự phụ thuộc giữa các pixel, xác định bởi Normalizing constant 1 P(y;,data)  f1(yi ;,data)  f2 (yi , y j ;,data) Z i 1 N i, j edges Labels to be predicted Individual predictions Pairwise predictions Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48
  47. Likelihood as an “Energy” 1 P(y;,data)  p1(yi ;,data)  p2 (yi , y j ;,data) Z i 1 N i, j edges Energy(y;,data)  1( yi ;,data)  2 ( yi , y j ;,data) i i, j edges “Cost” of assignment yi “Cost” of pairwise assignment yi ,yj Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 49
  48. Node y : pixel label Markov Random Fields i Edge: constrained pairs Cost to assign a label to Cost to assign a pair of labels to each pixel connected pixels Energy(y;,data)  1( yi ;,data)  2 ( yi , y j ;,data) i i, j edges Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 50
  49. Unary potential Example: “label smoothing” grid 0: -logP(yi = 0 ; data) 1: -logP(yi = 1 ; data) Pairwise Potential 0 1 0 0 K 1 K 0 Energy(y;,data)  1( yi ;,data)  2 ( yi , y j ;,data) i i, j edges 51
  50. Source (Label 0) Cost to assign to 1 Cost to split nodes Cost to assign to 0 Sink (Label 1) Energy(y;,data)  1( yi ;,data)  2 ( yi , y j ;,data) i i, j edges 52
  51. Source (Label 0) Cost to assign to 0 Cost to split nodes Cost to assign to 1 Sink (Label 1) Energy(y;,data)  1( yi ;,data)  2 ( yi , y j ;,data) i i, j edges 53
  52. Watershed . Region Growing . Dựa trên phân hoạch đồ thị (Shi & Malik , 97) Active Contour (Snake) – Cass, Witkin, Terzopoulos 1997 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 54