Введение
Медианный фильтр — один из видов цифровых фильтров, широко используемый в цифровой обработке сигналов и изображений для
уменьшения уровня шума.
Реализуется с помощью окна, состоящего из нечётного количества отсчётов. Значения отсчётов внутри окна сортируются по порядку; и
среднее значение, то есть значение находящееся в середине упорядоченного списка, принимается выходным значением. На следующем шаге окно
передвигается на один отсчёт вперёд и вычисления повторяются. Крайние значения массива мыслим продублированными столько раз, чтобы можно
было применить окно к первому и к последнему значению.
Медианная фильтрация — обычная процедура обработки изображений. Она особенно часто используется для уменьшения шума в
изображении.
Постановка задачи
Дана матрица NxN. Необходимо реализовать параллельный алгоритм медианной фильтрации этой матрицы.
Метод решения
(Примечание: для простоты был реализован фильтр 3x3)
Последовательный алгоритм:
Фильтрация проводится построчно – для первого элемента строки заполняется массив окрестности (с учетом того, что искусственно
добавляются три значения-соседи слева), этот массив сортируется быстрой сортировкой, затем среднее значение записывается в выходную
матрицу. Для каждого следующего элемента строки массив окрестности не заполняется заново – в него лишь добавляются новые три элемента,
замещая старые три. Для того, чтобы это было возможно сделать за один проход (по массиву окрестности и новым трем элементам) введен
специальный массив с «количеством жизней» элемента. Жизней может быть 1, 2 и 3. Добавляемые 3 элемента предварительно сортируются и
добавление производится слиянием: во время него элементы с 1й жизнью затираются, элементы, имевшие 2 и 3 жизни получают 1 и 2
соответственно, а добавляемые элементы становятся обладателями 3х жизней. Средний элемент записывается в выходной массив. Обработка
последнего элемента производится повторением итерации предпоследнего шага. На практике данный метод по сравнению с полной выборкой
окрестности и ее сортировкой показывает превосходство по скорости в 3 раза.
Параллельный алгоритм:
(Примечание: размерность матрицы была ограничена значениями кратными двойке)
Т.к. в данной задаче наблюдается независимость по данным, параллелизм производится на основе деления матрицы на части (по
несколько строк, а именно N/p, где p –количество процессов). Если учесть что в персональных компьютерах обычно 1, 2, 4 или 8 ядер у
процессора, то деление будет производиться без остатка. После деления матрицы на части по высоте – они обрабатываются последовательным
алгоритмом, но необходимо учесть, то при этом невозможно обработать граничные строки (за исключением первой и последней в матрице) –
после завершения параллельных вычислений, части собираются обратно в одну матрицу, а оставшиеся строки необходимо отфильтровать
отдельно.
Анализ эффективности
Время фильтрации 1го элемента строки:
(2*9+9*ln(9)*2+1)*t , где t - время выполнения одной операции.
- (2*9 операций – заполнение массива окрестности и соответствующего массива «жизней»
- 9*ln(9)*2 – быстрая сортировка массивов
- 1 – выборка и присваивание медианы выходному элементу
Фильтрация последующих элементов строки:
(9+3+18+1)*t
- 9+3 – проход по массиву окрестности с добавлением новых элементов и удалением старых
- 18 – копирование массива окрестности и массива «жизней» из вспомогательных массивов
- 1 – выборка и присваивание медианы выходному элементу
Итого на требующееся на фильтрацию строки время:
((2*9+9*ln(9)*2)+1+(N-1)*(9+3+18+1))*t ≈(21N+37)*t
Время на фильтрацию всей матрицы:
Tp = (α+ω/β*N^2/p)+(21N+37)*t*(N/p+2*(p-1))
- α – латентность
- β - пропускная способность среды передачи
- ω - размер элемента матрицы
- 2*(p-1) – количество строк, оставшихся неотфильтрованными при делении матрицы на части)
T1 = (21N+37)*t*N
Тогда:
Ускорение: Sp = (T1 )/(Tp ) = ((21N+37)*t*N)/((21N+37)*t*(N/p+2*(p-1) )+α+ω/β*N^2/p) = βp/
(β+ω/21) ,при N→∞
Эффективность: Ep = (Sp )/p = β/(β+ω/21) ,при N→∞
Демонстрация
|
Ширина матрицы
|
Время выполнения (сек)
|
|
1
|
2
|
4
|
8
|
|
Tт
|
Tп
|
Tт
|
Tп
|
Tт
|
Tп
|
Tт
|
Tп
|
|
512
|
0.027134
|
0.032746
|
0.013678
|
0.021245
|
0.0071519
|
0.017787
|
0.004184
|
0.016893
|
|
1024
|
0.108349
|
0.132294
|
0.054436
|
0.073122
|
0.027772
|
0.047679
|
0.0150759
|
0.058709
|
|
2048
|
0.433023
|
0.528755
|
0.216984
|
0.300326
|
0.109574
|
0.217646
|
0.0571389
|
0.212924
|
|
4096
|
1.731348
|
2.104721
|
0.866569
|
1.414157
|
0.435423
|
1.063785
|
0.222386
|
1.063785
|
|
8192
|
6.923902
|
8.393932
|
3.463692
|
8.237934
|
1.736097
|
8.139418
|
0.877371
|
8.139418
|
Сравнение теоретических оценок ускорения с практическими:
|
Ширина матрицы
|
2
|
4
|
8
|
|
Sт
|
Sп
|
Sт
|
Sп
|
Sт
|
Sп
|
|
512
|
1.977266
|
1.541351
|
3.794181
|
1.841007
|
6.485653
|
1.938436
|
|
1024
|
1.990388
|
1.809223
|
3.901360
|
2.774681
|
7.187350
|
2.9253385
|
|
2048
|
1.995641
|
1.760603
|
3.951864
|
2.429427
|
7.578548
|
2.483304
|
|
4096
|
1.997933
|
1.488322
|
3.976242
|
1.978521
|
7.785321
|
2.299073
|
|
8192
|
1.998995
|
1.018936
|
3.988201
|
1.031269
|
7.891650
|
1.026975
|
Характеристики машины:
Intеl Core i7 920 @ 2.80GHz 2.00ГБ ОЗУ
латентность: a = 0,00005 cек
пропускная способность: b = 25,6 ГБ/с
время выполнения стандартной операции: t = 0,000000004912 сек
размер элемента набора : w = 4
Об авторах
Работу выполнили студенты группы 8411: Муравьев Владимир и Соловьев Павел
