Showing 1–38 of 38 results for author: Gilboa, G

Fast and Simple Explainability for Point Cloud Networks

Authors: Meir Yossef Levi, Guy Gilboa

Abstract: We propose a fast and simple explainable AI (XAI) method for point cloud data. It computes pointwise importance with respect to a trained network downstream task. This allows better understanding of the network properties, which is imperative for safety-critical applications. In addition to debugging and visualization, our low computational complexity facilitates online feedback to the network at… ▽ More We propose a fast and simple explainable AI (XAI) method for point cloud data. It computes pointwise importance with respect to a trained network downstream task. This allows better understanding of the network properties, which is imperative for safety-critical applications. In addition to debugging and visualization, our low computational complexity facilitates online feedback to the network at inference. This can be used to reduce uncertainty and to increase robustness. In this work, we introduce \emph{Feature Based Interpretability} (FBI), where we compute the features' norm, per point, before the bottleneck. We analyze the use of gradients and post- and pre-bottleneck strategies, showing pre-bottleneck is preferred, in terms of smoothness and ranking. We obtain at least three orders of magnitude speedup, compared to current XAI methods, thus, scalable for big point clouds or large-scale architectures. Our approach achieves SOTA results, in terms of classification explainability. We demonstrate how the proposed measure is helpful in analyzing and characterizing various aspects of 3D learning, such as rotation invariance, robustness to out-of-distribution (OOD) outliers or domain shift and dataset bias. △ Less

Submitted 15 March, 2024; v1 submitted 12 March, 2024; originally announced March 2024.

DXAI: Explaining Classification by Image Decomposition

Authors: Elnatan Kadar, Guy Gilboa

Abstract: We propose a new way to explain and to visualize neural network classification through a decomposition-based explainable AI (DXAI). Instead of providing an explanation heatmap, our method yields a decomposition of the image into class-agnostic and class-distinct parts, with respect to the data and chosen classifier. Following a fundamental signal processing paradigm of analysis and synthesis, the… ▽ More We propose a new way to explain and to visualize neural network classification through a decomposition-based explainable AI (DXAI). Instead of providing an explanation heatmap, our method yields a decomposition of the image into class-agnostic and class-distinct parts, with respect to the data and chosen classifier. Following a fundamental signal processing paradigm of analysis and synthesis, the original image is the sum of the decomposed parts. We thus obtain a radically different way of explaining classification. The class-agnostic part ideally is composed of all image features which do not posses class information, where the class-distinct part is its complementary. This new visualization can be more helpful and informative in certain scenarios, especially when the attributes are dense, global and additive in nature, for instance, when colors or textures are essential for class distinction. Code is available at https://github.com/dxai2024/dxai. △ Less

Submitted 29 March, 2024; v1 submitted 30 December, 2023; originally announced January 2024.

Enhancing Neural Training via a Correlated Dynamics Model

Authors: Jonathan Brokman, Roy Betser, Rotem Turjeman, Tom Berkov, Ido Cohen, Guy Gilboa

Abstract: As neural networks grow in scale, their training becomes both computationally demanding and rich in dynamics. Amidst the flourishing interest in these training dynamics, we present a novel observation: Parameters during training exhibit intrinsic correlations over time. Capitalizing on this, we introduce Correlation Mode Decomposition (CMD). This algorithm clusters the parameter space into groups,… ▽ More As neural networks grow in scale, their training becomes both computationally demanding and rich in dynamics. Amidst the flourishing interest in these training dynamics, we present a novel observation: Parameters during training exhibit intrinsic correlations over time. Capitalizing on this, we introduce Correlation Mode Decomposition (CMD). This algorithm clusters the parameter space into groups, termed modes, that display synchronized behavior across epochs. This enables CMD to efficiently represent the training dynamics of complex networks, like ResNets and Transformers, using only a few modes. Moreover, test set generalization is enhanced. We introduce an efficient CMD variant, designed to run concurrently with training. Our experiments indicate that CMD surpasses the state-of-the-art method for compactly modeled dynamics on image classification. Our modeling can improve training efficiency and lower communication overhead, as shown by our preliminary experiments in the context of federated learning. △ Less

Submitted 20 December, 2023; originally announced December 2023.

Robustifying Point Cloud Networks by Refocusing

Authors: Meir Yossef Levi, Guy Gilboa

Abstract: The ability to cope with out-of-distribution (OOD) corruptions and adversarial attacks is crucial in real-world safety-demanding applications. In this study, we develop a general mechanism to increase neural network robustness based on focus analysis. Recent studies have revealed the phenomenon of \textit{Overfocusing}, which leads to a performance drop. When the network is primarily influenced… ▽ More The ability to cope with out-of-distribution (OOD) corruptions and adversarial attacks is crucial in real-world safety-demanding applications. In this study, we develop a general mechanism to increase neural network robustness based on focus analysis. Recent studies have revealed the phenomenon of \textit{Overfocusing}, which leads to a performance drop. When the network is primarily influenced by small input regions, it becomes less robust and prone to misclassify under noise and corruptions. However, quantifying overfocusing is still vague and lacks clear definitions. Here, we provide a mathematical definition of \textbf{focus}, \textbf{overfocusing} and \textbf{underfocusing}. The notions are general, but in this study, we specifically investigate the case of 3D point clouds. We observe that corrupted sets result in a biased focus distribution compared to the clean training set. We show that as focus distribution deviates from the one learned in the training phase - classification performance deteriorates. We thus propose a parameter-free \textbf{refocusing} algorithm that aims to unify all corruptions under the same distribution. We validate our findings on a 3D zero-shot classification task, achieving SOTA in robust 3D classification on ModelNet-C dataset, and in adversarial defense against Shape-Invariant attack. Code is available in: https://github.com/yossilevii100/refocusing. △ Less

Submitted 12 March, 2024; v1 submitted 10 August, 2023; originally announced August 2023.

Minimizing Quotient Regularization Model

Authors: Chao Wang, Jean-Francois Aujol, Guy Gilboa, Yifei Lou

Abstract: Quotient regularization models (QRMs) are a class of powerful regularization techniques that have gained considerable attention in recent years, due to their ability to handle complex and highly nonlinear data sets. However, the nonconvex nature of QRM poses a significant challenge in finding its optimal solution. We are interested in scenarios where both the numerator and the denominator of QRM a… ▽ More Quotient regularization models (QRMs) are a class of powerful regularization techniques that have gained considerable attention in recent years, due to their ability to handle complex and highly nonlinear data sets. However, the nonconvex nature of QRM poses a significant challenge in finding its optimal solution. We are interested in scenarios where both the numerator and the denominator of QRM are absolutely one-homogeneous functions, which is widely applicable in the fields of signal processing and image processing. In this paper, we utilize a gradient flow to minimize such QRM in combination with a quadratic data fidelity term. Our scheme involves solving a convex problem iteratively.The convergence analysis is conducted on a modified scheme in a continuous formulation, showing the convergence to a stationary point. Numerical experiments demonstrate the effectiveness of the proposed algorithm in terms of accuracy, outperforming the state-of-the-art QRM solvers. △ Less

