35 const float CTC::kMinProb_ = 1e-12;
37 const double CTC::kMaxExpArg_ = 80.0;
39 const double CTC::kMinTotalTimeProb_ = 1e-8;
41 const double CTC::kMinTotalFinalProb_ = 1e-6;
57 std::unique_ptr<CTC> ctc(
new CTC(labels, null_char, outputs));
58 if (!ctc->ComputeLabelLimits()) {
64 ctc->ComputeSimpleTargets(&simple_targets);
66 float bias_fraction = ctc->CalculateBiasFraction();
67 simple_targets *= bias_fraction;
68 ctc->outputs_ += simple_targets;
73 ctc->Forward(&log_alphas);
74 ctc->Backward(&log_betas);
76 log_alphas += log_betas;
77 ctc->NormalizeSequence(&log_alphas);
78 ctc->LabelsToClasses(log_alphas, targets);
85 : labels_(labels), outputs_(outputs),
null_char_(null_char) {
86 num_timesteps_ = outputs.
dim1();
87 num_classes_ = outputs.
dim2();
88 num_labels_ = labels_.
size();
93 bool CTC::ComputeLabelLimits() {
96 int min_u = num_labels_ - 1;
97 if (labels_[min_u] == null_char_) --min_u;
98 for (
int t = num_timesteps_ - 1; t >= 0; --t) {
99 min_labels_[t] = min_u;
102 if (labels_[min_u] == null_char_ && min_u > 0 &&
103 labels_[min_u + 1] != labels_[min_u - 1]) {
108 int max_u = labels_[0] == null_char_;
109 for (
int t = 0; t < num_timesteps_; ++t) {
110 max_labels_[t] = max_u;
111 if (max_labels_[t] < min_labels_[t])
return false;
112 if (max_u + 1 < num_labels_) {
114 if (labels_[max_u] == null_char_ && max_u + 1 < num_labels_ &&
115 labels_[max_u + 1] != labels_[max_u - 1]) {
127 targets->
Resize(num_timesteps_, num_classes_, 0.0f);
130 ComputeWidthsAndMeans(&half_widths, &means);
131 for (
int l = 0; l < num_labels_; ++l) {
132 int label = labels_[l];
133 float left_half_width = half_widths[l];
134 float right_half_width = left_half_width;
136 if (label == null_char_) {
137 if (!NeededNull(l)) {
138 if ((l > 0 && mean == means[l - 1]) ||
139 (l + 1 < num_labels_ && mean == means[l + 1])) {
145 if (l > 0) left_half_width = mean - means[l - 1];
146 if (l + 1 < num_labels_) right_half_width = means[l + 1] - mean;
148 if (mean >= 0 && mean < num_timesteps_) targets->
put(mean, label, 1.0f);
149 for (
int offset = 1; offset < left_half_width && mean >= offset; ++offset) {
150 float prob = 1.0f - offset / left_half_width;
151 if (mean - offset < num_timesteps_ &&
152 prob > targets->
get(mean - offset, label)) {
153 targets->
put(mean - offset, label, prob);
157 offset < right_half_width && mean + offset < num_timesteps_;
159 float prob = 1.0f - offset / right_half_width;
160 if (mean + offset >= 0 && prob > targets->
get(mean + offset, label)) {
161 targets->
put(mean + offset, label, prob);
174 int num_plus = 0, num_star = 0;
175 for (
int i = 0; i < num_labels_; ++i) {
176 if (labels_[i] != null_char_ || NeededNull(i))
184 float plus_size = 1.0f, star_size = 0.0f;
185 float total_floating = num_plus + num_star;
186 if (total_floating <= num_timesteps_) {
187 plus_size = star_size = num_timesteps_ / total_floating;
188 }
else if (num_star > 0) {
189 star_size = static_cast<float>(num_timesteps_ - num_plus) / num_star;
192 float mean_pos = 0.0f;
193 for (
int i = 0; i < num_labels_; ++i) {
195 if (labels_[i] != null_char_ || NeededNull(i)) {
196 half_width = plus_size / 2.0f;
198 half_width = star_size / 2.0f;
200 mean_pos += half_width;
201 means->
push_back(static_cast<int>(mean_pos));
202 mean_pos += half_width;
210 int num_classes = outputs.
dim2();
211 const float* outputs_t = outputs[t];
212 for (
int c = 1; c < num_classes; ++c) {
213 if (outputs_t[c] > outputs_t[result]) result = c;
220 float CTC::CalculateBiasFraction() {
223 for (
int t = 0; t < num_timesteps_; ++t) {
224 int label = BestLabel(outputs_, t);
225 while (t + 1 < num_timesteps_ && BestLabel(outputs_, t + 1) == label) ++t;
226 if (label != null_char_) output_labels.
push_back(label);
231 for (
int l = 0; l < num_labels_; ++l) {
232 ++truth_counts[labels_[l]];
234 for (
int l = 0; l < output_labels.
size(); ++l) {
235 ++output_counts[output_labels[l]];
238 int true_pos = 0, false_pos = 0, total_labels = 0;
239 for (
int c = 0; c < num_classes_; ++c) {
240 if (c == null_char_)
continue;
241 int truth_count = truth_counts[c];
242 int ocr_count = output_counts[c];
243 if (truth_count > 0) {
244 total_labels += truth_count;
245 if (ocr_count > truth_count) {
246 true_pos += truth_count;
247 false_pos += ocr_count - truth_count;
249 true_pos += ocr_count;
255 if (total_labels == 0)
return 0.0f;
256 return exp(std::max(true_pos - false_pos, 1) *
log(kMinProb_) / total_labels);
262 static double LogSumExp(
double ln_x,
double ln_y) {
264 return ln_x + log1p(exp(ln_y - ln_x));
266 return ln_y + log1p(exp(ln_x - ln_y));
272 log_probs->
Resize(num_timesteps_, num_labels_, -FLT_MAX);
273 log_probs->
put(0, 0,
log(outputs_(0, labels_[0])));
274 if (labels_[0] == null_char_)
275 log_probs->
put(0, 1,
log(outputs_(0, labels_[1])));
276 for (
int t = 1; t < num_timesteps_; ++t) {
277 const float* outputs_t = outputs_[t];
278 for (
int u = min_labels_[t]; u <= max_labels_[t]; ++u) {
280 double log_sum = log_probs->
get(t - 1, u);
283 log_sum = LogSumExp(log_sum, log_probs->
get(t - 1, u - 1));
286 if (u >= 2 && labels_[u - 1] == null_char_ &&
287 labels_[u] != labels_[u - 2]) {
288 log_sum = LogSumExp(log_sum, log_probs->
get(t - 1, u - 2));
291 double label_prob = outputs_t[labels_[u]];
292 log_sum +=
log(label_prob);
293 log_probs->
put(t, u, log_sum);
300 log_probs->
Resize(num_timesteps_, num_labels_, -FLT_MAX);
301 log_probs->
put(num_timesteps_ - 1, num_labels_ - 1, 0.0);
302 if (labels_[num_labels_ - 1] == null_char_)
303 log_probs->
put(num_timesteps_ - 1, num_labels_ - 2, 0.0);
304 for (
int t = num_timesteps_ - 2; t >= 0; --t) {
305 const float* outputs_tp1 = outputs_[t + 1];
306 for (
int u = min_labels_[t]; u <= max_labels_[t]; ++u) {
308 double log_sum = log_probs->
get(t + 1, u) +
log(outputs_tp1[labels_[u]]);
310 if (u + 1 < num_labels_) {
311 double prev_prob = outputs_tp1[labels_[u + 1]];
313 LogSumExp(log_sum, log_probs->
get(t + 1, u + 1) +
log(prev_prob));
316 if (u + 2 < num_labels_ && labels_[u + 1] == null_char_ &&
317 labels_[u] != labels_[u + 2]) {
318 double skip_prob = outputs_tp1[labels_[u + 2]];
320 LogSumExp(log_sum, log_probs->
get(t + 1, u + 2) +
log(skip_prob));
322 log_probs->
put(t, u, log_sum);
329 double max_logprob = probs->
Max();
330 for (
int u = 0; u < num_labels_; ++u) {
332 for (
int t = 0; t < num_timesteps_; ++t) {
334 double prob = probs->
get(t, u);
336 prob = ClippedExp(prob - max_logprob);
340 probs->
put(t, u, prob);
345 if (total < kMinTotalTimeProb_) total = kMinTotalTimeProb_;
346 for (
int t = 0; t < num_timesteps_; ++t)
347 probs->
put(t, u, probs->
get(t, u) / total);
355 NetworkIO* targets)
const {
359 for (
int t = 0; t < num_timesteps_; ++t) {
360 float* targets_t = targets->f(t);
362 for (
int u = 0; u < num_labels_; ++u) {
363 double prob = probs(t, u);
367 if (prob > class_probs[labels_[u]]) class_probs[labels_[u]] = prob;
371 for (
int c = 0; c < num_classes_; ++c) {
372 targets_t[c] = class_probs[c];
373 if (class_probs[c] > class_probs[best_class]) best_class = c;
384 int num_timesteps = probs->
dim1();
385 int num_classes = probs->
dim2();
386 for (
int t = 0; t < num_timesteps; ++t) {
387 float* probs_t = (*probs)[t];
390 for (
int c = 0; c < num_classes; ++c) total += probs_t[c];
391 if (total < kMinTotalFinalProb_) total = kMinTotalFinalProb_;
393 double increment = 0.0;
394 for (
int c = 0; c < num_classes; ++c) {
395 double prob = probs_t[c] / total;
396 if (prob < kMinProb_) increment += kMinProb_ - prob;
400 for (
int c = 0; c < num_classes; ++c) {
401 float prob = probs_t[c] / total;
402 probs_t[c] = std::max(prob, kMinProb_);
408 bool CTC::NeededNull(
int index)
const {
409 return labels_[index] == null_char_ && index > 0 && index + 1 < num_labels_ &&
410 labels_[index + 1] == labels_[index - 1];