scanner.c

00001 /*------------------------------------------------------------------------
00002  *  Copyright 2007-2009 (c) Jeff Brown <spadix@users.sourceforge.net>
00003  *
00004  *  This file is part of the ZBar Bar Code Reader.
00005  *
00006  *  The ZBar Bar Code Reader is free software; you can redistribute it
00007  *  and/or modify it under the terms of the GNU Lesser Public License as
00008  *  published by the Free Software Foundation; either version 2.1 of
00009  *  the License, or (at your option) any later version.
00010  *
00011  *  The ZBar Bar Code Reader is distributed in the hope that it will be
00012  *  useful, but WITHOUT ANY WARRANTY; without even the implied warranty
00013  *  of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *  GNU Lesser Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU Lesser Public License
00017  *  along with the ZBar Bar Code Reader; if not, write to the Free
00018  *  Software Foundation, Inc., 51 Franklin St, Fifth Floor,
00019  *  Boston, MA  02110-1301  USA
00020  *
00021  *  http://sourceforge.net/projects/zbar
00022  *------------------------------------------------------------------------*/
00023 
00024 #include <config.h>
00025 #include <stdlib.h>     /* malloc, free, abs */
00026 #include <string.h>     /* memset */
00027 
00028 #include <zbar.h>
00029 #include "svg.h"
00030 
00031 #ifdef DEBUG_SCANNER
00032 # define DEBUG_LEVEL (DEBUG_SCANNER)
00033 #endif
00034 #include "zbar_debug.h"
00035 
00036 #ifndef ZBAR_FIXED
00037 # define ZBAR_FIXED 5
00038 #endif
00039 #define ROUND (1 << (ZBAR_FIXED - 1))
00040 
00041 /* FIXME add runtime config API for these */
00042 #ifndef ZBAR_SCANNER_THRESH_MIN
00043 # define ZBAR_SCANNER_THRESH_MIN  4
00044 #endif
00045 
00046 #ifndef ZBAR_SCANNER_THRESH_INIT_WEIGHT
00047 # define ZBAR_SCANNER_THRESH_INIT_WEIGHT .44
00048 #endif
00049 #define THRESH_INIT ((unsigned)((ZBAR_SCANNER_THRESH_INIT_WEIGHT       \
00050                                  * (1 << (ZBAR_FIXED + 1)) + 1) / 2))
00051 
00052 #ifndef ZBAR_SCANNER_THRESH_FADE
00053 # define ZBAR_SCANNER_THRESH_FADE 8
00054 #endif
00055 
00056 #ifndef ZBAR_SCANNER_EWMA_WEIGHT
00057 # define ZBAR_SCANNER_EWMA_WEIGHT .78
00058 #endif
00059 #define EWMA_WEIGHT ((unsigned)((ZBAR_SCANNER_EWMA_WEIGHT              \
00060                                  * (1 << (ZBAR_FIXED + 1)) + 1) / 2))
00061 
00062 /* scanner state */
00063 struct zbar_scanner_s {
00064     zbar_decoder_t *decoder; /* associated bar width decoder */
00065     unsigned y1_min_thresh; /* minimum threshold */
00066 
00067     unsigned x;             /* relative scan position of next sample */
00068     int y0[4];              /* short circular buffer of average intensities */
00069 
00070     int y1_sign;            /* slope at last crossing */
00071     unsigned y1_thresh;     /* current slope threshold */
00072 
00073     unsigned cur_edge;      /* interpolated position of tracking edge */
00074     unsigned last_edge;     /* interpolated position of last located edge */
00075     unsigned width;         /* last element width */
00076 };
00077 
00078 zbar_scanner_t *zbar_scanner_create (zbar_decoder_t *dcode)
00079 {
00080     zbar_scanner_t *scn = malloc(sizeof(zbar_scanner_t));
00081     scn->decoder = dcode;
00082     scn->y1_min_thresh = ZBAR_SCANNER_THRESH_MIN;
00083     zbar_scanner_reset(scn);
00084     return(scn);
00085 }
00086 
00087 void zbar_scanner_destroy (zbar_scanner_t *scn)
00088 {
00089     free(scn);
00090 }
00091 
00092 zbar_symbol_type_t zbar_scanner_reset (zbar_scanner_t *scn)
00093 {
00094     memset(&scn->x, 0, sizeof(zbar_scanner_t) + (void*)scn - (void*)&scn->x);
00095     scn->y1_thresh = scn->y1_min_thresh;
00096     if(scn->decoder)
00097         zbar_decoder_reset(scn->decoder);
00098     return(ZBAR_NONE);
00099 }
00100 
00101 unsigned zbar_scanner_get_width (const zbar_scanner_t *scn)
00102 {
00103     return(scn->width);
00104 }
00105 
00106 unsigned zbar_scanner_get_edge (const zbar_scanner_t *scn,
00107                                 unsigned offset,
00108                                 int prec)
00109 {
00110     unsigned edge = scn->last_edge - offset - (1 << ZBAR_FIXED) - ROUND;
00111     prec = ZBAR_FIXED - prec;
00112     if(prec > 0)
00113         return(edge >> prec);
00114     else if(!prec)
00115         return(edge);
00116     else
00117         return(edge << -prec);
00118 }
00119 
00120 zbar_color_t zbar_scanner_get_color (const zbar_scanner_t *scn)
00121 {
00122     return((scn->y1_sign <= 0) ? ZBAR_SPACE : ZBAR_BAR);
00123 }
00124 
00125 static inline unsigned calc_thresh (zbar_scanner_t *scn)
00126 {
00127     /* threshold 1st to improve noise rejection */
00128     unsigned thresh = scn->y1_thresh;
00129     if((thresh <= scn->y1_min_thresh) || !scn->width) {
00130         dprintf(1, " tmin=%d", scn->y1_min_thresh);
00131         return(scn->y1_min_thresh);
00132     }
00133     /* slowly return threshold to min */
00134     unsigned dx = (scn->x << ZBAR_FIXED) - scn->last_edge;
00135     unsigned long t = thresh * dx;
00136     t /= scn->width;
00137     t /= ZBAR_SCANNER_THRESH_FADE;
00138     dprintf(1, " thr=%d t=%ld x=%d last=%d.%d (%d)",
00139             thresh, t, scn->x, scn->last_edge >> ZBAR_FIXED,
00140             scn->last_edge & ((1 << ZBAR_FIXED) - 1), dx);
00141     if(thresh > t) {
00142         thresh -= t;
00143         if(thresh > scn->y1_min_thresh)
00144             return(thresh);
00145     }
00146     scn->y1_thresh = scn->y1_min_thresh;
00147     return(scn->y1_min_thresh);
00148 }
00149 
00150 static inline zbar_symbol_type_t process_edge (zbar_scanner_t *scn,
00151                                                int y1)
00152 {
00153     if(!scn->y1_sign)
00154         scn->last_edge = scn->cur_edge = (1 << ZBAR_FIXED) + ROUND;
00155     else if(!scn->last_edge)
00156         scn->last_edge = scn->cur_edge;
00157 
00158     scn->width = scn->cur_edge - scn->last_edge;
00159     dprintf(1, " sgn=%d cur=%d.%d w=%d (%s)\n",
00160             scn->y1_sign, scn->cur_edge >> ZBAR_FIXED,
00161             scn->cur_edge & ((1 << ZBAR_FIXED) - 1), scn->width,
00162             ((y1 > 0) ? "SPACE" : "BAR"));
00163     scn->last_edge = scn->cur_edge;
00164 
00165 #if DEBUG_SVG > 1
00166     svg_path_moveto(SVG_ABS, scn->last_edge - (1 << ZBAR_FIXED) - ROUND, 0);
00167 #endif
00168 
00169     /* pass to decoder */
00170     if(scn->decoder)
00171         return(zbar_decode_width(scn->decoder, scn->width));
00172     return(ZBAR_PARTIAL);
00173 }
00174 
00175 inline zbar_symbol_type_t zbar_scanner_flush (zbar_scanner_t *scn)
00176 {
00177     if(!scn->y1_sign)
00178         return(ZBAR_NONE);
00179 
00180     unsigned x = (scn->x << ZBAR_FIXED) + ROUND;
00181 
00182     if(scn->cur_edge != x || scn->y1_sign > 0) {
00183         dprintf(1, "flush0:");
00184         zbar_symbol_type_t edge = process_edge(scn, -scn->y1_sign);
00185         scn->cur_edge = x;
00186         scn->y1_sign = -scn->y1_sign;
00187         return(edge);
00188     }
00189 
00190     scn->y1_sign = scn->width = 0;
00191     if(scn->decoder)
00192         return(zbar_decode_width(scn->decoder, 0));
00193     return(ZBAR_PARTIAL);
00194 }
00195 
00196 zbar_symbol_type_t zbar_scanner_new_scan (zbar_scanner_t *scn)
00197 {
00198     zbar_symbol_type_t edge = ZBAR_NONE;
00199     while(scn->y1_sign) {
00200         zbar_symbol_type_t tmp = zbar_scanner_flush(scn);
00201         if(tmp < 0 || tmp > edge)
00202             edge = tmp;
00203     }
00204 
00205     /* reset scanner and associated decoder */
00206     memset(&scn->x, 0, sizeof(zbar_scanner_t) + (void*)scn - (void*)&scn->x);
00207     scn->y1_thresh = scn->y1_min_thresh;
00208     if(scn->decoder)
00209         zbar_decoder_new_scan(scn->decoder);
00210     return(edge);
00211 }
00212 
00213 zbar_symbol_type_t zbar_scan_y (zbar_scanner_t *scn,
00214                                 int y)
00215 {
00216     /* FIXME calc and clip to max y range... */
00217     /* retrieve short value history */
00218     register int x = scn->x;
00219     register int y0_1 = scn->y0[(x - 1) & 3];
00220     register int y0_0 = y0_1;
00221     if(x) {
00222         /* update weighted moving average */
00223         y0_0 += ((int)((y - y0_1) * EWMA_WEIGHT)) >> ZBAR_FIXED;
00224         scn->y0[x & 3] = y0_0;
00225     }
00226     else
00227         y0_0 = y0_1 = scn->y0[0] = scn->y0[1] = scn->y0[2] = scn->y0[3] = y;
00228     register int y0_2 = scn->y0[(x - 2) & 3];
00229     register int y0_3 = scn->y0[(x - 3) & 3];
00230     /* 1st differential @ x-1 */
00231     register int y1_1 = y0_1 - y0_2;
00232     {
00233         register int y1_2 = y0_2 - y0_3;
00234         if((abs(y1_1) < abs(y1_2)) &&
00235            ((y1_1 >= 0) == (y1_2 >= 0)))
00236             y1_1 = y1_2;
00237     }
00238 
00239     /* 2nd differentials @ x-1 & x-2 */
00240     register int y2_1 = y0_0 - (y0_1 * 2) + y0_2;
00241     register int y2_2 = y0_1 - (y0_2 * 2) + y0_3;
00242 
00243     dprintf(1, "scan: x=%d y=%d y0=%d y1=%d y2=%d",
00244             x, y, y0_1, y1_1, y2_1);
00245 
00246     zbar_symbol_type_t edge = ZBAR_NONE;
00247     /* 2nd zero-crossing is 1st local min/max - could be edge */
00248     if((!y2_1 ||
00249         ((y2_1 > 0) ? y2_2 < 0 : y2_2 > 0)) &&
00250        (calc_thresh(scn) <= abs(y1_1)))
00251     {
00252         /* check for 1st sign change */
00253         char y1_rev = (scn->y1_sign > 0) ? y1_1 < 0 : y1_1 > 0;
00254         if(y1_rev)
00255             /* intensity change reversal - finalize previous edge */
00256             edge = process_edge(scn, y1_1);
00257 
00258         if(y1_rev || (abs(scn->y1_sign) < abs(y1_1))) {
00259             scn->y1_sign = y1_1;
00260 
00261             /* adaptive thresholding */
00262             /* start at multiple of new min/max */
00263             scn->y1_thresh = (abs(y1_1) * THRESH_INIT + ROUND) >> ZBAR_FIXED;
00264             dprintf(1, "\tthr=%d", scn->y1_thresh);
00265             if(scn->y1_thresh < scn->y1_min_thresh)
00266                 scn->y1_thresh = scn->y1_min_thresh;
00267 
00268             /* update current edge */
00269             int d = y2_1 - y2_2;
00270             scn->cur_edge = 1 << ZBAR_FIXED;
00271             if(!d)
00272                 scn->cur_edge >>= 1;
00273             else if(y2_1)
00274                 /* interpolate zero crossing */
00275                 scn->cur_edge -= ((y2_1 << ZBAR_FIXED) + 1) / d;
00276             scn->cur_edge += x << ZBAR_FIXED;
00277             dprintf(1, "\n");
00278         }
00279     }
00280     else
00281         dprintf(1, "\n");
00282     /* FIXME add fall-thru pass to decoder after heuristic "idle" period
00283        (eg, 6-8 * last width) */
00284     scn->x = x + 1;
00285     return(edge);
00286 }
00287 
00288 /* undocumented API for drawing cutesy debug graphics */
00289 void zbar_scanner_get_state (const zbar_scanner_t *scn,
00290                              unsigned *x,
00291                              unsigned *cur_edge,
00292                              unsigned *last_edge,
00293                              int *y0,
00294                              int *y1,
00295                              int *y2,
00296                              int *y1_thresh)
00297 {
00298     register int y0_0 = scn->y0[(scn->x - 1) & 3];
00299     register int y0_1 = scn->y0[(scn->x - 2) & 3];
00300     register int y0_2 = scn->y0[(scn->x - 3) & 3];
00301     if(x) *x = scn->x - 1;
00302     if(cur_edge) *cur_edge = scn->cur_edge;
00303     if(last_edge) *last_edge = scn->last_edge;
00304     if(y0) *y0 = y0_1;
00305     if(y1) *y1 = y0_1 - y0_2;
00306     if(y2) *y2 = y0_0 - (y0_1 * 2) + y0_2;
00307     /* NB not quite accurate (uses updated x) */
00308     zbar_scanner_t *mut_scn = (zbar_scanner_t*)scn;
00309     if(y1_thresh) *y1_thresh = calc_thresh(mut_scn);
00310     dprintf(1, "\n");
00311 }
00312