Search

Ultrasonic vocalizations (USVs) analysis is a well-recognized tool to investigate animal communication. It can be used for behavioral phenotyping of murine models of different disorders. The USVs are usually recorded with a microphone sensitive to ultrasound frequencies and they are analyzed by specific software. Different calls typologies exist, and each ultrasonic call can be manually classified, but the qualitative analysis is highly time-consuming. Considering this framework, in this work we proposed and evaluated a set of supervised learning methods for automatic USVs classification. This could represent a sustainable procedure to deeply analyze the ultrasonic communication, other than a standardized analysis. We used manually built datasets obtained by segmenting the USVs audio tracks analyzed with the Avisoft software, and then by labelling each of them into 10 representative classes. For the automatic classification task, we designed a Convolutional Neural Network that was trained receiving as input the spectrogram images associated to the segmented audio files. In addition, we also tested some other supervised learning algorithms, such as Support Vector Machine, Random Forest and Multilayer Perceptrons, exploiting informative numerical features extracted from the spectrograms. The performance showed how considering the whole time/frequency information of the spectrogram leads to significantly higher performance than considering a subset of numerical features. In the authors’ opinion, the experimental results may represent a valuable benchmark for future work in this research field.

The very fundamental operation of even/odd decomposition is at the core of some of the simplest information representation and signal processing tasks. So far most of its use has been for rearranging data to provide fast implementations of various types of transforms (Fourier, DCT, ...) or for achieving elementary data transformation, such as the Walsh–Hadamard transform. This work proposes to look into the decomposition framework to obtain a richer perspective. In the context of an iterated even/odd decomposition, it is possible to pinpoint intermediate layered levels of symmetries which cannot be easily captured in the original data. In addition this determines a hierarchical fingerprinting for any sort of continuous finite support analog signal or for any discrete-time sequence which may turn out useful in several recognition or categorization tasks. It also may help to achieve sparsity within a natural hierarchical framework, which could be easily extended for many other types of orthogonal transformations. This paper also suggests a global measure of the energy imbalance across the hierarchy of the decomposition to capture the overall fingerprinting of this interpretation.

Symmetry detection algorithms are enjoying a renovated interest in the scientific community, fueled by recent advancements in computer vision and computer graphics applications. This paper is inspired by recent efforts in building a symmetric object detection system in natural images. In particular, it is first shown how correlation can be a core operator that allows finding local reflection symmetry points in 1-D sequences that are optimal in an energetic sense. Then, the importance of 2-D correlation in natural images to correctly align the symmetric object axis is demonstrated. Using the correlation as described is crucial in boosting the performance of the system, as proven by the results on a standard dataset.

It is well-known that the application of the Discrete Cosine Transform (DCT) in transform coding schemes is justified by the fact that it belongs to a family of transforms asymptotically equivalent to the Karhunen-Loeve Transform (KLT) of a first order Markov process. However, when the pixel-to-pixel correlation is low the DCT does not provide a compression performance comparable with the KLT. In this paper, we propose a set of symmetry-based Graph Fourier Transforms (GFT) whose associated graphs present a totally or partially symmetric grid. We show that this family of transforms well represents both natural images and residual signals outperforming the DCT in terms of energy compaction. We also investigate how to reduce the cardinality of the set of transforms through an analysis that studies the relation between efficient symmetry-based GFTs and the directional modes used in H.265 standard. Experimental results indicate that coding efficiency is high.

A recent and fascinating interest in computational symmetry for computer vision and computer graphics applications has led to a remarkable realization of new symmetry detection algorithms. Such a concern is culminated in a symmetry detection competition as a workshop affiliated with the 2011 and 2013 CVPR Conferences. In this paper, we propose a method based on the computation of the symmetry level associated to each pixel. Such a value is determined through the energy balance of the even/odd decomposition of a patch with respect to a central axis (which is equivalent to estimate the middle point of a row-wise convolution). Peaks localization along the perpendicular direction of each angle allows to identify possible symmetry axes. The evaluation of a feature based on gradient information allows to establish a classification confidence for each detected axis. By adopting the aforementioned rigorous validation framework, the proposed method indicates significant performance increase.

