画像表示効率の最大化: 視覚的な並べ替えがどのように役立つか

TLDR: 2022 年 1 月、HTW ベルリンの Visual Computing Group は、画像の並べ替えを評価する実験を行いました。ソートされた配置の画像は、はるかに迅速に見つかることが示されました。画像の並べ替えを評価するための新しい尺度は、人間が知覚する並べ替えの品質を説明するために通常使用されるものよりも大幅に優れていることが証明されました。さらに、提案された並べ替え方法は、他の方法と比較してはるかに効率的に高品質の画像並べ替えを生成することができました。

2000 人以上の参加者が私たちの実験に参加しました。ここでもう一度感謝したいと思います。掲載記事（https://onlinelibrary.wiley.com/doi/epdf/10.1111/cgf.14718) 実験の結果については、専門家以外には理解しにくい場合があります。したがって、ここでは、実験の動機、実装、および結果をわかりやすい方法で要約しようとします。

一度に多くの画像を認識するのは難しい

人間は複雑な画像をすばやく認識して理解できますが、多くの画像を一度に認識することは困難です。この問題は、写真アーカイブ内の画像や e コマース Web サイトの製品を検索するときに発生します。このような場合、関連する画像の数が非常に多いと、検索が非常に困難になることがよくあります。画面上で一度に認識できる画像は 10 ～ 20 個だけであるため、目的の画像や製品を見つけるには、構造化されていないリストをエンドレスにスクロールする必要があることがよくあります。

人間は、画像を並べて表示すると、画像を認識しやすくなります。上の画像は、256 個の IKEA キッチン用品を示しています。左側はランダムな順序で、右側は類似性で並べ替えられています。特定の画像を検索する場合、並べ替えられていない場合、唯一のオプションは画像を行ごとに「スキャン」することです。並べ替えられた配置では、適切な領域をすばやく特定でき、その領域に焦点を合わせて検索できます。

実験の目的

実施された実験の目的は、画像を適切に並べ替えることで、人々が一度により多くの画像をどの程度認識できるか、および画像を見つけるのにかかる時間をどのように短縮できるかを判断することでした。具体的には、次の質問が取り上げられました。

• 人々はどのタイプの画像分類を快適で役立つと認識していますか?
• 人々が知覚する視覚的な並べ替えの品質を客観的に測定するにはどうすればよいでしょうか?
• 人々の好みに合わせて並べ替えられた配置を効率的に作成するには、どの方法が最適ですか?

上記の質問に対する実験で得られた答えを提示する前に、簡単な例を使用してソートの原理を説明したいと思います。数字 6、5、2、8、および 3 をサイズに従って並べ替える場合、これは、各数字が前の数字よりも大きくなるように数字を配置する必要があることを意味します。

一般的に、1∙2∙3 ∙ … ∙ n = n! (「n 階乗」と読む) n 個のオブジェクトを配置する方法。5 つの数字の場合、既に 120 の可能な配置があり、そのうちの 2 つだけが (昇順または降順で) 並べ替えられます。より大きな数のセットの場合、並べ替え (最適な配置) を決定するための効率的なアルゴリズムがあります。

画像を並べ替えるには？

画像の並べ替えに関しては、適切な並べ替えが実際にどのように見えるか、またはそれをどのように判断するかは明確ではありません。ソート番号と比較すると、主な違いが 2 つあります。まず、画像の外観と内容は個々の番号ではなく、いわゆる特徴ベクトルによって記述されます。これは、各画像が高次元空間のベクトルで表され、通常、類似した画像のベクトルが互いに近くに配置されていることを意味します。次に、並べ替えられた画像は通常 2D グリッド上に配置されます。これは、水平方向と垂直方向の両方に隣接する画像があることを意味します。可能な配置の数は、画像の数に応じて階乗的に増加します。10×10 のグリッドに 100 枚の画像を配置すると、すでに 100 枚の画像があります。= 9.3∙10¹⁵⁷ の可能性 (158 桁の数字) を配置します。これだけの数を考えると、最速のコンピューターですべてのバリアントを試すことは不可能です。すべての配置を比較できたとしても、どれが最もよくソートされているかは明確ではありません。

画像の並べ替えの原理を説明するために、色の 2 次元の並べ替えを例として使用できます。色は赤、緑、青の成分で表されるため、3D ベクトルとして表すことができます。色を 2 次元で並べ替えるには、これらの 3D ベクトルに 2D グリッド上の位置を割り当てる必要があります。次の図は、27 ∙ 27 (= 729) の位置を持つ 2D グリッド上の 9 ∙ 9 ∙ 9 (= 729) RGB 色の並べ替え可能な配置を示しています。

上記の色の例と比較した画像の視覚的な並べ替えの違いは、画像の特徴ベクトルの次元がはるかに高いことだけです。画像の視覚的な外観を記述するには 100 次元未満で十分ですが、画像の内容を記述するには数千の次元が必要になる場合があります。次に、並べ替えプロセスは、類似した画像を互いに近くに配置しようとします。画像を並べ替えるアルゴリズムが実際にどのように機能するかを知りたい場合は、私たちの論文でそれについて読むことができます.

