Single pass automatic photo album page layout

• US 20050071781A1
• 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 8,065,627 B2
• Time in Patent Office: Days
• US Class Current: 715/838
• 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 quickly and efficiently 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 containing a first image. The system generates a second tree, where the second tree modifies the first tree by inserting a second image at a location or position on the first tree. This iterative process of inserting images one at a time continues until the system generates a final tree including all images. In each iteration, the position in the binary tree where the system inserts each subsequent image can be either a leaf or a node. The system generates a series of candidate trees, one for each subsequent image inserted into each and every location in the preceding tree, and the candidate tree having a highest score indicates the selected location for the subsequent image and the new baseline, preferred binary tree.

Claims

1. A method for arranging a set of objects within an area, comprising:

(a) initiating a binary tree and associating a first object with the binary tree;

(b) selecting a subsequent object not included in the binary tree;

(c) establishing at least one candidate tree, wherein each candidate tree comprises objects from the binary tree and the subsequent object;

(d) computing a score for each candidate tree and selecting one candidate tree having a highest score associated with placement of the subsequent object;

(e) repeating (b), (c), and (d) until the candidate tree includes the set of objects; and

(f) arranging the objects within the area in accordance with the candidate tree.

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

at least one node; and

at least one leaf emanating from one node;

wherein a subtree of the binary tree comprises a position within the binary tree and all nodes and leaves emanating from the position; and

wherein a subtree of the candidate tree comprises a location within the candidate tree and all nodes and leaves emanating from the location.

3. The method of claim 2, wherein establishing each candidate tree is performed by modifying the binary tree, where the step of modifying comprises:

a. removing one subtree of the binary tree associated with one desired position;

b. inserting a new node into the binary tree at the desired position;

c. associating either a horizontal or a vertical cut with the new node;

d. inserting a new leaf into the binary tree emanating from the new node;

e. associating the new leaf with the subsequent object; and

f. inserting the subtree into the binary tree, said subtree also emanating from the new node.

4. The method of claim 3, wherein the desired position may be one from a group comprising:

a leaf in the binary tree; and

a node in the binary tree.

5. The method of claim 2, further comprising normalizing the candidate tree after establishing the candidate tree, where normalizing comprises:

a. for each node in the candidate tree, characterizing a bounding box of the objects included in the subtree rooted in the node; and

b. allocating a region of the area in accordance with the bounding box for each object.

6. The method of claim 1, wherein computing the score for each candidate tree comprises determining a fraction of the area occupied by the objects in the candidate tree, and wherein selecting one candidate tree comprises determining the candidate tree having a greatest fraction of the area occupied by the objects in each candidate tree.

7. The method of claim 1, wherein computing the score for each candidate tree comprises assessing minimum and maximum values for object sizes for all objects in the area, and wherein selecting one candidate tree comprises determining the candidate tree having the greatest ratio of minimum area object size value divided by maximum area object size value.

8. A method for arranging a set of objects within an area, comprising:

establishing a tree structure;

associating a first object with the tree structure to form a candidate tree;

modifying the candidate tree to form at least one alternate candidate tree by associating a subsequent object with at least one available location on the candidate tree;

computing scores for each alternate candidate tree with the subsequent object in each available location;

selecting the alternate candidate tree having a best score;

designating the selected alternate candidate tree to be the candidate tree;

repeating said modifying, computing, selecting and designating for all remaining subsequent objects; and

arranging the set of objects within the area in accordance with the candidate tree.

9. The method of claim 8, wherein the tree structure, candidate tree, each alternate candidate tree, and the selected alternate candidate tree each comprise:

at least one node; and

at least one leaf emanating from one node;

wherein a subtree of the candidate tree comprises a location within the candidate tree and all nodes and leaves emanating from the location;

wherein a subtree of each alternate candidate tree comprises a spot within the alternate candidate tree and all nodes and leaves emanating from the spot.

10. The method of claim 9, wherein modifying the candidate tree comprises:

a. removing one subtree of the candidate tree associated with one desired location;

b. inserting a new node into the candidate tree at the desired location;

c. associating either a horizontal or a vertical cut with the new node;

d. inserting a new leaf into the candidate tree emanating from the new node;

e. associating the new leaf with the subsequent object; and

f. inserting the subtree into the candidate tree, said subtree also emanating from the new node.

11. The method of claim 10, wherein the desired location may be one from a group comprising:

a leaf in the candidate tree; and

a node in the candidate tree.

12. The method of claim 9, further comprising normalizing the alternate candidate tree after modifying the candidate tree, where normalizing comprises:

a. for each node in the alternate candidate tree, characterizing a bounding box of the objects included in the subtree rooted in the node; and

b. allocating a region of the area in accordance with the bounding box for each object.

13. The method of claim 8, wherein computing scores comprises determining a fraction of the area occupied by the objects in the alternate candidate tree, and wherein selecting the alternate candidate tree having a best score comprises determining the alternate candidate tree having a greatest fraction of the area occupied by the objects in each alternate candidate tree.

14. The method of claim 8, wherein computing scores comprises assessing minimum and maximum values for object sizes for all objects in the area for each alternate candidate tree, and wherein selecting the alternate candidate tree having a best score comprises determining the alternate candidate tree having a greatest ratio of minimum object size value divided by maximum object size value.

15. A method for arranging a set of objects within an area, comprising:

establishing a candidate tree having at least one node, and at least one leaf connected to one node, and at least one object associated with the candidate tree;

modifying the candidate tree to form at least one alternate candidate tree by associating a subsequent object with at least one available location on the candidate tree;

computing scores for each alternate candidate tree with the subsequent object in each available location;

selecting the alternate candidate tree having a best score, and designating the selected alternate candidate tree to be the candidate tree;

repeating said modifying, computing, and selecting for all remaining subsequent objects; and

arranging the set of objects within the area in accordance with the candidate tree.

16. The method of claim 15, wherein a subtree of the candidate tree comprises a location within the candidate tree and all nodes and leaves emanating from the location, and wherein a subtree of each alternate candidate tree comprises a spot within the alternate candidate tree and all nodes and leaves emanating from the spot.

17. The method of claim 16, wherein modifying the candidate tree comprises:

a. removing one subtree of the candidate tree associated with one desired location;

b. inserting a new node into the candidate tree at the desired location;

c. associating either a horizontal or a vertical cut with the new node;

d. inserting a new leaf into the candidate tree emanating from the new node;

e. associating the new leaf with the subsequent object; and

f. inserting the subtree into the candidate tree, said subtree also emanating from the new node.

18. The method of claim 17, wherein the desired location may be one from a group comprising:

a leaf in the candidate tree; and

a node in the candidate tree.

19. The method of claim 16, further comprising normalizing the alternate candidate tree after modifying the candidate tree, where normalizing comprises:

a. for each node in the alternate candidate tree, characterizing a bounding box of the objects included in the subtree rooted in the node; and

b. allocating a region of the area in accordance with the bounding box for each object.

20. The method of claim 15, wherein computing scores comprises determining a fraction of the area occupied by the objects in the alternate candidate tree, and wherein selecting the alternate candidate tree having a best score comprises determining the alternate candidate tree having a greatest fraction of the area occupied by the objects in each alternate candidate tree.

21. The method to claim 15, wherein computing scores comprises assessing minimum and maximum values for object sizes for all objects in the area for each alternate candidate tree, and wherein selecting the alternate candidate tree having a best score comprises determining the alternate candidate tree having a greatest ratio of minimum object size value divided by maximum object size value.