CN102084378B - Camera-based document imaging - Google Patents

Abstract

Processes and systems for converting digital photographs of text documents into scan quality images are disclosed. A grid representing deformations in the image is constructed on the image by extracting the document text from the image and analyzing visual cues from the text. The image is transformed to straighten such a grid, thereby removing the distortions introduced by the camera image capture process. Variations in illumination, extraction of text line information, and modeling of curved lines in the image may all be corrected.

Description

Camera-based document imaging

Cross References to Related Applications

This patent application claims priority under 35 U.S.C. 119(e) to U.S. Provisional Application No. 61/126,781, filed May 6, 2008, and U.S. Provisional Application No. 61/126,779, filed May 6, 2008 , both applications are hereby incorporated by reference.

technical field

This application relates generally to digital image processing, and more particularly to processing images captured by cameras.

Background technique

Document management systems are becoming more and more popular. Such a system eases the burden of storing and processing large document databases. Many institutions store large amounts of information in physical documents that they want to convert into digital format for ease of management. Currently, a combination of optical scanning and optical character recognition (OCR) technologies, such as those embodied in ABBYY-FineReaderPro 8.0, convert these documents into electronic form. However, this process can be inconvenient, especially for media forms such as bound books or posters, which are difficult to scan quickly and accurately. Also, the process of preparing documents and then scanning them can be slow.

Storing images that are aesthetically pleasing and contain only minor distortions is preferable. When images contain severe distortions, the effects of the distortions make those images more difficult to read. Furthermore, OCR assumes that the input image contains no distortions. For purposes of this application, a document image without significant distortion is referred to herein as an "ideal image".

In many cases, modern digital cameras have the potential to improve the digitization process. Cameras are usually smaller and easier to handle than scanners. Also, the document does not require much preparation before being captured by the camera. For example, posters or signs can be left on the walls. The downside of this flexibility is that it introduces imperfections into the image. Photos captured by the camera may be distorted in ways that do not exist for the scanned image. The most obvious effects are distortions due to perspective, camera lenses, uneven lighting conditions, and physically curled documents. Current OCR techniques expect their input to come from a scanner and therefore do not perform the necessary pre-processing to deal with the above-mentioned distortions in the captured document image. OCR technology is a key part of processing images in document management software, so the distortion introduced by cameras when capturing document images makes current cameras not a satisfactory replacement for scanners. Therefore, dewarping the document image captured by the camera and removing the distortion is a necessary process in the transition from the scanner to the camera.

Most research on image correction focuses on specific types of curling. One way to flatten an arbitrarily curled document is to project a photo into a 3D grid that approximates the surface of the original document. (See "Image restoration of arbitrarily warped documents" by Michael S. Brown and W. Brent Seales, pp. 1295-1306, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10).) The flattening algorithm A lattice is modeled as a collection of mass points connected by springs and affected by gravity. The algorithm attempts to minimize the stretching of the surface by fitting the spring to a state of minimum potential energy. Although this approach has proven successful, it relies on physical modeling of time steps. The experimental run time for this algorithm is on the order of minutes, which is too slow. Furthermore, the algorithm assumes that it has an accurate 3D surface representing the document, which would have to be reconstructed from information extracted from the 2D image.

One method of unfolding an image without prior knowledge of the document's surface is to build a grid over the image based on information gleaned from lines of text within the document. (See "Document flattening through grid modeling and regularization" by Shijian Lu and Chew Lim Tan, Proceedings of the 18th International Conference on Pattern Recognition Issue 1, 2006, pp. 971-974.) This approach assumes that in the original document The rows are straight and evenly spaced, and the curvature in each grid cell is approximately constant. Each grid cell represents a square of the same size in the original document. In a warped image, the top and bottom sides of the cell should be parallel to the tangent vector, and the left and right sides of the cell should be parallel to the normal vector. Each quadrilateral cell is mapped into a square using a linear transformation, effectively unfolding the document. In some cases, this approach lacks the information needed to determine the alignment and spacing of vertical cell boundaries. Some have attempted to obtain this information using "vertical stroke analysis," which focuses on straight-line segments of individual characters as markers of the vertical orientation of the text. (See "Perspective rectification of document images using fuzzy set and morphological operations" written by ShijianLu Chen, Ben M.Chen and C.C.Ko on pages 541-553 of Image and Vision Computing No. 24 in 2005.)

In order to create continuous, smooth transitions without utilizing an intermediate grid structure, another approach models the page as a developable surface. (See "Unwarping Images of Curved Documents Using Global Shape Optimization" by Jian Liang, Daniel DeMenthon, and David Doermann, pp. 25-29, Pro. First International Workshop on Camera-based Document Analysis and Recognition, 2005.) Extensible surfaces are The result of curling a flat surface without stretching it. This approach attempts to find surface rulings by analyzing text. A scribe is a line that is straight along a surface until the plane is curled. The inverse transform unwraps the surface by correcting the scribe lines.

However, none of these methods have been found to be entirely satisfactory for developing documents captured with digital cameras.

Contents of the invention

It is an object of the present invention to solve, or at least ameliorate, one or more of the above-mentioned problems associated with digital images. Accordingly, there is provided a method for processing a photographic image of a document containing lines of text comprising text characters having vertical strokes. The method consists of analyzing the position and shape of lines of text and straightening them into a regular grid in order to expand the image of the document image. In one embodiment, the method includes three main steps: (1) text detection, (2) shape and orientation detection, and (3) image transformation.

The text detection step finds the pixels in the image that correspond to text and creates a binary image containing only those pixels. This process addresses unpredictable lighting conditions by identifying local background light intensities. Text pixels are grouped into character regions, and characters are grouped into text lines.

The shape and orientation detection step identifies typographic features and determines the orientation of the text. The extracted features are the points in the text corresponding to the top and bottom of the text characters (endpoints) and the angles of vertical lines in the text (vertical strokes). Also, curves are fitted to the top and bottom of the text lines to approximate the original document shape.

The image transformation step relies on a raster building process where the extracted features are used as a basis for identifying document curls. Generates a vector field representing the horizontal and vertical stretch of the document at each point. Alternatively, an optimization problem based approach can be used.

Further aspects, objects and desired features and advantages of the present invention will become better understood from the following description considered in connection with the accompanying drawings, in which various embodiments of the disclosed invention are illustrated by way of example. It should be expressly understood, however, that the drawings are by way of illustration only and not as a definition of the limits of the invention.

Description of drawings

FIG. 1 is a flowchart illustrating steps of camera-based document image development processing.

FIG. 2 illustrates a photograph including an example image of a document containing lines of text.

FIG. 3 illustrates the output image of the photo of FIG. 2 after binarization of the image of FIG. 2 using simple thresholding.

Figure 4 illustrates the output image of the photograph of Figure 2 after binarization with Retinex-type normalization followed by thresholding.

Figure 5 illustrates a grayscale image of an extremely curled document containing lines of text and other documents created from photographs of the document.

FIG. 6 illustrates an output image after filtering processing is performed on the image of FIG. 5 .

FIG. 7 illustrates an output image after rough thresholding is performed on the output image of FIG. 6 .

FIG. 8 illustrates the output image after performing a process on the output image of FIG. 6 in which the foreground (the area initially identified as text) is removed and empty pixels are inserted.

FIG. 9 illustrates the output image after performing a full binarization process on the image of FIG. 5 .

FIG. 10 is a diagram illustrating various features in English typesetting.

Figure 11 illustrates a photographic image of a document with lines of text, where control points have been marked as dark and light points.

FIG. 12 illustrates an output image after performing an optimization-based expansion process on the image of FIG. 11 .

Figure 13 depicts one embodiment of a system for processing captured images.

Figure 14 is a flowchart illustrating the steps of an alternative embodiment of camera-based document image expansion processing.

15 is a flowchart illustrating the steps of another embodiment of camera-based document image expansion processing.

Detailed ways

Embodiments of the present invention will now be described with reference to the accompanying drawings. For ease of description, any reference number representing an element in one figure will represent the same element in any other figure. FIG. 1 is a flowchart illustrating the steps of a camera-based document image development process according to one embodiment of the present invention.

Referring to FIG. 1 , a method 100 for developing a document image captured by a camera is provided. Method 100 involves analyzing the position and shape of lines of text included in an imaged document and then straightening them into a regular grid. In the illustrated embodiment, method 100 includes three main steps: (1) text detection step 102 , (2) shape and orientation detection step 104 , and (3) image transformation step 106 . Each major step may further include several sub-steps, as described below.

1. Text detection

The text detection step 102 finds the pixels in the image that correspond to the text and creates a binary image that only contains the pixels. In this embodiment, the text detection step 102 addresses unpredictable lighting conditions by identifying local background light intensities. In this embodiment, in order to properly recognize text, five sub-steps are performed in the text detection step 102 . These sub-steps are a binarization step 110 , a text region detection step 112 , a text line grouping step 114 , a centroid spline calculation step 116 and a noise removal step 118 . In other embodiments, different sub-steps may be used, or their order may be varied.

1.1 Dualization

