Enhanced Radon Transform Skew Estimation And Correctıon Algorithm For Scanned Multiple-Choice Forms

Document Skew

To begin the literature, document skew is an undesirable tilt or offset from the centre-line by a certain degree of a scanned document image observed after capture. It had been broadly classified into three groups; global skew, multiple skew, and non-uniform text line skew (Abdu, 2013). Variation of the degree of skew however, plus the orientation, size and nature of the objects in the document image play a vital role in the choice of technique or method employed and its accuracy. A detailed survey of over 50 various skew detection algorithms was given in (Hull, 1998). These classes largely include projection profile analysis (Papandreou & Gatos, 2011), the connected component analysis (Sarfraz et al., 2007), and more recently Radon and Hough transform methods (Gari et al., 2017; Rajput, Som, & Kar, 2016).

Related Literature

The traditional projection profile analysis was among the earliest method where the input image is rotated through a range of angles (Jain & Borah, 2014; Papandreou & Gatos, 2011). At each angle, the projection profile features of objects in the image are evaluated using a criterion function (Jain & Borah, 2014). The function would then reach its maximum value when the projection profile is evaluated at the correct skew angle. The skew angle can easily be determined by analysing the maximum of the function. The projection profile technique is one of the most effective approaches to skew estimation but is often subject to low performance and accuracy when the document image contains noise, graphics, and or the amount of text objects is sparse (Gaofeng, Chunhong, Nanning, & Chen, 2010).

The nearest neighbour clustering based method (Konya, Eickeler, & Seibert, 2010) is similar to the connected component analysis technique as it also involves connected components (objects). In this method, for each identified object, the direction of its nearest neighbour is estimated and accumulated in a histogram. The angle corresponding to the maximum peak of the histogram is extracted as the relevant image skew. This kind of process is generally slow however, explicitly when the time it takes for labelling the objects in the binary image is determined by O(n^2 ), where n is the number of objects (Gaofeng et al., 2010). Moreover, to avoid the extraction of a false peak graphic objects must first be filtered out from the image (Konya et al., 2010).

Principal connected component analysis on the other hand is solemnly based on finding the orientation along which the largest variation of objects occurs (Sarfraz et al., 2007). The objects can be labelled depending on the connectivity of the pixels that make up an object or inform of their enclosing bounding boxes. Once an object has been classified as a connected component, each object's orientation is estimated through computation by getting the angle between the x-axis and the major ellipse that has the same second moments as the object. A skew detection algorithm that uses this method starts by first dilating the input binarized image as in the case of the projection profile technique and then getting the orientation of each object (Dhandra, Malemath, Mallikarjun, & Hegadi, 2006). The final skew angle is determined by taking the average of all the orientations. In this method, however, ambiguities may arise in the case of non-uniform text line or if the input image contains graphics of varying shapes and sizes not to mention different orientations. Therefore, considering the average of all the objects' orientation does not seem to be a suitable approach as some MC forms contain no text objects while others may have the text, but not significant enough to provide the correct orientation or with a different orientation with the main concerned answer regions. Other methods employ the use of trigonometric formulae, histograms processing and the concept of Euclidean distance all applied to the bounding box enclosing a defined area in the input image (Sarfraz et al., 2007; Shafii & Sid-Ahmed, 2015). The calculated slope between extreme opposite corners of the bounding box was used to get the resulting skew variation.

