Yabu.log

ITなどの雑記

COBOLが基本情報午後問題から廃止されるらしいので解いてみた&動かしてみた

COBOL 資格

基本情報の午後試験からCOBOLが廃止されますのでH30秋のCOBOLを解きました。問題自体は完答できて満点でした。それだけだと面白くないのでMacにCOBOL環境を構築して実行してみました。

問題はこちらの設問10です。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2018h30_2/2018h30a_fe_pm_qs.pdf

問題内容

  • 全社員の資格(4つ限定w)の合格状況を管理するプログラム
  • プログラムは半年に一回だけ実行されるバッチ。この利用頻度だとCOBOLからリプレースされないだろうとちょっと納得できる設定。
  • 繰り返しと分岐をきちんと理解していないと完答できないような良問だと個人的に思う。

情報サービス企業であるＰ社には社内資格として資格１～４があり，従業員に取得を奨励している。 社内資格を取得するための試験は定期的に実施しており， 全従業員の保有状況を保有資格ファイルで管理する。Ｐ社の事業年度は４月から翌年３月までであり， 上期（４月～９月）と下期（ 10 月～翌年３月）の２期から成る。 資格試験に合格した従業員の情報は合格ファイルに１期分を蓄積する。 上期の合格者を蓄積した合格ファイルは 10 月初めに，下期の合格者を蓄積した合格ファイルは ４月初めにプログラムを実行して，保有資格ファイルに反映する運用である。

ざっくり概要がわかる程度に紹介しましたが、完全版が見たい人は上記リンク先を見てください。

環境

$ cobc --version
cobc (OpenCOBOL) 1.1.0
Copyright (C) 2001-2009 Keisuke Nishida / Roger While
Built    Aug 24 2018 04:30:53
Packaged Feb 06 2009 10:30:55 CET

ソース&ビルド

open-cobolをインストールします

brew install open-cobol

適当に写経したままだと動かなかったので先頭8行を足した。

IDENTIFICATION DIVISION.
PROGRAM-ID. QLF.
ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
      FILE-CONTROL.
      SELECT SRT-FILE  ASSIGN TO 'sort.txt'.
      SELECT QLF-FILE ASSIGN TO 'qlf.txt'.
      SELECT PAS-FILE  ASSIGN TO 'pas.txt'.
DATA DIVISION.
FILE SECTION.
  SD SRT-FILE.
    01 SRT-REC.
       02 SRT-NO        PIC X(8).
       02 SRT-CD        PIC 9(1).
       02 SRT-DATE      PIC 9(8).
  FD QLF-FILE.
    01 QLF-REC.
       02 QLF-NO        PIC X(8).
       02 QLF-INF.
          03 QLF-DATE      PIC 9(8) OCCURS 4.
  FD PAS-FILE.
    01 PAS-REC.
       02 PAS-NO        PIC X(8).
       02 PAS-CD        PIC 9(1).
       02 PAS-DATE      PIC 9(8).
WORKING-STORAGE SECTION.
77 SRT-FLAG       PIC X(1) VALUE SPACE.
   88 SRT-EOF        VALUE "E".
77 CR-NO          PIC X(8) VALUE SPACE.
PROCEDURE DIVISION.
MAIN-PROC.
    OPEN I-O QLF-FILE.
    SORT SRT-FILE ASCENDING KEY SRT-NO
         USING PAS-FILE
         OUTPUT PROCEDURE IS RET-PROC.
    CLOSE QLF-FILE.
    STOP RUN.
RET-PROC.
    PERFORM TEST BEFORE UNTIL SRT-EOF
       RETURN SRT-FILE AT END    SET SRT-EOF TO TRUE
                                 PERFORM WRI-PROC
                       NOT AT END PERFORM UPD-PROC
       END-RETURN
    END-PERFORM.
UPD-PROC.
    IF  SRT-NO NOT = CR-NO THEN
       PERFORM WRI-PROC
       MOVE SRT-NO TO QLF-NO
       READ QLF-FILE END-READ
       MOVE QLF-NO TO CR-NO
    END-IF.
     MOVE SRT-DATE TO QLF-DATE(SRT-CD).
WRI-PROC.
    IF CR-NO NOT = SPACE THEN
       REWRITE QLF-REC
    END-IF.

ちなみにプログラムの大部分は 【基本情報技術者試験】平成30年 秋期 午後 問題と解答 からコピペしたものを手直しした。

