What is the best way to approach this algorithm?

Question

1.50/5 (2 votes)

See more:

Hi,

I am currently working on a project using the AForge Framework. I am trying implement an algorithm called the "three step search". It will be used for motion detection via a webcam.

Three Step Search (TSS) [1,2]

This algorithm was introduced by Koga et al in 1981. It became very popular because of its simplicity and also robust and near optimal performance. It searches for the best motion vectors in a coarse to fine search pattern. The algorithm may be described as:

Step 1: An initial step size is picked. Eight blocks at a distance of step size from the centre (around the centre block) are picked for comparison.

Step 2: The step size is halved. The centre is moved to the point with the minimum distortion.

Steps 1 and 2 are repeated till the step size becomes smaller than 1. A particular path for the convergence of this algorithm is shown below:

http://www.ece.cmu.edu/~ee899/project/r4-1.gif[^]

Fig 2 : Example path for convergence of Three Step Search

Source: http://www.ece.cmu.edu/~ee899/project/deepak_mid.htm[^]

The problem I have having is understanding how the coordinates are set for the part where it says "An initial step size is picked. Eight blocks at a distance of step size from the centre (around the centre block) are picked for comparison."

I do know that these blocks are compared using a formula called mean square error. If I could just figure out a way of creating the search block then it would go a long way in figuring out how to implement the rest of this algorithm. Apologies if this is a bit confusing to understand. I have tried to explain it the best way possible. I could be going about this the total wrong way as I am relatively new to C# and its concepts.

I have been on the Matlab website where I have found the source code for the algorithm but it is written for Matlab which I do not understand.

I have uploaded the Matlab code here is that helps understand it more.

http://pastebin.com/sCKXZhKx[^]

Posted 21-Aug-14 12:02pm

Grad1985

Updated 21-Aug-14 12:54pm

v9

Add a Solution

Comments

Sergey Alexandrovich Kryukov 21-Aug-14 18:18pm

Was that so difficult to present text information in text, not a bitmap? A bitmap is not readable, you cannot copy text. You could publish a link (it's good to give credit, anyway). Also, it would be better to explain: algorithm — for what problem?
—SA

Grad1985 21-Aug-14 18:21pm

I didn't post the link or text because I cannot remember the site that I found the information on. If I find it, I will share it.

Sergey Alexandrovich Kryukov 21-Aug-14 18:33pm

Please do. And please avoid putting text on a bitmap. Actually, all your bitmap could be rendered in HTML and included in your post. Most members avoid loading any images from image storage sites.
—SA

Nathan Minier 22-Aug-14 9:50am

The issue, as I understand it, is determining your STARTING reference quadrants. Your intent is to use a webcam. A webcam has a variable but finite number of possible steps sizes, or quadrants if we want to use that as our unit of consideration, as that's what the steps will refine.

It would appear that your initial quadrants should be defined as a function which segments out the pixels available, which is a variable depending on the capabilities of the camera being used. In this use case, pixels(or blocks of) are your unit of measure to define quadrants.

let x=horizontal pixels, y = vertical pixels

q1 = (0,0) to (x/2-1,y/2-1)
q2 = (x/2,0) to (x,y/2-1)
q3 = (0,y/2) to (x/2-1,y)
q4 = (x/2,y/2) to (x,y)

This is your starting condition.

Grad1985 22-Aug-14 11:52am

This is exactly what I was looking for. I am going to add this later tonight. I will let you know how it goes. Thanks for your help

gggustafson 23-Aug-14 10:27am

+5 Suggest you move this to a Solution.

Nathan Minier 25-Aug-14 8:15am

Agreed, thanks.

Grad1985 26-Aug-14 12:55pm

I can understand this in theory but I am having problems translating it to code. I keep running into this problem when I am trying to create new applications without following tutorials.

Nathan Minier 26-Aug-14 13:23pm

If you're having trouble with the code, then you need to get some basic design theory down before trying to tackle projects that will require anything other than boilerplate.

I will give you some basic advice on it, though.

First, you need a class to define your step. I would have it contain 4 subclasses that define quadrants as well as your center point. After initialization, the quadrants will need to base around that point. I would suggest using System.Drawing.Rectangle for your quadrants, as it has a lot of built-in functionality that will benefit you:

http://msdn.microsoft.com/en-us/library/system.drawing.rectangle%28v=vs.110%29.aspx

Secondly, we need to set our initial state. Let's look at documentation for the framework you intend to use:

http://www.aforgenet.com/framework/docs/html/01c875c5-3556-d700-ec3b-4023bfe81a19.htm

Frame events in the framework you are using are Bitmaps. Bitmaps have properties:
http://msdn.microsoft.com/en-us/library/4e7y164x

Two of those properties are height and width. On your first frame capture, use those properties to slice 4 rectangles out and stow those in your step object. Then you can begin your transforms.

Grad1985 26-Aug-14 13:52pm

Thanks a lot. I appreciate your help.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Nathan Minier · Accepted Answer · 2014-08-25T02:15:00

The issue, as I understand it, is determining your STARTING reference quadrants. Your intent is to use a webcam. A webcam has a variable but finite number of possible steps sizes, or quadrants if we want to use that as our unit of consideration, as that's what the steps will refine.

It would appear that your initial quadrants should be defined as a function which segments out the pixels available, which is a variable depending on the capabilities of the camera being used. In this use case, pixels(or blocks of) are your unit of measure to define quadrants.

let x=horizontal pixels, y = vertical pixels

q1 = (0,0) to (x/2-1,y/2-1)
q2 = (x/2,0) to (x,y/2-1)
q3 = (0,y/2) to (x/2-1,y)
q4 = (x/2,y/2) to (x,y)

This is your starting condition.