Frank Nielsen :: List of selected publications

Frank Nielsen Steering self-learning distance algorithms Communications of the ACM, (52) 11 , pp. VE, November 2009. PDF    10.1145.1592761    Search web Abstract: The concept of distance expresses the distortion measure between any pair of entities lying in a common space. Distances are ubiquitous in computational science. We concisely review the role and recent development of distance families in computer science. Nowadays, the most appropriate distance functions of complex high-dimensional data sets cannot anymore be guessed manually and hard-coded, but rather need to be fully automatically learnt, or even better partially user-steered for personalization. We envision a whole new generation of personalized information retrieval systems incorporating self-learning built-in distance modules, and providing user interfaces to better take into considerations users/groups subjective tastes. BibTeX label: @article{2009-SteeringLearningDistance-CACM , author={Frank Nielsen} , title={Steering self-learning distance algorithms} , journal={Communications of the ACM} , month={November} , year={2009} , volume={52} , number={11} , pages={VE} , doi={10.1145.1592761} , abstract={ The concept of distance expresses the distortion measure between any pair of entities lying in a common space. Distances are ubiquitous in computational science. We concisely review the role and recent development of distance families in computer science. Nowadays, the most appropriate distance functions of complex high-dimensional data sets cannot anymore be guessed manually and hard-coded, but rather need to be fully automatically learnt, or even better partially user-steered for personalization. We envision a whole new generation of personalized information retrieval systems incorporating self-learning built-in distance modules, and providing user interfaces to better take into considerations users/groups subjective tastes. } }

Richard Nock and Frank Nielsen Bregman divergences and surrogates for learning IEEE Transactions on Pattern Matching and Machine Intelligence, (31) 11 , pp. 2048-2059, November 2009. PDF    10.1109/TPAMI.2008.225    Search web Abstract: Bartlett et al. (2006) recently proved that a ground condition for surrogates, classification calibration, ties up their consistent minimization to that of the classification risk, and left as an important problem the algorithmic questions about their minimization. In this paper, we address this problem for a wide set which lies at the intersection of classification calibrated surrogates and those of Murata et al. (2004). This set coincides with those satisfying three common assumptions about surrogates. Equivalent expressions for the members-sometimes well known-follow for convex and concave surrogates, frequently used in the induction of linear separators and decision trees. Most notably, they share remarkable algorithmic features: for each of these two types of classifiers, we give a minimization algorithm provably converging to the minimum of any such surrogate. While seemingly different, we show that these algorithms are offshoots of the same "master" algorithm. This provides a new and broad unified account of different popular algorithms, including additive regression with the squared loss, the logistic loss, and the top-down induction performed in CART, C4.5. Moreover, we show that the induction enjoys the most popular boosting features, regardless of the surrogate. Experiments are provided on 40 readily available domains. BibTeX label: @article{2009-BregmanSurrogateLearning-PAMI , author={Richard Nock and Frank Nielsen} , title={Bregman divergences and surrogates for learning} , journal={IEEE Transactions on Pattern Matching and Machine Intelligence} , month={November} , year={2009} , volume={31} , number={11} , pages={2048-2059} , doi={10.1109/TPAMI.2008.225} , abstract={ Bartlett et al. (2006) recently proved that a ground condition for surrogates, classification calibration, ties up their consistent minimization to that of the classification risk, and left as an important problem the algorithmic questions about their minimization. In this paper, we address this problem for a wide set which lies at the intersection of classification calibrated surrogates and those of Murata et al. (2004). This set coincides with those satisfying three common assumptions about surrogates. Equivalent expressions for the members-sometimes well known-follow for convex and concave surrogates, frequently used in the induction of linear separators and decision trees. Most notably, they share remarkable algorithmic features: for each of these two types of classifiers, we give a minimization algorithm provably converging to the minimum of any such surrogate. While seemingly different, we show that these algorithms are offshoots of the same "master" algorithm. This provides a new and broad unified account of different popular algorithms, including additive regression with the squared loss, the logistic loss, and the top-down induction performed in CART, C4.5. Moreover, we show that the induction enjoys the most popular boosting features, regardless of the surrogate. Experiments are provided on 40 readily available domains. } }

Frank Nielsen and Richard Nock Approximating smallest enclosing balls with applications to machine learning International Journal on Computational Geometry and Applications, (19) 5, October 2009. PDF    Search web Abstract: In this paper, we first survey prior work for computing exactly or approximately the smallest enclosing balls of point or ball sets in Euclidean spaces. We classify previous work into three categories: (1) purely combinatorial, (2) purely numerical, and (3) recent mixed hybrid algorithms based on coresets. We then describe two novel tailored algorithms for computing arbitrary close approximations of the smallest enclosing Euclidean ball of balls. These deterministic heuristics are based on solving relaxed decision problems using a primal-dual method. The primal-dual method is interpreted geometrically as solving for a minimum covering set, or dually as seeking for a minimum piercing set. Finally, we present some applications in machine learning of the exact and approximate smallest enclosing ball procedure, and discuss about its extension to non-Euclidean information- theoretic spaces. BibTeX label: @article{2009-EnclosingBallMachineLearning-IJCGA , author={Frank Nielsen and Richard Nock} , title={Approximating smallest enclosing balls with applications to machine learning} , journal={International Journal on Computational Geometry and Applications} , month={October} , year={2009} , volume={19} , number={5} , abstract={ In this paper, we first survey prior work for computing exactly or approximately the smallest enclosing balls of point or ball sets in Euclidean spaces. We classify previous work into three categories: (1) purely combinatorial, (2) purely numerical, and (3) recent mixed hybrid algorithms based on coresets. We then describe two novel tailored algorithms for computing arbitrary close approximations of the smallest enclosing Euclidean ball of balls. These deterministic heuristics are based on solving relaxed decision problems using a primal-dual method. The primal-dual method is interpreted geometrically as solving for a minimum covering set, or dually as seeking for a minimum piercing set. Finally, we present some applications in machine learning of the exact and approximate smallest enclosing ball procedure, and discuss about its extension to non-Euclidean information- theoretic spaces.} }

Yukiko Matsuoka and Jason E. Shoemaker and Natalia Polouliakh and Yukiko Muramoto and Ken Fujii and Samik Ghosh and Richard Nock and Frank Nielsen and Yoshihiro Kawaoka and Hiroaki Kitano A systems biology approach to influenza virus infection Tenth International Conference on Systems Biology (ICSB)September 2009. (Stanford, USA) Search web Abstract: Viral infections have a tremendous impact on human health, yet little is known about pathogen-host interactions. Systematic approach and comprehensive efforts are now needed to analyze virus infections in different biological systems, identify pathogen-host interactions, characterize host cell responses, and correlate the data with in silico modeling and simulation. Among various viruses, influenza viruses are an ideal model system due to their impact on human health and the global economy. Looking at the current outbreak of new influenza, understanding of the mechanism of host-virus interactions and cellular responses to influenza infection is even more coveted for development of novel preventative and therapeutic treatments. To enable systematic research, it is important to gather integrated data on virus replication and pathogenicity, host cell interaction partners, and the host genes that are differentially regulated upon virus infection. Comprehensive data analysis and integration is expected to identify host factors, machineries, pathways, and responsenetworks that are critical in influenza viral infection, and biomarkers that predict the outcome of an infection in particular. As for the ffrst step of our comprehensive efforts, we study the cellular transcriptome in response to viral infection of influenza, in particular, viruses of high or low pathogenicity. Data analysis and modeling of cellular response networks will be carried out with a novel clustering method. In this poster, we present our first effort to analyze the microarray data on the host cell responses induced by the influenza viruses of high or low pathogenicity with manifold clustering method, and characterize the cellular transcriptomes in influenza virusinfected primary cells. We would try to elucidate the difference in mechanism of host cell responses by high or low pathogenicity viruses. BibTeX label: @inproceedings{2009-C-Influenza-ICSB , author={Yukiko Matsuoka and Jason E. Shoemaker and Natalia Polouliakh and Yukiko Muramoto and Ken Fujii and Samik Ghosh and Richard Nock and Frank Nielsen and Yoshihiro Kawaoka and Hiroaki Kitano} , title={A systems biology approach to influenza virus infection} , booktitle={Tenth International Conference on Systems Biology (ICSB)} , month={September} , year={2009} , address={Stanford, USA} , abstract={ Viral infections have a tremendous impact on human health, yet little is known about pathogen-host interactions. Systematic approach and comprehensive efforts are now needed to analyze virus infections in different biological systems, identify pathogen-host interactions, characterize host cell responses, and correlate the data with in silico modeling and simulation. Among various viruses, influenza viruses are an ideal model system due to their impact on human health and the global economy. Looking at the current outbreak of new influenza, understanding of the mechanism of host-virus interactions and cellular responses to influenza infection is even more coveted for development of novel preventative and therapeutic treatments. To enable systematic research, it is important to gather integrated data on virus replication and pathogenicity, host cell interaction partners, and the host genes that are differentially regulated upon virus infection. Comprehensive data analysis and integration is expected to identify host factors, machineries, pathways, and responsenetworks that are critical in influenza viral infection, and biomarkers that predict the outcome of an infection in particular. As for the ffrst step of our comprehensive efforts, we study the cellular transcriptome in response to viral infection of influenza, in particular, viruses of high or low pathogenicity. Data analysis and modeling of cellular response networks will be carried out with a novel clustering method. In this poster, we present our first effort to analyze the microarray data on the host cell responses induced by the influenza viruses of high or low pathogenicity with manifold clustering method, and characterize the cellular transcriptomes in influenza virusinfected primary cells. We would try to elucidate the difference in mechanism of host cell responses by high or low pathogenicity viruses.} }

Vincent Garcia and Frank Nielsen and Richard Nock Levels of details for Gaussian mixture models Ninth Asian Conference on Computer Vision (ACCV)September 2009. (Xi'an, China) Search web Abstract: BibTeX label: @inproceedings{2009-C-LGMM-Springer , author={Vincent Garcia and Frank Nielsen and Richard Nock} , title={Levels of details for Gaussian mixture models} , booktitle={Ninth Asian Conference on Computer Vision (ACCV)} , month={September} , year={2009} , address={Xi'an, China} , publisher={Springer-Verlag} }

