/*libdmtx - Data Matrix Encoding/Decoding LibraryCopyright (C) 2006 Mike LaughtonThis library is free software; you can redistribute it and/ormodify it under the terms of the GNU Lesser General PublicLicense as published by the Free Software Foundation; eitherversion 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 ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNULesser General Public License for more details.You should have received a copy of the GNU Lesser General PublicLicense along with this library; if not, write to the Free SoftwareFoundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USAContact: mike@dragonflylogic.com*//* $Id: dmtxregion.c,v 1.14 2006/10/06 19:17:39 mblaughton Exp $ *//** * Scans through a line (vertical or horizontal) of the source image to * find and decode valid Data Matrix barcode regions. * * @param decode   pointer to DmtxDecode information struct * @param dir      scan direction (DmtxUp|DmtxRight) * @param lineNbr  number of image row or column to be scanned * @return         number of barcodes scanned */extern intdmtxScanLine(DmtxDecode *decode, DmtxDirection dir, int lineNbr){   int              success;   DmtxJumpScan     jumpScan;   DmtxEdgeScan     edgeScan;   DmtxEdgeFollower followLeft, followRight;   DmtxMatrixRegion matrixRegion;   assert(decode->image.width > 0 && decode->image.height > 0);   assert(dir == DmtxDirUp || dir == DmtxDirRight);   // The outer loop steps through a full row or column of the source   // image looking for regions that alternate between 2 colors.  This   // alternating pattern is what you would expect if you took a pixel-wide   // slice of a Data Matrix barcode image.  libdmtx refers to these   // regions as "jump regions" since the color value is seen as jumping   // back and forth across an imaginary middle color (or "edge").   // Initialize jump scan to cover entire line   JumpScanInit(&jumpScan, dir, lineNbr, 0, (dir & DmtxDirHorizontal) ?         decode->image.width : decode->image.height);   // Loop once for each jump region candidate found on this line   while(JumpScanNextRegion(&jumpScan, decode) != DMTX_END_OF_RANGE) {      // Does this jump region meet necessary requirements?      if(!JumpRegionValid(&jumpScan.region))         continue;      // We now have a sufficiently-long region of 2 alternating colors.      // Next inspect each color boundary (or "edge") in this region to      // uncover finder bar candidates.      // Initialize edge scan to search within current jump region      EdgeScanInit(&edgeScan, &jumpScan);      // Loop once for each color edge found in this jump region      while(EdgeScanNextEdge(&edgeScan, decode, &(jumpScan.region.gradient)) != DMTX_END_OF_RANGE) {         // Finder bars are detected by tracing (or "following") an edge to         // the left and to the right of the current scan direction.  If         // the followers find edges that are sufficiently straight and         // long then they are pursued as valid finder bar candidates.         EdgeFollowerInit(&followLeft, &edgeScan, &(jumpScan.region.gradient), TurnCorner(dir, DMTX_TURN_CCW));         EdgeFollowerInit(&followRight, &edgeScan, &(jumpScan.region.gradient), TurnCorner(dir, DMTX_TURN_CW));         EdgeFollowerFollow(&followLeft, decode);         EdgeFollowerFollow(&followRight, decode);         // We now hold a rough trace of the finder bars that border 2         // adjacent sides of a Data Matrix region.  The following steps         // will refine that region by building a transformation matrix         // that maps input pixel coordinates to a rectangular (usually         // square) 2D space of predetermined dimensions.  This is done         // by capturing and tweaking a "chain" of input values that are         // inputs to the transformation matrix and its inverse.         MatrixRegionInit(&matrixRegion, &(jumpScan.region.gradient));         success = MatrixRegionAlignFinderBars(&matrixRegion, decode, &followLeft, &followRight);         if(!success)            continue;         success = MatrixRegionAlignTop(&matrixRegion, decode);         if(!success)            continue;         success = MatrixRegionAlignSide(&matrixRegion, decode);         if(!success)            continue;         // XXX When adding clipping functionality against previously         // scanned barcodes, this is a good place to add a test for         // collisions.  Although we tested for this early on in the jump         // region scan, the subsequent follower and alignment steps may         // have moved us into a collision with another matrix region.  A         // collision at this point is grounds for immediate failure.         success = MatrixRegionFindSize(&matrixRegion, decode);         if(!success)            continue;         success = PopulateArrayFromImage(&matrixRegion, decode);         if(!success)            continue;         success = DecodeRegion(&matrixRegion);         if(!success)            continue;         // We are now holding a valid, fully decoded Data Matrix barcode.         // Add this to the list of valid barcodes and continue searching         // for more.         if(decode && decode->finalCallback)            (*(decode->finalCallback))(&matrixRegion);         decode->matrix[decode->matrixCount++] = matrixRegion;         if((decode->option & DmtxSingleScanOnly) && decode->matrixCount > 0)            break;      }   }   return decode->matrixCount;}/** * Sets the location and boundaries of a region to be scanned. * * @param range    Pointer to target DmtxScanRange * @param dir      Line direction (DmtxDirUp|DmtxDirLeft|DmtxDirDown|DmtxDirRight) * @param lineNbr  Number of row or column in image * @param firstPos Offset of first pixel in scan range * @param lastPos  Offset of last pixel in scan range * @return void */static voidScanRangeSet(DmtxScanRange *range, DmtxDirection dir, int lineNbr, int firstPos, int lastPos){   memset(range, 0x00, sizeof(DmtxScanRange));   range->dir = dir;   range->lineNbr = lineNbr;   range->firstPos = firstPos;   range->lastPos = lastPos;}/** * XXX * @param dir XXX * @param turn XXX * @return XXX */static DmtxDirectionTurnCorner(DmtxDirection dir, int turn){   DmtxDirection newDir;   newDir = (turn == DMTX_TURN_CW) ? 0x0f & (dir >> 1) : 0x0f & (dir << 1);   return (newDir) ? newDir : (dir ^ 0x0f) & 0x09;}/** * Initializes jump scan variable boundaries and starting point.  Should * be called once per input line (row or column) prior to searching for * jump regions. * * @param jumpScan XXX * @param dir      XXX * @param lineNbr  XXX * @param start    XXX * @param length   XXX * @return void */static voidJumpScanInit(DmtxJumpScan *jumpScan, DmtxDirection dir, int lineNbr, int start, int length){   memset(jumpScan, 0x00, sizeof(DmtxJumpScan));   ScanRangeSet(&(jumpScan->range), dir, lineNbr, start, start + length - 1);   // Initialize "current" region to end at start of range   jumpScan->region.anchor2 = start;}/** * Zeros out *jumpRegion and repoints location to start the next region. * JumpScanInit() must be called before first call to JumpRegionIncrement(); * * @param jumpRegion XXX * @param range Pass range if initializing, NULL if incrementing * @return void */static voidJumpRegionIncrement(DmtxJumpRegion *jumpRegion){   int anchorTmp;   // NOTE: First time here will show jump->region.gradient.isDefined ==   // DMTX_FALSE due to initialization in JumpScanInit()   // Reuse the trailing same-colored pixels from the previous region as   // the leading part of this region if a gradient was established   anchorTmp = (jumpRegion->gradient.isDefined) ? jumpRegion->lastJump : jumpRegion->anchor2;   memset(jumpRegion, 0x00, sizeof(DmtxJumpRegion));   jumpRegion->anchor1 = anchorTmp;}/** * XXX * * @param jumpScan XXX * @param decode   XXX * @return offset | DMTX_END_OF_RANGE */// XXX THIS FUNCTION HAS NOT BEEN REWRITTEN YETstatic intJumpScanNextRegion(DmtxJumpScan *jumpScan, DmtxDecode *decode){   DmtxJumpRegion  *region;   DmtxScanRange   *range;   int             anchor1Offset, anchor2Offset;   float           colorDist;   float           offGradient, alongGradient;   DmtxColor3      cDist;   int             minMaxFlag;   float           aThird;   // XXX When adding clipping against previously scanned barcodes you will do a check:   // if first point is in an existing region then fast forward to after the existing region   // if non-first point hits a region then this defines the end of your jump region   region = &(jumpScan->region);   range = &(jumpScan->range);   if(region->anchor2 == range->lastPos)      return DMTX_END_OF_RANGE;   JumpRegionIncrement(region);   anchor1Offset = dmtxImageGetOffset(&(decode->image), jumpScan->range.dir, range->lineNbr, region->anchor1);   dmtxColor3FromPixel(&(region->gradient.color), &(decode->image.pxl[anchor1Offset]));   // For each pixel in the range   for(region->anchor2 = region->anchor1 + 1; region->anchor2 != range->lastPos; region->anchor2++) {      anchor2Offset = dmtxImageGetOffset(&(decode->image), jumpScan->range.dir, range->lineNbr, region->anchor2);      // Capture previous and current pixel color      region->gradient.colorPrev = region->gradient.color;      dmtxColor3FromPixel(&(region->gradient.color), &(decode->image.pxl[anchor2Offset]));      // Measure color distance from previous pixel color      dmtxColor3Sub(&cDist, &(region->gradient.color), &(region->gradient.colorPrev));      colorDist = dmtxColor3Mag(&cDist);      // If color distance is larger than image noise      if(colorDist > DMTX_MIN_JUMP_DISTANCE) {         // If gradient line does not exist then         if(!region->gradient.isDefined) {            // Create gradient line            region->gradient.ray.p = region->gradient.colorPrev;            region->gradient.ray.c = cDist;            dmtxColor3Norm(&(region->gradient.ray.c));            // Update tMax, tMin, and derived values            region->gradient.isDefined = 1;            region->gradient.tMin = 0; // XXX technically this is not necessary (already initialized)            region->gradient.tMax = dmtxDistanceAlongRay3(&(region->gradient.ray), &(region->gradient.color));            region->gradient.tMid = (region->gradient.tMin + region->gradient.tMax)/2.0;            minMaxFlag = 1; // Latest hit was on the high side            region->lastJump = region->anchor2; // XXX see, this is why the logic shouldn't be in two places         }         else { // Gradient line does exist            // Measure distance from current gradient line            offGradient = dmtxDistanceFromRay3(&(region->gradient.ray), &(region->gradient.color));            // If distance from gradient line is large            if(offGradient > DMTX_MAX_COLOR_DEVN) {               if(decode && decode->stepScanCallback)                  (*(decode->stepScanCallback))(decode, range, jumpScan);               return DMTX_SUCCESS;            }            else { // Distance from gradient line is small               // Update tMax, tMin (distance along gradient lines), and derived values if necessary               alongGradient = dmtxDistanceAlongRay3(&(region->gradient.ray), &(region->gradient.color));               if(alongGradient < region->gradient.tMin)                  region->gradient.tMin = alongGradient;               else if(alongGradient > region->gradient.tMax)                  region->gradient.tMax = alongGradient;               region->gradient.tMid = (region->gradient.tMin + region->gradient.tMax)/2.0;               // Record that another big jump occurred               // XXX this should probably record gradient direction shifts rather than big jumps               aThird = (region->gradient.tMax - region->gradient.tMin)/2.0;               if(((minMaxFlag == 1 && alongGradient < region->gradient.tMin + aThird) ||                     (minMaxFlag == -1 && alongGradient > region->gradient.tMax - aThird)) &&                     aThird > 5.0) {                  region->jumpCount++;                  region->lastJump = region->anchor2;                  minMaxFlag *= -1;               }            }         }      }   }   if(decode && decode->stepScanCallback)      (*(decode->stepScanCallback))(decode, range, jumpScan);   return DMTX_SUCCESS;}/** * Returns true if a jump region is determined to be valid, else false. * * @param jumpRegion XXX * @return jump region validity (true|false) */static intJumpRegionValid(DmtxJumpRegion *jumpRegion){   return (jumpRegion->jumpCount > DMTX_MIN_JUMP_COUNT &&           abs(jumpRegion->anchor2 - jumpRegion->anchor1) > DMTX_MIN_STEP_RANGE);}/** * XXX * * @param * @return void */static voidEdgeScanInit(DmtxEdgeScan *edgeScan, DmtxJumpScan *jumpScan){   memset(edgeScan, 0x00, sizeof(DmtxEdgeScan));   // Set edge scan range by starting with a copy of the jump scan's range   edgeScan->range = jumpScan->range;   edgeScan->range.firstPos = jumpScan->region.anchor1;   edgeScan->range.lastPos = jumpScan->region.anchor2 - 1;   // Initialize "current" edge to end at start of full jump scan range   edgeScan->edge.offset = edgeScan->edgeNext.offset = edgeScan->range.firstPos;