上記ファイルをコンパイルします

$ cobc -x --free -W prog.cob

実行前ファイル内容確認〜実行

必要になるファイルを用意する。sort.txt処理に必要な中間ファイルなので空でOK

$ ls
pas.txt     prog        prog.cob    qlf.txt     sort.txt
$ cat pas.txt 
00000001220180203
$ cat qlf.txt 
00000001
0000000220170101
00000003

実行〜結果確認

$ cat qlf.txt 
00000001
00000002
00000003
$ ./prog
$ cat qlf.txt 
00000001        20180203        
00000002                        
00000003

無事00000001の社員の資格2の合格日が更新されました。

感想

COBOLは自分の知ってるどの言語よりも自然言語(英文)っぽく書けるように工夫されている。可読性は高いと思う。

参考にさせていただいたサイト

動かす時に少し調べました。

ファイル管理段落

gnucobol - Opening file for reading in COBOL - Stack Overflow

第 5 章 ファイル状態コード

MacにCobolを入れていじってみた話 - Qiita

ubuntuのssh serverに公開鍵認証でログインする

SSH セキュリティ

前職ではsshを本格的に使ったことがなく、せいぜい自宅でgithubに公開鍵をupした程度しか使ってなかったのでサーバー側、クライアント側を一通り動かして見ました。

サーバー側のsshの設定

設定ファイルは/etc/ssh/sshd_configなのでコレを編集して様々な設定を適用可能

  • 待受portを22から変更
  • ポートフォワーディングを禁止する
  • パスワード認証を無効化する(常に事前に登録した公開鍵を使う)

※todo:セキュリティ的にましな設定を調べてまとめる

変更を加えたらリスタートしましょう

sudo systemctl restart sshd.service

接続

パスワードを使って接続

クライアント側で実行するとuserのパスワードを聞かれ、ログインできます。

ssh <user name>@<server name(or ip)>

RSAで認証して接続

クライアント側でRSAの鍵を作る

$ ssh-keygen -t rsa

クライアント側のPCから鍵をサーバーに送る

ssh-copy-id -i <key file> <user name>@<server name( or ip)>

クライアント側から秘密鍵を指定して接続

ssh -i <private key file> <user name>@<server name(or ip)>

note複数の鍵がある場合、

~/.ssh/configファイルに設定を書いておくと実行するときにオプションの指定などをすべて省略できるので便利。(ssh <接続名>だけで接続できる)

Host  <接続名1>
  HOSTname <server name (or ip)>
  port <port no>
  User <user name>
  IdentityFile <key file>

Host <接続名2>
  ...(以下略)

切断

exitコマンドで切断可能

weikum本に記載されている全定義の一覧リスト

Transaction DB

現在5章を読む勉強会に参加していますが、 5章まで全部読めていません。最近読めていないところを見直すと、理解を曖昧にしていた用語の定義が前半の方に乗っていたので、この際全部調べて定義の掲載箇所を一覧できるものを作ってみました。

下表を参考におっ、こんな定義も乗ってたか!という感じで使ってもらえると嬉しいです。*1

