Automatic photo album page layout

• US 7,743,322 B2
• Filed: 09/30/2003
• Issued: 06/22/2010
• Est. Priority Date: 09/30/2003
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Atkins, C. Brian
• Primary Examiner(s): HAILU, TADESSE
• Application Number:
  US10/675,724
• Publication Number:
  US 20050071783A1
• Time in Patent Office: 2,457 Days
• Field of Search: 715/792, 715853-855, 715/517, 715/838, 715/243, 715/253, 715/788, 715/790, 345/418, 345/619, 345/622, 345/635, 345/440
• US Class Current: 715/243
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method for locating objects, such as images having fixed aspect ratios, within a predefined space, such as a printed page, is provided. The method comprises generating a binary tree structure comprising at least one node and a plurality of leaves, each leaf corresponding to an image and being associated with one node. The method further comprises characterizing a bounding box for each node in the binary tree structure, the bounding box establishing a boundary for all leaves associated with the node. The method also comprises manipulating bounding boxes to fit within the predefined space. The method may be selectively repeated to reposition images within the binary tree structure or to reform the binary tree structure and characterize and manipulate using the reformed binary tree structure. The end result is at least one potential layout having all images located within the predefined space.

Claims

1. A computer-implemented method of producing a layout of objects on a page, comprising:

generating different tree structures each having at least one node and at least one leaf, wherein each node corresponds to a respective partition of the page and each leaf defines a relative location of a respective one of the objects on the page, wherein each object has a respective fixed aspect ratio and is associated with a respective relative area proportion that has a value such that a ratio of the respective relative area proportion to a respective amount of area on the page that is occupied by the object in the layout is equal to an identical constant value for all the objects;

for each of the tree structures, characterizing a respective bounding box for each respective node in the tree structure based on the respective aspect ratios and the respective relative area proportions associated with all of the objects in all subtrees below the respective node, wherein each bounding box includes all of the objects in all subtrees below the respective node;

for each of the tree structures, assigning regions within the page for each node in the tree structure in accordance with the respective bounding box associated with the node;

for each of the tree structures, determining a respective score that comprises a measure of available space on the page that is unoccupied by the objects arranged on the page in accordance with partitions of the page defined by the tree structure;

selecting one of the tree structures based on the determined scores; and

producing a layout of the objects on the page based on the selected tree structure.

2. The method of claim 1, wherein the characterizing comprises:

for each of the tree structures, establishing for each node of the tree structure a respective relative area proportion and a respective aspect ratio as a function of the relative area proportions and the aspect ratios of all children of the node, wherein for each node a respective ratio of the respective relative area proportion to a respective amount of area on the page that is occupied by the node in the layout is equal to an identical constant value for all the nodes.

3. The method of claim 2, wherein said establishing comprises for each of the nodes:

determining a respective aspect ratio and a respective relative area proportion for each child of the node; and

determining the respective relative area proportion and the respective aspect ratio of the node based on the respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node.

4. The method of claim 1, further comprising iteratively performing the generating, the characterizing, the assigning, the determining, and the selecting for each of the different tree structures in sequence.

5. The method of claim 1, further comprising reassigning objects to leaves within the tree structure after said characterizing and assigning, and repeating said characterizing and assigning for the reassigned objects.

6. A computer-implemented method of producing a layout of objects on a page, comprising:

generating a tree structure having at least one node and at least one leaf, where each leaf corresponds to one of the objects;

associating a respective bounding box with each node in the tree structure, wherein each bounding box includes all objects in any subtree below the associated node, each object has a respective fixed aspect ratio and is associated with a respective relative area proportion that has a value such that a ratio of the respective relative area proportion to a respective amount of area on the page that is occupied by the object in the layout is equal to an identical constant value for all the objects, and the associating comprises

establishing a respective relative area proportion and a respective aspect ratio for each node as a function of the relative area proportions and the aspect ratios of all children of the node, and

prior to the establishing, adjusting relative area proportions of at least one child of each node and all children thereof so that predetermined dimensions of the children are equal;