Frank Nielsen and Richard Nock Sided and Symmetrized Bregman Centroids IEEE Transactions on Information Theory, (55) 6 , pp. 2048-2059, June 2009. PDF    10.1109/TIT.2009.2018176    Search web Abstract: In this paper, we generalize the notions of centroids and barycenters) to the broad class of information-theoretic distortion measures called Bregman divergences. Bregman divergences form a rich and versatile family of distances that unifies quadratic Euclidean distances with various well-known statistical entropic measures. Since besides the squared Euclidean distance, Bregman divergences are asymmetric, we consider the left-sided and right-sided centroids and the symmetrized centroids as minimizers of average Bregman distortions. We prove that all three centroids are unique and give closed-form solutions for the sided centroids that are generalized means. Furthermore, we design a provably fast and efficient arbitrary close approximation algorithm for the symmetrized centroid based on its exact geometric characterization. The geometric approximation algorithm requires only to walk on a geodesic linking the two left/right-sided centroids. We report on our implementation for computing entropic centers of image histogram clusters and entropic centers of multivariate normal distributions that are useful operations for processing multimedia information and retrieval. These experiments illustrate that our generic methods compare favorably with former limited ad hoc methods. BibTeX label: @article{2009-BregmanCentroids-TIT , author={Frank Nielsen and Richard Nock} , title={Sided and Symmetrized Bregman Centroids} , journal={IEEE Transactions on Information Theory} , month={June} , year={2009} , volume={55} , number={6} , pages={2048-2059} , doi={10.1109/TIT.2009.2018176} , abstract={ In this paper, we generalize the notions of centroids and barycenters) to the broad class of information-theoretic distortion measures called Bregman divergences. Bregman divergences form a rich and versatile family of distances that unifies quadratic Euclidean distances with various well-known statistical entropic measures. Since besides the squared Euclidean distance, Bregman divergences are asymmetric, we consider the left-sided and right-sided centroids and the symmetrized centroids as minimizers of average Bregman distortions. We prove that all three centroids are unique and give closed-form solutions for the sided centroids that are generalized means. Furthermore, we design a provably fast and efficient arbitrary close approximation algorithm for the symmetrized centroid based on its exact geometric characterization. The geometric approximation algorithm requires only to walk on a geodesic linking the two left/right-sided centroids. We report on our implementation for computing entropic centers of image histogram clusters and entropic centers of multivariate normal distributions that are useful operations for processing multimedia information and retrieval. These experiments illustrate that our generic methods compare favorably with former limited ad hoc methods. } }

Frank Nielsen and Aurelien Serandour Accuracy of distance metric learning algorithms Workshop on Data Mining using Matrices and Tensors (DMMT)June 2009. (Paris, France) 10.1145/1581114.1581115    Search web Abstract: In this paper, we wanted to compare distance metric-learning algorithms on UCI datasets. We wanted to assess the accuracy of these algorithms in many situations, perhaps some that they were not initially designed for. We looked for many algorithms and chose four of them based on our criteria. We also selected six UCI datasets. From the data's labels, we create similarity dataset that will be used to train and test the algorithms. The nature of each dataset is different (size, dimension), and the algorithms' results may vary because of these parameters. We also wanted to have some robust algorithms on dataset whose similarity is not perfect, whose the labels are no well defined. This occurs in multi-labeled datasets or even worse in human-built ones. To simulate this, we injected contradictory data and observed the behavior of the algorithms. This study seeks for a reliable algorithm in such scenarios keeping in mind future uses in recommendation processes. BibTeX label: @inproceedings{2009-C-MetricLearning-ACM , author={Frank Nielsen and Aurelien Serandour} , title={Accuracy of distance metric learning algorithms} , booktitle={Workshop on Data Mining using Matrices and Tensors (DMMT)} , month={June} , year={2009} , address={Paris, France} , publisher={ACM} , doi={10.1145/1581114.1581115} , abstract={ In this paper, we wanted to compare distance metric-learning algorithms on UCI datasets. We wanted to assess the accuracy of these algorithms in many situations, perhaps some that they were not initially designed for. We looked for many algorithms and chose four of them based on our criteria. We also selected six UCI datasets. From the data's labels, we create similarity dataset that will be used to train and test the algorithms. The nature of each dataset is different (size, dimension), and the algorithms' results may vary because of these parameters. We also wanted to have some robust algorithms on dataset whose similarity is not perfect, whose the labels are no well defined. This occurs in multi-labeled datasets or even worse in human-built ones. To simulate this, we injected contradictory data and observed the behavior of the algorithms. This study seeks for a reliable algorithm in such scenarios keeping in mind future uses in recommendation processes. } }

Frank Nielsen and Richard Nock The dual Voronoi diagrams with respect to representational Bregman divergences International Symposium on Voronoi Diagrams (ISVD)June 2009. (DTU Lyngby, Denmark) PDF    Search web Abstract: We present a generalization of Bregman Voronoi diagrams induced by a Bregman divergence acting on a representation function. Bregman divergences are canonical distortion measures of flat spaces induced by strictly convex and differentiable functions, called Bregman generators. Considering a representation function further allows us to conveniently embed the not necessarily flat source space into a dually flat space for which the dual Voronoi diagrams can be derived from an equivalent power affine diagram. We explain the fundamental dualities induced by the pair of Legendre convex conjugates coupled with a pair of conjugate representations. In particular, we show that Amari's celebrated family of $\alpha$-divergences and Eguchi and Copas's $\beta$-divergences are two cases of representational Bregman divergences that are often considered in information geometry. We report closedform formula for their centroids and describe their dual Voronoi diagrams on the induced statistical manifolds. BibTeX label: @inproceedings{2009-C-RepresentationalBregmanVoronoi-ISVD , author={Frank Nielsen and Richard Nock} , title={The dual Voronoi diagrams with respect to representational Bregman divergences} , booktitle={International Symposium on Voronoi Diagrams (ISVD)} , month={June} , year={2009} , address={DTU Lyngby, Denmark} , publisher={IEEE} , abstract={ We present a generalization of Bregman Voronoi diagrams induced by a Bregman divergence acting on a representation function. Bregman divergences are canonical distortion measures of flat spaces induced by strictly convex and differentiable functions, called Bregman generators. Considering a representation function further allows us to conveniently embed the not necessarily flat source space into a dually flat space for which the dual Voronoi diagrams can be derived from an equivalent power affine diagram. We explain the fundamental dualities induced by the pair of Legendre convex conjugates coupled with a pair of conjugate representations. In particular, we show that Amari's celebrated family of $\alpha$-divergences and Eguchi and Copas's $\beta$-divergences are two cases of representational Bregman divergences that are often considered in information geometry. We report closedform formula for their centroids and describe their dual Voronoi diagrams on the induced statistical manifolds. } }

Frank Nielsen and Paolo Piro and Michel Barlaud Bregman vantage point trees for efficient nearest neighbor queries IEEE International Conference on Multimedia and Expo (ICME), pp. 878-881, June 2009. (New York City, USA) PDF    10.1109/ICME.2009.5202635    Search web Abstract: Nearest Neighbor (NN) retrieval is a crucial tool of many computer vision tasks. Since the brute-force naive search is too time consuming for most applications, several tailored data structures have been proposed to improve the efficiency of NN search. Among these, vantage point tree (vp-tree) was introduced for information retrieval in metric spaces. Vptrees have recently shown very good performances for image patch retrieval with respect to the L2 metric. In this paper we generalize the seminal vp-tree construction and search algorithms to the broader class of Bregman divergences. These distorsion measures are preferred in many cases, as they also handle entropic distances (e.g., Kullback-Leibler divergence) besides quadratic distances. We also extend vp-tree to deal with symmetrized Bregman divergences, which are commonplace in applications of content-based multimedia retrieval. We evaluated performances of our Bvp-tree for exact and approximate NN search on two image feature datasets. Our results show good performances of Bvp-tree, specially for symmetrized Bregman NN queries. BibTeX label: @inproceedings{2009-BregmanVantagePointTree-IEEE , author={Frank Nielsen and Paolo Piro and Michel Barlaud} , title={ Bregman vantage point trees for efficient nearest neighbor queries } , booktitle={IEEE International Conference on Multimedia and Expo (ICME)} , month={June} , year={2009} , pages={878-881} , address={New York City, USA} , publisher={IEEE} , doi={10.1109/ICME.2009.5202635} , abstract={ Nearest Neighbor (NN) retrieval is a crucial tool of many computer vision tasks. Since the brute-force naive search is too time consuming for most applications, several tailored data structures have been proposed to improve the efficiency of NN search. Among these, vantage point tree (vp-tree) was introduced for information retrieval in metric spaces. Vptrees have recently shown very good performances for image patch retrieval with respect to the L2 metric. In this paper we generalize the seminal vp-tree construction and search algorithms to the broader class of Bregman divergences. These distorsion measures are preferred in many cases, as they also handle entropic distances (e.g., Kullback-Leibler divergence) besides quadratic distances. We also extend vp-tree to deal with symmetrized Bregman divergences, which are commonplace in applications of content-based multimedia retrieval. We evaluated performances of our Bvp-tree for exact and approximate NN search on two image feature datasets. Our results show good performances of Bvp-tree, specially for symmetrized Bregman NN queries. } }

Frank Nielsen A concise and practical introduction to programming algorithms in Java ( pp. XXVIII, 252 pages) , Undergraduate Topics in Computer Science (UTiCS) , Springer-Verlag , March 2009. PDF    Search web Abstract: BibTeX label: @book{2009-JavaIntroduction-Springer , author={Frank Nielsen} , title={A concise and practical introduction to programming algorithms in Java} , month={March} , year={2009} , pages={XXVIII, 252 pages} , series={ Undergraduate Topics in Computer Science (UTiCS) } , publisher={Springer-Verlag} }

Frank Nielsen A volume shader for quantum voronoi diagrams inside the 3D Bloch ball ShaderX7: Advanced Rendering Techniques , March 2009. Search web Abstract: BibTeX label: @incollection{2009-QuantumVoronoiGPU-CRM , author={Frank Nielsen} , title={A volume shader for quantum voronoi diagrams inside the 3D Bloch ball} , booktitle={ShaderX7: Advanced Rendering Techniques} , month={March} , year={2009} , publisher={Charles River Media/Thomson Publishing} }

