CROSS REFERENCE TO RELATED APPLICATION

This application claims the priority and benefit of India provisional patent application 155/CHE/2008 filed on 18/01/2008, and entitled "Separation of Image Regions in Document Processing", which is incorporated herein by reference.

BACKGROUND

1. Field of the Invention

The present invention relates generally to image processing and particularly to a technique for classifying a digital image portion.

2. Related Art

A digital image refers to a two dimensional arrays of picture elements ' (pixels). Each pixel may be assigned with a numerical value representing the brightness and/or color at the corresponding location in the image. The numerical value is often represented using binary digits (Bits). For example, each pixel may be represented using number of bits (8 bits, 24 bits) depending on the Image type.

In case of monochrome images, numerical value (representing grey levels) of each pixel may be represented using 8 bits. Similarly, in case of color digital images, numerical value (corresponding to the chrominance and/or intensity of such chrominance as well known in the field of art) of each pixel may be represented using higher number of bits (for example, 24 bits).

Characteristics (for example, color variations, edges, and variations in intensity, variation of grey levels) often differ from one portion of the image to the other. Accordingly, portions of the image are classified based on the desired predetermined characteristics. Such classification enables efficient processing of image data (bits of the pixels) for various applications.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be described with reference to the following accompanying drawings.

Figure 1 is a block diagram of image processing system illustrating example environment in which various aspects of the present invention may be
implemented.

Figure 2 is a block diagram illustrating a digital image with multiple portions.

Figure 3 is a flowchart illustrating manner in which a digital image portion is classified in an embodiment of the present invention.

Figure 4A is an image depicting example image portions.

Figure 4B depicts visual representations of bit planes of the image portions.

Figure 5 is block diagram illustrating the classification of a document image in one embodiment of the present invention.

Figure 6 depicts an example document image (8 bit scan of a document).

Figure7 is flowchart illustrating the manner in which classification of text portion and picture portion is performed in one embodiment of the present invention.

Figure 8 A illustrate an example visual indication of text-picture map.

Figure 8B illustrate text-picture map after filtering operation/post-processing.

Figure 9 depicts classified/separated text portion.

In the drawings, like reference numbers generally indicate identical, functionally similar, and/or structurally similar elements. The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number.

DETAILED DESCRIPTION

1. Overview

According to an aspect of the present invention, a received image portion is classified/ separated by analyzing the bit planes of the received image portion. In one embodiment, bit planes are extracted for the received image portion and the bit planes are compared. The image portion is then classified based on the result of such comparison.

According to another aspect of the present invention, an average value is computed for a set of higher order (corresponding to most significant bits) bit planes. The average value is then compared in the descending order for a predetermined number of bi planes. The image portion is then classified based on the comparison.

Yet another aspect of the present invention determines the correlation among set of predetermined number of bit planes. The image portion is then is classified based on the correlation values and/or the variation in the correlation between the bit planes.

Several aspects of the invention are described below with reference to examples for illustration. It should be understood that numerous specific details, relationships, and methods are set forth to provide a full understanding of the invention. One skilled in the relevant art, however, will readily recognize that the invention can be practiced without one or more of the specific details, or with other methods, etc. In other instances, well-known structures or operations are not shown in detail to avoid obscuring the features of the invention.

2. Example Environment

Figure 1 is a block diagram of image processing system illustrating example environment in which various aspects of the present invention may be implemented. Image processing system 100 is shown comprising image source 110, memory 120, printer 140, processor 150, storage 160, transmitter 170 and display device 180. Each block is described below in further detail.

Image source 110 provides digital image on path 115 for processing. Image source 110 may represent any known image sources such as scanner, digital camera, storage units (with images stored), and/or any communication device transmitting/receiving an image over a communication channel. The digital image provided on path 115 may represent a color and/or monochrome images.

Transmitter 170 transmits image data (received on path 157) on a channel using any of the known transmission techniques. For example, transmitter may encode the image data in accordance with the transmission standards such as 802.11, OFDM, WiMAX, Ethernet etc.

