Pattern recognization algorithms

Cogman

Lifer
Sep 19, 2000
10,283
134
106
So I have a picture coming in. I want to have an AI that can see the picture, tell if it is part of another master picture, and then output the coordinates of that spot.. The picture can be rotated, colors distorted, and unentered. (IE, think of getting a piece of a map and then finding where you are based off of that information).

My initial thoughts are to use a neural network to do the pattern matching, but I can't help but feel that the variability of the input, and the amount of needed information from the output would be too much for a neural network (I especially see it having difficulties "seeing" a rotated image correctly).

What else could be used in a project like this? Or are there neural networks that might be able to hack it?

(In the best case, I would like to be able to give the AI a section of the map, randomly located, and randomly rotated, and then have the AI post a route to get from where it is to some location)
 

bobsmith1492

Diamond Member
Feb 21, 2004
3,875
3
81
I just learned about optimal filters the other day at work; this sounds like a potential application.

Here is a decent summary:
http://www.dspguide.com/ch17/3.htm

Basically you take your reference signal and convolve it with your incoming signal. The closer they match, the higher output signal you will get.

In your case, you would divide the map up into small pieces and check your incoming picture against each piece. Whichever convolution results in the highest output signal is the closest match; then, you can decide if you want a threshold to filter out images that don't match anything.
 

CycloWizard

Lifer
Sep 10, 2001
12,348
1
81
I agree with bobsmith: filters should go a long way. For your application, you might even be able to use a lookup table, since there are only a finite number of possible matches. Of course, the feasibility of this approach depends on the size of your master image.
 

Cogman

Lifer
Sep 19, 2000
10,283
134
106
Originally posted by: CycloWizard
I agree with bobsmith: filters should go a long way. For your application, you might even be able to use a lookup table, since there are only a finite number of possible matches. Of course, the feasibility of this approach depends on the size of your master image.

not feasable, the master image is too big and the search needs to be done to fast.

So if I'm understanding this correct, the filter method basically consists of parsing the image into a wave form and then looking for the waves the match the closest, correct?
 

Minas

Junior Member
Jul 27, 2009
18
0
0
I suspect that rotation will be the biggest matching problem, whichever method you use.

My first inclination would be to reduce the complexity by pre-processing the random image section. Edge detection would probably be a start.
 

Knavish

Senior member
May 17, 2002
910
3
81
If you're worried about speed, you definitely need to do a multi-resolution search. For example, rescale the big image and the sample image to 1/4 size & do a correlation search. Now you can threshold based on this correlation and you'll have a small subset of the image to search at 1/2 resolution. Repeat the procedure at 1/2 resolution and you'll just have a few areas you need to search at full resolution.

Piece of cake! LOL
 
May 11, 2008
20,272
1,151
126
If you want to get an easy start, A friend of mine showed me roborealms.

roborealms

I have not used it yet and i am sure it is limited but if you want to start somewhere, roborealm can maybe help you. I am planning on using it just to understand the fundamentals of pattern recognition. Although if you want to write your own software i suggest by googling and reading all the papers on pattern recognition done by insects and sealife. I have read some interesting things in the past. For example how a fly uses it's eyes to determine it's vertical position by comparing relative speeds of the ground moving below it. The faster the ground moves, the closer the fly is to the ground.

I think that at least it is a good start to understand the fundamentals.

Pretty soon i will have an ARM7 development pcb and i can finally start developing on it.
Later i will combine AMR7 USB powered pheriperals with for example a small x86powered pcb like the one in an eeeBOX from asus.

Anyway, good luck...



EDIT
: removed some typing errors.
 
Dec 30, 2004
12,553
2
76
Originally posted by: William Gaatjes
If you want to get an easy start, A friend of mine showed me roborealms.

roborealms

I have not used it yet and i am sure it is limited but if you want to start somewhere, roborealm can maybe help you. I am planning on using it just to understand the fundamentals of pattern recognition. Although if you want to write your own software i suggest by googling and reading all the papers on pattern recognition done by insects and sealife. I have read some interesting things in the past. For example how a fly uses it's eyes to determine it's vertical position by comparing relative speeds of the ground moving below it. The faster the ground moves, the closer the fly is to the ground.

I think that at least it is a good start to understand the fundamentals.

Pretty soon i will have an ARM7 development pcb and i can finally start developing on it.
Later i will combine AMR7 USB powered pheriperals with for example a small x86powered pcb like the one in an eeeBOX from asus.

Anyway, good luck...



EDIT
: removed some typing errors.

Mind telling us your application? Sounds fun.
 
May 11, 2008
20,272
1,151
126
Originally posted by: soccerballtux

Mind telling us your application? Sounds fun.


At first some handy tools to get to know the hardware and when i feel comfortable with the hardware : Robotics.

I plan on buying this development board to start : SAM7-P256 .

May not be the most modern ARM version today but it is a good start.
And it has DMA which comes in handy for datatransfers without putting a burden on the cpu.

Olimex

I can design pcb's circuits, electronic circuits, software and some basic mechanical devices.
And i will use those skills to design sensor circuitry with USB connections.

I just want to build some good sensors/ actuator controls and connect them with a big brain which would maybe be the eeebox. But i might as well end up with another x86 board. I am still hoping AMD wakes up and comes with a 5W version of the Athlon. I think that an Athlon XP Barton style cpu build on a modern process could easily be a 2,5 to 5 Watt cpu while being 4 times as fast as an Atom. But unfortunately AMD will not see the netbook market or the very low power/high performance x86 market. When Intel has a huge market share AMD will wake up.

When it coms to robotics i think the trick is in replicating the outside world in a compressed form inside a 3d world in memory/hardrive . Our brains do that in essence. Everything we know around as becomes an extention of our inner representation of our body.

And since a lot of people build 3d engines, what i would like to do is build a robotic device that is able to map the world around it by only using what is relevant.
Like for instance a set of rules that are basically questions ?

Like for example : "What is solid" ?
The idea is to create a lot of lookup tables where each table is a question. And each question is based on a sensor or a combination of sensors. What will happen is during mapping multiple sensors give readings and a structure is build up with lookuptable entries. Now the combination of these lookuptable entries are stored in the 3d representation. When you would then run the 3d engine in a simulation, it should be possible to get in the real world from point a to point b.
But this all depends on basic principles.

If i would ever have the chance i would like to build some highly parallel imaging camera where all the time seperate processors all have 1 simple task but essentially do that task all the time. Tasks like seek for a circle, seek for a rectangle, seek for a horizontall plane when comparing horizontal plane with data from a gyroscoop. Seek a triangle, seek a square.
Seek for a vertical plane compared with data from a gyroscoop. That is in essence what our brains do. We just programs our brains as a child to not only seek circles but also seek characters like 1 or S.

When we see something that seem solid we touch it to make sure. But if we would have sonar we could also use that sonar to verify what we see is a solid "thing". When you look at how children learn or think back how you did it when you where a child, a hot stove is not hot untill you touched it. The same goes for everything else we encounter as a child.
The tricky part is not building lookup tables or structures that map all this information. The tricky part is to how to combine all that data in the inner 3d world. That is for me a big question and i hope to be sparked with ideas when i have my advanced sensors and software capable of using and categorizing al the information from the sensors.

That is where i think that GPS receivers are fun, but overkill when for instance mapping a room. GPS is interesting whel crossing a large distance. But in essence in this case too you translate the place you want to be in a set of coördinates and vice versa.

This all afcourse is my opinion.

 
May 11, 2008
20,272
1,151
126
I forgot to add something, Let's take the eye for example.

I had this idea that when you have a camera , you can use the feedback signal of the focus to determine the z axis or depth from different objects that you can see with the camera. I am sure our brains use the feedback from the fous to learn as well.

Lets say that you have some servo circuit controlling the focus of the lens objective.
When something is close, the feedback signal has a certain value. When you focus on something that is more far away, you have the previous value minus the difference for the new focus value. In this way you know that what you see now, must be further away just because the value is smaller. With this approach, you do not need an absolute value. Just the fact that there is a difference is enough. And the sign determines if what you are focused on now is further away then the previous object or closer then the previous object. Take 2 camera's and you have pretty good depth vision for a robotic device.

Determining if something is in focus is just driving the servo until the difference between adjacent pixels is large. At least that is the easy way. I am sure the camera manufacturers have some great algorithms for autofocus.

Now combine that with a system that is non stop searching for geometric objects and who knows...




 

CycloWizard

Lifer
Sep 10, 2001
12,348
1
81
Originally posted by: William Gaatjes
I forgot to add something, Let's take the eye for example.

