Position-width-pulse algorithm for recognition of handwritten characters

An algorithm for the recognition of handwritten characters based on the position-width-pulse method of recognition of curves is presented in the article. An algorithm for transformation of characters into curves is presented and a recognition procedure described. Numerical estimators of the proximity S _w of curves that graphically map the image of characters to be recognized relative to printed characters used as reference characters are calculated. A conclusion that assigns a recognized character to a corresponding reference character is arrived at on the basis of the minimum value of S _w with specified reliability.     

Asymptotic assessments of CRC error probabilities in some telecommunication protocols

We study the value distributions for the control cyclic redundancy check (CRC) of length k, drawn at the data section of volume n. The behavior of CRC value distribution is examined at large n and fixed values of k (k = const, n → ∞). With the application of the character theory, we find the conditions of asymptomatic uniformity of the CRC distribution. The asymptomatic results can be applied during the assessment of errors of a series of protocols such as USB, X.25, HDLC, Bluetooth, Ethernet, etc.     

SAGE: Semantic Annotation of Georeferenced Environments

The emergence of portable 3D mapping systems are revolutionizing the way we generate digital 3D models of environments. These systems are human-centric and require the user to hold or carry the device while continuously walking and mapping an environment. In this paper, we adapt this unique coexistence of man and machines to propose SAGE (Semantic Annotation of Georeferenced Environments). SAGE consists of a portable 3D mobile mapping system and a smartphone that enables the user to assign semantic content to georeferenced 3D point clouds while scanning a scene. The proposed system contains several components including touchless speech acquisition, background noise adaptation, real time audio and vibrotactile feedback, automatic speech recognition, distributed clock synchronization, 3D annotation localization, user interaction, and interactive visualization. The most crucial advantage of SAGE technology is that it can be used to infer dynamic activities within an environment. Such activities are difficult to be identified with existing post-processing semantic annotation techniques. The capability of SAGE leads to many promising applications such as intelligent scene classification, place recognition and navigational aid tasks. We conduct several experiments to demonstrate the effectiveness of the proposed system.     

Diverse nearest neighbors queries using linear skylines

k-nearest neighbor (k-NN) queries are well-known and widely used in a plethora of applications. However, in the original definition of k-NN queries there is no concern regarding diversity of the answer set with respect to the user’s interests. For instance, travelers may be looking for touristic sites that are close to where they are, but that would also lead them to see different parts of the city. Likewise, if one is looking for restaurants close by, it may be more interesting to learn about restaurants of different categories or ethnicities which are nonetheless relatively close. The interesting novel aspect of this type of query is that there are two competing criteria to be optimized: closeness and diversity. We propose two approaches that leverage the notion of linear skyline queries in order to find the k diverse nearest neighbors within a radius r from a given query point, or (k, r)-DNNs for short. Our proposed approaches return a relatively small set containing all optimal solutions for any linear combination of the weights a user could give to the two competing criteria, and we consider three different notions of diversity: spatial, categorical and angular. Our experiments, varying a number of parameters and exploring synthetic and real datasets, in both Euclidean space and road networks, respectively, show that our approaches are several orders of magnitude faster than a straightforward approach.     

Fast computation of Gröbner basis of homogenous ideals of $$ \mathbb{F} $$[ x,y]

This paper provides a fast algorithm for Grobnerbases of homogenous ideals of F[x, y] over a finite field F. We show that only the 8-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary 5-polynomials that are processed. We also show that the computational complexity of our new algorithm is O（N^2）, where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

Sub-vector based biometric speaker verification using MLLR super-vector