Binarization 110 is the process of identifying pixels in an image that make up text, thereby separating the image into text and non-text pixels. The purpose of binarization is to localize text and eliminate irrelevant information by extracting useful information about the shape of the document from the image. This processing takes as input a raw color image. Its output is a binary matrix of the same dimensions as the original image, where zeros represent the location of the text in the input image and ones represent anywhere else. In other implementations, this can be reversed. The binarization process preferably involves (a) pixel normalization, (b) thresholding and (c) artifact removal, each of which will be described in more detail below.

a. Pixel normalization

In general, text pixels are darker than their surroundings. Simple or crude binarization techniques generally take a specific threshold and assume that all pixels on an image that are brighter than the threshold are white and all pixels that are darker than the threshold are black. While this technique works well for scanned documents, a single global threshold will not work well for the variety of images captured by photographing documents due to differences in lighting and font weight. FIG. 2 illustrates a photograph including an example image 202 of a document, where the document contains lines of text and has poor imaging quality. Note that the illumination is darker in the upper right region 204 of the image 202 compared to the rest of the image 202 due to the curling of the original document. FIG. 3 illustrates an output image 206 of the photograph of FIG. 2 after binarizing the image 202 of FIG. 2 using simple thresholding. Note that the entire upper right region 208 of the image 202 is considered a text region.

