R Abdullah

M Christie

G Schofield

C Lino

P Olivier

Advanced Composition in Virtual Camera Control

Rapid increase in the quality of 3D content coupled with the evolution of hardware rendering techniques urges the development of camera control systems that enable the application of aesthetic rules and conventions from visual media such as film and television. One of the most important problems in cinematography is that of composition, the precise placement of elements in shot. Researchers already considered this problem, but mainly focused on basic compositional properties like size and framing. In this paper, we present a camera system that automatically configures the camera in order to satisfy advanced compositional rules. We have selected a number of those rules and specified rating functions for them, then using optimisation we find the best possible camera configuration. Finally, for better results, we use image processing methods to rate the satisfaction of rules in shot.

Introduction

As the field of computer animation evolved, camera control has developed from the simple process of tracking an object to also tackle the aesthetic problems a cinematographer faces in reality. As Giors noted, the camera is the window through which the spectator interacts with the simulated world [START_REF] Giors | The full spectrum warrior camera system[END_REF]. This means that not only the content of screen space becomes very important but also its aesthetic qualities, making composition a very important aspect of camera control.

For practical purposes, we divide the problem of composition into two levels: the basic level in which simple properties like position, size, and framing are considered and the advanced level in which more generic, aesthetic rules from photography and cinematography are considered. The rule of thirds is a good example of advanced level composition.

We are developing a camera system that automatically adjusts a camera in order to satisfy certain compositional rules gleaned from photography and cinematography literature, namely, the rule of thirds, diagonal dominance, visual balance, and depth of field. We implement rating functions for these rules and use optimisation to find the best possible camera configuration. The rating functions depend on image processing, rather than geometrical approximation as implemented in most systems. Though it has the disadvantage of not being real, it has the advantage of being precise which is a requirement in composition.

We start by discussing the most relevant research in this area, focussing on approaches to composition in different applications. Then, we explain the composition rules we have selected and how to rate them. Finally, we demonstrate the use of our system in rendering a scene from a well known film.

Background

Many previous approaches targeted composition, but most of them only handled basic compositional rules. Olivier et al. [START_REF] Olivier | Visual composition as optimisation[END_REF], in their CamPlan, utilised a set of relative and absolute composition properties to be applied on screen objects. All the properties realised in CamPlan are basic. Burelli et al. [START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF] defined a language to control the camera based on visual properties such as framing. They start by extracting feasible volumes in according to some of these properties and then search inside them using particle swarm optimisation. Like CamPlan, this approach lacks support of advanced composition rules.

Another limitation in previous approaches is the use of geometrical approximation of objects for faster computation. In his photographic composition assistant, Bares [START_REF] Bares | A photographic composition assistant for intelligent virtual 3d camera systems[END_REF] improves composition by applying transformations on the camera to shift and resize screen elements. However, the system depends on approximate bounding boxes which is often not sufficiently accurate. To alleviate this problem, Ranon et al. [START_REF] Ranon | Accurately measuring the satisfaction of visual properties in virtual camera control[END_REF] developed a system to accurately measure the satisfaction of visual properties and developed a language that enables the definition of different properties. The main shortcoming of their system is that it only evaluates the satisfaction of properties, rather than finding camera configurations satisfying them.

The final limitation that we are concerned about is that the methods used in previous work on composition either has limited applicability in computer graphics, or cannot be applied at all. For example, in Bares's assistant, depending on restricted camera transformations rather than a full space search limits the application of the method to improving camera configurations rather than finding camera configurations.

In digital photography world, Banerjee et al. [START_REF] Banerjee | Unsupervised automation of photographic composition rules in digital still cameras[END_REF] described a method to apply the rule of thirds to photographs by shifting the main subject(s) in focus so that it lies on the closest power corner. The main subject(s) is detected using a wide shutter aperture that blurs objects out of focus. Besides the limitation of the method to only one object and one rule, the method cannot be applied in computer graphics. Similarly, Gooch et al. [START_REF] Gooch | Artistic composition for image creation[END_REF] applied the rule of thirds on a 3D object by projecting its silhouette on screen and matching it with a template. Again, the method is limited to one object only.

Liu et al. [START_REF] Liu | Optimizing photo composition[END_REF] addressed the problem of composition using cropping and retargeting. After extracting salient regions and prominent lines, they use particle swarm optimisation [START_REF] Kennedy | Particle swarm optimization[END_REF] to find the coordinates of the cropping that maximise the aesthetic value of an image based on rule of thirds, diagonal dominance, and visual balance. Though it addresses advanced composition, it cannot be applied to computer graphics.

Our system is an attempt to address the main shortcomings of the approaches above, namely a) the lack of advanced composition rules b) the use of approximate geometrical models, and finally c) the limited applicability.

Composition Rules

Although we implement basic composition rules in our system, our primary focus is on more advanced aesthetic conventions. We have explored some of the most important rules in the literature of photography and cinematography and selected the following for implementation because they have a clear impact on the results:

1. Rule of Thirds: The rule of thirds proposes that a useful starting point for any compositional grouping is to place the main subject of interest on any one of the four intersections (called the power corners) made by two equally spaced horizontal and vertical lines [START_REF] Ward | Picture Composition for Film and Television[END_REF]. It also proposes that prominent lines of the shot should be aligned with the horizontal and vertical lines [START_REF] Grill | Photographic Composition[END_REF]. See figure 1a. Composition systems that have implemented this rule are [START_REF] Banerjee | Unsupervised automation of photographic composition rules in digital still cameras[END_REF][START_REF] Bares | A photographic composition assistant for intelligent virtual 3d camera systems[END_REF][START_REF] Byers | Say Cheese! Experiences with a Robot Photographer[END_REF][START_REF] Gooch | Artistic composition for image creation[END_REF][START_REF] Liu | Optimizing photo composition[END_REF]. 2. Diagonal Dominance: The rule proposes that "diagonal arrangements of lines in a composition produces greater impression of vitality than either vertical or horizontal lines" [START_REF] Ward | Picture Composition for Film and Television[END_REF]. For example, in figure 1b, the table is placed along the diagonal of the frame. A system that has implemented this rule is [START_REF] Liu | Optimizing photo composition[END_REF]. 3. Visual Balance: The visual balance rule states that for an equilibrium state to be achieved, the visual elements should be distributed over the frame [START_REF] Ward | Picture Composition for Film and Television[END_REF]. For example, in figure 1c, the poster in the top-left corner balance the weight of the man, the bottle, the cups, and other elements. Systems that have implemented this rule are [START_REF] Bares | A photographic composition assistant for intelligent virtual 3d camera systems[END_REF][START_REF] Liu | Optimizing photo composition[END_REF][START_REF] Lok | Evaluation of Visual Balance for Automated Layout[END_REF]]. 4. Depth of Field: The depth of field rule is used to draw attention to the main subject of a scene by controlling the parameters of camera lens to keep the main subject sharp while blurring other elements. See figure 1d.

Besides the advanced composition rules, it is also important to have a set of basic rules to help in controlling some of the elements of the frame. For this, we have implemented the following basic composition rules:

1. Framing Rule: This rule specifies that the frame surrounding a screen element should not go beyond the specified frame. This rule is useful when an element needs to be placed in a certain region of the frame. See figure 1e.

Other systems that have implemented this rule is [START_REF] Bares | Virtual 3D Camera Composition from Frame Constraints[END_REF][START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF][START_REF] Lino | A Real-time Cinematography System for Interactive 3D Environments[END_REF][START_REF] Olivier | Visual composition as optimisation[END_REF]]. 2. Visibility Rule: This rule specifies that a minimum/maximum percentage of an element should be visible. For example, a case like that of figure 1f in which showing a character causes another character to be partially in view can be avoided by applying this rule on the character to the right. Other systems that have implemented this rule are [START_REF] Bares | Virtual 3D Camera Composition from Frame Constraints[END_REF][START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF][START_REF] Olivier | Visual composition as optimisation[END_REF].

Position Rule:

This rule specifies that the centre of mass of an element should be placed on a certain position of the screen. Other systems that have implemented this rule are [START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF][START_REF] Olivier | Visual composition as optimisation[END_REF]. 4. Size Rule: This rule specifies that the size of a certain element should not be smaller than a certain minimum or larger than a certain maximum (specified by the user of the system). This rule is mainly useful to control the size of an element to ensure its size reflects its importance on the frame. Other systems that have implemented this rule are [START_REF] Bares | Virtual 3D Camera Composition from Frame Constraints[END_REF][START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF][START_REF] Olivier | Visual composition as optimisation[END_REF].