I had this idea that when you have a camera , you can use the feedback signal of the focus to determine the z axis or depth from different objects that you can see with the camera. I am sure our brains use the feedback from the fous to learn as well.

Lets say that you have some servo circuit controlling the focus of the lens objective.
When something is close, the feedback signal has a certain value. When you focus on something that is more far away, you have the previous value minus the difference for the new focus value. In this way you know that what you see now, must be further away just because the value is smaller. With this approach, you do not need an absolute value. Just the fact that there is a difference is enough. And the sign determines if what you are focused on now is further away then the previous object or closer then the previous object. Take 2 camera's and you have pretty good depth vision for a robotic device.

Determining if something is in focus is just driving the servo until the difference between adjacent pixels is large. At least that is the easy way. I am sure the camera manufacturers have some great algorithms for autofocus.

Now combine that with a system that is non stop searching for geometric objects and who knows...
I did this about three years ago. I connected a motor to a webcam and used it to measure the focal length of a lens from the eye by moving along the optic axis until a target (on the other side of the lens) was optimally in focus. The method I used was to use a black and white target, then maximize the image intensity.

This is similar to what you're proposing, but different in a few key ways. The first is that I had a well-defined target with some known properties. This is the same scenario used by ophthalmologists and optometrists because even the human eye/brain system has a hard time discerning whether objects of similar colors which have non-straight edges. A digital system could handle non-round images better because it would obviously lack the intrinsic edge-finding algorithm that the eye has (lateral inhibition), but would still have a very hard time measuring contrast with a high degree of accuracy when two objects of similar color are near each other. Still, it can probably be done, given that the hardware and software are of sufficient quality to achieve the desired resolution, so let me know if you want any input from someone who has done something similar.
 
May 11, 2008
20,272
1,151
126
When the time comes i will, thank you.
Perhaps this will be an effort of many people with similair thoughts but different skills...

Finally we communicate.

 

imgod2u

Senior member
Sep 16, 2000
993
0
0
The simplest way, as others mentioned, is to perform a correlation from pieces of the image. But since the relative size is unknown, your best bet (depending on processing speed limitations) might be either FFT or Wavelet-based correlation.

Treat your sample image as a 2D mother wavelet and then run a wavelet analysis on the master image. Your highest point of time/scale correlation should be the match.
 

Shalmanese

Platinum Member
Sep 29, 2000
2,157
0
0
Another way of doing it would be to run the SIFT algorithm to find points of interest and then do matching based on that.
 
Dec 30, 2004
12,553
2
76
Originally posted by: William Gaatjes
When the time comes i will, thank you.
Perhaps this will be an effort of many people with similair thoughts but different skills...

Finally we communicate.

You'd better be a flipping genius because image processing code you're talking about is insanely tricky to write. I salute you for the endeavor.
 
May 11, 2008
20,272
1,151
126
Originally posted by: soccerballtux
Originally posted by: William Gaatjes
When the time comes i will, thank you.
Perhaps this will be an effort of many people with similair thoughts but different skills...

Finally we communicate.

You'd better be a flipping genius because image processing code you're talking about is insanely tricky to write. I salute you for the endeavor.


This will not be a lonely endavour. Friends/colleagues at my work, and friends outside of my work are interested too and willing to make this a collective effort. And afcourse at least here on the anandtech i am confident there are people who when we would all work together could and want to join forces too. Maybe one day the world will have not only an open source kernel and operating system for general use but also an open source robotic operating system. Optimized software together with optimized hardware designs. All open source.


But i agree.
Although i am not a dumb guy, my knowledge has it's limits too as do i have myself.
If i would win the lottery and i never have to worry about paying bills, i would devote my life instead of 8 hour work a day into 8 hours a day of collecting all the information i need to gather. And do testing, thinking, sharing, discussing and designing with others. And not only about robotics but about energy harvesting and genetics as well. But that would be a dream come too.

A man needs his dreams .
 

will889

Golden Member
Sep 15, 2003
1,463
5
81
Originally posted by: William Gaatjes
Originally posted by: soccerballtux
Originally posted by: William Gaatjes
When the time comes i will, thank you.
Perhaps this will be an effort of many people with similair thoughts but different skills...

Finally we communicate.

You'd better be a flipping genius because image processing code you're talking about is insanely tricky to write. I salute you for the endeavor.


