Computer vision-based methods for enhanced JBIG2 and generic bitonal compression

• US 9,047,655 B2
• Filed: 02/10/2014
• Issued: 06/02/2015
• Est. Priority Date: 08/24/2007
• Status: Active Grant

• Current Assignee: Foxit Software, Inc.
• Original Assignee: Cvision Technologies Incorporated (Foxit Software, Inc.)
• Inventors: Gross, Ari David, Meyers, Raphael, Tinna, Navdeep
• Primary Examiner(s): Seth, Manav
• Application Number:
  US14/176,754
• Publication Number:
  US 20140153838A1
• Time in Patent Office: 477 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06K 7/143 Glyph-codes
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/76 based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations

Abstract

A system and method of symbol matching may include a processor configured to determine which pixels of a first symbol are tangent pixels; for each of the determined tangent pixels, determine whether a second symbol includes a pixel corresponding to the tangent pixel that includes at least one same tangent constraint as that of the tangent pixel; accept the first and second symbols as a match based on shared tangent constraints conditional upon a determination that the second symbol includes for each of at least a subset of the tangent pixels of the first symbol a corresponding pixel that includes the at least one same tangent constraint as that of the tangent pixel; and generate a document including a single symbol that is mapped to the first and second symbols.

Claims

1. A computer-implemented image compression method comprising:

determining, in a first determining step and by a computer processor, that (a) a respective instance of each of a pair of models occurs within a respective word and (b) a same single neighboring model neighbors the instances of both models of the pair in each of the respective words of the respective instances at a same side of the respective instances;

determining, in a second determining step, by the processor, and based on the determining of the first determining step, to use a particular one of a plurality of matching algorithms for comparing the pair of models;

responsive to determining in the second determining step that the particular matching algorithm should be used, determining, in a third determining step and by the processor, whether the pair of models should be merged into a single model; and

storing, by the processor, a representation of the image, the representation including a plurality of models and being based on the determination of the third determining step.

2. The method of claim 1, wherein the determining of the second determining step is based on a determination that, with respect to each of both the right and left sides of the respective instances, a same respective single neighboring model neighbors both of the model instances.

3. The method of claim 1, wherein the particular matching algorithm is selected from the plurality of matching algorithms by the processor executing instructions that provide that the more consecutive intra-word character positions beginning from the respective model instances at which a same respective neighboring model appears for the two model instances, the looser the matching algorithm that is selected.

4. The method of claim 1, wherein the determining of the second determining step is conditional upon that a difference between the respective distances between the respective model instances to the same single neighboring model is not greater than a predetermined threshold number of pixels.

5. The method of claim 1, wherein the determining of the second determining step is conditional upon that a vertical and a horizontal positioning of the same single neighboring model relative to each of the respective model instances is the same.

6. A computer-implemented image compression method comprising:

comparing, in a first comparing step, using a first matching algorithm, and by a computer processor, each of at least a subset of a plurality of glyphs of an image to one or more other glyphs of the plurality of glyphs;

for each pair of glyphs compared in the comparing step, determining, by the processor and based on a result of the comparison, whether to group the pair of glyphs into a single one of a plurality of models;

comparing, in a second comparing step, using a second matching algorithm that is looser than the first matching algorithm, and by the processor, a first combination of a first pair of glyphs that are consecutively positioned in the image, to a second combination of a second pair of glyphs that are consecutively positioned in the image, wherein at least one of (a) the glyphs of the first position of the respective combinations are represented by different ones of the models based on the first matching algorithm and (b) the glyphs of the second position of the respective combinations are represented by different ones of the models based on the first matching algorithm; and

for each of the first and second positions for which the respective glyphs are represented by different ones of the models, merging, by the processor, the different models into a single model based on a determination in the second comparing step that the first and second combinations match.

7. A computer-implemented image encoding method comprising:

for each of at least a subset of a plurality of glyphs of an image, assigning, by a computer processor and to the glyph, a respective ‘

x’

value characterizing a horizontal position of the respective glyph and a respective ‘

y’

value characterizing a vertical position of the respective glyph;

in a first sorting step, sorting, by the processor, the at least the subset of glyphs by their respective ‘

x’

values;

in a second sorting step, sorting, by the processor, the at least the subset of glyphs by their respective ‘

y’

values;

assigning, by the processor, each of the at least the subset of glyphs to one of a plurality of ‘

x’

bins to evenly distribute the at least the subset of bins over all of the ‘

x’

bins, the distribution over the ‘

x’

