[libcamera-devel,v6,04/10] ipa: Add common contrast based AF implementation

18511 diff mbox series

Create a new class with contrast based Auto Focus implementation
using hill climbing algorithm. This common implementation is independent
of platform specific code. This way, each platform can just implement
contrast calculation and run the AF control loop basing on this class.
This implementation is based on the code that was common for IPU3
and RPi AF algorithms.

Signed-off-by: Daniel Semkowicz <dse@thaumatec.com>
---
 .../libipa/algorithms/af_hill_climbing.cpp    | 374 ++++++++++++++++++
 src/ipa/libipa/algorithms/af_hill_climbing.h  |  91 +++++
 src/ipa/libipa/algorithms/meson.build         |   2 +
 3 files changed, 467 insertions(+)
 create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.cpp
 create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.h

Hi Daniel

On Fri, Mar 31, 2023 at 10:19:24AM +0200, Daniel Semkowicz via libcamera-devel wrote:
> Create a new class with contrast based Auto Focus implementation
> using hill climbing algorithm. This common implementation is independent
> of platform specific code. This way, each platform can just implement
> contrast calculation and run the AF control loop basing on this class.
> This implementation is based on the code that was common for IPU3
> and RPi AF algorithms.
>
> Signed-off-by: Daniel Semkowicz <dse@thaumatec.com>
> ---
>  .../libipa/algorithms/af_hill_climbing.cpp    | 374 ++++++++++++++++++
>  src/ipa/libipa/algorithms/af_hill_climbing.h  |  91 +++++
>  src/ipa/libipa/algorithms/meson.build         |   2 +
>  3 files changed, 467 insertions(+)
>  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.cpp
>  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.h
>
> diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.cpp b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> new file mode 100644
> index 00000000..244b8803
> --- /dev/null
> +++ b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> @@ -0,0 +1,374 @@
> +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> +/*
> + * Copyright (C) 2021, Red Hat
> + * Copyright (C) 2022, Ideas On Board
> + * Copyright (C) 2023, Theobroma Systems
> + *
> + * af_hill_climbing.cpp - AF contrast based hill climbing common algorithm
> + */
> +
> +#include "af_hill_climbing.h"
> +
> +#include "libcamera/internal/yaml_parser.h"
> +
> +/**
> + * \file af_hill_climbing.h
> + * \brief AF contrast based hill climbing common algorithm
> + */
> +
> +namespace libcamera {
> +
> +namespace ipa::algorithms {
> +
> +LOG_DEFINE_CATEGORY(Af)
> +
> +/**
> + * \class AfHillClimbing
> + * \brief Contrast based hill climbing auto focus control algorithm
> + * implementation
> + *
> + * Control part of the auto focus algorithm. It calculates the lens position
> + * based on the contrast measure supplied by the platform-specific
> + * implementation. This way it is independent from the platform.
> + *
> + * Platform layer that use this algorithm should call process() function
> + * for each each frame and set the lens to the calculated position.
> + *
> + * Focus search is divided into two phases:
> + * 1. coarse search,
> + * 2. fine search.
> + *
> + * In the first phase, the lens is moved with bigger steps to quickly find
> + * a rough position for the best focus. Then, based on the outcome of coarse
> + * search, the second phase is executed. Lens is moved with smaller steps
> + * in a limited range within the rough position to find the exact position
> + * for best focus.
> + *
> + * Tuning file parameters:
> + * - **coarse-search-step:** The value by which the lens position will change
> + *   in one step in the *coarse search* phase. Unit is lens specific.
> + * - **fine-search-step:** The value by which the lens position will change
> + *   in one step in the *fine search* phase. Unit is lens specific.
> + * - **fine-search-range:** Search range in the *fine search* phase, expressed
> + *   as a percentage of the coarse search result. Valid values are
> + *   in the [0, 100] interval. Value 5 means 5%. If coarse search stopped
> + *   at value 200, the fine search range will be [190, 210].
> + * - **max-variance-change:** ratio of contrast variance change in the
> + *   *continuous mode* needed for triggering the focus change. When the variance
> + *   change exceeds this value, focus search will be triggered. Valid values are
> + *   in the [0.0, 1.0] interval.
> + * .
> + *
> + * \todo Search range in the *fine search* phase should depend on the lens
> + * movement range rather than coarse search result.
> + * \todo Implement setRange.
> + * \todo Implement setSpeed.
> + * \todo Implement setMeteringMode.
> + * \todo Implement setWindows.
> + * \todo Implement the AfPauseDeferred mode.
> + */
> +
> +/**
> + * \brief Initialize the AfHillClimbing with lens configuration and tuning data
> + * \param[in] minFocusPosition Minimum position supported by camera lens
> + * \param[in] maxFocusPosition Maximum position supported by camera lens
> + * \param[in] tuningData The tuning data for the algorithm
> + *
> + * This method should be called in the libcamera::ipa::Algorithm::init()
> + * method of the platform layer.
> + *
> + * \return 0 if successful, an error code otherwise
> + */
> +int AfHillClimbing::init(int32_t minFocusPosition, int32_t maxFocusPosition,
> +			 const YamlObject &tuningData)
> +{
> +	minLensPosition_ = minFocusPosition;
> +	maxLensPosition_ = maxFocusPosition;

ok, I now see why you need to save minLensPosition_ and
maxLensPosition_ in the context at init() time.

I'm debated if this bits could be moved to configure(), but whatever
feels right to you works for me here.

Looking at the diff with v5, this now looks good to me
Reviewed-by: Jacopo Mondi <jacopo.mondi@ideasonboard.com>

Thanks
  j

> +
> +	coarseSearchStep_ = tuningData["coarse-search-step"].get<uint32_t>(30);
> +	fineSearchStep_ = tuningData["fine-search-step"].get<uint32_t>(1);
> +	fineRange_ = tuningData["fine-search-range"].get<uint32_t>(5);
> +	fineRange_ /= 100;
> +	maxChange_ = tuningData["max-variance-change"].get<double>(0.5);
> +
> +	LOG(Af, Debug) << "coarseSearchStep_: " << coarseSearchStep_
> +		       << ", fineSearchStep_: " << fineSearchStep_
> +		       << ", fineRange_: " << fineRange_
> +		       << ", maxChange_: " << maxChange_;
> +
> +	return 0;
> +}
> +
> +/**
> + * \brief Run the auto focus algorithm loop
> + * \param[in] currentContrast New value of contrast measured for current frame
> + *
> + * This method should be called in the libcamera::ipa::Algorithm::process()
> + * method of the platform layer for each frame.
> + *
> + * Contrast value supplied in the \p currentContrast parameter can be platform
> + * specific. The only requirement is the contrast value must increase with
> + * the increasing image focus. Contrast value must be highest when image is in
> + * focus.
> + *
> + * \return New lens position calculated by the AF algorithm
> + */
> +int32_t AfHillClimbing::process(double currentContrast)
> +{
> +	currentContrast_ = currentContrast;
> +
> +	if (shouldSkipFrame())
> +		return lensPosition_;
> +
> +	switch (mode_) {
> +	case controls::AfModeManual:
> +		/* Nothing to process. */
> +		break;
> +	case controls::AfModeAuto:
> +		processAutoMode();
> +		break;
> +	case controls::AfModeContinuous:
> +		processContinuousMode();
> +		break;
> +	}
> +
> +	return lensPosition_;
> +}
> +
> +void AfHillClimbing::processAutoMode()
> +{
> +	if (state_ == controls::AfStateScanning) {
> +		afCoarseScan();
> +		afFineScan();
> +	}
> +}
> +
> +void AfHillClimbing::processContinuousMode()
> +{
> +	/* If we are in a paused state, we won't process the stats. */
> +	if (pauseState_ == controls::AfPauseStatePaused)
> +		return;
> +
> +	if (state_ == controls::AfStateScanning) {
> +		afCoarseScan();
> +		afFineScan();
> +		return;
> +	}
> +
> +	/*
> +	 * AF scan can be started at any moment in AfModeContinuous,
> +	 * except when the state is already AfStateScanning.
> +	 */
> +	if (afIsOutOfFocus())
> +		afReset();
> +}
> +
> +/**
> + * \brief Request AF to skip n frames
> + * \param[in] n Number of frames to be skipped
> + *
> + * For the requested number of frames, the AF calculation will be skipped
> + * and lens position will not change. The platform layer still needs to
> + * call process() function for each frame during this time.
> + * This function can be used by the platform layer if the hardware needs more
> + * time for some operations.
> + *
> + * The number of the requested frames (\p n) will be applied only if \p n has
> + * higher value than the number of frames already requested to be skipped.
> + * For example, if *skipFrames(5)* was already called for the current frame,
> + * then calling *skipFrames(3)* will not override the previous request
> + * and 5 frames will be skipped.
> + */
> +void AfHillClimbing::skipFrames(uint32_t n)
> +{
> +	if (n > framesToSkip_)
> +		framesToSkip_ = n;
> +}
> +
> +void AfHillClimbing::setMode(controls::AfModeEnum mode)
> +{
> +	if (mode == mode_)
> +		return;
> +
> +	LOG(Af, Debug) << "Switched AF mode from " << mode_ << " to " << mode;
> +	mode_ = mode;
> +
> +	state_ = controls::AfStateIdle;
> +	pauseState_ = controls::AfPauseStateRunning;
> +
> +	if (mode_ == controls::AfModeContinuous)
> +		afReset();
> +}
> +
> +void AfHillClimbing::setRange([[maybe_unused]] controls::AfRangeEnum range)
> +{
> +	LOG(Af, Error) << "setRange() not implemented!";
> +}
> +
> +void AfHillClimbing::setSpeed([[maybe_unused]] controls::AfSpeedEnum speed)
> +{
> +	LOG(Af, Error) << "setSpeed() not implemented!";
> +}
> +
> +void AfHillClimbing::setMeteringMode([[maybe_unused]] controls::AfMeteringEnum metering)
> +{
> +	LOG(Af, Error) << "setMeteringMode() not implemented!";
> +}
> +
> +void AfHillClimbing::setWindows([[maybe_unused]] Span<const Rectangle> windows)
> +{
> +	LOG(Af, Error) << "setWindows() not implemented!";
> +}
> +
> +void AfHillClimbing::setTrigger(controls::AfTriggerEnum trigger)
> +{
> +	if (mode_ != controls::AfModeAuto) {
> +		LOG(Af, Warning)
> +			<< "setTrigger() not valid in mode " << mode_;
> +		return;
> +	}
> +
> +	LOG(Af, Debug) << "Trigger called with " << trigger;
> +
> +	switch (trigger) {
> +	case controls::AfTriggerStart:
> +		afReset();
> +		break;
> +	case controls::AfTriggerCancel:
> +		state_ = controls::AfStateIdle;
> +		break;
> +	}
> +}
> +
> +void AfHillClimbing::setPause(controls::AfPauseEnum pause)
> +{
> +	if (mode_ != controls::AfModeContinuous) {
> +		LOG(Af, Warning)
> +			<< "setPause() not valid in mode " << mode_;
> +		return;
> +	}
> +
> +	switch (pause) {
> +	case controls::AfPauseImmediate:
> +		pauseState_ = controls::AfPauseStatePaused;
> +		break;
> +	case controls::AfPauseDeferred:
> +		LOG(Af, Warning) << "AfPauseDeferred is not supported!";
> +		break;
> +	case controls::AfPauseResume:
> +		pauseState_ = controls::AfPauseStateRunning;
> +		break;
> +	}
> +}
> +
> +void AfHillClimbing::setLensPosition(float lensPosition)
> +{
> +	if (mode_ != controls::AfModeManual) {
> +		LOG(Af, Warning)
> +			<< "setLensPosition() not valid in mode " << mode_;
> +		return;
> +	}
> +
> +	lensPosition_ = static_cast<int32_t>(lensPosition);
> +
> +	LOG(Af, Debug) << "Requesting lens position " << lensPosition_;
> +}
> +
> +void AfHillClimbing::afCoarseScan()
> +{
> +	if (coarseCompleted_)
> +		return;
> +
> +	if (afScan(coarseSearchStep_)) {
> +		coarseCompleted_ = true;
> +		maxContrast_ = 0;
> +		const auto diff = static_cast<int32_t>(
> +			std::abs(lensPosition_) * fineRange_);
> +		lensPosition_ = std::max(lensPosition_ - diff, minLensPosition_);
> +		maxStep_ = std::min(lensPosition_ + diff, maxLensPosition_);
> +	}
> +}
> +
> +void AfHillClimbing::afFineScan()
> +{
> +	if (!coarseCompleted_)
> +		return;
> +
> +	if (afScan(fineSearchStep_)) {
> +		LOG(Af, Debug) << "AF found the best focus position!";
> +		state_ = controls::AfStateFocused;
> +	}
> +}
> +
> +bool AfHillClimbing::afScan(uint32_t steps)
> +{
> +	if (lensPosition_ + static_cast<int32_t>(steps) > maxStep_) {
> +		/* If the max step is reached, move lens to the position. */
> +		lensPosition_ = bestPosition_;
> +		return true;
> +	}
> +
> +	/*
> +	 * Find the maximum of the variance by estimating its derivative.
> +	 * If the direction changes, it means we have passed a maximum one step
> +	 * before.
> +	 */
> +	if ((currentContrast_ - maxContrast_) >= -(maxContrast_ * 0.1)) {
> +		/*
> +		 * Positive and zero derivative:
> +		 * The variance is still increasing. The focus could be
> +		 * increased for the next comparison. Also, the max variance
> +		 * and previous focus value are updated.
> +		 */
> +		bestPosition_ = lensPosition_;
> +		lensPosition_ += static_cast<int32_t>(steps);
> +		maxContrast_ = currentContrast_;
> +	} else {
> +		/*
> +		 * Negative derivative:
> +		 * The variance starts to decrease, which means the maximum
> +		 * variance is found. Set focus step to previous good one,
> +		 * then return immediately.
> +		 */
> +		lensPosition_ = bestPosition_;
> +		return true;
> +	}
> +
> +	LOG(Af, Debug) << "Previous step is " << bestPosition_
> +		       << ", Current step is " << lensPosition_;
> +	return false;
> +}
> +
> +void AfHillClimbing::afReset()
> +{
> +	LOG(Af, Debug) << "Reset AF parameters";
> +	lensPosition_ = minLensPosition_;
> +	maxStep_ = maxLensPosition_;
> +	state_ = controls::AfStateScanning;
> +	coarseCompleted_ = false;
> +	maxContrast_ = 0.0;
> +	skipFrames(1);
> +}
> +
> +bool AfHillClimbing::afIsOutOfFocus() const
> +{
> +	const double diff_var = std::abs(currentContrast_ - maxContrast_);
> +	const double var_ratio = diff_var / maxContrast_;
> +	LOG(Af, Debug) << "Variance change rate: " << var_ratio
> +		       << ", Current lens step: " << lensPosition_;
> +	return var_ratio > maxChange_;
> +}
> +
> +bool AfHillClimbing::shouldSkipFrame()
> +{
> +	if (framesToSkip_ > 0) {
> +		framesToSkip_--;
> +		return true;
> +	}
> +
> +	return false;
> +}
> +
> +} /* namespace ipa::algorithms */
> +
> +} /* namespace libcamera */
> diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.h b/src/ipa/libipa/algorithms/af_hill_climbing.h
> new file mode 100644
> index 00000000..2147939b
> --- /dev/null
> +++ b/src/ipa/libipa/algorithms/af_hill_climbing.h
> @@ -0,0 +1,91 @@
> +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> +/*
> + * Copyright (C) 2021, Red Hat
> + * Copyright (C) 2022, Ideas On Board
> + * Copyright (C) 2023, Theobroma Systems
> + *
> + * af_hill_climbing.h - AF contrast based hill climbing common algorithm
> + */
> +
> +#pragma once
> +
> +#include <libcamera/base/log.h>
> +
> +#include "af.h"
> +
> +namespace libcamera {
> +
> +class YamlObject;
> +
> +namespace ipa::algorithms {
> +
> +LOG_DECLARE_CATEGORY(Af)
> +
> +class AfHillClimbing : public Af
> +{
> +public:
> +	int init(int32_t minFocusPosition, int32_t maxFocusPosition,
> +		 const YamlObject &tuningData);
> +	int32_t process(double currentContrast);
> +	void skipFrames(uint32_t n);
> +
> +	controls::AfStateEnum state() override { return state_; }
> +	controls::AfPauseStateEnum pauseState() override { return pauseState_; }
> +
> +private:
> +	void setMode(controls::AfModeEnum mode) override;
> +	void setRange(controls::AfRangeEnum range) override;
> +	void setSpeed(controls::AfSpeedEnum speed) override;
> +	void setMeteringMode(controls::AfMeteringEnum metering) override;
> +	void setWindows(Span<const Rectangle> windows) override;
> +	void setTrigger(controls::AfTriggerEnum trigger) override;
> +	void setPause(controls::AfPauseEnum pause) override;
> +	void setLensPosition(float lensPosition) override;
> +
> +	void processAutoMode();
> +	void processContinuousMode();
> +	void afCoarseScan();
> +	void afFineScan();
> +	bool afScan(uint32_t steps);
> +	void afReset();
> +	[[nodiscard]] bool afIsOutOfFocus() const;
> +	bool shouldSkipFrame();
> +
> +	controls::AfModeEnum mode_ = controls::AfModeManual;
> +	controls::AfStateEnum state_ = controls::AfStateIdle;
> +	controls::AfPauseStateEnum pauseState_ = controls::AfPauseStateRunning;
> +
> +	/* Current focus lens position. */
> +	int32_t lensPosition_ = 0;
> +	/* Local optimum focus lens position during scanning. */
> +	int32_t bestPosition_ = 0;
> +
> +	/* Current AF statistic contrast. */
> +	double currentContrast_ = 0;
> +	/* It is used to determine the derivative during scanning */
> +	double maxContrast_ = 0;
> +	/* The designated maximum range of focus scanning. */
> +	int32_t maxStep_ = 0;
> +	/* If the coarse scan completes, it is set to true. */
> +	bool coarseCompleted_ = false;
> +
> +	uint32_t framesToSkip_ = 0;
> +
> +	/* Position limits of the focus lens. */
> +	int32_t minLensPosition_;
> +	int32_t maxLensPosition_;
> +
> +	/* Minimum position step for searching appropriate focus. */
> +	uint32_t coarseSearchStep_;
> +	uint32_t fineSearchStep_;
> +
> +	/* Fine scan range 0 < fineRange_ < 1. */
> +	double fineRange_;
> +
> +	/* Max ratio of variance change, 0.0 < maxChange_ < 1.0. */
> +	double maxChange_;
> +};
> +
> +} /* namespace ipa::algorithms */
> +
> +} /* namespace libcamera */
> diff --git a/src/ipa/libipa/algorithms/meson.build b/src/ipa/libipa/algorithms/meson.build
> index 3df4798f..20e437fc 100644
> --- a/src/ipa/libipa/algorithms/meson.build
> +++ b/src/ipa/libipa/algorithms/meson.build
> @@ -2,8 +2,10 @@
>
>  libipa_algorithms_headers = files([
>      'af.h',
> +    'af_hill_climbing.h',
>  ])
>
>  libipa_algorithms_sources = files([
>      'af.cpp',
> +    'af_hill_climbing.cpp',
>  ])
> --
> 2.39.2
>

