描画した線をつまんで編集できる、CLIP STUDIOのようなベクターレイヤーを実装する


# はじめに
本記事はOpenCV Advent Calendar 2022 の10日目の記事です。

3日目の[【画像認識】AIひろゆきがスプラトゥーン3のキルデス報告してくれるアプリ作った話](https://qiita.com/Kazuma_Kikuya/items/71644455015a30a01571)に引き続きアドベントカレンダーに投稿します。

今やPCやタブレットを利用してデジタルイラストを書くことが当たり前になった時代。
僕が中学生の頃は、ライセンスが5000円で買える「ペイントツールsai」一強の時代でした。（今では利用者はほとんどいないでしょうが…）
その後CLIP STUDIOが台頭し、タブレット専用アプリもどんどん増えイラスト作成アプリは軍用割拠の時代ではないでしょうか。

僕がかつて、週刊連載の漫画アシスタントをやっていた時は**徹夜・泊まり込みの中CLIP STUDIOには嫌というほどお世話になりました**🤣🤣🤣
オートアクション、ショートカットの設定、G13のキー配置、時短術には今でも相当詳しいと思います。

さて、今どきのイラストアプリでは当たり前に搭載されているベクター機能というものがあります。
一度ペンを走らせ引いた線を制御点を線をつまむように引っ張ることで線を湾曲させる機能で、
ペン入れのやり直し、調整ができる機能です。
複数の点の位置とそれを繋いだ線、色、カーブなどを数値データとして記憶し再現しており、きれいなペン入れを表現することができます。

昔から同じようなプログラムを実装したい！と思っていたのですがこの手のグラフィック処理のアルゴリズムを解説している記事って全く無いですよね。
**Catmull-Romスプライン曲線**というアルゴリズムが利用できそうだったので試してみたところ、結構簡単にそれっぽいアプリが出来たのでそのアルゴリズムの解説を本記事でしていきたいと思います。

# DEMO
線の色や太さを設定することができるようになっています。
制御点から10px以内にカーソルが入った状態で右ドラッグで制御点を移動できます。

<iframe width="597" height="360" src="https://www.youtube.com/embed/ephADfQnPC4" title="Catmull-Rom Spline" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

Githubにソース載せてます。opencvとnumpyあればmain.py実行すれば動作します

https://github.com/kazumax75/Catmull-Rom_Spline
# 普通にドラッグで線を引いてみる
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/295263/b0a34e9b-1853-b61b-8110-8bb8751b4bc5.png)

手ぶれ補正などは一切無い純粋なxy座標のリストをそのまま描画しました。見ての通り、ゆっくりドラッグしないと点と点の隙間がスカスカですね。体感リフレッシュレート60Hzくらいで入力を受け付けてる感じがします。WinAPIのメッセージループでWM_MOVEが発生する感覚と体感同じかな？と思います。低レベルで取得したマウス移動の取得と、openCVのマウスイベント取得は遜色ないように思います（さらに低レベルであるRaw Input APIは試したことないです）
```python
import cv2
import numpy as np

def mouseCallback(event, x, y, flags, param):
    global lb_flag
    global img

    if event == cv2.EVENT_LBUTTONDOWN: 
        lb_flag = True
        img[y, x] = (255,0,0)
    elif event == cv2.EVENT_MOUSEMOVE and lb_flag:
        img[y, x] = (255,0,0)
    elif event == cv2.EVENT_LBUTTONUP and lb_flag :
        lb_flag = False

cv2.namedWindow('image')
cv2.setMouseCallback('image', mouseCallback)

lb_flag = False
width  = 1000
height = 800
img = np.zeros((height, width, 3), dtype=np.uint8)
img.fill(255) # 白で塗りつぶす

while(1):
    cv2.imshow('image', img )# 画像表示
    key = cv2.waitKey(1) & 0xFF # キー入力受付
    if key == ord('q'):# qキーで終了
        break

cv2.destroyAllWindows()
```

