Representing documents with runlength histograms
View Patent ↗An apparatus and method are provided for generating a representation of an image which may be used in tasks such as classification, clustering, or similarity determination. An image, such as a scanned document, in which the pixel colorant values are quantized into a plurality of colorant quantization levels, is partitioned into regions, optionally at a plurality of different scales. For each region, a runlength histogram is computed, which may be a combination of sub-histograms for each of the colorant quantization levels and optionally each of plural directions. The runlength histograms, optionally normalized, can then be combined to generate a representation of the document image.
1. A method for generating a representation of an image comprising:
receiving an image for which a representation is to be generated;
partitioning the image into a plurality of regions;
for each of the plurality of regions of the image, computing a runlength histogram;
generating a representation of the image based on the runlength histograms, comprising concatenating the runlength histograms from the plurality of regions; and
outputting the representation of the image.
2. The method of claim 1 , wherein the regions are at a plurality of scales, whereby at least some of the regions are at least partially overlapping.
3. The method of claim 1 , further comprising normalizing the image prior to computing the runlength histograms.
4. The method of claim 1 , wherein the computing of the runlength histogram comprises computing a runlength sub-histogram for each of a plurality of pixel colorant quantization levels and combining the sub-histograms.
5. The method of claim 4 , further comprising, prior to the computing of the runlength histograms, quantizing colorant values of pixels of the image into a plurality of quantization levels.
6. The method of claim 1 , wherein the computing of the runlength histogram comprises, for each region, computing a runlength sub-histogram for each of a plurality of directions.
7. The method of claim 1 , wherein each runlength histogram comprises a histogram of a number of runs of pixels of a same pixel colorant quantization level for each of a set of quantized run lengths.
8. The method of claim 7 , wherein the quantization of runlengths is logarithmic.
9. The method of claim 1 , further comprising normalizing the runlength histograms before concatenation or normalizing the concatenated runlength histograms.
10. The method of claim 1 , wherein the image comprises a scanned image of a text document.
11. The method of claim 10 , wherein the document comprises at least one of a form, a business record, an identification card, and a business card.
12. The method of claim 1 , wherein the image comprises a bitmap.
13. The method of claim 1 , wherein the image representation comprises a vector of values.
14. The method of claim 1 , further comprising associating the representation of the image with the image in memory.
15. A method of classifying images comprising:
generating image representations for a plurality of training images by the method of claim 1 ;
training a classifier based on the image representations and respective class labels of the training images; and
with the trained classifier, assigning a class to a new image based on its image representation.
16. A computer program product comprising a non-transitory recording medium which encodes instructions for performing the method of claim 1 .
17. A computer device comprising:
memory which stores instructions for performing the method of claim 1 ; and
a processor in communication with the memory for executing the instructions.
18. A method comprising:
receiving first and second images to be compared;
partitioning each of the images into a plurality of regions;
for each of the plurality of regions of the first image, computing a respective first runlength histogram;
generating a representation of the first image based on the runlength histograms computed for the first image, comprising concatenating the first runlength histograms from the plurality of regions of the first image;
for each of the plurality of regions of the second image, computing a respective second runlength histogram;
generating a representation of the second image based on the runlength histograms computed for the second image, comprising concatenating the runlength histograms from the plurality of regions of the second image; and
computing a measure of similarity between the first and second images based on the image representation of the first image and the image representation of the second image.
19. A computer implemented apparatus for generating an image representation of a document image comprising:
memory for storing a received document image;
a region extraction component which extracts a plurality of regions in the document image, at two or more different scales, whereby at least some of the regions are at least partially overlapping;
a histogram generation component which extracts a runlength histogram in each region and combines the histograms corresponding to the different regions;
an output component which outputs a representation of the image based on the combined histograms; and
a processor which implements the components.
20. The apparatus of claim 19 , further comprising:
a normalization component for normalizing the document image.
21. The apparatus of claim 19 , further comprising:
a colorant level quantization component which quantizes pixel colorant values in the document image into a plurality of pixel colorant quantization levels, the histogram generation component generating a histogram for each of the plurality of pixel colorant quantization levels.
22. A method for generating a representation of an image comprising:
scanning a document to generate an image of the document;
quantizing pixel colorant values into N colorant quantization levels;
partitioning the document into regions at a plurality of different scales;
for each region of the image, computing a runlength histogram comprising values for each of the N colorant quantization levels and for each of L directions, were N and L are respectively at least two; and
generating a representation of the document image based on a combination of the runlength histograms corresponding to different regions.
23. The method of claim 22 , wherein the partitioning of the document into regions at a plurality of different scales results at least some of the regions being at least partially overlapping.
24. A computer program product comprising a non-transitory recording medium which encodes instructions for performing the method of claim 22 .