第一个实时检测图像上人脸的算法由 Paul Viola 和 Michael Jones 于 2001 年开发。该算法的一部分是计算 Haar 特征的过程。作为这项任务的一部分,我们考虑这个概念的简化模型。
让我们考虑一个用大小为 n × m 的表格表示的矩形图像。表元素是指定图像中每个像素的亮度的整数。
一个特征也是一个大小为 n × m 的矩形桌子。特征的每个单元都被漆成黑色或白色。
要计算给定图像上给定特征的值,您必须执行以下步骤。首先,将特征表放在图像表上(没有旋转或反射),因此每个像素完全被黑色或白色单元覆盖。图像中某个特征的值是 W - B 的值,其中 W 是图像中被白色特征单元覆盖的像素的总亮度,B 是被黑色特征单元覆盖的像素的总亮度。
下面给出了最流行的 Haar 功能的一些示例。
您的任务是确定使用所谓的前缀矩形计算特征所需的操作数。
前缀矩形是图像上的任意矩形,其左上角与图像的左上角重合。
您有一个变量值,其值最初为零。在一次操作中,您可以计算任何前缀矩形处的像素值之和,将其乘以任何整数并添加到变量值。
您获得了一项功能。有必要计算在任意图像上计算该属性的值所需的最少操作次数。为了更好地理解该语句,请阅读第一个示例的解释。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 100) — 特征中的行数和列数。
接下来的 n 行包含该功能的描述。每行由 m 个字符组成,如果特征的该元素是白色,则第 i 行的第 j 个字符等于“W”,如果是黑色,则等于“B”。
输出
打印单个数字 — 计算特征值所需执行的最少操作数。
示例
输入 #1
6 8 BBBBBBBB BBBBBBBB BBBBBBBB WWWWWWWW WWWWWWWW WWWWWWWW
输出 #1
2
输入 #2
3 3 WBW BWW WWW
输出 #2
4
输入 #3
3 6 WWBBWW WWBBWW WWBBWW
输出 #3
3
输入#4
4 4 BBBB BBBB BBBB BBBW
输出#4
4
注意
第一个样本对应于特征 B,如图所示。在尺寸为 6 × 8 的图像中,该特征的值等于图像下半部分和上半部分像素的总亮度之差。要计算其值,请执行以下两个操作:
1、将第6行第8列右下角的前缀矩形中系数为1的像素之和添加到变量值中(该矩形用红框表示);
2.将第3行第8列右下角前缀矩形中的像素数与系数 - 2和变量值相加。
因此,根据需要,图像下部三行中的所有像素将包含因子 1,图像上部三行中的所有像素将包含因子 1 - 2 = - 1。