Реализация алгоритма медианной фильтрации Huang

@mihafiz97 · Регистрация: 14.12.2022

Студворк — интернет-сервис помощи студентам

Добрый день, помогите с реализацией алгоритма Huang’s O(n) median filtering algorithm.
Псевдокод алгоритма показан на рисунке Screenshot_1.png. Но я не понимаю, что значит операция Remove (предположу, что это значит удалить пиксель), add.
Мои предположения:
Add - добавляем значение пикселя X(i+k,j+r) в гистограмму H
Remove - удаляем значение пикселя X(i+k,j−r−1) из H

У них там написано Initialize kernel histogram H, не понимаю как построить гистограмму H.

полный текст статьи в файле ctmf.pdf. Может кто-нибудь делал такое? Или хотя бы поясните как читать псевдокод на рисунке Screenshot_1.png?

@mihafiz97 · 20.05.2024, 10:32 **[ТС]**

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

Инициализация разве не O(r)?

Вы правы, инициализация гистограммы равна О(r). И когда окно двигается по изображению, то выполняется r операций сложения и r операций вычитания, т.е. скорость тоже O(r). Тогда я не понимаю откуда авторы взяли скорость О(1)? Еще раз приведу скриншот.

@mihafiz97 · 20.05.2024, 10:50 **[ТС]**

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

Какой алгоритм применили для реализации Y = median(H)?

Перебираю значения от 0 до 256 (256 градаций серого), суммирую значения гистограммы до тех пор пока count не станет больше (r**2) / 2, как только выполняется это условие, то порядковый номер i является медианой
def median(H, kernel_size):
count, median = 0, 0
for i in range(0,256):
count += H[i]
if count > ((kernel_size)**2) / 2:
median = i
break
else:
median = i
return median

сейчас попробую на while переделать, может быстрее будет

Добавлено через 14 минут

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

сейчас попробую на while переделать, может быстрее будет

def median(H, kernel_size):
count, i = 0, 0
while count < ((kernel_size**2)) / 2 and i < 256:
count += H[i]
i += 1
return i - 1

Замена цикла for на цикл while ускорения не дало.

@Mikhaylo · 20.05.2024, 12:12

У меня такая мысль... Нужно хранить не просто гистограмму, но и ее count при расчете медианы в median(). Нет необходимости каждый раз подсчитывать count заново, пересчитать надо.

@mihafiz97 · 20.05.2024, 13:47 **[ТС]**

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

У меня такая мысль... Нужно хранить не просто гистограмму, но и ее count при расчете медианы в median(). Нет необходимости каждый раз подсчитывать count заново, пересчитать надо.

Это разве придаст скорость алгоритму О(1), все равно операции сложения и вычитания столбцов дают О(r)

@Mikhaylo · 20.05.2024, 15:43

А мне кажется, что авторов заботила только та часть алгоритма, которая внутри циклов 1...n, 1...m. Инициализация снаружи этих циклов и поэтому не столь сильно влияет на результат. Тело внутреннего цикла имеет сложность О(1).

Не сохраняют ли они в памяти n квадратных гистограмм? Тогда сложность будет, действительно, О(1), но память немного затрачивается.

Добавлено через 47 минут
Не знаю, почему, но они операции Add и Remove заменили на прибавление/вычитание столбцевых гистограмм и считают их О(1).
При этом медиана в среднем вычисляется как (2*r+1)^2/2 операций. Это O(r^2). Это не профанация, они позже эти операции подсчитывают.

Я бы оптимизировал вычисление медианы, запоминая count в median() для последующего пересчета.

Добавлено через 5 минут
Сообразил. Смотрите, r может быть равно 512, 1024, 8192, но сложений и вычитаний при Add/Remove всегда будет 256 для изображения в серых тонах.

@mihafiz97 · 20.05.2024, 16:06 **[ТС]**

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

Сообразил. Смотрите, r может быть равно 512, 1024, 8192, но сложений и вычитаний при Add/Remove всегда будет 256 для изображения в серых тонах.

