Это не совсем доступ к пикселям. Это больше о количестве вычислений, которые вы делаете для каждого пикселя, возможно векторизация вычислений, возможно распараллеливание вычислений (как вы делали во второй попытке) и многое другое (но мы, к счастью, можем проигнорировать эти детали здесь).
Давайте сначала сосредоточимся на сценарии, в котором мы не используем явного распараллеливания (т. Е. Пока нет forEach).
Давайте начнем с вашей исходной пороговой функции, сделаем ее немного более краткой и отметим ее как встроенную(что помогает незначительно):
inline void complicatedThreshold(Pixel& pixel)
{
if (std::pow(double(pixel.x) / 10, 2.5) > 100) {
pixel = { 255, 255, 255 };
} else {
pixel = { 0, 0, 0 };
}
}
и запустим его следующим образом:
void impl_1(cv::Mat frame)
{
auto pixel = frame.ptr<Pixel>();
auto const endPixel = pixel + frame.total();
for (; pixel != endPixel; ++pixel) {
complicatedThreshold(*pixel);
}
}
Мы проверим это (и улучшенные версии) на случайно сгенерированном 3-канальном изображенииразмер 8192x8192.
Базовая линия завершается за 3139 мс.
Используя impl_1 в качестве базовой линии, мы проверим все улучшения на корректность, используя следующиефункция шаблона:
template <typename T>
void require_same_result(cv::Mat frame, T const& fn1, T const& fn2)
{
cv::Mat working_frame_1(frame.clone());
fn1(working_frame_1);
cv::Mat working_frame_2(frame.clone());
fn2(working_frame_2);
if (cv::sum(working_frame_1 != working_frame_2) != cv::Scalar(0, 0, 0, 0)) {
throw std::runtime_error("Mismatch.");
}
}
Улучшение 1
Мы можем попытаться воспользоваться оптимизированными функциями, которые предоставляет OpenCV.
Напомним, что для каждого пикселя мы выполняем пороговую операцию при следующем условии:
std::pow(double(pixel.x) / 10, 2.5) > 100
Прежде всего, нам нужен только первый канал для наших вычислений. Давайте извлечем его, используя cv::extractChannel.
Далее, нам нужно преобразовать первый канал в тип double. Для этого мы можем использовать cv::Mat::convertTo. Эта функция предоставляет еще одно преимущество - она позволяет нам указывать коэффициент масштабирования. Мы можем предоставить alpha коэффициент 0.1, чтобы позаботиться о делении на 10. В этом же вызове
В качестве следующего шага мы используем cv::pow для выполнения возведения в степеньэффективным образом на весь массив. Мы сравниваем результат с пороговым значением 100. Оператор сравнения, который предоставляет OpenCV, вернет 255 для true и 0 для false. Учитывая это, нам просто нужно объединить 3 идентичные копии полученного массива, и все готово.
void impl_2(cv::Mat frame)
{
cv::Mat1b first_channel;
cv::extractChannel(frame, first_channel, 0);
cv::Mat1d tmp;
first_channel.convertTo(tmp, CV_64FC1, 0.1);
cv::pow(tmp, 2.5, tmp);
first_channel = tmp > 100;
cv::merge(std::vector<cv::Mat>{ first_channel, first_channel, first_channel }, frame);
}
Эта реализация завершается за 842 мс.
Улучшение 2
Этот расчет на самом деле не требует двойной точности ... давайте выполним его только с плавающей точкой.
void impl_3(cv::Mat frame)
{
cv::Mat1b first_channel;
cv::extractChannel(frame, first_channel, 0);
cv::Mat1f tmp;
first_channel.convertTo(tmp, CV_32FC1, 0.1);
cv::pow(tmp, 2.5, tmp);
first_channel = tmp > 100;
cv::merge(std::vector<cv::Mat>{ first_channel, first_channel, first_channel }, frame);
}
Эта реализация завершается за 516 мс.
Улучшение 3
ОК, но подождите. Для каждого пикселя мы должны разделить на 10 (или умножить на 0,1), а затем вычислить 2,5-ую экспоненту (это будет дорого) ... но есть только 256 возможных входных значений для изображения, которое может иметь миллионы пикселей. Что, если мы предварительно вычислили справочную таблицу и использовали ее вместо расчета на пиксель?
cv::Mat make_lut()
{
cv::Mat1b result(256, 1);
for (uint32_t i(0); i < 256; ++i) {
if (pow(double(i) / 10, 2.5) > 100) {
result.at<uchar>(i, 0) = 255;
} else {
result.at<uchar>(i, 0) = 0;
}
}
return result;
}
void impl_4(cv::Mat frame)
{
cv::Mat lut(make_lut());
cv::Mat first_channel;
cv::extractChannel(frame, first_channel, 0);
cv::LUT(first_channel, lut, first_channel);
cv::merge(std::vector<cv::Mat>{ first_channel, first_channel, first_channel }, frame);
}
Эта реализация завершается за 68 мс.
Улучшение 4
Однако нам не нужен справочный стол. Мы можем сделать некоторую математику, чтобы упростить эту «сложную» пороговую функцию:
\left(\frac{x}{10}\right)^{2.5} > 100">
Давайте применим соответствующую обратную величину для исключения возведения в степень с левой стороны.
\frac{x}{10} > \sqrt[2.5]{100}">
И позвольте нам подразумевать правую часть (это константа).
\frac{x}{10} > 6.30957">
Наконец, давайте умножим на 10, чтобы исключить дробь в левой части. .
x > 63.0957">
И поскольку мы имеем дело только с целыми числами, мы можем использовать
x > 63
ОК, давайте попробуем этос первым вариантом.
inline void complicatedThreshold_2(Pixel& pixel)
{
if (pixel.x > 63) {
pixel = { 255, 255, 255 };
} else {
pixel = { 0, 0, 0 };
}
}
void impl_5(cv::Mat frame)
{
auto pixel = frame.ptr<Pixel>();
auto const endPixel = pixel + frame.total();
for (; pixel != endPixel; pixel++) {
complicatedThreshold_2(*pixel);
}
}
Эта реализация завершается за 166 мс.
Примечание: как бы плохо это ни казалось по сравнению с предыдущим шагом, это почти20-кратное улучшение по сравнению с аналогичным базовым уровнем.
Улучшение 5
Это действительно похоже на пороговую операцию на первом канале, которая реплицируется на оставшиеся 2 канала.
void impl_6(cv::Mat frame)
{
cv::Mat first_channel;
cv::extractChannel(frame, first_channel, 0);
cv::threshold(first_channel, first_channel, 63, 255, cv::THRESH_BINARY);
cv::merge(std::vector<cv::Mat>{ first_channel, first_channel, first_channel }, frame);
}
Эта реализация завершается за 65 мс.
Время попытаться распараллелить это. Начнем с forEach.
Параллельная реализация базового алгоритма:
void impl_7(cv::Mat frame)
{
frame.forEach<Pixel>(
[](Pixel& pixel, const int* position)
{
complicatedThreshold(pixel);
}
);
}
Эта реализация завершается за 350 мс.
Параллельная реализация упрощенного алгоритма:
void impl_8(cv::Mat frame)
{
frame.forEach<Pixel>(
[](Pixel& pixel, const int* position)
{
complicatedThreshold_2(pixel);
}
);
}
Эта реализация завершается за 20 мс.
Это очень хорошо, мы в 157 раз лучше по сравнению с оригинальным наивным алгоритмом. Даже бьет лучшую попытку непараллелизации почти в 3 раза. Можем ли мы сделать лучше?
Дальнейшие улучшения
Еще один простой вариант - попробовать parallel_for_.
typedef void(*impl_fn)(cv::Mat);
void impl_parallel(cv::Mat frame, impl_fn const& fn)
{
cv::parallel_for_(cv::Range(0, frame.rows), [&](const cv::Range& range) {
for (int r = range.start; r < range.end; r++) {
fn(frame.row(r));
}
});
}
void impl_9(cv::Mat frame)
{
impl_parallel(frame, impl_1);
}
void impl_10(cv::Mat frame)
{
impl_parallel(frame, impl_2);
}
void impl_11(cv::Mat frame)
{
impl_parallel(frame, impl_3);
}
void impl_12(cv::Mat frame)
{
impl_parallel(frame, impl_4);
}
void impl_13(cv::Mat frame)
{
impl_parallel(frame, impl_5);
}
void impl_14(cv::Mat frame)
{
impl_parallel(frame, impl_6);
}
Время:
Test 9 minimum: 355 ms.
Test 10 minimum: 108 ms.
Test 11 minimum: 62 ms.
Test 12 minimum: 25 ms.
Test 13 minimum: 19 ms.
Test 14 minimum: 11 ms.
Итак, пошло, 285-кратное улучшение на 6-ядерном процессоре с включенным HT.