Systems and methods for comparing documents containing graphic elements

• US 7,555,712 B2
• Filed: 04/26/2005
• Issued: 06/30/2009
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Kodak Canada ULC
• Original Assignee: Kodak Graphic Communications Canada Company (Eastman Kodak Company)
• Inventors: Morgan, Rob, Croft, Lawrence
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US11/114,078
• Publication Number:
  US 20050240858A1
• Time in Patent Office: 1,526 Days
• Field of Search: 715/255, 715/229, 715/230, 715/247
• US Class Current: 715/247
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/93 Document management systems
• 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 two documents comprising graphic elements is described. Attributes of graphic elements amongst the two documents are examined to identify sufficiently similar graphic elements. A merged document can be automatically produced based on the comparison. The merged document advantageously preserves the investment made in modifying a first document during a production phase. A means for viewing the comparison results and overriding the automatically generated merge actions is provided.

Claims

1. A computer-implemented method for comparing first and second documents, the first and second documents containing corresponding first and second pluralities of graphic elements, the method comprising assigning a plurality of unique identifiers to the graphic elements of the first and second pluralities of graphic elements wherein each graphic element is assigned an identifier and wherein, upon determining that a first graphic dement of the first plurality of graphic dements is sufficiently similar to a second graphic dement of the second plurality of graphic dements, the method comprises associating the same one of the unique identifiers with both the first and second graphic elements;

associating a unique identifier with each graphic element of the first plurality of graphic elements;

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 an existing identifier with the graphic element of the second plurality of graphic elements if the graphic element is sufficiently similar to the first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the existing identifier;

wherein comparing 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;

wherein the plurality of similarity rules include rules that identify two graphic elements as being sufficiently similar if any differences in their corresponding attribute values result in the two graphic elements being visually similar when printed; and

wherein a similarity rule is based on at least one graphic element attribute accuracy value wherein two graphic elements are considered sufficiently similar if, for each at least one graphic element attribute accuracy value, the corresponding values of the two graphic element attributes differ by less than the corresponding accuracy value.

2. A computer-implemented method for comparing first and second documents, the first and second documents containing corresponding first and second pluralities of graphic elements, the method comprising assigning a plurality of unique identifiers to the graphic elements of the first and second pluralities of graphic elements wherein each graphic element is assigned an identifier and wherein, upon determining that a first graphic element of the first plurality of graphic elements is sufficiently similar to a second graphic element of the second plurality of graphic elements, the method comprises associating the same one of the unique identifiers with both the first and second graphic elements;

associating a unique identifier with each graphic element of the first plurality of graphic elements;

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 an existing identifier with the graphic element of the second plurality of graphic dements if the graphic element is sufficiently similar to the first graphic element of the first plurality of graphic elements wherein the first graphic element is associated with the existing identifier; and

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.

3. A method according to claim 2 comprising:

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; and

creating at least one target document based on the first and second documents, the first and second lists, and the edit data.

4. A method according to claim 3 wherein creating at least one target document comprises:

applying the edit data to at least one of the first list and the second list to form a target list; and

creating at least one target document based at least in part on graphic elements associated with the target list.

5. A method according to claim 3 wherein the first and second plurality of graphic elements are chosen for comparison based on a selection criterion wherein the selection criterion is based on graphic element attributes and information associated with the first and second documents;

and,

wherein zero or more unselected graphic elements from the first document and the second document are excluded by the selection criterion.

6. A method according to claim 3 wherein the edit data comprises a plurality of actions wherein actions comprise actions of a plurality of action types, the action types including:

delete, corresponding to a graphic element that is unique to the first document;

add, corresponding to a graphic element that is unique to the second document; and

no-action, corresponding to a graphic element in the first document that is sufficiently similar to a graphic element in the second document.

7. A method according to claim 6 wherein deriving the edit data from the first and second lists comprises:

examining identifiers from the first and second lists in an ordered fashion until a current common identifier is found;

creating a no-action action in the edit data for the current common identifier;

creating delete actions in the edit data for all identifiers in the first list between the previous common identifier, or the start of the first list initially, and the current common identifier;

creating add actions in the edit data for all identifiers from the second list, occurring between the previous common identifier, or the start of the second list initially, and the current common identifier; and

repeating the steps above until the end of the first and second lists is reached wherein the end of the first and second lists are treated as a current common identifier for the creating delete actions and creating add actions steps.

8. A method according to claim 7 wherein deriving edit data from the first and second lists comprises using a largest common substring algorithm.

9. A method according to claim 6 wherein creating at least one target document comprises creating a merged document.

10. A method according to claim 9 wherein creating a merged document comprises:

deleting, from the first document, each graphic element that is unique to the first document;