Natalia Polouliakh and Richard Nock and Frank Nielsen and Hiroaki Kitano G-protein coupled receptor signaling architecture of mammalian immune cells Public Libary of Science One, (4) 1 , pp. e4189, January 2009. PDF    10.1371/journal.pone.0004189    Search web Abstract: A series of recent studies on large-scale networks of signaling and metabolic systems revealed that a certain network structure often called "bow-tie network" are observed. In signaling systems, bow-tie network takes a form with diverse and redundant inputs and outputs connected via a small numbers of core molecules. While arguments have been made that such network architecture enhances robustness and evolvability of biological systems, its functional role at a cellular level remains obscure. A hypothesis was proposed that such a network function as a stimuli-reaction classifier where dynamics of core molecules dictate downstream transcriptional activities, hence physiological responses against stimuli. In this study, we examined whether such hypothesis can be verified using experimental data from Alliance for Cellular Signaling (AfCS) that comprehensively measured GPCR related ligands response for B-cell and macrophage. In a GPCR signaling system, cAMP and Ca2+ act as core molecules. Stimuli-response for 32 ligands to B-Cells and 23 ligands to macrophages has been measured. We found that ligands with correlated changes of cAMP and Ca2+ tend to cluster closely together within the hyperspaces of both cell types and they induced genes involved in the same cellular processes. It was found that ligands inducing cAMP synthesis activate genes involved in cell growth and proliferation; cAMP and Ca2+ molecules that increased together form a feedback loop and induce immune cells to migrate and adhere together. In contrast, ligands without a core molecules response are scattered throughout the hyperspace and do not share clusters. G-protein coupling receptors together with immune response specific receptors were found in cAMP and Ca2+ activated clusters. Analyses have been done on the original software applicable for discovering "bow-tie" network architectures within the complex network of intracellular signaling where ab initio clustering has been implemented as well. Groups of potential transcription factors for each specific group of genes were found to be partly conserved across B-Cell and macrophage. A series of findings support the hypothesis. BibTeX label: @article{2009-MamelianImmuneSystems-PLoSOne , author={Natalia Polouliakh and Richard Nock and Frank Nielsen and Hiroaki Kitano} , title={G-protein coupled receptor signaling architecture of mammalian immune cells} , journal={Public Libary of Science One} , month={January} , year={2009} , volume={4} , number={1} , pages={e4189} , doi={10.1371/journal.pone.0004189} , abstract={ A series of recent studies on large-scale networks of signaling and metabolic systems revealed that a certain network structure often called "bow-tie network" are observed. In signaling systems, bow-tie network takes a form with diverse and redundant inputs and outputs connected via a small numbers of core molecules. While arguments have been made that such network architecture enhances robustness and evolvability of biological systems, its functional role at a cellular level remains obscure. A hypothesis was proposed that such a network function as a stimuli-reaction classifier where dynamics of core molecules dictate downstream transcriptional activities, hence physiological responses against stimuli. In this study, we examined whether such hypothesis can be verified using experimental data from Alliance for Cellular Signaling (AfCS) that comprehensively measured GPCR related ligands response for B-cell and macrophage. In a GPCR signaling system, cAMP and Ca2+ act as core molecules. Stimuli-response for 32 ligands to B-Cells and 23 ligands to macrophages has been measured. We found that ligands with correlated changes of cAMP and Ca2+ tend to cluster closely together within the hyperspaces of both cell types and they induced genes involved in the same cellular processes. It was found that ligands inducing cAMP synthesis activate genes involved in cell growth and proliferation; cAMP and Ca2+ molecules that increased together form a feedback loop and induce immune cells to migrate and adhere together. In contrast, ligands without a core molecules response are scattered throughout the hyperspace and do not share clusters. G-protein coupling receptors together with immune response specific receptors were found in cAMP and Ca2+ activated clusters. Analyses have been done on the original software applicable for discovering "bow-tie" network architectures within the complex network of intracellular signaling where ab initio clustering has been implemented as well. Groups of potential transcription factors for each specific group of genes were found to be partly conserved across B-Cell and macrophage. A series of findings support the hypothesis. } }

Richard Nock and Pascal Vaillant and Claudia Henry and Frank Nielsen Soft memberships for spectral clustering, with application to permeable language distinction Pattern Recognition, (42) 1 , pp. 43-53, January 2009. PDF    10.1016/j.patcog.2008.06.024    Search web Abstract: Recently, a large amount of work has been devoted to the study of spectral clustering-a powerful unsupervised classification method. This paper brings contributions to both its foundations, and its applications to text classification. Departing from the mainstream, concerned with hard membership, we study the extension of spectral clustering to soft membership (probabilistic, EM style) assignments. One of its key features is to avoid the complexity gap of hard membership. We apply this theory to a challenging problem, text clustering for languages having permeable borders, via a novel construction of Markov chains from corpora. Experiments with a readily available code clearly display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus. BibTeX label: @article{2009-SoftSpectralClustering-PR , author={Richard Nock and Pascal Vaillant and Claudia Henry and Frank Nielsen} , title={Soft memberships for spectral clustering, with application to permeable language distinction} , journal={Pattern Recognition} , month={January} , year={2009} , volume={42} , number={1} , pages={43-53} , doi={10.1016/j.patcog.2008.06.024} , abstract={ Recently, a large amount of work has been devoted to the study of spectral clustering-a powerful unsupervised classification method. This paper brings contributions to both its foundations, and its applications to text classification. Departing from the mainstream, concerned with hard membership, we study the extension of spectral clustering to soft membership (probabilistic, EM style) assignments. One of its key features is to avoid the complexity gap of hard membership. We apply this theory to a challenging problem, text clustering for languages having permeable borders, via a novel construction of Markov chains from corpora. Experiments with a readily available code clearly display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus. } }

Frank Nielsen Emerging trends in visual computing ( pp. XII, 387 pages) , Lecture Notes in Computer Science , Springer-Verlag , Frank Nielsen, March 2009. PDF    Search web Abstract: BibTeX label: @book{2009-ETVC-Springer , author={Frank Nielsen} , title={Emerging trends in visual computing} , month={ March } , year={2009} , pages={XII, 387 pages} , series={ Lecture Notes in Computer Science } , publisher={Springer-Verlag} }

Richard Nock and Frank Nielsen Intrinsic geometries in learning Emerging trends in visual computing (ETVC), pp. 175-215, November 2008. (Ecole Polytechnique, Palaiseau, France) PDF    10.1007/978-3-642-00826-9_8    Search web Abstract: In a seminal paper, Amari (1998) proved that learning can be made more efficient when one uses the intrinsic Riemannian structure of the algorithms' spaces of parameters to point the gradient towards better solutions. In this paper, we show that many learning algorithms, including various boosting algorithms for linear separators, the most popular top-down decision-tree induction algorithms, and some on-line learning algorithms, are spawns of a generalization of Amari's natural gradient to some particular non-Riemannian spaces. These algorithms exploit an intrinsic dual geometric structure of the space of parameters in relationship with particular integral losses that are t be minimized. We unite some of them, such as AdaBoost, additive regression with the square loss, the logistic loss, the top-down induction performed in CART and C4.5, as a single algorithm on which we show general convergence to the optimum and explicit convergence rates under very weak assumptions. As a consequence, many of the classification calibrated surrogates of Bartlett et al. (2006) admit efficient minimization algorithms. BibTeX label: @inproceedings{2008-C-IntrinsicGeometries-ETVC , author={Richard Nock and Frank Nielsen} , title={Intrinsic geometries in learning} , booktitle={Emerging trends in visual computing (ETVC)} , month={November} , year={2008} , pages={175-215} , address={Ecole Polytechnique, Palaiseau, France} , doi={10.1007/978-3-642-00826-9_8} , abstract={ In a seminal paper, Amari (1998) proved that learning can be made more efficient when one uses the intrinsic Riemannian structure of the algorithms' spaces of parameters to point the gradient towards better solutions. In this paper, we show that many learning algorithms, including various boosting algorithms for linear separators, the most popular top-down decision-tree induction algorithms, and some on-line learning algorithms, are spawns of a generalization of Amari's natural gradient to some particular non-Riemannian spaces. These algorithms exploit an intrinsic dual geometric structure of the space of parameters in relationship with particular integral losses that are t be minimized. We unite some of them, such as AdaBoost, additive regression with the square loss, the logistic loss, the top-down induction performed in CART and C4.5, as a single algorithm on which we show general convergence to the optimum and explicit convergence rates under very weak assumptions. As a consequence, many of the classification calibrated surrogates of Bartlett et al. (2006) admit efficient minimization algorithms. } }

Frank Nielsen and Richard Nock Quantum Voronoi diagrams and Holevo channel capacity for $1$-qubit quantum states IEEE International Symposium on Information Theory (ISIT), pp. 96-100, July 2008. (Toronto, Canada) 10.1109/ISIT.2008.4594955    Search web Abstract: In this paper, we first introduce a smooth parametric family of Bregman-Csisz\'ar quantum entropies including the von Neumann and Burg quantum entropies. We then describe the dualistic nature of Voronoi diagrams for $1$-qubit quantum states inside the 3D Bloch ball representation. We show that these diagrams can be computed as Bregman Voronoi diagrams for the corresponding Bregman generator acting on Hermitian density matrices. This implies that these dual diagrams can be derived from power diagrams of balls in the Laguerre geometry, and allows one to prove by equivalence that the von Neumann quantum Voronoi diagram on the degenerated Bloch sphere of pure quantum states coincides with the ordinary Euclidean Voronoi diagram, bypassing the fact that the quantum divergence is not defined there. We then show how to compute the Holevo channel capacity of $1$-qubit quantum states, and provide a practical approximation algorithm based on Bregman core-sets. Finally, we define the quantum sided centroids that provide practical upper bounds on the Holevo capacity in linear time. BibTeX label: @inproceedings{2008-QuantumVoronoi-ISIT , author={Frank Nielsen and Richard Nock} , title={Quantum Voronoi diagrams and Holevo channel capacity for $1$-qubit quantum states} , booktitle={IEEE International Symposium on Information Theory (ISIT)} , month={July} , year={2008} , pages={96-100} , address={Toronto, Canada} , publisher={IEEE} , doi={10.1109/ISIT.2008.4594955} , abstract={ In this paper, we first introduce a smooth parametric family of Bregman-Csisz\'ar quantum entropies including the von Neumann and Burg quantum entropies. We then describe the dualistic nature of Voronoi diagrams for $1$-qubit quantum states inside the 3D Bloch ball representation. We show that these diagrams can be computed as Bregman Voronoi diagrams for the corresponding Bregman generator acting on Hermitian density matrices. This implies that these dual diagrams can be derived from power diagrams of balls in the Laguerre geometry, and allows one to prove by equivalence that the von Neumann quantum Voronoi diagram on the degenerated Bloch sphere of pure quantum states coincides with the ordinary Euclidean Voronoi diagram, bypassing the fact that the quantum divergence is not defined there. We then show how to compute the Holevo channel capacity of $1$-qubit quantum states, and provide a practical approximation algorithm based on Bregman core-sets. Finally, we define the quantum sided centroids that provide practical upper bounds on the Holevo capacity in linear time. } }

Frank Nielsen and Alexis Andre and Shigeru Tajima Real-time spherical videos from a fast rotating camera International Conference on Image Analysis and Recognition (ICIAR), pp. 326-335, June 2008. (Povoa de Varzim, Portugal) PDF    http://dx.doi.org/10.1007/978-3-540-69812-8_32    Search web Abstract: We present a new framework for the acquisition of full spherical videos using a high-speed rotating linear or area sensor equipped with a fish-eye lens. The high capture rate of the sensors allows us to reach high frame rates on the resulting videos. We describe the image processing workflows from the raw data to the full spherical frames, and we show experimental results of non-parallax panoramic videos covering the complete field of view. BibTeX label: @inproceedings{2008-SphericalVideo-ICIAR , author={Frank Nielsen and Alexis Andre and Shigeru Tajima} , title={Real-time spherical videos from a fast rotating camera} , booktitle={International Conference on Image Analysis and Recognition (ICIAR)} , month={June} , year={2008} , pages={326-335} , address={Povoa de Varzim, Portugal} , doi={http://dx.doi.org/10.1007/978-3-540-69812-8_32} , abstract={ We present a new framework for the acquisition of full spherical videos using a high-speed rotating linear or area sensor equipped with a fish-eye lens. The high capture rate of the sensors allows us to reach high frame rates on the resulting videos. We describe the image processing workflows from the raw data to the full spherical frames, and we show experimental results of non-parallax panoramic videos covering the complete field of view. } }

