Tài liệu Nhận dạng cử chỉ của bàn tay để điều khiển robot

MỤC LỤC PHẦN MỞ ĐẦU ........................................................................................................1 1. Tính cấp thiết của đề tài ....................................................................................... 1 2. Ý nghĩa khoa học và thực tiễn [1] .......................................................................1 3. Lịch sử nghiên cứu ............................................................................................... 1 3.1 Trên thế giới [3] ............................................................................................... 1 3.2 Trong nƣớc......................................................................................................3 4. Mục tiêu nghiên cứu............................................................................................. 3 5. Đối tƣợng và phạm vi nghiên cứu.......................................................................4 6. Sơ lƣợc về nội dung luận văn ...............................................................................4 7. Giới hạn đề tài .......................................................................................................4 CHƢƠNG 1. GIỚI THIỆU TỔNG QUAN............................................................. 6 1.1 Giới thiệu về thiết bị Camera Kinect ........................................................... 6 1.2 Các giai đoạn xử lý ảnh ...............................................................................11 1.3 Giới thiệu về SVM (Support Vector Machine) ..........................................12 1.4 Các công thức liên quan ..............................................................................13 1.5 Giới thiệu về mô-men bất biến ....................................................................17 1.6 Giới thiệu các phép toán hình thái học ...................................................... 17 1.7 Kết luận .........................................................................................................18 CHƢƠNG 2. NỘI DUNG NGHIÊN CỨU ............................................................ 19 2.1 Phát hiện làn da thông qua màu sắc [2] ..................................................... 19 2.2 Thuật toán SVM ........................................................................................... 20 2.2.1 Huấn luyện SVM ...................................................................................21 2.2.2 Các ƣu thế của SVM trong phân lớp bàn tay [5] ............................... 22 2.3 Phát hiện làn da ............................................................................................. 22 2.4 Mục tiêu ứng dụng của hình thái học .......................................................... 24 2.5 Các phép toán hình thái học [7] ...................................................................25 2.6 Các thao tác với hình thái học nhị phân [9] ................................................26 2.6.1 Phép Dilation (dãn nhị phân) [8] ......................................................... 27 2.6.2 Phép Erosion (bào mòn ảnh) [8] .......................................................... 29 2.6.3 Phép Opening và Closing (đóng và mở ảnh) [8] ..................................31 2.6.4 Thuật toán tách các thành phần liên thông ........................................32 2.6.5 Mô men bất biến [6] ...............................................................................34 2.7 Kết luận .........................................................................................................39 CHƢƠNG 3. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ .............................. 41 3.1 Quá trình thử nghiệm .................................................................................41 3.2 Kết quả thử nghiệm .................................................................................... 41 3.3 Đánh giá .........................................................................................................44 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................................. 45 PHỤ LỤC .................................................................................................................46 TÀI LIỆU THAM KHẢO........................................................................................ 46 DANH MỤC CÁC HÌNH VẼ Hình 1.1 : Camera Kinect của hàng Microsoft. ........................................................ 6 Hình 1.2: Nhận diện hành động game thủ và điều khiển nhân vật trong game. ......7 Hình 1.3: Những thành phần chính của Kinect ........................................................ 7 Hình 1.4: Chiếc xe có khả năng giúp nhận biết các món hàng bạn mua. ................9 Hình 1.5: Chiếc xe thử nghiệm tại hệ thống siêu thị Whole Foods ........................ 10 Hình 1.6: Điều khiển máy tính bằng Kinect............................................................ 11 Hình 1.7: Điều khiển máy tính bằng cử chỉ. ........................................................... 11 Hình 1.8: Các giai đoạn xử lý ảnh. .........................................................................12 Hình 1.9: Quan hệ láng giềng. ................................................................................14 Hình 1.10: Quan hệ lân cận. ................................................................................... 14 Hình 1.11: Khoảng cách City-Block. ......................................................................15 Hình 1.12: Khoảng cách ChessBoard.....................................................................15 Hình 2.1: Phần tử cấu trúc được chuyển đổi thành mảng vuông. .......................... 24 Hình 2.2: Kết quả được xử lý bởi phần tử cấu trúc. ...............................................25 Hình 2.3: Phép phản xạ và tịnh tiến của B. ............................................................ 26 Hình 2.4: Phép Dilation. ......................................................................................... 27 Hình 2.5: Ví dụ phép Dilation (dãn nhị phân) ........................................................ 28 Hình 2.6: Bàn tay xòe khi sử dụng Dilation............................................................ 28 Hình 2.7: Các bàn tay sau khi phân ngưỡng bị nhiễu. ...........................................29 Hình 2.8: Các bàn tay sau khi sử dụng Erosion ..................................................... 30 Hình 2.9: Phép Opening ......................................................................................... 31 Hình 2.10: Phép Closing ......................................................................................... 32 Hình 2.11: Bàn tay xòe khi sử dụng Opening và Closing. ......................................32 Hình 2.12: Tách thành phần liên thông. .................................................................33 Hình 2.13: Bằng cách sử dụng các thành phần liên thông để phát hiện các đối tượng khác trong thực phẩm đóng gói. ...................................................................34 Hình 2.14: Các biến đổi hình dáng đối tượng. ....................................................... 35 Hình 2.15: Ví dụ mô men bất biến. .........................................................................36 Hình 2.16: Quá trình truyền tín hiệu xuống Robot ................................................38 Hình 2.17: Lưu đồ xử lý ảnh ................................................................................... 39 Hình 3.1: Robot nhận tín hiệu mở kết nối. .............................................................. 41 Hình 3.2: Robot nhận tín hiệu qua phải..................................................................41 Hình 3.3: Robot nhận tín hiệu tiến. .........................................................................42 Hình 3.4: Robot nhận tín hiệu lùi............................................................................42 Hình 3.5: Robot nhận tín hiệu qua trái. ..................................................................42 Hình 3.6: Robot nhận tín hiệu tắt kết nối. ............................................................... 43 DANH MỤC BẢNG BIỂU Bảng 2.1: Bảng đánh giá thuật toán SVM. ............................................................. 22 Bảng 2.2: Giá trị của 7 mô men bất biến. ............................................................... 37 Bảng 3.1: Kết quả độ chính xác của chương trình sau khi kiểm nghiệm. ..............43 -1- PHẦN MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong những năm gần đây, các ứng dụng về trí tuệ nhân tạo ngày càng phát triển và được đánh giá cao. Một lĩnh vực đang được quan tâm của trí tuệ nhân tạo nhằm tạo ra các ứng dụng thông minh, mang tính tri thức con người đó là nhận dạng. Với sự phát triển mạnh mẽ của công nghệ và nhu cầu của con người ngày càng cao. Một bài toán được đặt ra là: Làm sao có thể điều khiển máy tính, các thiết bị giải trí, robot…bằng những cử chỉ, hành động và lời nói của con người ? Nhận dạng hình ảnh và âm thanh là một giải pháp để giải quyết bài toán này, và một phần nhỏ trong lĩnh vực đó là nhận dạng cử chỉ bàn tay. Lý do chủ quan khi chọn đề tài: Những năm gần đây robot là một trong những thế mạnh của Trường Đại Học Lạc Hồng. Và em muốn làm cho Đại Học Lạc Hồng sẽ trở nên mạnh hơn nữa về công nghệ chế tạo robot thông minh. Để lại một cái gì đó quý báu cho những sinh viên khóa sau của trường phát triển tốt hơn về các công nghệ cao và các ngành khác liên quan. 2. Ý nghĩa khoa học và thực tiễn [1] Đưa ra một bản lý thuyết với các nội dung tìm hiểu, phân tích về các phương pháp phát hiện làn da con người, các phép toán hình thái trong xử lý ảnh và nhận dạng cử chỉ bàn tay của con người. Nhằm mục đích góp một phần vào lĩnh vực ứng dụng của nhận dạng, cụ thể hơn ở đây là có thể ứng dụng vào việc điều khiển di chuyển robot… Ứng với mỗi cử chỉ bàn tay thì robot sẽ xử lý tiến, lùi, qua phải hay qua trái. 3. Lịch sử nghiên cứu 3.1 Trên thế giới [3] a) Phân vùng bàn tay: Bàn tay bắt buộc phải có trong hình ảnh. Màu sắc là tín hiệu dễ dàng nhận biết để tính toán, những thuộc tính không thay đổi liên quan đến bàn tay là kết cấu hình dáng và nét đặc trưng của màu da. Hình 1: Nơi làm việc tương tác của ứng dụng. -2- Hình 2: Giao diện ứng dụng và màu da đang học trong hình vuông. Hình 3: Công thức tính màu da. Ngoài ra, từ đường viền của bàn tay và bao lồi của tay chúng ta có thể tính toán chuỗi các đường viền giữa hai đỉnh lồi liên tiếp. Trình tự này được gọi là góc lồi. Từ độ sâu này, một số đặc điểm hình dạng bàn tay có thể được nhận được chiều sâu trung bình. Hình 4: Hình ảnh nhận dạng bao lồi của bàn tay. Hình 5: Công thức tính chiều sâu của bàn tay. b) Nhận dạng cử chỉ: Cử chỉ của chúng ta cơ bản gồm 4 cử chỉ theo 4 hướng để thực hiện những yêu cầu của ứng dụng. Những cử chỉ được định nghĩa với thứ tự như Start, Move, Stop, và No-Hand. -3Bước đầu tiên trong nhận dạng xử lí cử chỉ là mô hình cử chỉ Start. Chiều dài trung bình của góc lồi là một bàn tay mở với những ngón tay được tách rời rộng hơn ngón tay không tách rời. Đặc điểm này sẽ khác những cử chỉ từ Stop sang Start, từ Start sang Move; và từ không bàn tay sang Start. 3.2 Trong nƣớc Hiện nay trong nước có một số chương trình “Nhận dạng cử chỉ bàn tay” nhưng đa phần độ chính xác của chương trình chưa cao. Một số công cụ hỗ trợ cho nhận dạng bàn tay như là webcame, camera thường… nhưng chưa hỗ trợ nhiều chức năng và thường khó thao tác. 4. Mục tiêu nghiên cứu - Nhận dạng cử chỉ bàn tay của con người để xây dựng chương trình điều khiển robot như 7 cử chỉ sau: - No Hand: Không có bàn tay trong hình ảnh (robot sẽ không di chuyển) - Start: Là bàn tay xòe (robot sẽ bắt đầu) - Move: Là bàn tay khép (robot chuẩn bị di chuyển) - Stop: Là bàn tay nắm (robot dừng lại) - Front: Là bàn tay tiến gần Camera Kinect (robot tiến về phía trước) - Left: Là bàn tay nghiêng sang trái (robot di chuyển qua trái) - Right: Là bàn tay nghiêng phải (robot di chuyển qua phải) - Back: Là bàn tay lùi xa Camera Kinect (robot lùi về phía sau) Hình 6: Mô hình điều khiển và quá trình bàn tay chuyển đổi hợp lệ. -4- Kết nối Kinect. - Lập trình với Kinect để lấy hình ảnh cần lấy. - Phân ngưỡng ảnh, xóa nhiễu với Opening và Closing. - Dùng bộ phân lớp SVM để xác định bàn tay khép, xòe, nắm. - Dùng 7 mô men bất biến để xác định cử chỉ bàn tay (khép trái, khép phải). - Kết nối Robocon. - Viết báo cáo tổng kết đề tài. 5. Đối tƣợng và phạm vi nghiên cứu a) Đối tƣợng nghiên cứu: - Các lý thuyết cơ bản về ảnh số. - Hình thái học. b) Phạm vi nghiên cứu: - Về lý thuyết: Dựa trên cơ sở lý thuyết để tìm hiểu sử dụng các phương pháp, thuật toán phù hợp để xử lý. - Về ứng dụng: Xây dựng ứng dụng phần mềm trên máy tính “Nhận dạng cử chỉ của bàn tay để điều khiển robot”. - Điều kiện thực hiện: Nhận dạng để phát hiện bàn tay trong ảnh, trong đó ảnh được lấy trong môi trường bình thường (không tối quá hoặc sáng quá). - Đối tượng nghiên cứu: Robot người LHU. 6. Sơ lƣợc về nội dung luận văn Luận văn gồm 3 chương: Chương 1: Giới thiệu tổng quan - Về thành phần cấu tạo của thiết bị cảm biến kinect, các thư viện hỗ trợ. - Giới thiệu các ứng dụng hỗ trợ nhận bàn tay. Chương 2: Nội dung nghiên cứu - Phát hiện làn da thông qua màu sắc. - Các thao tác với hình thái học nhị phân. - Trích các đặc điểm bàn tay. - Kết nối robot. Chương 3: Kết quả và hướng phát triển -Kết quả nghiên cứu. -Hướng phát triển trong tương lai. 7. Giới hạn đề tài Đề tài tập trung vào tìm hiểu các phương pháp xử lý ảnh và nhận dạng các cử chỉ của bàn tay. -5Giới hạn luận văn: Vì thời gian có hạn nên Luận văn chỉ dừng lại ở việc tìm hiểu lý thuyết về xử lý ảnh, nhận dạng và demo nhận dạng các cử chỉ bàn tay. Trong phần trình bày lý thuyết, em không tập trung vào vấn đề chứng minh, tối ưu các thuật toán mà trình bày các vấn đề, phương pháp và các thuật toán về xử lý ảnh và nhận dạng được sử dụng trong chương trình demo. -6- Chƣơng 1. Giới thiệu tổng quan 1.1 Giới thiệu về thiết bị Camera Kinect a) Sự ra đời và phát triển Kinect (hay còn biết với mã là Project Natal) là thiết bị thu nhận các cảm biến chuyển động, được phát triển bởi Microsoft. Thời gian đầu, Kinect là thiết bị chuyên dụng của hệ máy Xbox 360, phục vụ cho việc chơi game (Hình 1.2). Hình 1.1 : Camera Kinect của hàng Microsoft. Các mốc thời gian ra đời, phát triển của kinect và các thành phần liên quan:  5/30/2007: Microsoft nung nấu ý tưởng về một thiết bị dùng camera ghi nhận cử động điều khiển thay cho các thiết bị truyền thống.  6/1/2009: Microsoft công bố “Project Natal” ở hội nghị thường niên E3.  6/13/2010: Trong suốt hội nghị E3, đổi tên “Project Natal” thành Kinect, chính thức là thiết bị hỗ trợ cho Xbox 360.  11/4/2010: Microsoft chính thức tung ra thị trường Kinect; cũng từ đây, nhưng kế hoạch phát triển driver nguồn mở cho Kinect của các tổ chức/hacker cũng bắt đầu thực hiện.  11/10/2010: hacker trẻ tuổi Hector đã phát triển thành công driver cho Kinect.  2/21/2011: Microsoft lên kế hoạch cho việc phát triển bộ SDK hỗ trợ cho Kinect. Kinect sử dụng webcam, thiết bị thu phát sóng hồng ngoại, và thiết bị thu nhận âm thanh để ghi nhận tín hiệu chuyển động của game thủ và nhận dạng các lệnh điều khiển thông qua giọng nói, giúp cho các game thủ tương tác với Xbox 360 mà không cần chạm vào bất kì thiết bị điều khiển nào. Trong đó, game thủ có thể thao tác như thật. -7- Hình 1.2: Nhận diện hành động game thủ và điều khiển nhân vật trong game. Kinect, hỗ trợ các chức năng tương tác sau:  Ghi nhận chuyển động tay (hand gesture), bao gồm các hành động xoay vòng (circle), di chuyển tay (wave gesture), push,...  Ghi nhận chuyển động toàn cơ thể (full body skeleton), xác định các vị trí chính của cơ thể như đầu, vai, cẳng tay, chân,…  Điều khiển bằng giọng nói.  Nhận dạng số người đang chơi. b) Nh ng thành phần chính của Kinect . Hình 1.3: Những thành phần chính của Kinect Các thành phần bên trong Kinect gồm có: bộ nhớ RAM, bộ cảm ứng Prime Sense PS1080-A2, quạt tản nhiệt, động cơ điều khiển góc ngẩng (Motorized Tilt), bộ gia tốc 3 trục, 4 microphone (Multi – Array Mic) và 3 camera: RGB camera, bộ cảm biến độ sâu (3D Depth Sensors). Các thông số kỹ thuật: - Khoảng cách hiệu quả: 0.83.5m. - RGB camera: độ phân giải 640 x 480, 30 frame/s, 32 bit màu. -8- Góc quay hiệu quả: 57º ngang, 43º dọc, ± 27º nghiêng. Kết nối: USB 2.0 Sensor: RGB& Depth Audio: 4 microphones Platfom: VS.NET 2010. Middleware: SDK Ngôn ngữ: C++,C# OS: Win 7 Dimensions: 1.5" x 7" x 1.9" c) Thƣ viện h trợ Kinect Ngay khi mới ra đời, Kinect đã được quan tâm bởi rất nhiều nhà phát triển phần mềm, không chỉ trên mảng phát triển game cho Xbox mà còn trên mảng xử lý ảnh ứng dụng trong y học, robot, mapping, … Do đó, mà nhiều thư viện được viết cho Kinect ra đời. Cho đến thời điểm hiện tại, các thư viện đáng chú ý là Libfreenect, Code Laboratories Kinect, OpenNI và Kinect SDK.  Thư viện Libfreenect: Libfreenect là thư viện được phát triển bởi OpenKinect, do một cộng đồng những người quan tâm đến phần cứng Kinect viết ra và chia sẻ. Cộng đồng OpenKinect làm việc hoàn toàn tự nguyện và không vì mục đích lợi nhuận, họ phát triển Libfreenect thành một mã nguồn mở cho các hệ điều hành khác nhau Windows, Linux và OS X. Hiện tại, Libfreenect được đóng gói cho việc sử dụng trên Python, C, C++, C#, Java JNI, Java JNA, Javascript.  Thư viện Code Laboratories Kinect: Code Laboratories (CL) là một công ty phần mềm chuyên hỗ trợ các nhà phát triển, lập trình viên khai thác các tính năng của các thiết bị xử lý ảnh. Trong số đó Kinect không phải là ngoại lệ, CL cung cấp cho người sử dụng những tính năng cơ bản nhất của Kinect về camera, audio và motor.  Thư viện OpenNI: Thư viện OpenNI được xem là thư viện mạnh nhất trước sự có mặt của Kinect SDK 1.0, thư viện này hỗ trợ đa ngôn ngữ trên nhiều platform khác nhau, giúp cho các lập trình viên có thể viết các ứng dụng trên Kinect rất dễ dàng tương tác tự nhiên Natural Interaction (NI). Mục đích chính của OpenNI là xây dựng các hàm API chuẩn, cho phép thư viện có khả năng kết hợp với các middleware nhằm làm tăng sức mạng cho Kinect.  Thư viện Kinect SDK: SDK cung cấp cho nhà phát triển những bộ cảm biến có chiều sâu, camera cảm biến màu sắc và xác định nguồn âm thanh theo chùm tia. Các nhà phát triển cũng có thể theo dõi ảnh ở dạng khung sườn của một hay hai người đang di chuyển trong tầm ngắm Kinect, từ đó các nhà phát triển có thể tạo ra những ứng dụng hướng theo cử chỉ (gesture). SDK gồm tính năng âm thanh như giảm tiếng ồn và hạn chế tiếng vang. Các nhà phát triển có thể truy cập vào công nghệ hình thành tia để nhận diện ra nguồn âm thanh hay có thể truy cập vào giao diện trình ứng dụng (API) để nhận diện giọng nói trong hệ thống Windows. -9Các nhà phát triển có thể viết ứng dụng bằng ngôn ngữ C#, C++ và bất cứ ngôn ngữ .Net nào. d) Một số ứng dụng của Kinect Mua sắm vốn là một hoạt động xã hội và những kinh nghiệm mua sắm có thể hỗ trợ nhiều người dùng cùng một lúc bằng cách tận dụng các công cụ xã hội. Ví dụ, các hình ảnh được chụp với các sản phẩm ảo có thể được chia sẻ thông qua Facebook và Twitter để giúp thông tin đến và phản hồi từ bạn bè. Hệ thống điều khiển dựa trên camera theo dõi chuyển động, Kinect của Microsoft đã chứng minh giá trị ứng dụng cao của mình trong nhiều lĩnh vực từ y tế đến giáo dục. Gần đây nhất, Microsoft đã giới thiệu một lĩnh vực ứng dụng mới cho công nghệ này đó chính là mua sắm. Hình 1.4: Chiếc xe có khả năng giúp nhận biết các món hàng bạn mua. Theo đó, một chiếc xe đẩy đã được thiết kế đặc biệt, tích hợp thiết bị Kinect và cùng một màn hình hiển thị đi kèm. Chiếc xe này có khả năng giúp nhận biết các món hàng bạn mua, tự động kiểm tra chúng với danh sách đi chợ và thậm chí có thể tự đi theo bạn loanh quanh trong siêu thị. -10- Hình 1.5: Chiếc xe thử nghiệm tại hệ thống siêu thị Whole Foods Nguyên mẫu này chỉ mới là bước thử nghiệm ban đầu tại hệ thống siêu thị Whole Foods, Mỹ. Microsoft hy vọng sẽ có thể phát hiện và khắc phục các hạn chế, đồng thời hoàn thiện sản phẩm trước khi chúng được đem ra ứng dụng trong thực tế. Trong trò chơi: Vào hai ngày 6-7/12/2011 tại Kuala Lumpur (Malaysia), chuyên gia Jason Trump của Microsoft cho hay Kinect đang khiến mọi người thay đổi quan niệm không hay về game. Không còn ngồi lỳ trước màn hình máy tính, Kinect giúp mọi người chơi vận động toàn bộ cơ thể như thể đang thực hiện một bài tập thể dục. Sử dụng Kinect, các nhà phát triển có thể tạo ra những trò chơi thú vị và mang đến những đột phá trong giáo dục. Giáo viên có thể khiến bài học sinh động hơn khi điều khiển bằng tay các hình minh họa. Chơi game sẽ giống như một quá trình liên tục khám phá, sửa sai, tìm tòi cái mới cho đến khi thành thục, nhuần nhuyễn mà không tạo cảm giác nhàm chán cho học sinh. Điều khiển màn hình máy tính không dùng chuột, bàn phím: Không cần dùng đến chuột và bàn phím, nhóm Fluid Interfaces Group của Viện công nghệ MIT (Mỹ) vẫn có thể cuộn thanh cuốn, bấm vào đường link, phóng to nội dung nhờ thiết bị chơi game Kinect. -11- Hình 1.6: Điều khiển máy tính bằng Kinect. Đại học Nam California (Mỹ) giới thiệu bộ công cụ có tên Sloow kết hợp với sensor cảm ứng của Microsoft để điều khiển hòm thư bằng hành động như mở email với động tác như đang xé phong bì, trả lời thư bằng cách hất ngón cái ra phía sau, hoặc làm động tác dán tem để gửi email đi. Hình 1.7: Điều khiển máy tính bằng cử chỉ. 1.2 Các giai đoạn xử lý ảnh Quá trình xử lý ảnh được xem như là quá trình thao tác với ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của quá trình xử lý ảnh là một ảnh tốt hơn hoặc là một kết luận. a) Các giai đoạn xử lý ảnh bao gồm: - Thu nhận ảnh: Ảnh được thu nhận chính là ảnh gốc để đưa vào xử lý ở các giai đoạn sau, nếu ảnh gốc có chất lượng kém thì các bước xử lý sau có hiệu quả thấp. Ảnh đầu vào sẽ được thu nhận qua các thiết bị như camera, sensor, máy scanner… - Tiền xử lý: -12Các phương pháp của tiền xử lý nhằm mục đích nâng cao chất lượng ảnh như: tăng độ tương phản, lọc nhiễu… - Phân đoạn: Phân vùng ảnh là tách một ảnh đầu vào thành các thành phần để biểu diễn, phân tích, nhận dạng ảnh. Nếu quá trình tách thành phần ảnh quá chi tiết thì việc nhận dạng các thành phần được tách trở nên phức tạp. Ngược lại, nếu việc tách các thành phần của ảnh quá đơn giản thì kết quả nhận được sẽ sai. - Biểu diễn: Giai đoạn này tiếp theo sau giai đoạn phân đoạn, vì vậy mà ảnh đầu ra của phân đoạn chứa các đặc điểm của vùng ảnh và mã liên kết vùng lân cận. Việc chọn các tính chất để thể hiện ảnh gọi là trích đặc trưng làm cơ sở cho việc phân biệt lớp đối tượng này với lớp đối tượng khác. - Nhận dạng: Nhận dạng ảnh là quá trình xác định ảnh, là quá trình so sánh với mẫu chuẩn đã được học. Theo lý thuyết về nhận dạng thì có 2 loại nhận dạng: Nhận dạng theo tham số và Nhận dạng theo cấu trúc. - Cơ sở trí thức: Ngoài việc tối ưu, đơn giản hóa trong việc xử lý và phân tích ảnh. Thì con người mong muốn tiếp nhận và xử lý ảnh theo phương pháp trí tuệ con người. Phân đọan Biểu diễn Tiền xử lý Cơ sở tri thức Nén ảnh ảnh Nhận dạng Thu nhận ảnh Ảnh nguồn Hình 1.8: Các giai đoạn xử lý ảnh. 1.3 Giới thiệu về SVM (Support Vector Machine) SVM sử dụng thuật toán học nhằm xây dựng một siêu phẳng làm cực tiểu hoá độ phân lớp sai của một đối tượng dữ liệu mới. Độ phân lớp sai của một siêu phẳng được đặc trưng bởi khoảng cách bé nhất tới siêu phẳng đấy. SVM có khả năng rất lớn cho các ứng dụng được thành công trong bài toán nhận dạng. -13Như đã biết, nhận dạng bàn tay là một cách tiếp cận mới để tạo ra tập phân lớp bàn tay từ các mẫu cho trước. Cách tiếp cận này phối hợp với sự thực thi ở mức độ cao và hiệu suất cùng với những am hiểu về mặt lý thuyết, tính chất thô ngày càng được hoàn thiện. Thông thường, hiệu quả ở mức độ cao không có các thành phần suy nghiệm. Phương pháp SVM có khả năng tính toán sẵn sàng và phân lớp, nó trở thành lý thuyết học mà có thể chỉ dẫn những ứng dụng thực tế trên toàn cầu. Đặc trưng cơ bản quyết định khả năng phân lớp là khả năng phân lớp những dữ liệu mới dựa vào những tri thức đã tích lũy được trong quá trình huấn luyện. Sau quá trình huấn luyện nếu hiệu suất tổng quát hóa của bộ phân lớp cao thì thuật toán huấn luyện được đánh giá là tốt. Hiệu suất tổng quát hóa phụ thuộc vào hai tham số là sai số huấn luyện hay và năng lực của máy học. Trong đó sai số huấn luyện là tỷ lệ lỗi phân lớptrên tập dữ liệu huấn luyện. Còn năng lực của máy học được xác định bằng kích thước Vapnik-Chervonenkis (kích thước VC). Kích thước VC là một khái niệm quan trọng đốivới một họ hàm phân tách (hay là tập phân lớp). Đại lượng này được xác định bằng số điểm cực đại mà họ hàm có thể phân tách hoàn toàn trong không gian đối tượng. Một tập phân lớp tốt là tập phân lớp có năng lực thấp nhất (có nghĩa là đơn giản nhất) và đảm bảo sai số huấn luyện nhỏ. Phương pháp SVM được xây dựng trên ý tưởng này. a) Nh ng ƣu điểm khi sử dụng SVM: - Cung cấp nhiều công cụ. - Phương pháp học mới. - Nền tảng lý thuyết học thống kê. - Tối ưu toàn cục, mô hình chất lượng cao, chịu đựng được nhiễu. - Thành công trong nhiều ứng dụng. b) Nh ng điểm hạn chế: - Khó dịch kết quả. - Độ phức tạp vẫn cao. - Xử lý dữ liệu kiểu số. - Tham số đầu vào. 1.4 Các công thức liên quan Gọi f(x, y) là ảnh số, p và q là các điểm ảnh, S là một tập con các điểm ảnh. Cho điểm ảnh p(x, y). a) Quan hệ láng giềng (Neighborhood): Các láng giềng theo hướng dọc và ngang được được định nghĩa: - Kí hiệu: N4(p) - Khi đó các điểm ảnh láng giềng của (x, y) là: (x+1, y), (x-1, y), (x, y+1), y-1). (x, -14Các láng giềng theo hướng chéo được định nghĩa: - Kí hiệu: ND(p) - Khi đó các điểm ảnh láng giềng của (x, y) là: (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1). Các láng giềng theo 8 hướng được định nghĩa: - Kí hiệu: N4(p) + ND(p) Hình 1.9: Quan hệ láng giềng. b) Quan hệ lân cận (Adjacency): Gọi V là tập các giá trị xám dùng để định nghĩa lân cận. Ví dụ V = {1} là một tập định nghĩa cho lân cận của các điểm ảnh có giá trị 1. 4-Adjacency: p và q là 4-Adjacency nếu q  N4(p) 8-Adjacency: p và q là 8-Adjacency nếu q  N8(p) m-Adjacency: p và q là m-Adjacency nếu q  N4(p) hoặc q  N D(p) và N4(p) ND(p)  V. m-Adjacency là sự cải tiến của 8-Adjacency nhằm loại bỏ bớt các đường liên kết kép thường gặp khi ta dùng 8-Adjacency. Ví dụ: Hình 1.10: Quan hệ lân cận. Trong đó: (a) là tập các điểm ảnh. (b) là kết quả 8-Adjacency. (c) là kết quả m-Adjacency. c) Quan hệ liên thông (Conectivity): -15Quan hệ liên thông giữa 2 điểm ảnh là quan trọng bởi vì nó được sử dụng để thiết lập các đường biên của đối tượng và các thành phần của các vùng ảnh. Hai điểm ảnh có quan hệ liên thông với nhau: - Chúng là láng giềng của nhau. - Các giá trị xám của chúng thỏa mãn tiêu chuẩn nhất định về sự tương đồng. Với thì tập các điểm ảnh trong S có liên thông với p thì được gọi là một thành phần liên thông của S. Nếu S chỉ có 1 thành phần liên thông thì S được gọi là 1 tập liên thông. d) Khoảng cách gi a các điểm ảnh: Cho p(x, y), q(s, t), z(u, v). D là hàm xác định khoảng cách. D(p, q) >= 0 ( D(p,q) = 0 nếu p = q) D(p, q) = D(q, p) D(p, z) =< D(p, q) + D(q, z) Khoảng cách Euclid: Các khoảng cách Euclid nhỏ hơn hoặc bằng r kể từ (x, y) là nằm trong đường tròn tâm (x, y) bán kính r. Khoảng cách City-Block: (Khoảng cách D4) Công thức: D4(p, q) = | x – s | + | y – t |. Hình 1.11: Khoảng cách City-Block. Khoảng cách ChessBoard (Khoảng cách D8) Công thức: D8(p, q) = max( | x – s | + | y – t | ). Hình 1.12: Khoảng cách ChessBoard. -16e) Độ lệch chuẩn: Là một khái niệm thông dụng trong quá trình khảo sát ảnh. Một trong những tham số thống kê quan trọng được tính cùng với giá trị trung bình, phương sai, giá trị và vị trí của điểm ảnh nhỏ nhất và lớn nhất, độ lệch… Thuật toán: Cho một dãy n giá trị cho trước x1, x2,…..xn Bƣớc 1: Tìm giá trị trung bình x của dãy số đã cho với công thức x1  x2  ....xn 1 N x   xi n N i 1 Bƣớc 2: Với mỗi x trong dãy, tính độ lệch của nó so với x với công thức: x - x Bƣớc 3: Tính bình phương của các giá trị thu được ở bước 2. Bƣớc 4: Tìm giá trị trung bình của các bình phương độ lệch tìm được ở bước 3. Các giá trị này được gọi là phương sai. Ký hiệu:  2 Bƣớc 5: Tính căn bậc hai của phương sai ta được kết quả theo công thức:  1 N N  ( x  x) 2 i i 1 Độ lệch chuẩn là giá trị thể hiện mức độ hội tụ hay phân tán của một tập dữ liệu. Nếu tập dữ liệu đó có độ lệch chuẩn nhỏ thì các phần tử của tập dữ liệu có sự tương đồng cao, ngược lại thì dữ liệu có vùng phân tán lớn. f) Ma trận hiệp phƣơng sai Nếu   E ( X ) là giá trị kỳ vọng của biến ngẫu nhiên X thì phương sai là: var( X )  E(( X   )2 ) . Nghĩa là phương sai là giá trị kỳ vọng của bình phương của độ lệch của X so với giá trị trung bình của nó. Nếu X và Y là hai vector, X i và Yi là các thành phần của hai vector và là các biến ngẫu nhiên có phương sai xác định (không quá lớn tới vô cực).  X1  X     X n  Thì ta có ma trận hiệp phương sai:  ij conv( X i , X j )  E[( X i  i )( X j   j )] với i  E ( X i ) -171.5 Giới thiệu về mô-men bất biến Khai thác các đặc điểm và phát hiện đối tượng là một trong những lĩnh vực nghiên cứu lớn của xử lý ảnh và đồ họa vi tính. Phát hiện đối tượng cơ bản dựa trên phép kết hợp và mô tả của hình dạng đối tượng. Một số kỹ thuật dùng để mô tả, thể hiện hình dạng của đối tượng như là: phân tích các đặc điểm vô hướng, nhận diện mô tả Fourier, mô-men bất biến hay là chuỗi đường biên. Mô-men bất biến thường được dùng để trích đặc điểm trong xử lý ảnh, và ghi nhận hình dạng đối tượng và phân lớp. Mô-men có thể cung cấp các ký tự của một đối tượng duy nhất mô tả hình dạng của đối tượng. Ghi nhận tính bất biến của hình dạng đối tượng được thực hiện bởi bộ phận lớp trong không gian mô men bất biến đa chiều. Kỹ thuật này được phát triển từ việc ghi nhận các đặc điểm bất biến từ mô-men của đối tượng và mô tả đối tượng. Kỹ thuật dùng mô men bất biến trong việc trích đặc điểm của đối tượng ảnh đạt được sự thành công như là việc khai thác các loại dữ liệu, phương thức ghi nhận các giá trị bất biến của mô men ảnh. Hu (Hu, 1962) là người đầu tiên đặt nền tảng toán học cho mô men bất biến 2 chiều và đã chứng minh bằng cách ứng dụng phát hiện hình dáng đối tượng. Hu định nghĩa 7 giá trị mô tả hình dạng đối tượng được tính toán từ những mô men trung tâm, và không phụ thuộc vào 3 dạng biến đổi đối tượng là chuyển đổi (chuyển đổi vị trí), co giãn (biến đổi kích thước) và hướng (biến đổi quay). 1.6 Giới thiệu các phép toán hình thái học “Morphology” là hình thái và cấu trúc của đối tượng, hay nó diễn tả những phạm vi và các mối quan hệ giữa các phần của một đối tượng. Trong sinh học, hình thái học chú trọng tới hình dạng của một cá thể hơn, chẳng hạn có thể phân tích hình dạng của một chiếc lá để từ đó có thể nhận dạng được loại cây đó là cây gì, nghiên cứu hình dạng của nhóm vi khuẩn, dựa trên đặc điểm nhận dạng của hình thái mà phân biệt chúng thuộc nhóm vi khuẩn nào… Trong xử lý ảnh, Morphology là phương pháp dùng để trích dãn, trích những thành phần trong ảnh, các thành phần đó hữu ích trong việc biểu diễn và diễn tả hình dạng của miền như: biên, xương và bao gồm. Tùy theo trường hợp cụ thể mà có một cách phân lớp phù hợp với nó: Có thể phân lớp dựa trên những hình dạng bao quanh như (elip, tròn,...), kiểu và mức độ của những hình dạng bất quy tắc (lồi, lõm,...), những cấu trúc trong (lỗ, đường thẳng, đường cong,...) mà đã được tích lũy qua nhiều năm quan sát. Hình thái toán học là một tập các phép toán dùng để phân tích ảnh và xử lý tín hiệu đa chiều theo mẫu, hình dạng S được chọn. Trong đó tín hiệu đầu vào được so sánh một cách cục bộ với S (thành phần cấu trúc) có dạng bất kì, tại điểm tham chiếu R (thông thường R là tâm của S và ánh xạ tương ứng tới tín hiệu đang xét). a) Phép Dilation Phép Dilation thì mở rộng thêm điểm ảnh vào đối tượng ảnh, làm cho ảnh trở nên lớn hơn.