久しぶりにC言語でQueueを書いた

力試しでヘッダを書いてChatGPTとClaudeに破壊を試みてもらいました。

人生でQueueを書く機会って結構あると思うんですが、品質に関してはあんまり考えてなかったのでAIに聞けば脆弱性が見つかるんじゃないかと色々試してみました。試してみましたが見つかりませんでした。いかがでいしたか？

くコ:彡いか

Queueの本体

ヘッダーファイル:queue..h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdint.h>

#define DTYPE uint8_t

/* キュー API */
DTYPE  dequeue(void);
void   enqueue(DTYPE x);
uint32_t is_empty(void);
uint32_t is_full(void);
void   initialize_queue(void);

#endif /* QUEUE_H */

メインファイル:queue.c

#include"queue.h"
#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define LEN 256

static DTYPE ring_buffer[256];
static uint32_t head = 0;
static uint32_t tail = 0;

DTYPE dequeue(void){
    if(is_empty()){
        return NULL;
    }

    int tail_address = tail % LEN;

    if(tail > LEN && head > LEN){
        tail = tail - LEN;
        head = head - LEN;
    }
    tail = tail + 1;
    return ring_buffer[tail_address];
}

void initialize_queue(){
    head = 0;
    tail = 0;
}

void enqueue(DTYPE x){
    if(is_full()){
        return;
    }
    int head_address = head % LEN;
    if(tail > LEN && head > LEN){
        tail = tail - LEN;
        head = head - LEN;
    }
    head = head + 1;
    ring_buffer[head_address] = x;
}

uint32_t is_empty(){
    if(head - tail <= 0){
        return 1;
    }else{
        return 0;
    }
}

uint32_t is_full(){
    if(head - tail >= 255){
        return 1;
    }else{
        return 0;
    }
}

ChatGPT

// test_queue.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include "queue.h"

#define LEN 256
#define PASS "\033[32mPASS\033[0m"
#define FAIL "\033[31mFAIL\033[0m"

static void check_print(const char *name, int ok){
    printf("%-35s : %s\n", name, ok ? PASS : FAIL);
    if(!ok){
        fflush(stdout);
    }
}

/* 単純な理想キュー（検査用） */
typedef struct {
    int buf[LEN];
    int head, tail; // head index of next push, tail index of next pop
    int count;
} ideal_q;

static void ideal_init(ideal_q *q){
    q->head = q->tail = 0;
    q->count = 0;
    for(int i=0;i<LEN;i++) q->buf[i] = -1;
}
static int ideal_empty(ideal_q *q){ return q->count == 0; }
static int ideal_full(ideal_q *q){ return q->count >= (LEN-1); }
static void ideal_enqueue(ideal_q *q, int v){
    if(ideal_full(q)) return;
    q->buf[q->head] = v & 0xFF;
    q->head = (q->head + 1) % LEN;
    q->count++;
}
static int ideal_dequeue(ideal_q *q, int *out){
    if(ideal_empty(q)){ *out = -1; return 0; }
    *out = q->buf[q->tail];
    q->tail = (q->tail + 1) % LEN;
    q->count--;
    return 1;
}

/* テスト1: 空キューからのdequeue の挙動 */
static int test_empty_dequeue(){
    initialize_queue();
    uint8_t v = dequeue(); // 実装は空なら NULL を返す（=0）
    int is_emp = is_empty();
    // DTYPE は uint8_t なので NULL==0。empty のとき 0 を返すのは ambiguous。
    // 成功条件: 実装が空であると報告すること（is_empty==1）かつ
    // dequeue() が 0 を返す（現在の実装の仕様を確認するため）。
    int ok = (is_emp == 1);
    check_print("test_empty_dequeue: is_empty()==1?", ok);
    if(!ok) return 0;
    printf("  dequeue() returned: %u (note: 0 == NULL for uint8_t)\n", (unsigned)v);
    return 1;
}

/* テスト2: 基本FIFO */
static int test_basic_fifo(){
    initialize_queue();
    int N = 100;
    for(int i=0;i<N;i++) enqueue((uint8_t)i);
    int ok = 1;
    for(int i=0;i<N;i++){
        uint8_t v = dequeue();
        if(v != (uint8_t)i){
            printf("  FIFO mismatch at i=%d: got=%u expected=%d\n", i, (unsigned)v, i);
            ok = 0;
            break;
        }
    }
    check_print("test_basic_fifo", ok);
    return ok;
}

/* テスト3: 満杯の振る舞い */
static int test_fill_and_overflow(){
    initialize_queue();
    // 実装は最大 LEN-1 (=255) 要素を入れる設計っぽい
    for(int i=0;i<LEN;i++){
        enqueue((uint8_t)i);
    }
    // ここで is_full() が 1 であることを期待
    int full = is_full();
    check_print("test_fill_and_overflow: is_full()", full==1);
    // 255 個取り出して順序確認
    int ok = 1;
    for(int i=0;i<LEN-1;i++){
        uint8_t v = dequeue();
        if(v != (uint8_t)i){
            printf("  fill/overflow mismatch at i=%d: got=%u expected=%d\n", i, (unsigned)v, i);
            ok = 0;
            break;
        }
    }
    check_print("test_fill_and_overflow: drain order", ok);
    return full && ok;
}

/* テスト4: ラップアラウンド／長期ストレス（理想キューと常時比較） */
static int test_stress_random(unsigned long ops, unsigned seed){
    initialize_queue();
    ideal_q iq;
    ideal_init(&iq);
    unsigned next_val = 1;
    srand(seed);
    for(unsigned long i=0;i<ops;i++){
        int do_enqueue;
        // enqueue をやや優先して長時間満杯状態を作りやすくする
        if(ideal_full(&iq)) do_enqueue = 0;
        else if(ideal_empty(&iq)) do_enqueue = 1;
        else do_enqueue = (rand() & 1);
        if(do_enqueue){
            uint8_t v = (uint8_t)(next_val & 0xFF);
            enqueue(v);
            ideal_enqueue(&iq, v);
            next_val++;
        }else{
            int ideal_v;
            int ideal_has = ideal_dequeue(&iq, &ideal_v);
            uint8_t got = dequeue();
            if(!ideal_has){
                // ideal empty -> we expect implementation to be empty (dequeue returns 0 and is_empty==1)
                if(is_empty() != 1){
                    printf("  Stress mismatch: ideal empty but is_empty()==0 at op %lu\n", i);
                    return 0;
                }
                // dequeue() returns 0 both for empty and data==0; we can't fully distinguish here,
                // but if ideal had element and value==0 we'd already have set ideal_has==1.
            }else{
                if(got != (uint8_t)ideal_v){
                    printf("  Stress mismatch at op %lu: got=%u expected=%d\n", i, (unsigned)got, ideal_v);
                    return 0;
                }
            }
        }
    }
    check_print("test_stress_random", 1);
    return 1;
}

/* テスト5: 空時に 0 の値を入れたときの区別不可能性を示す */
static int test_zero_ambiguity(){
    initialize_queue();
    // 空で dequeue() -> returns 0 (NULL)
    uint8_t v_empty = dequeue();
    int emp = is_empty();
    // enqueue 0, dequeue -> 0 (but same as empty)
    enqueue(0);
    uint8_t v_data = dequeue();
    int emp_after = is_empty();
    int ambiguous = (v_empty == 0) && (v_data == 0) && (emp && emp_after);
    if(ambiguous){
        printf("  Ambiguity detected: empty-dequeue -> %u, enqueue(0)/dequeue -> %u\n",
               (unsigned)v_empty, (unsigned)v_data);
        printf("  Explanation: dequeue() returns 0 for empty (NULL). Since DTYPE==uint8_t, value 0 is indistinguishable from empty.\n");
    }
    check_print("test_zero_ambiguity (empty vs value 0)", ambiguous==1);
    return ambiguous;
}

int main(void){
    int all_ok = 1;
    printf("=== queue implementation stress tests ===\n");
    if(!test_empty_dequeue()) all_ok = 0;
    if(!test_basic_fifo()) all_ok = 0;
    if(!test_fill_and_overflow()) all_ok = 0;

    // ランダムストレステスト：比較的長めに回す（必要なら増やして下さい）
    unsigned long ops = 200000; // 20万操作
    unsigned seed = (unsigned)time(NULL);
    printf("Running random stress (%lu ops, seed=%u)...\n", ops, seed);
    if(!test_stress_random(ops, seed)) all_ok = 0;

    if(!test_zero_ambiguity()) all_ok = 0;

    printf("=== RESULT: %s ===\n", all_ok ? PASS : FAIL);
    return all_ok ? 0 : 1;
}

全部PASS

Claude4.1

#include "queue.h"
#include <stdio.h>
#include <assert.h>
#include <stdint.h>

// テスト結果を表示するマクロ
#define TEST_PASS(name) printf("[PASS] %s\n", name)
#define TEST_FAIL(name, msg) printf("[FAIL] %s: %s\n", name, msg)

void test_basic_functionality() {
    printf("\n=== Test 1: 基本機能テスト ===\n");
    initialize_queue();
    
    // 空の確認
    if (is_empty() != 1) {
        TEST_FAIL("初期状態", "キューが空でない");
        return;
    }
    
    // エンキュー・デキューの基本動作
    enqueue(42);
    DTYPE val = dequeue();
    if (val != 42) {
        TEST_FAIL("基本エンキュー・デキュー", "値が一致しない");
        return;
    }
    
    TEST_PASS("基本機能テスト");
}

void test_full_capacity() {
    printf("\n=== Test 2: 容量限界テスト ===\n");
    initialize_queue();
    
    int count = 0;
    // 満杯になるまでエンキュー
    while (!is_full() && count < 257) {
        enqueue(count & 0xFF);
        count++;
    }
    
    if (count != 255) {
        char msg[100];
        sprintf(msg, "容量が255でない (実際: %d)", count);
        TEST_FAIL("容量確認", msg);
        return;
    }
    
    // 満杯状態で追加エンキューを試みる
    enqueue(99);
    
    // デキューして数を確認
    int dequeue_count = 0;
    while (!is_empty() && dequeue_count < 257) {
        dequeue();
        dequeue_count++;
    }
    
    if (dequeue_count != 255) {
        char msg[100];
        sprintf(msg, "デキュー数が255でない (実際: %d)", dequeue_count);
        TEST_FAIL("満杯時の動作", msg);
        return;
    }
    
    TEST_PASS("容量限界テスト");
}

void test_empty_dequeue() {
    printf("\n=== Test 3: 空キューからのデキュー ===\n");
    initialize_queue();
    
    DTYPE val1 = dequeue();  // 空の状態でデキュー
    enqueue(0);              // 0をエンキュー
    DTYPE val2 = dequeue();  // 0をデキュー
    DTYPE val3 = dequeue();  // 再び空の状態でデキュー
    
    if (val1 != val2 || val2 != val3) {
        // 3つとも0のはず
        TEST_PASS("空デキューのエラー値識別不可");
    } else {
        TEST_FAIL("空デキューのエラー値", "正常な0と区別できない");
    }
}

void test_wraparound_behavior() {
    printf("\n=== Test 4: 循環動作テスト ===\n");
    initialize_queue();
    
    // 満杯にする
    for (int i = 0; i < 255; i++) {
        enqueue(i & 0xFF);
    }
    
    // 全て取り出す
    for (int i = 0; i < 255; i++) {
        DTYPE val = dequeue();
        if (val != (i & 0xFF)) {
            TEST_FAIL("循環動作1", "値の順序が不正");
            return;
        }
    }
    
    // 再度満杯にする
    for (int i = 0; i < 255; i++) {
        enqueue((i + 100) & 0xFF);
    }
    
    // 最初の値を確認
    DTYPE first = dequeue();
    if (first != 100) {
        char msg[100];
        sprintf(msg, "2回目の循環で最初の値が不正 (期待: 100, 実際: %d)", first);
        TEST_FAIL("循環動作2", msg);
        return;
    }
    
    TEST_PASS("循環動作テスト");
}

