Detection and discrimination of seismic events have important implications. Precise detection of earthquakes may help prevent collateral damage and even save lives. On the other hand, the ability to identify explosions reliably not only helps prevent false alarms but also is crucial for monitoring nuclear experiments. In this work, we present a method for automatic discrimination of seismic events. A neural network is trained to fuse information from multiple seismic channels into a correlated space. Then, we augment the minority class to avoid class imbalance. Finally, a tree-based classifier is used to estimate the nature of the suspected event. We apply the proposed approach to 1609 events collected in Israel and Jordan. Our framework demonstrates improved precision and recall scores.

Sub-pixel objects are defined as objects which due to their size and due to the resolution of the camera occupy a fraction of a pixel or partially span adjacent pixels. Unsupervised detection of sub-pixel objects can be highly useful in areas such as medical imaging, and surveillance, to name a few. Hyper-spectral images offer extensive intensity information by describing a scene at hundreds and even thousands of wavelengths. This information can be utilized to obtain better sub-pixel detection results compared to those that are obtained using RGB images. Usually, only a small number of wavelengths contain the information that is required for the detection. Furthermore, the intensity images of many wavelengths are noisy and contain very little information. Accordingly, hyper-spectral images must be pre-processed first in order to extract the information that is needed for the sub-pixel detection. This extraction process produces an image where each pixel is represented by a small number of features which allows the application of fast and efficient detection algorithms. In this paper we propose the Diffusion Bases (DB) dimensionality reduction algorithm in order to derive the essential features for the sub-pixel detection. The effectiveness of the DB algorithm facilitates the application of a very simple algorithm for the detection of sub-pixel objects in the feature space. The proposed approach does not assume any distribution of the background pixels. We demonstrate the proposed framework for the detection of cardboard objects in airborne hyper-spectral images of a desert terrain.

The problem of learning from seismic recordings has been studied for years. There is a growing interest of developing automatic mechanisms for identifying the properties of a seismic event. One main motivation is the ability to have a reliable identification of man-made explosions. The availability of multiple high-dimensional observations has increased the use of machine learning techniques in a variety of fields. In this paper, we propose to use a kernel-fusion-based dimensionality reduction framework for generating meaningful seismic representations from raw data. The proposed method is tested on 2023 events that were recorded in Israel and Jordan. The method achieves promising results in the classification of event type as well as the estimation of the event location. The proposed fusion and dimensionality reduction tools may be applied to other types of geophysical data.

Broadcasting is a process in which an individual has an item of information which needs to be transmitted to all of the members in a network (which is viewed as a connected graph). k‐broadcasting is a variant of broadcasting in which each processor can transmit the message to up to k of its neighbors. Another variant of broadcasting is the concept of m‐time‐relaxed broadcasting, where we allow m additional time units, enabling one to decrease the number of edges in the communication network. The combination of m‐time‐relaxed and k‐broadcasting is studied in this article. The results shown here are an improvement on the upper bound obtained by Harutyunyan and Liestman, Discrete Math 262 (2003), 149–157, by constructing a connected graph, which admits m‐time‐relaxed k‐broadcasting for all n, and has fewer edges than the graph presented in Harutyunyan and Liestman, Discrete Math 262 (2003), 149–157. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 72–78 2017

The Nyström method is routinely used for out-of-sample extension of kernel matrices. We extend the applicability of this method and describe how it can be applied to find the singular value decomposition (SVD) of general matrices and the eigenvalue decomposition (EVD) of square matrices. We take as an input a matrix M ∈ Rm× n, a user defined integer s≤ min(m, n) and A_M ∈ Rs× s, a matrix sampled from the columns and rows of M. These are used to construct an approximate rank-s SVD of M in O(s^2(m+n)) operations. If M is square, the rank-s EVD can be similarly constructed in O(s^2 n) operations. The contribution of the proposed method is three-fold: first, it allows the compression of a general matrix M where the matrix A_M provides a compressed version of M. Second, it allows the approximation of the SVD and EVD when they cannot be directly calculated due to space and time limitations in case of large matrices. Third, a novel algorithm for selecting the initial sample is presented. The sample choice reduces the Nyström approximation error. We discuss the choice of A_M and propose an algorithm that selects a good initial sample for a pivoted version of $M$. The proposed algorithm performs well for general matrices and kernel matrices whose spectra exhibit fast decay.

Particle filter is a powerful tool for state tracking using non-linear observations. We present a multiscale based method that accelerates the tracking computation by particle filters. Unlike the conventional way, which calculates weights over all particles in each cycle of the algorithm, we sample a small subset from the source particles using matrix decomposition methods. Then, we apply a function extension algorithm that uses a particle subset to recover the density function for all the rest of the particles not included in the chosen subset. The computational effort is substantial especially when multiple objects are tracked concurrently. The proposed algorithm significantly reduces the computational load. By using the Fast Gaussian Transform, the complexity of the particle selection step is reduced to a linear time in n and k, where n is the number of particles and k is the number of particles in the selected subset. We demonstrate our method on both simulated and on real data such as object tracking in video sequences.

One of the main challenges in Computed Tomography (CT) is how to balance between the amount of radiation the patient is exposed to during scan time and the quality of the CT image. We propose a mathematical model for adaptive CT acquisition whose goal is to reduce dosage levels while maintaining high image quality at the same time. The adaptive algorithm iterates between selective limited acquisition and improved reconstruction, with the goal of applying only the dose level required for sufficient image quality. The theoretical foundation of the algorithm is nonlinear Ridgelet approximation and a discrete form of Ridgelet analysis is used to compute the selective acquisition steps that best capture the image edges. We show experimental results where for the same number of line projections, the adaptive model produces higher image quality, when compared with standard limited angle, non-adaptive acquisition algorithms.

