Eric Lombardi

Christian Wolf

Oya C ¸eliktutan

Bülent Sankur

Activity recognition from videos with parallel hypergraph matching on GPUs

Keywords:

In this paper, we propose a method for activity recognition from videos based on sparse local features and hypergraph matching. We benefit from special properties of the temporal domain in the data to derive a sequential and fast graph matching algorithm for GPUs.

Traditionally, graphs and hypergraphs are frequently used to recognize complex and often non-rigid patterns in computer vision, either through graph matching or point-set matching with graphs. Most formulations resort to the minimization of a difficult discrete energy function mixing geometric or structural terms with data attached terms involving appearance features. Traditional methods solve this minimization problem approximately, for instance with spectral techniques.

In this work, instead of solving the problem approximatively, the exact solution for the optimal assignment is calculated in parallel on GPUs. The graphical structure is simplified and regularized, which allows to derive an efficient recursive minimization algorithm. The algorithm distributes subproblems over the calculation units of a GPU, which solves them in parallel, allowing the system to run faster than real-time on medium-end GPUs.

Introduction

Many computer vision problems can be formulated as graphs and associated algorithms, since graphs provide a structured and flexible way to inject spatial and structural relationships into matching algorithms. In this paper, it is employed for recognition and localization of actions in videos. The task to detect and localize activities in time and in space and to classify them requires dealing with large quantities of video data in real time.

We formulate the activity recognition task as a correspondence problem between sparse features of short duration model actions and those of longer duration scene videos. The articulated nature of human motions makes it impossible to employ rigid transformations and methods (like RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]), while graph matching is able to cope with such non-rigid deformations. The proposed method structures space-time interest points into graphs or hypergraphs using proximity information, as is frequently done in the context of visual recognition (object or activity recognition). The optimal matching between a model video and a scene video is cast as a combinatorial problem to minimize a function containing terms measuring differences in appearance features as well as terms adressing space-time geometric distortions in the matching.

Despite advances in graph matching due to its popularity and effectiveness, it still remains a challenging task. The computational complexity renders the use of the exact problem on data having a large number of nodes, e.g. video data, intractable in practice. Formulations useful in vision are known to be NP-hard: while the graph isomorphism problem is conjectured to be solvable in polynomial time, it is known that exact subgraph matching is NP-hard [START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF], and so is subgraph isomorphism [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Graph matching solutions in practical problems therefore are of approximate nature.

Recently, computer vision has immensely benefited from development of general purpose computation on graphical processing units (GPUs). Prominent examples are classification in various applications (e.g. pose estimation [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF]) and convolution operations, for instance in deep learning architectures [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], feature tracking and matching [START_REF] Sinha | Gpu-based video feature tracking and matching[END_REF] and patch based image operations, as for instance inpainting [START_REF] Wang | Accelerating computer vision algorithms using opencl framework on the mobile gpu-a case study[END_REF]. While it is straightforward to profit from parallel architectures if the problem is inherently parallelizable and data-oriented, structured problems are often characterized by complex dependencies which make parallelization of the algorithms difficult. The main inpediments are irregular memory access, tree-based search structures, variable computation and memory units requirement [START_REF] Jenkins | Lessons learned from exploring the backtracking paradigm on the gpu[END_REF].

Whereas most existing work solves the matching problem approximatively, in this work the exact global minimum is calculated, which is made possible by two properties:

• We benefit from two sources, first from the application itself (activity recognition in videos)

and the fact that the data are embedded in space time, in particular from specific properties of the time dimension;

• We approximate the graphical structure and therefore solve a simplified problem exactly and efficiently. The work thus falls into the category of methods calculating the exact solution for an approximated model, unlike methods calculating an approximate solution of an exact problem. In this sense, it can be compared to [START_REF] Caetano | Graphical models and point pattern matching[END_REF], where the original graph of a 2D object is replaced by a k-tree allowing exact minimization by the junction tree algorithm. Our solution is different in that the graphical structure is not created randomly but is derived from the temporal dimensions of video data.

The linearly ordered nature of actions in time allows matching to proceed through a recursive algorithm over time, which is sequential in nature. However, the subproblems corresponding to calculations associated for individual time instants involve iterations over the domains of discrete variables, which are independent. Faster than real-time performance is achieved through a parallel solution of these subproblems on GPUs.

Related work

Graphs and graph matching in computer vision -In computer vision, graph matching has been mainly applied for object recognition, but some applications to action recognition problems have recently been reported. In this context, graphs are frequently constructed from sparse primitives like space time interest points [START_REF] Ta | Recognizing and localizing individual activities through graph matching[END_REF][START_REF] Gaur | A string of feature graphs model for recognition of complex activities in natural videos[END_REF][START_REF] Borzeshi | A discriminative prototype selection approach for graph embedding in human action recognition[END_REF] or from regions and adjacency information gathered from over-segmented videos [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF]. Common matching strategies in this context are off-the-shelf spectral techniques [START_REF] Ta | Recognizing and localizing individual activities through graph matching[END_REF] or dynamic time warping on strings of graphs [START_REF] Gaur | A string of feature graphs model for recognition of complex activities in natural videos[END_REF].

Other graph related work, albeit not necessarily by matching, is based on stochastic Kronecker graphs [START_REF] Todorovic | Human activities as stochastic kronecker graphs[END_REF] for modeling the features pertaining to a specific activity class, chain-graphs [START_REF] Zhang | Probabilistic image modeling with an extended chain graph for human activity recognition and image segmentation[END_REF], weighted directed graphs [START_REF] Li | Expandable data-driven graphical modeling of human actions based on salient postures[END_REF] where nodes are assigned to frames with salient postures or silhouettes that are shared among different action categories. Here, edges encode the transition probabilities between these postures. Salient postures are used for single-view and multi-view action recognition in [START_REF] Lv | Single view human action recognition using key pose matching and viterbi path searching[END_REF]. In [START_REF] Lv | Single view human action recognition using key pose matching and viterbi path searching[END_REF], different actions are linked by chain graphs, called as Action Nets. In [START_REF] Chen | Efficient activity detection with max-subgraph search[END_REF], the test video is first divided into several subvolumes and the maximum subgraph is searched through branch-and-cut algorithms.

Graph matching and graphs are not the only technique successfully employed for activity recognition. A review of the state of the art of this problem is beyond the scope of this paper, we refer the reader to [START_REF] Aggarwal | Human activity analysis: a review[END_REF] for a recent survey.

Solving the graph matching problem -Two different formulations dominate the literature on graph matching: (i) Exact matching: a strictly structure-preserving correspondence between the two graphs or at least between their respective parts is searched; (ii) Inexact matching, where compromises in the correspondence are allowed in principle by admitting structural deformations up to some extent. Matching proceeds by minimizing an objective (energy) function.

Most recent papers on graph matching in the computer vision context are based on inexact matching of valued graphs, i.e., graphs with additional geometric and/or appearance information associated with nodes and/or edges. Practical formulations of this problem are known to be NPhard [START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF], which makes approximations unavoidable. Two different strategies are frequently used: (i) Calculation of an approximate solution of the minimization problem; (ii) Calculation of the exact solution, most frequently of an approximated model.

Approximate solution -A well known family of methods solve a continuous relaxation of the original combinatorial problem. Zass and Shashua [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] presented a soft hypergraph matching method between sets of features that proceeds through an iterative successive projection algorithm in a probabilistic setting. They extended the Sinkhorn algorithm [START_REF] Knight | The sinkhorn-knopp algorithm: Convergence and applications[END_REF], which is used for soft assignment in combinatorial problems, to obtain a global optimum in the special case when the two graphs have the same number of vertices and an exact matching is desired. They also presented a sampling scheme to handle the combinatorial explosion due to the degree of hypergraphs. Zaslavskiy et al. [START_REF] Zaslavskiy | A path following algorithm for the graph matching problem[END_REF] employed a convex-concave programming approach to solve the least-squares problem over the permutation matrices. More explicitly, they proposed two relaxations to the quadratic as-signment problem over the set of permutation matrices which results in one quadratic convex and one quadratic concave optimization problem. They obtained an approximate solution of the matching problem through a path following algorithm that tracks a path of local minimum by linearly interpolating convex and concave formulations.

A specific form of relaxation is done by spectral methods, which study the similarities between the eigen-structures of the adjacency or Laplacian matrices of the graphs or of the assignment matrices corresponding to the minimization problem formulated in matrix form. In particular, Duchenne et al. [START_REF] Duchenne | A tensor-based algorithm for high-order graph matching[END_REF] generalized the spectral matching method from the pairwise graphs presented in [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] to hypergraphs by using a tensor-based algorithm to represent affinity between feature tuples, which is then solved as an eigen-problem on the assignment matrix. More explicitly, they solved the relaxed problem by using a multi-dimensional power iteration method, and obtained a sparse output by taking into account l 1 -norm constraints instead of the classical l 2 -norm. Leordeanu et al. [START_REF] Leordeanu | Semi-supervised learning and optimization for hypergraph matching[END_REF] made an improvement on the solution to the integer quadratic programming problem in [START_REF] Duchenne | A tensor-based algorithm for high-order graph matching[END_REF] by introducing a semi-supervised learning approach. In the same vein, Lee et al. [START_REF] Lee | Hyper-graph matching via reweighted random walks[END_REF] approached this problem via the random walk concept.

Another approach is to decompose the original discrete matching problem into subproblems, which are then solved with different optimization tools. A case in point, Torresani et al. [START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF] solved the subproblems through graph-cuts, Hungarian algorithm and local search. Lin et al. [START_REF] Lin | Layered graph matching by composite cluster sampling with collaborative and competitive interactions[END_REF] first determined a number of subproblems where each one is characterized by local assignment candidates, i.e., by plausible matches between model and scene local structures. For example, in action recognition domain, these local structures can correspond to human body parts. Then, they built a candidacy graph representation by taking into account these candidates on a layered (hierarchical) structure and formulated the matching problem as a multiple coloring problem. Finally, Duchenne et al. [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF] extended one dimensional multi-label graph cuts minimization algorithm to images for optimizing the Markov Random Fields (MRFs). Approximate graphical structure -An alternative approach is to approximate the data model, for instance the graphical structure, as opposed to applying an approximate matching algorithm to the complete data model. One way is to simplify the graph by filtering out the unfruitful portion of the data before matching. For example, a method for object recognition has been proposed by Caetano et al. [START_REF] Caetano | Graphical models and point pattern matching[END_REF], which approximates the model graph by building a k-tree randomly from the spatial interest points of the object. Then, matching was calculated using the classical junction tree algorithm [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF] known for solving the inference problem in Bayesian Networks.

A special case is the work by Bergthold et al. [START_REF] Bergtholdt | A Study of Parts-Based Object Class Detection Using Complete Graphs[END_REF], who perform object recognition using fully connected graphs of small size (between 5 and 15 nodes). The graphs can be small because the nodes correspond to semantically meaningful parts in an object, for instance landmarks in a face or body parts in human detection. A spanning tree is calculated on the graph, and from this tree a graph is constructed describing the complete state space. The A * algorithm then searches the shortest path in this graph using a search heuristic. The method is approximative in principle, as hypotheses are discarded due to memory requirements. However, for some of the smaller graphs used in certain applications, the exact solution can be obtained.

Parallel graph matching -Parallel algorithms have been proposed for the graph matching problem for some time. Although both exact solutions and approximate solutions, can be parallized in principle, most of the existing parallel algorithms have been proposed for approximate solution. Many spectral methods, which are approximative, can be naturally ported to a GPU architecture, as the underlying numerical algorithms require matrix operations. Similar matrix operations are employed in [START_REF] Rodenas | Parallel graduated assignment algorithm for multiple graph matching based on a common labelling[END_REF], where multiple graphs are matched using graduated assignment on GPUs.

Matching two graphs can also be performed by searching the maximum common subgraph of the two graphs [START_REF] Donatello | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF], a problem which can be transformed (in linear time) to the problem of searching the maximum clique of a graph. For this problem parallel and GPU algorithms do exist, albeit not very efficient ones [START_REF] Jenkins | Lessons learned from exploring the backtracking paradigm on the gpu[END_REF].

