OpenRaiser/Intern-Atlas huggingface dataset:
Implementation of Radon Transformation for Electrical Impedance Tomography (EIT)
Venue: arXiv cs.CV 2012
Year: 2012

Radon Transformation is generally used to construct optical image (like CT image) from the projection data in biomedical imaging. In this paper, the concept of Radon Transformation is implemented to reconstruct Electrical Impedance Topographic Image (conductivity or resistivity distribution) of a circular subject. A parallel resistance model of a subject is proposed for Electrical Impedance Topography(EIT) or Magnetic Induction Tomography(MIT). A circular subject with embedded circular objects is segmented into equal width slices from different angles. For each angle, Conductance and Conductivity of each slice is calculated and stored in an array. A back projection method is used to generate a two-dimensional image from one-dimensional projections. As a back projection method, Inverse Radon Transformation is applied on the calculated conductance and conductivity to reconstruct two dimensional images. These images are compared to the target image. In the time of image reconstruction, different filters are used and these images are compared with each other and target image.
Ordered Statistics Vertex Extraction and Tracing Algorithm (OSVETA)
Venue: arXiv cs.CG 2012
Year: 2012

We propose an algorithm for identifying vertices from three dimensional (3D) meshes that are most important for a geometric shape creation. Extracting such a set of vertices from a 3D mesh is important in applications such as digital watermarking, but also as a component of optimization and triangulation. In the first step, the Ordered Statistics Vertex Extraction and Tracing Algorithm (OSVETA) estimates precisely the local curvature, and most important topological features of mesh geometry. Using the vertex geometric importance ranking, the algorithm traces and extracts a vector of vertices, ordered by decreasing index of importance.
A short proof that $χ$ can be bounded $ε$ away from $Δ+1$ towards $ω$
Venue: arXiv cs.DM 2012
Year: 2012

In 1998 the second author proved that there is an $ε>0$ such that every graph satisfies $χ\leq \lceil (1-ε)(Δ+1)+εω\rceil$. The first author recently proved that any graph satisfying $ω> \frac 23(Δ+1)$ contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.
Probabilistic modal μ-calculus with independent product
Venue: arXiv cs.LO 2012
Year: 2012