preserving, from the first document, the zero or more unselected graphic elements from the first document;

preserving, from the first document, each graphic element from the first document that is sufficiently similar to a graphic element from the second document; and

adding, from the second document, each graphic element that is unique to the second document wherein adding preserves the relative order of a graphic element amongst graphic elements added from or sufficiently similar to those from the second document.

11. A method according to claim 10 wherein the selection criterion identifies graphic elements of the content graphic element category to preserve production graphic elements from the first document in the merged document.

12. A method according to claim 10 wherein creating the merged document includes generating information about graphic elements affected by creating the merged document.

13. A method according to claim 10 wherein creating the merged document includes deleting a graphic element from the merged document if the graphic element is dependent upon a graphic element deleted by creating the merged document.

14. A method according to claim 10 comprising:

adjusting attributes of a preserved trap-production graphic element to conform to trapping rules associated with the first document; and

creating a new trap-production graphic clement to conform to trapping rules associated with the first document.

15. A method according to claim 3 wherein the edit data comprises a plurality of actions wherein actions comprise actions of a plurality of action types, the action types including:

delete, corresponding to a graphic element that is unique to the first document;

add, corresponding to a graphic element that is unique to the second document;

no-action, corresponding to a graphic element in the first document that is sufficiently similar to a graphic element in the second document;

wherein creating at least one target document comprises creating a merged document;

deleting, from the first document, each graphic element that is unique to the first document;

preserving, from the first document, the zero or more unselected graphic elements from the first document;

preserving, from the first document, each graphic element from the first document that is sufficiently similar to a graphic element from the second document;

adding, from the second document, each graphic element that is unique to the second document wherein adding preserves the relative order of a graphic element amongst graphic elements added from or sufficiently similar to those from the second document;

wherein creating the merged document includes generating information about graphic elements affected by creating the merged document; and

wherein generating information about graphic elements affected by creating the merged document includes providing information about the printing plate colorants affected based on the colorants of the graphic elements affected by creating the merged document.

16. A method according to claim 3 wherein creating at least one target document comprises creating a layered document, having a plurality of layers including at least:

a common-to-both layer containing graphic elements from one of the first and second documents that are sufficiently similar to corresponding graphic elements of the other one of the first and second documents;

a unique-to-first layer containing graphic elements present in the first document but not the second document; and

,

a unique-to-second layer containing graphic elements present in the second document but not the first document.

17. A method according to claim 16 wherein creating a layered document comprises:

adding a plurality of graphic elements from the first and second documents to the layered document; and

associating each graphic element in the layered document with one of the layers based on the first and second documents, the first and second lists, the selection criterion and the edit data.

18. A method according to claim 17 wherein adding a plurality of graphic elements from the first and second documents comprises:

adding a plurality of graphic elements from the first document wherein the relative order of the plurality of graphic elements is preserved;

adding a plurality of graphic elements from the second document wherein the relative order of the plurality of graphic elements is preserved;

retaining a relative ordering of a graphic element added from one of the first or second document with respect to a common graphic element added from the other of the first or second document.

19. A method according to claim 16 comprising presenting a view of the target document, the view comprising a plurality of layer views, a layer view comprising pixels rendered from a plurality of graphic elements associated with a document layer, the visibility of a layer view being separately controllable.

20. A method according to claim 19 comprising:

selecting a graphic element associated with a layer view;

changing an edit data action associated with the graphic element to manifest a user-defined revision to the edit data.

21. A method according to claim 16 comprising:

selecting a graphic element associated with a layer;

changing an edit data action associated with the graphic element to manifest a user-defined revision to the edit data.

22. A method according to claim 3 wherein creating at least one target document comprises:

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

creating a unique-to-first document comprising graphic elements unique to the first document; and

creating a unique-to-second document comprising graphic elements unique to the second document.

23. A method according to claim 22 wherein creating a common-to-both document comprises applying the no-action edit data to either the first list or the second list to select graphic elements common to the first and second documents.

24. A method according to claim 23 wherein creating a unique-to-first document comprises applying the delete edit data to the first list to select graphic elements that are unique to the first document.

25. A method according to claim 23 wherein creating a unique-to-second document comprises applying the add edit data to the second list to select graphic elements that are unique to the second document.

26. A method according to claim 22 wherein a plurality of graphic elements associated with a layer view comprises graphic elements defined by one of the common-to-both document, the unique-to-first document, and the unique-to-second document.

27. A method according to claim 3 comprising:

presenting a view of at least one target document comprising a plurality of layer views, each layer view comprising pixels rendered from a plurality of graphic elements associated with a layer, the visibility of each layer view being controllable separately from the visibility of other layer views.