Реализация алгоритма размытия

[Dimonte]

Здравствуйте. Написал тут класс для простенького размытия точечных изображений (только градации серого). Алгоритм простой - берутся значения соседних точек по углам с весом 1/16 каждое, берутся значения точек по сторонам с весом 1/8 каждое, и значение самой точки с весом 1/4. Для повышения скорости расчеты значений сделал по возможности битовым сдвигом, но возникла проблема. Накапливается ошибка вычислений, в результате, уже на 10и проходах заметно заметное затемнение рисунка, а на 15и реализация уже откровенно проваливается. Сделал еще две реализации, одна несколько "честнее" обсчитывает точки и в основном цикле захватывает еще и крайние точки изображения (первая реализации обсчитывает их и угловые точки изображения отдельно). Другая работает практически как первая, но расчет значения через битовый сдвиг применяет не на каждое значение точек, а на блоки значений угловых и соседних точек. Результаты работы алгоритмов показаны на рисунках ниже.

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

10 проходов:


15 проходов:


При этом 10 проходов занимают на моем компьютере время (исходное изображение - 100х100 пикселей):
"честный" алгоритм - 223мс
битовый сдвиг каждого значения - 147мс
битовый сдвиг блоков - 165мс

Исходники приложены.

Для достижения сильного размытия больших изображений понадобится заметно больше проходов. Имеет смысл работать с какой-то из данных реализаций? Если да, то как можно поправить накапливающуюся ошибку (честное округление достаточно сильно бьет по скорости)? Или лучше отказаться от алгоритма вовсе и перейти к Гауссовому размытию, например?

[ramshteks]

а можно узнать каким боком тут ас3,0?

[etc]

Совершенно неоптимизированный код. Чем вам не угодил обычный BlurFilter?

[wvxvw]

А какая конечная цель? И почему обычный BlurFilter не подошел?
Время какое-то безумное... т.е. даже самый "быстрый" метод - это очень медленно по сравнению с родным фильтром. Ну, не знаю, из того, что может пригодиться... если использовался метод getPixel, то можно попробовать пойти в сторону getPixels и работать с массивом байтов (не уверен, но возможно все-тки будет пошустрее)

ой, пост выше не видел =)

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

for(var i:int = 0; i < bitmap.width; i++){
var somevar = bitmap.height + i;
}

var i:int;
var l:int = bitmap.width;
var h:int = bitmap.height;
for(i = 0; i < l; i++){
h + i;
}

[Dimonte]

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

Если использовать ByteArray, то, боюсь, операции выборки рабочих пикселей будут съедать весь возможный прирост скорости

Множественные вызовы методов - очень глупая ошибка, действительно. Убрал их, теперь для 10и проходов время:
1 - 172
2 - 137
3 - 158

Где я еще глупо наошибался? )

[wvxvw]

>> Если использовать ByteArray, то, боюсь, операции выборки рабочих пикселей будут съедать весь возможный прирост скорости.

Чет мне сомнительно...

фильтрами особо не увлекался, но из последнего, что делал - загрузчик + конвертор BMP формата. Тесты делались на картинках 720х480, загрузить, отрендерить и выслать 200 картинок занимало чуть больше 2 минут. т.е. 69120000 х 2 пикселей за 120000 мс (около 580мс на картинку включая пересылку в один конец в локальной файловой системе) т.е. примерно 1К пикселей в мс.

Прекалькуляция, где только возможно...
Вот это забить в константу, ну или по крайней мере, локальную переменную:

Math.pow((radius*2+1), 2);

т.е. посчитать 1 раз и больше не трогать

Умножение на два, деление на два с целыми числами быстрее будет работать, если использовать битовые операции, не существенно, но все же:
т.е. х * 2 == х << 1

var operatingBitmapData:BitmapData = new BitmapData(bitmapData.width, bitmapData.height);
operatingBitmapData = bitmapData.clone();

->

var operatingBitmapData:BitmapData = bitmapData.clone();

Мелочь, но все же

убрать все объявления переменных из тела цикла, если значение переменной не меняется, или возможен только ограниченый набор значений - вынести их в константы.

public static function boxBlur(bitmapData:BitmapData, radius:int = 1):BitmapData
		{
			....
			for (var i:int = 0; i < bitmapData.width; i++)
			{
				for (var f:int = 0; f < bitmapData.height; f++)
				{
					....
					var weightDivider:int = Math.pow((radius*2+1), 2);
					for (var g:int = 0; g < (radius*2+1); g++)
....

private static const weightDividerPow = 9;
private static const weightDivider = 3;
public static function boxBlur(bitmapData:BitmapData, radius:int = 1):BitmapData
		{
			....
			for (var i:int = 0; i < bitmapData.width; i++)
			{
				for (var f:int = 0; f < bitmapData.height; f++)
				{
					....
					weightDividerPow;
					....
					for (var g:int = 0; g < weightDivider; g++)
....

[etc]

Сообщение от Dimonte

Где я еще глупо наошибался? )

Ну, например, постоянные вычисления величин, типа (i + 1) (хотя это можно было сделать один раз), или (bitmapData.width-2). Про вызов геттеров и методов уже сказали.

[badun]

Сообщение от Dimonte

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

Для большего контроля над параметрами размытия можно использовать ConvolutionFilter с соответствующей матрицей.

[wvxvw]

ЗЫ. да, еще, если в цикле нужно сделать всего пароу итераций, и количество итераций заранее известно - лучше заменить цикл на эти самые несколько операций. Т.е.

for(var i:int=0; i<3; i++){
a=b+i;
}

i=0;
a=b+(++i);
a=b+(++i);
a=b+(++i);

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

[Dimonte]

Сообщение от badun

Для большего контроля над параметрами размытия можно использовать ConvolutionFilter с соответствующей матрицей.

Спасибо, опять я проглядел очевидное решение. )

Сообщение от wvxvw

ЗЫ. да, еще, если в цикле нужно сделать всего пароу итераций, и количество итераций заранее известно - лучше заменить цикл на эти самые несколько операций.

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