An internal design discussion this week prompted me to reflect on the history of logical arrays in MATLAB. Because the Image Processing Toolbox treats logical arrays as binary images, their behavior and use is important to those of us who develop (and use!) the product.
If you travel back in time to 1996, MATLAB had only a single type: the two-dimensional, double-precision matrix. No multidimensional arrays, integer arrays, char arrays, cell arrays, struct arrays, or logical arrays. You could define any type you wanted as long it was 2-D double.
But if you go back ten years earlier to 1987, you'll find that an important MATLAB "logical" behavior existed even then: logical indexing. Basically, logical indexing was defined back then as expression of the form A(B), where B was the same size as A and contained only 0s and 1s.
Below is a screen shot from MATLAB 3.13, which was the earliest version of MATLAB I ever used. (Amazingly, it still runs on my computer today!)
You can see above the effect of logical indexing: it extracts all the values in the locations where the indexing vector (or matrix) equals 1.
I don't know if this logical indexing behavior extends all the way back to the first commercial version of MATLAB in 1984. I do know that it's a very useful way to extract or modify sets of matrix elements corresponding to some criteria, and I use it all the time. I teach logical indexing when I give presentations on image processing in MATLAB.
But the logical indexing behavior implemented in these early MATLAB versions had a hidden dark side. Consider, for example, the expression A([1 1]) where A is a row vector. In early MATLAB, the result would be a two-element vector containing two copies of the first element of the vector. Unless ... the vector happened to have exactly two elements! In that case, the expression A([1 1]) would be treated as a logical indexing expression, and the output would be the same as A.
Here's a screen shot of MATLAB 4.2c (1994) showing the effect.
In other words, for a row vector A, A(ones(1,P)) resulted in a P-element row vector containing copies of A(1), unless A happened to have exactly P elements! Oh, that was bad. It was a bug waiting to happen in a lot of code.
We took steps to eliminate that "behavior discontinuity" in MATLAB 5.0 in 1997 by introducing the notion of a logical "attribute" of arrays. Logical operators and many appropriate functions produced outputs that were marked as logical, and only index arrays that had this logical attribute would cause logical indexing to be used.
Here's a screen shot from MATLAB 5.1 in 1997 showing this new form of logical indexing.
Notice the output of whos (there was no Workspace Browser yet). The variable b, which was the result of the expression a > 5, is shown as a double-precision matrix that is marked as logical.
This was an improvement in behavior, but there was still an issue of memory use. Double-precision is quite a "heavy" data type to be using for binary values! Nondouble data types had just been introduced in MATLAB 5.0, but hardly anyone knew about it yet. Only the Image Processing Toolbox was taking advantage of nondouble data types then. It was at this time that the Image Processing Toolbox established its convention of treating logical matrices as binary images. Before that, matrices containing only 0s and 1s were assumed to be binary, a flawed convention that was subject to a similar ambiguity as the previous form of logical indexing.
The last big change was in MATLAB 6.5 in 2002. In this version of MATLAB, logical because its own type rather than just an attribute. Here's a screen shot showing just the Command Window and the Workspace Browser.
Note how the variable b has class logical instead of double, and note how it only uses 9 bytes instead of 72.
I'll wrap up today with an almost-relevant question for you: What was your first version of MATLAB, and why did you start using it? Prove that you are a power reader and got to the end of this blog entry by posting your answer as a comment below.
It can take a lot of computational work sometimes to convert between color spaces. I was recently looking at the computational steps needed to convert between sRGB and a particular CMYK space known as US Web-coated SWOP, often just called CMYK SWOP.
The Image Processing Toolbox ships with ICC profiles corresponding to each of these spaces. If you give these profiles to makecform and applycform in order to convert sRGB color values to CMYK SWOP values, applycform will perform the following steps:
Linearize the sRGB values using the red, green, and blue tone reproduction curves.
Convert linearized RGB values to the sRGB profile connection space (XYZ) by multiplying by a matrix based on the red, green, and blue colorant tags.
Adjust the black point to compensate for the difference between the ICC version 2 profile (sRGB) and the ICC version 4 profile (CMYK SWOP). (This adjustment is a scale and an offset.)
Convert from the sRGB profile connection space (XYZ) to the CMYK SWOP profile connection space (Lab).
Scale by (257/256) to adjust ICC version 2 16-bit Lab encoding to ICC version 4 encoding.
Sometimes I'd really like to be able to go back in time and fix a few of the functional designs in the Image Processing Toolbox.
In a few cases the original design flaw is that we bundled up a little too much functionality in a single function. I'll
give you two examples: graythresh and edge.
The function graythresh uses Otsu's method to automatically determine a "good" threshold for a gray-scale image. You use it like this:
I = imread('coins.png');
imshow(I)
T = graythresh(I); % T is a normalized threshold value between 0 and 1
bw = im2bw(I, T);
imshow(bw)
The functional design flaw here is that Otsu's method doesn't really need the original image at all. It is defined solely
in terms of the histogram of the image. The first thing graythresh does is compute the histogram.
But what if you had already computed the histogram for some other purpose? There's no way to use graythresh without computing it again.
My own functional design sensibility has evolved toward writing more functions that do smaller, simpler steps. So today I
would design a function like graythresh so that it took a histogram as the input argument.
But isn't that less convenient? Yes. But I would move the "convenience" syntax elsewhere, probably to im2bw by giving it an "automatic threshold" syntax. If I could redesign im2bw together with graythresh, I would probably make the single-input syntax im2bw(I) use graythresh behind the scenes to compute the threshold automatically.
That design would be more convenient than it is today, because you could type im2bw(I) instead of im2bw(I, graythresh(I)), and it would also be more flexible because you would have access to smaller computational pieces.
The function edge has a similar problem. Several of the supported edge detection methods, such as Sobel and Roberts, use the gradient magnitude.
The gradient magnitude is computed within edge, but there's no separate toolbox function for computing it. The toolbox and MATLAB have the low-level functions and operators
that can be used to compute the gradient magnitude (fspecial, imfilter, ^2, sqrt), and the high-level function edge uses the gradient magnitude, but there's no function in the middle that conveniently computes the gradient magnitude for
you.
I mention these examples to encourage you to think about your own approach to breaking down your computations into functions.
I would also be interested to hear your opinions about what other functional designs in MATLAB and the Image Processing Toolbox
could be better. Please add your comments to this post.
Earlier this year, Perl programmer and author Mark Jason Dominus mentioned in an e-mail list that the 1974 paper "Structured Programming with go to Statements," by Donald E. Knuth, was one of his favorite computer science papers. I printed a copy and have been carrying it in my briefcase, unread, since then. I finally got a chance to read it on an airplane this week. I found it to be amazingly informative and entertaining, and I wanted to share a bit of it with you.
By the time I encountered Fortran 77 in my freshman year at Georgia Tech in 1982, the transition to structured programming was pretty much a done deal. Also, since I was in electrical engineering and not computer science, I did not learn anything at the time about the evolution of programming languages. So I was fascinated to read Knuth's perspective on the transition to structured programming, written as the transition was happening. I was also very interested to see how many themes that still concern and guide software developers today are mentioned by Knuth in this 1974 paper.
Knuth discusses in detail various techniques for eliminating go to statements in some illustrative algorithms, considering efficiency, readability, safety, etc. He looks at mechanical transformation techniques and compares proposed programming language features such as event indicators and different looping constructs. He considers a case involving multiway branching where he regards the go to as beneficial.
But his remarkable collection of asides and almost parenthetical observations fascinates me the most. Let me share a few choice bits with you.
Knuth introduces his paper with three quotes:
You may go when you will go, And I will stay behind. —Edna St. Vincent Millay
Most likely you go your way and I'll go mine. —Song title by Bob Dylan
Do you suffer from painful elimination? —Advertisement, J. B. Williams Co.
Knuth on the sometimes heated nature of the go to discussions:
In fact, the discussion has apparently caused some people to feel threatened; Dijkstra once told me that he actually received "a torrent of abusive letters" after publication of his article.
I was curiously comforted to discover that even legendary programmers can have trouble adjusting to new ideas:
I remember feeling frustrated on several occasions, at not seeing how to write programs in the new style; I would run to Bob Floyd's office asking for help, and he usually showed me what to do.
Knuth on some proposed alternatives to go to that don't really change anything:
Other go to-less languages for system programming have similarly introduced other statements which provide "equally powerful" alternative ways to jump. In other words, it seems that there is widespread agreement that go to statements are harmful, yet programmers and language designers still feel the need for some euphemism that "goes to" without saying go to.
Knuth's famous quote about premature optimization in context:
There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.
On avoiding code duplication:
[Copying common code] would be a pointless waste of energy just to eliminate a perfectly understandable go to statement: the resulting program would actually be harder to maintain than the former, since the action of printing a character now appears in two difference places.
On a pitfall of code comments:
Accompanying comments explain the program, [but] it is easy to make mistakes, partly because we rely so much on comments which might possibly be inaccurate descriptions of what the program really does.
Skepticism of quantitative metrics:
But there has been far too much emphasis on go to elimination instead of the really important issues; people have a natural tendency to set up an easily understood quantitative goal like the abolishment of jumps, instead of working directly for a qualitative goal like good program structure.
Programming puns about the 1960s:
I discussed [a] weakness of ALGOL in a letter to Niklaus Wirth in 1967, and he proposed two solutions to the problem, together with many other instructive ideas in an unpublished report on basic concepts of programming languages. His first suggestion was to write repeat begin S; when B exit; T; end
and readers who remember 1967 will also appreciate his second suggestion, turn on begin S; when B drop out; T; end
On teaching programming:
I have always felt that the transformation from recursion to iteration is one of the most fundamental concepts of computer science, and that a student should learn about it at about the same time he is studying data structures. [...] It surprises me that the literature on recursion removal is primarily concerned with "baby" examples like computing factorials or reversing lists [...]
On table-driven logic:
Multiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if tests. Peter Naur recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have discovered.
On flowcharts:
As an undergraduate, in 1959, I published an octopus flowchart which I sincerely hope is the most horribly complicated that will ever appear in print; anyone who believes that flowcharts are the best way to understand program flow is urged to look at this example.
And finally, I learned that the joke about using come from instead of go to dates back to at least R. Lawrence Clark in 1973.
I'm sorry to have disappeared off the blogging map the last couple of weeks. I got involved in some projects that needed many
hours of uninterrupted, focused time, which somehow doesn't mesh well with keeping up with the blog. ;-)
There have been several cases in the past when we have moved Image Processing Toolbox functionality into MATLAB.
The first case was the image file reading and writing functions. When Image Processing Toolbox version 1.0 shipped in 1993,
it included several pairs of functions for reading and writing image formats: tiffread, tiffwrite, bmpread, bmpwrite, etc. Pretty soon, users started complaining that we were charging them for a toolbox when all they wanted to do was read
or write a TIFF file. So we decided to move the functionality into MATLAB. Based on our experience with the original functions,
we also decided to present the functionality with redesigned interfaces. For example, we learned that it was frequently useful
to be able to read the metadata from an image file without actually reading the image pixels. The new image I/O functions
were imread, imwrite, and imfinfo, and they shipped with MATLAB 5.0 in 1997.
A simpler MATLAB move, similar to what Stephen is suggesting for padarray, happened a little bit later with circshift. This is one of the earliest cases I can remember where an Image Processing Toolbox function moved without modification
into MATLAB. In this case, the first opportunity to ship the function was in a toolbox release, but it was written with the
idea that it might go into MATLAB at some point.
The Image Processing Toolbox function ind2rgb moved into MATLAB a year or two after MATLAB 5.0. The driving factor here was the newly added ability to put image data
onto user interface buttons in Handle Graphics. Users would read an indexed image from an indexed image file, for example,
but then get stuck because the button wouldn't take the image data in indexed form.
The function rgb2ind eventually found its way from the toolbox into MATLAB also, but not until the R2009a release earlier this year. This change
was motivated in part by the reintroduction of GIF format support a couple of years ago. Users wanted to write GIF files,
but the GIF format supports only indexed images, and MATLAB users without the Image Processing Toolbox found it difficult
to convert their truecolor images to indexed form.
Moving rgb2ind was actually a fairly complicated move. Conversion to indexed format is a complex calculation, and rgb2ind called several other Image Processing Toolbox functions to do portions of the work. So all of these functions moved over
to MATLAB together with rgb2ind.
I wrote the original version of padarray and figured it might be a candidate for moving into MATLAB at some point. I can't really say for sure, though, whether and
when that might happen. Such a function move affects product tests, reference pages, release notes, and so it requires coordination
from several people and maybe a day or two of person-time. I suspect also that the current implementation may have some dependencies
on other Image Processing Toolbox utility functions, so these dependencies would need to be resolved. It's not a huge amount
of time, but then we never seem to have enough time to do everything we want to do with the product.
Anyway, thanks again, Stephen, for the suggestion.
Earlier this week I wrote about the lists I keep of MATLAB and Image Processing Toolbox changes that might be relevant to the material in Digital Image Processing Using MATLAB. I've been keeping these lists since we published the first edition, so they cover about five and a half years of software evolution.
I posted my MATLAB lists on Monday. Today I'm posting my Image Processing Toolbox lists. Note that these lists are not comprehensive; I noted only those items that I thought might be relevant to what's in the book.
As before, my challenge to readers is to find the oldest "new" feature you didn't know about before, preferably something that might be useful in your work. Let us know what you found by commenting on this post.
Version 3.1
New function stretchlim - computes "nice" limits for use with imadjust
Version 3.2
imfill - no longer requires the 'holes' argument for grayscale images
Version 4.0
imview - new image display and navigation - superseded by imtool in version 5.0
overview window
pixel region tool
magnification control
Import ICC color profiles
Support for XYZ, xyY, uvL, u'v'L, L*a*b*, L*ch, sRGB color spaces
adapthisteq - adaptive histogram equalization - works much better than histeq as an "all-purpose" image enhancement tool
decorrstretch - decorrelation stretch
fanbeam geometry for projections and inverse projections
bwboundaries (boundary tracing)
bwtraceboundary
uintlut - superseded by intlut in version 5.0
Version 4.1
Reading and writing L*a*b* data in TIFF files
Version 5.0
Modular programming with GUI components
Contrast adjustment tool, called "window-level" tool by radiologists
imdilate, imerode, imopen, imclose - substantial speed improvement for large rectangular strels; computation speed is now independent of the size of the strel
Version 5.1
Support for new medical image file formats: Analyze 7.5 and Interfile
Image Tool enhancement - new distance tool (imdistline) for measuring the distance between any two points
New GUI building blocks: impoint, imline, imrect
New ICC utility functions: iccroot and iccfind
New section in Users Guide on working with image sequences
Version 5.2
Support for additional ICC profile types: DeviceLink, ColorSpace, Abstract, Grayscale
Mouse pointer management functions for GUI programming (iptPointerManager, etc.)
Version 5.3
'symmetric' option for graycomatrix, for consistency with Haralick '73 definition.
ICC support extended to parametric curve types, and reading named colors in profiles
Version 5.4
imresize runs faster, uses less memory, supports new interpolation types, output size options, antialiasing control, user-defined interpolation kernels
applycform uses tetrahedral interpolation
watershed transform uses new algorithm (watershed section may need updated algorithm description)
'none' option for iradon for unfiltered backprojection
Version 6.0
New interactive video / image sequence viewer
Cropping added to imtool
Bayer demosaic function
Multiresolution pyramid function
New tools for building GUIs (imsave, imputfile)
New ROI tools (impoly, imellipse, imfreehand)
Support for NITF (National Imagery Transmission Format) import
Support for HDR (high dynamic range) image import
tonemap function for HDR images
Faster bwmorph
Faster imfilter for uint8 RGB images
Version 6.1 (R2008a)
Create and export high dynamic range (HDR) images
Measure grayscale properties with regionprops
Enhanced methods for ROI functions
Convert between sRGB and CMYK
ICCWRITE can create smaller files in some cases
New transformation types in cp2tform:
'similarity'
'nonreflective similarity'
Version 6.2 (R2008b)
Faster performance for:
Binary erosion and dilation
Hit-miss
Range filtering
Graycomatrix
New function cornermetric for corner detection
New createMask method for ROI functions
Version 6.3 (R2009a)
New function bwconncomp does connected components labeling using less memory
New function labelmatrix
imfilter now multithreaded
Display and navigation of very large images using R-Sets (multiresolution pyramid files) generated using new function rsetwrite
Toolbox preferences now set using MATLAB preferences panel and saved between sessions
End-point and branch-point detection added to bwmorph
Digital Image Processing Using MATLAB has three coauthors, and we are each responsible for different aspects of writing and other book-related activities. One of my responsibilities is to keep track of changes in MATLAB and Image Processing Toolbox that might affect the book. I look for new features that we might want to mention, as well as behavior changes that might affect existing text in the book.
I was looking at my lists recently and thought they might be interesting to publish here. I normally write about new features in the blog, but I do it one release at a time. We published the first edition of the book in late 2003, so looking at all of my lists gives you a birds-eye view of what's been happening in the products over a five-year period.
Today I'll post my MATLAB lists, and later in the week I'll post my Image Processing Toolbox lists. Note that these lists are not comprehensive; they contain only the items that I thought might be relevant to some topic in the book.
Here's my challenge to readers: Scan these lists and find the oldest "new" feature that you didn't already know about, preferably something that might be useful to you. Let us know about your find by commenting on this post.
Version 7.0
Single precision support
uipanels
dockable figures
array editor for viewing structures (useful in compression chapter?)
Cell mode and publishing tool
Conditional breakpoints
Directory reports (code quality issues; todo list; etc.)
M-Lint code-checker tool
Nondouble arithmetic
Single precision linear algebra
Single precision FFTs
class input for eps function
class inputs for realmax, realmin
new functions intmax, intmin
class inputs for ones, zeros, eye
class and size inputs for Inf, NaN
isfloat
isinteger
accumarray
mode argument for sort
new trig functions for inputs in degrees
new calling syntax for function handles
anonymous function handles
nested functions
isscalar
isvector
strtrim
textscan
expanded regular expression functions
bit functions on unsigned integers
compressed MAT-files
ftp functions
interactive plotting tools
data cursors
plot annotation (with MATLAB code generation)
hggroup
hgtransform
linkprop
axes OuterPosition and TightInset properties (may be useful for fine-tuning plot positioning in our book)
GUIDE changes: panels, button groups, ActiveX support, toolbar component, menu editor, key-press detection, edit-text, scroll bar, focus setting
uiwait - timeout argument
Version 7.1
new function hypot - square root of sum of squares
new function mode - most frequent values in sample
new function arrayfun - applies a given function to each element of an array. Especially useful for arrays of structures. (possibly useful with regionprops)
new function exifread - reads EXIF information from JPEG and TIFF image files
new function structfun - applies a given function to each field of a structure
new function swapbytes - swaps byte ordering
new function typecast - converts data types without changing underlying data
cellfun - modified to be able to apply a user-specified function to each element of a cell array
Plot Tools enabled on Macintosh
Time-series analysis tools
Version 7.2
New function idivide provides division similar to A./B on integers except that fractional quotients are rounded to integers according to a specified rounding mode
New features for regular expressions:
dynamic regular expressions (insertion of MATLAB expressions into regular expressions or replacement strings)
New function for generating literals
New parsing modes (case-sensitive, single-line, multiline, freespacing)
Version 7.3
New MAT-file format capable of storing data larger than 2 GB. Not on by default; must be selected
Data cursor text can be programmatically modified
Creating GUIs - details and documentation significantly updated
mwSize and mwIndex types for use in MEX-file programming
Version 7.4
Get online URL of displayed page in help browser
Create searchable database for your own toolbox's HTML help files.
bsxfun (definitely useful - may want to replace all uses of repmat in DIPUM with calls to bsxfun)
divide-by-zero and log-of-zero warnings now off by default
new function assert
new function verLessThan
new inputParser class
More GUIDE changes
Version 7.5
Help on selection (editor)
Code folding in editor - worth recapturing editor screenshots if we have any
new function maxNumCompThreads (may want to mention multithreaded computation in MATLAB intro chapter)
new 'split' option for regexp
new error handling ability - MException - plus related changes to catch
new multimedia file reader - mmreader
imread has several TIFF-related enhancements:
LZW, Deflate, and JPEG compression support
Arbitrary combinations of samples-per-pixel and bits-per-sample
Increased performance when using 'PixelRegion' parameter. (Might want to have a DIPUM example showing how to read a subset of a TIFF image.)
GUIDE changes - custom toolbar editor, icon editor, coordinate readout in layout editor, documentation on how to make GUIDE GUIs interact
Version 7.6 (R2008a)
Camera EXIF information incorporated into output from imfinfo
FFT functions no longer warn on uint8 input
Support for JPEG-2000 import
Version 7.7 (R2008b)
Find function names and get help using new function browser
View syntax hints while entering statements
New formats supported for imread:
JPEG 2000
netCDF
Version 7.8 (R2009a)
Performance improvements for low-level HDF 5 interface
Support for HDF 1.8.1
Performance improvement for JPEG 2000 import
New syntax for faster reading of TIFF files containing many images
New computational geometry classes TriRep, DelaunayTri, TriScatteredInterp
New functions now multithreaded: fft, fft2, fftn, ifft, ifft2, ifftn, prod, sum max, min
Some Image Processing Toolbox functions moved into MATLAB: rgb2ind, dither, cmunique, cmpermute, imapprox
I want to point you to Damian's second guest blog post on Loren's Art of MATLAB. Scattered data interpolation and data gridding definitely have application to multiple areas in image processing, and the related MATLAB capabilities have significantly improved in R2009a, the latest MATLAB release.
I wrote last week about new features in R2009a related to connected component labeling. There are two new functions, bwconncomp and labelmatrix, as well as additional syntaxes for an existing function, regionprops. The features were designed to reduce the amount of memory required to measure geometric properties of connected components
(objects) in binary images. In many cases the computational speed is improved as well.
We were concerned that existing users would not discover and use the new features. If users did not change their code, then
they would not benefit from the memory and speed improvements.
So we asked the MATLAB M-Lint team for help. M-Lint is the MATLAB code analysis tool that is behind those helpful suggestions
that the MATLAB Editor makes about your code. We asked the team to detect the code pattern where the output of bwlabel is passed as the first input argument to regionprops. I showed this coding pattern in Part 1. Here's what the MATLAB Editor now shows for the script is used to create Part 1:
If you hover over the underlined "L" with your mouse, a short message pops up:
And if you click on the short message, you get a full explanation of how to change your code:
As I mentioned in Part 1, the feedback of blog readers was influential in increasing the priority of this issue. I thank
you for your many comments on my previous blogs about bwlabel and regionprops.
If you get a chance to use the new features, let us know what you think by commenting on this post.
This is a "small world" story for a mid-summer Friday.
Outside work, family, and book writing, I like to play a little tournament chess. I'm just your middle-of-the-pack club player trying to get a bit better, and occasionally I work with a chess coach who goes over my games and tells me about the silly moves I make.
Well, earlier this year my wife called to tell me that my chess coach called the house and was hoping to talk to me that day. That was a bit of a puzzle, since we had no lessons scheduled. What could this be about?
When I called him back, my coach explained that he was working on an advertisement of services to be placed in the program materials for an upcoming national tournament. The printer had notified him that the graphics file he provided wasn't suitable; he needed to send a file that was "300 dpi."
My coach didn't know what that meant, so naturally he did an internet search for terms like "300 dpi." That brought him to my blog post, "Help! My publisher wants a 300 dpi TIFF." After a while, it dawned on him that this "Steve" fellow was actually his student, and he called me to see if I could help.
It made my day to be the "expert" (for a change) in one of our conversations.
Steve Eddins manages the Image & Geospatial development team at The MathWorks and coauthored Digital Image Processing Using MATLAB. He writes here about image processing concepts, algorithm implementations, and MATLAB.
Recent Comments