指定した点から二値画像の前景まで最短線分を描画する

# [画像をグラフに変換](https://github.com/Image-Py/sknw)してノード間の経路探索がしたい

「マウスイベントで得た座標」とスケルトン画像は相性が悪いです．
点がスケルトン上に乗ることはまず無いと言っていいでしょう．
これを解決する「追加したノードから最も距離が近いエッジにノードを追加してエッジでつなぐ」操作はグラフっぽくないという直感があります．
なので画像処理で解決する関数を書きました．
もっといい方法があるよ！NetworkXで丁度良い関数があるよ！という方は是非コメント欄で教えてください．

## 処理

1. 全ての輪郭と指定した点との距離から最短距離を求めて
1. 求めた最短距離を半径とする円と入力画像の重複部分を円弧と見立てて
1. 円弧の重心と指定した点を通る線分を描画して
1. はみ出た部分を消去する

コンパスで二等辺三角形を描くように線分の終点が複数得られることが多いです．
![multiple_end_pts.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/53728a98-3246-6357-4bd0-47881d98d8b4.png "複数の終点の例")

コードベタ貼り

```python:dsls.py
import os
import sys
import cv2
import numpy as np

def draw_shortest_line_segments(gray_src_img, pts):
    dest_img = gray_src_img.copy()
    rows, cols = gray_src_img.shape
    diagonal_length = int((rows**2 + cols**2)**0.5) + 1
    gray_blank = np.zeros((rows, cols), np.uint8)
    contours, _ = cv2.findContours(gray_src_img, cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)
    end_pts = np.array([], np.uint16)
    for i, pt in enumerate(pts):
        cnt_dists = np.array([])
        for cnt in contours:
            retval = cv2.pointPolygonTest(cnt, pt, True)
            cnt_dists = np.append(cnt_dists, abs(retval))
        if np.min(cnt_dists) == 0 or gray_src_img[pt[1], pt[0]] == 255:
            end_pts = np.append(end_pts, i)
            end_pts = np.append(end_pts, pt)
        else:
            radius = int(np.min(cnt_dists)) - 1
            while True:
                gray_tmp_img = gray_blank.copy()
                cv2.circle(gray_tmp_img, center=pt, radius=radius, color=255, thickness=1, lineType=cv2.LINE_8, shift=0)
                bin_candidate_end_pts = (gray_src_img != 0) & (gray_tmp_img == 255)
                if np.any(bin_candidate_end_pts):
                    gray_tmp_img = gray_blank.copy()
                    gray_tmp_img[bin_candidate_end_pts] = 255
                    _, _, _, centroids = cv2.connectedComponentsWithStats(gray_tmp_img)
                    for centroid in centroids[1:]:
                        radius_centroid = np.linalg.norm(centroid - pt)
                        if radius_centroid == 0:
                            print(f'Point {pt} : bullseye error.', file=sys.stderr)
                        else:
                            radius_ratio = radius/radius_centroid
                            end_pt = np.rint((1 - radius_ratio)*np.array(pt) + radius_ratio*centroid).astype(np.uint16)
                            cv2.line(gray_tmp_img, pt, end_pt, 255, thickness=1, lineType=cv2.LINE_8)
                            end_pts = np.append(end_pts, i)
                            end_pts = np.append(end_pts, end_pt)
                            gray_tmp_img[bin_candidate_end_pts] = 0
                            _, labels = cv2.connectedComponents(gray_tmp_img)
                            dest_img[labels == labels[pt[1], pt[0]]] = 255
                    break
                elif radius > diagonal_length:
                    print(f'Point {pt} : Distance exceeds the length of the diagonal.', file=sys.stderr)
                    break
                radius += 1
    end_pts = end_pts.reshape(int(end_pts.shape[0]/3),3)
    return dest_img, end_pts

if __name__ == "__main__":
    pts = [[302, 239], [2973, 238], [2944, 3887],[ 303, 3903]]
    input_file = sys.argv[1]
    gray_img = cv2.imread(input_file,0)
    dest_img, end_pts = draw_shortest_line_segments(gray_img, pts)
    print(end_pts)
    output_file = os.path.splitext(os.path.basename(input_file))[0] + '_sls.png'; cv2.imwrite(output_file, dest_img)
    cv2.imshow('dest_img', dest_img); cv2.waitKey(0); sys.exit()
```

## 極座標の説明
![polar.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/5ae74e6a-db24-7d15-adca-49737a7daa89.gif "輪郭抽出とスケルトン化の例")

## 課題
- カラー対応は各自
- 円の中心を指定した結果は未定義 <-- `bullseye error.`
- 円弧と線分の交点が離散値として求まらない場合，線分の終点は円弧より外にある
- 線分の終点は複数あることが多い

グラフ変換の前処理として使うならどれも問題にならないと思います．

## スケルトン画像の素材

![ske1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/f67cc0cc-fbe8-44a4-8d6f-ec8ec90efab0.png "素材1")
![ske2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/10093152-cc43-2805-3c89-ca534159ef7f.png "素材2")
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/a4076818-5543-403d-0a30-37c420eab406.png "素材3")
![IMG_6834_test_sknw_test_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/81fbcf11-3254-405c-c0a8-9c43d13c7e0c.png "グラフ変換を用いて求めた輪郭")
![25E9997C-D2BA-495B-A4B2-DEEA590EAA1D.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/207096/c980dc13-ae90-adad-1172-ab7513b202e7.png "素材4")

汎用的なホモグラフィー変換ツールを作るにはグラフをフィッティングする必要がありそう．