Systems and methods for comparing documents containing graphic elements

• US 7,694,217 B2
• Filed: 05/31/2006
• Issued: 04/06/2010
• Est. Priority Date: 04/26/2005
• Status: Active Grant

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Morgan, Robert T., Croft, Lawrence
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US11/421,210
• Publication Number:
  US 20060242570A1
• Time in Patent Office: 1,406 Days
• Field of Search: 715/229, 715/230, 715/232, 715/233, 715/255, 715/243, 715/244, 715/246, 715/247
• US Class Current: 715/229
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A system and methods for comparing graphic elements in a changed document to those in a reference document is described. Attributes of selected graphic elements are first adjusted before comparing so that comparing does not identify certain document changes.

Claims

1. A method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages to be compared, one from each of the first document and the second document, respectively comprise corresponding first and second pluralities of graphic elements, the method comprising the steps of:

compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

comparing, on the computer, the first plurality of graphic elements and the second plurality of graphic elements;

generating information describing results of the comparing step;

displaying or printing the information;

wherein compensating for the change in the second document comprises adjusting selected attributes of the one of the second plurality of graphic elements prior to performing the comparing step;

wherein the selected attributes comprise a position of the one of the second plurality of graphic elements, and wherein the adjusting selected attributes comprises providing a shift in the position of the one of the second plurality of graphic elements;

wherein providing the position shift comprises;

comparing graphic elements to identify shifted elements wherein comparing comprises performing an element-wise comparison of each graphic element of the second plurality of graphic elements with the first plurality of graphic elements and wherein shifted elements comprise elements that are sufficiently similar between the documents except for a difference in position;

determining at least one candidate group of shifted graphic elements having substantially the same difference in position;

selecting one of the candidate groups to form the basis of the position shift, if more than one candidate group is determined; and

calculating the position shift based on the selected group.

2. A method according to claim 1, wherein comparing graphic elements to identify shifted elements comprises:

generating a first list and a second list, each comprising display-ordered unique identifiers corresponding to and associated with the first and second plurality of graphic elements, respectively, by comparing graphic elements of the first and second plurality of graphic elements without consideration for graphic element position;

deriving edit data from the first and second lists wherein the edit data can be used to change the first list into the second list;

identifying shifted elements based at least on the edit data, wherein a shifted element has an associated identifier with the same relative display order in both lists; and

calculating a difference in position for each shifted element.

3. A method according to claim 1, wherein graphic elements having substantially the same difference in position comprise graphic elements having a plurality of differences in position, wherein the plurality of differences in position vary from each other within a configurable tolerance.

4. A method according to claim 1, wherein selecting one of the candidate groups to form the basis of the position shift comprises one of:

selecting a candidate group with the largest quantity of graphic elements;

selecting a candidate group whose graphic elements collectively paint the largest area;

or selecting a candidate group based on user input.

5. A method according to claim 1, wherein calculating the position shift based on the selected group comprises calculating based on an average difference in position for graphic elements of the selected group.

6. A method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages to be compared, one from each of the first document and the second document, respectively comprise corresponding first and second pluralities of graphic elements, the method comprising the steps of:

compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

comparing, on the computer, the first plurality of graphic elements and the second plurality of a graphic elements;

generating information describing results of the comparing step;

displaying or printing the information;

wherein comparing the first and second plurality of graphic elements comprises;

associating a unique identifier with each graphic element of the first plurality of graphic elements, wherein the unique identifiers associated with the graphic elements of the first plurality of graphic elements, once associated, become existing identifiers;

comparing each one of the second plurality of graphic elements with the first plurality of a graphic elements;

associating a unique identifier with a graphic element of the second plurality of graphic elements if the graphic element is not sufficiently similar to any graphic element of the first plurality of graphic elements;

associating one of the existing identifiers with a graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to a first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the one of the existing identifiers; and

wherein comparing each one of the second plurality of graphic elements with the first plurality of graphic elements comprises performing a plurality of element-wise comparisons based on a plurality of similarity rules.

7. A method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages to be compared, one from each of the first document and the second document, respectively comprise corresponding first and second pluralities of graphic elements, the method comprising the steps of:

compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

comparing, on the computer, the first plurality of graphic elements and the second plurality of graphic elements;

