OpenRaiser/Intern-Atlas huggingface dataset:
Wavelet subspace decomposition of thermal infrared images for defect detection in artworks
Venue: arXiv cs.CV 2015
Year: 2015

Monitoring the health of ancient artworks requires adequate prudence because of the sensitive nature of these materials. Classical techniques for identifying the development of faults rely on acoustic testing. These techniques, being invasive, may result in causing permanent damage to the material, especially if the material is inspected periodically. Non destructive testing has been carried out for different materials since long. In this regard, non-invasive systems were developed based on infrared thermometry principle to identify the faults in artworks. The test artwork is heated and the thermal response of the different layers is captured with the help of a thermal infrared camera. However, prolonged heating risks overheating and thus causing damage to artworks and an alternate approach is to use pseudo-random binary sequence excitations. The faults in the artwork, though, cannot be detected on the captured images, especially if their strength is weak. The weaker faults are either masked by the stronger ones, by the pictorial layer of the artwork or by the non-uniform heating. This work addresses the detection and localization of the faults through a wavelet based subspace decomposition scheme. The proposed scheme, on one hand, allows to remove the background while, on the other hand, removes the undesired high frequency noise. It is shown that the detection parameter is proportional to the diameter and the depth of the fault. A criterion is proposed to select the optimal wavelet basis along with suitable level selection for wavelet decomposition and reconstruction. The proposed approach is tested on a laboratory developed test sample with known fault locations and dimensions as well as real artworks. A comparison with a previously reported method demonstrates the efficacy of the proposed approach for fault detection in artworks.
Dense Subset Sum may be the hardest
Venue: arXiv cs.DS 2015
Year: 2015

The Subset Sum problem asks whether a given set of $n$ positive integers contains a subset of elements that sum up to a given target $t$. It is an outstanding open question whether the $O^*(2^{n/2})$-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", $O^*(2^{(0.5-δ)n})$-time algorithm, with some constant $δ> 0$. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size $β$, defined as the largest number of subsets of the $n$ input integers that yield the same sum. For every $ε> 0$ we give a truly faster algorithm for instances with $β\leq 2^{(0.5-ε)n}$, as well as instances with $β\geq 2^{0.661n}$. Consequently, we also obtain a characterization in terms of the popular density parameter $n/\log_2 t$: if all instances of density at least $1.003$ admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from novel combinations of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
A Novel Reconfigurable Hardware Design for Speech Enhancement Based on Multi-Band Spectral Subtraction Involving Magnitude and Phase Components
Venue: arXiv cs.SD 2015
Year: 2015

This paper proposes an efficient reconfigurable hardware design for speech enhancement based on multi band spectral subtraction algorithm and involving both magnitude and phase components. Our proposed design is novel as it estimates environmental noise from speech adaptively utilizing both magnitude and phase components of the speech spectrum. We performed multi-band spectrum subtraction by dividing the noisy speech spectrum into different non-uniform frequency bands having varying signal to noise ratio (SNR) and subtracting the estimated noise from each of these frequency bands. This results to the elimination of noise from both high SNR and low SNR signal components for all the frequency bands. We have coined our proposed speech enhancement technique as Multi Band Magnitude Phase Spectral Subtraction (MBMPSS). The magnitude and phase operations are executed concurrently exploiting the parallel logic blocks of Field Programmable Gate Array (FPGA), thus increasing the throughput of the system to a great extent. We have implemented our design on Spartan6 Lx45 FPGA and presented the implementation result in terms of resource utilization and delay information for the different blocks of our design. To the best of our best knowledge, this is a new type of hardware design for speech enhancement application and also a first of its kind implementation on reconfigurable hardware. We have used benchmark audio data for the evaluation of the proposed hardware and the experimental results show that our hardware shows a better SNR value compared to the existing state of the art research works.
OCReP: An Optimally Conditioned Regularization for Pseudoinversion Based Neural Training
Venue: arXiv cs.NE 2015
Year: 2015

