This paper discusses an image processing architecture and tools to address the problem of ship detection in synthetic-aperture radar images. The detection strategy relies on a tree-based representation of images, here a Maxtree, and graph signal processing tools. Radiometric as well as geometric attributes are evaluated and associated with the Maxtree nodes. They form graph attribute signals which are processed with graph filters. The goal of this filtering step is to exploit the correlation existing between attribute values on neighboring tree nodes. Considering that trees are specific graphs where the connectivity toward ancestors and descendants may have a different meaning, we analyze several linear, nonlinear, and morphological filtering strategies. Beside graph filters, two new filtering notions emerge from this analysis: tree and branch filters. Finally, we discuss a ship detection architecture that involves graph signal filters and machine learning tools. This architecture demonstrates the interest of applying graph signal processing tools on the tree-based representation of images and of going beyond classical graph filters. The resulting approach significantly outperforms state-of-the-art algorithms. Finally, a MATLAB toolbox allowing users to experiment with the tools discussed in this paper on Maxtree or Mintree has been created and made public.

This paper investigates several optimum graph-cut techniques for pruning binary partition trees (BPTs) and their usefulness for the low-level processing of polarimetric synthetic aperture radar (PolSAR) images. BPTs group pixels to form homogeneous regions, which are hierarchically structured by inclusion in a binary tree. They provide multiple resolutions of description and easy access to subsets of regions. Once constructed, BPTs can be used for a large number of applications. Many of these applications consist in populating the tree with a specific feature and in applying a graph cut called pruning to extract a partition of the space. In this paper, different pruning examples involving the optimization of a global criterion are discussed and analyzed in the context of PolSAR images for segmentation. Through the objective evaluation of the resulting partitions by means of precision-and-recall-for-boundaries curves, the best pruning technique is identified, and the influence of the tree construction on the performances is assessed.

The High Efficiency Video Coding standard (HEVC) supports a total of 35 intra prediction modes which aim at reducing spatial redundancy by exploiting pixel correlation within a local neighborhood. In this paper, we show that spatial correlation remains after intra prediction, leading to high energy prediction residues. We propose a novel scheme for encoding the prediction residues using a Mode Dependent Vector Quantization (MDVQ) which aims at reducing the redundancy in residual domain. The MDVQ codebook is optimized in a rate-distortion (RD) sense. Experimental results show that the codebook can be independent of the quantization parameter (QP) with no loss in terms of coding efficiency. A bitrate reduction of 1.1% on average compared to HEVC can be achieved, while further tests indicate that codebook adaptivity could substantially improve the performance.

BACKGROUND: In the last decade, a great number of methods for reconstructing gene regulatory networks from expression data have been proposed. However, very few tools and datasets allow to evaluate accurately and reproducibly those methods. Hence, we propose here a new tool, able to perform a systematic, yet fully reproducible, evaluation of transcriptional network inference methods. RESULTS: Our open-source and freely available Bioconductor package aggregates a large set of tools to assess the robustness of network inference algorithms against different simulators, topologies, sample sizes and noise intensities. CONCLUSIONS: The benchmarking framework that uses various datasets highlights the specialization of some methods toward network types and data. As a result, it is possible to identify the techniques that have broad overall performances.

This paper discusses the interest of Binary Partition Trees (BPTs) and the usefulness of graph cuts for low-level processing of PolSAR images. BPTs group pixels to form homogeneous regions, which are hierarchically structured by inclusion in a tree. They provide multiple resolutions of description and easy access to subsets of regions. Once constructed, BPTs can be used for many applications including filtering, segmentation, classification and object detection. Many processing strategies consist in populating the tree with a specific feature and in applying a graph-cut called pruning. Different graph-cuts are discussed and analyzed in the context of PolSAR images for speckle filtering and segmentation.

This study proposes a system to estimate the depth order of regions belonging to a monocular image sequence. For each frame, the regions are ordered according to their relative depth using information from the previous and following frames. The algorithm estimates occlusions relying on a hierarchical region‐based representation of the image by means of a binary tree. This representation is used to define the final depth order partition which is obtained through an energy minimisation process. Finally, to achieve a global and consistent depth ordering, a depth order graph is constructed and used to eliminate contradictory local cues. The system is evaluated and compared with the state‐of‐the‐art figure/ground labelling systems showing very good results.

This paper deals with the processing of polarimetric synthetic aperture radar (SAR) time series. Different approaches to deal with the temporal dimension of the data are considered, which are derived from different target characterizations in this dimension. These approaches are the basis for defining two different binary partition tree (BPT) structures that are employed for SAR polarimetry (PolSAR) data processing. Once constructed, the BPT is processed by a tree pruning, producing a set of spatiotemporal homogeneous regions, and estimating the polarimetric response within them. It is demonstrated that the proposed technique preserves the PolSAR information in the spatial and the temporal domains without introducing bias nor distortion. Additionally, the evolution of the data in the temporal dimension is also analyzed, and techniques to obtain BPT-based scene change maps are defined. Finally, the proposed techniques are employed to process two real RADARSAT-2 data sets.

The microarray data classification is an open and active research field. The development of more accurate algorithms is of great interest and many of the developed techniques can be straightforwardly applied in analyzing different kinds of omics data. In this work, an ensemble learning algorithm is applied within a classification framework that already got good predictive results. Ensemble techniques take individual experts, (i.e. classifiers), to combine them to improve the individual expert results with a voting scheme. In this case, a thinning algorithm is proposed which starts by using all the available experts and removes them one by one focusing on improving the ensemble vote. Two versions of a state of the art ensemble thinning algorithm have been tested and three key elements have been introduced to work with microarray data: the ensemble cohort definition, the nonexpert notion, which defines a set of excluded expert from the thinning process, and a rule to break ties in the thinning process. Experiments have been done on seven public datasets from the Microarray Quality Control study, MAQC. The proposed key elements have shown to be useful for the prediction performance and the studied ensemble technique shown to improve the state of the art results by producing classifiers with better predictions.

