Electronic Proceedings of the
ACM Workshop on Effective Abstractions in Multimedia
November 4, 1995
San Francisco, California

The Constraint-Based Layout Framework LayLab and Its Applications

Winfried H. Graf
German Research Center for Artificial Intelligence (DFKI) GmbH
Stuhlsatzenhausweg 3
D-66123 Saarbrücken, Germany
(+49 681) 302 5264
graf@dfki.uni-sb.de
http://www.dfki.uni-sb.de/~graf/

ACM Copyright Notice


Abstract

Although multimedia technology is so popular that virtually everyone is using it in some form, the current systems suffer from fundamental layout design problems. This document describes our work on the knowledge-based multimedia layout manager LayLab. LayLab's exploits a dedicated constraint engine that supports the incremental layout and design of interactive and dynamic multimedia displays and flowcharts as well as the treatment of discrete placement problems in finite domains. While we have provided the concepts of our work on constraint-based layout in previous papers [Graf1992,Graf1993,Graf1995], in this abstract, we emphasize the transfer of the theoretical results into a set of diverse applications. Moreover, we will discuss the AI-based layout approach in comparison to conventional techniques.

Table of Contents


Introduction

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.

< -- Table of Contents

Constraint-Based Multimedia Layout

Constraint representation

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.

< -- Constraint-Based Multimedia Layout

Constraint solving

The constraint solver has to satisfy the hybrid set of graphical constraints in a well-designed final layout as well as to handle local and global consistency among them. Regarding the heterogeneous requirements of static geometric placement versus interactive graphical layout, we treat the computation of a multimedia layout as a combination of constraint satisfaction (CS)---problem solving on constraints (search for solutions)---and constraint-based inference (CBI) problems---problem solving using constraints (modification of (sub)solutions). [4]

In order to address the two disjunct constraint problem classes we have developed the following hybrid layout constraint engine

[IMG]
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.

< -- Constraint-Based Multimedia Layout
< -- Table of Contents

The Architecture of LayLab

The generic layout tool LayLab has been developed for automating a broad class of layout and graphical editing tasks in dynamic multimedia environments for presenting, designing, and visualizing information. It takes into consideration semantic-pragmatic, aesthetical, and perceptual layout aspects as well as the communicative intent and situative context of the presentation. Therefore, the system achieves as an input a set of multimedia items and rhetorical information as well as a set of generation parameters, such as the user's layout preferences, presentation type and intent, output medium, and resource limitations. Thus, LayLab is one of the first principled constraint-based multimedia layout systems. [5]

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

< -- Table of Contents

LayLab Applications

The LayLab system has already shown its flexibility in numerous applications, such as layout manager in WIP and currently as multimedia display manager in the dynamic environment PPP LayLab.

Display management in dynamic multimedia environments

The display manager is designed for arranging the automatically generated multimedia output in a way that is best suited for the intended mapping along with managing the interface to the user and the application. The following two snapshots of a multimedia interface are designed with LayLab.

[IMG]
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]
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.

< -- LayLab applications

Incremental layout of flowcharts

Another domain with wide applicability addresses modeling, (re)design, and visualization of hierarchically structured flowcharts. The layout of large and complicated network diagrams is laborious to produce by hand. For example, in workflow management and visual programming it is unacceptable to waste time with layout specifications and tedious drawing operations.

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

< -- LayLab applications

Electronic publishing

Also in the expanding field of commercial yellow-page telephone directories, logical pagination and editing play a crucial role. Here the increasing dynamics of today's market as well as tough, innovative marketing strategies require effective tools that enable edition companies to produce customized documents with a large variety of objects easily and allow frequent updates and changes or even new editions in short time. But in practice, an efficient design of the layout of classified advertisements (ads) is a hard computational problem, especially for large sets of multi-column ads. Therefore, for the commercial application system YPPS (Yellow-Page Pagination System), LayLab 's finite domain solver FIDOS has been enriched by a special constraint abstraction, that represents heuristic placement strategies (based on weighted grids) for display ads, in order to allow for an automated logical pagination of printed yellow pages.

[IMG]
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.

