ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÊ THỊ MAI HƯƠNG
NGHIÊN CỨU MỘT SỐ THUẬT TOÁN
PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT VÀ ỨNG DỤNG
PHÂN ĐOẠN ẢNH X-QUANG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÊ THỊ MAI HƯƠNG
NGHIÊN CỨU MỘT SỐ THUẬT TOÁN
PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT VÀ ỨNG DỤNG
PHÂN ĐOẠN ẢNH X-QUANG
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Giáo viên hướng dẫn: TS.Nguyễn Đình Dũng
THÁI NGUYÊN - 2017
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng dẫn
khoa học của TS. Nguyễn Đình Dũng, các kết quả lý thuyết được trình bày trong
luận văn là sự tổng hợp từ các kết quả đã được công bố và có trích dẫn đầy đủ,
kết quả của chương trình thực nghiệm trong luận văn này được tác giả thực hiện
là hoàn toàn trung thực, nếu sai tôi hoàn toàn chịu trách nhiệm.
Thái Nguyên, tháng 6 năm 2016
Học viên
Lê Thị Mai Hương
i
LỜI CẢM ƠN
Luận văn này được hoàn thành tại Trường Đại học Công nghệ Thông tin
và Truyền thông dưới sự hướng dẫn của TS. Nguyễn Đình Dũng. Tác giả xin
bày tỏ lòng biết ơn tới các thầy cô giáo thuộc Trường Đại học Công nghệ Thông
tin và Truyền thông, các thầy cô giáo thuộc Viện Công nghệ Thông tin – Viện
Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tác giả
trong quá trình học tập và làm luận văn tại Trường, đặc biệt tác giả xin bày tỏ
lòng biết ơn tới TS. Nguyễn Đình Dũng đã tận tình hướng dẫn và cung cấp
nhiều tài liệu cần thiết để tác giả có thể hoàn thành luận văn đúng thời hạn.
Xin chân thành cảm ơn anh chị em học viên cao học và bạn bè đồng
nghiệp đã trao đổi, khích lệ tác giả trong quá trình học tập và làm luận văn tại
Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên.
Cuối cùng tác giả xin gửi lời cảm ơn đến gia đình, những người đã luôn
bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề tài.
Thái Nguyên, ngày tháng năm 2017
Học viên
Lê Thị Mai Hương
ii
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................ i LỜI CAM ĐOAN ................................................................................................... i DANH MỤC TỪ VIẾT TẮT ................................................................................ v DANH MỤC HÌNH VẼ ....................................................................................... vi LỜI MỞ ĐẦU ....................................................................................................... 1
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU VÀ BÀI TOÁN PHÂN ĐOẠN ẢNH X-QUANG NHA KHOA ................................................. 3 1.1. Khai phá dữ liệu ........................................................................................ 3 1.1.1. Khái niệm khai phá dữ liệu ................................................................ 3 1.1.2. Quá trình khai phá tri thức trong cơ sở dữ liệu .................................. 3 1.1.3. Các kỹ thuật tiếp cận trong khai phá dữ liệu: ........................................ 5 1.2. Phân cụm dữ liệu ...................................................................................... 6 1.2.1. Khái niệm phân cụm dữ liệu .............................................................. 6 1.2.2. Các bước cơ bản để phân cụm dữ liệu ............................................... 6 1.2.3. Các kiểu dữ liệu và độ đo tương tự, độ đo phi tương tự .................... 7 1.2.3.1. Phân loại kiểu dữ liệu dựa trên kích thước miền ......................... 7 1.2.3.2. Phân loại kiểu dữ liệu dựa trên hệ đo .......................................... 7 1.2.3.3. Khái niệm và phép đo độ tương tự .............................................. 9 1.2.4. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu ............................... 12 1.2.5. Ứng dụng của phân cụm dữ liệu ...................................................... 14 1.3. Cấu trúc giải phẫu răng ........................................................................... 15 1.3.1. Cấu trúc giải phẫu răng .................................................................... 15 1.3.2. Phân loại ảnh X - quang nha khoa ................................................... 17 1.4. Bài toán phân đoạn ảnh X - quang nha khoa .......................................... 19 1.4.1. Phân đoạn ảnh .................................................................................. 19 1.4.2. Phân loại các phương pháp phân đoạn ảnh ...................................... 20 1.4.3. Phân đoạn ảnh X – quang nha khoa ................................................. 21 KẾT LUẬN CHƯƠNG 1 .................................................................................... 23 CHƯƠNG 2: MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT ... 24 2.1. Phân cụm mờ .......................................................................................... 24 2.1.1. Các khái niệm cơ bản về tập mờ ...................................................... 24
iii
2.1.2. Thuật toán phân cụm mờ FCM (Fuzzy C-Means) ........................... 28 2.2. Thuật toán phân cụm nửa giám sát mờ bằng phương pháp học tích cực 31 2.3. Thuật toán phân cụm nửa giám sát mờ chuẩn (SSSFC) ......................... 33 2.4. Thuật toán phân cụm nửa giám sát mờ theo quy tắc entropy (eSFCM) 35 2.5. Thuật toán nửa giám sát mờ lai ghép ..................................................... 36 2.5.1. Lược đồ tổng quan lai ghép .............................................................. 36 2.5.2. Thuật toán tách ngưỡng Otsu ........................................................... 38 2.5.3. Thuật toán phân cụm nửa giám sát mờ lai ghép .............................. 40 KẾT LUẬN CHƯƠNG 2 .................................................................................... 41
CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG PHÂN ĐOẠN ẢNH X – QUANG NHA KHOA ....................................................................................................... 42 3.1. Đặc tả yêu cầu ......................................................................................... 42 3.1.1. Yêu cầu thực tế ................................................................................. 42 3.1.2. Mục đích của ứng dụng .................................................................... 43 3.2. Đặc tả dữ liệu .......................................................................................... 43 3.3. Các bước phân đoạn ảnh ......................................................................... 44 3.4. Thiết kế hệ thống .................................................................................... 45 3.4.1. Chức năng phân đoạn ảnh X – quang nha khoa ............................... 45 3.4.2. Chức năng xem chi tiết kết quả ........................................................ 46 3.4.3. Chức năng đánh giá chất lượng phân đoạn ...................................... 47 3.5. Minh họa các chức năng của ứng dụng .................................................. 48 3.5.1. Giao diện chính của ứng dụng .......................................................... 48 3.5.2. Chọn ảnh cần phân đoạn .................................................................. 49 3.5.3. Phân đoạn ảnh bằng thuật toán FCM ............................................... 49 3.5.4. Phân đoạn ảnh bằng thuật toán nửa giám sát mờ ............................. 50 3.5.5. Chọn độ đo đánh giá kết quả phân cụm ........................................... 50 3.6. Đánh giá kết quả phân đoạn ................................................................... 51 KẾT LUẬN CHƯƠNG 3 .................................................................................... 52 KẾT LUẬN ........................................................................................................ 53 TÀI LIỆU THAM KHẢO ................................................................................ 54 PHỤ LỤC ........................................................................................................... 57
CODE MATLAB CỦA ỨNG DỤNG PHÂN ĐOẠN ẢNH BẰNG THUẬT TOÁN BÁN GIÁM SÁT MỜ LAI GHÉP ...................................................... 57
iv
DANH MỤC TỪ VIẾT TẮT
Từ viết tắt Từ viết đầy đủ
Davies-Bouldin DB
Semi-supervised Entropy regularized Fuzzy Clustering eSFCM
Fuzzy C-Mean FCM
Pakhira, Bandyopadhyay and Maulik PBM
SSFCM Semi-Supervised Fuzzy C-Mean
Semi-Supervised Standard Fuzzy Clustering SSSFC
Simplified Silhouete Width Criterion SSWC
Cơ sở dữ liệu CSDL
Phân cụm dữ liệu PCDL
v
DANH MỤC HÌNH VẼ
Hình 1.1. Quá trình khám phá tri thức trong CSDL ............................................. 4
Hình 1.2. Cơ quan răng (răng và nha chu) .......................................................... 15
Hình 1.3. Một số loại ảnh X-Quang nha khoa .................................................... 19
Hình 1.4. Những khó khăn trong việc phân đoạn ảnh nha khoa ......................... 22
Hình 2.1. Hàm thuộc tuyến tính .......................................................................... 25
Hình 2.2. Hàm thuộc dạng sin. ............................................................................ 25
Hình 2.3. Hàm thuộc Gauss ................................................................................ 26
Hình 2.4. Bao trong của tập mờ .......................................................................... 26
Hình 2.5. Phép hợp tập mờ dạng 1 ...................................................................... 27
Hình 2.6. Phép giao tập mờ dạng 1 ..................................................................... 28
Hình 2.7. Phần bù của tập mờ trung bình ........................................................... 28
Hình 2.8. Lược đồ tổng quan của thuật toán lai ghép ......................................... 37
Hình 3.1: Ảnh dữ liệu đầu vào của ứng dụng ..................................................... 44
Hình 3.2: Biểu đồ usecase mô tả chức năng của ứng dụng ................................ 45
Hình 3.3: Biểu đồ trình tự chức năng phân đoạn ảnh ......................................... 46
Hình 3.4: Biểu đồ trình tự chức năng xem kết quả ............................................. 47
Hình 3.5: Biểu đồ trình tự chức năng đánh giá kết quả ..................................... 48
Hình 3.6: Giao diện chính của phần mềm .......................................................... 48
Hình 3.7: Chọn ảnh cần phân đoạn .................................................................... 49
Hình 3.8. Kết quả phân đoạn bằng FCM ............................................................ 49
Hình 3.9. Kết quả phân đoạn bằng SSSFC ......................................................... 50
Hình 3.10. Đánh giá kết quả phân đoạn .............................................................. 50
vi
LỜI MỞ ĐẦU
Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động
khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ
liệu khổng lồ và phức tạp đồng thời cũng tìm ra các mẫu tiềm ẩn trong dữ liệu
đó. Hiện nay việc khai phá dữ liệu được nghiên cứu theo các hướng mô tả khái
niệm, luật kết hợp, phân lớp và dự đoán, phân cụm (xem [1], [2], [7]) và có
nhiều ứng dụng trong thực tế, trong đó phân đoạn ảnh X-Quang trong lĩnh vực y
tế là một ứng dụng điển hình [13]. Ngày nay, việc xử lý các hình ảnh y tế có vai
trò quan trọng trong việc tự động hóa phân tích, hỗ trợ chẩn đoán và điều trị các
bệnh khác nhau. Trong đó, quá trình phân đoạn thường được yêu cầu như là giai
đoạn sơ bộ. Tuy nhiên các phân vùng trong hình ảnh y tế rất phức tạp nên việc
phân đoạn chính xác là rất quan trọng.
Trong các phương pháp phân đoạn ảnh hiện có, phân cụm là một phương
pháp được sử dụng rộng rãi bởi tính đơn giản và hiệu quả mà nó mang lại (xem
[8]-[12]). Phân cụm dữ liệu là lĩnh vực học máy không giám sát, nó có chức
năng tổ chức một tập đối tượng dữ liệu thành các cụm sao cho những đối tượng
trong cùng một cụm thì tương tự như nhau còn các đối tượng ở các cụm khác
nhau thì kém tương tự nhau hơn. Nhược điểm chung của thuật toán phân cụm là
chất lượng phân cụm phụ thuộc nhiều vào các tham số và thông tin khởi tạo. Để
giảm thiểu các hạn chế này, gần đây đã có nhiều tác giả (xem [8]-[12]) giải
quyết theo cách tiếp cận nửa giám sát, trong đó việc phân cụm được thực hiện
dựa vào các thông tin bổ trợ đóng vai trò điều khiển quá trình phân cụm, nhờ đó
mà chất lượng phân cụm được nâng lên đáng kể.
Mục tiêu của luận văn là nghiên cứu, tìm hiểu một số thuật toán phân cụm
nửa giám sát và xây dựng được một ứng dụng thử nghiệm cho thuật toán phân
đoạn ảnh X-quang hỗ trợ chuẩn đoán bệnh trong lĩnh vực nha khoa. Các kết quả
đạt được trong luận văn này là kết quả trong quá trình học tập và nghiên cứu của
tác giả tại Trường Đại học Công nghệ Thông tin và Truyền thông. Ngoài phần
1
mở đầu, kết luận và tài liệu tham khảo, nội dung luận văn được trình bày thành
ba chương:
Chương 1 trình bày các khái niệm cơ bản về phân cụm dữ liệu và bài toán
phân đoạn ảnh X-quang nha khoa.
Chương 2, tác giả tìm hiểu một số thuật toán phân cụm dữ liệu trong đó
tập trung nghiên cứu thuật toán phân cụm dữ liệu nửa giám sát.
Chương 3 là kết quả thực nghiệm cho thuật toán phân cụm nửa giám sát
đối với bài toán phân đoạn ảnh X-quang nha khoa.
2
CHƯƠNG 1
TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU VÀ BÀI TOÁN PHÂN
ĐOẠN ẢNH X-QUANG NHA KHOA
Chương này gồm 3 mục, mục 1.1 là các khái niệm cơ bản về Khai phá dữ
liệu. Mục 1.2 trình bày về các khái niệm về phân cụm dữ liệu, yêu cầu đối với
kỹ thuật phân cụm dữ liệu (xem [1], [2], [4]). Mục 1.3 là cấu tạo về răng, phân
loại ảnh X-quang và bài toán phân đoạn ảnh X-quang nha khoa [3].
1.1. Khai phá dữ liệu
1.1.1. Khái niệm khai phá dữ liệu
Khai phá dữ liệu là một công đoạn quan trọng nhất trong quá trình khám
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD). Do
sự phát triển mạnh mẽ của khai phá dữ liệu về phạm vi các lĩnh vực ứng dụng
trong thực tế và các phương pháp tìm kiếm nên có rất nhiều khái niệm khác
nhau. Tuy nhiên, ở đây có thể hiểu khai phá dữ liệu là một quá trình tìm kiếm,
chắt lọc các tri thức mới, tiềm ẩn, hữu dụng trong tập dữ liệu lớn.
1.1.2. Quá trình khai phá tri thức trong cơ sở dữ liệu
Các yêu cầu về thông tin trong các loại hoạt động như công tác quản lý,
hoạt động kinh doanh, phát triển sản xuất và dịch vụ, đặc biệt là trong việc ra
quyết định giải quyết một vấn đề ngày càng đòi hỏi chất lượng cao hơn. Người
làm quyết định không những cần dữ liệu mà còn cần có thêm hiểu biết, nhiều tri
thức để hỗ trợ cho việc ra quyết định của mình. Để giải quyết vấn đề đó thì kỹ
thuật khám phá tri thức trong cơ sở dữ liệu (KDD) đã ra đời. Khám phá tri thức
trong cơ sở dữ liệu là lĩnh vực liên quan đến các ngành như: xác suất thống kê,
học máy, trực quan hóa dữ liệu, tính toán song song ... Quá trình KDD có thể
chia thành 5 bước thực hiện như sau:
Trích chọn dữ liệu: Xác định mục đích của quy trình khai phá dữ liệu dựa
trên quan điểm của người dùng, thu thập và chuẩn bị dữ liệu để khai phá.
3
Tiền xử lý dữ liệu: Nhằm mục đích loại bỏ sự trùng lặp dữ liệu, cắt lìa
những thông tin có thể gây nhiễu, tập hợp những thông tin cần thiết cho mô hình
hóa, chọn các phương pháp xử lý những thông tin bị khiếm khuyết.
Chuyển đổi dữ liệu: Thực hiện thu gọn dữ liệu, phép ánh xạ dữ liệu, tìm
những đặc trưng phù hợp để mô tả và khai phá dữ liệu.
Khai phá dữ liệu: Chọn nhiệm vụ khai phá dữ liệu như phân lớp, gom
cụm, hồi quy, kết hợp, ... Từ nhiệm vụ đã chọn, sử dụng các thuật toán và các
phương pháp đã biết để tìm kiếm các mẫu trong dữ liệu, chọn ra các mẫu hữu
ích.
Trình bày và đánh giá: Từ các mẫu khai phá được tiến hành đánh giá hoặc
Trình bày, đánh giá
phiên dịch thành những tri thức hiểu được.
Khai phá
Chuyển đổi
Tiền xử lý DL
Trích chọn DL
Tri thức
Hình 1.1. Quá trình khám phá tri thức trong CSDL
4
1.1.3. Các kỹ thuật tiếp cận trong khai phá dữ liệu:
Các kỹ thuật áp dụng trong khai phá dữ liệu phần lớn được kế thừa từ các
lĩnh vực như: Cơ sở dữ liệu, Học máy, Trí tuệ nhân tạo, Xác suất thống kế, ... vì
vậy ta có hai hướng tiếp cận sau đây:
Theo quan điểm của học máy, các kỹ thuật trong Khai phá dữ liệu gồm:
- Học có giám sát (Supervised learning): Là quá trình gán nhãn lớp cho
các đối tượng trong tập dữ liệu dựa trên một bộ các đối tượng huấn luyện và
các thông tin về nhãn lớp đã biết.
- Học không giám sát (Unsupervised learning): Là quá trình phân chia một
tập dữ liệu thành các lớp hay cụm (cluster) dữ liệu tương tự nhau mà chưa biết
trước các thông tin về nhãn lớp.
- Học nửa giám sát (Semi- Supervised learning): Là quá trình chia một tập
dữ liệu thành các lớp con dựa trên một số thông tin bổ trợ cho trước.
Theo các lớp bài toán cần giải quyết, các kỹ thuật trong khai phá dữ liệu
gồm:
- Phân lớp và dự toán (Classification and Prediction): Đưa một đối tượng
vào một trong các lớp đã biết trước. Phân lớp và dự đoán còn được gọi là học
có giám sát.
- Luật kết hợp (Association rules): Là dạng luật biểu diễn tri thức ở dạng
khá đơn giản. Một luật kết hợp được mô tả như sau:Nếu a thì b với xác suất p
- Phân tích chuỗi theo thời gian: Giống như khai phá luật kết hợp nhưng có
thêm tính thứ tự và thời gian.
- Phân cụm (Clustering): Nhóm các đối tượng thành từng cụm dữ liệu. Đây
là phương pháp học không giám sát.
- Mô tả khái niệm: Mô tả, tổng hợp và tóm tắt khái niệm, ví dụ như tóm tắt
văn bản.
5
1.2. Phân cụm dữ liệu
1.2.1. Khái niệm phân cụm dữ liệu
Phân cụm dữ liệu (PCDL) là một kỹ thuật phát triển mạnh mẽ trong nhiều
năm trở lại đây do các ứng dụng và lợi ích to lớn của nó trong các lĩnh vực thực
tế. Ở mức độ cơ bản nhất có thể hiểu Phân cụm dữ liệu là một kỹ thuật trong
khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên
tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức
cho việc ra quyết định.
1.2.2. Các bước cơ bản để phân cụm dữ liệu
PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu
sao cho các đối tượng trong một cụm thì “tương tự” nhau và các đối tượng trong
các cụm khác nhau thì “phi tương tự” với nhau. Số cụm dữ liệu được xác định
bằng kinh nghiệm hoặc bằng một số phương pháp phân cụm.
Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp để
xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu.
Đây chính là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông
thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi
tương tự(Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo
tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn
hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự.
Trong quá trình PCDL thì vấn đề trở ngại lớn nhất đó là nhiễu (noise).
Nhiễu xuất hiện do trong quá trình thu thập thông tin, dữ liệu thiếu chính xác
hoặc không đầy đủ. Vì vậy chúng ta cần phải khử nhiễu trong quá trình tiến
hành phân cụm dữ liệu.
Các bước của một bài toán phân cụm dữ liệu gồm:
- Xây dựng hàm tính độ tương tự
- Xây dựng các tiêu chuẩn phân cụm
- Xây dựng mô hình cho cấu trúc dữ liệu
6
- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm
1.2.3. Các kiểu dữ liệu và độ đo tương tự, độ đo phi tương tự
Trong phần này ta phân tích các kiểu dữ liệu thường được sử dụng trong
PCDL. Trong PCDL, các đối tượng dữ liệu cần phân tích có thể là con người,
nhà cửa, tiền lương, các thực thể phần mềm, ... Các đối tượng này thường được
diễn tả dưới dạng các thuộc tính của nó. Các thuộc tính này là các tham số cần
cho giải quyết vấn đề PCDL và sự lựa chọn chúng có tác động đáng kể đến các
kết quả của phân cụm. Phân loại các kiểu thuộc tính khác nhau là một vấn đề
cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện
thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách
phân lớp dựa trên hai đặc trưng là: kích thước miền và hệ đo.
1.2.3.1. Phân loại kiểu dữ liệu dựa trên kích thước miền
- Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được,
nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ như các thuộc tính về
màu, nhiệt độ hoặc cường độ âm thanh.
- Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm
được. Thí dụ như các thuộc tính về số serial của một cuốn sách, số thành viên
trong một gia đình, ...
1.2.3.2. Phân loại kiểu dữ liệu dựa trên hệ đo
Giả sử có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính
thứ i của chúng. Ta có các lớp kiểu dữ liệu như sau:
- Thuộc tính định danh: Dạng thuộc tính khái quát hóa của thuộc tính nhị
phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai
phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là
𝑥 ≠ 𝑦 hoặc 𝑥 = 𝑦.
- Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự, nhưng
chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể
7
xác định là 𝑥 ≠ 𝑦 hoặc 𝑥 = 𝑦 hoặc 𝑥 > 𝑦 hoặc 𝑥 < 𝑦. Thí dụ như thuộc tính
Huy chương của vận động viên thể thao.
- Thuộc tính khoảng: Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với
thuộc tính khoảng, ta có thể xác định một thuộc tính là đứng trước hoặc đứng
sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi yi thì ta nói x cách y
một khoảng | xi– yi| tương ứng với thuộc tính thứ i. Ví dụ, thuộc tính số Serial
của một đầu sách trong thư viện hoặc thuộc tính số kênh trên truyền hình.
- Thuộc tính tỉ lệ: Là thuộc tính khoảng nhưng được xác định một cách
tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy
giá trị 0 làm gốc.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc
tính có thứ tự gọi chung là thuộc tính hạng mục, thuộc tính khoảng và thuộc tính
tỉ lệ được gọi là thuộc tính số.
Người ta còn đặc biệt quan tâm đến dữ liệu không gian. Đây là loại dữ liệu
có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian
mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí dụ
như thông tin về hình học, ... Dữ liệu không gian có thể là dữ liệu liên tục hoặc
rời rạc:
Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều
chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ liệu
trong không gian.
Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian.
Thông thường, các thuộc tính số được đo bằng các đơn vị xác định như là
Kilogams hoặc Centimeter. Tuy nhiên, các đơn vị đo có ảnh hưởng đến các kết
quả phân cụm. Thí dụ như thay đổi độ đo cho thuộc tính cân nặng từ Kilogams
sang Pound có thể mang lại kết quả khác nhau trong phân cụm. Để khắc phục
điều này người ta phải chuẩn hóa dữ liệu, tức là sử dụng các thuộc tính dữ liệu
không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hóa phụ thuộc vào ứng dụng
và người dùng, thông thường chuẩn hóa dữ liệu được thực hiện bằng cách thay
8
thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các trọng số cho các thuộc
tính.
1.2.3.3. Khái niệm và phép đo độ tương tự
Khi các đặc tính của dữ liệu được xác định, người ta tìm cách thích hợp để
xác định “khoảng cách” giữa các đối tượng (phép đo độ tương tự dữ liệu). Đây
là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường
các hàm này hoặc là để tính độ tương tự hoặc là tính độ phi tương tự giữa các
đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống
nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ
nghịch với hàm tính độ tương tự. Độ tương tự hoặc độ phi tương tự có nhiều
cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng.
Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà ta phân
tích. Thí dụ, đối với thuộc tính hạng mục người ta không sử dụng độ đo khoảng
cách mà sử dụng một hướng hình học của dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric.
Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để
tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự. Một
không gian metric là một tập trong đó có xác định các “khoảng cách” giữa từng
cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa
là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) gồm các đối
tượng dữ liệu trong CSDL gọi là một không gian metric, nếu với mỗi cặp phần
tử x, y thuộc X đều xác định một số thực δ(x, y), được gọi là khoảng cách giữa x
và y thỏa mãn hệ tính chất sau:
nếu x ≠ y;
nếu x = y;
với mọi x, y;
+ .
9
Hàm δ(x, y) được gọi là một metric của không gian. Các phần tử của X
được gọi là các điểm của không gian này.
Một số phép đo độ tương tự áp dụng đối với các kiểu dữ liệu khác nhau:
+ Thuộc tính khoảng: Sau khi chuẩn hóa, độ đo phi tương tự của hai đối
tượng dữ liệu x, y được xác định bằng các metric như sau: |xi – yi|q
Khoảng cách Minskowski: , với q là số nguyên
dương.
Khoảng cách Euclide: , (trường hợp đặc biệt của
khoảng cách Minskowski trong trường hợp q = 2.
Khoảng cách Manhattan: , trường hợp đặc biệt của
khoảng cách Minskowski trong trường hợp q = 1.
Khoảng cách cực đại: , đây là trường hợp của khoảng
cách Minskowski trong trường hợp .
+Thuộc tính nhị phân: Trước hết ta có xây dựng bảng tham số sau:
y: 1 y: 0
x: 1
x: 0
Bảng 1. Bảng tham số thuộc tính nhị phân
Trong đó: , các đối tượng x, y mà tất cả các thuộc tính của nó
đều là nhị phân biểu thị bằng 0 và 1. Bảng trên cho ta thông tin sau:
- là tổng số các giá trị thuộc tính có giá trị là 1 trong cả hai đối tượng x, y.
- là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y.
- là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y.
- là tổng số các giá trị thuộc tính có giá trị là 0 trong cả hai đối tượng x, y.
Các phép đo độ tương tự đối với dữ liệu thuộc tính nhị phân được định
nghĩa như sau:
10
- Hệ số đối sánh đơn giản: , ở đây cả hai đối tượng x và y có
vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số.
- Hệ số Jacard: , tham số này bỏ qua số các đối sánh
giữa 0-0. Công thức tính này được sử dụng trong trường hợp mà trọng số của
các thuộc tính có giá trị 1 của đối tượng dữ liệu có giá trị cao hơn nhiều so với
các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây là không đối
xứng.
+ Thuộc tính định danh: Độ đo phi tương tự giữa hai đối tượng x và y
được định nghĩa như sau: , trong đó m là số thuộc tính đối sánh
tương ứng trùng nhau và p là tổng số các thuộc tính.
+ Thuộc tính có thứ tự: Phép đo độ phi tương tự giữa các đối tượng dữ liệu
với thuộc tính thứ tự được thực hiện như sau, ở đây ta giả sử i là thuộc tính thứ
tự có giá trị ( kích thước miền giá trị):
Các trạng thái được sắp thứ tự như sau: , ta có thể thay thế mỗi
giá trị của thuộc tính bằng giá trị cùng loại , với .
Mỗi một thuộc tính thứ tự có các miền giá trị khác nhau, vì vậy ta chuyển
đổi chúng về cùng miền giá trị [0, 1] bằng cách thực hiện phép biến đổi sau cho
mỗi thuộc tính: , với
Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các
giá trị , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.
+ Thuộc tính tỷ lệ: Có nhiều cách khác nhau để tính độ tương tự giữa các
thuộc tính tỉ lệ. Một trong những số đó là sử dụng công thức tính logarit cho mỗi
thuộc tính , thí dụ , lúc này đóng vai trò như thuộc tính khoảng.
Phép biến đổi logarit này thích hợp trong trường hợp các giá trị của thuộc tính là
số mũ.
11
Trong thực tế, khi tính độ đo tương tự dữ liệu, người ta chỉ xem xét một
phần các thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc đánh trọng số cho tất
cả các thuộc tính dữ liệu. Trong một số trường hợp, người ta loại bỏ đơn vị đo
của các thuộc tính dữ liệu bằng cách chuẩn hóa chúng hoặc gán trọng số cho
mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng
trong các độ đo khoảng cách trên, thí dụ với mỗi thuộc tính dữ liệu đã được gán
trọng số tương ứng , độ tương tự dữ liệu được xác định như sau:
.
Người ta có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, thí
dụ dữ liệu kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân và ngược lại.
Nhưng giải pháp này rất tốn kém về chi phí tính toán, cần phải cân nhắc khi áp
dụng cách thức này.
Tùy từng trường hợp dữ liệu cụ thể mà người ta sử dụng các mô hình tính
độ tương tự khác nhau. Việc xác định độ tương tự dữ liệu thích hợp, chính xác,
đảm bảo khách quan là rất quan trọng và góp phần xây dựng thuật toán PCDL
có hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán của
thuật toán.
1.2.4. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
Việc xây dựng, lựa chọn một thuật toán phân cụm là bươc then chốt cho
việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu
cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ưu tiên giữa
chất lượng của các cụm hay tốc độ thực hiện thuật toán, ...
Hầu hết các nghiên cứu và phát triển thuật toán PCDL đều nhằm thỏa mãn
các yêu cầu cơ bản sau:
Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ
liệu nhỏ (khoảng 200 bản ghi dữ liệu) nhưng không hiệu quả khi áp dụng cho
tập dữ liệu lớn (khoảng 1 triệu bản ghi).
12
Thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu
quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau như dữ
liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục, ... và thích nghi với
kiểu dữ liệu hỗn hợp.
Khám phá ra các cụm với hình thù bất kỳ: Do hầu hết các CSDL có chứa
nhiều cụm dữ liệu với các hình thù khác nhau như: hình lõm, hình cầu, hình que,
... Vì vậy, để khám phá được các cụm có tính tự nhiên thì các thuật toán phân
cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ.
Tối thiểu lượng tri thức cần cho xác định các tham số vào: Do các giá trị
đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp để
xác định các giá trị vào thích hợp đối với các CSDL lớn.
Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu, khi đưa vào
xử lý cho thuật toán PCDL với các thứ tự vào của các đối tượng dữ liệu ở các
lần thực hiện khác nhau thì không ảnh hưởng lớn đến kết quả phân cụm.
Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm
trong KPDL đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác.
Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn
tránh dẫn đến chất lượng phân cụm thấp do nhạy cảm với nhiễu.
Ít nhạy cảm với các tham số đầu vào: Nghĩa là giá trị của các tham số đầu
vào khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm.
Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả
cho dữ liệu có số chiều khác nhau.
Dễ hiểu, dễ cài đặt và khả thi.
Các yêu cầu này đồng thời là các tiêu chí để đánh giá hiệu quả của các
phương pháp PCDL, đây là những thách thức cho các nhà nghiên cứu trong lĩnh
vực PCDL.
13
1.2.5. Ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu là một trong những công cụ chính của KPDL được ứng
dụng trong nhiều lĩnh vực như thương mại, khoa học. Các kỹ thuật PCDL đã
được áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau:
Thương mại: PCDL có thể giúp các thương nhân khám phá ra các nhóm
khách hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả họ từ các
mẫu mua bán trong CSDL khách hàng.
Sinh học: PCDL được sử dụng để xác định các loại sinh vật, phân loại các
Gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu.
Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí yêu cầu bồi
thường trung bình cao, xác định gian lận trong bảo hiểm thông qua các mẫu cá
biệt.
Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như dữ
liệu thu được từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống
thông tin địa lý (GIS), ... làm cho người dùng rất khó để kiểm tra các dữ liệu
không gian một cách chi tiết. PCDL có thể trợ giúp người dùng tự động phân
tích và xử lý các dữ liệu không gian như nhận dạng và chiết xuất các đặc tính
hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong CSDL không gian.
Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, ...
nhằm cung cấp thông tin cho quy hoạch đô thị.
Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung
cấp thông tin cho nhận dạng các vùng nguy hiểm.
Địa lý: Phân lớp các động vật, thực vật và đưa ra đặc trưng của chúng.
Khai phá Web: PCDL có thể khám phá các nhóm tài liệu quan trọng, có
nhiều ý nghĩa trong môi trường Web. Các lớp tài liệu này trợ giúp cho việc
khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng
đặc biệt hay khám phá ra cộng đồng Web, ...
Phân đoạn ảnh: Phân cụm ảnh thành từng vùng rồi trích chọn đặc trưng
của từng vùng, dựa vào đó ta có thể tra cứu các bức ảnh một cách nhanh chóng
14
và chính xác từ một cơ sở dữ liệu ảnh cho trước, hay phục vụ công tác chuẩn
đoán bệnh trong y tế đối với ảnh X-quang.
1.3. Cấu trúc giải phẫu răng
1.3.1. Cấu trúc giải phẫu răng
Cơ quan 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 chính danh gồm men, ngà (mô cứng) và tủy (mô mềm).
Nha chu gồm xê măng (còn gọi là xương chân răng, men chân răng), dây chằng,
xương ổ răng, nướu (lợi). 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.
Hình 1.2. Cơ quan răng (răng và nha chu)
Mỗi răng có phần thân răng và chân răng. Giữa thân răng và chân răng là
đường cổ răng (cổ răng giải phẫu), là một đường cong, còn gọi là đường nối
men – xê măng. Thân răng được bao bọc bởi men răng, chân răng được xê măng
bao phủ.
Nướu răng viền xung quanh cổ răng tạo thành một bờ, gọi là cổ răng sinh
lý. Phần răng thấy được trong miệng là thân răng lâm sàng. Cổ răng sinhh lý
thay đổi tùy theo nơi bám và bờ của viền nướu, khi tuổi càng cao thì nơi bám
này càng có khuynh hướng di chuyển dần về phía chóp răng. Nhiều trường hợp
15
bệnh lý, nướu răng có thể bị sưng hoặc trụt, làm thân răng (lâm sàng) bị ngắn lại
hoặc dài ra.
Cấu tạo của răng: Bao gồm men răng, ngà răng (mô cứng) và tủy răng
(mô mềm):
Men răng: Men răng phủ mặt ngoài ngà thân răng, là mô cứng nhất trong
cơ thể, có tỉ lệ chất vô cơ cao (96%).Hình dáng và bề dày của men được xác
định từ trước khi răng mọc ra, trong đời sống, men răng không có sự bồi đắp
thêm mà chi mòn dần theo tuổi, nhưng có sự trao đổi về vật lý và hóa học trong
môi trường với miệng.
Ngà răng: Kém cứng hơn men, chứa tỉ lệ chất vô cơ thấp hơn men (75%).
Trong ngà có nhiều ống ngà, chứa đuôi bào tương của nguyên bào ngà.Bề dày
ngà răng thay đổi trong đời sống do hoạt động của nguyên bào ngà. Ngà răng
ngày càng dày theo hướng về phía hốc tủy răng, làm hẹp dần hốc tủy.
Tủy răng: Là mô liên kết mềm, nằm trong hốc tủy gồm tủy chân và tủy
thân. Tủy răng trong buồng tủy gọi là tủy thân, tủy buồng, tủy răng trong ống
tủy gọi là tủy chân. Các nguyên bào ngà nằm sát vách hốc tủy.Tủy răng có
nhiệm vụ duy trì sự sống của răng, cụ thể là sự sống của nguyên bào ngà và tạo
ngà thứ cấp, nhận cảm giác của răng. Trong tủy răng có chứa nhiều mạch máu,
mạch bạch huyết và đầu tận cùng thần kinh.
Bộ phận nâng đỡ răng: Bao gồm xương ổ răng, xê măng, dây chằng nha
chu và nướu (lợi) răng.
Xương ổ răng: Là mô xương xốp, bên ngoài được bao bọc bằng màng
xương, nơi nướu răng bám vào. Xương ổ răng tạo thành một huyệt, có hình dáng
và kích thước phù hợp với chân răng.Bề mặt ổ răng, nơi đối diện với chân răng,
là mô xương đặc biệt và có nhiều lỗ thủng để cho các mạch máu và dây thần
kinh từ xương xuyên qua để nuôi dây chằng nha chu, gọi là xương ổ chính danh,
hay lá sàng. Trên hình ảnh tia X, phần xương ổ chính danh trông cản tia hơn, gọi
là lá cứng.Nền xương ổ không phân biệt được với xương hàm. Chiều cao xương
ổ răng thay đổi theo tuổi và tùy theo sự lành mạnh hay bệnh lý của mô nha chu.
16
Khi răng không còn trên xương hàm thì xương ổ răng và các thành phần của nha
chu cũng bị tiêu dần đi.
Xê măng: Là mô đặc biệt, hình thành cùng với sự hình thành chân răng,
phủ ngoài ngà chân răng.Xê măng được bồi đắp thêm ở phía chóp chủ yếu để bù
trừ sự mòn mặt nhai, được coi là hiện tượng “mọc răng suốt đời” hay “trồi mặt
nhai”. Xê măng cũng có thể tiêu hoặc quá sản trong một số trường hợp bất
thường hay bệnh lý.
Dây chằng nha chu: Là những bó sợi liên kết dày khoảng 0.25mm, một
đầu bám vào xê măng, còn đầu kia bám vào xương ổ chính danh. Cả xê măng,
dây chằng nha chu và xương ổ chính danh đều có nguồn gốc từ túi răng chính
danh.Dây chằng nha chu có nhiệm vụ giữ cho răng gắn vào xương ổ răng và
đồng thời có chức năng làm vật đệm, làm cho mỗi răng có sự xê dịch nhẹ độc
lập với nhau trong khi nhai, giúp lưu thông máu, truyền cảm giác áp lực và
truyền lực để tránh tác dụng có hại của lực nhai đối với răng và nha chi.
Nướu răng: Là phần niêm mạc phủ lên xương ổ răng (nướu dính) và cổ
răng (nướu rời)
1.3.2. Phân loại ảnh X - quang nha khoa
Ảnh X-quang nha khoa là một trong những cách phổ biến với chi phí thấp
nhất để thu được ảnh (thông tin) về răng. Bởi vì nhiều bệnh của răng và các mô
xung quanh không thể được nhìn thấy trực tiếp bằng mắt thường khi nha sĩ kiểm
tra miệng. Chụp X – quang có thể giúp phát hiện những vấn đề sau đây:
- Lỗ sâu giữa các răng hoặc phát hiện sâu răng bên dưới lớp trám răng
- Nhiễm trùng trong xương
- Bệnh nha chu
- Áp – xe hoặc u nang
- Phát hiện những biến chuyển bất thường trong răng miệng
- Phát hiện khối u
17
Phát hiện và điều trị các vấn đề về răng ở giai đoạn sớm có thể tiết kiệm
thời gian, tiền bạc và giảm những khó chịu không cần thiết. Ảnh X – quang có
thể giúp nha sĩ phát hiện các vấn đề đó.
Có rất nhiều loại ảnh X – quang nha khoa khác nhau, trong đó được chia
thành hai kiểu ảnh X – quang nha khoa chính: intraoral (ảnh X – quang phạm vi
trong miệng) và extraoral (ảnh X – quang phạm vi cả ngoài miệng).
- Intraoral: là loại ảnh X – quang nha khoa phổ biến nhất. Nó mô tả các
răng một cách chi tiết và cho phép nha sĩ tìm sâu răng, kiểm tra sức khỏe của các
răng và xương xung quanh răng, kiểm tra tình trạng phát triển của răng và theo
dõi sức khỏe chung của răng và xương hàm.
- Extraoral: cũng cho chúng ta thấy các răng nhưng mục đích chính là cho
thấy toàn bộ hàm răng và xương sọ. Nó không cung cấp đặc điểm chi tiết về
từng răng như ảnh intraoral và do đó, nó không được sử dụng để phát hiện sâu
răng hoặc một số vấn đề khác với từng chiếc răng. Thay vào đó, nó được sử
dụng để tìm các răng nêm vào nhau, theo dõi sự tăng trưởng và phát triển hàm
trong quan hệ với răng, để xác định các vấn đề tiềm ẩn giữa răng và hàm, hội
chứng rối loạn thái dương hàm hoặc các xương mặt khác.
Các ảnh X – quang thuộc kiểu extraoral như: panoramic, tomograms,
cephalometric projections, sialography, computed tomography. Trong đó phổ
biến nhất là ảnh X – quang panoramic. Ảnh này cho thấy toàn bộ khoang miệng:
tất cả các răng trong xương hàm trên và dưới. Nó hữu ích trong việc phát hiện
các vùng răng mới nổi, xác định sự liên quan của hàm răng và các cấu trúc
xương xung quanh, hỗ trợ trong việc chẩn đoán các khối u, v.v.
Ảnh X – quang thuộc kiểu intraoral: bitewing, periapical,occlusal. Mỗi loại
cho thấy những khía cạnh khác nhau của răng:
- Ảnh X – quang Bitewing (ảnh cắn cánh): cho thấy mô tả về hàm trên và
dưới trong một vùng của miệng. Mỗi ảnh bitewing cho thấy một chiếc răng từ
đỉnh đến phần xương hỗ trợ nó. Ảnh bitewing thường được sử dụng để phát hiện
18
sâu răng giữa các răng và sự thay đổi mật độ răng gây ra bởi các bệnh về nướu
răng. Nó cũng rất hữu ích trong việc xác định các điều trị chỉnh nha phù hợp
- Ảnh X – quang Periapical (ảnh quanh chóp) cho thấy toàn bộ răng từ đỉnh
đến dưới cả chân răng – nơi răng được neo ở xương hàm. Mỗi ảnh quanh chóp
cho thấy kích thước đầy đủ của một số chiếc răng trong một phần của hàm trên
hoặc dưới. Loại ảnh này được sử dụng để phát hiện các bất thường trong cấu
trúc của chân răng và xung quanh cấu trúc xương.
- Ảnh X – quang Occlusal: lớn hơn hai loại trên, nó cho thấy vị trí và sự
phát triển răng một cách đầy đủ. Nó cho thấy toàn bộ vòm răng ở hàm trên hoặc
dưới.
Ảnh X – quang này có thể được sử dụng trong các ứng dụng máy tính như
hệ thống nhận dạng người hoặc hỗ trợ về khía cạnh lâm sàng như hệ thống chẩn
đoán nha khoa hoặc hệ thống điều trị nha khoa.
a) Ảnh cắn cánh. b) ảnhquanh chóp. c)ảnh pano toàn hàm
Hình 1.3. Một số loại ảnh X-Quang nha khoa
1.4. Bài toán phân đoạn ảnh X - quang nha khoa
1.4.1. Phân đoạn ảnh
Trong thị giác máy tính, phân đoạn ảnh là quá trình phân vùng một ảnh kĩ
thuật số thành các vùng rời rạc và đồng nhất với nhau hay nói cách khác là xác
định các biên của các vùng ảnh đó. Các vùng ảnh đồng nhất này thông thường sẽ
tương ứng với toàn bộ hay từng phần của các đối tượng thật sự bên trong ảnh.
19
“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” .Trong một định nghĩa khác, phân đoạn ảnh được định nghĩa như
là quá trình trích chọn những vùng hữu ích/cần quan tâm từ ảnh nền ban đầu.
Mục đích của phân đoạn là để đơn giản hóa và/hoặc thay đổi đại diện của
một ảnh thành thứ có ý nghĩa hơn và dễ dàng để phân tích/xử lý. 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 đó.
Kết quả của phân đoạn ảnh là một tập các phân đoạn mà nó bao trùm toàn
bộ ảnh hoặc một tập các đường mức trích chọn được từ ảnh (như phát hiện cạnh
trong ảnh). Mỗi một pixel trong một vùng là tương đồng nhau về một số thuộc
tính hoặc tính chất tính toán, ví dụ như màu sắc, cường độ hoặc cách cấu tạo,
v.v. Những khu vực liền kề là có sự khác nhau đáng kể về (những) thuộc tính
giống nhau. Khi áp dụng với một tập các ảnh, điển hình là trong hình ảnh nha
khoa, các đường mức thu được sau khi phân đoạn ảnh có thể được sử dụng để
tạo dựng thành 3D với sự giúp đỡ của các thuật toán nội suy.
Có nhiều thuật toán và kĩ thuật với mục đích chung đã được phát triển cho
phân đoạn ảnh.Thường thì những thuật toán này phải kết hợp với kiến thức của
một lĩnh vực cụ thể thì mới giải quyết hiệu quả bài toán phân đoạn của các miền.
1.4.2. Phân loại các phương pháp phân đoạn ảnh
Có hai tính chất cơ bản mà nói chung các phương pháp phân đoạn ảnh đều
dựa vào, đó là một trong hai giá trị của mật độ: sự tương đồng và sự gián đoạn.
Hướng tiếp cận chủ yếu trong phương pháp đầu tiên dựa trên việc phân đoạn
một ảnh thành các vùng tương đồng nhau theo một tập các tiêu chí xác định
trước. Hướng tiếp cận của phương pháp thứ hai là phân đoạn ảnh dựa trên sự
thay đổi đột ngột về cường độ (như cạnh trong ảnh)
20
Chúng ta có thể phân loại các phương pháp phân đoạn ảnh dựa trên giá trị
của các pixel và mối quan hệ giữa chúng với 3 vùng: dựa trên pixel, dựa trên
đường biên và dựa trên vùng. Trong hướng tiếp cận dựa trên pixel, sự phân lớp
dựa trên giá trị độ xám (cường độ) của pixel trong ảnh. Phương pháp dựa trên
biên dựa trên sự thay đổi đột ngột của giá trị cường độ trong một vùng ảnh.
Phương pháp dựa trên vùng dựa trên sự khác nhau trong các giá trị định trước
của các pixel láng giềng trong ảnh đó.
1.4.3. Phân đoạn ảnh X – quang nha khoa
Phân đoạn ảnh nha khoa là bước xửu lý then chốt trong nha khoa nhằm hỗ
trợ bác sĩ chuẩn đoán một cách hiệu quả các bệnh về răng. Để phân tích một ảnh
X – quang nha khoa, chúng ta cần sử dụng một số tiến trình xử lý trên ảnh để
thu được những thông tin quan trọng.
Theo góc nhìn đối với ảnh nha khoa, phân đoạn là để xác định và phân loại
các răng riêng lẻ trong ảnh X- quang nha khoa hoặc các phần của răng như thân
răng và chân răng. Mỗi một răng hoặc mỗi phần của mỗi răng trích chọn được từ
ảnh ban đầu cho những dữ liệu quan trọng sẽ được sử dụng trong các bước tiếp
theo ở bất kì một ứng dụng nào.
Ảnh X – quang nha khoa thường có 3 vùng chính:
- Vùng thứ nhất tương ứng với vùng chứa các răng. Vùng này thường có
giá trị mức xám lớn nhất (vùng sáng nhất trên ảnh). Đây chính là vùng mà ta cần
xác định được trong quá trình phân đoạn.
- Vùng thứ hai tương ứng với vùng chứa lợi, xương và các cấu trúc quanh
răng. Vùng này thường có mức xám trung bình, tuy nhiên một số vùng xương có
giá trị mức xám khá gần với vùng răng. Điều này gây khó khăn không nhỏ cho
quá trình phân đoạn răng.
- Vùng thứ ba tương ứng với vùng nền trong ảnh, có giá trị độ xám thấp
nhất (vùng tối nhất).
Phân đoạn những ảnh nha khoa có nhiều khó khăn hơn trong quá trình xử
lý bởi vì sự đa dạng, phức tạp trong cấu trúc liên kết giữa các bộ phận, và chất
21
lượng hình ảnh thấp (do nhiễu, độ tương phản thấp, sự giống nhau của các mô
cơ thể, sự giới hạn trong các phương pháp quét ảnh, v.v). Chính bởi những điều
đó khiến quá trình phân đoạn cho những kết quả sai/kém hiệu quả. Ví dụ như:
những mẫu vật được sử dụng trong quá trình điều trị, các răng nêm/chèn vào
nhau, sự biến thể của các răng, khoảng trống giữa những răng bị thiếu, cũng như
các vấn đề trong quá trình xử lý ảnh. Hình sau cho thấy những khó khăn có thể
xuất hiện trong các ảnh nha khoa:
a) Những b) Các răng chèn vào nhau.
thành phần khác được sử dụng để lấp đầy các răng.
c) Những biến thể khác d) Khoảng trống ở những vị trí răng bị
thiếu nhau của răng.
Hình 1.4. Những khó khăn trong việc phân đoạn ảnh nha khoa
Mỗi phương pháp phân đoạn được đề xuất cho một vấn đề này có thể thực
hiện tốt nhưng trên một vấn đề khác có thể thực hiện yếu kém và không đáng kể.
Vì vậy, rất khó để có được một phương pháp phân đoạn nhất định mà phù hợp
hoàn toàn cho một vấn đề mở rộng.
22
KẾT LUẬN CHƯƠNG 1
Chương 1 của luận văn đã nêu ra kiến thức tổng quan về phân cụm dữ liệu,
ứng dụng của phân cụm dữ liệu và về cấu trúc giải phẫu răng, phân loại ảnh X –
quang nha khoa, bài toán phân đoạn ảnh từ đó nêu ra bài toán, những yêu cầu,
thách thức và ý nghĩa, ứng dụng thực tế của bài toán phân đoạn ảnh X – quang
nha khoa trong các hệ thống nhận dạng người hay hệ thống chẩn đoán, điều trị
nha khoa.
Trong chương tiếp theo, luận văn sẽ đưa ra một cái nhìn tổng quan về các
phương pháp phân đoạn ảnh nha khoa hiện có. Ở mỗi phương pháp đều đưa ra
các thuật toán cụ thể và đánh giá ưu, nhược điểm của các thuật toán đó.
23
CHƯƠNG 2
MỘT SỐ THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT
Các thuật toán phân cụm đã được nghiên cứu và phát triển từ những năm
50 của thế kỷ 20 như thuật toán K-Means (1956), thuật toán phân cụm dựa trên
đồ thị (1973), thuật toán phân cụm dựa trên lý thuyết mờ (1980), thuật toán phân
cụm dựa trên mật độ (1996) [14]. Từ những năm 2000 trở lại đây, phương pháp
phân cụm nửa giám sát bắt đầu được phát triển mạnh mẽ (xem [8], [9], [10],
[15]), đặc biệt là các phương pháp phân cụm nửa giám sát mờ bởi tính hiệu quả
mà nó mang lại (xem [11], [12], [13]). Nội dung chương này tập trung nghiên
cứu các thuật toán phân cụm nửa giám sát mờ và được trình bày thành 5 mục:
Mục 2.1 là các khái niệm cơ bản về lý thuyết tập mờ [4] và thuật toán phân cụm
mờ [16]. Mục 2.2 trình bày thuật toán phân cụm nửa giám sát mờ bằng phương
pháp học tích cực [21]. Mục 2.3 trình bày thuật toán phân cụm nửa giám sát mờ
chuẩn [17]. Mục 2.4 trình bày thuật toán phân cụm nửa giám sát mờ theo quy tắc
entropy [18]. Mục 2.5 là thuật toán phân cụm lai ghép nửa giám sát [13].
2.1. Phân cụm mờ
2.1.1. Các khái niệm cơ bản về tập mờ
Tập rõ và tập mờ: Một tập hợp theo nghĩa kinh điển, nghĩa là một phần tử
hoặc thuộc vào tập hoặc không thuộc vào tập, được gọi là một tập rõ (crisp set).
Một tập mờ (fuzzy set) A trên một tập nền X được xác định bằng hàm thuộc
(membership function) , với giá trị là độ thuộc của phần tử x
vào tập mờ A. Tập nền X luôn là tập rõ. Nếu tập nền X là rời rạc và hữu
hạn thì tập mờ A trên X được biểu diễn bằng
hoặc , trong đó là
độ thuộc của vào A. Nếu tập nền X là liên tục, thì tập mờ A trên X được biểu
diễn bằng . Chú ý rằng “/” là ký tự phân cách; là phép kết
24
hợp; và “+” là phép nối giữa các thành phần chứ không phải là phép chia, tổng,
tích phân và cộng như thông thường.
Các dạng hàm thuộc: Có hai dạng hàm thuộc thông dụng là: (1) hàm
thuộc tuyến tính và (2) hàm thuộc dạng sin. Hình 2.1 minh họa hàm thuộc tuyến
tính. Hàm này có bốn tham số a, b, c và d xác định hình dạng của hàm. Bằng
cách chọn các giá trị phù hợp cho chúng, ta có thể có các hàm thuộc dạng chữ S
(S-shaped), hình thang, tam giác và dạng chữ L (L-shaped).
Hình 2.1. Hàm thuộc tuyến tính
Nếu dạng đường cong là thích hợp hơn, ta nên chọn hàm thuộc dạng
sin (Hình 2.2). Cũng như với hàm thuộc tuyến tính, ta có thể có hàm thuộc
dạng chữ S, dạng chuông (bell-shaped) và dạng chữ L bằng cách chọn các
tham số thích hợp.
Hình 2.2. Hàm thuộc dạng sin
25
Trường hợp đặc biệt của hàm thuộc hình chuông là hàm Gauss (Hình 2.3)
sinh ra từ hàm mật độ xác suất của phân phối thường với hai tham số c (giá trị
trung bình) và (độ lệch chuẩn). Mặc dù xuất phát từ lý thuyết xác xuất, hàm
này cũng được sử dụng làm hàm thuộc tập mờ.
Hình 2.3. Hàm thuộc Gauss
Phép toán trên tập mờ: Các phép toán trên tập mờ được định nghĩa tương
tự như các phép toán trên tập rõ, bao gồm hợp, giao và bù.
Độ cao của tập mờ A là giá trị độ thuộc lớn nhất của A, ký hiệu hgt(A).
Nếu hgt(A) = 1, tập mờ được gọi là chuẩn. Ta có thể chuẩn hóa một tập mờ
bằng cách chia tất cả độ thuộc cho độ cao của nó.
Tập mờ A là bao trong (tập con của) tập mờ B (viết ) nếu
. Tập mờ A bao trong tập mờ B nếu đồ thị của A hoàn toàn
được phủ bởi đồ thị của B (Hình 2.4).
Hình 2.4. Bao trong của tập mờ
26
Có nhiều cách xác định phép hợp của hai tập mờ. Sau đây là các phép hợp
thông dụng nhất, với mọi :
Phép max được gọi là không tương tác (non-interactive) theo nghĩa độ
thuộc của hai tập mờ không tương tác với nhau. Cụ thể, một tập mờ có thể hoàn
toàn bị bỏ qua trong phép hợp nếu nó bao trong tập còn lại. Hai phép toán còn
lại là tương tác do độ thuộc của phép hợp được xác định bởi cả hai độ thuộc
thành phần. Hình 2.5 minh họa phép hợp dạng 1 của các tập mờ thấp và trung
bình trong. Ví dụ:
Hình 2.5. Phép hợp tập mờ dạng 1
Phép giao của hai tập mờ A, B được tính theo một trong các phép toán
sau:
Phép min là không tương tác, hai phép toán còn lại là tương tác. Hình 2.6
minh họa phép giao dạng 1 của các tập mờ thấp và trung bình.
27
Hình 2.6. Phép giao tập mờ dạng 1
Phép bù của tập mờ A được xác định: . Hình 2.7
minh họa phần bù của tập mờ trung bình.
Hình 2.7. Phần bù của tập mờ trung bình
2.1.2. Thuật toán phân cụm mờ FCM (Fuzzy C-Means)
Ta có thể định nghĩa bài toán phân cụm rõ như sau: Cho tập dữ liệu mẫu X,
ta kiểm tra các điểm dữ liệu xem nó giống với đặc điểm của nhóm nào nhất thì
ta gán điểm dữ liệu đó vào trong nhóm đó. Nhưng trong thực tế không phải lúc
nào bài toán phân cụm rõ cũng đáp dụng được.
Mỗi phương pháp phân cụm phân hoạch một tập dữ liệu ban đầu thành các
cụm dữ liệu có tính tự nhiên và mỗi đối tượng dữ liệu chỉ thuộc về một cụm dữ
liệu, phương pháp này chỉ phù hợp với việc khám phá ra các cụm có mật độ cao
và rời nhau, với đường biên giữa các cụm được xác định tốt. Tuy nhiên, trong
thực tế, đường biên giữa các cụm có thể mờ, các cụm có thể chồng lên nhau,
nghĩa là một số các đối tượng dữ liệu thuộc về nhiều cụm khác nhau, do đó mô
hình này không mô tả được dữ liệu thực. Vì vậy người ta đã áp dụng lý thuyết 28
về tập mờ trong PCDL để giải quyết cho trường hợp này. Cách thức kết hợp này
được gọi là phân cụm mờ.
Phân cụm mờ là phương pháp phân cụm dữ liệu mà cho phép mỗi điểm dữ
liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Ruspini (1969) giới
thiệu khái niệm phân hoạch mờ để mô tả cấu trúc cụm của tập dữ liệu và đề xuất
một thuật toán để tính toán tối ưu phân hoạch mờ. Dunn (1973) mở rộng phương
pháp phân cụm và đã phát triển thuật toán phân cụm mờ. Ý tưởng của thuật toán
là xây dựng một phương pháp phân cụm mờ dựa trên tối thiểu hóa hàm mục
tiêu. Năm 1981, Bezdek [16] đã cải tiến và tổng quát hóa hàm mục tiêu mờ bằng
cách đưa ra trọng số mũ để xây dựng thuật toán phân cụm mờ và được chứng
minh độ hội tụ của các thuật toán là cực tiểu cục bộ. Hàm mục tiêu được Bezdek
đề xuất dựa trên độ thuộc của phần tử dữ liệu xk vào cụm thứ j và được xác
định như sau:
(2.1)
Trong đó: 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 vào cụm j; là phẩn tử thứ
k của x={x1 , x2 ,..., xN }; vj là tâm của cụm j.
Ràng buộc của (2.1) là:
(2.2)
Bài toán đặt ra là cần xác định tâm cụm V={vj } và ma trân độ thuộc
U={ukj} từ (2.1) - (2.2).
Để tìm tâm cụm vj từ bài toán cực trị (2.1) với ràng buộc (2.2) ta làm như
sau:
Lấy đạo hàm của phiếm hàm J theo vj, ta được:
(2.3)
Giải hệ phương trình : ta có tâm cụm
29
(2.4)
Tiếp theo, ta sử dụng phương pháp nhân tửu Lagrange [5] với điều kiện
ràng buộc (2.2) ta thu được ma trận độ thuộc
(2.5)
Khi đó thuật toán phân cụm mờ được thực hiện như sau:
Tập dữ liệu X gồm N phần tử trong không gian r chiều; số cụm C; Input
mờ hóa m; ngưỡng 𝜀; số lần lặp lớn nhất MaxStep.
Output Ma trận độ thuộc U và tâm cụm V
Các bước của thuật toán
t=0 1
Khởi tạo ngẫu nhiên U(t) thỏa mãn điều kiện (2.2) 2
3 Repeat
4 Tính V(t) ={vj } theo (2.4)
t=t+1 5
6 Tính U(t) ={ukj} theo (2.5)
7 Until hoặc t > MaxStep
Việc chọn các tham số cụm rất ảnh hưởng đến kết quả phân cụm, tham số
này thường được chọn theo phép ngẫu nhiên hoặc theo kinh nghiệm.
Chưa có quy tắc nào nhằm lựa chọn tham số m đảm bảo việc phân cụm
hiệu quả, thông thường người ta chọn m = 2.
30
Nhược điểm lớn nhất của thuật toán FCM là nhạy cảm với các nhiễu và
phần tử ngoại lai trong dữ liệu. Nghĩa là các tâm cụm có thể nằm xa so với tâm
cụm thực tế. Do đó các cụm dữ liệu được khám phá có thể rất lệch so với các
cụm trong thực tế. Việc khử nhiễu và phần tử ngoại lai là một vấn đề cần phải
được giải quyết.
Phân cụm mờ là một sự mở rộng của phân cụm dữ liệu bằng cách thêm
vào yếu tố thể hiện mối quan hệ giữa các phần tử và các cụm dữ liệu thông qua
các trọng số trong ma trận U. Bằng cách này, ta có thể khám phá các cụm dữ
liệu phức tạp theo cách mềm dẻo từ một tập dữ liệu dã cho.
2.2. Thuật toán phân cụm nửa giám sát mờ bằng phương pháp học tích
cực
Các thuật toán phân cụm nửa 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, điều khiển quá trình phân
cụm và được xây dựng dựa trên 3 loại cơ bản sau:
- 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.
Với mục tiêu nâng cao chất lượng phân cụm, năm 2008, Grira [21] sử
dụng thông tin bổ trợ là là các ràng buộc Must-link và Cannot-link. Theo
phương pháp này, ta ký hiệu M là tập các ràng buộc Must-link, điều này có
nghĩa là M={(xi, xj): xi và xj thuộc cùng một cụm}, ∆ là tập các ràng buộc
Cannot-link, có nghĩa là M={(xi, xj): xi và xj không thuộc cùng một cụm}, khi đó
hàm mục tiêu được xác định như sau:
(2.6)
31
Giải hệ phương trình : ta có tâm cụm
(2.7)
Tìm cực trị của (2.6) với điều kiện ràng buộc (2.2) xác định được
(2.8)
Trong đó
(2.9)
(2.10)
(2.11)
M là tổng số các ràng buộc Must-link và Cannot-link.
Thuật toán thực hiện như sau:
Tập dữ liệu X gồm N phần tử trong không gian r chiều; số cụm C; Input
ngưỡng ε; số lần lặp lớn nhất MaxStep.
Output Ma trận độ thuộc U và tâm cụm V
Các bước của thuật toán
1 t=0
2 Khởi tạo ngẫu nhiên V(t)
3 Repeat
32
t=t+1 4
Tính theo (2.11) 5
6 Tính U(t) ={ukj} theo (2.8)
Cập nhật V(t) theo (2.7) 7
8 Until hoặc t > MaxStep
2.3. Thuật toán phân cụm nửa giám sát mờ chuẩn (SSSFC)
Gần đây, một số nghiên cứu về phân đoạn ảnh sử dụng phân cụm nửa giám
sát thường dùng loại thông tin bổ trợ là giá trị hàm độ thuộc được xác định
trước. Với loại thông tin bổ trợ này, Yasunuri [17] đã đề xuất một thuật toán
phân cụm nửa giám sát mờ 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 được xác định như sau:
(2.12)
Với điều kiện ràng buộc (2.2), là hàm độ thuộc bổ trợ của phần tử với
cụm đồng thời thỏa mãn
.
Giải hệ phương trình : ta có tâm cụm
(2.13)
Sử dụng phương pháp nhân tử Lagrange [5] tìm cực trị của (2.6) với điều kiện
ràng buộc (2.2) ta xác định được như sau:
Trường hợp :
33
, , . (2.14)
Trường hợp m=1:
, , . (2.15)
Thuật toán SSSFC:
Tập dữ liệu X gồm N phần tử trong không gian r chiều; số cụm C; Input
ma trận độ thuộc bổ trợ ; mờ hóa m; ngưỡng ԑ; số lần lặp lớn nhất
MaxStep.
Output Ma trận U và tâm cụm V
Các bước của thuật toán
t=0 1
2 Khởi tạo ngẫu nhiên V(t) ={vj }
3 Repeat
4 Tính U(t) ={ukj} theo (2.14) nếu m>1 hoặc theo (2.15) nếu m=1
t=t+1 5
6 Tính V(t) ={vj } theo (2.13)
7 Until hoặc t > MaxStep
34
2.4. Thuật toán phân cụm nửa giám sát mờ theo quy tắc entropy
(eSFCM)
Năm 2009, Zhang [20] đã á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. Đến năm 2012, Yin [18] có đề xuất hiệu chỉnh hệ số
Entropy và khi đó phân cụm nửa giám sát mờ dựa trên thuật toán eSFCM, sử
dụng độ thuộc bổ trợ để tăng hiệu suất phân cụm với điều kiện:
(2.16)
Với tâm cụm ban đầu được xác định theo công thức:
(2.17)
Sử dụng khoảng cách Mahalanobis, ma trận hiệp phương sai của các mẫu
được xác định:
(2.18)
Khoảng cách Mahalanobis:
(2.19)
Khi đó hàm mục tiêu của eSFCM được xác định như sau:
(2.20)
Với điều kiện ràng buộc (2.2) và hàm mục tiêu (2.19) ta có các công thức
xác định ma trận độ thuộc:
(2.21)
35
và tâm cụm:
(2.22)
Thuật toán eSFCM
Input
Tập dữ liệu X gồm N phần tử trong không gian r chiều; số cụm C; ma trận độ thuộc 𝑈̅ ; ngưỡng ε; số lần lặp lớn nhất MaxStep.
Output Ma trận độ thuộc U và tâm cụm V
Các bước của thuật toán
t=0 1
Tính ma trận P theo (2.18) với ma trận độ thuộc 2
và tâm cụm ban đầu V(0).
3 Repeat
4 t=t+1
5 Tính U(t) ={ukj} theo (2.21)
6 Tính V(t+1) theo (2.22)
7 Until hoặc t > MaxStep
2.5. Thuật toán nửa giám sát mờ lai ghép
Trong mục này, tác giả trình bày thuật toán nửa giám sát mờ lai ghép [13]
được thực hiện dựa trên sự lai ghép của thuật toán Otsu, thuật toán phân cụm mờ
(FCM) với thuật toán phân cụm nửa giám sát mờ (eSFCM).
2.5.1. Lược đồ tổng quan lai ghép
Trong hình 2.8 [6], luận văn minh họa mô hình kết hợp giữa Otsu – FCM –
eSFCM bằng một sơ đồ tổng quan. Đầu vào là một ảnh X-Quang nha khoa với
36
một vài tham số do người dùng xác định như là số lượng cụm (C), số mờ hóa
(m), ngưỡng Otsu (T) và ngưỡng dừng (𝜀).
Bắt đầu
Ảnh đầu vào và các tham số
Kiểm tra xem ảnh đầu vào có vùng nền
Sai
Đúng
Dùng phương pháp tách ngưỡng Otsu để loại bỏ vùng nền trong ảnh
Dùng phương pháp phân cụm FCM để xác định ma trận độ thuộc
Dùng phương pháp phân cụm eSFCM để phân đoạn ảnh với thông tin bổ trợ xác định từ ma trận độ thuộc
Đánh giá hiệu năng thuật toán bằng các tiêu chuẩn
Kết quả ảnh phân đoạn
Kết thúc
Hình 2.8. Lược đồ tổng quan của thuật toán lai ghép
37
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ủ thuật để kiểm tra điều này trước khi phân đoạn ảnh. Thuật toán
Otsu được áp dụng để loại bỏ các khu vục nền từ ảnh. Vùng nền là phần có giá
trị độ xám nhỏ nhất và là nền tảng của cấu trúc răng. Thuật toán này có ưu điểm
là xử lý nhanh và hiệu quả, đồng thời có thể phân biệt nền với các phần chính
của ảnh. Sau đó, tiến hành phân cụm mờ bằng thuật toán 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 áp 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
sau đó.
Ý nghĩa của thuật toán lai ghép (Otsu – FCM - eSFCM):
Khi sử dụng thuật toán Otsu [22] có thể xác định được các vùng độc lập
dựa trên việc tách ngưỡng từ một ảnh X-quang nha khoa. Thuật toán này
có ưu điểm là xử lý nhanh, hiệu quả và có thể xác định các vùng theo
ngưỡng vì vậy được sử dụng trong các bước tiền xử lý của đề xuất.
Cho phép sử dụng các thuật toán phân cụm mờ để xác định thông tin bổ
trợ cho phân cụm bán giám sát mờ thông qua ma trận độ thuộc nhận được.
Cho phép sử dụng các thuật toán eSFCM để nâng cao chất lượng cụm của
quá trình phân cụm từ đó nâng cao chất lượng ảnh phân đoạn.
2.5.2. Thuật toán tách ngưỡng Otsu
Thuật toán tách ngưỡng Otsu biến đổi một hình ảnh đầu vào thành một
ảnh nhị phân. Nó được giới thiệu trong [22] và cũng được sử dụng trong [23]
bởi Rad, Rahim &Norouzi. Một ảnh đầu vào có thể chia thành 3 khu vực theo
cường độ ảnh trong đó vùng có cường độ thấp nhất tương ứng với nền hoặc
vùng mô mềm; các khu vực có cường độ trung bình tương ứng với xương; và
các khu vực có cường dộ cao nhất tương ứng với răng. Tuy nhiên, trong trường
38
hợp các ảnh có cường độ của các răng nhiều thì hoàn toàn chia thành 2 vùng là
vùng nền và vùng ảnh (hay vùng chính), nên được sử dụng trong thuật toán
Otsu.
Otsu là một thuật toán tách ngưỡng nổi tiếng trong các kỹ thuật xử lý ảnh
dựa trên điểm ảnh. Kỹ thuật đơn giản nhất trong các thuật toán tách ngưỡng là
phân chia ảnh thành hai vùng dựa trên một ngưỡng toán cục T. Trong trường
hợp này, thuật toán Otsu chọn một ngưỡng với mục tiêu nhằm giảm thiểu những
thay đổi của các lớp bên trong của các điểm ảnh màu đen và trắng (nhãn mỗi
điểm trong ảnh thuộc vào vùng chính r0 hoặc vùng nền r1). Mỗi điểm ảnh được
gán nhãn dựa trên giá trị cấp xám của nó (f(x)). Nói cách khác:
Kết quả của bước tách ngưỡng là một ảnh nhị phân để đơn giản hóa quá
trình phân tích ảnh trong các bước tiếp theo.
Trong trường hợp tổng quát mà số lượng các cụm (C) là lớn hơn 2, nhiều
ngưỡng có thể được sử dụng để xác định các cụm khác nhau. Giả sử T1, T2, ...,Tn
(Ti là điểm cách đều trong đoạn [min, max] với mọi i = 1, 2, ... , n là các
ngưỡng. Giá trị của mỗi điểm ảnh f(x) được tính là trung bình của các giá trị R,
G, B tại điểm ảnh đó.
Thuật toán tách ngưỡng Otsu:
Input: Một ảnh X-Quang nha khoa và số lần lặp lớn nhất MaxStep
Output: Ảnh nhị phân của ảnh đầu vào
Otsu:
Bước 1: Chọn ngưỡng khởi tạo , số bước lặp t = 1
Bước 2: Repeat
2.1. t = t + 1
39
2.2. Phân hoạch ảnh thành 2 nhóm (dựa vào ngưỡng )
2.3. Tính toán giá trị mức xám trung bình trên các nhóm
2.4.Tính ngưỡng mới theo công thức
hoặc t = MaxStep Bước 3: Until
Rõ ràng là:
Một điểm ảnh thuộc vào
Sau đó, uị trong ma trận thuộc U gán bằng 1 nếu điểm ảnh j thuộc về cụm
thứ i và bằng 0 nếu ngược lại.
2.5.3. Thuật toán phân cụm nửa giám sát mờ lai ghép
Input: Ảnh đầu vào, số cụm C, ma trận độ thuộc 𝑈̅; ngưỡng dừng 𝜀; số
lần lặp lớn nhất MaxStep > 0
Output: Ảnh phân đoạn
Lai ghép:
Bước 1: Sử dụng thuật toán xử lý ảnh lấy ngưỡng Otsu
Bước 2: Phân cụm mờ (FCM) xác định ma trận độ thuộc UFCM Bước 3: Xây dựng thông tin bổ trợ 𝑈̅ 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.
Bước 4: Phân cụm nửa giám sát mờ (eSFCM) với ảnh đầu vào và thông tin bổ trợ U̅
Bước 5: Ảnh phân đoạn
Như vậy, thuật toán phân cụm nửa giám sát mờ lai ghép là một sự kết hợp
giữa thuật toán tách ngưỡng Otsu, thuật toán phân cụm mờ FCM và phân cụm
nửa 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
40
đị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 đoạn ảnh cuối cùng.
KẾT LUẬN CHƯƠNG 2
Trong chương này, luận văn đã nêu ra bài toán nghiên cứu và có được cái
nhìn tổng quan về bài toán phân cụm mờ, các phương pháp phân phân cụm mờ
và phân cụm bán giám sát mờ. Ở mỗi phương pháp luận văn đều có đánh giá ưu
nhược điểm và trình bày các thuật toán cụ thể, trong đó có trình bày thuật toán
phân cụm bán giám sát mờ lai ghép là cơ sở để tác giả xây dựng một ứng dụng
thử nghiệm ở chương 3.
41
CHƯƠNG 3
XÂY DỰNG ỨNG DỤNG PHÂN ĐOẠN ẢNH
X – QUANG NHA KHOA
3.1. Đặc tả yêu cầu
3.1.1. Yêu cầu thực tế
Như đã giới thiệu ở phần trước, việc xử lý các hình ảnh y tế ngày càng có
vai trò quan trọng, hỗ trợ bác sĩ trong chẩn đoán, điều trị nhiều loại bệnh khác
nhau. Một loại ảnh y tế vô cùng phổ biến và được chỉ định chụp cho nhiều loại
bệnh khác nhau đó là ảnh X – quang.
Thêm vào đó, như chúng ta đã biết, các loại bệnh về răng miệng rất phổ
biến ở mọi lứa tuổi. Các chuyên gia y tế đã cho biết hiện tại 90% người Việt
đang mắc các bệnh về răng miệng, chủ yếu là sâu răng và các bệnh nha chu, tới
75% người bị mắc sâu răng vĩnh viễn và 60% người Việt mắc các bệnh về tổ
chức cứng của răng như sâu, mòn, ảnh hưởng ăn nhai, gây vỡ, đục khoét hết
chân răng. Để chẩn đoán và điều trị những bệnh răng miệng, đặc biệt là những
bệnh liên quan đến cấu trúc về phần cứng của răng (sâu răng, rạn/vỡ/đục khoét
chân răng, xương ổ răng hoặc cấu trúc hàm, v.v.), bác sĩ thường chỉ định chụp
ảnh X – quang (với loại ảnh phù hợp với từng loại bệnh) để có thể quan sát được
vùng bệnh một cách tốt nhất.
Với số lượng bệnh nhân rất lớn như thế, việc phát triển các hệ thống hỗ trợ
chẩn đoán cũng như điều trị các bệnh răng miệng dựa trên các hình ảnh nha
khoa thu được là điều vô cùng cần thiết. Nó giúp giảm tải khối lượng công việc
của bác sĩ, hỗ trợ bác sĩ đưa ra quyết định một cách chính xác hơn, từ đó nâng
cao hiệu quả khám chữa bệnh.
Trong các hệ thống xử lý hình ảnh nha khoa đó, một giai đoạn cơ bản
không thể thiếu đó là phân đoạn ảnh X – quang đầu vào. Phân đoạn sẽ xác định
các vùng chứa răng trong ảnh X – quang nha khoa.Từ đó, dựa vào các vùng răng
42
thu được mới thực hiện các bước tiếp theo trong hệ thống như xác định hình
dáng, vị trí, các vùng bị tổn thương, v.v.
3.1.2. Mục đích của ứng dụng
Từ yêu cầu thực tế đặt ra, ứng dụng này nhằm mục đích phân đoạn ảnh X –
quang nha khoa dựa vào thuật toán phân cụm bán giám sát mờ mà cụ thể là thuật
toán bán giám sát mờ lai ghép (Otsu – FCM - eSFCM). Ứng dụng cho phép
phân đoạn ảnh X – quang thành các vùng khác nhau trong đó có vùng chứa răng,
nhằm loại bỏ những vùng nền không hữu ích trong các quá trình xử lý tiếp theo
của hệ thống nhận dạng, chẩn đoán hay điều trị nha khoa.
3.2. Đặc tả dữ liệu
Dữ liệu được sử dụng trong chương trình là ảnh X – quang nha khoa quanh
chóp và cắn cánh. Như đã giới thiệu ở phần 1.3.2, ảnh cắn cánh mô tả một
vùng của hàm trên và dưới. Với mỗi một chiếc răng nó cho thấy từ đỉnh đến
phần xương hỗ trợ. Ảnh cắn cánh thường được sử dụng để phát hiện sâu răng
giữa các răng và sự thay đổi mật độ răng gây ra bởi các bệnh về nướu răng. Nó
cũng rất hữu ích trong việc xác định các điều trị chỉnh nha phù hợp. Ảnh quanh
chóp cho thấy kích thước đầy đủ của một số chiếc răng (thường thì tối đa là 4
chiếc) trong một phần của hàm trên hoặc dưới. Chính vì khả năng mô tả chi tiết
từng chiếc răng nên loại ảnh này được sử dụng để phát hiện các bất thường của
một vài chiếc răng hay trong cấu trúc của chân răng và xung quanh răng ở phạm
vi hẹp.
Các ảnh được sử dụng làm dữ liệu về bản chất đều là ảnh xám, tuy nhiên nó
được lưu trữ dưới dạng truecolor với định dạng ảnh jpg. Bảng dưới đây mô tả
chi tiết đặc điểm của từng ảnh.
trị trị
Ảnh trị Giá pixel min Độ phân giải (dpi) Giá pixel max Dung lượng (KB)
Kích thước (width x hight) 229 x 160 96 img_1 255 0 Giá pixel trung bình 97.5949 3,41
img_2 257 x 196 96 255 0 116.5837 4,60
43
img_3 259 x 194 96 255 0 104.3974 8,10
img_4 474 x 620 96 255 0 96.4496 42,4
img_5 200 x 174 96 241 0 100.5537 3,30
img_6 300 x 214 96 225 0 93.1376 14,0
img_7 300 x 237 96 244 0 108.5878 14,4
img_8 500 x 355 96 255 0 107.4877 41,3
Bảng 2. Thuộc tính của các ảnh dữ liệu đầu vào
a) img_1 b) img_2 c) img_3 d) img_4
e) img_5 f) img_6 g) img_7 h) img_8
Hình 3.1: Ảnh dữ liệu đầu vào của ứng dụng
3.3. Các bước phân đoạn ảnh
Bài toán phân đoạn ảnh X – Quang nha khoa bằng thuật toán phân cụm nửa
giám sát mờ lai ghép gồm các bước sau:
- Bước 1: Đọc ảnh X – quang đầu vào và các tham số.
Bước này cho phép chọn ảnh X – quang cần phân đoạn vào ứng dụng.
Ảnh 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 trước khi phân đoạn ảnh.
- Bước 2: Sử dụng phương pháp tách ngưỡng Otsu để loại bỏ vùng nền
trong ảnh.
- Bước 3: Phân cụm mờ xác định ma trận độ thuộc.
44
Bước này thực hiện quá trình phân đoạn ảnh theo thuật toán phân cụm mờ
FCM để xác định ma trận độ thuộc UFCM
- Bước 4: Xây dựng thông tin bổ trợ 𝑈̅ từ ma trận độ thuộc UFCM
Tại bước này ta thu được ma trận độ thuộc bổ trợ 𝑈̅ từ mà trận độ thuộc
UFCM bằng cách bỏ đi các giá trị hàm thuộc nhỏ nhất tại các điểm.
- Bước 5: Phân cụm nửa giám sát mờ
Bước này thực hiện việc phân đoạn ảnh dựa vào thuật toán phân cụm nửa giám sát với đầu vào là ảnh và thông tin bổ trợ 𝑈̅
- Bước 6: Hiển thị kết quả: Hiển thị kết quả phân đoạn thu được và kết
thúc.
3.4. Thiết kế hệ thống
Hệ thống cho phép người dùng phân đoạn ảnh X – quang nha khoa, xem
chi tiết kết quả cũng như thời gian chạy và các độ đo đánh giá chất lượng phân
cụm.
Hình 3.2: Biểu đồ usecase mô tả chức năng của ứng dụng
3.4.1. Chức năng phân đoạn ảnh X – quang nha khoa
- Tác nhân: Người dùng
- Input: ảnh X – quang nha khoa cần phân đoạn
- Output: ảnh đã được phân đoạn
- Mô tả chi tiết:
45
+ Người dùng chọn ảnh cần phân đoạn
+ Người dùng nhập các tham số
+ Hệ thống kiểm tra tham số và yêu cầu nhập lại cho đến khi
thỏa mãn
+ Người dùng chọn phân đoạn ảnh
+ Hệ thống thực hiện phân đoạn bằng thuật toán eSFCM và trả
lại kết quả.
Do begin
While (Tham số thỏa mãn)
- Biểu đồ trình tự:
Hình 3.3: Biểu đồ trình tự chức năng phân đoạn ảnh
3.4.2. Chức năng xem chi tiết kết quả
- Tác nhân: Người dùng
- Input: Ảnh đã được phân đoạn và người dùng chọn xem chi tiết kết
quả phân cụm (phân đoạn).
- Output: Kết quả chi tiết được hiển thị
46
- Mô tả chi tiết:
+ Người dùng chọn chức năng xem chi tiết kết quả
+ Hệ thống hiển thị kết quả chi tiết
- Biểu đồ trình tự:
Hình 3.4: Biểu đồ trình tự chức năng xem kết quả
3.4.3. Chức năng đánh giá chất lượng phân đoạn
- Tác nhân: Người dùng
- Input: Ảnh đã được phân đoạn và người dùng chọn các độ đo đánh
giá kết quả phân cụm (phân đoạn).
- Output: Kết quả đánh giá được hiển thị
- Mô tả chi tiết:
+ Người dùng chọn chức năng đánh giá kết quả
+ Hệ thống hiển thị kết quả đánh giá
47
- Biểu đồ trình tự:
Hình 3.5: Biểu đồ trình tự chức năng đánh giá kết quả
3.5. Minh họa các chức năng của ứng dụng
3.5.1. Giao diện chính của ứng dụng
Hình 3.6: Giao diện chính của phần mềm
48
3.5.2. Chọn ảnh cần phân đoạn
Hình 3.7: Chọn ảnh cần phân đoạn
3.5.3. Phân đoạn ảnh bằng thuật toán FCM
Hình 3.8. Kết quả phân đoạn bằng FCM
49
3.5.4. Phân đoạn ảnh bằng thuật toán nửa giám sát mờ
Hình 3.9. Kết quả phân đoạn bằng SSSFC
3.5.5. Chọn độ đo đánh giá kết quả phân cụm
Hình 3.10. Đánh giá kết quả phân đoạn
50
3.6. Đánh giá kết quả phân đoạn
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. Trong phần cài đặt thực nghiệm, luận văn sử dụng các độ đo phân cụm sau:
Độ đo Davies-Bouldin (DB): có liên quan đến tiêu chuẩn tỷ số phương sai, dựa trên tỷ số giữa khoảng cách bên trong nhóm và khoảng cách bên ngoài nhóm. Đặc biệt, chất lượng của phân cụm được xác định bởi công thức sau:
𝑘 ∑ 𝐷𝑙 𝑙=1
𝐷𝐵 = (3.1) 1 𝑘
{𝐷𝑙,𝑚} (3.2)
𝑚)
𝑙 + 𝑑̅ 𝑑𝑚,𝑙
𝐷𝑙 = max 𝑙≠𝑚 (𝑑̅ (3.3) 𝐷𝑙,𝑚 =
𝑙, 𝑑̅
𝑚 là khoảng cách trung bình của các cụm l và m tương ứng,
Trong đó 𝑑̅
𝑑𝑚,𝑙 là khoảng cách giữa các cụm này. Cụ thể:
𝑙 =
𝑑̅ (3.4) 1 𝑁𝑙 ∑ ‖𝑥𝑖 − 𝑥̅𝑙‖; 𝑑𝑙,𝑚 = ‖𝑥̅𝑙 − 𝑥̅𝑚‖ 𝑥𝑖𝜖𝐶𝑙
Giá trị của DB càng nhỏ càng tốt
Độ đo Simplified Silhouete Width Criterion (SSWC): Là độ đo được tính
theo công thức:
𝑁 ∑ 𝑆𝑥𝑗 𝑗=1
𝑆𝑆𝑊𝐶 = (3.5) 1 𝑁
(3.6) 𝑆𝑥𝑗 = 𝑏𝑝,𝑗 − 𝑎𝑝,𝑗 𝑚𝑎𝑥{𝑎𝑝,𝑗, 𝑏𝑝,𝑗}
Trong đó 𝑎𝑝,𝑗 được định nghĩa là sự khác biệt của đối tượng p với cụm j của nó. Một cách tương tự, 𝑑𝑞,𝑗 là sự khác biệt của đối tượng q tới cụm j, 𝑞 ≠ 𝑝.
Độ đo PBM: Dựa trên khoảng cách của các cụm và khoảng cách giữa các
cụm với nhau. Độ đo PBM được tính toán theo công thức:
51
2
𝑘
𝑁
(3.7) 𝑃𝐵𝑀 = ( 𝐷𝐾) 1 𝑘 𝐸1 𝐸𝐾
𝑖=1
𝑙=1
(3.8) 𝐸1 = ∑‖𝑥𝑖 − 𝑥̅‖
, 𝐸𝐾 = ∑ ∑ ‖𝑥𝑖 − 𝑥̅𝑙‖ 𝑥𝑖𝜖𝐶𝑙
𝑙,𝑚=1,…,𝑘
𝐷𝐾 = max ‖𝑥̅𝑙 − 𝑥̅𝑚‖ (3.9)
Rõ ràng là trong độ đo PBM, giá trị càng cao thì hiệu năng của thuật toán càng cao. Do đó, phân hoạch tốt nhất nhận được khi PBM đạt giá trị cao nhất. Điều này xảy ra khi 𝐷𝐾 đạt cực đại còn 𝐸𝐾 đạt cực tiểu.
Độ đo IFV: Là độ đo được tính theo công thức
2
(3.10)
(3.11) ‖𝑉𝑘 − 𝑉𝑗‖ 𝑆𝐷𝑚𝑎𝑥 = max 𝑘≠𝑗
(3.12)
Giá trị của IFV càng lớn thì thuật toán càng hiệu quả.
KẾT LUẬN CHƯƠNG 3
Chương 3 đã mô tả quá trình xây dựng ứng dụng phân đoạn ảnh X – quang
nha khoa bằng phương pháp phân cụm mờ ban giám sát, cụ thể là thuật toán bán
giám sát mờ lai ghép: từ đặc tả yêu cầu, thiết kế đến triển khai cài đặt. Từ đó
minh họa một cách rõ ràng cách hoạt động, ứng dụng cũng như hiệu quả của
thuật toán phân cụm mờ trong phân đoạn ảnh X – quang nha khoa.Một số kết
quả của các ảnh phân đoạn cũng được đưa ra.
52
KẾT LUẬN
Với rất nhiều ý nghĩa trong thực tế, xử lý ảnh ngày càng thu hút sự quan
tâm đặc biệt từ các nhà khoa học trên thế giới, đặc biệt là trong xử lý các hình
ảnh y tế như X – quang, CT, v.v. Trong đó, phân đoạn ảnh được coi như bước
cơ bản và thiết yếu đầu tiên trước khi áp dụng các thao tác xử lý ảnh mức cao
hơn.
Xuất phát từ ý nghĩa thực tế đó, cùng với sự quan tâm và hứng thú với phân
đoạn ảnh nói chung và áp dụng vào phân đoạn ảnh nha khoa nói riêng, khóa
luận đã nghiên cứu và trình bày một số nội dung chính như sau:
- Tìm hiểu được những kiến thức tổng quan về giải phẫu răng, các loại ảnh
X – quang nha khoa, phân đoạn ảnh. Từ đó đặt bài toán phân đoạn ảnh X –
quang nha khoa và các ứng dụng thực tiễn của bài toán.
- Tổng hợp các phương pháp phân đoạn ảnh nha khoa điển hình, với mỗi
phương pháp đều đưa ra thuật toán, đánh giá và các ví dụ trực quan về từng
thuật toán. Từ đó cho chúng ta có cái nhìn từ tổng thể đến chi tiết các thuật toán
phân đoạn ảnh nha khoa hiện có.
- Cài đặt thuật toán phân cụm bán giám sát mờ lai ghép (Otsu - FCM –
eSFCM) để phân đoạn ảnh X – quang nha khoa. Trong đó có đưa ra các độ đo
(DB, PBM, SSWC) và thời gian chạy để đánh giá chất lượng của kết quả thu
được. Từ đó cho thấy tính hiệu quả của thuật toán phân cụm mờ ứng dụng trong
việc phân đoạn ảnh X – quang nha khoa.
Dựa trên những kết quả bước đầu đã đạt được, trong tương lai, đề tài có thể
được phát triển theo các hướng như sau:
- Tiếp tục cải tiến, xây dựng một phương pháp phân cụm mờ mới để đạt
được hiệu quả phân đoạn ảnh cao hơn.
- Phát triển hệ thống hỗ trợ chẩn đoán bệnh nha khoa, trong đó phân đoạn
ảnh là một bước thiết yếu để phân tích các đặc trưng và phát hiện các bệnh trên
răng.
53
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Đỗ Phúc (2006), Giáo trình khai phá dữ liệu , Nxb Đại học Quốc gia TP Hồ Chí
Minh.
[2] Nguyễn Thanh Thủy (2001), Khai phá dữ liệu, Nhà xuất bản Kỹ thuật và ứng
dụng.
[3] Hoàng Tử Hùng, Huỳnh Kim Khang, Ngô Thị Quỳnh Lan, Ngô Lê Thu
Thảo, Hoàng Đạo Bảo Trâm (2008), Giải phẫu Răng, Nhà xuất bản Y học, Hà
Nội.
[4] Bùi Công Cường (2001), Hệ mờ, mạng nơron và ứng dụng, Nhà xuất bản
khoa học và kỹ thuật, Hà nội.
[5] Doãn Tam Hòe (2005), Lý thuyết tối ưu và đồ thị, nhà xuất bản giáo dục.
[6] Trần Mạnh Tuấn, Phạm Huy Thông, Lê Hoàng Sơn, Nguyễn Đình Hóa
(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, 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.
Tiếng Anh
[6] Guojun Gan, Chaoqun Ma, Jianhong Wu (2007), Data Clustering, Theory,
Algorithms, and Applications, Society for Industrial and Applied Mathematics, United
States of America.
[7] Kiri Wagsta, Claire Cardie (2001), Constrained K-means Clustering with
Background Knowledge, Proceedings of the Eighteenth International Conference on
Machine Learning, page 577-584.
[8] Basu, S., Banerjee, A., Mooney, R. (2002), Semi–supervised clustering by
seeding, Proceedings of 19th International Conference on Machine Learning,
ICML.
[9] Sugato Basu, Mikhail Bilenko, Raymond J. Mooney (2004), A Probabilistic
Framework for Semi-Supervised Clustering, Proceedings of the Tenth ACM
54
SIGKDD International Conference on Knowledge Discovery and Khai phá dữ
liệu, page 59-68.
[10] Cui-Fang Gao, Xiao-Jun Wu, Song-Shun Zhang (2009), An improved semi-
supervised fuzzy clustering algorithm, Control and Decision, 25 (1), 115-120.
[11] Liang Chen, Xiaojun Wu, Cuifang Gao (2012), Semi-supervised Fuzzy
Clustering Algorithm Based on QPSO, Journal of Information & Computational
Science, page 93-101.
[12] Le Hoang Son, Tran Manh Tuan (2016) , A cooperative semi-supervised
fuzzy clustering framework for dental X-ray image segmentation, Expert Systems
With Applications, 46, pp. 380 – 393.
[13] Anil K. Jain (2010): Data clustering: 50 years beyond Kmeans. Pattern
Recognition Letters (PRL) 31(8):651-666.
[14] S. Basu, I. Davidson (2008), and K. L. Wagstaff, Constrained Clustering:
Advances in Algorithms, Theory, and Applications, Chapman and Hall/CRC
Data Mining and Knowledge Discovery Series, 1st edn.
[15] Bezdek, J. C. (1981), Pattern recognition with fuzzy objective function
algorithms, Kluwer Academic Publishers.
[16] Yasunori, E., Yukihiro, H., Makito, Y., & Sadaaki, M. (2009), On semi-
supervised fuzzy c-means clustering. In Fuzzy Systems, FUZZ-IEEE 2009. IEEE
International Conference on (pp. 1119-1124). IEEE.
[17] Yin, X., Shu, T., & Huang, Q. (2012), Semi-supervised fuzzy clustering
with metric learning and entropy regularization, Knowledge-Based
Systems, 35, 304-311.
[18] Y.C Hu, M.C Grossberg, and G. Mageras (2009), Survey of recent
volumetric medical image segmentation techniques, Biomedical Engineering,
InTech, Carlos Alexandre Barros de Mello (Ed.), ISBN: 978‑953‑307‑013‑1.
[19] Zhang, H., & Lu, J. (2009), Semi-supervised fuzzy clustering: A kernel-
based approach. Knowledge-Based Systems, 22(6), 477-481.
55
[20] Grira, N., Crucianu, M., and Boujemaa, N. (2008), Active semi-
supervised fuzzy clustering, Pattern Recognition, vol. 41, no. 5, pp. 1834-1844.
[21] Otsu, N. (1979), A threshold selection method from gray-level
histograms Automatica, 1(9), 62-66.
[22] Rad A. E., Mohd Rahim M. S., Rehman A., Altameem A. and Saba
T. (2013), Evaluation of current dental radiographs segmentation
approaches in computer-aided applications, IETE Technical Review, 30(3),
210-222.
56
PHỤ LỤC
CODE MATLAB CỦA ỨNG DỤNG PHÂN ĐOẠN ẢNH BẰNG THUẬT TOÁN BÁN GIÁM SÁT MỜ LAI GHÉP
1. Đọc ảnh:
function btn_open_Callback(hObject, eventdata, handles) [filename, pathname] = uigetfile({'*.jpg'}, 'Pick a deltal X - ray image'); set(handles.result_panel, 'visible', 'off'); set(handles.algorithms_panel, 'visible', 'off'); if filename ~= 0 IM = imread([pathname, filename]); axes(handles.original_img); imshow(IM); handles.num_of_data_point = size(IM(:, : , 1), 1) * size(IM(:, : , 1), 2); handles.filename = filename; set(handles.original_img,'UserData',IM); set(handles.final_img_panel, 'visible', 'off'); set(handles.result_panel, 'visible', 'on'); set(handles.num_of_clust, 'enable', 'on'); set(handles.num_of_clust,'UserData', 5); set(handles.num_of_clust,'string', '5'); set(handles.exponent, 'enable', 'on'); set(handles.exponent,'UserData', 2); set(handles.exponent,'string', '2'); set(handles.epsilon, 'enable', 'on'); set(handles.epsilon,'UserData', 0.005); set(handles.epsilon,'string', '0.005');
57
set(handles.max_num_iter, 'enable', 'on'); set(handles.max_num_iter,'UserData', 150); set(handles.max_num_iter,'string', '150'); set(handles.fcm_img_panel, 'visible', 'on'); else set(handles.num_of_clust, 'enable', 'off'); set(handles.exponent, 'enable', 'off'); set(handles.epsilon, 'enable', 'off'); set(handles.max_num_iter, 'enable', 'off'); end set(handles.final_img_panel, 'visible', 'off'); guidata(hObject, handles); * Nhập số lượng cụm: function num_of_clust_Callback(hObject, eventdata, handles) str = get(hObject,'string'); data = str2double(str); if isempty(data) || data < 1 || data > 15 || data ~= round(data) errordlg(strcat('The number of clusters must be a positive integer and should be less than 15'), 'Bad input'); set(hObject,'BackgroundColor','y'); else set(hObject,'BackgroundColor','w'); set(hObject,'UserData',data); end guidata(hObject, handles);
* Nhập tham số mờ:
function exponent_Callback(hObject, eventdata, handles) str = get(hObject,'string'); data = str2double(str); if isempty(data) || data < 1 errordlg('The weighting exponent must be a positive number', 'Bad input'); set(hObject,'BackgroundColor','y');
58
else set(hObject,'BackgroundColor','w'); set(hObject,'UserData',data); end guidata(hObject, handles);
* Nhập điều kiện dừng epsilon:
function epsilon_Callback(hObject, eventdata, handles) str = get(hObject,'string'); data = str2double(str); if isempty(data) || data < 0 errordlg('The minimum amount of improvement (eps) must be greater than 0. Example: 0.01, 0.006...', 'Bad input'); set(hObject,'BackgroundColor','y'); else set(hObject,'BackgroundColor','w'); set(hObject,'UserData',data); end guidata(hObject, handles);
* Nhập số vòng lặp tối đa:
function max_num_iter_Callback(hObject, eventdata, handles) str = get(hObject,'string'); data = str2double(str); if isempty(data) || data < 0 || data ~= round(data) errordlg('The maximum number of iterations must be a positive integer and greater than 0. Example: 50, 100, 200...', 'Bad input'); set(hObject,'BackgroundColor','y'); else set(hObject,'BackgroundColor','w'); set(hObject,'UserData',data); end
59
guidata(hObject, handles);
2. Thuật toán phân cụm mờ FCM:
function [center, U, obj_fcn] = FCM(data, cluster_n, options) global h; if nargin ~= 2 & nargin ~= 3, error('Too many or too few input arguments!'); end data_n = size(data, 1); in_n = size(data, 2); default_options = [2; 100; 1e-5; 1]; if nargin == 2, options = default_options; else if length(options) < 4, tmp = default_options; tmp(1:length(options)) = options; options = tmp; end nan_index = find(isnan(options)==1); options(nan_index) = default_options(nan_index); if options(1) <= 1, error('The exponent should be greater than 1!'); end end expo = options(1); max_iter = options(2); min_impro = options(3); display = options(4); obj_fcn = zeros(max_iter, 1); U = initfcm(cluster_n, data_n);
60
for i = 1:max_iter, [U, center, obj_fcn(i)] = stepfcm(data, U, cluster_n, expo); if display, fprintf('FCM:Iteration count = %d, obj. fcn = %f\n', i, obj_fcn(i)); end waitbar(i/max_iter, h); if i > 1, if abs(obj_fcn(i) - obj_fcn(i-1)) < min_impro, waitbar(1, h); set(h, 'visible', 'off'); break; end, end end set(h, 'visible', 'off'); iter_n = i; obj_fcn(iter_n+1:max_iter) = []; function U = initfcm(cluster_n, data_n) U = rand(cluster_n, data_n); col_sum = sum(U); U = U./col_sum(ones(cluster_n, 1), :); function [U_new, center, obj_fcn] = stepfcm(data, U, cluster_n, expo) mf = U.^expo; center = mf*data./((ones(size(data, 2), 1)*sum(mf'))'); dist = distfcm(center, data); obj_fcn = sum(sum((dist.^2).*mf)); tmp = dist.^(-2/(expo-1)); U_new = tmp./(ones(cluster_n, 1)*sum(tmp));
61
function out = distfcm(center, data) out = zeros(size(center, 1), size(data, 1)); for k = 1:size(center, 1), out(k, :) = sqrt(sum(((data-ones(size(data,1),1)*center(k,:)).^2)',1)); end
3. Phân cụm nửa giám sát mờ SSSFC:
function [V,U,J]=SSSFC(X,C,m,Eps,maxTest,U1) [N,r]=size(X); for i = 1:C for j = 1:r V(i,j) = min(X(:,j)) + rand() * (max(X(:,j)) - min(X(:,j))); end end minU1=min(U1); for i=1:C for k=1:N if U1(i,k)==minU1(k) U1(i,k)=0; end end end dem = 0; while (1>0) if m>1 for j = 1:C for i = 1:N tong1 = 0; for k = 1:C tong1=tong1+U1(k,i); end tong1=1-tong1;
62
d1 = 0; for k =1:r d1 = d1 + power(X(i,k)-V(j,k),2); end tong3=0; for k=1:C d2=0; for l=1:r d2 = d2 + power(X(i,l)-V(k,l),2); end tong3=tong3+power(1/d2,1/(m-1)); end U(j,i) = U1(j,i)+tong1*power(1/d1,1/(m-1))/tong3; end end else for j = 1:C for i = 1:N for k=1:C d2(k)=0; for l=1:r d2(k) = d2(k) + power(X(i,l)-V(k,l),2); end end mink=min(d2) if j==mink tong1=0; for k=1:C tong1=tong1+U1(k,i); end U(j,i)=U1(j,i)+1-tong1; else U(j,i)=U1(j,i); end end end end
63
for j = 1:C for i = 1:r tuso = 0; mauso = 0; for k = 1:N mauso = mauso + power(abs(U(j,k)-U1(j,k)),m); tuso = tuso + power(abs(U(j,k)-U1(j,k)),m) * X(k,i); end if (mauso ~= 0) W(j,i) = tuso / mauso; else W(j,i) = 0; end end end saiso = 0; for i = 1:C for j = 1:r saiso = saiso + power(W(i,j)-V(i,j),2); end end saiso = sqrt(saiso); if (saiso <= 0.00000001) break; else for i = 1:C for j = 1:r V(i,j)= W(i,j); end end end if(dem>=maxTest) break; end dem = dem + 1; end
64
J=0; for k=1:N tong1=0; for j=1:C tong2=0; for i=1: r tong2=tong2+power(X(k,i)-V(j,i),2); end tong1=tong1+power(tong2,1-m); end J=J+power(tong1,1-m); end MaxU=max(U); for k=1:N for j=1:C if U(j,k)==MaxU(k) cum(k)=j; end end end end
4. Phân cụm mờ SSFCDF
function [V,U,J,X]=SSFCDF(X,C,m,Eps,maxTest,U1) [N,r]=size(X); for i = 1:C for j = 1:r V(i,j) = min(X(:,j)) + rand() * (max(X(:,j)) - min(X(:,j))); end end for i = 1:N for j = 1:C Tu = 0; for k = 1:r Tu = Tu + power(X(i,k)-V(j,k),2);
65
end Tu = sqrt(Tu); tong = 0; for l =1:C Mau = 0; for k = 1:r Mau = Mau + power(X(i,k)-V(l,k),2); end Mau = sqrt(Mau); tong = tong + power(Tu/Mau, 2/(m-1)); end U(j,i) = 1/tong; end end minU1=min(U1); for i=1:C for k=1:N if U1(i,k)==minU1(k) U1(i,k)=0; end end end dem=0; while (1>0) for j = 1:C for i = 1:r tuso = 0; mauso = 0; for k = 1:N mauso = mauso + power(abs(U(j,k)-U1(j,k)),m)+power(U(j,k),m); tuso = tuso + (power(abs(U(j,k)-U1(j,k)),m)+power(U(j,k),m)) * X(k,i); end if (mauso ~= 0) V(j,i) = tuso / mauso; else V(j,i) = 0;
66
end
end
end
a=5;
b=5;
for i=1:N
y=floor(i/a);
z=mod(i,a);
n1=1;
ok=true;
beta=1;
if (y>1)&(y
67
for k=1:N tu=0; mau=0; y=floor(k/a); z=mod(k,a); for l=y-floor(N1(k)/2):y+floor(N1(k)/2) for j=z-floor(N1(k)/2):z+floor(N1(k)/2) d=0; c=l*a+j; if (c>0)&(c<=N)&(l~=y)&(j~=z) for s=1:r d=d+power(X(k,s)-X(c,s),2); end if d~=0 tu=tu+U(i,c)*power(sqrt(d),-1); mau=mau+power(sqrt(d),-1); end end end end if mau~=0 SI(i,k)=tu/mau; else SI(i,k)=U(i,k); end d1=0; for s=1:r d1=d1+power(X(k,s)-V(i,s),2); end R1(i,k)=d1*(1-alpha1*exp(-SI(i,k))); end end for i=1:N tong1=0; tong2=0; for j=1:C d=0; for k=1:r d=d+power(X(i,k)-V(j,k),2); end tong1=tong1+(U1(j,i)*d)/(2*d+power(R1(j,i),2));
68
tong2=tong2+1/(2*(2*d+power(R1(j,i),2))); end lamda(i)=(tong1-1)/tong2; end for j=1:C for i=1:N d=0; for k=1:r d=d+power(X(i,k)-V(j,k),2); end UT(j,i)=(-lamda(i)+2*U1(j,i)*d)/(2*(2*d+power(R1(j,i),2))); end end saiso = 0; for i = 1:C for j = 1:N saiso = saiso + power(UT(i,j)-U(i,j),2); end end saiso = sqrt(saiso); if (saiso <= 0.01) break; else for i = 1:C for j = 1:N U(i,j)= UT(i,j); end end end if(dem>=2) break; end dem = dem + 1;
69
US=sum(U); end dem sum(US) ; J=0; tong1=0; tong2=0; tong3=0; tong4=0; end
* Xem kết quả phân cụm
function btn_ok_result_Callback(hObject, eventdata, handles) selected_index = get(handles.result_popupmenu, 'Value'); list = get(handles.result_popupmenu, 'String'); selected_string = list {selected_index}; switch selected_string case 'Gia tri ham muc tieu' msgbox(sprintf('Gia tri cua ham muc tieu: %.6f', handles.obj_fcn), 'Objective function'); case 'Tam' str = ''; for i = 1:1:get(handles.num_of_clust,'UserData') str = strcat(str, sprintf('\n\nTam cum %2d: %20f %20f %20f', i, handles.center(i, 1), handles.center(i, 2), handles.center(i, 3))); end msgbox(str, 'Tam cua cum'); case 'Ma tran do thuoc' f = figure('Name', 'Ma tran do thuoc', 'NumberTitle','off', 'Position',[300 300 500 250]); t = uitable(f); set(t, 'Data', handles.U, 'Position',[10 10 480 230]); case 'Thoi gian' msgbox(sprintf('Thoi gian: %f', handles.elapsed_time), 'Time'); case 'DB' DB_value = ValidityIndex('DB', handles.data,
70
get(handles.num_of_clust,'UserData'), handles.center, handles.U); msgbox(sprintf('Gia tri do do DB: %f', DB_value), 'Gia tri do do DB'); case 'IFV' IFV_value = ValidityIndex('IFV', handles.data, get(handles.num_of_clust,'UserData'), handles.center, handles.U); msgbox(sprintf('Gia tri do do IFV: %f', IFV_value), 'Gia tri do do IFV'); case 'PBM' PBM_value = ValidityIndex('PBM', handles.data, get(handles.num_of_clust,'UserData'), handles.center, handles.U); msgbox(sprintf('Gia tri do do PBM: %f', PBM_value), 'Gia tri do do PBM'); case 'SSWC' SWC_value = ValidityIndex('SWC', handles.data, get(handles.num_of_clust,'UserData'), handles.center, handles.U); msgbox(sprintf('Gia tri do do SSWC: %f', SWC_value), 'Gia tri do do SSWC'); end
5. Các độ đo đánh giá kết quả phân cụm:
function value = ValidityIndex(indexName, data, numClust, center, U) switch indexName case 'DB' value = DB(data, numClust, center, U); case 'IFV' value = IFV(data, numClust, center, U); case 'PBM' value = PBM(data, numClust, center, U); case 'SWC' value = SWC(data, numClust, U); otherwise value = nan; end
* Độ đo DB:
function DB_value = DB(data, numClust, center, U) maxU = max(U); S = zeros(1, numClust); for i = 1 : numClust
71
index = find(U(i,:) == maxU); for j = index S(i) = S(i) + norm(data(j, :) - center(i, :)) ^ 2; end S(i) = sqrt(S(i)/size(index, 2)); end DB_value = 0; for i = 1:numClust maxSM = 0; for j = 1:numClust if j ~= i temp = (S(i) + S(j))/norm(center(i, :) - center(j, :)); maxSM = max(maxSM, temp); end end DB_value = DB_value + maxSM; end DB_value = DB_value/numClust;
* Độ đo IFV:
function IFV_value = IFV(data, numClust, center, U) sigmaD = 0; sum = 0; sizeData = size(data,1); for i = 1:numClust tg1 = 0; tg2 = 0; for j = 1:sizeData tg1 = tg1 + log(U(i, j))/log(2); tg2 = tg2 + U(i, j)^2; sigmaD = sigmaD + norm(data(j, :) - center(i, :))^2; end tg = (log(numClust)/log(2) - tg1/sizeData)^2; tg2 = tg2/sizeData;
72
sum = sum + tg * tg2; end sigmaD = sigmaD/(numClust * sizeData); calcSDmax = 0; for i = 1:numClust-1 for j = i+1:numClust calcSDmax = max(calcSDmax, norm(center(i, :) - center(j, :))^2); end end IFV_value = (sum * calcSDmax) / (sigmaD * numClust);
* Độ đo PBM:
function t = calcSumDistDataPoint2X(data, X) temp = data - X(ones(size(data, 1), 1), :); temp = temp.^2; temp = sum(temp, 2); temp = sqrt(temp); t = sum(temp); function PBM_value = PBM(data, numClust, center, U) E_1 = calcSumDistDataPoint2X(data, mean(data)); maxU = max(U); E_k = 0; for i = 1 : numClust index = find(U(i,:) == maxU); clustData = data(index, :); E_k = E_k + calcSumDistDataPoint2X(clustData, center(i, :)); end D_k = 0; for i = 1:numClust-1 for j = i+1:numClust D_k = max(D_k, norm(center(i, :) - center(j, :))); end
73
end PBM_value = (E_1 * D_k / (numClust * E_k)) ^ 2;
* Độ đo SWC:
function SWC_value = SWC(data, numClust, U) maxU = max(U); SWC_value = 0; for i = 1 : numClust index = find(U(i,:) == maxU); if size(index, 2) == 1 continue; end clustData = data(index, :); for j = index a_i_j = calcSumDistDataPoint2X(clustData, data(j, :)) / size(index, 2); b_i_j = 10^6; for k = 1 : numClust if k ~= i index_k = find(U(k,:) == maxU); clustData_k = data(index_k, :); d_k_j = calcSumDistDataPoint2X(clustData_k, data(j, :)) / size(index_k, 2); b_i_j = min(b_i_j, d_k_j); end end SWC_value = SWC_value + (b_i_j - a_i_j) / max(a_i_j, b_i_j); end end SWC_value = SWC_value / size(data, 1);
74
