まえがき

このアプリケーションには実用的な価値はないかもしれませんが、実際には多くの経験を積んでいます。 コンピュータービジョンについて少しお話ししたいと思います。 この領域は、現代のコンピューターコンピューティングで最も刺激的なものの1つであり、非常に複雑です。 人間の脳にとって簡単でシンプルなことは、コンピューターにとって非常に困難です。 今日のレベルのIT開発では、多くのことが依然として不可能です。



このプログラムは低レベル言語C ++を使用して記述されています。これは、すべてが内部からどのように機能するかを本当に理解したかったからです。 また、コンピュータービジョンの学習を開始する場合は、OpenCVライブラリが役立ちます。 CodeProjectでは、いくつかのレッスンを見つけることができます。 ウェブカメラからの画像は、Vadim Gorbatenkoのソースコード（AviCap CodeProject）を使用して取得されます。



以下の画像は、プログラムの仕組みを説明しています。







以下の時間間隔は、640 x 480ウェブカメラ解像度の2.8 GHz PCでのミリ秒単位の遅延です。 興味深い結果が得られています。 たとえば、最も遅いステップは、カメラからフレームを取得することです。 100ミリ秒かかります。これは、1秒あたり10フレームしか受信しないことを意味します。 これでは十分ではありません。 ウェブカメラは通常遅いです。 解像度を変更することで速度を上げることができます。 これを減らすと、撮影の速度は上がりますが、品質が犠牲になり、分析に完全に適さなくなる可能性があります。 もう1つの驚きは、画像をバイナリ（白または黒のみ）に変換するのにも12ミリ秒という長い時間がかかることです。 一方、OCRの修正と数独自体の解決には多くの時間がかかると予想していましたが、これらの手順が8ミリ秒で一緒に実行されることがわかったときはうれしい驚きでした。 以下では、各ステップを詳細に説明し、改善できる点を示します。

モノクロへの変換の仕組み

しきい値の選択

各コンピュータービジョンアプリケーションは、カラー（または白黒）画像をモノクロに変換することから始まります。 将来的には、色を使用するアルゴリズムが存在する可能性がありますが、今日のコンピュータービジョンアプリケーションはモノクロ画像で動作します（色覚異常です）。



画像を変換する最も簡単な方法は、一般的なしきい値です。 RGBカラー（200、200、200）のピクセルがあるとします。 コンポーネントの強度は0から255まで変化するため、ピクセルは非常に明るくなります。 強度の半分としてしきい値を選択すると、256/2 = 128になり、ピクセルが白に変わるはずです。 しかし、一般的なしきい値はほとんど使用されないため、実際のアプリケーションではほとんど使用されません。 ローカルしきい値アルゴリズムははるかに便利です。







画像をモノクロに正しく変換するために、適応しきい値選択を使用します。 128の固定しきい値は使用しません。代わりに、各ピクセルのしきい値を個別に考慮します。 それは11ピクセルの辺とピクセルの中心を持つ正方形を取り、すべてのポイントの強度を要約します。 強度の平均値は、特定のピクセルのしきい値になります。 現在のピクセルの強度の式：しきい値=合計/ 121、ここで121 = 11x11。 ピクセルの強度がしきい値を超える場合、白に変換され、そうでない場合は黒に変換されます。 以下の画像では、しきい値が決定されるピクセルは赤でマークされています。 そして、これらの計算は各ピクセルに対して行われます。 したがって、アルゴリズムでは画像ピクセルの幅*高さ* 121の読み取りが必要になるため、このステップは非常に遅くなります。

整数形式

このステップは、「整数形式」を使用して最適化できます。 整数形式は、画像サイズの整数の配列です。 意味は素晴らしいとシンプルです。 画像を撮ります。 ピクセルの強度が1である12x12の領域があると仮定します（現実の世界では決して発生せず、それほど簡単に発生しません）。整数画像は、左上から現在（右下）までのすべてのピクセルの合計です。







次の画像は、整数画像がどのように役立つかを示しています。 目標は、灰色の長方形内のピクセルの合計を計算することです。