In recent years, the theory of compressed sensing has emerged as an alternative for the Shannon sampling theorem, suggesting that compressible signals can be reconstructed from far fewer samples than required by the Shannon sampling theorem. In fact the theory advocates that nonadaptive, “random” functionals are in some sense optimal for this task. However, in practice, compressed sensing is very difficult to implement for large data sets, particularly because the recovery algorithms require significant computational resources. In this work, we present a new alternative method for simultaneous image acquisition and compression called adaptive compressed sampling. We exploit wavelet tree structures found in natural images to replace the “universal” acquisition of incoherent measurements with a direct and fast method for adaptive wavelet tree acquisition. The main advantages of this direct approach are that no complex recovery algorithm is in fact needed and that it allows more control over the compressed image quality, in particular, the sharpness of edges. Our experimental results show, by way of software simulations, that our adaptive algorithms perform better than existing nonadaptive methods in terms of image quality and speed.

Single Carrier FDMA (SC-FDMA) plays an important role in modern wireless communications as an alternative to OFDM mainly since it exhibits low peak-to-average power ratio. Accordingly, SC-FDMA is employed as the uplink scheme for the 3GPP long term evolution (LTE). In the presence of multipath, the SC-FDMA signal may arrive at the receiver perturbed by inter-symbol-interference, which renders the single-tap frequency-domain equalization suboptimal. Optimum maximum likelihood detection for SC-FDMA is often prohibitively complex, and hence useful mostly as a performance bound for suboptimal detection schemes. In this work, the optimum-detector performance is analyzed in detail; the analysis can be easily applied to any SC frequency-domain equalization scheme. Closed form bounds on the achievable bit error rate are provided for low and high SNR regimes in correlated and uncorrelated Rayleigh fading channels. The bounds reveal that the diversity order at high SNR is significantly smaller than in the low SNR regime. Moreover, error rate flaring behavior is demonstrated under optimum detection of SC-FDMA. The analytical results are verified by simulations.

The discrete Radon transform (DRT) was defined by Abervuch as an analog of the continuous Radon transform for discrete data. Both the DRT and its inverse are computable in O(n(2) log n) operations for images of size n × n. In this paper, we demonstrate the applicability of the inverse DRT for the reconstruction of a 2-D object from its continuous projections. The DRT and its inverse are shown to model accurately the continuum as the number of samples increases. Numerical results for the reconstruction from parallel projections are presented. We also show that the inverse DRT can be used for reconstruction from fan-beam projections with equispaced detectors.

With regard to the above paper (ibid., vol. 21, no. 2, pp. 733-741, Feb. 2012), a portion of the authors' corrections were not included before the work was finalized. These are detailed here.

We present a system for asynchronous replication of virtual machines (running on top of QEMU-KVM and Lguest). The system uses a home-grown block device replication layer for data replication and includes VM replication components for Lguest and QEMU-KVM. We describe both of these components in this paper. Unlike previous works in the field, we focus on low bit rate systems. We target environments with low band-width that make frequent migration impossible. We put bandwidth preservation and operation continuity at the top of our priorities. To this end we are willing to sacrifice performance in order to preserve decent operation continuity even in low bit rate environments. We focus on SOHO environments as our target market. SOHO environments are often characterized by low requirements for actual performance and disk usage. However, SOHO environments are also limited in bandwidth capacity, especially upstream. All of these are taken into careful consideration throughout this paper.

This paper presents Truly-protect, a system, incorporating a virtual machine, that enables execution of encrypted programs. Our intention is to form a framework for a conditional access/digital rights management system. We avoid relying on obscurity and rely only on assumptions about the system itself and on cryptographic measures to develop VM-based conditional access/trusted computing environment. Rolles in [18], proposes a general way of breaking systems of type described herein. We claim that Rolles' method fails to defeat our system.

In mobile networks emergence of failures is caused by various breakdowns of hardware and software elements. One of the serious failures in radio networks is a Sleeping Cell. In our work one of the possible root causes for appearance of this network failure is simulated in a dynamic network simulator. The main aim of the research is to detect the presence of a Sleeping Cell in the network and to define its location. For this purpose Diffusion Maps data mining technique is employed. The developed fault identification framework is using the performance characteristics of the network, collected during its regular operation, and for that reason it can be implemented in real Long Term Evolution (LTE) networks within the Self-Organizing Networks (SON) concept.

Image reconstruction from its projections is a necessity in many applications such as medical (CT), security, inspection, and others. This paper extends the 2-D Fan-beam method in [2] to 3-D. The algorithm, called Pyramid Beam (PB), is based upon the parallel reconstruction algorithm in [1]. It allows fast capturing of the scanned data, and in 3-D, the reconstructions are based upon the discrete X-ray transform [1]. The PB geometries are reordered to fit parallel projection geometry. The underlying idea is to use the algorithm in [1] by porting the proposed PB geometries to fit the algorithm in [1]. The complexity of the algorithm is comparable with the 3-D FFT. The results show excellent reconstruction qualities while being simple for practical use.

Multiple antenna techniques are used to enhance wireless links and therefore have been studied extensively. Many practical systems that differ from ideal schemes have been discussed in the literature. One example is a system that lacks precise channel information at the transmitter. We evaluate analytically the performance of a multiple input multiple output (MIMO) technique that uses partial channel knowledge. Specifically, we analyze a scheme with M transmit antennas and N receive antennas, employing eigenbeamforming at the transmitter and MRC at the receiver. We assume that only partial channel matrix is known to the transmitter, specifically only P out of N rows of the channel matrix are known. We derive the optimal beamformer for a single stream transmission case and show that it is the singular vector of the known channel submatrix. We show that the diversity order of a transmission scheme where such a precoder is used is MP+N-P and further show that increasing the value of P by one increases the diversity order by M-1. We also derive the array gain for this scheme. All the results are supported by simulations.

