|
Hi,
I have a number of still images containing concentric circles and I would like to be able to detect the centre point of the circles. Are there any algorithms out there that would allow me to do this?
Cheers,
Tony
|
|
|
|
|
the "Generalised Hough transform" may help
havent seen the code tho.
|
|
|
|
|
So if you're not familiar (or comfortable with making yourself familiar) with complex numbers, this may be a little useless, but here is my first guess as to how to do it.
You should be able to find a conformal mapping (look it up on wikipedia, it's basically a function that takes lines to lines and circles to circles, preserving angles, if I remember correctly), and I actually think you want a specific type of conformal mapping called a Mobius Transformation (also look that up on wikipedia - it's a function of the form f(z) = (az + b)/(cz+d), where a,b,c, and d are complex numbers and ad - bc != 0). Moreover, I think the function is just 1/z (where z is a complex number), but you'd want to double check that.
Anyway, there should be a Mobius Transformation that will transform your image so that your concentric circles are mapped to parallel lines, which I would imagine would be much easier to find, especially if the concentric circles are regularly spaced out. From there, you could either find the center point on your mapped image, and then take its inverse under your Mobius Transformation to find the original point, or you could find the lines and map those back through the Mobius Transformation. Then you'd basically have explicit equations for each of the circles that you could use to find your center points.
So check out these Mobius Transformations; if you've got the math background, I suspect they would make your problem much easier. Mobius Transformation followed by the basic Hough Transform referenced above (not the generalized form necessarily -- if you do that, you shouldn't have to do any of this MT stuff) should solve your problem, for instance.
|
|
|
|
|
Some ideas given here seem good, but they will tend to be computationally heavy. My work involves real time image processing in many domains, and in general most algorithms that are called "transform" are usually unacceptably slow (even for modern computers or DSP's). This, of course, depends on wether or not you can distribute the algorithm through various machines. In general I can't.
Anyway, without more details on your case I simply imagine white sheets of paper with concentric circles drawn in them. If this is the case then finding the center is a very fast and efficient operation.
Simply compute the mass center of all "pen" pixels. For example, if they are black then just sum the positions where you find them (keep X and Y separate) and in the end just divide the result by the image size. For example:
mass_center_x=0;
mass_center_y=0;
total_found=0;
for(y=0; y<image_size_y; y++) {
for(x=0; x<image_size_x; x++) {
if (Pixel(x, y)==BLACK) {
mass_center_x+=x;
mass_center_y+=y;
total_found++;
}
}
}
if (total_found>0) {
mass_center_x/=total_found;
mass_center_y/=total_found;
}
At this point the "mass_center_x" and "mass_center_y" contain the coordinates of the center of the concentric circles. This algorithm is very fast because each pixel is analyzed only once, and so runs in an amount of time directly proportional to the number of pixels. Also note that Y is the outer loop so as to exploit the CPU cache in the most efficient manner.
I hope this helps,
Rilhas
-- modified at 8:28 Sunday 20th May, 2007
|
|
|
|
|
I need help to implement the genetic algorithm to find the minimum spanning tree of a graph.(if possible in Matlab)
I have the program to generate different random spanning trees but to implement into the initial population.???
program to generate random spanning tree:
% To make random spanning tree from the adjacency matrix of a graph<br />
% Where A is the adjacency matrix<br />
<br />
<br />
n = length(A);<br />
Ta = sparse(n,n);<br />
comps = [1:n];<br />
<br />
for its = 1:(n-1),<br />
[ii,jj,vv] = find(A);<br />
r = ceil(rand(1)*length(ii));<br />
Ta(ii(r),jj(r)) = 1;<br />
comp = comps(jj(r));<br />
comps(comps == comps(ii(r))) = comp;<br />
nodes = find(comps == comp);<br />
<br />
for n = nodes;<br />
nds = find(A(n,nodes));<br />
A(n,nodes(nds)) = 0;<br />
end<br />
<br />
% A(nodes,nodes) = 0;<br />
end<br />
Ta = Ta + Ta';
an other problem is that the above program give an edge list not a adjacency list so to implement the initial population is not really easy.
If somebody can help me 
clem
|
|
|
|
|
|
Unfortunately, i don't want use the Prim's algorithm or Kruskal's algorithm but the a genetic algorithm.
|
|
|
|
|
Why - has it better performance?
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: Why - has it better performance?
No, because that's the homework assignment. 
|
|
|
|
|
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do?
Using both O(n^2) and O(n).
|
|
|
|
|
I do brutal
for (i=0 ; i < iMax-1; i++)
{
int temp = a[i];
if (temp > 51) continue;
for ( j=i+1; j < iMax; j++)
{
if (temp + a[j] == 51)
{
}
}
}
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
Good, but this is the O(n^2), do you know the n's ?
|
|
|
|
|
LongHC wrote: Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do?
First, determine how to break the number down into two numbers whose sum is the original number. Instead of 51, let's pick a smaller number, say 11. Here are the numbers whose sum is 11:
11 + 0 = 11
10 + 1 = 11
9 + 2 = 11
8 + 3 = 11
7 + 4 = 11
6 + 5 = 11
To find these numbers, we can start with two values: the original number and zero, call these x and y. Run a loop in which 1 is subtracted from x and 1 is added to y at each iteration. Continue the loop until x is less than y:
int x = 11;
int y = 0;
while(x > y)
{
x--;
y++;
}
Now, we need to search for these values in our array. It would be helpful to have our array sorted first. Then at each iteration through the loop, we perform a binary search for x an y and store the indexes to the numbers in a list, if they are in the array. We'll assume that the binary search returns -1 if the number isn't in the array:
Sort(array);
List list;
int x = 11;
int y = 0;
while(x > y)
{
int index = BinarySearch(array, x);
if(index >= 0)
{
list.Add(index);
}
index = BinarySearch(array, y);
if(index >= 0)
{
list.Add(index);
}
x--;
y++;
}
Note: this algorithm is off the top of my head. There may be better ways of doing this.
[EDIT] My algorithm doesn't take into account possible duplicates in the array.  [/EDIT]
-- modified at 10:54 Friday 13th April, 2007
|
|
|
|
|
If the integers are positive, then I can think of an O(n) solution. As this sounds like homework I will just give a hint - try using an array of 51 integers.
If the integers are unbounded then I can't see an O(n) solution.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: If the integers are positive, then I can think of an O(n) solution.
They are +ve numbers.
cp9876 wrote: As this sounds like homework
In fact this is not, I just came by this problem while reading and I tried so much in it and didn't get to any thing.
|
|
|
|
|
In that case, start with an array of 51 numbers c[i] initialised to -1.
for (int i = 0 ; i < 51 ; i++)
{
if (a[i] < 51)
{
int n = 51 - a[i];
if (c[n] >= 0)
{
}
else
{
c[n] = i;
}
}
}
Basically, for each element, store its location where its complement can find it
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thanks for your solution and for Leslie's one.
|
|
|
|
|
A few years ago, I wrote a Skip List[^] class in C#. I've found this data structure to be handy. For one thing, it's easily adapted to a priority queue[^].
What I'd like to do is add the ability to access items in the skip list by index, e.g. give me the n'th item in the list. This is easy enough to do in O(N) time by simply starting at the beginning of the list and moving one by one through the list until you've reached the desired item. I was looking for a better way. Kunth decribes a way to do this with binary search trees. I'd like to find the equivalent algorithm for skip lists.
William Pugh, the skip list's inventor, decribes a way in his skip list cookbook[^]. But his algorithm assumes the existance of a "distance" field in each node. The distance field represents the next nodes position minus the current nodes position.
I didn't find this very helpful. It requires each node and each pointer level to know their position in the list. Well, if they know that already, then it's easy enough to search for the specified item by position to begin with.
It would be easy enough to add a position field to each node. The position would represent the node's index into the list. The problem becomes trying to maintain this field as items are added and removed from the list. Descructive operations will make the position value of all subsequent nodes invalid.
This may be a problem where there isn't a solution, at least not one that works as well as the binary search tree approach. Anyway, I'd appreciate any insights.
|
|
|
|
|
Hi,
I think the distance field is the right way to go; you can fill it while populating
the skip list at very modest cost. And its update needs are limited, whereas an
absolute index field would require expensive updating when new nodes get added.
|
|
|
|
|
Well, I'm embarrassed to say it, but I just noticed the "InsertByPosition" algorithm at the end of William Pugh's cookbook paper; I hadn't looked at it when I made my original post. Looks like the algorithm for managing the distance field is right there.
|
|
|
|
|
|
I am impressed.
I kinda wish i wasn't... but i am...
|
|
|
|
|
Guys I'm very stuck.I've searched the web for the past three weeks for a class written in C# that has low pass, high pass, Band pass filters which I could used for my third year project data analysis. I'm very desperate and my eyes are bloody red right now due to lack sleep; please help...
I believe there are alot of geniuses in this forum who cannot be stopped by anything..Looking forward to receiving your help...
Cheers
kel
|
|
|
|
|
Write your own! I did when I was in college, though we didn't have fancy languages like C#. It took all of a few hours and was a great learning tool (for filter theory, not programming).
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
|
|
|
|
|
I was going to make the same comment. It is after all a project on data analysis. It shouldn't take too long to write some basic filters. Get some basic filtering routines going, initially use matlab or similar to calculate the coefficients, work up to doing your own. If you are stuck, look at some of the c++ signal processing libraries - the code should be similar.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