式：合計= DC-B + A 私たちの場合：110-44-40 + 16 = 42（手動で計算してみてください）。

グレーの長方形からすべてのピクセルを読み取る代わりに（例よりもはるかに大きくなる可能性があります）、1回のメモリ読み取りのみが必要です。 これは、アルゴリズムの大幅な最適化です。 しかし、それでも、画像をモノクロに変換することは非常に困難です。

回転角を決定する方法

Webカメラはスキャナーではありません。 また、画像は完全に滑らかになることはありません。つまり、物事の順序で少し斜めに回転した画像になります。 回転角度を決定するために、数独の画像には常に水平線と垂直線があるという事実を使用します。 画像の中央付近で最も表情豊かで太い線を決定します。 最も表情豊かなラインはノイズの影響を受けません。 画像内のモノクロの線を見つけるためのアルゴリズムは、ハフ変換と呼ばれます。



どのように機能しますか？ 学校の公式y =（x * cos（theta）+ rho）/ sin（theta）を覚えておく必要があります。





ここで、シータはラインの角度であり、ローはラインから座標の中心までの距離（0、0）です。

傾斜角と座標中心までの距離という2つの変数だけで線を記述できることが重要です。



このアルゴリズムは、モノクロ画像のすべてのピクセルを通過し、白いピクセルをスキップします。 彼が黒いピクセルに当たったとき、彼はこのピクセルを通過するあらゆる種類の線を1度ずつ「描画」しようとしています。 これは、各ピクセルに180本の想像線が通ることを意味します。 360を選ばない理由 はい、角度180-360は角度0-180度の線のコピーであるためです。



この一連の想像上の線はドライブと呼ばれ、シータとローの次元を持つ2次元配列であり、上記の式にありました。 各仮想線は、ドライブ内の1つの値で表されます。 ところで、このメソッドは行を（x、y）から配列（theta、tho）に変換するため、変換と呼ばれます。 各想像線はドライブに価値を追加し、想像線が実際のものと一致する可能性を高めます。 それは投票のようなものです。 これらの行には最も「投票」があります。



すべてのピクセルとその180の仮想線が「投票」された後、ドライブの最大値を見つける必要があります。 （ちなみに、それは投票を蓄積するため、ドライブと呼ばれます）投票の勝者は、最も表現力のある行です。 パラメータthetaおよびrhoは、上記の式で使用して描画できます。



次の画像は小さな例を示しています。 左側には、3つのピクセルで構成される線があります。 これは左から右への対角線であることは確かにわかっていますが、コンピューターの場合、これはそれほど明白ではありません。







この画像を見ると、ライン検出の仕組みを理解できます。 ハフ変換アルゴリズムは、白いピクセルをスキップします。 それぞれの黒いピクセルに、現在のピクセルを通る4本の想像上の緑の線（実際には180本ですが、簡単にするために4本を取る）を描画します。 最初のピクセルはラインA、B、C、Dに投票します。2番目のピクセルはラインE、B、G、Hに投票します。3番目はI、B、K、Lに投票します。3つのピクセルすべてがラインBに投票し、残りのラインは合計で一つの声。 したがって、行Bが票を獲得しました。



次の画像は、より複雑な例です。 左側には数独グリッドがあり、右側にはハフ変換アルゴリズムの画像を通過した後のドライブの配列があります。 明るい明るい領域は、多くの票を獲得した行です。 暗さは、画像内でこのようなパラメータを持つ線を見つける機会がないことを意味します。 明るい点にのみ焦点を当てます。 各行（AU）には、ドライブ内に明るい点があります。 すべての線がわずかに回転していることがわかります（約6度）。 ラインAはラインKよりも回転しません。画像は回転するだけでなく、面取りもされるためです。 また、よく見ると、線AとBがBとCよりも互いに近いことがわかります。これは両方の画像で確認できます。







ハフ変換は、パターン認識を行う場合に理解することが重要です。 投票を通じて現実的な仮想線の概念は、任意の幾何学的形状に拡張できます。 行はそれらの中で最も単純であるため、理解するのが最も簡単です。



