Nghiên cứu phát triển kỹ thuật tìm kiếm hình ảnh hai chiều dựa trên chuỗi thời gian

Luận văn thạc sĩ kỹ thuật phân tích máy tính phát triển kỹ thuật tìm kiếm hình ảnh hai chiều dựa trên chuỗi thời gian, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả

• Tác giả: Trần Công Đời
• Người hướng dẫn: TS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa - Đại học Quốc Gia Tp. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát Triển Kỹ Thuật Tìm Kiếm Hình Ảnh Hai Chiều Dựa Trên Chuỗi Thời Gian
• 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

Mục lục chi tiết

• LỜI CAM ĐOAN
• TÓM TẮT LUẬN VĂN
• DANH MỤC HÌNH VẼ
• DANH MỤC CÁC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Biểu diễn ảnh dạng chuỗi thời gian
• 1.3. Kỹ thuật tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian
• 1.4. Mục tiêu và giới hạn của đề tài
• 1.5. Tóm lược những kết quả đạt được
• 1.6. Cấu trúc của luận văn
• 2. CHƯƠNG 2: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Công trình về độ đo tương tự
• 2.1.1. Độ đo Minkowski – Độ đo khoảng cách Euclid
• 2.1.2. Độ đo xoắn thời gian động (Dynamic Time Warping – DTW)
• 2.1.3. Phương pháp chuỗi con chung dài nhất (Longest Common Subsequence – LCS)
• 2.2. Các công trình về biểu diễn chuỗi thời gian
• 2.2.1. Các phương pháp thu giảm số chiều
• 2.2.2. Các cấu trúc chỉ mục
• 2.3. Kỹ thuật xử lý phép quay trên chuỗi thời gian của ảnh
• 2.3.1. Các hướng tiếp cận
• 2.3.2. Các công trình
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 3.1. Phép biến đổi Fourier rời rạc DFT trên chuỗi thời gian của ảnh
• 3.1.1. Nén chuỗi Fourier
• 3.1.2. Hàm biên dưới
• 3.2. Cấu trúc dữ liệu VP-Tree
• 3.2.1. Xây dựng VP-Tree
• 3.2.2. Tìm kiếm lân cận gần nhất trên VP-Tree
• 3.3. Cấu trúc dữ liệu VPC-Tree
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Kỹ thuật tìm kiếm ảnh dựa trên dữ liệu chuỗi thời gian của ảnh
• 4.1.1. Phương pháp biến đổi ảnh sang dữ liệu chuỗi thời gian
• 4.1.2. Các phương pháp thu giảm số chiều
• 4.1.3. Cấu trúc dữ liệu sử dụng lập chỉ mục
• 4.1.4. Các mức độ lưu trữ trong tập dữ liệu
• 4.1.5. Giải thuật tìm kiếm lân cận trên cây VP-Tree cải tiến
• 4.2. Kiến trúc hệ thống
• 4.2.1. Hệ thống 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
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Tập dữ liệu dùng cho thực nghiệm
• 5.2. Các tiêu chuẩn tiến hành thực nghiệm
• 5.2.1. Hệ số thu giảm truy xuất
• 5.2.2. Số lần truy xuất đĩa trong quá trình tìm kiếm
• 5.2.3. Thời gian tìm kiếm
• 5.2.4. Kích thước lưu trữ chỉ mục
• 5.3. Đánh giá kết quả thực nghiệm
• 5.3.1. Thực nghiệm trên tập dữ liệu Data1
• 5.3.2. Thực nghiệm trên tập dữ liệu Data2 và Data3
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.2. Những đóng góp của đề tài
• 6.3. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới thiệu đề tài

Chương này trình bày các khái niệm cơ bản về chuỗi thời gian, đặc biệt là việc chuyển đổi hình ảnh hai chiều thành dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian là một tập hợp có thứ tự các quan sát đơn biến hoặc đa biến được đo theo thời gian. Việc chuyển đổi này cho phép áp dụng các kỹ thuật tìm kiếm hình ảnh hiện đại, mở rộng khả năng tìm kiếm và phân tích. Kỹ thuật tìm kiếm hình ảnh dựa trên dữ liệu chuỗi thời gian cung cấp một phương pháp mới để xử lý và truy vấn hình ảnh, đồng thời giải quyết các vấn đề như độ nhiễu và tính bất biến trong phép quay. Mục tiêu của đề tài là phát triển một khung tổng quát cho kỹ thuật này, giúp nâng cao hiệu quả và độ chính xác trong việc tìm kiếm.

1.1 Dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian được định nghĩa là tập hợp các quan sát theo thời gian, có thể là đơn biến hoặc đa biến. Trong nghiên cứu này, chuỗi thời gian được xem xét như một tập hợp dữ liệu hai chiều với các giá trị tương ứng. Các ứng dụng của chuỗi thời gian rất đa dạng, từ phân tích tài chính đến y tế, và đều yêu cầu các phương pháp tìm kiếm tương tự. Các thách thức trong việc xử lý dữ liệu này bao gồm độ nhiễu và sự không đồng nhất về số chiều của dữ liệu, điều này đòi hỏi các phương pháp lập chỉ mục hiệu quả để nâng cao tốc độ tìm kiếm.

1.2 Biểu diễn ảnh dạng chuỗi thời gian

