Newsgroup: it.comp.java
Titolo: Differenza tra 2 immagini : CRC-32 , è una buona strada ?

Salve a tutti ,
volendo determinare se due BufferedImage sono uguali oppure no ,
avevo pensato di operare nel seguente modo , ma vorrei sapere
qualche vostro parere se è una strada giusta oppure no :
1. Prendo le 2 BufferedImage
2. Ricavo il loro OutPutStream in formato JPG
3. Calcolo il CRC-32 con i bytes di entrambi gli OutPutStream
4. Se i CRC sono uguali , allora le immagini sono uguali
5. Se i CRC sono diversi , allora le immagini sono diverse
secondo voi , esiste una strada migliore di questa ?
grazie a tutti ,
max


io userei MD5 o SHA1 in quanto vengono normalmente usati proprio a
questo scopo (vedi hash normalmente associati alle immagini iso da
scaricare dalla rete).
C'e' pero' da dire che esiste comunque una piccola possibilita' che due
immagini diverse ti diano lo stesso hash. Inoltre per calcolare il CRC o
l'hash devi sempre processare tutti i byte delle due immagini... non e'
allora piu' conveniente fare un confronto pixel per pixel e fermarti
appena trovi un pixel diverso? Tra l'altro non avresti nemmeno
l'incertezza data dai precedenti  metodi.
ciao
-- 
Seti@Home Java Applets
http://maruko.webhop.net/

 l'incertezza data dai precedenti  metodi.
si , ma il problema è che se mai non esistano differenze il confronto
elaborerà tutti i pixel !
Ed a questo punto avevo pensato che forse era meglio un CRC-32 ...
mi sbaglio ?
max

mi sbaglio ?
e il CRC su cosa lo calcoli scusa? su mezza immagine?


> e il CRC su cosa lo calcoli scusa? su mezza immagine?
No , sinceramente pensavo che il confronto "int" per "int" (rgb per rgb)
fosse più lento di un calcolo CRC .
max



capisco... mi sa che ti tocca fare delle prove.
Ho notato che il calcolo del CRC32 e, forse,  di MD5 e SHA1 sono in
codice nativo quindi potresti recuperare qualcosa... forse.
In ogni caso come pensi di risolvere la collisione tra due immagini
diverse sullo stesso CRC?


> diverse sullo stesso CRC?
Ma come fanno due byte[] di 2 immagini diverse a dare lo stesso CRC ?
Cioč , basterebbe anche getRGB() diverso tra le 2 per far scattare il CRC
diverso : o sbaglio ?
Sto provando a fare il controllo pixel-by-pixel ma la mia CPU č a quota 90%
su 2 immagini
1024x768 .
max

diverso : o sbaglio ?
Sbagli. Devi usare un algoritmo collision resistant (o collision proof),
e CRC32 non lo e'. Cosi' come non credo lo siano MD5 e SHA1 ma non ci
metterei la mano sul fuoco.


 immagini diverse ti diano lo stesso hash.
Dalla relativa RFC leggo:
"It is conjectured that it is computationally infeasible to produce
two messages having the same message digest, or to produce any
message having a given prespecified target message digest."
(cit. 
http://www.faqs.org/rfcs/rfc1321.html
)
Interessa anche a me questo aspetto, hai per caso dei riferimenti 
matematici che evidenzino la cosa?
-- 
daniele


Quello che intendo io da quanto scritto e' questo:
a partire da un hash MD5 noto si puo' supporre che e' computazionalmente
impossibile creare un messaggio che dia tale hash.
Non dice che e' impossibile che due messaggi diano lo stesso hash dice
che e' "impossibile" creare un messaggio che dia l'hash voluto.
Cioe' e' una funzione difficile da invertire.
comunque dice anche:
"It is conjectured that the difficulty of coming up with two messages
having the same message digest is on the order of 2^64 operations,
and that the difficulty of coming up with any message having a given
message digest is on the order of 2^128 operations."
quindi, la possibilita' di avere 2 immagini con lo stesso hash esiste,
remota, ma esiste.
bisogna vedere se l'applicazione in questione puo' risentirne e bisogna
vedere, soprattutto, se e' meno costoso che il confronto byte a byte. Mi
sembra che l'algoritmo di calcolo sia un po' piu' complesso che un
confronto tra due byte...


 confronto tra due byte...
Ho fatto il confronto ,
la cpu č scesa a 10% ma invece di fare un confronto pixel per pixel salto i
PIXEL 2 alla volta .
MD5 e CRC-32 non mi servono piů , mi basta ed avanza la cpu a 10% anche
perchč č improbabile
che venga fatta la modifica in modo cosi piccolo (2 pixel) .
Ad ogni modo ,
ma perchč non riesco a catturare il mouse sullo schermo !???
faccio screen shoot ma non viene fuori ,
devo per caso "spalmarlo" sull'immagine che catturo ?
Non esiste un metodo che ritorni la posizione del mouse FUORI una finestra
Java
oppure la bitmap del mouse ?
max

 remota, ma esiste.
Pare di si...
-- 
daniele

 fosse più lento di un calcolo CRC .
No, è indubbiamente più veloce.
L'operatore "==" fa una singola istruzione assembler, un calcolo di un 
CRC ne usa parecchie di operazioni base.
Inoltre per calcolare il CRC devi comunque scorrerti tutta l'immagine, 
non ha senso che opssa essere più rapido...
-- 
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it

 non ha senso che opssa essere più rapido...
Si ,
pensavo solo che il CRC lavorasse ad un livello più "basso" tale da
permettere
un accelerazione .
Anche perchè "pixel-by-pixel" richiede comunque di "recuperare" quel
maledetto pixel ,
il ciclo FOR implementato in Java sarà sicuramente inferiore a quello del
CRC ,etcetc...
Ho testato ,
ed effettivamente il CRC è veramente un mattone rispetto al controllo
pixel-by-pixel .
grazie mille ,
max

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Max wrote:
| Si ,
| pensavo solo che il CRC lavorasse ad un livello più "basso" tale da
| permettere
| un accelerazione .
Lo pensavo anche io, prima di notare che la mia implemetnaizone
Java-only di SHA1 è *molto* più veloce di quella "nativa" del JCE...
(probabilmente semplicemente perché un ciclo SHA1 è molto breve e la mia
libreria specifica non ha alcun overhead che invece la super-generica
JCE ha...)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAkA72t4ACgkQaJiCLMjyUvv5vgCgoLjfRm7PBoYG0F0IvIgz4HlR
A4IAoOIz0KmekmuicuHO4oYDQy+mXpbF
=E3xk
-----END PGP SIGNATURE-----