assigning regions of the page for each node in the tree structure in accordance with the bounding box associated with the node; and

producing a layout of the objects on the page in accordance with the assignment of regions to the nodes.

7. The method of claim 6, wherein the adjusting comprises for each of the nodes:

determining a respective aspect ratio and a respective relative area proportion for each child of the node;

determining a factor for the node based on the respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node; and

multiplying the respective relative area proportions of a selected child of the node and all children of the selected child by the factor.

8. A method of producing a layout of fixed aspect ratio objects on a page, comprising:

generating a binary tree structure comprising

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the objects, and

a plurality of nodes including a root node, wherein each of the nodes corresponds to a respective partition of the page;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a relative size of a respective bounding box containing all bounding boxes respectively determined for all child nodes branching from the node, wherein the determining comprises

for each given one of the nodes corresponding to a respective horizontal partition of the page, determining relative sizes of the respective bounding boxes of all immediate children of the given node such that horizontal dimensions of the bounding boxes of all the immediate children of the given node are equal, and

for each particular one of the nodes corresponding to a respective vertical partition of the page, determining relative sizes of the respective bounding boxes of all immediate children of the given node such that vertical dimensions of the bounding boxes of all the immediate children of the given node are equal; and

producing a layout of the objects on the page based on the bounding box determined for the root node.

9. A method of producing a layout of fixed aspect ratio objects on a page, comprising:

generating a binary tree structure comprising

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the objects, and

a plurality of nodes including a root node, wherein each of the nodes corresponds to a respective partition of the page;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all nodes and leaves branching from the node, wherein each object is associated with a respective relative area proportion that has a value such that a ratio of the respective relative area proportion to a respective amount of area on the page that is occupied by the object in the layout is equal to an identical constant value for all the objects, and the determining comprises, for each of the nodes in the binary tree structure, determining a respective relative area proportion and a respective aspect ratio of the respective bounding box as a function of the respective aspect ratios and the respective relative area proportions of the objects associated with children of the node; and

producing a layout of the objects on the page based on the bounding box determined for the root node.

10. The method of claim 9, wherein the determining of the respective relative area proportion of each node further comprises adjusting the relative area proportion of each of the respective bounding boxes determined for at least one child of each of the nodes and all children thereof so that corresponding dimensions of the bounding boxes respectively determined for the children are equal.

11. The method of claim 10, wherein the adjusting comprises for each of the nodes:

determining a respective aspect ratio and a respective relative area proportion for each child of the node;

determining a factor for the node based on respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node; and

multiplying the respective relative area proportions of a selected child of the node and all the children of the selected child by the factor.

12. The method of claim 9, wherein said determining of the respective relative area proportion of each node comprises:

determining a respective aspect ratio and a respective relative area proportion for each child of the node; and

determining the respective relative area proportion and the respective aspect ratio of the node based on the respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node.

13. A method of producing a layout of fixed aspect ratio objects on a page, comprising:

generating a binary tree structure comprising

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the objects, and

a plurality of nodes including a root node, wherein each of the nodes corresponds to a respective partition of the page;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all nodes and leaves branching from the node;

producing a layout of the objects on the page based on the bounding box determined for the root node;

scoring the binary tree structure subsequent to the producing;

generating a different binary tree structure;

performing the determining and the producing for each node in the different binary tree structure;

scoring the different binary tree structure; and

selecting the one of the binary tree structure and the different binary tree structure that is scored higher.

14. A method of producing a layout of fixed aspect ratio objects on a page, comprising:

generating a binary tree structure comprising

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the objects, and

a plurality of nodes including a root node, wherein each of the nodes corresponds to a respective partition of the page;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all nodes and leaves branching from the node;

producing a layout of the objects on the page based on the bounding box determined for the root node;

reassigning objects to leaves within the tree structure after the determining and the producing; and

repeating the determining and the producing for the reassigned objects.

15. A method of producing a layout of images in a predefined space on a page while maintaining aspect ratios associated with said images, the method comprising:

generating a binary tree structure comprising

