Sử dụng kỹ thuật phân lớp dữ liệu để tính toán các bins màu động trong tra cứu ảnh dựa trên màu sắc

Nguyễn Văn Tới và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 49 - 53 49 SỬ DỤNG KỸ THUẬT PHÂN LỚP DỮ LIỆU ĐỂ TÍNH TOÁN CÁC BINS MÀU ĐỘNG TRONG TRA CỨU ẢNH DỰA TRÊN MÀU SẮC Nguyễn Văn Tới*, Phạm Việt Bình, Nguyễn Tiến Thành ĐH Công nghệ Thông tin & Truyền thông – ĐH Thái Nguyên TÓM TẮT Kỹ thuật tra cứu dựa trên màu sắc là một trong những hƣớng tiếp cận cơ bản trong tra cứu ảnh. Trong kỹ thuật này, ngƣời ta chia không gian màu ra thành các bins. Việc chia thành các bins màu có kích thƣớc bằng nhau và cố định dẫn đến một số hạn chế trong việc tra cứu nhƣ không tính đến tính tƣơng đồng giữa các màu khi phân các pixel vào các bins, vấn đề về tăng giảm độ sáng ảnh. Bài báo này trình bày một cách tính toán các bins màu mềm dẻo sử dụng kỹ thuật phân lớp dữ liệu. Chúng tôi đã thử nghiệm với thuật toán K-Means trên cơ sở dữ liệu ảnh MISC [4] và cơ sở dữ liệu ảnh IFIT (Thƣ viện ảnh của Khoa Công nghệ thông tin-ĐH Thái Nguyên). Từ khóa: Kỹ thuật phân lớp dữ liệu, bins màu động,thuật toán K-means GIỚI THIỆU* Cùng với sự phát triển nhanh chóng của công nghệ phần cứng trong đó có các thiết bị thu nhận ảnh, lƣu trữ dữ liệu, lƣợng dữ liệu ảnh trong các lĩnh vực và trong đời sống ngày càng gia tăng. Từ thực tế trên, nhu cầu lƣu trữ, quản lý và tra cứu ảnh đƣợc đặt ra. Tra cứu ảnh là việc tìm kiếm từ một cơ sở dữ liệu (CSDL) ảnh ra một ảnh theo một yêu cầu nào đó. Đã có nhiều hƣớng tiếp cận cho việc nghiên cứu vấn đề này (xem [1]). Một trong những hƣớng tiếp cận chính đó là tra cứu ảnh dựa vào màu sắc. Kỹ thuật cơ sở tra cứu ảnh dựa trên màu sắc sẽ đƣợc giới thiệu trong phần 2. Các kỹ thuật cơ sở tra cứu ảnh dựa trên màu sắc còn một số hạn chế. Những hạn chế này đƣợc giới thiệu trong phần 3 cùng với một số hƣớng tiếp cận khắc phục của một số tác giả. Trong bài báo này, chúng tôi đƣa ra một hƣớng khắc phục khác cho những hạn chế của kỹ thuật cơ sở. Ý tƣởng của cách khắc phục này là cải tiến việc tính toán các bins màu bằng cách sử dụng kỹ thuật phân lớp dữ liệu. Ý tƣởng này đƣợc trình bày trong phần 4. Việc thực nghiệm với thuật toán phân lớp dữ liệu K-Means và kết quả đƣợc trình bày trong phần 5. Trong phần 6, chúng tôi đƣa ra một số kết luận và hƣớng nghiên cứu tiếp theo. * Tel: 0912847077; Email: nvtoicntt@gmail.com KỸ THUẬT CƠ SỞ TRA CỨU ẢNH DỰA TRÊN MÀU SẮC Ý tƣởng của các kỹ thuật tra cứu ảnh trên cơ sở màu là tra cứu từ CSDL ảnh những ảnh có màu cảm nhận tƣơng tự ảnh truy vấn hay phù hợp với mô tả của ngƣời sử dụng. Ngƣời ta đã đề xuất một số kỹ thuật khác nhau nhƣng ý tƣởng chủ đạo là nhƣ nhau. Mỗi ảnh trong CSDL đƣợc biểu diễn bằng ba kênh của không gian màu. Không gian màu hay sử dụng nhất là RGB. Mỗi kênh màu đƣợc số hóa thành m khoảng. Nhƣ vậy, tổng số tổ hợp màu rời rạc (gọi là bins) sẽ là n = m3. Thí dụ, nếu mỗi kênh màu đƣợc số hóa thành 16 khoảng thì sẽ có 4096 bins. Biểu đồ màu H(M) là véc tơ (h1, h2, ..., hj, ..., hn), trong đó phần tử hj biểu diễn tổng số pixel trong ảnh M rơi vào bin j (j=1,..,n). Biểu đồ màu là véc tơ đặc trƣng, sẽ đƣợc lƣu trữ làm chỉ mục ảnh. Khi tra cứu ảnh, biểu đồ màu của ảnh truy vấn đƣợc tính toán. Sau đó, tính toán khoảng cách giữa biểu đồ màu của ảnh truy vấn và từng biểu đồ màu của các ảnh trong CSDL ảnh. Kết quả trình diễn cho ngƣời sử dụng là k ảnh đầu tiên có khoảng cách nhỏ nhất. Đã có nhiều độ đo khoảng cách biểu đồ màu giữa hai ảnh I và H đƣợc đề xuất. Ví dụ nhƣ: + Độ đo L-1 (thuộc nhóm Minkowski-form r=1):    n l ll jiJId 1 ),( . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyễn Văn Tới và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 49 - 53 50 + Độ đo khoảng cách Euclide (L-2) thuộc nhóm Minkowski-form r=2:     n l ll jiJId 1 2 ),( . MỘT SỐ KỸ THUẬT TĂNG CƢỜNG KỸ THUẬT CƠ SỞ ĐÃ ĐƢỢC ĐỀ XUẤT Kỹ thuật tra cứu ảnh trên cơ sở màu cơ bản có nhiều hạn chế. Trong phần này chúng tôi giới thiệu một số hạn chế và cách khắc phục đã đƣợc đề xuất. • Hạn chế thứ nhất của kỹ thuật cơ sở là không sử dụng tính tƣơng đồng giữa các màu. Khi đó, hai ảnh với màu cảm nhận tƣơng đồng nhƣng không có màu chung thì khoảng cách của chúng sẽ lớn, có thể là cực đại. Điều này xảy ra vì: + Ngƣời sử dụng nhiều khi không chỉ quan tâm đến các ảnh có màu chính xác nhƣ câu truy vấn mà còn quan tâm đến ảnh có màu cảm nhận tƣơng tự. + Màu của ảnh có thể thay đổi do nhiễu hay do thay đổi độ sáng. Với hạn chế thứ nhất này, một số tác giả đã đƣa ra những cách khắc phục nhƣ: Niblack [5] đƣa ra thƣớc đo mức độ giống nhau trong đó quan tâm đến đóng góp các màu cảm nhận tƣơng tự. Chan [6] đề xuất kỹ thuật tính toán khoảng cách màu trong đó các giá trị biểu đồ màu đƣợc điều chỉnh trên cơ sở mức độ tƣơng tự màu. Lu và Phillips [2] đƣa ra hƣớng tiếp cận sử dụng biểu đồ trọng số cảm nhận (PWH – perceptually weighted histogram). • Hạn chế thứ hai là không sử dụng quan hệ không gian giữa các pixel. Để giải quyết vấn đề này, Lu và Phillips [2] đƣa ra hƣớng tiếp cận là tách màu nền khỏi màu cận cảnh (phân đoạn ảnh) sau đó biểu đồ màu nền và biểu đồ màu cận cảnh đƣợc tính toán và sử dụng. • Hạn chế thứ ba là không gian màu lựa chon đƣợc lƣợng tử hóa đồng nhất mặc dù các màu điểm ảnh không phân bổ đồng nhất trong không gian màu. Wan và Kuo [7] đƣa ra giải pháp lƣợng tử hóa màu không đồng nhất. Để khắc phục những nhƣợc điểm của phƣơng pháp cơ sở, hƣớng tiếp cận lựa chọn không gian màu thích hợp cũng đã đƣợc đề cập. SỬ DỤNG KỸ THUẬT PHÂN LỚP DỮ LIỆU ĐỂ TÍNH TOÁN CÁC BINS MÀU Trong phần này, chúng tôi trình bày một hƣớng tiếp cận nhằm khắc phục hạn chế thứ nhất và hạn chế thứ ba nêu trên của kỹ thuật cơ sở. Hƣớng tiếp cận mà chúng tôi đƣa ra là cải tiến việc tính toán các bins màu bằng cách sử dụng kỹ thuật phân lớp dữ liệu. Giả sử ta muốn chia không gian màu ra thành k bins. Thay vì chọn các điểm chia cố định và đều nhau trên các kênh màu thì chúng ta sử dụng kỹ thuật phân lớp dữ liệu để phân các pixel của ảnh ra thành k lớp. Khi đó mỗi lớp sẽ là một bins. Khi phân lớp, mỗi pixel đƣợc coi là một phần tử. Toàn bộ các pixel của ảnh là một tập các phần tử. Chúng ta áp dụng kỹ thuật phân lớp để chia tập các phần tử này ra thành k lớp. Một số nhận xét: + Các pixel thuộc cùng một bins sẽ có màu tƣơng tự nhau. + Khắc phục đƣợc hạn chế thứ nhất (trong trƣờng hợp ảnh bị tăng giảm độ sáng). + Khắc phục hạn chế thứ ba, vì các bins ở đây không cố định, không phải là đƣợc chia đồng nhất mà phụ thuộc vào bản thân dữ liệu ảnh. + Việc tính toán các bins phức tạp. Hình 1 minh họa sự so sánh việc tính toán các bins màu cố định, đồng nhất và các bins màu đƣợc tính toán bằng kỹ thuật phân lớp dữ liệu. Trong hình 1(a), lƣợc đồ phía trên là histogram của ảnh I, lƣợc đồ phía dƣới là của ảnh J. Ảnh J thu đƣợc từ ảnh I bằng cách tăng độ sáng. Nhƣ vậy, khi ta phân chia các bins cố định, đồng nhất thì khoảng cách giữa hai ảnh này sẽ rất lớn. Còn trong hình 1(b) là hình ảnh các bins màu đƣợc tính toán bằng cách sử dụng kỹ thuật phân lớp dữ liệu. Nếu sử dụng cùng một phƣơng pháp phân lớp dữ liệu mà kết quả phƣơng pháp này chỉ phụ thuộc vào bản thân tập dữ liệu đầu vào thì sẽ cho kết quả là hai biểu đồ màu của ảnh I và J giống nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyễn Văn Tới và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 49 - 53 51 Hình 1. (a) Các bins màu đồng nhất, cố định (b) Các bins màu được tính toán bằng kỹ thuật phân lớp dữ liệu THỰC NGHIỆM Chúng tôi tiến hành thực nghiệm với thuật toán K-Means [3]. Khi áp dụng thuật toán K- Means cho việc tính toán các bins màu, khoảng cách giữa hai phần tử (hai màu) trong không gian màu RGB mà chúng tôi sử dụng là khoảng cách Euclide. Các điểm trung tâm xuất phát của các cụm đƣợc chỉ định theo cùng một nguyên tắc đối với các ảnh khác nhau. Ví dụ, nếu ảnh có bảng màu thì k điểm trung tâm đƣợc lấy là k phần tử cách đều nhau trong bảng màu. Chúng tôi tiến hành cài đặt thử nghiệm với Visual C++ 6.0 và chạy thử nghiệm với nhiều CSDL ảnh khác nhau. Kết quả thực nghiệm cho thấy phƣơng pháp chúng tôi đề xuất cho kết quả giống với kỹ thuật cơ sở trong trƣờng hợp bình thƣờng; tốt hơn kỹ thuật cơ sở trong trƣờng hợp ảnh tăng giảm độ sáng. Khi xuất hiện ảnh trong CSDL là ảnh thu đƣợc từ ảnh truy vấn bằng cách tăng hay giảm độ sáng thì phƣơng pháp cơ sở không tìm ra, còn phƣơng pháp đƣợc đề xuất trong bài báo này đã tìm ra. Tuy nhiên, chúng ta dễ nhận ra nhƣợc điểm của phƣơng pháp này là thời gian tính toán bins màu là lớn hơn kỹ thuật cơ sở. Hình 2 và hình 3 minh họa một số kết quả thực nghiệm. KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU TIẾP THEO Chúng tôi đã đề xuất ý tƣởng sử dụng kỹ thuật phân lớp dữ liệu để tính toán các bins màu nhằm khắc phục nhƣợc điểm cúa kỹ thuật cơ sở tra cứu ảnh dựa trên màu sắc. Kỹ thuật này cho kết quả tốt hơn kỹ thuật cơ sở trong trƣờng hợp ảnh tăng giảm độ sáng, tuy nhiên tốc độ tính toán các bins màu chậm hơn. Hƣớng nghiên cứu tiếp theo của chúng tôi sẽ là:  Nâng cao hiệu quả của kỹ thuật phân lớp dữ liệu áp dụng cho việc tính toán các bins màu.  Thực nghiệm với các độ đo khác nhau, kết hợp với các cải tiến đã có nhƣ sử dụng quan hệ không gian giữa các pixel. c H(c) c H(c) (a) H(c) c H(c) c (b) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyễn Văn Tới và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 49 - 53 52 Hình 2. Kết quả thực nghiệm với 100 ảnh của CSDL ảnh MISC [4] (2 truy vấn với 2 ảnh truy vấn khác nhau). Kết quả liệt kê 5 ảnh giống ảnh truy vấn nhất Hình 3. Kết quả thực nghiệm với 100 ảnh của CSDL ảnh MISC thêm 2 ảnh: 0a.jpg (thu được từ 0.jpg bằng cách tăng độ sáng) và 100a.jpg (thu được từ 100.jpg bằng cách giảm độ sáng). Kết quả thực hiện 2 truy vấn. Kết quả liệt kê 5 ảnh giống ảnh truy vấn nhất 100.jpg ảnh truy vấn 100.jpg Kết quả giống nhau của kỹ thuật cơ sở và kỹ thuật đề xuất 112.jpg 31.jpg 116.jpg 108.jpg 0.jpg ảnh truy vấn 0.jpg 49.jpg 23.jpg 40.jpg 34.jpg Kết quả giống nhau của kỹ thuật cơ sở và kỹ thuật đề xuất 0.jpg 0a.jpg 49.jpg 40.jpg 23.jpg 23.jpg 49.jpg 0.jpg 34.jpg 40.jpg Kết quả của phương pháp có dùng kỹ thuật phân lớp dữ liệu (tìm ra ảnh 0a.jpg là ảnh 0.jpg được tăng độ sáng): Kết quả của kỹ thuật cơ sở (không đưa ra ảnh 0a.jpg): 100.jpg ảnh truy vấn Kết quả của kỹ thuật sử dụng phân lớp dữ liệu (đưa ra ảnh 100a.jpg): 108.jp g 116.jpg 100.jpg 31.jpg 112.jpg Kết quả của kỹ thuật cơ sở (không đưa ra ảnh 100a.jpg, là ảnh 100.jpg được giảm độ sáng): 116.jp g 100a.jpg 100.jpg 108.jp g 112.jpg Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nguyễn Văn Tới và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 49 - 53 53 TÀI LIỆU THAM KHẢO [1]. Đặng Văn Đức, Hệ quản trị CSDL đa phương tiện, Giáo trình dành cho lớp Cao học - Khoa Công nghệ thông tin – Đại học Thái Nguyên. [2]. Guojun Lu; Phillips, J., (1998), Using perceptually weighted histograms for colour-based imageretrieval, Signal Processing Proceedings, 1998. ICSP apos’98. Fourth International Conference on Volume 2, Issue, Page(s):1150 - 1153. [3]. J. B. MacQueen, (1967), Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297. [4]. Jame Z Wang, J. Li. CSDL ảnh MISC, [5]. James Hafner, Harpreet S. Sawhney, Will Equitz, Myron Flickner, Wayne Niblack, (July 1995), Efficient Color Histogram Indexing for Quadratic Form Distance Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 7, pp. 729-736. [6]. S. K. Chan, National University of Singapore, (1994), Content-based Image Retrieval, MSc thesis. Xia Wan; Kuo, C.-C.J., (Sep 1998), A new approach to image retrieval with hierarchical colorclustering, Circuits and Systems for Video Technology, IEEE Transactions on Volume 8, Issue 5, Page(s):628 – 643 ABSTRACT USING DATA CLUSTERING TECHNIQUE FOR CALCULATING FLEXIBLE COLOR BINS IN SEARCHING IMAGES BASED ON COLORS Nguyen Van Toi * , Pham Viet Binh, Nguyen Tien Thanh College of Information Technology and Communication – TNU Techniques based on color is one of the basic approach in the image retrieval. In this technique, we divide the color space into bins. Divided the color space into equal and fixed size color bins causes some limitations as to be unused compatibility between the color of the pixel when add it into the bins, the increased, reduction of image brightness. This article presented a calculation of the color bins flexible use of the data clustering technique. We tested with the algorithm K-Means based on image data misc [4] and the database image IFIT (Gallery of the Faculty of Information Technology - Thai Nguyen University). Key words: Data clustering technique, flexible color bins, the algorithm K-Means * Tel: 0912847077; Email: nvtoicntt@gmail.com Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên