tesseract  5.0.0
intfeaturemap.cpp
Go to the documentation of this file.
1 // Copyright 2010 Google Inc. All Rights Reserved.
2 // Author: rays@google.com (Ray Smith)
4 // File: intfeaturemap.cpp
5 // Description: Encapsulation of IntFeatureSpace with IndexMapBiDi
6 // to provide a subspace mapping and fast feature lookup.
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 // http://www.apache.org/licenses/LICENSE-2.0
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 //
19 
20 #include "intfeaturemap.h"
21 
22 #include "intfeaturespace.h"
23 #include "intfx.h"
24 // These includes do not exist yet, but will be coming soon.
25 //#include "sampleiterator.h"
26 //#include "trainingsample.h"
27 //#include "trainingsampleset.h"
28 
29 namespace tesseract {
30 
31 const int kMaxOffsetDist = 32;
32 
33 IntFeatureMap::IntFeatureMap() : mapping_changed_(true), compact_size_(0) {
34  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
35  offset_plus_[dir] = nullptr;
36  offset_minus_[dir] = nullptr;
37  }
38 }
39 
41  Clear();
42 }
43 
44 // Pseudo-accessors.
46  return feature_space_.Index(f);
47 }
49  return feature_map_.SparseToCompact(feature_space_.Index(f));
50 }
51 int IntFeatureMap::MapIndexFeature(int index_feature) const {
52  return feature_map_.SparseToCompact(index_feature);
53 }
55  return feature_space_.PositionFromIndex(index_feature);
56 }
58  int index = feature_map_.CompactToSparse(map_feature);
59  return feature_space_.PositionFromIndex(index);
60 }
61 void IntFeatureMap::DeleteMapFeature(int map_feature) {
62  feature_map_.Merge(-1, map_feature);
63  mapping_changed_ = true;
64 }
65 bool IntFeatureMap::IsMapFeatureDeleted(int map_feature) const {
66  return feature_map_.IsCompactDeleted(map_feature);
67 }
68 
69 // Copies the given feature_space and uses it as the index feature map
70 // from INT_FEATURE_STRUCT.
71 void IntFeatureMap::Init(const IntFeatureSpace &feature_space) {
72  feature_space_ = feature_space;
73  mapping_changed_ = false;
74  int sparse_size = feature_space_.Size();
75  feature_map_.Init(sparse_size, true);
76  feature_map_.Setup();
77  compact_size_ = feature_map_.CompactSize();
78  // Initialize look-up tables if needed.
79  FCOORD dir = FeatureDirection(0);
80  if (dir.x() == 0.0f && dir.y() == 0.0f) {
81  InitIntegerFX();
82  }
83  // Compute look-up tables to generate offset features.
84  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
85  delete[] offset_plus_[dir];
86  delete[] offset_minus_[dir];
87  offset_plus_[dir] = new int[sparse_size];
88  offset_minus_[dir] = new int[sparse_size];
89  }
90  for (int dir = 1; dir <= kNumOffsetMaps; ++dir) {
91  for (int i = 0; i < sparse_size; ++i) {
92  int offset_index = ComputeOffsetFeature(i, dir);
93  offset_plus_[dir - 1][i] = offset_index;
94  offset_index = ComputeOffsetFeature(i, -dir);
95  offset_minus_[dir - 1][i] = offset_index;
96  }
97  }
98 }
99 
100 // Helper to return an offset index feature. In this context an offset
101 // feature with a dir of +/-1 is a feature of a similar direction,
102 // but shifted perpendicular to the direction of the feature. An offset
103 // feature with a dir of +/-2 is feature at the same position, but rotated
104 // by +/- one [compact] quantum. Returns the index of the generated offset
105 // feature, or -1 if it doesn't exist. Dir should be in
106 // [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
107 // A dir of 0 is an identity transformation.
108 // Both input and output are from the index(sparse) feature space, not
109 // the mapped/compact feature space, but the offset feature is the minimum
110 // distance moved from the input to guarantee that it maps to the next
111 // available quantum in the mapped/compact space.
112 int IntFeatureMap::OffsetFeature(int index_feature, int dir) const {
113  if (dir > 0 && dir <= kNumOffsetMaps) {
114  return offset_plus_[dir - 1][index_feature];
115  } else if (dir < 0 && -dir <= kNumOffsetMaps) {
116  return offset_minus_[-dir - 1][index_feature];
117  } else if (dir == 0) {
118  return index_feature;
119  } else {
120  return -1;
121  }
122 }
123 
124 //#define EXPERIMENT_ON
125 #ifdef EXPERIMENT_ON // This code is commented out as SampleIterator and
126 // TrainingSample are not reviewed/checked in yet, but these functions are a
127 // useful indicator of how an IntFeatureMap is setup.
128 
129 // Computes the features used by the subset of samples defined by
130 // the iterator and sets up the feature mapping.
131 // Returns the size of the compacted feature space.
133  feature_map_.Init(feature_space_.Size(), false);
134  int total_samples = 0;
135  for (it->Begin(); !it->AtEnd(); it->Next()) {
136  const TrainingSample &sample = it->GetSample();
137  std::vector<int> features;
138  feature_space_.IndexAndSortFeatures(sample.features(), sample.num_features(), &features);
139  int num_features = features.size();
140  for (int f = 0; f < num_features; ++f)
141  feature_map_.SetMap(features[f], true);
142  ++total_samples;
143  }
144  feature_map_.Setup();
145  compact_size_ = feature_map_.CompactSize();
146  mapping_changed_ = true;
147  FinalizeMapping(it);
148  tprintf("%d non-zero features found in %d samples\n", compact_size_, total_samples);
149  return compact_size_;
150 }
151 #endif
152 
153 // After deleting some features, finish setting up the mapping, and map
154 // all the samples. Returns the size of the compacted feature space.
156  if (mapping_changed_) {
157  feature_map_.CompleteMerges();
158  compact_size_ = feature_map_.CompactSize();
159 #ifdef EXPERIMENT_ON
160  it->MapSampleFeatures(*this);
161 #endif
162  mapping_changed_ = false;
163  }
164  return compact_size_;
165 }
166 
167 // Prints the map features from the set in human-readable form.
168 void IntFeatureMap::DebugMapFeatures(const std::vector<int> &map_features) const {
169  for (int map_feature : map_features) {
170  INT_FEATURE_STRUCT f = InverseMapFeature(map_feature);
171  f.print();
172  }
173 }
174 
175 void IntFeatureMap::Clear() {
176  for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
177  delete[] offset_plus_[dir];
178  delete[] offset_minus_[dir];
179  offset_plus_[dir] = nullptr;
180  offset_minus_[dir] = nullptr;
181  }
182 }
183 
184 // Helper to compute an offset index feature. In this context an offset
185 // feature with a dir of +/-1 is a feature of a similar direction,
186 // but shifted perpendicular to the direction of the feature. An offset
187 // feature with a dir of +/-2 is feature at the same position, but rotated
188 // by +/- one [compact] quantum. Returns the index of the generated offset
189 // feature, or -1 if it doesn't exist. Dir should be in
190 // [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
191 // A dir of 0 is an identity transformation.
192 // Both input and output are from the index(sparse) feature space, not
193 // the mapped/compact feature space, but the offset feature is the minimum
194 // distance moved from the input to guarantee that it maps to the next
195 // available quantum in the mapped/compact space.
196 int IntFeatureMap::ComputeOffsetFeature(int index_feature, int dir) const {
197  INT_FEATURE_STRUCT f = InverseIndexFeature(index_feature);
198  ASSERT_HOST(IndexFeature(f) == index_feature);
199  if (dir == 0) {
200  return index_feature;
201  } else if (dir == 1 || dir == -1) {
202  FCOORD feature_dir = FeatureDirection(f.Theta);
203  FCOORD rotation90(0.0f, 1.0f);
204  feature_dir.rotate(rotation90);
205  // Find the nearest existing feature.
206  for (int m = 1; m < kMaxOffsetDist; ++m) {
207  double x_pos = f.X + feature_dir.x() * (m * dir);
208  double y_pos = f.Y + feature_dir.y() * (m * dir);
209  int x = IntCastRounded(x_pos);
210  int y = IntCastRounded(y_pos);
211  if (x >= 0 && x <= UINT8_MAX && y >= 0 && y <= UINT8_MAX) {
212  INT_FEATURE_STRUCT offset_f;
213  offset_f.X = x;
214  offset_f.Y = y;
215  offset_f.Theta = f.Theta;
216  int offset_index = IndexFeature(offset_f);
217  if (offset_index != index_feature && offset_index >= 0) {
218  return offset_index; // Found one.
219  }
220  } else {
221  return -1; // Hit the edge of feature space.
222  }
223  }
224  } else if (dir == 2 || dir == -2) {
225  // Find the nearest existing index_feature.
226  for (int m = 1; m < kMaxOffsetDist; ++m) {
227  int theta = f.Theta + m * dir / 2;
228  INT_FEATURE_STRUCT offset_f;
229  offset_f.X = f.X;
230  offset_f.Y = f.Y;
231  offset_f.Theta = Modulo(theta, 256);
232  int offset_index = IndexFeature(offset_f);
233  if (offset_index != index_feature && offset_index >= 0) {
234  return offset_index; // Found one.
235  }
236  }
237  }
238  return -1; // Nothing within the max distance.
239 }
240 
241 } // namespace tesseract.
#define ASSERT_HOST(x)
Definition: errcode.h:59
FCOORD FeatureDirection(uint8_t theta)
Definition: intfx.cpp:70
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
int IntCastRounded(double x)
Definition: helpers.h:175
const int kMaxOffsetDist
void InitIntegerFX()
Definition: intfx.cpp:54
int Modulo(int a, int b)
Definition: helpers.h:158
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
int CompactSize() const
Definition: indexmapbidi.h:63
int CompactToSparse(int compact_index) const
Definition: indexmapbidi.h:55
void Init(int size, bool all_mapped)
bool Merge(int compact_index1, int compact_index2)
void SetMap(int sparse_index, bool mapped)
int SparseToCompact(int sparse_index) const override
Definition: indexmapbidi.h:140
bool IsCompactDeleted(int index) const
Definition: indexmapbidi.h:132
INT_FEATURE_STRUCT PositionFromIndex(int index) const
int Index(const INT_FEATURE_STRUCT &f) const
void IndexAndSortFeatures(const INT_FEATURE_STRUCT *features, int num_features, std::vector< int > *sorted_features) const
uint32_t num_features() const
const INT_FEATURE_STRUCT * features() const
void DebugMapFeatures(const std::vector< int > &map_features) const
int MapFeature(const INT_FEATURE_STRUCT &f) const
const IntFeatureSpace & feature_space() const
Definition: intfeaturemap.h:60
INT_FEATURE_STRUCT InverseIndexFeature(int index_feature) const
bool IsMapFeatureDeleted(int map_feature) const
INT_FEATURE_STRUCT InverseMapFeature(int map_feature) const
int MapIndexFeature(int index_feature) const
int OffsetFeature(int index_feature, int dir) const
void DeleteMapFeature(int map_feature)
int FindNZFeatureMapping(SampleIterator *it)
void Init(const IntFeatureSpace &feature_space)
int IndexFeature(const INT_FEATURE_STRUCT &f) const
int FinalizeMapping(SampleIterator *it)
const TrainingSample & GetSample() const
void MapSampleFeatures(const IntFeatureMap &feature_map)