Patent US1140586A successfully refreshed from Google Patents.
Patent US8065627B2 successfully refreshed from Google Patents.
US8065627B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Single pass automatic photo album page layout
Assignee: Hewlett Packard Development Co LP
•
Filing: 2003-09-30
•
Granted: 2011-11-22
•
Expires: 2023-09-30
Abstract
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.
Inventors
- 👤 C. Brian Atkins
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 09:58
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/60; G06F; G06F30/00; G06F30/10; G06F30/18
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
159 words
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.
Claim 2
Independent Claim
159 words
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.
Claim 3
Dependent Claim
89 words
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.
Claim 4
Dependent Claim
102 words
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.
Claim 5
Dependent Claim
34 words
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.
Claim 6
Dependent Claim
67 words
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.
Claim 7
Dependent Claim
60 words
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.
Claim 8
Dependent Claim
56 words
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.
Claim 9
Independent Claim
153 words
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.
Claim 10
Independent Claim
153 words
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.
Claim 11
Dependent Claim
96 words
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.
Claim 12
Dependent Claim
103 words
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.
Claim 13
Dependent Claim
34 words
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.
Claim 14
Dependent Claim
74 words
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.
Claim 15
Dependent Claim
60 words
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.
Claim 16
Dependent Claim
58 words
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.
Claim 17
Independent Claim
167 words
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.
Claim 18
Independent Claim
167 words
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.
Claim 19
Dependent Claim
66 words
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.
Claim 20
Dependent Claim
104 words
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.
Claim 21
Dependent Claim
34 words
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.
Claim 22
Dependent Claim
74 words
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.
Claim 23
Dependent Claim
60 words
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.
Claim 24
Dependent Claim
60 words
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.
References Cited (Backward Citations)
JPH01191270A
Cited
US5136686A
Cited
US5499366A
Cited
US5555362A
Cited
US5712995A
Cited
JPH09185728A
Cited
US5729254A
Cited
US5760786A
Cited
US5956738A
Cited
US5920315A
Cited
WO1998010356A1
Cited
JPH10293838A
Cited
US6727909B1
Cited
US6008809A
Cited
US6301586B1
Cited
US6448956B1
Cited
US20020051208A1
Cited
US6380954B1
Cited
US6563602B1
Cited
US6415306B2
Cited
US6636650B1
Cited
US6636648B2
Cited
US7124360B1
Cited
US7093263B1
Cited
WO2001039019A2
Cited
US7149968B1
Cited
US6771801B1
Cited
US6701306B1
Cited
US20020070982A1
Cited
EP1186992A2
Cited
US20040128284A1
Cited
WO2002037939A2
Cited
US20040054668A1
Cited
JP2002142092A
Cited
US20020122067A1
Cited
JP2002288669A
Cited
US20020145603A1
Cited
US6771292B2
Cited
WO2002084582A2
Cited
US7013432B2
Cited
US20030001879A1
Cited
GB2378340A
Cited
JP2003101749A
Cited
JP2003274139A
Cited
US7148990B2
Cited
US7096445B1
Cited
EP1503336A2
Cited
US20050071783A1
Cited
US20050071781A1
Cited
US20050240865A1
Cited
US20060200758A1
Cited
US20060279566A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2014-11-21 | 2015-05-23 | 2015-11-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2018-11-21 | 2019-05-23 | 2019-11-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2022-11-21 | 2023-05-23 | 2023-11-22 | $7700.00 | Window Closed / Lapsed |