diff mbox series

[FFmpeg-devel,v2] avfilter/vf_edgedetect: properly implement double_threshold()

Message ID CAGTf1Mn9THhN4CVR+sVRshTi4AhXrsLwGmfxZ_0ro5i09t2Fsg@mail.gmail.com
State Accepted
Commit 855d51bf481dddf425f9a82e4d1aa2cdc93c22f8
Headers show
Series [FFmpeg-devel,v2] avfilter/vf_edgedetect: properly implement double_threshold()
Related show

Checks

Context Check Description
andriy/default pending
andriy/make success Make finished
andriy/make_fate success Make fate finished

Commit Message

Valery Kot June 22, 2020, 3:29 p.m. UTC
=== Version 1 ===
vf_edgedetect video filter implements Canny algorithm
(https://en.wikipedia.org/wiki/Canny_edge_detector)

Important part of this algo is the double threshold step: pixels above
"high" threshold being kept, pixels below "low" threshold dropped,
pixels in between kept if they are attached to "high" pixels.

This is implemented in the double_threshold() function. However,
condition to start checking attached pixels, as it is now and as it
was in FFmpeg since 2012, only allows checking on the boundary, not
inside the video. It is a very lucky coincidence that those boundary
pixels are always 0, otherwise following lines would be reading
outside of the buffer.

As it is now, double_threshold() only implements "high" thresholding.
As a result, edges are either noisy or fragmented, depending on "high"
threshold selection; "low" threshold is simply ignored.

Attached one char patch fixes this.

=== Version 2 ===
- include avfilter/ in commit message
- update FATE tests
From 69bbe24bfe23efa3874448f28451b1abaa209d5d Mon Sep 17 00:00:00 2001
From: vkot <valery.kot@kinetiq.tv>
Date: Fri, 19 Jun 2020 16:57:13 +0200
Subject: [PATCH] avfilter/vf_edgedetect: properly implement double_threshold()

---
 libavfilter/vf_edgedetect.c               | 2 +-
 tests/ref/fate/filter-edgedetect          | 2 +-
 tests/ref/fate/filter-edgedetect-colormix | 2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)

Comments

