编程解决问题 BMP图片连通


题:
BMP是常见的图像存储格式。
如果用来存黑白图像(颜色深度=1),则其信息比较容易读取。

与之相关的数据:

(以下偏移均是从文件头开始)
偏移:10字节, 长度4字节: 图像数据真正开始的位置。
偏移:18字节, 长度4字节: 位图的宽度,单位是像素。
偏移:22字节, 长度4字节: 位图的高度,单位是像素。

从图像数据开始处,每个像素用1个二进制位表示。
从图片的底行开始,一行一行向上存储。

Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数,
不足的位均以 0 填充。例如,图片宽度为45像素,实际上每行会占用
8个字节。

可以通过Windows自带的画图工具生成和编辑二进制图像。
需要在“属性”中选择“黑白”,指定为二值图像。
可能需要通过查看 | 缩放 | 自定义... 把图像变大比例一些,
更易于操作。

图像的左下角为图像数据的开始位置。白色对应1,黑色对应0

我们可以定义:两个点距离如果小于2个像素,则认为这两个点连通。
也就是说:以一个点为中心的九宫格中,围绕它的8个点与它都是连通的。
如:t1.bmp 所示,左下角的点组成一个连通的群体;
而右上角的点都是孤立的。

程序的目标是:根据给定的黑白位图,分析出所有独立连通的群体,输出每个连通群体的面积。所谓面积,就是它含有的像素的个数。

输入数据固定存在in.bmp中。

如示例的in.bmp,
程序应该输出:
12
81
52
133

该输出表示:共有4个连通群体。
输出的连通体面积间的顺序可以随意。

请编程解决上述问题。

我们测试程序的时候,会使用不同的in.bmp文件。

源码BMPGame.java
BMP文件

bmp game
bmp game


import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;


public class BMPGame {
    
    private static int t(int i, int k, int w, int h, boolean[][][] x) {
        if (i<0 || i>=w || k<0 || k>=h) {
            return 0;
        }
        if (x[i][k][1]) {
            return 0;
        }
        x[i][k][1] = true;
        if (x[i][k][0]) {
            return t(i-1, k-1, w, h, x) + t(i+1, k-1, w, h, x) +
                    t(i-1, k+1, w, h, x) + t(i+1, k+1, w, h, x) + 
                    t(i, k-1, w, h, x) + t(i, k+1, w, h, x) + 
                    t(i-1, k, w, h, x) + t(i+1, k, w, h, x) + 1;
        }
        else {
            return 0;
        }
    }
    
    public static void main(String args[]) throws IOException {
        
        long st=System.currentTimeMillis();
        
        String path = "/Users/Tro/Desktop/t.bmp";
        File f = new File(path);
        BufferedImage b = ImageIO.read(f);
        int w = b.getWidth();
        int h = b.getHeight();
        boolean[][][] x = new boolean[w][h][2];
    
        
        for (int i=0; i<w; i++) {
            for (int k=0; k<h; k++) {
                x[i][k][0] = (b.getRGB(i, k)==-1)? false: true;
            }
        }
    
        for (int i=0; i<w; i++) {
            for (int k=0; k<h; k++) {
                int r = t(i, k, w, h, x);
                if (r>1) {
                    System.out.println(r);
                }
            }
        }
        
        long ed=System.currentTimeMillis();
        System.out.println(ed-st);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注