Шел один из зимних дней, а я сидел на работе и размышлял над математической задачей, которая мне волей-неволей досталась… Двойная сумма, двумерный массив, казалось бы, в чем тут может быть проблема?
Но как оказалось, что такая тривиальная процедура, как свертка последовательностей, даже при наличии полного комплекта математических пособий и книг по языку программирования D, мне просто не по зубам.
Даже в одномерном варианте…
Тогда, в то утро 2014 года, я думал, что это конец — я так и не смог решить эту задачу и сделать одномерную свертку, которая определяется достаточно просто, о чем свидетельствует описание процедуры в Википедии и подробный алгоритм на C++. Если быть до конца честным, то я даже не вчитывался в математику и решил организовать алгоритм, что называется «в лоб», просто проведя обыкновенную трансляцию в уме с одного языка программирования на другой, и вот тут меня (как и всегда, в общем-то) ждал пренеприятнейший сюрприз…
Алгоритм просто не сработал, хотя был полностью идентичной копией (за исключением, конечно, прямой работы с памятью — в D есть такая замечательная штука, как динамические массивы практически какой угодно мерности, а потому пляски с бубном и memset‘ы становятся ненужными) и мне просто пришлось изобрести свой велосипед (к сожалению, не сохранился, да и первый провал с медианным фильтром был в том же файле, что характерно).
Но, недавно, сквозь дни и месяца, ко мне словно рикошетом вернулась необходимость сделать свертку своими руками, причем, уже двумерную!
Эх, некоторые задачи имеют тенденцию возвращаться…
Двумерная свертка — это очень интересная, и как ни странно, довольно часто используемая операция, и практически каждый из нас использовал ее хотя бы однажды, когда работал с фотографиями или же пытался сделать какой-нибудь интересный эффект на произвольном изображении.
Но, что же это такое, свертка?
Если не вдаваться в математику, то все получается довольно просто, особенно, если вспомнить статью про медианный фильтр, так как свертка двумерного массива и по подходу и даже слегка по духу близка к медианному фильтру (а уж сколько общих элементов кода).
Представьте себе, что изображение (исходная картинка) — это некоторая таблица, в ячейки которой вписаны значения цвета, представленного некоторой структурой данных. По этой таблице, движется прямоугольная рамка (или окно, терминология та же самая, что и для медианного фильтра, с оговорками, конечно) нечетной длины и нечетной ширины.
Каждая ячейка рамки, условно говоря, имеет свою «стоимость», которая выражена некоторым числом, а кроме этого, внутри окна есть центральный элемент, который будет накладываться на каждый элемент прямоугольной таблицы изображения.
Дело в том, что наша рамка или окно плавно движется по изображению, каждый раз сдвигаясь по центральному элементу на один шаг и проходя «слева-направо, сверху-вниз» (честно говоря, мне трудно описать направление прохода, но надеюсь, вы меня поймете). Но рамка не просто движется, а меняет каждое значение прямоугольной матрицы изображения по довольно простому закону: каждый элемент прямоугольной таблицы окна, накрытый окном, умножается на соответствующую «стоимость», взятую из нашей рамки, после чего все значения суммируются и значением того элемента изображения, на котором находиться центральный элемент окна, становиться полученный результат такого «оконного суммирования».
Такого рода «скользящее суммирование» производиться до тех пор, пока не будет пройдено все изображение.
На словах, это очень сложно передать, и кажется, математика, в этом случае, гораздо проще повседневного языка, но, программный код лучше понимается (во всяком случае, для меня) по сравнению с операциями математического анализа:
auto convolution(SuperImage source, Filter filter)
{
int imageWidth = source.width;
int imageHeight = source.height;
int filterWidth = filter.getWidth;
int filterHeight = filter.getHeight;
auto convolutionResult = image(imageWidth, imageHeight);
for (int i = 0; i < imageWidth; i++)
{
for (int j = 0; j < imageHeight; j++)
{
float redComponent = 0, greenComponent = 0, blueComponent = 0;
for (int w = 0; w < filterWidth; w++)
{
for (int h = 0; h < filterHeight; h++)
{
auto fX = i + (w - (filterWidth / 2));
auto fY = j + (h - (filterHeight / 2));
if (((fX < 0) || (fX >= imageWidth) || (fY < 0) || (fY >= imageHeight)))
{
// do nothing
}
else
{
Color4f currentPixel = source[fX, fY];
float filterValue = filter[w, h];
redComponent += currentPixel.r * filterValue;
greenComponent += currentPixel.g * filterValue;
blueComponent += currentPixel.b * filterValue;
}
}
}
convolutionResult[i, j] = Color4f(redComponent, greenComponent, blueComponent);
}
}
return convolutionResult;
}
Тут все происходит именно так, как я описал: в роли прямоугольной матрицы изображения выступает абстрактный супертип SuperImage из уже известной нам библиотеки работы с изображениями, а вот в роли окна выступает что-то новое и подозрительное — некий класс Filter, непонятно откуда взятый.
Класс Filter отсутствует как в стандартной комплектации Phobos, так и в dlib, так как он был специально придуман мной для легкого и безболезненного создания собственных обработчиков изображения: ведь в самом деле, свертка — это и есть процедура, с помощью которой реализуются линейные фильтры с конечной импульсной характеристикой (КИХ-фильтры)!
Класс Filter представляет собой абстрактный класс — класс, экземпляр которого создать нельзя, но главное, что может он предоставить — это достаточно высокий уровень абстракции (для представления любого вида линейного КИХ-фильтра), а также наименьший общий знаменатель между различными существующими типами линейных фильтров, работающих внутри сверточной операции.
При этом сам класс выглядит примерно так:
abstract class Filter
{
protected
{
int width, height;
float[][] kernel;
float divisor = 0.0f;
float offset = 0.0f;
}
final pure int getWidth() const @property
{
return width;
}
final pure int getHeight() const @property
{
return height;
}
final pure float opIndex(int i, int j) const @property
{
return offset + divisor * kernel[i][j];
}
}
Идея класса проста: нам нужен некоторый ряд методов, которые универсальны для всех типов фильтров (не забываем про то, что это Filter является абстрактным), а также некоторый набор методов, которые будут легко переопределяемы и которые сыграют роль параметров фильтра.
В роли непереопределяемых универсалий методы getWidth, getHeight, opIndex, которые, в соответствии с принципами инкапсуляции, получают значения приватных членов класса: длину окна, ширину окна и индекс соответственно. Кроме того, в интересах сохранения структурной целостности любым производным от Filter классом, целый набор членов-данных класса мы объявляем защищенными, что предполагает возможность установки этих параметров внутри наследников Filter. Защищенными параметрами, в данном случае, служат следующие параметры окна: длина и ширина окна, «ядро свертки» (т.е. набор «стоимостей» окна или иными словами, набор коэффициентов, показывающих силу с какой влияет окружение на центральный пиксель), делитель и смещение (специально подобранные величины, служащие для того, чтобы выходное значение операции свертки входило в допустимый диапазон для типа данных, представляющего цвет пикселей).
В принципе, проект уже компилируется или собирается с помощью dub, но для испытаний не хватает хотя бы одного примера рабочего фильтра, а еще остается вопрос как (исходя из уже созданных нами функции и класса) сделать фильтр и где взять его параметры (ядро, делитель и смещение).
Строго говоря, параметры большинства фильтров уже известны (лишь иногда появляются новые) и описаны в статьях по цифровой обработке изображений или же в престижных математических журналах, и в принципе, являются общедоступными (если, конечно, знать, что искать и где), что нереально упрощает задачу: не нужно долго думать и выводить коэффициенты окна вручную.
Определим, к примеру, свой фильтр, который выделит ближайшие пиксели и поставит их примерно на один уровень яркости с центральным. Для этого, необходимо просто произвести наследование от абстрактном класса Filter и определить конструктор производного класса, задав внутри него значения для описанных выше параметров:
class Area4 : Filter
{
this()
{
width = 3;
height = 3;
divisor = 0.1f;
offset = 0.0f;
kernel = [
[ 0, 1, 0 ],
[ 1, 1, 1 ],
[ 0, 1, 0 ],
];
}
}
Написать свой фильтр для изображений, оказывается не так уж и муторно: достаточно реализовать свертку последовательностей и найти матрицу нужного эффекта. К слову, об эффекте, созданный нами фильтр сделает изображение более четким, но яркость может потерять пару полутонов — вот посмотрите на стандартное изображение, обработанное полученным фильтром Area4 с помощью вот такого кода:
import dlib.image;
import convolution;
import transformation;
void main()
{
auto standartImage = load(`Lenna.png`);
standartImage
.convolution(new Area4)
.savePNG("Lenna_FIR_test.png");
}
Файлы convolution.d и transformation.d содержат, соответственно, реализации свертки (конволюции) и фильтра Area4.
Изображение после воздействия сверточной матрицы:
В общем, на этом на тема свертки еще не окончена и скоро мы покажем еще пару интересных эффектов, основанных на свертке, но это уже будут совсем другие статьи…