Parallel and GPU algorithms for bi-partite matching have been proposed recently [START_REF] Vasconcelos | Bipartite graph matching computation on gpu[END_REF][START_REF] Kollias | Fast parallel algorithms for graph similarity and matching[END_REF]. Bipartite matching is, however, different and less difficult, as polynomial time algorithms are known for them. These algorithms alternate bidding (proposed assignments) kernels and assignment kernels on the GPU as well as convergence tests on the CPU. A similar problem, unfortunately also called graph matching, matches neighboring vertices of a single graph under unicity constraints. In other terms, a matching or independent edge set in a graph is a set of edges without common vertices. GPU algorithms have been proposed for this kind of problem [START_REF] Auer | A gpu algorithm for greedy graph matching[END_REF].

Problem Formulation

Detecting, recognizing and localizing activities in a video stream is cast as a matching problem between a scene video, which can be potentially long or short if the data is processed block-wise in a stream, and a dictionary of relatively much shorter model videos describing the set of activities to recognize. Matching is done by pairs, solving a correspondence problem between the scene video and a single model video at a time. We formulate the problem as a particular case of the general correspondence problem between two point sets with the objective of assigning points from the model set to points in the scene set, such that some geometrical invariance is satisfied. In particular, videos are represented as space-time interest points -see Figure 1a for examples of successful matchings between model point sets and scene point sets. Each point is described by its location in space-time and appearance features, i.e., a descriptor locally representing the space-time region around the point.

The M points of the model are organized as a hypergraph G={V, E}, where V is the set of nodes (corresponding to the points) and E is the set of edges. Let us recall that hypergraphs are a generalization of graphs, where edges, often called hyperedges, can link any number of nodes, generally >2. The set of scene nodes is not structured.

Each node i of the model graph is assigned a discrete variable z i , i = 1..M , which represents the mapping from the i th model node to some scene node, and can take values in 1..S, where S is the number of scene nodes. We use the shorthand notation z to denote the whole set of map variables z i . A solution of the matching problem is given through the values of the z i , where z i =j, i=1..M , is interpreted as model node i being assigned to scene node j = 1..S. Each combination of assignments z evaluates to an energy value in terms of the following energy function E(z):

E(z) = λ 1 i U (z i ) + λ 2 (i,j,k)∈E D(z i , z j , z k ) (1)
Here, U is a data attached term taking into account the distance between appearance features of point i and its assigned point z i , D is the geometric distortion between the space-time triangle associated with hyperedge (i, j, k) and the triangle associated with (z i , z j , z k ), and λ 1 and λ 2 are weights. For convenience, dependencies on all values over which we do not optimize have been omitted from the notation. U is defined as the Euclidean distance between the appearance features of assigned points in the case of a candidate match, and it takes a penalty value W d for dummy assignments which handle situations where a model point is not found in the scene:

U (z i ) = W d if z i = , ||f i -f z i || else, (2)
f i and f z i being respectively the feature vector of model point i, and the feature vector of scene point z i . The D term is based on angles. Since our data is embedded in space-time, angles include a temporal component not related to scale changes induced by zooming. We therefore split the geometry term D into a temporal distortion term D t and a spatial geometric distortion term D g , weighted by a parameter λ 3 :

D(z i , z j , z k ) = D t (z i , z j , z k ) + λ 3 D g (z i , z j , z k ) (3)
where the temporal distortion D t is defined as time differences over two pairs of nodes of the triangle:

D t (z i , z j , z k ) = ∆(i, j) + ∆(j, k) (4)
with:

∆(i, j) = |(t(i) -t(j)) -(t (z i ) -t (z j ))| (5)
Here, ∆(i, j) is the time distortion due to the assignment of model node pair (i, j) to scene node pair (z i , z j ). The temporal distortion term penalizes the discrepancy in the extent of time between model node pairs and the corresponding scene node pairs. The model node pairs should not be too close or too far from each other likewise the scene node pairs. Finally, D g is defined over differences of angles:

D g (z i , z j , z k ) = a(i, j, k) -a (z i , z j , z k ) a(j, i, k) -a (z j , z i , z k ) . (6)
Here, a(i, j, k) and a (z i , z j , z k ) denote the angles subtended at point j for, respectively, model triangle indexed by (i, j, k) and scene triangle indexed by (z i , z j , z k ). . is the L2 norm. The difference between angles takes into account the circular domain of angles.

Approximations

In the context of activity recognition, the geometric data are embedded in space-time. We make the following assumptions relative to the temporal domain to derive an efficient minimization algorithm: Assumption 1: Causality -While objects (and humans) can undergo arbitrary geometrical transformations like translation and rotation, which is subsumed by geometrical matching invariance in our formulation, human actions can normally not be reversed. In a correct match, the temporal order of the points should be retained, which can be formalized as follows

∀ i, j : t(i) ≤ t(j) ⇔ t (z i ) ≤ t (z j ) (7)
where the notation t(i) stands for the temporal coordinate of model interest point i, and t (z i ) stands for the temporal coordinate of scene interest point z i . Assumption 2: Temporal closeness -Another reasonable assumption is that the extent of time warping between model and scene time axes must be limited. In other words, two points which are close in time must be close in both the model set and the scene set. Since our graph is created from proximity information (time distances have been thresholded to construct the hyperedges), this can be formalized as follows:

∀ i, j, k ∈ E : |t (z i ) -t (z j )| < T ∧ |t (z j ) -t (z k )| < T ( 8
)
where T is a parameter.

We have shown in [START_REF] Celiktutan | Fast exact hyper-graph matching for spatiotemporal data[END_REF], that this problem can be solved in polynomial time if the data are embedded in space-time, as opposed to the general class of problems, which is NP-hard [START_REF] Torresani | Feature correspondence via graph matching: Models and global optimization[END_REF].

Due to the sequential nature of activities, graphs obtained from data embedded in space-time are generally elongated in time, i.e. the graphical structure is heavily influenced by the temporal order of the nodes. This is particularly true in the case of graphs constructed from space time interest points, which are commonly very sparse. Typical interest point detectors extract only few such points per frame -typically between 0 and 5 [START_REF] Laptev | Learning realistic human actions from movies[END_REF]. We take advantage of this observation to restrict the model graph by keeping only a single interest point per model frame. This is done by choosing the most salient one, i.e., the one with the highest confidence of the interest point detector.

We also restrict the set E of model graph edges to connections of each model point i to its two immediate frame-wise predecessors i -1 and i -2 as well as to its two immediate successors i + 1 and i + 2. This creates a planar graph with triangular structure, as illustrated in Figure 1b. A video is described by the way this planar graph twists in space time, as well as the appearance features associated with each node. According to the visual content of a video, there may be frames which do not contain any space time interest points, and therefore no nodes in the model graph. These empty frames are not taken into account, e.g. in Equation ( 8), when triplets of consecutive frame numbers are considered.

Minimization

The neighborhood system of this simplified graph can be described in a very simple way using the node indices of the graph, similar to the dependency graph of a second order Markov chain. The general energy given in (1) can therefore be expressed simpler as follows:

E(z) = M i=1 U (z i ) + M i=3 D(z i , z i-1 , z i-2 ) (9)
where we also have absorbed λ 1 and λ 2 into U and D, respectively. The elongated form of the graph allows us to derive an efficient inference algorithm for calculating z = arg min z E(z) based on the following recursion:

α i (z i-1 , z i-2 ) = min z i U (z i ) + D(z i , z i-1 , z i-2 ) + α i+1 (z i , z i-1 ) (10)
with the initialization

α M (z M -1 , z M -2 ) = min z M [U (z M ) + D(z M , z M -1 , z M -2 )] (11)
During the calculation of the trellis, the arguments of the minima in Equation ( 10) are stored in a table

β i (z i-1 , z i-2 ).
Once the trellis is completed, the optimal assignment can be calculated through classical backtracking:

z i = β i (z i-1 , z i-2 ), (12)
starting from an initial search for z 1 and z 2 :

( z 1 , z 2 ) = arg min z 1 ,z 2 [U (z 1 ) + U (z 2 ) + α 3 (z 2 , z 1 )] (13)
The computational complexity and the memory complexity of the algorithm are defined by the trellis, a M ×S×S matrix, where each cell corresponds to a possible value of a given variable. The calculation of each cell requires to iterate over all S possible combinations of z i . It is easy to see that the computational complexity is O(S 3 M ) and that the memory complexity is O(S 2 M ).

Exploiting the different assumptions on the spatio-temporal data given above, the computational complexity can be decreased further. A large amount of combinations from the trellis can be pruned applying the following constraints:

• given variable z i , all values for its predecessors z i-1 and z i-2 must be necessarily before z i , i.e. lower.

• given variable z i , we will allow a maximum number of T possibilities for the values of the successors z i+1 , z i+2 , which are required to be close.

These pruning measures decrease the complexity to O(SM T 2 ), where T is a small constant measured in the number of frames. Since T is a small constant, the computational complexity therefore becomes linear on the number of points in the scene: O(SM ).

Let us note that no such prior pruning is applied to the scene frames, which therefore may contain an arbitrary number of points. At a first glimpse it could be suspected that the single-pointper-frame approach could be too limited to adequately capture the essence of an action sequence. Experiments have shown, however, that the single chain performs surprisingly well. It should be noted again, that no restrictions have been imposed on the scene, in other words, none of the scene points have been eliminated.

A parallel solver for GPUs

Solving the matching problem requires computing Equations ( 11), ( 10), ( 12) and ( 13). However, the computational and memory complexity are dominated by the requirement to solve (10) for different indices i and for different combinations of z i-1 and z i-2 , which boils down to filling a three dimensional array with values, taking into account certain dependencies between these values. In the following section we will present a parallel solver for this problem designed for modern GPUs. Although the system has been implemented using the hardware independent OpenCL library, we kept the description as library independent as possible. For this reason, and to make the paper selfcontained, we first define some common terms (and refer to Figure 2 for a block scheme of modern GPU architecture):

Kernel -a kernel is a piece of code which is executed by the GPU in parallel on several independent hardware units;

Work-item -

GPU CPU RAM

Figure 2: The architecture of a CPU+GPU system as seen by the hardware independent OpenCL library.

Given the restrictions of memory access and execution on the GPU, parallel algorithms follow a classical three-step process:

• transfer data from RAM to global GPU memory;

• eventually transfer data from global GPU memory to different local GPU memory banks;

• execute the kernel multiple times in parallel on the GPU;

• transfer results from GPU memory to RAM Dependencies between results may require more complex schemes and/or multiple iterations of this process.

