Constraint-optimization system and method for document component layout generation

• US 20040019851A1
• 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,487,445 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 system for automatic document component layout comprising:

a. means for document layout constraint acquisition;

b. means for document layout variable specification which specifies a set of variables that can be adjusted to achieve a satisfactory layout;

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

d. means for constraint optimization for solving said constraints to find at least one layout which solves for the variables over said constraints.

2. A system for automatic document component layout as defined in claim 1 wherein said optimizable expression is either a minimization or a maximization.

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

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

5. A system for automatic document component layout as defined 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 system for automatic document component layout as defined in claim 5 wherein said variables to be adjusted comprise genes used by said genetic algorithm.

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

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

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

10. A system for automatic document component layout as defined 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 system for automatic document component layout as defined in claim 10 wherein said single fitness function is employed by the genetic algorithm in a refinement of said population of genomes.

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

13. A system for automatic document component layout as defined in claim 1 wherein said layout constraint acquisition means further comprises means for retrieval of said constraints from a storage device.

14. A system for automatic document component layout as defined in claim 13 wherein said layout constraint acquisition means comprises an application interface for input of said constraints.

15. A system for automatic document component layout as defined in claim 1 wherein said means for document layout constraint acquisition comprises computer resources and an application interface sufficient to enable a user thereof to specify a set of variables that can be adjusted to achieve a satisfactory layout.

16. A system for automatic document component layout as defined in claim 1 wherein said means for document layout constraint acquisition comprises computer resources and an application interface sufficient to enable a user thereof to define a set of constraints for said layout.

17. A system for automatic document component layout as defined in claim 1 wherein said means for document layout variable specification comprises computer hardware and software resources and an application interface sufficient to enable a user thereof to specify a set of variables that can be adjusted to achieve a satisfactory layout.

18. A system for automatic document component layout as defined in claim 1 wherein said means for relationship-constraint to optimization-constraint conversion comprises computer hardware and software resources sufficient to enable a user thereof to express 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.

19. A system for automatic document component layout as defined in claim 1 wherein said means for constraint optimization comprises computer resources sufficient to resolve said optimizable constraint to find a layout which solves for the variables over said constraints.

20. A system for automatic document component layout as defined in claim 1 wherein said means for applying said optimized constraints back onto a document comprises computer resources sufficient to resolve said optimizable constraint to find a layout which solves for the variables over said constraints.

21. A system for automatic document component layout as defined in claim 19 wherein said means for constraint optimization comprises:

a. means for constraint combining;

b. an optimization threshold specification means;

c. a layout variable to gene mapping means; and

d. a genetic algorithm engine.