これらの点をブレゼンハムのアルゴリズム等、点と点を直線で結ぶようにすると、お絵かきアプリとして最低限の線を引く機能が実装できました。
```python
import cv2
import numpy as np

def mouseCallback(event, x, y, flags, param):
    global lb_flag
    global img
    global prev_pt
    
    if event == cv2.EVENT_LBUTTONDOWN: 
        lb_flag = True
        img[y, x] = (255,0,0)
        prev_pt = (x, y)
    
    elif event == cv2.EVENT_MOUSEMOVE and lb_flag:
        cv2.line(
            img, 
            prev_pt, 
            (x, y),
            (255,0,0), # BGR
            thickness=1
        )
        prev_pt = (x, y)
        
    elif event == cv2.EVENT_LBUTTONUP and lb_flag :
        lb_flag = False

cv2.namedWindow('image')
cv2.setMouseCallback('image', mouseCallback)

lb_flag = False
prev_pt = ()
width  = 1000
height = 800
img = np.zeros((height, width, 3), dtype=np.uint8)
img.fill(255) # 白で塗りつぶす

while(1):
    # 画像表示
    cv2.imshow('image', img )
    
    # キー入力受付
    key = cv2.waitKey(1) & 0xFF
    if key == ord('c'):
        pass
        
    elif key == ord('q'):# qキーで終了
        break

cv2.destroyAllWindows()
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/295263/41b61088-eaf8-355f-2e1f-f477f5eedf9b.png)

余談ですが過去にC++/WintabでWacomタブレットの入力取得のコードを書いたときは、確か60Hz以上のリフレッシュレートで取得ができた気がします。ペンタブだとマウス入力の取得より多くのトラックポイントの取得ができるかも。
# cv2.approxPolyDP()で入力されたトラックポイントを間引く

ベクター機能の実装するには、入力された点からベクターの制御点のみを残すよう点を「間引く」処理が必要になります。

間引き処理に**openCVのapproxPolyDP**()を利用します。これは輪郭の近似するための関数です。

http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_imgproc/py_contours/py_contour_features/py_contour_features.html

approxPolyDP()はfindContours()の返す輪郭配列を引数として扱うことが多いと思いますが、実はxy座標の配列を渡すことも可能なのです。

GPSログのノイズ除去にも使われる**Douglas−Peuckerアルゴリズム**を利用してるようです。
詳しい原理を知らずともこの関数を利用すれば簡単に点の間引きが行えました。

```python
import cv2
import numpy as np

# 間引き対象のxy座標リスト
array = [
    (0,0),
    (0,1),
    (0,2),
    (0,3),
    (0,4),
    (0,5),
]
points = np.array(array, dtype=np.int32)

print("入力点", points)

epsilon = 0.001 * cv2.arcLength(points, False)
approx = cv2.approxPolyDP(points, epsilon, False)
approx = np.squeeze(approx)

print("間引き後", approx)
```
第2引数は間引く割合を指定します。cv2.arcLength()で線の長さを取得し、それを1/n倍にするというのが定石のようです。1/1000倍くらいがちょうど良さそうです

# Catmull-Romスプライン曲線

さて、ここまでで入力したストロークのキーポイントの取得までができました。
キーポイント同士を補完し繋いでいく処理が必要になりますが、元の入力された線と差が少ない補完が必要になります。

曲線アルゴリズムといえば、ベジェ曲線、スプライン曲線が有名ですが、これらのアルゴでは制御点を必ず通るものではありません。なので任意の数の制御点をすべて通るCatmull-Rom(キャットムル-ロム)スプライン曲線を試しました。

Catmull-Romスプラインは、４つの点を参照し内側の2点の間を補完してくれます

エルミート曲線を元にしたアルゴリズムだそうで、係数が4つ必要、つまり４つの点から補完座標を算出します。４つの点を参照し内側の2点の間を補完してくれます。

計算に4点必要なため、キーポイント配列の頭と末尾の値を複製します。

アルゴリズムの解説はググれば出尽くしているので参考にしながらクラスを作って実装。

http://wakaba-technica.sakura.ne.jp/library/interpolation_catmullrom_spline.html

## CatmullRomSplineクラスを定義する
インスタンス化時にapproxPolyDP()で間引き済みのxy座標のリストを渡しておき、getValue()で補完した座標算出します。描画の際は、
・制御点の数-1のループ
・点と点の補完する分割数のループ
とネストしたループ内でピクセル操作を行うのですが、ジェネレータ関数のplot()にまとめておけばシンプルなforで回すことができます。
```python
import copy
import numpy as np