To account for this variation in intensity, in one embodiment, a normalization operation may be performed on each pixel based on its relative intensity compared to its surroundings. In this regard, the method from Retinex can be used. (See "Retinex image processing" by Glenn Woodell, http://dragon.larc.nasa.gov/, 2007.) According to Retinex, the original image is divided into blocks large enough to contain a few text characters, but Small enough to have more consistent lighting than the page as a whole. Since, in a general document, there are usually fewer text pixels than background pixels, the median value in a block will be approximately the intensity value of the background page in a particular block. Each pixel value can then be divided by the median of the block to obtain a normalized value.

It should be understood that the size of the blocks can be adjusted and that a variety of block sizes can be used. For example, if the size of the block is too large, the median of the block may not accurately represent the background due to uneven lighting on the page. On the other hand, if the block size is too small compared to the size of the text characters, the median will incorrectly represent the text intensity instead of the background intensity. Also, due to varying conditions on a document page, a single block size may not fit the entire image. For example, text characters in titles are often large and thus require larger block sizes.

One process for determining the appropriate block size to use is by taking the entire image and dividing it into many very small blocks. The blocks are then reassembled step by step. At each level of reassembly, it is evaluated whether the current block is large enough to be used. Recomposition processing can stop at various points on the page. Whether the block size is "big enough" may be based on additional heuristics. For example, since a non-zero Laplacian has a very high correlation with the position of text in a document, a discrete second derivative or application of the Laplacian can be applied to the input image. Therefore, dimensioning the block to contain a certain amount of summed Laplacian ensures that the block is large enough to contain a few text characters.

It should be appreciated that the methods described above for determining whether a block is large enough to be normalized can be fine-tuned for a particular application (eg, camera type, document type, lighting, etc.).

b. Thresholding

As mentioned earlier, when pixels are normalized with respect to the background paper color, the pixels on the background will have a normalized value of about one, while the pixels on the text will have a much lower normalized value. Therefore, this comparison will not be affected by the absolute lightness or darkness of the image. Since the normalization operation on a pixel can be performed by exploiting only its local environment, it is also independent of local variations in lighting across pages.

To differentiate between white and black values, choose a threshold. However, since the intensity features of individual images are already filtered out by normalization as described above, a single threshold works consistently for most images. Also, because the normalized background has pixel values around one, in one embodiment, a threshold value slightly below one is chosen, such as 0.90 or 0.95. In other embodiments, it is contemplated that other suitable thresholds may be used, and that different blocks may use different values.

FIG. 4 illustrates an output image obtained when thresholding according to the present invention is performed on the non-ideal image illustrated in FIG. 2 after binarization with local normalization. When compared to the results of simple binarization illustrated in Figure 3, a significant improvement can be observed. In FIG. 4 , the text line 212 in the upper right area can now be distinguished from the background 214 .

c. Artifact removal

As shown in FIG. 4, in many cases, there will be artifacts or noise in the image after thresholding. The purpose of this stage is to identify and remove false positives or noise. For example, the edges of paper tend to be thin and dark relative to their surroundings. There may also be noise in the background when a particular block does not contain text. Such noise (eg, including noise due to illumination aberrations) may be recognized as text. Therefore, additional post-processing is preferably employed to remove noise.

A process for removing noise separates black or text pixels in the binarized image into connected parts. Three criteria were used to discard non-text connected regions. The first two criteria are used to check whether a region is "too big" or "too small" in terms of the number of pixels. The third criterion is based on the observation that a region is likely to be noisy if it consists entirely of pixels close to the first threshold. Actual text characters or glyphs may have some borderline pixels, but most of them should be much darker. Therefore, the average normalized value of the whole region can be checked, and regions whose average normalized value is too high should be removed. These criteria introduce three parameters: a minimum region area, a maximum region area and a threshold for region-wise average pixel values. Region-wise thresholds should be lower (stricter) than pixel-wise thresholds to have the desired effect on noise removal.

In the pixel normalization step of the binarization process described above, an estimate of the background paper color is made, then, if a pixel is much darker than that color, the pixel is identified as text and the image is divided into blocks, Assume the median color in each block as its background paper color. This method works well provided the previously mentioned parameters are well chosen. However, the parameters that make up a good choice sometimes vary drastically from one image to another, or even from one part of an image to another. To avoid these problems, the optional binarization described below can be employed.

Optionally, in this embodiment, the binarization step 110 can be performed by performing the following preferred steps. First, the foreground is roughly estimated by a rough thresholding method. The parameters for this coarse thresholding are chosen such that we rather identify too many pixels as text. These foreground pixels are then removed from the original image according to the chosen threshold. Holes left by the removal of foreground pixels are then filled by interpolating from the remaining values. This provides a new estimate of the background by removing the initial threshold and interpolating over the holes. Finally, thresholding can now be performed based on an improved estimate of the background. This process works well even when given uneven lighting conditions on photographic documents. A more detailed description of how this preferred binarization step 110 is performed is provided below.

First, a photograph of a document including lines of text is converted into a grayscale image 216, as shown in FIG. Grayscale image 216 includes an example image of a document containing lines of text, with an extremely curled main document 218 shown along with other documents 220 . In one embodiment, the conversion to gray scale can be achieved by using the rgb2gray function of Matlab.

Second, the image is preprocessed to reduce noise, thereby smoothing the captured image. In one embodiment, smoothing can be performed by using a Wiener filter, where the Wiener filter is a low pass filter. An image 222 shown in FIG. 6 illustrates an output image after filtering processing is performed on the image of FIG. 5 . Although the image 222 shown in FIG. 6 looks just like its input image 216 shown in FIG. 5, the filter does a good job of removing salt and pepper noise. The Wiener filter can be performed, for example, using Matlab's weiner2 function with a 3x3 neighborhood.

Third, the foreground is estimated by using simple or coarse thresholding. In this embodiment, the method attributed to Sauvola calculates the mean and standard deviation of the pixel values in the neighborhood for each pixel and uses this data to decide whether each pixel is dark enough to resemble text. (See "Adaptive Document Image Binarization" by J. Sauvola and M. Pietikainen, Pattern Recognition, Vol. 33, pp. 225-236, 2000, which is hereby incorporated by reference.) Fig. The output image 224 of the output image 222 after performing rough thresholding. In other embodiments, methods such as Niblack may also be used. (See "An Introduction to Digital Image Processing" by Wayne Niblack, Section 5.1, Prentice Hall International, 1985, pp. 113-117, which is hereby incorporated by reference.)

In areas like the top of page 226 (where the standard deviation is very small), the output is mostly noise. This is one reason why window size matters. Noise also occurs when the contrast is significant, such as around the edge 228 of the paper. However, the presence of noise artifacts is unimportant since noise artifacts can be removed at a later stage. In this example, a large number of false positives was chosen rather than false negatives because the following steps work best without false negatives.

Fourth, the background can be found by first removing the foreground (areas initially identified as text) by initial thresholding and then interpolating over the holes caused by the foreground removal. For those pixels identified as text by initial thresholding, their color values are replaced by interpolating the color values of neighboring pixels to approximate the background, as shown in image 230 in FIG. 8 . FIG. 8 illustrates the output image 230 after performing a process on the output image 224 of FIG. 7 in which the foreground has been removed and null pixels have been inserted. This image 230 may contain noise from text artifacts, since some darker pixels surrounding the text may not have been identified as text in the initial thresholding step. This effect is another reason to use a larger superset of the foreground in the initial thresholding step when estimating the background.

Finally, thresholding is performed based on the estimated background image 230 in FIG. 8 . In one embodiment, the comparison between the preprocessed output image 224 of FIG. 7 and the background image 230 of FIG. 8 is performed by Gatos' method. (See "Adaptive Degraded Document Image Binarization" by B. Gatos, I. Pratikakis, and S.J. Perantonis, Pattern Recognition, Vol. 39, pp. 317-327, 2006, which is hereby incorporated by reference.) Figure 9 illustrates The output image 240 after performing a full binarization process on the image 216 of FIG. 5 is shown. In FIG. 9 , text region 242 is well recognized from its background 244 even in an extremely curled region near edge 246 of master document 248 .

At a later stage, post-processing can be performed. Thresholding can be applied to the largest and smallest areas, and can remove common instances of noise (eg, large dark lines 250 around the edges of the main document 248).

Thus, the binarization step 110 previously described with respect to FIGS. Image 240, where the text area is distinguishable from its background.

1.2 Text area detection

After extracting the position of text pixels in the image, useful features of the original document can be identified, especially local horizontal and vertical text orientations. Then, a vector field can be built to model the text flow of a document. It should be noted that in images, horizontal and vertical data are separated. Although these directions are orthogonal in the source document, the perspective transformation decouples them. These orientations at locations with clear text features can be identified, and orientations across pages can be interpolated to describe the surface of the entire document.

Referring to FIG. 10 , languages using Latin character sets have a large number of characters including one or more long, straight, vertical lines called vertical strokes 260 . There are relatively few diagonal lines of similar length, and they often have significant angles to adjacent vertical strokes. This regularity makes vertical strokes an ideal text feature to obtain information about the vertical orientation of the page.

To find the horizontal orientation of a page, a set of parallel horizontal lines in a single line of text, called rulings, can be used. Unlike vertical strokes 260, these strokes themselves are not visible in the source document. Generally, the top and bottom of the characters fall on two main lines called x-height 262 and baseline 264 . The x-height 262 and baseline 264 dashes define the top and bottom of the text character x, respectively. In some text characters, a portion of the text character extends beyond the height of the text character x, like d and h, called ascenders 266 . A descender 268, on the other hand, refers to a portion of a text character that extends below the bottom of a text character x, like a y or q. In this embodiment, x-height 262 and baseline 264 are used as local maxima and minima (endpoints) for the character region. These endpoints are the "highest" and "lowest" pixels in the character region, where the directions for high and low are determined from a rough spline through the centroid of each character region in the text line. These endpoints are then used in the curve fitting process, which is described in a separate section.

Two pixels are connected if they have the same color, are adjacent to each other and share a common side. A pixel region is a group of connected black pixels. In this patent document, the terms "connected portion", "connected region" or just "character region" are all used interchangeably.

A properly binarized image should consist of a set of connected regions, each of which is assumed to correspond to a single text character that can be rotated or skewed without significant local curvature. The text region detection step 112 organizes all pixels identified as text pixels in the previous binarization step into connected pixel regions. In cases where the binarization step is successful—the binarized image has low noise and the text characters are well decomposed—each text character should be recognized as a connected region. However, there are cases where groups of text characters are marked as contiguous regions.

In this embodiment, Matlab's built-in region search algorithm (this algorithm is a standard breadth-first search algorithm) can be used to implement the text region detection step 112 and identify character regions.

1.3 Text line grouping

The text line grouping step 114 is used to group character regions in the image into text lines. The estimation of the text orientation is based on the local projected contours of the binary image and the available text orientations produced in the grouping process. Priority is given to groups with characters on the same line. Groups are allowed to reform when better possibilities are found. In other words, characters can be grouped into text lines using a guess-and-check algorithm that groups regions based on proximity and overwrites previous groups based on linearity. For each text line, an initial estimate of the local orientation is found by fitting a rough polynomial through the character centroids. Polynomial fitting preferably emphasizes performance over accuracy, since subsequent steps require this estimate, but do not need it to be very accurate. The tangent of the polynomial fit is used for the initial horizontal orientation estimate, and the initial vertical orientation is assumed to be preferably orthogonal.

1.4 Centroid spline calculation

In the centroid spline calculation step 116, the position of the "centroid" of each character region of the text line is calculated. In this embodiment, the centroid is the average value of the coordinates of each pixel in the character area. Then, compute a spline through these centroid coordinates.

1.5 Noise removal

After grouping character regions into text lines, the calculated positions of the splines can be used to determine which text lines do not correspond to real text. These are groupings of character regions consisting of extraneous pixels from background noise outside the page boundaries that do not correspond to true text lines. In this embodiment, noise is removed on a photo/column basis in this noise removal step 118 .

Because text can be grouped into paragraphs, regions corresponding to paragraphs can be identified. Therefore, splines representing lines of text that do not intersect paragraph regions may be treated as noise rather than true lines of text and should therefore be removed.

In order to identify a region corresponding to a paragraph, it may be assumed that in a paragraph a line of text is parallel to an immediately above or below a line of text, and that these lines of text have approximately the same shape and size. Additionally, it can also be assumed that the vertical distance between lines of text is constant.

Therefore, polygonal regions containing paragraphs can be identified by using dilate and erode filters. Dilation filters expand the boundaries of pixel regions, while erosion filters shrink the boundaries of pixel regions. These filters use different structural elements to define precisely how the filter affects the boundaries of the region. Circles can be used as structural elements, expanding and contracting areas by the radius of the circle.

In this embodiment, the noise removal step 118 is preferably performed in the following order. First, the structuring element is sized based on the distance between lines of text. By extending the text line distance, regions can be formed such that each pair of adjacent text lines is contained within a single region, effectively placing paragraphs within a region. Next, an erosion filter can be employed to double the text line distance to eliminate thin or distant regions from the main paragraph. A dilation filter can then be used to ensure that the remaining regions surround the corresponding paragraphs. Next, all regions whose area is smaller than a predetermined factor of the largest region's area can be discarded in order to remove the remaining noisy regions. In one embodiment, the predetermined factor is one quarter. Once the regions containing paragraphs are identified, all splines that do not intersect these regions can be removed, thus leaving only slice lines corresponding to true text lines.

While the removal process described above may occasionally remove valid lines of text (eg, headings and footers), paragraphs should contain enough information about the shape of the page for further processing.

2. Shape and orientation detection

The shape and orientation detection step 104 identifies typographic features and determines the orientation of the text. The identified features are the points in the text corresponding to the tops and bottoms of the text characters (endpoints) and the angles of vertical lines (vertical strokes) in the text. These characteristics may not be present in every single character. For example, a capital O has neither a vertical stroke nor an x-height endpoint. Also, curves are fitted to the top and bottom of the lines of text to approximate the original document shape.

In this embodiment, five sub-steps are performed in the shape and orientation detection step 104 . These sub-steps are endpoint detection step 120 , spline fitting step 122 , page orientation detection step 124 , outliner removal and vertical paragraph boundary determination step 126 and vertical stroke detection step 128 .

2.1 Endpoint detection

As mentioned earlier, the endpoints of a character are the top and bottom features in the character such that they are local minima or maxima in the identified character region. They tend to fall on the horizontal dashes of lines of text. In this embodiment, the endpoint detection step 120 is used to find out the horizontal orientation in the text document, since endpoints are well-defined features in character regions. Endpoints can be identified per character from thresholded character regions and centroid splines of text lines.

In order to find the local maxima and minima in the identified character regions, an orientation with respect to the character region is defined with respect to the orientation in which the maxima and minima are found. This orientation can be approximated by the angle of the spline through the character's centroid. This approximation suffers from high error because the endpoints in the character region are robust with respect to the chosen original orientation. For endpoints at the top and bottom of a vertical stroke, as much as 90° of character orientation error is required to misidentify the endpoints. If the character orientation has an error of as much as 40°, the endpoints at the top of the diagonal strokes can still be accurately identified. Endpoints at the top of a curve character (eg, the text character "o") are more sensitive to errors in orientation, since even a small error of a few degrees can place the endpoints in a different position on the curve. However, this error does not change the height of the identified endpoints by more than a few pixels.

The approximate orientation should be known before the endpoint is found. A change of coordinates can be performed on each region's pixels, where the new y-coordinate y' is given by the orientation, and the new x-coordinate x' is orthogonal to the y' direction. This can be achieved by applying a rotation matrix to the list of pixel coordinates. In other words, the new pixel coordinates are represented by floating-point numbers as opposed to the original integer coordinates. The x' coordinate can be rounded to the nearest integer in order to group pixels into columns in rotated space.

In order to find the global extrema in the character region, the pixel with the largest or smallest y' coordinate should be identified. A significantly larger portion of the global extrema falls on the cap height line 270 as shown in FIG. 10 , making it difficult to accurately distinguish any one dash if only the global extrema is considered. On the other hand, finding local extrema in character regions usually yields better results. Most of the local maxima are on the x-height dash, making the dash easy to find.

To separate the top endpoint from the bottom endpoint, the character region can first be split in half along the centroid spline. Only points above this centroid spline are likely to be local maxima lying on the x-height dash. And only points below this centroid spline are likely to be local minima lying on the baseline dash. In each half, local extrema are identified by an iterative process that selects the current global extrema and removes nearby pixels, as described in more detail in the next paragraph.

Starting from the identified endpoint, the iterative process finds the highest pixel in two adjacent columns of pixels that is not higher than the endpoint itself, and then deletes everything else in the endpoint column. Then, iterate over the pixels in an adjacent column, using the top of that column as the other endpoint for removal. In this way, pixels from characters in the character heading direction can be removed, thereby preserving other local extrema. The process is then repeated, using new global extrema as new endpoints in smaller sets of pixels.

2.2 Spline fitting

In a spline fitting step 122, splines are fitted to the top and bottom of the text line. After obtaining the endpoints as described in the previous section, the endpoints can be filtered and splines can be fitted to the endpoints. Splines are used to model the baseline 264 and x-height 262 strokes of each text line to indicate localized curling of the document.

Splines can be used to smoothly approximate data in a manner similar to higher-order polynomials, while avoiding problems associated with polynomials, such as the Runge phenomenon. (See "Runge's Phenomenon" by Chris Maes at http://demonstrations.wolfram.com/RungesPhenomenon, 2007, which is hereby incorporated by reference.) In this example, the spline is a piecewise cubic polynomial , with continuous derivatives at the coordinates where the polynomial segments meet. In this embodiment, if it is desired to reduce the fitting error, it is necessary to increase the number of polynomial segments instead of increasing the degree of the polynomial.

In this embodiment, an approximation spline passing near the endpoints rather than passing through the endpoints is employed.

An example of a spline is a linear spline (degree two). In linear splines, straight line segments are used to approximate the data. However, this linear spline lacks smoothness because the slope is discontinuous where the segments join. Higher degree splines can fix this problem by implementing continuous derivatives. A cubic spline S(x) of degree 3 with n segments can be represented by a set of polynomials {S _j (x)} defined over n consecutive intervals Ij:

where a _i,j are the coefficients chosen to ensure that the spline has continuous derivatives across the interval.

In this embodiment, spline fitting solves the problems of speed and accuracy by performing the processing described below. First, identify the orientation of the document by knowing that outliers occur mostly in the upper half of the text line when the text uses the Latin character set. Knowing this orientation makes it possible to fit splines to the bottom and top of the text line using different algorithms.

In this example, a median filter is applied to the bottom endpoint in order to reduce the influence of outliers. A small window is used for the filter because there are fewer outliers in the lower half of the text line, and those outliers do not tend to be clustered together in English text. The splines fitted to this new filtered data set are called bottom splines. Next, filter the top endpoints using distance from the bottom spline and a median filter with a large window size. This reduces the effect of large outliers on the top of the text line and ensures that the top and bottom splines are locally parallel.

Before fitting the spline, the top and bottom endpoints were filtered by utilizing a median filter, as previously described.

Regarding the filtering of the bottom endpoints, in this embodiment, the bottom endpoints are filtered using a median filter with a small window size w. In this embodiment, w is set to 3. Points are sorted by their x-coordinate value. Then, the y-coordinate value of each bottom endpoint is replaced by the median of the y-coordinates of neighboring points. For most points, there are 2w+1 neighbors, including the point itself. This is found by taking w points to the left of that endpoint and w points to the right of that endpoint in the sorted list. The first and last endpoints are discarded because they have no neighbors on one side. Other endpoints that are less than the window size from either end of the list should have their window size changed to that distance. This ensures that at any given endpoint, there will always be an equal number of points on the left and right for calculating the median. Choosing 2w+1 points (an odd number) also has the advantage that the median of the y-coordinate values will always be an integer.

Regarding the filtering of the top endpoint, in this embodiment, a different method is used than the filtering of the bottom endpoint. Because the English text contains more outliers in the top endpoint data. Consider the distance between the y-coordinate of the top endpoint corresponding to the x-coordinate and the bottom spline. Because bottom splines are generally robust, these distances should be locally constant for non-outlier data in large neighborhoods. Therefore, to remove outliers, a median filter with a large window size is applied to these distances. The y-coordinate of each top endpoint is replaced by the sum of the median distance at that point and the y-value of the bottom spline at the corresponding x-coordinate.

Once the top and bottom endpoints are filtered, two splines can be fitted to each text line. In this example, a bottom spline is fitted to the filtered bottom endpoint data set and a top spline is fitted to the filtered top endpoint data set. For both purposes, the same approximation spline is used. All points can be equally weighted, the spline can be cubic (degree 4), and the number of spline segments is determined by the number of character regions in the text line. In general, each character region corresponds to a text character. In some cases, several text characters or a single word can be blurred together into one region. In one embodiment, the number of spline segments is set to be the upper limit of the character area divided by 5, the minimum required being two segments.

The splines used for each text line are found independently of other text lines. However, information from adjacent lines of text can be used to make splines more consistent with respect to each other. This information can also be used to find errors in lines of text when the line found spans multiple lines of text.

The top spline used to determine local document curl can be ignored, as the data from the bottom spline is usually sufficient to unwrap the document accurately. This is because the text line has several consecutive uppercase text characters at the beginning or end of the text line which can contribute a large number of endpoints above the x-height line 262 which will not be considered outliers by the median filter remove. As a result, the spline will incorrectly curve upwards to fit the tops of uppercase text characters. However, computing the top spline is still preferred because the top spline gives other useful information about the text line height.

2.3 Page Orientation Determination

There are four possible orientations for a document: East (0°), North (90°), West (180°) or South (270°). This is the general direction the arrow drawn upwards in the original document points in the image. The number of horizontal splines is compared to the number of vertical splines to determine if the orientation is North/South or East/West. Since the top and bottom splines are different, it is necessary to distinguish between north and south or east and west in order to know which half of the text line is the upper half. This can be achieved by exploiting the observation that in English and other languages that use Latin character sets, the upper half of a text line is larger than the lower half because uppercase text characters, numbers, punctuation, and more have ascenders rather than descenders There are more outliers.

Therefore, in order to distinguish the top from the bottom of the document, in this embodiment, a representative sample of text lines whose length is close to the median length of all text lines is selected. For each line of text in the sample, the top is found by checking which side has more outliers. This can be done by applying the bottom spline fitting algorithm to both the top and bottom endpoint sets and measuring the error in these fits. In one embodiment, an orientation is determined when the number of lines of text producing equivalent orientations is at least 5% of all lines of text in the document and exceeds the number of lines of text producing alternative orientations by at least two. This ensures that orientation detection is accurate 99% of the time.

Regarding text line selection, a typical document contains 100 to 200 text lines. Therefore, ideally, only very few samples are used towards the computational step, which is significantly slower than conventional spline fitting. Typically, 5 to 10 lines of text are required to conclusively determine orientation, but this number can vary due to the "win by two" criterion. In this embodiment, in order to reduce the number of errors due to noise, the text lines are first sorted according to their length. Lines of text that are too short or too long are more likely to be noise, and long lines of text tend to give more accurate results than short lines of text. The average and median lengths of all text lines are calculated, and the maximum of these two numbers is considered the optimal line length. All text lines are then sorted according to the difference between their lengths and the optimal line length. Therefore, reasonable text line lengths are considered before outliers.

Regarding the error measure, after a spline is fitted to the top and bottom of each text line, the errors of the two fits can be compared. The error of the fit is calculated by considering the error at each endpoint. The error at an endpoint is the difference between the y-coordinate of that endpoint and the value of the spline function at the corresponding x-coordinate. These point-wise errors can be summed and scaled by the number of endpoints used to calculate the fit error.

Since the assumption that the top spline has more outliers comes from the assumption that the characters are Latin letters, this method may need to be modified for other character sets. Thus, a threshold is set on how much difference in fit error needs to be in order to derive the orientation of the text line. This threshold ensures that assumptions about text orientation are not incorrectly made when the orientation cannot be correctly determined. If the threshold is not met, the text is considered right up or rotated 90° clockwise. Once the orientation can be determined, the unwrapping step can be used to correctly rotate the image.

The parameters selected for the implementation of this embodiment are listed below: (1) The window size of the median filter for the bottom spline is set to 7. This value was chosen because approximately two endpoints can be found at each text character, so the window includes one text character to the right of the endpoint and one text character to the left of the endpoint. (2) The window size of the median filter used for the top spline is set to 21. This value is chosen to be much larger than the window size used for the bottom spline in order to allow stricter filtering of the top endpoints. (3) The number of spline segments in each line is set as the maximum number of character regions divided by 5, which requires at least two spline segments in each line. (4) The minimum number of regions in a valid text line is set to 5 to ensure that there are enough data points to define the spline.

2.4 Outlier removal and vertical paragraph boundary determination

The outlier removal and vertical paragraph boundary determination step 126 will now be described. At this point, connected text regions have been identified and grouped into possible text lines. For each possible text line, compute the centroid for each pixel-connected region. Then, an approximate orientation for each line of text is calculated. Lines of text whose orientation is very different from most other lines of text are discarded. Text lines that are much shorter than other text lines are also discarded. In one embodiment, the "clustercentroids" function of Matlab is used to implement the outlier removal process.

After eliminating erroneous text lines, the start and end points of each text line can be collected. The Hough transform can be used to determine whether the start of a line of text is aligned - if so, the line describing the left edge of the paragraph has been found. Similarly, if the end points of the lines of text are aligned, the paragraph is right-aligned and the right side of the paragraph is found. If these paragraph boundaries are found, they can be used in the final grid building step 132 to supplement the vertical stroke information (collected later in the algorithm). In the final grid building step 132, such paragraph boundary information is given more weight than vertical stroke information.

2.5 Vertical stroke detection

In this embodiment, the vertical stroke detection step 128 is performed by first intersecting the text pixel with the centroid spline of the text line. At each intersection point, a roughly vertical block of pixels is obtained by scanning along a local vertical direction. The local vertical orientation of each block can be estimated using a least squares linear fit. Then, the obtained set of pixels is filtered using a fitted quadratic polynomial, which facilitates the linearity and consistency of orientation among detected strokes. Outliers of the fitted polynomial can be removed without consideration. In one embodiment, outliers are removed by using a manually adjusted threshold of 10°. The result can then be smoothed by using an averaging filter.

Optionally, outliers can also be used to find vertical strokes, especially as camera resolution increases. It has been shown that larger pixel sets make it easier to analyze boundaries, rather than interiors. This is because larger sets of pixels have more well-defined boundaries, and the size of the interior grows faster than the size of the boundaries.

3. Image transformation

In this embodiment, two sub-steps are performed in this image transformation step 106 . These sub-steps are the interpolation creation step 130 and the grid creation and unwrapping step 132 .

In the grid building and unfolding step 132, the extracted features are used as the basis for identifying document curls. Generates a vector field representing the desired horizontal and vertical stretch of the document image at each point. Alternatively, the grid building and unfolding step 132 may be replaced by an optimization-based unfolding step 134 .

3.1 Interpolator Creation

In this interpolator creation step 130, an interpolator for vertical information is created from the vertical stroke and horizontal information from the top and bottom splines. In this embodiment, the unwrapping of the imaged document is performed by applying a two-dimensional warp to the imaged document. Warping is the local stretching of an imaged document in order to produce an image that looks like a flat document. How much the imaged document should be stretched can be locally determined from data from locally extracted features. These features may be 2D vectors in the imaging document fitted to one of two vector sets. The vectors of the first set are parallel to the direction of the text in the document, and the vectors of the second set are parallel to the direction of the vertical strokes in the text of the document. In a curl document for raw images, the vectors in these sets may point in any direction. It is desired to stretch the image such that these two sets of vectors become orthogonal, with all vectors in each set pointing in the same direction. Vectors parallel to lines of text should all point horizontally, and vectors parallel to vertical strokes should all point vertically.

Parallel vectors can be extracted by computing the unit tangent vectors of the text line splines at regularly spaced intervals. Also, the vertical strokes from each text line can be extracted by finding a set of parallel lines corresponding to dark lines in the text approximately orthogonal to the centroid samples of each text line. Each vertical stroke can be represented as a unit vector in the position and direction of the stroke. The angle of each vertical stroke can be estimated by using least squares linear regression. Here, the parallel vectors are called tangent vectors, and the perpendicular stroke vectors are called normal vectors. It should be noted that in the expanded document, the normal vector is orthogonal to the tangent vector. However, in the original image of the document, perspective distortion and page curvature make the angle between these vectors larger or smaller than 90°.

Basic interpolation processing is described below. The first step is to interpolate the tangent and normal vectors across the entire document. This is essential for determining how to expand parts of the image where there is no text or where the text does not provide useful information. A Java class can be used to store a known unit vector (x, y, θ). Once all known vectors have been collected for objects of this class, the angle θ of the unknown vector at a given location (x, y) can be calculated by taking the weighted average of the nearby known vectors in the (x, y) local neighborhood get. because , so this can be quite complicated. Since one angle at π-ε is very close to another angle at -π+ε (where ε is some very small number), ordinary interpolation techniques may not work well. The angles are calculated from the weighted average of the known vectors, where the weight of each known vector v is calculated using the following function.

$\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; e</span>}}^{\mathrm{<span\; class="notranslate">\; 10</span>}\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 5</span>}}}$

