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