As early stage of video processing, we introduce an iterative trajectory merging algorithm that produces a region-based and hierarchical representation of the video sequence, called the Trajectory Binary Partition Tree (BPT). From this representation, many analysis and graph cut techniques can be used to extract partitions or objects that are useful in the context of specific applications. In order to define trajectories and to create a precise merging algorithm, color and motion cues have to be used. Both types of informations are very useful to characterize objects but present strong differences of behavior in the spatial and the temporal dimensions. On the one hand, scenes and objects are rich in their spatial color distributions, but these distributions are rather stable over time. Object motion, on the other hand, presents simple structures and low spatial variability but may change from frame to frame. The proposed algorithm takes into account this key difference and relies on different models and associated metrics to deal with color and motion information. We show that the proposed algorithm outperforms existing hierarchical video segmentation algorithms and provides more stable and precise regions.

In this work, an image representation based on Binary Partition Tree is proposed for object detection in hyperspectral images. The BPT representation defines a search space for constructing a robust object identification scheme. Spatial and spectral information are integrated in order to analyze hyperspectral images with a region-based perspective. Experimental results demonstrate the good performances of this BPT-based approach.

The current increase of spatial as well as spectral resolutions of modern remote sensing sensors represents a real opportunity for many practical applications but also generates important challenges in terms of image processing. In particular, the spatial correlation between pixels and/or the spectral correlation between spectral bands of a given pixel cannot be ignored. The traditional pixel-based representation of images does not facilitate the handling of these correlations. In this paper, we discuss the interest of a particular hierarchical region-based representation of images based on binary partition tree (BPT). This representation approach is very flexible as it can be applied to any type of image. Here both optical and radar images will be discussed. Moreover, once the image representation is computed, it can be used for many different applications. Filtering, segmentation, and classification will be detailed in this paper. In all cases, the interest of the BPT representation over the classical pixel-based representation will be highlighted.

This paper proposes a system that relates objects in an image using occlusion cues and arranges them according to depth. The system does not rely on a priori knowledge of the scene structure and focuses on detecting special points, such as T-junctions and highly convex contours, to infer the depth relationships between objects in the scene. The system makes extensive use of the binary partition tree as hierarchical region-based image representation jointly with a new approach for candidate T-junction estimation. Since some regions may not involve T-junctions, occlusion is also detected by examining convex shapes on region boundaries. Combining T-junctions and convexity leads to a system which only relies on low level depth cues and does not rely on semantic information. However, it shows a similar or better performance with the state-of-the-art while not assuming any type of scene. As an extension of the automatic depth ordering system, a semi-automatic approach is also proposed. If the user provides the depth order for a subset of regions in the image, the system is able to easily integrate this user information to the final depth order for the complete image. For some applications, user interaction can naturally be integrated, improving the quality of the automatically generated depth map.

The optimal exploitation of the information provided by hyperspectral images requires the development of advanced image-processing tools. This paper proposes the construction and the processing of a new region-based hierarchical hyperspectral image representation relying on the binary partition tree (BPT). This hierarchical region-based representation can be interpreted as a set of hierarchical regions stored in a tree structure. Hence, the BPT succeeds in presenting: 1) the decomposition of the image in terms of coherent regions, and 2) the inclusion relations of the regions in the scene. Based on region-merging techniques, the BPT construction is investigated by studying the hyperspectral region models and the associated similarity metrics. Once the BPT is constructed, the fixed tree structure allows implementing efficient and advanced application-dependent techniques on it. The application-dependent processing of BPT is generally implemented through a specific pruning of the tree. In this paper, a pruning strategy is proposed and discussed in a classification context. Experimental results on various hyperspectral data sets demonstrate the interest and the good performances of the BPT representation.

Microarray data classification is a challenging problem due to the high number of variables compared to the small number of available samples. An effective methodology to output a precise and reliable classifier is proposed in this work as an improvement of the algorithm in [1]. It considers the sample scarcity problem and the lack of data structure typical of microarrays. Both problem are assessed by a two-step approach applying hierarchical clustering to create new features called metagenes and introducing a novel feature ranking criterion, inside the wrapper feature selection task. The classification ability has been evaluated on 4 publicly available datasets from Micro Array Quality Control study phase II (MAQC) classified by 7 different endpoints. The global results have showed how the proposed approach obtains better prediction accuracy than a wide variety of state of the art alternatives.

In this paper, we propose a system to obtain a depth ordered segmentation of a single image based on low level cues. The algorithm first constructs a hierarchical, region-based image representation of the image using a Binary Partition Tree (BPT). During the building process, T-junction depth cues are detected, along with high convex boundaries. When the BPT is built, a suitable segmentation is found and a global depth ordering is found using a probabilistic framework. Results are compared with state of the art depth ordering and figure/ground labeling systems. The advantage of the proposed approach compared to systems based on a training procedure is the lack of assumptions about the scene content. Moreover, it is shown that the system outperforms previously low-level cue based systems, while offering similar results to a priori trained figure/ground labeling algorithms.

