Đề tài Nghiên cứu một số kỹ thuật xác định độ đo tương tự và ứng dụng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN TRẦN QUANG HUY NGHIÊN CỨU MỘT SỐ KỸ THUẬT XÁC ĐỊNH ĐỘ ĐO TƯƠNG TỰ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Thái nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN TRẦN QUANG HUY NGHIÊN CỨU MỘT SỐ KỸ THUẬT XÁC ĐỊNH ĐỘ ĐO TƯƠNG TỰ VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: TS. Phạm Việt Bình Thái nguyên – 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng nội dung đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm. Tác giả luận văn Trần Quang Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 MỤC LỤC Nội dung Trang ĐẶT VẤN ĐỀ ............................................................................................... 8 LỜI NÓI ĐẦU .............................................................................................. 9 Chƣơng 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ ĐỘ ĐO TƢƠNG TỰ TRONG XỬ LÝ ẢNH ................................................................................ 11 1.1. Khái quát về xử lý ảnh ..................................................................... 11 1.1.1. Một số khái niệm cơ bản .............................................................. 11 1.1.2. Một số vấn đề trong xử lý ảnh ..................................................... 12 1.1.2.1. Các hệ thống xử lý ảnh ............................................................... 12 1.1.2.2. Các hình thái của ảnh.................................................................. 14 1.1.2.3. Một số ứng dụng trong xử lý ảnh ................................................ 15 1.1.2.4. Một số khái niệm, định nghĩa trong xử lý video .......................... 17 1.1.2.5. Lược đồ màu (Color Histogram) ................................................. 22 1.1.2.6. Lược đồ tương quan màu (Color Correlogram) .......................... 25 1.1.2.7. Đặc trưng chuyển động (Motion) ................................................ 26 1.1.2.8. Các bước thao tác với file video ................................................. 28 1.2. Độ đo tƣơng tự trong xử lý ảnh ....................................................... 30 Chƣơng 2: MỘT SỐ PHƢƠNG PHÁP XÁC ĐỊNH ĐỘ ĐO TƢƠNG TỰ .... 32 2.1. Độ đo dựa trên khoảng cách ............................................................ 32 2.1.1. Độ đo khoảng cách min – max..................................................... 32 2.1.2. Độ đo khoảng cách Euclid ........................................................... 32 2.1.3. Độ đo khoảng cách toàn phương: ................................................ 32 2.2. Độ đo sử dụng trọng số .................................................................... 32 2.2.1. Độ đo có trọng số: ....................................................................... 32 2.2.2. Độ đo hỗn hợp ............................................................................. 33 2.2.2.1. Thuộc tính rời rạc ....................................................................... 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 2.2.2.2. Thuộc tính có thứ tự ................................................................... 34 2.2.2.3. Thuộc tính liên tục ...................................................................... 35 2.2.2.4. Kết hợp độ đo của các thuộc tính ................................................ 36 2.2.2.5. Thuật toán nhanh cho thuộc tính liên tục .................................... 38 2.2.2.6. Thuật toán nhanh cho thuộc tính có thứ tự .................................. 40 2.3. Độ đo tƣơng tự có thể học (Trainable similarity measure) ............ 41 2.4. Độ đo dựa trên Histogram ............................................................... 43 2.4.1. Giới thiệu .................................................................................... 43 2.4.2. Định nghĩa ................................................................................... 43 2.4.3. Lược đồ mức xám hai chiều......................................................... 44 2.4.4. Các tính chất của lược đồ mức xám ............................................. 45 2.4.5. Quan hệ giữa lược đồ mức xám và ảnh ........................................ 46 2.4.6. Một chiều .................................................................................... 46 2.4.7. Hai chiều ..................................................................................... 47 CHƢƠNG 3: ỨNG DỤNG ĐỘ ĐO TƢƠNG TỰ TRONG VIỆC PHÂN LOẠI ẢNH TRONG FILE VIDEO .......................................................... 49 3.1. Giới thiệu bài toán ............................................................................ 49 3.2. Cài đặt thuật toán ............................................................................. 49 3.2.1. Code đọc ảnh ................................................................................ 49 3.2.2. Code đọc và extract frame file video ............................................ 56 3.3. Kết quả thực nghiệm và đánh giá .................................................... 59 PHẦN KẾT LUẬN ..................................................................................... 62 TÀI LIỆU THAM KHẢO .......................................................................... 63 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 ĐẶT VẤN ĐỀ Lĩnh vực xử lý ảnh số tĩnh và xử lý ảnh động (video) đã được hình thành và phát triển vào những thập kỷ đầu của thế kỷ XX. Các phương pháp xử lý ảnh bắt nguồn từ một số ứng dụng như nâng cao chất lượng thông tin hình ảnh đối với mắt người và xử lý số liệu, nhận dạng cho hệ thống tự động. Một trong những ứng dụng đầu tiên của xử lý ảnh là nâng cao chất lượng ảnh báo truyền qua cáp giữa London và New York vào những năm 1920. Thiết bị đặc biệt mã hóa hình ảnh, truyền qua cáp và khôi phục lại ở phía thu. Cùng với thời gian, do kỹ thuật máy tính phát triển nên xử lý hình ảnh ngày càng phát triển. Các kỹ thuật cơ bản cho phép tìm kiếm, đối sánh những ảnh để tìm ra sự tương tự. Từ năm 1964 đến nay, phạm vi xử lý ảnh và video (ảnh động) phát triển không ngừng. Các kỹ thuật xử lý ảnh số (digital image processing) đang được sử dụng để giải quyết một loạt các vấn đề nhằm nâng cao chất lượng thông tin hình ảnh. Và xử lý ảnh số được ứng dụng rất nhiều trong y tế, thiên văn học, viễn thám, sinh học, y tế hạt nhân, quân sự, sản xuất công nghiệp … Một ứng dụng quan trọng trong xử lý ảnh số mà không thể không nhắc đến đó là đối sánh một ảnh với các frame của một file video nhằm mục đích tìm kiếm sự giống nhau hay khác nhau, qua đó giúp cho quá trình xử lý công việc nhanh hơn mà không mất thời gian kiểm tra từng file video. Chính vì vậy, tôi lựa chọn đề tài “Nghiên cứu một số kỹ thuật xác định độ đo tƣơng tự và ứng dụng ” nhằm nghiên cứu một số kỹ thuật xác định độ đo tương tự như Trainable similarity measure (TSM) và Histogram dòng cột. Qua đó, tôi có thể đưa ra một số nhận xét và có thể có giải pháp đề xuất để phân loại đối tượng ảnh trong file video hiệu quả hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 LỜI NÓI ĐẦU Xử lý ảnh là một lĩnh vực đã và đang được quan tâm của nhiều nhà khoa học trong và ngoài nước bởi tính phong phú và lợi ích của nó được ứng dụng trong khoa học kỹ thuật, kinh tế, xã hội và đời sống con người. Lĩnh vực xử lý ảnh liên quan tới nhiều ngành khác như: hệ thống tin học, trí tuệ nhân tạo, nhận dạng, viễn thám, y học... Hiện nay, thông tin hình ảnh đóng vai trò rất quan trọng trong trao đổi thông tin, bởi phần lớn thông tin mà con người thu được thông qua thị giác. Do vậy, vấn đề nhận dạng trong xử lý ảnh, đặc biệt là nhận dạng đối tượng ảnh chuyển động đang được quan tâm bởi yêu cầu ứng dụng đa dạng của chúng trong thực tiễn. Mục đích đặt ra cho xử lý ảnh được chia thành hai phần chính: phần thứ nhất liên quan đến những khả năng từ các ảnh thu lại các ảnh để rồi từ các ảnh đã được cải biến nhận được nhiều thông tin để quan sát và đánh giá bằng mắt, chúng ta coi như là sự biến đổi ảnh (image transformation) hay sự làm đẹp ảnh (image enhancement). Phần hai nhằm vào nhận dạng hoặc đoán nhận ảnh một cách tự động, đánh giá nội dung các ảnh. Quá trình nhận dạng ảnh nhằm phân loại các đối tượng thành các lớp đối tượng đã biết (supervised learning) hoặc thành những lớp đối tượng chưa biết (unsupervised learning). Sau quá trình tăng cường và khôi phục (đối với những ảnh có nhiễu), giai đoạn tiếp theo, người ta phải trích rút các đặc tính quan trọng, quyết định của ảnh cần nhận dạng. Các đặc tính đó có thể là đặc tính hình học, đặc tính ngữ cảnh. Bên cạnh đó, trong những năm gần đây lượng dữ liệu video số đã tăng lên đáng kể cùng với việc sử dụng rộng rãi các ứng dụng đa phương tiện trong giáo dục, giải trí, kinh doanh, y tế… Thực tế này đặt ra các bài toán như: giảm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 dung lượng video và tăng tốc độ xử lý, tổ chức lưu trữ và tìm kiếm video hiệu quả, hiểu nội dung video, nhận dạng đối tượng trong video. Một số nhóm nghiên cứu trong và ngoài nước đã đưa ra các phương pháp giải quyết giảm dung lượng video, tổ chức cơ sở dữ liệu video, và đặc biệt lĩnh vực là nhận dạng đối tượng, đối tượng chuyển động trong dữ liệu video cũng đang được quan tâm bởi tính ứng dụng đa dạng và cần thiết của nó trong khoa học, xã hội và đời sống con người. Trong luận văn thạc sĩ với đề tài “Nghiên cứu một số kỹ thuật xác định độ đo tƣơng tự và ứng dụng”, tôi tập trung giải quyết bài toán đọc ảnh và so sánh với các frame trong file video để đưa ra nhận xét. Luận văn gồm phần mở đầu, phần kết luận, và 3 chương nội dung: Chương 1 : Khái quát về xử lý ảnh và độ đo tương tự trong xử lý ảnh Chương 2 : Một số phương pháp xác định độ đo tương tự Chương 3 : Ứng dụng trong việc phân loại ảnh Được sự giúp đỡ của các thầy cô trong Khoa Công nghệ thông tin - Đại học Thái Nguyên cũng như của bạn bè, đồng nghiệp, đặc biệt là chỉ bảo tận tình của Tiến sĩ Phạm Việt Bình và sự nỗ lực của bản thân, đến nay tôi đã hoàn thành đề tài. Tuy nhiên trong quá trình làm việc, mặc dù đã cố gắng nỗ lực hết sức nhưng do kiến thức và kinh nghiệm vẫn còn hạn chế nên không thể tránh khỏi còn sai sót, em tha thiết kính mong nhận được sự chỉ bảo của các thầy cô để đề tài được hoàn thiện hơn. Em xin chân thành cảm ơn. Thái Nguyên, ngày 30 tháng 10 năm 2009 Học viên thực hiện Trần Quang Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 CHƢƠNG 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ ĐỘ ĐO TƢƠNG TỰ TRONG XỬ LÝ ẢNH 1.1. Khái quát về xử lý ảnh 1.1.1. Một số khái niệm cơ bản[1] Xử lý ảnh là một trong những mảng quan trọng nhất trong kỹ thuật thị giác máy tính, là tiền đề cho nhiều nghiên cứu thuộc lĩnh vực này. Hai nhiệm vụ cơ bản của quá trình xử lý ảnh là nâng cao chất lượng thông tin hình ảnh và xử lý số liệu cung cấp cho các quá trình khác trong đó có việc ứng dụng thị giác vào điều khiển. Quá trình bắt đầu từ việc thu nhận ảnh nguồn (từ các thiết bị thu nhận ảnh dạng số hoặc tương tự) gửi đến máy tính. Dữ liệu ảnh được lưu trữ ở định dạng phù hợp với quá trình xử lý. Người lập trình sẽ tác động các thuật toán tương ứng lên dữ liệu ảnh nhằm thay đổi cấu trúc ảnh phù hơp với các ứng dụng khác nhau. Quá trình xử lý nhận dạng ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Hình 1.1. Quá trình xử lý ảnh Ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Bởi vì, ảnh có thể xem là tập hợp các điểm ảnh. Trong đó, mỗi điểm ảnh được xem như là đặc Ảnh Xử lý ảnh Ảnh tốt hơn Kết luận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian và do đó nó có thể xem như một hàm n biến P(c1, c2,..., cn). Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hình 1.2. Các bƣớc cơ bản trong một hệ thống xử lý ảnh 1.1.2. Một số vấn đề trong xử lý ảnh 1.1.2.1. Các hệ thống xử lý ảnh * Tiền xử lý Tiền xử lý là giai đoạn đầu tiên trong xử lý ảnh số. Tuỳ thuộc vào quá trình xử lý tiếp theo trong giai đoạn này sẽ thực hiện các công đoạn khác nhau như: nâng cấp, khôi phục ảnh, nắn chỉnh hình học, khử nhiễu v.v.. * Trích chọn đặc điểm Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm. * Đối sánh, nhận dạng Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy, được ứng dụng trong nhiều ngành khoa học khác nhau. Ví dụ mẫu có thể là ảnh của Thu nhận ảnh (scanner, camera…) Tiền xử lý (xoá nhiễu, lọc nhiễu,…) Trích chọn đặc điểm Hậu xử lý Đối sánh rút ra kết luận Hệ quyết định Lưu trữ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 vân tay, ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặc một ký đồ tín hiệu tiếng nói. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó. Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân tích phân biệt (discriminant analyis), trong đó mẫu đầu vào được định danh như một thành phần của một lớp đã xác định. Hoặc phân loại không có mẫu (unsupervised classification hay clustering) trong đó các mẫu được gán vào các lớp khác nhau dựa trên một tiêu chuẩn đồng dạng nào đó. Các lớp này cho đến thời điểm phân loại vẫn chưa biết hay chưa được định danh. Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai đoạn chủ yếu sau đây:  Thu nhận dữ liệu và tiền xử lý.  Biểu diễn dữ liệu.  Nhận dạng, ra quyết định. Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là:  Đối sánh mẫu dựa trên các đặc trưng được trích chọn.  Phân loại thống kê.  Đối sánh cấu trúc.  Phân loại dựa trên mạng nơ-ron nhân tạo. Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếp cận khác nhau. Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhận dạng và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lai (hybrid system) bao gồm nhiều mô hình kết hợp. Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc sống không chỉ tạo ra những thách thức về thuật giải, mà còn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải được trích chọn dựa trên các thủ tục phân tích dữ liệu. 1.1.2.2. Các hình thái của ảnh * Chuyển ảnh màu thành ảnh xám Đơn vị tế bào của ảnh số là pixel. Tùy theo mỗi định dạng là ảnh màu hay ảnh xám mà từng pixel có thông số khác nhau. Đối với ảnh màu từng pixel sẽ mang thông tin của ba màu cơ bản tạo ra bản màu khả kiến là Đỏ (R), Xanh lá (G) và Xanh biển (B) [Thomas 1892]. Trong mỗi pixel của ảnh màu, ba màu cơ bản R, G và B được bố trí sát nhau và có cường độ sáng khác nhau. Thông thường, mỗi màu cơ bản được biểu diễn bằng tám bit tương ứng 256 mức độ màu khác nhau. Như vậy mỗi pixel chúng ta sẽ có 28x3=224 màu (khoảng 16.78 triệu màu). Đối với ảnh xám, thông thường mỗi pixel mang thông tin của 256 mức xám (tương ứng với tám bit) như vậy ảnh xám hoàn toàn có thể tái hiện đầy đủ cấu trúc của một ảnh màu tương ứng thông qua tám mặt phẳng bit theo độ xám. Trong hầu hết quá trình xử lý ảnh, chúng ta chủ yếu chỉ quan tâm đến cấu trúc của ảnh và bỏ qua ảnh hưởng của yếu tố màu sắc. Do đó bước chuyển từ ảnh màu thành ảnh xám là một công đoạn phổ biến trong các quá trình xử lý ảnh vì nó làm tăng tốc độ xử lý là giảm mức độ phức tạp của các thuật toán trên ảnh. * Lược đồ xám của ảnh (Histogram) Lược đồ xám của một ảnh số có các mức xám trong khoảng [0,L−1] là một hàm rời rạc p(rk)=nk/n . Trong đó nk là số pixel có mức xám thứ rk, n là tổng số pixel trong ảnh và k=0,1,2....L−1. Do đó P(rk) cho một xấp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 xỉ xác suất xảy ra mức xám rk. Vẽ hàm này với tất cả các gia trị của k sẽ biểu diễn khái quát sự xuất hiện các mức xám của một ảnh. Chúng ta cũng có thể thề hiện lược đồ mức xám của ảnh thông qua tần suất xuất hiện mỗi mức xám qua hệ tọa độ vuông góc xOy. Trong đó, trục hoành biểu diễn số mức xám từ 0 đến N (số bit của ảnh xám). Trục tung biểu diễn số pixel của mỗi mức xám. Hình 1.3. Lược đồ xám của ảnh 1.1.2.3. Một số ứng dụng trong xử lý ảnh Như đã nói ở trên, các 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 tóan 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). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 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. Hình 1.4 Ảnh nhận được từ vệ tinh dùng trong khí tượng học 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ự đóan 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. Ảnh chụp từ vệ tinh có thể thu được thông qua các thiết bị ghi hình cảm nhận được tia sáng quang học ( 450 520 nm λ= − ), hoặc tia hồng ngoại ( 760 900 nm λ= − ). Trên hình 1.5a và 1.5b lần lượt là ảnh bề mặt trái đất nhận được từ 2 ống ghi hình nói trên, dễ dàng nhận thấy sự khác biệt rõ ràng giữa hai ảnh. Đặc biệt trên ảnh 1.3b, hình con sông được tách biệt rất rõ ràng so với vùng ảnh hai bên bờ. Thiết bị thu hình nhạy cảm với vật thể bức xạ các tia Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 trong miền hồng ngoại sẽ cho ra những bức ảnh trong đó vật thể có nhiệt độ thấp sẽ được phân biệt rõ ràng so với vật thể có nhiệt độ cao hơn. Như vậy việc lựa chọn các thiết bị ghi hình khác nhau sẽ tạo ra ảnh có đặc tính khác nhau, tùy thuộc vào mục đích sử dụng trong các lĩnh vực khoa học cụ th