Extracting metadata from a digitally scanned document

Presented are techniques for extracting metadata from a digitally scanned document. The text of the digitally scanned document is obtained and a first algorithm is provided to identify various numbers found within the text, determine which numbers correspond to the page numbers of the document, and associate the determined numbers with the pages of the document. Furthermore, a second algorithm is provided that uses the text to determine the page type of the pages within the document. The second algorithm is configured to determine if a page is a table of contents page, an index page, or a title page.

BACKGROUND

Today, there are many websites with search engines dedicated to searching for specific types of content. One specific type of content that some websites provide searching services for is books. Such search engines typically require the digitization and indexing of books supplied by libraries, publishers, and other book providers. Typically, metadata of a book such as the author, title, publisher, copyright year, subjects, correlation between leaf numbers of pages and page numbers printed in the book, the book structure (leaf number of title page, leaf number of table of contents pages, leaf number of index pages), table of contents data (list of chapter names with corresponding page leaf numbers), and index data (list of index terms with corresponding page leaf numbers) is needed to be identified, associated, and indexed with the actual contents of the book.

Books that are not available in digital form are usually scanned using optical character recognition (OCR) technology. However, many problems exist with OCR technology: OCR software typically does not perform any metadata extraction; the quality of OCR output is not perfect as some words do not get recognized correctly; the OCR software is usually not able to detect different formatting between different publishers and copyright years; and the OCR software may not be able to detect more than one sequence of page numbers in a book.

SUMMARY

Presented are techniques for extracting metadata from a digitally scanned document. Provided is a page identification component that is configured to receive text from a digitally scanned document, identify numbers from the text, determine which of the numbers are corresponding page numbers of pages of the document, and associate the determined numbers with the pages of the document in a database. Additionally, a structure analysis component is provided for receiving the text of the digitally scanned document and determining a page type of the pages of the document. The page type may be at least one of a table of contents page, an index page, and a title page.

DETAILED DESCRIPTION

As one skilled in the art will appreciate, embodiments of the present invention may be embodied as, among other things: a method, system, or computer-program product. Accordingly, the embodiments may take the form of a hardware embodiment, a software embodiment, or an embodiment combining software and hardware. In one embodiment, the present invention takes the form of a computer-program product that includes computer-useable instructions embodied on one or more computer-readable media.

FIG. 2is a block diagram of an embodiment of an exemplary computing device200according to an embodiment of the invention. Computing device200includes components such as optical character recognition (OCR) component202, page identification component (PIC)204, and structure analysis component (SAC)206. Computing device200further includes a communication interface (not shown). The communication interface may be an interface that can allow the computing device200to be directly connected to any other device or allows the computing device to be connected to another device over a network (not shown). The network can include, for example, a local area network (LAN), a wide area network (WAN), or the Internet. In an embodiment, the computing device200can be connected to another device via a wireless communication interface through the network.

Computing device200may be or can include a desktop computer, a laptop computer or other mobile computing device, a network-enabled cellular telephone (with or without media capturing/playback capabilities), wireless email client, or other client, machine or device to perform various tasks including Web browsing, search, electronic mail (email) and other tasks, applications and functions. Computing device200may additionally be any portable media device such as digital still camera devices, digital video cameras (with or without still image capture functionality), media players such as personal music players and personal video players, and any other portable media device. Computing device200may also be or can include a server such as a workstation running the Microsoft Windows, MacOS™, Unix™, Linux™, Xenix™, IBM AIX™, Hewlett-Packard UX™, Novell Netware™, Sun Microsystems Solaris™, OS/2™, BeOS™, Mach™, Apache™, OpenStep™ or other operating system or platform.

OCR component202is a computer hardware or software component configured to produce a text document for each page of a digitally scanned document. The digitally scanned document may be any type of document that has page numbers. For example, the digitally scanned document may be a book, article, journal, magazine, etc. Once the document has been scanned, the OCR component202can be executed on the digitally scanned document to extract the text found on each page of the document. An OCR document is produced by the OCR component202and includes the extracted text from each page of the digitally scanned document. In an embodiment, the OCR document will have the same pages and corresponding text as the digitally scanned document.

