b31233449a796a6343a91b3a7ec295b399f54948
[ffmpeg.git] / libavfilter / vf_edgedetect.c
1 /*
2  * Copyright (c) 2012 Clément Bœsch
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20
21 /**
22  * @file
23  * Edge detection filter
24  *
25  * @see https://en.wikipedia.org/wiki/Canny_edge_detector
26  */
27
28 #include "libavutil/opt.h"
29 #include "avfilter.h"
30 #include "formats.h"
31 #include "internal.h"
32 #include "video.h"
33
34 typedef struct {
35     const AVClass *class;
36     uint8_t  *tmpbuf;
37     uint16_t *gradients;
38     char     *directions;
39     double   low, high;
40     uint8_t  low_u8, high_u8;
41 } EdgeDetectContext;
42
43 #define OFFSET(x) offsetof(EdgeDetectContext, x)
44 #define FLAGS AV_OPT_FLAG_FILTERING_PARAM|AV_OPT_FLAG_VIDEO_PARAM
45 static const AVOption edgedetect_options[] = {
46     { "high", "set high threshold", OFFSET(high), AV_OPT_TYPE_DOUBLE, {.dbl=50/255.}, 0, 1, FLAGS },
47     { "low",  "set low threshold",  OFFSET(low),  AV_OPT_TYPE_DOUBLE, {.dbl=20/255.}, 0, 1, FLAGS },
48     { NULL }
49 };
50
51 AVFILTER_DEFINE_CLASS(edgedetect);
52
53 static av_cold int init(AVFilterContext *ctx)
54 {
55     EdgeDetectContext *edgedetect = ctx->priv;
56
57     edgedetect->low_u8  = edgedetect->low  * 255. + .5;
58     edgedetect->high_u8 = edgedetect->high * 255. + .5;
59     return 0;
60 }
61
62 static int query_formats(AVFilterContext *ctx)
63 {
64     static const enum AVPixelFormat pix_fmts[] = {AV_PIX_FMT_GRAY8, AV_PIX_FMT_NONE};
65     ff_set_common_formats(ctx, ff_make_format_list(pix_fmts));
66     return 0;
67 }
68
69 static int config_props(AVFilterLink *inlink)
70 {
71     AVFilterContext *ctx = inlink->dst;
72     EdgeDetectContext *edgedetect = ctx->priv;
73
74     edgedetect->tmpbuf     = av_malloc(inlink->w * inlink->h);
75     edgedetect->gradients  = av_calloc(inlink->w * inlink->h, sizeof(*edgedetect->gradients));
76     edgedetect->directions = av_malloc(inlink->w * inlink->h);
77     if (!edgedetect->tmpbuf || !edgedetect->gradients || !edgedetect->directions)
78         return AVERROR(ENOMEM);
79     return 0;
80 }
81
82 static void gaussian_blur(AVFilterContext *ctx, int w, int h,
83                                 uint8_t *dst, int dst_linesize,
84                           const uint8_t *src, int src_linesize)
85 {
86     int i, j;
87
88     memcpy(dst, src, w); dst += dst_linesize; src += src_linesize;
89     memcpy(dst, src, w); dst += dst_linesize; src += src_linesize;
90     for (j = 2; j < h - 2; j++) {
91         dst[0] = src[0];
92         dst[1] = src[1];
93         for (i = 2; i < w - 2; i++) {
94             /* Gaussian mask of size 5x5 with sigma = 1.4 */
95             dst[i] = ((src[-2*src_linesize + i-2] + src[2*src_linesize + i-2]) * 2
96                     + (src[-2*src_linesize + i-1] + src[2*src_linesize + i-1]) * 4
97                     + (src[-2*src_linesize + i  ] + src[2*src_linesize + i  ]) * 5
98                     + (src[-2*src_linesize + i+1] + src[2*src_linesize + i+1]) * 4
99                     + (src[-2*src_linesize + i+2] + src[2*src_linesize + i+2]) * 2
100
101                     + (src[  -src_linesize + i-2] + src[  src_linesize + i-2]) *  4
102                     + (src[  -src_linesize + i-1] + src[  src_linesize + i-1]) *  9
103                     + (src[  -src_linesize + i  ] + src[  src_linesize + i  ]) * 12
104                     + (src[  -src_linesize + i+1] + src[  src_linesize + i+1]) *  9
105                     + (src[  -src_linesize + i+2] + src[  src_linesize + i+2]) *  4
106
107                     + src[i-2] *  5
108                     + src[i-1] * 12
109                     + src[i  ] * 15
110                     + src[i+1] * 12
111                     + src[i+2] *  5) / 159;
112         }
113         dst[i    ] = src[i    ];
114         dst[i + 1] = src[i + 1];
115
116         dst += dst_linesize;
117         src += src_linesize;
118     }
119     memcpy(dst, src, w); dst += dst_linesize; src += src_linesize;
120     memcpy(dst, src, w);
121 }
122
123 enum {
124     DIRECTION_45UP,
125     DIRECTION_45DOWN,
126     DIRECTION_HORIZONTAL,
127     DIRECTION_VERTICAL,
128 };
129
130 static int get_rounded_direction(int gx, int gy)
131 {
132     /* reference angles:
133      *   tan( pi/8) = sqrt(2)-1
134      *   tan(3pi/8) = sqrt(2)+1
135      * Gy/Gx is the tangent of the angle (theta), so Gy/Gx is compared against
136      * <ref-angle>, or more simply Gy against <ref-angle>*Gx
137      *
138      * Gx and Gy bounds = [-1020;1020], using 16-bit arithmetic:
139      *   round((sqrt(2)-1) * (1<<16)) =  27146
140      *   round((sqrt(2)+1) * (1<<16)) = 158218
141      */
142     if (gx) {
143         int tanpi8gx, tan3pi8gx;
144
145         if (gx < 0)
146             gx = -gx, gy = -gy;
147         gy <<= 16;
148         tanpi8gx  =  27146 * gx;
149         tan3pi8gx = 158218 * gx;
150         if (gy > -tan3pi8gx && gy < -tanpi8gx)  return DIRECTION_45UP;
151         if (gy > -tanpi8gx  && gy <  tanpi8gx)  return DIRECTION_HORIZONTAL;
152         if (gy >  tanpi8gx  && gy <  tan3pi8gx) return DIRECTION_45DOWN;
153     }
154     return DIRECTION_VERTICAL;
155 }
156
157 static void sobel(int w, int h,
158                        uint16_t *dst, int dst_linesize,
159                          int8_t *dir, int dir_linesize,
160                   const uint8_t *src, int src_linesize)
161 {
162     int i, j;
163
164     for (j = 1; j < h - 1; j++) {
165         dst += dst_linesize;
166         dir += dir_linesize;
167         src += src_linesize;
168         for (i = 1; i < w - 1; i++) {
169             const int gx =
170                 -1*src[-src_linesize + i-1] + 1*src[-src_linesize + i+1]
171                 -2*src[                i-1] + 2*src[                i+1]
172                 -1*src[ src_linesize + i-1] + 1*src[ src_linesize + i+1];
173             const int gy =
174                 -1*src[-src_linesize + i-1] + 1*src[ src_linesize + i-1]
175                 -2*src[-src_linesize + i  ] + 2*src[ src_linesize + i  ]
176                 -1*src[-src_linesize + i+1] + 1*src[ src_linesize + i+1];
177
178             dst[i] = FFABS(gx) + FFABS(gy);
179             dir[i] = get_rounded_direction(gx, gy);
180         }
181     }
182 }
183
184 static void non_maximum_suppression(int w, int h,
185                                           uint8_t  *dst, int dst_linesize,
186                                     const  int8_t  *dir, int dir_linesize,
187                                     const uint16_t *src, int src_linesize)
188 {
189     int i, j;
190
191 #define COPY_MAXIMA(ay, ax, by, bx) do {                \
192     if (src[i] > src[(ay)*src_linesize + i+(ax)] &&     \
193         src[i] > src[(by)*src_linesize + i+(bx)])       \
194         dst[i] = av_clip_uint8(src[i]);                 \
195 } while (0)
196
197     for (j = 1; j < h - 1; j++) {
198         dst += dst_linesize;
199         dir += dir_linesize;
200         src += src_linesize;
201         for (i = 1; i < w - 1; i++) {
202             switch (dir[i]) {
203             case DIRECTION_45UP:        COPY_MAXIMA( 1, -1, -1,  1); break;
204             case DIRECTION_45DOWN:      COPY_MAXIMA(-1, -1,  1,  1); break;
205             case DIRECTION_HORIZONTAL:  COPY_MAXIMA( 0, -1,  0,  1); break;
206             case DIRECTION_VERTICAL:    COPY_MAXIMA(-1,  0,  1,  0); break;
207             }
208         }
209     }
210 }
211
212 static void double_threshold(int low, int high, int w, int h,
213                                    uint8_t *dst, int dst_linesize,
214                              const uint8_t *src, int src_linesize)
215 {
216     int i, j;
217
218     for (j = 0; j < h; j++) {
219         for (i = 0; i < w; i++) {
220             if (src[i] > high) {
221                 dst[i] = src[i];
222                 continue;
223             }
224
225             if ((!i || i == w - 1 || !j || j == h - 1) &&
226                 src[i] > low &&
227                 (src[-src_linesize + i-1] > high ||
228                  src[-src_linesize + i  ] > high ||
229                  src[-src_linesize + i+1] > high ||
230                  src[                i-1] > high ||
231                  src[                i+1] > high ||
232                  src[ src_linesize + i-1] > high ||
233                  src[ src_linesize + i  ] > high ||
234                  src[ src_linesize + i+1] > high))
235                 dst[i] = src[i];
236             else
237                 dst[i] = 0;
238         }
239         dst += dst_linesize;
240         src += src_linesize;
241     }
242 }
243
244 static int filter_frame(AVFilterLink *inlink, AVFrame *in)
245 {
246     AVFilterContext *ctx = inlink->dst;
247     EdgeDetectContext *edgedetect = ctx->priv;
248     AVFilterLink *outlink = inlink->dst->outputs[0];
249     uint8_t  *tmpbuf    = edgedetect->tmpbuf;
250     uint16_t *gradients = edgedetect->gradients;
251     int8_t   *directions= edgedetect->directions;
252     int direct = 0;
253     AVFrame *out;
254
255     if (av_frame_is_writable(in)) {
256         direct = 1;
257         out = in;
258     } else {
259         out = ff_get_video_buffer(outlink, outlink->w, outlink->h);
260         if (!out) {
261             av_frame_free(&in);
262             return AVERROR(ENOMEM);
263         }
264         av_frame_copy_props(out, in);
265     }
266
267     /* gaussian filter to reduce noise  */
268     gaussian_blur(ctx, inlink->w, inlink->h,
269                   tmpbuf,      inlink->w,
270                   in->data[0], in->linesize[0]);
271
272     /* compute the 16-bits gradients and directions for the next step */
273     sobel(inlink->w, inlink->h,
274           gradients, inlink->w,
275           directions,inlink->w,
276           tmpbuf,    inlink->w);
277
278     /* non_maximum_suppression() will actually keep & clip what's necessary and
279      * ignore the rest, so we need a clean output buffer */
280     memset(tmpbuf, 0, inlink->w * inlink->h);
281     non_maximum_suppression(inlink->w, inlink->h,
282                             tmpbuf,    inlink->w,
283                             directions,inlink->w,
284                             gradients, inlink->w);
285
286     /* keep high values, or low values surrounded by high values */
287     double_threshold(edgedetect->low_u8, edgedetect->high_u8,
288                      inlink->w, inlink->h,
289                      out->data[0], out->linesize[0],
290                      tmpbuf,       inlink->w);
291
292     if (!direct)
293         av_frame_free(&in);
294     return ff_filter_frame(outlink, out);
295 }
296
297 static av_cold void uninit(AVFilterContext *ctx)
298 {
299     EdgeDetectContext *edgedetect = ctx->priv;
300     av_freep(&edgedetect->tmpbuf);
301     av_freep(&edgedetect->gradients);
302     av_freep(&edgedetect->directions);
303 }
304
305 static const AVFilterPad edgedetect_inputs[] = {
306     {
307         .name         = "default",
308         .type         = AVMEDIA_TYPE_VIDEO,
309         .config_props = config_props,
310         .filter_frame = filter_frame,
311      },
312      { NULL }
313 };
314
315 static const AVFilterPad edgedetect_outputs[] = {
316      {
317          .name = "default",
318          .type = AVMEDIA_TYPE_VIDEO,
319      },
320      { NULL }
321 };
322
323 AVFilter ff_vf_edgedetect = {
324     .name          = "edgedetect",
325     .description   = NULL_IF_CONFIG_SMALL("Detect and draw edge."),
326     .priv_size     = sizeof(EdgeDetectContext),
327     .init          = init,
328     .uninit        = uninit,
329     .query_formats = query_formats,
330     .inputs        = edgedetect_inputs,
331     .outputs       = edgedetect_outputs,
332     .priv_class    = &edgedetect_class,
333     .flags         = AVFILTER_FLAG_SUPPORT_TIMELINE_GENERIC,
334 };