Pattern Matching (specific question)

asked 2015-03-30 02:10:30 -0600

KansaiRobot
124 ●2 ●4 ●8

Hello and thanks always for your help.

I have asked a rather general question regarding pattern matching. This time I would ask something more specific. Let's suppose I have a camera that points to an area where objects of several patterns are put. I want to find objects of a specific shape but with no regard for the size of these objects or their orientation.

To do this I build an "artificial image" (meaning not something out of a camera) and use it as "model". Take a look at the following:

A "bullet" shape model

This "bullet shape" is the shape of the object I want to find. You can see I build it artificially from a rectangle and a semicircle, and that it can have any orientation.

So what I want to do is to , once I have this "model" find objects in my camera image that resemble this model but vary in size and orientation.

Any idea on how to do this? Any pointers, advice or ideas would be greatly appreciated.

edit retag flag offensive close merge delete

Comments

Hi,

I would go on methods relative to shape-based detection like Chamfer matching:

Eduardo ( 2015-03-30 04:06:38 -0600 )edit

Thank you for your comment. Is this method robust to rotation and scaling?

Right now I am reading about keypoints, SURF and SIFT. Can't say I see the light at the end of the tunnel yet...

KansaiRobot ( 2015-03-31 02:46:18 -0600 )edit

In my opinion detection based upon keypoints won't help you much because there is no texture on images you show.

The basic Chamfer matching is not rotation nor scale invariant but there are extended methods that deal better with these cases and you can also manually rotate the images.

If your query images are relative simple (only basic shapes, no cluttered background, ...), you can try to detect the half-circle and the rectangle like Florian Castellane said.

Eduardo ( 2015-03-31 05:19:18 -0600 )edit

Have you checked Halcon library?

Sagar9172 ( 2017-10-30 23:45:13 -0600 )edit

Yes, I worked with halcon for a while. As you can see from my answer I solved this with pure C++ programming. But I don't remember the original motivation of my question so I suspect that I have not solved the difficult cases of finding patterns in ocluded positions.

KansaiRobot ( 2017-10-30 23:49:04 -0600 )edit

Now I have a new question, although related. Please check it

KansaiRobot ( 2017-10-30 23:49:53 -0600 )edit

add a comment

3 answers

Sort by » oldest newest most voted

answered 2017-10-30 23:08:45 -0600

KansaiRobot
124 ●2 ●4 ●8

updated 2017-11-09 02:42:19 -0600