Hi Laurent,

Thank you for the review.

On Wed, Apr 26, 2023 at 4:43 AM Laurent Pinchart
<laurent.pinchart@ideasonboard.com> wrote:
>
> Hi Daniel,
>
> Thank you for the patch.
>
> On Fri, Mar 31, 2023 at 10:19:24AM +0200, Daniel Semkowicz via libcamera-devel wrote:
> > Create a new class with contrast based Auto Focus implementation
> > using hill climbing algorithm. This common implementation is independent
> > of platform specific code. This way, each platform can just implement
> > contrast calculation and run the AF control loop basing on this class.
> > This implementation is based on the code that was common for IPU3
> > and RPi AF algorithms.
>
> How difficult would it be to port the IPU3 IPA module to use this class
> ? Having two users would help showing that the interface is generic
> enough.

The algorithm implementation is similar, so it should not be difficult.
This is what I would really like to see, because it would simplify the code :)
For basic version, without option to set AF windows, it should be just replacing
the algorithm code with the calls to the AfHillClimbing. AfHillClimbing is based
on the IPU3 code, so the platform code is already in the correct places.
It would be good to expose lens limits to the IPA for correct operation with
different cameras, because currently limits are hard-coded to 0-1023. Something
similar to patch 02 of this series would be needed.

Unfortunately, I do not have access to IPU3 hardware to work on such code.