Submitted 8 August, 2023; originally announced August 2023.

Comments: 20 pages

MSC Class: 49N45; 65K10; 90C05; 90C26

Additive Class Distinction Maps using Branched-GANs

Authors: Elnatan Kadar, Jonathan Brokman, Guy Gilboa

Abstract: We present a new model, training procedure and architecture to create precise maps of distinction between two classes of images. The objective is to comprehend, in pixel-wise resolution, the unique characteristics of a class. These maps can facilitate self-supervised segmentation and objectdetection in addition to new capabilities in explainable AI (XAI). Our proposed architecture is based on imag… ▽ More We present a new model, training procedure and architecture to create precise maps of distinction between two classes of images. The objective is to comprehend, in pixel-wise resolution, the unique characteristics of a class. These maps can facilitate self-supervised segmentation and objectdetection in addition to new capabilities in explainable AI (XAI). Our proposed architecture is based on image decomposition, where the output is the sum of multiple generative networks (branched-GANs). The distinction between classes is isolated in a dedicated branch. This approach allows clear, precise and interpretable visualization of the unique characteristics of each class. We show how our generic method can be used in several modalities for various tasks, such as MRI brain tumor extraction, isolating cars in aerial photography and obtaining feminine and masculine face features. This is a preliminary report of our initial findings and results. △ Less

Submitted 4 May, 2023; originally announced May 2023.

EPiC: Ensemble of Partial Point Clouds for Robust Classification

Authors: Meir Yossef Levi, Guy Gilboa

Abstract: Robust point cloud classification is crucial for real-world applications, as consumer-type 3D sensors often yield partial and noisy data, degraded by various artifacts. In this work we propose a general ensemble framework, based on partial point cloud sampling. Each ensemble member is exposed to only partial input data. Three sampling strategies are used jointly, two local ones, based on patches a… ▽ More Robust point cloud classification is crucial for real-world applications, as consumer-type 3D sensors often yield partial and noisy data, degraded by various artifacts. In this work we propose a general ensemble framework, based on partial point cloud sampling. Each ensemble member is exposed to only partial input data. Three sampling strategies are used jointly, two local ones, based on patches and curves, and a global one of random sampling. We demonstrate the robustness of our method to various local and global degradations. We show that our framework significantly improves the robustness of top classification netowrks by a large margin. Our experimental setting uses the recently introduced ModelNet-C database by Ren et al.[24], where we reach SOTA both on unaugmented and on augmented data. Our unaugmented mean Corruption Error (mCE) is 0.64 (current SOTA is 0.86) and 0.50 for augmented data (current SOTA is 0.57). We analyze and explain these remarkable results through diversity analysis. Our code is available at: https://github.com/yossilevii100/EPiC △ Less

Submitted 24 April, 2023; v1 submitted 20 March, 2023; originally announced March 2023.

Graph Laplacian for Semi-Supervised Learning

Authors: Or Streicher, Guy Gilboa

Abstract: Semi-supervised learning is highly useful in common scenarios where labeled data is scarce but unlabeled data is abundant. The graph (or nonlocal) Laplacian is a fundamental smoothing operator for solving various learning tasks. For unsupervised clustering, a spectral embedding is often used, based on graph-Laplacian eigenvectors. For semi-supervised problems, the common approach is to solve a con… ▽ More Semi-supervised learning is highly useful in common scenarios where labeled data is scarce but unlabeled data is abundant. The graph (or nonlocal) Laplacian is a fundamental smoothing operator for solving various learning tasks. For unsupervised clustering, a spectral embedding is often used, based on graph-Laplacian eigenvectors. For semi-supervised problems, the common approach is to solve a constrained optimization problem, regularized by a Dirichlet energy, based on the graph-Laplacian. However, as supervision decreases, Dirichlet optimization becomes suboptimal. We therefore would like to obtain a smooth transition between unsupervised clustering and low-supervised graph-based classification. In this paper, we propose a new type of graph-Laplacian which is adapted for Semi-Supervised Learning (SSL) problems. It is based on both density and contrastive measures and allows the encoding of the labeled data directly in the operator. Thus, we can perform successfully semi-supervised learning using spectral clustering. The benefits of our approach are illustrated for several SSL problems. △ Less

Submitted 19 April, 2023; v1 submitted 12 January, 2023; originally announced January 2023.

Comments: 12 pages, 6 figures

The Underlying Correlated Dynamics in Neural Training

Authors: Rotem Turjeman, Tom Berkov, Ido Cohen, Guy Gilboa

Abstract: Training of neural networks is a computationally intensive task. The significance of understanding and modeling the training dynamics is growing as increasingly larger networks are being trained. We propose in this work a model based on the correlation of the parameters' dynamics, which dramatically reduces the dimensionality. We refer to our algorithm as \emph{correlation mode decomposition} (CMD… ▽ More Training of neural networks is a computationally intensive task. The significance of understanding and modeling the training dynamics is growing as increasingly larger networks are being trained. We propose in this work a model based on the correlation of the parameters' dynamics, which dramatically reduces the dimensionality. We refer to our algorithm as \emph{correlation mode decomposition} (CMD). It splits the parameter space into groups of parameters (modes) which behave in a highly correlated manner through the epochs. We achieve a remarkable dimensionality reduction with this approach, where networks like ResNet-18, transformers and GANs, containing millions of parameters, can be modeled well using just a few modes. We observe each typical time profile of a mode is spread throughout the network in all layers. Moreover, our model induces regularization which yields better generalization capacity on the test set. This representation enhances the understanding of the underlying training dynamics and can pave the way for designing better acceleration techniques. △ Less

Submitted 18 December, 2022; originally announced December 2022.

BASiS: Batch Aligned Spectral Embedding Space

Authors: Or Streicher, Ido Cohen, Guy Gilboa

Abstract: Graph is a highly generic and diverse representation, suitable for almost any data processing problem. Spectral graph theory has been shown to provide powerful algorithms, backed by solid linear algebra theory. It thus can be extremely instrumental to design deep network building blocks with spectral graph characteristics. For instance, such a network allows the design of optimal graphs for certai… ▽ More Graph is a highly generic and diverse representation, suitable for almost any data processing problem. Spectral graph theory has been shown to provide powerful algorithms, backed by solid linear algebra theory. It thus can be extremely instrumental to design deep network building blocks with spectral graph characteristics. For instance, such a network allows the design of optimal graphs for certain tasks or obtaining a canonical orthogonal low-dimensional embedding of the data. Recent attempts to solve this problem were based on minimizing Rayleigh-quotient type losses. We propose a different approach of directly learning the eigensapce. A severe problem of the direct approach, applied in batch-learning, is the inconsistent mapping of features to eigenspace coordinates in different batches. We analyze the degrees of freedom of learning this task using batches and propose a stable alignment mechanism that can work both with batch changes and with graph-metric changes. We show that our learnt spectral embedding is better in terms of NMI, ACC, Grassman distance, orthogonality and classification accuracy, compared to SOTA. In addition, the learning is more stable. △ Less

