Scratchの仕様について

　Scratchという教育や学習様に作られたプログラミング言語がある。かく言う私も中学生の頃、Scratchが日本に来たあたりにScratchでコンピュータプログラミングを学んだ、言うなればScratch第一世代である。

　以前よりタートルだのRobo Designerだの色々な教育用プログラミング言語があったが、Scratchが今現在のプログラミング教育ムーブメントにおいて多く使われている理由はオブジェクト指向で構造化プログラミングという泥臭さだと思う。それまでの教育用プログラミング言語は僕が知っている限りフローチャートをそのまま実行する様な方式のものが多かったがScratchはそれらに比べ、実践的な文法を取っていて、c言語あたりにも少し勉強すれば容易に移行できるんじゃないとかと思う（僕の高専時代の友達はScratch風のc言語エディタを作っていたし）。

　どうでもいい前置きが長くなってしまったが、最近インタプリタとかを作っているうちにScratchのマルチパラダイムや、実行順序という物が気になって、暇を見つけてはちびちび調べていたのでそれについてここにメモしておく。

あくまでも僕個人が手探りで調べたものなので間違いがあったら教えていただけると助かります。

Scratchの１処理の実行範囲

Scratchのプログラムはマルチパラダイムであるが、実行する際はOSがひとつのCPUで複数のプログラムを動作させる様に、あるスクリプトのある区間を実行して、また別のスプライトのスクリプトのある実行区間を実行してということを繰り返している。

　具体的に言えば緑色のフラッグのStartブロックが呼び出されてプログラムが動作すると、下につながっているブロックを実行していき、描画ブロックと言った特殊なブロックを実行したら、そこでそのプログラムの実行を停止してスタンバイ状態にし、次のプログラム実行権を譲る。次に呼び出された時には特殊なブロックの下からまた実行すると言った具合である。

私が調べた結果、プログラムをスタンバイ状態に遷移させる命令は次に示す通りだ

• ｛見た目ブロック、動きブロック、音ブロック、ペンブロック｝を含む制御ブロックの終端

  

• クローンを呼び出した時（この時はプログラムが中断されクローン内部のプログラムを実行してから戻ってくるようだ）

多分他にもあるような気がするが僕が確認出来なのはこの２種類、赤丸で囲ったように、制御ブロックのうちスタンバイ状態に移行してしまうものは丁寧に↺マークががかいある。

Scratchのフレームレート

　Scratchは他のプログラミング言語と違いフレームという概念を気にせずプログラミングできるが、コンピュータプログラムである以上、フレームレートが存在する。スクラッチのフレームレートは３０FPSで固定でフレームごとにすべてのスプライトのすべてのスクリプトがスタンバイ状態に遷移するまで実行される。また、ターボモードを使えばフレームレート関係なく最速で実行されることになる。

　次のプログラムを実行してみれば実際にフレームレートを計測することができる。おそらく結果は３１になるはずだ。

Scratchの実行順序

　Scratchはマルチパラダイムなプログラミング言語だという、僕が使ってきた言語の中でマルチパラダイムと言えそうなのはVerilogくらいしか無いのだけど、ScratchはVerilogのマルチパラダイムと違って、プログラムの呼び出されるすべて並列していたり、入り乱れたたりしない事が分かった。僕が調べて分かったのはルールと次の様な感じである。

• あとから作られたスプライトの方が先に実行される。
• スプライト中の同じ条件で実行されるスクリプトがある場合最後、最初に作られたスプライトの方が先に実行される

次のプログラムを見てほしい、プログラムを見ただけでは実行結果がどうなるかわからない、このような場合は最初に操作されたものから実行され、最後に操作されたものが最後に実行される。例えばそれぞれのスクリプトの上にふられた番号の通りにプログラムを作成したとすると結果は-5となる。

クローンの最大数

　Scratchにはスプライト自身がクローンを作成するという機能があるが、この複製できる最大数はすべてのスプライト合わせて３０１となっている。次のプログラムを実行してもらえばクローンの最大数が３０１である事が確認できると思う。

以上で今まで調べて来た仕様に関する説明を終える。間違っている部分も多いと思われるが、もし誰かの参考になるのであれば嬉しい限りである。

TOEIC

　目覚まし時計の単調なビープ音で目が覚める。うるさいので叩く様にしてけした。今日はTOEICを受けに行かねばならないのだが、開場は11:45ごろだったはずなので移動時間を２時間程度と予想するとあと1時間半程度寝られるので二度寝した。私の下宿は駅から遠く自転車で一時間程度かかってしまう、そこからまた会場の名古屋まで電車で1時間程度かかるという計算だ。別に近所の豊橋会場で受けてもいいのだけれど、理由をつけて名古屋まで出かけたかったので、毎回名古屋会場を指定して申し込んでいる。

