问题标签 [baduk]

我正在寻找一种可以相当有效地支持联合、查找和去联合的数据结构（至少为 O(log n) 或更好），因为标准的不相交集结构不支持去联合。作为背景，我正在使用 MCTS [ http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]编写围棋 AI ，这将用于跟踪石头组，因为它们在回溯过程中连接和断开连接。我认为这可能会更容易，因为去联合不是在集合中的某个任意对象上，而是始终是最新联合的“撤消”。

我已经阅读了以下论文，虽然我可以执行建议的数据结构，但它似乎有点过头了，并且需要一段时间来实现 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article =1773&上下文=cstech

当然，虽然 O(a(n)) 会很棒，但我很确定路径压缩不适用于去联合，而且我会对 O(log n) 感到满意。我的直觉告诉我一个解决方案可能与堆有关，但我无法弄清楚任何事情。

我正在开发一个可以识别GO 板并为其创建SGF 文件的 Android 应用程序。

我制作了一个能够检测板并扭曲透视以使其方形的版本（下面的代码和示例图像）不幸的是，添加石头时它会变得有点困难。（下图）

关于普通围棋板的重要事项：

• 圆形黑白石头
• 黑板上的黑线
• 板材颜色从白色到浅棕色，有时带有木纹
• 石头放在两条线的交点上

如果我错了，请纠正我，但我认为我目前的方法不是一个好方法。有人对我如何将石头和线条与图片的其余部分分开有一个大致的想法吗？

我的代码：

一些图片：

_{（来源：八十二.axc.nl）}

_{（来源：八十二.axc.nl）}

编辑： 05-03-2016

耶！设法正确检测线石头和颜色。前提条件图片必须只是板本身，没有任何其他可见的背景。
我使用 houghLinesP (60lines) 和 houghCircles (17circles)，在我的手机（第 1 代 Moto G）上的持续时间约为 5 秒。
当它必须在不同的角度和闪电条件下工作时，检测板和翘曲是一个相当大的挑战......仍在努力

仍然欢迎提出不同方法的建议！！

_{（来源：八十二.axc.nl）}

编辑： 2016 年 3 月 15 日

我找到了一个很好的方法来让线与交叉类型的形态变换相交，当图片直接在板上方拍摄时效果惊人，不幸的是不是在一个角度（见下文） _{（来源：八十二.axc.nl）}

在我的最后一次更新中，我展示了线和石头检测以及从正上方拍摄的照片，从那时起我一直致力于检测电路板并以一种我的线和石头检测变得有用的方式扭曲它。

哈里斯角检测
我努力获得正确的参数设置，但我仍然不确定它们是否是最佳的，在使用哈里斯角之前找不到太多关于如何优化图像的信息。现在它检测到许多角落都是有用的。虽然感觉它可以工作。（上面有图片的例子）

当直接从上方拍摄图片，从某个角度使用或与旋转板一起使用时，交叉型形态变换
效果很好（示例中的图片中线）

如果外板线上没有石头并且光线条件不苛刻，则轮廓和轮廓线
效果很好。轮廓通常只是电路板的一部分（示例中带有图片的下一行）

提供正确的图片所有三种方法都有效，但不足以可靠。欢迎任何关于参数、图像预处理、不同方法或任何可能改进检测的想法=）

图片链接

编辑： 2016 年 3 月 31 日

检测线和石头几乎解决了，所以我将关闭这个问题。创建了一个新的的精确检测和变形的方法。

任何对我的进展感兴趣的人：这是我的 GOSU Snap Alpha 频道，现在不要期待太多！

编辑： 2016 年 16 月 10 日

更新：我看到有些人仍在关注这个问题。我测试了更多东西并开始使用 Tensorflow，我的神经网络看起来很有前途，你可以在这里看看。 还有很多工作要做，我当前的图像数据集很糟糕，现在我正在努力获取一个大数据集。

该应用程序最好使用带有粗线条和良好闪电的方板。