As different compositions need different rules, the rules are specified manually. All rules take an object ID(s) as a parameter and some other parameters depending on the rule's requirements. We refer the reader to section 5 for practical examples.

Rules Rating

The camera systems of many applications depend on methods specific to the geometry of the application only. However, our system is scene-independent, with the ability to impose many rules on many objects which makes the problem strongly non-linear. This, along with the aim of producing aesthetically-maximal results, suggests rating shots according to the satisfaction of rules and using optimisation to solve for the best possible camera configuration. We found the optimisation method used by Burelli et al. [START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF] and Liu et al. [START_REF] Liu | Optimizing photo composition[END_REF], particle swarm optimisation, to be very efficient, so we use it. The rating of shot is described in this section.

Rendering Approach

Many approaches use geometrical approximation (e.g. bounding boxes) of scene objects to efficiently rate rules via closed form mathematical expressions [START_REF] Bares | A photographic composition assistant for intelligent virtual 3d camera systems[END_REF][START_REF] Burelli | Virtual camera composition with particle swarm optimization[END_REF]. The downside of this approach is being inaccurate. To address this downside, we use the rendering approach. We render scene objects as an offline image and then process the resulting image to rate rules satisfaction for a certain camera configuration. The downside of the rendering approach is speed because of the time needed to render objects and process resulting images. Since composition rules apply to certain objects only, which we call ruled objects, we only render those objects and process the resulting image. However, one problem with image processing is the inaccuracy, difficulty, and cost of recognising object extents in an image. Since for the rules we selected the most important aspect is the region occupied by an object rather than its colours, we can safely avoid these problems by rendering objects with unique distinct colour for each. Moreover, since the same pixel might be occupied by more than one object, the colour we use for each object occupies only one bit of the RGBA pixel, then using blending with addition we can have as many as 32 objects occupying the same pixel. The problem then comes down to comparing each pixel in the rendered image against objects' colours. Figures 2a and2b illustrates the modified rendering process.

An important issue to consider in the rendering method is that the resulting image tells nothing about the parts of an object which are out of view, making the rating of some rules incorrect, e.g. visibility rule. To solve this problem we use a field of view wider than the original such that the original view covers only the rectangle having corners (25%, 25%) and (75%, 75%), rather than the whole screen. This way we know which parts of objects are visible and which are invisible. This is illustrated in figure 2b in which the white rectangle represents the separator between the visible and invisible areas.

Rating Functions

In our system, each rule usually has several factors determining its rating value. For example, the rating of the diagonal dominance rule is determined by two factors: the angle between the prominent line of an object and the diagonal lines of the screen and the distance between the prominent line and the diagonal lines. For any rule, we rate each of its factors, then find the mean of ratings.

To get the best results from particle swarm optimisation, we suggest the following criteria for the rating of each factor: Fig. 2: To make image processing easier, we only render ruled objects and use different colour for each object. Furthermore, we bring the pixels resulting from the rendering towards the centre of the image such so that we can process pixels which are originally out of view.

1. While the function must evaluate to 1 when the factor is fully satisfied, it must not drop to 0, otherwise the method will be merely an undirected random search. However, after some point, which we call the drop-off point, the function should drop heavily to indicate the dissatisfaction of the factor. 2. The function must have some tolerance near the best value, at which the function will still have the value 1. This gives more flexibility to the solver.

We suggest using Gaussian function as a good match for these criteria. For each factor, we decide a best value, a tolerance, and a drop-off value, and then use Gaussian function as follows:

F R = e ( ∆-∆ t ∆ do -∆ t ) 2 (1)
where F R is factor rating, ∆ is the difference between the current value of the factor and the best value, ∆ t is the tolerance of the factor, and ∆ do is the difference between the drop-off value and the best value.

Having the rating of each factor of a rule, we use geometric mean to find rule rating since it has the property of dropping down heavily if one of the factors drop heavily. However, the combined rating of all rules can be calculated using arithmetic or geometric mean (specified by the user) since sometimes it is not necessary to satisfy all rules. Moreover, weights can be specified for each rule according to its importance in the configuration.

The data in table 1 gives the parameters of the different factors of all the composition rules we support in our system. Table 2 lists some of the symbols used in table 1. Crucially, we separate the rule of thirds into two rules, one for the power corners and the other for horizontal and vertical lines. This is because they usually apply to different elements of the screen.

Shot Processing

To rate the satisfaction of a rule we need to process the shot after rendering. The rating of framing rule and size rule depend on the frame surrounding the object Table 1: The factors the camera solver depends on to rate the rules.

Symbol Description HD

Half the distance between the power corners (i.e. 0.33333) FW Width of the frame used by the framing rule. FH Height of the frame used by the framing rule. AOW Average width of the projection on screen of the object being considered by a rule.

AOH

Average object of the projection on screen of the object being considered by a rule.

Table 2: Symbols and abbreviations used in factors calculation.

on screen which can be easily found. The rating of visibility rule depends on the number of pixels in the visible and invisible areas which is also straightforward to calculate. The rating of visual balance and the power corners in the rule of thirds, the rating depends on the centroid of the object, which is also straightforward to calculate.

As for diagonal dominance and the horizontal and vertical lines in the rule of thirds, the rating depends on the prominent line of the ruled object, which is found by applying linear regression on the pixels of the object to find the best fitting line. The standard linear regression minimising the vertical distance between the line and the points. This is mainly useful in case the aim of the regression is to minimise the error which is represented by the vertical distance between the line and the points. However, in our case we want to find a line that fits best rather than a line that minimises the error so we use a modified linear regression called perpendicular linear regression [START_REF] Weisstein | Least squares fitting-perpendicular offsets[END_REF]. The method starts by finding the centroid of all the points then finding the angle of the line passing through the centroid which minimise the perpendicular distance. The angle is found according to the following equations:

tan(θ) = - A 2 ± ( A 2 ) 2 -1 (2)
where

A = n i=1 x 2 i - n i=1 y 2 i n i=1 x i y i (3)
where (x i , y i ) is the coordinate of the ith pixel of the object. Figure 3a illustrates the prominent line of the table in figure 1b and figure 3b illustrates the same concept but for a character to be positioned according to rule of thirds.

Finally, the rating of the depth of field rule is always 1, as the adjustment of the camera lens cannot be decided before the position, orientation, and field of view of the camera are found. Once they are found, the camera depth of field are adjusted according to the size of the object and its distance from the camera.

Evaluation

As a practical demonstration of our system, we decided to render a scene from Michael Radford's Nineteen Eighty-Four. The scene we selected is set in a canteen and revolves around 4 important characters in the plot, Smith, Syme, Parsons, and Julia. In the scene, the protagonist, Smith is engaged in conversation with Syme and Parsons at the lunch table, and Julia is watching Smith from across the room. An additional secondary character participates briefly in one of the conversations and we call him OPM (abbreviation of Outer Party Member).

The scene has been rendered in 3DSMAX and exported to OGRE. We used our system to automatically find camera configurations similar to those of the original scene. We then used those camera configurations to generate a video of the rendering of the scene. The video is attached with this paper. Table 3 lists some of the shots that have been generated and the rules used to generate each shot. For each shot, we repeated the test 10 times and calculated the mean and standard deviation of the achieved rating, processing time, and number of iterations until a solution is found, which we also include in the table in the second column, where the standard deviation is the value in brackets. Finally, our screen coordinates range from (-1, -1) at the bottom-left corner to (1, 1) at the top-right corner.

The system we ran the test on has a 2.66 GHz Intel Core 2 Quad Core Q9400 processor and an NVIDIA GeForce 9800 GT video card with 512 MB of video memory. For the rating, scene objects are rendered on an 128×128 offline texture. It is possible to use smaller texture sizes to reduce processing time, but this will decrease the accuracy of the results.

We configured the PSO to use 36 particles in each iteration, each particle representing a camera configuration of 3D position, 2 orientation angles, and an angle for the field of view. Initially, the position is randomly positioned in boxes manually specified around the objects of interest. The orientation and field of view angles are also randomly specified in a manually set range. The algorithm breaks if the rating reach 98% or after 100 iterations. As obvious from the table data, the standard deviation of the rating is either zero or negligible, which shows that the results obtained by the system are steady. Another thing to notice is that the processing time varies widely among the different shots because different shots have different rules. Also, the standard deviation of the time is relatively large because, depending on the initial random configurations, the required number of iterations before a solution is reached varies widely. In the fourth configuration specifically, the number of iterations is zero. This is because we fixed the position of the camera to Syme's eyes to show the view from his perspective, and only allowed the camera pitch and field of view to be adjusted, making it enough for the initial step to find a satisfactory solution. Finally, the rating of the last shot is relatively low because the used rules cannot be satisfied together.