円を見つける必要がある場合は、x、y、rの3次元のドライブが必要です。 ここで、xとyは円の中心の座標、rは半径です。

ハフ変換は、元の画像の領域と可能な角度を制限することにより最適化できます。 すべての線を分析する必要はなく、中心に近い線のみを分析する必要があります。 私たちのケースでは、それらから構築することができます。

グリッドを定義する方法

数独グリッドから数値を取得するには、グリッドの開始位置と終了位置を決定する必要があります。 この部分は人間の脳にとって最も単純な部分ですが、コンピューターにとっては最も難しい部分です。 なんで？ 前の手順でハフ変換を使用して見つかった行を使用しないのはなぜですか？ 余分なデータが多すぎます。 非常に多くの場合、新聞や雑誌はいくつかの数独を並べて印刷します（うーん、明らかに後者はコンピューターで認識されていません）。 画像に余分な行が多すぎます。 たとえば、次の画像をご覧ください。







コンピューターがどのラインが必要なものに属し、どれが単なる情報ノイズであるかを判断することは非常に困難です。 グリッドの終わりと次の始まりはどこですか。

この問題を解決するために、黒い線を定義しません。 代わりに、グリッドの周りに白い領域を定義します。 次の画像では、これを見ることができます。 緑の線1は黒のピクセルと交差しませんが、線2はこれを10回行います。 これは、グリッドライン1の背後がライン2よりも高い可能性があることを意味します。緑のラインが黒のピクセルと交差する回数を計算するだけで、グリッドの境界外にあると結論付けることができます。 線の下にある白から黒のピクセルへの遷移の数を単純に計算するだけで十分です。 ところで、各行を調べる必要はありません。実行速度を上げるには、3行ごとにこれらのアクションを実行するだけで十分です。







境界を定義したら、ハフ変換アルゴリズムを実行してグリッド線を正確に決定します。 これまで、歪みやその他の画像の欠陥は気にしませんでした。 回転角についてのみ。 このステップで修正されます。 ハフ変換を開始することにより、グリッド線の正確な位置を取得します。 これは、グリッド内の数値を決定するのに役立ちます。



TODO ：このステップは、よりノイズに強い場合があります。 次のバージョンでは、現在の方法とHaarのようなアルゴリズムを組み合わせて、グリッドの角度を決定する予定です。 これにより品質が向上することを願っています。 問題は、Haarのような方法が線ではなく、ソリッド領域でうまく機能することです。 線は小さな領域を占めるため、明るい長方形と暗い長方形の違いはそれほど大きくありません。

10x10グリッドを検出しようとするとどうなるかは興味深いです...

OCRはどのように機能しますか？

番号の場所を決定したら、それらを認識する必要があります。 比較的簡単です。 アルファベットには1〜9の数字のみが含まれます。

理論

各認識アルゴリズムには3つのステップがあります。

• 必要な特性の決定
• トレーニング
• 分類（実行時の認識）

必要な属性の識別は、アプリケーション開発の一部です。 たとえば、ナンバーワンは薄くて高いです。 これが彼女を他の人と区別するものです。 数字8には、上半分と下半分などに2つの円があります。

必要な属性を決定することは、何を認識する必要があるかによっては難しく、直感的ではありません。 たとえば、誰かの顔を認識するために何が必要ですか？ 誰でもではなく、特定のものです。

ゾーン

このアプリケーションでは、ゾーンの密度の方法が使用されました。 次のステップ（事前に行う必要があります）は、1から9までの数字でアプリケーションをトレーニングします。これらの画像は./resディレクトリにあります。 これらはサイズ5x5に縮小され、正規化され、静的配列OCRDigit :: m_zon [10] [5] [5]に格納されます。これは次のようになります。

5x5サイズに縮小することをゾーニングまたはゾーニングと呼びます。 上記の配列は関数密度と呼ばれます。

