0

我正在尝试解决以下问题：

给定一个输入，比如说，

0000000000000000
0011111111110000
0011111111110000
0011111111110000
0000000000000000
0000000111111110
0000000111111110
0000000000000000

我需要找到该字段中所有矩形的宽度和高度。输入实际上是一次单列（就像扫描仪从左到右移动一样）并且在程序的持续时间内是连续的（也就是说，扫描列不移动，但矩形在它上面移动）。

在这个例子中，我可以“等待一个矩形开始”（即观察零变为 1）然后观察它结束（一个回到零）并以“网格单位”测量该块。这对于上面概述的简单情况可以正常工作，但是如果矩形倾斜一个角度就会失败，例如：

0000000000000000
0000011000000000
0000111100000000
0001111111000000
0000111111100000
0000011111110000
0000000111100000
0000000011000000

我最初认为以下问题将适用：

动态规划 - 最大方块

但现在我不太确定。

我对回归或回归测试几乎没有经验，但我认为我可以将其表示为 8 个变量的输入.....

老实说，我根本不知道我会怎么做。这部分代码提取的大小需要与已知大小的矩形相匹配（即，来自数据库）。

我最初认为我可以将已知数据作为训练练习提供并存储阳性测试结果，但我真的不知道从哪里开始。

感谢您提供的任何建议。

4

3 回答 3

2

在扫描时收集过渡点（从 1 到 0，反之亦然），然后直接从那里或从每个对象的凸包计算长度和宽度。

如果矩形可以重叠，那么您将遇到更大的问题。

于 2010-07-30T15:15:31.667 回答
1

我会采取以下步骤：

  1. 将所有列放在一个矩阵中（这是正确过滤所必需的）
  2. 现在应用一个过滤器（需要谷歌一下）来锐化边缘和角落
  3. 创建一些结构来保存后续步骤的数据（这可以有许多不同的解决方案，选择您最喜欢的和/或最佳的）
  4. 垂直扫描（逐列）并为在一列中找到的每个后续“一”段（段表示您已经找到它的开始结束y坐标），请执行以下操作：
    1. 检查此段是否与上一列中的某个段重叠
    2. 如果没有，请考虑这是一个新的矩形。创建一个矩形对象并将它的句柄分配给段。对于新的矩形，update it's metrics（这个操作只需要线段的坐标 - x, ymin, ymax, 将在后面讨论）
    3. 如果是，假设这是同一个矩形，获取矩形的句柄，将此句柄分配给当前段，然后通过它的句柄获取矩形，然后update it's metrics

这很漂亮。在此之后，您将拥有一个矩形对象池，每个对象都有四个角坐标。做一些原始数学来近似矩形的宽度和高度。
那么魔法在哪里呢？好吧，这一切都发生在update rect metrics例行公事中。

对于每个矩形，我们有 13 个指标：

  • 最小 X => ymin1, ymax1
  • 最大 X => ymin2, ymax2
  • 最小 Y => xmin1, xmax1
  • 最大 Y => xmin2, xmax2
  • 平均垂直段长度

首先，我们必须确定这个矩形是否在我们的扫描网格中正确对齐。为此，我们比较值average vertical segment length和max Y - min Y。如果它们相同（我会选择 97% 左右的阈值，然后对其进行调整以获得最佳结果），那么我们假设矩形的坐标如下：

  1. （最小 X，最大 Y）
  2. （最小 X，最小 Y）
  3. （最大 X，最大 Y）
  4. （最大 X，最小 Y）。

在其他情况下，矩形被旋转，在这种情况下，我们将其坐标如下：

  1. (最小 X, (ymin1+ymax1)/2)
  2. ((xmin1+xmax1)/2, 最小 Y)
  3. (最大 X, (ymin2+ymax2)/2)
  4. ((xmin2+xmax2)/2, 最大 Y)
于 2010-07-30T17:01:57.137 回答
0

我向朋友提出了这个问题，他建议：

  1. 第一次看到 1 时，将其存储为新形状。洪水将其填充到右侧，并将这些点添加到相同的形状。
  2. 现在任何不在形状中的输入像素都是新形状。做同样的洪水填充。
  3. 在下一个输入列上，再次从原始形状点泛滥。将新像素添加到相应的形状
  4. 如果任何洪水填充没有为两个连续的列添加任何新像素，则您有一个完整的形状。继续前进，并尝试确定它的尺寸

然后，我们就可以获取我们隔离的形状的尺寸（如示例 2 中所示）。

为此，我们想到了：

  1. 如果形状中最左边的像素数低于每列的平均像素数，则可能旋转了该点。因此，通过获取最外层的像素来找到角点。使用它们之间的距离公式。最大 = 斜边，其他 = 宽度或高度。
  2. 否则，这个部分可能是完全对齐的，所以角落可能只是最左上角的像素，最右下角的像素，等等

大家怎么看？

于 2010-07-30T15:27:09.397 回答