bins being according to the sorted order of the at least the subset of glyphs of the first sorting step, so that a first group of the at least the subset of glyphs of the sorted order of the first sorting step are assigned to a first of the ‘

x’

bins, and each of a plurality of following groups of the at least the subset of glyphs of the sorted order of the first sorting step are assigned to respective following ones of the ‘

x’

bins;

assigning, by the processor, each of the at least the subset of glyphs to one of a plurality of ‘

y’

bins to evenly distribute the at least the subset of bins over all of the ‘

y’

bins, the distribution over the ‘

y’

bins being according to the sorted order of the at least the subset of glyphs of the first sorting step, so that a first group of the at least the subset of glyphs of the sorted order of the first sorting step are assigned to a first of the ‘

y’

bins, and each of a plurality of following groups of the at least the subset of glyphs of the sorted order of the first sorting step are assigned to respective following ones of the ‘

y’

bins;

for each of the at least the subset of glyphs for which a number of others of the at least the subset of glyphs that are each assigned to both the ‘

x’

bin and the ‘

y’

bin to which the respective glyph is assigned is at least a minimum threshold, comparing, by the processor, characteristics of the respective glyph to only those others of the at least the subset;

for each of the at least the subset of glyphs for which a number of others of the at least the subset of glyphs that are each assigned to both the ‘

x’

bin and the ‘

y’

bin to which the respective glyph is assigned is less than the minimum threshold;

comparing, by the processor, the respective glyph to other glyphs assigned to both the ‘

x’

bin and the ‘

y’

bin to which the respective glyph is assigned; and

iteratively moving outward, by the processor, one level at a time to all next-level combinations of the ‘

x’

bins and ‘

y’

bins that neighbor the bin combination to which the respective glyph is assigned to compare the characteristics of the respective glyph to others of the at least the subset of glyphs included in those other neighboring bin combinations until the number of others of the at least the subset of glyphs to which the respective glyph is compared satisfies the minimum threshold; and

storing a representation of the image based on the comparisons;

wherein the levels of the bin combinations are defined by an arrangement of the ‘

x’

bins along one of a horizontal axis and a vertical axis and an arrangement of the ‘

y’

bins along the other of the horizontal axis and the vertical axis, thereby forming cells that each corresponds to a respective bin combination of one of the ‘

x’

bins and one of the ‘

y’

bins, with eight neighbors one level out surrounding each one of the cells that is not an edge cell, each next level outward including eight more cells than the immediately preceding level prior to reaching an edge of the table of cells.

8. The method of claim 7, wherein a number of ‘

x’

bins to which all of the at least the subset of glyphs are assigned is equal to a number of ‘

y’

bins to which all of the at least the subset of glyphs are assigned.

9. The method of claim 7, wherein, with respect to each of the at least the subset of glyphs, the assigning of the respective ‘

x’

value to the glyph includes calculating an ‘

x’

centroid value of the respective glyph with respective to ‘

x’

values of those pixels of its mapping that are considered to be on, and the assigning of the respective ‘

y’

value to the glyph includes calculating a ‘

y’

centroid value of the respective glyph with respective to ‘

y’

values of those pixels of its mapping that are considered to be on.

10. The method of claim 8, wherein, with respect to each of the at least the subset of glyphs:

the assigning of the respective ‘

x’

value to the glyph further includes;

for each of those pixels of the mapping of the respective glyph that are considered to be on;

subtracting the ‘

x’

centroid value from the ‘

x’

value of the respective pixel to obtain a respective difference; and

squaring the respective difference to obtain a respective ‘

x’

difference value; and

calculating an average of the squared ‘

x’

difference values, the average being the assigned respective ‘

x’

value; and

the assigning of the respective ‘

y’

value to the glyph further includes;

for each of those pixels of the mapping of the respective glyph that are considered to be on;

subtracting the ‘

y’

centroid value from the ‘

y’

value of the respective pixel to obtain a respective difference; and

squaring the respective difference to obtain a respective ‘

y’

difference value; and

calculating an average of the squared ‘

y’

difference values, the average being the assigned respective ‘

y’

value.

11. The method of claim 10, wherein, with respect to each of the at least the subset of glyphs:

the ‘

x’

centroid value of the glyph is calculated by adding all ‘

x’

values for each of the on pixels of the glyph, and dividing the sum by the number of on pixels of the glyph to obtain an average, the average being the respective ‘

x’

centroid value; and

the ‘

y’

centroid value of the glyph is calculated by adding all ‘

y’