This paper shows how to compress (encode) losslessly, search and decompress (decode) textual data in a machine/device that has a limited memory (several kilobytes).

This paper describes a new and efficient method for low bit-rate image coding which is based on recent development in the theory of multivariate nonlinear piecewise polynomial approximation. It combines a binary space partition scheme with geometric wavelet (GW) tree approximation so as to efficiently capture curve singularities and provide a sparse representation of the image. The GW method successfully competes with state-of-the-art wavelet methods such as the EZW, SPIHT, and EBCOT algorithms. We report a gain of about 0.4 dB over the SPIHT and EBCOT algorithms at the bit-rate 0.0625 bits-per-pixels (bpp). It also outperforms other recent methods that are based on "sparse geometric representation." For example, we report a gain of 0.27 dB over the Bandelets algorithm at 0.1 bpp. Although the algorithm is computationally intensive, its time complexity can be significantely reduced by collecting a "global" GW n-term approximation to the image from a collection of GW trees, each constructed separately over tiles of the image.

XML is the standard format of content representation and sharing on the Web. XML is a highly verbose language, especially regarding the duplication of meta-data in the form of elements and attributes. As XML content is becoming more widespread so is the demand to compress XML data volume. The paper presents the best XML compression ratios reported to date. Its advantage over other XML compression techniques is that it uses syntactic information to enhance compression. Therefore, it is a fully syntactic based XML compression. The syntactic information is parsed from XML documents by an innovative XML parser. We developed a new XML parser-generator for that purpose. Our parser-generator is based on a syntactic dictionary (DTD, XML-Schema, etc.) of the XML in order to create an efficient and compact XML parsers. This XML parser-generator is adopted to streaming technologies and can be used in a wide variety of XML applications such as validators, converters, gateways, routers, browsers editors etc. The parsers' symbols are encoded by a partial prediction matching (PPM) codec. We compare between the performance of our algorithm and other existing XML compression techniques. The proposed compression algorithm achieves better compression ratio in comparison to other XML compression techniques that do not utilize syntactic structure. The superiority of our compression technique is more evident when it is tested on XML data sets that contain only tags and not free text

This paper presents an approach to the registration of significantly dissimilar images, acquired by sensors of different modalities. A robust matching criterion is derived by aligning the locations of gradient maxima. The alignment is achieved by iteratively maximizing the magnitudes of the intensity gradients of a set of pixels in one of the images, where the set is initialized by the gradient maxima locations of the second image. No explicit similarity measure that uses the intensities of both images is used. The computation utilizes the full spatial information of the first image and the accuracy and robustness of the registration depend only on it. False matchings are detected and adaptively weighted using a directional similarity measure. By embedding the scheme in a "coarse to fine" formulation, we were able to estimate affine and projective global motions, even when the images were characterized by complex space varying intensity transformations. The scheme is especially suitable when one of the images is of considerably better quality than the other (noise, blur, etc.). We demonstrate these properties via experiments on real multisensor image sets.

We present a method to enhance, by postprocessing, the performance of gradient-based edge detectors. It improves the performance of the edge detector by adding terms which are similar to the artificial dissipation that appear in the numerical solution of hyperbolic PDEs. This term is added to the output of the edge detector. The edges that are missed or blurred by the edge detector are reconstructed through the addition of the artificial dissipation terms. Edges that are detected correctly by the edge detector are preserved. We present the theory of the artificial dissipation and its improvement of the quality of the detected edges. We demonstrate the performance of the algorithm on diverse images.

Space-time block codes (STBCs) are designed for multiple-input-multiple-output (MIMO) channels. In order to avoid errors, single-input-single-output (SISO) fading channels require long coding blocks and interleavers that result in high delays. If one wishes to increase the data rate it is necessary to take advantage of space diversity. Early STBC, that where developed by Alamouti for known channels and by Tarokh for unknown channels, have been proven to increase the performance of channels characterized by Rayleigh fading. Codes that are based on division algebras have by definition nonzero diversity and therefore are suitable for STBC in order to achieve high rates at low symbol-to-noise ratio (SNR). This work presents new high-diversity group-based STBCs with improved performance both in known and unknown channels. We describe two new sets of codes for multiple antenna communication. The first set is a set of "superquaternions" and improves considerably on the Alamouti codes. It is based on the mathematical fact that "normalized" integral quaternions are very well distributed over the unit sphere in four-dimensional (4-D) Euclidean space. The second set of codes gives arrays of 3times3 unitary matrices with full diversity. Here the idea is to use cosets of finite subgroups of division algebras that are nine-dimensional (9-D) over their center, which is a finite cyclotomic extension of the field of rational numbers. It is shown that these codes outperform Alamouti and Gmr

We present an algorithm for the registration of rotated and translated volumes, which operates in the frequency domain. The Fourier domain allows to compute the rotation and translation parameters separately, thus reducing a problem with six degrees of freedom to two problems of three degrees of freedom each. We propose a three-step procedure. The first step estimates the rotation axis. The second computes the planar rotation relative to the rotation axis, and the third recovers the translational displacement by using the phase correlation technique. The rotation estimation is based on Euler's theorem, which allows to represent a rotation using only three parameters. Two parameters represent the rotation axis and one parameter represents the planar rotation perpendicular to the axis. By using the 3D pseudo-polar FFT, the estimation of the rotation axis is shown to be algebraically accurate. A variant of the angular difference function registration algorithm is derived for the estimation of the planar rotation around the axis. The experimental results show that the algorithm is accurate and robust to noise.

The estimation of large motions without prior knowledge is an important problem in image registration. In this paper we present the angular difference function (ADF) and demonstrate its applicability to rotation estimation. The ADF of two functions is defined as the integral of their spectral difference along the radial direction. It is efficiently computed using the pseudo-polar Fourier transform, which computes the discrete Fourier transform of an image on a near spherical grid. Unlike other Fourier based registration schemes, the suggested approach does not require any interpolation. Thus, it is more accurate and significantly faster.

