![[IMG]](clay-eng.JPG)
Figure 1. The hybrid layout constraint engine.
Although multimedia technology is so popular that virtually everyone is using it in some form, the current systems suffer from fundamental problems, for example, intent-based automated layout, high-level authoring, adaptation and interaction, abstract representations of the presentation content, and semantics of the interface (see also [Catarci et al. 1992,Maybury1993,Wahlster et al. 1993,Maybury1994,Wittenburg1995]). In most commonly marketed applications, such as multimedia presentation generation, flowchart design, electronic publishing, and digital directory access, especially inherent layout and design problems establish crucial points. In this respect, there comes an increasing need to build advanced tools for passive and active viewing based on effective abstractions, that support features like customized/customizable displays and individualized content on an adequate abstraction level.
While there has been significant research on automated layout that has mainly focused either on specific graphics types---in the context of graphics generation [Feiner et al. 1992]--- or on the application of specific formalisms, there seems to be no principled layout manager that makes use of the structural properties of the underlying multimedia information. Beside many other approaches---such as graph drawing algorithms (cf. [Di Battista et al. 1994,Cruz and Eades1995]), relational grammars (e.g. [Weitzman and Wittenburg1994,Brandenburg1994]), rule-based systems (e.g. [Feiner1988,Kosak et al. 1994]), and genetic algorithms (e.g., [Kosak et al. 1991,Hower et al. 1995])---especially constraint processing techniques as knowledge representation paradigm as well as inference mechanism have extensively been used for automated graphical layout (e.g. [Takahashi et al. 1991,Graf1992]; for an overview see also [Cruz et al. 1995] and [Hower and Graf1995]).
At DFKI we have been engaged in the developement of so-called IntelliMedia [1] that meet current drawbacks by incorporating AI techniques into the multimedia design process. In this paper, we describe the constraint-based layout framework LayLab that has been developed in the context of the IntelliMedia presentation and design system WIP [André et al. 1993,Wahlster et al. 1993] [2]. LayLab [Graf1992,Graf1993] has been designed as a task-independent, full-fledged multimedia layout toolkit for automating the layout of generated material as well as constraint-oriented support of graphical editing and design. We show how powerful constraint processing techniques, such as constraint hierarchies, finite-domain constraint abstractions, and indirect reference constraints, can be collected in a multimedia layout manager to maintain graphical style and consistency for a meaningful layout. Our guiding design rationales are interactivity, adaptivity, and incrementality in order to account for consistency, effectiveness, and expressiveness.
The logical structure of multimedia presentations is essentially characterized by the functional dependencies between a wide range of multimedia items, including canned and generated text and (2D/3D) graphics, animation, hypermedia and virtual elements. In WIP , the layout design process is based on an elaborated structuring of multimedia information along an intentional and a rhetorical dimension. Here, semantic-pragmatic relationships between multimedia fragments are expressed by means of so-called rhetorical relations, for instance, sequence, contrast, elaborate-exchange, comply-with-request, etc. (cf. [André and Rist1993,André and Rist1994]).
A central idea of our approach is to address automated layout by using constraint processing techniques (cf. [Tsang1993]) to represent and process causal design principles and perceptual criteria about human visual abilities for structuring and organizing multimedia documents. Semantic-pragmatic constraints, spatial constraints (geometrical-topological relations between absolute and relative coordinates), dynamic constraints (e.g., interactions), and temporal constraints (e.g., animation sequences) are represented in terms of equations and inequalities. LayLab 's underlying constraint language enables the aggregation of primitive graphical constraints (e.g., under, above, beside) to more complex constraints that represent visualization techniques, such as horizontal/vertical alignment, sequential ordering, balance, grouping, and symmetry.[3] Over-constrained situations and design alternatives are handled by prioritizing constraints in hierarchies [Borning et al. 1992]. An additional feature is the handling of dynamic constraints on sets of variables (e.g., stated by user interaction and editing operations) by allowing so-called indirect reference constraints, which introduce the concept of pointer variables into declarative constraint programming. As graphical constraints frequently have only local effects, they are incrementally generated by the system on the fly.
Geometrical placement heuristics in a finite domain search space---represented as a domain-specific grid---are formulated by special constraint abstractions on logical variables, that cumulate constraints and control knowledge (e.g., left-to-right or top-to-bottom placement for a specific reading order).
In order to account for adaptive presentations, application-specific requirements and generation parameters are mapped onto graphical constraints or propagators, that enable an a priori reduction of a finite discrete design space. Optimization criteria are reflected in domain-specific placement strategies. Since we aim at an intent-based layout [Graf1995], we also relate the communicative goal of the presentation (e.g., an instruction how to prepare espresso) to graphical constraints regarding expressiveness and effectiveness criteria, that specify which relationsships should be emphasized through specific layout patterns. This constraint representation provides a firm basis for an efficient computation of the final layout.
In order to address the two disjunct constraint problem classes we have developed the following hybrid layout constraint engine
Figure 1. The hybrid layout constraint engine.
It integrates two dedicated constraint solvers for interactive layout and the treatment of discrete placement problems.
(1) The local propagation solver SIVAS is based on the perturbation model that uses the value inference technique to propagate values in a data-driven computation. Here, we exploit the well-known DeltaBlue algorithm [Freeman-Benson et al. 1990] to solve constraint hierarchies efficiently and maintain an incremental solution as constraints are added or removed dynamically. In SIVAS , indirect reference constraints are solved using a lazy evaluation algorithm. Hereby, we consider the fact, that in interactive graphical environments not only the constraints changes frequently, but the constraint solving algorithm must be capable of finding solutions without reducing the direct manipulation responsiveness.
(2) The finite domain constraint solver FIDOS is based on the refinement model that uses the constraint propagation technique referred to as label inference. FIDOS enables LayLab to efficiently solve discrete combinatorial placement problems by using forward checking inference on propagators and placement strategies specified as constraint abstractions that enables an early a priori pruning of the search space.
Based on the central layout constraint engine, LayLab 's architecture embeds major, task-specific components that support the following functionality by the help of constraints: grid-based placement and display management in CLAY , semantic-based typography, and the multimedia editor InLay . LayLab can be driven in different execution modes according to the kind of application, such as fully-automated vs. semi-automated fashion, incremental design assistance, editing with automatic beautification, and interaction.
![[IMG]](laylab-eng.JPG)
Figure 2. The Architecture of the LayLab Framework.
Beside others InLay supports the user in multimedia authoring by enabling her to create an interface through pre-editing of layout sketches, which can automatically be beautified by the system following certain design constraints. Moreover, we facilitate the user to tailor the interface to her needs by post-editing automatically generated presentations using editable graphical histories or default layout templates.
![[IMG]](ppp2.gif)
Figure 3. Automatically produced layout of a
multimedia display.
In the first picture, the system has automatically determined the layout of a sequence of three graphics with elaborating texts as part of a graphics tutorial. Since it is impossible to anticipate all needs and requirements of each potential user, the system reacts on further user requests on the fly or allows the manipulation of the interface by user interaction (e.g., zooming, iconifying, moving windows)
![[IMG]](ppp1.gif)
Figure 4. Beautified layout with generated meta presenter.
Here, the user is requested to state only interface semantics, not syntax. For example, as the user requests to focus on the ``sphere window'', the system zooms into the corresponding window, enlarges its size, and adapts all other windows considering the display resources (in the second picture). Moreover, in order to communicate more effectively it generates and positions the animated character PPP as a meta-presenter to comment the generated material. The system automatically beautifies the display by resatisfying all constraints quickly enough to allow continuous interaction. The LayLab constraints are used to specify horizontal alignment and sequential ordering, consistency among multiple views, and behavior of different interactions.
Let's have a short look at a sequence of snapshots taken when LayLab is being used in a visual programming environment [Graf and Neurohr1995]:
![[IMG]](flow-3.gif)
Figure 5. Constraint-based visual programming.
Window A shows a program flowchart that has been automatically laid out by the system. In B the insertion of a new rectangular item by a user's mouse gesture is shown. Then LayLab supports the consistent layout of the flowchart by automatically beautifying the display after adding and connecting operations (in part C). As the user browses or edits the flowgraph, the system incrementally updates visibility changes in a smooth fashion nearly in real-time. Hereby it accounts for topological consistency in order to avoid visual discontinuities.
Furthermore, LayLab facilitates the user to zoom into deeper levels of a hierarchical information structure, to focus currently processed objects, and overview context information on an automatically generated virtual desktop simultaneously.
![[IMG]](ypps1.JPG)
Figure 6. A snapshot of the yellow-page pagination
system YPPS.
In the average case YPPS enables the pagination of one spread in less than five seconds. The flexibility of YPPS supports both system designers and the end user in specifying constraints in a high-level language as well as allows them to run the system in batch and edit mode either. Moreover, the end user can select among a set of optimization criteria and design parameters in order to tailor the layout to the specific needs of a company or country. In the next stage, YPPS will be extended to a display manager for electronic yellow-page delivery.
We think that the integration of two efficient, specialized solvers in a layout constraint engine provides a suitable compromise in the trade-off between declarativity/universality versus efficiency for the wide spectrum of graphical layout problems.
Current challenging research topics are concerned with any-time layout algorithms and the reuse of layout templates. Further applications of LayLab involve the generation of personalized electronic newspapers, intelligent multimedia retrieval as well as tele-shopping/marketing assistance.
[2] See also the work on WIP's automated graphics designer in [Krüger and Rist, in present volume]
[3] Extensive investigations of visual organization techniques for layout are provided in [Vanderdonckt and Gillo1994] and [Kosak et al. 1994].
[4] This classification reflects the two major constraint solving approaches: the perturbation model vs. the refinement model.
[5] Other graphics systems or user interfaces just apply general constraint solvers to restricted sets of layout problems or have an integrated specialized solver.