Abstract:
Single-image super-resolution (SISR) is the problem of generating a high resolution image from a single low resolution image. The SISR technique known as neighbor embedding utilizes a training ensemble of pairs of low and high resolution image patches, where the patches in a given pair represent the same image region. The present invention improves upon prior neighbor embedding algorithms by offering a practical, computationally efficient method of neighbor embedding for generating a high resolution version of a low resolution image. The technique may also be applied to generate high resolution versions of low resolution text images for subsequent input into OCR engines. OCR character error rates found on the high resolution images are drastically lower than those found when OCR is applied to the original low resolution text images.

Description:
FIELD OF INVENTION 
     The present invention relates to image analysis, and in particular to raising the image resolution for OCR enhancement. 
     BACKGROUND OF THE INVENTION 
     Generating a high resolution (HR) image from one or more low resolution (LR) images is called image super resolution (SR). HR images have a higher pixel density than their LR counterparts, and provide details which are obscured in LR versions. Image SR is very useful in a number of applications including satellite imagery, pattern recognition, and medical diagnosis, to name a few. 
     Single-image super-resolution (SISR) is the problem of generating a HR image from just one LR image. There are two basic types of image SISR techniques. The first involves interpolation, which cannot recover missing high-frequency information. The second type utilizes learning based methods (training). While the prior art has applied variants of learning based methods to scene, animal, and human images, few have successfully applied these methods to text images. Additionally, electronic conversion of scanned text images into machine-encoded text (e.g. ASCII) is known as optical character recognition (OCR). OCR is essential for automatic processing of text documents by facilitating electronic searching and efficient storage. OCR is used in machine translation, text-to-speech applications, text data mining, and is widely used for data entry from printed records. When the text resolution is poor, OCR engines frequently have unacceptably high character error rates (CER). Such catastrophic performance often occurs when documents are scanned at low dpi (pixels per inch) to conserve memory and even when the LR documents are readable by humans. Furthermore, the interpolation methods result in very high character error rates when OCR is applied to their HR text image estimates. Additionally, learning based methods exhibit computational speeds which are too slow in practice for OCR enhancement, unless their training models are quite small. This limitation on model size means that prior art models must be specifically trained on a particular low resolution font style and size, and cannot be applied to a different font style and size 
     The present invention addresses the SISR problem for various types of grayscale images (i.e. scenes, faces, text) and for text documents. The present invention also discloses a method that improves OCR performance by lowering OCR character error rate (CER), which we refer to as OCR enhancement. The present invention offers a solution that significantly accelerates computational speed compared to prior art learning based SISR so that a single model suffices for most Latin font styles and sizes, and also significantly lowers CER when HR image estimates obtained with the invention are input to OCR engines. 
     The prior art includes several published articles including “Super Resolution through Neighbor Embedding” by H. Chang, D. Yeung, and Y. Xiong, CVPR, volume 1, pp. 275-282, 2004. Chang et al discloses a method for creating high resolution images. However Chang et al&#39;s algorithm is inadequate for OCR enhancement because it utilizes an exact nearest neighbor search which is not fast enough for OCR. Specifically, exact nearest neighbor searches require exhaustively searching thousands of training vectors at multiple locations in the low resolution input image, which results in an extended processing time. Since this exhaustive search is extremely slow, Chang et al&#39;s method is limited to using an individual training model for each font style and size. Consequently, Chang et al&#39;s method also requires knowledge of the font style and size of the LR input image in order to apply the matching training model. However, with OCR enhancement, the font style and size of the input image are generally unknown. Therefore, Chang&#39;s method is inadequate for OCR enhancement. Additionally, Chang&#39;s method uses a feature vector consisting of first and second order partial derivatives of the LR input image at each pixel value in a corresponding K×K image patch, resulting in a feature vector which is four times longer than the feature vector of the present invention. Consequently Chang&#39;s et al&#39;s method uses unnecessarily large training models which require significant amounts of computer memory. This large memory footprint limits the amount of training information that can be represented by Chang et al&#39;s models, which in turn restricts the accuracy of Chang&#39;s HR image estimates. 
     The present invention uses a feature vector that is only 25% as long as Chang&#39;s and results in a model that requires only a quarter of the memory required for the Chang models. As such, the present invention results in four times as much training information that can be represented in the same computer memory as Chang&#39;s method, which in turn results in more accurate HR image estimates. 
     Other notable articles include “Nonlinear Dimensionality Reduction by Locally Linear Embedding” by S. T. Roweis and L. K. Saul (Science, vol. 290, pp. 2323-2326, 2000), “Resolution Enhancement based on Learning the Sparse Association of Patches” by J. Wang, S. Zhu, Y. Gong (Pattern Recognition Letters, vol. 31, pp. 1-10, 2010), “Locality Preserving Constraints for Super-resolution with Neighbor Embedding” by B. Li, H. Chang, S. Shan, and X. Chen (IEEE ICIP 2009, pp. 1189-1192). While the aforementioned prior art considers the noted SISR problem, none offer a solution that is as computationally efficient and accurate as the present invention and results in a lower CER than the prior art given the same memory resources. Not only does the prior art require significantly more memory than the present invention but it also takes more than 1000 times longer to construct a HR image estimate. The above mentioned articles are hereby incorporated by reference into the specification of the present invention. 
     The prior art also includes the following patents. U.S. Pat. No. 7,379,611 entitled “Generic Image Hallucination” discloses a learning based method SISR method. Here the prior art differs from the present invention because it uses a training set comprised of LR/HR pairs of “primitives”, i.e., patches which focuses on edges, ridges or corners. U.S. Pat. No. 7,379,611 is hereby incorporated by reference into the specification of the present invention. 
     U.S. Pat. No. 8,233,734 entitled “Image Upsampling with Training Images” discloses a method that creates a high resolution version of a low resolution input image creating a “course” HR image from a LR input image using patch matching where each patch contains a primitive (i.e., an edge, corner, or ridge) and use probabilistic models of primitives and contour smoothness constraints. The present invention does not use primitives or probabilistic models of same. U.S. Pat. No. 8,233,734 is hereby incorporated by reference into the specification of the present invention. 
     U.S. Pat. No. 7,218,796 entitled, “Patch-based Video Super-resolution”, discloses a method for video super-resolution that uses a training set containing HR/LR patch pairs and employs patch matching. Here, the prior art represents low resolution patches, primarily by using only the patch values, or by dividing the patch values by the energy in the patch. The present invention does not employ this type of feature vector. U.S. Pat. No. 7,218,796 is hereby incorporated by reference into the specification of the present invention. 
     U.S. Patent Appl. #20080267525, entitled “Soft Edge Smoothness Prior and Application on Channel Super Resolution”, discloses SISR that is based on edge segment extraction from the input LR image and performing a super-resolution on the extracted edges. The present invention does not require the use of edge information. U.S. Patent Appl. #20080267525 is hereby incorporated by reference into the specification of the present invention. 
     U.S. Patent Appl. #20110305404, entitled “Method and System for Example-based Face Hallucination discloses a learning based method which uses a training set of LR/HR face images, and in addition uses a dimensionality reduction technique to project the LR training images (each considered as a vector of pixel values) into a low dimensional space. Then an input LR image is projected in the same manner, and the projected LR input image is matched to the nearest LR projected training images. Thus, the method does not use local patches as in neighbor embedding, but uses global image projections in matching. U.S. Patent Appl. #20110305404 is hereby incorporated by reference into the specification of the present invention. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to offer a computationally efficient method of neighbor embedding (NE) to generate a high resolution output image from a low resolution input image. 
     Another object of the present invention is to generate a high resolution output image from a low resolution input text image which can be inputted into an OCR engine, which results in significantly lower character error rates than those found when the engine is applied directly to the low resolution text image. 
     The present method comprises the following steps. First, a training set, {(FL n,m , H* n,m )} is created. Next, a set of randomized k-d trees is created from the training set. At least one low resolution input image, P is received. From this low resolution image, P, a high resolution output image, T, is generated using the training set and the set of randomized k-d trees. Finally, when said input image is a text image, a text file is generated by inputting the high resolution output image, T, into an OCR engine. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a flowchart depicting the prior art. 
         FIG. 2  is a flowchart depicting the present invention. 
         FIG. 3  is a flowchart depicting the present invention. 
         FIG. 4  is a flowchart depicting the present invention. 
         FIG. 5  is a flowchart depicting the present invention. 
         FIG. 6  is a flowchart depicting the present invention. 
         FIG. 7  is an example of the results produced by the present invention. 
         FIG. 8  is an example of the results produced by the present invention. 
     
    
    
     DETAILED DESCRIPTION 
       FIGS. 1-2  illustrate the difference between known methods employed in OCR  10  and the OCR process in the present invention  20 . With respect to the known methods, a low resolution text image is inputted  11  to an OCR engine  12  directly to generate a text file  13 . However, as discussed above, the result is frequently of poor quality and in many cases, incomprehensible. In contrast,  FIG. 2  depicts the present invention in that a low resolution text image  21  can be manipulated using learning based techniques  22  as discussed below to produce a high resolution image  23 . This HR image can then be fed into an OCR engine  24  to generate a text file  25  that has a significantly lower character error rate than that produced by the prior art&#39;s OCR process. In both instances, it is obvious to individuals skilled in the art that these methods are being implemented on computer systems that are composed of varying computing devices and can be adapted to work with various types of systems. 
     As mentioned previously, the present invention offers solutions to two different problems. The first problem is how to generate an HR image from a LR input image (i.e. scene, animal, face, text images) using single-image super-resolution (SISR) in a manner which is computationally faster and requires significantly less computer memory than prior learning based methods. The second problem is how to reduce the character error rate currently found with OCR engines on low resolution input. 
       FIG. 3  depicts a computationally efficient method of neighbor embedding to produce a HR output image from an input LR text image or text document using SISR. First a training set of paired elements, {(FL n,m , H* n,m )}, is created 30 where FL n,m  are feature vectors and H* n,m  are high resolution image patches. Next, a set of randomized k-d trees are created using the first elements, FL n,m , as leaf nodes  31 . The set of k-d trees that are generated allow for an approximate nearest neighbor search which is 1000× faster, with a negligible loss of accuracy, than the exact nearest neighbor search by the prior art. The set of randomized k-d trees can be generated in various ways but in the preferred embodiment, the set of randomized k-d trees are generated using OpenCv Fast Library for Approximate Nearest Neighbors (FLANN). Next, at least one low resolution text image, P, is received 32. A high resolution image, T, is then generated from the low resolution text image, P, using the training set and the set of the randomized k-d trees that were previously created 33. People skilled in the art recognize that T is generated from a training set which is constructed using the same process which produced P (i.e. downsampling, scanning). As shown in  FIG. 2 , when the input image P is a text image, this high resolution output image, T, can then be inputted into an OCR engine to generate text file  34 . 
     As mentioned above, the first step of the present invention&#39;s method is to create a training set  30 .  FIG. 4  depict the process of creating the training set. The process to create a training set can vary depending on whether the user is starting with a user-defined set of high resolution images or a user-definable set of text documents, S n , that contain examples of a serif font (e.g. Times New Roman) and/or a sans serif font (e.g. Arial) having approximately the same number of words in 6 pt, 8 pt, 10 pt, and 12 pt. If the user is starting with a user-definable set of high resolution images, H n , corresponding low resolution images L n  can be generated by down-sampling each H n  by a positive integer, N. In the preferred embodiment, N is a user-definable small positive integer in the range of two to five  42 . On the other hand, if the user is starting with a user-definable number of text documents  40 , a high resolution image, H n , is generated by scanning each S n  at a high dpi  41  and a low resolution image, L n  is then generated by scanning each S n  at low dpi  42 . Note that the high dpi is equal to, N times the low dpi. Next, a patch dimension, K, is selected  43  where K is a user-definable small positive integer. In the preferred embodiment, K is in the range of two to five. Each low resolution image, L n , is then partitioned into a set of possibly overlapping K×K pixel patches, L n,m , where each K×K pixel patch has K×K pixel values  44 . Note that the number of low resolution patches used in training depends on the dimensions of the low resolution images, L n . For example, if L n  is 8×8 and K=4, there will be 4 non-overlapping K×K patches extracted from L n . However, overlapping patches results in more training patches. For instance, if L n  is 8×8 and K=4 and there is an overlap of 2, then there will be 9 overlapping K×K patches extracted from L n . Additionally, the value of each pixel value depends on the type of image it is (i.e. for a TIF image, the value may range from 0-255, etc). 
     The next step is to set J=NK using the user-defined values for N and K  45 . The high resolution image, H n , is then partitioned into a set of J×J pixel patches, H n,m , such that pixel patch L n,m , and pixel patch H n,m  both correspond to the same specific image region  46 . Note that the number of J×J high resolution patches, extracted from H n  will be the same as the number of K×K low resolution patches, L n,m , extracted from L n  since they are in one-to-one correspondence. Next, a feature vector, FL n,m , is generated for each low resolution patch, L n,m    47 . Additionally, the J×J pixel patch has J×J number of pixel values associated with it. Finally, a J×J high resolution patch, H* n,m  is generated for each said high resolution patch, H n,m , by subtracting the mean pixel value of said corresponding K×K pixel patch, L n,m , from each pixel value in said J×J pixel patch, H n,m    48 . 
       FIG. 5  depicts how a feature vector, FL n,m , having K×K components, is generated for each low resolution patch, L n,m . This is accomplished by first selecting one of the K×K pixel patches, L n,m , generated above 50 and then determining the minimum value, minp n,m , of the pixel values in the selected low resolution patch, L n,m    51 . The minp n,m  value is then subtracted from each of the pixel values in the selected low resolution patch L n,m    52 . Next, the components of the feature vector, FL n,m , are populated with the K×K values which result from subtracting minp n,m  from each pixel value in L n,m    53 . 
       FIG. 6  depicts how a high resolution image, T, is generated from a low resolution image, P. This is accomplished by first partitioning the low resolution image, P, into a set of K×K patches, P s  having K×K pixel values  60 . Next, a feature vector FP s  is generated for each of the K×K patches P s    61 . Note that the size of P and the patch dimension K determine how many patches P s  are automatically extracted from P and one feature vector is made from each extracted patch P s . The feature vectors FP s  are generated using the same process used to generate the feature vectors during the creation of the training set except that instead of using the training patches L n,m , the patches P s  from the user-selected image P are used. 
     The next step is to lexicographically order the feature vectors, FP s  generated in the previous step  62 . Next, a set of unique features vectors, FP s     k   , is generated by removing any duplicate feature vectors in the set of feature vectors FP s    63 . Lexicographically ordering the feature vectors, FP s , and removing any duplicate feature vectors provides an additional speed advantage by skipping over white space or other homogeneous regions in the low resolution text image. Next, a lookup table is constructed by assigning to each index, s, of FP s , the unique index, k, such that FP s =FP s     k      64 . Next, select a small positive integer, Q  65 . In the preferred embodiment, the value of Q can range from two to three. For each FP s     k    determine, using Euclidean distance, the approximate Q nearest feature vectors, {FL (n,m)     q   }, q=1, 2, . . . , Q, in the training set to FP s     k      66 . This step is best accomplished using randomized k-d trees. Next, compute a set of user-definable weights  67  which minimize the following term:
 
