›

Đồ án Tìm hiểu phương pháp cực tiểu năng lượng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh - Lê Thị Ngọc Mai

pdf 58 trang huongle 2490
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu phương pháp cực tiểu năng lượng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh - Lê Thị Ngọc Mai", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_tim_hieu_phuong_phap_cuc_tieu_nang_luong_dua_tren_do_d.pdf

Nội dung text: Đồ án Tìm hiểu phương pháp cực tiểu năng lượng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh - Lê Thị Ngọc Mai

  1. Bé gi¸o dôc vµ ®µo t¹o Tr•êng ®¹i häc d©n lËp h¶i phßng o0o TÌM HIỂU PHƢƠNG PHÁP CỰC TIỂU NĂNG LƢỢNG DỰA TRÊN ĐỘ ĐỒNG NHẤT VÀ ĐỘ KHÔNG ỔN ĐỊNH CHO PHÂN ĐOẠN ẢNH ®å ¸n tèt nghiÖp ®¹i häc hÖ chÝnh quy Ngµnh: C«ng nghÖ Th«ng tin Sinh viªn thùc hiÖn: Lê Thị Ngọc Mai Gi¸o viªn h•íng dÉn: PGS TS. Ngô Quốc Tạo M· sè sinh viªn: 110315 H¶i Phßng - 2011
  2. Mục lục LỜI CẢM ƠN 4 DANH MỤC TỪ VIẾT TẮT 5 DANH SÁCH ẢNH 6 LỜI MỞ ĐẦU 7 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ PHÂN ĐOẠN ẢNH 8 1.1 Tổng quan về xử lý ảnh 8 1.1.1 XLA là gì? 8 1.1.2 Sơ đồ tổng quát XLA 9 1.1.3 Mô tả (biểu diễn ảnh) 11 1.1.4 Các khái niệm cơ bản 13 1.2 Tổng quan về phân đoạn ảnh 15 CHƢƠNG 2: CÁC HƢỚNG TIẾP CẬN CHÍNH TRONG PHÂN ĐOẠN ẢNH 17 2.1 Các phƣơng pháp dựa trên không gian đặc trƣng 17 2.2 Các phƣơng pháp dựa trên không gian ảnh 17 2.3 Các phƣơng pháp dựa trên mô hình vật lý 18 2.4 Một số thuật toán phân đoạn ảnh 23 2.4.1 Thuật toán Entropy cực đại 23 2.4.2 Thuật toán độ lệch nhỏ nhất 29 CHƢƠNG 3: PHƢƠNG PHÁP CỰC TIỂU NĂNG LƢỢNG DỰA TRÊN ĐỘ ĐỒNG NHẤT VÀ ĐỘ KHÔNG ỔN ĐỊNH CHO PHÂN ĐOẠN ẢNH 36 3.1 Giới thiệu 36 3.1.1 Cơ sở lý thuyết 36 3.1.2 Tối ƣu và tự động ngƣỡng 36 3.2 Lý thuyết 37 3.2.1 Cƣờng độ dựa trên độ không ổn định 37 3.2.2 Bề mặt năng lƣợng và tối ƣu ngƣỡng 38 3.3 Phƣơng pháp 38
  3. 3 3.3.1 Phân bố xác suất tiên nghiệm đối tƣợng o( )và nền B( ) 39 3.3.2 Hàm mật độ  40 3.3.3 Bản đồ gradient chuẩn ∇σ 40 3.3.4 Tối ƣu giá trị của và σ trên bề mặt năng lƣợng E 40 3.4 Tiến trình giải thuật: 42 CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH VÀ ĐÁNH GIÁ 44 4.1 Cài đặt chƣơng trình 44 4.1.1 Định dạng ảnh BMP 44 4.1.2 Cài đặt thử nghiệm 45 4.2 Một số kết quả và đánh giá 54 KẾT LUẬN 57 TÀI LIỆU THAM KHẢO 58 Lê Thị Ngọc Mai – CT1101
  4. 4 LỜI CẢM ƠN Trƣớc hết em xin gửi lời cảm ơn đến PGS TS. Ngô Quốc Tạo – Viện CNTT, Viện KH&CN Việt Nam, ngƣời thầy đã hƣớng dẫn em rất nhiều trong suốt quá trình tìm hiểu nghiên cứu và hoàn thành đồ án tốt nghiệp từ lý thuyết đến ứng dụng. Sự hƣớng dẫn của thầy đã giúp em có thêm đƣợc những hiểu biết về phân đoạn ảnh, đặc biệt phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh. Đồng thời em cũng xin chân thành cảm ơn các thầy cô trong bộ môn cũng nhƣ các thầy cô trong trƣờng đã trang bị cho em những kiến thức cơ bản cần thiết để em có thể hoàn thành tốt đồ án này. Em xin gửi lời cảm ơn đến gia đình, bạn bè đã tạo mọi điều kiện thuận lợi để em có thể xây dựng thành công đồ án. Dù đã rất cố gắng để hoàn thành công việc đƣợc giao, song do trình độ còn hạn chế nên không thể tránh khỏi những thiếu sót. Em rất mong nhận đƣợc sự góp ý và thông cảm của mọi ngƣời. Em xin trân thành cảm ơn! Hải Phòng, Ngày tháng 7 năm 2011 Sinh viên thực hiện Lê Thị Ngọc Mai Lê Thị Ngọc Mai – CT1101
  5. 5 DANH MỤC TỪ VIẾT TẮT Kí hiệu viết tắt Giải thích XLA Xử lý ảnh R Red G Green B Blue Lê Thị Ngọc Mai – CT1101
  6. 6 DANH SÁCH ẢNH Hình 1.1 Quá trình XLA 8 Hình 1.2. Các bƣớc cơ bản trong XLA 9 Hình 1.3. Biểu diễn ảnh bằng mã chạy 11 Hình 1.4. Biểu diễn ảnh bằng mã xích (8 hƣớng) 12 Hình 1.5. Biểu diễn ảnh bằng mã tứ phân 13 Hình 1.6 Các láng giềng của điểm ảnh (x, y). 15 Hình 2.1. Phân đoạn theo thuật toán Entropy cực đại 28 Hình 2.2. Phân đoạn theo thuật toán độ lệch nhỏ nhất. 34 Hình 3.2. Ví dụ minh họa dòng năng lƣợng và bề mặt năng lƣợng. 41 Hình 3.1. Minh họa vực bên trong 42 Hình 4.1. Ảnh lƣu dƣới dạng BMP đuôi .bmp 44 Hình 4.2. Kết quả phân đoạn ảnh bông hoa và biểu đồ dòng năng lƣợng 54 Hình 4.3. Kết quả phân đoạn ảnh cô gái và biểu đồ dòng năng lƣợng. 55 Lê Thị Ngọc Mai – CT1101
  7. 7 LỜI MỞ ĐẦU Trong vài thập kỷ qua, khai thác đa tầng của thông tin trong ảnh hai hay nhiều chiều vẫn là chủ đề của rất nhiều bài nghiên cứu. Đặc biệt sự thông dụng của kỹ thuật ảnh trong nhiều ngành nhƣ y học, vật lý, hóa học đã làm đẩy mạnh quá trình xử lý ảnh bằng máy tính để khai thác dữ liệu ảnh lớn nhằm đƣa ra sản phẩm mong muốn. Phân đoạn là một nhiệm vụ nổi bật nhất trong ứng dụng ảnh cụ thể nhƣ những gì liên quan tới phân loại đối tƣợng, hình dạng, phân tích chuyển động Vì nhiều lý do mà xác định các đối tƣợng một cách chính xác và hiệu quả rất quan trọng trong xử lý ảnh trên máy tính và công việc này đƣợc gọi là phân đoạn ảnh. Trong thời gian đầu, các phƣơng pháp phân vùng ảnh đƣợc đƣa ra chủ yếu làm việc trên các ảnh mức xám do các hạn chế về phƣơng tiện thu thập và lƣu trữ. Ngày nay, cùng với sự phát triển về các phƣơng tiện thu nhận và biểu diễn ảnh , các ảnh màu đã hầu nhƣ thay thế hoàn toàn các ảnh mức xám trong việc biểu diễn và lƣu trữ thông tin do các ƣu thế vƣợt trội hơn hẳn so với ảnh mức xám. Do đó, các kỹ thuật, thuật giải mới thực hiện việc phân vùng ảnh trên các loại ảnh màu liên tục đƣợc phát triển để đáp ứng các nhu cầu mới. Các thuật giải, kỹ thuật này thƣờng đƣợc phát triển dựa trên nền tảng các thuật giải phân vùng ảnh mức xám đã có sẵn. Mục đích chính của em là tìm hiểu phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh. Và đƣợc trình bày trong 4 chƣơng: Chƣơng 1: Trình bày tổng quan về xử lý ảnh và phân đoạn ảnh bao gồm các khái niệm cơ bản, sơ đồ tổng quát của một hệ thống xử lý ảnh và các vấn đề cơ bản trong xử lý ảnh, vai trò, nhiệm vụ của phân đoạn ảnh. Chƣơng 2: Giới thiệu các hƣớng tiếp cận chính trong phân đoạn ảnh, bao gồm: các phƣơng pháp dựa trên không gian đặc trƣng, các phƣơng pháp dựa trên không gian ảnh, các phƣơng pháp dựa trên mô hình vật lý. Trong chƣơng này, em cũng xin trình bày hai thuật toán phân đoạn ảnh, đó là thuật toán Entropy cực đại và thuật toán độ chia nhỏ nhất. Chƣơng 3: Trình bày phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh bao gồm: giới thiệu tổng quan, cơ sở lý thuyết của phƣơng pháp, tiến trình giải thuật. Chƣơng 4: Cài đặt chƣơng trình, đƣa ra một số kết quả và đánh giá. Lê Thị Ngọc Mai – CT1101
  8. 8 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ PHÂN ĐOẠN ẢNH Xử lý ảnh là lĩnh vực mang tính khoa học và công nghệ. Nó là một ngành khoa học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ của nó phát triển rất nhanh, kích thích các trung tâm nghiên cứu, ứng dụng, đặc biệt là máy tính chuyên dụng cho nó. Khoảng hơn mười năm trở lại đây, phần cứng máy tính và các thiết bị liên quan đã có sự tiến bộ vượt bậc về tốc độ tính toán, dung lượng chứa, khả năng xử lý và giá cả đã giảm đến mức máy tính và các thiết bị liên quan đến xử lý ảnh đã không còn là thiết bị chuyên dụng nữa. Khái niệm ảnh số đã trở nên thông dụng với hầu hết mọi người trong xã hội và việc thu nhận ảnh số bằng các thiết bị cá nhân hay chuyên dụng cùng với việc đưa vào máy tính xử lý đã trở nên đơn giản. 1.1 Tổng quan về xử lý ảnh (XLA) 1.1.1 XLA là gì? Qua trình XLA là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra có thể là một ảnh “tốt hơn” hoặc một kết luận [1]. ảnh “tốt hơn” Xử lý ảnh Ảnh Kết luận Hình 1.1 Quá trình XLA Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh đƣợc xem nhƣ là đắc trƣng cƣờng độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tƣợng trong không gian và nó thể xem nhƣ một hàm n bất biến P(c1, c2, c3, ,cn). Do đó, ảnh trong XLA có thể xem nhƣ ảnh n chiều. Mục đích của XLA là:  Biến đổi ảnh làm tăng chất lượng ảnh: Phƣơng pháp biến đổi ảnh đƣợc sử dụng trong việc xử lý các ảnh chụp từ không trung (chƣơng trình đo đạc từ máy bay, vệ tinh và các ảnh vũ trụ) hoặc xử lý các ảnh trong y học (ảnh chụp cắt lát, ảnh siêu âm, vv ). Một ứng dụng khác Lê Thị Ngọc Mai – CT1101
  9. 9 của việc biến đổi ảnh là mã hoá ảnh, trong đó các ảnh đƣợc xử lý để rồi lƣu trữ hoặc truyền đi.  Tự động nhận dạng, đoán ảnh, đánh giá nội dung ảnh: Các phƣơng pháp nhận dạng ảnh đƣợc sử dụng khi xử lý tế bào, nhiễm sắc thể, nhận dạng chữ vv Thực chất của công việc nhận dạng chính là sự phân loại đối tƣợng thành các lớp đối tƣợng đã biết hoặc thành những lớp đối tƣợng chƣa biết. Bài toán nhận dạng ảnh là một bài toán lớn, có rất nhiều ý nghĩa thực tiễn và ta cũng có thể thấy rằng để công việc nhận dạng trở nên dễ dàng thì ảnh phải đƣợc tách thành các đối tƣợng riêng biệt – đây là mục đích chính của bài toán phân đoạn ảnh. Nếu phân đoạn ảnh không tốt sẽ dẫn đến sai lầm trong quá trình nhận dạng ảnh, bởi vậy ngƣời ta xem công đoạn phân đoạn ảnh là vấn đề then chốt trong quá trình xử lý ảnh nói chung. 1.1.2 Sơ đồ tổng quát XLA Thu nhận Tiền xử lý Phân đoạn Biểu diễn Nhận dạng ảnh ảnh và mô tả và nội suy Cơ sở tri thức Hình 1.2. Các bƣớc cơ bản trong XLA  Thu nhận ảnh (Image Acquisition): Ảnh có thể nhận qua camera màu hoặc đen trắng, scanner hay giác quan Thƣờng ảnh nhận qua camera và scanner là ảnh tƣơng tự hoặc ảnh số (với các camera đã số hóa). Camera thƣờng dùng là loại quét dòng; ảnh tạo ra có dạng hai chiều. Chất lƣợng của ảnh thu đƣợc phụ thuộc vào thiết bị thu và môi trƣờng (ánh sáng, phong cảnh). Lê Thị Ngọc Mai – CT1101
  10. 10  Tiền xử lý (Image Processing): Sau khi thu nhận, ảnh có thể nhiễu, độ tƣơng phản thấp nên cần đƣa vào bộ tiền xử lý đê nâng cao chất lƣợng. Chức năng chính của bộ tiền xử lý là lọc nhiễu, nâng độ tƣơng phản làm cho ảnh rõ hơn, nét hơn.  Phân đoạn ảnh (Image Segmetation): Phân đoạn ảnh là tách ảnh ban đầu thành các vùng thành phần để biểu diễn phân tích hoặc nhận dạng ảnh. Đây là phần phức tạp, khó khăn nhất trong XLA, cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này.  Biểu diễn ảnh (Image Representation): Ảnh đầu ra sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lân cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trƣng (Feature Selection) gắn với việc tách các đặc tính của ảnh dƣới dạng các thông tin định lƣợng hoặc làm cơ sở để phân lớp đối tƣợng này với đối tƣợng khác trong phạm vi ảnh nhận đƣợc. Ví dụ: trong nhận dạng các ký tự, ta miêu tả các đặc trƣng của từng ký tự, giúp phân biệt ký tự này với ký tự khác.  Nhận dạng và nội suy ảnh (Image Recagnition and Interpretation): Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thƣờng thu đƣợc bằng cách so sánh với mẫu chuẩn đã đƣợc học (hoặc lƣu) từ trƣớc. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh đƣợc phân theo hai loại nhận dạng cơ bản: - Nhận dạng theo tham số. - Nhận dạng theo cấu trúc. Một số đối tƣợng nhận dạng khá phổ biến hiện nay đang đƣợc áp dụng trong khoa học và công nghệ là nhận dạng ký tự, nhận dạng văn bán, nhận dạng vân tay, nhận dạng mã vạch, nhận dạng khuôn mặt  Cơ sở tri thức (Knowledge Base): Ảnh là một đối tƣợng phức tạp về đƣờng nét, độ sáng tối, dung lƣợng điểm ảnh, môi trƣờng để thu nhận ảnh phong phú, kéo theo nhiễu. Trong nhiều khâu xử lý và phân tích ảnh, ngoài việc đơn giản hóa các phƣơng pháp toán học đảm bảo tiện lợi cho xử lý, ngƣời ta bắt chƣớc quy trình tiếp nhận và XLA theo cách của con ngƣời. Trong các bƣớc xử lý đó, nhiều khâu hiện nay đã xử lý theo các phƣơng pháp trí tuệ con ngƣời. Vì vậy, ở đây cơ sở tri thức đƣợc phát huy Lê Thị Ngọc Mai – CT1101
  11. 11 1.1.3 Mô tả (biểu diễn ảnh) Từ hình 1.1, ảnh sau khi số hóa sẽ đƣợc lƣu vào bộ nhớ hoặc chuyển sang khâu tiếp theo để phân tích. Nếu lƣu trữ ảnh trực tiếp từ ảnh thô, đòi hổi dung lƣợng bộ nhớ phải cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thƣờng, các ảnh thô đó đƣợc biểu diễn lại (hay đơn giản là mã hóa) theo các đặc điểm của ảnh gọi là đặc trƣng ảnh (Image Features) nhƣ biên ảnh (boundary), vùng ảnh (Region). Một số phƣơng pháp biểu diễn thƣờng dùng: - Biểu diễn bằng mã chạy (Run-Length Code). - Biểu diễn bằng mã xích (Chaine Code). - Biểu diễn bằng mã tứ phân (Quad-Tree Code).  Biểu diễn bằng mã chạy: Phƣơng pháp này thƣờng biểu diễn cho vùng ảnh và áp dụng cho ảnh nhị phân. Một vùng ảnh R có thể mã hóa đơn giản nhờ một ma trận nhị phân: U(m, n) =1 nếu (m, n) R U(m, n) =0 nếu (m, n) R Trong đó: U(m, n) là hàm mô tả mức xám ảnh tại tọa độ (m, n). Với cách biểu diễn trên, một vùng ảnh đƣợc mô tả bằng một tập các chuỗi 0 hoặc 1. Giả sử ta mô tả ảnh nhị phân của một vùng ảnh đƣợc thể hiện theo tọa độ (x, y) theo các chiều và đặc tả chỉ đối với giá trị “1”, khi đó dạng mô rat có thể là: (x, y)r; trong đó, (x, y) là tọa độ, r là số lƣợng các bit có giá trị “1” liên tục theo chiều dọc hoặc chiều ngang (xem hình 1.3). 0 1 2 3 4 5 0 1 2 3 4 5 Hình 1.3. Biểu diễn ảnh bằng mã chạy (1, 1)2, (2, 2)2, (3, 3)2, (4, 4)1 Lê Thị Ngọc Mai – CT1101
  12. 12  Biểu diễn bằng mã xích: Phƣơng pháp thƣờng dùng để biểu diễn đƣờng biên ảnh. Một đƣờng bất kỳ đƣợc chia thành các đoạn nhỏ. Nối các điểm chia, ta có đƣợc đoạn thẳng kế tiếp đƣợc gán hƣớng cho đoạn thẳng đó, tạo thành một dây xích gồm các đoạn. Các hƣớng có thể chọn là 4, 8, 12, 24, mỗi hƣớng đƣợc mã hóa theo số thập phân hoặc số nhị phân thành mã của hƣớng (xem hình 1.4). 3 2 1 4 0 5 6 7 Hình 1.4. Biểu diễn ảnh bằng mã xích (8 hƣớng) A 111 110 000 001 000 110 101 011 100 010  Biểu diễn bằng mã tứ phân: Phƣơng pháp mã tứ phân đƣợc dùng để mã hóa cho vùng ảnh. Vùng ảnh đầu tiên đƣợc chia làm bốn phần thƣớng là bằng nhau bằng nhau. Nếu mỗi vùng là đồng nhất, tức là chứa toàn điểm đen (1) hay toàn điểm trắng (0) (xem hình 1.5. a))., thì gán cho vùng đó một mã và không chia tiếp. Các vùng không đồng nhất đƣợc chia tiếp làm bốn phần theo thủ tục trên cho đến khi tất cả các vùng đều đống nhất. Các mã phân chia thành các vùng con tạo thành một cây phân chia thành các vùng đồng nhất (xem hình 1.5. b)). Lê Thị Ngọc Mai – CT1101
  13. 13 0 1 2 3 4 5 6 7 0 17 18 6 9 10 1 19 20 2 21 22 25 26 7 11 3 23 24 27 28 4 13 14 5 4 6 15 16 7 a) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 b) Hình 1.5. Biểu diễn ảnh bằng mã tứ phân a) Chia ảnh thành các vùng đồng nhất b) Cây phân chia 1.1.4 Các khái niệm cơ bản  Ảnh số Gốc của ảnh (ảnh tự nhiên) là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính, ảnh cần phải đƣợc số hóa. Số hóa ảnh là sự biến đổi gần đúng một Lê Thị Ngọc Mai – CT1101
  14. 14 ảnh liên tục thành một tập hợp điểm phù hợp với ảnh thật về vị trí (không gian) và độ sáng (mức xám)  Điểm ảnh (pixel) Điểm ảnh (pixel) là một phần tử của ảnh số tại tọa độ (x, y) trong không gian ảnh 2 chiều với độ xám hoặc màu nhất định. Kích thƣớc và khoảng cách giữa các điểm ảnh đó đƣợc chọn sao cho mắt ngƣời cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần nhƣ ảnh thật. Mỗi phần tử trong ma trận gọi là một phần tử ảnh.  Mức xám Mức xám của một điểm ảnh là cƣờng độ sáng của nó, đƣợc gán bằng giá trị số tại điểm đó - Các thang giá trị mức xám thông thƣờng: 16, 32, 65, 128, 256 (mức 256 là phổ biến nhất, ở mức này mỗi pixel đƣợc mã hóa bởi 8bit). - Ảnh trắng đen: là ảnh chỉ có 2 màu trắng và đen (không chứa màu khác) với mức xám ở các điểm ảnh có thể khác nhau. - Ảnh nhị phân: là ảnh có 2 mức trắng đen phân biệt, tức là dùng 1bit mô tả 21 mức khác nhau. Nói cách khác: mỗi bit điểm ảnh nhị phân chỉ có thể là 0 hoặc 1. - Ảnh màu: trong khuôn khổ lý thuyết 3 màu (Red, Green, Blue) để tạo nên thế giới màu, ngƣời ta thƣờng dùng 3 byte để mô tả mức màu, khi đó các giá trị màu: 28*3=224≈16,7 triệu màu. - Ảnh xám: là trƣờng hợp đặc biệt của ảnh màu khi giá trị màu Red, Green, Blue bằng nhau.  Biên Biên là một đặc tính rất quan trọng của đối tƣợng trong ảnh, nhờ vào biên mà chúng ta phân biệt đƣợc đối tƣợng này với đối tƣợng kia. Một điểm ảnh có thể gọi là điểm biên nếu ở đó có sự thay đổi đột ngột về mức xám. Tập hợp các điểm biên tạo thành biên hay còn gọi là đƣờng bao ảnh.  Láng giềng Trong XLA có một khái niệm rất quan trọng, đó là khái niệm láng giềng. Có hai loại láng giềng: 4-láng giềng và 8-láng giềng. Lê Thị Ngọc Mai – CT1101
  15. 15 (x, y-1) (x-1, y-1) (x+1, y-1) (x-1, y) (x+1, y) (x, y) (x+1, y+1) (x-1, y+1) (x, y+1) Hình 1.6 Các láng giềng của điểm ảnh (x, y). 4-láng giềng của một điểm (x,y) là một tập hợp bao gồm láng giềng dọc và láng giềng ngang của nó: N4((x,y)) = {(x+1,y), (x-1,y), (x,y+1), (x,y-1)} (1.1) 8-láng giềng của (x,y) là một tập cha của 4-láng giềng và bao gồm láng giềng ngang, dọc và chéo: N8((x,y)) = N4((x,y)){(x+1,y+1),(x-1,y-1), (x+1,y-1),(x-1,y+1)} (1.2)  Vùng liên thông Một vùng R đƣợc gọi là liên thông nếu bất kỳ hai điểm (xA,yA) và (xB,yB) thuộc vào R có thể đƣợc nối bởi một đƣờng (xA,yA) (xi-1,yi-1), (xi,yi), (xi+1,yi+1) (xB,yB), mà các điểm (xi,yi) thuộc vào R và bất kỳ điểm (xi,yi) nào đều kề sát với điểm trƣớc (xi-1,yi-1) và điểm tiếp theo (xi+1,yi+1) trên đƣờng đó. Một điểm (xk,yk) đƣợc gọi là kề với điểm (xl,yl) nếu (xl,yl) thuộc vào láng giềng trực tiếp của (xk,yk). 1.2 Tổng quan về phân đoạn ảnh Phân đoạn ảnh là một thao tác ở mức thấp trong toàn bộ quá trình xử lý ảnh. Quá trình này thực hiện việc phân vùng ảnh 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. Vì thế, trong hầu hết các ứng dụng của lĩnh vực XLA, thị giác máy tính, phân đoạn ảnh luôn đóng một vai trò cơ bản và thƣờng là bƣớc tiền xử lý đầu tiên trong toàn bộ quá trình trƣớc khi thực hiện các thao tác khác ở mức cao hơn nhƣ nhận dạng đối tƣợng, biểu diễn đối tƣợng, nén ảnh dựa trên đối tƣợng, hay truy vấn ảnh dựa vào nội dung Lê Thị Ngọc Mai – CT1101
  16. 16 Trƣớc hết cần làm rõ khái niệm “vùng ảnh” (Segment) và đặc trƣng vật lý của vùng. Vùng ảnh là một chi tiết, một thực thể trông toàn cảnh. Nó là tập hợp các điểm ảnh có cùng hoặc gần cùng một tính chất nào đó: mức xám, mức màu, độ nhám Vùng ảnh là một trong hai thuộc tính của ảnh. Nói đến vùng ảnh là nói đến tính chất bề mặt. Đƣờng bao quanh một vùng ảnh là biên ảnh (Boundary). Các điểm ảnh trong một vùng ảnh có độ biến thiên giá trị mức xám tƣơng đối đồng đều hay tính kết cấu tƣơng đồng. Nguỡng (Threshold) là một khái niệm khá quen thuộc trong xử lý ảnh cũng nhƣ rất nhiều giải thuật khác. Nó dùng để chỉ một giá trị mà ngƣời ta dựa vào để phân hoạch một tập hợp thành các miền phân biệt. Giá trị ngƣỡng thƣờng đƣợc xác định dựa vào những điểm đặc biệt (ví dụ ở trung bình), dựa vào kinh nghiệm khảo sát. Nếu dựa vào số lƣợng ngƣỡng áp dụng cho cùng một tập dữ liệu ngƣời ta sẽ phân ra các phƣơng pháp ứng dụng ngƣỡng đơn, ngƣỡng kép, hay đa ngƣỡng. Nếu dựa vào sự biến thiên của giá trị ngƣỡng, trong cùng phạm vi ứng dụng ngƣời ta sẽ phân ra các phƣơng pháp dùng ngƣỡng cố định (Constant|Fixed Threshold) và không cố định (Adaptive Threshold). Ngƣỡng không cố định nghĩa là giá trị của nó sẽ thay đổi tùy theo sự biến thiên của tập dữ liệu theo không gian và thời gian. Thông thƣờng giá trị này đƣợc xác định thông qua khảo sát tập dữ liệu bằng phƣơng pháp thống kê. Xem xét các phƣơng pháp khác nhau cho phân đoạn ảnh mức xám với kết quả cho ra có thể chấp nhận đƣợc thì phƣơng pháp chọn ngƣỡng cố định là một trong những phƣơng pháp phân đoạn ảnh phổ biến nhất, bởi vì nó đơn giản và tƣơng đối bền vững. Thông thƣờng mức xám của điểm ảnh thuộc đối tƣợng cơ bản khác với mức xám của nền, bởi vậy bằng cách chon ngƣỡng thích hợp ta có thể dễ dàng tách riêng đối tƣợng và nền. Kết quả của chọn ngƣỡng là ảnh bitmap có một trạng thái cho biết các đối tƣợng cận cảnh, nhƣ văn bản in, một chú thích, phần lỗi của vật liệu và trạng thái còn lại sẽ tƣơng ứng với nền. Tùy thuộc vào ứng dụng, cận cảnh có thể đƣợc biểu diễn bởi mức xám 0, tức là màu đen đối với văn bản, còn nền đƣợc biểu diễn bởi mức xám 255 trong ảnh 8-bit. Hoặc ngƣợc lại, cận cảnh đƣợc biểu diễn bởi màu đen, nền bằng màu trắng. Tƣ tƣởng chính của phân đoạn ảnh: - Cho ngƣỡng t - Phân đoạn ảnh I[x,y]= Lê Thị Ngọc Mai – CT1101
  17. 17 CHƢƠNG 2: CÁC HƢỚNG TIẾP CẬN CHÍNH TRONG PHÂN ĐOẠN ẢNH Phân đoạn ảnh là chia ảnh thành các vùng không trùng lắp. Mỗi vùng gồm một nhóm pixel liên thông và đồng nhất theo một tiêu chí nào đó. Tiêu chí này phụ thuộc vào mục tiêu của quá trình phân đoạn. Ví dụ như đồng nhất về màu sắc, mức xám, kết cấu, độ sâu của các layer Sau khi phân đoạn mỗi pixel chỉ thuộc về một vùng duy nhất. Để đánh giá chất lượng của quá trình phân đoạn là rất khó. Vì vậy trước khi phân đoạn ảnh cần xác định rõ mục tiêu của quá trình phân đoạn là gì. Xét một cách tổng quát, ta có thể chia các hướng tiếp cận phân đoạn ảnh thành ba nhóm chính như sau: - Các phương pháp dựa trên không gian đặc trưng - Các phương pháp dựa trên không gian ảnh - Các phương pháp dựa trên mô hình vật lý. 2.1 Các phƣơng pháp dựa trên không gian đặc trƣng Nếu chúng ta giả định màu sắc bề mặt của các đối tƣợng trong ảnh là một thuộc tính bất biến và các màu sắc đó đƣợc ánh xạ vào một không gian màu nào đó, vậy thì chúng ta sẽ có một cái nhìn đối với mỗi đối tƣợng trong ảnh nhƣ là một cụm (cluster) các điểm trong không gian màu đó. Mức độ phân tán của các điểm trong trong một cụm đƣợc xác định chủ yếu bởi sự khác biệt về màu sắc. Một cách khác, thay vì ánh xạ các pixel trong ảnh vào một không gian màu cụ thể, ta xây dựng một histogram dựa trên các đặc trƣng màu dạng ad-hoc cho ảnh đó (ví dụ nhƣ Hue), và thông thƣờng, các đối tƣợng trong ảnh sẽ xuất hiện nhƣ các giá trị đỉnh trong histogram đó. Do đó, việc phân vùng các đối tƣợng trong ảnh tƣơng ứng với việc xác định các cụm – đối với cách biểu diễn thứ nhất – hoặc xác định các vùng cực trị của histogram – đối với cách biểu diễn thứ hai. Các phƣơng pháp tiếp cận này chỉ làm việc trên một không gian màu xác định. Dựa trên không gian đặc trƣng, ta có các phƣơng pháp phân đoạn: phƣơng pháp phân nhóm đối tƣợng không giám sát, phƣơng pháp phân lớp trung bình-k thích nghi, phƣơng pháp lấy ngƣỡng histogram. 2.2 Các phƣơng pháp dựa trên không gian ảnh Hầu hết những phƣơng pháp đƣợc đề cập trong phần trên đều hoạt động dựa trên các không gian đặc trƣng của ảnh (thông thƣờng là màu sắc). Do đó, các vùng Lê Thị Ngọc Mai – CT1101
  18. 18 ảnh kết quả là đồng nhất tƣơng ứng với các đặc trƣng đã chọn cho từng không gian. Tuy nhiên, không có gì đảm bảo rằng tất cả các vùng này thể hiển một sự cô đọng (compactness) về nội dung xét theo ý nghĩa không gian ảnh (ý nghĩa các vùng theo sự cảm nhận của hệ thần kinh con ngƣời). Mà đặc tính này là quan trọng thứ hai sau đặc tính về sự đồng nhất của các vùng ảnh. Do các phƣơng pháp gom cụm cũng nhƣ xác định ngƣỡng histogram đã nêu đều bỏ qua thông tin về vị trí của các pixel trong ảnh. Trong các báo cáo khoa học về phân vùng ảnh mức xám, có khá nhiều kỹ thuật cố thực hiện việc thoả mãn cùng lúc cả hai tiêu chí về tính đồng nhất trong không gian đặc trƣng của ảnh và tính cô đọng về nội dung ảnh. Tuỳ theo các kỹ thuật mà các thuật giải này áp dụng, chúng đƣợc phân thành các nhóm sau: - Các thuật giải áp dụng kỹ thuật chia và trộn vùng. - Các thuật giải áp dụng kỹ thuật tăng trƣởng vùng. - Các thuật giải áp dụng lý thuyết đồ thị. - Các giải thuật áp dụng mạng neural. - Các giải thuật dựa trên cạnh. 2.3 Các phƣơng pháp dựa trên mô hình vật lý Tất cả các giải thuật đƣợc xem xét qua, không ít thì nhiều ở mặt nào đó đều có khả năng phát sinh việc phân vùng lỗi trong các trƣờng hợp cụ thể nếu nhƣ các đối tƣợng trong ảnh màu bị ảnh hƣởng quá nhiều bởi các vùng sáng hoặc bóng mờ, các hiện tƣợng này làm cho các màu đồng nhất trong ảnh thay đổi nhiều hoặc ít một cách đột ngột. Và kết quả là các thuật giải này tạo ra các kết quả phân vùng quá mức mong muốn so với sự cảm nhận các đối tƣợng trong ảnh bằng mắt thƣờng. Để giải quyết vấn đề này, các giải thuật phân vùng ảnh áp dụng các mô hình tƣơng tác vật lý giữa bề mặt các đối tƣợng với ánh sáng đã đƣợc đề xuất. Các công cụ toán học mà các phƣơng pháp này sử dụng thì không khác mấy so với các phƣơng pháp đã trình bày ở trên, điểm khác biệt chính là việc áp dụng các mô hình vật lý để minh hoạ các thuộc tính phản chiếu ánh sáng trên bề mặt màu sắc của các đối tƣợng. Cột mốc quan trọng trong lĩnh vực phân vùng ảnh màu dựa trên mô hình vật lý đƣợc Shafer đặt ra. Ông giới thiệu mô hình phản xạ lưỡng sắc cho các vật chất điện môi không đồng nhất. Dựa trên mô hình này, Klinker đã đặt ra một giải thuật đặt ra một số giả thiết quang học liên quan đến màu sắc, bóng sáng, bóng mờ của các đối tƣợng và cố gắng làm phù hợp chúng với hình dạng của các cụm. Hạn chế chính của giải thuật này là nó chỉ làm việc trên các vật chất điện môi không đồng Lê Thị Ngọc Mai – CT1101
  19. 19 nhất. Hai ông cùng tên Tsang đã áp dụng mô hình phản xạ lƣỡng sắc trong không gian HSV để xác định các đƣờng biên trong ảnh màu. Healey đề xuất một mô hình phản xạ đơn sắc cho các vật chất kim loại. Các phƣơng pháp đề cập trong phần này chỉ áp dụng cho hai loại vật chất là kim loại và điện môi không đồng nhất. Một thuật toán tổng quát và phức tạp hơn cũng đƣợc Maxwell và Shafer đề xuất trong.  Tóm lại, một cái nhìn tổng quan về các phƣơng pháp phân đoạn ảnh nhƣ sau: Phƣơng pháp phân đoạn ảnh màu Dựa trên không gian đặc trƣng Dựa trên không gian ảnh Mô hình vật lý Phân nhóm đối tƣợng Chia và trộn vùng Phân lớp tb k-thích nghi Tăng trƣởng vùng Lấy ngƣỡng histogram Lý thuyết đồ thị Mạng Neural Dựa trên cạnh  Mỗi phƣơng pháp đều có những ƣu nhƣợc điểm nhất định: Phương pháp phân Ý tưởng Ưu điểm Khuyết điểm vùng Dựa trên không gian đặc trƣng Phân nhóm - - Phân loại - Không quan đối tƣợng không cần giám sát. tâm đến các thông tin Lê Thị Ngọc Mai – CT1101
  20. 20 - Tồn tại các trong không gian ảnh. phƣơng pháp heuristic - Có vấn đề và hữu hạn. trong việc xác định số lƣợng các cụm ban đầu. - Khó khăn trong việc điều chỉnh các cụm sao cho phù hợp với các vùng trong ảnh. - Chọn một - Sở hữu tính - Cực đại hoá phần tử k, sau đó liên tục trong không một xác suất hậu chọn ngẫu nhiên k gian ảnh và tính thích nghiệm có thể bị sai trung tâm. Tính toán nghi cục bộ đối với do các cực trị địa khoảng cách giữa các vùng ảnh. phƣơng. Phân lớp pixel trung bình mỗi trung bình - Sử dụng các - Hội tụ chậm. cụm. Từ khoảng cách ràng buộc về không k-thích này có thể tính toán gian ảnh. nghi trung bình mới của cụm và lặp lại quá trình cho đến khi mỗi pixel là một bộ phận của các cụm k. - Cho ngƣỡng t - Không cần biết - Bỏ qua các - Phân đoạn ảnh trƣớc bất kỳ thông tin thông tin về không nào từ ảnh. gian ảnh. I[x,y]= - Các giải thuật - Lấy ngƣỡng Lấy nhanh và dễ dàng cài trong các histogram ngƣỡng đặt. đa chiều là một quá histogram trình phức tạp. - Dễ ảnh hƣởng bởi nhiễu xuất hiện trong ảnh. Lê Thị Ngọc Mai – CT1101
  21. 21 Dựa trên không gian ảnh - Dựa vào độ - Sử dụng các - Định nghĩa sáng của điểm ảnh để thông tin về không mức độ đồng nhất về phân nhỏ vùng, sao gian ảnh là chính. màu sắc có thể phức Chia và cho các vùng là đồng - Cho kết quả tốt tạp và khó khăn. trộn vùng nhất. với các ảnh chứa - Quadtree có - Trộn các vùng nhiều vùng màu đồng thể gây ra các kết quả nhỏ theo tiêu chí nhất nhất. không nhƣ mong định. muốn. - Xem xét ảnh - Các vùng ảnh - Tốn kém chi từ các miền nhỏ nhất đồng nhất và liên phí sử dụng bộ nhớ rồi hợp chúng lại nếu thông. và tính toán. thỏa mãn tiêu chuẩn - Có một số - Gặp khó khăn nhƣ cùng màu, cùng thuật giải có tốc độ trong việc thu thập Tăng mức xám để đƣợc thực thi khá nhanh. tập các điểm mầm và trƣởng một miền đồng nhất xác định các điều vùng lớn hơn. kiện đồng nhất đầy đủ. - Chịu ảnh hƣởng bởi các đặc tính tự nhiên của kỹ thuật này. - Phát hiện biên - Thể hiện tốt - Một vài thuật giữa hai vùng của ảnh không gian ảnh bằng giải mất khá nhiều bằng cách so sánh sự đồ thị. thời gian thực hiện. khác nhau giữa nội - Một số thuật - Các đặc trƣng vùng với sự Lý thuyết toán có tốc độ thực cục bộ đôi khi đƣợc đồ thị - Phân đoạn dựa hiện nhanh. sử dụng nhiều hơn vào đồ thị tuân theo các đặc trƣng toàn chiến lƣợc tham lam, cục. có thời gian chạy gần nhƣ tuyến tính, nhƣng vẫn đảm bảo đƣợc Lê Thị Ngọc Mai – CT1101
  22. 22 việc phân đoạn chính xác và hiệu quả. - - Mức độ song - Màu sắc có thể song hoá cao và có tốc làm tăng độ phức tạp độ thực thi nhanh. của mạng. - Khả năng - Quá trình học Mạng chống chịu tốt trƣớc cần phải biết trƣớc số neural các thay đổi xấu. lƣợng các phân - Một công cụ lớp/cụm. hữu hiệu cho các ứng dụng nhận dạng và xử lý ảnh y khoa. - - Là phƣơng - Khó khăn pháp đƣợc hỗ trợ trong việc định nghĩa mạnh bởi các toán tử một hàm gradient cho dò biên. các ảnh màu. Dựa trên - Có hiệu năng - Nhiễu hoặc cạnh tốt với các ứng dụng các ảnh có độ tƣơng dò biên đối tƣợng theo phản kém ảnh hƣởng đƣờng cong. xấu đến kết quả phân vùng. Mô hình vật lý - Khẳng định - Bị giới hạn tính chắc chắn đối với vào một số lƣợng các vùng bóng nhất định các loại vật sáng/tối, và vùng chất hình thành nên bóng chuyển tiếp đối tƣợng. (diffuse hoặc shade) - Khó khăn - Phân vùng các trong việc xác định đối tƣợng dựa vào vùng bóng sáng và thành phần vật liệu bóng chuyển tiếp cấu tạo trong các ảnh thực. Lê Thị Ngọc Mai – CT1101
  23. 23 - Một vài giải thuật đòi hỏi các thông tin về hình dạng đối tƣợng (không luôn luôn đáp ứng đƣợc). - Chi phí tính toán khá cao. 2.4 Một số thuật toán phân đoạn ảnh 2.4.1 Thuật toán Entropy cực đại  Tiến trình giải thuật - Chia ảnh làm 2 vùng w0, w1 Trong đó: w0 = { | ≤ } W1 = { | > } - Tìm Entropy của 2 vùng Entropy (w0) = -  p0i log2 p0i Entropy (w1) = -  p1i log2 p1i Trong đó: p0i là xác suất điểm ảnh rơi vào vùng w0 p1i là xác suất điểm ảnh rơi vào vùng w1 p0i = i ≤  p1i = i >  Với: h(i) là giá trị histogram của mức xám i T(wi) là tổng số điểm ảnh trong vùng wi. - Tìm  sao cho : Entropy (w0) + Entropy(w1) cực đại =>  là ngƣỡng cần tìm Lê Thị Ngọc Mai – CT1101
  24. 24  Cài đặt chương trình - Thực hiện phân ngƣỡng theo thuật toán Entropy cực đại trên từng màu R, G, B. Sau khi phân đoạn đƣa ra biểu đồ histogram của từng màu và ngƣỡng của nó. - Input: Ảnh cần phân đoạn. Output: Ảnh đã đƣợc phân đoạn, biểu đồ histogram và ngƣỡng. void CImageSegmentationDoc::OnRunEntropy() { CImageSegmentationDoc *pDoc = pImageSegmentationDoc;// CDC dcMem; BITMAP bm; pDoc->m_bmBitmap.GetBitmap(&bm); RGBQUAD *pRGB = new RGBQUAD[256]; dcMem.CreateCompatibleDC(NULL); dcMem.SelectObject(pDoc->m_bmBitmap); ::GetDIBColorTable(dcMem,0,256,pRGB ); BYTE* p = new BYTE[bm.bmWidth*bm.bmHeight]; pDoc->m_bmBitmap.GetBitmapBits(bm.bmWidth*bm.bmHeight,p); int nguong=min+1; int maxnguong=0; double maxe=0; double tw0=0,tw1=0; double entropyw0=0,entropyw1=0,entropy=0; double p1[256]; int h,w; int i,j; Lê Thị Ngọc Mai – CT1101
  25. 25 h=bm.bmHeight; w=bm.bmWidth; while(nguong<max) { entropyw0=entropyw1=entropy=0; for(i=min;i<nguong;i++) tw0+=Histo[i]; for(j=nguong;j<=max;j++) tw1+=Histo[j]; for(i=min;i<=max;i++) { if(i<nguong) p1[i]=(double)(Histo[i]/tw0); else p1[i]=(double)(Histo[i]/tw1); } for(i=min;i<=max;i++) { if(i<nguong) { entropyw0+=p1[i]*log2(p1[i]); } else { entropyw1+=p1[i]*log2(p1[i]); } } entropy=-(entropyw0)-(entropyw1); Lê Thị Ngọc Mai – CT1101
  26. 26 // tim entropy max if(nguong==min+1) { maxe=entropy; maxnguong=nguong; } if(entropy>maxe) { maxe=entropy; maxnguong=nguong; } nguong++; } nguong=maxnguong; // hieu chinh anh for(i=0;i nguong) vtri=255; else vtri=0; p[i*w+j]=(BYTE)vtri; } ::SetDIBColorTable(dcMem,0,255,pRGB); pDoc->m_bmBitmap.SetBitmapBits(bm.bmWidth*bm.bmHeight,p); Lê Thị Ngọc Mai – CT1101
  27. 27 pDoc->UpdateAllViews(NULL); }  Một số kết quả a) b) c) d) e) Lê Thị Ngọc Mai – CT1101
  28. 28 f) g) h) i) k) Hình 2.1. Phân đoạn theo thuật toán Entropy cực đại a) và f). Ảnh gốc. b) và g). Ảnh sau khi phân đoạn. c), d), e), h), i), k) là biểu đồ histogram và ngƣỡng của các ảnh đƣợc phân đoạn (vạch đen là ngƣỡng). Lê Thị Ngọc Mai – CT1101
  29. 29 2.4.2 Thuật toán độ lệch nhỏ nhất  Tiến trình giải thuật - Chia ảnh thành 2 vùng w0, w1 nhƣ thuật toán Entropy cực đại - Tính độ lệch chuẩn 2 σ0 = 2 σ1 = Trong đó: là giá trị histogram của mức xám i. là lực lƣợng vùng w0. là lực lƣợng vùng w1. - Tìm  sao cho: 2 2 σ0 + σ1 đạt giá trị cực tiểu, khi đó  là ngƣỡng cần tìm  Cài đặt chương trình - Thực hiện phân ngƣỡng theo thuật toán độ lệch nhỏ nhất trên từng màu R, G, B. Sau khi phân đoạn đƣa ra biểu đồ histogram của từng màu và ngƣỡng của nó. - Input: Ảnh cần phân đoạn. Output: Ảnh đã phân đoạn, biểu đồ histogram và ngƣỡng. void CImageSegmentationDoc::OnRunDolech() { CImageSegmentationDoc *pDoc = pImageSegmentationDoc;// CDC dcMem; BITMAP bm; pDoc->m_bmBitmap.GetBitmap(&bm); RGBQUAD *pRGB = new RGBQUAD[256]; Lê Thị Ngọc Mai – CT1101
  30. 30 dcMem.CreateCompatibleDC(NULL); dcMem.SelectObject(pDoc->m_bmBitmap); ::GetDIBColorTable(dcMem,0,256,pRGB ); BYTE* p = new BYTE[bm.bmWidth*bm.bmHeight]; pDoc->m_bmBitmap.GetBitmapBits(bm.bmWidth*bm.bmHeight,p); int nguong=min+1; int minl=0; int minnguong=0; double hw0=0,hw1=0; double dolechw0=0,dolechw1=0,dolech=0; int w1=0,w0=0; double hw[256]; int h,w; int i,j; h=bm.bmHeight; w=bm.bmWidth; while(nguong<max) { dolechw0=dolechw1=dolech=w1=w0=0; for(i=min;i<nguong;i++) { hw0+=Histo[i]; w0++; } for(j=nguong;j<=max;j++) Lê Thị Ngọc Mai – CT1101
  31. 31 { hw1+=Histo[i]; w1++; } hw0=hw0/w0; hw1=hw1/w1; for(i=min;i<=max;i++) { if(i<nguong)hw[i]=(double)((Histo[i]-hw0)*(Histo[i]-hw0)); else hw[i]=(double)((Histo[i]-hw1)*(Histo[i]-hw1)); } for(i=min;i<=max;i++) { if(i<nguong) dolechw0+=hw[i]; else dolechw1+=hw[i]; } dolechw0=dolechw0/w0; dolechw1=dolechw1/w1; dolech=dolechw0+dolechw1; // tim do lech min if(dolech<minl) { minnguong=nguong; minl=(int)dolech; } nguong++; } nguong=minnguong; Lê Thị Ngọc Mai – CT1101
  32. 32 for(i=0;i nguong) vtri=255; else vtri=0; p[i*w+j]=(BYTE)vtri; } ::SetDIBColorTable(dcMem,0,255,pRGB); pDoc->m_bmBitmap.SetBitmapBits(bm.bmWidth*bm.bmHeight,p); pDoc->UpdateAllViews(NULL); } Lê Thị Ngọc Mai – CT1101
  33. 33  Một số kết quả a) b) c) d) e) Lê Thị Ngọc Mai – CT1101
  34. 34 f) g) h) i) k) Hình 2.2. Phân đoạn theo thuật toán độ lệch nhỏ nhất. a) và f). Ảnh gốc. b) và g). Ảnh sau khi phân đoạn. c), d), e), h), i), k) là biểu đồ histogram và ngƣỡng của các ảnh đƣợc phân đoạn (vạch đen là ngƣỡng). Lê Thị Ngọc Mai – CT1101
  35. 35  Đánh giá hai thuật toán: - Thuật toán đơn giản, cài đặt dễ dàng, thời gian tính toán nhanh. - Tuy nhiên, cũng nhƣ nhƣợc điểm của hầu hết các phƣơng pháp phân đoạn dựa trên biểu đồ histogram là không quan tâm tới vị trí điểm ảnh trong không gian, dễ bị ảnh hƣởng bởi nhiễu. Lê Thị Ngọc Mai – CT1101
  36. 36 CHƢƠNG 3: PHƢƠNG PHÁP CỰC TIỂU NĂNG LƢỢNG DỰA TRÊN ĐỘ ĐỒNG NHẤT VÀ ĐỘ KHÔNG ỔN ĐỊNH CHO PHÂN ĐOẠN ẢNH Hầu hết các phương pháp phân đoạn ảnh hiện nay dựa vào histogram, do đó, không khai thác được thông tin tạo bởi cường độ của ảnh. Ở đây, em xin giới thiệu một phương pháp tối ưu ngưỡng và gradient mới bằng cách tổ chức cường độ thành các đối tượng khác nhau của một ảnh, đó là phương pháp cực tiểu năng lượng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh. 3.1 Giới thiệu Phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh dựa trên độ không ổn định của lớp đối tƣợng và đặc trƣng của histogram để xây dựng nên một hàm năng lƣợng cho gradient cùng đặc trƣng của của đối tƣợng và hình khối trong một ảnh nhất định. Cuối cùng hàm năng lƣợng này đƣợc sử dụng để xác định một ngƣỡng và gradient tối ƣu. Phƣơng pháp mới đồng thời xác định giá trị tối ƣu cho cả ngƣỡng và gradient của đối tƣợng khác nhau 3.1.1 Cơ sở lý thuyết Cơ sở lý thuyết cho phƣơng pháp này là các đối tƣợng đƣợc biểu diễn có biên mờ (fuzzy boundaries) trong hình ảnh thu đƣợc và trong cảm nhận bằng giác quan, cƣờng độ có độ không ổn định cao kết hợp với biên ảnh thông thƣờng sẽ cho biết đƣợc đối tƣợng. 3.1.2 Tối ƣu và tự động ngƣỡng Thông thƣờng, ngƣỡng tối ƣu cùng với chọn gradient là các vấn đề khó khăn trong cách tiếp cận phân đoạn nâng cao hoặc ít nhất là hƣớng tới phƣơng pháp tự động. Tự động lựa chọn một ngƣỡng chắc chắn và chính xác vẫn là một thách thức trong ảnh phân đoạn. Nhiều phƣơng pháp lựa chọn ngƣỡng tự động đã đƣợc báo cáo trong năm thập kỷ qua. Tuy nhiên, thiếu sót phổ biến của các cách tiếp cận là hoàn toàn dựa trên histogram mà không sử dụng đến số lƣợng đáng kể các thông tin nhúng trong các phân bố không gian của cƣờng độ và hình thái trong ảnh. Thông thƣờng, không thể cho một ngƣời quan sát để chọn ngƣỡng cho một ảnh chỉ từ histogram của nó mà không thấy hình ảnh gốc. Mặt khác, ảnh chỉ chứa các phân vùng rõ ràng về đối tƣợng khác nhau thì việc chọn ngƣỡng là quá dễ dàng. Chính vì thế, phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định sử dụng trực tiếp các hiển thị đƣợc tạo ra trên ảnh của đối tƣợng. Lê Thị Ngọc Mai – CT1101
  37. 37 3.2 Lý thuyết 3.2.1 Cƣờng độ dựa trên độ không ổn định Ảnh số đƣợc biểu diễn bởi công thức: = (C, ) Trong đó: C: xác đị nh miền ảnh |C [IMIN,IMAX] với IMIN và IMAX biểu thị cƣờng độ nhỏ nhất và lớn nhất. C thể hiện các điểm với tọa độ tách rời thuộc bên trong một hình hộp chữ nhật. Một phần tử của C, thƣờng ký hiệu là một vectơ p, q hoặc r đƣợc gọi là một pixel 2 chiều (2D), một voxel trong không gian ba chiều (3D) và spel một trong không gian n chiều. Cho Fo  C và FB  C là các đối tƣợng giả định thực và lớp nền, tƣơng ứng trong ảnh . Cho o( ) biểu thị một xác suất tiêu nghiệm mà một đối tƣợng pixel có giá trị cƣờng độ . Ta có: o( ) = P((p)= | p  Fo) (3.1) Khi đó, P là xác suất. Tƣơng tự cho xác suất tiêu nghiệm B( ) cho nền pixel có giá trị cƣờng độ . B( ) = P((p)= | p  FB) (3.2) Gọi  là xác suất của pixel thuộc lớp đối tƣợng Fo, độc lập với cƣờng độ của một pixel, sao cho (1 - ) là xác suất của pixel các thuộc lớp nền FB. Theo đó,  đƣợc gọi là hàm mật độ. Vì vậy, xác suất mà pixel bất kỳ có giá trị cƣờng độ , thể hiện bởi ( ), đƣợc tính nhƣ sau: ( ) =  o( ) + (1 - ) B( ) (3.3) Sử dụng các phƣơng trình trên, ta có xác suất hậu nghiệm mà một pixel với giá trị cƣờng độ , thuộc lớp đối tƣợng đƣợc xác định bằng cách sử dụng quy tắc Bayes [3]. P(p F0 | (p)= ) = (3.4) Tƣơng tự, ta có xác suất hậu nghiệm mà một pixel với giá trị cƣờng độ thuộc lớp nền đƣợc cho bởi công thức: P(p FB | (p)= ) = (3.5) Lê Thị Ngọc Mai – CT1101
  38. 38 Thƣớc đo độ không ổn định để phân loại một pixel p C với giá trị cƣờng độ thuộc đối tƣợng hay lớp nền là entropy của hai giá trị xác suất hậu nghiệm nhƣ quy định tại phƣơng trình (3.4) và (3.5). Biện pháp này đƣợc gọi là độ không ổn định và đƣợc ƣớc tính theo phƣơng trình entropy của Shannon và Weaver [4] nhƣ sau: ℎ( ) = - log - log (3.6) Ở đây, ý tƣởng này là để mô hình một phân bố xác suất tiên nghiệm o( ) và B( ) và hàm mật độ  nhƣ là một hàm chọn ngƣỡng và tham số gradient σ. Nhƣ vậy, bản đồ độ không ổn định của ảnh thay đổi nhƣ một hàm của ngƣỡng và tham số gradient σ, và chúng ta sử dụng ℎ ,σ( ) | [IMIN, IMAX] để biểu diễn ngưỡng và gradient phụ thuộc hàm độ không ổn đị nh. Các phƣơng pháp tính toán phân bố xác suất tiên nghiệm o( ) và B( ) và hàm mật độ  nhƣ một hàm chọn các ngƣỡng và tham số gradient σ được giới thiệu trong phần sau. 3.2.2 Bề mặt năng lƣợng và tối ƣu ngƣỡng Từ phƣơng trình (3.6), ta có phạm vi tính toán của phƣơng pháp độ không ổn định là [0, 1]. Do đó ta cần chuẩn hóa tham số gradient σ và có thể thay đổi. Ở đây, ta sử dụng mô hình Gauss để tìm ∇σ chuẩn của cường độ gradient: ∇σ(p) = (3.7) Trong đó, ∇ là toán tử cường độ gradient và ∇σ là toán tử gradient chuẩn. Lưu ý, đầu ra của toán tử ∇ phụ thuộc vào phạm vi cường độ ảnh, trong khi hiệu suất ∇σ phụ thuộc vào đánh giá gradient trong phạm vi chuẩn hóa [0,1]. Cuối cùng hàm năng lượng E được tính như sau: E( ,σ) = (3.8) Theo phƣơng trình trên, mỗi pixel p tham gia vào năng lƣợng theo 2 cách - Độ không ổn đị nh cao và gradient thấp - Độ không ổn đị nh thấp và gradient cao 3.3 Phƣơng pháp Nhƣ giới thiệu ở phần trên, E là hàm năng lƣợng biến thiên theo hai thông số là ngƣỡng và gradient σ. Hai thông số này biểu diễn bề mặt năng lƣợng cho hàm E, đồng thời hàm E giúp tối ƣu hai thông số này trên bề mặt năng lƣợng. Để triển Lê Thị Ngọc Mai – CT1101
  39. 39 khai một thuật toán tối ƣu dựa trên ngƣỡng và gradient σ, ta cần thực hiện các bƣớc sau: Cho trƣớc các giá trị ngƣỡng và gradient σ, chúng ta cần tính: - Phân bố xác suất tiên nghiệm đối tƣợng o( )và nền B( ). - Hàm mật độ  - Bản đồ gradient chuẩn ∇σ. - Tối ƣu giá trị của và σ trên bề mặt năng lƣợng E. Trong các phần sau, em xin giới thiệu phƣơng pháp để hoàn thành các nhiệm vụ trên. Ban đầu, ảnh gốc đƣợc làm mờ bằng một hạt nhân Gaussian Blur G(x, y) = (3.9) Điều này nhằm mục đích: - Tăng vùng có độ không chắc chăn và mịn nhiễu trong vùng đồng nhất. - Bản đồ độ không ổn định tăng phù hợp với việc tăng bản đồ gradient do làm mờ. Ta có thể chỉ ra rằng tối ƣu ngƣỡng và gradient đƣợc áp dụng trên những ảnh gốc. Vì vậy, làm mờ đƣợc sử dụng trong quá trình tối ƣu hóa ngƣỡng và gradient mà không có bất kỳ ảnh hƣởng về cấu trúc hay việc làm mờ ở phân đoạn cuối cùng. 3.3.1 Phân bố xác suất tiên nghiệm đối tƣợng o( )và nền B( ) Theo giới thiệu ở trên, với giá trị bất kỳ cho trƣớc của thông số ngƣỡng và gradient σ, ta cũng tính đƣợc đối trƣợng tiên nghiệm và phân phối cƣờng độ nền theo công thức: o( ) (3.10) Và Lê Thị Ngọc Mai – CT1101
  40. 40 B( ) (3.11) 3.3.2 Hàm mật độ  Sau khi làm mờ bằng hạt nhân Gaussian Blur [6], các hàm cường độ f đƣợc thay thế bằng hàm cƣờng độ ảnh mờ fBlur trong khi tính giá trị độ không chắc chắn. Hàm mật độ  đƣợc tính bằng tỉ lệ số pixel của đối tƣợng trên tổng số pixel.  = (3.12) 3.3.3 Bản đồ gradient chuẩn ∇σ Bản đồ gradient chuẩn đƣợc tính theo công thức sau: ∇x(p) = Blur(p + ix) – Blur(p – ix) ∇y(p) = Blur(p + iy) – Blur(p – iy) ∇(p) = Trong đó, ix và iy là 2 vectơ đơn vị theo trục x và trục y. Cuối cùng, bản đồ chuẩn hóa gradient đƣợc tính toán từ cƣờng độ gradient sử dụng phƣơng trình (3.7). 3.3.4 Tối ƣu giá trị của và σ trên bề mặt năng lƣợng E Bây giờ, em xin giới thiệu các phƣơng pháp tối ƣu thông số ngƣỡng và gradient σ. Ở đây, chúng ta áp dụng kỹ thuật tìm kiếm vét cạn. Vì vậy, yếu tố quan trọng nhất ở đây là xác định hình học của các điểm tối ƣu trên bề mặt năng lƣợng. Đối với thông số ngƣỡng , dải cƣờng độ là [IMIN, IMAX], đƣợc sử dụng để tìm kiếm các vị trí tối ƣu. Mặt khác, tìm kiếm không gian cho các tham số gradient σ đƣợc thiết lập trong dải [1% (IMIN – IMAX), 40% (IMIN – IMAX)]. Chúng ta xác định hai vị trí tối ƣu trên bề mặt năng lƣợng (xem hình 3.2): - Vị trí tối ƣu loại I tạo thành hố (pit) trên bề mặt năng lƣợng E. - Vị trí tối ƣu loại II tạo thành thung lũng (valley) có ý nghĩa của một dòng năng lƣợng. Gọi Eσ biểu diễn tham số gradient cố định tại giá trị σ cho trƣớc và tham số ngƣỡng thay đổi, khi đó Eσ tạo thành một đƣờng cong năng lƣợng từ các giá trị tham số gradient σ. Cực tiểu địa phƣơng trên bề mặt năng lƣợng E đƣợc gọi là hố, Lê Thị Ngọc Mai – CT1101
  41. 41 còn cực tiểu của một dòng năng lƣợng Eσ đƣợc gọi là điểm thung lũng. Tùy thuộc vào độ phân giải của không gian tìm kiếm, cả Eσ và E có thể chứa một số lƣợng lớn các cực tiểu nhiễu. Ở đây, em sử dụng ý tƣởng của watershed, một ý tƣởng tƣơng tự nhƣ vực chứa nƣớc sử dụng trong phƣơng pháp phân đoạn watershed, để phân biệt giữa nhiễu và cực tiểu có ý nghĩa. a) b) Hình 3.2. Ví dụ minh họa dòng năng lƣợng và bề mặt năng lƣợng. a) Biểu một dòng năng lƣợng, các vạch đỏ biểu diễn các ngƣỡng tối ƣu hay các hố hợp lệ. b) Biểu diễn bề mặt năng lƣợng, các vạch đỏ là các hố hợp lệ, khoanh tròn đỏ biểu diễn thung lũng ý nghĩa. Gọi ( 1, σ1) biểu thị hố, nghĩa là cực tiểu địa phƣơng trên bề mặt năng lƣợng E. Các watershed của ( 1, σ1) đƣợc biểu diễn bởi B( 1, σ1), là tập hợp tất cả các vị trí ( , σ), nhƣ vậy tồn tại một đƣờng thẳng từ ( , σ) đến ( 1, σ1) và tất cả các điểm có giá trị năng lƣợng lớn hơn hoặc bằng E( 1, σ1). Về cơ bản, B( 1, σ1) tƣơng ứng với các vùng trên E các thể bị ngập bằng cách đổ nƣớc từ trên tại E( 1, σ1), hoặc không có nƣớc bị rò rỉ tại một vị trí có giá trị năng lƣợng ít hơn E( 1, σ1) (xem hình 3.1). Trong hình 3.1, các dòng màu đen biểu thị các dòng năng lƣợng của dải cƣờng độ [IMIN, IMAX] tại giá trị gradient σ0 cho trƣớc, mỗi màu cho thấy mỗi watershed sẽ cho một cựa tiểu địa phƣơng riêng, và độ sâu của vực là khoảng cách từ đỉnh của một màu đến dáy của nó, còn các vực màu đỏ là nhiễu hay các điểm thung lũng không hợp lệ. Một hố (hoặc một điểm thung lũng) đƣợc xem là một hố hợp lệ (tƣơng ứng một thung lũng hợp lệ) nếu chiều cao của B( 1, σ1) (tƣơng ứng Bσ( )) bao gồm ít Lê Thị Ngọc Mai – CT1101
  42. 42 nhất 3% sự biến động tối đa của E (tương ứng Eσ). Ví dụ sự thay đổi lớn nhất của các đường cong năng lượng Eσ là các vực màu xám. Độ sâu của các vực màu đỏ nhỏ dƣới 3% sự biến động tối đa và do đó không đƣợc coi là một thung lũng hợp lệ. Hình 3.1. Minh họa vực bên trong. Mỗi hố hợp lệ đƣợc xác định là một vị trí tối ƣu loại I. Một thung lũng đƣợc định nghĩa là một con đƣờng nối các điểm dọc theo thung lũng hợp lệ tham số gradient và một thung lũng đƣợc coi là ý nghĩa nếu chiều dài của nó bao gồm ít nhất 10% chiều dài tìm kiếm cùng các tham số gradient. Cuối cùng, một điểm tối ƣu loại II đƣợc xác định ở trung tâm của một thung lũng có ý nghĩa. 3.4 Tiến trình giải thuật:  Làm mờ ảnh gốc bởi hạt nhân Gaussian Blur (3.9).  Cho trƣớc một ngƣỡng 0 và gradient σ0. Xác định: - Hàm mật độ  theo phƣơng trình (3.12). - Phân bố xác suất tiên nghiệm của đối tƣợng o( ) theo phƣơng trình (3.10) và của nền B( ) theo phƣơng trình (3.11). - Gradient chuẩn theo phƣơng trình (3.7). - Hàm năng lƣợng E theo phƣơng trình (3.8) với tham số gradient σ thuộc dải cƣờng độ [1% (IMIN – IMAX), 40% (IMIN – IMAX)] và ngƣỡng biến thiên trong dải [IMIN, IMAX].  Xác định các vị trí tối ƣu loại I trên bề mặt năng lƣợng E và loại II của dòng năng lƣợng Eσ. Lê Thị Ngọc Mai – CT1101
  43. 43 Lê Thị Ngọc Mai – CT1101
  44. 44 CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH VÀ ĐÁNH GIÁ 4.1 Cài đặt chƣơng trình 4.1.1 Định dạng ảnh BMP Trong đồ họa máy tính, BMP là một định dạng tệp tin hình ảnh khá phổ biến. Các tệp tin đồ họa lƣu dƣới dạng BMP thƣờng có đuôi là .bmp (hình 4.1) hoặc .dib Hình 4.1. Ảnh lƣu dƣới dạng BMP đuôi .bmp Các thuộc tính tiêu biểu của một tệp tin ảnh BMP (cũng nhƣ file ảnh nói chung) là:  Số pixel trên mỗi điểm ảnh, thƣờng đƣợc ký hiệu là n. Một ảnh BMP n-bit có 2n màu. Giá trị n càng lớn thì ảnh càng có nhiều màu và càng rõ nét hơn. Giá trị tiêu biểu của n là 1 (ảnh đen trắng), 4 (ảnh 16 màu), 8 (ảnh 256 màu), 16 (ảnh 65536 màu) và 24 (ảnh 16 triệu màu). Ảnh BMP 24-bit có chất lƣợng hình ảnh trung thực nhất.  Chiều cao của ảnh (height), cho bởi điểm ảnh (pixel).  Chiều rộng của ảnh (width), cho bởi điểm ảnh. Cấu trúc một tệp tin ảnh BMP gồm 4 phần:  Bitmap Header (14 bytes): giúp nhận dạng tập tin bitmap. - Lƣu trữ thông tin cơ bản về tệp ảnh. Lê Thị Ngọc Mai – CT1101
  45. 45 - Chứa chữ ký của ảnh có giá trị 0x4D42, cỡ tệp tin, lƣu không, thông tin vùng bitmap infomation (lƣu địa chỉ vùng dữ liệu).  Bitmap Information (40 bytes): lƣu một số thông tin chi tiết giúp hiển thị ảnh nhƣ chiều rộng ảnh, chiều cao ảnh, số màu, kiểu nén, độ phân giải ngang, dọc  Color Palette (4*n bytes), n là số màu của ảnh: định nghĩa các màu sẽ đƣợc sử dụng trong ảnh. - Là mảng một chiều gồm n phần tử. - Mỗi mảng gồm 4 phần tử 1 byte cho R, 1 byte cho G. 1 byte cho B, 1 byte cho cƣờng độ (thƣờng không dùng).  Bitmap Data: lƣu dữ liệu ảnh. - Bố trí thành các dòng scanline. - Lƣu trữ từ dƣới lên. - Đƣợc dùng để XLA. Đặc điểm nổi bật nhất của định dạng BMP là tập tin hình ảnh thƣờng không đƣợc nén bằng bất kỳ thuật toán nào. Khi lƣu ảnh, các điểm ảnh đƣợc ghi trực tiếp vào tập tin - một điểm ảnh sẽ đƣợc mô tả bởi một hay nhiều byte tùy thuộc vào giá trị n của ảnh. Do đó, một hình ảnh lƣu dƣới dạng BMP thƣờng có kích cỡ rất lớn, gấp nhiều lần so với các ảnh đƣợc nén (chẳng hạn GIF, JPEG hay PNG). 4.1.2 Cài đặt thử nghiệm - Giá trị gradient σ biến thiên trong dải [1% (IMIN – IMAX), 40% (IMIN – IMAX)] và với mỗi giá trị gradient σ thì ngƣỡng biến thiên trong dải [IMIN, IMAX]. - Sử dụng các màu khác nhau cho các vùng đối tƣợng khác nhau. - Đƣa ra dòng năng lƣợng tại giá trị gradient σ hợp lệ lớn nhất. void CImageSegmentationDoc::OnRunCuctieu(int ga) { // TODO: Add your command handler code here CDC dcMem; Lê Thị Ngọc Mai – CT1101
  46. 46 BITMAP bm; m_bmBitmap.GetBitmap(&bm); RGBQUAD *pRGB = new RGBQUAD[256]; dcMem.CreateCompatibleDC(NULL); dcMem.SelectObject(m_bmBitmap); ::GetDIBColorTable(dcMem,0,256,pRGB ); BYTE* p = new BYTE[bm.bmWidth*bm.bmHeight]; BYTE* ptg = new BYTE[bm.bmWidth*bm.bmHeight]; m_bmBitmap.SetBitmapBits(bm.bmWidth*bm.bmHeight,pd); m_bmBitmap.GetBitmapBits(bm.bmWidth*bm.bmHeight,p); m_bmBitmap.GetBitmapBits(bm.bmWidth*bm.bmHeight,ptg); int t=min; // nguong bien thien int Thres[256]; // tap nguong int gra=ga; // gradient double he[256]; // Entropy double Po[256],Pb[256],P[256]; // xs tien nghiem va hau nghiem double E[256]; // nang luong int mdS=0,mdo=0; // ham mat do float tt=0.0; int h,w; int i,j,k,l; double e=2.718281828; double* grac = new double[bm.bmWidth*bm.bmHeight]; int dem1=0,dem2=0; h=bm.bmHeight; w=bm.bmWidth; Lê Thị Ngọc Mai – CT1101
  47. 47 for(i=0;i<256;i++) { Thres[i]=vitri[i]=0; he[i]=Po[i]=Pb[i]=P[i]=E[i]=0; } // Lam mo; double kqr,kqg,kqb; BYTE ByteRead; int red,green,blue; UINT r,g,b,th; // Nhan chap for(i=1;i<h;i++) for(j=1;j<w;j++) { kqr=kqg=kqb=0; for(k=-1;k<=1;k++) for(l=-1;l<=1;l++) { ByteRead=p[(i+k)*w+(j+l)]; red=pRGB[ByteRead].rgbRed; green=pRGB[ByteRead].rgbGreen ; blue=pRGB[ByteRead].rgbBlue; kqr+=red; kqg+=green; Lê Thị Ngọc Mai – CT1101
  48. 48 kqb+=blue; } r=BYTE((double)kqr/9+0.5); g=BYTE((double)kqg/9+0.5); b=BYTE((double)kqb/9+0.5); th=::GetNearestPaletteIndex(hPal,RGB(r,g,b)); ptg[i*w+j]=th; } // nguong bien thien tu min -> max for(t=min-1;t (t+1.5*gra)) Po[i]=1; else Po[i]=pow(e,(double)-(i-(t+1.5*gra)*(t+1.5*gra))/(2*gra*gra)); Lê Thị Ngọc Mai – CT1101
  49. 49 if (i<(t-1.5*gra)) Pb[i]=1; else Pb[i]=pow(e,(double)-(i-(t-1.5*gra)*(t-1.5*gra))/(2*gra*gra)); } for(i=min;i<=max;i++) { P[i]=(double)(tt*Po[i]+(1-tt)*Pb[i]); } // Tinh gradient chuan for(i=0;i<h;i++) for(j=0;j<w;j++) { double tg1,tg2,tg; double mu; if(i==0 && j==0) { tg1=ptg[(i+1)*w+j]; tg2=ptg[i*w+(j+1)]; } else if(i==0) { tg1=ptg[(i+1)*w+j]; tg2= (ptg[i*w+(j+1)] - ptg[i*w+(j-1)]); } else if(j==0) { tg1= (ptg[(i-1)*w+j] - ptg[(i+1)*w+j]); tg2=ptg[i*w+(j+1)]; Lê Thị Ngọc Mai – CT1101
  50. 50 } else if(i==(h-1) && j==(w-1)) { tg1=ptg[(i-1)*w+j]; tg2=ptg[i*w+(j-1)]; } else if(i==(h-1)) { tg1=ptg[(i-1)*w+j]; tg2= (ptg[i*w+(j+1)] - ptg[i*w+(j-1)]); } else if(j==(w-1)) { tg1= (p[(i-1)*w+j] - p[(i+1)*w+j]); tg2=p[i*w+(j-1)]; } else { tg1= (p[(i-1)*w+j] - p[(i+1)*w+j]); tg2= (p[i*w+(j+1)] - p[i*w+(j-1)]); } tg=tg1*tg1+tg2*tg2; mu=pow(e,(double)-tg/(2*gra*gra)); grac[i*w+j]=(double)(1-mu); } // pt entropy va nang luong for(i=min;i<=max;i++) Lê Thị Ngọc Mai – CT1101
  51. 51 { double tg1,tg2; tg1=(tt*Po[i])/P[i]; tg2=((1-tt)*Pb[i])/P[i]; he[i]=-tg1*log(tg1)-tg2*log(tg2); } for(i=0;i<h;i++) for(j=0;j<w;j++) { ByteRead=p[i*w+j]; E[t]+=(he[ByteRead]*(1-grac[i*w+j])+(1-he[ByteRead])*grac[i*w+j]); } } // Xac dinh vi tri toi uu loai I, II for(i=min-1;i<max;i++) { if(E[i]<E[i+1] && E[i]!=0) { Thres[dem1]=i; break; } } t=Thres[dem1]; while(t<=max) Lê Thị Ngọc Mai – CT1101
  52. 52 { if(E[t]>E[t+1]) { while(t =0) { for(i=0;i Thres[dem1]) { Lê Thị Ngọc Mai – CT1101
  53. 53 vtri=0; } else if(Thres[dem1]<=vtri && vtri<Thres[dem1+1]) { vtri=254-gtri; vtri-=gtri; } p[i*w+j]=(BYTE)vtri; } dem1 ; } ::SetDIBColorTable(dcMem,0,255,pRGB); m_bmBitmap.SetBitmapBits(bm.bmWidth*bm.bmHeight,p); UpdateAllViews(NULL); } Lê Thị Ngọc Mai – CT1101
  54. 54 4.2 Một số kết quả và đánh giá  Một số kết quả - Hình ảnh phân đoạn ảnh bông hoa với σ [2, 90] và [5, 230]. a) b) c) Hình 4.2. Kết quả phân đoạn ảnh bông hoa và biểu đồ dòng năng lƣợng a) Ảnh gốc. b) Ảnh sau khi phân đoạn. c) Biểu đồ dòng năng lƣợng tại σ = 32, màu đỏ biểu hiện giá trị năng lƣợng của tập ngƣỡng tối ƣu ={7, 31, 40, 61, 67, 121}. Lê Thị Ngọc Mai – CT1101
  55. 55 - Hình ảnh phân đoạn ảnh cô gái với σ [2,96] và [7,247] a) b) c) Hình 4.3. Kết quả phân đoạn ảnh cô gái và biểu đồ dòng năng lƣợng. a) Ảnh gốc. b) Ảnh sau khi phân đoạn. c) Biểu đồ dòng năng lƣợng tại σ = 74, màu đỏ biểu hiện giá trị năng lƣợng của ngƣỡng tối ƣu =9. Lê Thị Ngọc Mai – CT1101
  56. 56  Đánh giá Phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định có thể tự động xác định nhiều hơn một ngƣỡng cần thiết cho một ảnh. Tuy nhiên, thuật toán phức tạp, mất khá nhiều thời gian tính toán. Lê Thị Ngọc Mai – CT1101
  57. 57 KẾT LUẬN Trong quá trình nghiên cứu tài liệu và thực hiện đồ án dƣới sự hƣớng dẫn của PGS TS. Ngô Quốc Tạo – Viện CNTT, Viện KH&CN Việt Nam, em thấy bản thân đã đạt đƣợc một số kết quả nhƣ sau:  Tìm hiểu một cách tổng quan về XLA và phân đoạn ảnh, em đã có một cách nhìn hệ thống về các hƣớng tiếp cận chính trong phân đoạn ảnh và một số thuật toán. Đồng thời biết đƣợc ƣu điểm cũng nhƣ nhƣợc điểm của từng từng hƣớng tiếp cận để có thể đƣa ra cách lựa chọn phù hợp với từng loại ảnh.  Em đã tìm hiểu và cài đặt đƣợc phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định cho phân đoạn ảnh. Phƣơng pháp bề mặt năng lƣợng để tối ƣu đồng thời ngƣỡng và gradient để tăng cƣờng khả năng phân đoạn.  Ngoài ra, trong quá trình nghiên cứu em cũng tự tích lũy thêm cho mình các kiến thức về toán học, về kỹ thuật lập trình, Và quan trọng là rèn luyện kỹ năng để thực hiện một đề tài nghiên cứu khoa học. Bên cạnh những kết quả đạt đƣợc em tự thấy bản đồ án vẫn còn một số hạn chế:  Trong khuôn khổ một đồ án tốt nghiệp ,em mới chỉ trình bày lại các kiến thức tìm hiểu đƣợc chứ chƣa đề xuất đƣợc một phƣơng pháp hoàn toàn mới.  Do thời gian có hạn, nên việc trình bày các thuật toán phân đoạn cũng chƣa đƣợc đầy đủ và khoa học. Dựa trên những kết quả bƣớc đầu đã đạt đƣợc trong đồ án, em có đề xuất một số cải tiến thuật toán phân đoạn để phân đoạn hiệu quả hơn trong tƣơng lai.  Xây dựng một ứng dụng xử lý ảnh hoàn chỉnh dựa theo các thuật toán đã trình bày trong đồ án. Ứng dụng này nhằm phân đoạn ảnh để nhận diện đƣợc các thành phần có trong ảnh. Trích rút ra các đối tƣợng có trong ảnh và đặt tên cho chúng.  Các thuật toán phân đoạn trình bày trong luận văn áp dụng đối với ảnh tĩnh, trong thời gian tới, em hy vọng có thể tìm hiểu và phát triển phƣơng pháp cực tiểu năng lƣợng dựa trên độ đồng nhất và độ không ổn định đối với ảnh động hoặc các đoạn video ngắn. Lê Thị Ngọc Mai – CT1101
  58. 58 TÀI LIỆU THAM KHẢO Tài liệu tiếng việt: [1] TS Đỗ Năng Toàn, “Giáo trình môn học Xử lý ảnh”, Khoa CNTT – Trƣờng đại học Thái nguyên. [2] PGS. TS Nguyễn Quang Hoan, “Xử lý ảnh”, Học viện Bƣu chính viễn thông. [3] “Nhập môn xử lý ảnh”, Đại học bách khoa Hà Nội. Tài liệu tiếng anh: [4] P. K. Saha and J. K Udupa, “A new Optimum Thresholding Method Using Region Homogeneity and Class Unvertainty”, Proc SP1E: Medical Imaging 2000, vol. 3979, phƣơng pháp. 1.80-191, 2000. Website: [5] [6] [7] Lê Thị Ngọc Mai – CT1101