Algoritmo per generare tutte le possibili immagini di una particolare dimensione in 256 colori

-1

Stavo discutendo con un amico sul Teorema della scimmia infinita ed è stato allora che è venuto fuori. Supponiamo di voler generare un'immagine di dimensioni 60 x 80, cioè 4800 pixel e vogliamo usare 8bpp (bit per pixel) o 1 byte per ciascun colore (per un totale di 256 colori).

Ora qual è l'algoritmo per generare tutte le immagini possibili utilizzando questi valori? Penso che il numero totale di immagini generate sarà 256 ^ (60 x 80), cioè 256 elevato alla potenza 4800. Esiste un algoritmo che può essere utilizzato per generare tutte le combinazioni di valori di colore per slot da 4800 pixel?

    
posta A9S6 20.09.2016 - 07:23
fonte

4 risposte

5

Un'immagine 60 per 80 in cui ogni pixel può avere 256 colori (8 bit) espressi come bitmap è semplicemente un array di 60 * 80 = 4800 byte.

Se si considera l'array di byte come un singolo numero intero, basta contare da 0 a 0xFFFF ... FFFF (9,600 "F" s). Molti linguaggi moderni hanno tipi interi a lunghezza variabile (ad es. Java BigInteger ) in grado di gestire numeri così grandi.

Ogni volta che incrementi quel numero super grande, hai creato una nuova immagine.

Per visualizzare un'immagine, basta tagliare quel numero intero in segmenti da 8 bit e hai i tuoi 4.800 pixel. Ogni gruppo di 60 pixel è una riga. Questa è l'idea di base dietro le bitmap ( .bmp file).

NB. questo programma funzionerà fino alla morte termica dell'universo.

    
risposta data 20.09.2016 - 08:09
fonte
4

Ecco come lo farei. Consente di renderlo generale e dire che l'immagine è larghezza * altezza.

Pseudocodice:

int[width*height] rawImage;

initialize all rawImage values to 0;

while (rawImage[width*height-1] < 256) {

    create255ImageFrom(rawImage);

    rawImage[0]++;
    for(int i = 0;i<width*height-1;i++)
    {
        if (rawImage[i] > 255){
            rawImage[i] = 0;
            rawImage[i+1]++;
        }
    }

}

Potrebbero esserci alcuni errori off-by-one e edge. Ma generalmente dovrebbe funzionare.

Quello che fa è che fondamentalmente crea un "numero" con "altezza" di "cifre" in cui ogni "cifra" è 256 valori. Quindi, quando si aumenta la prima cifra e supera 255, aumenta la "cifra" successiva di una e quindi si imposta su 0; E va così fino a quando l'ultima cifra supera 255, il che significa che ha enumerato tutti i valori.

    
risposta data 20.09.2016 - 08:14
fonte
1

Niente è così semplice come sembra prima ...

Se generi tutte le immagini, un'immagine alla volta, allora saranno 256 ^ (60 x 80) immagini.

Se generi immagini a coppie, con un'immagine di 60 * 160 pixel "2 immagini in una" in cui un'immagine corrisponde alla metà superiore e l'altra alla metà inferiore; quindi non cambierebbe nulla, e sarebbe comunque pari a 256 ^ (60 x 80) immagini in totale.

Tuttavia, se generi una "meta immagine" di 60 * 160 pixel, ci sarà una immagine che inizia sulla riga superiore, una seconda immagine che inizia sulla seconda riga, una terza immagine sulla terza riga, .... Sarebbe in realtà sono un totale di 80 immagini in cui ogni immagine si sovrappone all'immagine precedente di 79 righe di pixel. Alcune di quelle immagini non sarebbero state viste prima, e non hanno bisogno di essere viste di nuovo, quindi finirebbe per essere meno lavoro.

Che cosa succede se hai generato una meta immagine da 6000 * 8000 "? Ogni "meta immagine" conterrebbe 10000 delle 60 x 80 immagini più piccole che si sovrappongono. Quanto lavoro vorrebbe salvare?

Ora ... Che cosa succede se generi 1 immagine, quindi la ruota di 90 gradi? È la stessa immagine. Puoi generare 1 immagine e conta come 4 rotazioni * 2 specchi = 8 variazioni della stessa immagine.

La domanda quindi è: qual è la "meta immagine" più piccola che è necessario generare, in modo che la "meta-immagine" contenga tutte le possibili 60 * 80 immagini almeno una volta, escluse rotazioni e specchi? Se puoi rispondere, la quantità di lavoro sarà significativamente inferiore a 256 ^ (60 * 80).

Per un esempio di quello che sto dicendo; immagina che siano 2 colori e 2 * 1 immagini. Per questo, il caso peggiore (la matematica che tutti usano) sarebbe 2 ^ (2 * 1) = 4 immagini, come questa:

    00
    01
    10
    11

Tuttavia, 01 e 10 sono specchi l'uno dell'altro, quindi ne hai bisogno solo uno. Questo dà l'equivalente di 3 immagini:

    00
    01
    11

Ora immagina una "meta immagine":

    0011

Questo contiene tutte e 3 le immagini precedenti che si sovrappongono. Tuttavia, questo è un totale di 4 pixel per tutte le immagini, non un totale di 8 pixel per tutte le immagini. È letteralmente la metà del lavoro.

    
risposta data 20.09.2016 - 09:49
fonte
0

solo per un 2X2
forza bruta
la risposta di Euforic è migliore

UInt64 count = 0;
byte[,] image = new byte[2, 2];
for (int i = 0; i < 256; i++)
{
    image[0, 0] = (byte)i;
    for (int j = 0; j < 256; j++)
    {
        image[0, 1] = (byte)j;
        for (int k = 0; k < 256; k++)
        {
            image[1, 0] = (byte)k;
            for (int m = 0; m < 256; m++)
            {
                image[1, 1] = (byte)m;
                count++;
            }
        }
    }
}
System.Diagnostics.Debug.WriteLine(count.ToString());
System.Diagnostics.Debug.WriteLine(Math.Pow(256, 4).ToString());
    
risposta data 20.09.2016 - 09:17
fonte

Leggi altre domande sui tag