This paper proposes a system to obtain the depth order of frames in image sequences using motion occlusion cues. The system first computes the forward and backward flows with the previous and next frames and estimates the occluded points. To obtain a region representation of the image, a Binary Partition Tree (BPT) is created for each frame. To estimate occlusion relations in the image, projective flow models are fitted to all regions in the image. The depth order solution is obtained by minimizing over the tree structure a cost function based on occlusion relations and the number of regions. Results show that optical flow algorithms can be used directly to estimate occlusion points. Promising results are obtained combining motion occlusions and region information by means of a BPT. Evaluation is performed comparing current state-of-the-art algorithms on figure/ground assignments, showing that the performance of the proposed system is comparable to current algorithms.

In this paper, the processing of temporal PolSAR image series is addressed through a region-based and multi-scale data representation, the Binary Partition Tree (BPT). This structure contains useful information related to the data structure at different detail levels that may be employed for different applications. The construction of this structure ans its exploitation is addressed in this work in the context of the speckle filtering and data segmentation applications. A new region model and processing strategy are defined to tackle with the temporal dimension of the data. Finally, to illustrate the capabilities of the proposed technique, results are shown with a real RADARSAT-2 dataset.

This paper presents a Polarimetric SAR data speckle filtering technique, based on a combined filtering in the spatial and polarimetric domains. It is based on a bilateral filtering employing distance measures over these domains. These measures concentrate all the information related to the domain structure that is needed for an adaptation to the scene morphology. A weighted average is performed over a given window favoring closer and similar pixels. As a consequence, an adaptive filtering is achieved, attaining higher filtering over homogeneous areas whereas point scatters remain almost unchanged. Results will be shown over a real RADARSAT-2 data.

In this paper,we propose the use of binary partition trees (BPT) to introduce a novel region-based and multi-scale polarimetric SAR (PolSAR) data representation. The BPT structure represents homogeneous regions in the data at different detail levels. The construction process of the BPT is based, firstly, on a region model able to represent the homogeneous areas, and, secondly, on a dissimilarity measure in order to identify similar areas and define the merging sequence. Depending on the final application, a BPT pruning strategy needs to be introduced. In this paper, we focus on the application of BPT PolSAR data representation for speckle noise filtering and data segmentation on the basis of the Gaussian hypothesis, where the average covariance or coherency matrices are considered as a region model. We introduce and quantitatively analyze different dissimilarity measures. In this case, and with the objective to be sensitive to the complete polarimetric information under the Gaussian hypothesis, dissimilarity measures considering the complete covariance or coherency matrices are employed. When confronted to PolSAR speckle filtering, two pruning strategies are detailed and evaluated. As presented, the BPT PolSAR speckle filter defined filters data according to the complete polarimetric information. As shown, this novel filtering approach is able to achieve very strong filtering while preserving the spatial resolution and the polarimetric information. Finally, the BPT representation structure is employed for high spatial resolution image segmentation applied to coastline detection. The analyses detailed in this work are based on simulated, as well as on real PolSAR data acquired by the ESAR system of DLR and the RADARSAT-2 system.

The 14 papers in this special issue are extended versions of papers presented at ICME 2011, held in Barcelona, Spain, on 11-15 July 2011.

This paper proposes a system to relate objects in an image using occlusion cues and arrange them according to depth. The system does not rely on any a priori knowledge of the scene structure and focuses on detecting specific points, such as T-junctions, to infer the depth relationships between objects in the scene. The system makes extensive use of the Binary Partition Tree (BPT) as the segmentation tool jointly with a new approach for T-junction estimation. Following a bottom-up strategy, regions (initially individual pixels) are iteratively merged until only one region is left. At each merging step, the system estimates the probability of observing a T-junction which is a cue of occlusion when three regions meet. When the BPT is constructed and the pruning is performed, this information is used for depth ordering. Although the proposed system only relies on one low-level depth cue and does not involve any learning process, it shows similar performances than the state of the art.

The work presented here proposes a new Binary Partition Tree pruning strategy aimed at the segmentation of hyperspectral images. The BPT is a region-based representation of images that involves a reduced number of elementary primitives and therefore allows to design a robust and efficient segmentation algorithm. Here, the regions contained in the BPT branches are studied by recursive spectral graph partitioning. The goal is to remove subtrees composed of nodes which are considered to be similar. To this end, affinity matrices on the tree branches are computed using a new distance-based measure depending on canonical correlations relating principal coordinates. Experimental results have demonstrated the good performances of BPT construction and pruning.

The aim of this paper is to present a Polarimetric Synthetic Aperture Radar data processing technique on the space-time domain. This approach is based on a Binary Partition Tree (BPT), which is a region-based and multi-scale data representation. Results with series of RADARSAT-2 real data are analyzed from the point of view of speckle filtering and change detection applications, to illustrate the capabilities to detect and preserve spatial and temporal contours.

This paper discusses hierarchical region-based representation using Binary Partition Tree in the framework of hyperspectral data. Based on region merging techniques, this region-based representation reduces the number of elementary primitives compared to the pixel based representation and allows a more robust filtering, segmentation, classification or information retrieval. The work presented here proposes a strategy for merging hyperspectral regions using a new association measure depending on canonical correlations relating principal coordinates. To demonstrate an example of BPT usefulness, a pruning strategy aiming at object detection is discussed. Experimental results demonstrate the good performances of BPT.

This paper presents a novel technique for automatic edge enhancement and detection in synthetic aperture radar (SAR) images. The characteristics of SAR images justify the importance of an edge enhancement step prior to edge detection. Therefore, this paper presents a robust and unsupervised edge enhancement algorithm based on a combination of wavelet coefficients at different scales. The performance of the method is first tested on simulated images. Then, in order to complete the automatic detection chain, among the different options for the decision stage, the use of geodesic active contour is proposed. The second part of this paper suggests the extraction of the coastline in SAR images as a particular case of edge detection. Hence, after highlighting its practical interest, the technique that is theoretically presented in the first part of this paper is applied to real scenarios. Finally, the chances of its operational capability are assessed.

