Функциональное программирование и обработка изображений

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

Есть весьма популярная в узких кругах утилита обработки изображений, называемая VIPS [1]. Утилита кроссплатформенная и используется для обработки очень больших изображений. Состоит она из двух частей – библиотеки libvips и утилиты с графическим интерфейсом nip2.

Библиотеку libvips можно использовать в связке с языками программирования Python, C и C++. Библиотека имеет несколько особенностей, которые с одной стороны позволяют обрабатывать очень и очень больших изображения (обработка автоматически распараллеливается и изображения размером в десятки гигабайт не выжирают разом память), а с другой стороны делают программирование очень необычным мероприятием.

Созданное один раз изображение в libvips нельзя изменить, а если нам очень надо – то мы должны создать новое, измененное (но и старое не исчезнет). Операции над изображением фактически не выполняются до тех пор, пока оно не сохраняется на диск (операции накапливаются до поры, до времени).

Эти и другие особенности libvips подталкивают к использованию функционального языка для работы с библиотекой, и такой язык встроен в nip2. Язык не имеет названия, поэтому дальше я буду называть его nip2.

Nip2 – ленивый функциональный объектно-ориентированный язык с лиспоподобным синтаксисом, позволяющий без особого труда разрабатывать расширения для VIPS.

Содержание

  1. Особенности nip2;
  2. порядок разработки и встраивания плагина в nip2;
  3. основы синтаксиса (функции, списки, классы);
  4. примеры небольших плагинов.

1. Особенности nip2

Язык nip2 является функциональным, со всеми вытекающими последствиями – о привычных нам циклах можно забыть.

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

foo a
 = bar a 123 (1/0)

bar fl a b
 = a, fl < 0
 = b

Пример листинг 1 демонстрирует ленивость языка. Функция foo вызывает функцию bar, при этом третьим аргументом передает выражение, содержащее деление на ноль. Если бы мы писали на С++, то ошибка возникала бы всякий раз при обращении к foo (потому что аргументы функции вычислялись бы до вызова), однако в nip2 картина иная.

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

Аналогичная “ленивость” проявляется и при обработке изображений. Если мы вырежем из изображения А область B, из области Bобласть C и сохраним C на диск. То работа с изображением A начнется только в момент сохранения. Помимо сохранения на диск, использованием изображения считается, например, вывод результата пользователю.

Язык nip2 использует динамическую типизацию, впрочем, это характерно для большинства функциональных языков. На листинг 1 видно, что типы данных не указываются, а значит, проверка типов не проводится. Ошибки проявят себя лишь когда программа будет запущена и потребует возвести строку в квадрат, например. Все это вместе с ленивостью nip2 значительно усложняет отладку программ.

Большинство функциональных языков производят оптимизацию хвостовой рекурсии (tail-recursion elimination) [2], т.к. вместо циклов в них используется рекурсия, но стек не резиновый. В nip2 хвостовая рекурсия циклом не заменяется, это не очень приятно. Реализация такой оптимизации планируется (в TODO-листе разработчиков, висящем на github, есть соответствующий пункт).

Наконец, nip2 – не язык общего назначения, он создан для разработки плагинов, обрабатывающих изображения. Любая функция или класс, сразу после сборки попадает в панель инструментов VIPS.

2. Порядок разработки плагина nip2

После запуска nip2 мы сразу можем приступать к написанию кода. Если нам требуется ввод значений – можно добавить мышкой на экран виджеты (Toolkits->Widgets-> …).

рис.1 виджеты nip2

рис.1 виджеты nip2

На рисунке 1 показано окно nip2 после добавления виджетов Number, Scale и Toggle. Нижнее поле позволяет нам ввести формулу над переменными A1, A2 и A3. После ввода формулы отобразится результат (как в A4, куда была введена формула “A1 + A2”). При открытии рисунка (File->Open) в окно nip2 будет добавлена переменная, связанная с открытым файлом.

Выпадающее меню Toolkits отображает все загруженные в настоящий момент плагины. Мы можем добавить туда свой плагин – выбираем Toolkits->Edit и вводим код в правое окно, после чего, в окне редактирования выбираем File->Process и новый плагин добавляется в меню (при отсутствии ошибок). Ошибки отображаются в Debug->Errors, а Debug->Trace позволяет просмотреть хронологию выполнения операций.

