Steve on Image Processing

Concepts, algorithms & MATLAB

What is the Shape of a Pixel? 4

Posted by Steve Eddins,

Contents

The Shape of a Pixel

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.

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 29-Sep-2017, 24-Oct-2017, and 20-Feb-2018.) Let me try to explain why.

Here's a binary image with a single foreground blob (or "object," or "connected component.")

bw = imread('Martha''s Vineyard (30x20).png');
imshow(bw)

Most of the time, we think of image pixels as being squares with unit area.

pixelgrid

We can use find to get the $x$- and $y$-coordinates of the pixel centers, and then we can use convhull 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 bwperim. I'm not going to show that step everywhere in this example, though.

[y,x] = find(bwperim(bw));
hold on
plot(x,y,'.')
hold off
title('Pixel centers')
h = convhull(x,y);
x_hull = x(h);
y_hull = y(h);
hold on
hull_line = plot(x_hull,y_hull,'r*','MarkerSize',12);
hold off
title('Pixel centers and convex hull vertices')

Notice that there are some chains of three or more colinear convex hull vertices.

xlim([21.5 32.5])
ylim([9.5 15.5])
title('Colinear convex hull vertices')

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 convhull using the 'Simplify' parameter.

h = convhull(x,y,'Simplify',true);
x_hull = x(h);
y_hull = y(h);
delete(hull_line);
hold on
plot(x_hull,y_hull,'r*','MarkerSize',12)
hold off
title('Colinear hull vertices removed')
imshow(bw)
hold on
plot(x_hull,y_hull,'r-*','LineWidth',2,'MarkerSize',12)
hold off
title('A Blob''s Convex Hull and Its Vertices')

Notice, though, that there are white bits showing outside the red convex hull polygon. That's because we are only using the pixel centers.

Weaknesses of Using the Pixel Centers

Consider a simpler binary object, one that has only one row.

bw2 = false(5,15);
bw2(3,5:10) = true;
imshow(bw2)
pixelgrid
[y,x] = find(bw2);

The function convhull doesn't even work on colinear points.

try
    hull = convhull(x,y,'Simplify',true);
catch e
    fprintf('Error message from convhull: "%s"\n', e.message);
end
Error message from convhull: "Error computing the convex hull. The points may be collinear."

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.

hold on
plot(x,y,'r-*','MarkerSize',12,'LineWidth',2)
hold off
title('Degenerate convex hull polygon')

We can solve this degeneracy problem by using square pixels.

Square Pixels

In the computation of the convex hull above, we treated each pixel as a point. We can, instead, treat each pixel as a square by computing the convex hull of all the corners of every pixel. Here's one way to perform that computation.

offsets = [ ...
     0.5  -0.5
     0.5   0.5
    -0.5  -0.5
    -0.5   0.5 ]';

offsets = reshape(offsets,1,2,[]);

P = [x y];
Q = P + offsets;
R = permute(Q,[1 3 2]);
S = reshape(R,[],2);

h = convhull(S,'Simplify',true);
x_hull = S(h,1);
y_hull = S(h,2);
imshow(bw2)
pixelgrid
hold on
plot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)
hold off
title('Convex hull of square pixels')

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.

points = [x_hull y_hull];
[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))
hold on
plot(end_points(:,1),end_points(:,2),'k','LineWidth',3)
hold off
title('The maximum Feret diameter is not horizontal')
d =

    6.0828


end_points =

   10.5000    2.5000
    4.5000    3.5000

The maximum Feret distance of this horizontal segment of is 6.0828 ($\sqrt{37}$) instead of 6, and the corresponding orientation in degrees is:

atan2d(1,6)
ans =

    9.4623

instead of 0.

Another worthy attempt is to use diamond pixels.

Diamond Pixels

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.

offsets = [ ...
     0.5   0.0
     0.0   0.5
    -0.5   0.0
     0.0  -0.5 ]';

offsets = reshape(offsets,1,2,[]);

