NHẬN DẠNG MÔ-TÍP TRONG DỮ LIỆU CHUỖI THỜI GIAN HÌNH ẢNH (FINDING MOTIF IN IMAGE TIMESERIES DATA)

Luận văn thạc sĩ về nhận dạng mô típ trong dữ liệu chuỗi thời gian hình ảnh. Nghiên cứu khoa học máy tính, ứng dụng và giải thuật liên quan đến xử lý ảnh.

• Tác giả: Trần Công Thanh
• Người hướng dẫn: Ts. Bùi Hoài Thắng
• Trường học: Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Nhận Dạng Mô-Típ Trong Dữ Liệu Chuỗi Thời Gian Hình Ảnh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Nhận Dạng Mô típ Chuỗi Thời Gian Ảnh 55

Nhận dạng mô-típ hình ảnh là một bài toán thu hút sự quan tâm lớn từ cộng đồng xử lý hình ảnh. Bài toán này có nhiều ứng dụng thực tế, ví dụ như trong khảo cổ học và sinh vật học. Luận văn của Trần Công Thanh (2011) nghiên cứu cách áp dụng kỹ thuật rời rạc hóa ESAX vào xử lý hình ảnh, so sánh hai phương pháp rời rạc hóa dữ liệu chuỗi thời gian SAX và ESAX khi áp dụng vào giải thuật chiếu ngẫu nhiên-Random Projection. Kết quả thực nghiệm cho thấy giải thuật chiếu ngẫu nhiên đã được nâng cao hiệu quả khi áp dụng phương pháp rời rạc hóa ESAX. Dữ liệu chuỗi thời gian hình ảnh ngày càng trở nên phổ biến, đòi hỏi các phương pháp hiệu quả để phân tích và khai thác thông tin. Bài toán nhận dạng mô-típ hành vi trở nên quan trọng trong nhiều lĩnh vực.

1.1. Dữ liệu chuỗi thời gian hình ảnh là gì Định nghĩa 42

Chuỗi thời gian là một tập hợp gồm n phần tử từ t1, t2,..., tn là tập có thứ tự gồm các trị thực, trong đó ti là dữ liệu đo ở thời điểm i. Nói cách khác, chuỗi thời gian là sự quan sát các dữ liệu theo thứ tự thời gian tuần tự. Hình ảnh có thể được chuyển đổi thành chuỗi thời gian bằng nhiều cách, như dựa vào góc lệch của các tiếp tuyến của các điểm trên đường biên hoặc dựa vào diện tích tạo bởi hai điểm liền kề trên đường biên và điểm trung tâm của hình.

1.2. Ứng dụng của nhận dạng mô típ hình ảnh trong thực tế 48

Việc tìm kiếm một mẫu thức tương tự một mẫu thức cho trước trong cơ sở dữ liệu chuỗi thời gian lớn (query-by-content) thu hút nhiều sự quan tâm của các nhà nghiên cứu và rất nhiều giải pháp đã được đề xuất. Vấn đề tìm kiếm mô-típ nói chung và tìm kiếm mô-típ hình ảnh nói riêng có rất nhiều ứng dụng trong thực tế như trong lãnh vực khảo cổ học: việc tìm các mô-típ chung giữa các tập dữ liệu thu thập sẽ cho biết được mối quan hệ giữa các khu vực, các thời kỳ với nhau.

II. Thách Thức Vấn Đề Trong Nhận Dạng Mô típ Ảnh 57

Việc phân tích chuỗi thời gian hình ảnh đối mặt với nhiều thách thức do đặc điểm của dữ liệu. Một trong những khó khăn lớn là khối lượng dữ liệu lớn, đòi hỏi các kỹ thuật thu giảm số chiều và rời rạc hóa. Dữ liệu thu thập thường chịu ảnh hưởng của yếu tố chủ quan và không đồng nhất, yêu cầu các phương pháp chuẩn hóa và xử lý nhiễu. Các giải thuật tìm kiếm mô-típ hình ảnh cần bất biến với góc quay để nhận diện sự tương đồng. Luận văn của Trần Công Thanh (2011) đề cập đến những thách thức này và đưa ra các giải pháp.