Submitted 19 April, 2023; v1 submitted 30 November, 2022; originally announced November 2022.

Comments: 14 pages, 10 figures

Spectral Total-Variation Processing of Shapes: Theory and Applications

Authors: Jonathan Brokman, Martin Burger, Guy Gilboa

Abstract: We present an analysis of total-variation (TV) on non-Euclidean parameterized surfaces, a natural representation of the shapes used in 3D graphics. Our work explains recent experimental findings in shape spectral TV [Fumero et al., 2020] and adaptive anisotropic spectral TV [Biton and Gilboa, 2022]. A new way to generalize set convexity from the plane to surfaces is derived by characterizing the T… ▽ More We present an analysis of total-variation (TV) on non-Euclidean parameterized surfaces, a natural representation of the shapes used in 3D graphics. Our work explains recent experimental findings in shape spectral TV [Fumero et al., 2020] and adaptive anisotropic spectral TV [Biton and Gilboa, 2022]. A new way to generalize set convexity from the plane to surfaces is derived by characterizing the TV eigenfunctions on surfaces. Relationships between TV, area, eigenvalue, eigenfunctions and their discontinuities are discovered. Further, we expand the shape spectral TV toolkit to include versatile zero-homogeneous flows demonstrated through smoothing and exaggerating filters. Last but not least, we propose the first TV-based method for shape deformation, characterized by deformations along geometrical bottlenecks. We show these bottlenecks to be aligned with eigenfunction discontinuities. This research advances the field of spectral TV on surfaces and its application in 3D graphics, offering new perspectives for shape filtering and deformation. △ Less

Submitted 2 February, 2024; v1 submitted 15 September, 2022; originally announced September 2022.

Comments: 19 pages, 20 figures

Analysis of Branch Specialization and its Application in Image Decomposition

Authors: Jonathan Brokman, Guy Gilboa

Abstract: Branched neural networks have been used extensively for a variety of tasks. Branches are sub-parts of the model that perform independent processing followed by aggregation. It is known that this setting induces a phenomenon called Branch Specialization, where different branches become experts in different sub-tasks. Such observations were qualitative by nature. In this work, we present a methodolo… ▽ More Branched neural networks have been used extensively for a variety of tasks. Branches are sub-parts of the model that perform independent processing followed by aggregation. It is known that this setting induces a phenomenon called Branch Specialization, where different branches become experts in different sub-tasks. Such observations were qualitative by nature. In this work, we present a methodological analysis of Branch Specialization. We explain the role of gradient descent in this phenomenon. We show that branched generative networks naturally decompose animal images to meaningful channels of fur, whiskers and spots and face images to channels such as different illumination components and face parts. △ Less

Submitted 12 June, 2022; originally announced June 2022.

How to Guide Adaptive Depth Sampling?

Authors: Ilya Tcenov, Guy Gilboa

Abstract: Recent advances in depth sensing technologies allow fast electronic maneuvering of the laser beam, as opposed to fixed mechanical rotations. This will enable future sensors, in principle, to vary in real-time the sampling pattern. We examine here the abstract problem of whether adapting the sampling pattern for a given frame can reduce the reconstruction error or allow a sparser pattern. We propos… ▽ More Recent advances in depth sensing technologies allow fast electronic maneuvering of the laser beam, as opposed to fixed mechanical rotations. This will enable future sensors, in principle, to vary in real-time the sampling pattern. We examine here the abstract problem of whether adapting the sampling pattern for a given frame can reduce the reconstruction error or allow a sparser pattern. We propose a constructive generic method to guide adaptive depth sampling algorithms. Given a sampling budget B, a depth predictor P and a desired quality measure M, we propose an Importance Map that highlights important sampling locations. This map is defined for a given frame as the per-pixel expected value of M produced by the predictor P, given a pattern of B random samples. This map can be well estimated in a training phase. We show that a neural network can learn to produce a highly faithful Importance Map, given an RGB image. We then suggest an algorithm to produce a sampling pattern for the scene, which is denser in regions that are harder to reconstruct. The sampling strategy of our modular framework can be adjusted according to hardware limitations, type of depth predictor, and any custom reconstruction error measure that should be minimized. We validate through simulations that our approach outperforms grid and random sampling patterns as well as recent state-of-the-art adaptive algorithms. △ Less

Submitted 20 May, 2022; originally announced May 2022.

Comments: 8 pages

Generalized Inversion of Nonlinear Operators

Authors: Eyal Gofer, Guy Gilboa

Abstract: Inversion of operators is a fundamental concept in data processing. Inversion of linear operators is well studied, supported by established theory. When an inverse either does not exist or is not unique, generalized inverses are used. Most notable is the Moore-Penrose inverse, widely used in physics, statistics, and various fields of engineering. This work investigates generalized inversion of non… ▽ More Inversion of operators is a fundamental concept in data processing. Inversion of linear operators is well studied, supported by established theory. When an inverse either does not exist or is not unique, generalized inverses are used. Most notable is the Moore-Penrose inverse, widely used in physics, statistics, and various fields of engineering. This work investigates generalized inversion of nonlinear operators. We first address broadly the desired properties of generalized inverses, guided by the Moore-Penrose axioms. We define the notion for general sets, and then a refinement, termed pseudo-inverse, for normed spaces. We present conditions for existence and uniqueness of a pseudo-inverse and establish theoretical results investigating its properties, such as continuity, its value for operator compositions and projection operators, and others. Analytic expressions are given for the pseudo-inverse of some well-known, non-invertible, nonlinear operators, such as hard- or soft-thresholding and ReLU. We analyze a neural layer and discuss relations to wavelet thresholding. Next, the Drazin inverse, and a relaxation, are investigated for operators with equal domain and range. We present scenarios where inversion is expressible as a linear combination of forward applications of the operator. Such scenarios arise for classes of nonlinear operators with vanishing polynomials, similar to the minimal or characteristic polynomials for matrices. Inversion using forward applications may facilitate the development of new efficient algorithms for approximating generalized inversion of complex nonlinear operators. △ Less

Submitted 19 September, 2023; v1 submitted 21 November, 2021; originally announced November 2021.

Comments: A significant extension of the SSVM 2023 conference paper (see also v2 here), in particular, new sections 7--9

Journal ref: J Math Imaging Vision, 2024; L. Calatroni et al. (Eds.): SSVM 2023, LNCS 14009, pp. 29--41, 2023

Latent Modes of Nonlinear Flows -- a Koopman Theory Analysis

Authors: Ido Cohen, Guy Gilboa