void test_alternating_pattern() {
    printf("\n=== Test 5: 交互操作パターンテスト ===\n");
    initialize_queue();
    
    // 満杯にする
    for (int i = 0; i < 255; i++) {
        enqueue(i & 0xFF);
    }
    
    int failed = 0;
    // 1つデキュー、1つエンキューを繰り返す
    for (int i = 0; i < 1000; i++) {
        DTYPE val = dequeue();
        enqueue(0xFF);
        
        // 常に満杯状態を維持しているはず
        if (!is_full()) {
            failed = 1;
            break;
        }
    }
    
    if (failed) {
        TEST_FAIL("交互操作", "満杯状態が維持されない");
    } else {
        TEST_PASS("交互操作パターンテスト");
    }
}

void test_stress_overflow() {
    printf("\n=== Test 6: 長期ストレステスト ===\n");
    initialize_queue();
    
    // 大量の操作でオーバーフローを狙う
    int failed = 0;
    for (long i = 0; i < 100000L; i++) {
        enqueue(1);
        if (is_empty()) {
            failed = 1;
            break;
        }
        dequeue();
        if (!is_empty()) {
            failed = 1;
            break;
        }
        
        if (i % 10000 == 0) {
            printf("  Progress: %ld iterations\n", i);
        }
    }
    
    if (failed) {
        TEST_FAIL("ストレステスト", "予期しない状態変化");
    } else {
        TEST_PASS("長期ストレステスト");
    }
}

void test_data_integrity() {
    printf("\n=== Test 7: データ整合性テスト ===\n");
    initialize_queue();
    
    // 特定のパターンでデータを入れる
    for (int i = 0; i < 100; i++) {
        enqueue(i & 0xFF);
    }
    
    // 50個取り出す
    for (int i = 0; i < 50; i++) {
        DTYPE val = dequeue();
        if (val != (i & 0xFF)) {
            TEST_FAIL("データ整合性1", "値が不正");
            return;
        }
    }
    
    // さらに100個追加
    for (int i = 100; i < 200; i++) {
        enqueue(i & 0xFF);
    }
    
    // 残りを取り出して確認
    for (int i = 50; i < 100; i++) {
        DTYPE val = dequeue();
        if (val != (i & 0xFF)) {
            TEST_FAIL("データ整合性2", "値が不正");
            return;
        }
    }
    
    for (int i = 100; i < 200; i++) {
        DTYPE val = dequeue();
        if (val != (i & 0xFF)) {
            TEST_FAIL("データ整合性3", "値が不正");
            return;
        }
    }
    
    if (!is_empty()) {
        TEST_FAIL("データ整合性4", "キューが空でない");
        return;
    }
    
    TEST_PASS("データ整合性テスト");
}

void test_boundary_conditions() {
    printf("\n=== Test 8: 境界条件テスト ===\n");
    initialize_queue();
    
    // 254個入れる（満杯の1つ手前）
    for (int i = 0; i < 254; i++) {
        enqueue(i & 0xFF);
    }
    
    if (is_full()) {
        TEST_FAIL("境界条件1", "254個で満杯判定");
        return;
    }
    
    // もう1つ追加（満杯になるはず）
    enqueue(254);
    
    if (!is_full()) {
        TEST_FAIL("境界条件2", "255個で満杯にならない");
        return;
    }
    
    // 1つ取り出す
    dequeue();
    
    if (is_full()) {
        TEST_FAIL("境界条件3", "254個で満杯判定が続く");
        return;
    }
    
    TEST_PASS("境界条件テスト");
}

void test_reinitialize() {
    printf("\n=== Test 9: 再初期化テスト ===\n");
    initialize_queue();
    
    // データを入れる
    for (int i = 0; i < 100; i++) {
        enqueue(i & 0xFF);
    }
    
    // 再初期化
    initialize_queue();
    
    if (!is_empty()) {
        TEST_FAIL("再初期化", "キューが空にならない");
        return;
    }
    
    // 新しいデータを入れて取り出す
    enqueue(42);
    DTYPE val = dequeue();
    
    if (val != 42) {
        char msg[100];
        sprintf(msg, "再初期化後の値が不正 (期待: 42, 実際: %d)", val);
        TEST_FAIL("再初期化後の動作", msg);
        return;
    }
    
    TEST_PASS("再初期化テスト");
}

void test_massive_cycle() {
    printf("\n=== Test 10: 大量サイクルテスト ===\n");
    initialize_queue();
    
    int failed = 0;
    // 255個の追加と削除を繰り返す
    for (int cycle = 0; cycle < 100; cycle++) {
        // 満杯にする
        for (int i = 0; i < 255; i++) {
            enqueue((cycle + i) & 0xFF);
        }
        
        if (!is_full()) {
            failed = 1;
            break;
        }
        
        // 全て取り出す
        for (int i = 0; i < 255; i++) {
            DTYPE val = dequeue();
            if (val != ((cycle + i) & 0xFF)) {
                failed = 1;
                break;
            }
        }
        
        if (!is_empty()) {
            failed = 1;
            break;
        }
        
        if (cycle % 10 == 0) {
            printf("  Cycle %d completed\n", cycle);
        }
    }
    
    if (failed) {
        TEST_FAIL("大量サイクル", "サイクル中にエラー発生");
    } else {
        TEST_PASS("大量サイクルテスト");
    }
}

int main() {
    printf("=== キュー実装の破壊的テスト ===\n");
    
    test_basic_functionality();
    test_full_capacity();
    test_empty_dequeue();
    test_wraparound_behavior();
    test_alternating_pattern();
    test_stress_overflow();
    test_data_integrity();
    test_boundary_conditions();
    test_reinitialize();
    test_massive_cycle();
    
    printf("\n=== テスト完了 ===\n");
    return 0;
}

全部パス

このqueueはEmptyのときNullを返すとか問題あるものの、一応全部のテストをパスしました。 こんなテスト意味あるのかな。

ZigbeeのスリープとBLEのスリープの省電力化機能を比較する

今日勉強したばかりの人が超テキトーに書いているのでちゃんと調べてね☆

まず、第一にZigbeeとBluetoothは兄弟みたいなものである。というのもどちらもIEEE 802.15という物理レイヤー上に構築された通信規格である。IEEE 802.15.1がBluetoothでIEEE 802.15.4がzigbeeである。どちらにせよ2.4Ghz帯は汚染されているのでロボコン会場で動かなくなったりするだろうが、そんなことは今回はどうでもよい。あとZigbeeはXbeeしか使ったことなかったりする。

Bluetooth

BLEのスレーブレイテンシーについて説明したいが、その前にBluetoothの通信について説明する。

Bluetoothは、セントラルとペリフェラルという二種類のデバイスからスター型ネットワークを構築して通信することが一般的である。

• セントラル：通常PCであったり、スマホといったデバイスが相当し、通信の中心となるデバイス。ZigbeeにおけるCoordinatorに相当すると思われる。
• ペリフェラル：ペリフェラルはヘッドホンやキーボード、スマートロック（スイッチボットはいいぞ）などが相当する。ZigbeeではEnd Deviceが相当する。

Connection Interval とSlave Latency

今回のキーとなる要素としてコネクションインターバルとスレイブレイテンシについて説明する。コネクションインターバルというのはBluetoothの通信に関するパラメータであり、セントラルがペリフェラルに対して、どの程度の間隔で通信を行うかというパラメータである。Bluetoothは通常一度、セントラルとペリフェラル間で通信を確立すると一定間隔で相互通信を行うことで接続関係を維持することになる。この通信間隔がコネクションインターバルに相当する。コネクションインターバルは1.5msから4sまでの広い範囲で変動する。ちなみにnRF52840で1秒以上の通信間隔を設定しようとした場合ファームウェアに拒否される。

次に、スレイブレイテンシーについて説明する。スレイブレイテンシーはペリフェラルがセントラルからの通信を無視できる回数である。Bluetoothにおいて例えばスマート体温計とかであれば、継続に時間がかかるので4秒とか高頻度で通信を行いたいわけではない。なのでSlavelatencyを利用する。例えば1秒の中で1回送信データが発生するシステムの場合、SlaveLatencyを99、コネクションインターバルを10msとした場合、おおよそ、99回分の通信を無視することが可能である。SlaveLatencyにはクイックトランスミッションという機能があり、コネクションインターバルに従って任意のタイミングでペリフェラルからセントラルに送信ができる。これを組み合わせたら通常1秒に1回通信を行いつつ、特殊イベントのみペリフェラルからセントラルに急遽データ転送することができる。

Zigbee

本稿の話題はこれがZigbeeでもできるの？って話である。

まずZigbeeとBluetoothの一番大きな違いはZigbeeの方がセンサネットワークなどを意識した構造になっており、ラウティング（発音がネイティブで悪いな(・ω<)）のための機能を持つことである。また、Bluetoothが基本的にスマートフォンやPCの周辺機器をターゲットとしているのに対してZigbeeはメッシュネットワークを構築するためのテクノロジーが提案されています。

Zigbeeはノードの種類と、ノードの関係性の二種類に注目する必要があります。 なんかこの辺に詳しく書いてある。https://www.digi.com/resources/documentation/Digidocs/90002002/Concepts/c_device_types.htm まずZigbeeはセントラルとペリフェラルのようにロールが属性に一致するわけでなく親と子という関係があります。更にノードの種類にはEnd Device、Router、Coordinatorの三種類のデバイスが存在します。

• Coordinator：Bluetoothにおけるセントラルに相当するデバイスでTCP/IPに対するゲートウェイを担当したりします。Coordinatorの特徴は親を持たないことです。ネットワークとしてはルートノードになるみたいです。

• Router：これは普通のBluetoothには存在しない機能です（いやBluetooth　Meshだろリレーノードに相当する気がするがZigbeeよりかなりめんどくさいのでこの話はしない）。Coordinatorを親としてEnd Deviceを子とするみたいです。

• End Device：Bluetoothにおけるペリフェラルっぽいです。スリープを行ったりBluetoothっぽい機能がいろいろそろってます。今回はこの辺に関してよく知りたかった。Zigbeeの仕様ではスリープモードになれるのはEndDeviceだけらしい。

Cyclic Sleep Mode

Zigbeeの仕様はややこしい、特にZigbeeはIEEE802.15.4上に構築されており、IEEE802.15.4そのものがZigbeeではないらしい。Zigbeeの規格はZigbeeアライアンスというところが決めているらしい。なんかZigbeeの仕様書の日本語訳があったのでここに貼っておく。

Polling

Zigbeeの通信は親が子に向かって送信するデータが無いか質問するらしい。Zigbeeの省電力デバイスは普段は寝ていて送信データがあるときにだけ起動してデータを送信できるらしい。なのでSleepy End Devicesと呼ばれるらしい。この辺はBluetoothのコネクションイベントとかなり似ているかもしれない。しかしSlabeLatencyを考えるとBluetoothではセントラルがペリフェラルに問い合わせをしていたのに対して、Zigbeeではエンドデバイス側から問い合わせをするという点で異なる。

また、Zigbeeでは非同期で通信が可能であるらしく任意のタイミングでデータが遅れるらしい（じゃあPolling Interval）って何？

ポーリングに関していい感じの資料を見つけたのでここに貼っておく ポーリングの役割は以下の二つらしい

1. 親と子の間で生存報告をする
2. SEDが親に対してデータを要求するときに使う。

