diff mbox series

[FFmpeg-devel] vf_edgedetect: properly implement double_threshold()

Message ID CAGTf1MnCX2JOO-VMTUCDKjCP76y5JsLnhubzat4MF48c2hfd6g@mail.gmail.com
State Superseded
Headers show
Series [FFmpeg-devel] vf_edgedetect: properly implement double_threshold()
Related show

Checks

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

Commit Message

Valery Kot June 19, 2020, 3:15 p.m. UTC
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.

Please review.

Valery
From b78f5960736de52d1c8e41bd598a465092c1de60 Mon Sep 17 00:00:00 2001
From: vkot <valery.kot@kinetiq.tv>
Date: Fri, 19 Jun 2020 16:57:13 +0200
Subject: [PATCH] vf_edgedetect: properly implement double_threshold()

---
 libavfilter/vf_edgedetect.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Comments

Alexander Strasser June 19, 2020, 8:43 p.m. UTC | #1
Hi Valery!

On 2020-06-19 17:15 +0200, Valery Kot wrote:
> 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.
>
> Please review.

Looks indeed like the condition is wrong.

I say looks because I did only look and didn't do actual testing.

I hope you will answer my question anyway: Does your patch completely
fix the problem or is it sacrificing the treatment of the outer most
pixels?


  Alexander

> From b78f5960736de52d1c8e41bd598a465092c1de60 Mon Sep 17 00:00:00 2001
> From: vkot <valery.kot@kinetiq.tv>
> Date: Fri, 19 Jun 2020 16:57:13 +0200
> Subject: [PATCH] vf_edgedetect: properly implement double_threshold()
>
> ---
>  libavfilter/vf_edgedetect.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> 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 ||
> --
Valery Kot June 19, 2020, 11:24 p.m. UTC | #2
>
> > 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.
> >
> > Please review.
>
> Looks indeed like the condition is wrong.
>
> I say looks because I did only look and didn't do actual testing.
>
> I hope you will answer my question anyway: Does your patch completely
> fix the problem or is it sacrificing the treatment of the outer most
> pixels?
>

>
Hi Alexander,
Outer pixels are already set to 0 (line 333, memset(tmpbuf, 0, inlink->w
<https://ffmpeg.org/doxygen/2.7/structAVFilterLink.html#a08e3e25929bb29d5f6ef768343ff7f57>
* inlink->h
<https://ffmpeg.org/doxygen/2.7/structAVFilterLink.html#a1efd10db9d097b6d27054da46e06e133>
);)
This  is correct, as it is not possible to properly calculate gradient
there.
Patch fixes handling of inner pixels and changes nothing for outer pixels.
Andriy Gelman June 22, 2020, 5:35 a.m. UTC | #3
Hi Valery, 

Thanks for the patch. 

Please also update the fate test:
https://patchwork.ffmpeg.org/project/ffmpeg/patch/CAGTf1MnCX2JOO-VMTUCDKjCP76y5JsLnhubzat4MF48c2hfd6g@mail.gmail.com/

On Fri, 19. Jun 17:15, Valery Kot wrote:
> 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.
> 
> Please review.
> 
> Valery

> From b78f5960736de52d1c8e41bd598a465092c1de60 Mon Sep 17 00:00:00 2001
> From: vkot <valery.kot@kinetiq.tv>
> Date: Fri, 19 Jun 2020 16:57:13 +0200

> Subject: [PATCH] vf_edgedetect: properly implement double_threshold()

Add an avfilter/ prefix to the commit title.

> 
> ---
>  libavfilter/vf_edgedetect.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> 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 ||
> -- 
> 2.26.2.windows.1
> 

> _______________________________________________
> 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".

Thanks,
Valery Kot June 22, 2020, 7:58 a.m. UTC | #4
On Mon, Jun 22, 2020 at 7:58 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
>
> Hi Valery,
>
> Thanks for the patch.
>
> Please also update the fate test:
> https://patchwork.ffmpeg.org/project/ffmpeg/patch/CAGTf1MnCX2JOO-VMTUCDKjCP76y5JsLnhubzat4MF48c2hfd6g@mail.gmail.com/

Thanks for feedback. Updating FATE tests is a bridge too far for me. I
can't even build FFmpeg itself at the moment, say nothing about
setting up the test environment and finding out how it works. Could
you please do this update for me?

> Add an avfilter/ prefix to the commit title.

I will, if FATE issue can be solved