Abstract: Extracting the latent underlying structures of complex nonlinear local and nonlocal flows is essential for their analysis and modeling. In this work, we attempt to provide a consistent framework through Koopman theory and its related popular discrete approximation -- dynamic mode decomposition (DMD). We investigate the conditions to perform appropriate linearization, dimensionality reduction, and… ▽ More Extracting the latent underlying structures of complex nonlinear local and nonlocal flows is essential for their analysis and modeling. In this work, we attempt to provide a consistent framework through Koopman theory and its related popular discrete approximation -- dynamic mode decomposition (DMD). We investigate the conditions to perform appropriate linearization, dimensionality reduction, and representation of flows in a highly general setting. The essential elements of this framework are Koopman Eigenfunction (KEF), for which existence conditions are formulated. This is done by viewing the dynamic as a curve in state-space. These conditions lay the foundations for system reconstruction, global controllability, and observability for nonlinear dynamics. We examine the limitations of DMD through the analysis of Koopman theory and propose a new mode decomposition technique based on the typical time profile of the dynamics. An overcomplete dictionary of decay profiles is used to sparsely approximate the flow. This analysis is also valid in the full continuous setting of Koopman theory, which is based on variational calculus. We demonstrate applications of this analysis, such as finding KEFs and their multiplicities, dynamics reconstruction, and global linearization. △ Less

Submitted 22 December, 2021; v1 submitted 15 July, 2021; originally announced July 2021.

Comments: Visit our websites https://idoc.webgr.technion.ac.il/ and https://guygilboa.net.technion.ac.il/. The MatLab code is available in https://github.com/IdoCohen5743/Examining-the-Limitations-of-DMD-through-Koopman-Theory-Analysis

Total-Variation -- Fast Gradient Flow and Relations to Koopman Theory

Authors: Ido Cohen, Tom Berkov, Guy Gilboa

Abstract: The space-discrete Total Variation (TV) flow is analyzed using several mode decomposition techniques. In the one-dimensional case, we provide analytic formulations to Dynamic Mode Decomposition (DMD) and to Koopman Mode Decomposition (KMD) of the TV-flow and compare the obtained modes to TV spectral decomposition. We propose a computationally efficient algorithm to evolve the one-dimensional TV-fl… ▽ More The space-discrete Total Variation (TV) flow is analyzed using several mode decomposition techniques. In the one-dimensional case, we provide analytic formulations to Dynamic Mode Decomposition (DMD) and to Koopman Mode Decomposition (KMD) of the TV-flow and compare the obtained modes to TV spectral decomposition. We propose a computationally efficient algorithm to evolve the one-dimensional TV-flow. A significant speedup by three orders of magnitude is obtained, compared to iterative minimizations. A common theme, for both mode analysis and fast algorithm, is the significance of phase transitions during the flow, in which the subgradient changes. We explain why applying DMD directly on TV-flow measurements cannot model the flow or extract modes well. We formulate a more general method for mode decomposition that coincides with the modes of KMD. This method is based on the linear decay profile, typical to TV-flow. These concepts are demonstrated through experiments, where additional extensions to the two-dimensional case are given. △ Less

Submitted 28 November, 2021; v1 submitted 20 May, 2021; originally announced May 2021.

Comments: The MatLab code is available here https://github.com/IdoCohen5743/Total-Variation-Mode-Decomposition Visit our websites https://idoc.webgr.technion.ac.il/ https://www.vision-and-sensing.com/ido-cohen https://www.vision-and-sensing.com/tom-berkov https://guygilboa.net.technion.ac.il/

Experts with Lower-Bounded Loss Feedback: A Unifying Framework

Authors: Eyal Gofer, Guy Gilboa

Abstract: The most prominent feedback models for the best expert problem are the full information and bandit models. In this work we consider a simple feedback model that generalizes both, where on every round, in addition to a bandit feedback, the adversary provides a lower bound on the loss of each expert. Such lower bounds may be obtained in various scenarios, for instance, in stock trading or in assessi… ▽ More The most prominent feedback models for the best expert problem are the full information and bandit models. In this work we consider a simple feedback model that generalizes both, where on every round, in addition to a bandit feedback, the adversary provides a lower bound on the loss of each expert. Such lower bounds may be obtained in various scenarios, for instance, in stock trading or in assessing errors of certain measurement devices. For this model we prove optimal regret bounds (up to logarithmic factors) for modified versions of Exp3, generalizing algorithms and bounds both for the bandit and the full-information settings. Our second-order unified regret analysis simulates a two-step loss update and highlights three Hessian or Hessian-like expressions, which map to the full-information regret, bandit regret, and a hybrid of both. Our results intersect with those for bandits with graph-structured feedback, in that both settings can accommodate feedback from an arbitrary subset of experts on each round. However, our model also accommodates partial feedback at the single-expert level, by allowing non-trivial lower bounds on each loss. △ Less

Submitted 17 December, 2020; originally announced December 2020.

Iterative Methods for Computing Eigenvectors of Nonlinear Operators

Authors: Guy Gilboa

Abstract: In this chapter we are examining several iterative methods for solving nonlinear eigenvalue problems. These arise in variational image-processing, graph partition and classification, nonlinear physics and more. The canonical eigenproblem we solve is $T(u)=λu$, where $T:\R^n\to \R^n$ is some bounded nonlinear operator. Other variations of eigenvalue problems are also discussed. We present a progres… ▽ More In this chapter we are examining several iterative methods for solving nonlinear eigenvalue problems. These arise in variational image-processing, graph partition and classification, nonlinear physics and more. The canonical eigenproblem we solve is $T(u)=λu$, where $T:\R^n\to \R^n$ is some bounded nonlinear operator. Other variations of eigenvalue problems are also discussed. We present a progression of 5 algorithms, coauthored in recent years by the author and colleagues. Each algorithm attempts to solve a unique problem or to improve the theoretical foundations. The algorithms can be understood as nonlinear PDE's which converge to an eigenfunction in the continuous time domain. This allows a unique view and understanding of the discrete iterative process. Finally, it is shown how to evaluate numerically the results, along with some examples and insights related to priors of nonlinear denoisers, both classical algorithms and ones based on deep networks. △ Less

Submitted 6 October, 2020; originally announced October 2020.

Adaptive LiDAR Sampling and Depth Completion using Ensemble Variance

Authors: Eyal Gofer, Shachar Praisler, Guy Gilboa

Abstract: This work considers the problem of depth completion, with or without image data, where an algorithm may measure the depth of a prescribed limited number of pixels. The algorithmic challenge is to choose pixel positions strategically and dynamically to maximally reduce overall depth estimation error. This setting is realized in daytime or nighttime depth completion for autonomous vehicles with a pr… ▽ More This work considers the problem of depth completion, with or without image data, where an algorithm may measure the depth of a prescribed limited number of pixels. The algorithmic challenge is to choose pixel positions strategically and dynamically to maximally reduce overall depth estimation error. This setting is realized in daytime or nighttime depth completion for autonomous vehicles with a programmable LiDAR. Our method uses an ensemble of predictors to define a sampling probability over pixels. This probability is proportional to the variance of the predictions of ensemble members, thus highlighting pixels that are difficult to predict. By additionally proceeding in several prediction phases, we effectively reduce redundant sampling of similar pixels. Our ensemble-based method may be implemented using any depth-completion learning algorithm, such as a state-of-the-art neural network, treated as a black box. In particular, we also present a simple and effective Random Forest-based algorithm, and similarly use its internal ensemble in our design. We conduct experiments on the KITTI dataset, using the neural network algorithm of Ma et al. and our Random Forest based learner for implementing our method. The accuracy of both implementations exceeds the state of the art. Compared with a random or grid sampling pattern, our method allows a reduction by a factor of 4-10 in the number of measurements required to attain the same accuracy. △ Less