z i ∈ [1, S] → z i-2 ↓ α i+1 α i z i-1 ∈ [1, S] → z i-1 ∈ [1, S] ↓ ∈ [1, S] = min zi∈[1,S] (f (z i-2 , z i-1 , z i ) + α i+1 (z i , z i-1 )
Figure 3: A visualization of the 3D trellis of Equation ( 10) as a series of 2D tables of size S×S. Each cell in table α i is a result of a minimization operation taking as input results from a row in table α i+1 .

Defining the GPU kernel

The recursion on i in Equation ( 10) produces (and works on) a 3D structure with 3 coordinates : i, z i-1 , z i-2 . Here, i is the model frame/node index, which can also be interpreted as a temporal coordinate, and which takes values in {1..M }; z i-1 and z i-2 are assignment variables which can each take values in {1..S}. It is convenient to visualize this trellis as a series of 2D tables, as illustrated in Figure 3. The kernel code will execute the minimization in Equation [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF], where a single work-item deals with a triplet of parameters given by i, z i-1 and z i-2 . Accordingly, a total number of M S 2 kernel executions (work-items) is required to fill the trellis. The dependencies in Equation ( 10) make it impossible to execute all kernels in parallel: it is easy to see, that a full row in α i+1 is required as input for each cell in α i . A scheduling is needed, which executes kernels in parallel with a block-wise sequential ordering, insuring that a whole α i+1 row is available, before the corresponding cell in α i is executed. This scheduling could theoretically be done by the kernel itself through synchronization points. However, kernel-wise synchronization is only possible for work-items of the same work-group. The amount of workitems in the studied problem (M S 2 ) makes it unreasonable to use a single work-group for the whole problem. Indeed, convenient values are M=30 and S=60. This corresponds to 1 seconds of model video and 2 seconds of scene video at 30 frames per second, using one node per frame. The amount of work items involved in the matching of the model graph to the scene graph, M S 2 , is then 108000. This value is far above the capacity of even a high end GPU like the GTX580, where a workgoup is limited to 1024 work items. If we match a model against larger blocks of the scene, for instance entire videos, then this value will be even higher (see also table 2 for comparisons of two different scenarios with S=754 and S=60).

A different solution is to perform synchronization through the CPU, i.e. launch parallel executions of a single array α i+1 on the GPU with the CPU taking over control between iterations over i. In other words, at the end of the kernel execution, the fall back to CPU execution acts as a syn- chronisation point for all work-items. Note, that the resulting scheduling is not different; a slight performance loss is due to the control flow change between the GPU and the CPU. This leads to a two-dimensional kernel, the dimensions being z i-1 and z i-2 . A single loop in the kernel iterates over z i to perform the minimization operation in (10).

T z i-2 i z i-1

Pruning the trellis

The causality assumption [START_REF] Caetano | Graphical models and point pattern matching[END_REF] and the temporal closeness assumption (8) restrict the admissible combinations of z i , z i-1 and z i-2 , and therefore allow us to prune combinations in the trellis. In particular, for a given value of z i-1 , the value of z i-2 is restricted to the interval ]z i-1 -T, z i-1 [. This limits the admissible values of the trellis to a cross section of size ∼ S×T in the 3D volume, as illustrated in Figure 4. The validity tests for these constraints are precomputed and stored in a boolean array. A similar reasoning restricts the values of z i , c.f section 3.4.

Precomputing the unary terms

The complexity of the unoptimized kernel is dominated by the calculation of the unary terms U (z i ), which are calculated in each iteration of the minimization loop, and which correspond to the Euclidean distance between the feature vector of a model node and the feature vector of a scene node. The size F of the appearance feature vector may vary, common sizes are 50 to 200 components (162 in the case of our HoG/HoF features). Assumptions ( 7) and ( 8) decrease the part of U for a work-item from O(F S), to O(F T ), where T ≤S (see also sub section 3.4). The unoptimized computational complexity for a whole array α i is O(F ST 2 ) and for the whole trellis it is O(F SM T 2 ). Another way to derive the same result is to consider that each minimization in equation [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] takes place over T iterations, that the minimization is performed SM T times (c.f. the blue cross section in figure 3), and that one term is of O(F ).

The unary terms take as input the model node and scene node. Therefore, out of the SM T 2 calls to U , only SM different input arguments exist, which can be pre-calculated on the GPU by a separate kernel. The pre-computed unary terms are stored in a look-up table of size S × M in the GPU global memory. They are later used by the main GPU kernel, which calculates one α i array. When the α i kernel evaluates the matching of model node i to scene node z i , it reads the corresponding pre-computed value of U in the look-up table.

z i → z i-1 ↓ α i+1 z i-1 → z i-2 ↓
Precomputing U for all combinations of model nodes and scene nodes saves T 2 calls to U . The pre-computations themselves can be done in O(F SM ), so total computational complexity is reduced from O(F SM T 2 ) to O(SM T 2 + F SM ). For typical values of T =10 and F =162, the speed up factor is ∼ 61.

Precomputing the minimization loop boundaries

The minimization loop involved in equation ( 10) is executed inside each kernel. During one kernel execution, i.e. for one work-item, z i-1 and z i-2 have a fixed value. The loop is then executed over z i , whose value are limited by z i-1 and z i-2 , according to causal constraint [START_REF] Caetano | Graphical models and point pattern matching[END_REF] and temporal closeness constraint [START_REF] Celiktutan | Fast exact hyper-graph matching for spatiotemporal data[END_REF]. Applying the two constraints above and performing some algebraic simplifications results in two equations involving z i :

t (z i ) ≥ t (z i -1) t (z i ) < t (z i -2) + T (14)
Equations ( 14) define an interval in temporal coordinates, which needs to be translated into an interval in scene nodes. Let us recall that the minimization in equation ( 10) is over possible scene nodes. As opposed to model graphs, scenes can feature multiple nodes per frame, as illustrated in figure [START_REF] Brendel | Learning spatiotemporal graphs of human activities[END_REF]. This distribution of nodes over frames can be pre-calculated and stored in a table:

minnode(f ) = inf({n : t (n) = f }), n = 1...S
where minnode(f ) gives the first node of a given scene frame f , assuming that the scene nodes are sorted in temporal (i.e. frame) order. Then, the boundaries of the minimization loop in equation ( 14) can be directly derived as follows:

   min(z i )=minnode(t (z i-1 )) max(z i )=minnode(t (z i-2 ) + T ) -1
where we took advantage of the fact that the maximum node of a frame f is equal to minnode(f + 1) -1. Function minnode(.) only depends on the distribution of the nodes in the scene. It can be pre-computed for each scene block, stored in GPU memory, and then shared by all work-items. Algorithm 1: The kernel executed for each work-item.

Kernel

Copy a cell of α i+1 from global mem. to local mem.; Wait for synchronization between all work-items; Compute one cell of array α i (minimization in ( 10)); end

Work-groups and local GPU memory

Local GPU memory (NVidia "shared memory" or OpenCL "local memory") offers faster access than global GPU memory. Local memory is associated to a work-group, i.e., only work-items of this work-group can access it. Read and write operations to local memory can be synchronized between work-items of a single work-group. The goal is to optimize performance by performing a single transfer from global memory to local memory, followed by several accesses to local memory directly done by the kernels executions. Efficiency is guaranteed by organizing work-groups such that work-items can share common data.

As illustrated in Figure 5, all cells of a single column of an array α i depend on the same row of array α i+1 . This can easily be derived from the recursive Equation ( 10): calculating one column α i (z i-1 , z i-2 ) for fixed i and z i-1 requires the values α i+1 (z i , z i-1 ) for fixed i + 1 and z i-1 over varying z i , which corresponds to a row in the precedently calculated array. This naturally leads to a configuration where one column of the currently calculated array α i is organized in a single work-group, where the column corresponds to the expression α i (z i-1 , z i-2 ) for fixed i and z i-1 .

The memory transfer of a whole row for a single workgroup is distributed over its work-items. As all tables α i are of square shape (the number of columns equals the number of rows), a single value is transferred by each work-item at the beginning of the kernel execution. After a synchronisation point, the minimization routine itself is executed. This results in the kernel structure given in Algorithm 1. As a result, S 2 read operations from slow global memory per work-group have been replaced by S read operations from global memory plus S 2 read operations from fast local memory. The total number of operations slightly grows by a small factor of (S + S 2 )/S 2 , which in practice is smaller than 1.017 for the configuration we employed (S=60). However, the total access time decreases due to faster memory accesses.

Algorithm 2: The CPU side algorithm.

Copy full data from RAM to global GPU memory; for i=M to 1 do

In parallel do Compute array α i on GPU (run kernel); if i<M then Copy array α i+1 from GPU to RAM; end end end Copy array α 1 from GPU to RAM;

GPU memory persistence

All model and scene data must be transfered from the CPU controlled RAM to the GPU, and hardware constraints force a transfer to global GPU memory. Let us recall that after a parallel computation of an array α i , execution falls back to the CPU, which controls the iterations over the different arrays α i for different indices i. This could potentially involve a large number of memory transfers between CPU RAM and global GPU memory, as data needs to be exchanged between the CPU and the GPU before and after each iteration.

Data is persistent in global GPU memory between kernel executions, which can be exploited to minimize the number of memory transfers. The full model data and the currently processed scene block are initially entirely transferred to the global GPU memory, and stay persistent between iterations over the tables α i . The α i arrays also stay in GPU memory between successive kernel executions.

Parallelizing calculations and transfer

After calculation of the trellis, the optimal point assignment is calculated with the backtracking step given in Equation ( 12). This step is of very low complexity (a single loop over M iterations) and inherently sequential, therefore it is performed on the CPU. The whole trellis (tables α i (z i-1 , z i-2 ) for i ∈ [1, M ]) must be transferred from global GPU memory to the CPU accessible RAM. Modern GPU architectures provide the ability to parallelize kernel executions and data transfer, which is here exploited to copy the results available in array α i+1 while kernel executions are computing the entries of α i . The CPU side of the matching algorithm is given in Algorithm 2:

Memory structure optimizations

An important concept in efficient computing on most GPU architectures is to ensure coalesced accesses to global GPU memory. Practically, this means that data in the global GPU memory has to be organised in contiguous blocks of multiples of 128 bytes to maximize access rate inside workitems. As a whole row of table α i+1 needs to be read for each cell (work-item) in α i , we store the different tables α i in row order.

Computational complexity and run-time

As mentioned in section 2.2, taking advantage of all approximations results in a computational complexity of O(SM T 2 ), where T is a small constant (T =10 in our experiments). However, that

Experimental Results

The presented matching algorithm has been evaluated on a real-world application, namely action recognition in video sequences. The widely used public KTH database [START_REF] Schuldt | Recognizing human actions: a local svm approach[END_REF] has been chosen as test dataset. It contains 25 subjects performing 6 actions (walking, jogging, running, handwaving, handclapping and boxing) recorded in four different scenarios including indoor/outdoor scenes and different camera viewpoints, totally 599 video sequences (one is corrupted). The subdivision of the sequences is the same as the one provided on the official dataset website 1 . This results in 2391 subsequences in total.

The images of the KTH database are of size 160x120. However, only the preprocessing steps depend on the image size, the complexity of the matching algorithm itself is independent of it.

We use spatio-temporal interest points extracted with the 3D Harris detector [START_REF] Laptev | Learning realistic human actions from movies[END_REF] to constitute the nodes of the graph. Appearance features are the well-known HoG-HoF features extracted with the publicly available code in [START_REF] Laptev | Learning realistic human actions from movies[END_REF]. The weighting parameters are set so that each distortion measure has the same range of values:

λ 1 =0.6, λ 2 =0.2, λ 3 =5, T =10 (λ 3 is explained in the appendix).
All experiments use the leave-one-subject-out (LOSO) strategy. We augmented the number of model graph prototypes by selecting different sub-sequences and constructed each graph consisting of 20 to 30 frames containing at least one or more salient interest points. Action classes on the unseen subjects are recognized with a nearest prototype classifier (NPC). The distance between model and prototypes is based on the matching energy given in Equation (1). However, experiments showed that best performance is obtained if only the appearance terms U (.) are used for distance calculation instead of the full energy [START_REF] Aggarwal | Human activity analysis: a review[END_REF].

We learned a set of discriminative prototypes using sequential floating forward search (SFFS) [START_REF] Pudil | Floating search methods for feature selection with nonmonotonic criterion functions[END_REF]: model graph prototypes are created from the training subjects and the prototype selection is optimized over the validation set.

The maximum admissible size of each work-group depends on the GPU itself and on the kernel specifically implemented for the problem. In our case, and for the Nvidia GeForce GTX 560 GPU, the limit is 768 work-items per work-group, which in practise is higher than the number of workitems we need: S=60 if scene blocks of 2 seconds are matched in video streaming mode, and S=754 if whole scene videos of 30 seconds are matched.

Floating point operations on Nvidia GPUs use different rounding algorithms than the FPUs on Intel CPUs, which may results in slightly different values obtained in the trellis. However, this did not impact the recognition results.

We would like to point out that many results have been published on the KTH database, but most of the results cannot be compared due to different evaluation protocols, as has been studied on the detailed report on the KTH database in [START_REF] Gao | Comparing evaluation protocols on the kth dataset[END_REF]. For completeness, we compare our performance with state-of-the-art methods. In Table 1, we report average action recognition performance and computational time for the aforementioned methods in Section 1. The results have been copied from the original papers. Although run-time calculations and used protocols differ between the papers, this table gives an overall idea that our proposed method is extremely competitive in terms The GPU implementation allows faster than real-time performance on standard medium end GPUs, e.g. a Nvidia GeForce GTS450. Table 2 compares run-times of the CPU implementation in Matlab/C (the critical sections were implemented in C) and the GPU implementation running on different GPUs with different characteristics, especially the number of calculation units. The runtimes are given for matching a single model graph with 30 nodes against scene blocks of different lengths. If the scene video is cut into smaller blocks of 60 frames, which is necessary for continuous video processing, real time performance can be achieved even on the low end GPU model. With these smaller chunks of scene data, matching all 50 graph models to a block of 60 frames (roughly 2 seconds of video) takes roughly 3 ms regardless of the GPU model.

We can observe that the results for the three different GPUs (GTS450, GTX560 and GTX580) are identical when models are matched against scenes of 60 nodes. In this case, the number of cuda cores is higher than the amount of requested work items per call, i.e. per frame. Therefore, adding additional cuda cores does not give us an increase in performance. Other architectural differences (frequency, bandwidth) between the video cards are negligible and beyond the precision of time measurement. If we match one model against a whole video (754 frames), which requires much more work items, then the extra amount of cuda cores of the GTX560 and GTX580 cards makes a large difference in performance. The processing time of 3 ms per frame is very much lower than the limit for real time processing, which is 40 ms for video acquired at 25 frames per second. Additional processing will be required in order to treat overlapping blocks, which increases running time to 6 ms per frame. The times given above also do not include interest point detection and feature extraction, but fast implementations of these steps do exist. As mentioned, in our experiments we used Laptev et al's STIP points [START_REF] Laptev | Learning realistic human actions from movies[END_REF], which performed slightly better than other detectors. Its pure CPU implementation requires 82 ms per frame. However, our own implementation of Dollar et al.'s points [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] runs in 2 ms per frame including the detection of HoG features (also on CPU). These run-times can be decreased porting the algorithms to GPU, especially Dollar et al.s detector, which essentially proceeds through linear filtering in time and space. The convolution operations can be easily performed on GPUs.

In table 3, we compare execution times between the CPU implementation of the matching algorithm, and several implementations on GPU, with different types of optimizations. Comparing the CPU version running time (2900 ms) with the non-optimized GPU version (794 ms), we can see that the parallel hardware architecture of the GPU is almost 4 times faster than the CPU. The algorithmically optimized version of the GPU kernel (including optimizations described in sections 3.2, 3.3, 3.4) takes 326 ms to run, and is then 2.4 times faster than the non-optimized version. Finally, the GPU architectural optimizations described in sections 3.5, 3.6, 3.7, 3.8 bring an additional speedup of factor 2 (178 ms vs. 326 ms).

The last line in the same table (table 3) shows a comparison with the fully optimized GPU version without temporal closeness constraint (1853 ms), giving the influence of the restriction of temporal warping. Figure 7 shows this effect of parameter T (restricting temporal warp) on performance. The parameter retained for all other experiments is T =10, and at this configuration we find the value of 178 ms also given in tables 2 and 3. Loosening the restrictions will not only significantly increase computational complexity, it will also decrease recognition performance. The restriction due to the parameter T allows to remove wrong assignments. No restrictions (T = +∞) will lead to a runtime of 1853 ms.

We also performed experiments to check the influence of the restriction to a single interest point per frame. The original formulation given in equation ( 1) is of polynomial complexity, but still too complex to solved in real time. We compared the proposed approximation to two different models allowing several interest points per frame :

Multiple points 1: a greedy approximation of the the full model, where interest points assignments are decoupled from frame assignments. First, for each model frame and for all possible assigned scene frames, the optimal interest point assignments are made based on unary terms U and inter-frame deformation terms D. Then, frames are assigned using the proposed model.

Multiple points 2: creation of several single point models (several second order chains), each of which is solved independently. The resulting matching distance is given as the average over the different chains. More details on these models are given in [START_REF] Celiktutan | Fast exact hyper-graph matching for spatiotemporal data[END_REF]. Results on the KTH are given in table 4. Results of the multiple point methods are comparable, even slightly lower. After investigating the results in detail, we believe that taking into account more points hurts performance because this decreases the invariance properties of the method. Space-time points are naturally very sparse, and taking more points actually leads to including less stable and less robust points.

Conclusion

An efficient parallel algorithm for activity recognition has been presented, which resorts to parallel hypergraph matching on GPUs. The traditional problem of irregular computation flow in graph matching has been addressed by restricting the graph to a regular structure, which allows efficient inference by a recursive function working on a 3D trellis. The values in the trellis are computed in a block-wise parallel manner. The method is competitive with the state of the art in terms of recognition performance while at the same time being faster in several orders of magnitude. The current implementation is faster than real time on medium-end GPUs even though only a part of the computing units are currently used. Further speed-up could be gained by matching a scene video block against several model graphs in parallel and by distributing the cells of the multiple trellis over the computing units of the GPU.

Figure 1 :

 1 Figure 1: Videos are represented through space time interest points: (a) examples of successful matches of space time points from the model video (left) to the scene video (right); (b) model videos are structured into graphs with a specific structure using proximity information.

Figure 4 :

 4 Figure 4: The 3D trellis of size M ×S 2 calculated by the recursive minimization algorithm. The shaded cross-section of size ∼ M ×S×T in the middle corresponds to the admissible combinations of i, z i-1 and z i-2 .

Figure 5 :

 5 Figure 5: Dependencies: one column of array α i is handled by the work-items of the same workgroup. The values of this column depend on a single row of previous array α i+1 .

Figure 6 :

 6 Figure 6: Example of a distribution of scene nodes over scene frames: as opposed to models, scenes may feature multiple nodes per frame. For example, frame 8 has nodes 9, 10 and 11.

Figure 7 :

 7 Figure 7: Performance as a function of parameter T : (a) run-time; (b) classification performance (accuracy). No restrictions (T = +∞) will lead to a runtime of 1853 ms (Nvidia GTX580, 754 scene nodes).

  the execution of a kernel on a single data package is called a work-item;Work-group -work-items can be grouped into work-groups; all work-items of one work-group share data in local memory;

	Work-group
	Work-item
	Local memory
	Global memory
	Global memory -global GPU memory can be accessed by all work-items. It is slower than local
	GPU memory;
	Local memory -local GPU memory is shared by the work-items of the same work-group. It is
	faster than global GPU memory;

RAM -the computer's (classical) main memory used by the CPU. It cannot be directly accessed by work-items, thus code running on the GPU.

Table 1 :

 1 WorkAverage perf. Run-time Evaluation Remarks on run-time Comparison with the state-of-the-art methods on the KTH database (LOOCV = Leaveone-out-cross validation).does not necessarily mean that run-time is a function of O(SM T 2 ), as parallel processing is not yet taken into account. Actual run-time is of course considerably lower. If we consider Q workunits (cores), run-time is of O( ST Q M T ): M kernel calls are launched, each one performing a minimization over T iterations, and each kernel call scheduling ST work-items. In the case where enough work-units are available on the GPU to perform all ST work-items of one call in parallel, i.e. Q ≥ ST , run-time is actually of O(M T ).

	Ta et al. [39]	91.2%	1.86s	LOOCV	s/frame, matching with 98
					model graphs
	Borzeshi et al. [5]	70.2%	N/A	Split 8/8/9
	Brendel & Todorovic [6]	N/A	10s	N/A	Matching 1000 nodes graph
					with 2000+ nodes graph
	Lv & Nevatia [30]	N/A	5.1s	N/A	s/frame
	Savarese et al. [35]	86.8%	N/A	LOOCV
	Ryoo & Aggarwal [34]	93.8%	N/A	LOOCV
	Mikolajczyk & Uemura [31] 95.3%	5.5s to 8s LOOCV	s/frame (-5s if SVM are not
					used)
	Baccouche et al. [3]	95.8	N/A	LOOCV	N/A
	Jiang et al. [19]	93.4%	N/A	LOOCV
	Our method on CPU	91.0%	0.2s	Split 8/8/9	s/frame, matching 754-
					nodes scene with 50 model
					graphs
	Our method on GPU	91.0%	0.02s	Split 8/8/9	s/frame, matching 754-
					nodes scene with 50 model
					graphs
	Our method on GPU	91.0%	0.0035s	Split 8/8/9	s/frame, matching 60-nodes
					scene with 50 model graphs

Table 2 :

 2 Running times in milliseconds for two different GPUs and for two different scene block sizes. The last column on the right gives times per frame for matching the whole set of 50 model graphs. The bold blue value of 178 ms is comparable to the values in table 3.

	Implementation	#Scene #Scene Time/single model	All 50 models
		nodes frames Tot(ms) per fr(ms)	Time/fr (ms)
	CPU: Intel Core 2 Duo,	754	723	2900	4.01 200.5
	E8600 @ 3.33 Ghz,
	Matlab/C(mex)
	Nvidia GeForce GTS450,	754	723	748	1.03	51.5
	192 cuda cores @ 1566 MHz,	60	55	4	0.07	3.5 real time!
	mem bandwidth 21.3 GB/sec
	Nvidia GeForce GTX560,	754	723	405	0.56	28 real time!
	336 cuda cores @ 1660 MHz,	60	55	4	0.07	3.5 real time!
	mem bandwidth 128 GB/sec
	Nvidia GeForce GTX580,	754	723	178	0.25	21 real time!
	512 cuda cores @ 1544 MHz,	60	55	4	0.07	3.5 real time!
	mem bandwidth 192 GB/sec

Table 3 :

 3 Contribution of different optimizations on execution time. Matching one model graph of 30 nodes to one scene graph of 754 nodes and 723 frames.

Table 4 :

 4 time with at the same time providing recognition performance comparable to the state of art. The best performing methods require several seconds of calculation per frame, whereas our method requires only 0.0035 seconds per frame. Our GPU algorithm is faster in several orders of magnitude.

	Method

Comparison of different model types with and without restriction to a single point per frame (M : number of model nodes, S: number of scene nodes, M : number of model frames, S: number of scene frames, R: maximum number of interest points per frame in the scene sequence, N = 3: number of matched single-chain-single-point model).

http://www.nada.kth.se/cvap/actions/

Acknowledgement

This work has been partially funded by the ANR project SoLStiCe (ANR-13-BS02-0002-01), a project of the grant program "ANR blanc".


Enrique Wulff-Barreiro
email: enrique.wulff@icman.csic.es

Spain)

