Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí trong khoa học máy tính

Luận văn thạc sĩ kỹ thuật nghiên cứu máy tính nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải

• Tác giả: Hoàng Việt Hùng
• Người hướng dẫn: PGS. TS Thoại Nam
• Trường học: Đại học Quốc gia TP.HCM Trường Đại học Bách Khoa
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên Cứu Và Xây Dựng Hệ Thống Tìm Kiếm Ảnh Dựa Trên Thuộc Tính Vị Trí
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Nội dung đề tài
• 1.3. Phương pháp giải quyết vấn đề
• 1.4. Tóm tắt các giải pháp và kết quả đạt được của đề tài
• 2. CHƯƠNG 2: KIẾN TRÚC MÔ HÌNH LBIS
• 2.1. Bài toán tìm kiếm hình ảnh tương tự dựa trên thuộc tính vị trí
• 2.2. Mô hình hệ thống LBIS
• 2.3. Giải pháp tối ưu hoá việc tìm kiếm hình ảnh trên mô hình hệ thống LBIS
• 2.4. Nâng cấp giải pháp tối ưu hoá việc tìm kiếm hình ảnh trên mô hình LBIS
• 3. CHƯƠNG 3: HIỆN THỰC MÔ HÌNH LBIS
• 3.1. Chọn hệ thống file system cho LBIS Store
• 3.2. Hiện thực hàm Locality Sensitive Hashing
• 3.3. Hiện thực hệ thống LBIS
• 3.4. Đánh giá hệ thống LBIS
• 4. CHƯƠNG 4: TỔNG KẾT VÀ ĐÁNH GIÁ
• 4.1. Các kết quả đạt được
• 4.2. Những hạn chế của đề tài
• 4.3. Hướng mở rộng khắc phục
• TÀI LIỆU THAM KHẢO
• PHẦN LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng quan về đề tài

Đề tài nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí (Location-Based Image Searching System - LBIS) nhằm đáp ứng nhu cầu ngày càng tăng về việc tìm kiếm hình ảnh tương đồng về địa điểm trên các mạng xã hội. Hệ thống này không chỉ giúp người dùng tìm kiếm hình ảnh mà còn cung cấp thông tin hữu ích từ các bức ảnh đã được chia sẻ. Việc sử dụng các giải thuật tìm kiếm thông minh và phức tạp là cần thiết để xử lý khối lượng dữ liệu khổng lồ, lên đến hàng trăm tỉ hình ảnh. Mô hình LBIS được thiết kế để tối ưu hóa quá trình tìm kiếm bằng cách nhóm thông tin metadata của các hình ảnh có điểm tương đồng về vị trí, từ đó sử dụng Locality Sensitive Hashing để tăng tốc độ tìm kiếm.

1.1. Giới thiệu về hệ thống tìm kiếm ảnh

Hệ thống tìm kiếm ảnh hiện nay chủ yếu dựa vào nội dung hình ảnh mà ít chú trọng đến thuộc tính vị trí. Tuy nhiên, thông tin về vị trí chụp ảnh có thể được tối ưu hóa để cải thiện tốc độ và độ chính xác của việc tìm kiếm. Đề tài này sẽ tập trung vào việc phát triển một hệ thống có khả năng tìm kiếm hình ảnh dựa trên thuộc tính vị trí, giúp người dùng dễ dàng tìm kiếm và nhận thông tin cần thiết từ các bức ảnh tương tự.

II. Nội dung đề tài

Đề tài sẽ giải quyết hai bài toán chính: xây dựng mô hình hệ thống LBIS kết nối với mạng xã hội và tối ưu hóa việc tìm kiếm hình ảnh dựa trên thuộc tính vị trí. Các thách thức lớn bao gồm việc xử lý khối lượng dữ liệu lớn từ các mạng xã hội, đảm bảo thời gian phản hồi nhanh chóng cho người dùng và đạt được độ chính xác cao trong kết quả tìm kiếm. Hệ thống LBIS sẽ được thiết kế để tổ chức và sắp xếp dữ liệu hình ảnh theo vị trí, từ đó cung cấp kết quả tìm kiếm nhanh chóng và hiệu quả.

2.1. Các thách thức trong việc xây dựng hệ thống

