So sánh các tính năng SIFT được lưu trữ trong cơ sở dữ liệu mysql

Question

Tôi hiện đang mở rộng thư viện hình ảnh được sử dụng để phân loại hình ảnh và tôi muốn tìm hình ảnh trùng lặp, hình ảnh được chuyển đổi và hình ảnh chứa hoặc được chứa trong các hình ảnh khác.
Tôi đã thử nghiệm triển khai SIFT từ OpenCV và nó hoạt động rất tốt nhưng sẽ khá chậm đối với nhiều hình ảnh. Quá tốc độ nó lên Tôi nghĩ rằng tôi có thể trích xuất các tính năng và lưu chúng trong một cơ sở dữ liệu như rất nhiều dữ liệu meta liên quan đến hình ảnh khác đã được tổ chức ở đó.

Cách nhanh nhất để so sánh các tính năng của hình ảnh mới với các tính năng trong cơ sở dữ liệu là gì?
Thông thường so sánh được thực hiện tính toán khoảng cách euclide bằng cách sử dụng kd-tree, FLANN hoặc với Pyramid Match Kernel mà tôi tìm thấy trong một chuỗi khác ở đây trên SO, nhưng chưa xem xét nhiều.

Vì tôi không biết cách lưu và tìm kiếm kd-tree trong cơ sở dữ liệu một cách hiệu quả, tôi hiện chỉ nhìn thấy ba tùy chọn:
* Hãy để MySQL tính khoảng cách euclide cho mọi tính năng trong cơ sở dữ liệu , mặc dù tôi chắc chắn rằng sẽ mất một thời gian không hợp lý cho nhiều hơn một vài hình ảnh.
* Tải toàn bộ tập dữ liệu vào bộ nhớ ngay từ đầu và tạo (các) cây kd. Điều này có lẽ sẽ nhanh, nhưng rất tốn nhiều bộ nhớ. Cộng với tất cả các dữ liệu sẽ cần phải được chuyển từ cơ sở dữ liệu.
* Lưu các cây đã tạo vào cơ sở dữ liệu và tải tất cả chúng, sẽ là phương pháp nhanh nhất nhưng cũng tạo ra lượng lưu lượng cao như với hình ảnh mới kd-cây sẽ phải được xây dựng lại và gửi đến máy chủ.

Tôi đang sử dụng triển khai SIFT của OpenCV, nhưng tôi chưa chết trên đó. Nếu có một tính năng trích xuất phù hợp hơn cho nhiệm vụ này (và gần như bằng nhau mạnh mẽ) Tôi vui mừng nếu có ai đó có thể đề nghị một.

Answer 1

Vì vậy, về cơ bản tôi đã làm điều gì đó rất giống với điều này một vài năm trước đây. Thuật toán bạn muốn xem xét đã được đề xuất một vài năm trước bởi David Nister, bài báo là: "Khả năng mở rộng công nhận với cây từ vựng". Họ khá nhiều có một giải pháp chính xác cho vấn đề của bạn có thể mở rộng đến hàng triệu hình ảnh.

Đây là liên kết đến tóm tắt, bạn có thể tìm thấy liên kết tải xuống bằng cách googleing tiêu đề. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

Ý tưởng cơ bản là tạo một cây có thuật toán k-means thứ bậc để mô hình hóa các tính năng và sau đó tận dụng phân phối thưa thớt các tính năng trong cây đó để nhanh chóng tìm thấy hàng xóm gần nhất của bạn ... đó là một vài năm kể từ khi tôi làm việc trên nó. Bạn có thể tìm thấy một bài thuyết trình powerpoint về các tác giả trang web ở đây: http://www.vis.uky.edu/~dnister/Publications/publications.html

Một vài lưu ý khác:

• tôi sẽ không bận tâm với kernel trận đấu kim tự tháp, nó thực sự hơn để cải thiện sự công nhận đối tượng so với sao chép/biến đổi hình ảnh phát hiện.

• Tôi sẽ không lưu trữ bất kỳ nội dung tính năng nào trong cơ sở dữ liệu SQL. Tùy thuộc vào ứng dụng của bạn, nó là đôi khi hiệu quả hơn để tính toán các tính năng của bạn nhanh chóng vì kích thước của chúng có thể vượt quá kích thước hình ảnh ban đầu khi được tính toán dày đặc. Biểu đồ các tính năng hoặc con trỏ tới các nút trong cây từ vựng hiệu quả hơn nhiều.

• Cơ sở dữ liệu SQL không được thiết kế để thực hiện các phép tính vectơ điểm nổi lớn. Bạn có thể lưu trữ mọi thứ trong cơ sở dữ liệu của mình, nhưng không sử dụng nó làm công cụ để tính toán. Tôi đã thử điều này một lần với SQLite và nó đã kết thúc rất nặng.