Submitted 5 October, 2021; v1 submitted 27 July, 2020; originally announced July 2020.

Comments: Accepted for publication in IEEE Transactions on Image Processing. For associated examples, see https://www.vision-and-sensing.com/post/adaptive-lidar-sampling-and-depth-completion-using-ensemble-variance-new-publication

Modes of Homogeneous Gradient Flows

Authors: Ido Cohen, Omri Azencot, Pavel Lifshitz, Guy Gilboa

Abstract: Finding latent structures in data is drawing increasing attention in diverse fields such as image and signal processing, fluid dynamics, and machine learning. In this work we examine the problem of finding the main modes of gradient flows. Gradient descent is a fundamental process in optimization where its stochastic version is prominent in training of neural networks. Here our aim is to establish… ▽ More Finding latent structures in data is drawing increasing attention in diverse fields such as image and signal processing, fluid dynamics, and machine learning. In this work we examine the problem of finding the main modes of gradient flows. Gradient descent is a fundamental process in optimization where its stochastic version is prominent in training of neural networks. Here our aim is to establish a consistent theory for gradient flows $ψ_t = P(ψ)$, where $P$ is a nonlinear homogeneous operator. Our proposed framework stems from analytic solutions of homogeneous flows, previously formalized by Cohen-Gilboa, where the initial condition $ψ_0$ admits the nonlinear eigenvalue problem $P(ψ_0)=λψ_0 $. We first present an analytic solution for \ac{DMD} in such cases. We show an inherent flaw of \ac{DMD}, which is unable to recover the essential dynamics of the flow. It is evident that \ac{DMD} is best suited for homogeneous flows of degree one. We propose an adaptive time sampling scheme and show its dynamics are analogue to homogeneous flows of degree one with a fixed step size. Moreover, we adapt \ac{DMD} to yield a real spectrum, using symmetric matrices. Our analytic solution of the proposed scheme recovers the dynamics perfectly and yields zero error. We then proceed to show that in the general case the orthogonal modes $\{ φ_i \}$ are approximately nonlinear eigenfunctions $P(φ_i) \approxλ_i φ_i $. We formulate Orthogonal Nonlinear Spectral decomposition (\emph{OrthoNS}), which recovers the essential latent structures of the gradient descent process. Definitions for spectrum and filtering are given, and a Parseval-type identity is shown. △ Less

Submitted 28 December, 2020; v1 submitted 3 July, 2020; originally announced July 2020.

Comments: For further details https://idoc.webgr.technion.ac.il/ https://www.vision-and-sensing.com/

Deeply Learned Spectral Total Variation Decomposition

Authors: Tamara G. Grossmann, Yury Korolev, Guy Gilboa, Carola-Bibiane Schönlieb

Abstract: Non-linear spectral decompositions of images based on one-homogeneous functionals such as total variation have gained considerable attention in the last few years. Due to their ability to extract spectral components corresponding to objects of different size and contrast, such decompositions enable filtering, feature transfer, image fusion and other applications. However, obtaining this decomposit… ▽ More Non-linear spectral decompositions of images based on one-homogeneous functionals such as total variation have gained considerable attention in the last few years. Due to their ability to extract spectral components corresponding to objects of different size and contrast, such decompositions enable filtering, feature transfer, image fusion and other applications. However, obtaining this decomposition involves solving multiple non-smooth optimisation problems and is therefore computationally highly intensive. In this paper, we present a neural network approximation of a non-linear spectral decomposition. We report up to four orders of magnitude ($\times 10,000$) speedup in processing of mega-pixel size images, compared to classical GPU implementations. Our proposed network, TVSpecNET, is able to implicitly learn the underlying PDE and, despite being entirely data driven, inherits invariances of the model based transform. To the best of our knowledge, this is the first approach towards learning a non-linear spectral decomposition of images. Not only do we gain a staggering computational advantage, but this approach can also be seen as a step towards studying neural networks that can decompose an image into spectral components defined by a user rather than a handcrafted functional. △ Less

Submitted 21 October, 2020; v1 submitted 17 June, 2020; originally announced June 2020.

Nonlinear Power Method for Computing Eigenvectors of Proximal Operators and Neural Networks

Authors: Leon Bungert, Ester Hait-Fraenkel, Nicolas Papadakis, Guy Gilboa

Abstract: Neural networks have revolutionized the field of data science, yielding remarkable solutions in a data-driven manner. For instance, in the field of mathematical imaging, they have surpassed traditional methods based on convex regularization. However, a fundamental theory supporting the practical applications is still in the early stages of development. We take a fresh look at neural networks and e… ▽ More Neural networks have revolutionized the field of data science, yielding remarkable solutions in a data-driven manner. For instance, in the field of mathematical imaging, they have surpassed traditional methods based on convex regularization. However, a fundamental theory supporting the practical applications is still in the early stages of development. We take a fresh look at neural networks and examine them via nonlinear eigenvalue analysis. The field of nonlinear spectral theory is still emerging, providing insights about nonlinear operators and systems. In this paper we view a neural network as a complex nonlinear operator and attempt to find its nonlinear eigenvectors. We first discuss the existence of such eigenvectors and analyze the kernel of ReLU networks. Then we study a nonlinear power method for generic nonlinear operators. For proximal operators associated to absolutely one-homogeneous convex regularization functionals, we can prove convergence of the method to an eigenvector of the proximal operator. This motivates us to apply a nonlinear method to networks which are trained to act similarly as a proximal operator. In order to take the non-homogeneity of neural networks into account we define a modified version of the power method. We perform extensive experiments for different proximal operators and on various shallow and deep neural networks designed for image denoising. Proximal eigenvectors will be used for geometric analysis of graphs, as clustering or the computation of distance functions. For simple neural nets, we observe the influence of training data on the eigenvectors. For state-of-the-art denoising networks, we show that eigenvectors can be interpreted as (un)stable modes of the network, when contaminated with noise or other degradations. △ Less

Submitted 19 April, 2021; v1 submitted 10 March, 2020; originally announced March 2020.

Comments: Accepted for publication in SIAM Journal on Imaging Sciences

MSC Class: 65H17; 47J10

Journal ref: SIAM Journal on Imaging Sciences, 14(3), 1114-1148, 2021

Unsupervised Enhancement of Real-World Depth Images Using Tri-Cycle GAN

Authors: Alona Baruhov, Guy Gilboa

