943 читателя, 23 поста
Администрация
Модераторы
Пишем полезные и не очень алгоритмы, а так же изучаем уже существующие.
Фильтрация изображений методом свертки
Автором данного топика является хабраюзер Popik , который сам не может запостить этот топик в силу астральных причин.
Вероятно, большинство хабросообщества не понаслышке знает о фильтрах обработки изображений, таких как размытие, повышение резкости, нахождение краев, тиснение и прочие. Некоторые работали с ними более тесно, некоторые использовали их как данность. Однако все ли знают, как именно происходит фильтрация изображения, и что общего между перечисленными фильтрами? В данном топике я постараюсь в общем виде описать алгоритм, по которому это все выполняется, а так же приведу его реализацию.
Итак, фильтры, которые были перечислены, а так же множество других основаны на свертке. Что же такое свертка? Свертка (англ. convolution) — это операция, показывающая «схожесть» одной функции с отражённой и сдвинутой копией другой. Понятие свёртки обобщается для функций, определённых на группах, а также мер. Несколько сложноватое определение, не так ли? Те, кому интересна математическая теоретическая часть, могут заглянуть по ссылке на Википедию, и, возможно, почерпнуть для себя что нибудь полезное.
Я же постараюсь дать свое определение-объяснение свертки «на пальцах» только для случая обработки изображений, которое может быть, не настолько умное и точное как в научной литературе, но как мне кажется, позволяющее понять суть данного процесса.
Итак, свертка – это операция вычисления нового значения выбранного пикселя, учитывающая значения окружающих его пикселей. Для вычисления значения используется матрица, называемая ядром свертки. Обычно ядро свертки является квадратной матрицей n*n, где n — нечетное, однако ничто не мешает сделать матрицу прямоугольной. Во время вычисления нового значения выбранного пикселя ядро свертки как бы «прикладывается» своим центром (именно тут важна нечетность размера матрицы) к данному пикселю. Окружающие пиксели так же накрываются ядром. Далее высчитывается сумма, где слагаемыми являются произведения значений пикселей на значения ячейки ядра, накрывшей данный пиксель. Сумма делится на сумму всех элементов ядра свертки. Полученное значение как раз и является новым значением выбранного пикселя. Если применить свертку к каждому пикселю изображения, то в результате получится некий эффект, зависящий от выбранного ядра свертки.
На этом мы закончим с теорией, и перейдем к примерам и реализации данного алгоритма. Мозг еще жив? :)
Приведу лишь главную часть кода на C#, полный исходный код свертки и небольшую программку для наглядного тестирования можно будет скачать по ссылке в конце статьи. Оговорюсь заранее, что код не писался как нечто очень оптимальное, и поле для оптимизаций еще есть. Например повысить скорость можно использованием предвычисленных значений пикселей, но не в этом суть.
Скачать программу пример
Вот и все. Надеюсь что данный материал был полезен и преподнес вам что-то новое. Если данная тема вас заинтересовала, то могу написать еще про базовые методы формирования ядер свертки, а так же про оптимизации данного алгоритма. Спасибо за внимание!
Введение.
Вероятно, большинство хабросообщества не понаслышке знает о фильтрах обработки изображений, таких как размытие, повышение резкости, нахождение краев, тиснение и прочие. Некоторые работали с ними более тесно, некоторые использовали их как данность. Однако все ли знают, как именно происходит фильтрация изображения, и что общего между перечисленными фильтрами? В данном топике я постараюсь в общем виде описать алгоритм, по которому это все выполняется, а так же приведу его реализацию.Немного теории.
Итак, фильтры, которые были перечислены, а так же множество других основаны на свертке. Что же такое свертка? Свертка (англ. convolution) — это операция, показывающая «схожесть» одной функции с отражённой и сдвинутой копией другой. Понятие свёртки обобщается для функций, определённых на группах, а также мер. Несколько сложноватое определение, не так ли? Те, кому интересна математическая теоретическая часть, могут заглянуть по ссылке на Википедию, и, возможно, почерпнуть для себя что нибудь полезное.
Я же постараюсь дать свое определение-объяснение свертки «на пальцах» только для случая обработки изображений, которое может быть, не настолько умное и точное как в научной литературе, но как мне кажется, позволяющее понять суть данного процесса.
Итак, свертка – это операция вычисления нового значения выбранного пикселя, учитывающая значения окружающих его пикселей. Для вычисления значения используется матрица, называемая ядром свертки. Обычно ядро свертки является квадратной матрицей n*n, где n — нечетное, однако ничто не мешает сделать матрицу прямоугольной. Во время вычисления нового значения выбранного пикселя ядро свертки как бы «прикладывается» своим центром (именно тут важна нечетность размера матрицы) к данному пикселю. Окружающие пиксели так же накрываются ядром. Далее высчитывается сумма, где слагаемыми являются произведения значений пикселей на значения ячейки ядра, накрывшей данный пиксель. Сумма делится на сумму всех элементов ядра свертки. Полученное значение как раз и является новым значением выбранного пикселя. Если применить свертку к каждому пикселю изображения, то в результате получится некий эффект, зависящий от выбранного ядра свертки.
На этом мы закончим с теорией, и перейдем к примерам и реализации данного алгоритма. Мозг еще жив? :)
Несколько примеров.
Реализация алгоритма.
Приведу лишь главную часть кода на C#, полный исходный код свертки и небольшую программку для наглядного тестирования можно будет скачать по ссылке в конце статьи. Оговорюсь заранее, что код не писался как нечто очень оптимальное, и поле для оптимизаций еще есть. Например повысить скорость можно использованием предвычисленных значений пикселей, но не в этом суть.
public static class Convolution
{
public static Bitmap Apply(Bitmap input, double[,] kernel)
{
//Получаем байты изображения
byte[] inputBytes = BitmapBytes.GetBytes(input);
byte[] outputBytes = new byte[inputBytes.Length];
int width = input.Width;
int height = input.Height;
int kernelWidth = kernel.GetLength(0);
int kernelHeight = kernel.GetLength(1);
//Производим вычисления
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
double rSum = 0, gSum = 0, bSum = 0, kSum = 0;
for (int i = 0; i < kernelWidth; i++)
{
for (int j = 0; j < kernelHeight; j++)
{
int pixelPosX = x + (i - (kernelWidth / 2));
int pixelPosY = y + (j - (kernelHeight / 2));
if ((pixelPosX < 0) ||
(pixelPosX >= width) ||
(pixelPosY < 0) ||
(pixelPosY >= height)) continue;
byte r = inputBytes[3 * (width * pixelPosY + pixelPosX) + 0];
byte g = inputBytes[3 * (width * pixelPosY + pixelPosX) + 1];
byte b = inputBytes[3 * (width * pixelPosY + pixelPosX) + 2];
double kernelVal = kernel[i, j];
rSum += r * kernelVal;
gSum += g * kernelVal;
bSum += b * kernelVal;
kSum += kernelVal;
}
}
if (kSum <= 0) kSum = 1;
//Контролируем переполнения переменных
rSum /= kSum;
if (rSum < 0) rSum = 0;
if (rSum > 255) rSum = 255;
gSum /= kSum;
if (gSum < 0) gSum = 0;
if (gSum > 255) gSum = 255;
bSum /= kSum;
if (bSum < 0) bSum = 0;
if (bSum > 255) bSum = 255;
//Записываем значения в результирующее изображение
outputBytes[3 * (width * y + x) + 0] = (byte)rSum;
outputBytes[3 * (width * y + x) + 1] = (byte)gSum;
outputBytes[3 * (width * y + x) + 2] = (byte)bSum;
}
}
//Возвращаем отфильтрованное изображение
return BitmapBytes.GetBitmap(outputBytes, width, height);
}
}
* This source code was highlighted with Source Code Highlighter.Скачать программу пример
Вот и все. Надеюсь что данный материал был полезен и преподнес вам что-то новое. Если данная тема вас заинтересовала, то могу написать еще про базовые методы формирования ядер свертки, а так же про оптимизации данного алгоритма. Спасибо за внимание!
комментарии (62)
И как-то вы с оригинальным определением завернули сложно. Применительно к обработке изображений это определение заставляет мозг сделать лоботомию изнутри, особенно сейчас, после работы :) Хорошо, что расшифровали потом :)
java.sun.com/javase/6/docs/api/java/awt/image/ConvolveOp.html
habrahabr.ru/blogs/algorithm/62738/#comment_1736334
Посоветовать ресурс, где есть все и сразу, не смогу, так как сам искал и не нашел.
Если постараться ответить кратко, то понять, почему ядро работает именно так, можно прочитав алгоритм и посмотрев на матрицу ядра. Например Box Blur — это вычисление среднего арифметического цветов пикселей, окружающих данный пиксель (берем их все с коэффициентом 1). Gaussian blur — среднее арифметическое с коэффициентами, поэтому размытие получается более мягким.
Нахождение краев и повышение резкости — по сути дифференцирование.
Хотя конечно вот так быстро и на пальцах не все объяснишь, да и нет смысла. Постараюсь в ближайшее время написать более подробно отдельный топик про это.
Спасибо :)
Все ядра получены чисто из эвристических соображений. И если понять как работает алгоритм «применения ядра свертки», то становится понятно почему само ядро имеет такой вид. Для простоты можно рассмотреть черно-белое изображение где каждый пиксель имеет один параметр — яркость(от 0 до 255). Взяв, например, черный квадрат на белом фоне, можно применить к нему ядро выделения вертикальных границ(как в топике). Тогда понятно, что белый фон(яркость 255) это ядро перекрасит в черный(яркость станет 0), потому что 1*255+1*255+1*255+0*255+0*255+0*255 -1*255 -1*255 -1*255 = 0. Тоже самое будет и с черным фоном -останется яркость 0. А вот на границе черного и белого(вертикальные стороны) будет 1*255+1*255+1*255+0*255+0*255+0*255 -1*0 -1*0 -1*0= 255 * 3 =253 (mod 256) то есть примерно белый. Что и требовалось. :)
При этом высокие частоты соответствуют границам объектов, а низкие частоты — фону и плавным переходам.
Сглаживание — это фильтр, который убирает высокие частоты из изображения. Выделение границ — это фильтр, который убирает низкие частоты из изображения. Повышение резкости — это фильтр, который усиливает высокие частоты, а низкие частоты оставляет без изменений.
в исходнике есть, в описании — нет. У многих по описанию и примерам возникнут вопросы о делении на 0…
У меня грядет защита диплома по facial recognition & identification в сентябре
– полосова фільтрація;– режекторна фільтрація) реализовано на SciLab(типа Matlab). Кому интересно могу навоять статью.
Гонсалес Р., Вудс Р. Цифровая обработка изображений
sakri.net/technology/flash/flex/convolution_filter/ConvolutionFilterExplorer.html
не подавай плохой пример, а то ж на копипастят…
А то что я не использовал предвычисленные таблицы — это умышленно, иначе алгоритм стал бы нечитаем для непосвященных.
что сложного в том чтобы понять такую вещь как
a = 3 * (width * y + x);
и последующее использование
>это умышленно, иначе алгоритм стал бы нечитаем для непосвященных
приводишь довод достойный первоклассника.
чем раньше начнут оптимизировать, тем чаше в работе на подсознании будет оптимизация… иначе будет получатся медленный какат коего сейчас наплодили дохрена, ибо зачем мучится оптимизировать, интел же новый процессор скоро выпустит стопяцот гигагерц…
если приводишь алгоритм, сделай его хорошо, потому что многие просто скопируют без оптимизации!
ЗЫ. и в шарпе надо это делать в unsafe. (:
А реализация/оптимизация алгоритма — это уже отдельная статья.
По-моему должно быть очевидно, что реализация алгоритма в лоб (как в данном примере) далеко не самая эффективная.
если реализация отдельная статья, зачем код?
> что реализация алгоритма в лоб (как в данном примере) далеко не самая эффективная
зачем нужна неэффективная реализация алгоритма?! (в стопяцотпервый раз — на плодят же дофига, не обязательно этот, но наплодят)
Кто просто копипастит, тот и будет пкопипастить! Он не будет вникать в оптимизацию, поэтому оно того не стоит. А чтобы объяснить само действие алгоритма самое то!
А вот те, кому правда интересно, те алгоритм поймут и уже перепишут как им надо! Так что не в пирожках мясо!
>стоит. А чтобы объяснить само действие алгоритма самое то!
дык и будут в том то и дело, не лучше ли чтоб копипастили что то хорошее?!
> Так что не в пирожках мясо!
а жаль, щас бы пирожок… (:
Копипастить будут максимум школьники-студенты для курсовых — пусть делают это наздоровье, оценку им поставят, т.к. специалистами они видимо стать при этом не хотят.
FFT — естественно быстрое преобразование фурье
1. Что делать на границе? Первый же пиксель (0, 0) и я в ступоре. Оказалось что пиксели изображения недостающие надо пропускать (это еще очевидно), но неочевидным оказалось то, что сумму сетки тоже надо брать только ту, что на пиксели наложена (тоесть не учитывать некоторое на границе как и в случае с изображением).
2. Деление на ноль (а как по коду оказалось — если меньше нуля то тоже надо единицу ставить)
if (kSum <= 0) kSum = 1;
А в целом — спасибо огромное, куча позитива и все такое). Вот, собственно, программка: dpaste.com/hold/59566/ (привентил прогресс-бар на всякий случай, брать его здесь code.google.com/p/python-progressbar/)
Насчет граничных случаев в большинстве описаний алгоритма ничего не сказано. Каждый реализует это так, как считает нужным. В инете находил достаточно много решений, таких как «заворачивание» изображений (если координата пикселя отрицательная, то берется пиксель с другого края картинки), игнорирование несуществующих пикселей с делением на полную сумму ядра и прочие методы. Однако приведенный мной метод показался мне наиболее логичным и дающим самый приличный результат на краях.
Насчет деления на ноль ситуация такая же. Я посчитал что в случае отрицательной или нулевой суммы делить на 1 — самое безобидное.
if ((pixelPosX < 0) || (pixelPosX >= width) || (pixelPosY < 0) || (pixelPosY >= height)) continue;
У меня была только методичка и желание заработать :)