使用画像セット

実験を行う前に、さまざまなサイズのさまざまな画像セットでテストを行いました。画像が多すぎると、並べ替えに関係なく、一部の画像を見つけるのが非常に困難であることが判明しました。これにより、実験の検索タスク中に多くの参加者が終了したことは間違いありません。一方、非常に小さいセットでは、通常、目的の画像が認識されてすぐに見つかるため、画像の並べ替えは検索時間にほとんど影響しませんでした。

実験では、4 つの異なるセットが使用されました。1 つ目は、ランダムに生成された 1024 の RGB カラーで構成され、さまざまな並べ替え方法の知覚品質を決定するためにのみ使用されました。他の 3 つの画像セットについては、目的の画像を見つけるまでの時間も記録されました。これら 3 つのセットは、一方では異なる検索シナリオを表すように選択されましたが、他方ではソートされた配置とランダムな配置の間で検索速度に大きな違いがありました。最初のセットは、概要ボードに表示できる 169 の交通標識で構成されていました。2 番目のセットは、通常 e コマース Web サイトで表示される IKEA キッチン用品の 256 枚の画像です。最後のセットは、インターネットからクロールされた 70 の関連性のない検索語に対する 400 の画像で構成されていました。このセットは、個人的な写真を表すことができます。

実験の実施

実験は 2 つの部分で構成されていました。最初の部分では、参加者の好みは、並べ替えられた画像配置のペアを表示し、2 つの配置のどちらを好むかを決定するように依頼することによって記録されました。好ましい配置は、「より明確な構造を持ち、より良い概要を提供し、検索された画像を見つけやすくする」ものでした. 実験の 2 番目の部分では、参加者は、並べ替えられた配置で検索された画像をできるだけ早く見つけるように求められました。参加者の並べ替えの好みによっても、より高速な検索が可能になるかどうかが調べられました。さらに、ソートの品質を使用して検索時間をどの程度予測できるかを調査しました。

調査された選別方法と品質対策

私たちの実験では、ソートされた配置を生成するためにさまざまな方法を使用しました。自己組織化マップ(SOM)に加えて、自己分類マップ(SSM)、IsoMatch、および離散t-SNE 投影を使用しました。これらの方法を独自のアプローチLinear Assignment Sorting (LAS) およびFast Linear Assignment Sortingと比較しました(FLAS)。各方法に使用されるアルゴリズムの詳細については、前述の出版物を参照してください。可能な限り、メソッドごとに異なるパラメーター設定を使用して複数の配置を生成しました。比較のためにソート品質が低い例を用意するために、ソートが不十分な配置もいくつか生成されました (「低品質」と指定)。画像を見つけるのが難しすぎたため、実験の中断につながる可能性があるため、ランダムな配置は使用されませんでした。

2D 配置を評価するための尺度はありますが、それらが人間の知覚品質をどの程度反映しているかを示す研究はありません。これらの品質測定は、高次元の特徴ベクトルの距離を、2D グリッド上の画像の結果の距離と比較します。通常、相互相関または正規化されたエネルギー関数が使用されますが、どちらも同様に動作するため、後者のみを比較しました。我々は、2D配置を評価するための「 Distance Preservation Quality」（DPQ）と呼ばれる新しい尺度を提案しました。

知覚される選別品質

次の図は、実験の最初の部分のスクリーンショットを示しています。参加者全員に 16 組の配置を見せ、左または右の配置のどちらを好むか、または両方を同等と見なすかを決定するよう求めました。

無意味な評価の潜在的な影響を排除するために、各実験では、非常に異なる品質の並べ替えのペアが提示されました。参加者がこのペアで有意に悪い並べ替えを好んだ場合、すべての並べ替えに対する評価は破棄されました。合計で、カラー セットの 32 の並べ替えと、3 つの画像セットのそれぞれの 23 の並べ替えが調べられました。ドイツのサッカー ブンデスリーガでは、1 シーズンに 18 チームと 18∙17 = 306 試合があり、これは 153 の異なる対戦に対応します。この実験では、カラー セットに 496 の可能なペアと、それぞれに 253 の可能なペアがありました。 3 つの画像セットの。

サッカーと同様のアプローチを使用して、試合が勝利、敗北、または引き分けで終了するすべての比較を評価しました。2 つの並べ替えの比較では、好ましい並べ替えが 1 ポイントを獲得しました。両方の分類が同じと評価された場合、両方とも 0.5 ポイントを受け取りました。シーズンごとに 2 つのチーム間で 2 つのゲームが行われるフットボールとは対照的に、各分類ペアは異なる参加者によって少なくとも 35 回評価されました。これらの評価から、ペアリングの各ソートの平均スコアが決定されました。合計が 1 になるこれら 2 つのスコアは、一方の並べ替えが他方よりも優れていると評価された比率を表します。すべての並べ替えの全体的な比較のために、すべてのペア比較から受け取ったスコアが合計されました。