2.1. Khối lượng dữ liệu lớn và yêu cầu về hiệu năng 47

Đặc trưng của chuỗi thời gian là dữ liệu lớn. Ví dụ như khi đo điện tâm đồ trong 1 giờ dữ liệu khoảng 1 Gigabyte. Đây là một khó khăn trong việc phân tích dữ liệu, tính toán và xử lý chuỗi thời gian, cũng như lưu trữ dữ liệu … đây cũng là điều kiện để phát triển các kỹ thuật thu giảm số chiều và các phương pháp rời rạc hoá….

2.2. Tính bất biến với góc quay trong nhận dạng hình ảnh 50

Giải thuật tìm kiếm mô-típ hình ảnh đòi hỏi phải bất biến với góc quay( rotation- invariant). Việc giải quyết vấn đề góc xoay thì có nhiều phương pháp được đưa ra như tìm trục chính (nhưng cách này có miền ứng dụng giới hạn và rất nhạy cảm với nhiễu [20])… trong luận văn sử dụng ma trận xoay (rotation matrix)[12].

III. Cách Nhận Dạng Mô típ Phương Pháp Chiếu Ngẫu Nhiên 58

Luận văn của Trần Công Thanh (2011) tập trung vào giải thuật chiếu ngẫu nhiên (Random Projection) để nhận dạng mẫu hình ảnh theo thời gian. Giải thuật này sử dụng phương pháp rời rạc hóa SAX (Symbolic Aggregate approXimation) và ESAX (Extended SAX) để giảm số chiều dữ liệu và biểu diễn chuỗi thời gian dưới dạng ký tự. Việc so sánh hiệu quả của hai phương pháp rời rạc hóa là trọng tâm của nghiên cứu. Phương pháp chiếu ngẫu nhiên đã chứng minh được khả năng giảm độ phức tạp tính toán trong nhiều bài toán.

3.1. Kỹ thuật rời rạc hóa SAX và ESAX Ưu điểm và nhược điểm 52

Phương pháp xấp xỉ gộp ký hiệu hoá – SAX do Lin và các cộng sự đề xuất năm 2003[15] là kỹ thuật ký hiệu hoá dựa trên kỹ thuật thu giảm số chiều PAA do Keogh và các cộng sự đề nghị năm 2000[8] mà trong đó sự thu giảm số chiều là sử dụng các giá trị trung bình của các phân đoạn với độ dài bằng nhau, nên có khả năng bị mất đi một số mẫu thức quan trọng trong dữ liệu. Để khắc phục nhược điểm này, Lkhagva và các cộng sự, năm 2006, [16] đã đề nghị một kỹ thuật rời rạc hoá mới là kỹ thuật xấp xỉ gộp ký hiệu hoá mở rộng – Extended SAX – ESAX. Kỹ thuật này dựa trên phương pháp PAA mở rộng –Extended-PAA là vẫn dựa vào PAA nhưng mỗi đoạn gồm 3 giá trị là trị trung bình của mỗi phân đoạn, thêm vào giá trị nhỏ nhất và lớn nhất của mỗi phân đoạn.

3.2. Giải thuật chiếu ngẫu nhiên Cách hoạt động và ứng dụng 53

Hiện thực giải thuật chiếu ngẫu nhiên-Random-Projection trong luận văn gồm các phần: Thu giảm số chiều luận văn áp dụng phương pháp thu giảm số chiều PAA, và kỹ thuật PAA mở rộng – EPAA. Tương ứng là phương pháp rời rạc hoá và biểu diễn chuỗi thời gian thành dạng ký tự là SAX, ESAX. Sử dụng giải thuật chiếu ngẫu nhiên-Random-Projection để tìm kiếm mô-típ trên tập dữ liệu chuỗi thời gian hình ảnh.

IV. So Sánh SAX vs