In this paper, we propose a sub-vector based speaker characterization method for biometric speaker verification, where speakers are represented by uniform segmentation of their maximum likelihood linear regression (MLLR) super-vectors called m-vectors. The MLLR transformation is estimated with respect to universal background model (UBM) without any speech/phonetic information. We introduce two strategies for segmentation of MLLR super-vector: one is called disjoint and other is an overlapped window technique. During test phase, m-vectors of the test utterance are scored against the claimant speaker. Before scoring, m-vectors are post-processed to compensate the session variability. In addition, we propose a clustering algorithm for multiple-class wise MLLR transformation, where Gaussian components of the UBM are clustered into different groups using the concept of expectation maximization (EM) and maximum likelihood (ML). In this case, MLLR transformations are estimated with respect to each class using the sufficient statistics accumulated from the Gaussian components belonging to the particular class, which are then used for m-vector system. The proposed method needs only once alignment of the data with respect to the UBM for multiple MLLR transformations. We first show that the proposed multi-class m-vector system shows promising speaker verification performance when compared to the conventional i-vector based speaker verification system. Secondly, the proposed EM based clustering technique is robust to the random initialization in-contrast to the conventional K-means algorithm and yields system performance better/equal which is best obtained by the K-means. Finally, we show that the fusion of the m-vector with the i-vector further improves the performance of the speaker verification in both score as well as feature domain. The experimental results are shown on various tasks of NIST 2008 speaker recognition evaluation (SRE) core condition.     

Symmetric Masks for In-fill Pixel Interpolation on Discrete <Emphasis Type="Italic">p</Emphasis>:<Emphasis Type="Italic">q</Emphasis> Lattices

A 2D p:q lattice contains image intensity entries at pixels located at regular, staggered intervals that are spaced p rows and q columns apart. Zero values appear at all other intermediate grid locations. We consider here the construction, for any given p:q, of convolution masks to smoothly and uniformly interpolate values across all of the intermediate grid positions. The conventional pixel-filling approach is to allocate intensities proportional to the fractional area that each grid pixel occupies inside the boundaries formed by the p:q lines. However, these area-based masks have asymmetric boundaries, flat interior values and may be odd or even in size. Where edges, lines or points are in-filled, area-based p:q masks imprint intensity patterns that recall p:q because the shape of those masks is asymmetric and depends on p:q. We aim to remove these “memory” artefacts by building symmetric p:q masks. We show here that smoother, symmetric versions of such convolution masks exist. The coefficients of the masks constructed here have simple integer values whose distribution is derived purely from symmetry considerations. We have application for these symmetric interpolation masks as part of a precise image rotation algorithm which disguises the rotation angle, as well as to smooth back-projected values when performing discrete tomographic image reconstruction.     

List decoding for a multiple access hyperchannel

We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size L ≥ 1 for a q-ary multiple access hyperchannel (MAHC) with s ≥ 2 inputs and one output. By definition, an output signal of this channel is the set of symbols of a q-ary alphabet that occur in at least one of the s input signals. For example, in the case of a binary MAHC, where q = 2, an output signal takes values in the ternary alphabet {0, 1, {0, 1}}; namely, it equals 0 (1) if all the s input signals are 0 (1) and equals {0, 1} otherwise. Previously, upper and lower bounds on the code rate for a q-ary MAHC were studied for L ≥ 1 and q = 2, and also for the nonbinary case q ≥ 3 for L = 1 only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of L ≥ 1 and q ≥ 2 in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.     

Topology-Preserving Image Segmentation by Beltrami Representation of Shapes

A new approach using the Beltrami representation of a shape for topology-preserving image segmentation is proposed in this paper. Using the proposed model, the target object can be segmented from the input image by a region of user-prescribed topology. Given a target image I, a template image J is constructed and then deformed with respect to the Beltrami representation. The deformation on J is designed such that the topology of the segmented region is preserved as which the object is interior in J. The topology-preserving property of the deformation is guaranteed by imposing only one constraint on the Beltrami representation, which is easy to be handled. Introducing the Beltrami representation also allows large deformations on the topological prior J, so that it can be a very simple image, such as an image of disks, torus, disjoint disks. Hence, prior shape information of I is unnecessary for the proposed model. Additionally, the proposed model can be easily incorporated with selective segmentation, in which landmark constraints can be imposed interactively to meet any practical need (e.g., medical imaging). High accuracy and stability of the proposed model to deal with different segmentation tasks are validated by numerical experiments on both artificial and real images.     