我正在开发一个可以识别GO 板并为其创建SGF 文件的 Android 应用程序。

我需要检测整个木板以使其变形并能够找到正确的线条和石头，如下所示。

_{（来源：八十二.axc.nl）}

现在我使用 Opencv RGB Mat 并执行以下操作：

• 分离通道

• 精明的独立频道

  /li>

• 组合（按位或）所有通道。

  /li>
• 找到电路板轮廓

我仍然无法始终如一地检测到棋盘，因为有些线条会消失，如下图所示，棋盘上的黑线和石头清晰可见，但在某些地方缺少棋盘边缘。

_{（来源：八十二.axc.nl）}

我该如何改进这种检测？或者我应该实施多种检测方法并在其中一种失败时在它们之间切换..

*重要的要记住*

• 围棋板颜色不同
• 围棋板可以是空的或完全装满石头，
  这意味着我不能依赖检测板上的外部黑线
• 背景并不总是纯白色

这是我想检测的一小部分带有围棋板的图片

* 更新 * 23-05-2016

我有点用opencv来解决这个问题的灵感用完了，所以非常感谢新的灵感！！！与此同时，我开始使用机器学习，第一个结果很好，我会及时通知你，但仍然对创建 opencv 实现寄予厚望。

我正在将 python 脚本转换为 cython 并对其进行优化以提高速度。现在我有 2 个版本，在我的台式机上，V2 的速度是 V1 的两倍，不幸的是，在我的笔记本电脑上，V1 的速度是 V2 的两倍，我无法找出为什么会有如此大的差异。两台计算机都使用：
- Ubuntu 16.04
- Python 2.7.12
- Cython 0.25.2
- Numpy 1.12.1
桌面：
- Intel® Core™ i3-4370 CPU @ 3.80GHz × 4 64bit。16GB RAM
笔记本电脑：
- Intel® Core™ i5-3210 CPU @ 2.5GHz × 2 64bit。8GB 内存

V1 - 你可以在这里找到完整的代码。所做的唯一更改是重命名go.py、preprocessing.py到go.pyx和preprocessing.pyx使用
import pyximport; pyximport.install() 来编译它们。你可以运行test.py。此版本使用 2d numpy 数组board来存储数据并在函数中go.pyx列出理解来处理数据。在测试期间，仅使用 numpy 数组不调用任何函数get_boardpreprocessing.pyxgo.pyboard

V2 - 你可以在这里找到完整的代码。相当多的东西已经改变了，你可以在下面找到一个列表，其中列出了影响这个测试用例的所有东西。请注意，所有函数和变量声明都必须在go.pxd. 您可以test.py使用以下命令运行：python test.py build_ext --inplace
2d numpy 数组替换为：

并且中的函数get_board_feature替换go.pyx了 numpy 列表理解：

get_board函数 inpreprocessing.pyx被替换为循环遍历数组并为每个位置调用get_board_feature的函数go.pyx

请让我知道我是否应该包含任何其他信息或运行某些测试。

cmp, diff 测试
V2go.c和preprocessing.c文件是一样的。V1 不生成.c文件进行比较

更新比较.so文件
V2go.so文件不同：

文件是相同的，不知道该preprocessing.so怎么想..

我一直在尝试制作一个 GO 棋盘游戏，在 python 中使用 pygame 和一个用于存储棋盘位置和石头颜色（0、1、2）的 numpy 数组。我的问题是我一直在使用 for 循环一次检查每个索引，并通过添加或删除一个 int 来检查相邻的索引：

这种方法似乎可以捕获单个棋子（只要它不在棋盘边缘，因为它也会开始导致越界问题），但是一旦几个相同颜色的棋子靠近每个棋子，就会变得非常复杂其他，可能需要也可能不需要捕获。

必须有更好的方法来搜索这些索引而不会导致超出范围？一个可以让我跟踪所有石头及其相邻空间的方法？