Luận văn 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ể . 1.5a 1.5b Hình 1.5 - Ảnh bề mặt trái đất thu được từ hai camera khác nhau Xử lý ảnh còn đượ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. 1.1.2.4. Một số khái niệm, định nghĩa trong xử lý video [9] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 * Khung hình (frame) Một đoạn video gồm nhiều ảnh tĩnh đặt liên tiếp nhau tạo nên chuyển động trong phim. Một khung hình là một ảnh tĩnh đó. Ví dụ: Khung hình i Khung hình i + 1 Hình 1.6. Các khung hình Để đoạn video có thể tạo cảm giác chuyển động, các khung hình phải được quay với tốc độ phù hợp. Vì mắt người chỉ có thể nhận được 24 hình/giây, nên nếu như trong một giây, lần lượt 24 hình hoặc nhiều hơn được phát thì mắt sẽ không nhận ra được sự rời rạc giữa những khung hình, mà chỉ thấy những cảnh liên tục. Có nhiều hệ video và mỗi hệ có tốc độ quay khác nhau như : NTSC 30 hình/giây, PAL 24 hình/giây, SECAM 29.99 hình/giây. Khung hình là đơn vị cơ bản nhất của dữ liệu video. Theo chuẩn của hệ NTSC thì một giây có 30 khung hình, vậy một phút có 1800 khung hình, một giờ có 60x1800 = 108000 khung hình. Có thể thấy rằng số lượng khung hình cho một đoạn video thường là rất lớn, cần phải có một đơn vị cấp cao hơn cho video số. * Không gian màu Một không gian màu là một mô hình đại diện cho màu về mặt giá trị độ sáng; một không gian màu xác định bao nhiêu thông tin màu được thể hiện. Nó định nghĩa không gian 1,2,3, hoặc 4 chiều mà mỗi chiều của nó, còn gọi là thành phần, đại diện cho những giá trị độ sáng. Một thành phần màu còn được gọi là một kênh màu. Mỗi điểm ảnh trong ảnh có thể được đại Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 diện bởi một điểm trong không gian màu 3 chiều. Những không gian màu thường được dùng để bao gồm RGB, CMY, Munsell, CIE l*a*b*, CIE L*u*v*, HSV, HSL. Cho đến nay vẫn chưa có sự thống nhất không gian nào là tốt nhất. Sau đây là một số không gian màu thường gặp - Không gian độ xám Không gian độ xám chỉ có một thành phần, biến đổi từ đen đến trắng, như trong hình. Không gian độ xám được dùng chủ yếu trong việc hiển thị và in ấn trắng đen và độ xám. Hình 1.7. Không gian màu độ xám - Không gian màu RGB Không gian RGB là không gian màu được sử dụng rộng rãi trong việc hiển thị hình ảnh. Ý tưởng tạo ra không gian màu RGB đến từ cái cách mà mắt con người hoạt động. Nó có những cơ quan cảm nhận để phát hiện ra 3 màu khác nhau: đỏ(red), lục (green), lam (blue). Không gian màu RGB cũng gồm có 3 thành phần màu: Red, Green, và Blue. Những thành phần này được gọi là màu gốc để cộng vào, vì mỗi màu được tạo nên bằng cách cộng thêm các phần tử vào màu đen(0,0,0). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Hình 1.8. Không gian RGB Hình 1.9. Không gian RGB Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 Hình 1.10. Không gian RGB - Không gian màu CMY Không gian CMY được dùng chủ yếu trong in ấn. CMY là viết tắt của Cyan-Magenta-Yellow (màu lục lam, màu đỏ tươi, màu vàng), đó là ba màu chính tương ứng với ba màu mực in. Chúng được gọi là những màu gốc để trừ, vì mỗi màu trong không gian CMY được tạo ra thông qua việc hấp thu độ sáng. Cyan hấp thu sự chiếu sáng của màu đỏ, Magenta hấp thu màu xanh lục, Yellow hấp thu màu xanh dương. Hình 1.11. Không gian CMY Mối quan hệ giữa RGB và CMY : C = 1 – R M = 1 – G Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 Y = 1 - B - Không gian màu HSV Mô hình HSV(Hue, Saturation, Value), còn gọi là HSB (Hue, Saturation, Brightness) định nghĩa một không gian màu gồm có 3 thành phần tạo nên : Hue, loại màu (chẳng hạn màu đỏ, xanh, hay vàng) Có giá trị từ 0 - 360 hoặc từ 0 - 2đ Saturation, độ thuần khiết của màu Có giá trị từ 0 – 100%, thường được chuẩn hoá về 0 – 1. Độ thuần khiết của một màu càng thấp, độ xám của màu đó càng nhiều và màu đó càng mờ. Value, độ sáng của màu Có giá trị từ 0 – 100%, thường được chuẩn hóa về 0 – 1. Mô hình HSV được tạo ra từ nãm 1978 bởi Alvy Ray Smith. Nó là một phép biến đổ i phi tuyến của không gian màu RGB. Mô hình HSV giúp tách bạch màu (H, S) và độ sáng (V), phù hợp với cảm nhận của con người. 1.1.2.5. Lược đồ màu (Color Histogram) * Định nghĩa Lược đồ màu của ảnh cho biết sự phân bố của các màu trong ảnh. n in iH ][ ][  Trong đó : i là một bin màu, nếu ảnh độ xám thì i[0,255] , nếu ảnh màu RGB thì i [0,224 ] n[i] : số điểm ảnh có giá trị màu là i n : tổng số điểm ảnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Hình 1.12. Lược đồ màu ứng với frame Hình 1.13. Mắt người không nhạy cảm với sự thay đổi màu sắc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 Để cải tiến phù hợp cho việc ứng dụng trong tìm kiếm, các màu trong không gian màu HSV được định lượng trước khi tính lược đồ màu. Có nhiều cách định lượng, một trong những cách đó là chia Hue thành 18 vùng, chia Saturation thành 3 vùng chia Value thành 3 vùng Khi đó, tổng số màu bằng HxSxI = 162 màu, chi phí tính toán và lư u trữ giảm đi rất nhiều, và lược đồ màu này rất thích hợp cho việc truy tìm thông tin thị giác. Hình 1.14. Các màu đã được định lượng trong không gian HSV * Ý nghĩa của lược đồ màu Đối với một màu ci, Hci(I) thể hiện số điểm ảnh có màu ci trong ảnh I. Nói cách khác, với mỗi điểm ảnh trong ảnh I, Hci(I) thể hiện xác suất điểm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 ảnh đó có màu là ci. Không có mang thông tin về không gian. * Đánh giá ưu điểm, khuyết điểm Ưu điểm - Tính toán lược đồ màu ít tốn chi phí, đơn giản, nhanh chóng. - Lược đồ màu bất biến đối với một số phép biến đổi hình học như phép biến đổi Affine : tịnh tiến, xoay, sự co, giãn. Khuyết điểm Lược đồ màu chỉ xét phân bố toàn cục về màu của ảnh mà không xét đến yếu tố cục bộ về vị trí, làm mất thông tin về quan hệ không gian giữa các màu. Dẫn đến việc có thể có nhiều ảnh khác nhau nhưng lại có cùng lược đồ màu Ứng dụng Được ứng dụng nhiều trong việc phân đoạn video và truy tìm thông tin thị giác. 1.1.2.6. Lược đồ tương quan màu (Color Correlogram) * Giới thiệu lược đồ tương quan màu Quan sát thấy rằng lược đồ màu thiếu thông tin về cách mà màu sắc được phân bố theo không gian, Một đặc trưng mới được giới thiệu gọi là lược đồ tương quan màu. Lược đồ tương quan màu hứa hẹn mô tả không chỉ là phân phối màu của các điểm ảnh mà còn là sự tương quan về không quan giữa các cặp màu. * Tính lược đồ tương quan màu Gọi [D] là tập gồm D khoảng cách d1 , d 2 ,..., d D được đo bằng độ đo L . Lược đồ tương quan màu của ảnh I được xác định với cặp màu ci , c j và khoảng cách d như sau: ]|||[Pr)( 212 , )( , 21 dppIpI Lc IpIp d cc j c ji    Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 Trong đó I là ảnh, kích thước MxN (Điểm ảnh), I c  p  I | Ip c, lược đồ tương quan màu thể hiện xác suất cặp điểm ảnh bất kỳ p1và p2 chịu sự ràng buộc về màu ( p1 có màu ci, p2 có màu c j ) và vị trí ( p1  p2 |L  d ). * Lược đồ tự tương quan màu Nếu chúng ta xét đến tất cả sự kết hợp có thể có của các cặp màu, kích thước của lược đồ tương quan màu sẽ rất lớn, hơn nữa, thời gian tính toán sẽ lâu. Do đó, một phiên bản đơn giản hơn được sử dụng, gọi là lược đồ tự tương quan màu. Lược đồ này chỉ quan tâm đến sự tương quan về không gian giữa những màu giống nhau và do đó giảm được số chiều và chi phí tính toán. Lược đồ tự tương quan màu được xác định như sau: )()( )(, )( II dcc d c   c ( d) (I ) là lược đồ tự tương quan màu của ảnh I ứng với màu c và khoảng cách d. * Ứng dụng - Dùng trong việc phân đoạn video - Tạo chỉ mục và so sánh ảnh - Định vị đối tượng, theo vết đối tượng So với lược đồ màu, lược đồ tự tương quan màu cho những kết quả truy tìm tốt hơn nhưng tốn chi phí nhiều hơn. 1.1.2.7. Đặc trưng chuyển động (Motion) * Giới thiệu Chuyển động là một trong những đặc trưng của dữ liệu video. Đây là một đặc trưng nổi bật của video mà ảnh tĩnh không có. Đặc trưng chuyển động được sử dụng rất rộng rãi trong các nghiên cứu cũng như cài đặt ứng dụng xử lý video số. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Hình 1.15. Đặc trưng chuyển động * Lược đồ chuyển động Nếu như lược đồ màu thể hiện sự phân phối màu trong ảnh thì lược đồ chuyển động cho thấy sự phân phối chuyển động của các khung hình liên tiếp. Sự phân phối này được thể hiện dưới dạng các góc chuyển động. - Thuật toán tính lược đồ chuyển động Chia khung hình thành n khối điểm ảnh, và định lượng các góc từ 0 đến 360 độ thành 8 phần : 0o-44o, 45o-89o,…, 315o-359o. Bước 1: khởi động mảng các góc đã định lượng : H [i] 0 , với i từ 0 đến 7. Bước 2: Xét một khối điểm ảnh của khung hình hiện tại, tính độ dịch chuyển của nó bằng cách : trong khung hình tiếp theo, tìm khối có sự khác biệt đặc trưng nhỏ nhất so với khối đang xét và sự khác biệt này cũng nhỏ hơn một ngưỡng định trước. Mục đích của bước này là để xem khối này dịch chuyển đến vị trí nào. Nếu không tìm thấy thì xem như khối điểm ảnh này không di chuyển. Bước 3 : Sau khi tính độ dịch chuyển, dễ dàng tính được góc dịch chuyển của khối và định lượng góc đó về một giá trị a, a nằm trong khoảng từ 0 đến 7. Bước 4 : tăng giá trị của H [a] H [a] 1 . Quay lại bước 2 cho đến khi tính hết tất cả các khối điểm ảnh của khung hình. ảnh tại vị trí điểm ảnh đang xét. Lặp lại bước 2 cho đến khi tính hết các điểm ảnh trong khung hình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Sau khi tính toán cho tất cả điểm ảnh trong khung hình, ta có được 2 ảnh chuyển động của khung hình theo 2 phương . - Ý nghĩa Ảnh chuyển động cho biết độ lớn chuyển động theo 2 phương của mỗi điểm ảnh của khung hình. Tại vị trí nào đó mà ảnh chuyển động có giá trị lớn thì điểm ảnh đó chuyển động càng nhiều. 1.1.2.8. Các bước thao tác với file video [1] AVI là chuẩn video thường được tích hợp trong các thư viện của các môi trường lập trình. Để xử lý video, cần có các thao tác cơ bản để chuyển về xử lý ảnh các khung hình (các frames). Bƣớc 1: Mở và đóng thƣ viện Trước mọi thao tác với file AVI, chúng ta phải mở thư viện: AVIFileInit( ) Hàm này không cần tham số, có nhiệm vụ khởi động thư viện cung cấp các hàm thao tác với file AVI. (Đó là thư viện vfw32.lib, được khai báo trong file vfw.h). Sau tất cả các thao tác bạn phải nhớ đóng thư viện đã mở lúc đầu, chỉ bằng lệnh: AVIFileExit( ) Nếu thiếu bất cứ hàm nào, dù là mở hay đóng thư viện thì trình biên dịch đều sẽ thông báo lỗi. Bƣớc 2: Mở và đóng file AVI để thao tác: Sau khi mở thư viện, bạn phải mở file AVI bạn định thao tác: AVIFileOpen(PAVIFILE* ppfile, LPCSTR fname, UINT mode, CLSID pclsidHandler) Thực chất, hàm này tạo ra một vùng đệm chứa con trỏ trỏ đến file có tên là fname cần mở. Và ppfile là con trỏ trỏ đến vùng bộ đệm đó. Tham số Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 mode quy định kiểu mở file; chẳng hạn OF_CREATE để tạo mới, OF_READ để đọc, OF_WRITE để ghi …. Tham số cuối dùng là NULL. Trước khi đóng thư viện, bạn phải đóng file AVI đã mở, bằng cách dùng hàm: AVIFileRelease(PAVIFILE pfile) Trong đó, pfile là con trỏ trỏ đến file cần đóng. Bƣớc 3: Mở dòng dữ liệu hình ảnh hay âm thanh trong file AVI đã mở ra để thao tác: AVIFileGetStream(PAVIFILE pfile, PAVISTREAM * ppavi, DWORD fccType, LONG lParam) Trong đó, pfile là con trỏ đến file đã mở; ppavi trỏ đến dòng dữ liệu kết quả; fccType là loại dòng dữ liệu chọn để mở, là streamtypeAUDIO nếu là tiếng và streamtypeVIDEO nếu là hình,…lParam đếm số loại dòng được mở, là 0 nếu chỉ thao tác với một loại dòng dữ liệu. Sau các thao tác với dòng dữ liệu này, bạn nhớ phải đóng nó lại: AVIStreamRelease(PAVITREAM pavi). Bƣớc 4: Trƣờng hợp thao tác với dữ liệu hình của phim Chuẩn bị cho thao tác với khung hình (frames): AVIStreamGetFrameOpen(PAVISTREAMpavi,LPBITMAPINFOHEADER lpbiWanted) Trong đó pavi trỏ đến dòng dữ liệu đã mở, lpbiWanted là con trỏ trỏ đến cấu trúc mong muốn của hình ảnh, ta dùng NULL để sử dụng cấu trúc mặc định. Hàm này trả về đối tượng có kiểu PGETFRAME để dùng cho bước 5. Sau khi thao tác với các frame rồi, phải gọi hàm : AVIStreamGetFrameClose(PGETFRAME pget) Bƣớc 5: Thao tác với frame Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Dùng hàm AVIStreamGetFrame(PGETFRAME pget, LONG lpos) Hàm này trả về con trỏ trỏ đến dữ liệu của frame thứ lpos. Dữ liệu đó có kiểu là DIB đã định khối. Thực hiện các thao tác mong muốn. 1.2. Độ đo tƣơng tự trong xử lý ảnh[3] Hiện nay trên thế giới có rất nhiều phương tiện dùng để thu thập thông tin và lưu dưới dạng số hoá. Trong khi lưu trữ các thông tin này người sử dụng gặp phải vấn đề với quá nhiều hình ảnh khác nhau và vấn đề quản lý những hình ảnh này. Rất nhiều các nhà lập trình đã tiếp cận và tạo ra hệ thống để quản lý một cách có hiệu quả nhất tức là dùng bộ nhớ thị giác của máy tính để lưu trữ và đối sánh những hình ảnh này. Nghiên cứu “sự tương tự” (thường ở dạng đối ngẫu của nó là “khoảng cách”) thuộc phạm vi toán học, chẳng hạn trong lý thuyết tôpô và xấp xỉ; nhưng trong khoa học máy tính và các ứng dụng máy tính có phần khác. Trong khoa học máy tính, phép tính xấp xỉ thường được sử dụng theo một lối không có tính hệ thống (non-systematic) và không theo thể thức (ad-hoc). Trong ngữ cảnh này, khái niệm “sự tương tự” xuất hiện ở nhiều dạng, diễn xuất, và nhiều ứng dụng. Khái niệm “sự tương tự” có nhiều dạng khác nhau. Bất chấp những khác biệt, chúng đều có điểm chung: “sự tương tự” được sử dụng để so sánh hai (hay nhiều) đối tượng, hai hoàn cảnh, hai vấn đề, v.v… với nhiều nguyên do khác nhau. Luôn có mục đích nào đó với một phép so sánh như thế, bởi vì một hành động tiếp sau đó được thực hiện và cuối cùng thì một vấn đề nào đó phải được giải quyết. Vì lý do đó, hai đối tượng được đem so sánh giữ những vai trò khác nhau. Đối tượng thứ nhất đang được xem xét và được gọi là vấn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 đề (problem). Đối tượng thứ hai là đã biết và đã lưu; thường được gọi là bản mẫu (prototype) hay tình huống (case). - Trong diễn xuất hình ảnh (Image Interpretation), các hình ảnh được diễn xuất theo ý nghĩa của chúng và chúng được so sánh với nhau. Ví dụ, một ảnh y khoa thực tế và một ảnh không có bệnh lý nào đó được so sánh với nhau; độ tương tự giữa những ảnh này được sử dụng để cho biết ảnh thực kia có chứa bệnh lý hay không. Xác minh hình ảnh (Image Identification) cũng thuộc về lĩnh vực này. - Trong tâm lý học nhận thức và xã hội (Cognitive and Social Psychology), “sự tương tự” là cái gì đó chủ quan; ám chỉ thái độ, giá trị, sở thích, và cá tính giữa những con người tương xứng mức độ nào. Có nhiều dạng mô hình về sự tương tự trong tâm lý học, bốn mô hình nổi bật là hình học (geometric), đặc tính (featural), dựa trên canh lề (alignment-based), và biến đổi (transformational). - Trong lĩnh vực an ninh, quốc phòng để xác định đối tượng ảnh khi muốn xác định vân tay, kiểm tra những băng đĩa mang những nội dung cần kiểm soát... Độ đo tương tự là một trong những phương pháp tốt để máy tính phân biệt được các hình ảnh qua nội dung của chúng. Thông thường hệ thống CBIR(content-based image retrieval) sẽ truy vấn hình ảnh bằng phương pháp đo tương tự dựa trên các chức năng, việc xác định nó có thể dưới nhiều hình thức như phát hiện biên, màu sắc, vị trí điểm ảnh… các phương pháp như histogram, màu sắc và phân tích histogram dòng cột sử dụng biểu đồ để xác định độ tương tự. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Chƣơng 2: MỘT SỐ PHƢƠNG PHÁP XÁC ĐỊNH ĐỘ ĐO TƢƠNG TỰ 2.1. Độ đo dựa trên khoảng cách 2.1.1. Độ đo khoảng cách min – max Được thực hiện dựa trên ý tưởng lấy phần giao của hai lược đồ cần so sánh, ta sẽ được một lược đồ, tính tổng các giá trị có được từ lược đồ này cho ta được độ đo min – max Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi K bin Intersection (h(I), h(M) =   K j 1 h(M)[j]}{h(I)[j],min Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi K bin Intersection (h(I), h(M) =   K j 1 h(M)[j]}{h(I)[j],max Matching(h(I),h(M)) =        ii iMhiIh MhIhtionInter ])[(,])[(max ))(),((sec 2.1.2. Độ đo khoảng cách Euclid Đây là cách tính khoảng cách Euclid thông thường giữa các K bin: Intersection (h(I), h(M) =   K j 1 2h(M))-(h(I) Hoặc có thể là: Intersection (h(I), h(M) =    K j MhIh 1 )()( 2.1.3. Độ đo khoảng cách toàn phương: Intersection (h(I), h(M) =     K j K j ij jhihajhih 1 1 )]()([)()([ 2.2. Độ đo sử dụng trọng số 2.2.1. Độ đo có trọng số: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 dhist(I,Q) = (h(I) – h(Q)) T A(h(I) – h(Q)) trong đó, h(I) và h(Q) là những lược đồ tương ứng của ảnh I và Q và A là ma trân đồng dạng K x K. Trong ma trận này, những màu mà rất giống nhay thì gần với giá trị một còn những màu khác nhau thì sẽ cí giá trị gần với không. 2.2.2. Độ đo hỗn hợp Một trong các độ đo hỗn hợp (độ đo MSM) được đưa ra bởi Goodall [1]. Để tính độ đo giống nhau giữa các đối tượng, đầu tiên ta tính độ đo cho từng thuộc tính, sau đó kết hợp lại. Dưới đây ta sẽ lần lượt xét các độ đo cho từng loại thuộc tính liên tục và rời rạc. Ngoài ra, ta cũng xét độ đo cho loại thuộc tính thứ tự trên thuộc tính rời rạc. 2.2.2.1. Thuộc tính rời rạc Loại thuộc tính đầu tiên mà ta xét là thuộc tính rời rạc. Các giá trị khác nhau thuộc tính không thể được so sánh. Ta coi cặp các giá trị khác nhau có độ giống nhau bằng 0; cặp các giá trị trùng nhau có độ giống nhau khác 0 và phụ thuộc vào xác suất xuất hiện của cặp giá trị đó. Cặp giá trị trùng nhau có xác suất xuất hiện nhỏ hơn sẽ có độ giống nhau lớn hơn. Kí hiệu Vi là các giá trị khác nhau của thuộc tính. Xác suất xuất hiện của các giá trị này là 1,1, 1    n i ii pnip . Kí hiệu Sij là độ giống nhau của cặp giá trị Vi và Vj, ta có: 0 0 ij ij i j S i j S       ngoài ra,      i k ij kli j k l p p S S       Gọi Pij là xác suất xuất hiện một cặp giá trị có độ giống nhau lớn hơn cặp (Vi, Vj). Dễ thấy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 2 , 1,          k k Q ij p i j P i j trong đó   : k iQ k p p  Từ đó, suy ra 21 , 1 0,             k k Q ij ij p i j S P i j với Q được xác định theo công thức ở trên. Trong thực tế, các giá trị xác suất pi là không biết trước nhưng ta có thể xấp xỉ các giá trị này bằng tần suất xuất hiện của chúng trong tập mẫu. Gọi m là số lượng các phần tử trong tập mẫu và fi là tần suất của giá trị Vi, độ đo giống nhau có thể được tính xấp xỉ bởi     1 1 , 1 0,            k k ij k Q f f i j S m m i j trong đó   : k iQ k f f  2.2.2.2. Thuộc tính có thứ tự Trong trường hợp này, ta cần phải tính tới tính có thứ tự trong độ đo giống nhau. Do có tính thứ tự nên thông thường một cặp giá trị sẽ có độ giống nhau nhỏ hơn so với các cặp giá trị nằm giữa chúng. Ví dụ, ta nói cặp (B, C) sẽ có độ giống nhau lớn hơn cặp (A, C) và (B, E). Tuy nhiên, ta không thể có sự so sánh như vậy với hai cặp (A, C) và (B, E). Trong trường hợp này, chúng ta lại sử dụng đến xác suất xuất hiện của các giá trị. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Giả sử các giá trị của thuộc tính là 1 2, ,..., nV V V . Theo cách hiểu thông thường và lập luận ở trên, ta có      i k ij kli j k l p p S S           ij kli j k l S S        ij ik jk iki j k S S S S      và       j l t t ij kl t i t k i j k l p X S S                       j l t t ij kl t i t k i j k l p X S S                 Xác suất ijP để xuất hiện một cặp có độ giống nhau hơn cặp  ,i jV V là 2 ,ij k k Q P p i j    với   : k iQ k p p  và 1 2 1 1 1 2 , n n ij k k l k k l k P p p p i j          trong đó  là số thoả mãn 1j t t t t k t i t k p p p           Trong trường hợp phải tính xấp xỉ, ta sử dụng công thức           1 1 1 1 1 , 1 1 2 , 1 1                       i i k Q ij n n i i k l k k l k f f i j m m P f f f f i j m m m m 2.2.2.3. Thuộc tính liên tục Với thuộc tính liên tục, ta sẽ sử dụng khoảng cách – trị tuyệt đối của hiệu của hai giá trị – làm tiêu chuẩn chính trong việc đo độ giống nhau. Cặp của hai giá trị trùng nhau thì có độ giống nhau lớn hơn cặp của hai giá trị khác Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 nhau; cặp có khoảng cách nhỏ hơn sẽ giống nhau hơn cặp có khoảng cách lớn hơn. Và khi các cặp có cùng khoảng cách ta sẽ sử dụng đến xác suất. Ta có:     i j k l ij kl j l i j k l t t ij kl t i t k j l i j k l t t ij kl t i t k V V V V S S V V V V p p S S V V V V p p S S                                      Tương tự, xác suất Pij là 2 2 i jk i i t i Q t T P p p p              trong đó       : 1i jQ i j k p p i n         và      :                                       t i k j k ti t i k j u u u j u i V V V V T t i t n V V V V p p Công thức để tính gần đúng độ giống nhau trong trường hợp này:     1 1 2 1 i jk i i i t i Q t T P f f f f m m                 2.2.2.4. Kết hợp độ đo của các thuộc tính Trong các phần trên ta đã xét độ giống nhau cho từng thuộc tính riêng rẽ. Độ đo giống nhau cho cặp hai đối tượng sẽ được kết hợp từ các độ đo này. Để có thể kết hợp được, ta phải giả sử là các giá trị của các thuộc tính của một đối tượng là độc lập với nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Kí hiệu Og và Oh là hai đối tượng cần tính độ giống nhau và k ghP là xác suất xuất hiện cặp giá trị của thuộc tính k có độ giống nhau lớn hơn cặp  ,k kg hv v . Ta định nghĩa quan hệ giữa hai đối tượng như sau: 1 1      t t k k gh ij gh ij k k P P S S trong đó t là số lượng thuộc tính và S là kí hiệu chỉ độ giống nhau giữa hai đối tượng. Nếu kí hiệu 1 gh ghP S là xác suất xuất hiện một cặp đối tượng có độ giống nhau lớn hơn cặp (Og, Oh), thì tương tự như đối với thuộc tính riêng rẽ, ta có: 1 1   t t k l gh i j Q k l p pP trong đó k ip là xác suất xuất hiện giá trị thứ i của thuộc tính thứ k và Q là tập tất cả các cặp đối tượng (Oi, Oj) thoả mãn 1 1    t t k k ij gh k k P P Việc tính chính xác S theo công thức trên yêu cầu số lượng tính toán rất lớn và trong thực tế người ta thường tính xấp xỉ nó bằng các phân bố của Fisher và Lancaster như sau  2 22 0 1 2 !       i t i e i P trong đó 1d ct t t   và 2 2 2 d c    , với 2 1 2 ln     ct k c k P cho các thuộc tính liên tục (phân bố Fisher) và ' ' 2 ' 1 ln ln 2 1          dt k k k k d k k k P P P P P P cho thuộc tính rời rạc (phân bố Lancaster). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 2.2.2.5. Thuật toán nhanh cho thuộc tính liên tục Để tính độ đo giống nhau trong trường hợp thuộc tính liên tục, ta cần phải duyệt qua các xác suất xuất hiện của giá trị của thuộc tính. Do đó, độ phức tạp tính toán trong trường hợp này là ( )n , với n là số lượng giá trị. Trong trường hợp thuộc tính liên tục (số), nếu tính trực tiếp theo công thức MSM như C. Li và G. Biswas [2] đề nghị thì độ phức tạp tính toán trong trường hợp xấu nhất là 2( )n . Chúng tôi đã đề xuất cách tính gián tiếp độ đo cho kết quả hoàn toàn trùng khớp những chỉ với độ phức tạp tính toán là ( )n như nêu trong [3, 4, 5]. Ý tưởng chính của phương pháp này là không tính trực tiếp độ đo theo công thức 2 2 i jk i i t i Q t T P p p p              trong đó T là tập các chỉ số t ( k t n  ) thoả mãn t i k jV V V V   hoặc   k t t i k j u u u j u i V V V V p p               mà tính gián tiếp thông qua 1jk jkS P  . Ta chỉ cần quan tâm đến trường hợp j k , bời vì khi j = k thì 2 jk i i Q P p   , với   : i kQ i p p  và tính Pjk với độ phức tạp tuyến tính. Dễ thấy, 1 1 2 , i n jk jk i t i t T S P p p j k              với iT là tập      : k t i t i k j t i k j u u u j u i T t V V V V V V V V p p i t n                                  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Ta có thể viết iT ở dạng đơn giản hơn như sau   0:i i iT t t t n T    trong đó it là giá trị nhỏ nhất còn thoả mãn t i k jV V V V   và 0 iT là tập chỉ số t thoả mãn   k t t i k j u u u j u i V V V V p p               . Chú ý rằng 0 iT hoặc là rỗng hoặc chỉ có một phần tử. Công thức tính Sjk còn có thể biến đổi như sau   1 2 1 , n jk i i i S p s j k     trong đó, 0 1 1 i it T i t t s p      Tính Sjk theo công thức này ta có thể tận dụng si tính được trong bước trước. Dưới đây là thuật toán với độ phức tạp tuyến tính. Một số kí hiệu trong thuật toán sij: độ đo giống nhau của cặp giá trị (Vi, Vj). sumij: tổng các tần xuất từ i tới j. dij: trị tuyệt đối của hai giá trị Vi và Vj. beforek: tổng các tần xuất từ 1 tới k – 1. sumt: tổng các tần xuất 1 tới t. f[k]: tần xuất của giá trị thứ k. n: số lượng giá trị của thuộc tính. Thuật toán (cho trường hợp i j ) t = 1; beforek = 0.0; sumt = 0.0; sij = 0.0; sumij = 0.0; dij = abs(v[j] – v[i]); for k = i to j do sumij = sumij + f[k]; for k = 1 to n do { Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 if (v[k] + dij <= v[n]) { if (k > 1) beforek = beforek + f[k-1]; while (t <= n and abs(v[t] – v[k] <= dij)) { sumt = sumt + f[t]; t = t + 1; } sij = sij + 2 * f[k] * (1 – sumt); if (abs(v[t – 1] – v[k]) = dij and sumt – beforek <= dij) sij = sij + 2 * fk * f[t – 1]; } } 2.2.2.6. Thuật toán nhanh cho thuộc tính có thứ tự Áp dụng phương pháp tương tự như đối với thuộc tính liên tục, ta cũng có thể tính độ đo giống nhau cho thuộc tính có thứ tự với độ phức tạp tuyến tính. Trước hết ta viết lại biểu thức tính Pij dưới dạng 1 2 1 1 1 1 2 1 1 1 2 1 2 2 2 n n ij k k l k k l k n n k k l k l k n n k l k k l k P p p p p p p p p p p p                                         trong đó  thoả mãn   1 1 j t t t t k t i t k k p p p                     . Ta có thể viết lại 1 2 n ij k l k k l k P p p p             với  bây giờ có thể nhận thêm giá trị k. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 Sử dụng các kí hiệu như trên, thuật toán tính nhanh cho thuộc tính có thứ tự được nêu như sau: t = 1; beforek = 0.0; sumt = 0.0; sumij = 0.0; pij = 0.0; for k = i to j do sumij = sumij + f[k]; for k = 1 to n do { if (k > 1) beforek = beforek + f[k – 1]; BOOL stop = FALSE; while (t <= n and not stop) { if (sumt – beforek <= sumij and sumt + f[t] – beforek > sumij) stop = TRUE; else { sumt = sumt + f[t]; t = t + 1; } } pij = pij + f[k] * (2 * (sumt - beforek) – f[k]); } 2.3. Độ đo tƣơng tự có thể học (Trainable similarity measure)[4] Đầu tiên, độ đo tương tự Sr(I, J) được xác định dựa trên việc tính toán hệ số tương quan giữa 2 ảnh cùng kích thước I và J:               i i ii i ii r JJII JJII JIS 22 , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 Trong đó, ký hiệu Ii và Ji biểu diễn cường độ của pixel thứ i tương ứng của các ảnh I và J biểu diễn giá trị trung bình tương ứng của các cường độ của ảnh. Độ tương tự S(I, J, R) được đề nghị dựa trên sự tương xứng cục bộ của ảnh trong tập hợp các vùng ảnh R. Mỗi vùng ảnh r  R được định nghĩa trong hệ tọa độ của ảnh I. Độ tương tự cục bộ s(I, J, r) giữa các vùng ảnh tương ứng r(I) và r(J) có thể được xác định, chẳng hạn, theo hệ số tương quan. Độ tương tự tổng thể S(I, J, R) là một hàm của tập hợp các độ tương tự cục bộ của các vùng r. Ở đây, để làm tăng tính chính xác của độ đo tương tự tổng thể trước các sai lệch cục bộ chúng ta sử dụng một điều kiện số học (arithmetic mean):       R j jmean rJIs R RJIS 1 ,, 1 ,, Tập hợp các vùng R được xác định cụ thể đối với mỗi nguyên mẫu (prototype) trong suốt quá trịnh học tương ứng với tập dữ liệu Tr = {(I1, w(I1)), … , (IN, w(IN))} với N ảnh, với w(I) biểu diến một lớp của ảnh I. Quá trình học độ đo tương tự đối với một ảnh nguyên mẫu (prototype image) Pr như sau: bắt đầu từ một tập hợp các vùng có thể chấp nhận Rinit , một tập con R được chọn tùy ý theo tính dễ phân tách (separability) của lớp (class) của đối tượng nguyễn mẫu (prototype object) w(Pr) từ tất cả các lớp liên quan trong tập Tr. Tính dễ phân tách tiêu chuẩn được chấp nhận là:     22 2 ˆ ˆˆ ,, NTT NTT rr RPTC      Sự tách biệt giữa các đối tượng học (training object) mục tiêu (target) và không mục tiêu (non-target) dựa trên độ tương tự S(I, Pr, R).Các ký hiệu T và NT biểu diễn tập hợp của đối tượng học mục tiêu và không mục tiêu: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43          rirj riri PwIwTINT PwIwTIT   : : Ký hiệu  NTT  ˆˆ và  22 ˆˆ NTT  biểu diễn điều kiện mean và sự sai khác của giá trị tương tự S(Ii, Pr, R), Ii  T (S(Ij, Pr, R), Ij  NT). 2.4. Độ đo dựa trên Histogram [12] 2.4.1. Giới thiệu Một trong những công cụ đơn giản và hữu ích nhất cho xử lý ảnh số là lược đồ mức xám. Trong khi lược đồ mức xám của một ảnh bất kỳ chứa một lượng thông tin đáng kể, thì dĩ nhiên các loại ảnh cũng hoàn toàn được xác định rõ bởi các lược đồ mức xám của chúng. Tính toán lược đồ mức xám cũng đơn giản và có thể thực hiện khi một ảnh được sao chép từ nơi này sang nơi khác. 2.4.2. Định nghĩa Lược đồ mức xám là một hàm cho thấy, cho mỗi mức xám, số lượng điểm ảnh thuộc một mức xám có trong một ảnh. Trục hoành là mức xám và trục tung là tần suất xuất hiện (số các điểm ảnh). Có một cách khác để định nghĩa lược đồ mức xám ví dụ dưới đây cho ta hiểu rõ hơn sự hữu ích của hàm này. Giả sử chúng ta có một ảnh liên tục được định nghĩa bởi hàm số D(x,y), hàm biến thiên chậm từ mức xám cao tại tâm đến mức xám thấp tại các điểm biên. Chúng ta có thể chọn một vài mức xám D1 và định nghĩa tập các bao quanh nối tất cả các điểm coa cùng giá trị D1 trong ảnh lại với nhau. Kết quả ta được các đường cong khép kín bao quanh các vùng, mà các mức xám trong vùng là lớn hơn hay gằng D1. Hàm diện tích ngưỡng A(D) của ảnh liên tục là khu vực được khép kín bởi tất cả các đường bao có cùng mức xám D. Bây giờ có thể xác định lược đồ mức xám như sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 )( )()( lim)( DA dD d D DDADA DH oD      Cho nên, lược đồ mức xám của ảnh liên tục là phủ định của đạo hàm hàm diện tích của nó. Dấu âm của kết quả từ thực tế là A(D) giảm trong trường hợp tăng D. Nếu ảnh được xem là biến ngẫu nhiên hai chiều, thì hàm diện tích sẽ tương ứng với hàm phân bố luỹ tích của nó và lược đồ mức xám tương ứng với hàm mật độ xác suất của nó. Với trường hợp hàm rời rạc, ta đặt D=1, khi đó biểu thức (1) trở thành )1()()(  DADADH Hàm diện tích của một ảnh số đơn thuần là số các điểm ảnh có mức xám lớn hơn hoặc bằng mức xám D bất kỳ. 2.4.3. Lược đồ mức xám hai chiều Thường thì người ta tìm cách để tạo ra các lược đồ mức xám có chiều từ hai trở lên. Đây là ích lợi đặc biệt cho ảnh màu. Các ảnh được số hoá từ ảnh hiển vi chứa tế bào bạch cầu (máu trắng) và nhiều tế bào hồng cầu. Khu vực được số hoá trong ánh sáng trắng, đỏ và lam thông qua bộ lọc màu. Lược đồ mức xám đỏ - lam (red versus blue) hai chiều của hai ảnh cuối cùng ở trạng thái thấp hơn. Lược đồ mức xám hai chiều là một hàm hai biến: mức xám trong ảnh đỏ và mức xám trong ảnh lam. Giá trị tại toạ độ (DR,DB) của nó là số cặp điểm ảnh tương ứng có mức xám DR trong ảnh đỏ và mức xám DB trong ảnh lam. Nhớ lại rằng một ảnh số đa phổ (multispectral) ví dụ như ảnh này có thể cho rằng mỗi điểm lấy mẫu chỉ có một điểm ảnh đơn, nhưng mỗi điểm ảnh lại có nhiều giá trị - trong trường hợp này là hai. Lược đồ mức xám hai chiều cho thấy sự phân bố các điểm ảnh trên cơ sở kết hợp hai mức xám. Nếu các thành phần đỏ và lam giống nhau thì lược đồ mức xám sẽ có giá trị không (zero), ngoại trừ các điểm trên đường chéo 450C. Những điểm ảnh có mức xám đỏ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 cao hơn mức xám lam và ngược lại sẽ tập trung ở trên và dưới đường chéo của lược đồ mức xám. 2.4.4. Các tính chất của lược đồ mức xám Khi một ảnh được cô đọng thành lược đồ mức xám, tất cả thông tin về không gian đều bị loại bỏ. Lược đồ mức xám chỉ rõ số các điểm ảnh có trong mỗi mức xám, nhưng khôngliên quan một chút nào đến vị trí mà những điểm ảnh đó định vị trong ảnh. Vì thế, lược đồ mức xám là duy nhất cho một ảnh bất kỳ, nhưng điều ngược lại không đúng. Các ảnh hết sức khác nhau có thể có lược đồ mức xám giống hệt nhau. Tất cả những phép toán dịch chuyển các đối tượng khắp nơi trong ảnh đều không làm ảnh hưởng đến đặc thù lược đồ mức xám. Tuy nhiên, lược đồ mức xám cũng có một vài thuộc tính hữu ích. Nếu chúng ta thay đổi các biến trong biểu thức trên và tích phân hai vế với cận từ D đến vô cùng, chúng ta nhận được hàm diện tích   )()()( DAPAdPPH D D    Nếu đặt D = 0, giả sử các mức xám không âm, ta được nh¶cña tÝch diÖn  0 )( dPPH Hoặc, trong trường hợp rời rạc    255 0 )( D NSNLDH trong đó NL và NS là số hàng và số cột tương ứng trong ảnh Nếu ảnh chứa chỉ một đối tượng xám cùng kiểu trên nền tương phản và chúng ta quy định rằng biên của đối tượng đó là đường bao định nghĩa bởi mức xám D1, khi đó    D dDDH thÓvËt tÝch diÖn)( Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 Nếu trong ảnh chứa nhiều đối tượng, thì tất cả những đường biên của chúng là đường bao tại mức xám D1, khi đó biểu thức (6) cho ta tổng diện tích tất cả các đối tượng Chuẩn hoá lược đồ mức xám bằng cách chia cho diện tích của ảnh ta được hàm mật độ xác suất (PDF) của ảnh. Một sự chuẩn hoá hàm diện tích tương tự tạo ra hàm phân bố luỹ tích (CDF) của ảnh. Lược đồ mức xám còn có tính chất hữu ích khác, trực tiếp từ định nghĩa của nó như số các điểm ảnh có trong mỗi mức xám: nếu ảnh gồm có hai miền rời nhau và đã biết lược đồ mức xám của mỗi miền, sau đó cộng hai lược đồ mức xám thành một lược đồ mức xám của toàn bộ ảnh. Hoàn toàn rõ ràng điều này có thể mở rộng cho số lượng miền rời nhau. 2.4.5. Quan hệ giữa lược đồ mức xám và ảnh Vì lược đồ mức xám của một ảnh là duy nhất, nên có khả năng nhận được lược đồ của các ảnh đơn giản mà ta đã biết dạng hàm của chúng. Mặc dù kỹ thuật này có lẽ ít khi sử dụng, nhưng nó mang lại sự hiểu biết bản chất lược đồ, và nó thiết lập cơ sở cho việc nghiên cứu sự chọn ngưỡng. Giả sử chúng ta có một ảnh của dạng hàm đã cho và chúng ta muốn tính lược đồ mức xám của nó. Chúng ta biết rằng đây là phủ định của đạo hàm đối với mức xám của hàm diện tích. Bởi thế cho nên, chúng ta có thể nhận được lược đồ nếu trước tiên chúng ta nhận được hàm diện tích từ chính sự thể hiện ảnh. Đôi khi điều này có thể được thực hiện một cách đơn giản bằng cơ sở sự quan sát. 2.4.6. Một chiều Với mục đích để cho dễ hiểu, đầu tiên chúng ta nói về trường hợp một chiều (dimension). ở đây từ “diện tích” thực tế chỉ có chiều dài, nhưng nó giải thích mối quan hệ giữa lược đồ và ảnh của nó. Xem xét xung Gauss một chiều cho bởi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47   xexD x - 2 )( Lưu ý rằng với x  0 (không âm), hàm là đơn điệu tăng (monotonic). Hơn nữa, diện tích chỉ đơn thuần là nghịch đảo của hàm ảnh. Vì thế, với giá trị x0 (không âm), chúng ta có thể giải biểu thức (15) bằng cách xem x như một hàm mức xám 0)ln()(  xDDx Là hàm diện tích đối với nửa ảnh bên phải. Bởi vì hai phần nửa ảnh đối xứng nhau, toàn bộ hàm diện tích sẽ gấp hai lần diện tích trong biểu thức (16). Lược đồ được cho bởi   )ln( 1 )ln(2)( DD D dD d DH   Và được trình bày trong hình 5-6. Lược đồ nhọn dần lên tại D = 0 bởi vì những vùng rộng của những mức xám thấp với các giá trị x dương và âm. Đỉnh nhọn nhỏ tại D = 1do ảnh có hệ số góc (slope) không tại x = 0 (chẳng hạn, xung Gauss “bằng phẳng” cục bộ chính tại đỉnh). 2.4.7. Hai chiều Thủ tục tương tự có thể mở rộng cho ảnh hai chiều bằng cách sử dụng có suy xét tính đối xứng trong ảnh. Ta có thể lấy đối xứng vòng theo cách dưới đây. Giả sử ảnh là xung Gauss đối xứng vòng tròn tâm nằm ở gốc. Hàm ảnh theo toạ độ cực cho bởi    0,0),( 2 rerD r Đường viền mức xám P không đổi là đường tròn có bán kính )ln()( pPr  Đường trên bọc kín một vùng   )ln()()( 2 PPrPA   Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Bây giờ, hàm diện tích của biểu thức (20) có thể được đạo hàm để tạo ra lược đồ P PA dD d PH   )()( Lưu ý rằng điểm có hệ số góc không tại gốc không đủ mạnh để tạo ra một đỉnh nhọn tai D = 1, như đã tạo ra đối với trường hợp một chiều. Với ảnh phức tạp hơn, lược đồ mức xám có thể nhận do sự phân vùng ảnh thành các miền rời nhau, sao cho có thể xác định được các hàm diện tích. Lược đồ mức xám của một ảnh trọn vẹn là tổng tất cả các lược đồ của các miền rời nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 CHƢƠNG 3 ỨNG DỤNG ĐỘ ĐO TƢƠNG TỰ TRONG VIỆC PHÂN LOẠI ẢNH TRONG FILE VIDEO 3.1. Giới thiệu bài toán Bài toán của chúng ta như sau: Đầu vào: - Đọc 1 file video - Đọc 1 file ảnh Đầu ra: - Kết luận về độ tương tự của file ảnh đối với một trong các frame của file video. 3.2. Cài đặt thuật toán 3.2.1. Code đọc ảnh bool ConvertToDFB(HBITMAP& hBitmap) { bool bConverted = false; BITMAP stBitmap; Input: - Ảnh - File video Tìm kiếm (Đối sánh) Output: - Kết luận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 if (GetObject(hBitmap, sizeof(stBitmap), &stBitmap) && stBitmap.bmBits) { HDC hScreen = GetDC(NULL); if (hScreen) { HBITMAP hDfb = CreateCompatibleBitmap(hScreen, stBitmap.bmWidth, stBitmap.bmHeight); if (hDfb) { // now let's ensure what we've created is a DIB. if (GetObject(hDfb, sizeof(stBitmap), &stBitmap) && !stBitmap.bmBits) { // ok, we're lucky. Now we have // to transfer the image to the DFB. HDC hMemSrc = CreateCompatibleDC(NULL); if (hMemSrc) { HGDIOBJ hOldSrc = SelectObject(hMemSrc, hBitmap); if (hOldSrc) { HDC hMemDst = CreateCompatibleDC(NULL); if (hMemDst) { HGDIOBJ hOldDst = SelectObject(hMemDst, hDfb); if (hOldDst) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 { // transfer the image using BitBlt // function. It will probably end in the // call to driver's DrvCopyBits function. if (BitBlt(hMemDst, 0, 0, stBitmap.bmWidth, stBitmap.bmHeight, hMemSrc, 0, 0, SRCCOPY)) bConverted = true; // success VERIFY(SelectObject(hMemDst, hOldDst)); } VERIFY(DeleteDC(hMemDst)); } VERIFY(SelectObject(hMemSrc, hOldSrc)); } VERIFY(DeleteDC(hMemSrc)); } } if (bConverted) { VERIFY(DeleteObject(hBitmap)); // it's no longer needed hBitmap = hDfb; } else VERIFY(DeleteObject(hDfb)); } ReleaseDC(NULL, hScreen); } Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 } return bConverted; } // This function converts the given bitmap to a DIB. // Returns true if the conversion took place, // false if the conversion either unneeded or unavailable bool ConvertToDIB(HBITMAP& hBitmap) { bool bConverted = false; BITMAP stBitmap; if (GetObject(hBitmap, sizeof(stBitmap), &stBitmap) && !stBitmap.bmBits) { // that is a DFB. Now we attempt to create // a DIB with the same sizes and pixel format. HDC hScreen = GetDC(NULL); if (hScreen) { union { BITMAPINFO stBitmapInfo; BYTE pReserveSpace[sizeof(BITMAPINFO) + 0xFF * sizeof(RGBQUAD)]; }; ZeroMemory(pReserveSpace, sizeof(pReserveSpace)); stBitmapInfo.bmiHeader.biSize = sizeof(stBitmapInfo.bmiHeader); stBitmapInfo.bmiHeader.biWidth = stBitmap.bmWidth; stBitmapInfo.bmiHeader.biHeight = stBitmap.bmHeight; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 stBitmapInfo.bmiHeader.biPlanes = 1; stBitmapInfo.bmiHeader.biBitCount = stBitmap.bmBitsPixel; stBitmapInfo.bmiHeader.biCompression = BI_RGB; if (stBitmap.bmBitsPixel <= 8) { stBitmapInfo.bmiHeader.biClrUsed = 1 << stBitmap.bmBitsPixel; // This image is paletted-managed. // Hence we have to synthesize its palette. } stBitmapInfo.bmiHeader.biClrImportant = stBitmapInfo.bmiHeader.biClrUsed; PVOID pBits; HBITMAP hDib = CreateDIBSection(hScreen, &stBitmapInfo, DIB_RGB_COLORS, &pBits, NULL, 0); if (hDib) { // ok, we're lucky. Now we have // to transfer the image to the DFB. HDC hMemSrc = CreateCompatibleDC(NULL); if (hMemSrc) { HGDIOBJ hOldSrc = SelectObject(hMemSrc, hBitmap); if (hOldSrc) { HDC hMemDst = CreateCompatibleDC(NULL); if (hMemDst) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 { HGDIOBJ hOldDst = SelectObject(hMemDst, hDib); if (hOldDst) { if (stBitmap.bmBitsPixel <= 8) { // take the DFB's palette and set it to our DIB HPALETTE hPalette = (HPALETTE) GetCurrentObject(hMemSrc, OBJ_PAL); if (hPalette) { PALETTEENTRY pPaletteEntries[0x100]; UINT nEntries = GetPaletteEntries(hPalette, 0, stBitmapInfo.bmiHeader.biClrUsed, pPaletteEntries); if (nEntries) { ASSERT(nEntries <= 0x100); for (UINT nIndex = 0; nIndex < nEntries; nIndex++) pPaletteEntries[nEntries].peFlags = 0; VERIFY(SetDIBColorTable(hMemDst, 0, nEntries, (RGBQUAD*) pPaletteEntries) == nEntries); } } } // transfer the image using BitBlt function. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 // It will probably end in the // call to driver's DrvCopyBits function. if (BitBlt(hMemDst, 0, 0, stBitmap.bmWidth, stBitmap.bmHeight, hMemSrc, 0, 0, SRCCOPY)) bConverted = true; // success VERIFY(SelectObject(hMemDst, hOldDst)); } VERIFY(DeleteDC(hMemDst)); } VERIFY(SelectObject(hMemSrc, hOldSrc)); } VERIFY(DeleteDC(hMemSrc)); } if (bConverted) { VERIFY(DeleteObject(hBitmap)); // it's no longer needed hBitmap = hDib; } else VERIFY(DeleteObject(hDib)); } ReleaseDC(NULL, hScreen); } } return bConverted; } Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 3.2.2. Code đọc và extract frame file video BOOL ExtractAVIFrames(CString szFileName) { AVIFileInit(); PAVIFILE avi; int res=AVIFileOpen(&avi, szFileName, OF_READ, NULL); if (res!=AVIERR_OK) { //an error occures if (avi!=NULL) AVIFileRelease(avi); return FALSE; } AVIFILEINFO avi_info; AVIFileInfo(avi, &avi_info, sizeof(AVIFILEINFO)); CString szFileInfo; szFileInfo.Format("Dimention: %dx%d\n" "Length: %d frames\n" "Max bytes per second: %d\n" "Samples per second: %d\n" "Streams: %d\n" "File Type: %d", avi_info.dwWidth, avi_info.dwHeight, avi_info.dwLength, avi_info.dwMaxBytesPerSec, (DWORD) (avi_info.dwRate / avi_info.dwScale), Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 avi_info.dwStreams, avi_info.szFileType); AfxMessageBox(szFileInfo, MB_ICONINFORMATION | MB_OK); PAVISTREAM pStream; res=AVIFileGetStream(avi, &pStream, streamtypeVIDEO /*video stream*/, 0 /*first stream*/); if (res!=AVIERR_OK) { if (pStream!=NULL) AVIStreamRelease(pStream); AVIFileExit(); return FALSE; } //do some task with the stream int iNumFrames; int iFirstFrame; iFirstFrame=AVIStreamStart(pStream); if (iFirstFrame==-1) { if (pStream!=NULL) AVIStreamRelease(pStream); AVIFileExit(); return FALSE; } iNumFrames=AVIStreamLength(pStream); if (iNumFrames==-1) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 { //Error getteing the number of frames inside the stream if (pStream!=NULL) AVIStreamRelease(pStream); AVIFileExit(); return FALSE; } BITMAPINFOHEADER bih; ZeroMemory(&bih, sizeof(BITMAPINFOHEADER)); bih.biBitCount=24; //24 bit per pixel bih.biClrImportant=0; bih.biClrUsed = 0; bih.biCompression = BI_RGB; bih.biPlanes = 1; bih.biSize = 40; bih.biXPelsPerMeter = 0; bih.biYPelsPerMeter = 0; //calculate total size of RGBQUAD scanlines (DWORD aligned) bih.biSizeImage = (((bih.biWidth * 3) + 3) & 0xFFFC) * bih.biHeight ; PGETFRAME pFrame; pFrame=AVIStreamGetFrameOpen(pStream, NULL/*(BITMAPINFOHEADER*) AVIGETFRAMEF_BESTDISPLAYFMT*/ /*&bih*/); //Get the first frame int index=0; for (int i=iFirstFrame; i<iNumFrames; i++) { Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 index= i-iFirstFrame; BYTE* pDIB = (BYTE*) AVIStreamGetFrame(pFrame, index); CreateFromPackedDIBPointer(pDIB, index); } AVIStreamGetFrameClose(pFrame); //close the stream after finishing the task if (pStream!=NULL) AVIStreamRelease(pStream); AVIFileExit(); return TRUE; } 3.3. Kết quả thực nghiệm và đánh giá - Giao diện chính của chương trình xác định độ đo tương tự của một ảnh với một trong những khung hình của file video. Hình 3.1 : Giao diện chính của chương trình Sau khi tải ảnh và tải một file video vào -> Kết luận độ tương tự của ảnh đó có trong file video. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 Hình 3.2: Kết quả thực nghiệm với ảnh có độ tương tự cao Đối với trường hợp không có ảnh tương tự hoặc độ tương tự nhỏ, chương trình sẽ như sau: Hình 3.3: Kết quả thực nghiệm với ảnh có độ tương tự thấp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 * Đánh giá: Trong chương trình này tôi sử dụng thuật toán so sánh Histogram để đối sánh các điểm ảnh với nhau. Khi đọc 1 ảnh vào chương trình sẽ tự động tính Histogram của ảnh đó, tiếp theo ta đọc một file video vào, và ta nhấn nút seach chương trình sẽ tự tách mỗi frame của file video ra và so sánh với histogram của file ảnh đó, lần lượt cho đến khi hết các Frame và chọn ra frame có độ tương tự lớn nhất để kết luận.. Kết quả cho thấy đây mới chỉ là bước đầu sử dụng thuật toán so sánh hai ảnh với nhau, đây là bước khởi đầu quan trọng trong quá trình đối sánh ảnh để sau này phát triển tốt hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 PHẦN KẾT LUẬN Thực tế của việc ứng dụng các thuật toán trong xử lý ảnh là rất lớn, rất nhiều các nhà lập trình đã nghiên cứu để đưa ra những phương pháp tìm kiếm, đối sánh ảnh nhằm ứng dụng rất lớn trong công tác an ninh, quốc phòng… Với thời gian còn hạn chế, trong Luận văn này tôi đã bước đầu tìm hiểu một số thuật toán như Transnable Similarity Measure (TMS) và Histogram để đối sánh một ảnh với từng frame trong file video. Đây cũng có thể được coi là nền tảng trong quá trình xử lý ảnh mà tôi đã tích luỹ được. Tuy nhiên trong quá trình nghiên cứu, mức độ thành công của tất cả các thuật toán tôi nghiên cứu là chưa được thành công lắm, chính vì vậy nếu có điều kiện tôi sẽ tiếp tục nghiên cứu và cài đặt thành công các thuật toán này một cách tốt nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 TÀI LIỆU THAM KHẢO [1]. Đỗ Năng Toàn, Phạm Việt Bình (2007), Giáo trình môn học Xử lý ảnh. [2]. Lương Mạnh Bá, Nguyễn Thanh Thủy (2002), Nhập Môn Xử lý ảnh số, Nxb Khoa học và Kỹ thuật, 2002. [3]. Anil K.Jain (1989), Fundamental of Digital Image Processing, Engwood cliffs. Prentice Hall [4]. J.R.Paker (1997), Algorithms for Image processing and Computer. John Wiley & Sons, Inc. Vision [5]. Randy Crane (1997), A simplified approach to image processing, Prentice-Hall, Inc. [6]. John C.Russ (1995), The Image Procesing Handbook. CRC Press, Inc. [7]. Adrian Low (1991), Introductory Computer Vision and Image, Copyright (c) 1991 by McGrow Hill Book Company Processing (UK) Limited. [8]. T. Pavlidis (1982), Algorithms for Graphics and Image Processing, Computer Science Press. [9]. Lương Xuân Cương, Ðỗ Xuân Tiến, Ðỗ Trung Tuấn (2004), “Kỹ thuật nâng cao khả năng phân đoạn dữ liệu video ứng dụng trong e-learning”, Báo cáo khoa học tại Hội thảo quốc gia “Một số vấn đề chọn lọc của Công nghệ thông tin”, Đà Nẵng, tháng 8/2004. [10]. Morpher Page, Website Sugano, M., Nakajima, Y., Yanagihara, H., Yoneyama, A., A fast scene change detection on MPEG coding parameter domain, International Conference on Image Processing, 1998. ICIP 98. Proceedings. 1998, Volume: 1, 1998, pp. 888 – 892 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 [11]. Nagasaka, A., Tanaka, Y., Automatic Video Indexing and Full-Video Search for Object Appearances, Visual Database Systems, II, Elsevier Science Publishers, 1992, pp. 113 – 127 [12]. Novak, C.L.; Shafer, S.A., Anatomy of a color histogram, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1992, pp. 599 – 605 [13]. Shahraray, B., Scene Change Detection and Content-Based Sampling of Video Sequences, Digital Video Compression: Algorithms and Technologies, A. Rodriguez, R. Safranek, E. Delp, Editors, Proc. SPIE 2419, 1995, pp. 2–13 [14]. Sawhney, H.S., Hafner, J.L., Efficient color histogram indexing, Proceedings of the IEEE International Conference on Image Processing, Volume: 2 , 1994 , pp. 66 – 70 [15]. Swanberg, D., Shu, C., & Jain, R. (1993). Knowledge-guided parsing in video databases. Proceedings. of SPIE Symposium on Electronic Imaging: Science and Technology, San Jose, CA, 13-24.