Truy vấn ảnh dựa trên đặc trưng trích từ phép biến đổi curvelets cho các thành phần của không gian màu HSV

Nội dung text: Truy vấn ảnh dựa trên đặc trưng trích từ phép biến đổi curvelets cho các thành phần của không gian màu HSV

1. TRUY VẤN ẢNH DỰA TRÊN ĐẶC TRƯNG TRÍCH TỪ PHÉP BIẾN ĐỔI CURVELETS CHO CÁC THÀNH PHẦN CỦA KHÔNG GIAN MÀU HSV TÓM TẮT Trong bài báo này, chúng tôi trình bày một phương pháp trích đặc trưng mới, áp dụng cho truy vấn ảnh màu. Theo đó, chúng tôi đã biểu diễn ảnh sang không gian màu HSV, sau đó thực hiện biến đổi curvelets cho từng thành phần màu Hue, Saturation, Value của ảnh. Các đặc trưng của ảnh thu được bằng cách tính toán giá trị trung bình và độ lệch chuẩn trên các hệ số curvelets thu được sau biến đổi. Phương pháp đề xuất đã được thực nghiệm truy vấn trên cơ sở dữ liệu ảnh OBJ, Coil-100 và WANG. Chúng tôi đã thấy rằng phương pháp mới đã cải thiện đáng kể độ chính xác truy vấn ảnh so với những nghiên cứu trước đây. A – GIỚI THIỆU Trong nhiều năm qua, truy vấn ảnh theo nội dung (Content based image retrieval - CBIR) đã có nhiều bước phát triển cũng như đã ứng dụng trong thực tế. Tuy nhiên, vấn đề nâng cao hiệu quả giải thuật trích đặc trưng ảnh và giảm thời gian truy vấn vẫn đang được nghiên cứu. Xu hướng nghiên cứu trong nhiều năm trở lại đây là cải tiến phương pháp trích những đặc trưng cơ bản của ảnh, phối hợp các đặc trưng này vào truy vấn. Cùng với xu hướng đó, việc ứng dụng các công cụ toán học mới (Wavelets, curvelets, contourlets, ) vào truy vấn ảnh đã đạt nhiều kết quả khả quan và vẫn không ngừng được phát triển. Biến đổi curvelets [1] là biến đổi đa phân giải và đa hướng, có khả năng nắm bắt thông tin các cạnh biên của ảnh rất hiệu quả. Nó được thiết kế để vửa kế thừa vừa khắc phục được những nhược điềm của pháp biến đổi wavelets vốn rất nổi tiếng và biến đổi Gabor filter. Một số nghiên cứu gần đây [2], [3] áp dụng biến đổi curvelets vào truy vấn ảnh texture đã đạt được nhiều kết quả quan trong cho thấy tiềm năng vượt trội của curvelets. Thế hệ đầu của biến đổi Curvelets được giới thiệu vào năm 2000 dựa trên nguyên lý biến đổi ridgelets [4] và biến đổi Random. Năm 2005, Candes et al. [5] giới thiệu thế hệ thứ hai của biến đổi curvelets áp dụng phương pháp biến đổi Fourier nhanh (FFT) vào tính toán và được gọi là biến đổi curvelets rời rạc nhanh (FDCT). Hai phiên bản của biến đổi curvelets nhanh được phát triển song song nhau đó là: curvelets via USFFT và curvelets via Wrapping đã cho thấy hiệu quả tốt trong nhiều ứng dụng của xử lý ảnh. Tuy nhiên, việc phân tích thuật toán của hai giải pháp đã cho thấy biến đổi curvelets dựa trên Wrapping được cho là đơn giản, dễ hiểu và dễ thực hiện hơn phiên bản kia. Độ phức tạp tính toán của nó chỉ là (푛2 log 푛) cho mảng có kích thước 푛 × 푛 và trong thực tế, chi phí tính toán của nó không vượt hơn 6 – 10 lần biến đổi FFT 2D (theo các nghiên cứu trước đây). Chính vì vậy mà chúng tôi đã chọn biến đổi curvelets dựa trên Wrapping để áp dụng vào trích đặc trưng ảnh, sử dụng trong hệ thống truy vấn ảnh. Trong bài báo này, chúng tôi dùng đặc trưng curvelets truy vấn trên cơ sở dữ liệu ảnh màu. Chương trình truy vấn thực hiện theo sơ đồ hình 1. Hệ thống CBIR bao gồm hai giai đoạn xử lý: Giai đoạn offline và online. Trong, giai đoạn offline, hệ thống sẽ thực hiện việc tạo dựng danh sách dữ liệu chứa đựng thông tin các tệp ảnh trong cơ sở dữ liệu truy vấn. Đặc trưng của từng tệp tin ảnh sẽ được trích dựa trên giải thuật quy định của hệ thống và các đặc 1
2. trưng này sẽ được lưu trữ vào cơ sở dữ liệu đặc trưng theo thứ tự của danh sách dữ liệu. Việc tạo dựng cơ sở dữ liệu đặc trưng thường mất rất nhiều thời gian tính toán, thời gian hoàn tất tỷ lệ thuận với kích thước cơ sở dữ liệu truy vấn. Quá trình này chạy ngầm trong hệ thống, chỉ thực hiện một lần và chỉ phải tiến hành tính toán lại khi cần cập nhật cơ sở dữ liệu. Giai đoạn thứ hai là truy vấn ảnh (giai đoạn online), đặc trưng ảnh yêu cầu được trích và so sánh với cơ sở dự liệu đặc trưng để tìm ra những ảnh có độ tương đồng gần nhất với ảnh đưa vào truy vấn. Thời gian thực hiện trong giai đoạn offline không tính vào thời gian truy vấn ảnh mà chỉ có thời gian rất ngắn của giai đoạn online ảnh hưởng đến thời gian truy vấn ảnh, do vậy hiệu suất về thời gian truy vấn vẫn được đảm bảo. Thời gian truy vấn chịu sự ảnh hưởng bởi độ phức tạp của giải thuật trích đặc trưng, phương pháp đo độ tương đồng và số lượng ảnh kết quả muốn hiển thị. Theo đó, độ phức tạp của giải thuật càng cao và số lượng ảnh kết quả muốn trả về càng lớn thì thời gian tính toán càng nhiều. Hình 1 Sơ đồ khồi hệ thống truy vấn ảnh (CBIR) B – NỘI DUNG 1. Giài thuật trích đặc trưng Phương pháp trích đặc trưng trong trường này (hình 2) dựa trên việc chuyển đổi không gian màu của ảnh RGB sang không gian HSV. Sau đó mỗi thành phần H, S, V của ảnh được đưa vào biến đổi curvelets. Giá trị trung bình và độ lệch chuẩn được tính toán trên các băng con của biến đổi curvelets để hình thành vector đặc trưng của ảnh. Như vậy, vector đặc trưng của một ảnh bao gồm 3 thành phần FH, FS, FV. Mỗi thành phần này chứa giá trị trung bình và độ lệch chuẩn của các hệ số curvelets tương ứng. 2. Phương pháp tính toán đặc trưng curvelets. Biến đổi curvelet dựa trên wrapping được áp dụng trên mỗi thành phần màu của ảnh để tạo ra các hệ số curvelet ở các tỉ lệ và hướng khác nhau sau đó lưu trữ vào các băng con (subbands). Trị trung bình và độ lệch chuẩn của mỗi băng con được tính toán để tạo thành vector đặc trưng đại diện cho ảnh. 2
3. Hình 2 Giải thuật trích đặc trưng curvelet cho ảnh từ các thành phần Hue Saturation, Value biểu diễn ảnh màu. Giá trị trung bình của mỗi băng con ở tỉ lệ a, hướng θ được tính như sau: ( ,휃) 휇 = (1) 휃 × Trong đó, M, N là kích băng con curvelets; ( , 휃) = ∑ ∑ | 푣푒푙푒푡 휃( , )|, là năng lượng của ảnh được biến đổi curvelet ở tỉ lệ a và hướng θ. Độ lệch chuẩn hóa của mỗi băng con ở tỉ lệ a, hướng θ: ∑ ∑ (| 푣푒푙푒푡 ( , )|−휇 )2 휎 = √ 휃 휃 (2) 휃 × Các giá trị này tạo thành vector đặc trưng curvelet cho 1 thành phần màu: = {(휎11, 휎21, , 휎2 , 휎3, , 휎3 , 휎퐽1, 휇11, 휇21, , 휇2 , 휇31, , 휇3 , , 휇퐽1)} (3) Kết quả tổng hợp 3 vector f tương ứng với thành phần H, S và V của ảnh chính là vector đặc trưng của ảnh. Trong miền tần số, curvelet ở góc θ tạo ra hệ số giống như ở góc θ +π. Do đó chỉ cần tính toán giá trị trung bình và độ lệch chuẩn hóa của nửa đầu trong tổng số băng con ở mỗi tỉ lệ. Sau quá trình trích đặc trưng các ảnh trong cơ sở dữ liệu sẽ được biễu diễn bởi vector đặc trưng curvelet f, và lưu trữ vào cơ sở dữ liệu đặc trưng phục vụ quá trình truy vấn sau đó. 3. Phương pháp đánh giá hiệu quả của quá trình truy vấn Trong CBIR, precision - recall là phương pháp đo được dùng rộng rãi nhất để đánh giá hiệu quả truy vấn ảnh. Độ chính xác được định nghĩa bởi P: 표.표 푒푙푒푣 푛푡 푖 푒푠 푒푡 푖푒푣푒 푃 = = (4) 표푡 푙 푛표.표 푖 푒푠 푒푡 푖푒푣푒 + 3
4. Độ phủ được định nghĩa bởi R: 표.표 푒푙푒푣 푛푡 푖 푒푠 푒푡 푖푒푣푒 푅 = = (5) 표푡 푙 푛표.표 푒푙푒푣 푛푡 푖 푒푠 푖푛 + Trong đó A là số ảnh có liên quan tìm được trong truy vấn, B là số ảnh không liên quan tìm được, C là số ảnh có liên quan nhưng không tìm được. Độ chính xác cho biết mức độ chính xác của quá trình truy vấn và độ phủ thể hiện khả năng truy vấn được các ảnh liên quan trong cơ sở dữ liệu. P, R có giá trị trong khoảng [0, 1]. Một hệ thông truy vấn được gọi là lý tưởng khi P, R đều ở mức cao. 4. Kỹ thuật đo đạc độ tương đồng Trong, hệ thống CBIR, khi các đặc trưng của ảnh truy vấn và ảnh trong cơ sở dữ liệu được trích xuất, thì vấn đề tiếp theo là làm thế nào để xét mức độ giống nhau của các ảnh dựa trên những đặc trưng đó. Các kỹ thuật đo độ tương đồng sẽ trả lời câu hỏi đó. Có nhiều phép đo khác nhau được ứng dụng như là: Minkowski, Mahalanobis, Cosine, Kullback-Leibler divergence, Jeffrey-Divergence, Chebyshev Gọi U = {U0, U1, , UN-1} và V = {V0, V1, , VN-1} lần lượt là vector truy vấn và vector tham chiếu. Định nghĩa phép đo Euclidean (L2): 1 −1 2 2(푈, ) = (∑푖=0 (푈푖 − 푖) )2 (6) C – KẾT QUẢ Trong phần này, chúng tôi trình bày theo cách so sánh kết quả truy vấn của phương pháp đề xuất và phương pháp sử dụng biến đổi curvelets thông thường. Một số kết quả được so sánh với các nghiên cứu trước đây nhằm thể hiện tính ưu việt của phương pháp mới. Lưu ý rằng, đặc trưng curvelets được thực hiện bằng cách biến đổi curvelets cho ảnh, sau đó tính toán đạc trưng từ các băng con thu được sau biến đổi theo công thức 1, 2, 3. Đặc trưng curvelets HSV thì được tính riêng rẽ cho mỗi thành phần màu HSV của ảnh. Vì thế độ dài của vector đặc trưng curvelets HSV gấp 3 lần Đặc trưng curvelets. 1. Khảo sát truy vấn trên tập ảnh OBJ Quá trình thực hiện như sau: cho ngưỡng số ảnh kết quả trả về tăng dần từ 1 đến 60 ảnh, bước tăng của Rn là 1. Mỗi lần một ảnh được đưa vào truy vấn, kết quả truy vấn trả về số ảnh có liên quan với ảnh truy vấn trên một ngưỡng Rn nhất định, và độ chính xác truy vấn ảnh cũng được tính toán. Sau khi tất cả ảnh trong cơ sở dữ liệu đã được dùng làm ảnh truy vấn, ta được một tập các giá trị độ chính xác truy vấn ứng với ngưỡng Rn xác định. Giá trị trung bình cho độ chính xác trên ngưỡng Rn này được tính và lưu trữ. Quá trình kết thúc khi 60 giá trị độ chính xác truy vấn trung bình theo 60 giá trị Rn được tính xong (hình 3). Qua quá trình khảo sát truy vấn trên tập ảnh OBJ, ta thấy hiệu quả truy vấn của phương pháp đề xuất đạt hiệu quả cao hơn phương pháp dùng đặc trưng curvelet thông thường đã thực hiện trong chương 3. Độ chính xác trung bình truy vấn theo giải thuật đề xuất lớn hơn rất nhiều so với giải thuật trích đặc trưng curvelet thông thường. Ví dụ PCHSV = 60,06 % > PC = 44,75 % khi Rn = 5 bằng với số ảnh trong 1 thể loại ảnh của tập ảnh này. Thêm nữa, kết quả thực nghiệm còn cho thấy khi ngưỡng Rn = 20 ảnh, thì độ phủ trung bình dùng đặc trưng đề xuất đã đạt tới 82,19 %; trong 4
5. khi độ phủ của truy vấn dùng đặc trưng curvelet thông thường chỉ là 64,6 % và chỉ khi Rn = 57 ảnh thì độ phủ của truy vấn trường hợp này mới đạt con số 81,88 %. 100 Curvelet HSV 80 Curvelet 60 40 Precision 20 0 20 30 40 50 60 70 80 Recall Hình 3 So sánh đường cong PR của truy vấn ảnh trên tập OBJ của đặc trưng curvelet HSV với curvelets. Kết quả khảo sát thời gian truy vấn của thực nghiệm này cho thấy rằng hiệu quả về thời gian tính toán trên đặc trưng đề xuất cũng đạt yêu cầu. So sánh giữa 2 đặc trưng thì sự chênh lệch nhau không đáng kể, chỉ nằm trong khoảng 0,2 giây. Bảng 4.1 Thời gian tính toán đặc trưng và thời gian truy vấn ảnh trong thực nghiệm truy vấn tập ảnh OBJ với 2 loại đặc trưng curvelet HSV và đặc trưng curvelet thông thường. Thời gian truy vấn trung bình / Thời gian trích đặc trưng ảnh Loại đặc Tính toán cho 265 ảnh Thời gian trung bình Số ảnh kết Số ảnh kết quả: trưng 320×240 pixels cho 1 ảnh quả: 10 100 Curvelet 100(giây) 0,377 (giây) 0,68 (giây) 0,72(giây) HSV Curvelet 80 (giây) 0,3 (giây) 0,5 (giây) 0,54 (giây) . Hình 4 so sanh truy vấn ảnh image49_1.jpg trong cơ sở dữ liệu OBJ giữa đặc trưng curvelets HSV bên trái, đặc trưng curvelets bên phải 2. Truy vấn trên tập ảnh Coil-100: 7200 ảnh/100 thể loại Trong khảo sát này, chúng tôi thực hiện biến đổi curvelets với các mức phân giải 4, 5 và 6. Kết quả so sánh độ chính xác và thời gian truy vấn ảnh được cho trong bảng 1. Ta thấy thời 5
6. gian tính toán cho đaặc trưng đề xuất tuy cao hơn đặc trưng curvelets nhưng đặc trưng Curvelets HSV đã cải thiện rất đáng kể độ chính xác truy vấn ảnh. Bảng 1: So sánh đặc trưng curvelets và đặc trưng đề xuất (số ảnh kết quả trả về là Rn = 50 ảnh) Thời gian tính Curvelets Mức phân giải Curvelets Thời gian tính toán toán HSV 4 56,56 % 685 (s) 68,76 % 885 (s) 5 58,54% 810 (s) 71,27% 1161 (s) 6 60,95% 1035 (s) 73,16 % 1842 (s) Hình 5 Kết quả trả về 50 ảnh trong truy vấn ảnh obj2_0.png trong tập Coil-100 sử dụng đặc trưng curvlet HSV bên trái, đặc trưng curvelets bên phải. 3. Tập ảnh WANG: 1000 ảnh/10 thể loại Khi khảo sát trên toàn tập dữ liệu ở ngưỡng Rn= 100 ảnh thì hiệu quả truy vấn của đặc trưng đề xuất cũng được cải thiện đáng kể, chênh lệch giữa hai cột giá trị trung bình (hình 6) là 5,13%. 100 80 60 40 Độ chính Độ% chính xác 20 0 Thể loại ảnh Curvelet HSV 4 mức Curvelet 4 mức Hình 6 Khảo sát truy vấn trên từng class của cơ sở dữ liệu ảnh WANG với Rn = 100 ảnh. 6
7. Trong thực nghiệm này, chúng tôi truy vấn cho 5 class ảnh được chọn trong tập ảnh WANG (Buses, Dinosaurs, Elephants, Flowers, Horses), áp dụng tính toán với số ảnh kết quả là Rn = 100. Biến đổi curvelets được thực hiện ở 4 mức phân giải. Các kết quả đạt được đem so sánh với kết quả tham chiếu được so sánh với các giải thuật truy vấn dùng đặc trưng wavelet correlogram [6] Contourlet co-occurrence [5]. Truy vấn ảnh dựa trên đặc trưng curvelet HSV cho hệu quả truy vất tốt nhất, kế đến là đặc trưng curvelet thông thường, các phương pháp khác cho hiệu quả kém hơn. Bàng 2: So sánh hiệu quả của phương pháp đề xuất với các nghiên cứu trước đây Thể loại ảnh Phương pháp Dinosau Elephan Flower Horse Trung Buses rs ts s s bình Curvelet HSV 4 mức 51,74 93,6 21,43 57,32 46,46 54,11 Curvelets 4 mức 42,72 82,5 22,94 69,15 24,47 48,356 Contourlet co-occurrence [6] 44,45 73,59 24,59 71,01 21,8 47,088 Optimal quantized wavelet 63,9 28,8 30,4 65,1 40 45,64 correlogram [7] Wavelet correlogram [7] 62,7 26,2 30,9 58,6 36,7 43,02 Hình 7 Kết quả trả về 20 ảnh trong truy vấn ảnh 761.jpg trong tập Wang sử dụng đặc trưng curvlet HSV bên trái, đặc trưng curvelets bên phải. 3. Tổng kết Qua các thực nghiệm áp dụng đặc trưng curvelets dựa trên ba thành phần màu H, S, V của ảnh vào truy vấn đã cho độ chính xác rất tốt, đồng thời vẫn đảm bảo tốc độ của hệ thống. Có được kết quả như vậy là nhờ vào khả năng trích xuất thông tin ảnh khá tốt của biến đổi curvelets, khai thác được mối tương quan về màu sắc của ảnh khi phân tích ảnh trên 3 thành phần riêng biệt đại diện cho thông tin màu của ảnh. Đặc trưng curvelets đề xuất đã cải thiện đáng kể hiệu quả truy vấn so với phương pháp curvelets trước đây và vượt trội so với các đặc trưng dựa trên các phép biến đổi khác như đả trình bày. LỜI CẢM ƠN Tác giả xin đặc biệt cảm ơn PGS. TS. Lê Tiến Thường đã tận tình hướng dẫn, chỉ bảo cho tôi trong suốt quá trình thực hiện nghiên cứu. 7
8. TÀI LIỆU THAM KHẢO 1. E. J. Cand`es and D. L. Donoho, Curvelets – a surprisingly effective nonadaptive representation for objects with edges. In C. Rabut A. Cohen and L. L. Schumaker, editors, Curves and Surfaces, pages 105–120, Vanderbilt University Press, 2000. Nashville, TN. 2. I. Sumana, M. Islam, D. S. Zhang and G. Lu, "Image Retrieval Using Discrete Curvelet Transform," in International Workshop on Multimedia Signal Processing (MMSP) Cairns, Queensland, Australia, ISBN 978-1-4244-2295-1, pp.11-16, October 8-10, 2008. 3. I.J. Sumana et al., "Comparison of Curvelet and Wavelet Texture Features for Content Based Image Retrieval," in EEE International Conference on Multimedia and Expo (ICME), 2012. 4. E. J. Candes and D. L. Donoho, Ridgelets: the key to higher-dimensional intermittency? Phil, Trans. R. Soc. Lond. A. 357 (1999), 2495–2509 5. E. J. Candès, L. Demanet, D. L. Donoho, and L. Ying, "Fast Discrete Curvelet Transforms," in Multiscale Modeling and Simulation, vol. 5, pp. 861-899, 2005. 6. Nguyễn Đức Hoàng, "Truy tìm ảnh theo nội dung sử dụng trích đặc điểm trên nền wavelets," Luận văn tiến sĩ, Trường đại học Bách khoa Thành phố Hồ Chí Minh, Hồ Chí Minh, 2013. 7. M. S. Tarzjan and H. A. Moghaddam, "Enhanced Wavelet Correlogram Methods for Image Indexing and Retrieval," in IEEE International Conference on Image Processing (ICIP 2005), vol. 1, Genoa, Italia, 2005, pp. 541 - 544. Tp. Hồ Chí Minh, Ngày tháng năm 2014 Xác nhận của Giáo viên Hướng dẫn Tác giả PGS. TS. Lê Tiến Thường Nguyễn Minh Sang 8
9. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.