The first generation of transitive stereo-metric satellites in China, TH-1 Satellite, is able to gain stereo images of three-line-array with resolution of 5 meters, multispectral images of 10 meters, and panchromatic ...
详细信息
ISBN:
(纸本)9781628411768
The first generation of transitive stereo-metric satellites in China, TH-1 Satellite, is able to gain stereo images of three-line-array with resolution of 5 meters, multispectral images of 10 meters, and panchromatic high resolution images of 2 meters. The procedure between level 0 and level 1A of high resolution images is so called relative radiometric correction (RRC for short). The processing algorithm of high resolution images, with large volumes of data, is complicated and time consuming. In order to bring up the processing speed, people in industry commonly apply parallel processing techniques based on CPU or GPU. This article firstly introduces the whole process and each step of the algorithm - that is in application - of RRC for high resolution images in level 0;secondly, the theory and characteristics of MPI (Message Passing Interface) and OpenMP (Open Multi-Processing) parallel programming techniques is briefly described, as well as the superiority for parallel technique in image processing field;thirdly, aiming at each step of the algorithm in application and based on MPI+OpenMP hybrid paradigm, the parallelizability and the strategies of parallelism for three processing steps: Radiometric Correction, Splicing Pieces of TDICCD (Time Delay Integration Charge-Coupled Device) and Gray Level Adjustment among pieces of TDICCD are deeply discussed, and furthermore, deducts the theoretical acceleration rates of each step and the one of whole procedure, according to the processing styles and independence of calculation;for the step Splicing Pieces of TDICCD, two different strategies of parallelism are proposed, which are to be chosen with consideration of hardware capabilities;finally, series of experiments are carried out to verify the parallel algorithms by applying 2-meter panchromatic high resolution images of TH-1 Satellite, and the experimental results are analyzed. Strictly on the basis of former parallel algorithms, the programs in the experiments are wri
An outlier is an observation that deviates so much front other observations as to arouse suspicion that it was generated by a different mechanism. Outlier detection has many applications, such as data cleaning, fraud ...
详细信息
ISBN:
(纸本)0769522785
An outlier is an observation that deviates so much front other observations as to arouse suspicion that it was generated by a different mechanism. Outlier detection has many applications, such as data cleaning, fraud detection and network intrusion. The existence of outliers can indicate individuals or groups that exhibit a behavior that is very different from most of the individuals of the dataset. In this paper we design two parallel algorithms, the first one is for finding out distance-based outliers based on nested loops along with randomization and the use of a pruning rule. The second parallel algorithin is for detecting density-based local outliers. In both cases data parallelism is used. We show that both algorithms reach near linear speedup. Our algorithms are tested on four real-world datasets coining front the Machine Learning Database Repository at the UCI.
We describe the parallelization of an efficient algorithm for balanced truncation that allows to reduce models with state-space dimension up to 0 (105). The major computational task in this approach is the solution of...
详细信息
ISBN:
(纸本)3540290672
We describe the parallelization of an efficient algorithm for balanced truncation that allows to reduce models with state-space dimension up to 0 (105). The major computational task in this approach is the solution of two largescale sparse Lyapunov equations, performed via a coupled LR-ADI iteration with (super-)linear convergence. Experimental results on a cluster of Intel Xeon processors illustrate the efficacy of our parallel model reduction algorithm.
The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive ...
详细信息
ISBN:
(纸本)0769512577;0769512585
The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive a number of efficient algorithms and embeddings for super-IPGs, proving their versatility. We show that a multitude of important networks can also be emulated in super-IPGs with optimal slowdown. Also, the intercluster diameter, average intercluster distance, and bisection bandwidth of suitably constructed super-IPGs are optimal within small constant factors. Finally, we show that when parallel computers, built as multiple chip-multiprocessors (MCMP), are based on super-IPGs, they can significantly outperform those based on hypercubes, k-ary n-cubes, and other networks in carrying out communication-intensive tasks.
We propose parallel algorithms for detecting collisions among 3-D objects in real-time. First, a basic algorithm of serial version is described. It can detect potential collisions among multiple objects with arbitrary...
详细信息
ISBN:
(纸本)078032904X
We propose parallel algorithms for detecting collisions among 3-D objects in real-time. First, a basic algorithm of serial version is described. It can detect potential collisions among multiple objects with arbitrary motion (translation and rotation) in three-dimensional (3-D) space. The algorithm can be used without modification for both convex and concave objects represented as polyhedra. This algorithm is efficient, simple to implement, and does not require any memory intensive auxiliary data structure to be precomputed and updated. Then, two parallel algorithms are proposed for MIMD multi-processors having a shared-memory;one uses a static and the other uses a dynamic method for proper load balancing. Experimental results demonstrate the performance of the proposed collision detection methods.
We consider the problem of finding the kth highest element in a totally ordered set of n elements (SELECT), and partitioning a totally ordered set into the top k and bottom n-k elements (PARTITION) using pairwise comp...
详细信息
ISBN:
(纸本)9781450341325
We consider the problem of finding the kth highest element in a totally ordered set of n elements (SELECT), and partitioning a totally ordered set into the top k and bottom n-k elements (PARTITION) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability 1-gamma), and noisy (where comparisons are correct with probability 1/2 + gamma/2 and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.
One of the many ways of solving free-boundary problems is, when possible, to put them (perhaps after suitable transformations) in the framework of variational or quasi-variational inequalities. It then remains to solv...
详细信息
Power-List, ParList and PList data structures are efficient tools for functional descriptions of parallel programs that are divide & conquer in nature. The goal of this work is to develop three parallel variants f...
详细信息
ISBN:
(纸本)3540440496
Power-List, ParList and PList data structures are efficient tools for functional descriptions of parallel programs that are divide & conquer in nature. The goal of this work is to develop three parallel variants for Fast Fourier Transformation using these theories. The variants are implied by the degree of the polynomial, which can be a power of two, a prime number, or a product of prime factors. The last variant includes the first two, and represents a general and efficient parallel algorithm for Fast Fourier Transformation. This general algorithm has a very good time complexity, and can be mapped on a recursive interconnection network.
In this paper, we design massively parallel algorithms for sparse matrix multiplication, as well as more general join-aggregate queries, where the join hypergraph is a tree with arbitrary output attributes. For each c...
详细信息
ISBN:
(纸本)9781450371087
In this paper, we design massively parallel algorithms for sparse matrix multiplication, as well as more general join-aggregate queries, where the join hypergraph is a tree with arbitrary output attributes. For each case, we obtain asymptotic improvement over existing algorithms. In particular, our matrix multiplication algorithm is shown to be optimal in the semiring model.
暂无评论