Привет, Хабр! Меня зовут Роман Кузьмин, я занимаюсь развитием фреймворков искусственного интеллекта в YADRO. В этой статье я расскажу об оптимизации алгоритма компьютерного зрения — детекторе углов, основанном на глобальных и локальных свойствах кривизны, — который реализован с помощью библиотеки OpenCV под архитектуру RISC-V. 

С коллегами из НГТУ им. Р. Е. Алексеева мы добились лучшей эффективности алгоритма за счет алгоритмических оптимизаций и ручной векторизации с использованием RVV. Я подробно опишу, что и где мы изменили, а в конце статьи оценю прогресс с помощью тестов на плате Lichee Pi 4a.

Открытая и модульная архитектура RISC-V — это перспективная платформа для задач компьютерного зрения. Под нее активно адаптируют ключевые библиотеки, в том числе OpenCV. Для максимальной производительности здесь часто требуется низкоуровневая оптимизация с использованием векторных расширений.

Далее я расскажу о том, как мы провели алгоритмическую, низкоуровневую и компиляторную оптимизацию алгоритма детектора угловых точек на основе метода кривизны контура (CSS). В работе использовали:

  • Одноплатный компьютер Lichee Pi 4A с поддержкой RVV 0.7.1 — хотя сейчас актуальна более свежая версия RVV, возможности компьютера несколько нас ограничили.

  • Компилятор GCC 10.4.0 и эмулятор QEMU 6.0.94 для отладки и первичного тестирования на x86-хосте.

  • Систему сборки CMake 3.31.6.

Описание алгоритма

На С++ с помощью OpenCV мы реализовали детектор угловых точек на основе метода кривизны контура (Curvature Scale Space). Затем оптимизировали его под RISC-V и для повышения точности добавили в него фильтрацию ложных углов методом касательных. 

Исходный алгоритм был описан на Хабре и более подробно — в статье 2008 года Corner detector based on global and local curvature properties под авторством Хе и Янг. Алгоритм включает следующие этапы:

  1. 1. Построение карты границ. Исходное изображение преобразуется в градации серого. Затем для получения бинарной карты границ изображения применяется оператор Кэнни.

    2. Экстракция кривых. Функция extract_curve обходит карту границ и соединяет пиксели в непрерывные кривые (контуры) с заданным максимальным разрывом Gap_size. Кривые классифицируются на замкнутые и незамкнутые.

    3. Сглаживание и расчет кривизны. Каждая кривая сглаживается гауссовским фильтром (sig). Затем для каждой точки вычисляется первая и вторая производная (через конечные разности). На их основе — значение кривизны контуров (K), которые сохраняются в массиве.

    4. Поиск угловых точек. В массиве значений кривизны алгоритм ищет локальные максимумы изменения интенсивностей. Для каждого кандидата строится окрестность, и с помощью функции curve_tangent вычисляется угол между двумя касательными в этой точке. Если разность углов касательных меньше порогового значения T_angle, алгоритм считает, что найдена угловая точка.

    5. Дополнительно для незамкнутых кривых конечные точки могут добавляться как углы (флаг Endpoint).

Неоптимизированную реализацию этого алгоритма мы запустили в среде RISC-V и приняли за референс для последующих измерений производительности. Корректность алгоритма проверили на эталонных изображениях. Наибольшую вычислительную нагрузку в этом алгоритме создают подалгоритмы сглаживания и вычисления производных, расчеты кривизны и касательных. Именно они стали основными целями работы.

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

Алгоритмические оптимизации

Здесь мы сосредоточили усилия на том, чтобы снизить вычислительную сложность и более эффективно использовать ресурсы.

Кеширование гауссова ядра для исключения избыточных вычислений

В исходном алгоритме в функции get_corner гауссово ядро для сглаживания пересчитывалось при обработке каждой кривой:

vector<double> t, gau; // Идет создание для каждой кривой
for (int i = -width; i <= width; ++i) t.push_back(i);
for (auto& ti : t) { double val = exp(-ti*ti/(2*ssq)) / ...}

В эти расчеты мы ввели статическую переменную для кеширования ядра:

static vector<double> gau_cache;
static double cached_sig = -1.0;
if (sig != cached_sig) {
  // Пересчет ядра, только если изменился параметр sig
  // Вычисление new_gau
  gau_cache.swap(new_gau);
  cached_sig = sig;
}
const auto& gau = gau_cache; // Использование закешированного ядра

