How would I tackle such a problem??? (Programmers, smart peoples I need ya!)

[zveruga]

I need to automate a job. The job is as follows:
The Setup: I am presented with various pictures. Lets assume the pictures are in some picture format, and I can use Photoshop to save them as any type of file that I want. Each picture contains a thick contiguous line, with small follicles coming off of it at various points. Think of a highway with roads branching out, or a tree with branches (but no sub-branches), or even a vein with little capillaries coming off of it.
The Constraints: Since the pictures are likely to be scanned or enlarged, or contain imperfections -- they will not be purely b/w, but will have shades of grey. Also, the branches DO NOT branch out further, and there is no need to count beyond the main stem. Finally, the main stem is visibly and clearly the thickest, and possibly the darkest of all lines present in the picture.
The Goal: To automatically tell the number of branches coming off the main stem, with a margin of error +-20% (but the less error the better).
Why: There are either too many branches to count manually, they are too tiny, or there are way too many such pictures to do it manually in a reasonable amount of time.

How would I tackle this task? I am thinking of various approaches...

1) Using a pre-existing application to analyze the branches in the picture. Does such application exist? For example, MicroStation can draw coordinates visually. But I need to do this in reverse -- to analyze a picture as data.
2) Using a pre-existing application to get rid of the "noise" in the picture, keeping only the largest contiguous object within the field.
3) Writing a program to do #1 or #2 myself. For this I need the following question answered: How do I convert a picture to data? Obviously, most formats use some form of compression to store pixel info. I need to find a decompressed format, or write a program to decompress it. Then i need to be able to interpret the data for every pixel -- color and location.
4) Perhaps I am overcomplicating things and there is an easier way to do this. Remember: The key is doing it simply, not necessarily doing it automatically all the way.

Thanks all.

 

[singh]

A sample picture would be of great help

 

[Matthias99]

Sample pictures would be helpful, I agree. As I'm thinking about this, the most important consideration is how *consistent* the pictures are going to be. Is the "main branch" always going, say, horizontally across the middle of the picture (or close to that)? Or do you have to be able to deal with crooked/diagonal/vertical/curved lines as well? Also, can you easily convert them to mochrome black/white only (using Photoshop filters, etc.)? Or is the resolution too low for that?

As far as getting the pictures in a simple format, Photoshop should be able to save your files in one of several uncompressed formats, such as BMP or TARGA. There are also libraries available that will read in, say, JPEG-compressed files and allow you to read and manipulate the pixel data in a high-level language like C++ or Java.

The more automated pre-processing you can do (and the more successful it is), the better any sort of algorithm will be able to work. Photoshop and other professional image editing software is good for this sort of thing.

 

[CTho9305]

Post a sample. I would think you'd do a flood fill algorithm with some threshold to detect edges, then check for branches by looking for points that are concave (you can do that by drawing lines from points within the filled region to other points).

 

[zveruga]

Ok, time to drop the air of mystery and explain what this is really for.

I am working toward my psychology degree, and I am currently working in a rat psychology research lab. We are looking at dendrites, and counting the little spines that come off them. SO, since we are looking at brain tissue, the dendrites will be going in any direction. But they are very thick and easily stand out from anything else in the picture, and can also be very easily isolated with crop functions in Photoshop. However, counting the spines, or little hairs that come off the main dendrite stem is a real pain. There are many of them, and very very tiny. Thats why I think a program would do a better job of counting them than manual approach. And its a whole lot easier too.

I will get you guys a sample of the picture as soon as I figure out how to transfer the picture from the Microscope to the PC (possible, just need the manual).

There arent any programmers in the lab, but I think i can figure out how to write one -- ill probably do it in Perl tho, its inefficient but I feel more comfortable with that language. Most important is to understand the algorithms needed to do this. Remember guys, if the program misses a spine or 2 no big deal. As long as it gives a roughly good estimate of how many spines each dendrite has, we are in business.

I also appreciate frank commentary if it is just too difficult to be done.

 

[DrPizza]

edit: Since this is a research project, I'd like to add that you may freely use the ideas I have expressed here for non-commercial use only. Should these ideas be incorporated into a commercial or proprietary product, permission must be sought from me (and probably $$$ to me) for use of these ideas.

Just a quick thought off the top of my head, but if you could get the computer to understand where the main stem is (and I don't think that would be hard), Calculate a function for a line across the picture representing the main stem (or if it's not straight, you could get even more sophisticated with curve fitting functions).

Then, on two imaginary lines (or curves) parallel to the main stem, each time the darkness increases (to darker gray, or whatever), increase your count by 1, then don't increase again until the darkness decreases. After it decreases, then after it increases again, increase the count by another 1.

 

[DrPizza]

Thought about it for a moment... getting the computer to recognize the main stem: (and I didn't mention in the previous post, consider the picture to be a 2 dimensional array of data points, like a 1st quadrant graph, with x values >=0 and y values >=0)

Either sample all of the data points, or every other or every 3rd, or... (consideration for computing time)
For all of the darkest points (x,y), do a linear regression (find the best fit line). Or, do a weighted average based on the darkness of the points. So, on a 0 to 16 scale, black being 16, darkest gray 15, etc. If the point is a 15 for darkness, weight it 15. If it's a 2, weight it 2.

 

[zveruga]

best fit line to find the main stem is actually a GREAT idea...
I could probably get the algorithm from any stats book.

YES this is absolutely non-commercial, unprofessional, just trying to get the job done. And if I didn't mention it yet, I am not getting paid for the lab work!

 

[Geniere]

It seem's software already exists which can be adapted for your purpose. I did a Google search for "pixel detection software", and some of the hits looked good.

 

[Wiktor]

I think Image-Pro plus is exactly what you're looking for.
We used the demo version of this app. and I know it can do things like count spots on a microscopic photo of tissue.
See if it can help you.

 

[kevinthenerd]

Originally posted by: zveruga
I need to find a decompressed format, or write a program to decompress it. Then i need to be able to interpret the data for every pixel -- color and location.

Good ole' bitmap will do the job. It's a simple format. The addressing, if I understand it correctly, goes something like this:

address = header + width*y + x

 

[zveruga]

Guys I didn't understand the problem fully and apologize for that. Although we do have a copy of image pro plus,it will do little good -- because a single image doesn't capture the details that are needed. When manually examining the slide, focus of the microscope needs to be constantly changed in order to see everything. A snap shot of an "average" focus won't work. Its probably easier to do this manually. Thanks anyway!

 

[DrPizza]

Oh, in that case, there are 3 easy steps to doing that problem.
1. Get doctorate
2. Get hired by a University
3. Hire grad students to do all the counting for you.