values for each of the on pixels of the glyph, and dividing the sum by the number of on pixels of the glyph to obtain an average, the average being the respective ‘

y’

centroid value.

12. The method of claim 7, wherein, with respect to each of the at least the subset of glyphs, the assigning of the respective ‘

x’

value to the glyph includes calculating a second order ‘

x’

moment value of the respective glyph, and the assigning of the respective ‘

y’

value to the glyph includes calculating a second order ‘

y’

moment value of the respective glyph.

13. The method of claim 7, wherein each of the glyph comparisons includes calculating an XOR distance between the compared glyphs.

14. The method of claim 13, further comprising:

for each of the at least the subset of glyphs for which one or more of the comparisons are performed, populating a respective list of the XOR distances of the respective glyph to other glyphs to which the respective glyph was compared in the one or more of the comparisons, wherein the list is limited no more than a predetermined maximum threshold number of closest XOR distances, wherein the stored representation is based on the lists.

15. A computer-implemented image encoding method comprising:

grouping, by a computer processor, glyphs of the image into bins based on respective second order ‘

x’

moment values of the glyphs and respective second order ‘

y’

moment values of the glyphs, the bins including ‘

x’

bins populated with respective sub-sets of the glyphs based on the second order ‘

x’

moment values of the glyphs and ‘

y’

bins populated with respective sub-sets of the glyphs based on the second order ‘

y’

moment values of the glyphs, and combinatory bins that are each formed by a respective intersection of a respective one of the ‘

x’

bins and a respective one of the ‘

y’

bins when the ‘

x’

bins are arranged along one of a horizontal axis and a vertical axis and the ‘

y’

bins are arranged along the other of the horizontal axis and the vertical axis, wherein boundaries of the ‘

x’

bins are selected to provide a uniform distribution of the glyphs over the ‘

x’

bins and boundaries of the ‘

y’

bins are selected to provide a uniform distribution of the glyphs over the ‘

y’

bins;

for each of the grouped glyphs;

calculating, by the processor, an XOR distance of the respective glyph to all other glyphs sharing the same combinatory bin as that of the respective glyph;

at least one of;

responsive to determining that the number of all other glyphs that share the same combinatory bin as that of the respective glyph is less than a predetermined threshold, calculating, by the processor, an XOR distance of the respective glyph to all other glyphs that are within those 3×

3 combinatory bins that immediately surround the combinatory bin to which the respective glyph has been assigned; and

responsive to determining that the number of all other glyphs that share the same combinatory bin as that of the respective glyph in addition to the number of all other glyphs in the 3×

3 surrounding combinatory bins is less than the predetermined threshold, calculating, by the processor, an XOR distance of the respective glyph to all other glyphs that are within those 5×

5 combinatory bins that immediately surround the 3×

3 surrounding combinatory bins; and

storing, by the processor, a list of no more than a predetermined maximum number of those other glyphs for which the shortest XOR distances to which from the respective glyph are calculated in the calculating step; and

generating, by the processor, a representation of the image based on the stored lists.

16. The method of claim 15, wherein the grouping is performed using at least one cumulative histogram of the second order ‘

x’ and

‘

y’

moment values.

17. The method of claim 15, wherein the generating of the representation includes, for each of at least one of the grouped glyphs:

determining, in a first determining step and by the processor, a difference value between the respective glyph and a glyph of the shortest XOR distance to the respective glyph, of the list stored for the respective glyph;

comparing, by the processor, the determined difference value to an area within a bounding box of the respective glyph;

based on the comparison, determining, in a second determining step and by the processor, that the respective glyph is to be encoded by referencing the glyph of the shortest XOR distance; and

encoding the respective glyph based on the determination of the second determining step.

18. The method of claim 17, wherein:

the comparison is performed by calculating Pdiff+k*((Hdiff)+(Wdiff)), and comparing a result of the calculation to the area;

Pdiff is a difference in on pixels between the two glyphs;

Hdiff is a difference in height between the two glyphs;

Wdiff is a difference in width between the two glyphs; and

k is a predetermined constant value.

19. The method of claim 18, wherein the determining of the second step is based on a set of instructions which, when executed by the processor, cause the processor to determine to perform the encoding of the respective glyph by referencing the glyph of the shortest XOR distance in an instance where the result of the calculation is less than a predetermined threshold percentage of the area, and cause the processor to determine not to perform the encoding of the respective glyph by referencing the glyph of the shortest XOR distance in an instance where the result of the calculation is at least the predetermined threshold percentage of the area.