Finally, the number of particles used has an important effect on the result. For in one hand, if we reduce the number of particles, the achieved rating will decrease, while if we increase the number of particles, the processing time will heavily increase with not much gain in rating. For more information about tuning particle swarm optimisation we refer the reader to [START_REF] Carlisle | An off-the-shelf pso[END_REF][START_REF] Pedersen | Tuning & Simplifying Heuristical Optimization[END_REF].

Conclusion and Future Work

We have implemented a camera system for advanced composition. The system has been implemented based on particle swarm optimisation, which proved to be very successful in finding solutions in high dimensional search spaces, a necessity for camera control. To get accurate results we rated shots based on image processing, as opposed to geometric approximation. The main shortcoming of our approach is the time it takes to find a solution, which makes the system limited to offline processing only. The other shortcoming is that the occlusion problem is not considered here as it requires full rendering of the scene which is a expensive operation. Future work will be focused on solving these two shortcomings. We are investigating the possibility of implementing the image processing computations on the GPU rather than the CPU. This would heavily reduce the processing time, as the bottleneck of our system is transferring the image data from the GPU memory and processing them in the CPU.

Fig. 1 :

 1 Fig. 1: Images illustrating composition rules

Fig. 3 :

 3 Fig.3: Illustrating how the prominent line of an object is found using perpendicular linear regression. The line in blue is the prominent line extracted from the object in dark red.

Acknowledgements

This research is part of the "Integrating Research in Interactive Storytelling (IRIS)" project, and we would like to thank the European Commission for funding it. We would also like to forward our thanks to Zaid Abdulla, from the American University of Iraq Sulaimani (AUI-S) for his invaluable help with the technical aspects of the research. Finally, we would like to thank the reviewers of this paper for their comments.

Table 3: The list of shots used in the rendering of a scene from Nineteen Eighty-Four. For each shot, we repeated the test 10 times and calculated the average rating the system could achieve and the average time spent in the solving process. The numbers in the brackets are the standard deviation of the results of the 10 tests.


Christophe Lino

Mathieu Chollet

Marc Christie

Rémi Ronfard

Posters and Demos Automated Camera Planner for Film Editing Using Key Shots

Keywords: Descriptors (according to ACM CCS): Computer Graphics [I, 3, 3]: Virtual Cinematography-

Generating films from 3D animations requires knowledge in cinematography (camera placement, framing and lighting) and editing (cutting between cameras). In applications where the user is already engaged in other tasks, such as playing a game, directing virtual actors, or narrating a story, it appears desirable to build systems that can make decisions about cinematography and editing and automatically generate a grammatically correct movie according to film grammar. In this paper, we introduce a framework for generating a well-edited movie based on the rules of film editing. Specifically, our system computes a sequence of shots by simultaneously choosing which camera to use, when to cut in and out of the shot, and where to cut to. We cast film editing as a cost minimization problem in the space of possible shot sequences and provide an efficient search algorithm. The method is illustrated with multiple edits of the same footage in different editing rhythms and styles.

Introduction

In this paper, we provide a general computational framework for automatically generating a cinematic editing of a 3D animation. Our framework proposes scores for shots and cuts, independently of the film idioms used to generate them. The score for a shot is based on the Hitchcock principle of showing action from the best angle [ST85] and the score for a transition between shots is based on the working practices of film and television [START_REF] Thompson R | Grammar of the Edit[END_REF]Tho98]. Previous work has described techniques for choosing camera setups and generating virtual footage based on the rules of cinematography [HCS96, ER07, JA10, LCL * 10]. Instead, we cast the problem of film editing as selecting a path in time through the collection of takes and precisely deciding when to enter the take and when to exit the take. This is a non traditional shortest path problem. We restrict the complexity by providing a cost function which is semi-markovian, i.e. the cost of a sequence is computed as a sum over its key shots and transitions between successive key shots. We propose a fast search algorithm suitable for online editing under that model.

Film Grammar Rules

Evaluating the score of an entire sequence for a movie is built up from the scores of its shots and transitions. We make the assumption that a cost function can be computed for each shot and cut in the sequence. The cost per shot (a shot is a part of a take of duration ∆t) is evaluated as a weighted sum of all violations of the rules of frame composition. And similarly, the cost of a cut is evaluated as a weighted sum of all violations of the rules of editing.

We further assume that the cost of a complete sequence s(t) ∈ [1, M], t ∈ [1, N] of N shots using M takes is the sum of the costs for all of its shots and cuts :

C(s) = ∑ t ∑ k w k C S k (s(t),t) + ∑ l w l C T l (s(t), s(t + 1),t)
A last term we add in the evaluation of a sequence is a score for the pacing of cuts and the duration of shots, which are important factors in the rhythmic perception of films [START_REF] Salt | Film Style and Technology: History and Analysis[END_REF]. When cutting from camera i to camera j at time t, this additional term takes into account the previous cutting time u(t) to estimate if the duration tu(t) of the closing shot is right, according to a user-defined log-normal law.

Online editing as path finding

In our model, film editing is cast as the search for a minimum-cost path through all available cameras, with entry and exit points in time. The cost function is a sum over Figure 1: Searching for the optimal transition in the observation window to decide whether to cut or stay in the shot. In top image, the current optimal shot sequence is drawn in red and recommends to cut at time t. A scanning process over the observation window (in light blue) is performed to seek for a possible better moment. In bottom image, a sequence with a better cost is found (displayed in red). The observation window is then shifted ahead and the process starts over.

all shots and transitions from shot to shot. As such, it is amenable to a time-efficient, offline dynamic programming solution. In this communication, we instead propose an informed best-first search which uses anticipation to locally decide the best moment for a transition in real time.

At a given depth in the search process, a critical decision needs to be made whether to stay within the current shot, or to perform a transition to another shot. To inform this decision, we rely on an observation window over the next w time steps. We study within the observation window the best transition to be performed, given the knowledge of the shots to come. If the best transition occurs immediately, the transition is performed. If the best transition occurs later in the observation window, we shift the window a step ahead and start the process over.

To compute the best moment for a transition inside the observation window we use an incremental scanning process, illustrated in Figure 1. Given the current shot is c, for a given time t in the observation window and for each shot i = c, the cost of a possible transition from shot c to shot i is given by

C CUT (c, i) = C S (c, 0,t) +C PACE (c d ) +C T (c, i) +C S (i,t, w)
where C S (i,t 1 ,t 2 ), C T (i, j) and C PACE represent resp. the costs associated to the shot i from time t 1 to time t 2 in the window, a transition between two shots i and j, and to the pace, and where c d represents the duration of shot c. The best cost over all available shots i at time t is compared to the cost of staying in the current shot:

C NOCUT (c) = C S (c, 0, w) +C PACE (c d )
If the cost of staying in the current shot c is the minimal cost (ie C NOCUT (c) ≤ min i C CUT (c, i)), we extend its duration by ∆t and the observation window is shifted ahead. If there exists a shot i such that C CUT (c, i) < C NOCUT (c) at time t, we need to know whether to cut at the current time t to shot i, or to wait for a better moment. To implement this, the process explores the successive time steps t + ∆t,t + 2∆t, ..t + w∆t in the observation window until a cost lower than C CUT (c, i) is found. In such case, the best cut occurs later and the observation windows is shifted ahead. Otherwise, t represents the best moment for a transition and a cut is performed towards shot i.

Conclusion

We have introduced a novel framework for virtual cinematography and editing which adds an evaluation function to previous approaches. Furthermore, we have introduced an efficient search strategy for finding the best sequence of shots from a large number of candidates generated by traditional film idioms. In future work, we would like to extend the approach to higher-level criteria, including story advancement, repetition, style and emotion.


Christophe Lino

Mathieu Chollet

Marc Christie

Remi Ronfard

Computational Model of Film Editing for Interactive Storytelling

Keywords:

Generating interactive narratives as movies requires knowledge in cinematography (camera placement, framing, lighting) and film editing (cutting between cameras). We present a framework for generating a well-edited movie from interactively generated scene contents and cameras. Our system computes a sequence of shots by simultaneously choosing which camera to use, when to cut in and out of the shot, and which camera to cut to.

Introduction