DEFINITION page
2.1 Partial Order 46
2.2 Page Model Transaction 46
2.3 Object Model Transaction 51
3.1 Schedules and Histories 66
3.2 Serial History 67
3.3 Herbrand Semantics of Steps 74
3.4 Herbrand Universe 75
3.5 Schedule Semantics 76
3.6 Final State Equivalence 77
3.7 Reads-From Relation 78
3.8 Final State Serializability 82
3.9 View Equivalence 83
3.10 View Serializability 85
3.11 Monotone Classes of Histories 92
3.12 Conflicts and Conflict Relations 93
3.13 Conflict Equivalence 93
3.14 Conflict Serializability 94
3.15 Conflict Graph (Serialization Graph) 96
3.16 Commutativity Based Equivalence 99
3.17 Commutativity Based Reducibility 100
3.18 Order Preservation 102
3.19 Commit Order Preservation 102
3.20 Closure Properties of Schedule Properties 106
3.21 Commit Serializability 107
3.22 Indivisible Units 111
3.23 Dependence of Steps 113
3.24 Relatively Serial Schedule 113
3.25 Relative Serializability 114
3.26 Push Forward and Pull Backward 116
3.27 Relative Serialization Graph 116
4.1 CSR Safety 130
4.2 Two-Phase Locking (2PL) 134
4.3 Conservative 2PL 142
4.4 Strict 2PL 143
4.5 Strong 2PL 144
5.1 Version Function 187
5.2 Multiversion Schedule 188
5.3 Monoversion Schedule 189
5.4 Reads-From Relation 190
5.5 View Equivalence 191
5.6 Multiversion View Serializability 192
5.7 Version Order 194
5.8 Multiversion Serialization Graph (MVSG) 195
5.9 Multiversion Conflict 197
5.10 Multiversion Reducibility 198
5.11 Multiversion Conflict Serializability 199
5.12 Multiversion Conflict Graph 199
6.1 Object Model History 218
6.2 Tree-Consistent Node Ordering 219
6.3 Object Model Schedule 219
6.4 Serial Object Model Schedule 221
6.5 Isolated Subtree 221
6.6 Layered History and Schedule 222
6.7 Flat Object Schedule 223
6.8 Commutative Operations 224
6.9 Commutativity Based Reducibility 226
6.10 Conflict Equivalence and Conflict Serializability 227
6.11 Tree-Reducible History 229
6.12 Level-to-Level Schedule 234
6.13 Conflict Faithfulness 238
6.14 State-Dependent Commutativity 241
6.15 Return Value Commutativity 242
8.1 IDM Transaction 286
8.2 Transaction Equivalence 287
8.3 Final State Serializability 289
8.4 Conflict Serializability 291
8.5 Conflict Graph 291
8.6 Extended Conflict Graph and Serializability 293
8.7 State Serializability 296
8.8 Transaction Chopping 302
8.9 Chopping Graph 302
8.10 Correct Chopping 304
10.1 Isolation Levels 361
10.2 Multiversion Read Committed and Snapshot Isolation Levels 362
10.3 Formal Definition of Snapshot Isolation 363
10.4 Snapshot Isolation Serialization Graph 363
11.1 Expansion of a Schedule 384
11.2 Expanded Conflict Serializability 385
11.3 Reducibility 387
11.4 Prefix Reducibility 389
11.5 Recoverability 391
11.6 Avoiding Cascading Aborts 392
11.7 Strictness 393
11.8 Rigorousness 394
11.9 Log Recoverability 398
11.10 Inverse Operation 408
11.11 Perfect Commutativity 411
11.12 Perfect Closure 413
11.13 Normal Commutativity Table 414
11.14 Strictness 415
11.15 Terminated Subtransactions 416
11.16 Expanded Object Model Schedule 417
11.17 Extended Tree Reducibility 418
12.1 Extended History 434
12.2 Stable Log 435
12.3 Log Buffer 435
12.4 Cached Database 436
12.5 Stable Database 437
12.6 Correct Crash Recovery 437
12.7 Logging Rules: Redo Rule, Undo Rule, Garbage Collection Rule 438
18.1 Global History 677
18.2 Conflict Serializability 678
18.3 Global History 692
18.4 Direct and Indirect Conflict 694
18.5 Global Conflict Graph 695
18.6 Commit-Deferred Transaction 699
18.7 Extended Commitment Ordering 701

ちなみにですが同じものが複数回出てきているものがあるかもしれませんが、それぞれ文脈が違っています。 例えばConflict Serializabilityは３回でてきていますが、

  • 3.14 Conflict Serializability
  • 8.4 Conflict Serializability
  • 18.2 Conflict Serializability

f:id:yuyubu:20190205150103p:plain
大元のSerializabillityの定義

f:id:yuyubu:20190205150213p:plain
IDM Transactionに置けるConflict Serializability

f:id:yuyubu:20190205150317p:plain
Global,Local historyにおけるConflict Serializability

とそれぞれ内容が違っています。

ちなみにこの本の勉強会は明日もあります。オススメです。一緒に楽しくトランザクションを勉強しましょう。

connpass.com

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) (English Edition)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) (English Edition)

*1:多分トランザクション資料を読む時の不明点確認は巻末のindexの方が良いと思う

賀正新年2019年あけましておめでとうございます

まだセーフです。

f:id:yuyubu:20190204183902p:plain
今年もよろしく

2018年の振り返りでも書いてみます。

転職した

仕事内容は書かないけど、分野的には 地理情報 + (R)DB + 画像処理 + 性能測定/改善な感じ。 一部は殆ど経験がない要素もあるので勉強したことを少しづつこのブログなどに書いていこうと思います。

