Sparse-sparse matrix multiplication (SpGEMM) is a well-studied problem on CPUs, GPUs, accelerators (e.g. FPGAs), and distributed systems. The main computational bottleneck in SpGEMM is the reduction process, which involves matching indices to accumulate partial products that map to the same output locations and requires irregular memory accesses. Efficient implementations must use the memory hierarchy effectively so that this reduction is done in fast local (cache) memory as much as possible. This is challenging, especially on GPUs, where the local memory is managed explicitly, as different rows of the result may have vastly different numbers of nonzero elements and vastly different numbers of partial products required to produce the output row which may not fit in the local memory. We demonstrate an SpGEMM implementation on GPUs which perfectly partitions the partial products into equal-size blocks such that each block maps to disjoint output locations. In this way, the block size can be chosen to maximize local memory, all reductions happen in local memory, and each block can be processed independently without communication or data from other blocks. We show how this partitioning can be achieved by solving many instances of a multiway merge partitioning problem. There are several algorithms in the literature for solving this problem. We present the mathematical formulation, missing from all papers providing algorithms for this problem, and show that this is a useful framework for parallelizing it efficiently for GPUs. To our knowledge, this partitioning scheme has never been applied to SpGEMM. We evaluate our SpGEMM implementation, MMSpGEMM, with respect to state-of-the-art implementations including cuSPARSE, TileSpGEMM, spECK, and AC-SpGEMM, achieving speedups of up to $5.3 x, 10.0 x, 1.3 x$, and $1.1 x$, respectively, on a select set of 20 SuiteSparse matrices, and much higher on synthetic matrix multiplications with different left and right matrices. Finally, we discuss improvements and limitations and suggest ways to incorporate the idea into more general SpGEMM routines.

Abstract. Image vectorization converts raster images into vector graphics composed of regions separated by curves. Typical vectorization methods first define the regions by grouping similar colored regions by color quantization, then approximate their boundaries by Bézier curves. In that way, the raster input is converted into an SVG format parameterizing the regions’ colors and the Bézier control points. This compact representation has many graphical applications thanks to its universality and resolution-independence. In this paper, we remark that image vectorization is nothing but an image segmentation, and that it can be built by fine to coarse region merging. Our analysis of the problem leads us to propose a vectorization method that alternates region merging and curve smoothing. We formalize the method by alternate operations on the dual and primal graph induced by any domain partition. In that way, we address a limitation of current vectorization methods, which separate the update of regional information from curve approximation. We formalize region merging methods by associating them with various gain functionals, including the classic Beaulieu–Goldberg and Mumford–Shah functionals. More generally, we introduce and compare region merging criteria that involve the number of regions, the scale, the area, and the internal standard deviation of each region. We also show that the curve smoothing, implicit in all vectorization methods, can be performed by the shape-preserving affine scale-space. We extend this flow to a network of curves and give a sufficient condition for the topological preservation of the segmentation. The general vectorization method that follows from this analysis shows explainable behaviors, explicitly controlled by a few intuitive parameters. It is experimentally compared to state-of-the-art software and proved to have comparable or superior fidelity and cost efficiency.

Abstract. Image vectorization is a process to convert a raster image into a scalable vector graphic format. The objective is to effectively remove pixelization effects while representing image boundaries by scalable parameterized curves. We propose a new image vectorization method which considers depth ordering among shapes and use curvature-based inpainting for convexifying shapes in the vectorization process. From a given color-quantized raster image, we first define each connected component of the same color as a shape layer and construct depth ordering among them using a newly proposed depth ordering energy. Global depth ordering among all shapes is described by a directed graph, and we propose an energy to remove cycles within the graph. After constructing a depth ordering of shapes, we convexify occluded regions by Euler’s elastica curvature-based variational inpainting and leverage the stability of Modica–Mortola double-well potential energy to inpaint large regions. This is following human vision perception, where boundaries of shapes extend smoothly, and we assume that shapes are likely to be convex. Finally, we fit Bézier curves to the boundaries and store vectorization results as a scalable vector graphics file, allowing superposition of curvature-based inpainted shapes following the depth ordering. This is a new way to vectorize images by decomposing an image into scalable shape layers with computed depth ordering. This approach makes editing shapes and images more natural and intuitive. We also consider grouping shape layers for semantic vectorization. We present various numerical results and comparisons against recent layer-based vectorization methods to validate the proposed model.