Shigeru Owada and Frank Nielsen and Takeo Igarashi and Ryo Haraguchi and Kazuo Nakazawa Projection plane processing for sketch-based volume segmentation International Symposium on Biomedical Imaging (ISBI), pp. 117-120, May 2008. (Paris, France) PDF    10.1109/ISBI.2008.4540946    Search web Abstract: Selecting a region of interest (ROI) within unsegmented volume data is one of the fundamental operations in volume data processing and analysis, yet it is difficult to perform the task efficiently This paper proposes several simple and intuitive sketching user interface tools for the selection task, in which the user can directly click or draw a stroke on the volume- rendered object on the screen. The main contribution is that the user's input is pre-processed in 2D domain before applying the traditional 2D-to-3D stroke elevation algorithm (the Volume Catcher system [1]). We tested the system with real- world examples to verify the effectiveness of our approach. BibTeX label: @inproceedings{2008-C-ProjectionPlaneVolumeSegmentation-ISBI , author={Shigeru Owada and Frank Nielsen and Takeo Igarashi and Ryo Haraguchi and Kazuo Nakazawa} , title={Projection plane processing for sketch-based volume segmentation} , booktitle={International Symposium on Biomedical Imaging (ISBI)} , month={May} , year={2008} , pages={117-120} , address={Paris, France} , doi={10.1109/ISBI.2008.4540946} , abstract={ Selecting a region of interest (ROI) within unsegmented volume data is one of the fundamental operations in volume data processing and analysis, yet it is difficult to perform the task efficiently This paper proposes several simple and intuitive sketching user interface tools for the selection task, in which the user can directly click or draw a stroke on the volume- rendered object on the screen. The main contribution is that the user's input is pre-processed in 2D domain before applying the traditional 2D-to-3D stroke elevation algorithm (the Volume Catcher system [1]). We tested the system with real- world examples to verify the effectiveness of our approach. } }

Frank Nielsen and Richard Nock The entropic centers of multivariate normal distributions European Workshop on Computational Geometry (EuroCG), pp. 221-224, March 2008. (Nancy, France) Search web Abstract: In this paper, we seek for a single best representative of a set of statistical multivariate normal distributions. To define the "best" center, we consider either minimizing the average or the maximum relative entropy of the center to the given set of normal distributions. Since the relative entropy is an asymmetric divergence, this yields the notion of left- and right-sided, and symmetrized entropic centroids and circumcenters along with their respective information radii. We show how to instantiate and implement for this special case of multivariate normals very recent work that tackled the broader case of finding centers of point sets with respect to Bregman divergences. BibTeX label: @inproceedings{2008-MultivariateNormalCenter-EuroCG , author={Frank Nielsen and Richard Nock} , title={The entropic centers of multivariate normal distributions} , booktitle={European Workshop on Computational Geometry (EuroCG)} , month={March} , year={2008} , pages={221-224} , address={Nancy, France} , publisher={IEEE} , abstract={In this paper, we seek for a single best representative of a set of statistical multivariate normal distributions. To define the "best" center, we consider either minimizing the average or the maximum relative entropy of the center to the given set of normal distributions. Since the relative entropy is an asymmetric divergence, this yields the notion of left- and right-sided, and symmetrized entropic centroids and circumcenters along with their respective information radii. We show how to instantiate and implement for this special case of multivariate normals very recent work that tackled the broader case of finding centers of point sets with respect to Bregman divergences. } }

Frank Nielsen An interactive tour of Voronoi diagrams on the GPU ShaderX6 , pp. 225-228, February 2008. Search web Abstract: BibTeX label: @incollection{2008-InteractiveVoronoiDiagram-CRM , author={Frank Nielsen} , title={An interactive tour of Voronoi diagrams on the GPU} , booktitle={ShaderX6} , month={February} , year={2008} , pages={225-228} , publisher={Charles River Media} }

Frank Nielsen A Volume shader for quantum Voronoi diagrams inside the 3D Bloch ball ShaderX7 , pp. 225-228, February 2008. Search web Abstract: BibTeX label: @incollection{2008-InteractiveVoronoiDiagram-CRM , author={Frank Nielsen} , title={A Volume shader for quantum Voronoi diagrams inside the 3D Bloch ball} , booktitle={ShaderX7} , month={February} , year={2008} , pages={225-228} , publisher={Charles River Media/Thomson Publishing} }

Frank Nielsen and Richard Nock On the smallest enclosing information disk Information Processing Letters, (105) 3 , pp. 93-97, January 2008. PDF    10.1016/j.ipl.2007.08.007    Search web Abstract: We present a generalization of Welzl's smallest enclosing disk algorithm [E. Welzl, Smallest enclosing disks (balls and ellipsoids), in: New Results and New Trends in Computer Science, in: Lecture Notes in Computer Science, vol. 555, Springer, 1991, pp. 359-370] BibTeX label: @article{2008-SmallestInformationDisk-IPL , author={Frank Nielsen and Richard Nock} , title={On the smallest enclosing information disk} , journal={Information Processing Letters} , month={January} , year={2008} , volume={105} , number={3} , pages={93-97} , doi={10.1016/j.ipl.2007.08.007} , abstract={We present a generalization of Welzl's smallest enclosing disk algorithm [E. Welzl, Smallest enclosing disks (balls and ellipsoids), in: New Results and New Trends in Computer Science, in: Lecture Notes in Computer Science, vol. 555, Springer, 1991, pp. 359-370]} }

Kazuhiro Hoshino and Frank Nielsen and Toshihiro Nishimura Noise reduction in CMOS image sensors for high quality imaging: The autocorrelation function filter on burst image sequences Graphics, Vision, and Image Processing, (7) 3 , pp. 17-24, November 2007. PDF    Search web Abstract: We propose a new method for image noise detection and reduction in complementary metal oxide semiconductor (CMOS) image sensors inspired from audio noise cancelling techniques. Our algorithm is based on computing efficiently the time-dependent pixel autocorrelation function (ACF) from constant time interval acquired sequences of images. We demonstrate the effectiveness of our approach for successfully detecting and reducing white noise. Further, we consider an adaptive filter that exhibits significant computational improvements making it highly practical. Finally, we report on experiments displaying the highquality imaging systems obtained in practice. BibTeX label: @article{2007-NoiseReductionCMOS-GVIP , author={Kazuhiro Hoshino and Frank Nielsen and Toshihiro Nishimura} , title={Noise reduction in CMOS image sensors for high quality imaging: The autocorrelation function filter on burst image sequences} , journal={Graphics, Vision, and Image Processing} , month={November} , year={2007} , volume={7} , number={3} , pages={17-24} , abstract={We propose a new method for image noise detection and reduction in complementary metal oxide semiconductor (CMOS) image sensors inspired from audio noise cancelling techniques. Our algorithm is based on computing efficiently the time-dependent pixel autocorrelation function (ACF) from constant time interval acquired sequences of images. We demonstrate the effectiveness of our approach for successfully detecting and reducing white noise. Further, we consider an adaptive filter that exhibits significant computational improvements making it highly practical. Finally, we report on experiments displaying the highquality imaging systems obtained in practice. } }

Shigeru Owada and Makoto Okabe and Takeo Igarashi and Frank Nielsen and Norimichi Tsumura Customized slider bars for adjusting multi-dimension parameter sets Smart Graphics (SG), pp. 230-232, June 2007. (Kyoto, Japan) 10.1007/978-3-540-73214-3_26    Search web Abstract: Application softwares usually support a single set of user interaction tools that are supposed to be optimal. It is satisfactory if the user interface (UI) is really optimal for everyone. However, since the user's intent and the preference vary one by one, such fixed toolkits may cause inefficiency of the UI. BibTeX label: @inproceedings{2007-C-CustomSlideBar-SG , author={Shigeru Owada and Makoto Okabe and Takeo Igarashi and Frank Nielsen and Norimichi Tsumura} , title={Customized slider bars for adjusting multi-dimension parameter sets} , booktitle={Smart Graphics (SG)} , month={June} , year={2007} , pages={230-232} , address={Kyoto, Japan} , doi={10.1007/978-3-540-73214-3_26} , abstract={ Application softwares usually support a single set of user interaction tools that are supposed to be optimal. It is satisfactory if the user interface (UI) is really optimal for everyone. However, since the user's intent and the preference vary one by one, such fixed toolkits may cause inefficiency of the UI. } }

Richard Nock and Frank Nielsen Self-improved gaps almost everywhere for the agnostic approximation of monomials Theoretical Computer Science, (377) 1-3 , pp. 139-150, May 2007. PDF    10.1016/j.tcs.2007.02.023    Search web Abstract: Given a learning sample, we focus on the hardness of finding monomials having low error, inside the interval bounded below by the smallest error achieved by a monomial (the best rule), and bounded above by the error of the default class (the poorest rule). It is well-known that when its lower bound is zero, it is an easy task to find, in linear time, a monomial with zero error. What we prove is that when this bound is not zero, regardless of the location of the default class in (0, 1/2), it becomes a huge complexity burden to beat significantly the default class. In fact, under some complexity-theoretical assumptions, it may already be hard to beat the trivial approximation ratios, even when relaxing the time complexity constraint to be quasi-polynomial or sub-exponential. Our results also hold with uniform weights over the examples. BibTeX label: @article{2007-AgnosticApproximationMonomials-TCS , author={Richard Nock and Frank Nielsen} , title={Self-improved gaps almost everywhere for the agnostic approximation of monomials} , journal={Theoretical Computer Science} , month={May} , year={2007} , volume={377} , number={1-3} , pages={139-150} , doi={10.1016/j.tcs.2007.02.023} , abstract={ Given a learning sample, we focus on the hardness of finding monomials having low error, inside the interval bounded below by the smallest error achieved by a monomial (the best rule), and bounded above by the error of the default class (the poorest rule). It is well-known that when its lower bound is zero, it is an easy task to find, in linear time, a monomial with zero error. What we prove is that when this bound is not zero, regardless of the location of the default class in (0, 1/2), it becomes a huge complexity burden to beat significantly the default class. In fact, under some complexity-theoretical assumptions, it may already be hard to beat the trivial approximation ratios, even when relaxing the time complexity constraint to be quasi-polynomial or sub-exponential. Our results also hold with uniform weights over the examples. } }

Richard Nock and Frank Nielsen A real generalization of discrete AdaBoost Artificial Intelligence, (171) 1 , pp. 25-41, January 2007. PDF    10.1016/j.artint.2006.10.014    Search web Abstract: BibTeX label: @article{2007-RealMetaAdaBoost-AI , author={Richard Nock and Frank Nielsen} , title={A real generalization of discrete AdaBoost} , journal={Artificial Intelligence} , month={January} , year={2007} , volume={171} , number={1} , pages={25-41} , doi={10.1016/j.artint.2006.10.014} }

