34 const float CTC::kMinProb_ = 1e-12;
36 const double CTC::kMaxExpArg_ = 80.0;
38 const double CTC::kMinTotalTimeProb_ = 1e-8;
40 const double CTC::kMinTotalFinalProb_ = 1e-6;
56 std::unique_ptr<CTC> ctc(
new CTC(labels, null_char, outputs));
57 if (!ctc->ComputeLabelLimits()) {
63 ctc->ComputeSimpleTargets(&simple_targets);
65 float bias_fraction = ctc->CalculateBiasFraction();
66 simple_targets *= bias_fraction;
67 ctc->outputs_ += simple_targets;
72 ctc->Forward(&log_alphas);
73 ctc->Backward(&log_betas);
75 log_alphas += log_betas;
76 ctc->NormalizeSequence(&log_alphas);
77 ctc->LabelsToClasses(log_alphas, targets);
84 : labels_(labels), outputs_(outputs), null_char_(null_char) {
85 num_timesteps_ = outputs.
dim1();
86 num_classes_ = outputs.
dim2();
87 num_labels_ = labels_.
size();
92 bool CTC::ComputeLabelLimits() {
95 int min_u = num_labels_ - 1;
96 if (labels_[min_u] == null_char_) --min_u;
97 for (
int t = num_timesteps_ - 1; t >= 0; --t) {
98 min_labels_[t] = min_u;
101 if (labels_[min_u] == null_char_ && min_u > 0 &&
102 labels_[min_u + 1] != labels_[min_u - 1]) {
107 int max_u = labels_[0] == null_char_;
108 for (
int t = 0; t < num_timesteps_; ++t) {
109 max_labels_[t] = max_u;
110 if (max_labels_[t] < min_labels_[t])
return false;
111 if (max_u + 1 < num_labels_) {
113 if (labels_[max_u] == null_char_ && max_u + 1 < num_labels_ &&
114 labels_[max_u + 1] != labels_[max_u - 1]) {
126 targets->
Resize(num_timesteps_, num_classes_, 0.0f);
129 ComputeWidthsAndMeans(&half_widths, &means);
130 for (
int l = 0; l < num_labels_; ++l) {
131 int label = labels_[l];
132 float left_half_width = half_widths[l];
133 float right_half_width = left_half_width;
135 if (label == null_char_) {
136 if (!NeededNull(l)) {
137 if ((l > 0 && mean == means[l - 1]) ||
138 (l + 1 < num_labels_ && mean == means[l + 1])) {
144 if (l > 0) left_half_width = mean - means[l - 1];
145 if (l + 1 < num_labels_) right_half_width = means[l + 1] - mean;
147 if (mean >= 0 && mean < num_timesteps_) targets->
put(mean, label, 1.0f);
149 float prob = 1.0f -
offset / left_half_width;
150 if (mean -
offset < num_timesteps_ &&
151 prob > targets->
get(mean -
offset, label)) {
152 targets->
put(mean -
offset, label, prob);
156 offset < right_half_width && mean +
offset < num_timesteps_;
158 float prob = 1.0f -
offset / right_half_width;
160 targets->
put(mean +
offset, label, prob);
173 int num_plus = 0, num_star = 0;
174 for (
int i = 0; i < num_labels_; ++i) {
175 if (labels_[i] != null_char_ || NeededNull(i))
183 float plus_size = 1.0f, star_size = 0.0f;
184 float total_floating = num_plus + num_star;
185 if (total_floating <= num_timesteps_) {
186 plus_size = star_size = num_timesteps_ / total_floating;
187 }
else if (num_star > 0) {
188 star_size =
static_cast<float>(num_timesteps_ - num_plus) / num_star;
191 float mean_pos = 0.0f;
192 for (
int i = 0; i < num_labels_; ++i) {
194 if (labels_[i] != null_char_ || NeededNull(i)) {
195 half_width = plus_size / 2.0f;
197 half_width = star_size / 2.0f;
199 mean_pos += half_width;
200 means->
push_back(static_cast<int>(mean_pos));
201 mean_pos += half_width;
209 int num_classes = outputs.
dim2();
210 const float* outputs_t = outputs[t];
211 for (
int c = 1; c < num_classes; ++c) {
212 if (outputs_t[c] > outputs_t[result]) result = c;
219 float CTC::CalculateBiasFraction() {
222 for (
int t = 0; t < num_timesteps_; ++t) {
223 int label = BestLabel(outputs_, t);
224 while (t + 1 < num_timesteps_ && BestLabel(outputs_, t + 1) == label) ++t;
225 if (label != null_char_) output_labels.
push_back(label);
230 for (
int l = 0; l < num_labels_; ++l) {
231 ++truth_counts[labels_[l]];
233 for (
int l = 0; l < output_labels.
size(); ++l) {
234 ++output_counts[output_labels[l]];
237 int true_pos = 0, false_pos = 0, total_labels = 0;
238 for (
int c = 0; c < num_classes_; ++c) {
239 if (c == null_char_)
continue;
240 int truth_count = truth_counts[c];
241 int ocr_count = output_counts[c];
242 if (truth_count > 0) {
243 total_labels += truth_count;
244 if (ocr_count > truth_count) {
245 true_pos += truth_count;
246 false_pos += ocr_count - truth_count;
248 true_pos += ocr_count;
254 if (total_labels == 0)
return 0.0f;
255 return exp(
MAX(true_pos - false_pos, 1) * log(kMinProb_) / total_labels);
261 static double LogSumExp(
double ln_x,
double ln_y) {
263 return ln_x + log1p(exp(ln_y - ln_x));
265 return ln_y + log1p(exp(ln_x - ln_y));
272 log_probs->
put(0, 0, log(outputs_(0, labels_[0])));
273 if (labels_[0] == null_char_)
274 log_probs->
put(0, 1, log(outputs_(0, labels_[1])));
275 for (
int t = 1; t < num_timesteps_; ++t) {
276 const float* outputs_t = outputs_[t];
277 for (
int u = min_labels_[t];
u <= max_labels_[t]; ++
u) {
279 double log_sum = log_probs->
get(t - 1,
u);
282 log_sum = LogSumExp(log_sum, log_probs->
get(t - 1,
u - 1));
285 if (
u >= 2 && labels_[
u - 1] == null_char_ &&
286 labels_[
u] != labels_[
u - 2]) {
287 log_sum = LogSumExp(log_sum, log_probs->
get(t - 1,
u - 2));
290 double label_prob = outputs_t[labels_[
u]];
291 log_sum += log(label_prob);
292 log_probs->
put(t,
u, log_sum);
300 log_probs->
put(num_timesteps_ - 1, num_labels_ - 1, 0.0);
301 if (labels_[num_labels_ - 1] == null_char_)
302 log_probs->
put(num_timesteps_ - 1, num_labels_ - 2, 0.0);
303 for (
int t = num_timesteps_ - 2; t >= 0; --t) {
304 const float* outputs_tp1 = outputs_[t + 1];
305 for (
int u = min_labels_[t];
u <= max_labels_[t]; ++
u) {
307 double log_sum = log_probs->
get(t + 1,
u) + log(outputs_tp1[labels_[
u]]);
309 if (u + 1 < num_labels_) {
310 double prev_prob = outputs_tp1[labels_[u + 1]];
312 LogSumExp(log_sum, log_probs->
get(t + 1, u + 1) + log(prev_prob));
315 if (u + 2 < num_labels_ && labels_[u + 1] == null_char_ &&
316 labels_[u] != labels_[u + 2]) {
317 double skip_prob = outputs_tp1[labels_[u + 2]];
319 LogSumExp(log_sum, log_probs->
get(t + 1, u + 2) + log(skip_prob));
321 log_probs->
put(t, u, log_sum);
328 double max_logprob = probs->
Max();
329 for (
int u = 0;
u < num_labels_; ++
u) {
331 for (
int t = 0; t < num_timesteps_; ++t) {
333 double prob = probs->
get(t,
u);
335 prob = ClippedExp(prob - max_logprob);
339 probs->
put(t,
u, prob);
344 if (total < kMinTotalTimeProb_) total = kMinTotalTimeProb_;
345 for (
int t = 0; t < num_timesteps_; ++t)
346 probs->
put(t,
u, probs->
get(t,
u) / total);
358 for (
int t = 0; t < num_timesteps_; ++t) {
359 float* targets_t = targets->
f(t);
361 for (
int u = 0;
u < num_labels_; ++
u) {
362 double prob = probs(t,
u);
366 if (prob > class_probs[labels_[
u]]) class_probs[labels_[
u]] = prob;
370 for (
int c = 0; c < num_classes_; ++c) {
371 targets_t[c] = class_probs[c];
372 if (class_probs[c] > class_probs[best_class]) best_class = c;
383 int num_timesteps = probs->
dim1();
384 int num_classes = probs->
dim2();
385 for (
int t = 0; t < num_timesteps; ++t) {
386 float* probs_t = (*probs)[t];
389 for (
int c = 0; c < num_classes; ++c) total += probs_t[c];
390 if (total < kMinTotalFinalProb_) total = kMinTotalFinalProb_;
392 double increment = 0.0;
393 for (
int c = 0; c < num_classes; ++c) {
394 double prob = probs_t[c] / total;
395 if (prob < kMinProb_) increment += kMinProb_ - prob;
399 for (
int c = 0; c < num_classes; ++c) {
400 float prob = probs_t[c] / total;
401 probs_t[c] =
MAX(prob, kMinProb_);
407 bool CTC::NeededNull(
int index)
const {
408 return labels_[index] == null_char_ && index > 0 && index + 1 < num_labels_ &&
409 labels_[index + 1] == labels_[index - 1];
void init_to_size(int size, T t)
void Resize(int size1, int size2, const T &empty)
static void NormalizeProbs(NetworkIO *probs)
void put(ICOORD pos, const T &thing)
static bool ComputeCTCTargets(const GenericVector< int > &truth_labels, int null_char, const GENERIC_2D_ARRAY< float > &outputs, NetworkIO *targets)