TECHNICAL FIELD

Embodiments of the present disclosure relate aligning text lines. More particularly, the embodiments relate to extracting arbitrarily curved text lines of an image captured and aligning the text lines horizontally.

BACKGROUND

Digital cameras are increasingly used for acquiring document images. In addition to imaging hard copy documents, digital cameras are now used for acquiring text present in 3D real world objects such as signboards, buildings, vehicles and T-shirts. Applications are being developed, where hand-held imaging devices can be used to read text from such sources. Texts from such sources are often oriented arbitrarily for artistic and other purposes. Though there has been a lot of research on document image analysis, there is very little work on retrieving text information from such images.

Conventional optical character recognition (OCR) systems perform well only in recognizing texts that are linearly aligned as shown in figure 1. Performance of state of the art OCR systems on multi-oriented text is determined. Figure 1A shows a binary input image to Nuance Omnipage Professional 16 OCR (Trial version), figure IB is the corresponding output. Figure 1C is the output of ABB Y FineReader 10 Professional OCR (Trial version). While the horizontally aligned text is easily detected and recognized, curved text not only poses a challenge to recognition but also makes the text segmentation process difficult. In most existing OCR systems, a skew correction process is often performed prior to recognition, should a need arise. Most skew estimation techniques assume the presence of long and straight text lines. This assumption may not always be true for scene images, which often contain short text lines that could be oriented in an arbitrary direction. It may also contain text laid out in a curvilinear fashion where every character in the text string is skewed differently. These issues call for specialized pre¬processing techniques that estimate and correct the skew of individual characters before feeding such a document to an OCR system.

One technique describes how to handle multiple skew in Bangla and Devanagari script documents using inherent characteristics of the script. Both the scripts have a headline that connects characters into a word. The method searches for the upper envelopes of each connected component (CC) to obtain the headlines. A clustering procedure is performed on the detected headlines and each of the resulting clusters gives an estimate of the skew of individual text line. Though the method can handle multiple skew, it requires that the document contain long straight text lines and is heavily dependent on the characteristics of the script. It is not applicable to majority of scripts since they do not have a headline. The method is also restricted to documents with skew angle less than 45°. These assumptions may not always be met for camera-based images that are characterized by unconstrained acquisition.

Other technique is for skew correction in documents that may contain several areas of text with different skew angles. Adjacent connected components are grouped using a nearest neighbour approach to form words which are further grouped into text lines. Then, the top-line and baseline for each text line are estimated using linear regression. Finally, the local skew angle of each text area is estimated and corrected independently to horizontal or vertical orientation.

Another technique uses connected component analysis and regression technique to restore curved text lines that arise around the spine of scanned pages of a book. The method first identifies the shaded region and binarizes the image using a modified Niblack's method to remove the shade. Then, clustering is performed on the connected components in the clean area to obtain text lines, which are modelled by straight reference lines using linear regression. A bottom-up approach is applied to cluster the connected components in the shaded area into warped text lines, and polynomial regression is used to model the warped text lines with quadratic reference curves. The method assumes that the document with moderate skew is scanned in such a way that the text lines are horizontal. It also requires that there are partially straight text lines in the image.

Another approach can identify the skew angles of individual characters in a document image using an instance-based matching method. Unlike other skew correction techniques, the method does not rely on the local straightness of the text lines and/or character strokes. It can handle documents where the characters do not form long straight lines. The method computes rotation variants and invariants for each character and stores them as instances. Skew is estimated at the connected component level. It identifies the character category, estimates local skew from the stored instances of the identified category and finally determines global skew employing a voting strategy. The font image and the rotation angle for which the match score is maximum yield the character category and the local skew angle. However, the method still assumes a single skew for the whole page and also requires that the documents have fonts similar to the ones that are stored as instances.

Further, two methods address curved text but yield only partial success. In one method, partial images of character strings are cut out from a colour document and assuming that the sequence of the characters constituting the text line is known, quadratic functions are used to approximate the curvature of the string. The type of curvature of the string is determined using heuristics and a suitable correction scheme is applied. The method assumes only one text string per image and cannot handle documents containing multiple text lines. Only linearly skewed and arc-form text are considered and it cannot handle other text layouts such as 'triangular' or 'wave' or a combination of different forms.