Frank Nielsen The digital chameleon principle: Computing invisibility by rendering transparency IEEE Computer Graphics and Applications, (27) 1 , pp. 90-96, January 2007. PDF    10.1109/MCG.2007.21    Search web Abstract: How many of us have had a dream of being invisible? But is that really that far-fetched, impossible, or improbable? As a child I used to daydream of magical powers that let me pursue exciting adventures in magical wonderlands. These great magical powers exhibited technology far beyond the current state of the art. I still clearly remember today those fantastic dreams. Indeed, dreaming that kind of fantasy let me feel good and relaxed, and they certainly colored my childhood. I personally think that daydreaming is also a kind of healing therapy of our day-to-day busy life to satisfy our curiosity. However, nowadays I also feel somewhat more conservative (and do not dream unfortunately anymore of Harry Potter worlds), partly because of my science background gained over the last 20 years or so of school education. School taught me the way to reasonably and rationally think without leaving much space for extravagance. That phenomenon is what Sir Arthur C. Clarke called the failure of the nerves in his book Profiles of the Future: An Inquiry into the Limits of the Possible.1 A good example cited by Clarke are excerpts of scholarly articles written by experts claiming the then impossibility of heavier-thanair flying machines. Nowadays, ... BibTeX label: @article{journals/cga/Nielsen07 , author={Frank Nielsen} , title={The digital chameleon principle: Computing invisibility by rendering transparency} , journal={IEEE Computer Graphics and Applications} , month={January} , year={2007} , volume={27} , number={1} , pages={90-96} , doi={10.1109/MCG.2007.21} , abstract={ How many of us have had a dream of being invisible? But is that really that far-fetched, impossible, or improbable? As a child I used to daydream of magical powers that let me pursue exciting adventures in magical wonderlands. These great magical powers exhibited technology far beyond the current state of the art. I still clearly remember today those fantastic dreams. Indeed, dreaming that kind of fantasy let me feel good and relaxed, and they certainly colored my childhood. I personally think that daydreaming is also a kind of healing therapy of our day-to-day busy life to satisfy our curiosity. However, nowadays I also feel somewhat more conservative (and do not dream unfortunately anymore of Harry Potter worlds), partly because of my science background gained over the last 20 years or so of school education. School taught me the way to reasonably and rationally think without leaving much space for extravagance. That phenomenon is what Sir Arthur C. Clarke called the failure of the nerves in his book Profiles of the Future: An Inquiry into the Limits of the Possible.1 A good example cited by Clarke are excerpts of scholarly articles written by experts claiming the then impossibility of heavier-thanair flying machines. Nowadays, ... } }

Frank Nielsen and Jean-Daniel Boissonnat and Richard Nock On Bregman Voronoi diagrams Symposium on Discrete Algorithms (SODA), pp. 746-755, January 2007. (Astor Crowne Plaza, New Orleans, Louisiana, USA) 10.1145/1283383.1283463    Search web Abstract: BibTeX label: @inproceedings{2007-BregmanVoronoi-SODA , author={Frank Nielsen and Jean-Daniel Boissonnat and Richard Nock} , title={On Bregman Voronoi diagrams} , booktitle={Symposium on Discrete Algorithms (SODA)} , month={January} , year={2007} , pages={746-755} , address={Astor Crowne Plaza, New Orleans, Louisiana, USA} , doi={10.1145/1283383.1283463} }

Frank Nielsen and Noriyuki Yamashita ClairVoyance: A Fast and Robust Precision Mosaicing System for Gigapixel Images IEEE Industrial Electronics Society (IECON), pp. 3471-3476, November 2006. (Paris, France) 10.1109/IECON.2006.347546    Search web Abstract: In this paper, we present CLAIRVOYANCE: a fully automatic photomosaicing system for building ultra high-resolution composited images from image sequences captured by tailored in-house motorized active pan-tilt digital camera units. Our stand-alone mobile systems built over the past five years are computationally fast, robust to various datasets and deliver unprecedented consumer-level image quality. We describe our simple yet novel lens calibration and radiometric correction procedures based on a fast block matching algorithm. All of our core image stitching components are based on the 2D Fourier phase correlation principle, and are thus easily amenable to hardware LSI implementation. We validate our approach by presenting sharp photomosaics obtained from a few hundreds up to a few thousands data sets of images BibTeX label: @inproceedings{2006-Clairvoyance-IECON , author={Frank Nielsen and Noriyuki Yamashita} , title={ClairVoyance: A Fast and Robust Precision Mosaicing System for Gigapixel Images } , booktitle={IEEE Industrial Electronics Society (IECON)} , month={November} , year={2006} , pages={3471-3476} , address={Paris, France} , doi={10.1109/IECON.2006.347546} , abstract={ In this paper, we present CLAIRVOYANCE: a fully automatic photomosaicing system for building ultra high-resolution composited images from image sequences captured by tailored in-house motorized active pan-tilt digital camera units. Our stand-alone mobile systems built over the past five years are computationally fast, robust to various datasets and deliver unprecedented consumer-level image quality. We describe our simple yet novel lens calibration and radiometric correction procedures based on a fast block matching algorithm. All of our core image stitching components are based on the 2D Fourier phase correlation principle, and are thus easily amenable to hardware LSI implementation. We validate our approach by presenting sharp photomosaics obtained from a few hundreds up to a few thousands data sets of images } }

Richard Nock and Frank Nielsen On weighting clustering IEEE Transactions on Pattern Analysis and Machine Intelligence, (28) 8 , pp. 1223-1235, August 2006. PDF    10.1109/TPAMI.2006.168    Search web Abstract: Recent papers and patents in iterative unsupervised learning have emphasized a new trend in clustering. It basically consists of penalizing solutions via weights on the instance points, somehow making clustering move toward the hardest points to cluster. The motivations come principally from an analogy with powerful supervised classification methods known as boosting algorithms. However, interest in this analogy has so far been mainly borne out from experimental studies only. This paper is, to the best of our knowledge, the first attempt at its formalization. More precisely, we handle clustering as a constrained minimization of a Bregman divergence. Weight modifications rely on the local variations of the expected complete log-likelihoods. Theoretical results show benefits resembling those of boosting algorithms and bring modified (weighted) versions of clustering algorithms such as k-means, fuzzy c-means, Expectation Maximization (EM), and k-harmonic means. Experiments are provided for all these algorithms, with a readily available code. They display the advantages that subtle data reweighting may bring to clustering. BibTeX label: @article{2006-WeightingClustering-PAMI , author={Richard Nock and Frank Nielsen} , title={On weighting clustering} , journal={IEEE Transactions on Pattern Analysis and Machine Intelligence} , month={August} , year={2006} , volume={28} , number={8} , pages={1223-1235} , doi={10.1109/TPAMI.2006.168} , abstract={ Recent papers and patents in iterative unsupervised learning have emphasized a new trend in clustering. It basically consists of penalizing solutions via weights on the instance points, somehow making clustering move toward the hardest points to cluster. The motivations come principally from an analogy with powerful supervised classification methods known as boosting algorithms. However, interest in this analogy has so far been mainly borne out from experimental studies only. This paper is, to the best of our knowledge, the first attempt at its formalization. More precisely, we handle clustering as a constrained minimization of a Bregman divergence. Weight modifications rely on the local variations of the expected complete log-likelihoods. Theoretical results show benefits resembling those of boosting algorithms and bring modified (weighted) versions of clustering algorithms such as k-means, fuzzy c-means, Expectation Maximization (EM), and k-harmonic means. Experiments are provided for all these algorithms, with a readily available code. They display the advantages that subtle data reweighting may bring to clustering. } }

Frank Nielsen and Shigeru Owada and Yuichi Hasegawa Autoframing: A recommendation system for detecting undesirable elements and cropping automatically photos International Conference on Multimedia and Expo (ICME), pp. 417-420, July 2006. (Toronto, Ontario, Canada) PDF    10.1109/ICME.2006.262525    Search web Abstract: In this paper, we present a recommendation system for automatically recentering and cropping digital still pictures that exhibit capturing artefacts. Autoframing images not only yields better visual pictures but more importantly allows us to remove undesirable artefacts such as lens obstructions by fingers, cellphone straps, or back heads. We report on our real-time prototype system that is targeted to consumer digital still cameras. BibTeX label: @inproceedings{2006-C-Autoframing-ICME , author={Frank Nielsen and Shigeru Owada and Yuichi Hasegawa} , title={Autoframing: A recommendation system for detecting undesirable elements and cropping automatically photos} , booktitle={International Conference on Multimedia and Expo (ICME)} , month={July} , year={2006} , pages={417-420} , address={Toronto, Ontario, Canada} , doi={10.1109/ICME.2006.262525} , abstract={ In this paper, we present a recommendation system for automatically recentering and cropping digital still pictures that exhibit capturing artefacts. Autoframing images not only yields better visual pictures but more importantly allows us to remove undesirable artefacts such as lens obstructions by fingers, cellphone straps, or back heads. We report on our real-time prototype system that is targeted to consumer digital still cameras. } }

Frank Nielsen Interactive image segmentation based on GPU cellular automata ShaderX5: Advanced Rendering Techniques , pp. 511-518, December 2005. Search web Abstract: BibTeX label: @incollection{2005-GPUSegmentation-CRM , author={Frank Nielsen} , title={Interactive image segmentation based on GPU cellular automata} , booktitle={ShaderX5: Advanced Rendering Techniques} , month={December} , year={2005} , pages={511-518} , publisher={Charles River Media/Thomson Publishing} }

Frank Nielsen A GPU panorama viewer for generic camera models ShaderX5: Advanced Rendering Techniques , pp. 543-552, December 2005. Search web Abstract: BibTeX label: @incollection{2005-GPUPanorama-CRM , author={Frank Nielsen} , title={A GPU panorama viewer for generic camera models} , booktitle={ShaderX5: Advanced Rendering Techniques} , month={December} , year={2005} , pages={543-552} , publisher={Charles River Media/Thomson Publishing} }

Frank Nielsen and Richard Nock ClickRemoval: Interactive pinpoint image object removal ACM Multimedia (MM), pp. 315-318, November 2005. (Singapore) http://doi.acm.org/10.1145/1101149.1101214    Search web Abstract: BibTeX label: @inproceedings{2005-ClickRemoval-MM , author={Frank Nielsen and Richard Nock} , title={ClickRemoval: Interactive pinpoint image object removal} , booktitle={ACM Multimedia (MM)} , month={November} , year={2005} , pages={315-318} , address={Singapore} , doi={http://doi.acm.org/10.1145/1101149.1101214} }

Richard Nock and Frank Nielsen Fitting the smallest enclosing Bregman ball European Conference on Machine Learning (ECML), pp. 649-656, October 2005. (Porto, Portugal) PDF    10.1007/11564096_65    Search web Abstract: Finding a point which minimizes the maximal distortion with respect to a dataset is an important estimation problem that has recently received growing attentions in machine learning, with the advent of one class classification. We propose two theoretically founded generalizations to arbitrary Bregman divergences, of a recent popular smallest enclosing ball approximation algorithm for Euclidean spaces coined by Badoiu and Clarkson in 2002. BibTeX label: @inproceedings{2005-C-BregmanBall-ECML , author={Richard Nock and Frank Nielsen} , title={Fitting the smallest enclosing Bregman ball} , booktitle={European Conference on Machine Learning (ECML)} , month={October} , year={2005} , pages={649-656} , address={Porto, Portugal} , doi={10.1007/11564096_65} , abstract={ Finding a point which minimizes the maximal distortion with respect to a dataset is an important estimation problem that has recently received growing attentions in machine learning, with the advent of one class classification. We propose two theoretically founded generalizations to arbitrary Bregman divergences, of a recent popular smallest enclosing ball approximation algorithm for Euclidean spaces coined by Badoiu and Clarkson in 2002. } }

