Search

The atrial fibrillation burden (AFB) is defined as the percentage of time spend in atrial fibrillation (AF) over a long enough monitoring period. Recent research has demonstrated the added prognosis value that becomes available by using the AFB as compared with the binary diagnosis. We evaluate, for the first time, the ability to estimate the AFB over long-term continuous recordings, using a deep recurrent neutral network (DRNN) approach. Methods: The models were developed and evaluated on a large database of p=2,891 patients, totaling t=68,800 hours of continuous electrocardiography (ECG) recordings acquired at the University of Virginia heart station. Specifically, 24h beat-to-beat time series were obtained from a single portable ECG channel. The network, denoted ArNet, was benchmarked against a gradient boosting (XGB) model, trained on 21 features including the coefficient of sample entropy (CosEn) and AFEvidence. Data were divided into training and test sets, while patients were stratified by the presence and severity of AF. The generalizations of ArNet and XGB were also evaluated on the independent test PhysioNet LTAF database. Results: the absolute AF burden estimation error |E_AF|, median and interquartile, on the test set, was 1.2 (0.1-6.7) for ArNet and 3.1 (0.0-11.7) for XGB for AF individuals. Generalization results on LTAF were consistent with E_AF of 2.6 (1.1-14.7) for ArNet and 3.6 (1.0-16.7) for XGB. Conclusion: This research demonstrates the feasibility of AFB estimation from 24h beat-to-beat interval time series utilizing recent advances in DRNN. Significance: The novel data-driven approach enables robust remote diagnosis and phenotyping of AF.

We present a new quantitative method for detecting changes in 3D medical images. The dissimilarity between shapes is quantified as a measure of the effort it takes to deform one 3D region into another. Our main tool is an assessment of conformal and isometric distortions of mappings between volumes. Unlike most existing techniques for shape comparison, our algorithm operates both on triangular and tetrahedral meshes, and therefore can be applied both for closed simply connected surfaces, as well as for volumetric domains homeomorphic to a ball, with geometrically complicated boundaries. Furthermore we extend our main geometric distortion measure to higher dimensions, in a manner that allows for the dealing with spatial data at the maximal, as well as at all the lower dimensions.

This paper concerns processing, analysis and classification of fully-textured images, which contain both natural stochastic texture (NST) and structured information (SI). Whereas the fractal attributes of Gaussianity and self-similarity, that characterize purely NST, are fully represented by the spatial spectrum, and the corresponding spatial phase of the NST is random, the structural, edge-and-curve-type, information is mostly represented by the local spatial phase. We therefore decompose textured images into two layers, corresponding to the NST and SI, respectively. We show that the extent to which the texture obeys the fractal property of self-similarity, can be assessed by the mutual information that exists between scales. The phase of this layer, in the spatial Fourier domain, is random and exhibit approximately uniform distribution. We confirm this random behavior using the Kolmagorov-Smirnov hypothesis testing framework. We proceed to construct a classification space that combines features/dimensions that characterize the two layers of the stochastic (fBm-type spectrum) and deterministic (phase) attributes of partial spatial information, and address the implementation of this space in classification of fully-textured images encountered in modeling and analysis of images in various fields by providing an example.

Piecewise Fractional Brownian motion (p-fBm) is a continuous non-stationary Gaussian process having stationary Gaussian increments, named piecewise fractional Gaussian noise (p-fGn). Unlike fractional Brownian motion (fBm) governed by a unique parameter (Hurst exponent), p-fBm is defined by three parameters: the Hurst exponent in low frequencies, the Hurst exponent in high frequencies and the threshold frequency, which separates the two regimes. In this paper, we present a synthesis method that generates a finite approximation of p-fBm series. Moreover, we analyze the synthesized p-fBm series and test the Gaussianity of both p-fBm and p-fGn. We test the stationarity of the first order increments (p-fGn) and explore an approach to estimation of the process Hurst parameters. Our contribution is relevant to modeling and analysis of certain textures that are characteristic of certain medical and other natural images.

Finite field multipliers are embedded in many applications. In some applications, e.g., in cryptographic primitives protected by security oriented codes, only $r$ bits out of the $m$ -bit product are required. In such cases, the circuit area can be significantly reduced by implementing a punctured finite field multiplier. This article deals with efficient implementation of multipliers. It is shown that the number of binary operations (equivalently, the number of gates) depends on both the chosen irreducible polynomial that defines the finite field and the indices of the $r$ coordinates that are computed. Upper and lower bounds are presented on the implementation cost of punctured multipliers over a finite field defined by an irreducible trinomial, and a set of $r$ coordinates that achieves the lower bound is itemized.