We propose a novel variational image vectorization algorithm (VIVA) which alternatively smooths contours by affine shortening flow and eliminates spurious regions by minimizing a Mumford-Shah-type functional. We introduce dual-primal graphs representing domain partitions which allows for effective iterative computation. The method provides varying levels of simplicity on the topology of the resulted vector graphics while effectively removing pixelization. It compares favorably to the state-of-the-art (SOTA) vectorization methods.

We propose a new deterministic methodology to predict the secondary structure of RNA sequences. What information of stem is important for structure prediction, and is it enough ? The proposed simple deterministic algorithm uses minimum stem length, Stem-Loop score, and co-existence of stems, to give good structure predictions for short RNA and tRNA sequences. The main idea is to consider all possible stem with certain stem loop energy and strength to predict RNA secondary structure. We use graph notation, where stems are represented as vertexes, and co-existence between stems as edges. This full Stem-graph presents all possible folding structure, and we pick sub-graph(s) which give the best matching energy for structure prediction. Stem-Loop score adds structure information and speeds up the computation. The proposed method can predict secondary structure even with pseudo knots. One of the strengths of this approach is the simplicity and flexibility of the algorithm, and it gives a deterministic answer. Numerical experiments are done on various sequences from Protein Data Bank and the Gutell Lab using a laptop and results take only a few seconds.

We propose a novel algorithm for converting quantized raster color images to resolution-independent scalable vector graphics (SVG). Starting from the discontinuity set of the input image, the algorithm connects the pieces of curves separating two constant regions to reconstruct the apparent contours of objects and interpret T-junctions and saddle points. This structure is depixelized by curve affine shortening, which requires maintaining the topology of the discontinuity set during filtering. The resulting Hierarchical Curve-based Vectorization (HCV) algorithm compares favorably to several state-of-art vectorization algorithms and software for color-quantized photos and pixel art1.

Binary shapes, or silhouettes, are essential in human communication. They include, for example, all fonts and many logos. They can be extracted from images in raster form but require a vectorization for resolution independent editing. In this paper, we propose a mathematically founded silhouette vectorization algorithm, which converts a raster 2D shape to a Scalable Vector Graphics (SVG) format whose control points are geometrically stable under affine transformations. The proposed method can also be used as a reliable feature point detector for silhouettes. Compared to state-of-the-art graphics software, our algorithm shows a superior reduction in the number of control points for an equal or better accuracy.

We propose a nonconvex variational decomposition model which separates a given image into piecewise-constant, smooth, and oscillatory components. This decomposition is motivated not only by image denoising and structure separation, but also by shadow and spot light removal. The proposed model clearly separates the piecewise-constant structure and smoothly varying harmonic part, thanks to having a separated oscillatory component. The piecewise-constant part is captured by TV-like nonconvex regularization, harmonic term via second-order regularization, and oscillatory (noise and texture) term via a $H^{-1}$-norm penalty. There are interesting interactions between these three regularization terms. We explore the effects of each regularization and the choice of parameters carefully. We propose an efficient alternating direction method of multipliers based minimization for fast numerical computation of the optimization problem. Various experiments are presented to show the robustness against a high level of noise, applications to soft spotlight and shadow removal, and the comparisons with other methods.

