2007 2008 2009 2010 2011 2012 2013 2014 2015 2017
2017
On Visibility & Empty-Region Graphs,
Sagi Katz and Ayellet Tal.
SMI 2017.
Abstract:
Empty-Region graphs are well-studied in Computer Graphics, Geometric Modeling, Computational Geometry, as well as in Robotics and Computer Vision. The vertices of these graphs are points in space, and two vertices are connected by an arc if there exists an empty region of a certain shape and size between them. In most of the graphs discussed in the literature, the empty region is assumed to be a circle or the union/intersection of circles. In this paper we propose a new type of empty-region graphs— the gamma-visibility graph. This graph can accommodate a variety of shapes of empty regions and may be defined in any dimension. Interestingly, we will show that commonly-used shapes are a special case of our graph. In this sense, our graph generalizes some empty-region graphs. Though this paper is mostly theoretical, it may have practical implication—the numerous applications that make use of empty-region graphs would be able to select the best shape that suits the problem at hand.

 

2015
On the Visibility of Point Clouds,
Sagi Katz and Ayellet Tal.
ICCV 2015 (ORAL).
Abstract:
Is it possible to determine the visible subset of points directly from a given point cloud? Interestingly, in [7] it was shown that this is indeed the case—despite the fact that points cannot occlude each other, this task can be performed without surface reconstruction or normal estimation. The operator is very simple—it first transforms the points to a new domain and then constructs the convex hull in that domain. Points that lie on the convex hull of the transformed set of points are the images of the visible points. This operator found numerous applications in computer vision, including face reconstruction, keypoint detection, finding the best viewpoints, reduction of points, and many more. The current paper addresses a fundamental question: What properties should a transformation function satisfy, in order to be utilized in this operator? We show that three such properties are sufficient—the sign of the function, monotonicity, and a condition regarding the function’s parameter. The correctness of an algorithm that satisfies these three properties is proved. Finally, we show an interesting application of the operator—assignment of visibility-confidence score. This feature is missing from previous approaches, where a binary yes/no visibility is determined. This score can be utilized in various applications; we illustrate its use in view-dependent curvature estimation.

 

Solving Multiple Square Jigsaw Puzzles with Missing Pieces,
Genady Paikin and Ayellet Tal.
IEEE Computer Vision and Pattern Recognition (CVPR), 2015.
Abstract:
Jigsaw-puzzle solving is necessary in many applications, including biology, archaeology, and every-day life. In this paper we consider the square jigsaw puzzle problem, where the goal is to reconstruct the image from a set of non-overlapping, unordered, square puzzle parts. Our key contribution is a fast, fully-automatic, and general solver, which assumes no prior knowledge about the original image. It is general in the sense that it can handle puzzles of unknown size, with pieces of unknown orientation, and even puzzles with missing pieces. Moreover, it can handle all the above, given pieces from multiple puzzles. Through an extensive evaluation we show that our approach outperforms state-of-the-art methods on commonly-used datasets. But, it can solve puzzles that none of previous approaches could – those with missing pieces or multiple puzzles whose pieces are mixed together.

 

2014
3D shape analysis for archaeology,
Ayellet Tal.
3D Research Challenges in Cultural Heritage; Springer Berlin Heidelberg, 2014.
Abstract:
Archaeology is rapidly approaching an impasse in its ability to handle the overwhelming amount and complexity of the data gener- ated by archaeological research. In this paper, we describe some results of our e orts in developing automatic shape analysis techniques for sup- porting several fundamental tasks in archaeology. These tasks include documentation, looking for corollaries, and restoration. We assume that the input to our algorithms is 3D scans of archaeological artifacts. Given these scans, we describe three techniques of documentation, for produc- ing 3D visual descriptions of the scans, which are all non-photorealistic. We then proceed to explain our algorithm for partial similarity of 3D shapes, which can be used to query databases of shape, searching for corollaries. Finally, within restoration, we describe our results for dig- ital completion of broken 3D shapes, for reconstruction of 3D shapes based on their line drawing illustrations, and for restoration of colors on 3D objects. We believe that when digital archaeological reports will spread around the globe and scanned 3D representations replace the 2D ones, our methods will not only accelerate, but also improve the results obtained by the current manual procedures.

 

How to Evaluate Foreground Maps?,
Ran Margolin, Lihi Zelnik-Manor, Ayellet Tal.
CVPR 2014.
Abstract:
The output of many algorithms in computer-vision is either non-binary maps or binary maps (e.g., salient object detection and object segmentation). Several measures have been suggested to evaluate the accuracy of these foreground maps. In this paper, we show that the most commonly-used measures for evaluating both non-binary maps and binary maps do not always provide a reliable evaluation. This includes the Area-Under-the-Curve measure, the Average- Precision measure, the F -measure, and the evaluation measure of the PASCAL VOC segmentation challenge. We start by identifying three causes of inaccurate evaluation. We then propose a new measure that amends these flaws. An appealing property of our measure is being an intuitive generalization of the F -measure. Finally we propose four meta-measures to compare the adequacy of evaluation measures. We show via experiments that our novel measure is preferable.

 

2013
Paper Of The Month
Pattern-Driven Colorization of 3D Surfaces,
George Leifman and Ayellet Tal.
CVPR 2013.
Abstract:
Colorization refers to the process of adding color to black & white images or videos. This paper extends the term to handle surfaces in three dimensions. This is important for applications in which the colors of an object need to be restored and no relevant image exists for texturing it. We focus on surfaces with patterns and propose a novel algorithm for adding colors to these surfaces. The user needs only scribble a few color strokes on one instance of each pattern, and the system proceeds to automatically colorize the whole surface. For this scheme to work, we address not only the problem of colorization, but also the problem of pattern detection on surfaces.

 

SIFTpack: A Compact Representation for Efficient SIFT Matching,
A. Gilinsky and L. Zelnik-Manor.
ICCV 2013.
Abstract:
What makes an object salient? Most previous work assert that distintness is the dominating factor. The difference between the various algorithms is in the way they compute distinctness. Some focus on the patterns, others on the colors, and several add high-level cues and priors. We propose a simple, yet powerful, algorithm that integrates these three factors. Our key contribution is a novel and fast approach to compute pattern distinctness. We rely on the inner statistics of the patches in the image for identifying unique patterns. We provide an extensive evaluation and show that our approach outperforms all state-of-the-art methods on the five most commonly-used datasets.

 

Video Inlays: A System for User-Friendly Matchmove,
D. Rudoy and L. Zelnik-Manor.
VRST 2013.
Abstract:
What makes an object salient? Most previous work assert that distintness is the dominating factor. The difference between the various algorithms is in the way they compute distinctness. Some focus on the patterns, others on the colors, and several add high-level cues and priors. We propose a simple, yet powerful, algorithm that integrates these three factors. Our key contribution is a novel and fast approach to compute pattern distinctness. We rely on the inner statistics of the patches in the image for identifying unique patterns. We provide an extensive evaluation and show that our approach outperforms all state-of-the-art methods on the five most commonly-used datasets.

 

Learning video saliency from human gaze using candidate selection,
D. Rudoy, D.B Goldman, E. Shechtman and L. Zelnik-Manor.
CVPR 2013.
Abstract:
What makes an object salient? Most previous work assert that distintness is the dominating factor. The difference between the various algorithms is in the way they compute distinctness. Some focus on the patterns, others on the colors, and several add high-level cues and priors. We propose a simple, yet powerful, algorithm that integrates these three factors. Our key contribution is a novel and fast approach to compute pattern distinctness. We rely on the inner statistics of the patches in the image for identifying unique patterns. We provide an extensive evaluation and show that our approach outperforms all state-of-the-art methods on the five most commonly-used datasets.

 

What Makes a Patch Distinct?,
Ran Margolin, Ayellet Tal, Lihi Zelnik-Manor.
CVPR 2013.
Abstract:
What makes an object salient? Most previous work assert that distintness is the dominating factor. The difference between the various algorithms is in the way they compute distinctness. Some focus on the patterns, others on the colors, and several add high-level cues and priors. We propose a simple, yet powerful, algorithm that integrates these three factors. Our key contribution is a novel and fast approach to compute pattern distinctness. We rely on the inner statistics of the patches in the image for identifying unique patterns. We provide an extensive evaluation and show that our approach outperforms all state-of-the-art methods on the five most commonly-used datasets.

 

Saliency Detection in Large Point Sets,
Elizabeth Shtrom, George Leifman and Ayellet Tal.
ICCV 2013.
Abstract:
While saliency in images has been extensively studied in recent years, there is very little work on saliency of point sets. This is despite the fact that point sets and range data are becoming ever more widespread and have myriad applications. In this paper we present an algorithm for detecting the salient points in unorganized 3D point sets. Our algorithm is designed to cope with extremely large sets, which may contain tens of millions of points. Such data is typical of urban scenes, which have recently become commonly available on the web. No previous work has handled such data. For general data sets, we show that our results are competitive with those of saliency detections of surfaces, although we do not have any connectivity information. We demonstrate the utility of our algorithm in two applications: producing a set of the most informative viewpoints and suggesting an informative city tour given a city scan.

 

Improving the Visual Comprehension of Point Sets,
Sagi Katz and Ayellet Tal.
CVPR 2013.
Abstract:
Point sets are the standard output of many 3D scanning systems and depth cameras. Presenting the set of points as is, might hide the prominent features of the object from which the points are sampled. Our goal is to reduce the number of points in a point set, for improving the visual comprehension from a given viewpoint. This is done by controlling the density of the reduced point set, so as to create bright regions (low density) and dark regions (high density), producing an effect of shading. This data reduction is achieved by leveraging a limitation of a solution to the classical problem of determining visibility from a viewpoint. In addition, we introduce a new dual problem, for determining visibility of a point from infinity, and show how a limitation of its solution can be leveraged in a similar way.

 

Computer-Based, Automatic Recording and Illustration of Complex Archaeological Artifacts,
Ayelet Gilboa, Ayellet Tal, Ilan Shimshoni, and Michael Kolomenkin.
Journal of Archaeological Science, 2013.
Abstract:
We report on the development of a computerized automatic system to illustrate complex archaeological objects. The illustrations are based on 3D scans of the artifacts. The 3D models can be automatically translated, by new algorithms speci cally designed for this purpose, into 3D or 2D line drawings; into colored images that emphasize the salient shape attributes of the artifacts and of the 3D designs on them; and to images that enhance faint/eroded designs that are otherwise dicult to discern. These illustrations are intended to replace traditional, manual drawings, which are very expensive to produce and not accurate enough. Our illustrations also provide a better visualization tool than the 3D models themselves. Though 3D scanning already improves the visibility of objects and their features, it does not suce for rapid visual recognition. Our system generates efcient, objective, accurate and simpli ed representations of complex objects and the designs on them from any number of required views.

 