In one method, arc-form text is transformed to linear-form text using concentric ellipsoidal contours. The method assumes that the text in the document is either circular or elliptical in shape and is limited to only the upper half circle or ellipse. The use of ellipsoidal contours also leads to severe distortion of the characters during the arc-to-linear transformation. This calls for a further de-tilting step. This post-processing step works only for upper case Latin script. Documents with multiple text lines and multiple text orientations cannot be handled. It also focuses only on the alignment of individual characters and does not account for the inter-word gap that is essential to obtain meaningful text.

In light of the foregoing discussion, there is a need for a method and system to solve the above mentioned problems.

SUMMARY

The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method and system as described in the description.

One embodiment is a method of extracting and aligning curvilinear text from a captured image. The first step of the method is receiving a binary image as an input. Connected component (CC) labelling is performed on the binary image for obtaining a set of disjoint components. One or more text lines are obtained by grouping adjacent CCs based on the proximity and regularity. The orientation of the text lines is determined by estimating angle between the centroids of a CC and its nearest neighbour CC. Text strings are identified by repeating the same for all the CCs and grouping successive neighbours that satisfy the criteria of proximity and size regularity. Alignment of the text lines is performed using vectors normal to a spline curve fitted to the centroids of each CC of the text string.

BRIEF DESCRIPTION OF THE ACCOMPANYING FIGURES

The novel features and characteristics of the disclosure are set forth in the appended claims. The embodiments of the disclosure itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying figures. One or more embodiments are now described, by way of example only, with reference to the accompanying figures in which:

Figure 1(a) illustrates a binary input image.

Figure 1(b) illustrates the output of Nuance Omnipage Professional 16 OCR.

Figure 1(c) illustrates output of ABBY Fine Reader 10 Professional OCR.

Figure 2 illustrates a block diagram of the text alignment method, as an embodiment.

Figure 3 illustrates parameters that guide the process of grouping CCs to obtain text lines.

Figure 4 illustrates text line extraction results on several images containing multi-oriented characters and multiple text lines.

Figure 5(a) illustrates an input image with a text string.

Figure 5(b) illustrates control points derived from the centroids of the characters of the input text string which is shown in figure 5(a).

Figure 5(c) illustrates a B-spline curve fitting and the estimated normal vectors.

Figure 5(d) illustrates horizontally aligned image of the input text string of figure 5(a).

Figures 6(a), (b) and (c) illustrate experimental results of OCR readability on images with curved text lines. In Figure 6(b), the input is identified as image and not a text string and hence the image is left as it is.

Figure 7(a) illustrates two input images to the text alignment technique, containing Kannada and Tamil curved text strings.

Figure 7(b) illustrates rectified output text lines of the text alignment technique with inputs as shown in figure 7(a).

Figure 8 illustrates a schematic flow diagram of the method.

Figure 9 illustrate a system block diagram to extract and align text lines of an image captured, as an embodiment.

One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the disclosure described herein.

DETAILED DESCRIPTION

The foregoing has broadly outlined the features and technical advantages of the present disclosure in order that the detailed description of the disclosure that follows may be better understood. Additional features and advantages of the disclosure will be described hereinafter which form the subject of the claims of the disclosure. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present disclosure. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the disclosure as set forth in the appended claims. The novel features which are believed to be characteristic of the disclosure, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that each of Figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present disclosure.

An exemplary embodiment of the present disclosure is a system to extract and align curved text in a captured image. The system block diagram 200 is shown in figure 2. An input block 202 receives a captured binary input image. The binary image is provided to the input block using an adaptive binarization technique. The next block is an identification block of text lines 204 to identify the text lines from the input binary image. The input to the text alignment block 206 is the identified text lines, where all the text components are represented in black irrespective of their original colours in the input image. An 8-connected component labelling is performed on this binary image to obtain a set of "M' disjoint components {CCj}, j=1,2,...,M. Small and spurious components from this binary image are removed by an area-based heuristic filtering.

