Pixel Sortって何?

この記事は新歓ブログリレー2026 7日目の記事です

はじめに

新入生の皆さん始めまして。24Bの zoi_dayo です。よろしくお願いします。
一応全班に所属しています。最近は動画編集とか作曲とか、あとtraPの †代表† をしています。

さて、皆さんはMVなどで次のようなエフェクトを見たことはありますか?

0:00

適用量? 長さ? を動かすことで、いい感じに非日常的な「破壊」を表現できて面白いです。最近のMVでもちょびちょび使われている印象があります。

さて、こういうエフェクトは「Pixel Sort」と呼ばれています。確かに、適用後の画像をよく見てみると部分ごとにグラデーションっぽくなっている (範囲ごとにSortされている) ようですね。

今回はこのエフェクトについてのお話です。ついでに実装もします。

結局どういうエフェクト?

どうやら、Kim Asendorf という方がこのエフェクトを作り、そこから有名になったようです。

https://x.com/kimasendorf/status/1439606243509907460

そして、その本人のGitHubでProcessingによる実装が提供されています。読ませてもらいましょう。

https://github.com/kimasendorf/ASDFPixelSort/blob/master/ASDFPixelSort.pde

Processingってなんぞや? と思われるかもしれませんが、まあJavaと思えば読めます。

パラメータで挙動を変更できるようになっていますが、挙動は簡単ですね。以下のとおりです。

画像の列ごとに、「色の値」が一定以上の範囲それぞれについて、色をソートする
1の変換後の画像について、行ごとに同じ操作を行う

つまり、画像の一部分について2回のソートを行っているわけですね。完成した画像だけを見ると一方向にだけソートされているように見えますが、2回目のソートの効果が目立っているだけのようです。

ソート対象かどうかを判別するための「色の値」についてですが、これは mode という変数でいろいろ切り替えられるようになっています。例えば、 mode == 0 のときは -12345678 以上のところを選びとることになっています。

なんだこの負の値? となった方もいるかもしれませんが、Processingでは色はARGBの各8bitで表現されています。これを32bit符号付き整数とみなしているわけです。画像が不透明であると仮定すると 0xFF000000 から 0xFFFFFFFF まで、10新法で表記すると -16777216 から -1 までの整数が出現しますね。(先頭のbitが1なので負になることに注意してください)

つまり、例えば mode == 0 のとき、以下の条件を満たすピクセルがソート対象となります。

R > 67
R == 67 && G > 158
R == 67 && G == 158 && b >= 178

めちゃくちゃ雑に言うと「明るいところ」ですね。R/G/Bで扱いにかなり差がありますが、この部分が気になる場合は mode == 2 や mode == 3 を使うと良いでしょう。この場合は brightness が使われます。max(R, G, B) ですね。

やってみよう

というわけで、まあ処理としては簡単なことがわかりました。ので、自分で作ってみましょう。
画像処理ということで、GLSLで書いてみようと思います。

一つ問題があります。GLSLのフラグメントシェーダは「その座標の頂点の色を求める」という動作をします。さて、Pixel Sort後の座標 (x, y) の色は何色になるでしょうか。簡単のため、前半分、つまり列ごとのソートだけを考えます。

ソート対象でないとき、そのままの色
ソート対象のとき、「自分を含むソート対象区間」をすべて取得し、ソートし、そのうち自分に該当する要素

さて、これを愚直に実装することを考えます。画像のサイズを $N \times N$ として、たとえば画像全体が処理範囲であるとき、1ピクセルの色を決定するために $N$ 要素のソートが発生します。計算量は合計で $O (N^{3} lo g N)$ となり、Nが1000程度のオーダーになることを考えるとかなり重いです。

少し考えると、全く同じソートを何回も行っている事がわかります。これを省略できるとよいのですが、残念ながら各ピクセルの処理は並列に行われる可能性があり、ソートしたものをキャッシュして使い回すといったことは難しそうです。

ので、今回はフラグメントシェーダでの (効率的な) 実装は諦め、コンピュートシェーダとして実装することにします。コンピュートシェーダは単にピクセルの色を決定するだけではなく、他の汎用的な計算も行えるようになったシェーダです。GPU上で自由にプログラミングができる感じですね。ただし、今回は入力も出力も普通の画像です。

シェーダの実行環境としては (お手軽・別のエフェクトと組み合わせられるので) TouchDesignerを利用します。

以下のようなシェーダを作成し、

// Pixel Sort
uniform bool uIsColumn = true;
uniform float uThreshold = .5;

layout (local_size_x = 8, local_size_y = 1) in;

const int MAX_HEIGHT = 1280;
const int MAX_WIDTH = 1280;

vec4 data[1280];

float getValue(vec4 pixel) {
    return max(pixel.r, max(pixel.g, pixel.b));
}

const int GAP_MIN = 1;

void main()
{
	if(gl_GlobalInvocationID.y != 0) return;
    int imageWidth = imageSize(sTDComputeOutputs[0]).x;
    int imageHeight = imageSize(sTDComputeOutputs[0]).y;
    if(imageWidth > MAX_WIDTH || imageHeight > MAX_HEIGHT) return;
    
    int size = uIsColumn ? imageHeight : imageWidth;
    int i = int(gl_GlobalInvocationID.x);
    if(i >= imageHeight + imageWidth - size) return;
    for (int j = 0; j < size; j++) {
        data[j] = texture(sTD2DInputs[0], (uIsColumn ? vec2(float(i) + 0.5, float(j) + 0.5) : vec2(float(j) + 0.5, float(i) + 0.5)) / vec2(float(imageWidth), float(imageHeight)));
    }
    
    for (int j = 0; j < size; ) {
        if (getValue(data[j]) >= uThreshold) {
            int start_j = j;
            int end_j = j+1;
            
            while (end_j < size && getValue(data[end_j]) >= uThreshold) {
                end_j++;
            }
            
            int length = end_j - start_j;
            
            int gap = 1;
            while (gap <= length / 3) {
                gap = gap * 3 + 1;
            }
            
            while (gap > GAP_MIN) {
                for (int jj = start_j + gap; jj < end_j; jj++) {
                    vec4 temp = data[jj];
                    float tempProd = getValue(temp);
                    int loc = jj - gap;
                        
                    while (loc >= start_j && getValue(data[loc]) > tempProd) {
                        data[loc + gap] = data[loc];
                        loc -= gap;
                    }
                    data[loc + gap] = temp;
                }
                gap /= 3;
            }
            j = end_j;
        } else {
            j++;
        }
    }
    for (int j = 0; j < size; j++) {
        imageStore(sTDComputeOutputs[0], uIsColumn ? ivec2(i, j) : ivec2(j, i), TDOutputSwizzle(data[j]));
    }
}

TouchDesignerに入れてあげると動きます。座標ごとに2回処理することにしています。

ソートアルゴリズムにはシェルソートを採用しました。今回作ったコードは適用範囲が大きくなったときにかなり動作が重くなってしまうのですが、もしリアルタイムでエフェクトを掛けたい場合、シェルソートは途中で止めてもまあある程度ソートされているので、最悪ここを妥協したら良いのではということです。難しい...

おわり

Pixel Sort、最近よく見かけるけどどういう動作なんだろう、と思って調べてみました。ソートの基準 (RGB→Valueの変換) をいじったらいろいろ遊べそうです。もしかしてこれソートをCPUでやったほうが早かったりしますか?

いかがでしたか? 明日は @sakura の記事が投稿されるらしいです。楽しみ〜

Pixel Sortって何?

はじめに

結局どういうエフェクト?

やってみよう

おわり

この記事をシェア

関連する記事