Steve on Image ProcessingNovember 19th, 2007Classification of operationsIn image processing textbooks, you often see low-level image processing operations grouped into two categories:
In a point process, the value of each output pixel is a function of only the corresponding input pixel. Examples include adding a constant to all image pixels and gamma correction. In a neighborhood process, the value of each output pixel is a function of the corresponding input pixel and a fixed set of neighborhood pixels around it. For example, filtering with a 3-by-3 filter is a neighborhood process. Each output pixel depends on the values of the corresponding input pixel, as well as that pixel's eight neighbors. Dilation is another example of a neighborhood process. Here are two more types of operations that I've found to be common:
Lots of operations have the word transform in them, such as Fourier transform, Hough transform, and geometric or spatial transform. But it's a little hard to define what makes something a transform. I think transforms tend to have these characteristics in common:
I'm hoping to find a better term for queue processes, but that's the best I've come up with so far. A queue process works by "spreading out" in some fashion from a set of starting pixels. I use the word "queue" here because implementations often involve a queue data structure, like this:
% Initialize the queue
for each pixel p in image:
if p satisfies some condition
push p onto queue
end if
end for
while queue not empty
get next pixel k from queue
record something about k in the output image
for each neighbor pixel j of pixel k
if j satisfies some condition
push j onto queue
end if
end for
end while
"Flood filling," which many of you can probably visualize, can be implemented this way. There are several algorithms in the Image Processing Toolbox that use queues in this fashion, including morphological reconstruction (imreconstruct) and the watershed transform (watershed). I have three questions for you:
Post your thoughts as a comment. 24 Responses to “Classification of operations”Leave a Reply |
|
|||
|
These postings are the author's and don't necessarily represent the opinions of The MathWorks. |
Even the point process can be viewed as a neighborhood operator, such as a 3×3 mask with number in the center and the others are zeros. Even scaling and offsets can be a 3×3 mask if the center operator is a Ax+b, where x== pixel value and A==scale factor, b== constant offset.
Tom
Dr. Tom—I agree with you, sort of. But both from a conceptual as well as an implementation point of view, it is very useful to distinguish between point and neighborhood processes.
“queue” process: why not “iterative” process?
In some sense, they may also be considered recursive (and often they are beautifully implemented as recursive functions), but I think that calling them “recursive processes” is misleading.
I have heard “seeded algorithm”, a counterpart to your “queue process” as it describes the first loop, but it does not sound much better.
I am not quite sure, but Luc Vincent always refers to morphological operations. So what about “morphological processes” instead queue processes.
I like “marching processes,” but for the fact that “marching” might imply something more uni-directional than intended. How about “progressive transforms,” or “wavefront transforms”?
Wolfgang—Morphological operations includes some neighborhood operations as well. In fact, the most basic morphological operations are dilation and erosion, which are both neighborhood operations.
Brett—”Marching” and “wavefront” are both interesting ideas.
Thinking about the queue process naming… I’m reading it as if the neighborhood is defined as one parses the queue and so the valid region seems to spread through the image — how about calling it “urban sprawl”. :)
Dave S—It was hard to explain to my wife what I was laughing about. :-)
on steve’s image processing dictionary:
good questions, steve.
i always thought ‘batch processing’ was a bit more intuitive than ‘queue processing’
it would clearly describe the first part of your second loop: record something about k in the output image (this could be any of the other processing methods - including another queue…).
if there IS an inner loop in your second one, which may or may not be necessary, one would use the term ‘iterative batch processing’… until the queue is empty.
re the term img ‘transformation’: i tend to think of it as ‘mapping’ in(to) another domain.
just some thoughts
urs
I think transforms generally are functions that have as input and output other functions. (For example the derivative could also be called a transform ).
What you are referring to as a “queue process” is
a “breadth-first search” through the 2-D array
of pixels. The queue simply schedules the operations,
which for your example (e.g., flood filling) spread
out from the seed pixel. If the word “search”
doesn’t seem general enough, you could call it
a “breadth-first process.”
As for distinguishing between “transforms”, “operations”,
“processing” and “filters”, I would prepend “image”
as an adjective, and divide them up as follows:
image processing and image filtering:
image –> image
examples: morphological filtering, convolution
image transform:
image –> (some other representation)
examples: hough transform, fourier transform,
wavelet transform
image operation:
image –> whatever
— Dan
Dan—I like your “search” suggestion. I’d probably use the more generic “search process” instead of “bread-first search process,” as some operations can be implemented just as well with a stack (depth-first search).
I was suggesting that for a general process scheduled by a
queue (fifo), you could call it a “breadth-first process”.
Similarly for one scheduled by a stack, you could
call it a “depth-first process”. Using “breadth-first”
instead of “queue” is more generic, because it is not
tied to a specific implementation. Using “search”
instead of “breadth-first” seems to overemphasize one
set of CS problems that, at least in its intent, is very
different from a flood fill (for example).
Dan—I believe I understand your point. But some algorithms, including flood-filling, can be performed using either a depth-first or a breadth-first process.
The best term is “breadth-first traversal” or “breadth-first search”. The terms are basically equivalent as far as fundamental algorithms are concerned, but the latter is more specific to a “search”. The former is more generic, and applies to this problem.
See http://en.wikipedia.org/wiki/Breadth-first_search
See also: Tarjan, R. E. “Depth-First Search and Linear Graph Algorithms.” SIAM J. Comput. 1, 146-160, 1972.
You could also say “depth-first traversal” (or “depth-first search”) if you just replace the word “queue” with “stack”, and the word “get” with “pop” in your algorithm.
I would stick with an established term like these four (breadth/depth-first traversal/search). They’ve been in use a long time (early 70’s at least). No need to make up a new term; it would just confuse people.
“Queue process” doesn’t extend to the depth-first traversal. It’s a little too generic of a term, as well, since queues can be used for all sorts of things, not just breadth-first traversals.
The term “iterative process” is either far too generic (is it any algorithm with a for loop?) or too specific (is it conjugate gradients for solving Ax=b?).
“recursive process” is also problematic; this is not a recursive algorithm (although it can be written as such).
I prefer “traversal” instead of “search” but the latter is more commonly used. And I see from Steve’s comments #13 and #15 that he’d probably prefer “traversal” to “search” too.
There is alternative term. The breadth/depth first traversal/search terms (all 4 of them) are refering to how to traverse the nodes of the graph (or pixels of your image, where each pixel is a node and there is an edge between two pixels i and j if they satisfy some condition).
What you are really talking about are methods that operate on connected components of a graph (or image). The term “connected components” is a structural term, not refering to exactly how you find them, what you do with them and so on. So it’s not tied to a particular algorithm, but instead to what you want to do with your image (or graph).
Both kinds (and others…) of traversals/searches can be used to find connected components. They just differ in the order that they explore the nodes (pixels) of the graph (image).
So you could refer to algorithms, methods, transforms, or whatever that operate on the connected components of an image (or graph) as a “connected component method”.
That term is also a helpful reminder that if you can precompute the graph the expresses the relationship between pixels (rather than constructing it on the fly when looking at 2 pixels), then you can just use dmperm.
So you could call this a “dmperm-based method” or more generically a “connected component method”.
“connected components” is also a well-established term. It’s much better to use a well-established term (if it applies) than invent a new one.
Tim—I agree and disagree. :-) I didn’t really like “queue-based” either. That’s why I posed the question. Neither “queue” nor “bread-first search” adequately captures the common implementation patterns I have seen. Connected components is both too general and not applicable (in some cases). I’m not trying to make up new terms; I’m just looking for one that applies well. I do like “traversal.” It works better than “search.”
it seems quite obvious now that my remarks were never worth a reply… i’m sorry for having bothered you all
Urs—I did not reply to you because I thought your thoughtful remarks stood just fine on their own and did not need a reply. I had nothing to add to them, and you did not ask a question that seemed to require a response.
Thanks, Steve … as always you’re a great source for Helpful Updates to MATLAB Operational User Resources (read that one as an acronym) … :-)
On a more serious note … if the pixel relationship is static (well-defined when the “search” or “traversal” starts), then “traversal” of the image/graph is a good term.
If the pixel relationship changes “with time” or “during the traversal”, then “traversal” doesn’t really fit (nor does “search”), since “breadth-first traversal” doesn’t envisage the graph changing as you look at it. Neither does “connected components” since things are changing and thus the components are not “fixed”.
Which one is more typical?
Tim—I think static pixel relationships is the more typical case.
Steve, Tim, I do think ‘recursive’ is the right name for this type of algorithm. You apply an operation to one pixel, then in turn to each of its neighbors, then to their neighbors, etc. Classic recursion. “Search” is not a good term because you’re not necessarily searching for anything. “Traversal” is not a good term either, because you can only build the tree as you are applying the operations to the nodes. You don’t always know a priori the order in which you will process the pixels. And sometimes you can visit nodes more than once. For example, when computing a geodesic distance you’d use a recursive algorithm (implemented with a queue, of course!) that will probably visit some pixels a few times, updating the distance.
Urs, I don’t really understand your suggestion for ‘batch processing’. I associate that term with applying the same operation to each item in a set, without the neighborhood relationship and ordering implied by the recursive operations.
That said, Steve’s ‘queue processes’ must be a subdivision of ‘neighborhood processes’. So now we have:
- recursive operations
- spatial filters
Am I missing something?
Chris—Makes sense to me. Thanks for your comment.