Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 const double kMinPCLengthIncrease = 1.0 / 1024;
34
35 IntFeatureMap::IntFeatureMap()
36 : mapping_changed_(true), compact_size_(0) {
37 for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
38 offset_plus_[dir] = NULL;
39 offset_minus_[dir] = NULL;
40 }
41 }
42
43 IntFeatureMap::~IntFeatureMap() {
44 Clear();
45 }
46
47 // Pseudo-accessors.
48 int IntFeatureMap::IndexFeature(const INT_FEATURE_STRUCT& f) const {
49 return feature_space_.Index(f);
50 }
51 int IntFeatureMap::MapFeature(const INT_FEATURE_STRUCT& f) const {
52 return feature_map_.SparseToCompact(feature_space_.Index(f));
53 }
54 int IntFeatureMap::MapIndexFeature(int index_feature) const {
55 return feature_map_.SparseToCompact(index_feature);
56 }
57 INT_FEATURE_STRUCT IntFeatureMap::InverseIndexFeature(int index_feature) const {
58 return feature_space_.PositionFromIndex(index_feature);
59 }
60 INT_FEATURE_STRUCT IntFeatureMap::InverseMapFeature(int map_feature) const {
61 int index = feature_map_.CompactToSparse(map_feature);
62 return feature_space_.PositionFromIndex(index);
63 }
64 void IntFeatureMap::DeleteMapFeature(int map_feature) {
65 feature_map_.Merge(-1, map_feature);
66 mapping_changed_ = true;
67 }
68 bool IntFeatureMap::IsMapFeatureDeleted(int map_feature) const {
69 return feature_map_.IsCompactDeleted(map_feature);
70 }
71
72 // Copies the given feature_space and uses it as the index feature map
73 // from INT_FEATURE_STRUCT.
74 void IntFeatureMap::Init(const IntFeatureSpace& feature_space) {
75 feature_space_ = feature_space;
76 mapping_changed_ = false;
77 int sparse_size = feature_space_.Size();
78 feature_map_.Init(sparse_size, true);
79 feature_map_.Setup();
80 compact_size_ = feature_map_.CompactSize();
81 // Initialize look-up tables if needed.
82 FCOORD dir = FeatureDirection(0);
83 if (dir.x() == 0.0f && dir.y() == 0.0f)
84 InitIntegerFX();
85 // Compute look-up tables to generate offset features.
86 for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
87 delete [] offset_plus_[dir];
88 delete [] offset_minus_[dir];
89 offset_plus_[dir] = new int[sparse_size];
90 offset_minus_[dir] = new int[sparse_size];
91 }
92 for (int dir = 1; dir <= kNumOffsetMaps; ++dir) {
93 for (int i = 0; i < sparse_size; ++i) {
94 int offset_index = ComputeOffsetFeature(i, dir);
95 offset_plus_[dir - 1][i] = offset_index;
96 offset_index = ComputeOffsetFeature(i, -dir);
97 offset_minus_[dir - 1][i] = offset_index;
98 }
99 }
100 }
101
102 // Helper to return an offset index feature. In this context an offset
103 // feature with a dir of +/-1 is a feature of a similar direction,
104 // but shifted perpendicular to the direction of the feature. An offset
105 // feature with a dir of +/-2 is feature at the same position, but rotated
106 // by +/- one [compact] quantum. Returns the index of the generated offset
107 // feature, or -1 if it doesn't exist. Dir should be in
108 // [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
109 // A dir of 0 is an identity transformation.
110 // Both input and output are from the index(sparse) feature space, not
111 // the mapped/compact feature space, but the offset feature is the minimum
112 // distance moved from the input to guarantee that it maps to the next
113 // available quantum in the mapped/compact space.
114 int IntFeatureMap::OffsetFeature(int index_feature, int dir) const {
115 if (dir > 0 && dir <= kNumOffsetMaps)
116 return offset_plus_[dir - 1][index_feature];
117 else if (dir < 0 && -dir <= kNumOffsetMaps)
118 return offset_minus_[-dir - 1][index_feature];
119 else if (dir == 0)
120 return index_feature;
121 else
122 return -1;
123 }
124
125
126 //#define EXPERIMENT_ON
127 #ifdef EXPERIMENT_ON // This code is commented out as SampleIterator and
128 // TrainingSample are not reviewed/checked in yet, but these functions are a
129 // useful indicator of how an IntFeatureMap is setup.
130
131 // Computes the features used by the subset of samples defined by
132 // the iterator and sets up the feature mapping.
133 // Returns the size of the compacted feature space.
134 int IntFeatureMap::FindNZFeatureMapping(SampleIterator* it) {
135 feature_map_.Init(feature_space_.Size(), false);
136 int total_samples = 0;
137 for (it->Begin(); !it->AtEnd(); it->Next()) {
138 const TrainingSample& sample = it->GetSample();
139 GenericVector<int> features;
140 feature_space_.IndexAndSortFeatures(sample.features(),
141 sample.num_features(),
142 &features);
143 int num_features = features.size();
144 for (int f = 0; f < num_features; ++f)
145 feature_map_.SetMap(features[f], true);
146 ++total_samples;
147 }
148 feature_map_.Setup();
149 compact_size_ = feature_map_.CompactSize();
150 mapping_changed_ = true;
151 FinalizeMapping(it);
152 tprintf("%d non-zero features found in %d samples\n",
153 compact_size_, total_samples);
154 return compact_size_;
155 }
156 #endif
157
158 // After deleting some features, finish setting up the mapping, and map
159 // all the samples. Returns the size of the compacted feature space.
160 int IntFeatureMap::FinalizeMapping(SampleIterator* it) {
161 if (mapping_changed_) {
162 feature_map_.CompleteMerges();
163 compact_size_ = feature_map_.CompactSize();
164 #ifdef EXPERIMENT_ON
165 it->MapSampleFeatures(*this);
166 #endif
167 mapping_changed_ = false;
168 }
169 return compact_size_;
170 }
171
172 // Prints the map features from the set in human-readable form.
173 void IntFeatureMap::DebugMapFeatures(
174 const GenericVector<int>& map_features) const {
175 for (int i = 0; i < map_features.size(); ++i) {
176 INT_FEATURE_STRUCT f = InverseMapFeature(map_features[i]);
177 f.print();
178 }
179 }
180
181 void IntFeatureMap::Clear() {
182 for (int dir = 0; dir < kNumOffsetMaps; ++dir) {
183 delete [] offset_plus_[dir];
184 delete [] offset_minus_[dir];
185 offset_plus_[dir] = NULL;
186 offset_minus_[dir] = NULL;
187 }
188 }
189
190 // Helper to compute an offset index feature. In this context an offset
191 // feature with a dir of +/-1 is a feature of a similar direction,
192 // but shifted perpendicular to the direction of the feature. An offset
193 // feature with a dir of +/-2 is feature at the same position, but rotated
194 // by +/- one [compact] quantum. Returns the index of the generated offset
195 // feature, or -1 if it doesn't exist. Dir should be in
196 // [-kNumOffsetMaps, kNumOffsetMaps] to indicate the relative direction.
197 // A dir of 0 is an identity transformation.
198 // Both input and output are from the index(sparse) feature space, not
199 // the mapped/compact feature space, but the offset feature is the minimum
200 // distance moved from the input to guarantee that it maps to the next
201 // available quantum in the mapped/compact space.
202 int IntFeatureMap::ComputeOffsetFeature(int index_feature, int dir) const {
203 INT_FEATURE_STRUCT f = InverseIndexFeature(index_feature);
204 ASSERT_HOST(IndexFeature(f) == index_feature);
205 if (dir == 0) {
206 return index_feature;
207 } else if (dir == 1 || dir == -1) {
208 FCOORD feature_dir = FeatureDirection(f.Theta);
209 FCOORD rotation90(0.0f, 1.0f);
210 feature_dir.rotate(rotation90);
211 // Find the nearest existing feature.
212 for (int m = 1; m < kMaxOffsetDist; ++m) {
213 double x_pos = f.X + feature_dir.x() * (m * dir);
214 double y_pos = f.Y + feature_dir.y() * (m * dir);
215 int x = IntCastRounded(x_pos);
216 int y = IntCastRounded(y_pos);
217 if (x >= 0 && x <= MAX_UINT8 && y >= 0 && y <= MAX_UINT8) {
218 INT_FEATURE_STRUCT offset_f;
219 offset_f.X = x;
220 offset_f.Y = y;
221 offset_f.Theta = f.Theta;
222 int offset_index = IndexFeature(offset_f);
223 if (offset_index != index_feature && offset_index >= 0)
224 return offset_index; // Found one.
225 } else {
226 return -1; // Hit the edge of feature space.
227 }
228 }
229 } else if (dir == 2 || dir == -2) {
230 // Find the nearest existing index_feature.
231 for (int m = 1; m < kMaxOffsetDist; ++m) {
232 int theta = f.Theta + m * dir / 2;
233 INT_FEATURE_STRUCT offset_f;
234 offset_f.X = f.X;
235 offset_f.Y = f.Y;
236 offset_f.Theta = Modulo(theta, 256);
237 int offset_index = IndexFeature(offset_f);
238 if (offset_index != index_feature && offset_index >= 0)
239 return offset_index; // Found one.
240 }
241 }
242 return -1; // Nothing within the max distance.
243 }
244
245 } // namespace tesseract.