Systems and methods for comparing documents containing graphic elements

• US 20050240858A1
• Filed: 04/26/2005
• Published: 10/27/2005
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Kodak Canada ULC
• Original Assignee: Creo Incorporated (Eastman Kodak Company)
• Inventors: Croft, Lawrence, Morgan, Rob
• Granted Patent: US 7,555,712 B2
• Time in Patent Office: Days
• US Class Current: 715/229
• 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 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, 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.

2. A method according to claim 1 comprising:

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

,

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.

3. A method according to claim 2 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.

4. A method according to claim 3 wherein performing a plurality of element-wise comparisons comprises:

creating a hash value for a graphic element based on attribute values of the graphic element;

associating the graphic element with the hash value; and

performing an element-wise comparison between a first graphic element and a second graphic element if the first and second graphic elements are associated with the same hash value.

5. A method according to claim 3 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.

6. A method according to claim 5 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.

7. A method according to claim 2 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.

8. A method according to claim 7 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.

9. A method according to claim 8 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.

10. A method according to claim 8 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.

11. A method according to claim 8 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.

12. A method according to claim 11 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.

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

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

15. A method according to claim 14 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.

16. A method according to claim 15 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.

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

18. A method according to claim 1 wherein the first and second documents conform to the Adobe®

Portable Document Format specification.

19. A method according to claim 17 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.

20. A method according to claim 15 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.

21. A method according to claim 1 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 element to conform to trapping rules associated with the first document.

22. A method according to claim 8 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.

23. A method according to claim 22 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.

24. A method according to claim 23 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.

25. A method according to claim 22 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.

26. A method according to claim 25 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.

27. A method according to claim 8 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.

28. A method according to claim 27 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.

29. A method according to claim 28 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.

30. A method according to claim 28 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.

31. A method according to claim 8 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.

32. A method according to claim 27 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.

33. A method according to claim 22 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.

54. A medium carrying a set of computer-readable signals comprising instructions which, when executed by a data processor, cause the data processor to execute a method according to claim 1.

34. A system for comparing documents, the system comprising:

identifier-assigning means for assigning a plurality of unique identifiers to graphic elements of a first and second plurality of graphic elements of a first and second document respectively; and

,

a comparison means for comparing graphic elements to determine if two graphic elements are sufficiently similar wherein the identifier-assigning means is configured to associate a unique identifier with both a first graphic element from the first document and a second graphic element from the second document if the comparison means determines that the first and second graphic elements are sufficiently similar to one another.

35. A system according to claim 34 wherein the identifier-assigning means comprises:

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

means for 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

,

means for associating an existing identifier 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 existing identifier.

36. A system according to claim 35 wherein the system for comparing documents also includes:

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

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

,

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

37. A system according to claim 36 wherein means for creating at least one target document comprises:

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

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

38. A system according to claim 37 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.

39. A system according to claim 38 wherein the edit data comprises a plurality of actions wherein actions comprise actions of a plurality of action types, the action types comprising:

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.

40. A system according to claim 39 wherein means for creating at least one target document comprises means for creating a merged document that is visually similar to the second document when printed.

41. A system according to claim 40 wherein means for creating a merged document comprises:

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

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

means for 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

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

42. A system according to claim 41 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.

43. A system according to claim 41 wherein means for creating the merged document also includes means for generating information about graphic elements affected by creating the merged document.

44. A system according to claim 42 comprising:

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

,

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

45. A system according to claim 36 wherein means for creating at least one target document comprises means for creating a layered document, having a plurality of layers including at least a common-to-both layer, a unique-to-first layer, and a unique-to-second layer.

46. A system according to claim 45 wherein means for comparing documents also includes means for visually comparing layers of a layered document.

47. A system according to claim 46 wherein means for visually comparing layers of a layered document comprises means for presenting a view of the layered document comprising a plurality of layer views, each layer view comprising pixels rendered from a plurality of graphic elements associated with a layered document layer, the visibility of a layer view being controllable separately from the visibility of other layer views.

48. A system according to claim 47 wherein means for visually comparing layers of a layered document includes:

means for selecting a graphic element associated with a layer view;

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

49. An apparatus for comparing documents, the apparatus comprising:

a document comparator, operative to;

determine a plurality of unique identifiers corresponding to a first and second plurality of graphic elements defined by a first and second document respectively 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 the characteristics of the first and second graphic elements are sufficiently similar;

organize 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

derive 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

a document merger, operative to create at least one target document based on the first and second documents, the first and second lists, and the edit data.

50. An apparatus according to claim 49 wherein the at least one target document comprises a merged document that is visually similar to the second document when printed.

51. An apparatus according to claim 49 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.

52. An apparatus according to claim 49 wherein the at least one target document comprises:

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

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

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

53. An apparatus according to claim 49 comprising a comparison visualizer operative to present 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.