A popular measure used in service systems is that of total absolute deviation of job completion times (TADC). It is relevant to settings where the objective is to balance the level of service provided to different customers. During the last decade, TADC has been studied in various machine settings, and under various assumptions on the job processing times. In this note, we study TADC on a two-machine no-wait proportionate flow shop, i.e. a flow shop with machine-independent processing times, and with no buffer between the machines. A very surprising and unique result is introduced: a simple index policy (the well-known largest processing time (LPT) first sequence) is shown to be optimal for instances of no more than seven jobs. This property does not hold for larger instances. We show that for instances of eight and nine jobs, there are exactly two schedules which are candidates for optimality. For the 10-job instance, the number of candidates increases. This uncommon behaviour of the optimal solution and...

A generic model of automatic gain control (AGC) is proposed as a general framework for multidimensional automatic contrast sensitivity adjustment in vision, as well as in other sensory modalities. We show that a generic feedback AGC mechanism, incorporating a nonlinear synaptic interaction into the feedback loop of a neural network, can enhance and emphasize important image attributes, such as curvature, size, depth, convexity/concavity and more, similar to its role in the adjustment of photoreceptors and retinal network sensitivity over the extremely high dynamic range of environmental light intensities, while enhancing the contrast. We further propose that visual illusions, well established by psychophysical experiments, are a by-product of the multidimensional AGC. This hypothesis is supported by simulations implementing AGC, which reproduce psychophysical data regarding size contrast effects known as the Ebbinghaus illusion, and depth contrast effects. Processing of curvature by an AGC network illustrates that it is an important mechanism of image structure pre-emphasis, which thereby enhances saliency. It is argued that the generic neural network of AGC constitutes a universal, parsimonious, unified mechanism of neurobiological automatic contrast sensitivity control. This mechanism/model can account for a wide range of physiological and psychophysical phenomena, such as visual illusions and contour completion, in cases of occlusion, by a basic neural network. Likewise, and as important, biologically motivated AGC provides attractive new means for the development of intelligent computer vision systems.

We address the challenging open problem of blindly separating time/position varying mixtures, and attempt to separate the sources from such mixtures without having prior information about the sources or the mixing system. Unlike studies concerning instantaneous or convolutive mixtures, we assume that the mixing system (medium) is varying in time/position. Attempts to solve this problem have mostly utilized, so far, online algorithms based on tracking the mixing system by methods previously developed for the instantaneous or convolutive mixtures. In contrast with these attempts, we develop a unified approach in the form of staged sparse component analysis (SSCA). Accordingly, we assume that the sources are either sparse or can be "sparsified." In the first stage, we estimate the filters of the mixing system, based on the scatter plot of the sparse mixtures' data, using a proper clustering and curve/surface fitting. In the second stage, the mixing system is inverted, yielding the estimated sources. We use the SSCA approach for solving three types of mixtures: time/position varying instantaneous mixtures, single-path mixtures, and multipath mixtures. Real-life scenarios and simulated mixtures are used to demonstrate the performance of our approach.

The phase of natural images represents structural information related to edges and contours, and plays a more important role than magnitude in this regard. The phase of stochastic textures is, however, commonly assumed to be random due to the consideration of a stochastic texture as a random process. In this study we show that phase information in textures can indeed be useful. We analyze the phase of 2D signals and propose a texture deconvolution algorithm, based on the magnitude and phase properties of textures. The algorithm is compared to a state-of-the-art algorithm.

We establish an error estimate for counting lattice points in Euclidean norm balls (associated to an arbitrary irreducible linear representation) for lattices in simple Lie groups of real rank at least two. Our approach utilizes refined spectral estimates based on the existence of universal pointwise bounds for spherical functions on the groups involved. We focus particularly on the case of the special linear groups where we give a detailed proof of error estimates which constitute the first improvement of the best current bound established by Duke, Rudnick and Sarnak in 1991, and are nearly twice as good in some cases.

Natural stochastic textures (NSTs), characterized by their fine details, are prone to corruption by artifacts, introduced during the image acquisition process by the combined effect of blur and noise. While many successful algorithms exist for image restoration and enhancement, the restoration of natural textures and textured images based on suitable statistical models has yet to be further improved. We examine the statistical properties of NST using three image databases. We show that the Gaussian distribution is suitable for many NST, while other natural textures can be properly represented by a model that separates the image into two layers; one of these layers contains the structural elements of smooth areas and edges, while the other contains the statistically Gaussian textural details. Based on these statistical properties, an algorithm for the denoising of natural images containing NST is proposed, using patch-based fractional Brownian motion model and regularization by means of anisotropic diffusion. It is illustrated that this algorithm successfully recovers both missing textural details and structural attributes that characterize natural images. The algorithm is compared with classical as well as the state-of-the-art denoising algorithms.

