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     int maxBucketCount = 0;
  32
  33     // Find tallest peak in histogram
  34     size_t firstPeak = 0;
  35     int firstPeakSize = 0;
  36     for (size_t i = 0; i < numBuckets; i++) {
  37       if (histogram[i] > firstPeakSize) {
  38         firstPeak = i;
  39         firstPeakSize = histogram[i];
  40       }
  41       if (histogram[i] > maxBucketCount) {
  42         maxBucketCount = histogram[i];
  43       }
  44     }
  45
  46     // Find second-tallest peak -- well, another peak that is tall and not
  47     // so close to the first one
  48     size_t secondPeak = 0;
  49     int secondPeakScore = 0;
  50     for (size_t i = 0; i < numBuckets; i++) {
  51       int distanceToBiggest = i - firstPeak;
  52       // Encourage more distant second peaks by multiplying by square of distance
  53       int score = histogram[i] * distanceToBiggest * distanceToBiggest;
  54       if (score > secondPeakScore) {
  55         secondPeak = i;
  56         secondPeakScore = score;
  57       }
  58     }
  59
  60     // Put firstPeak first
  61     if (firstPeak > secondPeak) {
  62       int temp = firstPeak;
  63       firstPeak = secondPeak;
  64       secondPeak = temp;
  65     }
  66
  67     // Kind of aribtrary; if the two peaks are very close, then we figure there is so little
  68     // dynamic range in the image, that discriminating black and white is too error-prone.
  69     // Decoding the image/line is either pointless, or may in some cases lead to a false positive
  70     // for 1D formats, which are relatively lenient.
  71     // We arbitrarily say "close" is "<= 1/16 of the total histogram buckets apart"
  72     if (secondPeak - firstPeak <= numBuckets >> 4) {
  73       throw new IllegalArgumentException
  74         ("Too little dynamic range in luminance");
  75     }
  76
  77     // Find a valley between them that is low and closer to the white peak
  78     size_t bestValley = secondPeak - 1;
  79     int bestValleyScore = -1;
  80     for (size_t i = secondPeak - 1; i > firstPeak; i--) {
  81       int fromFirst = i - firstPeak;
  82       // Favor a "valley" that is not too close to either peak -- especially not the black peak --
  83       // and that has a low value of course
  84       int score = fromFirst * fromFirst * (secondPeak - i) * (maxBucketCount - histogram[i]);
  85       if (score > bestValleyScore) {
  86         bestValley = i;
  87         bestValleyScore = score;
  88       }
  89     }
  90
  91     return bestValley;
  92   }
  93
  94 }