In this chapter we survey available solutions for high dynamic range (HDR) image watermarking. First, we briefly discuss watermarking in general terms, with particular emphasis on its requirements that primarily include security, robustness, imperceptibility, capacity, and the availability of the original image during recovery. However, with respect to traditional image watermarking, HDR images possess a unique set of features, such as an extended range of luminance values to work with and tone-mapping operators against which it is essential to be robust. These clearly affect the HDR watermarking algorithms proposed in the literature, which we extensively review next, including a thorough analysis of the reported experimental results. As a working example, we also describe the HDR watermarking system that we recently proposed and that focuses on combining imperceptibility, security, and robustness in tone-mapping operators at the expense of capacity. We conclude the chapter with a critical analysis of the current state and future directions of the watermarking applications in the HDR domain.

In this paper we propose a segmentation of finite support sequences based on the even/odd decomposition of a signal. The objective is to ind a more compact representation of information. To this aim, the paper starts to generalize the even/odd decomposition by concentrating the energy on either the even or the odd part by optimally placing the centre of symmetry. Local symmetry intervals are thus located. The sequence segmentation is further processed by applying an iterative growth on the candidate segments to remove any overlapping portions. Experimental results show that the set of segments can be more eficiently compressed with respect to the DCT transformation of the entire sequence, which corresponds to the near optimal KLT transform of the data chosen for the experiment.

The reconstruction error due to quantization of wavelet subbands can be modeled as a cyclostationary process because of the linear periodically shift variant property of the inverse wavelet transform. For N-dimensional data, N-dimensional reconstruction error power cyclostationary patterns replicate on the data sample lattice. For audio and image coding applications this fact is of little practical interest since the decoded data is perceived in its wholeness, the error power oscillations on single data elements cannot be seen or heard and a global PSNR error measure is often used to represent the reconstruction quality. A different situation is the one of 3D data (static volumes or video sequences) coding, where decoded data are usually visualized by plane sections and the reconstruction error power is commonly measured by a P SNR [ n ] sequence, with n representing either a spatial slicing plane (for volumetric data) or the temporal reference frame (for video). In this case, the cyclostationary oscillations on single data elements lead to a global P SNR [ n ] oscillation and this effect may become a relevant concern. In this paper we study and describe the above phenomena and evaluate their relevance in concrete coding applications. Our analysis is entirely carried out in the original signal domain and can easily be extended to more than three dimensions. We associate the oscillation pattern with the wavelet filter properties in a polyphase framework and we show that a substantial reduction of the oscillation amplitudes can be achieved under a proper selection of the basis functions. Our quantitative model is initially made under high-resolution conditions and then qualitatively extended to all coding rates for the wide family of bit-plane quantization-based coding techniques. Finally, we experimentally validate the proposed models and we perform a subjective evaluation of the visual relevance of the P SNR [ n ] fluctuations in the cases of medical volumes and video coding.

Approximation of digital signals by means of continuous-time functions is often required in many tasks of digital to analog conversion, signal processing, and coding. In many cases the approximation is performed based on an l2 optimality criterion; in this paper we study approximations of one-dimensional signals under the linfin norm. We first introduce approximations in linear spaces, for which linear programming methods are known. For the particular case of linear approximations (i.e., first-order polynomials), we propose a geometric solution that is shown to be computationally more efficient than the linear programming approach. Then, we study the problem of piecewise approximations, i.e., dividing the domain into intervals and approximating the signal in linear spaces within every segment independently, so as to reach an optimal noncontinuous approximation. Given an error bound delta, we establish a strategy to determine the minimum number k of segments for which the approximation is guaranteed to produce an error within delta. We then show how to find the optimal partition that gives the piecewise linfin optimal solution with k segments. The computational complexity of the algorithms is studied, showing that in many practical situations, the number of operations is O(n), with n being the number of samples