Hyperspectral imaging segmentation has been an active research area over the past few years. Despite the growing interest, some factors such as high spectrum variability are still significant issues. In this work, we propose to deal with segmentation through the use of Binary Partition Trees (BPTs). BPTs are suggested as a new representation of hyperspectral data representation generated by a merging process. Different hyperspectral region models and similarity metrics defining the merging orders are presented and analyzed. The resulting merging sequence is stored in a BPT structure which enables image regions to be represented at different resolution levels. The segmentation is performed through an intelligent pruning of the BPT, that selects regions to form the final partition. Experimental results on two hyperspectral data sets have allowed us to compare different merging orders and pruning strategies demonstrating the encouraging performances of BPT-based representation.

A new multi-scale PolSAR data filtering technique, based on a Binary Partition Tree (BPT) representation of the data, is proposed. Different alternatives for the construction and the exploitation of the BPT for filtering and segmentation are presented.\nResults with simulated and experimental PolSAR data are presented to shown the capabilities of the BPT-filtering strategy to maintain both spatial details and the polarimetric information.

The optimal exploitation of the information provided by hyperspectral images requires the development of advanced image processing tools. This paper introduces a new hierarchical structure representation for such images using binary partition trees (BPT). Based on region merging techniques using statistical measures, this region-based representation reduces the number of elementary primitives and allows a more robust filtering, segmentation, classification or information retrieval. To demonstrate BPT capabilities, we first discuss the construction of BPT in the specific framework of hyperspectral data. We then propose a pruning strategy in order to perform a classification. Labelling each BPT node with SVM classifiers outputs, a pruning decision based on an impurity measure is addressed. Experimental results on two different hyperspectral data sets have demonstrated the good performances of a BPT-based representation.

Generalized Lifting (GL) has been studied for lossy image compression in. It has been demonstrated that the method leads to a significant reduction of the wavelet coefficients energy and entropy. The definition of the GL relies on an estimation of the pdf of the pixel to encode conditioned to a surrounding context. The objective of this paper is to present an improved method for the estimation of the pdf at the local level. Rather than assuming that the local pdf is monomodal, symmetric, and centered at the central value of the best context match within a neighborhood, as in, we follow the idea of self similarity proposed in for denoising, and propose to estimate the pdf using all the causal contexts within a window. Therefore, all the available knowledge about the neighborhood is incorporated. No assumptions about the characteristics of the pdf are made. A generalized lifting operator that minimizes the energy is applied to each context during the encoding process. Experimental results show an important increment in the energy and entropy gains when compared to previous strategies.

Occlusion is one of the major consequences of the physical image generation process: it occurs when an opaque object partly obscures the view of another object further away from the viewpoint. Local signatures of occlusion in the projected image plane are T-shaped junctions. They represent, in some sense, one of the most primitive depth information. In this paper, we investigate the usefulness of T-junctions for depth segregation in single images. Our strategy consists in incorporating ordering information provided by T-junctions into a region merging algorithm and then reasoning about the depth relations between the regions of the final partition using a graph model. Experimental results demonstrate the effectiveness of the proposed approach.

During the last years, the amount of multimedia content has greatly increased. This has multiplied the need of efficient compression of the content but also the ability to search, retrieve, browse, or filter it. Generally, video compression and indexing have been investigated separately. However, as the amount of multimedia content grows, it will be very interesting to study representations that, at the same time, provide good compression and indexing functionalities. Moreover, even if the indexing metadata is created for functionalities such as search, retrieval, browsing, etc., it can also be employed to increase the efficiency of current video codecs. Here, we use it to improve the long term prediction step of the H.264/AVC video codec. This paper focuses on the comparison between four different MPEG-7 descriptors when used in the proposed scheme.

This paper introduces the design of context-based models of contours in the wavelet domain, which are used to construct generalized lifting (GL) mappings for image compression. The GL context-based mapping may significantly reduce the signal energy and the resulting bitrate. Here, we propose a strategy to define a reduced set of structured models to design the GL. The models capture the contour structures and are contrast-invariant. Initial experimental results applying the strategy on a wavelet subband exhibit potential gains. Iterations of the GL scheme as well as an adaptive entropy coding strategy may increase the coding gain.

This paper presents an algorithm for tree-based representation of single images and its applications to segmentation and filtering with depth. In a our recent work, we have addressed the problem of segmentation with depth by incorporating depth ordering information into a region merging algorithm and by reasoning about depth relations through a graph model. In this paper, we extend this previous work giving a two-fold contribution. First, we propose to model each pixel statistically by its probability distribution instead of deterministically by its color value. Second, we propose a depth-oriented filter, which allows to remove foreground regions and to replace them with a plausible background. Experimental results are satisfactory.

This paper studies nonlocal morphological operators. Following the strategy proposed for the Nonlocal means filter, these operators are based on a local and adaptive definition of the structuring element which is specified by searching for patches in the image that are similar to the one surrounding the pixel being filtered. After presenting the basic nonlocal morphological operators using generic structuring elements, we study their robustness in the presence of noise. Then, we illustrate the interest of some nonlocal morphological operators using flat structuring elements for denoising.

In this paper we introduce an adaptive local pdf estimation strategy for the construction of Generalized Lifting (GL) mappings in the wavelet domain. Our approach consists in trying to estimate the local pdf of the wavelet coefficients conditioned to a context formed by neighboring coefficients. To this end, we search in a small causal window for similar contexts. This strategy is independent of the wavelet filters used to transform the image. Experimental results exhibit interesting gains in terms of energy reduction comparable to those obtained in [8]. In order to take benefit from this energy reduction, specific entropy encoder should be designed in the future.