正規化とは、密度が0から1024まで変化することを意味します。ゾーンを正規化しないと、正しく比較できません。

プログラムの実行中に何が起こるか：元の画像から数字が取得されると、5x5のサイズに縮小されます。 その後、その各ピクセルが、トレーニングされた配列の9桁の各ピクセルと比較されます。 目標は、最小限の違いでフィギュアを見つけることです。

いずれの場合も5x5ゾーンを使用するため、この方法は画像サイズに対して不変です。 彼はターンに敏感ですが、私たちはすでにこれを面倒を見ました。 問題は、位置とバイアスに敏感であり、ネガ（黒地に白）と数字が上下逆になっている場合にも機能しないことです。

幅/高さの比率

ナンバーワンは特別な場合です。 4と7に類似しているため、上記の決定方法は信頼できない場合があります。 特定の単位パラメーター：この場合、幅は高さより40％小さくなります。 同じ比率のこのような数字は他にありません。 すでに25のゾーン（標識）があるため、これは26番目の標識です。

TODO ：次のバージョンでは、新しい機能の導入によりOCRの品質を改善できます。 たとえば、ゾーンパーティションを使用する場合、5、6、および9という数字は非常に似ています。 それらを区別するために、プロファイルを属性として使用できます。 この機能の機能は、数字のフレームの端とその境界の間のピクセル数（距離）です。

下の画像では、数字5と6のプロファイルは似ていますが、プロファイル9とは異なっています。左側のプロファイル5と9は似ていますが、プロファイル6とは異なります。







さらにいくつかの改善を追加できます。 プロフェッショナルOCRエンジンは多くの機能を使用します。 それらのいくつかは非常にエキゾチックです。

OCR結果の調整

OCRが完了すると、数独ルールに従って結果が調整されます。 1つの行、列、3x3ブロックに同じ数字を含めることはできません。 ルールに違反した場合、結果に調整を導入する必要があります。 間違った数字を、残りの数字から可能な数字に置き換えます。 たとえば、上の画像12では、diff = 5210が最小の差分値であるため、結果は5です。 この場合、diff = 5508であるため、次に可能な結果は6です。 したがって、5を6に置き換えます。2桁のうちどちらが間違っているかを判断するために、それらの差の値をサンプルと比較し、値が小さい方を正しいと見なします。 修正のソースコードは、関数SudSolver :: Fixit（）;にあります。

数独ソリューション機能はどのように機能しますか？

数独を解決するにはいくつかの方法があります。 一緒に機能し、互いに補完する3つの簡単な方法を使用します。オープンナンバー、隠しナンバー、オーバーキルです。

ブルートフォース

これは、難易度に関係なく、ソリューションを正確に提供するプログラマーによって最も広く使用されている方法です。 しかし、検索は非常に長くなる可能性があり、再帰の深さに依存します。 必要な反復回数はわかりません。 検索中に、1から9までの可能な値がセルに順番に入力され、設定された番号の数独の解決策が続行されます。 停止している場合（1つの行/列/ブロックで同じ番号を取得したら、その番号を次の番号に変更します）。 実際、複数の解決策が存在する場合がありますが、少なくとも1つの解決策が見つかったらクールです。 （翻訳者は検索で解決策を持っていて、驚くほど速く働きました）。



最初に、候補のテーブルを準備する必要があります-各空のセルの可能な値。 以下の画像は、候補者が正確に何であるかを説明しています。 それらは青く塗られています。 数独の規則によれば、最初のセルには数字の1、4、8のみを含めることができます。3つはそこに存在できません。既に2つのセルが低いからです。







ブルートフォース法は、解決策が見つかるまで、すべての青い数字を組み合わせようとします。 最初のセルを見てみましょう。 アルゴリズムは1つから読み取り、5番目のセルには値3があります。ある桁が他の値と一致しない場合、アルゴリズムは別の値を試します。 たとえば、左の6番目のセルにも候補として番号3がありますが、これは5番目のセルと一致しないため、アルゴリズムは次の数字、つまり4などを試行します。