In interactive storytelling, it is useful to present 3D animation in a cinematic style, which means selecting appropriate cameras and appropriate inter-cutting between cameras to properly convey the narrative. We propose an optimization framework for selecting shots and cuts while the narrative unfolds, based on a relatively simple scoring scheme driven by working practices of film and television [START_REF] Murch | In the blink of an eye[END_REF][START_REF] Thompson | Grammar of the Edit[END_REF]. We cast the problem of film editing as selecting a path inside an editing graph which consists of a collection of evolving film takes (a take is a continuous sequence of images from a given camera) and precisely deciding when to cut in and out of film takes. In contrast to related work, we also account for a precise enforcement of pacing (rhythm at which cuts are performed). We propose an algorithm suitable for online editing which uses an efficient best-first search technique. The algorithm relies on short-term anticipation to improve quality in cuts and produce movies consistent with the rules of cinematography and editing, including shot composition, continuity editing and pacing.

The paper is organized in two parts. The first part describes the score functions used to evaluate shots, transitions and pacing illustrated by a number of examples. The second part explains the search process for exploring the editing graph during the storytelling process with a very minimal lookahead.

Film Grammar Rules

In our system the score of a movie is built up incrementally as the sum of the scores of its shot fragments and transitions. The cost per fragment (a fragment is a part of a take of duration ∆t) is evaluated as a weighted sum of all violations of the rules of frame composition w k × C S k . And similarly, the cost of a transition (or cut) is evaluated as a weighted sum of all violations of the rules of editing w l × C T l (see equation 1). We compute a complete sequence s as a sequence of shots s i of durations d i and cuts between shots. Each shot s i is processed as the concatenation of fragments f (t) where t is a time interval of length ∆t. We then assume that the cost of s is the sum of the costs for all of its fragments and cuts, plus a function C P of the durations of shots:

C S A = 0.8 C S A = 0.3 C S A = 0.2 C S A = 0.7 C S A = 0.5 C S A = 0.2
(1)

C(s) = t k w k × C S k (f (t), t) + l w l × C T l (f (t), f (t + 1)) + i C P (d i ) 2.

Shot composition

The cost of a shot fragment integrates the violation of three terms: action, visibility, and composition. The action term C S A (t) measures the amount of the scene action which is missed in the given fragment, computed as a sum over all actions a occurring during the fragment:

(2)

C S A (t) = a imp(a) × M A [type(a), size(a), angle(a)]
where type(a) is the type of action, imp(a) its importance in the narrative, size(a) the screen size of its protagonist and angle(a) the profile angle of its protagonist. The action matrix M A contains empirical preferences for shot framings as a function of action types. Figure 1 illustrates the preferences for shot sizes and profiles for the special case of two actions types: pouring and drinking.

Shot transitions

A transition between shots causes a visual discontinuity. The art of the editor is to minimize the perception of discontinuity by selecting appropriate shots and moments for cutting [START_REF] Berliner | The illusion of continuity: Active perception and the classical editing system[END_REF][START_REF] D'ydewalle | Perceptual and cognitive processing of editing rules in film[END_REF][START_REF] Smith | An Attentional Theory of Continuity Editing[END_REF]. In this work, we compute the cost of a cut as a sum of terms measuring discontinuities in the screen positions, gaze directions and motion directions of actors. Moreover, we weight each term with the screen size size(i) of each actor i, so that continuity in the foreground receives a larger reward than in the background. Screen continuity Screen continuity prevents actors in successive shots to appear to jump around the screen. Because the actor's eyes are the most important center of attention, we favor transitions which maintain the actor's eyes at the same screen location.

Gaze continuity When watching a movie the gaze direction of actors should not change. We thus use a cost function that penalizes camera changes that cause apparent reversals in the actor's gaze directions.

(

) C T GAZE = i∈screen(f1)∩screen(f2) size(i) × δ(sign(x G i,f1 ) -sign(x G i,f2 )) 3
where screen(f k ) represents the actors that project on the screen during fragment f k , x G i,f k is the horizontal on-screen coordinate of the gaze direction for actor i in fragment f k and δ is the Kroneker symbol. Figure 2 shows two cuts with increasing gaze continuity scores.

Motion continuity

The motion direction of actors in two successive shots should not change also. We thus use a cost function that penalizes camera changes that cause apparent reversals in the actor's motion, defined as:

(4) C T M OT ION = i∈screen(f1)∩screen(f2) size(i) × δ(sign(x M i,f1 ) -sign(x M i,f2 ))
where x M i,f k is the screen motion of the actor's eyes in fragment f k measured in the horizontal on-screen direction, and δ is the Kroneker symbol.

Shot durations

To control the pace of the editing, we introduce a duration cost per shot, measuring the deviation from a log normal law, where d is the duration of the shot, µ and σ are resp. the mean and the standard deviation of the log normal law:

(5)

C P (d) = (log(d) -µ) 2 2σ 2
The log-normal distribution is a compact and discriminative representation of shot durations in movies as well as sentence lengths in natural language [START_REF] Salt | Film Style and Technology: History and Analysis[END_REF] and its two parameters can be used as a signature of film editing or writing styles.

The computation of an optimal sequence of shots consists in searching the path of least cost in our editing graph. Exact and efficient algorithms exist for computing a solution offline. For interactive storytelling applications, we instead describe an approximate method that chooses shots and cuts incrementally as the story unfolds and runs at interactive framerates. At a given depth in the search process (i.e. advancement in time over the fragments), a decision needs to be made whether to stay within the current shot or perform a cut to a shot in an other take. We use a short observation window over the next W fragments to compute the best moment for transition. Given the current shot is s c , for a given time t in the observation window and for each shot s i = s c , we compute the cost C CU T of a possible transition from shot s c to shot s i , and we compare it to the cost C N OCU T of staying in the current shot. If C N OCU T (s c ) ≤ min i C CU T (s c , s i ) (i.e. the cost of staying in s c is the minimal cost), we extend the duration of s c by ∆t and the observation window is shifted a fragment ahead. If there exists a shot s i such that C CU T (s c , s i ) < C N OCU T (s c ) at time t, we need to know whether to cut at the current time t to shot s i , or to wait for a better moment. To implement this, we scan successive fragments at t + ∆t, t + 2∆t, ..t + W ∆t in the observation window until a cost lower than C CU T (s c , s i ) is found. In such case, the best cut occurs later and the observation window can be shifted a fragment ahead. Otherwise, t represents the best moment for a transition and a cut is performed towards shot s i . Results are presented here http://sites.google.com/site/christophelino/work/film editing.

Conclusion

We have introduced a novel framework for virtual cinematography and editing which adds an evaluation function to previous approaches. Preliminary results demonstrate that our approach is efficient in separating correct from incorrect shot sequences in complex narratives with many actors and actions, and is thus appropriate for future research in film-mediated interactive storytelling.

This work has been funded (in part) by the European Commission under grant agreement IRIS (FP7-ICT-231824).

Fig. 1 .

 1 Fig. 1. Action costs. Left: Three shots of a drinking action. Right: Three shots of a pouring action.

Fig. 2 .

 2 Fig. 2. Gaze continuity. Left: the gaze direction of the main character changes, resulting in a poor cut. Right: keeping the gaze directions consistent results in a better cut.


Elisabeth Altmaier
email: elisabeth.altmaier@helmholtz-muenchen.de

Gabi Kastenmüller

Werner Römisch-Margl

Barbara Thorand

Klaus M Weinberger

Thomas Illig

Jerzy Adamski

Angela Döring

Karsten Suhre

Questionnaire-based self-reported nutrition habits associate with serum metabolism as revealed by quantitative targeted metabolomics

Keywords: dietary pattern, metabolomics, mass spectrometry, nutrition habits, food questionnaires, epidemiology

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Potential causes of complex diseases, such as type 2 diabetes and cardiovascular disease, can be analyzed from many different perspectives (Figure 1). For instance, a number of genomewide association studies (GWAS) identified associations between common genetic polymorphisms (SNPs) and diabetes or coronary artery disease [START_REF] Zeggini | Meta-analysis of genome-wide association data and large-scale replication identifies additional susceptibility loci for type 2 diabetes[END_REF][START_REF] Todd | Robust associations of four new chromosome regions from genome-wide analyses of type 1 diabetes[END_REF][START_REF] Samani | Genomewide association analysis of coronary artery disease[END_REF]. In addition to such heritable genetic predispositions, environmental factors such as the human lifestyle and nutrition habits play an important role in the development of the respective clinical outcome.

