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.
1. A computer-implemented method comprising:
obtaining a document image, the document image being at least two-dimensional;
obtaining one or more form images, wherein each of the one or more form images is at least two-dimensional and includes a plurality of rows and a plurality of columns;
projecting the document image onto a horizontal axis and a vertical axis to create a horizontal document projection and a vertical document projection;
projecting the one or more form images onto the horizontal axis and the vertical axis to create one or more horizontal form projections and one or more vertical form projections;
correlating the horizontal document projection with the one or more horizontal form projections to create one or more horizontal correlation functions and the vertical document projection with the one or more vertical form projections to create one or more vertical correlation functions;
calculating a correlation score for each of the one or more form images based on the one or more horizontal correlation functions and the one or more vertical correlation functions; and
determining which of the one or more form images corresponds to the document image based on a comparison of the correlation score for each of the one or more form images.
2. The computer-implemented method of claim 1 , further comprising:
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;
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;
combining the horizontal correlation score with the vertical correlation score for each of the one or more form images to create combined scores; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
3. The computer-implemented method of claim 1 , further comprising:
determining a missing portion and an available portion of the document image;
determining a horizontal weighting function by projecting the missing portion and the available portion onto the horizontal axis; and
determining a vertical weighting function by projecting the missing portion and the available portion onto the vertical axis.
4. The computer-implemented method of claim 3 , further comprising:
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;
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;
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; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
5. The computer-implemented method of claim 4 , wherein combining the weighted horizontal correlation score with the weighted vertical correlation score includes either adding or averaging the weighted horizontal correlation score and the weighted vertical correlation score.
6. The computer-implemented method of claim 1 , further comprising:
rotating the document image such that the document image is vertically aligned with the vertical axis and horizontally aligned with the horizontal axis.
7. The computer-implemented method of claim 1 , further comprising:
stretching or shortening the horizontal document projection over the horizontal axis such that the horizontal document projection either increases or decreases in length; or
stretching or shortening the vertical document projection over the vertical axis such that the vertical document projection either increases or decreases in length.
8. The computer-implemented method of claim 1 , wherein the document image is an image of a family history document and the one or more form images are images of one or more form types for family history documents.
9. The computer-implemented method of claim 1 , wherein calculating the correlation score for each of the one or more form images includes summing each of the one or more horizontal correlation functions and each of the one or more vertical correlation functions.
10. A computer readable storage media comprising instructions to cause one or more processors to perform operations comprising:
obtaining a document image, the document image being at least two-dimensional;
obtaining one or more form images, wherein each of the one or more form images is at least two-dimensional and includes a plurality of rows and a plurality of columns;
projecting the document image onto a horizontal axis and a vertical axis to create a horizontal document projection and a vertical document projection;
projecting the one or more form images onto the horizontal axis and the vertical axis to create one or more horizontal form projections and one or more vertical form projections;
correlating the horizontal document projection with the one or more horizontal form projections to create one or more horizontal correlation functions and the vertical document projection with the one or more vertical form projections to create one or more vertical correlation functions;
calculating a correlation score for each of the one or more form images based on the one or more horizontal correlation functions and the one or more vertical correlation functions; and
determining which of the one or more form images corresponds to the document image based on a comparison of the correlation score for each of the one or more form images.
11. The computer readable storage media of claim 10 , wherein the operations further comprise:
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;
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;
combining the horizontal correlation score with the vertical correlation score for each of the one or more form images to create combined scores; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
12. The computer readable storage media of claim 10 , wherein the operations further comprise:
determining a missing portion and an available portion of the document image;
determining a horizontal weighting function by projecting the missing portion and the available portion onto the horizontal axis; and
determining a vertical weighting function by projecting the missing portion and the available portion onto the vertical axis.
13. The computer readable storage media of claim 12 , wherein the operations further comprise:
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;
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;
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; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
14. The computer readable storage media of claim 10 , wherein calculating the correlation score for each of the one or more form images includes summing each of the one or more horizontal correlation functions and each of the one or more vertical correlation functions.
15. A system comprising:
one or more processors; and
one or more computer readable storage mediums comprising instructions to cause the one or more processors to perform operations comprising:
obtaining a document image, the document image being at least two-dimensional;
obtaining one or more form images, wherein each of the one or more form images is at least two-dimensional and includes a plurality of rows and a plurality of columns;
projecting the document image onto a horizontal axis and a vertical axis to create a horizontal document projection and a vertical document projection;
projecting the one or more form images onto the horizontal axis and the vertical axis to create one or more horizontal form projections and one or more vertical form projections;
correlating the horizontal document projection with the one or more horizontal form projections to create one or more horizontal correlation functions and the vertical document projection with the one or more vertical form projections to create one or more vertical correlation functions;
calculating a correlation score for each of the one or more form images based on the one or more horizontal correlation functions and the one or more vertical correlation functions; and
determining which of the one or more form images corresponds to the document image based on a comparison of the correlation score for each of the one or more form images.
16. The system of claim 15 , wherein the operations further comprise:
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;
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;
combining the horizontal correlation score with the vertical correlation score for each of the one or more form images to create combined scores; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
17. The system of claim 15 , wherein the operations further comprise:
determining a missing portion and an available portion of the document image;
determining a horizontal weighting function by projecting the missing portion and the available portion onto the horizontal axis; and
determining a vertical weighting function by projecting the missing portion and the available portion onto the vertical axis.
18. The system of claim 17 , wherein the operations further comprise:
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;
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;
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; and
determining which of the one or more form images corresponds to the document image by determining a maximum score of the combined scores.
19. The system of claim 15 , wherein the operations further comprise:
rotating the document image such that the document image is vertically aligned with the vertical
axis and horizontally aligned with the horizontal axis.
20. The system of claim 15 , wherein calculating the correlation score for each of the one or more form images includes summing each of the one or more horizontal correlation functions and each of the one or more vertical correlation functions.