11

R、G、B の 3 つの列に数千のデータ ポイントが格納された MySQL テーブルがあります。ユークリッド距離を使用して、特定のポイント (a、b、c) に最も近いデータ ポイントを見つけるにはどうすればよいですか?

色の RGB 値をテーブルに個別に保存しているため、値は各列で 0 ～ 255 に制限されています。私がやろうとしているのは、ユークリッド距離が最小の色を見つけることによって、最も近い色の一致を見つけることです。

距離を計算するためにテーブル内のすべてのポイントを実行することはもちろんできますが、スケーリングするには効率的ではありません。何か案は？

4

5 に答える 5

3

上記のコメントはすべて真実だと思いますが、私の謙虚な意見では、元の質問に答えていません. （私が間違っている場合は修正してください）。では、ここに私の 50 セントを足してみましょう。

テーブルが「色」と呼ばれ、列がr、g、bと呼ばれ、それらは0から255の範囲の整数であり、値を探している場合、selectステートメントを要求しています。与えられた値に最も近いテーブルは、言うことができます: rr, gg, bb, 次に、私はあえて次のことを試みます:

select min(sqrt((rr-r)*(rr-r)+(gg-g)*(gg-g)+(bb-b)*(bb-b))) from colors;

さて、この回答には多くの注意事項があります。あなたの質問が正しいかどうかわからないので、正しいかどうかを確認するか、私が助けられるように修正してください。

于 2012-06-11T05:06:42.263 に答える
2
  1. 正確な距離ではなく最小距離を探しているので、平方根をスキップできます。二乗ユークリッド距離がここに当てはまると思います。
  2. 値は 0 ～ 255 の範囲に制限されていると述べたので、255 の値を持つインデックス付きルックアップ テーブルを作成できます。

これが私がSQLに関して考えていることです。r0、g0、およびb0はターゲット カラーを表します。テーブルVectorには、上記の #2 で説明した平方値が保持されます。このソリューションはすべてのレコードを参照しますが、最初の行のみを並べ替えて選択することにより、結果セットを 1 に設定できます。

select 
    c.r, c.g, c.b,
    mR.dist + mG.dist + mB.dist as squared_dist
from 
    colors c,
    vector mR,
    vector mG,
    vector mB
where
    c.r-r0 = mR.point and
    c.g-g0 = mG.point and
    c.b-b0 = mB.point
group by
    c.r, c.g, c.b
于 2012-06-08T06:16:29.563 に答える
2

あなたができる最適化の最初のレベルは、各行の平方根を実行する必要がないように、クエリを制限したい距離を二乗することです。私が推奨する最適化の 2 番目のレベルは、クエリごとに不要な 2 乗の必要性を軽減するための前処理です (これにより、RGB の大きなテーブルの場合、余分な実行時間が発生する可能性があります)。確認するにはベンチマークを行う必要がありますが、a、b、c、および d の値を代入してクエリを実行することで、MySQL からのストレスを軽減できます。

ラテックス

最後の 2 行のパフォーマンスの違いは無視できることに注意してください。どちらが高速かを判断するには、システムでテスト クエリを使用する必要があります。

今読み直して、あなたが距離で注文していることに気づきました。その場合、d を削除して、すべてを片側に移動する必要があります。定数をプラグインして、MySQL 側での余分な処理を防ぐことができます。

于 2012-06-08T05:22:55.443 に答える
0

2つの選択肢があると思います。

あなたが言うように、セット全体を反復し、-1 のような信じられないほど低い数で最初に設定した最大値と比較してチェックする必要があります。これは線形時間で n 回実行されます (1 つのポイントをセット内のすべてのポイントと比較するだけなので、これは線形にスケーリングされます)。

私はまだ別のオプションを考えています...検索されたポイントでセット内のポイントが見つかるまで、入力ポイントから離れて幅優先検索を行うようなものですが、これにはもう少し考えが必要です(私はただし、これが平均してより効率的になるためには、3D 空間にかなり多くの人口が存在する必要があります)。

于 2012-06-08T05:17:23.380 に答える
0

すべてのポイントを実行して距離を計算する場合は、平方根関数を使用しないでください。必要ありません。最小の二乗和で十分です。

これが解決しようとしている問題です。(平面の場合、ax、y、または z 軸でソートされたすべてのポイントを選択します。次に、PHP を使用してそれらを処理します)

MySQL には空間データベースもあり、これを関数として持つ場合があります。私は積極的ではありませんが。

于 2012-06-08T05:24:45.300 に答える