Luận văn của Trần Công Thanh (2011) tập trung vào việc so sánh hiệu quả của hai phương pháp rời rạc hóa SAX và ESAX khi áp dụng vào giải thuật chiếu ngẫu nhiên. Kết quả thực nghiệm cho thấy việc sử dụng ESAX thường mang lại thời gian thực thi nhanh hơn và độ chính xác cao hơn so với SAX. Điều này chứng tỏ ESAX có khả năng bảo toàn thông tin quan trọng trong dữ liệu chuỗi thời gian hình ảnh tốt hơn.

4.1. Kết quả thực nghiệm Thời gian thực thi và độ chính xác 51

Kết quả thực nghiệm cho thấy giải thuật nhận dạng mô-típ khi dùng phương pháp rời rạc hoá hoá ESAX (cả hai cách xoay RT1,RT2) thường thời gian thực thi nhanh hơn, và độ chính xác cao hơn khi giải thuật dùng phương pháp rời rạc hoá SAX .

4.2. Ảnh hưởng của thông số đến hiệu suất giải thuật 50

Phần việc đầu tiên chúng tôi xây dựng phần mềm khảo sát các tập dữ liệu dựa vào khái niệm độ chặt cận dưới (Tightness of Lower Bound) để tìm ra các thông số phù hợp với tập dữ liệu, như: số chiều thu giảm w, kích thước tập ký tự dùng cho ký hiệu hoá a, huấn luyện giải thuật để tìm ra trị trung bình (average) của ma trận đụng độ (collision matrix) trong giải thuật chiếu ngẫu nhiên-Random-Projection.

V. Ứng Dụng Thực Tế Nhận Dạng Mô típ Trong Video 59

Việc nhận dạng hành động trong video là một ứng dụng quan trọng của nhận dạng mô-típ trong chuỗi thời gian hình ảnh. Các mô-típ hành vi có thể được sử dụng để phát hiện các hoạt động bất thường, theo dõi đối tượng và phân tích nội dung video. Các kỹ thuật như deep learning cho chuỗi thời gian hình ảnh đang được áp dụng rộng rãi trong lĩnh vực này. Từ đó có thể phát hiện dị thường trong chuỗi hình ảnh

5.1. Giám sát an ninh và phát hiện hành vi bất thường 49

Ứng dụng giám sát an ninh chuỗi thời gian hình ảnh. Các mô-típ hành vi có thể được sử dụng để phát hiện các hoạt động bất thường. Việc này giúp các nhà quản lý có thể đưa ra các cảnh báo hoặc các hành động kịp thời.

5.2. Ứng dụng trong y tế Theo dõi bệnh nhân từ xa 50

Ứng dụng y tế chuỗi thời gian hình ảnh (ví dụ: theo dõi bệnh nhân). Việc theo dõi bệnh nhân từ xa có thể sử dụng các mô-típ hành vi để phát hiện các dấu hiệu bất thường và cảnh báo cho bác sĩ hoặc người thân.

VI. Hướng Phát Triển Nghiên Cứu Tương Lai 50

Nghiên cứu về nhận dạng mô-típ trong chuỗi thời gian hình ảnh vẫn còn nhiều hướng phát triển tiềm năng. Việc kết hợp các kỹ thuật deep learning, sử dụng các bộ dữ liệu lớn và phát triển các giải thuật hiệu quả hơn là những mục tiêu quan trọng. Các ứng dụng mới trong lĩnh vực y tế, giao thông và nông nghiệp cũng mở ra nhiều cơ hội nghiên cứu.

6.1. Kết hợp deep learning để nâng cao độ chính xác 48

Mạng nơ-ron tái phát (RNN) cho chuỗi thời gian hình ảnh. Mạng nơ-ron tích chập (CNN) cho chuỗi thời gian hình ảnh. LSTM cho chuỗi thời gian hình ảnh. Transformer cho chuỗi thời gian hình ảnh.

6.2. Nghiên cứu các phương pháp bất biến với biến đổi hình ảnh 53