The probabilistic modal μ-calculus is a fixed-point logic designed for expressing properties of probabilistic labeled transition systems (PLTS's). Two equivalent semantics have been studied for this logic, both assigning to each state a value in the interval [0,1] representing the probability that the property expressed by the formula holds at the state. One semantics is denotational and the other is a game semantics, specified in terms of two-player stochastic parity games. A shortcoming of the probabilistic modal μ-calculus is the lack of expressiveness required to encode other important temporal logics for PLTS's such as Probabilistic Computation Tree Logic (PCTL). To address this limitation we extend the logic with a new pair of operators: independent product and coproduct. The resulting logic, called probabilistic modal μ-calculus with independent product, can encode many properties of interest and subsumes the qualitative fragment of PCTL. The main contribution of this paper is the definition of an appropriate game semantics for this extended probabilistic μ-calculus. This relies on the definition of a new class of games which generalize standard two-player stochastic (parity) games by allowing a play to be split into concurrent subplays, each continuing their evolution independently. Our main technical result is the equivalence of the two semantics. The proof is carried out in ZFC set theory extended with Martin's Axiom at an uncountable cardinal.
Explosion prediction of oil gas using SVM and Logistic Regression
Venue: arXiv cs.CE 2012
Year: 2012

The prevention of dangerous chemical accidents is a primary problem of industrial manufacturing. In the accidents of dangerous chemicals, the oil gas explosion plays an important role. The essential task of the explosion prevention is to estimate the better explosion limit of a given oil gas. In this paper, Support Vector Machines (SVM) and Logistic Regression (LR) are used to predict the explosion of oil gas. LR can get the explicit probability formula of explosion, and the explosive range of the concentrations of oil gas according to the concentration of oxygen. Meanwhile, SVM gives higher accuracy of prediction. Furthermore, considering the practical requirements, the effects of penalty parameter on the distribution of two types of errors are discussed.
3D Scene Grammar for Parsing RGB-D Pointclouds
Venue: arXiv cs.CV 2012
Year: 2012

We pose 3D scene-understanding as a problem of parsing in a grammar. A grammar helps us capture the compositional structure of real-word objects, e.g., a chair is composed of a seat, a back-rest and some legs. Having multiple rules for an object helps us capture structural variations in objects, e.g., a chair can optionally also have arm-rests. Finally, having rules to capture composition at different levels helps us formulate the entire scene-processing pipeline as a single problem of finding most likely parse-tree---small segments combine to form parts of objects, parts to objects and objects to a scene. We attach a generative probability model to our grammar by having a feature-dependent probability function for every rule. We evaluated it by extracting labels for every segment and comparing the results with the state-of-the-art segment-labeling algorithm. Our algorithm was outperformed by the state-or-the-art method. But, Our model can be trained very efficiently (within seconds), and it scales only linearly in with the number of rules in the grammar. Also, we think that this is an important problem for the 3D vision community. So, we are releasing our dataset and related code.
On the necessity of complexity
Venue: arXiv cs.LO 2012
Year: 2012

Wolfram's Principle of Computational Equivalence (PCE) implies that universal complexity abounds in nature. This paper comprises three sections. In the first section we consider the question why there are so many universal phenomena around. So, in a sense, we week a driving force behind the PCE if any. We postulate a principle GNS that we call the Generalized Natural Selection Principle that together with the Church-Turing Thesis is seen to be equivalent to a weak version of PCE. In the second section we ask the question why we do not observe any phenomena that are complex but not-universal. We choose a cognitive setting to embark on this question and make some analogies with formal logic. In the third and final section we report on a case study where we see rich structures arise everywhere.
Approximability and proof complexity
Venue: arXiv cs.CC 2012
Year: 2012

This work is concerned with the proof-complexity of certifying that optimization problems do \emph{not} have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof system is automatizable using semidefinite programming (SDP), meaning that any $n$-variable degree-$d$ proof can be found in time $n^{O(d)}$. Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the "$d/2$-round Lasserre value" of an optimization problem is equal to the best bound provable using a degree-$d$ SOS proof. These ideas were exploited in a recent paper by Barak et al.\ (STOC 2012) which shows that the known "hard instances" for the Unique-Games problem are in fact solved close to optimally by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al.\ can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot--Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor .952 ($> .878$) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?
Hardness Results on Curve/Point Set Matching with Fréchet Distance
Venue: arXiv cs.CG 2012
Year: 2012

Let P be a polygonal curve in R^d of length n, and S be a point-set of size k. We consider the problem of finding a polygonal curve Q on S such that all points in S are visited and the Fréchet distance from $P$ is less than a given epsilon. We show that this problem is NP-complete, regardless of whether or not points from S are allowed be visited more than once. However, we also show that if the problem instance satisfies certain restrictions, the problem is polynomial-time solvable, and we briefly outline an algorithm that computes Q.
Mobile-to-Mobile Video Recommendation
Venue: arXiv cs.NI 2012
Year: 2012

Mobile device users can now easily capture and socially share video clips in a timely manner by uploading them wirelessly to a server. When attending crowded events, such as an exhibition or the Olympic Games, however, timely sharing of videos becomes difficult due to choking bandwidth in the network infrastructure, preventing like-minded attendees from easily sharing videos with each other through a server. One solution to alleviate this problem is to use direct device-to-device communication to share videos among nearby attendees. Contact capacity between two devices, however, is limited, and thus a recommendation algorithm, such as collaborative filtering, is needed to select and transmit only videos of potential interest to an attendee. In this paper, we address the question: which video clip should be transmitted to which user. We proposed an video transmission scheduling algorithm, called CoFiGel, that runs in a distributed manner and aims to improve both the prediction coverage and precision of the collaborative filtering algorithm. At each device, CoFiGel transmits the video that would increase the estimated number of positive user-video ratings the most if this video is transferred to the destination device. We evaluated CoFiGel using real-world traces and show that substantial improvement can be achieved compared to baseline schemes that do not consider rating or contact history.
Dynamic Popular Content Distribution in Vehicular Networks using Coalition Formation Games
Venue: arXiv cs.GT 2012
Year: 2012

Driven by both safety concerns and commercial interests, vehicular ad hoc networks (VANETs) have recently received considerable attentions. In this paper, we address popular content distribution (PCD) in VANETs, in which one large popular file is downloaded from a stationary roadside unit (RSU), by a group of on-board units (OBUs) driving through an area of interest (AoI) along a highway. Due to high speeds of vehicles and deep fadings of vehicle-to-roadside (V2R) channels, some of the vehicles may not finish downloading the entire file but only possess several pieces of it. To successfully send a full copy to each OBU, we propose a cooperative approach based on the coalition formation games, in which OBUs exchange their possessed pieces by broadcasting to and receiving from their neighbors. Simulation results show that our proposed approach presents a considerable performance improvement relative to the non-cooperative approach, in which the OBUs broadcast randomly selected pieces to their neighbors as along as the spectrum is detected to be unoccupied.
Improved Modeling of the Correlation Between Continuous-Valued Sources in LDPC-Based DSC
Venue: arXiv cs.IT 2012
Year: 2012

Accurate modeling of the correlation between the sources plays a crucial role in the efficiency of distributed source coding (DSC) systems. This correlation is commonly modeled in the binary domain by using a single binary symmetric channel (BSC), both for binary and continuous-valued sources. We show that "one" BSC cannot accurately capture the correlation between continuous-valued sources; a more accurate model requires "multiple" BSCs, as many as the number of bits used to represent each sample. We incorporate this new model into the DSC system that uses low-density parity-check (LDPC) codes for compression. The standard Slepian-Wolf LDPC decoder requires a slight modification so that the parameters of all BSCs are integrated in the log-likelihood ratios (LLRs). Further, using an interleaver the data belonging to different bit-planes are shuffled to introduce randomness in the binary domain. The new system has the same complexity and delay as the standard one. Simulation results prove the effectiveness of the proposed model and system.
Results on Finite Wireless Sensor Networks: Connectivity and Coverage
Venue: arXiv cs.IT 2012
Year: 2012

Many analytic results for the connectivity, coverage, and capacity of wireless networks have been reported for the case where the number of nodes, $n$, tends to infinity (large-scale networks). The majority of these results have not been extended for small or moderate values of $n$; whereas in many practical networks, $n$ is not very large. In this paper, we consider finite (small-scale) wireless sensor networks. We first show that previous asymptotic results provide poor approximations for such networks. We provide a set of differences between small-scale and large-scale analysis and propose a methodology for analysis of finite sensor networks. Furthermore, we consider two models for such networks: unreliable sensor grids, and sensor networks with random node deployment. We provide easily computable expressions for bounds on the coverage and connectivity of these networks. With validation from simulations, we show that the derived analytic expressions give very good estimates of such quantities for finite sensor networks. Our investigation confirms the fact that small-scale networks possesses unique characteristics different from the large-scale counterparts, necessitating the development of a new framework for their analysis and design.
To What Extent Would E-mall Enable SMEs to Adopt E-Commerce?
Venue: arXiv cs.CY 2012
Year: 2012

This paper presents findings from a study of e-commerce adoption by Small and Medium Enterprises (SMEs) in Saudi Arabia. Only tiny number of Saudi commercial organizations, mostly medium and large companies from the manufacturing sector, in involved in e-commerce implementation. The latest report released in 2010 by The Communications and Information Technology Commission (CITC) in Saudi Arabia shows that only 8% of businesses sell online. Accordingly new research has been conducted to explore to what extent electronic mall (e-mall) would enable SMEs in Saudi Arabia to adopt and use online channels for their sales. A quantitative analysis of responses obtained from a survey of 108 SMEs in Saudi Arabia was conducted. The main results of the current analysis demonstrate the significant of organizational factors, and technology and environmental factors. Interestingly, traditional & cultural factors have no significance in this regard.
EGovernment Stage Model: Evaluating the Rate of Web Development Progress of Government Websites in Saudi Arabia
Venue: arXiv cs.CY 2012
Year: 2012

This paper contributes to the issue of eGovernment implementation in Saudi Arabia by discussing the current situation of ministry websites. It evaluates the rate of web development progress of vital government websites in Saudi Arabia using the eGovernment stage model. In 2010, Saudi Arabia ranked 58th in the world and 4th in the Gulf region in eGovernment readiness according to United Nations reports. In particular, Saudi Arabia has ranked 75th worldwide for its online service index and its components compared to the neighbouring Gulf country of Bahrain, which was ranked 8th for the same index. While this is still modest in relation to the Saudi government expectation concerning its vision for eGovernment implementation for 2010, and the results achieved by the neighbouring Gulf countries such as Bahrain and the United Arab Emirates on the eGovernment index, the Saudi government has endeavoured to meet the public needs concerning eGovernment and carry out the implementation of eGovernment properly. Governments may heed the importance of actively launching official government websites as the main portals for delivering their online services to all the different categories of eGovernment (including G2C, G2B, and G2G). However, certain Saudi ministries have not given due attention to this vital issue. This is evidenced by the fact that some of their websites are not fully developed or do not yet exist, which clearly impedes that particular ministry from appropriately delivering eServices.
A Semi-Structured Tailoring-Driven Approach for ERP Selection
Venue: arXiv cs.OH 2012
Year: 2012

It has been widely reported that selecting an inappropriate system is a major reason for ERP implementation failures. The selection of an ERP system is therefore critical. While the number of papers related to ERP implementation is substantial, ERP evaluation and selection approaches have received few attention. Motivated by the adaptation concept of the ERP systems, we propose in this paper a semi-structured approach for ERP system selection that differs from existing models in that it has a more holistic focus by simultaneously 1) considering the anticipated fitness of ERP solutions after the optimal resolution, within limited resources, of a set of the identified mismatches and 2) evaluating candidate products according to both functional and non-functional requirements. The approach consists of an iterative selection process model and an evaluation methodology based on 0-1 linear programming and MACBETH technique to elaborate multi-criteria performance expressions.
A Note on the Deletion Channel Capacity
Venue: arXiv cs.IT 2012
Year: 2012

