{"id":203,"date":"2008-03-25T10:45:04","date_gmt":"2008-03-25T14:45:04","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/03\/25\/bwlabel-search-order\/"},"modified":"2019-10-24T14:01:24","modified_gmt":"2019-10-24T18:01:24","slug":"bwlabel-search-order","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/03\/25\/bwlabel-search-order\/","title":{"rendered":"bwlabel search order"},"content":{"rendered":"
\r\n

I've received several questions over the past months about the search order for the function bwlabel<\/tt> and whether it can be changed. Today's post discusses the search-order issue, how useful it might or might not be to change\r\n it, and how to use regionprops<\/tt> to reorder labeled objects.\r\n <\/p>\r\n

First, though, a brief review of bwlabel<\/tt>: It takes a binary image, bw<\/tt>, and produces a label matrix<\/i>, L<\/tt>. The elements of L are integer values greater than or equal to 0. The elements equal to 0 are the background. The elements\r\n equal to 1 make up one object, the elements equal to 2 make up a second object, and so on. Here's a small example.\r\n <\/p>

bw = false(5, 5);\r\nbw(1:2, 1:2) = true;\r\nbw(4:5, 1:2) = true;\r\nbw(1:2, 4:5) = true;\r\nbw(4:5, 4:5) = true<\/pre>
\r\nbw =\r\n\r\n     1     1     0     1     1\r\n     1     1     0     1     1\r\n     0     0     0     0     0\r\n     1     1     0     1     1\r\n     1     1     0     1     1\r\n\r\n<\/pre>
L = bwlabel(bw)<\/pre>
\r\nL =\r\n\r\n     1     1     0     3     3\r\n     1     1     0     3     3\r\n     0     0     0     0     0\r\n     2     2     0     4     4\r\n     2     2     0     4     4\r\n\r\n<\/pre>
So bwlabel<\/tt> found four connected groups of foreground pixels in bw<\/tt>.  Since bwlabel<\/tt> scans the pixels of bw<\/tt> of column order, it finds the object in the lower-left corner second, which is why those pixels are labeled with a \"2\" in\r\n      L<\/tt>.\r\n   <\/p>\r\n   
Sometimes people ask if bwlabel<\/tt> can be made to search along the rows instead of along the columns, because they want the object in the upper right to be\r\n      found second.\r\n   <\/p>\r\n   
The search order for bwlabel<\/tt> is determined by the internal memory storage order of elements in MATLAB.  Searching along rows would substantially slow\r\n      the function down.  However, it is possible, with the assistance of regionprops<\/tt>, to efficiently postprocess the output of bwlabel<\/tt> so that objects are ordered however you wish.\r\n   <\/p>\r\n   
Before I show that technique, though, let me show an example of how ordering objects in two dimensions is not always straightforward,\r\n      no matter which way you search.\r\n   <\/p>\r\n   
Here's a snippet of a scanned text image we've look at before:<\/p>
url = 'https:\/\/blogs.mathworks.com\/images\/steve\/186\/scanned_page.png'<\/span>;\r\nbw = imread(url);\r\nbw = ~bw(1107:1194, 17:135);\r\nimshow(bw)<\/pre> 
One might expect that bwlabel<\/tt> would label the upper-left corner \"s\" as the first object found.  But that doesn't happen.\r\n   <\/p>
L = bwlabel(bw);\r\n\r\n% Show the object labeled first.<\/span>\r\nimshow(L == 1)<\/pre> 
Why is the F found first?  We can see why if we zoom in on the upper-left corner of the image.<\/p>
set(gcf, 'Position'<\/span>, [100 100 400 300])\r\nimshow(bw(1:50, 1:20), 'InitialMag'<\/span>, 'fit'<\/span>)<\/pre> 
The serif on the upper-left of the \"F\" extends to the left of the letter \"s.\"  Therefore, the columnwise scan performed by\r\n      bwlabel<\/tt> finds the \"F\" first.\r\n   <\/p>\r\n   
We could force a row-wise labeling search by transposing the binary image and then the output of bwlabel<\/tt>, like this:\r\n   <\/p>
L = bwlabel(bw')';<\/pre>
But another surprise awaits; the first object found still isn't the \"s\"!<\/p>
imshow(L == 1)<\/pre> 
The \"t\" is found first, because the vertical stem of the \"t\" extends higher than the top of the \"s\" character.<\/p>\r\n   
Also, bwlabel<\/tt> will merge two or more initially assigned labels if it discovers along the way that two or more apparently separate objects\r\n      are actually connected.  This can change the labeling order in unexpected ways.\r\n   <\/p>\r\n   
With those cautionary notes in mind, let me show you how to postprocess the output of bwlabel<\/tt> to sort objects as desired.\r\n   <\/p>\r\n   
First, let's use regionprops<\/tt> to get some object measurements that might be useful for object ordering.\r\n   <\/p>
s = regionprops(L, 'BoundingBox'<\/span>, 'Extrema'<\/span>, 'Centroid'<\/span>);<\/pre>
We could sort the objects from left to right according to the left edge of the bounding box.<\/p>
boxes = cat(1, s.BoundingBox);\r\nleft_edge = boxes(:,1);\r\n[sorted, sort_order] = sort(left_edge);\r\ns2 = s(sort_order);<\/pre>
Let's visualize that sort order.<\/p>
I = im2uint8(bw);\r\nI(~bw) = 200;\r\nI(bw) = 240;\r\nset(gcf, 'Position'<\/span>, [100 100 400 300]);\r\nimshow(I, 'InitialMag'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nfor<\/span> k = 1:numel(s2)\r\n   centroid = s2(k).Centroid;\r\n   text(centroid(1), centroid(2), sprintf('%d'<\/span>, k));\r\nend<\/span>\r\nhold off<\/span><\/pre> 
To sort according to a row-wise search order, sort lexicographically (using sortrows<\/tt><\/a> instead of sort<\/tt>) on the left-most top extremum of each object. This extremum is the first row of the 'Extrema'<\/tt> output from regionprops<\/tt>.\r\n   <\/p>
extrema = cat(1, s.Extrema);\r\nleft_most_top = extrema(1:8:end, :);\r\n[sorted, sort_order] = sortrows(fliplr(left_most_top));\r\ns2 = s(sort_order);\r\nimshow(I, 'InitialMag'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nfor<\/span> k = 1:numel(s2)\r\n   centroid = s2(k).Centroid;\r\n   text(centroid(1), centroid(2), sprintf('%d'<\/span>, k));\r\nend<\/span>\r\nhold off<\/span><\/pre> 
Notice how the characters still aren't well-ordered from left to right.  That's because the taller ones get sorted earlier.\r\n       Let's try sorting first on the bottom of each character instead of the top, and quantizing the bottom coordinate.  The left-most\r\n      bottom extremum is the 6th row in 'Extrema'<\/tt> measurement.\r\n   <\/p>
left_most_bottom = extrema(6:8:end, :);\r\nleft = left_most_bottom(:, 1);\r\nbottom = left_most_bottom(:, 2);\r\n% quantize the bottom coordinate<\/span>\r\nbottom = 6 * round(bottom \/ 6);\r\n[sorted, sort_order] = sortrows([bottom left]);\r\ns2 = s(sort_order);\r\nimshow(I, 'InitialMag'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nfor<\/span> k = 1:numel(s2)\r\n   centroid = s2(k).Centroid;\r\n   text(centroid(1), centroid(2), sprintf('%d'<\/span>, k));\r\nend<\/span>\r\nhold off<\/span><\/pre> 
That's somewhat better, but to get further I imagine that some higher-level analysis of the structure of text lines in the\r\n      image will be necessary.\r\n   <\/p>\r\n   
Notice that I did not modify the label matrix, L<\/tt>, in these postprocessing steps.  Next time I'll show how to relabel L<\/tt>.\r\n   <\/p>