A Constraint-Driven Approach to Automate the Organization and Playout of Presentations in Multimedia Databases

We introduce a constraint-driven methodology for the automated assembly, organization and playout of presentations from multimedia databases. We use inclusion and exclusion constraints for extracting a semantically coherent set of multimedia segments. Presentationorganization constraints are utilized for organizing the multimedia segments into apresentation, which in turn helps decide the playout order of the extractedmultimedia segments. The playout order of the segments is represented in a presentationgraph. If the specified set of organization constraints are not sufficient toconstruct a unique presentation graph, we propose two techniques so that a unique graph isconstructible. We also propose two playout algorithms, one for the generation, start andtermination of playout agents, the other for dynamic control of playout management on organized presentations.The characteristics of these algorithms are expressed in terms of presentation playout parameters.     

Constraint-based automation of multimedia presentation assembly

In this paper, we present a methodology for automated construction of multimedia presentations. Semantic coherency of a multimedia presentation is expressed in terms of presentation inclusion and exclusion constraints. When a user specifies a set of segments for a presentation, the multimedia database system adds segments into and/or deletes segments from the set in order to satisfy the inclusion and exclusion constraints. We discuss the consistency and the satisfiability of inclusion and exclusion constraints when exclusion is allowed. Users express a presentation query by (a) pointing and clicking to an initial set of desired multimedia segments to be included into the presentation, and (b) specifying an upper bound on the time length of the presentation. The multimedia database system then finds the set of segments satisfying the inclusion-exclusion constraints and the time bound. Using priorities for segments and inclusion constraints, we give two algorithms for automated presentation assembly and discuss their complexity. To automate the assembly of a presentation with concurrent presentation streams, we introduce presentation organization constraints that are incorporated into the multimedia data model, independent of any presentation. We define four types of presentation organization constraints that, together with an underlying database ordering, allow us to obtain a unique presentation graph for a given set of multimedia segments. We briefly summarize a prototype system that fully incorporates the algorithms for the segment selection problem.     

MPGS: an interactive tool for the specification and generation ofmultimedia presentations

Multimedia presentations are composed of objects belonging to different data types such as video, audio, text and image. An important aspect is that, quite often, the user defining a presentation needs to express sophisticated temporal and spatial constraints among the objects composing the presentation. We present a system (called MPGS-Multimedia Presentation Generator System) which supports the specification of constraints among multimedia objects and the generation of multimedia presentations according to the specified constraints. The constraint model provided by MPGS is very flexible and powerful in terms of the kinds of object constraints it can represent. A large number of innovative features are supported including: asynchronous and simultaneous spatial constraints; components of interest and priority levels; motion functions. Obviously, the flexibility provided to the users requires the development of nontrivial techniques to check constraint consistency and to generate a presentation satisfying the specified constraints. We illustrate the solutions we have devised in the framework of MPGS     

Conceptual modeling of multimedia objects for user-tailored information presentations

This paper presents a formal framework for the representation of knowledge concerning the use of multimedia information in the context of designing user-tailored information presentations. The aim is to support efficient development and maintenance of knowledge bases and effective utilization of knowledge for adaptive information presentations. It is conjectured that a hybrid knowledge representation framework that mixes formal knowledge structures with canned fragments of multimedia information and distinguishes between categories of medium-independent information items and types of presentation forms comprehensively can achieve this aim. The framework supports subject-based classification of reusable multimedia objects and their utilization according to presentation intentions and to pragmatic constraints. This approach, although it is considered complementary, contrasts to approaches that require systems to build every presentation from scratch.     

Querying multimedia presentations based on content

Considers the problem of querying multimedia presentations based on content information. Multimedia presentations are modeled as presentation graphs, which are directed acyclic graphs that visually specify the presentations. We present a graph data model for the specification of multimedia presentations and discuss query languages as effective tools to query and manipulate multimedia presentation graphs with respect to content information. To query the information flow throughout a multimedia presentation, as well as in each individual multimedia stream, we use revised versions of temporal operators Next, Connected and Until, together with path formulas. These constructs allow us to specify and query paths along a presentation graph. We present an icon-based graphical query language, GVISUAL, that provides iconic representations for these constructs and a user-friendly graphical interface for query specification. We also present an OQL-like language, GOQL (Graph OQL), with similar constructs, that allows textual and more traditional specifications of graph queries. Finally, we introduce GCalculus (Graph Calculus), a calculus-based language that establishes the formal grounds for the use of temporal operators in path formulas and for querying presentation graphs with respect to content information. We also discuss GCalculus/S (GCalculus with Sets) which avoids highly complex query expressions by eliminating the universal path quantifier, the negation operator and the universal quantifier. GCalculus/S represents the formal basis for GVISUAL, i.e. GVISUAL uses the constructs of GCalculus/S directly     

