Ứng dụng thuật toán phân cụm trong xây dựng ảnh chỉ số

- Kiều Huy Thắng ỨNG DỤNG THUẬT TOÁN PHÂN CỤM TRONG XÂY DỰNG ẢNH CHỈ SỐ LUẬN VĂN THẠC SỸ KHOA HỌC Ngành: Toán Công nghệ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.
- 6 CHƯƠNG I TỔNG QUAN VỀ ẢNH SỐ.
- 7 2 Các định dạng ảnh cơ bản trong ảnh số.
- Dữ liệu nén.
- Định dạng JPEG.
- Định dạng RAW.
- Định dạng PNG.
- Định dạng TIFF.
- Định dạng PSD.
- Các thuật toán về lập bảng chỉ số.
- Các thuật toán về phân cụm màu cho bài toán rút gọn màu.
- 27 * Thuật toán K-mean Thuật toán C-mean .
- Các ứng dụng của phân cụm màu.
- 49 CHƯƠNG III CHƯƠNG TRÌNH VÀ CÁC KẾT QUẢ ĐẠT ĐƯỢC………….51 1.
- Sơ đồ thuật toán.
- Giao diện của các chương trình.
- 62 KẾT LUẬN TÀI LIỆU THAM KHẢO TÓM TẮT LỜI MỞ ĐẦU Việc tạo ra hình ảnh trong lịch sử loài người khởi đầu bằng việc khắc các hình trên đá, sau đó là vẽ trên giấy, lụa, sơn mài, sử dụng máy chụp hình… Khi máy tính và kỹ thuật số ra đời cùng với những thiết bị đồ họa chuyên dụng khác, con người có thêm một công cụ mới để tạo lập, lưu trữ và xử lý dữ liệu ảnh.
- Việc xử lý ảnh số là cần thiết để đạt được một bức ảnh nhằm phục vụ một mục đích nào đó của người sử dụng.
- Xử lý ảnh số là một lĩnh vực đang được quan tâm và đã trở thành môn học chuyên ngành của sinh viên hệ kỹ sư, hệ cử nhân ngành Công Nghệ Thông Tin, cũng như một số ngành kỹ thuật khác trong các trường Đại học kỹ thuật.
- Xử lý ảnh có liên quan đến nhiều ngành khác như: hệ thống tin học, lý thuyết thông tin, thông tin liên lạc, trí tuệ nhân tạo, nhận dạng, v.v.
- Phân cụm ảnh là một trong các quá trình xử lý ảnh.
- Phân cụm ảnh được ứng dụng nhiều trong thực tế: để xử lý ảnh, rút gọn màu, xác định các đường viền trên ảnh…qua đó lại tiếp tục ứng dụng vào các mục đích khác như: tạo màu trong suốt, giấu tin trong file ảnh, áp dụng chuẩn đoán hình ảnh trong y học, dự đoán về thị trường, nén ảnh (đây là một trong những ứng dụng quan trọng nhất của quá trình phân cụm.
- Có nhiều thuật toán cho quá trình phân cụm và các thuật toán này đóng vai trò rất quan trọng đối với việc phân cụm Với các yêu cầu đó, luận văn sẽ đưa ra một chương trình về phân cụm ảnh sử dụng ngôn ngữ Java.
- Chương trình nhằm đạt được một số yêu cầu: đọc 4ảnh đầu vào, đưa ra một số cụm cho trước, tìm các điểm màu có cùng chỉ số đưa vào các cụm… Các mục tiêu chính của luận văn là.
- Tìm hiểu lý thuyết về ảnh kỹ thuật số, cách biểu diễn ảnh số trong máy tính • Tìm hiểu lý thuyết về phân cụm, tìm hiểu các thuật toán phân cụm ứng dụng trong rút gọn ảnh màu • Viết chương trình dựa trên các thuật toán cụ thể Kết cấu luận văn gồm ba phần chính.
- Chương I: Tổng quan về ảnh số Trong phần này, luận văn sẽ nêu ra các khái niệm về ảnh màu, ảnh kỹ thuật số, pixel, các dải màu.
- Chương II: Lý thuyết về phân cụm ảnh và ứng dụng Trong chương này, các khái niệm về phân cụm, các thuật toán phân cụm, các dạng phân cụm…sẽ được nêu ra - Chương III: Xây dựng chương trình phân cụm Chương này sẽ trình bày sơ qua về chương trình phân cụm được viết bằng ngôn ngữ Java dựa trên hai thuật toán cụ thể.
- Đã có nhiều chương trình, bài viết về phân cụm ảnh với nhiều thuật toán khác nhau.
- Tuy nhiên, việc tiếp tục thực hiện các chương trình phân cụm màu sẽ mang lại nhiều ưu điểm cũng như sự khác biệt với các chương trình đã có như.
- Vấn đề bản quyền: việc chủ động trong quá trình phân cụm ảnh sẽ giúp người sử dụng chủ động hơn trong việc áp dụng vào các ứng dụng khác + Vấn đề công nghệ: mỗi chương trình viết ra đều có những ưu điểm riêng biệt thích hợp với từng người sử dụng, theo từng ngôn ngữ lập trình cụ thể + Khả năng đánh giá: các chương trình được viết ra càng tăng thêm khả năng đánh giá về các thuật toán phân cụm.
- Mỗi thuật toán đều có một ưu điểm riêng.
- Có thuật toán chạy với tốc độ nhanh nhưng chất lượng lại không được tốt.
- Có thuật toán chạy với tốc độ chậm nhưng cho kết quả cao hơn.
- 6LỜI CẢM ƠN Tôi muốn gửi lời cảm ơn sâu sắc nhất đền thầy của tôi: PGS.TS Phan Trung Huy, người đã tận tình hướng dẫn tôi trong suốt quá trình làm bài luận văn này.
- Tôi xin chân thành cảm ơn các thầy, cô trong khoa Toán Tin Ứng Dụng Trường Đại học Bách Khoa Hà Nội đã tận tình dạy dỗ, truyền đạt kiến thức để tôi có thể hiểu được các kiến thức khoa học.
- Xin cảm ơn tất cả các bạn bè, đồng nghiệp đã giúp đỡ tôi trong suốt quá trình làm bài luận văn này.
- 7 CHƯƠNG I TỔNG QUAN VỀ ẢNH SỐ 1.
- Ảnh thực chất là một tập hợp các điểm màu liên tiếp xếp liền nhau, hoặc một tập hợp các đường hình học nhằm miêu tả một phong cảnh, sự vật hay chủ đề nào đó.
- Trên máy tính, ảnh được lưu trên các file nhị phân, theo các định dạng do nhà sản xuất quy định.
- Do vậy, để lưu trữ ảnh màu, người ta có thể lưu trữ từng mặt màu riêng biệt, mỗi màu lưu trữ như một ảnh đa cấp xám.
- Tín hiệu số và biểu diễn ảnh số * Pixel Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng.
- Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hoá ảnh.
- Trong quá trình số hoá, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hoá về không gian) và lượng hoá 8thành phần giá trị (rời rác hoá biên độ giá trị) mà bằng mắt thường không phân biệt được hai mức kề nhau.
- Trong quá trình này, người ta sử dụng khái niệm Picture Element mà quen gọi là Pixel- phần tử ảnh.
- Như vậy, ảnh là một tập hợp các điểm ảnh.
- Nhìn chung có thể xem một hàm hai biến chứa các thông tin như biểu diễn của một ảnh.
- Các tín hiệu liên tục theo thời gian qua quá trình số hóa ta thu được tín hiệu rời rạc (tín hiệu số).
- Ảnh số chính là ảnh xử lý bằng máy tính thu được từ ảnh liên tục bởi quá trình số hoá (lấy mẫu và lượng hoá), giá trị I(x,y) biểu diễn cường độ sang được mã hoá của mỗi điểm ảnh (x,y).
- Với cách biểu diễn trên, ảnh số chính là một phần của tín hiệu số trong không gian hai chiều.
- Và cách biểu diễn ảnh số thông dụng nhất là dùng bảng hai chiều thường gọi là ma trận ảnh hay bản đồ ảnh.
- Hệ thống số là một hệ thống tiếp nhận tín hiệu số ở đầu vào, xử lý tín hiệu theo một quy trình nào đấy và dữ liệu đầu ra cũng là tín hiệu số.
- Vì ảnh số là một phần của tín hiệu số nên hệ thống xử lý ảnh số có đặc thù như hệ thống số cộng thêm một số tính chất riêng.
- Các kênh (chanels) Kết quả của quá trình xử lý dữ liệu trên tệp RAW để nội suy ra các giá trị còn thiếu(hoặc trong máy ảnh, hoặc trong máy tính) là một mảng chữ nhật của các điểm ảnh, mỗi một điểm ảnh này có ba giá trị.
- Các kênh có thể tách rời nhau và được xem như các hình ảnh độc lập.
- Ảnh đơn sắc hay ảnh đa mức xám là một trường hợp đặc biệt khi ba kênh này đồng nhất với nhau.
- Màu ở trên sử dụng một thang chia từ 0-255 cho mỗi kênh.
- Số lượng màu lớn nhất trong một ảnh như thế có thể là 16 triệu màu (tương đương với 3256.
- Người ta cũng chỉ ra rằng, ta có thể làm hơn thế nữa với các ảnh RAW mà nó có thể chứa tới 4096 giá trị có thể cho mỗi kênh.
- 12-bit là một byte rưỡi, nhưng các tệp được lưu với giá trị dữ liệu trên toàn bộ byte.
- Bởi vậy để chứa những hình ảnh này, phần lưu trữ được chỉ định là 2 byte hay 16-bit cho mỗi kênh với mỗi điểm ảnh.
- Điều này có nghĩa là một số phần lưu trữ sẽ bị lãng phí, nhưng nó lại là không gian nhớ cho ta thao tác với ảnh.
- 10 Kích cỡ của ảnh Ta phải biết một điều quan trọng là bất kể dữ liệu ảnh được nén để lưu trên đĩa hay nó được tải vào bộ nhớ để xử lý thì cũng chiếm một số lượng lớn các byte.
- Do vậy một ảnh 12-megapixel được tải từ ảnh JPEG (mà nó chỉ chứa 8-bit trên mỗi kênh) thì cần 36MB bộ nhớ trong quá trình xử lý.
- Nếu nó được tải từ tệp RAW hoặc từ ảnh TIFF 16-bit thì cần 72MB nhớ trong quá trình xử lý.
- 2 Các định dạng ảnh cơ bản trong ảnh số Hiện tại có hơn 50 định dạng ảnh khác nhau, được chia làm hai loại cơ bản: ảnh bitmap và ảnh vector.
- Ảnh bitmap là loại ảnh được lưu trữ theo dạng từng điểm màu được xếp liền nhau theo một thứ tự nhất định do người định dạng ảnh quy định và có thể được nén bằng một vài thuật toán nén dữ liệu do người định dạng ảnh chọn.
- Đây là loại ảnh có chất lượng lưu trữ tốt, hình ảnh và màu sắc trung thực, nhưng lại tốn không gian lưu trữ, tốc độ hiển thị chậm và tương đối phức tạp trong việc xử lý.
- Một vài ví dụ về các loại ảnh bitmap phổ biến là: GIF, PCX, BMP, TIF, RLE, ICO, GEM… Ảnh vector là loại ảnh được lưu trữ theo cách mô tả đường biên của các đối tượng trong ảnh như là các hình và các đường hình học, ví dụ như elíp(ellipse), đa giác (polygon), hình cung (arc), đường thẳng(line), chữ nhật(rectangle)… Việc lưu trữ ảnh vector thực chất là lưu trữ lại các lệnh dùng để vẽ lại ảnh đó.
- Ảnh vector được lưu trữ dưới dạng hình học nên chất 11lượng lưu trữ không tốt lắm, nhưng bù lại, kích thước file ảnh tương đối nhỏ và việc xử lý ảnh rất đơn giản, thong qua các hàm toán học.
- Các file ảnh vector phổ biến hiện nay là WMF, CGM, CDR, GEM Metafile… Ảnh thu được sau quá trình số hoá thường được lưu lại cho các quá trình xử lý tiếp theo hay truyền đi.
- Trong quá trình phát triển của kỹ thuật xử lý ảnh, tồn tại nhiều định dạng khác nhau từ ảnh đen trắng IMG, ảnh đa cấp xám/ ảnh màu: BMP, GIP, JPEG,… Tuy nhiên, các định dạng này là khác nhau, song chúng tuân theo một cấu trúc chung nhất.
- Dữ liệu nén (data compression.
- Bảng màu (Palellet color) Đầu tệp Chứa các thông tin về kiểu ảnh, kích thước, độ phân giải, số bít dung cho 1 pixel, cách mã hoá, vị trí bảng màu,… Kích thước phần header rất khác nhau, phụ thuộc kiểu định dạng ảnh.
- Dữ liệu nén Số liệu ảnh đã được mã hoá bởi kiểu mã hoá chỉ ra trong phần header Bảng màu Chỉ ra số màu dùng trong ảnh và sử dụng thể hiện ảnh Qui trình đọc tệp ảnh Để xử lý được ảnh, ta phải tiến hành đọc tệp ảnh và chuyển vào bộ nhớ của máy tính dưới dạng ma trận số hliệu ảnh.
- Khi lưu trữ dưới dạng tệp, ảnh là một khối các byte.
- Cuối cùng ta đọc phần dữ liệu nén.
- Các máy ảnh số hiện nay thường sử dụng hai định dạng JPEG và RAW trong việc lưu trữ ảnh số dưới dạng file hoặc lưu vào đĩa cứng.
- Định dạng RAW không phải là định dạng chung nhất của file ảnh, mỗi nhà sản xuất máy ảnh số đều có định dạng riêng của mình.
- JPEG (thường là định dạng .JPG) là định dạng chung nhưng nó không sánh kịp so với RAW vì hai lý do chính sau đây.
- Thuật toán nén JPEG thường bị suy hao dữ liệu.
- Định dạng JPG chỉ lưu dữ được các kênh màu với 8 bit.
- Ngoài ra còn một vài định dạng khác của ảnh số như: .DNG, .TIFF, .PSD vv 13Định dạng JPEG JPEG là tên của thuật toán nén (phương pháp sử dụng bảng tính).
- Trong đó, dữ liệu được nén bằng cách.
- Có thể đạt được các tỷ lệ nén lớn, tuy nhiên sẽ có những suy hao đáng kể.
- Các file JPEG thường được sử dụng như những kết quả cuối cùng đối với việc hiển thị hay quá trình phân bố.
- Tuy nhiên, sau mỗi lần nén ta thường bị suy hao dữ liệu, thậm chí ở quá trình xử lý cấp cao.
- Định dạng RAW Mỗi nhà sản xuất đều có một thuật toán riêng để nén và giải nén các dữ liệu ảnh theo cách mà không để bị suy hao dữ liệu.
- Các phần tử nén trong phạm vi 6 được sử dụng phổ biến nhất.
- Tuy nhiên, có một hạn chế là, không có nhiều ứng dụng có thể đọc được các định dạng này.
- Các máy ảnh hiện nay được trang bị Photoshop hay các phần mềm tiện ích khác thì có thể đọc được định dạng RAW.
- Định dạng PNG Định dạng PNG do Adobe tạo ra như là một định dạng chung với một mức giống nhau về quá trình nén và được trông đợi để thay thế định dạng của nhiều hãng khác nhau.
- 14Định dạng TIFF Đây là định dạng đã có mặt từ rất lâu.
- Định dạng này cần đến thuật toán LZW.
- Nhưng nó không nén được nhiều lắm đối với ảnh màu Định dạng PSD PSD là định dạng của Photoshop.
- Nén được ít và không bị mất dữ liệu.
- Ta chỉ sử dụng định dạng này khi cần làm việc với từng lớp ảnh và muốn sử dụng lớp ảnh đó cho công việc khác.
- 15 Định dạng RAW có 12 bit cho mỗi kênh màu.
- Trong khi đó, JPEG chỉ có 8bit trên mỗi kênh màu Định dạng ảnh Bitmap Ta tìm hiểu chi tiết cấu trúc của ảnh này vì đây là đối tượng chính đóng vai trò vật mang tin trong bài toán của ta.
- Ảnh BIMAP do hãng Microsoft đề xuất, phần mở rộng là BMP và được sử dụng rộng rãi trên các ứng dụng của Windows.
- Dữ liệu của ảnh BITMAP là một ma trận điểm ảnh, mỗi điểm ảnh được biểu diễn bởi một số bit, thông thường là 8 bit hoặc 24 bit

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt