Browsing by Author "Sober, B"

Now showing 1 - 6 of 6

Open Access
Approximation of Functions over Manifolds: A Moving Least-Squares Approach
Sober, B; Aizenbud, Y; Levin, D
We present an algorithm for approximating a function defined over a $d$-dimensional manifold utilizing only noisy function values at locations sampled from the manifold with noise. To produce the approximation we do not require any knowledge regarding the manifold other than its dimension $d$. We use the Manifold Moving Least-Squares approach of (Sober and Levin 2016) to reconstruct the atlas of charts and the approximation is built on-top of those charts. The resulting approximant is shown to be a function defined over a neighborhood of a manifold, approximating the originally sampled manifold. In other words, given a new point, located near the manifold, the approximation can be evaluated directly on that point. We prove that our construction yields a smooth function, and in case of noiseless samples the approximation order is $\mathcal{O}(h^{m+1})$, where $h$ is a local density of sample parameter (i.e., the fill distance) and $m$ is the degree of a local polynomial approximation, used in our algorithm. In addition, the proposed algorithm has linear time complexity with respect to the ambient-space's dimension. Thus, we are able to avoid the computational complexity, commonly encountered in high dimensional approximations, without having to perform non-linear dimension reduction, which inevitably introduces distortions to the geometry of the data. Additionaly, we show numerical experiments that the proposed approach compares favorably to statistical approaches for regression over manifolds and show its potential.
Open Access
Artificial intelligence for art investigation: Meeting the challenge of separating x-ray images of the Ghent Altarpiece.
(Science advances, 2019-08-30) Sabetsarvestani, Z; Sober, B; Higgitt, C; Daubechies, I; Rodrigues, MRD
X-ray images of polyptych wings, or other artworks painted on both sides of their support, contain in one image content from both paintings, making them difficult for experts to "read." To improve the utility of these x-ray images in studying these artworks, it is desirable to separate the content into two images, each pertaining to only one side. This is a difficult task for which previous approaches have been only partially successful. Deep neural network algorithms have recently achieved remarkable progress in a wide range of image analysis and other challenging tasks. We, therefore, propose a new self-supervised approach to this x-ray separation, leveraging an available convolutional neural network architecture; results obtained for details from the Adam and Eve panels of the Ghent Altarpiece spectacularly improve on previous attempts.
Open Access
Computer aided restoration of handwritten character strokes
(CAD Computer Aided Design, 2017-08-01) Sober, B; Levin, D
© 2017 Elsevier Ltd This work suggests a new variational approach to the task of computer aided segmentation and restoration of incomplete characters, residing in a highly noisy document image. We model character strokes as the movement of a pen with a varying radius. Following this model, in order to fit the digital image, a cubic spline representation is being utilized to perform gradient descent steps, while maintaining interpolation at some initial (manually sampled) points. The proposed algorithm was used in the process of restoring approximately 1000 ancient Hebrew characters (dating to ca. 8th–7th century BCE), some of which are presented herein and show that the algorithm yields plausible results when applied on deteriorated documents.
Open Access
Expression of Fractals Through Neural Network Functions
Dym, N; Sober, B; Daubechies, I
To help understand the underlying mechanisms of neural networks (NNs), several groups have, in recent years, studied the number of linear regions $\ell$ of piecewise linear functions generated by deep neural networks (DNN). In particular, they showed that $\ell$ can grow exponentially with the number of network parameters $p$, a property often used to explain the advantages of DNNs over shallow NNs in approximating complicated functions. Nonetheless, a simple dimension argument shows that DNNs cannot generate all piecewise linear functions with $\ell$ linear regions as soon as $\ell > p$. It is thus natural to seek to characterize specific families of functions with $\ell$ linear regions that can be constructed by DNNs. Iterated Function Systems (IFS) generate sequences of piecewise linear functions $F_k$ with a number of linear regions exponential in $k$. We show that, under mild assumptions, $F_k$ can be generated by a NN using only $\mathcal{O}(k)$ parameters. IFS are used extensively to generate, at low computational cost, natural-looking landscape textures in artificial images. They have also been proposed for compression of natural images, albeit with less commercial success. The surprisingly good performance of this fractal-based compression suggests that our visual system may lock in, to some extent, on self-similarities in images. The combination of this phenomenon with the capacity, demonstrated here, of DNNs to efficiently approximate IFS may contribute to the success of DNNs, particularly striking for image processing tasks, as well as suggest new algorithms for representing self similarities in images based on the DNN mechanism.
Open Access
Literacy in Judah and Israel algorithmic and forensic examination of the Arad and Samaria Ostraca
(Near Eastern Archaeology, 2021-06-01) Faigenbaum-Golovin, S; Shaus, A; Sober, B; Gerber, Y; Turkel, E; Piasetzky, E; Finkelstein, I
A highly discussed issue in the fields of Hebrew epigraphy and biblical research is the level of literacy in the Iron Age kingdoms of Israel and Judah (Rollston 2010; Davies and Römer 2013; Schmidt 2015). Treating this topic using biblical texts, for example, the references to scribes at the time of a given monarch, may lead to circular argumentation: The reality behind a given account may reflect the time of the authors, who could have lived centuries later and retrojected their own situation back onto earlier history. A preferable methodology is to consider the material evidence—the corpora of Iron Age Hebrew ostraca from archaeological excavations. The idea is to use algorithmic and forensic methods to distinguish between handwritings and thus the number of authors in a given corpus.
Open Access
Potential contrast - A new image quality measure
(IS and T International Symposium on Electronic Imaging Science and Technology, 2017-01-01) Shaus, A; Faigenbaum-Golovin, S; Sober, B; Turkel, E
This paper suggests a new quality measure of an image, pertaining to its contrast. Several contrast measures exist in the current research. However, due to the abundance of Image Processing software solutions, the perceived (or measured) image contrast can be misleading, as the contrast may be significantly enhanced by applying grayscale transformations. Therefore, the real challenge, which was not dealt with in the previous literature, is measuring the contrast of an image taking into account all possible grayscale transformations, leading to the best "potential" contrast. Hence, we suggest an alternative "Potential Contrast" measure, based on sampled populations of foreground and background pixels (e.g. scribbles or saliency-based criteria). An exact and efficient implementation of this measure is found analytically. The new methodology is tested and is shown to be invariant to invertible grayscale transformations.