🔒 Locked

Algorithm to determine whether bubble is marked or not?

Started by cvbeginner May 26, 2012 at 7:02 PM 9 replies 2k views

Original Post

May 26, 2012 at 7:02 PM

Hello everyone! This is my first time using the forum, so please forgive me for any mistakes I might make!

Over the past few months, I have been working on an algorithm with these specifications:
input: image of a bubble and some buffer space around it (in 8bpp grayscale)
output: true if the bubble is marked, false otherwise

false: [sharedmedia=core:attachments:9038][sharedmedia=core:attachments:9036][sharedmedia=core:attachments:9035]
true: [sharedmedia=core:attachments:9033][sharedmedia=core:attachments:9034][sharedmedia=core:attachments:9032]
also true: [sharedmedia=core:attachments:9037]

I have tried a lot of different methods, such as:
[font=arial]1. Color method: taking the average darkness of the region surrounding the bubble ([font=courier new,courier,monospace]surDarkAvg[/font]) and the darkness of the entire region ([font=courier new,courier,monospace]darkAvg[/font]). The darker [font=courier new, monospace]darkAvg [/font][font=Helvetica Neue, Arial, Verdana, sans-serif]is than [font=courier new,courier,monospace]surDarkAvg[/font], the higher change of being marked.[/font][/font]
2. Edge detection: detecting the edges (= contiguous black pixels) of the bubble and noting that the farther apart edges are, the more likely the bubble is not filled

However, these methods yield widely varying results on darker bubbles and ones with different resolutions, so aren't accurate. I have spent a lot of time on this, so I wanted to ask you for your thoughts.
Also, there are complications like some bubbles being marked messily, where edge detection is not as accurate.

Thanks in advance!

Dustin Hopper

May 26, 2012 at 8:24 PM

Computer vision, excellent.

What does 'marked' entail?

cvbeginner

May 26, 2012 at 8:35 PM

Marked just means the bubble is at least, let's say, 75% filled in. I'm kind of looking for an algorithm that returns a percentage chance filled, so I can have a certain threshold value (say 50%) above which it says marked, otherwise unmarked.
Also, check out the sample images I posted.

alvaro

May 26, 2012 at 9:07 PM

Humans are remarkably good at this kind of task, but I can't figure out which of your examples are marked and which aren't. Would you mind labeling the data?

Your description about the bubbles being "filled" seems to indicate that there is more context that you are not giving us. Is it the case that these bubbles are printed on some form and humans are going to mark them with a pencil, or something like that?

cvbeginner

May 26, 2012 at 9:12 PM

Thanks for the response. I've labeled the data in the original post.

Yeah, the bubbles were printed on a lot of forms marked by people and were read by a webcam in grayscale.

Dustin Hopper

May 27, 2012 at 12:12 AM

I've been working on it for a bit, and these are the results I've been able to accomplish.

http://imgur.com/a/IxnED

Step-by-step, I first inverted the image, computed the average color of the image, then used a simple gaussian filter to smooth the image and perform simple edge improvement. Color the spots blue that are above the average color of the image as a constant threshold.

Then, I compare how much of the resulting images were colored as a percentage, and use linear regression with the two best image results to guesstimate a correct 'marked/unmarked' boundary.

I'm getting pretty good results from this, but one or two of the images just has too much error invariance in the marking.

u1->8% m1->89%
u2->15% m2->36%
u3->7% m3->38%
u4->21%(not good)

Not sure if any of this helped, but it was fun either way.

Dustin Hopper

May 27, 2012 at 1:21 AM

I'm now getting 100% accuracy, at least for the test data, by doing a second pass on the data and comparing all three images. It isn't too much of a speed decrease, since all of these images are very, very small.

EDIT: Source attached. I used OpenCV.

jameszhao00

May 27, 2012 at 2:26 AM

According to your sample images, the following might work

