{"id":215,"date":"2008-06-13T13:41:31","date_gmt":"2008-06-13T17:41:31","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/06\/13\/performance-optimization-for-applylut\/"},"modified":"2019-10-28T09:33:14","modified_gmt":"2019-10-28T13:33:14","slug":"performance-optimization-for-applylut","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/06\/13\/performance-optimization-for-applylut\/","title":{"rendered":"Performance optimization for applylut"},"content":{"rendered":"
\n

I thought I would finish my discussion of applylut<\/tt> and makelut<\/tt> by describing a performance optimization we implemented for version 6 (R2007b) of the Image Processing Toolbox.<\/p>\n

A couple of years ago, a developer on our team wanted to know the details of the 'thin' option of bwmorph<\/tt>. This syntax \"thins\" connected strokes in a binary image. For example:<\/p>\n

bw = imread('text.png'<\/span>);\r\nimshow(bw)<\/pre>\n
<\/p>\n
bwt = bwmorph(bw, 'thin'<\/span>);\r\nimshow(bwt)<\/pre>\n
<\/p>\n
With the syntax bwmorph(bw, 'thin', N)<\/tt>, you can tell bwmorph<\/tt> to repeat the thinning operation N times. If you use bwmorph(bw, 'thin', Inf)<\/tt>, then bwmorph<\/tt> will repeat the operation until the image stops changing.<\/p>\n
bwt = bwmorph(bw, 'thin'<\/span>, Inf);\r\nimshow(bwt)<\/pre>\n
<\/p>\n
So, in this long-ago conversation about bwmorph<\/tt>, I explained that many of the operations supported by bwmorph<\/tt> are implemented using applylut<\/tt>. About halfway through explaining applylut<\/tt>, I had a light bulb moment. It dawned on me that the thinning operation of bwmorph<\/tt> never<\/b> changes a 0-valued pixel to a 1! So for any 0-valued input pixel, it is kind of pointless to examine the surrounding 3-by-3
\nneighborhood, which is what applylut<\/tt> does. One could just immediately determine that the corresponding output pixel should be 0.<\/p>\n
There are other operations ('thicken', for example) that never change a 1-valued pixel to a 0.<\/p>\n
After some further discussion, we realized that applylut<\/tt> could examine any lookup table to determine whether it had one of these properties. So that's what we did. Starting in version
\n6 of the toolbox, applylut<\/tt> examines the input lookup table to see if it always transforms a 0-valued pixel to 0, or a 1-valued pixel to 1. If so, special-case
\ncode is used that skips the neighborhood lookup step for pixels that are 0 (or 1).<\/p>\n
Here's the time required on my Windows laptop to apply the thinning operation to text.png. (You can find the function timeit<\/tt> on the MATLAB Central File Exchange.)<\/p>\n
f = @() bwmorph(bw, 'thin'<\/span>, Inf);\r\ntimeit(f)<\/pre>\n
ans =\r\n\r\n    0.0044\r\n\r\n<\/pre>\n
Running with an older version of the Image Processing Toolbox, the same operation takes about 104 milliseconds. That's about
\na factor of 23 reduction in execution time!<\/p>\n
[Note added June 16, 2008:]<\/em> The applylut<\/tt> optimization was not the only change made to speed up the 'thin'<\/tt> option of bwmorph. We also realized that work being done using several lookup tables could be combined in a single lookup table.<\/p>\n
These optimizations went into the product in R2007b, which shipped in September 2007. Your mileage will certainly vary depending
\non your particular data. The speedup you see depends on how many 0-valued (or 1-valued) pixels the image contains.<\/p>\n
For your reference, here are my previous posts on applylut<\/tt> and makelut<\/tt>:<\/p>\n
\n