In this paper we deal with the use of generalized lifting (GL) for lossy image compression. We have demonstrated in [9] the potential of the method for coding assuming complete knowledge of the pdf of the image to encode. Here, we move towards a realistic scheme that does not assume complete knowledge of the pdf. We show that a multiscale GL produces interesting results even if the pdf of the image to encode is only partially known. We target the compression of a given image class and compute an estimate of the image class pdf. This pdf is available at both encoder and decoder. A decision algorithm minimizes the overhead produced by the difference between the class pdf and the image pdf. This algorithm also removes ambiguities in the decoding process. The encoding strategy is completed using an arithmetic encoder. Results exhibit improvements over the state of the art.

Connected operators are operators that act by merging of elementary regions called flat zones. They cannot create new contours nor modify their position. Therefore, they have very good contour preservation properties. This paper discusses connected operators based on region trees. The filtering approach involves three steps: first, a region tree representation of the input image is constructed. Second, the simplification is obtained by pruning the tree and third, the output image is constructed from the pruned tree. The paper focuses on the trees used in practice and discusses various pruning strategies used in practice.

This paper discusses the use of Binary Partition Trees (BPTs) for object detection. BPTs are hierarchical region-based representations of images. They define a reduced set of regions that covers the image support and that spans various levels of resolution. They are attractive for object detection as they tremendously reduce the search space. In this paper, several issues related to the use of BPT for object detection are studied. Concerning the tree construction, we analyze the compromise between computational complexity reduction and accuracy. This will lead us to define two parts in the BPT: one providing accuracy and one representing the search space for the object detection task. Then we analyze and objectively compare various similarity measures for the tree construction. We conclude that different similarity criteria should be used for the part providing accuracy in the BPT and for the part defining the search space and specific criteria are proposed for each case. Then we discuss the object detection strategy based on BPT. The notion of node extension is proposed and discussed. Finally, several object detection examples illustrating the generality of the approach and its efficiency are reported.

Traditionally, video indexing and compression have been considered as two separate functionalities. However, the high amount of available multimedia content creates the need for multimedia services to consider both the compression and the indexing aspects of the content in order to efficiently manage it. Therefore, it is interesting to find new techniques that efficiently exploit the indexing/compression information in order to improve the compression/indexing capabilities of the content. This paper focusses on the development of one technique where the compression efficiency of the H.264 encoder is increased by the use of standard indexing information, called indexing metadata. This indexing metadata, even if extracted or generated to support indexing capabilities, can be exploited to enhance current standard video codecs such as H.264.

This paper deals with the joint use of connected operators and image inpainting for image filtering. Connected operators filter the image by merging its flat zones while preserving contour information. Image inpainting restores the values of an image for a destroyed or consciously masked subregion of the image domain. In the present paper, it will be shown that image inpainting can be combined with connected operators to perform an efficient geometrical filtering technique. First, connected operators are presented and their drawbacks for certain applications are highlighted. Second, image inpainting methodology is introduced and a structural image inpainting algorithm is described. Finally, a general filtering scheme is proposed to show how the drawbacks of connected operators can be efficiently solved by structural image inpainting.

Abstract This article provides an overview of the tools specified by the MPEG‐7 standard for describing the structure of multimedia content. In particular, it focuses on tools that represent segments resulting from a spatial and/or temporal partitioning of multimedia content. The segments are described in terms of their decomposition and the general relations among them as well as attributes or features of segments. Decomposition efficiently represents segment hierarchies and can be used to create tables of contents or indexes. More general graph representations are handled by the various standard spatial and temporal relations. A segment can be described by a large number of features ranging from those targeting the life cycle of the content (e.g., creation and usage) to those addressing signal characteristics such as audio, color, shape, or motion properties.

A useful tool to construct wavelet decompositions is the lifting scheme. The generalized lifting is an extension of the classical lifting scheme to introduce more flexibility and to permit the creation of new nonlinear and adaptive transforms. However, the design of generalized prediction and update steps is more involved. This letter proposes a generalized prediction design that minimizes the detail signal energy and entropy at the same time. Two algorithm variants are given. The fixed prediction uses the image class statistics to derive the optimal transform. If the statistics are unknown, the adaptive prediction extracts them from the image being coded. The resulting decompositions are applied to lossless image coding, reporting good results. The adaptive algorithm has no bookkeeping or side information requirements, yet its performance is close to the fixed prediction performance.

The optimization of a quadratic objective function with linear constraints is useful for interpolation purposes. This formulation may be employed to derive an initial prediction in the lifting scheme domain in order to construct wavelet transforms. We modify the formulation to design final prediction and update lifting steps. The linear constraints relate wavelet bases and coefficients with the underlying signal. The objective function is the detail signal energy for the prediction lifting design and the gradient of the approximation signal for the update. To report concrete results and the power of the approach, we derive update steps using an auto-regressive image model that show better performance than the 5/3 wavelet for the compression of several image classes

For the last few years, video indexing and video compression have been considered as two separate functionalities. However, multimedia content is growing at such a rate that multimedia services will need to consider both the compression and the indexing aspects of the content in order to efficiently manage this audio-video content. Therefore, it is interesting to study the synergy between the representations of compression and indexing and in particular to find new schemas that allow the possibility to exploit indexing/compression information in order to increase the efficiency of video compression/indexing capabilities. The principal contribution of this paper is to study and develop new techniques where the compression efficiency of video codecs can be improved by the use of indexing metadata where indexing metadata refers to information that has been generated to support indexing capabilities.

