OpenCV C ++. Быстро рассчитать матрицу путаницы

int TP = 0,FP = 0,FN = 0,TN = 0;
cv::Mat truth(60,60, CV_8UC1);
cv::Mat detections(60,60, CV_8UC1);

this->loadResults(truth, detections); // loadResults(cv::Mat& t, cv::Mat& d);

Короче, ни один из трех.

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

struct result_t
{
int TP;
int FP;
int FN;
int TN;
};

Это позволит нам обернуть каждую реализацию в функцию со следующей сигнатурой, чтобы упростить тестирование и оценку производительности. (Обратите внимание, что я использую cv::Mat1b чтобы сделать это явным, мы хотим только маты типа CV_8UC1:

result_t conf_mat_x(cv::Mat1b truth, cv::Mat1b detections);

Я буду измерять производительность с помощью случайно сгенерированных данных размером 4096 x 4096.

Я использую MSVS2013 64bit с OpenCV 3.1 здесь. К сожалению, MSVS2010 не настроен с OpenCV, готовым для тестирования этого, и временным кодом с использованием c ++ 11, поэтому вам может потребоваться изменить его для компиляции.

---

Вариант 1 — «Прямые звонки»

Обновленная версия вашего кода выглядит так:

result_t conf_mat_1a(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };
for (int r(0); r < detections.rows; ++r) {
for (int c(0); c < detections.cols; ++c) {
int d(detections.at<uchar>(r, c));
int t(truth.at<uchar>(r, c));
if (d&&t) { ++result.TP; }
if (d&&!t) { ++result.FP; }
if (!d&&t) { ++result.FN; }
if (!d&&!t) { ++result.TN; }
}
}
return result;
}

Производительность и результаты:

#0:     min=120.017     mean=123.258    TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Основная проблема здесь в том, что это (особенно с VS2010) вряд ли будет автоматически векторизовано, поэтому будет довольно медленным. Использование SIMD может привести к ускорению на порядок. Дополнительно повторные звонки cv::Mat::at может добавить некоторые накладные расходы, а также.

Здесь действительно нечего получить, мы должны быть в состоянии добиться большего.

---

Вариант 2 — «RAM Heavy»

Код:

result_t conf_mat_2a(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };
{
cv::Mat truePos = detections.mul(truth);
result.TP = cv::countNonZero(truePos);
}
{
cv::Mat falsePos = detections.mul(~truth);
result.FP = cv::countNonZero(falsePos);
}
{
cv::Mat falseNeg = truth.mul(~detections);
result.FN = cv::countNonZero(falseNeg);
}
{
cv::Mat trueNeg = (~truth).mul(~detections);
result.TN = cv::countNonZero(trueNeg);
}

return result;
}

Производительность и результаты:

#1:     min=63.993      mean=68.674     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Это уже примерно вдвое быстрее, хотя и выполняется много ненужной работы.

Умножение (с насыщением) кажется излишним — bitwise_and будет делать работу, а также потенциально может сбрить немного времени.

Огромные накладные расходы налагаются рядом избыточных распределений матриц. Вместо выделения новой матрицы для каждого из truePos, falsePos, falseNeg а также trueNegмы можем использовать то же самое cv::Mat для всех 4 случаев. Поскольку форма и тип данных всегда будут одинаковыми, это означает, что произойдет только 1 распределение вместо 4.

---

Код:

result_t conf_mat_2b(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };

cv::Mat temp;
cv::bitwise_and(detections, truth, temp);
result.TP = cv::countNonZero(temp);
cv::bitwise_and(detections, ~truth, temp);
result.FP = cv::countNonZero(temp);
cv::bitwise_and(~detections, truth, temp);
result.FN = cv::countNonZero(temp);
cv::bitwise_and(~detections, ~truth, temp);
result.TN = cv::countNonZero(temp);

return result;
}

Производительность и результаты:

#2:     min=50.995      mean=52.440     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Необходимое время было сокращено на ~ 20% по сравнению с conf_mat_2a,

Далее обратите внимание, что вы рассчитываете ~truth а также ~detections дважды. Следовательно, мы можем исключить операции вместе с 2 дополнительными выделениями, используя их также.

NB: использование памяти не изменится — раньше нам требовалось 3 временных массива, и это все еще так.

---

Код:

result_t conf_mat_2c(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };

cv::Mat inv_truth(~truth);
cv::Mat inv_detections(~detections);

cv::Mat temp;
cv::bitwise_and(detections, truth, temp);
result.TP = cv::countNonZero(temp);
cv::bitwise_and(detections, inv_truth, temp);
result.FP = cv::countNonZero(temp);
cv::bitwise_and(inv_detections, truth, temp);
result.FN = cv::countNonZero(temp);
cv::bitwise_and(inv_detections, inv_truth, temp);
result.TN = cv::countNonZero(temp);

