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 chuyên sâu Nhận dạng mô típ trong chuỗi thời gian hình ảnh - Luận văn thạc sĩ Khoa học máy tính, phương pháp luận hiện đại, kết quả ứng

• 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 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 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: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• MỤC LỤC HÌNH
• MỤC LỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Động cơ nghiên cứu
• 1.1.1. Dữ liệu chuỗi thời gian
• 1.1.2. Bài toán nhận dạng mô-típ
• 1.2. Mục tiêu và giới hạn luận văn
• 1.3. Tóm tắt kết quả
• 1.4. Cấu trúc luận văn
• 2. CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Các kỹ thuật thu giảm số chiều dựa vào đặc trưng
• 2.1.1. Các phương pháp biến đổi trên miền tần số
• 2.1.2. Các kỹ thuật xấp xỉ tuyến tính từng đoạn
• 2.1.3. Các phương pháp rời rạc hoá
• 2.1.3.1. Kỹ thuật xấp xỉ gộp ký hiệu hoá – SAX
• 2.1.3.2. Kỹ thuật xấp xỉ gộp ký hiệu hoá mở rộng – Extended SAX
• 2.1.3.3. Phương pháp iSAX
• 2.2. Các công trình tìm kiếm mô-típ
• 2.2.1. Giải thuật Brute-Force
• 2.2.2. Giải thuật EMMA
• 2.2.3. Giải thuật nhận dạng mô-típ dùng kỹ thuật chiếu ngẫu nhiên
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 3.1. Cách chuyển hình ảnh sang chuỗi thời gian
• 3.2. Khái niệm trùng khớp
• 3.3. Mô-típ hình ảnh
• 3.4. Độ đo xoắn thời gian động
• 3.5. Chuẩn hoá dữ liệu
• 3.6. Một số giải thuật nhận dạng mô-típ
• 3.6.1. Giải thuật Brute-Force
• 3.6.2. Giải thuật EMMA
• 3.6.3. Giải thuật chiếu ngẫu nhiên-Random Projection
• 3.7. Hướng tiếp cận bài toán
• 4. CHƯƠNG 4: NỘI DUNG NGHIÊN CỨU
• 4.1. Giới thiệu hệ thống
• 4.2. Các thành phần hệ thống
• 4.2.1. Kỹ thuật thu giảm số chiều PAA, EPAA
• 4.2.2. Kỹ thuật rời rạc hoá SAX, ESAX
• 4.2.3. Giải thuật nhận dạng mô-típ dùng kỹ thuật rời rạc hoá SAX
• 4.2.4. Giải thuật nhận dạng mô-típ dùng kỹ thuật rời rạc hoá ESAX
• 4.3. Đánh giá giải thuật
• 4.3.1. Khảo sát các thông số
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Khảo sát các thông số
• 5.2. Hệ thống nhận dạng mô-típ
• 5.2.1. Giải thuật Brute-force
• 5.2.2. Giải thuật Chiếu ngẫu nhiên (Random Projection)
• 5.2.3. So sánh kết quả SAX / ESAX
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Những đóng góp của luận văn
• 6.2. Hướng phát triển đề tài
• TÀI LIỆU THAM KHẢO
• BẢNG PHỤ LỤC
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng quan về nhận dạng mô típ trong chuỗi thời gian hình ảnh

Nhận dạng mô típ trong chuỗi thời gian hình ảnh là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính. Nó liên quan đến việc tìm kiếm các mẫu lặp lại trong dữ liệu hình ảnh theo thời gian. Các ứng dụng của nó rất đa dạng, từ khảo cổ học đến sinh học. Việc hiểu rõ về chuỗi thời gian và cách thức hoạt động của nó là rất cần thiết để phát triển các giải pháp hiệu quả.

1.1. Định nghĩa chuỗi thời gian hình ảnh

Chuỗi thời gian hình ảnh là tập hợp các hình ảnh được ghi nhận theo thời gian. Mỗi hình ảnh trong chuỗi có thể được xem như một điểm dữ liệu trong không gian thời gian. Việc phân tích chuỗi thời gian hình ảnh giúp nhận diện các mô típ và xu hướng trong dữ liệu.

1.2. Tầm quan trọng của nhận dạng mô típ

