Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph has no cycles of odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map simply to ones in a similarity-transformed positive graph Laplacian, thus enabling reuse of well-studied spectral filters designed for positive graphs. We propose a fast method to learn a balanced signed graph Laplacian directly from data. Specifically, for each node i, to determine its polarity βi∈{−1,1} and edge weights $\left\{ {{w_{i,j}}} \right\}_{j = 1}^N$, we extend a sparse inverse covariance formulation based on linear programming (LP) called CLIME, by adding linear constraints to enforce "consistent" signs of edge weights $\left\{ {{w_{i,j}}} \right\}_{j = 1}^N$ with the polarities of connected nodes—i.e., positive/negative edges connect nodes of same/opposing polarities. For each LP, we adopt projections on convex set (POCS) to determine a suitable CLIME parameter ρ > 0 that guarantees LP feasibility. We solve the resulting LP via an off-the-shelf LP solver. Experiments on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables the use of spectral filters and graph neural networks designed for positive graphs on balanced signed graphs.

In this paper, we propose a method, based on graph signal processing, to optimize the choice of k in k-nearest neighbor graphs (kNNGs). kNN is one of the most popular approaches and is widely used in machine learning and signal processing. The parameter k represents the number of neighbors that are connected to the target node; however, its appropriate selection is still a challenging problem. Therefore, most kNNGs use ad hoc selection methods for k. In the proposed method, we assume that a different k can be chosen for each node. We formulate a discrete optimization problem to seek the best k with a constraint on the sum of distances of the connected nodes. The optimal k values are efficiently obtained without solving a complex optimization. Furthermore, we reveal that the proposed method is closely related to existing graph learning methods. In experiments on real datasets, we demonstrate that the kNNGs obtained with our method are sparse and can determine an appropriate variable number of edges per node. We validate the effectiveness of the proposed method for point cloud denoising, comparing our denoising performance with achievable graph construction methods that can be scaled to typical point cloud sizes (e.g., thousands of nodes).

This paper proposes a compression framework for adjacency matrices of weighted graphs based on graph filter banks. Adjacency matrices are widely used mathematical representations of graphs and are used in various applications in signal processing, machine learning, and data mining. In many problems of interest, these adjacency matrices can be large, so efficient compression methods are crucial. In this paper, we propose a lossy compression of weighted adjacency matrices, where the binary adjacency information is encoded losslessly (so the topological information of the graph is preserved) while the edge weights are compressed lossily. For the edge weight compression, the target graph is converted into a line graph, whose nodes correspond to the edges of the original graph, and where the original edge weights are regarded as a graph signal on the line graph. We then transform the edge weights on the line graph with a graph filter bank for sparse representation. Experiments on synthetic data validate the effectiveness of the proposed method by comparing it with existing lossy matrix compression methods.

An image denoiser can be used for a wide range of restoration problems via the Plug-and-Play (PnP) architecture. In this paper, we propose a general framework to build an interpretable graph-based deep denoiser (GDD) by unrolling a solution to a maximum a posteriori (MAP) problem equipped with a graph Laplacian regularizer (GLR) as signal prior. Leveraging a recent theorem showing that any (pseudo-)linear denoiser $\boldsymbol{\Psi}$, under mild conditions, can be mapped to a solution of a MAP denoising problem regularized using GLR, we first initialize a graph Laplacian matrix $\mathbf{L}$ via truncated Taylor Series Expansion (TSE) of $\Psi^{-1}$. Then, we compute the MAP linear system solution by unrolling iterations of the conjugate gradient (CG) algorithm into a sequence of neural layers as a feed-forward network—one that is amenable to parameter tuning. The resulting GDD network is “graph-interpretable”, low in parameter count, and easy to initialize thanks to $\mathbf{L}$ derived from a known well-performing denoiser $\boldsymbol{\Psi}$. Experimental results show that GDD achieves competitive image denoising performance compared to competitors, but employing far fewer parameters, and is more robust to covariate shift.

Neuromorphic cameras, also known as event-based cameras, can detect changes in the environmental brightness asynchronously and independently for each pixel. They output the changes, i.e., events, as 3-D (2-D pixel coordinates + time) streaming data. While event-based cameras are used in many applications because of their desirable characteristics, e.g., high temporal resolution, low latency, low power consumption, and high dynamic range, their measurements contain considerable noise due to their high sensitivity. In this paper, we propose a simple yet effective denoising method for event-based cameras based on graph spectral features. We utilize the fact that the real events captured are often densely distributed in the streaming data while the noise events are spatiotemporally sparse. In the proposed method, we first construct a graph where nodes represent events and edges represent the spatiotemporal distance between the events. Next, we calculate the Fiedler vector, which is the eigenvector of the graph operator associated with the second smallest eigenvalue. The obtained Fiedler vector is used for extracting real events directly. In the calculation of the Fiedler vector, we leverage a power method instead of the naive eigenvalue decomposition and thereby reduce its computational complexity. In experiments, we demonstrate that the proposed method effectively removes noise events from the raw events compared to alternative methods.

In this paper, we propose a restoration method of time-varying graph signals, i.e., signals on a graph whose signal values change over time, using deep algorithm unrolling. Deep algorithm unrolling is a method that learns parameters in an iterative optimization algorithm with deep learning techniques. It is expected to improve convergence speed and accuracy while the iterative steps are still interpretable. In the proposed method, the minimization problem is formulated so that the time-varying graph signal is smooth both in time and spatial domains. The internal parameters, i.e., time domain FIR filters and regularization parameters, are learned from training data. Experimental results using synthetic data and real sea surface temperature data show that the proposed method improves signal reconstruction accuracy compared to several existing time-varying graph signal re- construction methods.

This study proposes a filtering method for directed graph (digraph) signals. In order to realize digraph filtering, a novel graph Fourier transform (GFT), – Augmented GFT (AuGFT) –, is proposed by defining an Hermitian adjacency matrix. Although there has been the same method to give the adjacency matrix of digraphs, this study defines a novel digraph Laplacian. The existing digraph Laplacian does not give the graph signal variation considering the edge directions, while the novel one does. This paper introduces three important ideas. The first is the definition of a novel degree matrix to give the novel digraph Laplacian. The second is to decompose the symmetric and skew-symmetric components of the novel digraph Laplacian independently into their spectral components. The third is, based on the decomposition, to augment the conventional GFT for digraphs as an invertible real-valued dictionary. The new GFT is shown to provide a practical form of real-valued digraph filtering. The significance of the proposed method is verified through simulations of signal filtering on digraphs.

