[SciPy-Dev] New feature - discrete Frechet distance for scipy.spatial.distance

[Tyler Reddy]

Oh yeah, I forgot about that proposal!

Here's what the first author of the subquadratic Frechet paper had to say
when I asked him about implementations (hopefully they don't mind me
sharing!):

"I am not aware of such a code, and I am not sure whether it's worth the
effort for a variety of reasons. n^2 algorithm is so simple that it will
perform significantly better even for polygonal chains with tens of
thousands of vertices.

In practice, dynamic time warping does a better job in measuring
similarity  and outside CG community  (eg. computer vision, compuational
biology, speech recognition) DTW is often used instead of Frechet.

I have a paper in the ACM-GIS conference this year on approximation
algorithms for DTW, with an implementation.
The approx algorithm performs better than the quadratic DP algorithm when
the number of vertices is a few thousand or more.

-Pankaj"

On 23 January 2018 at 13:01, CJ Carey <perimosocordiae at gmail.com> wrote:

> Frechet distance is pretty similar to Dynamic Time Warping, which has also
> been requested for inclusion in scipy: https://github.com/
> scipy/scipy/issues/7638
>
> AFAIK, there's no current effort to add DTW, but I suspect it would make
> sense to have both it and Frechet variants in a similar namespace.
>
> On Tue, Jan 23, 2018 at 11:41 AM, Spiros Denaxas <s.denaxas at gmail.com>
> wrote:
>
>> Thanks - will do.
>> Spiros
>>
>> On Tue, Jan 23, 2018 at 3:27 PM, Tyler Reddy <tyler.je.reddy at gmail.com>
>> wrote:
>>
>>> I guess both call signatures have tradeoffs. What I did with
>>> directed_hausdorff looks more like "a," so you can probably start with that
>>> for now. I'd encourage you to start drafting a (work in progress) pull
>>> request -- you can progressively chip away at docstring, unit tests,
>>> cythonization (if this is helpful or you haven't already), maybe a concise
>>> asv performance benchmark to accompany it, etc.
>>>
>>> On 23 January 2018 at 02:38, Spiros Denaxas <s.denaxas at gmail.com> wrote:
>>>
>>>> Hi Tyler
>>>>
>>>> Thank you for the feedback. I agree that a subquadratic implementation
>>>> would be really cool but I havent seen one either and just by glancing at
>>>> the paper realize that this would take a substantial amount of effort.
>>>>
>>>> What is the canonical way of specying the flavour ? the two options I
>>>> can think of are: a) scipy.spatial.distance.continuous_frechet or b)
>>>> scipy.spatial.distance.frechet(P,Q, type="continuous")
>>>>
>>>> best
>>>> Spiros
>>>>
>>>>
>>>> On Mon, Jan 22, 2018 at 3:14 PM, Tyler Reddy <tyler.je.reddy at gmail.com>
>>>> wrote:
>>>>
>>>>> There are a few Python implementations of discrete Frechet around
>>>>> (i.e., in MDA: https://www.mdanalysis.org/doc
>>>>> s/documentation_pages/analysis/psa.html#MDAnalysis.analysis.
>>>>> psa.discrete_frechet ). Most of them use the quadratic time
>>>>> complexity dynamic programming approach, and it seems you have used that as
>>>>> well. I think there's probably interest in incorporating discrete Frechet
>>>>> in scipy since we already have directed_hausdorff, which is thematically
>>>>> similar.
>>>>>
>>>>> One thing that would be really impressive is if we could get a
>>>>> subquadratic implementation of discrete Frechet ( i.e.,
>>>>> http://epubs.siam.org/doi/abs/10.1137/130920526 ), but these
>>>>> algorithms seem to be extraordinarily complicated -- indeed the authors of
>>>>> the paper I cited there are not aware of any working implementations in the
>>>>> wild & when I asked one I think they suggested it wasn't worth implementing
>>>>> because for most input data sizes the much simpler algorithm will still
>>>>> win. Perhaps this sort of thing could be summarized in the docstring.
>>>>>
>>>>> There are quite a few different flavors of Frechet distance
>>>>> (continuous, homotopic, weak, etc.). From a design standpoint it might
>>>>> makes sense to have some kind of keyword to allow expansion for those in
>>>>> the future.
>>>>>
>>>>> On 22 January 2018 at 05:33, Spiros Denaxas <s.denaxas at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> Dear SciPy devs,
>>>>>>
>>>>>> I recently decided to clean up and package a Python implementation
>>>>>> [1] for calculating the discrete Frechet distance [2] between two polygonal
>>>>>> curves that I had lying around.
>>>>>>
>>>>>> I was thinking this could potentially be a useful addition to
>>>>>> scipy.spatial.distance. More than happy to do a pull request if you think
>>>>>> it will be useful.
>>>>>>
>>>>>> Spiros
>>>>>>
>>>>>> [1] https://github.com/spiros/discrete_frechet
>>>>>> [2] http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> SciPy-Dev mailing list
>>>>>> SciPy-Dev at python.org
>>>>>> https://mail.python.org/mailman/listinfo/scipy-dev
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20180123/3003405b/attachment.html>