| 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() | expand |
| Context | Check | Description |
|---|---|---|
| andriy/default | pending | |
| andriy/make | success | Make finished |
| andriy/make_fate | success | Make fate finished |
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,
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
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?
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".
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.
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
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
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 --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
=== 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(-)