tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
qrsequence.h
1 // File: qrsequence.h
3 // Description: Quasi-random sequence generator class.
4 // Author: Ranjith Unnikrishnan
5 // Created: Wed May 20 2009
6 //
7 // Class to generate a (deterministic) quasi-random Van der Corput sequence that
8 // covers the interval [0,N) without repetition.
9 //
10 // The sequence is generated by reversing the base-2 representation of the
11 // sequence of natural numbers {0, 1,... M-1}, where M is 2^{num_bits_} and
12 // num_bits is the minimum number of bits required to represent N. If a reversed
13 // numbers is >= N it is rejected and the next natural number is considered
14 // until a valid output number is found.
15 //
16 // (C) Copyright 2009, Google Inc.
17 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
18 // use this file except in compliance with the License. You may obtain a copy
19 // of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required
20 // by applicable law or agreed to in writing, software distributed under the
21 // License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS
22 // OF ANY KIND, either express or implied. See the License for the specific
23 // language governing permissions and limitations under the License.
24 //
26 
27 #ifndef TESSERACT_CCUTIL_QRSEQUENCE_H_
28 #define TESSERACT_CCUTIL_QRSEQUENCE_H_
29 
30 #include <cmath>
31 
33  public:
34  // Object is initialized with the size of the output range.
35  explicit QRSequenceGenerator(int N) : N_(N), next_num_(0) {
36  num_bits_ = static_cast<int>(ceil(log(static_cast<double>(N)) / log(2.0)));
37  }
38 
39  // Main worker method that retrieves the next number in the sequence.
40  // Returns kInvalidVal if called more than N times after object initialization
41  int GetVal() {
42  const int kInvalidVal = -1;
43  const int kMaxNaturalNumberValue = 1 << num_bits_;
44  if (next_num_ >= kMaxNaturalNumberValue)
45  return kInvalidVal;
46  int n = next_num_;
47 
48  while (next_num_ < kMaxNaturalNumberValue) {
50  if (n < N_) break;
51  }
52  return (next_num_ > kMaxNaturalNumberValue) ? kInvalidVal : n;
53  }
54 
55  protected:
56  // Outputs the integer formed by reversing the bits of the input integer. Only
57  // the lowest num_bits_ bits of the input integer are reversed.
58  int GetBinaryReversedInteger(int in_val) const {
59  int bit_pos = num_bits_;
60  int out_val = 0;
61  while(bit_pos--) {
62  // Set the value of the last bit.
63  out_val |= (in_val & 0x1);
64  if (bit_pos > 0) {
65  // Left-shift output value to prepare for storing the next bit.
66  out_val <<= 1;
67  }
68  // Right-shift input value to prepare for retrieving the next bit.
69  in_val >>= 1;
70  }
71  return out_val;
72  }
73  int N_;
74  // Next number to be considered for reversal and output.
75  int next_num_;
76  // number of bits required to represent the numbers of the sequence
77  int num_bits_;
78 };
79 
80 #endif // TESSERACT_CCUTIL_QRSEQUENCE_H_
int num_bits_
Definition: qrsequence.h:77
int N_
Definition: qrsequence.h:73
int GetBinaryReversedInteger(int in_val) const
Definition: qrsequence.h:58
int next_num_
Definition: qrsequence.h:75
Definition: qrsequence.h:32
QRSequenceGenerator(int N)
Definition: qrsequence.h:35
int GetVal()
Definition: qrsequence.h:41