Nhận dạng mô típ có vai trò quan trọng trong nhiều lĩnh vực, bao gồm khảo cổ học và sinh học. Nó giúp xác định mối quan hệ giữa các mẫu hình ảnh và hỗ trợ trong việc phân tích dữ liệu lớn.

II. Thách thức trong nhận dạng mô típ hình ảnh

Việc nhận dạng mô típ trong chuỗi thời gian hình ảnh gặp phải nhiều thách thức. Các vấn đề như khối lượng dữ liệu lớn, sự không đồng nhất trong dữ liệu và yếu tố chủ quan trong quá trình thu thập dữ liệu đều ảnh hưởng đến độ chính xác của các thuật toán nhận dạng.

2.1. Khối lượng dữ liệu lớn

Chuỗi thời gian hình ảnh thường chứa một lượng lớn dữ liệu, điều này gây khó khăn trong việc xử lý và phân tích. Các kỹ thuật thu giảm số chiều và rời rạc hóa là cần thiết để giảm thiểu khối lượng dữ liệu.

2.2. Sự không đồng nhất trong dữ liệu

Dữ liệu hình ảnh có thể được thu thập từ nhiều nguồn khác nhau, dẫn đến sự không đồng nhất. Điều này có thể làm giảm tính chính xác của các thuật toán nhận dạng mô típ.

III. Phương pháp rời rạc hóa trong nhận dạng mô típ

Phương pháp rời rạc hóa là một trong những kỹ thuật quan trọng trong nhận dạng mô típ. Hai phương pháp chính được nghiên cứu là SAX và ESAX. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, ảnh hưởng đến hiệu quả của việc nhận dạng mô típ.

3.1. Kỹ thuật SAX

SAX (Symbolic Aggregate approXimation) là một phương pháp rời rạc hóa dữ liệu chuỗi thời gian. Nó giúp giảm số chiều của dữ liệu mà vẫn giữ lại các thông tin quan trọng. Tuy nhiên, SAX có thể mất đi một số mẫu thức quan trọng trong dữ liệu.

3.2. Kỹ thuật ESAX

ESAX (Extended SAX) là một cải tiến của SAX, cho phép giữ lại nhiều thông tin hơn bằng cách thêm vào các giá trị cực trị của mỗi phân đoạn. Điều này giúp cải thiện độ chính xác trong việc nhận dạng mô típ.

IV. Ứng dụng thực tiễn của nhận dạng mô típ

Nhận dạng mô típ trong chuỗi thời gian hình ảnh có nhiều ứng dụng thực tiễn. Từ khảo cổ học đến sinh học, các mô típ hình ảnh giúp xác định mối quan hệ giữa các mẫu và hỗ trợ trong việc phân tích dữ liệu lớn.

4.1. Ứng dụng trong khảo cổ học

Trong khảo cổ học, việc tìm kiếm các mô típ hình ảnh giúp xác định mối quan hệ giữa các khu vực và thời kỳ khác nhau. Điều này có thể cung cấp thông tin quý giá về lịch sử và văn hóa.

4.2. Ứng dụng trong sinh học

Trong sinh học, nhận dạng mô típ giúp phân tích hình ảnh của các loài vật và xác định mối quan hệ tiến hóa giữa chúng. Điều này hỗ trợ trong việc nghiên cứu và bảo tồn các loài.

V. Kết luận và tương lai của nhận dạng mô típ

Nhận dạng mô típ trong chuỗi thời gian hình ảnh là một lĩnh vực nghiên cứu đầy tiềm năng. Với sự phát triển của công nghệ và các thuật toán mới, khả năng nhận dạng mô típ sẽ ngày càng chính xác và hiệu quả hơn. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều ứng dụng thực tiễn hơn nữa.

5.1. Xu hướng phát triển

Các nghiên cứu trong tương lai sẽ tập trung vào việc cải thiện độ chính xác và hiệu suất của các thuật toán nhận dạng mô típ. Việc áp dụng trí tuệ nhân tạo và học máy sẽ mở ra nhiều cơ hội mới.

5.2. Thách thức trong tương lai

