Алгоритм для создания всех возможных черно-белых пиксельных изображений в разрешении 640 x 360?

Ответ 1

Сначала ответьте на ваши вопросы. Да, будут записи на "некоторых" фотографиях. На самом деле появится текст, написанный человеком, который подходит в 640x360 пикселей. Также каждый другой текст (текст еще не написан или текст, который никогда не будет записан). Также вы увидите картины каждого человека, который был, был или будет жив. Подробнее см. Бесконечная теорема обезьяны.

Код для создания желаемого gif довольно прост. Для этого я использовал Java. Обратите внимание, что вам нужен дополнительный класс: AnimatedGifEncoder. Код не связан с памятью, потому что AanimatedGifEncoder будет записывать каждое изображение на диск, как только оно будет вычислено. Но убедитесь, что у вас достаточно свободного места на диске.

import java.awt.Color;
import java.awt.image.BufferedImage;

public class BigPicture {
    private final int width;
    private final int height;

    private final int WHITE = Color.WHITE.getRGB();
    private final int BLACK = Color.BLACK.getRGB();

    public BigPicture(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public void process(String outFile) {
        AnimatedGifEncoder gif = new AnimatedGifEncoder();
        gif.setSize(width, height);
        gif.setTransparent(null); // no transparency
        gif.setRepeat(-1); // play only once
        gif.setDelay(0); // 0 ms delay between images,
                         // 'cause ain't nobody got time for that!
        gif.start(outFile);
        BufferedImage bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_BINARY);

        // set the image to all white
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                bufferedImage.setRGB(x, y, WHITE);
            }
        }

        // add white image
        gif.addFrame(bufferedImage);

        // add all other combinations
        while (increase(bufferedImage)) {
            gif.addFrame(bufferedImage);
        }

        gif.finish();
    }

    /**
     * @param bufferedImage
     *            the image to increase
     * @return false if last pixel set to black => image is complete black
     */
    private boolean increase(BufferedImage bufferedImage) {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (bufferedImage.getRGB(x, y) == WHITE) {
                    bufferedImage.setRGB(x, y, BLACK);
                    return true;
                }
                bufferedImage.setRGB(x, y, WHITE);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        new BigPicture(640, 360).process("C:\\temp\\bigpicture.gif");
        System.out.println("finished.");
    }
}

Помните, что это займет некоторое время. Так что не беспокойтесь, ожидая и наслаждайтесь своей жизнью!;)

EDIT: поскольку мое решение немного нечеткое, я объясню алгоритм.

• Я определил метод под названием increase. Этот метод принимает BufferedImage и изменяет битовый шаблон изображения, чтобы появился следующий бит-шаблон. Метод просто немного дополняет. Метод вернет false, если изображение встретит последний бит-шаблон (все пиксели установлены на черный).
• Пока можно увеличить битовый шаблон (т.е. increase() возвращает true), мы сохраним изображение в качестве нового фрейма и снова увеличим изображение.
• Как работает метод increase(): метод сначала пробегает изображение в направлении x, затем в направлении y. Я предполагаю, что белые пиксели 0, а черные пиксели - 1. Итак, мы хотим взять битовый рисунок изображения и добавить 1. Мы проверяем первый пиксель: если он белый (0), мы можем добавить 1 без переполнения, чтобы мы превратили пиксель в черный (0 + 1 = 1 = > черный пиксель). После этого мы возвращаемся из метода, потому что хотим увеличить только одну позицию. Он возвращает true, потому что увеличение возможно. Если мы сталкиваемся с черным пикселем, у нас есть переполнение (1 + 1 = 2 или в двоичном 10). Поэтому мы должны установить текущий пиксель в белый цвет и добавить 1 в следующий пиксель. Это будет продолжаться до тех пор, пока мы не найдем первый белый пиксель.

Пример: сначала мы создаем метод печати: этот метод печатает изображение как двоичное число. Внимание, число обратное, и самый старший бит - бит в правой части.

public void print(BufferedImage bufferedImage) {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (bufferedImage.getRGB(x, y) == WHITE) {
                System.out.print(0); // white pixel
            } else {
                System.out.print(1); // black pixel
            }
        }
    }
    System.out.println();
}

теперь мы модифицируем цикл main-while:

print(bufferedImage); // this one prints the empty image
while (increase(bufferedImage)) {
    print(bufferedImage);
}

и теперь задайте короткий пример для проверки:

new BigPicture(1, 5).process("C:\\temp\\bigpicture.gif");

и, наконец, вывод:

00000 // 0 this is the first print before the loop -> "white image"
10000 // 1 the first white pixel is set to black
01000 // 2 the first overflow, so the second pixel is set to black "2"
11000 // 3
00100 // 4
10100 // 5
01100
11100
00010 // 8
10010
01010
11010
00110
10110
01110
11110
00001 // 16
10001
01001
11001
00101
10101
01101
11101
00011
10011
01011
11011
00111
10111
01111
11111 // 31 == 2^5 - 1
finished.

Ответ 2

Другими словами, каждый пиксель может быть либо черным, либо белым. 640 x 360 = 230,400 пикселей. Поэтому я считаю, что всего 460 800 изображений можно (230 400 x 2 для черно-белого).

В вашей вере есть небольшой недостаток. Вы правы в отношении количества пикселей: 230 400. К сожалению, это означает, что нет 2 * 230 400, но 2 ^ 230 400 возможных снимков, число которых составляет более 60 000 цифр (дольше, чем допустимый размер ответа, я боюсь). Для сравнения конкретное число с 45 цифрами означает диаметр наблюдаемой вселенной в сантиметрах (примерно ширина розового).

Чтобы понять, почему ваш расчет числа снимков неверен, рассмотрите этот пример: если ваши изображения содержали только три пиксела, вы могли бы иметь 8 разных изображений (2 ^ 3), а не 6 (2 * 3). Вот все они: BBB, BBW, BWB, BWW, WBB, WBW, WWB, WWW. Добавление другого пикселя удваивает размер возможных изображений, потому что у вас может быть белый для всех 3-пиксельных случаев или черный для всех 3-пиксельных случаев. Удвоение 1 (количество изображений, которое вы можете иметь с 0 пикселями) 230,400 раз дает вам 2 ^ 230 400.

Хорошо, что есть щедрость за этот вопрос, но он довольно отвлекает и контрпродуктивен, если это так же, как шутка в апреле.

Ответ 3

Я собираюсь пойти и ущипнуть некоторый код из связанного вопроса, просто для удовольствия.

from itertools import product
for matrix in product([0, 1], repeat=(math,pow(2,230400)):
    # render and save your .gif

Как уже было сказано, удачи!

В более серьезной заметке, если вы не хотите быть абсолютно уверенным, что у вас есть все перестановки, вы можете создать случайную матрицу 640x360 и сохранить ее как изображение.

Выполните это действие, скажем, 100 тыс. раз, и у вас будет хотя бы интересный набор изображений, на которые можно смотреть, но невозможно получить все возможные перестановки.

Затем вы можете удалить все одинаковые файлы, чтобы уменьшить набор только к уникальным изображениям.