< -- LayLab applications
< -- Table of Contents

Discussion, Conclusions, and Future Work

In this abstract, we have briefly discussed a novel approach towards a principled layout framework for arranging and authoring multimedia documents that is based on state-of-the-art constraint programming techniques. Although conventional techniques such as traditional graph drawing algorithms have been widely studied [Di Battista et al. 1994] and have been approved as rather efficient when dedicated to specific applications, an AI approach based on constraint technology provides the following strong advantages for automated multimedia layout: Constraint languages allow a flexible and intuitive formulation of complex layout restrictions as well as a declarative representation of design knowledge. Hence, a constraint-based layout system is easy to maintain, extend, and customize by the user. Moreover, it is easy to adapt to various presentation media and to tailor to a specific user profile by setting design parameters. Furthermore, constraint formalisms can cope with semantic aspects of the layout.

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.

< -- Table of Contents

End Notes

[1] In contrast to conventional multimedia and hypermedia systems, IntelliMedia systems rely on a representation of the content of the presentation, are not limited to canned presentation segments and hardwired layout patterns, and thus enable an infinite number of tailored presentations.

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


Acknowledgements

This work has been supported by a grant from The German Ministry for Research and Technology (BMBF) under contract ITW 9400. We would also like to thank the anonymous reviewers for their valuable comments.
< -- Table of Contents

Bibliography

André and Rist1993
E. André and T. Rist. The design of illustrated documents as a planning task. In Maybury1993, pages 94--116.

