tesseract 4.1.1
Loading...
Searching...
No Matches
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
30namespace tesseract {
31
32const 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}
53int 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}
63void IntFeatureMap::DeleteMapFeature(int map_feature) {
64 feature_map_.Merge(-1, map_feature);
65 mapping_changed_ = true;
66}
67bool 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.
73void 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)
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.
113int 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
180void 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.
201int 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.
#define ASSERT_HOST(x)
Definition: errcode.h:88
int Modulo(int a, int b)
Definition: helpers.h:158
int IntCastRounded(double x)
Definition: helpers.h:175
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
void InitIntegerFX()
Definition: intfx.cpp:49
FCOORD FeatureDirection(uint8_t theta)
Definition: intfx.cpp:66
const int kMaxOffsetDist
int size() const
Definition: genericvector.h:72
Definition: points.h:189
void rotate(const FCOORD vec)
Definition: points.h:763
float y() const
Definition: points.h:210
float x() const
Definition: points.h:207
int CompactSize() const
Definition: indexmapbidi.h:61
int CompactToSparse(int compact_index) const
Definition: indexmapbidi.h:53
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:138
bool IsCompactDeleted(int index) const
Definition: indexmapbidi.h:130
Definition: cluster.h:32
int MapFeature(const INT_FEATURE_STRUCT &f) const
INT_FEATURE_STRUCT InverseIndexFeature(int index_feature) const
void DebugMapFeatures(const GenericVector< int > &map_features) 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)
const IntFeatureSpace & feature_space() const
Definition: intfeaturemap.h:60
int IndexFeature(const INT_FEATURE_STRUCT &f) const
int FinalizeMapping(SampleIterator *it)
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, GenericVector< int > *sorted_features) const
void print() const
Definition: intproto.h:145
const TrainingSample & GetSample() const
void MapSampleFeatures(const IntFeatureMap &feature_map)