用於查找直線交點的算法

有關於我在某處看到的線路交叉點並試圖解決的問題。用於查找直線交點的算法

有一個64x64的8位像素網格，它有一束1像素寬的不同顏色的垂直和水平線。所有平行線之間至少有一個空格。問題是要找出每組彩色線條所形成的線路交叉點的數量（例如，所有綠色線路交叉點都計入一個總和）。並找出哪一組線路交叉數量最少。此外，顏色的所有垂直線都是相同的大小，並且同一顏色的所有水平線都是相同的大小。

我有一些想法，但他們都似乎相當低效。這將涉及通過網格中的每個像素，如果遇到顏色確定它是垂直線還是水平線，然後沿着線的方向行進，同時檢查相鄰兩側的不同顏色。

我想決定是否首先計算每種顏色的水平和垂直線的長度會加快這個過程。你們對於如何做到這一點有什麼好的想法嗎？

這裏有兩個例子。請注意，平行線總是在它們之間留有空間。

enter image description here

來源

2011-10-02 ballaw

不知道我知道，但在我看來，對於每一種顏色，你想要的水平線乘以垂直線的數目。然後對其進行排序以查看哪種顏色具有最大值？那麼如何通過檢查圖像像素來統計每種顏色的線條數量/類型？ –

我想要的是一條線以任何其他顏色穿過的次數。你爲每一行做這個，然後對每種顏色的所有交叉點進行求和。另外，由於線路可能在下方或者不在下方，因此線路不明確，如果線路在T（或橫向T）交叉點相遇，則不計算該線路。例如，第一張照片中綠色的交叉總數爲7. – ballaw

啊，好的。這是值得在這個問題，謝謝。 –

在你的線網格尋找2種3×3平方：

1).a. 2).a. 
    bab bbb 
    .a. .a.

「」代表背景（總是黑色？），「a」和「b」代表2種不同的顏色（也與背景顏色不同）。如果找到，則將1色線相交點和b色線相交點的計數提高1。

來源

2011-10-03 01:00:36

這聽起來像是一個贏家。但是T交叉點呢？他們不會被忽視嗎？此外，在邊緣，你不能比較整個廣場，因爲你會索引。我會開始研究這個。 – ballaw

@BobBusby：如果您檢查所有9個單元格完全是上述兩種模式中的一種，則您將忽略t型交叉點。是不是你想要的，你提到的含糊不清？如果你願意，你也可以計算t型交叉點，你需要使用這個算法尋找8個更多的模式。 –

Bob Busby在評論中寫道：「由於線條可能在下面或者沒有在線，因此如果線條在T（或橫向T）交叉點相遇，則不計算該交叉點。」如果我們認爲T交叉點不被視爲交叉點，那麼@Alex方法就完成了。然而，所有T都不明確是不正確的。例如，在第二個例子中，兩條水平的亮黃線T的右端結束，並帶有一條紅線。可以毫不含糊地推斷出在紅線下有黃色方塊，因爲頂部的黃線在包含紅線的列中結束。 –

掃描像素網格實際上是非常快速和有效。這是計算機視覺系統做這種事情的標準。許多這些掃描產生一個FIR濾波版本的圖像，強調正在搜索的細節種類。

主要技術術語是「卷積」（見http://en.wikipedia.org/wiki/Convolution）。我認爲它是一種加權移動平均數，儘管權重可能是負數。維基百科上的動畫使用一種相當乏味的脈衝（它可能是一種更有趣的形狀）以及一維信號（如聲音）而不是二維（圖像）信號顯示卷積，但這是一個非常普遍的概念。

很容易想到通過避免提前計算濾波版本可以實現更高效的處理，但通常的效果是因爲您沒有預先計算所有像素，所以最終計算每個像素數次。換句話說，將過濾圖像視爲基於查找表的優化，或者一種dynamic programming。

一些特定的原因，這是快是...

這是非常緩存友好，所以有效地訪問內存。
正是這種事情，矢量指令（MMX，SIMD等）被設計爲支持。
現在，您甚至可以將工作卸載到顯卡上。

另一個優點是你只需要編寫一個圖像濾波卷積函數。特定於應用程序的部分是您如何定義過濾器內核，這只是一個權重值的網格。事實上，你可能不應該自己編寫這個函數 - 各種數字代碼庫可以提供高度優化的版本。

爲了處理不同顏色的線條，我會先爲每種顏色生成一個灰度圖像，然後分別進行過濾和檢查。再次，將此視爲優化 - 試圖避免生成單獨的圖像可能會導致更多的工作，而不是更少的工作。