The purpose of this paper is to present a technique to extend the functionality and the application fields of a spatially selective coding within a JPEG2000 framework. The image quality drop between the regions of interest (ROI) and the background (BG) is considered. From the conventional point of view, the reconstructed image quality steeply drops along the ROI boundary; however this effect can be considered is perceived to be objectionable in some situations. Here we propose a simple quality decay management, which makes use of the concentric ROI with different scaling factors. This allows the technique to be perfectly consistent with the JPEG2000 part 2 ROI definitions and description. The proposed techniques may have a significant impact on applications where both coding rate minimization and coded image quality are important and/or become critical factors. Experiments and examples demonstrate the benefits of the presented approach.

Multi-View Stereo (MVS) algorithms scale poorly on large image sets, and quickly become unfeasible to run on a single machine with limited memory. Typical solutions to lower the complexity include reducing the redundancy of the image set (view selection), and dividing the image set in groups to be processed independently (view clustering). A novel formulation for view selection is proposed here. We express the problem with an Integer Linear Programming (ILP) model, where cameras are modeled with binary variables, while the linear constraints enforce the completeness of the 3D reconstruction. The solution of the ILP leads to an optimal subset of selected cameras. As a second contribution, we integrate ILP camera selection with a view clustering approach which exploits Leveraged Affinity Propagation (LAP). LAP clustering can efficiently deal with large camera sets. We adapt the original algorithm so that it provides a set of overlapping clusters where the minimum and maximum sizes and the number of overlapping cameras can be specified. Evaluations on four different dataset show our solution provides significant complexity reductions and guarantees near-perfect coverage, making large reconstructions feasible even on a single machine.

