Đồ án Tìm hiểu phương pháp làm mảnh ảnh

này, một định nghĩa khác của điểm biên được sử dụng: ở đây, một điểm biên đen có ít nhất một 8_láng giềng là trắng. Điều kiện này cùng với việc sử dụng XR(p) đòi hỏi một điều kiện bổ sung (F = x1 x3 x5 x7 = 0) để đảm bảo rằng không tạo ra các lỗ hổng khi các điểm đường biên được xoá đi. Bổ sung các điều kiện cho khả năng xoá p nhưng vẫn đảm bảo tính liên thông được đưa ra trong thuật toán này như sau: 1. Nếu XR(p) = 0 hoặc 8 thì p không thể xoá được. 2. Nếu XR(p) = 2 thì p được xoá đi nếu F = 0 và p không phải là một điểm cuối. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 16 3. Nếu XR(p) = 4 thì p được xoá đi nếu và chỉ nếu F = 0 và một trong 4 điểm ảnh góc là 0 với 1 trên cả hai phía. Điều kiện cuối tương đương với i= ∑ 1 4 x2i - 1 x 2ix2i + 1 = 1 4. Nếu XR(p) = 6 thì p được xoá đi nếu và chỉ nếu một trong 4_láng giềng của nó là 0 và ba láng giềng khác là 1 thuộc về từng 4_thành phần, hoặc i= ∑ 1 4 x2i - 1 = 3. Tuy nhiên, sử dụng các điều kiện trên bản thân chúng sẽ tạo các điểm cuối giả và các góc ăn mòn. Khi thu được một bộ S f với một lõi rỗng, mỗi điểm ảnh p được giữ lại trên S f được gán cho một nhãn : e(p) = 2(x5 + x3) + x1 + x7 + 1 Các điểm ảnh không lớn nhất dưới nhãn này được xoá đi, kết quả thu được, đa số, là xương có độ dày 2 điểm ảnh. Xương thu được theo cách này có thể bị ảnh hưởng mạnh tại điểm cuối cùng một nhánh bởi hình dạng của một khối lồi ra trên một mặt. 2.1.3. Thuật toán của Pavlidis Trong thuật toán này, đặc điểm của các điểm bội được định nghĩa lại trên giới hạn của các vùng láng giềng, và do đó có thể xác định được trên tuần tự hay song song thông qua việc so sánh các bộ mặt nạ với nhau. Đòi hỏi vùng láng giềng phải có dạng như Hình 3 và các dạng quay 900 của nó đối với các điểm bội. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 17 Định nghĩa các điểm bội cũng được thay đổi đôi chút. Người ta cũng đề xuất một sự phối hợp giữa tuần tự và song song rất có thể có hiệu quả hơn đối với những ảnh mà trên đó đa số các điểm ảnh không đòi hỏi phải được xử lý. Đối với những ảnh như vậy, mẫu có thể được chia ra thành các phần và ấn định cho từng bộ điều khiển. Mỗi một điều khiển hoạt động trên các điểm ảnh trong phần của nó một cách lần lượt, và khi các bước đã hoàn thành, nó đợi đến khi tất cả các bộ điều khiển khác hoàn thành trên cùng bước như vậy để cho các bộ điều khiển có thể được tiến hành đồng thời. Thuật toán này chủ yếu đảm bảo tính liên thông của xương bằng cách phát hiện và gán các điểm bội M cho xương S rồi tìm và gán cho S các điểm ảnh thích hợp để liên kết M với bên trong của P. Vì điều này có thể thu được các xương có độ dày không thích hợp khi P không đảm bảo rằng làm mảnh được đa số, do đó phải đan xen xoá đi được các điểm không bội từ biên C và giữ lại phần S. Đồng thời, biên được sử dụng để xác định xem một điểm có phải biên sẽ phải : a) coi như nhiễu và không được ghi nhãn là bội, hoặc b) được quan tâm đến độ lồi và ấn định cho S là chẵn dù nó là không đa. Điều này được hoàn thiện bởi việc tính toán n mã của các điểm biên từ mã xích Freeman nhận được trong dò biên. Mã ci của điểm ảnh pi là khác với mã xích pi , và với n > 1, mã n c in = nci + k n = −∑ 1 1 (n-k)(ci - k + ci + k) xác định độ cong của đường biên tại pi. Giá trị của ci được sử dụng để xác định a), và nếu c in vượt quá ngưỡng thì pi được gán cho S để nó có thể biểu diễn độ lồi có nghĩa. Một cách tự nhiên, nếu như ngưỡng có giá trị nhỏ hơn, thì thuật toán này sẽ nhạy cảm với những chỗ đường biên lồi ra. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 18 Khái niệm điểm bội được phát triển theo một quan điểm khác, nó được xem như là đối lập với những đường cong đơn giản. Trong mặt phảng liên tục, một đường cong (kín) được gọi là đơn giản nếu và chỉ nếu nó không bao giờ cắt chính nó; bởi thế đường cong đơn giản chia mặt phẳng thành hai phần liên thông gọi là bên trong và bên ngoài. Điều này cũng được mở rộng trên đường biên C của một mẫu số P cho một mẫu đơn liên thông và cho một mẫu đa liên thông. Đặc biệt C được coi là đơn giản, qui định rằng nó không chạm hay gối lên chính nó, và một khái niệm tổng thể được tìm ra tương đương với những điều kiện địa phương. Nếu chúng ta coi P - C là bên trong của C và P là bên ngoài của C, thì C là đơn giản, qui ước rằng mọi điểm p trong C đều phải thoả mãn các điều kiện sau: A1: N(p) ∩ C gồm có một thành viên (8_liên thông) nằm trong và một thành viên (4_liên thông) nằm ngoài. A2: N(p) ∩ C có chứa ít nhất hai điểm ảnh theo chiều ngang hay theo chiều dọc: một thuộc bên trong, một thuộc bên ngoài. Các điểm ảnh thoả mãn các điều kiện A1 và A2 được gọi là điểm ảnh thường, còn những cái không phải là thường thì đồng nghĩa với điểm bội trên các đường biên cánh cung khác trùng hay kề nhau. Xa hơn nữa, do A1 phải tính toán phức tạp nên tương đương với A1, A2 ta có, các điểm ảnh p là bội nếu nó thoả mãn ít nhất một trong các điều kiện sau: A3: Các điểm ảnh p hoặc dọc hoặc ngang thì cứ một thuộc P - C một thuộc P - C . A4: N(p) có 3 điểm liên tiếp ở giữa mà một là láng giềng chéo và thuộc vào C, hai điểm còn lại thuộc vào P . Các điều kiện A3 và A4 có những thuận lợi của các điều kiện địa phương mà được kiểm tra rất dễ dàng một khi các điểm biên được định vị. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 19 Bằng cách kiểm tra các điểm bội trên sự biến đổi 4_khoảng cách của P, mỗi đường biên kế tiếp được xác định bởi nhãn của nó trên biến đổi khoảng cách, do đó làm mảnh có thể được hoàn thành trên một loạt. Trong suốt quá trình kiểm tra này, các láng giềng của một điểm ảnh đã bị xoá đã được kiểm tra rồi nhưng vẫn phải kiểm tra lần nữa để xác minh xem chúng có bị trở thành điểm ảnh bội do việc bắt buộc phải giữ tính liên thông không. Xương bao gồm tất cả các điểm bội đã bị xoá, và nó có thể giảm độ dày đơn vị. 2.1.4. Thuật toán của Kwok Các thuật toán được nói ở trên thường dựa trên việc kiểm tra các điểm biên để xoá đi hay giữ lại. Một phương thức cài đặt khác để thu được xương là từ việc tạo sinh biên hoặc tạo sinh lặp một đường biên mới tồn tại bên trong cho đến khi chỉ còn lại xương . Quá trình này được dựa trên hướng của các điểm biên. Khi các điểm biên được dò theo một thứ tự, ba điểm liên tiếp sẽ tạo nên một góc θ với đỉnh là điểm p hiện thời. Các điểm trong của N(p) gần nhất với phân giác của góc θ được coi như một điểm trên đường biên tiếp theo, và p được xoá đi. Khi thủ tục này lặp lại cho đến lúc không còn các điểm ảnh bên trong xoá được, thì các đường biên còn lại tạo thành bởi một xương giả. Phương thức đơn giản này được lọc kỹ càng và mở rộng bằng cách sử dụng mã xích Freeman của các điểm biên sinh ra các đường biên mới. Mã xích này được sử dụng, cùng với việc xét các điểm ngắt và các điểm cuối, để nhận được tập các qui tắc để sinh ra các chu tuyến mới. Khi các điểm biên mới được xác định, thì mã xích cũng được tạo sinh. Thuật toán này cũng được cài đặt trên môi trường phân tán bằng cách gán các tập con không gối lên nhau của mẫu cho các bộ điều khiển khác nhau để làm mảnh sau đó đồng bộ hoá thông tin của các biên khi kết thúc mỗi vòng lặp. Trong một số sản phẩm gần Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 20 đây, một điểm biên được xoá đi nếu tất cả 4_láng giềng của nó trên mặt “trong” đều là đen, trong trường hợp này, chuỗi các mã xích tương ứng với các đoạn của đường biên mới thu được từ một bộ các điều kiện tiền định nghĩa có liên quan đến độ cong địa phương. 2.2. Làm mảnh theo loạt O’ Gorman đưa ra tiêu chuẩn làm mảnh mở rộng các cửa sổ thành kích thước k×k (k > 3), ở đây tâm của các điểm ảnh (k-2) × (k-2) có thể bị xoá đi cùng nhau nếu như các điểm ảnh biên trên của sổ có số giao Hilditch là 1 và nếu chúng chứa nhiều hơn (k - 2) các điểm ảnh trắng 4_liên thông và nhiều hơn (k - 2) các điểm ảnh đen. Đối với tất cả các điểm ảnh đen, cửa sổ k × k của nó được kiểm tra theo thứ tự k giảm cho đến khi k < 3 hoặc xoá đi điểm trung tâm. Với các giá trị lớn hơn của k, các lớp điểm ảnh dày hơn có thể được xoá đi trên một vòng lặp, do đó, để thu được xương của các mẫu dày thì chỉ cần số vòng lặp ít hơn. Tuy nhiên, việc tăng tốc độ này phải đổi lại kết quả thu được xương thô hơn (xương có nhiễu). Khi làm mảnh các mẫu lớn hơn, việc sử dụng một số k lớn hơn có thể làm ảnh hưởng không tốt đến tốc độ xử lý. 2.2.1. Thuật toán làm mảnh của Yakei Trong thuật toán này, mọi điểm ảnh đen được kiểm tra và gán theo qui tắc: L(p) = 2 nếu x3 = 0 hoặc x 3 + x 5 + x7 = 0 L(p) = 3 nếu x 3 + x 5 = 0 hoặc x 3 + x 5 + x 7 + x1 = 0 Hai loạt ngược chiều nhau được thực hiện để xoá đi các điểm ảnh được đánh dấu 2 và 3, một cách tương ứng, các điểm ảnh được cung cấp không phải Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 21 là các điểm cuối và có số liên thông bằng 1 (ở đây 4_liên thông hoặc 8_liên thông đều có thể được dùng). Mặc dù thuật toán này đơn giản và cho xương liên thông, nhưng các đường dọc có độ dày là một số chẵn các điểm ảnh có thể bị loại bỏ hoàn toàn. 2.2.2. Thuật toán làm mảnh SPTA SPTA [1] là một thuật toán tuần tự sử dụng hai loạt trên một chu trình, đầu tiên là từ trái qua phải, và rồi từ trên xuống dưới. Trên mỗi bước quét, p được đánh dấu để giữ lại (p là một điểm an toàn “safe point”) nếu như một trong các điều kiện sau là đúng: N1: N(p) thoả mãn một trong hai cửa sổ như Hình 4 hoặc các dạng quay của nó. N2: N(p) chứa đúng hai điểm kề 4 là đen. Các điều kiện này là tương đương với một điểm đường biên phía tây an toàn p nếu có biểu thức lôgic sau: x1(x2 + x3 + x7 + x8)(x3 + x 4)(x7 + x 6) = 0 Trên bước quét đầu tiên, các điểm đường biên phía tây được đánh dấu, sau đó là đến các điểm đường biên phía đông mà không phải là các điểm an toàn phía tây, và lặp lại quá trình này. Điều kiện N2 có tác dụng ngăn chặn sự xói mòn quá mức của các đường chéo có độ dày 2 điểm ảnh, nhưng nó có thể dẫn đến các nhánh nhiễu. Beffert và Shinghal [1] đã đề xuất một sự thay đổi đối với SPTA nhằm loại (trong đa số trường hợp) vòng kiểm tra cuối cùng khi không còn điểm ảnh nào có thể xoá được nữa, và sự thay đổi của thuật toán này được thực hiện trên một bộ đa xử lý sử dụng các phương pháp của hàm (a) và phân tích dữ liệu (b). Trong (a), mỗi bộ xử lý thực hiện một bước quét, và mỗi dòng hoàn chỉnh được xoá đi bởi bộ xử lý thực hiện bước quét Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 22 tiếp theo, mặt khác trên (b) mỗi bộ xử lý quét một phần của ảnh với các đường biên gối lên nhau. (b) (a) (b) Hình 4 Cấu hình các điểm ngắt, ít nhất một điểm ảnh trên mỗi nhóm được đánh dấu x hoặc y phải khác không (a) (b) (c) Hình5 : Cấu hình của điểm bội p. Mỗi một nhóm của các điểm ảnh được đánh dấu x hoặc y phải có ít nhất một thành viên nonzero. Trên (c), có ít nhất một điểm ảnh có đánh dấu z phải là nonzero; nếu chúng đều là nonzero thì các điểm ảnh x, y nhận giá trị bất kỳ đều được; điểm ảnh d là một điểm ảnh đường biên. 2.3. NHẬN XÉT x x x 0 1 x 1 0 x x x x 0 1 0 y y y x x x 0 1 0 y y y x x x 0 1 x 1 0 x x x z 0 1 d y y z Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 23 Nhìn chung, khi các điểm ảnh của P được xử lý một cách tuần tự, sẽ không có vấn đề gì trong việc đảm bảo tính liên thông của P và P khi các điều khiển tương thích với vùng 3 × 3 được sử dụng. Do đó trong các thuật toán này cần phải đảm bảo tính tô pô. Tuy nhiên nó cũng đòi hỏi nhiều hơn các thông tin tổng thể để giữ lại những đặc trưng hình học có ý nghĩa đối với khối hình số của P. Với mục đích này, xương thu được từ một loạt của P ít khi là có ý nghĩa, trái lại thuật toán dựa trên việc dò biên tuần tự lại có thể dẫn đến các kết quả tốt hơn. Phương pháp của Kwork cho phép sự tương quan giữa dạng của xương và những đường biên bên ngoài của mẫu mà thường là không thể đạt được chỉ với các điều khiển địa phương. Tất nhiên, việc xét tổng thể hơn này sẽ tăng thời gian tính toán và các thủ tục phức tạp hơn, và phần lớn độ phức tạp của các thuật toán làm mảnh tuần tự [2] là kết quả của việc cố gắng giữ lại nhiều đặc trưng hình học hơn. CHƯƠNG 3 CÁC THUẬT TOÁN LÀM MẢNH SONG SONG Trong làm mảnh song song, các điểm ảnh được kiểm tra để xoá dựa trên kết quả của vòng lặp trước đó. Vì nguyên nhân này, các thuật toán làm mảnh song song phù hợp để cài đặt trên các bộ xử lý song song, các điểm ảnh phải Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 24 thoả mãn tập các điều kiện để có thể được xoá đồng thời. Nhưng đáng tiếc là các thuật toán hoàn toàn song song khó có thể giữ được sự liên thông đối với một ảnh chỉ cho phép tác động lên khối 3 x 3 các điểm ảnh lân cận. Ví dụ, một hình chữ nhật với độ dầy 2 điểm ảnh rất có thể bị xoá trong một quá trình làm mảnh song song. Do đó cách thông thường là sử dụng các láng giềng 3 x 3 nhưng phải chia mỗi vòng lặp ra thành các vòng lặp con hoặc các chu trình con trên đó chỉ có một tập con các điểm biên được xét để xoá. Kết thúc mỗi vòng lặp con, ảnh được thay đổi để chuẩn bị cho bước tiếp theo. Tùy theo số chu trình con mà các thuật toán làm mảnh song song được chia ra thành các kiểu như sau: • Các thuật toán sử dụng 4_chu trình con, trên mỗi chu trình con có một kiểu của điểm biên (Đông, Tây, Nam, Bắc) được xoá đi. • Các thuật toán sử dụng 2_chu trình con, ví dụ, một chu trình xoá theo hướng Bắc rồi đến hướng Nam, một chu trình khác xoá trên các hướng còn lại. • Các thuật toán chỉ sử dụng 1_chu trình con, nhưng nó luôn phải thoả mãn một tập hợp có thứ tự các điều kiện để đảm bảo sự liên thông. 3.1. Làm mảnh song song sử dụng 1 chu trình con 3.1.1 Thuật toán Rutovitz Đây là một thuật toán song song cơ bản, một điểm ảnh p được xoá đi nếu tất cả các điều kiện sau đều được thoả mãn: R1: b(p)>=2 R2: Xr(p)=2 Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 25 R3: x1.x3.x5 = 0 hoặc XR (x3) ≠ 0 R4: x7.x1.x3 = 0 hoặc XR (x1) ≠ 0 Thuật toán này còn có thêm một điều kiện phụ b(p) ≤ 6 đảm bảo p có 4_láng giềng là trắng, do đó việc xoá p không tạo ra lỗ hổng. Đây là một thuật toán 1_vòng lặp con sử dụng các thông tin từ một cửa sổ 4 x 4, và nó cho ta các xương liên thông mà không nhạy cảm đối với nhiễu biên, nhưng lại có tạo ra xói mòn quá mức. Từ 4_thành phần rời nhau có thể là 8_liên thông, việc xoá đi các điểm p thoả mãn các điều kiện trên không giảm độ rộng đơn vị điểm ảnh của các đường chéo. Các điều kiện được thêm vào nhằm giải quyết vấn đề này, và cho phép xoá điểm p với XR(p) = 4 khi p nằm trên một đường chéo có độ rộng 2 điểm ảnh, nhưng vẫn đảm bảo được tính liên thông. Do tính không đối xứng tự nhiên của các điều kiện R3 và R4 nên xương thu được không nằm vào trung tâm. Do đó, sau phép quay 1800 các qui tắc này ta thu được tập đầy đủ các điều kiện cho phép xoá điểm p: D1: XR (p) = 0, 2 hoặc 4 D2: b(p) ≠ 1 D3: x1.x3.x5 = 0 D4: x1.x3.x7 = 0 D5: Nếu XR(p) = 4 thì thêm vào một trong 2 điều kiện a) hoặc b) a) x1.x7 = 1, x2 + x6 ≠ 0, và x3 + x4 + x5 + x8 = 0 b) x1.x3 = 1, x4 + x8 ≠ 0, và x2 +x5 + x6 + x7 = 0 D6-D8 nhận được từ do việc quay D3-D5 1800. Người ta cũng đã đề nghị rằng nên sử dụng 2 vòng lặp con cho thuật toán này, vòng thứ nhất xoá những điểm ảnh thoả mãn các điều kiện D1-D5, vòng lặp thứ hai xóa những điểm ảnh phù hợp với D1,D2 và D6-D8. Tất Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 26 nhiên, thuật toán này xoá đi những điểm ảnh đã bị cô lập. Độ phức tạp của các điều kiện D1-D5 dẫn đến một điều rằng nếu 2 sự phối hợp 4_láng giềng của p là 1, thì giá trị của điểm ảnh p nằm chính giữa góc nối sẽ không có hiệu lực đối với việc p sẽ bị xoá hay không, vì vậy p chỉ được quan tâm đến với giá trị 1. Trong các trường hợp này, p có thể bị xoá đi nếu như sự thay đổi số giao của nó là 2 với điều kiện là b(p) > 1. Cũng cần phải chú ý rằng sự thay đổi này của số giao nhau là xử lý cắt góc, bởi vậy số kết quả thực sự thu gấp 2 lần XH (p), và tất nhiên nó đo sự 8_liên thông chứ không phải 4_liên thông. 3.1.2.Thuật toán của Holt Holt đưa ra biểu thức logic cho sự tồn tại của một điểm ảnh như sau : v(C) ^ (~edge(C) ∨ (edge(E) ^ v(N) ^ v(S)) ∨ (edge(S) ^ v(W) ^ v(E)) ∨ (edge(E) ^ edge(SE) ^ edge(S)) Trong đó ~ biểu diễn cho phủ định (NOT).Hàm v trả về giá trị của điểm ảnh ( 1 =true cho điểm ảnh của đối tượng , 0 =false cho điểm ảnh nền) . Hàm edge(i) trả về giá trị true nếu i là điểm biên của đối tượng. Các kí tự E, SE, S, SW, W, NW, N biểu diễn cho 8_láng giềng , kí tự C biểu diễn cho điểm trung tâm như hình 6a. NW N NE W C E SW S SE Hình 6a cửa sổ 3x3 các điểm ảnh Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 27 Đôi khi quá trình làm mảnh hoàn thành , vẫn còn có những điểm ảnh có thể xoá được. Chủ yếu là dạng cầu thang gác , gần như một nửa số điểm ảnh trong một cầu thang gác có thể xoá được mà không làm ảnh hưởng hình dạng cũng như tính liên thông của mẫu. Hình 6b cho thấy những ví dụ về cầu thang gác mà trong mỗi cửa sổ điểm trung tâm có thể bị xoá. 1 biểu diễn cho điểm ảnh của đối tượng , 0 biểu diễn điểm ảnh nền , x không quan tâm đến giá trị . Hình 6b cửa sổ có dạng cầu thang gác Để tránh tạo ra các lỗ hổng thì một điều kiện được thêm vào, đó là một trong các giá trị x chuyển thành 0. Đối với cửa sổ có một góc hướng bắc như cửa sổ thứ 2 trong hình 6b biểu thức logic cho sự tồn tại được đưa ra như sau : v(C) ^ (v(N) ^((v(E) ^ ~v(NE) ^ ~v(SW) ^ (~v(W) ∨ ~v(S)) ∨ (v(W) ^ ~v(NW) ^ ~v(SE) ^ (~v(E) ∨ ~v(S)))))) Tương tự đối với hưóng nam và có sự thay đổi tương ứng. 3.1.3. Thuật toán của Favre và Keller Đây là một thuật toán sử dụng sơ đồ gán nhãn trong làm mảnh song song. Thuật toán này làm mảnh trên 1_chu trình và được hoàn thiện bởi việc mã lại các điểm ảnh mẫu để kết hợp thông tin liên thông từ một của sổ 5 × 5 vào các điểm ảnh đã được mã trên N(p). Hai đường quét đầu tiên được sử dụng để mã lại các điểm ảnh ở tâm, trong, biên và các điểm xương (tương ứng c, i, r và s). Điều kiện cơ bản là thay các điểm ảnh r bởi các điểm ảnh b (nền) Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 28 nếu có mặt dãy irb theo chiều dọc hoặc ngang, trừ trường hợp cần giữ lại được tính liên thông và các điểm cuối. Điều này cũng giống như phương thức làm mảnh “lý tưởng” mà Eckhardt và Maderlechner đưa ra, trên đó p là D hoàn chỉnh nếu nó thuộc một cấu trúc ipb dọc hoặc ngang, trong đó i là một điểm trong, còn b là một điểm nền. Một điểm I hoàn chỉnh được định nghĩa tương tự theo thuật ngữ của sự sắp chéo với điều kiện bổ sung là cả hai điểm ảnh kề 4 đối với cả b và p đều là trắng. Chúng ta cũng đưa ra giả thuyết rằng việc xoá song song các điểm ảnh là đơn và hoàn chỉnh (D hoặc I hoàn chỉnh) sẽ thu được xương giả được định nghĩa tốt và không bị biến đổi trong quá trình tịnh tiến và quay. Việc giữ lại các điểm cuối được thực hiện một cách rõ ràng bởi vì chúng chẳng bao giờ hoàn chỉnh. Bởi không thể xác định được một láng giềng của một điểm biên có là điểm bên trong hay không (điểm i) nếu chỉ sử dụng cửa sổ 3 × 3, nên các thông tin bổ xung được kết hợp chặt chẽ từ cửa sổ bên ngoài bởi việc định nghĩa các điểm không phải là điểm cuối. Nếu SC là tập các điểm biên đơn, B = P - SC, thì p ∈ P không phải là điểm cuối nếu và chỉ nếu: T1 : p là liền kề với một điểm trên B. T2 : mọi láng giềng của p ∈ P đều ∈ B hoặc kề với một điểm ∈ B ∩ N(p). T3 : Các điểm trên B ∩ N(p) đều được liên thông trên N(p) và T4 : b(p) ≥ 2. Quá trình hoạt động này xoá song song các điểm đơn, không phải là điểm cuối, đường biên giữ lại được tính chất tô pô. Để mở rộng giới hạn được đặt trên các vùng 3 × 3, sơ đồ ghép lai cũng đã được đề xuất để chứa những sự thay đổi khoảng cách trong làm mảnh. Việc sử dụng biến đổi khoảng cách này đã cung cấp thêm nhiều thông tin tổng thể Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 29 hơn. Nó cũng đã chứng tỏ rằng quá trình làm mảnh có thể giữ lại được tính liên thông trong khi quá trình thay đổi khoảng cách có khả năng xây dựng lại, kết hợp hai quá trình sẽ là hợp lý nếu cả hai thuộc tính đều được yêu cầu. Thủ tục này được đề nghị trên mỗi vòng lặp, tập I các điểm trong của các mẫu đang tồn tại P sẽ được xác nhận, và sự mở rộng của nó E(I) được định nghĩa là E(I) = { q|q ∈ I hoặc có một láng giềng trong I }. Do vậy, tập các điểm cực đại địa phương (độ lồi) có thể thu được là P - E(I), và các điểm đường biên có thể được xoá đi loại trừ các điểm cực đại địa phương không phải điểm đơn, hoặc điểm cuối (như đã nói ở trên). Các điểm biên còn lại được bổ xung vào xương, và xử lý được lặp lại với I như một mẫu đang tồn tại. Nó cũng chứng tỏ rằng một sơ đồ lai có là hiệu quả nhất vì có thể sử dụng phép biến đổi khoảng cách ban đầu để xoá đi số lượng lớn các điểm ảnh bên ngoài trên một số vòng cố định, và sau đó, có thể sử dụng một thuật toán bóc để làm mảnh phần ảnh còn lại thành độ rộng đơn vị. 3.1.4. Thuật toán của Huang , Wan , Liu Trong thuật toán này các tác giả tổng kết từ 256 dạng của 8_láng giềng của điểm ảnh p để đưa ra 1 bảng loại trừ , theo đó điểm ảnh p được xét có bị xoá hay không. Cột thứ nhất của bảng biểu thị số lượng điểm ảnh đen trong 8_láng giềng của p , cột thứ hai gồm các cửa sổ 3 x 3 nếu điểm p được xét phù hợp với một trong các cửa sổ đó thì p sẽ bị xoá. Điểm p được coi là điểm an toàn nếu không phù hợp với bất kỳ cửa sổ nào trong bảng loại trừ. Nếu b(p)=0,1 hoặc 8 thì p không bị xoá. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 30 Hình 7a Bảng loại trừ 1 biểu thị cho điểm đen , ô trống biểu thị cho điểm trắng Tuy nhiên những đường có độ rộng 2 pixel sẽ bị xoá và có thể làm mất tính liên thông của mẫu. Vì vậy nhóm tác giả sử dụng thêm các mẫu lưu trữ như hình 7b gồm các cửa sổ 3x4 , 4x3, 4x4 để lưu lại các điểm ảnh p thoả mãn để giải quyết vấn đề trên. Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 31 Hình 7b mẫu lưu trữ : ô trống biểu diễn điểm trắng, 1 biểu diễn điểm đen, x là điểm không cần quan tâm Thuật toán gồm 4 bước như sau: Bước 1 : Tính b(p). Bước 2 : Đối chiếu với bảng loại trừ xem p có là điểm an toàn hay không , nếu là điểm an toàn nhảy tới bước 4. Bước 3: xét p có thuộc đường có độ rộng 2 pixel hay không , nếu có sử dụng nhãn lưu trữ để quyết định có nên xoá p hay không. Bước 4 : lặp lại các bước trên cho đến khi không còn điểm ảnh nào bị xoá. 3.2. LÀM MẢNH SONG SONG 2 CHU TRÌNH CON 3.2.1. Thuật toán của Zang-Suen Đây là phép cài đặt dựa trên tập các điều kiện D1-D8 trong thuật toán Rutovitz theo 2 vòng lặp con. Vòng thứ nhất, p được xoá đi nếu nó thoả mãn các điều kiện sau: Z1: 2 ≤ b(p) ≤ 6 Z2: XR (p) = 2 Z3: x1.x3.x7 = 0 Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Sinh viên Hà Đức Kiên - CT702 Trang 32 Z4: x1.x7.x5 = 0 Trong vòng lặp thứ hai, Z3 và Z4 được thay bởi phép xoay chúng 1800.Nghĩa là : Z3: x1.x3.x5 = 0 Z4: x3.x5.x7 = 0 Vì vậy, chu trình con thứ nhất xoá đi 4 điểm ảnh đơn trên biên phía Đông-Nam cũng như các điểm ảnh góc Tây-Bắc, ngược lại chu trình thứ hai xoá các điểm biên theo hướng ngược lại. Đây là một thuật toán đơn giản và hiệu quả mà nó loại được nhiễu biên. Tuy nhiên, các đường chéo có độ rộng 2 điểm ảnh có thể bị xoá hẳn, và các hình vuông 2 × 2 cũng có thể bị xoá hoàn toàn. Người ta cũng đề nghị rằng điều kiện Z1 nên được thay bằng: 3 ≤ b(p) ≤ 6 để giữ lại được các cấu trúc đó. Đúng như dự đoán, sự cải biên này đã có hiệu quả. Bởi vậy, một bước xử lý phụ được đề xuất thêm để làm mảnh thành độ dày 1. Mặc dù việc xói mòn quá mức các đường chéo không phải là một vấn đề liên quan đến tính chất tô pô, nhưng sự biến mất hoàn toàn của một hình vuông 2 x 2 trong quá trình làm mảnh cho thấy sự thiếu sót của thuật toán về mặt tô pô. Đây chính là điều bất hợp lý của thuật toán này, do đó một sự thay đổi đã được đề xuất để tất cả các trường hợp đều có thể được xử lý đúng. Sự thay đổi này dựa trên 4_láng giềng đen của p khi XR (p) = 2. Nếu p có ít hơn 2 láng giềng thì không cần thay đổi gì. Nếu p có từ 2 đến 3 láng giềng và p thoả mãn các điều kiện