Nghiên cứu phương pháp genetic, phép toán hình thái và ứng dụng

  • Số trang: 54 |
  • Loại file: PDF |
  • Lượt xem: 22 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

MỤC LỤC DANH MỤC CÁC HÌNH VẼ ...................................................................................... 4 Chƣơng 1: MỞ ĐẦU ................................................................................................... 6 Chƣơng I: Các khái niệm cơ bản về toán học hình thái ................................................ 8 I.1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái ................................. 8 I.1.1. Một số khái niệm cơ bản về tập hợp ................................................... 9 I.1.2. Các phép toán logic trên ảnh nhị phân.............................................. 11 I.2. Phép toán làm béo (Dilation) và làm gầy (Erosion) ...................................... 12 I.2.1. Làm béo ........................................................................................... 12 I.2.2. Làm gầy ........................................................................................... 14 I.2.3. Phép toán Opening và Closing ........................................................ 14 I.2.4. Biến đổi Hit or Miss......................................................................... 17 I.3. Một số thuật toán dựa trên phép toán hình thái ............................................. 19 I.3.1. Trích chọn biên ................................................................................ 19 I.3.2. Tô miền ........................................................................................... 20 I.3.3. Tách các thành phần liên thông ........................................................ 21 I.3.4. Làm mảnh ........................................................................................ 23 I.3.5. Làm dầy ........................................................................................... 24 I.3.6. Tìm xƣơng của ảnh .......................................................................... 25 Chƣơng II: Thuật toán di truyền ................................................................................. 27 II.1. Thuật toán di truyền là gì? .......................................................................... 27 II.2. Sử dụng thuật toán di truyền trong toán học hình thái ................................. 27 2 II.3. Hoạt động của thuật toán di truyền ............................................................. 28 II.3.1. Quá trình lai ghép (phép lai) ............................................................... 30 Lai ghép một điểm .................................................................................... 30 Lai ghép hai điểm ..................................................................................... 30 Cắt và ghép ............................................................................................... 31 Ví dụ về phép lai ....................................................................................... 31 II.3.2. Quá trình đột biến (phép đột biến) ...................................................... 32 II.3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) ............... 33 II.4. Mô hình thuật toán...................................................................................... 33 Chƣơng III: Một cách tiếp cận di truyền trong bài toán phân rã phần tử cấu trúc........ 35 III.1. Tiếp cận ngẫu nhiên .................................................................................. 38 III.2. Cấu trúc dữ liệu ......................................................................................... 39 III.3. Giải thuật dựa trên thuật toán tìm kiếm di truyền ....................................... 42 CHƢƠNG IV. THỰC NGHIỆM ............................................................................... 47 IV.1. Mô tả bài toán và giả thuyết ...................................................................... 47 IV.2. Giao diện chính của chƣơng trình .............................................................. 47 IV.3. Một số kết quả thử nghiệm ........................................................................ 48 V. KẾT LUẬN ................................................................................................... 51 Tài liệu tham khảo ..................................................................................................... 52 3 DANH MỤC CÁC HÌNH VẼ Hình I.1.1. Ảnh nhị phân................................................................................................. 8 Hình I.1.2. Ảnh đa cấp xám ............................................................................................ 9 Hình I.1.3. Các phép toán cơ bản trên tập hợp ............................................................... 10 HÌnh I.1.4. Các phép toán cơ bản .................................................................................. 12 Hình I.2.1. Phép toán dilation........................................................................................ 13 Hình I.2.2. Ứng dụng của phép toán dilation ................................................................. 13 Hình I.2.3. Loại bỏ thành phần nhiễu ............................................................................ 14 Hình I.2.4. Phép toán Opening ...................................................................................... 15 Hình I.2.5. Phép toán Closing ....................................................................................... 15 Hình I.2.6. Phép toán Opening và Closing .................................................................... 16 Hình I.2.7. Xử lý nhiễu trong ảnh vân tay ..................................................................... 17 Hình I.2.8. Phép toán Hit ỏ Miss ................................................................................... 18 Hình I.3.1. Trích chọn biên ........................................................................................... 19 Hình I.3.2. Ảnh đƣợc trích chọn biên ............................................................................ 20 Hình I.3.3. Ví dụ thuật toán tô miền .............................................................................. 21 Hình I.3.4. Tìm các thành phần liên thông trong ảnh ..................................................... 22 Hình I.3.5. Xác định vật thể lạ trong ảnh ....................................................................... 23 Hình I.3.6. Làm mảnh ảnh ............................................................................................ 24 Hình I.3.7. Làm dầy ảnh ............................................................................................... 25 4 Hình I.3.8. Tìm xƣơng của ảnh ..................................................................................... 26 Hình II.1. Mô phỏng quá trình tiến hóa ......................................................................... 29 Hình II.2. Lai ghép một điểm ........................................................................................ 30 Hình II.3. Lai ghép hai điểm ......................................................................................... 31 Hình II.4. Cắt và ghép ................................................................................................... 31 Hình II.5. Ví dụ về phép lai .......................................................................................... 32 Hình II.6. Đột biến tại bít thứ 6 ..................................................................................... 32 Hình II.7. Mô tả hoạt động thuật toán ........................................................................... 33 Hình III.1. Cấu trúc dữ liệu........................................................................................... 40 Hình III.2. Ví dụ về cắt và ghép nối. ............................................................................. 44 5 MỞ ĐẦU Xử lý ảnh là một ngành phát triển mạnh mẽ trong khoa học máy tính. Sự phát triển của nó đƣợc tiếp sức bởi các công nghệ mới trong xử lý ảnh số, các bộ vi xử lý mới cùng các thiết bị lƣu trữ phổ biến. Những ngành nghiên cứu trƣớc kia chủ yếu xử dụng ảnh tƣơng tự nay đã chuyển sang các hệ thống ảnh số do sự linh đông và dễ đáp ứng của nó. Các thí dụ quan trọng có thể kể ra đây nhƣ trong y học, sản xuất phim và video, nhiếp ảnh,..v.v. Những nguồn dữ liệu này đã tạo ra một lƣợng khổng lồ các dữ liệu ảnh số. Xử lý ảnh quan tâm chủ yếu đến việc trích chọn các thông tin hữu ích từ trong ảnh. Các thuật toán xử lý ảnh đƣợc phân ra làm 3 mức. Mức thấp nhất là các phƣơng pháp thao tác trực tiếp với các dữ liệu thô, các giá trị điểm ảnh có thể bị nhiễu. Mức thứ hai là tận dụng các kết quả ở mức 1 để đƣa ra các kết quả tốt hơn nhƣ: phân đoạn ảnh, liên kết ảnh. Mức thứ ba là các phƣơng pháp trích trọn ngữ nghĩa các thông tin dựa trên các kết quả của các mức thấp hơn, ví dụ nhƣ: nhận dạng chữ viết tay, nhận dạng mặt ngƣời… Toán học hình thái (Mathematic Morphology) là một lĩnh vực riêng biệt trong xử lý ảnh. Không giống nhƣ các cách tiếp cận khác thiên về toán học tính toán, MM dựa trên cấu trúc và hình dạng, dùng các toán hình thái cơ bản để làm đơn giản ảnh nhƣng vẫn giữ lại những đặc trƣng chính. MM còn là một công cụ cơ bản để trích chọn các thành phần ảnh, nhƣ biên ảnh, xƣơng ảnh, rất hữu dụng cho việc biểu diễn các các vùng khác nhau trên một ảnh. Những kỹ thuật dùng toán hình thái nhƣ lọc ảnh, làm mảnh ảnh hay làm dầy ảnh có sử dụng toán học hình thái cũng đƣợc sử dụng trong quá trình tiền xử lý ảnh. Ngoài ra, một trong các ứng dụng quan trọng mà tôi đề cập chính trong luận văn này là: Phân rã phần tử cấu trúc thành các phần tử cấu trúc nhỏ hơn. Phần tử cấu trúc là phần tử tham gia trong các phép toán hình thái, và việc phân rã phần tử cấu trúc hoặc nói một cách khác là ma trận điểm ảnh có ba lợi ích quan trọng: Thứ nhất, làm giảm phép toán trong các ứng dụng mà phần tử đó tham gia. Thứ hai, giảm không gian lƣu trữ ảnh. Thứ ba, đối với các hệ thống chỉ hỗ trợ tập lệnh SIMD trên các phần tử nhỏ hơn nhiều phần tử cấu trúc, thì việc phân rã phần tử cấu trúc thành các phần tử cấu trúc nhỏ hơn là cần thiết. Trong khuôn khổ của luận văn thạc sỹ này, tôi muốn tập trung đi sâu vào tìm hiểu các phép toán hình thái và một số ứng dụng của phép toán hình thái trong xử lý ảnh. Phần chính của luận văn, tôi sẽ trình bày một số kết quả đạt đƣợc trong việc ứng 6 dụng thuật toán di truyền để giải quyết bài toán phân rã phần tử cấu trúc trong xử lý ảnh. Bố cục của luận văn này đƣợc tổ chức thành 3 chƣơng: Chương 1: Trình bày các kiến thức cơ bản về phép toán hình thái bao gồm các khái niệm, các thuật toán và các ứng dụng tiêu biểu của phép toán hình thái. Chương 2: Trình bày ngắn gọn các khái niệm liên quan đến thuật toán di truyền. Chương 3: Tập trung giải quyết bài toán phân rã phần tử cấu trúc bằng phƣơng pháp tiếp cận ngẫu nhiên dựa trên thuật toán di truyền. Chương 4: Trình bày kết quả thực nghiệm: Phân rã phần tử cấu trúc kích thƣớc 9x9 thành các phần tử cấu trúc kích thƣớc 3x3. Phần kết luận nêu tóm tắt các kết quả đạt đƣợc và đƣa ra các những vấn đề còn tồn đọng để nâng cao hiệu năng của thuật toán. 7 Chƣơng I: Các khái niệm cơ bản về toán học hình thái I.1. Quan hệ giữa khái niệm tập hợp và phép toán hình thái Toán học hình thái (MM) dựa trên khái niệm về tập hợp, và chính nhờ có khái niệm này mà toán học hình thái mang lại một cách tiếp mới cận đối với các bài toán xử lý ảnh. Trong hầu hết các trƣờng hợp, phép toán hình thái đều thể hiện một tính chất nào đó của phép toán liên quan đến khái niệm tập hợp. Bằng các khái niệm đơn giản về phép toán hợp, giao, phần bù...v.v, chúng ta có thể xây dựng các phép toán rất hữu ích cho các kỹ thuật xử lý ảnh. Ảnh số là sự biểu diễn ảnh dƣới dạng tín hiệu tƣơng tự hoặc tín hiệu số. Trong biểu diễn số của các ảnh đa mức xám, tập hợp các điểm ảnh đƣợc biểu diễn dƣới dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám hay cƣờng độ của ảnh tại vị trí đó, phần tử trong ma trận đƣợc gọi là một phần tử ảnh, thông thƣờng kí hiệu là PEL (Picture Element) hoặc là điểm ảnh (Pixel). Đối với ảnh nhị phân, ta ngầm định các điểm ảnh thể hiện đối tƣợng ảnh đƣợc mã hóa bởi các điểm ảnh có giá trị 1. Tƣơng ứng với đó, nền sẽ đƣợc mã hóa bởi các điểm ảnh có giá trị 0. Ảnh đa cấp xám có thể đƣợc biểu diễn bởi các tập hợp tập con của tập Z3. Hình I.1.1. Ảnh nhị phân 8 Mỗi một phần tử đƣợc đại diện bởi một bộ 3 phần tử (x1,x2,x3) tƣơng ứng là toạ độ điểm ảnh và mức xám tại ảnh đó. Hình I.1.2[17] mô tả một thể hiện đơn giản của ảnh đa cấp xám Hình I.1.2. Ảnh đa cấp xám Nhƣ vậy, ta đã hình dung đƣợc mối quan hệ giữa ảnh và khái niệm tập hợp. Đối với mỗi ảnh thì sẽ có tƣơng ứng một tập hợp thể hiện ảnh và ngƣợc lại, từ một tập hợp, ta có thể dựng lại ảnh tƣơng ứng. I.1.1. Một số khái niệm cơ bản về tập hợp Giả sử A là một tập thuộc Z 2 . Nếu a=(a1,a2) là một phần tử của A, thì ta kí hiệu là: a A Tƣơng tự nhƣ vậy, trong trƣờng hợp a không phải là phần tử con của A thì kí hiệu: a A Tập hợp không chứa phần tử nào thì đƣợc gọi là tập rỗng 9 Trong khuôn khổ của luận văn này, chúng ta sẽ quan tâm tới khái niệm phần tử của một tập hợp trong phạm vi của ảnh nhị phân. Ví dụ, khi ta viết Cw  {|wd   , dD  } thì nghĩa là C là tập các phần tử w là đối của các phần tử tƣơng ứng của tập D qua gốc tọa độ. Nếu nhƣ với mọi phần tử A đều thuộc tập B thì ta nói rằng tập A là một tập con của tập B và kí hiệu là : A B Hợp của hai tập A và tập B là tập tất cả các phần tử hoặc thuộc A hoặc thuộc B. CAB Tƣơng tự nhƣ vậy giao của hai tập A và tập B là tất cả các phần tử vừa thuộc A lại đồng thời thuộc B : Hình I.1.3. Các phép toán cơ bản trên tập hợp Phần bù của tập A là tập tất cả các phần tử không thuộc A C A  { w |wA } Hiệu A và B, kí hiệu là A-B đƣợc định nghĩa bởi Ngoài ra, trong toán học hình thái ngƣời ta còn đƣa ra hai định nghĩa khác, tập nghịch của A : 10  B  {w | w  b, b  B} và tập tịnh tiến của tập A bởi véc tơ z(z1,z2), đƣợc định nghĩa là tập tất cả các phần tử là ảnh của tập A trong phép tịnh tiến theo véc tơ z : Az  {c | c  a  z, a  A} I.1.2. Các phép toán logic trên ảnh nhị phân Phần lớn các ứng dụng trong chƣơng này là đề cập tới ảnh nhị phân. Các phép toán logic dù đơn giản nhƣng cung cấp một cách thực thi hiệu quả để có thể triển khai các thuật toán xử lý ảnh dựa trên phép toán hình thái. Phép toán cơ bản nhất đƣợc sử dụng trong xử lý ảnh là : phép toán AND, phép toán OR và phép toán NOT. Các tính chất của chúng đƣợc định nghĩa trong bảng dƣới đây : P Q P AND Q P OR q NOT p 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 0 Dựa trên ba phép toán cơ bản trên, ta có thể xây dựng đƣợc các phép toán phức tạp hơn bằng cách kết hợp chúng lại với nhau. Hình I.1.4[26]. dƣới đây thể hiện các phép toán dựa trên bộ các phép toán cơ bản ở trên. 11 Hình I.1.4. Các phép toán cơ bản I.2. Phép toán làm béo (Dilation) và làm gầy (Erosion) Ta bắt đầu thảo luận về phép toán hình thái, bƣớc đầu xem xét 2 phép toán hình thái cơ bản: làm béo và làm gầy. Đây là 2 phép toán cơ bản nhất và thực tế rằng đa số các thuật toán đều dựa trên 2 phép toán này. I.2.1. Làm béo Với A và B là 2 tập trong Z 2 , tập béo của A gây bởi tập B đƣợc ký hiệu là:  A  B  {z | ( B) z  A  } Tập B thƣờng đƣợc gọi là phần tử cấu trúc do sự tác động của nó gây sự ảnh hƣởng về cấu trúc lên tập A. Phƣơng trình trên không chỉ nhằm đƣa ra định nghĩa của phép toán làm béo mà còn mang lại những lợi thế khác, nó mang lại một cảm giác trực quan rằng các phần tử cấu trúc này nhƣ là một mặt nạ xoắn làm thay đổi cấu trúc của ảnh ban đầu. 12 Hình I.2.1[26](a) thể hiện ảnh tham gia thuật toán làm béo, hình I.2.1(b) mô tả phần tử cấu trúc và tập ngƣợc của nó( những điểm chấm đen mô tả các phần tử gốc). Trong trƣờng hợp này phần tử cấu trúc và phần tử cấu trúc nghịch của nó trùng nhau do B đối xứng. Hình I.2.1. Phép toán làm béo Một trong các ứng dụng đơn giản nhất của phép toán làm béo là nối các nét đứt trong quá trình nâng cao chất lƣợng ảnh. Hình I.2.2 dƣới đây là một ví dụ ảnh với các kí tự đứt gãy do quá trình quét ảnh không đƣợc tốt hay do việc zoom ảnh quá lớn. Độ dài lớn nhất của mỗi phần gãy trong ví dụ này là 2 pixel. Ta có thể dùng một phần tử cấu trúc đơn giản để nối các nét đứt này lại với nhau. Kết quả của việc thực hiện phép toán làm béo này là ảnh đƣợc khôi phục, các vết đứt gãy đƣợc thay thế bởi các điểm ảnh tạo cho các nét chữ đƣợc trơn và liên tục. Hình I.2.2. Ứng dụng của phép toán dilation 13 I.2.2. Làm gầy Cho tập A và B trong Z 2 , tập gầy của A gây bởi B đƣợc kí hiệu là Một trong các ứng dụng đơn giản nhất của phép toán làm gầy là loại bỏ các thành phần dƣ thừa hay các thành phần nhiễu. Hình I.2.3[26]. mô tả một ảnh nhị phân đƣợc cấu tạo bởi các hình vuông với các kích thƣớc là 1,2,5,7,9 và 15 điểm ảnh. Bằng cách sử dụng phần tử cấu trúc với kích thƣớc phù hợp và sử dụng phép toán làm gầy, chúng ta có thể loại bỏ các hình vuông điểm ảnh nhỏ (nhiễu) và giữ lại các hình vuông điểm ảnh với kích thƣớc lớn (các thành phần chính của ảnh) Hình I.2.3. Loại bỏ thành phần nhiễu I.2.3. Phép toán Opening và Closing Nhƣ chúng ta đã thấy, phép toán làm béo tăng kích thƣớc của ảnh còn phép toán làm gầy giảm kích thƣớc của ảnh. Trong phần này, chúng ta sẽ bàn đến 2 trong những phép toán quan trọng nhất: Opening và Closing. Opening ban đầu làm mịn đƣờng biên của đối tƣợng sau đó loại bỏ các phần lồi ra. Closing cũng nhằm mục đích làm mịn đƣờng biên nhƣng khác với phép toán Opening, phép toán Closing ban đầu sẽ làm dày đối tƣợng và sau đó mới thực hiện việc làm mịn biên của ảnh Opening của tập A bởi phần tử cấu trúc B đƣợc ký hiệu là A  B  ( A  B)  B Tƣơng tự Closing của A bởi B là : A  B  ( A  B)  B 14 Phép toán Opening có một cách thể hiện hình học đơn giản. Giả sử chúng ta coi phần tử cấu trúc B nhƣ là một quả bóng. Đƣờng bao của tập A  B đƣợc hình thành bằng cách cho B lăn trong cấu trúc hình học của A. A  B  {( B) z  A} Hình I.2.4. Phép toán Opening Ngƣợc lại, phép toán Closing cũng có một thể hiện tƣơng tự, nhƣng bằng cách ngƣợc lại. Quả bóng sẽ đƣợc lăn ở phía ngoài cấu trúc hình học của A. Hình I.2.5. Phép toán Closing 15 Hình I.2.6. Phép toán Opening Một số tính chất cơ bản của phép toán opening: - A  B là tập con của A - Nếu C là tập con của D thì C  B là tập con của D  B BBA )  B - (A Tƣơng tự nhƣ vậy, phép toán closing thỏa mãn các tính chất sau: - A là tập con của A  B - Nếu C là tập con của D thì C  B là tập con của D  B - ( A  B)  B  A  B Các phép toán hình thái còn đƣợc sử dụng để xây dựng các bộ lọc. Ví dụ nhƣ trong bài toán nhận dạnh vân tay ngƣời, ảnh cần nhận dạng có nhiễu (nhƣ thể hiện trong hình I.2.7(a)[26]. Các nhiễu là các chấm trắng nhỏ (khác với các ví dụ trƣớc, trong ví dụ này nội dung của ảnh đƣợc thể hiện bởi các điểm ảnh sáng còn nền là các điểm ảnh sẫm mầu). Mục tiêu của quá trình tiền xử lý ảnh trƣớc khi nhận dạng là việc lọc các thành phần nhiễu nhƣng đồng thời phải đảm bảo sự ảnh hƣởng đến các thành 16 phần vân tay ít nhất có thể. Để lọc các thành phần nhiễu, ta sử dụng phần tử cấu trúc đƣợc mô tả trong hình I.2.7(b) . Toàn bộ hình I.2.7 thể hiện từng bƣớc của quá trình lọc ảnh. Các nhiễu đƣợc hoàn toàn loại bỏ trong phép toán làm gầy ở giai đoạn đầu do kích thƣớc của các điểm nhiễu là nhỏ hơn kích thƣớc của phần tử cấu trúc và sau đó đƣợc khôi phục lại nguyên dạng nhƣ ảnh lúc đầu. Chú ý rằng, sau quá trình này gần nhƣ toàn bộ các thành phần nhiễu đã bị lọc bỏ. Hình I.2.7. Xử lý nhiễu trong ảnh vân tay I.2.4. Biến đổi Hit or Miss Biến đổi Hit or Miss là một công cụ cơ bản để dò tìm ảnh. Tôi giới thiệu khái niệm này với sự trợ giúp của hình I.2.8. Trong hình, tập A bao gồm 3 ảnh X, Y, Z. mục tiêu là tìm vị trí của một trong 3 ảnh trên, giả sử là X Giả sử gốc của mỗi ảnh là tại trung tâm của ảnh. Giả sử X đƣợc bao bởi một cửa sổ nhỏ W. Ta định nghĩa nền của tập X trên ảnh W là tập tất cả các điểm ảnh thuộc W mà không thuộc X, ký hiệu là W-X nhƣ đƣợc mô tả trong hình I.2.8(b). Trong hình I.2.8(c) mô tả phần bù của tập A. Hình I.2.8(d) thể hiện tập A gầy . Nhớ lại rằng tập gầy A bởi X là tập tất cả các vị trí của điểm gốc X sao cho X hoàn toàn nằm trong tập A. Hiểu theo cách hình học thuần túy thì có thể coi nhƣ là tập hợp tất cả các điểm gốc của X mà tại đó X giao (match) với tập A. Hình I.2.8[26] thể hiện việc làm gầy phần bù tập A bởi phần tử cấu trúc (W  X ) . Phần tối phía ngoài trong hình I.2.8(e) là phần bị ăn mòn. 17 Hình I.2.8. Phép toán Hit or Miss Chú ý rằng trong hình I.2.8(d) và (e), tập tất cả các vị trí mà X hoàn toàn nằm trong A là giao của ảnh gầy A bởi X với ảnh gầy A bởi (W  X ) nhƣ trong hình I.2.8(f). Nói một cách khác nếu ký hiệu B là tập cấu thành lên X và nền của nó, tập các C điểm phù hợp (match) của B trong A, ký hiệu là đƣợc định nghĩa bởi: Chúng ta có thể ký hiệu B(B1,B2), trong đó B1 là tập đƣợc tạo thành từ B và đối tƣợng, còn B2 đƣợc tạo thành từ B và nền. Khi đó, công thức trên có dạng biến đổi khác: 18 I.3. Một số thuật toán dựa trên phép toán hình thái I.3.1. Trích chọn biên Biên của A đƣợc ký hiệu là  ( A) có thể đạt đƣợc bằng cách ban đầu làm gầy A bởi B sau đó thực hiện phép trừ với A . (I.3-1)  () A  A( AB ) với B là phần tử cấu trúc thích hợp. Hình I.3.1. mô tả cơ chế của thuật toán trích chọn biên. Sử dụng thuật toán trên đối với đối tƣợng đơn giản A và phần tử cấu trúc B, kết quả đạt đƣợc là biên của đối tƣợng A nhƣ đã thấy ở hình I.3.1(d). Hình I.3.1. Trích chọn biên Mặc dù phần tử cấu trúc B ở trong ví dụ đƣợc cho bởi hình I.3.1 là một trong các phần tử cấu trúc đƣợc sử dụng nhiều nhất, tuy nhiên, tùy theo đặc điểm của ảnh cần đƣợc trích chọn, mà ta chọn các phần tử cấu trúc khác cho phù hợp. Biên của hình A trong ví dụ này có độ dày là 1 điểm ảnh, nhƣng với phần tử cấu trúc kích thƣớc là 5 x 5, thì biên của A sẽ có độ dày là 2 và 3 điểm ảnh. Nhƣ vậy, với các phần tử cấu trúc khác nhau thì cho ta kết quả khác nhau. Do vậy, việc chọn các phần tử cấu trúc tuỳ thuộc vào mục tiêu cũng nhƣ các ứng dụng cụ thể. Hình I.3.2[26]. cho ta một ứng dụng thuật toán tách biên cụ thể hơn. Trong ví dụ này, phần tử 1 đại diện cho điểm ảnh trắng, phần tử 0 tƣơng ứng với điểm ảnh đen. Do phần tử cấu trúc là phần tử cấu trúc trong ví dụ ở hình I.3.1, cho nên biên của ảnh đạt đƣợc chỉ có kích thƣớc là một điểm ảnh. 19 Hình I.3.2. Ảnh đƣợc trích chọn biên I.3.2. Tô miền Trong hình I.3.3, tập A chứa một tập con mà các phần tử liên thông 8. Xuất phát với một điểm p nằm bên trong, mục tiêu là tô toàn bộ miền có biên bởi các điểm đó. Ta xây dựng thuật toán nhƣ sau: X k  ( X k 1  B)  Ac (I.3-2) Trong đó X 0  p , và B là phần tử cấu trúc đối xứng nhƣ ở trên hình I.3.3. Thuật toán kết thúc tại bƣớc k nếu Xk  Xk1. Miền đƣợc tô chính là hợp của tập A và X k . 20
- Xem thêm -