We present an algorithm for aligning rotated and translated volumes, which operates in the frequency domain. The Fourier domain allows us to compute the rotation and translation parameters separately, thus reducing a problem with six degrees of freedom to two problems of three degrees of freedom each. We propose a three-step procedure. The first step estimates the rotation axis, the second computes the planar rotation relative to the rotation axis, and the third recovers the translational displacement by using the phase correlation technique. By using the 3-D pseudo-polar FFT, the estimation of the rotation axis is shown to be algebraically accurate. Experimental results show that the algorithm is accurate and robust to noise.

The estimation of large motions without prior knowledge is an important problem in image registration. In this paper, we present the angular difference function (ADF) and demonstrate its applicability to rotation estimation. The ADF of two functions is defined as the integral of their spectral difference along the radial direction. It is efficiently computed using the pseudopolar Fourier transform, which computes the discrete Fourier transform of an image on a near spherical grid. Unlike other Fourier-based registration schemes, the suggested approach does not require any interpolation. Thus, it is more accurate and significantly faster.

A new class of related algorithms for deblocking block-transform compressed images and video sequences is proposed in this paper. The algorithms apply weighted sums on pixel quartets, which are symmetrically aligned with respect to block boundaries. The basic weights, which are aimed at very low bit-rate images, are obtained from a two-dimensional function which obeys predefined constraints. Using these weights on images compressed at higher bit rates produces a deblocked image which contains blurred "false" edges near real edges. We refer to this phenomenon as the ghosting effect. In order to prevent its occurrences, the weights of pixels, which belong to nonmonotone areas, are modified by dividing each pixel's weight by a predefined factor called a grade. This scheme is referred to as weight adaptation by grading (WABG). Better deblocking of monotone areas is achieved by applying three iterations of the WABG scheme on such areas followed by a fourth iteration which is applied on the rest of the image. We refer to this scheme as deblocking frames of variable size (DFOVS). DFOVS automatically adapts itself to the activity of each block. This new class of algorithms produces very good subjective results and PSNR results which are competitive relative to available state-of-the-art methods.

One of the major challenges related to image registration is the estimation of large motions without prior knowledge. This paper presents a Fourier-based approach that estimates large translations, scalings, and rotations. The algorithm uses the pseudopolar (PP) Fourier transform to achieve substantial improved approximations of the polar and log-polar Fourier transforms of an image. Thus, rotations and scalings are reduced to translations which are estimated using phase correlation. By utilizing the PP grid, we increase the performance (accuracy, speed, and robustness) of the registration algorithms. Scales up to 4 and arbitrary rotation angles can be robustly recovered, compared to a maximum scaling of 2 recovered by state-of-the-art algorithms. The algorithm only utilizes one-dimensional fast Fourier transform computations whose overall complexity is significantly lower than prior works. Experimental results demonstrate the applicability of the proposed algorithms.

In this paper. we design a new family of biorthogonal wavelet transforms and describe their applications to still image compression. The wavelet transforms are constructed from various types of interpolatory and quasiinterpolatory splines. The transforms use finite impulse response and infinite impulse response filters that are implemented in a fast lifting mode.

Gradient-based motion estimation methods (GMs) are considered to be in the heart of state-of-the-art registration algorithms, being able to account for both pixel and subpixel registration and to handle various motion models (translation, rotation, affine, and projective). These methods estimate the motion between two images based on the local changes in the image intensities while assuming image smoothness. This paper offers two main contributions. The first is enhancement of the GM technique by introducing two new bidirectional formulations of the GM. These improve the convergence properties for large motions. The second is that we present an analytical convergence analysis of the GM and its properties. Experimental results demonstrate the applicability of these algorithms to real images.

This paper presents an implicit similarity-based approach to registration of significantly dissimilar images, acquired by sensors at different modalities. The proposed algorithm introduces a robust matching criterion by aligning the locations of gradient maxima. The alignment is formulated as a parametric variational optimization problem, which is solved iteratively by considering the intensities of a single image. The location of the maxima of the second image's gradient are used as initialization. We are able to robustly estimate affine and projective global motions using 'coarse to fine' processing, even when the images are characterized by complex space varying intensity transformations. Finally, we present the registration of real images, which were taken by multi-sensor and multi-modality using affine and projective motion models.

This paper suggests a novel contour-based algorithm for tracking moving objects in a video sequence. The algorithm uses the segmentation results of the input frames, which are represented by two region adjacency graphs (RAG) data structures. Based on the image segmentation result, the object's contour is divided into subcurves while junctions of the contour are derived. The junctions are being matched in a search area that is the RAG edges of the consecutive frame. Each pair of matched junctions may be connected by several of paths (edges) that are candidates to represent the tracked contour. Using algorithm for finding the k-shortest paths between two nodes these paths are obtained. Then, the construction of the tracked contour is done by a matching process between edges, which are the subcurves, and sets of candidate paths. The use of RAG to construct the tracked contour enables an accurate representation of the moving object while preserving efficient complexity.

This paper presents a fast global motion estimation (GME) algorithm based on gradient methods (GM), which can be used for real-time applications, such as in MPEG4 video compression. This approach improves the existing state-of-the-art GME algorithms by introducing two major modifications: first, only a small subset (down to 3%) of the original image pixels is used in the estimation process. Second, an interpolation-free formulation of the basic GM is derived, further decreasing the computational complexity. Experimental results show no loss of GME accuracy and compression efficiency compared to the MPEG-4 verification model, while reducing the computational complexity of the GME by a factor of 20.

We present a new unified approach to FFT based image registration. Prior works divided the registration process into two stages: the first was based on phase correlation (PC) which provides pixel accurate registration [5], while the second step provides subpixel registration accuracy [1, 3]. By extending the PC method we derive a FFT based image registration algorithm which is able to estimate large translations with subpixel accuracy. The algorithm's properties resemble those of the Gradient Methods [4] while outperforming it by exhibiting superior convergence range.

