Topic: Barcode/Datamatrix/Image Vectorization (Page 1 of 1)

Hello,

maybe one of you has an idea, or perhaps some experience on my current pet issue.

I'm trying to decode a 2-D barcode called DataMatrix with a cheap webcam ( close range, webcam isn't here yet,
but I expect the resolution to be good enough).

There's some code out there for decoding aligned barcodes ( a c library called libdmx, I believe ), and once
you have the bit muster, I guess it's not that hard.

My problem is aligning my barcodes in software - the use won't gurantee any kind of rotational stability, ie. the codes I scan can
be rotated any 360 degrees .

If you look at the pictures in wikipedia, you can see that the barcode comes with two orthogonal borders and is surrounded by a white space.
That makes it possibly to run a 'find edges' matrix over the image.

Once I've done that, I though about vectorizing the image, looking for two orthogonal vectors of (roughly) the same size and (roughly) joining on one side.

Works like a charm in 90 degree rotated images, but I'm complety stuck vectorizing lines at an angle.

I'm afraid I'm telling google all the wrong search words - at least I haven't found a single, understandable (=simple) vectorization algorithm yet .

Who has either a pointer on that, or a better idea to locate such a pattern in an image?

Thanks,
so long,
->Tyberius Prime


Edit: maybe adding some links might be helpful

(Edited by Tyberius Prime on 09-23-2006 13:19)

Well...
apperantly, I'm not alone.

Kahye Song at Stanford has a
short paper about detecting 'guide bars' which is more or less equivalent to my problem.
More or less - his guide bars are not connected, which allows him to use regions. Bars make rectangular regions, while squares (and circles )make square regions.

My guide bars are connected - but maybe I could just look for square regions. But they won't tell me anything about the orientation .

Actually, seems that was a class assignment.

Maybe I shouldn't fix on DataMatrix - but it'd be nice to give those open source projects a hand whilst solving my problem ( marking 1000ths of small plastic test tubes) at the same time.

Canny edge detection.
Well, I meant: edge detection.

I meant this even: http://www.parallax69software.com/vectorize.htm

Nevermind... the region ain't square if my image is angled...
But I guess they still should fall into a range of long/short side ratios.

Maybe check all regions with such a ratio for all white pixels on one side...

Is anybode understanding the Hough transformation
in house?

I was talking about the 4 thinning algorithms proposed on that page, thinning is a way to achieve what you want to do. anyway...

(hint: my current mission has a lot to do with what you're asking.. a whole lot)

You can also base your work on the outer square of the barcode area.
Will maybe try to produce some snapshots to expose my views, hold on.

And I think the transform you proposed is a bit of a ..hammer for the purpose.

Ok, proposal.

1) scanline detect the 4 extremums of your barcode surface.

scanline detect means: parse every line, memorizing only the distance of the first pixel you encouter from the left and right borders.
You can parse each line from left until the first black point appears, then skip to the right, do the same from the right of the line, and store these offsets in a table (the table can be of dimension: number2[pixel height of image], which maps to [x offset][y offset] implicitely).

max complexity is O(w*h). Generally, closer to half or less of that.

This is what is done in a graphic card pipeline to prepare offsets for textures, and in most 3d engines.



2) Now your image is a texture (the barcode perfectly fits a polygon), and due to it's square nature in real world, you can easilly unskew it. How?



By handling "floating point" pixels.

Given the canvas of your target, unskewed barcode image. It's w/h, we'll name "main_w" and "main_h".
Given the four points we have extracted before, A, B, C, D (in clockwise order)

All you have to do now is plot "main_w * main_h" pixels, and color them the same way as each row of the ABCD polygon.

To do this:
1) divide AD in main_h points. The same for BC.
2) parse your array of AnDn -> BnCn skewed lines, each time dividing the length of the line in main_w steps.

Max complexity is, again, O(w*h).

