3

I'm creating a program for localizing types of barcodes. (I know plenty exist, that's not the question :) ) I'm focusing for the time being on 1D barcodes.

The difficulty I have is that the barcodes I need to be able to locate could be situated anywhere within an image with other information (text/images/...), inequal lighting conditions (-> gradients), and barcodes could be scaled and orientated in any way.

[Edit] Unlike most barcode-related cases however, my application does not need to be run on a smartphone, so can allow myself some processing bandwidth

I have been researching as much as possible in books and publications, but think it's time to ask the experts...

What is the most appropriate approach for reliably localising 1D barcodes in difficult environments?

Currently, I'm applying otsu thresholding, basic edge detection and hough transforms. Problems i currently face:
- otsu thresholding is global and doesn't handle local gradients on large images well. are there localized algorithms that exist?
- hough locates the lines of the barcodes, but also other items (in particular text), and it's difficult to filter only the barcodes (thresholding the min number of pixels in the line throws out a lot, but also throws out the smaller barcodes)

Could anyone point me in the right direction?

I'm wondering about Fourier and Gabor filters, but they seem more complex, so want opinions before i start.

PS: I am doing everything in Octave and Java

Stevo
  • 67
  • 7
  • This question might help you with your thresholding problems. – penelope Dec 20 '13 at 08:40
  • I messed around with this once using the Radon transform to find them at any orientation or skew, even if parts were missing such that there wasn't a single scanline that intercepted the entire barcode. Basically the line in the Radon output that had the largest peak-to-peak amplitude was the correct orientation? Though if the barcode were perspective distorted, the result would no longer be in a horizontal line, it would be in a diagonal line. – endolith Dec 20 '13 at 17:38
  • endolith, i have heard of Radon, but haven't given it much attention till now. I'll research in that direction. Thanks. – Stevo Jan 03 '14 at 11:02
  • Could you share your conclusions with us? I am trying to tackle the same problem as you. – bellekci Jul 05 '15 at 21:43
  • I have tried different approaches, and actually found the simple approach of finding and combining areas where there is a high gradient magnitude in one direction and a low gradient magnitude at 90 degrees angle quite effective. I also created a method that would localise barcodes based on interpretation of the Hough transforms run repeatedly on specific and increasingly small areas, to 'hone in' on the barcode. If i remember correctly, this had high accuracy, at the cost of performance. Wavelets were also interesting but i didn't finish that exploration :) – Stevo Aug 10 '15 at 12:47

1 Answers1

5

Other than commercial barcode reading algorithms (many of which fail to read challenging codes), I would like to direct you to this paper which is one of the best academic works in that field in my opinion:

Gallo, Manduchi: Reading Challenging Barcodes with Cameras.

Here is a more recent version:

Gallo, Manduchi: Reading 1D Barcodes with Mobile Phones Using Deformable Templates

Judging by the performance they present it can decode really deformed and low quality barcodes.

Following the localization stage, you will require a robust and fast decoding algorithm. Here is one very strong algorithm from Simsekli and Birdal:

Simsekli, Birdal: A Unified Probabilistic Framework for Robust Decoding of Linear Barcodes.

Tolga Birdal
  • 5,465
  • 1
  • 16
  • 40
  • Thanks for the answer tbirdal. 2 very interesting papers. I had come across them, but reading them again makes me think i should definitely try the technique out. It's true that thresholding loses information, and avoiding it altogether may be preferable. Having said that, i am more concerned for the moment with localization (as opposed to reading). The papers assume a barcode is orientated in the same direction as the image and perform a simple gradient manipulation for localization. This is not enough for me. Any ideas in that direction? – Stevo Jan 03 '14 at 11:00
  • 1
    Sure, recently, E. Tekin proposed BLADE, an open source system for localization + decoding: http://www.ski.org/Rehab/Coughlan_lab/BLaDE/

    Also previous year, Gábor Sörös, from EPFL, utilized structure tensor for detecting a barcode saliency region:

    They claim that the method is quite robust. I have done a few dirty experiments on it, and wouldn't say it's best. It might worth a try though:

    http://www.vs.inf.ethz.ch/publ/papers/soeroesg-mum2013-localization.pdf

     – Tolga Birdal Jan 03 '14 at 11:28
  • Other than all that, if you are working in a controlled environment, I would say that you could hand tune your own barcode localization algorithm making use of:
    • Connected component labeling and bar filtering
    • Using gradient orientation to filter out lines or to group lines into barcode regions.

    There are also other methods with Hough Transforms, Radon Transforms etc. but from my perspective they are a bit overkill, since barcodes can be detected with great speed performance.

     – Tolga Birdal Jan 03 '14 at 11:28
  • Since my first post (and before your post) I attacked the problem from the gradient perspective and developed the following algorithm: Looking for regions in the image with high gradient magnitudes (in any direction) and (after gaussian convolution) relatively low variation in angle of gradient. I multiply the result with thresholded (otsu) image, to remove background false positives. It's not bad, but not good enough (i'm difficult :-) ). I will study the pdf document describing BLaDE as it seems interesting. I may retry using Hough with my newfound knowledge. – Stevo Jan 06 '14 at 14:18
  • Something important i haven't mentioned yet: unlike most barcode-related cases, my application does not need to be run on a smartphone, so can allow myself some processing bandwidth. – Stevo Jan 06 '14 at 14:23
  • Hough transform would give you a hard time in localizing multiple barcodes. The strategy of clustering line blob orientations might be a savior in this case. – Tolga Birdal Jan 06 '14 at 16:52
  • tbirdal, you have been a source of inspiration. Thanks. It's up to me now to spend a lot of time trying all these ideas out. I'm not expecting a single one of them to be enough, but rather a hybrid solution based on several complementary concepts. One last question: do you have experience with Gabor filters? Should i be considering them as well? In the long run, are they not similar to performing edge detection followed by gaussian convolution? – Stevo Jan 07 '14 at 08:31
  • Gabor filters are nice, they are proved to be robust and well suited to applications such as Face Analysis. For this application I would suggest using Sobel filters for gradient computation as they have great speed vs robustness property. – Tolga Birdal Jan 07 '14 at 08:38