In the alignment block 206, the individual text lines are first determined using the spatial regularity properties of text. A B-spline curve is fitted to each identified text string and its constituent characters are then individually aligned by estimating vectors normal to the fitted curve. The normal vectors, thus locally determined, give a fairly good estimate of the orientation of the individual characters. The rectified text string is obtained by rotating each character such that the normal vector is aligned vertically. The output of the text alignment block is shown as block 208.

One embodiment of the present disclosure is a method of extracting and aligning text of a captured curvilinear image. Individual text lines are first determined using the spatial regularity properties of text. A B-spline curve is fitted to each identified text string and its constituent characters are then individually aligned by estimating vectors normal to the fitted curve. The normal vectors, thus locally determined, give a fairly good estimate of the orientation of the individual characters. The rectified text string is obtained by rotating each character such that the normal vector is aligned vertically. The method is applicable for text laid out in various forms namely arc, wave, triangular or a combination of these with linearly skewed text lines.

The method of extracting and aligning curvilinear text in a image captured consists of the following steps. Firstly, the input to the text alignment block is a binary image that comes from an adaptive binarization technique, where all the text components are represented in black irrespective of their original colours in the input image. An 8-connected component labelling is performed on this binary image to obtain a set of 'M' disjoint components {CCj}, j = 1, 2,..., M. Small and spurious components from this binary image are removed by an area-based heuristic filtering.

The next step in the method is identification of text strings. Since text normally exhibits spatial regularity, we seek to obtain text lines by grouping adjacent CCs based on their proximity and regularity. The heights of characters in a text line are generally more 'stable' than their widths and do not vary even if they are represented in italics or bold. To make use of this observation during the search and grouping of similar adjacent CCs, the local orientation of the text is first determined from the angle between the centroids of a CC and its nearest neighbour (NN). If the angle lies in the intervals [45°, 135°] or [225°, 315°], the orientation of the text is assumed to be vertical; otherwise, it is horizontal. The estimated angle and orientation guide the subsequent NN search and grouping. Depending on whether the estimated text orientation is horizontal or vertical, the NN-search distance is made proportional to the height or width of the reference CC, respectively. For a given component CCref and its nearest neighbour CCnn1, CCnn2 is found, which is the subsequent NN of CCnn1. The resulting triplet is analyzed for similarity of sizes and angles and is grouped together whenever the following conditions are satisfied:

where Sd = Dist(CCref, CCnn1) refers to Euclidean distance between the centroids of CCref and CCref denotes the anti-clockwise angle of the line joining the centroids of the reference component and its i"1 neighbour with respect to the horizontal. The parameters Sref, dnni and <$„„2 represent the heights or widths of CCre/, CCnn\ and CC„„2, respectively depending on the search direction. These parameters are illustrated in Figure 3. Equation 1 checks that the relative angle difference between the two neighbours with respect to the reference component lies within a threshold value. Equation 2 tests the similarity in their sizes while equation 3 restricts the search distance. Since text exhibits some degree of regularity in general, the parameters Ti, T2, T3 and T4 work well for values in the range [20 30], [0.25 0.5], [1.5 2.0] and [2 3] respectively. The search process is repeated again by making CCnn\ as the reference component CCref.