- histogram the greyscale intensities into (# of greyscale level) bins
- if
- the histogram has > 2 bins with significant (e.g. > 4 %) values OR
- the ratio of the 2 significant bins is too different from a precomputed ratio
- it is marked!

cvbeginner

May 29, 2012 at 9:31 PM

Wow, thanks for your ideas trotlinebeercan and jameszhao00!

The OpenCV algorithm you proposed seems really interesting, but I don't want to use any external libraries.
I am going to try out the bucket algorithm you proposed james and post back what I come up with.

jameszhao00

May 30, 2012 at 12:26 AM

You will have to drop into OpenCV (or some other cv lib) to detect the enclosing oval's bounds.

cvbeginner

May 31, 2012 at 1:38 AM

Okay guys, so I added on the histogram approach to my algorithm. Now I have 3 values:
1. Original edge detection ==> f1 ranges between (0, 1.0) with 0 as surely unmarked
2. Original color detection ==> f2 ranges between (0, 1.0) with 0 as surely unmarked
3. Histogram ==> f3 ranges between (-0.1, 0.6) with -0.1 as surely unmarked

However, now I am not sure how to combine these 3 features to give a proper result. The thing is that these numbers vary depending on bubbles from different shadow conditions, etc.
Below are values for one batch of bubbles, with each feature run on each type of bubble.


 ----f1 marked----
 0.921717,0.927318,0.941889,0.951777,0.849224,0.921182,0.937046,0.935162,0.928395,0.931874,0.895884,0.924812,0.922886,0.94359,0.960976,0.966102,0.936893,0.938575,0.968059,0.967254
 ----f1 unmarked---
 0.513648,0.569007,0.520885,0.536946,0.588808,0.503563,0.485366,0.648438,0.634761,0.569682,0.604423,0.588808,0.534146,0.569378,0.570048,0.549751,0.572115,0.558537,0.533181,0.526316,0.536058,0.506757,0.507353,0.541262,0.495146,0.52657,0.501134,0.515892,0.545232,0.569588,0.495169,0.542998,0.516908,0.521951,0.53317,0.517073,0.5,0.504464,0.540865,0.577017,0.517073,0.538462,0.548387,0.588378,0.527094,0.495074,0.597531,0.589372,0.482014,0.513382,0.608076,0.502451,0.495169,0.496471,0.55198,0.528986,0.527981,0.540416,0.520782,0.556901
 
 ---f2 marked---
 0.945846,0.887927,0.88152,0.804752,0.805723,0.821429,0.861115,0.896657,0.902101,0.88456,0.803749,0.836843,0.5552,0.754623,0.776957,0.973357,0.841618,0.859666,0.812802
 
 ---f2 unmarked---
 0.171143,0.215157,0.188285,0.2157,0.204242,0.212565,0.193557,0.290459,0.170951,0.204252,0.272775,0.213372,0.225717,0.237029,0.202535,0.209917,0.261719,0.209235,0.20551,0.239533,0.249532,0.311185,0.173297,0.225331,0.183087,0.218236,0.141757,0.20633,0.229702,0.27018,0.20081,0.192302,0.212325,0.181655,0.235924,0.270537,0.181245,0.398543,0.203088,0.465899,0.213208,0.197326,0.210956,0.155082,0.194379,0.172727,0.1539,0.218518,0.195955,0.151265,0.181007,0.184102,0.192148,0.191495,0.191056,0.207912,0.175489,0.19905,0.18018,0.158215,0.190958
 
 ---f3 marked---
 0.769231,0.666667,0.679487,0.679487,0.6,0.530864,0.530864,0.682927,0.536585,0.634146,0.536585,0.634146,0.5125,0.443038,0.5125,0.594937,0.679487,0.564103,0.545455,0.631579
 
 ---f3 unmarked---
 -0.0512821,-0.0512821,-0.0512821,-0.153846,-0.141026,-0.153846,-0.0512821,-0.0897436,-0.141026,-0.126582,-0.141026,-0.227848,-0.0875,-0.0875,-0.1875,-0.0617284,-0.0617284,-0.0740741,-0.111111,-0.0617284,-0.0617284,-0.0487805,-0.0487805,-0.0487805,-0.146341,-0.146341,-0.0487805,-0.146341,-0.0487805,-0.097561,-0.146341,-0.0487805,-0.097561,-0.0740741,-0.146341,-0.097561,-0.111111,-0.0617284,-0.0617284,-0.0740741,-0.0740741,-0.0246914,-0.141026,-0.1,-0.0875,-0.0512821,-0.141026,-0.126582,-0.0512821,-0.153846,-0.141026,-0.0512821,-0.0512821,-0.153846,-0.0649351,-0.0512821,-0.102564,-0.0649351,-0.0649351,-0.0649351

I know you mentioned something about linear regression trotline; could you explain it a little bit to me if possible?
It's a big number crunching problem now...

Thanks for all your help so far!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.