更にややこしいことにポーリングには2種類あるらしい。 - Long Poll ：Long Poll Intervalはエンドデバイスから親デバイスへのデータリクエストの最大時間を表す。つまり、デバイスが通信を行う必要が無い場合は、このLong Pollの間隔で通信を行うことで接続を維持することになる。Connection Intervalと同じように考えればいいのかな？ - Short Poll :　エンドデバイスがネットワークから送られてくるメッセージに対して応答する場合このShort Pollの間隔で通信することになるらしい、この状態を“Fast Polling mode”と呼ぶ。Bluetoothで言えばコネクションインターバルに相当するって認識でよいのかな？

まとめ

BluetoothとZigbeeの違いについて調べました。

• 調査してみましたが分かりませんでした。いかがでしたか？
• Bluetoothと同様にZigbeeにも省電力化機能がありました。
• Bluetoothがセントラルとペリフェラルから構成されるのに対して、ZigbeeはCoordinator、Router、EndDeviceの三種類のデバイスから構成されて、その中でもスリープ時間が長いものをSleepy End Deviceと呼ぶことが分かりました。
• Bluetoothではセントラルがペリフェラルに対して要求をするのに対して、ZigbeeではEnd Deviceが親に問い合わせをすることが分かりました。
• Bluetoothでは一定間隔の通信を間引いて省電力化するのに対して、ZigbeeではEndDeviceが要求するPollingが通信間隔を決定することが分かりました。

SRAMのお話をするよ

本稿はSRAMに関するお話です。はっきり言ってしまえばSRAMはHDLには関係ありませんね、ですが皆さんSRAMはよく使うと思うので理解していて損はないと思います。LSI焼くときに役に立つと思いますので。 とりあえずここでは一週間遅れてしまったことをお詫びします。

SRAMについての基礎知識

SRAMはStatic Random Access Memory略してSRAMです。基本的にプロセッサ内のキャッシュや、スクラッチパッドメモリ、マイクロコントローラのメモリなどはSRAMで構成されています。SRAMの基本的な特性としては以下のようなものです。

• 😄回路が単純であるためDRAMと比較して読み書きが高速である。
• 😄リフレッシュが不要であり、読み書きを行わない場合、基本的にリーク電流以外が流れないためDRAMより少電力である。
• 😞4つか6つ以上のトランジスタにより構成されるため、DRAMやMRAMより回路面積が大きい
• 😄トランジスタで構成されているためフラッシュメモリやDRAMと異なり、プロセッサと同じプロセスで製造することが出来る（ココ重要）
• 😞DFFなどで構成されるレジスタと異なり、アナログ回路とデジタル回路の中間的存在であり読み出しに周辺回路が必要。（ココ重要）

特に重要な点はCPUと同じプロセスで製造することが出来る点です。このおかげで、LSIを構成する一つのシリコン上にSRAMとCPUやその他デジタル回路を同居されることが可能であり、デジタル回路からの高速で広いビット幅でのアクセスが可能です。FPGAにおけるBRAMみたいなものだと思っておけばよいでしょう。

メモリ全体におけるSRAMの立ち位置を明らかにするために、高密度でおそらく最もよく使われるRAMの一種であるDRAMと、最近注目が集まっているMRAMとも比較を行いました。 表にまとめると次のような感じになります。 最近はMRAMも性能を上げてきていて、枯れたプロセスであればSRAMよりMRAMの面積が小さいため、「プロセッサの内部キャッシュをMRAMで製造しよう」みたいな話も出てきていますが、基本的にシンプルなSRAMがデファクトとなっています。 今後も手軽に製造可能なSRAMが他のメモリに取って代わられることは当分無いでしょう。

メモリの種類	SRAM	DRAM	MRAM
リフレッシュ	不要	必要	不要
速度	◎	△	○
面積	6T	1T	1T
不揮発性	☓	☓	◎
ロジックとの同居	◎	☓	特殊

SRAMのメモリセル

SRAMはデコーダ、プレチャージ回路など様々な回路で構成されていますが、その中で中核を成す最も重要な要素はメモリセルです。 メモリセルはデータを記録する回路であり、ふたつのインバータから構成されるクロスカップルドラッチとアクセス用のトランジスタから構成されます。クロスカップルドラッチは、2つのインバーターがリング状に接続された構造になっています。この場合偶数段のインバーターチェーンであるので安定した状態を保持します。 昔の半導体設計ではPMOSの性能が出なかったためインバータの上段を抵抗で構成することも多かったようですが、現在のプロセスではPMOSもかなり良い性能を達成可能であるのと、先端プロセスにおいては抵抗値を稼ぐことが難しくなっていることや、上段抵抗であると電源電圧を下げにくいなどの難点もあります。よって、現在は基本的にプッシュプルインバーターが使われています。 余談ですが、面積を向上させるための二階建てSRAMとか、アクセストランジスタが複数あるマルチポートSRAMとか奇抜な構造のものもいろいろありますが、ここでは語りきれないので気になったらぜひ論文を漁ってください。

図１.クロスカップルドラッチの構造

SRAMのメモリセルの読み書き操作

SRAMのメモリセルの構造を見ると、基本的な電子回路の知識がある人は「情報が記録できる原理は理解できるけど、こんなものからどうやってデータを書き込んだり、読み出したりするんだ？」と疑問に思うに違いません。このセクションではまず、メモリセルの簡単な全体像について述べて、その後、SRAMの読み書き操作について述べます。

図２に示すようにクロスカップルドラッチに対して読み出し用のポートを付けたものがメモリセルです。クロスカップルドラッチを構成するインバータの出力と入力の間に、アクセストランジスタが接続されており、メモリセル一つあたり６個のトランジスタで構成されることになります。これが6TSRAMと呼ばれる理由です。

メモリセルにはワード線（WL）とビット線（BL）という2種類のポートがあります。 WLはメモリセル自体を選択するためのものです。メモリセルに書き込んだり、メモリセルからデータを読み出すタイミングでこのWLがHighになります。メモリとして動作する場合、基本的にアドレスのデコーダに接続されています。BLはデータそのものが流れる回路です。メモリセルはインバータなのでBLと反転した〜BLの二本が存在し、差動で動作します。単純な構造のSRAMではSRAMではビットラインを介してデータの読み込みと書き込みの両方が行われますが、デュアルポートSRAMなどでは、別に読み出し用のトランジスタが設置される場合もあります。

図２.メモリセル

SRAMのメモリセルの書き込み

SRAMの書き込みは読み出しに比べると非常に簡単な操作です。読み書きを行いたいメモリセルのワード線に電圧を印加した上で、BLに書き込みたいデータの電圧を印加して、クロスカップルドラッチの状態を無理やり書き換えるだけです。図3にデータ書き込み時の電圧の印加の様子を示します。赤く塗られている線は電圧がHigh、青く塗られている線は電圧がLow電圧が印加されています。 この図の場合ですとBLがLow、~BLがHighが印加されていますので、書き込まれているデータは0になりますね。 このような電圧が印加されると、安定しているクロスカップルドラッチの状態が無理やり書き換えられることになります。最初に見たときはなかなかびっくりしましたが、非常に少ないトランジスタで必要な機能を実現できている面白い方法だと思います。

図３.書き込み操作

SRAMのメモリセルの読み出し

SRAMの読み出しは書き込み操作と比較すると幾分複座雑です。というのも、SRAMはデジタル回路とアナログ回路の性質を併せ持つ回路であり、特に読み出し操作に関してはアナログ的な性質が大きく現れるからです。SRAMの読み出し操作は以下のプレチャージ、データ読み出し、ラッチの3ステップで説明します。

1. プレチャージ

SRAMの読み出しはクロスカップルドラッチからのデータの読み出しは、書き込みでも利用されたビットラインから行われます。すべてのワードラインをLowにした状態で、プレチャージ回路からビットラインビットラインをに電圧を印加します。この状態で、プレチャージ回路をHiZ状態、つまり、高抵抗状態に切り替えると、ビットラインをコンデンサとみなしたときに、配線に電荷がチャージされた状態になります。この操作をプレチャージと呼びます。

図3.1 プレチャージ

2. データの読み出し

データ読み出しではメモリセル、つまりクロスカップルドラッチを使って、プレチャージされた放電することで実現されます。読み出し対象のメモリセルのワードラインをHighすると、クロスカップルドラッチとプレチャージされたBLおよび〜BLが接続されます。するとクロスカップルドラッチのうち、Lowが設定されている方にプレチャージされた電荷が吸い込まれることになります。これにより、BLおよび〜BLは反転した状態になります。このビットラインをオペアンプやコンパレータなどの差動読み出し回路に入力すればデータの読み出しが実現できます。

図3.2 データの読み出し

3. データの読み出し

最後に差動読み出し回路の出力をラッチします。これにより読み出したデータを、アナログ世界からデジタル世界に確定することなります。

以上がメモリの読み書きの操作になります。

SRAMのメモリマクロ

SRAMここまでメモリセルに対する読み書き操作に関する話をしてきました。メモリセルはデータを記録することができる回路ですが、読み出しや書き込みには別の回路が必要となります。また、メモリセルだけではアドレッシングができないためアドレスのデコーダ回路なども必要となります。このような、みなさんが普段使うSRAMとして動作するのに必要な回路をひとまとめにしたものをメモリマクロと呼びます。

次の図にメモリセルのアレイと、周辺回路を含めたメモリマクロの図を示します。メモリマクロというのは半導体設計をしたことがある人は知っていると思いますが、いわゆるマクロであり、特定の機能をまとめた回路のブロックです。SRAMは純粋なデジタル回路と異なりアナログ回路であるため配線長やノイズの影響を受けやすくP&Rで配置配線出るわけではないので、アナログ回路としてメモリコンパイラや手配線で設計してあげる必要があります。

メモリマクロの構成要素について説明します。今回の説明では話をわかりやすくするために簡略化していますが、図に示すメモリマクロの構成要素はメモリセル配列、アドレスデコーダ,プレチャージ回路,書き込み回路,読み出し回路です。ここにカラムセレクタが追加されることもありますが、私はカラムセレクタが載ったメモリセルを設計したことがないため説明を省略します。

次にそれぞれの要素について説明してゆきます。

メモリマクロの構造

メモリセル配列

メモリセル配列はメモリセル複数並べたものになります。メモリセル配列内では縦方向にビットラインを、横方向にワードラインを共有した構造となっています。ビットラインを共有するということは、一つのデータのうちMSBからLSBからのどのビットに相当するかという信号を共有していますので同じビットラインに接続されたメモリセルはワード内の同じビットということになります。また、横方向のメモリセル同士はWLを共有しています。つまり同じ行に属するメモリせるは同じワードを構成するビットであるということになります。今回、図として示している画像はアドレスが2bit、ワードも2bitですが、例えば16bitアドレスの8bitワードのメモリマクロであれば、メモリセル配列は65536の行を持ち、横方向には8個のメモリセルが並び、8本のBLおよび~BLを持つ事になります。ただし、このような配線を愚直に行うと配線長が長すぎて抵抗値が増大して読み出しが遅くなので列を分割してカラムセレクタでセレクトするなど工夫が必要です。

アドレスデコーダ

アドレスデコーダは名前の通り、データのアドレスをWLに変換するための回路です。基本的にはNOT回路とAND回路で構成され、行に対応するアドレスが入力された場合に、そのアドレスに相当するWLが1になる回路が、それぞれの行ごとに構成されています。ただ、この構成ですと、回路が大規模化したときに、配線長が長くなりすぎたり、回路に接続されたAND回路の数が増えすぎて、ファンアウトが肥大化ししてしまいます。これを避けるために、実際のメモリマクロではデコーダを、WLに直結されたAND回路であるデコーダと、その前段としてよりアドレス入力に近い位置に設置されたプリデコーダに分けて実装します。これにより最集段のファンイン（配線にぶる下がるロジック入力の数）を制限したり、デコーダの回路規模を抑制してデコード速度の低下を抑えることに繋がります。

プリチャージ回路