Gradient based motion estimation techniques (GM) are considered to be in the heart of state-of-the-art registration algorithms [2], being able to account for both pixel and subpixel registration and to handle various motion models (translation, rotation, affine, projective). These methods estimate the motion between two images based on the local changes in the image intensities while assuming image smoothness. This paper introduces two new bidirectional formulations of the GM, improving the convergence properties for large motions. Experimental results demonstrate the applicability of these algorithms to real images.

A new algorithm for the removal of blocking artifacts in block-DCT compressed images and video sequences is proposed in this paper. The algorithm uses deblocking frames of variable size (DFOVS). A deblocking frame is a square of pixels which overlaps image blocks. Deblocking is achieved by applying weighted summation on pixels quartets which reside in deblocking frames. The pixels in a quartet are symmetrically aligned with respect to block boundaries. The weights are determined according to a special 2-D function and a predefined factor, we refer to as a grade. A pixel's grade is determined according to the amount of details in its neighborhood. Deblocking of monotone areas is achieved by iteratively applying deblocking frames of decreasing sizes on such areas. This new algorithm produces very good subjective results and PSNR results which are competitive relative to available state-of-the-art methods.

This paper presents a fast global motion estimation (GME) algorithm based on gradient methods (GM), which can be used for real-time applications, such as MPEG-4 video compression. Our approach improves existing state-of-the-art GME algorithms by introducing two major modifications: first, only a small subset (down-to 3%) of the original image pixels is used in the estimation process. Second, a warp-free formulation of the basic GM is derived, further decreasing the computational complexity. Experimental results show that a 20 fold computation complexity reduction is achieved, without compromising the GME accuracy and compression efficiency.

The emerging video coding standard MPEG-4 enables various content-based functionalities for multimedia applications. To support such functionalities, as well as to improve coding efficiency, MPEG-4 relies on a decomposition of each frame of an image sequence into video object planes (VOP). Each VOP corresponds to a single moving object in the scene. This paper presents a new method for automatic segmentation of moving objects in image sequences for VOP extraction. We formulate the problem as graph labeling over a region adjacency graph (RAG), based on motion information. The label field is modeled as a Markov random field (MRF). An initial spatial partition of each frame is obtained by a fast, floating-point based implementation of the watershed algorithm. The motion of each region is estimated by hierarchical region matching. To avoid inaccuracies in occlusion areas, a novel motion validation scheme is presented. A dynamic memory, based on object tracking, is incorporated into the segmentation process to maintain temporal coherence of the segmentation. Finally, a labeling is obtained by maximization of the a posteriori probability of the MRF using motion information, spatial information and the memory. The optimization is carried out by highest confidence first (HCF). Experimental results for several video sequences demonstrate the effectiveness of the proposed approach.

The main contribution of this work is a new paradigm for image representation and image compression. We describe a new multilayered representation technique for images. An image is parsed into a superposition of coherent layers: piecewise smooth regions layer, textures layer, etc. The multilayered decomposition algorithm consists in a cascade of compressions applied successively to the image itself and to the residuals that resulted from the previous compressions. During each iteration of the algorithm, we code the residual part in a lossy way: we only retain the most significant structures of the residual part, which results in a sparse representation. Each layer is encoded independently with a different transform, or basis, at a different bitrate, and the combination of the compressed layers can always be reconstructed in a meaningful way. The strength of the multilayer approach comes from the fact that different sets of basis functions complement each others: some of the basis functions will give reasonable account of the large trend of the data, while others will catch the local transients, or the oscillatory patterns. This multilayered representation has a lot of beautiful applications in image understanding, and image and video coding. We have implemented the algorithm and we have studied its capabilities.

This paper addresses the problem of segmentation of moving objects in image sequences, which is of key importance in content-based applications. We transform the problem into a graph labeling problem over a region adjacency graph (RAG), by introducing a Markov random field (MRF) model based on spatio-temporal information. The initial partition is obtained by fast, color-based watershed segmentation. The motion of each region is estimated and validated in a hierarchical framework. A dynamic memory, based on object tracking, is incorporated into the segmentation process to maintain temporal coherence. The performance of the algorithm is evaluated on several real-world image sequences.

We present wavelet based video compression algorithms. The motion estimation and compensation, which is an essential part in the compression, is based on segment movements. The proposed codec sequentially employs the following steps. We first divide each frame in the sequence into blocks resulted from the block matching algorithm. Then we apply the Hough transform, in order to group it into segments. Each segment contains blocks that have similar motion parameters. We estimate the motion parameters for each segment using several motion models and least-squares algorithms and apply motion compensation upon the frames in each group. In the wavelet domain an optimal vector bit allocation is used to distribute the bit budget among consecutive frames. The manipulated frames in each group are quantized and coded using techniques from still image compression. The residual error of the compression is reduced by applying error correction in the wavelet domain to enhance the quality of the reconstructed sequence.

We present a new family of biorthogonal wavelet transforms and a related library of biorthogonal symmetric wavelets. For the construction we use the interpolatory discrete splines which enable us to design perfect reconstruction filter banks related to the Butterworth filters. The construction is performed in a "lifting" manner. The proposed scheme is based on interpolation and, as such, it involves only samples of signals and it does not require any use of quadrature formulas. These filters have linear phase property. The filters yield perfect frequency resolution.

Abstract Broadcasting is the process of transmitting a message from a member in a network (originator) to all other members. A line‐broadcasting scheme allows two members to communicate during one time unit as long as there is a path of lines between them and no link is used in more than one call between two members. Farley [3] showed an algorithm that accomplishes line broadcasting in any tree on n vertices in minimum time, which is ⌈log 2 n ⌉ time units. Since the structure of the tree is unknown in advance, the total number of communication link uses (cost) of his scheme is Θ ( n − 1) ⌈log 2 n ⌉. In this paper, we present line‐broadcasting schemes for complete binary trees. The cost of the algorithms is linear in the number of vertices. This answers a question raised by Fujita and Farley [5]. © 2001 John Wiley & Sons, Inc.

