A Brief Exploration of OCR Techniques: 4. Text Localization

OCR技术浅探：4. 文字定位 苏剑林 · 2016-06-24 · Machine Learning image OCR text search

After the first part, we've already extracted decent text features from the image. Next comes text localization. This mainly proceeds in two steps: 1) proximity search, whose goal is to circle out lines of text; 2) text segmentation, whose goal is to cut a single line of text into individual characters.

Proximity Search

We could search for connected regions in the extracted feature map and treat each connected region as a single Chinese character. This works for most characters, but fails for some simpler ones—like "小", "旦", "八", "元"—which lack connectivity and thus get split apart, as shown in Figure 13. So we need a proximity search algorithm to merge regions that likely belong to the same character, in order to obtain single lines of text regions.

Figure 13: Directly searching for connected regions splits characters like "元" apart

The purpose of proximity search is to perform dilation, "gluing together" regions that likely belong to the same character. If we dilate without first searching, the dilation happens in all directions simultaneously, which risks gluing together lines above and below. So we only allow a region to dilate in a single direction. It's precisely by searching for nearby regions that we determine the dilation direction (up, down, left, or right):

Proximity search*
Starting from a connected region, we can find its horizontal bounding rectangle and expand the connected region to fill that entire rectangle. When the distance between this region and its nearest neighboring region is smaller than a certain threshold, we consider dilating this rectangle, in the direction of the nearest neighboring region.

Since this involves proximity, we need a notion of distance. Below we give a reasonably sensible definition of distance.

Distance

Figure 14: Two example regions

As shown above, a rectangular region can be determined by its upper-left corner coordinates $(x,y)$ and lower-right corner coordinates $(z,w)$, with coordinates measured from the upper-left corner as the origin. The center of this region is $\left(\frac{x+w}{2},\frac{y+z}{2}\right)$. For the two regions $S$ and $S'$ in the figure, we can compute the difference between their center vectors:

$$(x_c,y_c)=\left(\frac{x'+w'}{2}-\frac{x+w}{2},\frac{y'+z'}{2}-\frac{y+z}{2}\right)\tag{10}$$

Directly using $\sqrt{x_c^2+y_c^2}$ as the distance wouldn't be sensible, since proximity here should be measured with respect to the boundaries, not the center points. Hence we need to subtract off the region lengths:

$$(x'_c,y'_c)=\left(x_c-\frac{w-x}{2}-\frac{w'-x'}{2},y_c-\frac{z-y}{2}-\frac{z'-y'}{2}\right)\tag{11}$$

The distance is then defined as

$$d(S,S')=\sqrt{[\max(x'_c,0)]^2+[\max(y'_c,0)]^2}\tag{12}$$

As for direction, this can simply be judged from the argument (angle) of $(x_c,y_c)$.

However, following the "proximity search*" method described above, it's easy to glue together two lines of text, one above the other. So, based on our horizontal-layout assumption, a better approach is to only allow horizontal dilation:

Proximity search
Starting from a connected region, we can find its horizontal bounding rectangle and expand the connected region to fill that entire rectangle. When the distance between this region and its nearest neighboring region is smaller than a certain threshold, we consider dilating this rectangle in the direction of the nearest neighboring region — but the dilation operation is only carried out if that direction is horizontal.

Results

With a distance metric in hand, we can compute the distance between every pair of connected regions and find each region's nearest neighbor. We then enlarge each region by a quarter, in the direction of its nearest neighbor, so that adjacent regions can potentially merge into a new region, thereby stitching the fragments back together.

Experiments show that this proximity-search approach effectively consolidates fragmented text, with the results shown in Figure 15.

Figure 15: Text regions circled after proximity search