2D multi-coordinate adaptive dynamics programming method for robust document registration

Systems and methods for registering documents. A two-dimensional document image and one or more form images may be obtained. The document image may be projected onto a horizontal axis and a vertical axis to create a horizontal document projection and a vertical document projection. The form images may be projected onto the horizontal axis and the vertical axis to create a horizontal form projection and a vertical form projection. The horizontal document projection may be correlated with the horizontal form projection of the form images and the vertical document projection may be correlated with the vertical form projection of the form images. Correlation scores may be calculated based on the correlations.

BACKGROUND OF THE INVENTION

The genealogical and historical document communities have recognized the value in unlocking and providing access to historical documents in digital format as digitized images with indexed, searchable, enhanced, viewable data. Furthermore, leaders in the industry leverage image processing algorithms to better enhance and present document images to viewers. The ability to properly register, segment, and field the information on documents are prerequisite steps for higher-level operations such as handwriting recognition, hit-highlighting, context-aware tips and pop-ups, etc.

Unfortunately, many historical documents are damaged or degraded due to age, poor preservation, deterioration, and damage resulting from both man-made and natural disasters. Portions of pages may be burned, faded, torn, obscured, water-damaged, or otherwise missing or unreadable. Hence, robust methods for document registration that work reliably with historical documents are needed.

BRIEF SUMMARY OF THE INVENTION

A computer-implemented method for registering documents is provided. The method may include obtaining a document image, the document image being at least two-dimensional. The method may include obtaining one or more form images. Each of the one or more form images may be at least two-dimensional. The method may include projecting the document image onto one or both of a horizontal axis and a vertical axis to create one or both of a horizontal document projection and a vertical document projection. The method may include projecting each of the one or more form images onto one or both of the horizontal axis and the vertical axis to create one or both of a horizontal form projection and a vertical form projection. The method may include correlating either the horizontal document projection with the horizontal form projection of at least one of the one or more form images, or the vertical document projection with the vertical form projection of at least one of the one or more form images.

In some embodiments, the method may include projecting the document image both onto the horizontal axis to create the horizontal document projection and onto the vertical axis to create the vertical document projection. In some embodiments, the method may include projecting each of the one or more form images both onto the horizontal axis to create the horizontal form projection and onto the vertical axis to create the vertical form projection. In some embodiments, the method may include correlating the horizontal document projection with the horizontal form projection of each of the one or more form images to create one or more horizontal correlation functions. In some embodiments, the method may include correlating the vertical document projection with the vertical form projection of each of the one or more form images to create one or more vertical correlation functions. In some embodiments, the method may include calculating a horizontal correlation score for each of the one or more form images by averaging each of the one or more horizontal correlation functions. In some embodiments, the method may include calculating a vertical correlation score for each of the one or more form images by averaging each of the one or more vertical correlation functions. In some embodiments, the method may include combining the horizontal correlation score with the vertical correlation score for each of the one or more form images to create combined scores. In some embodiments, the method may include determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.

In some embodiments, the method may include determining a missing portion and an available portion of the document image. In some embodiments, the method may include determining a horizontal weighting function by projecting the missing portion and the available portion onto the horizontal axis. In some embodiments, the method may include determining a vertical weighting function by projecting the missing portion and the available portion onto the vertical axis. In some embodiments, the method may include calculating a weighted horizontal correlation score for each of the one or more form images by performing a weighted average of each of the one or more horizontal correlation functions using the horizontal weighting function. In some embodiments, the method may include calculating a weighted vertical correlation score for each of the one or more form images by performing a weighted average of each of the one or more vertical correlation functions using the vertical weighting function. In some embodiments, the method may include combining the weighted horizontal correlation score with the weighted vertical correlation score for each of the one or more form images to create combined scores. In some embodiments, the method may include determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.

In some embodiments, combining the weighted horizontal correlation score with the weighted vertical correlation score may include either adding or averaging the scores. In some embodiments, the method may include rotating the document image such that the document image is vertically aligned with the vertical axis and horizontally aligned with the horizontal axis. In some embodiments, the method may include stretching the horizontal document projection over the horizontal axis such that the horizontal document projection either increases or decreases in length. In some embodiments, the method may include stretching the vertical document projection over the vertical axis such that the vertical document projection either increases or decreases in length. In some embodiments, the document image may be an image of a family history document and the one or more form images may be images of one or more form types for family history documents.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present disclosure provide a novel and robust approach for registering damaged historical documents that are too difficult to register using off-the-shelf office document registration algorithms. Current approaches to solving the problem of document registration frequently rely on locating document page corners, borders, or perhaps a few key points of interest within the document. Since only three points are required to “fix a plane” in 3D space, the corner finding, and key-point finding approaches have been sufficient for working with modern office documents, but have proven inadequate and unreliable when applied to historical and/or damaged documents.

