Two-dimensional phase unwrapping via balanced spanning forests. Herszterg, I., Poggi, M., & Vidal, T. INFORMS Journal on Computing, 31(3):527–543, 2019.
Paper doi abstract bibtex 4 downloads Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$π$,$π$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.
@article{Herszterg2019,
abstract = {Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$\pi$,$\pi$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.},
annote = {1. Matheus Suknaic
2. Gabriel},
author = {Herszterg, I. and Poggi, M. and Vidal, T.},
doi = {10.1287/ijoc.2018.0832},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Herszterg, Poggi, Vidal/Herszterg, Poggi, Vidal - 2019 - Two-dimensional phase unwrapping via balanced spanning forests.pdf:pdf},
institution = {PUC-Rio},
journal = {INFORMS Journal on Computing},
mendeley-groups = {Teaching/INF2982-Modeling/Paper-Analysis,Teaching/INF2982-Modeling/Implementation},
number = {3},
pages = {527--543},
title = {{Two-dimensional phase unwrapping via balanced spanning forests}},
url = {https://arxiv.org/pdf/1812.08277.pdf},
volume = {31},
year = {2019}
}
Downloads: 4
{"_id":"xAhTZeThkrGiXbEQW","bibbaseid":"herszterg-poggi-vidal-twodimensionalphaseunwrappingviabalancedspanningforests-2019","authorIDs":["22qDSn3MhX9SE4QdJ","2eyrFQa9PCh5a8ea8","39vXMT4DP7K7Xq3aP","3yYf56wRPnWkN3Smu","3ynfnu9dzwCpjFyP8","4Cqr7mXmuwMcqmZgp","4LBfmwfTjMaiaWZGp","4h7RQtjm26FN2JHmm","5949255825f5fd9d7000004b","5CGJTxHpzSPzfjCzW","5de7abebbc280fdf01000076","5de7d6665e1638de010001f9","5de86a278ff138de0100014d","5dea95b1a71b4bdf0100014d","5dec4d93e16431f20100007b","5df133638fc423de01000199","5df1c8e21070c8ef0100003a","5df6f76fdf3bb9f201000085","5dfa57207d1403df01000026","5dfb19d0f85d64df01000004","5dfb3f97e04f92df0100007e","5dfd53b3991725de0100005a","5e01ffc621cdf8e4010000f1","5e02a17d64e549de01000091","5e0907cd79e131f3010000c7","5e0c109b24223cde01000043","5e0c88d9464605de010000c7","5e10d31b0192c6df010000b7","5e14d212429a53df01000027","5e14f043b46f1bdf0100005c","5e15757a1e2528de010000f8","5e1787e6cf35a4de0100019b","5e191498a7672ede01000136","5e1bb58061cb16df010000b8","5e1c5a47e556c6de0100015d","5e231b5f327a15de01000022","5e232ec8327a15de010000c7","5e23793bba9fb2de0100006f","5e25e56fa6f19fde0100012b","5e27b34528f7a6de0100014d","5e284bcbc4828cde010000b8","5e2895e288416fde01000018","5e28b0ef88416fde01000249","5e2b96caf92538df01000069","5e2f15434557f3de01000051","5e3002375bfc8ede010000e3","5e301fb77e0df1de0100011d","5e35f9c85cd57fde0100012a","5e36e2d6b26a0fde01000036","5e3800a6918d4ede010000c3","5e3c566fc798e0de0100015a","5e3c6a5767788ede010000be","5e3ce3ee5cd237de010000de","5e3d7c5596e576de0100006a","5e3dbff807ca74de01000114","5e3f1f497da304de01000027","5e4048bc668183de010000e1","5e410989f47523de010000a2","5e4161f2a59dc8df01000194","5e438e29639a35de0100009f","5e44200ffdc393de01000154","5e458c3686f11cdf01000140","5e460590a5737fde010000f1","5e480eabd4b913df0100007e","5e49e5e4885ce9df01000030","5e49ff68cc11a8df0100003a","5e4ab3b715f6c7df0100013c","5e4ac8d70d7631de01000082","5e4b0bee332a9bde01000108","5e4b1b96c59ab1f301000073","5e4c1bfc2dc400de0100010d","5e4d19527d0ec8de010000c2","5e4d25f47d0ec8de01000193","5e4ec057d9cddadf010000be","5e4eefc9338acfde01000033","5e4fede9f5b214df0100004f","5e533cc853de8dde01000031","5e538be6c02a31de01000016","5e54548088d190df0100005c","5e54fb7396ed20df01000020","5e56f3297840dfde01000015","5e582d0a1f3fc8de0100004c","5e5983f48049fcde01000094","5e5bfabed49321e0010000ce","5e5e04335c89fadf0100005e","5e5e26241e54a8df010002af","5e5e3439d3955dde01000021","5e5e3dccd3955dde010000c3","5e5f25518ca867de010000cf","5e5f69665766d9df01000011","5e5fdf9f5241b5de0100007f","5e6094a61fc211de010000bf","5e610b8c31c7d3de01000230","5e62bb57cb259cde0100008b","5e664abda77c4ade01000186","5e67a2bbd527f0de01000265","5e67feb9c1fce0de0100009b","5e6944466964dedf010002bd","5e69b3a123ebccde010001ea","5e6a14be38f351de01000097","6WaMPc3WMEYRf7aPs","6cETYuzEQYR8retFE","73FqktCgC2KRA2tAD","77tduPzfw3m3JNLL6","7A4HJ6DsPznXh7sve","85SGCBAgyjBo8EqhX","8RrxAppjhLH77rYBj","8mYe662FHks9DGP85","9Z6sLhM7Nf8JZW73M","9jZjeCWjPWp9GPhLZ","AQi5akoC7Gjoyos7P","BefrwkyiR8J7BpH2P","BgyqbABx82ccGwh7u","BsQpRnmxZAAaM5Dvv","CEofRTEfHXQmYXKmf","CHtRiPZPkRwY2Zj7P","CJsebKwmHZXfYfMjo","CPLtxLfbnrfQSHGiB","CjLc4EpPxRncABnnr","DA2hGTyXJ5QDgZY9P","DLXuK3bF2C2gr44vp","DPRDMkXjBidpi4TDy","EB5vie87D5rRFQRhH","FDhjZxCHhq2XiFeZ2","GSx5d2F7X439yA2yB","GwDyrbRR6A99TwkQC","GySvg6ZigwYkBPRZs","H4XtJC6XB9eB3E6de","Hc4Gb76fWgRBHmdb9","Jq73HtWDoKQ3JAwWo","KB5iWzr6nWj8bhRbP","KdiQQfsPGngvzYnj8","KkA72QCdDyG25v3ja","Koq8bRcrKQiGCJQ68","L2iNP5AjTduSscwoZ","Lak6KrCQjwkDWRTjG","M6ki37ZgE3yNsAfkL","MiMQgwyyJwJtxDBvk","MwBJWB9CH2kRd7DSa","MyM8bFL9PbJnj6xFj","NsK8HbdNJ7HrJ4CWt","NykasPxRbNPkYaFi6","P7tL46FCmpstpzc5G","Q9mdkfHXYB4L73a7z","R9evTLxzdqHJ6gg56","RDcEjnEuS49kyJbq7","RmCCdPrWkPKcvg8aE","Ru7stmEDSYkhFjtfB","SEL27kiy54WCdaK9P","Txq35A3ycpsEHJFEF","WQuu6QAQ4uygwgjJj","XJsoGYbpczCFkxyff","XPZWQtjJms9WJenoJ","XmDEEHxsYeqKxtds5","Y6ecKF4QK6uxEeD9a","Yj6btsirruZaWE6bm","a6uiXNEZFSTrwZqxY","avZwQMkQEEAjz9udR","awoTsndRPACdYbwLY","bJENH3RRYCbXdmWai","e8uLXuJtLro7DMw49","ehJ7KjD2Aqb9Efd6v","fsKEgFS3pySqRFdMc","gM9KMcoXiWZtAj5sY","gjjADg9JGSWhj8qbx","gxRgZbcdc2KFBF2o6","hsaFAvcArcu6EBHjb","iLPFjodLsRfo6uhmu","iX5PbZ3cMwgEWwC2k","jg9mQ5WtEN5o4kBZG","jxdbCYtZMzy4EdpP5","mH28RcRpdPG275rWc","mXJzPLn7g897B6cRE","mo3mdPgNy6xeyHTTw","nEaHJmLgCx2WtmFji","nHPSALCyaatA3Mgbv","ndYtnzwfxuqRuRQLz","o63vPZA3v7dSNBwsb","oD9oSutzwynEe9NXj","oijLT2TDpdc9T2CA5","qxrYJuZmthuQxnpdc","sYrkHzi2HZP2SDK7k","sjyTppdABxdRywBvL","suy82rpLS7tJ6H6Bw","t2dQWQPFqMuvbZaWa","ta4Ded5yZwWqpNab2","trPFdvK4jZKXXFfyZ","uLHCaJrHCX3XMyF8o","uyCNkc8aT5C6evZJD","voCzhan7GbpJ2Xg7n","vsedCHjb2BzDhg3oC","wChRzg6qYmaDdwjK9","wRbdKdQfwW38tKHrD","whTqfamkmDjHode9m","xMCrLWJ5bnK4scREL","xxR6RTsWFRB3CNo8r","ztt88xLAbCEz33TEh"],"author_short":["Herszterg, I.","Poggi, M.","Vidal, T."],"bibdata":{"bibtype":"article","type":"article","abstract":"Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$π$,$π$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.","annote":"1. Matheus Suknaic 2. Gabriel","author":[{"propositions":[],"lastnames":["Herszterg"],"firstnames":["I."],"suffixes":[]},{"propositions":[],"lastnames":["Poggi"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]}],"doi":"10.1287/ijoc.2018.0832","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Herszterg, Poggi, Vidal/Herszterg, Poggi, Vidal - 2019 - Two-dimensional phase unwrapping via balanced spanning forests.pdf:pdf","institution":"PUC-Rio","journal":"INFORMS Journal on Computing","mendeley-groups":"Teaching/INF2982-Modeling/Paper-Analysis,Teaching/INF2982-Modeling/Implementation","number":"3","pages":"527–543","title":"Two-dimensional phase unwrapping via balanced spanning forests","url":"https://arxiv.org/pdf/1812.08277.pdf","volume":"31","year":"2019","bibtex":"@article{Herszterg2019,\nabstract = {Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$\\pi$,$\\pi$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.},\nannote = {1. Matheus Suknaic\n2. Gabriel},\nauthor = {Herszterg, I. and Poggi, M. and Vidal, T.},\ndoi = {10.1287/ijoc.2018.0832},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Herszterg, Poggi, Vidal/Herszterg, Poggi, Vidal - 2019 - Two-dimensional phase unwrapping via balanced spanning forests.pdf:pdf},\ninstitution = {PUC-Rio},\njournal = {INFORMS Journal on Computing},\nmendeley-groups = {Teaching/INF2982-Modeling/Paper-Analysis,Teaching/INF2982-Modeling/Implementation},\nnumber = {3},\npages = {527--543},\ntitle = {{Two-dimensional phase unwrapping via balanced spanning forests}},\nurl = {https://arxiv.org/pdf/1812.08277.pdf},\nvolume = {31},\nyear = {2019}\n}\n","author_short":["Herszterg, I.","Poggi, M.","Vidal, T."],"key":"Herszterg2019","id":"Herszterg2019","bibbaseid":"herszterg-poggi-vidal-twodimensionalphaseunwrappingviabalancedspanningforests-2019","role":"author","urls":{"Paper":"https://arxiv.org/pdf/1812.08277.pdf"},"metadata":{"authorlinks":{"vidal, t":"https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib"}},"downloads":4,"html":""},"bibtype":"article","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My Collection.bib","creationDate":"2019-06-19T22:50:47.527Z","downloads":4,"keywords":[],"search_terms":["two","dimensional","phase","unwrapping","via","balanced","spanning","forests","herszterg","poggi","vidal"],"title":"Two-dimensional phase unwrapping via balanced spanning forests","year":2019,"dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"]}