Chuyển đổi hình ảnh hai chiều sang chuỗi thời gian giúp khai thác các đặc điểm của ảnh trong một không gian mới. Phương pháp được sử dụng trong luận văn này dựa trên đường biên hình dạng của ảnh, từ đó tạo ra dữ liệu chuỗi thời gian. Các đặc điểm như nhiễu, phép tỉ lệ và phép quay được xử lý để đảm bảo tính chính xác trong tìm kiếm. Việc biểu diễn ảnh dưới dạng chuỗi thời gian cho phép áp dụng các kỹ thuật machine learning và các phương pháp lập chỉ mục để cải thiện hiệu quả tìm kiếm.

1.3 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 chuỗi thời gian là một trong những ứng dụng quan trọng trong lĩnh vực tìm kiếm hình ảnh. Hàm khoảng cách được sử dụng để đo lường độ tương tự giữa các ảnh trong cơ sở dữ liệu, yêu cầu tính bất biến đối với nhiễu và phép quay. Các thách thức chính bao gồm việc xử lý ảnh truy vấn bị nhiễu và lƣu trữ tập dữ liệu lớn. Mục tiêu của nghiên cứu là phát triển một khung tổng quát cho kỹ thuật này, giúp cải thiện tốc độ và độ chính xác trong tìm kiếm.

II. Tổng thuật các công trình liên quan

Chương này tổng hợp các công trình nghiên cứu trước đây liên quan đến tìm kiếm hình ảnh và chuỗi thời gian. Các nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp như Dynamic Time Warping (DTW) và Longest Common Subsequence (LCS) có thể cải thiện đáng kể độ chính xác trong việc tìm kiếm hình ảnh. Những công trình này đã phát triển các độ đo tương tự, từ đó cung cấp nền tảng cho việc xây dựng các cấu trúc chỉ mục hiệu quả. Việc sử dụng các phương pháp nén dữ liệu cũng đã được nghiên cứu để giảm thiểu kích thước dữ liệu trong quá trình tìm kiếm. Những nghiên cứu này đã khẳng định tầm quan trọng của việc phát triển các phương pháp mới nhằm nâng cao hiệu quả tìm kiếm hình ảnh trong các ứng dụng thực tế.

2.1 Công trình về độ đo tương tự

Các công trình nghiên cứu về độ đo tương tự đã chỉ ra rằng độ đo Minkowski và độ đo khoảng cách Euclid là những phương pháp phổ biến trong việc đánh giá độ tương tự giữa các chuỗi thời gian. Đặc biệt, Dynamic Time Warping (DTW) được sử dụng để xử lý các chuỗi có độ dài khác nhau, cho phép tìm kiếm chính xác hơn trong các tập dữ liệu lớn. Những nghiên cứu này đã tạo điều kiện cho việc phát triển các kỹ thuật tìm kiếm hình ảnh hiệu quả hơn.

2.2 Các công trình về biểu diễn chuỗi thời gian

Việc biểu diễn chuỗi thời gian là một yếu tố quan trọng trong việc tìm kiếm hình ảnh. Nhiều phương pháp thu giảm số chiều đã được đề xuất, bao gồm Piecewise Aggregate Approximation (PAA) và Symbolic Aggregate approXimation (SAX). Những phương pháp này giúp giảm kích thước dữ liệu mà không làm mất đi các đặc trưng chính của dữ liệu, từ đó cải thiện tốc độ tìm kiếm và độ chính xác.

2.3 Kỹ thuật xử lý phép quay trên chuỗi thời gian của ảnh

Nghiên cứu về việc xử lý phép quay trên chuỗi thời gian của ảnh đã chỉ ra rằng việc áp dụng các phương pháp như Fourier Transform có thể giúp đạt được tính bất biến trong phép quay. Các công trình trước đã phát triển nhiều phương pháp để xử lý độ nhiễu và cải thiện độ chính xác trong tìm kiếm. Việc áp dụng các kỹ thuật này trong nghiên cứu hiện tại sẽ góp phần nâng cao hiệu quả của hệ thống tìm kiếm hình ảnh.

III. Cơ sở lý thuyết

Chương này trình bày các lý thuyết cơ bản liên quan đến chuỗi thời gian và các phương pháp xử lý dữ liệu. Biến đổi Fourier được sử dụng để trích xuất đặc trưng từ dữ liệu chuỗi thời gian, giúp đạt được tính bất biến trong phép quay. Cấu trúc dữ liệu VP-Tree được giới thiệu như một giải pháp lập chỉ mục hiệu quả, giúp tăng tốc độ tìm kiếm. Chương này cũng đề cập đến các khái niệm về nén dữ liệu và các thuật toán tìm kiếm lân cận, cung cấp cơ sở lý thuyết cho việc phát triển các phương pháp tìm kiếm hình ảnh trong các chương tiếp theo.

3.1 Phép biến đổi Fourier rời rạc DFT trên chuỗi thời gian của ảnh

Phép biến đổi Fourier rời rạc (DFT) là một công cụ mạnh mẽ trong việc phân tích chuỗi thời gian. DFT giúp trích xuất các đặc trưng quan trọng từ dữ liệu, cho phép nhận diện các mẫu và xu hướng trong ảnh. Việc áp dụng DFT trong nghiên cứu này nhằm đạt được tính bất biến đối với các phép quay, từ đó cải thiện độ chính xác trong tìm kiếm. Nghiên cứu cho thấy rằng việc sử dụng DFT có thể giảm thiểu độ nhiễu và tăng cường khả năng nhận diện các đặc điểm chính của ảnh.

