Spectral compressive sensing is a novel approach that enables extraction of spectral information from a spectral-sparse signal, exclusively from its compressed measurements. Thus, the approach has received considerable attention from various fields. However, standard compressive sensing algorithms always require a sparse signal to be on the grid, whose spacing is the standard resolution limit. Thus, these algorithms severely degenerate while handling spectral compressive sensing, owing to the off-the-grid issue. Some off-the-grid algorithms were recently proposed to solve this problem, but they are either inaccurate or computationally expensive. In this paper, we propose a novel algorithm named parameterized ℓ1-minimization (PL1), which can efficiently solves the off-the-grid spectral estimation problem with relatively low computational complexity.

The Euler number of a binary image is an important topological property for pattern recognition, image analysis, and computer vision. A famous method for computing the Euler number of a binary image is by counting certain patterns of bit-quads in the image, which has been improved by scanning three rows once to process two bit-quads simultaneously. This paper studies the bit-quad-based Euler number computing problem. We show that for a bit-quad-based Euler number computing algorithm, with the increase of the number of bit-quads being processed simultaneously, on the one hand, the average number of pixels to be checked for processing a bit-quad will decrease in theory, and on the other hand, the length of the codes for implementing the algorithm will increase, which will make the algorithm less efficient in practice. Experimental results on various types of images demonstrated that scanning five rows once and processing four bit-quads simultaneously is the optimal tradeoff, and that the optimal bit-quad-based Euler number computing algorithm is more efficient than other Euler number computing algorithms.

Train-borne video captured from the camera installed in the front or back of the train has been used for railway environment surveillance, including missing communication units and bolts on the track, broken fences, unpredictable objects falling into the rail area or hanging on wires on the top of rails. Moreover, the track condition can be perceived visually from the video by observing and analyzing the train-swaying arising from the track irregularity. However, it's a time-consuming and labor-intensive work to examine the whole large scale video up to dozens of hours frequently. In this paper, we propose a simple and effective method to detect the train-swaying quickly and automatically. We first generate the long rail track panorama (RTP) by stitching the stripes cut from the video frames, and then extract track profile to perform the unevenness detection algorithm on the RTP. The experimental results show that RTP, the compact video representation, can fast examine the visual train-swaying information for track condition perceiving, on which we detect the irregular spots with 92.86% recall and 82.98% precision in only 2 minutes computation from the video close to 1 hour.

Entity descriptions have been exponentially growing in community-generated knowledge databases, such as DBpedia. However, many of those descriptions are not useful for identifying the underlying characteristics of their corresponding entities because semantically redundant facts or triples are included in the descriptions that represent the connections between entities without any semantic properties. Entity summarization is applied to filter out such non-informative triples and meaning-redundant triples and rank the remaining informative facts within the size of the triples for summarization. This study proposes an entity summarization approach based on pre-grouping the entities that share a set of attributes that can be used to characterize the entities we want to summarize. Entities are first grouped according to projected multilingual categories that provide the multi-angled semantics of each entity into a single entity space. Key facts about the entity are then determined through in-group-based rankings. As a result, our proposed approach produced summary information of significantly better quality (p-value =1.52×10-3 and 2.01×10-3 for the top-10 and -5 summaries, respectively) than the state-of-the-art method that requires additional external resources.

Existing moving object's trajectory prediction algorithms suffer from the data sparsity problem, which affects the accuracy of the trajectory prediction. Aiming to the problem, we present an Entropy-based Sparse Trajectories Prediction method enhanced by Matrix Factorization (ESTP-MF). Firstly, we do trajectory synthesis based on trajectory entropy and put synthesized trajectories into the trajectory space. It can resolve the sparse problem of trajectory data and make the new trajectory space more reliable. Secondly, under the new trajectory space, we introduce matrix factorization into Markov models to improve the sparse trajectory prediction. It uses matrix factorization to infer transition probabilities of the missing regions in terms of corresponding existing elements in the transition probability matrix. It aims to further solve the problem of data sparsity. Experiments with a real trajectory dataset show that ESTP-MF generally improves prediction accuracy by as much as 6% and 4% compared to the SubSyn algorithm and STP-EE algorithm respectively.

In this paper, we propose a method for removing block noise which appears in JPEG (Joint Photographic Experts Group) encoded images. We iteratively perform the 3D wiener filtering and correction of the coefficients. In the wiener filtering, we perform the block matching for each patch in order to get the patches which have high similarities to the reference patch. After wiener filtering, the collected patches are returned to the places where they were and aggregated. We compare the performance of the proposed method to some conventional methods, and show that the proposed method has an excellent performance.

