Method and system for determining page numbers of page images

• US 7,743,320 B1
• Filed: 12/22/2006
• Issued: 06/22/2010
• Est. Priority Date: 06/22/2004
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Siegel, Hilliard B., Gordon, Charles
• Primary Examiner(s): Hong; Stephen S
• Assistant Examiner(s): TSUI, WILSON W
• Application Number:
  US11/615,737
• Time in Patent Office: 1,278 Days
• Field of Search: 715230-232, 715/253, 715/273
• US Class Current: 715/230
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

Page numbering of images of pages in a document includes extracting all numbers that are exactly one different than a number found on an adjacent page, and grouping the extracted numbers into a set of sequences that describe the candidate page numbers in the book. The sequences most likely to contain candidates that represent the actual page numbers are determined by merging the most reliable sequences together to bridge gaps between the sequences, and identifying those gaps where the page numbers have been intentionally omitted. Page images are labeled with numbers that are determined to be most likely to represent the actual page number. Page numbering is abandoned when insufficient numbers of pages numbers are able to be extracted or assigned relative to the total number of pages in the document.

Claims

1. A computer-implemented method for numbering page images, the method comprising:

obtaining images of pages of content in a document in an order in which the pages appear in the document;

extracting candidate page numbers from the content of the page images;

saving extracted candidate page numbers in a plurality of sequences of numbers wherein for each sequence a candidate page number extracted from a page image is one different than a candidate page number extracted from an adjacent page image in the order in which the pages appear in the document;

merging a first sequence and a second sequence of the plurality of sequences beginning with a more reliable sequence, wherein merging includes comparing the first sequence with the second sequence to determine whether a difference between a highest candidate page number in the first sequence and the lowest candidate page number in the second sequence matches a number of page images spanned by a gap between the first and the second sequences, and if so, assigning consecutive page numbers to the page images in the gap;

determining whether to abandon numbering of page images based on a variable completeness threshold determined based on a method of extracting candidate page numbers; and

labeling the page images in accordance with the extracted and assigned page numbers in the merged sequence.

2. The method of claim 1, wherein extracting candidate page numbers from the content of the page images includes recognizing numbers appearing in the content of the page images using a character recognition process.

3. The method of claim 1, wherein extracting candidate page numbers from the content of the page images includes extracting numbers from content represented in a text-accessible format.

4. The method of claim 1, wherein the gap between the first and second sequences spans one or more page images from which no numbers could be extracted.

5. The method of claim 1, wherein the gap between the first and second sequences spans one or more page images from which an extracted number was not saved in a sequence because the number was not one different than a number extracted from an adjacent page image.

6. The method of claim 1, further comprising assigning consecutive page numbers to the page images spanned by any unmatched gaps between the merged sequences after determining that the number of page images in the merged sequences meets the variable completeness threshold.

7. The method of claim 1, further comprising:

determining whether page images spanned by an unmatched gap between merged sequences represent an insert; and

assigning insert page numbers to the page images spanned by the unmatched gap.

8. The method of claim 7, wherein determining whether the page images spanned by an unmatched gap represent an insert includes determining whether a difference between the highest candidate page number in a merged sequence and the lowest candidate page number in another sequence is substantially small.

9. The method of claim 7, wherein the insert page numbers include one or more consecutive page numbers or fractional page numbers.

10. The method of claim 1, further comprising abandoning numbering of page images when the variable completeness threshold has not been met.

11. The method of claim 1, wherein the variable completeness threshold is a minimum number of page images from which page numbers must be extracted.

12. The method of claim 1, wherein the variable completeness threshold is a minimum number of page images for which page numbers must be determined from merging sequences of extracted page numbers.

13. The method of claim 1, wherein the variable completeness threshold is a percentage of the total number of pages in the document.

14. The method of claim 1, further comprising discarding shorter sequences spanning the same page images as a longer sequence.

15. The method of claim 1, wherein the variable completeness threshold is determined based on a type of the document.

16. The method of claim 1, wherein the variable completeness threshold is determined based on a quality of the images of pages of content in the document.

17. The method of claim 2, wherein the variable completeness threshold is determined based on a technology used in the character recognition process.

18. A computer-implemented system to facilitate numbering images of pages of a document, comprising:

a page image database operable to store page images organized according to an order in which pages appear in the document;

a memory operable to store candidate page numbers extracted from the page images;

