私が最速の画像サイズ変更をしたように。 パート0

こんにちは、私の名前はSashaです。最新のx86プロセッサ向けの最速の画像サイズ変更を書きました。 私が見つけてテストした他のすべてのライブラリが遅いので、私はそう言います。 Uploadcareでオンザフライで画像のサイズ変更を最適化する作業をしていたときに、このタスクを取りました。 コードを開くことにしました。その結果、 Pillow-SIMDプロジェクトが登場しました。 誰でも簡単にPythonアプリケーションで使用できます。

コードは特定のハードウェアで実行され、アーキテクチャを理解することによってのみ最適な最適化を達成できます。 合計で4〜5件の記事をリリースし、鉄のアーキテクチャに関する知識を適用して実際のタスクを最適化する方法を説明します。 私の例では、他のアプリケーションを最適化することをお勧めします。 最初の2つの記事は1週間以内に公開され、残りは公開されます。

タスクについて

「画像のサイズ変更」とは、畳み込みリサンプリングを使用して画像のサイズを変更することを意味します。 リサンプリングは、画像のデコードとエンコードを考慮せずに、8ビットRGBピクセルの配列を介してメモリに実行されますが、最終画像のメモリの割り当てを考慮し、特定の操作に必要な係数の準備を考慮します。

それはとても厳しいです。 トリック（ジープから小さな画像をデコードするなど）やアルゴリズムの組み合わせはなく、特定のアルゴリズムの動作を正直に測定するだけです。 特殊なケースのトリックと最適化は後で適用できますが、これらはこのシリーズの記事で検討する対象ではありません。

...畳み込みリサンプリングを使用します。 なに？

最適化が特に必要なものを明確にするために、畳み込みリサンプリングとは何かを説明します。 畳み込み（正確に言えば、 離散値の畳み込みは 、画像のピクセルが離散的であるため）は非常に簡単な数学的操作です。 一連の値No. 1（係数）と一連の値No. 2（データ、この場合はピクセルチャネルの強度）があります。 これらの2つの行の畳み込みの結果は、ペアのすべてのメンバーの積の合計になります。 とてもシンプル-ピースの合計。 マタンは彼が始める前に終わった。

この操作がサイズ変更にどのように関連付けられるかを正確に理解する必要があります。 一連の値No. 2は、元の画像の一連のピクセルです。 多くの値1は、フィルターから得られた係数です。 フィルターは、値をどの程度正確に縮小するかを決定する関数です。 Photoshopまたは別のグラフィックエディター（バイリニア、バイキュービック、場合によってはランチョス）のサイズ変更ウィンドウにフィルターのあるドロップダウンメニューに気付いたかもしれません。 これがこのフィルターです。 ただし、畳み込みの結果の値は、最終画像の1ピクセルの1チャネルの強度です。 つまり M×Nピクセルの画像を取得するには、M×N×Cの畳み込み演算を行う必要があります。Cはカラーチャンネルの数です。 はい、1回の操作でピクセル全体をカウントすることはできません。異なるチャネルの値は独立しており、個別に考慮する必要があります。

フィルターの機能は無限ではなく、その値は中央部分でのみゼロではありません。バイリニアフィルターの場合、これは-1〜1の値の範囲です。 –2から2のバイキュービックの場合–3から3のランチョスの場合（ただし、他の種類のランチョスもあります）。

これらの数値はフィルターウィンドウと呼ばれます。 フィルタはこの範囲でのみ適用され、外側ではゼロに等しくなります。 したがって、畳み込みに必要なソースピクセルの数は、フィルターウィンドウのサイズに縮小係数（または増加が発生した場合は1）を掛けた半径で取得されます。 これは例によって最もよく説明されると思います。 バイキュービックフィルタを使用して、2560ピクセルの幅の画像を2048の幅に縮小する必要があります。 最終画像の33番目のピクセルの値を検索するとします。 バイキュービックフィルターのウィンドウサイズは2で、縮小係数は2560/2048 = 1.25であるため、元の画像のピクセルの行をfloor((33 - 2) × 1,25)



33-2 floor((33 - 2) × 1,25)



からceil((33 + 2) × 1,25)



まで取得する必要がありますceil((33 + 2) × 1,25)



。 つまり 38番目から44番目のピクセルまで。 同じピクセルについて、係数値が計算されます。