where r is the radius of the neighborhood and d is the distance between v and (x,y).

It should be noted that d<r, so w(d) becomes very small as d approaches r. As d approaches 0, w(d) becomes very close to 1. In this embodiment, the constants (10 and 5) in the equation are used to normalize the weight values between 0 and 1 in a smooth manner. These values can be changed in order to change the results. The parameter r determines the radius of the vector's influence. The parameter r can be set arbitrarily at 100 pixels. However, other numbers could be used, since if there are no vectors in the neighborhood, the search will continue beyond that neighborhood, assigning very low weight to any vectors found. The parameter r can be chosen arbitrarily, since the underlying data structure is a kd tree, which supports fast nearest neighbor searches. For more information on kd trees, see "K-d trees for Semidynamic Point Sets" by Jon Louis Bentley, Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990, pp. 187-197.

The basic interpolation process described previously works reasonably well for regions of the document where the number of extracted features is dense. However, when two dense regions are separated by a sparse region, abrupt changes rather than smooth interpolation can show through the sparse region. Fully smooth interpolation is not desired because it can lead to incorrect results when one document partially occludes another. On the other hand, discontinuities are also undesirable when all regions in question are part of the same document.

Therefore, utilizing an exponential function as the basis for the weight function may allow partial realization of this behavior. This limits the vector's influence on the default radius of the search neighborhood under normal conditions.