Một trong những thách thức lớn nhất là khối lượng dữ liệu khổng lồ mà các mạng xã hội hiện nay lưu trữ. Ví dụ, Facebook hiện có khoảng 260 tỉ hình ảnh. Việc tìm kiếm hình ảnh tương tự dựa trên thuộc tính vị trí cần phải được thực hiện trong thời gian thực, điều này đòi hỏi hệ thống phải có khả năng xử lý nhanh chóng và hiệu quả. Hệ thống cũng cần phải đảm bảo rằng người dùng có thể nhận được kết quả chính xác và hữu ích từ các truy vấn của họ.

III. Phương pháp giải quyết vấn đề

Để giải quyết các bài toán đã đặt ra, đề tài sẽ khảo sát và đánh giá các giải pháp hiện có, đồng thời phát triển một mô hình LBIS đơn giản có khả năng kết nối với hệ thống Haystack của Facebook. Việc sử dụng Locality Sensitive Hashing sẽ giúp tối ưu hóa quá trình tìm kiếm hình ảnh dựa trên thuộc tính vị trí. Hệ thống sẽ được thử nghiệm để đảm bảo tính khả thi và hiệu quả trong việc tìm kiếm.

3.1. Xây dựng mô hình LBIS

Mô hình LBIS sẽ được xây dựng dựa trên việc kết nối với hệ thống Haystack của Facebook. Hệ thống này sẽ chỉ lưu trữ các thông tin cần thiết như photoid và vị trí của hình ảnh, từ đó giảm thiểu khối lượng dữ liệu cần xử lý. Việc phân hoạch dữ liệu theo vị trí không gian sẽ giúp quản lý và tìm kiếm hình ảnh một cách hiệu quả hơn.

IV. Kết quả đạt được

Kết quả của đề tài cho thấy mô hình LBIS có khả năng kết nối với mạng xã hội và cung cấp tính năng tìm kiếm hình ảnh dựa trên thuộc tính vị trí. Mô hình này đã được thử nghiệm và cho thấy tính khả thi trong việc tìm kiếm nhanh chóng và chính xác. Đề tài đã đưa ra hai giải pháp chính để giải quyết các bài toán con, từ đó tạo ra một hệ thống có thể đáp ứng nhu cầu của người dùng một cách hiệu quả.

4.1. Đánh giá hệ thống LBIS

Hệ thống LBIS đã được đánh giá dựa trên khả năng tìm kiếm và tốc độ phản hồi. Kết quả cho thấy rằng việc sử dụng Locality Sensitive Hashing đã giúp cải thiện đáng kể tốc độ tìm kiếm hình ảnh. Hệ thống cũng đã chứng minh được tính khả thi trong việc kết nối với các mạng xã hội hiện có, từ đó mở ra nhiều cơ hội ứng dụng trong thực tế.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh mạng xã hội phát triển mạnh mẽ, nhu cầu tìm kiếm hình ảnh dựa trên thuộc tính vị trí ngày càng tăng cao. Hiện nay, các mạng xã hội như Facebook đang lưu trữ khoảng 260 tỷ hình ảnh, với lượng ảnh mới được tải lên mỗi tuần lên đến khoảng 1 tỷ, tương đương 60 terabytes dữ liệu. Việc tìm kiếm hình ảnh tương tự dựa trên vị trí chụp ảnh không chỉ giúp người dùng nhanh chóng tiếp cận thông tin liên quan mà còn hỗ trợ các ứng dụng trong đời sống như đánh giá địa điểm, lựa chọn điểm đến du lịch. Tuy nhiên, các hệ thống hiện tại chủ yếu tập trung vào tìm kiếm dựa trên nội dung hình ảnh mà chưa khai thác hiệu quả các thuộc tính vị trí, dẫn đến chi phí xử lý cao và thời gian phản hồi chậm.

Mục tiêu nghiên cứu là xây dựng một hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí (Location-Based Image Searching System - LBIS) có khả năng kết nối với các mạng xã hội hiện có, tối ưu hóa việc lưu trữ và truy vấn dữ liệu vị trí nhằm đáp ứng yêu cầu tìm kiếm nhanh và chính xác trong môi trường dữ liệu lớn. Phạm vi nghiên cứu tập trung vào việc thiết kế mô hình hệ thống LBIS, khảo sát và áp dụng các giải thuật tìm kiếm không gian phù hợp, đồng thời thực hiện thử nghiệm trên mô hình dữ liệu giả lập tương ứng với quy mô thực tế của mạng xã hội Facebook.

