tesseract 4.1.1
Loading...
Searching...
No Matches
qrsequence.h
Go to the documentation of this file.
1
2// 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.
76 // number of bits required to represent the numbers of the sequence
78};
79
80#endif // TESSERACT_CCUTIL_QRSEQUENCE_H_
int GetBinaryReversedInteger(int in_val) const
Definition: qrsequence.h:58
QRSequenceGenerator(int N)
Definition: qrsequence.h:35