Image Analyzing: Scanning a barcode

Miscellaneous Topics
#1

i could need some brainstorming with forming an algorithm for a quite complex bit of work.
it doesnt fit into game dev, so i try my luck here, perhaps i meet some image processing
geeks here (i’m really no fan of image analyzing).

so the task is to get a scan of an EAN-13 barcode, which can be rotated and has passed
many local/pixel-filters to clear the image from disturbances like salt&pepper effects (eg.
gaussian, laplace filters whatever). the barcode will be black on white ground.

to get you an impression heres a barcode what i could look like if the filters did great work

http://zeus.fh-brandenburg.de/~huellein/barcode_rotated.gif

what i have done so far is to scan the image from left to right for the first appeareance of
black pixels and to follow the edge, assuming it is a barcode line. out of the scanned
pixels i calculate the regression line, so that i know the rotation angle of the barcode.

when i have the slope of each barcode line i can find a normal vector to it and scan the
width of each barcode line to read the binary code.
for validating issues, i do not only scan one times i scan for barcode lines and calculate
their slopes many -times.

so far, so good.

now the problems. i have to assume that the image still have many disturbances so that
my algorithms need many security-checks.
but one by one:

the barcode has so called “guard lines” these are the longer ones marking the beginning
and the end of the barcode. additionally they are coded as 101 so that the black (binary 1)
lines indicate the width of each “1”- line.
but i have no concrete idea how to identify them. if i scan each row of the image for a appereance
of black pixels they dont have to be from the first/last barcode line (if it is rotated or even
parallel to the x-axis)

if i scan the width of the guard lines x-times for getting the average width, e.g. 3px, i cant
assume that every 3rd pixel a new barcode line starts. there could be abberace from the
scanning resoulution, perhaps a line would be 3.4px wide …

  1. i dont need to identify the digits, but if a scan line hits them it will try to form a regression
    line out out the pixel cloud, not knowing it isnt a line …

i have much more problems, but enough for now.
i cant await your suggestions…

#2

there is only 1 set of lines to scan that are valid: those with the highest count of black/white color changes. So if you scan the image with multiple lines, those scans that have the highest count of black-line intersections will be the ones you are interested in. No need to rotate or normalize your image at this point! So when you have a line with those digits in them, they’ll have fewer black/white changes and can be discarded.

As a barcode says more than a thousand words… :wink:

http://home.hccnet.nl/s.balk/static/barcode.png

Decoding the resulting normalized barcode is a good way of veryfying your data. The first, center and last digit (the guardlines) should be equal to 6. So you only normalize your data when you are performing the last step: lines -> numbers.

#3

I’ve heard about games where you collect barcodes, input them to the game, and depending on the code you recieve some special powers/monsters/pokemons/etc. with which to play against other players.

#4

here you can see se result of my current technique:

http://zeus.fh-brandenburg.de/~huellein/b.jpg

as you can see i scaned from left to right and followed the outlines of
the hit barcode line. the green scatter lines mark the normal vector.

moreover you can see a porblem i didnt mention yet. you can see that
the red line dont catch the whole barcode line. im using a “left hand”
algorithm, so the pixel which iterates through the line tries to stay at
the left “wall” - in this case a white border.
first i thought i could avoid to take pixels twice by marking them (so not
only seeing white as a border pixel, but red ones too). but like you can
see it is then not possible to get the whole line because there can result
dead ends. but if i dont use a mrking system i have no clue when to end
the algorithm.
so the question is how to get all pixels for a regression line?

#5

Perform a flood-fill on that line. Lightning fast! Don’t be tempted to make the algorithm recusive though if you want raw performance.

Besides that, working with straight lines (as in my example) will save you a lot of work, as you will be 100% sure you don’t record digits.

#6

ahahaaaa … i feel a little ashamed right now, cause i searched for the flood fill
algorithm and it is much easier than my left-hand strategy. sometimes the really
simple ideas are what you are missing…

i will take some of your suggestions i call back, when the next problems occur…