ตรวจหาภาพซ้ำด้วย Perceptual hashing

Jun 17, 2019

Introduction

ในปัจจุบันเป็นยุคของ Big data ทำให้มีข้อมูลมากมายมหาศาลหลายรูปแบบ ซึ่ง รูปภาพ (Image) เป็นหนึ่งในข้อมูลที่มีหลายรูปแบบที่ได้รับความสนใจมาก เนื่องจากสามารถนำมาเป็นข้อมูลเพื่อประยุกต์ในงานได้อย่างหลากหลาย เช่น Image classification, Object detection แต่ก่อนที่จะนำข้อมูลนั้นมาใช้ มีสิ่งหนึ่ง ที่ไม่ควรมองข้าม นั่นคือ Data cleansing

Data Cleansing

คือ กระบวนการที่ใช้ในการตรวจสอบ รวมถึงแก้ไขข้อมูลที่ไม่ถูกต้อง เช่น Standardization แต่ในบทความนี้จะขอกล่าวถึงเรื่อง Detecting duplicate data โดยเป็น data ประเภทรูปภาพ

Detecting Duplicate Images

ปกติการหาข้อมูลที่ซ้ำ (Duplicate data) จะทำโดยการนำข้อมูลเหล่านั้นมาเปรียบเทียบความเหมือนกันได้ เช่น ข้อมูลประเภทข้อความ (Text) แต่ในกรณีของรูปภาพ จะไม่สามารถนำมาเปรียบเทียบกันตามปกติได้ เพราะ รูปภาพเกิดจากตัวเลข เช่น ภาพประเภท RGB ซึ่งมี 3 channels แต่ละ channel ก็จะมีตัวเลขอยู่หลายตัว ดังนั้นการเปรียบเทียบจึงต้องใช้ตัวเลขในภาพเหล่านั้น

Cryptographic hashing algorithms

ส่วนใหญ่จะใช้ในการตรวจสอบความถูกต้องของข้อมูล (Checksum) ซึ่งมีหลาย algorithms ที่น่าจะคุ้นเคยกันดี เช่น MD5, SHA-1 ตัวอย่างเมื่อนำมาใช้กับรูปภาพOriginal (Right) Photo by James Sutton on Unsplash

ทำการหาค่า hash ของ 2 ภาพนี้ โดยใช้ MD5

import hashlibimage_file = open('./cat.jpg', 'rb').read()
md5hash = hashlib.md5(image_file).hexdigest()
print(md5hash)

ผลลัพธ์ที่ได้ คือ

• ภาพด้านซ้าย (Grayscale): 53aa205b4b7eeed9f1dfddae92a76032

• ภาพด้านขวา (Original): 141a737df0de97ac414fd960a7003785

จากผลลัพธ์จะเห็นว่าค่า hash ที่ได้มีความแตกต่างกันมาก ซึ่งเป็นผลมาจาก Avalanche effect (Input data เปลี่ยนเพียงเล็กน้อย จะทำให้ Output data เปลี่ยนจากเดิมอย่างมาก) จึงไม่ถือว่าเป็น duplicate images

แต่ในงานบางประเภท เช่น Image classification ควรจะถือว่า 2 ภาพนี้เป็น duplicate images การใช้ Cryptographic hashing algorithms จะนำไปสู่ปัญหา เพราะไม่สามารถแยกได้ว่าภาพนี้ใกล้เคียงหรือเหมือนกัน จึงควรเปลี่ยนมาใช้สิ่งที่เรียกว่า Perceptual hashing algorithms

Perceptual hashing algorithms

เป็นสิ่งที่ใช้ในการหาร่องรอย (Fingerprint) ของ multimedia ต่างๆ รวมถึงรูปภาพด้วย โดย Perceptual hashing จะให้ค่า hash ที่คล้ายกัน (Analogous) ถ้ารูปภาพมีความคล้ายเคียงกัน แตกต่างจาก Cryptographic hashing ที่ให้ค่า hash ต่างกันอย่างมาก เนื่องจากผลของ Avalanche effect

