{"id":5702,"date":"2022-09-20T16:50:22","date_gmt":"2022-09-20T20:50:22","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=5702"},"modified":"2022-09-20T16:50:22","modified_gmt":"2022-09-20T20:50:22","slug":"puzzle-pieces-and-polyshapes","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2022\/09\/20\/puzzle-pieces-and-polyshapes\/","title":{"rendered":"Puzzle Pieces and Polyshapes"},"content":{"rendered":"
color segmentation, opening by reconstruction, boundary tracing, polyshapes<\/span><\/div>
Earlier this summer, Cleve sent me this picture of a puzzle.<\/span><\/div>
\"Cheese_puzzle.png\"<\/img><\/div>
He asked for tips on turning the individual \"cheese slices\" into patch objects for plotting and manipulation, perhaps something like this:<\/span><\/div>
\"colored-puzzle-pieces.png\"<\/img><\/div>
Cleve was working on what became <\/span>\"Polygons, Polyshapes and Puzzles,\" his 21-Aug-2022 blog post<\/span><\/a>.<\/span><\/div>
In my post today, I'll elaborate on this step.<\/span><\/div>
The first thing that occurred to me was to use color to segment the puzzle pieces from the rest of the image. I used the <\/span>Color Thresholder app<\/span><\/a> to determine some threshold values in CIELAB space.<\/span><\/div>
\"color-thresholder-screenshot.png\"<\/img><\/div>
<\/span><\/div>
rgb = imread(<\/span>\"Cheese_puzzle.png\"<\/span>);<\/span><\/span><\/div><\/div>
lab = rgb2lab(rgb);<\/span><\/span><\/div><\/div>
% Threshold values chosen with the help of colorThresholder.<\/span><\/span><\/div><\/div>
[L,a,b] = imsplit(lab);<\/span><\/span><\/div><\/div>
mask = ((30 <= L) & (L <= 98)) & <\/span>...<\/span><\/span><\/div><\/div>
((-20 <= a) & (a <= 16)) & <\/span>...<\/span><\/span><\/div><\/div>
((26 <= b) & (b <= 83));<\/span><\/span><\/div><\/div>
imshow(mask)<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
Next, we need to get rid of the extra unwanted foreground pixels. I'll use a method that the mathematical morphology folks call <\/span>opening by reconstruction<\/span><\/a>. The first step is to erode the image in a way that eliminates all the unwanted pixels, while maintaining at least a portion of all the objects we want to keep. An erosion by a vertical line will get rid of the thin horizontal lines, and an erosion by a horizontal line will get rid of the thin vertical lines.<\/span><\/div>
mask2 = imerode(mask,ones(21,1));<\/span><\/span><\/div><\/div>
imshow(mask2)<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
mask3 = imerode(mask2,ones(1,21));<\/span><\/span><\/div><\/div>
imshow(mask3)<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
In the image above, the extraneous foreground pixels are gone, but the puzzle pieces have been shrunk. I'll use morphological reconstruction to recover the entire puzzle pieces.<\/span><\/div>
mask4 = imreconstruct(mask3,mask);<\/span><\/span><\/div><\/div>
imshow(mask4)<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
Great. Now, how do we turn these puzzle pieces into some kind of easily plottable representations? Cleve had suggested patch objects, but it is complicated to create patch objects containing holes. I suggested using <\/span>polyshape<\/span> instead. A <\/span>polyshape<\/span> is an object that can represent shapes that are composed of polygons. You can create a <\/span>polyshape<\/span> from a collection of polygons that bound individual regions and holes, and the Image Processing Toolbox function <\/span>bwboundaries<\/span> can produce just such a list of polygons.<\/span><\/div>
b = bwboundaries(mask4)<\/span><\/span><\/div>
b = <\/span>9\u00d71 cell <\/span><\/div>
 <\/span><\/th>1<\/span><\/th><\/tr><\/thead>
1<\/span><\/th>1820\u00d72 double<\/span><\/td><\/tr>
2<\/span><\/th>1687\u00d72 double<\/span><\/td><\/tr>
3<\/span><\/th>1669\u00d72 double<\/span><\/td><\/tr>
4<\/span><\/th>1771\u00d72 double<\/span><\/td><\/tr>
5<\/span><\/th>1328\u00d72 double<\/span><\/td><\/tr>
6<\/span><\/th>613\u00d72 double<\/span><\/td><\/tr>
7<\/span><\/th>609\u00d72 double<\/span><\/td><\/tr>
8<\/span><\/th>457\u00d72 double<\/span><\/td><\/tr>
9<\/span><\/th>[472,980;472,980]<\/span><\/td><\/tr><\/tbody><\/table><\/div><\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
The <\/span>polyshape<\/span> function can take a collection of bounding polygons and automatically figure out which polygons bound regions and which bound holes, but the form of the <\/span>polyshape<\/span> input arguments is a bit different from what <\/span>bwboundaries<\/span> produces. Here is some code to convert the <\/span>bwboundaries<\/span> output into something that <\/span>polyshape<\/span> can handle.<\/span><\/div>
for <\/span>k = 1:length(b)<\/span><\/span><\/div><\/div>
X{k} = b{k}(:,2);<\/span><\/span><\/div><\/div>
Y{k} = b{k}(:,1);<\/span><\/span><\/div><\/div>
end<\/span><\/span><\/div><\/div>
ps = polyshape(X,Y)<\/span><\/span><\/div>
Warning: Boundaries with less than 3 points were removed.<\/div>
<\/div><\/div><\/div>
Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce inaccurate or unexpected results. Input data has been modified to create a well-defined polyshape.<\/div>
<\/div><\/div><\/div>
ps = <\/span><\/div>
polyshape with properties:\r\n\r\n Vertices: [3529\u00d72 double]\r\n NumRegions: 6\r\n NumHoles: 3\r\n<\/div><\/div><\/div><\/div><\/div><\/div>
Well, that's a bit messy. In my image processing work, I often see this warning message from polyshape. Usually it is because I'm passing a bunch of colinear vertices to polyshape. They are colinear because the vertices are on the image pixel grid. I generally ignore the warning.<\/span><\/div>
There's another issue, though. Why does the output of polyshape say it has 6 regions instead of 5? I had to search a bit for the reason. We can see it by zooming into one of the corners of the lower right puzzle piece and superimposing the boundary traced by bwboundaries.<\/span><\/div>
figure<\/span><\/span><\/div><\/div>
imshow(mask)<\/span><\/span><\/div><\/div>
hold <\/span>on<\/span><\/span><\/div><\/div>
plot(b{5}(:,2),b{5}(:,1),<\/span>'b'<\/span>)<\/span><\/span><\/div><\/div>
hold <\/span>off<\/span><\/span><\/div><\/div>
xlim([1120 1140])<\/span><\/span><\/div><\/div>
ylim([990 1010])<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
There's a spot where the traced boundary is self-intersecting, and that causes <\/span>polyshape<\/span> to treat that tiny triangle at the bottom as a separate region. We can do a little area-based processing of the <\/span>polyshape<\/span> to get rid of that triangle.<\/span><\/div>
Split the polyshape into separate regions:<\/span><\/div>
ps_regions = regions(ps)<\/span><\/span><\/div>
ps_regions = <\/span><\/div>
6\u00d71 polyshape array with properties:\r\n\r\n Vertices\r\n NumRegions\r\n NumHoles\r\n<\/div><\/div><\/div><\/div><\/div><\/div>
Find the area of each region:<\/span><\/div>
region_areas = area(ps_regions)<\/span><\/span><\/div>
region_areas = <\/span>6\u00d71<\/span><\/div><\/div>
105<\/sup> \u00d7<\/span><\/div>
1.7261\r\n 1.5884\r\n 1.0799\r\n 1.9781\r\n 0.9128\r\n 0.0000\r\n<\/div>
<\/div>
<\/div><\/div><\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
And get rid of the tiny region:<\/span><\/div>
ps_regions(region_areas < 1) = []<\/span><\/span><\/div>
ps_regions = <\/span><\/div>
5\u00d71 polyshape array with properties:\r\n\r\n Vertices\r\n NumRegions\r\n NumHoles\r\n<\/div><\/div><\/div><\/div><\/div><\/div>
Now we can plot our puzzle pieces. If you pass an array of polyshapes to plot, it will color each one separately.<\/span><\/div>
plot(ps_regions)<\/span><\/span><\/div><\/div>
axis <\/span>ij<\/span><\/span><\/div><\/div>
axis <\/span>equal<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
I love polyshapes. They come with a rich collection of useful functions (see \"Object Functions\" on the <\/span>polyshape<\/span> reference page<\/span><\/a>.) You can modify them, take them apart, join them using Boolean operations, measure them, query point locations, etc.<\/span><\/div>
For example, the <\/span>polybuffer<\/span> function can expand (or shrink) a polyshape based on the idea of creating a \"buffer zone\" around the shape. To illustrate, let's take one of the puzzle pieces and give it a 50-pixel buffer zone.<\/span><\/div>
ps5 = ps_regions(5);<\/span><\/span><\/div><\/div>
ps5_50 = polybuffer(ps5,50);<\/span><\/span><\/div><\/div>
figure<\/span><\/span><\/div><\/div>
plot(ps5_50)<\/span><\/span><\/div><\/div>
axis <\/span>ij<\/span><\/span><\/div><\/div>
axis <\/span>equal<\/span><\/span><\/div><\/div>
hold <\/span>on<\/span><\/span><\/div><\/div>
plot(ps5)<\/span><\/span><\/div><\/div>
hold <\/span>off<\/span><\/span><\/div>
<\/div>
<\/div>
<\/div>
<\/div><\/div><\/div><\/div><\/div>
Are polyshapes useful in your work? I'd like to hear about it. Please leave a comment.<\/span><\/div>\r\n<\/div>