# A Novel Data-Aided Frame Synchronization Method Based on Hough Transform for Optical Communications
## 3 HT-Based Frame Synchronization Algorithm  
### Hough Transform  
In 1962, [PERSON] devised an ingenious method, popularly called Hough transform (HT), which efficiently identifies lines in images [29; 30]. It is still an important tool for digital image processing nowadays. The core idea of Hough transform is to establish a dual relationship between points and lines, image space and Hough space. The principle of detecting straight lines based on Hough transform is briefly introduced as follows. Figure 1: Received frame sequence. F, frame; S, frame synchronization word; D, payload; \(L\), frame length; \(M\), synchronization word length; \(N\), payload length; (**a**) diagram of frame sequence with fixed synchronization word inserted. ; (**b**) sliding window starting from \(\tau_{m}\). The equation representation of a straight line in cartesian coordinates (we call it _xy_-space in this paper) can be expressed by slope (\(k\)) and intercept (\(b\)) as follows. \[y=kx+b \tag{3}\]  
If the parameter space, _kb_-space is established, the straight line in _xy_-space actually corresponds to a point in _kb_-space. Similarly, a straight line in _kb_-space corresponds to a point in _xy_-space. This is a so-called dual relationship mentioned above. It can be easily drawn that intersecting position relationship in _kb_-space corresponds to collinear position relationship in _xy_-space. However, there is a parameter problem with the established _kb_-space. The vertical lines in _xy_-space, whose slope is infinite, do not have corresponding points in _kb_-space. To this end, space is established and the correspondence can be written as. \[\rho=x\cos\theta+y\sin\theta \tag{4}\]  
As shown in Figure 2, \(\rho\) is the algebraic distance from the origin to the line and \(\theta\) is the angle between _x_-axis and the vector perpendicular to the line. If we restrict \(\theta\) to the interval \((-90^{\circ},90^{\circ})\), the dual relationship between _xy_-space and \(\rho\theta\)-space exists in any cases. However, the curve in \(\rho\theta\)-space corresponding to the point in _xy_-space is not a straight line, but a sinusoid. The _xy_-space is the image space while the \(\rho\theta\)-space is sometimes called Hough space. The properties of point-to-line dual relationship between image space and Hough space can be summarized as follows. * A point in image space corresponds to a sinusoid in Hough space;
* A point in Hough space corresponds a straight line in image space;
* The collinear position relationship of points in image space corresponds to the intersecting position relationship of curves in Hough space. However, it is essentially exhaustive that we map all the points in image space into their corresponding curves in Hough space, without any restrictions for straight line detection, and the computation required grows quadratically with the number of points [31]. To this end, Hough space is quantized into grids, and accumulator cells are created. For each non-background point \((x_{n},\ y_{n})\) in image space, the corresponding curve given by Equation (4) is entered in the grids by incrementing the count in each accumulator cell along the curve. Eventually, a given cell records the total number of curves passing through it, which means that these points in image space are collinear. Figure 3 gives an example for a thorough understanding. Figure 2: Dual relationship between _xy_-space and \(\rho\theta\)-space. (**a**) _xy_-space; (**b**) \(\rho\theta\)-space. There are five points in the image space with a black background, which corresponds to five curves in Hough space, respectively. \(\theta\) is quantified at 1-degree intervals and the interval for \(\rho\) is also one. Hough space is divided into accumulator cells. It can be seen from Hough space that the two points at \(\theta~{}=~{}\pm 45^{\circ}\) are generated by the intersection of the three curves, which means that there are two sets of three collinear points in the image space.