在大型稀疏矩陣中查找所有矩陣的子矩陣

這是圖像處理算法的一部分，其中需要進行更多的優化。我們有一個由0和1組成的大型稀疏矩陣。在這個稀疏矩陣中有一個或多個1的稠密區域。可以說整個矩陣代表一個圖像，0代表非視頻區域，1代表視頻區域。基本上所有附近的1應該被分組在一起以找出更接近的視頻區域。因此，圍繞全部1繪製邊界將會給出圖像中確切的視頻區域。在大型稀疏矩陣中查找所有矩陣的子矩陣

enter image description here

如在0和1的上述矩陣所示。有4個密集區域的1。我們已經嘗試了一種天真的方法，它具有更多的時間複雜性和預期的進一步改進。

我們嘗試的方法是，如果塊中1的數目高於特定閾值，則將3 * 3或2 * 2的塊大小中的所有0轉換。但即使這種方法也不能給我們視頻塊的確切邊界。

所以尋找一個更好的算法，既有時間和空間的複雜性。實際上，這個計算需要實時完成，所以算法的時間複雜度要低得多。如果我們可以在O（n）線性時間內實現，那將是非常好的。

來源

2013-01-19 vicky

你很高興發佈你的家庭作業，但你做了什麼？ – 2013-01-19 14:16:23

這不是一種家庭作業。我所尋找的只是一種方法。我可以做的實現。我試過飛利浦建議的掃描線算法，經過一些編輯後它工作正常。謝謝@philips – vicky

這裏常用的方法是應用掃描線算法。

基本上，它的工作原理如下：查看每一列。如果它由全零組成，則轉到下一列。如果它包含1，則保存最小和最大的垂直位置（它們可能是矩形座標的候選）。隨着您進一步移動掃描線，相應地調整您的候選人。如果您找到了候選人並且到達由全零組成的一行，則您的座標候選人就是該矩形的實際座標。

您可能（或另外）垂直掃描並檢查行而不是列。

根據您的矩陣（或您的任務）的屬性，有很多不同的可能的解決方案。考慮以下矩陣：

1 1 1 
1 1 1 
1 1 1

它包含多少個矩形？ 1？ 9？ 4？

在您的示例中，兩個觸摸矩形也可以視爲一個較大矩形的一部分。

一些建議：更清楚地說明你的問題。

來源

2013-01-19 08:49:43 Philip

在上面的場景中，整個矩陣代表我們的桌面屏幕區域。其中1表示某些動畫或視頻正在呈現的區域，0表示所有其他區域。 1之間的所有0實際上只是動畫或視頻，但由於運動較少而不是暫時的。因此，通過檢測1中的所有0，我們可以確保那些臨時區域爲動畫或視頻。這就是爲什麼我們需要檢測邊界矩形。 – vicky

是菲利普在你顯示的矩陣中會認爲它是1。 – vicky

在大型稀疏矩陣中查找所有矩陣的子矩陣

回答

相關問題