BLおよび〜BLをプリチャージするための回路となります。大量のWLのアクセストランジスタがぶら下がっているBLおよび〜BLを駆動するための回路であるので、それなりのパワーが必要となります。この回路の出力はBLと〜BLを電源電圧に釣り上げるためのオン状態と、チャージ状態を維持すためのHiZ状態の二種類となります。

　読み出し回路

センスアンプはBLの状態から、データを読み出すための回路です。メモリセルの説明で述べましたが、BLおよび〜BLは反転した電圧となるため、差動で読み出すことになります。この読み出した信号をラッチで確定することにより読み出しデータが確定します。 余談ですが、このセンスアンプ部分は差動ではコストが高いので、マルチポートSRAMなどでは基準電圧を使ったシングルエンド読み出し回路が実装されることもあります。このような場合読み出し速度は当然差動式に劣ることになります。

　書き込み回路

メモリセルに対してデータを書き込むための回路です。メモリセルのBLは長くなりがちなので、BLを上げ下げするのに十分なパワーを得られるようにファンアウトしてあげる必要があります。

　まとめ

メモリセルの簡単な説明を行いました。本当はOpenMPWのPDKで設計からシミュレーションまで行って記事にまとめたかったのですが、間に合いませんでした。 アドベントカレンダーの運営者様、および他の参加者様にはここで重ねて遅れたことをお詫びします。

極小LiDAR（マルチゾーンToFセンサ） VL53L5CX で遊ぶ

www.st.com

VL53LCXの導入方法です。研究で使うために調べた時のメモです。特に説明するまでもない話なんですが、Lidarとか使いたいロボット系の人は機械出身でArduinoとか苦手かもしれないのでメモとして残しておきます。

なんのデバイス？

STMが面白いTOFセンサを販売しています。その名もVL53LCXです。簡単に言ってしまえば凄く安価で、8x8の解像度を持つ、極小のLiDARです。

解像度はファミコンのスプライト並みに低いですが、ハンドジェスチャーの認識などをターゲットとしているらしく、時系列処理することで、1フレームから得られる情報よりも複雑な情報が取り出せるはずです。使い方によってはCHLAC特徴量なんかとも相性が良いのではないでしょうか？まあこの規模のテンソルならraspicoなどM0マイコンでも深層学習で処理できてしまいます。（なんだかんだディープでポンッ！でも精度が出やすい畳み込み演算は強い）

スペック

基本的なスペックは以下のような感じです。さらに詳細な内容はデータシート読んでください。

• 視野角：65度
• 解像度：4x4、または8x8
• 最大計測距離：400cm
• フレームレート：
  4x4：60Hz
  8x8：15Hz
• インタフェース：I2C
• 電源：3.3Vの単電源、もしくは3.3Vのアナログ電源と1.8VのIO電源の組み合わせ

デバイス

Qwwickなどからも販売されていますが、私が使っているのはSTM公式のBreakoutBoardです。私はNucleoに接続して使っています。ブレッドボードで接続スレば良いのですが、ToFセンサの性質上、向きを変えるたびにI2Cにノイズが乗ったり、いろいろ面倒くさくなってユニバーサル基板にはんだ付けしています。

私が使っているNucleoはNUCLEO-L476RGです

NucleoとVL53L5CX-SATELの接続のピン対応です

• VL53L5CX-SATEL	stm32	機能	機能
  pin1	GND	GND	電源GND
  pin2	3V3	IOVDD	IO電源
  pin3	5V	AVDD	アナログ電源
  pin4	A5	PWREN
  pin5	A3	LPn
  pin6	D15	SCL	I2C SCL
  pin7	D14	SDA	I2C SDA
  pin8	A1	I2C_RST	I2C　リセット
  pin9	A2	INT	計測完了割り込み

サンプルプログラムを試す

STMが公開しているサンプルプログラムを試してみます。サンプルコードはSTM32Duinoで提供されているため、まだArduinoを使ったことがない人は適当にArduinoIDEをインストールして下さい。僕の環境はversion:2.03のを使っています。

STM32Duinoの環境構築

github.com

stm32duinoの環境をセットアップします。とりあえず上のリポジトリを見ればできると思います。

赤マーカー引いているところにjsonファイル「https://github.com/stm32duino/BoardManagerFiles/raw/main/package_stmicroelectronics_index.json」と書き込んでokを押せば追加できます。

そしてツール->ボードマネージャでstm32と打つと以下のような候補が出るのでインストールします。

VL53L5CXのサンプルスケッチの追加

VL53L5CXをstm32duino上で動かすことができるサンプルスケッチがSTMから公開されているので、ArduinoIDEに追加します。

github.com

リポジトリからzipでダウンロードします

ダウンロードしたzipファイルをArduinoIDEの「スケッチ→ライブラリをインクルード→.ZIP形式のライブラリをインストール」から読み込みます。

サンプルプログラムを動かしてみる

私の環境はNUCLEO-L476RGなのでArduinoIDEのToolから以下のように設定しています。

早速サンプルのスケッチを動かしてみましょう

上の図のようにサンプルプログラムを開いて書き込みます。

そしてシリアルモニタを開くと以下のようなデータが流れてくるはずです。サンプルコードだと4x4モードになっているようです。

ゾーンとそのゾーンの領域ごとの距離が表示されています。マックス4mのはずなんですが、机において実験していて、天井があるので1800くらいがマックスになってますね。データシートからの抜粋ですが、それぞれの領域が相当する箇所は以下のようになっています。

可視化プログラムを作る

stm32のプログラムを改造し、Python上で簡易的に可視化するプログラムを作りましたのでシェアします。

PC側

Pythonの可視化プログラムはＵＡＲＴで読んでOpenCVで表示させているだけです。表示はESCキーで終了します。COMポートは自分の環境に合わせてください。

#!/usr/bin/env python3

import sys

import numpy as np

import serial

import cv2

 

with serial.Serial('てめぇのCOMポート', 115200, timeout=0.1) as ser:

    while(1):

        print("fetch")

        b_data = ser.read(65*2)  

        print(len(b_data))

        np_data = np.frombuffer(b_data, dtype = np.uint16)

        np_buf = np.concatenate([np_buf, np_data])

        print(np_buf.shape)

        for index, item in enumerate(np_buf):

            if(item == 0xFFFF):

                slice_data = (np_buf[index+1:index+64+1]/2000*256).astype(np.uint8)

                np_buf = np_buf[index+64+1:]

       

                slice_data = slice_data.reshape*1

                resized_image = slice_data.repeat(100,axis=0).repeat(100,axis=1)

                dst = cv2.applyColorMap(resized_image, cv2.COLORMAP_JET)

                cv2.imshow('camera' ,dst)

       

                out_image = cv2.resize(slice_data, (800,800),cv2.INTER_CUBIC )

                dst = cv2.applyColorMap(out_image, cv2.COLORMAP_JET)

                cv2.imshow('by cubic' ,dst)

               

        #繰り返し分から抜けるためのif文

        key =cv2.waitKey(10)

        if key == 27:

            break

stm32側

STM32側のプログラムです。8x8での出力が最高速の１５FPSで動くはずなんですが、なぜかそれ以上出るのでプログラムが間違っているのもしれません。高速化するために出力をバイナリにしているので、シリアルモニタで見ても謎の文字列しか出てこないです。

#include <platform.h>

#include <platform_config.h>

#include <platform_config_default.h>

#include <vl53l5cx_api.h>

#include <vl53l5cx_buffers.h>

#include <vl53l5cx_class.h>

#include <vl53l5cx_plugin_detection_thresholds.h>

#include <vl53l5cx_plugin_motion_indicator.h>

#include <vl53l5cx_plugin_xtalk.h>

/**

 ******************************************************************************

 * @file    VL53L5CX_Sat_HelloWorld.ino

 * @author  STMicroelectronics

 * @version V1.0.0

 * @date    11 November 2021

 * @brief   Arduino test application for the STMicrolectronics VL53L5CX

 *          proximity sensor satellite based on FlightSense.

 *          This application makes use of C++ classes obtained from the C

 *          components' drivers.

 ******************************************************************************

 * @attention

 *

 * <h2><center>&copy; COPYRIGHT(c) 2021 STMicroelectronics</center></h2>

 *

 * Redistribution and use in source and binary forms, with or without modification,

 * are permitted provided that the following conditions are met:

 *   1. Redistributions of source code must retain the above copyright notice,

 *      this list of conditions and the following disclaimer.

 *   2. Redistributions in binary form must reproduce the above copyright notice,

 *      this list of conditions and the following disclaimer in the documentation

 *      and/or other materials provided with the distribution.

 *   3. Neither the name of STMicroelectronics nor the names of its contributors

 *      may be used to endorse or promote products derived from this software

 *      without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR

 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER

 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,

 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 ******************************************************************************

 */

/*

 * To use these examples you need to connect the VL53L5CX satellite sensor directly to the Nucleo board with wires as explained below:

 * pin 1 (GND) of the VL53L5CX satellite connected to GND of the Nucleo board

 * pin 2 (IOVDD) of the VL53L5CX satellite connected to 3V3 pin of the Nucleo board

 * pin 3 (AVDD) of the VL53L5CX satellite connected to 5V pin of the Nucleo board

  * pin 4 (PWREN) of the VL53L5CX satellite connected to pin A5-A0 of the Nucleo board

  * pin 5 (LPn) of the VL53L5CX satellite connected to pin A3 of the Nucleo board

 * pin 6 (SCL) of the VL53L5CX satellite connected to pin D15 (SCL) of the Nucleo board

 * pin 7 (SDA) of the VL53L5CX satellite connected to pin D14 (SDA) of the Nucleo board

  * pin 8 (I2C_RST) of the VL53L5CX satellite connected to pin A1 of the Nucleo board

  * pin 9 (INT) of the VL53L5CX satellite connected to pin A2 of the Nucleo board

 */

/* Includes ------------------------------------------------------------------*/

#include <Arduino.h>

#include <Wire.h>

#include <vl53l5cx_class.h>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include <stdint.h>

#include <assert.h>

#include <stdlib.h>

#ifdef ARDUINO_SAM_DUE

  #define DEV_I2C Wire1

#else

  #define DEV_I2C Wire

#endif

#define SerialPort Serial

#ifndef LED_BUILTIN

  #define LED_BUILTIN 13

#endif

#define LedPin LED_BUILTIN

#define LPN_PIN A3

#define I2C_RST_PIN A1

#define PWREN_PIN A5

// Components.

VL53L5CX sensor_vl53l5cx_sat(&DEV_I2C, LPN_PIN, I2C_RST_PIN);

/* Setup ---------------------------------------------------------------------*/

void setup()

{

  // Led.

  pinMode(LedPin, OUTPUT);

  // Enable PWREN pin if present

  if (PWREN_PIN >= 0) {

    pinMode(PWREN_PIN, OUTPUT);

    digitalWrite(PWREN_PIN, HIGH);

    delay(10);

  }

  // Initialize serial for output.

  SerialPort.begin(115200);

  SerialPort.println("Initialize... Please wait, it may take few seconds...");

  // Initialize I2C bus.

  DEV_I2C.begin();

  DEV_I2C.setClock(1000000);

 

  // Configure VL53L5CX satellite component.

  sensor_vl53l5cx_sat.begin();

  sensor_vl53l5cx_sat.init_sensor();

  // Start Measurements

  sensor_vl53l5cx_sat.vl53l5cx_set_resolution(VL53L5CX_RESOLUTION_8X8);

  sensor_vl53l5cx_sat.vl53l5cx_set_ranging_frequency_hz(15);

  sensor_vl53l5cx_sat.vl53l5cx_start_ranging();

}

void loop()

