Phát hiện hình ảnh gần giống hệt

Question

Cách nhanh để sắp xếp một tập hợp hình ảnh nhất định bằng sự giống nhau của chúng với nhau.

Hiện tại tôi có một hệ thống phân tích biểu đồ giữa hai hình ảnh, nhưng đây là một hoạt động rất tốn kém và có vẻ quá quá mức.

Tối ưu Tôi đang tìm một thuật toán có thể cung cấp cho mỗi hình ảnh một điểm (ví dụ một số nguyên, chẳng hạn như RGB Average) và tôi có thể sắp xếp theo điểm số đó. Điểm số hoặc điểm số bên cạnh nhau là các bản sao có thể có.

0299393 
0599483 
0499994 <- possible dupe 
0499999 <- possible dupe 
1002039 
4995994 
6004994 

RGB Trung bình trên mỗi hình ảnh thật, có điều gì tương tự không?

Answer 1

Đã có rất nhiều nghiên cứu về tìm kiếm hình ảnh và các biện pháp tương tự. Nó không phải là một vấn đề dễ dàng. Nói chung, một int sẽ không đủ để xác định xem hình ảnh có giống nhau hay không. Bạn sẽ có tỷ lệ dương tính giả cao.

Tuy nhiên, vì đã có rất nhiều nghiên cứu được thực hiện, bạn có thể xem xét một số trong số đó. Ví dụ: this paper (PDF) cung cấp thuật toán quét hình ảnh nhỏ gọn phù hợp để tìm hình ảnh trùng lặp nhanh chóng và không lưu trữ nhiều dữ liệu. Có vẻ như đây là phương pháp phải nếu bạn muốn một thứ gì đó mạnh mẽ.

Nếu bạn đang tìm kiếm một cái gì đó đơn giản hơn, nhưng chắc chắn hơn ad-hoc, this SO question có một vài ý tưởng phong nha.

Answer 2

tôi giả định rằng phần mềm tìm kiếm hình ảnh trùng lặp khác thực hiện một FFT trên hình ảnh, và lưu trữ các giá trị của các tần số khác nhau như một vectơ:

Image1 = (u1, u2, u3, ..., un) 
Image2 = (v1, v2, v3, ..., vn) 

và sau đó bạn có thể so sánh hai hình ảnh cho equalness bởi tính toán khoảng cách giữa các vectơ trọng số của hai hình ảnh:

distance = Sqrt(
    (u1-v1)^2 + 
    (u2-v2)^2 + 
    (u2-v3)^2 + 
    ... 
    (un-vn)^2); 

Answer 3

Bạn phải quyết định "tương tự" là gì. Tương phản? Huế?

Ảnh có phải là "tương tự" với cùng một hình ảnh lộn ngược không?

Tôi đặt cược bạn có thể tìm thấy rất nhiều "cuộc gọi gần" bằng cách chia nhỏ hình ảnh thành các phần 4x4 và nhận được màu trung bình cho mỗi ô lưới. Bạn sẽ có mười sáu điểm cho mỗi hình ảnh. Để đánh giá sự giống nhau, bạn sẽ chỉ làm một tổng các ô vuông khác nhau giữa các hình ảnh.

Tôi không nghĩ rằng một băm đơn có ý nghĩa, trừ khi nó chống lại một khái niệm đơn lẻ như màu sắc, hoặc độ sáng hoặc độ tương phản.

Dưới đây là ý tưởng của bạn:

0299393 
0599483 
0499994 <- possible dupe 
0499999 <- possible dupe 
1002039 
4995994 
6004994 

Trước hết, tôi sẽ giả định đây là những số thập phân mà là R * (2^16) + G * (2^8) + B, hoặc một cái gì đó như thế. Rõ ràng điều đó không tốt bởi vì màu đỏ có trọng số bất thường.

Moving into HSV space sẽ tốt hơn. Bạn có thể spread the bits of HSV out vào băm, hoặc bạn chỉ có thể giải quyết H hoặc S hoặc V riêng lẻ, hoặc bạn có thể có ba băm cho mỗi hình ảnh.

---

Một điều nữa. Nếu bạn làm trọng lượng R, G, và B. Trọng lượng màu xanh lá cây cao nhất, sau đó màu đỏ, sau đó màu xanh để phù hợp với độ nhạy thị giác của con người.

Answer 4

