算法使直線出顛簸像素

Question

的問題：

我有，我從谷歌的靜態地圖API下載的圖像。我使用這個圖像來基本創建一個用戶點擊的「魔術棒」類型的功能。對於那些感興趣的人，我正在使用圖形切割算法來查找用戶點擊的形狀。然後使用輪廓跟蹤查找代表此形狀邊界的所有點（邊界點）。

我的目標：

理順線（如果可能的話），並儘量減少borderPoints的量（儘可能地）。我目前的用例是房屋屋頂，所以在大多數情況下，我希望我可以找到角落，只是將它們用作邊界點而不是所有的變化點。但由於顛簸的像素線，我無法找出如何找到這些角落。

我在一個解決方案嘗試：

一個簡單的技術是循環在檢查點前的點，當前點和後點。如果前面的點和後面的點具有相同的x或相同的y，則可以刪除當前點。這會稍微減少點數，但不如我想要的那麼多。

我也試過看前後點，看看當前點是否可以刪除，如果它不在一定的斜率範圍內，但沒有成功，因爲偶爾一個關鍵角點被刪除，因爲圖像是善良的的模糊和角落有點圓潤點。

我的問題：

有沒有做這種類型的事情任何算法？如果是這樣，他們叫什麼？如果沒有，關於如何主動解決這個問題的想法？

Answer 1

這聽起來類似於Ramer–Douglas–Peucker algorithm。通過利用所有點位於網格上的事實，您可能會做得更好。

Answer 2

我看來，像你正在尋找度1

對於一個快速的回答你的問題的多項式逼近中，你可能需要閱讀此：http://en.wikipedia.org/wiki/Simple_regression。數值示例部分具體顯示瞭如何計算線的公式。

多項式逼近允許您逼近一個函數，曲線，點組，但是您想用一個多項式函數來調用它，形式爲an.x^n + ... + a1.x^1 + a0

對於你的情況，你需要一條線，所以你需要一個函數a1.x + a0，其中a1和a0將被計算爲使用你所設置的點來最小化錯誤。

有多種計算錯誤的方法（稱爲規範）並將其最小化。例如，您可能會感興趣的是找到最小化與您擁有的任何點的距離（最小化最大值）的線，或者最小化與整組點的距離（最小化絕對差的總和），或者差異平方和等）

就算法而言，您可能需要特別考慮Chebyshev逼近和Remez算法。所有這些解決一個函數的近似值的任意程度的多項式，但在你的情況下，你只會關心1級。