1 /*
2 extract.c
3
4 *%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5 *
6 * Part of: SExtractor
7 *
8 * Author: E.BERTIN (IAP)
9 *
10 * Contents: functions for extraction of connected pixels from
11 * a bitmap.
12 *
13 * Last modify: 26/11/2003
14 *
15 *%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16 */
17
18 #ifdef HAVE_CONFIG_H
19 #include "config.h"
20 #endif
21
22 #include <math.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "define.h"
27 #include "globals.h"
28 #include "prefs.h"
29 #include "extract.h"
30 #include "plist.h"
31
32 /*------------------------- Static buffers for lutz() -----------------------*/
33
34 static infostruct *info, *store;
35 static char *marker;
36 static status *psstack;
37 static int *start, *end, *discan, xmin,ymin,xmax,ymax;
38
39
40 /******************************* lutzalloc ***********************************/
41 /*
42 Allocate once for all memory space for buffers used by lutz().
43 */
lutzalloc(int width,int height)44 void lutzalloc(int width, int height)
45 {
46 int *discant,
47 stacksize, i;
48
49 stacksize = width+1;
50 xmin = ymin = 0;
51 xmax = width-1;
52 ymax = height-1;
53 QMALLOC(info, infostruct, stacksize);
54 QMALLOC(store, infostruct, stacksize);
55 QMALLOC(marker, char, stacksize);
56 QMALLOC(psstack, status, stacksize);
57 QMALLOC(start, int, stacksize);
58 QMALLOC(end, int, stacksize);
59 QMALLOC(discan, int, stacksize);
60 discant = discan;
61 for (i=stacksize; i--;)
62 *(discant++) = -1;
63
64 return;
65 }
66
67
68 /******************************* lutzfree ************************************/
69 /*
70 Free once for all memory space for buffers used by lutz().
71 */
lutzfree()72 void lutzfree()
73 {
74 free(discan);
75 free(info);
76 free(store);
77 free(marker);
78 free(psstack);
79 free(start);
80 free(end);
81
82 return;
83 }
84
85
86 /********************************** lutz *************************************/
87 /*
88 C implementation of R.K LUTZ' algorithm for the extraction of 8-connected pi-
89 xels in an image
90 */
lutz(objliststruct * objlistroot,int nroot,objstruct * objparent,objliststruct * objlist)91 int lutz(objliststruct *objlistroot, int nroot, objstruct *objparent,
92 objliststruct *objlist)
93
94 {
95 static infostruct curpixinfo,initinfo;
96 objstruct *obj, *objroot;
97 pliststruct *plist,*pixel, *plistin, *plistint;
98
99 char newmarker;
100 int cn, co, luflag, objnb, pstop, xl,xl2,yl,
101 out, minarea, stx,sty,enx,eny, step,
102 nobjm = NOBJ,
103 inewsymbol, *iscan;
104 short trunflag;
105 PIXTYPE thresh;
106 status cs, ps;
107
108 out = RETURN_OK;
109
110 minarea = prefs.deb_maxarea;
111 plistint = plistin = objlistroot->plist;
112 objroot = &objlistroot->obj[nroot];
113 stx = objparent->xmin;
114 sty = objparent->ymin;
115 enx = objparent->xmax;
116 eny = objparent->ymax;
117 thresh = objlist->dthresh;
118 initinfo.pixnb = 0;
119 initinfo.flag = 0;
120 initinfo.firstpix = initinfo.lastpix = -1;
121 cn = 0;
122 iscan = objroot->submap + (sty-objroot->suby)*objroot->subw
123 + (stx-objroot->subx);
124 /* As we only analyse a fraction of the map, a step occurs between lines */
125 step = objroot->subw - (++enx-stx);
126 eny++;
127
128 /*------Allocate memory to store object data */
129
130 free(objlist->obj);
131 if (!(obj=objlist->obj=(objstruct *)malloc(nobjm*sizeof(objstruct))))
132 {
133 out = RETURN_FATAL_ERROR;
134 plist = NULL; /* To avoid gcc -Wall warnings */
135 goto exit_lutz;
136 }
137
138 /*------Allocate memory for the pixel list */
139
140 free(objlist->plist);
141 if (!(objlist->plist
142 = (pliststruct *)malloc((eny-sty)*(enx-stx)*plistsize)))
143 {
144 out = RETURN_FATAL_ERROR;
145 plist = NULL; /* To avoid gcc -Wall warnings */
146 goto exit_lutz;
147 }
148
149 pixel = plist = objlist->plist;
150
151 /*----------------------------------------*/
152
153 for (xl=stx; xl<=enx; xl++)
154 marker[xl] = 0 ;
155
156 objnb = objlist->nobj = 0;
157 co = pstop = 0;
158 curpixinfo.pixnb = 1;
159
160 for (yl=sty; yl<=eny; yl++, iscan += step)
161 {
162 ps = COMPLETE;
163 cs = NONOBJECT;
164 trunflag = (yl==0 || yl==ymax) ? OBJ_TRUNC : 0;
165 if (yl==eny)
166 iscan = discan;
167
168 for (xl=stx; xl<=enx; xl++)
169 {
170 newmarker = marker[xl];
171 marker[xl] = 0;
172 if ((inewsymbol = (xl!=enx)?*(iscan++):-1) < 0)
173 luflag = 0;
174 else
175 {
176 curpixinfo.flag = trunflag;
177 plistint = plistin+inewsymbol;
178 luflag = (PLISTPIX(plistint, cdvalue) > thresh?1:0);
179 }
180 if (luflag)
181 {
182 if (xl==0 || xl==xmax)
183 curpixinfo.flag |= OBJ_TRUNC;
184 memcpy(pixel, plistint, (size_t)plistsize);
185 PLIST(pixel, nextpix) = -1;
186 curpixinfo.lastpix = curpixinfo.firstpix = cn;
187 cn += plistsize;
188 pixel += plistsize;
189 if (cs != OBJECT)
190 /*------------------------------- Start Segment -----------------------------*/
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 if (newmarker)
214 /*---------------------------- Process New Marker ---------------------------*/
215
216 {
217 if (newmarker == 'S')
218 {
219 psstack[pstop++] = ps;
220 if (cs == NONOBJECT)
221 {
222 psstack[pstop++] = COMPLETE;
223 info[++co] = store[xl];
224 start[co] = UNKNOWN;
225 }
226 else
227 update (&info[co],&store[xl], plist);
228 ps = OBJECT;
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 >= minarea)
254 {
255 if (objlist->nobj>=nobjm)
256 if (!(obj = objlist->obj = (objstruct *)
257 realloc(obj, (nobjm+=nobjm/2)* sizeof(objstruct))))
258 {
259 out = RETURN_FATAL_ERROR;
260 goto exit_lutz;
261 }
262 lutzsort(&info[co], objlist);
263 }
264 }
265 else
266 {
267 marker[end[co]] = 'F';
268 store[start[co]] = info[co];
269 }
270 co--;
271 ps = psstack[--pstop];
272 }
273 }
274 }
275
276 /*---------------------------------------------------------------------------*/
277
278 if (luflag)
279 update (&info[co],&curpixinfo, plist);
280 else
281 {
282 if (cs == OBJECT)
283 /*-------------------------------- End Segment ------------------------------*/
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
304 exit_lutz:
305
306 if (objlist->nobj && out == RETURN_OK)
307 {
308 if (!(objlist->obj=(objstruct *)realloc(obj,
309 objlist->nobj*sizeof(objstruct))))
310 error(EXIT_FAILURE,"problem with mem. realloc. in lutz()","");
311 }
312 else
313 {
314 free(obj);
315 objlist->obj = NULL;
316 }
317
318 if (cn && out == RETURN_OK)
319 {
320 if (!(objlist->plist=(pliststruct *)realloc(plist,cn)))
321 error(EXIT_FAILURE,"problem with mem. realloc. in lutz()","");
322 }
323 else
324 {
325 free(objlist->plist);
326 objlist->plist = NULL;
327 }
328
329 return out;
330 }
331
332
333 /********************************* lutzsort ***********************************/
334 /*
335 Build the object structure.
336 */
lutzsort(infostruct * info,objliststruct * objlist)337 void lutzsort(infostruct *info, objliststruct *objlist)
338
339 {
340 objstruct *obj = objlist->obj+objlist->nobj;
341
342 memset(obj, 0, (size_t)sizeof(objstruct));
343 obj->firstpix = info->firstpix;
344 obj->lastpix = info->lastpix;
345 obj->flag = info->flag;
346 objlist->npix += info->pixnb;
347
348 preanalyse(objlist->nobj, objlist, ANALYSE_FAST);
349
350 objlist->nobj++;
351
352 return;
353 }
354
355