Frank Nielsen Visual computing: Geometry, graphics and vision ( pp. xiv+560 pages, 8-page color insert) , Charles River Media / Thomson Delmar Learning , August 2005. PDF    Search web Abstract: BibTeX label: @book{2005-VisualComputing-CRM , author={Frank Nielsen} , title={Visual computing: Geometry, graphics and vision} , month={August} , year={2005} , pages={xiv+560 pages, 8-page color insert} , publisher={Charles River Media / Thomson Delmar Learning} }

Richard Nock and Frank Nielsen Semi-supervised statistical region refinement for color image segmentation Pattern Recognition, (38) 6 , pp. 835-846, June 2005. PDF    10.1016/j.patcog.2004.11.009    Search web Abstract: Some authors have recently devised adaptations of spectral grouping algorithms to integrate prior knowledge, as constrained eigenvalues problems. In this paper, we improve and adapt a recent statistical region merging approach to this task, as a non-parametric mixture model estimation problem. The approach appears to be attractive both for its theoretical benefits and its experimental results, as slight bias brings dramatic improvements over unbiased approaches on challenging digital pictures. BibTeX label: @article{2005-SupervisedImageSegmentation-PR , author={Richard Nock and Frank Nielsen} , title={Semi-supervised statistical region refinement for color image segmentation} , journal={Pattern Recognition} , month={June} , year={2005} , volume={38} , number={6} , pages={835-846} , doi={10.1016/j.patcog.2004.11.009} , abstract={ Some authors have recently devised adaptations of spectral grouping algorithms to integrate prior knowledge, as constrained eigenvalues problems. In this paper, we improve and adapt a recent statistical region merging approach to this task, as a non-parametric mixture model estimation problem. The approach appears to be attractive both for its theoretical benefits and its experimental results, as slight bias brings dramatic improvements over unbiased approaches on challenging digital pictures. } }

Paul Agron and Leo Bachmair and Frank Nielsen A visual interactive framework for formal derivation International Conference on Computational Science (ICCS), pp. 1019-1026, May 2005. (Atlanta, GA, USA) PDF    10.1007/11428831_127    Search web Abstract: We describe a visual interactive framework that supports the computation of syntactic unifiers of expressions with variables. Unification is specified via built-in transformation rules. A user derives a solution to a unification problem by stepwise application of these rules. The software tool provides both a debugger-style presentation of a derivation and its history, and a graphical view of the expressions generated during the unification process. A backtracking facility allows the user to revert to an earlier step in a derivation and proceed with a different strategy. BibTeX label: @inproceedings{2005-C-VisualInteractive-ICCS , author={Paul Agron and Leo Bachmair and Frank Nielsen} , title={A visual interactive framework for formal derivation} , booktitle={International Conference on Computational Science (ICCS)} , month={May} , year={2005} , pages={1019-1026} , address={Atlanta, GA, USA} , doi={10.1007/11428831_127} , abstract={ We describe a visual interactive framework that supports the computation of syntactic unifiers of expressions with variables. Unification is specified via built-in transformation rules. A user derives a solution to a unification problem by stepwise application of these rules. The software tool provides both a debugger-style presentation of a derivation and its history, and a graphical view of the expressions generated during the unification process. A backtracking facility allows the user to revert to an earlier step in a derivation and proceed with a different strategy. } }

Shigeru Owada and Frank Nielsen and Takeo Igarashi Volume catcher Symposium on Interactive 3D Graphics and Games (SI3D), pp. 111-116, April 2005. (Washington, District of Columbia, USA) 10.1145/1053427.1053445    Search web Abstract: It is difficult to obtain a specific region within unsegmented volume data (region of interest, ROI). The user must first segment the volume, a task which itself involves significant user intervention, and then chooses a desired target within the 3D space. This paper proposes a simple and intuitive user interface for the task: the user traces the contour of the target region using a 2D free form stroke on the screen, and the system instantly returns a plausible 3D region inside the stroke by applying a segmentation algorithm. The main contribution is that the system infers the depth information of the ROI automatically by analyzing the data, whereas existing systems require the user to provide the depth information explicitly. Our system first computes the 3D location of the user-specified 2D stroke based on the assumption that the user traced the silhouette of the ROI, that is, the curve where the gradient is perpendicular to the viewing direction. The system then places constraint points around the 3D stroke to guide the following segmentation. Foreground constraints are placed inside the stroke and background constraints are placed outside the stroke. We currently use the statistical region-merging algorithm of Nock et al. [Nock and Nielsen 2004a] to perform the segmentation. We tested our system with real-world examples to verify the effectiveness of our approach. BibTeX label: @inproceedings{2005-C-VolumeCatcher-2005 , author={Shigeru Owada and Frank Nielsen and Takeo Igarashi} , title={Volume catcher} , booktitle={Symposium on Interactive 3D Graphics and Games (SI3D)} , month={April} , year={2005} , pages={111-116} , address={Washington, District of Columbia, USA} , doi={10.1145/1053427.1053445} , abstract={ It is difficult to obtain a specific region within unsegmented volume data (region of interest, ROI). The user must first segment the volume, a task which itself involves significant user intervention, and then chooses a desired target within the 3D space. This paper proposes a simple and intuitive user interface for the task: the user traces the contour of the target region using a 2D free form stroke on the screen, and the system instantly returns a plausible 3D region inside the stroke by applying a segmentation algorithm. The main contribution is that the system infers the depth information of the ROI automatically by analyzing the data, whereas existing systems require the user to provide the depth information explicitly. Our system first computes the 3D location of the user-specified 2D stroke based on the assumption that the user traced the silhouette of the ROI, that is, the curve where the gradient is perpendicular to the viewing direction. The system then places constraint points around the 3D stroke to guide the following segmentation. Foreground constraints are placed inside the stroke and background constraints are placed outside the stroke. We currently use the statistical region-merging algorithm of Nock et al. [Nock and Nielsen 2004a] to perform the segmentation. We tested our system with real-world examples to verify the effectiveness of our approach.} }

Frank Nielsen and Richard Nock A fast deterministic smallest enclosing disk approximation algorithm Information Processing Letters, (93) 6 , pp. 263-268, March 2005. PDF    10.1016/j.ipl.2004.12.006    Search web Abstract: We describe a simple and fast $O(n\log\frac{1}{\epsilon})$-time algorithm for finding a $(1+\epsilon)$-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented. BibTeX label: @article{2005-EnclosingDiskApproximation-IPL , author={Frank Nielsen and Richard Nock} , title={A fast deterministic smallest enclosing disk approximation algorithm} , journal={Information Processing Letters} , month={March} , year={2005} , volume={93} , number={6} , pages={263-268} , doi={10.1016/j.ipl.2004.12.006} , abstract={ We describe a simple and fast $O(n\log\frac{1}{\epsilon})$-time algorithm for finding a $(1+\epsilon)$-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented. } }

Frank Nielsen Surround video: a multihead camera approach The Visual Computer, (21) 1-2 , pp. 92-103, February 2005. PDF    10.1007/s00371-004-0273-z    Search web Abstract: We describe algorithms for creating, storing and viewing high-resolution immersive surround videos. Given a set of unit cameras designed to be almost aligned at a common nodal point, we first present a versatile process for stitching seamlessly synchronized streams of videos into a single surround video corresponding to the video of the multihead camera. We devise a general registration process onto raymaps based on minimizing a tailored objective function. We review and introduce new raymaps with good sampling properties. We then give implementation details on the surround video viewer and present experimental results on both real-world acquired and computer-graphics rendered full surround videos. We conclude by mentioning potential applications and discuss ongoing related activities. BibTeX label: @article{2005-SurroundVideo-VisualComputer , author={Frank Nielsen} , title={Surround video: a multihead camera approach} , journal={The Visual Computer} , month={February} , year={2005} , volume={21} , number={1-2} , pages={92-103} , doi={10.1007/s00371-004-0273-z} , abstract={ We describe algorithms for creating, storing and viewing high-resolution immersive surround videos. Given a set of unit cameras designed to be almost aligned at a common nodal point, we first present a versatile process for stitching seamlessly synchronized streams of videos into a single surround video corresponding to the video of the multihead camera. We devise a general registration process onto raymaps based on minimizing a tailored objective function. We review and introduce new raymaps with good sampling properties. We then give implementation details on the surround video viewer and present experimental results on both real-world acquired and computer-graphics rendered full surround videos. We conclude by mentioning potential applications and discuss ongoing related activities. } }

Richard Nock and Frank Nielsen Statistical region merging IEEE Transactions on Pattern Analysis and Machine Intelligence, (26) 11 , pp. 1452-1458, November 2004. PDF    10.1109/TPAMI.2004.110     Search web Abstract: This paper explores a statistical basis for a process often described in computer vision: image segmentation by region merging following a particular order in the choice of regions. We exhibit a particular blend of algorithmics and statistics whose segmentation error is, as we show, limited from both the qualitative and quantitative standpoints. This approach can be efficiently approximated in linear time/space, leading to a fast segmentation algorithm tailored to processing images described using most common numerical pixel attribute spaces. The conceptual simplicity of the approach makes it simple to modify and cope with hard noise corruption, handle occlusion, authorize the control of the segmentation scale, and process unconventional data such as spherical images. Experiments on gray-level and color images, obtained with a short readily available C-code, display the quality of the segmentations obtained. BibTeX label: @article{2004-StatisticalRegionMerging-PAMI , author={Richard Nock and Frank Nielsen} , title={Statistical region merging} , journal={IEEE Transactions on Pattern Analysis and Machine Intelligence} , month={November} , year={2004} , volume={26} , number={11} , pages={1452-1458} , doi={10.1109/TPAMI.2004.110 } , abstract={ This paper explores a statistical basis for a process often described in computer vision: image segmentation by region merging following a particular order in the choice of regions. We exhibit a particular blend of algorithmics and statistics whose segmentation error is, as we show, limited from both the qualitative and quantitative standpoints. This approach can be efficiently approximated in linear time/space, leading to a fast segmentation algorithm tailored to processing images described using most common numerical pixel attribute spaces. The conceptual simplicity of the approach makes it simple to modify and cope with hard noise corruption, handle occlusion, authorize the control of the segmentation scale, and process unconventional data such as spherical images. Experiments on gray-level and color images, obtained with a short readily available C-code, display the quality of the segmentations obtained. } }