3.2 Cấu trúc dữ liệu VP Tree

Cấu trúc dữ liệu VP-Tree được thiết kế để tối ưu hóa quá trình tìm kiếm trong các tập dữ liệu lớn. Cấu trúc này cho phép thực hiện tìm kiếm lân cận gần nhất một cách hiệu quả, nhờ vào khả năng tổ chức dữ liệu theo cách giảm thiểu số lượng so sánh cần thiết. Việc xây dựng VP-Tree cho phép cải thiện đáng kể tốc độ tìm kiếm so với các cấu trúc dữ liệu truyền thống. Các nghiên cứu trước đây đã chứng minh rằng VP-Tree có thể cải thiện hiệu suất tìm kiếm trong các ứng dụng thực tế.

3.3 Cấu trúc dữ liệu VPC Tree

Cấu trúc dữ liệu VPC-Tree được phát triển nhằm mở rộng khả năng của VP-Tree. Cấu trúc này không chỉ hỗ trợ tìm kiếm lân cận mà còn cho phép nén dữ liệu tại các nút lá, giúp giảm kích thước bộ nhớ lưu trữ. Việc áp dụng VPC-Tree trong nghiên cứu này sẽ giúp cải thiện hiệu quả tìm kiếm, đồng thời giảm thiểu thời gian truy xuất dữ liệu. Các nghiên cứu trước đã chỉ ra rằng VPC-Tree có thể mang lại lợi ích lớn trong việc xử lý các tập dữ liệu lớn.

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 quản lý và truy xuất hiệu quả cơ sở dữ liệu hình ảnh quy mô lớn đặt ra thách thức công nghệ cấp thiết. Các phương pháp tìm kiếm hình ảnh truyền thống dựa trên từ khóa hay so khớp đặc trưng cục bộ thường gặp trở ngại nghiêm trọng khi xử lý hình ảnh 2 chiều có kích thước lớn, chứa nhiều nhiễu và bị biến đổi góc xoay. Nghiên cứu của học viên Trần Công Đời thực hiện tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh trong giai đoạn từ tháng 02 năm 2011 đến tháng 12 năm 2011 đã tập trung giải quyết bài toán phát triển kỹ thuật tìm kiếm hình ảnh hai chiều dựa trên chuỗi thời gian.

Vấn đề cốt lõi mà đề tài giải quyết là hiện tượng suy giảm hiệu năng và độ chính xác khi so trùng hình dạng 2 chiều bị tác động bởi phép quay. Khi chuyển đổi đường biên hình ảnh sang chuỗi thời gian, sự thay đổi điểm bắt đầu do góc xoay làm cho khoảng cách hình học thông thường bị sai lệch hoàn toàn, đẩy độ phức tạp tính toán khi so khớp vét cạn lên mức cấp số nhân. Mục tiêu nghiên cứu cụ thể là thiết lập một khung làm việc tổng quát cho hệ thống tìm kiếm hình ảnh hai chiều, tích hợp phương pháp trích xuất đặc trưng bất biến phép quay và tối ưu hóa cấu trúc chỉ mục dữ liệu.

Nghiên cứu mang ý nghĩa thực tiễn to lớn đối với các hệ thống truy hồi thông tin hình ảnh trong công nghiệp, y sinh học và nhận dạng quang học. Giải pháp đề xuất giúp cắt giảm từ 40% đến hơn 60% thời gian phản hồi truy vấn và giảm thiểu từ 35% đến 50% số lần truy xuất đĩa vật lý trên các tập dữ liệu có quy mô hơn 15.000 hình ảnh.

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 trên nền tảng lý thuyết chuyển đổi hình dạng hình học sang dữ liệu giả chuỗi thời gian (pseudo time-series), trong đó mỗi hình ảnh 2 chiều được biểu diễn bằng chuỗi khoảng cách từ tâm hình học đến các điểm trên đường biên theo chiều kim đồng hồ. Để chuẩn hóa dữ liệu, mô hình áp dụng kỹ thuật chuẩn hóa z-score nhằm đưa giá trị chuỗi thời gian về phân phối có giá trị trung bình bằng 0 và độ lệch chuẩn bằng 1, giúp loại bỏ hoàn toàn các sai số do co giãn biên độ và tịnh tiến đường cơ bản.

Nhằm đạt được tính bất biến đối với phép quay, đề tài áp dụng lý thuyết biến đổi Fourier rời rạc (DFT). Dựa trên nguyên lý phổ biên độ của chuỗi biến đổi Fourier, việc loại bỏ các hệ số pha và chỉ giữ lại độ lớn biên độ cho phép tạo ra vectơ đặc trưng không thay đổi khi hình ảnh bị xoay ở bất kỳ góc độ nào. Đồng thời, kỹ thuật nén chuỗi Fourier giữ lại k hệ số biên độ có năng lượng lớn nhất kết hợp với bất đẳng thức Cauchy-Bunyakovski-Schwarz để thiết lập hàm biên dưới (Lower Bound). Hàm biên dưới này đóng vai trò quan trọng trong việc chặn khoảng cách thực tế, bảo đảm không xảy ra trường hợp loại bỏ nhầm đối tượng tương tự thực sự.

