java - 在具有一定容错性的文本正文中定位 ASCII 艺术图像

Question

是否有任何算法可以找到以下 ASCII 艺术图像？

    +
    +
   +++
 +++++++
 ++   ++
++  +  ++
++ +++ ++
++  +  ++
 ++   ++
 +++++++
   +++

在以下正文中？

complete_file_here

              + +    +              ++           +       +++    +     +
 +  ++     +   + ++++    + +       +         +          +  +   +++     +++ +
     +            + +   ++      ++  ++    + ++       +     +      +  +   +
+   ++      +  ++       +          + +       ++        ++  +           +
 ++++++ + +    +   ++  +  +   +   +  ++      +         +                     +
  + +   +      +               +      ++     +  ++            +   +    + +
+++   + ++   +  +            +  +++       + +       ++                     +
  +++++  +      +                            +  + +            +   +  +
 +   +   +              +    +      +            +  +   +      +    +     +
 ++    +              +     +       ++   +          +       +           ++

我必须用黄色突出显示对应于完整形状的 ASCII 艺术图像。见附图：

在此处输入图像描述

我必须搜索包含粗略形状的文件，但不完全，+可能会丢失一些）。形状缺失的公差+应手动设置。

现在，我有两个二维数组数据数组：[100][100] 和 SlimeTorpedo 数组：[13][11]。

如@kjartan（3-4 项目符号）所述，如何进行检测的代码：

int match = 0;
for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
        //Compare DataArr[i][j] with SlimeTorpedoArr[i][j]
        //Look for "checked" position in the picture ("+"), 
        //which corresponds to a checked position in the 
        //slime torpedo array.
        //match++;
    }
}

如何解决这个问题的一般指导是什么？

score 4 · Accepted Answer

假设宽度和高度参数（就字符数而言）对于您的第一个形状是已知的。让他们成为width和height。

将您的输入编码为二维位数组（或 + 符号）。所以你有 int[][] inputBits = new int[height][width];并且你应该正确地填充它。（这是你的任务，伙计。）
然后对较大的形状应用一个简单的搜索（假设它也被编码到另一个二维数组中）。每次将枢轴区域向右移动一次（枢轴区域相当于第一个形状的区域）并检查枢轴区域（二维数组）是否所有元素都等于第一个形状。这是一个蛮力算法=）

score 4 · Accepted Answer

使用匹配分数尝试蛮力：

在你的“史莱姆鱼雷”周围定义一个“正方形”；这是一个 2D 阵列，其宽度和高度比您的鱼雷略宽和略高。
在该二维数组中，根据需要将单元格标记为选中或未选中，以创建所需的图像。
现在循环遍历完整图像中的每个字符（我们称之为“索引”位置），并将每个字符附近的位置与 2D 数组中相应字符的位置进行比较。
在图片中查找“已选中”（或未选中）的位置，该位置对应于 slime 鱼雷阵列中已选中（或未选中）的位置（例如，图片中当前索引位置上方的字符 X 和左侧的 Y，即匹配粘液鱼雷阵列中心点上方的状态 X 和左侧的 Y）。对于每个这样的“匹配”，在图片中的该索引位置添加一个“点”。

现在的诀窍是：为了更有效，只检查粘液鱼雷中的一些位置 - 例如，每 10 个位置甚至更少。粗略地说，这应该将运行时间减少 10 倍。

这意味着您必须为整个图片中的每个字符检查(1/10)* 。the number of characters in the 2D array

现在跟踪全图中得分最高的位置。得分最高的位置应该是最佳匹配。

如果你愿意，你可以多次运行这个，不同程度的细节，例如第一次只检查 1/20 的位置，然后是 1/2，下一次，但这次只关注例如最高的 20 （或 50？100？）第一轮的得分位置。

（或者，您可以对得分高于某个阈值 S 的所有位置进行更详细的扫描）。

希望你能让我们知道无论你决定如何，有趣的问题！:)

针对以下评论进行更新：

也许我的解释有点不清楚。简而言之/伪代码，您需要执行以下操作来查找每个单元格的分数：

foreach(DataArraRow dataRow in dataArray){
    foreach(IndexCell index in dataRow){        

        // initialy, no score for this cell in the data array:
        indexCell.score = 0;

        // Now iterate through all SlimeTorpedo cells, and compare the 
        // symbol in it to the corresponding symbol in te data array:
        foreach(SlimeArrayRow slimeRow in slimeTorpedoArray){
            foreach(SlimeTorpedoCell slimeCell in slimeRow){
                if(IsMatchingSymbol(slimeCell.xPosition, 
                                    slimeCell.yPosition, 
                                    slimeCell.symbol, 
                                    indexCell){
                    indexCell.score += 1;
                }else{
                    indexCell.score -= 1;
                }
            }              
        }

    }
}


Function IsMatchingSymbol(x, y, slimeSymbol, indexCell){
   // Find the cell in the data array corresponding to the 
   // "slimeCell" currently being checked:
   var cellToCheck = getCell(indexCell.xPosition + x, 
                             indexCell.yPosition + y);

   if(cellToCheck.symbol == slimeSymbol){
       return true;
   }else{
       return false;
   }

}

这显然有点混乱，我不确定所有细节，但我希望它展示了一个应该可行的一般想法。当您完成迭代后，再次迭代所有单元格，并选择得分最高的单元格（或者在此过程中建立一个单独的高分列表 - 这可能会更快）。

您将不得不做一些更改，例如用ForEach常规For(int i=0; i < someArrayLength; i = i + levelOfDetail){ ... }或类似的东西替换循环，其中levelOfDetail是一个整数，您可以使用它来调整细节级别（即要检查 SlimeTorpedoArray 中的多少个单元格）。我相信你可以解决它... ;)

score 1 · Accepted Answer

对于那些感兴趣的人，我使用 Java 中的 XOR 映射解决了这个问题：

https://bitbucket.org/bluegod1/blifoscope-java/

它还考虑到可能存在误报或重复，它可以选择指定良好匹配的最小阈值，添加自定义数据图像文件等......

java - 在具有一定容错性的文本正文中定位 ASCII 艺术图像

3 回答 3

Related

Reference