Вопрос по c++ – Быстрый Медианный Фильтр в С ++

6

Кто-нибудь знает алгоритм быстрого медианного фильтра для 16-битных (беззнаковых коротких) массивов в c ++?

http://nomis80.org/ctmf.html

Это выглядит довольно многообещающе, но работает только с байтовыми массивами. Кто-нибудь знает, как изменить его для работы с шортами или альтернативный алгоритм?

Вы пробовали std :: nth_element? Это O (n) по сравнению с O (n log n) для быстрой сортировки. smocking
Если вы не хотите выполнять медианную фильтрацию, то есть то, что вы делаете, например, при обработке изображений, где вы находите одну медиану для каждого пикселя, но просто хотите найти одну медиану, комментарий @ smocking уместен. HelloGoodbye
Вы не хотите модифицировать этот алгоритм, чтобы он работал коротко, поскольку время работы на пиксель пропорционально 2 ^ n, где n - количество битов в используемом типе данных. 256 для 8-битных массивов уже достаточно болезненны, вы не хотите переходить к 65536 для 16-битных массивов. Смотрите мой ответ для более быстрого алгоритма, даже если он равен O (log r) на пиксель, а не O (1). HelloGoodbye

Ваш Ответ

5   ответов
0

где W - ширина фильтра, а N - количество выборок.

http://www.cas.cn/ky/kyjz/201305/W020130504687068232825.pdf

1

который выполняется в O (logr) время на пиксель, гдеr является радиусом фильтра и работает для любого типа данных (будь то 8-битные целые или двойные числа):

Быстрая медиана и двусторонняя фильтрация

0

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

Я разместил здесь некоторый эталонный код:1D скользящая медианная фильтрация в C ++

Он основан на шаблонах, поэтому он должен работать с большинством типов данных POD.

По моим результатамstd::nth_element имеет низкую производительность для движущейся медианы, поскольку он должен каждый раз сортировать окно значений.

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

Remove oldest value out of the pool (calls std::lower_bound) Insert new value into pool (calls std::lower_bound) Store new value in history buffer

Медиана теперь является средним значением в пуле.

Я надеюсь, что кто-то найдет это интересным и внесет свои идеи!

4

описанная в статье, основана на создании гистограммы с 256 бинами для 8-битного пиксельного канала. Преобразование в 16 бит на канал потребовало бы гистограммы с 65536 бинами, и гистограмма необходима для каждого столбца изображения. Повышение требований к памяти на 256 делает этот алгоритм менее эффективным в целом, но все еще, вероятно, выполнимым с сегодняшним оборудованием.

Использование предлагаемой оптимизации разбиения гистограммы на грубые и точные участки должно еще больше сократить время выполнения до 16x.

Я думаю, что для небольших значений радиуса вы обнаружите, что традиционные методы медианной фильтрации будут более эффективными.

3

Вот (PDF) - это что-то для C, это документ с заголовком «Быстрый поиск по медиане: реализация ANSI C». Автор утверждает, что это O (log (n)), он также предоставляет некоторый код, может быть, он вам поможет. Это не лучше, чем предложенный вами код, но, возможно, стоит посмотреть.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededextremely slowError: User Rate Limit Exceeded

Похожие вопросы