Сверхбыстрая медиана матрицы в opencv (так же быстро, как и матрица)

Я пишу некоторый код в openCV и хочу найти медианное значение очень большого матричного массива (одноканальное серое, float).

Я попробовал несколько методов, таких как сортировка массива (с использованием std:: sort) и выбор средней записи, но он очень медленный, если сравнивать с медианной функцией в Matlab. Если быть точным - то, что занимает 0,25 секунды в Matlab, занимает более 19 секунд в openCV.

Мое исходное изображение изначально представляет собой 12-битное изображение в оттенках серого с размерами 3840x2748 (~ 10,5 мегапикселей), преобразованное в float (CV_32FC1), где теперь все значения отображаются в диапазон [0,1] и в какой-то момент код я запрашиваю медианное значение, вызывая:

double myMedianValue = medianMat(Input);

Если функция medianMat:

double medianMat(cv::Mat Input){    
    Input = Input.reshape(0,1); // spread Input Mat to single row
    std::vector<double> vecFromMat;
    Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat    
    std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat
        if (vecFromMat.size()%2==0) {return (vecFromMat[vecFromMat.size()/2-1]+vecFromMat[vecFromMat.size()/2])/2;} // in case of even-numbered matrix
    return vecFromMat[(vecFromMat.size()-1)/2]; // odd-number of elements in matrix
}

Я приурочил функцию medinaMat сам по себе, а также различные части - как и ожидалось, узкое место:

  std::sort( vecFromMat.begin(), vecFromMat.end() ); // sort vecFromMat

Есть ли у кого-нибудь эффективное решение?

Спасибо!

ИЗМЕНИТЬ Я попытался использовать std:: nth_element, указанный в ответе Ади Шавита.

Функция medianMat теперь читается как:

double medianMat(cv::Mat Input){    
Input = Input.reshape(0,1); // spread Input Mat to single row
std::vector<double> vecFromMat;
Input.copyTo(vecFromMat); // Copy Input Mat to vector vecFromMat
std::nth_element(vecFromMat.begin(), vecFromMat.begin() + vecFromMat.size() / 2, vecFromMat.end());
return vecFromMat[vecFromMat.size() / 2];}

Время работы снизилось с 19 секунд до 3,5 секунд. Это все еще не так близко к 0,25 секунды в Matlab, используя медианную функцию...

Ответы

Ответ 1

OK.

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

Я в основном создаю гистограмму значений для моего исходного ввода с 2 ^ 12 = 4096 бит, вычисляю CDF и нормализую его, чтобы он отображался от 0 до 1 и находил наименьший индекс в CDF, который равен или больше 0,5. Затем я делю этот индекс на 12 ^ 2 и, таким образом, получаю запрашиваемое среднее значение. Теперь он работает через 0,11 секунды (и в режиме отладки без больших оптимизаций), что меньше половины времени, необходимого в Matlab.

Здесь функция (nVals = 4096 в моем случае соответствует 12-битным значениям):

double medianMat(cv::Mat Input, int nVals){

// COMPUTE HISTOGRAM OF SINGLE CHANNEL MATRIX
float range[] = { 0, nVals };
const float* histRange = { range };
bool uniform = true; bool accumulate = false;
cv::Mat hist;
calcHist(&Input, 1, 0, cv::Mat(), hist, 1, &nVals, &histRange, uniform, accumulate);

// COMPUTE CUMULATIVE DISTRIBUTION FUNCTION (CDF)
cv::Mat cdf;
hist.copyTo(cdf);
for (int i = 1; i <= nVals-1; i++){
    cdf.at<float>(i) += cdf.at<float>(i - 1);
}
cdf /= Input.total();

// COMPUTE MEDIAN
double medianVal;
for (int i = 0; i <= nVals-1; i++){
    if (cdf.at<float>(i) >= 0.5) { medianVal = i;  break; }
}
return medianVal/nVals; }

Ответ 2

Сортировка и принятие среднего элемента - не самый эффективный способ найти медиану. Для этого требуются операции O (n log n).

С С++ вы должны использовать std::nth_element() и взять средний итератор. Это операция O (n):

nth_element - это алгоритм частичной сортировки, который упорядочивает элементы в [first, last) таким образом, что:

  • Элемент, на который указывает nth, изменяется на любой элемент, который будет присутствовать в этой позиции , если [first, last) был отсортирован.
  • Все элементы перед этим новым n-м элементом меньше или равны элементам после нового n-го элемента.

Кроме того, ваши исходные данные являются 12-битными целыми числами. Ваша реализация делает несколько вещей, которые делают сравнение с Matlab проблематичным:

  • Вы преобразовали в плавающую точку (CV_32FC1 или double или оба), это дорого и требует времени
  • Код имеет дополнительную копию для vector<double>
  • Операции с поплавком и особенно удвоения стоят больше, чем на целые числа.

Предполагая, что ваше изображение непрерывно в памяти, как и по умолчанию для OpenCV, вы должны использовать CV_16C1 и работать непосредственно с массивом данных после reshape()

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

Документы OpenCV имеют несколько tutorials on как построить гистограммы. Когда у вас есть гистограмма, скопируйте значения bin до тех пор, пока не получите пропуск 3840x2748/2. Этот бункер является вашим медианом.

Ответ 3

Вероятно, быстрее найти его из исходных данных.

Поскольку исходные данные имеют 12-битные значения, есть только 4096 различных возможных значений. Это хороший и маленький стол! Пройдите все данные за один проход и подсчитайте, сколько из каждого значения у тебя есть. Это операция O (n). Тогда легко найти медианную, только считать size/2 элементы с любого конца таблицы.