However, due to the limitations of using OCR technology discussed previously, the OCR component202may not be able to identify certain metadata that is needed to be indexed into a search engine for searching purposes. Such information may include: the proper page number that corresponds to each page; an identification of the page within the digitally scanned document is the title page; an identification of pages within the digitally scanned document that are table of contents pages; and an identification of pages within the digitally scanned document that are index pages. The PIC204and the SAC206are two new components that have been created to extract the aforementioned metadata.

PIC204is a computer hardware or software component with logic to identify and associate page numbers with each page of a digitally scanned document once the document has been processed by the OCR component202. The logic includes an algorithm for determining the proper page numbers for each of the pages of the digitally scanned document. Once OCR component202produces the OCR document, the OCR document is received by the PIC204for processing. The PIC204first creates a list of each number found on each page of the OCR document.FIG. 3is an example of the lists of numbers identified on pages of the OCR document according to an embodiment of the invention.FIG. 3shows the page numbers identified for each of pages 10-17 of the OCR document. In an embodiment, the PIC204will only consider numbers found in an outer region surrounding a page of the digitally scanned document as it may be believed that actual page numbers will generally be found in this outer region. For example, as shown inFIG. 4, only numbers within the outer region402of page400will be identified by the PIC204. For example, only number “1” will be identified by the PIC204since it is located within the outer region of the page. Numbers “23” and “96” will not be identified by the PIC204since they are not located within the outer region. The size of the outer region may be predetermined by the developer of PIC204, administrator of PIC204, or any other entity authorized to set the size of the outer region. Once the lists of identified numbers for each page has been created, in an embodiment, the PIC204can further filter the list of numbers, for instance, by discarding negative numbers found on any pages or numbers that are greater than the total number of pages within the digitally scanned or OCR document.

The PIC204can proceed to generate sequences from the numbers found on each page of the OCR document. In an embodiment, the sequences are generated by locating a first number on a first page and determining if a number incremented by one is found on a separate adjacent page to the first page. For example, referring toFIG. 3, a sequence300of “12,13” can be generated from pages16and17, a sequence302of “20,21” can be generated from pages14and15, a sequence304of “30,31,32” can be generated from pages11-13, and a sequence306of “6,7,8,9” can be generated from pages10-13.

The PIC204can then assign a confidence level identifier to each of the generated sequences that correspond to a level of confidence that the sequence of numbers actually correspond to the page numbers of the pages of the digitally scanned document. In an embodiment, the confidence level identifier is assigned based on the length of the sequence. In an embodiment, the confidence level identifier is the length of the sequence. For example, sequences300and302each would be assigned a confidence level identifier of2, sequence304would be assigned a confidence level identifier of 3, and sequence306would be assigned a confidence level identifier of 4. In an embodiment, the confidence level identifiers are also associated with each number within the sequence.

In an embodiment, the PIC204can also be configured to connect two or more sequences if such sequences can be used to create one longer sequence. In an embodiment, the PIC204will connect a first sequence together with a second sequence when a number of pages between a last page number of the first sequence and a first page number in the second sequence is one less than the last page number subtracted from the first page number. For example, the last page number of sequence306is “9,” the first page number of sequence300is12, and there are two pages between the two sequences. Sequences306and300can be connected together since the number of pages between them (2) is one less than the result of the last page number of the first sequence (9) subtracted from the first page number of the second sequence (12) which is 3. Once the two sequences are connected, the pages between the sequences are assigned numbers that complete the connected sequence. For example, pages14and15would be assigned page numbers “10” and “11” to complete the connected sequence308of “6,7,8,9,10,11,12,13” with a confidence level identifier of8.

In an embodiment, two sequences are not connected together if the confidence level identifier of any numbers between the two sequences is higher than the confidence level identifiers of the either of the two sequences. For example, number “50” of page12would not be connected to number “52” of page14since number “9” of page13has a confidence level identifier of 4 even before the connected sequence308is created. In another embodiment, the two sequences are not connected if the confidence level of the potentially connected sequence is not greater than any numbers between the two sequences. For example, connecting “50” with “52” would potentially create a sequence of “50,51,52” with a confidence level of 3. However, the sequence of “50,51,52” would not be created as the confidence level of 3 would still not be greater than number9's confidence level of 4.

In an embodiment, the PIC204can filter the lists of sequences by discarding sequences that do not have confidence level identifiers that reach a predetermined threshold value. For example, the predetermined threshold value may be set to “3.” Accordingly,304,306, and308would be identified as having reached the threshold value and sequences300and302would be discarded from being considered as potential page numbers since they have confidence level identifiers of “2.”