Shigeru Owada and Frank Nielsen and Makoto Okabe and Takeo Igarashi Volumetric illustration: Designing 3D models with internal textures ACM Transactions on Graphics (SIGGRAPH), (23) 3 , pp. 322-328, August 2004. PDF    10.1145/1015706.1015723    Search web Abstract: This paper presents an interactive system for designing and browsing volumetric illustrations. Volumetric illustrations are 3D models with internal textures that the user can browse by cutting the models at desired locations. To assign internal textures to a surface mesh, the designer cuts the mesh and provides simple guiding information to specify the correspondence between the cross-section and a reference 2D image. The guiding information is stored with the geometry and used during the synthesis of cross-sectional textures. The key idea is to synthesize a plausible cross-sectional image using a 2D texturesynthesis technique, instead of sampling from a complete 3D RGB volumetric representation directly. This simplifies the design interface and reduces the amount of data, making it possible for non-experts to rapidly design and use volumetric illustrations. We believe that our system can enrich human communications in various domains, such as medicine, biology, and geology. BibTeX label: @article{2004-VolumetricIllustration-SIGGRAPH , author={Shigeru Owada and Frank Nielsen and Makoto Okabe and Takeo Igarashi} , title={Volumetric illustration: Designing 3D models with internal textures} , journal={ACM Transactions on Graphics (SIGGRAPH)} , month={August} , year={2004} , volume={23} , number={3} , pages={322-328} , doi={10.1145/1015706.1015723} , abstract={ This paper presents an interactive system for designing and browsing volumetric illustrations. Volumetric illustrations are 3D models with internal textures that the user can browse by cutting the models at desired locations. To assign internal textures to a surface mesh, the designer cuts the mesh and provides simple guiding information to specify the correspondence between the cross-section and a reference 2D image. The guiding information is stored with the geometry and used during the synthesis of cross-sectional textures. The key idea is to synthesize a plausible cross-sectional image using a 2D texturesynthesis technique, instead of sampling from a complete 3D RGB volumetric representation directly. This simplifies the design interface and reduces the amount of data, making it possible for non-experts to rapidly design and use volumetric illustrations. We believe that our system can enrich human communications in various domains, such as medicine, biology, and geology. } }

Richard Nock and Frank Nielsen On domain-partitioning induction criteria: worst-case bounds for the worst-case based Theoretical Computer Science, (321) 2-3 , pp. 371-382, August 2004. PDF    10.1016/j.tcs.2004.05.004    Search web Abstract: One of the most popular induction scheme for supervised learning is also one of the oldest. It builds a classi3er in a top-down fashion, following the minimization of a so-called index criterion. While numerous papers have reported experiments on this scheme, little has been known on its theoretical aspect until recent works on decision trees and branching programs using a powerful classi3cation tool: boosting. In this paper, we look at this problem from a worst-case computational (rather than informational) standpoint. Our conclusions for the ranking of these indexes' minimization follow almost exactly that of boosting (with matching upper and lowerbounds), and provide extensions to more classes of Boolean formulas such as decision lists, multilinear polynomials and symmetric functions. Our results also exhibit a strong worst-case for the induction scheme, as we build particularly hard samples for which the replacement of most index criteria, or the class of concept representation, even when producing the same ranking as boosting does for the indexes, makes no di8erence at all for the concept induced. This is clearly not a limit of previous analyses, but a consequence of the induction scheme. BibTeX label: @article{2004-DomainPartitioning-TCS , author={Richard Nock and Frank Nielsen} , title={On domain-partitioning induction criteria: worst-case bounds for the worst-case based} , journal={Theoretical Computer Science} , month={August} , year={2004} , volume={321} , number={2-3} , pages={371-382} , doi={10.1016/j.tcs.2004.05.004} , abstract={ One of the most popular induction scheme for supervised learning is also one of the oldest. It builds a classi3er in a top-down fashion, following the minimization of a so-called index criterion. While numerous papers have reported experiments on this scheme, little has been known on its theoretical aspect until recent works on decision trees and branching programs using a powerful classi3cation tool: boosting. In this paper, we look at this problem from a worst-case computational (rather than informational) standpoint. Our conclusions for the ranking of these indexes' minimization follow almost exactly that of boosting (with matching upper and lowerbounds), and provide extensions to more classes of Boolean formulas such as decision lists, multilinear polynomials and symmetric functions. Our results also exhibit a strong worst-case for the induction scheme, as we build particularly hard samples for which the replacement of most index criteria, or the class of concept representation, even when producing the same ranking as boosting does for the indexes, makes no di8erence at all for the concept induced. This is clearly not a limit of previous analyses, but a consequence of the induction scheme.} }

Shigeru Owada and Yoshihisa Shinagawa and Frank Nielsen Enumeration of contour correspondence International Journal on Image Graphics, (3) 4 , pp. 609-628, October 2003. PDF    10.1142/S0219467803001214    Search web Abstract: With the recent advances in computed tomography and magnetic resonance devices, cross-sectional images are now commonly used for diagnosis. However, how contours between cross-sections should be connected is often ambiguous. In this paper, we propose an algorithm that enumerates all possible cases of the correspondence of contours. This is useful for achieving fully automatic interpolation of contours, although our current implementation still requires some degree of manual interaction. BibTeX label: @article{2003-ContourCorrespondence-IJIG , author={Shigeru Owada and Yoshihisa Shinagawa and Frank Nielsen} , title={Enumeration of contour correspondence} , journal={International Journal on Image Graphics} , month={October} , year={2003} , volume={3} , number={4} , pages={609-628} , doi={10.1142/S0219467803001214} , abstract={With the recent advances in computed tomography and magnetic resonance devices, cross-sectional images are now commonly used for diagnosis. However, how contours between cross-sections should be connected is often ambiguous. In this paper, we propose an algorithm that enumerates all possible cases of the correspondence of contours. This is useful for achieving fully automatic interpolation of contours, although our current implementation still requires some degree of manual interaction.} }

Frank Nielsen Plenoptic path and its applications International Conference on Image Processing (ICIP), pp. 793-796, September 2003. (Barcelona, Catalonia, Spain) Search web Abstract: In this paper, we present a method for acquiring, spatially filtering and viewing annotated videos captured with a full field of view multihead camera moving along a path. We describe our tailored egomotion recovery algorithm used for calculating the trajectory path of the panoramic head. We then focus on sampling the plenoptic path efficiently according to geometric visibility events. Appropriate samplings allow us to filter and compress the panoramic images avoiding some redundancies in the image database. We present several applications and results of plenoptic paths either obtained from indoor shootings or perfectly rendered by computer graphics scripts. BibTeX label: @inproceedings{2003-PlenopticPath-ICIP , author={Frank Nielsen} , title={Plenoptic path and its applications} , booktitle={International Conference on Image Processing (ICIP)} , month={September} , year={2003} , pages={793-796} , address={Barcelona, Catalonia, Spain} , abstract={ In this paper, we present a method for acquiring, spatially filtering and viewing annotated videos captured with a full field of view multihead camera moving along a path. We describe our tailored egomotion recovery algorithm used for calculating the trajectory path of the panoramic head. We then focus on sampling the plenoptic path efficiently according to geometric visibility events. Appropriate samplings allow us to filter and compress the panoramic images avoiding some redundancies in the image database. We present several applications and results of plenoptic paths either obtained from indoor shootings or perfectly rendered by computer graphics scripts. } }

Shigeru Owada and Frank Nielsen and Kazuo Nakazawa and Takeo Igarashi A sketching interface for modeling the internal structures of 3D shapes Smart Graphics (SG), pp. 49-57, July 2003. (Heidelberg, Germany) PDF    Search web Abstract: This paper presents a sketch-based modeling system for creating objects that have internal structures. The user input consists of hand-drawn sketches and the system automatically generates a volumetric model. The volumetric representation solves any self-intersection problems and enables the creation of models with a variety of topological structures, such as a torus or a hollow sphere. To specify internal structures, our system allows the user to cut the model temporarily and apply modeling operations to the exposed face. In addition, the user can draw multiple contours in the Create or Sweep stages. Our system also allows automatic rotation of the model so that the user does not need to perform frequent manual rotations. Our system is much simpler to implement than a surface-oriented system because no complicated mesh editing code is required. We observed that novice users could quickly create a variety of objects using our system. BibTeX label: @inproceedings{2003-VTeddy-SG , author={Shigeru Owada and Frank Nielsen and Kazuo Nakazawa and Takeo Igarashi} , title={A sketching interface for modeling the internal structures of 3D shapes} , booktitle={Smart Graphics (SG)} , month={July} , year={2003} , pages={49-57} , address={Heidelberg, Germany} , abstract={ This paper presents a sketch-based modeling system for creating objects that have internal structures. The user input consists of hand-drawn sketches and the system automatically generates a volumetric model. The volumetric representation solves any self-intersection problems and enables the creation of models with a variety of topological structures, such as a torus or a hollow sphere. To specify internal structures, our system allows the user to cut the model temporarily and apply modeling operations to the exposed face. In addition, the user can draw multiple contours in the Create or Sweep stages. Our system also allows automatic rotation of the model so that the user does not need to perform frequent manual rotations. Our system is much simpler to implement than a surface-oriented system because no complicated mesh editing code is required. We observed that novice users could quickly create a variety of objects using our system. } }

Matthew J. Katz and Frank Nielsen and Michael Segal Maintenance of a piercing set for intervals with applications Algorithmica, (36) 1 , pp. 59-73, February 2003. PDF    10.1007/s00453-002-1006-1    Search web Abstract: We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log|S|), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + e)c(S), for 0 BibTeX label: @article{2003-PiercingSetIntervals-Algorithmica , author={Matthew J. Katz and Frank Nielsen and Michael Segal} , title={Maintenance of a piercing set for intervals with applications} , journal={Algorithmica} , month={February} , year={2003} , volume={36} , number={1} , pages={59-73} , doi={10.1007/s00453-002-1006-1} , abstract={ We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log|S|), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + e)c(S), for 0 } }

Kim Binsted and Takafumi Misawa and Shigeo Morishima and Frank Nielsen Danger Hamster 2000 ACM SIGGRAPH, Conference Abstracts and Applications (SIGGRAPH), pp. 81, July 2002. (New Orleans, Louisiana, USA) Search web Abstract: BibTeX label: @inproceedings{2000-C-DangerHamster-SIGGRAPH , author={Kim Binsted and Takafumi Misawa and Shigeo Morishima and Frank Nielsen} , title={Danger Hamster 2000} , booktitle={ACM SIGGRAPH, Conference Abstracts and Applications (SIGGRAPH)} , month={July} , year={2002} , pages={81} , address={New Orleans, Louisiana, USA} }