In this paper we consider the training of single hidden layer neural networks by pseudoinversion, which, in spite of its popularity, is sometimes affected by numerical instability issues. Regularization is known to be effective in such cases, so that we introduce, in the framework of Tikhonov regularization, a matricial reformulation of the problem which allows us to use the condition number as a diagnostic tool for identification of instability. By imposing well-conditioning requirements on the relevant matrices, our theoretical analysis allows the identification of an optimal value for the regularization parameter from the standpoint of stability. We compare with the value derived by cross-validation for overfitting control and optimisation of the generalization performance. We test our method for both regression and classification tasks. The proposed method is quite effective in terms of predictivity, often with some improvement on performance with respect to the reference cases considered. This approach, due to analytical determination of the regularization parameter, dramatically reduces the computational load required by many other techniques.
Pedestrian Static Trajectory Analysis of a Hypermarket
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we propose a combination of pedestrian data collection and analysis and modeling that may yield higher competitive advantage in the business environment. The data collection is only based on simple inventory and questionnaire surveys on a hypermarket to obtain trajectory path of pedestrian movement. Though the data has limitation by using static trajectories, our techniques showed that it is possible to obtain aggregation of flow pattern and alley attractiveness similar to the result of aggregation using dynamic trajectory. A case study of a real hypermarket demonstrates that daily necessity products are closely related to higher flow pattern. Using the proposed method, we are also able to quantify pedestrian behavior that shoppers tend to walk about 7 times higher than the ideal shortest path
Integrating Schedulability Analysis with UML-RT
Venue: arXiv cs.SY 2015
Year: 2015

The use of object oriented techniques and methodologies for the design of real-time control systems appear to be necessary in order to deal with the increasing complexity of such systems. Recently many object-oriented methods have been used for the modeling and design of real-time control systems. We believe that an approach that integrates the advancements in both object modeling and design methods, and real-time scheduling theory is the key to successful use of object oriented technology for real-time software. However, past approaches to integrate the two either restrict the object models, or do not allow sophisticated schedulability analysis techniques. In this paper we show how schedulability analysis can be integrated with object-oriented design; we develop the schedulability and feasibility analysis method for the external messages that may suffer release jitter due to being dispatched by a tick driven scheduler in real-time control system, and we also develop the scheduliability method for sporadic activities, where message arrive sporadically then execute periodically for some bounded time. This method can be used to cope with timing constraints in complex real-time control systems.
Cardinality Estimation Meets Good-Turing
Venue: arXiv cs.DS 2015
Year: 2015

Cardinality estimation algorithms receive a stream of elements whose order might be arbitrary, with possible repetitions, and return the number of distinct elements. Such algorithms usually seek to minimize the required storage and processing at the price of inaccuracy in their output. Real-world applications of these algorithms are required to process large volumes of monitored data, making it impractical to collect and analyze the entire input stream. In such cases, it is common practice to sample and process only a small part of the stream elements. This paper presents and analyzes a generic algorithm for combining every cardinality estimation algorithm with a sampling process. We show that the proposed sampling algorithm does not affect the estimator's asymptotic unbiasedness, and we analyze the sampling effect on the estimator's variance.
Extending UML-RT for Control System Modeling
Venue: arXiv cs.SE 2015
Year: 2015

