CN107133929B - Low-quality document image binarization method based on background estimation and energy minimization - Google Patents

Abstract

The invention discloses a low-quality document image binarization method based on background estimation and energy minimization. First, grayscale preprocessing is performed on a color document image, bilateral filtering is used to perform noise reduction processing on the image, image background estimation, and background reduction are performed. Divide and image enhancement, construct energy function, construct network graph, and finally use the graph cut algorithm based on augmented path to minimize the energy function. The invention significantly improves the binarization effect of document images under complex backgrounds, and can be applied to document image binarization with complex backgrounds such as writing in multiple colors, stroke gradients, ink infiltration, pages with stains or textures, uneven lighting, and low contrast. processing.

Description

Low-quality document image binarization method based on background estimation and energy minimization

technical field

The invention belongs to the technical fields of digital image processing, pattern recognition and machine learning, in particular to a low-quality document image binarization method based on background estimation and energy minimization.

Background technique

Document Analysis and Recognition (DAR) technology has been widely used in ancient book digitization, layout analysis and text recognition, video subtitle extraction, text information retrieval and other fields, mainly including image acquisition, binarization, skew correction, character segmentation and recognition and other processes . Image binarization is one of the key preprocessing steps, which converts grayscale images into binary images, so as to separate the foreground of characters from the background of the document. The effect of the binarization algorithm directly affects the performance of the entire DAR system, so many scholars have studied it in recent years and proposed many algorithms; however, it is affected by factors such as poor image contrast, ink infiltration, page stains or uneven lighting , binarizing low-quality document images remains a challenge.

Binarization algorithm can be roughly divided into global threshold method and local threshold method. The global threshold method uses a single threshold to divide the document image into two categories: character (foreground) and background. For example, the Otsu algorithm uses the grayscale histogram of the image to select an optimal threshold, so that the foreground and background pixels after threshold segmentation are classified into two categories. the largest variance. The global threshold method has a good segmentation effect for images with a large difference between the foreground and the background, that is, the histogram has a significant bimodal feature, but when dealing with low-quality document images, some or even all foreground details will be lost.

The local threshold method (also known as the adaptive threshold method) uses the convolution of the sliding window and the document image to set different thresholds in different parts of the image, such as Niblack, Sauvola, Wolf and other algorithms use the gray mean value in the pixel neighborhood and variance to construct the threshold segmentation surface, the performance of the algorithm depends on the size of the sliding window and the thickness of the character strokes. For document images of different quality, the window size needs to be dynamically adjusted to obtain the best threshold processing results; when the image contrast is low, a large number of noise points will be generated or misjudgment will be caused.

In addition, domestic and foreign researchers have also proposed many more complex algorithms, such as local contrast method, background estimation and stroke edge detection method, Laplace energy method, convolutional neural network method, etc. However, none of the above methods can well solve the image binarization in complex document backgrounds such as low contrast, inking, gradient lighting, smudges and textures.

SUMMARY OF THE INVENTION

In order to solve the above technical problems, the present invention proposes a low-quality document image binarization method based on background estimation and energy minimization, which significantly improves the document image binarization effect under complex backgrounds and is suitable for writing in multiple colors. , stroke gradient, ink soaking, pages with stains or textures, uneven lighting, low contrast and other complex background document image binarization processing.

The technical solution adopted in the present invention is: a low-quality document image binarization method based on background estimation and energy minimization, which is characterized in that it includes the following steps:

Step 1: Perform grayscale preprocessing on the color document image;

Step 2: Use bilateral filtering to denoise the image;

Step 3: Image background estimation, which includes the following sub-steps:

Step 3.1: for the image processed in step 2, perform stroke width transformation;

Step 3.2: Calculate the simulated distance and imaging height;

Step 3.3: For the image processed in step 2, the dark features in the document image are weakened by two morphological closing operations;

Step 3.4: Combine the results of Step 3.2 and Step 3.3 to perform image downsampling and upsampling;

Step 4: Background subtraction and image enhancement, including the following sub-steps:

Step 4.1: Background subtraction;

Calculate the absolute difference between the bilateral filtered image in step 2 and the background estimated image in step 3, the pixels with zero grayscale in the difference image belong to high-confidence background pixels, and set their grayscale value to 255;

Step 4.2: Histogram equalization;

Invert the non-zero pixel points in the background subtraction image to obtain the corresponding gray value of the point, and then perform histogram equalization on the entire image to increase the contrast between the foreground and background of the image;

Step 5: Construct the energy function;

Step 6: Construct the network diagram;

Step 7: Use the augmented path-based graph cut algorithm to minimize the energy function.

Compared with the existing algorithm, the present invention has the following significant advantages:

(1) The present invention uses the minimum mean value method to perform grayscale preprocessing on the color document image, and the obtained grayscale image has color independence, which can not only increase the contrast between foreground and background pixels, but also reduce the grayscale between foreground pixels. variance;

(2) The present invention adopts the nonlinear bilateral filtering algorithm to realize image noise reduction processing, because the spatial proximity and grayscale similarity of the image are considered at the same time, so as to achieve the purpose of edge preservation and denoising;

(3) The present invention adopts the method of stroke width transformation to estimate the stroke width in the document image, and its advantage is that the stroke feature is basically a unique feature of the text (of course, the interference of some degradation factors is not excluded, and subsequent operations are required. be eliminated), which is universal to texts in different languages;

(4) Based on the visual sensitivity test model, the present invention adopts morphological closing operation to realize image background estimation, and performs histogram equalization on the background subtracted image, effectively suppressing the influence of degradation factors, and simultaneously enhancing the local contrast of the image;

(5) The present invention realizes document image binarization based on the combined optimization algorithm of maximum flow/minimum cut. The graph cut algorithm has strong versatility, high feasibility, fast running speed (close to real-time performance), and is suitable for various degradation types. low-quality document images.

Description of drawings

Fig. 1: is the flow chart of the embodiment of the present invention;

FIG. 2 is a schematic diagram of the angular resolution of a vision test model according to an embodiment of the present invention.

Detailed ways

In order to facilitate the understanding and implementation of the present invention by those of ordinary skill in the art, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the embodiments described herein are only used to illustrate and explain the present invention, but not to limit it. this invention.

The main idea of the present invention is: when the target image is far away from the observer, the detail (stroke) information of the target image that can be observed becomes less and less, but the perceived background grayscale and depth are not affected by the distance, so The approximate background of the image can be estimated by simulating the scene of long-distance observation of the image, and then the energy function can be constructed for the image after excluding the estimated background, and the image binarization can be realized by using the graph cut algorithm.

Referring to Fig. 1, a method for binarizing low-quality document images based on background estimation and energy minimization provided by the present invention includes the following steps:

Step 1: minimum mean grayscale;

The invention adopts the minimum mean value method to perform grayscale preprocessing on the color document image f(x, y), and the specific calculation formula is:

Among them, f _i (x, y) are R, G, and B color component images, respectively, and f _gray (x, y) is the transformed grayscale image.

The obtained grayscale image has color independence, that is, in the grayscale image, the contrast between foreground and background pixels is relatively large, and the grayscale difference between foreground pixels is small.

Step 2: Denoising by bilateral filtering;

The present invention adopts nonlinear bilateral filtering algorithm to process image noise reduction, and its output pixel value Depending on the weighted combination of pixel values f(k,l) in the neighborhood S, the specific calculation formula is:

Among them, the weight coefficient w(i,j,k,l) depends on the domain kernel and range kernel the product of , that is and represent the Gaussian distance variance and the Gaussian grayscale variance, respectively.

Since the bilateral filter considers the spatial proximity and grayscale similarity of the image at the same time, the purpose of edge-preserving denoising can be achieved.

Step 3: Image background estimation;