We propose a simultaneous method of multimodal graph signal denoising and graph learning. Since sensor networks distributed in space can capture multiple modalities of data, referred to as modalities, they are assumed to have an underlying structure or correlations both in space and modality. Such multimodal data are regarded as graph signals on a twofold graph. Like regular signals, multimodal graph signals can be corrupted by noise during their sensing process. Furthermore, their spatial/modality relationships are not given a priori: We need to estimate twofold graphs during denoising. In this paper, we propose a signal denoising method on twofold graphs where graphs are learned simultaneously. Specifically, we formulate an optimization problem for that, and an iterative algorithm for solving it is unrolled with deep algorithm unrolling (DAU). In the proposed method, the parameters in iterations are learned from training data that results in faster convergence and denoising quality improvements. Experimental results demonstrate that the proposed method outperforms existing graph signal denoising methods.

We propose a sampling set selection method for graph signals under arbitrary signal priors. Most approaches of graph signal sampling assume that signals are bandlimited. However, in practical situations, there exist many full-band graph signals like piecewise smooth/constant signals. Our sampling set selection method allows for arbitrary graph signal models as long as they are linear. This can be derived from a generalized sampling framework. In contrast to existing works, we focus on the direct sum condition between sampling and reconstruction subspaces where the direct sum condition plays a key role for the best possible recovery of sampled signals. We also design a fast sampling set selection algorithm based on the proposed method with the Neumann series approximation. In sampling and recovery experiments, we validate the effectiveness of the proposed method for several graph signal models.

We propose a denoising method of multimodal graph signals with twofold smoothness regularization. Graph signal processing assumes that a signal has an underlying structure that is represented by a graph. In each node of the graph, we often have multimodal data or features that are correlated across modalities. Since these multimodal data are measured by various sensors, the observed data will be noisy. In this paper, we assume that a multimodal signal is smooth on two underlying graphs: One is a spatial graph (i.e., relationship among nodes) and the other is a modality graph (i.e., relationship among modalities). We formulate a regularized minimization problem based on smoothness on the twofold graphs. The problem is solved with an alternating minimization scheme. To avoid a hand-crafted parameter tuning that is usually costly and converges to local minima, we utilize deep algorithm unrolling (DAU) to train the parameters in the algorithm. To validate the proposed method, we conduct experiments on synthetic data and demonstrate that our method outperforms various existing graph signal denoising methods.

In this paper, we propose a parameter selection method for graph learning. Graph learning, a technique of learning graphs from observations, is required in many applications, e.g., classification, prediction, and clustering. However, there is no established method to determine hyperparameters that control the strength of the regularization reflecting prior knowledge. To resolve the problem, we consider a model selection criterion for the graph learning problem based on Laplacian constrained Gaussian Markov random field. The proposed criterion is the value based on model evidence, which is used for model selection in Bayesian statistics. It can be estimated by averaging the negative log-likelihood over the posterior distribution of a graph learning model. To compute this criterion, we present an efficient sampler of the posterior distribution. In the experiment with random graphs, we demonstrate that the proposed method can select hyperparameters having a good trade-off between F-measure and relative error.

Finding important edges in a graph is a crucial problem for various research fields such as network epidemics, signal processing, machine learning, and sensor networks. In this paper, we tackle the problem based on sampling theory on graphs. We convert the original graph to a line graph where its nodes and edges, respectively, represent the original edges and the connections between the edges. We then perform node sampling of the line graph based on the edge smoothness assumption: This process selects the most important edges in the original graph. We present a general framework of edge sampling based on graph sampling theory and we also reveal a theoretical relationship between the original and line graphs. Experimental results in synthetic graphs validate the effectiveness of our approach against some alternative edge selection methods.

This letter proposes a fast implementation of the regularity-constrained discrete sine transform (R-DST). The original DSTleaksthe lowest frequency (DC: direct current) components of signals into high frequency (AC: alternating current) subbands. This property is not desired in many applications, particularly image processing, since most of the frequency components in natural images concentrate in DC subband. The characteristic of filter banks whereby they do not leak DC components into the AC subbands is calledregularity. While an R-DST has been proposed, it has no fast implementation because of the singular value decomposition (SVD) in its internal algorithm. In contrast, the proposed regularity-constrained fast sine transform (R-FST) is obtained by just appending a regularity constraint matrix as a postprocessing of the original DST. When the DST size is$M\times M$($M=2^\ell$,$\ell \in \mathbb {N}_{\geq 1}$), the regularity constraint matrix is constructed from only$M/2-1$rotation matrices with the angles derived from the output of the DST for the constant-valued signal (i.e., the DC signal). Since it does not require SVD, the computation is simpler and faster than the R-DST while keeping all of its beneficial properties. An image processing example shows that the R-FST has fine frequency selectivity with no DC leakage and higher coding gain than the original DST. Also, in the case of$M=8$, the R-FST saved approximately$0.126$seconds in a 2-D transformation of$512\times 512$signals compared with the R-DST because of fewer extra operations.

We propose a design method of sampling matrices for graph signals that guarantees perfect recovery for arbitrary graph signal subspaces. When the signal subspace is known, perfect reconstruction is always possible from the samples with an appropriately designed sampling matrix. However, most graph signal sampling methods so far design sampling matrices based on the bandlimited assumption and sometimes violates the perfect reconstruction condition for the other signal models. In this paper, we formulate an optimization problem for the design of the sampling matrix that guarantees perfect recovery, thanks to a generalized sampling framework for standard signals. In experiments with various signal models, our sampling matrix presents better reconstruction accuracy both for noiseless and noisy situations.