P = [x y];
Q = P + offsets;
R = permute(Q,[1 3 2]);
S = reshape(R,[],2);

h = convhull(S,'Simplify',true);
x_hull = S(h,1);
y_hull = S(h,2);
imshow(bw2)
pixelgrid
hold on
plot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)
hold off
title('Convex hull of diamond pixels')

Now the max Feret diameter result looks better for the horizontal row of pixels.

points = [x_hull y_hull];
[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))
hold on
plot(end_points(:,1),end_points(:,2),'k','LineWidth',3)
hold off
d =

     6


end_points =

   10.5000    3.0000
    4.5000    3.0000

Hold on, though. Consider a square blob.

bw3 = false(9,9);
bw3(3:7,3:7) = true;
imshow(bw3)
pixelgrid
[y,x] = find(bw3);
P = [x y];
Q = P + offsets;
R = permute(Q,[1 3 2]);
S = reshape(R,[],2);

h = convhull(S,'Simplify',true);
x_hull = S(h,1);
y_hull = S(h,2);
hold on
plot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)
points = [x_hull y_hull];
[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))
plot(end_points(:,1),end_points(:,2),'k','LineWidth',3)
hold off
title('The max Feret diameter is not at 45 degrees')
d =

    6.4031


end_points =

    7.5000    3.0000
    2.5000    7.0000

We'd like to see the max Feret diameter oriented at 45 degrees, and clearly we don't.

Circular Pixels

OK, I'm going to make one more attempt. I'm going to treat each pixel as approximately a circle. I'm going to approximate a circle using 24 points that are spaced at 15-degree intervals along the circumference.

thetad = 0:15:345;
offsets = 0.5*[cosd(thetad) ; sind(thetad)];
offsets = reshape(offsets,1,2,[]);
Q = P + offsets;
R = permute(Q,[1 3 2]);
S = reshape(R,[],2);

h = convhull(S,'Simplify',true);
x_hull = S(h,1);
y_hull = S(h,2);

imshow(bw3)
pixelgrid
hold on
plot(x_hull,y_hull,'r-*','MarkerSize',12,'LineWidth',2)
points = [x_hull y_hull];
[d,end_points] = maxFeretDiameter(points,antipodalPairs(points))
plot(end_points(:,1),end_points(:,2),'k','LineWidth',3)
axis on
hold off
d =

    6.6569


end_points =

    7.3536    7.3536
    2.6464    2.6464

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.

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 pixelHull that can compute the convex hull of binary image pixels in a variety of different ways. The call pixelHull(bw,24) computes the pixel hull using a 24-point circle approximation.

Here's the maximum Feret diameter using that approximation.

imshow(bw)
V = pixelHull(bw,24);
hold on
plot(V(:,1),V(:,2),'r-','LineWidth',2,'MarkerSize',12)
[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));
plot(end_points(:,1),end_points(:,2),'m','LineWidth',3)
axis on
pixelgrid
hold off

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.

xlim([22.07 31.92])
ylim([8.63 15.20])

You have to use square pixels to get corner-to-corner.

imshow(bw)
V = pixelHull(bw,'square');
hold on
plot(V(:,1),V(:,2),'r-','LineWidth',2,'MarkerSize',12)
[d,end_points] = maxFeretDiameter(V,antipodalPairs(V));
plot(end_points(:,1),end_points(:,2),'m','LineWidth',3)
axis on
pixelgrid
hold off
xlim([22.07 31.92])
ylim([8.63 15.20])

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.

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.)

The rest of the post contains functions used by the code above.

function V = pixelHull(P,type)

if nargin < 2
    type = 24;
end

if islogical(P)
    P = bwperim(P);
    [i,j] = find(P);
    P = [j i];
end

if strcmp(type,'square')
    offsets = [ ...
         0.5  -0.5
         0.5   0.5
        -0.5   0.5
        -0.5  -0.5 ];

