Math(s)! Currently: Summer of Math Exposition

Hey @Exohedron
I has a real world math issue but is not formulated in a math statement.
Has an image - 640x480
The current program is looking for a crosshair - black on a white background.
Uses the algorithm
Scan each row for black pixels - take average distance of black from left edge. If the average distance is 1/2 the width +/- 5 pixels for each row, the vertical crosshair is found.
Do similar for top-to bottom - if average distance is 1/2 the height +/- 5 pixels, the horizontal crosshair is found.

scan a digital noise image (camera feed is borked)

The program finds a crosshair that isn't there.
Two image analysis experts couldn't figure out why.

:D

 

Hmm. I'm not an image analysis expert, but that sounds really crude, and hence easy to fool. If all you're computing is averages, then you can make all sorts of funny distributions that end up with the correct averages. I don't know what kind of computation limits you have in terms of speed or memory, but you might want to compute something like a variance or something to make sure that the black pixels that are being averaged are actually all together in one place, as opposed to, say, on the borders. The average of 4 and 5 is the same as the average of 0 and 9, but the first pair has a single cluster while the second pair has two, and I don't think you want your crosshairs to have multiple clusters.

Unfortunately, my image analysis instincts just scream "neural nets!" all the time, which I'm going to guess is a bit too much computational power to throw at this problem. But I wouldn't be surprised if the "best" scheme is convolutional.

 

I'd have to see the algorithm before attempting to make definitive statements, but that seems ripe for false positives. Any row or column with a black pixel will cause it to run the average test if I understand correctly. Like @Exohedron said, average don't care about clustering. If the average is within 5 of the expected value, welp.

I'm a little confused about whether it could really be that simple if two experts didn't see it, but stranger things have happened.

Image processing is an interest of mine. I don't think the simplicity of the algorithm is a bad thing at all, but it's really important to understand exactly what an algorithm means in practical terms.

 

I guess also there's the question of what exactly you're looking for: the presence of a crosshairs, or if the image has a crosshairs and nothing else. I think presence would probably be best off with a convolutional solution so that it would ignore other stuff, but I'm not sure if there's a significantly slicker way to detect if there's only a crosshairs and nothing else.

 

Looking for "is there a crosshair". And yeah - the algorithm is THAT simplistic - so on random noise it's going to find crosshairs because random distribution will put the center of black in the center of the image, most of the time.
I was thinking of adding a "ratio of white to black" to try to weed out that sort of error.
The image "experts" are obviously not up to the task of figuring out how to fix the errors.

 

If you're sure enough about the predictability of the crosshairs to use an algorithm that expects to find them centered within five pixels of the center of the image, why not limit the search to that area? It would save a lot of processing and time, particularly if you can reduce iteration down columns, which requires jumping around nonsequentially through memory

 

Well, the original problem is to FIND the crosshairs. The test that the search would work used them already centered. The problem appeared when the camera was broken and still finding crosshairs. Now we need to at least detect the difference between noise and image

 

Okay, so we're not assuming you know where the crosshairs are, or if there even is a crosshairs in the image. Are we trying to detect mere presence or are we trying to count crosshairs? Are you more concerned with false positives or false negatives?
What constitutes a valid crosshairs? For instance, if I have a 5x5 grid of pixels with the middle row and the middle column all black, and the four corners black, and the rest white, is that a valid crosshairs, despite the corners being filled in? How much wiggle room does "crosshairs" have?

 

We have a specific device with a crosshair etched into it. It is used to align the camera. We know how big the crosshair should be. So the first step was to detect where the crosshair is. We put it in the center and ran the test that a developer (no longer with the company) wrote and it seemed good. Then someone noticed the wire to the camera was broken so we put the image on the screen and it was random noise and still showing success. So now I'm trying to figure out a way to know when it is noise vs an actual image.

 

Ah, so first you want to figure out if you're actually looking at something that should have a crosshair in it at all, and then once you've figured that out, you want to find the crosshair in the image?
If the camera is on and working, will the image be very clean? Or will there still be a fair bit of noise?
If it's clean I can imagine maybe some sort of edge-detection system that looks for "white, white, ..., white, black, black, ..., black, white, white, ..., white" of the correct numbers as it scans along a row to find candidates for the crosshair, and then tests those candidates by looking for the rest of the crosshair. If it's somewhat noisy then we'll have to be a bit more robust about it, maybe searching for strings of pixels with high and low white density instead of strings of white and black.

 