When integrating geo-spatial data sets, a join algorithm is used for finding sets of corresponding objects (i.e., objects that represent the same real-world entity). This article investigates location-based join algorithms for integration of several data sets. First, algorithms for integration of two data sets are presented and their performances, in terms of recall and precision, are compared. Then, two approaches for integration of more than two data sets are described. In one approach, all the integrated data sets are processed simultaneously. In the second approach, a join algorithm for two data sets is applied sequentially, either in a serial manner, where in each join at least one of the joined data sets is a single source, or in a hierarchical manner, where two join results can be joined. For the two approaches, join algorithms are given. The algorithms are designed to perform well even when location of objects are imprecise and each data set represents only some of the real-world entities. Results of extensive experiments with the different approaches are provided and analyzed. The experiments show the differences, in accuracy and efficiency, between the approaches, under different circumstances. The results also show that all our algorithms have much better accuracy than applying the commonly used one-sided nearest-neighbor join.

This paper investigates a graph enumeration problem, called the maximal P-subgraphs problem, where P is a hereditary or connected-hereditary graph property. Formally, given a graph G, the maximal P-subgraphs problem is to generate all maximal induced subgraphs of G that satisfy P. This problem differs from the well-known node-deletion problem, studied by Yannakakis and Lewis [J. Lewis, On the complexity of the maximum subgraph problem, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 265–274; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proc. 10th Annual ACM Symposium on Theory of Computing, ACM Press, New York, USA, 1978, pp. 253–264; J. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (2) (1980) 219–230]. In the maximal P-subgraphs problem, the goal is to produce all (locally) maximal subgraphs of a graph that have property P, whereas in the node-deletion problem, the goal is to find a single (globally) maximum size subgraph with property P. Algorithms are presented that reduce the maximal P-subgraphs problem to an input-restricted version of this problem. These algorithms imply that when attempting to efficiently solve the maximal P-subgraphs problem for a specific P, it is sufficient to solve the restricted case. The main contributions of this paper are characterizations of when the maximal P-subgraphs problem is in a complexity class C (e.g., polynomial delay, total polynomial time).

The Mumford-Shah functional and related algorithms for image segmentation involve a tradeoff between a two-dimensional image structure and one-dimensional parametric curves (contours) that surround objects or distinct regions in the image. We propose an alternative functional that is independent of parameterization; it is a geometric functional given in terms of the surfaces representing the data and image in the feature space. The Γ-convergence technique is combined with the minimal surfaces theory to yield a global generalization of the Mumford-Shah segmentation function.

The aim of this study was to use a new approach to investigate aeolian particle granulometry and micromorphology. Taking total aeolian deposition into account, we used parameters such as, particle area, perimeter, shape analysis for particle roughness (area/perimeter) and elongation (long/short axis). These parameters were analyzed on temporal and spatial scales at four study sites in the eastern Negev Desert, Israel. The total collection of particles was sorted into three size groups based on particle area to facilitate comparison. The classic definition of particle size (equating particle length with particle diameter) produced relatively small variations among the three size classes (25-38.6%). Our proposed comprehensive method demonstrated significant variation among the three size classes (13.9-60.8%), e.g. the classic method placed 36.4% of the particles in size class two while the new method placed 60.8% of the particles in this size class; the differences were even more significant regarding size class 3 (38.6% vs. 13.9%, respectively). The classic method did not facilitate investigation of particle roughness and elongation. With this new approach, it was possible to clearly define the particles by size class, based on these characteristics. With roughness, the variation among size classes 2 and 3 was about 27%. With elongation, the variation among size classes two and three was about 21%. Applying similar investigation method to study the aeolian particle granulometry and micromorphology can better facilitate more detailed calculation of particle size distribution, roughness and elongation.

A method and algorithm of flattening folded surfaces, for two-dimensional representation and analysis of medical images, are presented. The method is based on an application to triangular meshes of classical results of Gehring and Vaisala regarding the existence of quasi-conformal and quasi-isometric mappings. The proposed algorithm is basically local and, therefore, suitable for extensively folded surfaces encountered in medical imaging. The theory and algorithm guarantee minimal distance, angle and area distortion. Yet, the algorithm is relatively simple, robust and computationally efficient, since it does not require computational derivatives. Both random-starting-point and curvature-based versions of the algorithm are presented. We demonstrate the algorithm using medical data obtained from real CT images of the colon and MRI scans of the human cortex. Further applications of the algorithm, for image processing in general are also considered. The globality of this algorithm is also studied, via extreme length methods for which we develop a technique of computing straightest geodesics on polyhedral surfaces.

Multiwindow Gabor representations highlight fingerprints suitable for indexing of macromolecules, based on their local periodic structures. This paper presents a technique for analysis, and comparison of DNA and protein sequences. We use local periodicities to compare sequences and develop techniques that can compare the similarity between sequences in the combined space. We further show that using correlation, and absolute error minimization between the query sequence and sequences in the database, one can search for sequences very efficiently. Thus, from the viewpoint of indexing (and otherwise), macromolecules are much simpler to deal with than images, in that a much more limited, and well-defined dictionary is sufficient for labeling the molecules.