色々勉強会に出た

継続して出ているもの、スポットで出たもの等色々あるが、 スポットで出れそうなもので興味が会ったものがいくつか会ったが、

などは予定が合わなかったり、疲れていたりで行けなかった。

初めて発表した

20分なのでLTという割に長いが、そこまで大きな発表ではない。

yuyubu.hatenablog.com

色々な人に会った

名前出すと迷惑なので控えますが、主に勉強会を通して面白い人に沢山会った。 酒が飲めないなどが理由で宴会などは元々嫌いだったけど、 いろんな会社の人と話す機会だと思って、勉強会の打ち上げなどは積極的に参加した。

紅茶を飲み始めた

私はハードコアなコーヒー党ですが、会社でコーヒーを入れるのは非常にめんどくさい。 というわけで色々模索した結果ティーバッグで紅茶を飲むのが良いのでは？という結論に至った。

Amazonとかコンビニで買ったやつはあまり美味しくないけど、ちゃんとした茶葉屋さんで買ったやつは美味しいと思う。

どうやら私はアッサムティーというやつが好きらしい。

初めて高度区分の試験に合格

まだまだ半人前の状態なので、これはなんで受かったのかよくわからない。

yuyubu.hatenablog.com

セキュリティはそこまで積極的に関わることにならなさそうだけど、今後もちょくちょく勉強して行きたいです。

15年ぶりに歯医者に行った

この件に関してはまだ治療中ですが、終わったらまとめて1つの投稿にしたいと思います。

2019年の意気込みとか

  • ランニングで適当な結果を出したい
  • 冬季はジムに通いたい
    • 寒いとランニングはきつい(アップ、ダウン、呼吸等)
    • 別に寒さに耐える苦行がやりたいわけではないので、運動習慣を途切れさせないためにも動きやすいジムなどにいくべきかなと思う。
  • 英語の技術書を読めるようにする
  • TOEICを毎月受ける
    • 特にTOEIC用に勉強はしませんが、実力ベンチとして受けようかなーと思います。
  • 発信する情報の質をあげる
    • 色々話題になったサイトじゃないけど日本のweb上の技術情報群の質を下げてる自覚はあるので...
  • テニスボールでリフティング1000回を達成する
    • 100回は時々できるようになってきた

今年中にほしいもの

  • Type-C 60WのPDができる4Kディスプレイ
  • 100Mbps安定する回線
  • iPad(バッテリーがそろそろ☠️)

という訳で今年もよろしくお願いいたします。

PCのセットアップに苦戦したがなんとかGRUBでWindows,Ubuntuのdual boot環境ができた(日記)

ubuntu grub

1つのSSD(500GB)上にwindows + ubuntuのdualboot環境を作った。

実施順は以下の通り

  • 1.ssdをフォーマット(windowsのインストールディスクにあったメニューで実施)
  • 2.Ubuntuをインストール(liveCDから)
  • 3.ubuntuにwindowsのインストール先パーティションを作る
    • ちなみにこれはインストールしたSSDからブートしたOSからはできなかったので態々LiveCDから行った
  • 4.windowsをインストール

一応職場のPCのOSは自由だが、 Windowsを利用する可能性があるので完全消去はまずいかなと思いこのような構成にした。 linuxなんてVMでいいじゃんと思うかもしれませんが、 vmだとスペックが使いきれな買ったり、UIの描画に若干違和感がある等のデメリットがある。

デメリット

1つのディスクを複数パーティションに分けてOSを導入すると、バックアップ,リカバリなどがややこしいらしい。

起こったトラブルとか

GPTパーティション云々

https://www.cyberarchitect.net/blog/archives/1806

Windowsインストール時に 「このディスクにWindowsをインストールすることはできません。選択されたディスクはGPTのパーティションの形式ではありません。」 というエラーがよくでた。

https://freesoft.tvbok.com/tips/efi_installation/diskpart_gpt_mbr.html

インストールDVDをUEFIブートした場合のみ、Windowsは GPT形式でインストールされます。 DVDを旧BIOS互換ブートした場合、Windows は MBR形式でインストールされます。

