RGB値の配列から平面を切り取るアルゴリズム（

Question

）R1 G1 B1 R2 G2 B2 R3 G3 B3 ... Rn Gn BnになるバイトRGB値のフラットな配列があります。だから、私のデータは次のようになります。

char imageData[WIDTH * HEIGHT * 3]; 

しかし、私は、このデータの単一平面を想定し、既存のCライブラリにWIDTH * HEIGHT配列を渡したいです。これは、R値（または単にG、またはBのみ）のシーケンスです。

新しい配列を割り当ててデータ（duh）をコピーするのは簡単です。しかし、イメージは非常に大きいです。もしそれがCライブラリではなく、 "スライシング"トラバーサルをフィニッシュするための何らかの反復インタフェースをとったなら、それは素晴らしいことでしょう。しかし、私は呼び出しているコードを編集することはできません...シーケンシャルメモリのブロックへの普通の古いポインタが必要です。

ただし、この配列への書き込みアクセス権があります。カラープレーンにソートするルーチンを作成することは実行可能です。私はまたそれを戻す逆変換が必要ですが、定義上、それをプレーンにソートした同じメソッドを適用してソートを解除することができます。

このアレイを効率的に（効率的に）R1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bnにしてから、もう一度戻すことはできますか？非純粋なアルゴリズムはありますか？

Answer 1

char *imageData = malloc (WIDTH * HEIGHT * 3 * sizeof(char)); 

この関数このR1 R2 R3を行う... RnのG1 G2 G3···GnをB1 B2 B3···Bnと,,

char *toRGB(char *imageData, int WIDTH, int HEIGHT){ 
    int len = WIDTH * HEIGHT; 
    char *RGB = malloc (len * sizeof(char)); 
    int i, j = 0,flag = 0; 

    for(i=0 ; i<=len ; i++, j+=3){ 
     if(j<len) 
      RGB[i] = imageData[j]; 
     else{ 
      switch(flag){ 
       case 0: j=-2; flag=1; break; // j=-2 the next iteration will start at j=1 
       case 1: j=-1; break; // j=-1 the next iteration will start at j=2 
      } 
     } 
    } 
    return RGB; 
} 

Answer 2

の行列を転置する方法について説明"A Simple In-Place Algorithm for In-Shuffle"本稿2 * Nと他の場合のためのヒントを与えるので、3 * Nも可能です。 This answer to other questionは、実際に可能であることを示しています。

または、転置された場所に各値を書き込んだり、その場所から値を取得したり、サイクルが接続されるまで続きを繰り返すアルゴリズムを使用します。処理された値をビットベクトルにフラグを立てます。このベクトルがすべて1になるまで続けます。

両方のアルゴリズムはキャッシュに適していません。おそらくPREFETCH命令を賢明に使用すると、これを改善できます。

編集：

C++、単一平面にRGBは、最適化されていない：

#include <iostream> 
#include <bitset> 
#include <vector> 

enum {N = 8}; 

void transpose(std::vector<char>& a) 
{ 
    std::bitset<3*N> b; 

    for (int i = 1; i < 3*N; ++i) 
    { 
    if (b[i]) 
     continue; 

    int ptr = i; 
    int next; 
    char nextVal = a[i]; 

    do { 
     next = ptr/3 + N*(ptr%3); 
     char prevVal = nextVal; 
     nextVal = a[next]; 
     a[next] = prevVal; 
     ptr = next; 
     b[ptr] = true; 
    } 
    while (ptr != i); 
    } 
} 

int main() 
{ 
    std::vector<char> a(3*N); 

    for (int i = 0; i != 3*N; ++i) 
    a[i] = i; 

    transpose(a); 

    for (int i = 0; i != 3*N; ++i) 
    std::cout << (int)a[i] << std::endl; 

    return 0; 
} 

私の当初の目的は、サイズ幅のビット・ベクトル高さ、幅のオーバーヘッドを与える使用することです高さ/ 8。しかし、常に空間のスピードを犠牲にすることは可能です。ビットベクトルは、WIDTHまたはHEIGHTまたは任意の望ましい値、さらには0であってもよい。トリックは、すべての値が転置される前のセルへのポインタを維持することである。ビットベクトルは、このポインタから始まるセル用です。すべて1である場合、次の位置に移動され、実際のデータ移動を除いてすべてのアルゴリズムステップが実行されます。そして、ビットベクトルは転置を続ける準備ができている。この変種は、O（N）の代わりにO（N^2）です。

EDIT2：、ちょうどインデックスを計算PREFETCHを呼び出して、キュー（リングバッファ）にインデックスをつけ、その後、キューからインデックスを取得し、データを移動：

PREFITCHの最適化を実現することは困難ではありません。

EDIT3：

（1）サイズ、O（N *ログ（N））時間Oである他のアルゴリズムのアイデア、キャッシュ・フレンドリーであり、 "周期" アルゴリズムよりも高速であってもよいです（画像のため<の1Gbのサイズ）：

チャーのいくつかの3×3マトリクスに

• スプリットN * 3マトリクス及び
• スプリットチャーの3×3のマトリックスに結果それらを転置[3]、それらを転置
• マトリックスサイズ配列のサイズよりも小さい
• 今では、3 * 2 * log3（N）個の配列があります。それらに参加してください。
• 最初に等しいサイズの結合片。長さ4の非常に単純な「サイクル」を使用することができます。
• は逆と等しくないサイズの作品に参加しましょう（逆の（a）、（b）は逆）あなたが唯一の飛行機が必要な場合

Answer 3

、これはかなり簡単に思えます。 3つすべてが必要な場合は、おそらくより洗練されたアルゴリズムでより良い運があります。

void PlanarizeR(char * imageData, int width, int height) 
{ 
    char *in = imageData; 
    int pixelCount = width * height; 
    for (int i = 0; i < pixelCount; ++i, in+=3) 
     std::swap(*in, imageData[i]) 
} 

ループをハイからローに逆にしてプロセスを逆にするのは難しくありません。