Если читатель скормит nip2 код из листинг 1 (каждую функцию надо скармливать отдельно) – то в меню будет добавлено 2 пункта – Toolkits->undefined->foo и Toolkits->undefined->bar.

Чтобы использовать наши функции достаточно выбрать поле, которое будет для них аргументом (например A1) и выбрать соответствующий пункт меню, но можно ввести выражение (в нижнее поле рисунка 1), например “foo A1” – будет добавлено поле A5, содержащее inf (если значение в A1 положительно) или 123.

Таким нехитрым образом, мы добавили небольшое расширение к nip2 и научились его использовать. Теперь разберемся более подробно с синтаксисом.

3. Синтаксис nip2

3.1 Функции

Описание функции состоит из имени функции, списком аргументов, и одного или нескольких тел.

Аргументы функции идут сразу за именем и не выделяются никаким особенным образом. Функция foo из листинг 1 принимает один аргумент с именем a, функция bar3 аргумента (fl, a и b).

Каждое тело функции отделяется символом “=”, так у функции foo всего одно тело, у bar2. Тело всегда содержит набор команд, которые надо выполнить, но может содержать также и условие (лишь одно, последнее тело всегда идет без условия). Условие отделяется запятой. Для выполнения выбирается первое тело, условие которого вернет истину.

Единственное тело функции foo требует вызвать функцию bar и передать ей 3 аргумента. У функции bar уже 2 тела, первое из них выполнится лишь когда первый аргумент имеет значение меньше нуля.

fact a
 = error "fact: bad argument (less then zero)", a < 0
 = 1, a < 2
 = a * fact (a - 1)

В листинг 2 приведен пример функции вычисления факториала. Во второй строке обрабатывается случай ошибки – неверного значения аргумента. В случае если условие сработает, вычисление завершится с ошибкой, а в окне ошибок появится заданный нами текст. В связи с тем, что nip2 не имеет развитых инструментов отладки, такие сообщения могут оказаться очень полезны.

/* вычисление чисел Фибоначчи
 22.02.14
*/
fib x
 = error "fib: bad arg < 0", x < 0
 = 0, x == 0
 = 1, x < 3
// = fib (x - 1) + fib (x - 2)
 = retval {
  fx1 = fib (x - 1);
  retval = fx1 + fib (x - 2);
 }

За описанием функции может располагаться блок, помещенный в фигурные скобки, содержащий какие-либо выражения, используемые в телах функций. В строке 9 листинг 2 создается переменная retval, значение которой и вернет функция fib для положительного аргумента со значением больше 2.

sum_n n
 = error "sum: bad argument (not integer)", (is_Real n) && (to_int n) != n
 = 0, n == 0
 = n - sum_n (n + 1), n < 0
 = n + sum_n (n - 1)
/* C stack overflow. Expression too complex */

Пример листинг 4 демонстрирует возможность использования составных выражений. Предикат is_Real является стандартным, как и функция to_int. В официальной справке эти моменты почти не прописаны, а то, что прописано имеет множество недочетов, поэтому гораздо надежнее искать функции в левой панели окна редактирования кода – можно посмотреть исходный код функций и, иногда, примеры использования.

3.2 Списки

Списки в nip2 выделяются квадратными скобками. Разделение на голову (первый элемент списка) и хвост (остальная часть) осуществляется оператором двоеточия. Пустой список обозначается пустыми квадратными скобками – []. Кроме того, получить первый элемент можно оператором hd, а хвост – оператором tl. Список может содержать значения разных типов, в том числе, вложенные списки.

listsum l
 = 0, l == []
 = (hd l) + listsum (tl l)
// listsum [1..100] --> 5050

В комментарии к листинг 5 приведен пример использования функции. Как видно из примера, в nip2 можно сгенерировать список (в примере генерируется список чисел от 1 до 100).

Достаточно удобно обрабатывать списки с использованием функций map, foldl и zip. Если Вам требуется применить некоторую функцию ко всем элементам списка и сформировать список результатов – вы можете сделать это с использованием map. Если же имеется 2 списка, соответствующие элементы которых должны выступать в роли аргументов некоторой функции – можно применять map2 (аналогично map3).