return result;
}

Производительность и результаты:

#3:     min=37.997      mean=38.569     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Необходимое время было сокращено на ~ 40% по сравнению с conf_mat_2a,

Есть еще потенциал для улучшения. Давайте сделаем некоторые наблюдения.

• element_count == rows * cols где rows а также cols представляют высоту и ширину cv::Mat (мы можем использовать cv::Mat::total()).
• TP + FP + FN + TN == element_count так как каждый элемент принадлежит ровно 1 из 4 наборов.
• positive_count количество ненулевых элементов в detections,
• negative_count это число нулевых элементов в detections,
• positive_count + negative_count == element_count так как каждый элемент принадлежит ровно 1 из 2 наборов
• TP + FP == positive_count
• TN + FN == negative_count

Используя эту информацию, мы можем рассчитать TN используя простую арифметику, тем самым устраняя bitwise_and и один countNonZero, Мы можем аналогичным образом рассчитать FPустраняя другого bitwise_andи с помощью второго countNonZero вычислять positive_count вместо.

Поскольку мы устранили оба использования inv_truthмы можем оставить это.

Примечание: использование памяти было уменьшено — теперь у нас есть только 2 временных массива.

---

Код:

result_t conf_mat_2d(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };

cv::Mat1b inv_detections(~detections);
int positive_count(cv::countNonZero(detections));
int negative_count(static_cast<int>(truth.total()) - positive_count);

cv::Mat1b temp;
cv::bitwise_and(truth, detections, temp);
result.TP = cv::countNonZero(temp);
result.FP = positive_count - result.TP;

cv::bitwise_and(truth, inv_detections, temp);
result.FN = cv::countNonZero(temp);
result.TN = negative_count - result.FN;

return result;
}

Производительность и результаты:

#4:     min=22.494      mean=22.831     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Необходимое время было сокращено на ~ 65% по сравнению с conf_mat_2a,

Наконец, так как нам нужно только inv_detections однажды мы можем использовать повторно temp хранить его, избавляясь от еще одного выделения и еще больше уменьшая объем памяти.

Примечание: использование памяти было уменьшено — теперь у нас есть только 1 временный массив.

---

Код:

result_t conf_mat_2e(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };

int positive_count(cv::countNonZero(detections));
int negative_count(static_cast<int>(truth.total()) - positive_count);

cv::Mat1b temp;
cv::bitwise_and(truth, detections, temp);
result.TP = cv::countNonZero(temp);
result.FP = positive_count - result.TP;

cv::bitwise_not(detections, temp);
cv::bitwise_and(truth, temp, temp);
result.FN = cv::countNonZero(temp);
result.TN = negative_count - result.FN;

return result;
}

Производительность и результаты:

#5:     min=16.999      mean=17.391     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Необходимое время было сокращено на ~ 72% по сравнению с conf_mat_2a,

---

Вариант 3 — «для каждого с лямбдой»

Это опять-таки страдает от той же проблемы, что и вариант 1, а именно маловероятно, что оно будет векторизовано, поэтому оно будет относительно медленным.

Основная проблема с вашей реализацией заключается в том, что forEach запускает функцию параллельно на нескольких срезах ввода, и нет никакой синхронизации. Текущая реализация возвращает неверные результаты.

Тем не менее, идея распараллеливания может быть применена с некоторыми усилиями к лучшему из Варианта 2.

---

Вариант 4 — «Параллель»

Давайте улучшать conf_mat_2e используя в своих интересах cv::parallel_for_. Самый простой способ распределить нагрузку между рабочими потоками — сделать это построчно.

Мы можем избежать необходимости синхронизации, разделяя промежуточный cv::Mat3i который будет держать TP, FP, а также FN для каждого ряда (напомним, что TN может быть рассчитано от других 3 в конце). Поскольку каждая строка обрабатывается только одним рабочим потоком, нам не нужно синхронизироваться. Как только все строки были обработаны, простой cv::sum даст нам всего TP, FP, а также FN, TN Затем рассчитывается.

NB: Мы можем снова уменьшить требования к памяти — нам нужен один буфер, охватывающий одну строку для каждого работника. Кроме того, нам нужно 3 * rows целые числа для хранения промежуточных результатов.

Код:

