Method and apparatus for image segmentation

Abstract

Segmentation of characters in a character set (10), made by placing a dark mark against a light background (12), is accomplished by establishing a vertical pixel projection for each pixel column in the image. The vertical pixel projections are filtered with a decay parameter so those pixel columns which contain only background have the highest projection. Thereafter, a set of "cut-points" (points of image segmentation) is obtained so that each cut-point coincides with a pixel column whose vertical pixel projection is both a local maxima and exceeds a predetermined threshold. The number of such cut-points is counted and if the number is not significantly greater than a predetermined number, the image is segmented along the cut-points. Otherwise, the vertical projections of those pixel columns coincident with the cut-points are filtered with a decreasing threshold to reduce the number of potential cut-points.

We claim: 
     
       1. A method of segmenting a character-containing image formed of a plurality of individual picture elements (pixels) to partition each character into a separate field, comprises the steps of: (a) establishing a vertical pixel projection for each column of pixels in the image in accordance with the sum of the intensities of the pixels in said column;   (b) filtering the vertical pixel projections such that the smaller the amount of character contained in each pixel column, the greater that column's vertical pixel projection;   (c) locating a plurality of potential cut-points in the image (points of image segmentation), each potential cut-point coinciding with a respective one of the pixel columns whose filtered vertical pixel projection has a local maxima and exceeds a predetermined threshold;   (d) counting the number of potential cut-points;   (e) segmenting the image at each potential cut-point if the number of potential cut-points approximates a prescribed number; otherwise   (f) filtering the vertical pixel projection of each pixel column coinciding with a respective one of the potential cut-points with a decreasing threshold to reduce the number of potential cut-points; and   (g) repeating steps (d) and (f) until the number of potential cut-points approximates said prescribed number.   
     
     
       2. The method according to claim 1 wherein the step (f) of filtering the vertical pixel projections with a decreasing threshold comprises the steps of: (a) establishing a set of "perfect" cut-points which are evenly distributed throughout the image;   (b) discarding each potential cut-point which is coincident with a pixel column whose vertical pixel projection is less than a predetermined threshold and whose location is greater than a predetermined distance from a respective one of the perfect cut-points;   (c) weighting the vertical pixel projections associated with the potential cut-points remaining after said discarding step,   (d) choosing those potential cut-points which are closest to the perfect cut-points and which are coincident with those pixel columns having the highest weights;   (e) counting the number of chosen potential cut-points;   (f) adjusting the predetermined threshold if the counted number of cut-points is less than a preselected number and repeating steps (b)-(e); otherwise   (g) creating additional potential cut-points to coincide with those pixel columns whose weighted vertical pixel projection exceeds a prescribed value;   (h) eliminating potential cut-points which are spaced within a predetermined distance from another potential cut-point;   (i) eliminating cut-points which cause inclusion of extraneous information; and   (j) counting the number of potential cut-points that remain and reexecuting step (f) if the number is less than the preselected number.   
     
     
       3. The method according to claim 1 wherein the step of filtering the vertical pixel projections such that the smaller the amount of character contained in the pixel column, the greater the column's vertical pixel projection, comprises the steps of: filtering each vertical pixel projection with a decay parameter; and   subsequently filtering the previously-filtered pixel projections with a convolution filter.   
     
     
       4. The method according to claim 2 wherein the step of weighting the vertical pixel projections comprises the steps of: computing a Gaussian profile about each perfect cut-point; and   multiplying each vertical pixel projection by the value of the closest perfect cut-point's Gaussian distribution at the location of the column associated with said vertical pixel projection.   
     
     
       5. The method according to claim 3 wherein the decay parameter is established in accordance with the ratio of the projection height of the characters to their width. 
     
     
       6. The method according to claim 3 wherein the convolution filter smooths the vertical pixel projections using the smoothing values [1,2,4,2,1]. 
     
     
       7. Apparatus for segmenting a character-containing image formed of a plurality of individual picture elements to partition each character into a separate field, comprising: (a) first means for establishing a vertical pixel projection for each column of pixels in the image in accordance with the sum of the intensities of the pixels in said column;   (c) second means, responsive to said first means, for filtering the vertical pixel projections such that the smaller the amount of character contained in each pixel column, the greater that column's vertical pixel projection;   (d) third means, responsive to said second means, for locating a plurality of potential cut-points in the image (points of image segmentation), each potential cut-point coinciding with a respective one of the pixel columns whose filtered vertical pixel projection has a local maxima and exceeds a predetermined threshold;   (e) fourth means, responsive to said third means, for counting the number of potential cut-points;   (f) fifth means, responsive to said fourth means, for segmenting the image at each potential cut-point if the number of potential cut-points approximates a prescribed number; and   (g) sixth means, responsive to said fourth means, for filtering the vertical pixel projection of each pixel column coinciding with a respective one of the potential cut-points with a decreasing threshold to reduce the number of potential cut-points when the number of cut-points is much greater than the prescribed number.   
     
     
       8. The apparatus according to claim 7 wherein the sixth means for filtering the vertical pixel project with a decreasing threshold comprises: (a) seventh means for establishing a set of "perfect" cut-points which are evenly distributed throughout the image;   (b) eighth means, responsive to said seventh means, for discarding each potential cut-point which is coincident with a pixel column whose vertical pixel projection is less than a predetermined threshold and whose location is greater than predetermined distance from a respective one of the perfect cut-points;   (c) ninth means, responsive to said eighth means, for weighting the vertical pixel projections associated with the potential cut-points remaining after discarding;   (d) tenth means, responsive to said ninth means, for choosing those potential cut-points which are closest to the perfect cut-points and which are coincident with those pixel columns having the highest weights;   (e) eleventh means, responsive to said tenth means, for counting the number of chosen potential cut-points;   (f) twelfth means, responsive to said eleventh means, for adjusting the predetermined threshold if the counted number of cut-points is less than a preselected number;   (g) thirteenth means, operative when said eleventh means has a predetermined number of cut-points greater than said preselected number, for creating additional potential cut-points, each coinciding with a pixel column whose weighted vertical pixel projection exceeds a prescribed value;   (h) fourteenth means, responsive to said thirteenth means, for eliminating each potential cut-point which is spaced within a predetermined distance from another potential cut-point;   (i) fifteenth means responsive to said thirteenth means for eliminating cut-points which cause inclusion of extraneous information;   (j) sixteenth means, responsive to said fourteenth and fifteenth means, for counting the number of potential cut-points and for causing said eleventh means to be operational if the counted number of potential cut-points is less than the preselected number.   
     
     
       9. The apparatus according to claim 7 wherein said second means for filtering the vertical pixel projections comprises: a first filter for filtering each vertical pixel projection with a decay parameter; and   a second convolution filter for subsequently filtering the vertical pixel projections filtered by the first filter.   
     
     
       10. The apparatus according to claim 8 wherein said eighth means for weighting the vertical pixel projections comprises: seventeenth means for computing a Gaussian profile about each perfect cut-point; and   eighteenth means, responsive to said seventeenth means, for multiplying each pixel projection by the value of the closest perfect cut-point's Gaussian distribution at the location of the pixel column corresponding to said vertical pixel projection.   
     
     
       11. The apparatus according to claim 9 wherein the decay parameter is established in accordance with the ratio of the projection height of the characters to their width. 
     
     
       12. The method according to claim 3 wherein the convolution filter is a five-point filter utilizing the smoothing values of [1,2,4,2,1].