OpenRaiser/Intern-Atlas huggingface dataset:
3D/2D Registration of Mapping Catheter Images for Arrhythmia Interventional Assistance
Venue: arXiv cs.CV 2009
Year: 2009

Radiofrequency (RF) catheter ablation has transformed treatment for tachyarrhythmias and has become first-line therapy for some tachycardias. The precise localization of the arrhythmogenic site and the positioning of the RF catheter over that site are problematic: they can impair the efficiency of the procedure and are time consuming (several hours). Electroanatomic mapping technologies are available that enable the display of the cardiac chambers and the relative position of ablation lesions. However, these are expensive and use custom-made catheters. The proposed methodology makes use of standard catheters and inexpensive technology in order to create a 3D volume of the heart chamber affected by the arrhythmia. Further, we propose a novel method that uses a priori 3D information of the mapping catheter in order to estimate the 3D locations of multiple electrodes across single view C-arm images. The monoplane algorithm is tested for feasibility on computer simulations and initial canine data.
Parallel Computation of Finite Element Navier-Stokes codes using MUMPS Solver
Venue: arXiv cs.MS 2009
Year: 2009

The study deals with the parallelization of 2D and 3D finite element based Navier-Stokes codes using direct solvers. Development of sparse direct solvers using multifrontal solvers has significantly reduced the computational time of direct solution methods. Although limited by its stringent memory requirements, multifrontal solvers can be computationally efficient. First the performance of MUltifrontal Massively Parallel Solver (MUMPS) is evaluated for both 2D and 3D codes in terms of memory requirements and CPU times. The scalability of both Newton and modified Newton algorithms is tested.
Color Image Clustering using Block Truncation Algorithm
Venue: arXiv cs.CV 2009
Year: 2009

With the advancement in image capturing device, the image data been generated at high volume. If images are analyzed properly, they can reveal useful information to the human users. Content based image retrieval address the problem of retrieving images relevant to the user needs from image databases on the basis of low-level visual features that can be derived from the images. Grouping images into meaningful categories to reveal useful information is a challenging and important problem. Clustering is a data mining technique to group a set of unsupervised data based on the conceptual clustering principal: maximizing the intraclass similarity and minimizing the interclass similarity. Proposed framework focuses on color as feature. Color Moment and Block Truncation Coding (BTC) are used to extract features for image dataset. Experimental study using K-Means clustering algorithm is conducted to group the image dataset into various clusters.
MIMO Wireless Communications under Statistical Queueing Constraints
Venue: arXiv cs.IT 2009
Year: 2009

The performance of multiple-input multiple-output wireless systems is investigated in the presence of statistical queueing constraints. Queuing constraints are imposed as limitations on buffer violation probabilities. The performance under such constraints is captured through the effective capacity formulation. A detailed analysis of the effective capacity is carried out in the low-power, wideband, and high--signal-to-noise ratio (SNR) regimes. In the low-power analysis, expressions for the first and second derivatives of the effective capacity with respect to SNR at SNR= 0 are obtained under various assumptions on the degree of channel state information at the transmitter. Transmission strategies that are optimal in the sense of achieving the first and second derivatives are identified. It is shown that while the first derivative does not get affected by the presence of queueing constraints, the second derivative gets smaller as the constraints become more stringent. Through the energy efficiency analysis, this is shown to imply that the minimum bit energy requirements do not change with more strict limitations but the wideband slope diminishes. Similar results are obtained in the wideband regime if rich multipath fading is being experienced. On the other hand, sparse multipath fading with bounded number of degrees of freedom is shown to increase the minimum bit energy requirements in the presence of queueing constraints. Following the low-SNR study, the impact of buffer limitations on the high-SNR performance is quantified by analyzing the high-SNR slope and the power offset in Rayleigh fading channels. Finally, numerical results are provided to illustrate the theoretical findings.
Binary Linear-Time Erasure Decoding for Non-Binary LDPC codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel, this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.
Interference with Symbol-misalignment
Venue: arXiv cs.NI 2009
Year: 2009

This paper studies the impact of interference asynchrony among different links in a wireless network. Without deliberate coordination and cooperation among the active links, there is a naturally occurring misalignment between the symbols of the targeted signal of a receiver and the symbols of the interfering signals. Interestingly, we show that the interference asynchrony can actually improve the BER performance, compared with the situation in which symbols of al signals ay aligned. In particular, we show that symbol misalignment can decrease the "effective interference power" and change the distribution of the interfering signals, in a way that results in lower BER. To ensure that symbol misalignment can be consistently attained, we propose two simple schemes that introduce time-varying symbol offsets to obtain an "average" performance of random symbol misalignment. Notably, our schemes do not change the simple receiver design structure; only the transmitters are modified in a minor way.
Generalizations of Wei's Duality Theorem
Venue: arXiv cs.IT 2009
Year: 2009

Wei's celebrated Duality Theorem is generalized in several ways, expressed as duality theorems for linear codes over division rings and, more generally, duality theorems for matroids. These results are further generalized, resulting in two Wei-type duality theorems for new combinatorial structures that are introduced and named {\em demi-matroids}. These generalize matroids and are the appropriate combinatorial objects for describing the duality in Wei's Duality Theorem. A new proof of the Duality Theorem is thereby given that explains the theorem in combinatorial terms. Special cases of the general duality theorems are also given, including duality theorems for cycles and bonds in graphs and for transversals.
A critical look at power law modelling of the Internet
Venue: arXiv cs.NI 2009
Year: 2009

This paper takes a critical look at the usefulness of power law models of the Internet. The twin focuses of the paper are Internet traffic and topology generation. The aim of the paper is twofold. Firstly it summarises the state of the art in power law modelling particularly giving attention to existing open research questions. Secondly it provides insight into the failings of such models and where progress needs to be made for power law research to feed through to actual improvements in network performance.
Improving Integral Cryptanalysis against Rijndael with Large Blocks
Venue: arXiv cs.CR 2009
Year: 2009

This report presents new four-round integral properties against the Rijndael cipher with block sizes larger than 128 bits. Using higher-order multiset distinguishers and other well-known extensions of those properties, the deduced attacks reach up to 7 and 8 rounds of Rijndael variants with 160 up to 256-bit blocks. For example, a 7-rounds attack against Rijndael-224 has a time complexity equal to $2^{80}$.
Finite element model selection using Particle Swarm Optimization
Venue: arXiv cs.AI 2009
Year: 2009

This paper proposes the application of particle swarm optimization (PSO) to the problem of finite element model (FEM) selection. This problem arises when a choice of the best model for a system has to be made from set of competing models, each developed a priori from engineering judgment. PSO is a population-based stochastic search algorithm inspired by the behaviour of biological entities in nature when they are foraging for resources. Each potentially correct model is represented as a particle that exhibits both individualistic and group behaviour. Each particle moves within the model search space looking for the best solution by updating the parameters values that define it. The most important step in the particle swarm algorithm is the method of representing models which should take into account the number, location and variables of parameters to be updated. One example structural system is used to show the applicability of PSO in finding an optimal FEM. An optimal model is defined as the model that has the least number of updated parameters and has the smallest parameter variable variation from the mean material properties. Two different objective functions are used to compare performance of the PSO algorithm.
The Complexity of Translation Membership for Macro Tree Transducers
Venue: arXiv cs.FL 2009
Year: 2009

Macro tree transducers (mtts) are a useful formal model for XML query and transformation languages. In this paper one of the fundamental decision problems on translations, namely the "translation membership problem" is studied for mtts. For a fixed translation, the translation membership problem asks whether a given input/output pair is element of the translation. For call-by-name mtts this problem is shown to be NP-complete. The main result is that translation membership for call-by-value mtts is in polynomial time. For several extensions, such as addition of regular look-ahead or the generalization to multi-return mtts, it is shown that translation membership still remains in PTIME.
An algorithm for computing cutpoints in finite metric spaces
Venue: arXiv cs.DS 2009
Year: 2009

The theory of the tight span, a cell complex that can be associated to every metric $D$, offers a unifying view on existing approaches for analyzing distance data, in particular for decomposing a metric $D$ into a sum of simpler metrics as well as for representing it by certain specific edge-weighted graphs, often referred to as realizations of $D$. Many of these approaches involve the explicit or implicit computation of the so-called cutpoints of (the tight span of) $D$, such as the algorithm for computing the "building blocks" of optimal realizations of $D$ recently presented by A. Hertz and S. Varone. The main result of this paper is an algorithm for computing the set of these cutpoints for a metric $D$ on a finite set with $n$ elements in $O(n^3)$ time. As a direct consequence, this improves the run time of the aforementioned $O(n^6)$-algorithm by Hertz and Varone by ``three orders of magnitude''.
Accelerating the Execution of Matrix Languages on the Cell Broadband Engine Architecture
Venue: arXiv cs.PL 2009
Year: 2009

Matrix languages, including MATLAB and Octave, are established standards for applications in science and engineering. They provide interactive programming environments that are easy to use due to their scripting languages with matrix data types. Current implementations of matrix languages do not fully utilise high-performance, special-purpose chip architectures such as the IBM PowerXCell processor (Cell), which is currently used in the fastest computer in the world. We present a new framework that extends Octave to harness the computational power of the Cell. With this framework the programmer is relieved of the burden of introducing explicit notions of parallelism. Instead the programmer uses a new matrix data-type to execute matrix operations in parallel on the synergistic processing elements (SPEs) of the Cell. We employ lazy evaluation semantics for our new matrix data-type to obtain execution traces of matrix operations. Traces are converted to data dependence graphs; operations in the data dependence graph are lowered (split into sub-matrices), scheduled and executed on the SPEs. Thereby we exploit (1) data parallelism, (2) instruction level parallelism, (3) pipeline parallelism and (4) task parallelism of matrix language programs. We conducted extensive experiments to show the validity of our approach. Our Cell-based implementation achieves speedups of up to a factor of 12 over code run on recent Intel Core2 Quad processors.
Applying physical layer network coding in wireless networks
Venue: arXiv cs.NI 2009
Year: 2009

