Tài liệu Nghiên cứu kỹ thuật phân đoạn random walker restart

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT&TT .. Vũ Mạnh Cƣờng NGHIÊN CỨU KỸ THUẬT PHÂN ĐOẠN RANDOM WALKER RESTART LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT&TT Vũ Mạnh Cƣờng NGHIÊN CỨU KỸ THUẬT PHÂN ĐOẠN RANDOM WALKER RESTART Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. ĐÀO NAM ANH Thái Nguyên 2 - 2012 LỜI CẢM ƠN Em xin được bày tỏ lòng biết ơn sâu sắc đến thầy TS. Đào Nam Anh – Chủ nhiệm khoa Công nghệ Thông tin Trường Đại học Công nghệ & Quản lý Hữu nghị đã tận tình hướng dẫn, chỉ bảo và đã dành rất nhiều thời gian quí báu của thầy cho em trong thời gian qua, đã giúp em hoàn thành bài luận văn đúng thời hạn của Trường Đại học Công nghệ Thông tin và Truyền thông. Em xin gửi lời cảm ơn đến Ban Giám hiệu, các Thầy cô giáo của Trường Đại học Công nghệ Thông tin và Truyền thông (Đại học Thái Nguyên), Viện Công nghệ Thông tin-Viện Khoa học và Công nghệ Việt Nam, đã giảng dạy cung cấp, trang bị cho chúng em những kiến thức, chuyên ngành, chuyên môn chuyên sâu trong suốt thời gian hai năm qua. Xin cảm ơn gia đình và bạn bè đã động viên cổ vũ em trong suốt quá trình học tập cũng như thời gian làm luận văn, đã giúp em hoàn thành khóa học, luận văn theo qui định. 3 LỜI CAM ĐOAN Tôi xin cam đoan luận văn là kết quả nghiên cứu của tôi, không sao chép của ai. Nội dung luận văn có tham khảo và sử dụng các tài liệu liên quan, các thông tin trong tài liệu được đăng tải trên các tạp chí và các trang website theo danh mục tài liệu của luận văn. Tác giả luận văn Vũ Mạnh Cƣờng 4 MỤC LỤC DANH MỤC CÁC THUẬT NGỮ, CÁC TỪ VIẾT TẮT.................................. i DANH MỤC CÁC BẢNG ..................................................................................iii DANH MỤC KÍ HIỆU........................................................................................iii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................ iv MỞ ĐẦU ............................................................................................................... 1 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH, PHÂN ĐOẠN ẢNH ......... 1 1.1 Các khái niệm cơ bản trong xử lý ảnh, phân đoạn ảnh 1 1.2 Các giai đoạn trong xử lý ảnh 2 1.2.1 Quan hệ giữa các điểm ảnh ................................................................ 8 1.2.2 Độ phân giải ....................................................................................... 9 1.3 Các phép toán cơ bản trên ảnh nhị phân 9 1.4 Một số ứng dụng xử lý ảnh cơ bản 16 1.5 Các hướng tiếp cận trong phân đoạn ảnh 17 1.5.1 Phân đoạn dựa vào ngưỡng .............................................................. 19 1.5.2 Phân đoạn dựa theo đường biên ....................................................... 23 1.5.3 Phân đoạn theo miền đồng nhất ....................................................... 36 CHƢƠNG 2: PHÂN ĐOẠN ẢNH DỰA TRÊN RWR ............................... 42 2.1 Random Walker Restart (RWR) 45 2.2 Phương pháp phân đoạn ảnh dựa trên RWR 49 2.2.1 Xây dựng đồ thị trọng số cho hình ảnh ............................................ 50 2.2.2 Tính xác suất..................................................................................... 51 2.2.3 Gán nhãn để phân đoạn ảnh ............................................................. 53 2.3 Độ phức tạp thuật toán 54 5 CHƢƠNG 3: CÀI ĐẶT THỬ NGHIỆM PHÂN ĐOẠN ẢNH .................. 56 3.1 Môi trường cài đặt 56 3.2 Chương trình thực nghiệm phân đoạn ảnh sử dụng RWR 56 3.2.1 Thiết lập thông số ............................................................................. 57 3.2.2 Kết quả phân đoạn RWR B_LIN với c=10-4 .................................... 58 3.2.3 Một số so sánh .................................................................................. 59 3.3 Kết luận và kiến nghị 63 TÀI LIỆU THAM KHẢO ................................................................................. 64 6 DANH MỤC CÁC THUẬT NGỮ, CÁC TỪ VIẾT TẮT CÁC THUẬT NGỮ Active Contour Đường viền động Blue Màu lam Boundary-Based Methods Phương pháp dựa vào biên Charge Coupled Device Thiết bị tích điện kép Closing Phép đóng Digitalizer Số hóa Dilation Phép dãn Dissimilarity Khác nhau Distance Khoảng cách Erosion Phép co Global Toàn cục Graph Cuts Cắt đồ thị Green Màu lục Grey Màu xám Image Processing Xử lý ảnh Image Recognition Nhận dạng ảnh Intelligent Scissors Kéo thông minh Local Cục bộ Opening Phép mở i Pixel Phần tử ảnh Random Walk Bước đi ngẫu nhiên Random Walk With Return Bước đi ngẫu nhiên với quay lại Red Màu đỏ Region-Based Methods Phương pháp dựa vào miền Scanner Quét ảnh Screen Resolution Độ phân giải màn hình Sensor Cảm ứng Similarity Giống nhau True Color Màu tự nhiên CÁC TỪ VIẾT TẮT CCD Charge Coupled Device DPI Dot per inch GC Graph Cuts PĐA Phân đoạn ảnh RW Random Walk RWR Random Walk With Return XLA Xử lý ảnh ii DANH MỤC CÁC BẢNG Bảng 2-1: B_LIN 48 DANH MỤC KÍ HIỆU Kí hiệu W = [wi,j] ~ W Định nghĩa Đồ thị có trọng số, 1 ≤ i, j ≤ n Ma trận trọng số bình thường liên quan đến W ~ W1 ~ Ma trận phân vùng kết hợp với W ~ ~ W2 Ma trận chéo phân vùng liên quan với W Q Hệ thống ma trận liên quan đến W: Q  I  cW U Ma trận n × t node- khái niệm S Ma trận t × t khái niệm - khái niệm V Ma trận t × n node - khái niệm 0 Ma trận khối có tất cả các thành phần bằng 0  Vector bắt đầu n × 1, phần tử thứ i =1, các phần tử còn lại bằng 0 ei  r i =[ ri, j ] ~ Vector xếp hạng n × 1, ri,j là số điểm liên quan của node j với node i c Xác suất khởi động lại, 0 ≤ c ≤ 1 n Tổng số node trong đồ thị k Số lượng phân vùng m Số lần lắp tối đa ξ1 Ngưỡng dừng quá trình lặp ξ2 Ngưỡng thưa thớt ma trận iii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1-1: Quá trình xử lý ảnh 2 Hình 1-2: Các giai đoạn chính trong xử lý ảnh 2 Hình 1-3: minh họa những thao tác nói trên với giá trị nhị phân “1” có màu đen, còn giá trị nhị phân “0” có màu trắng. 9 Hình 1-4: Các phép toán trên ảnh nhị phân 10 Hình 1-5: Hiệu quả của thao tác nhị phân đơn giản trên một ảnh nhỏ 11 Hình 1-6: Phép co nhị phân 12 Hình 1-7: Phép co nhị phân hình chữ E 12 Hình 1-8: A dãn bởi B 13 Hình 1-9: Sử dụng phép toán mở 15 Hình 1-10: Phép đóng 15 Hình 1-11: Phép đóng và mở 16 Hình 1-12: Ví dụ 1- Phân đoạn giúp xác định khu vực ảnh cần quan tâm 18 Hình 1-13: Ví dụ 2 - Phân đoạn theo cấu trúc. 18 Hình 1-14: Ví dụ 3 - Phân đoạn ảnh chụp viễn thám một vùng biển đảo 18 Hình 1-15: Lược đồ xám 21 Hình 1-16: Thuật toán đối xứng nền 22 Hình 1-17: Thuật toán tam giác 23 Hình 1-18: Đường biên lý tưởng 24 Hình 1-19: Đường biên bậc thang 25 Hình 1-20: Đường biên thực 25 Hình 2-1: Phân đoạn đơn nhãn 44 Hình 2-2: Kết quả phân đoạn 53 Hình 2-3: So sánh độ phức tạp thuật toán 55 iv MỞ ĐẦU Xử lý ảnh (Image Processing) là một trong những mảng quan trọng nhất trong kỹ thuật thị giác máy tính. Xử lý ảnh được ứng dụng trong nhiều lĩnh vực khác nhau như y học, an ninh, quốc phòng. 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. Phân đoạn ảnh có vai trò quan trọng trong việc chiết xuất thông tin từ những hình ảnh và việc khai thác các thông tin hữu ích và các thuộc tính từ hình ảnh. Nếu bước phân đoạn ảnh không tốt thì dẫn đến việc nhận diện sai lầm về các đối tượng có trong ảnh. 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. Hiện nay đã có nhiều thuật toán được đề xuất để giải quyết bài toán phân đoạn ảnh. Các thuật toán trên hầu hết đều dựa vào hai thuộc tính quan trọng của mỗi điểm ảnh so với các điểm lân cận của nó, đó là: sự khác (dissimilarity) và giống nhau (similarity). Các phương pháp dựa trên sự khác nhau của các điểm ảnh được gọi là các phương pháp biên (boundary-based methods), còn các phương pháp dựa trên sự giống nhau của các điểm ảnh được gọi là phương pháp miền (region-based methods). Tuy nhiên, các thuật toán theo cả hai hướng này đều vẫn chưa cho kết quả phân đoạn tốt, vì cả hai loại phương pháp này đều chỉ nắm bắt được các thuộc tính cục bộ (local) của ảnh. Do đó, việc tìm ra các thuật toán nắm bắt được các thuộc tính toàn cục (global) của bức ảnh đã trở thành một xu hướng. 1 Chương 1 của luận văn trình bày tổng quan về xử lý ảnh, các hướng tiếp cận chính trong phân đoạn ảnh. Trong chương 2, luận văn tập trung tìm hiểu và trình bày một phương pháp phân đoạn ảnh dựa trên Random Walker Restart (RWR) - một phương pháp được đánh giá là hiệu quả hơn các phương pháp phân đoạn ảnh trước đây, khắc phục được hai khó khăn quan trọng trong ảnh tự nhiên là bài toán đường biên yếu và kết cấu yếu. Phương pháp RWR dựa vào việc coi một bức ảnh như một đồ thị có trọng số. Sau khi tính xác suất trạng thái ổn định của mỗi điểm ảnh bằng cách sử dụng kỹ thuật phân đoạn ảnh chúng ta có thể ước lượng khả năng phân tách và cuối cùng gán nhãn vào mỗi điểm ảnh. Chương 3 phân tích kết quả thực nghiệm phân đoạn ảnh RWR với các ảnh tự nhiên có đường biên yếu và kết cấu yếu. 2 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH, PHÂN ĐOẠN ẢNH 1.1 Các khái niệm cơ bản trong xử lý ảnh, phân đoạn ảnh Cũng như xử lý dữ liệu bằng đồ hoạ, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này được xem xét như là một cấu trúc dữ liệu và được tạo ra bởi các chương trình. Xử lý ảnh số bao gồm các phương pháp và kỹ thuật để biến đổi, để truyền tải hoặc mã hóa các ảnh tự nhiên [1,2]. Mục đích của xử lý ảnh gồm: - Thứ nhất, biến đổi ảnh và làm đẹp ảnh. - Thứ hai, tự động nhận dạng ảnh hay đoán nhận ảnh và đánh giá các nội dung của ảnh. Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tượng mà người ta muốn đặc tả nó. Quá trình nhận dạng thường đi sau quá trình trích chọn các đặc tính chủ yếu của đối tượng. Có hai kiểu mô tả đối tượng : - Mô tả tham số (nhận dạng theo tham số) - Mô tả theo cấu trúc (nhận dạng theo cấu trúc) Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh thành những phần có nghĩa để phân biệt đối tượng này với đối tượng khác. Dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng biên của một đối tượng trên ảnh, tách cạnh, phân đoạn hình ảnh ... Kỹ thuật này được sử dụng nhiều trong y học (xử lý tế bào, nhiễm sắc thể). Trong thực tế người ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tượng khác nhau như: nhận dạng ảnh vân tay, nhận dạng chữ 1 (chữ cái, chữ số, chữ có dấu). Nhận dạng chữ in hoặc đánh máy trong văn bản phục vụ cho việc tự động hoá quá trình đọc tài liệu, tăng nhanh tốc độ và chất lượng thu nhận thông tin từ máy tính, Nhận dạng chữ viết tay (với mức độ ràng buộc khác nhau về cách viết, kiểu chữ, ...) Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho 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 [1]. Ảnh “tốt hơn” Xử lý ảnh Ảnh Kết luận Hình 1-1: Quá trình xử lý ảnh Ả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ó có thể xem như một hàm n biết P(c1, c2, ...cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh nhiều chiều. 1.2 Các giai đoạn trong xử lý ảnh Quá trình xử lý ảnh có thể được mô tả bằng sơ đồ sau: Phân đoạn ảnh Biểu diễn & Mô tả ảnh Tiền xử lý ảnh Thu nhận ảnh Cơ sở tri thức Nhận dạng & Giải thích Hình 1-2: Các giai đoạn chính trong xử lý ảnh 2 Thu nhận ảnh: Ảnh có thể thu nhận qua camera. Thường ảnh thu nhận qua camera là tín hiệu tương tự (loại camera ống kiểu CCIR), nhưng cũng có thể là tín hiệu số hoá (loại CCD - Charge Coupled Device). Ảnh có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh, tranh được quét qua scanner. Tiền xử lý ảnh: Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khử bóng, khử độ lệch,...với mục đích làm cho chất lượng ảnh trở nên tốt hơn nữa và thường được thực hiện bởi các bộ lọc. Ảnh được số hóa (Digitalizer) để biến đổi tín hiệu tương tự sang tín hiệu rời rạc (lấy mẫu) và số hóa bằng lượng hóa, trước khi chuyển sang giai đoạn xử lý, phân tích hay lưu trữ lại. 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 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... Mục đích của phân đoạn ảnh là để có một miêu tả tổng hợp về 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: Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh, hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó.Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là rất cần thiết. Để chuyển đổi chúng, câu hỏi đầu tiên cần phải trả lời là nên biểu diễn một vùng ảnh dưới dạng biên hay dưới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. 3 Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan tâm chủ yếu đến các đặc trưng hình dạng bên ngoài của đối tượng, ví dụ như các góc cạnh và điểm uốn trên biên chẳng hạn. Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tượng, ví dụ như vân ảnh hoặc cấu trúc xương của nó. Sự chọn lựa cách biểu diễn thích hợp cho một vùng ảnh chỉ mới là một phần trong việc chuyển đổi dữ liệu ảnh thô sang một dạng thích hợp hơn cho các xử lý về sau. Chúng ta còn phải đưa ra một phương pháp mô tả dữ liệu đã được chuyển đổi đó sao cho những tính chất cần quan tâm đến sẽ được làm nổi bật lên, thuận tiện cho việc xử lý chúng. Nhận dạng và giải thích: Đây là bước cuối cùng trong quá trình xử lý ảnh. Nhận dạng ảnh (image recognition) có thể được nhìn nhận một cách đơn giản là việc gán nhãn cho các đối tượng trong ảnh. Giải thích là công đoạn gán nghĩa cho một tập các đối tượng đã được nhận biết. Cơ sở tri thức: Như đã nói ở trên, ả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, môi trường để thu ảnh phong phú. 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. Tri thức được đề cập đến có thể chỉ đơn giản là sự chi tiết hóa các vùng ảnh, nơi được biết trước là sẽ có những thông tin đáng quan tâm để tìm ra lời giải cho bài toán. Ngoài mục đích hướng dẫn cách thức làm việc phù hợp cho mỗi bước xử lý ảnh, nó còn giúp điều khiển mối tương tác giữa các bước xử lý với nhau. Có thể thấy rằng, 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 tất cả các bước xử lý đã nêu ở trên, ví dụ như các ứng 4 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à giải thích 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... 1.1.2 Giới thiệu ảnh nhị phân Như đã giới thiệu ở trên. Trong quá trình xử lý ảnh, một ảnh thu nhập vào máy tính phải được mã hoá. Hình ảnh khi lưu trữ dưới dạng tập tin phải được số hoá. Tiêu chuẩn đặt ra là ảnh phải lưu trữ thế nào sao cho các ứng dụng khác nhau có thể thao tác trên các loại dữ liệu này. Hiện nay có trên 30 kiểu lưu trữ ảnh khác nhau, trong đó ta thường gặp các dạng ảnh sau: TIFF, GIF, BMP, PCX, JPEG, ... Nói chung mỗi kiểu lưu ảnh có ưu điểm riêng. Ả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 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á 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ư vậy, một ảnh là một tập hợp các Pixel [1]. Điểm ảnh là những thành tố tạo nên ảnh. Trên màn hình máy tính chúng là những điểm sáng li ti tạo ra bức ảnh để có thể nhìn thấy được. Để có thể thấy được các điểm sáng này phải dùng kính hiển vi phóng lớn chúng lên. Khi đó sẽ thấy các ô nhỏ hình vuông. Ví dụ một bàn cờ gồm 8 ô vuông hàng ngang và 8 ô vuông cột đứng, giả sử mỗi ô tượng trưng cho 1 pixel. Vậy bàn cờ có 8x8 =64 ô vuông hay 64 pixels. Nếu 64 ô vuông này tạo nên một bức ảnh có chiều cao là 1 inch và chiều ngang là 1 inch, chúng ta gọi bức ảnh đó 5 là 8dpi (dot per inch) image. Cách tính trong một ảnh có kích thước 4in x6 in với 300 dpi có bao nhiêu pixels: (4in x 300) x (6in x 300) = 2,160,000 pixels. Các điểm ảnh được sắp xếp gọn gàng thành cột vào hàng. Số pixel phân bổ trên cột đứng và hàng ngang màn hình được định nghĩa là Độ phân giải màn hình-Screen Resolution. Khi nói một màn hình có độ phân giải 1024x768 pixels tức là màn hình có 1024 cột điểm ảnh và 768 hàng điểm ảnh. Độ phân giải càng cao, ảnh càng nổi bật và đẹp hơn. Tuy nhiên, đối tượng trên màn hình có khuynh hướng co lại khi tăng độ phân giải. Độ phân giải và điểm ảnh là rất quan trọng trong xử lý ảnh kỹ thuật số. Mức xám của ảnh Nếu dùng 8 bít (1 byte) để biểu diễn mức xám thì số các mức xám có thể biểu diễn được là 28 hay 256. Mỗi mức xám được biểu diễn dưới dạng là một số nguyên nằm trong khoảng từ 0 đến 255, với mức 0 biểu diễn cho mức cường độ tối nhất và mức 255 biểu diễn cho mức cường độ sáng nhất. Ảnh đen trắng Ảnh đen trắng là ảnh có hai màu đen và trắng. Nếu phân mức đen trắng thành L mức, sử dụng số bit B để mã hóa mức đen trắng (hay mức xám) thì L được xác định: L=2B. Nếu L=2, B=1 nghĩa là chỉ có 2 mức 0 và 1. Ảnh dùng hai mức 0 và 1 để biểu diễn mức xám gọi là ảnh nhị phân. Mức 1 ứng với màu sáng còn mức 0 ứng với màu tối. Nếu L lớn hơn 2 đó là ảnh đa cấp xám. Như vậy ảnh nhị phân mỗi điểm ảnh được mã hóa trên 1 bit, còn ảnh 256 mức mỗi điểm ảnh được mã hóa trên 8 bit. Ảnh đen trắng nếu dùng 8 bit (1 byte) để biểu diễn mức xám số mỗi mức xám được biểu diễn dưới dạng một số nguyên nằm trong khoảng từ 0 đến 255, mức 0 biểu diễn cho cường độ đen nhất và mức 255 biểu diễn cho cường độ sáng nhất. 6 Ảnh màu Cách biểu diễn cũng tương tự như với ảnh đen trắng, chỉ khác là các số tại mỗi phần tử của ma trận biểu diễn cho ba mầu riêng rẽ gồm: đỏ(red), lục(green) và lam(blue). Để biểu diễn cho một điểm ảnh mầu cần 24 bít, 24 bít này được chia thành ba khoảng 8 bít. Mỗi khoảng này biểu diễn cho cường độ sáng của một trong các mầu chính tổ hợp của các mầu ta được nhiều mức biểu diễn, như vậy mỗi điểm ảnh có thể được mô tả rõ giá trị màu tự nhiên của nó (true color). Ảnh đa cấp xám Ảnh đa cấp xám được áp dụng trong nhiều lĩnh vực như sinh vật học hoặc trong công nghiệp. Thực tế chỉ ra rằng bất kỳ ứng dụng nào trên ảnh mức xám cũng ứng dụng được trên ảnh mầu. Ta có thể biến đổi ảnh mầu về ảnh xám. Mỗi điểm ảnh mầu có 3 giá trị (Red, Green, Blue), nếu 3 giá trị này bằng nhau thì ta có màu xám (Grey), khi đó với mỗi điểm ảnh ta chỉ cần lưu 1 giá trị. Việc xử lý ảnh nhị phân là một bước tiền xử lý các ảnh, để phân đoạn và tách ra các đặc tính. Nhờ vậy ta có thể biết được mối quan hệ tôpô giữa các điểm ảnh cũng như thực hiện các phép biến đổi ảnh không tuyến tính đạt hiệu quả; trong quá trình xử lý ảnh các phép biến đổi này dẫn đến sự đơn giản hóa việc đánh giá ảnh. Việc đếm các điểm ảnh trên ảnh nhị phân đã qua biến đổi tạo điều kiện thuận lợi cho việc tách ra các đặc tính. Bằng cách sử dụng các ảnh nhị phân đã qua xử lý như là những mặt nạ đối với các ảnh xám, ta có thể tách ra các vùng đáng quan tâm của một ảnh xám từ tập hợp các ảnh. Để tạo ra một ảnh nhị phân, một ảnh xám cần phải được biến đổi thành một ảnh nhị phân nhờ một quá trình phân đoạn thích hợp. Muốn thế phương pháp đơn giản nhất là phương pháp tách ngưỡng. Các giá trị nằm ở bên trên ngưỡng được gán giá trị 1 còn ở bên dưới ngưỡng thì được gán giá trị 0. Việc 7 tìm giá trị ngưỡng có thể thực hiện tự động nhờ kỹ thuật tách ngưỡng tự động. Quan hệ giữa các điểm ảnh 1.2.1 1.2.1.1 Các lân cận của điểm ảnh Giả sử một ảnh số được biểu diễn bằng hàm f(x, y), p và q là cặp điểm ảnh có quan hệ với nhau, điểm ảnh p có tọa độ (x, y). Định nghĩa các lân cận của điểm ảnh. - Lân cận 4 của p kí hiệu N4(p): N4(p) = {(x-1, y); (x, y-1); (x, y+1); (x+1, y)} - Lân cận chéo của p kí hiệu Np(p): Np(p) = {(x+1, y+1); (x+1, y-1); (x1, y+1); (x-1, y-1)} - Lân cận 8 của p kí hiệu N8(p): N8(p) = N4(p) + Np(p) 1.2.1.2 Các mối liên kết điểm ảnh Các mối liên kết được sử dụng để xác định giới hạn của đối tượng hoặc xác định vùng trong một ảnh. Một liên kết được đặc trưng bởi tính liền kề giữa các điểm và mức xám của chúng. Có ba loại liên kết: - Liên kết 4: Hai điểm ảnh p và q được gọi là liên kết 4 nếu q thuộc N4(p) - Liên kết 8: Hai điểm ảnh p và q được gọi là liên kết 8 nếu q thuộc N8(p) - Liên kết m (liên kết hỗn hợp): Hai điểm ảnh p và q được gọi là liên kết hỗn hợp nếu q thuộc N4(p) hoặc q thuộc N8(p) 8