QR码解析。 C源码解析QR

/*Copyright (C) 2008-2009 Timothy B. Terriberry (tterribe@xiph.org) You can redistribute this library and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.*/ #include <stdlib.h> #include <limits.h> #include <string.h> #include <time.h> #include "qrcode.h" #include "qrdec.h" #include "bch15_5.h" #include "rs.h" #include "isaac.h" #include "util.h" #include "binarize.h" #include "image.h" #include "error.h" #include "svg.h" typedef int qr_line[3]; typedef struct qr_finder_cluster qr_finder_cluster; typedef struct qr_finder_edge_pt qr_finder_edge_pt; typedef struct qr_finder_center qr_finder_center; typedef struct qr_aff qr_aff; typedef struct qr_hom qr_hom; typedef struct qr_finder qr_finder; typedef struct qr_hom_cell qr_hom_cell; typedef struct qr_sampling_grid qr_sampling_grid; typedef struct qr_pack_buf qr_pack_buf; /*The number of bits in an int. Note the cast to (int): this prevents this value from "promoting" whole expressions to an (unsigned) size_t.*/ #define QR_INT_BITS ((int)sizeof(int)*CHAR_BIT) #define QR_INT_LOGBITS (QR_ILOG(QR_INT_BITS)) /*A 14 bit resolution for a homography ensures that the ideal module size for a version 40 code differs from that of a version 39 code by at least 2.*/ #define QR_HOM_BITS (14) /*The number of bits of sub-module precision to use when searching for alignment patterns. Two bits allows an alignment pattern to be found even if the modules have been eroded by up to 50% (due to blurring, etc.). This must be at least one, since it affects the dynamic range of the transforms, and we sample at half-module resolution to compute a bounding quadrilateral for the code.*/ #define QR_ALIGN_SUBPREC (2) /* collection of finder lines */ typedef struct qr_finder_lines { qr_finder_line *lines; int nlines, clines; } qr_finder_lines; struct qr_reader { /*The GF(256) representation used in Reed-Solomon decoding.*/ rs_gf256 gf; /*The random number generator used by RANSAC.*/ isaac_ctx isaac; /* current finder state, horizontal and vertical lines */ qr_finder_lines finder_lines[2]; }; /*Initializes a client reader handle.*/ static void qr_reader_init (qr_reader *reader) { /*time_t now; now=time(NULL); isaac_init(&_reader->isaac,&now,sizeof(now));*/ isaac_init(&reader->isaac, NULL, 0); rs_gf256_init(&reader->gf, QR_PPOLY); } /*Allocates a client reader handle.*/ qr_reader *_zbar_qr_create (void) { qr_reader *reader = (qr_reader*)calloc(1, sizeof(*reader)); qr_reader_init(reader); return(reader); } /*Frees a client reader handle.*/ void _zbar_qr_destroy (qr_reader *reader) { zprintf(1, "max finder lines = %dx%d\n", reader->finder_lines[0].clines, reader->finder_lines[1].clines); if(reader->finder_lines[0].lines) free(reader->finder_lines[0].lines); if(reader->finder_lines[1].lines) free(reader->finder_lines[1].lines); free(reader); } /* reset finder state between scans */ void _zbar_qr_reset (qr_reader *reader) { reader->finder_lines[0].nlines = 0; reader->finder_lines[1].nlines = 0; } /*A cluster of lines crossing a finder pattern (all in the same direction).*/ struct qr_finder_cluster{ /*Pointers to the lines crossing the pattern.*/ qr_finder_line **lines; /*The number of lines in the cluster.*/ int nlines; }; /*A point on the edge of a finder pattern. These are obtained from the endpoints of the lines crossing this particular pattern.*/ struct qr_finder_edge_pt{ /*The location of the edge point.*/ qr_point pos; /*A label classifying which edge this belongs to: 0: negative u edge (left) 1: positive u edge (right) 2: negative v edge (top) 3: positive v edge (bottom)*/ int edge; /*The (signed) perpendicular distance of the edge point from a line parallel to the edge passing through the finder center, in (u,v) coordinates. This is also re-used by RANSAC to store inlier flags.*/ int extent; }; /*The center of a finder pattern obtained from the crossing of one or more clusters of horizontal finder lines with one or more clusters of vertical finder lines.*/ struct qr_finder_center{ /*The estimated location of the finder center.*/ qr_point pos; /*The list of edge points from the crossing lines.*/ qr_finder_edge_pt *edge_pts; /*The number of edge points from the crossing lines.*/ int nedge_pts; }; static int qr_finder_vline_cmp(const void *_a,const void *_b){ const qr_finder_line *a; const qr_finder_line *b; a=(const qr_finder_line *)_a; b=(const qr_finder_line *)_b; return ((a->pos[0]>b->pos[0])-(a->pos[0]<b->pos[0])<<1)+ (a->pos[1]>b->pos[1])-(a->pos[1]<b->pos[1]); } /*Clusters adjacent lines into groups that are large enough to be crossing a finder pattern (relative to their length). _clusters: The buffer in which to store the clusters found. _neighbors: The buffer used to store the lists of lines in each cluster. _lines: The list of lines to cluster. Horizontal lines must be sorted in ascending order by Y coordinate, with ties broken by X coordinate. Vertical lines must be sorted in ascending order by X coordinate, with ties broken by Y coordinate. _nlines: The number of lines in the set of lines to cluster. _v: 0 for horizontal lines, or 1 for vertical lines. Return: The number of clusters.*/ static int qr_finder_cluster_lines(qr_finder_cluster *_clusters, qr_finder_line **_neighbors,qr_finder_line *_lines,int _nlines,int _v){ unsigned char *mark; qr_finder_line **neighbors; int nneighbors; int nclusters; int i; /*TODO: Kalman filters!*/ mark=(unsigned char *)calloc(_nlines,sizeof(*mark)); neighbors=_neighbors; nclusters=0; for(i=0;i<_nlines-1;i++)if(!mark[i]){ int len; int j; nneighbors=1; neighbors[0]=_lines+i; len=_lines[i].len; for(j=i+1;j<_nlines;j++)if(!mark[j]){ const qr_finder_line *a; const qr_finder_line *b; int thresh; a=neighbors[nneighbors-1]; b=_lines+j; /*The clustering threshold is proportional to the size of the lines, since minor noise in large areas can interrupt patterns more easily at high resolutions.*/ thresh=a->len+7>>2; if(abs(a->pos[1-_v]-b->pos[1-_v])>thresh)break; if(abs(a->pos[_v]-b->pos[_v])>thresh)continue; if(abs(a->pos[_v]+a->len-b->pos[_v]-b->len)>thresh)continue; if(a->boffs>0&&b->boffs>0&& abs(a->pos[_v]-a->boffs-b->pos[_v]+b->boffs)>thresh){ continue; } if(a->eoffs>0&&b->eoffs>0&& abs(a->pos[_v]+a->len+a->eoffs-b->pos[_v]-b->len-b->eoffs)>thresh){ continue; } neighbors[nneighbors++]=_lines+j; len+=b->len; } /*We require at least three lines to form a cluster, which eliminates a large number of false positives, saving considerable decoding time. This should still be sufficient for 1-pixel codes with no noise.*/ if(nneighbors<3)continue; /*The expected number of lines crossing a finder pattern is equal to their average length. We accept the cluster if size is at least 1/3 their average length (this is a very small threshold, but was needed for some test images).*/ len=((len<<1)+nneighbors)/(nneighbors<<1); if(nneighbors*(5<<QR_FINDER_SUBPREC)>=len){ _clusters[nclusters].lines=neighbors; _clusters[nclusters].nlines=nneighbors; for(j=0;j<nneighbors;j++)mark[neighbors[j]-_lines]=1; neighbors+=nneighbors; nclusters++; } } free(mark); return nclusters; } /*Adds the coordinates of the edge points from the