Luận văn Tìm hiểu phép toán hình thái, phương pháp di truyền và ứng dụng

ả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 II.3.2 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 II.3.1, cho nên biên của ảnh đạt được chỉ có kích thước là một điểm ảnh. Trang 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình II.3.2. Ảnh được trích chọn biên 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: 1( ) c k kX X B A   (I.3-2) Trong đó X0=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à Xk Trang 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình II.3.3. Ví dụ thuật toán tô miền 3.3. Tách các thành phần liên thông Trong rất nhiều ứng dụng, việc phân tích ảnh đòi hỏi ta phải tách các thành phần liên thông để phục vụ cho tác vụ xử lý. Ví dụ như trong ứng dụng nhận dạng mặt người, việc đầu tiên cần phải xử lý là phải tách các thành phần liên thông, sau đó thực hiện việc nhận dạng trên các thành phần đó. Giả sử A chứa thành phần liên thông Y và p là một điểm của Y đã được biết trước. Thuật toán được mô tả bởi phương trình sau: Xk = (Xk-1 B) A k = 1,2,3, .... (I.3-3) Trong đó X0 = p và B là phần tử cấu trúc thích hợp. Nếu Xk= Xk-1 thì thuật toán hội tụ Y = Xk. Phương trình trên trên có cấu trúc giống như phương trình (II.3-2), tuy nhiên trong phương trình (II.3-3), thành phần A tham gia thuật toán, ngược Trang 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên lại, trong phương trình (II.3-2) thành phần bù của tập A tham gia thuật toán. Hình II.3.4. Tìm các thành phần liên thông trong ảnh Thành phần liên thông được sử dụng rộng rãi trong chẩn đoán tự động. Hình II.3.5(a) thể hiện ảnh X quang cấu trúc xương của một con cá. Mục tiêu là phải xác định được vật lạ trong quá trình xử lý cá trước khi đóng gói và gửi đi. Trong trường hợp này, các điểm ảnh thể hiện đối tượng (xương và vật lạ) có mật độ nhiều hơn so với mật độ các điểm ảnh cấu thành nền. Như vậy dẫn tới mức xám của đối tượng so với nền của ảnh sẽ có sự chênh lệch. Bằng cách đưa ra một ngưỡng đơn, ta có thể táchđược đối tượng ra khỏi nền. Kết quả của quá trình tách nền được thể hiện trên hình II.3.5(b). Đặc trưng quan trọng nhất của các hình phía dưới đó chính là các điểm cấu thành xương chứ không phải là các cô lập, các vật lạ. Chúng ta có thể giả thuyết rằng chỉ có các điểm còn lại sau khi ta thực hiện phép toán làm gầy bởi phần tử cấu trúc 5x5 là thành phần của xương. Kết quả của quá trình làm gầy là ảnh II.3.5(c). Chúng ta thực hiện việc đánh nhãn các đối tượng còn lại bằng cách tách các thành phần liên thông. Có tất cả 15 thành phần liên thông trong Trang 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên đó có 3 thành phần bị loại bỏ do kích thước quá nhỏ không có ý nghĩa. Kết hợp với ảnh gốc ban đầu, ta dễ dàng xác định được vị trí của các vật lạ. Hình II.3.5. Xác định vật thể lạ trong ảnh 3.4. Làm mảnh Mảnh của tập A gây bởi phần tử cấu trúc B, được ký hiệu là A  B, được định nghĩa thông qua biến đổi hit-or-miss: A  B = A – (A*B) = A  (A*B) c (II.3-4) Như trong phần trước đã nói, chúng ta chỉ quan tâm đến các mẫu phù hợp với các phần tử cấu trúc, bởi vậy không một phép toán nền nào được yêu cầu trong biến đổi hit-or-miss. Một cách biểu diễn hình học hữu ích cho việc làm mảnh ảnh A là dựa trên dãy các phần tử cấu trúc: {B} = {B1,B2,..., Bn} Trong đó Bi chính là phần tử Bi-1 nhưng được xoay đi. Sử dụng khái niệm này, chúng ta có thể xây dựng quá trình làm mảnh bởi một dãy các phần tử cấu trúc. Trang 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên A ⊗ {B} = ((...(( A⊗ B1) ⊗ B2)...) ⊗ Bn) (II.3-5) Hình II.3.6. Làm mảnh ảnh Quá trình để làm mảnh A bắt đầu bằng việc làm mảnh A bởi B1, sau đó tiếp tục với B2, quá trình làm mảnh kết thúc cho đến khi không có sự thay đổi nào xảy ra. Hình II.3.6(a) thể hiện tập tất cả các phần tử cấu trúc thường được sử dụng cho quá trình làm mảnh và II.3.6(b) biểu diễn ảnh A sau khi được làm mảnh bởi dãy các phần tử cấu trúc trong hình II.3.6(a). 3.5. Làm dầy Quá trình làm dầy một ảnh được thể hiện bởi công thức (I.3-6) Trong đó B là phần tử cấu trúc phù hợp. Tương tự như quá trình làm Trang 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên mảnh, làm dầy có thể được định nghĩa dưới dạng một dãy các phép toán. A ⊙ {B} = ((...(( A⊙ B1) ⊙ B2)...) ⊙ Bn) (I.3-7) Các phần tử cấu trúc được sử dụng trong phép toán làm dầy có cùng cấu trúc như các phần tử cấu trúc trong hình II.3.6(a), nhưng có sự chuyển đổi giá trị tại mỗi điểm ảnh. Nói cách khác là tương phản của nhau. Tuy nhiên thuật toán làm dầy hiếm khi được sử dụng trong thực tế. Thay vào đó người ta thường làm mảnh nền của ảnh để thu được hiệu quả làm dầy ảnh. Hình II.3.7. Làm dầy ảnh 3.6. Tìm xƣơng của ảnh Như trong hình (II.3.8) ký hiệu xương là S A( ) . Xương của ảnh A có thể được biểu diễn dưới tập các phép toán làm gầy kết hợp với phép toán opening: 0 ( ) ( ) K k i S A S A   (II.3-8) với ( ) ( ) ( )kS A A kB A kB B     (II.3-9) Trong đó B là phần tử cấu trúc và Trang 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( ) (...( ) ) ...)A kB A B B B      (II.3-10) với K là bước áp dụng cuối cùng trước khi A bị suy biến thành tập rỗng. Hay nói cách khác thì: K= max{k|(A  kB)  } (II.3-11) Hình II.3.8. Tìm xương của ảnh Công thức cho bởi hai phương trình trên thể hiện rằng S(A) có thể đạt được bằng cách lấy hợp của các tập xương con Sk(A) . Nó cũng chỉ ra rằng A có thể được xây dựng lại từ các tập con này bằng cách sử dụng phương trình 0 ( ( ) ) K k i A S A kB    (II.3-12) Trang 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG III. THUẬT TOÁN DI TRUYỀN 1. Thuật toán di truyền là gì? Có rất nhiều bài toán tối ưu mà người ta chưa tìm được thuật toán đa thức để giải quyết chúng ví dụ như bài toán xếp lịch, bài toán sắp xếp đồ vật hay các bài toán quy hoạch. Đối với các bài toán dạng này, người ta thường tìm một lời giải cho kết quả chấp nhận được. Với một số bài toán quy hoạch khó, ta cũng có thể dùng các thuật toán xác suất, những thuật toán này không đảm bảo cho ra kết quả tối ưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều “bằng chứng”, ta có thể giảm tùy thích xác suất sai của kết quả. Nói một cách trừu tượng, việc giải một bài toán có thể xem như việc tìm kiếm trong một không gian các lời giải có thể. Vì cái đích của chúng ta là “lời giải tốt nhất”, ta có thể coi công việc này là một quá trình tối ưu hóa. Đối với không gian nhỏ, phương pháp “vét cạn” cổ điển là đủ dùng; còn những không gian lớn hơn đòi hỏi các phương pháp trí tuệ nhân tạo đặc biệt. Các thuật toán di truyền nằm trong số các phương pháp đặc biệt đó. 2. Sử dụng thuật toán di truyền trong toán học hình thái Thuật toán di truyền là một trong những kỹ thuật phổ biến trong các bài toán hình thái có những ràng buộc yêu cần việc tối ưu hóa một tiêu chuẩn nào đó. Ngoài bài toán phân rã phần tử cấu trúc sẽ được trình bày chi tiết trong chương 3, người ta còn dùng thuật toán di truyền trong việc thiết kế các bộ lọc cho ảnh đa cấp xám và thiết kế các giải thuật đối với các ảnh nhị phân. Hơn nữa MM còn cung cấp các nền tảng cho việc phát triển giả thuyết di truyền. Chúng ta sẽ mô tả những ý tưởng đó như sau: Phân rã phần tử cấu trúc Một phần tử cấu trúc có thể được phân rã thành các phần tử cấu trúc có kích thước nhỏ hơn. Điều này rất có ích trong một số ứng dụng như: lưu trữ Trang 38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên hay tăng tốc độ tính toán. Thiết kế các bộ lọc cho ảnh đa cấp xám Thiết kế bộ lọc cho ảnh đa cấp xám là một bài toán tối ưu khó giải bằng thuật toán đa thức. Các tác giả Harvay và Marshall trong tài liệu [21,22,23,24] đã trình bày một cách tiếp cận thuật toán di truyền trong việc thiết kế bộ lọc ảnh đa cấp xám. Hơn nữa, nghiên cứu đó đã dẫn tới một cách tiếp cận mang tính cách mạng trong việc thiết kế giải thuật hình thái để tìm một dãy các phép toán hình thái phù hợp. Thiết kế giải thuật hình thái cho ảnh nhị phân Yu [25] đã trình bày một cách tiếp cận đơn giản cho bài toán phân đoạn ảnh sử dụng thuật toán di truyền. Ảnh được xem như là một tập hợp các đối tượng được nhúng vào một nền thuần nhất và bị gây nhiễu. Quá trình phân đoạn ảnh được thực hiện trên các ảnh 16x16 không chồng lấn. Các ảnh con sau khi được phân đoạn sẽ được kết hợp lại với nhau để đưa ra được phân đoạn lớn của ảnh. Hàm thích nghi đo độ tương tự của mỗi cá thể ảnh đối với ảnh gốc ban đầu. Nó cũng bao gồm cả hàm phạt để giảm tần số nhiễu trong các kết quả được phân đoạn. 3. Hoạt động của thuật toán di truyền Hoạt động của thuật toán di truyền dựa trên thuyết chọn lọc tự nhiên. Theo thuyết này thì quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất. Quá trình tiến hóa diễn ra trên nhiều thế hệ, thế hệ sau được sinh ra thường tốt hơn thế hệ trước do được kế thừa những mặt tốt của bố mẹ. Xuất phát từ ý tưởng đó, thuật toán di truyền đã được ra đời, kế thừa những tư tưởng của lý thuyết chọn lọc tự nhiên. Chúng ta sẽ nói về các “cá thể” trong một quần thể: thường thì các cá thể này còn được gọi là xâu hoặc nhiễm sắc thể. Mỗi tế bào trong cơ thể của một loại nào đó chứa một số nhất định nhiễm sắc thể (ví dụ Trang 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên trong cơ thể người có 46 nhiễm sắc thể); tuy nhiên, trong bài này thì ta chỉ nói về các cá thể chỉ chứa đúng một nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm các đơn vị - gen – xếp liên tiếp; mỗi gen điều khiển sự thừa kế của một hoặc vài tính trạng. Gen của tính trạng nhất định có vị trí xác định trên nhiễm sắc thể, vị trí đó được gọi là loci (vị trí trên xâu). Một tính trạng bất kỳ (thí dụ màu mắt) có thể được thể hiện với nhiều mức độ khác nhau; ta nói gen đó có nhiều trạng thái (gọi là allete). Mỗi nhiễm sắc thể (cá thể) sẽ biểu thị một lời giải có thể của một bài toán (ý nghĩa của mỗi nhiễm sắc thể, nghĩa là kiểu gen của nó, được quy ước bởi người lập trình); một qúa trình tiến hóa được thực hiện trên một quần thể nhiễm sắc thể là tương đương với sự tìm kiếm trong một không gian các lời giải có thể. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục đích: khai thác lời giải tốt nhất và khám phá không gian tìm kiếm. Phương pháp “leo núi” là một ví dụ về chiến lược khai thác lời giải tốt nhất theo các hướng cải tiến. Tìm kiếm ngẫu nhiên là một ví dụ điển hình của sự khám phá không gian tìm kiếm, không chú trọng khai thác các miền hứa hẹn trong không gian tìm kiếm. Thuật toán di truyền là lớp các phương pháp tìm kiếm tổng quát (không phụ thuộc vào miền xác định) với sự cân bằng đáng kể giữa khai thác và khám phá không gian tìm kiếm. Trang 40 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình III.1. Mô phỏng quá trình tiến hóa Thuật toán dị truyền, cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể được xem như là một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa thể hiển tính tối ưu ở chỗ, thế hệ sau Trang 41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hóa tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn được sinh ra để bổ xung và thay thế thế hệ cũ. Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình tiến hóa. Ngược lại, tiến hóa cũng tác động trở lại góp phần làm thay đổi môi trường. Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong quá trình tiến hóa nhờ sự lai ghép ở thế hệ cha mẹ. Một các thể mới có thể mang những tính trạng của cha mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới (đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến hóa, dù rằng đột biến xay ra với xác xuất nhỏ hơn nhiều so với hiện tượng di truyền. Các thuật toán tiến hóa, tuy có những đặc điểm khác biết, nhưng đề mô phỏng bốn quá trình cơ bản: Lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. Như vậy quá trình tiến hóa càng lâu thì càng có điều kiện cho các cá thể tốt được sinh ra, và chất lượng của các cá thể càng được nâng lên. 3.1. Quá trình lai ghép (phép lai) Phép lai là quá trình hình thành nhiếm sắc thể mới trên cơ sở các nhiễm sắc thể của cha mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều) nhiễm sắc thể cha mẹ với nhau. Lai ghép một điểm Trên nhiễm sắc thể của cơ thể cha mẹ sẽ chọn ra một vị trí (điểm lai). Dữ liệu ở các phía của điểm lai sẽ được hoán chuyển cho nhau giữa hai nhiễm sắc thể của cha mẹ. Kết quả ta sẽ có nhiễm sắc thể của thế hệ con. Trang 42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình III.2. Lai ghép một điểm Lai ghép hai điểm Trên cơ thể của cha mẹ được xác định hai điểm lai ghép. Mọi dữ liệu giữa hai điểm lai ghép đó được hoán đổi cho nhau trong nhiễm sắc thể của hai cha mẹ, tạo ra hai nhiễm sắc thể của thế hệ con Hình II.3. Lai ghép hai điểm Cắt và ghép Không giống như hai kiểu trên, với phương pháp lai “cắt và ghép” cho ta kết quả hai cơ thể con có độ dài nhiễm sắc thể khác nhau, lý do của sự khác biệt này chính là mỗi nhiễm sắc thể của cha mẹ đều có điểm lai khác nhau. Trang 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ví dụ về phép lai Ví dụ về một phép lại một điểm với xác suất Pc có thể mô phỏng như sau: Hình III.5. Ví dụ về phép lai - Chọn ngẫu nhiên hai (hay nhiều) các thể bất kì trong quần thể. Giả sử các nhiễm sắc thể của cha mẹ đều có m gen. - Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1 (ta gọi là điểm lai). Điểm lai chia các chuỗi cha mẹ dài m thành 2 nhóm chuỗi con dài m1 và m2. Hai chuỗi nhiễm sắc thể con mới sẽ là m11+m22 và m12+m21. - Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hóa tiếp theo. Trang 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3.2. Quá trình đột biến (phép đột biến) Đột biến là hiện tượng cá thể con mang một số tính trạng không có trong mã di truyền của cha mẹ. Mục đích của phép đột biến trong thuật toán di truyền là giúp cho thuật toán tránh được các cực trị cục bộ. Phép đột biến xảy ra với xác suất Pm nhỏ hơn rất nhiều so với xác suất Pc. Một phép đột biến có thể mô phỏng như sau: Hình III.6 Đột biến tại bít thứ 6 - Chọn ngẫu nhiên một cá thể cha mẹ bất kì trong quần thể. - Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤k≤m). - Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hóa tiếp theo. 3.3. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn) Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở độ thích nghi của nó. Còn phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để giữ lại trong quần thể các cá thể tốt. Phép chọn lọc có thể mô phỏng như sau: - Sắp xếp quần thể theo thứ tự độ tốt giảm dần. - Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể có độ thích nghi tốt nhất, ở đây ta giả sử quần thể có kích thước cố định m. 4. Mô hình thuật toán Trang 45 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trang 46 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình III.7. Mô tả hoạt động thuật toán Điều kiện kết thúc thuật toán thường bao gồm: Số lượng thế hệ được sinh ra. Một cá thể thỏa mãn các tiêu chuẩn của bài toán. Giá trị thích nghi cao nhất của cá thể được tìm thấy. Trang 47 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG IV. 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 Trong một số hệ thống song song cổ điển thì việc sử dụng các phần tử cấu trúc lớn là không hiệu quả, ví dụ như trên hệ thống SIMD, chỉ cho phép thực hiện các phép toán trên các lân cận nhỏ hơn nhiều so với kích thước của phần tử cấu trúc; hoặc các đặc trưng khác nhau của những hệ thống mục đích chung (serial) và hệ thống song song, yêu cầu những kỹ thuật khác nhau để phát huy những tính chất phần cứng đặc thù của mỗi hệ thống. Định nghĩa 1. Cho một tập các phần tử cấu trúc cơ bản Fi {i=1,..,M}. Phần tử cấu trúc B được gọi là lồi trên tập Fi đối với phép toán dãn ảnh nếu như B có thể biểu diễn được dưới dạng một chuỗi các phép toán làm béo liên tiếp trên tập các phần tử cấu trúc cơ bản. 1 2 3 ...k k k kmB F F F F     , với kj  [1..M], cho j=1,...,m (1) Ngược lại nếu B không thể biểu diễn dưới dạng chuỗi các phép toán dãn ảnh trên tập phần tử cấu trúc cho trước thì B được gọi là không lồi. Trong trường hợp này b có thể được biểu diễn dưới dạng: 1 2 3 ...... ZB C C C C     (2)  đại diện cho một phép toán boolean nào đó ví dụ như phép hợp hay phép giao. Trong phần này, chúng tôi đề cập đến vấn đề sử dụng cách tiếp cận ngẫu nhiên dựa trên thuật toán di truyền: bắt đầu từ một tập quần thể (các cá thể) của các lời giải có khả năng được xác định thông qua thuật toán vét cạn, một quá trình lặp biến đổi các cá thể hiện tại và/hoặc tạo ra các cá thể mới phù hợp với tập các toán tử di truyền được áp dụng một cách ngẫu nhiên. Các cá thể tối thiểu hóa hàm giá có xu hướng thay thế các cá thể khác và sau một Trang 48 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên số bước lặp đủ lớn, thì thuật toán có xu hướng hội tụ tới lời giải tối ưu. Trong thực tế, mục đích chính của công việc này chính là để phát triển công cụ có thể cho câu trả lời sơ bộ về vấn đề phân rã tối ưu của tập các phần tử cấu trúc không lồi thành chuỗi các phép toán cơ sở. Một số tính chất quan trọng của phép toán dãn ảnh ( ) ( ) ( )A B C A B A C      ( ) ( ) ( )A B C A B A C      Như vậy, các phần tử cấu trúc không lồi được phân rã sử dụng chuỗi phép hợp của tập phần tử cấu trúc lồi. Dưới đây ta sẽ xét một ví dụ chứng tỏ sự ưu việt của việc phân rã các phần tử cấu trúc lớn thành các phần tử cấu trúc nhỏ hơn. Trong phép toán dãn ảnh để thực hiện phép dãn ảnh A  B ta phải cần thực hiện card(A)*card(B) phép toán. Giả sử A , B lần lượt là ma trận (3) Số phép toán cần thực hiện là 15.12=180 phép toán Nhưng nếu bằng cách nào đó ta có thể phân rã tập B thành 2 tập con nhỏ hơn như ví dụ dưới đây: Và sử dụng luật kết hợp: 1 2 1 2 2( ) ( )R A B A B B A B B R B          (4) Trang 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trong đó: Như vậy số phép tính để tính là: 15*3+25*4=145. Ta xét một ví dụ khác đối với các phần tử cấu trúc không lồi. Như phần trước đã trình bày, phần tử B không lồi có thể được biểu diễn thành chuỗi các phần tử cấu trúc cơ bản liên kết với nhau bởi phép toán dãn ảnh và phép toán logic. 1 2B C C  (5) (6) Trong đó, C1, C2 là các tập lồi trên tập các phần tử cấu trúc cơ bản cho trước IS. (7) Do vậy, theo cách này, phép toán dãn ảnh của phần tử cấu trúc B tác động lên ảnh A 1 2( )R A B A C C     (8) có thể được thực hiện với 6 phép dãn cơ bản và 1 phép hợp logic. Đây là giải pháp 1 mức, chỉ bao gồm một mức đơn của hợp các phép dãn, hay còn gọi là tổng của các phép nhân. Hiển nhiên rằng, giải pháp đa mức có thể dẫn đến một kết quả tốt hơn. Trang 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ví dụ việc sử dụng tính chất quy tắc của chuỗi R= A  B có thể được biểu diễn theo giải pháp hai mức: (9) Giải pháp được mô tả ở trên chỉ đòi hỏi 5 phép dãn ảnh và một phép hợp logic. Một ứng dụng khác có thể liệt kê ra ở đây đó chính là việc lưu trữ. Ví dụ như ta có một ảnh thể hiện một nét bút. Thay vì việc ta lưu trữ toàn bộ ảnh của nét bút đó, ta chỉ cần lưu trữ các thành phần của nó. Một ví dụ khác, giả sử ta muốn lưu trữ hình một chiếc bút, ta phân chia thành ba phần khác nhau: đầu bút, thân bút và cuối bút. Ta xét thân bút để thấy rõ tại sao ta có thể lưu trữ chiếc bút với ít bộ nhớ hơn. Do thân bút là bộ phận đều nhất theo nghĩa hình khối, thay vì ta lưu trữ cả thân bút, ta chỉ cần lưu giữ chiều dài và chiều rộng của thân bút. Như vậy tiết kiệm được không gian lưu trữ. Qua các ví dụ ở trên, ta có thể thấy việc phân rã của các phần tử cấu trúc có thể nhằm vào nhiều mục đích khác nhau như: - Cực tiểu số các tập phân rã (để rút gọn số các phép dãn ảnh) - Cực tiểu tổng số phép tính toán (nâng cao tốc độ); - Cực tiểu tổng số phần tử trong tập phân rã (giảm kích cỡ cấu trúc dữ liệu và do đó cũng giảm đòi hỏi về bộ nhớ trong hệ thống tuần tự; Trang 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Khả năng cài đặt các phép toán hình thái phức tạp trện các hệ thống song song mà tập các chỉ dẫn của nó được dựa vào phép toán cơ sở đơn giản (để khắc phục vấn đề bị gây ra bởi kết nối tôpô bên trong mà nó giới hạn kích thước các phần tử cấu trúc có thể có). Hoặc thậm chí là việc xác định các nhân tử với hình dạng đã cho (nhằm trợ giúp cho việc nhận dạng các đối tượng hai chiều). Tiêu chuẩn tối ưu được nói tới trong luận văn này có thể thay đổi do tác động các tham biến của hàm mục tiêu. 1. Tiếp cận ngẫu nhiên Thuật toán di truyền (GAs) được sử dụng rộng rãi trong nhiều lĩnh vực, là thuật toán tối ưu dựa trên thuật toán ngẫu nhiên, các toán tử di truyền trên quần thể là các giải pháp có thể có của vấn đề được xem xét (các cá thể). Cấu trúc dữ liệu chính là bộ gen (Genome) và nhiễm sắc thể (Chromosome) - là tập bao gồm tập các Gen (Genes) và giá trị thích nghi (Fitness value). Trong quần thể các lời giải có thể có, tập các cá thể mới được tạo ra bởi toán tử di truyền được gọi l cá thể con. Để đánh giá các cá thể trong mỗi thế hệ một hàm thích nghi được định nghĩa để đo độ “thích nghi” của cá thể đó. Mỗi cá thể được cho là sẽ đem lại một độ đo thích hợp về hệ số thích nghi của nó, có nghĩa là “mặt tốt” của lời giải mà nó biểu diễn. Tại mỗi phép lặp (thế hệ) việc đánh giá hệ số thích nghi được thực hiện trên tất cả các cá thể. Nên ở tại bước lặp tiếp theo, quần thể mới được sinh ra, bắt đầu từ các cá thể có sự thích nghi cao nhất và thay thế hoàn toàn hoặc một bộ phận của thế hệ trước. Các toán tử di truyền đã được sử dụng để tạo ra các cá thể mới được chia nhỏ thành hai phạm trù chính: phép toán một ngôi (unary) tạo ra các cá thể mới, thay thế các cá thể hiện tại với kiểu đã được thay đổi (chẳng hạn như đột biến, sự thay đổi ngẫu nhiên của gene), và phép toán hai ngôi (binary), tạo ra cá thể mới thông qua việc Trang 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên kết hợp dữ liệu của hai cá thể (ví dụ như lai ghép, trao đổi nhiễm sắc thể giữa hai cá thể). Mỗi bước lặp được gọi là một thế hệ. Việc nghiên cứu thuật toán GAs dẫn đến nhiều chương trình tiến hoá tổng quát (EPs) hơn , hay tổng quát hoá GAs. Trong các GAs chuẩn, một cá thể được biểu diễn bởi bằng xâu nhị phân có độ dài cố định, mã hoá tập tham số tương ứng với lời giải mà nó biểu diễn; toán tử di truyền tác động lên các mã nhị phân này. Trong chương trình tiến hoá, các cá thể được biểu diễn bởi cấu trúc dữ liệu tổng quát hoá mà không có sự bắt buộc về độ dài cố định. 2. Cấu trúc dữ liệu Như phát biểu ở trên, cấu trúc dữ liệu biểu diễn một cá thể cần phải mô tả theo cách mềm dẻo là hợp các phần tử lồi như trong, cần phải chỉ ra hình dạng của nó và sự phân rã thành các phần tử (factors), nhưng cũng cần tạo ra pha đánh giá nhanh và đơn giản. Biểu diễn này biến đổi theo độ dài, vì số z các phân hoạch bao gồm việc phân rã nhiễm sắc thể J không bị chặn trên; mặt khác nhắc lại biểu thức (1), số m và hình dạng nhân tử Fkj tạo nên thành phần Ckj phụ thuộc trực tiếp vào Ck. Vì những lý do này, một cá thể được biểu diễn bằng chuỗi gen dài tuỳ ý, mỗi gen biểu diễn một phân hoạch của phần tử cấu trúc đầu vào (xem hình IV.1). Hợp lôgic của tất cả các gen tạo nên cá thể. Việc cài đặt đơn giản nhất bao gồm việc biểu diễn mỗi cá thể riêng với cấu trúc dữ liệu mà các trường của nó chứa toàn bộ các thông tin ở trên. Ngược lại, cấu trúc dữ liệu phân cấp phức tạp hơn được phát triển để vừa sử dụng dung lượng nhớ thấp hơn cho mỗi cá thể vừa làm dễ dàng và tăng tốc độ xác định các lời giải mới tốt hơn. Mặc dù việc quản lý cấu trúc dữ liệu này rõ ràng là phức tạp nhưng nó cho phép phát hiện phần giao nhau có thể có trong số các cá thể của quần thể. Mỗi mức phân cấp chỉ giải mã các thông tin thật Trang 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên sự cần thiết cho mức độ đó. Ba mức phân cấp được chỉ ra trong Hình IV.1. Mức phần tử (Factor level): Các thành phần cơ bản là các toán tử hình thái cơ sở (tức các thành phần của tập chỉ dẫn): Một số nguyên cho biết phần tử nào của tập chỉ dẫn được sử dụng, trong khi con trỏ cho phép đi theo chuỗi các phần tử. Mức độ gen (Gen level): Một gen gồm một hay nhiều các nhân tử (factors) và ó tương ứng với một chuỗi các phép dãn của các nhân tử; một số nguyên chỉ ra gốc của phân hoạch được mô tả bởi gen, vì vậy nó chỉ ra phép dịch chuyển được yêu cầu để khớp gen lên tập các phần tử cấu trúc khởi tạo và một con trỏ xác định gen tiếp theo. Mức độ cá thể (Individual level): Một hay nhiều gen sẽ hình thành cá thể tươngứng với một phép hợp của chuỗi các phép dãn, tương đương với việc phân rã, hoặc thông thường hơn, đối với một phần của sự phân rã. Số nguyên chỉ tổng số các gen hợp thành cá thể, con trỏ chỉ ra vị trí của gen đầu tiên của chuỗi, trong khi số chính xác gấp đôi chứa giá trị thích nghi của cá thể. Khởi tạo quần thể Định nghĩa 1: Tập IS là tập bao gồm M phần tử tử IS = {Fi, i=1,..,M}. Tập IS trong đa trường hợp là biểu diễn các cấu trúc hình khối hoặc các cấu trúc được chéo hoá. Việc sử dụng các cấu trúc hình khối hoặc được chéo hoá sẽ tiết kiệm được không gian lưu trữ và đồng thời giảm được số phép toán cần thực hiện trong các hệ thống đòi hỏi thao tác trên các ma trậm cỡ lớn. Định nghĩa 2: Ký hiệu H(x,y) thay cho H  {(x,y)} Trang 54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình IV.1. Cấu trúc dữ liệu Định nghĩa 3: Cho ảnh di truyền H. Ký hiệu ...nHAH H  (n thành phần, n≥0) Định nghĩa 4: Cho ảnh di truyền H, OH biểu diễn gốc cuả ảnh di truyền H. Dưới đây, B là phần tử cấu trúc đầu vào, Bi là tập con di truyền của B với gốc giống nhau và H đại diện cho bất kỳ tập di truyền nào, lồi tương ứng với tập chỉ dẫn (IS). 1 1 2 2... ...i i M MH q F q F q F q F   (10) Nếu OFi Fi đối với mỗi Fi thuộc tập chỉ dẫn, thì OH H. Việc xử lý bắt đầu bằng cách nhận dạng mỗi phần tử của tập hợp C(B), được xác định như sau: (h,k)( ){H|HC B B đối với vài (h,k)} (11) Trang 55 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Vì mỗi phần tử của C(B) có thể đại diện cho một gen có thể có, việc tìm kiếm này phải được xác định và vét cạn. Vì OFiFi, tập các cặp có thể (h,k) được cho bởi tập tất cả những phần tử của B; đối với một ảnh di truyền H, nếu cặp (h,k) B H, thì H(h,k)  C(B). Vì vậy, thuật toán sẽ duyệt tất cả các điểm ảnh của phần tử cấu trúc và xác định những phần tử nào có thể tạo nên chuỗi phép toán dãn nở hợp lý từ điểm ảnh đó. Xây dựng hàm thích nghi Hàm thích nghi f(I) được sử dụng để đánh giá mỗi cá thể I trong thuật toán tìm kiếm. Giả sử I được phân rã thành n phép hợp của các phần tử cấu trúc hình khối B B1, ,...,2Bn thì: 1 ( ) ( ) n i i f I f B   với f(Bi) = (k+l) * AConst (12) Trong đó AConst là một hằng số, đại lượng này sẽ tùy thuộc vào cỡ của ma trận đem làm dầy với ma trận cấu trúc B ban đầu, (k,l) là cỡ của ma trận Bi. Trong cài đặt này, mỗi nhân tử bị giới hạn kích cỡ 3x3 và OFi Fi Để đánh giá một cá thể I, ta dựa trên khái niệm hàm giá fC(I). fC(I) = f(I) nếu và chỉ nếu B = { |i= 1, 2,... } , Bi là phân hoạch chung tạo nên lời giải I của độ dài N. Hàm như vậy phải có một số tính chất sau: 1)Đối với lời giải phù hợp thì nó bằng f(I); 2)Nó cũng được xác định cho những lời giải không phù hợp (tức là những lời giải không phủ hoàn toàn phần tử cấu trúc gốc), do vậy mở rộng không gian tìm kiếm; 3)Dễ dàng cài đặt như hàm phạt. Hàm phạt được sử dụng trong các bài toán có ràng buộc cao, khi nhu Trang 56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên cầu của việc đánh giá những lời giải không phù hợp bằng cách phạt chúng đồng thời đề cao những lời giải phù hợp. Như vậy, hàm giá bao gồm hệ số phạt: fc = af(I) + bfp(I) (13) ở đây, a = 1 nếu và chỉ nếu Bi = B(B={Bi|i=1,2,...N)}), như phát biểu trên, ngược lại a có thể được biểu diễn bởi một phân số đối với tỉ số giữa số lượng các phần tử có mặt trong lời giải và tổng các phần tử có trong B. Qua các tham số do người sử dụng định nghĩa, hệ số b có liên hệ với kích cỡ của quần thể hiện tại, và fp là hàm phạt liên hệ với số phần trăm phủ B. Như ta đã nói mục đích của việc xử lý là nhận được sự phân rã làm cực tiểu số các phép tính cần thiết để tính các phép dãn của một ảnh di truyền với phần tử cấu trúc B, hàm thích nghi f(I) chủ yếu được cấu tạo bởi tổng giá của mỗi phân hoạch Bj; thêm vào đó, cũng cần tính đến số phép toán hợp lôgic được yêu cầu và làm nặng lên bởi một hệ số thích hợp. 3. Giải thuật dựa trên thuật toán tìm kiếm di truyền Cấu trúc của thuật toán được và chu trình xử lý đơn gồm 4 giai đoạn: + Khởi tạo tập các cá thể con ban đầu; + Toán tử lựa chọn: Lựa chọn hai cá thể trong quần thể vì mục đích tái tạo; + Toán tử di truyền hai ngôi: Kết hợp theo các cách khác nhau, các nhiễm sắc thể của cha và mẹ để nhận được con (tức là một hoặc hai con); + Các toán tử so sánh: lập phép đấu giữa thế cha mẹ và thế hệ con để chọn ra cá thể tốt nhất cho thế hệ tiếp theo; Giải thuật có thể có điều kiện dừng khác nhau, có thể việc lựa chọn ra hai cá thể với mục đích tái tạo dựa trên phép toán vét cạn, tức là mỗi cá thể đã Trang 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên được lựa chọn để tái sinh, quần thể vừa mới được tạo ra trải qua cùng một cách xử lý giống nhau: Quá trình hình thành các thế hệ này ngừng khi số thế hệ đã đạt tới một giá trị cực đại. Mặt khác ta có thể chia không gian cá thể tại mỗi thế hệ thành một số tập con rồi sau đó thực hiện lựa chọn ngẫu nhiên một số cá thể con trong tập được phân chia. Việc phân chia đó để đảm bảo tính ngẫu nhiên của thuật toán. Dưới đây tóm tắt lại các toán tử đã được trình bày: Khởi tạo tập cá thể con ban đầu Các cá thể con ở thế hệ thứ nhất chính là tập IS ban đầu. Nhớ rằng tập IS này là tập các phần tử cấu trúc hình khối. Đối với ảnh nhị phân B ban đầu, tập các cá thể khối là con của tập B có thể được tìm kiếm bằng cách duyệt từng điểm ảnh của B và tìm tất cả các cấu trúc hình khối có thể được xây dựng từ điểm gốc đó. Đối với các ma trận kích thước lớn, ta có thể lựa chọn ngẫu nhiên một số điểm ảnh trong ma trận B, từ các điểm ảnh đó ta sẽ xác định các cá thể ban đầu. Toán tử lựa chọn Trong bài , nhóm tác giả Giovanni Anelli, Alberto broggi và Giulioi Destri đưa ra toán tử dựa trên sơ đồ lựa chọn thi đấu như đã được đưa ra trong luận án tiến sỹ của tác giả R. Van Den Boomgard “Extension toward Computer vision, PhD thesis” với kích thước vòng đấu của hai bên. Sơ đồ cài đặt tận dụng một phiên bản được hiệu chỉnh nhỏ của kỹ thuật đám đông lựa chọn di truyền (genic selective crowding) buộc các cá thể thi đấu với cá thể khác có ít nhất các điểm ảnh chung. Theo cách như vậy, một áp lực được duy trì làm cho đối tượng giống nhau thi đấu với đối tượng giống nhau, và bằng cách này làm tăng ý nghĩa của vòng đấu. Tuy nhiên cách tiếp cận này, theo tôi là khó cài đặt và tốc độ hội tụ chậm do tính tổng quát của nó. Nhớ lại rằng Trang 58 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên mục đích của chúng ta là phân rã ảnh nhị phân thành tổng các thành phần khối hoặc các thành phần chéo hoá và từ các thành phần này ta sẽ xây dựng được dãy tích các thành phần cấu trúc cơ bản phục vụ cho việc lưu trữ hoặc trong việc tăng tốc độ tính toán. Vì vậy, theo tôi các cá thể ban đầu là tối quan trọng, tại mỗi thế hệ để đảm bảo thuật toán có thể đi tới một kết quả chấp nhận được thì việc lai tạo giữa cá thể hiện thời với các cá thể ở thế hệ thứ nhất như là một đảm bảo thế hệ tiếp theo sau tốt hơn thế hệ hiện thời. Các toán tử di truyền hai ngôi Để nhận được các cá thể phủ phần tử cấu trúc trong pha khởi tạo, chúng ta cần một toán tử biến đổi một cách đáng kể độ dài các nhiễm sắc thể của cá thể. Ngược lại, sau pha này khi độ dài trung bình của các cá thể xấp xỉ với cá thể tối ưu, chúng ta quan tâm về chất lượng của nhiễm sắc thể; vì lý do này, hai toán tử khác nhau đã được hình thành. Toán tử đầu tiên dựa trên toán tử cắt và ghép nối. Cho λ là số gen tạo nên nhiễm sắc thể: Toán tử này cắt ngẫu nhiên nhiễm sắc thể tương ứng với một trong λ điểm có thể. Nếu một trong λ-1 điểm nối hai gen liên tục được chọn, thì nhiễm sắc thể bị tách thành hai phần; ngược lại với xác suất 1/λ, không thay đổi. Hai, ba hoặc bốn đoạn nhiễm sắc thể của hai cá thể khác nhau được đặt trong ngăn xếp (stack); giai đoạn lai ghép hoặc hợp hai phần tử đầu tiên ở đỉnh ngăn xếp này theo cách này tạo nên một con đơn nhất, hoặc cải biến mỗi phần tử thành cá thể đầy đủ. Điều này chỉ ra cách mà số cá thể trong thế hệ theo sau có thể được thay đổi. Ví dụ được chỉ ra trong hình IV.2 Trang 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình IV.2 Ví dụ về cắt và ghép nối (a)Lai ghép thay thế, (b)Các toán tử Toán tử so sánh Ở giai đoạn này toán tử lựa chọn trong số các bố mẹ và con những cá thể được chèn vào trong thế hệ tiếp theo.Trong [8], tác giả X. Zhuang và R.M. Haralick đưa ra một sơ đồ dựa trên sơ đồ đa số quyết định. Toán tử di truyền một ngôi Trong GA chuẩn toán tử một ngôi là sự đột biến, nó chỉ đảo ngẫu nhiên một hay nhiều bit của xâu biểu diễn nhiễm sắc thể. Mặt khác cài đặt của chúng ta về phép đột biến có mục tiêu chủ yếu là chèn lại các gen đã bị bỏ trước đó và những gen bị mất; Tiêu biểu đây là trường hợp phân hoạch nhỏ mà sự đóng góp của nó để cải thiện hệ số thích nghi bị đánh giá thấp trong pha thực hiện trước. Đóng góp này có thể là cần sau này để đạt được phủ của toàn bộ B. Gen được rút ra từ mảng gen (chứa tất cả các gen có thể) và được lưu trữ trong bộ nhớ để cho mỗi gen được lựa chọn theo chu kỳ. Hai toán tử đã được tạo: Đột biến 1: Toán tử này so sánh mỗi gen tạo ra nhiễm sắc thể của các cá thể với gen g của mảng. Gen g thay thế một gen giống nhất trong chuỗi, đó là gen làm cực đại phần giao giữa hai gen như ví dụ dưới đây. Trang 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Đột biến 2: Toán tử này buộc gen g phải được tính đến việc loại bỏ các gen trùng lên nó. Nó có thể làm cho kém thích nghi nhưng nó có lợi để tăng sự đa dạng của nhiễm sắc thể như trong ví dụ dưới đây Giả sử ta có phần tử cấu trúc B được định nghĩa : {( , , ( , )) : 1, , 1, }B x y f x y x m y n   trong đó: 2( , ) : {0,1}f x y Z  Ta xây dựng mã giả của thuật toán như sau: Mã giả (presedo-code) //initialize population P:={}; For each (x,y) in B : Determine Trange={T:T is trange and T  B }; Add(P,T);// add all the elements of T to P //Choose randomly a number of elements in P Initilize randomly Q = { :q q P} ; numGen=0; Loop until numGen> threshold Choose some(A,B)  Q2: Make offspring A1,A2,B1,B2 between A and Trang 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên B Calculate fitness values of A1,A2,B1,B2 Add A1,A2,B1,B2 into current genration Q:={}, Choose the best individuals in current generation to make next generation numGen++; if(best(individual)= =B) exit; End Loop; Print best(individual); Trang 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG V. THỰC NGHIỆM Trong chương này, tôi sẽ trình bày cấu trúc của chương trình thực nghiệm và một số kết quả dựa trên thuật toán đã đưa ra trong chương IV 1. Mô tả bài toán và giả thuyết Ma trận phần tử cấu trúc đầu vào là ma trận có kích thước mxn được nhập từ file. Cấu trúc của file được mô tả dưới đây: - Dòng đầu bao gồm 2 số nguyên thể hiện kích thước của ma trận - Bắt đầu từ dòng thứ 2 đến dòng thứ n biểu diễn các giá trị tại mỗi điểm ảnh. Các giá trị điểm ảnh được phân biệt với nhau bởi dấu tab. Với giả thuyết phân rã ma trận cấu trúc ban đầu thành các phần tử cấu trúc kích thước 3x3. Kết quả cũng được lưu trữ dưới dạng file. 2. Giao diện chính của chƣơng trình Bước đầu, người dùng cần nhập vào file chứa thông tin về phần tử cấu trúc bằng cách nhấp vào nút “Nhập từ file” trên màn hình giao diện, sau đó chỉ tới nơi chứa file text chứa ma trận đầu vào. Sau khi kết thúc phần chọn file dữ liệu đầu vào, người dùng chọn các Trang 63 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tùy chọn, bao gồm: số thế hệ cá thể được sinh ra, số lượng cá thể lấy ngẫu nhiên tại mỗi thế hệ để thực hiện việc tạo ra các thế hệ tiếp sau, hệ số phạt. Cuối cùng người dùng nhấp vào nút phân rã để thực hiện việc phân rã ma trận đầu vào thành các ma trận với kích thước nhỏ hơn. Kết quả sẽ được lưu vào file C:\\result.txt và được pop-up ra ngoài màn hình. 3. Một số kết quả thử nghiệm Trong phần thực nghiệm này, ta sử dụng hàm mục tiêu được định nghĩa như sau: ( ) ( ) ( )c pf I af I bf I  Ta xét với ( ) ( ) card I a card B  , b=1 và AConst = 10 ( ( ) ( )) ( ) *40 ( ) p abs card I card B f I card B   Trong các ví dụ sau, ta quy ước phép toán làm béo có độ ưu tiên cao hơn phép lấy hợp. Trang 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3. Một số kết quả thử nghiệm Trong phần thực nghiệm này, ta sử dụng hàm mục tiêu được định nghĩa như sau: ( ) ( ) ( )c pf I af I bf I  Ta xét với ( ) ( ) card I a card B  , b=1 và AConst = 10 ( ( ) ( )) ( ) *40 ( ) p abs card I card B f I card B   Trong các ví dụ sau, ta quy ước phép toán làm béo có độ ưu tiên cao hơn phép lấy hợp. Ví dụ 1. ta xét ví dụ đầu tiên với ma trận B có dạng như sau Thử nghiệm trên bộ xử lý pentum 4 tốc độ 3.0GHz, 512 MB RAM. Thời gian chạy chương trình 2 phút. Ta thu được kết quả như sau: Ma trận B phân rã được thành hợp của 6 phần tử cấu trúc khối 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Trang 65 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Như vậy chuỗi phân rã của B dưới dạng các phần tử cấu trúc kích thước 3x3 sẽ như sau: 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 B                                                                                                       2 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0                                             Ví dụ 2. Giả sử ma trận B là ma trận cỡ 9x9 có dạng sau 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 Ma trận B được phân rã thành hợp các phần tử cấu trúc hình khối sau: 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Trang 66 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 Tương tự như vậy chuỗi phân rã của B dưới dạng các phần tử cấu trúc kích thước 3x3 sẽ như sau 2 2 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 B                                                                                                          2 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0                         Trang 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên VI. KẾT LUẬN Trong khuôn khổ của luận văn này, tôi đã trình bày một cách có hệ thống các khái niệm từ cơ bản đến nâng cao trong việc ứng dụng phép toán hình thái trong xử lý ảnh. Đồng thời, tôi cũng trình bày các khái niệm cơ bản nhất của thuật toán di truyền. Phần quan trọng nhất là trình bày một tiếp cận để phân rã các phần tử cấu trúc hình thái nhị phân có dạng tuỳ ý thành chuỗi các nhân tử cơ bản sử thuật toán di truyền. Việc áp dụng của kỹ thuật này đối với phần tử cấu trúc lồi đã chỉ ra phân rã tối ưu đã được thảo luận trong tài liệu. Ngoài ra luận văn này cũng cung cấp một cách phân rã các phần tử cấu trúc không lồi. Đối với các ma trận lớn, thuật toán lộ rõ nhược điểm là thời gian chạy chương trình là khá lớn. Một trong các cách giải quyết là xây dựng các thuật toán song song để có thể chạy được trên các máy tính đa CPU. Việc phân rã được quản lý bởi tiến trình “chủ”, mà tiến trình này sinh ra các tiến trình con trên các nút khác nhau của các cụm trạm làm việc; mỗi tiến trình con gánh vác một phần riêng đặc thù của công việc xử lý, mà tiến trình đó được thực hiện song song với tất cả các tiến trình khác. Việc cài đặt song song cho phép nâng cao tốc độ xử lý và phân rã các phần tử cấu trúc rất lớn. Do giải pháp là dựa trên cách tiếp cận ngẫu nhiên nên mỗi lần thực hiện thuật toán kết quả có thể ra là khác nhau, do đó độ “tốt” của mỗi phân rã do đó mà khác nhau. Người dùng có thể thực hiện việc phân rã nhiều lần, sau đó chọn lấy một cách phân rã tối ưu nhất. Điều này có thể thực hiện được dựa trên hàm mục tiêu. Trang 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Tài liệu tham khảo [1] P. Angeline, G. Saunders, and J. Pollack, “An Evolutionary Algorithm. That Constructs Recurrent Neural Networks,” IEEE Trans. Neural Networks, vol. 5, pp. 54-65, Jan. 1994. [2] A. Broggi, “ Speeding-Up Mathematical Morphology Computations with Special-Purpose Array Processors,” Proc. 27th Hawaii Int’l Conf. System Sciences, T.N. Mudge and B.D. Shriver, eds., vol. 1, pp. 321-330, Maui, Hawaii, Jan. 4-7 1994. Los Alamitos, Calif.: IEEE Computer Society. [3] E. Falkenauer, “A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems,” Evolutionary Computation, vol. 2 no. 2, 1994. [4] Giovanni Anelli, Alberto Broggi, Giulio Destri, "Decomposition of Arbitrarily Shaped Binary Morphological Structuring Elements Using Genetic Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 2, pp. 217-224, Feb., 1998. [5] Marcos Quintana, “Genetic programming applied to morphological image processing”, PhD thesis, pp. 9-30, 2004. [6] D.E. Goldberg, B. Korb, and K. Deb, “Messy Genetic Algorithms: Motivation, Analysis, and First Results,” Complex Systems, vol. 3, pp. 493- 530, 1989. [7] D.E. Goldberg, B. Korb, and K. Deb, “Messy Genetic Algorithms Revisited: Studies in Mixed Size and Scale,” Complex Systems, vol. 4, pp. 415-444, 1990. [8] R.M. Haralick, S.R. Sternberg, and X. Zhuang, “ Image Analysis Using Mathematical Morphology,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 4, pp. 532-550, Apr. 1987. [9] J. Holland, Adaption Natural and Artificial Systems. Ann Arbor, Mich.: Univ. of Michigan Press, 1975. Trang 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên [10] S.W. Mahfoud, “Crossover Interactions Among Niches,” Proc. First IEEE Conf. on Evolutionary Computation, pp. 188-193, 1994. [11] G. Matheron, Random Sets and Integral Geometry. New York: John Wiley, 1975. [12] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer-Verlag, 1992. [13] H. Park and R.T. Chin, “Optimal Decomposition of Convex Structuring Elements for a 4-Connected Parallel Array Processor,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 3, Mar. 1994. [14] H. Park and R.T. Chin, “Decomposition of Arbitrarily Shaped Morphological Structuring Elements,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 1, Jan. 1995. [15] J. Serra, Image Analysis and Mathematical Morphology. London: Academic Press, 1982. [16] M. Srinivas and L. Patnaik, “Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm,” IEEE Trans. System, Man, and Cybernetics, vol. 24, no. 4, Apr. 1994. [17] R. van den Boomgaard, Mathematical Morphology: Extensions Towards Computer Vision, PhD thesis, Universiteit Van Amsterdam, 1992. [18] R. van den Boomgaard and R. van Balen, “Methods for Fast Morphological Image Transforms Using Bitmapped Binary Images,” Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, vol. 54, no. 3, pp. 252-258, May 1992. [19] S.S. Wilson, “ Theory of Matrix Morphology,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 6, pp. 636-652, June 1992. [20] X. Zhuang and R.M. Haralick, “Morphological Structuring Element Decomposition,” Computer Vision, Graphics, and Image Processing, vol. 35, pp. 370-382, Sept. 1986. Trang 70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên [21] N. R. Harvey. New Techniques for the Design of Morphological Filters using Genetic Algorithms. PhD thesis, University of Strathclyde, Glasgow, UK, 1997. [22] N. R. Harvey and S. Marshall. Mathematical Morphology and Its Applications to Image Procesing, chapter Using Genetic Algorithms in the Design of Morphological Filters, pages 53-59. Kluwer Academic Publishers, 1994. [23] N. R. Harvey and S. Marshall. Rank-order morphological _lters: A new class of _lters. In IEEE Workshop on nonlinear signal and image processing, pages 975-978,Halkidiki, Greece, 1994. [24] N. R. Harvey and S. Marshall. The use of genetic algorithms in morphological _filter design. Signal Processing: Image Communication, 8(1):55-72, Jan 1996. [25] M. Yu, N. Eua-anant, A. Saudagar, and L. Udpa. Genetic algorithm approach to image segmentation using morphological operations. In International Conference on Image Processing, volume 3, pages 775-779, 1998. [26] GONALEZ RC WOOD, Digital image processing, 2002 by Prentice Hall Upper Saddle River, New Jersey, Chapter 9.