Abstract: Low quality depth poses a considerable challenge to computer vision algorithms. In this work we aim to enhance highly degraded, real-world depth images acquired by a low-cost sensor, for which an analytical noise model is unavailable. In the absence of clean ground-truth, we approach the task as an unsupervised domain-translation between the low-quality sensor domain and a high-quality sensor doma… ▽ More Low quality depth poses a considerable challenge to computer vision algorithms. In this work we aim to enhance highly degraded, real-world depth images acquired by a low-cost sensor, for which an analytical noise model is unavailable. In the absence of clean ground-truth, we approach the task as an unsupervised domain-translation between the low-quality sensor domain and a high-quality sensor domain, represented using two unpaired training sets. We employ the highly-successful Cycle-GAN to this task, but find it to perform poorly in this case. Identifying the sources of the failure, we introduce several modifications to the framework, including a larger generator architecture, depth-specific losses that take into account missing pixels, and a novel Tri-Cycle loss which promotes information-preservation while addressing the asymmetry between the domains. We show that the resulting framework dramatically improves over the original Cycle-GAN both visually and quantitatively, extending its applicability to more challenging and asymmetric translation tasks. △ Less

Submitted 11 January, 2020; originally announced January 2020.

PhIT-Net: Photo-consistent Image Transform for Robust Illumination Invariant Matching

Authors: Damian Kaliroff, Guy Gilboa

Abstract: We propose a new and completely data-driven approach for generating a photo-consistent image transform. We show that simple classical algorithms which operate in the transform domain become extremely resilient to illumination changes. This considerably improves matching accuracy, outperforming the use of state-of-the-art invariant representations as well as new matching methods based on deep featu… ▽ More We propose a new and completely data-driven approach for generating a photo-consistent image transform. We show that simple classical algorithms which operate in the transform domain become extremely resilient to illumination changes. This considerably improves matching accuracy, outperforming the use of state-of-the-art invariant representations as well as new matching methods based on deep features. The transform is obtained by training a neural network with a specialized triplet loss, designed to emphasize actual scene changes while attenuating illumination changes. The transform yields an illumination invariant representation, structured as an image map, which is highly flexible and can be easily used for various tasks. △ Less

Submitted 24 October, 2021; v1 submitted 28 November, 2019; originally announced November 2019.

Comments: Paper accepted for publication at BMVC 2021. This version has the same content as in the published version, including the supplementary material

Revealing Stable and Unstable Modes of Generic Denoisers through Nonlinear Eigenvalue Analysis

Authors: Ester Hait-Fraenkel, Guy Gilboa

Abstract: In this paper, we propose to analyze stable and unstable modes of generic image denoisers through nonlinear eigenvalue analysis. We attempt to find input images for which the output of a black-box denoiser is proportional to the input. We treat this as a nonlinear eigenvalue problem. This has potentially wide implications, since most image processing algorithms can be viewed as generic nonlinear o… ▽ More In this paper, we propose to analyze stable and unstable modes of generic image denoisers through nonlinear eigenvalue analysis. We attempt to find input images for which the output of a black-box denoiser is proportional to the input. We treat this as a nonlinear eigenvalue problem. This has potentially wide implications, since most image processing algorithms can be viewed as generic nonlinear operators. We introduce a generalized nonlinear power-method to solve eigenproblems for such black-box operators. Using this method we reveal stable modes of nonlinear denoisers. These modes are optimal inputs for the denoiser, achieving superior PSNR in noise removal. Analogously to the linear case (low-pass-filter), such stable modes are eigenfunctions corresponding to large eigenvalues, characterized by large piece-wise-smooth structures. We also provide a method to generate the complementary, most unstable modes, which the denoiser suppresses strongly. These modes are textures with small eigenvalues. We validate the method using total-variation (TV) and demonstrate it on the EPLL denoiser (Zoran-Weiss). Finally, we suggest an encryption-decryption application. △ Less

Submitted 6 July, 2020; v1 submitted 12 September, 2019; originally announced September 2019.

Introducing the p-Laplacian Spectra

Authors: Ido Cohen, Guy Gilboa

Abstract: In this work we develop a nonlinear decomposition, associated with nonlinear eigenfunctions of the p-Laplacian for p \in (1, 2). With this decomposition we can process signals of different degrees of smoothness. We first analyze solutions of scale spaces, generated by γ-homogeneous operators, γ \in R. An analytic solution is formulated when the scale space is initialized with a nonlinear eigenfunc… ▽ More In this work we develop a nonlinear decomposition, associated with nonlinear eigenfunctions of the p-Laplacian for p \in (1, 2). With this decomposition we can process signals of different degrees of smoothness. We first analyze solutions of scale spaces, generated by γ-homogeneous operators, γ \in R. An analytic solution is formulated when the scale space is initialized with a nonlinear eigenfunction of the respective operator. We show that the flow is extinct in finite time for γ \in [0, 1). A main innovation in this study is concerned with operators of fractional homogeneity, which require the mathematical framework of fractional calculus. The proposed transform rigorously defines the notions of decomposition, reconstruction, filtering and spectrum. The theory is applied to the p-Laplacian operator, where the tools developed in this framework are demonstrated. Keywords: Nonlinear spectra, filtering, shape preserving flows, p-Laplacian, nonlinear eigenfunctions. △ Less

Submitted 16 September, 2019; originally announced September 2019.

Optoacoustic Model-Based Inversion Using Anisotropic Adaptive Total-Variation Regularization

Authors: Shai Biton, Nadav Arbel, Gilad Drozdov, Guy Gilboa, Amir Rosenthal

Abstract: In optoacoustic tomography, image reconstruction is often performed with incomplete or noisy data, leading to reconstruction errors. Significant improvement in reconstruction accuracy may be achieved in such cases by using nonlinear regularization schemes, such as total-variation minimization and $L_1$-based sparsity-preserving schemes. In this paper, we introduce a new framework for optoacoustic… ▽ More In optoacoustic tomography, image reconstruction is often performed with incomplete or noisy data, leading to reconstruction errors. Significant improvement in reconstruction accuracy may be achieved in such cases by using nonlinear regularization schemes, such as total-variation minimization and $L_1$-based sparsity-preserving schemes. In this paper, we introduce a new framework for optoacoustic image reconstruction based on adaptive anisotropic total-variation regularization, which is more capable of preserving complex boundaries than conventional total-variation regularization. The new scheme is demonstrated in numerical simulations on blood-vessel images \textcolor{black} {as well as on experimental data} and is shown to be more capable than the total-variation-$L_1$ scheme in enhancing image contrast. △ Less

Submitted 7 August, 2019; originally announced August 2019.

Image-Guided Depth Sampling and Reconstruction

Authors: Adam Wolff, Shachar Praisler, Ilya Tcenov, Guy Gilboa

Abstract: Depth acquisition, based on active illumination, is essential for autonomous and robotic navigation. LiDARs (Light Detection And Ranging) with mechanical, fixed, sampling templates are commonly used in today's autonomous vehicles. An emerging technology, based on solid-state depth sensors, with no mechanical parts, allows fast, adaptive, programmable scans. In this paper, we investigate the topi… ▽ More Depth acquisition, based on active illumination, is essential for autonomous and robotic navigation. LiDARs (Light Detection And Ranging) with mechanical, fixed, sampling templates are commonly used in today's autonomous vehicles. An emerging technology, based on solid-state depth sensors, with no mechanical parts, allows fast, adaptive, programmable scans. In this paper, we investigate the topic of adaptive, image-driven, sampling and reconstruction strategies. First, we formulate a piece-wise linear depth model with several tolerance parameters and estimate its validity for indoor and outdoor scenes. Our model and experiments predict that, in the optimal case, about 20-60 piece-wise linear structures can approximate well a depth map. This translates to a depth-to-image sampling ratio of about 1/1200. We propose a simple, generic, sampling and reconstruction algorithm, based on super-pixels. We reach a sampling rate which is still far from the optimal case. However, our sampling improves grid and random sampling, consistently, for a wide variety of reconstruction methods. Moreover, our proposed reconstruction achieves state-of-the-art results, compared to image-guided depth completion algorithms, reducing the required sampling rate by a factor of 3-4. A single-pixel depth camera built in our lab illustrates the concept. △ Less

