{"id":78,"date":"2006-10-04T09:09:28","date_gmt":"2006-10-04T13:09:28","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=78"},"modified":"2019-10-22T16:28:00","modified_gmt":"2019-10-22T20:28:00","slug":"separable-convolution","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2006\/10\/04\/separable-convolution\/","title":{"rendered":"Separable convolution"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>The <a href=\"http:\/\/groups.google.com\/group\/sci.image.processing?hl=en\">sci.image.processing<\/a> newsgroup had a <a href=\"http:\/\/groups.google.com\/group\/sci.image.processing\/browse_thread\/thread\/fc567d195431fd7c\/48f08910b4c3c465?lnk=st&amp;q=&amp;rnum=3&amp;hl=en#48f08910b4c3c465\">discussion this week<\/a> on separable filters, which reminded me that separability has been on my blog topic ideas list for a while now.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">What is a separable filter?<\/a><\/li>\r\n         <li><a href=\"#5\">Associativity of convolution<\/a><\/li>\r\n         <li><a href=\"#7\">Computational advantage of separable convolution<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>What is a separable filter?<a name=\"1\"><\/a><\/h3>\r\n   <p>A two-dimensional filter kernel is <i>separable<\/i> if it can be expressed as the outer product of two vectors.  For example, let's look at a Sobel kernel.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">s = [-1 0 1; -2 0 2; -1 0 1]<\/pre><pre style=\"font-style:oblique\">\r\ns =\r\n\r\n    -1     0     1\r\n    -2     0     2\r\n    -1     0     1\r\n\r\n<\/pre><p>This kernel can be written as a matrix product of a column and a row vector.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">v = [1; 2; 1]<\/pre><pre style=\"font-style:oblique\">\r\nv =\r\n\r\n     1\r\n     2\r\n     1\r\n\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">h = [-1 0 1]<\/pre><pre style=\"font-style:oblique\">\r\nh =\r\n\r\n    -1     0     1\r\n\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">v * h<\/pre><pre style=\"font-style:oblique\">\r\nans =\r\n\r\n    -1     0     1\r\n    -2     0     2\r\n    -1     0     1\r\n\r\n<\/pre><h3>Associativity of convolution<a name=\"5\"><\/a><\/h3>\r\n   <p>As it turns out, the matrix product of a column vector and a row vector is equivalent to the two-dimensional convolution of\r\n      the two vectors.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">conv2(v, h)<\/pre><pre style=\"font-style:oblique\">\r\nans =\r\n\r\n    -1     0     1\r\n    -2     0     2\r\n    -1     0     1\r\n\r\n<\/pre><p>This matters because convolution is associative.  That is,<\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/78\/separable_filters_eq27697.png\"> <\/p>\r\n   <p>(I've used the asterix here to mean convolution.)  So if a filter <i>s<\/i> is separable:\r\n   <\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/78\/separable_filters_eq2722.png\"> <\/p>\r\n   <p>then you can filter with <i>s<\/i> by filtering first with <i>v<\/i>, and then filtering the result with <i>h<\/i>.\r\n   <\/p>\r\n   <h3>Computational advantage of separable convolution<a name=\"7\"><\/a><\/h3>\r\n   <p>Why would you want to filter this way?  Because you can do it faster. Filtering an M-by-N image with a P-by-Q filter kernel\r\n      requires roughly <i>MNPQ<\/i> multiplies and adds (assuming we aren't using an implementation based on the FFT).  If the kernel is separable, you can filter\r\n      in two steps.  The first step requires about <i>MNP<\/i> multiplies and adds. The second requires about <i>MNQ<\/i> multiplies and adds, for a total of <i>MN(P + Q)<\/i>.\r\n   <\/p>\r\n   <p>The computational advantage of separable convolution versus nonseparable convolution is therefore:<\/p>\r\n   <p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/78\/separable_filters_eq1821.png\"> <\/p>\r\n   <p>For a 9-by-9 filter kernel, that's a theoretical speed-up of 4.5.<\/p>\r\n   <p>That's enough for now.  <a href=\"https:\/\/blogs.mathworks.com\/steve\/?p=98\">Next time<\/a>, I'll write about how to determine whether a filter kernel is separable, and what MATLAB\r\n      and toolbox functions test automatically for separability.\r\n   <\/p>\r\n\r\n   <script language=\"JavaScript\"> \r\n<!--\r\n    function grabCode_78() {\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='78 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 78';\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_78()\"><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.3<br><\/p>\r\n<\/div>\r\n<!--\r\n78 ##### SOURCE BEGIN #####\r\n%% Separable filters\r\n% The <http:\/\/groups.google.com\/group\/sci.image.processing?hl=en sci.image.processing>\r\n% newsgroup had a <http:\/\/groups.google.com\/group\/sci.image.processing\/browse_thread\/thread\/fc567d195431fd7c\/48f08910b4c3c465?lnk=st&q=&rnum=3&hl=en#48f08910b4c3c465 \r\n% discussion this week> on\r\n% separable filters, which reminded me that separability has been on my\r\n% blog topic ideas list for a while now.\r\n%\r\n%% What is a separable filter?\r\n% A two-dimensional filter kernel is _separable_ if it can be expressed as\r\n% the outer product of two vectors.  For example, let's look at a Sobel\r\n% kernel.\r\n\r\ns = [-1 0 1; -2 0 2; -1 0 1]\r\n\r\n%%\r\n% This kernel can be written as a matrix product of a column and a row\r\n% vector.\r\n\r\nv = [1; 2; 1]\r\n\r\n%%\r\nh = [-1 0 1]\r\n\r\n%%\r\n\r\nv * h\r\n\r\n%% Associativity of convolution\r\n% As it turns out, the matrix product of a column vector and a row vector\r\n% is equivalent to the two-dimensional convolution of the two vectors.\r\n\r\nconv2(v, h)\r\n\r\n%%\r\n% This matters because convolution is associative.  That is,\r\n% \r\n% $$f \\ast (v \\ast h) = (f \\ast v) \\ast h$$\r\n% \r\n% (I've used the asterix here to mean convolution.)  So if a filter _s_ is\r\n% separable:\r\n%\r\n% $$s = v \\ast h$$\r\n%\r\n% then you can filter with _s_ by filtering first with _v_, and then\r\n% filtering the result with _h_.\r\n\r\n%% Computational advantage of separable convolution\r\n% Why would you want to filter this way?  Because you can do it faster.\r\n% Filtering an M-by-N image with a P-by-Q filter kernel requires roughly\r\n% _MNPQ_ multiplies and adds (assuming we aren't using an implementation \r\n% based on the FFT).  If the kernel is separable, you can filter\r\n% in two steps.  The first step requires about _MNP_ multiplies and adds.\r\n% The second requires about _MNQ_ multiplies and adds, for a total of\r\n% _MN(P + Q)_.\r\n%\r\n% The computational advantage of separable convolution versus nonseparable\r\n% convolution is therefore:\r\n%\r\n% $$ PQ\/(P+Q) $$\r\n%\r\n% For a 9-by-9 filter kernel, that's a theoretical speed-up of 4.5.\r\n%\r\n% That's enough for now.  Next time, I'll write about how to determine\r\n% whether a filter kernel is separable, and what MATLAB and toolbox\r\n% functions test automatically for separability.\r\n\r\n##### SOURCE END ##### 78\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      The sci.image.processing newsgroup had a discussion this week on separable filters, which reminded me that separability has been on my blog topic ideas list for a while now.\r\n      \r\n  ... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2006\/10\/04\/separable-convolution\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[248],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/78"}],"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=78"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/78\/revisions"}],"predecessor-version":[{"id":3506,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/78\/revisions\/3506"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}