Method and apparatus for image segmentation

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

The method according to claim 3 wherein the convolution filter smooths the vertical pixel projections using the smoothing values [1,2,4,2,1].

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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].