An affine-group-based design methodology of Gabor-type filter bank is presented for the purpose of image analysis and synthesis. Various tessellations of the combined spatial-feature space are considered. We combine ideas introduced by Daugman [J.G. Daugman, Uncertainty relation for resolution in space, spatial frequency, and orientation optimized by two-dimensional visual cortical filters, J. Opt. Soc. Am. 2 (7) (1985) 1160–1169], Lee [T.S. Lee, Image representation using 2D Gabor-wavelets, IEEE Trans. PAMI 18 (10) (1996) 959–971] and Manjunath and Ma [B.S. Manjunath, W.Y. Ma, Texture features browsing and retrieval of image data, IEEE Trans. PAMI 18 (8) (1996) 837–842], and extend them by applying the action of the full affine group on Gaborian-type mother wavelets. In this approach we adopt optimality criteria of minimal spatial-features combined uncertainty, as well as tightness of the frame tessellating this combined space. In this work, scalings in the x and y directions, allowing for independent dilations in these two directions, as well as rotations and translations are allowed. For each discrete set of scalings, rotations and translations the frame bounds are calculated. For frames where the frame operator is well approximated by a multiple of the identity, we use the same set of functions in the analysis and synthesis, as though the frame is equivalent to an orthogonal basis. Moreover, we show that in the case of independent scalings in the x and y directions, the number of dominant (characteristic) orientations of the filter bank may depend on scale. We further show that the orientation bandwidths thus obtained, resemble those attained under the constraint imposed by the uncertainty principle.

In signal processing, communications, and other branches of information technologies, it is often desirable to map the higher-dimensional signals on Sn. In this article we introduce a novel method of representing signals on Sn. This approach is based on geometric function theory, in particular on the theory of quasiregular mappings. The importance of sampling is underlined, and new geometric sampling theorems for general manifolds are presented.

A class of noncanonical duals for multiwindow Gabor (MWG) schemes, encompassing both rational and integer oversampling of the Gaborian combined time-frequency space, is considered. Using properties of Gabor frame matrices (GFM), block discrete Fourier transforms (BDFTs), and results from number theory, we use matrix factorization to establish existence conditions for noncanonical duals for both integer and rational oversampling rates, in the signal domain. For comparison and completeness of the results, we also obtain the equivalent results in the finite Zak transform (FZT) domain.

The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extension of the binary outerjoin operator to an arbitrary number of relations and is a useful operator for information integration. This paper presents the algorithm IncrementalFD for computing the full disjunction of a set of relations. IncrementalFD improves upon previous algorithms for computing the full disjunction in four ways. First, it has a lower total runtime when computing the full result and a lower runtime when computing only k tuples of the result, for any constant k. Second, for a natural class of ranking functions, IncrementalFD can be adapted to return tuples in ranking order. Third, a variation of IncrementalFD can be used to return approximate full disjunctions (which contain maximal approximately join consistent tuples). Fourth, IncrementalFD can be adapted to have a block-based execution, instead of a tuple-based execution.

Processing and classification of color Natural Stochastic Textures (NST) are of importance in various facets of image restoration, enhancement and pattern recognition. Existing denoising and deblurring algorithms produce over-smoothed images with sharp edges, but do not restore the fine textural color details. A recently proposed color-NST model, endowed with a small number of parameters, is extended and used for deblurring and denoising via a linear maximum-a-posteriori (MAP) scheme. The restored images exhibit better textural details than those recovered by other algorithms. Orientation and coherence-based features are combined with the color-NST model for classification, showing improvement over algorithms implementing only isotropic and color-based features.

Curvature is a fundamental component in differential geometry. It is used extensively in signal, image and shape processing, as a feature and in segmentation flows and regularization processes. In this paper we extend the notion of curvature in two ways. First, we present the Menger curvature which goes beyond classical curves and Riemannian manifolds to general metric spaces and is rigorously defined on a variety of discrete settings. We further extend the curvature to become a non-local entity using an adaptive, non-local integration measure, allowing curvature to be computed in a robust manner. Examples on natural and textural images highlight potential applications of these new concepts.

Denoising of Natural Stochastic Colored-Textures (color NST) is of special interest in image processing. Existing algorithms produce over-smoothed images with sharp edges, and do not restore the fine textural color details. We analyze the structure of color NST images and propose a simple model. This model is Gaussian and has a low number of parameters that can be estimated efficiently. A maximum-a-posteriori (MAP) scheme is proposed for patch-wise denoising of color NST. The denoised images exhibit better restored textural details compared to existing algorithms. A boosting algorithm is proposed for denoising of complex images containing both cartoon-type and textural image components.

