Зона кода

А давайте немного попрограммируем...

Эффект плавного появления изображения на холсте

C99Графические программы

Последнее время увлёкся я созданием анимаций, демонстрирующих различные виды трансформаций изображений. Я для развлечения придумывал различные простые алгоритмы преобразований картинок, после чего у меня возникало желание посмотреть, как эти преобразования будут выглядеть в анимированном виде, что называется, "пощупать глазами". В результате я создавал программы, реализующие эти алгоритмы и генерирующие кадры иллюстрирующих их анимаций.

Один тип преобразований я уже описал ранее. Сегодня хочу поговорить ещё об одном, достаточно простом алгоритме.

Речь идёт об эффекте плавного появления изображения на холсте. Его суть очень проста. Берётся некоторое изображение, например, фотография. Любое изображение, как известно, состоит из точек различных цветов. Точки нашего изображения разбиваются на группы. В качестве фона берётся белый прямоугольник. На него наносится первая группа точек. Полученное изображение рассматривается как кадр анимации. Затем на это же изображение наносится вторая группа, и это уже — следующий кадр.

Этот процесс повторяется многократно до тех пор, пока на изображение не будет нанесена последняя группа точек. Соответствующий кадр анимации будет в точности совпадать с нашим изображением, которое мы, в дальнейшем, будем называть "финальным", поскольку именно им завершается анимация.

Очень важно, чтобы точки заполняли холст как можно более равномерно. Для этого требуется, чтобы по группам они были распределены в случайном порядке. Тогда в итоговой анимации изображение будет появляться плавно, и в каждый момент времени уровни детализации различных частей кадра будут примерно одинаковыми.

Этот эффект будет, пусть и отдалённо, напоминать появление изображения на засвеченном фотоувеличителем листке фотобумаги после его погружения в проявляющий раствор. Автору, в силу его уже далеко не юного возраста, посчастливилось неоднократно получать фотографии именно таким способом в те времена, когда существование цифровых фотоаппаратов даже сложно было представить. Но повторюсь ещё раз: сходство отдалённое.

Кстати, в качестве фона можно брать не белый прямоугольник, а другое изображение (фотографию). Тогда мы получим трансформацию одной картинки в другую.

Писать программу будем на языке C99. Традиционно для генерации кадров будем использовать графическую библиотеку pgraph (предполагается, что читатель, хотя бы в общих чертах, знаком с этой библиотекой), а собирать кадры в анимацию будем с помощью видеоредактора VirtualDub.

Основная идея

Пожалуй, самый главный вопрос, на который мы должны ответить в ходе решения поставленной задачи, формулируется так. Каким образом обеспечить случайный порядок попадания точек на холст?

Оговоримся, что, разумеется, решая задачи с помощью компьютера, мы можем говорить лишь о псевдослучайных величинах. И здесь мог бы пригодиться генератор псевдослучайных чисел, с помощью которого мы получали бы номера точек, которые затем наносили бы на холст. Проблема заключается в том, что генератор может выдавать номера точек повторно, а мы каждую точку собираемся наносить только один раз.

Игнорирование повторных номеров точек — это не очень хорошее решение. Во-первых, чтобы выяснять, встречался ли уже номер точки, сформированный генератором, раньше, или нет, нужно хранить все ранее полученные номера (что не является проблемой) и каждый раз производить сверку текущего номера с уже имеющимися (а вот это уже приведёт к нежелательным затратам времени). Во-вторых, чем больше номеров сгенерировано, тем чаще будут попадаться повторения, проверка которых, опять же, приведёт к потере времени.

Наконец (и это, в-третьих), нет никакой гарантии, что, до того, как генератор "зациклится" (а зациклится он обязательно), он успеет перебрать абсолютно все номера точек. А если не успеет, то это приведёт к тому, что наша программа никогда не завершится.

Мы пойдём другим путём. Пронумеруем все точки и поместим номера в одномерный массив. А затем "перемешаем" их. Для этого нам также понадобится генератор псевдослучайных чисел. Будем получать с помощью него пары индексов элементов массива, после чего менять местами содержимое элементов, имеющих данные номера. Разумеется, чтобы тщательно перемешать номера точек, эти транспозиции значений элементов массива нужно производить многократно.

