Video học lập trình mỗi ngày

Thuật toán tìm kiếm hình ảnh đã được google trình làng vào năm 2010, tuy nhiên không chỉ riêng google làm được điều này mà còn rất nhiều nền tảng khác cũng có thể giúp bạn như tineye. Nhưng cái mà chúng ta quan tâm đến đó chính là thuật toán của họ. Vậy trong bài viết này chúng ta sẽ tìm hiểu các bước để tìm ra thuật toán này. 

Trước khi chúng ta đi vào phân tích thì nên nhớ rằng "Cấu trúc dữ liệu và thuật toán" tại sao nên học từ những ngày đầu tiên. Ngắn gọn thôi, google đứng lên hàng vạn những công ty khác là nhờ ban đầu họ có một thuật toán đó là pagerank. Nên nhớ là vậy, tôi có những bài viết về thuật toán vào năm 2021 nếu bạn có hứng thú thì xem qua. 

Bạn nhập URL của một trang web hoặc tải lên một bức ảnh trực tiếp và Google sẽ tìm thấy những bức ảnh tương tự. Hình dưới đây là nữ diễn viên người Mỹ Alyson Hannigan. 

Sau khi tải lên, Google trả về các kết quả sau: 

Nguyên lý của kỹ thuật tìm kiếm bằng hình ảnh?

Câu hỏi đó là "Làm sao để biết rằng hai hình đó là giống nhau"? Ai cũng hỏi được, nhưng ai là người giải đáp đây. Đọc tiếp xem sao. Theo giải thích của Tiến sĩ Neal Krawetz, nguyên tắc này rất đơn giản và dễ hiểu. Chúng ta có thể sử dụng một thuật toán nhanh để đạt được hiệu quả nhất có thể như sau: 

Lưu ý: Vì đây là một bản hiểu về thuật toán nên những câu chứ đôi khi có ngữ nghĩa về toán học, khô cằn cho nên thông cảm về sự mượt mà như văn chương.

Công nghệ quan trọng ở đây được gọi là "thuật toán băm" (Perceptual hash algorithms) dịch khó hiểu lắm :D, chức năng của nó là tạo ra một chuỗi "dấu vân tay" cho mỗi bức ảnh, sau đó so sánh dấu vân tay của các bức ảnh khác nhau. Kết quả càng gần thì các bức tranh càng giống nhau. Từ từ đừng nóng, để giải thích thêm. Và đây là cách triển khai đơn giản nhất:

Thuật toán tìm kiếm bằng hình ảnh theo các bước sau

Bước đầu tiên là giảm kích thước. 

Giảm hình ảnh xuống kích thước 8x8, tổng cộng 64 pixel. Chức năng của bước này là loại bỏ các chi tiết của bức tranh và chỉ giữ lại các thông tin cơ bản như cấu trúc, ánh sáng và bóng râm, đồng thời loại bỏ sự khác biệt trong các bức ảnh do các kích thước và tỷ lệ khác nhau gây ra. 

Bước thứ hai là đơn giản hóa màu sắc. 

Chuyển đổi hình ảnh đã giảm thành thang độ xám 64 cấp. Nói cách khác, chỉ có 64 màu cho tất cả các pixel. 

Bước thứ ba là tính giá trị trung bình. 

Tính giá trị trung bình của màu xám của tất cả 64 pixel. 

Bước thứ tư là so sánh mức độ xám của các pixel. 

So sánh mức xám của mỗi pixel với giá trị trung bình. Giá trị lớn hơn hoặc bằng giá trị trung bình được ghi là 1; giá trị nhỏ hơn giá trị trung bình được ghi là 0. 

Bước thứ năm là tính toán giá trị băm. 

Kết hợp các kết quả so sánh của bước trước để tạo thành một số nguyên 64-bit, chình là dấu vân tay của bức tranh này. Thứ tự của sự kết hợp không quan trọng, miễn là tất cả các hình ảnh theo cùng một thứ tự. 

Sau khi lấy được dấu vân tay, bạn có thể so sánh các bức ảnh khác nhau để xem 64 bit khác nhau bao nhiêu bit. Về lý thuyết, điều này tương đương với việc tính toán dựa trên thuật toán "khoảng cách Hamming". Nếu các bit dữ liệu khác nhau không vượt quá 5, có nghĩa là hai hình ảnh rất giống nhau; nếu lớn hơn 10, có nghĩa là chúng là hai hình ảnh khác nhau.

So sánh hai hình ảnh giống nhau - Source Code

Mã cụ thể để đạt được, có thể được tìm thấy trong reddit với ngôn ngữ python được viết bới imgHash.py . Mã này rất ngắn, chỉ có 53 dòng. Khi được sử dụng, tham số đầu tiên là ảnh tham chiếu và tham số thứ hai là thư mục nơi các ảnh khác được sử dụng để so sánh. Kết quả trả về là số bit dữ liệu khác nhau (khoảng cách Hamming) giữa hai ảnh.

#!/usr/bin/python

import glob
import os
import sys

from PIL import Image

EXTS = 'jpg', 'jpeg', 'JPG', 'JPEG', 'gif', 'GIF', 'png', 'PNG'

def avhash(im):
    if not isinstance(im, Image.Image):
        im = Image.open(im)
    im = im.resize((8, 8), Image.ANTIALIAS).convert('L')
    avg = reduce(lambda x, y: x + y, im.getdata()) / 64.
    return reduce(lambda x, (y, z): x | (z << y),
                  enumerate(map(lambda i: 0 if i < avg else 1, im.getdata())),
                  0)

def hamming(h1, h2):
    h, d = 0, h1 ^ h2
    while d:
        h += 1
        d &= d - 1
    return h

if __name__ == '__main__':
    if len(sys.argv) <= 1 or len(sys.argv) > 3:
        print "Usage: %s image.jpg [dir]" % sys.argv[0]
    else:
        im, wd = sys.argv[1], '.' if len(sys.argv) < 3 else sys.argv[2]
        h = avhash(im)

        os.chdir(wd)
        images = []
        for ext in EXTS:
            images.extend(glob.glob('*.%s' % ext))

        seq = []
        prog = int(len(images) > 50 and sys.stdout.isatty())
        for f in images:
            seq.append((f, hamming(avhash(f), h)))
            if prog:
                perc = 100. * prog / len(images)
                x = int(2 * perc / 5)
                print '\rCalculating... [' + '#' * x + ' ' * (40 - x) + ']',
                print '%.2f%%' % perc, '(%d/%d)' % (prog, len(images)),
                sys.stdout.flush()
                prog += 1

        if prog: print
        for f, ham in sorted(seq, key=lambda i: i[1]):
            print "%d\t%s" % (ham, f)

Ưu điểm của thuật toán này là đơn giản và nhanh chóng, không bị ảnh hưởng bởi kích thước của bức tranh, nhược điểm là không thể thay đổi nội dung của bức tranh. Nếu bạn thêm một vài từ vào hình ảnh, nó sẽ không được nhận dạng. Do đó, cách sử dụng tốt nhất của nó là tìm hình ảnh gốc dựa trên hình thu nhỏ. 

Đây không phải là bản gốc, những bản gốc và tham chiếu được link ở trong bài viết. Xin tham khảo. cảm ơn!