From 6e9c41a892ed0e0da326e0278b3221ce3f5713b8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B6rg=20Frings-F=C3=BCrst?= Date: Mon, 6 Oct 2014 14:00:40 +0200 Subject: Initial import of sane-backends version 1.0.24-1.2 --- sanei/sanei_magic.c | 1941 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1941 insertions(+) create mode 100644 sanei/sanei_magic.c (limited to 'sanei/sanei_magic.c') diff --git a/sanei/sanei_magic.c b/sanei/sanei_magic.c new file mode 100644 index 0000000..167d7dd --- /dev/null +++ b/sanei/sanei_magic.c @@ -0,0 +1,1941 @@ +/* + * sanei_magic - Image processing functions for despeckle, deskew, and autocrop + + Copyright (C) 2009 m. allan noah + + This file is part of the SANE package. + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program 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 + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, + MA 02111-1307, USA. + + As a special exception, the authors of SANE give permission for + additional uses of the libraries contained in this release of SANE. + + The exception is that, if you link a SANE library with other files + to produce an executable, this does not by itself cause the + resulting executable to be covered by the GNU General Public + License. Your use of that executable is in no way restricted on + account of linking the SANE library code into it. + + This exception does not, however, invalidate any other reasons why + the executable file might be covered by the GNU General Public + License. + + If you submit changes to SANE to the maintainers to be included in + a subsequent release, you agree by submitting the changes that + those changes may be distributed with this exception intact. + + If you write modifications of your own for SANE, it is your choice + whether to permit this exception to apply to your modifications. + If you do not wish that, delete this exception notice. + */ + +#include "../include/sane/config.h" + +#include +#include +#include +#include +#include + +#define BACKEND_NAME sanei_magic /* name of this module for debugging */ + +#include "../include/sane/sane.h" +#include "../include/sane/sanei_debug.h" +#include "../include/sane/sanei_magic.h" + +/* prototypes for utility functions defined at bottom of file */ +int * sanei_magic_getTransY ( + SANE_Parameters * params, int dpi, SANE_Byte * buffer, int top); + +int * sanei_magic_getTransX ( + SANE_Parameters * params, int dpi, SANE_Byte * buffer, int left); + +static SANE_Status getTopEdge (int width, int height, int resolution, + int * buff, double * finSlope, int * finXInter, int * finYInter); + +static SANE_Status getLeftEdge (int width, int height, int * top, int * bot, + double slope, int * finXInter, int * finYInter); + +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); + +void +sanei_magic_init( void ) +{ + DBG_INIT(); +} + +/* find small spots and replace them with image background color */ +SANE_Status +sanei_magic_despeck (SANE_Parameters * params, SANE_Byte * buffer, + SANE_Int diam) +{ + + SANE_Status ret = SANE_STATUS_GOOD; + + int pw = params->pixels_per_line; + int bw = params->bytes_per_line; + int h = params->lines; + int bt = bw*h; + + int i,j,k,l,n; + + DBG (10, "sanei_magic_despeck: start\n"); + + if(params->format == SANE_FRAME_RGB){ + + for(i=bw; iformat == SANE_FRAME_GRAY && params->depth == 8){ + for(i=bw; iformat == SANE_FRAME_GRAY && params->depth == 1){ + for(i=bw; i> (7-(j+l)%8) & 1; + } + } + + if(!curr) + continue; + + /*loop over rows and columns around window */ + for(k=-1; k> (7-(j+l)%8) & 1; + + if(hits) + break; + } + } + + /*no hits, overwrite with white*/ + if(!hits){ + for(k=0; kpixels_per_line; + int height = params->lines; + + int * topBuf = NULL, * botBuf = NULL; + int * leftBuf = NULL, * rightBuf = NULL; + + int topCount = 0, botCount = 0; + int leftCount = 0, rightCount = 0; + + int i; + + DBG (10, "sanei_magic_findEdges: start\n"); + + /* get buffers to find sides and bottom */ + topBuf = sanei_magic_getTransY(params,dpiY,buffer,1); + if(!topBuf){ + DBG (5, "sanei_magic_findEdges: no topBuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + botBuf = sanei_magic_getTransY(params,dpiY,buffer,0); + if(!botBuf){ + DBG (5, "sanei_magic_findEdges: no botBuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + leftBuf = sanei_magic_getTransX(params,dpiX,buffer,1); + if(!leftBuf){ + DBG (5, "sanei_magic_findEdges: no leftBuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + rightBuf = sanei_magic_getTransX(params,dpiX,buffer,0); + if(!rightBuf){ + DBG (5, "sanei_magic_findEdges: no rightBuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + /* loop thru left and right lists, look for top and bottom extremes */ + *top = height; + for(i=0; i leftBuf[i]){ + if(*top > i){ + *top = i; + } + + topCount++; + if(topCount > 3){ + break; + } + } + else{ + topCount = 0; + *top = height; + } + } + + *bot = -1; + for(i=height-1; i>=0; i--){ + if(rightBuf[i] > leftBuf[i]){ + if(*bot < i){ + *bot = i; + } + + botCount++; + if(botCount > 3){ + break; + } + } + else{ + botCount = 0; + *bot = -1; + } + } + + /* could not find top/bot edges */ + if(*top > *bot){ + DBG (5, "sanei_magic_findEdges: bad t/b edges\n"); + ret = SANE_STATUS_UNSUPPORTED; + goto cleanup; + } + + /* loop thru top and bottom lists, look for l and r extremes + * NOTE: We dont look above the top or below the bottom found previously. + * This prevents issues with adf scanners that pad the image after the + * paper runs out (usually with white) */ + DBG (5, "sanei_magic_findEdges: bb0:%d tb0:%d b:%d t:%d\n", + botBuf[0], topBuf[0], *bot, *top); + + *left = width; + for(i=0; i topBuf[i] && (botBuf[i]-10 < *bot || topBuf[i]+10 > *top)){ + if(*left > i){ + *left = i; + } + + leftCount++; + if(leftCount > 3){ + break; + } + } + else{ + leftCount = 0; + *left = width; + } + } + + *right = -1; + for(i=width-1; i>=0; i--){ + if(botBuf[i] > topBuf[i] && (botBuf[i]-10 < *bot || topBuf[i]+10 > *top)){ + if(*right < i){ + *right = i; + } + + rightCount++; + if(rightCount > 3){ + break; + } + } + else{ + rightCount = 0; + *right = -1; + } + } + + /* could not find left/right edges */ + if(*left > *right){ + DBG (5, "sanei_magic_findEdges: bad l/r edges\n"); + ret = SANE_STATUS_UNSUPPORTED; + goto cleanup; + } + + DBG (15, "sanei_magic_findEdges: t:%d b:%d l:%d r:%d\n", + *top,*bot,*left,*right); + + cleanup: + if(topBuf) + free(topBuf); + if(botBuf) + free(botBuf); + if(leftBuf) + free(leftBuf); + if(rightBuf) + free(rightBuf); + + DBG (10, "sanei_magic_findEdges: finish\n"); + return ret; +} + +/* crop image to given size. updates params with new dimensions */ +SANE_Status +sanei_magic_crop(SANE_Parameters * params, SANE_Byte * buffer, + int top, int bot, int left, int right) +{ + + SANE_Status ret = SANE_STATUS_GOOD; + + int bwidth = params->bytes_per_line; + + int pixels = 0; + int bytes = 0; + unsigned char * line = NULL; + int pos = 0, i; + + DBG (10, "sanei_magic_crop: start\n"); + + /*convert left and right to bytes, figure new byte and pixel width */ + if(params->format == SANE_FRAME_RGB){ + pixels = right-left; + bytes = pixels * 3; + left *= 3; + right *= 3; + } + else if(params->format == SANE_FRAME_GRAY && params->depth == 8){ + pixels = right-left; + bytes = right-left; + } + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + left /= 8; + right = (right+7)/8; + bytes = right-left; + pixels = bytes * 8; + } + else{ + DBG (5, "sanei_magic_crop: unsupported format/depth\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + DBG (15, "sanei_magic_crop: l:%d r:%d p:%d b:%d\n",left,right,pixels,bytes); + + line = malloc(bytes); + if(!line){ + DBG (5, "sanei_magic_crop: no line\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + for(i=top; ilines = bot-top; + params->pixels_per_line = pixels; + params->bytes_per_line = bytes; + + cleanup: + if(line) + free(line); + + DBG (10, "sanei_magic_crop: finish\n"); + return ret; +} + +/* find angle of media rotation against image background */ +SANE_Status +sanei_magic_findSkew(SANE_Parameters * params, SANE_Byte * buffer, + int dpiX, int dpiY, int * centerX, int * centerY, double * finSlope) +{ + SANE_Status ret = SANE_STATUS_GOOD; + + int pwidth = params->pixels_per_line; + int height = params->lines; + + double TSlope = 0; + int TXInter = 0; + int TYInter = 0; + double TSlopeHalf = 0; + int TOffsetHalf = 0; + + double LSlope = 0; + int LXInter = 0; + int LYInter = 0; + double LSlopeHalf = 0; + int LOffsetHalf = 0; + + int rotateX = 0; + int rotateY = 0; + + int * topBuf = NULL, * botBuf = NULL; + + DBG (10, "sanei_magic_findSkew: start\n"); + + dpiX=dpiX; + + /* get buffers for edge detection */ + topBuf = sanei_magic_getTransY(params,dpiY,buffer,1); + if(!topBuf){ + DBG (5, "sanei_magic_findSkew: cant gTY\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + botBuf = sanei_magic_getTransY(params,dpiY,buffer,0); + if(!botBuf){ + DBG (5, "sanei_magic_findSkew: cant gTY\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + /* find best top line */ + ret = getTopEdge (pwidth, height, dpiY, topBuf, + &TSlope, &TXInter, &TYInter); + if(ret){ + DBG(5,"sanei_magic_findSkew: gTE error: %d",ret); + goto cleanup; + } + DBG(15,"top: %04.04f %d %d\n",TSlope,TXInter,TYInter); + + /* slope is too shallow, don't want to divide by 0 */ + if(fabs(TSlope) < 0.0001){ + DBG(15,"sanei_magic_findSkew: slope too shallow: %0.08f\n",TSlope); + ret = SANE_STATUS_UNSUPPORTED; + goto cleanup; + } + + /* find best left line, perpendicular to top line */ + LSlope = (double)-1/TSlope; + ret = getLeftEdge (pwidth, height, topBuf, botBuf, LSlope, + &LXInter, &LYInter); + if(ret){ + DBG(5,"sanei_magic_findSkew: gLE error: %d",ret); + goto cleanup; + } + DBG(15,"sanei_magic_findSkew: left: %04.04f %d %d\n",LSlope,LXInter,LYInter); + + /* find point about which to rotate */ + TSlopeHalf = tan(atan(TSlope)/2); + TOffsetHalf = LYInter; + DBG(15,"sanei_magic_findSkew: top half: %04.04f %d\n",TSlopeHalf,TOffsetHalf); + + LSlopeHalf = tan((atan(LSlope) + ((LSlope < 0)?-M_PI_2:M_PI_2))/2); + LOffsetHalf = - LSlopeHalf * TXInter; + DBG(15,"sanei_magic_findSkew: left half: %04.04f %d\n",LSlopeHalf,LOffsetHalf); + + rotateX = (LOffsetHalf-TOffsetHalf) / (TSlopeHalf-LSlopeHalf); + rotateY = TSlopeHalf * rotateX + TOffsetHalf; + DBG(15,"sanei_magic_findSkew: rotate: %d %d\n",rotateX,rotateY); + + *centerX = rotateX; + *centerY = rotateY; + *finSlope = TSlope; + + cleanup: + if(topBuf) + free(topBuf); + if(botBuf) + free(botBuf); + + DBG (10, "sanei_magic_findSkew: finish\n"); + return ret; +} + +/* function to do a simple rotation by a given slope, around + * a given point. The point can be outside of image to get + * proper edge alignment. Unused areas filled with bg color + * FIXME: Do in-place rotation to save memory */ +SANE_Status +sanei_magic_rotate (SANE_Parameters * params, SANE_Byte * buffer, + int centerX, int centerY, double slope, int bg_color) +{ + + SANE_Status ret = SANE_STATUS_GOOD; + + double slopeRad = -atan(slope); + double slopeSin = sin(slopeRad); + double slopeCos = cos(slopeRad); + + int pwidth = params->pixels_per_line; + int bwidth = params->bytes_per_line; + int height = params->lines; + int depth = 1; + + unsigned char * outbuf; + int i, j, k; + + DBG(10,"sanei_magic_rotate: start: %d %d\n",centerX,centerY); + + outbuf = malloc(bwidth*height); + if(!outbuf){ + DBG(15,"sanei_magic_rotate: no outbuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + if(params->format == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + if(params->format == SANE_FRAME_RGB) + depth = 3; + + memset(outbuf,bg_color,bwidth*height); + + for (i=0; i= pwidth) + continue; + + sourceY = centerY + (int)(-shiftY * slopeCos + shiftX * slopeSin); + if (sourceY < 0 || sourceY >= height) + continue; + + for (k=0; kformat == SANE_FRAME_GRAY && params->depth == 1){ + + if(bg_color) + bg_color = 0xff; + + memset(outbuf,bg_color,bwidth*height); + + for (i=0; i= pwidth) + continue; + + sourceY = centerY + (int)(-shiftY * slopeCos + shiftX * slopeSin); + if (sourceY < 0 || sourceY >= height) + continue; + + /* wipe out old bit */ + outbuf[i*bwidth + j/8] &= ~(1 << (7-(j%8))); + + /* fill in new bit */ + outbuf[i*bwidth + j/8] |= + ((buffer[sourceY*bwidth + sourceX/8] + >> (7-(sourceX%8))) & 1) << (7-(j%8)); + } + } + } + else{ + DBG (5, "sanei_magic_rotate: unsupported format/depth\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + memcpy(buffer,outbuf,bwidth*height); + + cleanup: + + if(outbuf) + free(outbuf); + + DBG(10,"sanei_magic_rotate: finish\n"); + + return 0; +} + +SANE_Status +sanei_magic_isBlank (SANE_Parameters * params, SANE_Byte * buffer, + double thresh) +{ + SANE_Status ret = SANE_STATUS_GOOD; + double imagesum = 0; + int i, j; + + DBG(10,"sanei_magic_isBlank: start: %f\n",thresh); + + /*convert thresh from percent (0-100) to 0-1 range*/ + thresh /= 100; + + if(params->format == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + /* loop over all rows, find density of each */ + for(i=0; ilines; i++){ + int rowsum = 0; + SANE_Byte * ptr = buffer + params->bytes_per_line*i; + + /* loop over all columns, sum the 'darkness' of the pixels */ + for(j=0; jbytes_per_line; j++){ + rowsum += 255 - ptr[j]; + } + + imagesum += (double)rowsum/params->bytes_per_line/255; + } + + } + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + + /* loop over all rows, find density of each */ + for(i=0; ilines; i++){ + int rowsum = 0; + SANE_Byte * ptr = buffer + params->bytes_per_line*i; + + /* loop over all columns, sum the pixels */ + for(j=0; jpixels_per_line; j++){ + rowsum += ptr[j/8] >> (7-(j%8)) & 1; + } + + imagesum += (double)rowsum/params->pixels_per_line; + } + + } + else{ + DBG (5, "sanei_magic_isBlank: unsupported format/depth\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + DBG (5, "sanei_magic_isBlank: sum:%f lines:%d thresh:%f density:%f\n", + imagesum,params->lines,thresh,imagesum/params->lines); + + if(imagesum/params->lines <= thresh){ + DBG (5, "sanei_magic_isBlank: blank!\n"); + ret = SANE_STATUS_NO_DOCS; + } + + cleanup: + + DBG(10,"sanei_magic_isBlank: finish\n"); + + return ret; +} + +/* Divide the image into 1/2 inch squares, skipping a 1/4 inch + * margin on all sides. If all squares are under the user's density, + * signal our caller to skip the image entirely, by returning + * SANE_STATUS_NO_DOCS */ +SANE_Status +sanei_magic_isBlank2 (SANE_Parameters * params, SANE_Byte * buffer, + int dpiX, int dpiY, double thresh) +{ + int xb,yb,x,y; + + /* .25 inch, rounded down to 8 pixel */ + int xquarter = dpiX/4/8*8; + int yquarter = dpiY/4/8*8; + int xhalf = xquarter*2; + int yhalf = yquarter*2; + int blockpix = xhalf*yhalf; + int xblocks = (params->pixels_per_line-xhalf)/xhalf; + int yblocks = (params->lines-yhalf)/yhalf; + + /*convert thresh from percent (0-100) to 0-1 range*/ + thresh /= 100; + + DBG (10, "sanei_magic_isBlank2: start %d %d %f %d\n",xhalf,yhalf,thresh,blockpix); + + if(params->depth == 8 && + (params->format == SANE_FRAME_RGB || params->format == SANE_FRAME_GRAY) + ){ + + int Bpp = params->format == SANE_FRAME_RGB ? 3 : 1; + + for(yb=0; ybbytes_per_line + + (xquarter + xb*xhalf) * Bpp; + SANE_Byte * ptr = buffer + offset; + + /*count darkness of pix in this row*/ + int rowsum = 0; + + for(x=0; x thresh){ + DBG (15, "sanei_magic_isBlank2: not blank %f %d %d\n", blocksum/yhalf, yb, xb); + return SANE_STATUS_GOOD; + } + DBG (20, "sanei_magic_isBlank2: block blank %f %d %d\n", blocksum/yhalf, yb, xb); + } + } + } + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + + for(yb=0; ybbytes_per_line + + (xquarter + xb*xhalf) / 8; + SANE_Byte * ptr = buffer + offset; + + /*count darkness of pix in this row*/ + int rowsum = 0; + + for(x=0; x> (7-(x%8)) & 1; + } + + blocksum += (double)rowsum/xhalf; + } + + /* block was darker than thresh, keep image */ + if(blocksum/yhalf > thresh){ + DBG (15, "sanei_magic_isBlank2: not blank %f %d %d\n", blocksum/yhalf, yb, xb); + return SANE_STATUS_GOOD; + } + DBG (20, "sanei_magic_isBlank2: block blank %f %d %d\n", blocksum/yhalf, yb, xb); + } + } + } + else{ + DBG (5, "sanei_magic_isBlank2: unsupported format/depth\n"); + return SANE_STATUS_INVAL; + } + + DBG (10, "sanei_magic_isBlank2: returning blank\n"); + return SANE_STATUS_NO_DOCS; +} + +SANE_Status +sanei_magic_findTurn(SANE_Parameters * params, SANE_Byte * buffer, + int dpiX, int dpiY, int * angle) +{ + SANE_Status ret = SANE_STATUS_GOOD; + int i, j, k; + int depth = 1; + int htrans=0, vtrans=0; + int htot=0, vtot=0; + + DBG(10,"sanei_magic_findTurn: start\n"); + + if(params->format == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + if(params->format == SANE_FRAME_RGB) + depth = 3; + + /* loop over some rows, count segment lengths */ + for(i=0; ilines; i+=dpiY/20){ + SANE_Byte * ptr = buffer + params->bytes_per_line*i; + int color = 0; + int len = 0; + int sum = 0; + + /* loop over all columns */ + for(j=0; jpixels_per_line; j++){ + int curr = 0; + + /*convert color to gray*/ + for (k=0; k 156)?0:color; + + /*count segment length*/ + if(curr != color || j==params->pixels_per_line-1){ + sum += len * len/5; + len = 0; + color = curr; + } + else{ + len++; + } + } + + htot++; + htrans += (double)sum/params->pixels_per_line; + } + + /* loop over some cols, count dark vs light transitions */ + for(i=0; ipixels_per_line; i+=dpiX/20){ + SANE_Byte * ptr = buffer + i*depth; + int color = 0; + int len = 0; + int sum = 0; + + /* loop over all rows */ + for(j=0; jlines; j++){ + int curr = 0; + + /*convert color to gray*/ + for (k=0; kbytes_per_line+k]; + } + curr /= depth; + + /*convert gray to binary (with hysteresis) */ + curr = (curr < 100)?1: + (curr > 156)?0:color; + + /*count segment length*/ + if(curr != color || j==params->lines-1){ + sum += len * len/5; + len = 0; + color = curr; + } + else{ + len++; + } + } + + vtot++; + vtrans += (double)sum/params->lines; + } + + } + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + + /* loop over some rows, count segment lengths */ + for(i=0; ilines; i+=dpiY/30){ + SANE_Byte * ptr = buffer + params->bytes_per_line*i; + int color = 0; + int len = 0; + int sum = 0; + + /* loop over all columns */ + for(j=0; jpixels_per_line; j++){ + int curr = ptr[j/8] >> (7-(j%8)) & 1; + + /*count segment length*/ + if(curr != color || j==params->pixels_per_line-1){ + sum += len * len/5; + len = 0; + color = curr; + } + else{ + len++; + } + } + + htot++; + htrans += (double)sum/params->pixels_per_line; + } + + /* loop over some cols, count dark vs light transitions */ + for(i=0; ipixels_per_line; i+=dpiX/30){ + SANE_Byte * ptr = buffer; + int color = 0; + int len = 0; + int sum = 0; + + /* loop over all rows */ + for(j=0; jlines; j++){ + int curr = ptr[j*params->bytes_per_line + i/8] >> (7-(i%8)) & 1; + + /*count segment length*/ + if(curr != color || j==params->lines-1){ + sum += len * len/5; + len = 0; + color = curr; + } + else{ + len++; + } + } + + vtot++; + vtrans += (double)sum/params->lines; + } + + } + else{ + DBG (5, "sanei_magic_findTurn: unsupported format/depth\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + DBG (10, "sanei_magic_findTurn: vtrans=%d vtot=%d vfrac=%f htrans=%d htot=%d hfrac=%f\n", + vtrans, vtot, (double)vtrans/vtot, htrans, htot, (double)htrans/htot + ); + + if((double)vtrans/vtot > (double)htrans/htot){ + DBG (10, "sanei_magic_findTurn: suggest turning 90\n"); + *angle = 90; + } + + cleanup: + + DBG(10,"sanei_magic_findTurn: finish\n"); + + return ret; +} + +/* FIXME: Do in-place rotation to save memory */ +SANE_Status +sanei_magic_turn(SANE_Parameters * params, SANE_Byte * buffer, + int angle) +{ + SANE_Status ret = SANE_STATUS_GOOD; + int opwidth, ipwidth = params->pixels_per_line; + int obwidth, ibwidth = params->bytes_per_line; + int oheight, iheight = params->lines; + int depth = 1; + + unsigned char * outbuf = NULL; + int i, j, k; + + DBG(10,"sanei_magic_turn: start %d\n",angle); + + if(params->format == SANE_FRAME_RGB) + depth = 3; + + /*clean angle and convert to 0-3*/ + angle = (angle % 360) / 90; + + /*figure size of output image*/ + switch(angle){ + case 1: + case 3: + opwidth = iheight; + oheight = ipwidth; + + /*gray and color, 1 or 3 bytes per pixel*/ + if ( params->format == SANE_FRAME_RGB + || (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + obwidth = opwidth*depth; + } + + /*clamp binary to byte width. must be <= input image*/ + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + obwidth = opwidth/8; + opwidth = obwidth*8; + } + + else{ + DBG(10,"sanei_magic_turn: bad params\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + break; + + case 2: + opwidth = ipwidth; + obwidth = ibwidth; + oheight = iheight; + break; + + default: + DBG(10,"sanei_magic_turn: no turn\n"); + goto cleanup; + } + + /*get output image buffer*/ + outbuf = malloc(obwidth*oheight); + if(!outbuf){ + DBG(15,"sanei_magic_turn: no outbuf\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + /*turn color & gray image*/ + if(params->format == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + switch (angle) { + + /*rotate 90 clockwise*/ + case 1: + for (i=0; iformat == SANE_FRAME_GRAY && params->depth == 1){ + + switch (angle) { + + /*rotate 90 clockwise*/ + case 1: + for (i=0; i> (7-(i%8)) & 1; + + unsigned char mask = 1 << (7-(j%8)); + + if(curr){ + outbuf[i*obwidth + j/8] |= mask; + } + else{ + outbuf[i*obwidth + j/8] &= (~mask); + } + + } + } + break; + + /*rotate 180 clockwise*/ + case 2: + for (i=0; i> (j%8) & 1; + + unsigned char mask = 1 << (7-(j%8)); + + if(curr){ + outbuf[i*obwidth + j/8] |= mask; + } + else{ + outbuf[i*obwidth + j/8] &= (~mask); + } + + } + } + break; + + /*rotate 270 clockwise*/ + case 3: + for (i=0; i> (i%8) & 1; + + unsigned char mask = 1 << (7-(j%8)); + + if(curr){ + outbuf[i*obwidth + j/8] |= mask; + } + else{ + outbuf[i*obwidth + j/8] &= (~mask); + } + + } + } + break; + } /*end switch*/ + } + + else{ + DBG (5, "sanei_magic_turn: unsupported format/depth\n"); + ret = SANE_STATUS_INVAL; + goto cleanup; + } + + /*copy output back into input buffer*/ + memcpy(buffer,outbuf,obwidth*oheight); + + /*update input params*/ + params->pixels_per_line = opwidth; + params->bytes_per_line = obwidth; + params->lines = oheight; + + cleanup: + + if(outbuf) + free(outbuf); + + DBG(10,"sanei_magic_turn: finish\n"); + + return ret; +} + +/* Utility functions, not used outside this file */ + +/* Repeatedly call getLine to find the best range of slope and offset. + * Shift the ranges thru 4 different positions to avoid splitting data + * across multiple bins (false positive). Home-in on the most likely upper + * line of the paper inside the image. Return the 'best' edge. */ +static SANE_Status +getTopEdge(int width, int height, int resolution, + int * buff, double * finSlope, int * finXInter, int * finYInter) +{ + SANE_Status ret = SANE_STATUS_GOOD; + + int slopes = 31; + int offsets = 31; + double maxSlope = 1; + double minSlope = -1; + int maxOffset = resolution; + int minOffset = -resolution; + + double topSlope = 0; + int topOffset = 0; + int topDensity = 0; + + int i,j; + int pass = 0; + + DBG(10,"getTopEdge: start\n"); + + while(pass++ < 7){ + double sStep = (maxSlope-minSlope)/slopes; + int oStep = (maxOffset-minOffset)/offsets; + + double slope = 0; + int offset = 0; + int density = 0; + int go = 0; + + topSlope = 0; + topOffset = 0; + topDensity = 0; + + /* find lines 4 times with slightly moved params, + * to bypass binning errors, highest density wins */ + for(i=0;i<2;i++){ + double sStep2 = sStep*i/2; + for(j=0;j<2;j++){ + int oStep2 = oStep*j/2; + ret = getLine(height,width,buff,slopes,minSlope+sStep2,maxSlope+sStep2,offsets,minOffset+oStep2,maxOffset+oStep2,&slope,&offset,&density); + if(ret){ + DBG(5,"getTopEdge: getLine error %d\n",ret); + return ret; + } + DBG(15,"getTopEdge: %d %d %+0.4f %d %d\n",i,j,slope,offset,density); + + if(density > topDensity){ + topSlope = slope; + topOffset = offset; + topDensity = density; + } + } + } + + DBG(15,"getTopEdge: ok %+0.4f %d %d\n",topSlope,topOffset,topDensity); + + /* did not find anything promising on first pass, + * give up instead of fixating on some small, pointless feature */ + if(pass == 1 && topDensity < width/5){ + DBG(5,"getTopEdge: density too small %d %d\n",topDensity,width); + topOffset = 0; + topSlope = 0; + break; + } + + /* if slope can zoom in some more, do so. */ + if(sStep >= 0.0001){ + minSlope = topSlope - sStep; + maxSlope = topSlope + sStep; + go = 1; + } + + /* if offset can zoom in some more, do so. */ + if(oStep){ + minOffset = topOffset - oStep; + maxOffset = topOffset + oStep; + go = 1; + } + + /* cannot zoom in more, bail out */ + if(!go){ + break; + } + + DBG(15,"getTopEdge: zoom: %+0.4f %+0.4f %d %d\n", + minSlope,maxSlope,minOffset,maxOffset); + } + + /* topOffset is in the center of the image, + * convert to x and y intercept */ + if(topSlope != 0){ + *finYInter = topOffset - topSlope * width/2; + *finXInter = *finYInter / -topSlope; + *finSlope = topSlope; + } + else{ + *finYInter = 0; + *finXInter = 0; + *finSlope = 0; + } + + DBG(10,"getTopEdge: finish\n"); + + return 0; +} + +/* Loop thru a transition array, and use a simplified Hough transform + * to divide likely edges into a 2-d array of bins. Then weight each + * bin based on its angle and offset. Return the 'best' bin. */ +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) +{ + SANE_Status ret = 0; + + int ** lines = NULL; + int i, j; + int rise, run; + double slope; + int offset; + int sIndex, oIndex; + int hWidth = width/2; + + double * slopeCenter = NULL; + int * slopeScale = NULL; + double * offsetCenter = NULL; + int * offsetScale = NULL; + + int maxDensity = 1; + double absMaxSlope = fabs(maxSlope); + double absMinSlope = fabs(minSlope); + int absMaxOffset = abs(maxOffset); + int absMinOffset = abs(minOffset); + + DBG(10,"getLine: start %+0.4f %+0.4f %d %d\n", + minSlope,maxSlope,minOffset,maxOffset); + + /*silence compiler*/ + height = height; + + if(absMaxSlope < absMinSlope) + absMaxSlope = absMinSlope; + + if(absMaxOffset < absMinOffset) + absMaxOffset = absMinOffset; + + /* build an array of pretty-print values for slope */ + slopeCenter = calloc(slopes,sizeof(double)); + if(!slopeCenter){ + DBG(5,"getLine: cant load slopeCenter\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + /* build an array of scaling factors for slope */ + slopeScale = calloc(slopes,sizeof(int)); + if(!slopeScale){ + DBG(5,"getLine: cant load slopeScale\n"); + ret = SANE_STATUS_NO_MEM; + goto cleanup; + } + + for(j=0;j= maxSlope || slope < minSlope) + continue; + + /* offset in center of width, not y intercept! */ + offset = slope * hWidth + buff[i] - slope * i; + if(offset >= maxOffset || offset < minOffset) + continue; + + sIndex = (slope - minSlope) * slopes/(maxSlope-minSlope); + if(sIndex >= slopes) + continue; + + oIndex = (offset - minOffset) * offsets/(maxOffset-minOffset); + if(oIndex >= offsets) + continue; + + lines[sIndex][oIndex]++; + } + } + + /* go thru array, and find most dense line (highest number) */ + for(i=0;i maxDensity) + maxDensity = lines[i][j]; + } + } + + DBG(15,"getLine: maxDensity %d\n",maxDensity); + + *finSlope = 0; + *finOffset = 0; + *finDensity = 0; + + /* go thru array, and scale densities to % of maximum, plus adjust for + * prefered (smaller absolute value) slope and offset */ + for(i=0;i *finDensity){ + *finDensity = lines[i][j]; + *finSlope = slopeCenter[i]; + *finOffset = offsetCenter[j]; + } + } + } + + if(0){ + fprintf(stderr,"offsetCenter: "); + for(j=0;j txi){ + topXInter = txi; + topYInter = tyi; + } + + leftCount++; + if(leftCount > 5){ + break; + } + } + else{ + topXInter = width; + topYInter = 0; + leftCount = 0; + } + } + + botXInter = width; + botYInter = 0; + leftCount = 0; + + for(i=0;i -1){ + + int byi = bot[i] - (slope * i); + int bxi = byi/-slope; + + if(botXInter > bxi){ + botXInter = bxi; + botYInter = byi; + } + + leftCount++; + if(leftCount > 5){ + break; + } + } + else{ + botXInter = width; + botYInter = 0; + leftCount = 0; + } + } + + if(botXInter < topXInter){ + *finXInter = botXInter; + *finYInter = botYInter; + } + else{ + *finXInter = topXInter; + *finYInter = topYInter; + } + + DBG(10,"getEdgeSlope: finish\n"); + + return 0; +} + +/* Loop thru the image and look for first color change in each column. + * Return a malloc'd array. Caller is responsible for freeing. */ +int * +sanei_magic_getTransY ( + SANE_Parameters * params, int dpi, SANE_Byte * buffer, int top) +{ + int * buff; + + int i, j, k; + int winLen = 9; + + int width = params->pixels_per_line; + int height = params->lines; + int depth = 1; + + /* defaults for bottom-up */ + int firstLine = height-1; + int lastLine = -1; + int direction = -1; + + DBG (10, "sanei_magic_getTransY: start\n"); + + /* override for top-down */ + if(top){ + firstLine = 0; + lastLine = height; + direction = 1; + } + + /* build output and preload with impossible value */ + buff = calloc(width,sizeof(int)); + if(!buff){ + DBG (5, "sanei_magic_getTransY: no buff\n"); + return NULL; + } + for(i=0; iformat == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + if(params->format == SANE_FRAME_RGB) + depth = 3; + + /* loop over all columns, find first transition */ + for(i=0; i= height){ + farLine = firstLine; + } + if(nearLine < 0 || nearLine >= height){ + nearLine = firstLine; + } + + for(k=0; k 50*winLen*depth - near*40/255){ + buff[i] = j; + break; + } + } + } + } + + else if(params->format == SANE_FRAME_GRAY && params->depth == 1){ + + int near = 0; + + for(i=0; i> (7-(i%8)) & 1; + + /* move */ + for(j=firstLine+direction; j!=lastLine; j+=direction){ + if((buffer[(j*width+i)/8] >> (7-(i%8)) & 1) != near){ + buff[i] = j; + break; + } + } + } + } + + /* some other format? */ + else{ + DBG (5, "sanei_magic_getTransY: unsupported format/depth\n"); + free(buff); + return NULL; + } + + /* ignore transitions with few neighbors within .5 inch */ + for(i=0;ibytes_per_line; + int width = params->pixels_per_line; + int height = params->lines; + int depth = 1; + + /* defaults for right-first */ + int firstCol = width-1; + int lastCol = -1; + int direction = -1; + + DBG (10, "sanei_magic_getTransX: start\n"); + + /* override for left-first*/ + if(left){ + firstCol = 0; + lastCol = width; + direction = 1; + } + + /* build output and preload with impossible value */ + buff = calloc(height,sizeof(int)); + if(!buff){ + DBG (5, "sanei_magic_getTransX: no buff\n"); + return NULL; + } + for(i=0; iformat == SANE_FRAME_RGB || + (params->format == SANE_FRAME_GRAY && params->depth == 8) + ){ + + if(params->format == SANE_FRAME_RGB) + depth = 3; + + /* loop over all columns, find first transition */ + for(i=0; i= width){ + farCol = firstCol; + } + if(nearCol < 0 || nearCol >= width){ + nearCol = firstCol; + } + + for(k=0; k 50*winLen*depth - near*40/255){ + buff[i] = j; + break; + } + } + } + } + + else if (params->format == SANE_FRAME_GRAY && params->depth == 1){ + + int near = 0; + + for(i=0; i> (7-(firstCol%8)) & 1; + + /* move */ + for(j=firstCol+direction; j!=lastCol; j+=direction){ + if((buffer[i*bwidth + j/8] >> (7-(j%8)) & 1) != near){ + buff[i] = j; + break; + } + } + } + } + + /* some other format? */ + else{ + DBG (5, "sanei_magic_getTransX: unsupported format/depth\n"); + free(buff); + return NULL; + } + + /* ignore transitions with few neighbors within .5 inch */ + for(i=0;i