System and method for adaptive document layout via manifold content

• US 20030229845A1
• Filed: 05/30/2002
• Published: 12/11/2003
• Est. Priority Date: 05/30/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Salesin, David, Jacobs, Charles, Li, Wilmot
• Granted Patent: US 7,120,868 B2
• Time in Patent Office: Days
• US Class Current: 715/500
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents

Abstract

A system and method for improving document layout on arbitrary devices of different resolutions and size using manifold representations of content. Manifold representations of content are: multiple versions of anything that might appear in a document, from text, to images, to even such things as stylistic conventions. The specific content is selected and formatted dynamically, on the fly, by a layout engine in order to best adapt to a given viewing situation. A user interface for authoring and editing such manifold content is disclosed.

Claims

1. A computer-implemented process for creating an adaptive document, comprising using a computer to perform the following process, actions:

inputting manifold representations of document content; and

automatically formatting said manifold representations of document content to fit a viewing situation.

2. The computer-implemented process of claim 1 wherein inputting said manifold representations of document content comprises associating each representation of document content with a tree data structure.

3. The computer-implemented process of claim 2 wherein each branch of said tree data structure represents an alternate version of document content.

4. The computer-implemented process of claim 3 wherein said tree data structure originates in an AND node and contains one or more children of alternate document content.

5. The computer-implemented process of claim 2 wherein OR nodes are used to organize said manifold representations of document content in said tree data structure.

6. The computer-implemented process of claim 2 wherein

an AND node is used to specify a contiguous representation of document content in said tree data structure;

and

an OR node is used to specify one of a plurality of pieces of document content is said tree data structure.

7. The computer-implemented process of claim 2,

wherein said tree data structure is divided into sub-trees;

and

wherein two sub-trees are considered equivalent if their structure creates identical sets of document views.

8. The computer-implemented process of claim 2 wherein the process action of inputting a manifold representation of document content further comprises creating a new representation of document content by the following process actions:

inputting selected document content and said document tree;

looking for a document sub-tree that can exactly generate the region of selected document content;

if an exact sub-tree is not found, creating a new sub-tree corresponding to the region of selected document content; and

once an exact sub-tree corresponding to the selected document content is found or created, creating a new representation of manifold content by modifying the document tree so that the sub-tree corresponding to the region of selected document content becomes a child of a new OR node.

9. The computer-implemented process of claim 8 wherein said new representation of manifold content associated with said new OR node is combined under an AND node with the content before the selected document content and the content after the selected document content.

10. The computer-implemented process of claim 2 wherein an Extensible Markup Language (XML) file format is used to specify said tree data structure.

11. The computer-implemented process of claim 10 further comprising using XML file format to specify attributes associated with each representation of document content.

12. The computer-implemented process of claim 10 wherein at least one of the following is used to represent document content structure:

an OR node representing a choice of content;

an AND node representing a contiguous representation of content;

a text node representing text content;

a div node representing a collection of content to be laid out in a rectangle; and

an image node representing anan identifier associated with an image file.

13. The computer-implemented process of claim 11 wherein each child of an OR node is placed between the (OR) and (/OR) tokens and is associated with attributes in a REP node denoted by the token pair (REP) attributes . . . (/REP).

14. The computer-implemented process of claim 2 wherein a user can modify said alternate versions of content and wherein said user modifications will modify said tree data structure.

15. The computer-implemented process of claim 14 wherein modifying the alternate content modifies the tree data structure by at least one of the following:

deleting a version of document content will delete an OR node associated with said document content from said tree data structure;

copying a version of alternate content will duplicate said copied version of alternate version as a sub-tree to the document tree; and

copying a version of alternate content by using a special copy operation will copy a selected region of alternate content but not preserve its underlying structure in the document tree.

16. A graphic user interface for authoring an electronic document viewed on a display device, comprising a user interface for authoring alternate versions of document content.

17. The graphic user interface of claim 16 further comprising

an edit view pane for displaying a linear version of document content;

and

an alternate version view pane for displaying alternate versions of document content.

