1 /*
2 SPDX-FileCopyrightText: 1993-2011 Emmanuel Bertin -- IAP /CNRS/UPMC
3 SPDX-FileCopyrightText: 2014 SEP developers
4
5 SPDX-License-Identifier: LGPL-3.0-or-later
6 */
7
8 /* Note: was extract.c in SExtractor. */
9
10 #include <math.h>
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14 #include "sep.h"
15 #include "sepcore.h"
16 #include "extract.h"
17
18 #define NOBJ 256 /* starting number of obj. */
19
20 void lutzsort(infostruct *, objliststruct *);
21
22 /*------------------------- Static buffers for lutz() -----------------------*/
23
24 static infostruct *info=NULL, *store=NULL;
25 static char *marker=NULL;
26 static pixstatus *psstack=NULL;
27 static int *start=NULL, *end=NULL, *discan=NULL;
28 static int xmin, ymin, xmax, ymax;
29
30
31 /******************************* lutzalloc ***********************************/
32 /*
33 Allocate once for all memory space for buffers used by lutz().
34 */
lutzalloc(int width,int height)35 int lutzalloc(int width, int height)
36 {
37 int *discant;
38 int stacksize, i, status=RETURN_OK;
39
40 stacksize = width+1;
41 xmin = ymin = 0;
42 xmax = width-1;
43 ymax = height-1;
44 QMALLOC(info, infostruct, stacksize, status);
45 QMALLOC(store, infostruct, stacksize, status);
46 QMALLOC(marker, char, stacksize, status);
47 QMALLOC(psstack, pixstatus, stacksize, status);
48 QMALLOC(start, int, stacksize, status);
49 QMALLOC(end, int, stacksize, status);
50 QMALLOC(discan, int, stacksize, status);
51 discant = discan;
52 for (i=stacksize; i--;)
53 *(discant++) = -1;
54
55 return status;
56
57 exit:
58 lutzfree();
59
60 return status;
61 }
62
63 /******************************* lutzfree ************************************/
64 /*
65 Free once for all memory space for buffers used by lutz().
66 */
lutzfree()67 void lutzfree()
68 {
69 free(discan);
70 discan = NULL;
71 free(info);
72 info = NULL;
73 free(store);
74 store = NULL;
75 free(marker);
76 marker = NULL;
77 free(psstack);
78 psstack = NULL;
79 free(start);
80 start = NULL;
81 free(end);
82 end = NULL;
83 return;
84 }
85
86
87 /********************************** lutz *************************************/
88 /*
89 C implementation of R.K LUTZ' algorithm for the extraction of 8-connected pi-
90 xels in an image
91 */
lutz(pliststruct * plistin,int * objrootsubmap,int subx,int suby,int subw,objstruct * objparent,objliststruct * objlist,int minarea)92 int lutz(pliststruct *plistin,
93 int *objrootsubmap, int subx, int suby, int subw,
94 objstruct *objparent, objliststruct *objlist, int minarea)
95 {
96 static infostruct curpixinfo,initinfo;
97 objstruct *obj;
98 pliststruct *plist,*pixel, *plistint;
99
100 char newmarker;
101 int cn, co, luflag, pstop, xl,xl2,yl,
102 out, deb_maxarea, stx,sty,enx,eny, step,
103 nobjm = NOBJ,
104 inewsymbol, *iscan;
105 short trunflag;
106 PIXTYPE thresh;
107 pixstatus cs, ps;
108
109 out = RETURN_OK;
110
111 deb_maxarea = minarea<MAXDEBAREA?minarea:MAXDEBAREA; /* 3 or less */
112 plistint = plistin;
113 stx = objparent->xmin;
114 sty = objparent->ymin;
115 enx = objparent->xmax;
116 eny = objparent->ymax;
117 thresh = objlist->thresh;
118 initinfo.pixnb = 0;
119 initinfo.flag = 0;
120 initinfo.firstpix = initinfo.lastpix = -1;
121 cn = 0;
122
123 iscan = objrootsubmap + (sty-suby)*subw + (stx-subx);
124
125 /* As we only analyze a fraction of the map, a step occurs between lines */
126 step = subw - (++enx-stx);
127 eny++;
128
129 /*------Allocate memory to store object data */
130 free(objlist->obj);
131
132 if (!(obj=objlist->obj=(objstruct *)malloc(nobjm*sizeof(objstruct))))
133 {
134 out = MEMORY_ALLOC_ERROR;
135 plist = NULL; /* To avoid gcc -Wall warnings */
136 goto exit_lutz;
137 }
138
139 /*------Allocate memory for the pixel list */
140 free(objlist->plist);
141 if (!(objlist->plist
142 = (pliststruct *)malloc((eny-sty)*(enx-stx)*plistsize)))
143 {
144 out = MEMORY_ALLOC_ERROR;
145 plist = NULL; /* To avoid gcc -Wall warnings */
146 goto exit_lutz;
147 }
148
149 pixel = plist = objlist->plist;
150
151 /*----------------------------------------*/
152 for (xl=stx; xl<=enx; xl++)
153 marker[xl] = 0;
154
155 objlist->nobj = 0;
156 co = pstop = 0;
157 curpixinfo.pixnb = 1;
158
159 for (yl=sty; yl<=eny; yl++, iscan += step)
160 {
161 ps = COMPLETE;
162 cs = NONOBJECT;
163 trunflag = (yl==0 || yl==ymax) ? SEP_OBJ_TRUNC : 0;
164 if (yl==eny)
165 iscan = discan;
166
167 for (xl=stx; xl<=enx; xl++)
168 {
169 newmarker = marker[xl];
170 marker[xl] = 0;
171 if ((inewsymbol = (xl!=enx)?*(iscan++):-1) < 0)
172 luflag = 0;
173 else
174 {
175 curpixinfo.flag = trunflag;
176 plistint = plistin+inewsymbol;
177 luflag = (PLISTPIX(plistint, cdvalue) > thresh?1:0);
178 }
179 if (luflag)
180 {
181 if (xl==0 || xl==xmax)
182 curpixinfo.flag |= SEP_OBJ_TRUNC;
183 memcpy(pixel, plistint, (size_t)plistsize);
184 PLIST(pixel, nextpix) = -1;
185 curpixinfo.lastpix = curpixinfo.firstpix = cn;
186 cn += plistsize;
187 pixel += plistsize;
188
189 /*----------------- Start Segment -----------------------------*/
190 if (cs != OBJECT)
191 {
192 cs = OBJECT;
193 if (ps == OBJECT)
194 {
195 if (start[co] == UNKNOWN)
196 {
197 marker[xl] = 'S';
198 start[co] = xl;
199 }
200 else marker[xl] = 's';
201 }
202 else
203 {
204 psstack[pstop++] = ps;
205 marker[xl] = 'S';
206 start[++co] = xl;
207 ps = COMPLETE;
208 info[co] = initinfo;
209 }
210 }
211 }
212
213 /*-------------------Process New Marker ---------------------------*/
214 if (newmarker)
215 {
216 if (newmarker == 'S')
217 {
218 psstack[pstop++] = ps;
219 if (cs == NONOBJECT)
220 {
221 psstack[pstop++] = COMPLETE;
222 info[++co] = store[xl];
223 start[co] = UNKNOWN;
224 }
225 else
226 update(&info[co], &store[xl], plist);
227 ps = OBJECT;
228 }
229
230 else if (newmarker == 's')
231 {
232 if ((cs == OBJECT) && (ps == COMPLETE))
233 {
234 pstop--;
235 xl2 = start[co];
236 update(&info[co-1], &info[co], plist);
237 if (start[--co] == UNKNOWN)
238 start[co] = xl2;
239 else
240 marker[xl2] = 's';
241 }
242 ps = OBJECT;
243 }
244 else if (newmarker == 'f')
245 ps = INCOMPLETE;
246 else if (newmarker == 'F')
247 {
248 ps = psstack[--pstop];
249 if ((cs == NONOBJECT) && (ps == COMPLETE))
250 {
251 if (start[co] == UNKNOWN)
252 {
253 if ((int)info[co].pixnb >= deb_maxarea)
254 {
255 if (objlist->nobj>=nobjm)
256 if (!(obj = objlist->obj = (objstruct *)
257 realloc(obj, (nobjm+=nobjm/2)*
258 sizeof(objstruct))))
259 {
260 out = MEMORY_ALLOC_ERROR;
261 goto exit_lutz;
262 }
263 lutzsort(&info[co], objlist);
264 }
265 }
266 else
267 {
268 marker[end[co]] = 'F';
269 store[start[co]] = info[co];
270 }
271 co--;
272 ps = psstack[--pstop];
273 }
274 }
275 }
276 /* end process new marker -----------------------------------------*/
277
278 if (luflag)
279 update (&info[co],&curpixinfo, plist);
280 else
281 {
282 /* ----------------- End Segment ------------------------------*/
283 if (cs == OBJECT)
284 {
285 cs = NONOBJECT;
286 if (ps != COMPLETE)
287 {
288 marker[xl] = 'f';
289 end[co] = xl;
290 }
291 else
292 {
293 ps = psstack[--pstop];
294 marker[xl] = 'F';
295 store[start[co]] = info[co];
296 co--;
297 }
298 }
299 }
300 }
301 }
302
303 exit_lutz:
304
305 if (objlist->nobj && out == RETURN_OK)
306 {
307 if (!(objlist->obj=
308 (objstruct *)realloc(obj, objlist->nobj*sizeof(objstruct))))
309 out = MEMORY_ALLOC_ERROR;
310 }
311 else
312 {
313 free(obj);
314 objlist->obj = NULL;
315 }
316
317 if (cn && out == RETURN_OK)
318 {
319 if (!(objlist->plist=(pliststruct *)realloc(plist,cn)))
320 out = MEMORY_ALLOC_ERROR;
321 }
322 else
323 {
324 free(objlist->plist);
325 objlist->plist = NULL;
326 }
327
328 return out;
329 }
330
331 /********************************* lutzsort ***********************************/
332 /*
333 Add an object to the object list based on info (pixel info)
334 */
lutzsort(infostruct * info,objliststruct * objlist)335 void lutzsort(infostruct *info, objliststruct *objlist)
336 {
337 objstruct *obj = objlist->obj+objlist->nobj;
338
339 memset(obj, 0, (size_t)sizeof(objstruct));
340 obj->firstpix = info->firstpix;
341 obj->lastpix = info->lastpix;
342 obj->flag = info->flag;
343 objlist->npix += info->pixnb;
344
345 preanalyse(objlist->nobj, objlist);
346
347 objlist->nobj++;
348
349 return;
350 }
351
352 /********************************* update ************************************/
353 /*
354 update object's properties each time one of its pixels is scanned by lutz()
355 */
update(infostruct * infoptr1,infostruct * infoptr2,pliststruct * pixel)356 void update(infostruct *infoptr1, infostruct *infoptr2, pliststruct *pixel)
357 {
358 infoptr1->pixnb += infoptr2->pixnb;
359 infoptr1->flag |= infoptr2->flag;
360 if (infoptr1->firstpix == -1)
361 {
362 infoptr1->firstpix = infoptr2->firstpix;
363 infoptr1->lastpix = infoptr2->lastpix;
364 }
365 else if (infoptr2->lastpix != -1)
366 {
367 PLIST(pixel+infoptr1->lastpix, nextpix) = infoptr2->firstpix;
368 infoptr1->lastpix = infoptr2->lastpix;
369 }
370
371 return;
372 }
373