We propose a variational functional with a curvature constraint to reconstruct implicit surfaces from point cloud data. In the point cloud data, only locations are assumed to be given, without any normal direction or any curvature estimation. The minimizing functional balances two terms: the distance function from the point cloud to the surface and the mean curvature of the surface itself. We explore both the $L_1$ and $L_2$ norms for the curvature constraint. With the added curvature constraint, the computation becomes particularly challenging. We propose two efficient algorithms. The first algorithm is a novel operator splitting method. It replaces the original high-order PDEs by a decoupled PDE system, which is solved by a semi-implicit method. We also discuss an approach based on an augmented Lagrangian method. The proposed model shows robustness against noise and recovers concave features and corners better compared to models without curvature constraint. Numerical experiments on two- and three-dimensional data sets, noisy data and sparse data, are presented to validate the model. Experiments show that the operator splitting semi-implicit method is flexible and robust.

Motivated by the problems of lattice mixture identification and grain irregularity detection, we present a framework for lattice pattern representation and comparison and propose an efficient algorithm for lattice separation. We define new scale and shape descriptors, which considerably reduce the size of equivalence classes of lattice bases. These finite number of equivalence relations are fully characterized by the modular group theory. We construct the lattice space $\mathscr{L}$ based on the equivalent descriptors and define a metric $d_{\mathscr{L}}$ to accurately quantify the visual similarities and differences between lattices. We introduce the lattice identification and separation algorithm (LISA), which identifies individual lattice patterns from superposed lattices. LISA finds lattice candidates from the high responses in the image spectrum, then extracts different layers of lattice patterns one by one. By analyzing the frequency components, we explore the intricate dependency of LISA's performances on particle radius, lattice density, and relative translations. Various numerical experiments are presented to show LISA's robustness against a large number of lattice layers, moiré patterns, and missing particles.

This paper proposes two numerical algorithms for solving Euler's elastica-based inpainting model. The minimizing functional is nonsmooth and nonconvex and involves high-order derivatives, that traditional gradient descent based methods converge very slowly. Recent alternating minimization methods show fast convergence when a good choice of parameters is used. The objective of this paper is to introduce efficient algorithms which have simple structures with fewer parameters. These methods are based on operator splitting and alternating direction method of multipliers, and subproblems can be solved efficiently by Fourier transforms and shrinkage operators. For the first method, we relax the normal vector in the curvature term of the Euler's elastica model and exploit two operator splitting techniques to propose a Relaxed Normal Two Split (RN2Split) method. The second method, $\kappa$-weighted Total Variation ($\kappa$TV), solves the Euler's elastica minimization problem as a weighted total variation. We present the analytical properties of each algorithm. Various numerical experiments, including comparison with some existing state-of-the-art algorithms, are presented to show the efficiency and the effectiveness of the proposed RN2Split and $\kappa$TV methods.

We propose a novel method for constructing illusory foreground and background shapes from convex corners. We first introduce a new class of visual cues called corner bases, which expands zero-dimensional corner points to two-dimensional microstructures. These corner bases are then fused together by the functionalized elastica energy imposed upon an admissible phase field. The optimal phase field segments the visual field into disjoint connected components, which are further fused via a simple connectivity principle to construct both foreground illusory shapes and background occluded shapes. Robust and efficient numerical schemes are developed, and several generic examples are presented. Cognitive implications are highlighted.

Variational models have been studied for image segmentation application since the Mumford-Shah functional was introduced in the late 1980s. In this paper, we focus on multiphase segmentation with a new regularization term that yields an unsupervised segmentation model. We propose a functional that automatically chooses a favorable number of phases as it segments the image. The primary driving force of the segmentation is the intensity fitting term while a phase scale measure complements the regularization term. We propose a fast, yet simple, brute-force numerical algorithm and present experimental results showing the robustness and stability of the proposed model.

Colorization refers to an image processing task which recovers color in grayscale images when only small regions with color are given. We propose a couple of variational models using chromaticity color components to colorize black and white images. We first consider total variation minimizing (TV) colorization which is an extension from TV inpainting to color using chromaticity model. Second, we further modify our model to weighted harmonic maps for colorization. This model adds edge information from the brightness data, while it reconstructs smooth color values for each homogeneous region. We introduce penalized versions of the variational models, we analyze their convergence properties, and we present numerical results including extension to texture colorization.