Việc xây dựng giải thuật nhận dạng mô-típ hình ảnh đòi hỏi phải bất biến với góc quay( rotation- invariant).Việc giải quyết vấn đề góc xoay thì có nhiều phương pháp được đưa ra như tìm trục chính (nhưng cách này có miền ứng dụng giới hạn và rất nhạy cảm với nhiễu [20])… trong luận văn sử dụng ma trận xoay (rotation matrix)[12].

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu đề tài ký hiệu hoá a, huấn luyện giải thuật để tìm ra trị trung bình (average) của ma trận đụng độ (collision matrix) trong giải thuật chiếu ngẫu nhiên-Random-Projection. Tiếp theo, luận văn đã thực nghiệm giải thuật nhận dạng mô-típ trên các tập dữ liệu chuỗi thời gian hình ảnh. Kết quả thực nghiệm cho thấy giải thuật nhận dạng mô-típ khi dùng phương pháp rời rạc hoá hoá ESAX (cả hai cách xoay RT1,RT2) thường thời gian thực thi nhanh hơn, và độ chính xác cao hơn khi giải thuật dùng phương pháp rời rạc hoá SAX. Hiện thực của hệ thống sẽ được trình bày cụ thể trong các chương tiếp theo trong luận văn.

Cấu trúc luận văn: Các chương tiếp theo trong luận văn được tổ chức như sau:  Chương 2: Các công trình liên quan. Trong chương này đề cập đến các công trình liên quan đến bài toán nhận dạng mô-típ, như: các kỹ thuật thu giảm số chiều, kỹ thuật rời rạc hoá, giải thuật nhận dạng mô-típ …  Chương 3: Cơ sở lý thuyết, nêu lên các lý thuyết được sử dụng trong luận văn: kỹ thuật thu giảm số chiều PAA, kỹ thuật SAX , ESAX , giải thuật chiếu ngẫu nhiên-Random-Projection …  Chương 4: Nội dung nghiên cứu, là các vấn đề khi nhận dạng mô-típ hình ảnh trong luận văn cần giải quyết, cũng như khi hiện thực chương trình.  Chương 5: Thực nghiệm, chương này trình bày các kết quả thực nghiệm trên một số tập dữ liệu chuỗi thời gian hình ảnh đã được thực hiện trong luận văn.  Chương 6: Kết luận, chương này nêu những nhận xét, kết luận, các đóng góp và hướng phát triển luận văn.

Luận Văn Thạc Sĩ – Trần Công Thanh 8 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN Trong chương này, luận văn trình bày về các công trình liên quan đến đề tài như các kỹ thuật thu giảm số chiều, các phương pháp rời rạc hoá, giải thuật nhận dạng mô-típ …. Trong số các bài toán khai phá dữ liệu chuỗi thời gian như phân lớp, gom cụm, trực quan hoá chuỗi thời gian….,bài toán phát hiện mô-típ trong tập dữ liệu chuỗi thời gian cũng thu hút nhiều sự quan tâm của các nhà nghiên cứu [4][6][14][20]…, và bài toán này cũng hỗ trợ cho các vấn đề gom cụm, phân lớp, tìm luật kết hợp, trực quan hoá … trong cơ sở dữ liệu chuỗi thời gian. Đầu tiên hỗ trợ cho bài toán tìm mô-típ là các độ đo tương tự: độ đo Euclidean, độ đo xoắn thời gian động - (Dynamic Time Warping - DTW), độ đo chuỗi con chung dài nhất (Longest Common Subsequence - LCS)… Tùy theo từng ứng dụng, mục đích khác nhau mà người dùng chọn các độ đo phù hợp. Kích thước chuỗi thời gian nói chung và chuỗi thời gian hình ảnh nói riêng thường rất lớn nên các kỹ thuật thu giảm số chiều(dimensional reduction), rời rạc hoá (discretization) … được đề xuất nhằm làm giảm tài nguyên tính toán, cũng như tài nguyên lưu trữ khi làm việc với dữ liệu chuỗi thời gian.