Interpolation also implements basic outlier removal. Once the interpolation object stores all known vectors, each vector is removed from the interpolation object, and the object is queried to obtain the interpolated value at that point. If the angle difference between the actual vector and the interpolated vector exceeds a certain threshold, the vector is not added back to the interpolated object. The threshold can be 1°, which ensures that all vectors used for unwrapping coincide with those surrounding it. Most of the errors in the vectors due to incorrect feature extraction are removed. This method can result in too smooth, because it blocks sudden changes in the vector.

A preferred embodiment of interpolation is described below. This interpolator creation step 130 is based on fitting a two-dimensional surface to a vector domain. Starting from a polynomial function of degree n, a least-squares error method is used to fit the surface to the horizontal and vertical vector domains. Due to the Runge phenomenon, these functions may oscillate at the edges of the image. This problem can be solved by replacing higher degree polynomials with two-dimensional cubic polynomial splines.

Regarding vertical interpolation, this information can be interpolated across images after finding some vertical strokes that represent a tangent to the vertical curvature of the document. In this embodiment, vertical interpolation is performed by constructing a smooth continuous function that best approximates the vertical data.

Regarding angles, vertical stroke data can be expressed as the angle of each vertical stroke coupled to its coordinates. This representation can be complicated because of the modulo operations on angles that make up the basic operations (eg, finding the mean). This problem can be solved by assuming that all angles are within plus or minus 90° of the document's mean horizontal and mean vertical angles (for the tangent and vertical vector domains, respectively). All angles are shifted into these ranges, and it is assumed that the surface will not contain any angles outside of these ranges. This assumption is true for any document that is not bent more than 90° in any direction.

Once the angles are constrained to the appropriate range, they can be treated as regular data without worrying about modulo operations.

Regarding horizontal interpolation, the splines fitted to the top and bottom of the lines of text follow the horizontal curvature of the document. The angle of tangent at each pixel can be extracted to a spline, and a smooth continuous function that best approximates this horizontal tangent data can be constructed. As with vertical interpolation, the angles are first shifted into the proper range and then treated as normal data. This range is obtained by adding 90° to the vertical angular range.

The next step is to find the interpolation function that best approximates this data. A notable property of the data in this example is that it is not defined on a raster, but spread out across the image. First, a two-dimensional high-degree polynomial can be used as an interpolation function. Thin plate splines can then be treated as an optional interpolation technique that works better with non-rasterized data.

With respect to 2D polynomials, the goal is to fit a polynomial of degree n to the data using the method of least squares. An over-determined linear system of equations is set up in order to find the coefficients of the polynomial. polynomial has form. At each data point with coordinates (x _i , y _i ) and angle θ _i , the equation p(x _i , y _i ) = θ _i can be obtained, where the coefficients a _j are unknown. Repeating this process for each of the M data points yields a linear system of equations with N equations and (n+1) ² unknowns. It was found that n=10 and n=30 were sufficient for vertical and horizontal data, respectively. Approximately N=10000 data points can be expected, so this results in an overdetermined system. In this example, the backslash operator in Matlab was used to solve the overdetermined system because the least squares error method has numerical instability problems for n>20.

The goal here is to find the constant with respect to a polynomial of degree n that minimizes the sum of errors obtained at all data points. The error function can be written as E=∑ _i (θ _i -p(xi _, y _i )) ² , where the sum spans all data points p( _xi , y _i ), each of which has an angle θ _i associated with it , and p is an unknown polynomial function of degree n. If the function has constants a _i , . . . , a _(n+1) ² , it is desirable to minimize the error with respect to those constants. Therefore, let dE/da _i =0 for all a _i , a system of n equations with n unknowns can be obtained. It also happens to be a linear system. Therefore, what needs to be solved is M _x =b for the unknown vector x including the coefficient a _j . M is an n×n matrix, and b is a vector of length n. The matrix M happens to be symmetric positive definite, so the system can be solved by using Cholesky factorization, and thus obtain the coefficients of the polynomial.