Submitted 4 August, 2019; originally announced August 2019.

Adaptive Anisotropic Total Variation - A Nonlinear Spectral Analysis

Authors: Shai Biton, Guy Gilboa

Abstract: A fundamental concept in solving inverse problems is the use of regularizers, which yield more physical and less-oscillatory solutions. Total variation (TV) has been widely used as an edge-preserving regularizer. However, objects are often over-regularized by TV, becoming blob-like convex structures of low curvature. This phenomenon was explained mathematically in the analysis of Andreau et al. Th… ▽ More A fundamental concept in solving inverse problems is the use of regularizers, which yield more physical and less-oscillatory solutions. Total variation (TV) has been widely used as an edge-preserving regularizer. However, objects are often over-regularized by TV, becoming blob-like convex structures of low curvature. This phenomenon was explained mathematically in the analysis of Andreau et al. They have shown that a TV regularizer can spatially preserve perfectly sets which are nonlinear eigenfunctions of the form $λu \in \partial J_{TV}(u)$, where $\partial J_{TV}(u)$ is the TV subdifferential. For TV, these shapes are convex sets of low-curvature. A compelling approach to better preserve structures is to use anisotropic functionals, which adapt the regularization in an image-driven manner, with strong regularization along edges and low across them. This follows earlier ideas of Weickert on anisotropic diffusion, which do not stem directly from functional minimization. Adaptive anisotropic TV (A$^2$TV) was successfully used in several studies in the past decade. However, until now there is no theory formulating the type of structures which can be perfectly preserved. In this study we address this question. We rely on a recently developed theory of Burger et al on nonlinear spectral analysis of one-homogeneous functionals. We have that eigenfunction sets, admitting $λu \in \partial J_{A^2TV}(u)$, are perfectly preserved under A$^2$TV-flow or minimization with $L^2$ square fidelity. We thus investigate these eigenfunctions theoretically and numerically. We prove non-convex sets can be eigenfunctions in certain conditions and provide numerical results which characterize well the relations between the degree of local anisotropy of the functional and the admitted maximal curvature.... △ Less

Submitted 27 November, 2018; originally announced November 2018.

Learning Filter Functions in Regularisers by Minimising Quotients

Authors: Martin Benning, Guy Gilboa, Joana Sarah Grah, Carola-Bibiane Schönlieb

Abstract: Learning approaches have recently become very popular in the field of inverse problems. A large variety of methods has been established in recent years, ranging from bi-level learning to high-dimensional machine learning techniques. Most learning approaches, however, only aim at fitting parametrised models to favourable training data whilst ignoring misfit training data completely. In this paper,… ▽ More Learning approaches have recently become very popular in the field of inverse problems. A large variety of methods has been established in recent years, ranging from bi-level learning to high-dimensional machine learning techniques. Most learning approaches, however, only aim at fitting parametrised models to favourable training data whilst ignoring misfit training data completely. In this paper, we follow up on the idea of learning parametrised regularisation functions by quotient minimisation as established in [3]. We extend the model therein to include higher-dimensional filter functions to be learned and allow for fit- and misfit-training data consisting of multiple functions. We first present results resembling behaviour of well-established derivative-based sparse regularisers like total variation or higher-order total variation in one-dimension. Our second and main contribution is the introduction of novel families of non-derivative-based regularisers. This is accomplished by learning favourable scales and geometric properties while at the same time avoiding unfavourable ones. △ Less

Submitted 4 April, 2017; originally announced April 2017.

Nonlinear Spectral Image Fusion

Authors: Martin Benning, Michael Möller, Raz Z. Nossek, Martin Burger, Daniel Cremers, Guy Gilboa, Carola-Bibiane Schönlieb

Abstract: In this paper we demonstrate that the framework of nonlinear spectral decompositions based on total variation (TV) regularization is very well suited for image fusion as well as more general image manipulation tasks. The well-localized and edge-preserving spectral TV decomposition allows to select frequencies of a certain image to transfer particular features, such as wrinkles in a face, from one… ▽ More In this paper we demonstrate that the framework of nonlinear spectral decompositions based on total variation (TV) regularization is very well suited for image fusion as well as more general image manipulation tasks. The well-localized and edge-preserving spectral TV decomposition allows to select frequencies of a certain image to transfer particular features, such as wrinkles in a face, from one image to another. We illustrate the effectiveness of the proposed approach in several numerical experiments, including a comparison to the competing techniques of Poisson image editing, linear osmosis, wavelet fusion and Laplacian pyramid fusion. We conclude that the proposed spectral TV image decomposition framework is a valuable tool for semi- and fully-automatic image editing and fusion. △ Less

Submitted 23 March, 2017; originally announced March 2017.

Comments: 13 pages, 9 figures, submitted to SSVM conference proceedings 2017

MSC Class: 35P30; 62H35; 65M70; 94A08 ACM Class: G.1.3; G.1.6; G.1.8; I.4.0; I.4.5

Blind Facial Image Quality Enhancement using Non-Rigid Semantic Patches

Authors: Ester Hait, Guy Gilboa

Abstract: We propose to combine semantic data and registration algorithms to solve various image processing problems such as denoising, super-resolution and color-correction. It is shown how such new techniques can achieve significant quality enhancement, both visually and quantitatively, in the case of facial image enhancement. Our model assumes prior high quality data of the person to be processed, but no… ▽ More We propose to combine semantic data and registration algorithms to solve various image processing problems such as denoising, super-resolution and color-correction. It is shown how such new techniques can achieve significant quality enhancement, both visually and quantitatively, in the case of facial image enhancement. Our model assumes prior high quality data of the person to be processed, but no knowledge of the degradation model. We try to overcome the classical processing limits by using semantically-aware patches, with adaptive size and location regions of coherent structure and context, as building blocks. The method is demonstrated on the problem of cellular photography enhancement of dark facial images for different identities, expressions and poses. △ Less

Submitted 30 April, 2017; v1 submitted 27 September, 2016; originally announced September 2016.

Comments: Please see the updated published version: Hait, Ester, and Guy Gilboa. Blind Facial Image Quality Enhancement using Non-Rigid Semantic Patches. IEEE Transactions on Image Processing 26.6 (2017): 2705

Flows Generating Nonlinear Eigenfunctions

Authors: Raz Z. Nossek, Guy Gilboa