После того, как процесс перемешивания закончится, будем перебирать элементы массива в порядке увеличения индексов и извлекать номера точек, формируя из них группы. Как только очередная группа сформирована, процесс перебора приостанавливаем и наносим точки, номера которых содержатся в группе, на холст. Далее возобновляем перебор и продолжаем аналогичные действия до полного исчерпания элементов массива.

Как мы видим, всё довольно просто. Можно переходить к программированию.

Структура программы

Программа состоит из файла fenix.c (да-да, отсылка к той самой птичке, возрождающейся из пепла) и из файлов графической библиотеки pgraph. Вот, с чего начинается fenix.c:

1.#include "pgraph.h"
2.#define W 640            //Ширина кадра
3.#define H 360            //Высота кадра
4.#define I 10000000       //Количество транспозиций
5.#define F 576            //Количество точек в группе
6.
7.const int S = W * H;     //Количество точек в изображении

В 1-й строке подключается заголовочный файл графической библиотеки. Назначение макросов W, H, I, F, полагаю, понятно из комментариев в самом коде. Как видно, мы собираемся создавать кадры размером 640x360, ориентируясь на Ютьюб. Каждый такой кадр будет состоять из 230400 точек; это количество будет сохранено в константной переменной S (см. стр. 7).

Общее количество кадров, совпадает с количеством групп точек (как было показано, каждой группе точек соответствует кадр, на котором появляются точки из этой группы). Оно равно отношению S к F, т. е. 400. Демонстрация 400 кадров при стандартной частоте 25кадр./c будет продолжаться 16 секунд. Изначально я исходил из этой продолжительности видео, выбирая значение F. На самом деле, кадров будет немного больше 400, но об этом поговорим позже.

Количество транспозиций значений элементов массива, содержащего номера точек (см. стр. 4), подобрано интуитивно. Для того, чтобы хорошенько перемешать 200 с лишним тысяч точек требуется не меньшее количество транспозиций. А лучше взять гораздо больше, например, на порядок, т. е. примерно 2 миллиона транспозиций. Я решил взять ещё больше. Пусть будет 10 миллионов, благо даже при таком количестве транспозиций перемешивание занимает не очень много времени. На моём достаточно старом компьютере инициализация элементов массива с последующим перемешиванием значений занимает примерно 2 секунды. Вполне приемлемое время. А 10 миллионов с запасом хватит и для большего размера кадра.

В файле fenix.c будут размещены 3 функции: fill_array(), create_frame() и main(). Первая из них будет заниматься заполнением массива номерами точек и их перемешиванием. Вторая — генерацией одного кадра. Наконец, третья — общим управлением процессом построения кадров для анимации.

Рассмотрим эти функции более подробно.

Формирования массива с номерами точек — функция fill_array()

Функция fill_array() принимает в качестве параметра адрес массива, базовый тип которого — int, и заполняет массив данными. Предполагается, что массив уже создан заранее и число его элементов равно S. Вот код этой функции:

 1.void fill_array(int arr[])
 2.{
 3.    for (int i = 0; i < S; i++)
 4.        arr[i] = i;
 5.    int ind1, ind2, t;
 6.    for (int i = 0; i < I; i++)
 7.    {
 8.        ind1 = (rand() << 15 | rand()) % S;
 9.        ind2 = (rand() << 15 | rand()) % S;
10.        if (ind1 != ind2)
11.        {
12.            t = arr[ind1];
13.            arr[ind1] = arr[ind2];
14.            arr[ind2] = t;
15.        }
16.        else
17.            i--;
18.    }
19.}

Сначала заполняем массив номерами точек, т. е. числами от 0 до S - 1 (стр. 3, 4) (о том, как нумеруются точки, поговорим позднее). Далее в цикле for выполняем I транспозиций значений массива (стр. 6-18).

Обратите внимание на строки 8 и 9, в которых с помощью генератора псевдослучайных чисел формируются индексы элементов, чьи значения меняются местами. Поскольку функция rand() при одном вызове выдаёт псевдослучайное число от 0 до 32767, а индекс последнего элемента массива равен 230399, такого диапазона явно недостаточно. Проблему решаем уже знакомым нам способом: объединяем два псевдослучайных числа в одно с помощью побитовых операций сдвига и сложения, увеличив, тем самым, верхнюю границу диапазона до 1073741823. А в качестве интересующего нас индекса каждый раз берём остаток от деления результата объединения на 230399.

