dmtxregion.c

Linux系统下,二维码生成源代码.希望对大家有所帮助.

/*
libdmtx - Data Matrix Encoding/Decoding Library
Copyright (C) 2006 Mike Laughton

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

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

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

Contact: [e-mail]
*/

/* $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 int
dmtxScanLine(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 void
ScanRangeSet(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 DmtxDirection
TurnCorner(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 void
JumpScanInit(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 void
JumpRegionIncrement(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 YET
static int
JumpScanNextRegion(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 int
JumpRegionValid(DmtxJumpRegion *jumpRegion)
{
   return (jumpRegion->jumpCount > DMTX_MIN_JUMP_COUNT &&
           abs(jumpRegion->anchor2 - jumpRegion->anchor1) > DMTX_MIN_STEP_RANGE);
}

/**
 * XXX
 *
 * @param
 * @return void
 */
static void
EdgeScanInit(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;