# An Implementation of Document Image Reconstruction System on a Smart Device Using a 1D Histogram Calibration Algorithm

Authors: Lifeng Zhang; Qian Fan; Yujie Li; Yousuke Uchimura; Seiichi Serikawa
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In recent years, the smart devices equipped with imaging functions are widely spreading for consumer application. It is very convenient for people to record information using these devices. For example, people can photo one page of a book in a library or they can capture an interesting piece of news on the bulletin board when walking on the street. But sometimes, one shot full area image cannot give a sufficient resolution for OCR soft or for human visual recognition. Therefore, people would prefer to take several partial character images of a readable size and then stitch them together in an efficient way. In this study, we propose a print document acquisition method using a device with a video camera. A one-dimensional histogram based self-calibration algorithm is developed for calibration. Because the calculation cost is low, it can be installed on a smartphone. The simulation result shows that the calibration and stitching are well performed.


---

## Body

## 1. Introduction

In recent years, there is a growing trend for document digitization in order to reduce the cost of storage and administration of printed documents. The traditional method is using a digital still camera or a scanner. However, the scanner does not work in some situations like a wet surface or a bended surface. Moreover, fragile historical manuscripts cannot be acquired by a scanner. In a noncontact scanning device, a digital camera is used. Liang et al. proposed an approach estimating 3D document shape from texture flow [1, 2]. Stamatopoulos et al. presented a goal-oriented rectification methodology to compensate for undesirable document image distortions in order to improve the OCR result [3]. But their purpose for the processed targets is full page image. In this study, a low profile device is used. When taking a picture of an entire page area, the characters in the image tend to blur due to the limited resolution. In order to take photos for characters with a sufficient resolution, we take photos for several subareas for the whole image, respectively, and then stitch these images to get the whole document.When stitching natural images, a slight misalignment at the joint area of the reconstructed images cannot be detected clearly by human eyes. Somol and Haindl proposed a fast and adjustable suboptimal path search algorithm for finding minimum error boundaries between overlapping images [4]. It is a very attractive way for normalized nature images and patterned images. But for the character images, especially for the partially acquired images in which the camera state parameters are different, even a slight deviation at the joint part can be spotted immediately [5, 6]. This makes the produced documents hard to read and difficult to be recognized by an OCR software. To reduce such undesirable effect, each video frame is modified independently by estimating the camera state after the image acquisition so that the position matching can be performed accurately. Here we introduce a new approach for this purpose.When people go outside, nobody would always take a camera or scanner with them. But nowadays, most people have a smart device in which a builtin web camera is equipped. How to take the advantage of such a device is the biggest challenge of this research.


## 2. System Outline

The proposed system includes image acquisition, self-calibration, joint point detection, and image synthesis. The details are as follows.


### 2.1. Image Acquisition

In this research, a web camera is used for image acquisition. That means a huge data volume needs be deposited if we save all the data streams coming from the camera. Furthermore processing all of these data needs a lot of calculation cost. Because we assume that the proposed algorithm should work on a smartphone and should be used everywhere, such a heavy load might become the biggest weakness of our system. Therefore, an autoimage acquisition approach is proposed in this study. Because of the redundancy of each video frame, the neighboring two frames contain almost the same information. That is to say, every two frames with a half overlapped area are enough to fulfill our purpose. We move the web camera by hand in a zigzag line scan manner. When the distance from the previous acquired image is larger than the half of the picture size, the next picture is acquired automatically. Figure1 shows the flow chart of the image acquisition. In this work, optical flow is utilized for moving distance detection. In order to determine the flow instantly, a low computational cost method is employed. Because the printed document shows fewer changes in brightness value, we decided to use the gradient method called “Lucas-Kanade” which contributed in OpenCV library.Figure 1
Flow chart for image acquisitions.The details are as follows. If the image size isN×M pixels, then the amount of movement is N/2 or M/2, respectively. That means if the amount of movement along the X or Y-axis is x or y, respectively, the next image will be acquired when |x|≤N/2 or |y|≤M/2.


### 2.2. Calibration

For a handheld image acquisition system, the lighting condition, the imaging distance, and the imaging angle are changing frequently. Moreover the vibrations and view angle also influence the image quality. But such conditions cannot be improved perfectly by the users. Thus, we proposed a calibration method to deal with this problem.In our previous work [7], a self-calibration algorithm was introduced. We just show the outline of this algorithm and the result of each step of simulation in this study. Please go for details in our published paper.Distortion of the acquired image is assumed to occur due to the slope of the camera, which was separated into three different angles. Pitch angle, roll angle, and yaw angle are rotation angles ofX-axis,Y-axis, andZ-axis, respectively (see Figure 2). In this work, affine transformation and projective transformation are used to correct these angles.Figure 2
Definition of pitch, roll, and yaw angle for camera state estimation.Because the camera state is unknown at first, we cannot get all of the parameters that should be set for a projective transformation at one time. The parameters are detected for each angle, respectively, and the modification is performed step by step. The procedure is as follows:(a)
image binarization.(b)
modification of yaw angle,(c)
modification of roll angle,(d)
modification of pitch angle.The details of these steps are as follows.


#### 2.2.1. Binarization