The Radon transform can transform images with lines into a space range (or Radon space) of potential line quantities, with each line giving a peak or a valley in the space (Toft, 1996). Bright lines give peaks while dark lines give valleys. It is also found to be less sensitive to noise compared to other techniques such as the Hough transform as the noise tends to be attenuated during the process of integration. The compactness of the Radon transform had led to many line detection algorithms (Qiaoping & Couloigner, 2007; Rajput et al., 2016; Ramandi, Faez, & Ardekani, 2012; Sari, Suksmono, & Iwut, 2011). However, the Radon transform does not always produce suitable peaks (Qiaoping & Couloigner, 2007). Some of the techniques e.g. (Ramandi et al., 2012) that use this method apply dilation first on the binarized document image to make the text objects into a single line before taking its radon transform, while others (e.g. (Aithal, Rajesh, Siddalingaswamy, & Acharya, 2011)) detect the edges and rotation (Rajput et al., 2016). Each line in the image would give a peak in the case of a bright line which can then be extracted to determine the skew. The current traditional Radon transform methods such as the ones in (Rajput et al., 2016; Ramandi et al., 2012) rely on this phenomenon and resolve to directly extracting a single maximum peak and set its corresponding angle as the basis for the correct skew. Thus, inaccurate peaks may be extracted, especially in cases where there are no or non-uniform text in the input image such as that of a MCB form and this will eventually lead to non-determination of the correct skew. However, the typical Radon transform does not always produce suitable peaks especially when the image contains linear features of short extent, or when the linear features that have a long span exhibit curvature features (Gaofeng et al., 2010).

In our previous method, the problem of peak selection was solved by extracting the peaks and their corresponding angles based on two scenarios: for a MC form that contains a significant amount of straight line parameters (long linear features) the Radon peak value extracted will be high, and on the other hand if there is no presence of the line parameters or the amount is insignificant then the peak would be low (Abdu, 2013). If the first case holds true, it would mean that the form is a standard OMR based design and that the first extracted peak would be enough to determine the skew. However, if the later holds true, the form would be categorized as a customized (custom) OMR based. A threshold value is set to extract the correct peak and angle in either case. When the maximum peak value is greater than the threshold, it is extracted as the correct peak and used for the determination of the skew; but when the maximum radon peak is less than the threshold value, two more peaks are taken, and an interpolation is performed between the three peaks to determine the correct skew. The MC form image can then be corrected using the estimated skew as the amount and direction of rotation in degree.

The rest of the paper is organized as follows: Section 2 gives the identified problem statement from related works. Section 3 highlights the research questions, section 4 purpose of the study, section 5 the proposed research methods, section 6 findings, and finally section 7 gives the conclusion.

Existing methods

There are a different variety of techniques that have been proposed as reviewed in literature for the estimation and correction of skew in scanned document images (Aithal et al., 2011; Boukharouba, 2017; Dhandra et al., 2006; Gaofeng et al., 2010; Gari et al., 2017; Haji, James, & Chandran, 2016; Wagdy, Faye, & Rohaya, 2014). However, these approaches mainly focus on document images; specifically, images that contain a significant amount of text characters with the assumption that the text direction is the same as that of the border line. Moreover, it is assumed that the text orientation determines the orientation of the whole document. A notion that was found to not always be true in the case of MC forms. While this may be true for MC test or survey forms having text with orientation the same as the answer regions, it would not be the case for forms having independent text and answer regions orientations such as those that are customize for specific use. Hence these algorithms performed poorly in such case and would not be suitable for MCB forms.

Previous method

Our previously proposed work using Radon transform overcame the limitation of using a single extracted peak for detection of the skew but did not restrict the domain for which other relevant peaks would be extracted. Due to this the other peaks can be randomly extracted from any domain when the first maximum radon peak is less than the threshold value as it was not fine-tuned for camera images. This greatly limits the inherent capacity of the algorithm to accurately give the correct skew.

General Concept

The idea is to use simplified algorithms capable of performing the task at hand with less complexity. What algorithm would be suitable for application?

Towards Current and Future Applications

In this era of enhance mobile smart phones equipped with high-end cameras assessing MC forms on a mobile can be as easily as snapping a picture provided errors from capture are reduced to the barest minimum. What simplified way would be to reduce assessment error?

Pre-processing

