実験中です
23 Jun 2011-
随時更新や校正をします。
はじめに
画像処理関連は特許の問題が難しいので、ツール配布はしません。
VisualStudioでテストしていますが、ソリューションなし、関連DLLなしでの提示になります。
ソースファイルの著作権については、BSDライセンスに従ってください。
中綴じ雑誌のスキャン
スキャナで書籍を取り込むときに、意外と面倒なのが中綴じの雑誌です。
真ん中で分断して取り込めばいいと思えますが、
表紙と真ん中では紙面のサイズが異なるので、スキャンを自動化しにくいのです。
これは、折り曲げた後に裁断するため、外側ほど包み込む分の長さが余計にあるためです。
取り込みとして楽なのは、Ａ４の雑誌なら、中綴じなのを外して、
Ａ３（よりも少し短い）として取り込む方法です。
取り込んだ後に、自動でページ分割・ページ番号割り振りをしてくれれば完璧です。
というわけで、ページ分割する実験です。
大体真ん中で分断すればいいのですが、ページの終わりの検出とか、
変形サイズが混ざる場合のために、ページの分かれ目を検出する実験をしてみます。
準備 JPEG展開・圧縮のライブラリ
libjpeg（実際にはlibjpeg-turbo）を使って、JPEG展開・圧縮を行います。
C++だと使いにくいので、CLRでC#で使いやすいDLLにします。
インタフェースは、以下のようなものです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| using namespace System;
namespace saddlescan_jpg {
public ref class JpegToBmp
{
public:
int Convert(System::String^ filename);
int Width;
int Height;
array<unsigned char>^ Bitmap;
int GetR(int x, int y)
{
return Bitmap[(y * Width + x) * 3 + 2];
}
int GetG(int x, int y)
{
return Bitmap[(y * Width + x) * 3 + 1];
}
int GetB(int x, int y)
{
return Bitmap[(y * Width + x) * 3 + 0];
}
};
public ref class JpegWriter
{
public:
int Write(
System::String^ filename,
array<unsigned char>^ Bitmap,
int OriginalWidth,
int OriginalHeight,
int WidthOffset,
int HeightOffset,
int Width,
int Height);
};
}
|
JpegToBmp.Convertでファイル名を指定すると、
Bitmapに展開されます。
JpegWriterは、Bitmapを渡して、その一部の矩形領域をJPEGファイルにします。
基本型の定義
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class ColorRGB
{
public int R, G, B;
public ColorRGB(int r, int g, int b)
{
R = r;
G = g;
B = b;
}
public ColorRGB()
{
R = 0;
G = 0;
B = 0;
}
}
|
分散を使った分割
ライン内での画素の分散から良いヒント情報が得られるようなので、
分散を元に分割してみます。
準備
・ラインごとに、RGB別の分散を計算し、各パラメータの平均値(Average_y)を取る
・平均値の出現数の下位5%の値（以下 limit1）を計算する
オーバースキャンの検出
・画像の上下について、以下の状態が連続する場合にオーバースキャンした領域とみなす。ただし、２ラインまでは異なる状態を取っても良い。ここで得た画面最上部をMarginTop、最下部をMarginBottomとする。
・前の平均値と各RGB値で3以上乖離がない（実際にはまとめて適当に計算）
・Average_y が limit1 * 0.1 以下
中間点の検出
・MarginTopとMarginBottomの中間点から、以下の状態を満たす最も近いラインを中間とする。満たす点がない場合は、計算上の中間点を採用する。
・計算上の中間点から60%以上離れない（0%を中間点、100%をMargin*とする）
・Average_y が limit1 以下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
| System.Console.WriteLine(FileName);
DateTime time1 = new DateTime(DateTime.Now.Ticks);
image1.Source = null;
JpegToBmp bmp = new JpegToBmp();
int result = bmp.Convert(FileName);
System.Console.WriteLine("Decompress:{0}", result);
DateTime time2 = new DateTime(DateTime.Now.Ticks);
System.Console.WriteLine("Load JPEG : Time {0}s", (time2 - time1).TotalSeconds);
System.Console.WriteLine("X:{0} Y:{1}", bmp.Width, bmp.Height);
if (result != 0)
{
return;
}
BitmapSource image = BitmapSource.Create(
bmp.Width,
bmp.Height,
96, 96,
System.Windows.Media.PixelFormats.Bgr24,
null,
bmp.Bitmap,
bmp.Width * 3);
image.Freeze();
image1.Source = image;
ColorRGB[] bdt2Average = new ColorRGB[bmp.Height];
byte[] bdt = new byte[bmp.Width * bmp.Height * 3];
float[] bdt2Sd = new float[bmp.Height];
SortedDictionary<float, int> sdDictionary = new SortedDictionary<float, int>();
int sdDictionaryValueSum = 0;
for (int i = 0; i < bmp.Height; ++i)
{
ColorRGB average = new ColorRGB();
for (int j = 0; j < bmp.Width; ++j)
{
int idx = i * bmp.Width + j;
average.R += bmp.GetR(j, i);
average.G += bmp.GetG(j, i);
average.B += bmp.GetB(j, i);
}
average.R /= bmp.Width;
average.G /= bmp.Width;
average.B /= bmp.Width;
bdt2Average[i] = average;
float s = 0;
for (int j = 0; j < bmp.Width; ++j)
{
int idx = i * bmp.Width + j;
int diff = 0;
diff += (bmp.GetR(j, i) - average.R) * (bmp.GetR(j, i) - average.R);
diff += (bmp.GetG(j, i) - average.G) * (bmp.GetG(j, i) - average.G);
diff += (bmp.GetB(j, i) - average.B) * (bmp.GetB(j, i) - average.B);
s += diff / 3;
}
s /= bmp.Width;
bdt2Sd[i] = s;
if (sdDictionaryValueSum < bmp.Height / 20)
{
if (sdDictionary.ContainsKey(s))
{
sdDictionary[s]++;
}
else
{
sdDictionary.Add(s, 1);
}
sdDictionaryValueSum++;
}
else
{
if (sdDictionary.Last().Key > s)
{
sdDictionaryValueSum -= sdDictionary.Last().Value;
sdDictionary.Remove(sdDictionary.Last().Key);
if (sdDictionary.ContainsKey(s))
{
sdDictionary[s]++;
}
else
{
sdDictionary.Add(s, 1);
}
sdDictionaryValueSum++;
}
}
}
for (int i = 0; i < bmp.Height; ++i)
{
int sd = (int)(bdt2Sd[i] / sdDictionary.Last().Key * 128);
for (int j = 0; j < bmp.Width; ++j)
{
int idx = (i * bmp.Width + j) * 3;
if (sd <= 128)
{
bdt[idx++] = (byte)sd;
bdt[idx++] = (byte)sd;
bdt[idx++] = (byte)sd;
}
else
{
bdt[idx++] = 255;
bdt[idx++] = 255;
bdt[idx++] = 255;
}
}
}
int MarginTop = -1; // MarginTopは出力に含まない
{
ColorRGB average = null;
int ignoreCount = 0;
for (int i = 0; i < bmp.Height; ++i)
{
int sd = (int)(bdt2Sd[i] / sdDictionary.Last().Key * 128);
if (sd > 10)
{
++ignoreCount;
if (ignoreCount > 2)
{
break;
}
}
else
{
if (average == null)
{
average = bdt2Average[i];
// 1ラインだけでは削らない
}
else
{
int diff = 0;
diff += (bdt2Average[i].R - average.R) * (bdt2Average[i].R - average.R);
diff += (bdt2Average[i].G - average.G) * (bdt2Average[i].G - average.G);
diff += (bdt2Average[i].B - average.B) * (bdt2Average[i].B - average.B);
if (diff < 3 * 3 * 3)
{
average = bdt2Average[i];
ignoreCount = 0;
MarginTop = i;
}
}
}
}
}
int MarginBottom = bmp.Height; // MarginBottom は出力に含まない
{
ColorRGB average = null;
int ignoreCount = 0;
for (int i = bmp.Height - 1; i >= 0; --i)
{
int sd = (int)(bdt2Sd[i] / sdDictionary.Last().Key * 128);
if (sd > 10)
{
++ignoreCount;
if (ignoreCount > 2)
{
break;
}
}
else
{
if (average == null)
{
average = bdt2Average[i];
// 1ラインだけでは削らない
}
else
{
int diff = 0;
diff += (bdt2Average[i].R - average.R) * (bdt2Average[i].R - average.R);
diff += (bdt2Average[i].G - average.G) * (bdt2Average[i].G - average.G);
diff += (bdt2Average[i].B - average.B) * (bdt2Average[i].B - average.B);
if (diff < 3 * 3 * 3)
{
average = bdt2Average[i];
ignoreCount = 0;
MarginBottom = i;
}
}
}
}
}
System.Console.WriteLine("Margin {0} {1}", MarginTop, MarginBottom);
for (int i = 0; i < MarginTop; ++i)
{
for (int j = 0; j < bmp.Width; ++j)
{
int idx = (i * bmp.Width + j) * 3;
bdt[idx++] = 255;
bdt[idx++] = 0;
bdt[idx++] = 0;
}
}
for (int i = MarginBottom; i < bmp.Height; ++i)
{
for (int j = 0; j < bmp.Width; ++j)
{
int idx = (i * bmp.Width + j) * 3;
bdt[idx++] = 255;
bdt[idx++] = 0;
bdt[idx++] = 0;
}
}
int TrueHeight = MarginBottom - MarginTop + 1;
int Center = TrueHeight / 2 + MarginTop + 1;
for (int i = 0; i < TrueHeight / 2 * 0.6; ++i)
{
int y1 = Center + i;
if (y1 < bmp.Height)
{
float sd = bdt2Sd[y1] / sdDictionary.Last().Key;
if (sd < 1.0f)
{
Center = y1;
break;
}
}
int y2 = Center - i;
if (y2 < bmp.Height)
{
float sd = bdt2Sd[y2] / sdDictionary.Last().Key;
if (sd < 1.0f)
{
Center = y2;
break;
}
}
}
for (int i = Center - 1; i <= Center + 1; ++i)
{
for (int j = 0; j < bmp.Width; ++j)
{
int idx = (i * bmp.Width + j) * 3;
bdt[idx++] = 255;
bdt[idx++] = 0;
bdt[idx++] = 0;
}
}
System.Console.WriteLine("Center {0}", Center);
BitmapSource source2 = BitmapSource.Create(
bmp.Width,
bmp.Height,
96, 96,
System.Windows.Media.PixelFormats.Rgb24,
null,
bdt,
bmp.Width * 3);
image2.Source = source2;
JpegWriter writer = new JpegWriter();
writer.Write("test1.jpg", bmp.Bitmap,
bmp.Width, bmp.Height,
0, MarginTop + 1,
bmp.Width, Center - MarginTop + 1); // Center含む
writer.Write("test2.jpg", bmp.Bitmap,
bmp.Width, bmp.Height,
0, Center,
bmp.Width, MarginBottom - Center); // Center含む
|
端点と中間点の検出例です。
途中、中間点の検出ミスと思われる点が2箇所あります。
この検出ミスはしきい値の問題ですが、
実は原理的な問題もあります。
たとえば、ちょうど真ん中のページが
見開きになっていた場合、絵や写真が真ん中にもあります。
そのような場合に、真ん中で切っていいか？という問題です。
そして、その近くに情報量が少なそうな縦ラインがあったら
そこで切ったほうがいいという選択もありえます。
このアルゴリズムでは、情報量の少ないラインで切断する
というのが本質なので、中心に情報量があり
その近辺に情報量の少ないラインがあったら
そこで切断します。
でも、ページ分割では真ん中になって欲しいので
少し追加の処理が必要です。
見開きは単一ページに統合するという方式もありえます。
FFTを使った分割
横方向で取り込んだデータに対して、ＦＦＴで低周波成分だけ抽出したら
それっぽいデータが取れました。
分散での計算よりもノイズ的なものを無視しやすいと思いますが、
あまりそういう場面はないようです。
byte[y][x]の配列を１次元として扱って、
FFTで変換したあと、下位1%以下(本当は画像サイズに依存します)を残して、逆変換してます。
・横方向
・１次元として扱う
・閾値
あたりがポイントです。
最初は、縦方向で、一定の周期の情報のみを抜粋しようとしましたが
あまり芳しくありませんでした。
元画像は著作権上の問題があるので取り込み後に加工しています。
下が元画像、左がグレースケール化した画像、右が変換後の画像です。
実験にはfftwを使っています。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| IntPtr pin, pout, pin2, pout2;
float[] fin, fout, fin2, fout2;
GCHandle hin, hout, hin2, hout2;
IntPtr fplan1, fplan2;
int n = cinfo.Output_height * cinfo.Output_width;
pin = fftwf.malloc(n * 8);
pout = fftwf.malloc(n * 8);
fin = new float[n * 2];
fout = new float[n * 2];
for (int i = 0; i < n * 2; ++i)
{
fin[i] = 0;
}
hin = GCHandle.Alloc(fin, GCHandleType.Pinned);
hout = GCHandle.Alloc(fout, GCHandleType.Pinned);
for (int i = 0; i < cinfo.Output_height; ++i)
{
for (int j = 0; j < cinfo.Output_width; ++j)
{
fin[(i * cinfo.Output_width + j) * 2 + 0] =
(bitmap[i * cinfo.Output_width * 3 + j * 3 + 0] * 1 // B
+ bitmap[i * cinfo.Output_width * 3 + j * 3 + 1] * 6 // G
+ bitmap[i * cinfo.Output_width * 3 + j * 3 + 2] * 3) / 10; // R
}
}
Marshal.Copy(fin, 0, pin, n * 2);
Marshal.Copy(fout, 0, pout, n * 2);
fplan1 = fftwf.dft_1d(n, pin, pout, fftw_direction.Forward, fftw_flags.Estimate);
fplan2 = fftwf.dft_1d(n, pin, pout, fftw_direction.Backward, fftw_flags.Estimate);
fftw.execute(fplan1);
Marshal.Copy(pout, fout, 0, n * 2);
for (int i = 0; i < cinfo.Output_height; ++i)
{
for (int j = 0; j < cinfo.Output_width; ++j)
{
int idx = i * cinfo.Output_width + j;
if (idx < n * 0.01)
{
fin[idx + 0] = fout[idx + 0];
fin[idx + 1] = fout[idx + 1];
}
}
}
Marshal.Copy(fin, 0, pin, n * 2);
fftw.execute(fplan2);
Marshal.Copy(pout, fout, 0, n * 2);
|
連続する画像から紙面のサイズを推測する
まず、実際に測ってみます。
84枚、336ページの雑誌の例です。
ところどころに折り込みがあり、その場合はサイズが約２倍になっています。
スキャナで取り込み後に、前述の分散を用いた方法で、端点と中間点を計測したものを用います。
スキャナの特性で、上端は紙面の上端とほぼ一致します。後端はスキャナの自動端点検出を使っていますが、若干オーバースキャン気味になります。
長辺のミリ数です。
横から写した写真です。
小口を単純に裁断していない場合は、このように段差があります。
平らにした状態でどれくらい差があるかも調べました。
片側だけで7.3mmくらい違います。
基本的には内側に行くほど短いのですが、前述の理由で逆転している場所もあります。
変形サイズの考慮
折り込み
１ページ横幅を基準として、２倍や３倍くらいのサイズがあります。
２つ折りだったり、３つ折りだったり。
片側だけだったり両側だったり。
折られると若干短くなりますが、
基本的には１ページの横幅を基準として何かできそう。
両側とも２つ折り（両観音）と
片側だけ３つ折りの区別が自動でできるかどうかは、
紙面の内容次第です。
小サイズ
異なるサイズの用紙が入っていることがあります。
たとえば、A4雑誌の中間にB5サイズとか。
ハガキのようなものを綴じこんである場合（投げ入れ）
困ります。
糊付で片側のページしかない場合
もっと困ります。
ネタ
エッジ検出で中間点を探す
同じ紙面の複数スキャンを使って精度を上げる（多分やらない）
その他
傾き補正をする予定はありません。
傾きはスキャン時に傾かないようにするのが原則です。
傾き補正をすると解像度が落ちるので対応しません。
コメント
