24T2选了一节关于人工智能的课程，即COMP9517计算机视觉。之后会将笔记分周记录下来。



# 色彩表现形式

## 色彩空间RGB

![image.png](/static/img/9ee91c32299cf1d735238773101fc696.image.png)

RGB图像是一种使用红（Red）、绿（Green）和蓝（Blue）三种基本颜色来表示颜色的图像。这三种颜色的不同组合和强度可以产生广泛的颜色范围。

RGB颜色模型是一种加色模型，表示通过混合不同强度的红、绿、蓝光来产生其他颜色。每种颜色的值通常在0到255之间，0表示没有该颜色，255表示该颜色的最大强度。

RGB图像的颜色深度通常为24位（8位红色，8位绿色，8位蓝色），这允许表示大约1670万种不同的颜色。

:::note{title="注"}
在RGB颜色模型中，“通道强相关性”（strongly correlated channels）是指RGB三个颜色通道之间的相互依赖性，这会导致一些问题和局限性。

1. 颜色空间不独立：在RGB颜色模型中，红、绿、蓝三种颜色通道不是独立的。一个颜色的改变可能会影响其他两个通道，这种相互依赖性使得颜色操作变得复杂。例如，要调整一个颜色的亮度，可能需要同时调整所有三个通道的值。

2. 色彩表示不直观：由于RGB颜色空间是基于物理光源的混合，而不是人类视觉的感知模型，因此并不直观。人眼对颜色的感知更接近于其他颜色空间（如HSV、Lab），这些颜色空间的通道之间相对独立，更适合色彩分析和处理。

3. 压缩和存储效率：在图像压缩和存储中，通道的相关性会导致冗余信息增加。图像压缩算法（如JPEG）通常需要额外的步骤来处理这种相关性，以达到更高的压缩效率。

4. 颜色转换复杂：在许多图像处理任务中，需要将RGB图像转换为其他颜色空间（如YCbCr、HSV）来简化处理和分析。然而，这种转换需要额外的计算，并且在某些情况下可能会导致颜色信息的损失或失真。
:::

## 色彩空间HSV

![image.png](/static/img/6151b72943102d991a8b06f4344be9f9.image.png)

HSV色彩空间是一种将颜色表示为色相（Hue）、饱和度（Saturation）和明度（Value）的颜色模型。与RGB颜色模型不同，HSV颜色空间更符合人类对颜色的感知方式，因此在图像处理和计算机视觉中有广泛应用。

**色相（Hue, H）：**

- 表示颜色的种类或基本色调，例如红色、蓝色、黄色等。
- 色相通常以角度表示，从0度到360度。0度表示红色，120度表示绿色，240度表示蓝色。

**饱和度（Saturation, S）：**

- 表示颜色的纯度或浓度，饱和度越高，颜色越纯，饱和度越低，颜色越灰。
- 饱和度的取值范围从0到1（或0%到100%），0表示灰色（无色），1表示纯色。

**明度（Value, V）：**

- 表示颜色的亮度或明暗程度，明度越高，颜色越亮，明度越低，颜色越暗。
- 明度的取值范围从0到1（或0%到100%），0表示黑色（无亮度），1表示白色或该色相的最亮颜色。


:::note{title="注"}
在HSV色彩空间中，通道之间的“混淆”（confounded channels）问题指的是色相（Hue）、饱和度（Saturation）和明度（Value）之间的某些相互依赖性，这可能会导致一些问题和局限性。

1. 颜色边界不一致：在HSV色彩空间中，某些颜色的边界不是很明确。特别是当饱和度和明度接近于0时，色相变得不确定。例如，纯白色、纯黑色和不同灰度级别的颜色在色相上没有明确的定义，因为它们不具有特定的颜色。

2. 非线性变化：HSV色彩空间中的变化并不是线性的。例如，小幅度的明度或饱和度变化可能会对视觉效果产生较大的影响，而在某些范围内，变化的影响又可能较小。这种非线性特性使得在某些图像处理任务中处理起来更为复杂。

3. 相互依赖性：尽管HSV色彩空间比RGB在某些方面更符合人类感知，但色相、饱和度和明度之间仍然存在一定的相互依赖性。例如，改变明度可能会影响颜色的感知，尤其是在低饱和度的情况下。

4. 亮度和色相的耦合：在某些情况下，特别是低饱和度或高明度情况下，色相的变化可能会导致颜色的感知不准确。这是因为在极端情况下，明度和饱和度的影响会掩盖色相的变化。