Tatsuo Yotsukura and Shigeo Morishima and Frank Nielsen and Kim Binsted and Claudio S. Pinhanez HyperMask : Projecting a talking head onto a real object The Visual Computer, (18) 2 , pp. 111-120, April 2002. PDF    10.1007/s003710100140    Search web Abstract: HyperMask is a systemwhich projects an animated face onto a physicalmask worn by an actor. As the mask moves within a prescribed area, its position and orientation are detected by a camera and the projected image changes with respect to the viewpoint of the audience. The lips of the projected face are automatically synthesized in real time with the voice of the actor, who also controls the facial expressions. As a theatrical tool, HyperMask enables a new style of storytelling. As a prototype system, we put a self-contained HyperMask system in a trolley (disguised as a linen cart), so that it projects onto the mask worn by the actor pushing the trolley. BibTeX label: @article{2002-Hypermask-VisualComputer , author={Tatsuo Yotsukura and Shigeo Morishima and Frank Nielsen and Kim Binsted and Claudio S. Pinhanez} , title={HyperMask : Projecting a talking head onto a real object} , journal={The Visual Computer} , month={April} , year={2002} , volume={18} , number={2} , pages={111-120} , doi={10.1007/s003710100140} , abstract={ HyperMask is a systemwhich projects an animated face onto a physicalmask worn by an actor. As the mask moves within a prescribed area, its position and orientation are detected by a camera and the projected image changes with respect to the viewpoint of the audience. The lips of the projected face are automatically synthesized in real time with the voice of the actor, who also controls the facial expressions. As a theatrical tool, HyperMask enables a new style of storytelling. As a prototype system, we put a self-contained HyperMask system in a trolley (disguised as a linen cart), so that it projects onto the mask worn by the actor pushing the trolley. } }

Frank Nielsen and Nicolas de Mauroy On the precision of textures IEICE Transactions on Information and Systems, (E84-D) 12 , pp. 1684-1689, December 2001. PDF    Search web Abstract: In this paper, we first introduce the notion of texture precision given the 3d geometry of a scene. We then provide an algorithm to acquire a texture/color map of the scene within a given precision. The texture map is obtained using projective devices (like pinhole sensing device) from data acquired either in the real world or computer-synthesized. Finally, we describe a procedure to obtain level of precisions by combining a modified edge-collapse geometry technique with an appropriate remapping texture engine. We report on our experiments and give perspectives for further research. BibTeX label: @article{2001-PrecisionTextures-IEICE , author={Frank Nielsen and Nicolas de Mauroy} , title={On the precision of textures} , journal={IEICE Transactions on Information and Systems} , month={December} , year={2001} , volume={E84-D} , number={12} , pages={1684-1689} , abstract={In this paper, we first introduce the notion of texture precision given the 3d geometry of a scene. We then provide an algorithm to acquire a texture/color map of the scene within a given precision. The texture map is obtained using projective devices (like pinhole sensing device) from data acquired either in the real world or computer-synthesized. Finally, we describe a procedure to obtain level of precisions by combining a modified edge-collapse geometry technique with an appropriate remapping texture engine. We report on our experiments and give perspectives for further research. } }

Frank Nielsen On point covers of $c$-oriented polygons Theoretical Computer Science, (263) 1-2 , pp. 17-29, July 2001. PDF    10.1016/S0304-3975(00)00227-9    Search web Abstract: See on Elsevier for formula-friendly abstract. BibTeX label: @article{2001-PiercingOrientedPolygons-TCS , author={Frank Nielsen} , title={On point covers of $c$-oriented polygons} , journal={Theoretical Computer Science} , month={July} , year={2001} , volume={263} , number={1-2} , pages={17-29} , doi={10.1016/S0304-3975(00)00227-9} , abstract={ See on Elsevier for formula-friendly abstract. } }

Patrice Calegari and Frederic Guidec and Pierre Kuonen and Frank Nielsen Combinatorial optimization algorithms for radio network planning Theoretical Computer Science, (263) 1-2 , pp. 235-245, July 2001. PDF    10.1016/S0304-3975(00)00245-0    Search web Abstract: This paper uses a realistic problem taken from the telecommunication world as the basis for comparing different combinatorial optimization algorithms. The problem recalls the minimum hitting set problem, and is solved with greedy-like, Darwinism and genetic algorithms. These three paradigms are described and analyzed with emphasis on the Darwinism approach, which is based on the computation of epsilon-nets. BibTeX label: @article{2001-RadioNetworkPlanning-TCS , author={Patrice Calegari and Frederic Guidec and Pierre Kuonen and Frank Nielsen} , title={Combinatorial optimization algorithms for radio network planning} , journal={Theoretical Computer Science} , month={July} , year={2001} , volume={263} , number={1-2} , pages={235-245} , doi={10.1016/S0304-3975(00)00245-0} , abstract={ This paper uses a realistic problem taken from the telecommunication world as the basis for comparing different combinatorial optimization algorithms. The problem recalls the minimum hitting set problem, and is solved with greedy-like, Darwinism and genetic algorithms. These three paradigms are described and analyzed with emphasis on the Darwinism approach, which is based on the computation of epsilon-nets.} }

Frank Nielsen Randomized adaptive algorithms for mosaicing systems IEICE Transactions on Information and Systems, (E83-D) 7 , pp. 1386-1394, October 2000. PDF    Search web Abstract: Given a set of still images taken from a handheld camera, we present a fast method for mosaicing them into a single blended picture. We design time- and memory- efficient still image mosaicing algorithms based on geometric point feature matchings that can handle both arbitrary rotations and large zoom factors. We discuss extensions of the methodology to related problems like the recovering of the epipolar geometry for 3d reconstruction and object recognition tasks. BibTeX label: @article{2000-RandomizedMosaicing-IEICE , author={Frank Nielsen} , title={Randomized adaptive algorithms for mosaicing systems} , journal={IEICE Transactions on Information and Systems} , month={October} , year={2000} , volume={E83-D} , number={7} , pages={1386-1394} , abstract={ Given a set of still images taken from a handheld camera, we present a fast method for mosaicing them into a single blended picture. We design time- and memory- efficient still image mosaicing algorithms based on geometric point feature matchings that can handle both arbitrary rotations and large zoom factors. We discuss extensions of the methodology to related problems like the recovering of the epipolar geometry for 3d reconstruction and object recognition tasks. } }

Frank Nielsen Fast stabbing of boxes in high dimensions Theoretical Computer Science, (246) 1-2 , pp. 53-72, July 2000. PDF    10.1016/S0304-3975(98)00336-3    Search web Abstract: See on publisher site for formula. BibTeX label: @article{journals/tcs/Nielsen00 , author={Frank Nielsen} , title={Fast stabbing of boxes in high dimensions} , journal={Theoretical Computer Science} , month={July} , year={2000} , volume={246} , number={1-2} , pages={53-72} , doi={10.1016/S0304-3975(98)00336-3} , abstract={ See on publisher site for formula. } }

Alon Efrat and Matthew J. Katz and Frank Nielsen and Micha Sharir Dynamic data structures for fat objects and their applications Computational Geometry, (15) 4 , pp. 215-227, April 2000. PDF    10.1016/S0925-7721(99)00059-0    Search web Abstract: We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R2 or R3. Our planar structures are actually fitted for a more general class of objects - (alpha,beta)-covered objects - which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects.We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. BibTeX label: @article{2000-DynamicFatObjects-CGTA , author={Alon Efrat and Matthew J. Katz and Frank Nielsen and Micha Sharir} , title={Dynamic data structures for fat objects and their applications} , journal={Computational Geometry} , month={April} , year={2000} , volume={15} , number={4} , pages={215-227} , doi={10.1016/S0925-7721(99)00059-0} , abstract={ We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R2 or R3. Our planar structures are actually fitted for a more general class of objects - (alpha,beta)-covered objects - which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects.We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. } }

Kim Binsted and Frank Nielsen and Shigeo Morishima HyperMask: Virtual reactive faces for storytelling ACM Emerging Technologies, Conference Abstracts and Applications (SIGGRAPH), pp. 186, August 1999. (Los Angeles, California) 10.1145/311625.311991    Search web Abstract: BibTeX label: @inproceedings{1999-C-Hypermask-SIGGRAPH , author={Kim Binsted and Frank Nielsen and Shigeo Morishima} , title={HyperMask: Virtual reactive faces for storytelling} , booktitle={ACM Emerging Technologies, Conference Abstracts and Applications (SIGGRAPH)} , month={August} , year={1999} , pages={186} , address={Los Angeles, California} , doi={10.1145/311625.311991} }

Frank Nielsen and Claudio S. Pinhanez and Kim Binsted Projecting computer graphics on moving surfaces: A simple calibration and tracking method ACM SIGGRAPH, Emerging Technologies, Conference Abstracts and Applications, , pp. 266, August 1999. (Los Angeles, California) 10.1145/311625.311991    Search web Abstract: BibTeX label: @inproceedings{1999-C-ProjectorCamera-SIGGRAPH , author={Frank Nielsen and Claudio S. Pinhanez and Kim Binsted} , title={Projecting computer graphics on moving surfaces: A simple calibration and tracking method} , booktitle={ACM SIGGRAPH, Emerging Technologies, Conference Abstracts and Applications, } , month={August} , year={1999} , pages={266} , address={Los Angeles, California} , doi={10.1145/311625.311991} }

Frank Nielsen Grouping and querying: A paradigm to get output-sensitive algorithms Japan Conference on Discrete and Computational Geometry (JCDCG), pp. 250-257, December 1998. (Tokyo, Japan) Search web Abstract: BibTeX label: @inproceedings{1998-GroupingQuerying-JCDCG , author={Frank Nielsen} , title={Grouping and querying: A paradigm to get output-sensitive algorithms} , booktitle={Japan Conference on Discrete and Computational Geometry (JCDCG)} , month={December} , year={1998} , pages={250-257} , address={Tokyo, Japan} }

Frank Nielsen and Mariette Yvinec Output-sensitive convex hull algorithms of planar convex objects International Journal on Computational Geometry and Applications, (8) 1 , pp. 39-66, February 1998. PDF    10.1142/S0218195998000047    Search web Abstract: A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. BibTeX label: @article{1998-OutputSensitiveConvexHull-IJCGA , author={Frank Nielsen and Mariette Yvinec} , title={Output-sensitive convex hull algorithms of planar convex objects} , journal={International Journal on Computational Geometry and Applications} , month={February} , year={1998} , volume={8} , number={1} , pages={39-66} , doi={10.1142/S0218195998000047} , abstract={ A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. } }

Frank Nielsen Output-sensitive peeling of convex and maximal layers Information Processing Letters, (59) 5 , pp. 255-259, September 1996. PDF    10.1016/0020-0190(96)00116-0    Search web Abstract: We give an output-sensitive algorithm to compute the first k convex or maximal layers in O(n log Hk)-time where Hk is the number of points participating in the first k layers. Computing only the first k layers is interesting in various problems that arise in computational geometry (k-sets and dually k-levels, k-hulls and dually k-belts), pattern recognition, statistics, operations research, etc. BibTeX label: @article{1996-MaximaConvexLayers-IPL , author={Frank Nielsen} , title={Output-sensitive peeling of convex and maximal layers} , journal={Information Processing Letters} , month={September} , year={1996} , volume={59} , number={5} , pages={255-259} , doi={10.1016/0020-0190(96)00116-0} , abstract={ We give an output-sensitive algorithm to compute the first k convex or maximal layers in O(n log Hk)-time where Hk is the number of points participating in the first k layers. Computing only the first k layers is interesting in various problems that arise in computational geometry (k-sets and dually k-levels, k-hulls and dually k-belts), pattern recognition, statistics, operations research, etc. } }