　そこから何度か二度寝、三度寝と繰り返していると9:30あたりになっていた。適当に着替えようと思ったが、洗濯をサボっていたため、あまり洗いたての服が残っていない、仕方なく下着とズボンは洗ったものを、シャツは昨日着たものを洗濯カゴから引っ張りだしてまた着る。昨日は家でじっとしていたので、あまり汚れていないだろう。それから、必要なものを適当にトートバッグに突っ込んでマウンテンバイクに乗り駅に向かう、以前は週末になるたびに駅前に遊びに言っていたのだが、最近は飽きてしまってあまり足を運ばなくなっている。

　駅につくと腕時計を家に忘れたことに気づいた。　しょうが無いので駅ビルの中で時計が安く売っていないか探していると、運良く１００円ショップが見つかった。腕時計はなかったが親指サイズの小型の置き時計を見つける事ができたのでそれを購入した。

　駅に向かい券売機で切符を購入した。名鉄を利用したかったのだが間違えてJRの切符を購入してしまった。「まあ降りるときに精算すればいいだろう」と考え、改札をくぐり名鉄のホームに向かう。すでに１１時近くなってしまっていることに気づきかなり焦ったがなんとか、11:15の名古屋行きに乗車した。

　適当に席に座り先ほど買った時計の時間合わせをしようとした。スマートフォンを開き時間を確認するとすぐに電源が切れてしまった。しょうが無いので電車の発車時刻に合うように時間を合わせ、ドアが閉まった瞬間にスタートさせた。普段電車に乗る機会が無いので電車に乗るだけでも十分に楽しく感じる。何より車窓から見える景色にだんだん大きな建物が増え都会に近づいているのが見えるのが楽しかった。

　今回の名古屋会場は金山駅の近くなのでそこで降りる。駅を出て受験票の裏に描いてある地図を眺めているとそちらへ向かっていく人の流れがあったのでその後を追った。開場は東海興業専門学校という学校の裏にある施設だった。よくわからないが教室のようなものがたくさんあった。多分専門学校の一部としても使われているのだろう。

　入り口で自分の受験する部屋を確認し、部屋の前の受付で身分証明書と受験票を見せ、部屋に入った。部屋にはほとんどの受験者がすでに着席していた。適当に参考書を開いて眺めてると、試験官がいつものやたら冗長な注意書きを読み始める。証明写真付きの身分証明書と受験票を机の上に置くように言われたので、そのとおりにした。ふと横を見ると隣の受験者は大学生らしく名古屋大学の学生証を机の上にだしていた。なんだか僕の劣等感を煽り、きっとこの人は僕より全然良いスコアを取るのだろうと思うと試験を受ける前からなんかアレな気分になった。

　試験はリスニングとリーディングで構成されているが、リスニングはいつもどおりの半分しかわからない感じ、リーディングはパート７の中盤までしか終わらせることができなかった。テスト終盤には隣のやつの名古屋大学の学生書が頭の中でチラチラして集中できなくなってしまった。あまり真面目に対策せず、自分で精一杯やったと思えていいないからこうなってしまうのだろう。自分を恨むしか無い。

　院試の願書提出が６月だからあと受けることのできるTOEICは３月と４月しか無い、そんな時に真面目に取り組まないとは「全く私は何を考えているのだろう」とか思ってしまった。

つづく

ガバガバなステレオマッチングとか

どうも、とり天です。研究室配属ですが、なんか温室とかやってる研究室でセンサネットワークを使ったようなIoTな事ができそうなので良かったなと思います。

　最近ですがアルバイトに行き詰っています、というのはOpenCVを使ったアルバイトをしているのですが、呼び出しても動かないステレオマッチングの関数メンバがあったので、ソースコードを読んでみたところ、なんと関数内が空っぽで"return 0"になっていました。結構重要な機能だったのでショックでしたね。それと同時に自力でステレオマッチングを作ってみたので紹介します。EmacsでインデントしたあとGeditで編集してめちゃくちゃなインデントになっていますが気にしない、あとステレオ対応のWEBカメラ(ZED)とかで読み込んで分割する様に書かれてますが、ステレオカメラ持っていない人は適当に左右の視差のある画像を読み込むようにしてね。

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <stdexcept>
#include <opencv2/core/utility.hpp>
#include <opencv2/core.hpp>
#include "opencv2/highgui.hpp"
#include "opencv2/imgproc.hpp"