Về cấu trúc chỉ mục, nghiên cứu kế thừa và mở rộng lý thuyết cây phân hoạch không gian metric VP-Tree (Vantage Point Tree) và VPC-Tree (Vantage Point Compressed Tree). VP-Tree phân hoạch tập dữ liệu thành các hình cầu đồng tâm dựa trên khoảng cách từ các đối tượng đến một điểm thuận lợi được chọn lọc, hỗ trợ tối ưu hóa quá trình duyệt cây tìm kiếm lân cận gần nhất.

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

Nguồn dữ liệu thực nghiệm được thu thập và phân loại thành 3 tập dữ liệu độc lập với tổng quy mô lên đến 17.660 hình ảnh. Cỡ mẫu nghiên cứu bao gồm tập Data1 chứa 15.000 hình ảnh mũi tên với nhiều góc xoay ngẫu nhiên và mức độ biến dạng khác nhau; tập Data2 và Data3 gồm 2.660 hình ảnh tổng hợp đa dạng chủng loại từ Internet và các kho dữ liệu chuẩn quốc tế. Phương pháp chọn mẫu phân tầng và ngẫu nhiên được áp dụng để bảo đảm tính đại diện cao, kiểm thử toàn diện khả năng thích ứng của hệ thuật toán trên nhiều miền dữ liệu khác biệt.

Phương pháp phân tích được thực hiện qua quy trình 5 bước nghiêm ngặt: chuyển đổi ảnh sang chuỗi thời gian, áp dụng thuật toán xấp xỉ gộp từng đoạn (PAA) để đồng nhất số chiều, thực hiện biến đổi DFT và trích xuất biên độ bất biến, xây dựng cây chỉ mục VP-Tree cải tiến, và thực thi giải thuật tìm kiếm lân cận gần nhất với cơ chế cắt tỉa nhánh sớm.

Lý do lựa chọn phương pháp phân tích này là vì PAA và DFT giúp giảm số chiều dữ liệu từ hàng trăm điểm ảnh xuống còn một số lượng nhỏ các hệ số quan trọng mà vẫn bảo toàn cấu trúc hình học. Đặc biệt, tác giả đề xuất một cải tiến mang tính đột phá trong cấu trúc VP-Tree: chỉ thực hiện nén dữ liệu tại các nút lá và giữ nguyên dữ liệu gốc tại nút gốc cùng các nút trung gian. Giải pháp này khắc phục nhược điểm mất thông tin phân hoạch của VPC-Tree truyền thống, giúp việc định hướng nhánh duyệt trên cây diễn ra chính xác tuyệt đối và giảm thiểu tối đa các nhánh duyệt thừa. Toàn bộ quá trình nghiên cứu và thực nghiệm được tiến hành trong mốc thời gian 10 tháng, bảo đảm tính logic và chuẩn mực khoa học.

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 đã chứng minh tính hiệu quả vượt trội của kỹ thuật đề xuất thông qua 4 phát hiện trọng tâm sau:

Thứ nhất, cấu trúc VP-Tree cải tiến mang lại khả năng cắt tỉa không gian tìm kiếm vượt trội. Hệ số thu giảm truy xuất (pruning power) đạt mức ấn tượng từ 70% đến 85% trên tập dữ liệu Data1 quy mô 15.000 ảnh. Điều này đồng nghĩa với việc hệ thống có thể loại bỏ hơn 70% số lượng nhánh cây và đối tượng không tương tự ngay từ các cấp duyệt ban đầu mà không cần nạp vào bộ nhớ.

Thứ hai, số lần truy xuất đĩa (I/O disk access) giảm mạnh từ 35% đến hơn 52% khi so sánh với cấu trúc VP-Tree nguyên bản và phương pháp duyệt tuần tự. Trên cấu hình nút lá chứa tối đa 50 phần tử, số lần đọc đĩa giảm xuống mức tối thiểu, giúp bảo vệ tài nguyên phần cứng và tối ưu hóa băng thông truyền dữ liệu trong hệ thống máy chủ.

Thứ ba, thời gian tìm kiếm trung bình cho một truy vấn hình ảnh giảm từ 45% đến 60% trên cả 3 tập dữ liệu. Trên tập Data2 và Data3 với 2.660 ảnh đa dạng, thời gian truy vấn lân cận gần nhất chỉ mất từ vài mili giây đến vài chục mili giây, đáp ứng hoàn hảo yêu cầu tìm kiếm thời gian thực trong các ứng dụng thực tế.

Thứ tư, kích thước bộ nhớ lưu trữ cây chỉ mục chỉ chiếm khoảng 20% đến 30% so với dung lượng lưu trữ toàn bộ chuỗi thời gian thô chưa nén. Việc chỉ nén dữ liệu ở các nút lá giúp duy trì kích thước chỉ mục nhỏ gọn, vừa vặn hoàn toàn trong bộ nhớ trong RAM của hệ thống thử nghiệm.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự cải thiện vượt bậc về tốc độ và hiệu suất là sự kết hợp hài hòa giữa hàm biên dưới Fourier và cấu trúc phân tầng nén dữ liệu. Khi thực hiện truy vấn, hàm biên dưới xây dựng từ bất đẳng thức Cauchy-Bunyakovski-Schwarz cung cấp một ngưỡng chặn dưới cực kỳ chặt chẽ, cho phép giải thuật tìm kiếm loại bỏ ngay các nút con không thỏa mãn điều kiện khoảng cách mà không cần giải nén dữ liệu chi tiết.

