# [zbar源码分析]确定探测图形中心点数量

```static int qr_finder_centers_locate(qr_finder_center **_centers,
int _width,int _height){

qr_finder_line    **hneighbors;
qr_finder_cluster  *hclusters;
int                 nhclusters;
qr_finder_line    **vneighbors;
qr_finder_cluster  *vclusters;
int                 nvclusters;
int                 ncenters;

/*Cluster the detected lines.*/
hneighbors=(qr_finder_line **)mymalloc(SRAMEX, nhlines*sizeof(*hneighbors));
/*We require more than one line per cluster, so there are at most nhlines/2.*/
hclusters=(qr_finder_cluster *)mymalloc(SRAMEX, (nhlines1)*sizeof(*hclusters));
nhclusters=qr_finder_cluster_lines(hclusters,hneighbors,hlines,nhlines,0);
/*We need vertical lines to be sorted by X coordinate, with ties broken by Y
coordinate, for clustering purposes.
We scan the image in the opposite order for cache efficiency, so sort the
lines we found here.*/
qsort(vlines,nvlines,sizeof(*vlines),qr_finder_vline_cmp);
vneighbors=(qr_finder_line **)mymalloc(SRAMEX, nvlines*sizeof(*vneighbors));
/*We require more than one line per cluster, so there are at most nvlines/2.*/
vclusters=(qr_finder_cluster *)mymalloc(SRAMEX, (nvlines1)*sizeof(*vclusters));
nvclusters=qr_finder_cluster_lines(vclusters,vneighbors,vlines,nvlines,1);
/*Find line crossings among the clusters.*/
if(nhclusters=3nvclusters=3){
qr_finder_edge_pt  *edge_pts;
qr_finder_center   *centers;
int                 nedge_pts;
int                 i;
nedge_pts=0;
for(i=0;inhclusters;i++)nedge_pts+=hclusters[i].nlines;
for(i=0;invclusters;i++)nedge_pts+=vclusters[i].nlines;
nedge_pts=1;
edge_pts=(qr_finder_edge_pt *)mymalloc(SRAMEX, nedge_pts*sizeof(*edge_pts));
centers=(qr_finder_center *)mymalloc(SRAMEX,
QR_MINI(nhclusters,nvclusters)*sizeof(*centers));
ncenters=qr_finder_find_crossings(centers,edge_pts,
hclusters,nhclusters,vclusters,nvclusters);
*_centers=centers;
*_edge_pts=edge_pts;
}
else ncenters=0;
myfree(SRAMEX, vclusters);
myfree(SRAMEX, vneighbors);
myfree(SRAMEX, hclusters);
myfree(SRAMEX, hneighbors);
return ncenters;
}```

```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 *)mymalloc(SRAMEX, _nlines * sizeof(*mark));
if(NULL == mark)
return 1;
mymemset(mark, 0, _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+72;
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-boffs0b-boffs0
abs(a-pos[_v]-a-boffs-b-pos[_v]+b-boffs)thresh){
continue;
}
if(a-eoffs0b-eoffs0
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(nneighbors3)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=((len1)+nneighbors)/(nneighbors1);
if(nneighbors*(5QR_FINDER_SUBPREC)=len){
_clusters[nclusters].lines=neighbors;
_clusters[nclusters].nlines=nneighbors;
for(j=0;jnneighbors;j++)mark[neighbors[j]-_lines]=1;
neighbors+=nneighbors;
nclusters++;
}
}
myfree(SRAMEX, mark);
return nclusters;
}```

```struct qr_finder_cluster{
/*Pointers to the lines crossing the pattern.*/
qr_finder_line **lines;
/*The number of lines in the cluster.*/
int              nlines;
};```

```struct qr_finder_line {
/*The location of the upper/left endpoint of the line.
The left/upper edge of the center section is used, since other lines must
cross in this region.*/
qr_point pos;
/*The length of the center section.
This extends to the right/bottom of the center section, since other lines
must cross in this region.*/
int      len;
/*The offset to the midpoint of the upper/left section (part of the outside
ring), or 0 if we couldn't identify the edge of the beginning section.
We use the midpoint instead of the edge because it can be located more
reliably.*/
int      boffs;
/*The offset to the midpoint of the end section (part of the outside ring),
or 0 if we couldn't identify the edge of the end section.
We use the midpoint instead of the edge because it can be located more
reliably.*/
int      eoffs;
};```