Ý nghĩa của nghiên cứu thể hiện qua việc giảm thiểu chi phí lưu trữ và tăng tốc độ truy vấn hình ảnh dựa trên vị trí, góp phần nâng cao trải nghiệm người dùng trên các nền tảng mạng xã hội, đồng thời mở ra hướng phát triển các ứng dụng thông minh dựa trên dữ liệu vị trí trong lĩnh vực khoa học máy tính và công nghệ thông tin.

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 dựa trên các lý thuyết và mô hình sau:

• Hệ thống lưu trữ Haystack của Facebook: Là hệ thống lưu trữ hình ảnh quy mô lớn, quản lý khoảng 260 tỷ ảnh với kiến trúc phân tán gồm ba thành phần chính: Haystack Store, Haystack Directory và Haystack Cache. Haystack tối ưu hóa việc truy xuất dữ liệu bằng cách giảm thao tác trên đĩa và sử dụng bộ nhớ chính để lưu trữ metadata.

• Giải thuật Locality Sensitive Hashing (LSH): Là phương pháp hashing đặc biệt giúp nhóm các điểm dữ liệu gần nhau về mặt không gian vào cùng một bucket hoặc các bucket gần nhau, từ đó tăng tốc độ tìm kiếm gần đúng trong không gian đa chiều.

• Cấu trúc dữ liệu cây phân vùng không gian (Quad Tree, K-D Tree): Các cấu trúc này giúp phân vùng dữ liệu không gian thành các vùng con để giảm phạm vi tìm kiếm, nâng cao hiệu quả truy vấn.

• Hệ thống file XFS: Hệ thống file journaling có khả năng quản lý file lớn, hỗ trợ đa luồng và phục hồi nhanh khi sự cố, phù hợp cho việc lưu trữ và truy xuất dữ liệu lớn trong LBIS.

Các khái niệm chính bao gồm: metadata hình ảnh (PhotoID, vị trí GPS), phân hoạch không gian dựa trên kinh độ và vĩ độ, bảng ma trận không gian, và chỉ mục hash LSH.

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

• Nguồn dữ liệu: Sử dụng dữ liệu giả lập gồm PhotoID và vị trí GPS, mô phỏng quy mô dữ liệu thực tế của mạng xã hội Facebook với khoảng 260 tỷ ảnh, tương đương 3.8 terabytes dữ liệu metadata.

• Phương pháp phân tích: Thiết kế mô hình hệ thống LBIS gồm ba thành phần chính: LBIS WebService (giao tiếp với mạng xã hội), LBIS Directory (phân hoạch không gian và mapping file lưu trữ), LBIS Store (lưu trữ và tìm kiếm dữ liệu). Áp dụng giải thuật Locality Sensitive Hashing để đánh chỉ mục và tối ưu hóa tìm kiếm trong các file lưu trữ.

• Timeline nghiên cứu: Nghiên cứu và khảo sát hệ thống Haystack và các giải thuật tìm kiếm không gian trong 2 tháng đầu; thiết kế mô hình LBIS và xây dựng giải pháp tối ưu trong 3 tháng tiếp theo; hiện thực và thử nghiệm mô hình trong 2 tháng cuối.

• Cỡ mẫu và chọn mẫu: Mô phỏng dữ liệu với kích thước tương đương 6 triệu ảnh cho thử nghiệm hiệu năng, mở rộng quy mô 260 tỷ ảnh để đánh giá khả năng mở rộng của hệ thống.

• Lý do lựa chọn phương pháp: LSH được chọn vì khả năng giảm đáng kể thời gian tìm kiếm so với phương pháp tìm kiếm tuần tự, đồng thời phù hợp với đặc thù dữ liệu vị trí có tính phân bố không đồng đều. Hệ thống file XFS được chọn để đảm bảo hiệu suất và độ ổn định khi xử lý lượng lớn file lưu trữ.

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

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

1. Hiệu quả phân hoạch không gian: Việc chia không gian trái đất thành 38.000 vùng dựa trên kinh độ và vĩ độ giúp giảm đáng kể phạm vi tìm kiếm. Thời gian tìm kiếm trên tập dữ liệu 6 triệu ảnh giảm từ khoảng 30.000 ms xuống còn dưới 20 ms, tương đương giảm hơn 99% thời gian.

