Медианная фильтрация одномерных сигналов

Для понимания и успешной реализации медианного фильтра для матрицы предварительно определим медианную фильтрацию в случае одномерного сигнала. При использовании метода применяется окно в несколько отсчетов – группа фиксированной длины элементов текущего массива. Т.е. для каждого элемента медианный фильтр срабатывает следующим образом: берется текущий элемент и некоторое количество элементов справа и слева от него. Затем полученный набор сортируется и из него выбирается средний элемент. Если элемент находится возле края массива и справа либо слева от него элементов может не существовать, то вместо них берётся начальный либо конечный элемент текущего массива. Например, для массива на 5 элементов с окном в 3 отсчета применение медианного фильтра будет выглядеть так (полужирным выделены добавленные справа и слева элементы):

       A = {2, 14, 3, 80, 9}

       b₁ = med(2, 2, 14) = 2

       b₂ = med(2, 14, 3) = med(2, 3, 14) = 3

       b₃ = med(14, 3, 80) = med(3, 14, 80) = 14

       b₄ = med(3, 80, 9) = med(3, 9, 80) = 9

       b₅ = med(80, 9, 9) = med(9, 9, 80) = 9

       B = {2, 3, 14, 9, 9}

Входные данные

Две строки, в первой из которой записано количество входных сигналов N (N≤100). Во второй через пробел – сами входные сигналы (числа, каждое из которых по модулю не превышает 10⁹).

Выходные данные

Тот же самый набор чисел после применения медианного фильтра

Пример

Ввод	Вывод
5 2 14 3 80 9	2 3 14 9 9

Реализация

#include <iostream>

#include <algorithm>

#define WSIZE 3                 // окно размером в 3 отсчета

using namespace std;

int main() {

int n, a[100], i, j, k, b[WSIZE];

cin >> n;

for (i = 0; i < n; i++)     // заполняем исходный массив

   cin >> a[i];

for(i = 0; i < n; i++){     // определяем медианный (средний)

   for(j = 0; j < WSIZE; j++){ // элемент массива отсчётов

       ((k = i + j - WSIZE/2) = min(k, n-1)) = max(k, 0);

       b[j] = a[k];

   }

   sort(b, b + WSIZE);     // упорядочиваем массив отсчетов

   cout << b[WSIZE/2] << ' '; // выбираем средний элемент

}

}

Следует отметить, что такой метод фильтрации не позволяет исправить данные, если искажение произошло на границе массива.

Двумерный случай

Для использования медианной фильтрации применительно к матрице (например, для изображений) существует множество способов. Попробуем описать один из них, максимально приближенный к предыдущему. Также берётся фиксированное окно с отсчетами. Однако теперь это будет не отрезок. Как правило рассматривается окно квадратное или крестообразное.

Попробуем взять квадратное окно. Все элементы, попавшие в такое квадратное окно, запишем в массив, а затем в таком массиве после упорядочения выберем медианный элемент.

Так для окна с шириной 3 отсчета применение медианного фильтра для произвольного элемента матрицы будет выглядеть так:

1 2 1     3 90 3     1 4 4

В окно попадают элементы, которые после сортировки представляют собой набор:

{1, 1, 1, 2, 3, 3, 4, 4, 90}

Средний элемент набора равен 3. Именно на эту величину будет заменено значение 90 после применения фильтра.

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

5 5 4     5 5 4     2 2 1

Реализация

#include <iostream>

#include <algorithm>

#define WSIZE 3

using namespace std;

int main() {

int n, m, a[100][100], b[WSIZE*WSIZE], i, j, k;

cin >> n >> m;

for (i = 0; i < n; i++)

   for (j = 0; j < m; j++)

       cin >> a[i][j];

for(i = 0; i < n; i++){

   for (j = 0; j < m; j++){

       k = 0;

       for(int i1 = i - WSIZE/2; i1 <= i + WSIZE/2; i1++)

           for(int j1 = j - WSIZE/2; j1 <= j + WSIZE/2; j1++){

               int i2, j2;

               (i2 = max(i1, 0)) = min(i1, n-1);

               (j2 = max(j1, 0)) = min(j1, m-1);

               b[k++] = a[i2][j2];

           }

 

       sort(b, b + WSIZE*WSIZE);

       cout << b[WSIZE*WSIZE/2] << ' ';

   }

   cout << endl;

}

}

Многомерные массивы

Работа с многомерными массивами мало чем отличается от работы с матрицами, за исключением количества индексов (размерности массива). Например, при объявлении массива

int a[2][2][2];

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

…

a[0][0][0]

a[0][0][1]

a[0][1][0]

a[0][1][1]

a[1][0][0]

a[1][0][1]

a[1][1][0]

a[1][1][1]

…

байты

По сути, была создана матрица 2×2, элементами которой являются не целые числа, а массивы на 2 целочисленных элемента каждый.

Задача №115.  Minecraft

Вася обожает игру Minecraft. Сцена в этом игровом мире представляет собой параллелепипед, а все объекты – ландшафт и игровые предметы, составляются из кубиков единичного размера (см. рис). Отсутствие объекта в конкретном месте обозначается нулем, а наличие единицей.

Персонаж Васи попадает в фрагмент сцены размерами H×W×L (высота, ширина и длина соответственно). Помогите определить, на какую максимальную и минимальную высоту Вася может взобраться. Имейте ввиду, под землей могут быть пустоты, но ни одна из них не выходит на поверхность.

Рис. 19. Иллюстрация к задаче "Minecraft".

Входные данные

В первой строке 3 натуральных числа H, W, L записанных через пробел. Все числа не превышают 25.

Затем идут H строк – слои начиная от нижнего уровня №1, в каждой из которых записаны W×L натуральных чисел 0 или 1, где 0 обозначает отсутствие кубика, а 1 – его наличие.

Выходные данные

Выведите через пробел 2 числа – максимальную и минимальную высоту, на которую может взобраться Васин персонаж.

Пример

Ввод	Вывод
5 3 3 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0	4 1

Пояснение к примеру

Уровень №1

Уровень №2

Уровень №3

Уровень №4

Уровень №5

Решение

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

#include <iostream>

#define SIZE 25

using namespace std;

int h, w, l, a[SIZE][SIZE][SIZE], i, j, k, mi, ma;

int main(){

cin >> h >> w >> l;

mi = h; ma = 0;

for(i = 0; i<h; i++)      // записываем данные в

     for(j = 0; j<w; j++) // трехмерный массив

           for(k = 0; k < l; k++)

                cin >> a[i][j][k];

for(i = 0; i<w; i++) // рассматриваем все кубики

     for(j = 0; j<l; j++){ // верхнего слоя

           k = h – 1;      // от них спускаемся вниз

           while(k >= 0 && !a[k][i][j]) k--;

           mi = min(mi, k+1);

           ma = max(ma, k+1);

     }

cout << ma << ' ' << mi;

}