Examples would be the effect of meat and fish consumption on the risk of colorectal cancer, metabolic differences in the intake of green and black tea or the metabolic effects of dietary isoflavones in humans [START_REF] Norat | Meat, fish, and colorectal cancer risk: the European Prospective Investigation into cancer and nutrition[END_REF][START_REF] Van Dorsten | Metabonomics approach to determine metabolic differences between green tea and black tea consumption[END_REF][START_REF] Walsh | Influence of acute phytochemical intake on human urinary metabolomic profiles[END_REF][START_REF] Solanky | Biofluid 1H NMR-based metabonomic techniques in nutrition research -metabolic effects of dietary isoflavones in humans[END_REF][START_REF] Kimura | Meat, fish and fat intake in relation to subsite-specific risk of colorectal cancer: The Fukuoka Colorectal Cancer Study[END_REF][START_REF] Chao | Meat consumption and risk of colorectal cancer[END_REF][START_REF] Cross | A prospective study of red and processed meat intake in relation to cancer risk[END_REF][START_REF] Stella | Susceptibility of human metabolic phenotypes to dietary modulation[END_REF]. However, directly associating genes or lifestyle habits with clinical endpoints provides only limited information about the underlying disease-causing mechanisms. Moreover, the p-values of such associations are most often relatively low. Using quantitative targeted metabolomics as an access to intermediate phenotypes (as described in detail in [START_REF] Gieger | Genetics meets metabolomics: a genome-wide association study of metabolite profiles in human serum[END_REF]) provides a much closer insight into the mechanisms that cause the clinical endpoint. Using high resolution electrospray ionization tandem mass spectrometry (ESI-MS/MS) it is, today, possible to measure hundreds of metabolites at the same time in a single sample [START_REF] Altmaier | Bioinformatics analysis of targeted metabolomics--uncovering old and new tales of diabetic mice under medication[END_REF]. Gieger et al. [START_REF] Gieger | Genetics meets metabolomics: a genome-wide association study of metabolite profiles in human serum[END_REF] showed that associating genetic variants with changes in the homeostasis of metabolic compounds can yield larger effect sizes as well as access to the underlying molecular disease-causing mechanisms. Likewise, lifestyle parameters such as smoking habits and coffee consumption can be clearly discerned in metabolic profiles. Wang-Sattler et al. [START_REF] Wang-Sattler | Metabolic profiling reveals distinct variations linked to nicotine consumption in humans--first results from the KORA study[END_REF] suggest that smoking is associated with plasmalogen-deficiency disorders and Altmaier et al. [START_REF] Altmaier | Variation in the human lipidome associated with coffee consumption as revealed by quantitative targeted metabolomics[END_REF] could identify an increase in the concentration of two classes of sphingomyelins and a decrease in the acylcarnitine levels with an increased coffee consumption.

Here, we focus on the effect of nutrition habits on the human metabolism and in particular on how self-reported nutrition intake associates with metabolic profiles of the study participants" blood samples. Epidemiological studies provide growing evidence that diet is associated with the risk of many chronic diseases. Thus, an accurate assessment of nutrition habits is of growing importance. Though traditional measurement methods are improving and new techniques are developed [START_REF] Dowell | Use of electronic self-monitoring for food and fluid intake: A pilot study[END_REF][START_REF] Kikunaga | The application of a handheld personal digital assistant with camera and mobile phone card (Wellnavi) to the general population in a dietary survey[END_REF][START_REF] Subar | Formative research of a quick list for an automated self-administered 24-hour dietary recall[END_REF][START_REF] Slimani | Perspectives of using the EPIC-SOFT programme in the context of pan-European nutritional monitoring surveys: methodological and practical implications[END_REF][START_REF] Wang | Development of a new instrument for evaluating individuals' dietary intakes[END_REF], the complexity of nutrition intake naturally leads to errors in its assessment. Comprehensive information about nutrition habits would include a multitude of different factors, such as portion size of foods, frequency of consumption, food composition, daily variations in food intake and many more. However, documenting all these parameters in epidemiological studies is not always feasible. Thus, errors in the assessment of the consumed food are to be expected [START_REF] Michels | The role of nutrition in cancer development and prevention[END_REF][START_REF] Jenab | Biomarkers in nutritional epidemiology: applications, needs and new horizons[END_REF] and an independent validation against quantitatively measurable parameters is needed.

Here, we ask the question, in how far self-reported nutrition habits based on questionnaires can be associated with changes in the metabolic homeostasis. For clinical short-term studies, where factors like food intake are exactly defined and controlled, finding such associations would probably be not astonishing. Here, however, we focus on population studies, where a general nutrition habit is self-reported. Analyzing population studies for associations between the self-reported nutrition habits and the metabolic profile might then evaluate the quality and potential of the used questionnaires.

We present results from a study where we measured the metabolic profiles of 284 male participants from the KORA (Cooperative Health Research in the Region of Augsburg) study population. For each participant, information on many different factors concerning disease state, medication items or life style is available. In particular, most participants responded to a set of 18 questions of a qualitative food frequency questionnaire (see Table 4). Each of the queried food groups such as meat, fish, vegetables, cheese or chocolate was reported on a scale from 1 ("never") to 7 ("several times per day"). In a first step we analyzed these KORA food groups for associations with the measured metabolic profiles. In a second step we defined nutrition indices by pooling the food groups by their nutrient content, such as "dietary fibers", "saturated fatty acids", "monounsaturated fatty acids", and "polyunsaturated fatty acids" and tested them for associations with the metabolic data. In a third and final step we examined the effect of the overall diet on the human metabolism. For identifying associations of the nutrition lifestyle with the clinical outcome, dietary pattern analysis is a common approach [START_REF] Hu | Dietary pattern analysis: a new direction in nutritional epidemiology[END_REF][START_REF] Fung | Dietary patterns, meat intake, and the risk of type 2 diabetes in women[END_REF][START_REF] Liu | Dietary pattern, the metabolic syndrome, and left ventricular mass and systolic function: the Multi-Ethnic Study of Atherosclerosis[END_REF]. Following this idea, we identified dietary patterns and analyzed them for associations with the measured metabolic profiles. This approach may provide a broader picture of the impact of specific nutrition habits on health than the analysis of single food groups could do alone.

MATERIAL & METHODS

Experimental Setup

The research platform KORA (Cooperative Health Research in the Region of Augsburg) conducts population-based surveys and subsequent follow-up studies in the fields of health care research, epidemiology, health economics and genetics. A multitude of different parameters is provided, including life style factors (questionnaires related to physical activity, nutrition, alcohol consumption, smoking, etc.), medical history, and socio-demographic variables. The dataset analyzed here was taken from the F3 study, which was conducted in 2004-2005 as a follow-up of the third MONICA (Monitoring of Trends and Determinants in Cardiovascular Disease) survey (S3; 1994/1995). For this follow-up study F3, 3006 of the 4856 participants of the S3 were reexamined for a second time, thus, 10 years apart from the baseline examination. From this group, 284 male participants, aged between 55 and 79 years at the examination for F3, were chosen randomly for our analysis and were again recruited one to two years later for additional blood sampling. In total, 239 of these study participants provided details concerning their intake of the following foods: "Meat (except sausage)", "sausages and ham", "poultry", "fish", "potatoes", "pasta", "rice", "cooked vegetables", "fresh fruit", "chocolate, chocolates", cakes, pastries, biscuits", "salted snacks", "whole-grain bread, black bread, crispbread", "flaked oats, muesli, cornflakes", "curds, yoghurt and sour milk", "cheese", "eggs", and "milk". The foods were queried by a score from 1 to 7: "never", "once a month or less", "several times a month", "about once a week", "several times a week", "daily or almost daily", "several times per day" (see Table 1). Food indices were computed as the sum of the responses that make up the given indices (see Table 4). Thus, the indices "dietary fibers" and "polyunsaturated fatty acids" can each range from 3 to 21, "monounsaturated fatty acids" from 8 to 56, and "saturated fatty acids" ranges from 9 to 63. This food frequency questionnaire was validated against a 7-day dietary record (n=899; applied in a previous KORA/MONICA study) with the result that it can be used for analysis on group level [START_REF] Winkler | Validation of a short qualitative food frequency list used in several German large scale surveys[END_REF].

Blood samples

For collection of blood samples for metabolic analysis F3 study participants were invited again in 2006. To avoid variation due to circadian rhythm, blood was drawn in the morning between 8 and 10 am after a period of overnight fasting. Material was immediately horizontally shaken (10 min), followed by 40 min resting at 4°C to obtain complete coagulation. The material was then centrifuged (2000g; 4°C). Serum was aliquoted and stored for 2-4 hours at 4°C, after which it was deep frozen to -80°C until mass spectrometry analysis.

