摘要：本篇文章为应用于LCD上的定位研究，用于胶合与检测之上。本文采用的是十字标记，经由两十字标记的叠合来分析版子的方向与彼此之间的误差。文中将会介绍Hough Transform，并介绍Fast Hough Transform的方法来改善其运算速度过慢的问题。而Hough Transform将被应用在解决两十字对准会有互相叠合导致部分十字标记影像不见的问题，从而由部分的十字标记影像分析出正确的位置与角度。

1.       绪论

近几年LCD的市场大增，应用于其上的检测与定位系统已就变的相对重要。本篇文章乃是针对其定位系统提出算法，一般而言是应用于检测与胶合之用。应用于检测时，乃是先校正影像的偏转角度，以利后续对LCD的检测，如彩色滤光片缺陷检测[2]。应用于胶合时则是求出两块欲胶合的版子的角度与位置误差再补偿回两块版子的误差[3]，当这影像处理的补偿动作错误发生时，就必须用人工予以补救。
图1为三种常见于LCD定位的标记，(a)为两矩形标记，当两矩形完全重合时代表欲胶合的两块版子完全对准，然而缺点是难以计算角度的偏移。(b)为一环与一小点，应用灰度累积的方式，当两标记的中心点完全重合时代表对准[3]，缺点是当标记互有叠合时容易误判。(c)为十字标记，可以补足上述的缺点，但处理上比较复杂，因此多只用一个来作角度的补偿，少见于作叠合的处理。本文即是针对此种十字标记的叠合提出。

目前常见于图1前两种标记的方式为使用灰度累积的方式来算出标记间的位置偏移，再使用两组标记于板子的对角线的位置，用几何关系来求出角度的偏移[3]，其缺点就是无法用于十字标记上。Mu-Hsing Wu 在其彩色滤光片缺陷检测[2]一文中则是使用Cross correlation 的方式来对十字标记进行定位，然而这对两十字标记叠合时的诸多情况却无能为力。在本文中我们将使用Hough transform 来达成此一工作。

2.       十字标记定位上的问题

两个十字标记定位上的最大问题在于下面三点：
a.   位于下层的标记会被上层所遮掩，因此无法露出完整的影像。这使得灰度累积与Cross correlation方式无法在此处作用，因为仅对部分标记统计出中心点是并没有任何意义的。而Cross correlation使用的前提是两个影像必须相似，然而残存的影像可能已经不是个十字标记的图形，因此去检查两影像相关后的峰值是没法决定这标记的任何资料的。
b.   实时影像会造成在小区间的线段有变形的问题，这会使得如果仅对部分的线段进行检测会出现错误，因此得对整张影像进行分析。
c.   线段的方向繁多，如果仅用LMS Fit的方法来进行，光选择线的方向并将影像中的点分类到不同的线中就是个庞大的工程了。
这些问题都造成了两十字标记在定位对准上的难度大幅提升，而本篇所要提出的方法就可以解决上述所有问题。

3.   Hough transform

Hough transform [6][7]一般用于线段的检测，有两种主要的形式，一种用斜率表示，另一使用角度与半径的格式，第一种表示的最主要要缺点为斜率无限大时难以实作的问题，虽然有学者用斜率与斜率倒数(m、1/m) 并行的方式来解决此一问题[5]，但大部分的的文献还是使用第二种方法来实作，即是下式：

Hough transform 的优点是不必担心线段的断裂或噪声的干扰问题，然而其缺点是运算速度过慢。这个问题主要来自两方面，一是对每个点必须作反复的运算，其复杂度与参数平面的大小有关，如果Θ轴有180个刻度，那每个点就必须进行180次的运算。为了解决这个问题，一个灰阶变化的检测方式经常使用。运用X方向与Y方向的灰度变化的比值，可以直接用arctan 求出Θ，再代入(1)就可以直接得出R [6][9]，将本来要进行180次的运算用一次就解决了。然而当影像有比较多的干扰以及不平整的线段表面时这个方法就不是非常可行了，而本文的影像就有这种问题。Stavros J. Perantonis等人，则是在1999年提出由区块转换来进行Hough transforms 以取代对影像上的点作转换[8]。
另一个考验在于如何从参数平面求出适当的参数解。J. Basak and S.K. Pal 设计了Hough transform network [11] 来解决需要多个输出的问题，他们将x与y 当成两个输入，Θ与R当成一组输出，需要几个的线段就用几组输出并用两层的神经元予以训练。而Nicolas Guil则使用类似inverted tree的方式来解决这个问题[5]。

