{"id":1512,"date":"2015-12-14T15:43:12","date_gmt":"2015-12-14T20:43:12","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=1512"},"modified":"2019-11-01T12:14:49","modified_gmt":"2019-11-01T16:14:49","slug":"image-based-graphs","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2015\/12\/14\/image-based-graphs\/","title":{"rendered":"Image-based graphs"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p><a href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/\">Last time<\/a> I showed you the basics of using the new graph theory functionality in MATLAB R2015b. Today I want to talk about <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\">some functions I put on the File Exchange<\/a> for making graphs from images. Those of you working with graph-based image analysis algorithms might find them useful. I would be very interested in receiving feedback on these functions.<\/p><p>The function <tt>imageGraph<\/tt> creates a graph representing the neighbor relationships for every pixel in an image with a specified size. <tt>imageGraph3<\/tt> does the same thing for a 3-D image array.<\/p><p>The function <tt>binaryImageGraph<\/tt> creates a graph representing the neighbor relationships for every foreground pixel in a binary image. <tt>binaryImageGraph3<\/tt> creates a graph from a 3-D binary image array.<\/p><p>The function <tt>plotImageGraph<\/tt> plots a graph created by <tt>imageGraph<\/tt> or <tt>binaryImageGraph<\/tt> with the graph nodes arranged on a pixel grid.<\/p><p>Finally, the function <tt>adjacentRegionGraph<\/tt> creates a graph from a label matrix defining image regions. The graph represents the region adjacency relationships.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#eee5818a-b6ba-4a66-a6c6-79fa430a2952\">Example: Image graph with 8-connected pixels<\/a><\/li><li><a href=\"#1f5d6d2a-c24a-42e5-a25e-67bd7d398dd7\">Example: Image graph with 4-connected pixels<\/a><\/li><li><a href=\"#af29aa1c-a689-4319-9638-d908f8dcea12\">Example: Image graph with special connectivity<\/a><\/li><li><a href=\"#9a4864e1-9474-4d8d-a5b8-022c702d7e6e\">Example: Binary image graph<\/a><\/li><li><a href=\"#a88070f0-07f7-4009-bd2c-d7ab7eec38b5\">Region Graphs<\/a><\/li><li><a href=\"#f62aba62-3993-4e49-9bf4-dc2bc3dbf986\">Example: Region graph<\/a><\/li><\/ul><\/div><h4>Example: Image graph with 8-connected pixels<a name=\"eee5818a-b6ba-4a66-a6c6-79fa430a2952\"><\/a><\/h4><p>Create a graph for a 480-by-640 image with 8-connected pixels.<\/p><pre class=\"codeinput\">g = imageGraph([480 640],8)\r\n<\/pre><pre class=\"codeoutput\">\r\ng = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [1225442x2 table]\r\n    Nodes: [307200x3 table]\r\n\r\n<\/pre><p>Graph nodes contain the x-coordinate, y-coordinate, and linear index of the corresponding image pixels.<\/p><pre class=\"codeinput\">g.Nodes(1:5,:)\r\n<\/pre><pre class=\"codeoutput\">\r\nans = \r\n\r\n    x    y    PixelIndex\r\n    _    _    __________\r\n\r\n    1    1    1         \r\n    1    2    2         \r\n    1    3    3         \r\n    1    4    4         \r\n    1    5    5         \r\n\r\n<\/pre><p>Plot the image graph using <tt>plotImageGraph<\/tt>.<\/p><pre class=\"codeinput\">plotImageGraph(g)\r\naxis([100 110 220 230])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_01.png\" alt=\"\"> <h4>Example: Image graph with 4-connected pixels<a name=\"1f5d6d2a-c24a-42e5-a25e-67bd7d398dd7\"><\/a><\/h4><p>Create a graph for a 480-by-640 image with 4-connected pixels.<\/p><pre class=\"codeinput\">g = imageGraph([480 640],4)\r\n<\/pre><pre class=\"codeoutput\">\r\ng = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [613280x2 table]\r\n    Nodes: [307200x3 table]\r\n\r\n<\/pre><pre class=\"codeinput\">plotImageGraph(g)\r\naxis([100 110 220 230])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_02.png\" alt=\"\"> <h4>Example: Image graph with special connectivity<a name=\"af29aa1c-a689-4319-9638-d908f8dcea12\"><\/a><\/h4><p>Use a 3-by-3 connectivity matrix to create an image graph with 6-connected pixels. Each pixel is connected to its north, northeast, east, south, southwest, and west neighbors.<\/p><pre class=\"codeinput\">conn = [0 1 1; 1 1 1; 1 1 0];\r\ng = imageGraph([480 640],conn);\r\nplotImageGraph(g)\r\naxis([100 110 220 230])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_03.png\" alt=\"\"> <h4>Example: Binary image graph<a name=\"9a4864e1-9474-4d8d-a5b8-022c702d7e6e\"><\/a><\/h4><p>Create a graph whose nodes are the foreground pixels of the binary image text.png (a sample image that is included with the Image Processing Toolbox).<\/p><pre class=\"codeinput\">bw = imread(<span class=\"string\">'text.png'<\/span>);\r\nimshow(bw)\r\ntitle(<span class=\"string\">'Original image'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_04.png\" alt=\"\"> <pre class=\"codeinput\">g = binaryImageGraph(bw);\r\nfigure\r\nplotImageGraph(g)\r\naxis([60 85 30 45])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_05.png\" alt=\"\"> <h4>Region Graphs<a name=\"a88070f0-07f7-4009-bd2c-d7ab7eec38b5\"><\/a><\/h4><p>A label matrix defines a set of regions based on each unique element value in the matrix. For example, suppose you had the following label matrix:<\/p><pre class=\"codeinput\">L = [10 10 3 4.5 4.5; 10 10 3 4.5 4.5; 20 20 3 15 15; 20 20 3 15 15]\r\n<\/pre><pre class=\"codeoutput\">\r\nL =\r\n\r\n   10.0000   10.0000    3.0000    4.5000    4.5000\r\n   10.0000   10.0000    3.0000    4.5000    4.5000\r\n   20.0000   20.0000    3.0000   15.0000   15.0000\r\n   20.0000   20.0000    3.0000   15.0000   15.0000\r\n\r\n<\/pre><p>This label matrix defines 5 regions:<\/p><div><ul><li>A 2-by-2 region in the upper left labeled with the value 10.<\/li><li>A 2-by-2 region in the lower left labeled with the value 20.<\/li><li>A one-pixel-wide vertical region in the middle labeled with the value 3.<\/li><li>A 2-by-2 region in the upper right labeled with the value 4.5.<\/li><li>A 2-by-2 region at the lower right labeled with the value 15.<\/li><\/ul><\/div><p>The function <tt>adjacentRegionsGraph<\/tt> returns a graph with the same number of nodes as labeled regions. Edges in the graph indicate pairs of adjacent regions.<\/p><h4>Example: Region graph<a name=\"f62aba62-3993-4e49-9bf4-dc2bc3dbf986\"><\/a><\/h4><p>Compute an adjacent regions graph. Plot the graph, highlighting the nodes connected to the label 15.<\/p><pre class=\"codeinput\">g = adjacentRegionsGraph(L)\r\n<\/pre><pre class=\"codeoutput\">\r\ng = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [6x2 table]\r\n    Nodes: [5x1 table]\r\n\r\n<\/pre><p>The graph nodes contain the region labels.<\/p><pre class=\"codeinput\">g.Nodes\r\n<\/pre><pre class=\"codeoutput\">\r\nans = \r\n\r\n    Label\r\n    _____\r\n\r\n      3  \r\n    4.5  \r\n     10  \r\n     15  \r\n     20  \r\n\r\n<\/pre><p>The graph edges contain the labels for each adjacent region pair.<\/p><pre class=\"codeinput\">g.Edges\r\n<\/pre><pre class=\"codeoutput\">\r\nans = \r\n\r\n    EndNodes      Labels  \r\n    ________    __________\r\n\r\n    1    2        3    4.5\r\n    1    3        3     10\r\n    1    4        3     15\r\n    1    5        3     20\r\n    2    4      4.5     15\r\n    3    5       10     20\r\n\r\n<\/pre><p>Plot the graph, capturing the GraphPlot object as an output argument.<\/p><pre class=\"codeinput\">gp = plot(g,<span class=\"string\">'NodeLabel'<\/span>,g.Nodes.Label)\r\n<\/pre><pre class=\"codeoutput\">\r\ngp = \r\n\r\n  GraphPlot with properties:\r\n\r\n     NodeColor: [0 0.4470 0.7410]\r\n    MarkerSize: 4\r\n        Marker: 'o'\r\n     EdgeColor: [0 0.4470 0.7410]\r\n     LineWidth: 0.5000\r\n     LineStyle: '-'\r\n     NodeLabel: {'3'  '4.5'  '10'  '15'  '20'}\r\n     EdgeLabel: {}\r\n         XData: [0.0011 0.4051 -1.3642 1.3629 -0.4048]\r\n         YData: [0.0015 1.5564 -0.8540 0.8538 -1.5577]\r\n\r\n  Use GET to show all properties\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_06.png\" alt=\"\"> <p>Find the neighbors of the region labeled 15.<\/p><pre class=\"codeinput\">node_num = find(g.Nodes.Label == 15);\r\nneighbors_15 = neighbors(g,node_num);\r\nhighlight(gp,node_num,neighbors_15)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_07.png\" alt=\"\"> <p>Next time I plan to show you a graph-based maze solver ... that cheats.<\/p><p>I'd love for you try <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\">Image Graphs<\/a>. Please let me know what you think.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_bef91d97324646c3b1e569b499a45596() {\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='bef91d97324646c3b1e569b499a45596 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' bef91d97324646c3b1e569b499a45596';\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        copyright = 'Copyright 2015 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 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');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\">Copyright 2015 The MathWorks, Inc.<br><a href=\"javascript:grabCode_bef91d97324646c3b1e569b499a45596()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2015b<br><\/p><\/div><!--\r\nbef91d97324646c3b1e569b499a45596 ##### SOURCE BEGIN #####\r\n%% \r\n% <https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/ Last\r\n% time> I showed you the basics of using the new graph theory functionality\r\n% in MATLAB R2015b. Today I want to talk about\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\r\n% some functions I put on the File Exchange> for making graphs from images.\r\n% Those of you working with graph-based image analysis algorithms might find\r\n% them useful. I would be very interested in receiving feedback on these\r\n% functions.\r\n%\r\n% The function |imageGraph| creates a graph\r\n% representing the neighbor relationships for every pixel in an\r\n% image with a specified size. |imageGraph3| does the same thing for\r\n% a 3-D image array.\r\n%\r\n% The function |binaryImageGraph| creates a\r\n% graph representing the neighbor relationships for every foreground\r\n% pixel in a binary image. |binaryImageGraph3| creates a graph from\r\n% a 3-D binary image array.\r\n%\r\n% The function |plotImageGraph| plots a graph\r\n% created by |imageGraph| or |binaryImageGraph| with the graph nodes\r\n% arranged on a pixel grid.\r\n%\r\n% Finally, the function |adjacentRegionGraph| creates\r\n% a graph from a label matrix defining image regions. The graph\r\n% represents the region adjacency relationships.\r\n%\r\n%% Example: Image graph with 8-connected pixels\r\n%\r\n% Create a graph for a 480-by-640 image with 8-connected pixels.\r\n\r\ng = imageGraph([480 640],8)\r\n\r\n%%\r\n% Graph nodes contain the x-coordinate, y-coordinate, and linear\r\n% index of the corresponding image pixels.\r\n\r\ng.Nodes(1:5,:)\r\n\r\n%%\r\n% Plot the image graph using |plotImageGraph|.\r\n\r\nplotImageGraph(g)\r\naxis([100 110 220 230])\r\n\r\n%% Example: Image graph with 4-connected pixels\r\n%\r\n% Create a graph for a 480-by-640 image with 4-connected pixels.\r\n\r\ng = imageGraph([480 640],4)\r\n\r\n%%\r\n\r\nplotImageGraph(g)\r\naxis([100 110 220 230])\r\n\r\n%% Example: Image graph with special connectivity\r\n%\r\n% Use a 3-by-3 connectivity matrix to create an image graph with\r\n% 6-connected pixels. Each pixel is connected to its north,\r\n% northeast, east, south, southwest, and west neighbors.\r\n\r\nconn = [0 1 1; 1 1 1; 1 1 0];\r\ng = imageGraph([480 640],conn);\r\nplotImageGraph(g)\r\naxis([100 110 220 230])\r\n\r\n%% Example: Binary image graph\r\n%\r\n% Create a graph whose nodes are the foreground pixels of the binary\r\n% image text.png (a sample image that is included with the Image\r\n% Processing Toolbox).\r\n\r\nbw = imread('text.png');\r\nimshow(bw)\r\ntitle('Original image')\r\n\r\n%%\r\ng = binaryImageGraph(bw);\r\nfigure\r\nplotImageGraph(g)\r\naxis([60 85 30 45])\r\n\r\n%% Region Graphs\r\n% A label matrix defines a set of regions based on each unique\r\n% element value in the matrix. For example, suppose you had the\r\n% following label matrix:\r\n\r\nL = [10 10 3 4.5 4.5; 10 10 3 4.5 4.5; 20 20 3 15 15; 20 20 3 15 15]\r\n\r\n%%\r\n% This label matrix defines 5 regions:\r\n%\r\n% * A 2-by-2 region in the upper left labeled with the value 10. \r\n% * A 2-by-2 region in the lower left labeled with the value 20.\r\n% * A one-pixel-wide vertical region in the middle labeled with the\r\n% value 3.\r\n% * A 2-by-2 region in the upper right labeled with the value 4.5.\r\n% * A 2-by-2 region at the lower right labeled with the value 15.\r\n%\r\n% The function |adjacentRegionsGraph| returns a graph with the same\r\n% number of nodes as labeled regions. Edges in the graph indicate\r\n% pairs of adjacent regions.\r\n%\r\n%% Example: Region graph\r\n%\r\n% Compute an adjacent regions graph. Plot the graph, highlighting\r\n% the nodes connected to the label 15.\r\n\r\ng = adjacentRegionsGraph(L)\r\n\r\n%%\r\n% The graph nodes contain the region labels.\r\n\r\ng.Nodes\r\n\r\n%%\r\n% The graph edges contain the labels for each adjacent region pair.\r\n\r\ng.Edges\r\n\r\n%%\r\n% Plot the graph, capturing the GraphPlot object as an output\r\n% argument.\r\n\r\ngp = plot(g,'NodeLabel',g.Nodes.Label)\r\n\r\n%%\r\n% Find the neighbors of the region labeled 15.\r\n\r\nnode_num = find(g.Nodes.Label == 15);\r\nneighbors_15 = neighbors(g,node_num);\r\nhighlight(gp,node_num,neighbors_15)\r\n\r\n%%\r\n% Next time I plan to show you a graph-based maze solver ... that cheats.\r\n%\r\n% I'd love for you try\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\r\n% Image Graphs>. Please let me know what you think.\r\n\r\n% Copyright 2015 The MathWorks, Inc.\r\n##### SOURCE END ##### bef91d97324646c3b1e569b499a45596\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_basic_05.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p><a href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/\">Last time<\/a> I showed you the basics of using the new graph theory functionality in MATLAB R2015b. Today I want to talk about <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\">some functions I put on the File Exchange<\/a> for making graphs from images. Those of you working with graph-based image analysis algorithms might find them useful. I would be very interested in receiving feedback on these functions.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/12\/14\/image-based-graphs\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":1509,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[50,725,348,1135,76,36,1145,68,52],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1512"}],"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=1512"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1512\/revisions"}],"predecessor-version":[{"id":1513,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1512\/revisions\/1513"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media\/1509"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=1512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=1512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=1512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}