in Development

Finding more duplicate icons – An introduction to image feature extraction

Following a small experiment in the spring on detecting duplicate icons. We wanted to dive deeper into this field. One of the main task in finding identical icons, is that they are most often not digital duplicates, but still look identical. This challenge can be partly overcome by using a technique called feature extraction. Let me explain…

I’ll first start with what this text is and what it is not, it is a brief introduction to feature extraction written from the point of a beginner. It doesn’t dive into algorithms or what my designer colleagues sometimes refer to as ‘magic’. And any feedback, corrections or additions are more than welcomed. Just leave a comment bellow.

What are features?

An image feature is a general term but it usually means a part of an image that contains interesting details or a property of the image which we are interested in. What are ‘interesting details’? It depends on the overall goal and what the application is trying to achieve. Many computer vision algorithms use feature detection as the initial step and a large number of feature detectors have been developed. For example, some of the most commonly used features are:

Edges

http://blog.iconfinder.com/wp-content/uploads/2014/10/canny.png

Image before and after applying edge detection

Edges are points that are at the boundary of two image regions and are detected by computing the change in brightness, we can say that we have an edge where there is a rapid change in brightness. Usually the algorithm implementation puts some some constraints in place for the on the properties of an edge, for example the minimum length for it to be considered one, shape, smoothness, and gradient value. http://blog.iconfinder.com/wp-content/uploads/2014/10/edge.png

Zooming in we can see the luminosity change where the two regions meet and the edge is formed.

They can be used to find the boundaries of an object or a surface and they also significantly reduce the amount of data needed to be processed while preserving the details that we are interested in an image. Examples of edge detection algorithms: Sobel, Canny, Gabor, Kirsch, Prewitt.

Corners/interest points

http://blog.iconfinder.com/wp-content/uploads/2014/10/harris.png

Detected interest points using Harris corner detection marked in green.

A corner is the point located at the intersection of two edges and you can think of an interest point as a small region in the image (window) for which no matter in which neighboring direction you look there is a high variations in brightness. This means that an interest point can be a corner sometimes. In practice the terms are used interchangeably and most corner detection algorithms actually detect interest points rather than corners as they are far more useful.

http://blog.iconfinder.com/wp-content/uploads/2014/10/harris_diagram.png

http://blog.iconfinder.com/wp-content/uploads/2014/10/corner.png

Zooming in we can see the brightness changes in the neighboring regions.

What makes a good interest point is the ability to recognise that point at that same location, even if the image is resized, rotated, the brightness changes or the image was taken from a slightly different point of view. Examples of edge detection algorithms: Harris, SUSAN, Shi & Tomasi, FAST.

Blobs/regions of interest

http://blog.iconfinder.com/wp-content/uploads/2014/10/blob.png

Detected largest blob highlighted in green.

Blobs, or regions of interest, are regions where the brightness or color of the points change very little so they can be considered in some sense to be similar to each other. Examples of blob detection algorithms: FAST, Laplacian of Gaussian, Difference of Gaussians, Determinant of Hessian, MSER, PCBR.

Color

Color can hold sometimes a lot of information, Lego Image is the perfect example of that, the creative artist Jung Von Matt show how much information can be depicted by using just colors of familiar cartoon characters.

http://blog.iconfinder.com/wp-content/uploads/2014/10/lego_southpark.jpeg

Southpark characters made with Lego. Artist: Jung Von Matt

A good example of dominant color extraction can be found on the pyimagesearch blog.

Computer vision steps

http://blog.iconfinder.com/wp-content/uploads/2014/10/computer_vision_flow.png

Pre-processing

This is usually the first step before any computer vision methods can be applied, it usually includes steps such as:

  • Gray-scaling to reduce the amount of , we will only have to examine one value (light intensity) instead of three (red, green, blue color intensity).
  • Blurring to remove sensor noise and speckles from the image so that it does not introduce false information when detecting. Speckles can be for example falsely detected as corners.
  • Contrast enhancement to assure that relevant information can be detected.
  • Rescaling to reduce the amount of processing work needed to be done. For example in an 1920-by-1080 image we will have 2073600 values instead of 480000 values for an 800-by-600 image.

Feature detection

Feature detection is a low-level image processing operation and usually comes after the pre-processing step and it examines every pixel to see if the region around that pixel could be used as a feature. Feature detection can also be a sub-step in a larger algorithm, then the algorithm will typically only examine the image in the region of the features.

Feature description

Once the features that are interesting to us have been detected, they can be extracted. The result is known as a feature descriptor or feature vector and they characterize the region around the key point as rotation and luminosity invariance vectors. They can also reduce the amount of data required to describe the image region that corresponds to the feature, they are represented as N-element vector in another domain and two descriptors can be compared using a distance metric, the less this distance – the more similar descriptors are. One example of descriptor is the HOG (Histogram of Oriented Gradients) descriptor, such are SIFT and SURF descriptors. These are computed based on the gradients orientation and expressed as vectors. Practical example: We can find a corner with the Harris corner detection method, and we can describe it with any method we want (Histograms, HOG, Local Orientation for example).

Matching/indexing/recognition

Given that a descriptor has been created for each identified key point we can now process and make decisions based on them. We could, for example, make matches by comparing our descriptors with a known descriptor set stored in a database (OCR, facial recognition, object recognition) or compare the descriptors directly between two images to find matches.

http://blog.iconfinder.com/wp-content/uploads/2014/10/orb_matches.png

Matched descriptors from one image to another.

Next step

This post was meant as a general introduction to the terms used in the computer vision world. In the next post we are gonna take a few practical examples and see show we can create a content based image retrieval system step by step.

Write a Comment

Comment

  1. Great post, and thanks for the mention of PyImageSearch! Send me an email, I would be happy to chat about your CBIR system. Maybe we could collaborate on it together, or I could do a guest post! Definitely let me know!

  2. I stumbled across IF several years ago and was fascinated at watching it grow. You were actually documenting as you grew. Talking about using Postgres, DJANGO, and everything else. Actually writing articles on your chosen methodology. I understand IF has grown quite a bit and you need to keep an eye on security, but I wish you would write more technical articles.

    I work in a Windows shop, so I only work with things like NGINX and Postgres on my home network. It was so fascinating reading your technical articles because I don’t see a stack like yours in my day to day. Not a production one anyway. Just what I have strung together at home with an old HP Core 2 Compaq acting as a server. Which I obviously can’t get much out of.

    I’d just like to see mire articles talking about things like do you use virtualenv in production, why or why not. Are you using UWSGI or something else and why.

    I understand IF has grown quite a bit and you probably don’t have time to write technical articles while focusing on the day to day. And you’re probably more concerned about security now that you handle credit card info, but I assume you offload your PCI responsiblity to someone else. And even hearing you guys talk about how you handle PCI would be interesting to read. I mean if you offload that responsibility to mediate the risk. But then again you can’t realy share a lot of that.

    I just want to know more about your setup and why you do things a certain way. I’m very happy you guys got a design that is working for you. I remember checking the site constantly because you guys were changing the interface so often until you landed on the current one.

    I will continue to check the site and see what’s new! I wish you guys all the best. Thanks for inspiring me.