Single pass automatic photo album page layout

• US 8,065,627 B2
• Filed: 09/30/2003
• Issued: 11/22/2011
• 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): Augustine; Nicholas
• Application Number:
  US10/675,823
• Publication Number:
  US 20050071781A1
• Time in Patent Office: 2,975 Days
• Field of Search: 715/854, 715/788, 715/789, 715/790, 715/792, 715/798, 715/799, 715/800, 715/853
• US Class Current: 715/788
• 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:

initiating a first current binary tree comprising a leaf node;

associating a first object selected from the set with the leaf node;

establishing candidate binary trees, wherein each of the candidate binary trees comprises the current binary tree and a respective leaf node associated with another object selected from the set, and locations of the leaf nodes within each of the candidate binary trees correspond to relative positions of the associated objects within the area;

computing a respective score for each of the candidate binary trees

selecting one of the candidate binary trees as the current binary tree based on the computed scores;

repeating the establishing, the computing, and the selecting until the current binary tree includes all the objects in the set; and

after the repeating, arranging the objects within the area in accordance with the locations of the leaf nodes within the current binary tree.

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

at least one interior node; and

at least one leaf node emanating from the interior node;

wherein each subtree of the current binary tree comprises a respective position within the current binary tree and all interior nodes and leaf nodes emanating from the respective position; and

wherein each subtree of each of the candidate binary trees comprises a respective location within the candidate binary tree and all interior nodes and leaf nodes emanating from the respective location.

3. The method of claim 2, wherein the establishing comprises:

removing a subtree of the current binary tree associated with a selected position within the current binary tree;

inserting a new interior node into the current binary tree at the selected position;

associating either a horizontal or a vertical partition of the area with the new interior node;

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

associating the new leaf node with the other object selected from the set; and

inserting the previously removed subtree back into the binary tree at the new interior node.

4. The method of claim 3, wherein the selected position is selected from the group consisting of:

a leaf node in the current binary tree; and

an interior node in the current binary tree.

5. The method of claim 2, further comprising normalizing each of the candidate binary trees, wherein the normalizing comprises:

for each of the interior nodes in the candidate binary tree, characterizing a respective bounding box for the objects included in the subtree rooted in the interior node; and

for each of the objects, allocating a respective region of the area in accordance with the respective bounding box.

6. The method of claim 1, wherein the computing comprises determining respective fractions of the areas occupied by the objects in each of the candidate binary trees, and the selecting comprises selecting as the current binary tree the candidate binary tree having a greatest one of the fractions of the area occupied by the objects in the candidate binary tree.

7. The method of claim 1, wherein the computing comprises assessing minimum and maximum object size values for all the objects in the area, and the selecting comprises selecting as the current binary tree the candidate binary tree having a greatest respective 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 selected from the set with the tree structure to form a current candidate tree;

modifying the current candidate tree to form alternate candidate trees by associating a subsequent object selected from the set with different respective locations on the current candidate tree, wherein the respective locations correspond to relative positions of the associated objects within the area;

computing scores for each of the alternate candidate trees;

selecting one of the alternate candidate trees as the current candidate tree based on the computed scores;

repeating the modifying, the computing, and the selecting until all the objects in the set are associated with the current candidate tree; and

after the repeating, arranging all the objects in the set within the area in accordance with the locations in the current candidate tree associated with the objects.

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

at least one interior node; and

at least one leaf node emanating from the interior node;

wherein each subtree of the current candidate tree comprises a respective location within the current candidate tree and all interior nodes and leaf nodes emanating from the respective location;

wherein each subtree of each of the alternate candidate trees comprises a respective spot within the alternate candidate tree and all interior nodes and leaf nodes emanating from the spot.

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

removing a subtree of the current candidate tree associated with one selected location within the current candidate tree;

inserting a new interior node into the current candidate tree at the selected location;

associating either a horizontal or a vertical partition of the area with the new interior node;

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

associating the new leaf node with the subsequent object selected from the set; and

inserting the previously removed subtree back into the current candidate tree at the new interior node.

11. The method of claim 10, wherein the selected location is selected from the group consisting of:

a leaf node in the current candidate tree; and

an interior node in the current candidate tree.

12. The method of claim 9, further comprising normalizing each of the alternate candidate trees, wherein for each of the alternate candidate trees the normalizing comprises:

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

for each of the objects, allocating a respective region of the area in accordance with the respective bounding box.

13. The method of claim 8, wherein the computing comprises determining respective fractions of the area occupied by the objects in each of the alternate candidate trees, and the selecting comprises selecting as the current candidate tree the alternate candidate tree having a greatest one of the fractions of the area occupied by the objects in the alternate candidate tree.

14. The method of claim 8, wherein the computing comprises assessing minimum and maximum object size values for all objects in the area for each alternate candidate tree, and the selecting comprises selecting as the current candidate tree the alternate candidate tree having a greatest respective 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 current candidate tree having at least one interior node, at least one leaf node connected to the interior node, and at least one object selected from the set associated with the leaf node;

modifying the current candidate tree to form alternate candidate trees by associating a subsequent object selected from the set with a different respective location on the current candidate tree, wherein the respective locations correspond to relative positions of the associated objects within the area;

computing scores for each of the alternate candidate trees;

selecting one of the alternate candidate trees as the current candidate tree based on the computed scores;

repeating the modifying, the computing, and the selecting until all the objects in the set are associated with the current candidate tree; and

after the repeating, arranging all the objects in the set within the area in accordance with the locations in the current candidate tree associated with the objects.

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

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

removing a subtree of the current candidate tree associated with one selected location within the current candidate tree;

inserting a new interior node into the current candidate tree at the selected location;

associating either a horizontal or a vertical partition of the area with the new interior node;

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

associating the new leaf node with the subsequent object selected from the set; and

inserting the previously removed subtree back into the candidate tree at the new interior node.

18. The method of claim 17, wherein the selected location is selected from the group consisting of:

a leaf node in the current candidate tree; and

an interior node in current the candidate tree.

19. The method of claim 16, further comprising normalizing each of the alternate candidate trees, wherein for each of the alternate candidate trees the normalizing comprises:

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

for each of the objects, allocating a respective region of the area in accordance with the respective bounding box.

20. The method of claim 15, wherein the computing comprises determining respective fractions of the area occupied by the objects in each of the alternate candidate trees, and the selecting comprises selecting as the current candidate tree the alternate candidate tree having a greatest one of the fractions of the area occupied by the objects in the alternate candidate tree.

21. The method of claim 15, wherein the computing comprises assessing minimum and maximum object size values for all objects in the area for each of the alternate candidate trees, and the selecting comprises selecting as the current candidate tree the alternate candidate tree having a greatest respective ratio of minimum object size value divided by maximum object size value.