In this paper, we propose a deep algorithm unrolling (DAU) based on a variant of the alternating direction method of multiplier (ADMM) called Plug-and-Play ADMM (PnP-ADMM) for denoising of signals on graphs. DAU is a trainable deep architecture realized by unrolling iterations of an existing optimization algorithm which contains trainable parameters at each layer. We also propose a nested-structured DAU: Its submodules in the unrolled iterations are also designed by DAU. Several experiments for graph signal denoising are performed on synthetic signals on a community graph and U.S. temperature data to validate the proposed approach. Our proposed method outperforms alternative optimization- and deep learning-based approaches.

In this paper, we propose structural features for spatial graph convolution to classify signals on graphs. Existing graph convolution methods are limited to utilize the structural information of surrounding neighboring nodes for a target node in feature space. Graph convolution performances will be improved if it can fully utilize the structural information. To achieve this goal, we first define three structural features for characterizing the structure of surrounding neighboring nodes, i.e., feature angle, feature distance, and relationship embedding. We then concatenate the features and perform graph convolution by aggregating and integrating them. We use this graph convolution algorithm for the basis of graph neural networks for classification of 3D point clouds and nodes in a citation network. Through experiments, our approach presents higher classification accuracies than existing methods.

We consider generalized sampling for stochastic graph signals. The generalized graph sampling framework allows recovery of graph signals beyond the bandlimited setting by placing a correction filter between the sampling and reconstruction operators and assuming an appropriate prior. In this paper, we assume the graph signals are modeled by graph wide sense stationarity (GWSS), which is an extension of WSS for standard time domain signals. Furthermore, sampling is performed in the graph frequency domain along with the assumption that the graph signals lie in a periodic graph spectrum subspace. The correction filter is designed by minimizing the mean-squared error (MSE). The graph spectral response of the correction filter parallels that in generalized sampling for WSS signals. The effectiveness of our approach is validated via experiments by comparing the MSE with existing approaches.

We propose ScalpNet: A deep neural network to detect spatiotemporal abnormal intervals from EEGs of epilepsy patients. Since the number of trained clinicians is very limited, it is very crucial to establish automatic detection of abnormal signals caused by epilepsy from EEGs. We build a convolutional neural network detecting spatiotemporal intervals that will be abnormal based on the fact that peaky EEG signals can be observed not only in the electrode close to the focal region but those in the surrounding regions. In the experiments with a real dataset, our proposed ScalpNet presents higher classification accuracy than existing machine learning methods, including a convolutional neural network performed by channel-by-channel.

We propose a method for graph learning from spatiotemporal measurements. We aim at inferring time-varying graphs under the assumption that changes in graph topology and weights are sparse in time. The problem is formulated as a convex optimization problem to impose a constraint on the temporal relation of the time-varying graph. Experimental results with synthetic data show the effectiveness of our proposed method.

Signals defined on a network or a graph are often prone to errors due to missing data and noise. In order to restore the graph signal, interpolation and denoising are two necessary steps along with other graph signal processing procedures. However, existing graph signal interpolation and denoising methods are largely decoupled due to the opposite objectives of the two tasks and the inherent high computational complexity. The goal of this paper is to integrate graph interpolation and denoising using the Plug-and-Play (PnP) ADMM, a recently developed technique in image processing. When using the subsampling process as the forward model and graph filter as the denoiser, we show that PnP ADMM is equivalent to interpolating a bandlimited signal. Preliminary results are demonstrated via experiments, where the proposed method shows significantly better performance over existing methods.

This paper proposes a method to generate synthesized underwater images from clean RGB-D images taken on the ground. It is beneficial for training a deep neural network for underwater image restoration (UWIR), and also for measuring the performances among UWIR methods. The underwater images are synthesized on the modeling of an accurate degradation process with the consideration of absorption and scattering as well as ten water types. The water types result in different attenuation coefficients, i.e., different synthesized images. In the experimental results, it is validated that our method successfully synthesizes underwater images, and presents a state-of-the-art performance for UWIR by utilizing our synthesized images for the training of deep learning-based UWIR.

This letter proposes a class of$M$-channel spectral graph filter banks with a symmetric structure, that is, the transform has sampling operations and spectral graph filters on both the analysis and synthesis sides. The filter banks achieve maximum decimation, perfect recovery, and orthogonality. The proposed transform uses sampling in the graph frequency domain. This enables us to use any variation operators and apply the transforms to arbitrary graphs even when the filter banks have symmetric structures. We clarify the perfect reconstruction conditions and show design examples. An experiment on graph signal denoising conducted to examine the performance of the proposed filter bank is described.

This paper presents a framework for perfect reconstruction two-channel critically-sampled graph filter banks with spectral domain sampling. Graph signals have a unique characteristic: sampling in the vertex and graph spectral domains are generally different, in contrast to classical signal processing. Conventional graph filter banks are designed using vertex domain sampling, whereas the proposed approach utilizes a novel spectral domain sampling. Our proposed technique leads to perfect reconstruction transforms for any type of undirected graphs and can be applied both to combinatorial and symmetric normalized graph Laplacians. Some filter bank designs and an experiment on nonlinear approximation are shown to validate their effectiveness.

This paper proposes a new color model of videos, Dynamic Color Lines, as an extension of Color Lines Model for images. With our model, videos are assumed to be represented as dynamically moving elongated clusters in a 3-D RGB space. This can be done by assigning each pixel to the nearest cluster and by updating cluster directions and locations alternatively. The dynamic color lines model provides a heuristic approach for a new sparse and robust representation of videos. In numerical experiments, segmentation of surveillance videos and compression are performed.

We propose a novel sampling method of graph signals that simulta- neously inherits the characteristics of the sampled signals in the vertex and graph frequency domains. In the conventional sampling of graph signals, the sampled signal can retain the characteristics only in one (vertex or graph frequency) domain, but it is not suitable for another domain. The proposed method forms an optimization prob- lem to design appropriate sampling matrices in the graph frequency domain for inheriting the characteristics of the sampled signals in the vertex domain. We perform downsampling of graph signals based on the proposed approach and apply it to denoising with graph Laplacian pyramid along with the comparison to the existing methods.

