Một giải pháp phân vùng ảnh viễn thám kích thước lớn dựa trên Logic mờ - Nguyễn Tu Trung

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 34, 12- 2014 59 Một giảI pháp Phân vùng ảnh viễn thám kích thƯớc lớn dựa trên logic mờ NGUYễN TU TRUNG*, vũ văn thỏa** Tóm tắt: Phân vùng ảnh viễn thám là vấn đề được các nhà nghiên cứu viễn thám quan tâm. ảnh viễn thám có thể có nhiều kênh, độ phân giải rất cao. Có nhiều kĩ thuật phân vùng khác nhau như K-Means, C-Means, Watersed, ... Trong đó, Fuzzy C-Means (FCM) được đánh giá rất cao về khả năng phân vùng bằng việc sử dụng logic mờ. Tuy nhiên, phương pháp này gặp vấn đề khi phân vùng ảnh có kích thước lớn như ảnh viễn thám. Bài báo này trình bày một kĩ thuật cải tiến thuật toán FCM để có thể thực hiện với ảnh viễn thám kích thước lớn. Từ khóa: Phân vùng ảnh, ảnh viễn thám, C-Means, Fuzzy. 1. Mở đầu Xử lý ảnh viễn thám nói chung và phân vùng ảnh (hay phân cụm) viễn thám nói riêng là vấn đề được nghiên cứu từ lâu và hiện tại vẫn đang được quan tâm. Phân cụm là một quy trình dùng để trích chọn những nét chính của các đối tượng nền bởi việc định nghĩa các vùng tương ứng. Nhiệm vụ của chức năng phân vùng ảnh là từ ảnh đa ban đầu, tiến hành xử lý và phân chia thành các vùng, các cụm khác nhau. Hiện nay, có nhiều phương pháp phân vùng khác nhau như: Các phương pháp hình thái, Các phương pháp họ K-Means, Mô hình pha trộn Gaussian có giới hạn (FGMM), Tách và hợp, Các mô hình Markov, ... Hầu hết các phương pháp chỉ sử dụng cường độ của mỗi điểm ảnh để định nghĩa các vùng, nhưng đa ra các phân đoạn rất hỗn tạp, cụ thể với các ảnh đa phổ có độ phân giải cao. Hiện nay, một số thuật toán bao gồm thông tin ngữ cảnh trong quy trình để giảm bớt tính hỗn tạp của các phân đoạn. Trong đó, một số thông tin ngữ cảnh của các phân đoạn này được trích chọn từ ảnh cũng được sử dụng. Trong [1, 2], các tác giả đã đề xuất kĩ thuật phân cụm kết hợp thuật toán Watershed và biến đổi Wavelet để phân vùng ảnh. Fuzzy C-Means (FCM) được đánh giá rất cao về khả năng phân vùng bằng việc sử dụng logic mờ. Trong [3], Chen và cộng sự đã kết hợp giữa thuật toán phân cụm mờ và một biểu thức điều chỉnh mức xám để tăng cường độ tương phản của ảnh viễn thám. Trong [4], các tác giả cũng kết hợp giữa thuật toán phân cụm mờ và các biểu thức điều chỉnh mức xám khác để tăng cường độ ảnh y tế. Tuy nhiên, phương pháp này gặp vấn đề khi phân vùng ảnh có kích thước lớn như ảnh viễn thám. Một giải pháp phân vùng ảnh viễn thám được đề xuất nhằm khắc phục hạn chế này được trình bày sau đây. 2. thuật toán phân vụm mờ gốc Phân cụm C-Means mờ [5] là thuật toán được dùng rộng rãi của phân lớp mờ. Trong khi xem xét logic tập mờ, thuật toán được phát triển dựa trên phân cụm K-Means. Trong thuật toán này, mỗi điểm ảnh không về duy nhất cụm nào và được biểu diễn bởi nhiều thành viên của mỗi cụm. Thuật toán phân cụm được thực hiện với sự tối ưu lặp của việc cực tiểu hàm mục tiêu mờ ( ) được định nghĩa như đẳng thức 1 ([5]). Kỹ thuật điện tử & Khoa học máy tính N. T. Trung, V. V. Thoả, “Một giải pháp phân vùng ảnh viễn thám dựa trên logic mờ.” 60 (1) trong đó, là số cụm, là số pixel của ảnh, là giá trị thành viên của pixel thứ và trung tâm cụm thứ , là trọng số mũ, tham số mờ, là vector thứ , là Vector trung tâm của cụm thứ , là khoảng cách giữa và . Thành viên ) được ước lượng với khoảng cách giữa điểm ảnh thứ và tâm cụm thứ , và bị ràng buộc như sau: (2) Trung tâm cụm và giá trị có thể được tính theo công thức sau: (3) (4) Do đó, có thể được cực tiểu bởi việc lặp thông qua đẳng thức (3) và (4). Bước đầu tiên của việc lặp là khởi tạo số cụm cố định, tham số mờ , một ngưỡng hội tụ , sau đó tính toán và sử dụng đẳng thức (3) và (4) tương ứng. Việc lặp kết thúc khi sự thay đổi trong giữa hai lần lặp nhỏ hơn . Cuối cùng, mỗi điểm ảnh được phân lớp vào một sự kết hợp các thành viên của các cụm. 3. thuật toán phân cụm mờ cảI tiến 3.1. Nhược điểm của FCM với ảnh viễn thám kích thước lớn Thuật toán phân cụm mờ [5] nảy sinh vấn đề khi gặp ảnh có kích thước rất lớn mà cụ thể ở đây là ảnh viễn thám độ phân giải cao. Vấn đề nảy sinh từ ma trận độ thuộc . Theo công thức (4), kích thước của được tính nh sau: (Byte) (5) trong đó, là số cụm, là số pixel (kích thước) của ảnh. Giả sử ta có một ảnh kích thước và muốn phân nó thành 20 cụm. Khi đó, là . Ma trận độ thuộc được lưu trong RAM. Như vậy, chỉ cần có RAM 1GB thì có thể lưu ma trận độ thuộc trong trường hợp này. Tuy nhiên, nếu chúng ta muốn phân thành 40 cụm thì là 128 . Điều này nghĩa là nếu chỉ có RAM 1GB thì không đủ để chứa các phần tử của ma trận độ thuộc. Và để thuật toán FCM có thể thực hiện ta buộc phải tăng RAM. Nếu ảnh có kích thớc , số lớp = 20, là . Chúng ta thấy, với ảnh kích thước và số lớp như trên thì kể cả bộ nhớ RAM lớn nhất hiện nay cho máy tính cá nhân cũng không thể chứa dẫn tới FCM không thể thực thi nếu ma trận độ thuộc được lưu trên RAM. Chúng ta có thể nghĩ đến việc dùng đĩa cứng để lưu ma trận này thay vì dung RAM. Tuy nhiên, khi đó ngay cả với ảnh màu thông thường thì thời gian thực hiện của FCM là rất chậm. Với ảnh viễn thám, thời gian này có thể lên tới đơn vị ngày. Như vậy là không hiệu quả. Tất cả điều này đã giải thích nguyên nhân vì sao FCM [5] gặp vấn đề với ảnh kích thước rất lớn mà cụ thể là ảnh viễn thám. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 34, 12- 2014 61 3.2. Phân vùng ảnh viễn thám kích thước lớn với lsiFCM Phần này đề xuất thuật toán phân cụm mờ ảnh viễn thám kích thước lớn tạm gọi là lsiFCM (large size image Fuzzy cMeans). Sơ đồ thuật toán được minh hoạ trong hình 1. ảnh 1. Lưu đồ thuật toán lsiFCM. B1: Chia ô Chúng ta có thể biểu diễn lại ảnh theo khía cạnh tập hợp. Biểu diễn ban đầu của ảnh theo tập các pixel. Giả sử ảnh có kích thớc . Khi đó ta có: (6) ảnh gốc được chia thành ô (p ô theo chiều ngang, ô theo chiều dọc), mỗi ô có kích thước không quá 512 512 ( ) pixel để đảm bảo thủ tục FCM có thể thực thi. Theo chiều ngang, 2 ô liền kề có phần xếp chồng bằng một nửa kích thước mỗi ô . Theo chiều dọc, 2 ô liền kề có phần xếp chồng bằng một nửa kích thước mỗi ô. Khi đó, ta có biểu diễn mới của ảnh như sau: (7) trong đó, (8) Từ đây, chúng ta được tập các ô. Viết lại (7) theo dạng một chiều các ô ta được công thức biểu diễn ảnh nh sau: (9) trong đó, tương đương với trong (7) và . Kỹ thuật điện tử & Khoa học máy tính N. T. Trung, V. V. Thoả, “Một giải pháp phân vùng ảnh viễn thám dựa trên logic mờ.” 62 B2: Phân cụm FCM các ô Tiến hành phân cụm mỗi ô với thuật toán FCM. Sau khi đã phân cụm tất cả các ô, ta được tập tâm cụm như sau: 10) B3: Phân cụm FCM tập tâm cụm Sau khi thu được tập các tâm cụm của các ô, tiếp tục thực hiện thuật toán phân cụm FCM trên tập các tâm cụm này. Ta thu được tập tâm cụm với tâm cụm cuối cùng. B4: Tổng hợp Từ tâm cụm thu được trong B3, tính lại giá trị thành viên của từng điểm trong ảnh ảnh đầu vào với mỗi tâm cụm. Từ đó, tính ra tập các tâm cuối cùng. 4. kết quả THựC NGHIệM Kết quả hai thử nghiệm thuật toán đề xuất lsiFCM và so sánh kết quả với thuật toán KMeans đã được sử dụng phổ biến cho phân vùng ảnh viễn thám. Trong đó, thử nghiệm 1, ảnh gốc là ảnh vệ tinh Quickbird có kích thước (điểm ảnh). Với thử nghiệm 2, ảnh gốc là ảnh vệ tinh LANSAT về huyện Đà Bắc thuộc tỉnh Hoà Bình có kích thước . Bảng 1: ảnh đầu vào và kết quả phân cụm. Mẫu ảnh gốc KMeans lsiFCM Mẫu 1 Mẫu 2 Bảng 1 mô tả ảnh gốc và ảnh sau phân cụm của thuật toán KMeans và lsiFCM của các mẫu trong thử nghiệm 1 và 2. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN Quân sự, Số 34, 12- 2014 63 Bảng 2. Thống kê các cụm sau phân loại. Thuật toán Số cụm Cụm số Tâm cụm Số điểm KMeans 5 1 22, 27, 22 451077 2 44, 50, 43 905929 3 74, 78, 66 789952 4 107, 109, 90 1299396 5 139, 140, 118 800926 lsiFCM 5 1 75, 79, 66 825813 2 137, 139, 117 826079 3 108, 110, 91 1259879 4 21, 27, 21 375444 5 43, 49, 42 960070 Bảng 2 và 3 thống kê kết quả phân cụm của thuật toán KMeans và lsiFCM của các mẫu trong thử nghiệm 1 và 2. Bảng 3. Thống kê các cụm sau phân loại. Thuật toán Số cụm Cụm số Tâm cụm Số điểm KMeans 5 1 0, 0, 0 1287721 2 43, 76, 62 320749 3 100, 125, 118 114995 4 79, 70, 50 321694 5 225, 220, 192 82309 lsiFCM 5 1 99, 124, 117 1341432 2 76, 71, 51 1549810 3 232, 228, 200 1300001 4 15, 17, 15 1287112 5 45, 74, 60 299682 Với kết quả đạt được trong các thử nghiệm 1 và 2, chúng ta thấy với giải pháp đề xuất cho hiệu quả phân cụm tốt với ảnh viễn thám và đã giải quyết được vấn đề kích lớn ảnh viễn thám đầu vào lớn cho thuật toán phân cụm mờ. 5. kết luận Nội dung bài báo đã đề xuất một thuật toán phân vùng ảnh viễn thám. Đầu tiên, ảnh được chia thành nhiều ô có kích thước bằng nhau. Sau đó, tiến hành phân cụm mỗi ô với thuật toán FCM để thu được tập các tâm cụm. Sau khi tất cả các ô đều được phân cụm, ta có tập các tâm cụm của các ô này. Tiếp tục sử dụng thuật toán FCM để phân cụm tập các tâm này. Kết quả thu được tập các tâm mới. Quá trình tổng hợp là việc tính lại giá trị thành viên từng điểm ảnh và tập các tâm cuối cùng. Kỹ thuật điện tử & Khoa học máy tính N. T. Trung, V. V. Thoả, “Một giải pháp phân vùng ảnh viễn thám dựa trên logic mờ.” 64 Tài liệu tham khảo [1] C.R.Jung, J.Scharcanski. “Robust Watershed segmentation using the wavelet transforms,”Proceedings of the XV Brazilian Symposium on Computer Graphics and Image Processing, (SIBGRAPI’02) 1530-1834/02,2000,IEEE. [2] Claudio Rosito Jung. “Multiscale Image Segmentation using Wavelets and Watersheds,” Proceedings of the XVI Brazilian Symposium on Computer Graphics and Image Processing. (SIBGRAPI’02) 1530-1834/03, 2003, IEEE. [3] Chi-Farn Chen *, Hung-Yu Chang, Li-Yu Chang, A FUZZY-BASED METHOD FOR REMOTE SENSING IMAGE CONTRAST ENHANCEMENT, The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B2. Beijing 2008. [4] A.E. Hasanien, A. Badr, “A Comparative Study on Digital Mamography Enhancement Algorithms Based on Fuzzy Theory,” Studies in Informatics and Control, Vol.12, No.1, March 2003. [5] Bezdek J.C., R. Ehrlich, W.Full, “FCM: The fuzzy C-Means clustering algorithm,” Computers & Geosciences Vol. 10, No. 2-3, (1984), pp. 191- 203. abstract large size remote sensing image Clustering based on fuzzy logic Remote sensing image clustering is the issue that is interested by remote sensing researchers. Remote sensing image can have multi-bands and high resolution. There are multi-algorimths as K-Means, C-Means, Watersed, ... Therein, Fuzzy C-Means (FCM) is appraised very hight because it can clustering by using fuzzy logic. However, this method have problem when clustering images with large size as remote sensing image. This paper present a technique which improves the algorimth FCM to execute remote sensing image with large. Keywords: Image clustering, Clustering. Nhận bài ngày 18 tháng 09 năm 2014 Hoàn thiện ngày 22 tháng 10 năm 2014 Chấp nhận đăng ngày 05 tháng 12 năm 2014 Địa chỉ: * Viện Công nghệ thông tin, Viện Hàn Lâm Khoa học và Công nghệ Việt Nam; ** Học viện Bưu chính Viễn thông.