Có thư viện C ("libphash" - http://phash.org/) sẽ tính toán "băm nhận thức" của hình ảnh và cho phép bạn phát hiện hình ảnh tương tự bằng cách so sánh băm (vì vậy bạn không phải so sánh từng hình ảnh trực tiếp hình ảnh khác) nhưng tiếc là nó không có vẻ rất chính xác khi tôi thử nó.

Answer 5

Một giải pháp là thực hiện so sánh RMS/RSS trên mỗi cặp ảnh cần thiết để thực hiện sắp xếp bong bóng. Thứ hai, bạn có thể thực hiện FFT trên mỗi hình ảnh và thực hiện một số trục trung bình để truy xuất một số nguyên duy nhất cho mỗi hình ảnh mà bạn sẽ sử dụng làm chỉ mục để sắp xếp theo. Bạn có thể cân nhắc thực hiện bất kỳ sự so sánh nào trên phiên bản được thay đổi kích thước (25%, 10%) của bản gốc tùy thuộc vào sự khác biệt nhỏ mà bạn chọn để bỏ qua và bạn cần bao nhiêu lần tăng tốc. Hãy cho tôi biết nếu các giải pháp này là thú vị và chúng tôi có thể thảo luận hoặc tôi có thể cung cấp mã mẫu.

Answer 6

Một hình ảnh có nhiều tính năng, do đó, trừ khi bạn thu hẹp bản thân, chẳng hạn như độ sáng trung bình, bạn đang xử lý không gian vấn đề không gian n chiều.

Nếu tôi yêu cầu bạn chỉ định một số nguyên duy nhất cho các thành phố trên thế giới, vì vậy tôi có thể biết được số nào ở gần, kết quả sẽ không tuyệt vời. Ví dụ: bạn có thể chọn múi giờ làm số nguyên duy nhất và nhận kết quả tốt với một số thành phố nhất định. Tuy nhiên, một thành phố gần cực bắc và một thành phố khác gần cực nam cũng có thể ở cùng một múi giờ, mặc dù chúng nằm ở đầu đối diện của hành tinh. Nếu tôi cho phép bạn sử dụng hai số nguyên, bạn có thể nhận được kết quả rất tốt với vĩ độ và kinh độ. Vấn đề là tương tự cho sự giống nhau về hình ảnh.

Tất cả những gì đã nói, có các thuật toán cố gắng ghép các hình ảnh tương tự lại với nhau, đó là những gì bạn đang yêu cầu một cách hiệu quả. Đây là những gì xảy ra khi bạn phát hiện khuôn mặt với Picasa. Ngay cả trước khi bạn xác định bất kỳ khuôn mặt nào, nó cũng nhóm các khuôn mặt tương tự lại với nhau để dễ dàng đi qua một bộ mặt tương tự và đặt cho hầu hết chúng cùng một tên.

Ngoài ra còn có một kỹ thuật được gọi là Phân tích thành phần nguyên tắc, cho phép bạn giảm dữ liệu n chiều xuống bất kỳ số lượng kích thước nhỏ hơn nào. Vì vậy, một hình ảnh với các tính năng n có thể được giảm xuống một tính năng. Tuy nhiên, đây vẫn không phải là cách tiếp cận tốt nhất để so sánh hình ảnh.

Answer 7

Trong kỷ nguyên của các dịch vụ web mà bạn có thể thử http://tineye.com

Answer 8

tôi thực hiện một thuật toán rất đáng tin cậy cho việc này được gọi là Fast Multiresolution Image Querying. Mã của tôi (cổ đại, chưa được duy trì) cho điều đó là here.

Truy vấn hình ảnh Multiresolution hình ảnh nhanh nào được chia hình ảnh thành 3 phần dựa trên không gian màu YIQ (tốt hơn cho sự khác biệt phù hợp so với RGB). Sau đó, hình ảnh về cơ bản được nén bằng thuật toán wavelet cho đến khi chỉ có các tính năng nổi bật nhất từ ​​mỗi không gian màu có sẵn. Những điểm này được lưu trữ trong một cấu trúc dữ liệu. Các hình ảnh truy vấn đi qua cùng một quy trình và các tính năng nổi bật trong hình ảnh truy vấn được so khớp với các đối tượng trong cơ sở dữ liệu được lưu trữ. Càng có nhiều trận đấu thì hình ảnh càng giống nhau.

Thuật toán thường được sử dụng cho chức năng "truy vấn bằng phác thảo". Phần mềm của tôi chỉ cho phép nhập hình ảnh truy vấn qua URL, do đó không có giao diện người dùng. Tuy nhiên, tôi thấy nó hoạt động đặc biệt tốt cho phù hợp với hình thu nhỏ cho phiên bản lớn của hình ảnh đó.

Phần lớn ấn tượng hơn phần mềm của tôi là retrievr cho phép bạn thử thuật toán FMIQ bằng cách sử dụng hình ảnh Flickr làm nguồn. Rất tuyệt! Hãy thử nó qua phác thảo hoặc sử dụng một hình ảnh nguồn, và bạn có thể thấy nó hoạt động tốt như thế nào.

Answer 9

Tôi khuyên bạn nên xem xét di chuyển ra khỏi chỉ bằng cách sử dụng biểu đồ RGB. Bạn có thể thu được thông báo tốt hơn về hình ảnh của mình nếu bạn chụp ảnh 2 Haar wavelet của hình ảnh (dễ hơn rất nhiều so với âm thanh của nó, nó chỉ có rất nhiều trung bình và một số căn bậc hai được sử dụng để cân các hệ số của bạn) và chỉ giữ lại k hệ số trọng số lớn nhất trong wavelet như là một vectơ thưa thớt, bình thường hóa nó và lưu lại để giảm kích thước của nó. Bạn nên rescale R G và B bằng cách sử dụng trọng lượng cảm nhận trước ít nhất hoặc tôi khuyên bạn nên chuyển sang YIQ (hoặc YCoCg, để tránh nhiễu lượng tử) để bạn có thể lấy mẫu thông tin chrominance với tầm quan trọng giảm.

Bây giờ, bạn có thể sử dụng sản phẩm dấu chấm của hai trong số các vectơ chuẩn hóa thưa thớt này làm thước đo tương tự. Các cặp hình ảnh với các sản phẩm chấm lớn nhất sẽ có cấu trúc rất giống nhau. Điều này có lợi ích là hơi có khả năng chống thay đổi kích thước, thay đổi màu sắc và watermarking, và được thực sự dễ dàng để thực hiện và nhỏ gọn.

Bạn có thể trao đổi lưu trữ và độ chính xác bằng cách tăng hoặc giảm k.

Sắp xếp theo một điểm số duy nhất sẽ có thể gây khó khăn cho loại vấn đề phân loại này. Nếu bạn nghĩ về nó nó sẽ yêu cầu hình ảnh để chỉ có thể 'thay đổi' dọc theo một trục, nhưng họ không. Đây là lý do tại sao bạn cần một vectơ các tính năng. Trong trường hợp sóng Haar wavelet của nó khoảng nơi mà các gián đoạn sắc nét nhất trong hình ảnh xảy ra. Bạn có thể tính toán khoảng cách giữa các hình ảnh theo cặp, nhưng vì tất cả những gì bạn có là một số liệu khoảng cách, thứ tự tuyến tính không có cách nào để diễn tả 'tam giác' của 3 hình ảnh đều giống nhau. (tức là nghĩ về một hình ảnh có màu xanh lá cây, một hình ảnh có màu xanh và một hình ảnh có màu xanh dương.)

Điều đó có nghĩa là bất kỳ giải pháp thực sự nào cho vấn đề của bạn sẽ cần các hoạt động O (n^2) số lượng hình ảnh bạn có. Trong khi nếu nó đã có thể tuyến tính các biện pháp, bạn có thể yêu cầu chỉ O (n log n), hoặc O (n) nếu biện pháp phù hợp cho, nói, một loại radix. Điều đó nói rằng, bạn không cần phải chi tiêu O (n^2) kể từ khi thực hành bạn không cần phải sàng lọc thông qua toàn bộ, bạn chỉ cần tìm những thứ đó gần hơn một số ngưỡng. Vì vậy, bằng cách áp dụng một trong các kỹ thuật để phân vùng không gian vectơ thưa thớt của bạn, bạn có thể nhận được nhiều asymptotics nhanh hơn cho 'tìm kiếm tôi k của hình ảnh tương tự hơn so với vấn đề ngưỡng nhất định' so với việc so sánh mọi hình ảnh với mọi hình ảnh, bạn có thể cần ... nếu không chính xác những gì bạn yêu cầu. Trong bất kỳ trường hợp nào, tôi đã sử dụng điều này vài năm trước để có hiệu quả tốt khi cố gắng giảm thiểu số lượng hoạ tiết khác nhau mà tôi đã lưu trữ, nhưng cũng có rất nhiều tiếng ồn nghiên cứu trong không gian này cho thấy hiệu quả của nó (và trong trường hợp này so sánh nó với một hình thức tinh vi hơn của phân loại biểu đồ):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Nếu bạn cần độ chính xác tốt hơn trong việc phát hiện, các minHash và các thuật toán tF-IDF có thể được sử dụng với wavelet Haar (hoặc biểu đồ) để đối phó với các chỉnh sửa mạnh mẽ hơn:

Cuối cùng, Stanford có một tìm kiếm hình ảnh dựa trên một biến thể kỳ lạ hơn của cách tiếp cận này, dựa trên việc khai thác thêm tính năng từ các wavelet để tìm các phần xoay hoặc chia tỷ lệ hình ảnh, v.v. số lượng công việc bạn muốn làm.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

Answer 10

Hầu hết các phương pháp tiếp cận hiện đại để phát hiện gần sao chép hình ảnh sử dụng phát hiện điểm thú vị phát hiện và mô tả mô tả khu vực xung quanh điểm đó. Thường sử dụng SIFT. Sau đó, bạn có thể quatize descriptors và sử dụng các cụm từ như từ vựng trực quan.

Vì vậy, nếu chúng ta thấy trên tỷ lệ các từ hình ảnh phổ biến của hai hình ảnh cho tất cả các từ hình ảnh của những hình ảnh này, bạn ước tính sự giống nhau giữa các hình ảnh. Có rất nhiều bài viết thú vị. Một trong số đó là Near Duplicate Image Detection: minHash and tf-idf Weighting

Answer 11

Câu hỏi Good way to identify similar images? dường như cung cấp giải pháp cho câu hỏi của bạn.

Answer 12

Ví dụ sử dụng IMMI mở rộng và IMMI bạn có thể kiểm tra nhiều cách khác nhau như thế nào để đo lường sự tương đồng giữa các hình ảnh: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension-for-rapidminer-5

Bằng việc xác định một số ngưỡng và chọn một số phương pháp bạn có thể đo sự tương đồng.