{"id":9002,"date":"2017-12-07T16:10:33","date_gmt":"2017-12-07T21:10:33","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=9002"},"modified":"2017-12-08T09:04:31","modified_gmt":"2017-12-08T14:04:31","slug":"minimizing-energy-to-segment-images-or-cluster-data","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2017\/12\/07\/minimizing-energy-to-segment-images-or-cluster-data\/","title":{"rendered":"Minimizing energy to segment images, or cluster data"},"content":{"rendered":"<div class=\"content\"><!--introduction--><!--\/introduction--><\/p>\n<p><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/911\">Brett<\/a>&#8216;s Pick this week is <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/62641-pottslab-multilabel-segmentation-of-vectorial-data\">Pottslab &#8211; Multilabel segmentation of vectorial data<\/a>, by <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/profile\/authors\/4780621-martin\">Martin<\/a>.<\/p>\n<p>Segmenting images and clustering data are very common challenges, for which MATLAB (and MathWorks Toolboxes) provide numerous solutions. Martin&#8217;s Potts-energy-based approach works beautifully for some difficult cases. Consider the &#8216;lighthouse.png&#8217; image that ships with the <a href=\"https:\/\/www.mathworks.com\/products\/image.html\">Image Processing Toolbox<\/a>:<\/p>\n<p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse1.png\" alt=\"\"> <\/p>\n<p>If we wanted to &#8220;cluster&#8221; the colors of this images, we could:<\/p>\n<div>\n<ul>\n<li>Simply specify the number of clusters, and use <tt>rgb2ind()<\/tt>:<\/li>\n<\/ul>\n<\/div>\n<pre>nClusters = 9;\r\n[X,map] = rgb2ind(img,nClusters,'nodither');\r\nimshow(X,map)<\/pre>\n<p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse2.png\" alt=\"\"> <\/p>\n<div>\n<ul>\n<li>Actually do some statistical (e.g., k-means) clustering:<\/li>\n<\/ul>\n<\/div>\n<pre>rc = img(:,:,1);\r\ngc = img(:,:,2);\r\nbc = img(:,:,3);\r\nsegcolors = double([rc(:) gc(:) bc(:)]);\r\nIdx = kmeans(segcolors,nClusters,...\r\n\t'distance','sqEuclidean',...\r\n\t'start',map,...\r\n\t'emptyaction','singleton');\r\nclusteredImg = reshape(Idx,size(rc));\r\nimshow(clusteredImg,map)<\/pre>\n<p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse3.png\" alt=\"\"> <\/p>\n<div>\n<ul>\n<li>Use an energy-minimation approach like the one Martin provided:<\/li>\n<\/ul>\n<\/div>\n<pre>img = imresize(img, 0.5);\r\ngamma = 0.15;\r\nPottsImage = minL2Potts2DADMM(img, gamma, 'verbose', true);\r\nenergyU = energyL2Potts(PottsImage, img, gamma);\r\nenergyImg = energyL2Potts(img, img, gamma);\r\nimshow(PottsImage)\r\ntitle(sprintf('Potts segmentation (Potts energy: %.1f)', energyU));<\/pre>\n<p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse4.png\" alt=\"\"> <\/p>\n<p>In some regards, the Potts-energy approach provides superior results. And I didn&#8217;t have to specify the number of cluster <i>a priori<\/i> . Some observations, though:<\/p>\n<div>\n<ul>\n<li>I didn&#8217;t show it, but the &#8220;Potts energy&#8221; of the original (resized) image was about an order of magnitude higher than the energy of the clustered image.<\/li>\n<li>You&#8217;ll notice the call to <tt>imresize<\/tt> before I called the Potts functionality. This method is extremely memory intensive, and runs out of memory on my computer when I try to operate on the full-size original image, even though it&#8217;s pretty small (640 x 480 x 3). (You might have good success upsampling [with <tt>imresize<\/tt>] the PottsImage to align the clustering [and segmentations based thereon] to the original image. But this can also introduce &#8220;noise,&#8221; and extra computational expense, to the problem.)<\/li>\n<li>The Potts approach is relatively very slow, even on the smaller images. The <tt>rgb2ind<\/tt> computation took 17 msec on my laptop. The kmeans approach took 1.2 seconds. The Potts-energy approach took 3.3 seconds, including the necessary resizing.<\/li>\n<\/ul>\n<\/div>\n<p>Still, options are always good, and I&#8217;m very impressed with the quality of the Potts clustering. (Notice the quality of the roof segmentation, for instance.)<\/p>\n<p>Martin&#8217;s code is quite extensive, well-implemented (in object-oriented code), and documented. It is also much more flexible than I&#8217;ve demonstrated here. My focus is typically on image analysis, but the Potts-energy minimization can be applied to signal based operations, too, like denoising:<\/p>\n<p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/laplacianNoise.png\" alt=\"\"> <\/p>\n<p>Thanks, Martin, for sharing this very interesting and useful functionality!<\/p>\n<p>As always, I welcome your <a href=\"https:\/\/blogs.mathworks.com\/pick\/?p=9002#respond\">thoughts and comments<\/a>.<\/p>\n<p><script language=\"JavaScript\"> <!-- \n    function grabCode_3092e17fbb954bd4b9987a88397e1193() {\n        \/\/ Remember the title so we can use it in the new page\n        title = document.title;\n\n        \/\/ Break up these strings so that their presence\n        \/\/ in the Javascript doesn't mess up the search for\n        \/\/ the MATLAB code.\n        t1='3092e17fbb954bd4b9987a88397e1193 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 3092e17fbb954bd4b9987a88397e1193';\n    \n        b=document.getElementsByTagName('body')[0];\n        i1=b.innerHTML.indexOf(t1)+t1.length;\n        i2=b.innerHTML.indexOf(t2);\n \n        code_string = b.innerHTML.substring(i1, i2);\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\n\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \n        \/\/ in the XML parser.\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\n        \/\/ doesn't go ahead and substitute the less-than character. \n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\n\n        copyright = 'Copyright 2017 The MathWorks, Inc.';\n\n        w = window.open();\n        d = w.document;\n        d.write('\n\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\n\n\\n');\n\n        d.title = title + ' (MATLAB code)';\n        d.close();\n    }   \n     --> <\/script><\/p>\n<p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><a href=\"javascript:grabCode_3092e17fbb954bd4b9987a88397e1193()\"><span style=\"font-size: x-small;        font-style: italic;\">Get<br \/>\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><\/p>\n<p>      Published with MATLAB&reg; R2017b<\/p>\n<\/div>\n<p><!--\n3092e17fbb954bd4b9987a88397e1193 ##### SOURCE BEGIN #####\n%% Minimizing energy to segment images, or cluster data\n%% \n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/911 Brett>'s Pick this week\n% is\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/62641-pottslab-multilabel-segmentation-of-vectorial-data Pottslab - Multilabel segmentation of vectorial data>,\n% by <https:\/\/www.mathworks.com\/matlabcentral\/profile\/authors\/4780621-martin Martin>.\n%\n% Segmenting images and clustering data are very common challenges, for which MATLAB (and MathWorks Toolboxes) provide\n% numerous solutions. Martin's Potts-energy-based approach works beautifully for some difficult cases.\n% Consider the 'lighthouse.png' image that ships with the <https:\/\/www.mathworks.com\/products\/image.html Image Processing Toolbox>:\n%%\n% \n% <<https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse1.png>>\n% \n% If we wanted to \"cluster\" the colors of this images, we could:\n%\n% \n% * Simply specify the number of clusters, and use |rgb2ind()|:\n%%\n% \n%  nClusters = 9;\n%  [X,map] = rgb2ind(img,nClusters,'nodither');\n%  imshow(X,map)\n% \n%%\n% \n% <<https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse2.png>>\n% \n% * Actually do some statistical (e.g., k-means) clustering:\n%%\n% \n%  rc = img(:,:,1);\n%  gc = img(:,:,2);\n%  bc = img(:,:,3);\n%  segcolors = double([rc(:) gc(:) bc(:)]);\n%  Idx = kmeans(segcolors,nClusters,...\n%  \t'distance','sqEuclidean',...\n%  \t'start',map,...\n%  \t'emptyaction','singleton');\n%  clusteredImg = reshape(Idx,size(rc));\n%  imshow(clusteredImg,map)\n% \n%%\n% \n% <<https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse3.png>>\n% \n% * Use an energy-minimation approach like the one Martin provided:\n%%\n% \n%  img = imresize(img, 0.5);\n%  gamma = 0.15;\n%  PottsImage = minL2Potts2DADMM(img, gamma, 'verbose', true);\n%  energyU = energyL2Potts(PottsImage, img, gamma);\n%  energyImg = energyL2Potts(img, img, gamma);\n%  imshow(PottsImage)\n%  title(sprintf('Potts segmentation (Potts energy: %.1f)', energyU));\n%%\n% \n% <<https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse4.png>>\n% \n%% \n% In some regards, the Potts-energy approach provides superior\n% results. And I didn't have to specify the number of cluster _a priori_ . \n% Some observations, though:\n%%\n% \n% * I didn't show it, but the \"Potts energy\" of the original (resized)\n% image was about an order of magnitude higher than the energy of the\n% clustered image.\n% * You'll notice the call to |imresize| before I called the Potts\n% functionality. This method is extremely memory intensive, and runs\n% out of memory on my computer when I try to operate on the full-size\n% original image, even though it's pretty small (640 x 480 x 3). (You\n% might have good success upsampling [with |imresize|] the PottsImage\n% to align the clustering [and segmentations based thereon] to the\n% original image. But this can also introduce \"noise,\" and extra\n% computational expense, to the problem.)\n% * The Potts approach is relatively very slow, even on the smaller\n% images. The |rgb2ind| computation took 17 msec on my laptop. The\n% kmeans approach took 1.2 seconds. The Potts-energy approach took 3.3\n% seconds, including the necessary resizing.\n\n%%\n% Still, options are always good, and I'm very impressed with the\n% quality of the Potts clustering. (Notice the quality of the roof\n% segmentation, for instance.) \n%%\n% Martin's code is quite extensive, well-implemented (in\n% object-oriented code), and documented. It is also much more flexible\n% than I've demonstrated here. My focus is typically on image\n% analysis, but the Potts-energy minimization can be applied to signal\n% based operations, too, like denoising:\n%%\n% \n% <<https:\/\/blogs.mathworks.com\/pick\/files\/laplacianNoise.png>>\n% \n% \n%% \n% Thanks, Martin, for sharing this very interesting and useful functionality!\n%%\n% As always, I welcome your\n% <https:\/\/blogs.mathworks.com\/pick\/?p=9002#respond thoughts and comments>.\n##### SOURCE END ##### 3092e17fbb954bd4b9987a88397e1193\n--><\/p>\n","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/pick\/files\/lighthouse1.png\" onError=\"this.style.display ='none';\" \/><\/div>\n<p>\nBrett&#8216;s Pick this week is Pottslab &#8211; Multilabel segmentation of vectorial data, by Martin.<br \/>\nSegmenting images and clustering data are very common challenges, for which MATLAB (and&#8230; <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/pick\/2017\/12\/07\/minimizing-energy-to-segment-images-or-cluster-data\/\">read more >><\/a><\/p>\n","protected":false},"author":34,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/9002"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/comments?post=9002"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/9002\/revisions"}],"predecessor-version":[{"id":9022,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/9002\/revisions\/9022"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/media?parent=9002"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/categories?post=9002"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/tags?post=9002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}