barCodeSensor.h

00001 // Plunger sensor type for bar-code based absolute position encoders.
00002 // This type of sensor uses an optical sensor that moves with the plunger
00003 // along a guide rail with printed bar codes along its length that encode
00004 // the absolute position at each point.  We figure the plunger position
00005 // by reading the bar code and decoding it into a position figure.
00006 //
00007 // The bar code has to be encoded in a specific format that we recognize.
00008 // We use a reflected Gray code, optically encoded in black/white pixel
00009 // patterns.  Each bit is represented by a fixed-width area.  Half the
00010 // pixels in every bit are white, and half are black.  A '0' bit is
00011 // represented by black pixels in the left half and white pixels in the
00012 // right half, and a '1' bit is white on the left and black on the right.
00013 // To read a bit, we identify the set of pixels covering the bit's fixed
00014 // area in the code, then we see if the left or right half is brighter.
00015 //
00016 // (This optical encoding scheme is based on Manchester coding, which is 
00017 // normally used in the context of serial protocols, but translates to 
00018 // bar codes straightforwardly.  Replace the serial protocol's time
00019 // dimension with the spatial dimension across the bar, and replace the
00020 // high/low wire voltage levels with white/black pixels.)
00021 //
00022 // Gray codes are ideal for this type of application.  Gray codes are
00023 // defined such that each code point differs in exactly one bit from each
00024 // adjacent code point.  This provides natural error correction when used
00025 // as a position scale, since any single-bit error will yield a code point 
00026 // reading that's only one spot off from the true position.  So a bit read
00027 // error acts like a reduction in precision.  Likewise, any time the sensor
00028 // is halfway between two code points, only one bit will be ambiguous, so
00029 // the reading will come out as one of points on either side of the true
00030 // position.  Finally, motion blur will have the same effect, of creating
00031 // ambiguity in the least significant bits, and thus giving us a reading
00032 // that's correct to as many bits as we can make out.
00033 //
00034 // The half-and-half optical coding also has good properties for our
00035 // purposes.  The fixed-width bit regions require essentially no CPU work
00036 // to find the bits, which is good because we're using a fairly slow CPU.
00037 // The half white/half black coding of each pixel makes every pixel 
00038 // self-relative in terms of brightness, so we don't need to figure the 
00039 // black and white thresholds globally for the whole image.  That makes 
00040 // the physical device engineering and installation easier because the 
00041 // software can tolerate a fairly wide range of lighting conditions.
00042 // 
00043 
00044 #ifndef _BARCODESENSOR_H_
00045 #define _BARCODESENSOR_H_
00046 
00047 #include "plunger.h"
00048 
00049 // Gray code to binary mapping for our special coding.  This is a custom
00050 // 7-bit code, minimum run length 6, 110 positions populated.  The minimum
00051 // run length is the minimum number of consecutive code points where each
00052 // bit must remain fixed.  For out optical coding, this defines the smallest
00053 // "island" size for a black or white bar horizontally.  Small features are
00054 // prone to light scattering that makes them appear gray on the sensor.
00055 // Larger features are less subject to scatter, making them easier to 
00056 // distinguish by brightness level.
00057 static const uint8_t grayToBin[] = {
00058    0,   1,  83,   2,  71, 100,  84,   3,  69, 102,  82, 128,  70, 101,  57,   4,    // 0-15
00059   35,  50,  36,  37,  86,  87,  85, 128,  34, 103,  21, 104, 128, 128,  20,   5,    // 16-31
00060   11, 128,  24,  25,  98,  99,  97,  40,  68,  67,  81,  80,  55,  54,  56,  41,    // 32-47
00061   10,  51,  23,  38, 128,  52, 128,  39,   9,  66,  22, 128,   8,  53,   7,   6,    // 48-63
00062   47,  14,  60, 128,  72,  15,  59,  16,  46,  91,  93,  92,  45, 128,  58,  17,    // 64-79
00063   48,  49,  61,  62,  73,  88,  74,  75,  33,  90, 106, 105,  32,  89,  19,  18,    // 80-95
00064   12,  13,  95,  26, 128,  28,  96,  27, 128, 128,  94,  79,  44,  29,  43,  42,    // 96-111
00065  128,  64, 128,  63, 110, 128, 109,  76, 128,  65, 107,  78,  31,  30, 108,  77     // 112-127
00066 };
00067 
00068 
00069 // Auto-exposure counter
00070 class BarCodeExposureCounter
00071 {
00072 public:
00073     BarCodeExposureCounter()
00074     {
00075         nDark = 0;
00076         nBright = 0;
00077         nZero = 0;
00078         nSat = 0;
00079     }
00080     
00081     inline void count(int pix)
00082     {
00083         if (pix <= 2)
00084             ++nZero;
00085         else if (pix < 12)
00086             ++nDark;
00087         else if (pix >= 253)
00088             ++nSat;
00089         else if (pix > 200)
00090             ++nBright;
00091     }
00092     
00093     int nDark;      // dark pixels
00094     int nBright;    // bright pixels
00095     int nZero;      // pixels at zero brightness
00096     int nSat;       // pixels at full saturation
00097 };
00098 
00099 
00100 // Base class for bar-code sensors
00101 //
00102 // This is a template class with template parameters for the bar
00103 // code pixel structure.  The bar code layout is fixed for a given 
00104 // sensor type.  We can assume fixed pixel sizes because we don't 
00105 // have to process arbitrary images.  We only have to read scales 
00106 // specially prepared for this application, so we can count on them
00107 // being printed at an exact size relative to the sensor pixels.
00108 //
00109 // nBits = Number of bits in the code 
00110 //
00111 // leftBarWidth = Width in pixels of delimiting left bar.  The code is 
00112 // delimited by a black bar on the "left" end, nearest pixel 0.  This 
00113 // gives the pixel width of the bar.
00114 //
00115 // leftBarMaxOfs = Maximum offset of the delimiting bar from the left
00116 // edge of the sensor (pixel 0), in pixels
00117 //
00118 // bitWidth = Width of each bit in pixels.  This is the width of the
00119 // full bit, including both "half bits" - it's the full white/black or 
00120 // black/white pattern area.
00121 
00122 struct BarCodeProcessResult
00123 {
00124     int pixofs;
00125     int raw;
00126     int mask;
00127 };
00128 
00129 template <int nBits, int leftBarWidth, int leftBarMaxOfs, int bitWidth>
00130 class PlungerSensorBarCode: public PlungerSensorImage<BarCodeProcessResult>
00131 {
00132 public:
00133     PlungerSensorBarCode(PlungerSensorImageInterface &sensor, int npix)
00134         : PlungerSensorImage(sensor, npix, (1 << nBits) - 1)
00135     {
00136         startOfs = 0;
00137     }
00138 
00139     // process a configuration change
00140     virtual void onConfigChange(int varno, Config &cfg)
00141     {
00142         // check for bar-code variables
00143         switch (varno)
00144         {
00145         case 20:
00146             // bar code offset
00147             startOfs = cfg.plunger.barCode.startPix;
00148             break;
00149         }
00150         
00151         // do the generic work
00152         PlungerSensorImage::onConfigChange(varno, cfg);
00153     }
00154 
00155 protected:
00156     // process the image    
00157     virtual bool process(const uint8_t *pix, int npix, int &pos, BarCodeProcessResult &res)
00158     {
00159         // adjust auto-exposure
00160         adjustExposure(pix, npix);
00161         
00162         // clear the result descriptor
00163         res.pixofs = 0;
00164         res.raw = 0;
00165         res.mask = 0;
00166         
00167 #if 0 // $$$
00168 
00169         // scan from the left edge until we find the fixed '0' start bit
00170         for (int i = 0 ; i < leftBarMaxOfs ; ++i, ++pix)
00171         {
00172             // check for the '0' bit
00173             if (readBit8(pix) == 0)
00174             {
00175                 // got it - skip the start bit
00176                 pix += bitWidth;
00177                 
00178                 // read the gray code bits
00179                 int gray = 0;
00180                 for (int j = 0 ; j < nBits ; ++j, pix += bitWidth)
00181                 {
00182                     // read the bit; return failure if we can't decode a bit
00183                     int bit = readBit8(pix);
00184                     if (bit < 0)
00185                         return false;
00186                         
00187                     // shift it into the code
00188                     gray = (gray << 1) | bit;
00189                 }
00190             }
00191             
00192             // convert the gray code to binary
00193             int bin = grayToBin(gray);
00194             
00195             // compute the parity of the binary value
00196             int parity = 0;
00197             for (int j = 0 ; j < nBits ; ++j)
00198                 parity ^= bin >> j;
00199                 
00200             // figure the bit required for odd parity
00201             int odd = (parity & 0x01) ^ 0x01;
00202             
00203             // read the check bit
00204             int bit = readBit8(pix);
00205             if (pix < 0)
00206                 return false;
00207                 
00208             // check that it matches the expected parity
00209             if (bit != odd)
00210                 return false;
00211                 
00212             // success
00213             pos = bin;
00214             return true;
00215         }
00216         
00217         // no code found
00218         return false;
00219 
00220 #else
00221         int barStart = leftBarMaxOfs/2;
00222         if (leftBarWidth != 0) // $$$
00223         {
00224             // Find the black bar on the left side (nearest pixel 0) that
00225             // delimits the start of the bar code.  To find it, first figure
00226             // the average brightness over the left margin up to the maximum
00227             // allowable offset, then look for the bar by finding the first
00228             // bar-width run of pixels that are darker than the average.
00229             int lsum = 0;
00230             for (int x = 1 ; x <= leftBarMaxOfs ; ++x)
00231                 lsum += pix[x];
00232             int lavg = lsum / leftBarMaxOfs;
00233     
00234             // now find the first dark edge
00235             for (int x = 0 ; x < leftBarMaxOfs ; ++x)
00236             {
00237                 // if this pixel is dark, and one of the next two is dark,
00238                 // take it as the edge
00239                 if (pix[x] < lavg && (pix[x+1] < lavg || pix[x+2] < lavg))
00240                 {
00241                     // move past the delimier
00242                     barStart = x + leftBarWidth;
00243                     break;
00244                 }
00245             }
00246         }
00247         else
00248         {
00249             // start at the fixed pixel offset
00250             barStart = startOfs;
00251         }
00252 
00253         // Start with zero in the barcode and success mask.  The mask
00254         // indicates which bits we were able to read successfully: a
00255         // '1' bit in the mask indicates that the corresponding bit
00256         // position in 'barcode' was successfully read, a '0' bit means
00257         // that the image was too fuzzy to read.
00258         int barcode = 0, mask = 0;
00259 
00260         // Scan the bits
00261         for (int bit = 0, x0 = barStart; bit < nBits ; ++bit, x0 += bitWidth)
00262         {
00263 #if 0
00264             // Figure the extent of this bit.  The last bit is double
00265             // the width of the other bits, to give us a better chance
00266             // of making out the small features of the last bit.
00267             int w = bitWidth;
00268             if (bit == nBits - 1) w *= 2;
00269 #else
00270             // width of the bit
00271             const int w = bitWidth;
00272 #endif
00273 
00274             // figure the bit's internal pixel layout
00275             int halfBitWidth = w / 2;
00276             int x1 = x0 + halfBitWidth;     // midpoint
00277             int x2 = x0 + w;                // right edge
00278             
00279             // make sure we didn't go out of bounds
00280             if (x1 > npix) x1 = npix;
00281             if (x2 > npix) x2 = npix;
00282 
00283 #if 0
00284             // get the average of the pixels over the bit
00285             int sum = 0;
00286             for (int x = x0 ; x < x2 ; ++x)
00287                 sum += pix[x];
00288             int avg = sum / w;
00289             // Scan the left and right sections.  Classify each
00290             // section according to whether the majority of its
00291             // pixels are above or below the local average.
00292             int lsum = 0, rsum = 0;
00293             for (int x = x0 + 1 ; x < x1 - 1 ; ++x)
00294                 lsum += (pix[x] < avg ? 0 : 1);
00295             for (int x = x1 + 1 ; x < x2 - 1 ; ++x)
00296                 rsum += (pix[x] < avg ? 0 : 1);
00297 #else
00298             // Sum the pixel readings in each half-bit.  Ignore
00299             // the first and last bit of each section, since these
00300             // could be contaminated with scattered light from the
00301             // adjacent half-bit.  On the right half, hew to the 
00302             // right side if the overall pixel width is odd. 
00303             int lsum = 0, rsum = 0;
00304             for (int x = x0 + 1 ; x < x1 - 1 ; ++x)
00305                 lsum += pix[x];
00306             for (int x = x2 - halfBitWidth + 1 ; x < x2 - 1 ; ++x)
00307                 rsum += pix[x];
00308 #endif
00309                 
00310             // shift a zero bit into the code and success mask
00311             barcode <<= 1;
00312             mask <<= 1;
00313 
00314             // Brightness difference required per pixel.  Higher values
00315             // require greater contrast to make a reading, which reduces
00316             // spurious readings at the cost of reducing the overall 
00317             // success rate.  The right level depends on the quality of
00318             // the optical system.  Setting this to zero makes us maximally
00319             // tolerant of low-contrast images, allowing for the simplest
00320             // optical system.  Our simple optical system suffers from
00321             // poor focus, which in turn causes poor contrast in small
00322             // features.
00323             const int minDelta = 2;
00324 
00325             // see if we could tell the difference in brightness
00326             int delta = lsum - rsum;
00327             if (delta < 0) delta = -delta;
00328             if (delta > minDelta * w/2)
00329             {
00330                 // got it - black/white = 0, white/black = 1
00331                 if (lsum > rsum) barcode |= 1;
00332                 mask |= 1;
00333             }
00334         }
00335 
00336         // decode the Gray code value to binary
00337         pos = grayToBin[barcode];
00338         
00339         // set the results descriptor structure
00340         res.pixofs = barStart;
00341         res.raw = barcode;
00342         res.mask = mask;
00343     
00344         // return success if we decoded all bits, and the Gray-to-binary
00345         // mapping was populated
00346         return pos != (1 << nBits) && mask == ((1 << nBits) - 1);
00347 #endif
00348     }
00349     
00350     // read a bar starting at the given pixel
00351     int readBit8(const uint8_t *pix)
00352     {
00353         // pull out the pixels for the bar
00354         uint8_t s[8];
00355         memcpy(s, pix, 8);
00356         
00357         // sort them in brightness order (using an 8-element network sort)
00358 #define SWAP(a, b) if (s[a] > s[b]) { uint8_t tmp = s[a]; s[a] = s[b]; s[b] = tmp; }
00359         SWAP(0, 1);
00360         SWAP(2, 3);
00361         SWAP(0, 2);
00362         SWAP(1, 3);
00363         SWAP(1, 2);
00364         SWAP(4, 5);
00365         SWAP(6, 7);
00366         SWAP(4, 6);
00367         SWAP(5, 7);
00368         SWAP(5, 6);
00369         SWAP(0, 4);
00370         SWAP(1, 5);
00371         SWAP(1, 4);
00372         SWAP(2, 6);
00373         SWAP(3, 7);
00374         SWAP(3, 6);
00375         SWAP(2, 4);
00376         SWAP(3, 5);
00377         SWAP(3, 4);
00378 #undef SWAP
00379         
00380         // figure the median brightness
00381         int median = (int(s[3]) + s[4] + 1) / 2;
00382         
00383         // count pixels below the median on each side
00384         int ldark = 0, rdark = 0;
00385         for (int i = 0 ; i < 3 ; ++i)
00386         {
00387             if (pix[i] < median)
00388                 ldark++;
00389         }
00390         for (int i = 4 ; i < 8 ; ++i)
00391         {
00392             if (pix[i] < median)
00393                 rdark++;
00394         }
00395         
00396         // we need >=3 dark + >=3 light or vice versa
00397         if (ldark >= 3 && rdark <= 1)
00398         {
00399             // dark + light = '0' bit
00400             return 0;
00401         }
00402         if (ldark <= 1 && rdark >= 3)
00403         {
00404             // light + dark = '1' bit
00405             return 1;
00406         }
00407         else
00408         {
00409             // ambiguous bit
00410             return -1;
00411         }
00412     }
00413 
00414     // bar code sensor orientation is fixed
00415     virtual int getOrientation() const { return 1; }
00416     
00417     // send extra status report headers
00418     virtual void extraStatusHeaders(USBJoystick &js, BarCodeProcessResult &res)
00419     {
00420         // Send the bar code status report.  We use coding type 1 (Gray code,
00421         // Manchester pixel coding).
00422         js.sendPlungerStatusBarcode(nBits, 1, res.pixofs, bitWidth, res.raw, res.mask);
00423     }
00424     
00425     // adjust the exposure
00426     void adjustExposure(const uint8_t *pix, int npix)
00427     {
00428 #if 1
00429         // The Manchester code has a nice property for auto exposure
00430         // control: each bit area has equal numbers of white and black
00431         // pixels.  So we know exactly how the overall population of
00432         // pixels has to look: the bit area will be 50% black and 50%
00433         // white, and the margins will be all white.  For maximum
00434         // contrast, target an exposure level where the black pixels
00435         // are all below a certain brightness level and the white
00436         // pixels are all above.  Start by figuring the number of
00437         // pixels above and below.
00438         const int medianTarget = 160;
00439         int nBelow = 0;
00440         for (int i = 0 ; i < npix ; ++i)
00441         {
00442             if (pix[i] < medianTarget)
00443                 ++nBelow;
00444         }
00445         
00446         // Figure the desired number of black pixels: the left bar is
00447         // all black pixels, and 50% of each bit is black pixels.
00448         int targetBelow = leftBarWidth + (nBits * bitWidth)/2;
00449         
00450         // Increase exposure time if too many pixels are below the
00451         // halfway point; decrease it if too many pixels are above.
00452         int d = nBelow - targetBelow;
00453         if (d > 5 || d < -5)
00454         {
00455             axcTime += d;
00456         }
00457         
00458         
00459 #elif 0 //$$$
00460         // Count exposure levels of pixels in the left and right margins
00461         BarCodeExposureCounter counter;
00462         for (int i = 0 ; i < leftBarMaxOfs/2 ; ++i)
00463         {
00464             // count the pixels at the left and right margins
00465             counter.count(pix[i]);
00466             counter.count(pix[npix - i - 1]);
00467         }
00468         
00469         // The margin is all white, so try to get all of these pixels
00470         // in the bright range, but not saturated.  That should give us
00471         // the best overall contrast throughout the image.
00472         if (counter.nSat > 0)
00473         {
00474             // overexposed - reduce exposure time
00475             if (axcTime > 5)
00476                 axcTime -= 5;
00477             else
00478                 axcTime = 0;
00479         }
00480         else if (counter.nBright < leftBarMaxOfs)
00481         {
00482             // they're not all in the bright range - increase exposure time
00483             axcTime += 5;
00484         }
00485 
00486 #else // $$$
00487         // Count the number of pixels near total darkness and
00488         // total saturation
00489         int nZero = 0, nDark = 0, nBri = 0, nSat = 0;
00490         for (int i = 0 ; i < npix ; ++i)
00491         {
00492             int pi = pix[i];
00493             if (pi <= 2)
00494                 ++nZero;
00495             else if (pi < 12)
00496                 ++nDark;
00497             else if (pi >= 254)
00498                 ++nSat;
00499             else if (pi > 242)
00500                 ++nBri;
00501         }
00502         
00503         // If more than 30% of pixels are near total darkness, increase
00504         // the exposure time.  If more than 30% are near total saturation,
00505         // decrease the exposure time.
00506         int pct5 = uint32_t(npix * 3277) >> 16;
00507         int pct30 = uint32_t(npix * 19661) >> 16;
00508         int pct50 = uint32_t(npix) >> 1;
00509         if (nSat == 0)
00510         {
00511             // no saturated pixels - increase exposure time
00512             axcTime += 5;
00513         }
00514         else if (nSat > pct5)
00515         {
00516             if (axcTime > 5)
00517                 axcTime -= 5;
00518             else
00519                 axcTime = 0;
00520         }
00521         else if (nZero == 0)
00522         {
00523             // no totally dark pixels - decrease exposure time
00524             if (axcTime > 5)
00525                 axcTime -= 5;
00526             else
00527                 axcTime = 0;
00528         }
00529         else if (nZero > pct5)
00530         {
00531             axcTime += 5;
00532         }
00533         else if (nZero > pct30 || (nDark > pct50 && nSat < pct30))
00534         {
00535             // very dark - increase exposure time a lot
00536             if (axcTime < 450)
00537                 axcTime += 50;
00538         }
00539         else if (nDark > pct30 && nSat < pct30)
00540         {
00541             // dark - increase exposure time a bit
00542             if (axcTime < 490)
00543                 axcTime += 10;
00544         }
00545         else if (nSat > pct30 || (nBri > pct50 && nDark < pct30))
00546         {
00547             // very overexposed - decrease exposure time a lot
00548             if (axcTime > 50)
00549                 axcTime -= 50;
00550             else
00551                 axcTime = 0;
00552         }
00553         else if (nBri > pct30 && nDark < pct30)
00554         {
00555             // overexposed - decrease exposure time a little
00556             if (axcTime > 10)
00557                 axcTime -= 10;
00558             else
00559                 axcTime = 0;
00560         }
00561 #endif
00562         
00563         // don't allow the exposure time to go below 0 or over 2.5ms
00564         if (int(axcTime) < 0)
00565             axcTime = 0;
00566         if (axcTime > 2500)
00567             axcTime = 2500;
00568     }
00569 
00570 #if 0
00571     // convert a reflected Gray code value (up to 16 bits) to binary
00572     static inline int grayToBin(int grayval)
00573     {
00574         int temp = grayval ^ (grayval >> 8);
00575         temp ^= (temp >> 4);
00576         temp ^= (temp >> 2);
00577         temp ^= (temp >> 1);
00578         return temp;
00579     }
00580 #endif
00581 
00582     // bar code starting pixel offset
00583     int startOfs;
00584 };
00585 
00586 #endif