Memoryless channels with deletion errors as defined by a stochastic channel matrix allowing for bit drop outs are considered in which transmitted bits are either independently deleted with probability $d$ or unchanged with probability $1-d$. Such channels are information stable, hence their Shannon capacity exists. However, computation of the channel capacity is formidable, and only some upper and lower bounds on the capacity exist. In this paper, we first show a simple result that the parallel concatenation of two different independent deletion channels with deletion probabilities $d_1$ and $d_2$, in which every input bit is either transmitted over the first channel with probability of $λ$ or over the second one with probability of $1-λ$, is nothing but another deletion channel with deletion probability of $d=λd_1+(1-λ)d_2$. We then provide an upper bound on the concatenated deletion channel capacity $C(d)$ in terms of the weighted average of $C(d_1)$, $C(d_2)$ and the parameters of the three channels. An interesting consequence of this bound is that $C(λd_1+(1-λ))\leq λC(d_1)$ which enables us to provide an improved upper bound on the capacity of the i.i.d. deletion channels, i.e., $C(d)\leq 0.4143(1-d)$ for $d\geq 0.65$. This generalizes the asymptotic result by Dalai as it remains valid for all $d\geq 0.65$. Using the same approach we are also able to improve upon existing upper bounds on the capacity of the deletion/substitution channel.
A Comparative Study of Gaussian Mixture Model and Radial Basis Function for Voice Recognition
Venue: arXiv cs.LG 2012
Year: 2012

