Tài liệu ứng dụng phương pháp phát hiện biên trong nhận dạng các đối tượng hình học

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THANH HUY ỨNG DỤNG PHƯƠNG PHÁP PHÁT HIỆN BIÊN TRONG NHẬN DẠNG CÁC ĐỐI TƯỢNG HÌNH HỌC Chuyên ngành: Khoa học máy tính Mã số: 8480101 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng, Năm 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA Người hướng dẫn khoa học: TS. TRƯƠNG NGỌC CHÂU Phản biện 1: PGS.TS. NGUYỄN THANH BÌNH Phản biện 2: TS. HOÀNG VĂN DŨNG Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ kỹ thuật chuyên ngành Khoa học máy tính họp tại Trường Đại học Bách khoa Đà Nẵng vào ngày 5 tháng 01 năm 2019 Có thể tìm hiểu luận văn tại: - Trung tâm Học liệu và Truyền t hông Trường Đại học Bách khoa Đại học Đà Nẵng - Thư viện Khoa Công nghệ thông tin, Trường Đại học Bách khoa – Đại học Đà Nẵng 1 MỞ ĐẦU 1. Lý do chọn đề tài Thông tin giúp làm tăng hiểu biết của con người, là nguồn gốc của nhận thức và là cơ sở của quyết định. Hình ảnh là một nguồn cung cấp thông tin tương đối phong phú và trực quan so với những nguồn thông tin khác. Do đó, việc xử lý, nhận dạng hình ảnh sao cho thông tin thu được rõ ràng và chính xác nhất là một yêu cầu xuất phát thực tiễn. Sự phát triển nhanh chóng mạnh mẽ về công nghệ chế tạo, công nghệ phần cứng đã tạo ra các sản phẩm với nhiều tí nh năng ưu việt, chất lượng cao. Trong đó phải kể đến sự phát triển của các thiết bị thu nhận hình ảnh thực như máy ảnh, camera, máy scan,…tuy nhiên thách thức chính cho công nghệ phần mềm trong lĩnh vực này là việc tiền xử lý và xử lý nhận dạng các hình ảnh số thu được từ các hệ thống đó. Các thuật toán xử lý ảnh mà cụ thể là phát hiện xử lý biên của sự vật mà hình ảnh thu được là tiền đề căn bản để nhận dạng đối tượng một cách chính xác nhất, đặc biệt là các đối tượng hình học. Qua đó, giúp cho chúng ta có cái nhìn tổng quan hơn về xử lý ảnh, về các phương pháp phát hiện biên đối tượng trong ảnh và từ đó đưa ra được phương án nhận dạng tối ưu trong từng trường hợp cụ thể. Đề tài sẽ đưa ra ứng dụng cụ thể trong việc ứng dụng các thuật toán phát hiện biên vào bài toán nhận dạng các đối tượng hình học nhằm mình chứng cho quá trình lựa chọn giải thuật hợp lý khi xử lý các yêu cầu về nhận dạng và xử lý ảnh trong thực tế. 2. Mục tiêu nghiên cứu - Nghiên cứu các phương pháp phát hiện biên trong xử lý ảnh số - Nghiên cứu một số phương pháp nhận dạng đối tượng 2 - Đề xuất các giải thuật ứng dụng phương pháp phát hiện biên để nhận dạng các đối tượng hình học. 3. Đối tượng và phạm vi nghiên cứu a. Đối tượng nghiên cứu - Các phương pháp phát hiện biên. - Các phương pháp nhận dạng b. Phạm vi nghiên cứu Nhận dạng các đối tượng hình học: hình tròn, hình vuông, hình chữ nhật, hình thoi, hình elip và hình tam giác. 4. Phương pháp nghiên cứu Nghiên cứu, tìm hiểu các giải thuật nhằm phát hiện biên các đối tượng trong ảnh số. Sau đó kết hợp sử dụng các phương pháp nhận dạng để phát triển thuật toán nhận dạng các đối tượng hình học. Các phương pháp sẽ thực hiện để đạt được mục tiêu nghiên cứu: a. Phương pháp thu thập thông tin: - Thu thập các tài liệu tổng quan về xử lý ảnh. - Thu thập tài liệu, bài báo về các phương pháp phát hiện biên trong xử lý ảnh số. - Thu thập tài liệu, thông tin về các giải thuật nhận dạng. - Tìm kiếm các tài liệu trong và ngoài nước, các bài báo và công trình nghiên cứu liên quan đến các giải thuật nhận dạng các đối tượng hình học. b. Phương pháp so sánh - Tổng hợp và đối chiếu giữa những tài liệu thu được để đưa ra một cái nhìn tổng quan nhất giữa các phương pháp cũng như ưu nhược điểm của nó. c. Phương pháp phân tích 3 - Phân tích thuật toán, cách thức hoạt động cũng như đặc trưng của mỗi thuật toán. - Phân tích những hiệu quả áp dụng của các thuật toán đối với các ứng dụng cụ thể nhằm đạt đưa kết quả tốt nhất. d. Phương pháp chuyên gia - Tham vấn từ các chuyên gia trong lĩnh vực này nhằm hoàn thiện các nội dung cần nghiên cứu. e. Phương pháp thực nghiệm - Xây dựng giải thuật xử lý nâng cao chất lượng ảnh trong trường hợp ứng dụng cụ thể bằng các phương pháp đã được nghiên cứu, từ đó rút ra những kết luận cho việc nghiên cứu. 5. Bố cục của luận văn Mở đầu Chương 1: Cơ sở lý thuyết Chương 2: Xây dựng mô hình nhận dạng đối tượng hình học Chương 3: Triển khai thực nghiệm Cuối cùng là phần Kết luận và hướng phát triển. CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1. 1 TỔNG QUAN VỀ XỬ LÝ ẢNH SỐ 1.1.1 Giới thiệu về xử lý ảnh Cùng với ngôn ngữ tự nhiên, hình ảnh đã đóng một vai trò hết sức quan trọng trong việc trao đổi thông tin. Tính trực quan của hình ảnh đã giúp cho con người hiểu rõ và sâu sắc hơn các thông tin cần thu thập. Người ta đã chứng minh được rằng, trong tất cả các kênh thu nhận thông tin của con người thì lượng thông tin thu nhận qua kênh thị giác chiếm khoảng 70%. Hình ảnh là kết quả của việc thu 4 nhận và biểu diễn của năng lượng ánh sáng trải dài từ tia gamma (có bước sóng nhỏ) đến sóng radio (có bước sóng lớn). Tuy nhiên, mắt người chỉ cảm nhận được một vùng giới hạn rất nhỏ trong phổ điện từ. Ngược lại, máy tính có thể đọc được một vùng rất rộng trong phổ điện từ, từ tia gamma đến sóng radio. Nó có thể biểu diễn và xử lý những bức ảnh được sinh ra bởi những nguồn mà con người không thể nhận biết được, như ảnh siêu âm, ảnh hồng ngoại, ảnh trong vùng tia X, …. Do đó xử lý ảnh có một phạm vi ứng dụng tương đối rộng lớn. 1.1.2. Các bước cơ bản trong xử lý ảnh Thu nhận ảnh: ảnh có thể được thu nhận trong thế giới thực qua máy chụp hình, từ tranh ảnh thông qua máy quét hoặc từ vệ tinh qua các bộ cảm biến bằng tín hiệu số hoặc tín hiệu tương tự. Số hoá ảnh: Tất cả các thông tin được lưu trong máy tính đều ở dạng số. Vì vậy, ảnh sau khi thu nhận được từ các thiết bị khác cần phải được số hoá để lưu trữ hoặc có thể dùng để xử lý tiếp. Phân tích ảnh: Phân tích ảnh là một quá trình gồm nhiều giai đoạn nhỏ hơn: tăng cường ảnh để nâng cao chất lượng ảnh và khắc phục những thiếu sót trong quá trình thu nhận ảnh và số hoá ảnh như nhiễu, méo... làm nổi bật các đặc trưng chính của ảnh đảm bảo cho ảnh gần giống với hình ảnh thật nhất. Phát hiện và trích chọn các đặc trưng: như biên, màu, kết cấu,.... Sau quá trình này ảnh được lưu trữ hoặc sử dụng cho việc nhận dạng hoặc cho hệ hỗ trợ quyết định. Đối sánh, nhận dạng ảnh: Là quá trình đối sánh, phân lớp ảnh phục vụ cho các mục đích khác nhau. 5 Phát hiện và trích chọn đặc trưng Lưu trữ Camera Thu nhận Số hóa Đối sánh, nhận dạng Phân tích ảnh Sensor Lưu trữ Hệ quyết định Tổng quan các giai đoạn cơ bản trong xử lý ảnh 1.2. LÝ THUYẾT NHẬN DẠNG 1.2.1. Tổng quan về lý thuyết nhận dạng Nhận dạng đối tượng (Pattern Recognition) có thể định nghĩa như là một quá trình phân loại các đối tượng được biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp dựa theo những quy luật và những mẫu chuẩn, hoặc cũng có thể định nghĩa đó là phương tiện để xây dựng một hệ thống tin học có khả năng "Cảm nhận - nhận thức - nhận biết" các đối tượng vật lý gần giống khả năng của con người. Nhận dạng có gắn với ba khả năng trên là lĩnh vực hết sức rộng lớn có liên quan đến việc xử lý tín hiệu đầu vào trong không gian nhiều chiều, mô hình hoá bài toán, lý thuyết xử lý ảnh, cơ sở dữ liệu, phương pháp ra quyết định... Một hệ thống nhận dạng hoàn chỉnh phải có khả năng thể hiện được quá trình nhận thức của người qua các mức: + Mức cảm nhận + Mức nhận thức + Mức nhận biết 1.2.2 Các phương pháp nhận dạng Các phương pháp nhận dạng mẫu đã được nghiên cứu và áp dụng rộng rãi vào các hệ nhận dạng đối tượng hình học trong các thập 6 kỷ qua có thể tích hợp theo các hướng tiếp cận sau: Trích rút đặc trưng, đối sánh mẫu, thống kê, cấu trúc, mô hình Markov ẩn, mạng nơ ron và SVM. 1.2.2.1 Phương pháp trích rút đặc trưng Phương pháp trích rút đặc trưng là một trong những phương pháp cổ điển của nhận dạng. Phương pháp này được thể hiện rõ nét trong nhận dạng các đối tượng hình học. Thuật toán nhận dạng được thực hiện thông qua 2 bước chính: Bước 1: Trích chọn các đặc tính từ các mẫu hình học đầu vào. Bởi vì chúng ta chủ yếu quan tâm tới việc nhận dạng các mẫu hình học, hệ thống nhận dạng cũng dựa chủ yếu trên các thông tin về mặt hình học. Bước 2: Sử dụng logic mờ hoặc ước lượng toán học: Để vượt qua giới hạn về sự không rõ ràng giữa các hình, phương pháp sử dụng logic mờ để kết hợp một độ đo nào đó trong việc nhận dạng các hình. 1.2.2.2 Đối sánh mẫu Kỹ thuật nhận dạng đối tượng hình học đơn giản nhất dựa trên cơ sở đối sánh các nguyên mẫu (prototype) để nhận dạng hình. Nói chung, toán tử đối sánh xác định mức độ giống nhau giữa hai vectơ (nhóm các điểm, hình dạng, độ cong...) trong một không gian đặc trưng. Các kỹ thuật đối sánh có thể nghiên cứu theo ba hướng sau: + Đối sánh trực tiếp + Đối sánh mềm các mẫu biến dạng (Deformable Templates and Elastic Matching) + Đối sánh giảm nhẹ (Relaxation Matching) 1.2.2.3 Phương pháp tiếp cận cấu trúc 1.2.2.4 Các phương pháp thống kê 1.2.2.5 Các phương pháp học máy tiên tiến 7 a. Mô hình Markov ẩn b. Mạng nơ ron c. Máy vectơ tựa 1.2.2.6 Kết hợp các phương pháp nhận dạng Các phương pháp phân lớp đã được đề cập ở trên đều có thể áp dụng đối với các hệ nhận dạng đối tượng hình học. Mỗi kỹ thuật phân lớp đều có những ưu điểm và nhược điểm riêng. Vấn đề đặt ra là các phương pháp trên có thể kết hợp với nhau theo một cách nào đó để nâng cao hiệu quả nhận dạng hay không? Nhiều công trình nghiên cứu các kiến trúc phân lớp theo ý tưởng kết hợp các kỹ thuật phân lớp đã nêu trên. Các hướng tiếp cận kiến trúc kết hợp các phương pháp để phân lớp có thể chia thành ba nhóm sau: Kiến trúc tuần tự, kiến trúc song song và kiến trúc lai ghép. 1.3 CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN CỔ ĐIỂN 1.3.1 Phân loại các kỹ thuật phát hiện biên Phương pháp phát hiện biên trực tiếp Phương pháp phát hiện biên này nhằm làm nổi biên dựa vào sự biến thiên về giá trị độ sáng của điểm ảnh. Kỹ thuật chủ yếu dùng phát hiện biên ở đây là kỹ thuật đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient. Phương pháp này bao gồm kỹ thuật Gradient và kỹ thuật la bàn. Nếu lấy đạo hàm bậc hai của ảnh ta có phương pháp Laplace. Phương pháp phát hiện biên gián tiếp Là quá trình phân vùng dựa vào phép xử lý kết cấu đối tượng, cụ thể là dựa vào sự biến thiên nhỏ và đồng đều độ sáng của các điểm ảnh thuộc một đối tượng. Nếu các vùng của ảnh được xác định thì đường phân ranh giữa các vùng đó chính là biên ảnh cần tìm. Việc phát hiện biên và phân vùng đối tượng là hai bài toán đối ngẫu. Từ 8 phát hiện biên ta có thể tiến hành phân lớp đối tượng, như vậy là đã phân vùng được ảnh. Và ngược lại, khi đã phân vùng được ảnh nghĩa là đã phân lập được thành các đối tượng, từ đó có thể phát hiện được biên cần tìm. Quy trình phát hiện biên Bước 1: Do ảnh ghi được thường có nhiễu, bước đầu tiên của quá trình này là giảm nhiễu của ảnh cần xử lý. Bước 2: Làm nổi biên sử dụng các toán tử phát hiện biên. Bước 3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả. Bước 4: Liên kết và trích chọn biên. 1.3.2 Kỹ thuật phát hiện biên trực tiếp 1.3.2.1 Kỹ thuật phát hiện biên Gradient Kỹ thuật Gradient là kỹ thuật dò biên cục bộ dựa vào cực đại của đạo hàm. Đây là phép toán lấy đạo hàm bậc nhất trong không gian hai chiều. Theo định nghĩa Gradient là một véctơ có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh, ta có: f ( x, y ) f ( x) = f(x) f ( x dx , y ) dx f ( x, y ) f ( x, y ) f ( y) = f(y) f ( x, y dx) dy f ( x, y ) Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng (thực tế chọn dx= dy=1). Đây là phương pháp dựa theo đạo hàm riêng bậc nhất theo hướng x, y. 9 1.3.2.2 Pixel difference 1.3.2.3 Separated Pixel Difference 1.3.2.4 Toán tử Robert 1.3.2.5 Toán tử Prewitt Toán tử được Prewitt đưa ra vào năm 1970 có dạng: Hx= -1 0 1 -2 0 2 1 0 1 Hy = -1 -2 1 0 0 0 1 2 1 1.3.2.6 Toán tử (mặt nạ) Sobel Toán tử Sobel được Duda và Hart đặt ra năm 1973 với các mặt nạ tương tự như của Robert nhưng khác cấu hình: Hx = -1 0 1 -1 0 1 -1 0 1 Hy = -1 -1 -1 0 0 0 1 1 1 1.3.2.7 Toán tử Frie-Chen 1.3.2.8 Toán tử Boxcar 1.3.2.9 Toán tử Truncated Pyramid 1.3.3 Các toán tử la bàn Trong phương pháp Gradient, người ta chia nhỏ thành hai kỹ thuật (do dùng hai toán tử khác nhau). Đó là kỹ thuật Gradient và kỹ thuật la bàn. Kỹ thuật Gradient dùng toán tử Gradient lấy đạo hàm theo một hướng. 10 Kỹ thuật la bàn dùng toán tử la bàn lấy đạo hàm theo tám hướng: Bắc, Nam, Đông, Tây, Đông bắc, Tây bắc, Đông nam, Tây nam. Toán tử la bàn do Gradient dựa trên sự đánh giá tất cả các hướng có thể của một đường biên ảnh trong một ảnh rời rạc. Bởi vậy thay vì chỉ áp dụng hai mặt nạ như các toán tử trong kỹ thuật Gradient ở trên, tám mặt nạ đã được dùng, mỗi cái cung cấp một cạnh đường biên dọc theo một trong tám hướng có thể của vòng. Như vậy, mỗi điểm ảnh đầu ra là giá trị lớn nhất trong tám kết quả nhân xoắn của mặt nạ với ma trận ảnh. Sau mỗi lần nhân xoắn, ta quay mặt nạ này đi một góc 450 ngược chiều kim đồng hồ : 00, 450, 900, 1350, 1800, 2250, 2700, 3150. 1.3.3.1 Toán tử la bàn Kirsh 1.3.3.2 Toán tử la bàn Prewitt 1.3.3.3 Robinson 3 - Level 1.3.3.4 Robinson 5 – Level 1.3.4 Kỹ thuật phát hiện biên Laplace Để khắc phục hạn chế và nhược điểm của phương pháp Gradient, trong đó sử dụng đạo hàm riêng bậc nhất người ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai hay toán tử Laplace. Phương pháp dò biên theo toán tử Laplace hiệu quả hơn phương pháp toán tử Gradient trong trường hợp mức xám biến đổi chậm, miền chuyển đổi mức xám có độ trải rộng. Toán tử Laplace được xác định như sau: 2 2 f= x f 2 + 2 f y 2 11 Toán tử Laplace dùng một số kiểu mặt nạ khác nhau nhằm tính gần đúng đạo hàm riêng bậc hai. Các dạng mặt nạ theo toán tử Laplace bậc 3x3 có thể: 2 f x 2 = 2f(x,y) – f(x-1,y) – f(x+1,y) 2 f y 2 2 f= = 2f(x,y) – f(x,y-1) – f(x, y+1) 2 x f 2 + 2 f y 2 = 4f(x,y) – f(x-1,y) – f(x, y-1) – f(x+1,y) – f(x,y+1) Từ đó ta đưa ra được mặt nạ nhân chập của phương pháp đạo hàm bậc hai. Kết quả này cho ra mặt nạ thứ ba gọi là phương pháp Four - neighbor Laplace (sử dụng bốn láng giềng). Toán tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai. Dưới đây là ba kiểu mặt nạ hay dùng: H1 = 0 -1 0 -1 -1 -1 -1 4 -1 -1 -8 -1 0 -1 0 H2 -1= -1 -1 H3 = 1 -2 1 -2 4 -2 1 -2 1 1.4 CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG CAO 1.4.1 Phương pháp Canny Phương pháp này do John Canny ở phòng thí nghiệm MIT khởi xướng vào năm 1986. Canny đã đưa một tập hợp các ràng buộc mà một phương pháp phát hiện biên phải đạt được. Ông đã trình bày một phương pháp tối ưu nhất để thực hiện được các ràng buộc đó. Và phương pháp này được gọi là phương pháp Canny. 12 Cơ sở lý thuyết thuật toán Ý tưởng thuật toán: Ý tưởng của phương pháp này là định vị đúng vị trí bằng cách cực tiểu hoá phương sai 2 của vị trí các điểm cắt "Zero" hoặc hạn chế số điểm cực trị cục bộ để chỉ tạo ra một đường bao. Các ràng buộc mà phương pháp phát hiện biên Canny đã thực hiện được đó là: mức lỗi, định vị và hiệu suất. Trong đó: Mức lỗi: có ý nghĩa là một phương pháp phát hiện biên chỉ và phải tìm tất cả các biên, không biên nào được tìm bị lỗi. Định vị: Điều này nói đến độ chênh lệch cấp xám giữa các điểm trên cùng một biên phải càng nhỏ càng tốt. Hiệu suất: là làm sao cho khi tách biên không được nhận ra nhiều biên trong khi chỉ có một biên tồn tại. 1.4.2. Phương pháp Shen - Castan Shen và Castan có cùng quan điểm với Canny về một mẫu chung trong việc tách các đường biên. Đó là: nhân xoắn ảnh với một mặt nạ làm mịn, sau đó tìm ra điểm biên. Tuy nhiên trong những phân tích của họ lại tạo ra một hàm khác để tối ưu, đó là việc đề xuất cực tiểu hoá hàm sau trong không gian một chiều. 1.4.3 Phát hiện biên dựa vào Wavelet Phương pháp này sử dụng biến đổi Wavelet rời rạc (DWT) để phân tích ảnh thành nhiều ảnh có đặc điểm và xấp xỉ. Xấp xỉ giống như ảnh gốc, theo tỷ lệ ¼. 1.5. KẾT CHƯƠNG Các nội dung được trình bày ở trên tập trung vào lý thuyết tổng quan về xử lý ảnh, nhận dạng đối tượng và đặc biệt là các phương pháp nhận dạng phổ biến hiện nay và tập trung vào nghiên cứu chi tiết các phương pháp phát hiện biên cơ bản nhất. Mỗi phương pháp đều có 13 các ưu nhược điểm khác nhau phù hợp với các trường hợp cụ thể của đối tượng. Có hai nhóm phương pháp cơ bản, phương pháp phát hiện biên trực tiếp tập trung vào các đối tượng nhận dạng đơn giản, không hoặc ít nhiễu vì vậy việc cài đặt thuật toán và tốc độ xử lý thuật toán tương đối dễ dàng và nhanh chóng. Phương pháp phát hiện biên gián tiếp sử dụng các giải thuật phức tạp hơn, đòi hỏi thời gian xử lý nhiều hơn, được sử dụng để phát hiện biên các đối tượng phức tạp, mức độ nhiễu lớn, không đều. Các nghiên cứu trên cũng đã chỉ ra lịch sử quá trình nghiên cứu về nhận dạng đã phát triển nhiều phương pháp nhận dạng khác nhau, mỗi phương pháp có những ưu, nhược điểm và phù hợp với một đối tượng hoặc nhóm đối tượng nhất định (chữ viết, hình học, sinh trắc học,...). Đối với các phương pháp nhận dạng bằng trích chọn đặc trưng, bằng tập mờ hay phương pháp đối sánh: các phương pháp này cơ bản sử dụng các đặc trưng riêng có của đối tượng, kết quả nhận dạng tương đối tốt, tốc độ trong xử lý nhận dạng cao và sử dụng các thuật toán nhận dạng không phức tạp. Các phương pháp nhận dạng học máy là các phương pháp được nghiên cứu và phát triển về sau, được nhiều nhà khoa học tập trung nghiên cứu. Các phương pháp này thường được sử dụng nhận dạng các đối tượng phức tạp, đòi hỏi quá trình xử lý nhận dạng mất nhiều thời gian do phải trải qua quá trình học (huấn luyện), tốc độ xử lý chậm hơn và thuật toán nhận dạng bao gồm nhiều bước khác nhau, nhiều tham số, phức tạp hơn. Tuy nhiên, kết quả nhận dạng của các phương pháp này thường đưa đến hiệu quả cao hơn. Đối với bài toán cụ thể của với việc nhận dạng các đối tượng hình học, là các đối tượng cố định, có khả năng định nghĩa được các 14 đặc trưng và khả năng biến thiên về hình dạng, kích thước không ảnh hưởng nhiều đến kết quả nhận dạng. Hơn nữa, một trong những mục đích của luận văn là nhằm làm rõ vài trò của các phương pháp phát hiện biên trong nhận dạng, vì vậy ta sẽ lựa chọn phương pháp Trích rút đặc trưng nhằm giảm độ phức tạp của thuật toán, tăng tính hiệu quả và tăng tốc độ xử lý trong quá trình nhận dạng. Quá trình nghiên cứu các phương pháp phát hiện biên áp dụng vào thực tế ta nhận thấy, hình học là các đối tượng nhận dạng khá đơn giản, không phức tạp, bài toán được đưa ra ở mức độ khá lý tưởng với mức độ nhiễu ít (hoặc không có) vì vậy ta chỉ lựa chọn áp dụng phương pháp sử dụng đạo hàm bậc nhất (Sobel, Prewitt,...) để ứng dụng tìm biên của đối tượng hình học. CHƯƠNG 2: XÂY DỰNG MÔ HÌNH NHẬN DẠNG ĐỐI TƯỢNG HÌNH HỌC 2.1 BÀI TOÁN NHẬN DẠNG ĐỐI TƯỢNG HÌNH HỌC Đầu vào: Cho một hình ảnh chứa các đối tượng hình học (một đối tượng hoặc nhiều đối tượng), gồm các loại hình học đặc trưng nhất: hình vuông, hình chữ nhật, hình tròn, hình elip, hình tam giác, hình thoi. Ảnh đầu vào là ảnh không nhiễu (hoặc ít nhiễu), ít cạnh. Đầu ra: Yêu cầu của bài toán là xác định chính xác loại đối tượng hình học (hình vuông, hình chữ nhật, hình tròn, hình elip, hình tam giác, hình thoi). Ghi rõ tên loại hình học ở vị trí bên trái tâm của hình. Giải thuật được cài đặt và mô phỏng trực quan trên công cụ lập trình Matlab với hình ảnh đầu vào là các ảnh có phần mở rộng .tmp, jpg, jpge. 15 Ảnh đầu vào: Ảnh đầu vào chứa các đối tượng hình họ Ảnh đầu ra: Ảnh đầu ra nhận dạng các đối tượng hình học 2.2 XÂY DỰNG MÔ HÌNH NHẬN DẠNG 2.2.1 So sánh phương pháp phát hiện biên Để so sánh sự khác nhau giữa các phương pháp phát hiện biên, chúng ta sử dụng kết quả của phương pháp phát Sobel đại diện cho phương pháp đạo hàm bậc nhất, sử dụng kết quả của Eight-neighbor Laplace đại diện cho phương pháp phát hiện biên Laplace (phương pháp đạo hàm bậc hai) và sử dụng σ =1,4; T h =100, T 1 =50 đại diện cho phương pháp Canny (phương pháp gián tiếp). Từ các kết quả 16 nghiên cứu ở Chương 2, ta có một số nhận định về các phương pháp phát hiện biên như sau: a. Đối với ảnh không nhiễu Các phương pháp đều cho kết quả tốt. Song phương pháp phát hiện biên Sobel cho biên rõ nét nhưng lớn, còn phương pháp Laplace cho kết quả rõ nét, biên mảnh. Riêng phương pháp Canny do quá trình làm trơn ảnh nên từ một ảnh không nhiễu, các biên mờ bớt đi và to ra. Do vậy biên ảnh trong phương pháp Canny lớn nhưng lại không đầy đủ. Đối với loại ảnh này khi tìm biên nên áp dụng phương pháp Laplace, tiếp đến là phương pháp đạo hàm bậc nhất (Sobel, Kirsh, Prewitt...). Ngoài ra, do giải thuật phức tạp hơn, nên tốc độ xử lý sẽ chậm, vì vậy không nên sử dụng phương pháp Canny trong trường hợp này. b. Đối với ảnh có nhiều cạnh Khi phát hiện biên, các cạnh không quan trọng nên được loại bỏ. Ở đây, phương pháp Sobel vẫn phát hiện được biên nhưng các biên mờ, không được rõ nét, do trong ảnh có những vùng có mức xám thấp, sự thay đổi giữa các mức xám nhỏ. Chính vì vậy mà ảnh qua phương pháp Laplace cho kết quả rõ nét hơn (do phương pháp này sử dụng phương pháp đạo hàm bậc hai, các điểm biên là các điểm cắt không). Tuy vậy do ảnh có rất nhiều điểm biên nhỏ nên các biên ảnh ở trên qua phương pháp này rất nhiều và rối, chúng ta nên loại bỏ các điểm biên thừa. Còn đối với phương pháp Canny, do quá trình “Non-maximum Suppression” và do quá trình áp dụng ngưỡng mà các điểm biên phụ bị loại bớt đi, các biên chính được giữ lại nên biên rõ nét hơn. Đối với ảnh có nhiều có mức xám nhỏ, sự biến thiên các mức xám là thấp ta nên sử dụng phương pháp Laplace, song nếu ảnh đó có 17 quá nhiều biên thì ta nên sử dụng phương pháp Canny để loại bỏ bớt các cạnh không cần quan tâm. c. Đối với ảnh có nhiều nhiễu Phương pháp đạo hàm bậc nhất cho biên ảnh với nhiều điểm biên phụ. Còn phương pháp Laplace thì tạo biên kép nên hoàn toàn không xác định được biên. Còn đối với phương pháp Canny thì do quá trình làm trơn ảnh cho bớt nhiễu và quá trình “Non-maximum Suppression” để giảm bớt các biên phụ nên ảnh kết quả của phương pháp này rất rõ nét. Vì vậy đối với ảnh có nhiều nhiễu thì ta nên sử dụng phương pháp Canny để loại bỏ nhiễu và các điểm biên phụ không cần quan tâm, chỉ giữ lại các điểm biên chính theo mục đích sử dụng khác nhau. 2.2.2 Lựa chọn phương pháp Qua quá trình nghiên cứu trên ta thấy rằng, mỗi đối tượng và ngữ cảnh khác nhau của hình ảnh ta có thể sử dụng nhiều phương pháp và giải thuật để giải quyết bài toán đó, tuy nhiên thông thường chỉ áp dụng một phương pháp và giải thuật được đánh giá là phù hợp và tối ưu nhất. Đối với các ảnh không nhiễu (hoặc ít nhiễu), ít cạnh: Sử dụng phương pháp đạo hàm bậc nhất Sobel. Đối với các ảnh bị nhiễu, nhiều cạnh (cạnh yếu): Sử dụng phương pháp Canny. Trong trường hợp cụ thể của luận văn, ta sẽ lựa chọn phương pháp đạo hàm bậc nhất Sobel để tiến hành cài đặt giải thuật phục vụ phát hiện biên của đối tượng. 18 2.3 LỰA CHỌN GIẢI THUẬT NHẬN DẠNG Từ kết quả nghiên cứu của Chương 1, áp dụng bài toán thực tế của luận văn ta thấy rằng phương pháp trích rút đặc trưng là sự lựa chọn tối ưu trong trường trường hợp ngữ cảnh của bài toán đầu vào. Đối với phương pháp này ta sẽ tiến hành trích rút các đặc trưng cơ bản của từng loại hình học trên cơ sở đã xác định được các thông số biên, tiến hành áp dụng các ước lượng toán học để đưa ra kết luận. Dựa trên các cơ sở toán học, ta nhận thấy rằng có 02 phương pháp để nhận dạng đối tượng hình học thông qua trích rút đặc trưng: Trích diện tích đóng của hình và Trích diện tích của hình chữ nhật đóng. 2.3.1 Phương pháp trích diện tích đóng của hình Sau khi đọc ảnh, ta tiến hành chuyển ảnh sang chế độ đen trắng. Áp dụng phương pháp Sobel để xác định đường biên của các hình. Ta tính được diện tích của các hình sau khi chuyển ảnh sang ma trận dạng nhãn L (0,1), lúc này ta có được diện tích thứ nhất: Area1 = regionprops(L, 'area'). Ta tiếp tục tìm tập các tọa độ đường biên của mỗi hình, tìm tọa độ tâm của mỗi hình (Sn), sau đó tìm các giá trị min, max khoảng cách từ tâm mỗi hình đến tập các tọa độ biên của mỗi hình. Từ giá trị min (k2) và max (k1), áp dụng vào từng loại hình cụ thể ta có thể tính được diện tích thứ hai (Area2). + Tron = pi*k2 2 (Diện tích hình tròn) + Vuong = 4*k2 2 ; (Diện tích hình vuông) + Chunhat = 4*k2* (k 1 2 2 k2 ) + Tamgiacdeu= 3 /((k1+k2) 2 ; + Elip =k1*k2*pi; + Thoi = 2*k1*k2; (Diện tích hình chữ nhật) (Diện tích hình tam giác đều) (Diện tích hình Elip) (Diện tích hình thoi)