generating information describing results of the comparing step;

displaying or printing the information;

wherein comparing the first and second plurality of graphic elements comprises;

associating a unique identifier with each graphic element of the first plurality of graphic elements, wherein the unique identifiers associated with the graphic elements of the first plurality of graphic elements, once associated, become existing identifiers;

comparing each one of the second plurality of graphic elements with the first plurality of graphic elements;

associating a unique identifier with a graphic element of the second plurality of graphic elements if the graphic element is not sufficiently similar to any graphic element of the first plurality of graphic elements;

associating one of the existing identifiers with a graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to a first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the one of the existing identifiers; and

wherein two graphic elements are considered sufficiently similar if any differences in corresponding attribute values of the two graphic elements are inconsequential enough so that the two graphic elements are visually similar when printed.

8. A method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages to be compared, one from each of the first document and the second document, respectively comprise corresponding first and second pluralities of graphic elements, the method corn rising the steps of:

compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

comparing, on the computer, the first plurality of graphic elements and the second plurality of graphic elements;

generating information describing results of the comparing step;

displaying or printing the information;

wherein comparing the first and second plurality of graphic elements comprises;

associating a unique identifier with each graphic element of the first plurality of graphic elements, wherein the unique identifiers associated with the graphic elements of the first plurality of graphic elements, once associated, become existing identifiers;

comparing each one of the second plurality of graphic elements with the first plurality of graphic elements;

associating a unique identifier with a graphic element of the second plurality of graphic elements if the graphic element is not sufficiently similar to any graphic element of the first plurality of graphic elements;

associating one of the existing identifiers with a graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to a first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the one of the existing identifiers; and

wherein two graphic elements are considered sufficiently similar if a predetermined difference between corresponding attribute values of the two graphic elements is within a tolerance.

9. A method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages to be compared, one from each of the first document and the second document, respectively comprise corresponding first and second pluralities of graphic elements, the method comprising the steps of:

compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

comparing, on the computer, the first plurality of graphic elements and the second plurality of graphic elements;

generating information describing results of the comparing step;

displaying or printing the information;

wherein comparing the first and second plurality of graphic elements comprises;

associating a unique identifier with each graphic element of the first plurality of graphic elements, wherein the unique identifiers associated with the graphic elements of the first plurality of graphic elements, once associated, become existing identifiers;

comparing each one of the second plurality of graphic elements with the first plurality of graphic elements;

associating a unique identifier with a graphic element of the second plurality of graphic elements if the graphic element is not sufficiently similar to any graphic element of the first plurality of graphic elements;

associating one of the existing identifiers with a graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to a first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the one of the existing identifiers; and

further comprising organizing the unique identifiers into a first list and a second list, entries of the first list corresponding to a display order of the graphic elements from the first document, and entries of the second list corresponding to a display order of the graphic elements from the second document.

10. A computer-accessible memory system stoma computer code for implementing a method for page-wise comparing a first document and a second document, each including at least one page, wherein a pair of pages, one from each of the first document and second document, to be compared respectively, comprise corresponding first and second pluralities of graphic elements respectively, and wherein the computer code comprises:

code for compensating for a change made in producing the second document that would cause one of the second plurality of graphic elements to be identified as a changed element in a comparison of the first and second documents;

code for comparing the first plurality of graphic elements and the second plurality of graphic elements;

code for generating information describing results of the comparing;

wherein the computer code further comprises;

code for determining a plurality of unique identifiers corresponding to at least some of the first and second plurality of graphic elements, wherein a unique identifier is associated with both a first graphic element from the first document and a second graphic element from the second document if characteristics of the first graphic element and the second graphic element are sufficiently similar;

code for organizing the unique identifiers into a first list and a second list, the entries of the first list corresponding to a display order of the graphic elements from the first document, and the second list corresponding to a display order of the graphic elements from the second document; and

code for deriving edit data from the first and second lists, wherein the edit data can be used to change the first list into the second list.

11. A computer-accessible memory system according to claim 10, wherein the computer code further comprises code for generating at least one target document based at least on the first and second documents, the first and second lists, and the edit data.

12. A computer-accessible memory system according to claim 11, wherein the at least one target document comprises a layered document having a plurality of layers including at least:

a common-to-both layer comprising graphic elements from the first document that are sufficiently similar to graphic elements from the second document;

a unique-to-first layer comprising graphic elements that are unique to the first document; and

a unique-to-second layer comprising graphic elements that are unique to the second document.

13. A computer-accessible memory system according to claim 11, wherein The computer code further comprises code for presenting a view of at least one target document comprising a plurality of layer views, a layer view comprising pixels rendered from a plurality of graphic elements associated with a layer view, the visibility of a layer view being separately controllable.

14. A method for merging documents, the method comprising:

obtaining an original document from a data store comprising a plurality of graphic elements;

modifying the original document on a computer for print production to produce a first document wherein the first document includes at least one shifted graphic element that is substantially unmodified except for a positional shift on a page;

obtaining a second document from the data store comprising a revision to the original document;

identifying The positional shift for the at least one shifted graphic element of the first document;

applying the positional shift to the corresponding graphic elements of the second document;

merging the first and second documents into a merged document on the computer by comparing graphic elements of the first and second documents; and

displaying or printing the merged document.

15. A method according to claim 14 wherein identifying the positional shift for the at least one shifted graphic element comprises:

comparing graphic elements from the first document with graphic elements from the second document to identify shifted elements;

grouping the shifted elements based on the magnitude of their positional shifts; and

identifying the at least one shifted graphic element and the corresponding positional shift by selecting one of the groups.

16. A method according to claim 15 wherein comparing graphic elements to identify shifted elements comprises:

generating a first list and a second list, each comprising display-ordered unique identifiers corresponding to and associated with graphic elements of the first and second documents, respectively, by comparing graphic elements without consideration for graphic element position;

deriving edit data from the first and second lists wherein the edit data can be used to change the first list into the second list;

identifying shifted elements based at least on the edit data, wherein a shifted element has an associated identifier with the same relative display order in both lists; and

calculating a difference in position for each shifted element based on an actual position of the shifted graphic element defined by respective documents.

17. A method according to claim 14 wherein merging comprises:

comparing graphic elements of the first and second documents to derive edit data; and

applying the edit data to the first document to produce the merged document.

18. A method according to claim 17, wherein comparing graphic elements of the first and second document comprises:

selecting a first and second plurality of graphic elements from the first and second documents, respectively;

associating a unique identifier with each graphic element of the first plurality of graphic elements, wherein the unique identifiers associated with the graphic elements of the first plurality of graphic elements, once associated, become existing identifiers;

comparing each one of the second plurality of graphic elements with the first plurality of graphic elements;

associating a unique identifier with a graphic element of the second plurality of graphic elements if the graphic element is not sufficiently similar to any graphic element of the first plurality of graphic elements; and

associating one of the existing identifiers with a graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to a first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the one of the existing identifiers.

19. A method according to claim 18, wherein comparing each one of the second plurality of graphic elements with the first plurality of graphic elements comprises performing a plurality of element-wise comparisons based on a plurality of similarity rules.

20. A method according to claim 19, wherein two graphic elements are considered sufficiently similar if any differences in corresponding attribute values of the two graphic elements are inconsequential enough so that the two graphic elements are visually similar when printed.

21. A method according to claim 19, wherein two graphic elements are considered sufficiently similar if a predetermined difference between corresponding attribute values of the two graphic elements is within a tolerance.

22. A method according to claim 19, further comprising organizing the unique identifiers into a first list and a second list, entries of the first list corresponding to a display order of the graphic elements from the first document, and entries of the second list corresponding to a display order of the graphic elements from the second document.

23. A method according to claim 14 comprising visualizing the merged document to identify differences between the documents.

24. A computer-accessible memory system storing computer code for implementing a method for merging documents, the computer code comprising:

code for obtaining an original document comprising a plurality of graphic elements;

code for modifying the original document for print production to produce a first document wherein the first document includes at least one shifted graphic element that is substantially unmodified except for a positional shift on a page;

code for obtaining a second document comprising a revision to the original document;

code for identifying the positional shift for the at least one shifted graphic element of the first document;

code for applying the positional shift to the corresponding graphic elements of the second document; and

code for merging the first and second documents into a merged document by comparing graphic elements of the first and second documents.