Printer 140 receives the image data on path 154 and prints the corresponding image on a desired material. Printer may be implemented to print the images in grey scale or in color. Printer 140 may be implemented to receive the image data in a suitable format (for example, JPEG, TIF, BMP, postscript and PDF).

Printer may convert these formats to halftone format for printing purpose. Alternatively, processor 150 may perform half tone format conversion and send on path 154 for printing. Halftone conversion may be implemented using any of the known techniques such as error diffusion, ordered dither etc., to ensure fidelity and quality of the printed image.

Storage 160 stores the image data received on path 156. Storage 160 may maintain index to determine the location of the image and retrieve the desired image. Storage 160 may receive image data in various formats.

Display device 180 displays the image data (received on path 158). The display device 180 may be implemented to receive the image data in a suitable format (for example, JPEG, GIF, TIF, BMP). Display device 180 may be implemented in a known way.

Processor 150 divides the received digital image into multiple portions. Processor 150 then performs operations (for example, image compression, filter operation, image format conversion) on each portion. The operation is performed in conjunction with the desired application implemented on image processing system 100. Memory 120 operates as temporary storage for the processor 150. Accordingly, processor 150 may store the image data and other intermediate data while performing the desired operation.

Manner in which processor 150 operate in an embodiment is described below with an example image 200 (received on path 115).

Figure 2 is a block diagram illustrating a digital image with multiple portions. Digital image 200 is shown containing image portions 210, 220, 230 and 230. Characteristic of each image portions 210, 220, 230 and 240 are not similar. For example, image portion 210 may represent a picture (such as a grayscale, a color reproduction of a photograph, graphics in grayscale or color).

Image portion 220 may represent a text (typeset letters, alphabets, symbols in any language, and graphics) on a plain background. Similarly, image portion 230 may represent a background (all pixels having constant value) and portion 240 may represent a graph (bar pie charts or curves or scatter plots rendered in black and white).

In order to perform a desired operation on image 200, processor 150 determines the image portion 210, 220, 230 and 240 by classifying image 200 based on the characteristics. Operation on each image portions 210, 220, 230, and 240 is performed by adopting an approach that is suitable for corresponding image portion. Often classification techniques detect the presence/absence of desired characteristics.

Example prior classification techniques are described in paper by author R. M. Gray and J. Li., entitled Context based multi scale classification of document images based on wavelet coefficient distributions. IEEE Transactions on Image Processing, 13(9): 1604-1616, Sep. 2000. and by author R. Cattoni, T. Coianiz, S. Messelodi, and C. Modena., entitled Geometric layout analysis techniques for document image understanding: a review. Technical report, IRST, Trento, Italy, 1998.

Such prior approaches require higher processing power and time. Further, the prior approaches may classify image portion without considering the desired characteristics. Such classification may lead to undesired results. Various aspect of the present invention overcomes at least some of the disadvantages noted above.

3. Bit Plane based classification

Figure 3 is a flowchart illustrating manner in which a digital image portion is classified in an embodiment of the present invention. The flowchart is described with reference to Figure 1 merely for illustration. The extension of the approaches to other image processing systems will be apparent to one skilled in the relevant art by reading the disclosure provided herein, and such implementations are contemplated to be covered by various aspects of the present invention. The flowchart begins in step 301 and control passes to step 310.

In step 310, processor 150 receives an image portion. In one embodiment, processor 150 may receive image and divide the image into multiple image blocks (for example, macro blocks of KxL pixels) and image blocks may be stored in memory 120. In an alternative embodiment, processor 150 may directly receive the image blocks from any image sources.

In step 330, processor 150 extract/construct bit planes of the received image portion. Processer 150 may construct/store predetermined number of bit planes of the image portion. For example, if each pixel in the image portion is represented using N bits (BN.i, BN_2, — Bj, ~ Bo), N number of bit planes may be constructed/obtained for each bit (Bj) as well known in the field of art.