2. Tối ưu hóa tìm kiếm bằng LSH: Áp dụng Locality Sensitive Hashing giúp chuyển bài toán tìm kiếm gần đúng thành tìm kiếm chính xác trong các bucket hash, giảm thời gian tìm kiếm trong file từ hàng nghìn ms xuống còn vài chục ms. Ví dụ, với 1.000 ảnh, thời gian tìm kiếm giảm từ 5.000 ms xuống còn 12 ms.

3. Sắp xếp dữ liệu theo thứ tự vị trí: Việc lưu trữ dữ liệu theo thứ tự khoảng cách đến tâm vùng không gian giúp giảm chi phí tìm kiếm tuần tự, đồng thời kết hợp với LSH để xác định vị trí bắt đầu tìm kiếm trong file, giảm thiểu số block cần load.

4. Khả năng mở rộng và ổn định của hệ thống: Mô hình LBIS với kiến trúc phân tán, sử dụng hệ thống file XFS và các máy Store Machine có dung lượng 500 GB, có thể mở rộng để xử lý dữ liệu lên đến 3.8 TB metadata tương ứng với 260 tỷ ảnh. Việc nạp sẵn file index vào bộ nhớ chính giúp giảm thời gian truy vấn và tăng khả năng đáp ứng thời gian thực.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu suất là do mô hình LBIS tận dụng hiệu quả phân hoạch không gian và giải thuật LSH để giảm phạm vi tìm kiếm và số lượng dữ liệu cần xử lý trong mỗi truy vấn. So với các nghiên cứu trước đây tập trung vào tìm kiếm dựa trên nội dung ảnh, việc khai thác thuộc tính vị trí giúp giảm đáng kể chi phí tính toán và tăng tốc độ phản hồi.

Kết quả thử nghiệm trên mô hình dữ liệu giả lập cho thấy thời gian tìm kiếm giảm từ hàng chục giây xuống còn vài chục mili giây, phù hợp với yêu cầu truy vấn thời gian thực trên mạng xã hội. Việc sử dụng hệ thống file XFS cũng đảm bảo tính ổn định và khả năng phục hồi khi có sự cố, điều này rất quan trọng trong môi trường lưu trữ dữ liệu lớn.

Tuy nhiên, hệ thống vẫn tồn tại một số hạn chế như khả năng xử lý đồng thời nhiều truy vấn chưa được tối ưu hoàn toàn, và độ chính xác của LSH có thể bị ảnh hưởng bởi các trường hợp ngoại lệ trong hashing. Các giải pháp nâng cao như chạy nhiều hàm hash song song và lọc kết quả sau khi truy vấn được đề xuất để khắc phục.

Dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian tìm kiếm giữa phương pháp truyền thống và mô hình LBIS, cũng như bảng thống kê chi tiết thời gian từng bước trong quá trình tìm kiếm.

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

1. Triển khai hệ thống LBIS tích hợp với mạng xã hội: Thực hiện kết nối hệ thống LBIS với các nền tảng mạng xã hội lớn như Facebook để cung cấp tính năng tìm kiếm ảnh dựa trên vị trí, nhằm nâng cao trải nghiệm người dùng. Thời gian thực hiện dự kiến 6-12 tháng, do các nhóm phát triển mạng xã hội phối hợp.

2. Mở rộng quy mô và tối ưu xử lý đồng thời: Nâng cấp hệ thống để hỗ trợ xử lý đồng thời nhiều truy vấn, sử dụng các kỹ thuật cân bằng tải và phân tán dữ liệu hiệu quả. Mục tiêu giảm thiểu hiện tượng bottleneck, đảm bảo thời gian phản hồi dưới 100 ms cho mỗi truy vấn. Thời gian thực hiện 12 tháng, do đội ngũ kỹ thuật hệ thống đảm nhận.

3. Cải tiến thuật toán LSH và lọc kết quả: Áp dụng đa hàm hash song song và thuật toán lọc kết quả để tăng độ chính xác tìm kiếm, giảm thiểu sai số do hashing. Mục tiêu nâng cao độ chính xác trên 95% trong các thử nghiệm thực tế. Thời gian thực hiện 6 tháng, do nhóm nghiên cứu thuật toán đảm nhiệm.

4. Phát triển giao diện người dùng thân thiện: Thiết kế giao diện tìm kiếm ảnh dựa trên vị trí dễ sử dụng trên các thiết bị di động, tích hợp các tính năng bổ sung như xem bình luận, đánh giá địa điểm. Mục tiêu tăng tỷ lệ sử dụng tính năng trên 30% người dùng mạng xã hội trong 1 năm. Thời gian thực hiện 4-6 tháng, do nhóm phát triển ứng dụng đảm nhận.

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