//#include <cstdlib> 

//dvide image
void ImgDiv(cv::Mat src, cv::Mat right, cv::Mat left){
  int width = src.cols/2;
  int hight = src.rows;
  for(int i = 0; i < hight; i++){
    cv::Vec3b *p_src   = src.ptr<cv::Vec3b>(i);
    cv::Vec3b *p_right = right.ptr<cv::Vec3b>(i);
    cv::Vec3b *p_left  = left.ptr<cv::Vec3b>(i);
    for(int j = 0; j < width; j++){
      p_left[j] = p_src[j];
      p_right[j] = p_src[j + width];
    }
  }
}

void Depth2Hsv(cv::Mat src, cv::Mat res){
  if(src.cols != res.cols || src.rows != res.rows){
    //cout << "data size is not mach" << endl;
    return ;
  }
  int width = src.cols;
  int hight = src.rows;
  for(int i = 0; i < hight; i++){
    cv::Vec3b *p_src = src.ptr<cv::Vec3b>(i);
    cv::Vec3b *p_res = res.ptr<cv::Vec3b>(i);
    for(int j = 0; j < width; j++){
         p_res[j][0] = p_src[j][0] / 2;
         p_res[j][1] = 255;
         p_res[j][2] = 220;

    }
  }
}
void my_sad(cv::Mat right, cv::Mat left, cv::Mat dist ,int block_size, int diff ){
  if(right.channels() != 1 || left.channels() != 1 ||  dist.channels() != 1){
    std::cout << "Error : bad channnel" << std::endl;
    return ;
  }
  if(right.cols != left.cols || right.rows != left.rows){
    std::cout << "Error : not mach input image size" << std::endl;
    return ;
  }

  if(block_size % 2 != 1  ){
    std::cout << "Error : block size is not  2n + 1 " << std::endl;
    return ;
  }

  dist = cv::Scalar(0,0,0);
  std::cout << "width" << right.cols << " height" << right.rows << std::endl;
  int width = right.cols - block_size;
  int hight = right.rows - block_size;
  cv::Mat tmp = dist.clone();

  std::vector<std::vector<int> > arr;
  arr.resize(hight);
  for( int i=0; i < hight; i++ ){
    arr[i].resize(width,255);
  }
  for(int d = 0; d < diff ; d+=1){
    for(int i = (block_size/2+ 1) ; i < hight - (block_size/2+ 1) ; i += 1){
      cv::Vec3b *p_dist   = dist.ptr<cv::Vec3b>(i);
      cv::Vec3b *p_right = right.ptr<cv::Vec3b>(i);
      cv::Vec3b *p_left  = left.ptr<cv::Vec3b>(i);

      for(int j = (block_size /2) + 1; j < width - (block_size/2+ 1) -diff ; j+= 1 ) {
	int right_sum = 0;
	int left_sum = 0;      
	for(int l = 0; l < block_size ; l++){
	  cv::Vec3b *p_right = right.ptr<cv::Vec3b>(i - (block_size/2) + l);
	  cv::Vec3b *p_left  = left.ptr<cv::Vec3b>(i - (block_size/2) + l);
	  for(int m = 0; m <   block_size; m++){
	    right_sum += p_right[j/3][ - (block_size/2) + m + j % 3];
	    left_sum += p_left[j/3][ - (block_size/2) + m + d + j % 3];
	  } 
	}
	int delta =  ( (double)abs(right_sum - left_sum) / (double)(block_size * block_size *255)) * 255.0 ;

	if(delta < arr[i][j]) {
	  arr[i][j] = delta;
	  cv::Vec3b *p_dist = dist.ptr<cv::Vec3b>(i);
	  p_dist[j/3][ j % 3] =  (int)(( (double)d / (double)diff) * 255.0);
	}
      }
    }
  }
}