The MC forms images were acquired using ADF scanner and phone cameras. Hence, it is assumed here that the skew in the resulting images would not vary by more than ±6º and may contain some degree of blur. Phone camera images particularly were first manually cropped to remove the background. Normalization is the first step, resizing the images into specific ratio; this is necessary because images captured may vary in sizes especially when they are captured at different resolutions. A fixed value was chosen for the column size (W) while the row size (L) is automatically calculated to fit normal A4 size. Hence the column size is fixed at 750 and the scaling ratio between the horizontal and vertical dimensions is maintained at (1:1.3). Experiments in this perspective also showed that the larger the image size the less sharp it will be and this reduces the edge detection as compared to a smaller sized image. Smaller size images also make the processing faster. Larger images are down-scaled while smaller sized images are up-scaled. The un-sharp masking is used to counter the blur effect and sharpens the MC form image by amplifying the border and edge pixels. Sharpening is achieved by first smoothening the input image $f(x,y)$ using a Gaussian, which results in a further smoothed image $f_s(x,y)$. The result is then subtracted from the input image itself to get a filter mask $g_m(x,y)$. The mask is then finally added back to the original input image resulting in a de-blurred image $f_d(x,y)$. This expression is given by (Abdu, 2013):

$g_m(x,y)=f\left(x,y\right)-f_s(x,y)$ (1) $f_d\left(x,y\right)=f\left(x,y\right)+g_m(x,y)$ (2)

This method also effectively increases the contrast along the edges without much computation compare to other sharpening methods. The de-blurred image is then binarized using Otsu's thresholding method (OTSU, 1979) applied locally, after which the edges are detected using an edge detection algorithm. There are several techniques of edge detection in existence (Basu, 2002), but for this paper, Canny (1986) edge detector was used. It is pertinent to minimize computation complexities while maintaining robustness and thus, simple basic algorithms were employed to achieve the desired pre-processing results.

Radon Transform and Peaks Extraction

The Radon transform of the 2-D normalized image represented as a function $g_E(x,y)$ in Euclidean space can be defined by (Qiaoping & Couloigner, 2007):

$R\left(\rho ,\theta \right)=\underset{-\mathrm{\infty }}{\overset{+\mathrm{\infty }}{\iint }}{g}_E\left(x,y\right)\delta \left(\rho -xcos\theta -ysin\theta \right)dxdy$ (3)

and represented in discrete form as:

$R\left(\rho ,\theta \right)={\sum }_{x=\mathrm{0}}^m{\sum }_{y=\mathrm{0}}^n{g}_E(x,y)\delta \left(\rho -xcos\theta -ysin\theta \right)$ (4)

where $\delta (\dots )$ is a Dirac function that will result in a nonfinite value when the statement is zero and a zero for all other statements (it integrates to one).

The term $\delta (\rho -xcos\theta -ysin\theta )$ in the Dirac function $\delta$ in equation (3) & (4) forces the integration of $g_E(x,y)$ along the line defined by equation (5).

$\rho =xcos\theta +ysin\theta$ (5)

See Full Size >

Therefore, $R(\rho ,\theta )$ yields the projections across $g_E(x,y)$ at varying orientations $\theta$ and offsets $\rho$ along parallel paths or beams. The parallel beams are spaced 1-pixel unit apart with the source of rotation around the centre of the image. The geometry of the radon transform is illustrated in Figure 2 (Abdu, 2013).

The Radon transform would then contain a peak corresponding to every line in the image that is brighter than its surroundings and a valley for dark lines. Thus, detecting the lines would simply mean to detect the peaks and valleys in the $(\rho ,\theta )$ space, which can easily be done by setting up a threshold that will extract the maximum peak. For this experiment and given the nature of the normalized MC form image the Radon transform was then taken across an angle range of 180º (-90:89) sufficient for $\pm 6°$.

See Full Size >

Figure 3 is an example of the Radon transform of some of the MC form images. It is ideal to obtain sharp relevant peaks (e.g. Figure 3 (a) through (c)), however sparse (un-sharp) peaks can be observed as shown in Figure 3 (d) through (f) due to the shortage of straight line patterns.