> Thanks,
> --
> Andriy
>
Moritz Barsnick June 22, 2020, 10:53 a.m. UTC | #5
On Fri, Jun 19, 2020 at 17:15:06 +0200, Valery Kot wrote:
> -            if ((!i || i == w - 1 || !j || j == h - 1) &&
> +            if (!(!i || i == w - 1 || !j || j == h - 1) &&

NOT of a logical OR can be inverted, so this *may* be more readable as:
               if ((i && i != w - 1 && j && j != h - 1) &&
or even drop the bracket
               if (i && i != w - 1 && j && j != h - 1 &&

Untested, just from observation.

Moritz
Moritz Barsnick June 22, 2020, 10:57 a.m. UTC | #6
On Mon, Jun 22, 2020 at 09:58:42 +0200, Valery Kot wrote:
> Thanks for feedback. Updating FATE tests is a bridge too far for me. I
> can't even build FFmpeg itself at the moment, say nothing about
> setting up the test environment and finding out how it works. Could
> you please do this update for me?

Are you saying you analyzed this issue in the source code, but have
not had a chance to check whether the change really fixes the output?
[*]

Once you *do* understand how to build ffmpeg, you can follow the fate
instructions here:
https://ffmpeg.org/fate.html#Using-FATE-from-your-FFmpeg-source-directory

You don't actually need to add a new fate test in this case, but submit
the changed reference output with your patch (assuming that the changed
output is really correct!).

Cheers,
Moritz

[*] I'm not saying that someone couldn't do that for you instead, if
    they are willing.
Valery Kot June 22, 2020, 12:24 p.m. UTC | #7
On Mon, Jun 22, 2020 at 12:54 PM Moritz Barsnick <barsnick@gmx.net> wrote:
>
> On Fri, Jun 19, 2020 at 17:15:06 +0200, Valery Kot wrote:
> > -            if ((!i || i == w - 1 || !j || j == h - 1) &&
> > +            if (!(!i || i == w - 1 || !j || j == h - 1) &&
>
> NOT of a logical OR can be inverted, so this *may* be more readable as:
>                if ((i && i != w - 1 && j && j != h - 1) &&
> or even drop the bracket
>                if (i && i != w - 1 && j && j != h - 1 &&
>

Indeed, those three are equivalent. Complex logical conditions can be
written in different ways. I chose mine to minimize change, assuming
that there was just a typo in original algo implementation.
Valery Kot June 22, 2020, 12:37 p.m. UTC | #8
On Mon, Jun 22, 2020 at 12:57 PM Moritz Barsnick <barsnick@gmx.net> wrote:
>
> On Mon, Jun 22, 2020 at 09:58:42 +0200, Valery Kot wrote:
> > Thanks for feedback. Updating FATE tests is a bridge too far for me. I
> > can't even build FFmpeg itself at the moment, say nothing about
> > setting up the test environment and finding out how it works. Could
> > you please do this update for me?
>
> Are you saying you analyzed this issue in the source code, but have
> not had a chance to check whether the change really fixes the output?
> [*]

I tested master build from Zeranoe to confirm that there is a bug
(modifying low threshold changes nothing in output). Then I modified
double_threshold() function and tested it locally in a unit test (in
my own testbed).

>
> Once you *do* understand how to build ffmpeg, you can follow the fate
> instructions here:
> https://ffmpeg.org/fate.html#Using-FATE-from-your-FFmpeg-source-directory
>
> You don't actually need to add a new fate test in this case, but submit
> the changed reference output with your patch (assuming that the changed
> output is really correct!).

I am working on Windows, and don't have build environment for FFmpeg
at this moment. As this is not a pressing issue for me, I don't want
to spend time on it. I was just developing my own Canny filter
implementation and noticed that FFmpeg edge detector is
underperforming (quality wise). I could've do nothing, or just sent a
bug report, but chose to send this patch as a contribution to the
community.

>
> Cheers,
> Moritz
>
> [*] I'm not saying that someone couldn't do that for you instead, if
>     they are willing.
Andriy Gelman June 22, 2020, 2:55 p.m. UTC | #9
On Mon, 22. Jun 09:58, Valery Kot wrote:
> On Mon, Jun 22, 2020 at 7:58 AM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> >
> > Hi Valery,
> >
> > Thanks for the patch.
> >
> > Please also update the fate test:
> > https://patchwork.ffmpeg.org/project/ffmpeg/patch/CAGTf1MnCX2JOO-VMTUCDKjCP76y5JsLnhubzat4MF48c2hfd6g@mail.gmail.com/
> 
> Thanks for feedback. Updating FATE tests is a bridge too far for me. I
> can't even build FFmpeg itself at the moment, say nothing about
> setting up the test environment and finding out how it works. Could
> you please do this update for me?

It should be enough to change the hashes in two files.
Please resend with these changes.

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


Thanks,
Valery Kot June 22, 2020, 3:32 p.m. UTC | #10
On Mon, Jun 22, 2020 at 4:56 PM Andriy Gelman <andriy.gelman@gmail.com> wrote:
> It should be enough to change the hashes in two files.
> Please resend with these changes.
>
> 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

Just submitted patch V2, please drop this one.

Thanks for the help Andriy, appreciated!

Valery
Moritz Barsnick June 23, 2020, 8:49 a.m. UTC | #11
On Mon, Jun 22, 2020 at 14:24:19 +0200, Valery Kot wrote:
> On Mon, Jun 22, 2020 at 12:54 PM Moritz Barsnick <barsnick@gmx.net> wrote:
> > NOT of a logical OR can be inverted, so this *may* be more readable as:
> >                if ((i && i != w - 1 && j && j != h - 1) &&
> Indeed, those three are equivalent. Complex logical conditions can be
> written in different ways. I chose mine to minimize change, assuming
> that there was just a typo in original algo implementation.

No problem, I agree a one-byte change maybe more acceptable.

Moritz
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 ||