【蟻本】部分和問題
// あり本 p.34 // 部分和問題 // 数列の中からいくつか選び和がkにできるか判定する #include <bits/stdc++.h> using namespace std; static const int MAX_N = 20; int cnt = 0; int k,n; int a[MAX_N]; bool dfs(int i,int s) { if(i==n)return s==k; //a[i]を使わない場合 if(dfs(i+1,s))return true; //a[i]を使う場合 if(dfs(i+1,s+a[i]))return true; return false; } int main() { cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; cout<<(dfs(0,0)?"yes":"no")<<endl; return 0; }
【画像処理】画像機械学習の前処理
前処理フィルタについて | 画像処理.com | キーエンス
元の画像
グレイスケール
膨張フィルタ
収縮フィルタ
平均化フィルタ
平均化フィルタ
#coding:utf-8 """ $jupyter notebook $for python3.x """ from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans from PIL import Image from PIL import ImageDraw from random import randint from os.path import exists from os import mkdir from math import fabs from random import random from copy import deepcopy from math import log from math import sqrt import cv2 import numpy as np from collections import namedtuple import csv INF = 1e30 def convert(img): """収縮フィルタ""" #画像のサイズ height = img.shape[0] width = img.shape[1] #変換後のリスト img2 = np.zeros((width, height), np.uint8) #変換--------------------------------------------------------------- for y in range(1,height-1): for x in range(1,width-1): tmp = 0.0 for a in range(y-1,y+2): for b in range(x-1,x+2): tmp += img[a,b] tmp /= 9 img2[y,x] = tmp #------------------------------------------------------------------- #画像を表示 cv2.imshow("image",img2) cv2.waitKey(0)#キーを押すと終了 cv2.destroyAllWindows() #画像を出力 file_name = "expansion_filter" cv2.imwrite(file_name+".jpg",img2) def main(): #特徴ベクトルの型の定義 vec = namedtuple('vec_info',['GBR','coordinate']) #画像を読み込み filename = "ika.png" img = cv2.imread(filename,0) #GLAY_SCALE画像を出力 file_name = "GRAY_SCALE"+filename cv2.imwrite(file_name+".jpg",img) #膨張フィルタ convert(img) if __name__ == '__main__': main()
膨張フィルタ
for y in range(1,height-1): for x in range(1,width-1): tmp = -INF for a in range(y-1,y+2): for b in range(x-1,x+2): tmp = max(tmp,img[a,b]) img2[y,x] = tmp
収縮フィルタ
for y in range(1,height-1): for x in range(1,width-1): tmp = INF for a in range(y-1,y+2): for b in range(x-1,x+2): tmp = min(tmp,img[a,b]) img2[y,x] = tmp
for y in range(1,height-1): for x in range(1,width-1): tmp = list() for a in range(y-1,y+2): for b in range(x-1,x+2): tmp.append(img[a,b]) print(tmp) img2[y,x] = sorted(tmp)[4]
端っこについては考察していない.
4マスで考えれば良いのかな？
特徴抽出はあくまで中央のものだから端っこはあまり重要ではない気がするが
【Python】【画像処理】k-means法で画像を減色
減色された画像の色(代表ベクトル)とグラフの点の色が同じになるように改良した.
matplotlib.pyplotのscatterの色の指定ではc="#000000"のように16進数でRGBの順に指定する必要がある.
OpenCVではGBRの順なので気をつける.
#coding:utf-8 """ $jupyter notebook $for python3.x """ from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans from PIL import Image from PIL import ImageDraw from random import randint from os.path import exists from os import mkdir from math import fabs from random import random from copy import deepcopy from math import log from math import sqrt import cv2 import numpy as np from collections import namedtuple import csv def calc_centroid(vecs): g,b,r = 0,0,0 for v in vecs: g+=v[0][0] b+=v[0][1] r+=v[0][2] g/=len(vecs) b/=len(vecs) r/=len(vecs) return (int(round(g)),int(round(b)),int(round(r))) def rgb2hex(centroids): #gbr->rbgの16進数 hex_color_code = [] for v in centroids: tmp = [] hex_code = "" for e in v: if e<16: h = "0"+str(hex(e))[2:] else: h = str(hex(e))[2:] tmp.append(h) hex_code = tmp[2]+tmp[1]+tmp[0] hex_color_code.append("#"+hex_code) return hex_color_code def main(): #特徴ベクトルの型の定義 vec = namedtuple('vec_info',['GBR','coordinate']) #画像を読み込み img = cv2.imread("sample.png") #画像のサイズ height = img.shape[0] width = img.shape[1] #特徴ベクトルの総数(画素数) num_vec = height*width #各画素の特徴ベクトルを取得する vectors = [] for y in range(height): for x in range(width): BGR = img[y,x] v = vec(BGR,(y,x)) vectors.append(v) vectors = np.array(vectors) feature_vectors = vectors[:,0] #feature_vectors = np.reshape(feature_vectors,(1,len(feature_vectors))) tmp = [] for vec in feature_vectors: tmp.append(vec) feature_vectors = np.array(list(tmp)) #特徴空間の点をプロット feature_vectors_G = feature_vectors[:,0] feature_vectors_B = feature_vectors[:,1] feature_vectors_R = feature_vectors[:,2] #初期プロットの表示 fig = plt.figure() ax = Axes3D(fig) ax.scatter3D(feature_vectors_G,feature_vectors_B,feature_vectors_R) plt.show() #クラスタの個数 num_cluster = 50 #k-means法 km = KMeans(n_clusters=num_cluster, init='random', n_init=10, max_iter=100, tol=1e-04, random_state=0 ) y_km = km.fit_predict(feature_vectors)#y_kmにクラスタの番号が保存される #クラス毎に分類する #vectorsとfeature_vectorsとy_kmは互いに添字が一致 CLUSTER = [[] for _ in range(num_cluster)] for i,v in enumerate(vectors): for which_cluster in range(num_cluster): if y_km[i] == which_cluster: CLUSTER[which_cluster].append(v) #セントロイドを求める centroids = [[] for _ in range(len(CLUSTER))] for i,vecs in enumerate(CLUSTER): centroids[i] = calc_centroid(vecs) #セントロイドを16進数コードに変換する COLOR = rgb2hex(centroids) #クラス毎にプロットする #COLOR = ['b','g','r','c','m','y','k'] CLUSTER_COLOR = [[[],[],[]] for _ in range(num_cluster)] fig = plt.figure() ax = Axes3D(fig) ax.set_xlabel('G') ax.set_ylabel('B') ax.set_zlabel('R') for i,vecs in enumerate(CLUSTER): for j,v in enumerate(vecs): CLUSTER_COLOR[i][0].append(v[0][0]) CLUSTER_COLOR[i][1].append(v[0][1]) CLUSTER_COLOR[i][2].append(v[0][2]) for k in range(3): CLUSTER_COLOR[i][k] = np.array(CLUSTER_COLOR[i][k]) for i in range(len(CLUSTER_COLOR)): ax.scatter(CLUSTER_COLOR[i][0],CLUSTER_COLOR[i][1],CLUSTER_COLOR[i][2],c=COLOR[i]) plt.show() #画像を変換していく for i,vecs in enumerate(CLUSTER): for j,v in enumerate(vecs): img[v[1][0],v[1][1]] = centroids[i] #画像を表示 cv2.imshow("image",img) cv2.waitKey(0)#キーを押すと終了 cv2.destroyAllWindows() #画像を出力 file_name = "res_"+str(len(CLUSTER)) cv2.imwrite(file_name+".jpg",img) if __name__ == '__main__': main()
【Python】【画像処理】k-means法で画像を減色
上の画像を7色に減色した.
ソースコードは適宜変数を付け足していったので自分でもわからなくなったので注意.
#coding:utf-8 """ $jupyter notebook $for python3.x """ from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans from PIL import Image from PIL import ImageDraw from random import randint from os.path import exists from os import mkdir from math import fabs from random import random from copy import deepcopy from math import log from math import sqrt import cv2 import numpy as np from collections import namedtuple import csv def calc_centroid(vecs): g,b,r = 0,0,0 for v in vecs: g+=v[0][0] b+=v[0][1] r+=v[0][2] g/=len(vecs) b/=len(vecs) r/=len(vecs) return np.array([g,b,r]) def main(): #特徴ベクトルの型の定義 vec = namedtuple('vec_info',['GBR','coordinate']) #画像を読み込み img = cv2.imread("sample.png") #画像のサイズ height = img.shape[0] width = img.shape[1] #特徴ベクトルの総数(画素数) num_vec = height*width #各画素の特徴ベクトルを取得する vectors = [] for y in range(height): for x in range(width): BGR = img[y,x] v = vec(BGR,(y,x)) vectors.append(v) vectors = np.array(vectors) feature_vectors = vectors[:,0] #feature_vectors = np.reshape(feature_vectors,(1,len(feature_vectors))) tmp = [] for vec in feature_vectors: tmp.append(vec) feature_vectors = np.array(list(tmp)) #特徴空間の点をプロット feature_vectors_G = feature_vectors[:,0] feature_vectors_B = feature_vectors[:,1] feature_vectors_R = feature_vectors[:,2] #初期プロットの表示 fig = plt.figure() ax = Axes3D(fig) ax.scatter3D(feature_vectors_G,feature_vectors_B,feature_vectors_R) plt.show() #クラスタの個数 num_cluster = 7 #k-means法 km = KMeans(n_clusters=num_cluster, init='random', n_init=10, max_iter=100, tol=1e-04, random_state=0 ) y_km = km.fit_predict(feature_vectors)#y_kmにクラスタの番号が保存される #クラス毎に分類する #vectorsとfeature_vectorsとy_kmは互いに添字が一致 CLUSTER = [[] for _ in range(num_cluster)] for i,v in enumerate(vectors): for which_cluster in range(num_cluster): if y_km[i] == which_cluster: CLUSTER[which_cluster].append(v) #クラス毎にプロットする COLOR = ['b','g','r','c','m','y','k'] CLUSTER_COLOR = [[[],[],[]] for _ in range(num_cluster)] fig = plt.figure() ax = Axes3D(fig) for i,vecs in enumerate(CLUSTER): for j,v in enumerate(vecs): CLUSTER_COLOR[i][0].append(v[0][0]) CLUSTER_COLOR[i][1].append(v[0][1]) CLUSTER_COLOR[i][2].append(v[0][2]) for k in range(3): CLUSTER_COLOR[i][k] = np.array(CLUSTER_COLOR[i][k]) for i in range(len(CLUSTER_COLOR)): ax.scatter(CLUSTER_COLOR[i][0],CLUSTER_COLOR[i][1],CLUSTER_COLOR[i][2]) plt.show() #セントロイドを求める centroids = [[] for _ in range(len(CLUSTER))] for i,vecs in enumerate(CLUSTER): centroids[i] = calc_centroid(vecs) #画像を変換していく for i,vecs in enumerate(CLUSTER): for j,v in enumerate(vecs): img[v[1][0],v[1][1]] = centroids[i] #画像を表示 cv2.imshow("image",img) cv2.waitKey(0)#キーを押すと終了 cv2.destroyAllWindows() #画像を出力 file_name = "res_"+str(len(CLUSTER)) cv2.imwrite(file_name+".jpg",img) if __name__ == '__main__': main()
GBR値の3次元プロットの様子
k-means法で同じ位置にクラスタが出来ているのがわかる.
k-means法は自分で実装するよりfrom sklearn.cluster import KMeansを使うと楽だし正確.
【Python】３Dグラフを自動回転する
3Dグラフを自動で回転させる方法が載ってる.
meganehouser.hatenablog.com
【Jupyter】実行＋下のセル
Shift+Enterでできる！
【Python】【画像処理】画像の画素毎のGBR値を３Dグラフにプロットする
#coding:utf-8 """ $jupyter notebook $for python3.x """ from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans from PIL import Image from PIL import ImageDraw from random import randint from os.path import exists from os import mkdir from math import fabs from random import random from copy import deepcopy from math import log from math import sqrt import cv2 import numpy as np from collections import namedtuple import csv def main(): #特徴ベクトルの型の定義 vec = namedtuple('vec_info',['GBR','coordinate']) #画像を読み込み img = cv2.imread("sample.png") #画像のサイズ height = img.shape[0] width = img.shape[1] #特徴ベクトルの総数(画素数) num_vec = height*width #各画素の特徴ベクトルを取得する vectors = [] for y in range(height): for x in range(width): BGR = img[y,x] v = vec(BGR,(y,x)) vectors.append(v) vectors = np.array(vectors) feature_vectors = vectors[:,0] #feature_vectors = np.reshape(feature_vectors,(1,len(feature_vectors))) tmp = [] for vec in feature_vectors: tmp.append(vec) feature_vectors = np.array(list(tmp)) #特徴空間の点をプロット feature_vectors_G = feature_vectors[:,0] feature_vectors_B = feature_vectors[:,1] feature_vectors_R = feature_vectors[:,2] #初期プロットの表示 fig = plt.figure() ax = Axes3D(fig) ax.scatter3D(feature_vectors_G,feature_vectors_B,feature_vectors_R) plt.show() if __name__ == '__main__': main()
ライブラリは適当
グラフを動かせるようにしたい.
【追記】
デフォルトで回転できるようになってた.
【python】画像表示
jupyterで画像の読み込みするときに便利
from PIL import Image im = Image.open("./img_0.jpg") im.show()
【Python】【機械学習】3次元モデルのk-means
#for python3.6 from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np from sklearn.cluster import KMeans #サンプルを定義 a = [0.0,0.0,0.0] b = [0.1,0.1,0.1] c = [1.0,1.0,1.0] d = [0.9,0.8,0.7] e = [1.0,0.0,0.0] f = [0.9,0.1,0.1] dots = np.array([a,b,c,d,e,f]) X = dots[:,0]#各サンプルのx座標 Y = dots[:,1] Z = dots[:,2] #初期プロットの表示 fig = plt.figure() ax = Axes3D(fig) ax.scatter3D(X,Y,Z) plt.show() #クラスタの個数 num_cluster = 3 #k-means法 km = KMeans(n_clusters=num_cluster, init='random', n_init=2, max_iter=100, tol=1e-04, random_state=0 ) y_km = km.fit_predict(k)#y_kmにクラスタの番号が保存される #クラスタ毎に分類 CLUSTER = [[[],[],[]] for _ in range(num_cluster)] for i,v in enumerate(dots):#各ベクトルに対して for j in range(len(y_km)):#分類ラベルに対して if y_km[i] == j:#分類ラベルがjだったら CLUSTER[j][0].append(v[0])#クラスタjのx座標にベクトルvのx座標を入れる CLUSTER[j][1].append(v[1]) CLUSTER[j][2].append(v[2]) #グラフを描画 fig = plt.figure() ax = Axes3D(fig) for i,c in enumerate(CLUSTER):#各クラスタ毎に x,y,z = c[0],c[1],c[2]#x,y,z座標 ax.scatter3D(x,y,z) plt.show()
というように分類される.
【Python】3次元モデルのプロット
from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np x = np.arange(-3,3,0.25) y = np.arange(-3,3,0.25) X,Y = np.meshgrid(x,y) Z = np.sin(X) + np.cos(Y) fig = plt.figure() ax = Axes3D(fig) ax.plot_wireframe(X,Y,Z) plt.show()
散乱図のプロット
from mpl_toolkits.mplot3d import Axes3D import matplotlib.pyplot as plt import numpy as np a = [0.0,0.0,0.0] b = [0.1,0.1,0.1] c = [1.0,1.0,1.0] d = [0.9,0.8,0.7] e = [1.0,0.0,0.0] f = [0.9,0.1,0.1] k = np.array([a,b,c,d,e,f]) X = k[:,0] Y = k[:,1] Z = k[:,2] fig = plt.figure() ax = Axes3D(fig) ax.scatter3D(X,Y,Z) plt.show()
X=k[:,0]のように記述できるのは
k = array([[・,・,・],
[・,・,・],
..........,
[・,・,・]])のような形をしているからである.
k-means++法
k-means法ではセントロイドの初期値が不適切である場合, クラスタリングが上手く行かなかったり収束に時間がかかる場合がある.
この問題の対策としては
k-means++法での初期化
- 選択の対象となるk個のセントロイドを格納するために空のデータセットMを初期化する
- 入力サンプルから初期のセントロイド
をランダムに選択しMに割り当てる
- Mに含まれていないサンプル
ごとにMのセントロイドに対して距離の2乗が最小となるセントロイドを求める
- 次のセントロイド
をランダムに選択するには各サンプルの距離の重みを等しく以下の確立分布を使用する
- k個のセントロイドが選択されるまでステップ3-4を繰り返す
- 従来のk-means法を使って引き続き処理を行う
【Python】【スクレイピング】HTMLデータのスクレイピング
import urllib.request url = 'http://umashika5555.hatenablog.com/' response = urllib.request.urlopen(url) data = response.read() decoded_data = data.decode('utf_8') print(decoded_data)
import urllib.request import bs4 url = 'http://umashika5555.hatenablog.com/' soup = bs4.BeautifulSoup(urllib.request.urlopen(url).read()) print(str(soup))
【ネットワーク】お勉強19
フロー制御はTCPのプロトコルで, 相手のバッファが溢れないようにするもの.
相手のバッファに溜まっている量を見て満杯そうだったらあまり送らないようにする.
逆に空いているときは一気に送りつける.
一気に送りつけれる量のことをウィンドウサイズという.
TCPではスロースタートアルゴリズムを用いる.
これはルータなど中継するデバイスは基本的に第3層以下の運ぶことを目的にできているので, ホスト側から処理する.
ホスト計算機は閾値まで指数的に送るデータを増やしていき, 閾値になったら徐々にデータを増やしていく.
一度にたくさん送ると渋滞するかもしれないので様子を見ている.
輻輳が発生した場合, 確認応答が1つでも帰ってこなかった場合,いったん送る数を減らす.
TCPではフロー制御でバッファオーバーフローをスロースタートアルゴリズムで輻輳制御をしている!!!
TCPまとめ
スリーウェイハンドシェイクでコネクションを確率.
コネクションを確立して互いに確実に送受信ができることを示す.
送るときはフロー制御と輻輳制御を行う.
パケットの破棄が起きないように確実に送るため.
【Ubuntu】ショートカット
Alt+Tabでアプリケーションウィンドウの切り替えが便利
ubuntu.hatenablog.jp
【Python】【OpenCV】n*m のランダムな色の画像を作成
# vim: set fileencoding=utf-8 : import numpy as np import cv2 from random import randint import numpy as np cols = 320 rows = 320 #イメージ生成 image = np.zeros((rows, cols, 3), np.uint8) div = 16 # 縦横の分割数 w = cols / div # 分割された領域の横幅 h = rows / div # 分割された領域の縦幅 for segrow in xrange(div): y1 = segrow * h # 分割領域上 y2 = y1 + h # 分割領域下 for segcol in xrange(div): x1 = segcol * w #分割領域左 x2 = x1 + w #分割領域右 b = randint(0,255) g = randint(0,255) r = randint(0,255) c1 = np.array([b,g,r]) #(x1,y1)-(x2,y2)の矩形を塗りつぶす image[y1:y2, x1:x2] = c1 # 表示して[ESC]が押されるまで待つ cv2.imshow("image", image) while cv2.waitKey(33) != 27: pass
