pub(crate) const TILE: usize = 32;
const FLAT_TILE_SHARE: f32 = 0.8;
const MAX_CROPS: usize = 6;
const MIN_CROP_TILES: usize = 6;
const MIN_RICH_TILES: f32 = 0.03;
pub(crate) const FRAME_OVERHEAD: f64 = 150.0;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct CropBox {
pub(crate) x0: usize,
pub(crate) y0: usize,
pub(crate) width: usize,
pub(crate) height: usize,
}
fn flat_tiles(rgb: &[u8], width: usize, height: usize) -> (Vec<bool>, usize, usize) {
let (tw, th) = (width / TILE, height / TILE);
let px = rgb.as_chunks::<3>().0;
let at = |x: usize, y: usize| px[y * width + x];
let mut flat = vec![false; tw * th];
for ty in 0..th {
for tx in 0..tw {
let mut same = 0usize;
for y in ty * TILE..(ty + 1) * TILE {
for x in tx * TILE..(tx + 1) * TILE {
let p = at(x, y);
let n = usize::from(at(x.saturating_sub(1), y) == p)
+ usize::from(at((x + 1).min(width - 1), y) == p)
+ usize::from(at(x, y.saturating_sub(1)) == p)
+ usize::from(at(x, (y + 1).min(height - 1)) == p);
same += usize::from(n >= 2);
}
}
flat[ty * tw + tx] = same as f32 >= FLAT_TILE_SHARE * (TILE * TILE) as f32;
}
}
(flat, tw, th)
}
fn max_rect(free: &[bool], tw: usize, th: usize) -> (usize, usize, usize, usize, usize) {
let mut heights = vec![0usize; tw];
let mut best = (0, 0, 0, 0, 0);
let mut stack: Vec<(usize, usize)> = Vec::with_capacity(tw + 1);
for (y, row) in free[..tw * th].chunks_exact(tw).enumerate() {
for (height, &is_free) in heights.iter_mut().zip(row) {
*height = if is_free { *height + 1 } else { 0 };
}
stack.clear();
for (x, &cur) in heights.iter().chain(std::iter::once(&0)).enumerate() {
let mut start = x;
while let Some(&(s, h)) = stack.last() {
if h < cur {
break;
}
stack.pop();
let area = h * (x - s);
if area > best.0 {
best = (area, s, y + 1 - h, x, y + 1);
}
start = s;
}
stack.push((start, cur));
}
}
best
}
pub(crate) fn plan(rgb: &[u8], width: usize, height: usize) -> Vec<CropBox> {
if width < 4 * TILE || height < 4 * TILE {
return Vec::new();
}
let (mut free, tw, th) = flat_tiles(rgb, width, height);
let rich = free.iter().filter(|&&f| !f).count();
if (rich as f32) < MIN_RICH_TILES * free.len() as f32 || rich == free.len() {
return Vec::new();
}
let mut boxes = Vec::new();
while boxes.len() < MAX_CROPS {
let (area, x0, y0, x1, y1) = max_rect(&free, tw, th);
if area < MIN_CROP_TILES {
break;
}
for y in y0..y1 {
free[y * tw + x0..y * tw + x1].fill(false);
}
boxes.push(CropBox {
x0: x0 * TILE,
y0: y0 * TILE,
width: (x1 - x0) * TILE,
height: (y1 - y0) * TILE,
});
}
boxes
}
pub(crate) fn background_color(rgb: &[u8], width: usize, b: CropBox) -> [u8; 3] {
let pixels = rgb.as_chunks::<3>().0;
let mut crop = (b.y0..b.y0 + b.height).flat_map(|y| &pixels[y * width + b.x0..][..b.width]);
let mut color = *crop.next().expect("nonempty crop rectangle");
let mut run = 1usize;
let mut counts = std::collections::HashMap::<[u8; 3], usize>::new();
for &pixel in crop {
if pixel == color {
run += 1;
} else {
*counts.entry(color).or_default() += run;
color = pixel;
run = 1;
}
}
if counts.is_empty() {
return color;
}
*counts.entry(color).or_default() += run;
counts.into_iter().max_by_key(|&(c, n)| (n, c)).unwrap().0
}
pub(crate) const DETAIL_MAX_DISTANCE: f32 = 2.0;
const MIN_DETAIL_TILES: usize = 16;
const MIN_DETAIL_SIDE: usize = 3;
const MAX_DETAIL_CROPS: usize = 4;
const DETAIL_MIN_STEP: f32 = 3.0;
const DETAIL_MAX_CHROMA: f32 = 0.5;
pub(crate) const DETAIL_MARGIN: f64 = 0.9;
const DETAIL_HARD_SHARE: f32 = 0.5;
const DETAIL_HARD_STEP: i32 = 24;
const BLANK_MAX_STEP: f32 = 1.0;
#[derive(Clone, Copy, PartialEq, Eq)]
enum DetailTile {
Other,
Blank,
Detail,
}
fn detail_tiles(rgb: &[u8], width: usize, height: usize) -> (Vec<DetailTile>, usize, usize) {
let (tw, th) = (width / TILE, height / TILE);
let px = rgb.as_chunks::<3>().0;
let ycc = |x: usize, y: usize| {
let [r, g, b] = px[y * width + x].map(i32::from);
[(r + 2 * g + b) >> 2, r - b, g - ((r + b) >> 1)]
};
let mut tiles = vec![DetailTile::Other; tw * th];
for ty in 0..th {
for tx in 0..tw {
let (mut luma, mut chroma, mut hard) = (0i64, 0i64, 0i64);
for y in ty * TILE..(ty + 1) * TILE {
for x in tx * TILE..(tx + 1) * TILE {
let p = ycc(x, y);
for (nx, ny) in [(x + 1, y), (x, y + 1)] {
if nx >= (tx + 1) * TILE || ny >= (ty + 1) * TILE {
continue;
}
let q = ycc(nx, ny);
let step = (p[0] - q[0]).abs();
luma += i64::from(step);
chroma += i64::from((p[1] - q[1]).abs() + (p[2] - q[2]).abs());
if step >= DETAIL_HARD_STEP {
hard += i64::from(step);
}
}
}
}
let pairs = (2 * TILE * (TILE - 1)) as f32;
let (luma, chroma, hard) = (luma as f32, chroma as f32, hard as f32);
tiles[ty * tw + tx] =
if luma < BLANK_MAX_STEP * pairs && chroma < BLANK_MAX_STEP * pairs {
DetailTile::Blank
} else if luma >= DETAIL_MIN_STEP * pairs
&& chroma <= DETAIL_MAX_CHROMA * luma
&& hard >= DETAIL_HARD_SHARE * luma
{
DetailTile::Detail
} else {
DetailTile::Other
};
}
}
(tiles, tw, th)
}
pub(crate) fn plan_detail(
rgb: &[u8],
width: usize,
height: usize,
taken: &[CropBox],
) -> Vec<CropBox> {
if width < 4 * TILE || height < 4 * TILE {
return Vec::new();
}
let (tiles, tw, th) = detail_tiles(rgb, width, height);
let mut free: Vec<bool> = (0..tw * th)
.map(|i| {
let (tx, ty) = (i % tw, i / tw);
match tiles[i] {
DetailTile::Detail => true,
DetailTile::Other => false,
DetailTile::Blank => (ty.saturating_sub(1)..(ty + 2).min(th)).any(|y| {
(tx.saturating_sub(1)..(tx + 2).min(tw))
.any(|x| tiles[y * tw + x] == DetailTile::Detail)
}),
}
})
.collect();
for b in taken {
for y in b.y0 / TILE..(b.y0 + b.height) / TILE {
free[y * tw + b.x0 / TILE..y * tw + (b.x0 + b.width) / TILE].fill(false);
}
}
let mut boxes = Vec::new();
while boxes.len() < MAX_DETAIL_CROPS {
let (area, x0, y0, x1, y1) = max_rect(&free, tw, th);
if area < MIN_DETAIL_TILES || (x1 - x0).min(y1 - y0) < MIN_DETAIL_SIDE {
break;
}
for y in y0..y1 {
free[y * tw + x0..y * tw + x1].fill(false);
}
boxes.push(CropBox {
x0: x0 * TILE,
y0: y0 * TILE,
width: (x1 - x0) * TILE,
height: (y1 - y0) * TILE,
});
}
boxes
}
pub(crate) fn cut(rgb: &[u8], width: usize, b: &CropBox) -> Vec<u8> {
let mut out = Vec::with_capacity(b.width * b.height * 3);
for y in b.y0..b.y0 + b.height {
let start = (y * width + b.x0) * 3;
out.extend_from_slice(&rgb[start..start + b.width * 3]);
}
out
}
pub(crate) fn content(crop: Vec<u8>, b: &CropBox, distance: f32) -> Vec<u8> {
let steps = crate::vector_layers::coverage_steps(distance);
match crate::vector_layers::split(&crop, b.width, b.height, steps) {
Some(mut split) => {
crate::simd::rgb8_blend::blend_in_place(
split.base.as_chunks_mut::<3>().0,
split.layer.as_chunks::<3>().0,
&split.coverage,
);
split.base
}
None => crop,
}
}
#[cfg(test)]
mod tests {
use super::*;
fn mixed(width: usize, height: usize) -> Vec<u8> {
let mut rgb = vec![240u8; width * height * 3];
let mut seed = 1u32;
for y in 0..height / 2 {
for x in 0..width / 2 {
for k in 0..3 {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
rgb[(y * width + x) * 3 + k] = (seed >> 24) as u8;
}
}
}
rgb
}
#[test]
fn plan_boxes_cover_only_flat_tiles() {
let (w, h) = (512, 384);
let rgb = mixed(w, h);
let boxes = plan(&rgb, w, h);
assert!(!boxes.is_empty());
for b in &boxes {
assert_eq!(
b.x0 % TILE + b.y0 % TILE + b.width % TILE + b.height % TILE,
0
);
assert!(b.x0 >= w / 2 || b.y0 >= h / 2);
}
for (i, a) in boxes.iter().enumerate() {
for b in &boxes[i + 1..] {
let ox = a.x0 < b.x0 + b.width && b.x0 < a.x0 + a.width;
let oy = a.y0 < b.y0 + b.height && b.y0 < a.y0 + a.height;
assert!(!(ox && oy));
}
}
}
fn strokes(width: usize, height: usize, paper: [u8; 3], ink: [u8; 3]) -> Vec<u8> {
let mut seed = 5u32;
let mut rgb: Vec<u8> = (0..width * height * 3)
.map(|_| {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 24) as u8
})
.collect();
for y in 64..256 {
for x in 64..320 {
let on = y % 7 < 4 && (x + y / 7) % 5 < 2;
rgb[(y * width + x) * 3..][..3].copy_from_slice(if on { &ink } else { &paper });
}
}
rgb
}
#[test]
fn plan_detail_takes_two_tone_strokes_in_either_polarity() {
let (w, h) = (448, 320);
for (paper, ink) in [
([250, 250, 250], [20, 20, 20]),
([10, 10, 10], [230, 230, 230]),
] {
let boxes = plan_detail(&strokes(w, h, paper, ink), w, h, &[]);
assert_eq!(
boxes,
vec![CropBox {
x0: 64,
y0: 64,
width: 256,
height: 192
}]
);
}
}
#[test]
fn plan_detail_leaves_saturated_strokes_noise_and_taken_boxes() {
let (w, h) = (448, 320);
let red = strokes(w, h, [255, 255, 255], [255, 0, 0]);
assert!(plan_detail(&red, w, h, &[]).is_empty());
let gray = strokes(w, h, [250, 250, 250], [20, 20, 20]);
let taken = CropBox {
x0: 64,
y0: 64,
width: 256,
height: 192,
};
assert!(plan_detail(&gray, w, h, &[taken]).is_empty());
}
#[test]
fn plan_skips_flat_and_rich_images() {
let (w, h) = (256, 256);
assert!(plan(&vec![200u8; w * h * 3], w, h).is_empty());
let mut seed = 7u32;
let noise: Vec<u8> = (0..w * h * 3)
.map(|_| {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 24) as u8
})
.collect();
assert!(plan(&noise, w, h).is_empty());
}
#[test]
fn background_color_counts_only_the_box_and_keeps_color_ties() {
let (w, h) = (96, 64);
let mut rgb = vec![10u8; w * h * 3];
let b = CropBox {
x0: 32,
y0: 0,
width: 32,
height: 32,
};
for y in 0..32 {
for x in 32..64 {
rgb[(y * w + x) * 3..][..3].copy_from_slice(&[200, 100, 50]);
}
}
rgb[(5 * w + 40) * 3..][..3].copy_from_slice(&[1, 2, 3]);
assert_eq!(background_color(&rgb, w, b), [200, 100, 50]);
rgb[(5 * w + 40) * 3..][..3].copy_from_slice(&[200, 100, 50]);
assert_eq!(background_color(&rgb, w, b), [200, 100, 50]);
for y in 0..16 {
rgb.as_chunks_mut::<3>().0[y * w + 32..y * w + 64].fill([200, 100, 51]);
}
assert_eq!(background_color(&rgb, w, b), [200, 100, 51]);
}
}