The Experts below are selected from a list of 14157 Experts worldwide ranked by ideXlab platform

Sarp Erturk - One of the best experts on this subject based on the ideXlab platform.

  • two Bit transform for binary block motion estimation
    IEEE Transactions on Circuits and Systems for Video Technology, 2005
    Co-Authors: Alp Erturk, Sarp Erturk
    Abstract:

    One-Bit transforms (1BTs) have been proposed for low-complexity block-based motion estimation by reducing the Representation order to a single Bit, and employing binary matching criteria. However, as a single Bit is used in the Representation of image frames, bad motion vectors are likely to be resolved in 1BT-based motion estimation algorithms particularly for small block sizes. It is proposed in this paper to utilize a two-Bit transform (2BT) for block-based motion estimation. Image frames are converted into two-Bit Representations by a simple block-by-block two Bit transform based on multithresholding with mean and linearly approximated standard deviation values. In order to avoid blocking effects at block boundaries during the block-by-block transformation while enabling the two-Bit Representation to be constructed according to local detail, threshold values are computed within a larger window surrounding the transforming block. The 2BT makes use of lower Bit-depth and binary matching criteria properties of 1BTs to achieve low-complexity block motion estimation. The 2BT improves motion estimation accuracy and seriously reduces the amount of bad motion vectors compared to 1BTs, particularly for small block sizes. It is shown that the proposed 2BT-based motion estimation technique improves motion estimation accuracy in terms of peak signal-to-noise ratio of reconstructed frames and also results in visually more accurate frames subsequent to motion compensation compared to the 1BT-based motion estimation approach.

Alp Erturk - One of the best experts on this subject based on the ideXlab platform.

  • two Bit transform for binary block motion estimation
    IEEE Transactions on Circuits and Systems for Video Technology, 2005
    Co-Authors: Alp Erturk, Sarp Erturk
    Abstract:

    One-Bit transforms (1BTs) have been proposed for low-complexity block-based motion estimation by reducing the Representation order to a single Bit, and employing binary matching criteria. However, as a single Bit is used in the Representation of image frames, bad motion vectors are likely to be resolved in 1BT-based motion estimation algorithms particularly for small block sizes. It is proposed in this paper to utilize a two-Bit transform (2BT) for block-based motion estimation. Image frames are converted into two-Bit Representations by a simple block-by-block two Bit transform based on multithresholding with mean and linearly approximated standard deviation values. In order to avoid blocking effects at block boundaries during the block-by-block transformation while enabling the two-Bit Representation to be constructed according to local detail, threshold values are computed within a larger window surrounding the transforming block. The 2BT makes use of lower Bit-depth and binary matching criteria properties of 1BTs to achieve low-complexity block motion estimation. The 2BT improves motion estimation accuracy and seriously reduces the amount of bad motion vectors compared to 1BTs, particularly for small block sizes. It is shown that the proposed 2BT-based motion estimation technique improves motion estimation accuracy in terms of peak signal-to-noise ratio of reconstructed frames and also results in visually more accurate frames subsequent to motion compensation compared to the 1BT-based motion estimation approach.

Wengfai Wong - One of the best experts on this subject based on the ideXlab platform.

  • A Family of Bit-Representation-Optimized Formats for Fast Sparse Matrix-Vector Multiplication on the GPU
    IEEE Transactions on Parallel and Distributed Systems, 2015
    Co-Authors: Wai Teng Tang, Stephen John Turner, Wen Jun Tan, Rick Siow Mong Goh, Wengfai Wong
    Abstract:

    Sparse matrix-vector multiplication (SpMV) is an important kernel that is used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness due to the low arithmetic intensity of the kernel. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of Bit-Representation-optimized (BRO) compression formats for representing sparse matrices on GPUs. The proposed formats – BRO-CSR, BRO-ELL and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through the reduction of memory traffic. We also propose two other hybrid BRO formats which can potentially perform better than both HYB and BRO-HYB formats. Experimental results demonstrate that compared to uncompressed CSR and ELLPACK formats, our proposed compressed BRO-CSR and BRO-ELL formats are able to achieve average speedups of 2 $\times$ and 1.4 $\times$ respectively. Furthermore, we demonstrate that by using BRO-ELL, the preconditioned conjugate gradient method is able to achieve an average speedup of 1.3 $\times$ over ELLPACK.

  • accelerating sparse matrix vector multiplication on gpus using Bit Representation optimized schemes
    IEEE International Conference on High Performance Computing Data and Analytics, 2013
    Co-Authors: Wai Teng Tang, Yi Wen Wong, Weiguang Chen, Stephen John Turner, Wengfai Wong
    Abstract:

    The sparse matrix-vector (SpMV) multiplication routine is an important building block used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of Bit-Representation-optimized (BRO) compression schemes for representing sparse matrices on GPUs. The proposed schemes, BRO-ELL, BRO-COO, and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through reduction of memory traffic. Furthermore, we formulate a BRO-aware matrix reordering scheme as a data clustering problem and use it to increase compression ratios. With the proposed schemes, experiments show that average speedups of 1.5x compared to ELLPACK and HYB can be achieved for SpMV on GPUs.

