Shiraz University - CSE Dept - Machine Learning Project # 3 by M.M.Haji
mehdi.haji@gmail.com

Text Segmentation Using Naive Bayes Classifiers

I. Introduction

In this project, we apply naive bayes classifier to separate text from non-text blocks in a document image. This is an important part of Document Image Analysis and Recognition, because the text must be detected first and then recognized. Hence, various approaches have been proposed to solve the problem but most of them use texture classification and image segmentation methods based on Fourier power spectrum, mean and covariance, spatial texture energy, DCT and wavelet transform (and ...) and finally a classification algorithm such as 2-means may be applied on these features to classify the image blocks as text or non-text. These methods usually does not need training data. In our new method, we generate discrete training instances from the real dataset of project 1 to learn a naive bayes classifier for the text segmentation problem. In the rest of this report we describe our new algorothm, show some experimental results, compare it with the methods described in project 2 and finally draw some conclusions.

II. Proposed Segmentation Method

In project 1 we generated 100,000 instances for the text concept, of course we don't need such a large training set here, so we selected 10,000 of them randomly and convert each attribute value to discrete (nominal) form to be appropriate for naive bayes learner. Each real attribute value will be converted to 'S2', 'S1', 'CE', 'B1' or 'B2', where 'S2' means very small, 'S1' means small, 'CE' means center, 'B1' means big and 'B2' means very big. In order to have approximately 2000 instances in each of the 5 bins for each attribute, we used different sets of rules for each of our 18 attributes as follows: (implemented  in discretize_textdata.m)

For the IsText? concept, let V1 = 'Yes' and V2 = 'No', now we need to evaluate P(Ai | Vj) for i = 1,2, ..., 18 and j = 1,2. In order to avoid zero conditional probabilities we used m-estimate with m = 1 and p = 0.2, this is done in priprob_text.m which results:

It is clear that we have no information about the source image and hence P( V1 ) = P( V2 ) = 0.5, so we can classify a new instance this way: if  P(A1 | V1 ).P(A2 | V1 ). ... P(A18 | V1 ) > P(A1 | V2 ).P(A2 | V2 ). ... P(A18 | V2 ) then input is a text block and otherwise is a non-text block. We used the same set of rule-based smoothing filters of project 2 for post processing. This simple naive classifier is implemented in remove_nontext5.m. Below you see the segmentation result of this classifier on two test images:

By some other expriments, we concluded this new method is more accurate and faster than the one we proposed in project 2. We estimated the classification accuracy of this method using 10-fold cross-validation and it was about 85%. In order to improve classification accuracy we used another version of naive bayes classifier that estimates probabilities based on analysis of the original continuous training data [2] the effect was interesting: the classification accuracy reduced to 82%.

References:

1. Tom M. Mitchell, "Machine Learning", WCB/McGraw-Hill, 1997.

2. George H. John and Pat Langley, "Estimating Continuous Distributions in Bayesian Classifiers", Proceedings of the 11'th Conference on Uncertainty in Artificial Intelligence, pp. 338-345, 1995.