• Nếu bạn quyết định thực hiện điều này, hãy đọc kỹ chi tiết và giữ một bản sao một cách tiện dụng trong khi triển khai nó, vì có rất nhiều chi tiết nhỏ rất quan trọng để làm cho thuật toán hoạt động hiệu quả.

Answer 2

Điều quan trọng, tôi nghĩ, đó là đây không phải là câu hỏi SIFT. Đó là một câu hỏi về tìm kiếm gần đúng lân cận gần nhất. Giống như hình ảnh phù hợp với điều này cũng là một vấn đề nghiên cứu mở. Bạn có thể thử googling "gần đúng tìm kiếm hàng xóm gần nhất" và xem loại phương pháp có sẵn. Nếu bạn cần kết quả chính xác, hãy thử: "tìm kiếm lân cận gần chính xác".

Hiệu suất của tất cả các cấu trúc dữ liệu hình học này (như kd-tree) bị suy giảm khi số thứ nguyên tăng lên, do đó, khóa tôi nghĩ là bạn có thể cần trình bày mô tả SIFT của mình ở số thứ nguyên thấp hơn 10-30 thay vì 256-1024) để thực sự có hiệu quả tìm kiếm lân cận gần nhất (sử dụng PCA chẳng hạn).

Khi bạn có điều này, tôi nghĩ rằng nó sẽ trở thành thứ yếu nếu dữ liệu được lưu trữ trong MySQL hay không.

Answer 3

Tôi nghĩ tốc độ không phải là vấn đề chính ở đây. Vấn đề chính là làm thế nào để sử dụng các tính năng để có được kết quả mà bạn muốn.

Nếu bạn muốn phân loại hình ảnh (ví dụ: người, ô tô, nhà, mèo), thì hạt nhân Kim tự tháp chắc chắn đáng xem. Nó thực sự là một biểu đồ của các mô tả tính năng địa phương, vì vậy không cần phải so sánh các tính năng riêng lẻ với nhau. Ngoài ra còn có một lớp học của các thuật toán được gọi là "túi từ", mà cố gắng để cụm các tính năng địa phương để tạo thành một "từ vựng trực quan". Một lần nữa, trong trường hợp này một khi bạn có "từ hình ảnh", bạn không cần tính toán khoảng cách giữa tất cả các cặp mô tả SIFT, mà thay vào đó, hãy xác định từng thuộc tính của từng cụm. Mặt khác, nếu bạn muốn nhận được điểm tương ứng giữa các cặp hình ảnh, chẳng hạn như để quyết định xem một hình ảnh có được chứa trong hình ảnh khác hay tính toán chuyển đổi giữa các hình ảnh thì bạn cần phải tìm chính xác hàng xóm gần nhất.

Ngoài ra, còn có các tính năng địa phương khác với SIFT. Ví dụ SURF là các tính năng tương tự như SIFT, nhưng chúng nhanh hơn để trích xuất và chúng được hiển thị để hoạt động tốt hơn cho một số tác vụ nhất định.

Nếu tất cả những gì bạn muốn làm là tìm bản sao, bạn có thể tăng tốc độ tìm kiếm của mình một cách đáng kể bằng cách sử dụng bộ mô tả hình ảnh toàn cầu, chẳng hạn như biểu đồ màu. So sánh hai biểu đồ màu là các đơn vị có cường độ nhanh hơn so với hai bộ có chứa hàng trăm tính năng SIFT. Bạn có thể tạo danh sách ngắn các ứng cử viên sử dụng biểu đồ màu và sau đó tinh chỉnh tìm kiếm của bạn bằng SIFT.

Answer 4

Tôi có một số công cụ trong python bạn có thể phát với here. Về cơ bản một gói của nó sử dụng các vector chuyển đổi SIFT, và sau đó tính toán băm lưới mạng gần nhất của mỗi véc tơ sàng lọc 128d. Việc băm là phần quan trọng vì nó nhạy cảm với địa phương, đơn giản có nghĩa là các vectơ gần trong không gian R^n dẫn đến xác suất va chạm băm tương đương. Công việc tôi cung cấp là phần mở rộng của Andoni cung cấp truy vấn phỏng đoán thích ứng cho việc cắt tỉa danh sách tìm kiếm chính xác LSH, cũng như việc triển khai CUDA tối ưu hóa chức năng băm. Tôi cũng có một ứng dụng nhỏ mà tìm kiếm cơ sở dữ liệu hình ảnh với thông tin phản hồi trực quan tốt đẹp, tất cả theo bsd (ngoại lệ là SIFT có một số hạn chế bổ sung).