int main (void){
  cv::Mat src;
  cv::VideoCapture cap(0);
  int block = 7;
  int diff = 12;

  while(1){
    cap >> src;
    cv::resize(src, src, cv::Size(), 0.5, 0.5);
    cv::Mat right(src.rows, src.cols*0.5,src.type());
    cv::Mat left(src.rows, src.cols*0.5,src.type());
    ImgDiv(src,right,left);
    cv::cvtColor(right, right, CV_RGB2GRAY);
    cv::cvtColor(left, left, CV_RGB2GRAY);
    cv::Mat dist = right.clone();
     my_sad( right, left, dist , block, diff );
     cv::cvtColor(dist, dist, CV_GRAY2RGB);
     cv::Mat color(dist.rows, dist.cols, CV_8UC3);
     Depth2Hsv(dist, color);
     cv::cvtColor(color, color, CV_HSV2RGB);

     cv::imshow("window_r", right);
     cv::imshow("window_l", left);
     cv::imshow("window_d", color);
     
     cv::createTrackbar("block size","window_d",&block, 13,NULL,NULL);
     block = (block < 3  )? block = 3 : (block %2 != 1)? block - 1 : block;
     cv::createTrackbar("diffarence","window_d",&diff, 255,NULL,NULL); 
    int key = cv::waitKey(1);
    if(key == 113)//q
      {
	break;//
      }
    else if(key == 115)//s
      {
	cv::imwrite("img.png",dist );
      }
  }
}

まあアルゴリズムとしてはSADを用いたブロックマッチングを行っています。すごく適当な上に並列化もなにもしていないので、すごく重いです。

結果は次の画像に示す感じです。近いものほど赤く表示して、遠くのものほど青く表示しています。なんかキャリブレーションすら面倒くさくてしていませんがそれなりに遠くのものは遠くに、近くのものは近くと認識できているんじゃないかなぁ。部屋汚いね

左の画像

右の画像

深度マップ

まあ詳しい話とかは今度の技術書展で豊橋技科大コンピュータクラブの出す部誌に載せようと思うので、そのあとブログにも簡単に載せようかな

研究室配属

さてさて、今年も12月を迎え研究室配属の季節がやってまいりました。

結論から言って死にたい

本当に嫌で仕方ない。こう言うの書けるのはブログだけだから書く、

と言うのは僕は第一志望の学科に落ちてしまい今の環境生命工学課程にいるわけですが、現に半分単位落としてますし(卒業単位は足りる予定)化学、生物学が大嫌いで、バイトのプログラミングが楽しくてしょうがないのが現在の状況です。

はっきり言って高専卒で就職した方が何倍も良かったと思うし、大学に来たのは20代の貴重な2年間を学費とともに溝に捨てる最悪の選択だったと思います。

何一つ将来役に立ちそうな事は学んで無いですからね。小心者なんで講義はちゃんと出てるんですけど、化学式を見るたびに胸が張り裂けそうな辛い気持ちになります。

そんな中で研究室配属とか言い出すと死にたくてしょうがないわけです。第二志望の欄に環境生命工学課程とか書いてしまった。自分に怒りしか湧いてこない、

と言うわけで、もうすぐb4の卒研発表会があって、その後に研究室配属があるんで、なるべく楽そうな研究室を志望する予定です。

高専の時は放任主義で進捗チェックもあまりしない研究室だったのと、教員が専門外の分野の研究をしていたので、週報を書く必要も無く、ひたすら自分のペースで研究を続ける事が出来ました。一日18時間卒研のプログラムを書き続けり、誰にも邪魔されずリソースをじゃんじゃんブチ込める状況が楽しくてしょうがなかったのをよく覚えています。

化学に対してはそんな風に取り組める気が全くしないです。有機化学は嫌いでしょうがないし、生物系は単位全滅だし、無機は頭が足りないし、そもそもピペットの類が嫌いでしょうがない、八方ふさがりの状況です。

だから楽ちんと噂の社会学系の研究室で希望を出そうと思います。なんかゴミの分別表のアプリ作ってる所もあったので、職業プログラマ気触れの僕としてはまあ案内アプリを作るのは苦労しないだろうと思うので。大学院はちゃんと情報系のところに行けると良いな、大学院落ちたら化学の学位が付くと嫌なので中退して就職しようかな。

アルバイト始めました

どうも、前期に授業取りすぎて半分落としたとり天です。

ついこないだなのですが、知り合いからGPGPU関連のアルバイトを御紹介いただきまして、それをやることにしました。

バイトと言っても在宅で時間を自由に決められるので、昼間に時間を取りにくい僕に合ってると思います。

今もらってる仕事はドキュメントの作成なんで高専の学生実験みたいな感じですね。

スタックマシンの実装方法

状態遷移図

今回は前回作成したスタックマシン型のCPUをVerilogで実装する。そのためにCPUの動作を表した状態遷移図の作成を行った。

状態遷移図の各状態での動作は以下に示す通りである。

1. 命令フェッチ
2. 命令デコード
3. データフェッチ
4. データ操作命令実行
5. 演算命令実行

