Tài liệu Phương pháp phân đoạn ảnh dựa trên mô hình tách, ghép vùng

1 MỞ ĐẦU Ngày nay, xử lý ảnh đã trở thành một ngành khoa học lớn và có nhiều ứng dụng trong các lĩnh vực: Y tế (xử lý ảnh siêu âm, ảnh chụp cắt lớp), tìm kiếm tội phạm (nhận dạng ảnh tội phạm, dấu vân tay), thị giác máy tính (dùng xử lý ảnh phát hiện đối tượng chuyển động), tra cứu ảnh… Xử lý ảnh nghiên cứu các quá trình xử lý thông tin dạng hình ảnh, mà hình ảnh lại là một trong những dạng thông tin phong phú nhất đối với con người. Quá trình xử lý ảnh bao gồm các bước: thu nhận ảnh, tiền xử lý, phân đoạn ảnh, biểu diễn và mô tả, nhận dạng và nội suy dựa trên cơ sở tri thức. Phân đoạn ảnh là một trong những công việc quan trọng và khó khăn nhất của xử lý ảnh, quyết định sự thành công hay thất bại của toàn bộ công việc phân tích ảnh. Nếu bước phân đoạn ảnh không tốt thì sẽ dẫn đến việc nhận diện sai về các đối tượng trong ảnh. Chính vì vậy phải có những phương pháp phân đoạn ảnh tốt cùng với những kỹ thuật phân tích ảnh phù hợp để quá trình xử lý ảnh đạt hiệu quả tốt nhất. Phân đoạn ảnh là quá trình phân hoạch một ảnh số thành nhiều đoạn (tập các pixel). Mục tiêu của phân đoạn là đơn giản hóa hoặc thay đổi biểu diễn của một ảnh thành biểu diễn có ý nghĩa và dễ phân tích. Phân đoạn ảnh được sử dụng để xác định các đối tượng và các đường biên (đường thẳng, đường cong,...) trong ảnh. Nói cách khác, phân đoạn ảnh là quá trình gán nhãn cho mỗi pixel trong ảnh sao cho các pixel có cùng nhãn có chung các thuộc tính trực quan nào đó. Cho đến nay có nhiều hướng tiếp cận để phân đoạn ảnh, có thể chia thành ba nhóm chính như sau: Dựa trên không gian đặc trưng, dựa trên không gian ảnh, dựa trên các mô hình vật lý. Mỗi hướng tiếp cận có ưu và nhược điểm riêng và phụ thuộc nhiều vào lĩnh vực ứng dụng cụ thể. Do đó, việc Luận văn thạc sĩ Khoa học máy tính 2 nghiên cứu các phương pháp phân đoạn ảnh và tiến hành cài đặt các phương pháp phân đoạn ảnh là rất cần thiết. Vấn đề này chính là động lực để luận văn tìm hiểu các phương pháp phân đoạn ảnh số và ứng dụng trong tra cứu ảnh. Khi người sử dụng cung cấp một ảnh đầu vào (gọi là ảnh truy vấn), hệ thống phân đoạn ảnh truy vấn này thành các vùng và tính toán độ tương tự của ảnh truy vấn và các ảnh trong cơ sở dữ liệu ảnh dựa trên các vùng đã được phân đoạn này. Sau khi tính toán độ tương tự, hệ thống dựa trên độ tương tự của ảnh truy vấn với mỗi ảnh trong cơ sở dữ liệu ảnh để phân hạng các ảnh theo thứ tự giảm dần của độ tương tự. Do đó chất lượng của kỹ thuật phân đoạn sẽ ảnh hưởng rất nhiều đến độ chính xác của hệ thống tra cứu. Luận văn trình bày tổng quan về xử lý ảnh số và các phương pháp phân đoạn ảnh số đi sâu vào phương pháp tách cây tứ phân, tách theo vùng đồng nhất, phương pháp K-means và HAC. Trên cơ sở các phương pháp phân đoạn ảnh này tiến hành xây dựng chương trình phân đoạn ảnh sử dụng ngôn ngữ lập trình C# trên môi trường Visual Studio 2010 và SQL Server 2008. Nội dung luận văn gồm có ba chương: Chương 1: Giới thiệu tổng quan về xử lý ảnh và phân đoạn ảnh. Chương 2: Trình bày phân đoạn ảnh theo mô hình tách, ghép vùng. Chương 3: Chương trình phân đoạn ảnh và ứng dụng phân đoạn ảnh trong tra cứu ảnh. Xử lý ảnh cũng là vấn đề trừu tượng liên quan đến nhiều thuật toán, kỹ thuật xử lý cũng như viết chương trình. Em đã cố gắng hết sức để hoàn thiện luận văn, tuy nhiên do thời gian có hạn nên không thể tránh khỏi những thiếu sót. Em rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo trong Hội đồng chấm luận văn để luận văn được hoàn thiện hơn. Luận văn thạc sĩ Khoa học máy tính 3 CHƯƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ PHÂN ĐOẠN ẢNH 1.1 Tổng quan về xử lý ảnh 1.1.1 Giới thiệu về xử lý ảnh Ngày nay, xử lý ảnh [2] đã trở thành một ngành khoa học lớn và có mặt trong nhiều lĩnh vực của cuộc sống như trong y tế, tìm kiếm tội phạm, khí tượng thủy văn, thị giác máy tính, v.v. Xử lý ảnh là ngành khoa học nghiên cứu các quá trình xử lý thông tin dạng hình ảnh, mà hình ảnh lại là một trong những dạng thông tin phong phú nhất đối với con người. Trong quá trình xử lý ảnh, phân đoạn ảnh là bước quan trọng nhất và cũng là khó khăn nhất. Phân đoạn nhằm mục đích phân tích ảnh thành những thành phần có cùng tính chất nào đó để có thể sử dụng cho các ứng dụng về sau. Các phương pháp xử lý ảnh bắt đầu từ các ứng dụng chính: nâng cao chất lượng ảnh, phân đoạn ảnh và phân tích ảnh. Ứng dụng đầu tiên được biết đến là nâng cao chất lượng ảnh báo được truyền qua cáp từ London đến New York từ những năm 1920. Vấn đề nâng cao chất lượng ảnh có liên quan tới phân bố mức sáng và độ phân giải của ảnh. Việc nâng cao chất lượng ảnh được phát triển vào khoảng những năm 1955. Điều này có thể giải thích được vì sau thế chiến thứ hai, máy tính phát triển nhanh tạo điều kiện cho quá trình xử lý ảnh số thuận lợi. Năm 1964, máy tính đã có khả năng xử lý và nâng cao chất lượng ảnh từ mặt trăng và vệ tinh Ranger 7 của Mỹ bao gồm: làm nổi đường biên, lưu ảnh. Từ năm 1964 đến nay, các phương tiện xử lý, nâng cao chất lượng, phân đoạn ảnh và nhận dạng ảnh phát triển không ngừng. Luận văn thạc sĩ Khoa học máy tính 4 1.1.2 Quá trình xử lý ảnh Quá trình xử lý ảnh được xem như 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ủa một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh vào Xử lý ảnh Ảnh ra (tốt hơn) Kết luận Hình 1.1 Quá trình xử lý ảnh Ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Bởi vì, ảnh có thể xem là tập hợp các điểm ảnh. Trong đó, 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à do đó nó có thể xem như một hàm n biến P(c1,c2,...,cn). Quá trình xử lý ảnh [2] có thể được mô tả bằng sơ đồ sau: Biểu diễn và mô tả ảnh Phân đoạn Tiền xử lý ảnh CƠ SỞ TRI THỨC Nhận dạng và nội suy Thu nhận Hình 1.2 Quá trình xử lý ảnh  Thu nhận ảnh: Đây là bước đầu tiên của quá trình xử lý ảnh song kết quả của nó có ảnh hưởng rất nhiều đến các bước kế tiếp. Đầu tiên, ảnh tự nhiên từ thế giới ngoài được thu nhận qua các thiết bị thu như Luận văn thạc sĩ Khoa học máy tính 5 camera, máy chụp ảnh, v.v. Trước đây, ảnh thu nhận qua camera là tín hiệu tương tự (loại camera ống kiểu CCIR). Gần đây, với sự phát triển của công nghệ, ảnh màu hoặc đen trắng được lấy ra từ camera, sau đó nó được chuyển trực tiếp thành ảnh số tạo thuận lợi cho xử lý tiếp theo. Mặt khác, ảnh cũng có thể tiếp nhận từ vệ tinh qua các bộ cảm ứng hay ảnh, tranh được quét trên máy quét ảnh (scanner).  Tiền xử lý: Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khôi phục ảnh, nắn chỉnh hình học, v.v. Với mục đích làm cho chất lượng ảnh trở nên tốt hơn nữa, chuẩn bị cho các bước xử lý phức tạp kế tiếp sau đó. * Khử nhiễu: Nhiễu được chia thành hai loại: nhiễu hệ thống và nhiễu ngẫu nhiên. Đặc trưng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này bằng việc sử dụng phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu ngẫu nhiên, trường hợp đơn giản là các vết bẩn tương ứng với các điểm sáng hay tối, có thể khử bằng phương pháp nội suy, lọc trung vị và trung bình. * Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng đều của thiết bị thu nhận hoặc độ tương phản giữa các vùng ảnh. * Chỉnh tán xạ: Ảnh thu nhận được từ các thiết bị quang học hay điện tử có thể bị mờ, nhoè. Phương pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm tán xạ cho phép giải quyết việc hiệu chỉnh này. * Nắn chỉnh hình học: những biến dạng hình học thường do các thiết bị điện tử và quang học gây ra. Do đó, phương pháp hiệu chỉnh ảnh dựa trên mô hình được mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f(x',y') như sau: Luận văn thạc sĩ Khoa học máy tính 6  x'  hx ( x, y)   y '  hy ( x , y ) Trong đó hx, hy là các phương trình tuyến tính (biến dạng do phối cảnh) hay bậc hai (biến dạng do ống kính camera).  Phân đoạn ảnh: Phân đoạn ảnh là bước then chốt trong xử lý ảnh, giai đoạn này nhằm phân tích ảnh thành những thành phần có cùng tính chất nào đó, dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là cùng màu, cùng mức xám hay cùng độ nhám, v.v. Mục đích của phân đoạn ảnh là để có một miêu tả tổng hợp từ nhiều phần tử khác nhau cấu tạo nên ảnh thô. Vì lượng thông tin chứa trong ảnh rất lớn, trong khi đó trong đa số các ứng dụng chúng ta chỉ cần trích chọn một vài đặc trưng nào đó, do vậy cần có một quá trình để giảm lượng thông tin khổng lồ ấy. Quá trình này bao gồm phân vùng ảnh và trích chọn đặc tính chủ yếu.  Biểu diễn và mô tả ảnh: Ả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 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. Một số phương pháp biểu diễn thường dùng: o Biểu diễn bằng mã chạy (Run-Length Code). o Biểu diễn bằng mã xích (Chaine Code). Luận văn thạc sĩ Khoa học máy tính 7 o Biểu diễn bằng mã tứ phân (Quad-Tree Code).  Nhận dạng và nội suy: Đây là bước cuối cùng trong quá trình xử lý ảnh. 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. Có 2 kiểu nhận dạng ảnh 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ự (chữ in, chữ viết tay, chữ ký điện 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 mặt người, v.v. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Cơ sở tri thức: Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng điểm ảnh, v.v. 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 mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh 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ác cơ sở tri thức được phát huy. Không phải bất kỳ một ứng dụng xử lý ảnh nào cũng bắt buộc phải tuân theo các bước xử lý đã nêu ở trên, ví dụ như các ứng dụng chỉnh sửa ảnh nghệ thuật chỉ dừng lại ở bước tiền xử lý. Một cách tổng quát thì những chức năng xử lý bao gồm cả nhận dạng và nội suy thường chỉ có mặt trong hệ thống phân tích ảnh tự động hoặc bán tự động, được dùng để rút trích ra những thông tin quan trọng từ ảnh, ví dụ như các ứng dụng nhận dạng kí tự quang học, nhận dạng chữ viết tay, v.v. 1.1.3 Một số khái niệm cơ bản 1.1.3.1 Điểm ảnh - Pixel Luận văn thạc sĩ Khoa học máy tính 8 Ảnh trong thực tế [1] 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, ảnhcần phải được số hoá. Số hoá ảnh là sự 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á thành phần giá trị mà về nguyên tắc bằng mắt thường không phân biệt được hai điểm kề nhau. Trong quá trình này người ta sử dụng khái niệm Picture element mà ta quen gọi là Pixel - phần tử ảnh. Ảnh được xem như là tập hợp hữu hạn các điểm ảnh, thường được biểu diễn bằng một mảng hai chiều I(n,m) với n là số hàng, m là số cột. Ta ký hiệu P(x,y) – 1 phần tử trong ma trận là một điểm ảnh tại vị trí (x,y). 1.1.3.2 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,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. 1.1.3.3 Biên Luận văn thạc sĩ Khoa học máy tính 9 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 gọi là biên hay còn gọi là đường bao ảnh. 1.1.3.4 Láng giềng Trong xử lý ảnh 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. - 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)} Trong hình 1.3 các điểm P0, P2, P4, P6 là các 4-láng giềềng của P. P2(x,y-1) P4(x-1,y) P(x,y) P0(x+1,y) P6(x,y+1) Hình 1.3 Khái niệm 4-láng giềng - 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)} Trong hình 1.4 các điểm P0, P1, P2, P3, P4, P5, P6, P7 là các 8-láng giềng của P. P3(x-1,y-1) P2(x,y-1) P1(x+1,y-1) P4(x-1,y) P(x,y) P0(x+1,y) P5(x-1,y+1) P6(x,y+1) P7(x+1,y+1) Hình 1.4 Khái niệm 8-láng giềng 1.1.3.5 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 (x A,yA) và (xB,yB) thuộc vào R có thể được nối bởi một đường (x A,yB) ... (xi-1,yi-1), (xi,yi), Luận văn thạc sĩ Khoa học máy tính 10 (xi+1,yi+1) ... (xB,yB), mà các điểm (xi,yi) thuộc vào R và bất kỳ điểm (x i,yi) nào đều kề sát với điểm trước (x i-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 (x l,yl) nếu (xl,yl) thuộc vào láng giềng trực tiếp của (xk,yk). 1.1.3.6 Vùng ảnh (Segment) Vùng ảnh là một chi tiết, một thực thể trong toàn cảnh. Nó là một tập hợp các điểm 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.v. Vùng ảnh là một trong hai thuộc tính quan trọng của ảnh. 1.1.3.7 Đối tượng ảnh Quan hệ k-liên thông [3] trong E (k=4,8) là một quan hệ phản xạ, đối xứng và bắc cầu. Bởi vậy đó là một quan hệ tương đương. Mỗi lớp tương đương được gọi là một thành phần k-liên thông của ảnh. Ta sẽ gọi mỗi thành phần k-liên thông của ảnh là một đối tượng ảnh. 1.1.3.8 Chu tuyến ảnh Chu tuyến của một đối tượng ảnh là dãy các điểm của đối tượng ảnh P1,…,Pn sao cho Pi và Pi+1 là các 8-láng giềng của nhau (i=1,...,n-1) và P1 là 8-láng giềng của Pn, ∀i ∀Q không thuộc đối tượng ảnh và Q là 4-láng giềng của Pi (hay nói cách khác ∀i thì Pi là biên 4). Kí hiệu . Tổng các khoảng cách giữa hai điểm kế tiếp của chu tuyến là độ dài của chu tuyến và kí hiệu Len(C) và hướng PiPi+1 là hướng chẵn nếu Pi và Pi+1 là các 4 – láng giềng (trường hợp còn lại thì PiPi+1 là hướng lẻ). Hình 1.3 dưới đây biểu diễn chu tuyến của ảnh, trong đó, P là điểm khởi đầu chu tuyến. Luận văn thạc sĩ Khoa học máy tính 11 Hình 1.5 Ví dụ về chu tuyến của đối tượng ảnh 1.1.4 Các định dạng cơ bản trong xử lý ảnh Trong quá trình xử lý ảnh [1], một ảnh thu nhận vào máy tính phải được mã hóa. Hình ảnh khi lưu trữ dưới dạng tệp tin sẽ được số hóa. Một số dạng ảnh đã được chuẩn hóa như: Ảnh IMG, PCX, JPEG, TIFF, GIF, … • Ảnh IMG: Là ảnh đen trắng, phần đầu của ảnh có 16 bytes chứa các thông tin cần thiết. Ảnh IMG được nén theo từng dòng. Mỗi dòng bao gồm các gói. Các dòng giống nhau cũng nén thành một gói. • Ảnh PCX : Định dạng ảnh PCX là một trong những định dạng ảnh cổ điển nhất, phần đầu của ảnh có 128 bytes chứa các thông tin cần thiết. nó thường được dùng để lưu trữ ảnh vì thao tác đơn giản, cho phép nén và giải nén nhanh. Quá trình nén và giải nén được thực hiện trên từng dòng ảnh. • Ảnh JPEG: Là định dạng tập tin hầu hết các loại máy ảnh số và phần mềm xử lý ảnh đều hỗ trợ tương thích. JPEG chứa thông tin trung thực của màu sắc: 24 bit cho một điểm (pixel). JPEG là một tiêu chuẩn của kỹ thuật nén ảnh. Tỷ lệ nén có thể đạt tới 10:1 [17] nhưng phải trả giá bằng chất lượng. • Ảnh TIFF: Phần đầu của ảnh có 8 bytes chứa các thông tin cần thiết. Nó là ảnh mà dữ liệu chứa trong tệp thường được tổ chức thành các nhóm dòng ( cột) quét của dữ liệu ảnh. TIFT là lựa chọn cho mục đích lưu trữ ảnh lâu dài tuy nhiên dung lượng cồng kềnh. • Ảnh GIF: Với định dạng ảnh GIF những vướng mắc mà các định dạng khác gặp phải khi số màu trong ảnh tăng lên không còn nữa. Dạng ảnh GIF cho chất lượng cao độ phân giải đồ họa cũng đạt cao, cho phép hiển thị trên hầu hết các phần cứng. Do dung lượng nhỏ gọn nên GIFT là lựa chọn lý tưởng cho các ứng dụng web nhưng không phù hợp để lưu trữ ảnh. Luận văn thạc sĩ Khoa học máy tính 12 1.2 Đặc trưng ảnh 1.2.1 Màu sắc Mắt người rất nhạy cảm với màu sắc và đặc điểm màu là một trong những thành phần quan trọng giúp con người có thể nhận biết được hình ảnh. Vì vậy, đặc điểm màu sắc là đặc điểm cơ bản của nội dung ảnh. Đặc điểm màu sắc có thể cung cấp những thông tin rất hữu hiệu cho việc phân loại ảnh và chúng cũng rất hữu ích cho việc tra cứu ảnh. Cũng vì thế mà tra cứu ảnh dựa trên màu sắc được sử dụng rộng rãi trong các hệ thống tra cứu ảnh dựa trên nội dung. Biểu đồ màu thường được sử dụng để thể hiện những đặc điểm màu của các ảnh. Mặc dù vậy trước khi sử dụng biểu đồ màu chúng ta cần phải lựa chọn và xác định kiểu không gian màu và lựa chọn độ đo tương tự. 1.2.1.1 Không gian màu Không gian màu là sự biểu diễn tập các màu, một số không gian màu được sử dụng rộng rãi trong đồ họa máy tính. Màu sắc thường được xác định trong không gian màu 3 chiều.  Không gian màu RGB Không gian màu RGB là không gian màu được sử dụng nhiều nhất cho đồ hoạ máy tính. Đây là không gian màu cộng: đỏ, xanh lục và xanh lơ được kết hợp lại để tạo ra các màu khác. Không gian này không đồng nhất về nhận thức. Không gian màu RGB có thể được trực quan hoá như một hình khối, như được minh hoạ trong Hình 1.6. Luận văn thạc sĩ Khoa học máy tính 13 Hình 1.6 Không gian màu RGB được trực quan hoá như một hình khối Mỗi trục màu (R, G, B) có độ quan trọng như nhau. Do đó, mỗi trục nên được lượng hoá với cùng một độ chính xác. Khi không gian màu RGB được lượng hoá, số các bin sẽ luôn luôn là một hình khối. Thông thường, 8 (2 3), 64 (43), 216 (63), 512 (83) bin được sử dụng trong lượng hoá không gian màu RGB. Chuyển đổi từ một ảnh RGB sang một ảnh cấp xám nhận được tổng của R, G và B rồi chia kết quả cho ba.  Không gian màu HSx Không gian màu HSI, HSV, HSB và HSL [15] thường được gọi là HSx có mối liên quan gần gũi với sự nhận thức về màu sắc của con người hơn là không gian màu RGB. Những trục từ không gian màu HSx mô tả những đặc tính của màu như sắc độ, độ bão hoà và độ sáng. Sự khác nhau giữa những không gian màu HSx là sự biến đổi của chúng từ không gian màu RGB, chúng thường được mô tả bằng những hình dạng khác nhau (như hình nón, hình trụ). Trong hình 1.7 không gian màu HSV được mô tả như hình nón. Luận văn thạc sĩ Khoa học máy tính 14 Hình 1.7 Mô tả không gian màu HSV Sắc độ là thành phần của không gian màu HSx. Sắc độ là góc giữa những đường tham chiếu và điểm gốc màu trong không gian màu RGB. Vùng giá trị này từ 00 đến 3600. Theo uỷ ban quốc tế về màu sắc CIE thì sắc độ là thuộc tính của cảm giác có liên quan đến thị giác, qua đó một vùng xuất hiện tương tự với một màu được cảm nhận như red, green, blue hoặc là sự kết hợp của hai trong số những màu được cảm nhận. Cũng theo CIE độ bão hoà là màu được đánh giá theo tỷ lệ độ sáng của nó. Trong hình nón độ bão hoà là khoảng cách từ tâm đến cạnh hình nón. Chiều cao của đường cắt chính là giá trị đây chính là độ sáng hoặc độ chói của màu. Khi độ bão hoà S bằng 0 thì H không xác định, giá trị nằm trên trục V biểu diễn ảnh xám. Không gian màu HSV dễ dàng lượng tử hoá. Mức lượng tử hoá thông dụng trong không gian màu này là 162 mức với H nhận 18 mức, S và V nhận 3 mức. Luận văn thạc sĩ Khoa học máy tính 15  Không gian màu YUV và YIQ Các không gian màu YUV và YIQ được phát triển cho truyền hình vô tuyến. Không gian màu YIQ là giống như không gian màu YUV, ở đây mặt phẳng I-Q là một mặt phẳng quay 330 của mặt phẳng U-V. Tín hiệu Y biểu diễn độ chói của một pixel và là kênh duy nhất được sử dụng trong ti vi đen trắng. U và V cho YUV và I và Q cho YIQ là các thành phần màu. Kênh Y được định nghĩa bởi các giá trị năng lượng có trọng số của R(0.299), G(0.587) và B(0.144). Các không gian màu YUV và YIQ không là đồng nhất nhận thức. Khi các không gian màu YUV và YIQ được lượng hoá, mỗi trục được lượng hoá với cùng độ chính xác.  Không gian màu CIE XYZ và LUV Không gian màu [13] được phát triển đầu tiên bởi CIE là không gian màu XYZ. Thành phần Y là thành phần độ chói được định nghĩa bởi tổng trọng số của R(0.212671), G(0.715160), B(0.072169), X và Z là các thành phần màu. Không gian màu CIE LUV là sự biến đổi của không gian màu XYZ. Kênh L là độ chói của màu, kênh U và V là những thành phần màu. Vì vậy khi U và V được đặt bằng 0 thì kênh L biểu diễn ảnh xám. Trong lượng tử hoá không gian màu LUV mỗi trục được lượng tử hoá với mức xác định. Sơ đồ lượng tử hoá thường được sử dụng cho hai không gian màu này là 64, 125, 216 mức. 1.2.1.2 Lược đồ màu Lược đồ màu được xác định bằng một tập các bin, trong đó mỗi bin biểu thị xác suất của các pixel trong ảnh. Một lược đồ màu H của một ảnh đã cho được xác định bởi véc tơ: H={H[0], H[1], H[2], ..., H[i],... H[N]} Luận văn thạc sĩ Khoa học máy tính 16 Ở đây i biểu diễn một màu trong lược đồ màu và tương ứng với một khối con trong không gian màu RGB, H[i] là số các pixel có màu i trong ảnh và N là số các bin trong lược đồ màu. Mỗi pixel trong ảnh sẽ thuộc về một bin của lược đồ màu của ảnh, vì thế với lược đồ màu của một ảnh, giá trị của mỗi bin là số các pixel cùng màu. Để so sánh các ảnh có các kích cỡ khác nhau, các lược đồ màu được chuẩn hóa. Lược đồ màu chuẩn hóa H’ được xác định bằng: H’={H’[0], H’[1], H’[2], ..., H’[i],... H’[N]}, Ở đây H ' [i ]  H [i ] p , P là tổng số các pixel trong ảnh. Trong lược đồ lượng hóa không gian màu lý tưởng, các màu riêng biệt không được định vị trong cùng hình khối con và các màu tương tự được gán vào cùng hình khối con. Sử dụng một số màu sẽ giảm khả năng các màu tương tự được gán vào các bin khác nhau, nhưng cũng tăng khả năng các màu riêng biệt được gán vào cùng các bin, nội dung thông tin của các ảnh sẽ giảm. Mặt khác, các lược đồ màu với một số lượng lớn các bin sẽ chứa nhiều thông tin về nội dung của ảnh, theo đó giảm khả năng các màu riêng biệt sẽ được gán vào cùng các bin. Tuy nhiên, chúng tăng khả năng các màu tương tự sẽ được gán vào các bin khác nhau và tăng không gian lưu trữ biểu diễn ảnh và thời gian tính toán khoảng cách giữa các lược đồ màu. Do đó, cần có sự thỏa hiệp trong việc xác định số lượng các bin sẽ được sử dụng trong các lược đồ màu. 1.2.2 Kết cấu Kết cấu là một mô tả vùng trợ giúp tốt trong quá trình tra cứu. Kết cấu không có khả năng tìm ra các ảnh tương tự, nhưng nó có thể được sử dụng để phân lớp các ảnh kết cấu từ các ảnh không kết cấu và sau đó được kết hợp với các thuộc tính đặc trưng khác như màu để làm cho tra cứu hiệu quả hơn. Một trong những biểu diễn phổ biến nhất của đặc trưng kết cấu là ma trận đồng khả năng được đề xuất bởi Haralick và cộng sự. Ma trận dựa trên hướng và Luận văn thạc sĩ Khoa học máy tính 17 khoảng cách pixel. Các thống kê từ ma trận đồng khả năng được trích rút và được biểu diễn như thông tin kết cấu. Tamura và cộng sự [6] đã đề xuất phương pháp trích rút sáu thuộc tính kết cấu đặc trưng: Độ nhám (coarseness), tương phản (contrast), hướng (directionality), khả năng (likeliness), đều (regularity) và thô (roughness). 1.2.3 Hình dạng Hình dạng được xem như là một đặc trưng quan trọng trong mô tả các đối tượng nổi bật trong ảnh và có thể giúp phân biệt giữa hai ảnh. Bước đầu tiên là sử dụng một phương pháp phân đoạn thích hợp để chia ảnh thành các vùng. Các kỹ thuật phân đoạn có thể được phân lớp thành ba loại: dựa vào vùng, dựa vào đường biên và dựa vào pixel. Sau khi ảnh được phân đoạn và thu được các vùng, các đặc trưng thuộc về các vùng thu được sẽ được ghi lại. Các mã xích sử dụng 4 hoặc 8 liên thông để biểu diễn các đoạn thẳng tạo thành đường biên của vùng. Các dấu hiệu, số các hình và đa giác là các lược đồ biểu diễn khác. Bước tiếp theo là sử dụng các mô tả thích hợp cho các vùng này sao cho chúng có thể được sử dụng trong khi đối sánh các vùng của các ảnh khác nhau. Các mô tả hình được chia thành ba loại: Các mô tả dựa vào đường biên xác định các thuộc tính của đường biên. Các kỹ thuật dựa vào đường biên sử dụng các phác thảo vùng để tính toán hình. Mô tả Fourier là một trong những phương pháp phổ biến thuộc về loại này. Trong kỹ thuật này, đường biên của một vùng đã cho được thu và được biến đổi Fourier. Các hệ số Fourier trội được sử dụng như các mô tả hình. Các mô tả khác trong loại này là các mô men hình. Nếu một vùng có một hình phức hợp, nó có thể được phân tách tiếp thành các hình đơn giản hơn như các hình chữ nhật hoặc các hình tròn và một số thuộc tính của các hình đơn giản này và các quan hệ của chúng có thể được sử Luận văn thạc sĩ Khoa học máy tính 18 dụng cho các mô tả hình. Các mô tả vùng khác gồm màu và kết cấu. Một số đặc tính của vùng như trọng tâm, không cụ thể đối với đường biên hoặc nội dung của vùng. 1.3 Tổng quan về phân đoạn ảnh 1.3.1 Phân đoạn ảnh Phân đoạn ảnh [1] 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 xử lý ảnh, 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, v.v. Ở 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. 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. Luận văn thạc sĩ Khoa học máy tính 19 1.3.2 Một số phương pháp phân đoạn ảnh Để đá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 phân đoạn ảnh 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 các mô hình vật lý. 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 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 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 hoặc xác định các vùng cực trị của histogram. 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 thích nghi k -trung bình - Phương pháp lấy ngưỡng lược đồ. Các phương pháp dựa trên không gian ảnh Luận văn thạc sĩ Khoa học máy tính 20 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 ả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 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ự thuần 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 lược đồ đã 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. 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. 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 Luận văn thạc sĩ Khoa học máy tính