The uncertainty principle is a fundamental concept in the context of signal and image processing, just as much as it has been in the framework of physics and more recently in harmonic analysis. Uncertainty principles can be derived by using a group theoretic approach. This approach yields also a formalism for finding functions which are the minimizers of the uncertainty principles. A general theorem which associates an uncertainty principle with a pair of self-adjoint operators is used in finding the minimizers of the uncertainty related to various groups. This study is concerned with the uncertainty principle in the context of the Weyl-Heisenberg, the SIM(2), the Affine and the Affine-Weyl-Heisenberg groups. We explore the relationship between the two-dimensional affine group and the SIM (2) group in terms of the uncertainty minimizers. The uncertainty principle is also extended to the Affine-Weyl-Heisenberg group in one dimension. Possible minimizers related to these groups are also presented and the scale-space properties of some of the minimizers are explored.

Denoising algorithms based on gradient dependent regularizers, such as nonlinear diffusion processes and total variation denoising, modify images towards piecewise constant functions. Although edge sharpness and location is well preserved, important information, encoded in image features like textures or certain details, is often compromised in the process of denoising. We propose a mechanism that better preserves fine scale features in such denoising processes. A basic pyramidal structure-texture decomposition of images is presented and analyzed. A first level of this pyramid is used to isolate the noise and the relevant texture components in order to compute spatially varying constraints based on local variance measures. A variational formulation with a spatially varying fidelity term controls the extent of denoising over image regions. Our results show visual improvement as well as an increase in the signal-to-noise ratio over scalar fidelity term processes. This type of processing can be used for a variety of tasks in partial differential equation-based image processing and computer vision, and is stable and meaningful from a mathematical viewpoint.

We address the issue of textured image segmentation in the context of the Gabor feature space of images. Gabor filters tuned to a set of orientations, scales and frequencies are applied to the images to create the Gabor feature space. A two-dimensional Riemannian manifold of local features is extracted via the Beltrami framework. The metric of this surface provides a good indicator of texture changes and is used, therefore, in a Beltrami-based diffusion mechanism and in a geodesic active contours algorithm for texture segmentation. The performance of the proposed algorithm is compared with that of the edgeless active contours algorithm applied for texture segmentation. Moreover, an integrated approach, extending the geodesic and edgeless active contours approaches to texture segmentation, is presented. We show that combining boundary and region information yields more robust and accurate texture segmentation results.

Objective The Enriched Semantic Network (ESN) was introduced as an extension of the Unified Medical Language System (UMLS) Semantic Network (SN). Its multiple subsumption configuration and concomitant multiple inheritance make the ESN's relationship structures and semantic type assignments different from those of the SN. A technique for deriving the relationship structures of the ESN's semantic types and an automated technique for deriving the ESN's semantic type assignments from those of the SN are presented. Design The technique to derive the ESN's relationship structures finds all newly inherited relationships in the ESN. All such relationships are audited for semantic validity, and the blocking mechanism is used to block invalid relationships. The mapping technique to derive the ESN's semantic type assignments uses current SN semantic type assignments and preserves nonredundant categorizations, while preventing new redundant categorizations. Results Among the 426 newly inherited relationships, 326 are deemed valid. Seven blockings are applied to avoid inheritance of the 100 invalid relationships. Sixteen semantic types have different relationship structures in the ESN as compared to those in the SN. The mapping of semantic type assignments from the SN to the ESN avoids the generation of 26,950 redundant categorizations. The resulting ESN contains 138 semantic types, 149 IS-A links, 7,303 relationships, and 1,013,876 semantic type assignments. Conclusion The ESN's multiple inheritance provides more complete relationship structures than in the SN. The ESN's semantic type assignments avoid the existing redundant categorizations appearing in the SN and prevent new ones that might arise due to multiple parents. Compared to the SN, the ESN provides a more accurate unifying semantic abstraction of the UMLS Metathesaurus.

The fundamental problem of denoising and deblurring images is addressed in this study. The great difficulty in this task is due to the ill-posedness of the problem. We analyze multi-channel images to gain robustness and regularize the process by the Poly- akov action, which provides an anisotropic smoothing term that uses inter-channel information. Blind deconvolution is then solved by an additional anisotropic regularization term of the same type for the ker- nel. It is shown that the Beltrami regularizer leads to better results than the total variation (TV) regularizer. An analytic comparison to the TV method is carried out and results on synthetic and real data are

Image sharpening in the presence of noise is formulated as a non-convex variational problem. The energy functional incorporates a gradient-dependent potential, a convex fidelity criterion and a high order convex regularizing term. The first term attains local minima at zero and some high gradient magnitude, thus forming a triple well-shaped potential (in the one-dimensional case). The energy minimization flow results in sharpening of the dominant edges, while most noisy fluctuations are filtered out.

Signal and image enhancement is considered in the context of a new type of diffusion process that simultaneously enhances, sharpens, and denoises images. The nonlinear diffusion coefficient is locally adjusted according to image features such as edges, textures, and moments. As such, it can switch the diffusion process from a forward to a backward (inverse) mode according to a given set of criteria. This results in a forward-and-backward (FAB) adaptive diffusion process that enhances features while locally denoising smoother segments of the signal or image. The proposed method, using the FAB process, is applied in a super-resolution scheme. The FAB method is further generalized for color processing via the Beltrami flow, by adaptively modifying the structure tensor that controls the nonlinear diffusion process. The proposed structure tensor is neither positive definite nor negative, and switches between these states according to image features. This results in a forward-and-backward diffusion flow where different regions of the image are either forward or backward diffused according to the local geometry within a neighborhood.