Gene Myers - One of the best experts on this subject based on the ideXlab platform.

  • a fast Bit vector algorithm for approximate string matching based on dynamic programming
    Journal of the ACM, 1999
    Co-Authors: Gene Myers
    Abstract:

    The approximate string matching problem is to find all locations at which a query of length m matches a substring of a text of length n with k -or-fewer differences. Simple and practical Bit-vector algorithms have been designed for this problem, most notably the one used in agrep . These algorithms compute a Bit Representation of the current state-set of the k -difference automaton for the query, and asymptotically run in either O ( nm/w ) or O ( nm log s/ w ) time where w is the word size of the machine (e.g., 32 or 64 in practice), and s is the size of the pattern alphabet. Here we present an algorithm of comparable simplicity that requires only O ( nm/w) time by virtue of computing a Bit Representation of the relocatable dynamic programming matrix for the problem. Thus, the algorithm's performance is independent of k , and it is found to be more efficient than the previous results for many choices of k and small m . Moreover, because the algorithm is not dependent on k , it can be used to rapidly compute blocks of the dynamic programming matrix as in the 4-Russians algorithm of Wu et al.(1996). This gives rise to an O(kn/w) expected-time algorithm for the case where m may be arBitrarily large. In practice this new algorithm, that computes a region of the dynamic progr amming (d.p.) matrx w entries at a time using the basic algorithm as a subroutine is significantly faster than our previous 4-Russians algorithm, that computes the same region 4 or 5 entries at a time using table lookup. This performance improvement yields a code that is either superior or competitive with all existing algorithms except for some filtration algorithms that are superior when k/m is sufficiently small.

  • a fast Bit vector algorithm for approximate string matching based on dynamic programming
    Combinatorial Pattern Matching, 1998
    Co-Authors: Gene Myers
    Abstract:

    The approximate string matching problem is to find all locations at which a query of length m matches a substring of a text of length n with k-or-fewer differences. Simple and practical Bit-vector algorithms have been designed for this problem, most notably the one used in agrep. These algorithms compute a Bit Representation of the current state-set of the k-difference automaton for the query, and asymptotically run in O(nmk/w) time where w is the word size of the machine (e.g. 32 or 64 in practice). Here we present an algorithm of comparable simplicity that requires only O(nm/w) time by virtue of computing a Bit Representation of the relocatable dynamic programming matrix for the problem. Thus the algorithm's performance is independent of k, and it is found to be more efficient than the previous results for many choices of k and small m.

Ling Wang - One of the best experts on this subject based on the ideXlab platform.

  • a hybrid quantum inspired genetic algorithm for multiobjective flow shop scheduling
    Systems Man and Cybernetics, 2007
    Co-Authors: Binbin Li, Ling Wang
    Abstract:

    This paper proposes a hybrid quantum-inspired genetic algorithm (HQGA) for the multiobjective flow shop scheduling problem (FSSP), which is a typical NP-hard combinatorial optimization problem with strong engineering backgrounds. On the one hand, a quantum-inspired GA (QGA) based on Q-Bit Representation is applied for exploration in the discrete 0-1 hyperspace by using the updating operator of quantum gate and genetic operators of Q-Bit. Moreover, random-key Representation is used to convert the Q-Bit Representation to job permutation for evaluating the objective values of the schedule solution. On the other hand, permutation-based GA (PGA) is applied for both performing exploration in permutation-based scheduling space and stressing exploitation for good schedule solutions. To evaluate solutions in multiobjective sense, a randomly weighted linear-sum function is used in QGA, and a nondominated sorting technique including classification of Pareto fronts and fitness assignment is applied in PGA with regard to both proximity and diversity of solutions. To maintain the diversity of the population, two trimming techniques for population are proposed. The proposed HQGA is tested based on some multiobjective FSSPs. Simulation results and comparisons based on several performance metrics demonstrate the effectiveness of the proposed HQGA