Modeling spatio-temporal constraints for multimedia objects

The presentation of multimedia data is not only characterized by precise temporal constraints; also spatial constraints must be taken into account. An important requirement in multimedia systems is thus the integrated modeling of spatio-temporal constraints. Moreover, it is important to devise methods for checking the consistency of the specified constraints. In this paper, we first propose a spatio-temporal object graph (STOG) model that provides an integrated and graphical representation of spatio-temporal constraints. Second, we investigate consistency conditions between spatial and temporal constraints expressed in the STOG model. Then, we present a prototype system implementing the proposed model.     

A Multimedia Constraint System1

The MADE constraint system provides excellent opportunities to introduce constraints in a multimedia application. Multimedia applications are not only a good place to experiment with constraint systems; constraints in a multimedia environment are almost indispensable. Due to the overwhelming amount of data and the number of relations between several parts of this data, multimedia applications almost demand the support of a constraint management system. The MADE constraint system combines the object oriented programming paradigm, inherited from the mC++ language, the declarative constraint programming paradigm and the special requirements imposed upon the constraint system by the multimedia environment. Among other things, the MADE constraint system provides parallel satisfaction techniques; several constraints may be solved simultaneously and this satisfaction process is performed in parallel with the application. This not only reduces the time needed to solve the constraints, it also allows the multimedia application to proceed with its presentation while (beneath the surface) the constraints are maintained. This not only holds for the parts of the presentation that are not constrained at all, but also for those parts that are. Furthermore, the constraint system is transparent to the multimedia application; no special coding or preparation of the objects in the application is necessary. Constraints can be added later to the application without much work. Besides that, it is also possible to add and remove constraints at runtime; objects may be constrained for only a period of the time the application is running.     

Checking consistency in multimedia synchronization constraints

Constraint-based design is often used to correctly author a multimedia scenario due to its flexibility and efficiency. However, such a system must provide a mechanism with which users can easily manipulate the underlying structures to meet the application requirements. This paper proposes a novel method for analyzing multimedia synchronization constraints based on the constraint graph and classification, which is essential in developing efficient system support tools for constraint-based authoring systems. We specify temporal and spatial relations between multimedia objects, and use a directed graph to represent the constraints among the objects in a multimedia scenario. Moreover, we develop a method for analyzing temporal and spatial synchronization constraints based on graph theory, solving the problems of completeness checking, consistency checking, constraints relaxation and automatic spatio-temporal layout generation in a unified theoretical framework. We also discuss the effects of user interactive authoring. Compared with other methods, the proposed approach is simpler, more efficient, and easier to implement.     

点物体主方向关系的一致性检验

一致性检验问题是主方向关系推理中非常重要的基础理论问题,提出了一种利用欧几里德空间坐标图实施一致性检验的新方法。首先对研究的问题进行了定义,阐述了方向关系的坐标图表示方法,从而使得对点物体方向关系约束集的一致性检验就转化为检测图中是否存在环的问题,通过一致性判定、环的检测、实施方法这3个环节来具体实现。其算法的时间复杂度是O（n+e）,优于传统的O（n²）     

Graphical Transformation of Multimedia XML Documents

As a commonly acceptable standard for guiding Web markup documents, XML allows the Internet users to create multimedia documents of their preferred structures and share with other people. The creation of various multimedia document structures, typically as trees, implies that some kinds of conversion mechanisms are needed for people using different structures to understand each other. This paper presents a visual approach to the representation and validation of multimedia document structures specified in XML and transformation of one structure to another. The underlying theory of our approach is a context-sensitive graph grammar formalism. The paper demonstrates the conciseness and expressiveness of the graph grammar formalism. An example XML structure is provided and its graph grammar representation, validation and transformation to a multimedia representation are presented.     

Modelling and managing disjunctions in scheduling problems

