Hình ảnh vân tay để so sánh sự giống nhau của nhiều hình ảnh

Question

Tôi cần tạo vân tay của nhiều hình ảnh (khoảng 100.000 hiện có, 1000 mới mỗi ngày, RGB, JPEG, kích thước tối đa 800x800) để so sánh mọi hình ảnh với mọi hình ảnh khác rất nhanh. Tôi không thể sử dụng các phương thức so sánh nhị phân vì các hình ảnh gần giống nhau nên được nhận dạng.

Tốt nhất sẽ là một thư viện hiện có, nhưng cũng có một số gợi ý cho các thuật toán hiện có sẽ giúp tôi rất nhiều.

Answer 1

Một cách bạn có thể thực hiện việc này là thay đổi kích thước hình ảnh và giảm độ phân giải đáng kể (xuống 200x200 có thể?), Lưu trữ phiên bản nhỏ hơn (pixel-trung bình) để thực hiện so sánh. Sau đó xác định ngưỡng dung sai và so sánh từng pixel. Nếu RGB của tất cả các pixel nằm trong dung sai, bạn đã có một kết quả phù hợp.

Lần chạy ban đầu của bạn là O (n^2) nhưng nếu bạn lập danh mục tất cả, mỗi hình ảnh mới chỉ là một thuật toán O (n) để so sánh (bạn chỉ phải so sánh nó với từng hình ảnh được chèn trước đó). Nó cuối cùng sẽ bị phá vỡ tuy nhiên khi danh sách các hình ảnh để so sánh trở nên lớn hơn, nhưng tôi nghĩ rằng bạn đang an toàn trong một thời gian.

Sau 400 ngày chạy, bạn sẽ có 500.000 hình ảnh, có nghĩa là (giảm thời gian để thay đổi kích thước hình ảnh xuống) 200(H)*200(W)*500,000(images)*3(RGB) = 60.000.000.000 so sánh. Nếu mỗi hình ảnh là một trận đấu chính xác, bạn sẽ bị tụt lại phía sau, nhưng đó có thể không phải là trường hợp, phải không? Hãy nhớ rằng, bạn có thể giảm giá cho một hình ảnh ngay sau khi so sánh đơn nằm ngoài ngưỡng của bạn.

Answer 2

Bạn có thực sự muốn so sánh mọi hình ảnh với những hình ảnh khác không? Ứng dụng là gì? Có lẽ bạn chỉ cần một số loại lập chỉ mục và truy xuất hình ảnh dựa trên các mô tả nhất định? Sau đó, ví dụ bạn có thể xem tiêu chuẩn MPEG-7 cho Giao diện Mô tả Nội dung Đa phương tiện. Sau đó, bạn có thể so sánh các mô tả hình ảnh khác nhau, điều này sẽ không chính xác nhưng nhanh hơn nhiều.

Answer 3

Tương tự như câu trả lời của Ic - bạn có thể thử so sánh hình ảnh ở nhiều độ phân giải. Vì vậy, mỗi hình ảnh được lưu dưới dạng 1x1, 2x2, 4x4 .. 800x800. Nếu độ phân giải thấp nhất không khớp (tùy thuộc vào ngưỡng), bạn có thể từ chối ngay lập tức. Nếu nó khớp với nhau, bạn có thể so sánh chúng ở độ phân giải cao hơn tiếp theo, v.v ..

Ngoài ra - nếu ảnh chia sẻ bất kỳ cấu trúc tương tự nào, chẳng hạn như ảnh y tế, bạn có thể trích xuất cấu trúc đó thành mô tả đó là dễ dàng hơn/nhanh hơn để so sánh.

Answer 4

Dường như các thuật toán băm hình ảnh chuyên biệt là một lĩnh vực nghiên cứu hoạt động nhưng có lẽ một phép tính băm bình thường của các byte hình ảnh sẽ thực hiện thủ thuật.

Bạn đang tìm kiếm hình ảnh giống hệt byte thay vì tìm kiếm hình ảnh có nguồn gốc từ cùng một nguồn nhưng có thể là định dạng hoặc độ phân giải khác (điều này đánh tôi là một vấn đề khá khó).

Answer 5

Thuật toán băm thông thường hoặc thuật toán CRC không hoạt động tốt với dữ liệu hình ảnh. Bản chất chiều của thông tin phải được tính đến.

