A robust O(N log n) algorithm for optimal decoding of first-orderΣ-Δ sequences

An exact recursive formula is derived to describe the structure of an ideal first-order Σ-Δ output sequence as a function of its input. Specifically, it is shown that every Σ-Δ sequence generated by the constant input x∈[0, 1] can be decomposed into a shorter E-A subsequence whose input x'∈[0, 1) may be used to recover that of the original Σ-Δ sequence. This formula is applied to develop an O(N log N) algorithm for decoding an N-length sequence. Without knowledge of the modulator's initial state, it exhibits an average improvement, over all initial states, of 4.2 dB in output signal-to-noise ratio (SNR) compared with a near-optimal linear finite impulse response (FIR) filter. The regularity of the ideal first-order Σ-Δ structure with constant inputs permits the algorithm to be extended to bandlimited and noise-corrupted data. A simple error correction procedure is demonstrated, and it is shown that the recursive algorithm can outperform FIR filters on sequences of length N<64 having input SNRs as low as 30 dB     

Convolution backprojection formulas for 3-D vector tomography withapplication to MRI

Vector tomography is the reconstruction of vector fields from measurements of their projections. In previous work, it has been shown that the reconstruction of a general three-dimensional (3-D) vector field is possible from the so-called inner product measurements. It has also been shown how the reconstruction of either the irrotational or solenoidal component of a vector field can be accomplished with fewer measurements than that required for the full field. The present paper makes three contributions. First, in analogy to the two-dimensional (2-D) approach of Norton (1988), several 3-D projection theorems are developed. These lead directly to new vector field reconstruction formulas that are convolution backprojection formulas. It is shown how the local reconstruction property of these 3-D reconstruction formulas permits reconstruction of point flow or of regional flow from a limited data set. Second, simulations demonstrating 3-D reconstructions, both local and nonlocal, are presented. Using the formulas derived herein and those derived in previous work, these results demonstrate the reconstruction of the irrotational and solenoidal components, their potential functions, and the field itself from simulated inner product measurement data. Finally, it is shown how 3-D inner product measurements can be acquired using a magnetic resonance scanner     

Efficient algorithm for 2-D arithmetic Fourier transform

This article presents an efficient algorithm for the two-dimensional (2-D) arithmetic Fourier transform (AFT) based on the Mobius inversion formula of odd number series. It requires fewer multiplications and has less complexity over previous algorithms. In addition, a technique is proposed to carry out the on-axis Fourier coefficients. A parallel VLSI architecture is developed for the new algorithm     

A new algorithm to compute the discrete inverse radon transform

The aim of this paper is to compute the discrete inverse Radon transform over ⁿ . The Radon transform is a function with domainS ^n–1×. It is shown that under different measure this function can be defined with domain ⁿ . In this case one can compute the discrete inverse Radon transform in the Cartesian coordinate system without interpolating from polar to Cartesian coordinates or using the backprojection operator.     

Vector-radix algorithm for a 2-D discrete Hartley transform

A new multidimensional Hartley transform is defined and a vector-radix algorithm for fast computation of the transform is developed. The algorithm is shown to be faster (in terms of multiplication and addition count) compared to other related algorithms.     

Architectures for finite radon transform

Two VLSI architectures for the finite Radon transform are presented. The first is a reference architecture using memory blocks and the second is a memoryless architecture. The proposed architectures use 7/spl times/7 size image blocks and are prototyped for processing the CIF image sequence. The simulation and synthesis results show that the core speeds of the two proposed architectures are around 100 and 82 MHz, respectively.     

Radon变换和全变分相融合的图像复原算法

图像复原的核心是点扩散函数的估计和直接去卷积算法,针对拍照过程中,相机和被拍摄物体由于相对运动而导致的图像退化问题,提出一种基于Radon变换和全变分相融合的图像复原算法。首先利用radon变换对图像退化模型参数进行估计,然后采用全变分算法复原退化图像,最后在Matlab 2012平台进行仿真实验对算法的性能检验。仿真结果表明,相对于其它图像复原算法,本文算法可以准确估计退化模型参数,获得了更加理想的图像复原效果,具有一定的实际利用价值。     

基于Radon变换的多尺度虹膜特征提取算法

系统分析了基于虹膜特征的身份识别系统.针对典型预处理特点,设计了基于Radon变换的新特征提取算法.该算法在保持旋转、平移和尺度缩放不变性的同时,利用标准化方差加权的绝对距离,使识别准确度达到了93%.这种算法对于其它不规则图像的分析也具有启发意义.     

3-D vector radix algorithm for the 3-D new Mersenne numbertransform