In this paper is presented a method for modelling and managing various constraints encountered in task scheduling problems. The approach aims at characterizing feasible schedules through the analysis of the set of constraints and their interaction, regardless of any optimization criteria. This analysis is achieved by a constraint propagation process on a constraint graph and produces both restricted domains for the decision variables and an updated formulation of the initial constraints. The graphs usually used to model temporal constraints seem to be limited because they only allow the representation of strict precedence relations between two tasks. In order to model a larger variety of temporal constraints, particularly any constraint that connects two events (start- or finish- time of a task), a model called a time-bound-on-node (TBON) graph is proposed in which each task is featured by two nodes. Then it becomes possible to handle constraints on task durations, due for example to flexibilities in resource utilization. This kind of graph is not new and has already been investigated in related works on project planning and Constraint Satisfaction Problems. But its processing and interpretation deserved to he developed, particularly for the present purpose, which is the search for the necessary conditions of feasibility. With respect to conjunctive temporal constraints, the analysis is achieved with a polynomial algorithm based on the longest path search on a conjunctive TBON graph, yielding the necessary and sufficient conditions of feasibility. Taking account of resource constraints leads to defining disjunctive constraints. To this end, disjunctive sets of arcs are introduced, making the TBON graph nonconjunctive. In this case, a complete characterization of feasibility cannot reasonably be faced, due to the combinatorial feature. Nevertheless, a polynomial algorithm that applies reduction and deletion rules on the nonconjunctive part of the graph is proposed to restart new propagations on the conjunctive part until all deductions have been made.     

Modelling energy storage systems using Fourier analysis: An application for smart grids optimal management

In this paper, a new and efficient model for variables representation, named F-coding, in optimal power dispatch problems for smart electrical distribution grids is proposed. In particular, an application devoted to optimal energy dispatch of Distributed Energy Resources including ideal storage devices is here considered. Electrical energy storage systems, such as any other component that must meet an integral capacity constraint in optimal dispatch problems, have to show the same energy level at the beginning and at the end of the considered timeframe for operation. The use of zero-integral functions, such as sinusoidal functions, for the synthesis of the charge and discharge course of batteries is thus consequential. The issue is common to many other engineering problems, such as any dispatch problem where resources must be allocated within a given amount in a considered timeframe. Many authors have proposed different methods to deal with such integral constraints in the literature on smart grids management, but all of them do not seem very efficient. The paper is organized as follows. First, the state of the art on the optimal management problem is outlined with special attention to treatment of integral constraints, then the proposed new model for variables representation is described. Finally, the multiobjective optimization method and its application to the optimal dispatch problem considering different variables representations are considered.     

电子图书馆多媒体信息传输服务质量管理的研究

该文在浏览器/服务器环境下建立了一个数字化图书馆多媒体数据流同步传输的管理方案。定义了多媒体对象、任务、同步化传输约束条件以及相应的QOS评价指标,基于上述方案及评价指标,给出了数字化图书馆多媒体流同步传输的控制算法以及相应的实验结果。     

一种欠约束草图求解方法的研究

基于约束的参数化描述及求解是计算机辅助设计研究的一个热点，欠约束图的求解是参数化设计的基本问题，为了提高欠约束草图求解的参数化设计效率，提出了一种基于隐式约束优先级的欠约束草图求解方法，并首先给出了欠约束图求解的一般方法以及欠约束图的基本特征，提出了利用隐式约束去匹配缺少的显式约束；然后将隐式约束按照一定的规则分成不同的优先级，再利用优先级高的隐式约束去匹配变动约束图中的欠约束，直到完成约束图的有向化；最后，探讨了无尺寸约束图有向化过程中的基本特点，并给出了无尺寸约束图的求解算法和应用实例。实例应用结果表明，效果较好。     

A constrained approach to multifont Chinese character recognition

The constraint graph is introduced as a general character representation framework for recognizing multifont, multiple-size Chinese characters. Each character class is described by a constraint graph model. Sampling points on a character skeleton are taken as nodes in the graph. Connection constraints and position constraints are taken as arcs in the graph. For patterns of the same character class, the model captures both the topological invariance and the geometrical invariance in a general and uniform way. Character recognition is then formulated as a constraint-based optimization problem. A cooperative relaxation matching algorithm that solves this optimization problem is developed. A practical optical character recognition (OCR) system that is able to recognize multifont, multiple-size Chinese characters with a satisfactory performance was implemented     

