Rustで画像から輪郭抽出と塗りつぶしを行う

はじめに

以前から、Rustのimage crateを使用して画像の二値化などいろいろな処理の実装を行ってきました。 今回は二値化した白黒画像を使って白色部分の輪郭を抽出し、 その輪郭を別の色で塗りつぶす処理をRustを使用して行います。

今回作成したコードは https://gist.github.com/tk87s/ec42fd517697ed3507ac3ae7ec4a6715 にあります

輪郭抽出用サンプルとして以下の画像を使用します。

輪郭抽出

輪郭抽出はまず輪郭としたい目的の色にたどり着くまでラスタスキャンを行います。 二値化画像の場合は白(輝度255)か黒色(輝度0)を見つければいいのですが、ここでは輪郭抽出したい色を白色とします。 白色が見つかると、そこは必ず白と黒の境界となっているはずなので、その画素は輪郭の一部です。 ここから輪郭をトレースしていきます。

輪郭をトレースするのにはどこが隣接画素であるかの定義が必要ですが、ここではムーア近傍の8画素とします。 まず最初に見つかった白色画素の左下$(dx,dy)=(-1,1)$から8近傍を反時計周りで探索し、最初に白色が見つかったらそれを次の画素とします。 その画素もラスタスキャンの性質上必ず輪郭の一部となっているはずです。 正式には隣接同士の二つの白色画素を見つけて、その隣接している方向を取得する必要がありますが、今回は簡略化しています。

次の画素が見つかれば、進んだ向きを記録しておき次の8近傍の探索開始地点に使用します。 次の探索開始地点は前回に進んだ向きから時計回りに2方向先(反時計回りに6方向先)の近傍地点になります。 その開始地点から反時計回りに8近傍を探索することで、最初に見つかった白色画素が次トレースすべき輪郭の一部になっていることが保証されます。

上記を繰り返せばスタート地点に戻ってくるはずなので、それまでの軌跡が輪郭となり抽出が完了します。

    
let taps = [
    (1usize,0usize), (1,!0), (0,!0), (!0,!0),
    (!0,0), (!0,1), (0,1), (1,1)
];
 
let (w, h) = img.dimensions();
let mut cont_img = image::ImageBuffer::new(w, h);
let (w, h) = (w as usize, h as usize);
let mut used = vec![vec![false; w]; h];
 
let mut contours = vec![];
for r in 0..h {
    for c in 0..w {
 
        if let image::Luma([0]) = img.get_pixel(c as u32, r as u32) {continue;}
        if used[r][c] {continue;}
 
        let mut conts = VecDeque::new();
        conts.push_back((r, c));
 
        cont_img.put_pixel(c as u32, r as u32, image::Luma([255u8]));
        let mut curpos = (r,c,7);
        
        loop {
            let mut nextpos = (r,c,8);
            for dir in 0..8 {
                let id = (curpos.2 + 6 + dir)&7;
                let ny = curpos.0 + taps[id].1;
                let nx = curpos.1 + taps[id].0;
                if ny >= h || nx >= w {continue}
                if let image::Luma([0]) = img.get_pixel(nx as u32, ny as u32) {continue;}
                
                nextpos = (ny, nx, id);
                cont_img.put_pixel(nx as u32, ny as u32, image::Luma([255u8]));
                conts.push_back((ny,nx));
                break;
            }
 
            if nextpos.2 == 8 {
                conts.clear();
                break;
            }
            if nextpos.0 == r && nextpos.1 == c {
                break;
            }
            
            curpos = nextpos;
        }
        
        let mut sub_conts = vec![];
        for &(y,x) in conts.iter() {
            used[y][x] = true;
            sub_conts.push((x, y));
        }
 
        contours.push(sub_conts);
    }
}
Copy

さらに別の輪郭を探すためにさらにスキャンを行いますが、その際すでに抽出した輪郭の内部の白色連結部分を対象から外すため、 それらを探索して除外しておきます。

    
while let Some((y, x)) = conts.pop_front() {
    for &(dx, dy) in taps.iter() {
        let ny = y + dy;
        let nx = x + dx;
        if ny >= h || nx >= w || used[ny][nx] {continue;}
        if let image::Luma([0]) = img.get_pixel(nx as u32, ny as u32) {continue;}
        
        used[ny][nx] = true;
        conts.push_back((ny,nx));
    }
}
Copy

実際に抽出した画像は以下になります。

塗りつぶし(polygon fill color)

先ほどの輪郭抽出で得られた輪郭を使用して、塗りつぶしを行います。 塗りつぶし自体はRustのplotters crateなどを使用すれば可能ですが、今回はcrateなしで実装します。 ここではグレースケールの画像に輝度127の灰色で塗りつぶしを行いますが、カラー画像で任意の色を塗りつぶすことも可能です。

輪郭内部の画素を取得する方法としては、ScanLine Algorithmを使用します。

Scanline rendering: https://en.wikipedia.org/wiki/Scanline_rendering

画像のy座標のスキャンライン(x軸との平行線)と輪郭線との交点のx座標を取得し、 取得したx座標を昇順でソートすると最初から0-indexedで数えて偶数index区間は輪郭の内部となります。 あとはその輪郭の内部を任意の色で塗ればOKです。

今回は輪郭の全画素を取得しているので、輪郭各頂点のx座標を交点とすれば問題ありませんが、 例えば多角形の頂点のみを入力した場合、辺とスキャンラインの交点のx座標を計算する必要がありますが、 これはy座標が固定されているので1次方程式を解くだけです。 ただ交点の算出時にスキャンラインのy座標を、画素の中央、上端または下端に設定するか選択する必要はあります。 たとえば画像で5行目のスキャンラインを見る場合、y座標は $4,4.5,5$ などの選択肢があります。

    
fn polyfill_gray(img: &mut GrayImage, conts: &Vec<(usize, usize)>) {
    let h0 = *conts.iter().map(|(_,y)| y).min().unwrap();
    let h1 = *conts.iter().map(|(_,y)| y).max().unwrap(); 
    for r in h0..=h1 {
        let mut cols: Vec = conts.windows(2)
                                        .filter(|p| p[0].1 <= r && p[1].1 > r || p[0].1 > r && p[1].1 <= r)
                                        .map(|p| p[0].0)
                                        .collect();
        cols.sort();
 
        for c in cols.chunks(2) {
            if c.len() < 2 {continue;}
            for x in c[0]..=c[1] {
                img.put_pixel(x as u32, r as u32, image::Luma([127u8]));
            } 
        }
    }
}
Copy

まとめ

白色領域の端から適切に反時計回りに8近傍探索を行いながら輪郭をトレースすることで、輪郭の抽出をすることができました。 また、Scanline Algorithmを使用して輪郭線とx軸の平行線との交点から、輪郭の内部を識別して内部を塗りつぶすことができました。

Reference

1. https://en.wikipedia.org/wiki/Scanline_rendering