Algoritmi per creare mosaici di immagini - c'è un modo più veloce di questo?

Sì, ci sono due approcci migliori e più veloci.

• Problema più semplice: per ogni tessera, scegli il pollice migliore (con possibile duplicazione). Ok, questo è imbroglio, ma può solo portare a un risultato visivo migliore.
• Il tuo take è algoritmicamente più interessante, e si riduce al "problema di assegnazione lineare", assumendo che tu prenda MSE come costi di corrispondenza la cui somma deve essere minima. Tale problema può essere risolto in tempo polinomiale, ad esempio tramite il "Metodo ungherese"

Quindi, puoi regolare i costi sostituendo MSE con una distanza visivamente più accurata, senza modificare l'algoritmo sottostante.

Sono ragionevolmente sicuro che si tratti di un problema NP-difficile. Per trovare una soluzione 'perfetta' devi provare ogni possibilità in modo esauriente, e questo è esponenziale.

Un approccio potrebbe essere quello di usare la misura golosa e poi provare a migliorarla. Quello potrebbe essere prendendo un'immagine mal posizionata (una delle ultime) e trovando un altro posto dove metterla, poi prendendo quell'immagine e spostandola e così via. Hai finito quando hai (a) esaurito il tempo (b) l'adattamento è "abbastanza buono".

Se si introduce un elemento probabilistico potrebbe cedere a un approccio ricottura simulata o a un algoritmo genetico. Forse tutto ciò che stai cercando di ottenere è diffondere gli errori in modo uniforme. Sospetto che si stia avvicinando a quello che stai già facendo, quindi la risposta è: con l'algoritmo giusto potresti ottenere un risultato migliore più velocemente ma non c'è alcuna scorciatoia magica per i Nirvana.

Sì, questo è simile a quello che stai già facendo. Il punto è dimenticare una risposta magica e pensare in termini di 2 algoritmi: prima riempire, quindi ottimizzare.

Il riempimento potrebbe essere: casuale, migliore disponibile, prima migliore, abbastanza buono, qualche tipo di hot spot.

L'ottimizzazione potrebbe essere casuale, correggere il peggio o (come ho suggerito) la ricottura simulata o l'algoritmo genetico.

Hai bisogno di una metrica di "bontà" e una quantità di tempo che sei disposto a spendere per questo e basta sperimentare. Oppure trova qualcuno che lo abbia effettivamente fatto.

Se le ultime tessere sono il tuo problema, dovresti provare a metterle in anticipo, in qualche modo;)

Un approccio sarebbe quello di guardare la tessera che è la più lontana dal x% superiore delle sue partite (intuitivamente, io andrei con il 33%) e posizionarla nella sua migliore corrispondenza. Questa è la migliore corrispondenza possibile.

Inoltre, potresti scegliere di non utilizzare la migliore corrispondenza per la tessera peggiore, ma quella in cui introduce il minimo errore rispetto alla migliore corrispondenza per quella slot, in modo da non eliminare completamente le tue migliori corrispondenze per scopo di "controllo dei danni".

Un'altra cosa da tenere a mente è che alla fine stai producendo un'immagine da elaborare da un occhio. Quindi quello che vuoi veramente è usare un po 'di rilevamento dei bordi per determinare quali posizioni sull'immagine sono più importanti. Allo stesso modo, ciò che accade alla periferia dell'immagine è di scarso valore per la qualità dell'effetto. Superare questi due pesi e includerli nel calcolo della distanza. Qualsiasi jitter che si ottiene dovrebbe quindi gravitare verso il bordo e lontano dai bordi, disturbando quindi molto meno.

Anche con il rilevamento dei bordi in atto, potresti voler inserire il primo y% avidamente (forse fino a quando non scendi al di sotto di una certa soglia di "spigolosità" nelle tessere a sinistra), in modo che i "punti caldi" siano trattati davvero bene, e quindi passare a "controllo dei danni" per il resto.