Получив индексы, выполняем, в случае их несовпадения, саму транспозицию (стр. 10-15). Если же индексы совпали, то уменьшаем переменную цикла на единицу (см. стр. 16-17). Это делается для того, чтобы в случае совпадения индексов (т. е. в случае невыполнения транспозиции) тело цикла прокручивалось ещё один дополнительный раз с тем же самым значением переменной цикла. Можно было бы без этого обойтись, но, всё-таки, транспозиции "терять" не хочется. Пусть их будет ровно I.

Создание кадра — функция create_frame()

Функция  create_frame() принимает в качестве параметров адрес изображения, заполняемого точками, адрес финального изображения и адрес массива, хаотично заполненного номерами точек. Функция извлекает из массива группу, состоящую из F номеров точек, и копирует точки с заданными номерами из второго изображения в первое. В качестве результата функция возвращает адрес первого изображения.

Перед тем, как привести код функции, напомним одну особенность библиотеки pgraph. Если изображение хранится в объекте типа image, то информация о цветах его пикселей содержится в массиве pixels, являющимся полем этого объекта. Каждый элемент данного массива содержит цвет пикселя, номер которого совпадает с индексом массива, если нумеровать пиксели построчно слева направо снизу вверх.

Будем считать, что и мы нумеруем точки, из которых состоит изображение, точно таким же способом.

Таким образом, для того, чтобы скопировать точку номер i изображения, адресуемого указателем img2, в изображение, адресуемое указателем img1, нужно выполнить следующую операцию присваивания:

img1->pixels[i] = img2->pixels[i];

Кстати, нам совсем необязательно знать, как нужно нумеровать точки, чтобы их номера совпадали с индексами массивов pixels, т. к. мы каждый раз наносим на изображение совершенно произвольную группу точек. Главное для нас лишь то, что массив, формируемый в функции fill_array(), наполнен, по сути, индексами элементов массивов pixels. Так что в упомянутой выше операции присваивания роль индексов элементов будут играть значения элементов данного массива.

А теперь приведём код функции create_frame().

 1.image* create_frame(image *img1, image *img2, int arr[])
 2.{
 3.    static int i = 0;
 4.    int j = i + F;
 5.    color *pixels1 = img1->pixels;
 6.    color *pixels2 = img2->pixels;
 7.    for (; i < j; i++)
 8.        pixels1[arr[i]] = pixels2[arr[i]];
 9.    return img1;
10.}

Статическая переменная i (см. стр. 3) содержит количество точек, уже нанесённых на изображение, адресуемое указателем img, в момент вызова функции. После каждого вызова функции  значение i увеличивается на F (число точек в группе). Таким образом, группа номеров точек, которые должны быть нанесены на изображение, содержится в элементах массива arr с индексами от i до i + F (в строке 4 верхняя граница этого диапазона помещается в переменную j).

В строках 5 и 6 присваиваем указателям pixels1 и pixels2 адреса массивов, содержащих цвета пикселей первого и второго изображений соответственно. Благодаря этому в дальнейшем нам не придётся обращаться к массивам через указатели img1 и img2.

Наконец, в цикле мы копируем точки, номера которых хранятся в элементах массива arr с индексами от i до j, из 2-го изображения в первое с помощью операции присваивания, подробно рассмотренной выше (стр. 7, 8).

Последнее, что мы делаем — возвращаем из функции адрес модифицированного изображения.

Управление созданием кадров — функция main()

А вот код функции main():

 1.int main()
 2.{
 3.    int arr[S];
 4.    fill_array(arr);
 5.    image *img1 = create_image(W, H);
 6.    image *img2 = load_from_file("image2.bmp");
 7.    char filename[13];
 8.    int i;
 9.    for(i = 1; i <= 25; i++)
10.    {   
11.       sprintf(filename, "results\\%03d.bmp", i);
12.       save_to_file(img1, filename);        
13.    }
14.    int j = i + S / F;
15.    for(; i < j; i++)
16.    {   
17.       sprintf(filename, "results\\%03d.bmp", i);
18.       save_to_file(create_frame(img1, img2, arr), filename);
19.    }  
20.    j = i + 23;
21.    for(; i <= j; i++)
22.    {
23.       sprintf(filename, "results\\%03d.bmp", i);
24.       save_to_file(img2, filename);        
25.    }
26.    free(img1);
27.    free(img2);
28.    return 0;    
29.}

