MÔ HÌNH PHÂN LỚP FCM TRONG PHÂN ĐOẠN ẢNH VÀ THUẬT TOÁN DCA

MÔ HÌNH PHÂN LỚP FCM TRONG PHÂN ĐOẠN ẢNH VÀ THUẬT TOÁN DCA. TS. NGUYỄN TRỌNG PHÚC Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Giao thông Vận tải Tóm tắt: Trong bài báo này, chúng tôi giới thiệu một thuật toán nhanh và mềm dẻo trong bài toán phân đoạn ảnh thông qua mô hình phân lớp Fuzzy C-Means. Cách tiếp cận của chúng tôi dựa trên lý thuyết DC (hiệu hai hàm lồi) với thuật toán DCA tương ứng. DC và thuật toán DCA đã xuất hiện từ năm 1986 được phát triển...
Nội dung trích xuất từ tài liệu:
MÔ HÌNH PHÂN LỚP FCM TRONG PHÂN ĐOẠN ẢNH VÀ THUẬT TOÁN DCA MÔ HÌNH PHÂN LỚP FCM TRONG PHÂN ĐOẠN ẢNH VÀ THUẬT TOÁN DCA TS. NGUYỄN TRỌNG PHÚC Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Trường Đại học Giao thông Vận tải Tóm tắt: Trong bài báo này, chúng tôi giới thiệu một thuật toán nhanh và mềm dẻo trong bài toán phân đoạn ảnh thông qua mô hình phân lớp Fuzzy C-Means. Cách tiếp cận của chúng tôi dựa trên lý thuyết DC (hiệu hai hàm lồi) với thuật toán DCA tương ứng. DC và thuật toán DCA đã xuất hiện từ năm 1986 được phát triển đến nay và được áp dụng trong nhiều lĩnh vực khoa học liên quan đến các bài toán tối ưu như trong Machine Learning… Với một cách tiếp cận mềm dẻo, mô hình FCM ban đầu của bài toán được biến đổi thành mô hình mới mà DC có thể áp dụng được với thuật toán DCA đơn giản tương ứng. Để cải thiện tốc độ của thuật toán chúng tôi kết hợp thuật toán DCA và thuật toán FCM theo các cách khác nhau. Hơn nữa, chúng tôi xét đến mối quan hệ giữa các điểm ảnh trong không gian để đưa thêm thông tin vào trong mô hình bài toán ban đầu nhằm xử lý các ảnh trong thực tế, các ảnh nhiễu. Thông qua các kết quả thực tế, chúng tôi thấy được ưu điểm của phương pháp tiếp cận trong việc tăng tốc độ, chất lượng ảnh phân đoạn với các ảnh khác nhau, đặc biệt là ảnh trong y học. CNTT- CB Summary: We present a fast and robust algorithm for image segmentation problems via Fuzzy C-Means (FCM) clustering model. Our approach is based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) that have been successfully applied in a lot of various fields of Applied Sciences, including Machine Learning. In an elegant way, the FCM model is reformulated as a DC program for which a very simple DCA scheme is investigated. For accelerating the DCA, an alternative FCM-DCA procedure is developed. Moreover, in the case of noisy images, we propose a new model that incorporates spatial information into the membership function for clustering. Experimental results on noisy images have illustrated the effectiveness of the proposed algorithm and its superiority with respect to the standard FCM algorithm in both running-time and quality of solutions. I. GIỚI THIỆU CHUNG Phân đoạn ảnh giữ một vai trò rất quan trọng trong nhiều ứng dụng như các bài toán nhận dạng hay các bài toán xử lý ảnh trong y học ([2]; [3]). Phân đoạn ảnh là một bước cơ bản để có thể thực hiện việc phân tích các ảnh thu được. Một cách tổng quát, phân đoạn ảnh được định nghĩa như việc chia hình ảnh thành các đối tượng độc lập với nhau dựa trên các đặc tính của ảnh như mức xám hay kết cấu của ảnh. Có rất nhiều các thuật toán phân đoạn ảnh được đề xuất, chúng ta có thể chia ra làm 4 loại sau đây ([9]): - Phương pháp cơ bản: phân ngưỡng, phát triển vùng, tách biên… - Phương pháp thống kê: Maximum Likelihood Classifier (MLC)… - Phương pháp dựa trên mạng Neural. - Phương pháp dựa trên logic mờ (Fuzzy Clustering). Bài báo này đề cập đến thuật toán phân đoạn ảnh dựa trên mô hình Fuzzy C-Means (FCM) với việc áp dụng lý thuyết DC và thuật toán DCA tương ứng để giải quyết bài toán. Mục đích của chúng tôi là đưa ra một thuật toán nhanh và mềm dẻo để giải quyết bài toán bởi vì mô hình phân lớp trong bài toán phân đoạn ảnh là một mô hình lớn, nhiều hướng và cần có một thuật toán hiệu quả. Hơn nữa, với việc xem xét mối quan hệ liên thông giữa các điểm ảnh, chúng tôi đã áp dụng thuật toán để thực hiện phân đoạn các ảnh nhiễu. Bài báo bao gồm 4 chương. Chương 1 giới thiệu chung về bài toán và các tiếp cận thực tế. Chương 2 trình bày về mô hình FCM cũng như mô hình FCM khi quan tâm đến tính liên thông của các điểm ảnh. Chương 3 giới thiệu về cách phân rã mô hình theo DC và các thuật toán DCA kết hợp FCM. Chương cuối đề cập đến các kết quả thu nhận được khi thực hiện các thuật toán trên các ảnh thực tiễn và các nhận xét về các thuật toán. II. MÔ HÌNH FCM CỦA BÀI TOÁN 2.1. Mô hình FCM của bài toán Phân lớp Fuzzy C-Means (CFM) là một trong những phương pháp được ứng dụng rộng rãi CNTT-CB nhất trong Logic mờ. Được đưa ra bởi Bezdek ([2]) bởi sự mở rộng của thuật toán Dunn năm 1973, FCM là một trong những thuật toán hiệu quả trong bài toán phân lớp và đặc biệt là trong các bài toán phân đoạn ảnh. Với cách tiếp cận này, mỗi hình ảnh với nhiều đặc trưng sẽ được phân lớp thành các nhóm mà tại đó các điểm ảnh có cùng đặc trưng với nhau. Như vậy, bài toán phân lớp sẽ dẫn đến việc giải bài toán xác định giá trị min của tổng khoảng cách của các điểm ảnh đến tâm của mỗi phân đoạn trên miền đặc trưng của ảnh. Giả sử rằng X:= {x1, x2, ..., xn} định nghĩa tập các điểm ảnh của một ảnh cần phải phân thành c (0 trong đó ||.|| chính là giá trị chuẩn Euclidean trên không gian tương ứng và ma trận Vcd biểu diễn tập hợp các điểm tâm của các phân lớp trong không gian này còn tham số m được gọi là tham số mờ của các tập dữ liệu. Khi đó, mô hình của bài toán phân đoạn ảnh được biểu diễn: ⎧ n c ∑∑ 2 m ...