map f l
	= [], l == [];
	= f (hd l) : map f (tl l)

map2 fn l1 l2 = map (list_2ary fn) (zip2 l1 l2)

zip2 l1 l2
	= [], l1 == [] || l2 == []
	= [hd l1, hd l2] : zip2 (tl l1) (tl l2)

zip2 [1,2] ['a', 'b', 'c'] == [[1,'a'],[2,'b']]

Как видим, функция map2 реализуется через zip2, которая принимает 2 списка и формирует новый – содержащий вложенные двухэлементные списки из соответствующих элементов исходных списков. Если длины исходных списков различны – то лишние элементы будут отброшены с конца.

Не менее полезной является функция foldl, принимающая 3 аргумента – функцию (принимающую 2 аргумента), начальное значение первого аргумента и список. Функция последовательно применяется к каждому элементу списка и вычисленное значение становится на место первого аргумента функции при обработке следующего элемента.

foldl fn st l
	= st, l == []
	= foldl fn (fn st x) xs
{
	x:xs = l;
}

// foldl f x [1,2,3] --> f (f (f x 1) 2) 3

С использованием функции foldl, пример листинг 5 (нахождение суммы элементов списка) можно переписать проще и понятней.

my_plus a b = a + b
my_sum lst = foldl my_plus 0 lst

В библиотеке nip2 есть множество других полезных функций, например len, filter, concat (кстати, для конкатенации списков может быть использован оператор ++) которые не описаны в статье.

3.3 Классы

Классы nip2, поддерживают, например, наследование. Но в статье эти моменты освещены не будут. Мы остановимся на том, что дадут классы при встраивании плагина в VIPS.

Классы позволяют группировать функции и элементы управления. Во второй части статьи мы добавляли свой плагин в меню Toolkits, при этом, плагин представлял из себя одну функцию. Если таких функций будет много, возможно мы захотим их сгруппировать – это удобно.

improc = class {
// выделяет кусок изображения заданной высоты и наибольшей ширины
 extPart Y H Src
  = error "extPart: bad argument Y", Y >= Src.height
  = extract_area 0 Y Src.width (Src.height - Y) Src, (Y + H) > Src.height
  = extract_area 0 Y Src.width H Src;

// разбивает картинку на части, складывает части в список
 getParts From H Src
  = [], From >= Src.height
  = extPart From H Src : getParts (From + H) H Src;
}
// ImPart = improc.extPart 100 200 OldImg
//  --> ImPart будет содержать полоску высотой 200 пикселей из OldImg.
//      Полоска будет вырезана начиная с позиции 100 исходного изображения.

На листинг 9 приведен пример класса, группирующего функции обработки изображений. После обработки приведенного кода в меню nip2 будет добавлен пункт improc, содержащий два подпункта. Обращение к полям и методам класса осуществляется оператором точка (как показано в комментариях к листингу).

В этом же примере мы коснулись изображений (встроенная функция extract_area вырезает часть изображения), которые являются экземплярами класса Image. Подробнее про этот класс можно прочитать в официальной справке [3], а список доступных над ними функций – посмотреть в окне редактирования кода.

Помимо методов, класс может содержать поля. В качестве полей могут выступать константы, элементы управления (поля ввода данных, чекбоксы, …) и рассчитанные значения. Если в результате вычислений получается изображение – то оно отображается в виде уменьшенной копии). Однако, экземпляр класса будет отображен в nip2 только если у него есть родительский элемент (обычно таким элементом является открытое изображение).

MyTool Parent = class {
  my_sum a b = a + b;

  A = Number "первое слагаемое: " 0;
  B = Number "второе слагаемое: " 123;

  S1 = A.value - B.value;
  S2 = my_sum A.value B.value;
}

На листинг 10 приведен класс MyTool (пункт с таким именем будет добавлен в меню Toolkits), создаваться объект будет на основе элемента Parent (элемент в примере не используется, поэтому в качестве него может выступать что угодно). Класс содержит метод и 4 поля, два из которых представляют собой элементу управления, а два других – вычисляются.

