Thuật toán băm hình ảnh nhanh và đơn giản

Question

Tôi cần thuật toán băm hình ảnh (tốt và đơn giản). Giá trị băm được sử dụng trong bảng tra cứu, không phải cho mật mã.

Một số hình ảnh là "đồ họa máy tính" - nghĩa là các bản màu được tô màu, văn bản được tô màu và v.v ... trong khi đó cũng có những hình ảnh "nhiếp ảnh" - chứa phổ màu phong phú, chủ yếu là trơn tru.

Tôi cũng muốn thuật toán băm có thể được áp dụng cho các phần hình ảnh cụ thể. Ý tôi là, hình ảnh có thể được chia thành một ô lưới và hàm băm của mỗi ô chỉ phụ thuộc vào nội dung của ô này. Vì vậy, người ta có thể phát hiện một cách nhanh chóng nếu hai hình ảnh có các khu vực chung (trong trường hợp chúng được căn chỉnh phù hợp).

Lưu ý: Tôi chỉ cần biết hai hình ảnh (hoặc các bộ phận của chúng) là giống hệt nhau. Đó là, tôi không cần phải phù hợp với hình ảnh tương tự, không cần phải nhận diện tính năng, tương quan và các kỹ thuật DSP khác.

Tôi tự hỏi thuật toán băm ưa thích là gì.

Đối với hình ảnh "chụp ảnh" chỉ XOR-ing tất cả các pixel trong ô lưới là ok nhiều hơn hoặc ít hơn. Xác suất của cùng một giá trị băm cho các hình ảnh khác nhau là khá thấp, đặc biệt là do sự hiện diện của nhiễu (gần như trắng) phá vỡ tất cả các đối xứng tiềm năng. Cộng với quang phổ của hàm băm như vậy có vẻ tốt (bất kỳ giá trị nào có thể với gần như cùng xác suất).

Nhưng một thuật toán ngây thơ như vậy có thể không được sử dụng với đồ họa "nhân tạo". Các pixel giống hệt nhau, các mẫu lặp lại, tính bất biến bù hình học là rất phổ biến đối với các hình ảnh như vậy. XOR-ing tất cả các điểm ảnh sẽ cho 0 cho bất kỳ hình ảnh nào với số lượng pixel giống hệt nhau.

Sử dụng một cái gì đó như CRT-32 có vẻ hơi hứa hẹn, nhưng tôi muốn tìm ra điều gì đó nhanh hơn. Tôi nghĩ về công thức lặp đi lặp lại, mỗi điểm ảnh mới đột biến giá trị hash hiện tại, như thế này:

hashValue = (hashValue * /*something*/ | newPixelValue) % /* huge prime */ 

Làm số nguyên tố modulo lẽ nên đưa ra một sự phân tán tốt, vì vậy mà tôi đang nghiêng về phía tùy chọn này. Nhưng tôi muốn biết nếu có varians tốt hơn.

Xin cảm ơn trước.

Answer 1

Nếu bạn muốn làm cho nó rất nhanh, bạn nên xem xét lấy một tập hợp con ngẫu nhiên của các điểm ảnh để tránh đọc toàn bộ hình ảnh. Tiếp theo, tính toán hàm băm trên chuỗi giá trị tại các pixel đó. Tập hợp con ngẫu nhiên nên được chọn bởi trình tạo số giả ngẫu nhiên xác định với hạt giống cố định để hình ảnh giống hệt nhau tạo ra các tập con giống hệt nhau và do đó các giá trị băm giống hệt nhau.

Điều này sẽ hoạt động tốt ngay cả đối với hình ảnh nhân tạo. Tuy nhiên, nếu bạn có các hình ảnh khác nhau với một số lượng nhỏ pixel, điều này sẽ cho ra các xung đột băm. Lặp lại nhiều hơn cho độ tin cậy tốt hơn. Nếu đó là trường hợp, ví dụ, nếu hình ảnh của bạn thiết lập có khả năng có cặp với một điểm ảnh khác nhau, bạn phải đọc mỗi điểm ảnh để tính toán giá trị băm. Việc kết hợp tuyến tính đơn giản với các hệ số giả ngẫu nhiên sẽ đủ tốt ngay cả đối với hình ảnh nhân tạo.

pseudo-code của một thuật toán đơn giản

Random generator = new generator(2847) // Initialized with fixed seed 
int num_iterations = 100 

int hash(Image image) { 
    generator.reset() //To ensure consistency on each evaluation 
    int value = 0 
    for num_iteration steps { 
     int nextValue = image.getPixel(generator.nextInt()%image.getSize()).getValue() 
     value = value + nextValue*generator.nextInt() 
    } 
    return value 
} 

Answer 2

Hãy nhìn vào hướng dẫn này trên các thuật toán phash http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html được sử dụng để tìm phù hợp chặt chẽ hình ảnh.