　である。S１ではプログラム・カウンタの値から命令の読み出しを行う、S2では命令の解釈を行う、S３では必要であればデータのフェッチを行う、Ｓ４とS5は命令の実行であり、S4ではデータ操作命令の実行、S5では演算命令の実行を行う。

　メインメモリに二度アクセスするPush命令とPop命令を除き、命令の行う処理は１サイクルで実行できる内容であるが、デバッグのしやすさと、動作の理解のしやすさを考え、マルチサイクルで命令の実行を行う。

コンピュータシステムの構成

CPUだけではコンピュータとして成立せず、プログラムを実行できないので、CPUにメインメモリを接続する。このメインメモリには初期状態では実行するプログラムや、プログラム上で扱う定数などが格納されている。またプログラム実行時の変数等もメインメモリ上で扱われることになる。

メインメモリとCPUは10bitのアドレスバス、16bitのCPUデータ入力バス、16bitのCPUデータ出力バス、1bitのメモリ制御信号により接続される、

アドレスバスはメモリ上のデータを参照したり、メモリ上でデータを格納したり、する時にメインメモリ上のアドレスを指定するために使用される。CPUデータ入力バスはメインメモリからデータを読み出すのためのデータバスである。CPUデータ出力バスはCPUからメインメモリへデータを書き出すためのデータバスである。メモリ制御信号はメインメモリに対して行う操作を書き込みか、読み込みか指定するために使用される。今回の場合は読み込み/書き込みどちらの線を１にしたかで動作をしてできるようにする。

バスの動作は例えば0x0ff番地にデータ0x0064を書き込みたい場合は、アドレスバスを0xffに,CPUデータバスに0x64を指定し、書き込み信号を１にすれば良い。この状態でシステムクロックの立ち上がりが発生すると指定したアドレスにデータの書き込みが行われる。

Verilogによるスタックマシンの作成

スタックマシン

　スタックマシンとはデータをスタックと呼ばれるデータ構造を用いた計算機である。スタックと呼ばれるLastInFirstOutのデータ構造Push（データの挿入）、Pop（データの取り出し）、演算、という3種類の操作を行うことで計算を行う。このあたりに関しては詳しく解説しているサイトを見てほしい。

　多くのインタプリタ型言語の処理系で用いられる中間言語はスタックマシンであることが多い、しかし現在流通しているCPUのほとんどはレジスタと呼ばれるCPU内部の商用呂のランダムアクセスメモリを用いたものである。そこでverilogを用いてスタックマシンを作成してみようという考えに至った。HDLを用いたFPGA上で動作するスタックマシンは別に珍しいものではなく前例も多く存在するが、今回の目的はエクササイズであり、作成するスタックマシンは実用性では無く、なるべくシンプルな命令体系にすることに重点を置く。

今回作成するCPU

今回作成するCPUは命令長と扱える数値の大きさから、16bitCPUとした。命令も16bit、扱える数も16bitである。マルチサイクルプロセッサで、１命令の実行に４クロックの時間を要する。

 命令体系

純粋なスタックマシンは基本的にPush,Pop、演算という操作で計算を行うが、それだけではプログラムの制御ができないので、制御命令も必要となる、次の表に示すのが今回設計するCPUの命令セットである。

命令	バイナリ	機能
ADD	0b00000100_00000000	スタックから2つPopし加算結果をPushする
SUB	0b00001000_00000000	スタックから2つPopし減算結果をPushする
MUL	0b00001100_00000000	スタックから2つPopし乗算結果をPushする
DIV	0b00010000_00000000	スタックから2つPopし除算結果をPushする
PUSH	0b100001XX_XXXXXXXX	XXで指定したアドレスの値をPushする
POP	0b100010XX_XXXXXXXX	スタックから1つPopしXXで指定したアドレスに格納する
JMP	0b100011XX_XXXXXXXX	XXで指定したアドレスにプログラムカウンタを飛ばす
IZ	0b000100XX_XXXXXXXX	スタックのトップが0ならXXで指定したアドレスにプログラムカウンタを飛ばす
INZ	0b000100XX_XXXXXXXX	スタックのトップが0でないならXXで指定したアドレスプログラムカウンタを飛ばす

命令は16ビットから１０ビットまでにかけての命令を示すコードと、10ビット目から１ビット目にかけてのアドレスを示すフィールドで構成する。命令のフィールド先頭の16ビット目が命令のタイプを示しており、このビットが1だとPUSHなどのデータ制御命令とJMPなどのプログラム制御命令である。０だと演算命令である。

次回以降は今回設計した命令セットをVerilogで実装してゆく