Perceptual hashing มีหลายประเภท เช่น Average hash (aHash), Difference hash (dHash), Perceptual (DCT) hash (pHash), Wavelet hash (wHash) เมื่อใช้ Perceptual hash functions เหล่านี้ในการหาค่า hash ของภาพ จะสามารถนำค่า hash ที่ได้มาเทียบกันเพื่อหาความคล้ายคลึง (Similarity) ของภาพได้ โดยใช้ Hamming distance (นับจำนวน bits ที่ต่าง) ซึ่งถ้าได้เท่ากับ 0 แล้วว่าเป็นภาพเดียวกัน และถ้ายิ่งได้ค่าน้อย แสดงว่าภาพเหล่านั้นมีความใกล้เคียงกัน

ในบทความนี้จะขอกล่าวรายละเอียดของ pHash เท่านั้น โดยมีขั้นตอนคร่าวๆ ดังนี้ เริ่มแรกทำการ resize ภาพให้มีขนาด 32x32 pixels ต่อมาทำการ convert ภาพเป็น grayscale แล้วนำ matrix ที่ได้มาผ่าน Discrete Cosine Transform (DCT) โดย apply DCT ทีละ row เมื่อทำเสร็จจึง apply DCT ทีละ column หลังจากนั้นจะใช้ ค่า 8x8 pixels มุมบนซ้ายใน matrix มาคำนวณค่า hash โดยเทียบระหว่างค่าใน 8x8 pixels ทีละ pixel กับค่ามัธยฐาน (Median) ตัวอย่างเมื่อนำมาใช้กับรูปภาพ (ด้านบน)

ทำการหาค่า hash ของ 2 ภาพนี้ โดยใช้ pHash

from PIL import Image
import imagehashimage_file = Image.open('./cat.jpg')
phash = imagehash.phash(image_file)
print(phash)

ผลลัพธ์ที่ได้ คือ

• ภาพด้านซ้าย (Grayscale): ebac95d234638969

• ภาพด้านขวา (Original): ebac95d236238969

จากผลลัพธ์จะเห็นว่าค่า hash ทั้ง 2 ค่ามีความใกล้เคียงกัน ซึ่งเราสามารถใช้ค่าเหล่านี้ในการหาความคล้ายกันระหว่างภาพ (Image similarity) โดยคิด Hamming distance ได้ดังนี้

import imagehashgs_hash = imagehash.hex_to_hash('ebac95d234638969')
ori_hash = imagehash.hex_to_hash('ebac95d236238969')
print('Hamming distance:', gs_hash - ori_hash)

จะได้ผลลัพธ์คือ Hamming distance: 2

ซึ่งแสดงว่าภาพใกล้เคียงกันมาก โดยเราสามารถตั้ง threshold ค่าหนึ่ง เพื่อใช้ในการแยกได้ เช่น ตั้ง threshold = 10 ถ้าค่า Hamming distance มีค่าต่ำกว่า 10 จะถือว่าเป็น duplicate images

Conclusion

จะเห็นว่า Perceptual hashing เป็นวิธีที่เหมาะสมในการตรวจหาภาพซ้ำ รวมถึงภาพที่คล้ายเคียงกันได้อย่างมีประสิทธิภาพ

สุดท้ายนี้ เนื่องจากเป็นบทความแรก ถ้าผิดพลาดประการใด ก็ขออภัยด้วย มีข้อคิดเห็นอย่างไร ก็พูดคุยกันได้ครับ ขอบคุณครับ

References

• https://en.wikipedia.org/wiki/Cryptographic_hash_function

• https://en.wikipedia.org/wiki/Perceptual_hashing

• https://en.wikipedia.org/wiki/Hamming_distance

• https://tech.okcupid.com/evaluating-perceptual-image-hashes-okcupid

• http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html

• https://jenssegers.com/61/perceptual-image-hashes

ที่มาบทความ : https://blog.datawow.io