Реализация алгоритма медианной фильтрации 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), как выходящий за пределы. Такие столбцы не прибавляются и не вычитаются. Счётчики отрицательными не должны быть.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 6. Питон реализация энилоджиковской модели, картинка про Центральную часть будущей модели anaschu 26.06.2026 Етить. ИИ мне на основе моего старого файла R создал вот эту вот хмерь на пайтоне. Это уже новая модель, модель сукцессии грибной. потоки фосфора, азота. Углерода. 5 видов организмов. Я даже. . .	Как замкнутый ядерный цикл решит проблему недостатки фосфора? Био миграция фосфора со дна океана anaschu 26.06.2026 Биологический лифт: Концепция подъема фосфора со дна океана с помощью ЗЯТЦ Предлагаю на обсуждение альтернативу тяжелому промышленному бурению океанического дна. Вместо сложной инженерии мы можем. . .	сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .	сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .
сукцессия 3 anaschu 25.06.2026 Примерный план работ по модели	сукцессия 2 anaschu 25.06.2026 параметризировочная калибровочная таблица будущей модели	Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал (мат мет мод 29) anaschu 23.06.2026 Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал Материалы для обсуждения с МГСУ · 2026 Рисунки внутри приложенного ворд файла. Что за. . .	28. Конкретное развертывание плана номер 1 из поста номер 27 anaschu 22.06.2026 Можно ли из модели получить конкретные строительные требования? Честно — напрямую из текущей модели такие ответы не получить. Но цепочка логики есть, и она не такая длинная. Где разрыв . . .

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

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

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