A threshold value “ $t\ge 300$” based on experiments on the number of pixels contained in a single straight line was used to distinguish between the two designs of MC form (standard and customized). This threshold value was fixed, since the image has already been normalized to fixed pixel dimensions. If the detection of the first (standard OMR) design fails, such that ${\rho }_p<t$, the same scenario used in our previous work is applied here for the other two peaks but from the center domain in terms of their magnitude. That is, both peaks must be centralized peaks having similar magnitude. The final skew angle ${\theta }_S$ is then calculated using the three angles corresponding to the three extracted peaks such that ${\theta }_s=\underset{i=1}{\overset{3}{\sum }}{\theta }_{pi}/3$ (Abdu, 2013).

While the condition for extracting the relevant peaks was restricted to magnitude weight, however, the domain selection became prone to variability. Relevant peaks with smaller magnitudes from the centralized domain get ignored for others with larger magnitude like ${\rho }_p$ from other domains. The algorithm often selects these peaks not related to the centralized peaks, resulting in a false ${\theta }_s$.

Hit-and-miss Algorithm

Adding the hit-and-miss algorithm enhances the skew detection algorithm by constraining the peak selection to only the centralized domain of the Radon space. Two criteria were set such that each of the two additional peaks must be tested to satisfy as a relevant peak. Peaks that do not fulfill are discarded and the process repeats until the relevance is achieved. The first measure is the magnitude, where each extracted peak must satisfy the threshold condition for the custom OMR form. This can be interpreted as $\rho \to {\rho }_{pi}\leftrightarrow \rho \ge t$. The second measure is the domain, such that ${\theta }_2|{\theta }_3\in {\rho }_2{|\rho }_3\leftrightarrow -20°\le R_{\theta }(x^{\text{'}})\le 20°$ where $R_{\theta }\left(x^{\text{'}}\right)$ is the centralized Radon space domain. The correction procedure is whereby the image border line is rotated by degree of the amount of skew estimated. The boundary of the image is further adjusted to maintain its original size.

Please replace this text with context of your paper.

Please replace this text with context of your paper.

Please replace this text with context of your paper.

Please replace this text with context of your paper.

• Please replace this text with context of your paper.

• Please replace this text with context of your paper.

See Full Size >

Most of the reported works were tuned for document images, and thus the basis for comparison can be trivial. Regardless, the most common methods based on traditional Radon transform (Aithal et al., 2011; Rajput et al., 2016; Ramandi et al., 2012) and bounding box algorithms have been replicated in this research paper and compared with the proposed enhanced algorithm. The results are shown in Table 1 . The proposed algorithm clearly surpasses the other techniques in performance, and this shows that the other methods are not suitable for OMR MCB forms.

Results showed an excellent overall performance of the proposed enhanced algorithm at 98.9%. The least accuracy was 95% (in the case of phone camera images at 3MP). One observed reason is in the case of custom OMR based forms which have fewer line patterns, this makes the result slightly prone to error. Another reason is that when additional peaks need to be extracted as in the case of lower resolution images, the degree of blur becomes significantly higher affecting the edge detection algorithm leading to higher amount of biased and un-sharp peaks. Although, it is very unlikely that 3MP resolution setting be used since mobile phones come equipped with 5MP and higher resolution cameras. Thus, this limitation can be considered insignificant to the robustness of the proposed method with an average accuracy of 98.83% at 5MP, 99.98% at 8MP, and 100% at 10MP for both ADF and phone camera images.

The Bounding box algorithm performed the least with 53%. A logical reason for this is that for the correct orientation to be determined, the formed bounding box must be a trapezoid (two opposite sides parallel). The algorithm uses the concept of parallel lines theorem to form an equiangular rectangle from the formed bounding box. With most of the MC form images containing graphics (answer bubbles) as the only and or dominant objects, a trapezoid could not always be formed. The normal Radon transform approach uses a similar technique as that of (Aithal et al., 2011) as the image is first dilated prior to applying the transform. Taking the transform in this sense ultimately gives un-sharp and large peaks which are cumbersome. Hence extracting a single large peak that corresponds to the correct skew lead to low accuracy.