Recent advent of graph signal processing (GSP) has spurred intensive studies of signals that live naturally on irregular data kernels described by graphs (e.g., social networks, wireless sensor networks). Though a digital image contains pixels that reside on a regularly sampled 2-D grid, if one can design an appropriate underlying graph connecting pixels with weights that reflect the image structure, then one can interpret the image (or image patch) as a signal on a graph, and apply GSP tools for processing and analysis of the signal in graph spectral domain. In this paper, we overview recent graph spectral techniques in GSP specifically for image/video processing. The topics covered include image compression, image restoration, image filtering, and image segmentation.

Directional block transforms (DBTs), such as discrete Fourier transforms, are basically less efficient for sparse image representation than directional overlapped transforms, such as curvelet and contourlet, but have advantages in practical computation, such as less computational cost, less amount of memory usage to be used, and parallel processing. In order to realize efficient DBTs, this paper proposes directional discrete cosine transforms (DDCTs) by using discrete cosine and sine transforms. The resulting transforms provide richer directional orientations of atoms than conventional DBTs, and thus they are expected to be more efficient for image analysis and processing. In experiments, we evaluate DDCTs with conventional DBTs in image recovery by a convex optimization.

We propose an eigenvalue shrinkage method with a modified Chebyshev polynomial approximation (CPA). The eigenvalue shrinkage has been used in many fields of signal and image processing. However, the shrinkage takes enormous computation time especially in the case that a matrix constructed from a signal or image becomes very large, i.e., eigendecomposition can hardly be performed. The CPA is an approximation method of the shrinkage function that avoids the eigendecomposition of the matrix. Unfortunately, it is known that the CPA generates Gibbs phenomenon around points of discontinuity for approximating an ideal response. The Chebyshev-Jackson polynomial approximation (CJPA) will alleviate the problem, but the transition bandwidth becomes wide, which is an undesired characteristic for some applications. In this paper, we propose an eigenvalue shrinkage method with the reduced Gibbs phenomenon by modifying the CPA using the weighted least squares approach. Our method can reduce the error as well as the CJPA. Furthermore, it yields the narrow transition band. Some experimental results on spectral clustering validate the effectiveness of the method.

This paper addresses the problem of finding optimal sensor placement, i.e., determining F sensor positions from N possible locations. We propose a sensor selection method based on the localization operator of graph signal processing. This method can select sensors while considering the localizations both in graph vertex domain and graph spectral domain and is fast, since eigendecomposition of graph Laplacian matrix is not required. We also propose an interpretation of the conventional node selection based on graph sampling theory by using the graph localization operators. Experiments on selected sensor location, execution time and prediction error comparisons are conducted to show the effectiveness of our approach.

This paper addresses a polyphase1structure of spectral graph wavelets and filter banks. We consider two-channel critically sampled graph filter banks. In classical signal processing, polyphase structure of filter banks is very useful since downsampler (upsampler) can be placed before analysis filtering (after synthesis filtering). We theoretically derive that a similar structure is also possible for spectral graph filter banks. The structure can be used for any two-channel critically sampled spectral graph filter banks as long as an underlying graph is bipartite.

In this paper, we propose a multiple line extraction method from multimodal data points in high dimensional space. It can sparsely represent multimodal sensor network data by utilizing high correlation among channels in the data. We exploit the idea of Color Lines, which is a model using high correlation among RGB channels in computer vision. It represents real color images as a collection of multiple lines in RGB color space. By extracting color lines from multimodal data, our proposed method can utilize hidden inter-channel relationships unlike conventional methods. We apply the proposed method for compressing a multimodal data matrix and show its effectiveness.

We propose an image colorization method using fast soft-thresholding of singular values (singular value thresholding). An image colorization method with nuclear norm minimization (NNM) has been proposed and brings good results. NNM usually requires iterative application of singular value decomposition (SVD) for singular value thresholding. However, the computational cost of SVD in the colorization method becomes too expensive to handle high-resolution images. In this paper, we reduce its computational cost by using Chebyshev polynomial approximation (CPA). Singular value thresholding is expressed by a multiplication of certain matrices derived from the characteristic of CPA. As a result, our CPA-based technique makes the image colorization method much more efficient. In addition, we replace the optimization method used in the image colorization method by alternating direction method of multipliers, which further accelerates the computation. Experimental results verify the effectiveness of our method with respect to the computation time and the approximation precision.

We consider the problem of selecting optimal sensor placements. The proposed approach is based on the sampling theorem of graph signals. We choose sensors that maximize the graph cut-off frequency, i.e., the most informative sensors for predicting the values on unselected sensors. We study the existing methods in the context of graph signal processing and clarify the relationship between these methods and the proposed approach. The effectiveness of our approach is verified through numerical experiments, showing advantages in prediction error and execution time.

Edge-preserving smoothing is one of the most important topics for image and video processing. Recently, we presented a multiscale image decomposition method based on domain transform, which is an efficient edge-preserving smoothing method. It is robust to noise compared with the original domain transform. In this paper, we generalize the scheme so that it can be applied to not only domain transform but also any deformation (warping) of pixels (or nonuniformly sampled signals) through showing the facts that the domain transform is a specific method of mesh deformation with a simple cost function. We also propose construction methods of filters by using arbitrary continuous filters or graph spectral filters in order that various filters can be accommodated by our method. To evaluate the proposed method, we performed experiments on pencil drawing and stylization. These results show that our approach easily changes the smoothing strength in accordance with the applications due to its multiscale scheme.

We propose a deblurring algorithm of point cloud attributes inspired by multi-Wiener SURE-LET deconvolution. The image reconstructed by the SURE-LET approach is expressed as a linear combination of multiple filtered images by the filters defined on the frequency domain. The coefficients of the linear combination are calculated so that the estimate of mean squared error between the original and restored images is minimized. However, since the SURE-LET approach is only adjusted to images, it cannot directly be applied to point cloud attributes, e.g., texture data on 3D models, since they cannot be transformed to their frequency domain. To overcome the problem, we use graph signal processing (GSP) for deblurring the complex-structured data. That is, the SURE-LET approach is redefined on GSP, where the Wiener-like filtering is followed by the subband decomposition with an analysis graph filter bank, and then thresholding for each subband is performed. In the experiments, the proposed method is applied to blurred textures on 3D models, and the experimental results show clearly deblurred textures on a 3D model and present good SNRs.