A main distinguishing feature of a wireless network compared with a wired network is its broadcast nature, in which the signal transmitted by a node may reach several other nodes, and a node may receive signals from several other nodes, simultaneously. Rather than a blessing, this feature is treated more as an interference-inducing nuisance in most wireless networks today (e.g., IEEE 802.11). This paper shows that the concept of network coding can be applied at the physical layer to turn the broadcast property into a capacity-boosting advantage in wireless ad hoc networks. Specifically, we propose a physical-layer network coding (PNC) scheme to coordinate transmissions among nodes. In contrast to "straightforward" network coding which performs coding arithmetic on digital bit streams after they have been received, PNC makes use of the additive nature of simultaneously arriving electromagnetic (EM) waves for equivalent coding operation. And in doing so, PNC can potentially achieve 100% and 50% throughput increases compared with traditional transmission and straightforward network coding, respectively, in 1-D regular linear networks with multiple random flows. The throughput improvements are even larger in 2-D regular networks: 200% and 100%, respectively.
Type Safe Extensible Programming
Venue: arXiv cs.PL 2009
Year: 2009

Software products evolve over time. Sometimes they evolve by adding new features, and sometimes by either fixing bugs or replacing outdated implementations with new ones. When software engineers fail to anticipate such evolution during development, they will eventually be forced to re-architect or re-build from scratch. Therefore, it has been common practice to prepare for changes so that software products are extensible over their lifetimes. However, making software extensible is challenging because it is difficult to anticipate successive changes and to provide adequate abstraction mechanisms over potential changes. Such extensibility mechanisms, furthermore, should not compromise any existing functionality during extension. Software engineers would benefit from a tool that provides a way to add extensions in a reliable way. It is natural to expect programming languages to serve this role. Extensible programming is one effort to address these issues. In this thesis, we present type safe extensible programming using the MLPolyR language. MLPolyR is an ML-like functional language whose type system provides type-safe extensibility mechanisms at several levels. After presenting the language, we will show how these extensibility mechanisms can be put to good use in the context of product line engineering. Product line engineering is an emerging software engineering paradigm that aims to manage variations, which originate from successive changes in software.
Behavior Subtraction
Venue: arXiv cs.CV 2009
Year: 2009

Background subtraction has been a driving engine for many computer vision and video analytics tasks. Although its many variants exist, they all share the underlying assumption that photometric scene properties are either static or exhibit temporal stationarity. While this works in some applications, the model fails when one is interested in discovering {\it changes in scene dynamics} rather than those in a static background; detection of unusual pedestrian and motor traffic patterns is but one example. We propose a new model and computational framework that address this failure by considering stationary scene dynamics as a ``background'' with which observed scene dynamics are compared. Central to our approach is the concept of an {\it event}, that we define as short-term scene dynamics captured over a time window at a specific spatial location in the camera field of view. We compute events by time-aggregating motion labels, obtained by background subtraction, as well as object descriptors (e.g., object size). Subsequently, we characterize events probabilistically, but use a low-memory, low-complexity surrogates in practical implementation. Using these surrogates amounts to {\it behavior subtraction}, a new algorithm with some surprising properties. As demonstrated here, behavior subtraction is an effective tool in anomaly detection and localization. It is resilient to spurious background motion, such as one due to camera jitter, and is content-blind, i.e., it works equally well on humans, cars, animals, and other objects in both uncluttered and highly-cluttered scenes. Clearly, treating video as a collection of events rather than colored pixels opens new possibilities for video analytics.
Computing rational points in convex semi-algebraic sets and SOS decompositions
Venue: arXiv cs.SC 2009
Year: 2009