上記ブログを参照した程度の知識しかなかったのでBIOS=MBR,UEFI=GPTくらいのゆるい認識なので、 レガシーモード(BIOS)でしかブートできないWindowsにGPT強制されても...という 感じだったが、ubuntuでパーティションをGPTで作り直したらWindows10がインストールできようになった。(なんだったんだあれ？)

f:id:yuyubu:20190118185529j:plain

GRUBメニューが表示されない

dual環境を整備した後、起動時にwindows or ubuntuを選択するgrubメニューが表示されないという トラブルがあった。ちなみにgrubメニューがなくてもBIOSのUEFIブートの設定画面でUbuntuとWindowsの優先順位を変更することができる。 だけど、毎度起動OSを切り替えるたびにBIOSのメニューをカチカチいじるのは面倒なのでなんとかしてgrubメニューを出したい。

これはwindowsインストール後にubuntuでgrubをアップデートすることで対処できた。

sudo update-grub

f:id:yuyubu:20190118185524j:plain
grubメニュー。ubuntuとwindows boot managerが表示されている

askubuntu.com

セットアップするディスク以外は取り外す

ubuntuではsda,sdbの呼び方windows上ではディスク0,1,2,3...BIOS上ではインターフェース名(SATA1,M2等)と ２次記憶装置の名前を統一感の無い名前で表記しあってるので非常に混乱する。 のでOSをインストールする時は インストール対象のHDD/SSDとインストーラーのイメージが入っている記憶装置(USBメモリ/CD)の接続のみにとどめて、 他のデバイス(back up用HDDとか)は全部切り離しておいたほうが無難でしょう。

さて次はバックアップをどうするかでしょう。

SQL上で2状態3記号チューリングマシンをエミュレーションする　

SQL

SQLがチューリング完全かどうかは、意見が別れていると思いますが、

SQLや、ループの書けない表計算マクロなどもチューリング完全ではない。

it-words.jp

一般的にはwith recursive句が導入されたことによって再帰クエリが実行できるようになり、 チューリングマシンをSQLでシュミレートできるようになったので、　チューリング完全になったという風になっています。

で、今回実際にSQL上でチューリングマシンをエミュレートしてみようという挑戦になります。

blog.coelho.net

こちらのエントリにチューリングマシンのテーブル定義がありますが、動かすためのチューリングマシンのデータ(状態、シンボル、遷移関数)が無かったので、現在発見されているもっとも単純な万能チューリングマシンであるWolfram's 2-state 3-symbol Turing machineを利用しました。

CREATE TABLE State(    -- TM states
  sid INTEGER PRIMARY KEY,    -- 0 is always the initial state
  isFinal BOOLEAN NOT NULL,
  sname TEXT UNIQUE NOT NULL -- just for show
);

CREATE TABLE Symbol( -- TM symbols
  cid INTEGER PRIMARY KEY,  -- 0 is always the blank symbol
  cname TEXT UNIQUE NOT NULL
);

CREATE TABLE Transition( -- TM transition function
  sid INTEGER NOT NULL REFERENCES State,     -- initial state
  symbol INTEGER NOT NULL REFERENCES Symbol, -- & symbol
  UNIQUE(sid, symbol),
  new_state INTEGER NOT NULL REFERENCES State,
  new_symbol INTEGER NOT NULL REFERENCES Symbol,
  move INTEGER NOT NULL CHECK(move=-1 OR move=1)
);

CREATE TABLE Tape( -- TM initial tape contents
  tid INTEGER PRIMARY KEY,
  symbol INTEGER REFERENCES Symbol
);

(2,3)TMは遷移関数は全部で6個

f:id:yuyubu:20190115201437j:plain
(2,3)Turing Machine

凡例:{state, color} -> {state, color, offset}

{1, 2} -> {1, 1, -1},
{1, 1} -> {1, 2, -1},
{1, 0} -> {2, 1, 1 },
{2, 2} -> {1, 0, 1 },
{2, 1} -> {2, 2, 1 },
{2, 0} -> {1, 2, -1}

です。

データをいれます。適当に紙に起こして自分で考えながら書き起こしました。なお本データは(2,3)Turing machineのものですが、このブログ)にあるCTSでも可能かと思います。

INSERT INTO State VALUES(0,FALSE,1),(1,FALSE,2);

INSERT INTO Symbol VALUES(0,'0'),(1,'1'),(2,'2')

INSERT INTO Transition VALUES
(0,2,0,1,-1),
(0,1,0,2,-1),
(0,0,1,1, 1),
(1,2,0,0, 1),
(1,1,2,2, 1),
(1,0,0,2,-1)