Semistructured data occur in situations where information lacks a homogeneous structure and is incomplete. Yet, up to now the incompleteness of information has not been reflected by special features of query languages. Our goal is to investigate the principles of queries that allow for incomplete answers. We do not present, however, a concrete query language. Queries over classical structured data models contain a number of variables and constraints on these variables. An answer is a binding of the variables by elements of the database such that the constraints are satisfied. In the present paper, we loosen this concept in so far as we allow also answers that are partial; that is, not all variables in the query are bound by such an answer. Partial answers make it necessary to refine the model of query evaluation. The first modification relates to the satisfaction of constraints: in some circumstances we consider constraints involving unbound variables as satisfied. Second, in order to prevent a proliferation of answers, we only accept answers that are maximal in the sense that there are no assignments that bind more variables and satisfy the constraints of the query. Our model of query evaluation consists of two phases, a search phase and a filter phase. Semistructured databases are essentially labeled directed graphs. In the search phase, we use a query graph containing variables to match a maximal portion of the database graph. We investigate three different semantics for query graphs, which give rise to three variants of matching. For each variant, we provide algorithms and complexity results. In the filter phase, the maximal matchings resulting from the search phase are subjected to constraints, which may be weak or strong. Strong constraints require all their variables to be bound, while weak constraints do not. We describe a polynomial algorithm for evaluating a special type of queries with filter constraints, and assess the complexity of evaluating other queries for several kinds of constraints. In the final part, we investigate the containment problem for queries consisting only of search constraints under the different semantics.

Conformal and their natural generalization to quasi-conformal mappings of surfaces, have been extensively and successfully employed in various tasks of Computer Graphics and Imaging. Due to the intrinsic differences between surfaces and objects from higher dimensions, many important results on surfaces can not be directly generalized to produce desirable mapping of volumes. Moreover, in dimension higher than 2, there are no conformal maps apart from Mobius transformations. Therefore, most of the real-world applications generate only quasi-conformal transformations, which produce some conformal distortion. Hence it is tempting and natural to measure the quality of volume deformation by the amount of a conformal distortion it produces. In this paper we examine theoretical properties of quasi-conformal mappings in 3D. We apply those conclusion to process discrete volumetric data in the terms of conformality. We present numerical methods to measure “the degree of conformality” of a transformation between a given pair of domains, represented by volumetric meshes.

Applications of anisotropic diffusion equation to texture enhancement have shown that an image can be smoothed while preserving high frequency features like edges. However, preserving textures still remains challenging. One way to preserve textures is by adding an extra term to the diffusion equation. This additional term can be interpreted as a potential, similar to the role of Schrodinger's potential in the complex diffusion equation, or as a reaction term in a reaction-diffusion process. We show the effect of such potentials on texture denoising, highlighting that anisotropic diffusion with potential combines properties of diffusion (piecewise-smoothing) and potential (enhancing fine structures) filters. Simulations performed on pure texture samples indicate that the reconstruction depends on the type of texture and the transform operator used in the potential. The diffusion-with-potential approach is extended. Local and nonlocal results show that nonlocal diffusion improves the quality of denoising.

Unlike the well-established fact of non-Gaussian, highly kurtotic, statistical property that characterizes the general class of natural images, a wide class of Natural Stochastic Textures (NST) obeys, to a good approximation, Gaussianity. This is exploited in denoising, resolution enhancement, analysis, modelling and classification of textures and textured images. Denoising is performed by decomposition to cartoon and textural layers. A fractal model is used to restore the latter. Deconvolution is performed via a variational scheme in the frequency domain, using phase and long-range dependency properties of NST.

Enhancement of Natural Stochastic Textures (NST) is of special interest in image processing. These textures are considered to be realizations of random processes, and exhibit different statistical properties than those characteristic of cartoontype natural images or of structured textures. NSTs are interesting due to their fine details, which pose a challenge to enhancement algorithms. Existing algorithms, based on models of natural images, do not produce satisfactory results on NST. The long-range dependence (LRD) property of NST is explored and substantiated in this paper. An optimization scheme, implemented in the frequency domain, is then proposed. This scheme exploits the LRD as a property of the frequency magnitude, while a desired phase, extracted from the degraded image, is imposed. The scheme is general and can be further used in other image processing tasks. Zero-phase filters are of special interest in this context.

