Phát triển kỹ thuật dò biên, phát hiện biên và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN KHOA HỌC & CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN PHẠM VIỆT BÌNH PHÁT TRIỂN KỸ THUẬT DÒ BIÊN, PHÁT HIỆN BIÊN VÀ ỨNG DỤNG Chuyên ngành : BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH & HỆ THỐNG TÍNH TOÁN Mã số : 62.46.35.01 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2006 Phần mở đầu 1. Tính cấp thiết của đề tài Một trong những vấn đề trọng tâm nghiên cứu của lĩnh vực thị giác máy là biên và các thao tác trên nó vì các kỹ thuật phân đoạn ảnh chủ yếu dựa vào biên. Nhìn chung về mặt toán học, người ta coi điểm biên của ảnh là điểm có sự thay đổi đột ngột về độ xám. Tập hợp các điểm biên tạo thành biên hay đường bao của ảnh. Ví dụ, trong một ảnh nhị phân, một điểm có thể gọi là biên nếu đó là điểm đen và có ít nhất một điểm trắng bên cạnh. Việc nhận dạng đối tượng phụ thuộc nhiều vào các đặc trưng trích chọn và các đặc trưng này chủ yếu được trích chọn từ biên. Đây là một đề tài vẫn đang được quan tâm và phát triển. Nhất là, ở Việt Nam hiện nay, chưa có nhiều nghiên cứu về vấn đề nhận dạng các đối tượng ảnh, mặc dù những ứng dụng thực tế đang đòi hỏi có những cách giải quyết cụ thể, chẳng hạn như phần mềm nhận dạng các đối tượng địa lý, các biểu tượng trên bản đồ, phần mềm phát hiện và đếm các đối tượng chuyển động. Vì những lý do trên đây luận án lựa đã chọn đề tài "Phát triển kỹ thuật dò biên, phát hiện biên và ứng dụng". 2. Mục đích và phương pháp nghiên cứu của luận án Xu hướng nghiên cứu biên và các phương pháp xử lý trên nó đã được nhiều tác giả nghiên cứu và tiếp tục được nghiên cứu cả về mặt lý thuyết lẫn ứng dụng thực tế. Các sản phẩm kết hợp giữa biên và trung vị hiện nay là các sản phẩm nhập liệu tự động như MapScan for Windows (phần mềm nhập dữ liệu bản đồ tự động) có kết hợp biên với xương trong véc tơ hoá bản đồ, MarkRead 1.0 (phần mềm nhập phiếu điều tra dạng đánh dấu) dùng biên để tách các đối tượng chứa dấu, WinGIS, VectMap véc tơ hoá bản đồ dựa trên việc trích chọn xương ảnh. Biên và xương đã và đang tạo ra các kết quả thực tế rất phong phú và đa dạng. Xuất phát từ thực tế đó, phương pháp nghiên cứu chính của luận án là tiếp tục tiếp thu các kết quả trên và cải tiến chúng nhằm ứng dụng trong nhận dạng đối tượng ảnh. Với mục tiêu của đề tài được đặt ra như sau: • Tìm hiểu các kỹ thuật xử lý biên trong xử lý ảnh và đồ họa nhằm kế thừa các kết quả trên và cải tiến chúng. • Nghiên cứu các kỹ thuật phát hiện biên trực tiếp và gián tiếp. Dựa trên các nghiên cứu này đề xuất một số phương pháp phát hiện biên mới cho một số lớp bài toán. • Đề xuất một số bài toán ứng dụng thực tế có sử dụng các phương pháp trên và cài đặt. 3. Những đóng góp mới của luận án Luận án đã đề xuất được: 9 Một cải tiến cho thuật toán dò biên đã được phát triển của các tác giả Viện Công nghệ thông tin nhằm khắc phục một số ngoại lệ của thuật toán cũ. 9 Hai thuật toán phát hiện biên mới dựa vào trung bình cục bộ và các phép toán hình thái. Trên cơ sở đưa ra công thức mới về phép toán giãn nở nhằm chứng minh một cách lý thuyết một loạt tính chất của phép toán hình thái. Đã đưa ra một số ứng dụng của các kỹ thuật phát hiện biên, cụ thể: 9 Ứng dụng quá trình dò biên để tính toán kích thước chủ đạo của các đối tượng ảnh trong văn bản thông qua kỹ thuật tính biểu đồ tần xuất kích thước hình chữ nhật nhỏ nhất bao quanh đối tượng ảnh. Trên cơ sở đó đề xuất thuật toán phát hiện góc nghiêng văn bản. 9 Ứng dụng tính chất của đường biên và vị trí tương hỗ giữa chúng trong việc cắt chữ Việt in dính. 9 Ứng dụng kỹ thuật trừ ảnh và kỹ thuật phát hiện biên để giải quyết bài toán phát hiện đối tượng chuyển động. 4. Bố cục luận án Luận án gồm phần mở đầu, 3 chương nội dung, phần kết luận và tài liệu tham khảo được cấu trúc như sau: Chương 1: Trình bày tổng quan về xử lý ảnh và biên, các bước cơ bản của một hệ thống nhận dạng xử lý ảnh tổng quát. Sau đó nêu lên vai trò của xử lý biên trong trích chọn các đặc trưng của ảnh, khâu quan trọng trong quá trình nhận dạng ảnh. Chương 2: Trình bày các khái niệm về biên và các phương pháp phát hiện biên cơ bản. Trên cơ sở đó đề xuất một thuật toán dò biên cải tiến, một cách tiếp cận mới cho phát hiện biên dựa vào trung bình cục bộ. Chương này cũng đưa ra mối liên hệ mới giữa các phép toán hình thái và chứng minh một cách chặt chẽ về mặt toán học cho các tính chất của chúng. Cuối cùng đề xuất một thuật toán phát hiện biên mới dựa vào các phép toán hình thái. Chương 3: Trình bày một số ứng dụng của biên và xử lý biên: Tìm xương dựa trên làm mảnh. Phát hiện góc nghiêng văn bản tự động một cách thông minh. Đề xuất một thuật toán cắt chữ in dính dựa vào biên và đưa ra phương pháp phát hiện đối tượng chuyển động dựa vào biên. XỬ LÝ ẢNH Ảnh Ảnh “Tốt hơn” Kết luận Chương 1: Tổng quan về xử lý ảnh và biên 1.1. TỔNG QUAN VỀ XỬ LÝ ẢNH Quá trình xử lý nhận dạng ả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. 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). Sơ đồ tổng quát của một hệ thống xử lý ảnh: Lưu trữ Thu nhận ảnh (Scanner, Camera,Sensor) Tiền xử lý (xóa nhiễu, lọc, quay…) Trích chọn đặc điểm Hệ quyết định Đối sánh rút ra kết luận Hậu xử lý Hình 1.2. Các bước cơ bản trong một hệ thống xử lý ảnh 1.1.1. Tiền xử lý Tiền xử lý là giai đoạn đầu tiên trong xử lý ảnh số. Tuỳ thuộc vào quá trình xử lý tiếp theo trong giai đoạn này sẽ thực hiện các công đoạn khác nhau như: nâng cấp, khôi phục ảnh, nắn chỉnh hình học, khử nhiễu v.v.. 1.1.2. Trích chọn đặc điểm Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm. 1.1.3. Đối sánh, nhận dạng Nhận dạng tự động, mô tả đối tượng, phân loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó. 1.2. BIÊN VÀ VAI TRÒ TRONG NHẬN DẠNG 1.2.1. Biên và các phương pháp phát hiện biên cơ bản Điểm biên là điểm có sự thay đổi đột ngột về mức xám. Ta thường sử dụng hai phương pháp phát hiện biên cơ bản: Phát hiện biên trực tiếp: Phương pháp này làm nổi biên dựa vào sự biến thiên mức xám của ảnh. Kỹ thuật chủ yếu dùng để phát hiện biên ở đây là dựa vào sự biến đổi theo hướng. Nếu lấy đạo hàm bậc nhất của ảnh ta có kỹ thuật Gradient, nếu lấy đạo hàm bậc hai của ảnh ta có kỹ thuật Laplace. Phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân được ảnh thành các vùng thì ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu nhau vì dò biên để thực hiện phân lớp đối tượng mà khi đã phân lớp xong nghĩa là đã phân vùng được ảnh và ngược lại, khi đã phân vùng ảnh đã được phân lớp thành các đối tượng, do đó có thể phát hiện được biên. 1.2.1.1. Phương pháp phát hiện biên trực tiếp a) Kỹ thuật phát hiện biên Gradient Theo định nghĩa gradient là một véctơ có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh. b) Kỹ thuật phát hiện biên Laplace Các phương pháp đánh giá gradient ở trên làm việc khá tốt khi mà độ sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp cho hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc hai Laplace. 1.2.1.2. Phương pháp phát hiện biên gián tiếp a) Một số khái niệm cơ bản *Ảnh và điểm ảnh Ảnh là một mảng số thực 2 chiều (Iij) có kích thước (m×n), trong đó mỗi phần tử Iij(i = 1,...,m; j = 1,...,n) biểu thị mức xám của ảnh tại (i,j) tương ứng. *Các điểm 4 và 8-láng giềng Giả sử (i,j) là một điểm ảnh, các điểm 4 và 8 láng giềng là: N4= {(i’,j’) : |i-i’|+|j-j’| = 1}, N8 = {(i’,j’) : max(|i-i’|,|j-j’|) =1}. b) Chu tuyến của một đối tượng ảnh Định nghĩa 1: [Chu tuyến] 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 .Hình 1.2 biểu diễn chu tuyến của ảnh, P là điểm khởi đầu chu tuyến. P Hình 1.3. Ví dụ về chu tuyến của đối tượng ảnh Định nghĩa 2: [Chu tuyến đối ngẫu] Hai chu tuyến C= và C⊥= được gọi là đối ngẫu của nhau nếu và chỉ nếu ∀i ∃j sao cho: 1. Pi và Qj là 4-láng giềng của nhau. 2. Các điểm Pi là vùng thì Qj là nền và ngược lại. Định nghĩa 3: [Chu tuyến ngoài] Chu tuyến C được gọi là chu tuyến ngoài nếu và chỉ nếu: 1. Chu tuyến đối ngẫu C⊥ là chu tuyến của các điểm nền 2. Độ dài của C nhỏ hơn độ dài C⊥ Định nghĩa 4: [Chu tuyến trong] Chu tuyến C được gọi là chu tuyến trong nếu và chỉ nếu: 1. Chu tuyến đối ngẫu C⊥ là chu tuyến của các điểm nền 2. Độ dài của C lớn hơn độ dài C⊥ c) Thuật toán dò biên tổng quát Về cơ bản, các thuật toán dò biên trên một vùng đều bao gồm các bước sau: • Xác định điểm biên xuất phát • Dự báo và xác định điểm biên tiếp theo • Lặp bước 2 cho đến khi gặp điểm xuất phát Thuật toán dò biên tổng quát Bước 1: Xác định cặp nền-vùng xuất phát Bước 2: Xác định cặp nền-vùng tiếp theo Bước 3: Lựa chọn điểm biên Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2 1.2.2. Vai trò của biên trong nhận dạng Như đã đề cập tới ở phần tổng quan về một hệ thống nhận dạng và xử lý ảnh, quá trình nhận dạng có hai giai đoạn cần thực hiện: Giai đoạn học: Các đặc điểm của đối tượng mẫu được lưu trữ (gọi là học mẫu) và tập các phần tử mẫu được chia thành các lớp. Giai đoạn nhận dạng: Khi có đối tượng cần nhận dạng, các đặc điểm của đối tượng sẽ được trích chọn và sử dụng hàm quyết định để xác định đối tượng cần nhận dạng thuộc lớp nào. 1.3. KẾT LUẬN VÀ VẤN ĐỀ NGHIÊN CỨU Chương này đã trình bày tổng quan về xử lý ảnh và biên, gồm các nội dung chính sau: Hệ thống nhận dạng xử lý ảnh gồm các bước quan trọng như tiền xử lý, trích chọn đặc điểm, đối sánh, nhận dạng, tầm quan trọng của biên trong nhận dạng. Các phương pháp phát hiện biên trực tiếp dựa vào sự biến thiên của mức xám hay các phương pháp phát hiện biên gián tiếp thông qua kỹ thuật dò biên. Chương này cũng nêu rõ mục tiêu cơ bản của luận án là nghiên cứu một số phương pháp phát hiện biên nói riêng và xử lý biên nói chung và ứng dụng của nó trong nhận dạng và xử lý ảnh. Chương 2: Một số phương pháp phát hiện biên Biên là vấn đề chủ yếu trong phân tích ảnh vì các đặc điểm trích chọn trong quá trình phân tích để tiến tới hiểu ảnh chủ yếu dựa vào biên. Các phương pháp phát hiện biên truyền thống chia làm hai loại phát hiện biên: trực tiếp và gián tiếp. Chương này sẽ trình bày một cải tiến cho thuật toán dò biên và tiếp sau đó là các cách tiếp cận mới cho việc phát hiện biên dựa vào hình thái và dựa vào trung bình cục bộ. Cách tiếp cận này mang cả khuynh hướng trực tiếp và gián tiếp. 2.1. THUẬT TOÁN DÒ BIÊN CẢI TIẾN VỚI 4 CẶP NỀN VÙNG XUẤT PHÁT Mục này đề cập đến việc khắc phục một số ngoại lệ trong thuật toán dò biên, trên cơ sở đó đề xuất thuật toán dò biên cải tiến. 2.1.1. Đặt vấn đề Như đã trình bày trong mục 1.2.1.2, thuật toán dò biên tổng quát bao gồm các bước sau: Bước 1: Xác định cặp (nền ,vùng) xuất phát Bước 2: Xác định cặp (nền, vùng ) tiếp theo Bước 3: Lựa chọn các điểm biên Bước 4: Nếu gặp lại cặp xuất phát thì dừng nếu không quay lại bước 2. Việc xác định cặp (nền, vùng) xuất phát được xác định bằng cách duyệt ảnh từ trên xuống dưới, từ trái qua phải, điểm vùng đầu tiên đạt được và điểm trắng trước đó hoặc bên cạnh sẽ tạo thành cặp nền vùng xuất phát. Thuật toán dò biên nhằm tìm ra các chu tuyến trong và chu tuyến ngoài của đối tượng ảnh. Trong trường hợp các đối tượng ảnh có các đường mảnh, thuật toán thường gặp một số ngoại lệ không tìm hết biên trong: a) Ảnh gốc b) Ảnh biên [ Biên thiếu ] Hình 2.1. Ngoại lệ trong thuật toán dò biên sử dụng cặp nền vùng xuất phát 2.1.2. Cải tiến thuật toán dò biên 2.1.2.1. Khắc phục ngoại lệ đối với biên trong Ngoại lệ thiếu biên trong là do chúng ta đã đánh dấu các điểm trong quá trình dò biên nhằm tránh việc trùng lặp trong xử lý. Để khắc phục ngoại lệ này, chúng ta vẫn giữ nguyên thuật toán cũ nhưng trước mỗi lần dò biên cho một điểm thỏa mãn cặp (nền, vùng) xuất phát – tạm gọi là điểm hiện thời thì chúng ta phải kiểm tra: Nếu cặp nền vùng này chưa được dò (chưa được đánh dấu) thì dò như bình thường. Ngược lại chúng ta phải kiểm tra thêm một số bước (tuỳ chọn – thường là một hoặc hai). Nếu điểm đến bước này chưa được đánh dấu thì điểm hiện thời là một điểm thuộc chu tuyến chưa xét, chúng ta vẫn dò biên với điểm hiện thời, nếu ngược lại có nghĩa là điểm hiện thời nếu xét sẽ không cho chu tuyến mới nào. Hình 2.2 cho ta minh hoạ về thuật toán có cải tiến như nhận xét trên. Hình 2.2. Cải tiến tìm biên trong Độ rộng 1 pixel Điểm được xét Bước 1 Bước 2 Rõ ràng sau bước 2 thì điểm này thỏa mãn là điểm biên chưa được dò. Như vậy chúng ta có thể xử lý được ngoại lệ vừa nêu. Một điểm ảnh có ít nhất một trong 4-láng giềng là điểm nền trong khi nó là điểm vùng thì nó là điểm biên. Do đó, chúng ta cải tiến thuật toán tổng quát thay vì một cặp (nền, vùng) xuất phát thành 4 cặp (nền, vùng) xuất phát. a) Ảnh gốc b) Ảnh biên Hình 2.3. Ngoại lệ thiếu biên trong khi số bước dò không biết trước [ Biên thiếu ] 2.1.2.2. Thuật toán dò biên cải tiến Duyệt từ trên xuống dưới, từ trái qua phải. Đối với mỗi điểm vùng P, gọi Po, P2, P4, P6 là các điểm kề phải, trên, trái, dưới của P, ta sẽ kiểm tra các trường hợp sau : - Nếu P4 là điểm nền, thì cặp (nền, vùng) xuất phát sẽ là (P,P4). - Ngược lại nếu P0 là điểm nền, thì cặp xuất phát sẽ là (P,Po). - Ngược lại nếu P2 là điểm nền, thì cặp xuất phát sẽ là (P,P2). - Ngược lại nếu P6 là điểm nền, thì cặp xuất phát sẽ là (P,P6). Ta có thuật toán dò biên cải tiến bao gồm các bước cơ bản sau: Bước 1: Xác định tập các cặp (nền, vùng) xuất phát theo tiêu chuẩn cặp (nền, vùng) xuất phát cải tiến. Bước 2: Nếu còn cặp (nền, vùng) trong tập các cặp (nền, vùng) xuất phát tìm được trong bước 1 thì lấy ra một cặp, nếu không thuật toán kết thúc. Bước 3: Xác định cặp (nền, vùng) tiếp theo. Bước 4: Lựa chọn điểm biên vùng Bước 5: Nếu gặp lại cặp (nền, vùng) xuất phát thì quay lại thực hiện bước 2. Nếu không thì quay lại thực hiện bước 3. a) Ảnh gốc b) Ảnh biên bị thiếu do ngoại lệ c) Ảnh biên kết quả đã khắc phục được ngoại lệ Hình 2.1. Thuật toán cải tiến khắc phục được các ngoại lệ 2.2. PHÁT HIỆN BIÊN DỰA VÀO TRUNG BÌNH CỤC BỘ Phần này đề cập đến kỹ thuật mới dựa vào trung bình cục bộ trên cơ sở đánh giá độ chênh lệch về giá trị mức xám của điểm ảnh so với các điểm lân cận do đó kết hợp được ưu điểm của cả 2 khuynh hướng phát hiện biên trực tiếp và gián tiếp. Ý tưởng chính của thuật toán được đề xuất là xác định tất cả các điểm nằm trên biên không theo hướng tìm kiếm và sử dụng các ma trận lọc mà sẽ thông qua việc so sánh độ chênh lệch về mức xám của nó so với mức xám chung của các điểm ảnh lân cận (mức xám nền). Trước hết tính giá trị xám trung bình của các điểm ảnh nằm trong phạm vi của ma trận 3×3 hoặc 5×5 có tâm là điểm ảnh đang xét. Nếu như độ chênh lệch mức xám giữa điểm đang xét với giá trị xám trung bình thỏa mãn lớn hơn một mức tối thiểu δ1 nào đó (PTB+ δ1< P) thì chúng ta sẽ coi nó là điểm biên và ghi nhận lại, còn các điểm không thỏa mãn điều kiện trên sẽ được coi là điểm nền. δ1 N=5 Hình 2.5. Ma trận điểm ảnh trước và sau lọc Ảnh biên thu được với δ1= 25 Ảnh biên thu được với δ1= 250 Hình 2.6. Các ảnh biên kết quả thu được theo thuật toán đề xuất *Nhận xét: Thuật toán dò biên sử dụng trong chương trình tuy đã hạn chế được nhiều nhiễu so với việc sử dụng các bộ lọc và làm nổi rõ các đường biên nhưng vẫn không loại bỏ được hầu hết các nhiễu. Khi áp dụng thuật toán trên chúng ta vẫn có thể làm giảm bớt nhiễu đi nhiều hơn nữa bằng cách tăng giá trị của hệ số delta lên. Nhưng khi đó các đường biên thu được cũng bị đứt đoạn và mờ đi nhiều. 2.3. PHÁT HIỆN BIÊN DỰA VÀO CÁC PHÉP TOÁN HÌNH THÁI 2.3.1. Các phép toán hình thái và tính chất 2.3.1.1. Các phép toán hình thái cơ bản Các phép toán này được định nghĩa như sau: Giả thiết ta có đối tượng X và phần tử cấu trúc (mẫu) B trong không gian Euclide hai chiều. Kí hiệu Bx là dịch chuyển của B tới vị trí x. Định nghĩa 2.1: (DILATION) Phép "giãn nở" của X theo mẫu B là tập hợp của tất cả các điểm x sao cho Bx chạm tới X: X ⊕ B = {x : Bx ∩ X ≠ Φ} Định nghĩa 2.1’ (DILATION) Phép "giãn nở" của X theo mẫu B là hợp của tất cả các Bx với x thuộc X. Ta có: X ⊕ B = U Xx xB ∈ Định nghĩa 2.2: (EROSION) Phép "co" của X theo B là tập hợp tất cả các điểm x sao cho Bx nằm trong X: X \ B = {x : Bx ⊆ X} Ví dụ: Ta có tập X như sau: X = ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ 00 000 000 00 00 xxx xx xx xxx xxx x8 B = X ⊕ B = và X\B = ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ 000 00000 0000 0000 0000 xx x x x ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ xxxx xxxx xxx xxxxx xxxx 0 0 00 0 Định nghĩa 2.3: (OPEN) Phép toán mở (OPEN) của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã co và giãn nở liên liếp theo B. OPEN(X,B) = (X \ B) ⊕ B Ví dụ: Với tập X và B trong ví dụ trên ta có OPEN(X,B) = (X\B) ⊕ B = ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0xxx0 00000 00xx0 0xx00 xx000 Định nghĩa 2.4: (CLOSE) Phép toán đóng (CLOSE) của X theo cấu trúc B là tập hợp các điểm của ảnh X sau khi đã giãn nở và co liên tiếp theo B. CLOSE(X,B) = (X ⊕ B) \ B Theo ví dụ trên ta có: CLOSE(X,B) = (X ⊕ B) \ B = ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ 0xxx0 0xxx0 00xx0 xxxxx xxxx0 2.3.1.2. Một số tính chất của phép toán hình thái * Mệnh đề 2.1: (Tính gia tăng) (i) X ⊆ X’ ⇒ X \ B ⊆ X’ \ B ∀B X ⊕ B ⊆ X’ ⊕ B ∀B (ii) B ⊆ B' => X \ B ⊇ X \ B' ∀X X ⊕ B ⊆ X ⊕ B’ ∀X *Mệnh đề 2.2: (Tính phân phối với phép ∪) (i) X ⊕ (B ∪ B') = (X ⊕ B) ∪ (X ⊕ B') (ii) X\ (B ∪ B') = (X \ B) ∩ (X \B') * Ý nghĩa: Ta có thể phân tích các mẫu phức tạp trở thành các mẫu đơn giản thuận tiện cho việc cài đặt. * Mệnh đề 2.3: (Tính phân phối với phép ∩) (X ∩ Y) \ B = (X \ B) ∩ (Y \ B) * Mệnh đề 2.4: (Tính kết hợp) (i) (X ⊕ B) ⊕ B' = X ⊕ (B ⊕ B') (ii) (X \ B) \ B' = X \ (B ⊕ B') * Định lý 2.1 Giả sử, X là một đối tượng ảnh, B là mẫu. Khi đó, X sẽ bị chặn trên bởi tập CLOSE của X theo B và bị chặn dưới bởi tập CLOSE của X theo B. Ta có, (X ⊕ B) \ B ⊇ X ⊇ (X \ B) ⊕ B Chứng minh: Ta có: ∀ x ∈ X ⇒ Bx X ⊕ B (Vì X ⊕ B = ) ⊆ U Xx xB ∈ ⇒ x ∈ (X ⊕ B) \ B (theo định nghĩa phép co) ⇒ (X ⊕ B) \ B ⊇ X (1) Mặt khác, ∀ y ∈ (X \ B) ⊕ B, suy ra: ∃ x ∈ X \ B sao cho y ∈ Bx (Vì (X\B) ⊕ B = ) U BΘ∈Xx xB ⇒ Bx ⊆ X ⇒ y ∈ X Suy ra: X ⊇ (X \B) ⊕ B (2) Từ (1) và (2) Ta có: (X ⊕ B) \ B ⊇ X ⊇ (X \B) ⊕ B. *Hệ quả 2.1: (Tính bất biến) (i) ((X ⊕ B) \B) ⊕ B = X ⊕ B (ii) ((X \ B) ⊕ B) \ B = X\B Thật vậy, từ định lý 2.1 ta có X ⊆ (X ⊕ B) \ B ⇒ X ⊕ B ⊆ ((X ⊕ B) \B) ⊕ B (do tính chất gia tăng) (3) Mặt khác, cũng từ định lý 2.1 ta có (X \ B) ⊕ B ⊆ X ∀X Do đó, thay X bởi X ⊕ B ta có, ((X ⊕ B) \B) ⊕ B ⊆ X ⊕ B (4) Từ (3) và (4) Ta có: ((X ⊕ B) \B) ⊕ B = X ⊕ B Tương tự ta có, ((X \ B) ⊕ B) \ B = X\B 2.3.2. Phát hiện biên dựa vào phép toán hình thái Biên (hay đường biên) có thể hiểu đơn giản là các đường bao của các đối tượng trong ảnh chính là ranh giới giữa đối tượng và nền. Việc xem ranh giới là phần được tạo lập bởi các điểm thuộc đối tượng và thuộc nền cho phép ta xác định biên dựa trên các phép toán hình thái. Theo định lý 2.1 ta có, (X⊕B)\B ⊇ X ∀B Như vậy, có thể xem CLOSE(X,B) như là xấp xỉ trên của tập X theo mẫu B CLOSE(X,B)= (X⊕B)\B XÊp xØ trªn cña X (chøa X) OPEN(X,B)= ((X\B)⊕B) XÊp xØ d−íi cña X (thuéc X) X© B = CLOSE(X,B)\ OPEN(X,B) XÊp xØ biªn cña X theo mÉu B Hình 2.7. Xấp xỉ trên và dưới theo mẫu B của X Cũng theo định lý 2.1 ta có, (X\B)⊕B ⊆ X ∀B Do vậy, tập OPEN(X,B) = (X\B)⊕B có thể được xem như là xấp xỉ dưới của tập X theo mẫu B. Từ đó, tập CLOSE(X,B)\ OPEN(X,B) có thể được xem như là xấp xỉ biên của tập X theo mẫu và quá trình xấp xỉ biên của X theo mẫu B kí hiệu là X© B. Để tăng độ chính xác, người ta thường xem B là dãy các phần tử cấu trúc. {B} = {Bi, 1≤ i ≤ n } Và xấp xỉ biên của X theo tập cấu trúc B được xác định: ( )Un 1i iBX = © X©B = Thuật toán phát hiện biên dựa vào phép toán hình thái: Vào : Ảnh X và dãy mẫu B= {Bi, 1≤ i ≤ n }; Ra : Biên của đối tượng theo mẫu B Phương pháp: Bước 1: Tính X © Bi ∀i=1,n ( )Un 1i iBX = ©Bước 2: Tính Trong phần này đã được đặc tả thuật toán phát hiện biên dựa vào các phép toán hình thái bằng ngôn ngữ RAISE. 2.3.3. Thực nghiệm Chúng tôi đã cài đặt thuật toán đề xuất đối với các mẫu tách biên Bi là: B1= × 8 × × B3= 8 × × B4= 8 × × B2= 8 × Trong hình 2.5a dưới đây là ảnh gốc với 256 mức xám, Hình 2.5b là ảnh biên thu được qua phát hiện biên bằng Sobel, Hình 2.5c là ảnh biên thu được qua Laplace. Hình 2.5d là ảnh biên kết quả thực hiện bởi thuật toán phát hiện biên bằng các phép toán hình thái trên với ngưỡng tách θ = 128 a) Ảnh gốc đa cấp xám b)Ảnh biên thu được qua Sobel c)Ảnh biên thu được qua Laplace d) Ảnh kết quả dựa vào phép toán hình thái Hình 2. 8. Phát hiện biên bởi thuật toán dựa vào phép toán hình thái 2.4. KẾT LUẬN VÀ VẤN ĐỀ NGHIÊN CỨU Chương này tập trung nghiên cứu cải tiến phương pháp dò biên đã có và đề xuất một số cách tiếp cận phát hiện biên mới dựa vào trung bình cục bộ và đề xuất một phương pháp phát hiện biên mới dựa vào phép toán hình thái: • Đề xuất một cải tiến cho thuật toán dò biên trên cơ sở nghiên cứu các ngoại lệ và tìm cách khắc phục. Thuật toán đề xuất thay thế cặp điểm nền vùng xuất phát bởi 4 cặp nền vùng xuất phát từ đó khắc phục được nhược điểm của thuật toán gốc là bỏ sót các đường biên trong với trường hợp đối tượng có nhiều đường biên. • Đề xuất một thuật toán phát hiện biên dựa vào trung bình cục bộ có cả tính chất của thuật toán phát hiện biên gián tiếp lẫn tính chất của phát hiện biên trực tiếp. • Đưa ra mối liên hệ mới của phép toán giãn nở trên cơ sở đó chứng minh một cách chặt chẽ về mặt toán học các tính chất của các phép toán hình thái. Trên cơ sở đó đề xuất một thuật toán phát hiện biên mới.