Нужна помощь в векторизации этого кода

Question

У меня есть 8-битное изображение. Для каждого пикселя мне нужно определить его порядковое положение в текущей строке. Например, если строка:

32 128 16 64, 

тогда я нужен результат:

1 3 0 2, 

, поскольку 32 является первым наибольшее значение в строке, 128 третий самый высокий, 16 0th высоким и 64 является вторым по величине.

Мне нужно повторить описанную выше процедуру для всех строк изображения. Вот, не Векторизованные коды:

for (int curr = 0; curr < new_height; ++curr) 
{ 
    vector<pair<unsigned char, char> > ordered; 
    for (char i = 0; i < 4; ++i) 
    { 
     unsigned char val = luma24.at<unsigned char>(curr, i); 
     ordered.push_back(pair<unsigned char, char>(val, i)); 
    } 
    sort(ordered.begin(), ordered.end(), cmpfun); 
    for (int i = 0; i < 4; ++i) 
     signature.at<char>(curr, ordered[i].second) = i; 
} 

luma24 является 8-битным изображением Читаю с, и она имеет new_height строк и 4 столбца. signature - это подписанное изображение того же размера (на данный момент игнорируйте разницу в знаке, поскольку оно не имеет значения) - это то место, где я сохраняю результат. cmpfun - тривиальная функция компаратора.

Я пытался векторизацией выше кода и получил это:

Mat ordinal; 
luma24.convertTo(ordinal, CV_16UC1, 256, 0); 
Mat sorted = ordinal.clone(); 
for (int i = 0; i < 4; ++i) 
    ordinal(Range::all(), Range(i, i+1)) += i; 
cv::sort(ordinal, sorted, CV_SORT_EVERY_ROW | CV_SORT_ASCENDING); 
bitwise_and(sorted, Scalar(0x00ff), ordinal); 
Mat ordinal8; 
ordinal.convertTo(ordinal8, CV_8SC1, 1, 0); 
ordinal8.copyTo(signature(Range::all(), Range(0, 4))); 

мне пришлось упаковать значение 8-битное и 8-битовые порядковый номер в одном 16-разрядный канал, так как OpenCV не выполняет сортировать для многоканальных изображений. Это почти то, что мне нужно, но не совсем. Для примера входных данных, он дает мне:

2 0 3 1 

, так как наименьшее значение находится в 2-м столбце, следующий наименьший в 0-я колонна и т.д. Как я могу идти о преобразовании этого в результате мне нужно без доступ к каждому пикселю индивидуально?

По существу, мне нужно как-то векторизации это:

uint8_t x[] = {2, 0, 3, 1}; 
uint8_t y[4]; 
for (uint8_t i = 0; i < 4; ++i) 
    y[x[i]] = i; 

где x промежуточный результат мой текущий Векторизованных код дает мне и y результат я хочу.

Можно ли это сделать?

Answer 1

Я считаю, что это поможет вам. Он не требует выделения или стеков или сортировок, но предполагает, что ваш диапазон равен 0-255 (например, uint8). Большее предположение: оно будет исполнено только в том случае, если у вас широкие ряды. Если они действительно имеют ширину в 4 пикселя, то i < 256 является своего рода уродливым. Есть способы сделать это уйти, но я предполагаю, что 4 пикселя - это всего лишь «например», для простоты.

void processRow (int* rowpos, uint8_t* pixelsForRow, int w) { 
    uint32_t i, pv, v=0, hist[256]={0}; 
    for (i=0; i<w; i++)  hist[pixelsForRow[i]]++; 
    for (i=0; i<256; i++) {pv=hist[i]; hist[i]=v; v+=pv;} 
    for (i=0; i<w; i++)  rowpos[i] = hist[pixelsForRow[i]]++; 
} 

OK - так как это работает?
строка 1 в этой функции объявляет и опустошает таблицу гистограмм.
строка 2 вычисляет гистограмму.
строка 3 превращает ее в подсчитанную сортировку - и поэтому в гистограмме используется размер более крупного элемента, чем uint8
строка 4 применяет отсортированную позицию.

Есть 2 трюка; Во-первых, в строке 3 гистограммы «сдвинуты на 1 индекс», поэтому первое значение всегда «0» не так, как было бы, а второе значение - это то, что было первым счетчиком, и так далее. Второй трюк - «++» в строке 4 - всегда гарантирует, что порядковое значение уникально.

Давайте попробуем его на вашем входе:
[32 128 16 64]
строка 2: [0 ... 1 .... 1 .... 1 ... 1 ... 0] по индексам [0, 16, 32, 64, 128, 255] соответственно
строка 3: [0 ... 0 .... 1 .... 2 ... 3 ... 0] по индексам [0, 16 , 32, 64, 128, 255], соответственно
строка 4: [1, 3, 0, 2] ... выглядит правильно

Позволяет попробовать его на несколько иной вход:
[32 128 16 32]
строка 2: [0 ... 1 .... 2 .... 0 ... 1 ... 0] по индексам [0, 16, 32, 64, 128, 255] соответственно
строка 3: [0 ... 0 .... 1 .... 3 ... 3. ..0] по индексам [0, 16, 32, 64, 128, 255] соответственно
строка 4: [1, 3, 0, 2] ... совершенная


, но я не совсем уверен если это соответствует вашей потребности в векторизации - :)

Answer 2

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

Каждый элемент узла представляет собой структуру

// Members of struct explained here. 
// row_pos: stores position of that pixel in that row. 
//  we populate this while creating binary search tree. 
// 
// rank: stores its rank in that row.() 
// while doing in-order traversal, we come to know rank of that pixel. At that point only, we update that pixel location with its rank. 

typedef struct node 
{ 
    int row_pos, rank; 
    node *left, *right; // left and right nodes. 
}; 

последовательность шагов для каждой строки будет:

а) О (ж): создать дерево двоичного поиска, сохраняя положение каждого пикселя также в узле.

b) O (w): начать обход в порядке. Для каждого узла заполняйте местоположение пикселя этого узла рангом (начало отсчета с первым узлом как 0).