We present a video coder based on a bit allocation (BA) scheme for a coding approach where a wavelet-based video compression scheme is used to encode a group of frames (GOF). The proposed new BA method utilizes a Lagrangian multiplier technique to determine the optimal bit rate for each frame of a given GOF in a rate versus weighted distortion sense. The proposed baseline coder sequentially employs the application of the wavelet transform on each frame in the group. In the wavelet domain, an optimal-vector BA (rate-allocation strategy) is being used to distribute the bit budget among the frames. The manipulated frames in each group are quantized and coded using techniques from still-image compression. We describe and demonstrate the performance of the proposed algorithm in wavelet-based coding approaches. The first one, a combination of wavelet still compression and optimal BA (WCBA), is based on frame differences and exploits well the wavelet compression characteristics which keeps, for a given bit budget, the most important features. It does not utilize motion-compensation interpolation or a 3-D wavelet decomposition. In cases where "heavy" motion is detected, we extend WCBA into a combination of wavelet still compression, optimal BA, motion compensation with block matching, and error correction (WCBAM), which uses block matching for motion estimation, while the residual error of the compression is reduced by applying error correction in the wavelet domain to reduce temporal redundancies.

Compression is a relatively new introduced technique for seismic data operations. The main drive behind the use of data compression in seismic data is the very large size of seismic data acquired. Some of the most recent acquired marine seismic data sets exceed 10 Tbytes, and in fact there are currently seismic surveys planned with a volume of around 120 Tbytes. Thus, the need to compress these very large seismic data files is imperative. Nevertheless, seismic data are quite different from the typical images used in image processing and multimedia applications. Some of their major differences are the data dynamic range exceeding 100 dB in theory, very often it is data with extensive oscillatory nature, the x and y directions represent different physical meaning, and there is significant amount of coherent noise which is often present in seismic data. Up to now some of the algorithms used for seismic data compression were based on some form of wavelet or local cosine transform, while using a uniform or quasiuniform quantization scheme and they finally employ a Huffman coding scheme. Using this family of compression algorithms we achieve compression results which are acceptable to geophysicists, only at low to moderate compression ratios. For higher compression ratios or higher decibel quality, significant compression artifacts are introduced in the reconstructed images, even with high-dimensional transforms. The objective of this paper is to achieve higher compression ratio, than achieved with the wavelet/uniform quantization/Huffman coding family of compression schemes, with a comparable level of residual noise. The goal is to achieve above 40 dB in the decompressed seismic data sets. Several established compression algorithms are reviewed, and some new compression algorithms are introduced. All of these compression techniques are applied to a good representation of seismic data sets, and their results are documented in this paper. One of the conclusions is that adaptive multiscale local cosine transform with different windows sizes performs well on all the seismic data sets and outperforms the other methods from the SNR point of view. All the described methods cover wide range of different data sets. Each data set will have his own best performed method chosen from this collection. The results were performed on four different seismic data sets. Special emphasis was given to achieve faster processing speed which is another critical issue that is examined in the paper. Some of these algorithms are also suitable for multimedia type compression.

In this paper we investigate architectures that combine message-passing and shared-memory technologies, called hereinafter hybrid architectures. We introduced hybrid architectures in which large buses of the shared-memory are split into a number of small high-performance shared-memory blocks, which are connected via message-passing architecture, such as hypercube, grid or ring. This way we avoid the possible degradation of the achieved performance due to the fact that the bus performance does not scale well when the number of processors it connects increases. We study the saturation situations of several hybrid network architectures, where adding processors does not reduce the overall execution time. We show that the use of hybrid network architectures leads to significant improvement of the systems price/performance ratio, by significantly improving the performance with almost no system cost increment. Therefore, the usage of hybrid architectures demonstrates how minimal ‘cost’ spending could significantly increase the system performance. In addition, we show that different types of applications have different best hybrid architectures. Copyright © 2000 John Wiley & Sons, Ltd.

Wavelets are ill-suited to represent oscillatory patterns: rapid variations of intensity can only be described by the small scale wavelet coefficients, which are often quantized to zero, even at high bit rates. Our goal is to provide a fast numerical implementation of the best wavelet packet algorithm in order to demonstrate that an advantage can be gained by constructing a basis adapted to a target image. Emphasis is placed on developing algorithms that are computationally efficient. We developed a new fast two-dimensional (2-D) convolution decimation algorithm with factorized nonseparable 2-D filters. The algorithm is four times faster than a standard convolution-decimation. An extensive evaluation of the algorithm was performed on a large class of textured images. Because of its ability to reproduce textures so well, the wavelet packet coder significantly out performs one of the best wavelet coder on images such as Barbara and fingerprints, both visually and in term of PSNR.

This paper deals with the problem of scheduling spawned tasks when a query is issued to a database which resides on a MIMD multiprocessor. These tasks have the property that their associated dependency scheme can be presented as a directed tree. We present a theoretical framework with extensive experimental simulations which increase the throughput of database applications. We derive a family of algorithms for scheduling tasks. Their performance is tested on several common multiprocessor configurations. For better performance the adaptation of the scheduling algorithm to the multiprocessor configuration is examined and analyzed. The scheduling algorithms are divided into two cases: (a) permitted changes in the resources connection scheme of the multiprocessor, and (b) no changes allowed. The algorithms are scalable and their complexity is computed. In particular, we present an algorithm for scheduling tasks in the case where the construction of a central storage location is permitted. One of the main tools for the construction of the above algorithms is the notion of (t, 1)-domination and k-domination sets. Copyright © 1999 John Wiley & Sons, Ltd.

