Automatic photo album page layout

• US 20050071783A1
• Filed: 09/30/2003
• Published: 03/31/2005
• 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
• Granted Patent: US 7,743,322 B2
• Time in Patent Office: Days
• US Class Current: 715/851
• 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 method for locating objects by assembling a layout of objects within a space, comprising:

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

characterizing a bounding box for each node in the tree structure, wherein a bounding box for each node includes all objects in any subtree below the node; and

assigning regions within the space for each node in the tree structure in accordance with the bounding box associated with the node.

2. The method of claim 1, wherein each object has a fixed aspect ratio and a relative area proportion associated therewith, and said characterizing comprises:

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

3. The method of claim 2, wherein said characterizing further comprises 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, performed prior to said establishing.

4. The method of claim 2, wherein said establishing comprises:

determining right and left child relative area proportions and aspect ratios;

determining performance metrics for left and right children and comparing those performance metrics; and

determining node relative area proportion and aspect ratio based on compared performance metrics and left and right child relative area proportions and aspect ratios.

5. The method of claim 3, wherein said adjusting comprises:

determining right and left child relative area proportions and aspect ratios;

determining a factor for the node based on left and right child relative area proportions and aspect ratios; and

multiplying relative area proportions for one child and all its children by the factor.

6. The method of claim 1, further comprising:

scoring the tree structure subsequent to said assigning;

generating a different tree structure;

performing said characterizing and assigning for each node in the different tree structure;

scoring the different tree structure; and

passing one of the tree structure and different tree structure having a higher score.

7. 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.

8. A method for assigning fixed aspect ratio objects to a predefined space, comprising:

generating a binary tree structure comprising;

a plurality of leaves, wherein each leaf corresponds to one object; and

at least one node, wherein each node is associated with and represents all nodes and leaves branching therefrom;

defining a size appropriate bounding box for each node in the binary tree structure, wherein the bounding box for each node defines a boundary for all nodes and leaves branching therefrom; and

locating objects in the predefined space by manipulating at least one size appropriate bounding box to fit within the predefined space.

9. The method of claim 8, wherein each object has a relative area proportion associated therewith, and said defining comprises:

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

10. The method of claim 9, wherein said defining further comprises 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, performed prior to said establishing.

11. The method of claim 9, wherein said establishing comprises:

determining right and left child relative area proportions and aspect ratios;

determining performance metrics for left and right children and comparing those performance metrics; and

determining node relative area proportion and aspect ratio based on compared performance metrics and left and right child relative area proportions and aspect ratios.

12. The method of claim 10, wherein said adjusting comprises:

determining right and left child relative area proportions and aspect ratios;

determining a factor for the node based on left and right child relative area proportions and aspect ratios; and

multiplying relative area proportions for one child and all its children by the factor.

13. The method of claim 8, further comprising:

scoring the binary tree structure subsequent to said locating;

generating a different binary tree structure;

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

scoring the different binary tree structure; and

passing one of the binary tree structure and different binary tree structure having a higher score.

14. The method of claim 8, further comprising reassigning objects to leaves within the tree structure after said defining and locating, and repeating said defining and locating for the reassigned objects.

15. A method for locating images in a predefined space while maintaining aspect ratios associated with said images, the method comprising:

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;

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

manipulating bounding boxes to fit within the predefined space.

16. The method of claim 15, wherein each image has a fixed aspect ratio and a relative area proportion associated therewith, and said characterizing comprises:

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

17. The method of claim 16, wherein said characterizing further comprises 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, performed prior to said establishing.

18. The method of claim 16, wherein said establishing comprises:

determining right and left child relative area proportions and aspect ratios;

determining performance metrics for left and right children and comparing those performance metrics; and

determining node relative area proportion and aspect ratio based on compared performance metrics and left and right child relative area proportions and aspect ratios.

19. The method of claim 17, wherein said adjusting comprises:

determining right and left child relative area proportions and aspect ratios;

determining a factor for the node based on left and right child relative area proportions and aspect ratios; and

multiplying relative area proportions for one child and all its children by the factor.

20. The method of claim 15, further comprising:

scoring the binary tree structure subsequent to said manipulating;

generating a different binary tree structure;

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

scoring the different binary tree structure; and

passing one of the binary tree structure and different binary tree structure having a higher score.

21. The method of claim 15, further comprising reassigning images to leaves within the binary tree structure after said characterizing and manipulating, and repeating said characterizing and manipulating for the reassigned images.