a sequence merger component, coupled with the memory and the page image database, operable to merge two sequences of extracted candidate page numbers when a beginning candidate page number of a first sequence and an ending candidate page number of a second sequence differ by an amount that equals a number of page images in a gap between the first sequence and second sequence;

an insert identifier component, coupled with the sequence merger component, operable to identify omitted page numbers forming the gap between the first sequence and second sequence;

an assignment component, coupled with the insert identifier component, operable to assign consecutive page numbers to page images spanned by the gap, and labeling the page images in accordance with the extracted and assigned page numbers; and

a completion threshold component, coupled with the assignment component, operable to determine and apply a completeness threshold to determine whether to abandon the numbering of page images.

19. The system of claim 18, wherein the sequence merger component merges sequences having a greater likelihood of containing extracted numbers that represent actual page numbers of the page images before merging sequences having a lesser likelihood of containing extracted numbers that represent actual page numbers of the page images.

20. The system of claim 19, wherein the sequence merger component is further operable to sort sequences from longest to shortest and merge longer sequences before shorter sequences, wherein longer sequences have a greater likelihood of containing extracted numbers that represent actual page numbers than shorter sequences.

21. The system of claim 18, wherein the memory operable to store extracted numbers further includes memory in which to store the completeness threshold.

22. The system of claim 18, wherein the completeness threshold is a minimum number of occurrences of extracted numbers that have been determined to have a greater likelihood of representing actual page numbers.

23. The system of claim 18, wherein the completeness threshold is a minimum number of page images that have been numbered in accordance with the extracted and assigned page numbers.

24. The system of claim 18, wherein the completeness threshold is expressed as a percentage of the total number of pages in the document.

25. The system of claim 18, wherein the completeness threshold is determined based on a type of the document.

26. The system of claim 18, wherein the completeness threshold is determined based on a quality of the images of pages of content in the document.

27. A non-transitory computer-readable medium having encoded thereon instructions to number images of pages of a document, wherein the instructions, when executed by a computing apparatus, cause the computing apparatus to:

obtain images of pages in an order in which the pages occur in a document;

extract a number from at least one of the page images when the number is one different than a number extracted from an image of an adjacent page in the order in which the page occurs in the document;

store the extracted numbers as sequences of consecutive numbers that correspond to the order in which the pages occur in the document;

assign missing numbers to fill in gaps between the sequences when a count of the pages represented by a gap matches a count of the missing numbers that are needed to fill the gap;

assign missing numbers to partially fill in gaps between the sequences when a count of the pages represented by the gap does not match the count of the missing numbers that are needed to fill in the gap, but differs by a substantially small amount;

determine whether to abandon numbering of page images based on a variable completeness threshold; and

label the page images with the extracted and assigned numbers.

28. The computer-readable medium of claim 27, wherein the instructions further cause the computing apparatus to rank the sequences of consecutive numbers in order of reliability, where reliability is determined from an indication that the extracted numbers in the sequence are likely to match the actual page number of the page from which the image was obtained, and wherein the instructions to assign missing numbers to fill in the gaps between the sequences are performed in order of reliability.

29. The computer-readable medium of claim 28, wherein the indication that the extracted numbers are likely to match the actual page number of the page from which the image was obtained is determined based upon a length of the sequence, where the longer the sequence of consecutive numbers the greater the reliability.

30. The computer-readable medium of claim 29, wherein the instructions further cause the computing apparatus to discard smaller sequences that conflict with longer sequences.

31. The computer-readable medium of claim 27, wherein the substantially small amount is an integer of less than or equal to three.

32. The computer-readable medium of claim 27, wherein the instructions that cause the computing apparatus to assign missing numbers to partially fill in gaps between the sequences includes an instruction to choose which of the pages represented by the gap are assigned the missing numbers, and to assign an insert designation to the unassigned pages.

33. The computer-readable medium of claim 32, wherein the choice is arbitrary.

34. The computer-readable medium of claim 32, wherein the choice is made according to at least one of a type of document from which the image was obtained and a characteristic of the insert, the characteristic including at least one of a number of pages represented by the gap, a type of pages represented by the gap, and whether a page immediately adjacent to the gap is labeled with an extracted number or an assigned number.

35. The computer-readable medium of claim 28, wherein the indication that the extracted numbers are likely to match the actual page number of the page from which the image was obtained is a page type of the pages represented by the sequence, where a pre-determined page type indicates a greater reliability.