>
> > Signed-off-by: Daniel Semkowicz <dse@thaumatec.com>
> > ---
> >  .../libipa/algorithms/af_hill_climbing.cpp    | 374 ++++++++++++++++++
> >  src/ipa/libipa/algorithms/af_hill_climbing.h  |  91 +++++
> >  src/ipa/libipa/algorithms/meson.build         |   2 +
> >  3 files changed, 467 insertions(+)
> >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.cpp
> >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.h
> >
> > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.cpp b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > new file mode 100644
> > index 00000000..244b8803
> > --- /dev/null
> > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > @@ -0,0 +1,374 @@
> > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > +/*
> > + * Copyright (C) 2021, Red Hat
> > + * Copyright (C) 2022, Ideas On Board
> > + * Copyright (C) 2023, Theobroma Systems
> > + *
> > + * af_hill_climbing.cpp - AF contrast based hill climbing common algorithm
>
> s/contract based/constrast-based/
>
> Same below in this file and in af_hill_climbing.h.
>
> > + */
> > +
> > +#include "af_hill_climbing.h"
> > +
> > +#include "libcamera/internal/yaml_parser.h"
> > +
> > +/**
> > + * \file af_hill_climbing.h
> > + * \brief AF contrast based hill climbing common algorithm
> > + */
> > +
> > +namespace libcamera {
> > +
> > +namespace ipa::algorithms {
> > +
> > +LOG_DEFINE_CATEGORY(Af)
> > +
> > +/**
> > + * \class AfHillClimbing
> > + * \brief Contrast based hill climbing auto focus control algorithm
> > + * implementation
> > + *
> > + * Control part of the auto focus algorithm. It calculates the lens position
> > + * based on the contrast measure supplied by the platform-specific
> > + * implementation. This way it is independent from the platform.
>
> Many platforms have the ability to calculate focus statistics separately
> on different regions of the image (quite often using a grid, sometimes
> with more freely-configurable regions, and I've seen at least one
> platform where the regions can be ellipses instead of rectangles). Do
> you think it will be possible to support those in the future, possibly
> to implement touch-to-focus, in this class in a generic way, or would
> the platform-specific definition of the zones require moving some of the
> code from this class to platform-specific classes ?

If there is more than one focus window, there are different possibilities what
We can do with such information. For example, We can choose the window with the
highest peak contrast value or the position closest to the camera.
This is a bigger topic for the discussion. I can imagine additional AF control
that allows you to choose the priority when using multiple AF windows.
Probably it will be possible to do this in a generic way as how it is already
done for the one window. AfHillClimbing only expects generic contrast value
that rises with the focus is "better". AfHillClimbing will request platform
part to configure AF windows and will expect the platform part to supply the
expected number of measured contrast values (for each window).

>
> > + *
> > + * Platform layer that use this algorithm should call process() function
> > + * for each each frame and set the lens to the calculated position.
> > + *
> > + * Focus search is divided into two phases:
> > + * 1. coarse search,
> > + * 2. fine search.
> > + *
> > + * In the first phase, the lens is moved with bigger steps to quickly find
> > + * a rough position for the best focus. Then, based on the outcome of coarse
> > + * search, the second phase is executed. Lens is moved with smaller steps
>
> s/Lens/The lens/
>
> > + * in a limited range within the rough position to find the exact position
>
> s/within/around/
>
> > + * for best focus.
> > + *
> > + * Tuning file parameters:
>
> We use camelCase for tuning file parameters in the rkisp1 and ipu3
> tuning files, while Raspberry Pi uses a mix of snake_case and
> kebab-case. Given that this class is supposed to be
> platform-independent, I'm not sure I like parsing data directly from a
> tuning file. I think it be better to create a structure to represent the
> configuration data, fill it from the tuning file in platform-specific
> code, and pass it to the init function.

I had not noticed this difference before. I think your approach is better,
and I will rework it this way.

>
> > + * - **coarse-search-step:** The value by which the lens position will change
> > + *   in one step in the *coarse search* phase. Unit is lens specific.
>
> s/Unit/The unit/
>
> Same below.
>
> While the unit can be platform specific, it would be useful to document
> what it refers to. If my understanding is correct, the coarse step is
> expressed in the same units as the lens minimum and maximum positions.
> Could you please capture that ?
>
> I'm also wondering if we should express the coarse search step as a
> percentage of the lens movement range, to make is less platform
> specific.

This makes sense to express the coarse search step as a percentage of the lens
movement range. Especially, that lens limits are now passed from the v4l
subdevice internally to the IPA, so the user does not need to know what the
correct values are.

>
> > + * - **fine-search-step:** The value by which the lens position will change
> > + *   in one step in the *fine search* phase. Unit is lens specific.
> > + * - **fine-search-range:** Search range in the *fine search* phase, expressed
> > + *   as a percentage of the coarse search result. Valid values are
> > + *   in the [0, 100] interval. Value 5 means 5%. If coarse search stopped
> > + *   at value 200, the fine search range will be [190, 210].
>
> I would have envisioned doing the fine search in the full range around
> the position found by the coarse search, that is in the [coarse search
> position - coarse search step, coarse search position + coarse search
> step]. Going beyond that means we'll scan positions that will have lower
> contrast values (assuming the coarse search found the global maximum,
> not a local extremum). Using a (possibly significantly) smaller range
> means we could quite likely miss the real maximum.
>
> Are there expected use cases for not handling the fine search range
> automatically ?

This is the implementation currently used in the IPU3 and there were some
discussions in the previous version of this patch, why it is done this way.
Unfortunately, We can only guess the reason. Automating this seems to make
sense, especially, that it is not difficult and I do not see any disadvantages.

>
> > + * - **max-variance-change:** ratio of contrast variance change in the
> > + *   *continuous mode* needed for triggering the focus change. When the variance
> > + *   change exceeds this value, focus search will be triggered. Valid values are
> > + *   in the [0.0, 1.0] interval.
>
> Both the fine search range and max variance change are relative values
> in the [0%, 100%] range, with the former expressed as a percentage
> integer value and the latter a float. Is there a reason for that, or
> could both values be expressed the same way ? I think I'd go for floats
> in both cases.
>
> I'm tempted to rename "max-variance-change" to
> "variance-change-threshold" as it's a threshold to trigger a focus
> search. Same for the maxChange_ member variable.

I agree with it.

>
> > + * .
>
> Stray '.' ?

Dot is used to explicitly mark the end of the list in the Doxygen.
Without the dot, I had some formatting problems here.

>
> > + *
> > + * \todo Search range in the *fine search* phase should depend on the lens
> > + * movement range rather than coarse search result.
>
> This sounds like a quite simple change, should it be done already, or
> are there blockers ? I'm also puzzled by why the fine search range is a
> percentage of the coarse search result, what's the reason for that ?
>
> > + * \todo Implement setRange.
> > + * \todo Implement setSpeed.
> > + * \todo Implement setMeteringMode.
> > + * \todo Implement setWindows.
> > + * \todo Implement the AfPauseDeferred mode.
> > + */
> > +
> > +/**
> > + * \brief Initialize the AfHillClimbing with lens configuration and tuning data
> > + * \param[in] minFocusPosition Minimum position supported by camera lens
> > + * \param[in] maxFocusPosition Maximum position supported by camera lens
> > + * \param[in] tuningData The tuning data for the algorithm
> > + *
> > + * This method should be called in the libcamera::ipa::Algorithm::init()
> > + * method of the platform layer.
>
> s/method/function/
>
> Same below.
>
> > + *
> > + * \return 0 if successful, an error code otherwise
> > + */
> > +int AfHillClimbing::init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > +                      const YamlObject &tuningData)
> > +{
> > +     minLensPosition_ = minFocusPosition;
> > +     maxLensPosition_ = maxFocusPosition;
> > +
> > +     coarseSearchStep_ = tuningData["coarse-search-step"].get<uint32_t>(30);
> > +     fineSearchStep_ = tuningData["fine-search-step"].get<uint32_t>(1);
> > +     fineRange_ = tuningData["fine-search-range"].get<uint32_t>(5);
> > +     fineRange_ /= 100;
> > +     maxChange_ = tuningData["max-variance-change"].get<double>(0.5);
> > +
> > +     LOG(Af, Debug) << "coarseSearchStep_: " << coarseSearchStep_
> > +                    << ", fineSearchStep_: " << fineSearchStep_
> > +                    << ", fineRange_: " << fineRange_
> > +                    << ", maxChange_: " << maxChange_;
> > +
> > +     return 0;
> > +}
> > +
> > +/**
> > + * \brief Run the auto focus algorithm loop
> > + * \param[in] currentContrast New value of contrast measured for current frame
> > + *
> > + * This method should be called in the libcamera::ipa::Algorithm::process()
> > + * method of the platform layer for each frame.
> > + *
> > + * Contrast value supplied in the \p currentContrast parameter can be platform
>
> We use \a for function parameters, not \p. I'm not sure if one of the
> two is intrinsincly better than the other, but we should be consistent.
>
> This comment applies to the whole patch series, where applicable.

I will go through the series and change that.

>
> > + * specific. The only requirement is the contrast value must increase with
> > + * the increasing image focus. Contrast value must be highest when image is in
> > + * focus.
> > + *
> > + * \return New lens position calculated by the AF algorithm
> > + */
> > +int32_t AfHillClimbing::process(double currentContrast)
> > +{
> > +     currentContrast_ = currentContrast;
> > +
> > +     if (shouldSkipFrame())
> > +             return lensPosition_;
> > +
> > +     switch (mode_) {
> > +     case controls::AfModeManual:
> > +             /* Nothing to process. */
> > +             break;
> > +     case controls::AfModeAuto:
> > +             processAutoMode();
> > +             break;
> > +     case controls::AfModeContinuous:
> > +             processContinuousMode();
> > +             break;
> > +     }
> > +
> > +     return lensPosition_;
> > +}
> > +
> > +void AfHillClimbing::processAutoMode()
> > +{
> > +     if (state_ == controls::AfStateScanning) {
> > +             afCoarseScan();
> > +             afFineScan();
>
> The two functions are always called together, and they're both fairly
> small. I'd combine them into a single afScan().

I will try to improve that.

>
> > +     }
> > +}
> > +
> > +void AfHillClimbing::processContinuousMode()
> > +{
> > +     /* If we are in a paused state, we won't process the stats. */
> > +     if (pauseState_ == controls::AfPauseStatePaused)
> > +             return;
> > +
> > +     if (state_ == controls::AfStateScanning) {
> > +             afCoarseScan();
> > +             afFineScan();
> > +             return;
> > +     }
> > +
> > +     /*
> > +      * AF scan can be started at any moment in AfModeContinuous,
> > +      * except when the state is already AfStateScanning.
> > +      */
> > +     if (afIsOutOfFocus())
> > +             afReset();
> > +}
> > +
> > +/**
> > + * \brief Request AF to skip n frames
> > + * \param[in] n Number of frames to be skipped
> > + *
> > + * For the requested number of frames, the AF calculation will be skipped
> > + * and lens position will not change. The platform layer still needs to
> > + * call process() function for each frame during this time.
>
> s/call process() function/call the process() function/
>
> > + * This function can be used by the platform layer if the hardware needs more
> > + * time for some operations.
> > + *
> > + * The number of the requested frames (\p n) will be applied only if \p n has
> > + * higher value than the number of frames already requested to be skipped.
> > + * For example, if *skipFrames(5)* was already called for the current frame,
>
> Code spans use back-quotes, see
> https://www.doxygen.nl/manual/markdown.html#md_codespan.
>
> > + * then calling *skipFrames(3)* will not override the previous request
> > + * and 5 frames will be skipped.
> > + */
> > +void AfHillClimbing::skipFrames(uint32_t n)
> > +{
> > +     if (n > framesToSkip_)
> > +             framesToSkip_ = n;
> > +}
> > +
> > +void AfHillClimbing::setMode(controls::AfModeEnum mode)
> > +{
> > +     if (mode == mode_)
> > +             return;
> > +
> > +     LOG(Af, Debug) << "Switched AF mode from " << mode_ << " to " << mode;
> > +     mode_ = mode;
> > +
> > +     state_ = controls::AfStateIdle;
> > +     pauseState_ = controls::AfPauseStateRunning;
> > +
> > +     if (mode_ == controls::AfModeContinuous)
> > +             afReset();
> > +}
> > +
> > +void AfHillClimbing::setRange([[maybe_unused]] controls::AfRangeEnum range)
> > +{
> > +     LOG(Af, Error) << "setRange() not implemented!";
> > +}
> > +
> > +void AfHillClimbing::setSpeed([[maybe_unused]] controls::AfSpeedEnum speed)
> > +{
> > +     LOG(Af, Error) << "setSpeed() not implemented!";
> > +}
> > +
> > +void AfHillClimbing::setMeteringMode([[maybe_unused]] controls::AfMeteringEnum metering)
> > +{
> > +     LOG(Af, Error) << "setMeteringMode() not implemented!";
> > +}
> > +
> > +void AfHillClimbing::setWindows([[maybe_unused]] Span<const Rectangle> windows)
> > +{
> > +     LOG(Af, Error) << "setWindows() not implemented!";
> > +}
> > +
> > +void AfHillClimbing::setTrigger(controls::AfTriggerEnum trigger)
> > +{
> > +     if (mode_ != controls::AfModeAuto) {
> > +             LOG(Af, Warning)
> > +                     << "setTrigger() not valid in mode " << mode_;
> > +             return;
> > +     }
> > +
> > +     LOG(Af, Debug) << "Trigger called with " << trigger;
> > +
> > +     switch (trigger) {
> > +     case controls::AfTriggerStart:
> > +             afReset();
> > +             break;
> > +     case controls::AfTriggerCancel:
> > +             state_ = controls::AfStateIdle;
> > +             break;
> > +     }
>
> All this logic seems to implement requirements set by the AF controls
> definitions, not specific to this class. Should it be moved to the base
> AF class ? Same for setPause().

There was a discussion on similar topic in the previous version. Conclusion was
that at this point it is hard to decide what will be completely reusable by
other implementations, so only the interface is defined in the Af and most of
the implementation is done in the AfHillClimbing. We can move parts of the code
to the Af later, when more things become clear.

>
> > +}
> > +
> > +void AfHillClimbing::setPause(controls::AfPauseEnum pause)
> > +{
> > +     if (mode_ != controls::AfModeContinuous) {
> > +             LOG(Af, Warning)
> > +                     << "setPause() not valid in mode " << mode_;
> > +             return;
> > +     }
> > +
> > +     switch (pause) {
> > +     case controls::AfPauseImmediate:
> > +             pauseState_ = controls::AfPauseStatePaused;
> > +             break;
> > +     case controls::AfPauseDeferred:
> > +             LOG(Af, Warning) << "AfPauseDeferred is not supported!";
> > +             break;
> > +     case controls::AfPauseResume:
> > +             pauseState_ = controls::AfPauseStateRunning;
> > +             break;
> > +     }
> > +}
> > +
> > +void AfHillClimbing::setLensPosition(float lensPosition)
> > +{
> > +     if (mode_ != controls::AfModeManual) {
> > +             LOG(Af, Warning)
> > +                     << "setLensPosition() not valid in mode " << mode_;
> > +             return;
> > +     }
> > +
> > +     lensPosition_ = static_cast<int32_t>(lensPosition);
>
> The LensPosition control is defined in dioptres units. Unless I'm
> mistaken, the implementation in this class doesn't match that. This
> should be fixed, not necessarily with a fully calibrated implementation,
> but at least to map 0.0 to infinity and the maximum value of the lens
> position to the closest possible focus.

Ok, so just for confirmation. For example, for the VCM driver that I use,
the V4L2_CID_FOCUS_ABSOLUTE values are in 0-1023 range and V4L documentation
specifies that positive values set the focus closer to the camera.
In this case, the LensPosition will simply map to 0.0 - 1023.0.
Do I understand your approach correctly?

>
> > +
> > +     LOG(Af, Debug) << "Requesting lens position " << lensPosition_;
> > +}
> > +
> > +void AfHillClimbing::afCoarseScan()
> > +{
> > +     if (coarseCompleted_)
> > +             return;
> > +
> > +     if (afScan(coarseSearchStep_)) {
> > +             coarseCompleted_ = true;
> > +             maxContrast_ = 0;
> > +             const auto diff = static_cast<int32_t>(
> > +                     std::abs(lensPosition_) * fineRange_);
> > +             lensPosition_ = std::max(lensPosition_ - diff, minLensPosition_);
> > +             maxStep_ = std::min(lensPosition_ + diff, maxLensPosition_);
>
> I think the intent here it to set the scan range to [coarse position -
> diff, coarse position + diff], but as you modify lensPosition_ first,
> you effectively set it to [coarse position - diff, coarse position].

You are right... I will fix that :)

>
> Reading the code, maxStep_ seems to store a lens position, not a step.
> Is this correct ? If so, please rename the variable accordingly.

Yes, this is correct.

>
> > +     }
> > +}
> > +
> > +void AfHillClimbing::afFineScan()
> > +{
> > +     if (!coarseCompleted_)
> > +             return;
> > +
> > +     if (afScan(fineSearchStep_)) {
> > +             LOG(Af, Debug) << "AF found the best focus position!";
> > +             state_ = controls::AfStateFocused;
> > +     }
> > +}
> > +
> > +bool AfHillClimbing::afScan(uint32_t steps)
> > +{
> > +     if (lensPosition_ + static_cast<int32_t>(steps) > maxStep_) {
> > +             /* If the max step is reached, move lens to the position. */
> > +             lensPosition_ = bestPosition_;
> > +             return true;
> > +     }
> > +
> > +     /*
> > +      * Find the maximum of the variance by estimating its derivative.
> > +      * If the direction changes, it means we have passed a maximum one step
> > +      * before.
> > +      */
> > +     if ((currentContrast_ - maxContrast_) >= -(maxContrast_ * 0.1)) {
> > +             /*
> > +              * Positive and zero derivative:
> > +              * The variance is still increasing. The focus could be
> > +              * increased for the next comparison. Also, the max variance
> > +              * and previous focus value are updated.
> > +              */
> > +             bestPosition_ = lensPosition_;
> > +             lensPosition_ += static_cast<int32_t>(steps);
> > +             maxContrast_ = currentContrast_;
> > +     } else {
> > +             /*
> > +              * Negative derivative:
> > +              * The variance starts to decrease, which means the maximum
> > +              * variance is found. Set focus step to previous good one,
> > +              * then return immediately.
>
> Isn't this very prone to stopping on a local extremum ?

It is, and this is intended. When there are two objects on the scene, We will
just focus on the one closer to the camera. It is mitigated a bit, by setting
the threshold required to stop scanning to (maxContrast_ * 0.1).
To find global maximum We would need to scan the whole range which takes more
time. I hope we will see such implementation in the near future, so it
will be possible to choose between time and effectiveness :)

Thank you for that question, because when I analyzed the code again, I found
another problem :P maxContrast_ can be overwritten by a lower value,
near the top,
when contrast difference is smaller than (maxContrast_ * 0.1).

>
> > +              */
> > +             lensPosition_ = bestPosition_;
> > +             return true;
> > +     }
> > +
> > +     LOG(Af, Debug) << "Previous step is " << bestPosition_
> > +                    << ", Current step is " << lensPosition_;
>
> s/step/position/
>
> > +     return false;
> > +}
> > +
> > +void AfHillClimbing::afReset()
> > +{
> > +     LOG(Af, Debug) << "Reset AF parameters";
> > +     lensPosition_ = minLensPosition_;
> > +     maxStep_ = maxLensPosition_;
> > +     state_ = controls::AfStateScanning;
> > +     coarseCompleted_ = false;
> > +     maxContrast_ = 0.0;
> > +     skipFrames(1);
> > +}
> > +
> > +bool AfHillClimbing::afIsOutOfFocus() const
> > +{
> > +     const double diff_var = std::abs(currentContrast_ - maxContrast_);
> > +     const double var_ratio = diff_var / maxContrast_;
> > +     LOG(Af, Debug) << "Variance change rate: " << var_ratio
> > +                    << ", Current lens step: " << lensPosition_;
>
> s/Current/current/
> s/step/position/
>
> > +     return var_ratio > maxChange_;
> > +}
> > +
> > +bool AfHillClimbing::shouldSkipFrame()
> > +{
> > +     if (framesToSkip_ > 0) {
> > +             framesToSkip_--;
> > +             return true;
> > +     }
> > +
> > +     return false;
> > +}
> > +
> > +} /* namespace ipa::algorithms */
> > +
> > +} /* namespace libcamera */
> > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.h b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > new file mode 100644
> > index 00000000..2147939b
> > --- /dev/null
> > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > @@ -0,0 +1,91 @@
> > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > +/*
> > + * Copyright (C) 2021, Red Hat
> > + * Copyright (C) 2022, Ideas On Board
> > + * Copyright (C) 2023, Theobroma Systems
> > + *
> > + * af_hill_climbing.h - AF contrast based hill climbing common algorithm
> > + */
> > +
> > +#pragma once
> > +
> > +#include <libcamera/base/log.h>
> > +
> > +#include "af.h"
> > +
> > +namespace libcamera {
> > +
> > +class YamlObject;
> > +
> > +namespace ipa::algorithms {
> > +
> > +LOG_DECLARE_CATEGORY(Af)
> > +
> > +class AfHillClimbing : public Af
> > +{
> > +public:
> > +     int init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > +              const YamlObject &tuningData);
> > +     int32_t process(double currentContrast);
> > +     void skipFrames(uint32_t n);
> > +
> > +     controls::AfStateEnum state() override { return state_; }
> > +     controls::AfPauseStateEnum pauseState() override { return pauseState_; }
> > +
> > +private:
> > +     void setMode(controls::AfModeEnum mode) override;
> > +     void setRange(controls::AfRangeEnum range) override;
> > +     void setSpeed(controls::AfSpeedEnum speed) override;
> > +     void setMeteringMode(controls::AfMeteringEnum metering) override;
> > +     void setWindows(Span<const Rectangle> windows) override;
> > +     void setTrigger(controls::AfTriggerEnum trigger) override;
> > +     void setPause(controls::AfPauseEnum pause) override;
> > +     void setLensPosition(float lensPosition) override;
> > +
> > +     void processAutoMode();
> > +     void processContinuousMode();
> > +     void afCoarseScan();
> > +     void afFineScan();
> > +     bool afScan(uint32_t steps);
> > +     void afReset();
> > +     [[nodiscard]] bool afIsOutOfFocus() const;
> > +     bool shouldSkipFrame();
> > +
> > +     controls::AfModeEnum mode_ = controls::AfModeManual;
> > +     controls::AfStateEnum state_ = controls::AfStateIdle;
> > +     controls::AfPauseStateEnum pauseState_ = controls::AfPauseStateRunning;
> > +
> > +     /* Current focus lens position. */
> > +     int32_t lensPosition_ = 0;
> > +     /* Local optimum focus lens position during scanning. */
> > +     int32_t bestPosition_ = 0;
> > +
> > +     /* Current AF statistic contrast. */
> > +     double currentContrast_ = 0;
> > +     /* It is used to determine the derivative during scanning */
> > +     double maxContrast_ = 0;
> > +     /* The designated maximum range of focus scanning. */
> > +     int32_t maxStep_ = 0;
> > +     /* If the coarse scan completes, it is set to true. */
> > +     bool coarseCompleted_ = false;
> > +
> > +     uint32_t framesToSkip_ = 0;
> > +
> > +     /* Position limits of the focus lens. */
> > +     int32_t minLensPosition_;
> > +     int32_t maxLensPosition_;
> > +
> > +     /* Minimum position step for searching appropriate focus. */
> > +     uint32_t coarseSearchStep_;
> > +     uint32_t fineSearchStep_;
> > +
> > +     /* Fine scan range 0 < fineRange_ < 1. */
> > +     double fineRange_;
> > +
> > +     /* Max ratio of variance change, 0.0 < maxChange_ < 1.0. */
> > +     double maxChange_;
> > +};
> > +
> > +} /* namespace ipa::algorithms */
> > +
> > +} /* namespace libcamera */
> > diff --git a/src/ipa/libipa/algorithms/meson.build b/src/ipa/libipa/algorithms/meson.build
> > index 3df4798f..20e437fc 100644
> > --- a/src/ipa/libipa/algorithms/meson.build
> > +++ b/src/ipa/libipa/algorithms/meson.build
> > @@ -2,8 +2,10 @@
> >
> >  libipa_algorithms_headers = files([
> >      'af.h',
> > +    'af_hill_climbing.h',
> >  ])
> >
> >  libipa_algorithms_sources = files([
> >      'af.cpp',
> > +    'af_hill_climbing.cpp',
> >  ])
>
> --
> Regards,
>
> Laurent Pinchart