class ParallelConfMat : public cv::ParallelLoopBody
{
public:
enum
{
TP = 0
, FP = 1
, FN = 2
};

ParallelConfMat(cv::Mat1b& truth, cv::Mat1b& detections, cv::Mat3i& result)
: truth_(truth)
, detections_(detections)
, result_(result)
{
}

ParallelConfMat& operator=(ParallelConfMat const&)
{
return *this;
};

virtual void operator()(cv::Range const& range) const
{
cv::Mat1b temp;
for (int r(range.start); r < range.end; r++) {
cv::Mat1b detections(detections_.row(r));
cv::Mat1b truth(truth_.row(r));
cv::Vec3i& result(result_.at<cv::Vec3i>(r));

int positive_count(cv::countNonZero(detections));
int negative_count(static_cast<int>(truth.total()) - positive_count);

cv::bitwise_and(truth, detections, temp);
result[TP] = cv::countNonZero(temp);
result[FP] = positive_count - result[TP];

cv::bitwise_not(detections, temp);
cv::bitwise_and(truth, temp, temp);
result[FN] = cv::countNonZero(temp);
}
}

private:
cv::Mat1b& truth_;
cv::Mat1b& detections_;
cv::Mat3i& result_; // TP, FP, FN per row
};

result_t conf_mat_4(cv::Mat1b truth, cv::Mat1b detections)
{
CV_Assert(truth.size == detections.size);

result_t result = { 0 };

cv::Mat3i partial_results(truth.rows, 1);
cv::parallel_for_(cv::Range(0, truth.rows)
, ParallelConfMat(truth, detections, partial_results));
cv::Scalar reduced_results = cv::sum(partial_results);

result.TP = static_cast<int>(reduced_results[ParallelConfMat::TP]);
result.FP = static_cast<int>(reduced_results[ParallelConfMat::FP]);
result.FN = static_cast<int>(reduced_results[ParallelConfMat::FN]);
result.TN = static_cast<int>(truth.total()) - result.TP - result.FP - result.FN;

return result;
}

Производительность и результаты:

#6:     min=1.496       mean=1.966      TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216

Он работает на 6-ядерном процессоре с включенным HT (то есть 12 потоков).

Время выполнения было уменьшено на ~ 97,5% по сравнению с conf_mat_2a,

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

---

Тестовый код:

#include <opencv2/opencv.hpp>

#include <chrono>
#include <iomanip>

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::microseconds;

struct result_t
{
int TP;
int FP;
int FN;
int TN;
};

/******** PASTE all the conf_mat_xx functions here *********/

int main()
{
int ROWS(4 * 1024), COLS(4 * 1024), ITERS(32);

cv::Mat1b truth(ROWS, COLS);
cv::randu(truth, 0, 2);
truth *= 255;

cv::Mat1b detections(ROWS, COLS);
cv::randu(detections, 0, 2);
detections *= 255;

typedef result_t(*conf_mat_fn)(cv::Mat1b, cv::Mat1b);
struct test_info
{
conf_mat_fn fn;
std::vector<double> d;
result_t r;
};
std::vector<test_info> info;
info.push_back({ conf_mat_1a });
info.push_back({ conf_mat_2a });
info.push_back({ conf_mat_2b });
info.push_back({ conf_mat_2c });
info.push_back({ conf_mat_2d });
info.push_back({ conf_mat_2e });
info.push_back({ conf_mat_4 });

// Warm-up
for (int n(0); n < info.size(); ++n) {
info[n].fn(truth, detections);
}

for (int i(0); i < ITERS; ++i) {
for (int n(0); n < info.size(); ++n) {
high_resolution_clock::time_point t1 = high_resolution_clock::now();
info[n].r = info[n].fn(truth, detections);
high_resolution_clock::time_point t2 = high_resolution_clock::now();
info[n].d.push_back(static_cast<double>(duration_cast<microseconds>(t2 - t1).count()) / 1000.0);
}
}

for (int n(0); n < info.size(); ++n) {
std::cout << "#" << n << ":"<< std::fixed << std::setprecision(3)
<< "\tmin=" << *std::min_element(info[n].d.begin(), info[n].d.end())
<< "\tmean=" << cv::mean(info[n].d)[0]
<< "\tTP=" << info[n].r.TP
<< "\tFP=" << info[n].r.FP
<< "\tTN=" << info[n].r.TN
<< "\tFN=" << info[n].r.FN
<< "\tTotal=" << (info[n].r.TP + info[n].r.FP + info[n].r.TN + info[n].r.FN)
<< "\n";
}
}

---

Производительность и результаты MSVS2015, Win64, OpenCV 3.4.3:

#0:     min=119.797     mean=121.769    TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#1:     min=64.130      mean=65.086     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#2:     min=51.152      mean=51.758     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#3:     min=37.781      mean=38.357     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#4:     min=22.329      mean=22.637     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#5:     min=17.029      mean=17.297     TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216
#6:     min=1.827       mean=2.017      TP=4192029      FP=4195489      TN=4195118      FN=4194580      Total=16777216