Metabolite profiling

Targeted metabolite profiling by electrospray ionization (ESI) tandem mass spectrometry (MS/MS) was performed at Biocrates life sciences AG, Austria. The technique is described in detail in [START_REF] Weinberger | Metabolomics in diagnosing metabolic diseases[END_REF][START_REF] Weinberger | Using Comprehensive Metabolomics to Identify Novel Biomarkers[END_REF]. A comprehensive overview of the field and the related technologies is given in the review paper by Wenk [START_REF] Wenk | The emerging field of lipidomics[END_REF]. Briefly, the assay preparation was done by an automated robotics system (Hamilton Robotics GmbH) on a special double-filter 96 well plate containing isotope labeled internal standards. Assays used 10µl plasma and include phenylisothiocyanate (PITC)-derivatisation of amino acids, extraction with organic solvent and several liquid handling steps. Flow injection analysis coupled with multiple reaction monitoring scans (FIA MS/MS) on an API 4000 QTrap instrument (Applied Biosystems) was used for quantification of amino acids, acylcarnitines, sphingomyelins, phosphatidylcholines, and hexoses. LC-MS/MS methods using multiple reaction monitoring, neutral loss and precursor ion scans were applied for biogenic amines, eicosanoids and hydroxylated fatty acid derivatives as well as for intermediates of the energy metabolism. The quantification of the metabolites is achieved by reference to appropriate internal standards. The method is proven to be in conformance with the "Guidance for Industry -Bioanalytical Method Validation" published by the FDA (Food and Drug Administration), which implies proof of reproducibility within a given error range. This measurement platform has been successfully used in the past in different academic and industrial applications [START_REF] Gieger | Genetics meets metabolomics: a genome-wide association study of metabolite profiles in human serum[END_REF][START_REF] Altmaier | Bioinformatics analysis of targeted metabolomics--uncovering old and new tales of diabetic mice under medication[END_REF][START_REF] Wang-Sattler | Metabolic profiling reveals distinct variations linked to nicotine consumption in humans--first results from the KORA study[END_REF].

Metabolite spectrum

For all analyzed metabolites the concentrations are reported in μM. In total, 363 different chains and a single double bond in one of them. In some cases, the mapping of metabolite names to individual masses can be ambiguous. For example, stereo-chemical differences are not always discernable, neither are isobaric fragments.

Statistical analysis