Coverage is a fundamental problem in robotics, where one or more robots are required to visit each point in a target area at least once. While most previous work concentrated on finding a solution that completes the coverage as quickly as possible, in this paper we consider a new version of the problem: adversarial coverage. Here, the robot operates in an environment that contains threats that might stop the robot. We introduce the problem of finding the safest adversarial coverage path, and present different optimization criteria for the evaluation of these paths. We show that finding an optimal solution to the safest coverage problem is NP-Complete. We therefore suggest two heuristic algorithms: STAC, a spanningtree based coverage algorithm, and GSAC, which follows a greedy approach. These algorithms produce close to optimal solutions in polynomial time. We establish theoretical bounds on the total risk involved in the coverage paths created by these algorithms and on their lengths. Lastly, we compare the effectiveness of these two algorithms in various types of environments and settings.

Statistics of natural images has become an important subject of research in recent years. The highly kurtotic, non-Gaussian, statistics known to be characteristic of many natural images are exploited in various image processing tasks. In this paper, we focus on natural stochastic textures (NST) and substantiate our finding that NST have Gaussian statistics. Using the well-known statistical self-similarity property of natural images, exhibited even more profoundly in NST, we exploit a Gaussian self-similar process known as the fractional Brownian motion, to derive a fBm-PDE-based singleimage superresolution scheme for textured images. Using the same process as a prior, we also apply it in denoising of NST.

Texture enhancement presents an ongoing challenge, in spite of the considerable progress made in recent years. Whereas most of the effort has been devoted so far to enhancement of regular textures, stochastic textures that are encountered in most natural images, still pose an outstanding problem. The purpose of enhancement of stochastic textures is to recover details, which were lost during the acquisition of the image. In this paper, a texture model, based on fractional Brownian motion (fBm), is proposed. The model is global and does not entail using image patches. The fBm is a self-similar stochastic process. Self-similarity is known to characterize a large class of natural textures. The fBm-based model is evaluated and a single-image regularized superresolution algorithm is derived. The proposed algorithm is useful for enhancement of a wide range of textures. Its performance is compared with single-image superresolution methods and its advantages are highlighted.

We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present can also be used to push constraints from a given query to the EDB predicates. In showing our decidability results we describe a powerful tool, the query-tree, which is used for several optimization problems for datalog programs. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠.

Datalog (i.e., functiondfree logic) programs with monotonicity constraints on extensional predicates are considered. A monotonicity constraint states that one argument of a predicate or a constant is always less than another argument or a constant, according to some strict partial order. Relations of an extensional database are required to satisfy the monotonicity constraints imposed on their predicates. More specifically, a strict partial order is defined on the domain (i.e., set of constants) of the database, and every tuple of each relation satisfies the monotonicity constraints imposed on its predicate. This paper focuses on the problem of entailment of monotonicity constraints in the intensional database from monotonicity constraints in the extensional database. The entailment problem is proven to be decidable, based on a suggested algorithm for computing sound and complete disjunctions of monotonicity and equality constraints that hold in the intentional database. It is also shown that the entailment of monotonicity constraints in programs is a complete problem for exponential time. For linear programs, this problem is complete for polynomial space.

The paper aims to use the knowledge about how the visual system organizes the components of oculomotor system to propose a new tracking paradigm. The tracking system is assumed to be described by linear time-invariant discrete-time state-space equations. The approach described, motivated by the behavior of the visual system, is to switch off the smooth controller whenever a violation occurs and design a time-optimal control action, i.e., a "saccade", to drive the control system so that the constraint is satisfied after the shortest possible time interval. After that, the smooth controller is switched back into the loop. The way this switching is performed is critical for obtaining "good behavior". A method is proposed which is based on a careful definition of the target set for the saccade. The tracking system proposed in this paper is closely related to recent results in linear optimal and robust control theory.

A perfect reconstruction pair of synthesis and analysis filter banks define a frame and dual frame of l2, respectively. The discrete wavelet transform, and multiresolution analysis, can be viewed as the application of a non-uniform filter bank, defined by a uniform filter bank. The polyphase matrix representation of the corresponding frame operator is given for general oversampled wavelet-type filter banks. The issue of lower and upper frame bounds is treated, and bounds are given in a few special cases. It is shown that, contrary to the critical sampling case, a one-level tight frame does not in general produce a tight multilevel wavelet-type frame. The relation of the tightness of the wavelet type frame to the one level filter bank frame is investigated, and examples are presented, demonstrating the application of the results.

A technique for color image enhancement based on a model of the human visual system (HVS) is presented. A color image represented byRGBis first transformed into a color space based on the HVS cone response characteristics. Subsequently, chromatic correlation reduction and energy compression is realized by using a multispectral Karhunen?Loeve transform (KLT) of the cone responses. This yields a color opponent space related to the HVS characteristics. Spatial energy distribution is highly skewed; the chromatic channels contain significantly less relative energy than in standard opponent spaces such asYUV.A constant transform, which closely approximates the input-dependent KLT, has been found. In spite of the little spatial energy in the chromatic channels, chromatic edge enhancement in this space does add significantly to the perception of image detail and enhances its chromatic fidelity, as compared with standard edge enhancement of only the luminance channel. Chromatic edge enhancement is also less sensitive to noise than achromatic edge enhancement. Owing to the simplicity of the transform and enhancement processes, they can be employed for processing real-time video signals.

