1 // Copyright 2010 Google Inc. All Rights Reserved.
2 // Author: rays@google.com (Ray Smith)
3 ///////////////////////////////////////////////////////////////////////
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 //
18 ///////////////////////////////////////////////////////////////////////
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
IntFeatureMap()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
~IntFeatureMap()40 IntFeatureMap::~IntFeatureMap() {
41 Clear();
42 }
43
44 // Pseudo-accessors.
IndexFeature(const INT_FEATURE_STRUCT & f) const45 int IntFeatureMap::IndexFeature(const INT_FEATURE_STRUCT &f) const {
46 return feature_space_.Index(f);
47 }
MapFeature(const INT_FEATURE_STRUCT & f) const48 int IntFeatureMap::MapFeature(const INT_FEATURE_STRUCT &f) const {
49 return feature_map_.SparseToCompact(feature_space_.Index(f));
50 }
MapIndexFeature(int index_feature) const51 int IntFeatureMap::MapIndexFeature(int index_feature) const {
52 return feature_map_.SparseToCompact(index_feature);
53 }
InverseIndexFeature(int index_feature) const54 INT_FEATURE_STRUCT IntFeatureMap::InverseIndexFeature(int index_feature) const {
55 return feature_space_.PositionFromIndex(index_feature);
56 }
InverseMapFeature(int map_feature) const57 INT_FEATURE_STRUCT IntFeatureMap::InverseMapFeature(int map_feature) const {
58 int index = feature_map_.CompactToSparse(map_feature);
59 return feature_space_.PositionFromIndex(index);
60 }
DeleteMapFeature(int map_feature)61 void IntFeatureMap::DeleteMapFeature(int map_feature) {
62 feature_map_.Merge(-1, map_feature);
63 mapping_changed_ = true;
64 }
IsMapFeatureDeleted(int map_feature) const65 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.
Init(const IntFeatureSpace & feature_space)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.
OffsetFeature(int index_feature,int dir) const112 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.
FindNZFeatureMapping(SampleIterator * it)132 int IntFeatureMap::FindNZFeatureMapping(SampleIterator *it) {
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.
FinalizeMapping(SampleIterator * it)155 int IntFeatureMap::FinalizeMapping(SampleIterator *it) {
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.
DebugMapFeatures(const std::vector<int> & map_features) const168 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
Clear()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.
ComputeOffsetFeature(int index_feature,int dir) const196 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.
242