Mặc dù có nhiều tiềm năng, nhưng nhận dạng mô típ vẫn đối mặt với nhiều thách thức, bao gồm việc xử lý dữ liệu lớn và sự không đồng nhất trong dữ liệu. Giải quyết những vấn đề này sẽ là chìa khóa cho sự phát triển của lĩnh vực này.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu đa phương tiện, việc khai phá và truy vấn thông tin từ các cơ sở dữ liệu hình ảnh quy mô lớn đang đối mặt với thách thức nghiêm trọng về chi phí tính toán. Một phép đo tín hiệu y tế như điện tâm đồ ECG trong 1 giờ có thể tạo ra khoảng 1 Gigabyte dữ liệu, và các kho lưu trữ hình ảnh khảo cổ học hay sinh học cũng tích lũy hàng chục nghìn mẫu vật phức tạp theo thời gian. Bài toán nhận dạng mô-típ hình ảnh (Image Motif Discovery) hướng đến việc phát hiện tự động các mẫu hình lặp lại mang tính quy luật mà không cần biết trước mẫu truy vấn. Tuy nhiên, tính toán trực tiếp trên không gian 2D với độ phức tạp thuật toán vét cạn Brute-Force lên tới bậc hai về số lượng mẫu và chiều dài chuỗi khiến hệ thống truyền thống mất hàng chục giờ xử lý.

Đề tài tập trung giải quyết bài toán phát hiện mô-típ trong dữ liệu chuỗi thời gian hình ảnh với khả năng bất biến đối với góc xoay 360 độ. Mục tiêu cụ thể là nghiên cứu ứng dụng kỹ thuật rời rạc hóa xấp xỉ gộp ký hiệu hóa mở rộng ESAX (Extended Symbolic Aggregate Approximation), đồng thời tích hợp vào thuật toán Chiếu ngẫu nhiên (Random Projection) để so sánh hiệu năng thực nghiệm với phương pháp SAX cổ điển. Nghiên cứu được triển khai thực nghiệm trên các tập dữ liệu biên dạng hình ảnh tiêu chuẩn như hiện vật mũi tên đá, đường biên lá cây và các tư thế vận động hình thể. Kết quả đạt được minh chứng phương pháp ESAX giúp giảm hơn 30% số lần gọi hàm tính khoảng cách thực tế, nâng cao độ chính xác nhận dạng và duy trì độ phức tạp thời gian thực thi ở mức tuyến tính với số lượng chuỗi dữ liệu đầu vào.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự kết hợp chặt chẽ giữa các mô hình biểu diễn dữ liệu chuỗi thời gian và thuật toán khai phá mẫu ngẫu nhiên:

• Lý thuyết xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate Approximation) và PAA mở rộng EPAA: Phương pháp PAA chia chuỗi dữ liệu gốc độ dài n thành w phân đoạn bằng nhau và lấy giá trị trung bình đại diện, giúp giảm số chiều tính toán đáng kể. Kỹ thuật EPAA khắc phục hạn chế mất mát thông tin cục bộ của PAA bằng cách trích xuất bộ ba giá trị gồm giá trị trung bình, giá trị cực tiểu và giá trị cực đại trên từng phân đoạn.
• Kỹ thuật rời rạc hóa SAX và ESAX: Dữ liệu sau khi chuẩn hóa về phân bố xác suất Gauss chuẩn với giá trị trung bình bằng 0 và độ lệch chuẩn bằng 1 được phân chia bởi a điểm ngắt (breakpoints) có diện tích xác suất tương đương nhau (1/a). ESAX biểu diễn mỗi đoạn thành bộ ba ký tự theo đúng thứ tự thời gian xuất hiện, bảo toàn hình thái biên dạng tốt hơn SAX.
• Khoảng cách cận dưới MINDIST: Hàm khoảng cách trên từ ký hiệu đóng vai trò là cận dưới của khoảng cách Euclidean thực tế, đảm bảo nguyên tắc không phát sinh trường hợp loại trừ sai (no false dismissal) khi cắt tỉa không gian tìm kiếm.
• Thuật toán Chiếu ngẫu nhiên (Random Projection): Sử dụng kỹ thuật tạo mặt nạ ngẫu nhiên trên các từ ký tự để băm dữ liệu vào các nhóm (buckets), từ đó xây dựng ma trận va chạm (collision matrix) nhằm xác định nhanh các cặp đối tượng có khả năng cao tạo thành mô-típ.