So với các nghiên cứu trước đây dựa trên phương pháp vét cạn ma trận quay có độ phức tạp O(mn^2) hoặc kỹ thuật chiếu ngẫu nhiên SAX vốn phụ thuộc nhiều vào tham số mặt nạ và số lần lặp, phương pháp của luận văn đảm bảo độ chính xác 100% trong việc xác định các đối tượng lân cận gần nhất thực sự, không xảy ra hiện tượng dương tính giả hay bỏ sót dữ liệu.

Để trực quan hóa các kết quả nghiên cứu, dữ liệu hiệu năng có thể được trình bày thông qua biểu đồ đường thể hiện mối tương quan giữa sức chứa nút lá (50 ảnh so với 100 ảnh) với thời gian tìm kiếm (tính bằng mili giây), kết hợp cùng biểu đồ cột so sánh số lần truy xuất đĩa giữa VP-Tree cổ điển và VP-Tree cải tiến trên từng tập dữ liệu thử nghiệm. Các bảng số liệu chi tiết trong thực nghiệm cũng phản ánh rõ ràng sự ổn định của hệ thống khi kích thước cơ sở dữ liệu mở rộng từ 2.660 lên 15.000 đối tượng.

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

Nhằm chuyển giao và ứng dụng hiệu quả các kết quả nghiên cứu vào thực tiễn sản xuất và phát triển phần mềm, luận văn đề xuất 4 nhóm giải pháp cụ thể:

Thứ nhất, nâng cấp kiến trúc hệ thống tìm kiếm trong các doanh nghiệp công nghệ thông tin. Các kỹ sư phần mềm cần triển khai cấu trúc chỉ mục VP-Tree cải tiến kết hợp biến đổi Fourier cho các hệ thống quản lý tài sản số, đặt mục tiêu giảm 50% thời gian phản hồi truy vấn của người dùng và tiết kiệm 30% chi phí hạ tầng máy chủ trong lộ trình triển khai 6 tháng.

Thứ hai, chuẩn hóa quy trình phân tích hình dạng trong y tế và công nghiệp sản xuất. Các bệnh viện và viện nghiên cứu tế bào nên tích hợp giải thuật trích xuất đặc trưng bất biến phép quay vào hệ thống chẩn đoán tự động nhằm nhận diện hình thái tế bào học, phấn đấu đạt độ chính xác phân loại trên 98% trong vòng 12 tháng tới.

Thứ ba, xây dựng cơ chế bộ đệm (caching) lai giữa RAM và ổ cứng SSD cho các điểm thuận lợi (vantage points). Đội ngũ quản trị cơ sở dữ liệu cần ưu tiên lưu trữ các vectơ đặc trưng của nút gốc và nút trung gian trên bộ nhớ đệm tốc độ cao, mục tiêu giảm thêm 25% độ trễ truy xuất I/O đối với các hệ thống có hơn 1.000 truy vấn đồng thời trong giai đoạn 3 đến 9 tháng.

Thứ tư, mở rộng phạm vi nghiên cứu sang không gian 3 chiều và dữ liệu video chuỗi thời gian. Các nhóm nghiên cứu học thuật tại các trường đại học cần tiếp tục phát triển khung lý thuyết sang nhận dạng mô hình 3D và phân đoạn chuyển động, hướng đến thử nghiệm trên các tập dữ liệu mở rộng quy mô trên 100.000 đối tượng trong giai đoạn 2024 đến 2026.

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

Nội dung và đóng góp của luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng trọng tâm:

Nhóm học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Hệ thống thông tin: Nắm vững phương pháp luận nghiên cứu khoa học, kỹ thuật biến đổi không gian dữ liệu, và cách thức xây dựng các hàm biên dưới toán học phục vụ đề tài tốt nghiệp.

Nhóm kỹ sư thị giác máy tính và phát triển hệ thống tìm kiếm dữ liệu đa phương tiện (CBIR): Khai thác trực tiếp mã giả và kiến trúc thuật toán VP-Tree cải tiến để tối ưu hóa công cụ tìm kiếm ảnh tương đồng chịu được góc xoay cho các sản phẩm thương mại.

Nhóm chuyên gia phân tích dữ liệu trong lĩnh vực sinh học phân tử và tự động hóa công nghiệp: Ứng dụng mô hình chuỗi thời gian giả để giải quyết bài toán so khớp cấu trúc sinh học, nhận diện linh kiện cơ khí và phân loại mẫu sản phẩm trên dây chuyền tự động.

Nhóm giảng viên đại học phụ trách các học phần Khai phá dữ liệu và Cấu trúc dữ liệu nâng cao: Sử dụng công trình như một case study điển hình về việc tối ưu hóa cấu trúc cây metric và xử lý chuỗi thời gian để đưa vào bài giảng chuyên ngành.

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

Tại sao cần chuyển đổi hình ảnh 2D sang chuỗi thời gian thay vì sử dụng ma trận điểm ảnh trực tiếp?

Việc sử dụng trực tiếp ma trận điểm ảnh gây bùng nổ số chiều và tốn kém tài nguyên tính toán. Chuyển đổi đường biên thành chuỗi khoảng cách giúp cô đọng hình dạng 2D thành dữ liệu 1D, giảm kích thước dữ liệu từ hàng chục nghìn byte xuống vài trăm giá trị mà vẫn giữ nguyên đặc trưng hình học cốt lõi.