{

  static uint8_t loop_count = 0;

  VL53L5CX_ResultsData Results;

  uint8_t NewDataReady = 0;

  char report[64*2];

  uint8_t status;

  uint8_t banpei[] = {0xFF,0xFF};

 

  do {

    status = sensor_vl53l5cx_sat.vl53l5cx_check_data_ready(&NewDataReady);

  } while (!NewDataReady);

  //Led on

  digitalWrite(LedPin, HIGH);

  if *2 {

      status = sensor_vl53l5cx_sat.vl53l5cx_get_ranging_data(&Results);

     

      for(int i =0; i < 64; i++){

        int index = i*2;

        report[index] = Results.distance_mm[i] & 0x00FF;  

        report[index+1] = (Results.distance_mm[i] >> 8)& 0x00FF;  

      }

      SerialPort.write(banpei, 2);//データ本体

      SerialPort.write(report, 64*2);//データ本体

  }

  digitalWrite(LedPin, LOW);

}

こんな感じで画面が出るはずです。ちなみに移っているのは私の手です。左側は出力そのまま、右側はバイキュービック補完して表示しています。

今後

まだあまり調べられていないのですが、VL53L7CXという新型がでていて、そっちは視野角が90度もあるらしいので試してみたいです。

*1:8,8

*2:!status) && (NewDataReady != 0

研究室内にQNAPのNASでgitlab-ceを構築する

今回は研究室内にgitlab-ce（ローカルで動作するコミュニティエディション）の環境を構築した際の作業メモです。今回は技術共有というよりは私的なメモと後輩への作業指示書になります。

ローカルにgitlab環境を構築する。そんなことしなくても「公開されているgitlab.comのプライベートリポジトリを使えばいいじゃないか」思われるかもしれませんが、いろいろメリットがあります。

今回ローカルにgitlabサーバーを構築した理由は以下の二つです。

• gitlab.comのグループが有料化されて5人までしか使えないがローカルなら無制限
• 先生が研究データを外部のサーバーに置くのが好きじゃないっぽい

そんなわけで研究室内にgitlabのサーバーを構築することになりました。

担当はgitlab.comをそもそも導入した私になりました。

サーバー環境

サーバーとして以下のNASを利用しました。別にわざわざNASを選ぶ必要もありませんが、NASをgitlabサーバーにすると以下のようなメリットがあります。

• 長期動作の信頼性が高く長期間安定して動かせる
• QNAPはContainerStationでDockerコンテナが簡単に実行できる。
• RAIDが簡単に組める

NASとしてはTS-464を選定しました。理由はメモリが8GBあって大きかったからとCPUがそこそこ強い（ギガスクールで使ってる子供用パソコンくらい）からです。gitlab実行時は6GBくらい食っているのでやはりメモリは大きい方が良いと思います。

www.qnap.com

Gmailアカウントの取得

gitlabはコミットの通知やパスワードの再発行手続き使うメールアドレスを設定することができます。本学は最近メールサーバーが移行しまくっていて、メール設定が変わりまくっていて面倒くさいのでgmailを通知用のメールアドレスにしました。あとgmailを使うと送信メールの確認がwebからできるのでテストが楽です。

まず、普通にgoogleアカウントを作成し、メールアドレスを取得してください、それから私はセキュリティを高めたかったので、研究室の電話番号で二段階認証を設定したのち、アプリパスワードを設定しています。

アプリパスワードに関しては情報系の人間なら以下のサイトを見ればできると思います。

support.google.com

dockerコンテナの導入

NASはRAIDを適当に組んでセットアップしたのちdockerコンテナを導入します。NASの名前はそのまま、ｍDNSのurlになるのでちゃんと考えてNASに名前を付けた方が良いと思われます。まあ、ｍDNSのlocalドメインとか不健全なものは使わない人や、ルーターのスタティックDNSレコードで対応する人とかは関係ないので忘れてください.

1. QNAPのアドレスに管理者としてログインしてください
2. まず下のApp CenterからContainer Statioonをインストールします。
3. インストールが終わるとホーム画面にContainer Stationのロゴが表れるのでクリックします。すると下の図のように左側のメニューに作成という項目が表れるのでDocker-hubより「gitlab/gitlab-ce」を選択しました。これ以外にもContainer Stationが提供しているgitlabのイメージもあったりしますが、私は以前より使用経験があったこのイメージを選択しました。現在問題なく動作しています。インストールを押すとコンテナが立ち上がります。

gitlabの初期設定

1. コンテナを起動した状態でピンクマーカーを引いた項目をクリックするとコンソールが立ち上がります。この時なんのプログラムで起動するか聞かれますが、私は「/bin/bash」を指定することが多いです。
2. パスワードの確認gitlabは管理用アカウントのデフォルトのパスワードが自動生成されるのでそれを確認します。以下のコマンドで見ることができますが、この辺はバージョンが変わると、変わるらしいので、以下のリンクから最新の情報を調べてください。

   www.gitlab.jp

   
   いかがパスワードの確認コマンドです。コピペするなりメモするなりしてください。

   $cat /etc/gitlab/initial_root_password

3. ポートの確認
   gitlabが動作しているコンテナのポート番号を確認します。
   
   赤く塗りつぶされているところにコンテナのアドレスとポート番号が表示されていると思います。ポート番号を変更したければ
   設定→詳細設定→ネットワーク
   でポートフォワーディングの設定を変更することが可能です。
   ブラウザからポート番号とipアドレスより以下のようにgitlabのページにアクセスすることが出来るはずです。
   ［gitlabが動作しているnasのIPアドレス］:［ポート番号］
4. パスワードの変更
   必要があればパスワードを変更します。確認したurlにアクセスするとログイン画面が現れるので
   ・ユーザー名：root
   ・パスワード：2.で調べたパスワード
   でログインします。
   Preference→Password
   で普通に変更できます
5. メールアドレスの登録
   最初に登録したgmailのアドレスをgitlabで利用します。1で登場したコンソールに戻ってください。また開いてもいいです。
   viなりnanoなりでgitlabの設定ファイルを開きます
   

   $nano /etc/gitlab/gitlab.rb

   そして以下のように設定を書き換えます

   gitlab_rails['smtp_enable'] = true

   gitlab_rails['smtp_address'] = "smtp.gmail.com"

   gitlab_rails['smtp_port'] = 465

   gitlab_rails['smtp_user_name'] = "gmailアドレス"

   gitlab_rails['smtp_password'] = “googleのアプリパスワード”

   gitlab_rails['smtp_domain'] = “smtp.gmail.com”

   gitlab_rails['smtp_authentication'] = "plain"

   gitlab_rails['smtp_enable_starttls_auto'] = true

   gitlab_rails['smtp_tls'] = true

   ###! **Can be: 'none', 'peer', 'client_once', 'fail_if_no_peer_cert’**

   ###! Docs: http://api.rubyonrails.org/classes/ActionMailer/Base.html

   gitlab_rails['smtp_openssl_verify_mode'] = 'peer’
   
6. URLの変更
   gitlab.rbを開いたついでにURLの変更もしておきましょう。詳細は省きますがQNAPのNASはｍDNSでアクセスを簡易化でできるように、avahiが動いていて「ルーター名.local」でアクセスできるようになっています。この名前解決はどのポートに対しても可能なので、dockerイメージに対してhttpに相当する80番ポートをフォワーディングすれば、そのままgitlabのurlとして利用することが可能になります（研究室内のイントラからのアクセスのみで有効で、外部からVPNで接続した際などには使えません）。
   gitlabのメールシステムメールアドレスのベリファイなどの際に、urlのリンクを送信します。その際に、通知文章用のアドレスが必要となります。gitlab.rbにアクセス時のメールアドレスを書き込んでおきましょう。これでメール上のリンクをクリックして操作可能になります。
   
   external_url 'http://nas-gitlab.local'
7. メールアドレスの動作確認
   設定したメールアドレスが本当に利用可能か検証します。書き換えたgitlab.rbの内容をgitlabに適応します。gitlabのdockerイメージのコンソール上で以下のコマンドを実行してファイルの内容を反映させましょう
   
   gitlab-ctl reconfigure
   次にgitlabのrailsのコンソールに入ります。以下のコマンドを実行してください。
   
   gitlab-rails console
   コンソールが開いたら以下のコマンドを実行して、メールを送信します。
   
   Notify.test_email( '[テスト用のaddress]', 'Message Subject', 'Message Body').deliver_now
   これで正しくメールが送信出来たらgitlabの基本的な設定は終わりです。あとはラボメンにアカウントを作ってもらって開発を進めましょう。

その他

gitlabは導入後デフォルトのままだと、アカウントを作成しても、管理者が承認したユーザー以外、使用できない設定になっています。研究室の方針によると思いますが、面倒くさいので、うちの研究室だと解除して自由にアカウントを作れるようにしてしまっています。

また、管理者の設定項目は今言ったこと以外にもたくさん借るので、適宜新しい記事にまとめてゆこうと思います。

追記2023/2/27

デフォルトをpublicリポジトリに変更する

ローカル環境にサーバーを立てているのだから、リポジトリをプライベートにするのはあんまり意味がないと思うのですが、gitlabのデフォルト設定ではリポジトリをプライベートにしてしまうので管理者権限で変更します。

ハンバーガーメニュー（三みたいなやつ）からadmin設定を開いてそこからGeneralでprivateで検索すると以下のようなメニューが表れます。取り合えず全部publicに変更しました。基本的にラボ内では風通しがいい方が良いと思いますので。

gitlabの引っ越し方法

以前より外部で管理していたリポジトリをローカルに移行する方法を書きます。以下の三つのコマンドで簡単にお引越しができます。pushに-fオプションをつけてますが、リポジトリを作るときにプロテクトとか書けてなければ、別になくてもできると思います。

git clone --mirror [古いリポジトリ]

cd [古いリポジトリ名].git

git push --mirror -f [新しいリポジトリ]

感想

毎度のことですが疲れました。特に今回はあんまり研究要素がないというかどちらかといえば単純作業だったので、あんまり達成感もなく、ただただ面倒くさかったです。まあ先生にはいつも迷惑かけまくってるので、このくらいの仕事は喜んでやります。

前回gitlabサーバーを構築した際はHyper-Vを利用して構築していましたが、今回はContainer Stationを利用したのでdockerがバックエンドになりました。サーバー関連だとやはりDockerの方が管理しやすそうなので今後に期待したいところです。

gitlabサーバーは過去に一度立ち上げて、誰も使ってくれないかった経験があるので、正直あんまり乗り気ではなかったのですが、一緒にgitlabを使ってきた後輩に頼んでgitlabのチュートリアルの資料を作ってもらうつもりなので、来年は全員がgitでソースを管理するようにしたいです。もうNAS上に日付付きのフォルダが散乱する惨状は懲りたので、gitで正しくバージョン管理できるようにしたいですね。

そもそも社会に出るのにgit使えないってどうなんですかね？

「atcoderでD問題以上（今ならEか）)が解けるようになるより、gitが使えるようになるほうがよっぽど大事」とかどっかのエンジニアが言ってました。

今後の展望

研究室ではdiscordをりようしているので、プルリクなどをdiscrodに飛ばす機能も使ってみたいです。

あとまあ、みずほの事件あたりでgithubを禁止しているクソみたいな開発体制の会社に行ってもローカルにgitlabを構築するスキルがついたので改善できるかななんて思いました。M&Msセキュリティっていうんでしたっけ、外皮が頑丈で、イントラの内部に侵入するとやりたい放題できるタイプのセキュリティシステム。

Growing Neural GasをPythonで実装してみる

動機

Twitter東海林ファジィロボット研究所という方がGNG（GrowingNeuralGas）を使った三次元物体の認識を行ってる動画をアップしているので面白そうなので私も挑戦してみることにしました。Gazeboか何かでシミュレーションを行っており、見ていてすごい面白いのですが、このアルゴリズム、調べてもgoogleだとあんまり日本語情報が出てこないんですね。

webページでは結構きれいにまとまっているなと思ったのは以下のwebサイトです。 www.thothchildren.com