Phương pháp nghiên cứu

Nguồn dữ liệu thực nghiệm bao gồm các tập dữ liệu hình ảnh 2D được thu thập từ các kho dữ liệu nghiên cứu hình thái sinh học và chuyển động thực tế. Dữ liệu được tiền xử lý thông qua phương pháp chuyển đổi đường biên 2D thành chuỗi thời gian 1 chiều sử dụng khoảng cách trọng tâm (Centroid Distance). Tọa độ tâm hình ảnh được xác định chính xác theo công thức trung bình cộng tọa độ các điểm biên, sau đó tiến hành quét đường biên theo chiều kim đồng hồ để đo khoảng cách từ tâm đến từng điểm.

Cỡ mẫu thử nghiệm được chuẩn hóa đồng nhất về độ dài 128 đến 512 điểm dữ liệu cho mỗi chuỗi hình ảnh, áp dụng quy trình chuẩn hóa z-score để loại bỏ ảnh hưởng của tỷ lệ kích thước. Nhóm nghiên cứu lựa chọn phương pháp phân tích thực nghiệm so sánh đa chiều: khảo sát độ chặt cận dưới (Tightness of Lower Bound) để tìm bộ tham số tối ưu gồm số chiều nén w (khảo sát từ 8 đến 30 đoạn) và kích thước bảng chữ cái a (khảo sát từ 3 đến 20 ký tự). Quy trình nghiên cứu diễn ra qua hai giai đoạn: giai đoạn 1 tối ưu hóa các ma trận xoay RT1 và RT2 nhằm đảm bảo tính bất biến góc xoay; giai đoạn 2 chạy thuật toán Chiếu ngẫu nhiên với số vòng lặp từ 20 đến 100 lần để đánh giá độ chính xác và thời gian thực thi so với thuật toán Brute-Force đối chuẩn.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối chiếu giữa hai phương pháp rời rạc hóa SAX và ESAX trên nền tảng thuật toán Chiếu ngẫu nhiên đã ghi nhận 4 phát hiện quan trọng:

• Khả năng bảo toàn đặc trưng hình học vượt trội: Phương pháp ESAX với việc lưu trữ giá trị cực đại và cực tiểu giúp giảm thiểu đáng kể lỗi khôi phục tín hiệu so với SAX. Trong các cấu hình thử nghiệm với tham số w = 30 và a = 20, ESAX mô tả chính xác các góc nhọn và đoạn gấp khúc của đường biên hình ảnh, giúp nâng cao độ chính xác phân loại mô-típ thêm khoảng 18% đến 25% so với SAX.
• Cắt giảm đáng kể chi phí tính toán hàm khoảng cách: Khi truy vấn các ứng viên tiềm năng từ ma trận va chạm, hệ thống sử dụng ESAX giúp loại bỏ các ứng viên sai từ sớm nhờ cận dưới MINDIST chặt chẽ hơn. Số lần gọi hàm khoảng cách Euclidean thực tế giảm từ 30% đến 42% trên các tập dữ liệu hình ảnh chuyển động và hình học phức tạp.
• Hiệu quả ổn định của chiến lược xoay chuỗi ký tự RT2: Giữa hai phương thức tạo ma trận xoay, phương thức RT2 (xoay dựa trên từng khối bộ ba ký tự của ESAX) cho thấy sự ổn định cao hơn RT1, duy trì tỷ lệ phát hiện đúng 1-motif đạt mức trên 92% ngay cả khi góc xoay ban đầu của hình ảnh bị lệch ngẫu nhiên.
• Tối ưu hóa thời gian thực thi tổng thể: Thuật toán Chiếu ngẫu nhiên kết hợp ESAX đạt tốc độ xử lý nhanh hơn từ 1,3 đến 1,8 lần so với khi sử dụng SAX trên cùng cấu hình phần cứng, đồng thời vượt trội hoàn toàn so với thuật toán Brute-Force vốn có thời gian chạy tăng theo hàm số mũ bậc hai.

Thảo luận kết quả

