{"id":73,"date":"2006-07-27T12:59:14","date_gmt":"2006-07-27T16:59:14","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=73"},"modified":"2019-10-22T14:00:59","modified_gmt":"2019-10-22T18:00:59","slug":"spatial-transformations-handling-noninvertible-cases","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2006\/07\/27\/spatial-transformations-handling-noninvertible-cases\/","title":{"rendered":"Spatial transformations: Handling noninvertible cases"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>I've <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=55\">written previously<\/a> about how <tt>imtransform<\/tt> uses inverse mapping to compute the input-space location corresponding to each output pixel. I've <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=63\">also written<\/a> about how imtransform uses the forward mapping to determine the location of the output image in output space.\r\n   <\/p>\r\n   <p>But what about noninvertible mappings?  For example, the function <tt>cp2tform<\/tt> can produce several types of spatial transformations that aren't invertible.  It can infer a polynomial transformation from\r\n      a set of control points:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">pairs1 = [1 1; 5 21; 17 40; 28 1; 32 20; 45 40; 72 1; 77 20; 90 40];\r\npairs2 = [1 1; 1 21; 1 40; 20 1; 20 20; 20 40; 40 1; 40 20; 40 40];\r\nt_poly = cp2tform(pairs1, pairs2, <span style=\"color: #A020F0\">'polynomial'<\/span>,2);\r\nI = checkerboard(10, 2);\r\nJ = imtransform(I,t_poly);\r\n\r\nsubplot(1,2,1)\r\nimshow(I), title(<span style=\"color: #A020F0\">'checkerboard'<\/span>)\r\n\r\nsubplot(1,2,2)\r\nimshow(J), title(<span style=\"color: #A020F0\">'polynomial transformation'<\/span>)<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/72\/findbounds_search_01.png\"> <p>But the polynomial transformation isn't invertible.  Since <tt>imtransform<\/tt> uses inverse mapping and so must have at least the inverse transformation, <tt>cp2tform<\/tt> produces a tform structure where the polynomial transformation is used in the inverse direction, and the structure contains\r\n      nothing for the forward direction.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">t_poly<\/pre><pre style=\"font-style:oblique\">\r\nt_poly = \r\n\r\n       ndims_in: 2\r\n      ndims_out: 2\r\n    forward_fcn: []\r\n    inverse_fcn: @inv_polynomial\r\n          tdata: [6x2 double]\r\n\r\n<\/pre><p>If there's no forward transformation available, then how does <tt>findbounds<\/tt> work?  That is, how does it find the bounding rectangle of the image in output space?\r\n   <\/p>\r\n   <p>It does it by using a search.  Specifically, for an input-space location <b>u<\/b>, it uses <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/fminsearch.html\"><tt>fminsearch<\/tt><\/a> to find the output-space location <b>x<\/b> that minimizes:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/72\/findbounds_search_eq6538.png\"> <\/p>\r\n   <p>It's possible <tt>fminsearch<\/tt> might fail to converge, in which case <tt>findbounds<\/tt> issues a warning message and \"guesses\" that the output image's bounding rectangle is the same as the input image's bounding\r\n      rectangle.\r\n   <\/p>\r\n   <p>If you're interested in the details, look at the <tt>find_bounds_using_search<\/tt> subfunction inside <tt>findbounds.m<\/tt>.\r\n   <\/p>\r\n <script language=\"JavaScript\"> \r\n    function grabCode_73() {\r\n<!--\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='73 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 73';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Steve Eddins';\r\n        copyright = 'Copyright 2006 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n-->\r\n      <\/script>\r\n<noscript>\r\n<em>A JavaScript-enabled browser is required to use the \"Get the MATLAB code\" link.<\/em>\r\n<\/noscript>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_73()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code<\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.2<br><\/p>\r\n<\/div>\r\n<!--\r\n73 ##### SOURCE BEGIN #####\r\n%% Spatial transformations: Handling noninvertible cases\r\n% I've <https:\/\/blogs.mathworks.com\/steve\/?p=55\r\n% written previously> about how \r\n% <https:\/\/www.mathworks.com\/help\/images\/index.htmlimtransform.html\r\n% |imtransform|> uses inverse mapping to\r\n% compute the input-space location corresponding to each output pixel. I've\r\n% <https:\/\/blogs.mathworks.com\/steve\/?p=63 also \r\n% written> about how imtransform uses the forward mapping to determine\r\n% the location of the output image in output space.\r\n%\r\n% But what about noninvertible mappings?  For example, the function\r\n% <https:\/\/www.mathworks.com\/help\/images\/index.htmlcp2tform.html\r\n% |cp2tform|> can produce several types of spatial transformations that aren't\r\n% invertible.  It can infer a polynomial transformation\r\n% from a set of control points:\r\n\r\npairs1 = [1 1; 5 21; 17 40; 28 1; 32 20; 45 40; 72 1; 77 20; 90 40];\r\npairs2 = [1 1; 1 21; 1 40; 20 1; 20 20; 20 40; 40 1; 40 20; 40 40];\r\nt_poly = cp2tform(pairs1, pairs2, 'polynomial',2);\r\nI = checkerboard(10, 2);\r\nJ = imtransform(I,t_poly);\r\n\r\nsubplot(1,2,1)\r\nimshow(I), title('checkerboard')\r\n\r\nsubplot(1,2,2)\r\nimshow(J), title('polynomial transformation')\r\n\r\n%%\r\n% But the polynomial transformation isn't invertible.  Since |imtransform|\r\n% uses inverse mapping and so must have at least the inverse\r\n% transformation, |cp2tform| produces a tform structure where the polynomial\r\n% transformation is used in the inverse direction, and the structure\r\n% contains nothing for the forward direction.\r\n\r\nt_poly\r\n\r\n%%\r\n% If there's no forward transformation available, then how does\r\n% |findbounds|\r\n% work?  That is, how does it find the bounding rectangle of the image in\r\n% output space?\r\n%\r\n% It does it by using a search.  Specifically, for an input-space location \r\n% *u*, \r\n% it uses \r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/fminsearch.html\r\n% |fminsearch|> to find the output-space location *x* that minimizes:\r\n%\r\n% $$||u - T^{-1}\\{x\\}||$$\r\n% \r\n% It's possible |fminsearch| might fail to converge, in which case\r\n% |findbounds|\r\n% issues a warning message and \"guesses\" that the output image's bounding\r\n% rectangle is the same as the input image's bounding rectangle.\r\n%\r\n% If you're interested in the details, look at the\r\n% |find_bounds_using_search|\r\n% subfunction inside |findbounds.m|.\r\n\r\n##### SOURCE END ##### 73\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   I've written previously about how imtransform uses inverse mapping to compute the input-space location corresponding to each output pixel. I've also written about how imtransform uses the... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2006\/07\/27\/spatial-transformations-handling-noninvertible-cases\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[182,98,184,36,44,72,52],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/73"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=73"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/73\/revisions"}],"predecessor-version":[{"id":2196,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/73\/revisions\/2196"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=73"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=73"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=73"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}