Several applications for 3-D visualization require dense detection of correspondence for displacement estimation among heterogeneous multi-view images. Due to differences in resolution or sampling density and field of view in the images, estimation of dense displacement is not straight forward. Therefore, we propose a scale invariant polynomial expansion method that can estimate dense displacement between two heterogeneous views. Evaluation on heterogeneous images verifies accuracy of our approach.

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a triple p=(V,E,H), where (V,E) is a graph and H is a set of variables, which are ordered lists of vertices in V. A variable can be replaced with an arbitrary connected graph by a kind of hyperedge replacements. A substitution is a collection of such replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether or not a given graph G is obtained from a given graph pattern p by a substitution. In this paper, we show that GPMP for a graph pattern p and a graph G is solvable in polynomial time if the length of every variable in p is 2, p is of bounded treewidth, and G is connected.

We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in nlog σ+O(klog n) bits of space and supports fast pattern matching queries and updates, where σ is the alphabet size. Assume that α=logσn letters are packed in a single machine word on the standard word RAM model, and let f(k,n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1,n] in O(klog n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in $O(rac{m}{alpha} f(k,n))$ worst-case time and in $O(rac{m}{alpha} + f(k,n))$ expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.

Subspace membership encryption (SME), a generalization of inner product encryption (IPE), was recently formalized by Boneh, Raghunathan, and Segev in Asiacrypt 2013. The main motivation for SME was that traditional predicate encryptions did not yield function privacy, a security notion introduced by Boneh et al. in Crypto 2013 that captures the privacy of the predicate associated to the secret key. Although they gave a generic construction of SME based on any IPE, we show that their construction of SME for small attribute space was incorrect and provide an attack that breaks the attribute hiding security, a baseline security notion for predicate encryptions that captures the privacy of the attribute associated with the ciphertext. Then, we propose a generalized construction of SME and prove that the attribute hiding security can not be achieved even in the newly defined setting. Finally, we further extend our generalized construction of SME and propose a SME that achieves the attribute hiding property even when the attribute space is small. In exchange our proposed scheme does not yield function privacy and the construction is rather inefficient. Although we did not succeed in constructing a SME both yielding function privacy and attribute hiding security, ours is the first attribute hiding SME scheme whose attribute space is polynomial in the security parameter, and we formalized a richer framework for constructing SMEs and discovered a trade-off like relationship between the two security notions.

In a speech enhancement system for impact noise, it is important for any impact noise activity to be detected. However, because impact noise occurs suddenly, it is not always easy to detect. We propose a method for impact noise activity detection based on the kurtosis of an instantaneous power spectrum. The continuous duration of a generalized impact noise is shorter than that of speech, and the power of such impact noise varies dramatically. Consequently, the distribution of the instantaneous power spectrum of impact noise is different from that of speech. The proposed detection takes advantage of kurtosis, which depends on the sharpness and skirt of the distribution. Simulation results show that the proposed noise activity detection improves the performance of the speech enhancement system.

In both theoretical analysis and practical use for an antidictionary coding algorithm, an important problem is how to encode an antidictionary of an input source. This paper presents a proposal for a compact tree representation of an antidictionary built from a circular string for an input source. We use a technique for encoding a tree in the compression via substring enumeration to encode a tree representation of the antidictionary. Moreover, we propose a new two-pass universal antidictionary coding algorithm by means of the proposal tree representation. We prove that the proposed algorithm is asymptotic optimal for a stationary ergodic source.

Asymmetric bilinear maps using Type-3 pairings are known to be advantageous in several points (e.g., the speed and the size of a group element) to symmetric bilinear maps using Type-1 pairings. Kremer and Mazaré introduce a symbolic model to analyze protocols based on bilinear maps, and show that the symbolic model is computationally sound. However, their model only covers symmetric bilinear maps. In this paper, we propose a new symbolic model to capture asymmetric bilinear maps. Our model allows us to analyze security of various protocols based on asymmetric bilinear maps (e.g., Joux's tripartite key exchange, and Scott's client-server ID-based key exchange). Also, we show computational soundness of our symbolic model under the decisional bilinear Diffie-Hellman assumption.

An inter-subset uncorrelated zero-correlation zone (ZCZ) sequence pair set is one consisting of multiple ZCZ sequence pair subsets. What's more, two arbitrary sequence pairs which belong to different subsets should be uncorrelated sequence pairs in this set, i.e., the cross-correlation function (CCF) between arbitrary sequence pairs in different subsets are zeros at everywhere. Meanwhile, each subset is a typical ZCZ sequence pair set. First, a class of uncorrelated ZCZ (U-ZCZ) sequence pair sets is proposed from interleaving perfect sequence pairs. An U-ZCZ sequence pair set is a type of ZCZ sequence pair set, which of most important property is that the CCF between two arbitrary sequence pairs is zero at any shift. Then, a type of inter-subset uncorrelated ZCZ sequence pair set is obtained by interleaving proposed U-ZCZ sequence pair set. In particular, the novel inter-subset uncorrelated ZCZ sequence pair sets are expected to be useful for designing spreading codes for QS-CDMA systems.

Broadband satellites, operating at Ka band and above, are playing more and more important roles in future satellite networks. Meanwhile, rain attenuation is the dominant impairment in these bands. In this context, a dynamic power allocation scheme based on rain attenuation prediction is proposed. By this scheme, the system can dynamically adjust the allocated power according to the time-varying predicted rain attenuation. Extensive simulation results demonstrate the improvement of the dynamic scheme over the static allocation. It can be concluded that the allocated capacities match the traffic demands better by introducing such dynamic power allocation scheme and the waste of power resources is also avoided.

We propose three effective approximate belief propagation decoders for polar codes using Maclaurin's series, piecewise linear function, and stepwise linear function. The proposed decoders have the better performance than that of existing approximate belief propagation polar decoders, min-sum decoder and normalized min-sum decoder, and almost the same performance with that of original belief propagation decoder. Moreover, the proposed decoders achieve such performance without any optimization process according to the code parameters and channel condition unlike normalized min-sum decoder, offset min-sum decoder, and their variants.

This paper presents a new hole-filling method that uses extrapolated spatio-temporal background information to obtain a synthesized free-view. A new background codebook for extracting reliable temporal background information is introduced. In addition, the paper addresses estimating spatial local background to distinguish background and foreground regions so that spatial background information can be extrapolated. Background holes are filled by combining spatial and temporal background information. Finally, exemplar-based inpainting is applied to fill in the remaining holes using a new priority function. The experimental results demonstrated that satisfactory synthesized views can be obtained using the proposed algorithm.

With the ever-increasing number of web services registered in service communities, many users are apt to find their interested web services through various recommendation techniques, e.g., Collaborative Filtering (i.e., CF)-based recommendation. Generally, CF-based recommendation approaches can work well, when a target user has similar friends or the target services (i.e., services preferred by the target user) have similar services. However, when the available user-service rating data is very sparse, it is possible that a target user has no similar friends and the target services have no similar services; in this situation, traditional CF-based recommendation approaches fail to generate a satisfying recommendation result. In view of this challenge, we combine Social Balance Theory (abbreviated as SBT; e.g., “enemy's enemy is a friend” rule) and CF to put forward a novel data-sparsity tolerant recommendation approach Ser_RecSBT+CF. During the recommendation process, a pruning strategy is adopted to decrease the searching space and improve the recommendation efficiency. Finally, through a set of experiments deployed on a real web service quality dataset WS-DREAM, we validate the feasibility of our proposal in terms of recommendation accuracy, recall and efficiency. The experiment results show that our proposed Ser_RecSBT+CF approach outperforms other up-to-date approaches.

A bi-dimensional empirical mode decomposition (BEMD) is one of the powerful methods for decomposing non-linear and non-stationary signals without a prior function. It can be applied in many applications such as feature extraction, image compression, and image filtering. Although modified BEMDs are proposed in several approaches, computational cost and quality of their bi-dimensional intrinsic mode function (BIMF) still require an improvement. In this paper, an iteration-free computation method for bi-dimensional empirical mode decomposition, called iBEMD, is proposed. The locally partial correlation for principal component analysis (LPC-PCA) is a novel technique to extract BIMFs from an original signal without using extrema detection. This dramatically reduces the computation time. The LPC-PCA technique also enhances the quality of BIMFs by reducing artifacts. The experimental results, when compared with state-of-the-art methods, show that the proposed iBEMD method can achieve the faster computation of BIMF extraction and the higher quality of BIMF image. Furthermore, the iBEMD method can clearly remove an illumination component of nature scene images under illumination change, thereby improving the performance of text localization and recognition.

Conventional feature-rich parsers based on manually tuned features have achieved state-of-the-art performance. However, these parsers are not good at handling long-term dependencies using only the clues captured by a prepared feature template. On the other hand, recurrent neural network (RNN)-based parsers can encode unbounded history information effectively, but they perform not well for small tree structures, especially when low-frequency words are involved, and they cannot use prior linguistic knowledge. In this paper, we propose a simple but effective framework to combine the merits of feature-rich transition-based parsers and RNNs. Specifically, the proposed framework incorporates RNN-based scores into the feature template used by a feature-rich parser. On English WSJ treebank and SPMRL 2014 German treebank, our framework achieves state-of-the-art performance (91.56 F-score for English and 83.06 F-score for German), without requiring any additional unlabeled data.