class CatmullRomSpline:
    def __init__(self, pts):
        _points = []
        _points = copy.deepcopy(pts)
        _points.insert(0,  pts[0])
        _points.insert(-1, pts[-1])
        self.points = np.array(_points)
        # print(self.points)
        
    def __calcVal(self, x0, x1, v0, v1, t):
        return (2.0 * x0 - 2.0 * x1 + v0 + v1) * t**3 + (-3.0 * x0 + 3.0 * x1 - 2.0 * v0 - v1) * t**2 + v0 * t + x0
    
    def __getValue(self, idx, t):
        if not 0 <= t <= 1.0: return 
        
        p1 = self.points[idx]
        p2 = self.points[idx+1]
        p3 = self.points[idx+2]
        p4 = self.points[idx+3]
        
        v0 = (p3 - p1) * 0.5
        v1 = (p4 - p2) * 0.5
        
        return (
            self.__calcVal(p2[0], p3[0], v0[0], v1[0], t),
            self.__calcVal(p2[1], p3[1], v0[1], v1[1], t),
        )
    
    def getKeyPoints(self):
        return self.points[1:-1, :]
        
    def moveKeyPoint(self, index, x, y):
        if index == 0:
            # 先頭の制御点のとき
            self.points[0] = [x, y]
            self.points[1] = [x, y]
        elif index == self.points.shape[0] - 2 - 1:
            # 末尾の制御点のとき
            self.points[index+1] = [x, y]
            self.points[index+2] = [x, y]
        else:
            self.points[index + 1] = [x, y]
            
        return 
        
    def plot(self, div): #補完した座標を返すジェネレータ
        length = len(self.points) - 2 - 1
        for i in range(length):
            for j in range(div):
                _p = self.__getValue(i, j / div)
                yield _p
                
        # 最後の制御点を返す
        yield (self.points[-1])
```

# ペイントアプリのクラス設計を考えてみる
まずイラストアプリには
キャンバスがあり、その中にレイヤーが複数枚存在する。レイヤーには通常レイヤーとベクターレイヤがある。
ペンや消しゴム、バケツ塗りつぶし等のツールが存在し、色や太さの変更ができる。ツールはショートカットキーやボタンで切り替え可能。
CLIP STUDIOのペンツールであれば左ドラッグしたとき描画　右クリックしたとき、スポイトで色を拾う等挙動はツールごとに様々ある
と諸々考慮し下記のクラス設計に。

もっと細かく分けられそうですがざっとこんな感じでgithubのソースでは実装しました
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/295263/b3d3009a-0f65-e28d-e98d-360a73c2a540.png)

入力の受付はopenCVのイベントハンドラ、Win32APIのウィンドウメッセージ、ペンタブ入力等に対応したいので抽象化した。
Curveというインターフェース作ってCatmullRomSplineクラスに継承させたほうが良さそう

本当は点や線の描画処理と画像のラスタデータも抽象を作るべきだと思う。
openCVによる描画、DIBのポインタを直接操作した描画　等色々あるので
# まとめ

ほぼほぼクリスタの仕様と変わらないものが結構簡単に実装できましたね。
ベクタレイヤーの仕組みとしてはデバイスから入力された座標リストから制御点となる点以外を間引く処理、制御点間を補完する曲線の算出処理を行うことで実現しているようです。

点の間引きは分かりませんが、クリスタのベクターの補間アルゴリズムはCatmull-Romスプラインで間違いないと思います。（アルファ値は0.5じゃなさそうだけど）

saiのベクタ（ペン入れレイヤー）のほうが直感的な操作ができてかなり好みなのですが、あちらは曲線の感じCatmull-Romで無いのは間違いなさそうで、体感「区分的 3 次エルミート補間」に近い曲線かな？と推測しています。

https://qiita.com/maskot1977/items/913ef108ff1e2ba5b63f

フリーソフトのAzPainterがオープンソースでgithubに公開されているのでそちらも調査してみたいですね。