рис.2 использование класса с элементами управления

рис.2 использование класса с элементами управления

4. Примеры

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

MyCrop Img = class {

 my_crop x y w h src
  = "bad arguments", (x + w) > sw || (x + h) > sh
  = extract_area x y w h src {
   sw = src.width;
   sh = src.height;
  };

 X = Scale "X: " 0 (Img.width - 1) 0;
 Y = Scale "Y: " 0 (Img.height - 1) 0;
 W = Scale "W: " 1 Img.width Img.width;
 H = Scale "H: " 1 Img.height Img.height;

 Result = my_crop X.value Y.value W.value H.value Img;
}

Результат работы плагина приведен на рис. 3. Если подвигать ползунки так, чтобы вырезаемая область вышла за пределы исходного изображения – вместо картинки в результат будет помещена строка с ошибкой. Такое поведение класса ничуть не хуже использования встроенной функции error, которую мы применяли до сих пор. Потому как в случае неверных типов данных (строка вместо картинки) в окне ошибок мы увидим какие именно данные были переданы и узнаем причину ошибки – если попытаемся использовать результат как-то иначе (не просто выводить на экран).

рис.3 пример класса обрезки изображения

рис.3 пример класса обрезки изображения

Следующее расширение будет чуть более сложным. Исходное изображение разобьем на чередующиеся части А и Б. Результатом работы плагина будет изображение, в котором все части А и Б переставлены в парах как показано на рис.4.

рис.4 перестановка частей изображения

рис.4 перестановка частей изображения

MyMix Img = class {

 check_uint x descript
  = "ok", x > 0
  = ("error: " ++ descript ++ " is not valid scope") / 0;

 mix a b
  = [], a == [] || b == []
  = a, b == []
  = b, a == []
  = hd b : hd a : mix (tl a) (tl b);

 list2img l
  = "error: list2img, bad argument", l == []
  = hd l, l == [hd l]
  = join_tb (hd l) (list2img (tl l));

 AH = Number "размер части А: " 100;
 BH = Number "размер части В: " 200;

 _A = AH.value;
 _B = BH.value;

 _CH1 = check_uint _A "часть A";
 _CH2 = check_uint _B "часть В";

 _AParts = improc.getABParts 0 _A Img _B;
 _BParts = improc.getABParts _A _B Img _A;

 _BAParts = mix _AParts _BParts;

 Result = list2img _BAParts;
}

В листинг 12 есть несколько интересных моментов, на которых стоит остановиться:

  • часть полей класса начинаются с символа подчеркивания. Значения таких полей не отображаются в окне плагина;
  • функция check_uint проверяет корректность введенных данных – вводится высота части, которая не может быть равной нулю или отрицательной. В случае ошибки функция формирует строку с сообщением и нарочно выполняет деление строки на число. Такое деление приводит к ошибке и текст, сформированного сообщения попадает в соответствующее окно. Такие трюки вынуждены тем, что в nip2 нет нормального отладчика;
  • при маленьких значениях размеров частей и больших размерах изображения программа будет падать (из за переполнения стека). В этом примере я даже не пытался написать функции с хвостовой рекурсией, т.к. nip2 их все равно не оптимизирует. Если все же, такую функцию требуется выполнить над большим изображением – можно разделить изображение на части и обрабатывать каждую отдельно, ограничив как-то глубину вызовов.

Выводы

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

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

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

Лично у меня (в статье не отражено) возникли проблемы с разбиением изображения на очень большое количество частей. Проблемы не со стеком, а с памятью. Может быть я что-то делал не так, но скрипт на nip2 у меня так и не получился, пришлось писать на Си с libvips (и это было ужасно). Я плохо думаю на сборщик мусора, но может быть дело в кривизне рук…

Ссылки по теме

  1. архитектура VIPS на официальном сайте \ http://www.vips.ecs.soton.ac.uk/index.php?title=How_it_works
  2. оптимизация хвостовой рекурсии \ https://pro-prof.com/archives/813
  3. официальная справка по языку nip2 \ http://www.vips.ecs.soton.ac.uk/index.php?title=Nip2
  4. блог разработчиков libvips и nip2 \ http://libvips.blogspot.ru/

Добавить комментарий