Constraint-optimization system and method for document component layout generation

• US 7,487,445 B2
• Filed: 07/23/2002
• Issued: 02/03/2009
• Est. Priority Date: 07/23/2002
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Harrington, Steven J., Purvis, Lisa S.
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US10/202,188
• Publication Number:
  US 20040019851A1
• Time in Patent Office: 2,387 Days
• Field of Search: 715/517, 715/521, 715/522, 715/523, 715/524, 715/247, 715/249, 382/186, 382/187, 382/193
• US Class Current: 715/249
• 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 processor;

said processor 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;

said processor 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;

said processor solving the required constraints for each document layout member;

said processor solving the desired constraints for each document layout member to establish a score for each document layout member;

said processor selecting the document layout members having each solved required constraint relationship of the document layout satisfied and a score greater than or equal to a predetermined score;

said processor creating a new population of children document layout members by performing crossover/mutation operations upon the selected document layout members;

said processor solving the required constraints for each child document layout member;

said processor solving the desired constraints for each child document layout member to establish a score for each child document layout member;

said processor selecting the children document layout members having each solved required constraint relationship of the document layout satisfied and a score greater than or equal to a predetermined score; and

said processor re-iterating the creating, solving, and selecting processes until a termination condition is realized, the termination condition being defined as a failure to improve the layout after a predetermined number of iterations.

2. A system for automatic document component layout, comprising:

a processor;

said processor 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;

said processor 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;

said processor solving the required constraints for each document layout member;

said processor solving the desired constraints for each document layout member to establish a score for each document layout member;

said processor selecting the document layout members having each solved required constraint relationship of the document layout satisfied and a score greater than or equal to a predetermined score;

said processor creating a new population of children document layout members by performing crossover/mutation operations upon the selected document layout members;

said processor solving the required constraints for each child document layout member;

said processor solving the desired constraints for each child document layout member to establish a score for each child document layout member;

said processor selecting the children document layout members having each solved required constraint relationship of the document layout satisfied and a score greater than or equal to a predetermined score; and

said processor re-iterating the creating, solving, and selecting processes until a termination condition is realized, the termination condition being 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 than or equal to a predetermined score.

3. A system for automatic document component layout, comprising:

a processor;

said processor 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;

said processor 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;

said processor solving the required constraints for each document layout member;

said processor solving the desired constraints for each document layout member to establish a score for each document layout member;

said processor selecting the document layout members having each solved required constraint relationship of the document layout satisfied and a score less than or equal to a predetermined score;

said processor creating a new population of children document layout members by performing crossover/mutation operations upon the selected document layout members;

said processor solving the required constraints for each child document layout member;

said processor solving the desired constraints for each child document layout member to establish a score for each child document layout member;

said processor selecting the children document layout members having each solved required constraint relationship of the document layout satisfied and a score less than or equal to a predetermined score; and

said processor re-iterating the creating, solving, and selecting processes until a termination condition is realized, the termination condition being defined as a failure to improve the layout after a predetermined number of iterations.

4. A system for automatic document component layout, comprising:

a processor;

said processor 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;

said processor 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;

said processor solving the required constraints for each document layout member;

said processor solving the desired constraints for each document layout member to establish a score for each document layout member;

said processor selecting the document layout members having each solved required constraint relationship of the document layout satisfied and a score less than or equal to a predetermined score;

said processor creating a new population of children document layout members by performing crossover/mutation operations upon the selected document layout members;

said processor solving the required constraints for each child document layout member;

said processor solving the desired constraints for each child document layout member to establish a score for each child document layout member;

said processor selecting the children document layout members having each solved required constraint relationship of the document layout satisfied and a score less than or equal to a predetermined score; and

said processor re-iterating the creating, solving, and selecting processes until a termination condition is realized, the termination condition being 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 less than or equal to a predetermined score.