Tài liệu Nghiên cứu một số phương pháp phân cụm bán giám sát mờ trong phân đoạn ảnh nha khoa (tt)

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… TRẦN MẠNH TUẤN NGHIÊN CỨU MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM BÁN GIÁM SÁT MỜ TRONG PHÂN ĐOẠN ẢNH NHA KHOA Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TÁT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2016 Công trình đƣợc hoàn thành tại: Học viện Khoa học và Công nghệ Viện Hàn lâm Khoa học và Công nghệ Việt Nam Ngƣời hƣớng dẫn khoa học 1: PGS.TS. LÊ BÁ DŨNG Ngƣời hƣớng dẫn khoa học 2: TS. VŨ NHƢ LÂN Phản biện 1: PGS.TS. Trần Đình Khang Phản biện 2: PGS.TS. Ngô Thành Long Phản biện 3: TS. Phạm Thanh Hà Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi giờ ngày tháng năm Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam MỞ ĐẦU Phân đoạn ảnh là chia nhỏ một ảnh thành các vùng đông nhất cấu tạo nên ảnh hoặc các đối tượng [17], [52]. Phân đoạn ảnh thường được sử dụng để xác định: vị trí đối tượng (chẳng hạn như các loại cây trồng, khu vực đô thị, rừng của một hình ảnh vệ tinh, v.v.) và các đường biên, ranh giới (đường thẳng, đường cong, v.v.) trong ảnh. Với ảnh nha khoa thì mục đích của 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 X-quang nha khoa gồm 3 phần chính [54]: i) Phần răng: phần có độ xám cao và là phần ta nhìn thấy rõ nhất trên ảnh; ii) Phần cấu trúc răng: là phần có độ xám trung bình gồm lợi răng, xương, phần khác (tủy, xi măng v.v.); iii) Phần nền: là phần có giá trị độ xám nhỏ nhất là nền tảng của cấu trúc răng. Với cấu trúc của ảnh X-quang nha khoa thì việc phân đoạn ảnh phức tạp hơn phân đoạn ảnh thông thường [70]. Bài toán phân đoạn ảnh nha khoa đã được sử dụng để hỗ trợ việc chẩn đoán bệnh nha khoa và dự đoán tuổi nha khoa [51]. Đồng thời, phân đoạn ảnh nha khoa mang lại những thông tin có giá trị cho những nha sĩ trong quá trình phân tích các thông tin từ một hình ảnh [51]. Liên quan đến độ chính xác của phân đoạn ảnh nha khoa, cần có các phương pháp học máy khác nhau được áp dụng [30], [35]. Kết quả phân đoạn ảnh nha khoa còn cung cấp thêm các thông tin cho các nha sỹ trong quá trình chẩn đoán bệnh, giúp các nha sỹ chẩn đoán bệnh chính xác và hiệu quả hơn. Với bài toán phân đoạn ảnh nha khoa, 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 ảnh dựa trên phân ngưỡng [21], [27], phân đoạn ảnh dựa trên phân cụm [44], [70]. 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 và phương pháp phân cụm mờ được cho là xử lý tốt hơn [59]. Trong phân cụm rõ, 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 [10]. Trong phân cụm mờ, mỗi điểm dữ liệu có thể thuộc vào nhiều hơn một cụm với độ thuộc tương ứng [10]. Khi đó, 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ử trong ma trận chỉ ra mức độ các điểm dữ liệu thuộc vào các cụm khác nhau [10]. 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. Các thuật toán phân cụm mờ kết hợp với các thông tin bổ trợ do người dùng xác định trước hình thành lên nhóm các thuật toán phân cụm bán giám sát mờ [23]. Một số nghiên cứu gần đây cho thấy các thuật toán phân cụm bán giám sát mờ rất hiệu quả trong nhiều lĩnh vực như xử lý ảnh [16], [31], [49], nhận dạng mẫu, nhận dạng khuôn mặt [5], [33], đánh giá rủi ro [15], dự báo phá sản [36]. Đặc biệt là trong xử lý ảnh với các ảnh màu và ảnh y học. Cũng đã có một số kết quả được đưa ra cho bài toán phân đoạn ảnh nha khoa như sử dụng các đặc trưng của ảnh nha khoa như cấu trúc ảnh, màu sắc, hình dáng trong quá trình phân đoạn gồm phương pháp lấy ngưỡng [21], [27], phương pháp phân cụm [70]. Tuy nhiên nghiên cứu này, chưa có kết quả nào của phân cụm bán giám sát mờ được áp dụng cho các ảnh X-quang nói chung và ảnh X-quang nha khoa nói riêng, mà chủ yếu các nghiên cứu trước cũng đã sử dụng phân cụm mờ và đồng thời đã sử dụng các đặc trưng của ảnh nha khoa nhưng chưa sử dụng thông tin không gian. Nội dung nghiên cứu chính của luận án tập trung vào việc đề xuất, cải tiến các kỹ thuật phân đoạn ảnh bằng thuật toán phân cụm bán giám sát mờ. Trong quá trình phân đoạn ảnh nha khoa, các kỹ thuật phân cụm mờ (FCM) [10], phân cụm bán giám sát mờ (eSFCM) [67] và kỹ thuật tách ngưỡng Otsu [43] là các kỹ thuật cơ bản làm tiền đề cho các phương pháp mới được đề xuất trong luận án. Trong các phương pháp mới trình bày trong luận án, thông tin bổ trợ được xác định là ma trận độ thuộc của thuật toán phân cụm mờ FCM kết hợp với các thông tin đặc trưng của ảnh nha khoa. Đây là một cách tiếp cận mới mà các phương pháp trước đó chưa đề cập đến. Đồng thời, luận án trình bày một số cách xác định thông tin bổ trợ phù hợp ứng với từng đối tượng đầu vào khác nhau. Từ đó thực hiện việc cài đặt và đánh giá các đề xuất trên máy tính. Mục tiêu nghiên cứu: Nghiên cứu các thuật toán phân cụm bán giám sát mờ vào phân đoạn ảnh. Phát triển các nghiên cứu đề xuất cải tiến các phương pháp phân cụm bán giám sát mờ cho phân đoạn ảnh nha khoa. Các thuật toán cải tiến được đề xuất dựa trên các thông tin không gian đặc trưng của ảnh nha khoa nhằm mục đích nâng cao chất lượng phân cụm của các thuật toán phân cụm bán giám sát mờ áp dụng với bài toán phân đoạn ảnh nha khoa. Với mục tiêu nghiên cứu ở trên luận án đã thu đƣợc một số đóng góp mới nhƣ sau:  Luận án đã nghiên cứu phát triển các thuật toán phân cụm bán giám sát mờ trong phân đoạn ảnh nha khoa, cụ thể: - Đề xuất các phương pháp phân đoạn ảnh nha khoa dựa trên phân cụm bán giám sát mờ lai ghép. (Lai ghép giữa phân cụm bán giám sát mờ với phân cụm mờ và phương pháp tách ngưỡng Otsu). - Đề xuất phân cụm bán giám sát mờ có sử dụng đặc trưng không gian ảnh nha khoa vào bài toán phân đoạn ảnh; - Vận dụng các phương pháp giải tối ưu đa mục tiêu để giải bài toán tối ưu đa mục tiêu của phân cụm bán giám sát mờ, từ đó đưa ra các mệnh đề, định lý và tính chất nghiệm của bài toán; - Xây dựng kho dữ liệu các hàm xác định thông tin bổ trợ cho phân cụm bán giám sát mờ, từ đó lựa chọn hàm thông tin bổ trợ phù hợp với từng ảnh đầu vào để chất lượng cụm được tốt hơn.  Cài đặt thực nghiệm các thuật toán cải tiến dựa trên thu thập và phân tích dữ liệu ảnh về các mẫu bệnh nha khoa. Ứng dụng phân đoạn ảnh trong hệ hỗ trợ chẩn đoán nha khoa. Ngoài phần phần mở đầu và kết luận, luận án được cấu trúc thành ba chương: Chương 1 trình bày về tổng quan về phân cụm bán giám sát mờ trong bài toán phân đoạn ảnh. Đồng thời trình bày các lý thuyết cơ sở sử dụng trong quá trình học tập và nghiên cứu. Thông qua chương này, luận án đưa ra được cái nhìn tổng quan về bài toán nghiên cứu, các khái niệm và thuật toán cơ bản sử dụng trong nghiên cứu của luận án. Các đóng góp chính của luận án lần lượt được trình bày trong chương 2, chương 3. Chương 2 trình bày kết quả nghiên cứu các phương pháp phân cụm bán giám sát mờ sử dụng cho phân đoạn ảnh nha khoa. Trong chương này trình bày về phân cụm bán giám sát mờ lai ghép. Đặc biệt luận án còn trình bày đề xuất phát triển của phân cụm bán giám mờ có sử dụng thông tin đặc trưng không gian sử dụng phương pháp nhân tử Lagrange và thỏa dụng mờ giải bài toán tối ưu đa mục tiêu. Đồng thời, trong chương 2, luận án xây dựng cách xác định thông tin bổ trợ phù hợp từng ảnh đầu vào để có được kết quả phù hợp nhất. Chương 3 trình bày các kết quả thực nghiệm thu được khi cài đặt các thuật toán phân cụm bán giám sát mờ đề xuất ở chương 2 trên bộ dữ liệu ảnh X-quang nha khoa. Trong đó có phân tích dữ liệu sử dụng và các tiêu chí đánh giá thông qua các độ đo, từ đó xác định các kết quả này được sử dụng để đánh giá hiệu năng các thuật toán đề xuất và so sánh với các thuật toán khác đã được nghiên cứu gần đây cho các bài toán tương tự. Ứng dụng của phân đoạn ảnh trong thiết kế hệ hỗ trợ chẩn đoán bệnh. Cuối cùng, kết luận nêu những đóng góp, hướng phát triển, những vấn đề quan tâm và các công trình đã được công bố của luận án. CHƢƠNG 1. TỔNG QUAN VỀ PHÂN CỤM BÁN GIÁM SÁT MỜ TRONG PHÂN ĐOẠN ẢNH NHA KHOA Trong chương này, luận án đã nêu ra bài toán nghiên cứu trong thời gian vừa qua. Qua đó có được cái nhìn tổng quan về bài toán nghiên cứu trong luận án, cụ thể là bài toán phân đoạn ảnh nha khoa và bài toán chẩn đoán bệnh nha khoa. Luận án đã trình bày các kết quả nghiên cứu liên quan được đề xuất gần đây. Đồng thời trong chương này, luận án đã trình bày lý thuyết về tập mờ, phân cụm, phương pháp giải tối ưu và hệ suy diễn mờ. Các kiến thức này là nền tảng để giải quyết các bài toán phân đoạn ảnh và chẩn đoán nha khoa mà luận án đang hướng tới. 1.1 Bài toán phân đoạn ảnh nha khoa 1.1.1 Khái niệm Phân đoạn ảnh chia nhỏ một ảnh thành các vùng cấu thành nên nó hoặc các đối tượng [17], [52]. Phân đoạn ảnh thường được sử dụng để xác định vị trí đối tượng (chẳng hạn như các loại cây trồng, khu vực đô thị, rừng của một hình ảnh vệ tinh, v.v.) và các đường biên/ranh giới (đường thẳng, đường cong, v.v.) trong ảnh. Chính xác hơn, phân đoạn ảnh là quá trình gán nhãn cho mọi pixel trong ảnh mà những pixel có cùng nhãn thì có chung một số đặc điểm nhất định nào đó. 2 1.1.2 Ảnh X-quang nha khoa Cơ quan của răng bao gồm răng và nha chu quanh răng, là đơn vị hình thái và chức năng của bộ răng. Răng là bộ phận trực tiếp nhai nghiền thức ăn, nha chu là bộ phận giữ và nâng đỡ răng đồng thời là bộ phận nhận cảm, tiếp nhận và dẫn truyền lực nhai. Răng gồm men, ngà (mô cứng) và tủy (mô mềm). Nha chu gồm xương chân răng, men chân răng, dây chằng, xương ổ răng, nướu (lợi), xương. Bộ răng là một thể thống nhất thuộc hệ thống nhai tạo thành bởi sự sắp xếp có tổ chức của các cơ quan răng [2]. 1.1.3 Nhu cầu và ứng dụng trong y học 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 [14, 20] trong quá trình này. Khi đó, phân đoạn ảnh nha khoa là bước xử lý then chốt trong nha khoa 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 [55, 56]. Khi đó ứng dụng đầu tiên của phân đoạn ảnh là chẩn đoán bệnh nha khoa. Một trong những ứng dụng thú vị của phân đoạn ảnh nha khoa từ hình ảnh X-quang là giám định pháp y [23], [50], việc giám định pháp y thường sử dụng các công nghệ khoa học để phân tích (trong đó có phân tích răng) trong việc xác định con người, Do đó, nó trở nên quan trọng để đưa ra quyết định xác định hình thái mặt của con người dựa trên các đặc tính: kích thước răng, khoảng cách giữa các răng và các mẫu xoang, xương trên mặt v.v. [50]. Bên cạnh việc giám định pháp y, phân đoạn ảnh nha khoa còn có một số ứng dụng khác: xác định số răng [35], ước lượng tuổi nha khoa [65], phân đoạn ảnh nha khoa có thể phân tích các mảng bám răng [24], v.v. 1.2 Tổng quan về các nghiên cứu liên quan 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 [32, 49]. 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 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 [42], [43]. Khi đó quá trình phân đoạn ảnh là một trong các bước quan trọng và cần thiết để phân tích ảnh X-quang nha khoa cho các quá trình xử lý sau này như: hỗ trợ chẩn đoán [50], xác định các thành phần khác nhau trong ảnh (răng, lợi, tủy v.v.) [51]. (a) (b) Hình 1.1. Ảnh nha khoa (a) Ảnh X-quang nha khoa; (b) Lỗ trống răng bị thiếu Ảnh X-quang nha khoa gồm 3 phần chính (hình 1.1 a) [54]: i) Phần răng: phần có độ xám cao và là phần ta nhìn thấy rõ nhất trên ảnh; ii) Phần cấu trúc răng: là phần có độ xám trung bình gồm lợi răng, xương, phần khác (tủy, xi măng v.v.); iii) Phần nền: là phần có giá trị độ xám nhỏ nhất là nền tảng của cấu trúc răng. Với cấu trúc của ảnh X-quang nha khoa thì việc phân đoạn ảnh phức tạp hơn phân đoạn ảnh thông thường [71]. Nói cách khác, sự kết nối giữa các phần khác nhau của một hình ảnh nha khoa X-quang và chất lượng thấp của hình ảnh do tạp chất, độ tương phản thấp, sai sót về chức năng quét hình ảnh, v.v. làm giảm hiệu suất phân đoạn. Ví dụ, các lỗ trống trong răng bị mất trong (hình 1.1 b) không thể được xử lý bằng kỹ thuật xử lý ảnh dựa trên ngưỡng thông thường [26]. Vì vậy, phương pháp khai phá dữ liệu phân đoạn ảnh X-quang nha khoa đã được nghiên cứu để đạt được độ chính xác cao của phân đoạn [40]. 3 Các phƣơng pháp phân đoạn ảnh Dựa trên điểm ảnh Lấy ngưỡng Dựa trên biên Phát hiện biên Phân cụm Kỹ thuật Gradient Otsu Toàn cục K-Means Đường mức kích hoạt Fuzzy C Means Kích hoạt Dựa trên vùng Xây dựng vùng Phân tách/ Kết hợp Phương pháp đồ thị Tập mức Hình 1.2. Các phương pháp phân đoạn ảnh Hình 1.2 giới thiệu một số phương pháp phân đoạn ảnh [45] dựa trên điểm ảnh, dựa trên biên và dựa trên vùng. Trong phân đoạn ảnh có rất nhiều kỹ thuật khác nhau được sử dụng và các kỹ thuật đó có thể được chia thành 2 loại xu hướng cơ bản là: i) Áp dụng các kỹ thuật xử lý ảnh [13], [37] gồm: phương pháp ngưỡng, các phương pháp dựa biên và dựa trên vùng ; ii) Áp dụng phương pháp phân cụm [46] gồm: K-means [60], Fuzzy C-Means (FCM) [10]. Các phương pháp có sử dụng kỹ thuật xử lý ảnh thường phải biến đổi để biểu diễn ảnh dưới dạng nhị phân, thông qua ngưỡng hoặc sử dụng một đường cong phức tạp để xác định biên. Một phương pháp thường được sử dụng là phương pháp tách ngưỡng Otsu [43]. Các phương pháp này thường gặp vấn đề hết sức khó khăn là xác định tham số ngưỡng hay biên chung của các mẫu răng [59]. Trong khi các phương pháp sử dụng kỹ thuật phân cụm để xác định các cụm thì không cần trước thông tin về ngưỡng và các đường cong. Tuy nhiên các phương pháp này đặt ra một thách thức là việc lựa chọn các tham số và phát hiện biên giữa các cụm [12], [38], [39], [53]. Điều này đặt ra các động lực của việc cải tiến các phương pháp phân đoạn ảnh để đạt được hiệu suất tốt hơn. Các nghiên cứu trước đây [6], [66] cho thấy rằng nếu có thêm thông tin bổ sung kết hợp với quá trình phân cụm thì chất lượng phân cụm được tăng cường. Việc nghiên cứu đề xuất các phương pháp phân cụm bán giám sát mờ với các thông tin bổ trợ là một trong ba loại [70]: các ràng buộc Must-link và Cannot-link, các nhãn lớp của một phần dữ liệu, độ thuộc được xác định trước. Ví dụ, nếu chúng ta biết rằng một điểm ảnh đại diện cho một vùng tương ứng là răng thì ta gãn nhãn cho điểm ảnh vào lớp răng, các điểm ảnh khác trong ảnh X-quang nha khoa được phân cụm cùng với sự hỗ trợ của các điểm ảnh đã biết. Thông tin về điểm ảnh đã biết làm cho kết quả phân đoạn ảnh chính xác hơn. Trong các thuật toán phân cụm bán giám sát mờ được đề xuất trong luận án, thông tin bổ trợ được sử dụng là ma trận thành viên được xác định trước. Đối với loại thông tin này, các thuật toán phân cụm bán giám sát mờ (SSFC) [66], thuật toán phân cụm bán giám sát mờ sử dụng Entropy (eSFCM) [67] có hiệu quả hơn so với thuật toán phân cụm mờ FCM. Trong các thuật toán này, thông tin bổ trợ được tích hợp vào hàm mục tiêu của thuật toán phân cụm bán giám sát mờ FCM. Một ảnh X-quang đầu vào có thể chỉ ra một số bệnh về răng chứ không phải một bệnh duy nhất. Nếu việc chẩn đoán được thực hiện trên từng vùng của ảnh càng chi tiết thì kết quả chẩn đoán cho toàn bộ ảnh càng chính xác. Mục tiêu của phân đoạn từ một hình ảnh X-quang nha khoa là tạo ra nhiều phân vùng khác nhau từ một ảnh đầu vào sao cho các điểm ảnh trong một phân vùng có sự tương đồng cao hơn so với các phân vùng khác. Những ảnh X-quang nha khoa có thể được phân loại theo từng vùng khác nhau cụ thể là vùng nền và vùng cấu trúc răng hoặc vùng có bệnh và vùng không có bệnh [71]. Những vùng này sau đó được so sánh với các tiêu chuẩn bệnh bằng một phương pháp tìm kiếm nhanh để xác định hình ảnh nha khoa có hay không chứa bệnh nha khoa nào. 4 Vấn đề này đã được nghiên cứu rộng rãi trong các công trình [10], [12], [19], [29], [30], [43], [45]. Trong đó, các phương pháp điển hình và phổ biến là phương pháp tách ngưỡng Otsu [43], phân cụm mờ FCM [10], phân cụm bán giám sát mờ theo quy tắc Entropy eSFCM [67]. 1.3 Một số kiến thức cơ sở 1.3.1 Tập mờ Tập mờ [1] được coi là phần mở rộng của tập kinh điển. Nếu X là một không gian nền (một tập nền) và những phần tử của nó được biểu thị bằng x, thì một tập mờ A trong X được xác định bởi một cặp các giá trị: A  ( x,  A x ) | x  X ,0   A x   1 (1.1) Trong đó A(x) được gọi là hàm liên thuộc của x trong A viết tắt là MF. Nó không còn là hàm hai giá trị như đối với tập kinh điển nữa, mà là một hàm với một tập các giá trị hay còn gọi là một ánh xạ. Tức là, hàm liên thuộc ánh xạ mỗi một phần tử của X tới một giá trị liên thuộc trong khoảng [0,1]. 1.3.2 Phân cụm Phân cụm dữ liệu [10] là quá trình nhóm một tập các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương đồng, còn các đối tượng thuộc các cụm khác nhau sẽ ít tương đồng. 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 [10]. 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 lên nhóm các thuật toán gọi là phân cụm bán giám sát mờ [65]. Các thuật toán phân cụm bán giám sát mờ 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 [70] là: i)Các ràng buộc Mustlink và Cannot-link; ii) Các nhãn lớp của một phần dữ liệu; iii) Độ thuộc được xác định trước. Trong luận án tập trung nghiên cứu phân cụm bán giám sát mờ với thông tin bổ trợ là độ 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 [70] đã á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 [66] đã đề 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 [12] 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 u kj . 1.3.3 Phƣơng pháp giải bài toán tối ƣu đa mục tiêu Phương pháp nhân tử Lagrange Phương pháp thỏa dụng mờ 1.4. Kết luận Trong chương này, luận án đã nêu ra bài toán nghiên cứu trong thời gian vừa qua. Qua đó có được cái nhìn tổng quan về bài toán nghiên cứu trong luận án, cụ thể là bài toán phân đoạn ảnh nha kho. Luận án đã trình bày nghiên cứu liên qua trong thời gian qua. Đồng thời trong chương này, luận án đã trình bày lý thuyết về: tập mờ, phân cụm, phương pháp giải tối ưu. Các kiến thức này là nền tảng để giải quyết các bài toán phân đoạn ảnh và chẩn đoán nha khoa mà luận án đang hướng tới. CHƢƠNG 2. MỘT SỐ THUẬT TOÁN PHÂN CỤM BÁN GIÁM SÁT MỜ CHO PHÂN ĐOẠN ẢNH NHA KHOA Trong chương này, luận án trình bày các phương pháp phân cụm bán giám sát mờ mới cụ thể là thuật toán phân cụm bán giám sát mờ lai ghép sẽ được trình bày trong mục 2.1, các kết quả ở mục này đã được công bố tại [CT3]. Thuật toán phân cụm bán giám sát mờ có đặc trưng không gian được trình bày trong mục 2.2. Phương pháp giải tối ưu đa mục tiêu bằng thỏa dụng mờ với bài toán 5 phân cụm bán giám sát mờ có đặc trưng không gian được trình bày trong mục 2.3, các kết quả ở mục này đã được công bố tại [CT5]. Phương pháp xác định thông tin bổ trợ phù hợp cho thuật toán phân cụm bán giám sát mờ có đặc trưng không gian được trình bày trong mục 2.4, các kết quả ở mục này đã được công bố tại [CT2]. Cuối cùng một số đánh giá sẽ được đưa ra trong phần tổng kết chương 2.5. 2.1 Thuật toán phân cụm bán giám sát mờ lai ghép 2.1.1 Lƣợc đồ tổng quan lai ghép Lược đồ tổng quan được thể hiện trong Hình 2.1 dưới đây. Từ một ảnh X-quang có thể có hoặc không có chứa các vùng nền, khi đó sử dụng một thủ tục để kiểm tra điều này trước khi phân đoạn ảnh. Phương pháp Otsu được áp dụng để loại bỏ các khu vực nền từ hình ảnh. Sau đó tiến hành phân cụm mờ (FCM). Các kết quả của quá trình phân cụm là các tâm cụm và ma trận độ thuộc. Khi đó kết quả nhận được là gần đúng với kết quả của bài toán, đồng thời sử dụng các kết quả đó là các thông tin bổ trợ cho các thuật toán phân cụm bán giám sát mờ trong bước tiếp theo. Thuật toán phân cụm bán giám sát mờ (eSFCM) được sử dụng để cải thiện các kết quả của quá trình phân cụm trong giai đoạn xử lý phân đoạn ảnh. 2.1.2 Phƣơng pháp tách ngƣỡng Otsu Phương pháp tách ngưỡng Otsu được giới thiệu trong [43] (Otsu, 1975) và cũng được sử dụng trong [46] bởi Rad, Rahim & Norouzi (2014). Bắt đầu Ảnh đầu vào và các TS tham số Kiểm tra xem ảnh đầu vào có vùng nền hay không? Sai Đúng Dùng phương pháp tách ngưỡng Otsu để loại bỏ vùng nền trong ảnh Dùng thuật toán FCM để loại bỏ các vùng cấu trúc răng từ các kết quả của bước trước Dùng thuật toán eSFCM để làm rõ và cải tiến các kết quả với ma trận độ thuộc được xác định trước từ FCM Đánh giá hiệu năng của thuật toán bằng các tiêu chuẩn khác nhau Các kết quả phân đoạn ảnh Kết thúc Hình 2.1. Lược đồ tổng quan của phương pháp lai ghép 6 2.1.3 Thuật toán phân cụm bán giám mờ lai ghép Bảng 2.1. Thuật toán phân cụm bán giám sát mờ lai ghép Input Ảnh đầu vào, số cụm C, ma trận độ thuộc bổ trợ U ; ngưỡng dừng  ; số lần lặp lớn nhất maxStep> 0 Ảnh phân đoạn Output Lai ghép: 1: Sử dụng phương pháp xử lý ảnh lấy ngưỡng Otsu. 2: Phân cụm mờ (FCM) xác định ma trận độ thuộc UFCM. 3: Xây dựng thông tin bổ trợ U từ ma trận độ thuộc UFCM bỏ đi các giá trị hàm thuộc nhỏ nhất tại các điểm. 4: Phân cụm bán giám sát mờ (eSFCM) với anh đầu vào và thông bổ trợ U 5: Ảnh phân đoạn. 2.1.4 Phân tích và đánh giá thuật toán phân cụm bán giám sát mờ lai ghép Thuật toán được đề xuất trong mục này là một sự kết hợp giữa phương pháp tách ngưỡng Otsu, thuật toán phân cụm mờ FCM và phân cụm bán giám sát mờ (eSFCM). Thuật toán Otsu dùng để tách phần nền với phần chính của ảnh nha khoa. Những thông tin bổ trợ dùng trong eSFCM được xác định là kết quả của ma trận độ thuộc trong phân cụm FCM. Thuật toán eSFCM được sử dụng để phân cụm trong phân đoạn ảnh cuối cùng. Tuy nhiên thuật toán này có một số nhược điểm: chưa sử dụng các đặc trưng của ảnh nha khoa và khi phân cụm chưa sử dụng thành phần không gian trong hàm mục tiêu để tăng độ chính xác. 2.2. Thuật toán phân cụm bán giám sát mờ có đặc trƣng không gian 2.2.1. Lƣợc đồ tổng quát Hình 2.2 dưới đây xác định cơ chế chính của mô hình đề xuất. Đầu vào là một ảnh X-quang nha khoa và với một vài tham số do người dùng xác định. Thuật toán xác định các thông tin bổ trợ của ảnh và đồng thời tiến hành phương pháp phân cụm FCM cũng được sử dụng để phân đoạn các ảnh X-quang nha khoa đầu vào thành cùng một số cụm. Ma trận độ thuộc nhận được từ FCM cùng với các thông tin đặc trưng không gian được sử dụng cho việc tính toán các thông tin bổ trợ cho thuật toán phân cụm bán giám sát mờ mới. Sử dụng thông tin này, việc xây dựng và giải quyết bài toán phân đoạn ảnh nha khoa bằng các thuật toán phân cụm bán giám sát mờ mới (SSFC-SC) được thiết lập. Sau đó thuật toán SSFC-SC lặp lại để sử dụng xác định các tâm cụm và ma trận độ thuộc, xác định ảnh phân đoạn. Cuối cùng, các chỉ số hiệu năng được áp dụng để đánh giá chất lượng của các kết quả đạt được. 7 Ảnh đầu vào và các tham số Trích chọn đặc trưng nha khoa Cơ sở dữ liệu đặc trưng Áp dụng FCM để xác định ma trận độ thuộc xác định trước Xác định thông tin bổ trợ Tri thức chuyên gia Xây dựng một mô hình phân cụm bán giám sát mờ và thuật toán SSFC-SC Ảnh đã được phân đoạn Đánh giá các kết quả bằng các tiêu chuẩn khác nhau Hình 2.2. Lược đồ hoạt động của thuật toán mới 2.2.2 Xây dựng đặc trƣng ảnh nha khoa Luận án giới thiệu 5 đặc trưng cơ bản của một ảnh nha khoa bao gồm: 2.2.2.1 Entropy, giá trị Edge và cường độ(EEI) Những đặc trưng này được sử dụng để mô tả cấu trúc của một ảnh X-quang có thể được phân thành ba vùng tách biệt: vùng nền, vùng cấu trúc răng và các vùng răng [27]. 2.2.2.2 Local Patterns Binary (LBP) Đặc trưng này là một trường hợp đặc biệt của Texture Spectrum [8] Model, được sử dụng để xác định sự khác biệt giữa các phân vùng trong một ảnh X-quang. Đó là bất biến đối với bất kỳ chuyển đổi cường độ ánh sáng và bảo đảm trật tự của mật độ điểm ảnh trong một khu vực nhất định. 2.2.2.3 Red-Green-Blue (RGB) RGB đo màu của một ảnh X-quang, được chia thành ba ma trận theo giá trị Red-GreenBlue. Đối với một hình ảnh được 256 màu sắc, những ma trận đều giống nhau vì cả hai đều đo một hình ảnh màu xám [70]. 2.2.2.4 Đặc trưng Gradient (GRA) Đặc trưng này có thể được sử dụng để phân biệt khác nhau nhỏ giữa các bộ phận răng như men, cementum, xi măng, ống tủy, v..v [18]. 2.2.2.5 Đặc trưng mức Patch (Patch) Đặc trưng này được sử dụng để tính toàn bộ vector gradient với từng điểm ảnh ở mức patch, được biểu thị bởi δ(z) [20]. 2.2.3 Xác định thông tin bổ trợ Cách xác định các thông tin bổ trợ cho thuật toán mới SSFC-SC: - Bước 1: Từ ma trận độ thuộc tối ưu của FCM, xác định giá trị độ thuộc tối thiểu cho mỗi điểm dữ liệu và các thiết lập u1. 8 - Bước 2: Dựa vào các đặc trưng của ảnh nha khoa tại mục 2.2.2, khi đó ta ký hiệu là pw1, pw2, pw3, pw4, pw5 để tính toán giá trị đặc trưng của ảnh nha khoa tương ứng (pwi là giá trị đặc trứng thứ i mỗi điểm ảnh). Chuẩn hóa các đặc trưng của ảnh nha khoa ta xác định được trọng số đặc trưng của từng điểm ảnh: pwi . wi  (2.1) maxpwi  - Bước 3: Tính toán thông tin đặc trưng: l w u2  i 1 i . (2.2)  l  max wi   i 1  - Bước 4: Tổng hợp các mức của độ thuộc ở bước 1 và 3 để có được các thông tin bổ trợ như sau. when u1  u 2 u1 , , u kj   (2.3) when u1  u 2 u 2 , Trong đó   0,1 là kiến thức của chuyên gia trợ giúp cho việc xác định thông tin bổ trợ cho quá trình phân cụm bán giám sát mờ mới. 2.2.4 Thuật toán phân cụm bán giám sát mờ SSFC-SC 2.2.4.1 Mô hình hóa phân đoạn ảnh nha khoa N C J   u kjm X k  V j k 1 j 1 2 N C N C   u kjm Rkj2   u kjm k 1 j 1 k 1 j 1 N C 1 l wik   u kj  u kj  l i 1 k 1 j 1 m X k Vj 2  min (2.4) Với ràng buộc: C  ukj  1; j 1 u kj  0,1; C k  1, N ; u j 1  1; kj ukj  0,1; k  1, N (2.5) Trong đó:  m là số mờ hóa, m>0 ;  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  0,1 là độ thuộc của phần tử dữ liệu Xk từ cụm j, ;  X k  R r là phẩn tử thứ k của X  X1 , X 2 ,..., X N  ;  Vj là tâm của cụm j;  l: số lượng các đặc trưng;  wik: trọng số các đặc trưng;  Rkj: hàm xác định khoảng cách không gian từ điểm Xk đến tâm Vj. 2.2.4.2 Giải bài toán bằng phương pháp nhân tử Lagrange Để giải bài toán (2.4-2.5), ta sử dụng phương pháp nhân tử Lagrange như sau: Lấy đạo hàm của (2.4) theo V, ta được được nghiệm của bài toán: N N J  2 u kjm ( X k  V j )  2 u kjm u kj  u kj ( X k  V j ) . V j k 1 k 1 (2.6) Cho các đạo hàm bằng không, xác định được các tâm cụm.  u N Vj  k 1 N m kj   u kj  u kj x k . (2.7) N  C  L(U )  J    k   u kj  1 k 1  j 1  (2.8)  u k 1 m kj  u kj  u kj  Với hàm Lagrange được xác định là 9 L  mu kjm 1 X k  V j u kj 2  1 l   mu kjm 1 Rkj2  mu kjm 1   wik   m u kj  u kj  l i 1   m 1 X k Vj 2  k (2.9) Khi m=2, ta xác định công thức tính độ thuộc:  k  2u kj X k  V j u kj   2* 2 X k V j  Từ ràng buộc (2.40), ta có 2 2 1 l   R   wik  l i 1  . (2.10) 2 kj   2   C u X  V kj k j    K     1 l 2 1    j 1  2 X k  V j  Rkj2   wik     l i 1        C    j 1 2 2 X k  V j    2   1  l 1   Rkj2   wik   l i 1  (2.11) Kết hợp (2.10) và (2.11), ta xác định ma trận thành viên. Các nghiệm thu được khi giải bằng phương pháp nhân tử Lagrange của mô hình này là các tâm cụm trong phương trình (2.7) và ma trận độ thuộc xác định trong phương trình (2.10), (2.11). 2.2.5 Phân tích và đánh giá thuật toán SSFC-SC Trong mục này ta đã đưa ra thuật toán SSFC-SC mới. Khi đó thuật toán mới có sử dụng các thông tin đặc trưng không gian của ảnh nha khoa, phân cụm mờ. Thuật toán SSFC-SC có một số ưu điểm: i) Thuật toán SSFC-SC sử dụng các thông tin bổ trợ từ những kết quả của FCM và thông tin đặc trưng không gian của ảnh để có chất lượng tốt hơn so với phân cụm bán giám sát mờ eSFCM hay phân cụm mờ FCM. Các đánh giá dựa trên các kết quả thực nghiệm với các đo đo của phân cụm được trình bày ở chương 3. ii) Thuật toán SSFC-SC không mở rộng số lượng các thông số. Một số thông số khác của SSFC-SC như kích thước cửa sổ không gian thích ứng trong mục 2.2.4.1 cũng được tự động xác định trong quá trình phân cụm. Vì vậy, điều này làm cho thuật toán hiệu quả hơn trong điều kiện của tham số kiểm soát. iii) Thuật toán SSFC-FC có thể kết hợp giữa kiến thức của chuyên gia nha khoa để thu được kết quả tốt nhất. Tuy nhiên thuật toán vẫn còn có một số nhược điểm: Việc sử dụng thông tin bổ trợ không phải lúc nào cũng tốt với các ảnh khác nhau, cần cung cấp cách lựa chọn để sao cho hàm mục tiêu luôn tốt nhất với từng ảnh phân đoạn; Nghiệm thu được bằng cách giải tối ưu đa mục tiêu theo phương pháp nhân tử Lagrange mức hội tụ không ổn định, có một số trường hợp sự hội tụ chậm dẫn đến nghiệm thu được chưa hội tụ về nghiệm tối ưu toàn cục. 2.3 Thuật toán phân cụm bán giám sát mờ dựa trên thỏa dụng mờ 2.3.1 Thuật toán phân cụm bán giám sát mờ (SSFC-FS) Trên cơ sở bài toán (2.4)-(2.5), một thuật toán mới được đề xuất có tên là thuật toán phân cụm bán giám sát mờ với ràng buộc không gian dùng phương pháp thỏa dụng mờ (Semi-Supervised Fuzzy Clustering algorithm with Spatial Constraints using Fuzzy Satisficing hay SSFC-FS). Phân tích bài toán Theo công thức (2.4), hàm mục tiêu của bài toán có dạng J  J1  J 2  J 3  min . (2.12) N C J 1   u kjm X k  V j 2 (2.13) k 1 j 1 N C N C J 2   u kjm R 2jk   u kjm k 1 j 1 N k 1 j 1 C J 3   ukj  u kj m k 1 j 1 10 1 l  wik l i 1 X k Vj (2.14) 2 (2.15) Với các thành phần hàm mục tiêu được viết tường minh trong các công thức (2.13), (2.14), (2.15). Áp dụng định lý Weierstrass, sự tồn tại nghiệm tối ưu của bài toán trên được thể hiện trong bổ đề dưới đây: Bổ đề 2.1 Bài toán tối ưu đa mục tiêu (2.4)-(2.5) có hàm mục tiêu liên tục trên một tập compact khác rỗng. Do đó bài toán có phương án tối tu toàn cục liên tục và bị chặn. Trên cơ sở bổ đề 2.1 và phương pháp thỏa dụng mờ tương tác, việc tìm nghiệm tối ưu của bài toán được thực hiện như sau: Xác định nghiệm tối ƣu của bài toán: Bước khởi tạo: Giải các bài toán con bằng phương pháp nhân tử Lagrange, nghiệm tương ứng nhận được là u1 , u 2 , u 3 : Ký hiệu: (2.16) z i  minzhi , h  1,2,3, z i  maxzhi , h  1,2,3, i = 1, 2, 3. (2.17) S  u1 , u 2 , u 3 , t =1, a t   z . p   i i Bước lặp: t = 1  Bước 1: Hàm thỏa dụng mờ cho các bài toán con được xây dựng theo công thức sau: J z J z J z 1 ( J1 )  1 1 ; 2 ( J 2 )  2 2 ; 3 ( J 3 )  3 3 . (2.18) z2  z2 z3  z3 z1  z1 Trên cơ sở các hàm này, ta có hàm thỏa dụng tổ hợp như sau: Y  b11 ( J1 )  b2 2 ( J 2 )  b33 ( J 3 )  min , (2.19) Trong đó: b1  b2  b3  1 và 0  b1, b2 , b3  1 . (2.20) Bổ sung ràng buộc dưới đây: J i ( x)  ai( r ) , i  1, 2, 3. . (2.21)  bz b1 b2 b3 b z bz  J1  J2  J 3   1 1  2 2  3 3  . z1  z1 z2  z2 z3  z3  z1  z1 z 2  z 2 z 3  z 3  Lấy đạo hàm của Y trong (2.22) theo ukj b3 J 3 b1 J 1 b2 J 2 Y      k , k  1, N , j  1, C . u kj z 1  z 1 u kj z 2  z 2 u kj z 3  z 3 u kj Y (2.22) (2.23) Với mỗi bộ ( b1, b2 , b3 ) thỏa mãn (2.20), nghiệm tối ưu của bài toán là u t   u kj( t ) C N  Bước 2: - Nếu min  mini ( J i ), i  1,...,3   , với  là một ngưỡng do người dùng chọn thì u (t ) không là phương án chấp nhận được. Ngược lại, ta kiểm tra xem nếu u (t )  S p thì bổ sung u (t ) vào Sp . - Nếu cần mở rộng tập S p thì ta tăng t (t=t+1) và kiểm tra điều kiện sau: Nếu t > L1 hoặc là sau L2 lần lặp liên tiếp (L1, L2 là các giá trị tùy ý) mà tập S p không kết nạp thêm nghiệm nào thì đặt ait   z i , i  1, 2, 3 và lấy 1 chỉ số h bất kỳ từ tập {1, 2, 3} để gán aht   z h , z h  rồi lặp lại bước 1. - Nếu không cần mở rộng tập S p thì chuyển sang bước 3.  Bước 3: - Kết thúc thuật toán. Công thức nghiệm của bài toán được chỉ ra trong bổ đề sau: Bổ đề 2.2 Với bộ tham số b1, b2 , b3  đã cho, nghiệm u (r ) của bài toán cực tiểu hóa hàm mục tiêu Y trong (2.65) được xác định thỏa mãn đẳng thức: 11 b3 J 3 b1 J 1 b2 J 2 Y      k  0, j  1, C , k  1, N , u kj z 1  z 1 u kj z 2  z 2 u kj z 3  z 3 u kj ukj(t ) (2.24) b3t   t   d kj  ukj  k z3  z 3 2  , j  1, C , k  1, N  t  t  b1 b3  b2t   d kj     kj z  z z  z z  z 1 3 2 1 3 2   (2.25) 2  b1t  b3t  (t ) 2   u  u kj( t )  u kj  X k  kj z z z3  z 3 k 1  .  N 1 t1 t  2  b1 2 b   u kj( t )  3 u kj( t )  u kj   z  z z  z k 1  1 1 3 3  (2.26) V (t ) j    N      b3t   d kj  u jk C z3  z 3 1  t  b3t   b2t  j 1  b1    d kj  z  z   kj 2 Với  t   2   z1  z 1 z3  z 3  2 , k  1, N k C 1  t  b t   b r  j 1  b1   3 d kj  2   kj z2  z 2  z1  z 1 z3  z 3  (2.27) 2.3.2. Các tính chất và hệ quả từ phân tích nghiệm của thuật toán Các tính chất, các bổ đề, các mệnh đề, các định lý sau đã được chứng minh. Từ công thức tâm cụm V jt  trong (2.26), dễ dàng suy ra được các tính chất và các mệnh đề sau: Tính chất 2.1 Trong trường hợp b2  1, b1  b3  0 , các tâm cụm là không xác định. Tính chất 2.2 Nghiệm u (r ) tìm được là liên tục và bị chặn bởi b1, b2 , b3  . Mệnh đề 2.1 Với mọi giá trị của bộ tham số b1, b2 , b3  , từ công thức nghiệm trong (2.25) ta có:  b t    t  b3t  b t   b3t  b2t   d kj  u kj   1  3 d kj    kj   k   d kj  u kj , j  1, C , k  1, N z3  z 3 z2  z 2 2 z3  z 3  z1  z 1 z 3  z 3   . (2.28) Khi so sánh nghiệm tìm được theo phương pháp thỏa dụng mờ với nghiệm tìm được theo phương pháp nhân tử Lagrange, xét bài toán tối ưu (2.4) - (2.5) ta có thể nhận thấy rằng nghiệm nhận được từ phương pháp Lagrange là nghiệm tối ưu cục bộ. Mệnh đề 2.2 Nghiệm tối ưu của bài toán đã cho được xác định theo công thức sau:  u N Vj  k 1 N m kj  u k 1   u kj  u kj x k m kj  u kj  u kj  , u kj   2  u kj X k  V j  C K    l 2  j 1  2 X k  V j  R kj2  1  wik  l i 1     k  2u kj X k  V j  2*2 X k Vj     1       2  Rkj2     C    j 1 2 2 X k  V j    2 2 1 l  wik   l i 1    1 .  l 1   R kj2   wik   l i 1  (2.29) (2.30) Để đánh giá nghiệm theo phương pháp thỏa dụng mờ (FS) và phương pháp Lagrange (LA), ta dụng chỉ số IFV [64] với giá trị IFV cao hơn là nghiệm tốt hơn. Cụ thể, công thức tính chỉ số IFV như sau: 2 (2.31) 1 C  1 N 2  1 N   SDmax , IFV     ukj log2 C   log2 ukj    C j 1  N k 1 N k 1     D 12 (2.32) 1 C 1 N  d     kj k j C j 1  N k 1  Ký hiệu IFV(LA) là giá trị của chỉ số IFV của nghiệm tối ưu dùng phương pháp Lagrange và tương ứng cho nghiệm theo phương pháp thỏa dụng mờ là IFV(FS). 2 2  k   k    d kj u kj   d kj u kj     N 1 C 1 N 2  log C  1 2    SDmax , IFV LA       log 2  2   (2.33)  C j 1  N k 1  2d kj   kj   N k 1 2d kj   kj    D 2 SDmax  max Vk  V j ,  D   IFVFS         2 2  k k      w d u  w d u    3 kj kj 3 kj kj    SDmax 1 C  1 N 1 N 2 2  log2 C   log2        C j 1  N k 1  w1  w3 d kj  w2 kj   N k 1 w1  w3 d kj  w2 kj    D         (2.34) Bổ đề 2.3 Trong phương pháp Lagrange, tham số k được xác định theo công thức (2.30). Do đó, để so sánh nghiệm Lagrange với nghiệm thỏa dụng mờ, các tham số b1, b2 , b3  được chọn thỏa mãn:    d kju kj  k 2   2d kj   kj      d kju kj  k   N 2    log 2 C  1  log 2 N k 1 2d kj   kj             (2.35)     b3  b3 k     d kju kj  k d u  kj kj     z3  z 3 2 z3  z 3 2 1 N     log 2 C   log 2 , N     b b b b b b k  1 3 3 1 2 1 2      d kj    kj    z  z  z  z d kj  z  z  kj   z  z z  z z  z 2 2 2 2  1 1 3 3  1 1 3 3     l 1  kj  Rkj2   wik ,  j  1, C , k  1, N (2.36) l i 1 Định lý 2.1 Với các giá trị trong bộ tham số b1 , b2 , b3  cho trước thỏa mãn các điều kiện trong bổ đề 2.3 ta có: LA FS (2.37) IFV  - IFV   0 Tính chất 2.3 Các nghiệm tối ưu nhận được theo phương pháp thỏa dụng mờ là tốt hơn nghiệm tối ưu nhận dược theo phương pháp Lagrange. Giá trị mà chỉ số IFV có thể nhận đối với nghiệm nhận được theo phương pháp thỏa dụng mờ tại bước lặp thứ t được chỉ ra bằng cận dưới và cận trên như dưới đây: Định lý 2.2 Cận dưới của giá trị chỉ số IFV đối với nghiệm tối ưu u  u (t ) theo phương pháp thỏa dụng mờ được đánh giá bởi công thức: IFV FS   1 SDmax 2   log 2 C  2 C D Để đánh giá được cận trên, ta định nghĩa giới hạn L như sau:   b3  d kju kj  k N  z3  z 3 2   L  lim  log 2  u kj 0  b1 b3  b2  k 1  d kj    kj    z2  z 2  z1  z 1 z 3  z 3    Bổ đề 2.4 Với mọi giá trị của bộ tham số b1 , b2 , b3  , ta luôn có: 13 (2.38) (2.39)   b3 k b3 k d u  d u  N  kj kj kj kj N z3  z 3 2 z3  z 3 2   log 2  lim  log 2   L (2.40)  ukj 0  b1   b3  b b2 b b k 1 k  1   d kj   1  3 d kj  2  kj    kj  z2  z 2 z 2  z 2   z1  z1 z3  z 3   z1  z1 z3  z 3   Định lý 2.3 Cận trên của chỉ số IFV đối với nghiệm tối ưu nhận được theo phương pháp thỏa dụng mờ được đánh giá theo công thức: IFV FS   2 1 SDmax  L    log2 C   . C N D  (2.41) Hệ quả 2.1: Từ bất đẳng thức Cauchy–Schwarz được dùng trong các phép biến đổi trên, dấu bằng xảy ra khi: b3  d kj u kj  k z3  z 3 2  b1 b3  b2  d kj    kj z2  z 2  z1  z 1 z 3  z 3   constant L log 2 C  N Với ràng buộc trong (2.40), ta có thể viết lại như sau: b3  d kju kj  k z3  z 3 2 1  (2.42) L  b1 b3  b2  d kj    kj log 2 C  N z2  z 2  z1  z 1 z 3  z 3  Kết quả trong hệ quả 2.1 được cụ thể trong một số trường hợp đặc biệt sau: - Giả sử rằng b2 là một hằng số khác 1, ta có thể biểu diễn b1 và b3 dưới dạng: b1  1  b2  b3 ,0  b1, b2 , b3  1, b2  1, b2 = constant. Với ký hiệu: (2.43)   kj   1  d kj L  ukj 1  L  H kj   log 2 C        d kj , Ekj    , P   log 2 C   N  z3  z 3  z1  z1 z3  z 3   N   z1  z1 z2  z 2   C B b Akj b3 1  Ekj b2  Fkj ,   C 1 2  j 1 Bkj b3  Ekj b2  Fkj k Akj  d kj u kj z3  z 3 , j 1 kj 3  1 1  d kj , Bkj     z 3  z 3 z1  z 1  (2.44) Fkj   d kj z1  z 1 (2.45) M kj  H kj  PAkj , Trong trường hợp này, ta có thể biểu diễn b3 qua b2 như sau: b3  G kj  PE kj b2  Fkj  Fkj P (2.46) PE kj b2  M kj  Fkj P Giá trị của các tham số: b3  [0, 0.2] b1  [0.1, 0.4], b2  [0.3, 0.7]. Thứ 4, sự khác nhau về nghiệm nhận được từ 2 lần lặp liên tiếp trong quá trình thực hiện thuật toán được đánh giá sử dụng các ký hiệu: 8 1  b3r b1r 1  b1r b3r 1 ,  2  b3r b2r 1  b2r b3r 1 ,  3  r  r 1 (2.47) k k Định lý sau đây thể hiện sự chênh lệch về nghiệm giữa 2 lần lặp liên tiếp. 14 Định lý 2.4 [CT5] Khi các tham số của lần lặp thứ r và thứ r + 1 được xác định tương ứng là b1r  , b2r  , b3r   và b1r1 , b2r1 , b3r1  như trong Bổ đề 2.4, sự khác biệt giữa nghiệm tối ưu tìm được trong 2 lần lặp liên tiếp này được đánh giá bởi công thức: 2   d ukj1 d kj ukj kj  2   kj r 1 r   3 . ukj   ukj     (2.48)   z1  z1  z3  z 3 2  z2  z 2  z3  z 3     Hệ quả 2.2: Điều kiện dừng của thuật toán khi dùng phương pháp thỏa dụng mờ là u kjr 1  u kjr    . (2.49) 2.3.3 Phân tích và đánh giá thuật toán SSFC-FS - Hiệu quả của phương pháp mới đã được xác nhận trên lý thuyết đã trình bày trong mục 2.3.3 và cụ thể chất lượng phân cụm của thuật toán sử dụng phương pháp thỏa dụng mờ là tốt hơn so với sử dụng Lagrange. - Thuật toán mới đã được trang bị với những phân tích lý thuyết chặt chẽ. Nhiều định lý và các mệnh đề đã được trình bày. - Chất lượng phân cụm của phương pháp mới (SSFC-FS) là tốt hơn so với các thuật toán sử dụng Lagrange (SSFC-SC) i) Các giới hạn trên và dưới của chỉ số IFV của các nghiệm tối ưu được thể hiện trong phương trình (2.38, 2.41) ii) Điều kiện dừng tổng quát của phương pháp SSFC-FS được đưa ra Tuy nhiên một số nhược điểm của phương pháp này là: thời gian thực hiện thuật toán dài và việc sử dụng một cách xác định thông tin bổ trợ nhiều khi không phù hợp với các ảnh khác nhau. 2.4 Xác định thông tin bổ trợ phù hợp cho thuật toán SSFC-FS 2.4.1 Lƣợc đồ tổng quát Hình 2.3 minh họa cơ chế chính của phương pháp SSFC-FSAI. Dữ liệu đầu vào của phương pháp này là một ảnh X-quang nha khoa. Ảnh này được phân cụm theo thuật toán FCM và sau đó được trích chọn các thông tin đặc trưng. Từ những kết quả đạt được, một ma trận độ thuộc được xác định trước phù hợp và các thông số của nó được tính tự động cho từng ảnh nha khoa nhất định. Hàm lựa chọn thông tin bổ trợ này sau đó được sử dụng để tính toán các kết quả đầu ra cuối cùng của mô hình phân cụm bán giám sát mờ (sẽ được trình bày trong mục 2.4.2 dưới đây). Các hình ảnh phân đoạn được đánh giá theo những tiêu chí khác nhau. 2.4.2 Xây dựng tập các hàm thông tin bổ trợ Trong phần này, một số hàm thông tin bổ trợ [1] được giới thiệu bao gồm: + Hàm Gaussian + Hàm Bell + Hàm Sigmoid + Hàm sin Hyperbolic + Hàm Gudermannian + Hàm Fresnel + Hàm sóng tam giác Và một vài hàm được đề xuất + Hàm hỗn hợp: Hàm của SSFC-FS khi u1  u 2 u , ,   0,1 , j  1, C , k  1, N u kj   1 (2.50) khi u1  u 2 u 2 , l u2  w i 1 i  l  max  wi   i 1  Trong đó u1 được xác định là độ thuộc xác định khi sử dụng phân cụm mờ (FCM) + Hàm không gian: 15 (2.51) khi u kj  max i 1,C u ki  u 2 ,   0,1 , j  1, C , k  1, N u kj   khi u kj  max i 1,C u ki  0 Với u2 được định nghĩa từ các giá trị đặc trưng trong mỗi điểm ảnh. + Hàm phân cụm mờ: khi u kj  max i 1,C u ki   u kj ,   0,1 , j  1, C , k  1, N u kj     0 khi u  max u  kj ki i  1 , C  ukj nhận được bằng cách sử dụng phương pháp FCM. Phân đoạn ảnh bằng phương pháp FCM Xây dựng thông tin bổ trợ (2.53) Ảnh đầu vào và các tham số Xây dựng dữ liệu CSDLvề các thông tin bổ trợ (2.52) Trích chọn đặc trưng Xác định thông tin bổ trợ Chọn thông tin bổ trợ thích hợp nhất Phân cụm bán giám sát mờ sử dụng thông tin đặc trưng không gian (SSFC-SC) Ảnh phân đoạn Tri thức chuyên gia Đánh giá các kết quả dựa vào các chỉ số Hình 2.3. Sơ đồ khối của phương pháp SSFC-FSAI 2.4.3 Xác định hàm thông tin bổ trợ phù hợp cho dữ liệu ảnh nha khoa Bước 1: Dùng phương pháp FCM để phân đoạn ảnh đầu vào nhận được U, V. Bước 2: Tính toán hàm chỉ số đánh giá IFV Bước 3: Tính toán các giá trị của ma trận độ thuộc ứng với các giá trị IFV lớn nhất. Bước 4: Chọn ma trận độ thuộc và các giá trị tham số của nó như là một hàm bổ trợ. 2.4.4 Phân tích và đánh giá thuật toán SSFC-FSAI Thuật toán mới đề xuất có các ưu điểm sau: Thứ nhất, SSFC-FSAI tốt hơn so với SSFC-FS về chất lượng cụm. Trong đó, mỗi ảnh nha khoa được xử lý với một hàm bổ trợ khác nhau sao cho nó phù hợp nhất với ảnh đầu vào và do đó tăng độ chính xác tổng thể. Thứ hai, SSFC-FSAI tự động xác định các giá trị tham số cho chất lượng cao nhất của thuật toán phân cụm. Thứ ba, các thành phần mới mới kết hợp với các giai đoạn cũ một cách thống nhất, hỗ trợ một cách hiệu quả trong chẩn đoán y tế. 2.5 Kết luận Chương 2 đã trình bày các thuật toán phân cụm bán giám sát mờ trong phân đoạn ảnh nha khoa. Cụ thể là các thuật toán: phân cụm mờ bán giám sát lai ghép; phân cụm mờ bán giám sát mờ có sử dụng các thông tin đặc trưng không gian của ảnh nha khoa (SSFC-SC); sử dụng phương pháp giải tối ưu bằng thỏa dụng mờ cho phân cụm bán giám sát mờ có sử dụng các thông tin đặc trưng không gian của ảnh nha khoa (SSFC-FS); cuối cùng là cách xác định thông tin bổ trợ thích hợp nhất cho phương pháp SSFC-FS (SSFC-FSAI). 16 CHƢƠNG 3. ĐÁNH GIÁ THỰC NGHIỆM Chương 3 của luận án trình bày các kết quả thực nghiệm thu được khi cài đặt các thuật toán phân cụm bán giám sát mờ đề xuất ở chương 2 trên bộ dữ liệu ảnh X-quang nha khoa. Trong đó có phân tích dữ liệu sử dụng và các tiêu chí đánh giá thông qua các độ đo, từ đó xác định các kết quả này được sử dụng để đánh giá hiệu năng của các thuật toán đề xuất và so sánh với các thuật toán khác đã được nghiên cứu gần đây cho các bài toán tương tự. 3.1 Mô tả dữ liệu ảnh X-quang nha khoa 3.1.1 Đặc tả dữ liệu Bộ dữ liệu bao gồm 66 ảnh X-quang nha khoa được chụp từ máy chụp X-quang VATECH tại Bệnh viện Đại học Y Hà Nội, Việt Nam trong khoảng 2014 – 2015 của các bệnh nhân thuộc độ tuổi từ 16 đến 38 được chia thành 5 nhóm bệnh. Thống kê thông tin về bệnh nhân được chỉ ra như trong Bảng 3.1 dưới đây: Bảng 3.1. Thông tin về các nhóm bệnh nhân Giới tính Tuổi Số bệnh Nhóm bệnh nhân nhân Nam Nữ 16-22 23-30 31-38 Nhóm gãy chân răng 12 6 6 0 4 8 Nhóm răng mọc ngầm 15 8 7 3 6 6 Nhóm sâu răng 12 5 7 5 2 5 Nhóm thiếu răng 12 6 6 5 4 3 Nhóm tiêu xương 15 8 7 2 6 7 Tổng 66 33 33 15 22 29 3.1.2 Xác định các đặc trƣng của ảnh nha khoa Bằng việc trích chọn các đặc trưng cơ bản, ta có bộ dữ liệu đặc trưng của 66 ảnh. Bảng 3.2 trình bày các thống kê của từng đặc trưng trong tất cả các ảnh thuộc cơ sở dữ liệu ảnh nha khoa. Bảng 3.2. Thống kê các ảnh trong toàn bộ dữ liệu ảnh X-quang. Giá trị lớn Giá trị nhỏ Đặc trƣng Kỳ vọng Độ lệch Trung vị nhất nhất 44.02 3.25 51.12 31.58 43.97 EEI-M 153.31 2.29 157.07 147.25 153.84 LBP-M 117.48 9.19 139.03 82.94 117.83 RGB-M 0.42 0.0192 0.45 0.33 0.42 Gradient-M 0.026 0.004 0.033 0.19 0.26 Patch-M 3.2 Độ đo và tiêu chí đánh giá kết quả Mục đích: Các độ đo được sử dụng để đánh giá độ chính xác của các thuật toán phân đoạn ảnh. Từ đó tìm ra các giá trị thích hợp nhất cho các tham số cho phân đoạn các ảnh nha khoa. Tác giả luận án sử dụng các độ đo phân cụm [69] sau: PBM, IFV, DB, SSWC, TRA, BH, BR, VRC 3.3 Các kết quả so sánh phân đoạn ảnh Dựa trên bộ dữ liệu về ảnh X-quang nha khoa, các thuật toán được đề xuất trong các chương 2 (thuật toán eSSFCM-OTSU [CT3], SSFC-SC, SSFC-FS [CT5], SSFC-FSAI [CT2]) với các thuật toán đã có từ trước (FCM [10], OTSU[48], eSFCM[75]) được cài đặt thực nghiệm cùng với các thuật toán xử lý ảnh và các thuật toán phân cụm mờ có liên quan. 3.3.1 Kết quả trên tập cơ sở dữ liệu ảnh nha khoa Dựa trên kết quả tính toán giá trị của các độ đo trên từng ảnh, kỳ vọng và phương sai của các giá trị tương ứng với từng độ đo trên mỗi thuật toán được tính toán. Bên cạnh đó, để so sánh một cách định lượng các giá trị độ đo giữa các thuật toán đã được tính toán, giá trị trung bình tốt nhất trên mỗi dòng (ứng với từng độ đo) được ghi là 1 từ đó tính toán số lần mà thuật toán tốt nhất tốt hơn các thuật toán còn lại trên các dòng tương ứng với từng độ đo. Kết quả thống kê được trình bày trong Bảng 3.3 dưới đây. 17 Số lần tốt hơn PBM DB IFV SSWC Bảng 3.3. So sánh hiệu năng của các thuật toán trên bộ dữ liệu thực (Giá trị 1 được in đậm chỉ ra độ đo tốt nhất) SSFCFCM OTSU eSFCM eSFCM-Otsu SSFC-FS SC SSFCFSAI 1.58 1.01 62.01 2.01 1.31 1.58 1.32 1.33 1.00 1.26 21.89 1.28 1.08 1.00 1.04 1.16 1.38 1.29 Inf 1.93 1.80 2.78 1.67 2.79 1.80 1.08 4.34 1.96 1.33 1.53 1.32 1.27 6.14 1.00 1.00 2.20 1.51 2.01 1.47 1.45 1.06 1.23 41.29 1.18 1.08 1.39 1.00 1.15 1.11 1.27 36.76 1.00 1.00 1.10 1.09 1.00 VRC BH BR TRA Kết quả phân cụm trên bộ dữ liệu ảnh X-quang nha khoa được minh họa bởi hình 3.1. (a) Ảnh gốc (b) Tách ngưỡng OTSU (c) Phân đoạn FCM (d) Phân đoạn eSFCM (h) Phân đoạn SSFC(f) Phân đoạn SSFC- (g) Phân đoạn SSFCFS FSAI SC Hình 3.1. Ảnh phân đoạn 3.3.2 Kết quả với các tham số thay đổi Xác định các tham số thích hợp nhất: Mục này trình bày phương pháp xác đinh giá trị các tham số (số cụm và giá trị  ) thích hợp nhất với các ảnh đầu vào theo nghĩa thuật toán SSFC-SC đạt hiệu năng cao nhất. Trong phần trước, số cụm được cố định là C = 3 và giá trị  = 0.9. Để biết rõ sự thay đổi của thuật toán SSFC-SC theo các tham số này, các kết quả thực nghiệm trên bộ dữ liệu ảnh nha khoa với các giá trị  thay đổi được. Các kết quả số đã chỉ ra rằng khi giá trị của  càng lớn, nghĩa là thông tin bổ trợ được sử dụng càng nhiều, thì hiệu năng của thuật toán SSFC-SC cao hơn. Để xác nhận điều này, thuật toán SSFC-SC được cài đặt thực nghiệm trên cùng bộ dữ liệu với trường hợp trước chỉ thay số cụm C =5 cùng với  thay đổi. Kết quả của thực nghiệm này cũng cho kết luận như đối với trường hợp C = 3. Tương tự như vậy, khi cố định  = 0.9, các chỉ số khi thực nghiệm với các phương pháp này đối với các giá trị C, m thay đổi (C = 3, 5, 7 và m = 2, 4, 6) được ghi lại và có thể thấy rằng, đối với thuật toán SSFC-SC, các giá trị nhỏ của bộ tham số (m, C) cho hiệu năng cao hơn mặc dù thuật toán này vẫn có kết quả tốt hơn các thuật toán khác trong những trường hợp giá trị của các tham số này là chưa tốt. Từ chứng minh trong mục 2.2.4, chúng ta biết rằng, bài toán tối ưu (2.4-2.5) là lồi và có nghiệm tối ưu khi m = 2. Độ chính xác của các phương pháp phân cụm với số cụm thay đổi, số cụm được chọn phù hợp nhất là C = 3. Do đó các gợi ý về việc chọn tham số là phù hợp với các thực nghiệm đã được trình bày. Để có cái nhìn trực (e) Phân đoạn eSFCMOTSU 18