Let ${\cal P}=\{h_1, ..., h_s\}\subset \Z[Y_1, ..., Y_k]$, $D\geq °(h_i)$ for $1\leq i \leq s$, $σ$ bounding the bit length of the coefficients of the $h_i$'s, and $Φ$ be a quantifier-free ${\cal P}$-formula defining a convex semi-algebraic set. We design an algorithm returning a rational point in ${\cal S}$ if and only if ${\cal S}\cap \Q\neq\emptyset$. It requires $σ^{\bigO(1)}D^{\bigO(k^3)}$ bit operations. If a rational point is outputted its coordinates have bit length dominated by $σD^{\bigO(k^3)}$. Using this result, we obtain a procedure deciding if a polynomial $f\in \Z[X_1, >..., X_n]$ is a sum of squares of polynomials in $\Q[X_1, ..., X_n]$. Denote by $d$ the degree of $f$, $τ$ the maximum bit length of the coefficients in $f$, $D={{n+d}\choose{n}}$ and $k\leq D(D+1)-{{n+2d}\choose{n}}$. This procedure requires $τ^{\bigO(1)}D^{\bigO(k^3)}$ bit operations and the coefficients of the outputted polynomials have bit length dominated by $τD^{\bigO(k^3)}$.
Degraded Compound Multi-receiver Wiretap Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the degraded compound multi-receiver wiretap channel. The degraded compound multi-receiver wiretap channel consists of two groups of users and a group of eavesdroppers, where, if we pick an arbitrary user from each group of users and an arbitrary eavesdropper, they satisfy a certain Markov chain. We study two different communication scenarios for this channel. In the first scenario, the transmitter wants to send a confidential message to users in the first (stronger) group and a different confidential message to users in the second (weaker) group, where both messages need to be kept confidential from the eavesdroppers. For this scenario, we assume that there is only one eavesdropper. We obtain the secrecy capacity region for the general discrete memoryless channel model, the parallel channel model, and the Gaussian parallel channel model. For the Gaussian multiple-input multiple-output (MIMO) channel model, we obtain the secrecy capacity region when there is only one user in the second group. In the second scenario we study, the transmitter sends a confidential message to users in the first group which needs to be kept confidential from the second group of users and the eavesdroppers. Furthermore, the transmitter sends a different confidential message to users in the second group which needs to be kept confidential only from the eavesdroppers. For this scenario, we do not put any restriction on the number of eavesdroppers. As in the first scenario, we obtain the secrecy capacity region for the general discrete memoryless channel model, the parallel channel model, and the Gaussian parallel channel model. For the Gaussian MIMO channel model, we establish the secrecy capacity region when there is only one user in the second group.
Self-Dual Codes over Z_2xZ_4
Venue: arXiv cs.IT 2009
Year: 2009

Self-dual codes over $\Z_2\times\Z_4$ are subgroups of $\Z_2^α\times\Z_4^β$ that are equal to their orthogonal under an inner-product that relates to the binary Hamming scheme. Three types of self-dual codes are defined. For each type, the possible values $α,β$ such that there exist a code $\C\subseteq \Z_2^α\times\Z_4^β$ are established. Moreover, the construction of a $\add$-linear code for each type and possible pair $(α,β)$ is given. Finally, the standard techniques of invariant theory are applied to describe the weight enumerators for each type.
Secrecy Rate Region of the Broadcast Channel with an Eavesdropper
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider a scenario where a source node wishes to broadcast two confidential messages to two receivers, while a wire-tapper also receives the transmitted signal. This model is motivated by wireless communications, where individual secure messages are broadcast over open media and can be received by any illegitimate receiver. The secrecy level is measured by the equivocation rate at the eavesdropper. We first study the general (non-degraded) broadcast channel with an eavesdropper. We present an inner bound on the secrecy capacity region for this model. This inner bound is based on a combination of random binning, and the Gelfand-Pinsker binning. We further study the situation in which the channels are degraded. For the degraded broadcast channel with an eavesdropper, we present the secrecy capacity region. Our achievable coding scheme is based on Covers superposition scheme and random binning. We refer to this scheme as the Secret Superposition Scheme. Our converse proof is based on a combination of the converse proof of the conventional degraded broadcast channel and Csiszar Lemma. We then assume that the channels are Additive White Gaussian Noise (AWGN) and show that the Secret Superposition Scheme with Gaussian codebook is optimal. The converse proof is based on Costas entropy power inequality. Finally, we use a broadcast strategy for the slowly fading wire-tap channel when only the eavesdroppers channel is fixed and known at the transmitter. We derive the optimum power allocation for the coding layers, which maximizes the total average rate.
On the transmit strategy for the interference MIMO relay channel in the low power regime
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the interference channel with two transmitters and two receivers in the presence of a MIMO relay in the low transmit power regime. A communication scheme combining block Markov encoding, beamforming, and Willems' backward decoding is used. With this scheme, we get an interference channel with channel gains dependent on the signal power. A power allocation for this scheme is proposed, and the achievable rate region with this power allocation is given. We show that, at low transmit powers, with equal power constraints at the relay and the transmitters, the interference channel with a MIMO relay achieves a sum rate that is linear in the power. This sum rate is determined by the channel setup. We also show that in the presence of abundant power at the relay, the transmit strategy is significantly simplified, and the MAC from the transmitters to the relay forms the bottle neck of the system from the sum rate point of view.