Somewhat noisy but WAY cleaner than random

 

I has fixed it so random or near-random noise is caught early. Search for circles - if none or more than one is found, the image is either noise or not the thing we are looking for - don't bother looking for crosshairs. Random noise will produce artifacts that appear to be circles to the image library we are using.
We still have the issue of the crosshairs being "found" because the code is looking for "centroids" - from the comments it seems they are looking for "the center of mass of blackness" and not considering distribution - is it all close to the center or relatively scattered. So a greyscale image with no crosshair still finds one. That part surprises me because the circle in one corner should unbalance the results. I suspect the "centroid" algorithm is either the wrong thing to use or was not coded correctly.

 

I'm pretty sure the centroid is not the right thing to look for unless your data is super clean. Otherwise you're going to be triggering on everything, not just a crosshair.

 

I is not a math expert (is why I started this part of the discussion :) ). I isn't even an image expert (I make images, I doesn't analyze them). So -
I has been authorized to "look into a better way to do this".
The images are captured from a camera looking through a microscope - there is noise what probably amounts to 5-10 % just because of hardware. The target is an etched object that is mostly white, but may have scarring due to peoples accidently burning it with the laser (they forgot the test fixture was in place when they ran a test burn). The burns are about 25% darker than the target's normal white area. Ambient lights make the whole thing appear yellowish, so on the greyscale capture it is NEVER white/black, it is noisy.
My theory is that if I can find the center of black per section (like the top half of the image when looking for the top section of the crosshair) AND find the distribution of black in that section (is it all centered or all over the place) I can tell where the line is for that piece or there is just junk - black dots scattered randomly may have a center but it's irrelevent - they needs to be close to each other.
I has a brute force approach in mind for it, but I suspect there is a mathematical way of analyzing the data to get a distribution value I could use.

 

Hmm. Those noise sources make things a little tricky. How much computational power are you willing to spend? Like, my first thought is to literally test every possible position for the crosshair one by one, but that requires going over each pixel a bunch of times (as many times as there are pixels in the crosshair), which may be too much work depending on how the image is stored.
If the yellow is pretty uniform then that shouldn't be a problem; just isolate the yellow channel, or the red or green channels if you're working in RGB. Really you're only concerned about black versus not-black, not so much black versus white.
Just for scale, how big is the crossahir in pixels? And is it completely black or just somewhat black?

 

Trying to do this in as few passes as possible because the user is constantly tweaking the position of the camera to get the crosshair centered, so we is rescanning a lot. The cameras give us the image in greyscale (they get it in RGB but the library that controls the hardware converts it to grey before we get it). The crosshair line are about 10 pixels wide but not guaranteed - one of the things we are looking for is if the black paint on the etched lines is scraped off we invalidate the calibration and tell them to check the alignment tool and camera (in case the line is there but the camera isn't seeing it). When it is good the contrast between crosshair and not-crosshair is pretty high. So yeah, it's "black vs not-black". We can check by section - so looking for the top verticle of the crosshair we don't look at the whole image, just the top half. Same for bottom, left, and right. So I am thinking we could scan for black and find where teh center of black is, then check for distribution of black (so if it is all over the place, it's not really valid, but if it is strongly associated with the center than we can think it is really the line).

 

I has found what I need - the HoughLines function in OpenCV! And it looks like it can work in a single pass instead of the weird "checking quadrants" mechanism the old code was using.

 

It is finding the lines! I had to use a bit of other stuff to clean up the image (Canny, dilate/erode, etc) but I now has lines I can find and check for being somewhat verticle and horizontal and see if they are strong enough to count as being the crosshair. I was able to isolate the crosshair on the alignment tool even after it had been burned by the laser, so I is on the right track.

 

I'm going to throw a puzzle here and see if anyone can get it (and of course I'll explain it at some point later): what does the SVG image below represent?

 

I'm going to guess the outer automorphisms of S6