選別品質を評価する品質尺度は、ユーザーの品質評価に密接に対応する必要があります。次の図は、調査した 2 つの品質測定値と比較した、並べ替えの平均ユーザー評価 (ユーザー スコア) の相関関係を示しています。ここで、E'1 は一般的に使われている「正規化エネルギー関数」、DPQ は私たちが提案する「Distance Preservation Quality」の略です。シンボルの色は、さまざまな並べ替え方法を表しています。

2 つの図は、新しい DPQ 測定値がユーザー評価とより高い相関関係を持っていることを示しています。つまり、人間が知覚する並べ替えの品質を予測するのにより適していることを意味します。

検索回数

実験の 2 番目の部分では、ユーザーはさまざまな並べ替えられた配置を見せられ、それぞれに 4 つのランダムな画像が見つかりました。画像が見つかると、すぐに次の画像が表示されました。使用したソートは、実験の最初の部分と同じです。

もちろん、画像を見つけることの難しさは、検索する画像によって大きく異なります。さらに、参加者は検索能力が異なります。ほんの数回の試行で、これら 2 つの側面が結果を大きく歪める可能性があります。ただし、合計 28,000 以上のこれらの検索タスクが実行されました。これは、並べ替えごとに、4 つの画像ごとに 400 回を超える検索が実行されたことを意味します。この高い数は、検索タスクのさまざまな難易度と参加者の不平等な能力の両方を補いました。

次の図は、一連の交通標識とインターネット画像 (Web 画像) の 23 の異なる並べ替えの検索時間の分布を示しています。さまざまな並べ替えの検索時間の中央値は、色付きのマーカーとして表示されます。繰り返しますが、これは、正規化されたエネルギー関数と比較して、検索時間と DPQ 測定値との強い (負の) 相関を示しています。

高速検索を可能にする並べ替えと評価の高い並べ替えを比較すると、強い一致も見られました。ただし、結果として並べ替えの全体的な配置がわずかに悪いと評価されたとしても、迅速な検索のためには、すべての同様の画像が互いに非常に近くに配置されていることがより重要でした. 左側の次の図は、Web 画像セットで最も評価の高い並べ替えを示し、右側は画像が最も速く見つかった並べ替えを示しています。左側ではトランジションがスムーズですが、右側では関連するすべての画像が近くにあるため、ハードなトランジションが発生しています。

選別方法の比較

最後のステップは、さまざまな並べ替え方法のパフォーマンスをよりよく理解することでした。ランタイムはハードウェアに大きく依存するため、指定された時間は参考値としてのみ機能します。Distance Preservation Quality はユーザーの好みと高い相関があるため、必要な計算時間に応じてアルゴリズムの並べ替え品質を比較するために使用されました。

次の図は、メソッド パラメーターを変化させながら、調査したメソッドで達成された並べ替え品質と必要な計算時間を示しています。256 個のキッチン用品の画像のような小規模なデータセットの場合、FLAS メソッドは品質と計算時間の間で最適な妥協点を提供します。LAS と t-SNE はわずかに高い品質を実現できますが、10 倍から 100 倍遅くなります。1024 個のランダムな RGB カラーについては、LAS および FLAS メソッドが最高の並べ替え品質を達成しました。

別の調査は、異なるサイズの画像セットで品質と計算時間がどのように動作するかを調べることでした。前の図で⦿でマークされたパラメーター設定は、この目的のために選択されました。SOM、SSM、LAS、および FLAS は、より多くの画像に対してより優れた並べ替えを生成できますが、t-SNE および IsoMatch の並べ替えは悪化しました。

実験結果

全体として、以前に提起された質問に明確に答えることができたので、実験の結果に非常に満足していました. ソートされた配置では、人間が画像をはるかに速く見つけることができることが示されています。人々が快適で役立つと感じる画像の並べ替えを分析すると、すべての画像の類似関係をグローバルに維持するよりも、隣接する画像の局所的な類似性が高いことが重要であることがわかりました。さらに、画像並べ替えの新しい品質評価の提案は、人間が知覚する品質を反映するという点で、以前の方法よりも大幅に優れていました。

我々が提案したソーティング手法 LAS と FLAS は高品質のソーティングを生成でき、FLAS も非常に効率的であることが明らかになりました。さらに、当社の方法は、特定の画像の固定配置や長方形以外のレイアウトを使用する機能など、並べ替えに影響を与えるさまざまなオプションを提供します。FLAS メソッド (画像グラフを併用) は非常に高速であるため、何百万もの画像を視覚的に探索することが可能になります。Navigu.net は、このような視覚的な画像探索ツールの一例です。

私たちの研究の詳細については、www.visual-computing.comをご覧ください。