Three-dimensional convolutions and correlations are used for three-dimensional image-processing applications. Their calculation involves extensive computation, which makes the use of fast transforms very advantageous. As the number of arithmetic operations is very large, the accumulation of rounding or truncation errors arising in the use of the fast Fourier and Hartley transforms tends to increase. Number theoretic transforms are calculated modulo an integer and hence they are not subject to these errors. Previously, a one-dimensional transform called the new Mersenne number transform (NMNT) was introduced and applied successfully to the calculation of 1-D convolutions/correlations. Unlike other Mersenne number transforms, the NMNT can handle long data sequences and has fast algorithms. In the paper, the 1-D definitions are first extended to the 3-D case in detail for use in 3-D image processing applications. The concept and derivation of the 3-D vector radix algorithm is then introduced for the fast calculation of the 3-D NMNT. The proposed algorithm is found to offer substantial savings over the row-column approach in terms of arithmetic operations. Examples are given showing the validity of both transform and algorithm     

Fast algorithm for the 3-D DCT-II

Recently, many applications for three-dimensional (3-D) image and video compression have been proposed using 3-D discrete cosine transforms (3-D DCTs). Among different types of DCTs, the type-II DCT (DCT-II) is the most used. In order to use the 3-D DCTs in practical applications, fast 3-D algorithms are essential. Therefore, in this paper, the 3-D vector-radix decimation-in-frequency (3-D VR DIF) algorithm that calculates the 3-D DCT-II directly is introduced. The mathematical analysis and the implementation of the developed algorithm are presented, showing that this algorithm possesses a regular structure, can be implemented in-place for efficient use of memory, and is faster than the conventional row-column-frame (RCF) approach. Furthermore, an application of 3-D video compression-based 3-D DCT-II is implemented using the 3-D new algorithm. This has led to a substantial speed improvement for 3-D DCT-II-based compression systems and proved the validity of the developed algorithm.     

An O(k3·log(n/k)) algorithm for theconsecutive-k-out-of-n:F system

The fastest generally-recognized algorithms for computing the reliability of consecutive-k-out-of-n:F systems require O(n) time, for both the linear and circular systems. The authors' new algorithm requires O(k³·log(n/k)) time. The algorithm can be extended to yield an O(n·max{k³·log(n/k), log(n))} total time procedure for solving the combinatorial problem of counting the number of working states, with w working and n-w failed components, w=1,2,...,n     

New searching flow scheme for incremental backprojection algorithm

A new two-dimensional (2D) searching flow scheme is proposed for the incremental backprojection algorithm (see IEEE Trans. Med. Imaging, vol.9, p.207, 1990). In this scheme, the searching direction in a beam is determined only by the distance of the current pixel to the corresponding ray and no pixels outside the beam are involved in the procedure. The proposed scheme possesses a simple structure. Implementations on an AST-386 computer for the incremental backprojection algorithm by using this new scheme show that the processing time can be reduced by a factor of approximately 1.4 compared with the original scheme.<>     

A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification

Recent advances in geopositioning mobile phones have made it possible for users to collect a large number of GPS trajectories by recording their location information. However, these mobile phones with built-in GPS devices usually record far more data than needed, which brings about both heavy data storage and a computationally expensive burden in the rendering process for a Web browser. To address this practical problem, we present a fast polygonal approximation algorithm in 2-D space for the GPS trajectory simplification under the so-called integral square synchronous distance error criterion in a linear time complexity. The underlying algorithm is designed and implemented using a bottom-up multiresolution method, where the input of polygonal approximation in the coarser resolution is the polygonal curve achieved in the finer resolution. For each resolution (map scale), priority-queue structure is exploited in graph construction to construct the initialized approximated curve. Once the polygonal curve is initialized, two fine-tune algorithms are employed in order to achieve the desirable quality level. Experimental results validated that the proposed algorithm is fast and achieves a better approximation result than the existing competitive methods.     

A fast algorithm for backprojection with linear interpolation

In the filtered backprojection procedure for image reconstruction from projections, backprojection dominates the computation time. A simple algorithm that reduces the number of multiplications in linear interpolation and backprojection stage by 50%, with a small increase in the number of additions, is proposed. The algorithm performs the interpolation and backprojection of four views together. Examples of implementation are given and extension to interpolation of more than four views is discussed.     

A 1 log N parallel algorithm for detecting convex hulls on imageboards