1. Nhà phát triển hệ thống mạng xã hội: Có thể ứng dụng mô hình LBIS để tích hợp tính năng tìm kiếm ảnh dựa trên vị trí, nâng cao trải nghiệm người dùng và tăng tính cạnh tranh của nền tảng.

2. Nhà nghiên cứu khoa học máy tính và công nghệ thông tin: Tham khảo các giải thuật tìm kiếm không gian, kiến trúc hệ thống lưu trữ dữ liệu lớn, và ứng dụng LSH trong thực tế.

3. Chuyên gia phát triển ứng dụng di động: Áp dụng mô hình tìm kiếm ảnh vị trí để phát triển các ứng dụng du lịch, đánh giá địa điểm, hoặc các dịch vụ dựa trên vị trí người dùng.

4. Quản lý dữ liệu và kỹ sư hệ thống lưu trữ: Nghiên cứu cách tổ chức dữ liệu lớn hiệu quả, lựa chọn hệ thống file phù hợp và tối ưu hóa truy vấn trong môi trường phân tán.

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

1. LBIS khác gì so với các hệ thống tìm kiếm ảnh truyền thống?
   LBIS tập trung vào tìm kiếm dựa trên thuộc tính vị trí GPS của ảnh, trong khi các hệ thống truyền thống chủ yếu dựa trên nội dung hình ảnh hoặc từ khóa. Điều này giúp tăng tốc độ tìm kiếm và giảm chi phí xử lý trên dữ liệu lớn.

2. Giải thuật Locality Sensitive Hashing hoạt động như thế nào trong LBIS?
   LSH nhóm các điểm dữ liệu gần nhau về mặt không gian vào cùng một bucket hash, giúp chuyển bài toán tìm kiếm gần đúng thành tìm kiếm chính xác trong bucket, giảm đáng kể thời gian tìm kiếm.

3. Hệ thống LBIS có thể xử lý bao nhiêu truy vấn đồng thời?
   Phiên bản hiện tại hỗ trợ xử lý truy vấn không đồng thời, tuy nhiên có kế hoạch nâng cấp để xử lý đồng thời nhiều truy vấn với thời gian phản hồi dưới 100 ms.

4. LBIS có thể áp dụng cho các mạng xã hội khác ngoài Facebook không?
   Có thể, vì LBIS được thiết kế như một hệ thống con có khả năng kết nối với các mạng xã hội khác nhau, miễn là các mạng xã hội đó cung cấp dữ liệu metadata ảnh gồm PhotoID và vị trí GPS.

5. Độ chính xác của tìm kiếm vị trí trong LBIS có đảm bảo không?
   Độ chính xác cao nhờ sử dụng LSH và các bước lọc kết quả sau truy vấn. Mặc dù có thể có sai số nhỏ do đặc tính hashing, nhưng xác suất sai lệch là rất thấp và có thể cải thiện bằng cách chạy nhiều hàm hash song song.

Kết luận

• Đã xây dựng thành công mô hình hệ thống LBIS cho phép tìm kiếm hình ảnh dựa trên thuộc tính vị trí, kết nối hiệu quả với hệ thống mạng xã hội Facebook.
• Áp dụng giải thuật Locality Sensitive Hashing giúp tối ưu hóa thời gian tìm kiếm, giảm từ hàng chục giây xuống còn vài chục mili giây trên tập dữ liệu lớn.
• Mô hình phân hoạch không gian và tổ chức lưu trữ dữ liệu theo vùng giúp quản lý hiệu quả 3.8 terabytes metadata tương ứng với 260 tỷ ảnh.
• Hệ thống sử dụng XFS file system đảm bảo tính ổn định, khả năng phục hồi và hiệu suất cao trong môi trường lưu trữ phân tán.
• Các bước tiếp theo bao gồm nâng cấp khả năng xử lý đồng thời, cải tiến thuật toán tìm kiếm và phát triển giao diện người dùng thân thiện để ứng dụng rộng rãi trong thực tế.