There is a growing interest in adopting object technologies for the development of real-time control systems. Several commercial tools, currently available, provide object-oriented modeling and design support for real-time control systems. While these products provide many useful facilities, such as visualization tools and automatic code generation, they are all weak in addressing the central characteristic of real-time control systems design, i.e., providing support for a designer to reason about timeliness properties. We believe an approach that integrates the advancements in both object modeling and design methods and real-time scheduling theory is the key to successful use of object technology for real-time software. Surprisingly several past approaches to integrate the two either restrict the object models, or do not allow sophisticated schedulability analysis techniques. This study shows how schedulability analysis can be integrated with UML for Real-Time (UML-RT) to deal with timing properties in real time control systems. More specifically, we develop the schedulability and feasibility analysis modeling for the external messages that may suffer release jitter due to being dispatched by a tick driven scheduler in real-time control system and we also develop the scheduliablity modeling for sporadic activities, where messages arrive sporadically then execute periodically for some bounded time. This method can be used to cope with timing constraints in realistic and complex real-time control systems. Using this method, a designer can quickly evaluate the impact of various implementation decisions on schedulability. In conjunction with automatic code-generation, we believe that this will greatly streamline the design and development of real-time control systems software.
SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of computing the Walsh-Hadamard Transform (WHT) of some $N$-length input vector in the presence of noise, where the $N$-point Walsh spectrum is $K$-sparse with $K = {O}(N^δ)$ scaling sub-linearly in the input dimension $N$ for some $0<δ<1$. Over the past decade, there has been a resurgence in research related to the computation of Discrete Fourier Transform (DFT) for some length-$N$ input signal that has a $K$-sparse Fourier spectrum. In particular, through a sparse-graph code design, our earlier work on the Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm computes the $K$-sparse DFT in time ${O}(K\log K)$ by taking ${O}(K)$ noiseless samples. Inspired by the coding-theoretic design framework, Scheibler et al. proposed the Sparse Fast Hadamard Transform (SparseFHT) algorithm that elegantly computes the $K$-sparse WHT in the absence of noise using ${O}(K\log N)$ samples in time ${O}(K\log^2 N)$. However, the SparseFHT algorithm explicitly exploits the noiseless nature of the problem, and is not equipped to deal with scenarios where the observations are corrupted by noise. Therefore, a question of critical interest is whether this coding-theoretic framework can be made robust to noise. Further, if the answer is yes, what is the extra price that needs to be paid for being robust to noise? In this paper, we show, quite interestingly, that there is {\it no extra price} that needs to be paid for being robust to noise other than a constant factor. In other words, we can maintain the same sample complexity ${O}(K\log N)$ and the computational complexity ${O}(K\log^2 N)$ as those of the noiseless case, using our SParse Robust Iterative Graph-based Hadamard Transform (SPRIGHT) algorithm.
A fully data-driven method to identify (correlated) changes in diachronic corpora
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, a method for measuring synchronic corpus (dis-)similarity put forward by Kilgarriff (2001) is adapted and extended to identify trends and correlated changes in diachronic text data, using the Corpus of Historical American English (Davies 2010a) and the Google Ngram Corpora (Michel et al. 2010a). This paper shows that this fully data-driven method, which extracts word types that have undergone the most pronounced change in frequency in a given period of time, is computationally very cheap and that it allows interpretations of diachronic trends that are both intuitively plausible and motivated from the perspective of information theory. Furthermore, it demonstrates that the method is able to identify correlated linguistic changes and diachronic shifts that can be linked to historical events. Finally, it can help to improve diachronic POS tagging and complement existing NLP approaches. This indicates that the approach can facilitate an improved understanding of diachronic processes in language change.
Maximal Ratio Transmission in Wireless Poisson Networks under Spatially Correlated Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

The downlink of a wireless network where multi-antenna base stations (BSs) communicate with single-antenna mobile stations (MSs) using maximal ratio transmission (MRT) is considered here. The locations of BSs are modeled by a homogeneous Poisson point process (PPP) and the channel gains between the multiple antennas of each BS and the single antenna of each MS are modeled as spatially arbitrarily correlated Rayleigh random variables. We first present novel closed-form expressions for the distribution of the power of the interference resulting from the coexistence of one intended and one unintended MRT over the considered correlated fading channels. The derived expressions are then used to obtain closed-form expressions for the success probability and area spectral efficiency of the wireless communication network under investigation. Simulation results corroborate the validity of the presented expressions. A key result of this work is that the effect of spatial correlation on the network throughput may be contrasting depending on the density of BSs, the signal-to-interference-plus-noise ratio (SINR) level, and the background noise power.
Event-based Formalization of Safety-critical Operating System Standards: An Experience Report on ARINC 653 using Event-B
Venue: arXiv cs.SE 2015
Year: 2015

Standards play the key role in safety-critical systems. Errors in standards could mislead system developer's understanding and introduce bugs into system implementations. In this paper, we present an Event-B formalization and verification for the ARINC 653 standard, which provides a standardized interface between safety-critical real-time operating systems and application software, as well as a set of functionalities aimed to improve the safety and certification process of such safety-critical systems. The formalization is a complete model of ARINC 653, and provides a necessary foundation for the formal development and verification of ARINC 653 compliant operating systems and applications. Six hidden errors were discovered from the verification using the Event-B formal reasoning approach.
Population Synthesis via k-Nearest Neighbor Crossover Kernel
Venue: arXiv cs.NE 2015
Year: 2015

The recent development of multi-agent simulations brings about a need for population synthesis. It is a task of reconstructing the entire population from a sampling survey of limited size (1% or so), supplying the initial conditions from which simulations begin. This paper presents a new kernel density estimator for this task. Our method is an analogue of the classical Breiman-Meisel-Purcell estimator, but employs novel techniques that harness the huge degree of freedom which is required to model high-dimensional nonlinearly correlated datasets: the crossover kernel, the k-nearest neighbor restriction of the kernel construction set and the bagging of kernels. The performance as a statistical estimator is examined through real and synthetic datasets. We provide an "optimization-free" parameter selection rule for our method, a theory of how our method works and a computational cost analysis. To demonstrate the usefulness as a population synthesizer, our method is applied to a household synthesis task for an urban micro-simulator.
Encoding the Factorisation Calculus
Venue: arXiv cs.LO 2015
Year: 2015