The lifting scheme is a useful tool to create different types of wavelet decompositions, including adaptive and nonlinear. Generalized lifting is more flexible and can improve lifting results, but the design of generalized prediction and update steps remains difficult for a given application. A design strategy to optimize the prediction step according to the image statistics is established. The criterion aims to minimize the detail signal coefficients energy, The scheme is used for lossless compression of several classes of images without any book-keeping or side information requirements. Promising results are reported for certain classes of images.

A method for lossless coding using a multi-resolution scheme with an adaptive lifting step is introduced. To this goal, a generalized lifting scheme, where the sums included in classical lifting are generalized to include possibly non linear and/or adaptive operations, is proposed. The conditions for the reversibility of the scheme are analyzed. Although the framework is valid for any type of sampled signals, we focus in particular on the discrete case (signals represented with a finite number of bits). Finally, experiments with a generalized prediction step are reported They show the interest of the approach for lossless compression.

This paper deals with connected operators based on reconstruction process. Connected operators are filtering tools that act on the connected components of the space where the image is constant, the so-called “flat zones”. Intuitively, connected operators can remove boundaries between flat zones but cannot add new boundaries nor shift existing contours. After reviewing the filtering strategy, new operators are proposed to perform size and motion simplification. In the case of size simplification, the proposed approach allows a better preservation the contrast of maxima or minima that have not been totally simplified by the filtering process. In the case of motion simplification, two applications are presented: motion detection for maxima/minima and sequence simplification to improve the coding efficiency of standard encoders.

This paper deals with the extraction and characterization of foreground objects in video sequences. The algorithm first computes the mosaic image representing the background information and then extracts foreground objects. In this last step, the foreground objects are progressively extracted taking into account the reliability of the contour information. This extraction step is based on morphological tools. Finally, the foreground objects are characterized by their shape, texture and motion trajectory. Moreover, some information about the temporal evolution of non rigid objects is also extracted. This feature extraction algorithm is particularly suitable for the indexing, search and retrieval applications.

This paper gives an overview of Part 1 of ISO/IEC 15939 (MPEG-7 Systems). It first presents the objectives of the MPEG-7 Systems activity. In the MPEG-1 and MPEG-2 standards, "Systems" referred only to overall architecture, multiplexing, and synchronization. In MPEG-4, in addition to these issues, the Systems part encompasses interactive scene description, content description, and programmability, MPEG-7 brings new challenges to the Systems expertise, such as languages for description representation, binary representation of descriptions, and delivery of descriptions either separate or jointly with the audio-visual content. The paper then presents the description of the MPEG-7 Systems specification, starting from the general architecture up to the description of the individual MPEG-7 Systems tools. Finally, a conclusion describes the status of the standardization effort, as well as future extensions of the specification.

MPEG-7 multimedia description schemes (MDSs) are metadata structures for describing and annotating audio-visual (AV) content. The description schemes (DSs) provide a standardized way of describing in XML the important concepts related to AV content description and content management in order to facilitate searching, indexing, filtering, and access. The DSs are defined using the MPEG-7 description definition language, which is based on the XML Schema language, and are instantiated as documents or streams. The resulting descriptions can be expressed in a textual form (i.e., human readable XML for editing, searching, filtering) or compressed binary form (i.e., for storage or transmission). In this paper, we provide an overview of the MPEG-7 MDSs and describe their targeted functionality and use in multimedia applications.

This paper discusses region-based representations useful to create connected operators. The filtering approach involves three steps: 1) a region tree representation of the input image is constructed; 2) the simplification is obtained by pruning the tree; and 3) and output image is constructed from the pruned tree. The paper focuses in particular on the pruning strategies that can be used depending of the increasing of the simplification criteria.

This paper discusses the interest of binary partition trees as a region-oriented image representation. Binary partition trees concentrate in a compact and structured representation a set of meaningful regions that can be extracted from an image. They offer a multiscale representation of the image and define a translation invariant 2-connectivity rule among regions. As shown in this paper, this representation can be used for a large number of processing goals such as filtering, segmentation, information retrieval and visual browsing. Furthermore, the processing of the tree representation leads to very efficient algorithms. Finally, for some applications, it may be interesting to compute the binary partition tree once and to store it for subsequent use for various applications. In this context, the paper shows that the amount of bits necessary to encode a binary partition tree remains moderate.

This paper discusses the interest of Binary Partition Trees for image and region representation in the context of indexing and similarity based retrieval. Binary Partition Trees concentrate in a compact and structured way the set of regions that compose an image. Since the tree is able to represent images in a multiresolution way, only simple descriptors need to be attached to the nodes. Moreover, this representation is used for similarity based region retrieval.

This paper proposes two description schemes (DSs) to describe the visual information of an audio-visual (AV) document. The first one, is devoted to still images. It describes the image visual appearance and its structure with regions as well as its semantic content in terms of objects. The second DS is devoted to video sequences. It describes the sequence structure as well as its semantic content in terms of events. Features such as motion, camera activity, etc. are included in this DS. Moreover, it involves static visual representations such as key-frames, background mosaics and key-regions. These elements are considered as still images and are described by the first DS.

This paper discusses region-based representations of image and video that are useful for multimedia services such as those supported by the MPEG-4 and MPEG-7 standards. Classical tools related to the generation of the region-based representations are discussed. After a description of the main processing steps and the corresponding choices in terms of feature spaces, decision spaces, and decision algorithms, the state of the art in segmentation is reviewed. Mainly tools useful in the context of the MPEG-4 and MPEG-7 standards are discussed. The review is structured around the strategies used by the algorithms (transition based or homogeneity based) and the decision spaces (spatial, spatio-temporal, and temporal). The second part of this paper proposes a partition tree representation of images and introduces a processing strategy that involves a similarity estimation step followed by a partition creation step. This strategy tries to find a compromise between what can be done in a systematic and universal way and what has to be application dependent. It is shown in particular how a single partition tree created with an extremely simple similarity feature can support a large number of segmentation applications: spatial segmentation, motion estimation, region-based coding, semantic object extraction, and region-based retrieval.

