Geek asks and answers

Need help in vectorizing this code

I have an 8 bit image. For each pixel, I need to determine its ordinal position in the current line. For example, if the line:

32 128 16 64,

then i need the result:

1 3 0 2,

since 32 is the first highest value in a row, 128 is in 3rd place, 16 is in 0th place, and 64 is in second.

I need to repeat the above procedure for all lines of the image. Here is a non-vectorized code:

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

luma24is an 8 bit image that I am reading and has new_heightrows and 4 columns. signature- this is a signed image of the same size (for now, ignore the difference in the sign, because it does not matter) - this is where I store the result. cmpfunis the trivial function of the comparator.

I tried to vectorize the above code and got the following:

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

, next-lower 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 - , .

?

+5
2

, . , , 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 .

; -, 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]...


, -:)

0

, , . , .

node

// 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): , node.

b) O (w): . node node ( node 0).

0

More articles:


All Articles