Thứ hai là các kỹ thuật thu giảm số chiều dựa vào đặc trưng: • Các phép biến đổi trong miền tần số như phép biến đổi Fourier – Discrete Fourier Transform (DFT), phép biến đổi Wavelet – Discrete Wavelet Transform (DWT), phép phân rã trị kỳ dị - Singlular Value Decomposition (SVD)… • Các phép biến đổi xấp xỉ từng đoạn như phương pháp xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise Constant Approximation – APCA) mà cụ thể là kỹ thuật xấp xỉ gộp từng đoạn – PAA ( Piecewise Aggregate Approximation) [8]. Luận Văn Thạc Sĩ – Trần Công Thanh 9 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan • Các phương pháp biến đổi dựa vào điểm quan trọng. Thứ ba là kỹ thuật rời rạc hoá dữ liệu như cụ thể là kỹ thuật xấp xỉ gộp ký hiệu hoá – SAX (Symbolic Aggregate approXimation) [15], phương pháp xấp xỉ gộp ký hiệu hoá mở rộng Extended SAX(Extension of Symbolic Aggregate approXimation ) [16]… Quan trọng là các giải thuật tìm kiếm mô-típ như giải thuật Brute-Force nhận dạng mô-típ, giải thuật EMMA được Lin cùng các cộng sự đề xuất 2002[14], giải thuật chiếu ngẫu nhiên – Random Projections được Buhler và Tompa đề xuất 2001[4] … Các ký hiệu sử dụng trong luận văn được trình bày trong bảng 2. Các kỹ thuật thu giảm số chiều dựa vào đặc trưng: Kỹ thuật thu giảm số chiều là kỹ thuật biến đổi dữ liệu chuỗi thời gian thành những đường cơ bản đã được định nghĩa trước, chuyển chuỗi thời gian T=t 1 ,.t n thành chuỗi C = c 1 ,… c w từ đó người dùng có thể lưu trữ và xử lý trên chuỗi có w giá trị.

Từ C khi phục hồi về T sẽ bị sai số, giá trị sai số tỉ lệ nghịch vào thông số w, nếu w càng lớn thì giá trị sai số càng nhỏ và ngược lại. Các phương pháp biến đổi trên miền tần số: 2. Phương pháp biến đổi Fourier rời rạc: Phương pháp biến đổi rời rạc Fourier (Discrete Fourier Tranform) – DFT do R. Agrawal và cộng sự đề nghị[1][2].

Trong phương pháp biến đổi Fourier thì đường dữ liệu ban đầu được biểu diễn bởi các đường căn bản. Nhưng đường căn bản trong trường hợp này là đường sin và cosin.1) Ngoài khả năng nén dữ liệu, với cách tính khoảng cách dựa trên khoảng cách Euclidean thì phương pháp Fourier cho phép so sánh gián tiếp 2 chuỗi X, Y thông qua khoảng cách của 2 chuỗi X f , Y f đã được biến đổi. Sở dĩ phép biến đổi Fourier rời rạc có tính chất trên là vì: Luận Văn Thạc Sĩ – Trần Công Thanh 10 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan D(X, Y) ≥ α D(X f , Y f ) (trong đó α là hằng số) Vì vậy, phương pháp biến đổi Fourier đã được sử dụng trong nhiều ứng dụng và một số phương pháp lập chỉ mục như F-index, ST-index …. Ưu điểm của phương pháp DFT là thích hợp với các loại đường biểu diễn dữ liệu khác nhau và giải thuật để biến đổi dữ liệu.

Tuy nhiên, nhược điểm lớn nhất của phương pháp là rất khó giải quyết nếu các chuỗi thời gian có chiều dài khác nhau, và phương pháp có độ phức tạp O(nlgn). Ký Ý nghĩa hiệu C một chuỗi thời gian C = c 1 , c 2 , …. c n C Chuỗi xấp xỉ gộp từng đoạn – PAA của chuỗi thời gian C = c1 , c2 … cw Chuỗi biểu diễn ký tự SAX của chuỗi thời gian S Chuỗi ESAX của chuỗi thời gian S = s11 , s21 , s31 , s12 , s22 , s32 ,., s1w , s2w , s3w w Số chiều thu giảm - Số đoạn trong chuỗi PAA của chuỗi thời gian a Kích thước tập ký tự dùng để biểu diễn SAX hay ESAX ( dùng {a,b,c}, thì a = 3). Các ký hiệu dùng trong luận văn .2 Phương pháp biến đổi wavelet rời rạc : Phương pháp thu giảm số chiều bằng biến đổi Wavelet rời rạc( Discrete Wavelet Transform) – DWT do K.