5. 色彩校正的复杂性：在需要精确色彩校正和匹配的场景中，HSV色彩空间的通道混淆可能会带来一些复杂性。比如，在色彩校正和匹配中，需要对三个通道进行综合考虑，可能需要更复杂的算法。
:::

## 色彩空间YCbCr

![image.png](/static/img/f3a52096571064e622f1a59c805fdb5e.image.png)

CbCr是一种用于视频和图像处理的色彩空间，它将颜色分解为亮度（Luminance，Y）和两个色度（Chrominance，Cb和Cr）分量。这种色彩空间特别常用于视频压缩（如JPEG和MPEG）和电视广播。

**亮度（Luminance, Y）：**

- 表示图像的亮度信息，是人眼对图像亮暗程度的感知。
- 亮度分量Y主要基于RGB颜色模型中的绿分量，因为人眼对绿色最敏感。

**色度（Chrominance, Cb和Cr）：**

- Cb（蓝色差分量）：表示蓝色与亮度的差异。
- Cr（红色差分量）：表示红色与亮度的差异。
- 色度分量主要用于表示颜色信息，而不是亮度。


:::info{title="优点"}
1. 分离亮度和色度信息：YCbCr色彩空间将亮度和色度分离，这使得在视频压缩和处理时，可以独立处理亮度和色度。例如，人眼对亮度的敏感度高于色度，因此可以在压缩时减少色度的分辨率，而不显著影响视觉质量。

2. 视频压缩效率高：由于YCbCr色彩空间的这种特性，许多视频压缩标准（如JPEG、MPEG、H.264）都采用了YCbCr色彩空间来提高压缩效率。

3. 兼容性：YCbCr色彩空间与传统电视广播和视频设备高度兼容，是彩色视频信号的标准表示方法。
:::

## 色彩空间 L\*a\*b\*

![image.png](/static/img/2d625b4983fc172a12f66c8694cd531b.image.png)

L\*a\*b\*色彩空间（也称为CIELAB色彩空间）是一种基于人类视觉感知的色彩模型，由国际照明委员会（CIE）定义。

**L\*（亮度，Lightness）：**

- 表示颜色的明暗程度，范围从0到100。0表示黑色，100表示白色。
- 这个分量与人眼对亮度的感知一致。

**a\*（红绿轴，Green-Red）：**

- 表示颜色在绿色到红色之间的变化，正值表示颜色偏红，负值表示颜色偏绿。
- 通常范围从-128到127。

**b\*（黄蓝轴，Blue-Yellow）：**

- 表示颜色在蓝色到黄色之间的变化，正值表示颜色偏黄，负值表示颜色偏蓝。
- 通常范围从-128到127。


> Any numerical change corresponds to similar perceived change in color: Euclidean distances make sense.

这句注释的意义在于下面的特点部分的“感知均匀性”。


:::info{title="特点"}
1. 感知均匀性：L\*a\*b\*色彩空间的设计目标是使相同数值差异对应于人眼感知到的相同颜色差异，这使得在色彩调整和色差计算时更为准确。

2. 独立性：亮度（L\*）与色度（a\*和b\*）是独立的，这意味着可以分别调整颜色的明度和色调，而不会互相影响。

3. 设备无关性：L\*a\*b\*色彩空间是一种设备无关的色彩模型，不依赖于具体的显示设备、照明条件或观察者，使得颜色的表示和交换更加一致和可靠。
:::

# 考试例题 Example Exam Question

Which one of the following statements about colour spaces is incorrect?

A. The R, G, and B channels of the RGB colour space are often correlated.

B. The H and the S channel of the HSV colour space are confounded.

C. The Y channel of the YCbCr colour space represents the brightness.

D. The a\* channel of the L\*a\*b\* colour space is the green-blue component.

> 答案是D。在L\*a\*b\*中，a\*的通道掌握着green-red通道。

COMP9517 Week 1 Image Formation

COMP6991 FINAL EXAM 23T1

COMP6991 FINAL EXAM 22T3

COMP6991 PRAC EXAM 22T3

COMP9020 – Foundations of Computer Science

FINAL Exam – Term 3 2022

From Question 5 to Question 10

**With my own solution (might be incorrect)**



# Question 5

![image.png](/static/img/8e2ec7362acb9d23df7bdf3f1f162615.image.webp)

## 5.1

:::info{title="Question"}
Prove or disprove:

G has an Eulerian path
:::

Here is the degree list for all of the vertices:

- vertex 0: 3
- vertex 1: 2
- vertex 2: 2
- vertex 3: 4
- vertex 4: 4
- vertex 5: 2
- vertex 6: 2
- vertex 7: 3

We could find that there are 2 vertices (0 and 7) whose degree is odd. This could prove that there is an Eulerian path in G.

For example:

0 → 2 → 3 → 1 → 0 → 4 → 5 → 7 → 6 → 4 → 3 → 7

## 5.2

:::info{title="Question"}
Prove or disprove:

G has a Hamiltonian cycle
:::

If it has a Hamiltonian cycle, it means that no matter which vertex I start, I could find a cycle. Because this cycle should get every vertex.

Divide these vertices into 2 subsets: {0, 1, 2, 3} and {4, 5, 6, 7}. Edges (0, 4), (3, 4) and (3, 7) are linking these 2 subsets.

Set start point at vertex 1, and we could go to vertex 0 or vertex 3.

If we go to vertex 0, we could go to vertex 2 or vertex 4 for next step.

If we go to vertex 2, we must go to vertex 3 for next step, but it means that we could not come back from {4, 5, 6, 7} because we should use vertex 0 or vertex 3 to go back and get vertex 1 at the last step.

So we should return, and go to vertex 4 when we are at vertex 0. However, after a trip in {4, 5, 6, 7}, we can only go back by vertex 3, and then we must choose to go to vertex 2 and get vertex 0. This is also a bad path.

So we return again, and go to vertex 3 when we are at vertex 1. However, it is same when we come back from {4, 5, 6, 7}. we could only choose vertex 0 to come back, but we have to go to vertex 2 and reach the vertex 3 in the end.

In conclusion, after the path finding, we could prove that this graph does not have a Hamiltonian cycle.

## 5.3

:::info{title="Question"}
Prove or disprove:

The chromatic number of G is equal to the clique number of G.  That is, χ(G) = κ(G).
:::

The clique number should be the vertex number of the smallest complete sub-graph in G. 

In graph G, we could only find 2-clique (an edge and 2 vertices at 2 sides). There is not any tri-angle (3-complete graph) in G. Therefore, $κ(G) = 2$.

Set vertex 0 in BLACK. And we could find that:

- vertex 0: BLACK
- vertex 1: WHITE
- vertex 2: WHITE
- vertex 3: BLACK
- vertex 4: WHITE
- vertex 5: BLACK
- vertex 6: BLACK
- vertex 7: WHITE

2 colors(black & white) could color graph G. Therefore, $χ(G) = 2$.

We could prove that:

$$
χ(G) = κ(G)
$$


# Question 6

Let Σ = {a,b,c}

Consider the function del:Σ* → Σ* which works as follows:

For w∈Σ*, del(w) is the word that results from removing all c's from w.

For example:

- del(aabbcc) = aabb
- del(ccbbaacc) = bbaa
- del(bacabc) = baba
- del(cccc) = λ
- del(bbbb) = bbbb

## 6.1

:::info{title="Question"}
Give a recursive definition of the function del:Σ* → Σ*
:::

- $del(\lambda) = \lambda$
- $del(cx) = del(x)$
- $del(mx) = m + del(x)$ if $m \in {a,b}$

``` Python
def del(w):
    if not w:
        return w
    if w[0] == 'c':
        return del(w[1:])
    else:
        return w[0] + del(w[1:])
```

## 6.2


:::info{title="Question"}
Let Σ={a,b,c}.

For w∈Σ*, let P(w) be the proposition that:

For all $v \in Σ^*$: $del(wv) = del(w)del(v)$

Prove, using your definition of del from part (a), that P(w) holds for all w∈Σ*.
:::


When $w = \lambda$, P(w) could be:

For all $v \in Σ^*$: $del(v) = del(v)$

It is true.


When $w = w_1w_2...w_k$,

Set: $Σ' = {a,b}$, and single element $w_i$ could be: $Σ'^*c^*Σ'^*$.

$del(wv) = del((Σ'^*c^*Σ'^*)^*v) = (Σ'^*Σ'^*)^*del(v)$

In addition, $del(w) = (Σ'^*Σ'^*)^*$

Therefore, we could prove that:

P(w) holds for all w∈Σ*.


# Question 7

Consider the following two pieces of code.

The first moves the minimum element of a list to its head