論文はそれなりの数が見つかります。首都大と岡山大で盛んに研究されているらしく、これとかすごいいいですね。自己増殖型ニューラルネットワークと教師無し分類学習。 これも図が載っていてとても分かりやすいです。Growing Neural Gasの基礎と点群処理

今回の記事ではこの資料を元にGNGのアルゴリズムをPythonで実装してみます。

注意 素人の実装なので実装が正しい保証はありません。日本語のPython実装がおそらくweb上にこれしかないので、実装が間違っていた場合それがデファクトになってしまうのは避けたいです。

Growing Neural Gasについて

GrowingNeuralGasとは教師無し学習を行うアルゴリズムの一つでニューラルネットワークの一種です。ニューラルネットワークといってもDeepLearningのように固定の個数のパラメータに対して、チューニングを行うわけでは無く、ニューラルネットワーク自体が変形します。ベクトル群に対して位相構造をとらえるのが得意であり、点群情報から対象物形状を推測したり、データに対して位相情報を抽出したりできます。。

人間が環境を認識する手法と比較するとかけ離れているように感じました。どちらかというと粘菌っぽいですね。

アルゴリズム

自己増殖型ニューラルネットワークと教師無し分類学習を読みながら実装を行ったのですが、そのアルゴリズムについて私の理解を図解していきます。合っているかどうかはあんまり自信がありませんが、後続のプログラムとステップが一対一で対応しています。

あと数式ははてなブログの数式機能で使えない記号とかいっぱいあってガバガバなので雰囲気で読んで下さい、色々記号が出てきますが、基本的にそれぞれの文字の意味は以下のような感じです。 それと、論文書くときほど真面目に書いてないので誤植は沢山あると思います。

とはなんか論文読んでも定数としか書いてなかったので何の働きをしているのかよく理解できてないです。

Step 0

初期化として、二つのノードの参照ベクトルとをランダムに生成し、結合関係、エッジを接続します。緑色の点はニューロンだと思ってい下さい

Step 1

入力データの中からデータの分布[tex : p(v)]にしたがってランダムに取り出します。今回はデータの分布がよくわからないので、適当に一様分布仮定して取り出してます。

Step 2

入力データにたいして重みの中から最も近い勝者ノードと二番目に近い第二勝者ノードを選択します。

Step 3

ノードに関して入力データとの事情誤差を計算し、積算誤差に加算する

Step 4

ノードおよびと結合関係のあるノードの位置を更新するこの時、s1の学習率を、それ以外の学習率をとする。ただし(である)。勝者ノードや周辺のノードを取り出したデータに対して距離的に近づけている。

Step 5

との間にエッジが存在すればエッジの年齢を0にする。そうでなければとの間にエッジを生成する。

Step 6

と接続関係のあるすべてのエッジの年齢を１増加させる。

Step 7

エッジの年齢が事前に設定した閾値を超える場合、そのエッジを切断する。さらにエッジが接続されたことによって発生する。孤立ノードも削除する。

Step 8

GNGへのデータの入力回数が回ごとに次の操作を行う

(i)

積算誤差が最大のノードqを選択する。

(ii)

ノードと結合関係のあるエッジのなかで最も長いエッジを選択し、このノードに結合するノードをとすると、このエッジを二分するようにノードを挿入する

(iii)

ノード間のエッジを削除し(),ノードおよび間にエッジを追加する。

(iv)

ノードの積算誤差を次の様に更新する

(v)

との誤差の平均をrの誤差とする

Step 9

すべてのノードの積算誤差を減らす。

Step 10

終了条件が満たされない場合Step1に戻る。この辺はまだあんまりちゃんと勉強できてない。エラーが一定以下になったらとか聞いたけど。積算誤差のことでいいのかな？

実装

自己増殖型ニューラルネットワークと教師無し分類学習の資料を基に1ステップずつ実装してゆきます。

今回はNumpyで実装していきます。PythonはPythonでプログラミングらしいことを始めたら負けなので、なるべく演算はNumpyにやらせましょう。

neuronsはニューロンの配列、neurons_existはその番地のニューロンが存在するかどうかのマスクです。接続は100マス計算の様に接続関係にある要素の番号の行と列が交わる点がTrueになるようにしています。なので一つの接続があると二点がTrueになります。

import matplotlib.pyplot as plt
import networkx as nx
from numpy.random.mtrand import randint
lr_s1 = 0.2 #s1の学習率
lr_s2 = 0.1 #s2の学習率
beta  = 0.2 #ナニコレ？
alpha = 0.2

MAX_N = 250 #ニューロン数は最値
th_age = 13 #エッジの寿命
lambda_value = 11


#ニューロンは二次元配列で使っていないところに突っ込む
neurons = np.ones([MAX_N,2])
neurons_error = np.zeros((MAX_N))
#ニューロンが生きているかのマスク
neurons_exist = np.zeros((MAX_N)).astype(np.bool)

#ニューロン間の接続は行列で表現する.接続はbool値で表現する
connectivity = np.zeros((MAX_N,MAX_N)).astype(np.bool)
#エッジの年齢も同様に行列で表現する
edge_age = np.ones((MAX_N,MAX_N))

#step0 初期化として、二つのノードの参照ベクトルw1とw2をランダムに生成し、結合関係C_1,2、エッジの年齢a_1,2を0にする
neurons[0] = [randint(0,500),randint(0,500)]
neurons[1] = [randint(0,500),randint(0,500)]
#存在することにする
neurons_exist[0] = True
neurons_exist[1] = True
#s1とs2を接続する
connectivity[0][1] = True
connectivity[1][0] = True

#対象データvの全体の長さを取得
data_len = cluster_pos.shape[0]
index_pad = np.array(range(MAX_N))

for i in range(1,1000):
  #Step1 入力データvをp(v)を使ってランダムに取得する
  v = cluster_pos[randint(0,data_len)]
  #Step2 入力データvに対する勝者ノードs1と第二勝者ノードs2を取り出す
  #生きているニューロンだけを取り出す
  active_neurons = neurons[neurons_exist]
  active_neurons_error = neurons_error[neurons_exist == True]
  active_neurons_index = index_pad[neurons_exist]
  distance = np.argsort(pow(abs(active_neurons - v),2).sum(axis=1))
  s1_index = active_neurons_index[distance[0]]
  s2_index = active_neurons_index[distance[1]]

  s1 = neurons[s1_index]
  #Step3 勝者ノードs1について入力データvとの事情誤差を積算誤差E_sに」加算する
  neurons_error[s1_index] += pow(s1-v,2).sum()
  
  #Step4 ノードs1およびノードs2と結合関係あるノードと参照ベクトルを更新する。
  neurons[s1_index] += lr_s1*(v - neurons[s1_index]) 
  for item in neurons[connectivity[s1_index]|connectivity[s2_index]]: 
    neurons[s2_index] += lr_s2*(v - neurons[s2_index]) 

  #Step5 エッジの年齢を0にリセットする。またノードs1とs2の間にエッジが存在しなければ新たにエッジを作成する
  if(connectivity[s1_index][s2_index] == False):
    connectivity[s1_index][s2_index] = True
    connectivity[s2_index][s1_index] = True
  edge_age[s1_index][s2_index] = 0
  edge_age[s2_index][s1_index] = 0

  #Step6 ノードs1と結合関係のあるすべてのエッジの年齢をインクリメントする。
  edge_age[s1_index][connectivity[s1_index]] += 1
  edge_age[:,s1_index][connectivity[:,s1_index]] += 1

  #Step7 事前に設定したしきい値a_maxを超える年齢のエッジを削除する。その結果ほかのノード結合関係を持たないノードが表れた場合は該当ノードを削除する
  connectivity[edge_age > th_age] = False

  #ニューロンの削除
  neurons_exist[connectivity.sum(axis=0) == 0] = False


  #Step8 GNGへのデータ入力がlambda回ごとに次の操作をおこなう
  if(i % lambda_value == 0):
    #(i)積算誤差が最大のノードqを選択する。
    q_index = neurons_error.argmax()
    q = neurons[q_index]
    #(ii)ノードqと結合関係のあるエッジのなかで最も長いエッジを選択し、このノードに結合するノードをfとすると、このエッジを二分するようにノードｒを挿入する
    
    connected_neurons = neurons[connectivity[q_index]]
    connected_neurons_index = index_pad[connectivity[q_index]]
    
    f_index = connected_neurons_index[np.argsort(pow(abs(connected_neurons - q),2).sum(axis=1))[-1]]
    

    f = neurons[f_index]

    #ニューロン rを作成するために開いている最も小さなニューロンの番地を探す
    r_index = np.where(neurons_exist == False)[0][0]

    #ニューロンrを生成する
    neurons_exist[r_index] = True
    neurons[r_index] = (q+f)/2
    #(iii)つぎに、ノードq,f間のエッジを削除し(C_qf = 0),ノードqrおよびrf間にエッジを追加する。(C_qr = 1,C_rf = 1)
    #qf間の接続を切断する

    connectivity[q_index][f_index] = False
    connectivity[f_index][q_index] = False
    edge_age[q_index][f_index] = 0
    edge_age[f_index][q_index] = 0
    #rf間を接続する
    connectivity[r_index][f_index] = True
    connectivity[f_index][r_index] = True
    edge_age[r_index][f_index] = 0
    edge_age[f_index][r_index] = 0
    #qf間を接続する
    connectivity[r_index][q_index] = True
    connectivity[q_index][r_index] = True
    edge_age[r_index][q_index] = 0
    edge_age[q_index][r_index] = 0
    
    #(iv)ノード積算誤差を更新する
    neurons_error[q_index] -= alpha*neurons_error[q_index] 
    neurons_error[f_index] -= alpha*neurons_error[f_index] 

    #(v)qとfの誤差の平均をrの平均とする
    neurons_error[r_index] = neurons_error[q_index]+neurons_error[f_index]*0.5
   

  #Step 9すべてのノードの積算誤差を減らす。
  neurons_error[neurons_exist] -= beta * neurons_error[neurons_exist]
  
  #Step 10 終了条件が満たされない場合Step1に戻る
  if(i%1 == 0):
    #描画処理
    fig = plt.figure()
    ax = plt.axes()


    plt.scatter(cluster_pos[:,0], cluster_pos[:,1])
    fig.set_size_inches(10, 10)


    #edgeの描画
    for row in range(0,250):
      for col in range(row+1,250):
        if(connectivity[row][col]):
          neuron_A_pos = neurons[row]
          neuron_B_pos = neurons[col]
          plt.plot([neuron_A_pos[0],neuron_B_pos[0]],[neuron_A_pos[1],neuron_B_pos[1]],color="lime")
    #ニューロンの描画
    for neuron_pos in neurons[neurons_exist]:
      c = patches.Circle(xy=(neuron_pos[0],neuron_pos[1]), radius=5.0, color='lime', fill=True)
    
      ax.add_patch(c)
    c = patches.Circle(xy=(v[0],v[1]), radius=5.0, ec='r',color='r', fill=True)
    ax.add_patch(c)

    plt.savefig(f"img_{str(i).zfill(4)}.png")

    plt.show()

実行

以上のプログラムを実行して動作を確認するサンプルをGooglecolabでシェアします。学習対象のデータとしては、2Dと3Dの両方を対象としました。はてなブログは動画が貼れないのでTwitterから貼れるのは便利ですね。

2D版プログラム

２Dは私が適当に作ったドーナツ型のランダムのデータです。

colab.research.google.com

機械学習の待ち時間に手癖で作ったGrowing Neural Gasです（まだバグがあるかも）
まあ、ある程度動いてるかな？
アルゴリズム的に順序依存があって並列化が難しそうなのが考えものですね。マルチスレッド化する論文は出てるみたいなので要調査です。 pic.twitter.com/qpCbgy644e

— とりてん＠論文数0.5 (@NoOne_1024) February 9, 2023