∥ FP   s     k   −Σ q=1   Q   w   q   FL   (n,m)     q   ∥ 2 .
 
The invention computes weights in a simpler, faster manner than neighbor embedding algorithms used by the prior art, as {right arrow over (w)}=(A T  A) −1  A T {right arrow over (y)} where {right arrow over (w)}=[w 1 , w 2  . . . , w Q ] T  is the vector of weights, {right arrow over (y)}=FP s     k    and A=[FL (n,m)     1   , FL (n,m)     2   , . . . , FL (n,m)     Q   ]. This is made possible by not imposing the sum-to-one constraint on the weights used in previous NE algorithms, which is not necessary and may yield non-optimal results. Here, s takes the values 1, 2, 3, . . . , M, where M is the number of patches P s  found in partitioning P into K×K patches. M depends on K and the number of pixels in P. Additionally, the vectors FP s     k    are a subset of the vectors FP s , so k takes the values 1, 2, . . . , L, where L is the number unique feature vectors in the set {FP s }.
 
     Next, for each FP s     k   , compute a patch estimate, R k  from the user-definable number of weights computed above and the J×J high resolution patches, H* (n,m)     q    that correspond to the Q nearest feature vectors previously located  68 . Here, R k  is computed as follows:
 
 R   k =Σ q=1   Q   w   q   H   (n,m)     q   ;
 
