このコードをベクトル化するのに役立つ

Question

私は8ビットイメージを持っています。各ピクセルについて、私は現在の行の順序位置を計算する必要があります。たとえば、行がある場合：32は、行の第1の最高値である

1 3 0 2, 

ので、128が最高3であり、16は最高64 0番目である：

32 128 16 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は簡単なコンパレータ機能です。

私は上記のコードをベクトル化することを試みた。この得た：私はOpenCVのが行われないので、1つの16ビットのチャネルに8ビットの値と、8ビットの順序をパックしなければならなかった

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

をマルチチャンネル画像のソート。これは私が必要とするものですが、そうではありません。例えば、入力のために、それは私与える：最低値が2列目にあるので

2 0 3 1 

を、次の最低は私がすることなく、必要な結果にこれを変換して行くにはどうすればよいなど0列目、です個別に各ピクセルにアクセスしますか？

基本的に、私は何とかこれをベクトル化する必要があります：xは私の現在のベクトル化コードが私を与え、y中間結果である

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

は私が望む結果です。

できますか？

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行目はカウントされたソートになります。なぜなら、histはuint8よりも大きな要素サイズを使用しているからです。
4行目はソートされた位置を適用します。

2つのトリックがあります。まず、3行目でヒストグラムが「1つのインデックスだけシフト」され、最初の値は常に0になり、2番目の値は最初のカウントとなります。 2番目のトリックは4行目の "++"です。常に序数が一意であることを保証します。

あなたの入力で試してみましょう：
[32 128 16 64]
2行目：[0 ... 1 .... 1 ... 1 ... 1 ... 0]インデックス[0,16,32,64,128,255]それぞれインデックス0,16,32,64,128,255で
行3：[0 ... 0 .... 1 ... 2 ... 3 ... 0] 、32、64、128、255]それぞれ
ライン4：
[32 128 16 32]
：[1、3、0、2] ...右

に見えるが、わずかに異なる入力をそれを試すことができます ライン2：イ​​ンデックス[0,16,32,64,128,255]でそれぞれ[0 ... 1 .... 2 .... 0 ... 1 ... 0]
ライン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. 
}; 

配列である：

）O（W）：また、すべてのピクセルの位置を格納することにより、バイナリサーチツリーを作成ノード内にある。

b）O（w）：順序通りのトラバーサルを開始します。すべてのノードについて、そのノードのピクセル位置をランク（最初のノードを0としてカウントを開始）で埋めます。