Hành động ngay: Các nhà phát triển và nhà nghiên cứu được khuyến khích áp dụng mô hình LBIS để nâng cao hiệu quả tìm kiếm ảnh vị trí trên mạng xã hội, đồng thời tiếp tục nghiên cứu mở rộng và hoàn thiện hệ thống.

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

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA HOÀNG VIỆT HÙNG NGHIÊN CỨU VÀ XÂY DỰNG HỆ THONG TÌM KIEM ANH DUA TREN THUOC TÍNH VỊ TRÍ Chuyén nganh: KHOA HOC MAY TINH Mã số : 60. HỎ CHÍ MINH, tháng 11 năm 2013 Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang | CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRUONG ĐẠI HOC BACH KHOA —DHQG -HCM Cán bộ hướng dẫn khoa học : PGS. TS Thoại Nam Cán bộ chấm nhận xét 1 :.- te E SE SE E9EE+EE#EESEESEEEEESEEsEEsErsereersez Cán bộ chấm nhận xét 2 :.-- tt SE SE S98 E98E9EE£EESEESEESEESEESEEsEEsereerses Luan văn thạc sĩ được bảo vệ tai Trường Dai hoc Bách Khoa, DHQG Tp. Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa 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 TRƯỞNG KHOA. Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 2 ĐẠI HỌC QUOC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM ` , Độc lập - Tự do - Hanh phúc TRƯƠNG ĐẠI HỌC BÁCH KHOA NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Hoàng Việt Hùng. Ngày, thang, năm sinh: 01/12/298ã.- Nơi sinh: Đồng Nai. Chuyên ngành: Khoa học máy tính.

TÊN DE TÀI: NGHIÊN CỨU VÀ XÂY DỰNG HE THONG TÌM KIEM ANH DỰA TREN THUỘC TÍNH VỊ TRÍ. 2c Set Sa t1 E23 853858158853 E58 1531581111 EEserrersred II. NHIỆM VỤ VA NỘI DUNG. SG cà SH T1 HT HT HT Hàn HH nh IH.

NGÀY GIAO NHIỆM VU :. 2 SG ST ST TH TH TH TH TH HH IV. NGÀY HOÀN THÀNH NHIEM VU:. SG SG SE Hye V.

CÁN BỘ HUONG DÂN (Ghi rõ học ham, học vị, họ, tên): ¬ eeeeceeeeuesceeeees PGS. TS Thoại Nam. ---- - ----c cc CS SỲ S1 S HH cv, Tp. CAN BỘ HƯỚNG DAN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRUONG KHOA.

(Họ tên và chữ ký) Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 3 LOI CAM ON Em xin chân thành cam ơn thay Thoại Nam đã hướng dan và tận tình giúp đỡ em hoàn thành dé tài luận văn này. Em xin gửi lời cảm ơn đến các thây cô trong khoa Khoa Học và Kỹ Thuật Máy Tính đã ho trợ giúp đỡ em trong thời gian hoàn thành đê tài luận van. Cuôi cùng, em xin cảm ơn ba mẹ và bạn bè đã động viên, hô trợ giúp em có thê hoàn thành dé tài luận văn này. Hồ Chi Minh, ngày 22 tháng 11 năm 2013 Học viên Hoàng Việt Hùng Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 4 TÓM TẮT LUẬN VĂN THẠC SĨ Hiện tại, trên các mạng xã hội, nhu cầu về tìm kiếm hình ảnh tương đồng về địa điểm đang ngày một tăng lên.

Tuy nhiên dé có thé đáp ứng được những yêu cau nay đòi hỏi các hệ thống lưu trữ và tìm kiếm ảnh trên các trang mạng xã hội phải sử dụng các giải thuật tìm kiếm thông minh và tương đối phức tạp trên toàn bộ dữ liệu của hệ thông lên đến hàng trăm tỉ hình anh. Đề tài này dé ra một mô hình hệ thong Location-Based Image Searching System (LBIS System) có khả năng tối giảm và tổ chức lại giữ liệu để tăng tốc quá trình tìm kiếm hình ảnh và hơn thế nữa mô hình hệ thống này hướng tới gắn kết được các trang mạng xã hội. Mô hình LBIS giải quyết van dé trên bang cách nhóm thông tin metadata của các hình anh có điểm tương đồng về vị trí thành dang file để quản ly và sử dụng ham Locality Sensitive Hashing để tăng tốc quá trình tìm kiếm. Nowsaday, the requirements for identification of correlative location images have increased significantly on social networks.