Phương pháp DWT cũng giống phương pháp DFT, tuy nhiên đường cơ bản của nó không phải là đường lượng giác sin hay cosin mà là đường Haar. Đường Haar được định nghĩa theo các công thức ψ ij như sau: Luận Văn Thạc Sĩ – Trần Công Thanh 11 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan ψ if ψ (2 j x − i ) = (2.5 < t < 1 0 các trường hợp khác Ngoài sử dụng đường Haar, phương pháp Wavelet có thể sử dụng các đường cơ bản khác như đường Daubechies, Coiflet, Symmlet…Tuy nhiên, Haar Wavalet đã được sử dụng nhiều trong khai phá dữ liệu chuỗi thời gian và lập chỉ mục. Phương pháp biến đổi Wavelet rời rạc rất hiệu quả bởi vì nó mã hoá đơn giản và nhanh. Độ phức tạp của việc mã hoá này là tuyến tính.

Một ưu điểm của phương pháp Wavelet là nó hỗ trợ nhiều mức phân giải. Tuy nhiên nhược điểm là chiều dài chuỗi dữ liệu ban đầu của nó phải là một số lũy thừa hai và chiều dài của chuỗi con truy vấn cũng nên là số lũy thừa của hai thì giải thuật mới thực hiện hiệu quả. Các kỹ thuật xấp xỉ tuyến tính từng đoạn : Phương pháp xấp xỉ tuyến tính từng đoạn - PLA: Phương pháp xấp xỉ gộp từng đoạn – PLA (Piecewise Linear Approximation) do E. Keogh và cộng sự đề nghị năm 2001[10][11].

Phương pháp này rất đơn giản, các tác giả tuần tự xấp xỉ k giá trị liền kề nhau thành một đoạn thẳng tuyến tính. Quá trình cứ tiếp tục như vậy từ trái sang phải. Kết quả cuối cùng là đoạn thẳng có thể liên tục hoặc rời nhau. Ưu điểm của cách biểu diễn này là thời gian tính toán tuyến tính, trực quan và cách biểu diễn của nó hỗ trợ nhiều độ đo khoảng cách.

Nhược điểm lớn nhất là chưa có cách lập chỉ mục hiệu quả cho cách biểu diễn này. Luận Văn Thạc Sĩ – Trần Công Thanh 12 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan Kỹ thuật xấp xỉ gộp từng đoạn - PAA: Keogh và các cộng sự, 2000 [8] đã đề nghị kỹ thuật thu giảm chiều là kỹ thuật xấp xỉ gộp từng đoạn - PAA ( Piecewise Aggregate Approximation). Cho chuỗi thời gian C = c 1 , c 2 , …. c n có chiều dài n được chuyển vào không gian w chiều ( 1≤ w ≤ n) thành vector C = c1 , c2 … cw thành phần thứ i sẽ được tính theo công thức sau: ni w w ci = ∑ cj n j= n ( i −1)+1 (2.3) w Thành phần thứ i của vector C là trung bình cộng của k phần tử liên tiếp từ phần tử thứ (k ( i - 1) + 1)  ki của chuỗi thời gian C với tỉ số nén k = n w Nếu w bằng n thì chuỗi PAA bằng đúng chuỗi chuỗi thời gian gốc, nếu w bằng 1 thì chuỗi biểu diễn PAA chỉ còn là một giá trị trung bình cộng của chuỗi thời gian gốc.

Cho một chuỗi thời gian có tám phần tử muốn thu giảm về hai phần tử như hình 2. Chuỗi thời gian X = (-1,-2,-1,0,2,1,1,0) n =|X| =8 2 2 Tính PAA: X = ( ( (−1 + −2 + −1 + 0) ),( (2 + 1 + 1 + 0) )) w = X =2 8 8 X =(-1,1) Biểu diễn PAA của chuỗi thời gian có thể trực quan hoá là sự kết tuyến tính của các hàm vuông như hình 2.