```
extractMin(L):	 
    if length(L) <= 1: return L
 	 
    x = L.head	 
    L2 = extractMin(L.next)	 
    if x < L2.head:	 
        return L	 
    else:	 
        L3 = (x, L2.next)	 
        return (L2.head, L3)
```

The second sorts a list by repeatedly extracting the minimum element using `extractMin`

```
mySort(L):	 
    i = 0	 
    L2 = empty
    L3 = L	 
 	 
    while i < length(L):	 
        L3 = extractMin(L3) 
        L2 = (L3.head, L2)	 
        L3 = L3.next	 
        i = i+1	 
 	 
    return L2
```

## 7.1


:::info{title="Question"}
Find an asymptotic upper bound for T(n): the running time of the worst-case of `extractMin(L)` where L is a list with n elements.

You may assume that creating a list is an elementary operation, as is checking the length of L.
:::

The worst case is that:

for every element in position `i`, it is the least element compared with all elements before. function should move `n-i` times to make it to the top of this list.

$$
T(n) = T(n-1) + O(n)
$$

And the sum is:

$$
T(n) = O(n) + O(n-1) + ... + O(1) = O(\frac{n(n+1)}{2}) \\
T(n) = O(n^2)
$$


## 7.2

:::info{title="Question"}
Find an asymptotic upper bound for R(n): the running time of the worst-case of `mySort(L)` where L is a list of n elements.

You may assume that creating a list is an elementary operation, as is checking the length of L.  You may assume the running time of `extractMin` on a list of length n is T(n) [if not previously calculated].
:::

We have proved that the worst-case of `extractMin(L)` is: $O(n^2)$.

And for `mySort(L)`, it use $O(n)$ time to execute `while` command, and every loop it executes `extractMin(L)` to calculate the least element.

Therefore, the worst upper bould for $R(n) = O(n^2 \times n) = O(n^3)$.


# Question 8

A spaceship is full of crewmates and imposters.  Crewmates always tell the truth, and imposters always lie.  Everyone is either a crewmate or an imposter.  Three members of the spaceship, Red, Green and Blue, make the following statements:

- Red: Blue is not an imposter
- Green: At least one of Blue or Green is a crewmate
- Blue: Green is an imposter

You would like to know if at least one of Red or Blue is an imposter.

## 8.1

:::info{title="Question"}

Explain how this problem can be modelled as a problem in Propositional Logic.  In particular, clearly define:

- The propositional variables you are using and what propositions they represent
- Any formulas that are appropriate, and what propositions they represent
- The Propositional Logic problem to be solved
:::

We could define that:

- $R$：Red is crewmate
- $G$: Green is crewmate
- $B$: Blue is crewmate

According to the statement of Red, if Red is crewmate, we could find that Blue is crewmate. If Red is not crewmate, Blue is not crewmate. That means:

$$
R \rightarrow B\\
\neg R \rightarrow \neg B \\
R \leftrightarrow B
$$

According to the statement of Green, there is at least one crewmate between Green and Blue.

$$
\neg B \vee \neg G

$$

According to the statement of Blue, if Green is a crewmate, Blue is an imposter; if Green is an imposter, we could find that this statement is true, and Blue is crewmate. That means:

$$
\neg G \rightarrow B \\
G \rightarrow \neg B \\
\neg G \leftrightarrow B
$$


## 8.2

:::info{title="Question"}
Using the Propositional Logic model of part (a), solve the given problem.
:::

We have that:

- $R \leftrightarrow B$
- $\neg G \leftrightarrow B$
- $\neg B \vee \neg G$

According to first two statement, we could find that:

- $R \leftrightarrow \neg G$

Assum: R is true. 

- According to $R \leftrightarrow B$, B is true.
- According to $R \leftrightarrow \neg G$, G is false.
- $\neg B \vee \neg G$ is true. However, it should be false because Green is imposter.

Assum: R is false.

- According to $R \leftrightarrow B$, B is false.
- According to $R \leftrightarrow \neg G$, G is true.
- $\neg B \vee \neg G$ is true.

Therefore, there is a solution for this spaceship:

- Red is imposter
- Green is crewmate
- Blue is imposter


# Question 9

## 9.1


:::info{title="Question"}

Suppose you have:

- x indistinguishable red balls
- y indistinguishable blue balls
- z indistinguishable green balls

Show that there are:

$$
\binom{x+y+z}{z}\binom{x+y}{y}
$$