Многопоточность с использованием директив OpenMP

Мы распараллелили основной цикл обработки кривых (границ изображений) в функции get_corner с помощью директивы #pragma omp parallel for schedule(dynamic). 

Выбрали schedule(dynamic) для эффективной балансировки нагрузки между потоками при неравномерной вычислительной сложности кривых. Эта эффективность подтверждается значительным ускорением работы программы и снижением накладных расходов на синхронизацию, зафиксированных в профилях производительности. Итерации цикла распределяются между потоками динамически: каждый поток, завершив свою текущую часть работы, запрашивает следующую порцию (чанк) у планировщика.

Измененная часть кода get_corner.cpp:

  #pragma omp parallel for schedule(dynamic)
for (int i = 0; i < curve_num; ++i) {
  // Обработка отдельной кривой
}

Рефакторинг логики поиска локальных экстремумов

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

int state = 0; // 0: ожидаем рост, 1: ожидаем спад
  for (size_t j = 1; j < K.size(); ++j) {
    const double diff = K[j] - K[j - 1];
    if (state == 0 && diff > 0) { extremum.push_back(j-1); state=1; }
    else if (state == 1 && diff < 0) { extremum.push_back(j-1); state=0; }
  }

Векторные функции OpenCV

На этапе сглаживания кривых заменили скалярные операции свертки и вычисления производных на высокооптимизированные функции OpenCV. Вот исходный ручной цикл для применения гауссова ядра:

for (size_t n=0; n<smoothed.size(); ++n) {
    for (size_t k=0; k<gau.size(); ++k) { ... } // Вложенный цикл
  }

Вместо него мы использовали функцию filter2D:

cv::Mat smooth_x, smooth_y;
  cv::filter2D(ext_x, smooth_x, CV_64F, Mat(gau).t());
  cv::filter2D(ext_y, smooth_y, CV_64F, Mat(gau).t());

Низкоуровневая оптимизация

Здесь мы предварительно провели исследование эффективности векторных расширений RISC-V (RVV). А по итогам постарались по максимуму задействовать их там, где это оправдано.

Ручная векторизация функции гауссова размытия

С применением RVV-интринсиков мы реализовали ручную векторизацию функции гауссова размытия. Почему не автоматическую? Кастомный компилятор gcc, который разрабатывает для платы Lichee Pi поставщик чипов C910, предлагает такую опцию. Но для автоматической векторизации нужно обеспечить независимости итераций циклов, последовательный доступ к памяти и по возможности устранение ветвлений. А код функции гауссова размытия содержит так много ветвлений и вызовов сложных функций, что не поддался автоматической векторизации за счет флагов компиляции.

Реализация функции гауссова размытия с RVV-интринсиками:

vfloat64m1_t v_data_x = vle_v_f64m1(temp_x.data(), vl);
vfloat64m1_t v_data_y = vle_v_f64m1(temp_y.data(), vl);

vfloat64m1_t v_prod_x = vfmul_vv_f64m1(v_data_x, v_kernel, vl);
vfloat64m1_t v_prod_y = vfmul_vv_f64m1(v_data_y, v_kernel, vl);

vfloat64m1_t v_zero = vfmv_v_f_f64m1(0.0, vl);

vfloat64m1_t v_sum_x = vfredsum_vs_f64m1_f64m1(v_zero, v_prod_x, v_zero, vl);
vfloat64m1_t v_sum_y = vfredsum_vs_f64m1_f64m1(v_zero, v_prod_y, v_zero, vl);

sum_x += vfmv_f_s_f64m1_f64(v_sum_x, vl);
sum_y += vfmv_f_s_f64m1_f64(v_sum_y, vl);

Замена тяжеловесных библиотечных функций

Здесь наибольший результат принесла стала замена функции pow из библиотеки math на простые скалярные операции — возведение в степень через кратное умножение. Функция вместе с exp() использовалась в расчете гауссовского ядра для каждой точки, и в итоге замена на скалярные операции дала ускорение более чем в 30 раз.

Сравнительные результаты до и после замены функции pow(): сэкономлено 5,337 мс, подсчитано 596 углов (70% от фактического количества)
Сравнительные результаты до и после замены функции pow(): сэкономлено 5,337 мс, подсчитано 596 углов (70% от фактического количества)