By finding the maximum and minimum of {y(i)-mx(i)|1=/相似文献   

A virtually nonblocking self-routing permutation network which routes packets in O(log2 N) time

Asymptotically nonblocking networks are O(log₂ N) depth self-routing permutation devices in which blocking probability vanishes when N (the number of network inputs) increases. This behavior does not guarantee, also for very large N, that all information always and simultaneously reaches its destination (and consequently that a whole permutation passes through the device) which is a requirement of the PRAM machine. In this work the conditions for which an asymptotically nonblocking network becomes asymptotically permutation nonblocking are studied, finally a virtually nonblocking device is obtained by a retransmission procedure which guarantees that all permutations always pass through this permutation device. This revised version was published online in June 2006 with corrections to the Cover Date.     

VOIR: a volumetric image reconstruction algorithm based on Fouriertechniques for inversion of the 3-D Radon transform

A novel volumetric image reconstruction algorithm known as VOIR is presented for inversion of the 3-D Radon transform or its radial derivative. The algorithm is a direct implementation of the projection slice theorem for plane integrals. It generalizes one of the most successful methods in 2-D Fourier image reconstruction involving concentric-square rasters to 3-D; in VOIR, the spectral data, which is calculated by fast Fourier techniques, lie on concentric cubes and are interpolated by a bilinear method on the sides of these concentric cubes. The algorithm has great computational advantages over filtered-backprojection algorithms; for images of side dimension N, the numerical complexity of VOIR is O(N(3) log N) instead of O(N (4)) for backprojection techniques. An evaluation of the image processing performance is reported by comparison of reconstructed images from simulated cone-beam scans of a contrast and resolution test object. The image processing performance is also characterized by an analysis of the edge response from the reconstructed images.     

NEW FAST ALGORITHM OF 2-D DISCRETE COSINE TRANSFORM

In this paper, a new algorithm for the fast computation of a 2-D discrete cosine transform (DCT) is presented. It is shown that the N×N DCT, where N = 2m, can be computed using only N 1-D DCT's and additions, instead of using 2N 1-D DCT's as in the conventional row-column approach. Hence the total number of multiplications for the proposed algorithm is only half of that required for the row-column approach, and is also less than that of most of other fast algorithms, while the number of additions is almost comparable to that of others.     

Markerless real-time 3-D target region tracking by motion backprojection from projection images

Accurate and fast localization of a predefined target region inside the patient is an important component of many image-guided therapy procedures. This problem is commonly solved by registration of intraoperative 2-D projection images to 3-D preoperative images. If the patient is not fixed during the intervention, the 2-D image acquisition is repeated several times during the procedure, and the registration problem can be cast instead as a 3-D tracking problem. To solve the 3-D problem, we propose in this paper to apply 2-D region tracking to first recover the components of the transformation that are in-plane to the projections. The 2-D motion estimates of all projections are backprojected into 3-D space, where they are then combined into a consistent estimate of the 3-D motion. We compare this method to intensity-based 2-D to 3-D registration and a combination of 2-D motion backprojection followed by a 2-D to 3-D registration stage. Using clinical data with a fiducial marker-based gold-standard transformation, we show that our method is capable of accurately tracking vertebral targets in 3-D from 2-D motion measured in X-ray projection images. Using a standard tracking algorithm (hyperplane tracking), tracking is achieved at video frame rates but fails relatively often (32% of all frames tracked with target registration error (TRE) better than 1.2 mm, 82% of all frames tracked with TRE better than 2.4 mm). With intensity-based 2-D to 2-D image registration using normalized mutual information (NMI) and pattern intensity (PI), accuracy and robustness are substantially improved. NMI tracked 82% of all frames in our data with TRE better than 1.2 mm and 96% of all frames with TRE better than 2.4 mm. This comes at the cost of a reduced frame rate, 1.7 s average processing time per frame and projection device. Results using PI were slightly more accurate, but required on average 5.4 s time per frame. These results are still substantially faster than 2-D to 3-D registration. We conclude that motion backprojection from 2-D motion tracking is an accurate and efficient method for tracking 3-D target motion, but tracking 2-D motion accurately and robustly remains a challenge.     

3-D discrete analytical ridgelet transform.

In this paper, we propose an implementation of the 3-D Ridgelet transform: the 3-D discrete analytical Ridgelet transform (3-D DART). This transform uses the Fourier strategy for the computation of the associated 3-D discrete Radon transform. The innovative step is the definition of a discrete 3-D transform with the discrete analytical geometry theory by the construction of 3-D discrete analytical lines in the Fourier domain. We propose two types of 3-D discrete lines: 3-D discrete radial lines going through the origin defined from their orthogonal projections and 3-D planes covered with 2-D discrete line segments. These discrete analytical lines have a parameter called arithmetical thickness, allowing us to define a 3-D DART adapted to a specific application. Indeed, the 3-D DART representation is not orthogonal, It is associated with a flexible redundancy factor. The 3-D DART has a very simple forward/inverse algorithm that provides an exact reconstruction without any iterative method. In order to illustrate the potentiality of this new discrete transform, we apply the 3-D DART and its extension to the Local-DART (with smooth windowing) to the denoising of 3-D image and color video. These experimental results show that the simple thresholding of the 3-D DART coefficients is efficient.