Hiệu năng vượt trội của ESAX bắt nguồn từ cơ chế biểu diễn đa chiều cục bộ. Trong khi SAX thuần túy làm phẳng các biến động biên dạng bằng một giá trị trung bình duy nhất, phương pháp EPAA và ESAX nắm bắt được biên độ dao động thực tế thông qua các điểm cực trị. Điều này ngăn ngừa hiện tượng hai đường biên có hình thái hoàn toàn khác nhau nhưng có cùng giá trị trung bình bị ánh xạ vào cùng một ký hiệu.

Các kết quả thực nghiệm có thể được tổng hợp trực quan qua biểu đồ đường biểu diễn sự biến thiên của độ chặt cận dưới theo kích thước bảng chữ cái a, và bảng ma trận va chạm thể hiện tần suất tích lũy của các cặp mô-típ. Kết quả này củng cố các luận điểm lý thuyết của các nghiên cứu quốc tế trước đây về chuỗi thời gian tài chính, đồng thời chứng minh tính khả thi vượt bậc khi mở rộng mô hình này sang miền dữ liệu hình ảnh 2D. Thuật toán cũng loại bỏ thành công các trường hợp trùng khớp tầm thường (trivial match) giữa các khung hình liền kề, đảm bảo các mô-típ phát hiện được phản ánh đúng cấu trúc hình thái học có ý nghĩa thực tế.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đề xuất 4 nhóm khuyến nghị hành động cụ thể nhằm hoàn thiện và ứng dụng giải thuật vào thực tiễn:

• Tối ưu hóa tự động bộ tham số tiền xử lý: Các kỹ sư thị giác máy tính và phân tích dữ liệu cần xây dựng mô-đun tự động lựa chọn số chiều thu giảm w và kích thước ký tự a dựa trên việc đánh giá nhanh độ chặt cận dưới trước khi xử lý tập dữ liệu lớn. Mục tiêu là cắt giảm 50% thời gian cấu hình thủ công trong vòng 3 tháng tới.
• Nâng cấp kiến trúc xử lý song song trên GPU: Nhóm nghiên cứu hệ thống và các nhà phát triển phần mềm cần chuyển đổi giải thuật chiếu ngẫu nhiên sang mô hình tính toán đa luồng hoặc xử lý song song trên card đồ họa. Việc này hướng đến mục tiêu mở rộng quy mô xử lý các cơ sở dữ liệu trên 100.000 hình ảnh trong lộ trình 6 đến 12 tháng.
• Chuẩn hóa quy trình số hóa đường biên cho ứng dụng chuyên ngành: Các cơ quan nghiên cứu khảo cổ học và y sinh học nên ứng dụng quy trình chuyển đổi Centroid Distance kết hợp ma trận xoay RT2 để tự động nhận dạng, phân loại các mảnh gốm cổ, mẫu xương hoặc phân tích tư thế vận động y khoa với độ chính xác kỳ vọng đạt trên 95% trong vòng 12 tháng.
• Tích hợp cấu trúc cây chỉ mục phân cấp: Khuyến nghị các nhà nghiên cứu khoa học máy tính tiếp tục kết hợp kỹ thuật ESAX với cấu trúc cây chỉ mục như iSAX để giải quyết bài toán truy vấn mô-típ đa độ phân giải trên các tập dữ liệu kích thước Terabyte trong giai đoạn 18 tháng tiếp theo.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị học thuật và ứng dụng thực tiễn rõ nét cho 4 nhóm đối tượng chính:

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính, Trí tuệ Nhân tạo: Nắm vững phương pháp luận nghiên cứu thực nghiệm, kỹ thuật giảm số chiều dữ liệu và cách xây dựng các thuật toán khai phá dữ liệu bất biến góc xoay.
• Kỹ sư phát triển phần mềm thị giác máy tính và khai phá dữ liệu: Tiếp cận thuật toán tối ưu để triển khai các hệ thống truy vấn hình ảnh dựa trên nội dung (Content-Based Image Retrieval) với hiệu năng xử lý cao và chi phí bộ nhớ thấp.
• Các nhà nghiên cứu trong lĩnh vực Tin sinh học và Y sinh: Ứng dụng giải thuật để tìm kiếm các đoạn chuỗi tương đồng trong cấu trúc sinh học, nhận dạng bất thường trong điện tâm đồ ECG hoặc phân tích dáng đi bệnh lý.
• Chuyên gia số hóa di sản và khảo cổ học: Sử dụng công cụ để phân loại tự động hiện vật cổ, so khớp mẫu hoa văn và liên kết các di chỉ khảo cổ học dựa trên hình thái học 2D.