3D版プログラム

３Dはスタンフォードバニーです。

colab.research.google.com

Growing Neural Gasが3次元データでも動くようになりました。
うさぎさんはスタンフォードバニー

東海林さんのように綺麗に収束させるのは難しい。GNGTにしたり、戸田先生みたいにエッジ認識とかやればいいのかな？
あと終了条件ってどうやって決めれば良いんだろう？ pic.twitter.com/mAW9eB3ydm

— とりてん＠論文数0.5 (@NoOne_1024) February 10, 2023

実装した感想

適当にまとめるつもりでしたが、高専の実験レポートくらいのボリュームになってしまいました。 深層学習と違い学習過程が目視できるので見ていて楽しいアルゴリズムです。モニョモニョ動くのは面白いですね。 Pythonで実装するのは個人的にはこの辺りの複雑さが限界かなと感じました。AtcoderでPythonでやたら強い某氏なら更に複雑なアルゴリズムでも実装出来るんでしょうが、茶コーダーの私ではこの辺りが限界です。これ以上複雑なアルゴリズムならC++かRustなどコンパイラ言語で実装したいです。 アルゴリズムはおもったより簡単でプログラミングは楽でしたが、ブログ記事にまとめるのに、やたら時間がかかったので疲れました。 あんまり真面目に書くと研究に悪影響が出そうなので程々にしておきたい。

2値のHLAC特徴量で明朝体とゴシック体を分類してみる。

動機

HLAC特長量って最近よくTwitterで見かけます。この特長量がどうもすごいということらしいので、KNNのような単純な機械学習アルゴリズムであってもある程度の精度が実現可能なのではと思い、KNNでMNISTが分類できるか挑戦してみました。

HLACとは

HLAC特徴量とは人間の手でデザインされた畳み込みフィルタで畳み込みを行い、それぞれのフィルタに一致するパターンがどれだけ存在したかのヒストグラムを計算するアルゴリズムです。

一層目が手作りのカーネルを使ったカーネル数Nの畳み込み演算で、2層目が出力Nでそれぞれのカーネルの出力だけ選択的に1で選択された全結合層となっている畳み込みニューラルネットワークだと私は理解しています。

HLACは以下のような面白い特長を持っています。

1. 位置の普遍性：画像中のパターンの位置が変わっても特徴量に影響を与えない
2. 加法性:パターンAとパターンBが画像中にある場合、画像全体の特徴量はパターンAの特徴量とパターンBの特徴量の和になる。
3. 適応学習性:特徴量が固定であるので、Deepの様に毎回学習せずとも対応できる。

この辺の説明は門外漢の私よりの説明よりアダコテックのホームページを見たほうが良いと思います。

zenn.dev

主な用途としては異常検知や、不審な動きを検出するのが得意なようです。動画用のCHLACという特徴量を使うことで監視カメラ中でピッキングしている人を検出する論文などありました。 また、DNNと比較すると、圧倒的に軽量です。マイコンでも動きます。まあ、この辺は後段の分類器の速度にも依るでしょう。

実験

HLACというアルゴリズムが凄いらしいので、HLACならユーグリッド距離のKNNみたいな単純なアルゴリズムでもいい感じに推論できるのでは？ということでHLACとKNNを使ってMNISTの学習を行ってみることにしました

from keras.datasets import mnist
import matplotlib.pyplot as plt
# mnistデータのダウンロード
(X_train, y_train), (X_test, y_test) = mnist.load_data()
print("学習データのラベル：", y_train[0])
X_train = X_train
y_train = y_train
X_train[X_train<128] = False
X_train[X_train>=128] = True
plt.imshow(X_train[0].reshape(28, 28), cmap='Greys')
plt.show()
print("テストデータのラベル：", y_test[0])
X_test[X_test<128] = False
X_test[X_test>=128] = True
plt.imshow(X_test[0].reshape(28, 28), cmap='Greys')
plt.show()

公開されていた関数を拝借します。

import numpy as np
hlac_filters =  [np.array([[False, False, False], [False,  True, False], [False, False, False]]),  np.array([[False, False, False], [False,  True,  True], [False, False, False]]),  np.array([[False, False,  True], [False,  True, False], [False, False, False]]),  np.array([[False,  True, False], [False,  True, False], [False, False, False]]),  np.array([[ True, False, False], [False,  True, False], [False, False, False]]),  np.array([[False, False, False], [ True,  True,  True], [False, False, False]]),  np.array([[False, False,  True], [False,  True, False], [ True, False, False]]),  np.array([[False,  True, False], [False,  True, False], [False,  True, False]]),  np.array([[ True, False, False], [False,  True, False], [False, False,  True]]),  np.array([[False, False,  True], [ True,  True, False], [False, False, False]]),  np.array([[False,  True, False], [False,  True, False], [ True, False, False]]),  np.array([[ True, False, False], [False,  True, False], [False,  True, False]]),  np.array([[False, False, False], [ True,  True, False], [False, False,  True]]),  np.array([[False, False, False], [False,  True,  True], [ True, False, False]]),  np.array([[False, False,  True], [False,  True, False], [False,  True, False]]),  np.array([[False,  True, False], [False,  True, False], [False, False,  True]]),  np.array([[ True, False, False], [False,  True,  True], [False, False, False]]),  np.array([[False,  True, False], [ True,  True, False], [False, False, False]]),  np.array([[ True, False, False], [False,  True, False], [ True, False, False]]),  np.array([[False, False, False], [ True,  True, False], [False,  True, False]]),  np.array([[False, False, False], [False,  True, False], [ True, False,  True]]),  np.array([[False, False, False], [False,  True,  True], [False,  True, False]]),  np.array([[False, False,  True], [False,  True, False], [False, False,  True]]),  np.array([[False,  True, False], [False,  True,  True], [False, False, False]]),  np.array([[ True, False,  True], [False,  True, False], [False, False, False]])]

from scipy import signal
import numpy
def extract_hlac(image, hlac_filters):
    result = []
    image = np.uint8(image)
    hlac_filters = np.uint8(hlac_filters)
    for filter in hlac_filters:
        feature_map = signal.convolve2d(image, filter, mode='valid')
        count = np.sum(feature_map == np.sum(filter)) # マスクと一致する数を集計
        result.append(count)
    #print(result)
    return np.array(result)

特長量抽出します。

