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