RSS News FeedLocating An Image At Arbitrary Scales Translations and Rotatio
Message-ID:<m3ocx0h39l.fsf@local.localhost>
Subject:
Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 03:45:10 +0100
How does one do this? To begin assume the following idealized goal: we have a black background and a white rectangle with aspect ratio \alpha. at an arbitrary scale, translation, and rotation. How do we identify the translation (or location in the x-y plane) and rotation? I am beginning to read the paper, "Coarse-Level Object Recognition Using Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and Fauqueur, but am unsure if this is even the right approach. A question I can't seem to resolve with a quick perusal of the literature is this: Are approaches like those described by Anderson designed to identify *arbitrary* objects in the image that are a-priori unknown, or are they searching for an object that is known (and described somehow)? Obviously I am a beginner in the field, so please make the appropriate allowances. I do know general maths and 1-D signal processing fairly well. -- % Randy Yates % "Midnight, on the water... %% Fuquay-Varina, NC % I saw... the ocean's daughter." %%% 919-577-9882 % 'Can't Get It Out Of My Head' %%%% <yates@ieee.org> % *El Dorado*, Electric Light Orchestra http://www.digitalsignallabs.com
Message-ID:<3c673ea4-6674-45bd-988f-4a59b538d9b8@13g2000yql.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 13:22:53 +0100
On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? > > I am beginning to read the paper, "Coarse-Level Object Recognition Using > Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and > Fauqueur, but am unsure if this is even the right approach. > > A question I can't seem to resolve with a quick perusal of the > literature is this: Are approaches like those described by Anderson > designed to identify *arbitrary* objects in the image that are a-priori > unknown, or are they searching for an object that is known (and > described somehow)? > > Obviously I am a beginner in the field, so please make the appropriate > allowances. I do know general maths and 1-D signal processing fairly > well. In the paper you mention they are trying to find a given image patch in a much larger image. There is no notion of 'object' really, except that represented by an image patch. I am not sure what an 'arbitrary' object would be. There is no mystery here: what do you want to find? illywhacker;
Message-ID:<26e80fed-252b-40ba-8b94-d8a270cd08c4@m42g2000yqb.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 14:19:17 +0100
On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? The problem is that this example leaves out everything that renders such problems difficult. When the 'object', or rather knowledge of the object's parameters, determines precisely the image you expect to see and no two sets of parameters produce the same image, that is, when the image model takes the form: P(I | a) =3D \delta(I, f(a)) , where I is an image, a are the object parameters, and f is a injective function from object parameters to image space, then you simply invert f. This may not be trivial in general, but it is the simplest case. More generally, the image will not be determined given the parameters, and some sets of parameters might be more likely than others (e.g. your rectangle represents a house, so one might expect it to be horizontal, although it need not be). illywhacker;
Message-ID:<m3eixvoe7o.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 18:19:07 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> How does one do this? To begin assume the following idealized goal: we >> have a black background and a white rectangle with aspect ratio \alpha. >> at an arbitrary scale, translation, and rotation. How do we identify the >> translation (or location in the x-y plane) and rotation? > > The problem is that this example leaves out everything that renders > such problems difficult. When the 'object', or rather knowledge of the > object's parameters, determines precisely the image you expect to see > and no two sets of parameters produce the same image, that is, when > the image model takes the form: > > P(I | a) = \delta(I, f(a)) , > > where I is an image, a are the object parameters, and f is a injective > function from object parameters to image space, then you simply invert > f. This may not be trivial in general, but it is the simplest case. Yes, but you don't know f - you only have I. > More generally, the image will not be determined given the parameters, > and some sets of parameters might be more likely than others (e.g. > your rectangle represents a house, so one might expect it to be > horizontal, although it need not be). I appreciate your response, but where's the beef? I leave this post in almost as much confusion as I came. -- % Randy Yates % "Watching all the days go by... %% Fuquay-Varina, NC % Who are you and who am I?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://www.digitalsignallabs.com
Message-ID:<d0c3774c-c0db-4ed3-9cca-199908342675@h20g2000yqn.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 21:49:19 +0100
On Feb 18, 6:19=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > >> How does one do this? To begin assume the following idealized goal: we > >> have a black background and a white rectangle with aspect ratio \alpha= . > >> at an arbitrary scale, translation, and rotation. How do we identify t= he > >> translation (or location in the x-y plane) and rotation? > > > The problem is that this example leaves out everything that renders > > such problems difficult. When the 'object', or rather knowledge of the > > object's parameters, determines precisely the image you expect to see > > and no two sets of parameters produce the same image, that is, when > > the image model takes the form: > > > P(I | a) =3D \delta(I, f(a)) , > > > where I is an image, a are the object parameters, and f is a injective > > function from object parameters to image space, then you simply invert > > f. This may not be trivial in general, but it is the simplest case. > > Yes, but you don't know f - you only have I. You do. You gave f. You said the set of images you were considering were binary images formed by placing a white rectangle in a black background. So if I know the rectangle's parameters (i.e. the position of its centroid, its orientation, its length and its width), I can predict the image exactly. The function f takes me from any parameter set to a corresponding image. Since the problem is so constrained, it is not hard to solve. For example (and this is only one of many possibilities), I can find one point on the boundary, and then follow the boundary, taking note of the positions of the corners. This gives me all the information I need. My point is that precisely because the problem is so easy, it is not a good example. If you know 1d signal processing then I do not think there need be such confusion. The only difference between 1d and 2d is geometry :). The basic ideas of 1d signal processing also apply to 2d. > > More generally, the image will not be determined given the parameters, > > and some sets of parameters might be more likely than others (e.g. > > your rectangle represents a house, so one might expect it to be > > horizontal, although it need not be). > > I appreciate your response, but where's the beef? I leave this > post in almost as much confusion as I came. If you asked a precise question, you would get a precise answer. Since you used the phrase 'arbitrary object', presumably you know what you mean by it. When you say what it means, you will get a better answer. If you did not understand what I said about the Anderson paper you mentioned, you are free to ask for clarification of whatever you did not understand. illywhacker;
Message-ID:<m3k57m5zz4.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 14:16:15 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: >> illywhacker <illywac...@gmail.com> writes: >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> >> How does one do this? To begin assume the following idealized goal: we >> >> have a black background and a white rectangle with aspect ratio \alpha. >> >> at an arbitrary scale, translation, and rotation. How do we identify the >> >> translation (or location in the x-y plane) and rotation? >> >> > The problem is that this example leaves out everything that renders >> > such problems difficult. When the 'object', or rather knowledge of the >> > object's parameters, determines precisely the image you expect to see >> > and no two sets of parameters produce the same image, that is, when >> > the image model takes the form: >> >> > P(I | a) = \delta(I, f(a)) , >> >> > where I is an image, a are the object parameters, and f is a injective >> > function from object parameters to image space, then you simply invert >> > f. This may not be trivial in general, but it is the simplest case. >> >> Yes, but you don't know f - you only have I. > > You do. You gave f. You said the set of images you were considering > were binary images formed by placing a white rectangle in a black > background. So if I know the rectangle's parameters (i.e. the position > of its centroid, its orientation, its length and its width), I can > predict the image exactly. The function f takes me from any parameter > set to a corresponding image. If I know an image is of a rectangle, but I don't know what position or orientation the rectangle is in that image, how is it that I know f(a)? Let's take a simple example. Let's say the rectangle is rotated by some unknown angle theta, so that if Ii is the input rectangle, the output image is given by [x_o y_o] = [x_i y_i][cos(theta) 0; 0 sin(theta)] All I have is the output image (a vector of [x_o y_o]'s). How do I determine theta? One of us isn't understanding the other. It could be me, but I know what I'm asking for. I may not understand your terminology and notation, however. If I understand your notation, f(a) is the function I need to find. It is the unknown I seek to know. I would think it is precisely the transformation matrix that got me from the reference rectangle (theta = 0) to the rectangle in my image. Am I wrong about the meaning of f(a)? The only way I know to identify f(a) is to correlate the received image with the translated input image over all possible values of theta. However, this is impractical as it is too computationally expensive. -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<35a2960e-882d-4125-9f92-e334dcea7ea2@q9g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 14:43:08 +0100
On Feb 19, 2:16=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 18, 6:19=A0pm, Randy Yates <ya...@ieee.org> wrote: > >> illywhacker <illywac...@gmail.com> writes: > >> > On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > >> >> How does one do this? To begin assume the following idealized goal:= we > >> >> have a black background and a white rectangle with aspect ratio \al= pha. > >> >> at an arbitrary scale, translation, and rotation. How do we identif= y the > >> >> translation (or location in the x-y plane) and rotation? > > >> > The problem is that this example leaves out everything that renders > >> > such problems difficult. When the 'object', or rather knowledge of t= he > >> > object's parameters, determines precisely the image you expect to se= e > >> > and no two sets of parameters produce the same image, that is, when > >> > the image model takes the form: > > >> > P(I | a) =3D \delta(I, f(a)) , > > >> > where I is an image, a are the object parameters, and f is a injecti= ve > >> > function from object parameters to image space, then you simply inve= rt > >> > f. This may not be trivial in general, but it is the simplest case. > > >> Yes, but you don't know f - you only have I. > > > You do. You gave f. You said the set of images you were considering > > were binary images formed by placing a white rectangle in a black > > background. So if I know the rectangle's parameters (i.e. the position > > of its centroid, its orientation, its length and its width), I can > > predict the image exactly. The function f takes me from any parameter > > set to a corresponding image. > > If I know an image is of a rectangle, but I don't know what position or > orientation the rectangle is in that image, how is it that I know f(a)? > > Let's take a simple example. Let's say the rectangle is rotated by some > unknown angle theta, so that if Ii is the input rectangle, the output > image is given by > > =A0 [x_o y_o] =3D [x_i y_i][cos(theta) 0; 0 sin(theta)] > > All I have is the output image (a vector of [x_o y_o]'s). How do I > determine theta? > > One of us isn't understanding the other. It could be me, but I know what > I'm asking for. I may not understand your terminology and notation, > however. > > If I understand your notation, f(a) is the function I need to find. It > is the unknown I seek to know. I would think it is precisely the > transformation matrix that got me from the reference rectangle (theta =3D > 0) to the rectangle in my image. > > Am I wrong about the meaning of f(a)? Yes: obviously I was not clear. What you want to know is a, in this case shorthand for (position of centroid, length, breadth, orientation) or some other system of parameters that specifies a rectangle (e.g. two opposite corners and the orientation of a line passing through one of them). The function f takes a set of parameters and produces an image that consists of a black background with the rectangle described by those parameters superimposed on it in white. My point is that the image is completely determined by the parameter set, and only one parameter set can produce each feasible image. illywhacker;
Message-ID:<m3bpsy5xvk.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:01:35 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 19, 2:16 pm, Randy Yates <ya...@ieee.org> wrote: >> illywhacker <illywac...@gmail.com> writes: >> > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: >> >> illywhacker <illywac...@gmail.com> writes: >> >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> >> >> How does one do this? To begin assume the following idealized goal: we >> >> >> have a black background and a white rectangle with aspect ratio \alpha. >> >> >> at an arbitrary scale, translation, and rotation. How do we identify the >> >> >> translation (or location in the x-y plane) and rotation? >> >> >> > The problem is that this example leaves out everything that renders >> >> > such problems difficult. When the 'object', or rather knowledge of the >> >> > object's parameters, determines precisely the image you expect to see >> >> > and no two sets of parameters produce the same image, that is, when >> >> > the image model takes the form: >> >> >> > P(I | a) = \delta(I, f(a)) , >> >> >> > where I is an image, a are the object parameters, and f is a injective >> >> > function from object parameters to image space, then you simply invert >> >> > f. This may not be trivial in general, but it is the simplest case. >> >> >> Yes, but you don't know f - you only have I. >> >> > You do. You gave f. You said the set of images you were considering >> > were binary images formed by placing a white rectangle in a black >> > background. So if I know the rectangle's parameters (i.e. the position >> > of its centroid, its orientation, its length and its width), I can >> > predict the image exactly. The function f takes me from any parameter >> > set to a corresponding image. >> >> If I know an image is of a rectangle, but I don't know what position or >> orientation the rectangle is in that image, how is it that I know f(a)? >> >> Let's take a simple example. Let's say the rectangle is rotated by some >> unknown angle theta, so that if Ii is the input rectangle, the output >> image is given by >> >> [x_o y_o] = [x_i y_i][cos(theta) 0; 0 sin(theta)] >> >> All I have is the output image (a vector of [x_o y_o]'s). How do I >> determine theta? >> >> One of us isn't understanding the other. It could be me, but I know what >> I'm asking for. I may not understand your terminology and notation, >> however. >> >> If I understand your notation, f(a) is the function I need to find. It >> is the unknown I seek to know. I would think it is precisely the >> transformation matrix that got me from the reference rectangle (theta = >> 0) to the rectangle in my image. >> >> Am I wrong about the meaning of f(a)? > > Yes: obviously I was not clear. What you want to know is a, in this > case shorthand for (position of centroid, length, breadth, > orientation) or some other system of parameters that specifies a > rectangle (e.g. two opposite corners and the orientation of a line > passing through one of them). The function f takes a set of parameters > and produces an image that consists of a black background with the > rectangle described by those parameters superimposed on it in white. > > My point is that the image is completely determined by the parameter > set, and only one parameter set can produce each feasible image. Ok, fine. This just moves the question a wee tiny bit - I now ask "How do you find a"? -- % Randy Yates % "She tells me that she likes me very much, %% Fuquay-Varina, NC % but when I try to touch, she makes it %%% 919-577-9882 % all too clear." %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<9b6e20bf-0850-4d46-be41-a46ff20523a4@g38g2000yqd.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:29:14 +0100
On Feb 19, 3:01=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 19, 2:16 pm, Randy Yates <ya...@ieee.org> wrote: > >> illywhacker <illywac...@gmail.com> writes: > >> > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: > >> >> illywhacker <illywac...@gmail.com> writes: > >> >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: > >> >> >> How does one do this? To begin assume the following idealized go= al: we > >> >> >> have a black background and a white rectangle with aspect ratio = \alpha. > >> >> >> at an arbitrary scale, translation, and rotation. How do we iden= tify the > >> >> >> translation (or location in the x-y plane) and rotation? > > >> >> > The problem is that this example leaves out everything that rende= rs > >> >> > such problems difficult. When the 'object', or rather knowledge o= f the > >> >> > object's parameters, determines precisely the image you expect to= see > >> >> > and no two sets of parameters produce the same image, that is, wh= en > >> >> > the image model takes the form: > > >> >> > P(I | a) =3D \delta(I, f(a)) , > > >> >> > where I is an image, a are the object parameters, and f is a inje= ctive > >> >> > function from object parameters to image space, then you simply i= nvert > >> >> > f. This may not be trivial in general, but it is the simplest cas= e. > > >> >> Yes, but you don't know f - you only have I. > > >> > You do. You gave f. You said the set of images you were considering > >> > were binary images formed by placing a white rectangle in a black > >> > background. So if I know the rectangle's parameters (i.e. the positi= on > >> > of its centroid, its orientation, its length and its width), I can > >> > predict the image exactly. The function f takes me from any paramete= r > >> > set to a corresponding image. > > >> If I know an image is of a rectangle, but I don't know what position o= r > >> orientation the rectangle is in that image, how is it that I know f(a)= ? > > >> Let's take a simple example. Let's say the rectangle is rotated by som= e > >> unknown angle theta, so that if Ii is the input rectangle, the output > >> image is given by > > >> [x_o y_o] =3D [x_i y_i][cos(theta) 0; 0 sin(theta)] > > >> All I have is the output image (a vector of [x_o y_o]'s). How do I > >> determine theta? > > >> One of us isn't understanding the other. It could be me, but I know wh= at > >> I'm asking for. I may not understand your terminology and notation, > >> however. > > >> If I understand your notation, f(a) is the function I need to find. It > >> is the unknown I seek to know. I would think it is precisely the > >> transformation matrix that got me from the reference rectangle (theta = =3D > >> 0) to the rectangle in my image. > > >> Am I wrong about the meaning of f(a)? > > > Yes: obviously I was not clear. What you want to know is a, in this > > case shorthand for (position of centroid, length, breadth, > > orientation) or some other system of parameters that specifies a > > rectangle (e.g. two opposite corners and the orientation of a line > > passing through one of them). The function f takes a set of parameters > > and produces an image that consists of a black background with the > > rectangle described by those parameters superimposed on it in white. > > > My point is that the image is completely determined by the parameter > > set, and only one parameter set can produce each feasible image. > > Ok, fine. This just moves the question a wee tiny bit - I now > ask "How do you find a"? For this particular problem, two solutions have already been described, although I admit one does not seem very efficient. The main point is that it is simply inverting a function. If you are asking about some broader class of problems, you had better say which. illywhacker;
Message-ID:<53617d89-a5c5-497a-91ac-4ddbb7d071f2@m29g2000prd.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:25:42 +0100
Randy: If you know that it's just a simple rectangle but you just don't know it's angle or location, can't you just take two Radon transforms and analyze them to get that info? In other words, just project your image along the two axes so that you have the sum of the image along those two axes. Then check the width of your signal in the projected 1D profile. It will range from the minimum width of the rectangle to the length of the diagonal. By checking the length, you know the angle. Doing it in the other direction will just give you a second way to check/improve on the angle. Then just take the midpoints to get the midpoints of the rectangle in the x and y direction. Now, there will be some ambiguity as to whether it's + or - since the projection of a rectangle oriented at +10 degrees would look like that at -10 degrees, but there may be a way to resolve that. Heck, if you do this for all angles, instead of just 2, well, that's what CT is, and you know CT can reconstruct the complete object - much more than just angles and position. Would this work for you? If not, then post an image somewhere so we can see the true situation and complexity of the image. But I'm just wondering why regular blob analysis like all image analysis programs have won't work. They can give you the major and minor axis lengths plus angle of the major axis. What's wrong with that? Do you need to write it yourself for some reason? Regards, ImageAnalyst
Message-ID:<60cf8aa7-0afd-438b-8cbd-2c758539d2d9@w34g2000yqm.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:43:29 +0100
On Feb 19, 3:25=A0pm, ImageAnalyst <imageanal...@mailinator.com> wrote: > Randy: > If you know that it's just a simple rectangle but you just don't know > it's angle or location, can't you just take two Radon transforms and > analyze them to get that info? =A0In other words, just project your > image along the two axes so that you have the sum of the image along > those two axes. =A0Then check the width of your signal in the projected > 1D profile. =A0It will range from the minimum width of the rectangle to > the length of the diagonal. =A0By checking the length, you know the > angle. =A0Doing it in the other direction will just give you a second > way to check/improve on the angle. =A0Then just take the midpoints to > get the midpoints of the rectangle in the x and y direction. =A0Now, > there will be some ambiguity as to whether it's + or - since the > projection of a rectangle oriented at +10 degrees would look like that > at -10 degrees, but there may be a way to resolve that. =A0Heck, if you > do this for all angles, instead of just 2, well, that's what CT is, > and you know CT can reconstruct the complete object - much more than > just angles and position. =A0Would this work for you? =A0If not, then pos= t > an image somewhere so we can see the true situation and complexity of > the image. > > But I'm just wondering why regular blob analysis like all image > analysis programs have won't work. =A0They can give you the major and > minor axis lengths plus angle of the major axis. =A0What's wrong with > that? =A0Do you need to write it yourself for some reason? Hi Image, There are enormously many ways to solve this problem, but it is not really this particular problem that is bothering the OP, I believe. illywhacker;
Message-ID:<m3zlggd2yd.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 01:54:34 +0100
ImageAnalyst <imageanalyst@mailinator.com> writes: > Randy: > If you know that it's just a simple rectangle but you just don't know > it's angle or location, can't you just take two Radon transforms and > analyze them to get that info? In other words, just project your > image along the two axes so that you have the sum of the image along > those two axes. Then check the width of your signal in the projected > 1D profile. It will range from the minimum width of the rectangle to > the length of the diagonal. By checking the length, you know the > angle. Doing it in the other direction will just give you a second > way to check/improve on the angle. Then just take the midpoints to > get the midpoints of the rectangle in the x and y direction. Now, > there will be some ambiguity as to whether it's + or - since the > projection of a rectangle oriented at +10 degrees would look like that > at -10 degrees, but there may be a way to resolve that. Heck, if you > do this for all angles, instead of just 2, well, that's what CT is, > and you know CT can reconstruct the complete object - much more than > just angles and position. Would this work for you? If not, then post > an image somewhere so we can see the true situation and complexity of > the image. > > But I'm just wondering why regular blob analysis like all image > analysis programs have won't work. They can give you the major and > minor axis lengths plus angle of the major axis. What's wrong with > that? Do you need to write it yourself for some reason? > Regards, > ImageAnalyst Hi, Thank you for these suggestions and ideas, and sorry for taking so long to respond. I delayed because I don't really understand either of the ideas you have proposed, so I can't really offer much of a response. I'm against re-inventing the wheel just as much as the next guy, so if a canned "blob analysis" algorithm will do what I need, great! If you know that locating such example code (preferable in C or Matlab) is difficult, I'd appreciate a pointer. Thanks again for your time and help. -- % Randy Yates % "...the answer lies within your soul %% Fuquay-Varina, NC % 'cause no one knows which side %%% 919-577-9882 % the coin will fall." %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO http://www.digitalsignallabs.com
Message-ID:<m3ocwwd2rt.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 01:58:30 +0100
FYI, the application here is the decoding of potentially blurred UPC codes in a photographic image, with potentially much of the image containing other information. I am thinking that I could get registration (using the terminology another poster has given me) using the bars at the edges. So rectangles are actually pretty close to the types of objects I'll be "detecting." -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<0db57fbc-e48e-4179-a789-001f8d34133c@b40g2000pri.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 23:01:13 +0100
On Feb 17, 9:45=A0pm, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? > > I am beginning to read the paper, "Coarse-Level Object Recognition Using > Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and > Fauqueur, but am unsure if this is even the right approach. > > A question I can't seem to resolve with a quick perusal of the > literature is this: Are approaches like those described by Anderson > designed to identify *arbitrary* objects in the image that are a-priori > unknown, or are they searching for an object that is known (and > described somehow)? > > Obviously I am a beginner in the field, so please make the appropriate > allowances. I do know general maths and 1-D signal processing fairly > well. > -- > % =A0Randy Yates =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0% "Midnight, on the w= ater... > %% Fuquay-Varina, NC =A0 =A0 =A0 =A0 =A0 =A0% =A0I saw... =A0the ocean's = daughter." > %%% 919-577-9882 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0% 'Can't Get It Out Of My= Head' > %%%% <ya...@ieee.org> =A0 =A0 =A0 =A0 =A0 % *El Dorado*, Electric Light O= rchestrahttp://www.digitalsignallabs.com ---------------------------------------------------------------------------= ---------------------------- Here's another method using Hausdorf distances: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html (See section 4 on that page). Good luck, ImageAnalyst
Message-ID:<0e4f07d6-e3c4-4198-bb18-3f8b3e0efcd9@q9g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 09:53:02 +0100
Why don't you use simple phase correlation? http://en.wikipedia.org/wiki/Phase_correlation If you know that rotation angle of subimage is small you can first make phase correlation to calculate translational offset of subimage, after that translate subimage, switch to log-polar coordinates and get angle and scale as offset form phase correlation in log-polar coordinates. You can repeat both stage iteratively to get better precision (translating and rotating subimage each time), using subpixel correction at the last iteration. If you rotation angle could be big rotate subimage into 16(or like) base directions, make phase correlation and calculate offsets for each direction and use best fit as first approximation for rotation angle. After that repeat method 1.
Message-ID:<m31vtraoob.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 14:45:56 +0100
serg271 <serg271@gmail.com> writes: > Why don't you use simple phase correlation? > http://en.wikipedia.org/wiki/Phase_correlation > If you know that rotation angle of subimage is small you can first > make > phase correlation to calculate translational offset of subimage, > after that translate subimage, switch to log-polar coordinates and get > angle and scale as offset form phase correlation in log-polar > coordinates. > You can repeat both stage iteratively to get better precision > (translating and rotating subimage each time), using subpixel > correction at the last iteration. > > If you rotation angle could be big rotate subimage into 16(or like) > base directions, make phase correlation and calculate offsets for each > direction and use best fit as first approximation for rotation angle. > After that repeat method 1. Hi, Thank you for the suggestions. If the image only had x-y rotated versions in it, that would seem like a feasible approach. But it's also going to be a) scaled (different sizes), b) rotated in x-z, and c) rotated in y-z. That seems to be too many parameters to subdivide practically. -- % Randy Yates % "How's life on earth? %% Fuquay-Varina, NC % ... What is it worth?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://www.digitalsignallabs.com
Message-ID:<2c72191d-c2d8-40f7-a60f-4e8ed8bad7c6@p13g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 07:19:32 +0100
On Feb 21, 3:45=A0pm, Randy Yates <ya...@ieee.org> wrote:
> serg271 <serg...@gmail.com> writes:
> > Why don't you use simple phase correlation?
> >http://en.wikipedia.org/wiki/Phase_correlation
> > If you know that =A0rotation angle of subimage is small you can first
> > make
> > =A0phase correlation to calculate translational offset of subimage,
> > after that translate subimage, switch to log-polar coordinates and get
> > angle and scale as offset form phase correlation in log-polar
> > coordinates.
> > You can repeat both stage iteratively to get better precision
> > (translating and rotating subimage each time), using subpixel
> > correction at the last iteration.
>
> > If you rotation angle could be big rotate subimage into 16(or like)
> > base directions, make phase correlation and calculate offsets for each
> > direction and use best fit as first approximation for rotation angle.
> > After that repeat method 1.
>
> Hi,
>
> Thank you for the suggestions.
>
> If the image only had x-y rotated versions in it, that would
> seem like a feasible approach. But it's also going to be
> a) scaled (different sizes), b) rotated in x-z, and c)
> rotated in y-z. That seems to be too many parameters to
> subdivide practically.
Scaling is handled by log-polar coordinates. You get the scale as the
second coordinate (logarithm of scale)
If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
x-z, y-z rotations) that is altogether different task. You should have
mentioned it from the start. You also should be more specific in what
you want. Are you just want locate a license plate or street sign from
photo/video ? There is ample amount of methods for it, just google.
If seems you want to register 3d object, or 3d position of the planar
object (it's not clear to me which one). Depending on that you want to
get it's usually called either 3d "affine registration" (without
perspective distortion) or just 3d registration (with perspective
distortion)
All of those are huge areas.
For example one method would be used if you have 3d model of the
object you want to register, different is used if model is not known
("structure from motion")
Here is wiki overview (very incomplete)
http://en.wikipedia.org/wiki/Image_registration
Here are more thorough info:
http://homepages.inf.ed.ac.uk/rbf/CVonline/
Message-ID:<4a6ae70f-2d15-4644-8a51-d51d4a5d98b9@l39g2000yqn.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 07:24:30 +0100
On Feb 22, 8:19=A0am, serg271 <serg...@gmail.com> wrote:
> On Feb 21, 3:45=A0pm, Randy Yates <ya...@ieee.org> wrote:
>
>
>
> > serg271 <serg...@gmail.com> writes:
> > > Why don't you use simple phase correlation?
> > >http://en.wikipedia.org/wiki/Phase_correlation
> > > If you know that =A0rotation angle of subimage is small you can first
> > > make
> > > =A0phase correlation to calculate translational offset of subimage,
> > > after that translate subimage, switch to log-polar coordinates and ge=
t
> > > angle and scale as offset form phase correlation in log-polar
> > > coordinates.
> > > You can repeat both stage iteratively to get better precision
> > > (translating and rotating subimage each time), using subpixel
> > > correction at the last iteration.
>
> > > If you rotation angle could be big rotate subimage into 16(or like)
> > > base directions, make phase correlation and calculate offsets for eac=
h
> > > direction and use best fit as first approximation for rotation angle.
> > > After that repeat method 1.
>
> > Hi,
>
> > Thank you for the suggestions.
>
> > If the image only had x-y rotated versions in it, that would
> > seem like a feasible approach. But it's also going to be
> > a) scaled (different sizes), b) rotated in x-z, and c)
> > rotated in y-z. That seems to be too many parameters to
> > subdivide practically.
>
> Scaling is handled by log-polar coordinates. You get the scale as the
> second coordinate (logarithm of scale)
>
> If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
> x-z, y-z rotations) that is altogether different task. You should have
> mentioned it from the start. You also should be more specific in what
> you want. Are you just want locate a license plate or street sign from
> photo/video ? There is ample amount of methods for it, just google.
> If seems =A0you want to register 3d object, or 3d position of the planar
> object (it's not clear to me which one). Depending on that you want to
> get it's usually called either 3d "affine registration" (without
> perspective distortion) or just 3d registration (with perspective
> distortion)
> All of those are huge areas.
> For example one method would be used if you have 3d model of the
> object you want to register, different is used if model is not known
> ("structure from motion")
> Here is wiki overview (very incomplete)http://en.wikipedia.org/wiki/Image=
_registration
> Here are more thorough info:http://homepages.inf.ed.ac.uk/rbf/CVonline/
Just read your your other post. It seems all you want is bar-code
registration. It's a relatively simple task, which was discussed in
this ng already -check old posts. There is also a lot of info on the
web for it, just google.
Message-ID:<m3zlgebo73.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 14:23:12 +0100
serg271 <serg271@gmail.com> writes:
> On Feb 22, 8:19 am, serg271 <serg...@gmail.com> wrote:
>> On Feb 21, 3:45 pm, Randy Yates <ya...@ieee.org> wrote:
>>
>>
>>
>> > serg271 <serg...@gmail.com> writes:
>> > > Why don't you use simple phase correlation?
>> > >http://en.wikipedia.org/wiki/Phase_correlation
>> > > If you know that rotation angle of subimage is small you can first
>> > > make
>> > > phase correlation to calculate translational offset of subimage,
>> > > after that translate subimage, switch to log-polar coordinates and get
>> > > angle and scale as offset form phase correlation in log-polar
>> > > coordinates.
>> > > You can repeat both stage iteratively to get better precision
>> > > (translating and rotating subimage each time), using subpixel
>> > > correction at the last iteration.
>>
>> > > If you rotation angle could be big rotate subimage into 16(or like)
>> > > base directions, make phase correlation and calculate offsets for each
>> > > direction and use best fit as first approximation for rotation angle.
>> > > After that repeat method 1.
>>
>> > Hi,
>>
>> > Thank you for the suggestions.
>>
>> > If the image only had x-y rotated versions in it, that would
>> > seem like a feasible approach. But it's also going to be
>> > a) scaled (different sizes), b) rotated in x-z, and c)
>> > rotated in y-z. That seems to be too many parameters to
>> > subdivide practically.
>>
>> Scaling is handled by log-polar coordinates. You get the scale as the
>> second coordinate (logarithm of scale)
>>
>> If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
>> x-z, y-z rotations) that is altogether different task. You should have
>> mentioned it from the start. You also should be more specific in what
>> you want. Are you just want locate a license plate or street sign from
>> photo/video ? There is ample amount of methods for it, just google.
>> If seems you want to register 3d object, or 3d position of the planar
>> object (it's not clear to me which one). Depending on that you want to
>> get it's usually called either 3d "affine registration" (without
>> perspective distortion) or just 3d registration (with perspective
>> distortion)
>> All of those are huge areas.
>> For example one method would be used if you have 3d model of the
>> object you want to register, different is used if model is not known
>> ("structure from motion")
>> Here is wiki overview (very incomplete)http://en.wikipedia.org/wiki/Image_registration
>> Here are more thorough info:http://homepages.inf.ed.ac.uk/rbf/CVonline/
>
> Just read your your other post. It seems all you want is bar-code
> registration. It's a relatively simple task, which was discussed in
> this ng already -check old posts. There is also a lot of info on the
> web for it, just google.
Thanks for the hints and pointers - much appreciated.
--
% Randy Yates % "...the answer lies within your soul
%% Fuquay-Varina, NC % 'cause no one knows which side
%%% 919-577-9882 % the coin will fall."
%%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO
http://www.digitalsignallabs.com
Message-ID:<m3k57icl3e.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 20:44:53 +0100
serg271 <serg271@gmail.com> writes: > [...] > There is also a lot of info on the web for it, just google. By the way, one could feasibly argue that the entire sum of human knowledge is on the web. That doesn't mean google is always a reasonable way to access that information. Searches take time; often times, LOTS of time. I don't believe It is unreasonable to ask those in the know to provide pointers. I do thank you (once again) for the specifics you provided - very helpful. -- % Randy Yates % "The dreamer, the unwoken fool - %% Fuquay-Varina, NC % in dreams, no pain will kiss the brow..." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Eldorado Overture', *Eldorado*, ELO http://www.digitalsignallabs.com
Message-ID:<C9GdnZbj8Zp6tDfUnZ2dnUVZ_gSWnZ2d@giganews.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 1 Mar 2009 07:23:35 +0100
On Tue, 17 Feb 2009 21:45:10 -0500, Randy Yates wrote:
> How does one do this? To begin assume the following idealized goal: we
> have a black background and a white rectangle with aspect ratio \alpha.
> at an arbitrary scale, translation, and rotation. How do we identify the
> translation (or location in the x-y plane) and rotation?
>
> I am beginning to read the paper, "Coarse-Level Object Recognition Using
> Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and
> Fauqueur, but am unsure if this is even the right approach.
>
> A question I can't seem to resolve with a quick perusal of the
> literature is this: Are approaches like those described by Anderson
> designed to identify *arbitrary* objects in the image that are a-priori
> unknown, or are they searching for an object that is known (and
> described somehow)?
>
> Obviously I am a beginner in the field, so please make the appropriate
> allowances. I do know general maths and 1-D signal processing fairly
> well.
Translation is meaningful only if an object has moved from A to B.
Location and translation are not the same thing.
It's not clear from your problem description what you're trying to do.
If your object really is just a rectangle, it's easy enough to find its
center and corners, and then compare those values to a second rectangle.
(look into morphological erosion or 'thinning' or 'corner detection' to
extract that kind of info.)
If you need to find a known 'object' in a scale invariant way from an
unknown image, there are several approaches. Look into "Scale Invariant
Feature Transform (SIFT)" by Lowe, or "Shape Contexts" by Belongie
(fairly neat and simple), or if your 'rectangle' is complex and
surrounded by variants, you might use a multiscale salient feature
extraction and match like that of Kadir & Brady, "Saliency, Scale, and
Image Description". The latter works well with unknown objects since it
extracts detail and builds models of objects and clusters objects that
are similar as it goes.
Randy
Message-ID:<m3ocx0h39l.fsf@local.localhost>
Subject:
Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 03:45:10 +0100
How does one do this? To begin assume the following idealized goal: we have a black background and a white rectangle with aspect ratio \alpha. at an arbitrary scale, translation, and rotation. How do we identify the translation (or location in the x-y plane) and rotation? I am beginning to read the paper, "Coarse-Level Object Recognition Using Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and Fauqueur, but am unsure if this is even the right approach. A question I can't seem to resolve with a quick perusal of the literature is this: Are approaches like those described by Anderson designed to identify *arbitrary* objects in the image that are a-priori unknown, or are they searching for an object that is known (and described somehow)? Obviously I am a beginner in the field, so please make the appropriate allowances. I do know general maths and 1-D signal processing fairly well. -- % Randy Yates % "Midnight, on the water... %% Fuquay-Varina, NC % I saw... the ocean's daughter." %%% 919-577-9882 % 'Can't Get It Out Of My Head' %%%% <yates@ieee.org> % *El Dorado*, Electric Light Orchestra http://www.digitalsignallabs.com
Message-ID:<3c673ea4-6674-45bd-988f-4a59b538d9b8@13g2000yql.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 13:22:53 +0100
On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? > > I am beginning to read the paper, "Coarse-Level Object Recognition Using > Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and > Fauqueur, but am unsure if this is even the right approach. > > A question I can't seem to resolve with a quick perusal of the > literature is this: Are approaches like those described by Anderson > designed to identify *arbitrary* objects in the image that are a-priori > unknown, or are they searching for an object that is known (and > described somehow)? > > Obviously I am a beginner in the field, so please make the appropriate > allowances. I do know general maths and 1-D signal processing fairly > well. In the paper you mention they are trying to find a given image patch in a much larger image. There is no notion of 'object' really, except that represented by an image patch. I am not sure what an 'arbitrary' object would be. There is no mystery here: what do you want to find? illywhacker;
Message-ID:<26e80fed-252b-40ba-8b94-d8a270cd08c4@m42g2000yqb.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 14:19:17 +0100
On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? The problem is that this example leaves out everything that renders such problems difficult. When the 'object', or rather knowledge of the object's parameters, determines precisely the image you expect to see and no two sets of parameters produce the same image, that is, when the image model takes the form: P(I | a) =3D \delta(I, f(a)) , where I is an image, a are the object parameters, and f is a injective function from object parameters to image space, then you simply invert f. This may not be trivial in general, but it is the simplest case. More generally, the image will not be determined given the parameters, and some sets of parameters might be more likely than others (e.g. your rectangle represents a house, so one might expect it to be horizontal, although it need not be). illywhacker;
Message-ID:<m3eixvoe7o.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 18:19:07 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> How does one do this? To begin assume the following idealized goal: we >> have a black background and a white rectangle with aspect ratio \alpha. >> at an arbitrary scale, translation, and rotation. How do we identify the >> translation (or location in the x-y plane) and rotation? > > The problem is that this example leaves out everything that renders > such problems difficult. When the 'object', or rather knowledge of the > object's parameters, determines precisely the image you expect to see > and no two sets of parameters produce the same image, that is, when > the image model takes the form: > > P(I | a) = \delta(I, f(a)) , > > where I is an image, a are the object parameters, and f is a injective > function from object parameters to image space, then you simply invert > f. This may not be trivial in general, but it is the simplest case. Yes, but you don't know f - you only have I. > More generally, the image will not be determined given the parameters, > and some sets of parameters might be more likely than others (e.g. > your rectangle represents a house, so one might expect it to be > horizontal, although it need not be). I appreciate your response, but where's the beef? I leave this post in almost as much confusion as I came. -- % Randy Yates % "Watching all the days go by... %% Fuquay-Varina, NC % Who are you and who am I?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://www.digitalsignallabs.com
Message-ID:<d0c3774c-c0db-4ed3-9cca-199908342675@h20g2000yqn.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 21:49:19 +0100
On Feb 18, 6:19=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > >> How does one do this? To begin assume the following idealized goal: we > >> have a black background and a white rectangle with aspect ratio \alpha= . > >> at an arbitrary scale, translation, and rotation. How do we identify t= he > >> translation (or location in the x-y plane) and rotation? > > > The problem is that this example leaves out everything that renders > > such problems difficult. When the 'object', or rather knowledge of the > > object's parameters, determines precisely the image you expect to see > > and no two sets of parameters produce the same image, that is, when > > the image model takes the form: > > > P(I | a) =3D \delta(I, f(a)) , > > > where I is an image, a are the object parameters, and f is a injective > > function from object parameters to image space, then you simply invert > > f. This may not be trivial in general, but it is the simplest case. > > Yes, but you don't know f - you only have I. You do. You gave f. You said the set of images you were considering were binary images formed by placing a white rectangle in a black background. So if I know the rectangle's parameters (i.e. the position of its centroid, its orientation, its length and its width), I can predict the image exactly. The function f takes me from any parameter set to a corresponding image. Since the problem is so constrained, it is not hard to solve. For example (and this is only one of many possibilities), I can find one point on the boundary, and then follow the boundary, taking note of the positions of the corners. This gives me all the information I need. My point is that precisely because the problem is so easy, it is not a good example. If you know 1d signal processing then I do not think there need be such confusion. The only difference between 1d and 2d is geometry :). The basic ideas of 1d signal processing also apply to 2d. > > More generally, the image will not be determined given the parameters, > > and some sets of parameters might be more likely than others (e.g. > > your rectangle represents a house, so one might expect it to be > > horizontal, although it need not be). > > I appreciate your response, but where's the beef? I leave this > post in almost as much confusion as I came. If you asked a precise question, you would get a precise answer. Since you used the phrase 'arbitrary object', presumably you know what you mean by it. When you say what it means, you will get a better answer. If you did not understand what I said about the Anderson paper you mentioned, you are free to ask for clarification of whatever you did not understand. illywhacker;
Message-ID:<m3k57m5zz4.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 14:16:15 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: >> illywhacker <illywac...@gmail.com> writes: >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> >> How does one do this? To begin assume the following idealized goal: we >> >> have a black background and a white rectangle with aspect ratio \alpha. >> >> at an arbitrary scale, translation, and rotation. How do we identify the >> >> translation (or location in the x-y plane) and rotation? >> >> > The problem is that this example leaves out everything that renders >> > such problems difficult. When the 'object', or rather knowledge of the >> > object's parameters, determines precisely the image you expect to see >> > and no two sets of parameters produce the same image, that is, when >> > the image model takes the form: >> >> > P(I | a) = \delta(I, f(a)) , >> >> > where I is an image, a are the object parameters, and f is a injective >> > function from object parameters to image space, then you simply invert >> > f. This may not be trivial in general, but it is the simplest case. >> >> Yes, but you don't know f - you only have I. > > You do. You gave f. You said the set of images you were considering > were binary images formed by placing a white rectangle in a black > background. So if I know the rectangle's parameters (i.e. the position > of its centroid, its orientation, its length and its width), I can > predict the image exactly. The function f takes me from any parameter > set to a corresponding image. If I know an image is of a rectangle, but I don't know what position or orientation the rectangle is in that image, how is it that I know f(a)? Let's take a simple example. Let's say the rectangle is rotated by some unknown angle theta, so that if Ii is the input rectangle, the output image is given by [x_o y_o] = [x_i y_i][cos(theta) 0; 0 sin(theta)] All I have is the output image (a vector of [x_o y_o]'s). How do I determine theta? One of us isn't understanding the other. It could be me, but I know what I'm asking for. I may not understand your terminology and notation, however. If I understand your notation, f(a) is the function I need to find. It is the unknown I seek to know. I would think it is precisely the transformation matrix that got me from the reference rectangle (theta = 0) to the rectangle in my image. Am I wrong about the meaning of f(a)? The only way I know to identify f(a) is to correlate the received image with the translated input image over all possible values of theta. However, this is impractical as it is too computationally expensive. -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<35a2960e-882d-4125-9f92-e334dcea7ea2@q9g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 14:43:08 +0100
On Feb 19, 2:16=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 18, 6:19=A0pm, Randy Yates <ya...@ieee.org> wrote: > >> illywhacker <illywac...@gmail.com> writes: > >> > On Feb 18, 3:45=A0am, Randy Yates <ya...@ieee.org> wrote: > >> >> How does one do this? To begin assume the following idealized goal:= we > >> >> have a black background and a white rectangle with aspect ratio \al= pha. > >> >> at an arbitrary scale, translation, and rotation. How do we identif= y the > >> >> translation (or location in the x-y plane) and rotation? > > >> > The problem is that this example leaves out everything that renders > >> > such problems difficult. When the 'object', or rather knowledge of t= he > >> > object's parameters, determines precisely the image you expect to se= e > >> > and no two sets of parameters produce the same image, that is, when > >> > the image model takes the form: > > >> > P(I | a) =3D \delta(I, f(a)) , > > >> > where I is an image, a are the object parameters, and f is a injecti= ve > >> > function from object parameters to image space, then you simply inve= rt > >> > f. This may not be trivial in general, but it is the simplest case. > > >> Yes, but you don't know f - you only have I. > > > You do. You gave f. You said the set of images you were considering > > were binary images formed by placing a white rectangle in a black > > background. So if I know the rectangle's parameters (i.e. the position > > of its centroid, its orientation, its length and its width), I can > > predict the image exactly. The function f takes me from any parameter > > set to a corresponding image. > > If I know an image is of a rectangle, but I don't know what position or > orientation the rectangle is in that image, how is it that I know f(a)? > > Let's take a simple example. Let's say the rectangle is rotated by some > unknown angle theta, so that if Ii is the input rectangle, the output > image is given by > > =A0 [x_o y_o] =3D [x_i y_i][cos(theta) 0; 0 sin(theta)] > > All I have is the output image (a vector of [x_o y_o]'s). How do I > determine theta? > > One of us isn't understanding the other. It could be me, but I know what > I'm asking for. I may not understand your terminology and notation, > however. > > If I understand your notation, f(a) is the function I need to find. It > is the unknown I seek to know. I would think it is precisely the > transformation matrix that got me from the reference rectangle (theta =3D > 0) to the rectangle in my image. > > Am I wrong about the meaning of f(a)? Yes: obviously I was not clear. What you want to know is a, in this case shorthand for (position of centroid, length, breadth, orientation) or some other system of parameters that specifies a rectangle (e.g. two opposite corners and the orientation of a line passing through one of them). The function f takes a set of parameters and produces an image that consists of a black background with the rectangle described by those parameters superimposed on it in white. My point is that the image is completely determined by the parameter set, and only one parameter set can produce each feasible image. illywhacker;
Message-ID:<m3bpsy5xvk.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:01:35 +0100
illywhacker <illywacker@gmail.com> writes: > On Feb 19, 2:16 pm, Randy Yates <ya...@ieee.org> wrote: >> illywhacker <illywac...@gmail.com> writes: >> > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: >> >> illywhacker <illywac...@gmail.com> writes: >> >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: >> >> >> How does one do this? To begin assume the following idealized goal: we >> >> >> have a black background and a white rectangle with aspect ratio \alpha. >> >> >> at an arbitrary scale, translation, and rotation. How do we identify the >> >> >> translation (or location in the x-y plane) and rotation? >> >> >> > The problem is that this example leaves out everything that renders >> >> > such problems difficult. When the 'object', or rather knowledge of the >> >> > object's parameters, determines precisely the image you expect to see >> >> > and no two sets of parameters produce the same image, that is, when >> >> > the image model takes the form: >> >> >> > P(I | a) = \delta(I, f(a)) , >> >> >> > where I is an image, a are the object parameters, and f is a injective >> >> > function from object parameters to image space, then you simply invert >> >> > f. This may not be trivial in general, but it is the simplest case. >> >> >> Yes, but you don't know f - you only have I. >> >> > You do. You gave f. You said the set of images you were considering >> > were binary images formed by placing a white rectangle in a black >> > background. So if I know the rectangle's parameters (i.e. the position >> > of its centroid, its orientation, its length and its width), I can >> > predict the image exactly. The function f takes me from any parameter >> > set to a corresponding image. >> >> If I know an image is of a rectangle, but I don't know what position or >> orientation the rectangle is in that image, how is it that I know f(a)? >> >> Let's take a simple example. Let's say the rectangle is rotated by some >> unknown angle theta, so that if Ii is the input rectangle, the output >> image is given by >> >> [x_o y_o] = [x_i y_i][cos(theta) 0; 0 sin(theta)] >> >> All I have is the output image (a vector of [x_o y_o]'s). How do I >> determine theta? >> >> One of us isn't understanding the other. It could be me, but I know what >> I'm asking for. I may not understand your terminology and notation, >> however. >> >> If I understand your notation, f(a) is the function I need to find. It >> is the unknown I seek to know. I would think it is precisely the >> transformation matrix that got me from the reference rectangle (theta = >> 0) to the rectangle in my image. >> >> Am I wrong about the meaning of f(a)? > > Yes: obviously I was not clear. What you want to know is a, in this > case shorthand for (position of centroid, length, breadth, > orientation) or some other system of parameters that specifies a > rectangle (e.g. two opposite corners and the orientation of a line > passing through one of them). The function f takes a set of parameters > and produces an image that consists of a black background with the > rectangle described by those parameters superimposed on it in white. > > My point is that the image is completely determined by the parameter > set, and only one parameter set can produce each feasible image. Ok, fine. This just moves the question a wee tiny bit - I now ask "How do you find a"? -- % Randy Yates % "She tells me that she likes me very much, %% Fuquay-Varina, NC % but when I try to touch, she makes it %%% 919-577-9882 % all too clear." %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<9b6e20bf-0850-4d46-be41-a46ff20523a4@g38g2000yqd.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:29:14 +0100
On Feb 19, 3:01=A0pm, Randy Yates <ya...@ieee.org> wrote: > illywhacker <illywac...@gmail.com> writes: > > On Feb 19, 2:16 pm, Randy Yates <ya...@ieee.org> wrote: > >> illywhacker <illywac...@gmail.com> writes: > >> > On Feb 18, 6:19 pm, Randy Yates <ya...@ieee.org> wrote: > >> >> illywhacker <illywac...@gmail.com> writes: > >> >> > On Feb 18, 3:45 am, Randy Yates <ya...@ieee.org> wrote: > >> >> >> How does one do this? To begin assume the following idealized go= al: we > >> >> >> have a black background and a white rectangle with aspect ratio = \alpha. > >> >> >> at an arbitrary scale, translation, and rotation. How do we iden= tify the > >> >> >> translation (or location in the x-y plane) and rotation? > > >> >> > The problem is that this example leaves out everything that rende= rs > >> >> > such problems difficult. When the 'object', or rather knowledge o= f the > >> >> > object's parameters, determines precisely the image you expect to= see > >> >> > and no two sets of parameters produce the same image, that is, wh= en > >> >> > the image model takes the form: > > >> >> > P(I | a) =3D \delta(I, f(a)) , > > >> >> > where I is an image, a are the object parameters, and f is a inje= ctive > >> >> > function from object parameters to image space, then you simply i= nvert > >> >> > f. This may not be trivial in general, but it is the simplest cas= e. > > >> >> Yes, but you don't know f - you only have I. > > >> > You do. You gave f. You said the set of images you were considering > >> > were binary images formed by placing a white rectangle in a black > >> > background. So if I know the rectangle's parameters (i.e. the positi= on > >> > of its centroid, its orientation, its length and its width), I can > >> > predict the image exactly. The function f takes me from any paramete= r > >> > set to a corresponding image. > > >> If I know an image is of a rectangle, but I don't know what position o= r > >> orientation the rectangle is in that image, how is it that I know f(a)= ? > > >> Let's take a simple example. Let's say the rectangle is rotated by som= e > >> unknown angle theta, so that if Ii is the input rectangle, the output > >> image is given by > > >> [x_o y_o] =3D [x_i y_i][cos(theta) 0; 0 sin(theta)] > > >> All I have is the output image (a vector of [x_o y_o]'s). How do I > >> determine theta? > > >> One of us isn't understanding the other. It could be me, but I know wh= at > >> I'm asking for. I may not understand your terminology and notation, > >> however. > > >> If I understand your notation, f(a) is the function I need to find. It > >> is the unknown I seek to know. I would think it is precisely the > >> transformation matrix that got me from the reference rectangle (theta = =3D > >> 0) to the rectangle in my image. > > >> Am I wrong about the meaning of f(a)? > > > Yes: obviously I was not clear. What you want to know is a, in this > > case shorthand for (position of centroid, length, breadth, > > orientation) or some other system of parameters that specifies a > > rectangle (e.g. two opposite corners and the orientation of a line > > passing through one of them). The function f takes a set of parameters > > and produces an image that consists of a black background with the > > rectangle described by those parameters superimposed on it in white. > > > My point is that the image is completely determined by the parameter > > set, and only one parameter set can produce each feasible image. > > Ok, fine. This just moves the question a wee tiny bit - I now > ask "How do you find a"? For this particular problem, two solutions have already been described, although I admit one does not seem very efficient. The main point is that it is simply inverting a function. If you are asking about some broader class of problems, you had better say which. illywhacker;
Message-ID:<53617d89-a5c5-497a-91ac-4ddbb7d071f2@m29g2000prd.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:25:42 +0100
Randy: If you know that it's just a simple rectangle but you just don't know it's angle or location, can't you just take two Radon transforms and analyze them to get that info? In other words, just project your image along the two axes so that you have the sum of the image along those two axes. Then check the width of your signal in the projected 1D profile. It will range from the minimum width of the rectangle to the length of the diagonal. By checking the length, you know the angle. Doing it in the other direction will just give you a second way to check/improve on the angle. Then just take the midpoints to get the midpoints of the rectangle in the x and y direction. Now, there will be some ambiguity as to whether it's + or - since the projection of a rectangle oriented at +10 degrees would look like that at -10 degrees, but there may be a way to resolve that. Heck, if you do this for all angles, instead of just 2, well, that's what CT is, and you know CT can reconstruct the complete object - much more than just angles and position. Would this work for you? If not, then post an image somewhere so we can see the true situation and complexity of the image. But I'm just wondering why regular blob analysis like all image analysis programs have won't work. They can give you the major and minor axis lengths plus angle of the major axis. What's wrong with that? Do you need to write it yourself for some reason? Regards, ImageAnalyst
Message-ID:<60cf8aa7-0afd-438b-8cbd-2c758539d2d9@w34g2000yqm.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Thu, 19 Feb 2009 15:43:29 +0100
On Feb 19, 3:25=A0pm, ImageAnalyst <imageanal...@mailinator.com> wrote: > Randy: > If you know that it's just a simple rectangle but you just don't know > it's angle or location, can't you just take two Radon transforms and > analyze them to get that info? =A0In other words, just project your > image along the two axes so that you have the sum of the image along > those two axes. =A0Then check the width of your signal in the projected > 1D profile. =A0It will range from the minimum width of the rectangle to > the length of the diagonal. =A0By checking the length, you know the > angle. =A0Doing it in the other direction will just give you a second > way to check/improve on the angle. =A0Then just take the midpoints to > get the midpoints of the rectangle in the x and y direction. =A0Now, > there will be some ambiguity as to whether it's + or - since the > projection of a rectangle oriented at +10 degrees would look like that > at -10 degrees, but there may be a way to resolve that. =A0Heck, if you > do this for all angles, instead of just 2, well, that's what CT is, > and you know CT can reconstruct the complete object - much more than > just angles and position. =A0Would this work for you? =A0If not, then pos= t > an image somewhere so we can see the true situation and complexity of > the image. > > But I'm just wondering why regular blob analysis like all image > analysis programs have won't work. =A0They can give you the major and > minor axis lengths plus angle of the major axis. =A0What's wrong with > that? =A0Do you need to write it yourself for some reason? Hi Image, There are enormously many ways to solve this problem, but it is not really this particular problem that is bothering the OP, I believe. illywhacker;
Message-ID:<m3zlggd2yd.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 01:54:34 +0100
ImageAnalyst <imageanalyst@mailinator.com> writes: > Randy: > If you know that it's just a simple rectangle but you just don't know > it's angle or location, can't you just take two Radon transforms and > analyze them to get that info? In other words, just project your > image along the two axes so that you have the sum of the image along > those two axes. Then check the width of your signal in the projected > 1D profile. It will range from the minimum width of the rectangle to > the length of the diagonal. By checking the length, you know the > angle. Doing it in the other direction will just give you a second > way to check/improve on the angle. Then just take the midpoints to > get the midpoints of the rectangle in the x and y direction. Now, > there will be some ambiguity as to whether it's + or - since the > projection of a rectangle oriented at +10 degrees would look like that > at -10 degrees, but there may be a way to resolve that. Heck, if you > do this for all angles, instead of just 2, well, that's what CT is, > and you know CT can reconstruct the complete object - much more than > just angles and position. Would this work for you? If not, then post > an image somewhere so we can see the true situation and complexity of > the image. > > But I'm just wondering why regular blob analysis like all image > analysis programs have won't work. They can give you the major and > minor axis lengths plus angle of the major axis. What's wrong with > that? Do you need to write it yourself for some reason? > Regards, > ImageAnalyst Hi, Thank you for these suggestions and ideas, and sorry for taking so long to respond. I delayed because I don't really understand either of the ideas you have proposed, so I can't really offer much of a response. I'm against re-inventing the wheel just as much as the next guy, so if a canned "blob analysis" algorithm will do what I need, great! If you know that locating such example code (preferable in C or Matlab) is difficult, I'd appreciate a pointer. Thanks again for your time and help. -- % Randy Yates % "...the answer lies within your soul %% Fuquay-Varina, NC % 'cause no one knows which side %%% 919-577-9882 % the coin will fall." %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO http://www.digitalsignallabs.com
Message-ID:<m3ocwwd2rt.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 01:58:30 +0100
FYI, the application here is the decoding of potentially blurred UPC codes in a photographic image, with potentially much of the image containing other information. I am thinking that I could get registration (using the terminology another poster has given me) using the bars at the edges. So rectangles are actually pretty close to the types of objects I'll be "detecting." -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
Message-ID:<0db57fbc-e48e-4179-a789-001f8d34133c@b40g2000pri.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Wed, 18 Feb 2009 23:01:13 +0100
On Feb 17, 9:45=A0pm, Randy Yates <ya...@ieee.org> wrote: > How does one do this? To begin assume the following idealized goal: we > have a black background and a white rectangle with aspect ratio \alpha. > at an arbitrary scale, translation, and rotation. How do we identify the > translation (or location in the x-y plane) and rotation? > > I am beginning to read the paper, "Coarse-Level Object Recognition Using > Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and > Fauqueur, but am unsure if this is even the right approach. > > A question I can't seem to resolve with a quick perusal of the > literature is this: Are approaches like those described by Anderson > designed to identify *arbitrary* objects in the image that are a-priori > unknown, or are they searching for an object that is known (and > described somehow)? > > Obviously I am a beginner in the field, so please make the appropriate > allowances. I do know general maths and 1-D signal processing fairly > well. > -- > % =A0Randy Yates =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0% "Midnight, on the w= ater... > %% Fuquay-Varina, NC =A0 =A0 =A0 =A0 =A0 =A0% =A0I saw... =A0the ocean's = daughter." > %%% 919-577-9882 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0% 'Can't Get It Out Of My= Head' > %%%% <ya...@ieee.org> =A0 =A0 =A0 =A0 =A0 % *El Dorado*, Electric Light O= rchestrahttp://www.digitalsignallabs.com ---------------------------------------------------------------------------= ---------------------------- Here's another method using Hausdorf distances: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html (See section 4 on that page). Good luck, ImageAnalyst
Message-ID:<0e4f07d6-e3c4-4198-bb18-3f8b3e0efcd9@q9g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 09:53:02 +0100
Why don't you use simple phase correlation? http://en.wikipedia.org/wiki/Phase_correlation If you know that rotation angle of subimage is small you can first make phase correlation to calculate translational offset of subimage, after that translate subimage, switch to log-polar coordinates and get angle and scale as offset form phase correlation in log-polar coordinates. You can repeat both stage iteratively to get better precision (translating and rotating subimage each time), using subpixel correction at the last iteration. If you rotation angle could be big rotate subimage into 16(or like) base directions, make phase correlation and calculate offsets for each direction and use best fit as first approximation for rotation angle. After that repeat method 1.
Message-ID:<m31vtraoob.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sat, 21 Feb 2009 14:45:56 +0100
serg271 <serg271@gmail.com> writes: > Why don't you use simple phase correlation? > http://en.wikipedia.org/wiki/Phase_correlation > If you know that rotation angle of subimage is small you can first > make > phase correlation to calculate translational offset of subimage, > after that translate subimage, switch to log-polar coordinates and get > angle and scale as offset form phase correlation in log-polar > coordinates. > You can repeat both stage iteratively to get better precision > (translating and rotating subimage each time), using subpixel > correction at the last iteration. > > If you rotation angle could be big rotate subimage into 16(or like) > base directions, make phase correlation and calculate offsets for each > direction and use best fit as first approximation for rotation angle. > After that repeat method 1. Hi, Thank you for the suggestions. If the image only had x-y rotated versions in it, that would seem like a feasible approach. But it's also going to be a) scaled (different sizes), b) rotated in x-z, and c) rotated in y-z. That seems to be too many parameters to subdivide practically. -- % Randy Yates % "How's life on earth? %% Fuquay-Varina, NC % ... What is it worth?" %%% 919-577-9882 % 'Mission (A World Record)', %%%% <yates@ieee.org> % *A New World Record*, ELO http://www.digitalsignallabs.com
Message-ID:<2c72191d-c2d8-40f7-a60f-4e8ed8bad7c6@p13g2000yqc.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 07:19:32 +0100
On Feb 21, 3:45=A0pm, Randy Yates <ya...@ieee.org> wrote:
> serg271 <serg...@gmail.com> writes:
> > Why don't you use simple phase correlation?
> >http://en.wikipedia.org/wiki/Phase_correlation
> > If you know that =A0rotation angle of subimage is small you can first
> > make
> > =A0phase correlation to calculate translational offset of subimage,
> > after that translate subimage, switch to log-polar coordinates and get
> > angle and scale as offset form phase correlation in log-polar
> > coordinates.
> > You can repeat both stage iteratively to get better precision
> > (translating and rotating subimage each time), using subpixel
> > correction at the last iteration.
>
> > If you rotation angle could be big rotate subimage into 16(or like)
> > base directions, make phase correlation and calculate offsets for each
> > direction and use best fit as first approximation for rotation angle.
> > After that repeat method 1.
>
> Hi,
>
> Thank you for the suggestions.
>
> If the image only had x-y rotated versions in it, that would
> seem like a feasible approach. But it's also going to be
> a) scaled (different sizes), b) rotated in x-z, and c)
> rotated in y-z. That seems to be too many parameters to
> subdivide practically.
Scaling is handled by log-polar coordinates. You get the scale as the
second coordinate (logarithm of scale)
If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
x-z, y-z rotations) that is altogether different task. You should have
mentioned it from the start. You also should be more specific in what
you want. Are you just want locate a license plate or street sign from
photo/video ? There is ample amount of methods for it, just google.
If seems you want to register 3d object, or 3d position of the planar
object (it's not clear to me which one). Depending on that you want to
get it's usually called either 3d "affine registration" (without
perspective distortion) or just 3d registration (with perspective
distortion)
All of those are huge areas.
For example one method would be used if you have 3d model of the
object you want to register, different is used if model is not known
("structure from motion")
Here is wiki overview (very incomplete)
http://en.wikipedia.org/wiki/Image_registration
Here are more thorough info:
http://homepages.inf.ed.ac.uk/rbf/CVonline/
Message-ID:<4a6ae70f-2d15-4644-8a51-d51d4a5d98b9@l39g2000yqn.googlegroups.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 07:24:30 +0100
On Feb 22, 8:19=A0am, serg271 <serg...@gmail.com> wrote:
> On Feb 21, 3:45=A0pm, Randy Yates <ya...@ieee.org> wrote:
>
>
>
> > serg271 <serg...@gmail.com> writes:
> > > Why don't you use simple phase correlation?
> > >http://en.wikipedia.org/wiki/Phase_correlation
> > > If you know that =A0rotation angle of subimage is small you can first
> > > make
> > > =A0phase correlation to calculate translational offset of subimage,
> > > after that translate subimage, switch to log-polar coordinates and ge=
t
> > > angle and scale as offset form phase correlation in log-polar
> > > coordinates.
> > > You can repeat both stage iteratively to get better precision
> > > (translating and rotating subimage each time), using subpixel
> > > correction at the last iteration.
>
> > > If you rotation angle could be big rotate subimage into 16(or like)
> > > base directions, make phase correlation and calculate offsets for eac=
h
> > > direction and use best fit as first approximation for rotation angle.
> > > After that repeat method 1.
>
> > Hi,
>
> > Thank you for the suggestions.
>
> > If the image only had x-y rotated versions in it, that would
> > seem like a feasible approach. But it's also going to be
> > a) scaled (different sizes), b) rotated in x-z, and c)
> > rotated in y-z. That seems to be too many parameters to
> > subdivide practically.
>
> Scaling is handled by log-polar coordinates. You get the scale as the
> second coordinate (logarithm of scale)
>
> If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
> x-z, y-z rotations) that is altogether different task. You should have
> mentioned it from the start. You also should be more specific in what
> you want. Are you just want locate a license plate or street sign from
> photo/video ? There is ample amount of methods for it, just google.
> If seems =A0you want to register 3d object, or 3d position of the planar
> object (it's not clear to me which one). Depending on that you want to
> get it's usually called either 3d "affine registration" (without
> perspective distortion) or just 3d registration (with perspective
> distortion)
> All of those are huge areas.
> For example one method would be used if you have 3d model of the
> object you want to register, different is used if model is not known
> ("structure from motion")
> Here is wiki overview (very incomplete)http://en.wikipedia.org/wiki/Image=
_registration
> Here are more thorough info:http://homepages.inf.ed.ac.uk/rbf/CVonline/
Just read your your other post. It seems all you want is bar-code
registration. It's a relatively simple task, which was discussed in
this ng already -check old posts. There is also a lot of info on the
web for it, just google.
Message-ID:<m3zlgebo73.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 14:23:12 +0100
serg271 <serg271@gmail.com> writes:
> On Feb 22, 8:19 am, serg271 <serg...@gmail.com> wrote:
>> On Feb 21, 3:45 pm, Randy Yates <ya...@ieee.org> wrote:
>>
>>
>>
>> > serg271 <serg...@gmail.com> writes:
>> > > Why don't you use simple phase correlation?
>> > >http://en.wikipedia.org/wiki/Phase_correlation
>> > > If you know that rotation angle of subimage is small you can first
>> > > make
>> > > phase correlation to calculate translational offset of subimage,
>> > > after that translate subimage, switch to log-polar coordinates and get
>> > > angle and scale as offset form phase correlation in log-polar
>> > > coordinates.
>> > > You can repeat both stage iteratively to get better precision
>> > > (translating and rotating subimage each time), using subpixel
>> > > correction at the last iteration.
>>
>> > > If you rotation angle could be big rotate subimage into 16(or like)
>> > > base directions, make phase correlation and calculate offsets for each
>> > > direction and use best fit as first approximation for rotation angle.
>> > > After that repeat method 1.
>>
>> > Hi,
>>
>> > Thank you for the suggestions.
>>
>> > If the image only had x-y rotated versions in it, that would
>> > seem like a feasible approach. But it's also going to be
>> > a) scaled (different sizes), b) rotated in x-z, and c)
>> > rotated in y-z. That seems to be too many parameters to
>> > subdivide practically.
>>
>> Scaling is handled by log-polar coordinates. You get the scale as the
>> second coordinate (logarithm of scale)
>>
>> If you have 3d rotation, not 2d rotation, as implied by your post(x-y,
>> x-z, y-z rotations) that is altogether different task. You should have
>> mentioned it from the start. You also should be more specific in what
>> you want. Are you just want locate a license plate or street sign from
>> photo/video ? There is ample amount of methods for it, just google.
>> If seems you want to register 3d object, or 3d position of the planar
>> object (it's not clear to me which one). Depending on that you want to
>> get it's usually called either 3d "affine registration" (without
>> perspective distortion) or just 3d registration (with perspective
>> distortion)
>> All of those are huge areas.
>> For example one method would be used if you have 3d model of the
>> object you want to register, different is used if model is not known
>> ("structure from motion")
>> Here is wiki overview (very incomplete)http://en.wikipedia.org/wiki/Image_registration
>> Here are more thorough info:http://homepages.inf.ed.ac.uk/rbf/CVonline/
>
> Just read your your other post. It seems all you want is bar-code
> registration. It's a relatively simple task, which was discussed in
> this ng already -check old posts. There is also a lot of info on the
> web for it, just google.
Thanks for the hints and pointers - much appreciated.
--
% Randy Yates % "...the answer lies within your soul
%% Fuquay-Varina, NC % 'cause no one knows which side
%%% 919-577-9882 % the coin will fall."
%%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO
http://www.digitalsignallabs.com
Message-ID:<m3k57icl3e.fsf@local.localhost>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 22 Feb 2009 20:44:53 +0100
serg271 <serg271@gmail.com> writes: > [...] > There is also a lot of info on the web for it, just google. By the way, one could feasibly argue that the entire sum of human knowledge is on the web. That doesn't mean google is always a reasonable way to access that information. Searches take time; often times, LOTS of time. I don't believe It is unreasonable to ask those in the know to provide pointers. I do thank you (once again) for the specifics you provided - very helpful. -- % Randy Yates % "The dreamer, the unwoken fool - %% Fuquay-Varina, NC % in dreams, no pain will kiss the brow..." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Eldorado Overture', *Eldorado*, ELO http://www.digitalsignallabs.com
Message-ID:<C9GdnZbj8Zp6tDfUnZ2dnUVZ_gSWnZ2d@giganews.com>
Subject:
Re: Locating An Image At Arbitrary Scales, Translations, and Rotations
Date:Sun, 1 Mar 2009 07:23:35 +0100
On Tue, 17 Feb 2009 21:45:10 -0500, Randy Yates wrote:
> How does one do this? To begin assume the following idealized goal: we
> have a black background and a white rectangle with aspect ratio \alpha.
> at an arbitrary scale, translation, and rotation. How do we identify the
> translation (or location in the x-y plane) and rotation?
>
> I am beginning to read the paper, "Coarse-Level Object Recognition Using
> Interlevel Products of Complex Wavelets" by Anderson, Kingsbury, and
> Fauqueur, but am unsure if this is even the right approach.
>
> A question I can't seem to resolve with a quick perusal of the
> literature is this: Are approaches like those described by Anderson
> designed to identify *arbitrary* objects in the image that are a-priori
> unknown, or are they searching for an object that is known (and
> described somehow)?
>
> Obviously I am a beginner in the field, so please make the appropriate
> allowances. I do know general maths and 1-D signal processing fairly
> well.
Translation is meaningful only if an object has moved from A to B.
Location and translation are not the same thing.
It's not clear from your problem description what you're trying to do.
If your object really is just a rectangle, it's easy enough to find its
center and corners, and then compare those values to a second rectangle.
(look into morphological erosion or 'thinning' or 'corner detection' to
extract that kind of info.)
If you need to find a known 'object' in a scale invariant way from an
unknown image, there are several approaches. Look into "Scale Invariant
Feature Transform (SIFT)" by Lowe, or "Shape Contexts" by Belongie
(fairly neat and simple), or if your 'rectangle' is complex and
surrounded by variants, you might use a multiscale salient feature
extraction and match like that of Kadir & Brady, "Saliency, Scale, and
Image Description". The latter works well with unknown objects since it
extracts detail and builds models of objects and clusters objects that
are similar as it goes.
Randy