關於第二個想法，我可能已經理解了這個要求。從黑色和彩色生成黑白圖像，過濾並從中找到相交點可能更有意義。獲得交點後，請返回原始黑白圖像以將它們分類以進行計數。過濾和交叉找到每個像素仍然非常有效。分類不是每個像素都很有效，但只能在幾個點上完成。

你可以做到這一點基於以下FIR濾波器內核卷積...

.*. 
*** 
.*.

點是零（像素無關），或者可能是負值（喜歡黑色）。星號是正值（更喜歡白色）。也就是說，在十字路口尋找三乘三交叉。

然後，您掃描過濾後的結果，查找比某個閾值更亮的灰度像素 - 最適合您圖案的匹配。如果你真的只想要精確的穿越點，你可能只接受完美匹配的顏色，但你可能想爲T型連接等補貼。

來源

2011-10-03 00:38:48 Steve314

感謝您的幫助！我沒有足夠的先進技術去做那些有趣的事情，但是像你這樣的人讓我想變得更好。我見過的唯一卷積是一維的，所以我不知道如何將它應用到矩陣。 – ballaw

是你唯一的輸入64x64網格嗎？如果是這樣，那麼你正在尋找一個64x64的東西，因爲沒有其他方法可以確保你發現所有的線。所以我會假設你在談論運營層面的優化，而不是漸近的。我似乎記得舊的「Graphics Gems」系列有很多這樣的例子，重點是減少指令數量。我在漸近問題更好的自己，但這裏有幾個小點子：

網格單元擁有電網[I，J]是一個綠色的交集屬性如果

(grid[i,j] == green) 
&& 
(grid[i+1,j]==green || grid[i-1,j]==green) 
&& 
(grid[i,j+1]==green || grid[i, j-1]==green)

所以你可以掃描陣列一次，而不必擔心顯式檢測水平線和垂直線...只需使用這種關係進行穿過，並根據您找到的交點進行計算。所以至少你只需要一個簡單的邏輯就可以使用一個64x64的循環。

由於沒有兩條平行線直接相鄰，因此當您傳遞填充的單元格時，您知道可以將內部循環計數器加2。這會爲你節省一點工作。

根據你的體系結構，你可能有一個快速的方法來將整個網格與其自身的偏移副本進行和運算，這將是計算上述相交公式的一種很酷的方式。但是，你仍然需要遍歷整個事物來找到剩餘的填充單元格（它們是交叉點）。

即使你沒有像圖形處理器這樣的東西可以讓你和整個網格，你可以使用這個想法，如果顏色的數量少於你的字大小的一半。例如，如果您有8種顏色和64位計算機，則可以將8個像素填充爲單個無符號整數。所以，現在您可以一次對8個網格單元執行外部循環比較操作。這可以爲你節省很多工作，值得做兩遍，一個用於水平外環，一個用於垂直外環。

來源

2011-10-03 00:42:04 Eric

我想我的解釋很差。我正在尋找一種顏色的線與其他所有顏色的交點。他們也不必從各個方向相交。它可以只是一條線跨過另一條線。不過謝謝你的建議！ – ballaw

這不檢查所有方向的交叉點 - 再次查看OR。爲了適應與非綠線的交點，您可以將其調整爲：左或右不爲空，並且頂部或底部不爲空，並且左側或右側或頂部或底部不是綠色。 – Eric

簡單的方法來找到直路口

def straight_intersection(straight1, straight2): 
    p1x = straight1[0][0] 
    p1y = straight1[0][1] 
    p2x = straight1[1][0] 
    p2y = straight1[1][1] 
    p3x = straight2[0][0] 
    p3y = straight2[0][1] 
    p4x = straight2[1][0] 
    p4y = straight2[1][1] 
    x = p1y * p2x * p3x - p1y * p2x * p4x - p1x * p2y * p4x + p1x * p2y * p3x - p2x * p3x * p4y + p2x * p3y * p4x + p1x * p3x * p4y - p1x * p3y * p4x 
    x = x/(p2x * p3y - p2x * p4y - p1x * p3y + p1x * p4y + p4x * p2y - p4x * p1y - p3x * p2y + p3x * p1y) 
    y = ((p2y - p1y) * x + p1y * p2x - p1x * p2y)/(p2x - p1x) 
    return (x, y)

來源

2014-07-30 22:32:57 JonatasTeixeira

用於查找直線交點的算法

回答

相關問題