A comparative study of the application of Gaussian Mixture Model (GMM) and Radial Basis Function (RBF) in biometric recognition of voice has been carried out and presented. The application of machine learning techniques to biometric authentication and recognition problems has gained a widespread acceptance. In this research, a GMM model was trained, using Expectation Maximization (EM) algorithm, on a dataset containing 10 classes of vowels and the model was used to predict the appropriate classes using a validation dataset. For experimental validity, the model was compared to the performance of two different versions of RBF model using the same learning and validation datasets. The results showed very close recognition accuracy between the GMM and the standard RBF model, but with GMM performing better than the standard RBF by less than 1% and the two models outperformed similar models reported in literature. The DTREG version of RBF outperformed the other two models by producing 94.8% recognition accuracy. In terms of recognition time, the standard RBF was found to be the fastest among the three models.
Fixed-Orientation Equilateral Triangle Matching of Point Sets
Venue: arXiv cs.CG 2012
Year: 2012

Given a point set $P$ and a class $\mathcal{C}$ of geometric objects, $G_\mathcal{C}(P)$ is a geometric graph with vertex set $P$ such that any two vertices $p$ and $q$ are adjacent if and only if there is some $C \in \mathcal{C}$ containing both $p$ and $q$ but no other points from $P$. We study $G_{\bigtriangledown}(P)$ graphs where $\bigtriangledown$ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-$Θ_6$ graphs and TD-Delaunay graphs. The main result in our paper is that for point sets $P$ in general position, $G_{\bigtriangledown}(P)$ always contains a matching of size at least $\lceil\frac{n-2}{3}\rceil$ and this bound cannot be improved above $\lceil\frac{n-1}{3}\rceil$. We also give some structural properties of $G_{\davidsstar}(P)$ graphs, where $\davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G_{\davidsstar}(P)$ is simply a path. Through the equivalence of $G_{\davidsstar}(P)$ graphs with $Θ_6$ graphs, we also derive that any $Θ_6$ graph can have at most $5n-11$ edges, for point sets in general position.
Systematic and Integrative Analysis of Proteomic Data using Bioinformatics Tools
Venue: arXiv cs.CE 2012
Year: 2012

The analysis and interpretation of relationships between biological molecules is done with the help of networks. Networks are used ubiquitously throughout biology to represent the relationships between genes and gene products. Network models have facilitated a shift from the study of evolutionary conservation between individual gene and gene products towards the study of conservation at the level of pathways and complexes. Recent work has revealed much about chemical reactions inside hundreds of organisms as well as universal characteristics of metabolic networks, which shed light on the evolution of the networks. However, characteristics of individual metabolites have been neglected in this network. The current paper provides an overview of bioinformatics software used in visualization of biological networks using proteomic data, their main functions and limitations of the software.