Best regards
Daniel

Hi Daniel,

On Tue, May 16, 2023 at 03:02:45PM +0200, Daniel Semkowicz wrote:
> On Wed, Apr 26, 2023 at 4:43 AM Laurent Pinchart wrote:
> > On Fri, Mar 31, 2023 at 10:19:24AM +0200, Daniel Semkowicz via libcamera-devel wrote:
> > > Create a new class with contrast based Auto Focus implementation
> > > using hill climbing algorithm. This common implementation is independent
> > > of platform specific code. This way, each platform can just implement
> > > contrast calculation and run the AF control loop basing on this class.
> > > This implementation is based on the code that was common for IPU3
> > > and RPi AF algorithms.
> >
> > How difficult would it be to port the IPU3 IPA module to use this class
> > ? Having two users would help showing that the interface is generic
> > enough.
> 
> The algorithm implementation is similar, so it should not be difficult.
> This is what I would really like to see, because it would simplify the code :)
> For basic version, without option to set AF windows, it should be just replacing
> the algorithm code with the calls to the AfHillClimbing. AfHillClimbing is based
> on the IPU3 code, so the platform code is already in the correct places.
> It would be good to expose lens limits to the IPA for correct operation with
> different cameras, because currently limits are hard-coded to 0-1023. Something
> similar to patch 02 of this series would be needed.
> 
> Unfortunately, I do not have access to IPU3 hardware to work on such code.

If you have a chance to give it a try, we can certainly help testing the
implementation.

