[{"abstract":[{"text":" We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. ","lang":"eng"}],"date_updated":"2021-01-12T07:00:35Z","year":"2013","day":"01","author":[{"full_name":"Chen, Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"},{"full_name":"Yan, Zhu","last_name":"Yan","first_name":"Zhu"},{"last_name":"Metaxas","first_name":"Dimitris","full_name":"Metaxas, Dimitris"},{"full_name":"Lampert, Christoph","first_name":"Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert"}],"_id":"2901","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"JMLR","status":"public","oa":1,"title":"Computing the M most probable modes of a graphical model","alternative_title":[" JMLR: W&CP"],"month":"01","publication_status":"published","conference":{"start_date":"2013-04-29","name":" AISTATS: Conference on Uncertainty in Artificial Intelligence","end_date":"2013-05-01","location":"Scottsdale, AZ, United States"},"page":"161 - 169","date_created":"2018-12-11T12:00:14Z","oa_version":"None","type":"conference","date_published":"2013-01-01T00:00:00Z","department":[{"_id":"HeEd"},{"_id":"VlKo"},{"_id":"ChLa"}],"language":[{"iso":"eng"}],"publist_id":"3846","main_file_link":[{"url":"http://jmlr.org/proceedings/papers/v31/chen13a.html","open_access":"1"}],"scopus_import":1,"citation":{"ieee":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the M most probable modes of a graphical model,” presented at the  AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013, vol. 31, pp. 161–169.","ama":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.","short":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169.","mla":"Chen, Chao, et al. <i>Computing the M Most Probable Modes of a Graphical Model</i>. Vol. 31, JMLR, 2013, pp. 161–69.","apa":"Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., &#38; Lampert, C. (2013). Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169). Presented at the  AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR.","ista":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model.  AISTATS: Conference on Uncertainty in Artificial Intelligence,  JMLR: W&#38;CP, vol. 31, 161–169.","chicago":"Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69. JMLR, 2013."},"volume":31,"quality_controlled":"1","intvolume":"        31"},{"scopus_import":1,"publist_id":"3796","citation":{"ama":"Chen C, Kerber M. An output sensitive algorithm for persistent homology. <i>Computational Geometry: Theory and Applications</i>. 2013;46(4):435-447. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2012.02.010\">10.1016/j.comgeo.2012.02.010</a>","ieee":"C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” <i>Computational Geometry: Theory and Applications</i>, vol. 46, no. 4. Elsevier, pp. 435–447, 2013.","short":"C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013) 435–447.","chicago":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2013. <a href=\"https://doi.org/10.1016/j.comgeo.2012.02.010\">https://doi.org/10.1016/j.comgeo.2012.02.010</a>.","apa":"Chen, C., &#38; Kerber, M. (2013). An output sensitive algorithm for persistent homology. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2012.02.010\">https://doi.org/10.1016/j.comgeo.2012.02.010</a>","ista":"Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. 46(4), 435–447.","mla":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” <i>Computational Geometry: Theory and Applications</i>, vol. 46, no. 4, Elsevier, 2013, pp. 435–47, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2012.02.010\">10.1016/j.comgeo.2012.02.010</a>."},"volume":46,"quality_controlled":"1","intvolume":"        46","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"3367"}]},"publication_status":"published","doi":"10.1016/j.comgeo.2012.02.010","page":"435 - 447","date_created":"2018-12-11T12:00:27Z","publication":"Computational Geometry: Theory and Applications","oa_version":"None","type":"journal_article","language":[{"iso":"eng"}],"date_published":"2013-05-01T00:00:00Z","department":[{"_id":"HeEd"}],"status":"public","publisher":"Elsevier","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"An output sensitive algorithm for persistent homology","month":"05","date_updated":"2023-02-23T11:24:10Z","acknowledgement":"The authors thank Herbert Edelsbrunner for many helpful discussions and suggestions. Moreover, they are grateful for the careful reviews that helped to improve the quality of the paper.","abstract":[{"text":"In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ &gt; 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number of homology classes with persistence at least (1 - δ) Γ, n is the total number of simplices in the complex, d its dimension, and R d (n) is the complexity of computing the rank of an n × n matrix with O (d n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ) Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C (1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} &gt; 0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n log n).","lang":"eng"}],"issue":"4","day":"01","year":"2013","author":[{"last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","full_name":"Chen, Chao"},{"id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","full_name":"Kerber, Michael"}],"_id":"2939"},{"publication":"Proceedings of the 29th International Conference on Machine Learning","date_created":"2018-12-11T12:01:33Z","page":"211-218","publication_status":"published","conference":{"end_date":"2012-07-01","location":"Edinburgh, United Kingdom","start_date":"2012-06-26","name":"ICML: International Conference on Machine Learning"},"date_published":"2012-06-01T00:00:00Z","department":[{"_id":"ChLa"},{"_id":"HeEd"}],"language":[{"iso":"eng"}],"oa_version":"Preprint","type":"conference","article_processing_charge":"No","publist_id":"3572","scopus_import":"1","main_file_link":[{"url":"http://arxiv.org/abs/1206.4652","open_access":"1"}],"citation":{"ama":"Quadrianto N, Lampert C, Chen C. The most persistent soft-clique in a set of sampled graphs. In: <i>Proceedings of the 29th International Conference on Machine Learning</i>. ML Research Press; 2012:211-218.","ieee":"N. Quadrianto, C. Lampert, and C. Chen, “The most persistent soft-clique in a set of sampled graphs,” in <i>Proceedings of the 29th International Conference on Machine Learning</i>, Edinburgh, United Kingdom, 2012, pp. 211–218.","short":"N. Quadrianto, C. Lampert, C. Chen, in:, Proceedings of the 29th International Conference on Machine Learning, ML Research Press, 2012, pp. 211–218.","chicago":"Quadrianto, Novi, Christoph Lampert, and Chao Chen. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” In <i>Proceedings of the 29th International Conference on Machine Learning</i>, 211–18. ML Research Press, 2012.","mla":"Quadrianto, Novi, et al. “The Most Persistent Soft-Clique in a Set of Sampled Graphs.” <i>Proceedings of the 29th International Conference on Machine Learning</i>, ML Research Press, 2012, pp. 211–18.","apa":"Quadrianto, N., Lampert, C., &#38; Chen, C. (2012). The most persistent soft-clique in a set of sampled graphs. In <i>Proceedings of the 29th International Conference on Machine Learning</i> (pp. 211–218). Edinburgh, United Kingdom: ML Research Press.","ista":"Quadrianto N, Lampert C, Chen C. 2012. The most persistent soft-clique in a set of sampled graphs. Proceedings of the 29th International Conference on Machine Learning. ICML: International Conference on Machine Learning, 211–218."},"quality_controlled":"1","year":"2012","day":"01","abstract":[{"lang":"eng","text":"When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.\r\n    We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations."}],"date_updated":"2023-10-17T11:55:06Z","_id":"3127","author":[{"full_name":"Quadrianto, Novi","first_name":"Novi","last_name":"Quadrianto"},{"orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph"},{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao"}],"oa":1,"title":"The most persistent soft-clique in a set of sampled graphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publisher":"ML Research Press","month":"06"},{"publist_id":"3569","external_id":{"arxiv":["1107.3793"]},"quality_controlled":"1","volume":7357,"page":"189 - 200","date_created":"2018-12-11T12:01:33Z","language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"type":"conference","title":"Annotating simplices with a homology basis and its applications","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"day":"19","author":[{"full_name":"Busaryev, Oleksiy","last_name":"Busaryev","first_name":"Oleksiy"},{"full_name":"Cabello, Sergio","first_name":"Sergio","last_name":"Cabello"},{"last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","full_name":"Chen, Chao"},{"first_name":"Tamal","last_name":"Dey","full_name":"Dey, Tamal"},{"full_name":"Wang, Yusu","first_name":"Yusu","last_name":"Wang"}],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.3793"}],"citation":{"short":"O. Busaryev, S. Cabello, C. Chen, T. Dey, Y. Wang, in:, Springer, 2012, pp. 189–200.","ieee":"O. Busaryev, S. Cabello, C. Chen, T. Dey, and Y. Wang, “Annotating simplices with a homology basis and its applications,” presented at the SWAT: Symposium and Workshops on Algorithm Theory, Helsinki, Finland, 2012, vol. 7357, pp. 189–200.","ama":"Busaryev O, Cabello S, Chen C, Dey T, Wang Y. Annotating simplices with a homology basis and its applications. In: Vol 7357. Springer; 2012:189-200. doi:<a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">10.1007/978-3-642-31155-0_17</a>","chicago":"Busaryev, Oleksiy, Sergio Cabello, Chao Chen, Tamal Dey, and Yusu Wang. “Annotating Simplices with a Homology Basis and Its Applications,” 7357:189–200. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">https://doi.org/10.1007/978-3-642-31155-0_17</a>.","apa":"Busaryev, O., Cabello, S., Chen, C., Dey, T., &#38; Wang, Y. (2012). Annotating simplices with a homology basis and its applications (Vol. 7357, pp. 189–200). Presented at the SWAT: Symposium and Workshops on Algorithm Theory, Helsinki, Finland: Springer. <a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">https://doi.org/10.1007/978-3-642-31155-0_17</a>","mla":"Busaryev, Oleksiy, et al. <i>Annotating Simplices with a Homology Basis and Its Applications</i>. Vol. 7357, Springer, 2012, pp. 189–200, doi:<a href=\"https://doi.org/10.1007/978-3-642-31155-0_17\">10.1007/978-3-642-31155-0_17</a>.","ista":"Busaryev O, Cabello S, Chen C, Dey T, Wang Y. 2012. Annotating simplices with a homology basis and its applications. SWAT: Symposium and Workshops on Algorithm Theory, LNCS, vol. 7357, 189–200."},"intvolume":"      7357","publication_status":"published","conference":{"end_date":"2012-07-06","location":"Helsinki, Finland","start_date":"2012-07-04","name":"SWAT: Symposium and Workshops on Algorithm Theory"},"doi":"10.1007/978-3-642-31155-0_17","date_published":"2012-06-19T00:00:00Z","oa_version":"Preprint","oa":1,"status":"public","month":"06","year":"2012","date_updated":"2021-01-12T07:41:15Z","arxiv":1,"abstract":[{"text":"Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω &lt; 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently.\r\n\r\nUsing annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω  + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.\r\n","lang":"eng"}],"_id":"3129"},{"month":"01","title":"Hardness results for homology localization","status":"public","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"3267","author":[{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao"},{"full_name":"Freedman, Daniel","last_name":"Freedman","first_name":"Daniel"}],"day":"14","year":"2011","date_updated":"2023-02-21T16:07:10Z","abstract":[{"text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field.","lang":"eng"}],"issue":"3","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"10909"}]},"quality_controlled":"1","citation":{"apa":"Chen, C., &#38; Freedman, D. (2011). Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3, Springer, 2011, pp. 425–48, doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>.","ista":"Chen C, Freedman D. 2011. Hardness results for homology localization. Discrete &#38; Computational Geometry. 45(3), 425–448.","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>.","short":"C. Chen, D. Freedman, Discrete &#38; Computational Geometry 45 (2011) 425–448.","ama":"Chen C, Freedman D. Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. 2011;45(3):425-448. doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>","ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3. Springer, pp. 425–448, 2011."},"intvolume":"        45","volume":45,"publist_id":"3379","scopus_import":1,"language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"date_published":"2011-01-14T00:00:00Z","oa_version":"None","type":"journal_article","date_created":"2018-12-11T12:02:21Z","page":"425 - 448","publication":"Discrete & Computational Geometry","publication_status":"published","doi":"10.1007/s00454-010-9322-8"},{"date_published":"2011-11-30T00:00:00Z","language":[{"iso":"eng"}],"oa_version":"None","type":"book_chapter","publication":"Computer Vision","date_created":"2018-12-11T12:02:22Z","page":"239 - 268","publication_status":"published","quality_controlled":"1","citation":{"chicago":"Freedman, Daniel, and Chao Chen. “Algebraic Topology for Computer Vision.” In <i>Computer Vision</i>, 239–68. Nova Science Publishers, 2011.","mla":"Freedman, Daniel, and Chao Chen. “Algebraic Topology for Computer Vision.” <i>Computer Vision</i>, Nova Science Publishers, 2011, pp. 239–68.","ista":"Freedman D, Chen C. 2011.Algebraic topology for computer vision. In: Computer Vision. Computer Science, Technology and Applications, , 239–268.","apa":"Freedman, D., &#38; Chen, C. (2011). Algebraic topology for computer vision. In <i>Computer Vision</i> (pp. 239–268). Nova Science Publishers.","short":"D. Freedman, C. Chen, in:, Computer Vision, Nova Science Publishers, 2011, pp. 239–268.","ama":"Freedman D, Chen C. Algebraic topology for computer vision. In: <i>Computer Vision</i>. Nova Science Publishers; 2011:239-268.","ieee":"D. Freedman and C. Chen, “Algebraic topology for computer vision,” in <i>Computer Vision</i>, Nova Science Publishers, 2011, pp. 239–268."},"main_file_link":[{"url":"http://www.hpl.hp.com/techreports/2009/HPL-2009-375.pdf"}],"publist_id":"3378","_id":"3268","author":[{"last_name":"Freedman","first_name":"Daniel","full_name":"Freedman, Daniel"},{"full_name":"Chen, Chao","first_name":"Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87"}],"year":"2011","extern":"1","day":"30","abstract":[{"lang":"eng","text":"Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field. "}],"date_updated":"2021-01-12T07:42:16Z","alternative_title":["Computer Science, Technology and Applications"],"month":"11","title":"Algebraic topology for computer vision","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","status":"public","publisher":"Nova Science Publishers"},{"page":"1261 - 1268","date_created":"2018-12-11T12:02:22Z","publication":"Computer Graphics Forum","type":"journal_article","language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"publist_id":"3377","article_type":"original","article_processing_charge":"No","quality_controlled":"1","volume":30,"day":"19","author":[{"last_name":"Sheng","first_name":"Yu","full_name":"Sheng, Yu"},{"full_name":"Cutler, Barbara","first_name":"Barbara","last_name":"Cutler"},{"full_name":"Chen, Chao","first_name":"Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen"},{"full_name":"Nasman, Joshua","first_name":"Joshua","last_name":"Nasman"}],"publisher":"Wiley-Blackwell","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Perceptual global illumination cancellation in complex projection environments","publication_status":"published","doi":"10.1111/j.1467-8659.2011.01985.x","oa_version":"Published Version","date_published":"2011-07-19T00:00:00Z","scopus_import":1,"main_file_link":[{"url":"http://www.cs.cmu.edu/%7Eshengyu/download/egsr2011_paper.pdf","open_access":"1"}],"citation":{"chicago":"Sheng, Yu, Barbara Cutler, Chao Chen, and Joshua Nasman. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>. Wiley-Blackwell, 2011. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>.","ista":"Sheng Y, Cutler B, Chen C, Nasman J. 2011. Perceptual global illumination cancellation in complex projection environments. Computer Graphics Forum. 30(4), 1261–1268.","apa":"Sheng, Y., Cutler, B., Chen, C., &#38; Nasman, J. (2011). Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>","mla":"Sheng, Yu, et al. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>, vol. 30, no. 4, Wiley-Blackwell, 2011, pp. 1261–68, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>.","short":"Y. Sheng, B. Cutler, C. Chen, J. Nasman, Computer Graphics Forum 30 (2011) 1261–1268.","ieee":"Y. Sheng, B. Cutler, C. Chen, and J. Nasman, “Perceptual global illumination cancellation in complex projection environments,” <i>Computer Graphics Forum</i>, vol. 30, no. 4. Wiley-Blackwell, pp. 1261–1268, 2011.","ama":"Sheng Y, Cutler B, Chen C, Nasman J. Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. 2011;30(4):1261-1268. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>"},"intvolume":"        30","date_updated":"2021-01-12T07:42:16Z","abstract":[{"text":"The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods.","lang":"eng"}],"issue":"4","year":"2011","_id":"3269","status":"public","oa":1,"month":"07"},{"author":[{"full_name":"Chen, Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"orcid":"0000-0002-8030-9299","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"}],"_id":"3270","date_updated":"2021-01-12T07:42:17Z","abstract":[{"text":"The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.","lang":"eng"}],"day":"01","year":"2011","month":"01","status":"public","publisher":"TU Dortmund","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","title":"Persistent homology computation with a twist","type":"conference","oa_version":"None","language":[{"iso":"eng"}],"date_published":"2011-01-01T00:00:00Z","department":[{"_id":"HeEd"}],"publication_status":"published","conference":{"name":"EuroCG: European Workshop on Computational Geometry","start_date":"2011-03-28","location":"Morschach, Switzerland","end_date":"2011-03-30"},"date_created":"2018-12-11T12:02:22Z","page":"197 - 200","quality_controlled":"1","citation":{"ista":"Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry, 197–200.","mla":"Chen, Chao, and Michael Kerber. <i>Persistent Homology Computation with a Twist</i>. TU Dortmund, 2011, pp. 197–200.","apa":"Chen, C., &#38; Kerber, M. (2011). Persistent homology computation with a twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland: TU Dortmund.","chicago":"Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.","ama":"Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200.","ieee":"C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland, 2011, pp. 197–200.","short":"C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200."},"publist_id":"3376"},{"scopus_import":1,"publist_id":"3375","citation":{"apa":"Wagner, H., Chen, C., &#38; Vuçini, E. (2011). Efficient computation of persistent homology for cubical data. In R. Peikert, H. Hauser, H. Carr, &#38; R. Fuchs (Eds.), <i>Topological Methods in Data Analysis and Visualization II</i> (pp. 91–106). Springer. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>","mla":"Wagner, Hubert, et al. “Efficient Computation of Persistent Homology for Cubical Data.” <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert et al., Springer, 2011, pp. 91–106, doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>.","ista":"Wagner H, Chen C, Vuçini E. 2011.Efficient computation of persistent homology for cubical data. In: Topological Methods in Data Analysis and Visualization II. Theory, Algorithms, and Applications, , 91–106.","chicago":"Wagner, Hubert, Chao Chen, and Erald Vuçini. “Efficient Computation of Persistent Homology for Cubical Data.” In <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert, Helwig Hauser, Hamish Carr, and Raphael Fuchs, 91–106. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>.","short":"H. Wagner, C. Chen, E. Vuçini, in:, R. Peikert, H. Hauser, H. Carr, R. Fuchs (Eds.), Topological Methods in Data Analysis and Visualization II, Springer, 2011, pp. 91–106.","ieee":"H. Wagner, C. Chen, and E. Vuçini, “Efficient computation of persistent homology for cubical data,” in <i>Topological Methods in Data Analysis and Visualization II</i>, R. Peikert, H. Hauser, H. Carr, and R. Fuchs, Eds. Springer, 2011, pp. 91–106.","ama":"Wagner H, Chen C, Vuçini E. Efficient computation of persistent homology for cubical data. In: Peikert R, Hauser H, Carr H, Fuchs R, eds. <i>Topological Methods in Data Analysis and Visualization II</i>. Springer; 2011:91-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>"},"editor":[{"full_name":"Peikert, Ronald","last_name":"Peikert","first_name":"Ronald"},{"full_name":"Hauser, Helwig","first_name":"Helwig","last_name":"Hauser"},{"full_name":"Carr, Hamish","last_name":"Carr","first_name":"Hamish"},{"full_name":"Fuchs, Raphael","last_name":"Fuchs","first_name":"Raphael"}],"quality_controlled":"1","doi":"10.1007/978-3-642-23175-9_7","publication_status":"published","publication":"Topological Methods in Data Analysis and Visualization II","date_created":"2018-12-11T12:02:23Z","page":"91 - 106","oa_version":"None","type":"book_chapter","department":[{"_id":"HeEd"}],"date_published":"2011-11-14T00:00:00Z","language":[{"iso":"eng"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","status":"public","title":"Efficient computation of persistent homology for cubical data","alternative_title":["Theory, Algorithms, and Applications"],"month":"11","abstract":[{"lang":"eng","text":"In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets."}],"date_updated":"2021-01-12T07:42:18Z","year":"2011","day":"14","author":[{"full_name":"Wagner, Hubert","last_name":"Wagner","first_name":"Hubert"},{"first_name":"Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao"},{"last_name":"Vuçini","first_name":"Erald","full_name":"Vuçini, Erald"}],"_id":"3271"},{"status":"public","oa":1,"month":"11","abstract":[{"lang":"eng","text":"Interpreting an image as a function on a compact sub- set of the Euclidean plane, we get its scale-space by diffu- sion, spreading the image over the entire plane. This gener- ates a 1-parameter family of functions alternatively defined as convolutions with a progressively wider Gaussian ker- nel. We prove that the corresponding 1-parameter family of persistence diagrams have norms that go rapidly to zero as time goes to infinity. This result rationalizes experimental observations about scale-space. We hope this will lead to targeted improvements of related computer vision methods."}],"date_updated":"2021-01-12T07:42:35Z","year":"2011","article_number":"6126271","_id":"3313","scopus_import":1,"file_date_updated":"2020-07-14T12:46:07Z","ddc":["000"],"citation":{"mla":"Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.” <i>Proceedings of the IEEE International Conference on Computer Vision</i>, 6126271, IEEE, 2011, doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">10.1109/ICCV.2011.6126271</a>.","apa":"Chen, C., &#38; Edelsbrunner, H. (2011). Diffusion runs low on persistence fast. In <i>Proceedings of the IEEE International Conference on Computer Vision</i>. Barcelona, Spain: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">https://doi.org/10.1109/ICCV.2011.6126271</a>","ista":"Chen C, Edelsbrunner H. 2011. Diffusion runs low on persistence fast. Proceedings of the IEEE International Conference on Computer Vision. ICCV: International Conference on Computer Vision, 6126271.","chicago":"Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.” In <i>Proceedings of the IEEE International Conference on Computer Vision</i>. IEEE, 2011. <a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">https://doi.org/10.1109/ICCV.2011.6126271</a>.","ieee":"C. Chen and H. Edelsbrunner, “Diffusion runs low on persistence fast,” in <i>Proceedings of the IEEE International Conference on Computer Vision</i>, Barcelona, Spain, 2011.","ama":"Chen C, Edelsbrunner H. Diffusion runs low on persistence fast. In: <i>Proceedings of the IEEE International Conference on Computer Vision</i>. IEEE; 2011. doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">10.1109/ICCV.2011.6126271</a>","short":"C. Chen, H. Edelsbrunner, in:, Proceedings of the IEEE International Conference on Computer Vision, IEEE, 2011."},"doi":"10.1109/ICCV.2011.6126271","conference":{"location":"Barcelona, Spain","end_date":"2011-11-13","name":"ICCV: International Conference on Computer Vision","start_date":"2011-11-06"},"publication_status":"published","oa_version":"Submitted Version","date_published":"2011-11-06T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","title":"Diffusion runs low on persistence fast","day":"06","author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao","full_name":"Chen, Chao"},{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"}],"file":[{"file_id":"5282","checksum":"6984684081ba123808b344f9f2e64a8f","creator":"system","access_level":"open_access","date_updated":"2020-07-14T12:46:07Z","file_name":"IST-2016-540-v1+1_2011-P-08-RunEmpty.pdf","date_created":"2018-12-12T10:17:28Z","relation":"main_file","content_type":"application/pdf","file_size":614050}],"pubrep_id":"540","publist_id":"3327","quality_controlled":"1","has_accepted_license":"1","publication":"Proceedings of the IEEE International Conference on Computer Vision","date_created":"2018-12-11T12:02:37Z","type":"conference","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}]},{"type":"conference","oa_version":"None","date_published":"2011-07-22T00:00:00Z","department":[{"_id":"HeEd"},{"_id":"ChLa"}],"language":[{"iso":"eng"}],"doi":"10.1109/CVPR.2011.5995503","conference":{"location":"Colorado Springs, CO, United States","end_date":"2011-06-25","name":"CVPR: Conference on Computer Vision and Pattern Recognition","start_date":"2011-06-20"},"publication_status":"published","publication":"CVPR: Computer Vision and Pattern Recognition","date_created":"2018-12-11T12:02:45Z","page":"2089 - 2096","citation":{"chicago":"Chen, Chao, Daniel Freedman, and Christoph Lampert. “Enforcing Topological Constraints in Random Field Image Segmentation.” In <i>CVPR: Computer Vision and Pattern Recognition</i>, 2089–96. IEEE, 2011. <a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">https://doi.org/10.1109/CVPR.2011.5995503</a>.","mla":"Chen, Chao, et al. “Enforcing Topological Constraints in Random Field Image Segmentation.” <i>CVPR: Computer Vision and Pattern Recognition</i>, IEEE, 2011, pp. 2089–96, doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">10.1109/CVPR.2011.5995503</a>.","apa":"Chen, C., Freedman, D., &#38; Lampert, C. (2011). Enforcing topological constraints in random field image segmentation. In <i>CVPR: Computer Vision and Pattern Recognition</i> (pp. 2089–2096). Colorado Springs, CO, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">https://doi.org/10.1109/CVPR.2011.5995503</a>","ista":"Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in random field image segmentation. CVPR: Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 2089–2096.","short":"C. Chen, D. Freedman, C. Lampert, in:, CVPR: Computer Vision and Pattern Recognition, IEEE, 2011, pp. 2089–2096.","ieee":"C. Chen, D. Freedman, and C. Lampert, “Enforcing topological constraints in random field image segmentation,” in <i>CVPR: Computer Vision and Pattern Recognition</i>, Colorado Springs, CO, United States, 2011, pp. 2089–2096.","ama":"Chen C, Freedman D, Lampert C. Enforcing topological constraints in random field image segmentation. In: <i>CVPR: Computer Vision and Pattern Recognition</i>. IEEE; 2011:2089-2096. doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">10.1109/CVPR.2011.5995503</a>"},"quality_controlled":"1","related_material":{"record":[{"id":"5386","status":"public","relation":"earlier_version"}]},"article_processing_charge":"No","publist_id":"3294","scopus_import":"1","author":[{"first_name":"Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","full_name":"Chen, Chao"},{"full_name":"Freedman, Daniel","last_name":"Freedman","first_name":"Daniel"},{"full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"_id":"3336","acknowledgement":"The first author is supported by the Austrian Science Fund (FWF) grant No. P20134-N13. The authors would like to thank Sebastian Nowozin for helpful discussions.","abstract":[{"text":"We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.","lang":"eng"}],"date_updated":"2023-02-23T12:23:56Z","year":"2011","day":"22","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publisher":"IEEE","publication_identifier":{"isbn":["978-1-4577-0394-2"],"eisbn":["978-1-4577-0395-9"]},"title":"Enforcing topological constraints in random field image segmentation"},{"month":"03","alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Enforcing topological constraints in random field image segmentation","oa":1,"publication_identifier":{"issn":["2664-1690"]},"author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao","full_name":"Chen, Chao"},{"first_name":"Daniel","last_name":"Freedman","full_name":"Freedman, Daniel"},{"orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph"}],"file":[{"date_created":"2018-12-12T11:53:34Z","file_name":"IST-2011-0002_IST-2011-0002.pdf","date_updated":"2020-07-14T12:46:41Z","access_level":"open_access","checksum":"ad64c2add5fe2ad10e9d5c669f3f9526","creator":"system","file_id":"5495","file_size":26390601,"content_type":"application/pdf","relation":"main_file"}],"_id":"5386","date_updated":"2023-02-23T11:22:48Z","abstract":[{"text":"We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.","lang":"eng"}],"day":"28","year":"2011","citation":{"ieee":"C. Chen, D. Freedman, and C. Lampert, <i>Enforcing topological constraints in random field image segmentation</i>. IST Austria, 2011.","ama":"Chen C, Freedman D, Lampert C. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria; 2011. doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">10.15479/AT:IST-2011-0002</a>","short":"C. Chen, D. Freedman, C. Lampert, Enforcing Topological Constraints in Random Field Image Segmentation, IST Austria, 2011.","chicago":"Chen, Chao, Daniel Freedman, and Christoph Lampert. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria, 2011. <a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">https://doi.org/10.15479/AT:IST-2011-0002</a>.","apa":"Chen, C., Freedman, D., &#38; Lampert, C. (2011). <i>Enforcing topological constraints in random field image segmentation</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">https://doi.org/10.15479/AT:IST-2011-0002</a>","ista":"Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in random field image segmentation, IST Austria, 69p.","mla":"Chen, Chao, et al. <i>Enforcing Topological Constraints in Random Field Image Segmentation</i>. IST Austria, 2011, doi:<a href=\"https://doi.org/10.15479/AT:IST-2011-0002\">10.15479/AT:IST-2011-0002</a>."},"related_material":{"record":[{"id":"3336","status":"public","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:46:41Z","pubrep_id":"22","ddc":["000"],"type":"technical_report","oa_version":"Published Version","language":[{"iso":"eng"}],"department":[{"_id":"ChLa"}],"date_published":"2011-03-28T00:00:00Z","has_accepted_license":"1","publication_status":"published","doi":"10.15479/AT:IST-2011-0002","page":"69","date_created":"2018-12-12T11:39:02Z"},{"year":"2011","day":"13","abstract":[{"text":"In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ&gt;0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε&gt;0.","lang":"eng"}],"date_updated":"2023-02-23T11:05:04Z","_id":"3367","author":[{"full_name":"Chen, Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299"}],"title":"An output sensitive algorithm for persistent homology","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","status":"public","month":"06","date_created":"2018-12-11T12:02:56Z","page":"207 - 216","doi":"10.1145/1998196.1998228","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2011-06-13","location":"Paris, France","end_date":"2011-06-15"},"publication_status":"published","department":[{"_id":"HeEd"}],"date_published":"2011-06-13T00:00:00Z","language":[{"iso":"eng"}],"oa_version":"None","type":"conference","article_processing_charge":"No","scopus_import":1,"publist_id":"3245","related_material":{"record":[{"status":"public","relation":"later_version","id":"2939"}]},"citation":{"chicago":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology,” 207–16. ACM, 2011. <a href=\"https://doi.org/10.1145/1998196.1998228\">https://doi.org/10.1145/1998196.1998228</a>.","apa":"Chen, C., &#38; Kerber, M. (2011). An output sensitive algorithm for persistent homology (pp. 207–216). Presented at the SoCG: Symposium on Computational Geometry, Paris, France: ACM. <a href=\"https://doi.org/10.1145/1998196.1998228\">https://doi.org/10.1145/1998196.1998228</a>","mla":"Chen, Chao, and Michael Kerber. <i>An Output Sensitive Algorithm for Persistent Homology</i>. ACM, 2011, pp. 207–16, doi:<a href=\"https://doi.org/10.1145/1998196.1998228\">10.1145/1998196.1998228</a>.","ista":"Chen C, Kerber M. 2011. An output sensitive algorithm for persistent homology. SoCG: Symposium on Computational Geometry, 207–216.","ieee":"C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” presented at the SoCG: Symposium on Computational Geometry, Paris, France, 2011, pp. 207–216.","ama":"Chen C, Kerber M. An output sensitive algorithm for persistent homology. In: ACM; 2011:207-216. doi:<a href=\"https://doi.org/10.1145/1998196.1998228\">10.1145/1998196.1998228</a>","short":"C. Chen, M. Kerber, in:, ACM, 2011, pp. 207–216."},"quality_controlled":"1"},{"abstract":[{"text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. Our work is restricted to homology over the ℤ2 field.","lang":"eng"}],"acknowledgement":"Partially supported by the Austrian Science Fund under grantFSP-S9103-N04 and P20134-N13.","date_updated":"2023-02-23T11:19:46Z","year":"2010","day":"01","author":[{"full_name":"Chen, Chao","last_name":"Chen","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"full_name":"Freedman, Daniel","last_name":"Freedman","first_name":"Daniel"}],"_id":"10909","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics","status":"public","publication_identifier":{"eisbn":["9781611973075"]},"title":"Hardness results for homology localization","month":"02","doi":"10.1137/1.9781611973075.129","publication_status":"published","conference":{"start_date":"2010-01-17","name":"SODA: Symposium on Discrete Algorithms","end_date":"2010-01-19","location":"Austin, TX, United States"},"publication":"Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms","date_created":"2022-03-21T08:24:07Z","page":"1594-1604","type":"conference","oa_version":"None","department":[{"_id":"HeEd"}],"date_published":"2010-02-01T00:00:00Z","language":[{"iso":"eng"}],"article_processing_charge":"No","scopus_import":"1","citation":{"short":"C. Chen, D. Freedman, in:, Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010, pp. 1594–1604.","ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” in <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Austin, TX, United States, 2010, pp. 1594–1604.","ama":"Chen C, Freedman D. Hardness results for homology localization. In: <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2010:1594-1604. doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2010, pp. 1594–604, doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>.","ista":"Chen C, Freedman D. 2010. Hardness results for homology localization. Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1594–1604.","apa":"Chen, C., &#38; Freedman, D. (2010). Hardness results for homology localization. In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1594–1604). Austin, TX, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1594–1604. Society for Industrial and Applied Mathematics, 2010. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>."},"quality_controlled":"1","related_material":{"record":[{"id":"3267","relation":"later_version","status":"public"}]}},{"quality_controlled":"1","citation":{"ama":"Chen C, Freedman D. Topology noise removal for curve  and surface evolution. In: <i> Conference Proceedings MCV 2010</i>. Vol 6533. Springer; 2010:31-42. doi:<a href=\"https://doi.org/10.1007/978-3-642-18421-5_4\">10.1007/978-3-642-18421-5_4</a>","ieee":"C. Chen and D. Freedman, “Topology noise removal for curve  and surface evolution,” in <i> Conference proceedings MCV 2010</i>, Beijing, China, 2010, vol. 6533, pp. 31–42.","short":"C. Chen, D. Freedman, in:,  Conference Proceedings MCV 2010, Springer, 2010, pp. 31–42.","ista":"Chen C, Freedman D. 2010. Topology noise removal for curve  and surface evolution.  Conference proceedings MCV 2010. MCV: Medical Computer Vision, LNCS, vol. 6533, 31–42.","apa":"Chen, C., &#38; Freedman, D. (2010). Topology noise removal for curve  and surface evolution. In <i> Conference proceedings MCV 2010</i> (Vol. 6533, pp. 31–42). Beijing, China: Springer. <a href=\"https://doi.org/10.1007/978-3-642-18421-5_4\">https://doi.org/10.1007/978-3-642-18421-5_4</a>","mla":"Chen, Chao, and Daniel Freedman. “Topology Noise Removal for Curve  and Surface Evolution.” <i> Conference Proceedings MCV 2010</i>, vol. 6533, Springer, 2010, pp. 31–42, doi:<a href=\"https://doi.org/10.1007/978-3-642-18421-5_4\">10.1007/978-3-642-18421-5_4</a>.","chicago":"Chen, Chao, and Daniel Freedman. “Topology Noise Removal for Curve  and Surface Evolution.” In <i> Conference Proceedings MCV 2010</i>, 6533:31–42. Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-18421-5_4\">https://doi.org/10.1007/978-3-642-18421-5_4</a>."},"volume":6533,"intvolume":"      6533","publist_id":"2445","scopus_import":1,"type":"conference","oa_version":"None","date_published":"2010-12-31T00:00:00Z","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-18421-5_4","conference":{"name":"MCV: Medical Computer Vision","start_date":"2010-09-20","location":"Beijing, China","end_date":"2010-09-20"},"publication_status":"published","publication":" Conference proceedings MCV 2010","date_created":"2018-12-11T12:05:08Z","page":"31 - 42","alternative_title":["LNCS"],"month":"12","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","status":"public","title":"Topology noise removal for curve  and surface evolution","author":[{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao"},{"first_name":"Daniel","last_name":"Freedman","full_name":"Freedman, Daniel"}],"_id":"3782","acknowledgement":"Partially supported by the Austri an Science Fund unde r grant P20134-N13.\r\nWe thank Helena Molina-Abril for very helpful discussion. We thank anonymous reviewers for helpful comments.","abstract":[{"text":"In cortex surface segmentation, the extracted surface is required to have a particular topology, namely, a two-sphere. We present a new method for removing topology noise of a curve or surface within the level set framework, and thus produce a cortical surface with correct topology. We define a new energy term which quantifies topology noise. We then show how to minimize this term by computing its functional derivative with respect to the level set function. This method differs from existing methods in that it is inherently continuous and not digital; and in the way that our energy directly relates to the topology of the underlying curve or surface, versus existing knot-based measures which are related in a more indirect fashion. The proposed flow is validated empirically.","lang":"eng"}],"date_updated":"2021-01-12T07:52:10Z","year":"2010","day":"31"}]