cpp/core/src/common/BlackPointEstimator.cpp

   1 /*
   2  *  BlackPointEstimator.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 12/05/2008.
   6  *  Copyright 2008 Google UK. All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include "BlackPointEstimator.h"
  22 #include "IllegalArgumentException.h"
  23
  24 using namespace std;
  25
  26 namespace common {
  27
  28   size_t BlackPointEstimator::estimate(valarray<int> &histogram) {
  29
  30     size_t numBuckets = histogram.size();
  31
  32     // Find tallest peak in histogram
  33     size_t firstPeak = 0;
  34     int firstPeakSize = 0;
  35     for (size_t i = 0; i < numBuckets; i++) {
  36       if (histogram[i] > firstPeakSize) {
  37         firstPeak = i;
  38         firstPeakSize = histogram[i];
  39       }
  40     }
  41
  42     // Find second-tallest peak -- well, another peak that is tall and not
  43     // so close to the first one
  44     size_t secondPeak = 0;
  45     int secondPeakScore = 0;
  46     for (size_t i = 0; i < numBuckets; i++) {
  47       int distanceToBiggest = i - firstPeak;
  48       // Encourage more distant second peaks by multiplying by square of distance
  49       int score = histogram[i] * distanceToBiggest * distanceToBiggest;
  50       if (score > secondPeakScore) {
  51         secondPeak = i;
  52         secondPeakScore = score;
  53       }
  54     }
  55
  56     // Put firstPeak first
  57     if (firstPeak > secondPeak) {
  58       int temp = firstPeak;
  59       firstPeak = secondPeak;
  60       secondPeak = temp;
  61     }
  62
  63     // Kind of aribtrary; if the two peaks are very close, then we figure there is so little
  64     // dynamic range in the image, that discriminating black and white is too error-prone.
  65     // Decoding the image/line is either pointless, or may in some cases lead to a false positive
  66     // for 1D formats, which are relatively lenient.
  67     // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"
  68     if (secondPeak - firstPeak <= histogram.size() >> 4) {
  69       throw new IllegalArgumentException
  70         ("Too little dynamic range in luminance");
  71     }
  72
  73     // Find a valley between them that is low and closer to the white peak
  74     size_t bestValley = secondPeak - 1;
  75     int bestValleyScore = -1;
  76     for (size_t i = secondPeak - 1; i > firstPeak; i--) {
  77       int fromFirst = i - firstPeak;
  78       // Favor a "valley" that is not too close to either peak -- especially not the black peak --
  79       // and that has a low value of course
  80       int score = fromFirst * fromFirst * (secondPeak - i) * (256 - histogram[i]);
  81       if (score > bestValleyScore) {
  82         bestValley = i;
  83         bestValleyScore = score;
  84       }
  85     }
  86
  87     return bestValley;
  88   }
  89
  90 }