hybrid binarizer without holes
Steven Parkes
HB estimates black level on a block-level basis in order to handle shadows, etc. This works very well for blocks that have a fair amount of dynamic range in them. In blocks that don't (i.e., less than 10% of max for a byte), it presumes the area is white. (There's a "hack" (I think it's mine?) such that if the block is entirely 0 == black, it will in that one case, know that it's black. That makes some synthetic codes work that otherwise would fail.))
This works vey well in most cases. One condition that it fails fairly spectacularly for is qr codes (which have large black areas (the finder patterns)) in cases where the sampling rate (i.e., image resolution) is much greater than the feature/module size.
In that case, while estimating the black point of a block that falls entirely inside a finder, the low-contrast path is tickled and the area is assumed to be white. This punches a whole in the finder in the binarized result and the qr code detector fails.
The motivation for this for me is decoding images taken with a phone camera. Those are much higher resolution than the images I decode from the live preview and thus get holed. It's possible to decimate the pictures and decode that and that often works. But it limits the images that will decode since a lot of information is thrown away. Its more or less a random guess at what the feature-size to resolution ratio is, which can be anything. It works if people are taking pictures as they would from the live video feed, but since the resolution of the camera is greater, I'd like to be able to allow a larger variety of capture conditions.
It's admittdely not the highest priority for me, but it is an interesting puzzle that I wanted to see if I could come up with a simple (elegant?) solution for.
So I've been thinking about a way to tweak the algorithm. The overall idea is that in addition to the current block's dynamic range, we can look at more global information from the image to weaken the assumption that low dynamic range means white. This should be a very local change … it shouldn't sacrifice the accuracy of HB in other ways. And it won't cover every case, but it'd great if it could cover very unambiguous cases.
So I tweaked things to record not only the block mins and maxes, but the global mins and maxes for the image. Then, in the low contrast blocks, I look at how close the block min is to the global min and block max is to the global max. In cases where the block min is much closer to the global min (black_diff) than the block max is to the global max (white_diff), I use the max+1 as the black point, otherwise I use the current estimate, which is twice the minimum.
I ran through the blackbox tests with this. If I use the degenerate case of black_diff < white_diff, it works poorly for a lot of images because it misclassifies things until the "real" dynamic range of the image is known since it's only using the dynamic range of the portion of the image already processed, which will often be low for images with a simple white-ishbackground.
So I tried using multiples, e.g., 8*black_diff < white_diff. This makes the algorithm more conservative in the sense of preferring white false positives over black. I tried a number of multiplication factors. In my test set, once the factor goes above around 12, the holes come back. If the ratio is too low, more "black"ish artifacts (like the thumb in one of the tests) get blacked and things fail.
But that provides a pretty wide, relatively insensitive range. I'm using 8 for now.
There's also the issue of what the black point estimate should be. If it's less than the max, holes appear which cause failures. I don't want to assume the local maximum is the global maximum (to handle shadows) so I don't want to use it. Setting at it between max+1 and 2*max seems to work okay so I'm erring on the conservative side with max+1.
This causes only minor changes in the blackbox tests. I think it adds 8 but loses 12. The weird thing is that in the new decode fails (a couple of data matrix tests), the binarized images are virtually indistinguishable visually. I still want to look into exactly whats causing those no-decodes.
So I just thought I'd see what people think. It feels like a cheap and fairly clean improvement ...
Sean Owen
Steven Parkes
It'd be easy enough to make it an option, as you mention, and simple to turn on and off knowing a priori the size of the image being decoded.
But I still like the puzzle of why it is failing some images. It's not obvious to me why it should, so I want to explore/understand those first.
I posted to do a sanity check on the approach, see if there was some egregious flaw I was missing. Thanks for the comments. If anybody else has any ...
Daniel Switkin
Steven Parkes
Little subtle, but it doesn't lower it, it makes it 1. Since the max is 0, the min is 0 and twice the min is 0 which makes it white since the threshold is strictly <. I came across the same thing (see issue 469): my patch had been to use <= instead of < but the effect in this case is the same.
Sean Owen
Steven Parkes
Yeah. A lot of the simple rules fail on images that have any shading (=== overall reduced dynamic range) and, in particular, variable shading. Those are the cases where HB's approach really shines, these corner cases notwithstanding.
Steven Parkes
On Oct 11, 2011, at 1:10 PM, Daniel Switkin wrote:
> Before I get into your proposed fix Steven
Working on another idea that, if it works, will work a lot better ...
Steven Parkes
So I think there's a fairly simple and reliable mechanism for doing this.
I propose changing
int average;
if (max - min > 24) {
average = sum >> 6;
} else {
// When min == max == 0, let average be 1 so all is black
average = max == 0 ? 1 : min >> 1;
}
blackPoints[y][x] = average;
to
int average = -1;
if (max - min > 24) {
average = sum >> 6;
} else {
if (y > 0 && x > 0) {
int bp = (blackPoints[y-1][x] + 2*blackPoints[y][x-1] + blackPoints[y-1][x-1])/4;
if (min < bp) {
average = bp;
}
}
if (average == -1) {
average = min >> 1;
}
}
blackPoints[y][x] = average;
[As to the average = -1, I don't know if others have a different preferred style for not duplicating the min >> 1 which I don't like …]
The high level interpretation is that given we're looking for dark on light symbology, if we're in a low dynamic range area that should be dark, it was surrounded by a light region at some point and good black-point estimates were made at the transition. So in those cases, we use the average of those previous estimates.
We actually look at the black points of the block up, left, and up-left. Since I didn't want to do a real divide, I give the left block double weight.
I tried different conditionals, e,g., min < bp, max < bp, and (min+max)/2 < bp. min worked best in tests. It reduces false-whites without creating false-blacks. The rationale for this would be that the bp estimate at the transition could be on the low side if the average was dominated by dark pixels. It'd be nice to be able to update or reestimate the bp in these blocks rather than use the surrounding average but I haven't come up with any local way of doing that. While we have an estimate of what the local black value is, we don't have an estimate for the local white value.
The -6 blackbox tests are in the datamatrix tests. And that's a net -6, there are some new successes and some new failures.
I spent a fair amount of time tracking one error. It was on a previous version of the code that now passes but I think it demonstrates what's going on.
Image (datamatrix-2/03.jpg): http://dl.dropbox.com/u/11615635/zxing/image.jpg
Original binarized image: http://dl.dropbox.com/u/11615635/zxing/orig.png
And the new one: http://dl.dropbox.com/u/11615635/zxing/new.png
They look very similar. In fact, the key difference between decode and not in this case is a single pixel in the upper left hand corner:
Original zoomed: http://dl.dropbox.com/u/11615635/zxing/orig-zoomed.png
New zoomed: http://dl.dropbox.com/u/11615635/zxing/new-zoomed.png
I tracked this as far as getting a one pixel difference in the surrounding white rectangle estimate and that was enough to throw off the decode.
I believe the other new datamatrix failures are of the same class. I eyeballed the binarizer outputs and they all had tiny changes that were not very significant.
Steven Parkes
This image was originally 2k x 2.5k (taken with an iPhone 4).
It's an image of the IOS simulator but essentially it's the same for any high resolution image taken from an LCD screen: camera resolutions and focus have gotten so good, they can resolve the individual LCD pixels. Our eyes low-pass filter this stuff but the camera doesn't.
I don't have any ideas for an elegant solution that will commonly work with this. It's relatively easy to low pass filter the image by just decimating it which also has the benefit of reducing the computation required. But if the picture is of something further away, low pass filtering will blur things and inhibit the ability to resolve smaller codes.
So I'm back to trying a decimated decode with a fall-back to a full-resolution decode.
Daniel Switkin
> I want to mention that Sean's change in CL 1500 seems wrong to meLittle subtle, but it doesn't lower it, it makes it 1. Since the max is 0, the min is 0 and twice the min is 0 which makes it white since the threshold is strictly <. I came across the same thing (see issue 469): my patch had been to use <= instead of < but the effect in this case is the same.
Daniel Switkin
int average = -1;
if (max - min > 24) {
average = sum >> 6;
} else {
if (y > 0 && x > 0) {
int bp = (blackPoints[y-1][x] + 2*blackPoints[y][x-1] + blackPoints[y-1][x-1])/4;
if (min < bp) {
average = bp;
}
}
if (average == -1) {
average = min >> 1;
}
}
blackPoints[y][x] = average;
Steven Parkes
I think we're on the same page, but that's just a boundary condition to force back to the existing code if there aren't any previous estimates. The code actually checks the previous bp estimates of the blocks at left [x-1,y], up [x,y-1], and up-left [x-1,y-1]
> Perhaps your idea of neighboring blackPoints could be used for that.
That's what this code does, right? It just drops back to the existing mechanism where that's not possible.
int bp = (blackPoints[y-1][x] + 2*blackPoints[y][x-1] + blackPoints[y-1][x-1])/4;
if (min < bp) {
average = bp;
}
It's looking at the average of previous black points as the local estimate of the bp. If the current min is below the bp, we assume the "inherited" estimated bp is as good as we have. The intention/intuition is that the bp used within a large black area is the bp estimated at the boundary of the block, when it went from light to dark.
The conditional (min < bp) is supposed to protect against the (presumably rare) case where the bp block boundaries line up exactly with a transition from dark to light.
Daniel Switkin
Steven Parkes
Yeah, that's the key here. But there's something I'm not following because that's exactly the behavior that I'm proposing we change, though only in a subset of the cases.
Here's the whole new code
int average = -1;
if (max - min > 24) {
average = sum >> 6;
} else {
if (y > 0 && x > 0) {
int bp = (blackPoints[y-1][x] + 2*blackPoints[y][x-1] + blackPoints[y-1][x-1]) >> 2;
if (min < bp) {
average = bp;
}
}
if (average == -1) {
average = min >> 1;
}
}
blackPoints[y][x] = average;
This doesn't have the max == 0 condition anymore because it doesn't need it.
Here's what I think is supposed to happen. (I know some of this is obvious and repetitive, but there's something missing in this discussion and I don't know what it is.)
We have three cases here, generally speaking. Blocks that are a mix of light and dark pixels, blocks that are light only, and blocks there are dark only. When estimated the blackpoint (bp) we don't know a priori which case we have.
The mixed case is detected by a max-min difference greater that 24. In this case, the bp estimate is the average of all the pixels in the block. This seems like a simple and effective solution. The more abstract idea would be, I think, to assume you had a bimodal distribution of pixels and to use some kind of classifier like k-means to estimate the means and then use the midpoint between them. That would seem to work better than the current average for blocks that have far from an equal number of light and dark pixels. But the current average seems to work well enough to not warrant the extra complexity (even if I knew how to do it … I really only understand classification algorithms at the abstract level.) Moreover, I think we're more sensitive to false-black (signal) than to false-white (background) so I'd guess there are cases where something that was actually "more correct" by some metric would result in worse decoding.
So that leaves the all-light and all-dark blocks. The problem in both cases is we have no estimate of the dynamic range, no idea "how high is up". 128 is dark in one image and light in another. In fact, 128 could be dark in one part of an image and light in another of the same image. HB does a good job of handling many cases like this by not assuming a global dynamic range.
The legacy heuristic is to assume that all non-mixed blocks are white. That still doesn't provide any indication of the level of dark so the estimate is made at half the min in the block. This is an effective estimate in many cases but will fail in a some cases, e.g., where dark is 128 and light is 255. But it seems to work well enough and nothing better has been proposed.
So the final case is all dark blocks. The legacy heuristic assumes these to be light and sets the bp estimate at half the min which causes them generally to be binarized as light.
That was the impetus for the "max == 0" hack, so that synthetic black and non-black (black == 0, non-black != 0) images with a resolution such that the finder size was greater than the HB block size would decode. Without that condition, HB would create light regions inside the finder patterns and the finder pattern finder would fail.
But that's really just a hack on the "assume it's light" assumption. So what I'm preposing is not always assuming non-mixed blocks are light.
Then the questions are (assuming you maintain the current bp estimate of min/2 if it's a light block):
1) how do you know if it's a light or dark block
2) what do you use for the bp in a dark block
And we want to do this without assuming any global information like the global min and max for the image. That kind of assumption doesn't hold for images with varying local dynamic range, e.g., images with shadows.
The key to (1) is to assume that all-dark areas are surrounded by areas that are not all-dark, i.e., are all-light or mixed. SInce we're doing dark on light symbology, this should always be the case, at least for blocks we care about. We also assume we're making bp estimates top left to bottom right so if we are in a black region (that we care about) we have valid estimates at the boundary from light to dark that were based on either mixed or all light blocks. So to choose between all-light or all-dark, we just compare the values in the block with the average of the neighboring bp estimates. These estimates should always be reasonably accurate (as good as any of our estimates).
Actually, that skips a step, which is what about dark blocks that are surrounded by dark blocks? That leads to (2), what should the bp estimate be for a block that we decide is all dark? We have no idea what the dynamic range is, how high is high, since there are no light values in the block. But we do have the previous black points … so we just use the average of those values.
So the summary is the bp is estimated as
- the average the pixels for mixed blocks
- half the min value in the block for light blocks
- the average of the three previous bps for dark blocks
- mixed blocks are blocks with max - min > 24
- light blocks are blocks that are not mixed and either no previous bp estimates exist or where min >= the previous bp estimates
- dark blocks are blocks that are not mixed and min < the previous bp estimates
This only changes the algorithm in cases where black regions are surrounded by light regions but those are the only ones we care about … at least those are the only ones I'm addressing in this. If an algorithm existed that could subsume this (as this subsumes the max == 0 hack), that'd be great but I don't know of one.
The (min < bp) part still feels a bit arbitrary. I tried (max < bp) and (max + min)/2 < bp and they both performed more poorly.
Sean Owen
Steven Parkes
Yup. Some ad hoc low pass filtering. I think this combines with the fact that at least some of the decoders are more sensitive to false-dark (signal) than to false light (background) so the impact of errors is asymmetric.
Daniel Switkin
Steven Parkes
It can for blocks not surrounded by something light or mixed. Do you think it can for blocks that are?
I have no problem putting it back in but left it out since I didn't think it could matter. But maybe I missed something.
> Have you tried that?
Can't remember. I'll recheck.
> The min < bp check is probably what bugs me the most.
Me, too.
> Here's a few variations I brainstormed but haven't tested
I'll test 'em.
Steven Parkes
On Oct 14, 2011, at 9:22 AM, Daniel Switkin wrote:
> I believe we need to test for pixel <= threshold
and my earlier comment
> I have no problem putting it back in but left it out since I didn't think it could matter.
I actually meant the (max == 0) version when I said left out. Felt like a hack. I like the "<= threshold" version.
I wouldn't think it would make any difference, but against my current patch, it's a net blackbox win of +8.
Daniel Switkin
Steven Parkes
>> Here's a few variations I brainstormed but haven't tested
>
> I'll test 'em.
Delta blackbox test passes.
Baseline is my current patch with the <= threshold added back in.
Trust neighbors: -24
Blend with neighbors: -127
Conditional blend with neighbors: -118
Daniel Switkin
Sean Owen
-2 Aztec
-8 Datamatrix
+6 PDF417
+18 QR code
I did verify that it works correctly on a 3000x3000 image with 100x100 modules.
I'd like to commit this with some comments to Java.
Sean Owen
Daniel Switkin
Steven Parkes
Compared to my patch:
Straight legacy (max == 0 ? 1, < threshold): -14
Legacy with max == 0 ? 1 and <= threshold: -16
Legacy with <= threshold w/o max == 0 ? 1: -10
- As Sean mentioned, these haven't been including the rss tests since they aren't in the current build.xml.
- These don't include a new qr test that I've added.
As both Sean I have mentioned, these aren't monotonic. There are some new failures as well as the new successes. Even across the cases above these vary. I did look at one of the new datamatrix failures and it came down to being sensitive to a single pixel change on the corner of the code.
Steven Parkes
Please give me a chance to respond … I'm still trying to catch up.
Steven Parkes
On Oct 14, 2011, at 12:09 PM, Sean Owen wrote:
> I'd like to commit this with some comments to Java.
I really don't want to make a deal about this …
… but I guess I should let you know that this kind of discourages me, from the point of view of trying to be a valued member of the project/community.
I'm a committer, so I can commit my own code … unless I misunderstood what becoming a committer meant and it was really meant only for the C++ port. If that's the case, I really did misunderstand.
If that's not the case … I can tell you after having slaved on this for a couple of days, to have someone else commit it just makes me feel bad. I spent a lot of time looking at the issue and writing up the rationale, I have both Java and C++ versions of the patch queued to commit, etc.
I don't begrudge that at all … that's what it means to me to be part of an open source project. But I've figured I'm on an equal footing with other committers. I'm used to the attitude of committers being you commit what you write and/or sponsor from non-committer contributors. (I probably inherited this attitude from my work with Apache Lucene, which I think has an admirable approach to community.)
If that's not the case, I can live with it, but my approach to the project may end up changing some. I may not spend as much time trying to explain things, to create consensus. It's a lot of effort.
This extends over to the C++ port. I try pretty hard to keep it in sync with the Java port, at least the parts that are currently up to date. That can be a lonely challenge. On the flip side, I propose my changes in the Java code base even though I'm not currently using it. I figure it's just the right thing to do, to get agreement in general and then implement in both code bases.
From my point of view, I'd prefer the commit of this to be one commit, to both code bases since I know it's the same. To have someone else commit part of it makes extra work for me to go back and make sure they are the same. (I try to keep them as identical as possible, down to the variable names, to minimize future support effort).
Reminds me that I worry about how much the C++ port is considered a poor stepchild. I don't expect people contributing to the Java port to make equivalent changes to the C++ code base but there are lots of things that Java contributors can do or not do that can have a significant impact on how difficult it is to keep the C++ code up to date. I don't really know what to expect in terms of people's behavior, whether out of respect or otherwise, they make an effort to make things as easy as possible for people trying to maintain other ports, or whether that just isn't a consideration and the chips just fall where they may for the non-Java ports.
Sean Owen
Sean Owen
Steven Parkes
On Oct 14, 2011, at 2:05 PM, Sean Owen wrote:
> (the slightly bad news about the Java port is that it's about to be overhauled for Java 6. This will probably make it a bit harder to re-port as it uses more language features and JDK classes than before.)
Good to know.
Guess I was always swimming against the current. Guess it's as good a time as any to throw in the towel.
I'll check in the thresholding stuff but I can't reach parity between the Java and C++ after r1697.
Daniel Switkin
Steven Parkes
:)
I realized one way to make the C++ and Java tests stably comparable is to implement a luminance source with a known algorithm, which could be used just for the tests. That way "real" code gets the built-in mechanism which may be faster but we can still compare things to a known reference where performance isn't critical but repeatability is. In my C++ testing, I use ImageMagick to reduce RGB to grayscale but it's only somewhat by luck that it happens to use the same conversion function that the Java code used to use (and even that required a small tweak to the Java code).
Steven Parkes
On Jun 26, 2012, at 2:15 AM, pmenaria wrote:
> Hi, I want to increase the scanning distance of the qr code but want to keep the qr code size same. Can you suggest me something Pls.
Not sure why this is attached to the old binarizer thread.
The key to decoding is detection of the code and sufficient resolution to identify the qr modules. You can try bumping the resolution of the capture but how much this will help is unknown.