In this paper, we propose a convex optimization method of prefilters for image coding. JPEG, which is the de facto image coding method, generally produces some errors, e.g., blocking artifacts, under the low bit rate case. The undersampled time-domain lapped transform (TDLT) can efficiently reduce the errors. To improve the performance of the undersampled TDLT, its prefilter is determined by minimizing the errors between the original image and the image upsampled from the downsampled one. This approach enhances the performance but there exists a room for further improvements since the image derived by the prefilter would not become a smoothed image whose charactaristic is important for image coding. To resolve the problem, we consider to minimize a cost function with ℓ1regularization defined on the frequency domain of the downsampled image. It can be solved by using a convex optimization algorithm; the alternating direction method of multipliers. Some experimental results show the validity of our method.

A framework for oversampled filter banks for graph signals was recently proposed by Tanaka and Sakiyama (2014). It was shown that M-channel oversampled filter bank which is exactly orthogonal is not possible with polynomial spectral filter functions. The result is an extension of the critically sampled framework of Narang and Ortega (2012). In this work we present a solution that is nearly orthogonal which has the advantage of giving a nearly tight transform, i.e. nearly equal frame bounds. A family of target functions which satisfy the orthogonality condition is constructed using Bernstein polynomials. The design of the spectral filters is easily achieved through an approximation of the target functions. Filters with good spectral characteristics that are nearly orthogonal can be easily obtained using the proposed method.

This paper presents a design method of critically sampled graph wavelet transforms (CSGWTs) utilizing real-valued biorthogonal linear-phase wavelets for regular signals. Their filter characteristics are equivalent to those of biorthogonal linear-phase wavelets and can be expressed by real-valued closed-form with the sum of sinusoidal waves in the graph spectral domain. The proposed CSGWTs satisfy the perfect reconstruction condition for graph signals. Since the proposed filters are smooth functions, they are well-behaved even if we use a lower-order polynomial approximation. The performance of the proposed CSGWTs is evaluated by comparison with existing CSGWTs.

Improved retargeting pyramid (iRP) is a multiscale image pyramid using content-aware image resizing (also known as retargeting). It has been reported that the iRP outperforms conventional pyramids in linear approximation and denoising. However, the reason of its performance gain was not well discussed so far. In this paper, we reveal that retargeting in the iRP acts as locally underdecimated filters for significant region(s) while keeping its global downsampling ratio. Furthermore, our iRP is applied to various image processing applications to validate its performance.

In this paper, we propose a fast and an approximate solution of non-local/local filters using Chebyshev polynomial approximation (CPA). A non-local/local filter is generally expressible in a matrix form. From the matrix notation, image denoising performance is improved by filtering the eigenvalues of the filter matrix. However, it requires much execution time due to computational complexity of eigendecomposition. To reduce the computational cost, we apply the CPA to eigenvalue filtering, leading to an eigendecomposition-free procedure. Moreover, a fast SURE-based parameter optimization is possible by using the CPA. It enables us to determine a suitable filtering parameter efficiently. Numerical examples illustrate that the proposed method is significantly faster than conventional methods while it maintains high approximate precision.

The retargeting pyramid (RP) is a multiscale image pyramid using content-aware image resizing. In the previous implementation of the RP, a two-step interpolation is adopted to obtain the desired resolution. However, this interpolation leads to performance loss for image processing. In this paper, we improve the performance of the RP by replacing the two-step interpolation with a single interpolation using a matrix representation of the bilateral filter and Tikhonov regularization.

This paper proposes M-channel oversampled filter banks for graph signals. The filter set satisfies the perfect reconstruction condition. A method of designing oversampled graph filter banks is presented which allows us to design filters with arbitrary parameters, unlike the conventional critically-sampled graph filter banks. The practical performance of the proposed filter banks is validated through graph signal denoising experiments.

In this paper, we propose multidimensional (MD) linear-phase perfect reconstruction filter banks (LPPRFBs) with higher order feasible (HOF) building blocks. Since existing HOF building blocks are only applicable for one-dimensional LPPRFBs, we generalize them to MD LPPRFBs. The generalized structure can design MD LP-PRFBs with HOF building blocks for both even and odd number of channels. The proposed MD-LPPRFBs realize large filter sizes with fewer number of building blocks than the traditional order-1 structures.

In this paper, we propose a new patch-based image denoising algorithm using graph signal processing. The concept of this algorithm is to take advantage of the redundancy of the BM3D transform and the edge preservation property of graph-based image processing. More specifically, we collect similar patches in the image, and construct a graph by connecting obtained patches. Then we apply a graph wavelet filter bank on graph signals to attenuate additive white gaussian noise by shrinking derived coefficients. We apply our proposed algorithm to depth map denoising. The experimental results demonstrate significant performance gains for the edge preservation and the noise reduction.

This paper presents the trilateral filter (TF) in the perspective of graph signal processing. The TF is a single-pass nonlocal filter for edge-preserving smoothing. To smooth an image, it does not require many iterations compared to conventional smoothing methods, e.g., the bilateral filter. Additionally, one parameter is only required for filtering. Since the TF coefficients depend on original image data, it is not possible to provide a frequency domain representation using regular signal processing. To overcome this problem, we firstly show the TF as a vertex domain transform on a graph and then define it on graph spectral domain. In the experimental results, the proposed method presents better denoising performances than conventional methods.

Graph signals can represent high-dimensional data effectively and images can also be viewed as signals on weighted graphs by connecting the pixels with their neighboring ones. Recently, we proposed the graph oversampling methods for signal processing on graphs that appends nodes and links to the original graph to obtain an oversampled graph Laplacian matrix. In this paper, we consider new over-sampling methods of image graphs. By using the graph oversampling, we can make a bipartite graph that considers rectangular and diagonal connections simultaneously, while it cannot be realized by conventional critically sampled bipartite graphs. Furthermore, expanding the graphs according to the edge information enables us to decompose the image with the edge-preserving property. We perform the critically sampled graph filter bank on the oversampled graph and show that the proposed method outperforms other transforms, including the critically sampled graph filter banks and the graph Laplacian pyramid, in non-linear approximation and denoising experiments.

