Нужна помощь в векторизации этого кода
У меня 8-битное изображение. Для каждого пикселя мне нужно определить его порядковый номер в текущей строке. Например, если строка:
32 128 16 64,
тогда мне нужен результат:
1 3 0 2,
поскольку 32 является первым по величине значением в строке, 128 является третьим по величине, 16 является 0 самым высоким и 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 это результат, который я хочу.
Это можно сделать?
Решение
Я верю, что это поможет тебе. Он не требует выделений, стеков или сортировок, но предполагает, что ваш диапазон составляет 0-255 (например, uint8). Большее предположение: он будет эффективен только при наличии широких рядов. Если они действительно 4 пикселя в ширину, то я<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]]++;
}
ОК — так как это работает?
строка 1 в этой функции объявляет и очищает таблицу гистограмм.
строка 2 вычисляет гистограмму.
Строка 3 превращает его в подсчитанную сортировку — и поэтому Hist использует больший размер элемента, чем 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] … идеально
но я не совсем уверен, отвечает ли она вашей потребности в векторизации — 🙂
Другие решения
Еще один способ думать о том,
Для каждой строки создайте двоичное дерево поиска. При выполнении обхода по порядку мы можем получить ранг каждого пикселя.
Каждый элемент узла является структурой
// 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.
};
последовательность шагов для каждой строки будет:
a) O (w): создать двоичное дерево поиска, сохраняя позицию каждого пикселя также в узле.
б) O (w): начать обход по порядку. Для каждого узла заполните положение пикселя этого узла рангом (начните отсчет с первого узла как 0).