This will not be a lonely endavour. Friends/colleagues at my work, and friends outside of my work are interested too and willing to make this a collective effort. And afcourse at least here on the anandtech i am confident there are people who when we would all work together could and want to join forces too. Maybe one day the world will have not only an open source kernel and operating system for general use but also an open source robotic operating system. Optimized software together with optimized hardware designs. All open source.


But i agree.
Although i am not a dumb guy, my knowledge has it's limits too as do i have myself.
If i would win the lottery and i never have to worry about paying bills, i would devote my life instead of 8 hour work a day into 8 hours a day of collecting all the information i need to gather. And do testing, thinking, sharing, discussing and designing with others. And not only about robotics but about energy harvesting and genetics as well. But that would be a dream come too.

A man needs his dreams .



Agreed - even with a degree in physics I went into a totally different field.
 
May 11, 2008
20,272
1,151
126
Originally posted by: will889
Originally posted by: William Gaatjes
Originally posted by: soccerballtux
Originally posted by: William Gaatjes
When the time comes i will, thank you.
Perhaps this will be an effort of many people with similair thoughts but different skills...

Finally we communicate.

You'd better be a flipping genius because image processing code you're talking about is insanely tricky to write. I salute you for the endeavor.


This will not be a lonely endavour. Friends/colleagues at my work, and friends outside of my work are interested too and willing to make this a collective effort. And afcourse at least here on the anandtech i am confident there are people who when we would all work together could and want to join forces too. Maybe one day the world will have not only an open source kernel and operating system for general use but also an open source robotic operating system. Optimized software together with optimized hardware designs. All open source.


But i agree.
Although i am not a dumb guy, my knowledge has it's limits too as do i have myself.
If i would win the lottery and i never have to worry about paying bills, i would devote my life instead of 8 hour work a day into 8 hours a day of collecting all the information i need to gather. And do testing, thinking, sharing, discussing and designing with others. And not only about robotics but about energy harvesting and genetics as well. But that would be a dream come too.

A man needs his dreams .



Agreed - even with a degree in physics I went into a totally different field.


Now i really have to ask

What is your dream ?

Is it physics or the totally different field ?
 
sale-70-410-exam    | Exam-200-125-pdf    | we-sale-70-410-exam    | hot-sale-70-410-exam    | Latest-exam-700-603-Dumps    | Dumps-98-363-exams-date    | Certs-200-125-date    | Dumps-300-075-exams-date    | hot-sale-book-C8010-726-book    | Hot-Sale-200-310-Exam    | Exam-Description-200-310-dumps?    | hot-sale-book-200-125-book    | Latest-Updated-300-209-Exam    | Dumps-210-260-exams-date    | Download-200-125-Exam-PDF    | Exam-Description-300-101-dumps    | Certs-300-101-date    | Hot-Sale-300-075-Exam    | Latest-exam-200-125-Dumps    | Exam-Description-200-125-dumps    | Latest-Updated-300-075-Exam    | hot-sale-book-210-260-book    | Dumps-200-901-exams-date    | Certs-200-901-date    | Latest-exam-1Z0-062-Dumps    | Hot-Sale-1Z0-062-Exam    | Certs-CSSLP-date    | 100%-Pass-70-383-Exams    | Latest-JN0-360-real-exam-questions    | 100%-Pass-4A0-100-Real-Exam-Questions    | Dumps-300-135-exams-date    | Passed-200-105-Tech-Exams    | Latest-Updated-200-310-Exam    | Download-300-070-Exam-PDF    | Hot-Sale-JN0-360-Exam    | 100%-Pass-JN0-360-Exams    | 100%-Pass-JN0-360-Real-Exam-Questions    | Dumps-JN0-360-exams-date    | Exam-Description-1Z0-876-dumps    | Latest-exam-1Z0-876-Dumps    | Dumps-HPE0-Y53-exams-date    | 2017-Latest-HPE0-Y53-Exam    | 100%-Pass-HPE0-Y53-Real-Exam-Questions    | Pass-4A0-100-Exam    | Latest-4A0-100-Questions    | Dumps-98-365-exams-date    | 2017-Latest-98-365-Exam    | 100%-Pass-VCS-254-Exams    | 2017-Latest-VCS-273-Exam    | Dumps-200-355-exams-date    | 2017-Latest-300-320-Exam    | Pass-300-101-Exam    | 100%-Pass-300-115-Exams    |
http://www.portvapes.co.uk/    | http://www.portvapes.co.uk/    |