Ryo Hagimoto / zbar_010

ZBar bar code reader . http://zbar.sourceforge.net/ ZBar is licensed under the GNU LGPL 2.1 to enable development of both open source and commercial projects.

Dependents:   GR-PEACH_Camera_in_barcode levkov_ov7670

LICENSE

The ZBar Bar Code Reader is Copyright (C) 2007-2009 Jeff Brown <spadix@users.sourceforge.net> The QR Code reader is Copyright (C) 1999-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.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

ISAAC is based on the public domain implementation by Robert J. Jenkins Jr., and is itself public domain.

Portions of the bit stream reader are copyright (C) The Xiph.Org Foundation 1994-2008, and are licensed under a BSD-style license.

The Reed-Solomon decoder is derived from an implementation (C) 1991-1995 Henry Minsky (hqm@ua.com, hqm@ai.mit.edu), and is licensed under the LGPL with permission.

zbar/qrcode/binarize.c@0:56c5742b9e2b, 2016-04-19 (annotated)

Committer:
RyoheiHagimoto
Date:
Tue Apr 19 02:00:37 2016 +0000
Revision:
0:56c5742b9e2b
First revicion

Who changed what in which revision?

UserRevisionLine numberNew contents of line
RyoheiHagimoto 0:56c5742b9e2b 1 /*Copyright (C) 2008-2009 Timothy B. Terriberry (tterribe@xiph.org)
RyoheiHagimoto 0:56c5742b9e2b 2 You can redistribute this library and/or modify it under the terms of the
RyoheiHagimoto 0:56c5742b9e2b 3 GNU Lesser General Public License as published by the Free Software
RyoheiHagimoto 0:56c5742b9e2b 4 Foundation; either version 2.1 of the License, or (at your option) any later
RyoheiHagimoto 0:56c5742b9e2b 5 version.*/
RyoheiHagimoto 0:56c5742b9e2b 6 #include <stdlib.h>
RyoheiHagimoto 0:56c5742b9e2b 7 #include <math.h>
RyoheiHagimoto 0:56c5742b9e2b 8 #include <string.h>
RyoheiHagimoto 0:56c5742b9e2b 9 #include "util.h"
RyoheiHagimoto 0:56c5742b9e2b 10 #include "image.h"
RyoheiHagimoto 0:56c5742b9e2b 11 #include "binarize.h"
RyoheiHagimoto 0:56c5742b9e2b 12
RyoheiHagimoto 0:56c5742b9e2b 13 #if 0
RyoheiHagimoto 0:56c5742b9e2b 14 /*Binarization based on~\cite{GPP06}.
RyoheiHagimoto 0:56c5742b9e2b 15 @ARTICLE{GPP06,
RyoheiHagimoto 0:56c5742b9e2b 16 author="Basilios Gatos and Ioannis E. Pratikakis and Stavros J. Perantonis",
RyoheiHagimoto 0:56c5742b9e2b 17 title="Adaptive Degraded Document Image Binarization",
RyoheiHagimoto 0:56c5742b9e2b 18 journal="Pattern Recognition",
RyoheiHagimoto 0:56c5742b9e2b 19 volume=39,
RyoheiHagimoto 0:56c5742b9e2b 20 number=3,
RyoheiHagimoto 0:56c5742b9e2b 21 pages="317-327",
RyoheiHagimoto 0:56c5742b9e2b 22 month=Mar,
RyoheiHagimoto 0:56c5742b9e2b 23 year=2006
RyoheiHagimoto 0:56c5742b9e2b 24 }*/
RyoheiHagimoto 0:56c5742b9e2b 25
RyoheiHagimoto 0:56c5742b9e2b 26 #if 0
RyoheiHagimoto 0:56c5742b9e2b 27 /*Applies a 5x5 Wiener filter to the image, in-place, emphasizing differences
RyoheiHagimoto 0:56c5742b9e2b 28 where the local variance is small, and de-emphasizing them where it is
RyoheiHagimoto 0:56c5742b9e2b 29 large.*/
RyoheiHagimoto 0:56c5742b9e2b 30 void qr_wiener_filter(unsigned char *_img,int _width,int _height){
RyoheiHagimoto 0:56c5742b9e2b 31 unsigned *m_buf[8];
RyoheiHagimoto 0:56c5742b9e2b 32 unsigned *sn2_buf[8];
RyoheiHagimoto 0:56c5742b9e2b 33 unsigned char g;
RyoheiHagimoto 0:56c5742b9e2b 34 int x;
RyoheiHagimoto 0:56c5742b9e2b 35 int y;
RyoheiHagimoto 0:56c5742b9e2b 36 if(_width<=0||_height<=0)return;
RyoheiHagimoto 0:56c5742b9e2b 37 m_buf[0]=(unsigned *)malloc((_width+4<<3)*sizeof(*m_buf));
RyoheiHagimoto 0:56c5742b9e2b 38 sn2_buf[0]=(unsigned *)malloc((_width+4<<3)*sizeof(*sn2_buf));
RyoheiHagimoto 0:56c5742b9e2b 39 for(y=1;y<8;y++){
RyoheiHagimoto 0:56c5742b9e2b 40 m_buf[y]=m_buf[y-1]+_width+4;
RyoheiHagimoto 0:56c5742b9e2b 41 sn2_buf[y]=sn2_buf[y-1]+_width+4;
RyoheiHagimoto 0:56c5742b9e2b 42 }
RyoheiHagimoto 0:56c5742b9e2b 43 for(y=-4;y<_height;y++){
RyoheiHagimoto 0:56c5742b9e2b 44 unsigned *pm;
RyoheiHagimoto 0:56c5742b9e2b 45 unsigned *psn2;
RyoheiHagimoto 0:56c5742b9e2b 46 int i;
RyoheiHagimoto 0:56c5742b9e2b 47 int j;
RyoheiHagimoto 0:56c5742b9e2b 48 pm=m_buf[y+2&7];
RyoheiHagimoto 0:56c5742b9e2b 49 psn2=sn2_buf[y+2&7];
RyoheiHagimoto 0:56c5742b9e2b 50 for(x=-4;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 51 unsigned m;
RyoheiHagimoto 0:56c5742b9e2b 52 unsigned m2;
RyoheiHagimoto 0:56c5742b9e2b 53 m=m2=0;
RyoheiHagimoto 0:56c5742b9e2b 54 if(y>=0&&y<_height-4&&x>=0&&x<_width-4)for(i=0;i<5;i++)for(j=0;j<5;j++){
RyoheiHagimoto 0:56c5742b9e2b 55 g=_img[(y+i)*_width+x+j];
RyoheiHagimoto 0:56c5742b9e2b 56 m+=g;
RyoheiHagimoto 0:56c5742b9e2b 57 m2+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 58 }
RyoheiHagimoto 0:56c5742b9e2b 59 else for(i=0;i<5;i++)for(j=0;j<5;j++){
RyoheiHagimoto 0:56c5742b9e2b 60 g=_img[QR_CLAMPI(0,y+i,_height-1)*_width+QR_CLAMPI(0,x+j,_width-1)];
RyoheiHagimoto 0:56c5742b9e2b 61 m+=g;
RyoheiHagimoto 0:56c5742b9e2b 62 m2+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 63 }
RyoheiHagimoto 0:56c5742b9e2b 64 pm[x+4]=m;
RyoheiHagimoto 0:56c5742b9e2b 65 psn2[x+4]=(m2*25-m*m);
RyoheiHagimoto 0:56c5742b9e2b 66 }
RyoheiHagimoto 0:56c5742b9e2b 67 pm=m_buf[y&7];
RyoheiHagimoto 0:56c5742b9e2b 68 if(y>=0)for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 69 int sn2;
RyoheiHagimoto 0:56c5742b9e2b 70 sn2=sn2_buf[y&7][x+2];
RyoheiHagimoto 0:56c5742b9e2b 71 if(sn2){
RyoheiHagimoto 0:56c5742b9e2b 72 int vn3;
RyoheiHagimoto 0:56c5742b9e2b 73 int m;
RyoheiHagimoto 0:56c5742b9e2b 74 /*Gatos et al. give the expression
RyoheiHagimoto 0:56c5742b9e2b 75 mu+(s2-v2)*(g-mu)/s2 ,
RyoheiHagimoto 0:56c5742b9e2b 76 which we reduce to
RyoheiHagimoto 0:56c5742b9e2b 77 mu+(s2-v2)*g/s2-(s2-v2)*mu/s2 ,
RyoheiHagimoto 0:56c5742b9e2b 78 g-(v2/s2)*g+(v2/s2)*mu ,
RyoheiHagimoto 0:56c5742b9e2b 79 g+(mu-g)*(v2/s2) .
RyoheiHagimoto 0:56c5742b9e2b 80 However, s2 is much noisier than v2, and dividing by it often gives
RyoheiHagimoto 0:56c5742b9e2b 81 extremely large adjustments, causing speckle near edges.
RyoheiHagimoto 0:56c5742b9e2b 82 Therefore we limit the ratio (v2/s2) to lie between 0 and 1.*/
RyoheiHagimoto 0:56c5742b9e2b 83 vn3=0;
RyoheiHagimoto 0:56c5742b9e2b 84 for(i=-2;i<3;i++){
RyoheiHagimoto 0:56c5742b9e2b 85 psn2=sn2_buf[y+i&7];
RyoheiHagimoto 0:56c5742b9e2b 86 for(j=0;j<5;j++)vn3+=psn2[x+j];
RyoheiHagimoto 0:56c5742b9e2b 87 }
RyoheiHagimoto 0:56c5742b9e2b 88 m=m_buf[y&7][x+2];
RyoheiHagimoto 0:56c5742b9e2b 89 vn3=vn3+1023>>10;
RyoheiHagimoto 0:56c5742b9e2b 90 sn2=25*sn2+1023>>10;
RyoheiHagimoto 0:56c5742b9e2b 91 if(vn3<sn2){
RyoheiHagimoto 0:56c5742b9e2b 92 int a;
RyoheiHagimoto 0:56c5742b9e2b 93 g=_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 94 a=(m-25*g)*vn3;
RyoheiHagimoto 0:56c5742b9e2b 95 sn2*=25;
RyoheiHagimoto 0:56c5742b9e2b 96 _img[y*_width+x]=QR_CLAMP255(g+QR_DIVROUND(a,sn2));
RyoheiHagimoto 0:56c5742b9e2b 97 }
RyoheiHagimoto 0:56c5742b9e2b 98 else _img[y*_width+x]=(unsigned char)(((m<<1)+25)/50);
RyoheiHagimoto 0:56c5742b9e2b 99 }
RyoheiHagimoto 0:56c5742b9e2b 100 }
RyoheiHagimoto 0:56c5742b9e2b 101 }
RyoheiHagimoto 0:56c5742b9e2b 102 free(sn2_buf[0]);
RyoheiHagimoto 0:56c5742b9e2b 103 free(m_buf[0]);
RyoheiHagimoto 0:56c5742b9e2b 104 }
RyoheiHagimoto 0:56c5742b9e2b 105
RyoheiHagimoto 0:56c5742b9e2b 106 #else
RyoheiHagimoto 0:56c5742b9e2b 107 /*Applies a 3x3 Wiener filter to the image, in-place, emphasizing differences
RyoheiHagimoto 0:56c5742b9e2b 108 where the local variance is small, and de-emphasizing them where it is
RyoheiHagimoto 0:56c5742b9e2b 109 large.*/
RyoheiHagimoto 0:56c5742b9e2b 110 void qr_wiener_filter(unsigned char *_img,int _width,int _height){
RyoheiHagimoto 0:56c5742b9e2b 111 unsigned *m_buf[4];
RyoheiHagimoto 0:56c5742b9e2b 112 unsigned *sn2_buf[4];
RyoheiHagimoto 0:56c5742b9e2b 113 unsigned char g;
RyoheiHagimoto 0:56c5742b9e2b 114 int x;
RyoheiHagimoto 0:56c5742b9e2b 115 int y;
RyoheiHagimoto 0:56c5742b9e2b 116 if(_width<=0||_height<=0)return;
RyoheiHagimoto 0:56c5742b9e2b 117 m_buf[0]=(unsigned *)malloc((_width+2<<2)*sizeof(*m_buf));
RyoheiHagimoto 0:56c5742b9e2b 118 sn2_buf[0]=(unsigned *)malloc((_width+2<<2)*sizeof(*sn2_buf));
RyoheiHagimoto 0:56c5742b9e2b 119 for(y=1;y<4;y++){
RyoheiHagimoto 0:56c5742b9e2b 120 m_buf[y]=m_buf[y-1]+_width+2;
RyoheiHagimoto 0:56c5742b9e2b 121 sn2_buf[y]=sn2_buf[y-1]+_width+2;
RyoheiHagimoto 0:56c5742b9e2b 122 }
RyoheiHagimoto 0:56c5742b9e2b 123 for(y=-2;y<_height;y++){
RyoheiHagimoto 0:56c5742b9e2b 124 unsigned *pm;
RyoheiHagimoto 0:56c5742b9e2b 125 unsigned *psn2;
RyoheiHagimoto 0:56c5742b9e2b 126 int i;
RyoheiHagimoto 0:56c5742b9e2b 127 int j;
RyoheiHagimoto 0:56c5742b9e2b 128 pm=m_buf[y+1&3];
RyoheiHagimoto 0:56c5742b9e2b 129 psn2=sn2_buf[y+1&3];
RyoheiHagimoto 0:56c5742b9e2b 130 for(x=-2;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 131 unsigned m;
RyoheiHagimoto 0:56c5742b9e2b 132 unsigned m2;
RyoheiHagimoto 0:56c5742b9e2b 133 m=m2=0;
RyoheiHagimoto 0:56c5742b9e2b 134 if(y>=0&&y<_height-2&&x>=0&&x<_width-2)for(i=0;i<3;i++)for(j=0;j<3;j++){
RyoheiHagimoto 0:56c5742b9e2b 135 g=_img[(y+i)*_width+x+j];
RyoheiHagimoto 0:56c5742b9e2b 136 m+=g;
RyoheiHagimoto 0:56c5742b9e2b 137 m2+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 138 }
RyoheiHagimoto 0:56c5742b9e2b 139 else for(i=0;i<3;i++)for(j=0;j<3;j++){
RyoheiHagimoto 0:56c5742b9e2b 140 g=_img[QR_CLAMPI(0,y+i,_height-1)*_width+QR_CLAMPI(0,x+j,_width-1)];
RyoheiHagimoto 0:56c5742b9e2b 141 m+=g;
RyoheiHagimoto 0:56c5742b9e2b 142 m2+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 143 }
RyoheiHagimoto 0:56c5742b9e2b 144 pm[x+2]=m;
RyoheiHagimoto 0:56c5742b9e2b 145 psn2[x+2]=(m2*9-m*m);
RyoheiHagimoto 0:56c5742b9e2b 146 }
RyoheiHagimoto 0:56c5742b9e2b 147 pm=m_buf[y&3];
RyoheiHagimoto 0:56c5742b9e2b 148 if(y>=0)for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 149 int sn2;
RyoheiHagimoto 0:56c5742b9e2b 150 sn2=sn2_buf[y&3][x+1];
RyoheiHagimoto 0:56c5742b9e2b 151 if(sn2){
RyoheiHagimoto 0:56c5742b9e2b 152 int m;
RyoheiHagimoto 0:56c5742b9e2b 153 int vn3;
RyoheiHagimoto 0:56c5742b9e2b 154 /*Gatos et al. give the expression
RyoheiHagimoto 0:56c5742b9e2b 155 mu+(s2-v2)*(g-mu)/s2 ,
RyoheiHagimoto 0:56c5742b9e2b 156 which we reduce to
RyoheiHagimoto 0:56c5742b9e2b 157 mu+(s2-v2)*g/s2-(s2-v2)*mu/s2 ,
RyoheiHagimoto 0:56c5742b9e2b 158 g-(v2/s2)*g+(v2/s2)*mu ,
RyoheiHagimoto 0:56c5742b9e2b 159 g+(mu-g)*(v2/s2) .
RyoheiHagimoto 0:56c5742b9e2b 160 However, s2 is much noisier than v2, and dividing by it often gives
RyoheiHagimoto 0:56c5742b9e2b 161 extremely large adjustments, causing speckle near edges.
RyoheiHagimoto 0:56c5742b9e2b 162 Therefore we limit the ratio (v2/s2) to lie between 0 and 1.*/
RyoheiHagimoto 0:56c5742b9e2b 163 vn3=0;
RyoheiHagimoto 0:56c5742b9e2b 164 for(i=-1;i<2;i++){
RyoheiHagimoto 0:56c5742b9e2b 165 psn2=sn2_buf[y+i&3];
RyoheiHagimoto 0:56c5742b9e2b 166 for(j=0;j<3;j++)vn3+=psn2[x+j];
RyoheiHagimoto 0:56c5742b9e2b 167 }
RyoheiHagimoto 0:56c5742b9e2b 168 m=m_buf[y&3][x+1];
RyoheiHagimoto 0:56c5742b9e2b 169 vn3=vn3+31>>5;
RyoheiHagimoto 0:56c5742b9e2b 170 sn2=9*sn2+31>>5;
RyoheiHagimoto 0:56c5742b9e2b 171 if(vn3<sn2){
RyoheiHagimoto 0:56c5742b9e2b 172 int a;
RyoheiHagimoto 0:56c5742b9e2b 173 g=_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 174 a=m-9*g;
RyoheiHagimoto 0:56c5742b9e2b 175 sn2*=9;
RyoheiHagimoto 0:56c5742b9e2b 176 _img[y*_width+x]=QR_CLAMP255(g+QR_DIVROUND(a,sn2));
RyoheiHagimoto 0:56c5742b9e2b 177 }
RyoheiHagimoto 0:56c5742b9e2b 178 else _img[y*_width+x]=(unsigned char)(((m<<1)+9)/18);
RyoheiHagimoto 0:56c5742b9e2b 179 }
RyoheiHagimoto 0:56c5742b9e2b 180 }
RyoheiHagimoto 0:56c5742b9e2b 181 }
RyoheiHagimoto 0:56c5742b9e2b 182 free(sn2_buf[0]);
RyoheiHagimoto 0:56c5742b9e2b 183 free(m_buf[0]);
RyoheiHagimoto 0:56c5742b9e2b 184 }
RyoheiHagimoto 0:56c5742b9e2b 185 #endif
RyoheiHagimoto 0:56c5742b9e2b 186
RyoheiHagimoto 0:56c5742b9e2b 187 /*Computes a (conservative) foreground mask using the adaptive binarization
RyoheiHagimoto 0:56c5742b9e2b 188 threshold given in~\cite{SP00}, but knocking the threshold parameter down to
RyoheiHagimoto 0:56c5742b9e2b 189 k=0.2.
RyoheiHagimoto 0:56c5742b9e2b 190 Note on dynamic range: we assume _width*_height<=0x1000000 (24 bits).
RyoheiHagimoto 0:56c5742b9e2b 191 Returns the average background value.
RyoheiHagimoto 0:56c5742b9e2b 192 @ARTICLE{SP00,
RyoheiHagimoto 0:56c5742b9e2b 193 author="Jaakko J. Sauvola and Matti Pietik\"{a}inen",
RyoheiHagimoto 0:56c5742b9e2b 194 title="Adaptive Document Image Binarization",
RyoheiHagimoto 0:56c5742b9e2b 195 volume=33,
RyoheiHagimoto 0:56c5742b9e2b 196 number=2,
RyoheiHagimoto 0:56c5742b9e2b 197 pages="225--236",
RyoheiHagimoto 0:56c5742b9e2b 198 month=Feb,
RyoheiHagimoto 0:56c5742b9e2b 199 year=2000
RyoheiHagimoto 0:56c5742b9e2b 200 }*/
RyoheiHagimoto 0:56c5742b9e2b 201 static void qr_sauvola_mask(unsigned char *_mask,unsigned *_b,int *_nb,
RyoheiHagimoto 0:56c5742b9e2b 202 const unsigned char *_img,int _width,int _height){
RyoheiHagimoto 0:56c5742b9e2b 203 unsigned b;
RyoheiHagimoto 0:56c5742b9e2b 204 int nb;
RyoheiHagimoto 0:56c5742b9e2b 205 b=0;
RyoheiHagimoto 0:56c5742b9e2b 206 nb=0;
RyoheiHagimoto 0:56c5742b9e2b 207 if(_width>0&&_height>0){
RyoheiHagimoto 0:56c5742b9e2b 208 unsigned *col_sums;
RyoheiHagimoto 0:56c5742b9e2b 209 unsigned *col2_sums;
RyoheiHagimoto 0:56c5742b9e2b 210 int logwindw;
RyoheiHagimoto 0:56c5742b9e2b 211 int logwindh;
RyoheiHagimoto 0:56c5742b9e2b 212 int windw;
RyoheiHagimoto 0:56c5742b9e2b 213 int windh;
RyoheiHagimoto 0:56c5742b9e2b 214 int y0offs;
RyoheiHagimoto 0:56c5742b9e2b 215 int y1offs;
RyoheiHagimoto 0:56c5742b9e2b 216 unsigned g;
RyoheiHagimoto 0:56c5742b9e2b 217 unsigned g2;
RyoheiHagimoto 0:56c5742b9e2b 218 int x;
RyoheiHagimoto 0:56c5742b9e2b 219 int y;
RyoheiHagimoto 0:56c5742b9e2b 220 /*We keep the window size fairly large to ensure it doesn't fit completely
RyoheiHagimoto 0:56c5742b9e2b 221 inside the center of a finder pattern of a version 1 QR code at full
RyoheiHagimoto 0:56c5742b9e2b 222 resolution.*/
RyoheiHagimoto 0:56c5742b9e2b 223 for(logwindw=4;logwindw<8&&(1<<logwindw)<(_width+7>>3);logwindw++);
RyoheiHagimoto 0:56c5742b9e2b 224 for(logwindh=4;logwindh<8&&(1<<logwindh)<(_height+7>>3);logwindh++);
RyoheiHagimoto 0:56c5742b9e2b 225 windw=1<<logwindw;
RyoheiHagimoto 0:56c5742b9e2b 226 windh=1<<logwindh;
RyoheiHagimoto 0:56c5742b9e2b 227 col_sums=(unsigned *)malloc(_width*sizeof(*col_sums));
RyoheiHagimoto 0:56c5742b9e2b 228 col2_sums=(unsigned *)malloc(_width*sizeof(*col2_sums));
RyoheiHagimoto 0:56c5742b9e2b 229 /*Initialize sums down each column.*/
RyoheiHagimoto 0:56c5742b9e2b 230 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 231 g=_img[x];
RyoheiHagimoto 0:56c5742b9e2b 232 g2=g*g;
RyoheiHagimoto 0:56c5742b9e2b 233 col_sums[x]=(g<<logwindh-1)+g;
RyoheiHagimoto 0:56c5742b9e2b 234 col2_sums[x]=(g2<<logwindh-1)+g2;
RyoheiHagimoto 0:56c5742b9e2b 235 }
RyoheiHagimoto 0:56c5742b9e2b 236 for(y=1;y<(windh>>1);y++){
RyoheiHagimoto 0:56c5742b9e2b 237 y1offs=QR_MINI(y,_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 238 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 239 g=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 240 col_sums[x]+=g;
RyoheiHagimoto 0:56c5742b9e2b 241 col2_sums[x]+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 242 }
RyoheiHagimoto 0:56c5742b9e2b 243 }
RyoheiHagimoto 0:56c5742b9e2b 244 for(y=0;y<_height;y++){
RyoheiHagimoto 0:56c5742b9e2b 245 unsigned m;
RyoheiHagimoto 0:56c5742b9e2b 246 unsigned m2;
RyoheiHagimoto 0:56c5742b9e2b 247 int x0;
RyoheiHagimoto 0:56c5742b9e2b 248 int x1;
RyoheiHagimoto 0:56c5742b9e2b 249 /*Initialize the sums over the window.*/
RyoheiHagimoto 0:56c5742b9e2b 250 m=(col_sums[0]<<logwindw-1)+col_sums[0];
RyoheiHagimoto 0:56c5742b9e2b 251 m2=(col2_sums[0]<<logwindw-1)+col2_sums[0];
RyoheiHagimoto 0:56c5742b9e2b 252 for(x=1;x<(windw>>1);x++){
RyoheiHagimoto 0:56c5742b9e2b 253 x1=QR_MINI(x,_width-1);
RyoheiHagimoto 0:56c5742b9e2b 254 m+=col_sums[x1];
RyoheiHagimoto 0:56c5742b9e2b 255 m2+=col2_sums[x1];
RyoheiHagimoto 0:56c5742b9e2b 256 }
RyoheiHagimoto 0:56c5742b9e2b 257 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 258 int d;
RyoheiHagimoto 0:56c5742b9e2b 259 /*Perform the test against the threshold T = (m/n)*(1+k*(s/R-1)),
RyoheiHagimoto 0:56c5742b9e2b 260 where n=windw*windh, s=sqrt((m2-(m*m)/n)/n), and R=128.
RyoheiHagimoto 0:56c5742b9e2b 261 We don't actually compute the threshold directly, as that would
RyoheiHagimoto 0:56c5742b9e2b 262 require a square root.
RyoheiHagimoto 0:56c5742b9e2b 263 Instead we perform the equivalent test:
RyoheiHagimoto 0:56c5742b9e2b 264 (m/n)*(m/n)*(m2/n-(m/n)*(m/n))/16 > (((1/k)*g-((1-k)/k)*(m/n))*32)**2
RyoheiHagimoto 0:56c5742b9e2b 265 R is split up across each side of the inequality to maximize the
RyoheiHagimoto 0:56c5742b9e2b 266 dynamic range available for the right hand side, which requires
RyoheiHagimoto 0:56c5742b9e2b 267 31 bits in the worst case.*/
RyoheiHagimoto 0:56c5742b9e2b 268 /*(m/n)*(1+(1/5)*(sqrt((m2-m*m/n)/n)/128-1)) > g
RyoheiHagimoto 0:56c5742b9e2b 269 m*(1+(1/5)*(sqrt((m2-m*m/n)/n)/128-1)) > g*n
RyoheiHagimoto 0:56c5742b9e2b 270 m*sqrt((m2-m*m/n)/n) > 5*g*n-4*m<<7
RyoheiHagimoto 0:56c5742b9e2b 271 m*m*(m2*n-m*m) > (5*g*n-4*m<<7)**2*n*n || 5*g*n-4*m < 0 */
RyoheiHagimoto 0:56c5742b9e2b 272 g=_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 273 d=(5*g<<logwindw+logwindh)-4*m;
RyoheiHagimoto 0:56c5742b9e2b 274 if(d>=0){
RyoheiHagimoto 0:56c5742b9e2b 275 unsigned mm;
RyoheiHagimoto 0:56c5742b9e2b 276 unsigned mms2;
RyoheiHagimoto 0:56c5742b9e2b 277 unsigned d2;
RyoheiHagimoto 0:56c5742b9e2b 278 mm=(m>>logwindw)*(m>>logwindh);
RyoheiHagimoto 0:56c5742b9e2b 279 mms2=(m2-mm>>logwindw+logwindh)*(mm>>logwindw+logwindh)+15>>4;
RyoheiHagimoto 0:56c5742b9e2b 280 d2=d>>logwindw+logwindh-5;
RyoheiHagimoto 0:56c5742b9e2b 281 d2*=d2;
RyoheiHagimoto 0:56c5742b9e2b 282 if(d2>=mms2){
RyoheiHagimoto 0:56c5742b9e2b 283 /*Update the background average.*/
RyoheiHagimoto 0:56c5742b9e2b 284 b+=g;
RyoheiHagimoto 0:56c5742b9e2b 285 nb++;
RyoheiHagimoto 0:56c5742b9e2b 286 _mask[y*_width+x]=0;
RyoheiHagimoto 0:56c5742b9e2b 287 }
RyoheiHagimoto 0:56c5742b9e2b 288 else _mask[y*_width+x]=0xFF;
RyoheiHagimoto 0:56c5742b9e2b 289 }
RyoheiHagimoto 0:56c5742b9e2b 290 else _mask[y*_width+x]=0xFF;
RyoheiHagimoto 0:56c5742b9e2b 291 /*Update the window sums.*/
RyoheiHagimoto 0:56c5742b9e2b 292 if(x+1<_width){
RyoheiHagimoto 0:56c5742b9e2b 293 x0=QR_MAXI(0,x-(windw>>1));
RyoheiHagimoto 0:56c5742b9e2b 294 x1=QR_MINI(x+(windw>>1),_width-1);
RyoheiHagimoto 0:56c5742b9e2b 295 m+=col_sums[x1]-col_sums[x0];
RyoheiHagimoto 0:56c5742b9e2b 296 m2+=col2_sums[x1]-col2_sums[x0];
RyoheiHagimoto 0:56c5742b9e2b 297 }
RyoheiHagimoto 0:56c5742b9e2b 298 }
RyoheiHagimoto 0:56c5742b9e2b 299 /*Update the column sums.*/
RyoheiHagimoto 0:56c5742b9e2b 300 if(y+1<_height){
RyoheiHagimoto 0:56c5742b9e2b 301 y0offs=QR_MAXI(0,y-(windh>>1))*_width;
RyoheiHagimoto 0:56c5742b9e2b 302 y1offs=QR_MINI(y+(windh>>1),_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 303 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 304 g=_img[y0offs+x];
RyoheiHagimoto 0:56c5742b9e2b 305 col_sums[x]-=g;
RyoheiHagimoto 0:56c5742b9e2b 306 col2_sums[x]-=g*g;
RyoheiHagimoto 0:56c5742b9e2b 307 g=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 308 col_sums[x]+=g;
RyoheiHagimoto 0:56c5742b9e2b 309 col2_sums[x]+=g*g;
RyoheiHagimoto 0:56c5742b9e2b 310 }
RyoheiHagimoto 0:56c5742b9e2b 311 }
RyoheiHagimoto 0:56c5742b9e2b 312 }
RyoheiHagimoto 0:56c5742b9e2b 313 free(col2_sums);
RyoheiHagimoto 0:56c5742b9e2b 314 free(col_sums);
RyoheiHagimoto 0:56c5742b9e2b 315 }
RyoheiHagimoto 0:56c5742b9e2b 316 *_b=b;
RyoheiHagimoto 0:56c5742b9e2b 317 *_nb=nb;
RyoheiHagimoto 0:56c5742b9e2b 318 }
RyoheiHagimoto 0:56c5742b9e2b 319
RyoheiHagimoto 0:56c5742b9e2b 320 /*Interpolates a background image given the source and a conservative
RyoheiHagimoto 0:56c5742b9e2b 321 foreground mask.
RyoheiHagimoto 0:56c5742b9e2b 322 If the current window contains no foreground pixels, the average background
RyoheiHagimoto 0:56c5742b9e2b 323 value over the whole image is used.
RyoheiHagimoto 0:56c5742b9e2b 324 Note on dynamic range: we assume _width*_height<=0x8000000 (23 bits).
RyoheiHagimoto 0:56c5742b9e2b 325 Returns the average difference between the foreground and the interpolated
RyoheiHagimoto 0:56c5742b9e2b 326 background.*/
RyoheiHagimoto 0:56c5742b9e2b 327 static void qr_interpolate_background(unsigned char *_dst,
RyoheiHagimoto 0:56c5742b9e2b 328 int *_delta,int *_ndelta,const unsigned char *_img,const unsigned char *_mask,
RyoheiHagimoto 0:56c5742b9e2b 329 int _width,int _height,unsigned _b,int _nb){
RyoheiHagimoto 0:56c5742b9e2b 330 int delta;
RyoheiHagimoto 0:56c5742b9e2b 331 int ndelta;
RyoheiHagimoto 0:56c5742b9e2b 332 delta=ndelta=0;
RyoheiHagimoto 0:56c5742b9e2b 333 if(_width>0&&_height>0){
RyoheiHagimoto 0:56c5742b9e2b 334 unsigned *col_sums;
RyoheiHagimoto 0:56c5742b9e2b 335 unsigned *ncol_sums;
RyoheiHagimoto 0:56c5742b9e2b 336 int logwindw;
RyoheiHagimoto 0:56c5742b9e2b 337 int logwindh;
RyoheiHagimoto 0:56c5742b9e2b 338 int windw;
RyoheiHagimoto 0:56c5742b9e2b 339 int windh;
RyoheiHagimoto 0:56c5742b9e2b 340 int y0offs;
RyoheiHagimoto 0:56c5742b9e2b 341 int y1offs;
RyoheiHagimoto 0:56c5742b9e2b 342 unsigned b;
RyoheiHagimoto 0:56c5742b9e2b 343 unsigned g;
RyoheiHagimoto 0:56c5742b9e2b 344 int x;
RyoheiHagimoto 0:56c5742b9e2b 345 int y;
RyoheiHagimoto 0:56c5742b9e2b 346 b=_nb>0?((_b<<1)+_nb)/(_nb<<1):0xFF;
RyoheiHagimoto 0:56c5742b9e2b 347 for(logwindw=4;logwindw<8&&(1<<logwindw)<(_width+15>>4);logwindw++);
RyoheiHagimoto 0:56c5742b9e2b 348 for(logwindh=4;logwindh<8&&(1<<logwindh)<(_height+15>>4);logwindh++);
RyoheiHagimoto 0:56c5742b9e2b 349 windw=1<<logwindw;
RyoheiHagimoto 0:56c5742b9e2b 350 windh=1<<logwindh;
RyoheiHagimoto 0:56c5742b9e2b 351 col_sums=(unsigned *)malloc(_width*sizeof(*col_sums));
RyoheiHagimoto 0:56c5742b9e2b 352 ncol_sums=(unsigned *)malloc(_width*sizeof(*ncol_sums));
RyoheiHagimoto 0:56c5742b9e2b 353 /*Initialize sums down each column.*/
RyoheiHagimoto 0:56c5742b9e2b 354 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 355 if(!_mask[x]){
RyoheiHagimoto 0:56c5742b9e2b 356 g=_img[x];
RyoheiHagimoto 0:56c5742b9e2b 357 col_sums[x]=(g<<logwindh-1)+g;
RyoheiHagimoto 0:56c5742b9e2b 358 ncol_sums[x]=(1<<logwindh-1)+1;
RyoheiHagimoto 0:56c5742b9e2b 359 }
RyoheiHagimoto 0:56c5742b9e2b 360 else col_sums[x]=ncol_sums[x]=0;
RyoheiHagimoto 0:56c5742b9e2b 361 }
RyoheiHagimoto 0:56c5742b9e2b 362 for(y=1;y<(windh>>1);y++){
RyoheiHagimoto 0:56c5742b9e2b 363 y1offs=QR_MINI(y,_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 364 for(x=0;x<_width;x++)if(!_mask[y1offs+x]){
RyoheiHagimoto 0:56c5742b9e2b 365 col_sums[x]+=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 366 ncol_sums[x]++;
RyoheiHagimoto 0:56c5742b9e2b 367 }
RyoheiHagimoto 0:56c5742b9e2b 368 }
RyoheiHagimoto 0:56c5742b9e2b 369 for(y=0;y<_height;y++){
RyoheiHagimoto 0:56c5742b9e2b 370 unsigned n;
RyoheiHagimoto 0:56c5742b9e2b 371 unsigned m;
RyoheiHagimoto 0:56c5742b9e2b 372 int x0;
RyoheiHagimoto 0:56c5742b9e2b 373 int x1;
RyoheiHagimoto 0:56c5742b9e2b 374 /*Initialize the sums over the window.*/
RyoheiHagimoto 0:56c5742b9e2b 375 m=(col_sums[0]<<logwindw-1)+col_sums[0];
RyoheiHagimoto 0:56c5742b9e2b 376 n=(ncol_sums[0]<<logwindw-1)+ncol_sums[0];
RyoheiHagimoto 0:56c5742b9e2b 377 for(x=1;x<(windw>>1);x++){
RyoheiHagimoto 0:56c5742b9e2b 378 x1=QR_MINI(x,_width-1);
RyoheiHagimoto 0:56c5742b9e2b 379 m+=col_sums[x1];
RyoheiHagimoto 0:56c5742b9e2b 380 n+=ncol_sums[x1];
RyoheiHagimoto 0:56c5742b9e2b 381 }
RyoheiHagimoto 0:56c5742b9e2b 382 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 383 if(!_mask[y*_width+x])g=_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 384 else{
RyoheiHagimoto 0:56c5742b9e2b 385 g=n>0?((m<<1)+n)/(n<<1):b;
RyoheiHagimoto 0:56c5742b9e2b 386 delta+=(int)g-_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 387 ndelta++;
RyoheiHagimoto 0:56c5742b9e2b 388 }
RyoheiHagimoto 0:56c5742b9e2b 389 _dst[y*_width+x]=(unsigned char)g;
RyoheiHagimoto 0:56c5742b9e2b 390 /*Update the window sums.*/
RyoheiHagimoto 0:56c5742b9e2b 391 if(x+1<_width){
RyoheiHagimoto 0:56c5742b9e2b 392 x0=QR_MAXI(0,x-(windw>>1));
RyoheiHagimoto 0:56c5742b9e2b 393 x1=QR_MINI(x+(windw>>1),_width-1);
RyoheiHagimoto 0:56c5742b9e2b 394 m+=col_sums[x1]-col_sums[x0];
RyoheiHagimoto 0:56c5742b9e2b 395 n+=ncol_sums[x1]-ncol_sums[x0];
RyoheiHagimoto 0:56c5742b9e2b 396 }
RyoheiHagimoto 0:56c5742b9e2b 397 }
RyoheiHagimoto 0:56c5742b9e2b 398 /*Update the column sums.*/
RyoheiHagimoto 0:56c5742b9e2b 399 if(y+1<_height){
RyoheiHagimoto 0:56c5742b9e2b 400 y0offs=QR_MAXI(0,y-(windh>>1))*_width;
RyoheiHagimoto 0:56c5742b9e2b 401 y1offs=QR_MINI(y+(windh>>1),_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 402 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 403 if(!_mask[y0offs+x]){
RyoheiHagimoto 0:56c5742b9e2b 404 col_sums[x]-=_img[y0offs+x];
RyoheiHagimoto 0:56c5742b9e2b 405 ncol_sums[x]--;
RyoheiHagimoto 0:56c5742b9e2b 406 }
RyoheiHagimoto 0:56c5742b9e2b 407 if(!_mask[y1offs+x]){
RyoheiHagimoto 0:56c5742b9e2b 408 col_sums[x]+=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 409 ncol_sums[x]++;
RyoheiHagimoto 0:56c5742b9e2b 410 }
RyoheiHagimoto 0:56c5742b9e2b 411 }
RyoheiHagimoto 0:56c5742b9e2b 412 }
RyoheiHagimoto 0:56c5742b9e2b 413 }
RyoheiHagimoto 0:56c5742b9e2b 414 free(ncol_sums);
RyoheiHagimoto 0:56c5742b9e2b 415 free(col_sums);
RyoheiHagimoto 0:56c5742b9e2b 416 }
RyoheiHagimoto 0:56c5742b9e2b 417 *_delta=delta;
RyoheiHagimoto 0:56c5742b9e2b 418 *_ndelta=ndelta;
RyoheiHagimoto 0:56c5742b9e2b 419 }
RyoheiHagimoto 0:56c5742b9e2b 420
RyoheiHagimoto 0:56c5742b9e2b 421 /*Parameters of the logistic sigmoid function that defines the threshold based
RyoheiHagimoto 0:56c5742b9e2b 422 on the background intensity.
RyoheiHagimoto 0:56c5742b9e2b 423 They should all be between 0 and 1.*/
RyoheiHagimoto 0:56c5742b9e2b 424 #define QR_GATOS_Q (0.7)
RyoheiHagimoto 0:56c5742b9e2b 425 #define QR_GATOS_P1 (0.5)
RyoheiHagimoto 0:56c5742b9e2b 426 #define QR_GATOS_P2 (0.8)
RyoheiHagimoto 0:56c5742b9e2b 427
RyoheiHagimoto 0:56c5742b9e2b 428 /*Compute the final binarization mask according to Gatos et al.'s
RyoheiHagimoto 0:56c5742b9e2b 429 method~\cite{GPP06}.*/
RyoheiHagimoto 0:56c5742b9e2b 430 static void qr_gatos_mask(unsigned char *_mask,const unsigned char *_img,
RyoheiHagimoto 0:56c5742b9e2b 431 const unsigned char *_background,int _width,int _height,
RyoheiHagimoto 0:56c5742b9e2b 432 unsigned _b,int _nb,int _delta,int _ndelta){
RyoheiHagimoto 0:56c5742b9e2b 433 unsigned thresh[256];
RyoheiHagimoto 0:56c5742b9e2b 434 unsigned g;
RyoheiHagimoto 0:56c5742b9e2b 435 double delta;
RyoheiHagimoto 0:56c5742b9e2b 436 double b;
RyoheiHagimoto 0:56c5742b9e2b 437 int x;
RyoheiHagimoto 0:56c5742b9e2b 438 int y;
RyoheiHagimoto 0:56c5742b9e2b 439 /*Construct a lookup table for the thresholds.
RyoheiHagimoto 0:56c5742b9e2b 440 This bit uses floating point, but doesn't need to do much calculation, so
RyoheiHagimoto 0:56c5742b9e2b 441 emulation should be fine.*/
RyoheiHagimoto 0:56c5742b9e2b 442 b=_nb>0?(_b+0.5)/_nb:0xFF;
RyoheiHagimoto 0:56c5742b9e2b 443 delta=_ndelta>0?(_delta+0.5)/_ndelta:0xFF;
RyoheiHagimoto 0:56c5742b9e2b 444 for(g=0;g<256;g++){
RyoheiHagimoto 0:56c5742b9e2b 445 double d;
RyoheiHagimoto 0:56c5742b9e2b 446 d=QR_GATOS_Q*delta*(QR_GATOS_P2+(1-QR_GATOS_P2)/
RyoheiHagimoto 0:56c5742b9e2b 447 (1+exp(2*(1+QR_GATOS_P1)/(1-QR_GATOS_P1)-4*g/(b*(1-QR_GATOS_P1)))));
RyoheiHagimoto 0:56c5742b9e2b 448 if(d<1)d=1;
RyoheiHagimoto 0:56c5742b9e2b 449 else if(d>0xFF)d=0xFF;
RyoheiHagimoto 0:56c5742b9e2b 450 thresh[g]=(unsigned)floor(d);
RyoheiHagimoto 0:56c5742b9e2b 451 }
RyoheiHagimoto 0:56c5742b9e2b 452 /*Apply the adaptive threshold.*/
RyoheiHagimoto 0:56c5742b9e2b 453 for(y=0;y<_height;y++)for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 454 g=_background[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 455 /*_background[y*_width+x]=thresh[g];*/
RyoheiHagimoto 0:56c5742b9e2b 456 _mask[y*_width+x]=(unsigned char)(-(g-_img[y*_width+x]>thresh[g])&0xFF);
RyoheiHagimoto 0:56c5742b9e2b 457 }
RyoheiHagimoto 0:56c5742b9e2b 458 /*{
RyoheiHagimoto 0:56c5742b9e2b 459 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 460 fout=fopen("thresh.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 461 image_write_png(_background,_width,_height,fout);
RyoheiHagimoto 0:56c5742b9e2b 462 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 463 }*/
RyoheiHagimoto 0:56c5742b9e2b 464 }
RyoheiHagimoto 0:56c5742b9e2b 465
RyoheiHagimoto 0:56c5742b9e2b 466 /*Binarizes a grayscale image.*/
RyoheiHagimoto 0:56c5742b9e2b 467 void qr_binarize(unsigned char *_img,int _width,int _height){
RyoheiHagimoto 0:56c5742b9e2b 468 unsigned char *mask;
RyoheiHagimoto 0:56c5742b9e2b 469 unsigned char *background;
RyoheiHagimoto 0:56c5742b9e2b 470 unsigned b;
RyoheiHagimoto 0:56c5742b9e2b 471 int nb;
RyoheiHagimoto 0:56c5742b9e2b 472 int delta;
RyoheiHagimoto 0:56c5742b9e2b 473 int ndelta;
RyoheiHagimoto 0:56c5742b9e2b 474 /*qr_wiener_filter(_img,_width,_height);
RyoheiHagimoto 0:56c5742b9e2b 475 {
RyoheiHagimoto 0:56c5742b9e2b 476 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 477 fout=fopen("wiener.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 478 image_write_png(_img,_width,_height,fout);
RyoheiHagimoto 0:56c5742b9e2b 479 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 480 }*/
RyoheiHagimoto 0:56c5742b9e2b 481 mask=(unsigned char *)malloc(_width*_height*sizeof(*mask));
RyoheiHagimoto 0:56c5742b9e2b 482 qr_sauvola_mask(mask,&b,&nb,_img,_width,_height);
RyoheiHagimoto 0:56c5742b9e2b 483 /*{
RyoheiHagimoto 0:56c5742b9e2b 484 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 485 fout=fopen("foreground.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 486 image_write_png(mask,_width,_height,fout);
RyoheiHagimoto 0:56c5742b9e2b 487 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 488 }*/
RyoheiHagimoto 0:56c5742b9e2b 489 background=(unsigned char *)malloc(_width*_height*sizeof(*mask));
RyoheiHagimoto 0:56c5742b9e2b 490 qr_interpolate_background(background,&delta,&ndelta,
RyoheiHagimoto 0:56c5742b9e2b 491 _img,mask,_width,_height,b,nb);
RyoheiHagimoto 0:56c5742b9e2b 492 /*{
RyoheiHagimoto 0:56c5742b9e2b 493 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 494 fout=fopen("background.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 495 image_write_png(background,_width,_height,fout);
RyoheiHagimoto 0:56c5742b9e2b 496 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 497 }*/
RyoheiHagimoto 0:56c5742b9e2b 498 qr_gatos_mask(_img,_img,background,_width,_height,b,nb,delta,ndelta);
RyoheiHagimoto 0:56c5742b9e2b 499 free(background);
RyoheiHagimoto 0:56c5742b9e2b 500 free(mask);
RyoheiHagimoto 0:56c5742b9e2b 501 }
RyoheiHagimoto 0:56c5742b9e2b 502
RyoheiHagimoto 0:56c5742b9e2b 503 #else
RyoheiHagimoto 0:56c5742b9e2b 504 /*The above algorithms are computationally expensive, and do not work as well
RyoheiHagimoto 0:56c5742b9e2b 505 as the simple algorithm below.
RyoheiHagimoto 0:56c5742b9e2b 506 Sauvola by itself does an excellent job of classifying regions outside the
RyoheiHagimoto 0:56c5742b9e2b 507 QR code as background, which greatly reduces the chance of false alarms.
RyoheiHagimoto 0:56c5742b9e2b 508 However, it also tends to over-shrink isolated black dots inside the code,
RyoheiHagimoto 0:56c5742b9e2b 509 making them easy to miss with even slight mis-alignment.
RyoheiHagimoto 0:56c5742b9e2b 510 Since the Gatos method uses Sauvola as input to its background interpolation
RyoheiHagimoto 0:56c5742b9e2b 511 method, it cannot possibly mark any pixels as foreground which Sauvola
RyoheiHagimoto 0:56c5742b9e2b 512 classified as background, and thus suffers from the same problem.
RyoheiHagimoto 0:56c5742b9e2b 513 The following simple adaptive threshold method does not have this problem,
RyoheiHagimoto 0:56c5742b9e2b 514 though it produces essentially random noise outside the QR code region.
RyoheiHagimoto 0:56c5742b9e2b 515 QR codes are structured well enough that this does not seem to lead to any
RyoheiHagimoto 0:56c5742b9e2b 516 actual false alarms in practice, and it allows many more codes to be
RyoheiHagimoto 0:56c5742b9e2b 517 detected and decoded successfully than the Sauvola or Gatos binarization
RyoheiHagimoto 0:56c5742b9e2b 518 methods.*/
RyoheiHagimoto 0:56c5742b9e2b 519
RyoheiHagimoto 0:56c5742b9e2b 520 /*A simplified adaptive thresholder.
RyoheiHagimoto 0:56c5742b9e2b 521 This compares the current pixel value to the mean value of a (large) window
RyoheiHagimoto 0:56c5742b9e2b 522 surrounding it.*/
RyoheiHagimoto 0:56c5742b9e2b 523 unsigned char *qr_binarize(const unsigned char *_img,int _width,int _height){
RyoheiHagimoto 0:56c5742b9e2b 524 unsigned char *mask = NULL;
RyoheiHagimoto 0:56c5742b9e2b 525 if(_width>0&&_height>0){
RyoheiHagimoto 0:56c5742b9e2b 526 unsigned *col_sums;
RyoheiHagimoto 0:56c5742b9e2b 527 int logwindw;
RyoheiHagimoto 0:56c5742b9e2b 528 int logwindh;
RyoheiHagimoto 0:56c5742b9e2b 529 int windw;
RyoheiHagimoto 0:56c5742b9e2b 530 int windh;
RyoheiHagimoto 0:56c5742b9e2b 531 int y0offs;
RyoheiHagimoto 0:56c5742b9e2b 532 int y1offs;
RyoheiHagimoto 0:56c5742b9e2b 533 unsigned g;
RyoheiHagimoto 0:56c5742b9e2b 534 int x;
RyoheiHagimoto 0:56c5742b9e2b 535 int y;
RyoheiHagimoto 0:56c5742b9e2b 536 mask=(unsigned char *)malloc(_width*_height*sizeof(*mask));
RyoheiHagimoto 0:56c5742b9e2b 537 /*We keep the window size fairly large to ensure it doesn't fit completely
RyoheiHagimoto 0:56c5742b9e2b 538 inside the center of a finder pattern of a version 1 QR code at full
RyoheiHagimoto 0:56c5742b9e2b 539 resolution.*/
RyoheiHagimoto 0:56c5742b9e2b 540 for(logwindw=4;logwindw<8&&(1<<logwindw)<(_width+7>>3);logwindw++);
RyoheiHagimoto 0:56c5742b9e2b 541 for(logwindh=4;logwindh<8&&(1<<logwindh)<(_height+7>>3);logwindh++);
RyoheiHagimoto 0:56c5742b9e2b 542 windw=1<<logwindw;
RyoheiHagimoto 0:56c5742b9e2b 543 windh=1<<logwindh;
RyoheiHagimoto 0:56c5742b9e2b 544 col_sums=(unsigned *)malloc(_width*sizeof(*col_sums));
RyoheiHagimoto 0:56c5742b9e2b 545 /*Initialize sums down each column.*/
RyoheiHagimoto 0:56c5742b9e2b 546 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 547 g=_img[x];
RyoheiHagimoto 0:56c5742b9e2b 548 col_sums[x]=(g<<logwindh-1)+g;
RyoheiHagimoto 0:56c5742b9e2b 549 }
RyoheiHagimoto 0:56c5742b9e2b 550 for(y=1;y<(windh>>1);y++){
RyoheiHagimoto 0:56c5742b9e2b 551 y1offs=QR_MINI(y,_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 552 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 553 g=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 554 col_sums[x]+=g;
RyoheiHagimoto 0:56c5742b9e2b 555 }
RyoheiHagimoto 0:56c5742b9e2b 556 }
RyoheiHagimoto 0:56c5742b9e2b 557 for(y=0;y<_height;y++){
RyoheiHagimoto 0:56c5742b9e2b 558 unsigned m;
RyoheiHagimoto 0:56c5742b9e2b 559 int x0;
RyoheiHagimoto 0:56c5742b9e2b 560 int x1;
RyoheiHagimoto 0:56c5742b9e2b 561 /*Initialize the sum over the window.*/
RyoheiHagimoto 0:56c5742b9e2b 562 m=(col_sums[0]<<logwindw-1)+col_sums[0];
RyoheiHagimoto 0:56c5742b9e2b 563 for(x=1;x<(windw>>1);x++){
RyoheiHagimoto 0:56c5742b9e2b 564 x1=QR_MINI(x,_width-1);
RyoheiHagimoto 0:56c5742b9e2b 565 m+=col_sums[x1];
RyoheiHagimoto 0:56c5742b9e2b 566 }
RyoheiHagimoto 0:56c5742b9e2b 567 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 568 /*Perform the test against the threshold T = (m/n)-D,
RyoheiHagimoto 0:56c5742b9e2b 569 where n=windw*windh and D=3.*/
RyoheiHagimoto 0:56c5742b9e2b 570 g=_img[y*_width+x];
RyoheiHagimoto 0:56c5742b9e2b 571 mask[y*_width+x]=-(g+3<<logwindw+logwindh<m)&0xFF;
RyoheiHagimoto 0:56c5742b9e2b 572 /*Update the window sum.*/
RyoheiHagimoto 0:56c5742b9e2b 573 if(x+1<_width){
RyoheiHagimoto 0:56c5742b9e2b 574 x0=QR_MAXI(0,x-(windw>>1));
RyoheiHagimoto 0:56c5742b9e2b 575 x1=QR_MINI(x+(windw>>1),_width-1);
RyoheiHagimoto 0:56c5742b9e2b 576 m+=col_sums[x1]-col_sums[x0];
RyoheiHagimoto 0:56c5742b9e2b 577 }
RyoheiHagimoto 0:56c5742b9e2b 578 }
RyoheiHagimoto 0:56c5742b9e2b 579 /*Update the column sums.*/
RyoheiHagimoto 0:56c5742b9e2b 580 if(y+1<_height){
RyoheiHagimoto 0:56c5742b9e2b 581 y0offs=QR_MAXI(0,y-(windh>>1))*_width;
RyoheiHagimoto 0:56c5742b9e2b 582 y1offs=QR_MINI(y+(windh>>1),_height-1)*_width;
RyoheiHagimoto 0:56c5742b9e2b 583 for(x=0;x<_width;x++){
RyoheiHagimoto 0:56c5742b9e2b 584 col_sums[x]-=_img[y0offs+x];
RyoheiHagimoto 0:56c5742b9e2b 585 col_sums[x]+=_img[y1offs+x];
RyoheiHagimoto 0:56c5742b9e2b 586 }
RyoheiHagimoto 0:56c5742b9e2b 587 }
RyoheiHagimoto 0:56c5742b9e2b 588 }
RyoheiHagimoto 0:56c5742b9e2b 589 free(col_sums);
RyoheiHagimoto 0:56c5742b9e2b 590 }
RyoheiHagimoto 0:56c5742b9e2b 591 #if defined(QR_DEBUG)
RyoheiHagimoto 0:56c5742b9e2b 592 {
RyoheiHagimoto 0:56c5742b9e2b 593 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 594 fout=fopen("binary.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 595 image_write_png(_img,_width,_height,fout);
RyoheiHagimoto 0:56c5742b9e2b 596 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 597 }
RyoheiHagimoto 0:56c5742b9e2b 598 #endif
RyoheiHagimoto 0:56c5742b9e2b 599 return(mask);
RyoheiHagimoto 0:56c5742b9e2b 600 }
RyoheiHagimoto 0:56c5742b9e2b 601 #endif
RyoheiHagimoto 0:56c5742b9e2b 602
RyoheiHagimoto 0:56c5742b9e2b 603 #if defined(TEST_BINARIZE)
RyoheiHagimoto 0:56c5742b9e2b 604 #include <stdio.h>
RyoheiHagimoto 0:56c5742b9e2b 605 #include "image.c"
RyoheiHagimoto 0:56c5742b9e2b 606
RyoheiHagimoto 0:56c5742b9e2b 607 int main(int _argc,char **_argv){
RyoheiHagimoto 0:56c5742b9e2b 608 unsigned char *img;
RyoheiHagimoto 0:56c5742b9e2b 609 int width;
RyoheiHagimoto 0:56c5742b9e2b 610 int height;
RyoheiHagimoto 0:56c5742b9e2b 611 int x;
RyoheiHagimoto 0:56c5742b9e2b 612 int y;
RyoheiHagimoto 0:56c5742b9e2b 613 if(_argc<2){
RyoheiHagimoto 0:56c5742b9e2b 614 fprintf(stderr,"usage: %s <image>.png\n",_argv[0]);
RyoheiHagimoto 0:56c5742b9e2b 615 return EXIT_FAILURE;
RyoheiHagimoto 0:56c5742b9e2b 616 }
RyoheiHagimoto 0:56c5742b9e2b 617 /*width=1182;
RyoheiHagimoto 0:56c5742b9e2b 618 height=1181;
RyoheiHagimoto 0:56c5742b9e2b 619 img=(unsigned char *)malloc(width*height*sizeof(*img));
RyoheiHagimoto 0:56c5742b9e2b 620 for(y=0;y<height;y++)for(x=0;x<width;x++){
RyoheiHagimoto 0:56c5742b9e2b 621 img[y*width+x]=(unsigned char)(-((x&1)^(y&1))&0xFF);
RyoheiHagimoto 0:56c5742b9e2b 622 }*/
RyoheiHagimoto 0:56c5742b9e2b 623 {
RyoheiHagimoto 0:56c5742b9e2b 624 FILE *fin;
RyoheiHagimoto 0:56c5742b9e2b 625 fin=fopen(_argv[1],"rb");
RyoheiHagimoto 0:56c5742b9e2b 626 image_read_png(&img,&width,&height,fin);
RyoheiHagimoto 0:56c5742b9e2b 627 fclose(fin);
RyoheiHagimoto 0:56c5742b9e2b 628 }
RyoheiHagimoto 0:56c5742b9e2b 629 qr_binarize(img,width,height);
RyoheiHagimoto 0:56c5742b9e2b 630 /*{
RyoheiHagimoto 0:56c5742b9e2b 631 FILE *fout;
RyoheiHagimoto 0:56c5742b9e2b 632 fout=fopen("binary.png","wb");
RyoheiHagimoto 0:56c5742b9e2b 633 image_write_png(img,width,height,fout);
RyoheiHagimoto 0:56c5742b9e2b 634 fclose(fout);
RyoheiHagimoto 0:56c5742b9e2b 635 }*/
RyoheiHagimoto 0:56c5742b9e2b 636 free(img);
RyoheiHagimoto 0:56c5742b9e2b 637 return EXIT_SUCCESS;
RyoheiHagimoto 0:56c5742b9e2b 638 }
RyoheiHagimoto 0:56c5742b9e2b 639 #endif
RyoheiHagimoto 0:56c5742b9e2b 640