ImageHash module

Kwai chang caine · Post by **Kwai chang caine** » Wed Jan 22, 2014 6:00 pm

Never mind, if you cannot do better...you have already much worked

They are only some day, never i believe have a so better result

I'm already happy to this result

It's funny to see, the difference of the two pictures whith this error

At the beginning, when i have searching what is the pictures who put problem, i'm sure it's picture nearly similar...same color, etc..
And in fact no..the picture have nearly nothing to see, between her

Aaaahhh !!! KCC never understand the PC

Again thanks for all your great and precious help

wilbert · Post by **wilbert** » Fri Jan 24, 2014 11:55 am

@KCC,
Here's a different (ASM optimized) version you can try.
It uses a 24x24 matrix instead of 32x32 to reduce calculations.
http://www.purebasic.fr/english/viewtop ... 35#p436035

Kwai chang caine · Post by **Kwai chang caine** » Fri Jan 24, 2014 3:25 pm

Thanks a lot WILBERT i try this week end

I understand nothing...but it's very nice all this red hieroglyph

wilbert · Post by **wilbert** » Fri Jan 24, 2014 8:29 pm

Kwaï chang caïne wrote:Thanks a lot WILBERT i try this week end
I understand nothing...but it's very nice all this red hieroglyph

A little information, from the YIQ color space ( http://en.wikipedia.org/wiki/YIQ ), the human eye is most sensitive to Y, then I and least sensitive to Q.
If you would want to use two hashes from this model, it would make sense to use Y and I.

Kwai chang caine · Post by **Kwai chang caine** » Fri Jan 24, 2014 9:13 pm

wilbert · Post by **wilbert** » Sat Jan 25, 2014 7:44 am

Here's again an improved version.
Since computing the hash itself is really fast and loading and resizing is slow, I created a YIQhash structure so the hashes for all three channels can be computed at once.
I and Q contain color information so if you compare two grayscale images with each other, the total Hamming distance for YIQ is much lower compared to comparing two color images.
When a border is specified, the border of the image is ignored. When setting it to 1, the image is cropped to about 92% before computing a hash.
YIQhashToString and YIQhashFromString convert the YIQhash structure to and from a 48 character hex string.

Code: Select all

DeclareModule npHash; v0.1.6 (SSE)
  
  Structure YIQhash
    Y.q
    I.q
    Q.q
  EndStructure
  
  Declare.s YIQhashToString(*Hash.YIQhash)
  Declare   YIQhashFromString(YIQhashString.s, *Hash.YIQhash)
  Declare.i HammingDistance(Hash1.q, Hash2.q)                       ; Hamming distance
  Declare.i HammingDistanceYIQ(*Hash1.YIQhash, *Hash2.YIQhash)      ; Combined YIQ Hamming distance
  Declare.i MaxHammingDistanceYIQ(*Hash1.YIQhash, *Hash2.YIQhash)   ; Max Hamming Distance from Y,I and Q
  Declare   ImageHash(Image.i, *Hash.YIQhash, Border = 0)
  Declare   FileHash(ImageFile.s, *Hash.YIQhash, Border = 0)
  
EndDeclareModule

Module npHash
  
  UseJPEGImageDecoder()
  UsePNGImageDecoder()
  
  ; *** Hamming distance ***
  
  Procedure.i HammingDistance(Hash1.q, Hash2.q)
    !mov ecx, [p.v_Hash1]
    !xor ecx, [p.v_Hash2]
    !mov edx, ecx
    !shr edx, 1
    !and edx, 0x55555555
    !sub ecx, edx
    !mov edx, ecx
    !shr edx, 2
    !and edx, 0x33333333
    !and ecx, 0x33333333
    !add ecx, edx
    !mov edx, ecx
    !shr edx, 4
    !add ecx, edx
    !and ecx, 0x0f0f0f0f
    !imul eax, ecx, 0x01010101
    !shr eax, 24
    !mov ecx, [p.v_Hash1 + 4]
    !xor ecx, [p.v_Hash2 + 4]
    !mov edx, ecx
    !shr edx, 1
    !and edx, 0x55555555
    !sub ecx, edx
    !mov edx, ecx
    !shr edx, 2
    !and edx, 0x33333333
    !and ecx, 0x33333333
    !add ecx, edx
    !mov edx, ecx
    !shr edx, 4
    !add ecx, edx
    !and ecx, 0x0f0f0f0f
    !imul ecx, 0x01010101
    !shr ecx, 24
    !add eax, ecx
    ProcedureReturn
  EndProcedure
  
  Macro M_HammingDistance(mm_reg)
    !movq mm3, mm_reg
    !psrlq mm3, 1
    !pand mm3, mm5
    !psubb mm_reg, mm3
    !movq mm3, mm_reg
    !psrlq mm3, 2
    !pand mm_reg, mm6
    !pand mm3, mm6
    !paddb mm_reg, mm3
    !movq mm3, mm_reg
    !psrlq mm3, 4
    !paddb mm_reg, mm3
    !pand mm_reg, mm7
  EndMacro
  
  Macro M_HammingDistanceYIQ
    CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
      !mov rcx, [p.p_Hash1]
      !mov rdx, [p.p_Hash2]
      !movq mm0, [rcx]
      !movq mm1, [rcx + 8]
      !movq mm2, [rcx + 16]
      !pxor mm0, [rdx]
      !pxor mm1, [rdx + 8]
      !pxor mm2, [rdx + 16]
    CompilerElse
      !mov ecx, [p.p_Hash1]
      !mov edx, [p.p_Hash2]
      !movq mm0, [ecx]
      !movq mm1, [ecx + 8]
      !movq mm2, [ecx + 16]
      !pxor mm0, [edx]
      !pxor mm1, [edx + 8]
      !pxor mm2, [edx + 16]
    CompilerEndIf
    !pxor mm4, mm4
    !mov eax, 0xf3355
    !movd mm7, eax
    !punpcklbw mm7, mm7
    !pshufw mm5, mm7, 00000000b ; mm5 = 0x55555555
    !pshufw mm6, mm7, 01010101b ; mm6 = 0x33333333
    !pshufw mm7, mm7, 10101010b ; mm7 = 0x0f0f0f0f
    M_HammingDistance(mm0)    
    M_HammingDistance(mm1)    
    M_HammingDistance(mm2)  
  EndMacro  
  
  Procedure.i HammingDistanceYIQ(*Hash1.YIQhash, *Hash2.YIQhash)
    CompilerIf #PB_Compiler_Debugger
      If *Hash1 = 0 Or *Hash2 = 0
        RaiseError(#PB_OnError_InvalidMemory)
      EndIf
    CompilerEndIf
    M_HammingDistanceYIQ
    !paddb mm0, mm1
    !paddb mm0, mm2
    !psadbw mm0, mm4
    !movd eax, mm0
    !emms
    ProcedureReturn
  EndProcedure
  
  Procedure.i MaxHammingDistanceYIQ(*Hash1.YIQhash, *Hash2.YIQhash)
    CompilerIf #PB_Compiler_Debugger
      If *Hash1 = 0 Or *Hash2 = 0
        RaiseError(#PB_OnError_InvalidMemory)
      EndIf
    CompilerEndIf
    M_HammingDistanceYIQ
    !psadbw mm0, mm4
    !psadbw mm1, mm4
    !psadbw mm2, mm4
    !pmaxub mm0, mm1
    !pmaxub mm0, mm2
    !movd eax, mm0
    !emms
    ProcedureReturn
  EndProcedure
  
  ; *** npHash ***
  
  Global *DCT24Partial = AllocateMemory(784) & -16 + 16 ; create an aligned verison of the data
  CopyMemory(?DCT24Partial, *DCT24Partial, 768)
  
  DataSection
    DCT24Partial:
    !dd 0x3e937c37,0x3e90f632,0x3e8bf536,0x3e848f2d,0x3e75c902,0x3e5e3f11,0x3e42e7a2,0x3e243a79,0x3e02bdf4,0x3dbe0983,0x3d66ad6a,0x3c9aaac5
    !dd 0xbc9aaac5,0xbd66ad6a,0xbdbe0983,0xbe02bdf4,0xbe243a79,0xbe42e7a2,0xbe5e3f11,0xbe75c902,0xbe848f2d,0xbe8bf536,0xbe90f632,0xbe937c37
    !dd 0x3e928986,0x3e888d0a,0x3e6a8495,0x3e33f3b0,0x3de23eb8,0x3d1a55fe,0xbd1a55fe,0xbde23eb8,0xbe33f3b0,0xbe6a8495,0xbe888d0a,0xbe928986
    !dd 0xbe928986,0xbe888d0a,0xbe6a8495,0xbe33f3b0,0xbde23eb8,0xbd1a55fe,0x3d1a55fe,0x3de23eb8,0x3e33f3b0,0x3e6a8495,0x3e888d0a,0x3e928986
    !dd 0x3e90f632,0x3e75c902,0x3e243a79,0x3d66ad6a,0xbd66ad6a,0xbe243a79,0xbe75c902,0xbe90f632,0xbe90f632,0xbe75c902,0xbe243a79,0xbd66ad6a
    !dd 0x3d66ad6a,0x3e243a79,0x3e75c902,0x3e90f632,0x3e90f632,0x3e75c902,0x3e243a79,0x3d66ad6a,0xbd66ad6a,0xbe243a79,0xbe75c902,0xbe90f632
    !dd 0x3e8ec3f4,0x3e5105eb,0x3d9903fb,0xbd9903fb,0xbe5105eb,0xbe8ec3f4,0xbe8ec3f4,0xbe5105eb,0xbd9903fb,0x3d9903fb,0x3e5105eb,0x3e8ec3f4
    !dd 0x3e8ec3f4,0x3e5105eb,0x3d9903fb,0xbd9903fb,0xbe5105eb,0xbe8ec3f4,0xbe8ec3f4,0xbe5105eb,0xbd9903fb,0x3d9903fb,0x3e5105eb,0x3e8ec3f4
    !dd 0x3e8bf536,0x3e243a79,0xbc9aaac5,0xbe42e7a2,0xbe90f632,0xbe848f2d,0xbe02bdf4,0x3d66ad6a,0x3e5e3f11,0x3e937c37,0x3e75c902,0x3dbe0983
    !dd 0xbdbe0983,0xbe75c902,0xbe937c37,0xbe5e3f11,0xbd66ad6a,0x3e02bdf4,0x3e848f2d,0x3e90f632,0x3e42e7a2,0x3c9aaac5,0xbe243a79,0xbe8bf536
    !dd 0x3e888d0a,0x3de23eb8,0xbde23eb8,0xbe888d0a,0xbe888d0a,0xbde23eb8,0x3de23eb8,0x3e888d0a,0x3e888d0a,0x3de23eb8,0xbde23eb8,0xbe888d0a
    !dd 0xbe888d0a,0xbde23eb8,0x3de23eb8,0x3e888d0a,0x3e888d0a,0x3de23eb8,0xbde23eb8,0xbe888d0a,0xbe888d0a,0xbde23eb8,0x3de23eb8,0x3e888d0a
    !dd 0x3e848f2d,0x3d66ad6a,0xbe42e7a2,0xbe937c37,0xbe243a79,0x3dbe0983,0x3e8bf536,0x3e75c902,0x3c9aaac5,0xbe5e3f11,0xbe90f632,0xbe02bdf4
    !dd 0x3e02bdf4,0x3e90f632,0x3e5e3f11,0xbc9aaac5,0xbe75c902,0xbe8bf536,0xbdbe0983,0x3e243a79,0x3e937c37,0x3e42e7a2,0xbd66ad6a,0xbe848f2d
    !dd 0x3e800000,0x246550f9,0xbe800000,0xbe800000,0xa52bfcbb,0x3e800000,0x3e800000,0x258f529c,0xbe800000,0xbe800000,0xa5c8a6da,0x3e800000
    !dd 0x3e800000,0x2600fd8c,0xbe800000,0xbe800000,0xa61da7ab,0x3e800000,0x3e800000,0x263a51cb,0xbe800000,0xbe800000,0xa656fbea,0x3e800000
    !nphash.l_rcp64:
    !dd 0x3c800000
  EndDataSection
  
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    
    Macro M_Unrolled_x64
      !movaps xmm0, [r8]
      !mulps xmm0, [r9]
      !movaps xmm1, [r8 + 16]
      !movaps xmm2, [r8 + 32]
      !mulps xmm1, [r9 + 16]
      !mulps xmm2, [r9 + 32]
      !addps xmm0, xmm1
      !addps xmm0, xmm2
      !movaps xmm1, [r8 + 48]
      !movaps xmm2, [r8 + 64]
      !movaps xmm3, [r8 + 80]
      !mulps xmm1, [r9 + 48]
      !mulps xmm2, [r9 + 64]
      !mulps xmm3, [r9 + 80]
      !addps xmm0, xmm1
      !addps xmm0, xmm2
      !addps xmm0, xmm3
      !movhlps xmm1, xmm0
      !addps xmm0, xmm1
      !movaps xmm1, xmm0
      !shufps xmm1, xmm1, 1
      !addss xmm0, xmm1
      !movss [r10], xmm0
      !add r10, 4    
    EndMacro
    
    Procedure.q ComputeHash(*float24x24)
      !mov rdx, [p.p_float24x24]
      ; copy input
      !mov r11, rsp
      !sub rsp, 4608
      !and rsp, -16
      !xor rcx, rcx
      !nphash.l_mov0:
      !movups xmm0, [rdx + rcx]
      !movups xmm1, [rdx + rcx + 16]
      !movaps [rsp + rcx], xmm0
      !movaps [rsp + rcx + 16], xmm1
      !add rcx, 32
      !cmp rcx, 2304
      !jne nphash.l_mov0
      ; multiply matrices and calculate mean value
      !mov r8, [nphash.p_DCT24Partial]
      !lea r10, [rsp + 2304]
      !mov ch, 8
      !nphash.l_calc0:
      !lea r9, [rsp]
      !mov cl, 24
      !nphash.l_calc1:
      M_Unrolled_x64
      !add r9, 96
      !dec cl
      !jnz nphash.l_calc1
      !add r8, 96
      !dec ch
      !jnz nphash.l_calc0
      !xorps xmm4, xmm4
      !lea r9, [rsp + 2304]
      !lea r10, [rsp]
      !mov ch, 8
      !nphash.l_calc2:
      !mov r8, [nphash.p_DCT24Partial]
      !mov cl, 8
      !nphash.l_calc3:
      M_Unrolled_x64
      !addss xmm4, xmm0
      !add r8, 96
      !dec cl
      !jnz nphash.l_calc3
      !add r9, 96
      !add r10, 64
      !dec ch
      !jnz nphash.l_calc2
      !mulss xmm4, [nphash.l_rcp64]
      !shufps xmm4, xmm4, 0
      ; build hash
      !lea r9, [rsp]
      !mov cl, 8
      !nphash.l_calc4:
      !movaps xmm0, [r9]
      !movaps xmm1, [r9 + 16]
      !cmpps xmm0, xmm4, 2
      !cmpps xmm1, xmm4, 2
      !movmskps edx, xmm0
      !shl rax, 4
      !or rax, rdx
      !movmskps edx, xmm1
      !shl rax, 4
      !or rax, rdx
      !add r9, 96
      !dec cl
      !jnz nphash.l_calc4
      !mov rsp, r11
      ProcedureReturn
    EndProcedure
    
  CompilerElse
    
    Macro M_Unrolled_x86
      !movaps xmm0, [eax]
      !mulps xmm0, [ebx]
      !movaps xmm1, [eax + 16]
      !movaps xmm2, [eax + 32]
      !mulps xmm1, [ebx + 16]
      !mulps xmm2, [ebx + 32]
      !addps xmm0, xmm1
      !addps xmm0, xmm2
      !movaps xmm1, [eax + 48]
      !movaps xmm2, [eax + 64]
      !movaps xmm3, [eax + 80]
      !mulps xmm1, [ebx + 48]
      !mulps xmm2, [ebx + 64]
      !mulps xmm3, [ebx + 80]
      !addps xmm0, xmm1
      !addps xmm0, xmm2
      !addps xmm0, xmm3
      !movhlps xmm1, xmm0
      !addps xmm0, xmm1
      !movaps xmm1, xmm0
      !shufps xmm1, xmm1, 1
      !addss xmm0, xmm1
      !movss [edx], xmm0
      !add edx, 4
    EndMacro
    
    Procedure.q ComputeHash(*float24x24)
      !mov edx, [p.p_float24x24]
      ; copy input
      !push ebx
      !push ebp
      !mov ebp, esp
      !sub esp, 4608
      !and esp, -16
      !xor ecx, ecx
      !nphash.l_mov0:
      !movups xmm0, [edx + ecx]
      !movups xmm1, [edx + ecx + 16]
      !movaps [esp + ecx], xmm0
      !movaps [esp + ecx + 16], xmm1
      !add ecx, 32
      !cmp ecx, 2304
      !jne nphash.l_mov0
      ; multiply matrices and calculate mean value
      !mov eax, [nphash.p_DCT24Partial]
      !lea edx, [esp + 2304]
      !mov ch, 8
      !nphash.l_calc0:
      !lea ebx, [esp]
      !mov cl, 24
      !nphash.l_calc1:
      M_Unrolled_x86
      !add ebx, 96
      !dec cl
      !jnz nphash.l_calc1
      !add eax, 96
      !dec ch
      !jnz nphash.l_calc0
      !xorps xmm4, xmm4
      !lea ebx, [esp + 2304]
      !lea edx, [esp]
      !mov ch, 8
      !nphash.l_calc2:
      !mov eax, [nphash.p_DCT24Partial]
      !mov cl, 8
      !nphash.l_calc3:
      M_Unrolled_x86
      !addss xmm4, xmm0
      !add eax, 96
      !dec cl
      !jnz nphash.l_calc3
      !add ebx, 96
      !add edx, 64
      !dec ch
      !jnz nphash.l_calc2
      !mulss xmm4, [nphash.l_rcp64]
      !shufps xmm4, xmm4, 0
      ; build hash
      !lea ebx, [esp]
      !mov cl, 4
      !nphash.l_calc4:
      !movaps xmm0, [ebx]
      !movaps xmm1, [ebx + 16]
      !cmpps xmm0, xmm4, 2
      !cmpps xmm1, xmm4, 2
      !movmskps edx, xmm0
      !shl eax, 4
      !or eax, edx
      !movmskps edx, xmm1
      !shl eax, 4
      !or eax, edx
      !add ebx, 96
      !dec cl
      !jnz nphash.l_calc4
      !mov [esp + 2304], eax
      !mov cl, 4
      !nphash.l_calc5:
      !movaps xmm0, [ebx]
      !movaps xmm1, [ebx + 16]
      !cmpps xmm0, xmm4, 2
      !cmpps xmm1, xmm4, 2
      !movmskps edx, xmm0
      !shl eax, 4
      !or eax, edx
      !movmskps edx, xmm1
      !shl eax, 4
      !or eax, edx
      !add ebx, 96
      !dec cl
      !jnz nphash.l_calc5
      !mov edx, [esp + 2304]
      !mov esp, ebp
      !pop ebp
      !pop ebx
      ProcedureReturn
    EndProcedure
    
  CompilerEndIf
  
  Procedure.s YIQhashToString(*Hash.YIQhash)
    ProcedureReturn RSet(Hex(*Hash\Y), 16, "0") + RSet(Hex(*Hash\I), 16, "0") + RSet(Hex(*Hash\Q), 16, "0")
  EndProcedure
  
  Procedure YIQhashFromString(YIQhashString.s, *Hash.YIQhash)
    If *Hash 
      *Hash\Y = Val("$" + Left(YIQhashString, 16))
      *Hash\I = Val("$" + Mid(YIQhashString, 17, 16))
      *Hash\Q = Val("$" + Right(YIQhashString, 16))
    EndIf
  EndProcedure
  
  Procedure ImageHash(Image.i, *Hash.YIQhash, Border = 0)
    Protected.i img, c, x, y, size = 24 + Border << 1
    Dim float24x24.f(2, 23, 23)
    If *Hash
      *Hash\Y = 0 : *Hash\I = 0 : *Hash\Q = 0
      If IsImage(Image)
        ; fill image matrix
        If ImageWidth(Image) = size And ImageHeight(Image) = size
          StartDrawing(ImageOutput(Image))
        Else
          img = CreateImage(#PB_Any, size, size)
          StartDrawing(ImageOutput(img))
          DrawImage(ImageID(Image), 0, 0, size, size)
        EndIf
        For y = 0 To 23 : For x = 0 To 23 : c = Point(x + Border, y + Border)
            float24x24(0, x, y) = 0.299*Red(c) + 0.587*Green(c) + 0.114*Blue(c); Y
            float24x24(1, x, y) = 0.595716*Red(c) - 0.274453*Green(c) - 0.321263*Blue(c); I
            float24x24(2, x, y) = 0.211456*Red(c) - 0.522591*Green(c) + 0.311135*Blue(c); Q
        Next : Next
        StopDrawing()
        If img : FreeImage(img) : EndIf
        ; set hash
        *Hash\Y = ComputeHash(@float24x24(0, 0, 0))
        *Hash\I = ComputeHash(@float24x24(1, 0, 0))
        *Hash\Q = ComputeHash(@float24x24(2, 0, 0))
      EndIf
    EndIf
  EndProcedure
  
  Procedure FileHash(ImageFile.s, *Hash.YIQhash, Border = 0)
    Protected img.i = LoadImage(#PB_Any, ImageFile)
    If *Hash
      *Hash\Y = 0 : *Hash\I = 0 : *Hash\Q = 0
      If img And ResizeImage(img, 24 + Border << 1, 24 + Border << 1)
        ImageHash(img, *Hash, Border)
        FreeImage(img)
      EndIf
    EndIf
  EndProcedure
  
EndModule

Example:

Code: Select all

UseModule npHash

FileHash(Image1, @Hash1.YIQhash)
FileHash(Image2, @Hash2.YIQhash)
Debug HammingDistanceYIQ(Hash1, Hash2)

Kwai chang caine · Post by **Kwai chang caine** » Tue Jan 28, 2014 9:45 am

Yeeeeeees !!!!!I have testing your super code and that works very well !!!
All pictures similar are radicaly detected

Thanks a lot WILBERT for this jewel of ASM

Remain the problem of rotation, but i know the hash can't do something for that

IDLE code can normally detect the rotation, the two codes together and nothing can resist to KCC thanks to you two

I wish you a very good day

collectordave · Post by **collectordave** » Wed Oct 04, 2017 3:14 pm

Hi All

I am using wilberts solution in an application that checks well over 500,000 images and gives acceptable results when the image to check is vertical and cleaned up a bit.

I am just experimenting with checking the aspect ratio of each image as well.

Both the hash and the aspect are stored in a local database.

My question is is there any code to clean up an image before comparison? i.e. rempove any rotation and or compensate for any brightness introduced from taking a photograph.

kind regards

CD

PureBasic Forums - English

ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module

Re: ImageHash module