3

問題：

グーグルの静的マップAPIからダウンロードした画像があります。この画像を使用して、基本的にユーザーがクリックする「魔法の杖」タイプの機能を作成します。興味のある方のために、私はグラフカットアルゴリズムを使用して、ユーザーがクリックした形状を見つけています。次に、輪郭トレースを使用して、この形状の境界を表すすべてのポイント（borderPoints）を見つけます。

私の目標：

線をまっすぐにし（可能な場合）、borderPointsの量を最小限に抑えます（可能な限り）。私の現在のユースケースは家の屋根なので、ほとんどの場合、コーナーを見つけて、その間のすべての変化するポイントではなく、それらをborderPointsとして使用できることを望んでいます。しかし、でこぼこのピクセルラインのために、それらのコーナーを見つける方法を理解するのに苦労しています。

解決策の私の試み：

簡単な方法の1つは、前のポイント、現在のポイント、および後のポイントをチェックするポイントをループすることです。前のポイントと後のポイントのxまたはyが同じである場合、現在のポイントを削除できます。これにより、ポイント数が少し減りますが、私が望むほどではありません。

また、前後のポイントを見て、特定の勾配範囲内にない場合に現在のポイントを削除できるかどうかを確認しましたが、画像がぼやけていて、角は少し丸みを帯びていました。

私の質問：

この種のことを行うためのアルゴリズムはありますか？もしそうなら、それは（彼らは）何と呼ばれていますか？そうでない場合、この問題にプログラム的にアプローチする方法について何か考えはありますか？

4

2 に答える 2

3

これは、Ramer–Douglas–Peuckerアルゴリズムに似ています。すべてのポイントがグリッド上にあるという事実を利用することで、より良い結果が得られる可能性があります。

于 2012-10-09T17:16:40.303 に答える
1

次数1の多項式近似を探しているように私には思えます。

あなたの質問への素早い答えについては、これを読むことをお勧めします：http: //en.wikipedia.org/wiki/Simple_regression。数値例のセクションでは、直線の方程式を具体的に計算する方法を示します。

多項式近似を使用すると、関数、曲線、点のグループにアプローチできますが、an.x ^ n + ... + a1.x ^ 1+a0の形式の多項式関数を使用して呼び出す必要があります。

あなたの場合、線が必要なので、関数a1.x + a0が必要です。ここで、a1とa0が計算され、ポイントのセットとの誤差が最小限に抑えられます。

エラー（ノルムと呼ばれる）を計算して最小化するには、さまざまな方法があります。たとえば、任意のポイントまでの距離を最小化する（最大値を最小化する）線を見つけること、またはポイントのセット全体までの距離を最小化する（絶対差の合計を最小化する）、または差の二乗和など）

アルゴリズムに関しては、チェビシェフ近似とRemezアルゴリズムを具体的に調べたいと思うかもしれません。これらはすべて、任意の次数の多項式を使用した関数の近似を解きますが、あなたの場合は次数1のみを気にします。

于 2012-10-09T16:26:28.533 に答える