> > > Signed-off-by: Daniel Semkowicz <dse@thaumatec.com>
> > > ---
> > >  .../libipa/algorithms/af_hill_climbing.cpp    | 374 ++++++++++++++++++
> > >  src/ipa/libipa/algorithms/af_hill_climbing.h  |  91 +++++
> > >  src/ipa/libipa/algorithms/meson.build         |   2 +
> > >  3 files changed, 467 insertions(+)
> > >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.h
> > >
> > > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.cpp b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > > new file mode 100644
> > > index 00000000..244b8803
> > > --- /dev/null
> > > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > > @@ -0,0 +1,374 @@
> > > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > > +/*
> > > + * Copyright (C) 2021, Red Hat
> > > + * Copyright (C) 2022, Ideas On Board
> > > + * Copyright (C) 2023, Theobroma Systems
> > > + *
> > > + * af_hill_climbing.cpp - AF contrast based hill climbing common algorithm
> >
> > s/contract based/constrast-based/
> >
> > Same below in this file and in af_hill_climbing.h.
> >
> > > + */
> > > +
> > > +#include "af_hill_climbing.h"
> > > +
> > > +#include "libcamera/internal/yaml_parser.h"
> > > +
> > > +/**
> > > + * \file af_hill_climbing.h
> > > + * \brief AF contrast based hill climbing common algorithm
> > > + */
> > > +
> > > +namespace libcamera {
> > > +
> > > +namespace ipa::algorithms {
> > > +
> > > +LOG_DEFINE_CATEGORY(Af)
> > > +
> > > +/**
> > > + * \class AfHillClimbing
> > > + * \brief Contrast based hill climbing auto focus control algorithm
> > > + * implementation
> > > + *
> > > + * Control part of the auto focus algorithm. It calculates the lens position
> > > + * based on the contrast measure supplied by the platform-specific
> > > + * implementation. This way it is independent from the platform.
> >
> > Many platforms have the ability to calculate focus statistics separately
> > on different regions of the image (quite often using a grid, sometimes
> > with more freely-configurable regions, and I've seen at least one
> > platform where the regions can be ellipses instead of rectangles). Do
> > you think it will be possible to support those in the future, possibly
> > to implement touch-to-focus, in this class in a generic way, or would
> > the platform-specific definition of the zones require moving some of the
> > code from this class to platform-specific classes ?
> 
> If there is more than one focus window, there are different possibilities what
> We can do with such information. For example, We can choose the window with the
> highest peak contrast value or the position closest to the camera.
> This is a bigger topic for the discussion. I can imagine additional AF control
> that allows you to choose the priority when using multiple AF windows.
> Probably it will be possible to do this in a generic way as how it is already
> done for the one window. AfHillClimbing only expects generic contrast value
> that rises with the focus is "better". AfHillClimbing will request platform
> part to configure AF windows and will expect the platform part to supply the
> expected number of measured contrast values (for each window).
> 
> > > + *
> > > + * Platform layer that use this algorithm should call process() function
> > > + * for each each frame and set the lens to the calculated position.
> > > + *
> > > + * Focus search is divided into two phases:
> > > + * 1. coarse search,
> > > + * 2. fine search.
> > > + *
> > > + * In the first phase, the lens is moved with bigger steps to quickly find
> > > + * a rough position for the best focus. Then, based on the outcome of coarse
> > > + * search, the second phase is executed. Lens is moved with smaller steps
> >
> > s/Lens/The lens/
> >
> > > + * in a limited range within the rough position to find the exact position
> >
> > s/within/around/
> >
> > > + * for best focus.
> > > + *
> > > + * Tuning file parameters:
> >
> > We use camelCase for tuning file parameters in the rkisp1 and ipu3
> > tuning files, while Raspberry Pi uses a mix of snake_case and
> > kebab-case. Given that this class is supposed to be
> > platform-independent, I'm not sure I like parsing data directly from a
> > tuning file. I think it be better to create a structure to represent the
> > configuration data, fill it from the tuning file in platform-specific
> > code, and pass it to the init function.
> 
> I had not noticed this difference before. I think your approach is better,
> and I will rework it this way.
> 
> > > + * - **coarse-search-step:** The value by which the lens position will change
> > > + *   in one step in the *coarse search* phase. Unit is lens specific.
> >
> > s/Unit/The unit/
> >
> > Same below.
> >
> > While the unit can be platform specific, it would be useful to document
> > what it refers to. If my understanding is correct, the coarse step is
> > expressed in the same units as the lens minimum and maximum positions.
> > Could you please capture that ?
> >
> > I'm also wondering if we should express the coarse search step as a
> > percentage of the lens movement range, to make is less platform
> > specific.
> 
> This makes sense to express the coarse search step as a percentage of the lens
> movement range. Especially, that lens limits are now passed from the v4l
> subdevice internally to the IPA, so the user does not need to know what the
> correct values are.
> 
> > > + * - **fine-search-step:** The value by which the lens position will change
> > > + *   in one step in the *fine search* phase. Unit is lens specific.
> > > + * - **fine-search-range:** Search range in the *fine search* phase, expressed
> > > + *   as a percentage of the coarse search result. Valid values are
> > > + *   in the [0, 100] interval. Value 5 means 5%. If coarse search stopped
> > > + *   at value 200, the fine search range will be [190, 210].
> >
> > I would have envisioned doing the fine search in the full range around
> > the position found by the coarse search, that is in the [coarse search
> > position - coarse search step, coarse search position + coarse search
> > step]. Going beyond that means we'll scan positions that will have lower
> > contrast values (assuming the coarse search found the global maximum,
> > not a local extremum). Using a (possibly significantly) smaller range
> > means we could quite likely miss the real maximum.
> >
> > Are there expected use cases for not handling the fine search range
> > automatically ?
> 
> This is the implementation currently used in the IPU3 and there were some
> discussions in the previous version of this patch, why it is done this way.
> Unfortunately, We can only guess the reason. Automating this seems to make
> sense, especially, that it is not difficult and I do not see any disadvantages.

Let's try it then :-) We can also ask Kate why the IPU3 is implemented
this way.

> > > + * - **max-variance-change:** ratio of contrast variance change in the
> > > + *   *continuous mode* needed for triggering the focus change. When the variance
> > > + *   change exceeds this value, focus search will be triggered. Valid values are
> > > + *   in the [0.0, 1.0] interval.
> >
> > Both the fine search range and max variance change are relative values
> > in the [0%, 100%] range, with the former expressed as a percentage
> > integer value and the latter a float. Is there a reason for that, or
> > could both values be expressed the same way ? I think I'd go for floats
> > in both cases.
> >
> > I'm tempted to rename "max-variance-change" to
> > "variance-change-threshold" as it's a threshold to trigger a focus
> > search. Same for the maxChange_ member variable.
> 
> I agree with it.
> 
> > > + * .
> >
> > Stray '.' ?
> 
> Dot is used to explicitly mark the end of the list in the Doxygen.
> Without the dot, I had some formatting problems here.

Ah OK, my bad.

> > > + *
> > > + * \todo Search range in the *fine search* phase should depend on the lens
> > > + * movement range rather than coarse search result.
> >
> > This sounds like a quite simple change, should it be done already, or
> > are there blockers ? I'm also puzzled by why the fine search range is a
> > percentage of the coarse search result, what's the reason for that ?
> >
> > > + * \todo Implement setRange.
> > > + * \todo Implement setSpeed.
> > > + * \todo Implement setMeteringMode.
> > > + * \todo Implement setWindows.
> > > + * \todo Implement the AfPauseDeferred mode.
> > > + */
> > > +
> > > +/**
> > > + * \brief Initialize the AfHillClimbing with lens configuration and tuning data
> > > + * \param[in] minFocusPosition Minimum position supported by camera lens
> > > + * \param[in] maxFocusPosition Maximum position supported by camera lens
> > > + * \param[in] tuningData The tuning data for the algorithm
> > > + *
> > > + * This method should be called in the libcamera::ipa::Algorithm::init()
> > > + * method of the platform layer.
> >
> > s/method/function/
> >
> > Same below.
> >
> > > + *
> > > + * \return 0 if successful, an error code otherwise
> > > + */
> > > +int AfHillClimbing::init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > > +                      const YamlObject &tuningData)
> > > +{
> > > +     minLensPosition_ = minFocusPosition;
> > > +     maxLensPosition_ = maxFocusPosition;
> > > +
> > > +     coarseSearchStep_ = tuningData["coarse-search-step"].get<uint32_t>(30);
> > > +     fineSearchStep_ = tuningData["fine-search-step"].get<uint32_t>(1);
> > > +     fineRange_ = tuningData["fine-search-range"].get<uint32_t>(5);
> > > +     fineRange_ /= 100;
> > > +     maxChange_ = tuningData["max-variance-change"].get<double>(0.5);
> > > +
> > > +     LOG(Af, Debug) << "coarseSearchStep_: " << coarseSearchStep_
> > > +                    << ", fineSearchStep_: " << fineSearchStep_
> > > +                    << ", fineRange_: " << fineRange_
> > > +                    << ", maxChange_: " << maxChange_;
> > > +
> > > +     return 0;
> > > +}
> > > +
> > > +/**
> > > + * \brief Run the auto focus algorithm loop
> > > + * \param[in] currentContrast New value of contrast measured for current frame
> > > + *
> > > + * This method should be called in the libcamera::ipa::Algorithm::process()
> > > + * method of the platform layer for each frame.
> > > + *
> > > + * Contrast value supplied in the \p currentContrast parameter can be platform
> >
> > We use \a for function parameters, not \p. I'm not sure if one of the
> > two is intrinsincly better than the other, but we should be consistent.
> >
> > This comment applies to the whole patch series, where applicable.
> 
> I will go through the series and change that.
> 
> > > + * specific. The only requirement is the contrast value must increase with
> > > + * the increasing image focus. Contrast value must be highest when image is in
> > > + * focus.
> > > + *
> > > + * \return New lens position calculated by the AF algorithm
> > > + */
> > > +int32_t AfHillClimbing::process(double currentContrast)
> > > +{
> > > +     currentContrast_ = currentContrast;
> > > +
> > > +     if (shouldSkipFrame())
> > > +             return lensPosition_;
> > > +
> > > +     switch (mode_) {
> > > +     case controls::AfModeManual:
> > > +             /* Nothing to process. */
> > > +             break;
> > > +     case controls::AfModeAuto:
> > > +             processAutoMode();
> > > +             break;
> > > +     case controls::AfModeContinuous:
> > > +             processContinuousMode();
> > > +             break;
> > > +     }
> > > +
> > > +     return lensPosition_;
> > > +}
> > > +
> > > +void AfHillClimbing::processAutoMode()
> > > +{
> > > +     if (state_ == controls::AfStateScanning) {
> > > +             afCoarseScan();
> > > +             afFineScan();
> >
> > The two functions are always called together, and they're both fairly
> > small. I'd combine them into a single afScan().
> 
> I will try to improve that.
> 
> > > +     }
> > > +}
> > > +
> > > +void AfHillClimbing::processContinuousMode()
> > > +{
> > > +     /* If we are in a paused state, we won't process the stats. */
> > > +     if (pauseState_ == controls::AfPauseStatePaused)
> > > +             return;
> > > +
> > > +     if (state_ == controls::AfStateScanning) {
> > > +             afCoarseScan();
> > > +             afFineScan();
> > > +             return;
> > > +     }
> > > +
> > > +     /*
> > > +      * AF scan can be started at any moment in AfModeContinuous,
> > > +      * except when the state is already AfStateScanning.
> > > +      */
> > > +     if (afIsOutOfFocus())
> > > +             afReset();
> > > +}
> > > +
> > > +/**
> > > + * \brief Request AF to skip n frames
> > > + * \param[in] n Number of frames to be skipped
> > > + *
> > > + * For the requested number of frames, the AF calculation will be skipped
> > > + * and lens position will not change. The platform layer still needs to
> > > + * call process() function for each frame during this time.
> >
> > s/call process() function/call the process() function/
> >
> > > + * This function can be used by the platform layer if the hardware needs more
> > > + * time for some operations.
> > > + *
> > > + * The number of the requested frames (\p n) will be applied only if \p n has
> > > + * higher value than the number of frames already requested to be skipped.
> > > + * For example, if *skipFrames(5)* was already called for the current frame,
> >
> > Code spans use back-quotes, see
> > https://www.doxygen.nl/manual/markdown.html#md_codespan.
> >
> > > + * then calling *skipFrames(3)* will not override the previous request
> > > + * and 5 frames will be skipped.
> > > + */
> > > +void AfHillClimbing::skipFrames(uint32_t n)
> > > +{
> > > +     if (n > framesToSkip_)
> > > +             framesToSkip_ = n;
> > > +}
> > > +
> > > +void AfHillClimbing::setMode(controls::AfModeEnum mode)
> > > +{
> > > +     if (mode == mode_)
> > > +             return;
> > > +
> > > +     LOG(Af, Debug) << "Switched AF mode from " << mode_ << " to " << mode;
> > > +     mode_ = mode;
> > > +
> > > +     state_ = controls::AfStateIdle;
> > > +     pauseState_ = controls::AfPauseStateRunning;
> > > +
> > > +     if (mode_ == controls::AfModeContinuous)
> > > +             afReset();
> > > +}
> > > +
> > > +void AfHillClimbing::setRange([[maybe_unused]] controls::AfRangeEnum range)
> > > +{
> > > +     LOG(Af, Error) << "setRange() not implemented!";
> > > +}
> > > +
> > > +void AfHillClimbing::setSpeed([[maybe_unused]] controls::AfSpeedEnum speed)
> > > +{
> > > +     LOG(Af, Error) << "setSpeed() not implemented!";
> > > +}
> > > +
> > > +void AfHillClimbing::setMeteringMode([[maybe_unused]] controls::AfMeteringEnum metering)
> > > +{
> > > +     LOG(Af, Error) << "setMeteringMode() not implemented!";
> > > +}
> > > +
> > > +void AfHillClimbing::setWindows([[maybe_unused]] Span<const Rectangle> windows)
> > > +{
> > > +     LOG(Af, Error) << "setWindows() not implemented!";
> > > +}
> > > +
> > > +void AfHillClimbing::setTrigger(controls::AfTriggerEnum trigger)
> > > +{
> > > +     if (mode_ != controls::AfModeAuto) {
> > > +             LOG(Af, Warning)
> > > +                     << "setTrigger() not valid in mode " << mode_;
> > > +             return;
> > > +     }
> > > +
> > > +     LOG(Af, Debug) << "Trigger called with " << trigger;
> > > +
> > > +     switch (trigger) {
> > > +     case controls::AfTriggerStart:
> > > +             afReset();
> > > +             break;
> > > +     case controls::AfTriggerCancel:
> > > +             state_ = controls::AfStateIdle;
> > > +             break;
> > > +     }
> >
> > All this logic seems to implement requirements set by the AF controls
> > definitions, not specific to this class. Should it be moved to the base
> > AF class ? Same for setPause().
> 
> There was a discussion on similar topic in the previous version. Conclusion was
> that at this point it is hard to decide what will be completely reusable by
> other implementations, so only the interface is defined in the Af and most of
> the implementation is done in the AfHillClimbing. We can move parts of the code
> to the Af later, when more things become clear.

OK, let's keep code here, and move it later if useful.

> > > +}
> > > +
> > > +void AfHillClimbing::setPause(controls::AfPauseEnum pause)
> > > +{
> > > +     if (mode_ != controls::AfModeContinuous) {
> > > +             LOG(Af, Warning)
> > > +                     << "setPause() not valid in mode " << mode_;
> > > +             return;
> > > +     }
> > > +
> > > +     switch (pause) {
> > > +     case controls::AfPauseImmediate:
> > > +             pauseState_ = controls::AfPauseStatePaused;
> > > +             break;
> > > +     case controls::AfPauseDeferred:
> > > +             LOG(Af, Warning) << "AfPauseDeferred is not supported!";
> > > +             break;
> > > +     case controls::AfPauseResume:
> > > +             pauseState_ = controls::AfPauseStateRunning;
> > > +             break;
> > > +     }
> > > +}
> > > +
> > > +void AfHillClimbing::setLensPosition(float lensPosition)
> > > +{
> > > +     if (mode_ != controls::AfModeManual) {
> > > +             LOG(Af, Warning)
> > > +                     << "setLensPosition() not valid in mode " << mode_;
> > > +             return;
> > > +     }
> > > +
> > > +     lensPosition_ = static_cast<int32_t>(lensPosition);
> >
> > The LensPosition control is defined in dioptres units. Unless I'm
> > mistaken, the implementation in this class doesn't match that. This
> > should be fixed, not necessarily with a fully calibrated implementation,
> > but at least to map 0.0 to infinity and the maximum value of the lens
> > position to the closest possible focus.
> 
> Ok, so just for confirmation. For example, for the VCM driver that I use,
> the V4L2_CID_FOCUS_ABSOLUTE values are in 0-1023 range and V4L documentation
> specifies that positive values set the focus closer to the camera.
> In this case, the LensPosition will simply map to 0.0 - 1023.0.
> Do I understand your approach correctly?

That sounds good, but you need to ensure that the minimum value of the
V4L2 focus control maps to 0.0. If another VCM driver reports a
different range than 0-1023, that should be handled. 1023.0 as a maximum
would mean focussing at ~1mm from the camera, which is very, very close.
The focus lens isn't calibrated at the moment, and that's OK, but I'd
rather map the maximum to something more sensible, maybe 1m or 50cm, so
1.0 or 2.0.

> > > +
> > > +     LOG(Af, Debug) << "Requesting lens position " << lensPosition_;
> > > +}
> > > +
> > > +void AfHillClimbing::afCoarseScan()
> > > +{
> > > +     if (coarseCompleted_)
> > > +             return;
> > > +
> > > +     if (afScan(coarseSearchStep_)) {
> > > +             coarseCompleted_ = true;
> > > +             maxContrast_ = 0;
> > > +             const auto diff = static_cast<int32_t>(
> > > +                     std::abs(lensPosition_) * fineRange_);
> > > +             lensPosition_ = std::max(lensPosition_ - diff, minLensPosition_);
> > > +             maxStep_ = std::min(lensPosition_ + diff, maxLensPosition_);
> >
> > I think the intent here it to set the scan range to [coarse position -
> > diff, coarse position + diff], but as you modify lensPosition_ first,
> > you effectively set it to [coarse position - diff, coarse position].
> 
> You are right... I will fix that :)
> 
> > Reading the code, maxStep_ seems to store a lens position, not a step.
> > Is this correct ? If so, please rename the variable accordingly.
> 
> Yes, this is correct.
> 
> > > +     }
> > > +}
> > > +
> > > +void AfHillClimbing::afFineScan()
> > > +{
> > > +     if (!coarseCompleted_)
> > > +             return;
> > > +
> > > +     if (afScan(fineSearchStep_)) {
> > > +             LOG(Af, Debug) << "AF found the best focus position!";
> > > +             state_ = controls::AfStateFocused;
> > > +     }
> > > +}
> > > +
> > > +bool AfHillClimbing::afScan(uint32_t steps)
> > > +{
> > > +     if (lensPosition_ + static_cast<int32_t>(steps) > maxStep_) {
> > > +             /* If the max step is reached, move lens to the position. */
> > > +             lensPosition_ = bestPosition_;
> > > +             return true;
> > > +     }
> > > +
> > > +     /*
> > > +      * Find the maximum of the variance by estimating its derivative.
> > > +      * If the direction changes, it means we have passed a maximum one step
> > > +      * before.
> > > +      */
> > > +     if ((currentContrast_ - maxContrast_) >= -(maxContrast_ * 0.1)) {
> > > +             /*
> > > +              * Positive and zero derivative:
> > > +              * The variance is still increasing. The focus could be
> > > +              * increased for the next comparison. Also, the max variance
> > > +              * and previous focus value are updated.
> > > +              */
> > > +             bestPosition_ = lensPosition_;
> > > +             lensPosition_ += static_cast<int32_t>(steps);
> > > +             maxContrast_ = currentContrast_;
> > > +     } else {
> > > +             /*
> > > +              * Negative derivative:
> > > +              * The variance starts to decrease, which means the maximum
> > > +              * variance is found. Set focus step to previous good one,
> > > +              * then return immediately.
> >
> > Isn't this very prone to stopping on a local extremum ?
> 
> It is, and this is intended. When there are two objects on the scene, We will
> just focus on the one closer to the camera. It is mitigated a bit, by setting
> the threshold required to stop scanning to (maxContrast_ * 0.1).

OK. Please document this design decision in a comment in the code
(the documentation block of the AfHillClimb class seems to be a good
place).

> To find global maximum We would need to scan the whole range which takes more
> time. I hope we will see such implementation in the near future, so it
> will be possible to choose between time and effectiveness :)
> 
> Thank you for that question, because when I analyzed the code again, I found
> another problem :P maxContrast_ can be overwritten by a lower value,
> near the top,
> when contrast difference is smaller than (maxContrast_ * 0.1).
> 
> > > +              */
> > > +             lensPosition_ = bestPosition_;
> > > +             return true;
> > > +     }
> > > +
> > > +     LOG(Af, Debug) << "Previous step is " << bestPosition_
> > > +                    << ", Current step is " << lensPosition_;
> >
> > s/step/position/
> >
> > > +     return false;
> > > +}
> > > +
> > > +void AfHillClimbing::afReset()
> > > +{
> > > +     LOG(Af, Debug) << "Reset AF parameters";
> > > +     lensPosition_ = minLensPosition_;
> > > +     maxStep_ = maxLensPosition_;
> > > +     state_ = controls::AfStateScanning;
> > > +     coarseCompleted_ = false;
> > > +     maxContrast_ = 0.0;
> > > +     skipFrames(1);
> > > +}
> > > +
> > > +bool AfHillClimbing::afIsOutOfFocus() const
> > > +{
> > > +     const double diff_var = std::abs(currentContrast_ - maxContrast_);
> > > +     const double var_ratio = diff_var / maxContrast_;
> > > +     LOG(Af, Debug) << "Variance change rate: " << var_ratio
> > > +                    << ", Current lens step: " << lensPosition_;
> >
> > s/Current/current/
> > s/step/position/
> >
> > > +     return var_ratio > maxChange_;
> > > +}
> > > +
> > > +bool AfHillClimbing::shouldSkipFrame()
> > > +{
> > > +     if (framesToSkip_ > 0) {
> > > +             framesToSkip_--;
> > > +             return true;
> > > +     }
> > > +
> > > +     return false;
> > > +}
> > > +
> > > +} /* namespace ipa::algorithms */
> > > +
> > > +} /* namespace libcamera */
> > > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.h b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > > new file mode 100644
> > > index 00000000..2147939b
> > > --- /dev/null
> > > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > > @@ -0,0 +1,91 @@
> > > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > > +/*
> > > + * Copyright (C) 2021, Red Hat
> > > + * Copyright (C) 2022, Ideas On Board
> > > + * Copyright (C) 2023, Theobroma Systems
> > > + *
> > > + * af_hill_climbing.h - AF contrast based hill climbing common algorithm
> > > + */
> > > +
> > > +#pragma once
> > > +
> > > +#include <libcamera/base/log.h>
> > > +
> > > +#include "af.h"
> > > +
> > > +namespace libcamera {
> > > +
> > > +class YamlObject;
> > > +
> > > +namespace ipa::algorithms {
> > > +
> > > +LOG_DECLARE_CATEGORY(Af)
> > > +
> > > +class AfHillClimbing : public Af
> > > +{
> > > +public:
> > > +     int init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > > +              const YamlObject &tuningData);
> > > +     int32_t process(double currentContrast);
> > > +     void skipFrames(uint32_t n);
> > > +
> > > +     controls::AfStateEnum state() override { return state_; }
> > > +     controls::AfPauseStateEnum pauseState() override { return pauseState_; }
> > > +
> > > +private:
> > > +     void setMode(controls::AfModeEnum mode) override;
> > > +     void setRange(controls::AfRangeEnum range) override;
> > > +     void setSpeed(controls::AfSpeedEnum speed) override;
> > > +     void setMeteringMode(controls::AfMeteringEnum metering) override;
> > > +     void setWindows(Span<const Rectangle> windows) override;
> > > +     void setTrigger(controls::AfTriggerEnum trigger) override;
> > > +     void setPause(controls::AfPauseEnum pause) override;
> > > +     void setLensPosition(float lensPosition) override;
> > > +
> > > +     void processAutoMode();
> > > +     void processContinuousMode();
> > > +     void afCoarseScan();
> > > +     void afFineScan();
> > > +     bool afScan(uint32_t steps);
> > > +     void afReset();
> > > +     [[nodiscard]] bool afIsOutOfFocus() const;
> > > +     bool shouldSkipFrame();
> > > +
> > > +     controls::AfModeEnum mode_ = controls::AfModeManual;
> > > +     controls::AfStateEnum state_ = controls::AfStateIdle;
> > > +     controls::AfPauseStateEnum pauseState_ = controls::AfPauseStateRunning;
> > > +
> > > +     /* Current focus lens position. */
> > > +     int32_t lensPosition_ = 0;
> > > +     /* Local optimum focus lens position during scanning. */
> > > +     int32_t bestPosition_ = 0;
> > > +
> > > +     /* Current AF statistic contrast. */
> > > +     double currentContrast_ = 0;
> > > +     /* It is used to determine the derivative during scanning */
> > > +     double maxContrast_ = 0;
> > > +     /* The designated maximum range of focus scanning. */
> > > +     int32_t maxStep_ = 0;
> > > +     /* If the coarse scan completes, it is set to true. */
> > > +     bool coarseCompleted_ = false;
> > > +
> > > +     uint32_t framesToSkip_ = 0;
> > > +
> > > +     /* Position limits of the focus lens. */
> > > +     int32_t minLensPosition_;
> > > +     int32_t maxLensPosition_;
> > > +
> > > +     /* Minimum position step for searching appropriate focus. */
> > > +     uint32_t coarseSearchStep_;
> > > +     uint32_t fineSearchStep_;
> > > +
> > > +     /* Fine scan range 0 < fineRange_ < 1. */
> > > +     double fineRange_;
> > > +
> > > +     /* Max ratio of variance change, 0.0 < maxChange_ < 1.0. */
> > > +     double maxChange_;
> > > +};
> > > +
> > > +} /* namespace ipa::algorithms */
> > > +
> > > +} /* namespace libcamera */
> > > diff --git a/src/ipa/libipa/algorithms/meson.build b/src/ipa/libipa/algorithms/meson.build
> > > index 3df4798f..20e437fc 100644
> > > --- a/src/ipa/libipa/algorithms/meson.build
> > > +++ b/src/ipa/libipa/algorithms/meson.build
> > > @@ -2,8 +2,10 @@
> > >
> > >  libipa_algorithms_headers = files([
> > >      'af.h',
> > > +    'af_hill_climbing.h',
> > >  ])
> > >
> > >  libipa_algorithms_sources = files([
> > >      'af.cpp',
> > > +    'af_hill_climbing.cpp',
> > >  ])

