Patent US6934052B2 successfully refreshed from Google Patents.
US6934052B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for image layout using energy minimization
Assignee: Xerox Corp
•
Filing: 2001-09-05
•
Granted: 2005-08-23
•
Expires: 2021-09-05
Abstract
Abstract A novel method is disclosed for laying out a plurality of rectangles onto a bounding box area, where bboxArea represents a total area of the bounding box and totalRectArea represents the sum of the areas of all the rectangles. The method comprises the steps of: first adjusting all rectangles to a specified aspect ratio and then computing a sum of areas of all rectangle intersections (overlap) occurring as a result of said arrangement. Next, the function blackArea=totalRectArea−overlap is used to approximate the black area and all non-overlapping spaces remaining between the arranged rectangles are computed by: WhiteSpace=bboxArea−blackArea. Then, for the current arrangement, an energy function E=whiteSpace+(overlapPenlalty * overlap) is calculated and for each energy function, a state probability function is calculated such that: Pr=exp(−(E new −E old )/kT), where E old is the energy computed for the previously accepted state, E new is the energy calculated for the current state, T is a control parameter from T 0 −T end , and k is a constant. Typically, initial value of T 0 =100 and T end =0.0 and the overlapPenalty has an initial value of 100. The value for the control parameter T is subsequently lowered by a fraction of its present value using the relationship: T N+1 =T N * 0.95. A random number between 0 . . 1 is then selected and if the random number is less than the value of Pr then the new state E new is accepted thus new states are always accepted where E new is less than E old . The rectangles are again randomly arranged on the bounding box area and the method repeats itself until either T end is reached or the value of Pr is within acceptable limits.
Inventors
- 👤 Dennis L. Venable
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 09:58
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/387
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
433 words
A method for laying out a plurality of rectangles within a bounding box area to form a layout, the layout having a current configuration, comprising: (a) adjusting all rectangles to a specified aspect ratio; (b) computing an overlap sum of all areas corresponding to a common area of overlapping rectangles occurring as a result of the arrangement; (c) approximating a black area value, the black area value being equal to a difference between a total area value and the computed overlap sum, the total area value being the sum of the areas of all the plurality of rectangles; (d) calculating a white space value representing non-overlapping space remaining between the arranged rectangles, the white space value being equal to a difference between a bounding box area value and the black area value, the bounding box area value being equal a total area of the bounding box; (e) calculating an energy function, for the current configuration, the energy function being equal to the sum of the calculated white space value and an overlap product, the overlap product being a product of the computed overlap sum and a predetermined penalty value; (f) calculating a state probability function, the state probability function being equal to an exponential function of a negative of an energy function power, the energy function power being equal to an energy difference divided by a predetermined control parameter, the energy difference being a difference between a current calculated energy function and a previously calculated energy function; (g) determining if the calculated state probability function is within predetermined limits; (h) accepting the current configuration when it is determined that the calculated state probability function is within the predetermined limits; (i) lowering a value for the predetermined control parameter by a predetermined fraction when it is determined that the calculated state probability function is outside the predetermined limits; (j) obtaining a random value between zero and 1 when it is determined that the calculated state probability function is outside the predetermined limits; (k) determining if the random value is less than the value of the calculated state probability function when it is determined that the calculated state probability function is outside the predetermined limits; (l) making the previously calculated energy function equal to the current calculated energy function if the random value is less than the value of the calculated state probability function; and (m) randomly arranging the rectangles within the bounding box area when it is determined that the calculated state probability function is outside the predetermined limits and the random value is less than the value of the calculated state probability function.
Claim 2
Independent Claim
433 words
A method for laying out a plurality of rectangles within a bounding box area to form a layout, the layout having a current configuration, comprising: (a) adjusting all rectangles to a specified aspect ratio; (b) computing an overlap sum of all areas corresponding to a common area of overlapping rectangles occurring as a result of the arrangement; (c) approximating a black area value, the black area value being equal to a difference between a total area value and the computed overlap sum, the total area value being the sum of the areas of all the plurality of rectangles; (d) calculating a white space value representing non-overlapping space remaining between the arranged rectangles, the white space value being equal to a difference between a bounding box area value and the black area value, the bounding box area value being equal a total area of the bounding box; (e) calculating an energy function, for the current configuration, the energy function being equal to the sum of the calculated white space value and an overlap product, the overlap product being a product of the computed overlap sum and a predetermined penalty value; (f) calculating a state probability function, the state probability function being equal to an exponential function of a negative of an energy function power, the energy function power being equal to an energy difference divided by a predetermined control parameter, the energy difference being a difference between a current calculated energy function and a previously calculated energy function; (g) determining if the calculated state probability function is within predetermined limits; (h) accepting the current configuration when it is determined that the calculated state probability function is within the predetermined limits; (i) lowering a value for the predetermined control parameter by a predetermined fraction when it is determined that the calculated state probability function is outside the predetermined limits; (j) obtaining a random value between zero and 1 when it is determined that the calculated state probability function is outside the predetermined limits; (k) determining if the random value is less than the value of the calculated state probability function when it is determined that the calculated state probability function is outside the predetermined limits; (l) making the previously calculated energy function equal to the current calculated energy function if the random value is less than the value of the calculated state probability function; and (m) randomly arranging the rectangles within the bounding box area when it is determined that the calculated state probability function is outside the predetermined limits and the random value is less than the value of the calculated state probability function.
Claim 3
Dependent Claim
37 words
The method as in claim 1 , wherein the predetermined penalty value represents a constraint added for rectangles about a center of the bounding box, thereby effectively driving the rectangles toward outside edges of the bounding box.
Claim 4
Dependent Claim
38 words
The method as in claim 1 , wherein the predetermined penalty value represents a constraint added for rectangles near outside edges of the bounding box, thereby effectively driving the rectangles toward a center point of the bounding box.
Claim 5
Dependent Claim
18 words
The method as in claim 1 , wherein the predetermined penalty value has an initial value of 100.
References Cited (Backward Citations)
US5202670A
Cited
JPS63274267A
Cited
US4928252A
Cited
US5224181A
Cited
US5289570A
Cited
US5381523A
Cited
EP0577924A1
Cited
US5485568A
Cited
US5438512A
Cited
EP0784294A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-08-22 | 2009-02-21 | 2009-08-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-08-22 | 2013-02-21 | 2013-08-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-08-22 | 2017-02-21 | 2017-08-23 | $7700.00 | Window Closed / Lapsed |