Câu hỏi thường gặp

Tại sao cần chuyển đổi hình ảnh 2D thành chuỗi thời gian trước khi tìm mô-típ? Việc chuyển đổi đường biên 2D thành chuỗi thời gian 1 chiều thông qua khoảng cách trọng tâm giúp đơn giản hóa cấu trúc dữ liệu phức tạp. Phương pháp này cho phép tái sử dụng các thuật toán khai phá chuỗi thời gian mạnh mẽ, giảm hơn 70% tài nguyên tính toán so với việc xử lý trực tiếp trên lưới ma trận điểm ảnh 2D.

Phương pháp ESAX khắc phục nhược điểm gì của SAX truyền thống? SAX chỉ sử dụng giá trị trung bình trên mỗi đoạn nên dễ làm mất các điểm cực trị biên dạng quan trọng. ESAX bổ sung giá trị nhỏ nhất và lớn nhất vào mỗi phân đoạn, tạo thành bộ ba ký tự đặc trưng giúp giảm lỗi khôi phục và tăng độ chính xác phân biệt hình thái lên khoảng 20%.

Thuật toán Chiếu ngẫu nhiên giải quyết bài toán tốc độ như thế nào? Thay vì so sánh từng cặp hình ảnh với độ phức tạp bậc hai, Chiếu ngẫu nhiên sử dụng kỹ thuật tạo mặt nạ để băm các chuỗi ký hiệu vào các nhóm tương đồng. Nhờ đó, thuật toán chỉ cần kiểm tra chi tiết các ứng viên có tần suất va chạm cao, đưa thời gian xử lý về mức tuyến tính sau khoảng 20 đến 100 lần lặp.

Hệ thống xử lý vấn đề góc xoay của hình ảnh bằng cách nào? Nghiên cứu áp dụng ma trận xoay chuỗi ký tự bằng cách dịch chuyển tuần hoàn các ký hiệu SAX và ESAX. Khi hai hình ảnh giống nhau nhưng lệch góc quay, chuỗi ký tự của chúng sẽ khớp nhau sau một số bước dịch chuyển nhất định, đảm bảo tính bất biến toàn diện trong không gian 360 độ.

Trùng khớp tầm thường là gì và tại sao phải loại bỏ? Trùng khớp tầm thường xảy ra giữa các khung hình hoặc đoạn dữ liệu nằm liền kề nhau về mặt thời gian hoặc không gian, vốn luôn có độ tương đồng rất cao. Loại bỏ trùng khớp tầm thường giúp thuật toán tập trung tìm kiếm các mẫu lặp lại thực sự độc lập, tránh hiện tượng phát hiện mô-típ giả trong cơ sở dữ liệu.

Kết luận

• Luận văn đã hiện thực hóa thành công giải thuật nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh bất biến với góc xoay dựa trên kỹ thuật Chiếu ngẫu nhiên.
• Đóng góp trọng tâm là việc áp dụng và cải tiến phương pháp rời rạc hóa ESAX kết hợp với ma trận xoay RT1 và RT2, chứng minh tính ưu việt rõ rệt so với SAX cổ điển.
• Kết quả thực nghiệm khẳng định ESAX giúp tăng độ chính xác nhận dạng, giảm hơn 30% số lần tính toán khoảng cách Euclidean và rút ngắn thời gian xử lý toàn hệ thống.
• Cung cấp phương pháp luận chặt chẽ trong việc tối ưu hóa tham số nén dữ liệu w và kích thước bảng ký tự a dựa trên độ chặt cận dưới.
• Mở ra tiềm năng ứng dụng thực tiễn rộng mở trong các bài toán thị giác máy tính, phân loại hiện vật khảo cổ học, phân tích chuyển động y sinh và tìm kiếm hình ảnh quy mô lớn.

Các đơn vị nghiên cứu, doanh nghiệp phát triển giải pháp AI và các nhà khoa học dữ liệu quan tâm có thể tiếp cận toàn văn công trình để ứng dụng bộ khung giải thuật tối ưu này vào các bài toán khai phá dữ liệu đa phương tiện phức tạp.

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.