Nếu bạn cần dấu vân tay cực kỳ mạnh mẽ, các phép biến đổi affine (chia tỷ lệ, xoay, dịch, lật) được tính, bạn có thể sử dụng Radon transformation on the image source để tạo bản đồ quy chuẩn của dữ liệu ảnh - lưu trữ ảnh này với từng ảnh chỉ so sánh dấu vân tay. Đây là một thuật toán phức tạp và không dành cho những người yếu tim.

một số giải pháp đơn giản có thể xảy ra:

1. Tạo một biểu đồ độ sáng cho hình ảnh như một dấu vân tay
2. Tạo thu nhỏ lại các phiên bản của mỗi hình ảnh như một dấu vân tay
3. Kết hợp kỹ thuật (1) và (2) vào cách tiếp cận lai để cải thiện chất lượng so sánh

Biểu đồ độ sáng (đặc biệt là biểu đồ được tách thành các thành phần RGB) là một dấu vân tay hợp lý r một hình ảnh - và có thể được thực hiện khá hiệu quả. Trừ một biểu đồ từ một biểu đồ khác sẽ tạo ra một lược đồ mới mà bạn có thể xử lý để quyết định hai hình ảnh tương tự như thế nào. Biểu đồ, bởi vì chỉ đánh giá sự phân bố và sự xuất hiện của độ sáng/thông tin màu xử lý biến đổi affine khá tốt. Nếu bạn lượng hóa thông tin độ sáng của mỗi thành phần màu xuống giá trị 8 bit, dung lượng lưu trữ 768 byte là đủ cho dấu vân tay của một hình ảnh có kích thước gần như hợp lý. Biểu đồ độ sáng tạo ra âm bản sai khi thông tin màu trong hình ảnh được điều khiển. Nếu bạn áp dụng các biến đổi như độ tương phản/độ sáng, áp phích, thay đổi màu sắc, thay đổi thông tin độ sáng. Sai tích cực cũng có thể xảy ra với một số loại hình ảnh nhất định ... chẳng hạn như phong cảnh và hình ảnh trong đó một màu duy nhất thống trị người khác.

Sử dụng hình ảnh được chia tỷ lệ là một cách khác để giảm mật độ thông tin của hình ảnh xuống mức dễ so sánh hơn. Giảm dưới 10% kích thước hình ảnh ban đầu thường mất quá nhiều thông tin sẽ được sử dụng - vì vậy, hình ảnh 800x800 pixel có thể được thu nhỏ xuống 80x80 và vẫn cung cấp đủ thông tin để thực hiện lấy dấu vân tay. Không giống như dữ liệu biểu đồ, bạn phải thực hiện chia tỷ lệ dị hướng của dữ liệu hình ảnh khi độ phân giải nguồn có các tỷ lệ khung hình khác nhau. Nói cách khác, giảm một hình ảnh 300x800 thành hình thu nhỏ 80x80 gây biến dạng của hình ảnh, chẳng hạn khi so sánh với hình ảnh 300x500 (rất giống) sẽ gây ra âm bản sai. Dấu vân tay hình thu nhỏ cũng thường tạo ra âm bản sai khi các biến đổi affine được tham gia. Nếu bạn lật hoặc xoay hình ảnh, hình thu nhỏ của nó sẽ khác với hình ảnh gốc và có thể dẫn đến kết quả dương tính giả.

Kết hợp cả hai kỹ thuật là một cách hợp lý để phòng ngừa cược của bạn và giảm sự xuất hiện của cả hai xác thực sai và âm tính giả.

Answer 6

Một thời gian dài trước đây, tôi đã làm việc trên một hệ thống mà đã có một số đặc điểm giống nhau, và điều này là một xấp xỉ của thuật toán chúng tôi theo:

1. Divide hình thành các khu. Trong trường hợp của chúng tôi, chúng tôi đã xử lý video có độ phân giải 4: 3, vì vậy chúng tôi đã sử dụng 12 vùng. Làm điều này có độ phân giải của hình ảnh nguồn ra khỏi hình ảnh.
2. Đối với mỗi khu vực, tính toán một màu tổng thể - mức trung bình của tất cả các pixel trong vùng
3. Đối với toàn bộ hình ảnh, tính toán một màu tổng thể - mức trung bình của tất cả các khu

Vì vậy, đối với mỗi hình ảnh, bạn đang lưu trữ n + 1 giá trị số nguyên, trong đó n là số vùng bạn đang theo dõi.

Để so sánh, bạn cũng cần xem từng kênh màu riêng lẻ.

