AlgART / Java libraries
AlgART и обработка изображений: некоторые элементарные приемы
Даниил Алиевский, 2007
ОГЛАВЛЕНИЕ
- Введение
- AlgART-массивы
- AlgART-матрицы
- Матрицы и generics: extends или не extends?
- Двумерные изображения: Image2D
- Часть I. Чтение и создание изображения: класс SimplestTutorialDemo
- Конверсия RGB-изображения в полутоновое
- Вычисление средней яркости самым плохим способом: покоординатный цикл
- Вычисление средней яркости чуть менее плохим способом: цикл по массиву
- Вычисление средней яркости: пора вспомнить о пользователе
- Вычисление средней яркости: учимся писать эффективно
- Вычисление средней яркости: библиотечная функция все-таки лучше
- Генерация константного изображения простейшим способом: цикл по массиву
- Генерация константного изображения: произвольная разрядность результата
- Генерация константного изображения: да здравствует лень!
- Генерация константного изображения: ленимся грамотно
- Генерация константного изображения: сколько можно лениться?
- Генерация константного изображения: да будет цвет!
Введение
В этой статье мы рассмотрим некоторые простейшие приемы применения библиотек AlgART
на примере нескольких Java-классов — специально написанных примеров,
анализирующих и обрабатывающих двумерные растровые изображения.
Речь пойдет, главным образом, о пакете net.algart.arrays —
"сердце" библиотек AlgART.
Надо сразу сказать: библиотеки AlgART нетривиальны и обширны. С помощью нескольких примеров вполне овладеть ими нельзя, но можно "почувствовать" и научиться решать элементарные задачи. Исчерпывающую информацию об AlgART API можно найти в комментариях JavaDoc. Создавая библиотеки, я старался делать JavaDoc-комментарии максимально подробными и, по-возможности, снабжал простейшими примерами кода.
Ниже, при разборе примеров, я буду давать нужные пояснения к используемым
классам, интерфейсам и методам.
Однако при чтении рекомендуется иметь "под рукой" полный справочник JavaDoc
и просматривать комментарии к разбираемым методам.
Кроме того, рекомендуется в самом начале просмотреть обзорный комментарий к пакету
net.algart.arrays (package summary).
Перед тем, как двигаться дальше, я вкратце опишу три основных сущности (объекта),
необходимых для работы с изображениями средствами AlgART.
Это линейный массив, матрица и собственно изображение,
представленные соответственно интерфейсами Array, Matrix<? extends Array>
и Image2D.
1. AlgART-массивы
Интерфейс Array — базовый интерфейс библиотеки net.algart.arrays,
описывающий так называемый AlgART-массив.
(Далее под "массивом" мы почти всегда будем пониимать именно AlgART-массив.)
Его можно рассматривать как далеко развитый аналог таких стандартных классов,
как ArrayList и java.nio.Buffer.
В AlgART-массиве можно хранить любые типы данных, причем в отличие от ArrayList
хранение примитивных типов будет эффективным.
Адресация массива 63-битовая: все индексы и размеры имеют тип long.
Соответственно, размеры AlgART-массивов не ограничены лимитом 2 GB.
Даже на 32-разрядных OS библиотека позволяет легко создавать массивы произвольного размера:
для этого автоматически и прозрачно для программиста задействуются дисковые файлы.
Массивы могут хранить произвольные типы элементов (например, строки),
но для обработки изображений нас будут интересовать исключительно массивы,
элементы которых принадлежат к одному из 8 стандартных примитивных типов:
boolean, char, byte, short,
int, long, float и double.
Да, даже long и double:
хоть и маловероятно, что для описания яркости пиксела потребуется такая точность,
однако проще и естественнее универсально отработать все разрядности Java, чем
вводить искусственные ограничения. На деле тип char в данном случае совершенно бесполезен
(в нашей библиотеке он равнозначен short), однако для полноты поддерживается и он.
В иерархии интерфейсов пакета net.algart.arrays такие массивы представлены
следующими подинтерфейсами интерфейса Array:
PArray(обеспечивает доступ к массиву только на чтение) иUpdatablePArray(расширяетPArray, добавляя возможности модификации элементов).
У этих интерфейсов, в свою очередь, есть подинтерфейсы для представления каждого конкретного примитивного типа,
например, BitArray (массив boolean-элементов, т.е. битов),
ByteArray, ShortArray или UpdatableFloatArray, UpdatableCharArray.
Есть даже подинтерфейсы, описывающие группы примитивных типов, например, PFixedArray:
массив элементов любого из 6 примитивных типов boolean, char, byte, short, int, long.
Однако чаще всего мы будем использовать базовые интерфейсы
PArray и UpdatablePArray,
обеспечивающие универсальную обработку данных любого типа и разрядности.
(Есть также и подинтерфейсы, обеспечивающие, подобно ArrayList, изменение длины массива,
но при обработки изображений они требуется редко.)
Про AlgART-массивы можно рассказывать очень долго — почти вся библиотека "выстроена" именно вокруг них.
Однако нам пора переходить к следующему понятию - матрице.
Желающие узнать про основные возможности массивов — читайте package summary к пакету
net.algart.arrays и документацию к конкретным классам и интерфейсам.
2. AlgART-матрицы
Как это и принято, растровые изображения, при использовании библиотек AlgART,
будут представлены матрицами. В отличие от сложной и обширной концепции AlgART-массива,
AlgART-матрица — очень простое понятие, представленное единственным интерфейсом Matrix.
Матрица в библиотеке AlgART всегда хранится в линейном массиве,
строка за строкой (по аналогии с такими языками программирования, как C или Pascal).
Соответственно, чтобы перейти от понятия линейному массива к понятию матрицы, достаточно "добавить"
к массиву набор размерностей вдоль каждой координаты.
В библиотеке AlgART такое "добавление" производится простейшим возможным способом:
композицией. А именно, AlgART-матрица представляет собой всего-навсего пару:
- AlgART-массив (хранящий элементы матрицы);
- набор размеров матрицы.
Соответствующий интерфейс Matrix весьма лаконичен:
он предоставляет доступ к этому массиву и к набору размеров,
а также содержит минимальный набор полезных методов, например,
для вычисления линейного индекса в массиве по индексам в матрице.
Пора заметить: AlgART-матрицы (как и массивы языков C и Паскаль) изначально многомерны.
Для работы с изображениями, конечно, нужны двумерные матрицы.
Однако хорошо написанные алгоритмы обработки матриц
чаще всего не содержат кода, специфического для случая именно двух измерений.
Например, фильтры, сглаживающие изображение, можно без изменений применить
к трехмерным матрицам, описывающим некую физическую среду,
и даже к четырехмерным матрицам, описывающим нечто совсем таинственное.
Возможен и вырожденный случай — одномерные матрицы.
Они могут использоваться, например, когда модуль, обрабатывающий тип Matrix,
нужно применить к обычному линейному массиву.
Размеры матрицы, как и длина линейного массива, представлены типом
long. Не потому, что это реально необходимо
(хотя теоретически можно представить себе потребность в 30-гигабайтной матрице
3x10 000 000 000),
а потому, что так проще: меньше приходится приводить типы.
Наступление эпохи 64-разрядных процессоров, вероятно, очень скоро сделает операции с типом long
такими же быстрыми, как и с типом int;
так зачем же вводить лишние ограничения?
Впрочем, посвеместное применение типа long требует повышенной аккуратности:
будьте бдительны!
Следует помнить, что при сложении, вычитании или умножении размеров или адресов
возможно целочисленное переполнение с получением нелепого результата.
По этой причине, скажем, в классе Arrays,
содержащем библиотеку "полезных" методов, предусмотрена специальная функция longMul
для перемножения long-чисел с проверкой на переполнение.
Применяйте ее! При сложении и вычитании обычно все проще: так, при сложении 2 неотрицательных
чисел типа long однозначным признаком переполнения является отрицательность суммы.
Все размерности матрицы можно получить соответствующими методами
интерфейса Matrix.
Конечно же, контракт интерфейса Matrix
(заявленный в JavaDoc и свято соблюдаемый в реализациях)
гарантирует, что длина AlgART-массива, хранящего элементы матрицы,
всегда равна произведению размерностей.
Линейный индекс любого элемента матрицы в этом массиве вычисляется по формуле ix+iy*dimX+iz*dimX*dimY+...,
где ix, iy, iz, ... — индексы элемента в многомерной матрице,
а dimX, dimY, ... — соответствующие размерности.
Для двумерного случая формула упрощается до ix+iy*dimX.
Имеется метод index, вычисляющий линейный индекс по этой формуле.
3. Матрицы и generics: extends или не extends?
Последнее, что следует сказать про матрицы: интерфейс Matrix обладает
generics-параметром — типом хранимого массива. Так, матрица элементов примитивного типа описывается как
Matrix<? extends PArray>,
а матрица, допускающая изменение элементов, как
Matrix<? extends UpdatablePArray>.
Применение generics, как обычно, позволяет улучшить контроль типов и свести к минимуму
необходимость явных приведений типов.
Тут у читателя, особенно недостаточно владеющего технологией generics, может возникнуть резонный вопрос.
Почему Matrix<? extends PArray>, а не просто Matrix<PArray>?
На первый взгляд кажется, что второй, более очевидный вариант вполне равноценен первому.
Ведь, действительно, с переменной типа Matrix<PArray>
можно делать в точности то же самое, что и с Matrix<? extends PArray>:
а именно, извлекать массив типа PArray.
На самом деле равноценность кажущаяся.
Попробуйте создать список java.util.ArrayList, содержащий несколько матриц.
(На практике такие списки, действительно, частенько необходимы — в алгоритмах,
обрабатывающих сразу серию матриц.)
Вы убедитесь, что
List<Matrix<? extends PArray>> и
List<Matrix<PArray>> —
вещи совершенно разные и несовместимые друг с другом.
Список первого типа нельзя присвоить переменной второго типа (и наоборот).
Список первого типа нельзя передать в метод, аргумент которого объявлен как список второго типа (и наоборот).
В список второго типа нельзя добавить матрицу типа Matrix<? extends PArray>
(правда, можно наоборот).
Это поведение подробно разбирается в хороших учебниках по Java.
Что же предпочесть: вариант с обобщающим "? extends" или более простые "с виду"
Matrix<PArray> и Matrix<UpdatablePArray>?
Представьте себе функцию, которая принимает матрицу на входе, обрабатывает и возвращает другую матрицу на выходе. (Кстати, это типичная ситуация при обработке изображений.) Хотя бы вот эту:
public Matrix<PArray> myFunction(Matrix<PArray> m) {
return m; // что может быть проще
}
Написав такую функцию, вы быстро убедитесь, что не можете применить ее
ни к матрице типа Matrix<UpdatablePArray>, ни к матрице конкретного байтового типа
Matrix<ByteArray>.
Иначе говоря, общее правило должно быть таким:
в качестве аргументов методов всегда лучше использовать конструкцию
Для результатов методов, а также при объявлении переменных ситуация не столь однозначна.
Формально, нет никаких проблем, если метод, например, вернет конкретный
Matrix<UpdatablePArray>:
безусловно, такой результат можно будет использовать повсюду, где "подошел" бы тип
Matrix<? extends UpdatablePArray>.
Однако библиотеки AlgART предпочитают и в этом случае использовать
более общий тип с
Почему? По той же причине, по которой в языке Java принято максимально строго
контролировать типы — для минимизации будущих ошибок.
Если бы метод какого-нибудь полезного интерфейса (вроде Image2D,
к которому мы сейчас перейдем) вернул результат конкретный типа
Matrix<UpdatablePArray> или
Matrix<PArray>, возник бы соблазн присвоить
его переменной такого же типа. Далее сей соблазн мог бы "распространиться":
если большинство переменных вашего класса или пакета имеют тип Matrix<PArray>,
почему бы не объявить где-нибудь метод с аргументом такого типа?
Более того, по мере развития вашего кода могут появиться списки матриц,
скажем, List<Matrix<PArray>>.
Все будет замечательно до тех пор, пока не понадобится применить ваши классы
к матрице с массивом другого типа.
Вероятнее всего, это окажется передача в метод, принимающий аргумент
Matrix<PArray>, матрицы Matrix<UpdatablePArray>.
Или, еще хуже, попытка построить список из матриц более частного типа,
скажем, занести в список List<Matrix<PArray>>
конкретную Matrix<BitArray>.
И в этот момент весь ваш код придется переписывать —
переводить его на "правильные рельсы" Matrix<? extends PArray>.
Автор, между прочим, в процессе разработки библиотек пару раз "наступал" на эти грабли.
Гораздо лучше ограничить себя с самого начала и всегда применять конструкцию "? extends". Что и сделано в библиотеках AlgART.
Подробнее про матрицы читайте JavaDoc-документацию к интерфейсу Matrix.
4. Двумерные изображения: Image2D
Вообще говоря, абстракции матрицы уже достаточно, чтобы создавать практически любые алгоритмы обработки изображений.
(Обращаю внимание: я говорю не разработке графических пакетов типа Photoshop, где работа с цветом исключительно важна, а о математических алгоритмах, предназначенных для обработки и анализа изображений. Именно таким алгоритмам посвящена данная статья. Алгоритмы, как правило, работают именно с матрицами.)
Действительно, полутоновое изображение (наиболее популярный тип для задач анализа и распознавания)
всегда можно представить числовой матрицей, содержащей яркости пикселов.
Цветное изображение очевидным образом представляется несколькими "параллельными" матрицами одинакового размера,
содержащими цветовые составляющие для каждого пиксела.
Так, RGB-изображение можно представить как систему из 3 матриц,
содержащих red-, green- и blue-компоненты.
Прочие цветовые модели — HSL, HSV, ARGB, CMYK, YUV, XYZ, ... —
также сводятся к системе матриц, как правило, 3 или 4.
Соответственно, для представления любого изображения можно всегда использовать либо переменную типа
Matrix<? extends PArray> (в случае полутонового изображения),
либо (в зависимости от алгоритма) 3 или 4 такие переменные,
либо очень простой класс с 3 или 4 полями типа Matrix<? extends PArray>,
созданный специально для группы алгоритмов, нетривиально обрабатывающих цветность
(например, конвертирующих HLS в RGB).
На самом деле, в рамках пакета net.algart.arrays и его подпакетов так оно и есть.
Все базовые алгоритмы, рассчитанные на работу с изображениями и реализованные в этом пакете и подпакетах,
как правило, работают с единственной матрицей, представляющей полутоновое изображение.
При желании, эти методы можно вызвать для любой выбранной цветовой
компоненты или для всех цветовых компонент по очереди.
Скажем, простейшее сглаживание цветной RGB-картинки (удаление мелкого аддитивного шума)
сводится к применению соответствующего библиотечного метода по очереди к трем матрицам,
представляющим цветовые компоненты.
Иначе говоря, я вынужден огорчить пользователей, привыкших к пакетам типа java.awt или JAI. В библиотеках AlgART отсутствует поддержка цветности. Такую цену пришлось заплатить за алгоритмическую мощь и универсальность библиотек применительно к массивам и матрицам. По-настоящему качественная, современная реализация понятия цветности сделала бы сроки выхода библиотек AlgART абсолютно неприемлемыми. Надо сказать, что изображения и не являются основной и единственной областью применения библиотек. AlgART-массивы и матрицы с тем же успехом могут использоваться практически в любых численных расчетах: например, при решении систем линейных уравнений или физическом моделировании.
Однако, если все же говорить о применении библиотек AlgART к обработке изображений,
то совсем игнорировать цветность было бы неправильно.
Большая часть изображений, встречающихся в реальной жизни — полученные,
например, со сканера, фотоаппарата или видеокамеры — как правило, цветные.
Было бы неудобно, если бы вообще отсутствовал какой-либо стандартный класс,
позволяющий хранить такое изображение и передавать его универсальным алгоритмам,
рассчитанным на обработку AlgART-матриц (например, фильтрующим помехи или выделяющим контура частиц).
Такой класс — точнее, интерфейс — действительно существует.
Это интерфейс Image2D,
расположенный в отдельном пакете com.simagis.images.color
и описывающий либо полутовое, либо цветное двумерное изображение.
Данный интерфейс расположен вне пакета net.algart:
формально он не входит в состав библиотек AlgART.
Иначе говоря, автор библиотек AlgART старательно открещивается от всяких упреков
по поводу этого интерфейса. Если он покажется вам убогим, почему бы вам не написать свой?
Интерфейс Image2D практически тривиален.
Image2D — это просто либо одна AlgART-матрица
Matrix<? extends PArray>
(содержащая яркости пикселов полутонового изображения),
либо три таких матрицы (R, G и B-компоненты) с идентичными размерами, объединенные в одном объекте.
Имеются методы извлечения матриц
Никакие другие модели, кроме RGB, не поддерживаются.
Единственная цель существования интерфейса —
обеспечить простой способ хранения изображений
и применения к ним алгоритмов, умеющих обрабатывать матрицы.
Для RGB-картинок такое применение практически тривиально:
как правило, это либо простой покомпонентый вызов метода,
рассчитанного на тип Matrix<? extends PArray>,
для каждой из 3 матриц R, G, B, либо — что более типично для задач анализа —
получение матрицы яркостей пикселов по стандартной формуле 0.299r+0.587g+0.114b
и применение метода уже к ней.
Такую матрицу яркостей, в случае цветного изображения,
автоматически возвращает метод
Интерфейса Image2D достаточно для большинства алгоритмов обработки и анализа,
включая всевозможную фильтрацию, выделение границ, структуры, анализа частиц и других геометрических объектов.
Алгоритмы, которые нуждаются в специальном анализе других типов цветности,
например, HLS, оперируют другими классами, обычно аналогичными Image2D.
Далее в этой статье мы будем рассмотривать примеры алгоритмов,
обрабатывающих объекты типа Image2D.
Часть I. Чтение и создание изображения: класс SimplestTutorialDemo
Далее мы рассмотрим — с душераздирающей подробностью —
маленький и очень простой класс SimplestTutorialDemo.
Это специально написанный учебный класс, состоящий из static-методов
и решающий настолько тривиальные задачи, насколько я смог придумать.
Зато он решает их множеством способов, начиная с самых простых и кончая самыми правильными.
В процессе совершенствования способа решения вы сможете шаг за шагом
ознакомиться с фундаментальными концепциями библиотек AlgART.
Если есть возможность, рекомендую открыть исходник этого класса в какой-нибудь оболочке, позволяющей легко получать JavaDoc-комментарии к любому вызываемому библиотечному методу: изучение этих комментариев может помочь пониманию. Исходный файл класса доступен здесь: SimplestTutorialDemo.java.
Прежде чем начинать разбор класса, надо сделать одно замечание.
Все методы этого класса (и прочих учебных классов, рассматриваемых в этой статье),
используют специальную аннотацию @Name, импортируемую из пакета
com.simagis.plugin3.
Об этом следует упомянуть, главным образом, для того, чтобы вы не обращали на нее внимания.
Никакого влияния на исполнение кода она не оказывает,
и никакого значения для понимания используемых приемов она не имеет.
На самом деле эта аннотация нужна для единственной цели:
приписать параметрам методов символьные имена,
которые, в отличие от обычных имен аргументов методов, сохраняются в скомпилированном байт-коде
и доступны для внешнего приложения, вызывающего этот класс.
Благодаря информации об именах параметров, такое приложение может упростить запуск методов,
предоставляя визуальный интерфейс для настройки конкретных параметров.
Примером такого приложения является SIMAGIS:
система обработки изображений, ради которой, в значительной степени, создавались обсуждаемые библиотеки.
Эта система позволяет также создавать и визуализировать изображения типа Image2D,
что, как легко видеть, довольно полезно, если вы хотите проверить рассматриваемые методы на практике.
1. Конверсия RGB-изображения в полутоновое
Не думайте, что я на самом деле собираюсь описывать, как решается такая задача.
Пока рано. Речь идет всего лишь о вызове готового метода, предусмотренного
в интерфейсе Image2D.
Итак, вот наш первый пример:
public static Image2D toGrayscale(Context context, @Name("image")Image2D image) {
ImageContext imageContext = context.as(ImageContext.class);
Matrix<? extends PArray> m = image.i();
Image2D result = imageContext.newGrayscaleImage2D(m);
return result;
}
Уже декларация метода требует от нас остановиться и внимательно рассмотреть его первый параметр.
Что это за Context?
Имею честь представить концепцию контекста, реализованную в библиотечном пакете
net.algart.contexts.
Расскажу о контекстах в двух словах. Как обычно, желающие могут прочитать обстоятельные
JavaDoc-комментарии в документации к пакету.
Если очень коротко, контекст алгоритма (или, в общем случае, контекст произвольных вычислений или других операций) — это информация, которая не настолько важна, чтобы служить входными данными или параметрами алгоритма, но которая в то же время способна оказать влияние на его работу.
Наверно, самый очевидный пример контекста — сама Java-машина
(или операционная система в языках типа C/C++). Именно она отвечает за
исполнение любого оператора new, отводящего блок памяти,
а без такого оператора затруднительно написать даже самый простейший алгоритм.
Внутренняя информация JVM, прежде всего, доступный объем памяти в "куче",
безусловно, влияет на работу любого алгоритма, хотя формально не содержится в его входных параметрах.
Действительно, при одном количестве памяти алгоритм выдаст OutOfMemoryError,
а при другом — сработает нормально.
Это означает, что в принципе можно считать JVM неявным параметром,
передаваемым каждому алгоритму. (Кстати, неявное становится явным,
когда мы пишем native-метод Java-класса на языке C:
каждому native-методу передается указатель на среду исполнения Java-машины.)
JVM и ее память — контекст глобальный, общий для всего Java-приложения.
Такой контекст не надо как-то специально передавать в библиотечные классы,
решающие те или иные задачи.
Другим примером глобального контекста может служить файловая система:
с помощью системного свойства (System.getProperty)
алгоритм, требующий непомерных объемов временных данных,
может узнать каталог временных файлов операционной системы
и сохранить наиболее "тяжелые" временные объекты на диске.
Еще один пример — логгеры java.util.logging:
они настраиваются глобально для всего приложения и при этом иногда используются внутри алгоритмов.
Если вы прочитали package summary к пакету net.algart.arrays,
вы могли обратить внимание, что эта библиотека использует немало контекстной информации подобного рода,
передаваемой через системные свойства (system properties).
К сожалению, не всякую информацию, полезную для исполнения алгоритма, можно передать "глобально", настраивая те или иные системные свойства, глобальные константы и т.п. Скажем, рассмотрим типичную проблему: показать пользователю ход исполнения алгоритма. Ведь не все алгоритмы заканчивают работу в долю секунды. Что, если решаемая задача требует нескольких минут или даже часов? Еще хуже, если требуемое время сильно и сложным образом зависит от параметров. В этом случае, когда пользователь выбрал неудачные параметры алгоритма, надо дать ему понять, что задача будет решаться не меньше часа и неплохо бы ее прервать (или пойти обедать).
Как "научить" абстрактный математический алгоритм, например,
решающий систему уравнений или фильтрующий изображение,
показывать проценты своего исполнения?
Глобальные настройки приложения (вроде каталога временных файлов) здесь не спасают:
у приложения может быть несколько окон, и в каждом может параллельно исполняться свой алгоритм,
требующий отдельного визуального элемента для вывода процентов.
Можно, конечно, передать функции (или классу) специальный параметр, скажем, JProgressBar,
если вам не жаль уродовать изящную архитектуру чисто алгоритмического модуля
столь "приземленными" деталями.
Но что делать, если, кроме процента выполнения, понадобится что-то еще?
Например, специальный слушатель, реагирующий на кнопку Stop и останавливающий расчеты?
(Стандартный вызов Thread.interrupt, увы, в текущей версии Java несовместим
с библиотекой net.algart.arrays: об этом можно прочесть в JavaDoc.)
Возникает ситуация, напоминающая причины, по которым в современные языки добавили механизм исключений.
А именно: чтобы предусмотреть передачу алгоритму всех возможных полезных ему вещей,
нужно загромоздить простой и ясный API вызова алгоритма передачей всех этих вещей.
Интерфейс Context, передаваемый первым параметром в наш самый первый метод —
это в меру изящное (будем надеяться) решение, предлагаемое библиотеками AlgART.
Сам по себе интерфейс Context почти тривиален
и не позволяет алгоритму узнать ничего "полезного".
Основной метод этого интерфейса выглядит так:
public <T extends Context> T as(Class<T> contextClass);
Этот метод — своего рода "шлюз", позволяющий алгоритму узнать практически все, что угодно.
Идея в том, что метод as возвращает некий
частный контекст — экземпляр некоторого наследника Context.
А вот этот наследник уже может иметь практически полезные методы, необходимые алгоритму.
Предполагается, что вызывающий код
(в нашем случае приложение, вызывающее методы SimplestTutorialDemo)
передаст такую реализацию Context, которая сможет вернуть все необходимые
алгоритму частные контексты. Создаются такие реализации достаточно просто.
Более того, набор поддерживаемых контекстов может загружаться в виде сервис-провайдеров
и определяться уже после компиляции конечного приложения.
Желающие могут посмотреть JavaDoc к пакету net.algart.contexts
или исходники законченных примеров, такие, как SimpleImageContext.
Первая же строчка вызываемого метода выполняет операцию извлечения частного контекста.
Это вызов метода второго варианта as:
ImageContext imageContext = context.as(ImageContext.class);
Методу as передается класс ImageContext.class
— конкретный частный контекст, нужный нашему алгоритму.
Единственная его задача — создание экземпляра Image2D по имеющейся AlgART-матрице
или набору AlgART-матриц. Что и делается в конце нашего метода toGrayscale:
Image2D result = imageContext.newGrayscaleImage2D(m);
Что произойдет, если реализация Context, переданная приложением в наш метод,
"не умеет" возвращать экземпляры ImageContext?
В этой ситуации будет возбуждено необъявляемое исключение UnsupportedContextException.
Если вернуться к аналогии с виртуальной машиной (в качестве "неявного" контекста),
эту ошибку можно сравнить с ситуацией, когда мы исполняем Java-приложение на виртуальной
машине, не поддерживающей нужный набор библиотечных классов (скажем,
на если мы запускаем программу на устаревшей версии JVM,
или если мы пытаемся выполнить J2EE-программу на виртуальной машине J2SE).
Правильно документированный класс должен декларировать
в JavaDoc-комментариях полный набор необходимых ему контекстов —
так же, как обычно декларируется необходимая классу версия Java.
(Наш учебный класс, ради простоты, вообще не снабжен документитацией.)
Большинство классов требуют, как минимум, поддержки стандартых контекстов,
реализуемых стандартным классом DefaultContext (см. JavaDoc).
ImageContext — типичный пример частного контекста-фабрики.
Мы и далее будем сталкиваться с ситуациями, когда для генерации экземпляров абстрактных интерфейсов
привлекаются частные контексты-фабрики.
(Сравните: первым рассмотренным выше примером контекста была JVM, реализующая оператор new,
т.е. базовый оператор-фабрику языка Java.)
Такой подход значительно повышает гибкость системы.
Приложение, вызывающее алгоритмический метод, который должен вернуть некую сущность
— реализацию интерфейса,
может передать через контекст такую фабрику, которая будет создавать экземпляры наиболее
удобного для приложения типа.
Так, реализация ImageContext, передаваемая системой SIMAGIS,
создает такие Image2D, которые изначально "умеют" храниться в ячейках таблиц SIMAGIS.
Это значительно упрощает интеграцию в систему классов вроде нашего
SimplestTutorialDemo (в терминах SIMAGIS они называются "плагинами").
Фабрики — далеко не единственный пример контекстной информации.
В дальнейших методах мы увидим, как из параметра типа Context,
как "чертики из коробочки", "выскакивают" самые различные частные контексты,
сообщающие алгоритму необходимые дополнительные сведения или позволяющие сделать
другие полезные вещи.
Собственно, мы рассмотрели почти весь метод toGrayscale.
Он ведь абсолютно тривиален. Все, что здесь происходит, помимо
получения контекста и возврата результата, это выделение яркостной компоненты изображения:
Matrix<? extends PArray> m = image.i();
Если входное изображение image было цветое (RGB),
то матрица m будет содержать
яркости каждого пиксела, рассчитанные по формуле 0.299r+0.587g+0.114b.
Если полутоновое, то m будет содержать непосредственно значения интенсивности пикселов.
Как в действительноти это реализовано, мы пока рассматривать не будем:
решение подобных задач будет темой одной из следующих глав.
После получения m, метод контекста newGrayscaleImage2D превращает
полученную матрицу обратно в экземпляр Image2D, уже заведомо полутоновой.
Он и возвращается методом.
2. Вычисление средней яркости самым плохим способом: покоординатный цикл
Надо полагать, читатель уже изрядно устал. Уже столько всего рассказано, а мы ведь до сих пор не сделали ровно ничего интересного. Мы даже пока не пробовали решить столь простую задачу, как чтение численного значения яркости конкретного пиксела.
Что ж, вот наш следующий метод:
public static double meanOf_1(Context context, @Name("image")Image2D image) {
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long dimX = m.dimX();
long dimY = m.dimY();
double sum = 0.0;
for (long i = 0; i < dimY; i++) {
for (long j = 0; j < dimX; j++) {
long index = m.index(j, i);
sum += a.getDouble(index);
}
}
return sum / (dimX * dimY);
}
Вычисление средней яркости всех пикселов — наверно, самая простая возможная задача анализа изображения. Попробуем разобрать приведенный выше пример решения этой задачи: наверно, самый очевидный из всех возможных (правда — забегая вперед — и чуть ли не самый худший).
Как и раньше, в качестве первого параметра здесь передается контекст.
Однако он никак не используется. На самом деле это редчайшее исключение.
В реальных, не учебных методах контекст нужен почти всегда.
Параметр Context в декларации метода сохранен "на всякий случай".
Когда вы сами будете писать практические методы, если даже вам покажется,
что контекст не нужен, на всякий случай всегда включайте его в список параметров.
Вполне возможно, что по мере будущего развития и усложнения метода контекст все же понадобится,
а изменить декларацию будет уже нельзя по соображениям совместимости.
Кстати, заметим: по негласной традиции, контекст всегда должен передаваться самым первым параметром.
Первый оператор метода нам уже знаком: это получение матрицы интенсивностей m.
В случае цветного изображения, это фактически означает автоматическую конверсию в
"ближайшее по яркости" полутоновое изображение.
Очень многие промышленные алгоритмы анализа и распознавания изображений
начинаются с такого оператора: достаточно редко цветовая информация настолько важна,
что реально помогает проанализировать (например, измерить) изображенные предметы.
Следующим оператором мы "спускаемся" еще на один шаг по иерархии вложенных объектов:
получаем из матрицы m линейный AlgART-массив a, хранящий
(строка за строкой) все элементы матрицы. Напомню, что AlgART-матрица
— всего-навсего пара "AlgART-массив" + "набор размерностей".
Поэтому метод извлечения массива, dimX и dimY.
Посмотрим на следующий далее цикл.
Для каждой пары координат i и j вычисляется индекс в линейном
массиве a, и затем по индексу из массива извлекается вещественное числа,
которое прибавляется к общей сумме sum:
long index = m.index(j, i);
sum += a.getDouble(index);
(Напоминаю: все индексы и размеры в AlgART-массивах и AlgART-матрицах 63-разрядные,
поэтому используется тип long.)
На что здесь надо обратить внимание? Прежде всего, на порядок аргументов метода index.
Первым идет индекс по x-координате (т.е. j), вторым — по y (т.е. i).
Если бы мы имели дело с трехмерной матрицей, следующим аргументом был бы индекс по z.
Это необходимо запомнить.
Если бы матрица хранилась в двумерном Java-массиве m[][],
то, вероятно, порядок употребления индексов был бы обратный: m[i][j]
(хотя, разумеется, это вопрос вкуса программиста).
Далее, обратите внимание на число аргументов метода index.
Если вы заглянете в интерфейс Matrix, вы увидите, что это —
метод с переменным числом параметров (vararg).
Что произойдет, если вы случайно укажете недостаточное или слишком большое количество аргументов?
Согласно JavaDoc-комментариям к Matrix, методы этого интерфейса,
в том числе index, ведут себя так, как будто число измерений матрицы бесконечено.
Но при этом все размеры матрицы "за пределами" истинного числа размерностей считаются равными 1,
а все недостающие аргументы метода index подразумеваются равными 0.
Так, наша двумерная матрица "очень похожа" на трехмерную матрицу
dimX x dimY x 1 и на четырехмерную матрицу
dimX x dimY x 1 x 1.
Мы имеем право вместо IndexOutOfBoundsException:
у нашей матрицы если только одна, нулевая "плоскость" в трехмерном пространстве
и только одна, нулевая "гиперплоскость" в четырехмерном.
Перейдем теперь к следующему оператору: Matrix<? extends PArray> говорит о том,
что мы имеем дело с любым из 8 примитивных типов Java.
Интерфейс PArray — общий предок всех частных интерфейсов,
описывающих массивы конкретных примитивных типов. В тех интерфейсах,
например, ByteArray, имеются специальные методы для получения значений нужной разрядности:
getByte для ByteArray, getBit (результат boolean)
для BitArray, и т.д.
Но уже в самом общем интерфейсе PArray объявлен метод getDouble,
позволяющий прочитать числовое значение любой разрядности с автоматической
конверсией к типу double.
Правила конверсии четко специфицированы в JavaDoc.
Обратите на них внимание: их надо запомнить!
Наиболее важно для нас следующее:
по соглашению библиотеки AlgART, типы данных byte и short
везде, где возможно, интерпретируются как беззнаковые.
Иначе говоря, cчитается, что каждый элемент AlgART-массива ByteArray
содержит целое число от 0 до 28−1=255,
а каждый элемент AlgART-массива ShortArray
содержит целое число от 0 до 216−1=65535.
(Однако, типы int и long считаются знаковыми:
изменяющимися от -231 до 231−1 и от -263 до 263−1
соответственно.)
В частности, для элемента байтового массива,
содержащего двоичное число 11111111, метод getDouble возвращает 255
(а не −1, как можно было бы подумать).
Да, это противоречит традиции языка Java, в котором все
целочисленные типы данных всегда знаковые.
Но это намного удобнее почти во всех алгоритмах,
имеющих дело с массивами 8- или 16-битовых целых чисел.
В частности, это удобно при работе с изображениями.
Ведь яркость пиксела описывается неотрицательным числом.
При разрядности int или long вполне можно "пожертвовать"
последним 32-м (64-м) битом и представлять пикселы неотрицательными значениями
Java-типов int и long. И действительно,
для реальных изображений при такой разрядности наш объект Image2D всегда
будет содержать 0 в старшем (знаковом) бите каждого элемента.
Однако 8- и даже 16-битовая точность не настолько велика, чтобы игнорировать один бит.
Здесь гораздо удобнее использовать для представления неотрицательной яркости все 8 или 16 битов.
Разумеется, при необходимости (и желании) вам ничто не мешает проинтерпретировать 8- и 16-битовые элементы AlgART-массивов и матриц в классическом смысле, как знаковые величины. Это потребовало бы некоторого усложения кода: проверки, что мы имеем дело с конкретным частным подинтерфейсом, и соответствующим приведением типа. Например:
long index = m.index(j, i);
double value;
if (a instanceof ByteArray) {
value = (byte)((ByteArray)a).getByte();
// getByte() возвращает тип int, а не byte, причем
// этот int-результат неотрицательный (0..255),
// в соответствии с соглашениями библиотеки.
// Поэтому необходим дополнительный оператор
// приведения типа: (byte)(...)
} else if (a instanceof ShortArray) {
value = (short)((ShortArray)a).getShort();
// getShort(), аналогично, возвращает неотрицательный
// int (0..65535), поэтому необходим оператор
// приведения типа: (short)(...)
} else {
value = a.getDouble(index);
}
sum += value;
На практике, однако, такая необходимость вряд ли будет встречаться часто.
На этом мы заканчиваем разбор метода. Последний его оператор вполне тривиален: конечно, средняя яркость есть сумма всех элементов, деленная на их количество, т.е. на dimX * dimY.
3. Вычисление средней яркости чуть менее плохим способом: цикл по массиву
Пора заняться усовершенствованием нашего алгоритма. На самом деле, наш цикл, который смотрелся бы вполне уместно при обработке классического двумерного массива Java, при обработке AlgART-матрицы — одно из наихудших решений в плане эффективности. Рассмотренный только что пример полезен с точки зрения обучения, так как знакомит с некоторыми важными концепциями доступа к элементам. Но на практике так писать не следует почти никогда — разве что если быстродействие вас совершенно не интересует.
Самый очевидный недостаток цикла "бросается в глаза", даже если ничего не знать об архитектуре AlgART-массивов. Раз все равно все элементы хранятся в линейном массиве, зачем делать вложенные циклы по x и по y? Ведь их можно просуммировать одним циклом по линейному массиву?
Исправим это:
public static double meanOf_2(Context context, @Name("image")Image2D image) {
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long length = a.length();
double sum = 0.0;
for (long k = 0; k < length; k++) {
sum += a.getDouble(k);
}
return sum / length;
}
Здесь мы вообще игнорируем размерности матрицы, а сразу извлекаем исходный AlgART-массив
и работаем исключительно с ним. Как результат, исчез вызов метода index.
Хотя метод index кажется тривиальным, он все-таки тратил определенное время.
Не только на вычисление индекса (j+dimX*i), но и на проверку аргументов:
как всякий добропорядочный метод, он проверяет, что переданные покоординатные индексы корректны
(не отрицательны и меньше соответствующих размеров матрицы).
В итоге, на моем компьютере новая версия обрабатывает большую 8-битовую картинку
примерно на 30% быстрее.
Заметим, что метод index в действительности используется весьма редко,
особенно во внутренних циклах алгоритма.
Чаще всего элементы "перебираются" последовательно, и на каждой итерации достаточно
просто перейти к следующему элементу линейного AlgART-массива.
И даже когда нужен более сложный порядок анализа элементов,
обычно эффективнее работать непосредственно с индексом в линейном массиве:
например, прибавлять к нему заранее заготовленные смещения, соответствующие тем или иным
сдвигам координтат в матрице.
Дополнительным преимуществом нового алгоритма оказалась нечувствительность к числу измерений. Без каких-либо изменений такой цикл способен вычислить среднее значение и 3-мерной матрицы, и 1-мерного массива. Как уже говорилось, такая универсальность присуща очень многим профессиональным алгоритмам обработки AlgART-матриц.
4. Вычисление средней яркости: пора вспомнить о пользователе
Наш метод решает слишком простую задачу, чтобы выполняться долго. Тем не менее, последняя его реализация еще достаточно плоха, и поэтому способна продемонстрировать проблемы, возникающие у сложных "долгоиграющих" алгоритмов. По крайней мере, если передать нашему методу матрицу, сравнимую по размерам с оперативной памятью компьютера, алгоритм "задумается" весьма ощутимо. Может быть, на несколько секунд или даже минут.
Что может предпринять пользователь в это время? Да ничего. Или сидеть и ждать, или переключиться на другую задачу. Наш цикл не содержит никаких операторов, которые позволили бы его прервать или хотя бы показать, какой процент работы уже готов.
Перед тем как переходить к дальнейшей оптимизации метода, вспомним про контексты и ликвидируем указанные недостатки. А именно, "научим" алгоритм прерываться и показывать проценты исполнения. На самом деле, правила хорошего тона требуют, чтобы такие вещи умел практически любой профессиональый алгоритм — за исключением гарантированно быстрых методов, вроде решения одного квадратного уравнения или вставки одного элемента в сбалансированное дерево.
Итак:
public static double meanOf_3(Context context, @Name("image")Image2D image) {
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long length = a.length();
double sum = 0.0;
for (long k = 0; k < length; k++) {
sum += a.getDouble(k);
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, false);
}
}
return sum / length;
}
Здесь мы получаем два частных контекста:
контекст прогресса ProgressUpdater и
контекст прерываний InterruptionContext,
и используем их, чтобы решить две задачи:
визуализацию хода исполнения и возможность прерывания алгоритма.
Если мы вызовем метод meanOf_3 из "доброжелательной" системы,
такой, как SIMAGIS,
предоставляющей "умные" реализации всех стандартных и многих нестандартных частных контекстов,
то система сможет "красиво" показать исполнение нашего цикла в виде — например,
"полоски прогресса" (JProgressBar) — и остановить наш цикл при помощи соответствующей кнопки
в пользовательском интерфейсе.
Но что делать, если же мы захотим вызвать этот метод из более простой программы, в которой не предусмотрены средства для визуализации хода исполнения и прерывания работы?
В этом случае к нашим услугам "контекст-заглушка",
возвращаемый методом DefaultContext,
реализующего сразу несколько стандартных, общеупотребительных частных контекстов,
которые предусмотрены в пакете net.algart.contexts и могут понадобиться
практически в любой задаче.
Нужные нам сейчас ProgressUpdater и InterruptionContext
относятся к их числу и поддерживаются объектом ProgressUpdater не покажет никаких процентов исполнения,
а частный контекст InterruptionContext не поможет остановить вычисления.
Однако наш метод, по крайней мере, не выдаст исключения и решит свою задачу.
(Впрочем, на самом деле контекст-заглушка не совсем тривиален.
Если он используется для получения стандартных контекстов, реализуемых классом
DefaultContext, то, и правда, возвращаемые контексты не делают ничего "умного".
Но если мы потребуем от контекста-заглушки вернуть нестандартный контекст,
такой как использованный в первом нашем примере ImageContext,
то контекст-заглушка предпримет дополнительную попытку обслужить запрос,
обратившись к набору так называемых сервис-провайдеров.
С помощью этой техники внешнее приложение способно обеспечить "заглушками"
даже нестандартные контексты, возможно, применяемые в библиотечных модулях.
Подробнее см. JavaDoc-комментарии к классам AbstractContext и
DefaultContext.)
Теперь рассмотрим, как ProgressUpdater и
InterruptionContext используются в алгоритме.
В нашем методе мы время от времени,
а именно, раз в 65536 итераций, обращаемся к методам этих интерфейсов:
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, false);
}
Метод InterruptionContext проверяет тот факт, что пользователь пытается
остановить вычисления: например, что была нажата кнопка Stop.
В этом случае метод выбрасывает исключение net.algart.contexts.InterruptionException,
в результате чего метод естественным образом завершается.
Программа может отловить это исключение, чтобы удостовериться, что метод действительно был прерван
и, например, сообщить об этом пользователю.
Обратите внимание: в отличие от стандартного InterruptedException,
исключение InterruptionContext необъявляемое. Это не случайно.
Вспомните: по определению, контекст — это дополнительная,
факультативная информация, не настолько важная, чтобы влиять на контракт метода.
Быть может, мы захотим применять данный метод для обработки сравнительно небольших изображений,
где он работает считанные миллисекунды. В этом случае возможность прервать его
не только не нужна, но может даже оказаться вредной, нарушающей логику вызывающего кода.
(Наш метод, кстати, действительно работает почти мгновенно для любого
изображения "добропорядочных" размеров, скажем, 1024x1024.)
В такой ситуации нормальным решением является передача контекста, не умеющего прерываться,
например InterruptionException было объявляемым,
его пришлось бы добавить в декларацию метода и тем самым потребовать
от пользователей обработки — например, перехвата.
Получилось бы крайне нелогично:
программа вызывает наш метод с полной гарантией, что InterruptionException
произойти не может, а тем не менее анализировать это исключение необходимо.
Пришлось бы писать код наподобие следующего, категорически осуждаемого
всеми учебниками по Java:
double mean;
try {
mean = SimplestTutorialDemo.meanOf_3(DefaultContext.getInstance(), image);
// "пустышка" DefaultContext.getInstance()
// заведомо не позволит методу прерваться
} catch (InterruptionException ex) {
// страшное и ужасное решение: игнонируем исключение
}
Чтобы не нужно было писать такие ужасы, исключение
InterruptionException сделано необъявляемым (RuntimeException).
Перейдем к методу ProgressUpdater
объявлен следующим образом:
public void updateProgress(double readyPart, boolean force);
Смысл его достаточно прост: хорошая реализация контекста прогресса
должна в этом методе показать пользователю, что готовая часть вычислений составляет
readyPart (величина от 0.0 до 1.0).
В самом простейшем случае, данный метод может вывести на экран надпись вроде следующей:
Параметр force не столь очевиден.
Дело в том, что алгоритмы, работающие с контекстом прогресса,
обычно вызывают метод updateProgress часто.
Как правило, нет никакого смысла при каждом вызове реально обновлять
соответствующий графический элемент, такой как JProgressBar.
Не только нет смысла, но и опасно: так можно "из лучших побуждений" замедлить
алгоритм в сотни раз.
Передавая в качестве этого параметра значение false,
алгоритм "говорит" приложению:
данное обновление прогресса можно проигнорировать,
так как я скоро либо снова вызову updateProgress, либо закончу вычисленияВ этом случае считается, что приложение имеет право пропустить очередное обновление экранного элемента, если с последнего обновления прошло мало времени (скажем, меньше 10 миллисекунд).
Как правило, это совершенно нормальное поведение, и поэтому чаще всего
в качестве параметра force передается false.
Но существуют ситуации, когда это не так. А именно, может оказаться, что алгоритм собирается
выполнить какую-то "долгоиграющую" операцию, не сопровождающуюся
регулярным обращением к контексту прогресса.
Например, это может быть выделение большого блока памяти, или обращение к
"долгому" методу сторонней библиотеки, не поддерживающей контексты AlgART.
В этом случае полезно гарантировать, что визуальный элемент, показывающий прогресс
выполнения, обновится, и индикатор JProgressBar не "застрянет"
в каком-то случайном предыдущем положении. Для этого достаточно вызвать
updateProgress с параметром force=true.
Например, в нашем методе можно было бы гарантировать такой вызов при последней
итерации цикла:
if ((k & 0xFFFF) == 0 || k == length - 1) {
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, k == length - 1);
}
Напоследок заметим, что "не слишком частое" обращение к контекстам — это общее правило,
которому рекомендуется всегда следовать. Было бы грубой ошибкой
вызывать методы ic.checkInterruption и pu.updateProgress
при каждой итерации внутреннего цикла, которая, в нашем случае,
требует лишь считанных тактов процессора.
Да, качественная реализация контекста, наверно, предоставит достаточно быстродействующие методы,
но вряд ли они будут работать совсем "мгновенно".
Умеренным решением является обращение к таким контекстам, как
ProgressUpdater и InterruptionContext,
не реже, чем каждые 10–100 миллисекунд — чтобы обеспечить плавное изменение "полоски прогресса"
и практически мгновенную останвку вычислений — но и не чаще, чем, скажем, раз в несколько микросекунд.
Вызов один раз в 65536 итераций простого суммирования — подходящий компромисс.
5. Вычисление средней яркости: учимся писать эффективно
Наши предыдушие решения базировались на методе getDouble.
Это простой путь, поэтому мы начали именно с него.
Но, к сожалению, это не очень эффективно.
Как мы увидим в данном разделе, нашу задачу можно решить в десятки раз быстрее.
Метод getDouble, а также его "близнецы" из частных интерфейсов,
описывающих конкретные типы массивов —
ByteArray.getByte, ShortArray.getShort и т.д. —
в современной реализации, в среднем, расходуют до сотни тактов процессора.
На сегодняшних персональных компьютерах это означает десятки наносекунд.
(Это средняя цифра для случая последовательного чтения массива.
Обращение "вразброс" к элементам большого массива может работать значительно медленнее.)
Для сравнения, простое обращение к обычному массиву Java,
благодаря оптимизатору Java HotSpot,
обычно требует считанных тактов, может быть, даже одного такта
(если нужный элемент "попадает" в кэш процессора).
Операция суммирования — основное действие, выполняемое нашим циклом —
тоже укладывается в несколько тактов, даже для вещественных чисел.
Почему же метод getDouble такой медленный?
Тут полезно немного отвлечься от нашего алгоритма вычисления средней яркости
и рассказать кое-что о том,
что стоит "за кулисами" внешне простого метода getDouble.
Вспомните: AlgART-массивы имеют 63-битовую адресацию (индексы типа long).
Один массив способен хранить практически сколь угодно большой объем данных,
ограниченный лишь оперативной и дисковой памятью.
И это достаточно важно: уже сегодня объемы оперативной памяти в несколько гигабайтов
для простой "персоналки" вполне типичны, и эту память надо уметь эффективно использовать.
Даже обычные "плоские" изображения в некоторых случаях превышают по объему гигабайт,
а для трехмерных, пространственных моделей такие объемы — норма.
Для адресации же байтового массива, более длинного, чем 2 Гб,
32-битовый тип int оказывается недостаточным.
В отличие от AlgART-массивов, все стандартные структуры языка Java,
предназначенные для хранения последовательности элементов,
имеют 31-битовую адресацию (тип индекса int) и изначально ограничены
примерно 2 миллиардами элементов. Это касается и стандартных массивов языка,
и класса ByteBuffer из java.nio, и коллекций из java.util.
Есть только одно очевидное исключение: классы для работы с файлами,
такие как RandomAccessFile.
Все это означает, что 63-битовая адресация AlgART-массивов, реализованная в рамках
языка Java, достигается далеко не бесплатно.
Чтобы преодолеть 2-миллиардный лимит, библиотака AlgART ассоциирует массив
с дисковым файлом (как правило, временным, удаляемым при завершении программы).
Файл делится на относительно небольшие блоки, размером по несколько мегабайтов.
Всякий раз, когда происходит обращение к AlgART-массиву, в частности, через метод getDouble,
система определяет соответствующий блок файла и мапирует его, вызовом FileChannel.map,
в буфер типа ByteBuffer.
Затем обращение переадресуется к методам
класса ByteBuffer (или его аналогов для других примитивных типов:
ShortBuffer, IntBuffer, и т.д.).
Заметим: даже для файлов, не превышающих (предельного для Java) объема 2 Гб,
используются сравнительно маленькие блоки, не более нескольких мегабайтов.
Это необходимо на 32-разрядных операционных системах, которые,
независимо от объема RAM, ограничивают доступное адресное пространства
одной программы лимитом порядка 2 гигабайтов.
Если бы мы попытались отобразить (мапировать) файл размером, скажем, 1 Гб
в единственный ByteBuffer,
вместо того чтобы "дробить" его на маленькие блоки,
то несколько таких AlgART-массивов уже переполнили бы адресное пространство, доступное
всей виртуальной машине Java.
Разумеется, несколько наиболее часто используемых блоков файла кэшируются.
Экземпляры ByteBuffer, отображенные на самые "популярные" блоки,
используются многократно. Переотображение (вызов FileChannel.map)
происходит лишь тогда, когда требуется доступ к новому участку AlgART-массива,
отсутствующему в кэше.
Реальный алгоритм кэширования и переотображения довольно сложен.
Каждый раз, когда мы обращаемся хотя бы к одному элементу массива,
приходится выполнить ряд проверок и, возможно, коррекций внутренних структур данных.
Более того, эти операции обычно синхронизуются,
чтобы сделать возможной параллельную обработку одного AlgART-массива из нескольких потоков.
(Далее мы увидим, что распараллеливание действительно очень полезно и реально повсеместно
применяется библиотеками AlgART на многопроцессорных или многоядерных компьютерах.)
Неудивительно, что вызов getDouble требует некоторого времени.
Возможно, это время сократится в будущих версиях библиотек AlgART и компиляторов Java,
но, вероятнее всего, методы типа getDouble
всегда будут значительно проигрывать простому обращению к Java-массиву
вроде byte[] или short[].
Каков же выход из положения? Для последовательных алгоритмов вроде нашего, просматривающих массив элемент за элементом, решение вполне традиционно — блочный доступ: чтение за один вызов достаточно длинного блока элементов с размещением их в обычном массиве Java. Такой вызов в библиотеках AlgART работает с максимальной эффективностью и дает практически такую же скорость, какую можно было бы получить при прямой работе с Java-массивом (или указателем языка C).
Даже при беглом взгляде на базовый интерфейс Array,
вероятно, вы обратите внимание на метод getData,
который позволяет обеспечить блочный доступ: этот метод читает целый блок последовательных элементов.
Однако, необходимо предупредить читателя:
это не тот метод, который, скорее всего, понадобится вам в прикладных алгоритмах
последовательной обработки массива.
Метод getData (и его "близнец" getBits
из интерфейса BitArray) действительно бывает необходим в низкоуровневых,
сложных программах, реализующих некоторые нетривиальные алгоритмы и абстракции.
Но для прикладных задач, как правило, удобнее — и эффективнее —
применять другую технологию, называемую "буфер данных".
Буфер данных представлен в пакете net.algart.arrays
интерфейсом DataBuffer.
(Не путайте с классом Buffer из java.nio:
между ним и DataBuffer нет ничего общего.)
Экземпляр такого интерфейса возвращается методами buffer,
расположенными в базовом интерфейсе Array.
Подобно самим AlgART-массивам, буфера данных имеют частные разновидности,
соответствующие конкретным типам и представленные 9-ю наследниками DataBuffer:
а именно, DataByteBuffer, DataShortBuffer и т.д.,
заканчивая DataObjectBuffer.
Я настоятельно рекомендую внимательно изучить JavaDoc-комментарий
к интерфейсу DataBuffer.
В этом комментарии подробно описаны основные понятия и приемы, связанные
с использованием буферов данных.
Полное понимание концепции DataBuffer весьма важно
для правильного использования этого удобного и мощного инструмента.
Итак, рассмотрим четвертую реализацию алгоритма подсчета средней яркости,
опирающуюся на применение DataBuffer:
public static double meanOf_4(Context context, @Name("image")Image2D image) {
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
DataBuffer buf = a.buffer(DataBuffer.AccessMode.READ);
double sum = 0.0;
for (buf.map(0); buf.hasData(); buf.mapNext()) {
ic.checkInterruption();
pu.updateProgress((double)buf.position() / (double)a.length(), false);
if (a instanceof BitArray) {
long[] data = (long[])buf.data();
sum += PackedBitArrays.cardinality(data,
buf.fromIndex(), buf.toIndex());
} else if (a instanceof CharArray) {
char[] data = (char[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof ByteArray) {
byte[] data = (byte[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k] & 0xFF;
} else if (a instanceof ShortArray) {
short[] data = (short[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k] & 0xFFFF;
} else if (a instanceof IntArray) {
int[] data = (int[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof LongArray) {
long[] data = (long[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof FloatArray) {
float[] data = (float[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof DoubleArray) {
double[] data = (double[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else {
throw new AssertionError("Must not occur");
}
}
return sum / a.length();
}
Сразу бросается в глаза, что размер метода резко увеличился.
В нем появилось 8 веток, отвечающих за обработку разных примитивных типов элементов.
Раньше универсальная поддержка всех примитивных типов была "спрятана" в методе
getDouble, имеющемся в интерфейсе PArray.
Конверсия элементов прочих типов в число типа double
занимает так мало времени по сравнению с прочей "кухней", реализуемой
методом getDouble (как и другими методами доступа к одному элементу),
что затратами на конверсию можно было пренебречь.
Но буфера данных DataBuffer, в отличие от методов доступа к одному элементу,
не поддерживают автоконверсии типов.
Это оправдано: буфера данных разработаны для реализации максимально эффективных алгоритмов,
где, как правило, неявное преобразование типов всех элемента нежелательно.
Ценой эффективности является усложнение кода: необходимость повторения почти одинакового кода
для разных примитивных типов.
Код с ветвлением по 8 типам, увы, присущ многим алгоритмам, которые хотят эффективно обработать числовые AlgART-массивы, не теряя при этом универсальности — применимости к любому из восьми примитивных типов. Может быть, когда-нибудь в языке появятся средства, позволяющие упростить написание такого кода для примитивных типов (вроде tempalates языка C++). Но пока приходится писать 8 веток. Впрочем, как мы увидим в дальнейших главах, при программировании обработки изображений редко приходится "опускаться" до таких приземленных вещей, как работа с отдельными элементами матрицы.
Перейдем к анализу приведенного кода. Рассмотрим первый новый для нас оператор:
DataBuffer buf = a.buffer(DataBuffer.AccessMode.READ);
Смысл оператора достаточно прост: для заданного AlgART-массива a
возвращается буфер данных, соответствующий этому массиву и предназначенный для чтения данных.
Примерно так же, как для коллекции java.util
можно получить соответствующий ей объект Iterator.
Здесь стоит обратить внимание на две вещи. Во-первых, мы явно указываем
режим доступа READ. Зачем?
Это — "подсказка" библиотеке, что нам не понадобится модифицировать массив.
Можно было бы и обойтись без такой подсказки.
Имеется перегруженная версия метода buffer без аргументов, выбирающая
режим автоматически.
Однако существуют ситуации (хоть и не очень типичные),
когда буфер данных с режимом доступа, выбранным по умолчанию, будет работать
медленнее, чем буфер с режимом READ.
Правилом "хорошего тона" является всегда явно указывать, какой режим работы
с буфером данных нам необходим — благо это ничего не стоит.
Кроме возможной оптимизации, это улучшает читабельность кода, ибо явно
указывает на намерения программиста.
Надо заметить, что режим доступа DataBuffer.AccessMode.READ
— это не более чем "подсказка". Такой режим никоим образом не гарантирует,
что возвращенный буфер данных не позволит изменить элементы массива.
(Для получения таких гарантий нужна другая технология: метод Array. См. JavaDoc, в частности, комментарий к пакету — package summary.)
Если вы все же попытаетесь, пользуясь буфером данных в режиме READ,
модифицировать исходный массив,
может быть, это получится, может быть, ваша попытка будет проигнорирована,
а может быть, изменится лишь часть массива — это не оговорено документацией.
Все, что можно сказать: реализация DataBuffer постарается,
по возможности, сэкономить время, избегая ненужных вам операций записи данных в массив.
Вторая вещь, о которой иногда полезно задуматься — размер буфера (capacity).
Иначе говоря, число последовательных элементов AlgART-массива, которые
будут "за один раз" читаться из массива в буфер и сохраняться
в обычной памяти (массиве) языка Java.
По умолчанию, выбирается некоторый "разумный" размер, обеспечивающий
почти оптимальную скорость обмена с AlgART-массивом: вероятнее всего
(но отнюдь не обязательно) несколько тысяч элементов.
Вы можете задать этот объем "вручную": у метода buffer
есть соответствующие перегруженные версии.
Так, при дальнейшей оптимизации нашего метода было бы невредно явно задать размер буфера,
чтобы гарантировать, что буфер не будет длиннее 215−1=32767 элементов.
Это позволило бы просуммировать в одном цикле, заведомо без переполнения,
все элементы типа byte или short,
используя переменную-сумматор типа int.
Впрочем, на данном этапе мы не будем настолько углубляться в оптимизацию.
Идем дальше. Обратите внимание на организацию цикла:
for (buf.map(0); buf.hasData(); buf.mapNext()) {
. . .
}
Напоминает итераторы по коллекциям java.util, не правда ли?
Однако есть и отличия. Прежде всего, буфер данных ориентирован на произвольный,
а не последовательный доступ, поэтому его можно — и нужно — явно "позиционировать"
на некоторый участок AlgART-массива. Так как мы собираемся обрабатывать массив
в естественном порядке, слева направо, то цикл начинается с позиционирования
буфера на начало массива: map.
Чаще всего это
При переходе к следующей итерации цикла вызывается метод map, вычислив следующую позицию
в массиве: в JavaDoc приведен соответствующий пример цикла.
Но вариант с map или mapNext.
При последнем вызове mapNext "сдвинет" буфер на позицию,
равную длине AlgART-массива. Это корректная ситуация, но буфер в этом случае
считается пустым. Соответственно, метод false, и цикл естественным образом завершится.
Рассмотрим теперь тело цикла. Вначале идет уже знакомое нам обращение к контекстам прерываний
и прогресса. (Удобнее вызвать контекст прогресса в начале, а не в конце цикла,
так как количество уже обработанных данных оказывается равным текущей начальной
позиции буфера, возвращаемой методом
Далее начинается ветвление по типам элементов. Все ветки начинаются с вызова
метода ByteArray
это будет массив byte[], для ShortArray — массив short[],
и т.д. С различными типами Java-массива нужно работать по-разному:
это главная причина, по которой необходимы 8 веток.
Заметим, что затребованный фрагмент AlgART-массива вовсе не обязательно
окажется в начале Java-массива buffer.
Но
С массивом, полученным методом READ
это может привести к изменениям в исходном массиве.
Существует важный частный случай AlgART-массивов: так называемые простые массивы,
являющиеся "оболочкой" вокруг самых обыкновенных, стандартных массивов Java.
Такие AlgART-массивы часто применяются, например, для оптимизации.
В случае простого AlgART-массива метод asImmutable,
то DataBuffer не позволит нарушить неизменяемость: в этом случае
DataBuffer будет копировать данные в отдельный Java-массив.)
Первая из 8 веток цикла посвящена случаю битового массива: BitArray.
Это самый сложный случай, поскольку биты в AlgART-массивах, так же как и в буферах
данных, упакованы в 64-битовые целые числа типа long.
Соответственно, метод long[].
Обрабатывать такой упакованный массив "вручную" было бы крайне неудобно.
Так, простейшее чтение бита с индексом index выражается следующим громоздким оператором:
(data[(int)(index >>> 6)] & (1L << (index & 63))) != 0
К счастью, в составе пакета net.algart.arrays предусмотрен специальный
класс PackedBitArrays, содержащий сервисные функции для большинства
задач, возникающих при обработке битов, упакованных в массивы long[].
В нашем примере мы используем готовую высокоэффективную функцию cardinality,
решающую в точности нашу задачу: подсчет количества единичных битов
(или, что то же самое, суммы) в произвольном фрагменте упакованного битового массива.
Все прочие ветки алгоритма похожи друг на друга и практически очевидны. Но, вероятно,
вы заметили, что вместо методов
Методы long.
Ведь обычный Java-массив long[] может
содержать более 231−1 битов. Например, даже 32-разрядные версии Java
в состоянии создать массив long[] длиной в гигабайт, а это уже 233 битов.
И хотя маловероятно, что вам потребуется DataBuffer такого объема
(впрочем, кто знает, какими "порциями" мы будем обрабатывать сверхбольшие массивы
через несколько лет в 64-разрядных OS), корректный код для случая битов должен
опираться на 64-разрядные методы
В противоположность битовому случаю, для всех остальных типов элементов
мы имеем дело с обычным, неупакованным Java-массивом byte[], short[] и т.д.
В нем по определению не может быть более 231−1 элементов,
более того, для его индексации пригоден только тип int, но не long.
Чтобы не заставлять программиста всякий раз приводить результаты методов
int, интерфейс DataBuffer
предусматривает 32-битовые версии этих методов
В заключение, обратите внимание на операторы "& 0xFF" и "& 0xFFFF"
при обработке типов byte и short.
Эти операторы нужны, чтобы, подобно предыдущим версиям нашего метода,
обработать 8- и 16-битовые элементы как беззнаковые.
Метод getDouble выполнял такую коррекцию внутри себя,
теперь же мы должны выполнить преобразование явно.
Мы закончили рассмотрение первого примера обработки AlgART-массива,
построенного на применении DataBuffer.
Относительная сложность такого решения окупается с лихвой:
на моем компьютере новый метод работает примерно в 10 раз быстрее,
чем предыдущий вариант.
6. Вычисление средней яркости: библиотечная функция все-таки лучше
Последний разобранный нами вариант подсчета среднего достаточно эффективен. Можно было бы выполнить ряд очевидных оптимизаций, например, заменить, где возможно, вещественное сложение целочисленным. Но это уже не так интересно.
На самом деле, если мы хотим найти оптимальное решение некоторой задачи, в 90% случаев нужно последовать классическому рецепту: поискать готовое решение в библиотеках. Почти наверняка оно окажется не хуже вашего. А если даже оно не оптимально, вероятнее всего, алгоритм будет оптимизирован в одной из следующих версий библиотки.
Как и следовало ожидать, такая простая задача, как суммирование элементов массива,
уже предусмотрена в библиотеках AlgART.
Это метод sumOf библиотечного класса Arrays.
С его использованием решение нашей задачи записывается совсем лаконично:
public static double meanOf_5(Context context, @Name("image")Image2D image) {
ArrayContext arrayContext = new DefaultArrayContext(context);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
double sum = Arrays.sumOf(arrayContext, a);
return sum / a.length();
}
По сравнению с предыдущими примерами, здесь добавилось только одно понятие.
Это контекст массивов: интерфейс ArrayContext.
На самом деле ArrayContext реализует ту же самую концепцию,
что и контексты типа Context, рассмотренные нами раньше.
Но ArrayContext, расположенный, в отличие от Context,
в пакете net.algart.arrays, несколько проще.
ArrayContext — это как бы "пакет net.algart.contexts в миниатюре".
В отличие от нетривиальной системы интерфейсов и классов,
здесь мы имеем дело всего с одним интерфейсом —
реализующим, однако, практически все задачи,
необходимые при работе с массивами на уровне пакета net.algart.arrays.
В модулях, ориентированных исключительно на обработку AlgART-массивов и матриц,
часто достаточно работать с ArrayContext.
Более мощный пакет net.algart.contexts обычно привлекается,
когда, кроме AlgART-массивов, необходимы другие сущности, такие, как
необходимые нам изображения Image2D
(про которые ArrayContext, конечно, ничего не "знает").
Разумеется, общий контекст Context допускает автоматическое
преобразование к ArrayContext. В нашем примере преобразование выполняется
в первой строчке:
ArrayContext arrayContext = new DefaultArrayContext(context);
Именно такой контекст, ArrayContext, следует передавать
вычислительным функциям пакета net.algart.arrays,
в частности, функции Arrays.sumOf.
Насколько наш новый метод лучше предыдущего, выполняющего суммирование "вручную"?
Конечно, библиотечная функция Arrays.sumOf содержит мелкие оптимизации
вроде целочисленного суммирования, которыми мы пренебрегли в учебном методе
meanOf_4.
Но главное преимущество sumOf — распараллеливание вычислений.
Вообще, распараллеливание — одно из важных достоинств большинства расчетных методов, предусмотренных в библиотеках AlgART. Современые компьютеры часто оснащены несколькими процессорами либо многоядерными процессорами, позволяющими параллельно выполнить несколько задач, например, просуммировать несколько фрагментов одного большого AlgART-массива. Для этого достаточно создать несколько потоков и поручить каждому выполнение своей части задачи. Таким образом на многопроцессорном или многоядерном компьютере можно добиться многократного ускорения вычислений.
При помощи пакета java.util.concurrent распараллеливание
программируется довольно просто. Более того,
для распареллеливания обработки массивов в большинстве случаев
можно использовать библиотечный класс Arrays.ParallelExecutor,
который "берет на себя" большую часть рутинной работы по организации
совместной работы потоков и взаимодействию с контекстом ArrayContext.
Профессиональный метод Arrays.sumOf, действительно,
опирается на этот класс.
Деталями распараллеливания — например, количеством параллельных потоков
— тоже управляет соответствующий контекст
(либо часть ArrayContext, либо независимый интерфейс
net.algart.contexts.ArrayThreadPoolContext).
В JavaDoc вы можете найти детали такого управления.
Если вы решите задействовать параллельность в своих собственных вычислительных методах,
рекомендую посмотреть, как реализован в библиотеке метод sumOf
(или один из похожих методов, скажем, rangeOf)
и изучить документацию к Arrays.ParallelExecutor.
Даже если ParallelExecutor окажется для ваших целей недостаточен,
в любом случае рекомендую использовать ArrayThreadPoolContext:
тогда приложения смогут управлять вашим распараллеливанием таким же образом,
как и распараллеливанием в библиотеках AlgART.
7. Генерация константного изображения простейшим способом: цикл по массиву
Мы научились получать на входе алгоритма изображения, представленные AlgART-матрицами, и анализировать несколькими способами значения яркостей пикселов (т.е. элементы матрицы). Рассмотрим теперь обратную задачу: создание нового изображения и заполнение его какими-то значениями, для начала — некоторой числовой константой.
Начнем с простейшего, хотя и неэффективного способа: поэлементного присваивания элементов. Мы уже говорили, что для таких задач поокординатный цикл по матрице (по y и по x) никакого смысла не имеет, разве что вам хочется слегка замедлить алгоритм. Начнем с цикла по линейному массиву: аналога разобранного выше простейшего способа вычисления суммы элементов в очень похожем цикле.
public static Image2D constant_1(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("value")float value)
{
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
Matrix<UpdatableFloatArray> m = mm.newFloatMatrix(dimX, dimY);
UpdatableFloatArray a = m.array();
long length = a.length();
for (long k = 0; k < length; k++) {
a.setFloat(k, value);
}
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(m);
return result;
}
В отличие от предыдущих примеров, мы собираемся решить новую для нас задачу:
создать "с нуля" AlgART-матрицу (т.е. отвести память),
элементы которой мы будем заполнять константным значением.
Размеры матрицы и желаемое значение — это аргументы метода dimX,
dimY, value.
AlgART-матрица, также как и AlgART-массив — это интерфейс.
Для создания экземпляров матриц и массивов, в соответствии с хорошими традициями шаблона Factory,
служит класс под названием MemoryModel... впрочем, нет, не класс, а опять интерфейс!
Почему интерфейс и почему MemoryModel?
MemoryModel, или модель памяти — фундаментальное понятие библиотек AlgART.
Архитектура AlgART-массивов изначально спроектирована так, чтобы физический способ хранения данных
был легко и произвольно расширяем.
Этот способ хранения называется моделью памяти.
Основная задача интерфейса MemoryModel — служить фабрикой,
создающей экземпляры массивов и матриц любого желаемого типа и размера.
В зависимости от того, какая реализация MemoryModel применяется
(т.е. какая выбрана конкретная модель памяти),
будут создаваться различные реализации массивов и матриц:
практически неотличимые друг от друга с точки зрения использования,
но совершенно разные по "внутреннему устройству".
Например, существует простая модель памяти: класс SimpleMemoryModel,
реализующий интерфейс MemoryModel.
В этом случае AlgART-массив — всего лишь "оболочка" вокруг обычного Java-массива,
хранящегося в Java-куче. Это самый эффективный вариант с точки зрения быстродействия,
но такие массивы ограничены размерами памяти JVM и предельной длиной 231−1 элементов
(несколько больше для битовых массивов, за счет упаковки битов в long-значения).
Но есть и альтернативная, большая модель памяти LargeMemoryModel.
Здесь AlgART-массив реально представляет собой дисковый файл, а операции доступа к его элементам
приводят к отображению фрагментов файла в память: мы рассказывали об этом
выше, когда разбирали механизм работы метода getDouble.
Этот вариант несколько медленнее, но не накладывает никаких ограничений на размер массивов,
за исключением естественного предела — свободного места на диске —
и чисто теоретического лимита на число элементов 263−1
(т.е. более 9 миллионов терабайт).
Другой интересный пример модели памяти (впрочем, не имеющий прямого отношения к обработке изображений)
— комбинированная модель памяти CombinedMemoryModel.
Она предназначена для хранения массивов объектов, а не примитивных типов,
и позволяет хранить AlgART-массив однотипных структур в одном или нескольких других AlgART-массивах,
уже состоящих из элементов примитивных типов.
Например, AlgART-массив объектов типа "точка" (2 числа x и y, допустим, типа float),
внешне "выглядящий" как обычный массив объектов и похожий на классический ArrayList,
при помощи такой модели можно сохранить в AlgART-массиве float-значений,
в котором поочередно будут записываться x- и y-координаты каждой точки.
Такой способ позволит как сэкономить память — на точку будет израсходовано ровно 2*4=8 байтов,
в отличие от ArrayList или массива объектов Java, где добавятся изрядные накладные
расходы на поддержание отдельного экзепляра объекта — так и преодолеть лимит 2 Гб
и задействовать для хранения точек свободное дисковое пространство.
Разумеется, профессиональное приложение должно каким-то образом выбрать желаемую модель памяти,
которой будет рекомендовано пользоваться библиотечным алгоритмам для создания своих массивов и матриц.
В сложном приложении, возможно, модель памяти будет отличаться от стандартных, предусмотренных
в пакете net.algart.arrays, хотя бы своими настройками
(вроде каталога временных файлов, в котором следует создавать большие массивы).
Для передачи этой информации в алгоритм, как обычно, используется контекст.
Речь идет о частном контексте памяти: класс ArrayMemoryContext.
Его задача — вернуть модель памяти MemoryModel, которую должен
использовать алгоритм для создания любого AlgART-массива или матрицы
(кроме, быть может, совсем маленьких массивов, для которых SimpleMemoryModel
является оптимальным выбором).
Это и происходит в начале нашего метода:
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
Если в качестве параметра context в данный метод
передан "контекст-заглушка" net.algart.arrays.globalMemoryModel":
см. метод SimpleMemoryModel.
Располагая экземпляром MemoryModel, нет проблем создать матрицу желаемого
типа и размера. В этом примере мы, не мудрствуя лукаво, создаем вещественную матрицу
типа float:
Matrix<UpdatableFloatArray> m = mm.newFloatMatrix(dimX, dimY);
Тип AlgART-массива в данном случае — UpdatableFloatArray,
т.е. допускающий модифицацию элементов (но не изменение длины) массив вещественных
чисел float.
Следующий цикл вполне тривиален:
long length = a.length(); // можно было бы написать dimX*dimY, но так нагляднее
for (long k = 0; k < length; k++) {
a.setFloat(k, value);
}
Метод setFloat — "брат-близнец" подробно разбиравшегося выше метода
getDouble, объявленный в конкретном интерфейсе UpdatableFloatArray.
С тем же успехом можно было бы использовать setDouble:
чуть более общий метод, объявленный в интерфейсе UpdatablePArray.
В дальнейших разделах мы заменим setFloat более эффективными решениями.
Последние два оператора знакомы нам по первому разобранному нами примеру, когда мы возвращали полутоновой эквивалент RGB-картинки:
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(m);
Как и там, мы используем частный контекст ImageContext,
чтобы на основании AlgART-матрицы создать изображение типа Image2D.
В качестве результата возвращается полутоновое изображение, яркость всех пикселов которого
равна переданной константе value.
Что значит "яркость равна переданной константе"? На самом деле, вопрос интерпретации вещественного
числа в качестве яркости, на данный момент — вне нашей компетенции.
Это решает программа, которая вызвала наш метод и собирается что-то делать с полученным Image2D:
визуализировать, экспортировать в BMP-файл, делать что-то еще.
(Может быть, это вообще не яркость, а уровень высот в будущей топографической карте,
которую предполагается показать в виде трехмерной поверхности.)
В качестве "разумного умолчания" я рекомендую принять следующее соглашение: для вещественных чисел значение 0.0 соответствует нулевой яркости (черные пикселы), значение 1.0 — максимальной яркости (белые пикселы), значения между 0.0 и 1.0 — промежуточным яркостям. Значения вне диапазона 0.0...1.0 "некорректны" и могут показываться, например, как черные (отрицательные) и белые (большие чем 1.0). Если бы мы создавали изображение с другим типом элементов (что мы и будем делать в следующих разделах), то рекомендуемые соглашения такие:
- тип
byte: яркость увеличивается от 0 (черный цвет) до 28−1=255 (белый); - тип
short: яркость увеличивается от 0 (черный цвет) до 216−1=65535 (белый); напоминаем, что в библиотеках AlgART типыbyteиshortсчитаются беззнаковыми; - тип
char: так же, какshort(хотя кому нужен типcharдля обработки изображений, остается загадкой); - тип
int: яркость увеличивается от 0 (черный цвет) до 231−1 (белый), отрицательные значения в качестве яркости являются некорректными; - тип
long: яркость увеличивается от 0 (черный цвет) до 263−1 (белый), отрицательные значения в качестве яркости являются некорректными; - тип
boolean(битовые массивы): 0 (false) означает черный цвет, 1 (true) — белый.
Подчеркиваю: это лишь рекомендация для визуализации и экспорта в других форматы изображений. Таким соглашениям следует, например, система SIMAGIS, хотя там есть возможность, при желании, настроить другие диапазоны для представления яркостей. Для программирования алгоритмов данные соглашения обычно не имеют значения.
8. Генерация константного изображения: произвольная разрядность результата
В предыдущем примере мы создаем вещественную матрицу с элементами фиксированного
типа, а именно float.
На самом деле такое решение редко является приемлемым.
Почему именно float? Потому что так удобнее разработчику — раз аргумент
value такого типа?
А если мы хотим получить байтовое (8-битовое) изображение?
В конце концов, необходимость экономить память и место на диске никто не отменял,
а 8-битовая матрица в 4 раза компактнее.
В "настоящих", серьезных алгоритмах, создающих новое изображение, таких как фильтр удаления шума, тип элементов результата (разрядность) обычно определяется входными данными. Скажем, алгоритм удаления аддитивного шума может создать результирующее изображение с той же разрядностью, что и исходное, или получить желаемый примитивный тип непосредственно в качестве аргумента метода.
Исправимся. Изменим предыдущий метод, чтобы он вернул константное изображение произвольной разрядности, которую мы укажем в параметре. Заодно вспомним о пользователе и добавим контексты прерываний и прогресса, подробно рассмотренные нами ранее.
public static Image2D constant_2(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Class<?> eType = typeOf(elementType);
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
UpdatablePArray a = m.array();
long length = a.length();
for (long k = 0; k < length; k++) {
a.setDouble(k, value);
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)k / (double)length, false);
}
}
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(m);
return result;
}
Теперь желаемый тип элементов результата — один из 8 примитивных типов Java —
описывается строчным параметром elementType, а значение-заполнитель
value — уже не float, а double,
которым можно описать практически любое значение любого примитивного типа...
Стоп! Почему, собственно, elementType строчный?
Ведь ясно, что нужен параметр типа Class!
На самом деле тут нет никаких "глубокомысленных" причин. Просто так удобнее.
Если вы все-таки когда-нибудь вызовете этот метод (на что я надеюсь) —
или написав собственный тест-утилиту, или применив мощную оболочку
SIMAGIS — вам придется как-то задавать этот параметр.
А если даже не вызовете, то во всяком случае этот метод вызывал я,
пока писал этот текст, а об удобстве автора тоже надо подумать.
Удобнее, если значение параметра можно ввести
при исполнении программы, а не "зашивать" в код теста.
Самый простой способ задать примитивный тип (не самый лучший, но зато вполне очевидный) —
набрать его имя, т.е. строчку "boolean", "byte" и т.д.
В учебном классе SimplestTutorialDemo есть простенькая сервисная private-функция
typeOf, преобразующая подобную строку в объект типа Class,
описывающий один из примитивных типов. Эта функция вызывается в нашем методе, чтобы превратить
elementType в переменную eType типа Class
(вернее, Class<?>, в соответствии с традициями современной Java).
Текст typeOf невелик, скучен и потому здесь не приводится. При желании, я полагаю,
вы можете запросто написать десяток подобных функций.
Начало нового метода почти повторяет предыдущий вариант, только добавляется
извлечение уже знакомых нам контекстов прогресса и прерываний.
Затем, как и ранее, мы создаем матрицу при помощи модели памяти mm,
но на этот раз указываем желаемый класс примитивного типа eType.
Это делается почти так же просто, как и создание матрицы конкретного типа:
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
Так, так... А зачем тут параметр UpdatablePArray.class?
Согласно здравому смыслу, а также описанному в самом начале понятию матрицы
и традициям нормальных языков программирования, чтобы создать матрицу,
вполне достаточно указать ее размеры и тип элементов!
То, что она окажется Matrix<? extends UpdatablePArray>, уже вытекает
из значения аргумента eType, который, как предполагается
(если функция typeOf написана без ошибок), всегда описывает примитивный тип!
Тут мне остается лишь принести извинения за язык Java. Его технология generics,
по крайней мере в версиях Java 5 и Java 6, скажем так, кажется автору недостаточно развитой.
Может быть (и многие надеются на это), в следующих версиях ее расширят,
но пока, во избежание трудноуловимых ошибок, generics-методы генерации
порой приходится снабжать методы "костылями": параметрами типа Class,
с точки зрения логики совершенно избыточными.
Что же все-таки делает этот параметр?
Взгляните на декларацию вызываемого метода newMatrix:
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<T> arraySupertype, Class<?> elementType, long ...dim);
Давайте попытаемся убрать первый параметр, чтобы сделать метод более "логичным":
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<?> elementType, long ...dim);
(По секрету: должен сознаться, к стыду своему, что в процессе создания библиотек в одной из ранних версий так оно и было. И на старуху бывает проруха...)
На первый взгляд все нормально: мы можем присвоить результат любой матрице типа Matrix<T>,
где T — произвольный updatable-массив, т.е. допускающий изменения элементов.
(Кстати: конечно, updatable.
Кому нужна свежесозданная матрица, если ее элементам не удастся ничего присвоить.)
Конкретный тип массива T, скажем, UpdatableByteArray, будет определяться типом
элементов elementType, например:
Matrix<UpdatableByteArray> m = mm.newMatrix(byte.class, dimX, dimY);
Будет ли?... А вот и нет. В языке Java, при всей его замечательности в прочих отношениях, информация о generic-типах стирается в момент компиляции. Во время исполнения программы такой оператор присваивания выполняется в точности так, как если бы мы написали просто:
Matrix m = mm.newMatrix(byte.class, dimX, dimY);
Что отсюда следует? Следует возможность написать следующую страшную вещь, которая, что ужаснее всего, без ошибок отработает во время выполнения:
Matrix<UpdatableByteArray> m = mm.newMatrix(short.class, dimX, dimY);
Сам по себе вызов newMatrix, какой бы хитроумной она ни была, не в состоянии
усмотреть в таких параметрах чего-либо "крамольного". Ну просят его создать матрицу с элементами
short, что ж, он и создаст. Откуда же методу newMatrix знать,
что глупый программист собирается присвоить созданную матрицу переменной типа
Matrix<UpdatableByteArray>, а не Matrix<UpdatableShortArray>?
Что будет дальше? Оператор присваивания спокойно отработает —
ведь после "стирания" в нем не осталось никаких намеков на UpdatableByteArray!
Сравните: если бы речь шла об обычных, не "генерализованных" классах и интерфейсах,
то никакого стирания бы не было, а компилятор потребовал бы от нас вставить оператор приведения типа.
При исполнении этого оператора, в случае несоответсвия типов,
произошло бы исключение времени выполнения ClassCastException.
Например:
UpdatableByteArray a = (UpdatableByteArray)mm.newUnresizableArray(
short.class, arrayLen);
// - Генерируется ClassCastException при приведении типа,
// так как метод возвращает тип UpdatableShortArray,
// несовместимый с UpdatableByteArray.
// Если же убрать приведение типов "(UpdatableByteArray)",
// будет синтаксическая ошибка, так как newUnresizableArray
// возвращает UpdatableArray, а не UpdatableByteArray.
Какие были бы последствия описаного метода newMatrix?
Самые печальные. При указании ошибочного типа элементов матрицы
ошибка останется незамеченной и "выплывет" где-то позже.
Возможно, при первой попытке "поработать" с созданной матрицей,
когда мы, скажем, попытаемся присвоить массив UpdatableByteArray.
Компилятор в этом случае не потребует явно приводить тип (как было бы при отсутствии generics),
поскольку "считает", что матрица Matrix<UpdatableByteArray> в принципе
не может содержать никакого другого массива, кроме UpdatableByteArray.
Приведение типа произойдет неявно, и программа выдаст ClassCastException
на "совершенно ровном" месте. Да и то, если повезет: скажем, код, ориентированный
на матрицы общего вида Matrix<? extends UpdatablePArray>
выполнится без исключений,
но, быть может, абсолютно неверно, если программист, видя тип конкретной переменной
Matrix<UpdatableByteArray>, существенно использовал 8-битовость элементов.
Правильное решение —
явно передать методу аргумент типа Class<T>, где T —
нужный нам generic-тип. Так и сделано в библиотеке AlgART. Для удобства читателя,
повторим декларацию из интерфейса Matrix:
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<T> arraySupertype, Class<?> elementType, long ...dim);
(Кстати сказать, аналогичный прием используется
и в других методах, возвращающих результат с generics-параметром,
например, в методе Matrix.cast.)
Что изменилось, когда мы добавили параметр Class<T> arraySupertype?
С одной стороны, теперь метод знает, какой именно тип массива T
должен быть у создаваемой матрицы. Если тип элемента ему не соответствует,
то метод самостоятельно сгенерирует исключение ClassCastException:
ошибка далее не распространится.
С другой стороны, компилятор теперь получил возможность проконтролировать тип результата.
Ведь переданный параметр Class сам обладает параметром T, причем
тем же самым, который указан в качестве параметра матрицы.
Если мы попытаемся "обмануть" метод newMatrix, указав соответствующие друг другу,
но неверные arraySupertype и elementType,
то мы просто не сможем присвоить результат переменной-матрице с неподходящим generics-типом.
Скажем, следующий код попросту не скомпилируется:
Matrix<UpdatableByteArray> m =
mm.newMatrix(UpdatableShortArray.class, short.class, dimX, dimY);
// ошибка: несовместимые параметры T у результата метода и переменной m
В нашем алгоритме мы "заказываем" тип массива UpdatablePArray.class:
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
Это значит, что метод newMatrix непременно вернет матрицу,
generics-параметр которой соответствует массиву с элементами примитивного типа, т.е.
является UpdatablePArray или его наследником.
Такую матрицу, естественно, мы имеем право присвоить переменной типа
Matrix<UpdatablePArray> и, конечно же,
переменной более общего типа Matrix<? extends UpdatablePArray>.
Мы выбираем второй, более общий вариант: см. вступление про матрицы и generics.
Дальнейшая часть метода достаточно очевидна.
Производится цикл по массиву и каждому его элементу присваивается значение value.
На этот раз используется общий метод setDouble интерфейса UpdatablePArray,
применимый к массивам любого примитивного типа.
Подобно методу getDouble, метод setDouble позволяет
писать общие, хотя и не самые эффективные алгоритмы, обрабатывающие массивы элементов
любого примитивного типа. Подобно getDouble, этот метод выполняет автоматическое
преобразование типов. И подобно getDouble, этот метод нарушает традиции
языка Java, воспринимая значения типа byte и short как беззнаковые...
Стоп. А правда ли нарушает? Загляните в JavaDoc-комментарий к setDouble.
Как ни странно, в отличие от getDouble, в этом комментарии нет никаких
оговорок насчет типов byte и short. Простым английским языком сказано:
"Sets the element #index by convertion from double,
as xxx
(byte, short, int, long,
float, double or char),
or as value!=0.0 for boolean element type."
В чем дело? Неужели ошибка? Может быть, getDouble и setDouble
не соответствуют друг другу — записав значение методом setDouble,
при чтении методом getDouble мы рискуем получить нечто совершенно другое?
Конечно, никакой ошибки здесь нет — иначе, надо полагать, я бы не стал об этом писать.
Однако разобраться в этом весьма важно, дабы не попасть "впросак" потом,
когда вам понадобится реализовать аналогичную конверсию самостоятельно —
скажем, при заполнении AlgART-массива через DataBuffer.
Чтобы понять, почему в setDouble "все чисто", надо внимательно проанализировать, что
на самом деле делает кажущийся столь простым оператор приведения типа
setDouble.
Пусть value — переменная типа double,
содержащая значение 200, и мы пытаемся выполнить setDouble с таким аргументом
для случая байтового массива UpdatableByteArray.
Мнения библиотек AlgART и языка Java насчет интерпретации такой величины в качестве байта
расходятся. Для нас, "любителей AlgART", это нормальный беззнаковый байт, равный 200.
Для языка Java, такое значение не может храниться в переменной типа byte:
эти переменные изменяются от −128 до +127.
Что произойдет, если все же выполнить приведение типа setDouble?
Если вы напишете коротенький тест, вы убедитесь, что
Почему? Потому, что язык Java вначале приводит вещественный тип к
"универсальному" целочисленному типу int, а только потом конвертирует
тип int в более узкие типы byte, short или char.
Именно такое поведение зафиксировано в спецификации языка.
И если приведение double к int сопровождается усечением
слишком больших значений до диапазона Integer.MIN_VALUE..Integer.MAX_VALUE,
то конверсия int в byte (как и всякая конверсия более
широкого целого типа к более узкому) означает всего-навсего отбрасывание старших битов.
В результате 200.0 превращается вначале в положительное int-значение 200
(в двоичной системе это 11001000),
а уже это число далее превращается в байт, состоящий из тех же самых 8 битов 11001000.
С точки зрения Java, полученный байт равен -56, а с нашей, "беззнаковой" точки зрения
он как раз содержит 200! Иначе говоря, все в порядке: последующий вызов getDouble,
действуя в соответствии с "беззнаковыми" соглашениями, для такого байта вернет правильное
значение 200.0. Т.е. произойдет в точности то, что требуется.
Будьте внимательны! В качестве "универсальной разменной монеты" для целых чисел
язык Java применяет именно int, а не long.
Поэтому, если мы попытаемся повторить те же действия с чрезвычайно большим
(больше Integer.MAX_VALUE) целым значением,
представленным типом double, и переменной (типом элемента) int,
поведение будет другим! Впрочем, по-прежнему согласующимся с документацией
на методы getDouble и setDouble.
А именно, если попытаться привести очень большое число double,
скажем, 1012, к типу int (оператором long
с последующим отбрасыванием "лишних" битов. Вместо этого, оператор Integer.MAX_VALUE.
На этом мы заканчиваем рассмотрение данного примера и переходим к разбору более
эффективных решений, не использующих метод setDouble.
9. Генерация константного изображения: да здравствует лень
Сейчас мы могли бы пойти тем же путем,
что и при вычислении средней яркости:
заменить поэлементный цикл вызовов setDouble использованием
буферов данных (DataBuffer), возможно, добавить распараллеливание.
Однако это довольно скучно. Кроме того, решения, которые мы изложим далее,
во многих случаях оказываются более удобными и эффективными.
Поэтому мы оставим перевод предыдущего примера на технику DataBuffer
читателю в качестве упражнения. В некоторых алгоритмах
такой способ заполнения массива, безусловно, является правильным решением, и невредно
его освоить. На случай, если читатель окажется настолько храбрым
(и при этом недостаточно ленивым — вопреки заголовку параграфа),
что действительно возьмется за это упражнение, дам несколько подсказок.
Цикл заполнения массива m)
при помощи DataBuffer должен быть аналогичен циклу чтения матрицы
через DataBuffer, разобранному нами ваше
в алгоритме вычисления средней яркости. С той очевидной разницей,
что теперь массив
Во-первых, разумеется, режим чтения DataBuffer.AccessMode.READ
(параметр метода a.buffer) теперь не годится. Нужно указать режим
DataBuffer.AccessMode.READ_WRITE. Или ничего не указывать,
вызвав метод
Во-вторых, в конце цикла, после заполнения очередного массива
Будьте внимательны! Если вы забудете вызвать READ, в некоторых случаях ваш метод,
тем не менее, будет работать правильно!
Например, если модель памяти mm, использованная для создания матрицы
— это SimpleMemoryModel.
Напоминаю, что в этом случае AlgART-массив является "оболочкой" вокруг обычного Java-массива.
Соответственно, результат метода
Осталось добавить, что в классе PackedBitArrays вы найдете метод,
нужный для заполнения константой упакованного битового массива.
А также, что на этот раз
поддержка беззнаковости для типов byte
и short не потребует специальных усилий
(в отличие от цикла вычисления суммы, где пришлось использовать операторы
&0xFF и &0xFFFF):
вспомните рассуждения о методе setDouble в конце предыдущего параграфа.
Удачи в решении упражнения!
Перейдем к обещанному альтернативному решению задачи. Вот оно:
public static Image2D constant_3(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
Class<?> eType = typeOf(elementType);
if (dimX < 0)
throw new IllegalArgumentException("Negative dimX");
if (dimY < 0)
throw new IllegalArgumentException("Negative dimY");
long length = Arrays.longMul(dimX, dimY);
if (length == Long.MIN_VALUE)
throw new TooLargeArrayException();
PArray a;
if (eType == boolean.class) {
a = Arrays.nBitCopies(length, value != 0.0);
} else if (eType == char.class) {
a = Arrays.nCharCopies(length, (char)value);
} else if (eType == byte.class) {
a = Arrays.nByteCopies(length, (byte)value);
} else if (eType == short.class) {
a = Arrays.nShortCopies(length, (short)value);
} else if (eType == int.class) {
a = Arrays.nIntCopies(length, (int)value);
} else if (eType == long.class) {
a = Arrays.nLongCopies(length, (long)value);
} else if (eType == float.class) {
a = Arrays.nFloatCopies(length, (float)value);
} else if (eType == double.class) {
a = Arrays.nDoubleCopies(length, (double)value);
} else {
throw new AssertionError("Must not occur");
}
Matrix<? extends PArray> m = Matrices.matrix(a, dimX, dimY);
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(m);
return result;
}
По сравнению с предыдущим решением, сразу обращает на себя внимание странная вещь: куда-то пропали контексты прерываний и прогресса. Что это — небрежность автора, которому больше не хочется думать о пользователе?
На самом деле, эти контексты стали не нужны.
По очень простой причине: данный метод выполняется практически мгновеннно.
Вернее, не весь метод, а его основная часть, от начала до вызова
newGrayscaleImage2D — метода, находящегося "вне нашей компетенции"
и поставляемого внешним приложением через контекст ImageContext.
На моем компьютере основная часть метода, создающая AlgART-матрицу m,
отрабатывает примерно за 50 микросекунд,
причем независимо от размеров создаваемой матрицы.
Очевидно, контексты прерываний и прогресса при такой скорости просто не нужны.
(Собственно, их и вставить было бы некуда: в этом решении нет ни циклов,
ни методов, принимающих контексты в качестве аргумента.)
В чем секрет такого "супербыстродействия"? Если вы имели дело с методом
nCopies из класса java.util.Collections, вы, наверно, уже догадались.
Итак — добро пожаловать в мир лени!
На более "официальном" языке применяемый механизм называется
ленивые, или отложенные вычисления.
Это значит, что методы nXxxCopies, являющиеся "сердцем" новой реализации,
сами по себе не выполняют заказанную задачу — заполнение константой
некоторой области памяти. Вместо этого они возвращают реализацию интерфейса
PArray, в которой методы доступа всегда возвращают
элементы, равные заказанной константе. Создание экземпляра такой реализации
почти не требует ни времени, ни памяти. Подобные реализации AlgART-массивов
мы будем называть ленивыми массивами.