Using the look up table, identify, for each K×K patch, P s , the integer k that corresponds to s  69 . Using this integer k, compute a high resolution patch estimate, R k * by adding the mean value of the pixel values in the K×K patch P s  to each pixel value in the patch estimate R k    70 . Next, assign this result to a position in T that corresponds to the location of K×K patch, P s , in P  71  and locate any region within T where the high resolution patch estimates, R k *, overlap  72 . Finally, average the pixel values of the high resolution patch estimates, R k * in any overlapping regions  73 .
 
       FIGS. 7-8  depict examples of the result as produced by the present invention for SISR of a text image and for OCR enhancement.  FIG. 7  depicts images of a passage from a text document in 8pt Times New Roman font. From top to bottom: (a) LR image of the passage scanned at 75 dpi  75 ; (b) HR output image produced by prior art (Bicubic Interpolation) at 4× magnification  76 ; (c) HR output image produced by the present invention at 4× magnification  77 ; and (d) HR image of the passage scanned at 300 dpi  78 .  FIG. 8  depicts OCR performance on an Arial 8pt text document. From top to bottom: (a) The actual words in the document  80 ; (b) OCR transcript from a LR image of the document scanned at 75 dpi  81 ; (c) OCR transcript from the HR image estimate obtained from the LR image using Bicubic Interpolation at 4× magnification  82 ; and (d) OCR transcript from the present invention&#39;s HR image estimate obtained from the LR image at 4× magnification  83 . As shown, the present invention produced the results with the lowest CER. 
     While the preferred embodiment has been disclosed and illustrated, a variety of substitutions and modifications can be made to the present invention without departing from the scope of the invention.