1. Đối với hình ảnh tổng thể, so sánh các kênh màu cho màu sắc tổng thể để xem nếu họ nằm trong một ngưỡng nhất định - nói, 10%
2. Nếu những hình ảnh nằm trong ngưỡng, bên cạnh so sánh từng phân khu. Nếu tất cả các vùng cũng nằm trong ngưỡng, hình ảnh là một kết hợp đủ mạnh mà bạn có thể gắn cờ chúng để so sánh thêm.

Điều này cho phép bạn nhanh chóng loại bỏ hình ảnh không phù hợp; bạn cũng có thể sử dụng nhiều vùng hơn và/hoặc áp dụng thuật toán đệ quy để có được độ tin cậy khớp mạnh hơn.

Answer 7

Có một cách tiếp cận đặc biệt ít hơn so với các biến thể hình ảnh được chia nhỏ đã được đề xuất ở đây giữ lại hương vị chung của chúng, nhưng mang lại cơ sở toán học nghiêm ngặt hơn nhiều cho những gì đang diễn ra.

Chụp Haar wavelet của hình ảnh. Về cơ bản, Haar wavelet là sự liên tiếp của sự khác biệt so với hình ảnh có độ phân giải thấp hơn cho mỗi hình ảnh có độ phân giải cao hơn, nhưng được cân nhắc bởi mức độ sâu của bạn trong 'cây' của mipmaps. Tính toán đơn giản. Sau đó, một khi bạn có các wavelet Haar một cách thích hợp trọng, ném đi tất cả, nhưng các hệ số lớn nhất k (về giá trị tuyệt đối), bình thường hóa các vector và lưu nó.

Nếu bạn lấy sản phẩm dấu chấm của hai trong số các vectơ chuẩn hóa đó, nó sẽ cho bạn một phép đo tương tự với 1 là gần như giống hệt nhau. Tôi đã đăng thêm thông tin qua here.

Answer 8

hoặc bạn có thể sử dụng http://tineye.com thực hiện chính xác những gì bạn muốn! (Kiểm tra API thương mại)

nhưng tôi đang quan tâm về cách họ làm điều đó, mà công nghệ vv ...

Answer 9

Vì vậy, bạn muốn làm "dấu vân tay phù hợp với" đó là khá khác biệt so với "phù hợp hình ảnh". phân tích dấu vân tay đã được nghiên cứu sâu sắc trong suốt 20 năm qua, và một số thuật toán thú vị đã được phát triển để đảm bảo tỷ lệ phát hiện bên phải (đối với các FAR và FRR biện pháp - False Acceptance Rate và False Rate chối).

Tôi khuyên bạn nên xem xét kỹ hơn về LFA (Phân tích đối tượng địa lý) các kỹ thuật phát hiện, chủ yếu được xây dựng trên kiểm tra minutiae. Minutiae là đặc điểm cụ thể của bất kỳ dấu vân tay nào, và đã được xếp vào một số lớp. Lập bản đồ một hình ảnh raster đến một bản đồ minutiae là những gì thực sự hầu hết các Cơ quan hành chính làm để nộp tội phạm hoặc khủng bố.

Xem here để tham khảo thêm

Answer 10

Đối với iPhone hình ảnh so sánh và phát triển giống hình ảnh kiểm tra: http://sites.google.com/site/imagecomparison/

Để nhìn thấy nó trong hành động, hãy kiểm tra eyeBuy Visual Search trên iTunes AppStore.

Answer 11

Bạn chắc chắn nên xem phash.

Để so sánh hình ảnh có dự án này php: https://github.com/kennethrapp/phasher

Và nhỏ của tôi javascript bản sao: https://redaktorcms.com/dev/phasher/demo_js/index.html

Thật không may đây là "bitcount" dựa trên nhưng sẽ nhận ra hình ảnh xoay. Một cách tiếp cận khác trong javascript là xây dựng một biểu đồ độ sáng từ hình ảnh nhờ sự trợ giúp của canvas. Bạn có thể hình dung một biểu đồ đa giác trên vải và so sánh rằng đa giác trong cơ sở dữ liệu của bạn (ví dụ như mySQL không gian ...)

Đây là một bản demo cho biểu đồ video: https://redaktorcms.com/dev/globetrottr/testHashVideo.php

Answer 12

Tính đến năm 2015 (trở lại tương lai ... vào câu hỏi năm 2009 hiện được xếp hạng cao trong Google), tính tương tự về hình ảnh có thể được tính bằng các kỹ thuật Học tập sâu. Gia đình của các thuật toán được gọi là bộ mã hóa tự động có thể tạo ra một đại diện véc tơ có thể tìm kiếm được sự giống nhau. Có một bản demo here.