Hi Laurent,

On Wed, May 31, 2023 at 5:34 PM Laurent Pinchart
<laurent.pinchart@ideasonboard.com> wrote:
>
> Hi Daniel,
>
> On Tue, May 16, 2023 at 03:02:45PM +0200, Daniel Semkowicz wrote:
> > On Wed, Apr 26, 2023 at 4:43 AM Laurent Pinchart wrote:
> > > On Fri, Mar 31, 2023 at 10:19:24AM +0200, Daniel Semkowicz via libcamera-devel wrote:
> > > > Create a new class with contrast based Auto Focus implementation
> > > > using hill climbing algorithm. This common implementation is independent
> > > > of platform specific code. This way, each platform can just implement
> > > > contrast calculation and run the AF control loop basing on this class.
> > > > This implementation is based on the code that was common for IPU3
> > > > and RPi AF algorithms.
> > >
> > > How difficult would it be to port the IPU3 IPA module to use this class
> > > ? Having two users would help showing that the interface is generic
> > > enough.
> >
> > The algorithm implementation is similar, so it should not be difficult.
> > This is what I would really like to see, because it would simplify the code :)
> > For basic version, without option to set AF windows, it should be just replacing
> > the algorithm code with the calls to the AfHillClimbing. AfHillClimbing is based
> > on the IPU3 code, so the platform code is already in the correct places.
> > It would be good to expose lens limits to the IPA for correct operation with
> > different cameras, because currently limits are hard-coded to 0-1023. Something
> > similar to patch 02 of this series would be needed.
> >
> > Unfortunately, I do not have access to IPU3 hardware to work on such code.
>
> If you have a chance to give it a try, we can certainly help testing the
> implementation.
>
> > > > Signed-off-by: Daniel Semkowicz <dse@thaumatec.com>
> > > > ---
> > > >  .../libipa/algorithms/af_hill_climbing.cpp    | 374 ++++++++++++++++++
> > > >  src/ipa/libipa/algorithms/af_hill_climbing.h  |  91 +++++
> > > >  src/ipa/libipa/algorithms/meson.build         |   2 +
> > > >  3 files changed, 467 insertions(+)
> > > >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > > >  create mode 100644 src/ipa/libipa/algorithms/af_hill_climbing.h
> > > >
> > > > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.cpp b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > > > new file mode 100644
> > > > index 00000000..244b8803
> > > > --- /dev/null
> > > > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.cpp
> > > > @@ -0,0 +1,374 @@
> > > > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > > > +/*
> > > > + * Copyright (C) 2021, Red Hat
> > > > + * Copyright (C) 2022, Ideas On Board
> > > > + * Copyright (C) 2023, Theobroma Systems
> > > > + *
> > > > + * af_hill_climbing.cpp - AF contrast based hill climbing common algorithm
> > >
> > > s/contract based/constrast-based/
> > >
> > > Same below in this file and in af_hill_climbing.h.
> > >
> > > > + */
> > > > +
> > > > +#include "af_hill_climbing.h"
> > > > +
> > > > +#include "libcamera/internal/yaml_parser.h"
> > > > +
> > > > +/**
> > > > + * \file af_hill_climbing.h
> > > > + * \brief AF contrast based hill climbing common algorithm
> > > > + */
> > > > +
> > > > +namespace libcamera {
> > > > +
> > > > +namespace ipa::algorithms {
> > > > +
> > > > +LOG_DEFINE_CATEGORY(Af)
> > > > +
> > > > +/**
> > > > + * \class AfHillClimbing
> > > > + * \brief Contrast based hill climbing auto focus control algorithm
> > > > + * implementation
> > > > + *
> > > > + * Control part of the auto focus algorithm. It calculates the lens position
> > > > + * based on the contrast measure supplied by the platform-specific
> > > > + * implementation. This way it is independent from the platform.
> > >
> > > Many platforms have the ability to calculate focus statistics separately
> > > on different regions of the image (quite often using a grid, sometimes
> > > with more freely-configurable regions, and I've seen at least one
> > > platform where the regions can be ellipses instead of rectangles). Do
> > > you think it will be possible to support those in the future, possibly
> > > to implement touch-to-focus, in this class in a generic way, or would
> > > the platform-specific definition of the zones require moving some of the
> > > code from this class to platform-specific classes ?
> >
> > If there is more than one focus window, there are different possibilities what
> > We can do with such information. For example, We can choose the window with the
> > highest peak contrast value or the position closest to the camera.
> > This is a bigger topic for the discussion. I can imagine additional AF control
> > that allows you to choose the priority when using multiple AF windows.
> > Probably it will be possible to do this in a generic way as how it is already
> > done for the one window. AfHillClimbing only expects generic contrast value
> > that rises with the focus is "better". AfHillClimbing will request platform
> > part to configure AF windows and will expect the platform part to supply the
> > expected number of measured contrast values (for each window).
> >
> > > > + *
> > > > + * Platform layer that use this algorithm should call process() function
> > > > + * for each each frame and set the lens to the calculated position.
> > > > + *
> > > > + * Focus search is divided into two phases:
> > > > + * 1. coarse search,
> > > > + * 2. fine search.
> > > > + *
> > > > + * In the first phase, the lens is moved with bigger steps to quickly find
> > > > + * a rough position for the best focus. Then, based on the outcome of coarse
> > > > + * search, the second phase is executed. Lens is moved with smaller steps
> > >
> > > s/Lens/The lens/
> > >
> > > > + * in a limited range within the rough position to find the exact position
> > >
> > > s/within/around/
> > >
> > > > + * for best focus.
> > > > + *
> > > > + * Tuning file parameters:
> > >
> > > We use camelCase for tuning file parameters in the rkisp1 and ipu3
> > > tuning files, while Raspberry Pi uses a mix of snake_case and
> > > kebab-case. Given that this class is supposed to be
> > > platform-independent, I'm not sure I like parsing data directly from a
> > > tuning file. I think it be better to create a structure to represent the
> > > configuration data, fill it from the tuning file in platform-specific
> > > code, and pass it to the init function.
> >
> > I had not noticed this difference before. I think your approach is better,
> > and I will rework it this way.
> >
> > > > + * - **coarse-search-step:** The value by which the lens position will change
> > > > + *   in one step in the *coarse search* phase. Unit is lens specific.
> > >
> > > s/Unit/The unit/
> > >
> > > Same below.
> > >
> > > While the unit can be platform specific, it would be useful to document
> > > what it refers to. If my understanding is correct, the coarse step is
> > > expressed in the same units as the lens minimum and maximum positions.
> > > Could you please capture that ?
> > >
> > > I'm also wondering if we should express the coarse search step as a
> > > percentage of the lens movement range, to make is less platform
> > > specific.
> >
> > This makes sense to express the coarse search step as a percentage of the lens
> > movement range. Especially, that lens limits are now passed from the v4l
> > subdevice internally to the IPA, so the user does not need to know what the
> > correct values are.
> >
> > > > + * - **fine-search-step:** The value by which the lens position will change
> > > > + *   in one step in the *fine search* phase. Unit is lens specific.
> > > > + * - **fine-search-range:** Search range in the *fine search* phase, expressed
> > > > + *   as a percentage of the coarse search result. Valid values are
> > > > + *   in the [0, 100] interval. Value 5 means 5%. If coarse search stopped
> > > > + *   at value 200, the fine search range will be [190, 210].
> > >
> > > I would have envisioned doing the fine search in the full range around
> > > the position found by the coarse search, that is in the [coarse search
> > > position - coarse search step, coarse search position + coarse search
> > > step]. Going beyond that means we'll scan positions that will have lower
> > > contrast values (assuming the coarse search found the global maximum,
> > > not a local extremum). Using a (possibly significantly) smaller range
> > > means we could quite likely miss the real maximum.
> > >
> > > Are there expected use cases for not handling the fine search range
> > > automatically ?
> >
> > This is the implementation currently used in the IPU3 and there were some
> > discussions in the previous version of this patch, why it is done this way.
> > Unfortunately, We can only guess the reason. Automating this seems to make
> > sense, especially, that it is not difficult and I do not see any disadvantages.
>
> Let's try it then :-) We can also ask Kate why the IPU3 is implemented
> this way.
>
> > > > + * - **max-variance-change:** ratio of contrast variance change in the
> > > > + *   *continuous mode* needed for triggering the focus change. When the variance
> > > > + *   change exceeds this value, focus search will be triggered. Valid values are
> > > > + *   in the [0.0, 1.0] interval.
> > >
> > > Both the fine search range and max variance change are relative values
> > > in the [0%, 100%] range, with the former expressed as a percentage
> > > integer value and the latter a float. Is there a reason for that, or
> > > could both values be expressed the same way ? I think I'd go for floats
> > > in both cases.
> > >
> > > I'm tempted to rename "max-variance-change" to
> > > "variance-change-threshold" as it's a threshold to trigger a focus
> > > search. Same for the maxChange_ member variable.
> >
> > I agree with it.
> >
> > > > + * .
> > >
> > > Stray '.' ?
> >
> > Dot is used to explicitly mark the end of the list in the Doxygen.
> > Without the dot, I had some formatting problems here.
>
> Ah OK, my bad.
>
> > > > + *
> > > > + * \todo Search range in the *fine search* phase should depend on the lens
> > > > + * movement range rather than coarse search result.
> > >
> > > This sounds like a quite simple change, should it be done already, or
> > > are there blockers ? I'm also puzzled by why the fine search range is a
> > > percentage of the coarse search result, what's the reason for that ?
> > >
> > > > + * \todo Implement setRange.
> > > > + * \todo Implement setSpeed.
> > > > + * \todo Implement setMeteringMode.
> > > > + * \todo Implement setWindows.
> > > > + * \todo Implement the AfPauseDeferred mode.
> > > > + */
> > > > +
> > > > +/**
> > > > + * \brief Initialize the AfHillClimbing with lens configuration and tuning data
> > > > + * \param[in] minFocusPosition Minimum position supported by camera lens
> > > > + * \param[in] maxFocusPosition Maximum position supported by camera lens
> > > > + * \param[in] tuningData The tuning data for the algorithm
> > > > + *
> > > > + * This method should be called in the libcamera::ipa::Algorithm::init()
> > > > + * method of the platform layer.
> > >
> > > s/method/function/
> > >
> > > Same below.
> > >
> > > > + *
> > > > + * \return 0 if successful, an error code otherwise
> > > > + */
> > > > +int AfHillClimbing::init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > > > +                      const YamlObject &tuningData)
> > > > +{
> > > > +     minLensPosition_ = minFocusPosition;
> > > > +     maxLensPosition_ = maxFocusPosition;
> > > > +
> > > > +     coarseSearchStep_ = tuningData["coarse-search-step"].get<uint32_t>(30);
> > > > +     fineSearchStep_ = tuningData["fine-search-step"].get<uint32_t>(1);
> > > > +     fineRange_ = tuningData["fine-search-range"].get<uint32_t>(5);
> > > > +     fineRange_ /= 100;
> > > > +     maxChange_ = tuningData["max-variance-change"].get<double>(0.5);
> > > > +
> > > > +     LOG(Af, Debug) << "coarseSearchStep_: " << coarseSearchStep_
> > > > +                    << ", fineSearchStep_: " << fineSearchStep_
> > > > +                    << ", fineRange_: " << fineRange_
> > > > +                    << ", maxChange_: " << maxChange_;
> > > > +
> > > > +     return 0;
> > > > +}
> > > > +
> > > > +/**
> > > > + * \brief Run the auto focus algorithm loop
> > > > + * \param[in] currentContrast New value of contrast measured for current frame
> > > > + *
> > > > + * This method should be called in the libcamera::ipa::Algorithm::process()
> > > > + * method of the platform layer for each frame.
> > > > + *
> > > > + * Contrast value supplied in the \p currentContrast parameter can be platform
> > >
> > > We use \a for function parameters, not \p. I'm not sure if one of the
> > > two is intrinsincly better than the other, but we should be consistent.
> > >
> > > This comment applies to the whole patch series, where applicable.
> >
> > I will go through the series and change that.
> >
> > > > + * specific. The only requirement is the contrast value must increase with
> > > > + * the increasing image focus. Contrast value must be highest when image is in
> > > > + * focus.
> > > > + *
> > > > + * \return New lens position calculated by the AF algorithm
> > > > + */
> > > > +int32_t AfHillClimbing::process(double currentContrast)
> > > > +{
> > > > +     currentContrast_ = currentContrast;
> > > > +
> > > > +     if (shouldSkipFrame())
> > > > +             return lensPosition_;
> > > > +
> > > > +     switch (mode_) {
> > > > +     case controls::AfModeManual:
> > > > +             /* Nothing to process. */
> > > > +             break;
> > > > +     case controls::AfModeAuto:
> > > > +             processAutoMode();
> > > > +             break;
> > > > +     case controls::AfModeContinuous:
> > > > +             processContinuousMode();
> > > > +             break;
> > > > +     }
> > > > +
> > > > +     return lensPosition_;
> > > > +}
> > > > +
> > > > +void AfHillClimbing::processAutoMode()
> > > > +{
> > > > +     if (state_ == controls::AfStateScanning) {
> > > > +             afCoarseScan();
> > > > +             afFineScan();
> > >
> > > The two functions are always called together, and they're both fairly
> > > small. I'd combine them into a single afScan().
> >
> > I will try to improve that.
> >
> > > > +     }
> > > > +}
> > > > +
> > > > +void AfHillClimbing::processContinuousMode()
> > > > +{
> > > > +     /* If we are in a paused state, we won't process the stats. */
> > > > +     if (pauseState_ == controls::AfPauseStatePaused)
> > > > +             return;
> > > > +
> > > > +     if (state_ == controls::AfStateScanning) {
> > > > +             afCoarseScan();
> > > > +             afFineScan();
> > > > +             return;
> > > > +     }
> > > > +
> > > > +     /*
> > > > +      * AF scan can be started at any moment in AfModeContinuous,
> > > > +      * except when the state is already AfStateScanning.
> > > > +      */
> > > > +     if (afIsOutOfFocus())
> > > > +             afReset();
> > > > +}
> > > > +
> > > > +/**
> > > > + * \brief Request AF to skip n frames
> > > > + * \param[in] n Number of frames to be skipped
> > > > + *
> > > > + * For the requested number of frames, the AF calculation will be skipped
> > > > + * and lens position will not change. The platform layer still needs to
> > > > + * call process() function for each frame during this time.
> > >
> > > s/call process() function/call the process() function/
> > >
> > > > + * This function can be used by the platform layer if the hardware needs more
> > > > + * time for some operations.
> > > > + *
> > > > + * The number of the requested frames (\p n) will be applied only if \p n has
> > > > + * higher value than the number of frames already requested to be skipped.
> > > > + * For example, if *skipFrames(5)* was already called for the current frame,
> > >
> > > Code spans use back-quotes, see
> > > https://www.doxygen.nl/manual/markdown.html#md_codespan.
> > >
> > > > + * then calling *skipFrames(3)* will not override the previous request
> > > > + * and 5 frames will be skipped.
> > > > + */
> > > > +void AfHillClimbing::skipFrames(uint32_t n)
> > > > +{
> > > > +     if (n > framesToSkip_)
> > > > +             framesToSkip_ = n;
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setMode(controls::AfModeEnum mode)
> > > > +{
> > > > +     if (mode == mode_)
> > > > +             return;
> > > > +
> > > > +     LOG(Af, Debug) << "Switched AF mode from " << mode_ << " to " << mode;
> > > > +     mode_ = mode;
> > > > +
> > > > +     state_ = controls::AfStateIdle;
> > > > +     pauseState_ = controls::AfPauseStateRunning;
> > > > +
> > > > +     if (mode_ == controls::AfModeContinuous)
> > > > +             afReset();
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setRange([[maybe_unused]] controls::AfRangeEnum range)
> > > > +{
> > > > +     LOG(Af, Error) << "setRange() not implemented!";
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setSpeed([[maybe_unused]] controls::AfSpeedEnum speed)
> > > > +{
> > > > +     LOG(Af, Error) << "setSpeed() not implemented!";
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setMeteringMode([[maybe_unused]] controls::AfMeteringEnum metering)
> > > > +{
> > > > +     LOG(Af, Error) << "setMeteringMode() not implemented!";
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setWindows([[maybe_unused]] Span<const Rectangle> windows)
> > > > +{
> > > > +     LOG(Af, Error) << "setWindows() not implemented!";
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setTrigger(controls::AfTriggerEnum trigger)
> > > > +{
> > > > +     if (mode_ != controls::AfModeAuto) {
> > > > +             LOG(Af, Warning)
> > > > +                     << "setTrigger() not valid in mode " << mode_;
> > > > +             return;
> > > > +     }
> > > > +
> > > > +     LOG(Af, Debug) << "Trigger called with " << trigger;
> > > > +
> > > > +     switch (trigger) {
> > > > +     case controls::AfTriggerStart:
> > > > +             afReset();
> > > > +             break;
> > > > +     case controls::AfTriggerCancel:
> > > > +             state_ = controls::AfStateIdle;
> > > > +             break;
> > > > +     }
> > >
> > > All this logic seems to implement requirements set by the AF controls
> > > definitions, not specific to this class. Should it be moved to the base
> > > AF class ? Same for setPause().
> >
> > There was a discussion on similar topic in the previous version. Conclusion was
> > that at this point it is hard to decide what will be completely reusable by
> > other implementations, so only the interface is defined in the Af and most of
> > the implementation is done in the AfHillClimbing. We can move parts of the code
> > to the Af later, when more things become clear.
>
> OK, let's keep code here, and move it later if useful.
>
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setPause(controls::AfPauseEnum pause)
> > > > +{
> > > > +     if (mode_ != controls::AfModeContinuous) {
> > > > +             LOG(Af, Warning)
> > > > +                     << "setPause() not valid in mode " << mode_;
> > > > +             return;
> > > > +     }
> > > > +
> > > > +     switch (pause) {
> > > > +     case controls::AfPauseImmediate:
> > > > +             pauseState_ = controls::AfPauseStatePaused;
> > > > +             break;
> > > > +     case controls::AfPauseDeferred:
> > > > +             LOG(Af, Warning) << "AfPauseDeferred is not supported!";
> > > > +             break;
> > > > +     case controls::AfPauseResume:
> > > > +             pauseState_ = controls::AfPauseStateRunning;
> > > > +             break;
> > > > +     }
> > > > +}
> > > > +
> > > > +void AfHillClimbing::setLensPosition(float lensPosition)
> > > > +{
> > > > +     if (mode_ != controls::AfModeManual) {
> > > > +             LOG(Af, Warning)
> > > > +                     << "setLensPosition() not valid in mode " << mode_;
> > > > +             return;
> > > > +     }
> > > > +
> > > > +     lensPosition_ = static_cast<int32_t>(lensPosition);
> > >
> > > The LensPosition control is defined in dioptres units. Unless I'm
> > > mistaken, the implementation in this class doesn't match that. This
> > > should be fixed, not necessarily with a fully calibrated implementation,
> > > but at least to map 0.0 to infinity and the maximum value of the lens
> > > position to the closest possible focus.
> >
> > Ok, so just for confirmation. For example, for the VCM driver that I use,
> > the V4L2_CID_FOCUS_ABSOLUTE values are in 0-1023 range and V4L documentation
> > specifies that positive values set the focus closer to the camera.
> > In this case, the LensPosition will simply map to 0.0 - 1023.0.
> > Do I understand your approach correctly?
>
> That sounds good, but you need to ensure that the minimum value of the
> V4L2 focus control maps to 0.0. If another VCM driver reports a
> different range than 0-1023, that should be handled. 1023.0 as a maximum
> would mean focussing at ~1mm from the camera, which is very, very close.
> The focus lens isn't calibrated at the moment, and that's OK, but I'd
> rather map the maximum to something more sensible, maybe 1m or 50cm, so
> 1.0 or 2.0.

I initially thought about just shifting the raw values to the right, so the
min = 0.0 and max = 0 + (lens_max -  lens_min). But maybe using the fixed range,
e.g. [0.0; 1.0] is simpler, as I would only need to convert the values in
one place.

>
> > > > +
> > > > +     LOG(Af, Debug) << "Requesting lens position " << lensPosition_;
> > > > +}
> > > > +
> > > > +void AfHillClimbing::afCoarseScan()
> > > > +{
> > > > +     if (coarseCompleted_)
> > > > +             return;
> > > > +
> > > > +     if (afScan(coarseSearchStep_)) {
> > > > +             coarseCompleted_ = true;
> > > > +             maxContrast_ = 0;
> > > > +             const auto diff = static_cast<int32_t>(
> > > > +                     std::abs(lensPosition_) * fineRange_);
> > > > +             lensPosition_ = std::max(lensPosition_ - diff, minLensPosition_);
> > > > +             maxStep_ = std::min(lensPosition_ + diff, maxLensPosition_);
> > >
> > > I think the intent here it to set the scan range to [coarse position -
> > > diff, coarse position + diff], but as you modify lensPosition_ first,
> > > you effectively set it to [coarse position - diff, coarse position].
> >
> > You are right... I will fix that :)
> >
> > > Reading the code, maxStep_ seems to store a lens position, not a step.
> > > Is this correct ? If so, please rename the variable accordingly.
> >
> > Yes, this is correct.
> >
> > > > +     }
> > > > +}
> > > > +
> > > > +void AfHillClimbing::afFineScan()
> > > > +{
> > > > +     if (!coarseCompleted_)
> > > > +             return;
> > > > +
> > > > +     if (afScan(fineSearchStep_)) {
> > > > +             LOG(Af, Debug) << "AF found the best focus position!";
> > > > +             state_ = controls::AfStateFocused;
> > > > +     }
> > > > +}
> > > > +
> > > > +bool AfHillClimbing::afScan(uint32_t steps)
> > > > +{
> > > > +     if (lensPosition_ + static_cast<int32_t>(steps) > maxStep_) {
> > > > +             /* If the max step is reached, move lens to the position. */
> > > > +             lensPosition_ = bestPosition_;
> > > > +             return true;
> > > > +     }
> > > > +
> > > > +     /*
> > > > +      * Find the maximum of the variance by estimating its derivative.
> > > > +      * If the direction changes, it means we have passed a maximum one step
> > > > +      * before.
> > > > +      */
> > > > +     if ((currentContrast_ - maxContrast_) >= -(maxContrast_ * 0.1)) {
> > > > +             /*
> > > > +              * Positive and zero derivative:
> > > > +              * The variance is still increasing. The focus could be
> > > > +              * increased for the next comparison. Also, the max variance
> > > > +              * and previous focus value are updated.
> > > > +              */
> > > > +             bestPosition_ = lensPosition_;
> > > > +             lensPosition_ += static_cast<int32_t>(steps);
> > > > +             maxContrast_ = currentContrast_;
> > > > +     } else {
> > > > +             /*
> > > > +              * Negative derivative:
> > > > +              * The variance starts to decrease, which means the maximum
> > > > +              * variance is found. Set focus step to previous good one,
> > > > +              * then return immediately.
> > >
> > > Isn't this very prone to stopping on a local extremum ?
> >
> > It is, and this is intended. When there are two objects on the scene, We will
> > just focus on the one closer to the camera. It is mitigated a bit, by setting
> > the threshold required to stop scanning to (maxContrast_ * 0.1).
>
> OK. Please document this design decision in a comment in the code
> (the documentation block of the AfHillClimb class seems to be a good
> place).
>
> > To find global maximum We would need to scan the whole range which takes more
> > time. I hope we will see such implementation in the near future, so it
> > will be possible to choose between time and effectiveness :)
> >
> > Thank you for that question, because when I analyzed the code again, I found
> > another problem :P maxContrast_ can be overwritten by a lower value,
> > near the top,
> > when contrast difference is smaller than (maxContrast_ * 0.1).
> >
> > > > +              */
> > > > +             lensPosition_ = bestPosition_;
> > > > +             return true;
> > > > +     }
> > > > +
> > > > +     LOG(Af, Debug) << "Previous step is " << bestPosition_
> > > > +                    << ", Current step is " << lensPosition_;
> > >
> > > s/step/position/
> > >
> > > > +     return false;
> > > > +}
> > > > +
> > > > +void AfHillClimbing::afReset()
> > > > +{
> > > > +     LOG(Af, Debug) << "Reset AF parameters";
> > > > +     lensPosition_ = minLensPosition_;
> > > > +     maxStep_ = maxLensPosition_;
> > > > +     state_ = controls::AfStateScanning;
> > > > +     coarseCompleted_ = false;
> > > > +     maxContrast_ = 0.0;
> > > > +     skipFrames(1);
> > > > +}
> > > > +
> > > > +bool AfHillClimbing::afIsOutOfFocus() const
> > > > +{
> > > > +     const double diff_var = std::abs(currentContrast_ - maxContrast_);
> > > > +     const double var_ratio = diff_var / maxContrast_;
> > > > +     LOG(Af, Debug) << "Variance change rate: " << var_ratio
> > > > +                    << ", Current lens step: " << lensPosition_;
> > >
> > > s/Current/current/
> > > s/step/position/
> > >
> > > > +     return var_ratio > maxChange_;
> > > > +}
> > > > +
> > > > +bool AfHillClimbing::shouldSkipFrame()
> > > > +{
> > > > +     if (framesToSkip_ > 0) {
> > > > +             framesToSkip_--;
> > > > +             return true;
> > > > +     }
> > > > +
> > > > +     return false;
> > > > +}
> > > > +
> > > > +} /* namespace ipa::algorithms */
> > > > +
> > > > +} /* namespace libcamera */
> > > > diff --git a/src/ipa/libipa/algorithms/af_hill_climbing.h b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > > > new file mode 100644
> > > > index 00000000..2147939b
> > > > --- /dev/null
> > > > +++ b/src/ipa/libipa/algorithms/af_hill_climbing.h
> > > > @@ -0,0 +1,91 @@
> > > > +/* SPDX-License-Identifier: LGPL-2.1-or-later */
> > > > +/*
> > > > + * Copyright (C) 2021, Red Hat
> > > > + * Copyright (C) 2022, Ideas On Board
> > > > + * Copyright (C) 2023, Theobroma Systems
> > > > + *
> > > > + * af_hill_climbing.h - AF contrast based hill climbing common algorithm
> > > > + */
> > > > +
> > > > +#pragma once
> > > > +
> > > > +#include <libcamera/base/log.h>
> > > > +
> > > > +#include "af.h"
> > > > +
> > > > +namespace libcamera {
> > > > +
> > > > +class YamlObject;
> > > > +
> > > > +namespace ipa::algorithms {
> > > > +
> > > > +LOG_DECLARE_CATEGORY(Af)
> > > > +
> > > > +class AfHillClimbing : public Af
> > > > +{
> > > > +public:
> > > > +     int init(int32_t minFocusPosition, int32_t maxFocusPosition,
> > > > +              const YamlObject &tuningData);
> > > > +     int32_t process(double currentContrast);
> > > > +     void skipFrames(uint32_t n);
> > > > +
> > > > +     controls::AfStateEnum state() override { return state_; }
> > > > +     controls::AfPauseStateEnum pauseState() override { return pauseState_; }
> > > > +
> > > > +private:
> > > > +     void setMode(controls::AfModeEnum mode) override;
> > > > +     void setRange(controls::AfRangeEnum range) override;
> > > > +     void setSpeed(controls::AfSpeedEnum speed) override;
> > > > +     void setMeteringMode(controls::AfMeteringEnum metering) override;
> > > > +     void setWindows(Span<const Rectangle> windows) override;
> > > > +     void setTrigger(controls::AfTriggerEnum trigger) override;
> > > > +     void setPause(controls::AfPauseEnum pause) override;
> > > > +     void setLensPosition(float lensPosition) override;
> > > > +
> > > > +     void processAutoMode();
> > > > +     void processContinuousMode();
> > > > +     void afCoarseScan();
> > > > +     void afFineScan();
> > > > +     bool afScan(uint32_t steps);
> > > > +     void afReset();
> > > > +     [[nodiscard]] bool afIsOutOfFocus() const;
> > > > +     bool shouldSkipFrame();
> > > > +
> > > > +     controls::AfModeEnum mode_ = controls::AfModeManual;
> > > > +     controls::AfStateEnum state_ = controls::AfStateIdle;
> > > > +     controls::AfPauseStateEnum pauseState_ = controls::AfPauseStateRunning;
> > > > +
> > > > +     /* Current focus lens position. */
> > > > +     int32_t lensPosition_ = 0;
> > > > +     /* Local optimum focus lens position during scanning. */
> > > > +     int32_t bestPosition_ = 0;
> > > > +
> > > > +     /* Current AF statistic contrast. */
> > > > +     double currentContrast_ = 0;
> > > > +     /* It is used to determine the derivative during scanning */
> > > > +     double maxContrast_ = 0;
> > > > +     /* The designated maximum range of focus scanning. */
> > > > +     int32_t maxStep_ = 0;
> > > > +     /* If the coarse scan completes, it is set to true. */
> > > > +     bool coarseCompleted_ = false;
> > > > +
> > > > +     uint32_t framesToSkip_ = 0;
> > > > +
> > > > +     /* Position limits of the focus lens. */
> > > > +     int32_t minLensPosition_;
> > > > +     int32_t maxLensPosition_;
> > > > +
> > > > +     /* Minimum position step for searching appropriate focus. */
> > > > +     uint32_t coarseSearchStep_;
> > > > +     uint32_t fineSearchStep_;
> > > > +
> > > > +     /* Fine scan range 0 < fineRange_ < 1. */
> > > > +     double fineRange_;
> > > > +
> > > > +     /* Max ratio of variance change, 0.0 < maxChange_ < 1.0. */
> > > > +     double maxChange_;
> > > > +};
> > > > +
> > > > +} /* namespace ipa::algorithms */
> > > > +
> > > > +} /* namespace libcamera */
> > > > diff --git a/src/ipa/libipa/algorithms/meson.build b/src/ipa/libipa/algorithms/meson.build
> > > > index 3df4798f..20e437fc 100644
> > > > --- a/src/ipa/libipa/algorithms/meson.build
> > > > +++ b/src/ipa/libipa/algorithms/meson.build
> > > > @@ -2,8 +2,10 @@
> > > >
> > > >  libipa_algorithms_headers = files([
> > > >      'af.h',
> > > > +    'af_hill_climbing.h',
> > > >  ])
> > > >
> > > >  libipa_algorithms_sources = files([
> > > >      'af.cpp',
> > > > +    'af_hill_climbing.cpp',
> > > >  ])
>
> --
> Regards,
>
> Laurent Pinchart

Best regards
Daniel