The purpose of this paper is to assert the existence of a database relating the culture collection of marine microalgae sited at the Marine Sciences Institute from Andalusia (Spanish Council for Scientific Research). This collection reports 79 strains, belonging to 10 algal classes, most of them are marine algae, interesting from the aquaculture point of view. The author contributes with the comparative data gathered on the growth characteristics, biomass and energy content of cultured marine microalgae. Cell volume of the algae by distribution range, mean and mode are provided. Gross biochemical composition of the algae, as a percentage of the total protein, carbohydrate and lipid content is also available. To facilitate information about which culture methods (beaker, sterilized plastic, agar) are enjoyed to which strain is also the point here. The database constitutes a reference point for a worldwide scoped collection. It concerns the spread of a scientific object eventually stimulating the exchange of experiences and know-how in this digital domain. It could provide mechanisms for the exchange of open-source software components, and also to establish close contacts with relevant application communities.

Introduction.-Those researching for model exchange for microalgae species variety between different areas of the world, require the corresponding tools supported by algorithms, software and data. It is recognized that research collections do not give complete information on all the species, and one needs models to relate the volumes of the samples to the number of species and the abundances of them on the one hand and also to the forecasting of the total species on the other. [START_REF] Yakimov | Simulating community species structure[END_REF] The most productive and fullest conceptual model in this sense is an explicit hypermedia system that can be used to aid navigation and re-orient lost users. [START_REF] Beynon-Davies | A semantic database approach to knowledge-based hypermedia systems[END_REF] There is also the question of optimal frequency structures in large systems. For the analysis and formalization of the species structure we assume that an indicator of quantity is the number of individuals while the number of species is an indicator of quality [START_REF] Yakimov | Simulating community species structure[END_REF]. 79 is the total number of marine microalgae strains in this Spanish Council for Scientific Research Collection, belonging to 10 algal classes.

