英语原文共 37 页
目录
介绍
围棋游戏
围棋是一项古老的棋盘游戏，它起源于中国。它最初记载于公元前625年中国河南的文言文中（Bell，1979年）。
传统来说，它是在被称作围棋棋盘的木板上玩黑色和白色的棋子。棋盘上有一个正方形网格，传统上由19x19行组成。在比赛期间，棋子被放置在交叉处。初学者使用较小的棋盘（通常为13x13或者9x9行）。
两位选手轮流在棋盘上放一颗棋子。一旦棋子被放在木板上，它就不能动了。然而，它可以从板上去除（“被捕获”）。游戏的目标是占领比对手玩家更多的区域。由于游戏规则与我们的工作没有直接关系，我们请感兴趣的读者参考文献（例如Iwamoto，1972年）来理解这些规则。这些规则也可以在互联网上找到，比如在Sensei#39;sLibrary或维基百科（Wikipedia）上。
游戏记录
传统的游戏记录（在日语中被称为kifu）是在一个带有网格的特殊表格上手写的。每一次移动的次数都写在它放置的位置上。通常用到两支不同颜色的钢笔——分别代表每个玩家的移动，这使得游戏记录更容易阅读。手写记录中的任何错误都很难纠正。
如今，电脑、平板电脑或智能手机都可以用来记录游戏，这有利于记录，因为错误很容易纠正，并且游戏结果记录可以方便地显示。但它仍然分散了玩家对游戏的注意力。
论文提纲
在本文中，我们考查了在围棋中实现自动光学游戏位置识别的可能性。我们实现了一个系统，只需要一个（网络）相机和一台计算机就能使玩家可以轻松地记录他们的游戏。记录是完全自动的，不会使玩家从游戏中分心。它是可靠的，并且游戏结果记录可以很容易地在任何围棋编辑程序中显示和编辑。
在第一章中，我们介绍了透视几何、颜色理论的基本概念，并介绍了后面使用的算法。在第二章中，我们详细介绍了围棋位置的光学识别问题。在第三章中，我们调查了相关的学术著作和目前可用的围棋记录软件。在第四章中，我们描述了我们的游戏位置识别方法，并在第五章中给出了基于该方法的应用。我们在第六章中评估了我们的应用程序的性能。
1.理论及算法
在本章中，我们解释了一些基本的理论概念和算法，这些基本概念和算法将应用于之后的章节。
1.1透视
如果我们用平行于栅格并在其中心正上方定位的相机拍摄一幅正方形网格，图像将包含一个正方形网格。由于我们不想对我们的程序的用户强加这样的条件，我们必须处理一个透视转换后的正方形网格的图像。传统的围棋棋盘也考虑到了这一点，因此网格实际上是矩形的，使玩家在旁边以某一角度看的时候为正方形。
在对透视变换进行推理时，我们假设三维场景通过一个点（称为焦点）投射到一个二维平面上。
对于场景中的每一组平行线，我们在图像中都有一组在共同点上相交的线。这个点叫做灭点。当直线同样平行于投影平面时，灭点位于无穷远处。这是为了引入投影几何，但就我们的目的而言，标准向量空间中的灭点就足够了。
根据图像中若干灭点，我们区分了一个或两个点透视。具有更多灭点的透视是常见的，但是由于我们只对由两组平行线组成的板网格感兴趣，所以它们与我们无关。
透视变换的重要性质是保留线条。这意味着场景中的一条线被投影到图像中的一条线上，场景中两条线的相交被投影到相应直线的交点上，以此类推。我们可以用它来推导出这样的关系，如果我们在图像中连接板的角，我们就可以在对角线的交点处得到板的中心。这可用于计算网格中的所有交叉点，只需知道图像中网格的角点坐标即可。
有关透视在计算机视觉中应用的更多信息，请参阅（Sonka等人，2014年）。
1.2颜色空间
颜色空间是一种抽象的数学模型，描述了一种将颜色表示为数字向量的方法。存储和操作图像最常用的颜色空间是RGB。这是因为计算机屏幕和数码相机传感器都使用红色、绿色和蓝色通道来显示和记录图像。人眼也含有三种锥细胞，它们对红、绿、蓝三种光有反应。
RGB没有直接的语义解释。对于图像分析，我们可能需要使用不同的颜色空间。这样的颜色空间例子包括HSL和HSV（Joblove和Greenberg，1978年）。
这些空间由色调、饱和度和亮度值组成，它们比RGB值更容易解释。
我们使用亮度从多色图像中获得灰度图像。它来自YUV颜色空间及其变体，主要用于视频编码。亮度定义为Y=0.2126R 0.7152G 0.0722B。这反映了绿光对人类视觉强度的影响最大，蓝光的影响最小。数码相机通常在绿色通道中有较好的分辨力，因此赋予绿色图像分析最大的权重也是有意义的。
1.3 霍夫变换
线条的霍夫变换是由Duda和Hart在1972年提出的，是对霍夫于1962年的先前工作的补充。
我们通过将图像转换至霍夫空间来检测图像中的线条。霍夫空间中的一个点对应于原始图像中的一条线。每一条线都是用它与图像中心的角度和距离来表示的。霍夫变换在灰度图像中有效。因此，图像中的每个点只有唯一值（我们将其称为强度）。霍夫空间中的每个点，特别是对应直线的两个参数，也只有一个值。霍夫变换是一种简单的投票算法。图像中的每个点P通过将其强度加到与P所在的直线对应的霍夫空间中的每个点的强度上来投票。因此，霍夫空间中某一点的强度表示图像中相应直线的累积强度。霍夫空间中的峰值表示图像中不同的线条。
|
算法1 霍夫变换 |
|
function Hough transform(img) function Dist((x, y), theta;) L is the line going through point [x, y] at angle theta; d larr; x · cos(theta;) y · sin(theta;) // L到最初位置的距离 return Round(d) m larr; zeroes for x, y larr; (0, 0), size(img) do if img[x, y] gt; 0 then for alpha; larr; 0, pi; do // 在某些步骤里采用0到pi;的角度 d larr; Dist((x, y), alpha;) m[alpha;, d] larr; m[alpha;, d] img[x, y] return m |
如前所述，霍夫变换是一个连续函数。在实践中，我们理所当然地只从它计算一个离散样本。由于输入图像也是离散的，我们必须合理地定义在直线上的关系。我们通过只考虑直线角度的一个子集（用某个步骤均匀采样）来解决这个问题。当计算点P位于哪条线，我们计算每个角度alpha;的距离d，使得有一条线从图像中心以角度alpha;距离d穿过点P。然后将距离四舍五入到离散霍夫空间中最近的点。我们使用从0到pi;的角度和负数距离，因此所有平行线有相同的角度但是不同的距离。
有关伪代码，请参见算法1。图4.2和图4.3是一个图像及其霍夫变换的例子。
O#39;gorman和clowe于1976年通过使用局部梯度来减少无用投票的数量和计算时间，改进了霍夫变换。Ballard于1981年进一步推广了霍夫变换来检测任意形状。
1.4随机抽样一致性算法
RANSAC（RANdom Sample And Consensus）算法最早由Fischler和Bolles于1981年提出。它是一种利用被大量异常值污染的数据估计模型参数的随机方法。
图1.1：线性模型的RANSAC估计。数据集由所有点组成，红线为最小二乘法估计的模型，蓝线为Theil-Sen估计的模型，绿线为RANSAC估计的模型（一致集为绿点）。
我们将用一个线性模型的例子来说明RANSAC过程。假设我们有一些由带有高斯噪声的线性模型生成的数据（如图1.1中的绿点）。我们想要估计模型的参数。在这种情况下，我们可以使用最小二乘方法（图1.1的绿线）来估计模型参数。
现在我们使用来自相同模型的数据，但这次使用的是异常值（图1.1中的蓝点）。这些离群值是随机分布的，因此我们不能期望它们与模型的偏差相互抵消。如您所见，可能会有很多异常值，但是仍然可以区分这条线。这次，最小二乘（图1.1中的红线）比较偏离。Theil-Sen估计（Sen，1968）较好，但仍不够好（图1.1中的蓝线）。这就是RANSAC的有用之处。
|
算法2RANSAC算法 |
|
procedure RANSAC(data, distance, threshold, max iter) best larr; {} i larr; 0 while |best| lt; threshold and i lt; max iter do consensus larr; random sample(data) c larr; 0 while c lt; |consensus| do c larr; |consensus| model larr; estimate(consensus) consensus larr; filter(model, data, distance) if |best| lt; |consensus| then best larr; consensus i larr; i 1 return best |
在每次随机抽样一致性算法迭代中，我们随机选择足够的数据点来确定模型的参数（二维线性情况下为2个数据点）。然后我们根据这个模型检查所有的数据点。我们创建一个所谓的一致集，它由比d更接近模型的数据点组成（d是一个参数）。我们假设一致集由正确数据组成，因此我们可
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