4.       FHT算法

这里最主要的观念是缩放刻度，一般而言是依照着Θ或R的中的一个坐标轴，依次的将点透过( 1)转换到参数平面上去。如果能事先知道方程式解大约的位置，就可以不必在每个坐标刻度上都做转换。因此先将参数平面以大的刻度表示，以式(1)计算出结果，当某一个刻度有比较多的累计值时再以较细的刻度去计算，这可以必避免掉浪费在不可能区域的计算。

图3及图4表示了这样的结构，按树状图来说，当其某节点的上的累积值大于一阀值时，就将其分为更多的子节点来计算。而将其拿到参数平面上来看时就是当坐落于某一区块内的累计值大于阀值时，就以更细的刻度予以计算。而当计算的精度达到要求的精度时，停止此一递回的程序。如果以4乘4的方式去分割平面，即把R和Θ轴都四等分，在树的第四层就可以达成180度的要精度要求。而这里所节省下的计算就是那些未达到第四层节点所花费的计算，同时线段的参数解必然也仅存在那些第四层的节点上，又可以节省下搜寻解的计算量。

图5.

(a)xy平面上的点及(b)其在参数平面上转换的结果，其中xy平面上的原点在左上角，而参数平面的横轴为R纵轴为Θ
然而如果有太多点坐落于原点的附近就会破坏此一计算上的优点，考虑下式：

其中Xi Yi 为影像空间上的点，Rimax为其在参数空间上最大的振幅。从式(2)可以发现越接近原点的点其振幅越小，从图5中一样可以看到相同的结论，这会使得算法效果不显著。因此在参数空间的切割上做了些的调整，从( 2 )中可以观察到振幅与点的位置是呈正比关系，

为了达到无论R的大小，经过的切割平面数都尽量的相同。在切割R轴时，R越小则ΔR越小，即切割出的参数平面越小。按照这个方式就可以减少靠近原点的值总是停留在同一参数空间的问题，可以提升在R值较大的参数平面使用率比较小的问题。下面是此一提升HT速度的算法，使用的是一递回的方式：

这里的RootPlane和SonPlane都是一个节点，包含了它在参数平面的四个边界、层数Level以及经过了这个平面的所有点Pi。至于该在第几层结束程序就看对精度的要求，可以用下式得出：

如果对Θ轴的要求为180个刻度，N就是180，而k就是对Θ轴每次分割的个数，一般而言k=2,3,4都有不错的效果。Vote就是经过此平面的点数，用以和Threshold做比较，决定是否有足够的点数经过此一平面。如果有足够的点经过此一平面，就进入下一层计算此平面的子平面。当Threshold太大时虽然可以提高运算速度但可能会使得正确的解被略过了，而如果定的太小不但使得运算速度变慢，也会使得其在解答的收敛速度上的优势被抹煞。至于此点是否坐落于此平面里则可以和平面的中心点作比较，这是最直接的方法，直接将点代入平面中心的角度，然后检查是否在此平面内，或者参考Nicolas Guil等人在[5]里提出的 一些方法。
关于参数平面的刻度规划可以从式(2)中得出，其最大的解必然和影像的大小相关。一张300乘240的图其最大的R仅需设400就足够了。而R和Θ的关系可以参照L. Lin[9]和Keishi Hanahara[10]所使用的关系式：

NΘ为Θ轴的刻度数目，ΔR为R轴的刻度大小，而N为影像平面的大小。这个式子可以帮助衡量参数平面的刻度大小是否合理，正常而言，一般的要求都能满足此一式子的条件。

5.       计算十字标记的坐标

