需要帮助向量化此代码

Question

我有一个8位的图像。对于每个像素，我需要计算出它在当前行的顺序位置。例如，如果行是:

32 128 16 64,

那么我需要结果:

1 3 0 2,

由于32是行中第1大的值，128是第3大的，16是第0大的，64是第2大的。

我需要对图像的所有行重复上述过程。以下是非矢量化代码:

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

因为最低值在第二列，下一个最低值在第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]]++;
}

那么它是如何工作的呢?
该函数的第1行声明并清空直方图表。
第2行计算直方图。
第3行将其转换为计数排序-这就是为什么hist使用比uint8更大的元素大小
第4行应用排序后的位置。

这里有两个技巧;首先，在第3行中，直方图"移动了1个索引"，这样第一个值总是"0"，而不是任何值，第二个值是第一个计数的值，以此类推。第二个技巧是第4行的"++"——总是确保序数值是唯一的。

让我们在你的输入上试试:
[32 128 16 64]
第二行:[0…1....1....1…1…][0,16, 32, 64, 128, 255]
第三行:[0…0....1....2…3…][0,16, 32, 64, 128, 255]
第4行:[1,3,0,2]…看起来对

让我们在稍微不同的输入上尝试一下:
[32 128 16 32]
第二行:[0…1....2....0…1…][0,16, 32, 64, 128, 255]
第三行:[0…0....1....3…3…][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.
};

每一行的步骤序列为:

a) O(w):创建一个二叉搜索树，将每个像素的位置也存储在节点中。

b) O(w):开始有序遍历。对于每个节点，用rank填充该节点的像素位置(从第一个节点开始计数为0)。