GIỚI THIỆU ĐỀ TÀI
Dữ liệu chuỗi thời gian
Chuỗi thời gian (Time Series) T = t1, t2, … tn là tập hợp có thứ tự các quan sát đơn biến hoặc đa biến được ghi nhận sau những khoảng thời gian đều đặn Trong nghiên cứu này, chúng tôi chỉ tập trung vào các giá trị thực của t i.
Chuỗi thời gian là tập hợp dữ liệu hai chiều với các giá trị (T,X), trong đó T đại diện cho thời điểm và X là giá trị quan sát Khi khoảng thời gian quan sát là bằng nhau, T có thể không cần thiết, và chuỗi thời gian có thể được coi là dữ liệu n chiều.
Dữ liệu có yếu tố thời gian rất phong phú, bao gồm thông tin về giá chứng khoán, điện tâm đồ, mực nước, lưu lượng truyền trên mạng và dữ liệu tài chính.
Một số hướng nghiên cứu trên dữ liệu chuỗi thời gian như:
Lập chỉ mục (Indexing) cho phép tìm kiếm những chuỗi thời gian tương tự nhất với một chuỗi truy vấn Q trong cơ sở dữ liệu DB, bằng cách sử dụng một hàm tính độ tương tự hoặc độ sai biệt D(Q,C).
- Gom cụm (clustering): tìm những sự phân nhóm theo tự nhiên của những chuỗi thời gian trong cơ sở dữ liệu DB theo một hàm tính độ tương tự D(Q,C)
- Phân lớp (Classification): cho một chuỗi thời gian chƣa gán nhóm Q, gán nó vào một trong những nhóm đã được định nghĩa trước
Tóm tắt chuỗi thời gian Q với n điểm dữ liệu lớn, tạo ra sự xấp xỉ phù hợp với giới hạn như màn hình máy tính hay trang giấy, trong khi vẫn giữ nguyên các đặc trưng bản chất của dữ liệu.
Phát hiện bất thường (Anomaly detection) là quá trình xác định các phần của chuỗi thời gian Q có chứa những hành vi không bình thường, dựa trên các mô hình hành vi bình thường đã được xác định Lĩnh vực này còn được biết đến với nhiều tên gọi khác nhau, chẳng hạn như phát hiện những hành vi gây ngạc nhiên.
Surprising behavior, interesting behavior, unexpected behavior, and novel behavior all contribute to our understanding of what is considered unusual There are numerous definitions that help clarify the concept of abnormality in behavior.
Biểu diễn ảnh dạng chuỗi thời gian
Có nhiều phương pháp để chuyển đổi ảnh thành chuỗi thời gian, trong đó bài viết này tập trung vào phương pháp dựa trên đường biên hình dạng của ảnh Dữ liệu chuỗi thời gian, hay còn gọi là dữ liệu giả chuỗi thời gian, được định nghĩa là chuỗi giá trị khoảng cách từ tâm của hình ảnh đến các điểm trên đường biên hình dạng theo chiều kim đồng hồ.
Hình 1.1 Chuyển ảnh 2 chiều sang dữ liệu chuỗi thời gian (nguồn [26])
Dữ liệu chuỗi thời gian của ảnh có những đặc điểm như nhiễu từ điểm ảnh, các phép tỉ lệ và phép quay Trong số đó, việc xử lý nhiễu do phép quay đã thu hút sự quan tâm từ nhiều công trình nghiên cứu.
Một số hướng nghiên cứu trên dữ liệu chuỗi thời gian của ảnh: tìm kiếm tương tự trên chuỗi thời gian của ảnh, tìm motif, tìm dị thường, …
Kỹ thuật tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian
Kỹ thuật tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian cho phép tìm kiếm ảnh tương tự bằng cách sử dụng thông tin từ chuỗi thời gian Hàm khoảng cách được sử dụng để đo lường độ tương tự giữa các ảnh thông qua dữ liệu chuỗi thời gian, và cần đảm bảo tính bất biến trước nhiễu để đạt được kết quả chính xác.
- Ảnh truy vấn bị nhiễu, nhất là phép quay
- Số chiều dữ liệu chuỗi thời gian không đồng nhất
- Lưu trữ tập dữ liệu ảnh lớn
- Thời gian tìm kiếm phải nhỏ và chính xác.
Mục tiêu và giới hạn của đề tài
Mục tiêu chính của luận văn là phát triển một khung tổng quát cho kỹ thuật tìm kiếm ảnh 2 chiều dựa trên chuỗi thời gian, đồng thời tập trung giải quyết các vấn đề liên quan đến hiệu quả và độ chính xác trong quá trình tìm kiếm hình ảnh.
Trong tập dữ liệu và ảnh truy vấn, các ảnh thường không đồng nhất về số chiều Để giải quyết vấn đề này, chúng tôi đề xuất áp dụng phương pháp thu giảm số chiều PAA cho dữ liệu chuỗi thời gian, giúp đưa các ảnh về cùng một số chiều.
Để xử lý nhiễu trên ảnh, chúng tôi đề xuất sử dụng phương pháp chuẩn hóa 0 và biến đổi Fourier trên chuỗi thời gian nhằm đạt tính bất biến trong phép quay Kỹ thuật này không chỉ giúp giảm số chiều của chuỗi biến đổi mà còn cho phép áp dụng kỹ thuật nén chuỗi hiệu quả.
Kích thước dữ liệu trong tìm kiếm thường rất lớn, do đó, các ứng dụng cần áp dụng phương pháp lập chỉ mục để tăng tốc độ tìm kiếm Phương pháp này có thể bao gồm việc giảm số chiều để giảm kích thước dữ liệu hoặc sử dụng các cấu trúc biểu diễn dữ liệu nhằm cải thiện hiệu suất tìm kiếm Chúng tôi đề xuất áp dụng phương pháp lập chỉ mục với cấu trúc cây VP cải tiến dựa trên [23].
- Cải tiến giải thuật tìm kiếm trên cấu trúc chỉ mục dựa trên các giải thuật của [9] [15] [23]
Tóm lƣợc những kết quả đạt đƣợc
Xây dựng khung tổng quát cho ứng dụng bao gồm hai thành phần chính: tổ chức dữ liệu và lập chỉ mục cho tập dữ liệu tìm kiếm, cùng với thành phần truy vấn ảnh để tìm kiếm ảnh tương tự dựa trên ảnh truy vấn được cung cấp.
Chúng tôi thực hiện chuẩn hóa dữ liệu và giảm số chiều bằng phương pháp PAA, biến đổi Fourier, đồng thời lập chỉ mục dựa trên cấu trúc cây VP cải tiến.
Bài viết đề cập đến việc xử lý dữ liệu đầu vào là chuỗi thời gian hoặc hình ảnh, chuyển đổi chúng thành chuỗi thời gian và chuẩn hóa dữ liệu Quá trình này bao gồm việc thu giảm số chiều để đồng nhất với tập dữ liệu, áp dụng biến đổi Fourier và thực hiện tìm kiếm trên cấu trúc chỉ mục VP cải tiến Ngoài ra, thuật toán tìm kiếm cũng được tối ưu hóa để phù hợp với cây VP cải tiến, dựa trên các giải thuật đã được nghiên cứu trước đó.
Luận văn này thực hiện hai cải tiến quan trọng: đầu tiên, đề xuất sử dụng cây VP chỉ nén dữ liệu tại các nút lá, không nén dữ liệu tại nút gốc và nút trung gian; thứ hai, cải tiến thuật toán tìm kiếm trên cây VP đã được nâng cấp.
Qua thực nghiệm cho thấy các cải tiến đã mang lại kết quả đáng kể trong việc giảm thời gian tìm kiếm ảnh.
Cấu trúc của luận văn
Phần còn lại của luận văn đƣợc tổ chức nhƣ sau:
Chương 2 trình bày tổng quan các công trình liên quan về các hàm tính độ tương tự, các phương pháp thu giảm số chiều, các cấu trúc chỉ mục phổ biến, các phương pháp xử lý phép quay ảnh
Chương 3 làm rõ cơ sở lý thuyết nền tảng của các phương pháp biểu diễn, các giải thuật, cấu trúc dữ liệu dùng làm chỉ mục đƣợc chọn sau khi khảo sát các công trình có liên quan ở chương 2 Cụ thể đó là phép biến đổi Fourier để đạt được tính bất biến trong phép quay, kỹ thuật nén và xây dựng hàm biên dưới; cấu trúc chỉ mục VP-Tree và giải thuật tìm kiếm lân cận trên VP-Tree
Trong Chương 4, chúng tôi giới thiệu phương pháp giải quyết vấn đề dựa trên cấu trúc VP-Tree và điều chỉnh thuật toán tìm kiếm lân cận để phù hợp với cấu trúc này Ngoài ra, hệ thống thực hiện phương pháp giải quyết vấn đề cũng sẽ được trình bày trong chương này.
Chương 5 trình bày các tiêu chuẩn để thực hiện thí nghiệm và công bố kết quả thực nghiệm Chúng tôi đã tiến hành thí nghiệm hệ thống trên nhiều tập dữ liệu khác nhau, đồng thời kiểm tra với các thông số thiết lập khác nhau cho mỗi tập dữ liệu.
Chương 6 là một số kết luận và hướng mở rộng của đề tài.
TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
Công trình về độ đo tương tự
Trong bài toán tìm kiếm, kết quả tìm kiếm được xác định là tương tự với đối tượng truy vấn thông qua độ tương tự Độ tương tự giữa hai đối tượng được đánh giá dựa trên khoảng cách giữa chúng; nếu khoảng cách bằng không, chúng hoàn toàn giống nhau, và nếu khoảng cách nhỏ hơn một giá trị ngưỡng r đã được xác định, chúng được coi là tương tự Các tính chất này là cơ sở cho việc đo lường độ tương tự trong tìm kiếm.
2.1.1 Độ đo Minkowski – Độ đo khoảng cách Euclid p n i p i i y x Y
) , ( trong đó, p = 1 (độ đo Manhattan) p = 2 (độ đo Euclid) p = ∞ (độ đo Max)
Trong các công trình liên quan, độ đo Euclid đƣợc sử dụng rộng rãi vì những ƣu điểm sau: Ƣu điểm:
Có thể áp dụng cho nhiều bài toán như phân loại, gom cụm và tìm kiếm tương tự Phương pháp này thích hợp với các phép biến đổi biểu diễn xấp xỉ như DFT, DWT, PAA và APCA.
Đo độ xoắn thời gian động DTW được công nhận là vượt trội hơn so với đo Euclid, tuy nhiên, kết quả thực nghiệm trên tập dữ liệu lớn cho thấy sự khác biệt giữa hai phương pháp này không đáng kể.
Không thể áp dụng cho các chuỗi thời gian có đường cơ bản biến đổi giống nhau nhưng lệch nhau về thời gian hoặc biên độ khác nhau Để khắc phục nhược điểm này, cần chuẩn hóa các chuỗi thời gian trước khi tính khoảng cách Một phương pháp chuẩn hóa phổ biến là đưa về dạng trung bình zero và độ lệch chuẩn là 1.
(1) Đường cơ bản khác nhau (2) Biên độ dao động khác nhau
Hình 2.1 Trường hợp 2 chuỗi có đường cơ bản lệch nhau và biên độ dao động khác nhau [16]
Ví dụ, cho Q có giá trị trung bình là mean(Q) và độ lệch chuẩn là std(Q), Q’ là chuỗi chuẩn hóa của Q đƣợc tính nhƣ sau:
2.1.2 Độ đo xoắn thời gian động (Dynamic Time Warping –DTW)
Phương pháp DTW (Dynamic Time Warping) được Berndt và các cộng sự đề xuất vào năm 1994 nhằm giải quyết vấn đề so sánh hai đường biểu diễn dữ liệu không hoàn toàn giống nhau nhưng có hình dạng biến đổi tương tự Khi áp dụng phương pháp Minkowski để tính khoảng cách giữa các điểm tương ứng, kết quả có thể không chính xác nếu hai đường lệch nhau về thời gian, như minh họa trong Hình 2.2.a Để cải thiện độ chính xác, DTW cho phép một điểm có thể ánh xạ tới nhiều điểm khác nhau, không theo thứ tự nhất định, như thể hiện trong Hình 2.2.b.
(a) Tính theo khoảng cách Euclid (b) Tính theo khoảng cách DTW
Để tính toán DTW giữa hai chuỗi thời gian S = s1, s2,…,sn và T = t1, t2,…,tm, ta sẽ sắp xếp chúng trên mặt phẳng lưới n x m Mỗi điểm trên lưới (i,j) đại diện cho sự ánh xạ giữa các thành phần s_i và t_j Đường đi xoắn W sẽ ánh xạ các thành phần của S và T, giúp xác định sự tương đồng giữa hai chuỗi.
“khoảng cách” giữa chúng là nhỏ nhất
Trong đó w k tương ứng với điểm (i,j) k
Có rất nhiều cách tính khoảng cách giữa 2 thành phần s i và t j , có thể tính theo một trong hai cách sau: δ(i, j) = |s i – t j | δ(i, j) = (s i – t j ) 2
Hình 2.3 Độ đo độ xoắn thời gian động với cửa sổ warp Sakoe-Chiba độ rộng
R Trên hình warping path giới hạn trong cửa sổ bán kính R (nguồn [13]) Để giới hạn không gian tìm kiếm đường đi xoắn, những ràng buộc sau phải đƣợc thỏa mãn:
Tính đơn điệu (monotonicity): những điểm ánh xạ phải có thứ tự theo thời gian, tức là i k-1 ≤ i k và j k-1 ≤ j k
Tính liên tục (continuity): những bước chuyển trên lưới chỉ giới hạn ở những điểm lân cận, i k – ik-1 ≤ 1 và j k –j k-1 ≤ 1
Cửa sổ xoắn (warping window) là một khái niệm quan trọng trong đó các điểm ánh xạ phải nằm trong một khoảng nhất định, được xác định bởi điều kiện |i k – j k | ≤ ω Ở đây, ω đại diện cho chiều rộng của cửa sổ xoắn, là một số nguyên dương.
Để cải thiện hiệu quả và tốc độ tìm kiếm, cần thỏa mãn một số ràng buộc nhất định Việc tìm kiếm đường đi xoắn có thể được thực hiện thông qua thuật toán quy hoạch động, dựa trên công thức truy hồi xác định khoảng cách tích lũy λ(i, j) cho mỗi điểm, với λ(i, j) = δ(i, j) + min[λ(i-1, j), λ(i-1, j-1), λ(i, j-1)] Phương pháp này mang lại nhiều ưu điểm trong việc tối ưu hóa quá trình tìm kiếm.
Cho kết quả chính xác hơn độ đo Euclid
Cho phép nhận dạng mẫu có hình dạng giống nhau nhƣng chiều dài hình dạng về thời gian có thể khác nhau
Trong so trùng ảnh, dữ liệu chuỗi thời gian của một ảnh có thể khác nhau ở điểm bắt đầu Khi sử dụng khoảng cách Euclid, chúng được xem là hoàn toàn khác nhau Tuy nhiên, khi áp dụng độ xoắn thời gian động với cửa sổ xoắn thích hợp, kết quả đo lường cho thấy chúng có sự tương đồng.
Thời gian chạy lâu Một số ràng buộc đƣợc đề ra để tăng tốc độ tìm kiếm [4]
2.1.3 Phương pháp chuỗi con chung dài nhất (Longest Common Subsequence
Phương pháp LCS do Vlachos và các cộng sự phát triển vào năm 2004 cho phép loại bỏ các điểm bất thường trong quá trình so sánh, điều này đặc biệt hữu ích trong phân tích ảnh khi gặp phải các điểm khuyết Ý tưởng cốt lõi của phương pháp là xác định các chuỗi con chung; hai chuỗi sẽ được coi là tương đồng hơn nếu chúng có chuỗi con chung dài hơn Ví dụ, với hai chuỗi X và Y, việc tìm kiếm chuỗi con chung sẽ giúp đánh giá mức độ tương đồng giữa chúng.
Y = 2, 5, 4, 7, 3, 10, 8, 6 LCS = 2, 5, 7, 10 => Dist(X,Y) = |LCS| = 4 Ƣu điểm:
Thể hiện tính trực quan của dữ liệu và cho phép bỏ qua những điểm bất thường
Trong các bài toán so trùng ảnh, thuật toán LCS (Longest Common Subsequence) rất hữu ích khi so sánh những ảnh bị thiếu chi tiết Chẳng hạn, khi so sánh hai sọ người, nếu một trong hai sọ thiếu phần mũi, thì LCS sẽ không tính đến phần này trong việc đánh giá độ tương tự, dẫn đến việc phần mũi bị bỏ qua.
Trước khi áp dụng phương pháp Euclid, việc chuẩn hóa dữ liệu là cần thiết để ngăn chặn hiện tượng tịnh tiến đường cơ bản và co giãn biên độ.
Các công trình về biểu diễn chuỗi thời gian
Chuỗi thời gian thường có khối lượng dữ liệu lớn, dẫn đến chi phí cao trong việc truy xuất và tính toán Do đó, nghiên cứu về chuỗi thời gian tập trung vào việc biểu diễn dữ liệu dưới dạng khác để giảm kích thước và nâng cao hiệu năng tìm kiếm Các phương pháp này chủ yếu nhằm giảm số chiều của dữ liệu để hỗ trợ lập chỉ mục Sau đó, dữ liệu có thể được rời rạc hóa thành chuỗi bit hoặc chuỗi ký tự, giúp áp dụng các kỹ thuật nén dữ liệu và khai phá dữ liệu văn bản Ngoài ra, việc chuẩn hóa dữ liệu trước khi giảm số chiều là cần thiết để tránh các vấn đề như tịnh tiến dữ liệu và co giãn biên độ.
2.2.1 Các phương pháp thu giảm số chiều
2.2.1.1 Phương pháp biến đổi Fourier rời rạc DFT (Discrete Fourier
Phương pháp DFT, được Agrawal và các cộng sự giới thiệu vào năm 1993, chuyển đổi tín hiệu từ miền thời gian sang miền tần số Phương pháp này lập chỉ mục trên một số tần số đầu tiên và loại bỏ các tần số còn lại, dựa trên nhận định rằng năng lượng của hầu hết các chuỗi thời gian thực tế thường tập trung chủ yếu ở những tần số này.
Chuỗi biến đổi X f (f = 0,…,n-1) của chuỗi X t (t = 0,…,n-1) đƣợc định nghĩa nhƣ sau:
X f là tập hợp các số phức, và hàm tính độ tương tự được đề xuất cho phương pháp này là phương pháp Euclid Để lập chỉ mục, các chỉ số như F-Index và ST-index được khuyến nghị sử dụng.
Thu giảm số chiều của dữ liệu gốc
Bảo toàn khoảng cách Euclid sau khi biến đổi theo định lý Parseval, đảm bảo thỏa mãn điều kiện chặn dưới cho khoảng cách thực của dữ liệu gốc Phương pháp Fast Fourier có độ phức tạp tính toán O(nlogn).
Transform (một cải tiến của DFT)
Chỉ áp dụng cho các loại dữ liệu có năng lượng tập trung ở một vài tần số đầu tiên, như tiếng ồn hồng (pink noise) và tiếng ồn nâu (brown noise), phương pháp này sẽ thiếu sót thông tin quan trọng khi áp dụng cho dữ liệu có năng lượng phân bố đều (tiếng ồn trắng - white noise) hoặc tập trung ở các tần số cao (tiếng ồn xanh - blue noise, tiếng ồn tím - violet noise).
Tính toán phức tạp vì domain thu giảm là các số phức
Không tận dụng đƣợc các giải thuật và cấu trúc dữ liệu cho dạng ký tự và bit
Khó giải quyết khi các chuỗi thời gian có chiều dài khác nhau
Hình 2.1 Các dạng biểu diễn phổ biến nhất cho khai phá dữ liệu chuỗi thời gian (nguồn [16])
2.2.1.2 Phương pháp xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate
Phương pháp PAA, được đề xuất bởi Keogh và các cộng sự vào năm 2001, là kỹ thuật tuần tự xấp xỉ k giá trị liền kề thành một giá trị trung bình cộng Quá trình này diễn ra từ đầu đến cuối chuỗi thời gian, và kết quả thu được là một đường thẳng có dạng bậc thang.
Ví dụ cho chuỗi x j (j = 1,…,n), chuỗi biến đổi X i (i = 1,…,N) (N là số chiều thu giảm) đƣợc tính theo công thức sau:
Hình 2.4 Phương pháp biểu diễn PAA với n8, N=8 (nguồn [14] )
Hỗ trợ các phương pháp tính khoảng cách như: khoảng cách Euclid, DTW, Minkowski…Ngoài ra, một phương pháp đo khoảng cách được đề xuất như sau:
Trong đó, X x i |i 1, ,N và Y y i |i 1, ,N là 2 chuỗi xấp xỉ của 2 chuỗi X và Y
Phương pháp này không phụ thuộc vào cấu trúc chỉ mục cụ thể nào, có thể sử dụng F-index, R-tree… Ƣu điểm:
Thời gian tính toán nhanh và dễ dàng
Hỗ trợ câu truy vấn có chiều dài khác nhau
Hàm khoảng cách được đề nghị có giá trị chặn dưới chặt so với dữ liệu gốc
Xây dựng lại chuỗi ban đầu có thể gặp nhiều khó khăn và thường dẫn đến lỗi lớn, trong khi các phương pháp hiện có cung cấp công thức để tái tạo chuỗi ban đầu với tỷ lệ lỗi thấp.
Không quan tâm đến những điểm đặc biệt khác nhƣ điểm giá trị nhỏ nhất, lớn nhất của mỗi đoạn xấp xỉ
2.2.1.3 Phương pháp xấp xỉ gộp ký hiệu hóa SAX (Symbolic Aggregate approXimation)
Phương pháp SAX, được đề xuất bởi Lin và các cộng sự vào năm 2003, dựa trên việc thu giảm số chiều thông qua phương pháp PAA và giả định rằng dữ liệu đã được chuẩn hóa với trung bình bằng 0 và độ lệch chuẩn bằng 1 Dữ liệu ban đầu được chia thành các đoạn bằng phương pháp PAA, sau đó ánh xạ mỗi đoạn thành các ký tự rời rạc Do không gian thu giảm là không gian ký tự, cần có cơ chế ánh xạ sự khác biệt giữa hai ký tự thành giá trị số, vì không thể sử dụng các hàm tính khoảng cách với đối số là các giá trị thực.
Phương pháp SAX áp dụng hàm MINDIST để tính khoảng cách trong không gian thu giảm, đảm bảo điều kiện chặn dưới Chỉ mục hóa được thực hiện thông qua phương pháp tập tin xấp xỉ hóa vector, bên cạnh đó có thể sử dụng R-tree và các kỹ thuật lập chỉ mục cho chuỗi ký tự cổ điển như cây hậu tố Ƣu điểm của phương pháp này là hiệu quả trong việc xử lý dữ liệu.
Không gian thu giảm, với các ký tự và dữ liệu rời rạc, cho phép áp dụng các thuật toán và cấu trúc dữ liệu như kỹ thuật băm, mô hình Markov và cây hậu tố Điều đặc biệt là có thể định nghĩa hàm tính khoảng cách trên không gian này, thỏa mãn điều kiện chặn dưới, điều mà nhiều phương pháp rời rạc hóa khác không đạt được.
Bảng ánh xạ khoảng cách giữa hai ký tự được tính toán trước cho từng loại dữ liệu, giúp việc tính toán khoảng cách diễn ra nhanh chóng thông qua bảng này.
Ánh xạ các giá trị thực thành ký tự phụ thuộc vào loại dữ liệu cụ thể, vì vậy cần huấn luyện dữ liệu để xác định cách ánh xạ tối ưu cho từng loại.
Không quan tâm đến các điểm đặc biệt nhƣ điểm giá trị nhỏ nhất và lớn nhất của mỗi đoạn, giống như phương pháp PAA
2.2.2 Các cấu trúc chỉ mục
Dữ liệu chuỗi thời gian chiều dài n có thể được coi là một điểm trong không gian n chiều, và sau khi giảm chiều xuống không gian m chiều (m v q dist(v,q) node dist(v,q) (node + )
=> tìm cả hai cây con S , S >
=> cắt nhánh S > , tìm trên cây con S v q dist(v,q) node dist(v,q) > (node - )
=> tìm cả hai cây con S , S >
Trong quá trình xử lý, chỉ những ứng cử viên có giá trị biên dưới nhỏ hơn BSF.distance mới được truy xuất từ chuỗi nguyên gốc không nén để tính toán khoảng cách và cập nhật giá trị cho BSF Các khoảng cách này được lưu trữ trong hàng đợi theo thứ tự tăng dần, đảm bảo hiệu quả trong việc tìm kiếm và xử lý dữ liệu.
BSF.ID = NULL; BSF.distance = INF;
Qfft = biến đổi Fourier lấy biên độ (Q);
/* Parameter: Node of VP-tree, Uncompressed Query Signature Qfft, Current Nearest Neighbor */
/* queue = priority queue of compressed shape signatures sorted on LB */ if NODE.isLeaf { for each compressed time-series cT in node {
LB queue.top().LB) { retrieve uncompressed T of queue.top() from disk; dist = D(T,Qfft); /* full distance */
BSF.distance = dist; BSF.ID = T;
} } else { /* vantage point */ dist = D(VP,Qfft); /* full distance */ if dist < BSF.distance {
BSF.distance = dist; BSF.ID = T;
} if (dist NODE ) { Search(NODE.left,Qfft, BSF); if (dist NODE −BSF.distance) then Search(NODE.right,Qfft, BSF);
} else { Search(NODE.right,Qfft, BSF); if (dist NODE +BSF.distance) then Search(NODE.left, Qfft, BSF);
Hình 4.3 Mã giả giải thuật tìm kiếm lân cận trên VP-Tree cải tiến
Kiến trúc hệ thống
Kiến trúc hệ thống xây dựng từ kỹ thuật tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian của ảnh đƣợc đề xuất nhƣ Hình 4.4
Hệ thống tương tác với người dùng thông qua giao diện người dùng, nhận input và trả output
Input: chuỗi thời gian của ảnh (shape) hoặc có thể là một ảnh đƣợc đƣa vào hệ thống qua giao diện người dùng
Do sự không đồng nhất của tập dữ liệu, bao gồm cả chuỗi thời gian và hình ảnh, nền tảng có thể là một chuỗi thời gian hoặc một bức ảnh Để cải thiện tốc độ tìm kiếm hình ảnh, hệ thống áp dụng cấu trúc dữ liệu VP-Tree cải tiến để lập chỉ mục cho tập dữ liệu Kiến trúc hệ thống bao gồm hai thành phần chính: hệ thống lập chỉ mục cho tập dữ liệu và hệ thống tìm kiếm dựa trên cấu trúc chỉ mục đã được tạo ra.
4.2.1 Hệ thống lập chỉ mục cho tập dữ liệu
Quá trình lập chỉ mục cho tập dữ liệu đƣợc thực hiện nhƣ Hình 4.5
Hình 4.4 Kiến trúc hệ thống tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian của ảnh
Chuỗi thời gian của ảnh (shape) hoặc shape
2 Thu giảm số chiều bằng PAA
3 Biến đổi Fourier và loại bỏ thành phần đối xứng
4 Thực hiện so trùng mẫu
Cấu trúc chỉ mục VPC
Tập dữ liệu lưu trữ trên bộ nhớ ngoài gồm: chuỗi Fourier, chuỗi thời gian, và ảnh
Hình 4.5 Lập chỉ mục cho tập dữ liệu 4.2.2 Hoạt động của hệ thống tìm kiếm trên cấu trúc chỉ mục:
- Người dùng đưa ảnh truy vấn (dạng chuỗi thời gian hoặc ảnh) vào hệ thống thông qua giao diện người dùng
- Ảnh truy vấn đƣợc chuyển sang dữ liệu chuỗi thời gianvà thực hiện chuẩn hóa dữ liệu trên chuỗi này
- Tiếp theo thực hiện giảm chiều bằng phương pháp PAA trên chuỗi thời gian của ảnh để ảnh truy vấn và tập dữ liệu cùng số chiều
Biến đổi Fourier trên chuỗi thời gian của ảnh cho phép phân tích các thành phần tần số của hình ảnh Trong quá trình này, chỉ lấy thành phần biên độ và loại bỏ thành phần đối xứng, dẫn đến việc tạo ra chuỗi Fourier của ảnh Việc này giúp cải thiện khả năng xử lý và phân tích hình ảnh một cách hiệu quả.
Chuẩn hóa, giảm chiều PAA Tập dữ liệu timeseries, ảnh
Biến đổi Fourier Chuyển sang dạng timeseries
- Chuỗi Fourier của ảnh đƣợc sử dụng để tìm kiếm các ảnh lân cận dựa trên cấu trúc chỉ mục VP-Tree lập trước
- Kết quả quá trình tìm kiếm trả về ảnh gần với ảnh truy vấn nhất