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

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.

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.