André and Rist1994
E. André and T. Rist. Multimedia presentations: The support of passive and active viewing. In Working Notes of the AAAI Spring Symposium on `Intelligent Multimedia Multimodal Systems', Stanford University, CA, 1994.

André et al. 1993
E. André, W. Finkler, W. Graf, T. Rist, A. Schauder, and W. Wahlster. WIP: The automatic synthesis of multimodal presentations. In Maybury1993, pages 75--93.

Borning et al. 1992
A. Borning, B. Freeman-Benson, and M. Wilson. Constraint hierarchies. LISP and Symbolic Computation: An International Journal, 5(3):223--270, 1992.

Brandenburg1994
F. J. Brandenburg. Designing graph drawings by layout graph grammars. In R. Tamassia and I. G. Tollis, editors, Graph Drawing: DIMACS International Workshop, LNCS 894, pages 416--427. Springer-Verlag, Berlin, Germany, 1994.

Catarci et al. 1992
T. Catarci, M. F. Costabile, and S. Levialdi, editors. Advanced Visual Interfaces. World Scientific Series in Computer Science - Vol. 36. World Scientific Press, Singapore, 1992. Proceedings of the International Workshop AVI '92.

Cruz and Eades1995
I. F. Cruz and P. Eades, editors. Journal of Visual Languages and Computing, Special Issue on Graph Visualization. Academic Press, New York, NY, July 1995.

Cruz et al. 1995
I. F. Cruz, K. Mariott, and P. Van Hentenryck, editors. International Workshop on Constraints for Graphics and Visualization (CGV '95) in conjunction with the International Conference on Principles and Practice of Constraint Programming (CP95). Cassis, France, September 18 1995.

Di Battista et al. 1994
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Journal of Computational Geometry Theory and Applications, 4(5):235--282, 1994. Also available via http://www.cs.brown.edu/people/rt/gd-biblio.html.

Feiner et al. 1992
S. Feiner, J. Mackinlay, and J. Marks. Automating the design of effective graphics for intelligent user interfaces. Tutorial Notes, Human Factors in Computing Systems, CHI-92, Monterey, CA, U.S.A., May. 4, 1992.

Feiner1988
S. Feiner. A grid-based approach to automating display layout. In Proceedings of the Graphics Interface '88, Edmonton, Canada, pages 192--197. Morgan Kaufmann, Los Altos, CA, June 1988.

Freeman-Benson et al. 1990
B. Freeman-Benson, J. Maloney, and A. Borning. An incremental constraint solver. Communications of the ACM, 33(1):54--63, 1990.

Graf and Neurohr1995
W. H. Graf and S. Neurohr. Constraint-based layout in visual program design. In Proceedings of the 1995 IEEE Symposium on Visual Languages, pages 116--117, Darmstadt, Germany, September 5--9 1995.

Graf1992
W. H. Graf. Constraint-based graphical layout of multimodal presentations. In Catarci et al. 1992, pages 365--385.

Graf1993
W. H. Graf. LayLab: A constraint-based layout manager for multimedia presentations. In G. Salvendy and M. J. Smith, editors, Human-Computer Interaction: Software and Hardware Interfaces, pages 446--451. Elsevier, Amsterdam, 1993. Proceedings of HCI International'93 (5th International Conference on Human-Computer Interaction jointly with 9th Symposium on Human Interface (Japan)).

Graf1995
W. H. Graf. Intent-based layout in interactive multimedia communication. In Proceedings of the First International Workshop on Intelligence and Multimodality in Multimedia Interfaces (IMMI-1), Edinburgh, Scotland, July 13--14 1995.

Hower and Graf1995
W. Hower and W. H. Graf. Research in constraint-based layout, visualization, CAD, and related topics: A bibliographical survey. In Cruz et al. 1995. Also available as DFKI Research Report RR-95-12 and via http://www.uni-koblenz.de/~walter/ and http://www.dfki.uni-sb.de/~graf/.

Hower et al. 1995
W. Hower, D. Köstner, and M. Rosendahl. Computer-aided layout by evolutionary computing. In R. C. Veltkamp and E. H. Blake, editors, Proceedings of the EUROGRAPHICS '95 Workshop on Programming Paradigms in Graphics, Maastricht, Netherlands, September 2--3 1995.

Kosak et al. 1991
C. Kosak, J. Marks, and S. Shieber. A parallel genetic algorithm for network-diagram layout. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 458--465. Morgan Kaufmann, Los Altos, CA, 1991.

Kosak et al. 1994
C. Kosak, J. Marks, and S. Shieber. Automating the layout of network diagramms with specified visual organization. IEEE Transactions on Systems, Man, and Cybernetics, 24(3):440--454, 1994.

Krüger and Rist1995
A. Krüger and T. Rist. Since less is often more: Methods for stylistic abstractions in 3D-graphics. In present volume, 1995.

Maybury1993
M. Maybury, editor. Intelligent Multimedia Interfaces. AAAI Press, Menlo Park, CA, 1993.

Maybury1994
M. T. Maybury. Research in multimedia and multimodal parsing and generation. Journal of Artificial Intelligence Review: Special Issue on the Integration of Natural Language and Vision Processing, 8(1-3), 1994.

Takahashi et al. 1991
S. Takahashi, S. Matsuoka, A. Yonezawa, and T. Kamada. A general framework for bi-directional translation between abstract and pictorial data. In Proceedings of the UIST'91 (ACM SIGGRAPH Symp. on User Interface Software and Technology), pages 165--174, Hilton Head, SC, U.S.A., 1991.

Tsang1993
E. Tsang, editor. Foundations of Constraint Satisfaction. Academic Press, New York, NY, 1993.

Vanderdonckt and Gillo1994
J. Vanderdonckt and X. Gillo. Visual techniques for traditional and multimedia layout. In Proceedings of the Workshop on Advanced Visual Interfaces (AVI 94), pages 95--104, New York, NY, 1994. ACM Press.

Wahlster et al. 1993
W. Wahlster, E. André, W. Finkler, H.-J. Profitlich, and T. Rist. Plan-based integration of natural language and graphics generation. Artificial Intelligence, Special Issue on Natural Language Processing, 63, 1993.

Weitzman and Wittenburg1994
L. Weitzman and K. Wittenburg. Automatic generation of multimedia documents using relational grammars. In Proceedings of the ACM Multimedia '94, pages 443--451, San Francisco, CA, October 1994.

Wittenburg1995
K. Wittenburg. Visual language parsing: If I had a hammer ... In Proceedings of the International Conference on Cooperative Multimodal Communication (CMC/95), pages 17--33, Eindhoven, NL, May 24--26, 1995.
< -- Table of Contents