LabVIEW
two bugs in IMAQ Correlate
I've learned to accept that NI Vision has more bugs than a Department of Homeland Security cocktail party, but the joy of simultaneously discovering two bugs in the same VI is something that I'm not sure words can adequately describe. Not the kind of words they allow me to post on the LabVIEW support forum anyhow.
The good news- IMAQ correlate works great unless you use the "optional rectangle" that allows the user to define a processing window smaller than the source image.
The bad news- I'm not sure what country the NI Vision programming team hails from, but I’m certain that in their native tongue, "optional rectangle" translates roughly to "self destruct."
With the attached VI, IMAQ correlate takes about 60ms to generate a normalized correlation map with a 316 by 316 template on a 316 by 316 source image on my computer. Not bad at all. So being naive, I think to myself that I'll press my luck and use the optional rectangle to eliminate the bulk of the unnecessary calculations that are being performed, since I only need the center of the correlation map. I should know better by now.
bug #1: Reducing the processing area drastically increases the amount of computation time on my computer. Feel free to run the attached VI and use the enumeration control to select various correlation window sizes. The image on the right shows the source image with the overlaid correlation window in red (nothing is overlaid if full size window is selected.) These are the results I get:
100000 pixel correlation map ==> 60 ms
10000 pixel correlation map ==> 2440 ms
4000 pixel correlation map ==> 246 ms
1000 pixel correlztion map ==> 100 ms
100 pixel correlation map ==> 32 ms
Right. So to sum up, performing 1/10 of the calculation only takes roughly 40 times as long as just doing the whole thing. Nicely done, bizarro, evil twin, parallel universe programming team. Your hilarious programming shenanigans have given me a brain aneurism that I’ll be enjoying for weeks.
bug #2: If the portion of the image that corresponds to the processing window contains all zeros, the correlation map will always be all zeros. I know, I know, you're thinking "oh, silly root, that's how correlation is supposed to work." Wrong!
Run the vi and make sure that “add a center dot” is toggled ON and “blank out pattern” is toggled to OFF. Set the correlation window size to “full size” and you'll see a pretty, happy pattern that is, in fact, the proper normalized correlation map of the template image and source image. Note that the source image has a single dot in the center. Now toggle “blank out pattern” ON. You’ll see that the proper correlation map for an image of a dot is, in fact, a dot. Select the 1/250 window with and toggle “blank out pattern” OFF and ON. you’ll see that the correlation map still corresponds to the pattern you see when viewing the full correlation map, you’re just seeing a smaller processing window.
Now with the correlation window size set to 1/250, toggle “blank out pattern” to OFF and toggle “add a center dot” OFF and ON. You’ll see that you don’t get jack squat if the correlation processing window is small, even though if you turn the center dot back on, you can see the interesting symmetrical pattern that corresponds to a correlation done using the entire source image pattern and entire template pattern over the specified processing region, as it should be. I suspect that the reason that it goes blank when you turn off the dot is that code to normalize the correlation map is screwy. Again, nice job. I was planning on having a mental breakdown and tearing patches of my hair out anyway.
I should make it clear that I don’t mean to imply that I think that there are only two bugs in this particular vi, I just thought I might as well add them both to my expansive entomology collection as I merrily skip through the plague of locusts.
If anyone already has a normalized correlation .dll, please post a link, otherwise I’ll post whatever our code monkeys come up with so long as they manage to properly optimize it.
Happy programming,
-root
Looks like the slowdown issue is a problem with memory allocation inside IMAQ correlate. A template image that is slightly smaller than the optional processing window works fine, but a template image that is even slightly larger than the optional processing window causes an incredible slowdown. Looks like you guys are making an invalid assumption that the template window will be smaller than the processing window; when it's not, you have to reallocate memory the same number of times as there are pixels in the operating window. You need to compare the template image size to the optional processing window size before allocating memory space.
I can think of plenty of reasons why one may want to perform a correlation over a processing window that is smaller than the template kernel. For instance, pyramidal pattern matching. I mention this technique specifically because you describe it in gory detail in your vision concept manual under the pattern matching techniques.
I do not see a detailed description of the precise mechanism by which your IMAQ pattern match vi works, but judging from the advanced pattern match function inputs, it looks like you use a multitiered correlation approach with the final stage operating over a small match window using a large template. If I were you, I would look carefully over my code for IMAQ pattern match and make darned sure that you aren't making the same memory allocation mistake in the final stages of match refinement, when you will be using normalized cross correlation to register a relatively large pattern template over a small potential match area. If the same problem is present in IMAQ pattern match (frankly, I don't see why it wouldn't be unless you had two separate development teams write two separate normalized cross correlation routines), then you can also increase the speed of IMAQ pattern match by fixing the bug in your normalized cross correlation routine.
At the risk of being both impolite and impatient, I'd like to point out that I've both paid for this software and taken the time to isolate the specific problem behavior at this point, and I'd like to ask you to please promptly resolve this issue and post a link to he repaired call library function once you've got it working.
-root
Right, so I wasn’t reporting that I thought correlate shouldn’t be “searching outside” of the search window. Yes, correlation should be searching outside of the edges of the search window. I was reporting that the correlation goes jet black if the portion of the source image corresponding to the search window contains all zeros even if the correlation should not be jet black because correlation applies the template outside of the search window, just like you said. I even took the time to write a program specifically to demonstrate this problem to you, because that’s how I roll. Please go back to the original post, open the vi, and follow the instructions and you will see that the correlation is good when you have the center dot turned on in the image, but goes jet black when you turn off the center dot, even though the correlation pattern returned comes mostly from features in the area outside the small search window because of the large template, just like we both agree that it should.
It should not go black when you turn off the center dot. This is a bug.
As far as it being difficult to conceive of anyone being insane enough to want to perform a correlation over a small processing region with a larger template, I admit that I am, in fact, completely crazy. But just for fun, let’s briefly entertain the inconceivably preposterous notion anyway. Take as an example the pyramidal matching technique described just under the section on normalized cross correlation in the official National Instruments Vision Concepts Manual.
In my copy it’s on page 12-5.
“Pyramidal Matching
You can improve the computation time of pattern matching by reducing the
size of the image and the template. In pyramidal matching, both the image
and the template are sampled to smaller spatial resolutions. For instance, by
sampling every other pixel, the image and the template can be reduced
to one-fourth of their original sizes. Matching is performed first on the
reduced images. Because the images are smaller, matching is faster.
When matching is complete, only areas with high match scores need to
be considered as matching areas in the original image.”
- National Instruments Corporation, July 2007
If I’ve narrowed down the search area to a tiny portion of the image, then it is entirely conceivable that the refined search window will be smaller than the template. Using the technique that National Instruments suggests above, the IMAQ Correlate function in LabVIEW explodes and takes a thousand times longer to compute the correlation than searching over a larger window would because of an undocumented condition that must be met to prevent a slowdown of two or three orders of magnitude.
For example; say I have a 1000 by 1000 image and I’ve got a 100 by 100 search pattern template. Instead of searching over a big, high resolution area, I reduce the resolution of both the image and the template by a factor of ten, then I search over the resampled 100 by 100 image with a resampled 10 by 10 template. I see one really bright pixel in the correlation map- “aha!” I say to myself (sometimes I talk to myself), “now I know the location of the match in the full resolution image within a ten by ten window that corresponds to that bright pixel! I’ll search over that section for the exact match!! Wheeeeeeee! When I search over the 10 by 10 pixel search window with the 100 by 100 template, the power grid fails.
I’m guessing that the “we” you refer to who “couldn’t think of any cases” where the template would need to be larger than the search area isn’t the same “we” who wrote the portion of the Labview Vision Concepts manual that suggests doing exactly that.
continued below-
-cont.
Now allow me to answer your question about my particular application. I have video where the camera is slewing around a little horizontally or vertically and I’m taking successive frames and translating them so that they line back up with each other. Exactly like digital image stabilization, but only ever with two frames at a time.
IMAQ match pattern is fast, but with high res images IMAQ learn pattern is a bit too sluggish to make us dance merrily and sing happy songs. Geometric pattern matching is simply not a good choice of technique to use for a general purpose matching technique on random video of weird, random scenery.
So, I came up with a fairly robust technique to extract invariant features from random scenes, and we use 2D correlation to match a constellation of features up between frames and viola! It works like a charm.
Thing is, I don’t need correlation performed over the whole frame, because the camera has a maximum slew rate of something like ten pixels a second. So we can cut down the computation time in a really big way by just searching over a 20 by 20 processing ("search" ) window for each feature, even though the feature template might be larger than that. At this point I noticed the two bugs.
-root
Thanks.
Frankly, the code you've got seems well optimized excluding the slowdown when an oversized template is used. I wouldn't be disappointed if it turns out that the best remedy is to simply make sure that the actual region of operation during calculation is at least as large as the template map plus border. If R&D can find a clever way to make normalized cross correlation with a large template and a small search window faster than a large template with an equal search window, then all the better.
What about the bug that causes the correlation map to go black?
thanks again,
-root
