Efficient document processing system and method

• US 8,489,585 B2
• Filed: 12/20/2011
• Issued: 07/16/2013
• Est. Priority Date: 12/20/2011
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Larlus, Diane, Perronnin, Florent
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/331,096
• Publication Number:
  US 20130159292A1
• Time in Patent Office: 574 Days
• Field of Search: 707/723, 382173-180, 382/190, 382/195, 382/205, 382/206
• US Class Current: 707/723
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A document processing system and method are disclosed. In the method local scores are incrementally computed for document samples, based on local features extracted from the respective sample. A global score is estimated for the document based on the local scores currently computed, i.e., on fewer than all document samples. A confidence in a decision for the estimated global score is computed. The computed confidence is based on the local scores currently computed and, optionally, the number of samples used in computing the estimated global score. A classification decision, such as a categorization or retrieval decision for the document is output, based on the estimated score when the computed confidence in the decision reaches a threshold value.

Claims

1. A document processing method comprising:

incrementally,

for each of a set of samples of a document, extracting local features from the sample;

for each of the samples, computing a local score based on the local features extracted from the sample;

estimating a global score for the document based on the local scores currently computed; and

computing a confidence in a decision for the estimated global score, the computed confidence being based on the local scores currently computed; and

outputting a decision for the document based on the estimated score when the computed confidence in the decision reaches a threshold value, the extracting of local features, computing the local score, estimating of the global score, and the computing of the confidence in the decision being repeated with additional samples until the computed confidence in the decision reaches the threshold value.

2. The method of claim 1, wherein at least one of the computing of the local score, estimating of the global score, computing of the confidence in the decision, and outputting of the decision is performed with a processor.

3. The method of claim 1, wherein the computing of the confidence in the decision is also based on a number of the samples used in computing the estimated global score.

4. The method of claim 1, wherein the decision for the document is based on the estimated global score having reached a threshold value.

5. The method of claim 4, wherein the decision for the document is based on the document score being higher or lower than the threshold value.

6. The method of claim 4, further comprising computing at least one of a lower bound and an upper bound of a distribution of the local scores currently computed and wherein the decision for the document is based on the lower bound of a distribution of the local scores currently computed being above the threshold value for the estimated global score or the upper bound of a distribution of the local scores currently computed being below the threshold value for the estimated global score.

8. The method of claim 1, wherein the estimated global score is computed as a function of the aggregated local scores and a number of the samples whose local scores are aggregated.

9. The method of claim 1, wherein the confidence computation is based on an assumption that the sample scores follow a predictable distribution.

10. The method of claim 9, wherein the confidence computation is based on a t-student test.

11. The method of claim 1, wherein the decision comprises at least one of a categorization decision and a retrieval decision.

12. The method of claim 11, wherein the decision comprises a categorization decision and the method comprises computing a decision based on the estimated global score and a class model which has been trained to categorize documents based on an aggregate of their local scores.

13. The method of claim 1, wherein the document comprises at least one of a text document and an image.

14. The method of claim 1, further comprising, for at least one value of confidence in the decision, storing a set of values for an early stopping function for different values of the number of samples, and wherein the computing of the confidence in a decision is based on the early stopping function value for the current value of the number of samples.

15. The method of claim 1, further comprising stopping the computing of the local score when the estimated global score also has reached a threshold value.

16. The method of claim 1, further comprising computing a first accumulator as a current aggregate of the local scores computed so far and storing the first accumulator, the estimated global score being a function of the first accumulator and a number of samples in the current aggregate.

17. The method of claim 1, further comprising computing a second accumulator as a current aggregate of the square of each of the local scores computed so far and storing the second accumulator for computing a variance estimate of the local scores computed so far, the variance estimate being used to determine whether the estimated global score is at least a threshold value.

18. The method of claim 1, further comprising, based on the local scores for samples computed so far, estimating a number of additional samples for which local features are still to be extracted and the local score is still to be computed and reestimating the global score for the document and recomputing the confidence in the decision when the local scores for that number of samples have been computed.

19. The method of claim 1, further comprising reestimating the global score at least once and recomputing the confidence in the decision at least once until the computed confidence in the decision is at least the threshold value and the estimated global score is at least a threshold value.

20. The method of claim 1, wherein the computing of the local score further comprises, for each sample, extracting features from the sample and generating a descriptor based on the extracted features, the local score being based on the descriptor.

21. The method of claim 20, wherein the descriptor represents a statistical distribution of the extracted features.

22. A document processing system comprising:

memory which stores instructions for performing the method of claim 1; and

a processor in communication with the memory for executing the instructions.

23. A computer program product comprising a non-transitory storage medium storing instructions which, when executed by a computer, perform the method of claim 1.

7. A document processing method comprising:

incrementally, for each of a set of samples of a document, computing a local score based on local features extracted from the sample;

estimating a global score for the document based on the local scores currently computed;

computing a confidence in a decision for the estimated global score, the computed confidence being based on the local scores currently computed;

computing at least one of a lower bound and an upper bound of a distribution of the local scores currently computed, comprising accessing a data structure which stores values of a parameter B(α

,T) for different numbers of samples and a preselected value of the confidence in the decision and,

if Y_T>

ε

computing the lower bound according to;

24. A document processing system comprising:

a descriptor generator which, progressively, for each of a set of samples of a document, generates a local descriptor based on features extracted from the sample of the document;

a scoring component which incrementally estimates a global score for the document based on the local descriptors currently computed for the set of samples of the document;

a confidence computing component which computes a confidence in a decision for the estimated global score, the computed confidence being based on the local descriptors currently computed and optionally the number of the samples used in computing the estimated global score;

a decision output component which outputs a decision for the document based on the estimated score when the computed confidence in the decision reaches a threshold value, wherein the generating of the local descriptor based on features extracted from the sample of the document, the estimating of the global score, and the computing of the confidence in the decision are repeated with additional samples until the computed confidence in the decision for the document reaches the threshold value; and

a processor which implements the descriptor generator, scoring component, confidence computing component, and decision output component.

25. The method of claim 24, wherein the decision output component instructs the descriptor generator to discontinue generating the local descriptors when the computed confidence in the decision reaches the threshold value and the estimated global score reaches a threshold value.

26. A document processing system including a processor and memory, which takes as input a document and outputs a decision for a class when:

an estimate of the document score for the class is higher than a threshold ε

or lower than a threshold −

ε

;

the estimated document score for the class being computed as an aggregation of local scores computed from local features;

the local features and scores being computed incrementally and used to compute a confidence in the class decision; and

the extraction of the local features and local score computation being discontinued as soon as the computed confidence in the class decision exceeds a threshold α

, the memory including instructions, implemented by the processor, for incrementally extracting the local features, computing the scores, and computing the confidence in the decision.