Đánh giá hiệu năng của thuật toán phân cụm mờ bán giám sát cho bài toán phân đoạn ảnh nha khoa

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

62
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Đánh giá hiệu năng của thuật toán phân cụm mờ bán giám sát cho bài toán phân đoạn ảnh nha khoa trình bày tổng quan các kỹ thuật phân cụm mờ bán giám sát và đề xuất một lược đồ tổng quát mới cho việc áp dụng các kỹ thuật này cho bài toán phân đoạn ảnh nha khoa.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đánh giá hiệu năng của thuật toán phân cụm mờ bán giám sát cho bài toán phân đoạn ảnh nha khoa

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 ĐÁNH GIÁ HIỆU NĂNG CỦA THUẬT TOÁN PHÂN CỤM MỜ BÁN GIÁM SÁT CHO BÀI TOÁN PHÂN ĐOẠN ẢNH NHA KHOA Trần Mạnh Tuấn1, Phạm Huy Thông2, Lê Hoàng Sơn2, Nguyễn Đình Hóa3 1 Trường Đại học Công nghệ thông tin và truyền thông, Đại học Thái Nguyên 2 Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội 3 Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội tmtuan@ictu.edu.vn, thongph@vnu.edu.vn, sonlh@vnu.edu.vn, hoand@vnu.edu.vn TÓM TẮT - Phân đoạn ảnh nha khoa là bước xử lý quan trọng trong nha khoa thực hành nhằm hỗ trợ bác sĩ chẩn đoán một cách hiệu quả các bệnh quanh răng như viêm chân răng, bệnh nha chu, viêm túi răng, v.v. Đối với bài toán này, các kỹ thuật xử lý ảnh thông thường hay phân cụm rõ thường gặp vấn đề về xác định tham số ngưỡng hay biên chung của các mẫu răng. Khi đó kỹ thuật phân cụm mờ cụ thể là phân cụm mờ bán giám sát là một công cụ tương đối hiệu quả trong việc xử lý các vấn đề liên quan đến chất lượng cụm mà trong đó một số thông tin đã được phân loại sẽ định hướng cho quá trình xử lý về sau. Trong bài báo này, chúng tôi sẽ tổng quan các kỹ thuật phân cụm mờ bán giám sát và đề xuất một lược đồ tổng quát mới cho việc áp dụng các kỹ thuật này cho bài toán phân đoạn ảnh nha khoa. Tiếp theo, trên cơ sở thực nghiệm với dữ liệu gồm 8 bệnh nhân được thu thập trong giai đoạn 2014-2015 tại trường Đại học Y Hà Nội, hiệu năng của các thuật toán được đánh giá theo các độ đo khác nhau được khảo sát kỹ lưỡng. Kết luận của bài báo chỉ ra thuật toán phân cụm mờ bán giám sát có hiệu năng tốt nhất cho bài toán phân đoạn ảnh nha khoa. Từ khóa – Phân cụm mờ bán giám sát, ảnh nha khoa, phân đoạn ảnh, hiệu năng thuật toán. I. GIỚI THIỆU Phân đoạn ảnh là giai đoạn đầu tiên trong quá trình xử lý ảnh và đóng vai trò rất quan trọng [16, 24] trong quá trình này. Phân đoạn ảnh cũng là công việc khó khăn nhất của xử lý ảnh. Trong đó, phân đoạn ảnh nha khoa là bước xử lý then chốt trong nha khoa thực hành nhằm hỗ trợ bác sĩ chẩn đoán một cách hiệu quả các bệnh về răng như viêm chân răng, bệnh nha chu, viêm túi răng [19, 20]. Đối với bài toán này, các nghiên cứu trước đây đã đưa ra các kỹ thuật phân đoạn như: phân đoạn dựa trên phân ngưỡng [8, 13], phân đoạn dựa trên các thuật toán phân cụm [21, 32]. Tuy nhiên các phương pháp này thường gặp vấn đề khi xác định tham số ngưỡng hay biên chung của các mẫu răng [26]. Do vậy phương pháp phân cụm mờ cụ thể là phân cụm mờ bán giám sát là một công cụ tương đối hiệu quả trong việc xử lý các vấn đề liên quan đến chất lượng cụm mà trong đó một số thông tin đã được phân loại sẽ định hướng cho quá trình phân cụm về sau. Trong phân cụm không mờ, dữ liệu được chia vào các nhóm, trong đó mỗi điểm dữ liệu thuộc vào chính xác một cụm [2]. Trong phân cụm mờ, các điểm dữ liệu có thể thuộc vào nhiều hơn một cụm và tương ứng với các điểm dữ liệu là ma trận độ thuộc, với giá trị của các phần tử chỉ ra mức độ các điểm dữ liệu thuộc vào các cụm khác nhau [2]. Các phương pháp phân cụm mờ được sử dụng nhiều trong các bài toán nhận dạng mẫu, phát hiện tri thức từ các cơ sở dữ liệu, đánh giá rủi ro và nó có ứng dụng nhiều trong phân đoạn ảnh. Trong các nghiên cứu gần đây việc sử dụng các thông tin bổ trợ cung cấp bởi người dùng được gắn với đầu vào trong phân cụm mờ để hướng dẫn, giám sát và điều khiển quá trình phân cụm. Khi đó các thuật toán phân cụm mờ kết hợp với các thông tin bổ trợ hình thành nên nhóm các thuật toán gọi là phân cụm mờ bán giám sát [7]. Một số nghiên cứu gần đây cho thấy các thuật toán phân cụm mờ bán giám sát rất hiệu quả trong nhiều lĩnh vực như xử lý ảnh [5, 14, 24], nhận dạng mẫu, nhận dạng khuôn mặt [1, 17], đánh giá rủi ro [4], dự báo phá sản [18]. Đặc biệt là trong xử lý ảnh với các ảnh màu và ảnh y học. Trong các nghiên cứu này, chưa có kết quả nào của phân cụm mờ bán giám sát được áp dụng cho các ảnh X-quang nói chung và ảnh X-quang nha khoa nói riêng. Do vậy đóng góp chính của bài báo này là trình bày tổng quan các phương pháp phân cụm mờ bán giám sát. Sau đó, đưa ra lược đồ áp dụng phân cụm mờ bán giám sát cho bài toán phân đoạn ảnh nha khoa. Việc đánh giá hiệu năng của thuật toán thực hiện dựa trên bộ dữ liệu thực tế gồm 8 ảnh X-quang nha khoa của các bệnh nhân trong giai đoạn 2014-2015 tại trường Đại học Y Hà Nội để phục vụ việc chẩn đoán hình ảnh. Cuối cùng, bài báo đưa ra một số kết luận liên quan đến việc sử dụng thuật toán với các bộ dữ liệu khác. Ý nghĩa của nghiên cứu này là tìm ra một thuật toán có hiệu quả trong việc phân đoạn ảnh X-quang nha khoa. Để thực hiện điều này, chúng tôi xây dựng một mô hình toán học dưới dạng bài toán tối ưu và sử dụng các thông tin bổ trợ để cải thiện chất lượng phân đoạn ảnh. Dựa trên tập mẫu về các ảnh X-quang nha khoa thực tế, mô hình được đánh giá một cách cụ thể kết quả là sự phân biệt giữa cấu trúc răng và các mô trong ảnh. Việc phân đoạn chính xác này có ý nghĩa trong quá trình xử lý ảnh tiếp theo. Phần tiếp theo của bài báo được tổ chức như sau: trong phần II, chúng tôi tổng quan lại các phương pháp phân cụm mờ bán giám sát. Phần III đưa ra lược đồ áp dụng cho phân đoạn ảnh nha khoa dựa trên phân cụm mờ bán giám sát. Phần IV là một số kết quả được thực hiện trên bộ dữ liệu thực và đánh giá hiệu năng của các thuật toán đã trình bày. Cuối cùng là kết luận và các hướng phát triển trong thời gian tới. Trần Mạnh Tuấn, Phạm Huy Thông, Lê Hoàng Sơn, Nguyễn Đình Hóa 131 II. TỔNG QUAN VỀ PHÂN CỤM MỜ BÁN GIÁM SÁT Trong phần này, mục 2.1 sẽ trình bày thuật toán cơ sở của phân cụm mờ bán giám sát (Fuzzy C-means - FCM). Mục 2.2 sẽ trình bày về các loại thông tin bổ trợ được sử dụng trong phân cụm mờ bán giám sát và trong phân đoạn ảnh. Mục 2.3 trình bày về một số thuật toán phân cụm mờ bán giám sát sử dụng thông tin bổ trợ về độ thuộc được xác định trước trong phân đoạn ảnh. 2.1. Thuật toán Fuzzy C-means Thuật toán phân cụm mờ được Bezdek [2] đề xuất dựa trên độ thuộc ukj của phần tử dữ liệu Xk từ cụm j. Hàm mục tiêu được xác định như sau: N C m J = ∑∑ u kj X k − V j 2 → min (1) k =1 j =1 + m là số mờ hóa + C là số cụm, N là số phần tử dữ liệu, r là số chiều của dữ liệu. + ukj là độ thuộc của phần tử dữ liệu Xk từ cụm j. + X k ∈ R là phẩn tử thứ k của X = {X 1 , X 2 ,..., X N }. r + Vj là tâm của cụm j. Khi đó ràng buộc của (1) là: C ∑u kj = 1; j =1 u kj ∈ [0,1]; ∀k = 1, N (2) Sử dụng phương pháp Lagrange, xác định được tâm của cụm dựa vào (3) và độ thuộc dựa vào (4) từ hàm mục tiêu (1): C Vj = ∑u k =1 C m kj ∑u Xk (3) m kj k =1 (4) 1 u kj = ⎛ X k −Vj ⎞ ⎟ X k − Vi ⎟ i =1 ⎝ ⎠ C ∑⎜ ⎜ 1 m −1 Khi đó thuật toán Fuzzy C-means như sau (xem bảng 1) Bảng 1. Thuật toán Fuzzy C-means Input Tập dữ liệu X gồm N phần tử trong không gian r chiều; số cụm C; mờ hóa m; ngưỡng ԑ; số lần lặp lớn nhất MaxStep>0. Output Ma trận U và tâm cụm V. FCM 1 t=0 2 ( u kjt ) ← random; 3 Repeat 4 t=t+1 5 Tính V j ; j = 1, C bởi công thức (3) 6 Tính ( ) u ( ) ; (k = 1, N ; j = 1, C ) bởi công thức (4) 7 Until U (t ) − U (t −1) ≤ ε hoặc t > MaxStep (k = 1, N ; j = 1, C ) thỏa mãn điều kiện (2) (t ) t kj 132 ĐÁNH GIÁ HIỆU NĂNG CỦA THUẬT TOÁN PHÂN CỤM MỜ BÁN GIÁM SÁT CHO BÀI TOÁN PHÂN ĐOẠN ẢNH NHA KHOA 2.2. Thông tin bổ trợ trong phân cụm mờ bán giám sát Các thuật toán phân cụm mờ bán giám sát xây dựng dựa trên các thuật toán phân cụm mờ kết hợp với các thông tin bổ trợ được người dùng cung cấp. Các thông tin bổ trợ nhằm mục đích hướng dẫn, giám sát và điều khiển quá trình phân cụm. Thông tin bổ trợ thường được xây dựng dựa trên 3 loại cơ bản [31] là: + Các ràng buộc Must-link và Cannot-link: Ràng buộc Must-link yêu cầu 2 phần tử phải thuộc vào cùng 1 cụm, ngược lại ràng buộc Cannot-link chỉ ra 2 phần tử không thuộc cùng 1 cụm (mà phải thuộc 2 cụm khác nhau). + Các nhãn lớp của một phần dữ liệu: Một phần của dữ liệu được gán nhãn và phần còn lại không được gán nhãn. + Độ thuộc được xác định trước. Một số nghiên cứu về phân đoạn ảnh sử dụng phân cụm bán giám sát thường dùng loại thông tin bổ trợ là giá trị hàm độ thuộc bổ sung. Với loại thông tin bổ trợ này, Zhang [30] đã áp dụng quy tắc entropy để giảm số chiều và đề xuất một tiếp cận mới với ý tưởng là kết hợp một thành phần theo quy tắc entropy vào hàm mục tiêu. Bên cạnh đó, Yasunori [29] đã đề xuất thuật toán phân cụm mờ bán giám sát trên cơ sở của FCM bổ sung thêm hàm độ thuộc bổ trợ sử dụng trong quá trình phân cụm. Bouchachia và Pedryzc [3] sử dụng thông tin bổ trợ vào việc xác định các thành ~ phần u kj thông qua giá trị trung gian uik . Trong bài báo này nhóm chúng tôi đề xuất việc sử dụng thông tin hàm độ thuộc là giá trị hàm độ thuộc nhận được sau khi sử dụng thuật toán phân cụm FCM. Các thuật toán này lần lượt được trình bày trong mục 2.3 dưới đây. 2.3. Các thuật toán phân cụm mờ bán giám sát sử dụng thông tin bổ trợ về độ thuộc 2.3.1. Phân cụm mờ bán giám sát tiêu chuẩn (SEMI-SUPERVISED STANDARD FUZZY CLUSTERING) Yasunori et al. [29] đã đề xuất một thuật toán phân cụm mờ bán giám sát với thông tin bổ trợ là hàm độ thuộc bổ sung trong hàm mục tiêu của FCM để cải thiện hiệu quả trong quá trình phân cụm của thuật toán. Khi đó hàm mục tiêu [29] được xác định như sau N C J (U , V ) = ∑∑ | ukj − ukj |m || X k − V j ||2 → min k =1 j =1 (5) X k với cụm C j là ukj ∈ [0,1] đồng thời Với điều kiện ràng buộc (2), khi đó hàm độ thuộc bổ trợ của phần tử thỏa mãn { C } ∑u U = ukj | ukj ∈ [0,1], k = 1, N , j = 1, C , j =1 kj ( ≤ 1 , ∀k = 1, N ) Khi đó dựa vào điều kiện (2) và hàm mục tiêu (5) chúng ta có N Vj = ∑u kj − ukj k =1 N ∑u kj m − ukj Xk m , j = 1, C k =1 (6) Và u kj được xác định theo 2 trường hợp sau - m >1 : 2 - m =1: ⎛ ⎞ m −1 1 ⎜ ⎟ ⎜ X k − Vj ⎟ C ⎛ ⎞ ⎠ , k = 1, N , j = 1, C . ukj = ukj + ⎜1 − ∑ ukj ⎟ ⎝ 2 ⎝ i =1 ⎠ C ⎛ ⎞ m −1 1 ⎜ ∑⎜ X − V ⎟ ⎟ i =1 ⎝ k i ⎠ C ⎧ 2 ⎪ukj + 1 − ∑ ukj , k = arg min X k − Vi i j =1 , k = 1, N , j = 1, C . ukj = ⎨ ⎪u , otherwise. ⎩ kj Thuật toán Semi-Supervised Standard Fuzzy Clustering (SSSFC) như sau (xem bảng 2) (7) (8) Trần Mạnh Tuấn, Phạm Huy Thông, Lê Hoàng Sơn, Nguyễn Đình Hóa 133 Bảng 2. Thuật toán Semi-Supervised Standard Fuzzy Clustering Input Tập dữ liệu X gồm N phần tử , số cụm C, ma trận độ thuộc bổ trợ maxStep > 0. Output Ma trận U và tâm cụm V. U , ngưỡng ε , số lần lặp tối đa SSSFC 1: t=0 2: Khởi tạo ngẫu nhiên Vj ; ( j = 1, C ) 3: Repeat (t) 4: t=t+1 5: Tính u kj ( k = 1, N ; j = 1, C ) bới công thức (7) với 6: Tính 7: Until V Vj ( t +1) (t ) m > 1 hoặc công thức (8) với m = 1 . ( j = 1, C ) bởi công thức (6) − V (t −1) ≤ ε or t > maxStep 2.3.2. Phân cụm mờ bán giám sát đã hiệu chỉnh (SEMI-SUPERVISED ENTROPY REGULARIZED FUZZY CLUSTERING) Thuật toán semi-supervised entropy regularized fuzzy clustering được Yasunori và cộng sự [29] đề xuất năm 2009, đến năm 2012 Yin [30] có đề xuất hiệu chỉnh hệ số Entropy và khi đó thuật toán phân cụm mờ bán giám sát dựa trên thuật toán Entropy Regularized Fuzzy Clustering (eSFCM), sử dụng độ thuộc bổ trợ ukj để tăng hiệu suất phân cụm với điều kiện C ∑u kj ukj ∈ [0,1]; ≤ 1; j =1 ∀k = 1, N (9) Với tâm cụm ban đầu được xác định theo công thức N vj = ∑u k =1 N 2 kj Xk ∑u 2 kj ; j = 1,..., C (10) k =1 Để sử dụng khoảng cách Mahalanobis, ma trận hiệp phương sai của các mẫu được tính như sau A= 1 C N 2 T ∑∑ ukj (x k − v j )(x k − v j ) N j =1 k =1 Sau đó, khoảng cách được tính bởi công thức (với (11) A = P −1 ) 2 d A ( x1 , x2 ) = (x1 − x2 ) A(x1 − x2 ) T (12) Khi đó hàm mục tiêu [29, 30] của eSFCM được xác định như sau N C J (U ,V ) = ∑∑ ukj X k − V j k =1 j =1 2 A N C ( ) + λ−1 ∑∑ ukj − ukj ln ukj − ukj → min k =1 j =1 (13) Với điều kiện ràng buộc (8) và hàm mục tiêu (13) ta có các công thức xác định ma trận độ thuộc ukj = ukj + e C − λ X k −V j ∑e 2 A − λ X k −V i 2 A i =1 Trong đó X k − V j 2 A = d A( k , j ) và tâm cụm C ⎛ ⎞ ⎜1 − ∑ uki ⎟ , k = 1, N , j = 1, C ⎝ i =1 ⎠ (14) 134 ĐÁNH GIÁ HIỆU NĂNG CỦA THUẬT TOÁN PHÂN CỤM MỜ BÁN GIÁM SÁT CHO BÀI TOÁN PHÂN ĐOẠN ẢNH NHA KHOA ∑ = ∑ N u Xk k =1 kj N Vj ; j = 1, C u k =1 kj (15) Thuật toán Semi-Supervised Entropy Regularized Fuzzy Clustering (eSFCM) như sau (xem bảng 3) Bảng 3. Thuật toán Semi-Supervised Entropy Regularized Fuzzy Clustering Input Output eSFCM 1: Tập dữ liệu X gồm N phần tử , số cụm C, độ thuộc bổ trợ Ma trận U và tâm cụm V. Tính ma trận P theo công thức (11) với ma trận độ thuộc 2: 3: 4: 5: Tính 7: Until U U đã cho và các tâm cụm v j ban đầu; t = 1; Repeat t=t+1 6: U , ngưỡng ε , số lần lặp tối đa maxStep > 0. Tính u kj ( k = 1, N ; j = 1, C ) bới công thức (14) Vj ( t +1) (t ) ( j = 1, C ) bởi công thức (15) − U ( t −1) ≤ ε or t > maxStep 2.3.3. Thuật toán Semi-Supervised Fuzzy C-Mean của Bouchachia và Pedrycz Bouchachia và Pedrycz [3] đã đề xuất phương pháp phân cụm mờ bán giám sát với thông tin bổ trợ là độ thuộc bổ trợ ukj cho trước, khi đó hàm mục tiêu [3] được xác định bởi C N C L C 2 2 2 J (U ,V , λ ) = ∑∑ u ik d ik + α ∑∑ (u ik − u ik ) 2 d ik − λ ∑ (u ik − 1) Tham số λ i =1 k =1 i =1 k =1 (16) i =1 được xác định bởi công thức C N α 1 − 1+α ∑∑ u ik λ= i =1 k =1 C N (17) 1 ∑∑ 2(1 + α )d i =1 k =1 2 ik với các phần tử của ma trận độ thuộc U được tính như sau α u ik + u ik = 1+α 1− α C ∑u 1 + α l =1 C d ∑ d ik l =1 lk ik (18) H Với H là số lớp, mỗi lớp h chứa một số các cụm C h thỏa mãn (t ) = u ik ( t −1) h = C và π h là tập các cụm thuộc vào h =1 ~ lớp h thì các giá trị uik được cho bởi công thức (t là số bước lặp) u ik ∑C H ⎛ ⎞ ⎧1, ( + 2 βδ k ∑ ⎜ f hk − ∑ u ikt −1) ⎟ * ⎨ ⎜ ⎟ 0, h =1 ⎝ i∈π h ⎠ ⎩ k ∈π h k ∉π h (19) Tâm cụm i được xác định bởi ∑ (u N vi = 2 ij ) + α (u ij − u ik ) 2 x j j =1 ∑ (u N j =1 2 ij + α (u ij − u ik ) 2 ) Thuật toán được thực hiện theo các bước như sau (xem bảng 4) (20)