{"id":2826,"date":"2018-03-16T12:19:48","date_gmt":"2018-03-16T16:19:48","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2826"},"modified":"2019-11-01T19:53:17","modified_gmt":"2019-11-01T23:53:17","slug":"what-is-the-shape-of-a-pixel","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2018\/03\/16\/what-is-the-shape-of-a-pixel\/","title":{"rendered":"What is the Shape of a Pixel?"},"content":{"rendered":"<div class=\"content\"><h3>Contents<\/h3><div><ul><li><a href=\"#ec364fc4-9f08-4a9b-b5a2-ce9f44fd7fdb\">The Shape of a Pixel<\/a><\/li><li><a href=\"#341ed497-1b23-4ef6-95a9-d346ad7c504a\">Weaknesses of Using the Pixel Centers<\/a><\/li><li><a href=\"#756547b1-ac64-4f76-acfb-646bdcc0a149\">Square Pixels<\/a><\/li><li><a href=\"#27191473-0165-46fd-a8a4-272a6d026587\">Diamond Pixels<\/a><\/li><li><a href=\"#6aa744d5-c2ae-491f-bf76-d255833e97bb\">Circular Pixels<\/a><\/li><\/ul><\/div><h4>The Shape of a Pixel<a name=\"ec364fc4-9f08-4a9b-b5a2-ce9f44fd7fdb\"><\/a><\/h4><p>What is the shape of a pixel? At various times, I have a pixel as a square (often), a point (sometimes), or a rectangle (occasionally). I recall back in grad school doing some homework where we were treating pixels as hexagons.<\/p><p>As I haved worked through the last few posts on computing Feret diameters, though, I have started to entertain the possible usefulness of considering pixels to be circles. (See <a href=\"https:\/\/blogs.mathworks.com\/steve\/2017\/09\/29\/feret-diameter-introduction\/\">29-Sep-2017<\/a>, <a href=\"https:\/\/blogs.mathworks.com\/steve\/2017\/10\/24\/feret-diameters-and-antipodal-vertices\/\">24-Oct-2017<\/a>, and <a href=\"https:\/\/blogs.mathworks.com\/steve\/2018\/02\/20\/minimum-feret-diameter\/\">20-Feb-2018<\/a>.) Let me try to explain why.<\/p><p>Here's a binary image with a single foreground blob (or \"object,\" or \"connected component.\")<\/p><pre class=\"codeinput\">bw = imread(<span class=\"string\">'Martha''s Vineyard (30x20).png'<\/span>);\r\nimshow(bw)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_01.png\" alt=\"\"> <p>Most of the time, we think of image pixels as being squares with unit area.<\/p><pre class=\"codeinput\">pixelgrid\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_02.png\" alt=\"\"> <p>We can use <tt>find<\/tt> to get the $x$- and $y$-coordinates of the pixel centers, and then we can use <tt>convhull<\/tt> to find their convex hull. As an optimization that I think will often reduce execution time and memory, I'm going to preprocess the input binary image here by calling <tt>bwperim<\/tt>. I'm not going to show that step everywhere in this example, though.<\/p><pre class=\"codeinput\">[y,x] = find(bwperim(bw));\r\nhold <span class=\"string\">on<\/span>\r\nplot(x,y,<span class=\"string\">'.'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Pixel centers'<\/span>)\r\nh = convhull(x,y);\r\nx_hull = x(h);\r\ny_hull = y(h);\r\nhold <span class=\"string\">on<\/span>\r\nhull_line = plot(x_hull,y_hull,<span class=\"string\">'r*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12);\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Pixel centers and convex hull vertices'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_03.png\" alt=\"\"> <p>Notice that there are some chains of three or more colinear convex hull vertices.<\/p><pre class=\"codeinput\">xlim([21.5 32.5])\r\nylim([9.5 15.5])\r\ntitle(<span class=\"string\">'Colinear convex hull vertices'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_04.png\" alt=\"\"> <p>In some of the other processing steps related to Feret diameter measurements, colinear convex hull vertices can cause problems. We can eliminate these vertices directly in the call to <tt>convhull<\/tt> using the <tt>'Simplify'<\/tt> parameter.<\/p><pre class=\"codeinput\">h = convhull(x,y,<span class=\"string\">'Simplify'<\/span>,true);\r\nx_hull = x(h);\r\ny_hull = y(h);\r\ndelete(hull_line);\r\nhold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Colinear hull vertices removed'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_05.png\" alt=\"\"> <pre class=\"codeinput\">imshow(bw)\r\nhold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'LineWidth'<\/span>,2,<span class=\"string\">'MarkerSize'<\/span>,12)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'A Blob''s Convex Hull and Its Vertices'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_06.png\" alt=\"\"> <p>Notice, though, that there are white bits showing outside the red convex hull polygon. That's because we are only using the <b>pixel centers<\/b>.<\/p><h4>Weaknesses of Using the Pixel Centers<a name=\"341ed497-1b23-4ef6-95a9-d346ad7c504a\"><\/a><\/h4><p>Consider a simpler binary object, one that has only one row.<\/p><pre class=\"codeinput\">bw2 = false(5,15);\r\nbw2(3,5:10) = true;\r\nimshow(bw2)\r\npixelgrid\r\n[y,x] = find(bw2);\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_07.png\" alt=\"\"> <p>The function <tt>convhull<\/tt> doesn't even work on colinear points.<\/p><pre class=\"codeinput\"><span class=\"keyword\">try<\/span>\r\n    hull = convhull(x,y,<span class=\"string\">'Simplify'<\/span>,true);\r\n<span class=\"keyword\">catch<\/span> e\r\n    fprintf(<span class=\"string\">'Error message from convhull: \"%s\"\\n'<\/span>, e.message);\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><pre class=\"codeoutput\">Error message from convhull: \"Error computing the convex hull. The points may be collinear.\"\r\n<\/pre><p>But even if it did return an answer, the answer would be a degenerate polygon with length 5 (even though the number of foreground pixels is 6) and zero area.<\/p><pre class=\"codeinput\">hold <span class=\"string\">on<\/span>\r\nplot(x,y,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12,<span class=\"string\">'LineWidth'<\/span>,2)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Degenerate convex hull polygon'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_08.png\" alt=\"\"> <p>We can solve this degeneracy problem by using <b>square pixels<\/b>.<\/p><h4>Square Pixels<a name=\"756547b1-ac64-4f76-acfb-646bdcc0a149\"><\/a><\/h4><p>In the computation of the convex hull above, we treated each pixel as a <b>point<\/b>. We can, instead, treat each pixel as a <b>square<\/b> by computing the convex hull of all the <b>corners<\/b> of every pixel. Here's one way to perform that computation.<\/p><pre class=\"codeinput\">offsets = [ <span class=\"keyword\">...<\/span>\r\n     0.5  -0.5\r\n     0.5   0.5\r\n    -0.5  -0.5\r\n    -0.5   0.5 ]';\r\n\r\noffsets = reshape(offsets,1,2,[]);\r\n\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,<span class=\"string\">'Simplify'<\/span>,true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n<\/pre><pre class=\"codeinput\">imshow(bw2)\r\npixelgrid\r\nhold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12,<span class=\"string\">'LineWidth'<\/span>,2)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Convex hull of square pixels'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_09.png\" alt=\"\"> <p>This result looks good at first glance. However, it loses some of its appeal when you consider the implications for computing the maximum Feret diameter.<\/p><pre class=\"codeinput\">points = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nhold <span class=\"string\">on<\/span>\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'k'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'The maximum Feret diameter is not horizontal'<\/span>)\r\n<\/pre><pre class=\"codeoutput\">\r\nd =\r\n\r\n    6.0828\r\n\r\n\r\nend_points =\r\n\r\n   10.5000    2.5000\r\n    4.5000    3.5000\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_10.png\" alt=\"\"> <p>The maximum Feret distance of this horizontal segment of is 6.0828 ($\\sqrt{37}$) instead of 6, and the corresponding orientation in degrees is:<\/p><pre class=\"codeinput\">atan2d(1,6)\r\n<\/pre><pre class=\"codeoutput\">\r\nans =\r\n\r\n    9.4623\r\n\r\n<\/pre><p>instead of 0.<\/p><p>Another worthy attempt is to use <b>diamond<\/b> pixels.<\/p><h4>Diamond Pixels<a name=\"27191473-0165-46fd-a8a4-272a6d026587\"><\/a><\/h4><p>Instead of using the four corners of each pixel, let's try using the middle of each pixel edge. Once we define the offsets, the code is exactly the same as for square pixels.<\/p><pre class=\"codeinput\">offsets = [ <span class=\"keyword\">...<\/span>\r\n     0.5   0.0\r\n     0.0   0.5\r\n    -0.5   0.0\r\n     0.0  -0.5 ]';\r\n\r\noffsets = reshape(offsets,1,2,[]);\r\n\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,<span class=\"string\">'Simplify'<\/span>,true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n<\/pre><pre class=\"codeinput\">imshow(bw2)\r\npixelgrid\r\nhold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12,<span class=\"string\">'LineWidth'<\/span>,2)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'Convex hull of diamond pixels'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_11.png\" alt=\"\"> <p>Now the max Feret diameter result looks better for the horizontal row of pixels.<\/p><pre class=\"codeinput\">points = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nhold <span class=\"string\">on<\/span>\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'k'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nd =\r\n\r\n     6\r\n\r\n\r\nend_points =\r\n\r\n   10.5000    3.0000\r\n    4.5000    3.0000\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_12.png\" alt=\"\"> <p>Hold on, though. Consider a square blob.<\/p><pre class=\"codeinput\">bw3 = false(9,9);\r\nbw3(3:7,3:7) = true;\r\nimshow(bw3)\r\npixelgrid\r\n[y,x] = find(bw3);\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,<span class=\"string\">'Simplify'<\/span>,true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_13.png\" alt=\"\"> <pre class=\"codeinput\">hold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12,<span class=\"string\">'LineWidth'<\/span>,2)\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'k'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\nhold <span class=\"string\">off<\/span>\r\ntitle(<span class=\"string\">'The max Feret diameter is not at 45 degrees'<\/span>)\r\n<\/pre><pre class=\"codeoutput\">\r\nd =\r\n\r\n    6.4031\r\n\r\n\r\nend_points =\r\n\r\n    7.5000    3.0000\r\n    2.5000    7.0000\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_14.png\" alt=\"\"> <p>We'd like to see the max Feret diameter oriented at 45 degrees, and clearly we don't.<\/p><h4>Circular Pixels<a name=\"6aa744d5-c2ae-491f-bf76-d255833e97bb\"><\/a><\/h4><p>OK, I'm going to make one more attempt. I'm going to treat each pixel as <b>approximately<\/b> a <b>circle<\/b>. I'm going to approximate a circle using 24 points that are spaced at 15-degree intervals along the circumference.<\/p><pre class=\"codeinput\">thetad = 0:15:345;\r\noffsets = 0.5*[cosd(thetad) ; sind(thetad)];\r\noffsets = reshape(offsets,1,2,[]);\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,<span class=\"string\">'Simplify'<\/span>,true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n\r\nimshow(bw3)\r\npixelgrid\r\nhold <span class=\"string\">on<\/span>\r\nplot(x_hull,y_hull,<span class=\"string\">'r-*'<\/span>,<span class=\"string\">'MarkerSize'<\/span>,12,<span class=\"string\">'LineWidth'<\/span>,2)\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'k'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\naxis <span class=\"string\">on<\/span>\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nd =\r\n\r\n    6.6569\r\n\r\n\r\nend_points =\r\n\r\n    7.3536    7.3536\r\n    2.6464    2.6464\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_15.png\" alt=\"\"> <p>Now the max Feret diameter orientation is what we would naturally expect, which is $\\pm 45^{\\circ}$. The orientation would also be as expected for a horizontal or vertical segment of pixels.<\/p><p>Still, a circular approximation might not always give exactly what a user might expect. Let's go back to the Martha's Vinyard blob that I started with. I wrote a function called <tt>pixelHull<\/tt> that can compute the convex hull of binary image pixels in a variety of different ways. The call <tt>pixelHull(bw,24)<\/tt> computes the pixel hull using a 24-point circle approximation.<\/p><p>Here's the maximum Feret diameter using that approximation.<\/p><pre class=\"codeinput\">imshow(bw)\r\nV = pixelHull(bw,24);\r\nhold <span class=\"string\">on<\/span>\r\nplot(V(:,1),V(:,2),<span class=\"string\">'r-'<\/span>,<span class=\"string\">'LineWidth'<\/span>,2,<span class=\"string\">'MarkerSize'<\/span>,12)\r\n[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'m'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\naxis <span class=\"string\">on<\/span>\r\npixelgrid\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_16.png\" alt=\"\"> <p>I think many people might expect the maximum Feret diameter to go corner-to-corner in this case, but it doesn't exactly do that.<\/p><pre class=\"codeinput\">xlim([22.07 31.92])\r\nylim([8.63 15.20])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_17.png\" alt=\"\"> <p>You have to use square pixels to get corner-to-corner.<\/p><pre class=\"codeinput\">imshow(bw)\r\nV = pixelHull(bw,<span class=\"string\">'square'<\/span>);\r\nhold <span class=\"string\">on<\/span>\r\nplot(V(:,1),V(:,2),<span class=\"string\">'r-'<\/span>,<span class=\"string\">'LineWidth'<\/span>,2,<span class=\"string\">'MarkerSize'<\/span>,12)\r\n[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));\r\nplot(end_points(:,1),end_points(:,2),<span class=\"string\">'m'<\/span>,<span class=\"string\">'LineWidth'<\/span>,3)\r\naxis <span class=\"string\">on<\/span>\r\npixelgrid\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_18.png\" alt=\"\"> <pre class=\"codeinput\">xlim([22.07 31.92])\r\nylim([8.63 15.20])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_19.png\" alt=\"\"> <p>After all this, I'm still not completely certain which shape assumption will generally work best. My only firm conclusion is that the point approximation is the worst choice. The degeneracies associated with point pixels are just too troublesome.<\/p><p>If you have an opinion, please share it in the comments. (Note: A comment that says, \"Steve, you're totally overthinking this\" would be totally legit.)<\/p><p><i>The rest of the post contains functions used by the code above.<\/i><\/p><pre class=\"codeinput\"><span class=\"keyword\">function<\/span> V = pixelHull(P,type)\r\n\r\n<span class=\"keyword\">if<\/span> nargin &lt; 2\r\n    type = 24;\r\n<span class=\"keyword\">end<\/span>\r\n\r\n<span class=\"keyword\">if<\/span> islogical(P)\r\n    P = bwperim(P);\r\n    [i,j] = find(P);\r\n    P = [j i];\r\n<span class=\"keyword\">end<\/span>\r\n\r\n<span class=\"keyword\">if<\/span> strcmp(type,<span class=\"string\">'square'<\/span>)\r\n    offsets = [ <span class=\"keyword\">...<\/span>\r\n         0.5  -0.5\r\n         0.5   0.5\r\n        -0.5   0.5\r\n        -0.5  -0.5 ];\r\n\r\n<span class=\"keyword\">elseif<\/span> strcmp(type,<span class=\"string\">'diamond'<\/span>)\r\n    offsets = [ <span class=\"keyword\">...<\/span>\r\n         0.5  0\r\n         0    0.5\r\n        -0.5  0\r\n         0   -0.5 ];\r\n\r\n<span class=\"keyword\">else<\/span>\r\n    <span class=\"comment\">% type is number of angles for sampling a circle of diameter 1.<\/span>\r\n    thetad = linspace(0,360,type+1)';\r\n    thetad(end) = [];\r\n\r\n    offsets = 0.5*[cosd(thetad) sind(thetad)];\r\n<span class=\"keyword\">end<\/span>\r\n\r\noffsets = offsets';\r\noffsets = reshape(offsets,1,2,[]);\r\n\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nk = convhull(S,<span class=\"string\">'Simplify'<\/span>,true);\r\nV = S(k,:);\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_f024816cb729487aaace442476b0b27b() {\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='f024816cb729487aaace442476b0b27b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' f024816cb729487aaace442476b0b27b';\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 2018 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\"><br><a href=\"javascript:grabCode_f024816cb729487aaace442476b0b27b()\"><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; R2017b<br><\/p><\/div><!--\r\nf024816cb729487aaace442476b0b27b ##### SOURCE BEGIN #####\r\n%% The Shape of a Pixel\r\n% What is the shape of a pixel? At various times, I have a pixel as a square \r\n% (often), a point (sometimes), or a rectangle (occasionally). I recall back in \r\n% grad school doing some homework where we were treating pixels as hexagons.\r\n% \r\n% As I haved worked through the last few posts on computing Feret diameters, \r\n% though, I have started to entertain the possible usefulness of considering pixels \r\n% to be circles. (See <https:\/\/blogs.mathworks.com\/steve\/2017\/09\/29\/feret-diameter-introduction\/ \r\n% 29-Sep-2017>, <https:\/\/blogs.mathworks.com\/steve\/2017\/10\/24\/feret-diameters-and-antipodal-vertices\/ \r\n% 24-Oct-2017>, and <https:\/\/blogs.mathworks.com\/steve\/2018\/02\/20\/minimum-feret-diameter\/ \r\n% 20-Feb-2018>.) Let me try to explain why.\r\n% \r\n% Here's a binary image with a single foreground blob (or \"object,\" or \"connected \r\n% component.\")\r\n\r\nbw = imread('Martha''s Vineyard (30x20).png');\r\nimshow(bw)\r\n%% \r\n% Most of the time, we think of image pixels as being squares with unit \r\n% area.\r\n%%\r\npixelgrid\r\n%% \r\n% We can use |find| to get the $x$- and $y$-coordinates of the pixel centers, \r\n% and then we can use |convhull| to find their convex hull. As an optimization \r\n% that I think will often reduce execution time and memory, I'm going to preprocess \r\n% the input binary image here by calling |bwperim|. I'm not going to show that \r\n% step everywhere in this example, though.\r\n%%\r\n[y,x] = find(bwperim(bw));\r\nhold on\r\nplot(x,y,'.')\r\nhold off\r\ntitle('Pixel centers')\r\nh = convhull(x,y);\r\nx_hull = x(h);\r\ny_hull = y(h);\r\nhold on\r\nhull_line = plot(x_hull,y_hull,'r*','MarkerSize',12);\r\nhold off\r\ntitle('Pixel centers and convex hull vertices')\r\n%% \r\n% Notice that there are some chains of three or more colinear convex hull \r\n% vertices.\r\n%%\r\nxlim([21.5 32.5])\r\nylim([9.5 15.5])\r\ntitle('Colinear convex hull vertices')\r\n%% \r\n% In some of the other processing steps related to Feret diameter measurements, \r\n% colinear convex hull vertices can cause problems. We can eliminate these vertices \r\n% directly in the call to |convhull| using the |'Simplify'| parameter.\r\n%%\r\nh = convhull(x,y,'Simplify',true);\r\nx_hull = x(h);\r\ny_hull = y(h);\r\ndelete(hull_line);\r\nhold on\r\nplot(x_hull,y_hull,'r*','MarkerSize',12)\r\nhold off\r\ntitle('Colinear hull vertices removed')\r\n%%\r\nimshow(bw)\r\nhold on\r\nplot(x_hull,y_hull,'r-*','LineWidth',2,'MarkerSize',12)\r\nhold off\r\ntitle('A Blob''s Convex Hull and Its Vertices')\r\n%% \r\n% Notice, though, that there are white bits showing outside the red convex \r\n% hull polygon. That's because we are only using the *pixel centers*.\r\n%% Weaknesses of Using the Pixel Centers\r\n% Consider a simpler binary object, one that has only one row.\r\n%%\r\nbw2 = false(5,15);\r\nbw2(3,5:10) = true;\r\nimshow(bw2)\r\npixelgrid\r\n[y,x] = find(bw2);\r\n%% \r\n% The function |convhull| doesn't even work on colinear points.\r\n\r\ntry\r\n    hull = convhull(x,y,'Simplify',true);\r\ncatch e\r\n    fprintf('Error message from convhull: \"%s\"\\n', e.message);\r\nend\r\n%% \r\n% But even if it did return an answer, the answer would be a degenerate \r\n% polygon with length 5 (even though the number of foreground pixels is 6) and \r\n% zero area.\r\n\r\nhold on\r\nplot(x,y,'r-*','MarkerSize',12,'LineWidth',2)\r\nhold off\r\ntitle('Degenerate convex hull polygon')\r\n%% \r\n% We can solve this degeneracy problem by using *square pixels*.\r\n%% Square Pixels\r\n% In the computation of the convex hull above, we treated each pixel as a *point*. \r\n% We can, instead, treat each pixel as a *square* by computing the convex hull \r\n% of all the *corners* of every pixel. Here's one way to perform that computation.\r\n\r\noffsets = [ ...\r\n     0.5  -0.5\r\n     0.5   0.5\r\n    -0.5  -0.5\r\n    -0.5   0.5 ]';\r\n\r\noffsets = reshape(offsets,1,2,[]); \r\n\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,'Simplify',true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n%%\r\nimshow(bw2)\r\npixelgrid\r\nhold on\r\nplot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)\r\nhold off\r\ntitle('Convex hull of square pixels')\r\n%% \r\n% This result looks good at first glance. However, it loses some of its \r\n% appeal when you consider the implications for computing the maximum Feret diameter.\r\n%%\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nhold on\r\nplot(end_points(:,1),end_points(:,2),'k','LineWidth',3)\r\nhold off\r\ntitle('The maximum Feret diameter is not horizontal')\r\n%% \r\n% The maximum Feret distance of this horizontal segment of is 6.0828 ($\\sqrt{37}$) \r\n% instead of 6, and the corresponding orientation in degrees is:\r\n\r\natan2d(1,6)\r\n%% \r\n% instead of 0.\r\n% \r\n% Another worthy attempt is to use *diamond* pixels.\r\n%% Diamond Pixels\r\n% Instead of using the four corners of each pixel, let's try using the middle \r\n% of each pixel edge. Once we define the offsets, the code is exactly the same \r\n% as for square pixels.\r\n\r\noffsets = [ ...\r\n     0.5   0.0\r\n     0.0   0.5\r\n    -0.5   0.0\r\n     0.0  -0.5 ]';\r\n\r\noffsets = reshape(offsets,1,2,[]); \r\n\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,'Simplify',true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n%%\r\nimshow(bw2)\r\npixelgrid\r\nhold on\r\nplot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)\r\nhold off\r\ntitle('Convex hull of diamond pixels')\r\n%% \r\n% Now the max Feret diameter result looks better for the horizontal row \r\n% of pixels.\r\n%%\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nhold on\r\nplot(end_points(:,1),end_points(:,2),'k','LineWidth',3)\r\nhold off\r\n%% \r\n% Hold on, though. Consider a square blob.\r\n\r\nbw3 = false(9,9);\r\nbw3(3:7,3:7) = true;\r\nimshow(bw3)\r\npixelgrid\r\n[y,x] = find(bw3);\r\nP = [x y];\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,'Simplify',true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n%%\r\nhold on\r\nplot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nplot(end_points(:,1),end_points(:,2),'k','LineWidth',3)\r\nhold off\r\ntitle('The max Feret diameter is not at 45 degrees')\r\n%% \r\n% We'd like to see the max Feret diameter oriented at 45 degrees, and clearly \r\n% we don't.\r\n\r\n%% Circular Pixels \r\n% OK, I'm going to make one more attempt. I'm going to treat each pixel as \r\n% *approximately* a *circle*. I'm going to approximate a circle using 24 points \r\n% that are spaced at 15-degree intervals along the circumference.\r\n\r\nthetad = 0:15:345;\r\noffsets = 0.5*[cosd(thetad) ; sind(thetad)];\r\noffsets = reshape(offsets,1,2,[]); \r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nh = convhull(S,'Simplify',true);\r\nx_hull = S(h,1);\r\ny_hull = S(h,2);\r\n\r\nimshow(bw3)\r\npixelgrid\r\nhold on\r\nplot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)\r\npoints = [x_hull y_hull];\r\n[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))\r\nplot(end_points(:,1),end_points(:,2),'k','LineWidth',3)\r\naxis on\r\nhold off\r\n%% \r\n% Now the max Feret diameter orientation is what we would naturally expect, \r\n% which is $\\pm 45^{\\circ}$. The orientation would also be as expected for a horizontal \r\n% or vertical segment of pixels.\r\n% \r\n% Still, a circular approximation might not always give exactly what a user \r\n% might expect. Let's go back to the Martha's Vinyard blob that I started with. \r\n% I wrote a function called |pixelHull| that can compute the convex hull of binary \r\n% image pixels in a variety of different ways. The call |pixelHull(bw,24)| computes \r\n% the pixel hull using a 24-point circle approximation.\r\n% \r\n% Here's the maximum Feret diameter using that approximation.\r\n\r\nimshow(bw)\r\nV = pixelHull(bw,24);\r\nhold on\r\nplot(V(:,1),V(:,2),'r-','LineWidth',2,'MarkerSize',12)\r\n[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));\r\nplot(end_points(:,1),end_points(:,2),'m','LineWidth',3)\r\naxis on\r\npixelgrid\r\nhold off\r\n%% \r\n% I think many people might expect the maximum Feret diameter to go corner-to-corner \r\n% in this case, but it doesn't exactly do that.\r\n%%\r\nxlim([22.07 31.92])\r\nylim([8.63 15.20])\r\n%% \r\n% You have to use square pixels to get corner-to-corner.\r\n%%\r\nimshow(bw)\r\nV = pixelHull(bw,'square');\r\nhold on\r\nplot(V(:,1),V(:,2),'r-','LineWidth',2,'MarkerSize',12)\r\n[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));\r\nplot(end_points(:,1),end_points(:,2),'m','LineWidth',3)\r\naxis on\r\npixelgrid\r\nhold off\r\n%%\r\nxlim([22.07 31.92])\r\nylim([8.63 15.20])\r\n%% \r\n% After all this, I'm still not completely certain which shape assumption \r\n% will generally work best. My only firm conclusion is that the point approximation \r\n% is the worst choice. The degeneracies associated with point pixels are just \r\n% too troublesome.\r\n% \r\n% If you have an opinion, please share it in the comments. (Note: A comment \r\n% that says, \"Steve, you're totally overthinking this\" would be totally legit.)\r\n% \r\n% _The rest of the post contains functions used by the code above._\r\n%%\r\nfunction V = pixelHull(P,type)\r\n\r\nif nargin < 2\r\n    type = 24;\r\nend\r\n\r\nif islogical(P)\r\n    P = bwperim(P);\r\n    [i,j] = find(P);\r\n    P = [j i];\r\nend\r\n\r\nif strcmp(type,'square')\r\n    offsets = [ ...\r\n         0.5  -0.5\r\n         0.5   0.5\r\n        -0.5   0.5\r\n        -0.5  -0.5 ];\r\n    \r\nelseif strcmp(type,'diamond')\r\n    offsets = [ ...\r\n         0.5  0\r\n         0    0.5\r\n        -0.5  0\r\n         0   -0.5 ];\r\n     \r\nelse\r\n    % type is number of angles for sampling a circle of diameter 1.\r\n    thetad = linspace(0,360,type+1)';\r\n    thetad(end) = [];\r\n    \r\n    offsets = 0.5*[cosd(thetad) sind(thetad)];\r\nend\r\n\r\noffsets = offsets';\r\noffsets = reshape(offsets,1,2,[]);        \r\n\r\nQ = P + offsets;\r\nR = permute(Q,[1 3 2]);\r\nS = reshape(R,[],2);\r\n\r\nk = convhull(S,'Simplify',true);\r\nV = S(k,:);\r\nend\r\n##### SOURCE END ##### f024816cb729487aaace442476b0b27b\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/ShapeOfAPixel_m_19.png\" onError=\"this.style.display ='none';\" \/><\/div><p>ContentsThe Shape of a PixelWeaknesses of Using the Pixel CentersSquare PixelsDiamond PixelsCircular PixelsThe Shape of a PixelWhat is the shape of a pixel? At various times, I have a pixel as a... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2018\/03\/16\/what-is-the-shape-of-a-pixel\/\">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":[1209,50,140,835,1207,733,102,348,466,90,76,36,118,32,1195,68,170,1211,1197,52,100,360,298],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/2826"}],"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=2826"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/2826\/revisions"}],"predecessor-version":[{"id":2880,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/2826\/revisions\/2880"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=2826"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=2826"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=2826"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}