If the polynomial exhibits the Runge phenomenon and starts oscillating violently around the edges of the image, especially if the image has sparse data outside the center, this can be fixed by dividing the document into rasters and adding Data points containing the angle of the document to resolve.

Alternatively, two-dimensional cubic spline interpolation can be used as higher degree polynomial interpolation since it avoids the Runge phenomenon. Matlab's 2D cubic spline function can only be used on rasterized data. Values should be found on a grid such that a cubic spline generated on that grid best approximates the data.

In this embodiment, a 10×10 grid is used for vertical interpolation, and a 30×30 grid is used for horizontal interpolation to obtain finer resolution. It is necessary to generate a set of n ² spline basis functions e _i , these functions are splines on an n×n grid, the grid contains 1 in the i-th cell, and all others are 0. A spline on an n×n grid containing the value a _i in the ith cell is equal to ∑ _i a _i e _i . The error function used for this spline is

$\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; =</span>\underset{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}$

in yes at the angle.

It is desired to find the coefficients a _i that minimize the error function. However, if there are raster cells that do not contain any data, the spline behavior in those cells may be unconstrained. Therefore, in this example, the small constraint term added to the error function. This makes the coefficient a _i (the coefficient at grid cell i with no data point) equal to the average coefficient of a _j of i's four neighboring grid cells. In one embodiment, e is set slightly higher to also constrain cells containing few data points. The new error function can be written as:

$\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; =</span>\underset{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}_{\mathrm{<span\; class="notranslate">\; adjacent\; cells</span>}}}\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}$

This produces an overdetermined system of linear equations. In one embodiment, such a system is solved using Matlab. Finally, a spline on such a grid with value a _i in the i-th cell is produced and can be used to interpolate the original data.

3.2. Grid establishment and expansion

In this embodiment, the grid building and unfolding step 132 involves building a grid with the following properties. (1) All grid cells are quadrangular. (2) The four corners of a grid cell must be shared with all immediate neighbors. (3) Each grid cell is small enough that the local curvature of the document in that cell is roughly constant. (4) The sides of the grid cells must be parallel to the tangent or normal vector. (5) Each grid cell across the warped image corresponds to a fixed-size square in the original document.

Processing starts by placing an arbitrary grid cell in the center of the image. The grid cell is rotated until it meets the fourth criterion above. The grid cells can then be built outward using the known grid cells to fix the two or three corner points of the grid cells to be built. The last point can be computed by querying the interpolation object for the tangent and normal vectors at that position and then stepping in that direction.

In most cases, the three corner points of the grid cell to be created are already known. Therefore, the two sides of the grid cell to be created can intersect at exactly one point, which can be used to determine the fourth corner point of the grid cell to be created. When the grid cells to be built are added horizontally or vertically directly from the central cell, only the two corner points are known. In this case, the processing would be somewhat arbitrary.

The grid building and unfolding step 132 may perform better if the two problems associated with the grid building process are well resolved. The first problem arises when it is necessary to determine how much to stretch text horizontally and where. Once the tangent vectors and vertical strokes are correctly identified, the document can be expanded with straight lines of text. However, unless the text characters are stretched horizontally to varying degrees along each text line, the text may not look aesthetically pleasing. Text characters on portions of the page that are curved about the camera will appear distorted horizontally, with a narrowed width. Text characters on relatively flat parts of the paper will appear normal. In one embodiment, when the horizontal stretching nature of text has very accurate tangent and normal vectors, additional code that tests for and corrects for such stretching can be used to address this issue.

The second problem is that the grid building process builds the grid outward from some central cell. This means that any small errors in tangential and perpendicular strokes will be propagated outward through the entire grid. Small errors early in the grid-building process can cause large grid-building errors, expanding or shrinking grid cells abnormally. In one embodiment, creating multiple grid cells can be used to address this issue.

3.3. Optimization-based deployment

Optionally, the optimization-based unwrapping step 134 may be performed as the last unwrapping transformation step 106 . The optimization-based unwrapping step 134 finds a map that determines where in the original image each pixel in the output image should be sampled from. The unfolding function computes this mapping globally, which distinguishes it from raster building.

In this embodiment, the optimization-based deployment step 134 is performed in two steps. First, consider subsets of pixels in the input image and determine where those pixels should map into the output image. These pixels are called control points. The problem is formulated as an optimization problem that specifies properties of an ideal solution and searches the solution space for an optimal solution.

Second, once a set of control points is obtained in the input image, smooth interpolation can be performed across them to determine where each point in the original image should map to. This determines the natural stretch of the original image from the text features. Interpolation can be achieved using thin plate splines.

To construct the optimization function, first find a set of points in the original image that are easily mapped to the output image. It is better if the set of points is well distributed throughout the input image. In this embodiment, a fixed number of points evenly spaced along each text line is chosen.

An optimization problem can be set up to find where in the output image these points should be mapped. The optimization problem consists of estimating an error function for errors in possible point maps. This error function is also called the objective function. In one embodiment, Matlab's implementation of standard methods for minimizing error in optimization problems can be used to find optimal solutions.

The objective function considers several properties of the text line in order to compute the error of possible point mappings. For example, in a good mapping, all points in the same text line lie along a straight line, adjacent text lines are all evenly spaced, and text lines are left-aligned.

Once the objective function has been used to determine the mapping of control points from the output image to the input image, thin plate splines can be used to interpolate the mapping for other pixels.

In this embodiment, the mapping of these control points is used to generate a mapping for the entire image by modeling the image transformation as a thin plate spline. Thin plate splines are a family of parametric functions that interpolate discrete data occurring in two dimensions. They are often used in image processing to represent non-rigorous deformations. Several properties of thin plate splines make them ideal for optimization-based unfolding. Most importantly, they smoothly interpolate discrete data. Most other two-dimensional data fitting methods either do not strictly interpolate or require the data to appear on a grid.

Generic splines are a parametric family of functions designed to create smooth functions that match data values at discrete data points by minimizing a weighted average of the function's error measure and roughness measure. (See "SplinesToolbox User's Guide" by Carl de Boor, MathWork, Inc., 2006, which is hereby incorporated by reference.) The measure of error is the least squares error at the data points. For scalar data occurring at ^R2 , the function can be viewed as a three-dimensional shape. One possible measure of functional roughness is defined by a physical simulation of the bending energy of a sheet metal:

$\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; \&Integral;</span>}_{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; \&infin;</span>}^{<span\; class="notranslate">\; \&infin;</span>}{<span\; class="notranslate">\; \&Integral;</span>}_{<span\; class="notranslate">\; -</span><span\; class="notranslate">\; \&infin;</span>}^{<span\; class="notranslate">\; \&infin;</span>}<span\; class="notranslate">\; [</span>{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; xx</span>}}<span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; xy</span>}}<span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; yy</span>}}<span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ]</span>\mathrm{<span\; class="notranslate">\; dxdy</span>}$

Splines fit data with a minimum amount of curvature by minimizing the sum of roughness and error measurements.