2012
On SIFTs and their Scales,
T. Hassner, V. Mayzels and L. Zelnik-Manor.
CVPR 2012.
Abstract:
Scale invariant feature detectors often find stable scales in only a few image pixels. Consequently, methods for feature matching typically choose one of two extreme options: matching a sparse set of scale invariant features, or dense matching using arbitrary scales. In this paper we turn our attention to the overwhelming majority of pixels, those where stable scales are not found by standard techniques. We ask, is scale-selection necessary for these pixels, when dense, scale-invariant matching is required and if so, how can it be achieved? We make the following contributions: (i) We show that features computed over different scales, even in low-contrast areas, can be different; selecting a single scale, arbitrarily or otherwise, may lead to poor matches when the images have different scales. (ii)We show that representing each pixel as a set of SIFTs, extracted at multiple scales, allows for far better matches than singlescale descriptors, but at a computational price. Finally, (iii) we demonstrate that each such set may be accurately represented by a low-dimensional, linear subspace. A subspaceto-point mapping may further be used to produce a novel descriptor representation, the Scale-Less SIFT (SLS), as an alternative to single-scale descriptors. These claims are verified by quantitative and qualitative tests, demonstrating significant improvements over existing methods.

 

Mesh Colorization,
George Leifman and Ayellet Tal.
Computer Graphics Forum (EUROGRAPHICS) Volume 31, Issue 2, 421-430, 2012.
Abstract:
This paper proposes a novel algorithm for colorization of meshes. This is important for applications in which the model needs to be colored by just a handful of colors or when no relevant image exists for texturing the model. For instance, archaeologists argue that the great Roman or Greek statues were full of color in the days of their creation,and traces of the original colors can be found. In this case, our system lets the user scribble some desired colors in various regions of the mesh. Colorization is then formulated as a constrained quadratic optimization problem, which can be readily solved. Special care is taken to avoid color bleeding between regions, through the definition of a new direction field on meshes.

 

Surface Regions of Interest for Viewpoint Selection,
George Leifman, Elizabeth Shtrom and Ayellet Tal
IEEE Computer Vision and Pattern Recognition (CVPR), 414-421, 2012 (ORAL).
Abstract:
While the detection of the interesting regions in images has been extensively studied, relatively few papers have addressed surfaces. This paper proposes an algorithm for detecting the regions of interest of surfaces. It looks for regions that are distinct both locally and globally and accounts for the distance to the foci of attention. Many applications can utilize these regions. In this paper we explore one such application—viewpoint selection. The most informative views are those that collectively provide the most descriptive presentation of the surface. We show that our results compete favorably with the state-of-the-art results.

 

Saliency For Image Manipulation,
R. Margolin, L. Zelnik-Manor, and A. Tal
To appear in The Visual Computer, 2012.
Abstract:
Every picture tells a story. In photography, the story is portrayed by a composition of objects, commonly referred to as the subjects of the piece. Were we to remove these objects, the story would be lost. When manipulating images, either for artistic rendering or cropping, it is crucial that the story of the piece remains intact. As a result, the knowledge of the location of these prominent objects is essential. We propose an approach for saliency detection that combines previously suggested patch distinctness with an object probability map. The object probability map infers the most probable locations of the subjects of the photograph according to highly distinct salient cues. The benefits of the proposed approach are demonstrated through state-of-the-art results on common data-sets. We further show the benefit of our method in various manipulations of real world photographs while preserving their meaning.

 

Crowdsourcing Gaze Data Collection,
Dmitry Rudoy, Dan B Goldman, Eli Shechtman and Lihi Zelnik-Manor.
Collective Intelligence (CI 2012), 2012.
Abstract:
Undoubtedly, a key feature in the popularity of smartmobile devices is the numerous applications one can install. Frequently, we learn about an application we desire by seeing it on a review site, someone elses device, or a magazine. A user-friendly way to obtain this particular application could be by taking a snapshot of its corresponding icon and being directed automatically to its download link. Such a solution exists today for QR codes, which can be thought of as icons with a binary pattern. In this paper we extend this to App-icons and propose a complete system for automatic icon-scanning: it first detects the icon in a snapshot and then recognizes it. Icon scanning is a highly challenging problem due to the large variety of icons (~500K in App-Store) and background wallpapers. In addition, our system should further deal with the challenges introduced by taking pictures of a screen. Nevertheless, the novel solution proposed in this paper provides high detection and recognition rates. We test our complete icon-scanning system on icon snapshots taken by independent users, and search them within the entire set of icons in App-Store. Our success rates are high and improve significantly on other methods.Abstract

 

Icon Scanning: Towards Next Generation QR Codes,
I. Friedman and L. Zelnik-Manor
To appear in CVPR' 2012.
Abstract:
Undoubtedly, a key feature in the popularity of smartmobile devices is the numerous applications one can install. Frequently, we learn about an application we desire by seeing it on a review site, someone elses device, or a magazine. A user-friendly way to obtain this particular application could be by taking a snapshot of its corresponding icon and being directed automatically to its download link. Such a solution exists today for QR codes, which can be thought of as icons with a binary pattern. In this paper we extend this to App-icons and propose a complete system for automatic icon-scanning: it first detects the icon in a snapshot and then recognizes it. Icon scanning is a highly challenging problem due to the large variety of icons (500K in App-Store) and background wallpapers. In addition, our system should further deal with the challenges introduced by taking pictures of a screen. Nevertheless, the novel solution proposed in this paper provides high detection and recognition rates. We test our complete icon-scanning system on icon snapshots taken by independent users, and search them within the entire set of icons in App-Store. Our success rates are high and improve significantly on other methods.

 

Context-Aware Saliency Detection,
S. Goferman, L. Zelnik-Manor, and A. Tal
To appear in PAMI, 2012.
Abstract:
We propose a new type of saliency context-aware saliency which aims at detecting the image regions that represent the scene. This definition differs from previous definitions whose goal is to either identify fixation points or detect the dominant object. In accordance with our saliency definition, we present a detection algorithm which is based on four principles observed in the psychological literature. The benefits of the proposed approach are evaluated in two applications where the context of the dominant objects is just as essential as the objects themselves. In image retargeting we demonstrate that using our saliency prevents distortions in the important regions. In summarization we show that our saliency helps to produce compact, appealing, and informative summaries.

 

2011
Surface Partial Matching & Application to Archaeology,
Arik Itskovich and Ayellet Tal.
Computers & Graphics 35(2): 334-341, 2011.
Abstract:
Partial matching is a fundamental problem in shape analysis, a field that is recently gaining an increasing importance in computer graphics. This paper proposes a novel approach to performing partial matching of surfaces. Given two surfaces MA and MB, our goal is to find the best match to MA within MB. The key idea of our approach is to integrate feature-point similarity and segment similarity. Specifically, we introduce a probabilistic framework in which the segmentation and the correspondences of neighboring feature points allow us to enhance or moderate our certainty of a feature-point similarity. The utility of our algorithm is demonstrated in the domain of archaeology, where digital archiving is becoming ever more widespread. In this domain, automatic matching can serve as a worthy alternative to the expensive and time-consuming manual procedure that is used today.

 

Reconstruction of relief objects from line drawings,
Michael Kolomenkin, George Leifman, Ilan Shimshoni, and Ayellet Tal.
IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2011, 993-1000.
Abstract:
This paper addresses the problem of automatic reconstruction of a 3D relief from a line drawing on top of a given base object. Reconstruction is challenging due to four reasons ? the sparsity of the strokes, their ambiguity, their large number, and their inter-relations. Our approach is able to reconstruct a model from a complex drawing that consists of many inter-related strokes. Rather than viewing the interdependencies as a problem, we show how they can be exploited to automatically generate a good initial interpretation of the line drawing. Then, given a base and an interpretation, we propose an algorithm for reconstructing a consistent surface. The strength of our approach is demonstrated in the reconstruction of archaeological artifacts from drawings. These drawings are highly challenging, since artists created very complex and detailed descriptions of artifacts regardless of any considerations concerning their future use for shape reconstruction.

 

Incorporating Temporal Context in Bag-of-Words Models,
T. Glaser and L. Zelnik-Manor
To appear in VECTaR'11
Abstract:
Bag-of-Words (BoW) is a highly popular model for recognition, due to its robustness and simplicity. Its modeling capabilities, however, are somewhat limited since it discards the spatial and temporal order of the codewords. In this paper we propose a new model: Contextual Sequence of Words (CSoW) which incorporates temporal order into the BoW model for video representation. The temporal context is incorporated in three scales that capture different aspects of the variability between different performances of the same action. We show that using CSoW instead of BoW leads to a significant improvement in action recognition rates, on several different setups.

 

Viewpoint Selection for Human Actions,
D. Rudoy and L. Zelnik-Manor
To appear in International Journal of Computer Vision (IJCV);
Abstract:
In many scenarios a dynamic scene is filmed by multiple video cameras located at different viewing positions. Visualizing such multi-view data on a single display raises an immediate question - which cameras capture better views of the scene? Typically, (e.g. in TV broadcasts) a human producer manually selects the best view. In this paper we wish to automate this process by evaluating the quality of a view, captured by every single camera. We regard human actions as threedimensional shapes induced by their silhouettes in the space-time volume. The quality of a view is then evaluated based on features of the space-time shape, which correspond with limb visibility. Resting on these features, two view quality approaches are proposed. One is generic while the other can be trained to fit any preferred action recognition method. Our experiments show that the proposed view selection provide intuitive results which match common conventions. We further show that it improves action recognition results

 

Sensing Matrix Optimization for Block-Sparse Decoding,
L. Zelnik-Manor, K. Rosenblum and Y. C. Eldar
To appear in IEEE Transactions on Signal Processing
Abstract:
Recent work has demonstrated that using a carefully designed sensing matrix rather than a random one, can improve the performance of compressed sensing. In particular, a welldesigned sensing matrix can reduce the coherence between the atoms of the equivalent dictionary, and as a consequence, reduce the reconstruction error. In some applications, the signals of interest can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which leads to blocksparse representations. In this work, we propose a framework for sensing matrix design that improves the ability of blocksparse approximation techniques to reconstruct and classify signals. This method is based on minimizing a weighted sum of the inter-block coherence and the sub-block coherence of the equivalent dictionary. Our experiments show that the proposed algorithm significantly improves signal recovery and classification ability of the Block-OMP algorithm compared to sensing matrix optimization methods that do not employ block structure.

 

Posing to the camera: Automatic viewpoint selection for human actions,
D. Rudoy and L.Zelnik-Manor.
ACCV, 2010.
Abstract:
In many scenarios a scene is filmed by multiple video cameras located at different viewing positions. The diffculty in watching multiple views simultaneously raises an immediate question - which cameras capture better views of the dynamic scene? When one can only display a single view (e.g. in TV broadcasts) a human producer manually selects the best view. In this paper we propose a method for evaluating the quality of a view, captured by a single camera. This can be used to automate viewpoint selection. We regard human actions as three-dimensional shapes induced by their silhouettes in the space-time volume. The quality of a view is evaluated by incorporating three measures that capture the visibility of the action provided by these space-time shapes. We evaluate the proposed approach both qualitatively and quantitatively.

 

The Natural 3D Spiral,
Gur Harary and Ayellet Tal.
Computer Graphics Forum (EUROGRAPHICS) 30(2)): 237-246, 2011.
Abstract:
Logarithmic spirals are ubiquitous in nature. This paper presents a novel mathematical definition of a 3D logarithmic spiral, which provides a proper description of objects found in nature. To motivate our work, we scanned spiral-shaped objects and studied their geometric properties. We consider the extent to which the existing 3D definitions capture these properties. We identify a property that is shared by the objects we investigated and is not satisfied by the existing 3D definitions. This leads us to present our definition in which both the radius of curvature and the radius of torsion change linearly along the curve. We prove that our spiral satisfies several desirable properties, including invariance to similarity transformations, smoothness, symmetry, extensibility, and roundness. Finally, we demonstrate the utility of our curves in the modeling of several animal structures.

 

2010
Salient Edges: A Multi Scale Approach,
Michal Holtzman-Gazit, Lihi Zelnik-Manor, and Irad Yavneh.
ECCV 2010 Workshop on Vision for Cognitive Tasks.
Abstract:
Finding the salient features of an image is required by many applications such as image re-targeting, automatic cropping, object tracking, video encoding, and selective sharpening. In this paper we present a novel method for detection of salient objects' edges which combines local and regional considerations. Our method uses multiple levels of detail, and does not favor one level over another as done in other multi-scale methods. The proposed local-regional multi-level approach detects edges of salient objects and can handle highly textured images, while maintaining a low computational cost. We show empirically that these are useful for improving image abstraction results. We further provide qualitative results together with quantitative evaluation which shows that the proposed method outperforms previous work on saliency detection.

 

Piecewise 3D Euler spirals,
David Ben-Haim, Gur Harary and Ayellet Tal.
ACM-SIAM Symposium on Solid and Physical Modeling (SPM) '10, September 2010, 201-206.
Abstract:
3D Euler spirals are visually pleasing, due to their property of having their curvature and their torsion change linearly with arc-length. This paper presents a novel algorithm for fitting piecewise 3D Euler spirals to 3D curves with ^2$ continuity and torsion continuity. The algorithm can also handle sharp corners. Our piecewise representation is invariant to similarity transformations and it is close to the input curves up to an error tolerance.

 

Large Scale Max-Margin Multi-Label Classification with Priors,
B.Hariharan, L. Zelnik-Manor, S. V. N. Vishwanathan and M. Varma.
ICML 2010.
Abstract:
We propose a max-margin formulation for the multi-label classification problem where the goal is to tag a data point with a set of pre-specified labels. Given a set of L labels, a data point can be tagged with any of the 2L possible subsets. The main challenge therefore lies in optimising over this exponentially large label space subject to label correlations.
\ Existing solutions take either of two approaches. The first assumes, a priori, that there are no label correlations and independently trains a classifier for each label (as is done in the 1-vs-All heuristic). This reduces the problem complexity from exponential to linear and such methods can scale to large problems. The second approach explicitly models correlations by pairwise label interactions. However, the complexity remains exponential unless one assumes that label correlations are sparse. Furthermore, the learnt correlations reflect the training set biases.
\ We take a middle approach that assumes labels are correlated but does not incorporate pairwise label terms in the prediction function. We show that the complexity can still be reduced from exponential to linear while modelling dense pairwise label correlations. By incorporating correlation priors we can overcome training set biases and improve prediction accuracy. We provide a principled interpretation of the 1-vs-All method and show that it arises as a special case of our formulation. We also develop efficient optimisation algorithms that can be orders of magnitude faster than the state-of-the-art.

 

Approximate Nearest Subspace Search,
R. Basri, T. Hassner and L. Zelnik-Manor.
IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 33(2): 266--278, Feb. 2011.
Abstract:
Subspaces offer convenient means of representing information in many Pattern Recognition, Machine Vision, and Statistical Learning applications. Contrary to the growing popularity of subspace representations, the problem of efficiently searching through large subspace databases has received little attention in the past. In this paper we present a general solution to the problem of Approximate Nearest Subspace search. Our solution uniformly handles cases where the queries are points or subspaces, where query and database elements differ in dimensionality, and where the database contains subspaces of different dimensions. To this end we present a simple mapping from subspaces to points, thus reducing the problem to the well studied Approximate Nearest Neighbor problem on points. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its capabilities on synthetic and real data. Our experiments indicate that an approximate nearest subspace can be located significantly faster than the nearest subspace, with little loss of accuracy.

 

3D Euler Spirals for 3D Curve Completion,
Gur Harary and Ayellet Tal.
ACM Symposium on Computational Geometry, 2010, 393-402.
Abstract:
Shape completion is an intriguing problem in geometry processing with applications in CAD and graphics. This paper defines a new type of 3D curves, which can be utilized for curve completion. It can be considered as the extension to three dimensions of the 2D Euler spiral. We prove several properties of these curves -- properties that have been shown to be important for the appeal of curves. We illustrate their utility in two applications. The first is ``fixing'' curves detected by algorithms for edge detection on surfaces. The second is shape illustration in archaeology, where the user would like to draw curves that are missing due to the incompleteness of the input model.

 

Context-Aware Saliency Detection,
Stas Goferman, Lihi Zelnik-Manor, and Ayellet Tal.
IEEE Computer Vision and Pattern Recognition (CVPR) 2010 (ORAL), 2376-2383.
Abstract:
We propose a new type of saliency - context-aware saliency - which aims at detecting the image regions that represent the scene. This definition differs from previous definitions whose goal is to either identify fixation points or detect the dominant object. In accordance with our saliency definition, we present a detection algorithm which is based on four principles observed in the psychological literature. The benefits of the proposed approach are evaluated in two applications where the context of the dominant objects is just as essential as the objects themselves. In image retargeting we demonstrate that using our saliency prevents distortions in the important regions. In summarization we show that our saliency helps to produce compact, appealing, and informative summaries.

 

Puzzle-like Collage,
Stas Goferman, Ayellet Tal, Lihi Zelnik-Manor.
Computer Graphics Forum (EUROGRAPHICS) 29(2), 2010, 459-468.
Abstract:
Collages have been a common form of artistic expression since their first appearance in China around 200 BC. Recently, with the advance of digital cameras and digital image editing tools, collages have gained popularity also as a summarization tool. This paper proposes an approach for automating collage construction, which is based on assembling regions of interest of arbitrary shape in a puzzle-like manner. We show that this approach produces collages that are informative, compact, and eye-pleasing. This is obtained by following artistic principles and assembling the extracted cutouts such that their shapes complete each other.

 

Animation of Flocks Flying in Line Formations,
Marina Klotsman and Ayellet Tal.
CASA 2010 (short).
Abstract:
The coordinated flight of bird flocks is a pleasant and attractive sight. While most previous approaches have focused on animating cluster formations, this paper introduces a technique for animating flocks that fly in certain patterns (so-called line formations). We distinguish between the behavior of such flocks during initiation and their behavior during steady flight. We provide a biologically-motivated technique for animating bird flocks, which produces plausible and realistic-looking flock animations.

 

2009
A General Framework for Approximate Nearest Subspace Search,
Ronen Basri, Tal Hassner and Lihi Zelnik-Manor.
2nd IEEE International Workshop on Subspace Methods at the IEEE International Conference on Computer Vision (ICCV), Kyoto, Sept 2009
Abstract:
Subspaces offer convenient means of representing information in many Pattern Recognition, Machine Vision, and \ Statistical Learning applications. Contrary to the growing popularity of subspace representations, the problem \ of efficiently searching through large subspace databases has received little attention in the past. In this paper we \ present a general solution to the Approximate Nearest Subspace search problem. Our solution uniformly handles \ cases where both query and database elements may differin dimensionality, where the database contains subspaces \ of different dimensions, and where the queries themselves may be subspaces. To this end we present a simple \ mapping from subspaces to points, thus reducing the problem to the well studied Approximate Nearest Neighbor problem on \ points. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its \ performance on synthetic and real data. Our tests indicate that an approximate nearest subspace can be located significantly\ faster than the nearest subspace, with little loss of accuracy.

 

Prominent field for shape processing of archaeological artifacts,
Michael Kolomenkin, Ilan Shimshoni, and Ayellet Tal.
IEEE Workshop on eHeritage and Digital Art Preservation (ICCV Workshop) 2009.
Abstract:
Archaeological artifacts are of vital importance in archaeological research. \ We propose a new approach for automatic processing of scanned artifacts. \ It is based on the definition of a new direction field on surfaces (a normalized vector field), termed the prominent field. \ We demonstrate the applicability of the prominent field in two applications. \ The first is surface enhancement if archaeological artifacts, which helps enhance eroded features and remove scanning noise. \ The second is artificial coloring that can replace manual artifact illustration in archaeological reports.

 

Relief Analysis and Extraction,
Rony Zatzarinni, Ayellet Tal, and Ariel Shamir.
SIGGRAPH Asia, ACM Transactions on Graphics, Volume 28, Issue 5, 2009, 136:1-9.
Abstract:
We present an approach for extracting reliefs and details from relief surfaces. \ We consider a relief surface as a surface composed of two components: a base surface and a height function which is defined over this base. \ However, since the base surface is unknown, the decoupling of these components is a challenge. \ We show how to estimate a robust height function over the base, without explicitly extracting the base surface. \ This height function is utilized to separate the {\color{blue} relief} from the base. \ Several applications benefiting from this extraction are demonstrated, \ including relief segmentation, detail exaggeration and dampening, \ copying of details from one object to another, and curve drawing on meshes.

 

Mesh Segmentation Refinement,
Lotan Kaplansky and Ayellet Tal.
Computer Graphics Forum (Pacific Graphics), 28(7), 1995-2003, October 2009
Abstract:
This paper proposes a method for refining existing mesh segmentations, employing a novel extension of the active contour approach to meshes. \ Given a segmentation, produced either by an automatic segmentation method or interactively, \ our algorithm propagates the segment boundaries to more appropriate locations. \ In addition, unlike most segmentation algorithms, our method allows the boundaries to pass through the mesh faces, \ resulting in smoother curves, particularly visible on coarse meshes. The method is also capable of changing the number of segments, \ by enabling splitting and merging of boundary curves during the process. \ Finally, by changing the propagation rules, it is possible to segment the mesh by a variety of criteria, \ for instance geometric-meaningful segmentations, texture-based segmentations, or constriction-based segmentations.

 

Uncluttering Graph Layouts Using Anisotropic Diffusion and Mass Transport,
Yaniv Frishman and Ayellet Tal.
IEEE Transactions on Visualization and Computer Graphics, 15(5), 2009, 777-788.
Abstract:
Many graph layouts include very dense areas, making the layout difficult to understand. \ In this paper, we propose a technique for modifying an existing layout in order to reduce the clutter in dense areas. \ A physically-inspired evolution process, based on a modified heat equation is used to create an improved layout density image, \ making better use of available screen space. Using results from optimal mass transport problems, \ a warp to the improved density image is computed. The graph nodes are displaced according to the warp. \ The warp maintains the overall structure of the graph, thus limiting disturbances to the mental map, \ while reducing the clutter in dense areas of the layout. \ The complexity of the algorithm depends mainly on the resolution of the image visualizing the graph and is linear in the size of the graph. \ This allows scaling the computation according to required running times. \ It is demonstrated how the algorithm can be significantly accelerated using a graphics processing unit (GPU), \ resulting in the ability to handle large graphs in a matter of seconds. Results on several layout algorithms and applications are demonstrated.

 

On Edge Detection on Surfaces,
Michael Kolomenkin, Ilan Shimshoni, and Ayellet Tal.
IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2009, 2767-2774.
Abstract:
Edge detection in images has been a fundamental problem in computer vision from its early days.\ Edge detection on surfaces, on the other hand, has received much less attention. \ The most common edges on surfaces are ridges and valleys, \ used for processing range images in computer vision, \ as well as for non-photorealistic rendering in computer graphics. \ We propose a new type of edges on surfaces, termed relief edges. \ Intuitively, the surface can be considered as an unknown smooth manifold, \ on top of which a local height image is placed. \ Relief edges are the edges of this local image. \ We show how to compute these edges from the local differential geometric surface properties, \ by fitting a local edge model to the surface. \ We also show how the underlying manifold and the local images can be roughly approximated and exploited in the edge detection process. \ Last but not least, \ we demonstrate the application of relief edges to artifact illustration in archaeology.

 

FlexiStickers - Photogrammetric Texture Mapping using Casual Images,
Yochay Tzur and Ayellet Tal.
SIGGRAPH 2009, ACM Transactions on Graphics, Volume 28, Issue 3, 2009, 45:1-10.
Abstract:
Texturing 3D models using casual images has gained importance in the last decade, with the advent of huge databases of images. We present a novel approach for performing this task, which manages to account for the 3D geometry of the photographed object. Our method overcomes the limitation of both the constrained-parameterization approach, which does not account for the photography effects, and the photogrammetric approach, which cannot handle arbitrary images. The key idea of our algorithm is to formulate the mapping estimation as a Moving-Least-Squares problem for recovering local camera parameters at each vertex. The algorithm is realized in a {\em FlexiStickers} application, which enables fast interactive texture mapping using a small number of constraints.
 

 

2008
Demarcating Curves for Shape Illustration,
Michael Kolomenkin, Ilan Shimshoni, and Ayellet Tal.
SIGGRAPH Asia 2008, ACM Transactions on Graphics, Volume 27, Issue 5, December 2008.
Abstract:
Curves on objects can convey the inherent features of the shape. This paper defines a new class of view-independent curves, denoted demarcating curves. In a nutshell, demarcating curves are the loci of the ``strongest'' inflections on the surface. Due to their appealing capabilities to extract and emphasize 3D textures, they are applied to artifact illustration in archaeology, where they can serve as a worthy alternative to the expensive, time-consuming, and biased manual depiction currently used.

 

Image-Based Texture Replacement Using Multiview Images,
Doron Tal, Ilan Shimshoni, and Ayellet Tal.
Doron Tal, Ilan Shimshoni, and Ayellet Tal. ACM Symposium on Virtual Reality (VRST), 2008, 185-192.
Abstract:
Augmented reality is concerned with combining real-world data, such as images, with artificial data. Texture replacement is one such task. It is the process of painting a new texture over an existing textured image patch, such that depth cues are maintained. This paper proposes a general and automatic approach for performing texture replacement, which is based on multiview stereo techniques that produce depth information at every pixel. The use of several images allows us to address the inherent limitation of previous studies, which are constrained to specific texture classes, such as textureless or near-regular textures. To be able to handle general textures, a modified dense correspondence estimation algorithm is designed and presented.

 

Online Dynamic Graph Drawing (journal version),
Yaniv Frishman and Ayellet Tal.
IEEE Transactions on Visualization and Computer Graphics, Volume 14, Number 4, July/August 2008, 727-740.
Abstract:
This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and thus the user's mental map, while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided.

 

Mesh Segmentation for CAD Applications,
Ayellet Tal.
ESDA - 9th Biennial ASME Conference on Engineering Systems Design and Analysis, 2008 (invited).
Abstract:
Segmentation of meshes has received a lot of attention in recent years, due to its growing number of applications. In this paper, we discuss properties that have been used in the literature to evaluate segmentation algorithms. Then, we describe some applications of segmentation in CAD. For each application, we review one of our segmentation algorithms that is suitable for the problem. We focus on four applications: modeling by example, shape-based retrieval, skeleton extraction, and paper crafting.

 

Unsupervised Learning of Categorical Segments in Image Collections,
Marco Andreetto, Lihi Zelnik-Manor and Pietro Perona.
To appear in the Sixth IEEE Computer Society Workshop on Perceptual Organization in Computer Vision (POCV08), in Computer Vision and Pattern Recognition (CVPR08), Anchorage, Alaska, Jun. 2008.
Abstract:
Which one comes first: segmentation or recognition? We propose a probabilistic framework for carrying out the two simultaneously.  The framework combines an LDA 'bag of visual words' model for recognition, and a hybrid parametric-nonparametric model for segmentation.  If applied to a collection of images, our framework can simultaneously discover the segments of each image, and the correspondence between such segments.  Such segments may be thought of as the 'parts' of corresponding objects that appear in the image collection.  Thus, the model may be used for learning new categories, detecting/classifying objects, and segmenting images.
 

 

Flat refractive geometry,
Tali Treibitz, Yoav Y. Schechner and Hanumant Singh.
Proc. IEEE CVPR (2008).
Abstract:
While the study of geometry has mainly concentrated on single-viewpoint (SVP) cameras, there is growing attention to more general non-SVP systems.  Here we study an important class of systems that inherently have a non-SVP: a perspective camera imaging through an interface into a medium.  Such systems are ubiquitous: they are common when looking into water-based environments.  The paper analyzes the common flat-interface class of systems.  It characterizes the locus of the viewpoints (caustic) of this class, and proves that the SVP model is invalid in it.  This may explain geometrical errors encountered in prior studies.  Our physics-based model is parameterized by the distance of the lens from the medium interface, beside the focal length.  The physical parameters are calibrated by a simple approach that can be based on a single-frame.  This directly  determines the system geometry.  The calibration is then used to compensate for modeled system distortion.  Based on this model, geometrical measurements of objects are significantly more accurate, than if based on an SVP model.  This is demonstrated in real-world experiments. 
 

 

A walk through the web's video clips,
Sara Zanetti, Lihi Zelnik-Manor and Pietro Perona.
To appear in the First IEEE Workshop om Internet Vision, in Computer Vision and Pattern Recognition (CVPR08), Ancorage, Alaska, Jun. 2008.
Abstract:
Approximately 105 video clips are posted every day on the web.  The popularity of web-based video databases poses a number of challenges to machine vision scientists: how do we organize, index and search such large wealth of data? Contest-based video search and classification have been proposed in the literature and applied successfully to analyzing movies, TV broadcasts and lab-made videos.  We explore the performance of some of these algorithms on a large data-set of approximately 3000 videos.  we collected our data-set directly from the web minimizing bias for content or quality, way so as to have a faithful representation of the statistics of this medium.  We find that the algorithms that we have come to trust do not work well on video clips, because their quality is lower and their subject is more varied.  We will make the data publicly available to encourage further research.
 

 

On controlling light transport in poor visibility environments,
Mohit Gupta, Srinivas G. Narasimhan and Yoav Y. Schechner.
Proc. IEEE CVPR (2008).
Abstract:
Poor visibility conditions due to murky water, bad weather, dust and smoke severely impede the performance of vision systems.  Passive methods have been used to restore scene contrast under moderate visibility by digital post-processing.  However, these methods are ineffective when the quality of acquired images is poor to begin with.  In this work, we design active lighting and sensing systems for controlling light transport before image formation, and hence obtain higher quality data.  First, we present a technique of polarized light striping based on combining polarization imaging and structured light striping.  We show that this technique out-performs different existing illumination and sensing methodologies.  Second, we present a numerical approach for computing the optimal relative sensor-source position, which results in the best quality image.  Our analysis accounts for the limits imposed by sensor noise.
 

 

A general Framework for Approximate Nearest Subspace Search,
Ronen Basri, Tal Hassner and Lihi Zelnik-Manor.
Technical Report CCIT #699, Department of Electrical Engineering, Technion, June 2008.
Abstract:
Subspaces offer convenient means of representing information in many Pattern Recognition, Machine Vision, and Statistical Learning applications.  Contrary to the growing popularity of subspace representations, the problem of efficiently searching through large subspace databases has received little attention in the past.  In this paper we present a general solution to the Approximate Nearest Subspace search problem.  Our solution uniformly handles cases where both query and database elements may differ in dimensions, and where the queries themselves may be subspaces.  To this end we present a simple mapping from subspaces to points, thus reducing the problem to the well studied Approximate Nearest Neighbor problem on points.  We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its capabilities on synthetic and real data.  Our experiments indicate that an approximate nearest subspace can be located significantly faster than the nearest subspace, with little loss of accuracy.
 

 

Overcoming visual reverberations,
Yaron Diamant and Yoav Y. Schechner.
Proc. IEEE CVPR (2008).
Abstract:
An image acquired through a glass window is a superposition of two sources : a scene behind the window, and a reflection of a scene in front of the window.  Light rays incident on the window are reflected back and forth inside the glass.  Such internal reflections affect the radiance of both sources. : a spatial effect is created of dimmed and shifted reflections.  Our work generalizes the treatment of transparent scenes to deal with this effect.  First, we present a physical model of the image formation.  It turns out that each of the transmitted and reflected scenes undergoes a convolution with a particular point spread function (PSF), composed of distinct delta functions.  Therefore, scene recovery involves inversion of these PSFs.  We analyze the fundamental limitations faced by any attempt to solve this inverse problem.  We then present a solution approach.  The approach is based on deconvolution by linear filtering and simple optimization.  The input to the algorithm is a pair of frames, taken through a polarizing filter.  The method is demonstrated experimentally.
 

 

MOVIS: A system for Visualizing Distributed Mobile Object Environments,
Yaniv Frishman and Ayellet Tal.
Journal of Visual Languages and Computing, Vol 19(3), June 2008, 303-320.
Abstract:
This paper presents MOVIS -- a system for visualizing mobile object frameworks. In such frameworks, the objects can migrate to remote hosts, along with their state and behavior, while the application is running. An innovative graph--based visualization is used to depict the physical and the logical connections in the distributed object network. Scalability is achieved by using a focus+context technique jointly with a user-steered clustering algorithm. In addition, an event synchronization model for mobile objects is presented. The system has been applied to visualizing several mobile object applications.

 

A focus on recent developments and trends in underwater imaging,
Donna M. Kocak, Fraser R. Daligleish, Frank M. caimi and Yoav Y. Schechner.
Marine Technology Society Journal, Vol. 42, No. 1, pp. 52-67 (2008), Special issue on State of the Technology.
Abstract:
Advances in the field of underwater optical imaging are reviewed for the years 2005 to present.  A synopsis of research and technical innovations is presented, organized in much the same way as the previous report (Kocak and Caimi, 2005).  Several recent applications of novel systems are shown as examples, and trends in emerging underwater imaging research and development are briefly summarized.
 

 

MAVIS: A Multi-Level Algorithm Visualization System within a Collaborative Distance Learning Environment,
Igal Koifman, Ilan Shimshoni and Ayellet Tal.
Symposium on Human Centric Computing Languages and Environments, September 2002, 216-225.
Journal of Visual Languages and Computing, Volume 19, Issue 2, April 2008, 182-202.

Abstract:
We present in this paper a new model for an algorithm visualization system. Our model views the visualization system as an integral part of a broader distance learning environment. As such, it supports the heterogeneity of the Internet the visualization is expected to run on and the diversity of the expected users. It does so by defining a few manners for handling multi-level visualizations. First, a visualization can run in various abstraction levels of the algorithm, depending on the familiarity of the students with the studied materials. Second, a visualization can use various levels of graphics, depending on the capabilities of the client machines. Third, the messages sent between the machines can be of various levels, depending on the communication loads. Another important aspect of a distance learning environment, which is supported by our model, is to facilitate collaboration and data sharing between the students and the instructor and between the students themselves.This paper also presents a system, MAVIS, that realizes the model, and demonstrates its use on case studies.

 

Space variant ultrasound frequency compounding based on noise characteristics,
Yael Erez, Yoav Y. Schechner and Dan Adam.
Ultrasound in Medicine and Biology, Vol 34, No. 6, pp. 981-1000 (2008).
Abstract:
Ultrasound images are very noisy.  Along with system noise, a significant noise source is the speckle phenomenon caused by interference in the viewed object.  Most of the past approaches for denoising ultrasound images essentially blur the image and they do not handle attenuation.  We discuss an approach that does not blur the image and handles attenuation.  It is based on frequency compounding, in which images of the same object are acquired in different acoustic frequencies and, then, compounded.  Existing frequency compounding methods have been based on simple averaging, and have achieved only limited enhancement.  The reason is that the statistical and physical characteristics of the signal and noise vary with depth, and the noise is correlated between acoustic frequencies.  Hence, we suggest two spatially varying frequency compounding methods, based on the understanding of these characteristics.  As demonstrated in experiments, the proposed approaches suppress various noise sources and also recover attenuated objects while maintaining a high resolution.
 

 

2007
Cross-modal localization via sparsity,
Einat Kidron, Yoav Y. Schechner and Michael Elad.
IEEE Trans. Signal Processing, Vol. 55 , No. 4 , pp. 1390-1404, 2007.
Abstract:
Cross-modal analysis is a natural progression beyond processing of single-source signals. Simultaneous processing of two sources can reveal information that is unavailable when handling the sources separately. Indeed, human and animal perception, computer vision, weather forecasting, and various other scientific and technological fields can benefit from such a paradigm. A particular cross-modal problem is localization: out of the entire data array originating from one source, localize the components that best correlate with the other. For example, auditory and visual data sampled from a scene can be used to localize visual events associated with the sound track. In this paper we present a rigorous analysis of fundamental problems associated with the localization task. We then develop an approach that leads efficiently to a unique, high definition localization outcome. Our method is based on canonical correlation analysis (CCA), where inherent ill-posedness is removed by exploiting sparsity of cross-modal events. We apply our approach to localization of audio-visual events. The proposed algorithm grasps such dynamic audio-visual events with high spatial resolution. The algorithm effectively detects the pixels that are associated with sound, while filtering out other dynamic pixels, overcoming substantial visual distractions and audio noise. The algorithm is simple and efficient thanks to its reliance on linear programming, while being free of user-defined parameters.

 

Online Dynamic Graph Drawing (best paper award)
Yaniv Frishman and Ayellet Tal.
 EuroVis, May 2007, 75-82.
Abstract:
This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and thus the user's mental map, while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to $8$ compared to the CPU implementation. An application to visualization of discussion threads in Internet sites is provided.

 

Multi-Level Graph Layout on the GPU
Yaniv Frishman and Ayellet Tal.
IEEE Transactions on Visualization and Computer Graphics (InfoVis 2007)
Abstract:
This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.

 

llumination multiplexing within fundamental limits
Nenanel Ratner and Yoav Y. Schechner
Proc. IEEE CVPR (2007).
Abstract:
Taking a sequence of photographs using multiple illumination sources or settings is central to many computer vision and graphics problems. A growing number of recent methods use multiple sources rather than single point sources in each frame of the sequence. Potential benefits include increased signal-to-noise ratio and accommodation of scene dynamic range. However, existing multiplexing schemes, including Hadamard-based codes, are inhibited by fundamental limits set by Poisson distributed photon noise and by sensor saturation. The prior schemes may actually be counterproductive due to these effects. We derive multiplexing codes that are optimal under these fundamental effects. Thus, the novel codes generalize the prior schemes and have a much broader applicability. Our approach is based on formulating the problem as a constrained optimization. We further suggest an algorithm to solve this optimization problem. The superiority and effectiveness of the method is demonstrated in experiments involving object illumination.

 

Harmony In motion
Zohar Barzelay and Yoav Y. Schechner
Proc. IEEE CVPR (2007).
Abstract:
Cross-modal analysis offers information beyond that extracted from individual modalities. Consider a camcorder having a single microphone in a cocktail-party: it captures several moving visual objects which emit sounds. A task for audio-visual analysis is to identify the number of independent audio-associated visual objects (AVOs), pinpoint the AVOs spatial locations in the video and isolate each corresponding audio component. Part of these problems were considered by prior studies, which were limited to simple cases, e.g., a single AVO or stationary sounds. We describe an approach that seeks to overcome these challenges. It acknowledges the importance of temporal features that are based on significant changes in each modality. A probabilistic formalism identifies temporal coincidences between these features, yielding cross-modal association and visual localization. This association is of particular benefit in harmonic sounds, as it enables subsequent isolation of each audio source. We demonstrate this in challenging experiments, having multiple, simultaneous highly nonstationary AVOs.

 

Variational distance dependent image restoration
Ran Kaftory, Yoav Y. Schechner and Joshua Zeevi
Proc. IEEE CVPR (2007).
Abstract:
There is a need to restore color images that suffer from distance-dependent degradation during acquisition. This occurs, for example, when imaging through scattering media. There, signal attenuation worsens with the distance of an object from the camera. A naive restoration may attempt to restore the image by amplifying the signal in each pixel according to the distance of its corresponding object. This, however, would amplify the noise in a nonuniform manner. Moreover, standard space-invariant denoising over-blurs close by objects (which have low noise), or insufficiently smoothes distant objects (which are very noisy). We present a variational method to overcome this problem. It uses a regularization operator which is distance dependent, in addition to being edge-preserving and color- channel coupled. Minimizing this functional results in a scheme of reconstruction while denoising. It preserves important features, such as the texture of close by objects and edges of distant ones. A restoration algorithm is presented for reconstructing color images taken through haze. The algorithm also restores the path radiance, which is equivalent to the distance map. We demonstrate the approach experimentally.

 

Multiplexing for optimal lighting
Yoav Y. Schechner, Shree K. Nayar, and Peter N. Belhumeur
IEEE Trans. Pattern Analysis & Machine Intelligence, Vol. 29 , No. 8 , pp. 1339-1354 (2007).
Abstract:
Imaging of objects under variable lighting directions is an important and frequent practice in computer vision, machine vision, and image-based rendering. Methods for such imaging have traditionally used only a single light source per acquired image. They may result in images that are too dark and noisy, e.g., due to the need to avoid saturation of highlights. We introduce an approach that can significantly improve the quality of such images, in which multiple light sources illuminate the object simultaneously from different directions. These illumination-multiplexed frames are then computationally demultiplexed. The approach is useful for imaging dim objects, as well as objects having a specular reflection component. We give the optimal scheme by which lighting should be multiplexed to obtain the highest quality output, for signal-independent noise. The scheme is based on Hadamard codes. The consequences of imperfections such as stray light, saturation, and noisy illumination sources are then studied. In addition, the paper analyzes the implications of shot noise, which is signal-dependent, to Hadamard multiplexing. The approach facilitates practical lighting setups having high directional resolution. This is shown by a setup we devise, which is flexible, scalable, and programmable. We used it to demonstrate the benefit of multiplexing in experiments.

 

Regularized image recovery in scattering media
Yoav Y. Schechner and Yuval Averbuch
IEEE Trans. Pattern Analysis & Machine Intelligence, Vol. 29 , No. 9 , pp. 1655-1660 (2007)
Abstract:
When imaging in scattering media, visibility degrades as objects become more distant. Visibility can be significantly restored by computer vision methods that account for physical processes occurring during image formation. Nevertheless, such recovery is prone to noise amplification in pixels corresponding to distant objects, where the medium transmittance is low. We present an adaptive filtering approach that counters the above problems: While significantly improving visibility relative to raw images, it inhibits noise amplification. Essentially, the recovery formulation is regularized, where the regularization adapts to the spatially varying medium transmittance. Thus, this regularization does not blur close objects. We demonstrate the approach in atmospheric and underwater experiments, based on an automatic method for determining the medium transmittance.

 

Image-based prediction of imaging and vision performance
Saar Bobrov and Yoav Y. Schechner
Journal of the Optical Society of America - A, Vol. 24 , No. 7, pp. 1920-1929 (2007)
Abstract:
Some scenarios require performance estimation of an imaging or a computer vision system prior to its actual operation such as in system design, as well as in tasks of high risk or cost. To predict the performance, we propose an image-based approach that accounts for underlying image-formation processes while using real image data. We give a detailed description of image formation from scene photons to image gray levels. This analysis includes all the optical, electrical, and digital sources of signal distortion and noise. On the basis of this analysis and our access to the camera parameters, we devise a simple image-based algorithm. It transforms a baseline high-quality image to render an estimated outcome of the system we wish to operate or design. We demonstrate our approach on thermal imaging systems.
2006
Temporal Coherence in Bounding Volume Hierarchies for Collision Detection,
Oren Tropp, Ayellet Tal, Ilan Shimshoni and David Dobkin.
International Journal of Shape Modeling, Vol. 12, No. 2, December 2006, 159--178.
Abstract:
Collision detection is a fundamental problem in computer graphics. In this paper, temporal coherence is studied and an algorithm exploiting it for bounding volume hierarchies, is presented. We show that maintaining some of the intersection tests computed in the previous frame, along with certain information, is able to speedup the intersection tests considerably. The algorithm is able to accelerate the collision detection for small motions and works as fast as the regular algorithm for large motions, where temporal coherence does not exist. The algorithm framework can be implemented for any type of bounding volume hierarchy. To demonstrate this, it was implemented for the OBB and the AABB data structures and tested on several benchmark scenarios.
Ultrasound Image Denoising by Spatially Varying Frequency Compounding,
Yael Erez, Yoav Y. Schechner and Dan Adam.
Proc. DAGM Symposium, LNCS 4147, pp. 1-10, 2006.
Abstract:
Ultrasound images are very noisy. Along with system noise, a signicant noise source is the speckle phenomenon, caused by interfer- ence in the viewed object. Most past approaches for denoising ultrasound images essentially blur the image, and they do not handle attenuation. Our approach, on the contrary, does not blur the image and does handle attenuation. Our denoising approach is based on frequency compounding, in which images of the same object are acquired in dierent acoustic fre- quencies, and then compounded. Existing frequency compounding meth- ods have been based on simple averaging, and have achieved only limited enhancement. The reason is that the statistical and physical characteris- tics of the signal and noise vary with depth, and the noise is correlated. Hence, we suggest a spatially varying frequency compounding, based on understanding of these characteristics. Our method suppresses the var- ious noise sources and recovers attenuated objects, while maintaining high resolution.
Mesh Retrieval by Components,
Ayellet Tal and Emanuel Zuckerberger.
International Conference on Computer Graphics Theory and Applications,142-149, 2006.
Abstract:
We describe an approach for retrieving three-dimensional objects similar to a given one from a database. The key idea of our technique is to decompose each object into its meaningful components, and fit each component to a basic shape. This decomposition is represented as an attributed graph, which is considered the {\em signature} of the object. Our signature leverages human vision theories such as Marr's and Biederman's. We show that this signature gives rise to a retrieval algorithm which is invariant to non-rigid transformations. Finally, a system which realizes our technique was built and tested on a databa se of about 400 objects. The paper presents the retrieval results and conclusions are being drawn.
Blind Haze Separation,
Sarit Shwartz , Einav Namer and Yoav Y. Schechner.
IEEE CVPR, Vol. 2, pp. 1984-1991 , 2006 .
Abstract:
Outdoor imaging is plagued by poor visibility conditions due to atmospheric scattering, particularly in haze. A major problem is spatially-varying reduction of contrast by stray radiance (airlight), which is scattered by the haze particles towards the camera. Recent computer vision methods have shown that images can be compensated for haze, and even yield a depth map of the scene. A key step in such a scene recovery is subtraction of the airlight. In particular, this can be achieved by analyzing polarization-filtered images. However, the recovery requires parameters of the airlight. These parameters were estimated in past studies by measuring pixels in sky areas. This paper derives an approach for blindly recovering the parameter needed for separating the airlight from the measurements, thus recovering contrast, with neither user interaction nor existence of the sky in the frame. This eases the interaction and conditions needed for image dehazing, which also requires compensation for attenuation. The approach has proved successful in experiments, some of which are shown here.
Instant 3Descatter,
Tali Treibitz and Yoav Y. Schechner.
IEEE CVPR, Vol. 2, pp. 1861-1868 , 2006 .
Abstract:
Imaging in scattering media such as fog and water is important but challenging. Images suffer from poor visibility due to backscattering and signal attenuation. Most prior methods for visibility improvement use active illumination scanners (structured and gated), which are slow and cumbersome. On the other hand, natural illumination is inapplicable to dark environments. The current paper counters these deficiencies. We study the formation of images under wide field (non-scanning) artificial illumination. We discovered some characteristics of backscattered light empirically. Based on these, the paper presents a visibility recovery approach which also yields a rough estimate of the 3D scene structure. The method is simple and requires compact hardware, using active wide field polarized illumination. Two images of the scene are instantly taken, with different states of a camera-mounted polarizer. A recovery algorithm then follows. We demonstrate the approach in underwater field experiments.
Efficient Separation of Convolutive Image Mixtures,
Sarit Shwartz, Yoav Y. Schechner, and Michael Zibulevsky.
ICA - Int. Conference on Independent Component Analysis and Blind Signal Separation, pp. 246-253 , 2006 .
Abstract:
Convolutive mixtures of images are common in photography of semi-reflections. They also occur in microscopy and tomography. Their formation process involves focusing on an object layer, over which defocused layers are superimposed. Blind source separation (BSS) of convolutive image mixtures by direct optimization of mutual information is very complex and suffers from local minima. Thus, we devise an efficient approach to solve these problems. Our method is fast, while achieving high quality image separation. The convolutive BSS problem is converted into a set of instantaneous (pointwise) problems, using a short time Fourier transform (STFT). Standard BSS solutions for instantaneous problems suffer, however, from scale and permutation ambiguities. We overcome these ambiguities by exploiting a parametric model of the defocus point spread function. Moreover, we enhance the efficiency of the approach by exploiting the sparsity of the STFT representation as a prior.
Depth From Diffracted Rotation,
Adam Greengard, Yoav Y. Schechner and Rafael Piestun.
OPTICS LETTERS, Volume 31, Number 2, 181-183, January 2006.
Abstract:
The accuracy of depth estimation based on defocus effects has been essentially limited by the depth of field of the imaging system. We show that depth estimation can be improved significantly relative to classical methods by exploiting three-dimensional diffraction effects. We formulate the problem by using information theory analysis and present, to the best of our knowledge, a new paradigm for depth estimation based on spatially rotating point-spread functions (PSFs). Such PSFs are fundamentally more sensitive to defocus thanks to their first-order axial variation. Our system acquires a frame by using a rotating PSF and jointly processes it with an image acquired by using a standard PSF to recover depth information. Analytical, numerical, and experimental evidence suggest that the approach is suitable for applications such as microscopy and machine vision.
Mesh segmentation A comparative study,
M. Attene, S. Katz, M. Mortara, G. Patane, M. Spagnuolo, and A.Tal.
Shape Modeling International (SMI), July 2006.
Abstract:
Mesh segmentation has become an important component in many applications in computer graphics. In the last several years, many algorithms have been proposed in this growing area, offering a diversity of methods and various evaluation criteria. This paper provides a comparative study of some of the latest algorithms and results, along several axes. We evaluate only algorithms whose code is available to us, and thus it is not a comprehensive study. Yet, it sheds some light on the vital properties of the methods and on the challenges that future algorithms should face.
Paper Craft Models from Meshes,
Idan Shatz, Ayellet Tal and George Leifman.
The Visual Computer (Pacific Graphics), Volume 22, Issue 9, September 2006, 825-834.
Abstract:
This paper introduces an algorithm for segmenting a mesh into developable approximations. The algorithm can be used in various applications in CAD and computer graphics. This paper focuses on paper crafting and demonstrates that the algorithm generates approximations that are developable, easy to cut, and can be glued together. It is also shown that the error between the given model and the paper model is small.
2005
Visualization of Mobile Object Environments,
Yaniv Frishman and Ayellet Tal
ACM Symposium on Software Visualization, May 2005, to appear.
Abstract:
This paper presents a system for visualizing mobile object frameworks. In such frameworks, the objects can migrate to remote hosts, along with their state and behavior, while the application is running. An innovative graph-based visualization is used to depict the physical and the logical connections in the distributed object network. Scalability is achieved by using a focus+context technique jointly with a user-steered clustering algorithm. In addition, an event synchronization model for mobile objects is presented. The system has been applied to visualizing several mobile object applications.
Advanced Visibility Improvement Based on Polarization Filtered Images,
Einav Namer and Yoav Y. Schechner.
SPIE 5888: Polarization Science and Remote Sensing II, pp. 36-45, 2005 .
Abstract:
Recent studies have shown that major visibility degradation effects caused by haze can be corrected for by analyzing polarization-filtered images. The analysis is based on the fact that the path-radiance in the atmosphere (airlight) is often partially polarized. Thus, associating polarization with path-radiance enables its removal, as well as compensation for atmospheric attenuation. However, prior implementations of this method suffered from several problems. First, they were based on mechanical polarizers, which are slow and rely on moving part. Second, the method had failed in image areas corresponding to specular objects, such as water bodies (lakes) and shiny construction materials (e.g., windows). The reason for this stems from the fact that specular objects reflect partially polarized light, confusing a naive association of polarization solely with path-radiance. Finally, prior implementations derived necessary polarization parameters by manually selecting reference points in the field of view. This human intervention is a drawback, since we would rather automate the process. In this paper, we report our most recent progress in the development of our visibility-improvement method. We show directions by which those problems can be overcome. Specifically, we added algorithmic steps which automatically extract the polarization parameters needed, and make visibility recovery more robust to polarization effects originating from specular objects. In addition, we now test an electrically-switchable polarizer based on a liquid crystal device for improving acquisition speed.
Mesh Segmentation using Feature Point and Core Extraction,
Sagi Katz, George Leifman, and Ayellet Tal.
The Visual Computer (Pacific Graphics), Volume 21, Numbers 8-10, 649-658, October 2005.
Abstract:
Mesh segmentation has become a necessary ingredient in many applications in computer graphics.
This paper proposes a novel hierarchical mesh segmentation algorithm, which is based on new methods for prominent feature point and core extraction.
The algorithm has several benefits. First, it is invariant both to the pose of the model and to different proportions between the model's components. Second, it produces correct hierarchical segmentations of meshes, both in the coarse levels of the hierarchy and in the fine levels, where tiny segments are extracted. Finally, the boundaries between the segments go along the natural seams of the models.
Temporal Coherence in Bounding Volume Hierarchies for Collision Detection,
Oren Tropp, Ayellet Tal, Ilan Shimshoni and David Dobkin.
The Visual Computer (Pacific Graphics), 2005.
Abstract:
Collision detection is a fundamental problem in computer graphics.
In this paper, temporal coherence is studied and an algorithm exploiting it for bounding volume hierarchies, is presented.
We show that maintaining some of the intersection tests computed in the previous frame, along with certain information, is able to speedup the intersection tests considerably.
The algorithm is able to accelerate the collision detection for small motions and works as fast as the regular algorithm for large motions, where temporal coherence does not exist. The algorithm framework can be implemented for any type of bounding volume hierarchy. To demonstrate this, it was implemented for the OBB and the AABB data structures and tested on several benchmark scenarios.
Fast kernel entropy estimation and optimization,
Sarit Shwartz, Michael Zibulevsky and Yoav Y. Schechner.
Signal Processing, Special Issue on Information Theoretic Signal Processing, Vol. 85, No. 5, pp. 1045-1058 (2005).
Abstract:
Differential entropy is a quantity used in many signal processing problems.
Often we need to calculate not only the entropy itself, but also its gradient with respect to various variables, for efficient optimization, sensitivity analysis, etc. Entropy estimation can be based on an estimate of the probability density function, which is computationally costly if done naively. Some prior algorithms use computationally efficient non-parametric entropy estimators. However, differentiation of the previously proposed estimators is difficult and may even be undefined. To counter these obstacles, we consider non-parametric kernel entropy estimation that is differentiable. We present two different accelerated kernel algorithms. The first accelerates the entropy gradient calculation based on a back propagation principle. It allows calculating the differential entropy gradient in the same complexity as that of calculating the entropy itself. The second algorithm accelerates the estimation of both entropy and its gradient by using fast convolution over a uniform grid. As an example, we apply both algorithms to blind source separation.
Minimal-Cut Shape Composition,
T. Hassner, L. Zelnik-Manor, G. Leifman, R. Basri.
International Conference on Shape Modeling and Applications, 2005.
Abstract:
Constructing new, complex models is often done by reusing parts of existing models, typically by applying a sequence of segmentation, alignment and composition operations. Segmentation, either manual or automatic, is rarely adequate for this task, since it is applied to each model independently, leaving it to the user to trim the shapes and determine where to connect them. In this paper we propose a new composition tool. Our tool obtains as input two models, aligned either manually or automatically, and a small set of constraints indicating which portions of the two shapes should be preserved in the final output. It then automatically negotiates the best location to connect the models, trimming and stitching them as required to produce a seamless result. We offer a method based on the graph theoretic minimal cut as a means of implementing this new tool. We describe a system intended for both expert and novice users, allowing the user easy and flexible control over the composition result. In addition, we show our method to be well suited for a variety of model processing applications such as model repair, hole filling, and piecewise rigid deformations.
Generalized mosaicing: Polarization panorama,
Yoav Y. Schechner and Shree K. Nayar.
IEEE Trans. Pattern Analysis & Machine Intelligence, Vol. 27, No. 4, pp. 631-636 (2005).
Abstract:
We present an approach to image the polarization state of object points in a wide field of view, while enhancing the radiometric dynamic range of imaging systems by generalizing image mosaicing. The approach is biologicallyinspired, as it emulates spatially varying polarization sensitivity of some animals. In our method, a spatially varying polarization and attenuation filter is rigidly attached to a camera. As the system moves, it senses each scene point multiple times, each time filtering it through a different filter polarizing angle, polarizance, and transmittance. Polarization is an additional dimension of the generalized mosaicing paradigm, which has recently yielded high dynamic range images and multispectral images in a wide field of view using other kinds of filters. The image acquisition is as easy as in traditional image mosaics. The computational algorithm can easily handle nonideal polarization filters (partial polarizers), variable exposures, and saturation in a single framework. The resulting mosaic represents the polarization state at each scene point. Using data acquired by this method, we demonstrate attenuation and enhancement of specular reflections and semireflection separation in an image mosaic.
Recovery of Underwater Visibility and Structure by Polarization Analysis,
Yoav Y. Schechner and Nir Karpel.
Accepted to IEEE Journal of Oceanic Engineering (2005).
Abstract:
Underwater imaging is important for scientific research and technology, as well as for popular activities, yet it is plagued by poor visibility conditions. In this work, we present a computer vision approach which easily removes degradation effects in underwater vision. We analyze the physical effects of visibility degradation. It is shown that the main degradation effects can be associated with partial polarization of light. Then, an algorithm is presented, which inverts the image formation process for recovering good visibility in images of scenes. The algorithm is based on a couple of images taken through a polarizer at different orientations. As a by-product, a distance map of the scene is also derived. In addition, this work analyzes the noise sensitivity of the recovery. We successfully demonstrated our approach in experiments, which were conducted in the sea. Great improvements of scene contrast and color correction were obtained, nearly doubling the underwater visibility range.
Radiometric framework for image mosaicking,
Anatoly Litvinov and Yoav Y. Schechner.
To be published in the Journal of the Optical Society of America - A (2005).
Abstract:
Nonuniform exposures often affect imaging systems, e.g., owing to vignetting. Moreover, the sensor's radiometric response may be nonlinear. These characteristics hinder photometric measurements. They are particularly annoying in image mosaicking, in which images are stitched to enhance the field of view. Mosaics suffer from seams stemming from radiometric inconsistencies between raw images. Prior methods feathered the seams but did not address their root cause. We handle these problems in a unified framework. We suggest a method for simultaneously estimating the radiometric response and the camera nonuniformity, based on a frame sequence acquired during camera motion. The estimated functions are then compensated for. This permits image mosaicking, in which no seams are apparent. There is no need to resort to dedicated seamfeathering methods. Fundamental ambiguities associated with this estimation problem are stated.
Addressing Radiometric Nonidealities: A Unified Framework,
Anatoly Litvinov and Yoav Y. Schechner.
Accepted to IEEE CVPR (2005).
Abstract:
Cameras may have non-ideal radiometric aspects, including spatial non-uniformity, e.g., due to vignetting; a nonlinear radiometric response of the sensor; and temporal variations due to automatic gain control (AGC). Often, these characteristics exist simultaneously, and are typically unknown. They thus hinder consistent photometric measurements. In particular, they create annoying seams in image mosaics. Prior studies approached part of these problems while excluding others. We handle all these problems in a unified framework. We suggest an approach for simultaneously estimating the radiometric response, the spatial non-uniformity and the temporally varying gain. The approach does not rely on dedicated processes that intentionally vary exposure settings. Rather, it is based on an ordinary frame sequence acquired during camera motion. The estimated non-ideal characteristics are then compensated for. We state fundamental ambiguities associated with this recovery problem, while exposing a novel image invariance.
The method is demonstrated in several experiments, where different frames are brought into mutual radiometric consistency. The accuracy achieved is sufficient for seamless mosaicing, with no need to resort to dedicated seam-feathering methods.
Pixels that Sound,
E. Kidron, Y. Schechner.
Accepted to IEEE CVPR (2005).
Abstract:
People and animals fuse auditory and visual information to obtain robust perception. A particular benefit of such cross-modal analysis is the ability to localize visual events associated with sound sources. We aim to achieve this using computer-vision aided by a single microphone. Past efforts encountered problems stemming from the huge gap between the dimensions involved and the available data. This has led to solutions suffering from low spatio-temporal resolutions. We present a rigorous analysis of the fundamental problems associated with this task. Then, we present a stable and robust algorithm which overcomes past deficiencies. It grasps dynamic audio-visual events with high spatial resolution, and derives a unique solution. The algorithm effectively detects pixels that are associated with the sound, while filtering out other dynamic pixels. It is based on canonical correlation analysis (CCA), where we remove inherent ill-posedness by exploiting the typical spatial sparsity of audio-visual events. The algorithm is simple and efficient thanks to its reliance on linear programming and is free of user-defined parameters. To quantitatively assess the performance, we devise a localization criterion. The algorithm capabilities were demonstrated in experiments, where it overcame substantial visual distractions and audio noise.
2004
Portable polarimetric underwater imaging system with a linear response,
Nir Karpel and Yoav Y. Schechner.
SPIE 5432: Polarization: Measurement, Analysis and Remote Sensing VI, pp. 106-115, 2004.
Abstract:
Polarized light plays an important role in the underwater environment. Light that is scattered within the water is partially polarized. Biological and articial systems can exploit this phenomenon. We aim to utilize this phenomenon in a new generation of underwater imaging systems in order to partially compensate for the loss of color and visibility. In order to obtain quantitative measurement of radiance and polarization, the imaging system should have a linear radiometric response and low noise. In addition, the interface of the camera with the water should have a minimum eect on the polarization. In this paper, we describe a portable lightweight imaging system that addresses these conditions. We detail the design considerations and empirical verications.
Placing Three-Dimensional Models in an Uncalibrated Single Image of an Architectural Scene,
Sara Keren, Ilan Shimshoni and Ayellet Tal.
ACM Symposium on Virtual Reality, November 2002, 186-193, 223.
PRESENCE, 13(6): 692-707, 2004 (invited to a special issue).