Several color-to-gray image mapping (CGIM) methods were proposed so far to restore a color image from its corresponding printed grayscale image. They are based on embedding chrominance values into high-frequency subbands of the luminance signal. In the conventional methods, textures often become noticeable in the chrominance-embedded gray image since subsampled chrominance values are embedded directly. As a result, qualities of the chrominance-embedded grayscale images are degraded especially for images with rich textures. In this paper, we propose an improved CGIM method using DC level shifting and directional transform. In the experimental results, our method greatly improves the qualities of both the chrominance-embedded grayscale and the restored color images in comparison with conventional methods.

The multiplierless fast Fourier transform (FFT) with dyadic-valued (rational) coefficients is important for many signal processing tools. The proposed lifting based FFT (L-FFT) based on fast Hartley transform (FHT) has a simpler structure than existing ones because fewer lifting steps need to be approximated. In addition, it has a structure of real-valued calculation followed by complex-valued parts, thereby it requires fewer memories for the internal implementation than the conventional FFTs.

The retargeting pyramid (RP) method is a good alternative to the well-known Laplacian pyramid (LP) approach for multiscale image decomposition. RP can be obtained by replacing the low-pass filtering and downsampling processes in LP with content-aware image resizing (a.k.a. retargeting), which is a technique being developed in computer vision research. In this paper, we improve RP so that it obtains good scalable image representation. The improved RP is then integrated with a well-known multiscale-multidirection (MSMD) transform, contourlet transform, to construct a saliency-oriented MSMD image representation. In the experiment, our decomposition outperforms the conventional pyramid structures.

In distributed video coding (DVC), a low resolution video sequence is usually generated with spatial and/or temporal downsampling at an encoder. At a decoder side, interpolation is performed and the interpolated pixels are further refined by using an error-correcting code such as Turbo codes or LDPC. In our previous work, we proposed a spatial domain DVC which uses a line-based downsampling method called selective data pruning (SDP). SDP is used for reducing the spatial frame size before compression. After decoding, received frames are decoded and interpolated back to their original size by high-order edge-directed interpolation (HEDI). In this paper, we propose a modified high-order edge-directed interpolation (M-HEDI) to avoid interpolation artifacts. Experimental results show that the interpolated frames by using M-HEDI have higher quality than those using HEDI. The proposed method outperforms conventional DVCs and the video coding standard H.264/AVC in majority of all the test video sequences.

In image compression, decimation and interpolation techniques as pre-/postprocessing of a compression framework offer excellent energy compaction capability for low bit rate image coding. However, an interpolation filter cannot be defined as the inverse matrix of the given decimation filter since the former is a wide matrix and the latter is a tall one. Even without any compression, there will be some distortions in the reconstructed image. To tackle the problem, interpolation-dependent image downsampling (IDID) method produces optimized downsampled images, which leads to the optimized prefilter of a given postfilter. In this paper, we propose to integrate IDID with time-domain lapped transforms (TDLTs) to improve image coding performances.

Complex-valued conjugate symmetric Hadamard transform (C-CSHT) is a variant of complex Hadamard transform and effective for some signal processing and communication applications. Its closed-form factorization of the general N-channel (N = 2m) case was recently proposed, however, there still exist a room to find an effective factorization especially for unified factorization of C-CSHT and its real-valued transform counterpart (R-CSHT). In this paper, we present another simple closed-form factorization of C-CSHT based on that of R-CSHT. The proposed factorization is applicable for both complex- and real-valued CSHTs with one factorization. Furthermore, the relationship with the common block transform, DCT, is revealed.

Discrete cosine transform (DCT) is known as efficient frequency transform, and when it is implemented on software/hardware, multiplier is undesirable for faster implementation. This paper presents a realization of multiplierless fast DCT for lossy image/video coding on arbitrary devices. First, the proposed DCT is constructed by using fast Hartley transform (FHT). Next, the redundancy of the structure is eliminated by using several characteristics of rotation matrix. Then, multiplierless DCT is obtained by approximating rotation matrices to multiplierless lifting structures with adders and bit-shifters. Finally, the proposed DCT is validated by comparing with the conventional DCTs in image coding.

Several color-to-gray mapping methods were proposed to restore a color image from its corresponding grayscale image. These methods are based on embedding chrominance signals into high-frequency subbands of the luminance signal. In the conventional methods, only separable filters are used for the subband decomposition. In addition, subbands at fixed positions are always used to embed chrominance signals. However, in many images, diagonal components are included as well as horizontal/vertical ones. Therefore, qualities of chrominance-embedded grayscale and restored color images are sometimes degraded especially for images with rich textures. In this paper, we propose an improved color restoration method using a directional transform named hybrid wavelets and directional filter banks which considers directionality in images. Experimental results show our method improves the image qualities of the restored color images as well as the chrominance-embedded grayscale images.

We propose a low-complexity, pixel-based watermarking method utilizing the edge areas in an image. In this method, an image is divided into blocks and the blocks are classified as edge blocks and non-edge blocks. The histogram of pixels in an edge block is a bi-modal distribution which has two peaks. Therefore, these pixels are further classified into two classes named “high peak class” and “low peak class”. Then, a bit of the watermark is embedded by controlling the between-class variance by changing the pixel values in each class of the edge block. We utilized the discriminant analysis method for deciding a threshold and controlling the between-class variance. The proposed method can improve the image quality while maintaining robustness against compression and smoothing. In this paper, we evaluated the image quality of watermarked images using PSNR and SSIM. We also evaluated robustness against JPEG compression and Gaussian filtering.

This paper proposes an image coding method incorporated with content-aware image resizing. It is a promising application of our previously proposed rate-dependent seam carving (RD-SC). RD-SC is combined with lifting-based discrete wavelet transform to construct a new multiresolution image representation. Furthermore, the modified parent-children relationship of SPIHT is shown. Our proposed image coding presents comparable performances to the conventional SPIHT even for the original size, and retargeted image quality is satisfactory.

In this paper, we present a seam carving, which is a well-known content-aware image resizing method, with a constraint on bitrates for seam path information (SPI). The SPI corresponds to pixel positions to be pruned and it generally requires high bitrate when we store or transmit it. However, the SPI should be transmitted to re ceivers in the case that the receivers are devices with low computing power, such as cell phones and PDAs since seam carving at the receivers is a computationally-demanding process. We resolve the problem by applying piecewise linear approximation to the seam paths. In the experimental results, the retargeted images yielded by the original seam carving and the proposed one are very similar, whereas required bitrate for the SPI in the proposed method is 34-97 % less than the original one.