Embodiments of the present disclosure leverage algorithms from the field of speech recognition to solve the problem of registering noisy signals in digital images of damaged historical documents. In speech recognition, dynamic time warping (DTW) algorithms are used to match spoken words with expected words (for example, in a telephone voice response system, or SIRI-like voice activated speech recognition system). These algorithms are tolerant of temporal variation-words being spoken faster, or slower, or even at variable rate, are robust to variations in pitch (high or low) and volume (loud or soft), and are tolerant of longer or shorter delays at the beginning or ending of the speech signal.

Embodiments of the present disclosure adapt several features of 1D algorithms from the speech recognition domain for use in 2D image processing. Embodiments of the present disclosure enable robust recognition and registration of document profile signals even in cases where the historical documents are severely deteriorated or damaged. This is accomplished, in part, by observing that projected profiles of 2D documents along a given axis yield a 1D signal similar to a 1D audio signal. The realm of 1D projections that can take on 2D document images include, but are not limited to, enhanced line projection profiles, blank space projection profiles, connected component projection profiles, machine-print projection profiles, handwriting projection profiles, black-run projection profiles, white-run projection profiles, intensity projection profiles, gradient magnitude projection profiles, gradient orientation projection profiles, etc. Given an ample set of 1D signals, the 1D DTW algorithms from speech recognition may be adapted for use with the image data. Just as the DTW algorithms are robust to variations in rate, pitch, volume, etc. in speech recognition, embodiments of the present disclosure are robust to image variations in scale, translation, cropping, aspect ratio, intensity, noise, fading, blurring, and even significantly damaged documents where entire sections, even more than half of the image, may be damaged, obscured, or even completely missing.

Unlike other approaches, embodiments of the present disclosure are independently scale invariant along the X and Y axes. This is important because some scanning hardware for historical documents (particularly microfilm scanners) do not preserve aspect ratio and, in fact, exhibit some variability in aspect ratio between scanned images. Additionally, embodiments of the present disclosure are independently translation invariant on the X and Y axes. This is important because documents may be damaged or, more commonly, mis-cropped in the X axis, the Y axis, or both. In addition to being scale and translation invariant, some embodiments of the present disclosure provide rotational invariance, which is a significant advantage compared to other algorithms that are not rotationally invariant.

FIG. 1illustrates a damaged document102and a database of forms106, according to an embodiment of the present disclosure. In some embodiments, an objective of the present disclosure includes determining which of several possible forms is associated with a damaged document. In some embodiments, database of forms106includes a form104which may be similar and/or identical to damaged document102if the damaged portions were in an original state. Form104may also be a template version of damaged document102with empty entries, as shown inFIG. 1. Database of forms106may include forms of different sizes and configurations, and may be obtained by analyzing large numbers of historical documents to determine common structures and templates.

FIG. 2illustrates horizontal projections108and vertical projections110of damaged document102and form104, according to an embodiment of the present disclosure. Horizontal projections108include horizontal document projection108-1(denoted as pd(x)) and horizontal form projection108-2(denoted as pƒ(x)). Vertical projections110include vertical document projection110-1(denoted as pd(y)) and vertical form projection110-2(denoted as pƒ(y)). Projections may be obtained by performing mathematical operations along an axis. For example, in some embodiments, horizontal projections are obtained by a summation of all pixel values at each x value and vertical projections are obtained by a summation of all pixel values at each y value. Pixel values may be an RGB value, a darkness value, a lightness value, or some other value. In some embodiments, horizontal projections are obtained by an averaging of all pixel values at each x value and vertical projections are obtained by an averaging of all pixel values at each y value. Horizontal and vertical projections may be filtered to improve smoothness or reduce outliers that may distort the analysis.

FIG. 3illustrates horizontal and vertical correlations between damaged document102and form104, according to an embodiment of the present disclosure. In some embodiments, correlating horizontal document projection108-1with horizontal form projection108-2creates a horizontal correlation function112(denoted as ƒ(x)), and correlating vertical document projection110-1with vertical form projection110-2creates a vertical correlation function114(denoted as ƒ(y)). In some embodiments, correlating two projections yields a correlation function in accordance with the traditional correlation function used in statistics. In some embodiments, correlating two projections includes determining the similarity in values between the two projections, such that two projections that are identical would yield a correlation function equal to 100% or 1 at all values of the independent variable (either x or y). In some embodiments, correlating two projections includes determining the difference or error between the two projections, such that two projections that are identical would yield a correlation function equal to 0% or 0 at all values of the independent variable (either x or y). For example, the correlation function may be equal to the square of the difference between the two projections, such as if pd(x)=3 at x=5 and pƒ(x)=6 at x=5, then ƒ(x)=(3−6)2=9 at x=5.