Once the PIC has discarded the inadequate sequences, the PIC204can determine which of the remaining sequences has the highest confidence level identifier and can associate such sequences with the corresponding pages of the OCR document. For example, since sequence308has the highest confidence level identifier of 8, sequence308is assigned to and associated with the tenth through seventeenth pages of the OCR document. The association of the assigned page numbers and the pages of the OCR document are then stored in a database for future use.

The SAC206is a computer hardware or software component with logic to analyze the text of each page of an OCR document to determine the page type for at least a portion of the pages (e.g., whether a page is a title page, a table of contents page, or an index page). The logic includes an algorithm for determining the type of page for each of the pages of a digitally scanned document. Once PIC component204identifies the page numbers of the OCR document, the OCR document is further processed by the SAC206to identify each page's page type.

The SAC206first analyzes the text of each page within the OCR document to determine a first score that corresponds to the likelihood the page is a table of contents page, a second score that corresponds to the likelihood the page is an index page, and a third score that corresponds to the likelihood the page is a title page. The first score is determined by identifying the amount of table of contents page characteristics found on the page. The table of contents page characteristics are parameters that are generally found on a typical table of contents page. For example, some table of contents page characteristics can be, but are not limited to: the page area covered by words, the number of columns found on the page; the percentage of lines starting with the word “chapter;” the number of sequences of lines ending with a number; a ratio of the length of the longest sequence of lines ending with an increasing number divided by the number of lines ending with a number; the presence of keywords such as “Table of Contents” and “contents” found on the page; and the presence of keywords not indicating a table of contents page such as “index,” “glossary,” and “illustrations.” The greater the likelihood the page is a table of contents page, the higher its corresponding table of contents page score will be.

The second score is determined by identifying the amount of index page characteristics found on the page. The index page characteristics are parameters that are generally found on a typical index page. For example, some index page characteristics can be, but are not limited to: the page area covered by words, the number of index entries found on the page; a ratio of the length of the longest sequence of alphabetized indexed entries divided by the number indexed entries; the presence of keywords indicating an index page; and the presence of keywords not indicating an index page. The greater the likelihood the page is an index page, the higher its corresponding index page score will be.

The third score is determined by identifying the amount of title page characteristics found on the page. The title page characteristics are parameters that are generally found on a typical title page. For example, some index page characteristics can be, but are not limited to: the presence of the keywords “title” and “author” found on the page; the font size of the words on the page; the location of the page (i.e. odd pages located close to the beginning of the document may receive a higher score). The greater the likelihood the page is a title page, the higher its corresponding title page score will be.

Once the three scores for each page have been calculated, a mean score for each type of score (table of contents page, index page, and title page) is calculated based the scores of all of the pages in OCR document. For example, a first mean score will be calculated based on each page's table of contents page score, a second mean score will be calculated based on each page's index page score, and a third score will be calculated based on each page's title page score. Once the three mean scores have been calculated, candidate table of contents pages, candidate index pages, and candidate title pages are identified. Such identified pages are pages that have a score for a particular type of page that is greater than predetermined value of standard deviations away from the corresponding mean score. The predetermined value of standard deviations may be set by an administrator or other authorized entity. In an embodiment, the candidate title page with the highest number of standard deviations away from the title page mean score is considered the title page of the OCR document and is assigned the title page identifier. In another embodiment, the candidate title page with the highest third score (title page score) is considered the title page and is assigned the title page identifier.

Once the candidate table of contents and index pages have been identified, a first set of one or more sequences of pages incremented by one are created from the page numbers of the candidate table of contents pages, and a second set of one or more sequences of pages incremented by one are created from the page numbers of the candidate index pages. For example, if a group of candidate pages consisted of pages8,144,7,36,9,11, and35, a first sequence would be “7,8,9” and a second sequence would be “35,36.” Moreover, two or more sequences can be connected together to form a connected sequence when a number of pages that are not candidate pages between a last page number of a first sequence and a first page number of a second sequence is below a first predetermined threshold identifier. For example, in the above example, page11may be connected to the sequence “7,8,9” if the number of pages between page9and11(i.e. one page: page10) was below the predetermined threshold identifier. If the predetermined threshold identifier was 3 pages, page11can be added to the sequence since there is only one page between page9and11. In such an example, the pages between the two sequences, page10in this example, are added to the connected sequence of candidate pages for the particular type of page (table of contents or index). For example, the connected sequence “7,8,9,10,11” can be created.