この瞬間まで、私は画像が実際に二次元構造であるという事実を見渡しながら、いくつかの係数といくつかのピクセルについて話しました。 そして、論理的には、線ではなく元の画像の一部を折りたたむ必要があるようです。 ただし、畳み込みの特性の1つは、操作を垂直方向と水平方向に別々に実行して2つのパスを作成できることです。 大まかに言うと、これによりO（n²）からO（2n）への1つの畳み込みの複雑さが軽減されます（実際にはそれよりも少ないですが、依然として重要です）。

なぜすべて同じ畳み込み

一般に、「イメージのサイズ変更」という語句には、実行する必要がある情報に関する最小限の情報が含まれています。 彼女は、描かれたオブジェクトのジオメトリを維持しながら、オリジナルを使用して有限サイズの画像を取得する必要があると言います。 ただし、元の画像はさまざまな方法で使用できます。 たとえば、最終ピクセルごとに、元のピクセルから1つのピクセルをマップして、変更せずに使用できます。 これは最近傍法と呼ばれます。 絵は荒く、破れ、不快です：

これは、元のピクセルのごく一部が最終画像で使用されたためです（上記の例では、1％未満）。 最終画像に入らないピクセルの情報は失われました。

畳み込みによるリサンプリングは次のようになります。

畳み込みのリサンプリングでは、最終画像に対する各ソースピクセルの寄与が正しく考慮されます。 それは普遍的だからです 広範囲のスケーリング係数に対して同等に良好で予測可能な結果を​​提供しますが、ローカルレベルでのジオメトリの歪みは含まれません（一部のフィルタは依然として与えるため、そのような歪みを与えないフィルタが使用されるという注意事項があります）。 そして一般的に、1つのことを除いて、すべての側面からそれはすべて非常に正確で優れています。パフォーマンスです。

枕

Pillowは、Alex ClarkとEric Soroosが率いるコミュニティによって開発されたPythonイメージライブラリです。 Uploadcareは、私がチームに加わる前からPillowを使用していました。 それから私には奇妙に思えた-画像を扱うことは主要なタスクの一つであり、なぜそれのために言語に結び付けられたライブラリーを取る必要があったのか。 何百万人もの開発者が使用する多くの機能を備えた同じImageMagickを使用する方がよいのではないでしょうか。 数年後、私にとっても枕にとっても成功したと言えます。 結局のところ、最初の時点で両方のライブラリのパフォーマンスはほぼ同じでしたが、私がピローのためにしたImageMagickのために何かをする力があるかどうかは非常に疑わしいです。

Pillowは、非常に古いPILライブラリのフォークです。 歴史的に、PILではサイズ変更に畳み込みは使用されませんでした。 PILでの最初の畳み込みサイズ変更の実装はバージョン1.1.3で登場し、ANTIALIASフィルターを使用して利用できました。ANTIALIASフィルターの名前は、他のフィルターが低品質のアルゴリズムを使用するという事実を強調しました。 ネットワーク上では、PIL（および枕として、受信者として）のサイズを変更するときにANTIALIASフィルターのみを使用する関連する推奨事項がなくなっていることがよくあります。

残念ながら、ANTIALIASのパフォーマンスはかなり低かった。 ソースコードを調べて何ができるかを確認しましたが、ANTIALIASのサイズ変更の実装（つまり、畳み込み）を残りのフィルターで使用できることがわかりました。 また、ANTIALIAS定数自体は、大きなウィンドウ（±3）を持つLanczosフィルターに対応するため、非常に低速です。 私がしたかった最初の最適化は、バイリニアフィルターとバイキュービックフィルターの畳み込みを有効にすることでした。 そのため、アプリケーションで安価なバイキュービックフィルターを使用して（±2のウィンドウを使用）、品質をあまり低下させないようにすることができます。

さらに、サイズ変更自体のコードを見ることに興味がありました。 このモジュールで簡単に見つけました。 そして、私は主にPythonで書いていますが、パフォーマンスの面でいくつかの疑わしい場所にすぐに気付きました。 数回最適化した後、2.5倍になりました（これについては次の記事で説明します ）。 その後、SIMDを試し、すべての計算を整数に変換し、サイクルとグループ計算を積極的に展開し始めました。 このタスクは非常に興味深いものでした。生産性を向上させる方法について、私の頭の中には常にいくつかのアイデアがありました。 私はウサギの穴にどんどん深く入り込み、別の仮説を定期的にテストしました。