Jay and Given-Wilson have recently introduced the Factorisation (or SF-) calculus as a minimal fundamental model of intensional computation. It is a combinatory calculus containing a special combinator, F, which is able to examine the internal structure of its first argument. The calculus is significant in that as well as being combinatorially complete it also exhibits the property of structural completeness, i.e. it is able to represent any function on terms definable using pattern matching on arbitrary normal forms. In particular, it admits a term that can decide the structural equality of any two arbitrary normal forms. Since SF-calculus is combinatorially complete, it is clearly at least as powerful as the more familiar and paradigmatic Turing-powerful computational models of Lambda Calculus and Combinatory Logic. Its relationship to these models in the converse direction is less obvious, however. Jay and Given-Wilson have suggested that SF-calculus is strictly more powerful than the aforementioned models, but a detailed study of the connections between these models is yet to be undertaken. This paper begins to bridge that gap by presenting a faithful encoding of the Factorisation Calculus into the Lambda Calculus preserving both reduction and strong normalisation. The existence of such an encoding is a new result. It also suggests that there is, in some sense, an equivalence between the former model and the latter. We discuss to what extent our result constitutes an equivalence by considering it in the context of some previously defined frameworks for comparing computational power and expressiveness.
Online Anomaly Detection via Class-Imbalance Learning
Venue: arXiv cs.LG 2015
Year: 2015

Anomaly detection is an important task in many real world applications such as fraud detection, suspicious activity detection, health care monitoring etc. In this paper, we tackle this problem from supervised learning perspective in online learning setting. We maximize well known \emph{Gmean} metric for class-imbalance learning in online learning framework. Specifically, we show that maximizing \emph{Gmean} is equivalent to minimizing a convex surrogate loss function and based on that we propose novel online learning algorithm for anomaly detection. We then show, by extensive experiments, that the performance of the proposed algorithm with respect to $sum$ metric is as good as a recently proposed Cost-Sensitive Online Classification(CSOC) algorithm for class-imbalance learning over various benchmarked data sets while keeping running time close to the perception algorithm. Our another conclusion is that other competitive online algorithms do not perform consistently over data sets of varying size. This shows the potential applicability of our proposed approach.
Boosting Java Performance using GPGPUs
Venue: arXiv cs.DC 2015
Year: 2015

Heterogeneous programming has started becoming the norm in order to achieve better performance by running portions of code on the most appropriate hardware resource. Currently, significant engineering efforts are undertaken in order to enable existing programming languages to perform heterogeneous execution mainly on GPUs. In this paper we describe Jacc, an experimental framework which allows developers to program GPGPUs directly from Java. By using the Jacc framework, developers have the ability to add GPGPU support into their applications with minimal code refactoring. To simplify the development of GPGPU applications we allow developers to model heterogeneous code using two key abstractions: \textit{tasks}, which encapsulate all the information needed to execute code on a GPGPU; and \textit{task graphs}, which capture the inter-task control-flow of the application. Using this information the Jacc runtime is able to automatically handle data movement and synchronization between the host and the GPGPU; eliminating the need for explicitly managing disparate memory spaces. In order to generate highly parallel GPGPU code, Jacc provides developers with the ability to decorate key aspects of their code using annotations. The compiler, in turn, exploits this information in order to automatically generate code without requiring additional code refactoring. Finally, we demonstrate the advantages of Jacc, both in terms of programmability and performance, by evaluating it against existing Java frameworks. Experimental results show an average performance speedup of 32x and a 4.4x code decrease across eight evaluated benchmarks on a NVIDIA Tesla K20m GPU.
Allowing Software Developers to Debug HLS Hardware
Venue: arXiv cs.SE 2015
Year: 2015

High-Level Synthesis (HLS) is emerging as a mainstream design methodology, allowing software designers to enjoy the benefits of a hardware implementation. Significant work has led to effective compilers that produce high-quality hardware designs from software specifications. However, in order to fully benefit from the promise of HLS, a complete ecosystem that provides the ability to analyze, debug, and optimize designs is essential. This ecosystem has to be accessible to software designers. This is challenging, since software developers view their designs very differently than how they are physically implemented on-chip. Rather than individual sequential lines of code, the implementation consists of gates operating in parallel across multiple clock cycles. In this paper, we report on our efforts to create an ecosystem that allows software designers to debug HLS-generated circuits in a familiar manner. We have implemented our ideas in a debug framework that will be included in the next release of the popular LegUp high-level synthesis tool.