Abstract:
This paper discusses the problem of inserting three-dimensional models into a single image. The main focus of the paper is on the accurate recovery of the camera's parameters, so that 3D models can be inserted in the ``correct'' position and orientation. An important aspect of this paper is a theoretical and an experimental analysis of the errors. We also implemented a system which ``plants'' virtual 3D objects in the image, and tested the system on many indoor augmented reality scenes. Our analysis andexperiments have shown that errors in the placement of the objects are un-noticeable.
Dynamic Drawing of Clustered Graphs,
Yaniv Frishman and Ayellet Tal.
IEEE Symposium on Information Visualization, October 2004, 191-198.
Abstract:
This paper presents an algorithm for drawing a sequence of graphs that contain an inherent grouping of their vertex set into clusters. It differs from previous work on dynamic graph drawing in the emphasis that is put on maintaining the clustered structure of the graph during incremental layout. The algorithm works online and allows arbitrary modifications to the graph. It is generic and can be implemented using a wide range of static force-directed graph layout tools. The paper introduces several metrics for measuring layout quality of dynamic clustered graphs. The performance of our algorithm is analyzed using these metrics. The algorithm has been successfully applied to visualizing mobile object software.
Relevance Feedback for 3D Shape Retrieval,
George Leifman, Ron Meir and Ayellet Tal.
The 5th Israel-Korea Bi-National Conference on Geometric Modeling and Computer Graphics, October 2004, 15-19.
Abstract:
The last few years have witnessed an increasing interest in shape-based retrieval of 3D models for computer graphics applications. Object similarity is a subjective matter, dependent on the human viewer, since objects have semantics and are not mere geometric entities. Relevance feedback aims at addressing the subjectivity of similarity. This paper presents a novel relevance feedback algorithm which is based both on supervised and unsupervised feature extraction techniques. We show that the proposed approach produces good results and outperforms previously proposed techniques.
Modeling by Example,
Thomas Funkhouser, Michael Kazhdan, Philip Shilane, Patrick Min, William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, David Dobkin.
SIGGRAPH 2004, ACM Transactions on Graphics, Vol 23, No 3, August 2004, 652-663.
Abstract:
In this paper, we investigate a data-driven synthesis approach to constructing 3D geometric surface models. We provide methods with which a user can search a large database of 3D meshes to find parts of interest, cut the desired parts out of the meshes with intelligent scissoring, and composite them together in different ways to form new objects. The main benefit of this approach is that it is both easy to learn and able to produce highly detailed geometric models -- the conceptual design for new models comes from the user, while the geometric details come from examples in the database. The focus of the paper is on the main research issues motivated by the proposed approach: (1) interactive segmentation of 3D surfaces, (2) shape-based search to find 3D models with parts matching a query, and (3) composition of parts to form new models. We provide new research contributions on all three topics and incorporate them into a prototype modeling system. Experience with our prototype system indicates that it allows untrained users to create interesting and detailed 3D models.
ICA using kernel entropy estimation with NlogN complexity,
Sarit Shwartz, Michael Zibulevsky and Yoav Y. Schechner.
Proc. ICA 2004: pp. 422-429 (2004).
Abstract:
Mutual information (MI) is a common criterion in independent component analysis (ICA) optimization. MI is derived from probability density functions (PDF). There are scenarios in which assuming a parametric form for the PDF leads to poor performance. Therefore, the need arises for non-parametric PDF and MI estimation. Existing nonparametric algorithms suffer from high complexity, particularly in high dimensions. To counter this obstacle, we present an ICA algorithm based on accelerated kernel entropy estimation. It achieves both high separation performance and low computational complexity. For K sources with N samples, our ICA algorithm has an iteration complexity of at most O(KN logN + K2N).
Clear underwater vision,
Yoav Y. Schechner and Nir Karpel.
Proc. IEEE CVPR, Vol. 1, pp. 536-543 (2004).
Abstract:
Underwater imaging is important for scientific research and technology, as well as for popular activities. We present a computer vision approach which easily removes degradation effects in underwater vision. We analyze the physical effects of visibility degradation. We show that the main degradation effects can be associated with partial polarization of light. We therefore present an algorithm which inverts the image formation process, to recover a good visibility image of the object. The algorithm is based on a couple of images taken through a polarizer at different orientations. As a by product, a distance map of the scene is derived as well. We successfully used our approach when experimenting in the sea using a system we built. We obtained great improvement of scene contrast and color correction, and nearly doubled the underwater visibility range.
Uncontrolled modulation imaging,
Yoav Y. Schechner and Shree K. Nayar.
Proc. IEEE CVPR, Vol. 2, pp. 197-204 (2004).
Abstract:
To obtain high dynamic range or hyperspectral images, multiple frames of the same field of view are acquired while the imaging settings are modulated; images are taken at different exposures or through different wavelength bands. A major problem associated with such modulations has been the need for perfect synchronization between image acquisition and modulation control. In the past, this problem has been addressed by using sophisticated servo-control mechanisms. In this work, we show that the process of modulation imaging can be made much simpler by using vision algorithms to automatically relate each acquired frame to its corresponding modulation level. This correspondence is determined solely from the acquired image sequence and does not require measurement or control of the modulation. The image acquisition and the modulation work continuously, in parallel, and independently. We refer to this approach as computational synchronization. It makes the imaging process simple and easy to implement. We have developed a prototype modulation imaging system that uses computational synchronization and used it to acquire high dynamic range and multispectral images.
Attenuating Natural Flicker Patterns,
Yoav Y. Schechner and Nir Karpel.
MTS/IEEE OCEANS, pp. 1262-1268 (2004).
Abstract:
Waves on the water surface create spatiotemporal illumination patterns underwater. Concave regions on the surface diverge light rays refracting into the water, while convex regions create convergence of rays (caustics). Therefore, the natural illumination of underwater objects is spatially varying. Moreover, in shallow water this nonuniform intensity distribution varies significantly in time, as the water surface changes with the wave motion. In this paper we present a method that attenuates these illumination patterns, and results in an image which appears as if taken under much more stable and uniform illumination. The method is based on just a few consecutive frames taken of the scene. These frames are analyzed by a non-linear algorithm which preserves consistent image components while filtering out fluctuations. The use of the nonlinear algorithm alleviates the need for long acquisition periods and is therefore fast. We demonstrate its effectiveness and efficiency in underwater experiments.
Recovering Scenes by Polarization Analysis,
Yoav Y. Schechner and Nir Karpel.
MTS/IEEE OCEANS, pp. 1255-1261 (2004).
Abstract:
We devise a computer vision approach which removes degradation effects in optical underwater imaging. It exploits natural illumination. By analysis of the physical effects of visibility degradation, we associate natural backscatter with partial polarization of light. This is contrary to prior studies which have associated polarization with light emanating from the objects, rather than the backscatter. Our algorithm takes advantage of this aspect to invert the image formation process. In this paper we show that our method achieves a much better visibility recovery, compared to prior methods. This is demonstrated in underwater experimentation in the sea. In addition, the physics-based analysis of the polarization filtered images recovers a range-map of the scene. This allows 3D rendering of the scene from various viewpoints.
2003
Hierarchical Mesh Decomposition using Fuzzy Clustering and Cuts,
Sagi Katz and Ayellet Tal.
SIGGRAPH 2003, ACM Transactions on Graphics, Volume 22 , Issue 3, July 2003, 954-961.
Abstract:
Cutting up a complex object into simpler sub-objects is a fundamental problem in various disciplines. In image processing, images are segmented while in computational geometry, solid polyhedra are decomposed. In recent years, in computer graphics, polygonal meshes are decomposed into sub-meshes. In this paper we propose a novel hierarchical mesh decomposition algorithm. Our algorithm computes a decomposition into the meaningful components of a given mesh, which generally refers to segmentation at regions of deep concavities. The algorithm also avoids over-segmentation and jaggy boundaries between the components. Finally, we demonstrate the utility of the algorithm in control-skeleton extraction.
Signatures of 3D Models for Retrieval,
George Leifman, Sagi Katz, Ayellet Tal and Ron Meir.
The 4th Israel-Korea Bi-National Conference on Geometric Modeling and Computer Graphics, February 2003, 159-163.
Abstract:
This paper examines the problem of searching a database of three-dimensional objects for objects similar to a given object. We present two novel signatures for 3D retrieval. We also introduce several measures that can be used for comparing the quality of signatures. Finally, we describe an experimental study where various signatures are compared, and show that one of the proposed signatures outperforms other signatures discussed in the past.
Inner-Cover of Non-Convex Shapes,
D. Cohen-Or, S. Lev-Yehudi, A. Karol and A. Tal.
International Journal of Shape Modeling, 9:2 (2003), 223-238.
Abstract:
We present an algorithm that for a given simple non-convex polygon P finds an approximate inner-cover by large convex polygons. The algorithm is based on an initial partitioning of P into a set C of disjoint convex polygons which are an exact tessellation of P. The algorithm then builds a set of large convex polygons contained in P by constructing the convex hulls of subsets of C. We discuss different strategies for selecting the subsets and we claim that in most cases our algorithm produces an effective approximation of P.
A theory of multiplexed illumination,
Yoav Y. Schechner, Shree K. Nayar and Peter N. Belhumeur.
Proc. IEEE ICCV, Vol. 2, pp. 808-815 (2003).
Abstract:
Imaging of objects under variable lighting directions is an important and frequent practice in computer vision and image-based rendering. We introduce an approach that significantly improves the quality of such images. Traditional methods for acquiring images under variable illumination directions use only a single light source per acquired image. In contrast, our approach is based on a multiplexing principle, in which multiple light sources illuminate the object simultaneously from different directions. Thus, the object irradiance is much higher. The acquired images are then computationally demultiplexed. The number of image acquisitions is the same as in the single-source method. The approach is useful for imaging dim object areas. We give the optimal code by which the illumination should be multiplexed to obtain the highest quality output. For n images corresponding to n light sources, the noise is reduced by ?n/2 relative to the signal. This noise reduction translates to a faster acquisition time or an increase in density of illumination direction samples. It also enables one to use lighting with high directional resolution using practical setups, as we demonstrate in our experiments.
Generalized mosaicing: High dynamic range in a wide field of view,
Yoav Y. Schechner and Shree K. Nayar.
International Journal of Computer Vision 53 pp. 245-267 (2003).
Abstract:
We present an approach that significantly enhances the capabilities of traditional image mosaicking. The key observation is that as a camera moves, it senses each scene point multiple times. We rigidly attach to the camera an optical filter with spatially varying properties, so that multiple measurements are obtained for each scene point under different optical settings. Fusing the data captured in the multiple images yields an image mosaic that includes additional information about the scene. We refer to this approach as generalized mosaicing. In this paper we show that this approach can significantly extend the optical dynamic range of any given imaging system by exploiting vignetting effects. We derive the optimal vignetting configuration and implement it using an external filter with spatially varying transmittance.We also derive efficient scene sampling conditions as well as ways to self calibrate the vignetting effects. Maximum likelihood is used for image registration and fusion. In an experiment we mounted such a filter on a standard 8-bit video camera, to obtain an image panorama with dynamic range comparable to imaging with a 16-bit camera.
Polarization-based vision through haze,
Yoav Y. Schechner, Srinivas G. Narasimhan, and Shree K. Nayar.
Applied Optics 42, No. 3, pp. 511-525 (2003),
Special issue about Light and Color in the Open Air.

Abstract:
We present an approach for easily removing the effects of haze from passively acquired images. Our approach is based on the fact that usually the natural illuminating light scattered by atmospheric particles _airlight_ is partially polarized. Optical filtering alone cannot remove the haze effects, except in restricted situations. Our method, however, stems from physics-based analysis that works under a wide range of atmospheric and viewing conditions, even if the polarization is low. The approach does not rely on specific scattering models such as Rayleigh scattering and does not rely on the knowledge of illumination directions. It can be used with as few as two images taken through a polarizer at different orientations. As a byproduct, the method yields a range map of the scene, which enables scene rendering as if imaged from different viewpoints. It also yields information about the atmospheric particles. We present experimental results of complete dehazing of outdoor scenes, in far-from-ideal conditions for polarization filtering. We obtain a great improvement of scene contrast and correction of color.
 
 
CG&M Lab    Contact Us EE Labs EE Department Technion