Thin plate splines are a family of functions that solve this minimization problem with rotation invariance. This family can be expressed as the sum of radial basis functions centered at the data points plus a linear term defining the plane. radial basis function is a function whose value at R2 is radially symmetric around the origin, so The radial basis functions used for thin plate splines are A thin plate spline f(x) fitted to n control points located at { _xi } has the form:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; ax</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; by</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\mathrm{<span\; class="notranslate">\; \&phi;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>$

Where a, b, c and _ki are a set of n+3 constants.

Thin plate splines are general smoothing functions that compromise error and roughness. Strict interpolation can be restored by allowing weights on the error measure to approach 1 and weights on the roughness measure to approach 0. This is equivalent to only trying to minimize the roughness with zero error. A general solution to this narrower problem is also thin-plate splines. (See "Thin Plate Splines" by Serge Belongie at http://mathworld.wolfram.com/ThinPlateSpline.html in 2008, which is hereby incorporated by reference.) Finding the constant The specific problem of weights can be reduced to a definite system of linear equations. (See "Splines Toolbox User's Guide" by Carl de Boor, MathWorks, Inc., 2006, which is hereby incorporated by reference.) The reasons for using strictly interpolating thin plate splines are discussed below.

Although thin plate splines were originally designed for scalar data, they can be generalized to vector data values. By independently assuming two dimensions of data behavior, each coordinate can be modeled with its own independent scalar thin-plate spline function. This is the usual approach when using such thin plate splines in image processing applications. (See "Warping Aerial Photographs to Orthomaps Using Thin Plate Splines" by Cedric A. Zala and Ian Barrodale, Advances in Computational Mathematics, Vol. 11, pp. 211-227, 1999, which is hereby incorporated by reference.) By using thin plate Spline interpolation is used for the mapping of all other points, and the mapping from one two-dimensional image to another can be uniquely defined by some control point, where the position of the control point in both images is known. These control points are found by an optimization problem. Generates two thin-plate splines for x and y coordinates in the input image, then evaluates at each point in the output image in order to find the corresponding pixel in the input image.

Because the control points in the input and output images are of the same data type, i.e. points in R2, it is possible to use thin plate splines to define transformations in either direction. In the forward mapping process, the control points in the input image can be used as data stations, while the control points in the output image can be data values. Evaluating the thin-plate spline at a pixel in the input image yields where that pixel maps to in the output image. This transformation can be problematic when it is used with discrete image matrices. In general, all output positions will be unreasonably real numbers, not integers, so exact pixel correspondence will be unclear. More importantly, if the transformation squeezes or stretches the input image, several pixels may map to the same point, or several regions in the output image may fall between pixels mapped by the original.

In this embodiment, inverse mapping is used instead of forward mapping to avoid the problem of having undefined pixels in the output image. In the inverse mapping process, the control points in the output image are data stations, while the control points in the input image are data values. Evaluating the thin-plate spline at the pixel location in the output image returns the pixel mapped from it in the input image. Non-integer answers can be interpreted as distance-weighted averages of the four surrounding integer points. Because each pixel in the image matrix can be unambiguously defined from a thin-plate spline evaluation, once the spline function is obtained, producing the output image is straightforward.

Generating and evaluating thin plate splines can be computationally heavy for a large number of control points. There are methods that can be used to speed up this process that, when used on text documents, have minimal impact on the resulting image. The first approach is to reduce the number of control points per thin-plate spline by dividing the image into blocks and generating a separate thin-plate spline function for each block. The image can be divided into blocks of recursively varying size in order to limit the maximum number of control points in each spline. Runtime is not very sensitive to this parameter. However, when the number of control points exceeds 728, Matlab uses a much slower iterative algorithm (see "Splines Toolbox User's Guide" by Carl de Boor, MathWorks, Inc., 2006, which is incorporated by reference at this). In this embodiment, the maximum number of control points is limited to 500.

Each part of the image is expanded and these parts are linked together to form the complete output image. In general, thin plate splines are discontinuous at boundaries when used in this manner. However, optimizing the model creates segments that tend to align neatly. The unwrapping of each patch uses control points from a region whose area is about twice as large as that of the actual output image. Since the control points are fairly evenly spaced across a piece of text, two adjacent segments will share a large number of control points near their common border. The two transformations correspond very well in the neighborhood of this boundary by requiring the thin-plate spline to be strictly interpolated. Although not an exact correspondence, the difference is usually much smaller than a pixel so that no artifacts are visible in the output image.

If further testing shows that the segments themselves are not aligned correctly, it is possible to force them to do so by using samples from one segment as control points for the other. Evaluating the thin plate splines of one segment at regular intervals along the boundary of another segment, and using the results as control points for the second segment, will make the two functions coincide exactly at the points sampled, and the interpolation should Make them match along the entire border. A potential disadvantage of doing this is that the result may depend on the order in which the segments are expanded. The two segments have different expansions, but only one of them is changed to match the other, so the order will affect the output image. Another option is to investigate standard image-mosaicking algorithms. Most of these algorithms also use thin-plate splines, so it is possible that they are implemented as part of segment transformations rather than as post-processing effects.

The second improvement only affects the evaluation of thin plate splines, not the generation. Evaluating a thin plate spline for n control points requires finding n Euclidean distances and n logarithms. Performing this calculation on every single pixel in the image is extremely slow. This can be ignored. If the document deformation is not too severe, the thin plate spline will also not have drastic local changes. The result of evaluating the thin plate spline is a grid of ordered pairs showing where in the original image pixels should be sampled from. An accurate approximation of such a grid can be obtained by evaluating thin-plate splines every few pixels and filling the rest of the grid with simple linear interpolation. In practice, the transformation is simple enough that a local linear approximation is accurate for a neighborhood of a few pixels. Sampling thin-plate splines every ten pixels reduces the number of necessary spline evaluations by two orders of magnitude without noticeable visible artifacts on normal text documents. Since ten pixels is approximately the minimum for a recognizable character, and the feature detection step assumes curvature larger than a single character, this approximation should not adversely affect unwrapping. By combining these two optimizations, the thin-plate spline transformation can be obtained for standard-sized images with a runtime of one to two minutes or so in Matlab.

A sample image 280 developed using the optimization method is shown in FIG. 11 . Control points 286 are marked with dark colored dots, while those sets of points 282, 288 to be horizontally aligned are marked with light colored dots. This image 280 contains the type of document that has a high density of left-right justified text.

As shown in Figure 12, the output 214 of the optimized unwrapping method is applied to the sample image. The lines of text are mostly straightened, and the columns are aligned left and right. The imperfection in the alignment is due to the fact that the point we are aligning is somewhere in the first and last text character in a way that is not necessarily consistent for every line. The splines we fit to the column boundaries can be used to get a better set of points to align.

There are several other alternatives to the grid building and unfolding step 132 . An alternative approach is to apply a series of basic transformations to the entire image in order to correct various types of warping. This approach will allow control over which transformation is applied, specifying exactly what type of curl we should correct. However, this is also limited, since an image can only be rectified if the original deformation can be expressed as some combination of these fundamental transformations. This method can also be applied iteratively for smoother unrolling.

Another alternative is to fit splines between text line splines across the entire page, using the splines to sample pixels for the output image. Each spline will represent a horizontal row of pixels in the output image. This approach can benefit from utilizing global optimization between splines such that the splines are relatively consistent with each other.

Another alternative is to reconstruct the surface in 3D and flatten the surface using ideas such as the mass-spring system discussed in Brown and Seals. (See "Image Restoration of Arbitrarily Warped Document" written by Michael S. BROWN and W. Brent SEALES, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 10, No. 1295-1306, October 2004, via incorporated herein by reference.)

The methods described herein for processing captured images may be applied to any type of processing application, and (without limitation) are particularly well suited for computer-based applications for processing captured images. The methods described herein can be implemented by hardware circuits, computer software, or a combination of hardware circuits and computer software, and are not limited to specific hardware or software implementations.

FIG. 13 is a block diagram illustrating a computer system 1300 upon which embodiments of the invention described above may be implemented. Computer system 1300 includes a bus 1345 or other communication mechanism for communicating information, and a processor 1335 coupled with bus 1345 for processing information. Computer system 1300 also includes main memory 1320 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus 1345 for storing information and instructions to be executed by processor 1335 . Main memory 1320 may also be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 1335 . Computer system 1300 also includes a read only memory (ROM) 1325 or other static storage device coupled to bus 1345 for storing static information and instructions for processor 1335 . A storage device 1330 (eg, a magnetic or optical disk) is provided and coupled to bus 1345 for storing information and instructions.

Computer system 1300 can be coupled by bus 1345 to a display 1305 (eg, a cathode ray tube (CRT)) for displaying information to a computer user. An input device 1310 including alphanumeric and other keys is coupled to bus 1345 for communicating information and command selections to processor 1335 . Another type of user input device is a cursor controller 1315 , such as a mouse, trackball, or cursor arrow keys, for communicating direction information and command selections to the processor 1335 and for controlling cursor movement on the display 1305 . Such input devices typically have two degrees of freedom in two axes, a first axis (eg, x) and a second axis (eg, y), allowing the device to specify a position in a plane.

The methods described herein relate to the use of computer system 1300 to process captured images. Processing of captured images is provided by computer system 1300 in response to processor 1335 executing one or more sequences of one or more instructions contained in main memory 1320, according to one embodiment. Such instructions may be read into main memory 1320 from another computer-readable medium (eg, storage device 1330 ). Execution of the sequences of instructions contained in main memory 1320 causes processor 1335 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory 1320 . In alternative embodiments, hard-wired circuitry may be used instead of or in combination with software instructions to implement the embodiments described herein. Thus, embodiments described herein are not limited to any specific combination of hardware circuitry and software.

The term "computer-readable medium" is used herein to refer to any medium that participates in providing instructions to processor 1335 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 1330 . Volatile media includes dynamic memory, such as main memory 1320 . Transmission media include coaxial cables, copper wire and fiber optics, including the wires that comprise bus 1345 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications.

Common forms of computer readable media include, for example, floppy disks, flexible disks, hard disks, magnetic tape, or any other magnetic media, CD-ROMs, any other optical media, punched cards, paper tape, any other physical media with a pattern of holes, RAM, PROM and EPROM, FLASH-EPROM, any other memory chip or cartridge, carrier wave as described below, or any other computer-readable medium.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 1335 for execution. For example, the instructions may initially be carried on a disk in the remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 1300 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infrared detector coupled to bus 1345 can receive the data carried in the infrared signal and place the data on bus 1345 . Bus 1345 brings the data to main memory 1320 , from which processor 1335 retrieves and executes the instructions. The instructions received by main memory 1320 can optionally be stored on storage device 1330 either before or after execution by processor 1335 .

Computer system 1300 also includes a communication interface 1340 coupled to bus 1345 . Communication interface 1340 provides bi-directional data communication coupled to network link 1375 , which connects to local network 1355 . For example, communication interface 1340 may be an Integrated Services Digital Network (ISDN) card or a modem to provide data communication to a corresponding type of telephone line. As another example, communication interface 1340 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 1340 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link 1375 generally provides data communication over one or more networks to other data services. For example, network link 1375 may provide a connection through local network 1355 to host computer 1350 or to a data device operated by Internet Service Provider (ISP) 1365 . The ISP 1365, in turn, provides data communication services over a global packet data communication network, commonly referred to as the "Internet" 1360. Local network 1355 and Internet 1360 both use electrical, electromagnetic or optical signals to carry digital data streams. The signals through the various networks and the signals on network link 1375 and through communication interface 1340 that carry the digital data to and from computer system 1300 are example forms of carrier waves that carry the information.

Computer system 1300 can send messages and receive data, including program code, over a network, network link 1375 and communication interface 1340 . In the Internet example, the server 1370 may send the requested code for the application through the Internet 1360, ISP 1365, local network 1355, and communication interface 1340. As described below, one such download application is used to process captured images in accordance with the present invention.

Received code may be processed by processor 1335 as it is received, and/or stored in storage device 1330 or other non-volatile memory for later execution. In this manner, computer system 1300 can obtain the application code in the form of a carrier wave.

While the invention has been disclosed using examples, including the best mode, and the examples enable any person skilled in the art to make and use the invention, the patentable scope of the invention is defined by the claims and may include those skilled in the art Other examples can come to mind. Accordingly, the examples disclosed herein are to be considered non-limiting. In fact, it is contemplated that any combination of features disclosed herein may be combined without limitation with any other combination of other features disclosed herein.

Furthermore, although specific terms are resorted to for the sake of clarity, the invention is not intended to be limited to the specific terms so selected, and it is to be understood that each specific term includes all equivalents.

It should also be understood that the image processing described herein may be embodied in software or hardware, and may be implemented by a computer system capable of processing captured images as described herein.

Claims (20)

1. for the treatment of a method for the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with vertical stroke, and the method comprises:

(a) utilize the normalized threshold process of pixel to carry out the dualization to digital picture, to form the pixel of the text of document in discriminating digit image;

(b) detect indication text towards typesetting feature;

(c) top and the bottom to line of text by spline-fitting;

(d) utilize vector with the direction of the vertical stroke parallel vector parallel with the direction of line of text to set up tetragonal grid;

(e) vector that the vector that makes to be parallel to line of text by stretching image is parallel to the direction of the vertical stroke quadrature that becomes, launches document; And

(f) utilize optical character recognition to process the document of expansion.

2. the method for claim 1, wherein dualization is processed and is comprised that illusion removes step, that is and, if the join domain of a black pixel surpasses maximum area parameter, this illusion is removed the join domain that step abandons whole black pixel.

3. the method for claim 1, wherein dualization is processed and is comprised that illusion removes step, that is and, if the join domain of a black pixel is less than minimum area parameter, this illusion is removed the join domain that step abandons whole black pixel.

4. for the treatment of a method for the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with vertical stroke and top end and bottom end points, and the method comprises:

(a) detect top end and the bottom end points of line of text;

(b), for each line of text, spline-fitting is arrived to top end, and spline-fitting is arrived to bottom end points;

(c) by distinguishing top section and the base section of line of text, the page of determining the image of taking pictures towards;

(d) for each line of text calculate approximate towards, and remove the exceptional value in line of text;

(e) by determining that whether starting point or the terminal of line of text aligns, and finds out vertical paragraph boundaries;

(f) by detecting the vertical stroke in text character along partial vertical scanning direction, to obtain vertical pixel piece at each joining place of the barycenter batten of line of text and the text pixel of text character;

(g) utilize vector with the direction of the vertical stroke parallel vector parallel with the direction of line of text, set up tetragonal grid; And

(h) vector that the vector that makes to be parallel to line of text by stretching image is parallel to the direction of the vertical stroke quadrature that becomes, launches document.

5. method as claimed in claim 4, wherein by distinguish the page that the top section of line of text and base portion assign to determine the image of taking pictures towards step also comprise: selecting the representative sample of line of text and each line of text in sample is detected to which side has more exceptional value, and wherein the length of sample approaches the intermediate value length of all line of text.

6. for the treatment of a method for the image of taking pictures that comprises imaged document, wherein imaged document comprises line of text, and line of text comprises the text character with vertical stroke, and the method comprises:

(a) detect indication imaged document Chinese version towards typesetting feature;

(b) top and the bottom to the one or more line of text in imaged document by spline-fitting;

(c) utilize vector with the direction of the vertical stroke parallel vector parallel with the direction of line of text to set up tetragonal grid; And

(d) by each location of pixels in the output image for launching, calculate the correspondence position in its imaged document in the image of taking pictures, and calculate its pixel color and/or intensity, the imaged document of launching to take pictures in image by using near one or more pixels of this correspondence position in imaged document.

7. method as claimed in claim 6, the described correspondence position in the imaged document of wherein taking pictures in image in step (d) is by utilizing its x coordinate of a mathematical function modeling and calculating with its y coordinate of another mathematical function modeling.

8. method as claimed in claim 7, wherein these two mathematical functions utilize thin plate spline technology to produce.

9. method as claimed in claim 6, wherein also will generate reference mark before the calculating for the correspondence of each location of pixels, and wherein correspondence is to calculate for the subset of location of pixels.

10. method as claimed in claim 9, wherein the subset of location of pixels comprises the one or more points that are positioned in one or more line of text.

11. methods as claimed in claim 9, wherein the subset of location of pixels comprises left terminal and the right terminal of one or more line of text.

12. methods as claimed in claim 6, wherein the color of output pixel and/or intensity are that four nearest pixels are calculated from input picture.

13. 1 kinds of methods for the treatment of the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with end points and vertical stroke, the method comprises:

(a) by finding out corresponding to the set of pixels of text character in digital picture and creating the binary picture that only comprises described set of pixels, detect text filedly, wherein this set of pixels is grouped into character zone, and character zone is grouped into again line of text;

(b) by the end points of identification text character and the shape that vertical stroke detects the document of taking pictures in digital picture;

(c) by distinguish the top section of line of text and base portion assign to detect the document of taking pictures in digital picture towards; And

(d) based on grid, set up and process the new digital picture that digital service unit is become to this document of taking pictures, at grid, set up the end points and the vertical stroke that in processing, identify and be used as the identification curling basis of document.

14. methods as claimed in claim 13, wherein detect shape step and spline-fitting are arrived to top and the bottom of line of text, so that approximate original document shape.

15. methods as claimed in claim 13, wherein detect text filed step further comprising the steps of:

(a1) by threshold process method standard and/or simple, estimate prospect text;

(a2) from original image, remove these foreground pixels;

(a3) by carrying out interpolation from remaining value, fill the hole staying due to removal, this by remove initial threshold process and on hole interpolation the new estimation to background is provided; And

(a4) threshold process is carried out in the improved estimation based on background.

16. methods as claimed in claim 13, wherein shift step depends on grid and sets up processing, sets up the feature extracting in processing be used as the identification curling basis of document at grid.

17. methods as claimed in claim 13, wherein shift step depends on optimization problem.

18. 1 kinds of computer systems for the treatment of the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with vertical stroke, this computer system comprises:

Be used for utilizing the normalized threshold process of pixel to carry out dualization, to form the device of pixel of the text of document in recognition image;

For detection of indication text towards the device of typesetting feature;

For spline-fitting is arrived to the top of line of text and the device of bottom;

For utilizing the vector parallel with the direction of the line of text vector parallel with the direction of vertical stroke to set up the device of tetragonal grid;

The vector that is parallel to the direction of vertical stroke for make to be parallel to the vector of line of text by the stretching image quadrature that becomes, launches the device of document; And

For utilizing optical character recognition to process the device of the document of expansion.

19. 1 kinds of computer systems for the treatment of the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with vertical stroke, this computer system comprises:

For detection of the top end of line of text and the device of bottom end points;

For for each line of text, spline-fitting is arrived to top end, and spline-fitting is arrived to the device of bottom end points;

For by distinguishing top section and the base section of line of text, the page of determining the image of taking pictures towards device;

Be used to each line of text calculate approximate towards, and remove the device of the exceptional value in line of text;

For starting point or terminal by definite line of text, whether align, find out the device of vertical paragraph boundaries;

Be used for by detect the vertical stroke of text character along partial vertical scanning direction, to obtain the device of vertical pixel piece at each joining place of the barycenter batten of line of text and the text pixel of text character;

For utilizing the vector parallel with the direction of the line of text vector parallel with the direction of vertical stroke, set up the device of tetragonal grid; And

The vector that is parallel to the direction of vertical stroke for make to be parallel to the vector of line of text by the stretching image quadrature that becomes, launches the device of document.

20. 1 kinds of computer systems for the treatment of the digital picture of the document of taking pictures that comprises line of text, wherein line of text comprises the text character with vertical stroke, this computer system comprises:

For detecting text filed device by finding out corresponding to the set of pixels of text character in digital picture and creating the binary picture that only comprises described set of pixels, wherein this set of pixels is grouped into character zone, and character zone is grouped into again line of text;

For the end points by identification text character and the device that vertical stroke detects shape;

For by distinguish the top section of line of text and base portion assign to detect the document of taking pictures towards device; And

For setting up and process the device that digital service unit is become to the new digital picture of this document of taking pictures based on grid, the end points identifying in grid foundation is processed and vertical stroke are as the identification curling basis of document.