Andriy Gelman June 27, 2020, 9:35 p.m. UTC | #1
On Mon, 22. Jun 17:29, Valery Kot wrote:
> === Version 1 ===
> vf_edgedetect video filter implements Canny algorithm
> (https://en.wikipedia.org/wiki/Canny_edge_detector)
> 
> Important part of this algo is the double threshold step: pixels above
> "high" threshold being kept, pixels below "low" threshold dropped,
> pixels in between kept if they are attached to "high" pixels.
> 
> This is implemented in the double_threshold() function. However,
> condition to start checking attached pixels, as it is now and as it
> was in FFmpeg since 2012, only allows checking on the boundary, not
> inside the video. It is a very lucky coincidence that those boundary
> pixels are always 0, otherwise following lines would be reading
> outside of the buffer.
> 
> As it is now, double_threshold() only implements "high" thresholding.
> As a result, edges are either noisy or fragmented, depending on "high"
> threshold selection; "low" threshold is simply ignored.
> 
> Attached one char patch fixes this.
> 
> === Version 2 ===
> - include avfilter/ in commit message
> - update FATE tests

> From 69bbe24bfe23efa3874448f28451b1abaa209d5d Mon Sep 17 00:00:00 2001
> From: vkot <valery.kot@kinetiq.tv>
> Date: Fri, 19 Jun 2020 16:57:13 +0200
> Subject: [PATCH] avfilter/vf_edgedetect: properly implement double_threshold()
> 
> ---
>  libavfilter/vf_edgedetect.c               | 2 +-
>  tests/ref/fate/filter-edgedetect          | 2 +-
>  tests/ref/fate/filter-edgedetect-colormix | 2 +-
>  3 files changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/libavfilter/vf_edgedetect.c b/libavfilter/vf_edgedetect.c
> index a5614ea63b..df8afbd532 100644
> --- a/libavfilter/vf_edgedetect.c
> +++ b/libavfilter/vf_edgedetect.c
> @@ -294,7 +294,7 @@ static void double_threshold(int low, int high, int w, int h,
>                  continue;
>              }
>  
> -            if ((!i || i == w - 1 || !j || j == h - 1) &&
> +            if (!(!i || i == w - 1 || !j || j == h - 1) &&

lgtm. I saw a small improvement when testing.

Would be nice to allow weak edges that become strong to trigger neighboring weak
edges in the future.

Thanks,
Valery Kot June 29, 2020, 7:26 a.m. UTC | #2
On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
>
> lgtm. I saw a small improvement when testing.
>
> Would be nice to allow weak edges that become strong to trigger neighboring weak
> edges in the future.

Thanks for the comment.

You are right, ideally double_threshold should be recursive (seed from
each "high" peak and spread over "low" peaks). But then potentially we
may end up with width*height/2 recursion depth, which may lead to
stack overflow. So probably some recursion limit is needed, and hence
suboptimal solution.

Or iterative approach, running through the complete image again and
again checking if "low" peaks are touching already selected edge
pixels. Stop when no new pixels can be added to the edge. Better, but
still potentially width*height/2 iterations with width*height
operations each, completely killing performance.

Maybe later I'll try to implement it in a generic way, but this is out
of scope for this patch.

Regards,

Valery Kot
Andriy Gelman July 4, 2020, 5:03 p.m. UTC | #3
On Mon, 29. Jun 09:26, Valery Kot wrote:
> On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> >
> > lgtm. I saw a small improvement when testing.
> >
> > Would be nice to allow weak edges that become strong to trigger neighboring weak
> > edges in the future.
> 
> Thanks for the comment.
> 
> You are right, ideally double_threshold should be recursive (seed from
> each "high" peak and spread over "low" peaks). But then potentially we
> may end up with width*height/2 recursion depth, which may lead to
> stack overflow. So probably some recursion limit is needed, and hence
> suboptimal solution.
> 
> Or iterative approach, running through the complete image again and
> again checking if "low" peaks are touching already selected edge
> pixels. Stop when no new pixels can be added to the edge. Better, but
> still potentially width*height/2 iterations with width*height
> operations each, completely killing performance.
> 
> Maybe later I'll try to implement it in a generic way, but this is out
> of scope for this patch.
> 
> Regards,
> 
> Valery Kot

Any objections if I apply this patch?
Limin Wang July 5, 2020, 1:37 a.m. UTC | #4
On Sat, Jul 04, 2020 at 01:03:48PM -0400, Andriy Gelman wrote:
> On Mon, 29. Jun 09:26, Valery Kot wrote:
> > On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> > >
> > > lgtm. I saw a small improvement when testing.
> > >
> > > Would be nice to allow weak edges that become strong to trigger neighboring weak
> > > edges in the future.
> > 
> > Thanks for the comment.
> > 
> > You are right, ideally double_threshold should be recursive (seed from
> > each "high" peak and spread over "low" peaks). But then potentially we
> > may end up with width*height/2 recursion depth, which may lead to
> > stack overflow. So probably some recursion limit is needed, and hence
> > suboptimal solution.
> > 
> > Or iterative approach, running through the complete image again and
> > again checking if "low" peaks are touching already selected edge
> > pixels. Stop when no new pixels can be added to the edge. Better, but
> > still potentially width*height/2 iterations with width*height
> > operations each, completely killing performance.
> > 
> > Maybe later I'll try to implement it in a generic way, but this is out
> > of scope for this patch.
> > 
> > Regards,
> > 
> > Valery Kot
> 
> Any objections if I apply this patch? 

The patch look fine to me, but no sign-off?

> 
> -- 
> Andriy
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> https://ffmpeg.org/mailman/listinfo/ffmpeg-devel
> 
> To unsubscribe, visit link above, or email
> ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".
Andriy Gelman July 5, 2020, 3:19 a.m. UTC | #5
On Sun, 05. Jul 09:37, lance.lmwang@gmail.com wrote:
> On Sat, Jul 04, 2020 at 01:03:48PM -0400, Andriy Gelman wrote:
> > On Mon, 29. Jun 09:26, Valery Kot wrote:
> > > On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> > > >
> > > > lgtm. I saw a small improvement when testing.
> > > >
> > > > Would be nice to allow weak edges that become strong to trigger neighboring weak
> > > > edges in the future.
> > > 
> > > Thanks for the comment.
> > > 
> > > You are right, ideally double_threshold should be recursive (seed from
> > > each "high" peak and spread over "low" peaks). But then potentially we
> > > may end up with width*height/2 recursion depth, which may lead to
> > > stack overflow. So probably some recursion limit is needed, and hence
> > > suboptimal solution.
> > > 
> > > Or iterative approach, running through the complete image again and
> > > again checking if "low" peaks are touching already selected edge
> > > pixels. Stop when no new pixels can be added to the edge. Better, but
> > > still potentially width*height/2 iterations with width*height
> > > operations each, completely killing performance.
> > > 
> > > Maybe later I'll try to implement it in a generic way, but this is out
> > > of scope for this patch.
> > > 
> > > Regards,
> > > 
> > > Valery Kot
> > 
> > Any objections if I apply this patch? 

> 
> The patch look fine to me, but no sign-off?
> 

Thanks, will add one.
Alexander Strasser July 6, 2020, 6:49 p.m. UTC | #6
On 2020-07-04 23:19 -0400, Andriy Gelman wrote:
> On Sun, 05. Jul 09:37, lance.lmwang@gmail.com wrote:
> > On Sat, Jul 04, 2020 at 01:03:48PM -0400, Andriy Gelman wrote:
> > > On Mon, 29. Jun 09:26, Valery Kot wrote:
> > > > On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> > > > >
> > > > > lgtm. I saw a small improvement when testing.
> > > > >
> > > > > Would be nice to allow weak edges that become strong to trigger neighboring weak
> > > > > edges in the future.
> > > >
> > > > Thanks for the comment.
> > > >
> > > > You are right, ideally double_threshold should be recursive (seed from
> > > > each "high" peak and spread over "low" peaks). But then potentially we
> > > > may end up with width*height/2 recursion depth, which may lead to
> > > > stack overflow. So probably some recursion limit is needed, and hence
> > > > suboptimal solution.
> > > >
> > > > Or iterative approach, running through the complete image again and
> > > > again checking if "low" peaks are touching already selected edge
> > > > pixels. Stop when no new pixels can be added to the edge. Better, but
> > > > still potentially width*height/2 iterations with width*height
> > > > operations each, completely killing performance.
> > > >
> > > > Maybe later I'll try to implement it in a generic way, but this is out
> > > > of scope for this patch.
> > > >
> > > > Regards,
> > > >
> > > > Valery Kot
> > >
> > > Any objections if I apply this patch?
>
> >
> > The patch look fine to me, but no sign-off?
> >
>
> Thanks, will add one.

I guess it's OK to push. In my few tests for some cases it looked
a bit better.

I didn't understand why this doesn't make things worse for the
outermost frame of pixels, but Valery commented it wouldn't make
any difference because of the surrounding code.

I just looked at that function and because it checks all the eight
surrounding pixels, I thought we might now miss cases that wouldn't
have been missed before. Should of course be usually be better for
most pictures.

Anyway I couldn't get around to build a mental model for this call,
so I might well be missing context.


  Alexander
Andriy Gelman July 6, 2020, 8:02 p.m. UTC | #7
Hi Alex,
Thanks for testing.

On Mon, 6 Jul 2020 at 14:49, Alexander Strasser <eclipse7@gmx.net> wrote:

> On 2020-07-04 23:19 -0400, Andriy Gelman wrote:
> > On Sun, 05. Jul 09:37, lance.lmwang@gmail.com wrote:
> > > On Sat, Jul 04, 2020 at 01:03:48PM -0400, Andriy Gelman wrote:
> > > > On Mon, 29. Jun 09:26, Valery Kot wrote:
> > > > > On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <
> andriy.gelman@gmail.com> wrote:
> > > > > >
> > > > > > lgtm. I saw a small improvement when testing.
> > > > > >
> > > > > > Would be nice to allow weak edges that become strong to trigger
> neighboring weak
> > > > > > edges in the future.
> > > > >
> > > > > Thanks for the comment.
> > > > >
> > > > > You are right, ideally double_threshold should be recursive (seed
> from
> > > > > each "high" peak and spread over "low" peaks). But then
> potentially we
> > > > > may end up with width*height/2 recursion depth, which may lead to
> > > > > stack overflow. So probably some recursion limit is needed, and
> hence
> > > > > suboptimal solution.
> > > > >
> > > > > Or iterative approach, running through the complete image again and
> > > > > again checking if "low" peaks are touching already selected edge
> > > > > pixels. Stop when no new pixels can be added to the edge. Better,
> but
> > > > > still potentially width*height/2 iterations with width*height
> > > > > operations each, completely killing performance.
> > > > >
> > > > > Maybe later I'll try to implement it in a generic way, but this is
> out
> > > > > of scope for this patch.
> > > > >
> > > > > Regards,
> > > > >
> > > > > Valery Kot
> > > >
> > > > Any objections if I apply this patch?
> >
> > >
> > > The patch look fine to me, but no sign-off?
> > >
> >
> > Thanks, will add one.
>
> I guess it's OK to push. In my few tests for some cases it looked
> a bit better.
>
> I didn't understand why this doesn't make things worse for the
> outermost frame of pixels, but Valery commented it wouldn't make
> any difference because of the surrounding code.
>
> I just looked at that function and because it checks all the eight
> surrounding pixels, I thought we might now miss cases that wouldn't
> have been missed before. Should of course be usually be better for
> most pictures.


The point of the first check is to skip pixels on the boundary so that the
surrounding pixels check does not seg fault.
It was only by luck that src[i] is always zero on the boundary so that the
surrounding pixels check is not evaluated.

You could treat pixels on the boundary separately, but I don't think it's
worth it.

Andriy
Andriy Gelman July 7, 2020, 4:20 a.m. UTC | #8
On Mon, 06. Jul 16:02, Andriy Gelman wrote:
> Hi Alex,
> Thanks for testing.
> 
> On Mon, 6 Jul 2020 at 14:49, Alexander Strasser <eclipse7@gmx.net> wrote:
> 
> > On 2020-07-04 23:19 -0400, Andriy Gelman wrote:
> > > On Sun, 05. Jul 09:37, lance.lmwang@gmail.com wrote:
> > > > On Sat, Jul 04, 2020 at 01:03:48PM -0400, Andriy Gelman wrote:
> > > > > On Mon, 29. Jun 09:26, Valery Kot wrote:
> > > > > > On Sun, Jun 28, 2020 at 12:03 AM Andriy Gelman <
> > andriy.gelman@gmail.com> wrote:
> > > > > > >
> > > > > > > lgtm. I saw a small improvement when testing.
> > > > > > >
> > > > > > > Would be nice to allow weak edges that become strong to trigger
> > neighboring weak
> > > > > > > edges in the future.
> > > > > >
> > > > > > Thanks for the comment.
> > > > > >
> > > > > > You are right, ideally double_threshold should be recursive (seed
> > from
> > > > > > each "high" peak and spread over "low" peaks). But then
> > potentially we
> > > > > > may end up with width*height/2 recursion depth, which may lead to
> > > > > > stack overflow. So probably some recursion limit is needed, and
> > hence
> > > > > > suboptimal solution.
> > > > > >
> > > > > > Or iterative approach, running through the complete image again and
> > > > > > again checking if "low" peaks are touching already selected edge
> > > > > > pixels. Stop when no new pixels can be added to the edge. Better,
> > but
> > > > > > still potentially width*height/2 iterations with width*height
> > > > > > operations each, completely killing performance.
> > > > > >
> > > > > > Maybe later I'll try to implement it in a generic way, but this is
> > out
> > > > > > of scope for this patch.
> > > > > >
> > > > > > Regards,
> > > > > >
> > > > > > Valery Kot
> > > > >
> > > > > Any objections if I apply this patch?
> > >
> > > >
> > > > The patch look fine to me, but no sign-off?
> > > >
> > >
> > > Thanks, will add one.
> >
> > I guess it's OK to push. In my few tests for some cases it looked
> > a bit better.
> >
> > I didn't understand why this doesn't make things worse for the
> > outermost frame of pixels, but Valery commented it wouldn't make
> > any difference because of the surrounding code.
> >
> > I just looked at that function and because it checks all the eight
> > surrounding pixels, I thought we might now miss cases that wouldn't
> > have been missed before. Should of course be usually be better for
> > most pictures.
> 
> 
> The point of the first check is to skip pixels on the boundary so that the
> surrounding pixels check does not seg fault.
> It was only by luck that src[i] is always zero on the boundary so that the
> surrounding pixels check is not evaluated.
> 
> You could treat pixels on the boundary separately, but I don't think it's
> worth it.

Thanks, applied.
diff mbox series

Patch

diff --git a/libavfilter/vf_edgedetect.c b/libavfilter/vf_edgedetect.c
index a5614ea63b..df8afbd532 100644
--- a/libavfilter/vf_edgedetect.c
+++ b/libavfilter/vf_edgedetect.c
@@ -294,7 +294,7 @@  static void double_threshold(int low, int high, int w, int h,
                 continue;
             }
 
-            if ((!i || i == w - 1 || !j || j == h - 1) &&
+            if (!(!i || i == w - 1 || !j || j == h - 1) &&
                 src[i] > low &&
                 (src[-src_linesize + i-1] > high ||
                  src[-src_linesize + i  ] > high ||
diff --git a/tests/ref/fate/filter-edgedetect b/tests/ref/fate/filter-edgedetect
index 23c9953e61..e49639afac 100644
--- a/tests/ref/fate/filter-edgedetect
+++ b/tests/ref/fate/filter-edgedetect
@@ -1 +1 @@ 
-edgedetect          93ceace33f6636bcdbeb037317c65745
+edgedetect          04ff46bb35edff3dbad4102391516d25
diff --git a/tests/ref/fate/filter-edgedetect-colormix b/tests/ref/fate/filter-edgedetect-colormix
index e828c6bd19..0df17344bc 100644
--- a/tests/ref/fate/filter-edgedetect-colormix
+++ b/tests/ref/fate/filter-edgedetect-colormix
@@ -1 +1 @@ 
-edgedetect-colormix 1b8658252e2f03fbae30e6d63dd24c7c
+edgedetect-colormix 9f50c5586f899a8f5a10059154d64bde