ラスター画像をトレースして SVG にする試み
Vector Graphics を扱うアプリを書いているのだが、 普通の raster 画像のインポートをサポートしたい。
関連しそうな技術を調べてみると テキストから画像を生成するAIで、 ベクターデータを生成するものがあった。
これはすごいが、今のところはラスター画像をSVGに変換できればそれでよい。 さらに調べてみたところ potrace というものが存在していた。
このように白黒の raster 画像をベクターデータに変換するツールです。
ここでは、以下の potrace のドキュメントを参考にしつつ raster to vector 変換の自前実装をつくります。
potrace は OSS でソースコードが提供されています。 いろいろなプログラム言語へ移植もされていますので、 成果だけ必要な方は、そちらをご利用ください。
単純な例で考える
この単純なラスタ画像（白黒）をベクターデータにすることを考えます。
これをベクター情報に変えるために、 黒の部分の縁をトレースすることを考えます。 「縁」を把握するための方法は、2x2 の４つのピクセルを見て、 全部が「白」または全部が「黒」だったら、縁ではない。 それ以外のケースでは「縁」である、と考えます。
つまり、たとえば以下の赤で囲んだ４つのピクセルは全部白なので「縁」ではない。
以下の４つのピクセルは、白と黒のピクセルが両方含まれているから「縁」である。
このように、「縁」である４つのピクセル（これを以後「ウインドウ」と呼ぶ）を見つけたら、ウインドウを順に上下左右いずれかにスライドしながら時計まわりで「縁」から「縁」に移動していき、最初にスタートしたウインドウ位置に戻ったら、一つの塊をベクター化したことになる。
・・・という考え方です。
実際にやってみます。
ウインドウを順に 右、右、下、右、下、下、左、左、上、左、上、上にスライドさせると元の位置に戻る。
これで概ね察しがつくと思いますが、ウインドウの状態によって「上下左右」のうちでスライドする方向は限定されます。２つとも白ピクセルまたは２つとも黒ピクセルが残る方向へ移動するのは悪手で（なぜなら移動した先が全部「白」または全部「黒」の縁でないウインドウ位置に来てしまう可能性があるから）、移動しても必ずまた「縁」になるスライド方向は自ずと限定されます。 これに加えて、縁のたどり方を時計回りにするという制約を加えることで、移動する方向はひとつの決まります。スタート地点とする「縁」ウインドウをきめれば、その次のウインドウ、またその次のウインドウが確定していき、最終的にもとのウインドウに戻るまで移動を繰り返すことで、この黒ピクセルの塊の「縁」をトレースすることができます。
もっとも、現在の例では出現しませんが、 以下のようなウインドウに遭遇する可能性はあります。
この場合、先に説明したロジックで移動方向を判定しても、移動する方向が一つに決まりません。 ただし、その場合でも一つ前の移動方向を考慮しすれば、次に移動する方向を一つに決めることができます（たぶん）。
実装する
それでは、本当にこの発想で、トレースできるか確かめるため作動するコードを書きます。 言語は TypeScript を使用します。
上記に例示した通りで考えると、 ウインドウ位置 (0,0)..(1,1) は「縁」のウインドウなので、これをスタート地点と決めます。
＜状態１＞
このとき、ウインドウを上下左右のいずれかに一つ移動させたときに、 必ずまた「縁」のウインドウになり得る移動方向は、「右」または「下」です。今は、時計回りにパースすると決めているので、移動方向は「右」に決定です。
＜状態２＞
このときは、「縁」をキープする移動方向は「左」または「右」だが、時計回りにパースしているので「右」に決定。
以下、同様に判断していくと、（この例であれば）すべて現在のウインドウ状態から、次に移動する方向が一意に決定できます。
これをどのようにコードで表現するか、という問題ですが、次のようにします。
ピクセルを 0 or 1 で表現し、画像は 二次元配列で表現します。
type Pixel = 0 | 1
type Image = Array<Array<Pixel>>// height x width (行列)
const image: Image = [
[0,0,0,0,0],
[0,1,1,0,0],
[0,1,1,1,0],
[0,0,1,1,0],
[0,0,0,0,0]]
そして、ウインドウは４つのピクセルとして表現します。
// [leftTopPixel, rightTopPixel, leftBottomPixel, rightBottomPixel]
type Window = [Pixel, Pixel, Pixel, Pixel]
ウインドウ状態の種類(WindowKind)は全部で16パターンあるので以下のように表現します。 便宜上 WindowKind の種類に 'UNKNOWN' を追加しています。
type WindowKind =
'0000' | '0001' | '0010' | '0011' |
'0100' | '0101' | '0110' | '0111' |
'1000' | '1001' | '1010' | '1011' |
'1100' | '1101' | '1110' | '1111' | 'UNKNOWN'
そして、現在のウインドウ状態から次にどの方向に移動するかを表現するために Direction を定義します。 全部白や全部黒のウインドウパターン(WindowKind)だったり、一意に方向が決定できない場合を表現するために、 'UNKNOWN' と 'ERROR' も追加。
type Direction = 'left' | 'up' | 'right' | 'down' | 'UNKNOWN' | 'ERROR'
最後に、現在のウインドウからどの方向へ移動するか決定する関数 next を定義したい。 次のようなシグニチャを持つ関数です。
const next = (current: Window): Direction => {}
その前に補助関数として、Window を WindowKind に変換する toWindowKind を定義します。
const toWindowKind = (window: Window): WindowKind => {
return `${window[0]}${window[1]}${window[2]}${window[3]}`
}
それでは、現在のウインドウから次の移動方向を決定する関数 next を定義します。
const next = (current: Window): Direction => {
switch (toWindowKind(current)) {
case '0000': return 'ERROR'
case '0001': return 'right'
case '0010': return 'down'
case '0011': return 'right'
case '0100': return 'up'
case '0101': return 'up'
case '0110': return 'UNKNOWN'
case '0111': return 'up'
case '1000': return 'left'
case '1001': return 'UNKNOWN'
case '1010': return 'down'
case '1011': return 'right'
case '1100': return 'left'
case '1101': return 'left'
case '1110': return 'down'
case '1111': return 'ERROR'
case 'UNKNOWN': return 'ERROR'
}
}
'0000', '1111' のように「縁」でないウインドウがきた場合は、'ERROR' を返します。 そのほか、'0110', '1001' のように一意に方向が決定できない場合は、（今のところ） 'UNKNOWN' を返します。
それでは、この next 関数を使ってみます。 たとえば、現在の画像の例の (0,0)..(1.1) の位置にあるウインドウに対して、次の移動方向を計算してみます。
const window00: Window = [0,0,0,1]
console.log( next(window00) ) // right
実行してみます。（とりあえず deno を使います。）
$ deno run --check index.ts
right
うまくいきました。
あとは、画像の座標を指定して、画像からウインドウを作り出す関数 toWindow を定義しましょう。
type XIndex = number
type YIndex = number
interface Point {
x: XIndex,
y: YIndex
}
const toPoint = (x: XIndex, y: YIndex): Point => { return {x:x, y:y} }
const toWindow = (image: Image, pt: Point): Window => {
const x = pt.x
const y = pt.y
return [
image[y][x],
image[y][x+1],
image[y+1][x],
image[y+1][x+1]]
}
指定する座標はウインドウの 左上のピクセル位置 です。
これで「縁」をトレースするためのすべての関数が用意できました。
再帰関数 trace でスタート地点となるウインドウから順に「縁」を移動していき元のスタート位置に戻るまで繰り返します。 再帰関数 trace はこんなシグニチャを持ちます。
const trace = (image: Image, startPoint: Point, current: PointAndWindow, acc: Array<Point>): Array<Point> => {}
対象画像 image とトレース開始地点 startPoint 現在トレース中の位置とウインドウ current そしてトレース位置を蓄積する変数 acc です。
この関数を実装する前に、補助関数 toNextPointAndWindow を定義します。 これは、現在の位置とウインドウから次の位置とウインドウを返す関数です。
type PointAndWindow = [Point, Window]
const toNextPointAndWindow = (current: PointAndWindow): PointAndWindow => {
const currentPoint = current[0]
const currentX = currentPoint.x
const currentY = currentPoint.y
const currentWindow = current[1]
switch( next(currentWindow) ){
case 'left' :
const leftPt = toPoint(currentX-1, currentY)
const leftW = toWindow(image, leftPt)
return [leftPt, leftW]
case 'up' :
const upPt = toPoint(currentX, currentY-1)
const upW = toWindow(image, upPt)
return [upPt, upW]
case 'right' :
const rightPt = toPoint(currentX+1, currentY)
const rightW = toWindow(image, rightPt)
return [rightPt, rightW]
case 'down' :
const downPt = toPoint(currentX, currentY+1)
const downW = toWindow(image, downPt)
return [downPt, downW]
default :
return current
}
}
toNextPointAndWindow の switch case の default で current を返しています。 next 関数は left, up, right, down のいずれかが正常な状態では返ります。 しかし、想定外の場合（ つまり unknonw , error の場合）は、この関数は current を返すことになります。 これは暫定的な振る舞いなので注意してください。
それでは、補助関数 toNextPointAndWindow を使って、再帰関数 trace を定義します。
const trace = (image: Image, startPoint: Point, current: PointAndWindow, acc: Array<Point>): Array<Point> => {
const currentPoint = current[0]
if( startPoint.x==currentPoint.x && startPoint.y==currentPoint.y ){
return acc
} else {
const nextAcc = acc.concat(current[0])
const nextPointAndWindow = toNextPointAndWindow(current)
return trace(image, startPoint, nextPointAndWindow, nextAcc)
}
}
再帰関数なので、大きな画像に対して処理すればスタックオーバーフローが起きるかも。 今はその問題はないこととして進めます。
再帰終了の条件は、元の位置に戻ってきた時です。 それ以外の場合は、現在の（位置と）ウインドウから次の（位置と）ウインドウを探して、再帰的にトレースを実行します。 もちろん、再帰のたびに、結果の位置情報を acc に蓄積していきます。
それでは、この trace 関数を使って、実際にトレースしてみます。
スタート地点となるウインドウは (0,0)..(1,1) 決めうちで（今のところは）よいとしましょう。
const image: Image = [
[0,0,0,0,0],
[0,1,1,0,0],
[0,1,1,1,0],
[0,0,1,1,0],
[0,0,0,0,0]]
const startPoint: Point = toPoint(0,0)
const startOne: PointAndWindow = [startPoint, toWindow(image, startPoint)]
const nextOne = toNextPointAndWindow( startOne )
const pointList = trace(image, startPoint, nextOne, [startPoint])
console.log(pointList)
実行してみます。
$ deno run --check index.ts
[
{ x: 0, y: 0 }, { x: 1, y: 0 },
{ x: 2, y: 0 }, { x: 2, y: 1 },
{ x: 3, y: 1 }, { x: 3, y: 2 },
{ x: 3, y: 3 }, { x: 2, y: 3 },
{ x: 1, y: 3 }, { x: 1, y: 2 },
{ x: 0, y: 2 }, { x: 0, y: 1 }
]
この図形をトレースできました。
SVGにする
トレースして得られた点の集合からSVGを生成して、本当に意図通りトレースできたか確認します。
トレース結果として得られた点は、ウインドウの左上の座標です。SVGに変換するにあたっては、これをウインドウの中央の点に変換してから使います。 変換といっても x, y それぞれ +1 するだけです。
const svgPointList = pointList.map((pt)=> toPoint(pt.x+1, pt.y+1))
SVGのパスコマンドを生成。
const head = (arr: Array<Point>): Point => { return arr[0] }
const tail = (arr: Array<Point>): Array<Point> => { return arr.slice(1) }
const headPt = head(svgPointList)
const tailPts = tail(svgPointList)
const cmd = `M ${headPt.x},${headPt.y}` + tailPts.map( (pt)=> `L ${pt.x},${pt.y}` ).join(' ') + 'z'
const pathElement = `<path d=\"${cmd}\"/>`
SVGのヘッダフッダ部分などをつけて完成させる。
const w = image[0].length // 5
const h = image.length // 5
const svg = [
'<?xml version="1.0" encoding="utf-8"?>',
'\n',
'<!DOCTYPE svg PUBLIC ',
'"-//W3C//DTD SVG 1.1//EN" ',
'"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">',
'\n',
'<svg ',
'xmlns="http://www.w3.org/2000/svg" version="1.1" ',
`x="0px" y="0px" width="${w}px" height="${h}px" `,
`viewBox="0.0 0.0 ${w} ${h}">`,
'<g stroke="rgb(0,0,0)" stroke-width="0.254" fill="none">',
pathElement,
'</g>',
'</svg>'].join('')
await Deno.writeTextFile('./polygon.svg', svg)
実行してSVGファイルを生成。
$ deno run --allow-write --check index.ts
生成された polygon.svg を拡大した画像
意図通りパースできたようです。
別の画像を試してみましょう。
const image: Image = [
[0,0,0,0,0,0,0,0],
[0,1,1,0,0,0,0,0],
[0,0,1,1,1,0,0,0],
[0,0,1,1,1,1,1,0],
[0,0,1,1,1,0,0,0],
[0,1,1,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]
変換！
うまくいきました。
スタート地点のウインドウを自動で決定する
上記例は、(0,0)..(1.1) の位置のウインドウが「縁」であったため、スタートとするウインドウを決め打ちで作動していたが、 もしそうでないラスター画像をトレースしようとしたら意図通り作動しない。
そこで、対象とするラスター画像から「縁」にあたるウインドウを見つける機能を追加します。 toAllPointAndWindowList と toAllEdgePointAndWindowList 関数です。
toAllPointAndWindowList 関数は、与えられた画像に含まれるすべての（位置と）ウインドウを返します。
const toAllPointAndWindowList = (image: Image): Array<PointAndWindow> => {
const range = (v: number)=>{ return [...Array(v).keys()] }
const w = image[0].length
const h = image.length
return range(h-1).map((yIndex)=> {
return range(w-1).map((xIndex)=> {
const p = toPoint(xIndex, yIndex)
const w = toWindow(image, p)
const pAndW: PointAndWindow = [p, w]
return pAndW
})
}).flat()
}
toAllEdgePointAndWindowList 関数は、「縁」である（位置と）ウインドウだけのリストにして返します。
const toAllEdgePointAndWindowList = (image: Image): Array<PointAndWindow> => {
return toAllPointAndWindowList(image).filter((pAndW)=> {
const windowKind = toWindowKind(pAndW[1])
switch( windowKind ) {
case 'UNKNOWN' :
case '0000' :
case '1111' :
case '0110' :
case '1001' :
return false
default:
return true
}
})
}
これを使ってスタート地点を計算するには以下のようにします。
const startPointAndWindow = toAllEdgePointAndWindowList(image)[0]
const startPoint = startPointAndWindow[0]
それでは、(0,0)..(1,1) の位置のウインドウが 「縁」ではない ラスター画像を使って、実際に機能するか確かめます。
const image: Image = [
[0,0,0,0,0,0,0,0],
[0,0,0,1,1,0,0,0],
[0,0,1,1,1,1,0,0],
[0,1,1,1,1,1,1,0],
[0,1,1,1,1,1,1,0],
[0,0,1,1,1,1,0,0],
[0,0,0,1,1,0,0,0],
[0,0,0,0,0,0,0,0]]
実行してできた画像を確認します。
うまくいきました。
まだ一番外側はピクセルは必ず 0 でないと意図通り作動しないなど、このコードの改善すべき点は多い。 そもそも、ポリゴンが２つあったらどうする、とか。
まとめ
これで、ごく単純な白黒画像の一つだけ存在するポリゴンの縁をパースできるようになりました。 より複雑かつ実践的なラスター画像をベクター画像にするにはまだここから長い道程があるのですが、 それは機会があれば。
例によって最後にコードを掲載します。
使用した deno のバージョンはこちら。
$ deno --version
deno 1.35.3 (release, x86_64-unknown-linux-gnu)
v8 11.6.189.12
typescript 5.1.6
コード。
type Pixel = 0 | 1
type Image = Array<Array<Pixel>>// height x width (行列)
type Window = [Pixel, Pixel, Pixel, Pixel] // [leftTopPixel, rightTopPixel, leftBottomPixel, rightBottomPixel]
type WindowKind =
'0000' | '0001' | '0010' | '0011' |
'0100' | '0101' | '0110' | '0111' |
'1000' | '1001' | '1010' | '1011' |
'1100' | '1101' | '1110' | '1111' | 'UNKNOWN'
type Direction = 'left' | 'up' | 'right' | 'down' | 'UNKNOWN' | 'ERROR'
const toWindowKind = (window: Window): WindowKind => {
return `${window[0]}${window[1]}${window[2]}${window[3]}`
}
const next = (current: Window): Direction => {
switch (toWindowKind(current)) {
case '0000': return 'ERROR'
case '0001': return 'right'
case '0010': return 'down'
case '0011': return 'right'
case '0100': return 'up'
case '0101': return 'up'
case '0110': return 'UNKNOWN'
case '0111': return 'up'
case '1000': return 'left'
case '1001': return 'UNKNOWN'
case '1010': return 'down'
case '1011': return 'right'
case '1100': return 'left'
case '1101': return 'left'
case '1110': return 'down'
case '1111': return 'ERROR'
case 'UNKNOWN': return 'ERROR'
}
}
type XIndex = number
type YIndex = number
interface Point {
x: XIndex,
y: YIndex
}
const toPoint = (x: XIndex, y: YIndex): Point => { return {x:x, y:y} }
const toWindow = (image: Image, pt: Point): Window => {
const x = pt.x
const y = pt.y
return [
image[y][x],
image[y][x+1],
image[y+1][x],
image[y+1][x+1]]
}
type PointAndWindow = [Point, Window]
const toNextPointAndWindow = (current: PointAndWindow): PointAndWindow => {
const currentPoint = current[0]
const currentX = currentPoint.x
const currentY = currentPoint.y
const currentWindow = current[1]
switch( next(currentWindow) ){
case 'left' :
const leftPt = toPoint(currentX-1, currentY)
const leftW = toWindow(image, leftPt)
return [leftPt, leftW]
case 'up' :
const upPt = toPoint(currentX, currentY-1)
const upW = toWindow(image, upPt)
return [upPt, upW]
case 'right' :
const rightPt = toPoint(currentX+1, currentY)
const rightW = toWindow(image, rightPt)
return [rightPt, rightW]
case 'down' :
const downPt = toPoint(currentX, currentY+1)
const downW = toWindow(image, downPt)
return [downPt, downW]
default :
return current
}
}
const trace = (image: Image, startPoint: Point, current: PointAndWindow, acc: Array<Point>): Array<Point> => {
const currentPoint = current[0]
if( startPoint.x==currentPoint.x && startPoint.y==currentPoint.y ){
return acc
} else {
const nextAcc = acc.concat(current[0])
const nextPointAndWindow = toNextPointAndWindow(current)
return trace(image, startPoint, nextPointAndWindow, nextAcc)
}
}
const toAllPointAndWindowList = (image: Image): Array<PointAndWindow> => {
const range = (v: number)=>{ return [...Array(v).keys()] }
const w = image[0].length
const h = image.length
return range(h-1).map((yIndex)=> {
return range(w-1).map((xIndex)=> {
const p = toPoint(xIndex, yIndex)
const w = toWindow(image, p)
const pAndW: PointAndWindow = [p, w]
return pAndW
})
}).flat()
}
const toAllEdgePointAndWindowList = (image: Image): Array<PointAndWindow> => {
return toAllPointAndWindowList(image).filter((pAndW)=> {
const windowKind = toWindowKind(pAndW[1])
switch( windowKind ) {
case 'UNKNOWN' :
case '0000' :
case '1111' :
case '0110' :
case '1001' :
return false
default:
return true
}
})
}
const head = (arr: Array<Point>): Point => { return arr[0] }
const tail = (arr: Array<Point>): Array<Point> => { return arr.slice(1) }
/*
const image: Image = [
[0,0,0,0,0],
[0,1,1,0,0],
[0,1,1,1,0],
[0,0,1,1,0],
[0,0,0,0,0]]
*/
/*
const image: Image = [
[0,0,0,0,0,0,0,0],
[0,1,1,0,0,0,0,0],
[0,0,1,1,1,0,0,0],
[0,0,1,1,1,1,1,0],
[0,0,1,1,1,0,0,0],
[0,1,1,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]
*/
const image: Image = [
[0,0,0,0,0,0,0,0],
[0,0,0,1,1,0,0,0],
[0,0,1,1,1,1,0,0],
[0,1,1,1,1,1,1,0],
[0,1,1,1,1,1,1,0],
[0,0,1,1,1,1,0,0],
[0,0,0,1,1,0,0,0],
[0,0,0,0,0,0,0,0]]
const startPointAndWindow = toAllEdgePointAndWindowList(image)[0]
const startPoint = startPointAndWindow[0]
//const startPoint: Point = toPoint(0,0)
const startOne: PointAndWindow = [startPoint, toWindow(image, startPoint)]
const nextOne = toNextPointAndWindow( startOne )
const pointList = trace(image, startPoint, nextOne, [startPoint])
const svgPointList = pointList.map((pt)=> toPoint(pt.x+1, pt.y+1))
const headPt = head(svgPointList)
const tailPts = tail(svgPointList)
const cmd = `M ${headPt.x},${headPt.y}` + tailPts.map( (pt)=> `L ${pt.x},${pt.y}` ).join(' ') + 'z'
const pathElement = `<path d=\"${cmd}\"/>`
const w = image[0].length
const h = image.length
const svg = [
'<?xml version="1.0" encoding="utf-8"?>',
'\n',
'<!DOCTYPE svg PUBLIC ',
'"-//W3C//DTD SVG 1.1//EN" ',
'"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">',
'\n',
'<svg ',
'xmlns="http://www.w3.org/2000/svg" version="1.1" ',
`x="0px" y="0px" width="${w}px" height="${h}px" `,
`viewBox="0.0 0.0 ${w} ${h}">`,
'<g stroke="rgb(0,0,0)" stroke-width="0.254" fill="none">',
pathElement,
'</g>',
'</svg>'].join('')
await Deno.writeTextFile('./polygon.svg', svg)
以上です。