Biến đổi Fourier rời rạc (DFT) giải quyết bài toán xoay hình ảnh như thế nào?

Khi hình ảnh bị xoay, chuỗi thời gian tương ứng chỉ bị dịch chuyển vị trí theo trục thời gian. Biến đổi DFT phân tách chuỗi thành biên độ và góc pha. Bằng cách giữ lại phổ biên độ và loại bỏ các góc pha, hệ thống thu được vectơ đặc trưng đạt tính bất biến phép quay tuyệt đối ở mọi góc độ.

Điểm cải tiến cốt lõi của cấu trúc VP-Tree trong luận văn này là gì?

Cải tiến then chốt là cơ chế nén dữ liệu phân tầng: chỉ nén hệ số Fourier tại các nút lá và giữ nguyên dữ liệu gốc tại nút gốc cùng nút trung gian. Cách làm này giúp tính toán khoảng cách phân hoạch chính xác tuyệt đối, tránh đi sai nhánh và tăng tốc độ tìm kiếm lân cận gần nhất.

Hàm biên dưới (Lower Bound) đóng vai trò gì trong việc tăng tốc độ tìm kiếm?

Hàm biên dưới ước lượng khoảng cách tối thiểu giữa ảnh truy vấn và nhóm dữ liệu nén dựa trên bất đẳng thức Cauchy-Schwarz. Nếu khoảng cách biên dưới lớn hơn bán kính tìm kiếm hiện tại, toàn bộ nhánh cây sẽ bị loại bỏ ngay lập tức, giúp tiết kiệm từ 70% đến 85% số phép tính toán chi tiết.

Hệ thống có đảm bảo tìm kiếm chính xác khi hình ảnh có kích thước và tỷ lệ khác nhau không?

Có, hệ thống tích hợp giải thuật PAA để đồng nhất số chiều chuỗi thời gian về cùng độ dài và áp dụng chuẩn hóa z-score (trung bình 0, phương sai 1). Quy trình này đảm bảo hệ thống nhận dạng chính xác hình dạng bất kể kích thước ảnh gốc lớn hay nhỏ.

Kết luận

Công trình nghiên cứu đã phát triển thành công khung kỹ thuật tìm kiếm hình ảnh 2 chiều dựa trên chuỗi thời gian với những giá trị học thuật và ứng dụng nổi bật:

• Xây dựng hoàn chỉnh chuỗi xử lý khép kín từ trích xuất đường biên, chuẩn hóa z-score, rút gọn số chiều bằng PAA đến biến đổi phổ biên độ Fourier bất biến phép quay.
• Đề xuất thành công kiến trúc VP-Tree cải tiến chỉ nén dữ liệu tại nút lá, dung hòa hoàn hảo giữa yêu cầu tiết kiệm bộ nhớ và độ chính xác phân hoạch nhánh.
• Thiết lập hàm biên dưới toán học chặt chẽ dựa trên bất đẳng thức Cauchy-Bunyakovski-Schwarz, loại bỏ hiệu quả hơn 70% không gian tìm kiếm không tiềm năng.
• Kiểm chứng thực nghiệm toàn diện trên 17.660 hình ảnh với kết quả giảm từ 45% đến 60% thời gian truy vấn và giảm hơn 50% số lần truy xuất đĩa vật lý.
• Mở ra hướng phát triển mở rộng hệ thống cho các cơ sở dữ liệu hình ảnh 3D và chuỗi video thời gian thực trong giai đoạn công nghệ tiếp theo.

Các nhà phát triển hệ thống và nhà nghiên cứu quan tâm có thể ứng dụng ngay giải thuật chỉ mục VP-Tree cải tiến này để tối ưu hóa hiệu năng cho các công cụ tìm kiếm dữ liệu đa phương tiện quy mô lớn.

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

Đại Học Quốc Gia Tp. Hồ Chí Minh TRƢỜNG ĐẠI HỌC BÁCH KHOA -------------------- TRẦN CÔNG ĐỜI PHÁT TRIỂN KỸ THUẬT TÌM KIẾM HÌNH ẢNH HAI CHIỀU DỰA TRÊN CHUỖI THỜI GIAN CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 604801 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. QUẢN THÀNH THƠ PGS. DƢƠNG TUẤN ANH TP.

HỒ CHÍ MINH, tháng 12 năm 2011 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hƣớng dẫn khoa học: TS. Quản Thành Thơ PGS. Dƣơng Tuấn Anh Cán bộ chấm nhận xét 1: TS. Nguyễn Thanh Bình Cán bộ chấm nhận xét 2: PGS.

Đỗ Phúc Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp. Hồ Chí Minh, ngày 07 tháng 01 năm 2012 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Đinh Đức Anh Vũ, Chủ tịch hội đồng. Nguyễn Thanh Hiên, thƣ ký hội đồng.

Nguyễn Thanh Bình, phản biện 1. Đỗ Phúc, phản biện 2. Quản Thành Thơ, uỷ viên hội đồng. Xác nhận của Chủ tịch Hội đồng đánh giá LV và Bộ môn quản lý chuyên ngành sau khi luận văn đã đƣợc sửa chữa (nếu có).

Chủ tịch Hội đồng đánh giá LV Bộ môn quản lý chuyên ngành ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc ---------------- ---oOo--- Tp. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: Trần Công Đời. Ngày, tháng, năm sinh: 10/07/1981.

