### Browsing by Author "Sidiropoulos, N.D."

###### Results Per Page

###### Sort Options

Item Fast Digital Locally Monotonic Regression(1995) Sidiropoulos, N.D.; ISRIn [1], Restrepo and Bovik developed an elegant mathematical framework in which they studied locally monotonic regressions in RN . The drawback is that the complexity of their algorithms is exponential in N. In this paper, we consider digital locally monotonic regressions, in which the output symbols are drawn from a finite alphabet, and, by making a connection to Viterbi decoding, provide a fast O(|A|2 aN) algorithm that computes any such regression, where |A| is the size of the digital output alphabet, a stands for lomo-degree, and N is sample size. This is linear in N , and it renders the technique applicable in practice.Item Further Results on MAP Optimality and Strong Consistency of Certain Classes of Morphological Filters(1994) Sidiropoulos, N.D.; Baras, John S.; Berenstein, Carlos A.; ISRIn two recent papers [1], [2], Sidiropoulos et al. have obtained statistical proofs of Maximum A Posteriori} (MAP) optimality and strong consistency of certain popular classes of Morphological filters, namely, Morphological Openings, Closings, unions of Openings, and intersections of Closings, under i.i.d. (both pixel-wise, and sequence-wide) assumptions on the noise model. In this paper we revisit this classic filtering problem, and prove MAP optimality and strong consistency under a different, and, in a sense, more appealing set of assumptions, which allows the explicit incorporation of geometric and Morphological constraints into the noise model, i.e., the noise may now exhibit structure; Surprisingly, it turns out that this affects neither the optimality nor the consistency of these field-proven filters.Item Image Deconvolution Using Multiple Sensors(1990) Sidiropoulos, N.D.; Baras, J.S.; ISRWe consider the two dimensional Analytic Bezout Equation (ABE) and investigate the properties of a particular solution, based on certain conditions imposed on the convolution kernels. We use a family of suitably chosen sensors which besides being strongly coprime also satisfies additional technical conditions. The results permit the reconstruction of the original signal with arbitrarily good resolution, i.e. achieving arbitrarily large bandwidths, depending solely upon computational resources. The theoretical foundations of this technique provide a rigorous mathematical framework, and simulation results have been promising. The feasibility of construction reasonable good discrete-time, finite-bandwidth approximations has been established, and efficient Data Parallel Grid layouts that perform the required computation have been designed. A number of implementation problems arising out of the need to approximate a basically infinite computation have been addressed.Item Mathematical Programming Algorithms for Regression-based Nonlinear Filtering in IRN(1997) Sidiropoulos, N.D.; Bro, R.; ISRConstrained regression problems appear in the context of optimal nonlinear filtering, as well as in a variety of other contexts, e.g., chromatographic analysis in chemometrics and manufacturing, and spectral estimation. This paper presents novel mathematical programming algorithms for some important constrained regression problems in IRN . For brevity, we focus on four key problems, namely, locally monotonic regression (the optimal counterpart of iterated median filtering), and the related problem of piecewise monotonic regression, runlength-constrained regression (a useful segmentation and edge detection technique), and uni- and oligo- modal regression (of interest in chromatography and spectral estimation). The proposed algorithms are exact and efficient, and they also naturally suggest slightly suboptimal but very fast approximate algorithms, which may be preferable in practice.Item Optimal Filtering of Digital Binary Images Corrupted by Union/Intersection(1992) Sidiropoulos, N.D.; Baras, John S.; Berenstein, Carlos A.; ISRWe model digital binary image data as realizations of a bounded discrete random set, a mathematical object which can be directly defined on a finite lattice. We consider the problem of estimating realizations of discrete random sets distorted by a degradation process which can be described by a union/intersection model. First we present an important structural result concerning the probabilistic specification of discrete random sets defined on a finite lattice. Then we formulate the optimal filtering problem for the case of discrete random sets. Two distinct filtering approaches are pursued. For images which feature strong spatial statistical variations we propose a simple family of spatially varying filters, which we call mask filters, and, for each degradation model, derive explicit formulas for the optimal Mask filter. We also consider adaptive mask filters, which can be effective in a more general setting. For images which exhibit a stationary behavior, we consider the class of Morphological filters. First we provide some theoretical justification for the popularity of certain Morphological filtering schemes. In particular, we show that if the signal is smooth, then these schemes are optimal (in the sense of providing the MAP estimate of the signal) under a reasonable worst-case statistical scenario. Then we show that, by using an appropriate (under a given degradation model) expansion of the optimal filter, we can obtain universal characterizations of optimality which do not rely on strong assumptions regarding the spatial interaction of geometrical primitives of the signal and the noise. This approach corresponds to a somewhat counter- intuitive use of fundamental morphological operators; however it is exactly this mode of the use that enables us to arrive at characterizations of optimality in terms of the fundamental functionals of random set theory, namely the generating functionals of the signal and the noise.Item Recovering Information from Summary Data(1997) Faloutsos, Christos; Jagadish, H.V.; Sidiropoulos, N.D.; ISRData is often stored in summarized form, as a histogram of aggregates (COUNTs,SUMs, or AVeraGes) over specified ranges. Queries regarding specific values, or ranges different from those stored, cannot be answered exactly from the summarized data. In this paper we study how to estimate the original detail data from the stored summary.We formulate this task as an inverse problem, specifying a well-defined cost function that has to be optimized under constraints.