INSERT INTO Tape VALUES(0,0);

以下がチューリングマシンを動かすクエリです

WITH RECURSIVE running(rid, sid, tape, pos) AS (
  -- first store initial tape contents
  SELECT 0, 0, ARRAY(SELECT symbol FROM Tape ORDER BY tid), 1
  UNION
  -- then proceed to compute iterations
  SELECT p.rid+1, t.new_state,
         -- build updated tape as an array
         p.tape[1:p.pos-1] ||                      -- prefix
           t.new_symbol ||                         -- updated cell
           p.tape[p.pos+1:array_length(p.tape,1)], -- suffix
         -- move cursor position
         p.pos+t.move
  FROM running AS p
  -- get state details, to know whether to stop
  JOIN State AS s ON (p.sid=s.sid)
  -- get corresponding state transition
  JOIN Transition AS t ON (t.sid=p.sid AND
                           -- coalesce defaults to blank
                           t.symbol=COALESCE(p.tape[p.pos],0))
  WHERE -- stop on a final state
        NOT p.rid = 100
)
-- just store the computed table
INSERT INTO Run
  SELECT * FROM running;

(2,3)Turing machineは終了状態がないため、100回目の処理終了時でストップするように条件を書き換えています。

rid | sid |            tape             | pos
-----+-----+-----------------------------+-----
  0 |   0 | {0}                         |   1
  1 |   1 | {1}                         |   2
  2 |   0 | {1,2}                       |   1
  3 |   0 | {2,2}                       |   0
  4 |   1 | {1,2,2}                     |   1
  5 |   1 | {2,2,2}                     |   2
  6 |   0 | {2,0,2}                     |   3
  7 |   0 | {2,0,1}                     |   2
  8 |   1 | {2,1,1}                     |   3
  9 |   1 | {2,1,2}                     |   4
 10 |   0 | {2,1,2,2}                   |   3
 11 |   0 | {2,1,1,2}                   |   2
 12 |   0 | {2,2,1,2}                   |   1
 ・・・・・・・・・・・・・・・・・・・・・・・・・・・
 90 |   0 | {2,1,1,1,2,2,2,1,2,2,1,2}   |   1
 91 |   0 | {1,1,1,1,2,2,2,1,2,2,1,2}   |   0
 92 |   1 | {1,1,1,1,1,2,2,2,1,2,2,1,2} |   1
 93 |   1 | {2,1,1,1,1,2,2,2,1,2,2,1,2} |   2
 94 |   1 | {2,2,1,1,1,2,2,2,1,2,2,1,2} |   3
 95 |   1 | {2,2,2,1,1,2,2,2,1,2,2,1,2} |   4
 96 |   1 | {2,2,2,2,1,2,2,2,1,2,2,1,2} |   5
 97 |   1 | {2,2,2,2,2,2,2,2,1,2,2,1,2} |   6
 98 |   0 | {2,2,2,2,2,0,2,2,1,2,2,1,2} |   7
 99 |   0 | {2,2,2,2,2,0,1,2,1,2,2,1,2} |   6
100 |   1 | {2,2,2,2,2,1,1,2,1,2,2,1,2} |   7

これをビジュアライズしたい。とりあえず桁を揃えてごにょごにょした。

1,0,0,0,0,0,0,0,0,0,0,0,0
1,2,0,0,0,0,0,0,0,0,0,0,0
2,2,0,0,0,0,0,0,0,0,0,0,0
1,2,2,0,0,0,0,0,0,0,0,0,0
2,2,2,0,0,0,0,0,0,0,0,0,0
・・・・・・・・・・・・・・・
2,2,1,1,2,2,2,1,2,2,1,2,0
2,1,1,1,2,2,2,1,2,2,1,2,0
1,1,1,1,2,2,2,1,2,2,1,2,0
1,1,1,1,1,2,2,2,1,2,2,1,2
2,1,1,1,1,2,2,2,1,2,2,1,2
2,2,1,1,1,2,2,2,1,2,2,1,2
2,2,2,1,1,2,2,2,1,2,2,1,2
2,2,2,2,1,2,2,2,1,2,2,1,2
2,2,2,2,2,2,2,2,1,2,2,1,2
2,2,2,2,2,0,2,2,1,2,2,1,2
2,2,2,2,2,0,1,2,1,2,2,1,2
2,2,2,2,2,1,1,2,1,2,2,1,2

