Document mosaicing

Document mosaicing is a process that stitches multiple, overlapping snapshot images of a document together to produce one large, high resolution composite. The document is slid under a stationary, over-the-desk camera by hand until all parts of the document are snapshotted by the camera's field of view. As the document slid under the camera, all motion of the document is coarsely tracked by the vision system. The document is periodically snapshotted such that the successive snapshots are overlap by about 50%. The system then finds the overlapped pairs and stitches them together repeatedly until all pairs are stitched together as one piece of document.

The document mosaicing can be divided into four main processes.

• Tracking
• Feature detecting
• Correspondences establishing
• Images mosaicing.

Tracking (simple correlation process)

In this process, the motion of the document slid under the camera is coarsely tracked by the system. Tracking is performed by a process called simple correlation process. In the first frame of snapshots, a small patch is extracted from the center of the image as a correlation template as shown in Figure 1. The correlation process is performed in the four times size of the patch area of the next frame. The motion of the paper is indicated by the peak in the correlation function. The peak in the correlation function indicates the motion of the paper. The template is resampled from this frame and the tracking continues until the template reaches the edge of the document. After the template reaches the edge of the document, another snapshot is taken and the tracking process performs repeatedly until the whole document is imaged. The snapshots are stored in an ordered list to facilitate pairing the overlapped images in later processes.

Feature detecting for efficient matching

Feature detection is the process of finding the transformation that aligns one image with another. There are two main approaches for feature detection.

• Feature-based approach : Motion parameters are estimated from point correspondences. This approach is suitable for the case that there is plenty supply of stable and detectable features.
• Featureless approach : When the motion between the two images is small, the motion parameters are estimated using optical flow. On the other hand, when the motion between the two images is large, the motion parameters are estimated using generalised cross-correlation. However, this approach requires a computationally expensive resources.

Each image is segmented into a hierarchy of columns, lines, and words to match the organised sets of features across images. Skew angle estimation and columns, lines and words finding are the examples of feature detection operations.

Skew angle estimation

Firstly, the angle that the rows of text make with the image raster lines (skew angle) is estimated. It is assumed to lie in the range of ±20°. A small patch of text in the image is selected randomly and then rotated in the range of ±20° until the variance of the pixel intensities of the patch summed along the raster lines is maximised. See Figure 2.

To ensure that the found skew angle is accurate, the document mosaic system performs calculation at many image patches and derive the final estimation by finding the average of the individual angles weighted by the variance of the pixel intensities of each patch.

Columns, lines and words finding

In this operation, the de-skewed document is intuitively segmented into a hierarchy of columns, lines and words. The sensitivity to illumination and page coloration of the de-skewed document can be removed by applying a Sobel operator to the de-skewed image and thresholding the output to obtain the binary gradient, de-skewed image. See Figure 3.

The operation can be roughly separated into 3 steps: column segmentation, line segmentation and word segmentation.

1. Columns are easily segmented from the binary gradient, de-skewed images by summing pixels vertically as shown in Figure 4.
2. Baselines of each row are segmented in the same way as the column segmentation process but horizontally.
3. Finally, individual words are segmented by applying the vertical process at each segmented row.

These segmentations are important because the document mosaic is created by matching the lower right corners of words in overlapping images pair. Moreover, the segmentation operation can organize the list of images in the context of a hierarchy of rows and column reliably.

The segmentation operation involves a considerable amount of summing in the binary gradient, de-skewed images, which done by construct a matrix of partial sums whose elements are given by

[math]\displaystyle{ p_{iy}=\sum_{u=1}^{i}\sum_{v=1}^{j}b_{uv} }[/math]

The matrix of partial sums is calculated in one pass through the binary gradient, de-skewed image.

[math]\displaystyle{ \sum_{u=u_{1}}^{u_{2}}\sum_{v=v_{1}}^{v_{2}}b_{uv}=p_{u_{2}v_{2}}+p_{u_{1}v_{1}}-p_{u_{1}v_{2}}-p_{u_{2}v_{1}} }[/math]

Correspondences establishing

The two images are now organized in hierarchy of linked lists in following structure :

• image=list of columns
• row=list of words
• column=list of row
• word=length (in pixels)

At the bottom of the structure, the length of each word is recorded for establishing correspondence between two images to reduce to search only the corresponding structures for the groups of words with the matching lengths.

Seed match finding