徐々に、コードは大きくなり、高速になりました。 仕事の一部は枕に返されました。 しかし、SIMDコードは特定のアーキテクチャ向けに作成されたため移植が困難でした。Pillowはクロスプラットフォームライブラリです。 したがって、 Pillow-SIMDの非クロスフォークを作成することが決定されました。 Pillow-SIMDバージョンは、元のPillowのバージョンと完全に一貫しており、一部の操作に速度を追加します。

AVX2を搭載したPillow-SIMDの最新バージョンでは、リサイズは元のPILよりも15〜30倍高速です。 冒頭で述べたように、これは私がテストすることに成功した高品質のサイズ変更の最速の実装です。 さまざまなライブラリのベンチマークの結果が収集されているページを見ることができます 。

PillowとPillow-SIMDで私が嬉しいのは、これらが初心者の開発者でも実際に使用できる本当のライブラリだということです。 これはStack Overflowで公開されているコードの一部ではなく、どこに貼り付けるかが不明確です。 そして、各操作をコンストラクターとしてアセンブルする必要がある「プリミティブブロック」ではありません。 さらに、30分コンパイルする複雑なインターフェイスを備えた複雑なC ++ライブラリもありません。 これは、1行のインストール行、1行のライブラリインポート行、1行のイメージ読み込み行であり、「ちょっと、ママ、見て、アプリケーションで最も速いサイズ変更を使用します」です。

パフォーマンス測定

記事では、バイリニア、バイキュービック、ランチョスフィルターを使用して、2560×1600ピクセルの解像度の元の画像が320x200、2048x1280、5478x3424の解像度にサイズ変更されたテーブル形式でパフォーマンス測定値をアップロードします（つまり、合計9つの操作）。 元の画像は、第3レベルのプロセッサのキャッシュに完全に収まらないほど大きく取られます。 同時に、画像の実際のコンテンツはパフォーマンスの点では重要ではありません。少なくとも白猫、黒猫、猫の写真のサイズを変更できます。 以下は、最適化前のPillowバージョン2.6ライブラリの結果の例です。

 Scale 2560×1600 RGB image to 320x200 bil 0.08927 s 45.88 Mpx/s to 320x200 bic 0.13073 s 31.33 Mpx/s to 320x200 lzs 0.16436 s 24.92 Mpx/s to 2048x1280 bil 0.40833 s 10.03 Mpx/s to 2048x1280 bic 0.45507 s 9.00 Mpx/s to 2048x1280 lzs 0.52855 s 7.75 Mpx/s to 5478x3424 bil 1.49024 s 2.75 Mpx/s to 5478x3424 bic 1.84503 s 2.22 Mpx/s to 5478x3424 lzs 2.04901 s 2.00 Mpx/s
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここの2番目の列は秒単位の時間で、3番目の列はこの操作の元の画像の帯域幅です。 つまり、操作に0.2秒かかった場合、スループットは2560×1600 / 0.2 = 20.48メガピクセル/秒になります。

元の画像は、164ミリ秒で320×200の解像度にサイズ変更されます。 まあ、ちょっと悪くない。 最適化する必要はまったくないかもしれませんが、そのままにしておきますか？ 携帯電話からの写真の解像度が平均して12メガピクセルになったことを思い出すと、すべてがそれほどバラ色ではないことがわかります。 iPhoneからの写真は、開梱を考慮せずに0.5秒縮小されます。 他の操作を考慮すると、1分あたり約80枚、1時間あたり約5000枚の画像を処理でき、現在のサービスの負荷は1時間あたり約13万件です。 この負荷を処理するには、26台のAWS c4.largeサーバーを制限で実行する必要があります。 実際には、4台のサーバーのみが関与しており、暑い時間での負荷は約40％です。

そのような効果を惑星の規模に外挿し、画像のサイズを変更するすべてのコードをより効果的なものに置き換えることができれば、その恩恵はthe大です。 数万台のサーバーが節約され、数百キロワットの電力が節約されました。 そして、これは世界の消費の100万分の1です。 はい、あなたは地球を救うことができます！

次： パート1、一般的な最適化