Method for image layout using energy minimization

• US 6,934,052 B2
• Filed: 09/05/2001
• Issued: 08/23/2005
• Est. Priority Date: 01/08/1998
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Venable, Dennis L.
• Primary Examiner(s): Lee, Thomas D.
• Application Number:
  US09/946,268
• Publication Number:
  US 20020051208A1
• Time in Patent Office: 1,448 Days
• Field of Search: 358/1.2, 358/1.12, 358/1.18, 358/450, 358/452, 358/540, 345/115, 345/118
• US Class Current: 358/1.18
• CPC Class Codes: H04N 1/387 Composing, repositioning or otherwise geometrically modifying originals

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₀−T_end, and k is a constant. Typically, initial value of T₀=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.

Claims

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

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

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

4. The method as in claim 1, wherein the predetermined penalty value has an initial value of 100.