Normally, the unique threshold cannot be determined for the binarization process because the text color and the brightness are changing in the ambient lighting environment. In this study, we provide an adaptive threshold [8] for each local area in the image for binarization processing. Consider
(1)B(i,j)={1ifmW×W(i,j)<l(i,j)*bias0otherwise,
where mW×W(i,j) is the local mean over a w=10 pixel-sized window and bias=52. Figure 3 shows one processing example.Local area image binarization.
(a)
Original image
(b)
Binarized image


#### 2.2.2. One-Dimensional Histogram

In this study we use a one-dimensional histogram to detect the correction parameters. Here is the overview.For a binarized character image, with consideration of the number of black pixels on the horizontal line, we get the one-dimensional histogram as shown in Figure4.Comparison of one-dimensional histogram on horizontal direction.
(a)
Histogram without distortion
(b)
Histogram with distortionIn Figure4(a), the histogram appears regularly like a bar chart if the characters are laid in a horizontal direction. Suppose the number of the bar is K and the most frequently appearing pixel number in each bar area is na-max⁡ (0<a<K;a:integer). In order to get the bar width, we find out two y positions Ra and La and when the pixel number is less than na-max⁡/4 on both sides of each bar, the width Wa=Ra-La of each bar (character line width) can be calculated, respectively, and the blank width between the two neighboring character lines can be calculated as Ib=La+1-Ra (0≤a≤K-1; b:integer). These parameters are used to modify the pitch angle described in following process.Generally, the obtained image has a distortion in some degree. The one-dimensional histogram rarely appears the same as Figure4(a). In most cases the bar blurs as in Figure 4(b). This confused us in determining the width of the character line and the distance between the two neighbor lines. In order to detect the parameters in this case, we developed a local histogram method as illustrated in Figure 5. In this study, we set three strap areas on the image in advance and then make one-dimensional histogram of them. In Figure 5(b) the resulting histograms reflect the condition of the character line’s distortion even if the overall character line is not horizontal. The modification parameters can be derived from such information. The details will be described in the following process.Local area 1D histogram detection.
(a)
Select strap area on image
(b)
1D histogram of each strap


#### 2.2.3. Yaw Angle Modification

In this research, all of the calibration parameters are derived from one-dimensional histogram. Such histograms were made from not only the overall image but also the local areas of an image. Each gravity point shown in Figure6(a) is calculated from its neighboring local area histograms. By calculating the line directions and the disappearing point from these gravity points, the yaw angle is modified as in Figure 6(c).Yaw angle modification procedure.
(a)
Gravity point detection result
(b)
Rotation angleθn detection
(c)
Yaw angle modified resultThe calculation of the gravity point of each gathered histogram is shown in Figure5(b). The gravity point gCk is calculated by
(2)gCk=∑y=lckrck‍B(y)·y∑y=lckrck‍B(y),
where k is the gathered histogram number, B(y) is the pixel number when the coordinate of each strap is y·lck, and rck is the boundary coordinate of each gathered histogram. The resulting image is shown in Figure 6. The average θ can be calculated from θn.In this study, the average rotation angleθ=(1/2K)∑n=02K‍θn is obtained as the yaw angle. The rotation is made by using an affine transform shown as:
(3)[x′y′1]=[cos⁡θ-sinθ0sinθcos⁡θ0001][xy1],[x′y′1]=[10Tx01Ty001][xy1],
where θ is the rotation parameter and Tx and Ty are the shift parameters of theX-axis andY-axis direction, respectively. By adopting the nearest neighboring interpolation and a rapid calculation method to give the absent pixels, we got the yaw angle calibration image shown as Figure 6(c).


#### 2.2.4. Roll Angle Modification

After yaw angle modification, we perform local histogram processing again to the previous result again, but this time we set two straps on the image automatically. And finally we find four gravity points on two separated character lines. For an image without roll angle distortion, these four points must be the vertex of a rectangle. Using this characteristic, the roll angle can be modified by using projective transformation.Generally, the projective transformation can be expressed as follows:(4)X=a1x+b1y+c1A0x+b0y+c0,Y=a2x+b2y+c2A0x+b0y+c0,
where X,Y are transformed coordinates and x,y are pretransformed coordinates. And a0, b0, c0, a1, b1, c1, a2, b2, and c2 are transformation parameters. If these transformation parameters are known, the projection can be made easily. But, at this stage, we need to figure out these unknown parameters first based on the coordinates of G1, G2, G3, and G4 which were obtained previously and the reasonable relationship of these points.As shown in (4), there are nine transformation parameters which are unknown. The known information is four detected gravity point coordinates and their expected positions. In fact, we can reduce one parameter by dividing c0 into both the numerator and the denominator of (4). The alternate form is shown as in
(5)X=a1x+b1y+c1A0x+b0y+1,Y=a2x+b2y+c2A0x+b0y+1.
The number of the unknown transform parameters is reduced to eight. Therefore, we can make eight equations as follows:
(6)A[a1b1c1a2b2c2a3b3]=[X1Y1X2Y2X3Y3X4Y4],
where
(7)A=[x1y11000-X1x1-X1y1000x1y11-Y1x1-Y1y1x2y21000-X2x2-X2y2000x2y21-Y2x2-Y2y2x3y31000-X3x3-X3y3000x3y31-Y3x3-Y3y3x4y41000-X4x4-X4y4000x4y41-Y4x4-Y4y4],
and then calculate the inverse matrix A-1; the eight unknown transform parameters can be obtained as
(8)[a1b1c1a2b2c2a3b3]=A-1[X1Y1X2Y2X3Y3X4Y4],
and finally the transform can be performed by using (5). The result is shown in Figure 7(b). Tables 1 and 2 show the gravity points coordinate before and after the roll angle calibration.Table 1
Gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
43
G
4
240
220Table 2
Calibrated gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
42
G
4
240
224Roll angle modification result.
(a)
Gravity point detection result
(b)
Gravity point after modification


#### 2.2.5. Pitch Angle Modification

Pitch angle modification parameter is estimated from an overall one-dimensional histogram that was created based on the above steps. Different from the previous two steps, the modification parameter cannot be derived from the gravity point. Because no difference can be obtained from the gravity point between the expected final result and the processing result at this moment, we have to estimate the modification parameters through the slight variation of the width of the horizontal direction’s histogram bar and the width of blank interval shown as Figure8. Figure 9 is a binarized image for making histogram shown as Figure 8 to acquire the modification parameters. Table 3 shows a measurement result of horizontal 1D histogram bar width and an interval width of each character line. Pitch angle modification parameter detection is an irritation procedure; thus Figure 10 seems to blur because of the cumulative error. But once the parameter is decided, the resulting image can be calculated just one time and no cumulative error occurs in the final calibration image (see Figure 10).Table 3
Width of each histogram bar and interval.
Index
Bar width[pixels]
Interval width[pixels]
1
8
10
2
9
10
3
9
11
4
8
11
5
9
12
6
8
12
7
9
12
8
9
12
9
9
13
10
10
—Figure 8
Calculate the line width and interval width.Figure 9
Pitch angle modification result.Figure 10
Final calibration modification result.Here we use the coordinates of the gravity points shown in Figure7(b) as the initial reference points, where the coordinates are (p1x,p1y), (p2x,p2y), (p3x,p3y), and (p4x,p4y) and the estimation coordinates of the modified points are (p1x′,p1y′), (p2x′,p2y′), (p3x′,p3y′), and (p4x′,p4y′), respectively. The width of histogram bar Wi, the width of blank interval Sj, NumW, and NumS are numbers of histogram bar and blank interval, respectively. Because we use an iterative algorithm for parameter estimation, first we define an evaluation function as
(9)E=compS-centerS2+compW-centerW2,
where
(10)centerW=∑i=1NumW‍Wi×i∑i=1NumW‍Wi,centerS=∑j=1NumS‍Sj×j∑j=1NumS‍Sj,compW=∑i=1NumW‍iNumW,compS=∑j=1NumS‍jNumS.IfcompW<centerW∩compS<centerS,
(11)p1x′=p1x+FW+FS2,p1y′=p1y,p2x′=p2x,p2y′=p2y,p3x′=p3x-FW+FS2,p3y′=p3y,p4x′=p4x,p4y′=p4y.Otherwise,(12)p1x′=p1x,p1y′=p1y,p2x′=p2x-FW+FS2,p2y′=p2y,p3x′=p3x,p3y′=p3yp4x′=p4x+FW+FS2,p4y′=p4y,
where FW=(compW-centerW)×(compW)2 and FS=(compS-centerS)×(compS)2.Perform the projective transformation iteratively using the estimated coordinates, and then evaluate the accuracy of the correction based on the evaluation functionE. Terminate the iteration when E≤T (T is threshold). Otherwise the algorithm remakes a one-dimensional histogram and repeats this procedure again. Finally, we get the completely modified result.In fact, the size normalization is also achieved at this step. Because the width of the histogram bar and the interval is calculated, we can use such figure as a universal parameter for the normalization procedure.


### 2.3. Image Synthesis

After calibrating all the acquired partial images of a character document, discovering the same area of the neighborhood images becomes the important task for image synthesis. In this study, we set four template subimages on a “base image to connect” and search the same local position on “the image to be connected.” Then, we calculate the “connecting coordinate” based on the resulting positions. Figure11 demonstrates the image connection. Because the surrounding areas are noisy and the neighbored images have an almost half overlapped area, only the center part of the subimages can be used for image synthesis.Figure 11
Illustration of image connection.


## 2.1. Image Acquisition

In this research, a web camera is used for image acquisition. That means a huge data volume needs be deposited if we save all the data streams coming from the camera. Furthermore processing all of these data needs a lot of calculation cost. Because we assume that the proposed algorithm should work on a smartphone and should be used everywhere, such a heavy load might become the biggest weakness of our system. Therefore, an autoimage acquisition approach is proposed in this study. Because of the redundancy of each video frame, the neighboring two frames contain almost the same information. That is to say, every two frames with a half overlapped area are enough to fulfill our purpose. We move the web camera by hand in a zigzag line scan manner. When the distance from the previous acquired image is larger than the half of the picture size, the next picture is acquired automatically. Figure1 shows the flow chart of the image acquisition. In this work, optical flow is utilized for moving distance detection. In order to determine the flow instantly, a low computational cost method is employed. Because the printed document shows fewer changes in brightness value, we decided to use the gradient method called “Lucas-Kanade” which contributed in OpenCV library.Figure 1
Flow chart for image acquisitions.The details are as follows. If the image size isN×M pixels, then the amount of movement is N/2 or M/2, respectively. That means if the amount of movement along the X or Y-axis is x or y, respectively, the next image will be acquired when |x|≤N/2 or |y|≤M/2.


## 2.2. Calibration

For a handheld image acquisition system, the lighting condition, the imaging distance, and the imaging angle are changing frequently. Moreover the vibrations and view angle also influence the image quality. But such conditions cannot be improved perfectly by the users. Thus, we proposed a calibration method to deal with this problem.In our previous work [7], a self-calibration algorithm was introduced. We just show the outline of this algorithm and the result of each step of simulation in this study. Please go for details in our published paper.Distortion of the acquired image is assumed to occur due to the slope of the camera, which was separated into three different angles. Pitch angle, roll angle, and yaw angle are rotation angles ofX-axis,Y-axis, andZ-axis, respectively (see Figure 2). In this work, affine transformation and projective transformation are used to correct these angles.Figure 2
Definition of pitch, roll, and yaw angle for camera state estimation.Because the camera state is unknown at first, we cannot get all of the parameters that should be set for a projective transformation at one time. The parameters are detected for each angle, respectively, and the modification is performed step by step. The procedure is as follows:(a)
image binarization.(b)
modification of yaw angle,(c)
modification of roll angle,(d)
modification of pitch angle.The details of these steps are as follows.


### 2.2.1. Binarization

Normally, the unique threshold cannot be determined for the binarization process because the text color and the brightness are changing in the ambient lighting environment. In this study, we provide an adaptive threshold [8] for each local area in the image for binarization processing. Consider
(1)B(i,j)={1ifmW×W(i,j)<l(i,j)*bias0otherwise,
where mW×W(i,j) is the local mean over a w=10 pixel-sized window and bias=52. Figure 3 shows one processing example.Local area image binarization.
(a)
Original image
(b)
Binarized image


### 2.2.2. One-Dimensional Histogram

In this study we use a one-dimensional histogram to detect the correction parameters. Here is the overview.For a binarized character image, with consideration of the number of black pixels on the horizontal line, we get the one-dimensional histogram as shown in Figure4.Comparison of one-dimensional histogram on horizontal direction.
(a)
Histogram without distortion
(b)
Histogram with distortionIn Figure4(a), the histogram appears regularly like a bar chart if the characters are laid in a horizontal direction. Suppose the number of the bar is K and the most frequently appearing pixel number in each bar area is na-max⁡ (0<a<K;a:integer). In order to get the bar width, we find out two y positions Ra and La and when the pixel number is less than na-max⁡/4 on both sides of each bar, the width Wa=Ra-La of each bar (character line width) can be calculated, respectively, and the blank width between the two neighboring character lines can be calculated as Ib=La+1-Ra (0≤a≤K-1; b:integer). These parameters are used to modify the pitch angle described in following process.Generally, the obtained image has a distortion in some degree. The one-dimensional histogram rarely appears the same as Figure4(a). In most cases the bar blurs as in Figure 4(b). This confused us in determining the width of the character line and the distance between the two neighbor lines. In order to detect the parameters in this case, we developed a local histogram method as illustrated in Figure 5. In this study, we set three strap areas on the image in advance and then make one-dimensional histogram of them. In Figure 5(b) the resulting histograms reflect the condition of the character line’s distortion even if the overall character line is not horizontal. The modification parameters can be derived from such information. The details will be described in the following process.Local area 1D histogram detection.
(a)
Select strap area on image
(b)
1D histogram of each strap


### 2.2.3. Yaw Angle Modification

In this research, all of the calibration parameters are derived from one-dimensional histogram. Such histograms were made from not only the overall image but also the local areas of an image. Each gravity point shown in Figure6(a) is calculated from its neighboring local area histograms. By calculating the line directions and the disappearing point from these gravity points, the yaw angle is modified as in Figure 6(c).Yaw angle modification procedure.
(a)
Gravity point detection result
(b)
Rotation angleθn detection
(c)
Yaw angle modified resultThe calculation of the gravity point of each gathered histogram is shown in Figure5(b). The gravity point gCk is calculated by
(2)gCk=∑y=lckrck‍B(y)·y∑y=lckrck‍B(y),
where k is the gathered histogram number, B(y) is the pixel number when the coordinate of each strap is y·lck, and rck is the boundary coordinate of each gathered histogram. The resulting image is shown in Figure 6. The average θ can be calculated from θn.In this study, the average rotation angleθ=(1/2K)∑n=02K‍θn is obtained as the yaw angle. The rotation is made by using an affine transform shown as:
(3)[x′y′1]=[cos⁡θ-sinθ0sinθcos⁡θ0001][xy1],[x′y′1]=[10Tx01Ty001][xy1],
where θ is the rotation parameter and Tx and Ty are the shift parameters of theX-axis andY-axis direction, respectively. By adopting the nearest neighboring interpolation and a rapid calculation method to give the absent pixels, we got the yaw angle calibration image shown as Figure 6(c).


### 2.2.4. Roll Angle Modification

After yaw angle modification, we perform local histogram processing again to the previous result again, but this time we set two straps on the image automatically. And finally we find four gravity points on two separated character lines. For an image without roll angle distortion, these four points must be the vertex of a rectangle. Using this characteristic, the roll angle can be modified by using projective transformation.Generally, the projective transformation can be expressed as follows:(4)X=a1x+b1y+c1A0x+b0y+c0,Y=a2x+b2y+c2A0x+b0y+c0,
where X,Y are transformed coordinates and x,y are pretransformed coordinates. And a0, b0, c0, a1, b1, c1, a2, b2, and c2 are transformation parameters. If these transformation parameters are known, the projection can be made easily. But, at this stage, we need to figure out these unknown parameters first based on the coordinates of G1, G2, G3, and G4 which were obtained previously and the reasonable relationship of these points.As shown in (4), there are nine transformation parameters which are unknown. The known information is four detected gravity point coordinates and their expected positions. In fact, we can reduce one parameter by dividing c0 into both the numerator and the denominator of (4). The alternate form is shown as in
(5)X=a1x+b1y+c1A0x+b0y+1,Y=a2x+b2y+c2A0x+b0y+1.
The number of the unknown transform parameters is reduced to eight. Therefore, we can make eight equations as follows:
(6)A[a1b1c1a2b2c2a3b3]=[X1Y1X2Y2X3Y3X4Y4],
where
(7)A=[x1y11000-X1x1-X1y1000x1y11-Y1x1-Y1y1x2y21000-X2x2-X2y2000x2y21-Y2x2-Y2y2x3y31000-X3x3-X3y3000x3y31-Y3x3-Y3y3x4y41000-X4x4-X4y4000x4y41-Y4x4-Y4y4],
and then calculate the inverse matrix A-1; the eight unknown transform parameters can be obtained as
(8)[a1b1c1a2b2c2a3b3]=A-1[X1Y1X2Y2X3Y3X4Y4],
and finally the transform can be performed by using (5). The result is shown in Figure 7(b). Tables 1 and 2 show the gravity points coordinate before and after the roll angle calibration.Table 1
Gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
43
G
4
240
220Table 2
Calibrated gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
42
G
4
240
224Roll angle modification result.
(a)
Gravity point detection result
(b)
Gravity point after modification


### 2.2.5. Pitch Angle Modification

Pitch angle modification parameter is estimated from an overall one-dimensional histogram that was created based on the above steps. Different from the previous two steps, the modification parameter cannot be derived from the gravity point. Because no difference can be obtained from the gravity point between the expected final result and the processing result at this moment, we have to estimate the modification parameters through the slight variation of the width of the horizontal direction’s histogram bar and the width of blank interval shown as Figure8. Figure 9 is a binarized image for making histogram shown as Figure 8 to acquire the modification parameters. Table 3 shows a measurement result of horizontal 1D histogram bar width and an interval width of each character line. Pitch angle modification parameter detection is an irritation procedure; thus Figure 10 seems to blur because of the cumulative error. But once the parameter is decided, the resulting image can be calculated just one time and no cumulative error occurs in the final calibration image (see Figure 10).Table 3
Width of each histogram bar and interval.
Index
Bar width[pixels]
Interval width[pixels]
1
8
10
2
9
10
3
9
11
4
8
11
5
9
12
6
8
12
7
9
12
8
9
12
9
9
13
10
10
—Figure 8
Calculate the line width and interval width.Figure 9
Pitch angle modification result.Figure 10
Final calibration modification result.Here we use the coordinates of the gravity points shown in Figure7(b) as the initial reference points, where the coordinates are (p1x,p1y), (p2x,p2y), (p3x,p3y), and (p4x,p4y) and the estimation coordinates of the modified points are (p1x′,p1y′), (p2x′,p2y′), (p3x′,p3y′), and (p4x′,p4y′), respectively. The width of histogram bar Wi, the width of blank interval Sj, NumW, and NumS are numbers of histogram bar and blank interval, respectively. Because we use an iterative algorithm for parameter estimation, first we define an evaluation function as
(9)E=compS-centerS2+compW-centerW2,
where
(10)centerW=∑i=1NumW‍Wi×i∑i=1NumW‍Wi,centerS=∑j=1NumS‍Sj×j∑j=1NumS‍Sj,compW=∑i=1NumW‍iNumW,compS=∑j=1NumS‍jNumS.IfcompW<centerW∩compS<centerS,
(11)p1x′=p1x+FW+FS2,p1y′=p1y,p2x′=p2x,p2y′=p2y,p3x′=p3x-FW+FS2,p3y′=p3y,p4x′=p4x,p4y′=p4y.Otherwise,(12)p1x′=p1x,p1y′=p1y,p2x′=p2x-FW+FS2,p2y′=p2y,p3x′=p3x,p3y′=p3yp4x′=p4x+FW+FS2,p4y′=p4y,
where FW=(compW-centerW)×(compW)2 and FS=(compS-centerS)×(compS)2.Perform the projective transformation iteratively using the estimated coordinates, and then evaluate the accuracy of the correction based on the evaluation functionE. Terminate the iteration when E≤T (T is threshold). Otherwise the algorithm remakes a one-dimensional histogram and repeats this procedure again. Finally, we get the completely modified result.In fact, the size normalization is also achieved at this step. Because the width of the histogram bar and the interval is calculated, we can use such figure as a universal parameter for the normalization procedure.


## 2.2.1. Binarization

Normally, the unique threshold cannot be determined for the binarization process because the text color and the brightness are changing in the ambient lighting environment. In this study, we provide an adaptive threshold [8] for each local area in the image for binarization processing. Consider
(1)B(i,j)={1ifmW×W(i,j)<l(i,j)*bias0otherwise,
where mW×W(i,j) is the local mean over a w=10 pixel-sized window and bias=52. Figure 3 shows one processing example.Local area image binarization.
(a)
Original image
(b)
Binarized image


## 2.2.2. One-Dimensional Histogram

In this study we use a one-dimensional histogram to detect the correction parameters. Here is the overview.For a binarized character image, with consideration of the number of black pixels on the horizontal line, we get the one-dimensional histogram as shown in Figure4.Comparison of one-dimensional histogram on horizontal direction.
(a)
Histogram without distortion
(b)
Histogram with distortionIn Figure4(a), the histogram appears regularly like a bar chart if the characters are laid in a horizontal direction. Suppose the number of the bar is K and the most frequently appearing pixel number in each bar area is na-max⁡ (0<a<K;a:integer). In order to get the bar width, we find out two y positions Ra and La and when the pixel number is less than na-max⁡/4 on both sides of each bar, the width Wa=Ra-La of each bar (character line width) can be calculated, respectively, and the blank width between the two neighboring character lines can be calculated as Ib=La+1-Ra (0≤a≤K-1; b:integer). These parameters are used to modify the pitch angle described in following process.Generally, the obtained image has a distortion in some degree. The one-dimensional histogram rarely appears the same as Figure4(a). In most cases the bar blurs as in Figure 4(b). This confused us in determining the width of the character line and the distance between the two neighbor lines. In order to detect the parameters in this case, we developed a local histogram method as illustrated in Figure 5. In this study, we set three strap areas on the image in advance and then make one-dimensional histogram of them. In Figure 5(b) the resulting histograms reflect the condition of the character line’s distortion even if the overall character line is not horizontal. The modification parameters can be derived from such information. The details will be described in the following process.Local area 1D histogram detection.
(a)
Select strap area on image
(b)
1D histogram of each strap


## 2.2.3. Yaw Angle Modification

In this research, all of the calibration parameters are derived from one-dimensional histogram. Such histograms were made from not only the overall image but also the local areas of an image. Each gravity point shown in Figure6(a) is calculated from its neighboring local area histograms. By calculating the line directions and the disappearing point from these gravity points, the yaw angle is modified as in Figure 6(c).Yaw angle modification procedure.
(a)
Gravity point detection result
(b)
Rotation angleθn detection
(c)
Yaw angle modified resultThe calculation of the gravity point of each gathered histogram is shown in Figure5(b). The gravity point gCk is calculated by
(2)gCk=∑y=lckrck‍B(y)·y∑y=lckrck‍B(y),
where k is the gathered histogram number, B(y) is the pixel number when the coordinate of each strap is y·lck, and rck is the boundary coordinate of each gathered histogram. The resulting image is shown in Figure 6. The average θ can be calculated from θn.In this study, the average rotation angleθ=(1/2K)∑n=02K‍θn is obtained as the yaw angle. The rotation is made by using an affine transform shown as:
(3)[x′y′1]=[cos⁡θ-sinθ0sinθcos⁡θ0001][xy1],[x′y′1]=[10Tx01Ty001][xy1],
where θ is the rotation parameter and Tx and Ty are the shift parameters of theX-axis andY-axis direction, respectively. By adopting the nearest neighboring interpolation and a rapid calculation method to give the absent pixels, we got the yaw angle calibration image shown as Figure 6(c).


## 2.2.4. Roll Angle Modification

After yaw angle modification, we perform local histogram processing again to the previous result again, but this time we set two straps on the image automatically. And finally we find four gravity points on two separated character lines. For an image without roll angle distortion, these four points must be the vertex of a rectangle. Using this characteristic, the roll angle can be modified by using projective transformation.Generally, the projective transformation can be expressed as follows:(4)X=a1x+b1y+c1A0x+b0y+c0,Y=a2x+b2y+c2A0x+b0y+c0,
where X,Y are transformed coordinates and x,y are pretransformed coordinates. And a0, b0, c0, a1, b1, c1, a2, b2, and c2 are transformation parameters. If these transformation parameters are known, the projection can be made easily. But, at this stage, we need to figure out these unknown parameters first based on the coordinates of G1, G2, G3, and G4 which were obtained previously and the reasonable relationship of these points.As shown in (4), there are nine transformation parameters which are unknown. The known information is four detected gravity point coordinates and their expected positions. In fact, we can reduce one parameter by dividing c0 into both the numerator and the denominator of (4). The alternate form is shown as in
(5)X=a1x+b1y+c1A0x+b0y+1,Y=a2x+b2y+c2A0x+b0y+1.
The number of the unknown transform parameters is reduced to eight. Therefore, we can make eight equations as follows:
(6)A[a1b1c1a2b2c2a3b3]=[X1Y1X2Y2X3Y3X4Y4],
where
(7)A=[x1y11000-X1x1-X1y1000x1y11-Y1x1-Y1y1x2y21000-X2x2-X2y2000x2y21-Y2x2-Y2y2x3y31000-X3x3-X3y3000x3y31-Y3x3-Y3y3x4y41000-X4x4-X4y4000x4y41-Y4x4-Y4y4],
and then calculate the inverse matrix A-1; the eight unknown transform parameters can be obtained as
(8)[a1b1c1a2b2c2a3b3]=A-1[X1Y1X2Y2X3Y3X4Y4],
and finally the transform can be performed by using (5). The result is shown in Figure 7(b). Tables 1 and 2 show the gravity points coordinate before and after the roll angle calibration.Table 1
Gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
43
G
4
240
220Table 2
Calibrated gravity points coordinate.
Gravity point
x
y
G
1
80
42
G
2
80
224
G
3
240
42
G
4
240
224Roll angle modification result.
(a)
Gravity point detection result
(b)
Gravity point after modification


## 2.2.5. Pitch Angle Modification

Pitch angle modification parameter is estimated from an overall one-dimensional histogram that was created based on the above steps. Different from the previous two steps, the modification parameter cannot be derived from the gravity point. Because no difference can be obtained from the gravity point between the expected final result and the processing result at this moment, we have to estimate the modification parameters through the slight variation of the width of the horizontal direction’s histogram bar and the width of blank interval shown as Figure8. Figure 9 is a binarized image for making histogram shown as Figure 8 to acquire the modification parameters. Table 3 shows a measurement result of horizontal 1D histogram bar width and an interval width of each character line. Pitch angle modification parameter detection is an irritation procedure; thus Figure 10 seems to blur because of the cumulative error. But once the parameter is decided, the resulting image can be calculated just one time and no cumulative error occurs in the final calibration image (see Figure 10).Table 3
Width of each histogram bar and interval.
Index
Bar width[pixels]
Interval width[pixels]
1
8
10
2
9
10
3
9
11
4
8
11
5
9
12
6
8
12
7
9
12
8
9
12
9
9
13
10
10
—Figure 8
Calculate the line width and interval width.Figure 9
Pitch angle modification result.Figure 10
Final calibration modification result.Here we use the coordinates of the gravity points shown in Figure7(b) as the initial reference points, where the coordinates are (p1x,p1y), (p2x,p2y), (p3x,p3y), and (p4x,p4y) and the estimation coordinates of the modified points are (p1x′,p1y′), (p2x′,p2y′), (p3x′,p3y′), and (p4x′,p4y′), respectively. The width of histogram bar Wi, the width of blank interval Sj, NumW, and NumS are numbers of histogram bar and blank interval, respectively. Because we use an iterative algorithm for parameter estimation, first we define an evaluation function as
(9)E=compS-centerS2+compW-centerW2,
where
(10)centerW=∑i=1NumW‍Wi×i∑i=1NumW‍Wi,centerS=∑j=1NumS‍Sj×j∑j=1NumS‍Sj,compW=∑i=1NumW‍iNumW,compS=∑j=1NumS‍jNumS.IfcompW<centerW∩compS<centerS,
(11)p1x′=p1x+FW+FS2,p1y′=p1y,p2x′=p2x,p2y′=p2y,p3x′=p3x-FW+FS2,p3y′=p3y,p4x′=p4x,p4y′=p4y.Otherwise,(12)p1x′=p1x,p1y′=p1y,p2x′=p2x-FW+FS2,p2y′=p2y,p3x′=p3x,p3y′=p3yp4x′=p4x+FW+FS2,p4y′=p4y,
where FW=(compW-centerW)×(compW)2 and FS=(compS-centerS)×(compS)2.Perform the projective transformation iteratively using the estimated coordinates, and then evaluate the accuracy of the correction based on the evaluation functionE. Terminate the iteration when E≤T (T is threshold). Otherwise the algorithm remakes a one-dimensional histogram and repeats this procedure again. Finally, we get the completely modified result.In fact, the size normalization is also achieved at this step. Because the width of the histogram bar and the interval is calculated, we can use such figure as a universal parameter for the normalization procedure.


## 2.3. Image Synthesis

After calibrating all the acquired partial images of a character document, discovering the same area of the neighborhood images becomes the important task for image synthesis. In this study, we set four template subimages on a “base image to connect” and search the same local position on “the image to be connected.” Then, we calculate the “connecting coordinate” based on the resulting positions. Figure11 demonstrates the image connection. Because the surrounding areas are noisy and the neighbored images have an almost half overlapped area, only the center part of the subimages can be used for image synthesis.Figure 11
Illustration of image connection.


## 3. Simulation

### 3.1. Comparison Experiment

Because this research is designed for smart device using, after developing the algorithm on a PC system, implementation for Android device is also needed.The PC system construction is ACER notebook which has a core i5 1.6 GHz processor, 4 GB memory, and a web camera (Logicool Webcam Pro 9000). The development tool is Microsoft Visual Studio 2010 professional edition, and OpenCV1.1 library was included.The Android tablet is SONY SGPT112JP/S which has a NVIDIA Tegra 2 mobile processor, 1 GB main memory, and a mobile CMOS sensor HD camera; the display is 9.4 inch WXGA. The development tool is Eclipse with Android SDK, also OpenCV 2.3.4 for Android was included. Table4 shows other specifications.Table 4
Experiment conditions.
Camera imaging size
5.11 M pixels
Video size
640 × 480
Video codec
AVC/H.264
Frame rate
29.63 fpsIn order to evaluate the performance of these two systems, the same images are used which are captured by a web camera (Logicool Webcam Pro 9000; frame size:640×480). The left side of Figure 12 is the original images and the right side of Figure 12 is PC system calibrated images, respectively. The processed image is initialized to the same character scale and trimmed off the surrounding area which includes pseudo information. Therefore, the size is different from the original one. Figure 13 shows the connection result of the PC system. The processing time is within 5 seconds.Figure 12
Calibration results. Left: original images and right: calibrated images.Figure 13
Connection result on PC with Windows 7.Figure14 shows the comparison of the image calibration results between the PC system and the Android tablet. The size of the left images is different from the right side. This means that the result of these two systems is somehow different. We made investigation about this problem and realized that the difference is mainly caused by the calculation accuracy and the version difference of OpenCV library. Figure 15 shows the connection result performed on Android tablet. The processing time is about 30 seconds.Figure 14
Comparison of calibration results processed by Windows 7 and Android 4.1 tablet. Left: processed by Windows 7 and right: processed by Android 4.1 tablet.Figure 15
Connection result by Android 4.1 tablet.Table5 shows the tolerant angle of each direction defined in Figure 2. Ordinarily, people can take a video with a portable device within this range easily. Although it is possible to extend the tolerant angles using an additional algorithm, it will cost more calculation time. Such tolerant angles are considered enough in this study.Table 5
Tolerance angle.
Range[deg.]
Yaw angle
−35°~35°
Row angle
−17°~17°
Pitch angle
−15°~15°


### 3.2. Overall Experiment on Android Pad

In order to test the performance of implementation on a smart device, an overall experiment has been performed.The image processing on a portable device is a time-consuming process. Therefore, we divide the whole process into two parts. One is for video acquisition and the other is for image synthesis. The base function of smart device was used for image acquisition and the video file is stored on the flush memory of the device. Image synthesis is performed using all of the procedure introduced in this work.Approximately a 10-second video was taken with a target as shown in Figure16. 23 photo frames were selected automatically. Figure 17 shows a part of the autocaptured frames and their autocalibration results. Figure 18 shows the completely reconstructed document image. Table 6 shows the time consumption.Table 6
Processing time.
Procedure
Processing time[sec]
Video frame selection
146
Calibration
97
Image synthesis
22
Total
265Figure 16
Original printed document.Calibration result examples.
(a)
Autocaptured frames
(b)
Autocalibrated imagesFigure 18
Completely reconstructed document image.


## 3.1. Comparison Experiment

Because this research is designed for smart device using, after developing the algorithm on a PC system, implementation for Android device is also needed.The PC system construction is ACER notebook which has a core i5 1.6 GHz processor, 4 GB memory, and a web camera (Logicool Webcam Pro 9000). The development tool is Microsoft Visual Studio 2010 professional edition, and OpenCV1.1 library was included.The Android tablet is SONY SGPT112JP/S which has a NVIDIA Tegra 2 mobile processor, 1 GB main memory, and a mobile CMOS sensor HD camera; the display is 9.4 inch WXGA. The development tool is Eclipse with Android SDK, also OpenCV 2.3.4 for Android was included. Table4 shows other specifications.Table 4
Experiment conditions.
Camera imaging size
5.11 M pixels
Video size
640 × 480
Video codec
AVC/H.264
Frame rate
29.63 fpsIn order to evaluate the performance of these two systems, the same images are used which are captured by a web camera (Logicool Webcam Pro 9000; frame size:640×480). The left side of Figure 12 is the original images and the right side of Figure 12 is PC system calibrated images, respectively. The processed image is initialized to the same character scale and trimmed off the surrounding area which includes pseudo information. Therefore, the size is different from the original one. Figure 13 shows the connection result of the PC system. The processing time is within 5 seconds.Figure 12
Calibration results. Left: original images and right: calibrated images.Figure 13
Connection result on PC with Windows 7.Figure14 shows the comparison of the image calibration results between the PC system and the Android tablet. The size of the left images is different from the right side. This means that the result of these two systems is somehow different. We made investigation about this problem and realized that the difference is mainly caused by the calculation accuracy and the version difference of OpenCV library. Figure 15 shows the connection result performed on Android tablet. The processing time is about 30 seconds.Figure 14
Comparison of calibration results processed by Windows 7 and Android 4.1 tablet. Left: processed by Windows 7 and right: processed by Android 4.1 tablet.Figure 15
Connection result by Android 4.1 tablet.Table5 shows the tolerant angle of each direction defined in Figure 2. Ordinarily, people can take a video with a portable device within this range easily. Although it is possible to extend the tolerant angles using an additional algorithm, it will cost more calculation time. Such tolerant angles are considered enough in this study.Table 5
Tolerance angle.
Range[deg.]
Yaw angle
−35°~35°
Row angle
−17°~17°
Pitch angle
−15°~15°


## 3.2. Overall Experiment on Android Pad

In order to test the performance of implementation on a smart device, an overall experiment has been performed.The image processing on a portable device is a time-consuming process. Therefore, we divide the whole process into two parts. One is for video acquisition and the other is for image synthesis. The base function of smart device was used for image acquisition and the video file is stored on the flush memory of the device. Image synthesis is performed using all of the procedure introduced in this work.Approximately a 10-second video was taken with a target as shown in Figure16. 23 photo frames were selected automatically. Figure 17 shows a part of the autocaptured frames and their autocalibration results. Figure 18 shows the completely reconstructed document image. Table 6 shows the time consumption.Table 6
Processing time.
Procedure
Processing time[sec]
Video frame selection
146
Calibration
97
Image synthesis
22
Total
265Figure 16
Original printed document.Calibration result examples.
(a)
Autocaptured frames
(b)
Autocalibrated imagesFigure 18
Completely reconstructed document image.


## 4. Conclusion

In this work, we implement the self-calibration algorithm for partial character image synthesis on a PC and on an Android tablet separately. The simulation results show that the distortions were well repaired, and the image was reconstructed well on a PC system, but the Android system still shows a low performance because of the lack of calculation ability. For future work, we would improve the image synthesis algorithm to get a more satisfying result and speed up the calculation on a tablet device so that it can better meet the needs for practical application.



---

*Source: 313452-2014-06-12.xml*