Медианная фильтрация изображений

Необходимо отфильтровать медианным фильтром 5-мегапиксельное изображение (NxN).

Это довольно трудоёмкий алгоритм, если делать его в лоб. Сложность там будет что-то типа N*N*n*n*log(n), где N - размер изображений (для простоты асимптотик пусть будет квадратное), n - размер окна. Алгоритм таков: бежим по пикселям, собираем все пиксели окна, сортируем их и ищем медиану. Если медиану искать не сортировкой, а "недосортировкой Хаара" (я забыл правильное название линейного алгоритма поиска статистики), получится убрать логарифм. Хочется убрать n-ки.

Ещё один алгоритм. Организуем две кучи, суммарным размером n*n, значением будет значение пикселя. Добавление имеет асимптотику log(n), для поддержки удаления расширяем ключ, делаем специальный класс оповещения о смене ключа в куче, в общем удаление за log(n) тоже достигается (хотя, к сожалению, сильно вырастет константа, что очень удручает, так как константа и для добавление нормально подрастает).

Итог, у нас есть две кучи с логарифмическим временем вставки и удаления. Одна min-куча, и одна max-куча, организуем их так, чтобы их вершины как раз были бы медианным срезом всей коллекции (я на самом деле описал классический алгоритм для скользящей медианы, он описан в любом нормальном алгоритмическом источнике, например у Кормена).

Теперь поддерживаем эту пару куч для окна. Сдвиг окна вправо это n*log(n) операций, сдвиг вниз можно считать столько же, если заранее за O(N) предрассчитать кучи для крайних левых положений окна (тогда на самом деле сдвиг вниз займёт O(1), надо просто взять нужную кучу, но это уже детали, которые сейчас не так важны). В итоге каждый шаг окном имеет сложность n*log(n), итоговая сложность фильтрации O(N*N*n*log(n)), очень неплохо, время работы алгоритма сократится раз в 5-10.

Теперь вопросы.

1. Выше изложено переложение классического алгоритма скользящей медианы на двумерный случай. Не ошибся ли я где-то в этом переложении? Для классического одномерного алгоритма получаемая сложность окажется N*log(n), размер всей коллекции умноженный на логарифм размера окна, для двумерного по аналогии можно было бы ожидать сложности O(N*N*log(n*n)) = O(N*N*log(n)), однако в алгоритме выше так не получилось. Возможно это следствие какой-то ошибки.

2. Есть ли какие-то хитрости, позволяющие эффективно реализовать быстрое удаление из кучи, чтобы минимизировать константу в асимптотике? Потому что в моей реализации очень большие накладные расходы на хранение индексов, что замедляет в том числе и вставку.

3. Вышеизложенный алгоритм имеет огромный расход памяти, мы в начале инициализируем почти N куч. Можно ли как-то этот оверхед снизить, не потеряв в скорости?

4. Ну и наконец-то (может у меня XY-проблема?), может есть какой-то "правильный" и обкатанный алгоритм медианной фильтрации, который, возможно, даже лучше по асимптотике, а я занимаюсь велосипедостроением, причём не самого высокого качества? Это было бы идеально, так как отбрасывает все остальные вопросы :) .

PS. Этот фильтр будет применяться в задаче обработки видеопотока в реальном времени, нужно успевать выдавать хотя бы 14-16 кадров в секунду, и это при том, что просто отфильтровать это далеко не единственное, что делается с картинкой, отсюда такие попытки по оптимизации. Поэтому приходится бороться и за константу, а не только асимптотику.