In this paper, we extend a rate-dependent content-aware image retargeting method, generalized selective data pruning, to video sequence. It is regarded as a spatial-domain video retargeting, i.e., reduction of the spatial video size, with a rate-dependent property for side information. It is realized by the piecewise linear approximation of seam carving. The side information bitrate for video retargeting can vary depending on the control parameter and is negligible to transmit with the encoded video bitstream while the method maintains video retargeting performance.

In current distributed video coding (DVC), interpolation is performed at the decoder and the interpolated pixels are reconstructed by using error-correcting codes, such as Turbo codes and LDPC. There are two possibilities for downsampling video sequences at the encoder: temporally or spatially. Traditionally temporal downsampling, i.e., frame dropping, is used for DVC. Furthermore, those with spatial downsampling (scaling) have been investigated. Unfortunately, most of them are based on uniform downsampling. Due to this, details in video sequences are often discarded. For example, edges and textured regions are difficult to interpolate, and thus require many parity bits to restore the interpolated portions for the spatial domain DVC. In this paper, we propose a new spatial domain DVC based on adaptive line dropping so-called selective data pruning (SDP). SDP is a simple nonuniform downsampling method. The pruned lines are determined to avoid cutting across edges and textures. Experimental results show the proposed method outperforms a conventional DVC for sequences with a large amount of motions.

Image concentration is an image resizing technique which shrinks an image size but does not change important region(s) in the original image, whereas image dilution is the reverse process to image concentration. In this paper, we incorporate image concentration/dilution process in image coding. An image retargeting method called seam carving is used for image concentration. Furthermore, it is modified to yield rate-distortion optimized seams by a hierarchical search process. Our method can be incorporated into any image encoder since the image concentration (dilution) is a pre(post)- processing of image encoder (decoder). In the experimental results, JPEG/SPIHT with image concentration/dilution presents significant bitrate savings compared with the original JPEG/SPIHT alone and reconstructed image qualities are very similar to each other.

In this paper, an improved method of image concentration for image coding with concentration and dilution is presented. Image concentration is an image resizing technique which shrinks an image size but does not change important region(s) in the original image, whereas image dilution is the reverse process to image concentration. The authors have proposed an image coding approach based on the image concentration and dilution. This paper focuses on an improvement of image concentration to enhance quality of the reconstructed (diluted) image. In the experimental results, the improved method obtains bitrate savings compared with image encoders alone, and the reconstructed images do not have perceptually noticeable artifacts.

Adaptive directional wavelet transform is an effective alternative of the traditional 2-D wavelet transform for image coding. It is able to transform an image adaptively along diagonal orientations as well as conventional vertical/horizontal directions. However, it requires to transmit transform direction information to the decoder side. For image coding at very low bitrates, the bit budget of the direction information degrades a reconstructed image quality. In this paper, a method to construct a scalable bitstream for transform directions is presented. We utilize the fact that the matrix yielded by transform direction indices still contains the original image characteristics. The matrix is transformed by a block-lifting based DCT, then encoded by SPIHT to yield a scalable bitstream. Our method is effective for very low bitrate image coding, and is comparable to the non-scalable one for middle-to-high bitrates.

In this paper, we propose a data embedding method into still images based on Vector Quantization (VQ). In recent years, several VQ-based data embedding methods have been proposed. For example, `Mean Gray-Level Embedding method (MGLE)' are `Pair wise Nearest-Neighbor Embedding method (PNNE)' are simple, but not sufficiently effective. Meanwhile, an efficient adaptive data hiding method called `Adaptive Clustering Embedding method (ACE)' was proposed, but is somewhat complicated because the VQ indices have to be adaptively clustered in the embedding process. In our proposed method, output vectors are considered as nodes, and nodes are linked as a tree structure and information is embedded by using some of linked vectors. The simulation results show that our proposed method indicates higher SNR than the conventional methods under the same amounts of embedded data.

Graphical passwords are an authentication method that uses pictures as passwords instead of using alphanumeric characters. We propose a graphical password method which is difficult to steal original pass-image by using characteristics of human vision system. In our method, we combine low frequency components of a decoy picture with high frequency components of a pass-image. It is easy for legitimate users to recognize the pass-image in the blended image. On the other hand, this task is difficult for attackers. We used discrete wavelet transform (DWT) to blend a decoy image and a pass-image. User studies are conducted to evaluate memorability and shoulder-surfing robustness of this method. We also compared our method with other existing methods in terms of the authentication time and the success ratio by the user test. The results show that our method is more usable and secure against shoulder-surfing.

This paper proposes an efficient approach for adaptive directional wavelet transform (WT) based on directional prefiltering. Although the adaptive directional WT is able to transform an image along diagonal orientations as well as traditional horizontal and vertical directions, it sacrifices computation speed for good image coding performance. We present two efficient methods to find the best transform directions by prefiltering using 2-D filter bank or 1-D directional WT along two fixed directions. The proposed direction calculation methods achieve comparable image coding performance comparing to the conventional one with less complexity. Furthermore, transform direction data of the proposed method can be used for content-based image retrieval to increase retrieval ratio.

This paper proposes a computationally efficient approach of adaptive directional wavelet transform (AD WT). The AD WT is based on lifting implementation of WT, and it is able to transform an image along diagonal orientations as well as traditional horizontal and vertical directions. The AD WT sacrifices computational speed for its good image coding performance. We present an alternative method to find the best transform directions by pre-directional filterings for the AD WT. The proposed direction calculation method shows very comparable image coding performance to the conventional one, whereas its computational cost is relatively very low.

In this paper, we propose an extension of combined 2D and 1D-directional filter banks (TODFBs) with adaptive approach in their 1D-directional stages. TODFBs show better performance in image coding and denoising compared to the traditional wavelet transform (WT), however, they still have possibilities to improve their performance in image coding by adopting the adaptive directional WTs for their 1D-directional stages. An efficient method to determine the transform directions is also proposed. In image coding results, our proposed filter banks gain PSNR and visual quality improvements compared with the WTs and the non-adaptive TODFBs.