In some embodiments, correlating two projections (or signals) includes identifying the peaks in each of the two projections and aligning the two projections such that their peaks are aligned as close as possible. Documents and forms generally include strong vertical and horizontal lines which cause significant peaks in horizontal and vertical projections. This feature of the projections can be exploited by ignoring all content of the projections except for the peaks. In some embodiments, all peaks above a certain x value threshold or y value threshold are considered in the correlation. The correlation function may be related to the error in the independent variable between peaks of the two projections. For example, if horizontal document projection108-1has a peak at x=324 and horizontal form projection108-2has a peak at x=368, then horizontal correlation function112may have low values (indicating poor correlation) between 324<x<368. By way of another example, if both horizontal document projection108-1and horizontal form projection108-2have peaks at x=345, then horizontal correlation function112may have a high value (indicating good correlation) at x=345. The magnitude of the peaks may also influence the correlation function. For example, peaks in the two projections that are similar in magnitude indicate better correlation than peaks that differ substantially in magnitude.

FIG. 4illustrates weighting functions116and118of damaged document102, according to an embodiment of the present disclosure. In some embodiments, damaged document102may be partitioned into available portions and missing portions to create a partitioned document400. Partitioned document400is similar in size to damaged document102, and may include a first value (such as 1) in portions that are determined to be available and may include a second value (such as 0) in portions that are determined to be missing. Horizontal weighting function116(denoted as w(x)) and vertical weighting function118(denoted as w(y)) may then be obtained in a similar manner to horizontal projections108and vertical projections110. In some embodiments, weighting functions116and118represent the percentage of availability of partitioned document400at each value of the independent variable (either x or y). Weighting functions116and118may facilitate the analysis by providing a confidence level to horizontal projections108, vertical projections110, horizontal correlation function112, and vertical correlation function114. For example, a document projection in which a large portion of the document is missing may be particularly distorted along portions with a low percentage of availability. Such portions may be less reliable than portions with a high percentage of availability.

FIGS. 5A-5Hillustrate various damaged documents, according to an embodiment of the present disclosure.FIG. 5Aillustrates a damaged document with a missing top.FIG. 5Billustrates a damaged document with a missing left side.FIG. 5Cillustrates a damaged document with all edges missing.FIG. 5Dillustrates a damaged document with multiple corners missing.FIG. 5Eillustrates a damaged document with a missing upper right corner.FIG. 5Fillustrates a damaged document with more than half of the document missing.FIG. 5Gillustrates a damaged document that is over cropped on the left side.FIG. 5Hillustrates a damaged document that is over cropped on the top side.

FIG. 6illustrates a method for calculating a horizontal correlation score, according to an embodiment of the present disclosure. The horizontal correlation score may be calculated directly from horizontal correlation function112by averaging or by summation of horizontal correlation function112. Alternatively, a weighted horizontal correlation score may be calculated by performing a weighted average of horizontal correlation function112using horizontal weighting function116as the weights for the averaging.

FIG. 7illustrates a method for calculating a vertical correlation score, according to an embodiment of the present disclosure. Similar to the horizontal correlation score, the vertical correlation score may be calculated directly from vertical correlation function114by averaging or by summation of vertical correlation function114. Alternatively, a weighted vertical correlation score may be calculated by performing a weighted average of vertical correlation function114using vertical weighting function118as the weights for the averaging.

FIG. 8illustrates a method800for registering a damaged document, according to an embodiment of the present disclosure. At step802, a document image is obtained and provided as an input. The document image may be similar to damaged document102. At step804, the document image is rotated and/or aligned such that the document image is vertically aligned with the vertical axis and horizontally aligned with the horizontal axis. The orientation of the document is determined by searching for sets of lines that are parallel with each other. At step806, horizontal document projection pd(x) and vertical document projection pd(y) are created as described in reference toFIG. 2. At step808, the horizontal and vertical document projections are stretched and/or shortened to improve correlation with form projections. At step810, a forms database is created and/or maintained. The forms database may be similar to database of forms106, and may contain several possible forms for registering the damaged document. At step812, each of the forms in the forms database may be projected onto the horizontal and vertical axis to create horizontal form projections pƒ1(x), pƒ2(x), . . . pƒN(x) and vertical form projections pƒ1(y), pƒ2(y), . . . , pƒN(y), where N is the number of forms.