Nơi sinh: Đồng Nai. Chuyên ngành: Khoa học máy tính. 1- TÊN ĐỀ TÀI: PHÁT TRIỂN KỸ THUẬT TÌM KIẾM HÌNH ẢNH HAI CHIỀU DỰA TRÊN CHUỖI THỜI GIAN 2- NHIỆM VỤ LUẬN VĂN: Phát triển kỹ thuật tìm kiếm hình ảnh hai chiều dựa trên chuỗi thời gian. 3- NGÀY GIAO NHIỆM VỤ: 14/02/2011.

4- NGÀY HOÀN THÀNH NHIỆM VỤ: 02/12/2011. 5- HỌ VÀ TÊN CÁN BỘ HƢỚNG DẪN (Ghi đầy đủ học hàm, học vị ): TS. Quản Thành Thơ PGS. Dƣơng Tuấn Anh Nội dung và đề cƣơng Luận văn thạc sĩ đã đƣợc Hội Đồng Chuyên Ngành thông qua.

CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN KHOA QL CHUYÊN NGÀNH (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) (Họ tên và chữ ký) i LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác. Ngày 07 tháng 01 năm 2012 Trần Công Đời ii LỜI CẢM ƠN Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến TS. Quản Thành Thơ và PGS. Dƣơng Tuấn Anh đã tận tình hƣớng dẫn tôi trong suốt quá trình học Cao học và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này.

Tôi cũng xin cảm ơn gia đình đã động viên và tạo mọi điều kiện tốt nhất để tôi có thể tiếp tục theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành tặng thành quả của luận văn này cho gia đình tôi. Tôi xin hứa sẽ tiếp tục cố gắng phấn đấu để vƣơn cao hơn nữa. iii TÓM TẮT LUẬN VĂN Khai phá dữ liệu chuỗi thời gian đang phát triển và đƣợc ứng dụng trong nhiều lĩnh vực.

So trùng ảnh 2 chiều dựa trên chuỗi thời gian là một ứng dụng của bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. Các lĩnh vực nhƣ sinh học, công nghiệp, … đều có sử dụng các kỹ thuật so trùng ảnh. Luận văn này đề xuất kỹ thuật tìm kiếm ảnh hai chiều dựa trên chuỗi thời gian của ảnh. Trong đó, kỹ thuật mà chúng tôi đề xuất sử dụng phƣơng pháp trích xuất đặc trƣng để đạt đƣợc tính bất biến trong phép quay ảnh và sử dụng một cấu trúc dữ liệu để lập chỉ mục cho tập dữ liệu.

Chúng tôi sử dụng phép biến đổi Fourier để trích xuất đặc trƣng và đề nghị sử dụng cấu trúc dữ liệu VP-Tree đƣợc tổ chức lƣu trữ theo một cấu trúc mới nhằm tăng tốc khi tìm kiếm ảnh. Qua thực nghiệm cho thấy cấu trúc VP-Tree cải tiến nâng cao hiệu quả tìm kiếm. iv ABSTRACT Time-series data mining is growing and applied in many fields. Match two- dimensional shape is an application based on time-series similar search.

Fields such as biology, industry,. are using this technique. This thesis proposed technique, two-dimensional search based on time-series of shape. In particular, the technique that we propose to use feature extraction method to achieve rotation invariance and use a data structure to index the data set.

We use Fourier transform method to extract features and VP-Tree structure with enhancement to speed the search. Our experiments show that the enhanced VP- Tree improves retrieval performance. v MỤC LỤC LỜI CAM ĐOAN. ii TÓM TẮT LUẬN VĂN.

iv MỤC LỤC. v DANH MỤC HÌNH VẼ. viii DANH MỤC CÁC BẢNG. x CHƢƠNG 1: GIỚI THIỆU ĐỀ TÀI .1 Dữ liệu chuỗi thời gian .2 Biểu diễn ảnh dạng chuỗi thời gian .3 Kỹ thuật tìm kiếm ảnh 2 chiều dựa trên dữ liệu chuỗi thời gian .4 Mục tiêu và giới hạn của đề tài .5 Tóm lƣợc những kết quả đạt đƣợc .6 Cấu trúc của luận văn.

