Fast Transposing Matrix Algorithm for FPU Data

[guga]

Para objetos semelhantes ele aponta qual o percentual mas...entre laranjas e mexericas...kkk.. não sei..bem pensado. É algo à se testar.

O link da demonstração online do phash é:
http://www.phash.org

tenta selecionar foto de laranjas e mexericas etc e ve qual o resultado que o phash encontrou. Se ele conseguir discernir mesmo entre uma laranja e uma mexerica etc, nossa...então o algoritmo é melhor do que pensei :)

[guga]

Aliás...o que já consegui portar foi a função hamming Distance do phash. Apesar de eu achar um pouco lenta, pelo menos já consegui portar. Assim vou fazendo aos poucos para facilitar a otimização quando tudo ficar pronto.

A biblioteca tb tem uma função para calcular o Fast Fourier Transformation. Eu converti ela e posto mais tarde para tentarmos otimizar :)

Code Select Expand


[XValue: Q$ 0]

Proc ph_hamming_distance:
    Arguments @Hash1, @Hash2
    Uses ecx, edx, esi, edi

    mov edi D@Hash1
    mov esi D@Hash2
    mov eax D$edi | xor eax D$esi | mov D$XValue eax
    mov ecx D$edi+4 | xor ecx D$esi+4 | mov D$XValue+4 ecx

    call aullshr 1, D$XValue, D$XValue+4

    and eax 055555555 | and edx 055555555
    mov ecx D$XValue | sub ecx eax | mov D$XValue ecx
    mov eax D$XValue+4 | sbb eax edx | mov D$XValue+4 eax

    mov esi D$XValue | and esi 033333333
    mov edi D$XValue+4 | and edi 033333333

    call aullshr 2, D$XValue, D$XValue+4
    and eax 033333333 | add esi eax | mov D$XValue esi
    and edx 033333333 | adc edi edx | mov D$XValue+4 edi

    call aullshr 4, D$XValue, D$XValue+4
    add eax D$XValue
    mov ecx D$XValue+4 | adc ecx edx
    and eax 0F0F0F0F | mov D$XValue eax
    and ecx 0F0F0F0F | mov D$XValue+4 ecx

    call allmul D$XValue, D$XValue+4, 01010101, 01010101
    call aullshr 56, eax, edx

EndP


; results in eax/edx

Code Select Expand


Proc aullshr:
    Arguments @Flag, @Val1, @Val2
    Uses ecx

    mov ecx D@Flag | movzx ecx cl
    mov eax D@Val1
    mov edx D@Val2

    .If cl < 040
        If cl < 020
            shrd eax edx cl
            shr edx cl
        Else
            mov eax edx
            xor edx edx
            and cl 01F
            shr eax cl
        End_If
    .Else
        xor eax eax
        xor edx edx
    .End_If

EndP

___________________________________________________________________________________

Code Select Expand

Proc allmul:
    Arguments @Val1, @Val1a, @Val2, @Val2a
    Uses ebx

    mov eax D@Val1a
    If D@Val2a = eax
        mov eax D@Val1
        mul D@Val2
    Else
        mul D@Val2
        mov ebx eax
        mov eax D@Val1
        mul D@Val2a
        add ebx eax
        mov eax D@Val1
        mul ecx
        add edx ebx
    End_If

EndP

[mineiro]

Irei tentar o site amanhã e me aprofundar no assunto, gosto de alimento cerebral.
Creio que já tenha visto neste fórum uma função fft rápida, esqueci agora qual usuário a fez, talvez no velho fórum.
abraços dom.

[guga]

Não vi ainda mas, se foi criada, creio que possa ter sido ou pelo JJ ou por Siekmanski . Ambos são ótimos quando o assunto é otimização de código :)

[LordAdef]

doideira, não conhecia isso. Interessante

[guga]

Oi Lord

Sim, é muto interessante a técnica. No entanto, phash utiliza uma biblioteca tosca de manipulação de imagem chamada CImg que é incrivelmente lenta e confusa de portar.

Estou tentando portar ela para assembly e tentando entender direito a funcionalidade. basicamente, eles utilizam uma máscara por cima de uma imagem. A máscara é invertida (transposta mas, não do modo 'normal". A transposição se dá fazendo um flip horizontal e outro vertical da máscara) e depois passam essa máscara por sobre a imagem aplicando uma convolação de matrix. Antes da convolação e do flip, a imagem e a máscara precisam ser convertidas para greyscale (Eu vou usar Luma que é mais preciso).

Eu havia criado uma dll do pHash que tem as funções de exportação necessárias "ph_dct_imagehash" e "ph_hamming_distance" mas, após testar elas quanto à velocidade, é impraticável para usá-las em vídeo, por exemplo.

Exatamente por isso que estou otimizando e tentando rever toda a funcionalidade da biblioteca para fazê-la simplificada sem a necessidade de se utilizar biblioteca externa de manipulação de imagens. A idéia é apenas recriar as funções do pHash tomando como base os pixels já convertidos para Luma (normalizado) e apenas aplicar as alterações necessárias das matrizes e a convolação.

Isso garantirá uma maior rapidez do algoritmo. Se eu conseguir criar uma função que consiga criar o phash de uma imagem (e identificar com o de outro) utilizando apenas alguns nanosegundos, será melhor. Acredito que a função como um todo, talvez se consiga fazer em torno de uns 800 nanosegundos (para uma imagem de 32x32, por exemplo), já incluindo a convolação.  Ou seja, uma imagem de 640x480 pode ser feita em algo que leve alguns poucos microsegundos. (Creio que uns 10 no máximo 20 mas, quanto menos, melhor).

Eu conseguindo isolar apenas o algoritmo de phash, já é um avanço pois se alguém quiser criar um programa de identificação de cenas (como eu estou fazendo) ou de busca por imagens etc, a velocidade final dependerá apenas da forma como o programador  usou para ter acesso aos pixels antes de passar pelo algoritmo e nunca em função do algoritmo em si (Que é o que acontece com o phash  atualmente)