Summary form only given. Presents a new fast wavelet packet compression algorithm that encodes very efficiently textured images. This fast wavelet packet compression technique relies on four stages: 1. Very fast convolution and decimation of the image with factorized filters. 2. Selection of a best basis in a large library of waveforms. The best basis is that basis which is best adapted to the content of the image. 3. Scanning of the wavelet packet coefficients by increasing frequency. This organization yields sequences of coefficients with a rapid decay. 4. Successive embedded approximation quantization, and entropy coding of the coefficients. We implemented the wavelet packet coder and decoder, and actual bit streams were created for each experiment. Our implementation used the 7-9 biorthogonal filters. We present the results of the algorithm, using the test image 512 x 512 Barbara. In order to evaluate the performance of the algorithm, we compared our algorithm to the SPIHT wavelet coder of Said and Pearlman (1996).

We describe a new multi-layered representation technique for images. An image is encoded as the superposition of one main approximation, and a sequence of residuals. The strength of the multi-layered method comes from the fact that we use different bases to encode the main approximation and the residuals. The different bases complement each others: some of the basis functions will give reasonable account of the large trend of the data, while others will catch the local transients, or the oscillatory patterns. By selecting different bases, we allow different features to be discovered in the image.

Multicast has become popular in recent years with the introduction of new, very fast networks. Existing solutions of the multicast design and implementation problems are either inefficient in microkernel environments or too expensive in terms of the host operating system overhead involved. In our search for a new solution we investigate various aspects of the problem. Exploring the desired semantics, we come to the conclusion that control functions, group maintenance algorithms and various ordering semantics can be implemented on top of the basic services, and that the efficiency of these implementations is less critical than that of the basic services. We describe a few naive solutions to supporting multicast in microkernels and show their limitations. Then we suggest a new solution to the problem and show analytically that it is significantly better than other solutions. The solution we decided to implement is a hybrid solution supporting control operations in user space and data operations in the kernel. It enables the semantics of multicast or group communication abstractions to be separated from the operating system support and mechanisms used to implement those abstractions. Since we propose an efficient solution while introducing minimal changes to the Mach kernel, our hybrid solution suggests splitting the group communication burden between the microkernel and a group server (GS). To implement our hybrid solution the Mach kernel has been modified. Finally, we present an implementation of our new solution for the Mach 3.0 microkernel environment and show a very significant measured speedup in performance of multicast operations over naive methods for multicasting. © 1998 John Wiley & Sons, Ltd.

A portable parallelization of the Cooley–Tukey FFT algorithm for MIMD multiprocessors is presented. The implementation uses the virtual machine for multiprocessors (VMMP) and PVM portable software packages. Since VMMP provides the same set of services on all target machines, a single version of the parallel FFT code was used for shared memory (25-processor Sequent Symmetry), shared bus (MOS-running distributed UNIX) and distributed memory multiprocessor (transputer network and 64-processor IBM SP2). It is accompanied with detailed performance analysis of the implementations. The algorithm achieved high efficiencies on all target machines. The analysis indicates that most overheads are caused by the target architecture and not by VMMP or PVM inefficiencies. The portability analysis of the FFT provides several important insights. On the message passing architecture, the parallel FFT algorithm can obtain linearly increasing speedup with respect to the number of processors with only a moderate increase in the problem size. The parallel FFT can be executed by any number of processors, but generally the number of processors is much less than the length of the input data. The results indicate that the parallel FFT is portable: it achieves very good speedups on either a shared memory multiprocessor with high memory bandwidth or on a message passing multiprocessor without any change in the programs. © 1998 John Wiley & Sons, Ltd.

We construct a new algorithm for motion compensation of wavelet coefficients. The new approach outperforms standard block matching techniques both in terms of higher PSNR, and better perceptual quality. The algorithm works directly in the wavelet coefficients domain and has been successfully used for wavelet based very low bit rate video coding.

The Portable Parallelizing Fortran Compiler (PPFC) is an additional component for the portable programming environment developed in Tel-Aviv University for scientific code. This environment supports portable and efficient programming of diverse MIMD multiprocessors, both distributed- and shared-memory. Till now this environment has consisted of two tools: the Virtual Machine for MultiProcessors (VMMP) and the Portable Parallelizing Pascal compiler (P3C). We have added the PPFC which is an automatic parallelizer compiler for the Fortran language. The compiler is fully automatic (does not require additional declarations to assist parallelization), which is characterized by loops operating on regular data structures, and produces efficient and portable code for a variety of multiprocessors from the same serial code. The parallel implementation uses the VMMP, which is a software package that provides a coherent set of services for explicitly parallel application programs running on diverse MIMD multiprocessors. VMMP is intended to simplify parallel program writing and to promote portable and efficient programming. The PPFC parallelized 12 out of the 24 Livermore Loops. It was also applied to parallelize all the 14 Fortran application programs that where parallelized by the P3C and achieved the same speed-ups and efficiencies. In most examples the PPFC achieved high speed-ups and efficiencies on all target multiprocessors. The PPFC emphasizes efficiency and code portability. Although PPFC employs a relatively simple data flow analysis, it produces efficient code for various widely used application programs.

Schemes for image compression of black-and-white images based on the wavelet transform are presented. The multiresolution nature of the discrete wavelet transform is proven as a powerful tool to represent images decomposed along the vertical and horizontal directions using the pyramidal multiresolution scheme. The wavelet transform decomposes the image into a set of subimages called shapes with different resolutions corresponding to different frequency bands. Hence, different allocations are tested, assuming that details at high resolution and diagonal directions are less visible to the human eye. The resultant coefficients are vector quantized (VQ) using the LGB algorithm. By using an error correction method that approximates the reconstructed coefficients quantization error, we minimize distortion for a given compression rate at low computational cost. Several compression techniques are tested. In the first experiment, several 512x512 images are trained together and common table codes created. Using these tables, the training sequence black-and-white images achieve a compression ratio of 60-65 and a PSNR of 30-33. To investigate the compression on images not part of the training set, many 480x480 images of uncalibrated faces are trained together and yield global tables code. Images of faces outside the training set are compressed and reconstructed using the resulting tables. The compression ratio is 40; PSNRs are 30-36. Images from the training set have similar compression values and quality. Finally, another compression method based on the end vector bit allocation is examined.

