The image has size
$$2^N\times 2^N,$$
with pixel coordinates \(0\le x,y\le 2^N-1\). A pixel is black exactly when
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $$
So the image is a digital disk centered at \((c,c)\). The quadtree encoding uses:
$$\text{uniform block} \Rightarrow 2\text{ bits},\qquad \text{mixed block} \Rightarrow 1+\sum_{i=1}^4 L_i.$$
The goal is to compute the total encoding length for \(N=24\) without expanding all pixels.
1) Length depends only on whether a block is uniform. If every pixel in a square block has the same color, the encoder stops immediately and emits a leaf of length \(2\). Otherwise it emits one split bit and recurses into the four children. Since black and white leaves both cost \(2\), we never need to know which color a uniform block has, only whether it is uniform.
2) Reformulate the color test geometrically. For a block
$$B=[x_0,x_1]\times [y_0,y_1]$$
with integer pixel coordinates, define the squared distance to the center
$$D(x,y)=(x-c)^2+(y-c)^2.$$
The block is:
$$\text{all black if } \max_{(x,y)\in B} D(x,y)\le R^2,$$
$$\text{all white if } \min_{(x,y)\in B} D(x,y)>R^2.$$
Only if neither condition holds is the block mixed.
3) Exact formula for the nearest pixel. The minimum of \(D(x,y)\) over the block is obtained by clamping the center coordinate into the interval of the block:
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1).$$
Then
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
This works because \(D(x,y)\) is the sum of two independent convex quadratic functions, one in \(x\) and one in \(y\).
4) Exact formula for the farthest pixel. The maximum of \(D(x,y)\) over an axis-aligned block is always attained at a corner. Therefore we can compute
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
and then
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
This is exactly what the fast solver uses.
5) Uniformity test. With these two numbers, the recursion decision is immediate:
$$d_{\max}^2\le R^2 \Rightarrow \text{all black},$$
$$d_{\min}^2>R^2 \Rightarrow \text{all white},$$
otherwise the circle boundary crosses the block and the block must be subdivided.
6) Recursive length formula. If \(B\) is uniform,
$$L(B)=2.$$
If \(B\) is mixed and split into \(B_{NW},B_{NE},B_{SW},B_{SE}\), then
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
The child order matters for the bitstream but not for the total length. The code uses the order NW, NE, SW, SE.
Example 1: \(N=1\). The image is \(2\times2\), with \(c=1\) and \(R^2=1\). Among the four pixels, \((1,1)\), \((1,0)\), and \((0,1)\) are black, while \((0,0)\) is white. So the root block is mixed and must split into four \(1\times1\) leaves:
$$L=1+4\cdot 2=9.$$
Example 2: small checkpoints. The fast method agrees with the brute-force quadtree on
$$N=1,2,3,4,5$$
and the corresponding lengths are
$$9,\ 30,\ 86,\ 212,\ 499.$$
These values are a strong sanity check for the geometric pruning logic.
The brute-force method explicitly colors every pixel and then compresses. The fast method never builds the bitmap: it replaces “is this block monochrome?” by the exact min/max distance test above. Because those tests are necessary and sufficient, every block is classified exactly as in the brute-force version, so both traversals visit the same logical quadtree and produce the same total length.
The running time is proportional to the number of visited quadtree nodes, not to the total number of pixels \(4^N\). Large regions fully inside or fully outside the disk terminate immediately; only blocks near the circle boundary recurse deeply. Memory usage is just the recursion depth:
$$O(N).$$
Das Bild hat Größe
$$2^N\times 2^N,$$
mit Pixelkoordinaten \(0\le x,y\le 2^N-1\). Ein Pixel ist genau dann schwarz, wenn
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $$
Die Quadtree-Kodierung lautet:
$$\text{uniformer Block}\Rightarrow 2,\qquad \text{gemischter Block}\Rightarrow 1+\sum_{i=1}^4L_i.$$
Gesucht ist die Gesamtlänge für \(N=24\), ohne alle Pixel explizit zu erzeugen.
1) Alles hängt von der Uniformität eines Blocks ab. Ist ein Block vollständig schwarz oder vollständig weiß, endet die Kodierung dort mit einer Blattlänge \(2\). Nur gemischte Blöcke werden weiter unterteilt.
2) Geometrischer Test. Für einen Block
$$B=[x_0,x_1]\times [y_0,y_1]$$
betrachte
$$D(x,y)=(x-c)^2+(y-c)^2.$$
Dann gilt:
$$\max_{B}D\le R^2 \Rightarrow \text{alles schwarz},$$
$$\min_{B}D>R^2 \Rightarrow \text{alles weiß}.$$
Nur sonst ist der Block gemischt.
3) Kleinste Distanz per Clamping. Der nächste Pixel zum Zentrum entsteht durch
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1),$$
also
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
4) Größte Distanz an einer Ecke. Die größte quadratische Distanz in einem achsenparallelen Block liegt an einer Ecke. Daher
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
und
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
5) Rekursionsformel. Für uniforme Blöcke gilt
$$L(B)=2.$$
Für gemischte Blöcke mit vier Kindern:
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
Beispiel \(N=1\). Das Bild ist \(2\times2\). Drei Pixel sind schwarz, einer weiß; also ist der Wurzelblock gemischt und liefert
$$L=1+4\cdot2=9.$$
Weitere Checkpoints sind
$$9,\ 30,\ 86,\ 212,\ 499$$
für \(N=1,2,3,4,5\).
Die Brute-Force-Variante färbt alle Pixel und komprimiert danach. Die schnelle Variante ersetzt die Farbprüfung eines Blocks durch den exakten Test mit \(d_{\min}^2\) und \(d_{\max}^2\). Da dieser Test genau entscheidet, ob ein Block vollständig innen, vollständig außen oder gemischt ist, erzeugen beide Varianten logisch denselben Quadtree und daher dieselbe Gesamtlänge.
Die Laufzeit ist proportional zur Zahl der besuchten Quadtree-Knoten, nicht zu \(4^N\). Große Innen- und Außenbereiche werden sofort abgeschnitten; tiefe Rekursion entsteht nur nahe der Kreisgrenze. Der Speicherbedarf ist nur die Rekursionstiefe:
$$O(N).$$
Görüntü boyutu
$$2^N\times 2^N$$
ve piksel koordinatları \(0\le x,y\le 2^N-1\) aralığındadır. Bir piksel ancak
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2} $$
ise siyah olur. Yani merkez \((c,c)\) etrafında dijital bir disk vardır. Quadtree kodlama kuralı:
$$\text{uniform blok}\Rightarrow 2,\qquad \text{karışık blok}\Rightarrow 1+\sum_{i=1}^4L_i.$$
Amaç, \(N=24\) için toplam uzunluğu tüm pikselleri gezmeden bulmaktır.
1) Uzunluk sadece blok tek-renk mi sorusuna bağlıdır. Bir blok tamamen siyah ya da tamamen beyazsa kodlama orada durur ve uzunluk \(2\) olur. Renk hangisi olursa olsun yaprak maliyeti aynı olduğundan, önemli olan yalnızca blok uniform mu sorusudur.
2) Renk testi geometrik mesafe testine iner. Bir
$$B=[x_0,x_1]\times [y_0,y_1]$$
bloğu için
$$D(x,y)=(x-c)^2+(y-c)^2$$
tanımlayalım. O zaman
$$\max_B D\le R^2 \Rightarrow \text{blok tamamen siyah},$$
$$\min_B D>R^2 \Rightarrow \text{blok tamamen beyaz}.$$
Yalnızca bu iki durumun dışında blok karışıktır.
3) En yakın piksel clamp ile bulunur. Merkeze en yakın piksel koordinatları
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1)$$
olur ve
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2$$
elde edilir. Bunun nedeni, \(D(x,y)\)'nin \(x\) ve \(y\) açısından ayrı ayrı konveks kuadratik olmasıdır.
4) En uzak piksel bir köşededir. Eksen hizalı bir blokta en büyük karesel mesafe her zaman köşelerden birinde alınır. Bu yüzden
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|)$$
ve
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2$$
hesaplamak yeterlidir.
5) Özyinelemeli uzunluk bağıntısı. Uniform blok için
$$L(B)=2$$
olur. Karışık blok dört çocuğa bölünürse
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE})$$
olur. Çocuk sırası bit dizisi için önemlidir ama toplam uzunluğu değiştirmez; kod NW, NE, SW, SE sırasını kullanır.
Örnek \(N=1\). Görüntü \(2\times2\) boyutundadır. Üç piksel siyah, bir piksel beyaz olduğu için kök blok karışıktır ve dört adet \(1\times1\) yaprağa ayrılır:
$$L=1+4\cdot 2=9.$$
Küçük checkpoint değerleri de
$$9,\ 30,\ 86,\ 212,\ 499$$
şeklinde \(N=1,2,3,4,5\) için doğrulanır.
Brute-force sürüm önce tüm pikselleri boyar, sonra quadtree kurar. Hızlı sürüm ise “bu blok tek-renk mi?” sorusunu tam olarak \(d_{\min}^2\) ve \(d_{\max}^2\) ile cevaplar. Bu test gerekli ve yeterli olduğu için iki yöntem aynı mantıksal quadtree'yi gezer ve aynı toplam uzunluğu üretir.
Çalışma süresi ziyaret edilen quadtree düğüm sayısıyla orantılıdır; \(4^N\) piksel sayısıyla değil. Diskin tamamen içinde ya da tamamen dışında kalan büyük bölgeler hemen budanır; derin özyineleme sadece sınır yakınında görülür. Bellek kullanımı ise yalnızca özyineleme derinliği kadardır:
$$O(N).$$
La imagen tiene tamaño
$$2^N\times 2^N,$$
con coordenadas de píxel \(0\le x,y\le 2^N-1\). Un píxel es negro exactamente cuando
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $$
La codificación quadtree cumple
$$\text{bloque uniforme}\Rightarrow 2,\qquad \text{bloque mixto}\Rightarrow 1+\sum_{i=1}^4L_i.$$
El objetivo es hallar la longitud total para \(N=24\) sin recorrer todos los píxeles.
1) Todo depende de si el bloque es uniforme. Si un bloque es completamente negro o completamente blanco, la codificación termina allí con longitud \(2\). Como ambas hojas cuestan lo mismo, basta saber si el bloque es uniforme.
2) Test geométrico. Para un bloque
$$B=[x_0,x_1]\times [y_0,y_1]$$
definimos
$$D(x,y)=(x-c)^2+(y-c)^2.$$
Entonces
$$\max_B D\le R^2 \Rightarrow \text{todo negro},$$
$$\min_B D>R^2 \Rightarrow \text{todo blanco}.$$
Solo en el caso intermedio el bloque es mixto y debe subdividirse.
3) Distancia mínima exacta. El píxel más cercano al centro se obtiene “recortando” la coordenada \(c\) al intervalo del bloque:
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1),$$
de modo que
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
4) Distancia máxima exacta. La mayor distancia cuadrada en un rectángulo alineado con ejes siempre aparece en una esquina. Por eso basta calcular
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
y luego
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
5) Recurrencia de longitud. Para un bloque uniforme,
$$L(B)=2.$$
Para un bloque mixto,
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
Ejemplo \(N=1\). La imagen es \(2\times2\). Tres píxeles son negros y uno blanco, así que la raíz es mixta y se divide en cuatro hojas:
$$L=1+4\cdot2=9.$$
Los checkpoints pequeños son
$$9,\ 30,\ 86,\ 212,\ 499$$
para \(N=1,2,3,4,5\).
La versión brute force colorea todos los píxeles y luego comprime. La versión rápida sustituye esa comprobación por el test exacto con \(d_{\min}^2\) y \(d_{\max}^2\). Como ese test caracteriza exactamente si el bloque está completamente dentro, completamente fuera o mezclado, ambos métodos recorren el mismo quadtree lógico y producen la misma longitud total.
El tiempo es proporcional al número de nodos visitados del quadtree, no al número total de píxeles \(4^N\). Las grandes regiones interiores o exteriores se podan enseguida; la recursión profunda solo aparece cerca de la frontera del círculo. La memoria es solo la profundidad de recursión:
$$O(N).$$
图像大小为
$$2^N\times 2^N,$$
像素坐标满足 \(0\le x,y\le 2^N-1\)。当且仅当
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2} $$
时像素为黑色。四叉树编码规则为
$$\text{一致块}\Rightarrow 2,\qquad \text{混合块}\Rightarrow 1+\sum_{i=1}^4L_i.$$
目标是在 \(N=24\) 时精确求出总编码长度，而不是逐像素展开。
1) 关键只在于判断块是否一致。 如果一个方块全黑或全白，编码立刻结束，长度为 \(2\)。因为黑叶子和白叶子代价相同，我们根本不需要区分是哪一种颜色，只需要知道这个块是否一致。
2) 用几何距离做一致性判定。 对块
$$B=[x_0,x_1]\times [y_0,y_1]$$
定义
$$D(x,y)=(x-c)^2+(y-c)^2.$$
则有
$$\max_B D\le R^2 \Rightarrow \text{全黑},$$
$$\min_B D>R^2 \Rightarrow \text{全白}.$$
只有两者都不成立时，这个块才是混合块。
3) 最小距离的精确公式。 距离中心最近的像素坐标通过 clamp 得到：
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1),$$
于是
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
4) 最大距离的精确公式。 在轴对齐方块中，最大平方距离总是在某个角点上取得。因此只需计算
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
再令
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
5) 长度递推。 若块一致，则
$$L(B)=2.$$
若块混合并分成四个象限，则
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
示例 \(N=1\). 图像是 \(2\times2\)。其中三个像素为黑，一个为白，所以根节点是混合块，必须分裂成四个叶子：
$$L=1+4\cdot2=9.$$
更小规模的 checkpoint 值为
$$9,\ 30,\ 86,\ 212,\ 499$$
对应 \(N=1,2,3,4,5\)。
暴力方法是先给每个像素上色，再压缩。快速方法完全不构造位图，而是用 \(d_{\min}^2\) 与 \(d_{\max}^2\) 的精确判定来回答“这个块是否单色”。由于这个判定既必要又充分，所以快速方法和暴力方法会访问完全相同的逻辑四叉树，因此得到相同的总编码长度。
运行时间与实际访问到的四叉树节点数成正比，而不是与总像素数 \(4^N\) 成正比。完全在圆内或圆外的大块会立刻剪枝，深递归只发生在圆边界附近。内存只需要递归深度：
$$O(N).$$
Изображение имеет размер
$$2^N\times 2^N,$$
а пиксель с координатами \(0\le x,y\le 2^N-1\) черный тогда и только тогда, когда
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $$
Длина quadtree-кода задается правилами
$$\text{однородный блок}\Rightarrow 2,\qquad \text{смешанный блок}\Rightarrow 1+\sum_{i=1}^4L_i.$$
Нужно найти общую длину для \(N=24\), не строя изображение пиксель за пикселем.
1) Важна только однородность блока. Если квадрат полностью черный или полностью белый, кодирование сразу заканчивается длиной \(2\). Поскольку цена черного и белого листа одинакова, важно лишь понять, однороден блок или нет.
2) Геометрический тест. Для блока
$$B=[x_0,x_1]\times [y_0,y_1]$$
рассматриваем
$$D(x,y)=(x-c)^2+(y-c)^2.$$
Тогда
$$\max_B D\le R^2 \Rightarrow \text{весь блок черный},$$
$$\min_B D>R^2 \Rightarrow \text{весь блок белый}.$$
И только в остальных случаях блок смешанный.
3) Точная минимальная дистанция. Ближайший к центру пиксель находится с помощью clamp:
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1),$$
откуда
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
4) Точная максимальная дистанция. Максимум квадратного расстояния в прямоугольном блоке всегда достигается в одной из вершин. Поэтому
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
и
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
5) Рекурсия длины. Для однородного блока
$$L(B)=2,$$
а для смешанного блока
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
Пример \(N=1\). Изображение имеет размер \(2\times2\). Три пикселя черные, один белый, поэтому корневой блок смешанный и распадается на четыре листа:
$$L=1+4\cdot2=9.$$
Малые checkpoint-значения:
$$9,\ 30,\ 86,\ 212,\ 499$$
для \(N=1,2,3,4,5\).
Brute-force версия сначала окрашивает все пиксели, а затем сжимает. Быстрая версия не строит растр вообще, а заменяет вопрос «однороден ли этот блок?» точным тестом через \(d_{\min}^2\) и \(d_{\max}^2\). Так как этот тест необходим и достаточен, обе версии обходят один и тот же логический quadtree и дают одну и ту же общую длину.
Время работы пропорционально числу реально посещенных узлов quadtree, а не числу пикселей \(4^N\). Большие области целиком внутри или вне круга сразу отсекаются; глубокая рекурсия возникает только возле границы круга. Память равна глубине рекурсии:
$$O(N).$$
لدينا صورة ثنائية بحجم
$$2^N\times 2^N,$$
ويكون البكسل ذو الإحداثيين \(0\le x,y\le 2^N-1\) أسود إذا وفقط إذا
$$ (x-c)^2+(y-c)^2\le R^2,\qquad c=2^{N-1},\quad R^2=2^{2N-2}. $$
طول ترميز quadtree يعطى بالقانون
$$\text{كتلة متجانسة}\Rightarrow 2,\qquad \text{كتلة مختلطة}\Rightarrow 1+\sum_{i=1}^4L_i.$$
المطلوب حساب الطول الكلي عند \(N=24\) من دون توليد جميع البكسلات صراحة.
1) المهم فقط هل الكتلة متجانسة أم لا. إذا كانت الكتلة كلها سوداء أو كلها بيضاء، ينتهي الترميز فورًا بطول \(2\). وبما أن كلفة الورقة السوداء والبيضاء متساوية، فنحن لا نحتاج إلى معرفة اللون نفسه، بل نحتاج فقط إلى معرفة هل الكتلة متجانسة.
2) اختبار هندسي بالمسافة. لكتلة
$$B=[x_0,x_1]\times [y_0,y_1]$$
نعرّف
$$D(x,y)=(x-c)^2+(y-c)^2.$$
عندئذ
$$\max_B D\le R^2 \Rightarrow \text{الكتلة كلها سوداء},$$
$$\min_B D>R^2 \Rightarrow \text{الكتلة كلها بيضاء}.$$
فقط عندما لا يتحقق أي منهما تكون الكتلة مختلطة.
3) أقل مسافة بدقة. أقرب بكسل إلى المركز يُحصل عليه عبر clamp:
$$x_{\min}=\operatorname{clamp}(c,x_0,x_1),\qquad y_{\min}=\operatorname{clamp}(c,y_0,y_1),$$
ومن ثم
$$d_{\min}^2=(x_{\min}-c)^2+(y_{\min}-c)^2.$$
4) أكبر مسافة بدقة. أكبر مسافة مربعة داخل كتلة محاذية للمحاور تتحقق دائمًا عند إحدى الزوايا. لذلك يكفي حساب
$$dx_{\max}=\max(|x_0-c|,|x_1-c|),\qquad dy_{\max}=\max(|y_0-c|,|y_1-c|),$$
ثم
$$d_{\max}^2=dx_{\max}^2+dy_{\max}^2.$$
5) علاقة الطول التكرارية. للكتلة المتجانسة
$$L(B)=2,$$
أما للكتلة المختلطة
$$L(B)=1+L(B_{NW})+L(B_{NE})+L(B_{SW})+L(B_{SE}).$$
مثال \(N=1\). الصورة بحجم \(2\times2\). ثلاثة بكسلات سوداء وواحد أبيض، لذلك تكون الكتلة الجذرية مختلطة وتنقسم إلى أربع أوراق:
$$L=1+4\cdot2=9.$$
وقيم التحقق الصغيرة هي
$$9,\ 30,\ 86,\ 212,\ 499$$
عند \(N=1,2,3,4,5\).
النسخة brute-force تلوّن كل البكسلات ثم تضغط. أما النسخة السريعة فلا تبني الصورة أصلًا، بل تستبدل سؤال “هل هذه الكتلة أحادية اللون؟” باختبار دقيق يعتمد على \(d_{\min}^2\) و\(d_{\max}^2\). وبما أن هذا الاختبار ضروري وكافٍ، فإن الطريقتين تمران على quadtree منطقي واحد وتعطيان الطول الكلي نفسه.
زمن التنفيذ يتناسب مع عدد عقد quadtree التي تمت زيارتها فعليًا، وليس مع عدد البكسلات \(4^N\). المناطق الكبيرة الواقعة بالكامل داخل القرص أو خارجه تُقص فورًا، أما التعمق الكبير فيحدث فقط قرب الحد الدائري. الذاكرة هي عمق الاستدعاء فقط:
$$O(N).$$