分析十字坐标的边缘线条，不难发现这种标记是由两组互相相差90度的线段所组成，找到一组就能立刻在参数平面的另一边相差90度的地方立即找倒另一组，而且解都在同一个Θ轴上，这些信息都有助于在分析由算法传回的值时找出正确的解。这些信息被整理在图6中，就单一方向上的线条而言一共有四条，包含两长两短。因为角度相同，所以在参数平面上也位在同一个Θ的刻度上，将其单独拉出来看就成了图6(b)的图形。观察这两个图形的关系，原本在空间中是四条直线到了参数平面上了四个共线的点，然而其在空间中的几何关系依然没变，也存在于参数平面上的点，甚至变得更明显了。这些关系式表示在下面：

如果再辅以已经知道的十字宽(W)高(L)还可以再加入下列的关系式：

图6

(a)十字标记的各项参数及其在(b)参数平面上单一角度上的投影结果

从上面两式使用HT来分析十字标记的优点就被显现出来了，无论标记有多少部分被遮住，只要能找到一个以上的边，标记的中心线就能够被找出来。至于要如何判定是哪个边则可以参考图6. (b)中表示的，较短的边自然拥有较少的累积值，较长的边拥有较高累积值，依照此关系可以把R1/R4和R2/R3区分开来。同样的方式也可以找出Rc2，至于其余的关系式表示在下面：

式(8) 为计算十字标记中心点的公式，而式(9)则算出了其角度，式(10)则用以的算出中心点在X,Y方向上的投影，将其换算回直角坐标。
下面参考图7的示意图，将如何计算两十字标记的角度与位置上的误差表示如下：

在上面已经论述过了，无论其中一个十字标记如何被另一个所覆盖都不会影响从参数平面求取十字标记的中心点与角度。因为两个一样大的标记除非是重叠，否则必定有一部份的标记裸露出来，而只要有一段漏出来，其在参数平面上就会有一个点，这就足够经由式(6)(7)求出其两个中心线，因此Ra/Rb的取得不会是问题，只要套入(10)就可以把两的标记的中心点转回直角坐标平面。两个十字标记间的所有校正所需的参数就可从(11)中取得了。

6.       执行步骤

可以将简单叙述系统执行的动作，将上述的方法整合成一个完整的动作。
步骤一：执行二值化与边缘运算的处理。相对于只进行二值化的影像，经过边缘运算后的影像不但拥有更多的信息，如四个边的特性被显现，而且执行HT时也会更加的快速，毕竟每个点都必须经大量的运算才被投影到参数平面上。而二值化的阀值则是给定的。
步骤二：选定十字标记的宽的一半为FHT算法的阀值，计算所需的内存空间大小，初始化根平面与最大的层数。标记的宽高是给定的，其宽度事实上就代表了宽这个线段由多少个像素所组成，也代表了应该有多少点该在此宽度所在的参数节点上。
步骤三：执行FHT 算法。将所有的点丢到根平面上，计算每个点和其子平面的关系，这里选用的是四分树，所以每个平面都有四个子平面。找出所有和点有相关的子平面，将点丢到此一平面内，再把此点当成根平面重复此程序。
步骤四：从所有FHT传回的半径与角度找出十字的边界线。按照着在上一节所叙述的方式，依累积的大小与几何关系在参数平面上找出十字标记的边界与角度。
步骤五：求出两十字标记的位置与方向的误差。按照着在上一章节(8)-(11)的关系式将两个标记的误差求出来。
步骤六：将此误差传回。

讨论

本文中提到的方法因为对系统的精度要求最高，其次为速度上的考量，对于HT目前普遍讨论的另一个问题—内存空间的使用，反而并没有那样的注重。一者也是因为这是在上计算机上的运算，而这样的内存需求对目前的计算机实在是轻而易举，因此反而是以空间换取时间，以争取在实时影像处理上的一个最佳效果。
而本文同时也显现了一个在HT参数平面进行影像分析的好处，它可以无视于影像的缺陷与噪声的干扰，将原本线的探讨变为点的分析，却依然保有所有几何特性，这是在影像空间的分析如样板比对的方式所不能及的。