Создаём массив из S элементов (стр. 1) и заполняем его номерами точек, расположенными в хаотичном порядке (стр. 4). Создаём фоновое изображение — белый прямоугольник шириной W и высотой H (стр. 5). Загружаем из файла image2.bmp, расположенного в корневом каталоге исполняемого файла, финальное изображение (стр. 6). Предполагается, что оно будет иметь точно такие же ширину и высоту, что и фоновое.

Создаём символьный массив для хранения имён графических файлов, в которых будут храниться кадры (стр. 7) и переменную i — счётчик кадров, который будет участвовать в формировании имён файлов (стр. 8).

Кадры будущей анимации создаём в 3 приёма. Сначала формируем первые 25 кадров, каждый из которых совпадает с фоновым изображением (стр. 9-13). Затем с помощью функции create_frame() создаём S / F кадров, образующих основную часть анимации, демонстрирующую заполнение холста точками. Наконец, дублируем 24 раза последний кадр основной части анимации, представляющий собой финальное изображение (стр. 20-25).

Таким образом, общее количество кадров будет равно значению выражения 49 + S / F, а фоновое и финальное изображения будут демонстрироваться зрителю в начале и конце ролика соответственно ровно по одной секунде каждое (при частоте кадров, равной 25кадр./c.).

Не забываем освободить память, выделенную для хранения изображений, адресуемых указателями img1 и img2 (стр. 26, 27).

В результате выполнения программы графические файлы, содержащие кадры анимации, будут записываться в папку results, которая к моменту выполнения должна уже существовать и располагаться в той же директории, что и исполняемый файл. Файлы, в порядке их создания, будут называться 001.bmp, 002.bmp и т. д. (мы предполагаем, что кадров будет меньше 1000).

Тестирование программы

Выберем в качестве финального изображения уже знакомый нам по статье о пиксельном взрыве утренний горный пейзаж:

Финальное изображение

Финальное изображение

Скачать исходный файл, готовый к использованию в программе, можно здесь. Напоминаю, что располагаться графический файл должен в том же каталоге, в котором находится исполняемый файл программы.

Запускаем программу. В результате её выполнения в директории results обнаруживаем 449 графических файлов общим размером около 295МБ. Собираем кадры в анимацию с помощью видеоредактора VirtualDub, используя сжимающий без потерь кодек Huffyuv и установив требуемую частоту 25кадр./с. (подробности использования VirtualDub'а см. в этой и в этой статьях). В итоге получаем файл размером около 231МБ. Из-за наличия мелких деталей сжатие без потерь, как мы видим, не очень эффективно: размер видеоролика составляет целых 78% суммарного размера файлов с кадрами.

Вот что получилось после загрузки ролика на Ютьюб:

Как ни странно, Ютьюб показывает нам ролик в весьма приемлемом качестве. Я ожидал, что из-за сильного сжатия качество будет значительно хуже.

А теперь давайте в качестве фонового изображения возьмём следующую фотографию, так же нам уже знакомую:

Исходное (фоновое) изображение

Исходное (фоновое) изображение

Файл в виде, "готовом к употреблению", можно скачать по ссылке. Графический файл с данным пейзажем называется image1.bmp. Его нужно разместить в директории, содержащей исполняемый файл программы.

Но, чтобы программы использовала файл image1.bmp, в функции main() нужно заменить 5-ю строку следующей:

image *img1 = load_from_file("image1.bmp");

В результате выполнения программы снова получаем 449 файлов общим размером 295МБ. А созданный с помощью VirtualDub'а ролик имеет размер уже 277МБ, это значительно больше, чем в прошлый раз, что неудивительно: из-за появления второго изображения количество мелких деталей выросло. На этот раз отношения размера ролика к суммарному размеру кадров превышает 93%.

Ниже расположен ютьюбовский вариант этого ролика:

И снова замечу, что качество более, чем терпимое.

Заключение

Как мне кажется, идея трансформации и её программная реализация оказались несложными, а видеоролики — забавными. В следующей статье рассмотрим ещё один способ преобразования одного изображения в другое.

Скачать исходный код