Search results for " Complexity theory"
showing 10 items of 131 documents
An advanced variant of an interpolatory graphical display algorithm
2004
In this paper an advanced interpolatory graphical display algorithm based on cardinal B-spline functions is provided. It is well-known that B-spline functions are a flexible tool to design various scale rapresentations of a signal. The proposed method allows to display without recursion a function at any desiderable resolution so that only initial data and opportune vectors weight are involved. In this way the structure of the algorithm is independent across the scale and a computational efficiency is reached. In this paper mono and bi-dimensional vectors weight generated by means of centered cubic cardinal B-spline functions have been supplied. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Wei…
Attentional vs computational complexity measures in observing paintings
2009
Because of the great heterogeneity of subjects and styles, esthetic perception delineates a special and elusive field of research in vision, which represents an interesting challenge for cognitive science tools. With specific regard to the role of visual complexity, in this paper we present an experiment aimed to measure this dimension in a heterogeneous set of paintings. We compared perceived time complexity measures - based on a temporal estimation paradigm - with physical and statistical properties of the paintings, obtaining a strong correlation between psychological and computational results.
Convolutional Regression Tsetlin Machine: An Interpretable Approach to Convolutional Regression
2021
The Convolutional Tsetlin Machine (CTM), a variant of Tsetlin Machine (TM), represents patterns as straightforward AND-rules, to address the high computational complexity and the lack of interpretability of Convolutional Neural Networks (CNNs). CTM has shown competitive performance on MNIST, Fashion-MNIST, and Kuzushiji-MNIST pattern classification benchmarks, both in terms of accuracy and memory footprint. In this paper, we propose the Convolutional Regression Tsetlin Machine (C-RTM) that extends the CTM to support continuous output problems in image analysis. C-RTM identifies patterns in images using the convolution operation as in the CTM and then maps the identified patterns into a real…
Low-Rate Reduced Complexity Image Compression using Directionlets
2006
The standard separable two-dimensional (2-D) wavelet transform (WT) has recently achieved a great success in image processing because it provides a sparse representation of smooth images. However, it fails to capture efficiently one-dimensional (1-D) discontinuities, like edges and contours, that are anisotropic and characterized by geometrical regularity along different directions. In our previous work, we proposed a construction of critically sampled perfect reconstruction anisotropic transform with directional vanishing moments (DVM) imposed in the corresponding basis functions, called directionlets. Here, we show that the computational complexity of our transform is comparable to the co…
A Variational Approach for Denoising Hyperspectral Images Corrupted by Poisson Distributed Noise
2014
Poisson distributed noise, such as photon noise is an important noise source in multi- and hyperspectral images. We propose a variational based denoising approach, that accounts the vectorial structure of a spectral image cube, as well as the poisson distributed noise. For this aim, we extend an approach for monochromatic images, by a regularisation term, that is spectrally and spatially adaptive and preserves edges. In order to take the high computational complexity into account, we derive a Split Bregman optimisation for the proposed model. The results show the advantages of the proposed approach compared to a marginal approach on synthetic and real data.
Space-Frequency Quantization using Directionlets
2007
In our previous work we proposed a construction of critically sampled perfect reconstruction transforms with directional vanishing moments (DVMs) imposed in the corresponding basis functions along different directions, called directionlets. Here, we combine the directionlets with the space-frequency quantization (SFQ) image compression method, originally based on the standard two-dimensional (2-D) wavelet transform (WT). We show that our new compression method outperforms the standard SFQ as well as the state-of-the-art compression methods, like SPIHT and JPEG-2000, in terms of the quality of compressed images, especially in a low-rate compression regime. We also show that the order of comp…
Computational Complexity and Communication: Coordination in Two-Player Games
2002
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of the computational power available to agents. We introduce the concept of limited computational complexity, and by borrowing results from cryptography, we construct a communication protocol to establish that every correlated equilibrium of a two-person game with rational payoffs can be achieved by means of computationally restricted unmediated communication. This result provides an example in game theory where limitations of computational abilities of players are helpful in solv…
Representing 2D Digital Objects
2000
The paper describes the combination a multi-views approach to represent connected components of 2D binary images. The approach is based on the Object Connectivity Graph (OCG), which is a sub-graph of the connectivity graph generated by the Discrete Cylindrical Algebraic Decomposition(DCAD) performed in the 2D discrete space. This construction allows us to find the number of connected components, to determine their connectivity degree, and to solve visibility problem. We show that the CAD construction, when performed on two orthogonal views, supply information to avoid ambiguities in the interpretation of each image component. The implementation of the algorithm is outlined and the computati…
New delay-dependent stability conditions for time-varying delay systems
2013
Published version of an article in the journal: Mathematical Problems in Engineering. Also available from the publisher at: http://dx.doi.org/10.1155/2013/360924 Open Access This paper addresses the delay-dependent stability for systems with time-varying delay. First, by taking multi-integral terms into consideration, new Lyapunov-Krasovskii functional is defined. Second, in order to reduce the computational complexity of the main results, reciprocally convex approach and some special transformations are introduced, and new delay-dependent stability criteria are proposed, which are less conservative and have less decision variables than some previous results. Finally, two well-known example…
Verbal ordinal classification with multicriteria decision aiding
2008
Abstract Professionals in neuropsychology usually perform diagnoses of patients’ behaviour in a verbal rather than in a numerical form. This fact generates interest in decision support systems that process verbal data. It also motivates us to develop methods for the classification of such data. In this paper, we describe ways of aiding classification of a discrete set of objects, evaluated on set of criteria that may have verbal estimations, into ordered decision classes. In some situations, there is no explicit additional information available, while in others it is possible to order the criteria lexicographically. We consider both of these cases. The proposed Dichotomic Classification (DC…