SUMMARY This paper deals with the problem of recovering the input signal applied to a linear time-invariant system from the measurements of its output and the a priori knowledge of the input statistics (blind equalization). Under the assumption of an i.i.d. non-Gaussian input sequence a new iterative procedure based on phase-sensitive high-order cumulants for adjusting the coeƒcients of a transversal equalizer is introduced. The main feature of the proposed technique is the automatic selection of the equalization delay so as to improve the equalization performance. A method for the a posteriori evaluation of the obtained accuracy in PAM systems is also introduced. It consists of the computation of an upper bound on the probability of error depending on certain moments of the equalizer output and the statistics of the channel input and therefore can be used in a blind equalization context. Based on the result of such a computation, it can be decided whether it is necessary to consider a longer equalization filter in the iterative procedure. ( 1997 by John Wiley & Sons, Ltd.

With the recent development of tools for data sharing in social networks and peer to peer networks, the same information is often stored in different nodes. Peer-to-peer protocols usually allow one user to collect portions of the same file from different nodes in the network, substantially improving the rate at which data are received by the end user. In some cases, however, the same multimedia document is available in different lossy versions on the network nodes. In such situations, one may be interested in collecting all available versions of the same document and jointly decoding them to obtain a better reconstruction of the original. In this paper we study some methods to jointly decode different versions of the same image. We compare different uses of the method of Projections Onto Convex Sets (POCS) with some Convex Optimization techniques in order to reconstruct an image for which JPEG and JPEG2000 lossy versions are available.

This paper presents an algorithm based on a two-layer coding scheme, where the original information is represented by means of a Low Dynamic Range (LDR) image, obtained by applying a tone mapping operator to the original HDR (High Dynamic Range), plus an enhancement layer, which allows to recover the full dynamic range. More specifically, the original HDR is represented with a format similar to the well known RGBE, which uses a shared exponent to compactly represent floating point numbers. With respect to the original RGBE, here the mantissa is composed by an approximation of the LDR image while the shared exponent represents the enhancement layer. This particular choice allows to split the original HDR into a color image, the mantissa, and a grayscale image, the exponent, which are very smooth signals that can be efficiently compressed by conventional image coding methods. With respect to already proposed similar schemas, two desirable features are then provided: a high coding efficiency, combined with the possibility to retrieve a displayable version of the original content.

Keywords: LTS1 Reference LCAV-ARTICLE-1991-004doi:10.1016/1047-3203(91)90023-9 Record created on 2005-04-18, modified on 2017-05-12

In this paper we propose a revisitation of the topic of unique decodability and of some fundamental theorems of lossless coding. It is widely believed that, for any discrete source X, every "uniquely decodable" block code satisfies E[l(X_1 X_2 ... X_n)]>= H(X_1,X_2,...,X_n), where X_1, X_2,...,X_n are the first n symbols of the source, E[l(X_1 X_2 ... X_n)] is the expected length of the code for those symbols and H(X_1,X_2,...,X_n) is their joint entropy. We show that, for certain sources with memory, the above inequality only holds when a limiting definition of "uniquely decodable code" is considered. In particular, the above inequality is usually assumed to hold for any "practical code" due to a debatable application of McMillan's theorem to sources with memory. We thus propose a clarification of the topic, also providing an extended version of McMillan's theorem to be used for Markovian sources., Comment: Accepted for publication, IEEE Transactions on Information Theory

In the current video analysis scenario, effective clustering of shots facilitates the access to the content and helps in understanding the associated semantics. This paper introduces a cluster analysis on shots which employs dendrogram representation to produce hierarchical summaries of the video document. Vector quantization codebooks are used to represent the visual content and to group the shots with similar chromatic consistency. The evaluation of the cluster codebook distortions, and the exploitation of the dependency relationships on the dendrograms, allow to obtain only a few significant summaries of the whole video. Finally the user can navigate through summaries and decide which one best suites his/her needs for eventual post-processing. The effectiveness of the proposed method is demonstrated by testing it on a collection of video-data from different kinds of programmes. Results are evaluated in terms of metrics that measure the content representational value of the summarization technique.

A new QIM-based image watermarking system for still images is proposed. The new system is expressly designed to cope with non-linear value-metric scaling attacks such as histogram stretching and gamma correction. By recognizing that any value-metric scaling attack must not change the global appearance of the image, we argue that the watermark should be inserted into high level visual features. We move a first step into this direction by proposing a system embedding the watermark into the kurtosis of selected image blocks. Though the kurtosis is not strictly invariant against non-linear gain, its value tends to remain constant whenever the image content is not altered significantly. The experiments we carried out confirm the validity of the new system, though some problems still need to be solved to make it suitable for real applications.

Many second generation image coding techniques have been studied in recent years. Most of these methods consider the l/sub 2/ norm of the error introduced in the coded image, while for the l/sub /spl infin// case only predictive or transform based methods were considered up to now, focusing on near-lossless coding. In this paper we present a first scheme for l/sub /spl infin// norm in the framework of second generation image coding. The image is adaptively segmented into rectangular regions of varying size leading to a binary tree decomposition. The grey levels of the pixels within every leaf are approximated by means of l/sub /spl infin// sub-optimal bilinear surfaces.

In this paper we consider the use of variable length non prefix-free codes for coding constrained sequences of symbols. We suppose to have a Markov source where some state transitions are impossible, i.e. the stochastic matrix associated with the Markov chain has some null entries. We show that classic Kraft inequality is not a necessary condition, in general, for unique decodability under the above hypothesis and we propose a relaxed necessary inequality condition. This allows, in some cases, the use of non prefix-free codes that can give very good performance, both in terms of compression and computational efficiency. Some considerations are made on the relation between the proposed approach and other existing coding paradigms., Comment: 5 pages, 3 figures. To be presented at the 2005 IEEE International Symposium on Information Theory

In this work, an infinite impulse response (IIR) filtering framework for blind equalization of possibly non-minimum phase channels is proposed. The equalizer herein studied is an IIR generalization of the tapped delay line (TDL), called the Kautz filter, having as a transfer function a weighted sum of rational orthonormal functions on the unit circle. A procedure for blind estimation of the equalizer parameters (weights and poles), using higher order statistics (HOS) of the channel output, is presented. The weights are adjusted by means of a generalized version of the super-exponential (SE) method. The above method is combined with two algorithms for the pole selection. Simulation results demonstrate the advantages of the proposed method over TDL blind equalization.

We present a modified version of an embedded wavelet coding scheme, first suggested by Shapiro (see IEEE Transactions on Signal Processing, vol.41, no. 12, p.3445-3462, 1993), that improves the performance of the original algorithm in a visual subjective distortion sense. We preserve the features of the original Shapiro's embedded coder. It is possible to choose a fixed target bit rate, as the information needed to represent an image coded at some rate always contains the needed information for the same image coded at lower rates. Therefore, the decoder can cease decoding the bit stream at any point, simulating an image coded at a lower rate corresponding to the truncated bit stream. We also introduce some perceptive improvements by adopting different (more regular) filters with respect to the original QMF pyramid filters proposed by Simoncelli, Hingorani et al. (1987) and used by Shapiro. These filters are synthesized using a "wavelet approach" instead of a "subband approach", and this leads to a better control on their regularity properties, jointly with better perceptual performance.

Current wavelet-based image coders obtain high performance thanks to the identification and the exploitation of the statistical properties of natural images in the transformed domain. Zerotree-based algorithms, as Embedded Zerotree Wavelets (EZW) and Set Partitioning In Hierarchical Trees (SPIHT), offer high Rate-Distortion (RD) coding performance and low computational complexity by exploiting statistical dependencies among insignificant coefficients on hierarchical subband structures. Another possible approach tries to predict the clusters of significant coefficients by means of some form of morphological dilation. An example of a morphology-based coder is the Significance-Linked Connected Component Analysis (SLCCA) that has shown performance which are comparable to the zerotree-based coders but is not embedded. A new embedded bit-plane coder is proposed here based on morphological dilation of significant coefficients and context based arithmetic coding. The algorithm is able to exploit both intra-band and inter-band statistical dependencies among wavelet significant coefficients. Moreover, the same approach is used both for two and three-dimensional wavelet-based image compression. Finally we the algorithms are tested on some 2D images and on a medical volume, by comparing the RD results to those obtained with the state-of-the-art wavelet-based coders.

In this letter, an efficient morphological wavelet coder is proposed. The clustering trend of significant coefficients is captured by a new kind of multiresolution binary dilation operator. The layered and adaptive nature of the subband dilation makes it possible for the coding technique to produce an embedded bit-stream with a modest computational cost and state-of-the-art rate-distortion performance. Morphological wavelet coding appears promising because the localized analysis of wavelet coefficient clusters is adequate to capture intrinsic patterns of the source, which can have substantial benefits for reducing further the data redundancy.

We study the effects of the quantization of the three-dimensional wavelet transform coefficients, encoded using a 3D zerotree-based compression scheme. The processing of the quantization error operated by the synthesis filter bank actually determines a modulation of the reconstruction error statistics. This effect entails a non-negligible and potentially objectionable PSNR oscillation among adjacent slices of the decoded 3D data-set, which, e.g. in the biomedical field, would typically be used jointly to reach a diagnosis. In particular, we propose a cyclostationary model of the error statistics fluctuations and an experimental validation of the model itself. Moreover some strategies to reduce such oscillation are suggested and evaluated.

The segmentation of video sequences into regions underlying a coherent motion is one of the most important processing in video analysis and coding. In this paper, we propose a reliability measure that indicates to what extent an affine motion model represents the motion of an image region. This reliability measure is then proposed as a criterion to coherently merge moving image regions in a Minimum Description Length (MDL) framework. To overcome the region-based motion estimation and segmentation chicken and egg problem, the motion field estimation and the segmentation task are treated separately. After a global motion compensation, a local motion field estimation is carried out starting from a translational motion model. Concurrently, a Markov Random Field model based algorithm provides for an initial static image partition. The motion estimation and segmentation problem is then formulated in the view of the MDL principle. A merging stage based on a directed weighted graph gives the final spatio-temporal segmentation. The simulation results show the effectiveness of the proposed algorithm.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

The optical flow (OF) can be used to perform motion-based segmentation or 3D reconstruction. Many techniques have been developed to estimate the OF. Some approaches are based on global assumptions; others deal with local information. ALthough OF has been studied for more than one decade, reducing the estimation error is still a difficult problem. Generally, algorithms to determine the OF are based on an equation, which links the gradient components of the luminance signal, so as to impose its invariance over time. Therefore, to determine the OF, it is usually necessary to calculate the gradient components in space and time. A new way to approximate this gradient information from a spatio- temporal wavelet decomposition is proposed here. In other words, assuming that the luminance information of the video sequences be represented in a multiresolution structure for compression or transmission purposes, we propose to estimate the luminance gradient components directly from the coefficients of the wavelet transform. Using a multiresolution formalism, we provide a way to estimate the motion field at different resolution levels. OF estimates obtained at low resolution can be projected at higher resolution levels so as to improve the robustness of the estimation to noise and to better locate the flow discontinuities, while remaining computationally efficient. Results are shown for both synthetic and real-world sequences, comparing it with a non multiresolution approach.© (1997) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

This paper deals with the problem of recovering the input signal applied to a linear time-invariant system from the measures of its output and the a-priori knowledge of the input statistics (blind equalization). Under the assumption of an i.i.d. non-Gaussian input sequence, a new iterative procedure based on phase sensitive high-order cumulants for adjusting the coefficients of a transversal equalizer is introduced. The main feature of the proposed technique is that it realizes the automatic selection of the equalization delay so as to improve the equalization performance.

For low bit-rate compression applications, segmentation-based coding methods provide, in general, high compression ratios when compared with traditional (e.g., transform and subband) coding approaches. In this paper, we present a new segmentation-based image coding method that divides the desired image using binary space partitioning (BSP). The BSP approach partitions the desired image recursively by arbitrarily oriented lines in a hierarchical manner. This recursive partitioning generates a binary tree, which is referred to as the BSP-tree representation of the desired image. The most critical aspect of the BSP-tree method is the criterion used to select the partitioning lines of the BSP tree representation, In previous works, we developed novel methods for selecting the BSP-tree lines, and showed that the BSP approach provides efficient segmentation of images. In this paper, we describe a hierarchical approach for coding the partitioning lines of the BSP-tree representation. We also show that the image signal within the different regions (resulting from the recursive partitioning) can be represented using low-order polynomials. Furthermore, we employ an optimum pruning algorithm to minimize the bit rate of the BSP tree representation (for a given budget constraint) while minimizing distortion. Simulation results and comparisons with other compression methods are also presented.

In this abstract, we present a novel technique to encode video sequences, that performs a region-based motion compensation of each frame to be encoded so as to generate a predicted frame. The set of regions to be motion compensated for a given frame has been obtained through a quadtree segmentation of the motion field estimated between a single reference frame (representing a typical projection of the scene) and the frame to be encoded. This way, no DPCM loop in the temporal domain is introduced, avoiding the feedback of the quantization errors. Under the assumption that the projection of the scene on the image plane remains nearly constant, only slight deformations of the reference frame occur from one frame to the next, so that very limited information needs to be coded: (1) the segmentation shape; (2) the motion information. Temporal correlation is used to predict both types of information so as to further reduce any left redundancy. As the segmentation may not be perfect, spatial correlation may still exist between neighboring regions. This is used in the strategy designed to encode the motion information. The motion and segmentation information are estimated on the basis of a two stage process using the frame to be encoded and the reference frame: (1) a hierarchical top-down decomposition, followed by (2) a bottom-up merging strategy. This procedure can be nicely embedded in a quadtree representation, which ensures a computationally efficient but rather robust segmentation strategy. We show how the proposed method can be used to encode QCIF video sequences with a reasonable quality at a 10 frame/s rate using roughly 20 kbit/s. Different schemes for prediction are compared pointing the advantage of the single reference frame for both prediction and compensation.© (1995) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

An image coding technique based on symmetry extraction and Binary Space Partitioning (BSP) tree representation for still pictures is presented. Axes of symmetry, detected through a principal axis of inertia approach and a coefficient of symmetry measure, are used to divide recursively an input image into a finite number of convex regions. This recursive partitioning results in the BSP tree representation of the image data. The iterative partition occurs whenever the current left/right node of the tree cannot be represented `symmetrically' by its counterpart, i.e., the right/left node. This splitting process may also end whenever the region associated with a given node has homogeneous characteristics or its size falls below a certain threshold. Given a BSP tree partition for a given input image, and the `seed' leaf nodes (i.e., those that cannot be generated by mirroring their counterparts), the remaining leaf nodes of the tree are reconstructed using a predictive scheme with respect to the `seed' leaf nodes.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Keywords: LTS1 Reference LCAV-CONF-1991-007 Record created on 2005-04-18, modified on 2017-05-12

Keywords: LTS1 Reference LTS-CONF-1991-022 Record created on 2006-06-14, modified on 2016-08-08

A multiresolution method for constructing a BSP (binary space partitioning) tree is introduced. This approach derives a hierarchy (pyramid) of scale-space images from the original image. In this hierarchy, a BSP tree of an image is built from other trees representing low-resolution images of the pyramid. A low-resolution image BSP tree serves as an initial guess to construct a higher-resolution image tree. Due to filtering when constructing the pyramid, details are discarded. As a result, a more robust segmentation is obtained. Moreover a significant computational advantage is achieved. >

This paper presents an approximation algorithm for two-dimensional signals (e.g., images) using polynomial functions. The proposed algorithm is based on an adaptive segmentation of the original signal into adjacent regions and on the approximation of the signal in each region by a two-dimensional polynomial function. The segmentation is obtained by an adaptive region growing technique which allows perfect adaptation between the chosen approximation and the inner structure of the signal. Results of this technique are presented in the context of image coding applications.

Past work on unsupervised segmentation of a texture image has been based on several restrictive assumptions to reduce the difficulty of this challenging segmentation task. Typically, a fixed number of different texture regions is assumed and each region is assumed to be generated by a simple model. Also, different first order statistics are used to facilitate discrimination between different textures. This paper introduces an approach to unsupervised segmentation that offers promise for handling unrestricted natural scenes containing textural regions. A simple but effective feature set and a novel measure of dissimilarity are used to accurately generate boundaries between an unknown number of regions without using first order statistics or texture models. A two stage approach is used to partition a texture image. In the first stage, a set of sliding windows scans the image to generate a sequence of feature vectors. The windowed regions providing the highest inhomo-geneity in their textural characteristics determine a crude first-stage boundary, separating textured areas that are unambiguously homogeneous from one another. These regions are used to estimate a set of prototype feature vectors. In the second stage, supervised segmentation is performed to obtain an accurate boundary between different textured regions by means of a constrained hierarchical clustering technique. Each inhomo-geneous window obtained in the first stage is split into four identical subwindows for which the feature vectors are estimated. Each of the subwindows is assigned to a homogeneous region to which it is connected. This region is chosen according to the closest prototype vector in the feature space. Any two adjacent subwindows that are assigned to different regions will in turn be considered as inhomogeneous windows and each is then split into four subwindows. The classification scheme is repeated in this hierarchical manner until the desired boundary resolution is achieved. The technique has been tested on several multi-texture images yielding accu-rate segmentation results comparable or superior to the performance obtained by human visual segmentation.

In many image processing applications, the discrete values of an image can be embedded in a continuous function. This type of representation can be useful for interpolation, geometrica! transformations or special features extraction. Given a rectangular M x N discrete image (or sub-image), it is shown how to compute a continuous polynomial function that guarantees an exact fit at the considered pixei locations. The polynomials coefficients can be expressed as a linear one-to-one separable transform of the pixels. The transform matrices can be computed using a fast recursive algorithm which enables efficient inversion of a Vandermonde matrix. It is also shown that the least square polynomial approximation with M' x N' coefficients, in the separable formulation, involves the inversion of two M' x M' and N' x N' Hankel matrices. Zu~mmenf~ung. In mehreren Anwendungen der Bildverarbeitung krnnen digitale Bildgrauwerten als Teile ununter- brochenen Funktionen behandelt werden. Diese Darstellung gilt auch fiir Interpolation, geometrische Transformationen oder Ermittlung yon speziellen Formen. In diesem Artikei handelt es sich um die Verrechnung einer ununterbrochenen Polynom Funktion Ffir ein gegebenes rechteckiges digitales Biid, die eine genaue Interpolation in bestimmten Punkten ermfglicht. Die Polynomial Koeffizienten k~innen mit einer iinearen trennbaren Punkttransformation ermittelt werden. Die Transformation- matrizen sind mit einem schnellen rekursiven AIgorithmus erreichbar, mit dem eine Vandermondematrize einfach umgekehrt wird. Es wird auch gezeigt, dass die polynomiale Approximation der kleinsten Quadraten mit M' x N' Koeflizienten, im Fall eines rechtwinkligen Bild, zwei M' x M' and N' x N' Hankel Matrizen Umkehrungen ernrtigt. R~mr. Dans beaucoup d'applications du traitement des images, on peut considrrer les valeurs discrrtes d'une image numrrique comme faisant pattie d'une fonction continue. Ce type de reprrsentation peut 8tre utile pour l'interpolation, pour effectuer des transformations gromrtriques ou extraire des proprirtrs locales. I~tant donnre une image (ou sous-image) rectangulaire de dimension M x N donnre sous forme numrrique, on montre comment on peut trouver un polynSme garantissant une interpolation exacte des points de l'image. Les coefficients du polynrme sont obtenus au moyen d'une transformation linraire bijective srparable des points de l'image. Les matrices de cette transformation peuvent ~tre calculres en utiisant un algorithme rrcursif rapide qui permet rinversion efficace des matrices de Vandermonde. Dans un deuxirme temps, on expose comment trouver la meilleure approximation polynSmiale au sens des moindres carrrs avec M'x N' coefficients darts le cas d'une image rectangulaire, ce qui permet une formulation srparable du problrme. Le rrsuitat comprend notamment l'inversion de deux matrices carrres de Hankel de rang respectivement M' et N'.

A new way to improve the representation of images using a discrete wavelet transform for coding purposes is presented. The idea lies in combining all wavelet coefficients related to detail information at a same resolution level but along different orientations (horizontal, vertical, and diagonal), into a single image. Given that detail information is located for all subband images in the neighborhood of high frequency textures or edge locations, the pattern of significant coefficients remains unchanged after the combination process. This process allows one to further reduce the number of transformed coefficients by 2/3, while preserving the multiresolution structure. This information can thus be efficiently coded using a multiresolution embedded coding scheme, such as Shapiro's (see IEEE Trans. on Signal Proc., vol.SP-41, no.12, p.3445-62, 1993) zerotree coder. Overall, a higher coding efficiency can be reached while preserving the cross-scale prediction of significance among the coefficients. Ultimately, approximate detail information must be recovered from the combined and coded data for each subband of the original wavelet, so as to reconstruct a decoded image.

Efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (x/sub i/, y/sub i/), i=1..n, with x/sub i/