More than 2 years after I asked the question, (I didn't know I was looking for something like this on that time) I implemented this. The key is to use border pursuit, and then Fourier descriptors. Now Fourier descriptors are size invariant but not rotation invariant. To make them rotation invariant, I read the excellent book "Feautre Extraction and Image Processing" byNixon and Aguado

However I suspect that on that time (as now too) I was looking for ways to find those patterns when the pattern was inside a bunch of other patterns

Unfortunately - unless the patters are quite separable, the above method won't work.

I am going to describe the process I implemented here in broad terms, if you need a clarification please say so and I will edit >that< part.

The steps I took for recognition of shapes (and it works with letters too) are:

Gray Scaling
Binarization (with histograms)
Labeling
Fourier Descriptor representation
Fourier Descriptor Comparison

Once I finished those, the process was that I showed the camera a shape and take notes of its FD representation. Once I took notes of the shapes I wanted to recognize I edited my code (I know , not fancy- sorry) and introduced that as "models" for the step 5. I reckon that an "automatic" method would have been better though. Also take into account that I implemented this all by myself without using OpenCV functions but I think equivalent functions can be found, so if you do, share your knowledge

1. Gray Scaling

Here I simply scan the image pixel by pixel and multiplied the RGB elements to find the Y element. In theory this is: Y=0.2990R+0.587G+0.114B but I used integer equivalent integer constants that were a multiply of these and later I shifted the result. This is because integer calculation is faster.

(At the same time, I built a histogram -since i was scanning the pixels already, - I know it is not good modular design but anyway it works. This histogram is going to be used in the next step

2. Binarization

I did not want to use a binarization in which I had to manually give a threshold so I use the histogram for automatic thresholding. In the case I am commenting I think I used the method called "Mode method" but I am not sure since I work in japanese actually. Anyway, the method is basically take the histogram that was constructed in the previous step and find the two tallest peaks. Then find the lowest valley between them and set the threshold there.

In a different application I have used the "Discriminant analysis Method". It also works well but I have not made comparisons

3. Labeling

Labeling involves a little complicated procedure. I am not sure I will be able to explain it here very well but it basically involves scanning the image pixel by pixel, processing only the white pixels (the blacks are background), then when finding ... (more)

edit flag offensive delete link

Comments

I was trying to achieve a similar task and I ended up using Hausdorff distance. I answered a similar question on SO.

eshirima ( 2017-10-31 08:07:17 -0600 )edit

At one point I was recommended to use Fourier Descriptors but I am not sure of where to start.. Does OpenCV have a sample tutorial for them? Or could you elaborate on them a bit more?

eshirima ( 2017-10-31 08:08:26 -0600 )edit

Wow, I didn't see your question in SO. That is exactly the problem I solved. To be completely sincere I was quite desperated so in the end I did not use OpenCV, instead I implemented Fourier descriptors by myself. I don't really remember the details right now(I can look it up if you are interested) but the thing worked like this. First I digitalized the image and segmented it (since they are separated there is no problem with that). Then after I performed a border following and I built the Fourier Descriptors based on that. Originally I did till there and the solution was not rotation invariant. But then I found the algorithms in the book of Nixon Aguado which modified the descriptors to make them rotation invariant. With that I performed a simple euclidean comparison

KansaiRobot ( 2017-10-31 19:16:13 -0600 )edit

The last part (comparison) could be replaced with Neural networks as well. But for few model patterns, comparison is enough. Fourier transforms are really useful!. The Nixon Aguado book have another solution but i have not read it yer nor implemented. I will also take a look at what you post

KansaiRobot ( 2017-10-31 19:17:45 -0600 )edit

Thanks a lot. Couple questions. 1: So for my case, I can make my contours define the Fourier descriptors then? 2: What about translations? i.e. your template points are on a different coordinate system to your test image. I take it you performed some sort of translation to put move them to a similar system right? 3: So if I understood the logic, its literally calculating the Fourier descriptors of your template image and those of your test image then finding those with the lowest distance?

eshirima ( 2017-11-01 08:27:58 -0600 )edit

As far as I remember translations have no effect whatsoever once a figure is defined as Fourier descriptors. Meaning that the figure no matter where it is, have the same FD. Actually Translation and Sizing invariance are the easiest requirements. (I don't quite follow your talk about "different coordinate system", I mean translation to me just means moving from one point to another in a coordinate system) You don't need to do anything special for these invariances. It is for rotation invariance that you have to modify a little the FD because originally the same figure will have different FD if it is rotated. And for your last question, yes it basically it is just comparing distances.

KansaiRobot ( 2017-11-02 04:50:14 -0600 )edit

I talked about Neural Networks because when the number of models increase, comparing to each of them takes more time, so in that case training a NN would prove beneficial. But for simplest cases euclidean comparison is enough

KansaiRobot ( 2017-11-02 04:51:24 -0600 )edit

I think I'm almost there but I am a little stuck on how to move forward. So far, I implemented this guy then found their respective magnitudes and downscaled them down to the log scale as per this recommendation. All of this was done in the template/model image. 1: Do I even need to find the magnitudes @ this point? Because I don't see how they can be used for distance comparisons. 2: If the magnitudes are not needed, then I just need to use the raw complex values attained from DFT? 3: You said something about making the DFTs rotation invariant. How did you do that? I thought the results from DFT were already R invariant.

eshirima ( 2017-11-02 10:54:46 -0600 )edit

I do not necessarily need the code but can you edit your answer to at least include an outline of the steps you took to solve the problem? The general algorithm at least for future users.

eshirima ( 2017-11-02 10:59:14 -0600 )edit

Yes, sorry for my late reply. We had a long weekend here. I will do something like this in these days. Hope it can help.

KansaiRobot ( 2017-11-05 18:42:21 -0600 )edit

see more comments

answered 2015-03-31 02:57:35 -0600

Florian Castellane
1 ●1

You may want to look at pattern matching. Techniques using the Fourier-Mellin Transform are invariant to scale and rotation, so they do what you're looking for, but computing said transform can be quite expensive (more than the Fourier transform of the whole image). Alternatively, since the pattern you look for is quite simple, you could look for the half-circle and the lines separately, and then put it all together using the positions.

Since your question is not completely specific to OpenCV, you might want to ask on Stack Exchange as well: http://dsp.stackexchange.com/

Hope this helps.

edit flag offensive delete link

Comments

Thank you for your answer. As a matter of fact, I am looking at how to implement pattern matching in OpenCV. I have used pattern matching with other computer vision tools and now I would like to use openCV to implement it. However when I look in books or homepages I can't find anything similar to what I used to do: -Defining a model, and applying that model on images to find matchings.

How to do this with OpenCV??

KansaiRobot ( 2015-03-31 04:30:14 -0600 )edit

Which computer vision tools did you already use ?

"Defining a model, and applying that model on images to find matchings."

Could you elaborate more ? Do you mean something like template matching ?

Eduardo ( 2015-03-31 05:02:57 -0600 )edit

add a comment