擅长:python、mysql、java
<p>我会用分水岭式算法来解决这个问题。我在下面描述了这个方法,但它只处理单个(多段)线,所以您需要将图像分割成多行的图像。在</p>
<p>玩具示例:</p>
<pre><code>0000000
0111110
0111110
0110000
0110000
0000000
</code></pre>
<p>其中<code>0</code>表示黑色,<code>1</code>表示白色。在</p>
<p>现在我的解决方案实现:</p>
^{pr2}$
<p>输出:</p>
<pre><code>[[0 0 0 0 0 0 0]
[0 5 4 4 5 6 0]
[0 5 4 3 4 5 0]
[0 6 5 0 0 0 0]
[0 0 0 0 0 0 0]]
</code></pre>
<p>现在结束由上面数组中最大值的位置表示(在本例中是<code>6</code>)。在</p>
<p><strong>解释</strong>:我正在检查尽可能多的白色像素。对于每一个这样的像素,我是“泛洪”图像-我放置特殊值(<code>127</code>-不同于<code>0</code>,不同于<code>255</code>),然后推广它-在每一步中,所有与特殊值相邻的<code>255</code>本身都成为特殊值。我正在计算删除所有<code>255</code>所需的步骤。因为如果你从末端开始(等速)注水,比在任何其他位置都有水源的情况下要花费更多的时间,那么最大的泛洪次数就是终点。在</p>
<p>我必须承认,我没有深入地测试这一点,所以我不能保证在特殊情况下正确工作,例如在自交线的情况下。我也意识到我的解决方案的粗糙度,特别是在检测邻居和传播特殊值方面,所以请随意改进它。我假设所有的边界像素都是黑色的(没有一条线接触到图像的“框架”)。在</p>