{"id":207,"date":"2008-04-21T12:11:27","date_gmt":"2008-04-21T16:11:27","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/04\/21\/corresponding-labels\/"},"modified":"2019-10-28T09:29:49","modified_gmt":"2019-10-28T13:29:49","slug":"corresponding-labels","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/04\/21\/corresponding-labels\/","title":{"rendered":"Corresponding labeled objects in two images"},"content":{"rendered":"
\r\n

Several questions I've seen about bwlabel<\/tt> are about finding the correspondences between object labels in two images. In other words, if a particular pixel is in the\r\n foreground in two binary images, is that pixel labeled the same in both images, or is it different? In general, for foreground\r\n pixels in the same locations, how do object labels in one binary image match up to object labels in the second?\r\n <\/p>\r\n

I'll show one method using the same small binary image that I've been using in my other recent bwlabel posts<\/a>.\r\n <\/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, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
Compute and display the labeled objects.<\/p>
L1 = bwlabel(bw);\r\n\r\nI = im2uint8(bw);\r\nI(~bw) = 200;\r\nI(bw) = 240;\r\ns = regionprops(L1, 'extrema'<\/span>);\r\nimshow(I, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nfor<\/span> k = 1:numel(s)\r\n   e = s(k).Extrema;\r\n   text(e(1,1), e(1,2), sprintf('%d'<\/span>, k));\r\nend<\/span>\r\nhold off<\/span><\/pre> 
Now let's try a morphological closing operation on this image.<\/p>
bw2 = imclose(bw, ones(3,3));\r\nimshow(bw2, 'InitialMagnification'<\/span>, 'fit'<\/span>)<\/pre> 
Compute and display the labeled objects in the second image.<\/p>
L2 = bwlabel(bw2);\r\n\r\nI2 = im2uint8(bw2);\r\nI2(~bw2) = 200;\r\nI2(bw2) = 240;\r\ns2 = regionprops(L2, 'extrema'<\/span>);\r\nimshow(I2, 'InitialMagnification'<\/span>, 'fit'<\/span>)\r\nhold on<\/span>\r\nfor<\/span> k = 1:numel(s2)\r\n   e2 = s2(k).Extrema;\r\n   text(e2(1,1), e2(1,2), sprintf('%d'<\/span>, k));\r\nend<\/span>\r\nhold off<\/span><\/pre> 
Compare the two sets of labels visually.  You can see that the broken \"f\" character on the bottom line was labeled with 6\r\n      and 7 in the first image.  In the second image, the broken pieces have been merged and labeled with 4.\r\n   <\/p>\r\n   
On the first line of the first image, the \"s\" and \"t\" characters are distinct and are labeled with 2 and 4, respectively.\r\n       In the second image, they have been merged into one object that was labeled 2.\r\n   <\/p>\r\n   
Let's see how to compute all of the correspondences between the object labels in the two images.  First, compute the set of\r\n      pixels that belong to the foreground in both images.\r\n   <\/p>
overlap = bw & bw2;<\/pre>
Next, compute the corresponding label pairs by using logical indexing into the two label matrices.<\/p>
pairs = [L1(overlap), L2(overlap)];<\/pre>
Eliminate the duplicates in the list of pairs.<\/p>
pairs = unique(pairs, 'rows'<\/span>);<\/pre>
Let's look at a few of the pairs to see how to interpret their meaning:<\/p>
pairs(1:5, :)<\/pre>
\r\nans =\r\n\r\n     1     1\r\n     2     2\r\n     3     3\r\n     4     2\r\n     5     1\r\n\r\n<\/pre>
Pixels belonging to objects 1 and 5 in the first image belong to a single object, labeled 1, in the second image.  Similarly,\r\n      pixels belonging to objects 2 and 4 in the first image belong to a single object, labeled 2, in the second image.  Pixels\r\n      labeled with a 3 in the first image are also labeled with a 3 in the second image.\r\n   <\/p>\r\n   
Depending on your application, you might want to form an adjacency graph, represented as a sparse matrix.<\/p>
S = sparse(pairs(:,1), pairs(:,2), 1);\r\nspy(S)<\/pre> 
One way to use the graph is to find all the object labels in image 1 that correspond to a given label in image 2. For example,\r\n      here are all the first-image objects corresponding to the object labeled with 6 in the second image:\r\n   <\/p>
find(S(:, 6))<\/pre>
\r\nans =\r\n\r\n     9\r\n    10\r\n\r\n<\/pre>
My other recent bwlabel<\/tt> posts were about search order<\/a> and relabeling<\/a>. You can also look the archive of all my posts about connected-component labeling<\/a>.\r\n   <\/p>