The structure of the presentation is as follows:

In Section 1 it is discussed the database where the culture collection of marine microalgae electronic table is presented by means of the standard for storing structured text hypertext markup language (HTML). Three distinct stages of hypermedia development has been distinguished: cataloging of the artifacts [ie introduction of the documentation (graphs and summaries of the papers), compilation of the thesaurus providing the classification space, and presentation involving a system controlled form of navigation. Different usages activities have been previewed: directed research oriented activity by the academics, and activities more able to act as tools for curatorial information management.

In Section 2 the reader can make up his/her mind whether the core group inside the microalgae collection is worth his/her scientific interests. Either by examining the growth characteristics, biomass, energy content of the microalgae, or their cell volume and gross biochemical composition.

In Section 3 the filter instrument introduced to supply the information on the culture method is provided.

In Section 4, the strategies of scientific research built after this microalgae collection, and acknowledged through the Science Citation Index, are exposed. So, a bibliometric overview diagram of usages of the collection is supplied.

Section 5 discusses five unequally rich information based approaches of the material in the collection. It outlines extensions to the work performed, in particular the modelling of the way the microalgae have been collected.

1. The database of the marine microalgae culture collection of the Oceanography Department of the Spanish Council for Scientific Research, Cadiz (Spain): An hypermedia information system, building and composition.

The Culture collection of Microalgae is assigned to an electronic table written into the simplest implementation between the markup languages, ie hypertext markup language (Marine_microalgae.html). The construction of this table corresponds to the data gathered for authoring and classification by the curator. Thus the structure of the information is defined via intensional relations, offering the capability of providing intelligent assistance in the authoring of the hypermedia material. And the actual occurrences of relationships of relevance to hypermedia nodes are comprised into the extensional information.

[2] [START_REF] Wulff-Barreiro | Conceptual control in herarchical and combinatories structures : UDC vs. bilindex[END_REF] The scheme of the database matches the electronic table with a thesaurus. A keyword index has been built as a single comprehensive index and an identified point of access to any data [START_REF] Lord | Strategies and tactics for managing electronic data records : a view from the pharmaceutical industry[END_REF].

Related to this driver are the summaries of the reported documents (after the pre-/post-prints facilitated by the authors) where the priorities in research have been claimed for, after the microalgae collection. Throughout their storage life in the database these documents will be interpreted with the curator provided keywords, displayed inmediately at the left of the abstract's text, and in the layout of the Video Display Unit.

Another focus of data implements the bibliometric overview which tries to make more attractive the data on the microalgae, from a competitive viewpoint, by reporting some of the uses associated with them after an analysis of the Science Citation Index.

At last a web-designed page retains the memory on previous experiments conducted on the growth characteristics, biomass and energy content of the core group in the microalgae collection.

All the material is designed with Dublin Core metadata ready to be incorporated to an Internet web site.

The database: An electronic application supplying with information on growth characteristics, biomass and energy contents. Some proficiencies related with cell volume and gross biochemical composition.

Throughout 20 selected strains, and after seven days (data already published [START_REF] Lubián | Culture collection of microalgae of the Marine Sciences Institute of Andalusia (CSIC)[END_REF]) of growth development, when we move from Cyanophyceae to Bacillariophyceae, the growth characteristics, chlorophyll and energy potentially available data are exposed (into the page Benchmarking_The_Core_Group.html) both referred to organic matter obtained and to biomass.

The significance of the relations between the numbers of species is inclined to regulate the optimal-nutritional criteria. It seems that standard indices for species richness, equilibration, and dominance could afford with the applied aspect of aquaculture engineering raised by this approach. [START_REF] Yakimov | Simulating community species structure[END_REF] The range of cell concentrations describes a wide interval (from 0,3 10 6 ml -1 (Tetraselmis sp.) to 118,5 10 6 ml -1 (Synechococcus sp.)). But when expressed in terms of maximum biomass obtained, the variation is less random (between 139 and 207 μg ml -1 ), been the two limiting cases Synechococcus sp., Tetraselmis Chuii and Tetraselmis Suecica (superior bound) and N.atomus and N.maculata (inferior bound).

Looking ahead, the values of the growth rates can be expressed between 0,34 and 0,67 d -1 . And the exceptions to the bounded area are Tetraselmis sp (1,12 d -1 ), and C. gracilis and C.calcitrans (0,23 d -1 and 0,21 d -1 ).

When one estimates the Chlorophyll levels, massively influenced by pigment composition and by the metabolism of the strains under the culture conditions, the distribution is splitted up, by means of the regularity of most species, into two differing in cardinality subgroups. When referred after the biomass: the upper one with Tetraselmis suecica (36,7 mg g -1 ), Phaeodactylum tricornutum (27,8 mg g -1 ), Tetraselmis sp (24,8 mg g -1 ), and Dunaliella salina (23,0 mg g -1 ); and encoded as involving the smallest value: Nannochloris maculata (10,1 mg g -1 ). And when the index is to be built in terms of μg ml -1 the oscillation would be between Nannochloris maculata (0,61 μg ml -1 ) and Synechococcus sp (3,91μg ml -1 ).

The energetic value, developed from the chemical composition, varies between Tetraselmis Suecica (26,3 J mg -1 ) and Nannochloris maculata (55,2 mg -1 ).

The cell volumes of the algae present an interval of oscillation between 1,4 μm 3 attached to Nannochloris maculata and 723,0 μm 3 derived from the Tetraselmis sp. The means are also between these two algae, ie a range from 3,0 to 419,9 μm 3 respectively. All the distributions have been reported to present asimmetry to the right (positive skewness, the mean is greater than the mode).

The gross biochemical composition of the core group inside the algae collection, as a percentage of the total protein, carbohydrate and lipid content, reveals an accumulation of reserve substances (carbohydrate and lipid content) facing the proteins. And Synechococcus resulted in providing maximum protein contents (minimum of lipids), Nannochloris maculata affording with the minimum of proteins, and Chaetoceros calcitrans presenting the maximum of lipids.

The key instrument introduced to supply the information on the stock culture method is provided.

Mastery of techniques lay at the center of microalgae pursuit. Tools like media challenge the algololist's ability to grow, isolate, and observe strains in the laboratory, since the environment provided in the laboratory induces changes into the morphological traits used for identification proposed. And the eventual compression of the data in accordance with the species structure from optimal variety to anomalous state can demonstrate to the users (possesors) of the collection that an adequate representation and expression is available from the layout of the electronic table presented by html means.

Agar is a seaweed product, with the advantage of remaining firm at body temperature, the preferred growing temperature for most algae. It is symbolized with an A. The culture is performed in a tube with quarterly renewal (see Marine_microalgae.html).

All subsequent stock cultures are mantained either in 100 ml beaker, what is marked up with M in the electronic table; or in a 6 ml tube of sterilized plastic, expressed with a T. (Both procedures with weekly renewal.)

The filtered and sterilized sea water is enriched with Guillard's f/2 medium.

Bibliometric overview diagram of usages of the collection

Under this heading it is proposed to evaluate the context of the citations produced towards the publication: This expertise is available visualizing the results of a short citation study inside the Science Citation Index. Additional data has been derived from the presence of this collection inside the Cambridge Scientific Abstracts databases on aquatic science. The remain analysis approaches those publications from the Oceanography Dpt. (CSIC. Cádiz) not included into SCI, but resting on the collection for the management of the strains.

Following closely the distribution of the amounts of references under each entry of the thesaurus, we can presume that the bibliometric appraisal of the presence of the Marine Microalgae Culture Collection, at Cádiz CSIC Station, into the Cambridge Scientific Abstracts (ASFA, Aquatic Sciences and Fisheries Information System), maintains similar properties. Interesting enough is the position of temporal monopoly on spanish total production in what concerns scientific journal articles, for the period considered 1997-2000. (What could be contrasted with the data on Ph.D. produced by the labo doctoral students, no more than 6 over the 60 amounting for the total spanish production).

In particular, set against the seven microalgae bibliographies were Cádiz-CSIC labo. was detected, the only spanish references available were those identified with the staff of the Oceanographic Dpt. And this despite the eventual uninvolvement with productions (like turbot) known to need as microalgae diet a particular one included in the collection (as Tetraselmis chuii).

Intimately connected with the rise of Nannochloropsis gaditana Lubián as a new species 4 over the 5 contributions on this microalgae, in ASFA, come from CSIC-Cádiz Marine Microalgae Collection. Equally, the percentual rates of the collection in ASFA are: 14% of the production on Rhodomonas baltica, 11% on Tetraselmis chuii, 11% on Nannochloropsis oculata, 100% on Nannochloris maculata, 100% on Nannochloris atomus, and 4% on Chaetoceros gracilis.

More data extracted from the databases report on the presence of the sequence of the 18S rRNA gene of Nannochloropsis gaditana Lubián, in GenBank and in the DNA Databank of Japan (DDBJ).

Additional retrieval questions to facilitate navigation through the database

The following questions for developing benchmarked perspectives between the species presented in the collection (and under the three nominal regions in which they could be splitted up, ie species that are not numerous, intermediate ones, and ones predominant in numbers) are proposed: [START_REF] Yakimov | Simulating community species structure[END_REF] Is it culturing the prerequisite for identification?, ie Does the phenotype expressed in pure culture necessarily reflect the phenotype(s) expressed in the natural setting?

[2] Do the major phylogenetic assemblages serve specific community functions linked to carbon cycling?, or Is it the mineralization of organic carbon a way to approach the collection? [START_REF] Hayla | Measuring nature: quantitative data in field biology[END_REF] Has the question on sulphate reduction as an (obligately) anaerobic process make sense in ICMAN's collection of marine microalgae?, ie Which is the identity of the microalgae populations associated with aerobic sulfate reduction? [START_REF] Lord | Strategies and tactics for managing electronic data records : a view from the pharmaceutical industry[END_REF] Which way were collected the microalgae (by coring and subsampling)?, At which increments?, How were transported the samples?, In water?, Under which conditions of temperature?, Was constancy of temperature obtained?, Which kind of material (aluminium?) is employed to cool the samples? [START_REF] Lubián | Culture collection of microalgae of the Marine Sciences Institute of Andalusia (CSIC)[END_REF] Could be determined the marine microalgae that may function as nutritional generalists?, Which is the range of substrates they oxidize? When asking: [START_REF] Yakimov | Simulating community species structure[END_REF] Is it culturing the prerequisite for identification?, ie Does the phenotype expressed in pure culture necessarily reflect the phenotype(s) expressed in the natural setting?

It could be retrieved from the database that:

In rapidly identifying marine microalgae taxon-specific attributes of plants may be of use. Limited to the division or class level the identification of algal phylogenetic groups rely on pigment "signatures". Work on Ultrastructure and pigments of some planktonic chlorophyceae and Eustigmatophyceae of similar morphology _Nannochloris, Nannochloropsis, Algae, taxonomic aspects_. has been performed after the culture collection of microalgae here at Puerto Real. Mass mortality of farmed bluefin tuna (an area where CSIC station in Cadiz has been notorious in the past) has derived into experiments on the different light adaptation phenotypes after long-term culturing under similar physiological conditions.

[2] Do the major phylogenetic assemblages serve specific community functions linked to carbon cycling?, or Is it the mineralization of organic carbon a way to approach the collection?

From the database, and under the titles: Effects of high irradiance and temperature on photosynthesis and photoinhibition in Nannochloropsis gaditana Lubián (Eustigmatophyceae), relationships between bio-optical characteristics and photoinhibition of phytoplankton, and A comparative study of acid and alkaline phosphtase activies in several strains of Nannochloris (Chlorophyceae) and Nannochloropsis (Eustigmatophyceae) are some of the pertinent retrievable items.

In fact, specific for microalgal phylogenetic groups chlorophylls and carotenoids indicate the activity of the Xanthophyll cycle acting as a photoprotection system. The carbon fixation rates remarqued when researching on the Xanthophyll cycling as optimizer of the biosynthesis of light-harvesting Xanthophylls under fluctuating light conditions, have been studied after strains from the collection.

[3] Has the question on sulfate reduction as an (obligately) anaerobic process make sense in ICMAN's collection of marine microalgae?, ie Which is the identity of the microalgae populations associated with aerobic sulfate reduction?

It has been observated that Haematococcus pluvialis is one of the favored organisms for biotechnological production of Keracarotenoids, antioxidative compounds, but without relationships with the strain present in the collection.

[4] Which way were collected the microalgae (by coring and subsampling)?, At which increments?, How were transported the samples?, In water?, Under which conditions of temperature?, Was constancy of temperature obtained?, Which kind of material (aluminium?) is employed to cool the samples?

According to the database no more than the last question could be answered.

Works on Effects of slow and rapid warming on the cryopreservation of marine microalgae and Effects of culture age on cryopreservation of marine microalga, have been retrieved. After what, the development of marine microalgae cryostorage might contribute to improve hatcheries efficiency by assuring the permanent and inmediate availability of high-quality and stable stock cultures. The algae were the following: Tetraselmis chuii, Nannochloris atomus, Nannochloropsis gaditana (showing the best tolerances to biological freezing, with mean viabilities of 97.9%, 80.5% and 61.6% respectively), and Rhodomonas baltica and Isochrysis galbana (with the lowest viability). The material employed to cool the samples was a Cryoson BV-25 biological freezer, which was filled with a platinum sensor for temperature and two copper thermocouples (connecting the sample with the CPU, and recording the environmental temperature in the freezing chamber).

Searching for producing more information on the cryopreservation of the marine microalgae of scientific and commercial interest a viability index for cryopreserve marine microalgae employing different cooling rates, with or without cryoprotective compounds, has been conducted. Tetraselmis chuii, Nannochloropsis gaditana and Nannochloris atomus Butcher could be cryopresrved without cryoprotectant. Isochrysis galbana gave the poorest results. Rhodomonas baltica was very poorly cryopreserved at the higher salinity (as associated with freshwater environments). Between the diatoms, Chaetoceros gracilis achieved the higher post-throw viability.

[5] Could be determined the marine microalgae that may f unction as nutritional generalists?, Which is the range of substrates they oxidize? When examining the differences in the mode of inorganic carbon utilization it has been shown (in: Comparative study of dissolved inorganic carbon utilization and photosynthetic responses in Nannochloris (Chlorophyceae) and Nannochloropsis (Eustigmatophyceae) species), after strains from the collection, that Nannochloropsis species are able to transport bicarbonate across the plasmalemma. Nannochloris species was affected by the inhibitor acetazolamide.

A further question on an effective means of increasing microalgal populations within confined environments could be answered after microalgae cultures from the the collection. The population growth of microalgae in monospecific culture and their related bacteria has been found the subject of a document in the database.

Conclusion.-I end with a final generalization:

When the establishment of the new algal class, Eustigmatophyceae, was stated, some botanists wished to explain the differences between Nannochloris and Nannochloropsis microalgae genuses. The historical record of 1982, (Lazaroa, 4: 287-293.), when Nannochloropsis gaditana Lubián showed to be a new species of the genus Nannochloropsis, confines to the semantics of a theory the development of a Microalgae culture collection.

Data have retained a powerful hold on problems using the theoretical tools already at hand. And those whose main concern is the application of scientific findings to ecotoxicology and aquaculture problems have approach the boundaries of their criterias by allocating resources for the creation of a particular database.

  Lubián,LMª; Yúfera,M. (1989) Culture collection of microalgae of the Marine Sciences Institute of Andalusia (CSIC). In: Acuicultura intermareal. 1989. M. Yúfera (Ed.). Inst.Cien.Mar.Andalucía, Cádiz. pp.69-78.

The qualitative indicator suggested by the 49 different species cultured in the collection has been attained with the expansion in knowledge provided by the use of data for comparisons. Through achieving systematic comparative studies between microalgae strains the collection has grown, and this is the background of the database.

The database building can shed light on the conditions which determine the uses of the strains, the pattern of species diversity, and the meaning of the activities entrenching the laboratory system and the microalgae collection.

Spanish Council for Scientific Research, Cádiz (