A seed match finding is done by comparing each row in image1 with each row in image2. The two rows are then compared to each other by every word. If the length (in pixel) of the two words (one from image1 and one from image2) and their immediate neighbours agree with each other within a predefined tolerance threshold (5 pixels, for example), then they are assumed to match. The row of each image is assumed a match if there are three or more word matches between the two rows. The seed match finding operation is terminated when two pairs of consecutive row match are found.

Match list building

After finishing a seed match finding operation, the next process is to build the match list to generate the correspondences points of the two images. The process is done by searching the matching pairs of rows away from the seed row.

Images mosaicing

Figure 5 : Mosaicing of two document images. Blurring is evident in the affine mosaic (b), but not in the mosaic constructed using a plane-to-plane projectivity (a). Close-ups of typical seams of (a) and (b) are shown in (c) and (d) respectively.

Given the list of corresponding points of the two images, finding the transformation of the overlapping portion of the images is the next process. Assuming a pinhole camera model, the transformation between pixels (u,v) of image 1 and pixels (u0, v0) of image 2 is demonstrated by a plane-to-plane projectivity.

[math]\displaystyle{ \left[\begin{array}{c} su'\\ sv'\\ s \end{array}\right]=\left[\begin{array}{ccc} p_{11} & p_{12} & p_{13}\\ p_{21} & p_{22} & p_{23}\\ p_{31} & p_{32} & 1 \end{array}\right]\left[\begin{array}{c} u\\ v\\ 1 \end{array}\right] \qquad Eq.1 }[/math]

The parameters of the projectivity is found from four pairs of matching points. RANSAC regression technique is used to reject outlying matches and estimate the projectivity from the remaining good matches.

The projectivity is fine-tuned using correlation at the corners of the overlapping portion to obtain four correspondences to sub-pixel accuracy. Therefore, image1 is then transformed into image2's coordinate system using Eq.1. The typical result of the process is shown in Figure 5.

Many images coping

Finally, the whole page composition is built up by mapping all the images into the coordinate system of an "anchor" image, which is normally the one nearest the page center. The transformations to the anchor frame are calculated by concatenating the pair-wise transformations found earlier. The raw document mosaic is shown in Figure 6.

However, there might be a problem of non-consecutive images that are overlap. This problem can be solved by performing Hierarchical sub-mosaics. As shown in Figure 7, image1 and image2 are registered, as are image3 and image4, creating two sub-mosaics. These two sub-mosaics are later stitched together in another mosaicing process.

Applied areas

There are various areas that the technique of document mosaicing can be applied to such as :

• Text segmentation of images of documents
• Document Recognition
• Interaction with paper on the digital desk
• Video mosaics for virtual environments
• Image registration techniques

Relevant research papers

• Huang, T.S.; Netravali, A.N. (1994). "Motion and structure from feature correspondences: A review". Proceedings of the IEEE 82 (2): 252–268. doi:10.1109/5.265351. 
• D.G. Lowe. [1] Perceptual Organization and Visual Recognition. Kluwer Academic Publishers, Boston, 1985.
• Irani, M.; Peleg, S. (1991). "Improving resolution by image registration". CVGIP: Graphical Models and Image Processing 53 (3): 231–239. doi:10.1016/1049-9652(91)90045-L. 
• Shivakumara, P.; Kumar, G. Hemantha; Guru, D. S.; Nagabhushan, P. (2006). "Sliding window based approach for document image mosaicing". Image and Vision Computing 24 (1): 94–100. doi:10.1016/j.imavis.2005.09.015. http://dl.acm.org/citation.cfm?id=1709248.1709280. 
• [2] Camera-Based Document Image Mosaicing. (n.d.). Image (Rochester, N.Y.), 1.
• Kumar, G. H.; Shivakumara, P.; Guru, D. S.; Nagabhushan (2004). "Document image mosaicing : A novel approach". Text 29 (3): 329–341. doi:10.1007/bf02703782. http://www.ias.ac.in/sadhana/Pdf2004Jun/Pe1149.pdf. 
• Sato, T., Ikeda, S., Kanbara, M., Iketani, A., Nakajima, N., Yokoya, N., & Yamada, K. (n.d.). High-resolution Video Mosaicing for Documents and Photos by Estimating Camera Motion. Mosaic A Journal for the Interdisciplinary Study of Literature.

Bibliography

• Anthony, Zappalá; Andrew Gee; Michael Taylor (1999). "Document mosaicing". Image and Vision Computing 17 (8): 589–595. doi:10.1016/S0262-8856(98)00178-4. 

External links

• Advanced Vision homepage