elseif strcmp(type,'diamond')
    offsets = [ ...
         0.5  0
         0    0.5
        -0.5  0
         0   -0.5 ];

else
    % type is number of angles for sampling a circle of diameter 1.
    thetad = linspace(0,360,type+1)';
    thetad(end) = [];

    offsets = 0.5*[cosd(thetad) sind(thetad)];
end

offsets = offsets';
offsets = reshape(offsets,1,2,[]);

Q = P + offsets;
R = permute(Q,[1 3 2]);
S = reshape(R,[],2);

k = convhull(S,'Simplify',true);
V = S(k,:);
end


Get the MATLAB code

Published with MATLAB® R2017b

4 CommentsOldest to Newest

Cris replied on : 1 of 4

Steve,

I have been using your idea of joining pixel edge centers to create a polygonal representation of objects. I think that is the best approach. The polygon always has an area exactly half a pixel smaller than the area of the object (assuming it’s a solid object), and it works great for the convex hull. With regard to the Feret diameter being slightly off from what you expect from the square grid representation of the object: I don’t see this as a problem. The true boundary of the object does not follow the grid edges, it lies somewhere in between the pixel centers. The exact location has been lost by the sampling and binarization. Hence enforcing the pointy corners rather than assuming a slightly smaller shape has no advantage. This amounts to tweaking measurements within the uncertainty bounds. This is why I appreciate your circle idea, it acknowledges that we don’t know the exact location, and a circle is a really good estimate of the true boundary. However, it seems computationally more expensive and doesn’t provide any more precision than the diamond assumption, because the both results are within the maximum precision you can expect from the given data.

Thanks for this post! Very enjoyable to revisit these concepts.

Mark Hayworth replied on : 3 of 4

Steve, I think it helps to take a step back and think of where the binary pixel actually came from originally. It came from, say, thresholding a gray scale image. So what about that gray scale pixel? You probably know about the concept of IFOV in remote sensing – Instantaneous field of view. Essentially it’s the area that the pixel would cover on the original scene (the earth). So, it might be a 10 meter by 10 meter patch on the earth that corresponds to a pixel. Now that place in the scene has a bunch of intensities but they all fall on the CCD pixel and what you get is the AVERAGE intensity of the rectangular/square patch – a single value that represents that rectangular/square IFOV. It’s rectangular/square because that is the shape of the CCD well on the image sensor. Now if you had super resolution and were able to threshold within the pixel, would it all be uniform and give a single true or false value? No, most likely it wouldn’t (unless you had a truly uniform scene). You’d have some crazy shape that is the actual shape within that pixel. It might have curvy boundaries – who knows? You can’t know. So I think it’s not practical, but really a theoretical concept, to think that you should have a point, circle, square, diamond or whatever shape. Any of these will not match the ACTUAL shape you’d have if you could have enough resolution to see the actual scene. So, I guess I’m saying it doesn’t matter what shape you assume since they’ll ALL be wrong, and you shouldn’t worry if one or another is off by a tiny bit.

Mark—Thanks for your helpful perspective.

I didn’t make it very clear in this post, but partly I was motivated by and writing from a software developer point of view. My previous experience with functions in the Image Processing Toolbox has made me more aware of the need to anticipate and meet user expectations, wherever possible. It is also important to strive for consistency with various parts of the software. Inconsistent or surprising treatment of pixel geometry has caused user confusion before, such as with imcrop. In this case, when I realized that the square pixel assumption would lead to the maximum Feret diameter *never* being at exactly 0 or 90 degrees, I knew that such a result would be surprising and confusing. I was seeking a pixel geometry assumption that would give less surprising results. To put it another way: if we shipped a max Feret diameter capability in Image Processing Toolbox, and it returned an orientation of something other than 0 degrees for a horizontal, one-pixel-high row of pixels, that would practically guarantee tech support calls.

Add A Comment

Your email address will not be published. Required fields are marked *

Preview: hide