Luận văn: Tìm kiếm ảnh dựa vào nội dung

Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMTRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊNKHOA CÔNG NGHỆ THÔNG TINBỘ MÔN CÔNG NGHỆTRI THỨCNGUYỄNQUỐC UY - 9912745TÌM KIẾMẢNH DỰAVÀONỘIDUNGLUẬN VĂN CỬ NHÂN TIN HỌCGIÁO VIÊN HƯỚNG DẪNTh.s LÝ QUỐCNGỌCTP.HCM, 07/2003Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại họcLỜI CẢMƠNTrước tiên, em xin chân thành gửi lời cảmơn đến Thầy Lý Quốc Ngọc,người đã nhiệt tình, tận tâm, hướng dẫnvề kiến thứcđể em có thểlàm đượcluậnvăn này.Đúng lúc tưởng chừng đã bị bế tắt trong công việc, Thầy đãđộng viên giúpem mạnh dạng hoàn thành luận văn này. Một lần nữa em xin tỏ lòng biếtơn Thầy.Sau hết, xin gửi lời cảmơn đến gia đình bạn bè, người thân đãủng hộ độngviên tinh thần để luận văn được hoàn thành.Xin chân thành cảmơn tất cả !TPHCM, 07/2003Người thực hiệnNguyễn Quốc UyKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại họcNHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại họcNHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại họcMỤC LỤCLỜIMỞĐẦUPHẦN1: TỔNG QUAN1. Sự hình thành bài toán ..............................................................................32. Cách tiếpcận: .............................................................................................32.1.Đặctrưng màu sắc: .................................................................................42.2.Đặctrưng vân: .........................................................................................42.3.Đặctrưng hình dáng: ..............................................................................42.4. Độ đo: .......................................................................................................42.5. Mô hình giao diện: ..................................................................................5PHẦN 2: CÁC PHƯƠNG PHÁP TÌM KIẾM ẢNH DỰA VÀO NỘI DUNGChương 1: Tìm kiếm ảnh dựa vào màu sắc .................................................91. Màu sắc: ......................................................................................................101.1. Một sốđặc tính vậtlýđặtbiệt củamàu sắc ..........................................101.2. Hệthống màu chuẩn RGB .....................................................................101.3. Hệthống màu CMY ................................................................................121.4. Hệthống màu L*a*b...............................................................................121.5. Hệthống màu HSI...................................................................................122. Tìm kiếmảnh dựavàomàu sắc ................................................................142.1. Lượtđồmàu ............................................................................................142.2. Các loạiđộ đo màu sắc............................................................................19Chương 2:Tìm kiếm ảnh dựa vào vân..........................................................22Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học1. Vân ...............................................................................................................231.1. Vân là gì? ................................................................................................231.2. Một sốloại vân tiêu biểu .........................................................................242. Tìm kiếmảnh dựa vào vân ........................................................................252.1. Mậtđộcủađường biên và hướng của biên...........................................252.2. Phân hoạch vùng nhịphân cụcbộ.........................................................272.3. Ma trậnđồng hiệnvàđốitượngđồng hiện ..........................................282.4.Độ đonăng lượng củavân dựavàoluậtđo ..........................................312.5. Tương quan tựđộng và quang phổnăng lượng ...................................332.6. Phânđoạn vân (Texture segmentation) ................................................34Chương 3:Tìm kiếm ảnh dựa vào hình dạng...............................................351. Hình dạng....................................................................................................361.1. Khái niệmvềhình dạng ..........................................................................361.2.Đặcđiểmhìnhdạngđốivớiviệc tìm kiếmảnh ....................................362. Tìm kiếmảnh dựavàohìnhdạng .............................................................372.1. Lượtđồhình dạng...................................................................................372.2.Độso khớpđường biên củahìnhdạng..................................................382.3. So khớpvớiảnh phát họa .......................................................................40PHẦN 3 CÀI ĐẶT VÀ KẾT QUẢ THỬ NGHIỆMChương 1:Cài đặt ...........................................................................................441. Chương trình ..............................................................................................452. Phần Màu sắc..............................................................................................46Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học3. Phần Vân .....................................................................................................504. Phần Hình dạng ..........................................................................................53Chương 2:Kết quả thử nghiệm .....................................................................541. Phần Màu sắc..............................................................................................552. Phần Vân .....................................................................................................733. Phần Hình dạng ..........................................................................................77PHẦN 4 KẾT LUẬNĐánh giá kết quả đạt được ...........................................................................80Hướng phát triển ............................................................................................80Tài liệu tham khảo .........................................................................................81Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại họcTÓM TẮT LUẬN VĂNTên đề tài : Tìm kiếm ảnh dựa vào nội dungTìm kiếm ảnh dựa vào nội dung là mộtđề tài nghiên cứu về khả năng để xây dựngmộtchương trình cho phép tìm kiếmảnh trên một cơ sở dữ liệuảnh cho trước. Việctìm kiếm này dựa trên nội dung của những bức ảnh trong cơ sở dữ liệu. Nội dungcủa một bức ảnh có thể là màu sắc của bức ảnh, vân của bức ảnh, hay những kiểuhình dạng.Luận văn này tập trung vào việc nghiên cứu những lý thuyết để xây dựng nên mộtứng dụng như vậy, đồng thời ứng dụng lý thuyết đó để xây dựng nên một số demo,cho thấy khả năng có thể phát triển được thànhứng dụng hoàn thiệnđược.Đề tài gồm có ba phần: tìm kiếmảnh dựa vào màu sắc, vân và hình dạng.Tìm kiếm ảnh dựa vào màu sắc: cách tiếp cậnchính là dựa vào lượt đồ màu (colourhistogram)Tìm kiểm ảnh dựa vào vân: cách tiếp cận chính là dựa vào ma trận đồng hiện (co-occurrence matrix)Tìm kiếm ảnh dựa vào hình dạng: cách tiếp cận chính là dựa vào sự so khớp ảnhphát họa (sketch matching)Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học1LỜI MỞ ĐẦUSựmởrộng của multimedia, cùng vớikhốilượng hìnhảnh và phim lớn, sựphát triểncủanhững xa lộthông tin hiệntạiđã thu hút ngày càng nhiềunhữngchuyên giađi vào nghiên cứunhững công cụcung cấp cho việclấy thông tin từdữliệuảnh từnội dung của chúng. Lấy thông tin từdữliệuảnh có liên quanđến rấtnhiều các lĩnh vực khác, từnhững phòng trưng bày tranh nghệthuậtcho tớinhữngnơilưu trữtranh nghệthuậtlớn nhưviệnbảo tàng, kho lưu trữảnh chụp, kho lưutrữảnh tộiphạm, cơsởdữliệuảnh vềđịa lý, y học, ...điềuđó làm cho lĩnh vựcnghiên cứu này phát triển nhanh nhất trong công nghệthông tin.Lấy thông tin từdữliệuảnhđặtra nhiều thách thức nghiên cứumớicho cáckhoa học gia và các kỹsư.Phântíchảnh, xửlýảnh, nhậndạng mẫu, giao tiếpgiữangườivàmáy lànhững lĩnh vực nghiên cứu quan trọng góp phần vào phạmvinghiên cứu mớinày.Khía cạnh tiêu biểucủalấy thông tin từdữliệuảnh dựatrên những công bốcó sẵnnhưlà nhữngđốitượng nhậnthức nhưmàu sắc, vân (texture), hình dáng, cấutrúc, quan hệkhông gian, hay thuộcvềngữnghĩacănbảnnhư:đốitượng, vai tròhay sựkiện hay liên quanđến thông tin vềngữnghĩa quan hệnhưcảmgiác, cảmxúc, nghĩacủaảnh. Thật ra phân tíchảnh, nhậndạng mẫu, hay xửlýảnhđóng mộtvai trò cănbảntronghệthống lấy thông tin từảnh. Chúng cho phép sựtrích rút tựđộng hầuhếtnhững thông tin vềnhậnthức, thông qua phân tích sựphân bổđiểmảnh và sựphân tíchđộ đo.Tìm kiếm theo cách thông thường dựatrên vănbảngiờđây đượcbổsung bởitruy vấndựavàonội dung, nhắmvàokhíacạnh nhậnthức thông tinảnh. Thực hiệntruy vấnởmứcnhậnthứcđòi hỏinhững phương thức mới, cho phép chỉđịnhđếnnhững thuộc tính liên quanđếnthịgiác cần tìm. Giao diệnđồhọa phải hỗtrợđặctảnhững ví dụđónhưlà những mẫucósẵn. Khiđóngười dùng trong một vòng lặp,mô hình giao diệnsao cho ngườidùngcóthểtruy cậpvàosựgiống nhau giữanhữngđốitượng.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học2PHẦN 1TỔNG QUANKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học31. Sự hình thành bài toán:Bên cạnh kho dữliệuvănbản, kho dữliệuảnh ngày càng trởnên khổng lồvượt quá sựkiểmsoátcủa con người. Khi có nhu cầu tìm kiếmmộtvàitấmảnh nàođótrong một cơsởdữliệuhàngtrămngànảnh,điềunày khócóthểthực hiệnđược khi ta tìm kiếmbằng tay theo cách thông thường, nghĩalàxem lầnlượttừng tấmảnh một chođếnkhi tìmthấyảnh có nội dung cầntìm.Song song vớisựphát triểncủanhững phương tiệnkỹthuậtsố, trong tươnglai, sốlượngảnh sẽcòn tăng nhanh hơnnữa, nhiềuhơnnữa. Dođó, nhu cầuthậtsựđòi hỏiphải có một công cụhỗtrợcho việc tìm kiếmnày càngsớmcàng tốt. Vì vậyđềtài “tìm kiếmdữliệuảnh dựavàonội dung” rađờiđểgópphầnđápứng nhu cầu này.“Tìm kiếmdữliệuảnh dựavàonội dung” là gì?Đây là một chủđềnghiêncứumới trong công nghệthông tin. Mụcđích chính củanólàlấynhữngảnhtừcơsởdữliệuphùhợpvới tiêu chí truy vấn.Thếhệđầutiên củahệthống tìm kiếmảnh dựavàonội dung cho phép truycậptrực tiếpđếnảnh thông qua thuộc tính chuỗi. Những tìm kiếmđặcthùcho những hệthống dạng này là “tìm tấtcảnhững tranh vẽcủatrườngFlorentine trong thếkỷthứXV” hay “tìm kiếmtấtcảnhững tấmảnh vềđấtđai của Cezanne”. Metadata củahệthống trong thếhệđầutiên dựatrênchuỗi, sơđồtrình bày, mô hình quan hệ, cấu trúc khung. Xem hình 1.1.Thếhệmớicủahệthống tìm kiếmảnh hỗtrợđầyđủviệc lấy thông tin dựavào nội dung thuộcvềthịgiác. Chúng cho phép phân tíchđốitượng, tựđộngtrích rútđặctrưng. Xem hình 1.2.Những phần tửthuộcvềthịgiác nhưlà màu sắc, vân, hình dạngđốitượng,quan hệkhông gian có liên quan trực tiếpđến khía cạnh nhậnthức củanộidungảnh. Ta trựctiếpđánh vào những phầntửnày trong việc tìm kiếm.Dođó, nội dung củađềtài sẽgiải quyếtnhưsau: hệthống tìm kiếmảnh dựavào nội dung, bađặctrưng là màu sắc,vân và hình dạng.Đềtài chỉtập chungvào demo một sốphương pháp làm củatừng phần.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học42. Cách tiếpcận:Đề tài tiếpcận theo mô hình thống kê.Có ba loại tìm kiếmảnhđềtài tập chung giải quyếtlà:-Tìm kiếmảnh dựavàomàu sắc.-Tìm kiếmảnh dựavàovân.-Tìm kiếmảnh dựavàohìnhdạng.2.1.Đặctrưng màu sắc:Màu sắc là vấnđềcầntập chung giải quyết nhiềunhất, vì mộtảnh màu thìthông tin quan trọng nhấttrongảnh chính là màu sắc. Hơn nữa thông tin vềmàu sắc là thông tin người dùng quan tâm nhất; qua đặctrưng màu sắc, cóthểlọc đượcrấtnhiềulớpảnh, thông qua vịtrí, không gian,định lượng củamàu trongảnh.2.2.Đặctrưng vân:Có những lớpảnh mà màu sắc không thểgiải quyếtđược,đòi hỏiphải dùngđặctrưng vân. Ví dụnhưnhữngảnh liên quanđến cấutrúccủađiểmảnhnhư: cỏ, mây,đá, sợi.Vân sẽgiải quyếttốt cho việc tìm kiếmđốivớilớpảnh này.2.3.Đặctrưng hình dáng:Đối vớinhững lớpảnh cần tìm mà liên quanđếnhìnhdạng củađốitượng thìđặctrưng vân và màu không thểgiải quyếtđược. Ví dụnhưtìm một vậtcóhình dạng ellipse hay hình tròn trongảnh.Tìm kiếm theo hình dáng thậtsựlà một cáiđích củahệthống tìm kiếmdựavào nội dung muốnđạttới.2.4. Độ đo:Cóýnghĩa quan trọng trong tìm kiếmảnh dựavàonộidung.Độ đomangýnghĩa quyếtđịnh kếtquảtìm kiếmsẽnhưthếnào, mức độchính xác.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học52.5. Mô hình giao diện:Giao diệncũng là một vấnđề đáng quan tâm của bài toán tìm kiếmảnh. Môhình giao diệndựa trên mô hình tìm kiếm cho phép lặp.Đây mô hình người dùng có thể đặc tả yêu cầu tìm kiếm với nhiều cấp độ.Quá trình tìm kiếm có thể là một quá trình lặp đi lặp lại nhiều lần: tìm kiếm,lọc, chỉnh sửa ngưỡng cho đến khi đạt đến kết quả như mong muốn. Do đógiao diện chương trình phải hỗ trợ chức năng cho phép chọn lọc kết quả, loạibỏ những kết quả không phù hợp, lưu lại những kết quả đã vừa ý, tìm kiếmtrong kết quả vừa tìmđược, thay đổi mức độ chính xác của việc tìm kiếm.Hai vấnđề đượcđềtài quan tâm vềgiao diện tìm kiếm là: mô hình tìm kiếmtheo không gian toàn cụcvàcụcbộ.Đốivớiđặctrưng màu: giao diệnchophép giao tiếpcảtoàn cục và cụcbộ. Đặctrưng vân và hình dạngđềtài chỉdừng lạiởmứctoàncục.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học6Hệthống tìm kiếmChỉmụcTruy vấnbằng vănbảnTrình bày nội dungNgười dùngPhản hồiChú thích(làm bằng tay)Hình 1.1 Mô hình củahệthống tìm kiếmthếhệđầu tiênKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học7Hệthống tìm kiếmChỉmụcTruy vấnbằng văn bảnTrình bày nội dungNgười dùngPhản hồiChú thích(làm bằng tay)Hình 1.2 Mô hình củahệthống tìm kiếmthếhệmớiTruy vấnbằng vídụTìm lướtquaTrích rútđặttrưngKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học8PHẦN2CÁC PHƯƠNG PHÁP TÌM KIẾMẢNH DỰA VÀO NỘI DUNGKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học9Chương 1:Tìm kiếm ảnh dựa vào màu sắc1. Màu sắc1.1. Một sốđặc tính vậtlýđặtbiệt củamàu sắc1.2. Hệthống màu chuẩn RGB1.3. Hệthống màu CMY1.4. Hệthống màu L*a*b1.5. Hệthống màu HSI2. Tìm kiếmảnh dựavàomàu sắc2.1. Lượtđồmàu2.2. Các loạiđộ đo màu sắcKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học101. Màu sắc:Sự nhận thức về màu sắc là quá trình quan trọng của con người. Sự nhậnthức về màu sắc phụ thuộcvào cả tính chất vật lý của ánh sáng và quá trìnhxử lý của thị giác với sự góp phần rất quan trọng của kinh nghiệm. Conngười dùng thông tin màu sắc để phân biệt đối tượng, vật liệu, đồ ăn, vị trí vàngay cả thời gian của ngày.Với sự phát triển mạnh mẽcủa các thiết bị kinh tế, máy móc xử lý màu sắctrở nên thông dụng: Chúng ta có các thiết bị như máy quay phim màu, thiếtbị chiếu màu và những phần mềm xử lý ảnh màu. Máy móc có thể dùng màusắc cho những mục đích như là con người. Đặc biệt, màu sắc thuận tiện bởivì nó cung cấp phép đo lường đa dạng tại mỗi điểm ảnh đơn, có thể phân lớp,phân loại mà không cần đến những sự xử lý không gian phức tạp để đưa đếnquyết định.1.1. Một số đặc tính vật lý đặc biệt về màu sắc:Con người chỉ có khả năng nhận thức được ánh sáng có bức xạ điện từ vớibước sóng trong khoảng 400 – 700 nanomet. Cơ quan thị giác cảm nhậnđược ánh sáng là do bề mặt đối tượng phát ra ánh sáng, là kết quả của sựtương tác giữa năng lượng chiếu sáng và những phân tử của bề mặt đốitượng. Một đối tượng màu xanh dương sẽ có bề mặt màu xanh dương khichiếu ánh sáng trắng vào. Nhưng đối tượng đó sẽ có màu tím khi chiếu ánhsáng đỏ vào.1.2. Hệ thống màu chuẩn RGB:Mắt người có thể phân biệt hàng ngàn màu sắc khác nhau, những con sốchính xác hơn vẫn cònđang được bàn cãi nhiều. Ba màu RGB (Red-Green-Blue) mã hóa hệ thống đồ họa sử dụng ba byte (28)3hay khoảng chừng 16triệu màu phân biệt. Máy tính có thể phân biệt bất kỳ màu gì sau khiđượcmã hóa, nhưng việc mã hóa có thể không trình bàyđược những sự khác biệtKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học11trong thế giới thực. Mỗi điểm ảnh RGB bao gồm một byte cho màu R, mộtbyte cho màu G và một byte cho màu B.Việc mã hóa một màu tùy ý trong dãy hiển thị được làm bằng cách tổ hợp bamàu chính. Ví dụ: Red(255,0,0), Green(0,255,0), Blue(0,0,255), Black(0,0,0)Hệ thống màu RGB là một hệ thống màu cộng vào bởi vì mỗi màu được tạonên bằng cách cộng thêm các phần tử vào màu đen(0,0,0)Khuôn dạng của không gian màu RGB là định dạng phổ biến nhất của ảnhsố, lý do chính là tính tương thích với màn hình hiển thị chính là màn hình vitính. Tuy nhiên không gian màu RGB có hạn chế lớn nhất là không phù hợpvới cách con người cảm nhận về màu sắc. Dođó không phù hợpcho việcứng dụng vào tìm kiếmảnh.BlueGreenRed[1,0,1]Magenta[1,1,0]Yellow[0,1,1]Cyan[0,0,0] [0,0,1][0,1,0][1,0,0][0,1,1]WhiteHình 1: KhốimàuKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học121.3. Hệthống màu CMY:Hệ thống màu CMY theo mô hình in trên giấy trắng và theo khuôn mẫu trừtừ màu trắng thay vì thêm vào từ màu đen như hệ thống màu RGB.CMY là viết tắt của Cyan-Magenta-Yellow (màu lục lam, màu đỏ tươi, màuvàng), đó là ba màu chính tươngứng với ba màu mực in. 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àuxanh dương. Do đó, tạo ra sự phản ánh tươngứng như khi inảnh được chiếusáng với ánh sáng trắng. Hệ thống dưới dạng âm tính vì mã hóa theo dạnghấp thụ màu. Có một số mã hóa như sau: trắng (0,0,0) vì không có ánh sángtrắng được hấp thụ, đen (255,255,255) vì tất cả các thành phần của màu trắngđều được hấp thụ.Hệ thống màu CMY dường như là một sự đảo ngược của hệ thống màuRGB. Đặc tính của nó là sựđơn giản, ứng dụng nhiều trong thực tế. Tuynhiên khuyết điểm của nó cũng tương tự như không gian màu RGB, tức làcách mã hóa khác với cách mà con người cảm nhận về màu sắc. Không thíchhợp cho bài toán tìm kiếm ảnh dựa vào nội dung.1.4. Hệthống màu L*a*b:Mô hình L*a*b đượcđềcửbởi CIE cho việc lượng hóa sựkhác biệtcủamàusắc trong vậtchiếusángcủa ánh sáng ban ngày. Tuy nhiên nó có mộtsựchuyểnđổiđượcghi vàođểmà tính toán cho việc thích nghi vớinhữngnguồnsáng.Đây là hệthống màu có sựtách riêng ánh sáng và màu sắc ra riêng. Dođó,cũng có khảnăng lớn cho việc tìm kiếmdựavàonội dung.1.5. Hệ thống màu HSI: Hue-Saturation-IntensityHệ thống màu HSI mã hóa thông tin màu sắc bằng cách chia giá trị intensityI từ hai giá trị được mã hóa thuộc về độ hội tụ của màu- hue H và saturationS.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học13Thành phần không gian màu HSI gồm có ba phần: Hue được định nghĩa cógiá trị 0-2Π , mang thông tin về màu sắc. Saturation có giá trị 0-1, mang giátrị về độ thuần khiết của thành phần Hue. Intensity (Value) mang thông tinvề độ sáng của điểm ảnh.Ta có thể hình dung không gian màu HSI như là vậthình nón. Với trục chính biểu thị cường độ sáng Intensity. Khoảng cách đếntrục biểu thị độ tập chung Saturation. Góc xung quanh trục biểu thị cho sắcmàu Hue.Đôi khi, hệ thống màu HSI được coi như là hệ thống màu HSV dùngValuethay vìIntensity.Hệ thống màu HSI thì thích hợp hơn với một số thiết kế đồ họa bởi vì nócung cấp sự điều khiển trực tiếp đến ánh sáng và hue. Hệ thống màu HSIcũng hỗ trợ tốt hơn cho những thuật toán xử lý ảnh vì sự tiêu chuẩn hóa vềánh sáng và tập chung vào hai tham số về độ hội tụ màu, và cườngđộmàu.Hệ thống màu HSI có sự phân chia rõ rệt giữa ánh sáng và màu sắc. Do đócó khả năng rất lớn được áp dụng cho việc tính đặc trưng và so sánh sự giốngHình 2: Khối nón màu minh họahệthống màu HSIGreenBlue CyanYellowMagentaRed[0,0,0]Black H=2Π/3GreenRedH=0 CyanH=ΠBlueH=4Π/3H=Π/3YellowIWhiteHSI=0.5I=1Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học14nhau về màu sắc của hai ảnh. Do đó nó rất thích hợp cho việc tìm kiếm ảnhdựa vào màu.Sự giống và khác nhau giữa hai ảnh về mặt màu sắc đối với mắt người chỉmang ý nghĩa tương đối. Do đó khi áp dụng vào bài toán này trên máy tínhthì ta cũng giả lập sự tương đối này.Phương pháp chính của việc tìm kiếm theo màu sắc là dùng lượt đồ màu đểlàm đặc trưng cho từng ảnh. Do những đặc điểm riêng của mô hình màu HSIvà đặc trưng của việc tìm kiếm nên tính lượt đồmàu cũng được dùng một mômình rất đặc biệt để phù hợp cho những đặc điểm riêng này.2. Tìm kiếmảnh dựavàomàu sắc:Phương pháp phổ biến để tìm kiếm ảnh trong một tập những ảnh hỗn tạp chotrước là dựa vào lượt đồ màu của chúng. Đây là cách làm khá đơn giản, tốcđộ tìm kiếm tương đối nhanh nhưng khuyết điểm là kết quả tìm kiếm lại cóđộ chính xác không cao. Nhưng đây có thể được xem như là bước lọc đầutiên cho những tìm kiếm sau. Muốn được kết quả chính xác cao đòi hỏi sựkết hợp đồng thời với vân (texture) và hình dáng (shape).Cho đến nay, để giải quyết vấn đề về màu sắc, cách tiếp cận chính vẫn là dựavào lượt đồ màu.2.1. Lượt đồ màu:Lượt đồ màu: Nhưlà một bảng tóm tắt thông tin vềmàu sắc cho mộtảnhmàu bấtkỳ.Và việc tính lượtđồmàu này đượctiếnhànhmột cách rất nhanh chóng trongảnh mà chỉ qua một lần duyệt qua toàn bộ ảnh. Dođóứng dụng vào việc tìmkiếmảnh sẽcó lợirấtlớnvềmặttốcđộ.Một số tính chất cần quan tâm của lượt đồ màu đối với vấn đề truy tìmảnh:-Việc tính lượt đồ màu của ảnh diễn ra rất nhanh chóng trong ảnh chỉ quamột lần duyệt qua toàn bộ ảnh.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học15-Lượt đồ màu tương đối bất biến đối với phép tịnh tiến, xoay ảnh, và nhất làsự kéo nhỏ, kéo giãn, thayđổi kích thước của ảnh.-Lượt đồ màu của một ảnh màu có thể là một cách miêu tả rất có ý nghĩacho việc truy tìmảnh hay nhận dạng đối tượng trong ảnh2.1.1. Lượt đồ màu thông thường RGB:Đối với ảnh 256 màu, lượtđồmàu củaảnh tươngđương vớilượtđồmàu củaảnh xám.Đối với ảnh 24 bit màu, lượtđồmàu miêu tảkhảnăng kếtnốivềcườngđộcủa ba kênh màu R, G, B. Lượtđồmàu này đượcđịnh nghĩanhưsau:hR,G,B[r, g, b] = N*Prob{R=r, G=g, B=b}trong đóN làsốlượngđiểm có trongảnh.Lượtđồmàuởdạng này được tính bằng cách rờirạc hoá từng màu trongảnh, sau đólàđếmsốđiểmảnh củamỗimàu.Khi mà sốlượng màu là có hạn, đểthuậntiệnhơn, ngườita thường chuyểnđổi ba kênh màu thành một biếngiátrịmàu duy nhất. Cho mộtảnh RGB,mộtkiểuchuyển đổithườngđượcsửdụng là:m= r+Nrg+NrNgb trong đóNr,Nglà sốlượng bin củamàu đỏvà màu xanh lục.Điều này mang lạimột lượtđồ đơn duy nhấtnhưsau:h[m] = N*Prob{M=m}Một cách khácđểtính lượtđồmàu củaảnh RGB là ta phân ra thành 3 lượtđồriêng biệthR[], hG[], hB[]. Khi đó, mỗilượtđồ được tính bằng cáchđếmkênh màu tươngứng trong mỗiđiểmảnh.2.1.2. Lượt đồ màu HSI:Mô hình màu HSI có nhữngưu điểm lớn cho việc tìm kiếm hìnhảnh dựa vàonội dung và nhất là trong công việc tìm kiếm dựa vào màu sắc. Nhưng nhữngảnh màu thông thường được lưu trữ ở dạng kỹ thuật số trong máy tínhKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học16thường theo chuẩn RGB, do đó để có được ảnh màu HSI ta phải qua côngđoạn chuyển đổi. Chuyển từ hệ màu RGB sang hệ màu HSI là một thuật giảicó rất nhiều trong hầu hết những sách về xử lý ảnh cổ điển.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học17Gọi R,G,B là giá trị nhập của RGB với giá trị trong khoảng[0,1] hay [0,255]I : Giá trị xuất của cường độ intensity [0,1]S : Giá trị xuất của độ bảo hòa saturation [0,1]H : Giá trị xuất của màu sắc hue [0,2Π]R,G,B,H,I,S: Tất cả đều là những giá trị số thực.Procedure RGB_to_HSI(in R,G,B; out H,S,I){I:=Max(R,G,B);Min:=Min(R,G,B);If (I>=0) thenS:=(I-Min)/I;Else S:=0;If (S<=0) then{H:=-1;Return;}Diff:= I-Min;If (R=I) then H:=(Π/3)*(G-R) /Diff;Else if (G=I) then H:=(2*Π/3)+Π/3*(B-R)/diff;Else if (B=I) then H:=(4*Π/3)+Π/3*(R-G)/diff;If (H<=0) H:=H+Π/2;}Thuật toán chuyển đổi từ RGB sang HSIKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học18Theo các phương pháp truyền thống, việc tạo lượt đồ màu chỉ đơn giản bằngcách chia không gian màu thành những ngăn riêng biệt, sau đó đếm nhữngpixel có màu sắc phù hợp trong những ngăn này. Cách làm này rất đơn giản,nhưng không phù hợp cho việc so sánh, tìm kiếm ảnh. Vì những thay đổi nhỏvề điều kiện chiếu sáng, sự thay đổi về cường độ có thể gây nên những thayđổi lớn trong lượt đồ màu. Do đó, haiảnh rất giống nhau về màu sắc có thểcó lượt đồ màu hoàn toàn khác nhau.Ví dụ :không gian màu HSI, thành phần Hue trong nhiều trường hợp manggiá trị nhưng không thể hiện được màu sắc trong hiển thị: Khi giá trịIntensity nằm trong khoảng 0-0.2, Hue mang bất kỳ giá trị nào thì màu màmắt người nhìn thấy vẫn là màu đen. Vì vậyđốivớicác cách tínhlượtđồmàu thông thường,điểmảnh A có Hue bằng 2π, Intensity bằng 0.1 vàđiểmảnh B có Hue bằngπ, Intensity bằng 0.1 sẽnằm trong những bin khác nhau.Nhưng thậtra,điểmảnh A vàđiểmảnh Bđềucógiátrịhiểnthịlà màuđen.Lượt đồ HSI cải tiến:Một phương pháp được đề suất để giải quyết cho trường hợptrênlà tadựa vào Intensity để lọc trước những giá trị mà Hue không thể biểu thị được.Sau đó dùng Saturation để lọc những giá trị có sắc màu xám. Phần còn lạicủa không gian màu ta sẽ chia đều mỗi thành phần thành những khoảng nhấtđịnh có sự tương đồng về màu sắc.Để giá trị của lượt đồ màu HSI được tính một cách phù hợp nhất đối với việctìm kiếm, chúng ta cần chia nhỏ không gian 24 bit màu, tươngứng với 224màu, xuống một con số có thể chấp nhận được. Một con số được đề nghị là 5giá trị mức xám, 162 cho giá trị sắc màu, tổng cộng là ta chỉ cần lưu trữ 167bin màu.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học19Hue và Saturation khi Intensity < 0.33Hue và Saturation khi Intensity > 0.332.2. Các loại độ đo màu:Bước tiếp theo của quá trình tìm kiếm dữ liệu ảnh dựa vào nội dung là xácđịnh độ trùng khớp của hai lượt đồ màu vừa tính được ở bước trên. Do đó,phát sinh ra một giá trị để biếu thị cho sự trùng khớp này, có nhiều cách đểtính giá trị này. Ta gọi những giá trị được tính từ những cách khác nhau nàylà các loại độ đo màu.Một cách đơngiản,độ đo màu làđượccoimột giá trị đểbiểuthịcho độsokhớp sự trùng khớp của hai lượt đồ màu. Tùy theo từng trường hợp, từng loạiđộ đo màu giá trịnày có thể âm hoặc dương lớn hoặc nhỏ tươngứng với mứcđộ giống nhau như thế nào của các loại lượt đồ màu.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học20Mỗi loại độ đo màu có nhữngưu và khuyết điểm riêng, trong từng trườnghợp cụ thể.Gọi h(I) và h(M) tươngứng là 2 lượt đồ màu của hai ảnh I vàảnh M. Khi đócác loại độ đo màu được định nghĩa là một số nguyên (hoặc số thực) theo cácloại độ đo tươngứng như sau:2.2.1. Độ đokhoảng cách min-max:Đượcthựchiệndựatrênýtưởng lấy phầngiao củacủahai lượtđồcần sosánh, ta sẽđượcmột lượtđồ, tính tổng các giá trịcóđượctừlượtđồnày chota đượ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) ) =∑= Kj1min{h(I)[j],h(M)[j]}Đố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) ) =∑= Kj1max{h(I)[j],h(M)[j]}Matching ( h(I), h(M)) =∑∑iii M h i I hM h I h tion Inter]) )[ ( ], )[ ( max()) ( ), ( ( sec2.2.2. Độ đokhoảng cách euclid:Đây là cách tính khoảng cáchơclit thông thường giữa các K bin:Intersection( h(I), h(M) ) =∑= Kj12)) ( ) ( (M h I h−Hoặc có thể là:Intersection( h(I), h(M) ) =∑= Kj1) ( ) (M h I h−Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học212.2.3. Độ đokhoảng cách toàn phương:Intersection(h(I),h(M)) =∑∑== KiKj 11[h(i)-h(j)] aij[h(i)-h(j)]2.2.3. Độ đo có trọng số:dhist(I, Q) = (h(I) – h(Q))TA(h(I) – h(Q))trongđó, h(I) và h(Q) là những lượtđồtươngứng củaảnh I và Q, và A là matrậnđồng dạng KxK. Trong ma trậnnày, những màu mà rấtgiống nhau thìgầnvớigiátrịmột, còn những màu rất khác nhau thì sẽcó giá trịgầnvớikhông.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học22Chương 2:Tìm kiếm ảnh dựa vào vân1. Vân1.1. Vân là gì?1.2. Một sốloạivân tiêu biểu.2. Tìm kiếmảnh dựa vào vân2.1. Mậtđộcủađường biên và hướng củabiên2.2. Phân hoạch vùng nhịphân cụcbộ2.3. Ma trậnđồng hiệnvàđốitượngđồng hiện2.4.Độ đonăng lượng củavân dựa vào luậtđo2.5. Tương quan tựđộng và quang phổnăng lượngKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học231. Vân:1.1. Vân là gì?Vân (texture),đếnnàyvẫn chưa có một định nghĩa chính xác cụ thể về vân,là một đốitượng dùng để phân hoạchảnh ra thành những vùng được quantâm vàđểphân lớpnhững vùngđó.Vân cung cấp thông tin vềsựsắpxếpvềmặt không gian củamàu sắcvàcườngđộcủamộtảnh.Vân đượcđặctrưng bởisựphân bổkhông gian củanhững mức cườngđộtrong một khu vựclánggiềng với nhau.Vân củaảnh màu và vânđốivớiảnh xám là nhưnhau.Vân gồm nhiềuvân gốc hay vân phần tửgộplại,đôi khi đượcgọi là texel.Xét về vấn đề phân tích vân, có hai đặc trưng chính yếu nhất:-Cấu trúc vân được định nghĩa như sau: vân là tập hợp nhữngtexelđượcsắp xếp theo một số quy luật nhất định hay có cấu trúc không gian lặp đilặp lại.-Sự thống kê vân được định nghĩa như sau: vân là một độ đo về số lượngcủa sự sắp xếp những mức xám hay cường độ sáng trong vùng.Cấu trúc vân: một vân bất kỳ có thể coi như là một tập của những texel thôtrong một quan hệ không gian đặcbiệt nào đó. Một cấu trúc không gian củamột vân bất kỳ sau đó có thể bao gồm một sự mô tả của texel và một đặc tảvề không gian. Những texel đương nhiên phải được phân đoạn và quan hệkhông gian phải được tính toán một cách thật hiệu quả. Texel là những vùngảnh có thể trích rút từ một số hàm phân ngưỡng đơn giản. Đặc điểm quan hệkhông gian của chúng có thể miêu tả như sau:Giả sử rằng chúng ta có tập những texel, với mỗi phần tử của tập hợp này tacó thể đặc trưng bởi một điểm ý nghĩa nhất, điểm này gọilà trọng tâm. Đặt Slà tập của những điểm này. Với mỗi cặp điểm P và Q trong tập S, ta có thểxây dựng đường phân giác trực giao nối chúng lại với nhau. Đường phângiác trực giao này chia mặt phẳng thành hai nửa mặt phẳng, một trong chúngKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học24là tập của nhữngđiểm gần với P hơn và cái còn lại là tập những điểm gần vớiQ hơn. Đặt HQ(P) là nửa mặt phẳng gần P hơn. Ta có thể lặp lại quá trình nàyvới mỗi điểm Q trong S. Đa giác Voronoi của P là vùng đa giác bao gồm tấtcả những điểm gần P hơn những điểm khác củaS và được định nghĩa:V(P) = ∩HQ(P)Q∈S, Q≠P1.2. Một số loại vân tiêu biểu:Vân giấyVânđáVân dệtVân nướcVân cátVân gỗVân sợiGiấythô5%xéoXéo ngắnZíc ZắcgạchlợpvánCa rôCỏKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học252. Tìm kiếm ảnh dựa vào vân:Trong hầu hết các trường hợp, phân đoạn những ảnh thật ra những texel khóhơn nhiều đối với trường hợp tự nhiên sinh ra những hoa văn thiên nhiên.Thay vì vậy, việc định lượng về số hay thông tin thống kê bằng số mô tả chomột vân có thể được tính từ chính mức xác, hay mức màu của chúng. Tuycách tiếp cận này ít trực quan nhưng nó có hiệu suất tính toán cao, hơn nữacách tiếp cận này cũng phù hợp với đồng thời cho việc phân đoạn vân vàphân loại vân.2.1. Mật độ của đường biên và hướng của biên:Từ khi phương pháp dò biênđược phổ biến rộng và sự đơn giản trong ứngdụng vào quy trình dòđối tượng, nó trở thành là bộ dò biên như là bước tiênquyết trong việc phân tích vân. Số lượng điểm ảnh trong một vùngảnh xácđịnh trước về mặt kích thước cho ta thấy được một số biểu thị về mật độđiểm trong vùngảnh đó. Hướng của những đường biên này cũng có thể hữudụng trong việc mô tả đặc điểm hoa văn của vân.Xét khu vực gồm có N điểm ảnh. Giả sử rằng bộ dò biên dựa trên gradient ápdụng vào cho vùngảnh này sinh ra hai kết xuất của của mỗi điểm ảnh p: 1)độ lớn gradient Mag(p) và 2) phương hướng gradient Dir(p). Một trongnhững đối tượng vân rất đơn giản là số đường biên trên một khu vực đượcđịnh nghĩa như sau:Fedgeness=NT p Mag p} ) ( | {≥với T là ngưỡng định nghĩa trước.Số đường biên trên một khu vực để đánh giá mật độ, nhưng không đánh giáđược phương hướng của vân.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học26Độ đo này có thể được mở rộng để có thể bao gồm cả mật độ và phươnghướng bằng cách dùng lượt đồ cho cả độ lớn gradient và phương hướnggradient. Gọi Hmag(R) biểu thị lượt đồ bình thường của độ lớn gradient củakhu vực R, và gọi Hdirbiểu thị lượt đồ bình thường của phướng hướnggradient của khu vực R. Cả hai lượt đồ này có số lượng bin lớn hơn một sốcố định, trình bày những nhóm độ lớn gradient và những nhóm của phươnghướng gradient. Cả hai được tiêu chuẩn hóa theo kích thước NRcủa khu vựcảnh R. Khi đó ta có :Fmag dir= (Hmag(R), Hdir(R))là một mô tả của vân định lượng của khu vực ảnh R.Xét haiảnh 5x5 như sau:Ảnh bên trái có mật độ điểm cao hơnảnh bên phải. Nó có một cạnh trongmỗi 25 điểm ảnh của nó, vì vậy số cạnh trên một đơn vị khu vực của nó là1.0.Ảnh bên phải có 6 cạnh trên mỗi 25 điểm ảnh của nó, vì vậy số cạnh trênKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học27một đơn vị khu vực của nó là 0.24. Đối với lượt đồ độ lớn gradient, chúng tađề dùng hai bin trình bày cho đường biên sáng và đường biên tối. Với lượtđồ phương hướng gradient, chúng ta sẽ dùng ba bin cho đường biên ngang,đường biên dọc và đường biên xéo.Ảnh bên trái có 6 đường biên tối và 19đường biên sáng, nên lượt đồ độ lớn gradient bình thường củanó là(0.24,0.76), nghĩa là 24 phần trăm của đường biên là đường biên tối, 76 phầntrăm của đường biên là đường biên sáng. Nó cũng được xem như có 12đường biên ngang, 13 đường biên dọc, và không có đường biên xéo, vậy lượtđồ phương hướng gradient bình thường của nó là (0.48,0.52, 0.0), nghĩa là 48phần trăm đường biên là ngang, 52 phần trăm đường biên là dọc và 0 phầntrăm đường biên xéo.Ảnh bên phải không có đường biên tối và có 6 đườngbiên sáng, nên lượt đồ độ lớn gradient bình thường của nó là (0.0,0.24). Nókhông có đường biên ngang, không có đường biên dọc, nhưng có 6 đườngbiên xéo, vậy lượt đồ phương hướng gradient bình thường của nó là (0.0,0.0,0.24).Trong trường hợp hai ảnh này, độ đo đường biên trên một đơn vị khu vực thìthích hợp để phân biệt giữa chúng, nhưng trong trường hợp tổng quát độ đolượt đồ thường cung cấp một cơ chế mô tả mạnh hơn nhiều. Hai lượt đồ n-bin H1và H2có thể được so sánh bởi tính khoảng cách L1của chúng.L1(H1,H2) =∑=−nii H i H12 1] [ ] [2.2. Phân hoạch vùng nhị phân cục bộ:Một cách khác rất đơn giản, nhưng là độ đo vân hữu dụng là độ phân hoạchvùng nhị phân cục bộ. Đối với mỗi điểm ảnh p trong ảnh, tám điểm lân cậnđược xem xét rằng cường độ intensity của chúng có lớn hơn của điểm ảnh phay không. Những kếtquả từ tám điểm ảnh lân cận được sử dụng để xâydựng nên một số nhị phân tám chữ số là b1b2b3b4b5b6b7b8, trong đó bi=0 nếuKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học28cường độ intensity của láng giềng thứ i nhỏ hơn hay bằng với p và bi=1 trongtrường hợp ngược lại. Một lượt đồ của những số này được dùng để biểu thịcho vân của ảnh. Hai ảnh hay hai khu vực ảnh được so sánh bởi việc tínhtoán độ dài L1 giữa lượt đồ của chúng được định nghĩa ở trên.2.3. Ma trận đồng hiện và đối tượng đồng hiện:Ma trận đồng hiện là một mảng C hai chiều trong đó cả dòng và cộttươngứng với một tập các giá trị có thể có V. Ví dụ như, đối với ảnh mứcxám V có thể là tập những mức xám có thể có, đối với ảnh màu V có thể làtập những màu có thể có. Giá trị của C(i,j) cho thấy rằng bao nhiêu lần giá trịi cùng xuất hiện trong với giá trị j trong một số quan hệ không gian đượcđịnh nghĩa trước. Ví dụ : quan hệ không gian có thể có giá trị i xuất hiện lậptức ngay bên phải của giá trị j. Rõ ràng hơn, chúng ta sẽ xem xét trường hợpriêng trong đó tập V là tập những mức xám và quan hệ không gian đượcmang lại bởi vectơ d, chỉ định độ dịch chuyển giữa điểm ảnh có giá trị i vàđiểm ảnh có giá trị j.Gọi d là một vectơ dịch chuyển (dr,dc) ở đó dr thì thay thế cho hàng và dcthay thế cho cột. Gọi V là tập của những mức xám. Ma trận đồng hiện mứcxám choảnh I được định nghĩa bởi:Cd[i,j]= |{[r,c] sao cho I[r,c]=i và I[r+dr,c+dc]=j}|Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học29Minh họa nội dung này với một ảnh 4x4 I và ba ma trận đồng hiện cho I làC[0,1], C[1,0] và C[1,1].Chú thích C[0,1] : vị trí [1,0] có giá trị 2, chỉ định rằng j=0 xuất hiện hai lầntrực tiếp bên phải của i=1 trong ảnh. Tuy nhiên vị trí [0,1] có giá trị 0, chỉđịnh rằng j=1 không bao giờ xuất hiện trực tiếp bên phải của i=0 trong ảnh.012040212202002012040212202002012020212112001ijijijC[1,1] C[1,0] C[0,1]1100110000220022Ảnh 1ijKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học30Giá trịlớn nhất trong ma trận đồng hiện là 4 tại vị trí [0,0], chỉ định rằng giátrị 0 xuất hiện 4 lần trực tiếp bên phải của giá trị 0 khác trong ảnh.Có hai biến tấu quan trọng của ma trận đồng hiện từ ma trận đồng hiện mứcxám chuẩn.Đầu tiên tiêu chuẩn hoá ma trận đồng hiện mức xám Ndđược định nghĩa bới:Nd[i,j]=∑∑ijdj i Cj i Cd] , [] , [Tiêu chuẩn hoá những giá trị của ma trận đồng hiện nằm giữa giá trị 0 và 1.Và do đó có thể xem xét chúng dưới dạng xác suất trong ma trận lớn.Thứ hai là ma trận đồng hiện mức xám đối xứng Sdđịnh nghĩa bởi :Sd[i,j] = Cd[i,j]+C-d[i,j]thực chất là một cặp của nhóm của những đối xứng kề cận nhau.Ma trận đồng hiện nắm bắt thuộc tính của vân, nhưng chúng không hữu dụngtrực tiếp cho việc phân tích sâu hơn về vân, như là so sánh hai vân. Thay vìvậy, những đối tượng số học của vân được tính toán từ ma trận đồng hiện cóthể được dùng để trình bày vân chặt chẽ hơn, súc tích hơn. Dưới đây lànhững đối tượng chuẩn bắt nguồn từ một ma trận đồng hiện chuẩn.Energy =∑∑ijdj i N] , [2Entropy = -∑∑ijd dj i N j i N] , [ log ] , [2Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học31Contrast =∑∑−ijdj i N j i] , [ ) (2Homogeneity =∑∑− +ijdj ij i N1] , [Correlation =j i ijd j ij i N j iσ σµ µ∑∑− −] , [ ) )( (Trong đój iµµ,là giá trị trung bình vàj iσσ,là độ lệch chuẩn của hàng vàcột i, j.Nd[i] =∑jdj i N] , [Nd[j] =∑idj i N] , [Một vấn đề với độ vân lệch từ ma trận đồng hiện là bằng cách nào đểchọn véctơ d. Một giải pháp được đề nghị bởi Zucker và Terzopoulos làdùng kiểmtra bằng thống kê2χđể chọn những giá trị của d mà vân có cấutrúc nhất; đó là, giá trị cực đại của giá trị:∑∑− =ijd ddj N i Nj i Nd1] [ ] [] , [( ) (22χ)2.4. Độ đo năng lượng của vân dựa vào luật đo:Một cách tiếp cận khác đối với việc sinh ra nhữngđối tượng vân làdùng những mặt nạ cục bộ để mà dò tìm những kiểu vân khác nhau.Luật đo đưa ra một cách tiếp cận dựa vào năng lượng vân, đo lường số lượngbiến số lớn trong phạm vi một cửa sổ cố định kích thước trước. Một tập củaKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học329 mặt nạ 5x5 được dùng để tính năng lượng vân, được trình bày bởi mộtvéctơ gồm 9 giá trị cho mỗi điểm ảnh của ảnh được mang ra phân tích.Những mặt nạ được tính từ những vectơ dưới đây :L5 (Level) = [ 1 4 6 4 1]E5 (Edge) = [ -1 -2 0 2 1]S5 (Spot) = [ -1 0 2 0 -1]R5 (Ripple) = [ 1 -4 6 -4 1]Tên của những vectơ nói rõ mục đích của chúng. Vectơ L5 mang lại trọnglượng trung tâm trung bìnhđịa phương. Vectơ E5 dòđường biên. Vectơ S5dòđiểm. Vectơ R5 dò sự gợn sóng. Mặt nạ 2 chiều được tính bằng tíchnhững cặp vectơ tươngứng. Ví dụ như mặt nạ E5L5 được tính bằng tích củavectơ E5 và L5 như sau:Bước đầu tiên trong hàm Luật đo là loại bỏ tất cả những ảnh hưởng của sựchiếu sáng bằng cách di chuyển một cửa sổ nhỏ đi khắp trong ảnh, và tríchrút ra trung bìnhđịa phương cho mỗi điểm ảnh, để cho ra kết quả là một ảnhtiền xử lý, trong đó cường độ intensity của mỗi điểm láng giềng xấp xỉkhông. Kích thước của cửa sổ phụ thuộc vào lớp ảnh loại nào; Người ta quendùng cửa sổ kích thước 15x15 cho những khung ảnh tự nhiên. Sau quá trìnhtiền xử lý, mỗi 16 mặt nạ 5x5 được áp vàoảnh tiền xử lý, sinh ra 16 ảnh lọc.Gọi Fk[i,j] là kết quả lọc với mặt nạ thứ k tại điểm ảnh [i,j]. Khi đó bản đồnăng lượng vân Ekcho bộ lọc k được định nghĩa bởi:-1-2012x [1 4 6 4 1 ] =-1 -4 -6 -4 -1-2 -8 -12 -8 -20 0 0 0 02 8 12 8 21 4 6 4 1Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học33Ek[r,c] =∑∑+− =+− = 7777] , [cc jrr ikj i FMỗi bản đồ năng lượng vân là một ảnh đầy đủ, trình bàyứng dụng của mặtnạ thứ k tới ảnh nhập vào.Một khi 16 bản đồ năng lượng được sinh ra, những cặp đối xứng thíchhợp được nối lại để sinh ra 9 bản đồ cuối cùng, là sự thay thế mỗi cặp với giátrị trung bình của chúng. Ví dụ như: E5L5 đo được nội dung của đường biênngang, và L5E5 đo được nội dung đường biên ngang. Trung bình cộng củahai bản đồ đo được toàn bộ nội dung củađường biên của ảnh.Có tổng cộng 9 bản đồ năng lượng tổng hợp là :L5E5/E5L5 L5S5/S5L5L5R5/R5L5 E5E5E5S5/S5E5 E5R5/R5E5S5S5 S5R5/R5S5R5R51.5: Tương quan tự động và quang phổ năng lượng:Hàm tương quan tự động của một ảnh có thể được dùngđể dò tìmnhững phần tử hoa văn của vân và cũng đồng thời mô tả tính mịn/tính thôcủa vân. Hàm tương quan tự động()dc dr,ρcủa một ảnh với kích thước(N+1)x(N+1) với một độ dời d = (dr, dc) là:∑∑ ∑∑== ==+ +=NrNc NrNcc r Idc c dr r I c r Idc dr002 00] , [] , [ ] , [) , (ρ=] , [ ] , [] , [ ] , [c r oI c r Ic r oI c r IdKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học34Nếu vân ở dạng thô, khi đó hàm tương quan tự động sụt giảm chậm;ngược lại nó sẽ sụt giảm rất nhanh. Đối với những vân theo quy tắc, hàm tựđộng tương quan sẽ yếu. Khi I[r+dr, c+dc] không được xác định rõ làđườngbao của ảnh, một phương phápđể tính toán những giá trị ảnh ảo phải đựợcđịnh nghĩa.Hàm tự động tương tác liên quan với quang phổ nặng lượng của phépbiến đổi Fourier. Nếu I[r,c] là hàmảnh và F(u,v) là biến đổi Fourier của nó,2) , (v u Fđược coi như là quang phổ năng lượng.2.6. Phân đoạn vân (Texture segmentation):Bất kỳ độ đo một vân nào, cung cấp một giá trị hay vectơ giá trị tạimỗi điểm ảnh, mô tả vân trong những điểm láng giềng của điểm ảnh đó, cóthể được dùng để phân đoạn ảnh thành những vùng có vân giống nhau. Nhưnhững thuật toán phân đoạn ảnh khác, những thuật toán phân đoạn vân có hailoại chính: cách tiếp cận dựa vào vùng và cách tiếp cận dựa vào đường biên.Cách tiếp cận dựa vào vùng có ý tưởng chính là nhóm hay phân chia nhữngđiểm ảnh với những đặc tính vân giống nhau. Cách tiếp cận dựa vào đườngbiên có ý tưởng là đi tìm những đường biên vân giữa những điểm ảnh đến từnhững sự phân bổ vân khác nhau.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học35Chương 3:Tìm kiếm ảnh dựa vào hình dạng1. Hình dạng1.1. Khái niệmvềhình dạng1.2.Đặcđiểmhìnhdạngđốivớiviệc tìm kiếmảnh2. Tìm kiếmảnh dựavàohìnhdạng2.1. Lượtđồhình dạng2.2.Độso khớpđường biên củahìnhdạng2.3. So khớpvớiảnh phát họaKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học361. Hình dạng:1.1. Khái niệmvềhình dạng:Màu sắc và vân là những thuộc tính có khái niệm toàn cục của một bức ảnh.Trong khi đó, hình dạng không phải là một thuộc tính của ảnh. Thay vì vậy,hình dạng có khuynh hướng chỉ định tới một khu vực đặc biệt của ảnh. Hayhình dạng chỉlà biên củađốitượng nàođótrongảnh.1.2.Đặcđiểmhìnhdạng vớiviệc tìm kiếmảnhHình dạng là một cấp cao hơn màu sắc và vân. Nó đòi hỏi sự phân biệt giữacác vùng để tiến hành xử lý về độ đo của hình dạng. Trong nhiều trường hợp,sự phân biệt này cần thiết phải làm bằng tay. Nhưng sự tự động hóa trongmột số trường hợp có thể khả thi. Trong đó, vấn đề chính yếu nhất là quátrình phânđoạn ảnh. Nếu quá trình phânđoạn ảnh được làm một cách chínhxác, rõ ràng và nhất là hiệu quả thì sự tìm kiếm thông tin dựa vào hình dạngcó thể có hiệu lực rất lớn.Nhận dạng ảnh hai chiều là một khía cạnh quan trọng của quá trình phân tíchảnh. Tính chất hình dạng toàn cục ám chỉ đến hình dạng ảnh ở mức toàn cục.Hai hình dạng có thể được so sánh với nhau theo tính chất toàn cục bởinhững phương pháp nhận dạng theo hoa văn, mẫu vẽ. Sự so khớp hình dạngảnh cũng có thể dùng những kỹ thuật về cấu trúc, trong đó một ảnh được môtả bởi những thành phần chính của nó và quan hệ không gian của chúng. Vìsự hiển thị ảnh là một quá trình liên quan đến đồ thị, do đó những phươngpháp so khớp về đồ thị có thể được dùng cho việc so sánh hay so khớp. Sự sokhớp về đồ thị rất chính xác, vì nó dựa trên những quan hệ không gian hầunhư bất biến trong toàn thể các phép biến đổi hai chiều. Tuy nhiên, quá trìnhso khớp về đồ thị diễn ra rất chậm, thời gian tính toán tăng theo cấp số mũtươngứng với số lượng các phần tử. Trong việc tìm kiếm dữ liệu ảnh dựaKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học37vào nội dung, ta cần những phương pháp có thể quyết định sự giống và khácnhau một cách nhanh chóng. Thông thường, chúng ta luôn đòi hỏi sự bấtbiến cả đối với kích thước của ảnh cũng như hướng của ảnh trong khônggian. Vì vậy, một đối tượng có thể được xác định trong một số hướng. Tuynhiên, tính chất này không thường được yêu cầu trong tìm kiếmảnh. Trongrất nhiều cảnh vật, hướng của đối tượng thường là không đổi. Ví dụ như: câycối, nhà cửa, ...Độ đo về hình dạng rất nhiều trong phạm vi lý thuyết của bộ môn xửlýảnh. Chúng trải rộng từ những độ đo toàn cục dạng thô với sự trợ giúp củaviệc nhận dạng đối tượng, cho tới những độ đo chi tiết tự động tìm kiếmnhững hình dạng đặc biệt. Lượt đồ hình dạng là một ví dụ của độ đo đơngiản, nó chỉ có thể loại trừ những đối tượng hình dạng không thể so khớp,nhưng điều đó sẽ mang lại khẳng định sai, vì chỉ như là việc làm của lượt đồmàu. Kỹ thuật dùng đường biên thìđặc hiệu hơn phương pháp trước, chúnglàm việc với sự hiện hữu của đường biên của hình dạng đối tượng và đồngthời cũng tìm kiếm những hình dạng đối tượng gần giống với đường biênnhất. Phương pháp vẽ phác họa có thề là phương pháp có nhiều đặc trưng rõràng hơn, không chỉ tìm kiếm những đường biên đối tượng đơn, mà cònđốivới tập những đối tượng đãđược phân đoạn trong một ảnh mà người dùngvẽ hay cung cấp. Ta sẽ đi vào chi tiết trong chương sau mô tả về hình dạngđối tượng.2. Tìm kiếm ảnh dựa vào hình dạng:2.1. Lượt đồ hình dạng:Lượtđồhình dạngđược cho rằng là dễdàng trong tính toán và nhanh trong thihành. Chúng sửdụng cảsựso sánh vềmàu sắc và vân. Vấnđềchính làđịnh nghĩabiến cho lượtđồhình dạngđượcđịnh nghĩa. Xem nhưhình dạng trongảnh là mộtvùng những giá trịmột trongảnh nhịphân, trong khi toàn thểnhững giá trịkhácđều là giá trịkhông. Một kiểucủa so khớphìnhdạngảnh là so khớphìnhchiếuKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học38thông qua hình chiếuđứng và hình chiếunằm củahìnhdạng. Giảsửrằng hình dạngcó n hàng và có m cột. Mỗihàngvàmỗi cộtlàmột bin trong lượtđồhình dạng.Tổng sốđượclưutrữtrong một bin là tổng sốnhững giá trị1 đượclưu trữtrongdòng hoặccột tươngứngđó.Điềunàyđưađếnmột lượtđồgồm có m+n bin,nhưngđiềunày cũng chỉcó ý nghĩa khi tấtcảnhữngảnh chúng ta xem xét phải cócùng một kích thước.Đểlàm cho việc so khớphìnhchiếubấtbiếnđốivớikíchthước, sốlượng bin của dòng và sốlượng bin củacộtphảiổnđịnh. Bằng cáchđịnhnghĩanhững bin từgóc trái trênđến góc phảidướicủahìnhdạng, sựchuyểnđổi bấtbiếnđãđạt được. Việc so khớphìnhchiếu không bấtbiến đốivới phép xoayảnh,nhưng nó có thểlàm việctốtvớisựxoay nhỏvà sựthiếu chính xác thuộcvềhìnhhọcởmứcđộnhỏ. Một cách khácđểlàm nó bấtbiếnđốivới phép quay là tính toántheo trục toạđộêlípvừanhất và xoay chúng chođến khi trục chính là trụcnằm ngang. Vì chúng takhông biếtnơiđâu là phía trên cùng củahìnhdạng, xoay hai khảnăng có thểxảy rađểthử. Hơnnữa, nếutrục chính và trục phụcó cùng chiều dài, thì 4 khảnăng xoayphảiđược xem xét. So khớphìnhchiếuđượcsửdụng thành công trong tìm kiếmảnh logo.Những khảnăng khácđểxây dựng lượtđồthông qua góc tiếptuyếntạimỗiđiểmảnh trên đường bao củahìnhdạng.Độ đo này thì hoàn toàn tựđộng vềmặtkích thướcvàbấtbiếnđốivớisựdịch chuyển, nhưng nó cũng không bấtbiếnđốivới xoay đốitượng, bởi vì góc tiếptuyếnđượctính từhình dạngđốivớimột hướngxácđịnh. Có một sốcách khác nhauđểgiải quyếtvấnđềnày. Cách thứnhấtlàxoay hình dạng vềtrục chính nhưđãmôtảởtrên. Một cách khácđơn giản hơnlàxoay lượtđồhình dạng. Nếulượtđồcó K bin, thì sẽcó K khảnăng xoay. Những vịtrí xoay không đúng có thểlàmảnh hưởng tốcđộcủaviệc tính toán, đặcbiệtlàtrong trường hợplượtđồvàảnh có kích thướclớn. Hoặclàlượtđồcó thểđượctiêuchuẩn hoá bởi cách chọn bin vớisốđếmlớnnhấtlàbinđầu tiên. Một vài bin lớnnhấtnênđượcthửvì có thểcó sựtồntạicủanhiễu.2.2. Độ so khớp đường biên của hình dạng:Thuật toán so khớpđường biênđòi hỏisựtrích rút và trình bày đường biên củacảảnh cần truy vấnvàảnh mang ra so khớp. Đường biên có thểđược trình bày bởiKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học39một dãy nhữngđiểmảnh hay có thểđượcxấpxỉbởimộtđa giác.Đốivớimột dãynhữngđiểmảnh, một loại so khớpcổđiển là dùng mô tảFourierđểso sánh haihình dạng với nhau. Trong toán học hàm liên tục, mô tảFourier là những hệsốcủadãy triển khai Fourier củahàmmàđịnh nghĩađường biên củahìnhdạngảnh. Trongtrường hợpđặcbiệt, hình dạngđược trình bày bởidãycủamđiểm<V0,V1,...,Vm-1>.Từnhững dãyđiểm này, một dãy củavectơđơnvị:k kk kkV VV Vv− −=+ +1 1và một dãy củanhững sai phân:∑=−− =kii i kV V l11,k>000= lcó thểđượctính.Mô tảFourier {a-M,...,a0,...,aM}sau đóđượcxấpxỉbởi:∑=−−− =mkl L jnk k nke v vLnL a1) / 2 (12) () 2(1ππNhững mô tảnày có thểđược dùngđể định nghĩađộ đo khoảng cách hình dạng.GiảsửQ làảnh truy vấn và I làảnh mang hình dạngđược so sánh với Q. Gọi{Qna}là dãy củanhững mô tảFourier choảnh truy vấn, và {Qna}làmôtảFourier choảnh. Khiđóđộ đo khoảng cách Fourier nhưsau:2 / 12) , (  − =∑− =MM nQn In Fouriea a Q I dKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học40Nhưđãmôtả, khoảng cách này chỉbấtbiếnđốivới phép tịnh tiến. Nếumànhữngbấtbiếnkhácđòi hỏi, có thểdùng sựkếthợpvớinhiềuhàmsốhọcthểgiải quyếtvấnđềtỷlệ, xoay, vàđiểm bắtđầuđểcực tiểu hoá ), (Q I dFourierNếumàđường biên được trình bày dướidạng mộtđa giác, chiềudàicủacáccạnh và góc giữa chúng có thểđược tính và dùngđểtrình bày hình dạng. Một hìnhdạng có thểđược trình bày bởimột dãy nhữngđiểmnốiliền nhau (Xi, Yi,iα), vớicặpđường thẳng giao nhau tạiđiểm (Xi, Yi) với góc lớniα. Cho một dãy Q = Q1,Q2, ..., Qncủa nhữngđiểm nốiliền nhau trình bày đường biên củađốitượng truyvấn Q và một dãy tương tựI=I1, I2, ..., Imtrình bày đường biên củađốitượng I, mụctiêu là tìm mộtánhxạtừQ tớiI màánhxạtừdãy phânđoạncủaảnh truy vấntớidãycóchiềudàitương tựphânđoạncủaảnh và sao cho cặpcủa dãy phânđoạntruyvấngầnkềmà gặptạimột gócđặc biệtαnên ánh xạtớimột cặpnhững dãy phânđoạngầnkềmà gặp nhau tạimột góc'αtương tự.Một kỹthuật so khớpđường biên khác là so khớpmềmdẻo (elasticmatching) trongđóhìnhdạng truy vấnđượclàm biến dạngđểtrởnên càng giốngvớihìnhdạngảnh mẫucàngtốt. Sựcách biệtgiữahìnhdạngảnh truy vấnvàhìnhdạng củaảnh mẫudựa vào hai thành phần chính: (1) năng lượngđòi hỏi trong quátrình biếndạng từhình dạngảnh truy vấn tớimức độphù hợpnhấtvớihìnhdạngtrongảnh mẫu. Và (2) sựđo lường vềđộgiống nhau giữahìnhdạngảnh truy vấnsau khi bịbiếndạng khớpvớihìnhdạng trongảnh mẫu.2.3. So khớp ảnh phát họa :Hệthống so khớppháthọa cho phép người dùng nhậpvàomột bảnpháthọacủanhữngđường biên chính trong mộtảnh và sau đóhệthống sẽtìm kiếmnhữngảnh màu hayảnh xám mà cóđường biên khớpnhất. Nhữngảnh màu đượctiền xửlý nhưsauđể đạtđượcmột dạng trung gian gọilàảnhđược trích rút (abstractimage).-Ápdụng phép biếnđổi affineđểgiảmkíchthướcảnh vềkích thướcchỉđịnh trước. Dùng một mặtnạtrung vịđểlọc nhiễu. Kếtquảcủabướcnàycho ra mộtảnhđược tiêu chuẩn hóaKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học41- Dò biên sửdụng thuật toán dò tìm đường biên dựa trên gradient. Dò biênđượctiến hành qua hai bước: những biên toàn cục sẽđược tìm thấy trướctiên vớimột ngưỡng toàn cụcdựa trên giá trịtrung bình và biếnđổicủagradient; sauđó, nhữngđường biên cục bộsẽđượcchọntừtoàn cụctheonhững ngưỡng cụcbộ. Kếtquảcủabước này cho raảnh gọilàảnhđãđượclọc biên (refined edge image).-Tiến hành làm mảnh và rút ngắntrênảnhđãđượclọc biên. Kếtquảcuốicùngđượcgọilàảnhđượctríchrút.Khi ngườisửdụng nhậpvào một bứcảnh phát họaởdạng thô nhưlà mộtảnh truyvấn, nó cũng lần lượtđượcđưa qua các giaiđoạnchuẩn hóa kích thước, nhịphânhóa, làm mảnh hoá, và rút gọn. Kếtquảcủa quá trình xửlý này cho ra mộtảnh gọilà bản phát họađềunét. Giờđây, bản phát họađều nét phảiđược so khớpvớinhữngảnhđược trích rútởtrên. Thuậtgiải so khớplàthuậtgiải dựavào mốitươngquan. Haiảnh sẽđược chia ra làm những hệthống lưới ô vuông.Đốivớimỗihệthống lưới ô vuông củaảnh truy vấn, tương quan cục bộvớihệthống lưới ô vuôngtươngứng củaảnh cơsởdữliệusẽđượctính.Đểthiếtthựchơn, tương quan cục bộđượctínhcho một vài những dịch chuyển khác biệt trong vịtrí trong hệthống ôlướitrênnhữngảnh cơsởdữliệuvàgiátrịtương quan cựcđại qua tấtcảnhữngdịch chuyểnlàkếtquảcủa cho hệthốngôlướiđó.Độ đo sựgiống nhau cuối cùnglà tổng củamỗitương quan cụcbộ.Độ đo khoảng cách là nghịchđảocủađộ đo sựgiống nhau này.Từnhững chú giải trên, nó có thểđượcbiểu diển lạidướidạng sau:))] ( )), ( ( ( ˆ[1) , (1g L g A shift d ax m Q I dQn n correlatio ng sketch∑=trongđóAI(g) quy cho hệthống ô lướig củaảnhđượctríchrútđược tính từảnh cơsởdữliệuI,shift(AI(g)) quy cho phiên bản đượcdịch chuyển củahệthống lướigKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học42của cùngảnhđược trích rút, và LQ(g) quy cho hệthống ô lướig củabảnhọađềunét có kếtquảtừảnh truy vấn Q.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học43PHẦN 3CÀIĐẶT VÀKẾTQUẢTHỬNGHIỆMKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học44Chương 1:Càiđặt1. Chương trình2. Phần Màu sắc3. PhầnVân4. Phần Hình dạngKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học451. Chương trình:-Chương trình gồm3 mođun riêng cho mỗi phần: màu sắc, vân và hìnhdạng.-Mỗiphầncủachương trìnhđượclập trình trên môi trường Visual C++ 7.0,vớisựhỗtrợcủathưviện lậptrìnhMFC, một thưviện liên kếttĩnh .dll củaintel hỗtrợcho việc truy xuấtảnh jpeg.-Mỗiphần là một bản demo cho cơsởlý thuyếtđãđượcnêuởphần 2.-Phầnmàu sắc, chương trình demo tập chung vào phần màu sắc là nhiềunhất, vìđây là phần khảthi và có thểứng dụngđượcliềnvàothựctếvớitốcđộvà kếtquảchấpnhậnđược.-Phần vân: chương trình làm phần tìm và so sánh vân dựavàokỹthuậtmatrậnđồng hiệnvàthống kê khác biệt ở lượt đồ xám.-Phầnhìnhdạng: chương trình làm phần so khớpảnh phát họa kếthợpvớilượtđồhình dạng.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học462. Phầnmàu sắc:Quy trình thựchiệnnhưsau:Bước1: Nhậnvàoảnh mẫu, tính lượtđồmàu HSI choảnh mẫuBước2:Đọcảnh từcơsởdữliệu:Nếucònảnh: Tính lượtđồmàu củaảnh, qua Bước3Nếuhếtảnh: KếtthúcBước 3: So sánh 2 lượtđồmàu vừa tínhđượcdựavàođộ đo nàođó.Bước4: So sánhkếtquảđộđovớingưỡng, thông báo kếtquả.Quay lạibước2.Tính lượtđồmàu:Mô hình màu đượcứng dụng vào việc cài đặtlàmôhìnhmàu HSI.Cấutrúccủalượtđồmàu nhưsau:struct ColorHistogram{unsigned int grey[5]; (1)unsigned int val[18][3][3];}Quá trình tính lượtđồmàu HSI cho việc tìm kiếm:Bước1: Nhậnvàoảnh RGB,đổisangảnh HSIBước2:Đọcgiátrịđiểm tiếp theoNếu không cóđiểm thì kếtthúc.Nếutồntạiđiểm, qua bước3.Bước3:Đọc thành phần intensity.Nếu intensity < 0.3 thì chođây làđiểm màuđen. Quay lạibước2Nếu intensity>=0.3, qua bước4Bước4: Đọc thành phầnSaturationNếu Saturation <0.08 thì chođây làđiểmảnh xám, gán giá trịtươngứng cho lượtđồmàu. Quay lạibước2.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học47Nếu Saturation>=0.08 thì chođây làđiểmảnh màu, gán giá trịtươngứng cho lượtđồmàu dựavàothành phần Hue, Saturation, vàIntensity.Quay lạibước2.2.1. Tìm kiếm theo tỉ lệ phần trăm về màu sắc:-Người dùng xác định tỉ lệ phần trăm một số màu cần tìm kiếm, nhưngkhông quan tâm đến vị trí xuất hiện của những màu này. Chúng có thể xuẩthiện khắp nơi trongảnh hoặc tập chung tại một khu vực nào đó. Ví dụ: Tìm kiếm những bức ảnh có chứa khoảng 20-30% màu đỏ, 30-50%màu trắng, 10-40% màu đen.- Cách tiến hành: Không cần phải tính lượt đồ màu mà chỉ cần đếm số lượngnhững màu được chọn để tìm kiếm.+ Màu được tìm kiếm được xếp vào một trong 167 bin của (1)+ Trong quá trình tìm kiếm, nếu điểm ảnh nào nằm trong bin có màuđược chọn thì số lượng trong bin đó tăng thêm 1.+ Nếu tỉ lệ tổng số điểm ảnh trong từng bin được chọn trên tổng sốlượng điểm ảnh của ảnh nằm trong khoảngđược đặt ra thìảnh đó thỏamãn yêu cầu tìm kiếm.2.2. Tìm kiếm theo lượt đồ màu toàn cục dựa trênảnh mẫu:-Người dùng chọn một ảnh, những ảnh tìmđược là những ảnh có sắc màugần giống với ảnh cần tìm nhất theo một ngưỡng tự chọn trước.- Cách tiến hành: Ý tưởng cách làm là so sánh lượt đồ màu toàn cục của ảnhvới những ảnh khác trong cơ sở dữ liệu. Nếu ảnh trong cơ sở dữ liệu có lượtđồ màu phù hợp với độ đo theo một ngưỡng nhất định sẽ được chọn.+ Tính lượt đồ màu của ảnh gốc như (1).+ Trong quá trình tìm kiếm, tính lượt đồ màu của từng ảnh. Sau đó so sánhnhững lượt đồ này với nhau theo các loại độ đo được chọn.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học48+ Những ảnh thỏa mãn nhu cầu tìm kiếm là những ảnh có sự giao nhau của 2lượt đồ đạt giá trị thỏa mãn ngưỡng.Độ đo được dùng : Min-Max, Euclid, độ đo khoảng cách toàn phương.2.3. Tìm kiếm theo màu chỉ định dạng lưới:-Người dùng xác định vị trí những khoảng màu sẽ xuất hiện trong tấm ảnh.Những vùng màu được chọn dưới dạng ô lưới. Người dùng có thể xác địnhđộ chia nhỏ của từng ô lưới.- Cách tiến hành : Dựa vào những ô lưới của người dùng đãấn định, tiếnhành chiaảnh trong cơ sở dữ liệu cần theo những ô lưới. Dùng mỗi màu đạidiện cho một ô lưới, tiến hành so sánh ô lưới mà người dùngấn định với ôlưới trong những ảnh vừa xác lập cho ra được theo một ngưỡng định trước.+ Xác định mức độ chia nhỏ của mức lưới. Đồng thời xác định những màuđược chọn trong các mắt lưới.+ Tương tự như trên, màu trong những mắt lưới này sẽ được xếp vào 1 trong167 bin như trong (1).+ Trong quá trình tìm kiếm, ảnh tìm kiếm sẽ được chia theo đúng tỉ lệ của ôlưới xác lập ở trên.+Ứng với những ô lưới có màu được chọn, tính lượt đồ màu của ô lướitươngứng trênảnh. Tính màu đại diện trong ô lưới của ảnh. Sau đó tiến hànhso sánh màu này với màu được chọn trong ô lưới ban đầu.+ Tổng những so sánh ô lưới trên so với một ngưỡng sẽ cho được kết quảảnh có phù hợp hay không.2.4. Tìm kiếm toàn cục theo dạng so sánh lưới dựa trênảnh mẫu:-Người dùng chỉ định ảnh mẫu với yêu cầu là: Tìm những ảnh có sắc màugần giống với ảnh này. Cách tìm kiếm này khác với cách tìm kiếm dựa trênlượt đồ màu là nó quan tâm đến vị trí của những khoảng màu trongảnh.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học49Cách tìm kiếm này không những tìm ra những ảnh có sắc màu gần giống vớiảnh mẫu mà còn giống nhau ở ví trí tươngứng những sắc màu đó.- Cách tiến hành: Ý tưởng phương pháp này giống như phương pháp so sánhlưới cục bộ có tương tác với người dùng.+ Chia lưới cho ảnh mẫu. Tính những màu đại diện cho từng ô lưới. Tạothành một mảng những màu đại diện.+ Trong quá trình tìm kiếm ảnh, mỗi ảnh tìm kiếm ta cũng tiến hành chiathành những ô lưới và tính màu đại diện cho mỗi ô lưới. Ta cũng được mộtmảng những màu đại diện.+ Tiến hành so sánh mảng màu đại diện với ngưỡng cho trước.2.5.Tìm kiếm kết hợp giữa màu chỉ định dạng lưới và toàn cục theo một ảnhmẫu:-Đây là sự kết hợp giữa phương pháp tìm toàn cục theo dạng lưới và tìm cụcbộ theo dạng lưới. Tương tự như tìm toàn cục theo dạng lưới nhưng còn chophép người dùng thay đổi khoảng màu của từng ô lưới. Những ô lưới khôngbị thay đổi khoảng màu sẽ dùng khoảng màu của ảnh mẫu đãđược chọn.- Cách tiến hành:+ Tương tự như trên, tiến hành chia lưới trênảnh mẫu.+ Nhận những giá trị của màu đã bị thay đổi trên lưới. Được mảng nhữngmàu đại diện.+ Trong quá trình tìm kiếm, mỗi ảnh tìm kiếm được chia lưới theo tỉ lệ tươngứng như trên. Sau đó, tính mảng màu đại diện.+ Tiến hành so sánh mảng màu đại diện này với nhau để tìm rađược ảnh phùhợp với yêu cầu tìm kiếmKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học503. Phầnvân:Quy trình thựchiệnnhưsau:Bước1: Nhậnvàoảnh mẫu, tính vectơvân đặctrưng choảnh mẫuBước2:Đọcảnh từcơsởdữliệu:Nếucònảnh: Tính vectơcủaảnh, qua Bước3Nếuhếtảnh: KếtthúcBước 3: So sánh 2 vectơvân vừa tínhđượcdựavàođộ đo nàođó.Bước4: So sánhkếtquảđộđovớingưỡng, thông báo kếtquả.Quay lạibước2.3.1. Tìm kiếmảnh dựa vào ma trậnđồng hiện:Kỹthuậtdùngma trậnđồng hiệnđốivớiviệc tìm kiếmảnh, quađó, vân củamỗiảnhđượcđặttrưng bởimột vectơvân, vectơnày có 5 thành phần, giá trịcủamỗi thành phầntươngứng vớinhững thành phần của các công thức dướiđây.Công thức đượcápdụng:Energy =∑∑ijdj i N] , [2Entropy = -∑∑ijd dj i N j i N] , [ log ] , [2Contrast =∑∑−ijdj i N j i] , [ ) (2Homogeneity =∑∑− +ijdj ij i N1] , [Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học51Correlation =j i ijd j ij i N j iσ σµ µ∑∑− −] , [ ) )( (Các bướctínhma trậnđồng hiệnnhưsau:Bước1:Ảnh màu nhậnvàođược chuyểnsangảnh xám (intensity)Bước 2: Tính ma trậnđồng hiệntrênảnh mức xám này.Sau bướcnày cóthểcó thêm bước2’.Bước2’: Chuẩnhoáma trậnđồng hiện.Bước 3: Tính các giá trịEnergy, Entropy, Constrast, Homogeneity,Correlation.Bước 4: Gán các giá trịvừatínhđượccho vectơvânđặttrưng.3.2. Tìm kiếmảnh dựa vào thống kê khác biệtởlượtđồxám:Kỹthuậtnày cũng tương tựnhưđốivớima trậnđồng hiện, nhưng nóthường mang lạikếtquảtìm kiếmkhảquan hơn nhiều, tốc tộcũng nhanhhơnđốivớima trậnđồng hiện. Vectơvân củatrường hợpnày cũng có 5thành phầnchính, mỗi thành phầntươngứng vớicác giátrịcủa công thứcdướiđây:Gọih[I]làlượtđồxám củaảnh.Mean =∑= 2551] [ *ii h iVariance =∑=−25512] [ * ) (ii h mean iSkewness =3 25513) var (] [ * ) (iancei h mean ii∑=−Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học52Kurtosis =34] [ * ) (25514− −∑= ii h mean iEntropy =∑=−2551]) [ ln( * ] [ii h i hCác bướctínhthống kê khác biệtởlượtđồxám nhưsau:Bước 1:Ảnh màu được chuyển sangảnh dạng xámBước 2: Tính lượtđồxám choảnh xám vừatínhđượcBước 3: Tính các giá trịmean, variance, skewness, kurtosis, entropy dựa vàocác biểuthứcởtrên.Bước 4: Gán các giá trịvừatínhđượcvàovectơKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học534. Phần hình dạng:Quy trình thựchiệnnhưsau:Bước1: Nhậnvàoảnh mẫu phát thảo.Phânđoạnảnh bằng ngưỡng.Tính lượtđồhình dạng choảnh vừa phânđoạnBước2:Đọcảnh từcơsởdữliệu:Nếucònảnh: Phânđoạnảnh, tính lượtđồhình dạng, qua Bước3Nếuhếtảnh: KếtthúcBước 3: So sánh 2 lượtđồhình dạng vừa tínhđượcdựavàođộ đo nàođó.Bước4: So sánhkếtquảđộđovớingưỡng, thông báo kếtquả.Quay lạibước2.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học54Chương 2:Kếtquảthửnghiệm1. Phần Màu sắc2. PhầnVân3. Phần Hình dạngKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học551.Phần màu sắc:Một sốkếtquảthửnghiệmmộtsốchức năng chính củachương trình.Cơsởdữliệuthửnghiệm: hơn800ảnhđủmọithểloại.1.1.Tìm kiếm với chức năng tìm kiếm dựa trên lượt đồ toàn cục:Ảnhđưa vào tìm kiếm:Ngưỡng banđầuđượcchọn là 50, cho ra kếtquảtìm kiếm nhưsau:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học56Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học57Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học58Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học59Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học60Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học61Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học62Sau khiđổingưỡng lại là 60, và tìm kiếm trong kếtquảvừa tìmđược, lặplạiquátrình tìm kiếm, ta thu đượckếtquảnhưsau:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học63Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học64Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học651.2.Tìm kiếm với chức năng tìm kiếm dựa trên phầntrămmàu:Nhậpvào: Chọn màu xanh blue (128,128,255), vớitỉlệphần trămxuấthiệntrongảnh là từ20-40%. Kếtquảthu đượcnhưsau:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học66Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học67Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học68Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học691.3.Tìm kiếm với chức năng tìm kiếm dựavịtrí màu sắc trong không gian:Chọnngưỡng là 70, vịtrí màu sắc : nữatrên củaảnh là màu trắngKếtquảthu đượcnhưsau:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học70Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học71Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học72Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học732. Phần vân:2.1. Ma trậnđồng hiện:Vân đượcđưavàokiểmtra:Vớimức ngưỡng là 0.06Kếtquảthu đượclà:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học74Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học752.1. Thống kê khác biệtvớilượtđồxám:Vân đượcđưavàokiểmtra:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học76Vớimức ngưỡng là 0.06Kếtquảthu đượclà:Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học773. Phần hình dạng:Rấttiếclàkếtquảthu được không khảquan lắm.Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học78PHẦN 4KẾTLUẬNKhoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học79Đánh giá kết quả đạt đượcNgườidùngcóthểdùng chương trình nàyđểtìm kiếmảnh theo màu sắc,vân, và hình dáng. Việc tìm kiếmảnh với tiêu chí màu có kếtquảtốt. Phùhợpvớithịgiác người. Việc sửdụng sáng tạomột hệthống tính toán lượtđồmàu HSI mớiđã làm cho việc tìm kiếmảnh dựavàomàu sắcđạtkếtquảtốt.Có thểtìm kiếm theo màu vớirấtnhiềutiêu chíđặtra.Tìm kiếmảnh theo vân và hình dạng, chương trình còn sơsài, chưađápứngđược. Vì thựcsựđây là hai mảngđềtài rấtkhó, cầncónhiềusựđầutưnghiên cứuhơn.Hướng phát triển-Kếthợp các chức năng màu sắc, vân, hình dạng lạivới nhauđểgiúp việctìm kiếm đượchiệuquảhơn. Sựkếthợpgiữa các chức năng này với nhausẽmang lạikếtquảkhảquan hơnnhiều, vì nó làm tăng khảnăng tìm kếtquảchính xác, theo nhưmong muốn.-Tổchức thành databaseảnhđốivớinhững sốlượngảnh lớncốđịnh.Điềunày sẽgiúp cho tốcđộtìm kiếmđạt giá trịcực tiểu.-Có thểphát triểnthêmđể ứng dụngđượcvàothực tế:oGiúp tìm hàng hoá trong siêu thịdựavàohìnhảnh.ooTìmảnh trên mạng.o....Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học80Tài liệu tham khảo[1] Linda G.Shapiro, George C.StockmanCOMPUTER VISIONUpper Saddle River, New JerseyPrentice-Hall, Inc 2001[2] Ratael C.Gonzalez, Richard E. WoodsDIGITAL IMAGE PROCESSINGAddison-Wesley Publishing Company, Inc 1993[3]Marius Tico, Taneli Haverinen, Pauli KuosmanenA METHOD OF COLOR HISTOGRAM CREATION FOR IMAGERETRIEVALSignal Processing LaboratoryDigital Media InstituteTampere University of TechnologyP.O. BOX 553, FIN-33101, Tampere, FINLAND,[email protected][4] Charles E. Jacobs, Adam Finkelstein, David H. SalesinFAST MULTIRESOLUTION IMAGE QUERYINGDepartment of Computer Science and EngineeringUniversity of WashingtonSeattle, Washington 98195Khoa CNTT - ÐH KHTN TP.HCMKhoa CNTT - ÐH KHTN TP.HCMLuận văn tốt nghiệp đại học81[5] Alberto Del BimboVISUAL INFORMATION RETRIEVALDepartment of Science of InformationUniversity of Fizenze Finenze, ItalyMORGAN KAUFMANN, 1999