Компиляторная оптимизация

Мы исследовали влияние компиляторных флагов на производительность и перепробовали разные их комбинации. Вот какая оказалась наиболее эффективной:

  • march=rv64gcv0p7 (генерация кода для 64-битного ядра с поддержкой векторных расширений v0.7);

  • O2 (баланс между производительностью и размером кода);

  • ftree-vectorize (включение автоматической векторизации циклов);

  • ffast-math (ускорение математических операций).

Замечу, что флаг ffast-math не является безопасным и может вызвать ошибки в логике вещественных чисел. Однако именно этот набор флагов обеспечил прирост производительности на 33% по сравнению с неоптимизированной версией (-O0).

Скорость выполнения алгоритма corner_detector_rvv с флагами O0, O2, O3 и без флагов. Number of tests — количество запусков. Time – время выполнения алгоритма. 
Скорость выполнения алгоритма corner_detector_rvv с флагами O0, O2, O3 и без флагов. Number of tests — количество запусков. Time – время выполнения алгоритма. 

А вот сравнительные результаты с разными оптимизациями. Самой успешной стала комбинация внедрения rvv-интринсиков в функции, упрощения арифметических операций и компиляции с нужными флагами:

Запуск на Lichee Pi 4A

На плате Lichee Pi 4A мы запустили базовую версию алгоритма corner_detector (cd), версию с алгоритмической оптимизацией, а также с алгоритмической и низкоуровневой оптимизацией. После всех оптимизаций исходный алгоритм стал на 39% быстрее:

Слева направо:

  • cd_alg_rvv_flag — первоначальный алгоритм оптимизировали алгоритмически и скомпилировали под RISC-V (автоматическая векторизация);

  • cd_alg_02 — первоначальный алгоритм оптимизировали алгоритмически и скомпилировали с -о2, ffast-math;

  • cd_rvv_flag — первоначальный алгоритм оптимизировали по RISC-V и скомпилировали с флагами для компиляции rvv (автоматическая векторизация);

  • cd_rvv_02 — первоначальный алгоритм оптимизировали по RISC-V и скомпилировали с -o2 и другими флагами, которые показали наилучший результат в компиляторной оптимизации;

  • cd — первоначальный алгоритм.

Cd_alg_rvv_flag оказался медленнее, чем cd_alg_02, то есть чистая алгоритмическая оптимизация выигрывает по скорости у автоматической векторизации алгоритма. Сd_rvv_02 оказался наиболее быстрым, что говорит об успешной векторной оптимизации, которая по скорости превзошла cd_alg_02 на LicheePi.

Разные виды оптимизации лучше всего отработали в разных частях алгоритма. В сложных нерегулярных участках кода — например, в алгоритмически оптимизированной функции размытия — ручная векторизация оказалась наиболее эффективна и ускорила выполнение кода на 6%. С другой стороны, для регулярных операций — например, сложения матриц — автоматическая векторизация компилятором обеспечила сопоставимую производительность. При этом очевидна экономия на разработке и поддержке кода.

Результат работы алгоритма до и после оптимизации
Результат работы алгоритма до и после оптимизации

Качество детектирования углов после внедрения всех оптимизаций кода упало практически в два раза по сравнению с базовым алгоритмом на основе метода кривизны контура (CSS). Здесь нужны дополнительные доработки, чтобы сохранить точность после оптимизации. При этом благодаря методу касательных новый детектор эффективнее фильтрует ложные срабатывания.

Результат работы оптимизированного алгоритма
Результат работы оптимизированного алгоритма

Несмотря на неоднозначность некоторых результатов, мы доказали: у RISC-V большой потенциал для задач компьютерного зрения. С помощью алгоритмических улучшений, целенаправленной низкоуровневой векторизации и тонкой настройки компилятора мы достигли значительного прироста производительности.

Выражаю благодарность П. С. Пшеницыной, Э. С. Соколовой и П. А. Шагаловой за совместную работу над исследованием, которое легло в основу этой статьи.

В рамках Зимней школы RISC-V сезона 2024–2025 студенты Университета Лобачевского (ННГУ) также оптимизировали OpenCV под RISC-V, но уже на уровне отдельных функций. Подробнее об этом проекте — в другой статье нашего блога.