18. The graphic user interface of claim 16 wherein alternate versions of document content are indicated by an indicator associated with that portion of document content.

19. The graphic user interface of claim 18 wherein said indicator is a line beneath that portion of document content.

20. The graphic user interface of claim 16 wherein hovering with an input device cursor over a region of document content configurable into alternate document content further comprises bringing up a menu with editing choices.

21. The graphic user interface of claim 20 wherein said menu of editing choices comprises at least one of the following user options:

select version, which when activated highlights selected content in said alternate version view pane along with other unhighlighted versions of document content;

pop selection, which when activated displays the highest level of alternate version content if nested versions of alternate content exist;

create version, which when activated to creates a version of alternate content; and

freeze version, which when activated to prevent a version of alternate content from being changed.

22. The graphic user interface of claim 19 wherein alternate versions of document content are nested, and wherein only the outermost level of alternate content is indicated with a line underneath.

23. The graphic user interface of claim 22 wherein overlapping versions of alternate content are not underlined twice and wherein:

only the outermost shell of alternate content is displayed with an underline for alternate content that is selected;

alternate content outside the selected version of alternate content is displayed with an underline; and

the user can display change a currently selected region of alternate content by selecting another region of alternate content that is displayed.

24. The graphic user interface of claim 17 wherein the user can change a first version of alternate content that is displayed in the edit view pane by selecting a second version of alternate content displayed in alternate version view pane, said second version of alternate content then replacing said first version in the edit view pane.

25. The graphic user interface of claim 17 wherein an indicator is drawn to the left margin of the beginning of each piece of alternate version content in the alternate version view pane to indicate a start of an alternate version of document content.

26. The graphic user interface of claim 17 wherein a user can add alternate versions of document content by copying document content or by entering the alternate version in the alternate version view pane.

27. The graphic user interface of claim 17 wherein an image version of alternate content is identified by an icon.

28. The graphic user interface of claim 27 wherein backspacing over said icon removes said image file.

29. The graphic user interface of claim 27 wherein a user can view an image file in a separate view pane by clicking on the menu with an input device to bring up a menu and choosing an option that allows image viewing.

30. The graphic user interface of claim 17 wherein hovering over a portion of alternate content with an input device cursor in the alternate version pane provides a menu of user options.

31. The graphic user interface of claim 30 wherein said menu comprises at least one of the following user options:

add version, to add a new version of alternate content;

delete version, to delete a version of alternate content; and

copy version, to copy a version of alternate content.

32. The graphic user interface of claim 17 further comprising text editing functionality of at least one of:

selecting font type;

selecting font size; and

selecting font style.

33. A system for laying out a document, the system comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

create a plurality of versions of content; and

automatically format said versions of content to fit a display.

34. The system of claim 33 wherein said plurality of versions of content comprise at least one of:

text;

graphics;

images;

links;

formatting instructions;

stylistic conventions; and

user interface controls.

35. The system of claim 33 wherein said display comprises at least one of:

a hand-held device;

a wide-screen display; and

a computer monitor.

36. The system of claim 33 wherein said program module to format further comprises a sub-module to use at least one of the following attributes in automatically formatting the data:

user-preferences;

available computing power; and

available bandwidth.

37. The system of claim 33 wherein said plurality of versions of content can be combined to create alternate document views, each document view depicting different document content.

38. The system of claim 33 wherein said alternate versions of content are organized using a tree data structure employing OR nodes to arrange said alternate versions of content.

39. The system of claim 33 wherein said sub-module to automatically format said versions of content to fit a display, comprises sub-modules for:

inputting a tree data structure used to arrange said alternate versions of content into content nodes, and a rectangular region wherein said content is to be displayed;

traversing said tree data structure, calling an appropriate layout engine when content nodes are encountered to determine the size of a rectangular pane of content within said rectangular region; and

once the pane sizes are determined for each content node, rendering said content in each pane.

40. The system of claim 39 wherein said content rendering sub-module further comprises sub-modules for:

inputting pane size, alternate versions of content, and attributes of the content to be rendered;