ソリューションが多数の反復を必要とする場合、列挙は非常に遅くなる可能性があります。 たとえば、次の画像はアルゴリズムにとって非常に悪いケースです。 左上のセルから開始すると検索数が多すぎますが、良いニュースがあります。オプションが少ないセルから開始してください。 これにより、ソリューションが高速化されます。







アルゴリズムのパフォーマンスを向上させるための最適化がさらにいくつかあります。たとえば、候補の数が最小のセルから最大のセルに再帰シーケンスを並べ替えるなどです。 ただし、これは部分的な最適化にすぎないため、このアルゴリズムは使用しません。 すべての数独には不良セルがあり、リアルタイムアプリケーションの場合ほど高速に処理されません。

オープンナンバー

次の図は、この方法を説明しています。 セルに単一の候補がある場合、この数字はこのセルにあると自信を持って言えます。 値を設定したら、次のステップは候補リストを再構築することです。 候補のリストは、単一の候補が存在する限り縮小されます。 これは、コンピューターにとって明白で簡単な方法です。 しかし、私が思うほど人々には明らかではありません。 ライブプレーヤーは、候補者のリストを頭の中で保持し、常に再構築して調整することはできません。

隠し番号

前と同様に、以下の画像はこの方法を説明しています。 数字の7を見てください。数独を解く場合、7は指定されたセルにあるべきだと言うでしょう。







このセルに4、7、8、9（図15を参照）の4つの候補がある場合でも、トリックは3x3ブロック、行、列の候補から一意の番号を探していることです。 この方法はパズル全体を解くことができるかもしれませんが、方法2の方がうまく機能します。単一の候補がオープンディジット方式で終わると、隠しディジット方式がシーンに入ります。

すべての方法を組み合わせる

このためには、処理速度とソリューションが重要です。 列挙は速すぎません。 したがって、3つの方法すべてを組み合わせて使用​​します。 方法2と3は非常に高速ですが、高速パズルを解くことができるだけです。 パズルを解くようにアプリケーションに要求するので、これは本当に複雑であることを意味します。 以下は作業のアルゴリズムです。 高速メソッド2と3は左側にあり、パズルの解決に失敗した場合にのみ、列挙メソッドを使用して右側に制御が渡されるため、このアルゴリズムの作業が軽減されます。







方法2と3がパズルを解決できない場合にのみ、プログラムは値をねじり始めます。 そして、それでも、ブルートフォースアルゴリズムは600,000回の反復に制限されています。 また、3つの試みがあり、その後プログラムはattemptsめます。 各試行の間に、新しいシーケンスがパズルをより速く解決するのに役立つことを期待して、再帰的なシーケンスがランダムに再配置されます。 数独を解決できなかったら、カメラの次のフレームで幸運になるかもしれません。 提示されたフローチャートは、関数SudSolver :: SolveMe（）で説明されています。

バッファリングソリューション

ソリューションが見つかると、SudResultVoter型の配列に保存します。 OCRは結果の正確性を100％保証するものではないため、バッファリングが必要であり、時々異なるソリューションが得られます。 不安定なソリューションを回避するために、（最後の12個のソリューションの精度のために）常に最強を示します。 時々、配列はゼロにリセットされ、古い決定を忘れて新しい決定にチャンスを与えます。

映像

TODO：

将来のアイデア：

• Android用のプログラムを書き換えます。 スマートフォンでどのように機能するのだろうか
• マルチプロセッサシステムで一部の機能を並列化します。 現在、ほとんどのPCには少なくとも2つのコアがあります。 通常、並列化によりパフォーマンスが向上します。 しかし、ウェブカメラを介したソルバーでは、精度や品質ほどスピードは必要ありません。 原則として、タスクの並列化により、類似したフレームでの操作が改善されますが、設定は異なります。 すべてのタスクが完了した後、最良の結果を得るだけです。

デモのダウンロード-170 KB

ソースのダウンロード-307 KB



GitHubにはソースミラーもあります： github.com/NeonMercury/Realtime-Webcam-Sudoku-Solver