Consequently, complex image searching methods are required to handle the searching on extreme large-scale storage systems, which usually comprise hundreds of billions of photos. This thesis proposes the Location-Based Image Searching System (LBIS System) for reducing and organizing the big data in order to improve the speed of searching the images. LBIS solves the problems by grouping the metadata of images, which have correlative locations for managing and using Locality Sensitive Hashing for quickly searching. Nghiên cứu và xây dung hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 5 LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả thao 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 bay trong luận vặn này là do chúng em 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 để lay mot bang cấp ở trường này hoặc trường khác.

Hồ Chí Minh, ngày 22 tháng 11 năm 2013 Học viên Hoàng Việt Hùng Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 6 MỤC LỤC I. TONG QUAN VE DE TÀI. - SE E121 515115151 15151 111 ke gi 11 1. GiGi thiGu GE ti.

II Nội dung để tải. - - c1 HE TT TT HT TT TH TT HT TH ng ngu 13 Phương pháp giải quyết vấn đồ. - --- cv 1v TT 1n TT ng ng ru 14 Tóm tat các giải pháp và kết quả đạt được của dé tài. CAC VAN DE LIEN QUAN Q.ccccccssecessececssceccscesceeseceesecsesacesacecescseaceceaees 17 Hệ thống Haystack — Facebook.

Tổng quan về hệ thống HaystacÌK. 20 Khảo sát các hệ thông File Sysf€m.---- G1 1 HH ng ng ngu 21 Khao sát các giải thuật tim kiếm liên quan đến không gian. Nhóm giải thuật Tree Based. Locality- Sensitive Hashing.