Briefly, an /'h bit plane represents array/matrix of /* bit, 5, of all the pixels in the received image. In case of Kx.L image block, /'h bit plane represents a K x L matrix of value Bj of the /* bit of corresponding pixels in image block. Processor 150 may construct more than one bit planes.

In step 360, processor 150 compares the bit plane and generates a comparison result. The comparison may be performed with the parameters or elements of each bit plane. Parameter such as average value may be computed using the bit value of the bit planes and the parameters may be compared against a predetermined value. Alternatively bit planes may be compared observing the elements (each bit in the bit pane) and its distribution.

In one embodiment, correlation/similarity between bit planes are computed and compared. Correlations between two or more bit planes may be computed using any known/defined correlation technique.

In one embodiment of the present invention, average correlation between ith and jth bit planes of an image block B of size K x L is computed as;

Where C(i,j,m,n)is given by:

Wherein BXm,ri) and Bj(m,n) represent bit values for the location (m,n) in the ith and the jth bit planes, respectively, wherein B,(m,n) and Bj(m,n) can take a value of 1 or 0.

From above equation 1 and 2, it may be appreciated that, a image block with highly correlated bit planes may have an average correlation value closer to 1.0 while that of an image block having lower correlation between bit planes may result in an lower average correlation closer to 0.0.

In step 370, processor 150 classifies the Image portion based on the result of the comparison. In case of computation of correlations as described above, the image portion may be classified by comparing the correlation value with a predetermined threshold. The flowchart ends in step 399.

Due to above approach, at least some image portions are classified with less error. Further, due to above approach classification of the image portion is accomplished with reduced complexity. The approach described above (flowchart of Figure 3) is further illustrated with reference to Figure 4A and 4B.

Figure 4A is an example image containing image portions 410 and 450. Image portion 410 exhibits the characteristic of a text (here onwards referred to as text portion) and image portion 450 exhibit characteristic of a picture (here onwards referred to as picture portion) as well known in the field of art. Text portion 410 and picture portion 450 may represent example image block received according to step 310.

Figure 4B illustrates bit planes of each portion 410 and 450. Blocks 410A- 410C respectively depicts visual representation of bit planes of N-l, N-2 and N-3 bit position of text portion 410 (N-l bit is the most significant bit of the sequence N-l,....1,0). Similarly, visual representation 450A-450C respectively corresponds to the bit planes of N-l, N-2 and N-3 Bit position of picture portion 450.

It may be appreciated that similarity/correlation among bit 410A through 410C appear to be higher compared to bit planes 450A through 450C. Degree of correlation may be determined using any of the known technique. Accordingly, portions 410 and 450 may be classified/ separated for processing using the different approaches.

Various aspect of the present invention is described below with reference to an example imaging application below.

4. An Example Embodiment

Figure 5 is block diagram illustrating the classification of a document image in one embodiment of the present invention. The block diagram is shown containing document image source 510, image processor 550, two tone imaging device 570, and storage 580. Image processor 550 is shown further containing image classification 540, half toning block 560, and image compression block 565. Each block is further described below.

Image source 510 provide a document images (which can be composed of a heterogeneous portions such as (but not restricted to) text, picture and graphics) a well known image type in the art. The document image may be generated by scanning a document or retrieving a document from the storage.

An example document image (8 bit scan of a document) is depicted in Figure 6. Shown there document image 600 containing a text portion 650 and picture portion 630. Text portion 650 represents a portion containing black or white letters or graphical symbols on a plain complimentary background. While picture portion 630(other portions that are not text), represents a continuous variation in the texture and pixel value.

Continuing with reference to Figure 5, two tone imaging device 570 takes as input image data in a two tone format on path 567 and generates two tone images on an object. For example, a monochrome printer prints an image with two tones "dot" and "no dot" to represent an image on an object. Two tone imaging device 570 receives the image data (from processor 550) in a suitable format such as half tone format. Techniques such as error diffusion, ordered dither, dynamic thresholding may be used for generating the halftone formats of the image.

Storage device 580 receives the image data in a compressed format on path 568 and stores the data in a memory as image files. Storage device may represent any of the mass storage devices such as hard disc (secondary storage) or memory cards. The interface 568 may be implemented using corresponding data transfer bus or protocol.

Processor 550 provides two tone image data and compressed image data respectively on path 567 and 568. Processor 550 performs various operations on the received (on path 515) image in order provide the required data on path 567 and 568. Operation of the processor is further described below with reference to the image classification blocks 540, half toning 560, and image compression block 565.

Halftoning block 560 receives text portion and picture portion from the image classification block 540. Half toning block 560 adopts a first and a second half toning techniques (approach) to respectively convert the text portion and picture portion to halftone. Suitable halftone approach is used to retain the fidelity of the image when printed or displayed on an object.

First and second approaches are suitably selected to provide a desired performance on the text and picture portion. For example dynamic thresholding approach may be used for converting a text portion to halftone format, while error diffusion may be used to convert the picture portion to halftone format.

Similarly, Image compression block 565 receives text portion and picture portion. Image compression block 565 adapts a first and a second compression technique respectively compresses the text portion and picture portion. The first and second compression approaches are suitably selected to provide a desired performance on the text and picture portion. For example The JPEG algorithm can be suitably adapted to best compress the text and the picture portions.

Image classification block 540 segments the received document image (received on path 515) into text portion and picture portion using bit plane correlation approach described above with reference to Figure 3. Image classification block 540 then provides the text portion and picture portion to halftoning block 560 and image compression block 565.

In one embodiment, Image classification block 540 receives document image in grey scale (pixels are represented in grey scale). In case of a color images, Image classification block 540 converts pixels to corresponding grey scale values using any known technique.

Image classification block 540 divides the received document image into non overlapping blocks of M x M (or any other dimensions/shapes) pixels and indexes its coordinates (I, J) that indicate its relative position in the input document image. Image classification block 540 initializes matrix, T is initialized to store the average correlation numbers for each block. Image classification block 540 then decomposes each block (I, J) into its bit planes.

Manner in which each blocks (I, J) may be determined as text or picture portion is illustrated below with reference to Figure 7.

5. Example Bit plane Correlation

Figure 7 is flowchart illustrating the manner in which classification of text portion and picture portion is performed in one embodiment of the present invention. The flowchart is described with reference to a document image for illustration. Wherein the portion of image with alphanumeric characters and graphics printed in black or white against plane complementary (white or dark respectively) background is considered as text. Likewise, all other portions that do not fall under the above defined text are considered as picture portions.

Accordingly, characteristics that determine the above defined text and pictures are identified and used for classifying/separating text portions and picture portion as described below. Flowchart begins in step 701 and control passes to step 710.

In step 710, image classification block 540 receives document image block and generates bit planes. The description below is provided for an example block of M x M (or any other dimension or shape) pixels merely for illustration. Considering a document image block (I, J) is received and each pixel in the block is represented using a N bits, Number of bit planes may be represented as bit planes b0(i,j), bi(i,j),.... bN_i(i,j). N-l th bit is the most significant bit.

Similarly, bit value of a pixel on m th row and n th column in each bit plane may be respectively represented as bo(i,j) (m,n), bi^j) (m,n), .... bN-i(i,j) (m,n). For example, bj(U) (m,n) represents a bit value of the pixel (m,n) in i bit plane of (I,J) block.

In step 720, image classification block 540 computes the mean of N-l th bit plane for the received block. Mean of the bit plane is computed as Mean of bit values of all the pixels (m,n) in bN_1(i,j) bit plane. The mean value may be represented as fjN.|(I,J).

In step 730, image classification block 540 checks if all bits in the highest plane are 1. nN-i(IJ)=l represents all bits in the highest plane have value 1. Control passes to step 740 if |JN.i(I,J)=l. Else control passes to step
735.

In step 735, image classification block 540 checks if all bits in the highest plane are 0. pN.](I,J)=0 represents all bits in the highest plane have value 0, control passes to step 760 if |jN_i(I,J)=0. Else control passes to step 780

In step 740, image classification block 540 computes the mean for the lower bit planes. Mean for k th bit plane is represented as |Jk(I,J). Mean for lower bit plane may be computed by selecting value of k such that N-l > k > 0

In step 745, image classification block 540 determines a bit plane where mean is less than a predetermined value. Such determination may be performed iteratively by computing Mk(IJ) for each k descending from k =N-2. Iteration is stopped for k=p where (Jp(U) ^ MTI wherein |JTi is a predetermined threshold value. |JTI is chosen to be a value close to 1, such as 0.8. It is used to determine, how many consecutive bit planes starting from bit plane N-l have virtually no variation in pixel value.

In step 750, image classification block 540 classifies the block as picture block if the determined bit plane is above a predetermined bit plane. If p computed in the step 745 is less than a threshold PT then classify the block as text block. On the other hand, the block is classified as picture block if p is greater than threshold PT. The block (I, J) classified as text may be indexed and stored as T(I, J) = 1. The block is indexed and stored as T(I, J) = 0 otherwise. Control then passes to step 799.

In step 760, image classification block 540 computes the mean for the lower bit planes. Mean for lower bit plane may be computed using approach described with reference to step 740. Briefly, mean for lower bit plane may be computed by selecting value of k such that N-l > k > 1.

In step 765, image classification block 540 determines a bit plane where mean is greater than a predetermined value. Such determination may be performed iteratively by computing |Jk(I,J) for each k descending from K =N-2. Iteration is stopped for k=q such that pq(I,J) > |JT2 wherein |JT2 is a predetermined threshold value. |JT2 is chosen to be a value close to 0, such as 0.2. It is used to determine, how many consecutive bit planes starting from bit plane N-l have virtually no variation in pixel value.

In step 770, image classification block 540 classifies/assigns block as picture if the determined bit plane is above a predetermined bit plane. If q computed in the step 745 is less than a threshold QT then image classification block 540 classifies the block as text block. On the other hand, the block is classified as picture block if q is greater than threshold QT. The block (I, J) classified as text may be indexed and stored as T (I, J) = 1, block is indexed and stored as T(I, J) = 0 otherwise (as noted above). Control passes to step 799.

In step 780, image classification block 540 computes the average correlations between bit planes. Average correlation is computed using
equation 1 described above. The average correlation may be computed between selected bit planes.

In one embodiment average correlations is computed for all the combinations between bit planes bN-i(i,j) bN.2(ij) bN-2(i,j) and bN.3(i,j)- For example average correlation C(N-l,N-2, (I,J)) is computed between bit planes bN-i(i,j) and bN.2(u). Similarly, average correlations C(N-l,N-3, (I,J)), C(N-l,N-4, (I,J))> C(N-2,N-3, (I,J)), C(N-2,N-4, (I,J)), and C(N-3,N-4, (I,J)) are computed.

In step 790, image classification block 540 classify the image block as picture if based on predetermined set of conditions. In one embodiment, received block (I,J) is classified as text block if C(N-l,N-2, (I,J)) > 0.9 and difference between maximum and minimum correlation values computed is greater than 0.9. The received block is indexed and assigned as T(I,J)=0.

On the other hand, if the above conditions are not satisfied, image classification block 540 indexes and assigns T(I,J) as:

T(I,J) = median[C(N-l,N-3, (I,J)), C(N-l,N-4, (I,J)), C(N-2,N-3, (I,J)), C(N-2,N-4, (I,J)), and C(N-3,N-4, (I,J)))]. .Control passes to step 799. Flowchart ends in step 799.

Accordingly, T(I,J) for all values of I (0 to L) and for all values of J (0 to K) computed in steps 750, 770 and 790 generate L X K text-picture map of T(I,J). An example visual indication of such text-picture map is illustrated in Figure 8A. The map is computed for document image 600. the document image 600 is decomposed into 16 X 16 blocks. The T(I,J) is computed by setting QT and PT =4, |JTi=0.8 and MT2= 0.2.

The lighter pixels in the map indicate that the corresponding blocks have a higher average correlation. This in turn means that these blocks have a higher probability of being text blocks. Likewise, darker pixels indicate a lower average correlation for the corresponding blocks. This means such blocks have a higher probability of being image blocks.

The effect of misclassification (such as where text blocks could be falsely identified as having a higher probability of being image blocks and vice versa) can be mitigated using any known approaches. These approaches make use of the correlation number assigned to/computed for the neighboring blocks as a context to minimize misclassification .

In one embodiment, min and max filters using a window size of 3X3 pixels are applied on the text-picture map. The results of such an operation are shown in Figure 8B. At this point, a threshold is computed using Otsu's method described in paper titled N. Otsu. A threshold selection method from gray-level histograms. IEEE Transactions on System, Man and Cybernetics, 9(l):62-66, 1979. This histogram-based method is invoked after excluding 0 and 1 values from T.

It may be appreciated from the forgoing description that, a text block will have a correlation of 1 or close to 1. Likewise an image block may have an average correlation of close to zero. It therefore seems natural to have the threshold around 0.5. Based on this, image classification block 540 set the computed correlation value to 0.4 if the computed threshold is less than 0.4 Likewise if the threshold is computed to be greater than 0.6 then it is brought down to 0.6.

Image classification block 540 classifies the image block with a correlation number above the threshold as a text block while a block with correlation number below the threshold is provided as an image block. Figure 9 is an example set of blocks separated as text block using the above approach. It may be appreciated that, text portion of the document image is provided as text while picture portion is provided as picture portion. Separated picture portion and text portions are provided to image half toning block 560 and image compression block 565.

7. Conclusion

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

I/we claim,

1. A method of classifying a portion of a digital image comprising;

receiving an image portion;

extracting plurality of bit planes of said image portion;

comparing first set of bit planes, wherein said first set of bit planes is comprised in said plurality of bit planes; and

classifying said image portion based on result of said comparing.

2. The method of claim 1 further comprising;

computing a numerical value for each bit plane in said first set of bit planes, wherein said numerical value is computed using plurality of bits in corresponding bit plane,

wherein said comparing compares said numerical value of each bit plane in said first set of bit planes.

3. The method of claim 1 further comprising;

computing correlation between bit planes in said first set of bit planes; and

wherein said comparing compare correlation value with a predetermined value.

4. The method of claim 3, wherein said correlation between ith bit plane and
jth bit plane of a image portion B is computed as;

Wherein C(i,j,B) average correlation between ith and jth bit plane of image portion B, KXL represents the dimension of the said image portion B, and

Wherein B,(m,n)and Bj{m,n) represent bit values for the location (m,n) in the ith and the jth bit planes

5. The method of claim 4, wherein, said correlation C(i,j,B) is computed only if an average value of bit planes is less than a threshold for a predetermined set of bit planes.

6. The method of claim 5, further comprising;

Computing plurality of correlations wherein, said plurality of correlation is computed as correlation C(i,j,B) between all combination of p higher order bit planes.

7. The method of claim 5, further comprising;

Classifying said image portion as text portion if maximum difference between said pluralities of correlation is substantially equal to 0.9

8. The method of claim 2 wherein said numerical value represents the average of all the bits in corresponding bit plane.

9. The method of claim 8, further comprising;

computing said average of the most significant bit plane;

determining if the computed average is equal to a value 1;

computing a average value of K number of bit planes if computed average value is equal to 1,wherein said K number of bit planes are selected in the order of descending from said most significant bit plane; and classifying said image portion as text portion if said K is greater than a predetermined value P

10. The method of claim 8, further comprising;

computing said average of the most significant bit plane;

computing a average value of K number of bit planes if computed average value is equal to 0, wherein said K number of bit planes are selected in the order of descending from said most significant bit plane; and

classifying said image portion as text portion if said K is less than a predetermined value Q