1 /*
2 * sanei_magic - Image processing functions for despeckle, deskew, and autocrop
3
4 Copyright (C) 2009 m. allan noah
5
6 This file is part of the SANE package.
7
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the
11 License, or (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <https://www.gnu.org/licenses/>.
20
21 As a special exception, the authors of SANE give permission for
22 additional uses of the libraries contained in this release of SANE.
23
24 The exception is that, if you link a SANE library with other files
25 to produce an executable, this does not by itself cause the
26 resulting executable to be covered by the GNU General Public
27 License. Your use of that executable is in no way restricted on
28 account of linking the SANE library code into it.
29
30 This exception does not, however, invalidate any other reasons why
31 the executable file might be covered by the GNU General Public
32 License.
33
34 If you submit changes to SANE to the maintainers to be included in
35 a subsequent release, you agree by submitting the changes that
36 those changes may be distributed with this exception intact.
37
38 If you write modifications of your own for SANE, it is your choice
39 whether to permit this exception to apply to your modifications.
40 If you do not wish that, delete this exception notice.
41 */
42
43 #include "../include/sane/config.h"
44
45 #include <stdio.h>
46 #include <stdlib.h>
47 #include <string.h>
48 #include <errno.h>
49 #include <math.h>
50
51 #define BACKEND_NAME sanei_magic /* name of this module for debugging */
52
53 #include "../include/sane/sane.h"
54 #include "../include/sane/sanei_debug.h"
55 #include "../include/sane/sanei_magic.h"
56
57 /* prototypes for utility functions defined at bottom of file */
58 int * sanei_magic_getTransY (
59 SANE_Parameters * params, int dpi, SANE_Byte * buffer, int top);
60
61 int * sanei_magic_getTransX (
62 SANE_Parameters * params, int dpi, SANE_Byte * buffer, int left);
63
64 static SANE_Status getTopEdge (int width, int height, int resolution,
65 int * buff, double * finSlope, int * finXInter, int * finYInter);
66
67 static SANE_Status getLeftEdge (int width, int height, int * top, int * bot,
68 double slope, int * finXInter, int * finYInter);
69
70 static SANE_Status getLine (int height, int width, int * buff,
71 int slopes, double minSlope, double maxSlope,
72 int offsets, int minOffset, int maxOffset,
73 double * finSlope, int * finOffset, int * finDensity);
74
75 void
sanei_magic_init(void)76 sanei_magic_init( void )
77 {
78 DBG_INIT();
79 }
80
81 /* find small spots and replace them with image background color */
82 SANE_Status
sanei_magic_despeck(SANE_Parameters * params,SANE_Byte * buffer,SANE_Int diam)83 sanei_magic_despeck (SANE_Parameters * params, SANE_Byte * buffer,
84 SANE_Int diam)
85 {
86
87 SANE_Status ret = SANE_STATUS_GOOD;
88
89 int pw = params->pixels_per_line;
90 int bw = params->bytes_per_line;
91 int h = params->lines;
92 int bt = bw*h;
93
94 int i,j,k,l,n;
95
96 DBG (10, "sanei_magic_despeck: start\n");
97
98 if(params->format == SANE_FRAME_RGB){
99
100 for(i=bw; i<bt-bw-(bw*diam); i+=bw){
101 for(j=1; j<pw-1-diam; j++){
102
103 int thresh = 255*3;
104 int outer[] = {0,0,0};
105 int hits = 0;
106
107 /* loop over rows and columns in window */
108 /* find darkest pixel */
109 for(k=0; k<diam; k++){
110 for(l=0; l<diam; l++){
111 int tmp = 0;
112
113 for(n=0; n<3; n++){
114 tmp += buffer[i + j*3 + k*bw + l*3 + n];
115 }
116
117 if(tmp < thresh)
118 thresh = tmp;
119 }
120 }
121
122 /* convert darkest pixel into a brighter threshold */
123 thresh = (thresh + 255*3 + 255*3)/3;
124
125 /*loop over rows and columns around window */
126 for(k=-1; k<diam+1; k++){
127 for(l=-1; l<diam+1; l++){
128
129 int tmp[3];
130
131 /* don't count pixels in the window */
132 if(k != -1 && k != diam && l != -1 && l != diam)
133 continue;
134
135 for(n=0; n<3; n++){
136 tmp[n] = buffer[i + j*3 + k*bw + l*3 + n];
137 outer[n] += tmp[n];
138 }
139 if(tmp[0]+tmp[1]+tmp[2] < thresh){
140 hits++;
141 break;
142 }
143 }
144 }
145
146 /*no hits, overwrite with avg surrounding color*/
147 if(!hits){
148
149 /* per channel replacement color */
150 for(n=0; n<3; n++){
151 outer[n] /= (4*diam + 4);
152 }
153
154 for(k=0; k<diam; k++){
155 for(l=0; l<diam; l++){
156 for(n=0; n<3; n++){
157 buffer[i + j*3 + k*bw + l*3 + n] = outer[n];
158 }
159 }
160 }
161 }
162 }
163 }
164 }
165
166 else if(params->format == SANE_FRAME_GRAY && params->depth == 8){
167 for(i=bw; i<bt-bw-(bw*diam); i+=bw){
168 for(j=1; j<pw-1-diam; j++){
169
170 int thresh = 255;
171 int outer = 0;
172 int hits = 0;
173
174 for(k=0; k<diam; k++){
175 for(l=0; l<diam; l++){
176 if(buffer[i + j + k*bw + l] < thresh)
177 thresh = buffer[i + j + k*bw + l];
178 }
179 }
180
181 /* convert darkest pixel into a brighter threshold */
182 thresh = (thresh + 255 + 255)/3;
183
184 /*loop over rows and columns around window */
185 for(k=-1; k<diam+1; k++){
186 for(l=-1; l<diam+1; l++){
187
188 int tmp = 0;
189
190 /* don't count pixels in the window */
191 if(k != -1 && k != diam && l != -1 && l != diam)
192 continue;
193
194 tmp = buffer[i + j + k*bw + l];
195
196 if(tmp < thresh){
197 hits++;
198 break;
199 }
200
201 outer += tmp;
202 }
203 }
204
205 /*no hits, overwrite with avg surrounding color*/
206 if(!hits){
207 /* replacement color */
208 outer /= (4*diam + 4);
209
210 for(k=0; k<diam; k++){
211 for(l=0; l<diam; l++){
212 buffer[i + j + k*bw + l] = outer;
213 }
214 }
215 }
216 }
217 }
218 }
219
220 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
221 for(i=bw; i<bt-bw-(bw*diam); i+=bw){
222 for(j=1; j<pw-1-diam; j++){
223
224 int curr = 0;
225 int hits = 0;
226
227 for(k=0; k<diam; k++){
228 for(l=0; l<diam; l++){
229 curr += buffer[i + k*bw + (j+l)/8] >> (7-(j+l)%8) & 1;
230 }
231 }
232
233 if(!curr)
234 continue;
235
236 /*loop over rows and columns around window */
237 for(k=-1; k<diam+1; k++){
238 for(l=-1; l<diam+1; l++){
239
240 /* don't count pixels in the window */
241 if(k != -1 && k != diam && l != -1 && l != diam)
242 continue;
243
244 hits += buffer[i + k*bw + (j+l)/8] >> (7-(j+l)%8) & 1;
245
246 if(hits)
247 break;
248 }
249 }
250
251 /*no hits, overwrite with white*/
252 if(!hits){
253 for(k=0; k<diam; k++){
254 for(l=0; l<diam; l++){
255 buffer[i + k*bw + (j+l)/8] &= ~(1 << (7-(j+l)%8));
256 }
257 }
258 }
259 }
260 }
261 }
262
263 else{
264 DBG (5, "sanei_magic_despeck: unsupported format/depth\n");
265 ret = SANE_STATUS_INVAL;
266 }
267
268 DBG (10, "sanei_magic_despeck: finish\n");
269 return ret;
270 }
271
272 /* find likely edges of media inside image background color */
273 SANE_Status
sanei_magic_findEdges(SANE_Parameters * params,SANE_Byte * buffer,int dpiX,int dpiY,int * top,int * bot,int * left,int * right)274 sanei_magic_findEdges(SANE_Parameters * params, SANE_Byte * buffer,
275 int dpiX, int dpiY, int * top, int * bot, int * left, int * right)
276 {
277
278 SANE_Status ret = SANE_STATUS_GOOD;
279
280 int width = params->pixels_per_line;
281 int height = params->lines;
282
283 int * topBuf = NULL, * botBuf = NULL;
284 int * leftBuf = NULL, * rightBuf = NULL;
285
286 int topCount = 0, botCount = 0;
287 int leftCount = 0, rightCount = 0;
288
289 int i;
290
291 DBG (10, "sanei_magic_findEdges: start\n");
292
293 /* get buffers to find sides and bottom */
294 topBuf = sanei_magic_getTransY(params,dpiY,buffer,1);
295 if(!topBuf){
296 DBG (5, "sanei_magic_findEdges: no topBuf\n");
297 ret = SANE_STATUS_NO_MEM;
298 goto cleanup;
299 }
300
301 botBuf = sanei_magic_getTransY(params,dpiY,buffer,0);
302 if(!botBuf){
303 DBG (5, "sanei_magic_findEdges: no botBuf\n");
304 ret = SANE_STATUS_NO_MEM;
305 goto cleanup;
306 }
307
308 leftBuf = sanei_magic_getTransX(params,dpiX,buffer,1);
309 if(!leftBuf){
310 DBG (5, "sanei_magic_findEdges: no leftBuf\n");
311 ret = SANE_STATUS_NO_MEM;
312 goto cleanup;
313 }
314
315 rightBuf = sanei_magic_getTransX(params,dpiX,buffer,0);
316 if(!rightBuf){
317 DBG (5, "sanei_magic_findEdges: no rightBuf\n");
318 ret = SANE_STATUS_NO_MEM;
319 goto cleanup;
320 }
321
322 /* loop thru left and right lists, look for top and bottom extremes */
323 *top = height;
324 for(i=0; i<height; i++){
325 if(rightBuf[i] > leftBuf[i]){
326 if(*top > i){
327 *top = i;
328 }
329
330 topCount++;
331 if(topCount > 3){
332 break;
333 }
334 }
335 else{
336 topCount = 0;
337 *top = height;
338 }
339 }
340
341 *bot = -1;
342 for(i=height-1; i>=0; i--){
343 if(rightBuf[i] > leftBuf[i]){
344 if(*bot < i){
345 *bot = i;
346 }
347
348 botCount++;
349 if(botCount > 3){
350 break;
351 }
352 }
353 else{
354 botCount = 0;
355 *bot = -1;
356 }
357 }
358
359 /* could not find top/bot edges */
360 if(*top > *bot){
361 DBG (5, "sanei_magic_findEdges: bad t/b edges\n");
362 ret = SANE_STATUS_UNSUPPORTED;
363 goto cleanup;
364 }
365
366 /* loop thru top and bottom lists, look for l and r extremes
367 * NOTE: We don't look above the top or below the bottom found previously.
368 * This prevents issues with adf scanners that pad the image after the
369 * paper runs out (usually with white) */
370 DBG (5, "sanei_magic_findEdges: bb0:%d tb0:%d b:%d t:%d\n",
371 botBuf[0], topBuf[0], *bot, *top);
372
373 *left = width;
374 for(i=0; i<width; i++){
375 if(botBuf[i] > topBuf[i] && (botBuf[i]-10 < *bot || topBuf[i]+10 > *top)){
376 if(*left > i){
377 *left = i;
378 }
379
380 leftCount++;
381 if(leftCount > 3){
382 break;
383 }
384 }
385 else{
386 leftCount = 0;
387 *left = width;
388 }
389 }
390
391 *right = -1;
392 for(i=width-1; i>=0; i--){
393 if(botBuf[i] > topBuf[i] && (botBuf[i]-10 < *bot || topBuf[i]+10 > *top)){
394 if(*right < i){
395 *right = i;
396 }
397
398 rightCount++;
399 if(rightCount > 3){
400 break;
401 }
402 }
403 else{
404 rightCount = 0;
405 *right = -1;
406 }
407 }
408
409 /* could not find left/right edges */
410 if(*left > *right){
411 DBG (5, "sanei_magic_findEdges: bad l/r edges\n");
412 ret = SANE_STATUS_UNSUPPORTED;
413 goto cleanup;
414 }
415
416 DBG (15, "sanei_magic_findEdges: t:%d b:%d l:%d r:%d\n",
417 *top,*bot,*left,*right);
418
419 cleanup:
420 if(topBuf)
421 free(topBuf);
422 if(botBuf)
423 free(botBuf);
424 if(leftBuf)
425 free(leftBuf);
426 if(rightBuf)
427 free(rightBuf);
428
429 DBG (10, "sanei_magic_findEdges: finish\n");
430 return ret;
431 }
432
433 /* crop image to given size. updates params with new dimensions */
434 SANE_Status
sanei_magic_crop(SANE_Parameters * params,SANE_Byte * buffer,int top,int bot,int left,int right)435 sanei_magic_crop(SANE_Parameters * params, SANE_Byte * buffer,
436 int top, int bot, int left, int right)
437 {
438
439 SANE_Status ret = SANE_STATUS_GOOD;
440
441 int bwidth = params->bytes_per_line;
442
443 int pixels = 0;
444 int bytes = 0;
445 unsigned char * line = NULL;
446 int pos = 0, i;
447
448 DBG (10, "sanei_magic_crop: start\n");
449
450 /*convert left and right to bytes, figure new byte and pixel width */
451 if(params->format == SANE_FRAME_RGB){
452 pixels = right-left;
453 bytes = pixels * 3;
454 left *= 3;
455 right *= 3;
456 }
457 else if(params->format == SANE_FRAME_GRAY && params->depth == 8){
458 pixels = right-left;
459 bytes = right-left;
460 }
461 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
462 left /= 8;
463 right = (right+7)/8;
464 bytes = right-left;
465 pixels = bytes * 8;
466 }
467 else{
468 DBG (5, "sanei_magic_crop: unsupported format/depth\n");
469 ret = SANE_STATUS_INVAL;
470 goto cleanup;
471 }
472
473 DBG (15, "sanei_magic_crop: l:%d r:%d p:%d b:%d\n",left,right,pixels,bytes);
474
475 line = malloc(bytes);
476 if(!line){
477 DBG (5, "sanei_magic_crop: no line\n");
478 ret = SANE_STATUS_NO_MEM;
479 goto cleanup;
480 }
481
482 for(i=top; i<bot; i++){
483 memcpy(line, buffer + i*bwidth + left, bytes);
484 memcpy(buffer + pos, line, bytes);
485 pos += bytes;
486 }
487
488 /* update the params struct with the new image size */
489 params->lines = bot-top;
490 params->pixels_per_line = pixels;
491 params->bytes_per_line = bytes;
492
493 cleanup:
494 if(line)
495 free(line);
496
497 DBG (10, "sanei_magic_crop: finish\n");
498 return ret;
499 }
500
501 /* find angle of media rotation against image background */
502 SANE_Status
sanei_magic_findSkew(SANE_Parameters * params,SANE_Byte * buffer,int dpiX,int dpiY,int * centerX,int * centerY,double * finSlope)503 sanei_magic_findSkew(SANE_Parameters * params, SANE_Byte * buffer,
504 int dpiX, int dpiY, int * centerX, int * centerY, double * finSlope)
505 {
506 SANE_Status ret = SANE_STATUS_GOOD;
507
508 int pwidth = params->pixels_per_line;
509 int height = params->lines;
510
511 double TSlope = 0;
512 int TXInter = 0;
513 int TYInter = 0;
514 double TSlopeHalf = 0;
515 int TOffsetHalf = 0;
516
517 double LSlope = 0;
518 int LXInter = 0;
519 int LYInter = 0;
520 double LSlopeHalf = 0;
521 int LOffsetHalf = 0;
522
523 int rotateX = 0;
524 int rotateY = 0;
525
526 int * topBuf = NULL, * botBuf = NULL;
527
528 DBG (10, "sanei_magic_findSkew: start\n");
529
530 (void) dpiX;
531
532 /* get buffers for edge detection */
533 topBuf = sanei_magic_getTransY(params,dpiY,buffer,1);
534 if(!topBuf){
535 DBG (5, "sanei_magic_findSkew: can't gTY\n");
536 ret = SANE_STATUS_NO_MEM;
537 goto cleanup;
538 }
539
540 botBuf = sanei_magic_getTransY(params,dpiY,buffer,0);
541 if(!botBuf){
542 DBG (5, "sanei_magic_findSkew: can't gTY\n");
543 ret = SANE_STATUS_NO_MEM;
544 goto cleanup;
545 }
546
547 /* find best top line */
548 ret = getTopEdge (pwidth, height, dpiY, topBuf,
549 &TSlope, &TXInter, &TYInter);
550 if(ret){
551 DBG(5,"sanei_magic_findSkew: gTE error: %d",ret);
552 goto cleanup;
553 }
554 DBG(15,"top: %04.04f %d %d\n",TSlope,TXInter,TYInter);
555
556 /* slope is too shallow, don't want to divide by 0 */
557 if(fabs(TSlope) < 0.0001){
558 DBG(15,"sanei_magic_findSkew: slope too shallow: %0.08f\n",TSlope);
559 ret = SANE_STATUS_UNSUPPORTED;
560 goto cleanup;
561 }
562
563 /* find best left line, perpendicular to top line */
564 LSlope = (double)-1/TSlope;
565 ret = getLeftEdge (pwidth, height, topBuf, botBuf, LSlope,
566 &LXInter, &LYInter);
567 if(ret){
568 DBG(5,"sanei_magic_findSkew: gLE error: %d",ret);
569 goto cleanup;
570 }
571 DBG(15,"sanei_magic_findSkew: left: %04.04f %d %d\n",LSlope,LXInter,LYInter);
572
573 /* find point about which to rotate */
574 TSlopeHalf = tan(atan(TSlope)/2);
575 TOffsetHalf = LYInter;
576 DBG(15,"sanei_magic_findSkew: top half: %04.04f %d\n",TSlopeHalf,TOffsetHalf);
577
578 LSlopeHalf = tan((atan(LSlope) + ((LSlope < 0)?-M_PI_2:M_PI_2))/2);
579 LOffsetHalf = - LSlopeHalf * TXInter;
580 DBG(15,"sanei_magic_findSkew: left half: %04.04f %d\n",LSlopeHalf,LOffsetHalf);
581
582 rotateX = (LOffsetHalf-TOffsetHalf) / (TSlopeHalf-LSlopeHalf);
583 rotateY = TSlopeHalf * rotateX + TOffsetHalf;
584 DBG(15,"sanei_magic_findSkew: rotate: %d %d\n",rotateX,rotateY);
585
586 *centerX = rotateX;
587 *centerY = rotateY;
588 *finSlope = TSlope;
589
590 cleanup:
591 if(topBuf)
592 free(topBuf);
593 if(botBuf)
594 free(botBuf);
595
596 DBG (10, "sanei_magic_findSkew: finish\n");
597 return ret;
598 }
599
600 /* function to do a simple rotation by a given slope, around
601 * a given point. The point can be outside of image to get
602 * proper edge alignment. Unused areas filled with bg color
603 * FIXME: Do in-place rotation to save memory */
604 SANE_Status
sanei_magic_rotate(SANE_Parameters * params,SANE_Byte * buffer,int centerX,int centerY,double slope,int bg_color)605 sanei_magic_rotate (SANE_Parameters * params, SANE_Byte * buffer,
606 int centerX, int centerY, double slope, int bg_color)
607 {
608
609 SANE_Status ret = SANE_STATUS_GOOD;
610
611 double slopeRad = -atan(slope);
612 double slopeSin = sin(slopeRad);
613 double slopeCos = cos(slopeRad);
614
615 int pwidth = params->pixels_per_line;
616 int bwidth = params->bytes_per_line;
617 int height = params->lines;
618 int depth = 1;
619
620 unsigned char * outbuf;
621 int i, j, k;
622
623 DBG(10,"sanei_magic_rotate: start: %d %d\n",centerX,centerY);
624
625 outbuf = malloc(bwidth*height);
626 if(!outbuf){
627 DBG(15,"sanei_magic_rotate: no outbuf\n");
628 ret = SANE_STATUS_NO_MEM;
629 goto cleanup;
630 }
631
632 if(params->format == SANE_FRAME_RGB ||
633 (params->format == SANE_FRAME_GRAY && params->depth == 8)
634 ){
635
636 if(params->format == SANE_FRAME_RGB)
637 depth = 3;
638
639 memset(outbuf,bg_color,bwidth*height);
640
641 for (i=0; i<height; i++) {
642 int shiftY = centerY - i;
643
644 for (j=0; j<pwidth; j++) {
645 int shiftX = centerX - j;
646 int sourceX, sourceY;
647
648 sourceX = centerX - (int)(shiftX * slopeCos + shiftY * slopeSin);
649 if (sourceX < 0 || sourceX >= pwidth)
650 continue;
651
652 sourceY = centerY + (int)(-shiftY * slopeCos + shiftX * slopeSin);
653 if (sourceY < 0 || sourceY >= height)
654 continue;
655
656 for (k=0; k<depth; k++) {
657 outbuf[i*bwidth+j*depth+k]
658 = buffer[sourceY*bwidth+sourceX*depth+k];
659 }
660 }
661 }
662 }
663
664 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
665
666 if(bg_color)
667 bg_color = 0xff;
668
669 memset(outbuf,bg_color,bwidth*height);
670
671 for (i=0; i<height; i++) {
672 int shiftY = centerY - i;
673
674 for (j=0; j<pwidth; j++) {
675 int shiftX = centerX - j;
676 int sourceX, sourceY;
677
678 sourceX = centerX - (int)(shiftX * slopeCos + shiftY * slopeSin);
679 if (sourceX < 0 || sourceX >= pwidth)
680 continue;
681
682 sourceY = centerY + (int)(-shiftY * slopeCos + shiftX * slopeSin);
683 if (sourceY < 0 || sourceY >= height)
684 continue;
685
686 /* wipe out old bit */
687 outbuf[i*bwidth + j/8] &= ~(1 << (7-(j%8)));
688
689 /* fill in new bit */
690 outbuf[i*bwidth + j/8] |=
691 ((buffer[sourceY*bwidth + sourceX/8]
692 >> (7-(sourceX%8))) & 1) << (7-(j%8));
693 }
694 }
695 }
696 else{
697 DBG (5, "sanei_magic_rotate: unsupported format/depth\n");
698 ret = SANE_STATUS_INVAL;
699 goto cleanup;
700 }
701
702 memcpy(buffer,outbuf,bwidth*height);
703
704 cleanup:
705
706 if(outbuf)
707 free(outbuf);
708
709 DBG(10,"sanei_magic_rotate: finish\n");
710
711 return ret;
712 }
713
714 SANE_Status
sanei_magic_isBlank(SANE_Parameters * params,SANE_Byte * buffer,double thresh)715 sanei_magic_isBlank (SANE_Parameters * params, SANE_Byte * buffer,
716 double thresh)
717 {
718 SANE_Status ret = SANE_STATUS_GOOD;
719 double imagesum = 0;
720 int i, j;
721
722 DBG(10,"sanei_magic_isBlank: start: %f\n",thresh);
723
724 /*convert thresh from percent (0-100) to 0-1 range*/
725 thresh /= 100;
726
727 if(params->format == SANE_FRAME_RGB ||
728 (params->format == SANE_FRAME_GRAY && params->depth == 8)
729 ){
730
731 /* loop over all rows, find density of each */
732 for(i=0; i<params->lines; i++){
733 int rowsum = 0;
734 SANE_Byte * ptr = buffer + params->bytes_per_line*i;
735
736 /* loop over all columns, sum the 'darkness' of the pixels */
737 for(j=0; j<params->bytes_per_line; j++){
738 rowsum += 255 - ptr[j];
739 }
740
741 imagesum += (double)rowsum/params->bytes_per_line/255;
742 }
743
744 }
745 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
746
747 /* loop over all rows, find density of each */
748 for(i=0; i<params->lines; i++){
749 int rowsum = 0;
750 SANE_Byte * ptr = buffer + params->bytes_per_line*i;
751
752 /* loop over all columns, sum the pixels */
753 for(j=0; j<params->pixels_per_line; j++){
754 rowsum += ptr[j/8] >> (7-(j%8)) & 1;
755 }
756
757 imagesum += (double)rowsum/params->pixels_per_line;
758 }
759
760 }
761 else{
762 DBG (5, "sanei_magic_isBlank: unsupported format/depth\n");
763 ret = SANE_STATUS_INVAL;
764 goto cleanup;
765 }
766
767 DBG (5, "sanei_magic_isBlank: sum:%f lines:%d thresh:%f density:%f\n",
768 imagesum,params->lines,thresh,imagesum/params->lines);
769
770 if(imagesum/params->lines <= thresh){
771 DBG (5, "sanei_magic_isBlank: blank!\n");
772 ret = SANE_STATUS_NO_DOCS;
773 }
774
775 cleanup:
776
777 DBG(10,"sanei_magic_isBlank: finish\n");
778
779 return ret;
780 }
781
782 /* Divide the image into 1/2 inch squares, skipping a 1/4 inch
783 * margin on all sides. If all squares are under the user's density,
784 * signal our caller to skip the image entirely, by returning
785 * SANE_STATUS_NO_DOCS */
786 SANE_Status
sanei_magic_isBlank2(SANE_Parameters * params,SANE_Byte * buffer,int dpiX,int dpiY,double thresh)787 sanei_magic_isBlank2 (SANE_Parameters * params, SANE_Byte * buffer,
788 int dpiX, int dpiY, double thresh)
789 {
790 int xb,yb,x,y;
791
792 /* .25 inch, rounded down to 8 pixel */
793 int xquarter = dpiX/4/8*8;
794 int yquarter = dpiY/4/8*8;
795 int xhalf = xquarter*2;
796 int yhalf = yquarter*2;
797 int blockpix = xhalf*yhalf;
798 int xblocks = (params->pixels_per_line-xhalf)/xhalf;
799 int yblocks = (params->lines-yhalf)/yhalf;
800
801 /*convert thresh from percent (0-100) to 0-1 range*/
802 thresh /= 100;
803
804 DBG (10, "sanei_magic_isBlank2: start %d %d %f %d\n",xhalf,yhalf,thresh,blockpix);
805
806 if(params->depth == 8 &&
807 (params->format == SANE_FRAME_RGB || params->format == SANE_FRAME_GRAY)
808 ){
809
810 int Bpp = params->format == SANE_FRAME_RGB ? 3 : 1;
811
812 for(yb=0; yb<yblocks; yb++){
813 for(xb=0; xb<xblocks; xb++){
814
815 /*count dark pix in this block*/
816 double blocksum = 0;
817
818 for(y=0; y<yhalf; y++){
819
820 /* skip the top and left 1/4 inch */
821 int offset = (yquarter + yb*yhalf + y) * params->bytes_per_line
822 + (xquarter + xb*xhalf) * Bpp;
823 SANE_Byte * ptr = buffer + offset;
824
825 /*count darkness of pix in this row*/
826 int rowsum = 0;
827
828 for(x=0; x<xhalf*Bpp; x++){
829 rowsum += 255 - ptr[x];
830 }
831
832 blocksum += (double)rowsum/(xhalf*Bpp)/255;
833 }
834
835 /* block was darker than thresh, keep image */
836 if(blocksum/yhalf > thresh){
837 DBG (15, "sanei_magic_isBlank2: not blank %f %d %d\n", blocksum/yhalf, yb, xb);
838 return SANE_STATUS_GOOD;
839 }
840 DBG (20, "sanei_magic_isBlank2: block blank %f %d %d\n", blocksum/yhalf, yb, xb);
841 }
842 }
843 }
844 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
845
846 for(yb=0; yb<yblocks; yb++){
847 for(xb=0; xb<xblocks; xb++){
848
849 /*count dark pix in this block*/
850 double blocksum = 0;
851
852 for(y=0; y<yhalf; y++){
853
854 /* skip the top and left 1/4 inch */
855 int offset = (yquarter + yb*yhalf + y) * params->bytes_per_line
856 + (xquarter + xb*xhalf) / 8;
857 SANE_Byte * ptr = buffer + offset;
858
859 /*count darkness of pix in this row*/
860 int rowsum = 0;
861
862 for(x=0; x<xhalf; x++){
863 rowsum += ptr[x/8] >> (7-(x%8)) & 1;
864 }
865
866 blocksum += (double)rowsum/xhalf;
867 }
868
869 /* block was darker than thresh, keep image */
870 if(blocksum/yhalf > thresh){
871 DBG (15, "sanei_magic_isBlank2: not blank %f %d %d\n", blocksum/yhalf, yb, xb);
872 return SANE_STATUS_GOOD;
873 }
874 DBG (20, "sanei_magic_isBlank2: block blank %f %d %d\n", blocksum/yhalf, yb, xb);
875 }
876 }
877 }
878 else{
879 DBG (5, "sanei_magic_isBlank2: unsupported format/depth\n");
880 return SANE_STATUS_INVAL;
881 }
882
883 DBG (10, "sanei_magic_isBlank2: returning blank\n");
884 return SANE_STATUS_NO_DOCS;
885 }
886
887 SANE_Status
sanei_magic_findTurn(SANE_Parameters * params,SANE_Byte * buffer,int dpiX,int dpiY,int * angle)888 sanei_magic_findTurn(SANE_Parameters * params, SANE_Byte * buffer,
889 int dpiX, int dpiY, int * angle)
890 {
891 SANE_Status ret = SANE_STATUS_GOOD;
892 int i, j, k;
893 int depth = 1;
894 int htrans=0, vtrans=0;
895 int htot=0, vtot=0;
896
897 DBG(10,"sanei_magic_findTurn: start\n");
898
899 if(params->format == SANE_FRAME_RGB ||
900 (params->format == SANE_FRAME_GRAY && params->depth == 8)
901 ){
902
903 if(params->format == SANE_FRAME_RGB)
904 depth = 3;
905
906 /* loop over some rows, count segment lengths */
907 for(i=0; i<params->lines; i+=dpiY/20){
908 SANE_Byte * ptr = buffer + params->bytes_per_line*i;
909 int color = 0;
910 int len = 0;
911 int sum = 0;
912
913 /* loop over all columns */
914 for(j=0; j<params->pixels_per_line; j++){
915 int curr = 0;
916
917 /*convert color to gray*/
918 for (k=0; k<depth; k++) {
919 curr += ptr[j*depth+k];
920 }
921 curr /= depth;
922
923 /*convert gray to binary (with hysteresis) */
924 curr = (curr < 100)?1:
925 (curr > 156)?0:color;
926
927 /*count segment length*/
928 if(curr != color || j==params->pixels_per_line-1){
929 sum += len * len/5;
930 len = 0;
931 color = curr;
932 }
933 else{
934 len++;
935 }
936 }
937
938 htot++;
939 htrans += (double)sum/params->pixels_per_line;
940 }
941
942 /* loop over some cols, count dark vs light transitions */
943 for(i=0; i<params->pixels_per_line; i+=dpiX/20){
944 SANE_Byte * ptr = buffer + i*depth;
945 int color = 0;
946 int len = 0;
947 int sum = 0;
948
949 /* loop over all rows */
950 for(j=0; j<params->lines; j++){
951 int curr = 0;
952
953 /*convert color to gray*/
954 for (k=0; k<depth; k++) {
955 curr += ptr[j*params->bytes_per_line+k];
956 }
957 curr /= depth;
958
959 /*convert gray to binary (with hysteresis) */
960 curr = (curr < 100)?1:
961 (curr > 156)?0:color;
962
963 /*count segment length*/
964 if(curr != color || j==params->lines-1){
965 sum += len * len/5;
966 len = 0;
967 color = curr;
968 }
969 else{
970 len++;
971 }
972 }
973
974 vtot++;
975 vtrans += (double)sum/params->lines;
976 }
977
978 }
979 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
980
981 /* loop over some rows, count segment lengths */
982 for(i=0; i<params->lines; i+=dpiY/30){
983 SANE_Byte * ptr = buffer + params->bytes_per_line*i;
984 int color = 0;
985 int len = 0;
986 int sum = 0;
987
988 /* loop over all columns */
989 for(j=0; j<params->pixels_per_line; j++){
990 int curr = ptr[j/8] >> (7-(j%8)) & 1;
991
992 /*count segment length*/
993 if(curr != color || j==params->pixels_per_line-1){
994 sum += len * len/5;
995 len = 0;
996 color = curr;
997 }
998 else{
999 len++;
1000 }
1001 }
1002
1003 htot++;
1004 htrans += (double)sum/params->pixels_per_line;
1005 }
1006
1007 /* loop over some cols, count dark vs light transitions */
1008 for(i=0; i<params->pixels_per_line; i+=dpiX/30){
1009 SANE_Byte * ptr = buffer;
1010 int color = 0;
1011 int len = 0;
1012 int sum = 0;
1013
1014 /* loop over all rows */
1015 for(j=0; j<params->lines; j++){
1016 int curr = ptr[j*params->bytes_per_line + i/8] >> (7-(i%8)) & 1;
1017
1018 /*count segment length*/
1019 if(curr != color || j==params->lines-1){
1020 sum += len * len/5;
1021 len = 0;
1022 color = curr;
1023 }
1024 else{
1025 len++;
1026 }
1027 }
1028
1029 vtot++;
1030 vtrans += (double)sum/params->lines;
1031 }
1032
1033 }
1034 else{
1035 DBG (5, "sanei_magic_findTurn: unsupported format/depth\n");
1036 ret = SANE_STATUS_INVAL;
1037 goto cleanup;
1038 }
1039
1040 DBG (10, "sanei_magic_findTurn: vtrans=%d vtot=%d vfrac=%f htrans=%d htot=%d hfrac=%f\n",
1041 vtrans, vtot, (double)vtrans/vtot, htrans, htot, (double)htrans/htot
1042 );
1043
1044 if((double)vtrans/vtot > (double)htrans/htot){
1045 DBG (10, "sanei_magic_findTurn: suggest turning 90\n");
1046 *angle = 90;
1047 }
1048
1049 cleanup:
1050
1051 DBG(10,"sanei_magic_findTurn: finish\n");
1052
1053 return ret;
1054 }
1055
1056 /* FIXME: Do in-place rotation to save memory */
1057 SANE_Status
sanei_magic_turn(SANE_Parameters * params,SANE_Byte * buffer,int angle)1058 sanei_magic_turn(SANE_Parameters * params, SANE_Byte * buffer,
1059 int angle)
1060 {
1061 SANE_Status ret = SANE_STATUS_GOOD;
1062 int opwidth, ipwidth = params->pixels_per_line;
1063 int obwidth, ibwidth = params->bytes_per_line;
1064 int oheight, iheight = params->lines;
1065 int depth = 1;
1066
1067 unsigned char * outbuf = NULL;
1068 int i, j, k;
1069
1070 DBG(10,"sanei_magic_turn: start %d\n",angle);
1071
1072 if(params->format == SANE_FRAME_RGB)
1073 depth = 3;
1074
1075 /*clean angle and convert to 0-3*/
1076 angle = (angle % 360) / 90;
1077
1078 /*figure size of output image*/
1079 switch(angle){
1080 case 1:
1081 case 3:
1082 opwidth = iheight;
1083 oheight = ipwidth;
1084
1085 /*gray and color, 1 or 3 bytes per pixel*/
1086 if ( params->format == SANE_FRAME_RGB
1087 || (params->format == SANE_FRAME_GRAY && params->depth == 8)
1088 ){
1089 obwidth = opwidth*depth;
1090 }
1091
1092 /*clamp binary to byte width. must be <= input image*/
1093 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
1094 obwidth = opwidth/8;
1095 opwidth = obwidth*8;
1096 }
1097
1098 else{
1099 DBG(10,"sanei_magic_turn: bad params\n");
1100 ret = SANE_STATUS_INVAL;
1101 goto cleanup;
1102 }
1103
1104 break;
1105
1106 case 2:
1107 opwidth = ipwidth;
1108 obwidth = ibwidth;
1109 oheight = iheight;
1110 break;
1111
1112 default:
1113 DBG(10,"sanei_magic_turn: no turn\n");
1114 goto cleanup;
1115 }
1116
1117 /*get output image buffer*/
1118 outbuf = malloc(obwidth*oheight);
1119 if(!outbuf){
1120 DBG(15,"sanei_magic_turn: no outbuf\n");
1121 ret = SANE_STATUS_NO_MEM;
1122 goto cleanup;
1123 }
1124
1125 /*turn color & gray image*/
1126 if(params->format == SANE_FRAME_RGB ||
1127 (params->format == SANE_FRAME_GRAY && params->depth == 8)
1128 ){
1129
1130 switch (angle) {
1131
1132 /*rotate 90 clockwise*/
1133 case 1:
1134 for (i=0; i<oheight; i++) {
1135 for (j=0; j<opwidth; j++) {
1136 for (k=0; k<depth; k++) {
1137 outbuf[i*obwidth + j*depth + k]
1138 = buffer[(iheight-j-1)*ibwidth + i*depth + k];
1139 }
1140 }
1141 }
1142 break;
1143
1144 /*rotate 180 clockwise*/
1145 case 2:
1146 for (i=0; i<oheight; i++) {
1147 for (j=0; j<opwidth; j++) {
1148 for (k=0; k<depth; k++) {
1149 outbuf[i*obwidth + j*depth + k]
1150 = buffer[(iheight-i-1)*ibwidth + (ipwidth-j-1)*depth + k];
1151 }
1152 }
1153 }
1154 break;
1155
1156 /*rotate 270 clockwise*/
1157 case 3:
1158 for (i=0; i<oheight; i++) {
1159 for (j=0; j<opwidth; j++) {
1160 for (k=0; k<depth; k++) {
1161 outbuf[i*obwidth + j*depth + k]
1162 = buffer[j*ibwidth + (ipwidth-i-1)*depth + k];
1163 }
1164 }
1165 }
1166 break;
1167 } /*end switch*/
1168 }
1169
1170 /*turn binary image*/
1171 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
1172
1173 switch (angle) {
1174
1175 /*rotate 90 clockwise*/
1176 case 1:
1177 for (i=0; i<oheight; i++) {
1178 for (j=0; j<opwidth; j++) {
1179 unsigned char curr
1180 = buffer[(iheight-j-1)*ibwidth + i/8] >> (7-(i%8)) & 1;
1181
1182 unsigned char mask = 1 << (7-(j%8));
1183
1184 if(curr){
1185 outbuf[i*obwidth + j/8] |= mask;
1186 }
1187 else{
1188 outbuf[i*obwidth + j/8] &= (~mask);
1189 }
1190
1191 }
1192 }
1193 break;
1194
1195 /*rotate 180 clockwise*/
1196 case 2:
1197 for (i=0; i<oheight; i++) {
1198 for (j=0; j<opwidth; j++) {
1199 unsigned char curr
1200 = buffer[(iheight-i-1)*ibwidth + (ipwidth-j-1)/8] >> (j%8) & 1;
1201
1202 unsigned char mask = 1 << (7-(j%8));
1203
1204 if(curr){
1205 outbuf[i*obwidth + j/8] |= mask;
1206 }
1207 else{
1208 outbuf[i*obwidth + j/8] &= (~mask);
1209 }
1210
1211 }
1212 }
1213 break;
1214
1215 /*rotate 270 clockwise*/
1216 case 3:
1217 for (i=0; i<oheight; i++) {
1218 for (j=0; j<opwidth; j++) {
1219 unsigned char curr
1220 = buffer[j*ibwidth + (ipwidth-i-1)/8] >> (i%8) & 1;
1221
1222 unsigned char mask = 1 << (7-(j%8));
1223
1224 if(curr){
1225 outbuf[i*obwidth + j/8] |= mask;
1226 }
1227 else{
1228 outbuf[i*obwidth + j/8] &= (~mask);
1229 }
1230
1231 }
1232 }
1233 break;
1234 } /*end switch*/
1235 }
1236
1237 else{
1238 DBG (5, "sanei_magic_turn: unsupported format/depth\n");
1239 ret = SANE_STATUS_INVAL;
1240 goto cleanup;
1241 }
1242
1243 /*copy output back into input buffer*/
1244 memcpy(buffer,outbuf,obwidth*oheight);
1245
1246 /*update input params*/
1247 params->pixels_per_line = opwidth;
1248 params->bytes_per_line = obwidth;
1249 params->lines = oheight;
1250
1251 cleanup:
1252
1253 if(outbuf)
1254 free(outbuf);
1255
1256 DBG(10,"sanei_magic_turn: finish\n");
1257
1258 return ret;
1259 }
1260
1261 /* Utility functions, not used outside this file */
1262
1263 /* Repeatedly call getLine to find the best range of slope and offset.
1264 * Shift the ranges thru 4 different positions to avoid splitting data
1265 * across multiple bins (false positive). Home-in on the most likely upper
1266 * line of the paper inside the image. Return the 'best' edge. */
1267 static SANE_Status
getTopEdge(int width,int height,int resolution,int * buff,double * finSlope,int * finXInter,int * finYInter)1268 getTopEdge(int width, int height, int resolution,
1269 int * buff, double * finSlope, int * finXInter, int * finYInter)
1270 {
1271 SANE_Status ret = SANE_STATUS_GOOD;
1272
1273 int slopes = 31;
1274 int offsets = 31;
1275 double maxSlope = 1;
1276 double minSlope = -1;
1277 int maxOffset = resolution;
1278 int minOffset = -resolution;
1279
1280 double topSlope = 0;
1281 int topOffset = 0;
1282 int topDensity = 0;
1283
1284 int i,j;
1285 int pass = 0;
1286
1287 DBG(10,"getTopEdge: start\n");
1288
1289 while(pass++ < 7){
1290 double sStep = (maxSlope-minSlope)/slopes;
1291 int oStep = (maxOffset-minOffset)/offsets;
1292
1293 double slope = 0;
1294 int offset = 0;
1295 int density = 0;
1296 int go = 0;
1297
1298 topSlope = 0;
1299 topOffset = 0;
1300 topDensity = 0;
1301
1302 /* find lines 4 times with slightly moved params,
1303 * to bypass binning errors, highest density wins */
1304 for(i=0;i<2;i++){
1305 double sStep2 = sStep*i/2;
1306 for(j=0;j<2;j++){
1307 int oStep2 = oStep*j/2;
1308 ret = getLine(height,width,buff,slopes,minSlope+sStep2,maxSlope+sStep2,offsets,minOffset+oStep2,maxOffset+oStep2,&slope,&offset,&density);
1309 if(ret){
1310 DBG(5,"getTopEdge: getLine error %d\n",ret);
1311 return ret;
1312 }
1313 DBG(15,"getTopEdge: %d %d %+0.4f %d %d\n",i,j,slope,offset,density);
1314
1315 if(density > topDensity){
1316 topSlope = slope;
1317 topOffset = offset;
1318 topDensity = density;
1319 }
1320 }
1321 }
1322
1323 DBG(15,"getTopEdge: ok %+0.4f %d %d\n",topSlope,topOffset,topDensity);
1324
1325 /* did not find anything promising on first pass,
1326 * give up instead of fixating on some small, pointless feature */
1327 if(pass == 1 && topDensity < width/5){
1328 DBG(5,"getTopEdge: density too small %d %d\n",topDensity,width);
1329 topOffset = 0;
1330 topSlope = 0;
1331 break;
1332 }
1333
1334 /* if slope can zoom in some more, do so. */
1335 if(sStep >= 0.0001){
1336 minSlope = topSlope - sStep;
1337 maxSlope = topSlope + sStep;
1338 go = 1;
1339 }
1340
1341 /* if offset can zoom in some more, do so. */
1342 if(oStep){
1343 minOffset = topOffset - oStep;
1344 maxOffset = topOffset + oStep;
1345 go = 1;
1346 }
1347
1348 /* cannot zoom in more, bail out */
1349 if(!go){
1350 break;
1351 }
1352
1353 DBG(15,"getTopEdge: zoom: %+0.4f %+0.4f %d %d\n",
1354 minSlope,maxSlope,minOffset,maxOffset);
1355 }
1356
1357 /* topOffset is in the center of the image,
1358 * convert to x and y intercept */
1359 if(topSlope != 0){
1360 *finYInter = topOffset - topSlope * width/2;
1361 *finXInter = *finYInter / -topSlope;
1362 *finSlope = topSlope;
1363 }
1364 else{
1365 *finYInter = 0;
1366 *finXInter = 0;
1367 *finSlope = 0;
1368 }
1369
1370 DBG(10,"getTopEdge: finish\n");
1371
1372 return 0;
1373 }
1374
1375 /* Loop thru a transition array, and use a simplified Hough transform
1376 * to divide likely edges into a 2-d array of bins. Then weight each
1377 * bin based on its angle and offset. Return the 'best' bin. */
1378 static SANE_Status
getLine(int height,int width,int * buff,int slopes,double minSlope,double maxSlope,int offsets,int minOffset,int maxOffset,double * finSlope,int * finOffset,int * finDensity)1379 getLine (int height, int width, int * buff,
1380 int slopes, double minSlope, double maxSlope,
1381 int offsets, int minOffset, int maxOffset,
1382 double * finSlope, int * finOffset, int * finDensity)
1383 {
1384 SANE_Status ret = 0;
1385
1386 int ** lines = NULL;
1387 int i, j;
1388 int rise, run;
1389 double slope;
1390 int offset;
1391 int sIndex, oIndex;
1392 int hWidth = width/2;
1393
1394 double * slopeCenter = NULL;
1395 int * slopeScale = NULL;
1396 double * offsetCenter = NULL;
1397 int * offsetScale = NULL;
1398
1399 int maxDensity = 1;
1400 double absMaxSlope = fabs(maxSlope);
1401 double absMinSlope = fabs(minSlope);
1402 int absMaxOffset = abs(maxOffset);
1403 int absMinOffset = abs(minOffset);
1404
1405 DBG(10,"getLine: start %+0.4f %+0.4f %d %d\n",
1406 minSlope,maxSlope,minOffset,maxOffset);
1407
1408 /*silence compiler*/
1409 (void) height;
1410
1411 if(absMaxSlope < absMinSlope)
1412 absMaxSlope = absMinSlope;
1413
1414 if(absMaxOffset < absMinOffset)
1415 absMaxOffset = absMinOffset;
1416
1417 /* build an array of pretty-print values for slope */
1418 slopeCenter = calloc(slopes,sizeof(double));
1419 if(!slopeCenter){
1420 DBG(5,"getLine: can't load slopeCenter\n");
1421 ret = SANE_STATUS_NO_MEM;
1422 goto cleanup;
1423 }
1424
1425 /* build an array of scaling factors for slope */
1426 slopeScale = calloc(slopes,sizeof(int));
1427 if(!slopeScale){
1428 DBG(5,"getLine: can't load slopeScale\n");
1429 ret = SANE_STATUS_NO_MEM;
1430 goto cleanup;
1431 }
1432
1433 for(j=0;j<slopes;j++){
1434
1435 /* find central value of this 'bucket' */
1436 slopeCenter[j] = (
1437 (double)j*(maxSlope-minSlope)/slopes+minSlope
1438 + (double)(j+1)*(maxSlope-minSlope)/slopes+minSlope
1439 )/2;
1440
1441 /* scale value from the requested range into an inverted 100-1 range
1442 * input close to 0 makes output close to 100 */
1443 slopeScale[j] = 101 - fabs(slopeCenter[j])*100/absMaxSlope;
1444 }
1445
1446 /* build an array of pretty-print values for offset */
1447 offsetCenter = calloc(offsets,sizeof(double));
1448 if(!offsetCenter){
1449 DBG(5,"getLine: can't load offsetCenter\n");
1450 ret = SANE_STATUS_NO_MEM;
1451 goto cleanup;
1452 }
1453
1454 /* build an array of scaling factors for offset */
1455 offsetScale = calloc(offsets,sizeof(int));
1456 if(!offsetScale){
1457 DBG(5,"getLine: can't load offsetScale\n");
1458 ret = SANE_STATUS_NO_MEM;
1459 goto cleanup;
1460 }
1461
1462 for(j=0;j<offsets;j++){
1463
1464 /* find central value of this 'bucket'*/
1465 offsetCenter[j] = (
1466 (double)j/offsets*(maxOffset-minOffset)+minOffset
1467 + (double)(j+1)/offsets*(maxOffset-minOffset)+minOffset
1468 )/2;
1469
1470 /* scale value from the requested range into an inverted 100-1 range
1471 * input close to 0 makes output close to 100 */
1472 offsetScale[j] = 101 - fabs(offsetCenter[j])*100/absMaxOffset;
1473 }
1474
1475 /* build 2-d array of 'density', divided into slope and offset ranges */
1476 lines = calloc(slopes, sizeof(int *));
1477 if(!lines){
1478 DBG(5,"getLine: can't load lines\n");
1479 ret = SANE_STATUS_NO_MEM;
1480 goto cleanup;
1481 }
1482
1483 for(i=0;i<slopes;i++){
1484 if(!(lines[i] = calloc(offsets, sizeof(int)))){
1485 DBG(5,"getLine: can't load lines %d\n",i);
1486 ret = SANE_STATUS_NO_MEM;
1487 goto cleanup;
1488 }
1489 }
1490
1491 for(i=0;i<width;i++){
1492 for(j=i+1;j<width && j<i+width/3;j++){
1493
1494 /*FIXME: check for invalid (min/max) values?*/
1495 rise = buff[j] - buff[i];
1496 run = j-i;
1497
1498 slope = (double)rise/run;
1499 if(slope >= maxSlope || slope < minSlope)
1500 continue;
1501
1502 /* offset in center of width, not y intercept! */
1503 offset = slope * hWidth + buff[i] - slope * i;
1504 if(offset >= maxOffset || offset < minOffset)
1505 continue;
1506
1507 sIndex = (slope - minSlope) * slopes/(maxSlope-minSlope);
1508 if(sIndex >= slopes)
1509 continue;
1510
1511 oIndex = (offset - minOffset) * offsets/(maxOffset-minOffset);
1512 if(oIndex >= offsets)
1513 continue;
1514
1515 lines[sIndex][oIndex]++;
1516 }
1517 }
1518
1519 /* go thru array, and find most dense line (highest number) */
1520 for(i=0;i<slopes;i++){
1521 for(j=0;j<offsets;j++){
1522 if(lines[i][j] > maxDensity)
1523 maxDensity = lines[i][j];
1524 }
1525 }
1526
1527 DBG(15,"getLine: maxDensity %d\n",maxDensity);
1528
1529 *finSlope = 0;
1530 *finOffset = 0;
1531 *finDensity = 0;
1532
1533 /* go thru array, and scale densities to % of maximum, plus adjust for
1534 * preferred (smaller absolute value) slope and offset */
1535 for(i=0;i<slopes;i++){
1536 for(j=0;j<offsets;j++){
1537 lines[i][j] = (float)lines[i][j] / maxDensity * slopeScale[i] * offsetScale[j];
1538 if(lines[i][j] > *finDensity){
1539 *finDensity = lines[i][j];
1540 *finSlope = slopeCenter[i];
1541 *finOffset = offsetCenter[j];
1542 }
1543 }
1544 }
1545
1546 if(0){
1547 fprintf(stderr,"offsetCenter: ");
1548 for(j=0;j<offsets;j++){
1549 fprintf(stderr," %+04.0f",offsetCenter[j]);
1550 }
1551 fprintf(stderr,"\n");
1552
1553 fprintf(stderr,"offsetScale: ");
1554 for(j=0;j<offsets;j++){
1555 fprintf(stderr," %04d",offsetScale[j]);
1556 }
1557 fprintf(stderr,"\n");
1558
1559 for(i=0;i<slopes;i++){
1560 fprintf(stderr,"slope: %02d %+02.2f %03d:",i,slopeCenter[i],slopeScale[i]);
1561 for(j=0;j<offsets;j++){
1562 fprintf(stderr,"% 5d",lines[i][j]);
1563 }
1564 fprintf(stderr,"\n");
1565 }
1566 }
1567
1568 /* don't forget to cleanup */
1569 cleanup:
1570 for(i=0;i<slopes;i++){
1571 if(lines[i])
1572 free(lines[i]);
1573 }
1574 if(lines)
1575 free(lines);
1576 if(slopeCenter)
1577 free(slopeCenter);
1578 if(slopeScale)
1579 free(slopeScale);
1580 if(offsetCenter)
1581 free(offsetCenter);
1582 if(offsetScale)
1583 free(offsetScale);
1584
1585 DBG(10,"getLine: finish\n");
1586
1587 return ret;
1588 }
1589
1590 /* find the left side of paper by moving a line
1591 * perpendicular to top slope across the image
1592 * the 'left-most' point on the paper is the
1593 * one with the smallest X intercept
1594 * return x and y intercepts */
1595 static SANE_Status
getLeftEdge(int width,int height,int * top,int * bot,double slope,int * finXInter,int * finYInter)1596 getLeftEdge (int width, int height, int * top, int * bot,
1597 double slope, int * finXInter, int * finYInter)
1598 {
1599
1600 int i;
1601 int topXInter, topYInter;
1602 int botXInter, botYInter;
1603 int leftCount;
1604
1605 DBG(10,"getEdgeSlope: start\n");
1606
1607 topXInter = width;
1608 topYInter = 0;
1609 leftCount = 0;
1610
1611 for(i=0;i<width;i++){
1612
1613 if(top[i] < height){
1614 int tyi = top[i] - (slope * i);
1615 int txi = tyi/-slope;
1616
1617 if(topXInter > txi){
1618 topXInter = txi;
1619 topYInter = tyi;
1620 }
1621
1622 leftCount++;
1623 if(leftCount > 5){
1624 break;
1625 }
1626 }
1627 else{
1628 topXInter = width;
1629 topYInter = 0;
1630 leftCount = 0;
1631 }
1632 }
1633
1634 botXInter = width;
1635 botYInter = 0;
1636 leftCount = 0;
1637
1638 for(i=0;i<width;i++){
1639
1640 if(bot[i] > -1){
1641
1642 int byi = bot[i] - (slope * i);
1643 int bxi = byi/-slope;
1644
1645 if(botXInter > bxi){
1646 botXInter = bxi;
1647 botYInter = byi;
1648 }
1649
1650 leftCount++;
1651 if(leftCount > 5){
1652 break;
1653 }
1654 }
1655 else{
1656 botXInter = width;
1657 botYInter = 0;
1658 leftCount = 0;
1659 }
1660 }
1661
1662 if(botXInter < topXInter){
1663 *finXInter = botXInter;
1664 *finYInter = botYInter;
1665 }
1666 else{
1667 *finXInter = topXInter;
1668 *finYInter = topYInter;
1669 }
1670
1671 DBG(10,"getEdgeSlope: finish\n");
1672
1673 return 0;
1674 }
1675
1676 /* Loop thru the image and look for first color change in each column.
1677 * Return a malloc'd array. Caller is responsible for freeing. */
1678 int *
sanei_magic_getTransY(SANE_Parameters * params,int dpi,SANE_Byte * buffer,int top)1679 sanei_magic_getTransY (
1680 SANE_Parameters * params, int dpi, SANE_Byte * buffer, int top)
1681 {
1682 int * buff;
1683
1684 int i, j, k;
1685 int winLen = 9;
1686
1687 int width = params->pixels_per_line;
1688 int height = params->lines;
1689 int depth = 1;
1690
1691 /* defaults for bottom-up */
1692 int firstLine = height-1;
1693 int lastLine = -1;
1694 int direction = -1;
1695
1696 DBG (10, "sanei_magic_getTransY: start\n");
1697
1698 /* override for top-down */
1699 if(top){
1700 firstLine = 0;
1701 lastLine = height;
1702 direction = 1;
1703 }
1704
1705 /* build output and preload with impossible value */
1706 buff = calloc(width,sizeof(int));
1707 if(!buff){
1708 DBG (5, "sanei_magic_getTransY: no buff\n");
1709 return NULL;
1710 }
1711 for(i=0; i<width; i++)
1712 buff[i] = lastLine;
1713
1714 /* load the buff array with y value for first color change from edge
1715 * gray/color uses a different algo from binary/halftone */
1716 if(params->format == SANE_FRAME_RGB ||
1717 (params->format == SANE_FRAME_GRAY && params->depth == 8)
1718 ){
1719
1720 if(params->format == SANE_FRAME_RGB)
1721 depth = 3;
1722
1723 /* loop over all columns, find first transition */
1724 for(i=0; i<width; i++){
1725
1726 int near = 0;
1727 int far = 0;
1728
1729 /* load the near and far windows with repeated copy of first pixel */
1730 for(k=0; k<depth; k++){
1731 near += buffer[(firstLine*width+i) * depth + k];
1732 }
1733 near *= winLen;
1734 far = near;
1735
1736 /* move windows, check delta */
1737 for(j=firstLine+direction; j!=lastLine; j+=direction){
1738
1739 int farLine = j-winLen*2*direction;
1740 int nearLine = j-winLen*direction;
1741
1742 if(farLine < 0 || farLine >= height){
1743 farLine = firstLine;
1744 }
1745 if(nearLine < 0 || nearLine >= height){
1746 nearLine = firstLine;
1747 }
1748
1749 for(k=0; k<depth; k++){
1750 far -= buffer[(farLine*width+i)*depth+k];
1751 far += buffer[(nearLine*width+i)*depth+k];
1752
1753 near -= buffer[(nearLine*width+i)*depth+k];
1754 near += buffer[(j*width+i)*depth+k];
1755 }
1756
1757 /* significant transition */
1758 if(abs(near - far) > 50*winLen*depth - near*40/255){
1759 buff[i] = j;
1760 break;
1761 }
1762 }
1763 }
1764 }
1765
1766 else if(params->format == SANE_FRAME_GRAY && params->depth == 1){
1767
1768 int near = 0;
1769
1770 for(i=0; i<width; i++){
1771
1772 /* load the near window with first pixel */
1773 near = buffer[(firstLine*width+i)/8] >> (7-(i%8)) & 1;
1774
1775 /* move */
1776 for(j=firstLine+direction; j!=lastLine; j+=direction){
1777 if((buffer[(j*width+i)/8] >> (7-(i%8)) & 1) != near){
1778 buff[i] = j;
1779 break;
1780 }
1781 }
1782 }
1783 }
1784
1785 /* some other format? */
1786 else{
1787 DBG (5, "sanei_magic_getTransY: unsupported format/depth\n");
1788 free(buff);
1789 return NULL;
1790 }
1791
1792 /* ignore transitions with few neighbors within .5 inch */
1793 for(i=0;i<width-7;i++){
1794 int sum = 0;
1795 for(j=1;j<=7;j++){
1796 if(abs(buff[i+j] - buff[i]) < dpi/2)
1797 sum++;
1798 }
1799 if(sum < 2)
1800 buff[i] = lastLine;
1801 }
1802
1803 DBG (10, "sanei_magic_getTransY: finish\n");
1804
1805 return buff;
1806 }
1807
1808 /* Loop thru the image height and look for first color change in each row.
1809 * Return a malloc'd array. Caller is responsible for freeing. */
1810 int *
sanei_magic_getTransX(SANE_Parameters * params,int dpi,SANE_Byte * buffer,int left)1811 sanei_magic_getTransX (
1812 SANE_Parameters * params, int dpi, SANE_Byte * buffer, int left)
1813 {
1814 int * buff;
1815
1816 int i, j, k;
1817 int winLen = 9;
1818
1819 int bwidth = params->bytes_per_line;
1820 int width = params->pixels_per_line;
1821 int height = params->lines;
1822 int depth = 1;
1823
1824 /* defaults for right-first */
1825 int firstCol = width-1;
1826 int lastCol = -1;
1827 int direction = -1;
1828
1829 DBG (10, "sanei_magic_getTransX: start\n");
1830
1831 /* override for left-first*/
1832 if(left){
1833 firstCol = 0;
1834 lastCol = width;
1835 direction = 1;
1836 }
1837
1838 /* build output and preload with impossible value */
1839 buff = calloc(height,sizeof(int));
1840 if(!buff){
1841 DBG (5, "sanei_magic_getTransX: no buff\n");
1842 return NULL;
1843 }
1844 for(i=0; i<height; i++)
1845 buff[i] = lastCol;
1846
1847 /* load the buff array with x value for first color change from edge
1848 * gray/color uses a different algo from binary/halftone */
1849 if(params->format == SANE_FRAME_RGB ||
1850 (params->format == SANE_FRAME_GRAY && params->depth == 8)
1851 ){
1852
1853 if(params->format == SANE_FRAME_RGB)
1854 depth = 3;
1855
1856 /* loop over all columns, find first transition */
1857 for(i=0; i<height; i++){
1858
1859 int near = 0;
1860 int far = 0;
1861
1862 /* load the near and far windows with repeated copy of first pixel */
1863 for(k=0; k<depth; k++){
1864 near += buffer[i*bwidth + k];
1865 }
1866 near *= winLen;
1867 far = near;
1868
1869 /* move windows, check delta */
1870 for(j=firstCol+direction; j!=lastCol; j+=direction){
1871
1872 int farCol = j-winLen*2*direction;
1873 int nearCol = j-winLen*direction;
1874
1875 if(farCol < 0 || farCol >= width){
1876 farCol = firstCol;
1877 }
1878 if(nearCol < 0 || nearCol >= width){
1879 nearCol = firstCol;
1880 }
1881
1882 for(k=0; k<depth; k++){
1883 far -= buffer[i*bwidth + farCol*depth + k];
1884 far += buffer[i*bwidth + nearCol*depth + k];
1885
1886 near -= buffer[i*bwidth + nearCol*depth + k];
1887 near += buffer[i*bwidth + j*depth + k];
1888 }
1889
1890 if(abs(near - far) > 50*winLen*depth - near*40/255){
1891 buff[i] = j;
1892 break;
1893 }
1894 }
1895 }
1896 }
1897
1898 else if (params->format == SANE_FRAME_GRAY && params->depth == 1){
1899
1900 int near = 0;
1901
1902 for(i=0; i<height; i++){
1903
1904 /* load the near window with first pixel */
1905 near = buffer[i*bwidth + firstCol/8] >> (7-(firstCol%8)) & 1;
1906
1907 /* move */
1908 for(j=firstCol+direction; j!=lastCol; j+=direction){
1909 if((buffer[i*bwidth + j/8] >> (7-(j%8)) & 1) != near){
1910 buff[i] = j;
1911 break;
1912 }
1913 }
1914 }
1915 }
1916
1917 /* some other format? */
1918 else{
1919 DBG (5, "sanei_magic_getTransX: unsupported format/depth\n");
1920 free(buff);
1921 return NULL;
1922 }
1923
1924 /* ignore transitions with few neighbors within .5 inch */
1925 for(i=0;i<height-7;i++){
1926 int sum = 0;
1927 for(j=1;j<=7;j++){
1928 if(abs(buff[i+j] - buff[i]) < dpi/2)
1929 sum++;
1930 }
1931 if(sum < 2)
1932 buff[i] = lastCol;
1933 }
1934
1935 DBG (10, "sanei_magic_getTransX: finish\n");
1936
1937 return buff;
1938 }
1939