で結果できたのがこの画像。若干桁揃えのルールが違うため、同じ形状にならなかったが、wolframのサイトの画像とほぼ同一ものもが得られた。(チューリングマシンがエミュレートできた？)

f:id:yuyubu:20190108202637p:plain
2 3 チューリングマシンの1~100世代後のテープの状態

うーんこれだけだとよくわからんということでチューリングマシンの原論文(Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem")を読んだけどさらに意味わからなくなった。論文名でググったらどうも日本語の解説書籍があるらしいので買って読んでます。

チューリングを読む コンピュータサイエンスの金字塔を楽しもう

チューリングを読む コンピュータサイエンスの金字塔を楽しもう

github.com

ポスタリゼーションとCannyのエッジ検出アルゴリズムの組み合わせでイラストから下絵の作成に挑戦

画像処理 OpenCV

いらすとやの画像を借りて試してみました。

www.irasutoya.com

f:id:yuyubu:20181227190046p:plain
対象画像

1.Gaussianオペレータを適用することによりエッジをぼかす
2.Sobelオペレータを適用し画像を微分する
3.微分画像を繊細化する
4.繊細化した結果の連結性を上げるために、2つの閾値を用いた２値化を行う

と複雑な手順が必要ですが、opencvなら関数一個で処理できます。

image = cv2.Canny(image,0,0,3)

f:id:yuyubu:20181227185311p:plain
普通にCannyアルゴリズムを適応

Cannyアルゴリズムをそのままイラストに適応するとうまく行きませんでした。 これはイラストやのイラストは肌や副部分にフェルト生地のような質感を感じさせる着色がなされているためだと思います。 また、イラストやの画像は問題ありませんが、ネットで拾ってきた野良画像は結構ノイズが乗っていることが多いのでそちらの影響も受けてしまいます。

例えば私のアイコン画像でそのまま試すと以下のようになりました。

f:id:yuyubu:20181227193002p:plain
Cannyアルゴリズムはノイズの影響に弱い

このフェルトのような質感をポスタリゼーションで均一化すればうまく行くのではないかと思い試してみました。

結果、posterlizationとdenoiseをCannyアルゴリズムの前に実施するとうまく行きました。

# denoiseのためのフォーマット変換
img_src = cv2.cvtColor(img_src,cv2.COLOR_GRAY2BGR)

# denoise
img_src = cv2.fastNlMeansDenoisingColored(img_src,None,10,10,7,21)

# ルックアップテーブルの生成

look_up_table = np.ones((256, 1), dtype = 'uint8' ) * 0

for i in range(256):
    if i <= 0:
       look_up_table[i][0] = 0
    elif i < 32:
       look_up_table[i][0] = 32
    elif i < 64:
       look_up_table[i][0] = 64
    elif i < 96:
       look_up_table[i][0] = 96
    elif i < 128:
       look_up_table[i][0] = 128
    elif i < 160:
       look_up_table[i][0] = 160
    elif i < 192:
       look_up_table[i][0] = 192
    elif i < 224:
       look_up_table[i][0] = 224
    else:
       look_up_table[i][0] = 255

#postrization実行
img_src = cv2.LUT(img_src, look_up_table)

#Canny

img_dst = cv2.Canny(img_src,0,0,3)

#bit反転
img_dst = cv2.bitwise_not(img_dst)

f:id:yuyubu:20181227184432p:plain
Canny関数適応前にdenoise処理とポスタリゼーション処理を実施

ですがこのプログラムは私のアイコン画像に対してはうまく動きませんでした。

f:id:yuyubu:20181227194213p:plain
うまく行かなかった例

なぜでしょうか。理由はポスタリゼーションで腕と背景の色が同一化されてしまったためです。 ポスタリゼーションの度合いを変えることで、こちらの画像もうまくエッジ検出できました。

f:id:yuyubu:20181231155411p:plain
うまくいった画像

ですがこのエッジ検出にはまだまだ課題があります。飛び出し坊やくんの

  • 手と顔
  • 手とズボン

の境界が検出できていません。この件に関しましてはまた後日描きたいと思います。

ちなみに今回のエントリのようなエッジ検出は画像の性質を見てうまく動くようなポスタリゼーションを実施する必要があります。