KIÊN TRÚC MÔ HINH LBIS. Bai toán tìm kiếm hình ảnh tương tự dựa trên thuộc tính vị trí. Mô hình hệ thống LBIS. (G6 E1 SE1 v91 E111 HT ng ng ru 31 3.

Giải pháp tối ưu hoá việc tìm kiếm hình ảnh trên mô hình hệ thống LBIS. Nâng cấp giải pháp tối ưu hoá việc tìm kiếm hình ảnh trên mô hình LBIS (LBIS „25157020. HIỆN THỰC MÔ HINH LBIS.- i2 St S22 E323 E23 ESEESEESEESEEsEEseeserssed 46 Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 7 1. Chon hệ thống file system cho LBIS Store.

Hiện thực ham Locality Sensitive Hashing. Hiện thực hệ thống LIBIS.- - G2183 E11 vn HT ng ru 47 4. Đánh giá hệ thống LBIS. TONG KẾT VÀ ĐÁNH GIIÁ.

5 S: Sẻ S111 EEE1E1 1 12121111121 ke 64 1. — Các kết quả dat ẨưỢC.- c1 HT TT T TH HT HT Hư 64 2. Những hạn chế của dé tải.-- - skE x1 S91 11 11 H11 kg TT HH ng dư 65 3. Hướng mở rộng khắc phục .---G- + SE E9E 1S SE SE cvE cvg ggg rrơu 65 TÀI LIEU THAM KHẢO.

_ Locality Sensitive Hashing. Hướng dẫn cài đặt. LG ST TT TH TY TH TH TT HH ru 73 PHAN LÝ LICH TRÍCH NGANG. 5-5 <5 SE 515151111121 1121 11111121 cce 78 Nghiên cứu và xây dựng hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang § MỤC LỤC HÌNH Hình 1: Giải pháp dành cho 2 CAS€ SÍMđÌÿ.

S122 SS SA tt txy 12 Hình 2: Oud trình tim kiếm hình ảnh của Haystack .occcccccccccccccccscssscsevsvecsecevsvevevees 17 Hình 3: Qua trình upload hình ảnh của FlqySÍđCÃ. c5 553313 +++++skxx2 18 Hình 4: Layout của một NeedÏe. SH 1211111111111 111111111111 151111 ky 20 Hình 5: Layout của mỘI Index ƒlÌ©. - - cece cence cece cece eee eee 11111111111 1111k ky 20 Hình 6: Kiến trúc của NIF.

rrg 21 Hình 7: Cách tô chức file của AF. sách ThS nh TH HH HH tea 22 Hình 8: Kiến trúc file của OC@AN StOVEe .ccccccccscccsccscsvsesevevsvsevevssesvsvscseuevssestsvscsevees 22 Hình 9: Kiến trúc GES.ocecccceccescsseeseesesseesessesesseesessessesussssesseaseanssessestesnssessesieaneaneees 23 Hình 10: Kiến trúc DVHđIHO.sc- ccSnTtvEE E SE TH TH HH eo 23 Hình 11: Kiến trúc ÑF. cc St St E1 1H12 24 Hình 12: Kiến trúc của XI S. rrrg 25 Hình 13: Không gian phán hoạch của cây QuadTree .--Ặcccccc++++S+s+2 26 Hình 14: Không gian phán hoạch cây K-D TT€©.

Q1 HS SE eee EEE EEE TT nhu 27 Hình 16: Hàm hash bình thuOng. cece cece SH SH ST kg nhu 27 Hình 17: Ham Locality Sensitive Flashing.- ccc vn H SH xxx ey 28 Hình 18: Kết quả do đạc của nhóm Zerry ZlHB. Sách treo 30 Hình 19: Cách tô chức file trên Store Machine .cccccccccccccscscsessvscscsevevsesseseevseeees 32 Hình 20: Không gian trái đất được phân hoạCh. cScce tt vs Ersrrrrersrrree 33 Hình 21: Cách thức mapping của LBIS DDIF€CÍOFW.

34 Hình 22: Quá trình upload anh lên LBÌÏS. cá cece x2 121111 cty 35 Hình 23: Quá trình tim kiếm ảnh trên LBÌẨS. ST T ng re 36 Hình 24: Thứ tự li trữ tren ƒ1Ï@. cece cece E SE K kg eee 111K nền nu 40 Hình 25: Quá trình lưu trữ Với LSHH.

Ặ TS SH SH ST này 4] Hình 26: Oud trình tìm kiếm với LSH .occccccccccccccccsccscscsesecscsessvsvsscsvsvscsevevssestsvsceeeees 42 Hình 27: Layout của Ï file IH(€X. TS eee c cece cee eee eee 111111 cv ky 43 Hình 28: Quá trình xod ảnh trên LBÌ. Ă Ác ccc kEk v1 111kg này 44 Hình 29: Thông tin về Descriptor của XFS File SŠVSI€IM. cac cc Set trierree 46 Hình 30: Kiến trúc luận lý của hệ thong LBIS.

ST TS TS re 47 Hình 31: Kiến trúc vật lý của hệ thong LBIE.Sc kctcT ng tr tra 46 Hình 32: Không gian thé giới thực được phân hoạch .-ccccc set srrersrerree 50 Hình 33: Biểu AO feSI.22 ra 63 Hình 34: LSH và vi trí các điểm trên Qual CAU.ceccceccccesccscscsscsvsvscssvsvseesvsvssestevseeeeees 69 Hình 35: Bai todn nearest neighbour SCAPrching. 71 Hình 36: Chay chương trình tao (đÍ4ÍŒS©Í.v tt vxy 73 Hình 37: Chạy chương trình truy vẫn ma tr@neicccccccccccccccccvscscsesscscecsevsvsvssesvsvsceseees 74 Nghiên cứu và xây dung hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Hình 38: Chạy chương trình test LBIS Store với LSH.-ẶẶ c2 75 Nghiên cứu và xây dung hệ thống tìm kiếm ảnh dựa trên thuộc tính vị trí Trang 10 I. TONG QUAN VE DE TÀI 1. Giới thiệu đề tài Cac mạng xã hội [1] hiện nay như myspace, facebook, twitter thu hút được rất nhiều người dùng và việc ghé thăm các mạng xã hội đã trở thành một hoạt động thường xuyên của nhiều người trên thế giới.

Hiện tại, có hàng trăm mạng xã hội với rất nhiều hoạt động cung cấp cho người dùng. Và một trong sô những tính năng mà mạng xã hội cung câp cho người dùng đó là việc chia sẻ hình ảnh. Người dùng có thể lưu trữ được hình ảnh của họ trên các trang này và chia sẻ cho bạn của họ hoặc thậm chí là chia sẻ rộng rãi cho mọi người. Các hệ thống mạng xã hội trên không chỉ lưu trữ các bức hình ma còn lưu trữ những thông tin cần thiết của bức hình đó nếu người dùng cung cấp, ví dụ: vi trí chụp, thời gian, tag.

Chính vì vậy mạng xã hội và những hình ảnh trên đó là một trong những tai nguyên quý giá để các ứng dụng có thé khai thác được dữ liệu và cung cấp cho ngưởi dùng những thông tin cần thiết trong cuộc sống.