The process is continued till all the CCs are considered and we obtain the individual text lines {Tkj, k= 1, 2,..., K where K is the total number of detected text lines. Figure 3 shows the parameters that guide the above process of grouping CCs to obtain text lines. Figure 4 illustrates the identified text strings for images that have multiple text lines, oriented arbitrarily.

B-splines are piecewisc polynomial functions that can provide local approximations of contours of arbitrary shapes using a small number of parameters. B-splines are used because they exploit the smoothness inherently present in the text layout. Since polynomial fitting results in numerical problems for vertically aligned text, the usual practice is to swap the x and y coordinates before curve fitting. The issue still remains for an image that contains horizontal as well as vertical text lines. B-splines can be used to represent curves of any shape thereby making it an ideal choice for handling images that contain multiple text lines. For each identified text string 7k, the centroids of the constituent characters are identified and represented as follows:

where 'Nk' is the number of characters in the kth text string. These points serve as the control points for fitting B-splinc curves. The ith point in the resulting curve is represented as follows:

The order of the spline curve is chosen to be 5 so that the resulting curve is smooth and offers robustness to the zigzag pattern of the control points. The zigzag pattern arises due to the presence of ascenders and descenders. The normal vector at the f point of the curve is then computed using the following relation.

The subscript i denotes the position on the spline curve at which the normal vector is computed and || . ||2 denotes the L2 norm.

In one embodiment, horizontal alignment of text is illustrated. The normal vectors which are locally determined, give a fairly good estimate of the orientation of the individual characters. The rectified text string is obtained by simply rotating each character such that the normal vector is aligned vertically. The required angle of rotation for any character is computed as:

The values of 6k are indicative of the type of orientation of the text string Tk Here, a positive or negative value of 0 implies rotation in an anti-clockwise/clockwise direction. For a linearly skewed text string, the standard deviation of the Ok is 'small'. In such a case, the whole text string may be rotated by a global angle which is computed as the median value of 6k. On the other hand, if 6k varies progressively from positive to negative values or vice versa, the text string is curved. In this case, each character is individually rotated. The output image is generated by stacking the rotated characters in a left to right direction such that the spacing between the characters is proportional to the corresponding inter-character centroid distances. The inter-character spacing (S*,,,+i) between the component CCj and CC,-+i is computed as follows:

where is the Euclidean distance between the centroids of the ith and (/+1)//7 component and Wt represent the width of the component CCj. The results of all the intermediate steps involved in the alignment process of a sample text string arc shown in Figures 5(a) to 5(d). Figure 5(a) illustrates an input text string, figure 5(b) shows control points derived from the centroids of the characters of the input text string which is shown in figure 5(a). Figure 5(c) illustrates a B-spline curve fitting and the estimated normal vectors. Figure 5(d) illustrates the output horizontally aligned image of the input text string of figure 5(a).

Figure 8 illustrates a schematic flow diagram of the method of extracting and aligning text lines of an image captured. First a binary input image is captured 802, next step is to identify text lines of the input image 804, then aligning the text line 806, which involves the steps of identifying control points for B-spline curve fitting, the estimated normal vectors, rotating the characters of the text and rectifying the text strings or lines to restore the text line 808.

The performance of the method of extracting and aligning curvilinear text from a captured image is tested by collecting a set of 35 images containing text in various orientations and layout styles such as arc, wave, triangular and a combination of these with linearly skewed text lines. Nuance Omnipage professional 16 (trial version) OCR software is used to evaluate the performance of the method. Some example outputs of applying OCR directly on the input images are shown in Figure 6. Without the text alignment pre-processing step, the OCR software yields only erroneously recognized characters in most cases as shown in figure 6(a) or even fails to detect any text at all in some images, as shown in figure 6(b). Figure 6(c) shows a particular case where the input image is automatically inverted by the application/ software before recognition and subsequently identifies 3 text blocks and 1 image block. The resulting OCRed output is therefore fully erroneous. Clearly, a document input with straight text lines seems to be necessary for current OCR systems to work reliably.

After applying the text alignment technique, the recognition accuracy improves significantly. The data set contains 359 characters in all, out of which 3 characters are erroneously recognized yielding an overall recognition accuracy of 99.2%. Some example outputs of the rectified images and the corresponding OCR outputs are shown in Table 1. In the last row of the table, a character 'R' of the rectified word image is wrongly recognized. This may be attributed to its unconventional font style. Since the OCR software yields only erroneous results on the raw input images, they are not included in the table.

Once the individual text strings are identified and the corresponding B-spline fit is obtained, the estimation of normals does not depend on the individual characters. Therefore, the method can handle a variety of text layouts. The method relies only on the overall curvature of the text string and does not assume any characteristics of the script. Hence, it can be easily extended to align text in other scripts since the arrangement of characters in a text string exhibits some degree of regularity in general. The method is tested on multi-script images containing English and two other Indie scripts Kannada and Tamil. Figure 7 shows some example outputs of the method on images with Indic-script content.

Table 1 shows the results of the method of extracting and aligning curvilinear text in several captured images with text oriented arbitrarily. The corresponding horizontally aligned images and the OCR outputs obtained on them using Omnipage Professional 16 (trial version) are also shown:

The method is for the alignment of character strings laid out in arbitrary orientations. Just like the skew detection and correction steps in conventional OCRs, alignment of curvilinear to rectilinear text is an indispensable pre-processing step in the analysis of newer document types that contain multi-oriented text. The effectiveness of the method is amply illustrated by the experiment results with various orientations of text and multi-script document images.

The text grouping step successfully identifies all the individual text lines present in the images regardless of their orientations. However, due to the presence of ascenders and descenders in lower case letters, the positions of the centroid exhibit a zigzag pattern resulting in small errors in the local skew estimate of some characters. This is observed to be within the skew tolerance of the OCR system. The recognition accuracy after text alignment is comparable to that of unskewed text.

Figure 9 shows the system block diagram 900 to extract and align text lines of an image captured. First a binary input image 902 is captured using the input block 904. Connected component (CC) block 906 performs connected component labelling on the binary image to obtain a set of disjoint components. An identifying block 908 obtains text lines by grouping adjacent CC based on the proximity and regularity. Text alignment block 910 is used to align the identified text lines and generate an output image 912.

References:

1. A. Bagdanov and J. Kanai, Projection profile based skew estimation algorithm for JBIG compressed images, Proc. Intl. Conf. Document Analysis and Recognition, 401 -405,1997.

2. H. Baird, The skew angle of printed documents, Proc. Conf. Society of Photographic Scientists and Engineers, 40, 21 - 24,1987.

3. H. Hase, M.Yoneda, T. Shinokawa and C. Y. Suen, Alignment of free layout color texts for character recognition, Proc. Int. Conf. Document Analysis and Recognition, 932-936,2001.
4. A. Hashizume, P.S. Pch and A. Rosenfeld, A method for detecting the orientation of aligned component, Pattern Recognition Letters, 4, 125 - 132, 1986.

5. T. Kasar, J. Kumar and A. G. Ramakrishnan, Font and background color independent text binarization, Proc. Intl. Workshop Camera Based Document Analysis and Recognition, 3 - 9, 2007.

6. Y. Lu and C. L. Tan, A nearest-neighbor chain based approach to skew estimation in document images. Pattern Recognition Letters, 24(14), 2315 - 2323, 2003.

7. K. Mahata and A.G. Ramakrishnan, Precision skew detection through principal axis, Proc. Intl. Conf. Multimedia Processing and Systems, 186 - 188, 2000.

8. L. O'Gorman, The document spectrum for page layout analysis, IEEE Trans. PAMI, 15,1162-1173, 1993.

9. O. Okun, M. Pietikainen and J. Sauvola, Document skew estimation without angle range restriction, Intl. .11. Document Analysis and Recognition, 2, 132 - 144, 1999.

10. U. Pal and B.B. Chaudhuri, An improved document skew angle estimation technique,
Pattern Recognition Letters, 17(8), 899 - 904, 1996.

11. U. Pal, M. Mitra and B.B. Chaudhuri, Multi-skew detection of Indian script documents, Proc. Intl. Conf. Document analysis and Recognition, 292 - 296, 2001.

12. D.F. Rogers and J.A. Adams, Mathematical Elements for Computer Graphics, McGraw-Hill, 1990.

13. P. Saragiotis and N. Papamarkos, Local skew correction in documents, Intl. Jl. Pattern Recognition and Artificial Intelligence, 22(4), 691 - 710, 2008.

14. S. N. Srihari and V. Govindaraju, Analysis of textual images using the Hough transform, Machine Vision and Applications, 2(3), 141 - 153, 1989.

15. T. Steinherz, N. Intrator and E. Rivlin, Skew detection via principal component analysis, Proc. Intl. Conf. on Document Analysis and Recognition, 153 - 156, 1999.

16. S. Uchida, M. Sakai, M. Iwamura, S. Omachi and K. Kise, Skew estimation by instances, Proc. Intl. Workshop Document Analysis Systems, 201 - 208, 2008.

17. T. Vasudev, G. Hcmanthkumar and P. Nagabhushan, Transformation of arc-form-text to linear-form-text suitable for OCR, Pattern Recognition Letters, 28, 2343 - 2351, 2007.

18. B.Y. Yu and A.K. Jain, A fast and robust skew detection algorithm for generic documents, Pattern Recognition, 29(10), 1599 - 1629, 1996.

19. Z. Zhang and C.L. Tan, Correcting document image warping based on regression of curved textlines, Proc. Int. Conf. Document Analysis and Recognition, 1, 589 - 593, 2003.

The present disclosure is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects. Many modifications and variations can be made without departing from its spirit and scope, as will be apparent to those skilled in the art. Functionally equivalent methods and devices within the scope of the disclosure, in addition to those enumerated herein, will be apparent to those skilled in the art from the foregoing descriptions. Such modifications and variations are intended to fall within the scope of the appended claims. The present disclosure is to be limited only by the terms of the appended claims, along with the full scope of equivalents to which such claims are entitled. It is also to be understood that the terminology used herein is for the purpose of describing particular embodiments only, and is not intended to be limiting.

With respect to the use of any plural and/or singular terms herein, those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.

In addition, where features or aspects of the disclosure are described in terms of Markush groups, those skilled in the art will recognize that the disclosure is also thereby described in terms of any individual member or subgroup of members of the Markush group.

While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.

We claim

1. A method of extracting and aligning curvilinear text from a captured image comprising acts of:

a. receiving a binary image as an input;

b. performing connected component (CC) labelling on the binary image for obtaining a set of disjoint components;

c. determining the local orientation of the text line by estimating angle between the centroids of a CC and its nearest neighbour CCnn;

d. obtaining one or more text strings by repeating step c for all the CCs and grouping successive neighbours that satisfy the criteria of proximity and size regularity; and

e. fitting a spline curve to the centroids of the CCs of each identified text string and aligning the text string using vectors normal to the fitted spline curve.

2. The method as claimed in claim 1, wherein the image captured is either camera captured or scanned.

3. The method as claimed in claim 2, wherein the text of the image captured is selected from any one of an arc, wave, triangular, curve and any combination of the above with linear skew.

4. The method as claimed in claim 1, wherein the receiving of a binary image is input using an adaptive binary technique.

5. The method as claimed in claim 1, wherein the spline curve is a B-spline curve.

6. The method as claimed in claim 1, wherein the text lines are aligned vertically for the estimated angle in the range 45° and 135° or 225° and 315°.

7. The method as claimed in claim 1, wherein the output image is generated by stacking the rotated characters in a left to right direction.

8. The method as claimed in claim 7, wherein the output image is a text line with proportionate spacing between the characters.

9. The method as claimed in claim 1, wherein the extracting and aligning curvilinear text from a captured image relies only on the curvature of the text string and independent of the script.

10. The method as claimed in claim 1, wherein the extracting and aligning curvilinear text from a captured image is applicable for any script in which the arrangement of the characters in a text string exhibits a degree of regularity.

11. A system to extract and align text of an image captured comprising:

a. an input block to receive a binary image;

b. connected component (CC) block to perform connected component labeling on the binary image to obtain a set of disjoint components;

c. an identifying block to obtain text lines by grouping adjacent CC based on the proximity and regularity; and

d. text alignment block to align the identified text lines and generate an output image.

12. The system as claimed in claim 11, wherein the input block receives the binary image using an adaptive binary technique.

13. The system as claimed in claim 11, wherein the input image is selected from at least one of camera captured image or scanned image.

14. The system as claimed in claim 11, wherein the extracting and aligning curvilinear text from a captured image is applicable for any script in which the arrangement of the characters in a text string exhibits a degree of regularity.