Image Processing: Algorithm Improvement for 'Coca

 

One of the most interesting projects I've worked on in the past couple of years was a project about image processing. The goal was to develop a system to be able to recognize Coca-Cola 'cans' (note that I'm stressing the word 'cans', you'll see why in a minute). You can see a sample below, with the can recognized in the green rectangle with scale and rotation.

模板匹配

Some constraints on the project:

  • The background could be very noisy.
  • The can could have any scale or rotation or even orientation (within reasonable limits).
  • The image could have some degree of fuzziness (contours might not be entirely straight).
  • There could be Coca-Cola bottles in the image, and the algorithm should only detect the can!
  • The brightness of the image could vary a lot (so you can't rely "too much" on color detection).
  • The can could be partly hidden on the sides or the middle and possibly partly hidden behind a bottle.
  • There could be no can at all in the image, in which case you had to find nothing and write a message saying so.

    • So you could end up with tricky things like this (which in this case had my algorithm totally fail):

    总失败

    I did this project a while ago, and had a lot of fun doing it, and I had a decent implementation. Here are some details about my implementation:

    Language : Done in C++ using OpenCV library.

    Pre-processing : For the image pre-processing, ie transforming the image into a more raw form to give to the algorithm, I used 2 methods:

  • Changing color domain from RGB to HSV and filtering based on "red" hue, saturation above a certain threshold to avoid orange-like colors, and filtering of low value to avoid dark tones. The end result was a binary black and white image, where all white pixels would represent the pixels that match this threshold. Obviously there is still a lot of crap in the image, but this reduces the number of dimensions you have to work with. 二值化的图像
  • Noise filtering using median filtering (taking the median pixel value of all neighbors and replace the pixel by this value) to reduce noise.
  • Using Canny Edge Detection Filter to get the contours of all items after 2 precedent steps. 轮廓检测

    • Algorithm : The algorithm itself I chose for this task was taken from this awesome book on feature extraction and called Generalized Hough Transform (pretty different from the regular Hough Transform). It basically says a few things:

  • You can describe an object in space without knowing its analytical equation (which is the case here).
  • It is resistant to image deformations such as scaling and rotation, as it will basically test your image for every combination of scale factor and rotation factor.
  • It uses a base model (a template) that the algorithm will "learn".
  • Each pixel remaining in the contour image will vote for another pixel which will supposedly be the center (in terms of gravity) of your object, based on what it learned from the model.

    • In the end, you end up with a heat map of the votes, for example here all the pixels of the contour of the can will vote for its gravitational center, so you'll have a lot of votes in the same pixel corresponding to the center, and will see a peak in the heat map as below:

    GHT

    Once you have that, a simple threshold-based heuristic can give you the location of the center pixel, from which you can derive the scale and rotation and then plot your little rectangle around it (final scale and rotation factor will obviously be relative to your original template). In theory at least...

    Results : Now, while this approach worked in the basic cases, it was severely lacking in some areas:

  • It is extremely slow ! I'm not stressing this enough. Almost a full day was needed to process the 30 test images, obviously because I had a very high scaling factor for rotation and translation, since some of the cans were very small.
  • It was completely lost when bottles were in the image, and for some reason almost always found the bottle instead of the can (perhaps because bottles were bigger, thus had more pixels, thus more votes)
  • Fuzzy images were also no good, since the votes ended up in pixel at random locations around the center, thus ending with a very noisy heat map.
  • In-variance in translation and rotation was achieved, but not in orientation, meaning that a can that was not directly facing the camera objective wasn't recognized.

    • Can you help me improve my specific algorithm, using exclusively OpenCV features, to resolve the four specific issues mentioned?

    I hope some people will also learn something out of it as well, after all I think not only people who ask questions should learn. :)

    An alternative approach would be to extract features (keypoints) using the scale-invariant feature transform (SIFT) or Speeded Up Robust Features (SURF).

    It is implemented in OpenCV 2.3.1.

    You can find a nice code example using features in Features2D + Homography to find a known object

    Both algorithms are invariant to scaling and rotation. Since they work with features, you can also handle occlusion (as long as enough keypoints are visible).

    在这里输入图片说明

    Image source: tutorial example

    The processing takes a few hundred ms for SIFT, SURF is bit faster, but it not suitable for real-time applications. ORB uses FAST which is weaker regarding rotation invariance.

    The original papers

  • SURF: Speeded Up Robust Features
  • Distinctive Image Features from Scale-Invariant Keypoints
  • ORB: an efficient alternative to SIFT or SURF

    • To speed things up, I would take advantage of the fact that you are not asked to find an arbitrary image/object, but specifically one with the Coca-Cola logo. This is significant because this logo is very distinctive, and it should have a characteristic, scale-invariant signature in the frequency domain, particularly in the red channel of RGB. That is to say, the alternating pattern of red-to-white-to-red encountered by a horizontal scan line (trained on a horizontally aligned logo) will have a distinctive "rhythm" as it passes through the central axis of the logo. That rhythm will "speed up" or "slow down" at different scales and orientations, but will remain proportionally equivalent. You could identify/define a few dozen such scanlines, both horizontally and vertically through the logo and several more diagonally, in a starburst pattern. Call these the "signature scan lines."

    签名扫描线

    Searching for this signature in the target image is a simple matter of scanning the image in horizontal strips. Look for a high-frequency in the red-channel (indicating moving from a red region to a white one), and once found, see if it is followed by one of the frequency rhythms identified in the training session. Once a match is found, you will instantly know the scan-line's orientation and location in the logo (if you keep track of those things during training), so identifying the boundaries of the logo from there is trivial.

    I would be surprised if this weren't a linearly-efficient algorithm, or nearly so. It obviously doesn't address your can-bottle discrimination, but at least you'll have your logos.

    (Update: for bottle recognition I would look for coke (the brown liquid) adjacent to the logo -- that is, inside the bottle. Or, in the case of an empty bottle, I would look for a cap which will always have the same basic shape, size, and distance from the logo and will typically be all white or red. Search for a solid color eliptical shape where a cap should be, relative to the logo. Not foolproof of course, but your goal here should be to find the easy ones fast.)

    (It's been a few years since my image processing days, so I kept this suggestion high-level and conceptual. I think it might slightly approximate how a human eye might operate -- or at least how my brain does!)

    Fun problem: when I glanced at your bottle image I thought it was a can too. But, as a human, what I did to tell the difference is that I then noticed it was also a bottle...

    So, to tell cans and bottles apart, how about simply scanning for bottles first? If you find one, mask out the label before looking for cans.

    Not too hard to implement if you're already doing cans. The real downside is it doubles your processing time. (But thinking ahead to real-world applications, you're going to end up wanting to do bottles anyway ;-)

    链接地址: http://www.djcxy.com/p/2248.html

    上一篇: Firefox Marketplace应用程序许可证

    下一篇: 图像处理：对'古柯'的算法改进