2D Dynamic Time Warping Algorithm
arges
I need a fast and good 2D Dynamic Time Warping Algorithm.
Anybody can refer me to find any materials or papers.
Thanks,
Arges.
illywhacker
Do you mean you want to warp one image to match another? This problem
is much harder than the 1D problem as the group of possible warpings
is much larger, more complicated, and harder to charaterize. This is
because in 2D you have geometry. The topic is 'image registration',
and there is a vast amount of work on it. If you search for:
"image registration" diffeomorphism
for example, you will find a lot of papers. It ishard to say more
without knowing more about your problem.
illywhacker;
ImageAnalyst
I never heard of warping time, except perhaps on Star Trek.
arges
wrote:
Did you search on the google with "Dynamic Time Warping Algorithm"?.
My search result is 89.700.
ImageAnalyst
> On 27 Aðustos, 16:14, ImageAnalyst <imageanal...@mailinator.com>
Arges:
I did now. Cool. I learn something new every day and I like that.
Thanks for bringing it up. Sorry though that I can't help you.
Perhaps one of the 92,500 Google hits will be a winner. I can
understand your question though, because it would take quite a while
to wade through 92,500 Google hits!
Regards,
ImageAnalyst
illywhacker
> On 27 Aðustos, 16:14, ImageAnalyst <imageanal...@mailinator.com>
In 1D you can optimize over all piecewise linear warpings in time
polynomial in the number of pieces, using dynamic programming. You
cannot do this in 2D as there is no ordering. The key point is what
space of warpings you wish to search over.
illywhacker;
aruzinsky
Until today, I never heard of "Dynamic Time Warping Algorithm,"
either, but
http://en.wikipedia.org/wiki/Dynamic_time_warping
says, "The extension of the problem for two-dimensional "series" like
images (planar warping) is NP-complete, while the problem for one-
dimensional signals like time series can be solved in polynomial
time."
Until today, I never heard of "NP-complete," but
http://en.wikipedia.org/wiki/NP-complete
says, "The most notable characteristic of NP-complete problems is that
no fast solution to them is known"
Duh?
illywhacker
In this instance, this means that no polynomial time algorithm is
known that will find the global solution to a certain type of
optimization problem. It does not prevent the existence of fast,
approximate solutions to this type of problem, nor of polynomial time
solutions to more restricted optimization problems that might
adequately serve the needs of the OP. Indeed, image registration uses
both types of techniques all the time.
illywhacker;
aruzinsky
I found this:
http://www.cse.buffalo.edu/~hlei/Research/papers/DirectImageMatching(61).pdf
which says, "Our algorithm also guarantees continuity and monotonicity
and the complexity is only O(N6)."
I use a proprietary algorithm that visually compensates for small
warpings of any kind, e.g., tree branches swaying in a light wind, but
I do not think it is Dynamic Time Warping.
arges
wrote:
> On Aug 27, 1:26 am, arges <mustafa.sa...@gmail.com> wrote:
>
> > Hi all,
> > I need a fast and good 2D Dynamic Time Warping Algorithm.
> > Anybody can refer me to find any materials or papers.
> > Thanks,
> > Arges.
>
> I found this:
>
>
> which says, "Our algorithm also guarantees continuity and monotonicity
> and the complexity is only O(N6)."
>
> I use a proprietary algorithm that visually compensates for small
> warpings of any kind, e.g., tree branches swaying in a light wind, but
> I do not think it is Dynamic Time Warping.
Hi aruzinsky,
There is an implementation 2DTW in this link.
But, cost is too high to perform fast analysis.
Total Computational Complexity is O(N6).
It is not practically usable.
aruzinsky
> On 27 Aðustos, 19:50, aruzinsky <aruzin...@general-cathexis.com>
>
> - Show quoted text -
There are other practical problems with the method in that paper. The
cost function is based on pairs of pixels rather than pairs of local
pixel groups therefore there is no kind of statistical averaging to
reduce the influence of noise. Also, to align images of different
exposure, you need something like sample correlation which, again,
cannot be based on a single pair of pixels. Also, I see no subpixel
accuracy in that method.
I suspect that I can't align that author's images, but I might be
wrong. If you post a link to two typical images that you are trying
to align, I will see whether I can align them.
arges
Images are here: http://rapidshare.com/files/140623289/images.zip.html
I am not trying to align images, I am trying to find similarity
between images.
I am trying to find their distances(2DDW distances) . Distances are
shows their similarities each other.
aruzinsky
>
> - Show quoted text -
That paper was published in 2004 and the authors said that their
algorithm is the fastest so, unless someone published something faster
in 4 years, you are probably out of luck.
In principle, I don't see much difference between this and measuring a
norm of differences between aligned images. If the alignment is
subpixel, it might even give a lower 2DDW distance than without
subpixel alignment.
http://www.general-cathexis.com/images/3AlignedTo4.jpg
This took about 4 secs. The non-overlapping regions are filled in
with reflections because this is mostly for artistic use.
arges
You did a good job.
I understood everything about my problem.
Well done.
Kind Regards.
illywhacker
> Images are here: http://rapidshare.com/files/140623289/images.zip.html
> I am not trying to align images, I am trying to find similarity
> between images.
> I am trying to find their distances(2DDW distances) . Distances are
> shows their similarities each other.
To do that you have to place a 'distance' on the space of 2D warpings.
This is not given a priori.
illywhacker;
illywhacker
> You did a good job.
> I understood everything about my problem.
> Well done.
Well done yourself. You are the only person in the world who
understands everything about this problem.
illywhacker;
Eamonn
classic DTW algorithm. Here is a picture for this…
http://www.cs.ucr.edu/~eamonn/shape/Gorilla2Gorilla.bmp
Since your images have a vein like structure, there are distance
measures for this kind of data, see
Michael Barnathan, Jingjing Zhang, Despina Kontos, Predrag R. Bakic,
Andrew D. A. Maidment, Vasileios Megalooikonomou: Analyzing Tree-Like
Structures in Biomedical Images Based on Texture and Branching: An
Application to Breast Imaging. Digital Mammography / IWDM 2008: 25-32
eamonn
illywhacker
This is true for shapes, i.e. essentially binary images. But these
boundary matching methods do not provide correspondences between the
interior points of the skulls, which may or may not be important.
Since there is so much work on this problem, it seems foolish to offer
solutions without knowing the details of the OP's application.
A search on 'image registration' is a good way to start off the
research necessary to find an appropriate solution.
illywhacker;
arges
I didn't understand the implementation from the paper and picture that
you given.
How can I convert 2D shapes to 1D.
Regards.
illywhacker
> On 1 Eylül, 11:21, illywhacker <illywac...@gmail.com> wrote:
> > On Aug 31, 3:32 am, Eamonn <eamonn.ke...@gmail.com> wrote:
>
> > > Many 2d shapes can simply be converted to 1D, then you can use the
> > > classic DTW algorithm. Here is a picture for this…http://www.cs.ucr.edu/~eamonn/shape/Gorilla2Gorilla.bmp
>
> > > Since your images have a vein like structure, there are distance
> > > measures for this kind of data, see
>
> > > Michael Barnathan, Jingjing Zhang, Despina Kontos, Predrag R. Bakic,
> > > Andrew D. A. Maidment, Vasileios Megalooikonomou: Analyzing Tree-Like
> > > Structures in Biomedical Images Based on Texture and Branching: An
> > > Application to Breast Imaging. Digital Mammography / IWDM 2008: 25-32
>
> > This is true for shapes, i.e. essentially binary images. But these
> > boundary matching methods do not provide correspondences between the
> > interior points of the skulls, which may or may not be important.
> > Since there is so much work on this problem, it seems foolish to offer
> > solutions without knowing the details of the OP's application.
>
> > A search on 'image registration' is a good way to start off the
> > research necessary to find an appropriate solution.
>
> you given.
> How can I convert 2D shapes to 1D.
I did not give it: Eamonn did. Eamonn was talking about matching
curves,
which may represent the boundaries of objects. If the distance between
images that you wish to set up should only depend on the boundaries of
objects in the images, then this might (I stress, *might*) be an
approach
to consider.
You have never said what you really want to do, and this makes
concrete
advice difficult to give. No one wants to compare images just for the
sake
of it.
illywhacker;