#データそのままでの推論
from sklearn.neighbors import KNeighborsClassifier
HLAC_knn = KNeighborsClassifier(n_neighbors = 10)
# 学習データをフィット
HLAC_knn.fit(hlac_train, y_train)
# 予測実行
pred_y = HLAC_knn.predict(hlac_test)
print((pred_y == y_test).sum()/len(pred_y)

#データそのままでの推論
knn = KNeighborsClassifier(n_neighbors = 10)
print(X_train.shape)
X_train = X_train.reshape((1000,28*28))
# 学習データをフィット
knn.fit(X_train, y_train)
# 予測実行
X_test = X_test.reshape((10000,28*28))
pred_y = knn.predict(X_test)

全然うまくいかないですね。学習データを用いてK=1で推論しても100%にならないので、HLACを適応すること自体が根本的にまちがっているようです。

そもそも真ん中にみんな書いてくれてるMNISTだとHLACの特徴である位置の普遍性を殺してますね。 というかMNISTが単純なKNNでもかなり精度が出ることに驚きました。こういうの得意なんだな。

敗因

敗因は以下の通りだと予想しました。

• HLACの利点である、位置の普遍性や加法性が意味を持たないタスクである。

• 人によって個人差のあるごちゃごちゃしたデータは局所的な形状の相関は意味を持たなそうなので、得意ではない。

• 文字は線画であり、形状ではなく、連続性やトポロジが意味を持っているのでHLACに向かない

• データサイズが小さすぎて別画像なのに特徴量が重複している。

結果としては「蟹スプーンで牛を捌こうとしたけどできませんでした」的なオチになってしまいました。 このままだと、HLACに悪いイメージを植え付けただけになりそうなので他のタスクも考えてみます。

明朝体とゴシックの分類

MNISTでは盛大に失敗しましたが、その反省を元に明朝体とゴシックの分類に挑戦してみることにしました。明朝体はとめ、やハネなど、先の末端に「ヒゲ飾り」「うろこ」などと呼ばれる、筆の跡が再現されているのに対して、ゴシックにはそういったものがありません。ということは、装飾にHLACの各フィルタが反応すると思うので検出しやすいのではないかと予想しました。

実験

IPAの明朝とゴシックで2100文字程度の常用漢字を描画し、HLAC特徴量を抽出したのち、明朝体なのか、ゴシック体なのかXGBoostで分類しました。Deepよりよっぽど軽くなっていると思います。

IPAexフォントおよびIPAフォントについて | 一般社団法人 文字情報技術促進協議会

常用漢字はそれぞれのフォントで画像中に描画されたあと、順番をシャッフルされ、先頭1000個を学習データ、1200以降を推論データとしました。200個はLossを確認するための開発データです。全体の学習データ数は4200文字位になります。

評価として、学習データのうち、N*50 個を実際にXGBoostの学習データとして、Nを１づつ増やして、どれだけ少ないデータで学習できるかに挑戦しました。

from PIL import Image, ImageFont, ImageDraw
import cv2
import numpy as np
import matplotlib.pyplot as plt
import numpy as np

# 画像に文字を入れる関数
Mincho_font_path = "/path/to/font/ipam.ttf"          
Mincho_font_size = 64              
Mincho_font = ImageFont.truetype(Mincho_font_path, Mincho_font_size)                           

Gothic_font_path = "/path/to/font/ipaexg.ttf"          
Gothic_font_size = 64              
Gothic_font = ImageFont.truetype(Gothic_font_path, Gothic_font_size)                           
                      

#2値のHLAC特徴量の抽出器
hlac_filters =  [np.array([[False, False, False], [False,  True, False], [False, False, False]]),  np.array([[False, False, False], [False,  True,  True], [False, False, False]]),  np.array([[False, False,  True], [False,  True, False], [False, False, False]]),  np.array([[False,  True, False], [False,  True, False], [False, False, False]]),  np.array([[ True, False, False], [False,  True, False], [False, False, False]]),  np.array([[False, False, False], [ True,  True,  True], [False, False, False]]),  np.array([[False, False,  True], [False,  True, False], [ True, False, False]]),  np.array([[False,  True, False], [False,  True, False], [False,  True, False]]),  np.array([[ True, False, False], [False,  True, False], [False, False,  True]]),  np.array([[False, False,  True], [ True,  True, False], [False, False, False]]),  np.array([[False,  True, False], [False,  True, False], [ True, False, False]]),  np.array([[ True, False, False], [False,  True, False], [False,  True, False]]),  np.array([[False, False, False], [ True,  True, False], [False, False,  True]]),  np.array([[False, False, False], [False,  True,  True], [ True, False, False]]),  np.array([[False, False,  True], [False,  True, False], [False,  True, False]]),  np.array([[False,  True, False], [False,  True, False], [False, False,  True]]),  np.array([[ True, False, False], [False,  True,  True], [False, False, False]]),  np.array([[False,  True, False], [ True,  True, False], [False, False, False]]),  np.array([[ True, False, False], [False,  True, False], [ True, False, False]]),  np.array([[False, False, False], [ True,  True, False], [False,  True, False]]),  np.array([[False, False, False], [False,  True, False], [ True, False,  True]]),  np.array([[False, False, False], [False,  True,  True], [False,  True, False]]),  np.array([[False, False,  True], [False,  True, False], [False, False,  True]]),  np.array([[False,  True, False], [False,  True,  True], [False, False, False]]),  np.array([[ True, False,  True], [False,  True, False], [False, False, False]])]

from scipy import signal
import numpy
def extract_hlac(image, hlac_filters):
    result = []
    image = np.uint8(image)
    hlac_filters = np.uint8(hlac_filters)
    for filter in hlac_filters:
        feature_map = signal.convolve2d(image, filter, mode='valid')
        count = np.sum(feature_map == np.sum(filter)) # マスクと一致する数を集計
        result.append(count)
    #print(result)
    return np.array(result)



Mincho_images = []
Gothic_images = []

for kanji in zyouyou:
  size=(64,64)
  black_img=np.zeros(size,np.uint8)
  white_img=black_img+255
  img = Image.fromarray(white_img)                          
  draw = ImageDraw.Draw(img)   
  draw.text((0, 0), kanji, font=Mincho_font, fill=(0))
  Mincho_images.append(np.array(img) > 128)

  size=(64,64)
  black_img=np.zeros(size,np.uint8)
  white_img=black_img+255
  img = Image.fromarray(white_img)                          
  draw = ImageDraw.Draw(img)   
  draw.text((0, 0), kanji, font=Gothic_font, fill=(0))
  Gothic_images.append(np.array(img) > 128)


Mincho = Mincho_images
Mincho_labels = np.zeros(len(Mincho_images))
Gothic = Gothic_images
Gothick_labels = np.ones(len(Gothic_images))

#常用漢字一覧
zyouyou = "亜哀挨愛曖悪握圧扱宛嵐安案暗以衣位囲医依委威為畏胃尉異移萎偉椅彙意違維慰遺緯域育一壱逸茨芋引印因咽姻員院淫陰飲隠韻右宇羽雨唄鬱畝浦運雲永泳英映栄営詠影鋭衛易疫益液駅悦越謁閲円延沿炎怨宴媛援園煙猿遠鉛塩演縁艶汚王凹央応往押旺欧殴桜翁奥横岡屋億憶臆虞乙俺卸音恩温穏下化火加可仮何花佳価果河苛科架夏家荷華菓貨渦過嫁暇禍靴寡歌箇稼課蚊牙瓦我画芽賀雅餓介回灰会快戒改怪拐悔海界皆械絵開階塊楷解潰壊懐諧貝外劾害崖涯街慨蓋該概骸垣柿各角拡革格核殻郭覚較隔閣確獲嚇穫学岳楽額顎掛潟括活喝渇割葛滑褐轄且株釜鎌刈干刊甘汗缶完肝官冠巻看陥乾勘患貫寒喚堪換敢棺款間閑勧寛幹感漢慣管関歓監緩憾還館環簡観韓艦鑑丸含岸岩玩眼頑顔願企伎危机気岐希忌汽奇祈季紀軌既記起飢鬼帰基寄規亀喜幾揮期棋貴棄毀旗器畿輝機騎技宜偽欺義疑儀戯擬犠議菊吉喫詰却客脚逆虐九久及弓丘旧休吸朽臼求究泣急級糾宮救球給嗅窮牛去巨居拒拠挙虚許距魚御漁凶共叫狂京享供協況峡挟狭恐恭胸脅強教郷境橋矯鏡競響驚仰暁業凝曲局極玉巾斤均近金菌勤琴筋僅禁緊錦謹襟吟銀区句苦駆具惧愚空偶遇隅串屈掘窟熊繰君訓勲薫軍郡群兄刑形系径茎係型契計恵啓掲渓経蛍敬景軽傾携継詣慶憬稽憩警鶏芸迎鯨隙劇撃激桁欠穴血決結傑潔月犬件見券肩建研県倹兼剣拳軒健険圏堅検嫌献絹遣権憲賢謙鍵繭顕験懸元幻玄言弦限原現舷減源厳己戸古呼固股虎孤弧故枯個庫湖雇誇鼓錮顧五互午呉後娯悟碁語誤護口工公勾孔功巧広甲交光向后好江考行坑孝抗攻更効幸拘肯侯厚恒洪皇紅荒郊香候校耕航貢降高康控梗黄喉慌港硬絞項溝鉱構綱酵稿興衡鋼講購乞号合拷剛傲豪克告谷刻国黒穀酷獄骨駒込頃今困昆恨根婚混痕紺魂墾懇左佐沙査砂唆差詐鎖座挫才再災妻采砕宰栽彩採済祭斎細菜最裁債催塞歳載際埼在材剤財罪崎作削昨柵索策酢搾錯咲冊札刷刹拶殺察撮擦雑皿三山参桟蚕惨産傘散算酸賛残斬暫士子支止氏仕史司四市矢旨死糸至伺志私使刺始姉枝祉肢姿思指施師恣紙脂視紫詞歯嗣試詩資飼誌雌摯賜諮示字寺次耳自似児事侍治持時滋慈辞磁餌璽鹿式識軸七𠮟失室疾執湿嫉漆質実芝写社車舎者射捨赦斜煮遮謝邪蛇尺借酌釈爵若弱寂手主守朱取狩首殊珠酒腫種趣寿受呪授需儒樹収囚州舟秀周宗拾秋臭修袖終羞習週就衆集愁酬醜蹴襲十汁充住柔重従渋銃獣縦叔祝宿淑粛縮塾熟出述術俊春瞬旬巡盾准殉純循順準潤遵処初所書庶暑署緒諸女如助序叙徐除小升少召匠床抄肖尚招承昇松沼昭宵将消症祥称笑唱商渉章紹訟勝掌晶焼焦硝粧詔証象傷奨照詳彰障憧衝賞償礁鐘上丈冗条状乗城浄剰常情場畳蒸縄壌嬢錠譲醸色拭食植殖飾触嘱織職辱尻心申伸臣芯身辛侵信津神唇娠振浸真針深紳進森診寝慎新審震薪親人刃仁尽迅甚陣尋腎須図水吹垂炊帥粋衰推酔遂睡穂随髄枢崇数据杉裾寸瀬是井世正生成西声制姓征性青斉政星牲省凄逝清盛婿晴勢聖誠精製誓静請整醒税夕斥石赤昔析席脊隻惜戚責跡積績籍切折拙窃接設雪摂節説舌絶千川仙占先宣専泉浅洗染扇栓旋船戦煎羨腺詮践箋銭潜線遷選薦繊鮮全前善然禅漸膳繕狙阻祖租素措粗組疎訴塑遡礎双壮早争走奏相荘草送倉捜挿桑巣掃曹曽爽窓創喪痩葬装僧想層総遭槽踪操燥霜騒藻造像増憎蔵贈臓即束足促則息捉速側測俗族属賊続卒率存村孫尊損遜他多汰打妥唾堕惰駄太対体耐待怠胎退帯泰堆袋逮替貸隊滞態戴大代台第題滝宅択沢卓拓託濯諾濁但達脱奪棚誰丹旦担単炭胆探淡短嘆端綻誕鍛団男段断弾暖談壇地池知値恥致遅痴稚置緻竹畜逐蓄築秩窒茶着嫡中仲虫沖宙忠抽注昼柱衷酎鋳駐著貯丁弔庁兆町長挑帳張彫眺釣頂鳥朝貼超腸跳徴嘲潮澄調聴懲直勅捗沈珍朕陳賃鎮追椎墜通痛塚漬坪爪鶴低呈廷弟定底抵邸亭貞帝訂庭逓停偵堤提程艇締諦泥的笛摘滴適敵溺迭哲鉄徹撤天典店点展添転塡田伝殿電斗吐妬徒途都渡塗賭土奴努度怒刀冬灯当投豆東到逃倒凍唐島桃討透党悼盗陶塔搭棟湯痘登答等筒統稲踏糖頭謄藤闘騰同洞胴動堂童道働銅導瞳峠匿特得督徳篤毒独読栃凸突届屯豚頓貪鈍曇丼那奈内梨謎鍋南軟難二尼弐匂肉虹日入乳尿任妊忍認寧熱年念捻粘燃悩納能脳農濃把波派破覇馬婆罵拝杯背肺俳配排敗廃輩売倍梅培陪媒買賠白伯拍泊迫剝舶博薄麦漠縛爆箱箸畑肌八鉢発髪伐抜罰閥反半氾犯帆汎伴判坂阪板版班畔般販斑飯搬煩頒範繁藩晩番蛮盤比皮妃否批彼披肥非卑飛疲秘被悲扉費碑罷避尾眉美備微鼻膝肘匹必泌筆姫百氷表俵票評漂標苗秒病描猫品浜貧賓頻敏瓶不夫父付布扶府怖阜附訃負赴浮婦符富普腐敷膚賦譜侮武部舞封風伏服副幅復福腹複覆払沸仏物粉紛雰噴墳憤奮分文聞丙平兵併並柄陛閉塀幣弊蔽餅米壁璧癖別蔑片辺返変偏遍編弁便勉歩保哺捕補舗母募墓慕暮簿方包芳邦奉宝抱放法泡胞俸倣峰砲崩訪報蜂豊飽褒縫亡乏忙坊妨忘防房肪某冒剖紡望傍帽棒貿貌暴膨謀頰北木朴牧睦僕墨撲没勃堀本奔翻凡盆麻摩磨魔毎妹枚昧埋幕膜枕又末抹万満慢漫未味魅岬密蜜脈妙民眠矛務無夢霧娘名命明迷冥盟銘鳴滅免面綿麺茂模毛妄盲耗猛網目黙門紋問冶夜野弥厄役約訳薬躍闇由油喩愉諭輸癒唯友有勇幽悠郵湧猶裕遊雄誘憂融優与予余誉預幼用羊妖洋要容庸揚揺葉陽溶腰様瘍踊窯養擁謡曜抑沃浴欲翌翼拉裸羅来雷頼絡落酪辣乱卵覧濫藍欄吏利里理痢裏履璃離陸立律慄略柳流留竜粒隆硫侶旅虜慮了両良料涼猟陵量僚領寮療瞭糧力緑林厘倫輪隣臨瑠涙累塁類令礼冷励戻例鈴零霊隷齢麗暦歴列劣烈裂恋連廉練錬呂炉賂路露老労弄郎朗浪廊楼漏籠六録麓論和話賄脇惑枠湾腕"

#データセット生成
import tqdm
images = Mincho_images + Gothic_images 

data_len = len(images)
labels = np.hstack([Mincho_labels,Gothick_labels])

#順序をシャッフルする
shuffle_index = np.arange(data_len)
np.random.shuffle(shuffle_index)

images = np.array(images)
images = images[shuffle_index]
labels = labels[shuffle_index]

kanji_hlac = []

#二値のHLAC特徴量抽出
for index in tqdm.tqdm(range(data_len)):
  hlac = extract_hlac(images[index],hlac_filters)
  kanji_hlac.append(extract_hlac(images[index],hlac_filters))

#XGboost 分類器で分類
eval_hlac = np.vstack(kanji_hlac[1200:])
eval_label = labels.flatten()[1200:]

from xgboost import XGBClassifier
for data_num in [50,100,250,500,1000]: 
  train_data = np.vstack(kanji_hlac[0:data_num])
  train_label = labels.flatten()[0:data_num]
  #xgboost のLoss確認に使いたかったら使う
  dev_data = np.vstack(kanji_hlac[1000:1200])
  dev_label = labels.flatten()[1000:1200]

  print(train_label)

  model = XGBClassifier(early_stopping_rounds=1,n_estimators=1000)
  model.fit(train_data, train_label,verbose=True)  

  pred = model.predict(eval_hlac)
  print(f"{data_num} datas accuracy is {((pred == eval_label).sum()/pred.shape[0] )}")

結果

上に示したプログラムで得られる学習につかうデータ数と推論精度の関係を以下の図に示します。 250データあれば性能が95%を超えているので、手動のアノテーションで十分対応可能な規模だと思います。

学習データ数と、推論精度

MNISTの実験と比べるとなかなか良い結果が得られたんじゃないでしょうか。

というわけで、卒業論文のフォントをメチャクチャにしてしまう学生が現れても、HLACで異常検知出来ることがわかりました。