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