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

Question

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

Я пробовал несколько методов, таких как сортировка массива (с использованием 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 самого по себе, а также различным частям - как и ожидался узкой является in:

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

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

Спасибо!

EDIT Я попытался использовать 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, используя среднюю функцию ...

Answer 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; } 

Answer 2

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

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

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

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

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

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

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

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

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

Answer 3

Скорее всего, быстрее найти его из исходных данных.

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