Supponiamo di avere due immagini simili come segue
Immagine 1 (base)
Immagine2(obiettivo)
La seconda immagine è fondamentalmente una variazione della prima immagine, tranne che con un ovale verde schiaffeggiato in cima (infatti, ho usato image1 come base per produrre immagine2). Per risparmiare spazio, mi rendo conto che invece di memorizzare due immagini separate, ho semplicemente bisogno di memorizzare la differenza e quindi registrare l'offset, ad esempio, in un file di testo.
Quindi andrei a ritagliare arbitrariamente quell'ovale che voglio, e ho effettivamente rasato 2 KB in totale perché le mie immagini sono a tinta unita, quindi è ben compresso.
Questaè(oera?)unatecnicacomuneusatainvarieapplicazionicomeigiochiperspingereversoilbassoladimensionedelfile,specialmentesesihaunasingolaimmaginecondozzinedivariazioni,maquellevariazionicopronoforseil10%dell'interaimmagine,quindicisonomoltidatiridondanti.Eselavoricon32bppcompleticonunsaccoeunsaccodicoloriovunque,questopuòsommarsiabbastanzarapidamente.
problema
Ilproblemaacuisonointeressatoèquesto:datal'immaginedibase(immagine1)elavariazioneritagliata,unisciliinsiemeinmododafinireconl'immagineoriginale(immagine2)
idee
Selavariazioneritagliatamantienelasuaposizionesemplicementerimuovendotuttiipixelridondanti,ilproblemaègiàrisolto.Tuttavia,nonèsempreilcaso.
Ilmioapprocciosibasaingranpartesulfattochel'immaginedidestinazioneèderivatadall'immaginedibase.Pergliesempisopra,ladifferenzaèunsingoloovaleverde.Datochehoritagliatol'ovalesenzafarealcunosforzoperisolarlodallosfondo,misonodatounmodoperdeterminaresel'immagineritagliata"si adatta" al suo posto.
Quindi, ad esempio, se dovessi posizionare casualmente l'immagine ritagliata da qualche parte nel mezzo, potrei ottenere qualcosa di simile
Ora,quandoloconfronticonl'immaginedibase,puoivederecheirettangolirossoeblusonoleggermentefuoridimolto,edèvisivamentesbagliato.
Senonsapessinulladeipixelcircostanti(adesempio,selavariazioneritagliatafossesemplicementel'ovaleverde),sarebbeimpossibileriprodurrel'immaginedidestinazionesenzapassaremanualmente.
Possoquantificareindirettamentecome"vicino" la mia immagine candidata è all'immagine di destinazione prendendo la somma delle differenze tra tutti i pixel tra l'immagine candidata e l'immagine di base: gli unici pixel che dovrebbero essere diversi sono quelli che rendono su la variazione; il resto dei pixel circostanti che si trovavano nel rettangolo dovrebbe essere esattamente uguale all'immagine di base e dovrebbe contribuire con una differenza di 0.
Soluzione di base
Un approccio a forza bruta calcola fondamentalmente la somma di tutte le differenze di pixel di ogni posizione possibile che l'immagine ritagliata può essere posizionata, quindi restituisce tutte le posizioni che minimizzano questa somma. Per immagini sufficientemente complesse, le probabilità che ci siano più risultati sono piuttosto piccole rispetto alle immagini semplici.
Ad un certo punto mi sono reso conto che devo solo considerare i pixel all'interno del rettangolo dell'immagine ritagliata, perché quelli sono gli unici pixel dell'immagine candidata che cambiano rispetto all'immagine di base, quindi questo evita alcuni calcoli non necessari.
Miglioramenti?
La mia idea sembra piuttosto lenta. Beh, ci vorranno meno di un minuto per le immagini di dimensioni 1280x960 o 1920x1080p, ed è ancora molto più veloce di farlo a mano.
Il mio approccio può essere migliorato? Ad esempio, ho davvero bisogno di provare tutte le combinazioni possibili?
Sarebbe interessante vedere se c'erano altri modi per affrontare il problema.