a plurality of nodes includes a root node, wherein each of the nodes corresponds to a respective partition of the predefined space on the page, and

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the images and is associated with a respective one of the nodes;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a relative size of a respective bounding box containing all bounding boxes respectively determined for all child nodes branching from the node, wherein the determining comprises

for each given one of the nodes corresponding to a respective horizontal partition of the page, determining relative sizes of the respective bounding boxes of all immediate children of the given node such that horizontal dimensions of the bounding boxes of all the immediate children of the given node are equal, and

for each particular one of the nodes corresponding to a respective vertical partition of the page, determining relative sizes of the respective bounding boxes of all immediate children of the given node such that vertical dimensions of the bounding boxes of all the immediate children of the given node are equal; and

producing a layout of the images in the predefined space on the page based on the bounding box determined for the root node.

16. A method of producing a layout of images in a predefined space on a pace while maintaining aspect ratios associated with said images, the method comprising:

generating a binary tree structure comprising

a plurality of nodes includes a root node, wherein each of the nodes corresponds to a respective partition of the predefined space on the page, and

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the images and is associated with a respective one of the nodes;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all leaves associated with the node, wherein each image has a fixed aspect ratio and is associated with a respective relative area proportion that has a value such that a ratio of the respective relative area proportion to a respective amount of area on the page that is occupied by the image in the layout is equal to an identical constant value for all the images, and the determining, for each of the nodes in the binary tree structure, ascertaining the respective area of the respective bounding box as a function of the respective aspect ratios and the respective relative area proportions of the images associated with children of the node; and

producing a layout of the images in the predefined space on the pace based on the bounding box determined for the root node.

17. The method of claim 16, wherein the determining of the respective relative area proportion of each node further comprises adjusting the relative area proportion of each of the respective bounding boxes determined for at least one child of each of the nodes and all children thereof so that corresponding dimensions of the bounding boxes respectively determined for the children are equal.

18. The method of claim 17, wherein the adjusting comprises for each of the nodes:

determining a respective aspect ratio and a respective relative area proportion for each child of the node;

determining a factor for the node based on the respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node; and

multiplying the respective relative area proportions of a selected child of the node and all the children of the selected child by the factor.

19. The method of claim 16, wherein the ascertaining comprises for each of the nodes:

determining a respective aspect ratio and a respective relative area proportion for each child of the node; and

determining the respective relative area proportion and the respective aspect ratio of the node based on the respective relative area proportions and the respective aspect ratios of the children of the node and an orientation of the page partition corresponding to the node.

20. A method of producing a layout of images in a predefined space on a page while maintaining aspect ratios associated with said images, the method comprising:

generating a binary tree structure comprising

a plurality of nodes includes a root node, wherein each of the nodes corresponds to a respective partition of the redefined space on the page, and

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the images and is associated with a respective one of the nodes;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all leaves associated with the node;

producing a layout of the images in the predefined space on the page based on the bounding box determined for the root node;

generating a different binary tree structure;

performing said determining for each node in the different binary tree structure; and

assigning to each of the binary tree structures a respective score that comprises a measure of available space on the page that is unoccupied by the images arranged on the page in accordance with partitions of the page defined by the tree structure; and

selecting one of the tree structures based on the respective scores assigned to the binary tree structure.

21. A method of producing a layout of images in a predefined space on a page while maintaining aspect ratios associated with said images, the method comprising:

generating a binary tree structure comprising

a plurality of nodes includes a root node, wherein each of the nodes corresponds to a respective partition of the predefined space on the page, and

a plurality of leaves, wherein each of the leaves corresponds to a respective one of the images and is associated with a respective one of the nodes;

for each of the nodes in the binary tree structure, determining a respective aspect ratio and a respective area of a respective bounding box containing all bounding boxes respectively determined for all leaves associated with the node; and

producing a layout of the images in the predefined space on the page based on the bounding box determined for the root node;

reassigning images to leaves within the binary tree structure after the determining; and

producing, and repeating the determining and the producing for the reassigned images.