Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

Оптимизация программы по скорости на примере медианного фильтра

Введение

В данной статье я решил привести пример оптимизации по скорости исполнения алгоритма, предназначенного для обработки видео изображения. В качестве примера, мной был выбран алгоритм медианной фильтрации. Медианная фильтрация является эффективным способом подавления шумов, которые неизбежно появляются на цифровых камерах в условиях малого освещения сцены. Алгоритм этот достаточно ресурсоемок – так например, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. И если для обработки одиночных фотографий скорость в принципе не сильно важна, то при обработке видео потока скорость обработки кадра является критическим параметром при выборе алгоритма.

Для справки напоминаю суть алгоритма:

  1. Для каждой точки исходного изображения берется некоторая окрестность (в нашем случае 3x3).

  2. Точки данной окрестности сортируются по возрастанию яркости.

  3. Средняя точка (5-я для фильтра 3х3) отсортированной окрестности записывается в итоговое изображение.

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

Collapse )