Constraint-optimization system and method for document component layout generation

• US 20040019850A1
• Filed: 07/23/2002
• Published: 01/29/2004
• 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.
• Granted Patent: US 7,243,303 B2
• Time in Patent Office: Days
• US Class Current: 715/517
• 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 the steps of:

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

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

c. solving said constraints to find at least one layout which solves for the variables over the constraints.

2. The method for automatic document component layout as in claim 1 wherein said optimization is expressed as either a minimization or a maximization.

3. A method for automatic document component layout as in claim 2 wherein said constraint optimization expression incorporates a termination mechanism.

4. A method for automatic document component layout as in claim 3 wherein said optimization comprises a genetic algorithm.

5. A method for automatic document component layout as in claim 4 wherein said termination mechanism is defined as a failure of said genetic algorithm to improve the layout after a predetermined number of generations.

6. A method for automatic document component layout as in claim 5 wherein said variables to be adjusted comprise genes used by said genetic algorithm.

7. A method for automatic document component layout as in claim 6 wherein each genome in said genetic algorithm population corresponds to a candidate layout.

8. A method for automatic document component layout as in claim 7 wherein said constraints describing a relationship wherein the best possible value corresponds to the satisfaction of this relationship.

9. A method for automatic document component layout as in claim 8 wherein all constraints are combined into a single fitness function.

10. A method for automatic document component layout as in claim 9 wherein said constraints derived from said relationship are weighted such that any variation from said best possible value yields an unfit result.

11. A method for automatic document component layout as in claim 10 wherein said single fitness function is employed by the genetic algorithm in a refinement of said population of genomes.

12. A method for automatic document component layout as in claim 11 wherein said termination mechanism includes obtaining a fitness value which exceeds a predetermined threshold.