半监督图核降维方法

基于图结构的数据表示和分析,在机器学习领域正得到越来越广泛的关注。以往研究主要集中在为图数据定义一个度量其相似性关系的核函数即图核,一旦定义出图核,就可以用标准的支持向量机(SVM)来对图数据进行分类。将图核方法进行扩充,先利用核主成分分析(kPCA)对图核诱导的高维特征空间中的数据进行降维,得到与原始图数据相对应的低维向量表示的数据,然后对这些新得到的数据用传统机器学习方法进行分析;通过在kPCA中利用图数据中的成对约束形式的监督信息,得到基于图核的半监督降维方法。在MUTAG和PTC等标准图数据集上的实验结果验证了所提方法的有效性。     

STAMP: A Model for Generating Adaptable Multimedia Presentations

The STAMP model addresses the dynamic generation of multimedia presentations in the domain of Multimedia Web-based Information Systems. STAMP allows the presentation of multimedia data obtained from XML compatible data sources by means of query. Assuming that the size and the nature of the elements of information provided by a data source is not known a priori, STAMP proposes templates which describe the spatial, temporal, navigational structuration of multimedia presentations whose content varies. The instantiation of a template is done with respect to the set of spatial and temporal constraints associated with the delivery context. A set of adaptations preserving the initial intention of the presentation is proposed.Ioan Marius Bilasco is a Ph.D. student at the University Joseph Fourier in Grenoble, France, since 2003. He received his BS degree in Computer Science form the University Babes Bolyai in Cluj-Napoca, Romania and his MS degree in Computer Science from the University Joseph Fourier in Grenoble, France. He joined the LSR-IMAG Laboratory in Grenoble in 2001. His research interests include adaptability in Web-based Information Systems, 3D multimedia data modelling and mobile communications.Jérôme Gensel is an Assistant Professor at the University Pierre Mendès France in Grenoble, France, since 1996. He received his Ph.D. in 1995 from the University of Grenoble for his work on Constraint Programming and Knowledge Representation in the Sherpa project at the French National Institute of Computer Sciences and Automatics (INRIA). He joined the LSR-IMAG Laboratory in Grenoble in 2001. His research interests include adaptability and cooperation in Web-based Information Systems, multimedia data (especially video) modeling, semi-structured and object-based knowledge representation and constraint programming.Marlène Villanova-Oliver is an Assistant Professor at the University Pierre Mendès France in Grenoble, France, since 2003. In 1999, she received her MS degree in Computer Science from the University Joseph Fourier of Grenoble and the European Diploma of 3rd cycle in Management and Technology of Information Systems (MATIS). She received her Ph.D. in 2002 from the National Polytechnic Institute of Grenoble (INPG). She is a member of the LSR-IMAG Laboratory in Grenoble since 1998. Her research interests include adaptability in Web-based Information Systems, user modeling, adaptable Web Services.     

Genetic algorithm for the personnel assignment problem with multiple objectives

The assignment problem is a well-known graph optimization problem defined on weighted-bipartite graphs. The objective of the standard assignment problem is to maximize the summation of the weights of the matched edges of the bipartite graph. In the standard assignment problem, any node in one partition can be matched with any node in the other partition without any restriction. In this paper, variations of the standard assignment problem are defined with matching constraints by introducing structures in the partitions of the bipartite graph, and by defining constraints on these structures. According to the first constraint, the matching between the two partitions should respect the hierarchical-ordering constraints defined by forest and level graph structures produced by using the nodes of the two partitions respectively. In order to define the second constraint, the nodes of the partitions of the bipartite graph are distributed into mutually exclusive sets. The set-restriction constraint enforces the rule that in one of the partitions all the elements of each set should be matched with the elements of a set in the other partition. Even with one of these constraints the assignment problem becomes an NP-hard problem. Therefore, the extended assignment problem with both the hierarchical-ordering and set-restriction constraints becomes an NP-hard multi-objective optimization problem with three conflicting objectives; namely, minimizing the numbers of hierarchical-ordering and set-restriction violations, and maximizing the summation of the weights of the edges of the matching. Genetic algorithms are proven to be very successful for NP-hard multi-objective optimization problems. In this paper, we also propose genetic algorithm solutions for different versions of the assignment problem with multiple objectives based on hierarchical and set constraints, and we empirically show the performance of these solutions.