Step 3.1 Stroke Width Transformation (SWT): Use Canny operator to perform edge detection on the grayscale image after bilateral filtering, and search for another edge pixel q corresponding to each edge pixel p according to its gradient direction. The Euclidean distance between points ||p-q|| is the stroke width estimate of all pixels on the [p,q] path, unless the pixel has been assigned a smaller width value, then the stroke width SWE of the image is all Mathematical expectation of stroke width estimation for non-zero pixels, the specific calculation formula is:

Among them, n is the total number of non-zero value pixels in the output image s(x, y) of the stroke width transformation.

Step 3.2 Calculate the simulated distance and imaging height: Based on the visual sensitivity test model, the smallest image that can be perceived by the human eye at the smallest resolution angle (angle of 1'), as shown in Figure 2. Since the contrast of low-quality document images is usually lower than that of the binary image on the eye chart, the minimum viewing angle of the corresponding target is usually greater than the minimum viewing angle of the vision test, and the thicker the strokes of the image, the less the observation distance required to perceive the details of the strokes. Therefore, in the present invention, the resolution angle corresponding to the stroke width of the document image is assumed to be 3′, and the simulated observation distance d ₀ is determined according to the stroke width estimated in step 3.1. The specific calculation formula is:

d ₀ =SWE×cotθ,

Among them, θ is the observation resolution angle, here is the 3' viewing angle.

Since the lens of the human eye is similar to a convex lens, according to the lens imaging law and the focal length equation, the imaging height h _i on the retina when the distance from the target image is d ₀ can be obtained. The specific calculation formula is:

Among them, f is the distance between the human eye lens and the retina, that is, the focal length of the lens (about 17mm), and h ₀ is the original height of the target image.

Step 3.3 Morphological closing operation: The dark features (character strokes) in the document image are weakened by two morphological closing operations, both of which use circular structural elements. In the present invention, the diameter of the first structural element is set as the stroke width of the image, and the diameter of the second structural element is 12 pixels larger than the stroke width of the image.

Step 3.4 Image downsampling and upsampling: the observed image height is h _i when the distance from the target image is d ₀ , therefore, the image after the morphological closing operation is scaled to the h _i height by bilinear downsampling; Linear interpolation restores the scaled image to its original size, and the resulting image is the estimated background image. When doing image scaling, keep the image aspect ratio unchanged.

Step 4: Background subtraction and image enhancement;

Step 4.1 Background subtraction: Calculate the absolute difference between the bilateral filtered image and the background estimated image. The pixels with zero grayscale in the difference image belong to the high-confidence background pixels, and set their grayscale value to 255 (white) .

Step 4.2 Histogram equalization: Invert the non-zero pixel points in the background subtraction image to obtain the corresponding gray value of the point, and then perform histogram equalization on the entire image to increase the contrast between the foreground and background of the image.

Step 5: Construct the energy function;

The specific form of the Laplace energy function is:

Among them, the data item represents the cost of assigning a certain label to the pixel, such as It refers to the cost of assigning the label 0(1) to the pixel p _ij ; the boundary term represents the cost of discontinuous adjacent pixels, that is, the cost of assigning different labels to two adjacent pixels.

The Laplace transform of the image can reflect the sudden change of the gray level of the image. When the sign of the Laplace value of a pixel in the image is positive, the corresponding pixel is generally located at the valley (dark) of the grayscale image; otherwise , when the sign of the Laplacian value of a pixel in the image is negative, the corresponding pixel is located at the peak (bright) of the grayscale image. Therefore, the data item defining the Laplace energy function in the present invention is specifically expressed as:

in, represents the Laplacian value at pixel p _ij ;

Boundary items can be divided into horizontal boundary items and vertical boundary terms The present invention uses the Canny edge detection operator to determine the boundary term, the pixels located near the edge are more likely to be discontinuous, and the discontinuity cost between the pixels located on both sides of the edge can be directly set to zero, specifically expressed as:

Among them, E _ij represents the edge detection result at the pixel p _ij , I _ij represents the gray value at the pixel p _ij , and c is an arbitrary constant (>0).

Step 6: Construct the network diagram;

Each pixel p _ij of the image constitutes the intermediate node of the network graph, and two additional terminal nodes s and t are attached. The edge connecting the intermediate nodes is called nlink, and its weight is determined by the boundary term of the energy function; the edge connecting the intermediate node and the terminal node is called tlink, and its weight is determined by the data item of the energy function. The weight of the edge (p _ij ,s) is The weight of the edge (p _ij ,t) is The weight of the edge (p _ij ,p _i+1,j ) is The weight of the edge (pi _ij ,pi _,j+1 ) is

Step 7: Use the augmented path-based graph cut algorithm to minimize the energy function;

Two search trees S and T are established based on the network graph. The root nodes of the trees are located at the source point s and the sink point t, respectively. The nodes of the search tree are divided into two categories: active nodes and passive nodes. Active nodes can be connected by unsaturated edges. Free nodes are expanded to active nodes to realize tree growth.

Step 7.1 Growth stage: The two trees continue to grow until the active nodes of the two trees meet and find a path from the source point to the sink point;

Step 7.2 Augmentation phase: the path obtained in step 7.1 is augmented, the augmentation will form at least one saturated edge, the child nodes connecting the edge become isolated nodes, and the trees S and T are split into multiple children. Tree;

Step 7.3 Adoption phase: Find the parent node for each isolated node. If there is no parent node that meets the conditions, turn it into a free node until all isolated nodes are processed.

The above three steps are repeated until the two trees no longer grow and are separated by saturated edges, and the minimum cut of the graph, that is, the minimum value of the energy function, is obtained, thereby realizing the final binarization of the image.

It should be understood that the parts not described in detail in this specification belong to the prior art.

It should be understood that the above description of the preferred embodiments is relatively detailed, and therefore should not be considered as a limitation on the protection scope of the patent of the present invention. In the case of the protection scope, substitutions or deformations can also be made, which all fall within the protection scope of the present invention, and the claimed protection scope of the present invention shall be subject to the appended claims.

Claims (7)

1. a low-quality document image binarization method based on background estimation and energy minimization, is characterized in that, comprises the following steps: Step 1: Perform grayscale preprocessing on the color document image; Step 2: Use bilateral filtering to denoise the image; Step 3: Image background estimation, which includes the following sub-steps: Step 3.1: for the image processed in step 2, perform stroke width transformation; Step 3.2: Calculate the simulated distance and imaging height; Step 3.3: For the image processed in step 2, the dark features in the document image are weakened by two morphological closing operations; Step 3.4: Combine the results of Step 3.2 and Step 3.3 to perform image downsampling and upsampling; Step 4: Background subtraction and image enhancement, including the following sub-steps: Step 4.1: Background subtraction; Calculate the absolute difference between the bilateral filtered image in step 2 and the background estimated image in step 3, the pixels with zero grayscale in the difference image belong to high-confidence background pixels, and set their grayscale value to 255; Step 4.2: Histogram equalization; Invert the non-zero pixel points in the background subtraction image to obtain the corresponding gray value of the point, and then perform histogram equalization on the entire image to increase the contrast between the foreground and background of the image; Step 5: Construct the energy function; The specific form of the Laplace energy function is: Among them, the data item represents the cost of assigning a certain label to the pixel, refers to the cost of assigning the label 0/1 to the pixel p _ij ; ▽ ² I _ij represents the Laplacian value at the pixel p _ij ; the boundary term represents the cost of the discontinuity of adjacent pixels, that is, when two adjacent pixels are assigned different labels The cost of ; the boundary terms are divided into horizontal boundary terms and vertical boundary terms E _ij represents the edge detection result at the pixel p _ij , I _ij represents the gray value at the pixel p _ij , c is an arbitrary constant, and c>0; Step 6: Construct the network diagram; Each pixel p _ij of the image constitutes the intermediate node of the network graph, and two additional terminal nodes s and t are attached; the edge connecting the intermediate node is called nlink, and its weight is determined by the boundary term of the energy function; connecting the intermediate node with The edge of the terminal node is called tlink, and its weight is determined by the data item of the energy function; the weight of the edge (p _ij , s) is The weight of the edge (p _ij ,t) is The weight of the edge (p _ij ,p _i+1,j ) is The weight of the edge (pi _ij ,pi _,j+1 ) is Step 7: Use the augmented path-based graph cut algorithm to minimize the energy function; Two search trees S and T are established based on the network graph. The root nodes of the trees are located at the source point s and the sink point t, respectively. The nodes of the search tree are divided into two categories: active nodes and passive nodes. Active nodes can be connected by unsaturated edges. Free nodes are expanded to active nodes to realize tree growth; Step 7.1: Growth stage; The two trees continue to grow until the active nodes of the two trees meet and find a path from the source to the sink; Step 7.2, the augmentation stage; Augment the path obtained in step 7.1, the augmentation will form at least one saturated edge, the child node connecting the edge becomes an isolated node, and the trees S and T are split into multiple subtrees; Step 7.3: Adoption Phase; Find a parent node for each isolated node, if there is no parent node that meets the conditions, turn it into a free node until all isolated nodes are processed; Step 7.4: Repeat the above three steps until the two trees no longer grow and are separated by saturated edges, then the minimum cut of the graph, that is, the minimum value of the energy function, is obtained, thus realizing the final binarization of the image. 2. The low-quality document image binarization method based on background estimation and energy minimization according to claim 1, characterized in that: in step 1, a minimum mean method is used to perform grayscale on the color document image f(x, y). Preprocessing, where the preprocessing formula is: Among them, f _i (x, y) are R, G, and B color component images, respectively, and f _gray (x, y) is the transformed grayscale image. 3. the low-quality document image binarization method based on background estimation and energy minimization according to claim 1, is characterized in that: adopt nonlinear bilateral filtering algorithm to carry out image noise reduction processing in step 2, and its output pixel value Depending on the weighted combination of pixel values f(k,l) in the neighborhood S, the specific calculation formula is: Among them, the weight coefficient w(i,j,k,l) depends on the domain kernel and range kernel the product of , that is and represent the Gaussian distance variance and the Gaussian grayscale variance, respectively. 4. the low-quality document image binarization method based on background estimation and energy minimization according to claim 1, is characterized in that: adopt Canny operator to carry out edge detection to the grayscale image after bilateral filtering in step 3.1, and For each edge pixel p, find another edge pixel q corresponding to it according to its gradient direction, and the Euclidean distance between the two points ||p-q|| is the stroke width estimate of all pixels on the path of [p,q] , unless the pixel has been assigned a smaller width value, the stroke width SWE of the image is the mathematical expectation of the estimated stroke width of all non-zero pixels. The specific calculation formula is: Among them, n is the total number of non-zero value pixels in the output image s(x, y) of the stroke width transformation. 5. The low-quality document image binarization method based on background estimation and energy minimization according to claim 1, characterized in that: in step 3.2, and according to the stroke width SWE estimated in step 3.1, the simulated observation distance d is _determined . , the specific calculation formula is: d ₀ =SWE×cotθ, Among them, θ is the observation resolution angle; According to the lens imaging law and the focal length equation, the imaging height h _i on the retina when the distance from the target image is d ₀ is obtained. The specific calculation formula is: Among them, f is the distance between the human eye lens and the retina, that is, the focal length of the lens, and h ₀ is the original height of the target image. 6. The low-quality document image binarization method based on background estimation and energy minimization according to claim 1, characterized in that: in step 3.3, both closing operations adopt circular structural elements; The diameter is set to the stroke width of the image, and the diameter of the second structuring element is 12 pixels larger than the stroke width of the image. 7. The low-quality document image binarization method based on background estimation and energy minimization according to claim 1, characterized in that: in step 3.4, the observed image height is h _i when the distance target image is d ₀ , Therefore, the image after the morphological closing operation is scaled to the height h _i by bilinear downsampling; then the scaled image is restored to the original size by bilinear interpolation, and the obtained image is the estimated background image ; keep the image aspect ratio unchanged when doing image scaling.