Constraint-optimization system and method for document component layout generation

• US 7,243,303 B2
• Filed: 07/23/2002
• Issued: 07/10/2007
• Est. Priority Date: 07/23/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Harrington, Steven J, Purvis, Lisa S
• Primary Examiner(s): BASHORE, WILLIAM L
• Application Number:
  US10/202,046
• Publication Number:
  US 20040019850A1
• Time in Patent Office: 1,813 Days
• Field of Search: 715/525, 715/517, 715518-521, 707/100, 707/517, 345/620, 345/670, 395/767
• US Class Current: 715/253
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood

Abstract

What is disclosed is a system and method for specifying a custom document as a multi-criteria constraint optimization problem, and a method to automatically create the specified document using existing constraint optimization solving algorithms. The present method specifies the document, its content components, its layout requirements, and its desired aesthetic criteria are expressed as elements of a constraint optimization problem which when solved, results in an automated document layout for the set of content components that satisfies not only certain primitive content and layout constraints, but which also advantageously fulfills desired design properties and which provides a way to ensure that the generated document is well designed. The method for automatic document layout comprises the steps of determining a set of variables that can be adjusted to achieve a satisfactory layout; expressing said satisfactory layout as a set of constraints on said determined set of variables wherein at least one of said set of constraints is expressed as being optimizable; and solving said constraints to find a layout which solves for the variables over the constraints. The system for automatic document layout on multi-function office equipment comprises means for document layout constraint acquisition; means for document layout variable specification which specifies a set of variables that can be adjusted to achieve a satisfactory layout; means for relationship-constraint to optimization-constraint conversion which expresses said satisfactory layout as a set of constraints on said set of variables wherein at least one of said set of constraints is expressed as being optimizable; and means for constraint optimization for solving said constraints to find a layout which solves for the variables over said constraints.

Claims

1. A method for automatic document component layout comprising:

(a) determining a set of variables that can be adjusted to achieve a satisfactory layout;

(b) expressing the satisfactory layout as a set of constraints, the set of constraints including required constraints and desired constraints, on the determined set of variables wherein at least one of the desired constraints is expressed as being optimizable, each required constraint specifying a relationship between a variable and a document layout value, each desired constraint being an objective function;

(c) inputting a plurality of sets of document layout values, each set of document layout values representing a specific document layout;

(d) solving the required constraints for each document layout;

(e) solving the desired constraints for each document layout to establish a score for each document layout; and

(f) selecting the document layout having each solved required constraint relationship of the document layout satisfied and a highest score to be the satisfactory layout.

2. The method for automatic document component layout as in claim 1, wherein each desired constraint is weighted.

3. A method for automatic document component layout comprising:

(a) determining a set of variables that can be adjusted to achieve a satisfactory layout;

(b) expressing the satisfactory layout as a set of constraints, the set of constraints including required constraints and desired constraints, on the determined set of variables wherein at least one of the desired constraints is expressed as being optimizable, each required constraint specifying a relationship between a variable and a document layout value, each desired constraint being an objective function;

(c) inputting a plurality of sets of document layout values, each set of document layout values representing a specific document layout;

(d) solving the required constraints for each document layout;

(e) solving the desired constraints for each document layout to establish a score for each document layout; and

(f) selecting the document layout having each solved required constraint relationship of the document layout satisfied and a lowest score to be the satisfactory layout.

4. The method for automatic document component layout as in claim 3, wherein each desired constraint is weighted.

5. A method for automatic document component layout comprising:

(a) creating a population of document layout members, each document layout being represented by a plurality of document layout values, each document layout value corresponding to a document layout variable;

(b) establishing a set of constraints, the set of constraints including required constraints and desired constraints, each required constraint specifying a relationship between a variable and a document layout value, each desired constraint being an objective function;

(c) solving the required constraints for each document layout member;

(d) solving the desired constraints for each document layout member to establish a score for each document layout member;

(e) selecting the document layout members having each solved required constraint relationship of the document layout satisfied and a score greater that a predetermined score;

(f) creating a new population of children document layout members by performing crossover/mutation operations upon the selected document layout members;

(g) solving the required constraints for each child document layout member;

(h) solving the desired constraints for each child document layout member to establish a score for each child document layout member;

(i) selecting the children document layout members having each solved required constraint relationship of the document layout satisfied and a score greater that a predetermined score; and

(j) re-iterating the creating, solving, and selecting processes until a termination condition is realized.

6. The method for automatic document component layout as in claim 5, wherein the termination condition is defined as a failure to improve the layout after a predetermined number of iterations.

7. The method for automatic document component layout as in claim 5, wherein the termination condition is defined as a predetermined number of iterations.

8. The method for automatic document component layout as in claim 5, wherein the termination condition is defined as when the selecting process fails to select a document layout member from the population that has each solved required constraint relationship of the document layout satisfied and a score greater that a predetermined score.