Constraint-based albuming of graphic elements

• US 7,644,356 B2
• Filed: 06/10/2005
• Issued: 01/05/2010
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Enachescu, Mihaela Irina, Lin, Xiaofan, Atkins, C. Brian
• Primary Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US11/151,167
• Publication Number:
  US 20060279566A1
• Time in Patent Office: 1,670 Days
• Field of Search: 715/200, 715/243, 715/764
• US Class Current: 715/243
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

Methods, machines, systems and machine-readable instructions for albuming graphic elements are described. In one aspect, candidate relative layouts of graphic elements on a page are identified. Each of the candidate relative layouts describes a respective set of layout relationships among the graphic elements. A respective set of constraints describing the corresponding set of layout relationships among the graphic elements is generated for each of the candidate relative layouts. A respective determinate layout of the graphic elements on the page is determined from each set of constraints. One of the determinate layouts is selected as a final layout of the graphic elements on the page.

Claims

1. A machine-implemented method of albuming graphic elements, comprising:

identifying candidate relative layouts of graphic elements on a page, wherein each of the candidate relative layouts describes a respective set of layout relationships among the graphic elements;

generating for each of the candidate relative layouts a respective set of constraints describing the corresponding set of layout relationships among the graphic elements;

determining a respective determinate layout of the graphic elements on the page from each set of constraints; and

selecting one of the determinate layouts as a final layout of the graphic elements on the page.

2. The method of claim 1, wherein the identifying comprises locating the graphic elements in respective tree structures corresponding to the candidate relative layouts, each of the tree structures having one or more leaf nodes corresponding to respective ones of the graphic elements and one or more interior nodes corresponding to respective divisions of the page.

3. The method of claim 2, wherein the locating comprises locating in a respective one of the tree structures a graphic assembly comprising at least two constituent graphic elements.

4. The method of claim 3, wherein the locating of the graphic assembly comprises identifying a respective tree structure for each of multiple presentations of the graphic assembly corresponding to different respective arrangements of the constituent graphic elements.

5. The method of claim 3, wherein the identifying comprises sequentially adding graphic assemblies to each of the tree structures.

6. The method of claim 5, wherein the adding comprises evaluating all possible presentations of each added graphic assembly in each of a respective set of available node locations in the corresponding tree structures.

7. The method of claim 1, further comprising generating a set of paths through each of the candidate relative layouts.

8. The method of claim 7, wherein each of the paths corresponds to a list of ones of the graphic elements in respective partitions of one of the candidate relative layouts separated by divisions crossed by the path.

9. The method of claim 1, wherein the generating comprises generating relative position constraints preserving relative positions of the graphic elements in each of the candidate relative layouts.

10. The method of claim 9, further comprising determining a set of paths through each of the candidate relative layouts, and generating the relative position constraints from the sets of paths.

11. The method of claim 10, wherein the generating of the relative position constraints comprises generating a constraint for each traversal of the paths through a division of the corresponding candidate relative layouts.

12. The method of claim 9, wherein the generating of the relative position constraints comprises incorporating specified minimum distances between adjacent graphic elements in the relative position constraints.

13. The method of claim 1, wherein the generating comprises generating constraints promoting aspect ratios with widths greater than heights for textual graphic elements respectively associated with at least one other of the graphic elements.

14. The method of claim 1, wherein the generating comprises generating constraints specifying minimal dimensions for at least one of the graphic elements.

15. The method of claim 1, wherein the generating comprises generating constraints specifying dimensions of ones of the graphic elements designated as having fixed areas.

16. The method of claim 1, wherein the generating comprises generating constraints specifying aspect ratios of ones of the graphic elements designated as having variable areas.

17. The method of claim 1, wherein the generating comprises generating rules constraining relative areas of ones of the graphic elements designated as having variable areas.

18. The method of claim 1, wherein the generating comprises generating at least one constraint promoting maximization of areas of ones of the graphic elements designated as having variable areas.

19. The method of claim 1, wherein the generating comprises generating each set of constraints free of redundant constraints.

20. The method of claim 1, wherein the generating comprises generating constraints specifying alignment relationships among graphic elements designated as being related.

21. The method of claim 1, wherein the generating comprises generating textual constraints for ones of the graphic elements comprising text.

22. The method of claim 21, wherein the generating of the textual constraints comprises modeling height and width dimensions of the graphic elements comprising text.

23. The method of claim 1, wherein the determining comprises solving each set of constraints to obtain estimates of attributes and positions of the graphic elements in the determinate layouts.

24. The method of claim 23, wherein the determining additionally comprises:

correcting a set of attributes estimated for a given one of the graphic elements in a given candidate layout;

modifying the set of constraints corresponding to the given candidate layout; and

solving the modified set of constraints to obtain revised estimates of attributes and positions of the graphic elements in the determinate layout corresponding to the given candidate layout.

25. The method of claim 24, wherein the correcting, modifying, and solving of the modified set of constraints are performed only with respect to layouts designated as final layouts.

26. The method of claim 1, further comprising initiating the determining of the determinate layouts by transmitting a message from a client to a server.

27. A machine for albuming graphic elements, comprising one or more machine-readable media and digital electronic circuitry configured to perform computer process operations comprising:

identifying candidate relative layouts of graphic elements on a page, wherein each of the candidate relative layouts describes a respective set of layout relationships among the graphic elements;

generating for each of the candidate relative layouts a respective set of constraints describing the corresponding set of layout relationships among the graphic elements;

determining a respective determinate layout of the graphic elements on the page from each set of constraints; and

selecting one of the determinate layouts as a final layout of the graphic elements on the page.

28. A machine-readable medium storing machine-readable instructions causing a machine to perform operations comprising:

identifying candidate relative layouts of graphic elements on a page, wherein each of the candidate relative layouts describes a respective set of layout relationships among the graphic elements;

generating for each of the candidate relative layouts a respective set of constraints describing the corresponding set of layout relationships among the graphic elements;

determining a respective determinate layout of the graphic elements on the page from each set of constraints; and

selecting one of the determinate layouts as a final layout of the graphic elements on the page.

29. A computer system for albuming graphic elements, comprising:

computer hardware programmed to perform computer process operations comprising

identifying candidate relative layouts of graphic elements on a page,

wherein each of the candidate relative layouts describes a respective set of layout relationships among the graphic elements,

generating for each of the candidate relative layouts a respective set of constraints describing the corresponding set of layout relationships among the graphic elements,

determining a respective determinate layout of the graphic elements on the page from each set of constraints, and

selecting one of the determinate layouts as a final layout of the graphic elements on the page.