The statistical analysis system R (http://www.r-project.org/) and SPSS for Windows (Version 16.0, Chicago: SPSS Inc.) were used for this statistical analysis.

As a basis for our statistical analysis, we used in particular ratios between metabolite concentrations. As shown previously, the use of such ratios leads to a strong reduction in the overall variance and therefore improves the strength of association [START_REF] Altmaier | Bioinformatics analysis of targeted metabolomics--uncovering old and new tales of diabetic mice under medication[END_REF]. A high increase in the strength of association may also indicate that the two metabolites are linked by a metabolic pathway that is influenced by the respective (nutrition) factor.

Thus, the ratios of the concentrations of all possible pairs (363 2 ) of metabolites are computed.

For the identification of metabolites influenced by the nutrition habits, for each of the 18 food groups, the four nutrition indices and the seven dietary patterns, a linear regression test was applied to model each metabolite ratio. To control for the effect of testing multiple hypotheses and, thus, taking possible correlations among metabolites into account, the positive false discovery rate (q-value) was computed for each ratio and each dietary variable. The positive false discovery rate is defined by Storey et al. [START_REF] Storey | The positive false discovery rate: A Bayesian interpretation and the qvalue[END_REF] as pFDR = E[V/R | R>0], where "positive" means that at least one rejection occurred. The pFDR can be used to define the q-value, which is a natural pFDR analogue to the p-value. Thus, the q-value is a measure for the fraction of false positives appearing even if the test itself was significant. In contrast to the p-value the qvalue is a multiple hypothesis testing quantity [START_REF] Storey | The positive false discovery rate: A Bayesian interpretation and the qvalue[END_REF].

The dietary patterns were identified using principal component analysis on the food groups using SPSS. Only principal components with an eigenvalue larger than one were considered for further analysis. For each of these principal components a new variable with the transformed values (method: regression) was calculated. To each of these new variables a linear regression test was applied to model each metabolite ratio analogical to the food variables above. Thereby, metabolite ratios can be identified that are influenced by the respective dietary pattern.

RESULTS

Food groups associate with saturation and chain length of phospholipids

As a first step, in order to gain insight into nutrition associated metabolic changes, we tested the association of self-reported intake of single food groups with the metabolite profiles in human serum using linear regression. The results are summarized in Table 2. Using age and BMI as cofactors for the linear regression showed no substantial difference to the analysis without any cofactors. All analyzed food groups mainly affected the degree of saturation and/or the chain length of the fatty acid residues of the glycero-phosphatidylcholines.

An association with a decrease in saturation of the fatty acid residues could be observed for the consumption of "sausages, ham" and "fish" (e.g. the ratio between PC aa C40:4 and PC aa C40:6 with a q-value of 8.67x10 -10 ). In contrast, an increase in saturation was associated with "flaked oats, muesli, cornflakes" and "cheese". The results for "flaked oats, muesli, cornflakes" additionally revealed a decrease in the chain lengths of the fatty acid residues. For "vegetables, cooked" the ratio between hexanoylcarnitine (C6) and kynurenin concentrations was found as association with the lowest q-value (q-value: 5.89x10 -3 ). "Fresh fruit" associated most strongly with a ratio composed of an acylcarnitine and a glucosylceramide, namely C10/GlcCer C22:2 (q-value: 2.27x10 -3 ) and "chocolate, chocolates" with ratios containing each a sphingomyelin and a glycero-phosphatidylcholine, e.g. SM C22:0/PC aa C38:3 (qvalue: 1,35x10 -4 ). "Curds, yoghurt, sour milk" achieved the lowest q-value for association with SM (OH) C28:1/SM (OH) C20:1 (q-value: 2.93x10 -2 ), a ratio composed of two Nhydroxylacyloylsphingosyl-phosphocholines. For all these associations positive false discovery rates (q-value) below 0.05 were thus obtained. For the following food groups no association with a positive false discovery rate (q-value) smaller than 0.05 could be identified:

"meat (except sausage)", "poultry", "potatoes", "pasta", "rice", "cakes, pastries, biscuits", "salted snacks", "whole-grain bread, black bread, crispbread", "eggs" and "milk". In summary, the analysis of the food groups shows that associations of several of these food groups with different metabolic profiles can be observed, albeit some of them with relatively low q-values. Most of these differences are related to the saturation and chain length of phospholipids.

The nature of the nutrient intake indices matches the character of the associating metabolic profiles

As a next step, we aimed to identify those metabolites that are influenced by the food indices "dietary fibers", "saturated fatty acids", "monounsaturated fatty acids", and "polyunsaturated fatty acids".

The index "dietary fibers" was defined by the food groups "vegetables, cooked", "wholegrain bread, black bread, crispbread" and "flaked oats, muesli, cornflakes" (Table 4). For this index "dietary fibers" metabolite ratios that suggest a shift towards more saturation and smaller chain length of the fatty acid residues showed the strongest association (Table 3), e.g.

the ratio PC ae C36:1/ PC aa C40:4 with a positive false discovery rate (q-value) of 1.20x10 -5 and a positive correlation coefficient of 0.4. In order to investigate this observed shift towards more saturation further, sums of the serum concentrations of glycero-phosphatidylcholines were used for analysis. The association with the lowest q-value (2.45x10 -7 ) was the ratio of the sum of all acyl-alkyl-PC with one or two double bonds and the sum of all diacyl-PC with 4 or 5 double bonds (Figure 2). This supports the idea that "dietary fibers" are associated with an increase in phospholipid saturation. To answer the question whether the binding type of the fatty acids in the glycero-phosphatidylcholineacyl or alkylmay influence the observed association, we focused on those ratios that contain exclusively diacyl-PCs (Table 3b) or exclusively acyl-alkyl-PCs (Table 3c). For both separately analyzed classes also an increase of the saturation of the fatty acid residues could be observed. The sum of all diacyl-PC showed only a slight negative association with dietary fibers (p-value: 1.53x10 -3 , q-value:

1.79x10 -2 ), while for the sum of all acyl-alkyl-PC no association could be detected. Thus, the intake of dietary fibers mainly associates with the saturation of the fatty acid residues but might also have an effect on the type of PC that is formed.

The index "dietary fibers" is the sum of the food groups "cooked vegetables", "whole-grain bread, black bread, crispbread" and "flaked oats, muesli, cornflakes" (Table 4). The analysis of these factors showed that only self-reported "flaked oats, muesli, cornflakes" (q-value:

2.24x10 -4 ) consumption was also associated with a higher saturation and a smaller fatty acid chain length. The analysis of the index "dietary fibers" lead to an increased strength of association and, thus, shows that additional information can be obtained when using nutrition indices as compared to individual food groups.

The index "polyunsaturated fatty acids" is composed of the three food groups: "meat (except sausage)", "poultry" and "fish". This index was associated with a decrease in saturation of the fatty acid residues of the glycero-phosphatidylcholines, where the signal of the strongest associating ratio is found for PC aa C40:5/PC aa C40:6 with a small positive false discovery rate (q-value: 5.94x10 -5 ) and a negative correlation coefficient of -0.38 (Figure 3).

Docosapentaenoyl-CoA (C22:5) and Docosahexaenoyl-CoA (C22:6) are closely connected in the biosynthesis of unsaturated fatty acids [START_REF] Sprecher | Reevaluation of the pathways for the biosynthesis of polyunsaturated fatty acids[END_REF]. Synthesis of these metabolites to a glycerol 3phosphate, and further addition of a stearoyl-moiety (C18:0), followed by a dephosphorylation step and the addition of a phosphocholin moiety in the Kennedy pathway, leads to the formation of the glycerol-phosphatidylcholins PC aa C40:5 and PC aa C40:6, respectively. Thus, a decrease of the ratio PC aa C40:5/PC aa C40:6 indicates an increase in the polyunsaturated fatty acid C22:6. The index "polyunsaturated fatty acids" is defined by the food groups "meat (except sausage)", "poultry" and "fish". Among these groups the strongest association could be found for fish intake with the ratio PC aa C40:4/PC aa C40:6 (q-value: 8.67x10 -10 ).

The indices "saturated fatty acids" and "monounsaturated fatty acids" are both composed of the eight food groups "meat (except sausage)", "sausages and ham", "poultry", "chocolate, chocolates", "cakes, pastries, biscuits", "salted snacks", "cheese" and "eggs". This nearly identical composition of these both indices is typical for southern German (Bavarian) lifestyle [START_REF] Winkler | Trends in dietary sources of nutrients among middleaged men in southern Germany. Results of the MONICA Project Augsburg: dietary surveys 1984/1985 and 1994/1995. MONItoring trends and determinants in CArdiovascular disease[END_REF]. The index "saturated fatty acids" in addition contains the food group "curds, yoghurt, sour milk". Both indices associated with metabolite ratios composed of the different phospholipids.

Three of the index defining food groups, namely "sausages and ham", "chocolate, chocolates" and "cheese", achieved results with a q-value lower than 5%. The resulting ratios mainly describe the state of saturation of the fatty acid residues of the glycero-phosphatidylcholines.

The index "saturated fatty acids" includes, besides the eight food groups, additionally the factor "curds, yoghurt and sour milk". This difference to "monounsaturated fatty acids" became apparent in additionally resulting ratios containing the sphingomyelin SM (OH) C20:1, which was, among the food groups, only included in the results of "curds, yoghurt and sour milk".

The indices "saturated fatty acids" and "monounsaturated fatty acids" present a complex pattern of differences in the phospholipid metabolism, which is probably due to the large number of food compounds defining these indices suggesting that these indices may need refinement in the future. In summary, especially the analysis of the index "polyunsaturated fatty acids" provides an impressive example that the self-reported nutrient intake can in fact be observed in the metabolite profile of human serum.

Dietary lifestyle can be detected in serum metabolite profile

To identify the major dietary patterns in the KORA F3 dataset, we analyzed the food groups by principal component analysis (Table 4). Seven of the resulting principal components achieved an eigenvalue larger than one and were further analyzed. Each of the seven principal components can be interpreted as a dietary pattern (DP). The association of these seven DPs with the metabolite dataset was tested. Three of the seven DPs yielded results with a false discovery rate (q-value) lower than 0.05. The lowest q-value was achieved by the first principal component. This first component was composed of a high intake of poultry, fish, rice, cooked vegetables, fresh fruit, chocolate, flaked oats, curds, cheese and milk, and a low consumption of meat and sausages. The metabolite ratios that most strongly associate with this DP consisted each of a diacyl-PC with four or five double bonds in the numerator and an acyl-alkyl-PC with one or two double bonds in the denominator and showed a positive correlation. This fact is particularly visible when examining the ratio of the sums of these both groups of glycero-phosphatidylcholines for analysis (q-value: 1.07x10 -8 ) (Figure 4, Table 5).

The fourth and the sixth DP were both associated with different phospho-lipids. The fourth DP describes a lifestyle that incorporates a high consumption of meat, poultry, fish, salted snacks and eggs and a low intake of potatoes, pasta, cakes, whole-grain bread and flaked oats (lowest q-value for association with metabolite ratios: 3.42x10 -3 ). It can be interpreted as "traditional Bavarian" lifestyle, since meat, sausages, poultry and fish played an important role in the nutrition (note that the probands live in Bavaria). The sixth DP indicates a high intake of whole-grain bread, eggs and milk, and a low consumption of fish, fresh fruit and cakes (lowest q-value: 1.35x10 -5 ). These three principal components (component one, four and six) explain a variance of 15.6, 7.9% and 6.0% respectively. Because of its high explained variance the first principal component was of main interest. The first DP associates with a decrease in saturation of the fatty acid side chains of glycero-phosphatidylcholines. Thus, the principal component that explains most of the variance in the self-reported dietary intake is also the variable that displays the strongest association to serum measured profiles.

DISCUSSION

In this study we asked the question if self-reported nutrition intake reflects de facto changes in body metabolite composition. We analyzed the effect of different nutrition habits on the metabolism of 239 male participants of the KORA project, aged between 55 and 79 years. In total, 363 metabolites were measured for each sample by high-throughput electrospray ionization tandem mass spectrometry.

Our analysis shows that self-reported information about general nutrition habits collected by food frequency questionnaires can be associated with different metabolic profiles. This could be done for a population study, which means that food intake was not predetermined as it is for clinical short-term studies. Apart from that the associations could be found though the time points of the interview and the blood collection differed by a year. This, in reverse, indicates that nutrition habits are stable over longer time periods. We could find associations between self-reported nutrition intake and serum based metabolite concentrations on three levels of analysis: single food groups, nutrition indices and dietary patterns. Using age and BMI as cofactors for the linear regression showed no substantial difference to the analysis without any cofactors. Life-style factors as well as possible gene-nutrition interactions may influence the relationship between nutrition intake and metabolic profile, but were not used as cofactors for reasons of possible over-fitting of the statistical model.

Analyzing the 18 single food groups we showed that even on the lowest level, namely single food groups, self-reported information about these single food consumptions can be associated with different metabolic profiles. Most of these differences relate to the saturation and chain length of different classes of phospholipids.

In a next step we combined single food groups into indices according to their nutrient content and showed that nutrition habits can be associated with metabolic changes and thereby provide additional information. For the index "dietary fibers", we observed an association with a shift towards more saturation and smaller chain length of the fatty acid residues of phosphatidylcholins. To the best of our knowledge, such an effect of dietary fiber consumption on the saturation of fatty acid residues in humans was not reported in literature so far. Thus, the observed association was unexpected and confounding by other aspects of diet can not totally be excluded. An explanation for the association might be that increased dietary fiber intake functions as an indicator for increased carbohydrate intake, which was observed to be directly correlated to adipose tissue monounsaturated fatty acids [START_REF] Rubba | Influence of dietary intake of energy and carbohydrate on the proportion of saturated and monounsaturated fatty acids in adipose tissue of middle aged men[END_REF]. This association between dietary fiber intake and saturation was stronger than any of the associations between the food compounds that build this index and the metabolic data. This shows that additional information can be extracted from the data by using nutrition indices compared to food groups. For instance, the index "polyunsaturated fatty acids" was associated with a decrease in saturation of the fatty acid side chains of the glycero-phosphatidylcholines. This provides a convincing example that the self-reported increased intake of polyunsaturated fatty acids can be observed in the serum as an increase in glycero-phosphatidylcholins containing polyunsaturated fatty acids. Applying a principal component analysis to all food groups to identify dietary patterns the effect of the overall diet on the human metabolism was

shown. The dietary pattern with the largest explained variance can be compared to a similar pattern found by Liu et al. [START_REF] Liu | Dietary pattern, the metabolic syndrome, and left ventricular mass and systolic function: the Multi-Ethnic Study of Atherosclerosis[END_REF] in a multi-ethnic US population, who denote this pattern as "health conscious". This lifestyle may be interpreted as "healthy", basically since meat and sausages are replaced by poultry and fish. It was strongly associated with aas healthy considereddecrease in saturation of the fatty acid side chains of glycerophosphatidylcholines. Thus, the self-reported healthy lifestyle including a high content of consumed fish and poultry can effectively be detected in the human blood and this even months or years after the report.

The associations we reported in this paper were found in a metabolite set that contained no free fatty acids, but glycerophospholipids. It is true that using free fatty acids would provide additional information. Here, however, we use a high-throughput technology that allows the measurement of hundreds of metabolites in a fully automated manner for many samples at a time which is more appropriate for future large population studies. Moreover, the different phospholipid species are not only meant as substitutes for free fatty acid profiles, but carry much independent information e.g. on lipid trafficking, membrane composition and others [START_REF] Wenk | The emerging field of lipidomics[END_REF]. Also discussable is that as study participants only older men were chosen who may not be as good informed about their nutrition intake as their wives. This selection is due to the fact that our study originated from an explorative metabolomics study with multiple objectives. However, the fact that we still obtain a significant signal under more unfavourable conditions supports the validity of our results.

For our analysis we used information about food frequencies and not about portion sizes of food. Of course, using portion sizes would be a more precise way to assess nutrition intake.

However, in the setting of an epidemiological examination, the questionnaires are limited by the very nature of this kind of large scale population studies. The fact, that we obtain significant results despite this limitation shows again the power of this approach.

In summary, we have shown that metabolomics provides the possibility to evaluate and improve questionnaires and to detect which single foods should be chosen to compose a meaningful nutrition index. This, again, may improve future questionnaire-based studies on human health. Beyond this, metabolomics might be a future tool to identify biomarkers reflecting the effect of nutrition intake on the human metabolism. Such dietary biomarkers could then be an objective and independent assessment for the "true" food intake [START_REF] Day | Epidemiological assessment of diet: a comparison of a 7-day diary with a food frequency questionnaire using urinary markers of nitrogen, potassium and sodium[END_REF][START_REF] Kaaks | Uses and limitations of statistical accounting for random error correlations, in the validation of dietary questionnaire assessments[END_REF][START_REF] Sugar | Logistic regression with exposure biomarkers and flexible measurement error[END_REF]. In addition, other dietary assessment methods (than questionnaires) [START_REF] Bingham | Biomarkers in nutritional epidemiology[END_REF][START_REF] Potischman | Biomarkers of nutritional exposure and nutritional status: an overview[END_REF][START_REF] Tasevska | Urinary sucrose and fructose as biomarkers for sugar consumption[END_REF] could be validated using metabolic biomarkers. of the sum of all acyl-alkyl-PC with one or two double bonds on their fatty acid residues divided by the concentrations of the sum of all diacyl-PC with four or five double bonds as a function of dietary fiber intake. The linear regression q-value for the association is 2.45x10 -7 .

FIGURES AND TABLES

Boxes extend from 1 st quartile (Q 1 ) to 3 rd quartile (Q 3 ); median is indicated as a horizontal line; whiskers are drawn to the observation that is closest to, but not more than a distance of the ratio PC aa C40:5/PC aa C40:6 (legend see Fig. 2; q-value: 5.94x10 -5 ). The principal components with an eigenvalue larger than one are listed together with their explained variance. The "x" indicates that the index is deduced from the respective food.

  metabolites were measured in plasma: 18 amino acids, nine reducing mono-, di-and oligosaccharides (abbreviated as Hn for n-hexose, dH for desoxyhexose, UA for uronic acid, HNAc for N-acetylglucosamine), 21 acylcarnitines (Cx:y, where x denotes the number of carbons in the side chain and y the number of double bonds), seven hydroxylacylcarnitines (C(OH)x:y) and dicarboxylacylcarnitines (Cx:y-DC), free carnitine (C0), seven biogenic amines, seven prostaglandins and 293 lipids. These lipids are subdivided into 14 different ceramides (Cer) and glucosylceramides (GlcCer), 71 different sphingomyelins (SMx:y) and sphingomyelin-derivatives, such as N-hydroxyldicarboacyloylsphingosyl-phosphocholine (SM(OH,COOH)x:y) and N-hydroxylacyloylsphingosyl-phosphocholine (SM (OH)x:y), five glycero-phosphatidic acids (PA), 124 glycero-phosphatidylcholines (PC), 42 glycerophosphatidylethanolamines (PE), four phosphatidylglycerols (PG), 30 glycerophosphatidylinositols (PI) and glycero-phosphatidylinositol-bisphosphate (PIP2), and three glycero-phosphatidylserines (PS). Glycero-phospholipids are further differentiated with respect to the presence of ester (a) and ether (e) bonds in the glycerol moiety, where two letters (aa, ae, or ee) denote that the first as well as the second position of the glycerol unit are bound to a fatty acid residue, while a single letter (a or e) indicates a bond with only one fatty acid residue; the latter molecular species are usually called lyso-phospholipids. E.g. PC ae 36:1 denotes a plasmalogen phosphatidylcholine with 36 carbons in the two fatty acid side

Figure 1 :

 1 Figure 1: Overview over different perspectives for analyzing complex diseases:

Figure 2 :

 2 Figure 2: Dietary fibers associate with an increase in saturation of the fatty acid residues of

1. 5 (

 5 Q 3 -Q 1 ) from the end of the box. Observations that are more distant than this are shown individually on the plot. The number of individuals in each group is given in the boxes.

Figure 3 :

 3 Figure 3: Polyunsaturated fatty acid intake associates with a decrease in the concentration of

Figure 4 :

 4 Figure 4: First principal component generated by principal component analysis on all food

Table 1 :

 1 Characteristics of the population related to nutrition habits and age. The foods were queried in a food frequency questionnaire by a score from 1 to 7: "never", "once a month or less", "several times a month", "about once a week", "several times a week", "daily or almost daily", "several times per day".

		Minimum	Maximum	Mean	Standard deviation	Variance
	Meat (except sausage)	2	6	3.09	.818	.670
	Sausages, ham	1	7	2.86	.932	.868
	Poultry	2	7	4.75	1.165	1.357
	Fish	1	7	4.69	1.113	1.239
	Potatoes	1	7	3.17	.906	.821
	Pasta	2	7	3.43	.830	.689
	Rice	2	7	4.69	1.219	1.487
	Vegetables, cooked	1	7	3.38	.951	.905
	Fresh fruit	1	7	2.59	1.178	1.388
	Chocolate, chocolates	1	7	4.67	1.738	3.022
	Cakes, pastries, biscuits	1	7	4.10	1.467	2.152
	Salted snacks	2	7	5.86	1.236	1.527
	Whole-grain bread, black bread, crispbread	1	7	3.33	1.747	3.052
	Flaked oats, muesli, cornflakes	1	7	5.76	1.732	3.000
	Curds, yoghurt, sour milk	1	7	4.07	1.852	3.430
	Cheese	2	7	3.09	1.089	1.186
	Eggs	2	7	4.67	1.166	1.359
	Milk	1	7	4.63	1.978	3.912
	Age	55	79	65.91	6.892	47.506

Table 3 :

 3 Results of the linear regression test with the strongest association to dietary fibers (A); limited to those ratios containing only diacyl-PC (B) and those containing only acyl-alkyl-PC (C).

	A

Table 4 :

 4 Composition of the principal components on the food groups and composition of the food indices. Positive values indicate a positive contribution to the respective compound (analogous for negative values).

ACKNOWLEDGEMENTS

The KORA research platform and the MONICA Augsburg studies were initiated and financed by the Helmholtz Zentrum München, -National Research Center for Environmental Health, which is funded by the German Federal Ministry of Education, Science, Research and Technology and by the State of Bavaria. The KORA study group consists of H.-E. Wichmann (speaker), R. Holle, J. John, T. Illig, C. Meisinger, A. Peters, and their coworkers, who are responsible for the design and conduct of the KORA studies. We gratefully acknowledge the contribution of all members of field staffs who were involved in planning and conducting the MONICA/KORA Augsburg studies. Finally, we express our appreciation to all study participants for donating their blood and time. This work was partially funded by the Federal Ministry of Education and Research within the SysMBo project (project number: 0315494A), by the research consortium GANI_MED (project number: 03IS2061A) and by the Deutsches Zentrum für Diabetesforschung e.V..