Vectorizing computations at decoding of nonbinary codes with small density of checks

A modification of the decoding q-ary Sum Product Algorithm (q-SPA) was proposed for the nonbinary codes with small check density based on the permutation matrices. The algorithm described has a vector realization and operates over the vectors defined on the field GF(q), rather than over individual symbols. Under certain code parameters, this approach enables significant speedup of modeling.     

Reverse direction-based surrounder queries for mobile recommendations

This paper proposes a new spatial query called a reverse direction-based surrounder (RDBS) query, which retrieves a user who is seeing a point of interest (POI) as one of their direction-based surrounders (DBSs). According to a user, one POI can be dominated by a second POI if the POIs are directionally close and the first POI is farther from the user than the second is. Two POIs are directionally close if their included angle with respect to the user is smaller than an angular threshold ??. If a POI cannot be dominated by another POI, it is a DBS of the user. We also propose an extended query called competitor RDBS query. POIs that share the same RDBSs with another POI are defined as competitors of that POI. We design algorithms to answer the RDBS queries and competitor queries. The experimental results show that the proposed algorithms can answer the queries efficiently.     

Pseudo-Randomness of Certain Sequences of <Emphasis Type="Italic">k</Emphasis> Symbols with Length <Emphasis Type="Italic">pq</Emphasis>

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.     

A competitive study of the pseudoflow algorithm for the minimum <Emphasis Type="Italic">s</Emphasis>–<Emphasis Type="Italic">t</Emphasis> cut problem in vision applications

Rapid advances in image acquisition and storage technology underline the need for real-time algorithms that are capable of solving large-scale image processing and computer-vision problems. The minimum s–t cut problem, which is a classical combinatorial optimization problem, is a prominent building block in many vision and imaging algorithms such as video segmentation, co-segmentation, stereo vision, multi-view reconstruction, and surface fitting to name a few. That is why finding a real-time algorithm which optimally solves this problem is of great importance. In this paper, we introduce to computer vision the Hochbaum’s pseudoflow (HPF) algorithm, which optimally solves the minimum s–t cut problem. We compare the performance of HPF, in terms of execution times and memory utilization, with three leading published algorithms: (1) Goldberg’s and Tarjan’s Push-Relabel; (2) Boykov’s and Kolmogorov’s augmenting paths; and (3) Goldberg’s partial augment-relabel. While the common practice in computer-vision is to use either BK or PRF algorithms for solving the problem, our results demonstrate that, in general, HPF algorithm is more efficient and utilizes less memory than these three algorithms. This strongly suggests that HPF is a great option for many real-time computer-vision problems that require solving the minimum s–t cut problem.     

Fast Regulation Control of a Class of Input-delayed Linear Systems with Pre-feedback

A control problem of a class of input-delayed linear systems is considered in this paper. Due to the delay τ in the input, any designed feedback controller can only be engaged after t ≥ τ. Then, this can become the cause of slow regulation since any feedback information cannot be available during the delay. So, the initial function defined for -τ ≤ t ≤ 0 is engaged as an ‘initial non-feedback input’ for 0 ≤ t ≤ τ, which governs the system behavior during this initial time period. There have been numerous research results on the control of input-delayed linear systems by far. Yet, there have been no results on the examination and design of this initial function. Utilizing a time optimal control in the existing results, we show that if some pre-feedback as the initial function is engaged, the system response of the input-delayed linear system can be much improved, and a bang-bang input function is a good candidate as a pre-feedback which can provide better starting state values for the state feedback controller in order to perform the fast regulation. Two examples are given for the illustration of our results.     

Social influence determination on big data streams in an online social network