In particular, we propose the use of a Linear Regularization method, which ﲭaximizes the smoothness of the estimate. Our main theoretical contribution is a Theorem, which shows that, for smooth enough distributions, we can achieve full recovery from summary data.

Our theorem is closely related to the well known Shannon-Nyquist sampling theorem.

We describe how to apply this theory to a variety of database problems, that involve partial information, such as OLAP, data warehousing and histograms in query optimization. Our main practical contribution is that the Linear Regularization method is extremely effective, both on synthetic and on real data. Our experiments show that the proposed approach almost consistently outperforms the ﲵniformity assumption, achieving significant savings in root-mean-square error: up to 20% for stock price data, and up to 90% for smoother data sets.

Item Recovering Information from Summary Data(1997) Faloutsos, Christos; Jagadish, H.V.; Sidiropoulos, N.D.; ISRData is often stored in summarized form, as a histogram of aggregates (COUNTs,SUMs, or AVeraGes) over specified ranges. Queries regarding specific values, or ranges different from those stored, cannot be answered exactly from the summarized data. In this paper we study how to estimate the original detail data from the stored summary.We formulate this task as an inverse problem, specifying a well-defined cost function that has to be optimized under constraints.

In particular, we propose the use of a Linear Regularization method, which ﲭaximizes the smoothness of the estimate. Our main theoretical contribution is a Theorem, which shows that, for smooth enough distributions, we can achieve full recovery from summary data.

Our theorem is closely related to the well known Shannon-Nyquist sampling theorem.

We describe how to apply this theory to a variety of database problems, that involve partial information, such as OLAP, data warehousing and histograms in query optimization. Our main practical contribution is that the Linear Regularization method is extremely effective, both on synthetic and on real data. Our experiments show that the proposed approach almost consistently outperforms the ﲵniformity assumption, achieving significant savings in root-mean-square error: up to 20% for stock price data, and up to 90% for smoother data sets.

Item Statistical Inference, Filtering, and Modeling of Discrete Random Sets(1992) Sidiropoulos, N.D.; Baras, J.S.; ISRThe objective of this dissertation is the systematic study of several aspects of modeling, statistical inference, and filtering of "random" binary digital images, or, uniformly bounded discrete random sets. This study consists of two interleaved parts. In the first part, we consider some important aspects of a theory of uniformly bounded discrete random sets. The fundamental result is a strengthened version of a backbone theorem of continuous- domain random set theory, namely the uniqueness theorem of Choquet-Kendall-Matheron, for the case of uniformly bounded discrete random sets.The vehicle through which much of the discussion is carried out is a "special" discrete random set model, the discrete radial Boolean random set, which is closely related to the theory of Morphological shape-size distributions. The continuous-domain Boolean random set has been successfully used in a variety of applications. A good portion of the first part of this dissertation is devoted to the statistical inference of the discrete radial Boolean random set. We consider three problems: parameter estimation, binary hypothesis testing, and classification of "random" known shapes in Boolean clutter. The tools come mainly from the area of Morphological shape analysis. The focus is on inference procedures which are both computationally efficient, and statistically sound.

In the second part, we consider the problem of estimating realizations of uniformly bounded discrete random sets, distorted by a degradation process which can be described by a union/intersection noise model. Two different optimal filtering approaches are considered. The first involves a class of filters which arises quite naturally from the set-theoretic analysis of optimal filters. We call this the class of mask filters. The second approach deals with optimal Morphological filters. First, we provide some fresh statistical insight into certain "folk theorems" of Morphological filtering. We do so by exploiting the uniformly bounded discrete random set formulation of the filtering problem. Then we show that, by using an appropriate (under a given degradation model) expansion of the optimal filter, we can obtain "universal" characterizations of optimality, in terms of the fundamental functionals of random set theory, namely the generating functionals of the signal and the noise.

Item Structurally Robust Weak Continuity(1995) Sidiropoulos, N.D.; Baras, John S.; Berenstein, Carlos A.; ISRBuilding on earlier work, we pose the following optimization: Given a sequence of finite extent, find a finite-alphabet sequence of finite extent, which satisfies a hard structural (syntactic) constraint (e.g., it is piecewise constant of plateau run-length > M, or locally monotonic of a given lomo-degree), and which minimizes the sum of a per-letter fidelity measure, and a first-order smoothness-complexity measure. This optimization represents the unification and outgrowth of several digital nonlinear filtering schemes, including the digital counterpart of the so-called Weak Continuity (WC) formulation of Mumford-Shah and Blake-Zisserman, the Minimum Description Length (MDL) approach of Leclerc, and previous work by the first author in so- called VORCA filtering and Digital Locally Monotonic Regression. It is shown that the proposed optimization admits efficient Viterbi-type solution, and overcomes a shortcoming of WC, while preserving its unique strengths. Similarly, it overcomes a drawback of VORCA and Digital Locally Monotonic Regression, while maintaining robustness to outliers.