Abstract: Nonlinear variational methods have become very powerful tools for many image processing tasks. Recently a new line of research has emerged, dealing with nonlinear eigenfunctions induced by convex functionals. This has provided new insights and better theoretical understanding of convex regularization and introduced new processing methods. However, the theory of nonlinear eigenvalue problems is sti… ▽ More Nonlinear variational methods have become very powerful tools for many image processing tasks. Recently a new line of research has emerged, dealing with nonlinear eigenfunctions induced by convex functionals. This has provided new insights and better theoretical understanding of convex regularization and introduced new processing methods. However, the theory of nonlinear eigenvalue problems is still at its infancy. We present a new flow that can generate nonlinear eigenfunctions of the form $T(u)=λu$, where $T(u)$ is a nonlinear operator and $λ\in \mathbb{R} $ is the eigenvalue. We develop the theory where $T(u)$ is a subgradient element of a regularizing one-homogeneous functional, such as total-variation (TV) or total-generalized-variation (TGV). We introduce two flows: a forward flow and an inverse flow; for which the steady state solution is a nonlinear eigenfunction. The forward flow monotonically smooths the solution (with respect to the regularizer) and simultaneously increases the $L^2$ norm. The inverse flow has the opposite characteristics. For both flows, the steady state depends on the initial condition, thus different initial conditions yield different eigenfunctions. This enables a deeper investigation into the space of nonlinear eigenfunctions, allowing to produce numerically diverse examples, which may be unknown yet. In addition we suggest an indicator to measure the affinity of a function to an eigenfunction and relate it to pseudo-eigenfunctions in the linear case. △ Less

Submitted 27 September, 2016; originally announced September 2016.

Spectral Decompositions using One-Homogeneous Functionals

Authors: Martin Burger, Guy Gilboa, Michael Moeller, Lina Eckardt, Daniel Cremers

Abstract: This paper discusses the use of absolutely one-homogeneous regularization functionals in a variational, scale space, and inverse scale space setting to define a nonlinear spectral decomposition of input data. We present several theoretical results that explain the relation between the different definitions. Additionally, results on the orthogonality of the decomposition, a Parseval-type identity a… ▽ More This paper discusses the use of absolutely one-homogeneous regularization functionals in a variational, scale space, and inverse scale space setting to define a nonlinear spectral decomposition of input data. We present several theoretical results that explain the relation between the different definitions. Additionally, results on the orthogonality of the decomposition, a Parseval-type identity and the notion of generalized (nonlinear) eigenvectors closely link our nonlinear multiscale decompositions to the well-known linear filtering theory. Numerical results are used to illustrate our findings. △ Less

Submitted 12 January, 2016; originally announced January 2016.

Separation Surfaces in the Spectral TV Domain for Texture Decomposition

Authors: Dikla Horesh, Guy Gilboa

Abstract: In this paper we introduce a novel notion of separation surfaces for image decomposition. A surface is embedded in the spectral total-variation (TV) three dimensional domain and encodes a spatially-varying separation scale. The method allows good separation of textures with gradually varying pattern-size, pattern-contrast or illumination. The recently proposed total variation spectral framework is… ▽ More In this paper we introduce a novel notion of separation surfaces for image decomposition. A surface is embedded in the spectral total-variation (TV) three dimensional domain and encodes a spatially-varying separation scale. The method allows good separation of textures with gradually varying pattern-size, pattern-contrast or illumination. The recently proposed total variation spectral framework is used to decompose the image into a continuum of textural scales. A desired texture, within a scale range, is found by fitting a surface to the local maximal responses in the spectral domain. A band above and below the surface, referred to as the \textit{Texture Stratum}, defines for each pixel the adaptive scale-range of the texture. Based on the decomposition an application is proposed which can attenuate or enhance textures in the image in a very natural and visually convincing manner. △ Less

Submitted 15 November, 2015; originally announced November 2015.

Semi-Inner-Products for Convex Functionals and Their Use in Image Decomposition

Authors: Guy Gilboa

Abstract: Semi-inner-products in the sense of Lumer are extended to convex functionals. This yields a Hilbert-space like structure to convex functionals in Banach spaces. In particular, a general expression for semi-inner-products with respect to one homogeneous functionals is given. Thus one can use the new operator for the analysis of total variation and higher order functionals like total-generalized-var… ▽ More Semi-inner-products in the sense of Lumer are extended to convex functionals. This yields a Hilbert-space like structure to convex functionals in Banach spaces. In particular, a general expression for semi-inner-products with respect to one homogeneous functionals is given. Thus one can use the new operator for the analysis of total variation and higher order functionals like total-generalized-variation (TGV). Having a semi-inner-product, an angle between functions can be defined in a straightforward manner. It is shown that in the one homogeneous case the Bregman distance can be expressed in terms of this newly defined angle. In addition, properties of the semi-inner-product of nonlinear eigenfunctions induced by the functional are derived. We use this construction to state a sufficient condition for a perfect decomposition of two signals and suggest numerical measures which indicate when those conditions are approximately met. △ Less

Submitted 15 November, 2015; originally announced November 2015.

Nonlinear Spectral Analysis via One-homogeneous Functionals - Overview and Future Prospects

Authors: Guy Gilboa, Michael Moeller, Martin Burger

Abstract: We present in this paper the motivation and theory of nonlinear spectral representations, based on convex regularizing functionals. Some comparisons and analogies are drawn to the fields of signal processing, harmonic analysis and sparse representations. The basic approach, main results and initial applications are shown. A discussion of open problems and future directions concludes this work. We present in this paper the motivation and theory of nonlinear spectral representations, based on convex regularizing functionals. Some comparisons and analogies are drawn to the fields of signal processing, harmonic analysis and sparse representations. The basic approach, main results and initial applications are shown. A discussion of open problems and future directions concludes this work. △ Less

Submitted 5 October, 2015; originally announced October 2015.

MSC Class: 35A15; 35A22; 68U10; 35P30

Spectral Representations of One-Homogeneous Functionals

Authors: Martin Burger, Lina Eckardt, Guy Gilboa, Michael Moeller

Abstract: This paper discusses a generalization of spectral representations related to convex one-homogeneous regularization functionals, e.g. total variation or $\ell^1$-norms. Those functionals serve as a substitute for a Hilbert space structure (and the related norm) in classical linear spectral transforms, e.g. Fourier and wavelet analysis. We discuss three meaningful definitions of spectral representat… ▽ More This paper discusses a generalization of spectral representations related to convex one-homogeneous regularization functionals, e.g. total variation or $\ell^1$-norms. Those functionals serve as a substitute for a Hilbert space structure (and the related norm) in classical linear spectral transforms, e.g. Fourier and wavelet analysis. We discuss three meaningful definitions of spectral representations by scale space and variational methods and prove that (nonlinear) eigenfunctions of the regularization functionals are indeed atoms in the spectral representation. Moreover, we verify further useful properties related to orthogonality of the decomposition and the Parseval identity. The spectral transform is motivated by total variation and further developed to higher order variants. Moreover, we show that the approach can recover Fourier analysis as a special case using an appropriate $\ell^1$-type functional and discuss a coupled sparsity example. △ Less

Submitted 18 March, 2015; originally announced March 2015.