At step814, horizontal document projection pd(x) is correlated with horizontal form projections pƒ1(x), pƒ2(x), . . . pƒN(x) to create horizontal correlation functions ƒ1(x), ƒ2(x), . . . ƒN(x) and vertical document projection pd(y) is correlated with vertical form projections pƒ1(y), pƒ2(y), . . . pƒN(y) to create vertical correlation functions ƒ1(y), ƒ2(y), . . . ƒN(y). For example, horizontal correlation function ƒ1(x) is the result of correlating horizontal document projection pd(x) with horizontal form projection pƒ1(x). Correlating two projections/signals may be performed similar to that described in reference toFIG. 3. In some embodiments, document projections pd(x) and pd(Y) are recursively fed back into step808where they are again stretched and/or shortened, and then step814is repeated with new document projections pd(x) and pd(y). Step814may be repeated multiple times with new document projections pd(x) and pd(y) until the correlation functions are improved. In some embodiments, step808not only performs stretching and shrinking but also performs vertical and/or horizontal translation, which may also improve the correlation functions. In some embodiments, step808may be performed within step814.

At step824, combined scores S1, S2, . . . SNare analyzed and a maximum combined score is found. At step826, the form corresponding to the maximum combined score is identified and used to register the document image. Proper registration of the damaged document allows the information in the damaged document to be recorded, and allows for an account of what data is missing. For example, if the damaged document is a census record, it may be determined that missing portions correspond to a missing name, age, gender, or place of residence.

FIG. 9illustrates a simplified computer system900, according to some embodiments of the present disclosure. A computer system900as illustrated inFIG. 9may be incorporated into devices such as a portable electronic device, mobile phone, or other device as described herein.FIG. 9provides a schematic illustration of one embodiment of a computer system900that can perform some or all of the steps of the methods provided by various embodiments. It should be noted thatFIG. 9is meant only to provide a generalized illustration of various components, any or all of which may be utilized as appropriate.FIG. 9, therefore, broadly illustrates how individual system elements may be implemented in a relatively separated or relatively more integrated manner.

The computer system900is shown comprising hardware elements that can be electrically coupled via a bus905, or may otherwise be in communication, as appropriate. The hardware elements may include one or more processors910, including without limitation one or more general-purpose processors and/or one or more special-purpose processors such as digital signal processing chips, graphics acceleration processors, and/or the like; one or more input devices915, which can include without limitation a mouse, a keyboard, a camera, and/or the like; and one or more output devices920, which can include without limitation a display device, a printer, and/or the like.

The computer system900might also include a communications subsystem930, which can include without limitation a modem, a network card (wireless or wired), an infrared communication device, a wireless communication device, and/or a chipset such as a Bluetooth™ device, an 802.11 device, a WiFi device, a WiMax device, cellular communication facilities, etc., and/or the like. The communications subsystem930may include one or more input and/or output communication interfaces to permit data to be exchanged with a network such as the network described below to name one example, other computer systems, television, and/or any other devices described herein. Depending on the desired functionality and/or other implementation concerns, a portable electronic device or similar device may communicate image and/or other information via the communications subsystem930. In other embodiments, a portable electronic device, e.g. the first electronic device, may be incorporated into the computer system900, e.g., an electronic device as an input device915. In some embodiments, the computer system900will further comprise a working memory935, which can include a RAM or ROM device, as described above.

As mentioned above, in one aspect, some embodiments may employ a computer system such as the computer system900to perform methods in accordance with various embodiments of the technology. According to a set of embodiments, some or all of the procedures of such methods are performed by the computer system900in response to processor910executing one or more sequences of one or more instructions, which might be incorporated into the operating system940and/or other code, such as an application program945, contained in the working memory935. Such instructions may be read into the working memory935from another computer-readable medium, such as one or more of the storage device(s)925. Merely by way of example, execution of the sequences of instructions contained in the working memory935might cause the processor(s)910to perform one or more procedures of the methods described herein. Additionally or alternatively, portions of the methods described herein may be executed through specialized hardware.

The communications subsystem930and/or components thereof generally will receive signals, and the bus905then might carry the signals and/or the data, instructions, etc. carried by the signals to the working memory935, from which the processor(s)910retrieves and executes the instructions. The instructions received by the working memory935may optionally be stored on a non-transitory storage device925either before or after execution by the processor(s)910.

As used herein and in the appended claims, the singular forms “a”, “an”, and “the” include plural references unless the context clearly dictates otherwise. Thus, for example, reference to “a user” includes a plurality of such users, and reference to “the processor” includes reference to one or more processors and equivalents thereof known to those skilled in the art, and so forth.