Abstract The use of a massively parallel machine is aimed at the development of applications programs to solve most significant scientific, engineering, industrial and commercial problems. High‐performance computing technology has emerged as a powerful and indispensable aid to scientific and engineering research, product and process development, and all aspects of manufacturing. Such computational power can be achieved only by massively parallel computers. It also requires a new and more effective mode of interaction between the computational sciences and applications and those parts of computer science concerned with the development of algorithms and software. We are interested in using parallel processing to handle large numerical tasks such as linear algebra problems. Yet, programming such systems has proven itself to be very complicated, error‐prone and architecture‐specific. One successful method for alleviating this problem, a method that worked well in the case of the massively pipelined supercomputers, is to use subprogram libraries. These libraries are built to efficiently perform some basic operations, while hiding low‐level system specifics from the programmer. Efficiently porting a library to a new hardware, be it a vector machine or a shared memory or message passing based multiprocessor, is a major undertaking. It is a slow process that requires an intimate knowledge of the hardware features and optimization issues. We propose a scheme for the creation of portable implementations of such libraries. We present an implementation of BLAS (basic linear algebra subprograms), which is used as a standard linear algebra library. Our parallel implementation uses the virtual machine for multiprocessors (VMMP) (1990), which is a software package that provides a coherent set of services for explicitly parallel application programs running on diverse MIMD multiprocessors, both shared memory and message passing. VMMP is intended to simplify parallell program writing and to promote portable and efficient programming. Furthermore, it ensures high portability of application programs by implementating the same services on all target multiprocessors. Software created using this scheme is automatically efficient on both categories of MIMD machines, and on any hardware VMMP has been ported to. An additional level of abstraction is achieved using the programming language C++, an object‐oriented language. Eckel, Stroustrup, 1989, 1986). For the programmer who is using BLAS‐3, it is hiding both the data structures used to define linear algebra objects, and the parallel nature of the operations performed on these objects. We coded BLAS on top of VMMP. This code was run without any modifications on two shared memory machines‐the commercial Sequent Symmetry and the experimental Taunop. (The code should run on any machine the VMMP was ported onto, given the availability of a C++ compiler). Performance results for this implementation are given. The speed‐up of the BLAS‐3 routines, tested on 22 processors of the Sequent, was in the range of 8.68 to 15.89. Application programs (e.g. Cholesky factorization) using the library routines achieved similar efficiency.

The performances of the Viterbi and the interacting multiple model (IMM) algorithms applied to radar tracking and detection are investigated and compared. In the first case considered, target acceleration is identical to one of the system models, while in the second case it is not. The algorithm performance depends monotonically on the maximal magnitude of the difference between the model acceleration, on the time interval between measurements, and on the reciprocal of the measurement error standard deviation. In general, when these parameters are relatively large, both algorithms perform well. When they are relatively small, the Viterbi algorithm is better. However, during delay periods, namely right after the start of a maneuver, the IMM algorithm provides better estimations.>

The implementations of the Viterbi algorithm (VA) and the interacting multiple model (IMM) algorithm on a shared-bus and shared-memory multiple-input multiple-data (MIMD) multiprocessor are discussed. The computational complexity as well as the speedup and efficiency are examined in detail. It is shown that the computational complexity of the parallel implementation of these algorithms is about the same in both memory space and processing time categories. Efficiency with P processors is about 1-1/P for small P and is expected to be relatively high for large P, especially when many filters and large state and measurement vectors are considered.>

General high-resolution smoothing techniques for estimating deterministic sinusoidal frequencies from short-record noisy data are presented. These techniques are general in the sense that methods such as the modified least squares Prony method, as well as those which are based on eigenvector decompositions, may be considered as special cases of them. The theoretical basis of these smoothing techniques is discussed, and their performance in the presence of white Gaussian noise at low signal-to-noise ratio (SNR) is examined. It is shown that close to the threshold of the maximum-likelihood method (SNR approximately=3 dB) these symmetric smoothing techniques provide better accuracy than any other current method.>

The Speech Recognition Group at IBM Research in Yorktown Heights has developed a real-time, isolated-utterance speech recognizer for natural language based on the IBM Personal Computer AT and IBM Signal Processors. The system has recently been enhanced by expanding the vocabulary from 5,000 words to 20,000 words and by the addition of a speech workstation to support usability studies on document creation by voice. The system supports spelling and interactive personalization to augment the vocabularies. This paper describes the implementation, user interface, and comparative performance of the recognizer.

The Speech Recognition Group at IBM Research in Yorktown Heights has designed a real-time, isolated-utterance speech recognizer for natural language with a 5,000-word vocabulary based on the IBM Personal Computer (PC) AT model and two IBM Signal Processors realized in VLSI technology. The enrollment period for a new user is approximately 20 minutes. The basic vocabulary is chosen from the most common words in several collections of documents such as office memoranda and business letters. The system supports spelling and interactive personalization to augment this vocabulary. Signal processing, vector quantization, and acoustic matching algorithms are programmed on the IBM Signal Processors which fit into the PC AT chassis. The PC AT controls the Processors and implements the decoder stack search and the language model, as well as the application-specific interface. The modular architecture of the design is expandable to a 20,000-word vocabulary system by the addition of two more IBM Signal Processors housed in a PC Expansion Unit.