This paper discusses the interest of binary partition trees as shape-oriented image representations. Binary partition trees concentrate in a compact and structured representation a set of meaningful regions that can be extracted from an image. This representation can be used for a large number of processing goals such as filtering, segmentation, information retrieval and visual browsing. Furthermore, the processing of the tree representation leads to very efficient algorithms.

This paper deals with a class of morphological operators called connected operators. These operators filter the signal by merging its flat zones. As a result, they do not create any new contours and are very attractive for filtering tasks where the contour information has to be preserved. This paper shows that connected operators work implicitly on a structured representation of the image made of flat zones. The max-tree is proposed as a suitable and efficient structure to deal with the processing steps involved in antiextensive connected operators. A formal definition of the various processing steps involved in the operator is proposed and, as a result, several lines of generalization are developed. First, the notion of connectivity and its definition are analyzed. Several modifications of the traditional approach are presented. They lead to connected operators that are able to deal with texture. They also allow the definition of connected operators with less leakage than the classical ones. Second, a set of simplification criteria are proposed and discussed. They lead to simplicity-, entropy-, and motion-oriented operators. The problem of using a nonincreasing criterion is analyzed. Its solution is formulated as an optimization problem that can be very efficiently solved by a Viterbi algorithm. Finally, several implementation issues are discussed showing that these operators can be very efficiently implemented.

Connected operators are increasingly used in image processing due to their properties of simplifying the image with various criteria, without loosing contour's information. These properties are related to the connected operator approach that either preserves or completely eliminates a determined connected component, according to an established criterion of analysis. In this paper we will define a new connected operator for stereo images. The goal is to simplify one of the images (left) in the sense that the operator will eliminate the image components that are not present at a determined location in the other image (right). This filter let us select in a stereo image, objects as a function of their distance from the observer (for instance used in auto guided vehicles).

This paper discusses the use of connected operators for robust motion estimation. The proposed strategy involves a motion estimation step, extracting the dominant motion, and a filtering step, relying on connected operators that remove objects that do not follow the dominant motion. These two steps are iterated in order to obtain an accurate motion estimation and a precise definition of the objects following this motion. This strategy can be applied on the entire frame or on individual connected components. As a result, the complete (motion-oriented) segmentation and motion estimation of the frame can be achieved.

This paper presents a generic video coding algorithm allowing the content-based manipulation of objects. This manipulation is possible thanks to the definition of a spatiotemporal segmentation of the sequences. The coding strategy relies on a joint optimization in the rate-distortion sense of the partition definition and of the coding techniques to be used within each region. This optimization creates the link between the analysis and synthesis parts of the coder. The analysis defines the time evolution of the partition, as well as the elimination or the appearance of regions that are homogeneous either spatially or in motion. The coding of the texture as well as of the partition relies on region-based motion compensation techniques. The algorithm offers a good compromise between the ability to track and manipulate objects and the coding efficiency.

In this paper we describe a very low bit rate video coding system that belongs to the class of object based coding systems. The system takes advantage of homogeneity in both gray level and motion, trying to use the most adequate criterion for defining a partition in order to obtain the best compromise between cost and quality. In order to do so, multiple partitions are generated for every image in a hierarchical way, from the coarsest one to the finest one. Then, a decision step will chose which parts of the image need to be coded with regions from one partition or from another. The aim of the paper is to study the features that this multiple partition must have, and propose a way to create it.

This paper presents a video coding scheme for very low bit rate applications. The coding approach relies on the notion of active meshes and can be viewed as a particular case of region-based coding. The active mesh is used to efficiently represent and code the various regions of the scene as well as the motion information. The algorithm involves the following steps: projection (time tracking of the regions); partition and motion coding; synthesis; modification of the mesh topology (introduction of new regions and elimination of useless regions); and texture coding.

We present a coding scheme that achieves, for each image in the sequence, the best segmentation in terms of rate-distortion theory. It is obtained from a set of initial regions and a set of available coding techniques. The segmentation combines spatial and motion criteria. It selects at each area of the image the most adequate criterion for defining a partition in order to obtain the best compromise between cost and quality. In addition, the proposed scheme is very suitable for addressing content-based functionalities.

This paper deals with the use of some morphological tools for video coding at very low bit rates. Rather than describing a complete coding algorithm, the purpose of this paper is to focus on morphological connected operators and segmentation tools that have proved to be attractive for compression.

This paper presents a video coding scheme for very low bit rate applications. The coding approach relies on active meshes and can be viewed as a particular case of region-based coding. The active mesh is used to efficiently represent and code the various regions of the scene and the motion information. The variation of the mesh topology as well as the strategy for coding the synthesis error are defined by an optimization technique following the rate-distortion criterion.

This paper deals with the use of some morphological tools for image and video coding. Mathematical morphology can be considered as a shape-oriented approach to signal processing, and some of its features make it very useful for compression. Rather than describing a coding algorithm, the purpose of this paper is to describe some morphological tools that have proved attractive for compression. Four sets of morphological transformations are presented: connected operators, the region-growing version of the watershed, the geodesic skeleton, and a morphological interpolation technique. The authors discuss their implementation, and show how they can be used for image and video segmentation, contour coding, and texture coding.

