1 /* nearest.c
2 *
3 * 31/10/17
4 * - from labelregion
5 */
6
7 /*
8
9 This file is part of VIPS.
10
11 VIPS is free software; you can redistribute it and/or modify
12 it under the terms of the GNU Lesser General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU Lesser General Public License for more details.
20
21 You should have received a copy of the GNU Lesser General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301 USA
25
26 */
27
28 /*
29
30 These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk
31
32 */
33
34 /*
35 #define DEBUG
36 */
37
38 #ifdef HAVE_CONFIG_H
39 #include <config.h>
40 #endif /*HAVE_CONFIG_H*/
41 #include <vips/intl.h>
42
43 #include <stdio.h>
44
45 #include <vips/vips.h>
46 #include <vips/internal.h>
47
48 #include "pmorphology.h"
49
50 /* A seed pixel. We fill outwards from each of these.
51 */
52 typedef struct _Seed {
53 int x;
54 int y;
55 int r;
56
57 /* Bits saying which octant can still grow. When they are all zero, the
58 * seed is dead.
59 */
60 int octant_mask;
61 } Seed;
62
63 typedef struct _VipsFillNearest {
64 VipsMorphology parent_instance;
65
66 VipsImage *out;
67 VipsImage *distance;
68
69 /* Size of our image.
70 */
71 int width;
72 int height;
73
74 /* All our seed pixels. There can be a lot of these.
75 */
76 GArray *seeds;
77 } VipsFillNearest;
78
79 typedef VipsMorphologyClass VipsFillNearestClass;
80
81 G_DEFINE_TYPE( VipsFillNearest, vips_fill_nearest, VIPS_TYPE_MORPHOLOGY );
82
83 static void
vips_fill_nearest_finalize(GObject * gobject)84 vips_fill_nearest_finalize( GObject *gobject )
85 {
86 VipsFillNearest *nearest = (VipsFillNearest *) gobject;
87
88 #ifdef DEBUG
89 printf( "vips_fill_nearest_finalize: " );
90 vips_object_print_name( VIPS_OBJECT( gobject ) );
91 printf( "\n" );
92 #endif /*DEBUG*/
93
94 VIPS_FREEF( g_array_unref, nearest->seeds );
95
96 G_OBJECT_CLASS( vips_fill_nearest_parent_class )->finalize( gobject );
97 }
98
99 struct _Circle;
100 typedef void (*VipsFillNearestPixel)( struct _Circle *circle,
101 int x, int y, int octant );
102
103 typedef struct _Circle {
104 VipsFillNearest *nearest;
105 Seed *seed;
106 int octant_mask;
107 VipsFillNearestPixel nearest_pixel;
108 } Circle;
109
110 static void
vips_fill_nearest_pixel(Circle * circle,int x,int y,int octant)111 vips_fill_nearest_pixel( Circle *circle, int x, int y, int octant )
112 {
113 float *p;
114 float radius;
115 int dx, dy;
116
117 if( (circle->seed->octant_mask & (1 << octant)) == 0 )
118 return;
119
120 /* We need to do this as float, or we'll have dithering along edges.
121 */
122 p = (float *) VIPS_IMAGE_ADDR( circle->nearest->distance, x, y );
123 dx = x - circle->seed->x;
124 dy = y - circle->seed->y;
125 radius = sqrt( dx * dx + dy * dy );
126
127 if( p[0] == 0 ||
128 p[0] > radius ) {
129 VipsMorphology *morphology = VIPS_MORPHOLOGY( circle->nearest );
130 VipsImage *in = morphology->in;
131 int ps = VIPS_IMAGE_SIZEOF_PEL( in );
132 VipsPel *pi = VIPS_IMAGE_ADDR( in,
133 circle->seed->x, circle->seed->y );
134 VipsPel *qi = VIPS_IMAGE_ADDR( circle->nearest->out,
135 x, y );
136
137 int i;
138
139 p[0] = radius;
140 circle->octant_mask |= 1 << octant;
141
142 for( i = 0; i < ps; i++ )
143 qi[i] = pi[i];
144 }
145 }
146
147 static void
vips_fill_nearest_pixel_clip(Circle * circle,int x,int y,int octant)148 vips_fill_nearest_pixel_clip( Circle *circle, int x, int y, int octant )
149 {
150 if( (circle->seed->octant_mask & (1 << octant)) == 0 )
151 return;
152
153 if( x >= 0 &&
154 x < circle->nearest->width &&
155 y >= 0 &&
156 y < circle->nearest->height )
157 vips_fill_nearest_pixel( circle, x, y, octant );
158 }
159
160 static void
vips_fill_nearest_scanline(VipsImage * image,int y,int x1,int x2,int quadrant,void * client)161 vips_fill_nearest_scanline( VipsImage *image,
162 int y, int x1, int x2, int quadrant, void *client )
163 {
164 Circle *circle = (Circle *) client;
165
166 circle->nearest_pixel( circle, x1, y, quadrant );
167 circle->nearest_pixel( circle, x2, y, quadrant + 4 );
168
169 /* We have to do one point back as well, or we'll leave gaps at
170 * around 45 degrees.
171 */
172 if( quadrant == 0 ) {
173 circle->nearest_pixel( circle, x1, y - 1, quadrant );
174 circle->nearest_pixel( circle, x2, y - 1, quadrant + 4 );
175 }
176 else if( quadrant == 1 ) {
177 circle->nearest_pixel( circle, x1, y + 1, quadrant );
178 circle->nearest_pixel( circle, x2, y + 1, quadrant + 4 );
179 }
180 else {
181 circle->nearest_pixel( circle, x1 + 1, y, quadrant );
182 circle->nearest_pixel( circle, x2 - 1, y, quadrant + 4 );
183 }
184 }
185
186 static void
vips_fill_nearest_grow_seed(VipsFillNearest * nearest,Seed * seed)187 vips_fill_nearest_grow_seed( VipsFillNearest *nearest, Seed *seed )
188 {
189 Circle circle;
190
191 circle.nearest = nearest;
192 circle.seed = seed;
193 circle.octant_mask = 0;
194
195 if( seed->x - seed->r >= 0 &&
196 seed->x + seed->r < nearest->width &&
197 seed->y - seed->r >= 0 &&
198 seed->y + seed->r < nearest->height )
199 circle.nearest_pixel = vips_fill_nearest_pixel;
200 else
201 circle.nearest_pixel = vips_fill_nearest_pixel_clip;
202
203 vips__draw_circle_direct( nearest->distance,
204 seed->x, seed->y, seed->r,
205 vips_fill_nearest_scanline, &circle );
206
207 /* Update the action_mask for this seed. Next time, we can skip any
208 * octants where we failed to act this time.
209 */
210 seed->octant_mask = circle.octant_mask;
211
212 seed->r += 1;
213 }
214
215 static int
vips_fill_nearest_build(VipsObject * object)216 vips_fill_nearest_build( VipsObject *object )
217 {
218 VipsMorphology *morphology = VIPS_MORPHOLOGY( object );
219 VipsFillNearest *nearest = (VipsFillNearest *) object;
220 VipsImage **t = (VipsImage **) vips_object_local_array( object, 2 );
221
222 int ps;
223 int x, y, i;
224
225 if( VIPS_OBJECT_CLASS( vips_fill_nearest_parent_class )->
226 build( object ) )
227 return( -1 );
228
229 if( vips_image_wio_input( morphology->in ) )
230 return( -1 );
231 nearest->width = morphology->in->Xsize;
232 nearest->height = morphology->in->Ysize;
233
234 ps = VIPS_IMAGE_SIZEOF_PEL( morphology->in );
235 nearest->seeds = g_array_new( FALSE, FALSE, sizeof( Seed ) );
236 for( y = 0; y < nearest->height; y++ ) {
237 VipsPel *p;
238
239 p = VIPS_IMAGE_ADDR( morphology->in, 0, y );
240 for( x = 0; x < nearest->width; x++ ) {
241 for( i = 0; i < ps; i++ )
242 if( p[i] )
243 break;
244
245 if( i != ps ) {
246 Seed *seed;
247
248 g_array_set_size( nearest->seeds,
249 nearest->seeds->len + 1 );
250 seed = &g_array_index( nearest->seeds,
251 Seed, nearest->seeds->len - 1 );
252 seed->x = x;
253 seed->y = y;
254 seed->r = 1;
255 seed->octant_mask = 255;
256 }
257
258 p += ps;
259 }
260 }
261
262 /* Create the output and distance images in memory.
263 */
264 g_object_set( object, "distance", vips_image_new_memory(), NULL );
265 if( vips_black( &t[1], nearest->width, nearest->height, NULL ) ||
266 vips_cast( t[1], &t[2], VIPS_FORMAT_FLOAT, NULL ) ||
267 vips_image_write( t[2], nearest->distance ) )
268 return( -1 );
269
270 g_object_set( object, "out", vips_image_new_memory(), NULL );
271 if( vips_image_write( morphology->in, nearest->out ) )
272 return( -1 );
273
274 while( nearest->seeds->len > 0 ) {
275 #ifdef DEBUG
276 printf( "looping for %d seeds ...\n", nearest->seeds->len );
277 #endif /*DEBUG*/
278
279 /* Grow all seeds by one pixel.
280 */
281 for( i = 0; i < nearest->seeds->len; i++ )
282 vips_fill_nearest_grow_seed( nearest,
283 &g_array_index( nearest->seeds, Seed, i ) );
284
285 /* Remove dead seeds.
286 */
287 i = 0;
288 while( i < nearest->seeds->len ) {
289 Seed *seed = &g_array_index( nearest->seeds, Seed, i );
290
291 if( seed->octant_mask == 0 )
292 g_array_remove_index_fast( nearest->seeds, i );
293 else
294 i += 1;
295 }
296 }
297
298 return( 0 );
299 }
300
301 static void
vips_fill_nearest_class_init(VipsFillNearestClass * class)302 vips_fill_nearest_class_init( VipsFillNearestClass *class )
303 {
304 GObjectClass *gobject_class = G_OBJECT_CLASS( class );
305 VipsObjectClass *vobject_class = VIPS_OBJECT_CLASS( class );
306
307 gobject_class->finalize = vips_fill_nearest_finalize;
308 gobject_class->set_property = vips_object_set_property;
309 gobject_class->get_property = vips_object_get_property;
310
311 vobject_class->nickname = "fill_nearest";
312 vobject_class->description =
313 _( "fill image zeros with nearest non-zero pixel" );
314 vobject_class->build = vips_fill_nearest_build;
315
316 VIPS_ARG_IMAGE( class, "out", 2,
317 _( "Out" ),
318 _( "Value of nearest non-zero pixel" ),
319 VIPS_ARGUMENT_REQUIRED_OUTPUT,
320 G_STRUCT_OFFSET( VipsFillNearest, out ) );
321
322 VIPS_ARG_IMAGE( class, "distance", 3,
323 _( "Distance" ),
324 _( "Distance to nearest non-zero pixel" ),
325 VIPS_ARGUMENT_OPTIONAL_OUTPUT,
326 G_STRUCT_OFFSET( VipsFillNearest, distance ) );
327
328 }
329
330 static void
vips_fill_nearest_init(VipsFillNearest * nearest)331 vips_fill_nearest_init( VipsFillNearest *nearest )
332 {
333 }
334
335 /**
336 * vips_fill_nearest: (method)
337 * @in: image to test
338 * @out: image with zero pixels filled with the nearest non-zero pixel
339 * @...: %NULL-terminated list of optional named arguments
340 *
341 * Optional arguments:
342 *
343 * * @distance: output image of distance to nearest non-zero pixel
344 *
345 * Fill outwards from every non-zero pixel in @in, setting pixels in @distance
346 * and @value.
347 *
348 * At the position of zero pixels in @in, @distance contains the distance to
349 * the nearest non-zero pixel in @in, and @value contains the value of that
350 * pixel.
351 *
352 * @distance is a one-band float image. @value has the same number of bands and
353 * format as @in.
354 *
355 * See also: vips_hist_find_indexed().
356 *
357 * Returns: 0 on success, -1 on error.
358 */
359 int
vips_fill_nearest(VipsImage * in,VipsImage ** out,...)360 vips_fill_nearest( VipsImage *in, VipsImage **out, ... )
361 {
362 va_list ap;
363 int result;
364
365 va_start( ap, out );
366 result = vips_call_split( "fill_nearest", ap, in, out );
367 va_end( ap );
368
369 return( result );
370 }
371