In this paper, a calculation method of transform directions for adaptive directional wavelet transform (AD WT) is proposed. It uses 2-D highpass filters as a preprocessing of the conventional calculation stage. The filters can reduce the number of direction candidates effectively. In image coding, our proposed framework shows very comparable results to the conventional AD WT and outperforms the traditional separable WT.

In this paper, effective multiresolution image representations using a combination of 2-D filter bank (FB) and directional wavelet transform (WT) are presented. The proposed methods yield simple implementation and low computation costs compared to previous 1-D and 2-D FB combinations or adaptive directional WT methods. Furthermore, they are nonredundant transforms and realize quad-tree like multiresolution representations. In applications on nonlinear approximation, image coding, and denoising, the proposed filter banks show visual quality improvements and have higher PSNR than the conventional separable WT or the contourlet.

In this paper, a novel design method of critically sampled contourlet transform (CSCT) is proposed. Although, several types of CSCT have been proposed, they have some problems on efficiency and flexibility of their frequency plane partition patterns. In contrast to the way in conventional design methods based on a "top-down" approach, the proposed one is based on a "bottom-up" one. That is, the proposed CSCT decomposes the frequency plane into small directional sub- bands, and then synthesizes them up to a target frequency plane partition, while the conventional ones decompose into it directly. By this way, the proposed CSCT can provide an efficient and flexible frequency plane partition for image coding.

In this paper, an effective multiresolution image representation using the combination of 2D quincunx filter bank (FB) and directional wavelet transform (WT) is presented. The proposed method yields simple implementation and low calculation costs compared to the other 1D and 2D FB combinations or adaptive directional WTs. Furthermore, it is a nonredundant transform and realizes quad-tree like multiresolution representation. In applications on nonlinear approximation and image coding, the proposed filter bank shows visual quality improvements and has higher PSNR.

This paper proposes new building blocks for the lattice structure of oversampled linear-phase perfect reconstruction filter banks (OLPPRFBs). The structure is an extended version of higher-order feasible building blocks for critically-sampled LPPRFBs. It uses fewer number of building blocks and design parameters than those of traditional OLPPRFBs, whereas the frequency characteristic of the new OLPPRFB is comparable to that of traditional one.

This paper introduces an image transform method by using M-channel biorthogonal filter banks (BOFBs) with an efficient lifting factorization. The proposed lifting factorization of a building block in their lattice structure has unity diagonal scaling coefficients and guarantees perfect reconstruction even if the obtained coefficients are quantized. Since the number of rounding operators of proposed lifting-based BOFBs (LBBOFBs) can be reduced by merging the lifting steps, the proposed structure is efficient for lossless image coding. Image coding results indicate better performance than conventional methods.

In this paper, we present the structure and design method for a first-order linear-phase filter bank (FOLPFB) which has unequal filter lengths in its synthesis bank (UFLPFB). A FOLPFB is a generalized version of biorthogonal LPFBs regarding their synthesis filter lengths. Ringing artifact is the main disadvantage of image coding based on FOLPFBs. UFLPFBs can reduce the ringing artifacts as well as approximate smooth regions well.

In recent years, two-channel complex-valued filterbanks have been studied and found theirs several important applications by many researchers, such as complex signal and image processing. One of those important results is that there is no two-channel complex-valued linear-phase paraunitary filterbank (CLPPUFB), except for its filter lengths of 2. In this paper, we introduce a class of special complex-valued filterbanks which is a subclass of biorthogonal filterbanks. Those filterbanks are called complex pseudo-orthogonal filterbanks (CPOFB), based on the concept of pseudo-orthogonality (PO). This kind of orthogonality, we propose, is different from the conventional one essentially. This paper also shows possibility to design a two-channel complex linear-phase filterbank (CLPFB) with its filter lengths are more than 2, based on PO. Finally, we show a design example of a complex linear-phase pseudo-orthogonal filterbank (CLPPOFB). Moreover, such CPOFB can satisfy the linear-phase condition simultaneously with filter lengths are more than 2. This paper shows a theory, a design method and an example of CLPPOFB

Future electric lights will be composed of white LED (light emitting diodes). Indoor wireless optical communication systems utilizing white LED lights have been proposed in our laboratory and we have been studying it. Generally, plural lights are installed in our room. Therefore, their optical path difference must be considered. In this paper, the influence of optical path difference has been investigated and two approaches for this problem are introduced. One uses OOK-RZ (on-off keying, return-to-zero) coding and the other uses optical OFDM (orthogonal frequency division multiplexing). From the results of computer simulations, we have found that these approaches are feasible for wireless optical communication systems utilizing white LED lights.

The vehicle information and communication system (VICS) is starting to become practicable. The infrared system of a VICS detects vehicles on the road by using optical beacons to control traffic and to supply real-time traffic information. But it needs an enormous budget because the optical beacons must be located on every lane of the road throughout the country. We propose a traffic information system using existing LED traffic lights, and focus on its visible rays and power used for traffic control, the number and location of the traffic lights, and the movement toward LED traffic lights. We design the best service area not to interfere with other service areas and analyze its basic performance such as the suitable modulation, required SNR and the amount of receivable information.

We propose a wireless optical communication system with white colored LEDs for a wireless home link (WHL). The white colored LEDs have a high power output and are regarded as lamps for the next generation. In the proposed system, this device is used for a wireless home link. The proposed system is suitable for private networks such as consumer communication networks. From numerical and simulation results, it is confirmed that the proposed system is available and the problems to be solved are made clear.

In indoor optical channels, intersymbol interference (ISI) due to the multipath propagation prevents high data rate transmission. A new optical multi-wavelength PPM (pulse position modulation) has been investigated for improving the quality of transmission. In this strategy, parallel transmission is accomplished which lowers the data rate per channel and thus reduces the effect of ISI. Furthermore, this strategy also implements a parallel coding technique in the predetermined parallel branches. This parallel coding corrects errors without changing the system data rate. The simulation results show that a combination of these methods can achieve high quality transmission without reduction of the total data rate.