Nitrate level in cotton (Gossypium hirsutum L.) leaf petioles is commonly used as a practical guide to N fertilization, especially in cases of critically low N levels. The optimization of N supply to irrigated cotton requires a reliable method for monitoring the plant's N status. The feasibility of using leaf N concentrations monitored by near-infrared analysis (NIRA) as a guide for N fertilization in irrigated cotton was examined in this study. Three field trials were conducted in three consecutive years. The NIRA data from fresh leaf disks were calibrated against laboratory N measurements expressed as g N kg -1 dry matter (R 2 = 0.90). Validation of the calibration showed a high correlation between NIRA estimates and laboratory data from two field trials. Dawn leaf sampling was selected for routine monitoring of plant N status. Application of NIRA-guided N fertilization was examined in the third-year trial. The NIRA-guided treatment, with only 60 kg N ha -1 , resulted in only a 7.5% lower yield (statistically nonsignificant) relative to the commercial predetermined N treatment with 150 kg N ha -1 . Yield was linearly correlated with leafN concentration. Cotton leaf N concentration was reliably monitored by NIRA. Only 30 s are required for each N determination; using 10 samples, about 7 min are needed per plot. Once its reliability under various conditions is established, this method could be used for on-the-spot decision-making regarding N-fertilizer application in irrigated cotton.

Two-dimensional (2-D) compactly supported, orthogonal wavelets and filter banks having linear phase are presented. Two cases are discussed: wavelets with two-fold symmetry (centrosymmetric) and wavelets with four-fold symmetry that are symmetric (or anti-symmetric) about the vertical and horizontal axes. We show that imposing the requirement of linear phase in the case of order-factorable wavelets imposes a simple constraint on each of its polynomial order-1 factors. We thus obtain a simple and complete method of constructing orthogonal order-factorable wavelets with linear phase. This method is exemplified by design in the case of four-band separable sampling. An interesting result that is similar to the one well-known in the one-dimensional (1-D) case is obtained: orthogonal order-factorable wavelets cannot be both continuous and have four-fold symmetry.

Irrelevance reasoning refers to the process in which a system reasons about which parts of its knowledge are relevant (or irrelevant) to a specific query. Aside from its importance in speeding up inferences from large knowledge bases, relevance reasoning is crucial in advanced applications such as modeling complex physical devices and information gathering in distributed heterogeneous systems. This article presents a novel framework for studying the various kinds of irrelevance that arise in inference and efficient algorithms for relevance reasoning. We present a proof-theoretic framework for analyzing definitions of irrelevance. The framework makes the necessary distinctions between different notions of irrelevance that are important when using them for speeding up inferences. We describe the query-tree algorithm which is a sound, complete and efficient algorithm for automatically deriving certain kinds of irrelevance claims for Horn-rule knowledge bases and several extensions. Finally, we describe experimental results that show that significant speedups (often orders of magnitude) are obtained by employing the query-tree in inference.

The discrete (finite) Gabor scheme is generalized by incorporating multiwindows. Two approaches are presented for the analysis of the multiwindow scheme: the signal domain approach and the Zak transform domain approach. Issues related to undersampling, critical sampling, and oversampling are considered. The analysis is based on the concept of frames and on generalized (Moore-Penrose) inverses. The approach based on representing the frame operator as a matrix-valued function is far less demanding from a computational complexity viewpoint than a straightforward matrix algebra in various operations such as the computation of the dual frame. DFT-based algorithms, including complexity analysis, are presented for the calculation of the expansion coefficients and for the reconstruction of the signal in both signal and transform domains. The scheme is further generalized and incorporates kernels other than the complex exponential. Representations other than those based on the dual frame and nonrectangular sampling of the combined space are considered as well. An example that illustrates the advantages of the multiwindow scheme over the single-window scheme is presented.

The Gabor scheme is generalized to incorporate several window functions as well as kernels other than the exponential. The properties of the sequence of representation functions are characterized by an approach based on the concept of frames. Utilizing the piecewise Zak transform (PZT), the frame operator associated with the multiwindow Gabor-type frame is examined for a rational oversampling rate by representing the frame operator as a finite-order matrix-valued function in the PZT domain. Completeness and frame properties of the sequence of representation functions are examined in relation to the properties of the matrix-valued function. Calculations of the frame bounds and the dual frame, as well as the issue of tight frames, are considered. It is shown that the properties of the sequence of representation functions are essentially not changed by replacing the widely used exponential kernel with other kernels. Some examples and the issue of a different sampling rate for each window are also considered. The so-called Balian–Low theorem is generalized to consideration of a scheme of multiwindows which makes it possible to overcome in a way the constraint imposed by the original theorem in the case of a single window.