Можете пояснить ? Я не совсем понял, я беру апертуру kernel_size = 2*r+1, если я беру r=1, то у меня на итерацию по столбцам 3 сложения и 3 вычитания, если r=2, то соответственно 5 сложений и 5 вычитаний и чем больше r, тем больше пикселей участвуют в операциях сложения и вычитания, значит и алгоритм медленнее выполняется.

@Mikhaylo · 20.05.2024, 17:48

Не путайте квадрат-апертуру с гистограммой H. Квадрат содержит (2*r+1)^2 чисел, а гистограмма всегда 256 чисел и 256 счетчиков для greyscale-изображения. Add/Remove заменяем на сложение/вычитание гистограмм.

@mihafiz97 · 21.05.2024, 10:10 **[ТС]**

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

Не путайте квадрат-апертуру с гистограммой H. Квадрат содержит (2*r+1)^2 чисел, а гистограмма всегда 256 чисел и 256 счетчиков для greyscale-изображения. Add/Remove заменяем на сложение/вычитание гистограмм.

Вы имеете ввиду вычитание всей гистограммы? Например, я инициализировал H 3x3, затем по псевдокоду я должен H посчитать для первой итерации как H = H + h(2) - h(-1), где h2 - это столбец справа от H, а h(-1) это столбец слева от H

Допустим H = {0:1, 1:3, 3:0, ...., 255:5}
h(2) = {0:2, 1:2, 3:0, ...., 255:1}
h(-1) ={0:5, 1:5, 3:4, ...., 255:6}

Тогда получаем H = {0:-2, 1:0, 3:-4,...,255:0}. У меня выходят отрицательные значения количества пикселей для 0 и 3 чего быть не должно. В моем понимании сложение и вычитание гистограмм это сложение и вычитание значений количества пикселей. Может тут как-то по другому нужно складывать и вычитать?

@Mikhaylo · 21.05.2024, 10:36

Вы должны проигнорировать h(-1), как выходящий за пределы. Такие столбцы не прибавляются и не вычитаются. Счётчики отрицательными не должны быть.

Новые блоги и статьи Все статьи Все блоги /
Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .

@Mikhaylo 821 / 580 / 75 Регистрация: 20.09.2014 Сообщений: 3,827
	20.05.2024, 12:12
	У меня такая мысль... Нужно хранить не просто гистограмму, но и ее count при расчете медианы в median(). Нет необходимости каждый раз подсчитывать count заново, пересчитать надо. 0

@Mikhaylo 821 / 580 / 75 Регистрация: 20.09.2014 Сообщений: 3,827
	20.05.2024, 15:43
	А мне кажется, что авторов заботила только та часть алгоритма, которая внутри циклов 1...n, 1...m. Инициализация снаружи этих циклов и поэтому не столь сильно влияет на результат. Тело внутреннего цикла имеет сложность О(1). Не сохраняют ли они в памяти n квадратных гистограмм? Тогда сложность будет, действительно, О(1), но память немного затрачивается. Добавлено через 47 минут Не знаю, почему, но они операции Add и Remove заменили на прибавление/вычитание столбцевых гистограмм и считают их О(1). При этом медиана в среднем вычисляется как (2r+1)^2/2 операций. Это O(r^2). Это не профанация, они позже эти операции подсчитывают. Я бы оптимизировал вычисление медианы, запоминая count в median() для последующего пересчета. Добавлено через 5 минут* Сообразил. Смотрите, r может быть равно 512, 1024, 8192, но сложений и вычитаний при Add/Remove всегда будет 256 для изображения в серых тонах. 0

@Mikhaylo 821 / 580 / 75 Регистрация: 20.09.2014 Сообщений: 3,827
	20.05.2024, 17:48
	Не путайте квадрат-апертуру с гистограммой H. Квадрат содержит (2*r+1)^2 чисел, а гистограмма всегда 256 чисел и 256 счетчиков для greyscale-изображения. Add/Remove заменяем на сложение/вычитание гистограмм. 0

@Mikhaylo 821 / 580 / 75 Регистрация: 20.09.2014 Сообщений: 3,827
	21.05.2024, 10:36
	Вы должны проигнорировать h(-1), как выходящий за пределы. Такие столбцы не прибавляются и не вычитаются. Счётчики отрицательными не должны быть. 0