2 * Core OCR algorithm (first exact bitmap match)
5 * This is part of ypp-sc-tools, a set of third-party tools for assisting
6 * players of Yohoho Puzzle Pirates.
8 * Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
10 * This program is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program. If not, see <http://www.gnu.org/licenses/>.
23 * Yohoho and Puzzle Pirates are probably trademarks of Three Rings and
24 * are used without permission. This program is not endorsed or
25 * sponsored by Three Rings.
32 struct DatabaseNode *then;
35 #define MAXGLYPHCHRS 7
37 typedef struct DatabaseNode {
38 char s[MAXGLYPHCHRS+1]; /* null-terminated; "" means no match here */
44 static const char *context_names[]= {
49 struct OcrCellTypeInfo {
50 /* bitmaps of indices into context_names: */
51 unsigned initial, nextword, midword;
55 const struct OcrCellTypeInfo ocr_celltype_number= {
60 const struct OcrCellTypeInfo ocr_celltype_text= {
61 .initial=2, /* Uppercase */
62 .nextword=3, /* Either */
63 .midword=1, /* Lower only */
69 #define NCONTEXTS (sizeof(context_names)/sizeof(context_names[0]))
73 DatabaseNode contexts[NCONTEXTS];
74 OcrResultGlyph *results;
75 int aresults, nresults;
78 DEBUG_DEFINE_DEBUGF(ocr)
80 #define FGETSLINE (dbfile_getsline(lbuf,sizeof(lbuf),__FILE__,__LINE__))
82 static void cleardb_node(DatabaseNode *n) {
85 for (i=0; i<n->nlinks; i++)
86 cleardb_node(n->links[i].then);
89 static void readdb(OcrReader *rd) {
91 DatabaseNode *current, *additional;
92 char chrs[MAXGLYPHCHRS+1];
98 for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
99 cleardb_node(&rd->contexts[ctxi]);
102 asprintf(&dbfname,"%s/charset-%d.txt",get_vardir(),rd->h);
105 if (!dbfile_open(dbfname))
109 dbassert(!strcmp(lbuf,"# ypp-sc-tools pctb font v1"));
111 dbassert( dbfile_scanf("%d", &h) == 1);
116 if (!lbuf[0] || lbuf[0]=='#') continue;
117 if (!strcmp(lbuf,".")) break;
119 for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
120 if (!strcmp(lbuf,context_names[ctxi]))
122 /* not found, just skip */
123 for (;;) { FGETSLINE; if (!lbuf[0]) break; }
128 int c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c!=EOF);
129 if (c=='\n') { dbassert(nchrs); break; }
130 dbassert(nchrs<MAXGLYPHCHRS);
133 c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c=='x');
134 dbassert( dbfile_scanf("%2x", &cr) == 1);
135 assert(cr>0 && cr<=255);
141 if (nchrs>1 && chrs[nchrs-1]==' ') {
147 current= &rd->contexts[ctxi];
150 if (!lbuf[0]) { dbassert(current != &rd->contexts[ctxi]); break; }
152 cv= strtoul(lbuf,&ep,16); dbassert(!*ep);
153 dbassert(!(cv & ~((1UL << rd->h)-1)));
155 for (j=0; j<current->nlinks; j++)
156 if (current->links[j].col == cv) {
157 current= current->links[j].then;
161 additional= mmalloc(sizeof(*additional));
163 additional->nlinks= additional->alinks= 0;
164 additional->links= 0;
165 if (current->nlinks==current->alinks) {
168 current->links= mrealloc(current->links,
169 sizeof(*current->links) * current->alinks);
171 current->links[current->nlinks].col= cv;
172 current->links[current->nlinks].then= additional;
179 dbassert(!current->s[0]);
180 strcpy(current->s, chrs);
181 current->endsword= endsword;
188 static void cu_pr_ctxmap(FILE *resolver, unsigned ctxmap) {
189 fprintf(resolver,"{");
192 for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
193 if (!(ctxmap & (1u << ctxi))) continue;
194 fprintf(resolver,"%s%s",spc,context_names[ctxi]);
197 fprintf(resolver,"}");
200 static void callout_unknown(OcrReader *rd, int w, Pixcol cols[],
201 int unk_l, int unk_r, unsigned unk_ctxmap) {
203 const OcrResultGlyph *s;
207 FILE *resolver= resolve_start();
209 fatal("OCR failed - unrecognised characters or ligatures.\n"
210 "Character set database needs to be updated or augmented.\n"
211 "See README.charset.\n");
215 "%d %d ",unk_l,unk_r);
216 cu_pr_ctxmap(resolver,unk_ctxmap);
217 for (i=0, s=rd->results; i<rd->nresults; i++, s++) {
218 if (!strcmp(s->s," ")) continue;
219 fprintf(resolver," %d %d ",s->l,s->r);
220 cu_pr_ctxmap(resolver,s->ctxmap);
221 fprintf(resolver," ");
222 for (p=s->s; (c= *p); p++) {
223 if (c=='\\') fprintf(resolver,"\\%c",c);
224 else if (c>=33 && c<=126) fputc(c,resolver);
225 else fprintf(resolver,"\\x%02x",(unsigned char)c);
228 fputc('\n',resolver);
232 "static char *t[] = {\n"
233 "/* columns rows colors chars-per-pixel */\n"
238 for (y=0, pv=1; y<rd->h; y++, pv<<=1) {
241 fputc(cols[x] & pv ? 'o' : ' ', resolver);
242 fputs("\",\n",resolver);
244 fputs("};\n",resolver);
250 static void add_result(OcrReader *rd, const char *s, int l, int r,
252 if (rd->nresults >= rd->aresults) {
253 rd->aresults++; rd->aresults<<=1;
254 rd->results= mrealloc(rd->results, sizeof(*rd->results)*rd->aresults);
256 rd->results[rd->nresults].s= s;
257 rd->results[rd->nresults].l= l;
258 rd->results[rd->nresults].r= r;
259 rd->results[rd->nresults].ctxmap= ctxmap;
264 const char *ocr_celltype_name(OcrCellType ct) { return ct->name; }
266 OcrResultGlyph *ocr(OcrReader *rd, OcrCellType ct, int w, Pixcol cols[]) {
276 debugf("OCR h=%d w=%d",rd->h,w);
277 for (x=0; x<w; x++) debugf(" %"PSPIXCOL(PRIx),cols[x]);
291 if (nspaces == ct->space_spaces) {
292 debugf("OCR x=%x nspaces=%d space\n",x,nspaces);
293 ctxmap= ct->nextword;
298 /* something here, so we need to add the spaces */
299 if (nspaces >= ct->space_spaces)
300 add_result(rd," ",x-nspaces,x+1,0);
306 DatabaseNode *uniquematch= 0;
307 int uniquematch_rx=-1;
309 debugf("OCR lx=%d ctxmap=%x ",lx,ctxmap);
311 for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
312 DatabaseNode *current= &rd->contexts[ctxi];;
313 DatabaseNode *bestmatch= 0;
317 if (!(ctxmap & (1u << ctxi))) continue;
318 debugf(" || %s",context_names[ctxi]);
325 debugf(" cv=%"PSPIXCOL(PRIx),cv);
326 for (i=0; i<current->nlinks; i++)
327 if (current->links[i].col == cv)
334 current= current->links[i].then;
336 debugf(" \"%s\"%s",current->s,current->endsword?"_":"");
347 if (uniquematch && strcmp(bestmatch->s, uniquematch->s)) {
348 debugf( " ambiguous");
352 uniquematch= bestmatch;
353 uniquematch_rx= bestmatch_rx;
359 add_result(rd, uniquematch->s, lx, uniquematch_rx, ctxmap);
361 if (uniquematch->s[0]) ctxmap= ct->midword;
362 else debugf(" (empty)");
363 if (uniquematch->endsword) {
364 nspaces= ct->space_spaces;
366 ctxmap= ct->nextword;
371 debugf(" || UNKNOWN");
372 for (rx=lx; rx<w && cols[rx]; rx++);
373 debugf(" x=%d ctxmap=%x %d..%d\n",x, ctxmap, lx,rx);
375 callout_unknown(rd, w,cols, lx,rx-1, ctxmap);
379 add_result(rd, 0,-1,-1,0);
380 debugf("OCR finished %d glyphs\n",rd->nresults);
385 OcrReader *ocr_init(int h) {
388 rd= mmalloc(sizeof(*rd));
389 memset(rd,0,sizeof(*rd));