{"662217":{"#nid":"662217","#data":{"type":"news","title":"Mathematicians Discover Highly Efficient Method for Solving \u2018Hard Minimal Problems\u2019","body":[{"value":"\u003Cp\u003EA team led by Georgia Tech mathematician \u003Ca href=\u0022https:\/\/math.gatech.edu\/people\/anton-leykin\u0022\u003EAnton Leykin\u003C\/a\u003E has developed a powerful new technique for solving problems related to 3D reconstruction. The research team\u0026rsquo;s open access paper, \u003Ca href=\u0022https:\/\/www.researchgate.net\/publication\/356842134_Learning_to_Solve_Hard_Minimal_Problems\u0022\u003E\u0026quot;Learning to Solve Hard Minimal Problems\u0026quot;\u003C\/a\u003E, has also won the prestigious \u003Ca href=\u0022https:\/\/cvpr2022.thecvf.com\/cvpr-2022-paper-awards\u0022\u003Ebest paper award at CVPR 2022\u003C\/a\u003E, the Computer Vision and Pattern Recognition Conference (CVPR) \u0026mdash; selected from a pool of over 8,000 papers submitted this year.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe team\u0026rsquo;s research idea revolved around developing a new way to solve a family of problems known as hard minimal problems, which are essential for 3D reconstruction. \u0026ldquo;A minimal problem is a smallest geometric problem one can consider in the 3D reconstruction context,\u0026rdquo; Leykin explained. \u0026ldquo;For example, recovering a 3D scene consisting of 5 points from 2 views (2-dimensional images of 5 points in the plane) without knowing the relative position and orientation of the second camera with respect to the first.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn other words, the problem focuses on \u0026ldquo;solving\u0026rdquo; how to see in three dimensions by analyzing multiple two-dimensional perspectives \u0026mdash; this is how humans and self-driving cars see in 3D. One way to understand this is by imagining our eyes as cameras. Both eyes capture two-dimensional images, each from a slightly different perspective. By considering the perspective of the image sent by each eye, our brains create a 3D rendering of these two-dimensional images. While our brains might do this with seeming ease in the case of our vision, solving these problems mathematically can be more difficult.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/inf.ethz.ch\/people\/people-atoz\/person-detail.MjkzNjg5.TGlzdC8zMDQsLTIxNDE4MTU0NjA=.html\u0022\u003EPetr Hruby\u003C\/a\u003E, currently a Ph.D. student at the ETH Zurich Department of Computer Science, with a recent Master\u0026rsquo;s degree from Czech Technical University, serves as the paper\u0026rsquo;s lead author. He is joined by co-authors Leykin, a professor in the \u003Ca href=\u0022https:\/\/math.gatech.edu\/\u0022\u003ESchool of Mathematics\u003C\/a\u003E at \u003Ca href=\u0022https:\/\/research.gatech.edu\/\u0022\u003EGeorgia Tech\u003C\/a\u003E; \u003Ca href=\u0022https:\/\/math.washington.edu\/people\/timothy-duff\u0022\u003ETimothy Duff\u003C\/a\u003E, NSF Postdoctoral Fellow at the University of Washington (Georgia Tech Ph.D. in \u003Ca href=\u0022https:\/\/aco.gatech.edu\/\u0022\u003EAlgorithms, Combinatorics, and Optimization\u003C\/a\u003E, 2021); and \u003Ca href=\u0022https:\/\/cvut.academia.edu\/TomasPajdla\u0022\u003ETomas Pajdla\u003C\/a\u003E, professor at the Czech Technical University in Prague Czech Institute of Informatics, Robotics and Cybernetics. The core of the team started working together during \u003Ca href=\u0022https:\/\/icerm.brown.edu\/programs\/sp-f18\/\u0022\u003Ethe Institute for Computational and Experimental Research in Mathematics (ICERM) semester on Nonlinear Algebra in 2018\u003C\/a\u003E, of which Leykin was the primary organizer.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAfter \u003Ca href=\u0022https:\/\/syncedreview.com\/2019\/10\/29\/iccv-2019-best-papers-announced\/\u0022\u003Etheir first project won the best student paper award at the 2019 International Conference on Computer Vision (ICCV)\u003C\/a\u003E, the team decided to pursue research in hard minimal problems.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESince the technique the researchers developed is general, Leykin said it can be applied to many other situations with similar mathematical problems. In addition, the \u003Ca href=\u0022https:\/\/github.com\/petrhruby97\/learning_minimal\u0022\u003Esoftware pieces derived from the researchers\u0026rsquo; findings are in the public domain\u003C\/a\u003E, and can be used by a broad computer vision community.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESolve-and-Pick vs. Pick-and-Solve\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESolving minimal problems can be difficult, because they often have many spurious solutions (solutions that might solve the equation, but are ultimately unhelpful or unexpected).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPreviously, the state-of-the-art technique for solving minimal problems used a \u0026ldquo;solve-and-pick\u0026rdquo; approach. Solve-and-pick involves first determining all of the possible solutions to a problem, and then picking the optimal solutions \u0026mdash; this is done by removing non-real solutions, using inequalities, and evaluating how well they support the solution. But, when there are many spurious solutions, this type of optimization can be costly and time-consuming.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EInstead of using this traditional solve-and-pick approach, the researchers investigated the opposite: a \u0026ldquo;pick-and-solve\u0026rdquo; technique that learns, for a given data sample, how to first pick a promising starting point and then continue it to a meaningful solution. This approach is unique in that it avoids computing large numbers of spurious solutions.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBy selecting a suitable starting point and solving from that point (instead of solving from all points), the method can quickly find and track a path to the solution more quickly, learning how to find that target solution more efficiently.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;Instead of finding all possible solutions and then deciding which one is relevant, we aimed at \u0026lsquo;guessing\u0026rsquo; which path leads to one physically meaningful solution \u0026mdash; as long as the guess is correct with high probability, this becomes practically useful,\u0026rdquo; said Leykin. \u0026ldquo;For a \u0026lsquo;hard\u0026rsquo; minimal problem, this is like finding a needle in a haystack \u0026mdash; we need to guess one correct path out of several hundreds.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETo do so, the research combined concepts spanning several fields of mathematics: algebra, geometry, numerical analysis, and statistics. Computer science and engineering components also played a vital role: \u0026ldquo;We had to use neural networks for one particular task and, of course, implement the algorithms efficiently,\u0026rdquo; Leykin said. Since the minimal problem solvers are executed as subroutines millions, billions, or trillions of times, efficiency was essential.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESolving the hard problems\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETo test their method, the researchers developed a solver using their pick-and-solve technique for a well-known problem in the field. They benchmarked and studied their engineering choices with another familiar problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFinally, they applied their technique to a harder problem \u0026ndash; reconstructing a 3D view using four 2D points in three views. The researchers\u0026rsquo; implementation of their method solves this problem in about 70 microseconds on average \u0026ndash; ten times faster than any other method.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe team hopes that their solution could change how these problems are approached and solved in the future. \u0026ldquo;Previously, \u0026lsquo;hard\u0026rsquo; minimal problems were avoided in practical applications, since there were no fast reliable solvers for them,\u0026rdquo; Leykin said. \u0026ldquo;We hope that, over time, our work will convince the industry to reconsider \u0026ndash; the \u0026lsquo;hard\u0026rsquo; problems are not that hard after all!\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/math.gatech.edu\/seminars-colloquia\/series\/school-mathematics-colloquium\/anton-leykin-20221013\u0022\u003ELeykin will soon deliver a colloquium\u003C\/a\u003E on the work with the School of Mathematics. \u003Ca href=\u0022https:\/\/math.gatech.edu\/this-week-s-seminar-and-colloquia\u0022\u003ELearn more\u003C\/a\u003E.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003ECitation:\u003Cbr \/\u003E\r\nHruby, Petr \u0026amp; Duff, Timothy \u0026amp; Leykin, Anton \u0026amp; Pajdla, Tomas. (2021). Learning to Solve Hard Minimal Problems.\u003C\/em\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":[{"value":"Implications of new research span from math, to helping autonomous vehicles use 2D camera images to \u201csee\u201d in three dimensions, and beyond. "}],"field_summary":[{"value":"\u003Cp\u003EA team led by Georgia Tech mathematician Anton Leykin has developed a powerful new technique for solving problems related to 3D reconstruction. The research team\u0026rsquo;s paper has also won the prestigious best paper award at CVPR 2022. The team hopes that their method \u0026mdash; which can solve some of these problems significantly faster than any previous technique \u0026mdash; could change how these problems are approached and solved in mathematics, computer science, and industrial applications.\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"A team led by Georgia Tech mathematician Anton Leykin has developed a powerful new technique for solving problems related to 3D reconstruction."}],"uid":"34518","created_gmt":"2022-10-17 17:22:02","changed_gmt":"2022-10-17 17:22:32","author":"sbarone7","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2022-10-10T00:00:00-04:00","iso_date":"2022-10-10T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"662216":{"id":"662216","type":"image","title":"slide_leykin_hard_minimal","body":null,"created":"1666027308","gmt_created":"2022-10-17 17:21:48","changed":"1666027308","gmt_changed":"2022-10-17 17:21:48","alt":"","file":{"fid":"250799","name":"slide_leykin_hard_minimal.png","image_path":"\/sites\/default\/files\/images\/slide_leykin_hard_minimal.png","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/slide_leykin_hard_minimal.png","mime":"image\/png","size":94920,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/slide_leykin_hard_minimal.png?itok=8IPs3luR"}},"661974":{"id":"661974","type":"image","title":"Anton Leykin, Professor in the School of Mathematics","body":null,"created":"1665410176","gmt_created":"2022-10-10 13:56:16","changed":"1665424192","gmt_changed":"2022-10-10 17:49:52","alt":"","file":{"fid":"250735","name":"Anton_Leykin.jpeg","image_path":"\/sites\/default\/files\/images\/Anton_Leykin.jpeg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/Anton_Leykin.jpeg","mime":"image\/jpeg","size":106012,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/Anton_Leykin.jpeg?itok=rsDrZKKO"}},"661975":{"id":"661975","type":"image","title":"Multiple 2D photographs taken from different locations can be used to create a 3D image \u2014 solving minimal problems allows the 3D image to be rendered. Source: \u0022Continuous ratio optimization via convex relaxation with app...\u0022 doi: 10.1109\/CVPR.2009.5206608","body":null,"created":"1665412713","gmt_created":"2022-10-10 14:38:33","changed":"1665424096","gmt_changed":"2022-10-10 17:48:16","alt":"","file":{"fid":"250737","name":"1_Y_42IRgvwqM7_mhVkpP41A.jpg","image_path":"\/sites\/default\/files\/images\/1_Y_42IRgvwqM7_mhVkpP41A.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/1_Y_42IRgvwqM7_mhVkpP41A.jpg","mime":"image\/jpeg","size":73988,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/1_Y_42IRgvwqM7_mhVkpP41A.jpg?itok=wa9YywPs"}}},"media_ids":["662216","661974","661975"],"groups":[],"categories":[{"id":"135","name":"Research"}],"keywords":[{"id":"168854","name":"School of Mathematics"},{"id":"191409","name":"hard minimal problems"},{"id":"191410","name":"Anton Leykin"},{"id":"191411","name":"3d reconstruction"},{"id":"170067","name":"mathematics research"},{"id":"173647","name":"_for_math_site_"}],"core_research_areas":[{"id":"39431","name":"Data Engineering and Science"},{"id":"39501","name":"People and Technology"},{"id":"39541","name":"Systems"}],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EBy: Selena Langner\u003Cbr \/\u003E\r\nWriter, College of Sciences at Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EEditor:\u0026nbsp;\u003Ca href=\u0022mailto:jess@cos.gatech.edu\u0022\u003EJess Hunt-Ralston\u003C\/a\u003E\u003Cbr \/\u003E\r\nDirector of Communications\u003Cbr \/\u003E\r\nCollege of Sciences at Georgia Tech\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["jess.hunt@cos.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}