Social networks have become a good place to promote products and also to campaign for causes. Maximizing the spread of information in an online social network at a least cost has attracted the attention of publicist’s. In general, influence user ranking methods are derived either by a network’s topological features or by user features but not both. Existing Influence Maximization Problem (IMP) operates as a modification of greedy algorithms that cannot scale streaming data. Which are time consuming and cannot handle large networks because it requires heavy Monte-Carlo simulation. This is also an NP hard problem in both linear threshold and independent cascade models. Our proposed work aims to address IMP through a Rank-based sampling approach in the Map-Reduce environment. This novel technique combines user and topological features of the network enabling it to handle real-time streaming data. Our experiment of influenced rank-based sampling approach to influence maximization is compared to the greedy approach with and without sampling that exhibits an accuracy of 82%. Performance analysis in terms of running time is reduced from O(n ³) to O(k n). Where ‘k’ is the size of the sample dataset and ‘n’ is the number of user’s.     

Physical layer security of underlay cognitive radio using maximal ratio combining

We investigate the secrecy outage performance of maximal ratio combining (MRC) in cognitive radio networks over Rayleigh fading channels. In a single-input multiple-output wiretap system, we consider a secondary user (SU-TX) that transmits confidential messages to another secondary user (SU-RX) equipped with M (M ≥ 1) antennas where the MRC technique is adopted to improve its received signal-to-noise ratio. Meanwhile, an eavesdropper equipped with N (N ≥ 1) antennas adopts the MRC scheme to overhear the information between SU-TX and SU-RX. SU-TX adopts the underlay strategy to guarantee the service quality of the primary user without spectrum sensing. We derive the closed-form expressions for an exact and asymptotic secrecy outage probability.     

Efficient and secure multi secret sharing schemes based on boolean XOR and arithmetic modulo

Multi Secret Sharing (MSS) scheme is an efficient method of transmitting more than one secret securely. In (n, n)-MSS scheme n secrets are used to create n shares and for reconstruction, all n shares are required. In state of the art schemes n secrets are used to construct n or n + 1 shares, but one can recover partial secret information from less than n shares. There is a need to develop an efficient and secure (n, n)-MSS scheme so that the threshold property can be satisfied. In this paper, we propose three different (n, n)-MSS schemes. In the first and second schemes, Boolean XOR is used and in the third scheme, we used Modular Arithmetic. For quantitative analysis, Similarity metrics, Structural, and Differential measures are considered. A proposed scheme using Modular Arithmetic performs better compared to Boolean XOR. The proposed (n, n)-MSS schemes outperform the existing techniques in terms of security, time complexity, and randomness of shares.     

Cache-Oblivious R-Trees

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant ε, a structure that answers a rectangle query using \(O(\sqrt{N/B}+T/B)\) memory transfers and a point query using O((N/B) ^ε ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.     

Cross-document word matching for segmentation and retrieval of Ottoman divans

Motivated by the need for the automatic indexing and analysis of huge number of documents in Ottoman divan poetry, and for discovering new knowledge to preserve and make alive this heritage, in this study we propose a novel method for segmenting and retrieving words in Ottoman divans. Documents in Ottoman are difficult to segment into words without a prior knowledge of the word. In this study, using the idea that divans have multiple copies (versions) by different writers in different writing styles, and word segmentation in some of those versions may be relatively easier to achieve than in other versions, segmentation of the versions (which are difficult, if not impossible, with traditional techniques) is performed using information carried from the simpler version. One version of a document is used as the source dataset and the other version of the same document is used as the target dataset. Words in the source dataset are automatically extracted and used as queries to be spotted in the target dataset for detecting word boundaries. We present the idea of cross-document word matching for a novel task of segmenting historical documents into words. We propose a matching scheme based on possible combinations of sequence of sub-words. We improve the performance of simple features through considering the words in a context. The method is applied on two versions of Layla and Majnun divan by Fuzuli. The results show that, the proposed word-matching-based segmentation method is promising in finding the word boundaries and in retrieving the words across documents.