In an embodiment, additional pages next to a sequence or a connected sequence can be added to the sequence or connected sequence by relaxing the requirements for the number of standard deviations away from the mean that a page's table of contents or index page score needs to be in order to be a candidate page. In such an embodiment, a new predetermined value of standard deviations away from the table of contents or index page mean score can be used to determine if the pages close to the sequences should be added. In such an embodiment, the new predetermined value of standard deviations will be less than the original predetermined value that was used to generate the original group of candidate pages. For example, by requiring only 1 standard deviation (new) away from a particular type of mean score for a page to be considered a candidate page instead of 3 standard deviations (original), page12(has score that is 1 standard deviation away from the mean) may be recognized as a candidate page and can be added to the above connected sequence to form a new connected sequence of “7,8,9,10,11,12.”

Once the sequences and connected sequences have been generated, a sequence score is assigned to each sequence and connected sequence. The sequence score is assigned based on the length of the sequence. In an embodiment, the longer the sequence, the higher its sequence score will be. In an embodiment, the length of the sequence is the sequence score. For example, the connected sequence “7,8,9,10,11,12” would have a sequence score of 6. Once all scores have been calculated for the sequences of table of contents pages, the sequence of pages with the highest score will be considered the table of contents pages and the table of contents page identifier will be assigned to and associated with the pages of the sequence in a database. Once all scores have been calculated for the sequence of index pages, the sequence of pages with the highest score will be considered the index pages and the index page identifier will be assigned to and associated with the pages of the sequence in a database.

In an embodiment, some sequences may be split apart and their corresponding sequence score may be lowered accordingly if a multi-page property test fails across all pages within the sequence. For example, for a sequence of candidate table of contents pages, a multi-page property test of calculating a ratio of the length of the longest sequence of lines ending with an increasing number divided by the number of lines ending with a number can be applied to all pages in the sequence. If the ratio drops below a certain predetermined threshold value at any identified page, the identified page may be removed from the sequence as well as any pages that come after the identified page. For a sequence of candidate index pages, a multi-page property test of calculating a ratio of the length of the longest sequence of alphabetized indexed entries divided by the number indexed entries can be applied to all pages in the sequence. If the ratio drops below a certain predetermined threshold value at any identified page, the identified page may be removed from the sequence as well as any pages that come after the identified page.

FIG. 5is a flow diagram of an exemplary method500for extracting metadata from a digitally scanned document according to an embodiment of the invention. At operation502, text from a digitally scanned document is obtained. In an embodiment, the text may be obtained using OCR technology. At operation504a list of one or more numbers found on each page is generated for at least a portion of a plurality of pages within the document. At operation506, sequences of numbers incremented by one from the list of one or more numbers are created from each of the at least a portion of the plurality of pages. In an embodiment, each number in the sequence is from a separate adjacent page. At operation508, a first confidence level is assigned to each of the one or more sequences. In an embodiment, the first confidence level corresponds to the length of the corresponding sequence. At operation510, sequences that have a confidence level above a first predetermined threshold value are identified. At operation512, the identified sequences are associated to corresponding pages of the digitally scanned document within a database. In an embodiment, operations502,504,506,508,510, and512are performed by a PIC204.

FIG. 6is a flow diagram of another exemplary method600for extracting metadata from a digitally scanned document according to an embodiment of the invention. At operation602, text from a digitally scanned document is obtained. In an embodiment, the text is obtained using OCR technology. At operation604, a first score is determined for each page within the document, wherein the first score corresponds to the likelihood the page is a table of contents page. At operation606, a second score is determined for each page within the document, wherein the second score corresponds to the likelihood the page is an index page. At operation608, a third score is determined for each page within the document, wherein the third score corresponds to the likelihood the page is a title page. At operation610, a title page identifier, a table of contents page identifier, and an index page identifier is assigned to one or more pages within the document based on the first, second, and third scores. In an embodiment, operations602,604,606,608, and610are performed by a SAC206.

While particular embodiments of the invention have been illustrated and described in detail herein, it should be understood that various changes and modifications might be made to the invention without departing from the scope and intent of the invention. The embodiments described herein are intended in all respects to be illustrative rather than restrictive. Alternate embodiments will become apparent to those skilled in the art to which the present invention pertains without departing from its scope.