›
›

Đồ án Tìm hiểu phương pháp BPR (bending potential ratio) cho bài toán tìm xương của ảnh - Nguyễn Thị Lan

pdf 51 trang huongle 1620
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu phương pháp BPR (bending potential ratio) cho bài toán tìm xương của ảnh - Nguyễn Thị Lan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_tim_hieu_phuong_phap_bpr_bending_potential_ratio_cho_b.pdf

Nội dung text: Đồ án Tìm hiểu phương pháp BPR (bending potential ratio) cho bài toán tìm xương của ảnh - Nguyễn Thị Lan

  1. 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o TÌM HIỂU PHƢƠNG PHÁP BPR (BENDING POTENTIAL RATIO) CHO BÀI TOÁN TÌM XƢƠNG CỦA ẢNH ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY NGÀNH CÔNG NGHỆ THÔNG TIN Sinh viên thực hiên: Nguyễn Thị Lan Giáo viên hướng dẫn: Ths. Ngô Trƣờng Giang Mã số sinh viên: 110853 HẢI PHÒNG - 2011 ___ Sinh viên: Nguyễn Thị Lan – CT1102
  2. 2 LỜI CẢM ƠN Trong lời đầu tiên của báo cáo Đồ án Tốt Nghiệp “Tìm hiểu phương pháp BPR(Bending Potential Ratio) cho bài toán tìm xương của ảnh” này, em muốn gửi những lời cám ơn và biết ơn chân thành nhất của mình tới tất cả những người đã hỗ trợ, giúp đỡ em về kiến thức, và tinh thần trong quá trình thực hiện Đồ án. Trước hết, em xin chân thành cám ơn Thầy Giáo. Ths. Ngô Trường Giang, Giảng viên Khoa Công Nghệ Thông Tin, Trường ĐHDL Hải Phòng, người đã trực tiếp hướng dẫn, nhận xét, giúp đỡ em trong suốt quá trình thực hiện Đồ án. Xin chân thành cảm ơn các Thầy Cô trong Khoa Công Nghệ Thông Tin và toàn Thầy Cô trong Trường Đại Học Dân Lập Hải Phòng đã giúp đỡ em trong suốt quá trình học tập. Em cũng xin bày tỏ lòng biết ơn đến gia đình và những người bạn đã luôn giúp đỡ động viên em rất nhiều trong quá trình học tập và làm Đồ án Tốt Nghiệp. Do thời gian thực hiện có hạn, kiến thức còn nhiều hạn chế nên Đồ án thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định. Em rất mong nhận được ý kiến đóng góp của Thầy Cô giáo và các bạn để em có thêm kinh nghiệm và tiếp tục hoàn thiện bài báo cáo của mình. Em xin chân thành Cám ơn! Hải Phòng, tháng 7/2011 Sinh viên Nguyễn Thị Lan ___ Sinh viên: Nguyễn Thị Lan – CT1102
  3. 3 MUC LỤC MUC LỤC 3 MỞ ĐẦU 5 DANH MỤC HÌNH VẼ 6 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH 7 1.1 Các khái niệm cơ bản trong xử lý ảnh 7 1.1.1 Xử lý ảnh là gì? 7 1.1.2 Ảnh và điểm ảnh 7 1.1.3 Độ phân giải 8 1.1.4 Mức xám 8 1.2 Các phép toán cơ bản trên ảnh nhị phân 9 1.2.1 Phép toán logic trên ảnh nhị phân 9 1.2.2 Các phép toán hình thái trên ảnh nhị phân 9 1.3 Các giai đoạn cơ bản của Xử lý ảnh 17 1.4 Một số ứng dụng cơ bản của xử lý ảnh 18 CHƢƠNG 2: XƢƠNG VÀ CÁC THUẬT TOÁN TÌM XƢƠNG 20 2.1 Khái niệm xương 20 2.2 Các hướng tiếp cận trong việc tìm xương 20 2.2.1 Phương pháp tìm xương dựa trên làm mảnh 20 2.2.2 Tìm xương không dựa trên làm mảnh 22 2.3 Cắt tỉa xương của ảnh 29 2.3.1 Khái niệm cắt tỉa xương 29 2.3.2 Kỹ thuật cắt tỉa xương với DCE 29 CHƢƠNG 3: KỸ THUẬT CẮT TỈA XƢƠNG DỰA VÀO ĐỘ UỐN 33 3.1 Giới thiệu 33 3.2 Phương pháp cắt tỉa xương theo BPR (Bending Potential Ratio) 35 3.2.1 Định nghĩa cơ bản 35 3.2.2 Tỷ lệ uốn (BPR – Bending Potential Ratio) 37 3.2.3 Đề xuất cho phát triển cắt tỉa xương 41 ___ Sinh viên: Nguyễn Thị Lan – CT1102
  4. 4 3.2.4 Kết luận 44 CHƢƠNG 4: KẾT QUẢ THỰC NGHIỆM 45 4.1 Môi trường cài đặt 45 4.2 Một số kết quả thử nghiệm 45 4.2.1 Giao diện chương trình. 45 4.2.2 Một số kết quả tìm xương khác nhau của các phương pháp 46 4.2.3 Hiệu quả của việc sử dụng ngưỡng t 48 KẾT LUẬN 50 TÀI LIỆU THAM KHẢO 51 ___ Sinh viên: Nguyễn Thị Lan – CT1102
  5. 5 MỞ ĐẦU Xương được coi như hình dạng cơ bản của một đối tượng, với số ít các điểm ảnh cơ bản và nó là cách biểu diễn đối tượng một cách cô đọng. Ta có thể lấy được các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương. Vị trí, sự định hướng, độ dài của một đoạn xương đặc trưng cho đoạn ảnh đó. Vì thế mà xương được ứng dụng trong rất nhiều lĩnh vực như đồ họa máy tính, tra cứu ảnh, nhận dạng ký tự, . . . Các thuật toán tìm xương đã được đưa ra nhưng đều gặp phải những hạn chế tương tự nhau đó là có độ nhạy cảm cao đối với nhiễu đường biên, những biến đổi nhỏ trên đường biên của đối tượng có thể làm thay đổi đáng kể xương nhận được ảnh hưởng tới độ chính xác của xương. Để giải quyết được những hạn chế và khó khăn trên. Đồ án trình bày kỹ thuật cắt tỉa xương của ảnh bằng phương pháp BPR(Bending Potential Ratio) để làm mịn xương và cho ra hình dạng xương phù hợp với cấu trúc của đối tượng. Đồ án bao gồm 4 chương: Chương 1: Tổng quan về xử lý ảnh Chương 2: Xương và các kỹ thuật tìm xương Chương 3: Kỹ thuật cắt tỉa xương của ảnh dựa vào độ uốn Chương 4: Kết quả thực nghiệm ___ Sinh viên: Nguyễn Thị Lan – CT1102
  6. 6 DANH MỤC HÌNH VẼ Hình 1.1. Hình minh họa các phép toán trên ảnh nhị phân 9 Hình 1.2. Hiệu quả của thao tác nhị phân đơn giản trên một ảnh nhỏ 10 Hình 1.3. A dãn bởi B 11 Hình 1.4. Dãn mất điểm ảnh 12 Hình 1.5. Dãn ảnh sử dụng phần tử cấu trúc 12 Hình 1.6. Phép co nhị phân 13 Hình 1.7. Sử dụng phép toán mở 15 Hình 1.8. Phép đóng 15 Hình 1.9. Phép đóng với độ sâu lớn 16 Hình 1.10. Các giai đoạn chính trong Xử lý ảnh 17 Hình 2.1. Trục trung vị 23 Hình 2.2. Xương Voronoi rời rạc ảnh hưởng của các hàm hiệu chỉnh khác nhau 25 Hình 2.3. Minh họa thuật toán trộn hai sơ đồ Voronoi 27 Hình 2.4. Minh họa thuật toán thêm một điểm biên vào sơ đồ Voronoi 28 Hình 2.5. Minh họa cắt tỉa xương với DCE 32 Hình 3.1. Minh họa xương của ảnh 34 Hình 3.2. Định nghĩa của điểm ghost và BPR 37 Hình 3.3. Vùng của điểm ghost 38 Hình 3.4. Mẫu hình chữ nhật với cùng một đỉnh được thêm vào đường biên của hình 40 Hình 3.5. Xương chân của 1 con lạc đà 42 Hình 4.1. Giao diện chương trình 45 Hình 4.2. Xương của quả táo thu được bằng các phương pháp 46 Hình 4.3. Xương của con lạc đà thu được bằng các phương pháp 47 Hình 4.4. Minh họa xương của đối tượng trong việc sử dụng các ngưỡng khác nhau, t là giá trị ngưỡng. 49 ___ Sinh viên: Nguyễn Thị Lan – CT1102
  7. 7 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH 1.1 Các khái niệm cơ bản trong xử lý ảnh 1.1.1 Xử lý ảnh là gì? Cũng như xử lý dữ liệu bằng đồ họa, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này được xem xét như là một cấu trúc dữ liệu và được tạo ra bởi các chương trình. Xử lý ảnh số bao gồm các phương pháp và kỹ thuật biến đổi, để truyền tải hoặc mã hóa các ảnh tự nhiên. Xử lý ảnh là lĩnh vực nghiên cứu, là quá trình biến đổi từ một ảnh ban đầu sang một ảnh mới tuân thủ tính chất và đặc trưng riêng của xử lý. Có 2 mục đích chính của xử lý ảnh: Cải thiện chất lượng phục vụ cho quan sát. Chuẩn bị các điều kiện cho việc trích chọn các đặc trưng phục vụ cho việc nhận dạng và ra quyết định. 1.1.2 Ảnh và điểm ảnh Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng chúng được biểu diễn bằng một hàm 2 biến thực hoặc phức kí hiệu là f(x, y). Trong đó x, y là các giá trị tọa độ không gian và giá trị của f sẽ tỷ lệ với độ sáng của ảnh tại điểm này. Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hóa ảnh. Trong quá trình số hóa, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng tử hóa thành phần giá trị mà về nguyên tắc bằng mắt thường không phân biệt được hai điểm kề nhau. Trong quá trình này, người ta sử dụng khái niệm Picture element mà ta quen gọi hay viết tắt là Pixel – phần tử ảnh. Như vậy, mỗi ảnh là một tập hợp các Pixel. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  8. 8 Ảnh số là ảnh xử lý bằng máy tính thu được từ ảnh liên tục bởi quá trình số hóa, thường được biểu diễn bởi mảng hai chiều I(n, p): n dòng và p cột. Người ta thường kí hiệu I(x, y) để chỉ một pixel. Một pixel có thể được lưu trữ bằng 1, 4, 8, 16 hay 24 bít. Thường được kí hiệu là I[m, n]. 1.1.3 Độ phân giải Độ phân giải (Resolution) là mật độ của ảnh được ấn định trên ảnh số khi hiển thị. Như vậy khoảng cách giữa các điểm ảnh được chọn sao cho mắt người vẫn thấy được sự liên tục của ảnh. Việc chọn này tạo nên mật độ phân bổ đó chính là độ phân giải được phân bổ liên tục theo x, y. 1.1.4 Mức xám Mức xám (Gray level): Giá trị I[x, y] biểu diễn cường độ sáng được mã hóa của mỗi điểm ảnh (x, y). Giá trị đó còn được gọi là mức xám (grey level). I[x, y] có giá trị rời rạc và để tiện xử lý, ta coi giá trị của I[x, y] là nguyên: I[x, y] {0, 1, , L-1} với L là mức xám tối đa dùng để biểu diễn. Ảnh có nhiều mức xám gọi là ảnh đa cấp xám. Ảnh chỉ có 2 mức xám 0 và 1 gọi là ảnh nhị phân. Cách mã hóa kinh điển thường dùng là 16, 32 hay 64 mức. Mã hóa 256 mức là phổ dụng nhất do lý do kỹ thuật. Vì 28 = 256 (0, 1, . . . , 255), nên với 256 mức mỗi pixel sẽ được mã hóa bởi 8bit. Ảnh nhị phân, mỗi pixel mã hóa trên 1bit; còn ảnh 256 màu, mỗi pixel mã hóa trên 8bit. Ảnh màu là ảnh tổ hợp từ 3 màu cơ bản: đỏ (Red), lục (Green), lam (Blue) và thường thu nhận trên các dải băng tần khác nhau. Để biểu diễn cho mỗi điểm ảnh màu cần 3byte để mô tả 24bit màu. Ảnh xám là trường hợp đặc biệt của ảnh màu. Mỗi điểm ảnh màu có 3 giá trị (Red, Green, Blue), nếu 3 giá trị này bằng nhau thì ta có ảnh xám. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  9. 9 1.2 Các phép toán cơ bản trên ảnh nhị phân 1.2.1 Phép toán logic trên ảnh nhị phân Phép toán cơ bản nhất được sử dụng trong xử lý ảnh là: phép AND, phép 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: Hình 1.1 dưới đây minh họa những thao tác nói trên với giá trị nhị phân “1” có màu đen, còn giá trị nhị phân “0” có màu trắng. Hình 1.1. Hình minh họa các phép toán trên ảnh nhị phân 1.2.2 Các phép toán hình thái trên ảnh nhị phân Hình thái (morphology) có nghĩa là “hình thức và cấu trúc của một đối tượng”, hoặc là cách sắp xếp mối quan hệ bên trong giữa các phần của đối tượng. Hình thái có liên quan đến hình dạng, và hình thái số là một cách để mô tả hoặc phân tích hình dạng của một đối tượng số. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  10. 10 Những thao tác hình thái nhị phân được xây dựng trên ảnh chỉ có 2 mức xám 0 và 1, “0” ứng với màu trắng, “1” ứng với màu đen. Trước hết, để bắt đầu, ta hãy xem hình 1.2a. Tập hợp các điểm ảnh đen tạo nên đối tượng ảnh hình vuông và trong hình 1.2b, đối tượng ảnh cũng là hình vuông nhưng là hình vuông lớn hơn so với hình 1.2a một điểm ảnh về mọi phía, nghĩa là thay mọi lân cận trắng của các điểm ảnh trong hình 1.2a thành các điểm ảnh đen. Đối tượng trong hình 1.2b cũng được thao tác tương tự, tức là hình 1.2b được tăng thêm một điểm ảnh về mọi phía. Thao tác đó có thể coi như một phép dãn đơn giản, phép dãn một điểm ảnh về mọi phía. Việc dãn đó có thể được thực hiện cho đến khi toàn bộ ảnh được thay bằng các điểm ảnh đen. Do vậy, đối tượng ảnh trong hình 1.2a có thể được viết lại là{(3, 3) (3, 4) (4, 3) (4,4)}, với điểm ảnh phía trên bên trái là (0, 0). Tuy nhiên, việc viết như vậy sẽ rất dài dòng và bất tiện nên ta gọi đơn giản đối tượng ảnh là A, và các phần tử trong đó là các điểm ảnh. Hình 1.2. Hiệu quả của thao tác nhị phân đơn giản trên một ảnh nhỏ (a) Ảnh ban đầu (b) Ảnh dãn 1 điểm ảnh (c) Ảnh dãn 2 điểm ảnh so với ảnh ban đầu. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  11. 11 1.2.2.1 Phép dãn nhị phân (Dilation) Bây giờ ta sẽ chỉ ra thao tác tập hợp đơn giản nhằm mục đích định nghĩa phép dãn nhị phân. Phép dịch A bởi điểm x(hàng, cột), được định nghĩa là một tập: (A)x ={c | c = a + x, a A} (1.1) Chẳng hạn nếu x có toạ độ (1, 2), khi đó điểm ảnh đầu tiên phía trên bên trái của A sẽ dịch đến vị trí: (3, 3) + (1, 2) = (4, 5). Các điểm ảnh khác trong A sẽ dịch chuyển một cách tương ứng, tức ảnh được dịch sang phải (cột) điểm ảnh và xuống phía dưới (hàng) điểm ảnh. Bây giờ ta có thể định nghĩa phép dãn (dilation) qua lý thuyết tập hợp như sau: Phép dãn tập A bởi tập B, đó là tập : A B = {c | c =a + b, a A, b B} (1.2) Dễ thấy trong toán học, đây là phép tổng trực tiếp A và B. A là đối tượng ảnh được thao tác và B được gọi là phần tử cấu trúc (viết tắt là cấu trúc). Để hiểu kĩ hơn về điều này, ta hãy coi A là đối tượng trong hình 1.2a và B={(0,0), (0, 1)} Những phần tử trong tập C = A B được tính dựa trên công thức (1.1), có thể viết lại như sau: A B = (A + {(0, 0)}) (A + {(0, 1)}) (1.3) Hình 1.3. A dãn bởi B ___ Sinh viên: Nguyễn Thị Lan – CT1102
  12. 12 (a) Tập A ban đầu (b) Tập A cộng phân tử (0, 0) (c) Tập A cộng phân tử (0, 1) (d) Hợp của (b) và (c) (kết quả phép dãn). Nhận thấy rằng trong hình 1.4, có một số phần tử của đối tượng ban đầu sẽ không có. Hình 1.4. Dãn mất điểm ảnh (a) Ảnh A1 (b) Phần tử cấu trúcB1 (c) A1 được dãn bởi B1. Từ những điều trên, giúp ta tiếp cận đến một thao tác dãn ảnh có thể được “ máy tính hóa”. Ta hãy coi những phần tử cấu trúc như là một mẫu và dịch nó trên ảnh. Điều này được thể hiện khá rõ trong hình 1.5. Hình 1.5. Dãn ảnh sử dụng phần tử cấu trúc ___ Sinh viên: Nguyễn Thị Lan – CT1102
  13. 13 (a) Góc cấu trúc định vị trên điểm ảnh đen đầu tiên và những điểm đen cấu trúc được chép sang ảnh kết quả ở những vị trí tương ứng (b) Quá trình tương tự với điểm đen tiếp theo. (c) Quá trình hình thành. 1.2.2.2 Phép co nhị phân (Erotion) Nếu như phép dãn có thể nói là thêm điểm ảnh vào trong đối tượng ảnh, làm cho đối tượng ảnh trở nên lớn hơn thì phép co sẽ làm cho đối tượng ảnh trở nên nhỏ hơn, ít điểm ảnh hơn. Trong trường hợp đơn giản nhất, một phép co nhị phân sẽ tách lớp điểm ảnh bao quanh đối tượng ảnh, chẳng hạn hình 1.2b là kết quả của phép co được áp dụng đối với hình 1.2c. Nhìn chung, phép co một ảnh A bởi cấu trúc B có thể được định nghĩa như là tập: A B = {c |(B)c A} (1.4) Đầu tiên, ta hãy xét một ví dụ đơn giản sau đây: Hình 1.6. Phép co nhị phân (a) Phần tử cấu trúc được dịch chuyển đến vị trí một điểm đen trong ảnh. Trong trường hợp này, các thành viên của cấu trúc đều phù hợp với những điểm đen của ảnh cho nên cho kết quả điểm đen. (b) Phần tử cấu trúc dịch chuyển tới điểm ảnh tiếp theo trong ảnh, và có một điểm không phù hợp và kết quả là điểm trắng. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  14. 14 (c) Ở lần dịch chuyển tiếp theo, các thành viên của cấu trúc lại phù hợp nên kết quả là điểm đen. (d) Tương tự được kết quả cuối cùng là điểm trắng. Ta nhận thấy một điều quan trọng là: Phép co và phép dãn không phải là những thao tác ngược nhau. Có thể trong một số trường hợp đúng là phép co sẽ giải hoạt hiệu quả của phép dãn. Nhưng nhìn chung thì điều đó là không đúng, ta sẽ quan sát chúng một cách cụ thể hơn ở sau. Tuy nhiên, giữa phép co và phép dãn có mối quan hệ qua biểu thức sau đây: (B A)c = Bc  (1.5) Tức là phần bù của phép co ảnh A bởi B được coi như phép dãn phần bù của A bởi tập đối của B. Nếu như cấu trúc B là đối xứng (ở đây ta quan niệm đối xứng theo toạ độ) thì tập đối của B không thay đổi, nghĩa là  = A Khi đó: (B A)c = Bc A (1.6) Hay, phần bù của phép co A bởi B được coi như phép dãn nền của ảnh A (ta quy ước trong ảnh nhị phân rằng: đối tượng ảnh là những điểm đen quan sát, ảnh A là bao gồm cả điểm đen và nền). 1.2.2.3 Phép mở (Opening) Nếu như ta áp dụng phép co ảnh đối với một ảnh và sau đó lại áp dụng tiếp phép dãn ảnh đối với kết quả trước thì thao tác đó được gọi là phép mở ảnh, hay với I là ảnh, D là Dilation (dãn) và E là Erosion (co). Opening (I) = D(E(I)) (1.7) Tên của phép toán “mở” ảnh dường như đã phản ánh rõ tác dụng của nó. Tác dụng của nó chính là “mở” những khoảng trống nhỏ giữa các phần tiếp xúc trong đối tượng ảnh, làm cho ảnh dường như bớt “gai”. Hiệu quả này dễ quan sát nhất khi sử dụng cấu trúc đơn giản. Hình 1.7 trình bày ảnh có ___ Sinh viên: Nguyễn Thị Lan – CT1102
  15. 15 những phần của nó tiếp xúc nhau. Sau thao tác mở đơn giản đối tượng ảnh đã dễ nhận hơn so với ban đầu. Hình 1.7. Sử dụng phép toán mở (a) Một ảnh có nhiều vật thể được liên kết (b) Các vật thể được cách ly bởi phép mở với cấu trúc đơn giản (c) Một ảnh có nhiễu (d) Ảnh nhiễu sau khi sử dụng phép mở, các điểm nhiễu. 1.2.2.4 Phép đóng (Closing) Tương tự phép mở ảnh nhưng trong phép đóng ảnh, thao tác dãn ảnh được thực hiện trước, sau đó mới đến thao tác co ảnh và cùng làm việc trên cùng một phần tử cấu trúc. Close (I) = E(D(I)) (1.8) Hình 1.8. Phép đóng ___ Sinh viên: Nguyễn Thị Lan – CT1102
  16. 16 (a) Kết quả đóng sử dụng cấu trúc đơn giản. (b) Ảnh của một bảng mạch được phân ngưỡng và có các vết đứt (c) Ảnh tương tự sau khi đóng nhưng những nét đứt đã được nối liền. Hình 1.9. Phép đóng với độ sâu lớn (a) Từ hình 1.8a, sử dụng phép đóng với độ sâu 2 (b) Phép đóng với độ sâu 3 (c) Một vùng bàn cờ (d) Vùng bàn cờ được phân ngưỡng thể hiện những điểm bất quy tắc và một vài lỗ. (e) Sau khi thực hiện phép đóng với độ sâu 1 (f) Sau khi thực hiện phép đóng với độ sâu 2. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  17. 17 1.3 Các giai đoạn cơ bản của Xử lý ảnh Hình 1.10. Các giai đoạn chính trong Xử lý ảnh Trước hết là quá trình thu nhận ảnh. Ảnh thu nhận qua camera. Thường ảnh thu nhận qua camera là tín hiệu tương tự (loại camera ống kiểu CCIR), nhưng cũng có thể là loại tín hiệu số hóa (loại CCD- Charge Coupled Device). Ảnh cũng có thể thu nhận từ vệ tinh qua các bộ cảm ứng (sensor), hay ảnh, tranh được quét trên scaner. Tiếp theo là quá trình số hóa (Digitalizer) để biến đổi tín hiệu tương tự sang tín hiệu rời rạc (lấy mẫu) và số hóa bằng lượng hóa, trước khi chuyển sang giai đoạn xử lý, phân tích hay lưu trữ lại. Quá trình phân tích ảnh thực chất bao gồm nhiều công đoạn nhỏ. Trước hết là công việc tăng cường ảnh (Image Enhancement) để nâng cao chất lượng ảnh. Do những nguyên nhân khác nhau: có thể do chất lượng thiết bị thu nhận ảnh, do nguồn sáng hay do nhiễu, ảnh có thể bị suy biến. Do vậy cần phải tăng cường và khôi phục (Image Restoration) lại ảnh để làm nổi bật một số đặc tính chính của ảnh, hay làm cho ảnh gần giống nhất với trạng thái gốc – trạng thái trước khi ảnh bị biến dạng. Giai đoạn tiếp theo là phát hiện các đặc ___ Sinh viên: Nguyễn Thị Lan – CT1102
  18. 18 tính như biên (Edge Detection), phân vùng ảnh (Image Segmentation), trích chọn các đặc tính (Feature Extraction), v. v Cuối cùng, tùy theo mục đích của ứng dụng, sẽ là giai đoạn nhận dạng, phân lớp hay các quyết định khác. 1.4 Một số ứng dụng cơ bản của xử lý ảnh Kỹ thuật xử lý ảnh trước đây chủ yếu được sử dụng để nâng cao chất lượng hình ảnh, chính xác hơn là tạo cảm giác về sự gia tăng chất lượng ảnh quang học trong mắt người quan sát. Thời gian gần đây, phạm vi ứng dụng xử lý ảnh mở rộng không ngừng, có thể nói hiện không có lĩnh vực khoa học nào không sử dụng các thành tựu của công nghệ xử lý ảnh số. Trong y học các thuật toán xử lý ảnh cho phép biến đổi hình ảnh được tạo ra từ nguồn bức xạ X-ray hay nguồn bức xạ siêu âm thành hình ảnh quang học trên bề mặt film x-quang hoặc trực tiếp trên bề mặt màn hình hiển thị. Hình ảnh các cơ quan chức năng của con người sau đó có thể được xử lýtiếp để nâng cao độ tương phản, lọc, tách các thành phần cần thiết (chụp cắt lớp) hoặc tạo ra hình ảnh trong không gian ba chiều (siêu âm 3 chiều). Trong lĩnh vực địa chất, hình ảnh nhận được từ vệ tinh có thể được phân tích để xác định cấu trúc bề mặt trái đất. Kỹ thuật làm nổi đường biên (image enhancement) và khôi phục hình ảnh (image restoration) cho phép nâng cao chất lượng ảnh vệ tinh và tạo ra các bản đồ địa hình 3-D với độ chính xác cao. Trong ngành khí tượng học, ảnh nhận được từ hệ thống vệ tinh theo dõi thời tiết cũng được xử lý, nâng cao chất lượng và ghép hình để tạo ra ảnh bề mặt trái đất trên một vùng rộng lớn, qua đó có thể thực hiện việc dự báo thời tiết một cách chính xác hơn. Dựa trên các kết quả phân tích ảnh vệ tinh tại các khu vục đông dân cư còn có thể dự đoán quá trình tăng trưởng dân số, tốc độ ô nhiễm môi trường cũng như các yếu tố ảnh hưởng tới môi trường sinh thái. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  19. 19 Xử lý ảnh được sử dụng nhiều trong các hệ thống quản lý chất lượng và số lượng hàng hóa trong các dây truyền tự động, ví dụ như hệ thống phân tích ảnh để phát hiện bọt khí bên vật thể đúc bằng nhựa, phát hiện các linh kiện không đạt tiêu chuẩn (bị biến dạng) trong quá trình sản xuất hoặc hệ thống đếm sản phẩm thông qua hình ảnh nhận được từ camera quan sát. Xử lý ảnh còn được sử dụng rộng rãi trong lĩnh vực hình sự và các hệ thống bảo mật hoặc kiểm soát truy cập: quá trình xử lý ảnh với mục đích nhận dạng vân tay hay khuôn mặt cho phép phát hiện nhanh các đối tương nghi vấn cũng như nâng cao hiệu quả hệ thống bảo mật cá nhân cũng như kiểm soát ra vào. Ngoài ra, có thể kể đến các ứng dụng quan trọng khác của kỹ thuật xử lý ảnh tĩnh cũng như ảnh động trong đời sống như tự động nhận dạng, nhận dạng mục tiêu quân sự, máy nhìn công nghiệp trong các hệ thống điều khiển tự động, nén ảnh tĩnh, ảnh động để lưu và truyền trong mạng viễn thông v. v. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  20. 20 CHƢƠNG 2: XƢƠNG VÀ CÁC THUẬT TOÁN TÌM XƢƠNG 2.1 Khái niệm xƣơng Xương được coi như hình dạng cơ bản của một đối tượng, với số ít các điểm ảnh cơ bản. Ta có thể khôi phục các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương. Có một số định nghĩa toán học khác nhau về xương trong các tài liệu kỹ thuật và có nhiều thuật toán khác nhau cho tính toán chúng. Trong các tài liệu kỹ thuật, các khái niệm về xương và trục trung vị thường được sử dụng thay thế cho nhau ở một số tác giả, trong khi một số tác giả khác lại xem chúng chỉ liên quan với nhau mà không giống nhau. Tương tự, các khái niệm về tìm xương và làm mảnh cũng được coi là như nhau với một số tác giả và khác nhau đối với một số tác giả khác. Xương được sử dụng nhiều trong ứng dụng lĩnh vực máy tính, phân tích hình ảnh, và xử lý hình ảnh số, bao gồm nhận dạng ký tự quang học, nhận dạng vân tay, kiểm tra thị giác, nhận dạng mẫu, nén ảnh nhị phân. 2.2 Các hƣớng tiếp cận trong việc tìm xƣơng Các kỹ thuật tìm xương luôn là chủ đề nghiên cứu trong xử lý ảnh. Do đó tính phức tạp của nó, mặc dù có những nỗ lực cho việc phát triển các thuật toán tìm xương nhưng các phương pháp đưa ra đều bị mất mát thông tin. Có thể chia thành hai loại tìm thuật toán tìm xương cơ bản: Các thuật toán tìm xương dựa trên làm mảnh Các thuật toán tìm xương không dựa trên làm mảnh 2.2.1 Phƣơng pháp tìm xƣơng dựa trên làm mảnh 2.2.1.1 Sơ lƣợc về thuật toán làm mảnh Nghiên cứu về làm mảnh ta cần chú ý các vấn đề sau: Không phải tất cả các đối tượng đều có thể làm mảnh. Làm mảnh chỉ hữu dụng với các đối tượng là đường, nghĩa là chúng chỉ thẳng hoặc ___ Sinh viên: Nguyễn Thị Lan – CT1102
  21. 21 cong và nó không có tác dụng với các đối tượng có hình dạng đóng trong một vùng. Làm mảnh thông thường là bước chuẩn bị cho các bước tiếp theo xử lý một đối tượng của ảnh. Các bước tiếp theo làm việc trên các thuộc tính cần thiết của xương. Thuật toán làm mảnh ảnh số nhị phân là một trong các thuật toán quan trọng trong xử lý ảnh và nhận dạng. Xương chứa những thông tin bất biến về cấu trúc của ảnh, giúp cho quá trình nhận dạng hoặc vecto hóa sau này. Thuật toán làm mảnh là quá trình lặp duyệt và kiểm tra tất cả các điểm thuộc đối tượng. Trong mỗi lần lặp tất cả các điểm đối tượng sẽ được kiểm tra: nếu như chúng thỏa mãn điều kiện xóa nào đó tùy thuộc vào mỗi thuật toán thì nó sẽ bị xóa đi. Quá trình cứ lặp lại cho đến khi không còn điểm biên nào được xóa. Đối tượng được bóc dần lớp biên cho đến khi nào bị thu mảnh lại chỉ còn các điểm biên. 2.2.1.2 Tìm xƣơng dựa trên làm mảnh Thuật toán làm mảnh song song là thuật toán mà trong đó các điểm được xử lý theo phương pháp song song, tức là được xử lý cùng một lúc. Giá trị của mỗi điểm sau một lần lặp chỉ phụ thuộc vào giá trị của các láng giềng bên cạnh (thường là 8 – láng giềng) mà giá trị của các điểm này đã được xác định trong một lần lặp trước đó. Trong máy có nhiều bộ vi xử lý mỗi vi xử lý sẽ xử lý một vùng của đối tượng, nó có quyền đọc từ các điểm ở vùng khác nhau nhưng chỉ được ghi trên vùng của nó xử lý. Trong thuật toán làm mảnh tuần tự các điểm thuộc đối tượng sẽ được kiểm tra theo một thứ tự nào đó (chẳng hạn các điểm được xét từ trái qua phải, từ trên xuống dưới). Giá trị của điểm sau mỗi lần lặp không những phụ thuộc vào giá trị của các láng giềng bên cạnh mà còn phụ thuộc vào các điểm đã được xét trước đó trong chính lần lặp đang xét. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  22. 22 Chất lượng của thuật toán làm mảnh được đánh giá theo các tiêu chuẩn được liệt kê dưới đây nhưng không nhất thiết phải thỏa mãn đồng thời tất cả các tiêu chuẩn: Bảo toàn tính liên thông của đối tượng và phần bù của đối tượng Sự tương hợp giữa xương và cấu trúc của ảnh đối tượng Bảo toàn các thành phần liên thông Bảo toàn các điểm cụt Xương chỉ gồm các điểm biên, càng mảnh càng tốt Bền vững đối với nhiễu Xương cho phép khôi phục ảnh ban đầu của đối tượng Xương thu được ở chính giữa đường nét của đối tượng được làm mảnh Xương nhận được bất biến với phép quay 2.2.2 Tìm xƣơng không dựa trên làm mảnh Để tách được xương của đối tượng có thể sử dụng đường biên của đối tượng. Với bất cứ một điểm p nào đó trên đối tượng, đều có thể bao nó bởi một đường biên. Nếu như có nhiều hơn một điểm biên có khoảng cách ngắn nhất thì p nằm trên trục trung vị. Tất cả các điểm như vậy lập thành trục trung vị của đối tượng. Điều đó phải được thực hiện với độ phân giải cao, hoặc khoảng cách Euclide là không bằng nhau, và như thế các điểm ảnh xương sẽ mất đi. Ta dễ dàng thu được một xấp xỉ của trục trung vị trên một lưới đơn giản sau 2 bước: Bước thứ nhất, tính khoảng cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất. Như vậy cần phải tính toán khoảng cách tới tất cả các điểm biên của ảnh. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  23. 23 Bước thứ hai, khoảng cách của ảnh đã được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên xương của đối tượng. Hình 2.1. Trục trung vị Hầu hết các nhà nghiên cứu đều cho rằng thay đổi trục trung vị thường không mang lại một xương chuẩn, và thời gian tính toán quá dài, tuy nhiên nó là mẫu cơ bản của phần lớn các phương pháp làm mảnh. Phương pháp thay đổi trục trung vị được coi là một phương pháp làm mảnh không lặp, ngoài ra còn có một vài thuật toán duyệt các điểm biên 2 bên mẫu, tính điểm trung tâm các đường nối giữa các điểm biên đó và xương thu được là tâp hợp các điểm trung tâm đó (line following) hoặc các phương thức sử dụng chuỗi Fourier (Fourier transform) cũng được coi là làm mảnh không lặp. 2.2.2.1 Khái quát lƣợc đồ Voronoi Lược đồ Voronoi là một công cụ hiệu quả trong hình học tính toán. Cho hai điểm Pi, Pj là 2 phần tử của tập Ω gồm n điểm trong mặt phẳng. Tập các điểm trong mặt phẳng gần hơn là nửa mặt phẳng H (Pi, Pj) chứa điểm và bị giới hạn bởi đường trung trực của đoạn thẳng. Do đó, tập các điểm gần hơn bất kỳ điểm nào có thể thu được bằng cách giao n-1 các nửa mặt phẳng H (Pi, Pj) V ( ) = H ( ) i j (i= 1, , n) (2.1) Định nghĩa 2.1 [Đa giác/ Sơ đồ Voronoi] Sơ đồ Voronoi của Ω là tập hợp tất cả các V ( ) ___ Sinh viên: Nguyễn Thị Lan – CT1102
  24. 24 Vor (Ω) = V ( ) Ω (là một đa giác) (2.2) Định nghĩa 2.2 [Đa giác Voronoi tổng quát] Cho tập các điểm Ω, đa giác Voronoi của tập con U của Ω được định nghĩa như sau: V (U)= {P | v U, w Ω \ U : d (P, w)}= V ( ) U (2.3) 2.2.2.2 Trục trung vị Voronoi rời rạc Định nghĩa 2.3 [Bản đồ khoảng cách – Distance Map] Cho đối tượng S, đối với mỗi (x, y) S, ta tính giá trị khoảng cách map(x, y) với hàm khoảng cách d (. , . ) như sau: (x, y) S: map (x, y)= min d[ (x, y ), ( )] (2.4) Trong đó ( ) B (S) – tập các điểm biên của S Tập tất cả các map (x, y), kí hiệu là DM (S), được gọi bản đồ khoảng cách của S. Chú ý: Nếu hảm khoảng cách d (. , . ) là khoảng cách Euclide, thì phương trình (2.4) chính là khoảng cách ngắn nhất từ một điểm bên trong đối tượng tới biên. Do đó, bản đồ khoảng cách được gọi là bản đồ khoảng cách Euclide EDM(S) của S. Định nghĩa trên được dùng cho cả hình rời rạc lẫn liên tục. Định nghĩa 2.4 [ Tập các điểm biên sinh] Cho map (x, y) là khoảng cách ngắn nhất từ (x, y) đến biên (theo định nghĩa 2.3). Ta định nghĩa : Khi đó tập các điểm biên sinh ^B (S) được định nghĩa bởi: ^B (S)= (x, y), (x, y) S (2.5) ___ Sinh viên: Nguyễn Thị Lan – CT1102
  25. 25 Do S có thể chứa các đường biên rời nhau, nên ^B (S) bao gồm nhiều tập con, mỗi tập mô tả một đường biên phân biệt: ^B (S) = { } (2.6) Định nghĩa 2.5 [Trục trung vị Voronoi rời rạc (DVMA)] Trục trung vị Voronoi rời rạc được định nghĩa là kết quả của sơ đồ Voronoi bậc nhất rời rạc của tập các điểm biên sinh giao với hình sinh S: DVMA (^B (S))=Vor (^B (S)) S (2.7) 2.2.2.3 Xƣơng Voronoi rời rạc Định nghĩa 2.6 [ Xương Voronoi rời rac – Discrete Voronoi Skeleton] Xương Voronoi rời rạc theo ngưỡng T, kí hiệu là SkeDVMA (^B (S),T) (hoặc Ske (^B (S), T)) là một tập con của trục trung vị Voronoi: SkeDVMA (^B (S), T) = { (x, y)| (x, y) DVMA (^B (S)), Ψ (x, y) > T } (2.8) Ψ: là hàm hiệu chỉnh Dễ thấy ngưỡng T càng lớn thì số lượng điểm tham gia trong xương Voronoi càng ít (Hình 2.2). Hình 2.2. Xương Voronoi rời rạc ảnh hưởng của các hàm hiệu chỉnh khác nhau ___ Sinh viên: Nguyễn Thị Lan – CT1102
  26. 26 (a) Ảnh nhị phân. (b) Sơ đồ Voronoi (c) Hiệu chỉnh bởi hàm Potential, T= 9.0 (d) Hiệu chỉnh bởi hàm Potential, T=18.0 2.2.2.4 Thuật toán tìm xƣơng Thuật toán tìm xương dựa trên một số ý tưởng sau: Tăng trưởng: Việc tính toán sơ đồ Voronoi được bắt đầu từ một điểm sinh trong mặt phẳng. Sau đó điểm sinh thứ hai được thêm vào và quá trình tính toán tiếp tục với đa giác Voronoi đã tìm được với điểm vừa được thêm vào đó. Cứ như thế, quá trình tính toán sơ đồ Voronoi được thực hiện cho đến khi không còn điểm sinh nào được thêm vào. Nhược điểm của chiến lược này là mỗi khi điểm mới được thêm vào, nó có thể gây ra sự phân vùng toàn bộ các đa giác Voronoi đã được tính. Chia để trị: Tập các điểm biên đầu tiên được chia thành hai tập điểm có kích cỡ bằng nhau. Sau đó thuật toán tính toán sơ đồ Voronoi cho cả hai tập con điểm biên đó. Cuối cùng, người ta thực hiện việc ghép cả hai sơ đồ Voronoi trên để thu hút được kết quả mong muốn. Tuy nhiên, việc chia tập các điểm biên thành hai phần không phải được thực hiện một lần, mà được lặp lại nhiều lần cho đến khi việc tính toán sơ đồ Voronoi trở nên đơn giản. Vì thế, việc tính sơ đồ Voronoi trở thành vấn đề làm thế nào để trộn hai sơ đồ Voronoi lại với nhau. Thuật toán sẽ trình bày ở đây là sự kết hợp của 2 ý tưởng trên. Tuy nhiên, nó sẽ mang lại nhiều dáng dấp của thuật toán chia để trị Hình 2.3 minh họa ý tưởng của thuật toán này. Mười một điểm biên được chia thành 2 phần (bên trái: 1-6, bên phải: 7-11) bởi đường gấp khúc , và hai sơ đồ Voronoi tương ứng Vor ( ) và Vor( ). Để thu được sơ đồ Voronoi Vor( ), ta thực hiện việc trộn hai sơ đồ trên và xác định lại ___ Sinh viên: Nguyễn Thị Lan – CT1102
  27. 27 một số đa giác sẽ bị sửa đổi do ảnh hưởng của các điểm bên cạnh thuộc sơ đồ kia. Mỗi phần tử của sẽ là một bộ phận của đường trung trực nối hai điểm mà một điểm thuộc Vor ( ) và một thuộc Vor ( ). Trước khi xây dựng , ta tìm ra phần tử đầu và cuối của nó. Nhìn vào hình 2.3, ta nhận thấy rằng cạnh là các tia. Dễ nhận thấy rằng việc tìm các cạnh đầu và cuối của trở thành việc tìm cạnh vào . Hình 2.3. Minh họa thuật toán trộn hai sơ đồ Voronoi Sau khi tìm được , các điểm cuối của được sử dụng để xây dựng phần tử đầu tiên trong hình bên). Sau đó thuật toán tìm điểm giao của với Vor ( ) và Vor ( ). Trong ví dụ trên, đầu tiên giao với V(3). Kể từ đây, các điểm nằm trên phần kéo dài sẽ gần điểm 6 hơn điểm 3. Do đó, phần tử tiếp theo của sẽ thuộc vào đường trung trực của điểm 6 và điểm 7. Sau đó điểm giao tiếp theo của sẽ thuộc vào Vor ( ); sẽ đi vào V(9) và sẽ được thay thể bởi . Quá trình này sẽ kết thúc khi gặp phần tử cuối . Trên đây chỉ là minh họa cho thuật toán trộn hai sơ đồ Voronoi trong chiến lược chia để trị. Tuy nhiên, trong thuật toán sẽ trình bày ở đây thì sự thực hiện có khác một chút. Tập các điểm ảnh không phải được đưa ngay vào từ đầu mà sẽ được quét vào từng dòng một. Giả sử tại bước thứ i, ta đã thu được một sơ đồ Voronoi gồm i-1 hàng các điểm sinh Vor ( ). Tiếp theo, ta quét lấy một hàng các điểm ảnh từ tập các điểm biên còn lại. Thực hiện việc tính toán sơ đồ Voronoi Vor ( ) cho hàng này, sau đó trộn Vor ( ) ___ Sinh viên: Nguyễn Thị Lan – CT1102
  28. 28 với Vor ( ). Kết quả ta sẽ được một sơ đồ mới, và lại thực hiện việc quét hàng các điểm sinh còn lại v. v. . Quá trình này sẽ kết thúc khi không còn điểm biên nào để thêm vào sơ đồ Voronoi. Do Vor ( ) sẽ có dạng răng lược (nếu có k điểm thì Vor ( ) sẽ gồm k-1 đường thẳng đứng), nên việc trộn Vor ( ) với Vor ( ) có phần đơn giản hơn. Hình 2.4. Minh họa thuật toán thêm một điểm biên vào sơ đồ Voronoi Giải thuật trên có thể được mô tả bằng ngôn ngữ tựa Pascal như sau: Procedure VORONOI (*Si: Tập các điểm cua i dòng quét đầu tiên, 0 <= i <=iMAX, Vor (Si) sơ đồ Voronoi của Si *) Begin i:=0;Si:=rỗng; While (i<imax∧ Si ⊂ straight_line) do Begin (Khởi tạo sơ đồ Voronoi cho đến khi nó chưa ít nhất một đỉnh ) Increment i;GetScanLine Li; Vor (Si) = VoroPreScan (Vor (Si-1, Li)); End ___ Sinh viên: Nguyễn Thị Lan – CT1102
  29. 29 While (i < imax) do Begin Increment i; GetScanLine Li; Vor (Li) := các đường trung trực sinh bởi các điểm sinh thuộc Li Vor (Si) := VoroLink (Vor (Si-1), Vor (Li)); End End. Giả sử xét trên hệ trục tọa độ thực. Ảnh vào được quét từ dưới lên. Tọa độ y (biến i) tương ứng với từng dòng quét được tăng dần theo từng dòng. Trong thủ tục trên, hàm quan trọng nhất là hàm VoroLink, hàm này thực hiện việc trộn sơ đồ Voronoi của dòng dã được quét trước đó với sơ đồ Voronoi của dòng hiện tại thứ i. Trong vòng lặp trên, hàm VoroPreScan là một biến cụ thể của hàm VoroLink, có nhiệm vụ khởi tạo sơ đồ Voronoi và thoát khỏi vòng lặp ngay khi nó thành lập được sơ đồ Voronoi chứa ít nhất một đỉnh. Hàm VoroLink thực hiện việc trộn hai sơ đồ Voronoi Vor (Si-1) và Vor (Li) với nhau để thành Vor (Si). 2.3 Cắt tỉa xƣơng của ảnh 2.3.1 Khái niệm cắt tỉa xƣơng Cắt tỉa xương của ảnh là loại bỏ đi một ít nhiễu hoặc vài sự thay đổi của đường biên dẫn đến tạo ra những nhánh thừa cái mà có thể làm ảnh hưởng nghiêm trọng tới hình dạng cơ bản của xương. 2.3.2 Kỹ thuật cắt tỉa xƣơng với DCE 2.3.2.1 Ý tƣởng chính của phƣơng pháp Nhóm tác giả Xiang Baia, Login Jan Latec ki, Wen-Yu Liu đã đề xuất một phương pháp loại bỏ hoàn toàn những điểm lồi ra mà không loại bỏ những điểm biên, vì vậy không loại bỏ những điểm xương chính. Những điểm ___ Sinh viên: Nguyễn Thị Lan – CT1102
  30. 30 sai hoặc thừa ra hoàn toàn bị loại bỏ trong khi những nhánh xương chính không bị ngắn đi. Phương pháp này có thể cắt tỉa xương dựa trên việc phân chia đường biên thành những đoạn cong. Ý tưởng chính của phương pháp là di chuyển tất cả các điểm xương của điểm tăng trưởng nằm trên cùng đoạn đường biên. Từ đó đã đặt ra câu hỏi là làm thế nào để tìm ra các đoạn phân chia đường biên tốt nhất. Nhóm tác giả đã tìm ra được sự phân chia như vậy nhờ quá trình DCE. Phương pháp cắt tỉa xương có thể được áp dụng với bất kỳ bộ xương đầu vào nào. Mỗi điểm xương là trung tâm của vòng tròn lớn nhất và những điểm đường biên tiếp tuyến với đường tròn đều được đưa ra. Cắt tỉa xương không phải thực hiện sau khi đã tính được bộ xương mà được thực hiện đồng thời với quá trình tăng trưởng xương. 2.3.2.2 Rời rạc hóa đƣờng cong DCE được giới thiệu bởi các nhóm tác giả Xiang Bai và các cộng sự. Đường biên của đối tượng trong ảnh số bị thay đổi bởi nhiễu và các lỗi phân đoạn. DCE loại bỏ những thay đổi đó trong khi vẫn đảm bảo được hình dạng ban đầu của đối tượng bởi đơn giản hóa hình dạng. Bất kỳ đường cong của ảnh số có thể được coi là một đa giác mà không bị mất thông tin, nhưng phải có số đỉnh lớn để nghiên cứu sự phát triển của hình dạng. Ý tưởng cơ bản của sự phát triển đề xuất là các đa giác đều đơn giản hơn. Trước tiên tác giả Xiang Bai đưa ra phép đo liên quan K: (2.9) Trong đó s1, s2 là những cạnh của đa giác liên quan tới đỉnh v; (s1, s2) là góc quay tại đỉnh chung của đoạn s1, s2; l là tổng độ dài của đường cong đa giác C. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  31. 31 Đầu vào là đường biên đa giác P với n đỉnh, DCE tạo ra một chuỗi các đa giác đơn giản với K là nhỏ nhất. Tác giả còn chỉ ra rằng một tính chất quan trọng của DCE là phân chia trình tự với đa giác đầu vào P. {v1, . . . . , vn} là đỉnh của P, {u1, . . . . , um} n-k {v1, . . . . , vn} là đỉnh lồi của P sao cho m n-k. Nhận thấy DCE và phân chia trình tự có thể được định nghĩa cho một tập hữu hạn của đường cong đa giác. Trong mỗi bước DCE một vectơ đơn được loại bỏ từ một đa giác mà phép đo liên quan là nhỏ nhất. Phương pháp cắt tỉa đề xuất có thể được áp dụng cho mặt phẳng D, với đường biên D bao gồm số các đa giác đóng đơn giản. DCE có thể loại bỏ hiệu quả nhiễu và từng phần không quan trọng của ảnh, nhưng vẫn cần phải có một giới hạn T dừng đúng cách để phù hợp với những ứng dụng cụ thể. Nói cách khác tìm kiếm k để đa giác đơn giản Pn-k miêu tả chi tiết những đường biên đầu vào. 2.3.2.3 Phƣơng pháp cắt tỉa xƣơng với DCE Cho một bộ xương S(D) của một mặt phẳng D và đưa ra một DCE đa giác đơn giản Pk, thể hiện cắt tỉa xương bằng cách di chuyển tất cả những điểm s S(D), như vậy tạo ra những điểm tăng trưởng tan(s) của s chứa trong cùng đoạn DCE mở. Mỗi điểm cắt tỉa s là kết quả từ phần đường biên cục bộ với sự phân chia DCE, và do đó, s có thể coi như là điểm xương không quan trọng và có thể loại bỏ. Quá trình làm đơn giản đường biên với DCE đã hoàn thành cắt tỉa nhánh của xương. Đặc biệt, loại bỏ một đỉnh lồi v từ Pn-k tới Pn-(k+1) bởi DCE, tức là hoàn thành loại bỏ những nhánh xương mà kết thúc tại v. Trong hình 2.5 minh họa việc sử dụng DCE thu được một hình đa giác với 7 đỉnh và xương của đối tượng được cắt tỉa dựa trên đa giác đó. Chỉ có 5 nhánh xương kết thúc tại 5 đỉnh lồi của đa giác đơn giản. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  32. 32 Hình 2.5. Minh họa cắt tỉa xương với DCE Tác giả thực hiện phân tích đoạn DCE dựa trên các đỉnh lồi bởi đơn giản hóa DCE. Khi một đỉnh lồi trở thành một đỉnh lõm trong quá trình phát triển của DCE, thì những nhánh xương kết thúc tại đỉnh đó bị loại bỏ. Cách tiếp cận này cho phép loại bỏ những nhánh nhỏ trong quá trình phát triển DCE. Một thuộc tính quan trọng của DCE là gây ra phân chia đường biên và mỗi phân chia làm giảm các đỉnh của đường biên đa giác, kết quả có một nhánh xương kết thúc tại mỗi điểm phân chia. Theo các kết quả thực nghiệm mà tác giả đã nghiên cứu, trong một bước tiến hóa DCE nếu đỉnh ui của đa n-k n- (k+1) giác bị xóa (tức là ui P – P ) hoặc trở thành lõm (do việc xóa đi một trong những đỉnh bên cạnh của nó) thì cung [ui-1, ui+1] thay thế cung [ui-1, ui], [ui, ui+1]. Khi đó cắt tỉa xương sẽ loại bỏ toàn bộ nhánh xương kết thúc tại ui. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  33. 33 CHƢƠNG 3: KỸ THUẬT CẮT TỈA XƢƠNG DỰA VÀO ĐỘ UỐN Chương này trình bày kỹ thuật cắt tỉa xương được đề xuất bởi tác giả Wei Shena, Xiang Baia, Rong Hu, Hongyuan Wang, Login Jan Latec ki [4]. 3.1 Giới thiệu Xương còn được gọi là trục trung vị, lần đầu tiên được xác định bởi tác giả Blum[6], là cách mô tả hình dạng rất hữu ích, vì nó chứa các đặc trưng hình dạng của đối tượng gốc. Như vậy, xương là một dạng cần thiết để biểu diễn và phân tích hình dạng trong nhiều lĩnh vực ứng dụng như hệ thống tra cứu ảnh dựa trên nội dung, hệ thống nhận dạng ký tự. . . Những thập kỷ qua, có rất nhiều phương pháp trích chọn xương đã được đề xuất. Các thuật toán toán tìm xương có thể được phân thành 5 loại: 1. Thuật toán làm mảnh 2. Thuật toán miền rời rạc dựa trên lược đồ Voronoi 3. Thuật toán dựa trên khoảng cách biến đổi 4. Thuật toán co đường biên của đối tượng được lặp đi lặp lại 5. Dựa trên phép toán hình thái học Hầu hết các phương pháp này có một hạn chế chung đó là có độ nhạy cảm cao đối với nhiễu đường biên: những biến đổi nhỏ trên đường biên của đối tượng có thể làm thay đổi đáng kể xương nhận được. Do các phương pháp này thường tạo ra các nhánh xương giả, ảnh hưởng tới việc nhận dạng đối tượng dựa trên cấu trúc xương. Ví dụ như xương trong hình 3.1(a) có nhiều nhánh xương thừa được phát sinh ra bởi nhiễu đường biên. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  34. 34 (a) (b) Hình 3.1. Minh họa xương của ảnh Bộ xương (a) có nhiều nhánh thừa, để loại bỏ chúng phương pháp cắt tỉa xương được áp dụng. Hình (b) minh họa kết quả cắt tỉa xương. Nhiều phương pháp của các tác giả đã được đề xuất để phát triển cắt tỉa xương. Một trong số các phương pháp đó là cần làm mịn đường biên trước khi tính toán các điểm xương, nhằm mục đích loại bỏ nhiễu đường biên không mong muốn. Tuy nhiên, làm mịn đường biên có thể làm thay đổi vị trí đường biên và do đó vị trí của xương có thể bị dịch chuyển, đó là khó khăn trong việc phân biệt nhiễu từ các thông tin hình dạng tần số thấp trên đường bao. Một số khác gán độ đo có ý nghĩa cho các điểm xương hoặc nhánh xương, sau đó những điểm xương hoặc nhánh xương sẽ được cắt tỉa khi giá trị ý nghĩa nhỏ hơn giá trị ngưỡng. Một vài phương pháp quan trọng dựa trên độ đo đã được đề xuất: Tác giả Ogniewicz và Kubler đã trình bày một vài độ đo dựa trên chiều dài như chiều dài cung giữa hai điểm và chiều dài đoạn đường bao ngắn nhất giữa hai điểm. Tác giả Shaked và Bruckstein tổng hợp nhiều phương pháp, và họ đề nghị chọn độ dày bào mòn cực đại như là là độ đo. Tác giả Couprie và Zrour cũng đã đề xuất độ đo được gọi là góc phân giác, là góc giữa đường kết nối các điểm xương với các điểm được tạo ra nó. Những ___ Sinh viên: Nguyễn Thị Lan – CT1102
  35. 35 độ đo của các phương pháp được các tác giả đề xuất đều có hạn chế tương tự nhau: Thứ nhất, là một số nhánh xương thừa không được loại bỏ hoàn toàn, ảnh hưởng tới quá trình đối sánh hình dạng dựa trên cấu trúc xương. Thứ hai, kết quả của việc cắt tỉa là không thể hiện được các chi tiết nhỏ. Thứ ba, đôi khi kết quả của việc cắt tỉa trái với trực giác của con người. Để khắc phục các hạn chế nêu trên của các phương pháp cắt tỉa xương hiện tại nên nhóm tác giả Wei Shena, Xiang Baia, Rong Hu, Hongyuan Wang, Login Jan Latec ki đã đề xuất một phương pháp cắt tỉa xương dựa trên độ đo ý nghĩa gọi là tỷ lệ uốn (BPR – Bending Potential Ratio). Việc đưa ra quyết định về việc một nhánh xương nên được cắt tỉa hay không là dựa vào ngữ cảnh của đoạn đường biên tương ứng với nhánh xương. Phương pháp BPR đã chỉ ra sự đóng góp của đoạn đường biên đó với đánh giá trên hình dạng toàn cục, chứ không chỉ đánh giá trên hình dạng cục bộ như phương pháp cắt tỉa xương khác. Nói chung nó phụ thuộc vào vị trí cụ thể trong toàn bộ đường bao (ví dụ, một đoạn có thể được coi là không ý nghĩa trên một vị trí này nhưng nó có thể trở thành ý nghĩa trong một vị trí khác). BPR là độ đo ý nghĩa không giống như các độ đo ý nghĩa khác chỉ chứa thông tin hình dạng cục bộ của những đường bao trong ngữ cảnh cụ thể, nó mô tả khả năng uốn của một đoạn đường bao. BPR có thể đánh giá cả hai thông tin hình dạng cục bộ và toàn cục. Vì vậy theo tác giả Wei Shena [4] thì xương không nhạy cảm với biến dạng đường biên cục bộ. 3.2 Phƣơng pháp cắt tỉa xƣơng theo BPR (Bending Potential Ratio) 3.2.1 Định nghĩa cơ bản Để đơn giản tác giả Wei Shena đã giả thiết rằng đường biên của một đối tượng 2D là một đường cong đóng C trong R2. Tập F được bao bọc bên trong đường bao C biểu diễn vùng của đối tượng. Tất cả các định nghĩa và ___ Sinh viên: Nguyễn Thị Lan – CT1102
  36. 36 phát biểu sau sẽ được áp dụng cho một tập phẳng F có đường bao bao gồm một số hữu hạn đường cong khép kín, nghĩa là F có thể có một số hữu hạn các lỗ, vì nếu một điểm xương có nguồn gốc từ hai đường cong khác nhau nó sẽ không bao giờ bị loại bỏ khỏi xương. Do đó, bất kỳ một điểm xương nào được lấy ra bắt đầu từ một đường cong duy nhất, nó sẽ bị dịch chuyển và do đó thuật toán chỉ tập trung giải quyết vào trường hợp của một đường cong đơn C. Cho một điểm p, hàm khoảng cách k được định nghĩa như sau: (3.1) Trong đó, d (, ) là độ đo khoảng cách Euclide Đối với một điểm , r (p) biểu thị một tập hợp các điểm biên gần p nhất. Khi đó, d (p, r (p)) = k (p) (3.2) Định nghĩa 3.1. Tập các điểm sinh R (p) như là một tập hợp các điểm nằm trên đường bao C mà gần với điểm p nhất hoặc là 8- láng giềng của p nằm phía trong đường bao, tức là R (p) = R8 (p) r (p) = {r (q) | q N8 (p)} r (p), (3.3) Trong đó N8 (p) là 8 láng giềng của điểm p trong đường bao và R8 (p) = {r (q)| q N8 (p)}. Do vậy, nếu p là một điểm của xương, n (R (p)) 2 (3.4) Trong đó hàm n () biểu thị số của các phần tử trong tập hợp. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  37. 37 3.2.2 Tỷ lệ uốn (BPR – Bending Potential Ratio) 3.2.2.1 Định nghĩa của tỷ lệ uốn Xét hai điểm q1, q2 R (p) (n (R (p)) 2) thể hiện trong hình 3.2, các đoạn đường bao ngắt nhất giữa q1 và q2 được ký hiệu là C (q1, q2). Khi đoạn đường bao là một tâp hợp các điểm ảnh, chúng ta đo chiều dài của đoạn đường bao bằng tổng khoảng cách Euclide giữa mỗi cặp ảnh điểm lân cận. Khoảng cách giữa hai điểm láng giềng di chuyển theo chiều ngang/dọc là 1 và theo đường chéo là . Nếu q1, và q2 chia đường bao thành 2 đoạn có chiều dài bằng nhau, một trong 2 đoạn đó được ký hiệu là C (q1, q2). Hình 3.2. Định nghĩa của điểm ghost và BPR Định nghĩa 3.2. Cho một đoạn đường cong C (q1, q2), gọi l (q1, q2) là chiều dài của cung C (q1, q2). Chúng ta xây dựng một hình tam giác cân với cơ 2 sở q1q2 và với đỉnh g R d (g, q1)= d (g, q2) = l (q1, q2). (3.5) Thực tế có hai điểm khác nhau thỏa mãn công thức (3.5), nó được đánh dấu với g1 và g2 thể hiện trong hình 3.3c. Tác giả Wei Shena định nghĩa điểm g là điểm chốt của C (q1, q2). ___ Sinh viên: Nguyễn Thị Lan – CT1102
  38. 38 Thông thường, điểm chốt g không nằm trên đường bao, trừ khi các đoạn đường bao là một đoạn của đa giác đối xứng như trong hình 3.3b. Nếu g nằm trên đường bao như hình 3.3a, thì l (g, q1)> d (g, q1), l (g, q2)>d (g, q2), l(q1, q2 ) >d (g, q1)+d (g, q2), và g sẽ không thỏa mãn công thức (3.5). Hình 3.3. Vùng của điểm ghost Định nghĩa 3.3. Cho điểm p nằm trong đường cong C với n(R(p)) , và gọi q1, q2 là hai điểm thuộc R (p). Gọi g là điểm chốt của đoạn đư ờng bao C (q1, q2). Từ hình 3.2 cho hg là chiều cao của tam giác q1pq2. Tỷ lệ uốn (BPR) (q1, p, q2) được định nghĩa như sau: . (3.6) 3.2.2.2 Xác định tỷ lệ uốn BPR Từ hình 3.2, khi tam giác q1pq2 là một tam giác cân, thì ta có hg = (3.7) Dễ thấy hg cung cấp thông tin hình dạng cục bộ của đoạn đường bao C(q1, q2), với chiều dài của cung l (q1, q2), thuộc tính của đoạn đường bao. Với một khoảng cách d(q1, q2) cố định, nếu l (q1, q2) lớn thì có khả năng uốn cong của C(q1, q2) là lớn. Do đó, hg phản ánh tỷ lệ uốn của đoạn đường bao C(q1,q2). Một đoạn đường bao cùng với điểm uốn cong cực đại và có một kết nối giữa ___ Sinh viên: Nguyễn Thị Lan – CT1102
  39. 39 độ cong cực đại của đường bao và xương tạo ra một nhánh xương. Do đó, hg được xem xét như là một phép đo để đánh giá tầm quan trọng của đoạn đường bao. Theo công thức lượng giác, chúng ta có (3.8) Từ đó ta suy ra (3.9) Nếu p là một điểm xương, là xấp xỉ với, ; vì vậy có được (3.10) Công thức (3.10) chỉ ra rằng hp chứa không chỉ là thông tin của góc phân giác mà còn là chiều rộng của đối tượng. Dù một đoạn đường bao là ý nghĩa hay không được xác định không chỉ bởi các thông tin của chính nó, ví dụ: chiều dài của cung, nhưng cũng có thể trong ngữ cảnh đó là nơi mà đã được xác định vị trí của nó. Đoạn đường bao tương tự có thể nhiều hơn, có thể được coi là không ý nghĩa nếu nó nằm trong một phần rộng của hình dạng, trong khi nếu nó nằm trên một phần nhỏ của hình dạng thì nó có thể được coi như là một đặc trưng riêng. Do đó tỉ lệ hg và hp, tỷ lệ uốn tích hợp cả hai thông tin hình dạng cục bộ và toàn cục. Nó có thể được sử dụng để xác định xem một đường cong tạo ra một nhánh xương. Đặc biệt, hp là bằng 0 nếu các tiếp tuyến trên q1 và q2 là song song. Trong trường hợp này giá trị BPR là vô hạn, nó chỉ ra rằng p là một điểm xương. Hình 3.4 chỉ ra hiệu quả của phương pháp BPR trong cắt tỉa xương. Các đỉnh của hình 3.4 là tương tự nhau, tuy nhiên, chúng có hình dạng khác nhau góp phần cho đối tượng. Đỉnh của hình 3.4a có nhiều khả năng là một chi tiết không đáng kể trên đường biên, và ___ Sinh viên: Nguyễn Thị Lan – CT1102
  40. 40 vì vậy nhánh có nguồn gốc từ nó nên được cắt tỉa, trong khi đỉnh với cùng kích thước như hình 3.4b có nhiều khả năng là đặc trưng hình dạng quan trọng, và như vậy có thể tạo ra một nhánh xương. Đỉnh trong hình 3.4c là gần góc bên phải hơn so với đỉnh trong hình 3.4a, và do đó nó đưa ra một nhánh xương, vì nó thay thế góc bên phải như đặc trưng của hình dạng. Như đã chỉ ra trong hình 3.4, xương thu được bởi phương pháp của tác giả Wei Shena có thể phân biệt giữa nhánh không đáng kể như trong hình 3.4a và các nhánh quan trọng như trong hình 3.4 (b, c). Hình 3.4. Mẫu hình chữ nhật với cùng một đỉnh được thêm vào đường biên của hình Hàng (1). Xương thu được bằng phương pháp đề xuất. Hàng (2). Xương của cùng một hình được cắt tỉa bằng độ đo ý nghĩa của chiều dài đoạn đường biên ngắn nhất ___ Sinh viên: Nguyễn Thị Lan – CT1102
  41. 41 3.2.2.3 Mối quan hệ của BPR với các độ đo ý nghĩa khác Bằng công thức (3.7), (3.8) và (3.11) chúng ta có được (3.11) Công thức (3.11) thể hiện sự kết nối giữa BPR và độ đo ý nghĩa: khoảng cách của dây cung , chiều dài của đoạn đường biên ngắn nhất l và góc phân giác . Sự tích hợp của cả 3 độ đo này là một trong những đóng góp chính của phương pháp đã được đề xuất. Nó là hợp lý để tích hợp ba độ đo với nhau theo cách này, nếu góc lớn hơn, có nhiều khả năng p là một điểm xương, và chức năng của tiếp tuyến này càng củng cố cho phương pháp này, đặc biệt khi góc = (giá trị lớn nhất), giá trị BPR là vô hạn. Hơn nữa tỷ lệ của l có tính chất cục bộ địa phương. 3.2.3 Đề xuất cho phát triển cắt tỉa xƣơng Tác giả Wei Shena đề xuất một ý tưởng cho phát triển xương đệ quy bằng cách thêm điểm để phù hợp với một tiêu chí dựa trên BPR. 3.2.3.1 Tiêu chí để cắt tỉa nhánh xƣơng giả Một tiêu chí được giới thiệu trong [4] được sử dụng để xác định xem nơi các điểm cho trước có là một điểm của xương. Đó là lý do tại sao tác giả gọi chúng là điểm sinh. Tác giả Wei Shena đã xem xét các tiêu chí ở đây trong vùng ảnh: Đối với một điểm p cho trước bên trong đường bao V với n(R (p)) 2, nếu có q1 r(p) và q2 R8 thỏa mãn: (p, q1) - (p, q2) max (abs (x1 – x2), abs (y1 – y2)), (3.12) ___ Sinh viên: Nguyễn Thị Lan – CT1102
  42. 42 Điểm p được coi là một điểm xương, nơi mà (x1 – y1), và (x2 – y2) là tọa độ tương ứng của q1, q2. Dựa trên công thức (3.12) thì thu được xương, nhưng xương thu được chứa quá nhiều nhánh giả, ví dụ các nhánh có màu được thể hiện trong hình 3.5a. Lưu ý rằng các nhánh xương giả được đánh dấu cùng với màu sắc được tạo ra từ các đoạn đường bao không ý nghĩa của màu sắc giống nhau. Độ đo ý nghĩa BPR được đề xuất để giải quyết vấn đề này. Hình 3.5. Xương chân của 1 con lạc đà a) Xương được cắt tỉa dựa trên phương pháp tiếp cận trong. b) Xương được tạo ra bởi tiêu chuẩn 1 có một số điểm cần thiết, như là một phần màu xanh lá cây. c) Xương được cắt tỉa bằng phương pháp làm mảnh được đề xuất. Tiêu chí 1: Điểm p thuộc nhánh xương cắt tỉa nếu có tồn tại q1 r(p) và q2 R8(p) thỏa mãn (3.13) Trong đó t là một ngưỡng cho trước, và và là tọa độ tương ứng của và . Rõ ràng, tiêu chí 1 là một điều kiện cần thiết để xác định một điểm hình là điểm xương hay không, và dựa trên độ đo ý nghĩa được đề xuất, chỉ cần các ___ Sinh viên: Nguyễn Thị Lan – CT1102
  43. 43 cặp của các điểm đường bao kết nối với đoạn đường bao ý nghĩa là được sử dụng để xác định xem các điểm tương ứng là các điểm xương. Vì vậy các nhánh xương giả không được sinh ra bằng việc thay đổi tiêu chuẩn này. 3.2.3.2 Phát triển xƣơng cắt tỉa Dựa trên tiêu chí 1, tác giả Wei Shena cung cấp các ý tưởng cho phát triển cắt tỉa xương kết nối. Đối với một đối tượng 2D, đường biên F được bao bọc bên trong đường bao C biểu diễn vùng của đối tượng, và Sk là xương của đối tượng. Thuật toán phát triển xương cắt tỉa: Procedure SkeletonGrow (Input F, Output Sk) 01. Choosen the point pm F, such that k (pm) is maximum 02. If pm satisfies Criterion 1 03. Add (pm, k (pm)) to Sk and push pm to a stack S 04. End 05. While S not empty 06. p pop (S) 07. For 8 neighbors x of p that satisfy Criterion 1 08. Add (x, k (x)) to Sk, push x to S 09. End 10. End Xương dựa trên ý tưởng được đề xuất được thể hiện trong hình 3.5b, các nhánh xương giả được cắt tỉa. Một phần của xương thu được có thể chứa các điểm dư thừa, như phần màu xanh lá cây trong hình 3.5b. Trong nhiều phương pháp đối sánh hình dạng dựa trên cấu trúc xương, lấy một số điểm mẫu từ xương hoặc phát hiện những điểm đặc trưng (điểm cuối và điểm giao nhau) là cần thiết. Việc lấy các điểm giao thừa từ xương sẽ thuận lợi cho việc phân tích và đối sánh phù hợp thu được hình dạng phù hợp để phân tích. Để ___ Sinh viên: Nguyễn Thị Lan – CT1102
  44. 44 làm điều này bất kỳ các phép toán topo đều có thể được sử dụng để cắt tỉa xương. Tác giả Wei Shena sử dụng phương pháp làm mảnh được đề xuất và kết quả thể hiện trong hình 3.5c. 3.2.3.3 Độ phức tạp của BPR Để tính toán BPR cần các thông số đường biên bởi chiều dài cung, trong đó có độ phức tạp O(m), m là số điểm đường biên. Đối với một điểm p được kiểm tra, xem nó có được thêm vào xương hay không, thì số điểm sinh là n. Kiểm tra điểm p thỏa mãn được tiêu chuẩn 1 có độ phức tạp O(n). Như vậy, tổng thời gian phức tạp của phương pháp tiếp cận là O(nN+m), trong đó N là số lượng điểm ảnh bên trong đường biên. Trên thực tế, trong ứng dụng thực tế, n thường bằng một giá trị nhỏ hơn, thường là 3 hoặc 4, và m là ít hơn nhiều so với N. 3.2.4 Kết luận Trong bài này, tác giả Wei Shena và các cộng sự đã trình bày một độ đo có ý nghĩa mới cho cắt tỉa xương được gọi là tỷ lệ uốn. Dựa trên độ đo ý nghĩa, tác giả đề xuất một thuật toán cho phát triển xương. Thí nghiệm của tác giả trên tập dữ liệu MPEG-7 thu được cho thấy xương không nhạy cảm với nhiễu đường biên, theo nhiều quy mô, trong đó những nhánh xương không đáng kể được cắt tỉa, trong khi nhánh quan trọng vẫn còn. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  45. 45 CHƢƠNG 4: KẾT QUẢ THỰC NGHIỆM 4.1 Môi trƣờng cài đặt Chương trình được cài đặt trên Môi trường Windows 7, sử dụng ngôn ngữ Matlap với máy tính có cấu hình như sau: CPU : i5 – 450M HDD: 320 GB Memory: 2GB Tập dữ liệu được sử dụng trong thử nghiệm là tập dữ liệu thuộc: MPEG-7 4.2 Một số kết quả thử nghiệm 4.2.1 Giao diện chƣơng trình. Hình 4.1. Giao diện chương trình ___ Sinh viên: Nguyễn Thị Lan – CT1102
  46. 46 4.2.2 Một số kết quả tìm xƣơng khác nhau của các phƣơng pháp Hình 4.2. Xương của quả táo thu được bằng các phương pháp a. Phương pháp tìm xương theo trục trung vị. b. Phương pháp tìm xương theo Matlab. c. Phương pháp tìm xương theo DCE với N = 15, N là số đỉnh được lựa chọn bởi DCE d. Phương pháp tìm xương theo BPR với t = 0. 8, t là giá trị ngưỡng được lựa chọn bởi BPR. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  47. 47 Hình 4.3. Xương của con lạc đà thu được bằng các phương pháp a. Phương pháp tìm xương theo trục trung vị. b. Phương pháp tìm xương theo Matlab. c. Phương pháp tìm xương theo DCE với N = 15, N là số đỉnh được lựa chọn bởi DCE d. Phương pháp tìm xương theo BPR với t = 1. 2, t là giá trị ngưỡng được lựa chọn bởi BPR ___ Sinh viên: Nguyễn Thị Lan – CT1102
  48. 48 4.2.3 Hiệu quả của việc sử dụng ngƣỡng t Hiệu quả của các giá trị ngưỡng t khác nhau trên xương của một đối tượng được minh họa trong hình 4.4. Như đã giới thiệu trong mục 3.1, độ đo ý nghĩa được đề xuất, BPR có thể được thực hiện như một trường hợp đặc biệt giữa những mô hình khác nhau. Do đó, nhiều chi tiết xương có thể thu được bằng cách thiết lập ngưỡng t có giá trị khác nhau cho BPR. Khi giá trị ngưỡng t tăng, có ít hơn các nhánh trong xương, mà đại điện ý nghĩa cho các bộ phận của đối tượng, và các bộ phận không quan trọng bị bỏ qua. Đây là những đặc tính phù hợp với nhận thức của con người. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  49. 49 Hình 4.4. Minh họa xương của đối tượng trong việc sử dụng các ngưỡng khác nhau, t là giá trị ngưỡng. ___ Sinh viên: Nguyễn Thị Lan – CT1102
  50. 50 KẾT LUẬN Sau thời gian tìm hiểu, nghiên cứu đề tài “Tìm hiểu phương pháp BPR(Bending Potential Ratio) cho bài toán tìm xương của ảnh” và triển khai thực hiện, em đã đạt được một số kết quả như sau: Về lý thuyết, đồ án của em đã trình bày và hiểu được: Tổng quan về xử lý ảnh số. Môt sốhướng tiếp cận trong tìm xương của ảnh. Tìm hiểu thuật toán cắt tỉa xương của ảnh dựa vào BPR(Bending Potential Ratio) do Wei Shena và các cộng sự đề xuất [4]. Về thực nghiệm, em đã cài đặt thử nghiệm chương trình tìm xương và cắt tỉa xương dựa vào độ đo BBR và so sánh với kết quả tìm xương theo hàm tìm xương của matlab. Tuy nhiên trong quá trình thực hiện, thời gian không có nhiều, năng lực chuyên môn còn nhiều hạn chế, nên đề tài mới chỉ dừng lại ở mức đọc, dịch hiểu và tìm hiểu tóm lược về phương pháp, chưa đánh giá tổng hợp được phương pháp. Nếu có điều kiện, em sẽ tìm đọc tài liệu để nghiên cứu nhằm tổng hợp nhiều phương pháp và đưa ra được những đánh giá kết luận dựa trên những gì đã tìm hiểu được. Trong thời gian tới đề tài sẽ phát triển ở mức cao hơn, ví dụ như có thể tra cứu ảnh dựa trên cấu trúc xương. Em rất mong nhận được sự đóng góp ý kiến của các Thầy Cô và các bạn để em có thêm kiến thức và kinh nghiệm tiếp tục hoàn thiện nội dung nghiên cứu trong đề tài. Em xin chân thành Cám ơn! ___ Sinh viên: Nguyễn Thị Lan – CT1102
  51. 51 TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt [1]. Đỗ Năng Toàn, Phạm Việt Bình (2007), Giáo trình xử lý ảnh, Nhà xuất bản Đại học Thái Nguyên. [2]. Lương Mạnh Bá, Nguyễn Thanh Thủy(2007), Nhập môn xử lý ảnh số, Nhà xuất bản KHKT. [3]. Nguyễn Thị Hoa (2010), Đồ án Tốt Nghiệp, Trường ĐHDL Hải Phòng Tài liệu Tiếng Anh [4]. Wei Shena, Xiang Bai, Rong Hu, Hongyuan Wang, Login Jan Latec ki(2010), Skeleton Growing and Prunning with Bending Potential Ratio, CVPR. [5]. Xiang Baia, Login Jan Latec ki(2007), Skeleton Prunning by Contour Partitionning with Discrete Curve Evolution, CVPR. [6]. H. Blum, in: A Tranformation for Extrating New Description of Shape, Models for the Perception of Speech and Visual Form, MIT Press, 1967pp, 363-380. ___ Sinh viên: Nguyễn Thị Lan – CT1102