Home » Posts tagged 'Algorithms'
Tag Archives: Algorithms
Implementing a moving average
Known by many names, such as as Cumulative Moving Average, Rolling Average, Running Average, Moving Mean or Rolling Mean, the object is to update an average value on receipt of a new value over a set window size.
Example:
Imagine we have accumulated 10 values and our window size is 10.
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
The average of this sequence is (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) / 10 = 5.5
We now add a new sample, 11 to the sequence. As the windows size is 10, we drop the first value.
[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
The average of this sequence is (2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) / 10 = 6.5
Now, averaging over 10 samples each time is not that big an issue, but what if it’s 1000 or 10,000? Then, the overhead, both in processing time and storage has statrted to become a little excessive. In the case of 10,000 samples of ‘double’ we are looking at 10,000 additions + 1 division each time a sample is added and a likely storage requirement of 80,000 bytes!
So we have an algorithm that has processing and storage complexity of O(N).
So let’s look at the problem again.
There are many ways of getting the same average:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] = Average of 5.5
[ 7, 7, 7, 7, 7, 4, 4, 4, 4, 4 ] = Average of 5.5
But what about this?
[ 5.5, 5.5 , 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5 ] = Average of 5.5
An average of 5.5 can be got from 10 samples of 5.5. So why store 10 samples? We can simply simulate the original sum just by multiplying the current average by the number of samples!
The calculation of the average for adding a new sample becomes this:
((Old_Average * Sample_Size) + New_Sample) / (Sample_Size + 1)
Now we have 1 multiplication, 2 additions and 1 division.
Our algorithm now has a complexity of O(1).
We can average over as large a sample size as we like and it will always take the same amount of time and use the same amount of storage. We can also change the sample size on-the-fly if we wish.
There is one downside in that the average will not exactly match the original version, as the actual oldest value is not being erased from the sum. But for the performance and storage advantages it may be a perfectly suitable solution. You may find that you will need a slightly smaller sample size with the rolling mean to get similar results.
UPDATE:
The multiplication may be elided by re-arranging the formula.
Old_Average + ((New_Sample – Old_Average) / (Sample_Size + 1))
This may produce a negative interim value, which may be a problem if you are using scaled unsigned integral types for the average value.
Scanning an arbitrarily rotated rectangular region
Quite often in image processing we need to scan a rectangular region in an image. The region is usually aligned to capture a specific feature in the image. You may be presented with a skewed image, necessitating that the region should also be skewed.
If it is not absolutely necessary to scan the region at the angle of skew, then the fastest way to interrogate the pixels is to scan the image horizontally.
As was shown in the previous post, the crossing points between two lines can be easily and efficiently determined.
By moving a reference line down across the region, the start and end x coordinates of each scan line can be found.
Only the y coordinate of the reference line is relevant, though it must have a length of at least 1 unit.
Of course, we must check every line in the rectangle, and every line in the rectangle may produce a crossing point.
The reference line shown below will identify points P1, P2, P3 and P4 as valid crossing points.
The solution is to compare the crossing coordinates against the bounds of the enclosing rectangle. In the example above this would eliminate points P1 and P4.
Vertical scans may be easily achieved by simply having a vertical reference line.
This technique can be applied to any convex hull.
Finding the crossing points of two lines
This is a task that has come up for me many times when creating algorithms for images analysis. Searching the web will invariably turn up the y = Mx + C solution. This is sub-optimal in two ways. First, it has big problems with vertical lines. As the line tends to vertical then m will tend to infinity. This Is Not Good. Secondly, getting any sort of accuracy is impossible without using floating point or large scaling factors.
The code I was modifying at the time was using the y = Mx + C method. It was fairly complex and had to check for lines that were nearly vertical, and flip the axes. It had bugs. I had this gut feeling that must be a better way to solve this, without all of the messing about with edge cases.
Finally after a bit of Googling I came across the lesser used form for describing lines, C = Ax + By. Having lines described in this slightly different form allows a method to find crossing points that is much more code friendly.
Most image processing algorithms I have created work perfectly fine when pixel coordinates are restricted to integral values, allowing integer maths for the following example.
Take two lines, L1 = x1,y1 to x2,y2 and L2 = x3,y3 to x4,y4.
Calculate the values of A, B and C for each line.
For L1:
A1 = y2 – y1
B1 = x1 – x2
C1 = (A1 * x1) + (B1 * y1)
And similarly for L2:
A2 = y4 – y3
B2 = x3 – x4
C2 = (A2 * x3) + (B2 * y3)
Next, work out the determinant.
D = (A1 * B2) – (A2 * B1)
If D is zero then the lines are parallel and there is no crossing point to be found.
If D is not zero then the coordinates of the crossing point may be found thus:
X = ((B2 * C1) – (B1 * C2)) / D
Y = ((A1 * C2) – (A2 * C1)) / D
The two lines do not have to actually cross for this to work. This makes it a great way to find all of the crossing points relative to a reference line.
Next time I will show you how this technique can allow you to scan a rectangular region that is at an arbitrary angle.
Applications of dot and cross products
The problem
Sometimes in graphical applications there is a need to know the relative position of a point with respect to a line from a reference point.
Where is the target in relation to the reference and its direction?
Dot and cross products can make this an easy task.
Let’s start with a reminder of what dot and cross products are.
Take two vectors x1 , y1 and x2 , y2
The dot product is (x1 * x2) + (y1 * y2) and the cross product is (x1 * y2) – (x2 * y1)
Take the example above. We have a reference object at Xr,Yr facing in the direction of the arrow.
The target is at point Xt,Yt
A arbitrary point on the line from the reference in the specified direction is Xw,Yw
First, find the relative coordinates of the target and waypoint relative to the reference.
dXw = Xw – Xr
dYw = Yw – Yr
dXt = Xt – Xr
dYt = Yt – Yr
Now find the dot and cross products of these vectors.
Dot = (dXw * dXt) + (dYw * dYt)
Cross = (dXw * dYt) – (dXt * dYw)
Assuming the coordinate system is as below.
Dot > 0, Cross < 0 : The target is forward of the reference and to the right.
Dot > 0, Cross > 0 : The target is forward of the reference and to the left.
Dot < 0, Cross < 0 : The target is behind the reference and to the right.
Dot < 0, Cross > 0 : The target is behind the reference and to the left.
‘Forward’, ‘Behind’, ‘Left’ and ‘Right’ are relative to the reference’s direction. This calculation will be correct for any direction.
Other uses
This technique can also be used to determine if a point is within a closed convex hull.
A closed convex hull defined by the lines L1, L2, L3, L4 L5.
Point P1 is inside the hull, point P2 is outside.
For P1, the cross product for all of the lines will indicate that the it is to the right and therefore, must be inside.
For P2, the cross product for L1 will put it on the left hand side and therefore it cannot be inside the hull.
Why does this work?
The dot product of vectors A and B is |A||B|cos(Ø)
The cross product of vectors A and B is |A||B|sin(Ø)
Where Ø is the angle between the vectors A and B. Range +-180°
Therefore the sign of the result indicates the quadrant that target occupies in the circle around the reference, relative to the reference’s direction.
Recent Comments