Fast 7x7 медианный фильтр 2d C++

Question

Я пытаюсь преобразовать следующий код из MATLAB в C++

function data = process(data) 
    data = medfilt2(data, [7 7], 'symmetric'); 
    mask = fspecial('gaussian', [35 35], 12); 
    data = imfilter(data, mask, 'replicate', 'same'); 
    maximum = max(data(:)); 
    data = 1 ./ (data/maximum); 
    data(data > 10) = 16; 
end 

моя проблема в medfilt2 - который является 2D медианный фильтр, мне нужно, чтобы поддерживать 10 бит на пикселей и больше изображений.

1. Я просмотрел openCV, у него есть средний фильтр 5x5, который поддерживает 16 бит, но 7x7 поддерживает только байты.

http://docs.opencv.org/2.4/modules/imgproc/doc/filtering.html?highlight=medianblur#medianblur

2.I есть также заглянуть в Intel IPP, но я могу видеть только 1D медианный фильтр https://software.intel.com/en-us/node/502283

Есть ли быстрая реализация для 2D-фильтр?
ищет somehthing как этот
http://ndevilla.free.fr/median/median.pdf с использованием параллельного программирования и векторизованного (/ SSE AVX) операций ...
или это
Существует быстрая медиану процедура фильтрации, разработанная TSHuang, она представлены в книге: Двумерная цифровая обработка сигналов II. Трансформации и медианные фильтры. Отредактировано T.S.Huang. Springer-Verlag. 1981.

также здесь есть некоторые примеры кода http://www.sergejusz.com/engineering_tips/median_filter.htm

Update: здесь быстрый алгоритм https://nomis80.org/ctmf.pdf
здесь оптимизированная версия исходного кода http://nomis80.org/ctmf.html

Answer 1

мотивировано тем, что OpenCV не реализует 16-разрядный медианный фильтр для больших размеров ядра (более 5), я попробовал три разных стратегии.

Все они основаны на алгоритме скользящего окна Хуан [2]. То есть, гистограмма обновляется путем удаления и вставки элементов изображения в виде слайдов окна слева направо. Это довольно просто для 8-битного изображения и уже реализовано в OpenCV. Однако большая гистограмма в 65536 бинов делает вычисления немного сложными.

... Алгоритм все еще остается O (log r), но соображения хранения делают его непрактичным для 16-битных изображений и невозможным для изображений с плавающей запятой. [3]

Я использовал стандартную библиотеку C++ , где это применимо, и не реализовал дополнительные стратегии оптимизации Weiss.

1) Наивная реализация сортировки. Я думаю, что это лучшая отправная точка для произвольного типа пикселя (в частности, float).

2) Редкая гистограмма. Мы не хотели бы перешагнуть через 65536 бункеров, чтобы найти медиану каждого пикселя, так как же тогда сохранить редовую гистограмму? Опять же, это подходит для всех типов пикселей, но это не имеет смысла, если все пиксели в окне разные (например, float).

typedef std::map< _Type, int > Map; 
//... 
// inside the sliding window, update the histogram as follows 
for (/* pixels to remove */) 
{ 
    // _Type px 
    Map::iterator it = map.find(px); 
    if (it->second > 1) 
     it->second -= 1; 
    else 
     map.erase(it); 
} 
// ... 
for (/* pixels to add */) 
{ 
    // _Type px 
    Map::iterator lower = map.lower_bound(px); 
    if (lower != map.end() && lower->first == px) 
     lower->second += 1; 
    else 
     map.insert(lower, std::pair<_Type,int>(px, 1)); 
} 
//... and compute the median by integrating from the one end until 
// until the appropriate sum is reached .. 

3) Плотная гистограмма.Так что это плотная гистограмма, но вместо простого 65536 массива, мы делаем поиск немного легче, разделив его на суб-контейнеры, например:

[0...65535] <- px 
[0...4095] <- px/16 
[0...255] <- px/256 
[0...15] <- px/4096 

Это делает вставку немного медленнее (постоянной времени), но поиск намного быстрее. Я нашел 16 хороший номер.

Рисунок Я проверил методы (1) красный, (2) синий и (3) черный друг от друга и 8bpp OpenCV (зеленый). Для всех, кроме OpenCV, входное изображение имеет шкалу серого цвета 16 бит. Пунктирные линии усекаются в динамическом диапазоне [0,255], а гладкие линии усекаются на [0, 8020] (с помощью умножения на 16 и сглаживания, чтобы добавить больше дисперсии на значения пикселей).

Интересно, что расхождение разреженной гистограммы по мере увеличения дисперсии значений пикселей возрастает. N-й элемент всегда безопасен, OpenCV является самым быстрым (если 8bpp в порядке), а плотная гистограмма отстает.

Я использовал Windows 7, 8 x 3,4 ГГц и Visual Studio v. 10. Mine работало многопоточно, реализация OpenCV однопоточная. Размер входного изображения 2136x3201 (http://i.imgur.com/gg9Z2aB.jpg, от Vogue).

[2]: Huang, T: "Двумерный Signal Processing II: Превращает и медианные фильтры", 1981

[3]: Вайс, B: "Быстрая медиана и Двустороннее Filtering", 2006

Answer 2

Я нашел это онлайн, это тот же алгоритм, который OpenCV имеет, однако, до 16 бит и оптимизирован для SSE.

https://github.com/aoles/EBImage/blob/master/src/medianFilter.c