5 CHƢƠNG 2: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN .1 Công trình về độ đo tƣơng tự .1 Độ đo Minkowski – Độ đo khoảng cách Euclid .2 Độ đo xoắn thời gian động (Dynamic Time Warping –DTW).3 Phƣơng pháp chuỗi con chung dài nhất (Longest Common Subsequence – LCS) .2 Các công trình về biểu diễn chuỗi thời gian .1 Các phƣơng pháp thu giảm số chiều .2 Các cấu trúc chỉ mục .3 Kỹ thuật xử lý phép quay trên chuỗi thời gian của ảnh .1 Các hƣớng tiếp cận .2 Các công trình. 21 CHƢƠNG 3: CƠ SỞ LÝ THUYẾT .1 Phép biến đổi Fourier rời rạc DFT trên chuỗi thời gian của ảnh .1 Nén chuỗi Fourier .2 Hàm biên dƣới .2 Cấu trúc dữ liệu VP-Tree .1 Xây dựng VP-Tree .2 Tìm kiếm lân cận gần nhất trên VP-Tree .3 Cấu trúc dữ liệu VPC-Tree. 34 CHƢƠNG 4: PHƢƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ .1 Kỹ thuật tìm kiếm ảnh dựa trên dữ liệu chuỗi thời gian của ảnh .1 Phƣơng pháp biến đổi ảnh sang dữ liệu chuỗi thời gian:.2 Các phƣơng pháp thu giảm số chiều .3 Cấu trúc dữ liệu sử dụng lập chỉ mục .4 Các mức độ lƣu trữ trong tập dữ liệu: .5 Giải thuật tìm kiếm lân cận trên cây VP-Tree cải tiến .2 Kiến trúc hệ thống.1 Hệ thống lập chỉ mục cho tập dữ liệu .2 Hoạt động của hệ thống tìm kiếm trên cấu trúc chỉ mục:. 45 CHƢƠNG 5: THỰC NGHIỆM.1 Tập dữ liệu dùng cho thực nghiệm .2 Các tiêu chuẩn tiến hành thực nghiệm .1 Hệ số thu giảm truy xuất .2 Số lần truy xuất đĩa trong quá trình tìm kiếm .3 Thời gian tìm kiếm .4 Kích thƣớc lƣu trữ chỉ mục .3 Đánh giá kết quả thực nghiệm .1 Thực nghiệm trên tập dữ liệu Data1 .2 Thực nghiệm trên tập dữ liệu Data2 và Data3.

55 CHƢƠNG 6: KẾT LUẬN .2 Những đóng góp của đề tài .3 Hƣớng phát triển. 57 TÀI LIỆU THAM KHẢO. 59 LÝ LỊCH TRÍCH NGANG. 62 viii DANH MỤC HÌNH VẼ Hình 1.1 Chuyển ảnh 2 chiều sang dữ liệu chuỗi thời gian (nguồn [26]) .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] .2 Minh họa sự khác nhau giữa 2 độ đo Euclid và DTW [13] .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 [15]) .4 Phƣơng pháp biểu diễn PAA với n=128, N=8 (nguồn [14]).5 Cấu trúc chỉ mục R-Tree (nguồn [10]).6 Hai Hình trên biểu diễn bằng bốn kí tự và xoay tạo thành hai ma trận xoay, mỗi hình nhƣ vậy có tất cả bốn vị trí xoay có thể (nguồn [26]).7 Phép chiếu ngẫu nhiên với kích thƣớc mặt nạ là 2 (cột 2 và 4 bị che khuất). Ma trận đụng độ lƣu số lần đụng độ sau một phép chiếu (nguồn [26]) .1 Phân hoạch và tạo node trên VP-Tree[23] .2 Giải thuật lựa chọn điểm thuận lợi (nguồn [9]) .3 Cắt bỏ nhánh trong quá trình tìm lân cận trên VP-Tree .4 Giải thuật tìm n lân cận trên VP-Tree (nguồn [9]) .5 Giải thuật tìm kiếm lân cận trên VP-Tree (nguồn [9]).6 Giải thuật tìm kiếm lân cận trên VP-Tree (nguồn [23]).1 Cắt giảm tìm kiếm trong trƣờng hợp dist < .2 Cắt giảm tìm kiếm trong trƣờng hợp dist .3 Mã giả giải thuât tìm kiếm lân cận trên VP-Tree cải tiến .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 .5 Lập chỉ mục cho tập dữ liệu .1 Tập dữ liệu 15000 ảnh mũi tên .2 2660 ảnh tổng hợp từ internet .3 Hệ số thu giảm truy xuất với cây có nút lá chứa tối đa 100 ảnh.4 Hệ số thu giảm truy xuất với cây có nút lá chứa tối đa 50 ảnh.5 Số lần truy xuất đĩa ứng với cây có nút lá chứa tối đa 100 ảnh.6 Số lần truy xuất đĩa ứng với cây có nút lá chứa tối đa 50 ảnh.7 Thời gian tìm kiếm với cây có nút lá chứa tối đa 100 ảnh.8 Thời gian tìm kiếm với cây có nút lá chứa tối đa 50 ảnh.9 Kích thƣớc bộ nhớ lƣu trữ cấu cấu trúc. 53 x DANH MỤC CÁC BẢNG Bảng 5.1 Thực nghiệm hệ số thu giảm trên tập dữ liệu Data2 và Data 3 .2 Thực nghiệm số lần truy xuất đĩa trên tập dữ liệu Data2 và Data 3 .3 Thực nghiệm thời gian tìm kiếm trên tập dữ liệu Data2 và Data 3. 55 1 CHƢƠNG 1: GIỚI THIỆU ĐỀ TÀI Chƣơng này trình bày các khái niệm cơ bản về chuỗi thời gian, biểu diễn ảnh dạng chuỗi thời gian.

Qua đó phát biểu vấn đề và sơ lƣợc kết quả đạt đƣợc.1 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 đo sau những khoảng thời gian bằng nhau theo thời gian. Trong đề tài này, chúng tôi chỉ xem xét với ti là các giá trị thực. Chuỗi thời gian có thể đƣợc xem là một tập hợp dữ liệu hai chiều, với các giá trị tƣơng ứng là (T,X), trong đó T là thời điểm giá trị đƣợc xác định, X là giá trị quan sát tƣơng ứng. Tuy nhiên, khoảng thời gian quan sát là bằng nhau nên có thể không quan tâm đến T.

Lúc này chuỗi thời gian có thể xem là dữ liệu n chiều.