In this paper a new morphological interpolation technique is presented. It is applied to the coding of the smooth (primary) component in a sketch-based image compression approach for very low bit-rates. The interpolation technique is intended to perform two dimensional interpolation from any set of initial pixels and, in particular, from sketch data. It makes intensive use of geodesic dilation, a morphological operator that may be implemented by means of FIFO queues. This results in a very efficient process compared to those that perform interpolation by linear filtering on the initial image. For the application of this method to interpolative image coding, the sketch data is extracted as a set of maximum curvature lines by means of the watershed algorithm. From such information, the interpolation technique obtains a fair reconstruction of both the smooth texture component and the main transitions of the image signal at low bit-rate cost.

This paper presents a region-based coding algorithm for video sequences. The coding approach involves a time-recursive segmentation relying on the pixels homogeneity, a region-based motion estimation, and motion compensated contour and texture coding. This algorithm is mainly devoted to very low bit rate video coding applications. One of the important features of the approach is that no assumption is made about the sequence content. Moreover the algorithm structure leads to a scalable coding process giving various levels of quality and bit rates. The coding as well as the segmentation are controlled to regulate the bit stream. Finally, the interest of morphological tools in the content of region-based coding is extensively reviewed.>

This correspondence deals with the notion of connected operators. Starting from the definition for operator acting on sets, it is shown how to extend it to operators acting on function. Typically, a connected operator acting on a function is a transformation that enlarges the partition of the space created by the flat zones of the functions. It is shown that from any connected operator acting on sets, one can construct a connected operator for functions (however, it is not the unique way of generating connected operators for functions). Moreover, the concept of pyramid is introduced in a formal way. It is shown that, if a pyramid is based on connected operators, the flat zones of the functions increase with the level of the pyramid. In other words, the flat zones are nested. Filters by reconstruction are defined and their main properties are presented. Finally, some examples of application of connected operators and use of flat zones are described.

In object-based video coding systems, the scenes are described in terms of three dimensional objects, which can be coded as textures and contours. However, in order to achieve high compression ratios, the redundancy in the temporal dimension must be exploited using motion compensation. In this context, motion compensation can take advantage of the description of the scene as three dimensional regions. In this paper we present a motion estimation method which finds, in a fast and computationally simple manner, the affine parameters for every region of the scene. These parameters correspond to the motion of the texture. An ordering between regions is established in order to have the right compensation of contours.>

This paper describes a segmentation-based coding algorithm for very low bit rate. The algorithm involves a segmentation relying on a time recursive morphological segmentation technique. It extracts both large and contrasted regions. Then, a simple region-based motion estimation is performed. Finally, the sequence is coded by contour-texture motion compensation. The proposed method leads to very low bit rates while being able to represent the meaningful regions of the scene. Moreover, it makes no assumption about the scene content and can be used for any sequence.

This paper deals with a hierarchical morphological segmentation algorithm for image sequence coding. Mathematical morphology is very attractive for this purpose because it efficiently deals with geometrical features such as size, shape, contrast, or connectivity that can be considered as segmentation-oriented features. The algorithm follows a top-down procedure. It first takes into account the global information and produces a coarse segmentation, that is, with a small number of regions. Then, the segmentation quality is improved by introducing regions corresponding to more local information. The algorithm, considering sequences as being functions on a 3-D space, directly segments 3-D regions. A 3-D approach is used to get a segmentation that is stable in time and to directly solve the region correspondence problem. Each segmentation stage relies on four basic steps: simplification, marker extraction, decision, and quality estimation. The simplification removes information from the sequence to make it easier to segment. Morphological filters based on partial reconstruction are proven to be very efficient for this purpose, especially in the case of sequences. The marker extraction identifies the presence of homogeneous 3-D regions. It is based on constrained flat region labeling and morphological contrast extraction. The goal of the decision is to precisely locate the contours of regions detected by the marker extraction. This decision is performed by a modified watershed algorithm. Finally, the quality estimation concentrates on the coding residue, all the information about the 3-D regions that have not been properly segmented and therefore coded. The procedure allows the introduction of the texture and contour coding schemes within the segmentation algorithm. The coding residue is transmitted to the next segmentation stage to improve the segmentation and coding quality. Finally, segmentation and coding examples are presented to show the validity and interest of the coding approach.

A class of nonlinear filters called rank order based filters, including, as special cases, rank order and morphological (with flat structuring element) filters, are dealt with. How they achieve size-sensitive multiresolution decompositions is described. The necessity of a special processing stage dedicated to shape preservation is shown, and a solution is proposed. The problem of filter mask (or structuring element) optimization to minimize a statistical criterion is also studied. The proposed algorithms are very simple, and their derivation is performed by using an implicit formulation of the filtering process. Both techniques are applied to a practical defect detection problem.>

This paper deals with surface defect detection. The approach investigated here attempts to detect grey level as well as texture defects. The defects are regarded as being characterized by abrupt, local and unpredictable changes in an image. On the other hand, a defect-free surface is assumed to be regular and homogeneous, possibly with smooth and slow variation in its features. The detection is based on adaptive image modeling. It is shown that a classical autoregressive model is not really suitable for this detection problem. Then, two modified models are proposed. Their advantage lies in their taking into account the grey level value as well as the texture information.The model adaptation can be stated as a joint optimization problem with constraint. Two different algorithms are defined and tested. The first algorithm performs the adaptation in a recursive way while enforcing the constraint at each step, whereas the second one imposes the constraint only at optimum. The performance of each algorithms is assessed with a statistical test using synthetic images. Finally, it is shown how this adaptive modeling technique can be applied to practical defect detection problems. Several cases are presented and discussed.