Since the algorithm proposed above is composed of two sequences of identical theorical complexity, O(width*height), it's total theorical complexity
is O(width"height) (not 2O(width*height)).

Aka one single image pass.

You can then use the middle line I represented above and the same notion of proportions to accurately read your barcode.

(Edited by _Mauro on 09-23-2006 17:08)

Thanks Mauro, that vectorization link was just what I was looking for - it's always difficult to search for subjects you don't even know the names about. ( And don't get me started on how much 'vectorization software' there is out there. Google is useless if you want to find 'vectorization algorithms').


Alas, If I was parsing 1-dimensional barcodes, I'd be done already .
(More specifically: I would print my barcode as a circle in the first place. Just find the center ( count edges ), work outwards, bingo.


I'm making fair progress using regions to find potential barcodes ( there might be more than one in an image...) and rotating*.
Nearly all of the students in the assignment I linked used a region based approach.
And while their problem involved two seperated guiding bars (simpler - you can match the two regions, instead of having one large region), once I have rotated a region to be 'straight',
I can resume with my own, simpelton vector based approach.


So long,
->Tyberius Prime

*I don't need skewing. Objects will be planar to the sensor, just in any rotation.

Both approaches can work, among many others certainly. I see exactly where you decided to focus on lines continuity.
Yet I've opted for something which is more like a "rotozoomer", and based on textures processing.

I've started implementing it to see how it works.

http://www.beyondwonderland.com/data/java/barcodes/header.html
source code


At this stage, I have:
- left and right edge pixels (red)
- extremums (top left, right, bottom left, right)(blue)

From this, I can use my extremums to determine which point in the edge pixels is the closest, and therefore spot my ABCD points in the above piccis (really catch the barcode "tile").

If I had many barcodes, and I will test that too, I'd make a first "identification" pass based on uniformity of colors.
for example: subdivide the picture using a grid, compute the color uniformity of an area, if it's uniform give it up, otherwise label it workable.

Subdivide the remaining squares in smaller squares and repeat, until you get to quite small squares.

Treat remaining "groups" of pixels by copying them to new images, which will pass through the "vectorizer".
In the vectorizer part of the code, check only two three lines of the "supposed" barcode, if you find they describe the same barcode, then chances are...

It is right.

For circles, as you said, work from the center along the radius.

quote:

---

Note to self: this could be developed further to recognize the 3d perspective of an image with two three barcodes, and probably start 3d reconstruction...

---

[ ] you have looked at the wikipedia article and discovered that matrixcodes don't have bars on the left and right.

is the real thing I want to parse.
Note that the image noise and skratches on the barcode surface etc don't make it easier.

I need to find and transform* the region borderd by that 'L' on one side, and the alternating dots on the other one.
*(Guess a transformation vector would be all I need to build the bitmatrix, no need to transform the actual pixels).


For deskewing your algorithm is sound of course, thanks again.

On a side note, "Single pass" isn't quite the same as algorithmic complexity. Yes, your code is O(n * m), which ignores
scalar factors. But for a fixed size problem, the scalar factor is important.

So long,
->Tyberius Prime

(Edited by Tyberius Prime on 09-28-2006 11:05)

My 2 cents if the data matrix won't be rotated too much and the picture above is somewhat representative of the images you'll have to process.

1. crop to a 480x480

2. convert the image to b&w ( eventually using the most homogenous channel ). Then Auto-level it.

3. posterize the image to 2 to only have pure b&w.


4. walk along the edges of the 480x480 square and floofill in white

5. paint every black pixel in white if it has less than N black neighbors. That's basically a Maximize morphological operator.

Now only the DM should remain.

6. Crop the image to fit the DM

7. resize it to 14x14 with bilinear filtering. Note that you might need a pass of Minimize morphological operator if you used a simple Maximize morphomat operator in 5

8. posterize to 2 again, and voila.

This process worked like a charm, in Photoshop, with your image.
Hope that helps,



(Edited by poi on 09-28-2006 15:20)

It will be rotated any which way, unfortunatly.

By now, I'm pretty sure the hough transformation is what I need.
After all, it finds lines in images, and I have two fairly long lines at a certain angle, plus a number of short, parallel lines.

I've got it up and running and it's not doing badly ( having quirks though ), for one (conceptual )exception:

r = x * cos ( theta ) + y * sin (theta )
If a line is parallel to the x-axis, theta is 0.

Later on, doing the backwards transformation on the points containing the longest/most likely lines in the hough space,
I simply do
for x = 0 to width:
y = ( r - x * cos ( theta) / sin(theta) )
paintPixelBlue(x,y)
(I know this does not paint lines paralell to the y a

And here comes the problem. Theta is 0, ergo sin(theta) = 0 as well.
I know there's a a line parallel to my axis, but I just lost all information to where it is .


So long,

->Tyberius Prime

To work even with extreme rotation, I was about to suggest a Active Contours (Snakes) approach, between my steps 5 and 6. Set the original shape of the snake to the 480x480 square and make it shrink till it finds the DM. Then do a shape or polygon simplification on the outline formed by the control points of the snake to get a quadrilatere.

Then you can either transform that quad into a square and rotate it so that you get the black L on the bottom and left sides, and go on to step 6 and further.

Or you can subdivide the quad in 14x14 and see the average color around each point of that 14x14 grid. Make sure to test the center of the cells. Then rotate your small (14x14) set of values so the L shape is correctly positionned.



(Edited by poi on 09-28-2006 15:51)