20. The method of claim 18, wherein Pdiff is the XOR difference between the first and second glyphs.

21. The method of claim 17, wherein:

the comparison is performed by calculating Pdiff+k*((Hdiff*M1)+(Wdiff*M2)), and comparing a result of the calculation to the area;

Pdiff is a difference in on pixels between the two glyphs;

Hdiff is a difference in height between the two glyphs;

Wdiff is a difference in width between the two glyphs;

k is a predetermined constant value;

M1 is a predetermined constant value;

M2 is a predetermined constant value; and

at least one of M1 and M2 is greater than 1.

22. A computer-implemented image compression method comprising:

for each of at least a subset of a plurality of models that each represents a respective symbol formed of on pixels, adding, by a computer processor, at least one of blank rows and blank columns of off pixels to the respective model; and

generating, by the processor, a representation of an image including pointers to the plurality of models with respective image location information.

23. The method of claim 22, wherein the adding of blank rows includes adding blank rows of off pixels to respective bottoms of those of the plurality of models that are non-descender models to ensure that new respective bottoms of the non-descender models, obtained by the addition of the blank rows at the respective bottoms, are of a same bottom positioning as that of those of the plurality of models that are descender models.

24. The method of claim 22, further comprising:

determining a ratio of glyphs of the image to models used for representing the glyphs, wherein the adding of the blank rows is performed conditional upon that the determined ratio satisfies a minimum threshold value.

25. A computer-implemented image compression method comprising:

determining, in a first determining step and by a computer processor, a difference between a first glyph and second glyph;

comparing, by the processor, the determined difference to an area within a bounding box of the first glyph;

based on the comparison, determining, in a second determining step and by the processor, that the first glyph is to be encoded by referencing the second glyph; and

encoding the first glyph based on the determination of the second determining step.

26. The method of claim 25, wherein the difference is an XOR difference.

27. The method of claim 25, wherein:

the comparison is performed by calculating Pdiff+k*((Hdiff)+(Wdiff)), and comparing a result of the calculation to the area;

Pdiff is a difference in on pixels between the first and second glyphs;

Hdiff is a difference in height between the first and second glyphs;

Wdiff is a difference in width between the first and second glyphs; and

k is a predetermined constant value.

28. The method of claim 27, wherein the determining of the second step is based on a set of instructions which, when executed by the processor, cause the processor to determine to perform the encoding of the first glyph by referencing the second glyph in an instance where the result of the calculation is less than a predetermined threshold percentage of the area, and cause the processor to determine not to perform the encoding of the first glyph by referencing the second glyph in an instance where the result of the calculation is at least the predetermined threshold percentage of the area.

29. The method of claim 27, wherein Pdiff is an XOR difference between the first and second glyphs.

30. The method of claim 25, wherein:

the comparison is performed by calculating Pdiff+k*((Hdiff*M1)+(Wdiff*M2)), and comparing a result of the calculation to the area;

Pdiff is a difference in on pixels between the first and second glyphs;

Hdiff is a difference in height between the first and second glyphs;

Wdiff is a difference in width between the first and second glyphs;

k is a predetermined constant value;

M1 is a predetermined constant value;

M2 is a predetermined constant value; and

at least one of M1 and M2 is greater than 1.

31. A computer-implemented image compression method comprising:

grouping glyphs of an image into a plurality of representative models;

(b) for each distinct pair of the plurality of models, counting a number of co-occurrences in the image of glyphs represented by the pair of models neighboring each other in a same order, with a same vertical difference between the glyphs, and a same horizontal difference between the glyphs;

(c) subsequently, determining for which of all pairs of models a greatest number of co-occurrences are counted in the counting step;

(d) determining whether the number of co-occurrences, counted for the pair determined to be that for which the greatest number of co-occurrences were counted, is at least a predetermined threshold minimum;

(e) responsive to determining that the number of occurrences is at least the predetermined threshold minimum, generating a new composite model, for inclusion as one of the plurality of representative models, the new composite model corresponding to the pair of models, for which the greatest number of co-occurrences were determined to have been counted, as a whole;

(f) iteratively repeating steps (b)-(e) until an iteration in which there is no pair of models for which a counted number of co-occurrences is at least the predetermined threshold minimum; and

(g) encoding the image using the plurality of representative models.

32. The method of claim 31, wherein a predetermined amount of tolerance is allowed between the vertical difference and a predetermined amount of tolerance is allowed between the horizontal difference for two glyph pairs to be considered co-occurrences.