ways of placing the balls into x+y+z distinguishable boxes with exactly one ball per box.
:::

We could use 3 steps to place all the balls:

1. select z empty boxes and place all of the green balls.
2. select y empty boxes and place all of the blue balls.
3. place all of the red balls into the rest boxes.

Because every ball is indistinguishable, we do not need to consider the order of placing between same color balls.

For the first step, we have $T_1$ ways:

$$
T_1 = C_{x+y+z}^{z} = \binom{x+y+z}{z}
$$

For the second step, we have $T_2$ ways:

$$
T_2 = C_{x+y}^{y} = \binom{x+y}{y}
$$

And the last step do not need any extra calcuation. Because after step 1 and step 2, there is just one option for step 3 to put balls.

In addition, the selection in step 1 could effect selection in step 2. Because every box is distinguishable. Therefore, every selection is unique.

So we could prove that the way of placing balls are:

$$
T_1 \times T_2 = \binom{x+y+z}{z}\binom{x+y}{y}
$$


## 9.2

:::info{title="Question"}
Show that for all x,y,z ∈ ℕ:

$$
\binom{x+y+z}{z}\binom{x+y}{y} = \binom{x+y+z}{x}\binom{y+z}{y}
$$
:::

If we have the same question in 9.1, we could change the steps in another way:

1. select x empty boxes and place all of the red balls.
2. select y empty boxes and place all of the blue balls.
3. place all of the green balls into the rest boxes.

Because every ball is indistinguishable, we do not need to consider the order of placing between same color balls.

For the first step, we have $T_3$ ways:

$$
T_3 = C_{x+y+z}^{x} = \binom{x+y+z}{x}
$$

For the second step, we have $T_4$ ways:

$$
T_4 = C_{y+z}^{y} = \binom{y+z}{y}
$$

And the last step do not need any extra calcuation. Because after step 1 and step 2, there is just one option for step 3 to put balls.

In addition, the selection in step 1 could effect selection in step 2. Because every box is distinguishable. Therefore, every selection is unique.

So we could prove that the way of placing balls are:

$$
T_3 \times T_4 = \binom{x+y+z}{x}\binom{y+z}{y}
$$

We use different ways to solve same question, and the result should be equal.

Therefore, it should be:

$$
T = T_1 \times T_2 = T_3 \times T_4
$$

It means that:

$$
\binom{x+y+z}{z}\binom{x+y}{y} = \binom{x+y+z}{x}\binom{y+z}{y}
$$


# Question 10


Let $Σ = \{a,b,c\}$

Let $p(k, n)$ be the probability that a word (over Σ) of length n, drawn uniformly at random from the set of all words of length n, contains exactly k c's.


## 10.1

:::info{title="Question"}
What is p(0,n)? 

Justify your answer
:::

For every character in a n-word, the possibility that it is not 'c' is $\frac{2}{3}$.

Therefore, $p(0,n) = (\frac{2}{3})^n$.

## 10.2

:::info{title="Question"}
What is p(n,n)? 

Justify your answer
:::

For every character in a n-word, the possibility that it is 'c' is $\frac{1}{3}$.

Therefore, $p(n,n) = (\frac{1}{3})^n$.

## 10.3

:::info{title="Question"}
Give, with justification, an expression for p(k,n), either:

- in terms of combinatorial functions, or
- recursively, in terms of p(k', n') where k'≤k and n'≤n
:::

We use combinatorial functions to solve this question.

For a n-word, we should select k characters to set 'c', and other characters are not 'c'.

Therefore, we could find that:

$$
p(k,n) = \binom{n}{k} \times (\frac{1}{3})^k \times 1 \times (\frac{2}{3})^{n-k}
$$

It is:

$$
p(k,n) = \binom{n}{k} \times \frac{2^{n-k}}{3^k}
$$


By the way, the recursive way is:

$$
p(k,n) = \frac{1}{3}p(k-1,n-1) + \frac{2}{3}p(k, n-1)
$$

## 10.4


:::info{title="Question"}
What is the expected number of c's in a word of length n, drawn uniformly at random from the set of all words (over Σ) of length n?
:::

For every character, $c_i$, in n-word, the possibility of 'c', $p_i$, is $\frac{1}{3}$.

The expected number of c is:

$$
\sum_{i=1}^n p_i \times length(w_i) = \frac{1}{3} \times 1 + \frac{1}{3} \times 1 ... + \frac{1}{3} \times 1 = \frac{n}{3}
$$