/*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 <config.h>
#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
评论0
最新资源