evaluating each version of text content to find the best line breaking solution for each version of alternate content, providing a text goodness score for each version;

evaluating each version of image content to find the best figure placement solution, providing a figure goodness score for each version of figure placement;

determining the best combinations of alternate versions of text and figure content using a layout goodness score based on said text and figure goodness scores; and

rendering the text and figure combination with the best layout goodness score is then rendered in the pane.

41. The system of claim 43 further comprising a program sub-module for refining the best combinations and re-computing the layout goodness scores for the best combinations after refining said best combinations.

42. The system of claim 40 wherein the sub-module for evaluating each version of text content to find the best line breaking solution further comprises sub-modules for:

recording break points for any place that the text could be broken, including breakpoints that correspond to alternate text wordings as the tree is traversed;

recording information about conflicting break points as said tree is traversed;

starting with the 0-th and working towards the m-th partial paragraph, where m is the total number of breakpoints found when recording break points for any place the text could be broken, computing the minimum cumulative badness, S_i, associated with the sub-problem of breaking the i-th partial paragraph, wherein the content up to break point i is the i-th partial paragraph;

storing for each computed minimum cumulative minimum badness, S_i, the previous break, P_i, used to achieve minimum cumulative badness;

once the minimum cumulative badness for all recorded break points, S_m, and P_m, the previous breakpoint used to achieve S_m, have been computed, recovering the actual breaks that achieve the minimum badness for the entire paragraph, by backtracking through the computed set of previous breaks, starting at P_m; and

collecting all of the words between breaks to determine the actual text for each line of paragraph.

43. The system of claim 40 wherein the sub-module for computing a layout goodness score further comprises a scoring mechanism, where content attributes associated with each version of content are evaluated for each version of content, providing a penalty score for each version and wherein the content version with the lowest penalty score is rendered.

44. The system of claim 43 wherein said penalty score is determined if a version of content'"'"'s viewing parameters fall outside of a range given by an attribute associated with said version of content.

45. The system of claim 44 wherein said penalty score contains two terms,

a constant value as a penalty for falling outside of the valid viewing range at all, and

a weighted value proportional to how far outside of the range the parameter is.

46. The system of claim 45 wherein said penalty score is determined as said weighted value multiplied by distance outside of valid viewing range plus said constant value.

47. The system of claim 43 wherein said content attributes include at least one of:

attributes concerning page size;

attributes concerning column size;

attributes concerning page coverage; and

attributes concerning figure size.

48. The system of claim 43 wherein said content attributes include at least one of:

minimum page width,

maximum page width,

minimum page height,

maximum page height,

page size weight,

page size bias,

minimum column width,

maximum column width,

columns size weight,

column size bias,

minimum page coverage;

maximum page coverage;

minimum vertical page coverage;

maximum vertical page coverage;

minimum horizontal page coverage;

maximum horizontal page coverage;

page coverage weight;

minimum figure width,

maximum figure width,

figure size weight, and

figure size bias.

49. The system of claim 40 wherein said sub-module for evaluating each version of image content to find the best figure placement solution, further comprises a sub-module for providing a goodness score for each version of figure placement.

50. The system of claim 49 wherein said sub-module for providing a goodness score for figure placement further comprises sub-modules for:

determining an approximate rough goodness score for each version of figure placement of the page layout using an approximate text flow to try all versions of figure placement; and

once all versions of figure placement have been tried, using a more careful text formatting procedure for the best few versions of figure placement.

51. The system of claim 49 wherein the sub-module for providing a goodness score for figure placement further comprises sub-modules for at least one of:

measuring distances between figures and the text that references them, and penalizing figures that do not fall on the same page as their reference;

computing a score for the formatting of each line of text;

computing a score for any widows or orphans; and

computing a score for user preferences.

52. A computer-readable medium having computer-executable instructions for creating a document adaptable for viewing on different display sizes, said computer executable instructions comprising:

creating a plurality of alternate versions of content; and

automatically selecting some of said alternate versions of content to best fit a given display size.